Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы


  Аппроксимация изображений генетическим



Download 9,87 Mb.
Pdf ko'rish
bet197/228
Sana20.06.2022
Hajmi9,87 Mb.
#683557
TuriКнига
1   ...   193   194   195   196   197   198   199   200   ...   228
Bog'liq
Algorithms3

6.4. 
Аппроксимация изображений генетическим 
алгоритмом при помощи EvoJ 
В этом разделе рассматривается вопрос, как можно применить 
генетический алгоритм для аппроксимации изображений 
полигонами.


А.Е. Кононюк Дискретно-непрерывная математика 
361 
6.4.1. Выбор способа описания решения 
Следуя традиционному пути решения задач при помощи EvoJ, для 
начала выберем как мы опишем решения для нашей задачи. 
Прямолинейным решением будет описать аппроксимацию как простой 
список полигонов: 
public interface PolyImage { 
List
 getCells(); 

Такой подход имеет право на жизнь, нам вполне удастся подобрать 
удовлетворительную картинку рано или поздно. Cкорее всего поздно
так как такой подход снижает эффективность скрещивания хороших 
решений. И вот почему. 


А.Е. Кононюк Дискретно-непрерывная математика 
362 
Представим для простоты следующую картинку. 
Допустим у нас в генофонде есть два хороших решения, каждое из 
которых отличается от идеального на один полигон.


А.Е. Кононюк Дискретно-непрерывная математика 
363 
Обратите внимание на одну особенность: в обоих случаях полигон 
номер 0 идеально совпадает с одним из полигонов изображения, тогда 
когда другой лежит где-то в стороне. Был бы здорово скрестить эти два 
решения таким образом, чтобы в результате вместе оказались два 
первых полигона из обоих решений, однако это не возможно — EvoJ 
отображает все переменные на байтовый массив и при скрещивании 
работает с байтами, не меняя порядка их следования. 
Процесс кроссинговера разъясняется на следующем рисунке. 
Таким образом два элемента с одинаковым индексом никак не могут 
оказаться в результирующем решении.
Результат скрещивания скорее всего будет выглядеть так: 


А.Е. Кононюк Дискретно-непрерывная математика 
364 
Что сильно скажется на эффективности скрещивания, значительно 
замедлив эволюцию. 
Обойти проблему можно, «правильно» засеяв исходную популяцию — 
равномерно распределив полигоны по области изображения, таким 
образом, чтобы расположение полигона в списке, согласовывалось с 
его геометрическим расположением на рисунке. При этом придется 
ограничить мутацию, чтобы полигоны не могли слишком далеко 
«переползти». 
Более продвинутый подход заключается в изначальном разделении 
изображения на ячейки, с назначением каждой ячейке собственного 
списка полигонов. В виде интерфейса Java это описывается так: 
public interface PolyImage { 
Colour getBkColor(); 
List>> getCells(); 

Внешний список задает ряды ячеек, следующий по вложенности — 
столбцы, и, наконец, внутренний список — полигоны находящиеся в в 
соответствующей ячейке. Такой подход автоматически обеспечивает 
примерное соответствие положения полигона в байтовом массиве и его 
геометрического места на рисунке. 
Каждый полигон опишем как: 


А.Е. Кононюк Дискретно-непрерывная математика 
365 
public interface Polygon { 
List
 getPoints(); 
Colour getColor(); 
int getOrder(); 

Здесь свойство order определяет глобальный порядок отрисовки 
полигона. Цвет полигона опишем как: 
public interface Colour { 
@MutationRange("0.2") 
@Range(min = "0", max = "1", strict = "true") 
float getRed(); 
@MutationRange("0.2") 
@Range(min = "0", max = "1", strict = "true") 
float getGreen(); 
@MutationRange("0.2") 
@Range(min = "0", max = "1", strict = "true") 
float getBlue(); 
void setRed(float red); 
void setGreen(float green); 
void setBlue(float blue); 

Иными словами, просто как три компоненты цвета, желающие еще 
могут добавить альфа-канал, однако мы будем рисовать все полигоны с 
50% прозрачностью, это снизит число безразличных мутаций. 
Назначение аннотаций здесь очевидно. Точки полигона опишем как: 


А.Е. Кононюк Дискретно-непрерывная математика 
366 
public interface Point { 
int getX(); 
int getY(); 

При этом координаты X и Y будем считать относительно центра 
ячейки, которой принадлежит полигон. Обратите внимание, что 
аннотации регулирующие допустимые значения переменных 
присутствуют только в описании цвета. Это связано с тем, что 
допустимые значения координат зависят от размера изображения и от 
конфигурации ячеек, а допустимые значения компоненты цвета — 
вещи предопределенные. Кроме того, аннотацию на два внутренних 
списка в интерфейсе 
PolyImage
вообще никак повесить нельзя. 
Чтобы задать все необходимые параметры мы воспользуемся 
механизмом под названием Detached
Перейдем к программированию.

Download 9,87 Mb.

Do'stlaringiz bilan baham:
1   ...   193   194   195   196   197   198   199   200   ...   228




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish