Застосування еволюційних алгоритмів для розв'язання задачі апроксимації зображень многокутниками
Loading...
Date
2017
Authors
Глибовець, Микола
Петльована, Марія
Кирієнко, Оксана
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
У статті описано розробку та реалізацію еволюційного алгоритму розв’язку задачі апроксимації
зображення многокутниками, запропоновано структуру даних для ефективного кодування
зображень (зі змінною кількістю рядків та стовпців зображення, кількістю многокутників в одній
клітинці, кількістю точок многокутників та ступенем їх перетинання). Було впроваджено
стратегії мутації для виведення розв’язку з локального оптимуму та подальшого знаходження
глобального оптимуму. Для пришвидшення роботи алгоритму етапи селекції та перевірки критерію
завершення було реалізовано з використанням моделі розподілених обчислень MapReduce.
This article describes a development and implementation of an evolutionary algorithm for solving the problem of image approximation by polygons, a proposed data structure for efficient image coding (with the variable number of image rows and columns, polygons in one cell, polygons points and their intersection degree), an implemented mutation strategies for solving output from a local optimum and further global optimum finding. The selective and verifiable stages of a completion criterion were implemented using the MapReduce by distributing computing model to speed up the algorithm running. The conducted research confirms a perspective of the evolutionary algorithms usage for solving image processing and generating new images problems. In particular, we can propose such algorithm improvements: 1) to highlight a mask of importance of the image areas – a certain image with the accented areas of interest that can be used for the fitness function calculation, which will reduce the noise in the population and concentrate searches on the explorer’s area of the interest; 2) to continue setting up the algorithm parameters – to pick up the optimal algorithm parameters (particularly, setting up mutations in mutation strategies) and to apply the parameter self-adaptation during the evolution; 3) to apply a parallel evolutionary algorithm model, for instance, an island model that allows one to run the algorithm several times at once and to combine the “achievements” of different runs – islands for getting the best solution; 4) the presented algorithm can be transformed into photo-robot generation algorithm by changing the function of comparing the generated image with a benchmark to the interactive user.
This article describes a development and implementation of an evolutionary algorithm for solving the problem of image approximation by polygons, a proposed data structure for efficient image coding (with the variable number of image rows and columns, polygons in one cell, polygons points and their intersection degree), an implemented mutation strategies for solving output from a local optimum and further global optimum finding. The selective and verifiable stages of a completion criterion were implemented using the MapReduce by distributing computing model to speed up the algorithm running. The conducted research confirms a perspective of the evolutionary algorithms usage for solving image processing and generating new images problems. In particular, we can propose such algorithm improvements: 1) to highlight a mask of importance of the image areas – a certain image with the accented areas of interest that can be used for the fitness function calculation, which will reduce the noise in the population and concentrate searches on the explorer’s area of the interest; 2) to continue setting up the algorithm parameters – to pick up the optimal algorithm parameters (particularly, setting up mutations in mutation strategies) and to apply the parameter self-adaptation during the evolution; 3) to apply a parallel evolutionary algorithm model, for instance, an island model that allows one to run the algorithm several times at once and to combine the “achievements” of different runs – islands for getting the best solution; 4) the presented algorithm can be transformed into photo-robot generation algorithm by changing the function of comparing the generated image with a benchmark to the interactive user.
Description
Keywords
еволюційні алгоритми, задачі апроксимації зображення многокутниками, MapReducе, evolutional algorithm
Citation
Глибовець М. М. Застосування еволюційних алгоритмів для розв'язання задачі апроксимації зображень многокутниками / Глибовець М. М., Петльована М. В., Кирієнко О. В. // Наукові записки НаУКМА. Комп'ютерні науки. - 2017. - Т. 198. - С. 21-26.