автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Алгоритмы и программные средства эволюционной обработки изображений



Белоусов Артем Анатольевич

Алгоритмы и программные средства эволюционной обработки изображений

05.13.01 - Системный анализ, управление и обработка информации (отрасль: промышленность)

Автореферат на соискание ученой степени кандидата технических наук

- 9 ЛЕ/{ ?о)о

Томск-2010

004616418

Работа выполнена на кафедре Вычислительной техники Государственного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский политехнический университет».

Научный руководитель:

доктор технических наук, старший научный сотрудник В.Г. Спицын

Официальные оппоненты:

доктор технических наук, профессор Кориков Анатолий Михайлович

Ведущая организация:

Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева

Защита состоится 24 декабря 2010 г. в 14 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.269.06 при Национальном исследовательском Томском политехническом университете по адресу: 634034, г. Томск, ул. Советская, 84, Институт Кибернетики ТПУ, ауд. 214.

С диссертацией можно ознакомиться в научно-технической библиотеке Национального исследовательского Томского политехнического университета по адресу: 634034, г. Томск, ул. Белинского, 55.

Автореферат разослан 23 ноября 2010 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212.169.06

кандидат технических наук, Напрюшкин Александр Алексеевич

к.т.н., доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Применение цифровых изображений началось еще в начале 1920-х годов, когда была реализована передача иллюстраций для газет по трансокеанскому подводному кабелю между Лондоном и Нью-Йорком, позволившая сократить время передачи изображения через Атлантику до 3 часов. А появление компьютеров в середине XX века привело к возникновению новой области науки - цифровой обработки изображений.

Первые компьютеры, обладающие достаточной для обработки изображений мощностью, появились в 60-х годах прошлого века. Одновременно с этим возникла необходимость обработки снимков, получаемых с космических аппаратов. В 1964 году цифровое улучшение качества изображений было впервые применено для исправления искажений на снимках переданных космическим аппаратом «Рейнджер-7», появившихся вследствие особенностей его бортовой камеры. Вслед за этим стали появляться и другие задачи по цифровой обработке изображений, такие как сжатие изображений, сегментация, морфологический анализ и многие другие.

Характерной особенностью многих методов цифровой обработки изображений является проблема формализуемости преобразований. Попытки решения данных задач детерминированными методами часто сталкиваются с различными ограничениями, такими как сложность формального представления преобразований, наличие большого количества параметров и отсутствие эталонного решения. В процессе развития методов и средств обработки изображений стали появляться методы обработки изображений, основанные на применении новых концепций поиска решений в вычислительных системах. Одной из таких концепций явились эволюционные вычисления.

Идеи применения принципов естественного отбора для решения задач впервые были опубликованы Джоном Холландом в начале 60-х годов

3

прошлого века, однако широкое признание и распространение получили после опубликования в 1975 году его классической работы о генетических алгоритмах под названием «Адаптация в естественных и искусственных системах». Эта работа является основополагающей в области исследования генетических алгоритмов. В ней же была сформулирована и доказана теорема схем, дающая обоснование эффективности генетических алгоритмов. Теорема схем доказывает происходящее при смене поколений экспоненциальное распространение хорошо приспособленных схем с малыми порядком и определяющей длиной. Эта теорема была дополнена гипотезой строительных блоков Гольдберга в 1989 году. Работы Рехенберга 1973 года и Швефеля 1981 года описывают эволюционные стратегии, а Фогель, Оуэне и Уолш в 1966 году описали эволюционное программирование. Работы в области эволюционных вычислений велись и в России. В основном эти исследования опирались на работы по самообучающимся системам и стохастической оптимизации. В результате исследований эволюционных вычислений в целом и генетических алгоритмов в частности была показана их высокая эффективность при решении задач многопараметрической оптимизации.

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

Применение генетических алгоритмов в таких задачах позволяет находить решения даже при неизвестной форме преобразования, например при подборе структуры и весов нейронной сети при нейро-эволюционном подходе к улучшению изображений. Для работы генетического алгоритма достаточно возможности формального представления решений и критерия

4

оценки результата. При этом за счет наличия стохастической составляющей ГА обладают достаточно широким пространством поиска, а за счет механизма наследования позволяют сохранить свойства близких к оптимальным решений.

Таким образом, можно сделать вывод об актуальности исследования методов обработки изображений, основанных на эволюционных вычислениях.

Исследования и разработки по теме диссертационной работы проводились в соответствии с утвержденным планом НИР Института «Кибернетический центр» ТПУ в рамках проекта "Разработка технологии автоматизированного улучшения качества цифровых изображений на основе применения эволюционирующей нейронной сети" поддержанного грантом РФФИ № 06-08-00840 (2006 - 2008 гг.), проекта «Создание программного комплекса автоматизированной обработки изображений и распознавания образов на основе применения искусственных нейронных сетей, регуляторных сетей и эволюционных алгоритмов» поддержанного грантом РФФИ № 09-08-00309 (2009 - 2011 гг.), а также поддержаны грантами по программам «У.М.Н.И.К.» и «Microsoft Бизнес-Старт» Фонда содействия развитию малых форм предприятий в научно-технической сфере

Тема диссертационной работы утверждена на Совете Института «Кибернетический Центр» (протокол № 10 от 24.11.2007 г.).

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

Для достижения поставленной цели необходимо последовательное решение следующих задач:

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

5

2. Выбор и исследование операторов и модели генетического алгоритма, наиболее подходящих для решения задач обработки цифровых изображений.

3. Разработка алгоритма обработки изображений, основанного на ГА, с учетом результатов решения предыдущих задач. Решение данной задачи предполагает также исследование эффективности применения разработанного алгоритма.

4. Разработка и адаптация дополнительных этапов обработки для повышения скорости или качества обработки. Исследование эффективности применения выбранных дополнительных этапов обработки.

5. Апробация разработанного алгоритма для решения задачи улучшения визуального качества изображений.

Методы исследований. В работе использованы методы математической статистики, теории оптимизации, цифровой обработки изображений, теории информации, мягких вычислений, технологий программирования.

Научную новизну полученных в диссертации результатов определяют:

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

■ усиление контраста на основе модели "Освещенность-Отраженность",

■ выравнивание гистограмм изображений,

■ адаптивное масштабирование изображений.

2. Упрощенная функция преобразования изображений, позволившая сократить затраты времени на вычисление локальных характеристик и повысить качество обработки.

3. Модифицированная оценка качества изображений, учитывающая особенности человеческого зрения и алгоритма обработки изображений.

4. Адаптивный способ масштабирования изображений, позволяющий ускорить поиск решения генетическим алгоритмом за счет сокращения времени преобразования уменьшенных копий изображения и оценки их качества.

Практическая ценность н реализация результатов работы. Практически значимыми являются методы, алгоритмы, аналитические оценки и формулы, разработанные и полученные в результате диссертационного исследования.

Разработанные программные средства для обработки изображений используются в ООО НПП «Томская электронная компания» для обработки снимков микроструктуры металла шлифов на этапе их предварительной подготовки для анализа микроструктуры. Кроме того, внедренное программное обеспечение применяется в отделе маркетинга для автоматического улучшения фотоснимков низкого качества, полученных в промышленных условиях. Результаты внедрения подтверждены соответствующим актом. Кроме того планируется широкое распространение разработанных программных средств для конечных пользователей. Потенциальными потребителями разработанных продуктов являются исследовательские организации, производящие обработку цифровых снимков в различных областях (металлографии, дефектоскопии, техническом зрении, дистанционном зондировании), а также пользователи, производящие обработку фотоснимков низкого качества для личного пользования.

Основные положения, выносимые на защиту:

1. Комплексный метод повышения визуального качества цифровых изображений позволяет достаточно быстро и эффективно улучшать качество изображений. Результаты обработки по ряду параметров превосходят известные аналоги.

2. Применение предобработки изображения при помощи I-R (Illuminance-Reflectance) алгоритма и алгоритма выравнивания гистограмм позволяет повысить скорость обработки за счет исключения из ядра

7

преобразования изображений среднеквадратического отклонения по окрестности. Качество обработки при этом повышается.

3. Модифицированная оценка качества изображений позволяет учитывать особенности человеческого зрения и особенности функционирования алгоритма.

4. Адаптивное масштабирование изображений позволяет значительно сократить время обработки изображений без существенных потерь качества обработки в тех случаях, когда исходное изображение обладает достаточной энтропией.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих симпозиумах, конференциях и семинарах: XIII Международный симпозиум «Оптика атмосферы и океана. Физика атмосферы» (г. Томск, 2006 г.), IV и V Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, 2006 и 2007 г.), XIII и XIV Международная научно-практическая конференция студентов, аспирантов и молодых ученых «Современные техника и технологии» (г. Томск, 2007 и 2008 г.), VI Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (г. Томск, 2009 г.).

По результатам диссертационных исследований опубликовано 11 работ.

Личный вклад:

1. Постановка задач диссертационного исследования выполнена автором совместно с В.Г. Спицыным.

2. Модификация оценки качества изображений для целевой функции генетического алгоритма и ядра преобразования изображений выполнена автором.

3. Формирование критериев сравнения моделей ГА применительно к решаемой задаче выполнено автором. Им же произведено

8

экспериментальное исследование трех моделей ГА и произведен выбор наиболее подходящей из них для реализации.

4. Исследование и модификация алгоритма выравнивания гистограмм выполнена автором.

5. Исследование и реализация метода на основе модели Освещенность-Отраженность выполнена автором совместно с

A.Ю. Шековым.

6. Постановка задачи исследования возможности масштабирования обрабатываемых изображений выполнена автором совместно с

B.Г. Спицыным и Ю.Р. Цоем.

7. Модификация генетического алгоритма улучшения цифровых изображений после внедрения предварительных этапов обработки и адаптивного масштабирования изображений произведена автором.

8. Исследование методов металлографических исследований и адаптация разработанного алгоритма для задачи исследования макро- и микроструктуры металлических шлифов произведены автором.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 138 наименования и приложения. Объем основного текста диссертации составляет 168 страниц машинописного текста, иллюстрированного 31 рисунком и 25 таблицами.

Содержание работы

Во введении обосновывается актуальность темы диссертационной работы, формулируется цель и задачи исследования и приводится краткое содержание работы по главам.

В первой главе представлен обзор различных методов цифровой обработки изображений. Приведена классификация областей применения цифровой обработки изображений по типу используемых изображений.

Представлен аналитический обзор эволюционного подхода к решению различных задач. Описаны основные операторы генетического алгоритма и

9

возможные варианты их реализации. Рассмотрены и различные модели генетических алгоритмов, существующие на данный момент. Сделаны выводы о достоинствах существующих моделей ГА, использованные в дальнейших исследованиях в главе 2.

Проанализированы возможности применения ГА для решения различных задач обработки изображений. Рассмотрены основные проблемы, присущие задачам обработки цифровых изображений. Приведены конкретные примеры применения ГА для решения задач улучшения визуального качества изображений, распознавания образов и обработки медицинских изображений.

Применительно к задаче улучшения изображений рассмотрены варианты преобразования яркостей точек и различные способы оценки изображений. Проанализированы параметры изображений, которые возможно формально оценить.

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

1. быстрая сходимость к решениям, близким к оптимальным;

2. наличие возможности регулировки направления поиска решений извне через влияние на генетический алгоритм или внутренние процедуры;

3. минимальное количество вычислений целевой функции ввиду ее высокой вычислительной сложности;

4. представление генов в целочисленном виде с возможностью использования как чисел с плавающей запятой.

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

Приведено описание схемы алгоритма и основных функций, применяемых при обработке. Рассмотрены недостатки функции преобразования яркостей точек и предложены варианты их устранения. Описаны необходимые модификации оценки целевой функции алгоритма для повышения качества обработки.

В разработанном алгоритме каждая особь кодирует параметры а, Ь, с и к функции преобразования изображений (1), значения которых необходимо подобрать с помощью генетического алгоритма. При этом на этапе оценки особи производится преобразование изображения по формуле (1) с параметрами, закодированными в этой особи, а затем производится оценка особи по формуле (2). Количество (г](1')) и интенсивность (Е(1)) краевых пикселей, используемые в формуле (2) рассчитываются при помощи оператора Собеля, мера энтропии Н(1) вычисляется по формуле (3), а уровень адаптации к зрению человека по яркости при помощи формулы (4). Параметр ОС определяет количество превышений максимально допустимого значения яркости и позволяет избежать преобразований, приводящих к «вырождению» изображения.

g(x,y) = T(f(x,y)) =

М ^

а(х,у) + Ь)

lf(x,y) - ст(х,у)] + т{х,у)а\

х = O...Hslze -1; (1)

y = 0..Wme-l,

где g(x, у) и f(x, у) - полученная и исходная яркость точки с координатами (х, у), М - глобальное среднее значение яркости изображения, т(х, у) -среднее значение яркости в окрестности п*п, а(х, у) - значение среднеквадратического отклонения в этой же окрестности, a Wsize и — ширина и высота изображения соответственно.

F(x) - ln(ln(E(/)) + е) Ц{11 eH{n -LQ-OC (2)

Н 'W

те size

П

#(/) = 2>(0;

/

v,.log2(v,.), V,*0 (3)

u(i) = ,

l0,v,=0

где v, - частота встречаемости пикселей, имеющих уровни градаций яркости между граничными значениями А, и В,.

LQ = \-L~L(4)

max ' ^

где L - средняя яркость по изображению, a Lmax - максимальное возможное значение яркости.

На основе анализа алгоритма и сформулированных в главе 1 требований к нему выбраны возможные модели генетических алгоритмов. Приведено их детальное описание и выбраны критерии сравнения моделей применительно к поставленным задачам.

Описаны эксперименты, проведенные для выбора модели ГА. На основе результатов экспериментов показано, что модель СНС (Cross generational elitist selection, Heterogeneous recombination, Cataclysmic mutation) является несколько быстрее остальных (на 3,9 % быстрее канонической модели и на 4,7% быстрее модели Генитор), однако ввиду отсутствия мутации на основной фазе работы алгоритма и меньшего размера популяции имеет меньшее пространство поиска, что приводит к более низкой приспособленности найденного решения. Модель Генитор, напротив, обладает наиболее низким быстродействием из-за высоких накладных расходов на операторы ГА, однако дает значительно лучшие результаты. По суммарным показателям модель Генитор является наилучшей моделью ГА применительно к данной задаче.

Далее во второй главе приводятся результаты анализа быстродействия разработанного алгоритма и выявляются наиболее ресурсоемкие этапы обработки. На основе результатов анализа и экспериментов показано, что наибольшие затраты на обработку приходятся на вычисление локальных

характеристик (более 63 % общего времени обработки) и преобразование изображений (более 28 % времени). Предложены варианты сокращения времени обработки на основе применения предварительных этапов для исключения среднеквадратического отклонения из функции преобразования яркостей точек и снижения затрат времени на расчет локальных характеристик. Для снижения затрат времени на преобразование изображения предложена обработка уменьшенной копии изображения, с последующим применением преобразования яркости с найденными параметрами к исходному изображению.

Приведено описание и исследование метода повышения контрастности изображения на основе модели Освещенность-Отраженность (Illuminance-Reflectance, I-R). На основе результатов экспериментов показано, что применение данной модели значительно повышает количество и интенсивность краевых пикселей. Обоснован выбор параметров данного преобразования.

Описан метод выравнивания гистограмм, позволяющий повысить как количество и интенсивность краевых пикселей, так и уровень адаптации к зрению человека по яркости. Описаны недостатки этого метода и ограничения на максимальную и минимальную разницу между соседними градациями яркости, введенные для устранения этих недостатков.

Приведена схема использования описанных методов в качестве предварительных этапов обработки. Исследовано влияние такой схемы применения на скорость и результат окончательной обработки. На основе экспериментов показано, что применение выравнивания гистограмм и I-R алгоритма для предобработки изображений с одновременным исключением среднеквадратического отклонения из ядра преобразования приводит к сокращению времени обработки изображения в среднем на 41,8 %, при этом значение комплексной оценки качества удалось повысить приблизительно в 3 раза.

Приведены результаты исследования возможности масштабирования исходного изображения для сокращения времени на поиск решения генетическим алгоритмом. Исследована зависимость снижения качества обработки при масштабировании от различных параметров исходного изображения, таких как размер изображения, средняя яркость, значение комплексных оценок и ее составляющих. Выявлено, что подобный этап может быть применен только к изображениям, обладающим достаточно большой энтропией, в противном случае наблюдается значительное снижение качества обработки. Для сохранения качества обработки на уровне не менее 90 % по сравнению с обработкой немасштабированного изображения необходимо применять масштабирование только к тем изображениям, исходная энтропия которых составляет не менее 6,22. Описана схема использования масштабирования в итоговом алгоритме.

В третьей главе приведено полное описание разработанных программных средств и результаты их тестирования. Описываются методы и средства, примененные при реализации библиотеки для эволюционной обработки изображений и программных средств.

Сформулированы требования к библиотеке функций, реализующей разработанный алгоритм. Описывается набор принципов проектирования классов SOLID, использованный для разработки архитектуры библиотеки GeneticEnhancer.

Произведен анализ доступных средств разработки и на основе анализа выбраны языки программирования для реализации библиотеки. Для разработки была выбрана платформа Microsoft .Net Framework и языки программирования Visual С++ и Visual С#, поскольку они отвечают всем сформулированным требованиям.

Описывается технология ОрепМР, использованная для параллельной обработки массивов данных. Произведено исследование влияния применения данной технологии на время обработки. Показано, что применение параллельных вычислений для преобразования изображений и

14

нахождения значения целевой функции позволяет сократить время обработки приблизительно на 10 %.

Приведено детальное описание структуры классов разработанной библиотеки, включающей 3 основных группы классов:

1. классы, обеспечивающие логику работы ГА;

2. классы, обеспечивающие логику оценки изображений;

3. вспомогательные классы.

Приведено описание разработанных программных средств автоматизированного тестирования методов обработки изображений. Описана программа улучшения визуального качества изображений для конечных пользователей. Перечислены функции и возможности каждой из этих программ.

В четвертой главе приведено описание задач металлографии, решаемых с использованием цифровых изображений. Описываются методы исследования макро- и микроструктуры металлических шлифов.

Получаемые в металлографии снимки, в частности снимки микроструктуры, используемые в отделе металловедения ООО НПП «Томская электронная компания» обладают рядом особенностей, которые необходимо учитывать при обработке. Ключевая особенность снимков, полученных через окуляр микроскопа, является круглая форма информативной области и черная рамка вокруг нее. Эта рамка не является абсолютно черной, в ней встречаются различные градации яркости от 0 до 5, однако эти градации не различимы невооруженным глазом. Такая особенность изображений значительно влияет на все предварительные и основные этапы обработки, а в особенности на выравнивание гистограммы и вычисление энтропии, поскольку они зависят от частоты встречаемости различных градаций яркости, а наличие черной рамки приводит к появлению чрезвычайно большой доли неинформативных точек с низкими градациями яркости. Для учета этой особенности снимков на стадии извлечения яркостей

все точки рамки помечаются особым образом, и их обработка не производится ни на одном из этапов алгоритма.

Второй особенностью снимков является неравномерное распределение яркости по информативной области. Однако разработанный алгоритм позволяет исправлять такие искажения без модификации.

Произведено тестирование разработанного алгоритма как независимое, так и в сравнении с алгоритмом автонастройки уровней и алгоритмом Multi-Scale Retinex, разработанным в NASA. Среднее время обработки изображения из тестового набора составило 3.9 секунды. Размер изображений при этом составил от 0,09 до 0,65 мегапикселей. Важным достоинством разработанного алгоритма является отсутствие затрат времени на обучение и адаптивная обработка каждого изображения в отдельности. Значение комплексной оценки изображения при этом увеличилось в среднем в 23,83 раза. Выявлена зависимость между повышением значения оценки и ее исходным значением, причем форма этой зависимости близка к логарифмической. Пример результатов работы предложенного алгоритма приведен на рис. 1.

а) 6)

Рис. 1. Пример обработки изображения с использованием предлагаемого алгоритма: а) исходное изображение', б) улучшенное изображение

При сравнении результатов обработки различными алгоритмами для каждого из них в соответствии с оценкой VIF, обратной оценкой VIF и комплексной оценкой, использованной в работе вычислялись ранги по

каждому изображению. Значения сумм рангов для рассматриваемых алгоритмов приведены в таблице 1 (наименьшее значение принадлежит алгоритму, показавшему наилучший результат). Как видно из таблицы, при сравнении качества обработанных изображений на основе оценки VIF (Visual Information Fidelity) разработанный алгоритм дает худшие результаты, однако при использовании представленной комплексной оценки и обратной оценки V1F разработанный алгоритм превосходит аналоги.

Таблица 1. Значения суммы рангов для алгоритмов обработки изображений по используемым оценкам визуального качества.

Алгоритм обработки Сумма рангов по оценкам

fviF frVIF Комплексная оценка Сумма

Multi-Scale Retinex 115 101 112 328

Автонастройка уровней 88 144 137 369

Алгоритм на основе ГА 121 79 75 275

В заключении приведены выводы и результаты диссертационной работы.

Основные результаты и выводы

В результате выполнения диссертационной работы были получены следующие основные научные и практические результаты и сделаны следующие выводы:

1. Разработана модифицированная комплексная оценка качества изображений. Исследования показали, что данная оценка учитывает как основные критерии качества изображений (такие, как контрастность и полнота использования возможных градаций яркости), так и особенности восприятия человека (уровень адаптации к зрению человека по яркости). Кроме того, учитываются некоторые особенности функционирования алгоритма.

2. Предложено использовать в качестве основы для проектирования генетического алгоритма модель Генитор с однородным оператором

кроссинговера. В результате экспериментов установлено, что данная модель наиболее точно удовлетворяет особенностям решаемой задачи ввиду максимально широкого пространства поиска.

3. Обосновано использование выравнивания гистограмм и I-R алгоритма в качестве предварительных этапов при обработке изображений. Применение таких предварительных этапов позволило отказаться от использования среднеквадратического отклонения по окрестности в ядре преобразования изображений, и в результате сократить время обработки изображений более чем на 40 % при одновременном повышении качества обработки.

4. Исследована возможность адаптивного применения масштабирования изображений для сокращения времени работы алгоритма. Установлена зависимость между снижением качества обработки и энтропией исходного изображения. Показано, что масштабирование может применяться без значительных потерь качества результирующего изображения в тех случаях, когда энтропия исходного изображения не менее 6,22.

5. Предложен комплексный метод улучшения изображений, включающий I-R обработку, выравнивание гистограмм, адаптивное масштабирование изображений и обработку генетическим алгоритмом. Исследование предложенного алгоритма показало, что он позволяет достаточно быстро и эффективно повышать визуальное качество изображений. Сравнение с алгоритмами автонастройки уровней и Multi-Scale Retinex показало, что по ряду оценок качества обработки предложенный алгоритм превосходит аналоги, хотя и проигрывает им в скорости обработки.

6. Спроектирована и реализована библиотека обработки изображений на базе генетического алгоритма. Гибкая архитектура библиотеки позволяет вносить изменения и добавлять дополнительные этапы обработки с минимальными трудозатратами и изменениями исходного кода библиотеки. Создана дополнительная библиотека для параллельной обработки массивов данных, использующая технологию ОрепМР.

18

Разработаны программные средства для исследователей и обычных пользователей, использующие функции библиотеки.

7. Исследована предметная область металлографии. Разработанный метод адаптирован для обработки снимков макро- и микроструктуры металлических шлифов. В результате применения комплексного алгоритма на этапе подготовки изображений к металлографическому анализу удалось значительно повысить информативность снимков.

Основные публикации по теме диссертации

Перечень публикаций по теме диссертации:

1. Белоусов А. А., Спицын В.Г., Сидоров Д.В. Применение генетических алгоритмов и вейвлет-преобразований для повышения качества изображений // Известия Томского политехнического университета. - 2006. -Т. 309.-Ха 7.-С. 21-26.

2. Белоусов А.А., Спицын В.Г. Применение генетических алгоритмов для повышения качества полутоновых изображений // Молодежь и современные информационные технологии: Сборник трудов IV Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых - Томск, ТПУ, 28 февраля - 2 марта 2006. - Томск: ТПУ. -2006.-С. 411-413.

3. Belousov A.A., Spitsyn V.V. Colour image enhancement using evolutionary algorithm, Proceedings of XII International Research-Practical Conference of Students, Post-Graduate Students and Young Scientists "Modern engineering and technology", 27 - 31 March 2006. - Tomsk: Tomsk Polytechnic University. - 2006. - Pp. 111-113.

4. Belousov A.A., Spitsyn V.G., Sidorov D.V. Applying wavelets and evolutionary algorithms to automatic image enhancement // Proceedings of SPIE. -2006. - Vol. 6522. - P. 652210-1-652210-9.

5. Belousov A.A., Sidorov D.V., Spitsyn V.G. Applying wavelets and evolutionary algorithms to automatic image enhancement // XIII International

Symposium "Atmospheric and Ocean Optics. Atmospheric Physics", Tomsk, July 2-6.-2006.-Pp. 104.

6. Белоусов A.A., Спицын В.Г. Двухэтапный метод улучшения изображений // Труды XIII Международной научно-практической конференции студентов, аспирантов и молодых ученых "Современная техника и технологии ". Т. 2. Томск. 26 - 30 марта 2007 г. - Изд-во ТПУ. -2007. - С. 282-284.

7. Спицын В.Г., Цой Ю.Р., Чернявский A.B., Белоусов A.A., Сидоров Д.В. Улучшение качества изображений на основе применения эволюционирующей нейронной сети, вейвлет-преобразования и генетического алгоритма // Труды Российского научно-технического общества радиотехники, электроники и связи имени A.C. Попова. Серия: Цифровая обработка сигналов и ее применение. Выпуск: IX-2, Доклады 9-й Международной конференции "Цифровая обработка сигналов и ее применение", 28-30 марта 2007, Москва. - М. - 2007. - С. 570-574.

8. Spitsyn V.G., Tsoy Y.R., Belousov A.A. Images Enhancement with Use of Evolving Neural Network, Wavelet Transform and Genetic Algorithm // 2007 IEEE Antennas and Propagation Society International Symposium, June 10-15, 2007, Honolulu, Hawai'i. - USA. - 2007. - Vol. 4. - Pp. 1497-1500.

9. Белоусов A.A. Высокоскоротной метод повышения качества изображений // Современные техника и технологии: Труды XIV Международной научно-практической конференции студентов, аспирантов и молодых ученых - Томск, 24-28 марта 2008. - Томск: ТПУ. - 2008. -С. 244-245.

10. Белоусов A.A. Двухэтапный метод улучшения изображений // Технологии Microsoft в теории и практике программирования: Сборник трудов VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых - Томск, 17-18 марта 2009. — Томск: ТПУ. -2009.-С. 123-125.

11. Belousov A.A., Spitsyn V.G., Sidorov D.V., Application of Wavelet Transform and Genetic Algorithms for Image Processing // Proceedings of International Conference on Image Processing, Computer Vision, & Pattern Recognition, Las Vegas, USA, July 13-16,2009. - Vol. 2. - Pp. 846-851.

Тираж 100. Заказ № 1123. Томский государственный университет систем управления и радиоэлектроники 634050, г. Томск, пр. Ленина, 40. Тел.: 53-30-18.

Список использованных сокращений и обозначений.

ВВЕДЕНИЕ.

Глава 1. Аналитический обзор эволюционных алгоритмов и их применения к обработке изображений.

1.1. Задачи обработки изображений.

1.2. Анализ эволюционных алгоритмов.

1.2.1. Операторы генетического алгоритма.

1.2.2. Модели генетических алгоритмов.

1.3. Обработка изображений при помощи генетических алгоритмов.

1.3.1. Улучшение изображений.

1.3.2. Распознавание образов.

1.3.3. Обработка медицинских изображений.

1.4. Цели и задачи исследования.

Применение цифровых изображений началось еще в начале 1920-х годов, когда была реализована передача иллюстраций для газет по трансокеанскому подводному кабелю между Лондоном и Нью-Йорком, позволившая сократить время передачи изображения через Атлантику до 3 часов [12]. А появление компьютеров в середине XX века привело к возникновению новой области науки - цифровой обработки изображений.

Первые компьютеры, обладающие достаточной для обработки изображений мощностью, появились в 60-х годах прошлого века. Одновременно с этим возникла необходимость обработки снимков, получаемых с космических аппаратов. В 1964 году цифровое улучшение качества изображений было впервые применено для исправления искажений на снимках переданных космическим аппаратом «Рейнджер-7», появившихся вследствие особенностей его бортовой камеры. Вслед за этим стали появляться и другие задачи по цифровой обработке изображений, такие как сжатие изображений, сегментация, морфологический анализ и многие другие.

Характерной особенностью многих методов цифровой обработки изображений является проблема формализуемости преобразований. Попытки решения данных задач детерминированными методами часто сталкиваются с различными ограничениями, такими как сложность формального представления преобразований, наличие большого количества параметров и отсутствие эталонного решения. В процессе развития методов и средств обработки изображений стали появляться методы обработки изображений, основанные на применении новых концепций поиска решений в вычислительных системах. Одной из таких концепций явились эволюционные вычисления.

Идеи применения принципов естественного отбора для решения задач впервые были опубликованы Джоном Холландом в начале 60-х годов прошлого века, однако широкое признание и распространение получили после опубликования в 1975 году его классической работы о генетических алгоритмах под названием «Адаптация в естественных и искусственных системах» [93]. Эта работа является основополагающей в области исследования генетических алгоритмов. В ней же была сформулирована и доказана теорема схем, дающая обоснование эффективности генетических алгоритмов. Теорема схем доказывает происходящее при смене поколений экспоненциальное распространение хорошо приспособленных схем с малыми порядком и определяющей длиной. Эта теорема была дополнена гипотезой строительных блоков Гольдберга в 1989 году [84, 94]. Работы Рехенберга 1973 года [119] и Швефеля 1981 года [122, 123] описывают эволюционные стратегии, а Фогель, Оуэне и Уолш в 1966 году описали эволюционное программирование [36, 79, 80]. Работы в области эволюционных вычислений велись и в России. В основном эти исследования опирались на работы по самообучающимся системам [16] и стохастической оптимизации [32]. В результате исследований эволюционных вычислений в целом и генетических алгоритмов в частности была показана их высокая эффективность при решении задач многопараметрической оптимизации.

Важным преимуществом генетических алгоритмов является сочетание стохастических и детерминированных свойств. Применение генетических алгоритмов для поиска экстремумов сложных многомодальных функций дает возможность поиска решений за приемлемое время и с достаточно высокой точностью [1, 42, 22, 90,]. Кроме того, генетические алгоритмы могут применяться для поиска решений в сложноформализуемых задачах, для которых применение детерминированных методов вообще невозможно.

Применение генетических алгоритмов в таких задачах позволяет находить решения даже при неизвестной форме преобразования, например при подборе структуры и весов нейронной сети при нейро-эволюционном подходе к улучшению изображений [35]. Для работы генетического алгоритма достаточно возможности формального представления решений и 6 критерия оценки результата. При этом за счет наличия стохастической составляющей ГА обладают достаточно широким пространством поиска, а за счет механизма наследования позволяют сохранить свойства близких к оптимальным решений.

Таким образом, можно сделать вывод об актуальности исследования методов обработки изображений, основанных на эволюционных вычислениях.

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

Для достижения поставленной цели необходимо последовательное решение следующих задач:

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

2. Выбор и исследование операторов и модели генетического алгоритма, наиболее подходящих для решения задач обработки цифровых изображений.

3. Разработка алгоритма обработки изображений, основанного на ГА, с учетом результатов решения предыдущих задач. Решение данной задачи предполагает также исследование эффективности применения разработанного алгоритма.

4. Разработка и адаптация дополнительных этапов обработки для повышения скорости и качества обработки. Исследование эффективности применения выбранных дополнительных этапов обработки.

5. Апробация разработанного алгоритма для решения задачи улучшения визуального качества изображений.

Методы исследований. В работе использованы методы математической статистики, теории оптимизации, цифровой обработки 7 изображений, теории информации, мягких вычислений, технологий программирования.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих симпозиумах, конференциях и семинарах: XIII Международный симпозиум «Оптика атмосферы и океана. Физика атмосферы» (г. Томск, 2006 г.), IV и V Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, 2006 и 2007 г.), XIII и XIV Международная научно-практическая конференция студентов, аспирантов и молодых ученых «Современные техника и технологии» (г. Томск, 2007 и 2008 г.), VI Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (г. Томск, 2009 г.).

По результатам диссертационных исследований опубликовано 11 работ. Список публикаций приведен в Приложении 1.

Кратко изложим основное содержание работы.

В первой главе представлен обзор различных задач цифровой обработки изображений. Приведена классификация областей применения цифровой обработки изображений по типу используемых изображений.

Представлен аналитический обзор эволюционного подхода к решению различных задач. Описаны основные операторы генетического алгоритма и возможные варианты их реализации. Рассмотрены также и различные модели генетических алгоритмов, существующие на данный момент. Сделаны выводы о достоинствах существующих моделей ГА, использованные в дальнейших исследованиях в главе 2.

Проанализированы возможности применения ГА для решения различных задач обработки изображений. Рассмотрены основные проблемы, присущие задачам обработки цифровых изображений. Приведены конкретные примеры применения ГА для решения задач улучшения визуального качества изображений, распознавания образов и обработки медицинских изображений.

Применительно к задаче улучшения изображений рассмотрены варианты преобразования яркостей пикселей и различные способы оценки изображений. Проанализированы параметры изображений, которые возможно формально оценить.

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

1. быстрая сходимость к решениям, близким к оптимальным;

2. наличие возможности регулировки направления поиска решений извне через влияние на генетический алгоритм или внутренние процедуры;

3. минимальное количество вычислений целевой функции ввиду ее высокой вычислительной сложности;

4. представление генов в целочисленном виде с возможностью использования как чисел с плавающей запятой.

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

Приведено описание схемы алгоритма и основных функций, применяемых при обработке. Рассмотрены недостатки функции преобразования яркостей точек и предложены варианты их устранения. Описаны необходимые модификации оценки целевой функции алгоритма для повышения качества обработки.

На основе анализа алгоритма и сформулированных в главе 1 требований к нему выбраны возможные модели генетических алгоритмов. Приведено их детальное описание и выбраны критерии сравнения моделей применительно к поставленным задачам.

Описаны эксперименты, проведенные для выбора модели ГА. На основе результатов экспериментов показано, что модель СНС работает несколько быстрее остальных (на 3,9 % быстрее канонической модели и на 4,7% быстрее модели Генитор), однако ввиду отсутствия мутации на основной фазе работы алгоритма и меньшего размера популяции имеет меньшее пространство поиска, что приводит к более низкой приспособленности найденного решения. Модель Генитор, напротив, обладает наиболее низким быстродействием из-за высоких накладных расходов на операторы ГА, однако дает значительно лучшие результаты. По суммарным показателям модель Генитор является наилучшей моделью ГА применительно к данной задаче.

Также во второй главе проведен анализ быстродействия разработанного алгоритма и выявлены наиболее ресурсоемкие этапы обработки. На основе результатов анализа и экспериментов показано, что наибольшие затраты на обработку приходятся на вычисление локальных характеристик (более 63 % общего времени обработки) и преобразование изображений (более 28 % времени). Предложены варианты сокращения времени обработки на основе применения предварительных этапов для исключения среднеквадратического отклонения из функции преобразования яркостей точек и снижения затрат времени на расчет локальных характеристик. Для снижения затрат времени на преобразование изображения предложена обработка уменьшенной копии изображения, с последующим применением преобразования яркости с найденными параметрами к исходному изображению.

Приведено описание и исследование метода повышения контрастности изображения на основе модели Освещенность-Отраженность (Illuminance-Reflectance, I-R). На основе результатов экспериментов показано, что применение данной модели значительно повышает количество и интенсивность краевых пикселей. Обоснован выбор параметров данного преобразования.

Описан метод выравнивания гистограмм, позволяющий повысить как количество и интенсивность краевых пикселей, так и уровень адаптации к зрению человека по яркости. Описаны недостатки этого метода и ограничения на максимальную и минимальную разницу между соседними градациями яркости, введенные для устранения этих недостатков.

Приведена схема использования описанных методов в качестве предварительных этапов обработки. Исследовано влияние такой схемы применения на скорость и результат окончательной обработки. На основе экспериментов показано, что применение выравнивания гистограмм и 1-Я алгоритма для предобработки изображений с одновременным исключением среднеквадратического отклонения из ядра преобразования приводит к сокращению времени обработки изображения в среднем на 41,8 %, при этом значение комплексной оценки качества удалось повысить приблизительно в 3 раза.

Приведены результаты исследования возможности масштабирования исходного изображения для сокращения времени на поиск решения генетическим алгоритмом. Исследована зависимость снижения качества обработки при масштабировании от различных параметров исходного изображения, таких как размер изображения, средняя яркость, значение комплексных оценок и ее составляющих. Выявлено, что подобный этап может быть применен только к изображениям, обладающим достаточно большой энтропией, в противном случае наблюдается значительное снижение качества обработки. Для сохранения качества обработки на уровне не менее 90 % по сравнению с обработкой немасштабированного изображения необходимо применять масштабирование только к тем изображениям, исходная энтропия которых составляет не менее 6,22. Описана схема использования масштабирования в итоговом алгоритме.

В третьей главе приведено полное описание разработанных программных средств. Описываются методы и средства, примененные при реализации библиотеки для эволюционной обработки изображений и программных средств.

Сформулированы требования к библиотеке функций, реализ>пющей разработанный алгоритм. Описывается набор принципов проектирования классов SOLID, использованный для разработки архитектуры библиотеки GeneticEnhancer.

Произведен анализ доступных средств разработки и на основе анализа выбраны языки программирования для реализации библиотеки. Для разработки была выбрана платформа Microsoft .Net Framework и языки программирования Visual С++ и Visual С#, поскольку они отвечают всем сформулированным требованиям.

Описывается технология ОрепМР, использованная для параллельной обработки массивов данных. Произведено исследование влияния применения данной технологии на время обработки. Показано, что применение параллельных вычислений для преобразования изображений и нахождения значения целевой функции позволяет сократить время обработки приблизительно на 10%.

Приведено детальное описание структуры классов разработанной библиотеки, включающей 3 основных группы классов:

1. классы, обеспечивающие логику работы ГА;

2. классы, обеспечивающие логику оценки изображений;

3. вспомогательные классы.

Осуществлено описание разработанных программных средств автоматизированного тестирования методов обработки изображений. Описана программа улучшения визуального качества изображений для конечных пользователей. Перечислены функции и возможности каждой из этих программ.

В четвертой главе приведено описание задач металлографии, решаемых с использованием цифровых изображений. Описываются методы исследования макро- и микроструктуры металлических шлифов.

Анализируются особенности получаемых при исследовании цифровых снимков. Произведена адаптация разработанного алгоритма для решения задач металлографии, учитывающая особенности получаемых снимков.

Произведено тестирование разработанного алгоритма как независимое, так и в сравнении с алгоритмом автонастройки уровней и алгоритмом Multi-Scale Retinex, разработанным в NASA. Среднее время обработки изображения из тестового набора составило 3.9 секунды. Размер изображений при этом составил от 0,09 до 0,65 мегапикселей. Важным достоинством разработанного алгоритма является отсутствие затрат времени на обучение и адаптивная обработка каждого изображения в отдельности. Значение комплексной оценки изображения при этом увеличилось в среднем в 23,83 раза. Выявлена зависимость между повышением значения оценки и ее исходным значением, причем форма этой зависимости близка к логарифмической.

В результате сравнения разработанного алгоритма с алгоритмом автонастройки уровней и MSR показано, что при сравнении качества обработанных изображений на основе оценки VIF (Visual Information Fidelity) разработанный алгоритм дает худшие результаты, однако при использовании представленной комплексной оценки и обратной оценки VIF разработанный алгоритм превосходит аналоги.

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

• усиление контраста на основе модели "Освещенность-Отраженность",

• выравнивание гистограмм изображений,

• адаптивное масштабирование изображений.

2. Упрощенная функция преобразования изображений, позволившая сократить затраты времени на вычисление локальных характеристик и повысить качество обработки.

3. Модифицированная оценка качества изображений, учитывающая особенности человеческого зрения и алгоритма обработки изображений.

4. Адаптивный способ масштабирования изображений, позволяющий ускорить поиск решения генетическим алгоритмом за счет сокращения времени преобразования уменьшенных копий изображения и оценки их качества.

Практическая ценность и реализация результатов работы. Практически значимыми являются методы, алгоритмы, аналитические оценки и формулы, разработанные и полученные в результате диссертационного исследования.

Разработанные программные средства для обработки изображений используются в ООО НПП «Томская электронная компания» для обработки снимков микроструктуры металла шлифов на этапе их предварительной подготовки для анализа микроструктуры. Также внедренное программное обеспечение применяется в отделе маркетинга для автоматического улучшения фотоснимков низкого качества, полученных в промышленных условиях. Результаты внедрения подтверждены соответствующим актом. Кроме того планируется широкое распространение разработанных программных средств для конечных пользователей. Потенциальными потребителями разработанных продуктов являются исследовательские организации, производящие обработку цифровых снимков в различных областях (металлографии, дефектоскопии, техническом зрении, дистанционном зондировании), а также пользователи, производящие обработку фотоснимков низкого качества для личного пользования.

Личный вклад:

1. Постановка задач диссертационного исследования выполнена автором совместно с В.Г. Спицыным.

2. Модификация оценки качества изображений для целевой функции генетического алгоритма и ядра преобразования изображений выполнена автором.

3. Формирование критериев сравнения моделей ГА применительно к решаемой задаче выполнено автором. Им же произведено экспериментальное исследование трех моделей ГА и произведен выбор наиболее подходящей из них для реализации.

4. Исследование и модификация алгоритма выравнивания гистограмм выполнена автором.

5. Исследование и реализация метода на основе модели Освещенность-Отраженность выполнена автором совместно с А.Ю. Шековым.

6. Постановка задачи исследования возможности масштабирования обрабатываемых изображений выполнена автором совместно с В.Г. Спицыным и Ю.Р. Цоем.

7. Модификация генетического алгоритма улучшения цифровых изображений после внедрения предварительных этапов обработки и-адаптивного масштабирования изображений произведена автором.

8. Исследование методов металлографических исследований и адаптация разработанного алгоритма для задачи исследования макро- и микроструктуры металлических шлифов произведены автором.

Основные положения, выносимые на защиту:

1. Комплексный метод повышения визуального качества цифровых изображений позволяет достаточно быстро и эффективно улучшать качество изображений. Результаты обработки по ряду параметров превосходят известные аналоги.

2. Применение предобработки изображения при помощи 1-11 алгоритма и алгоритма выравнивания гистограмм позволяет повысить скорость обработки за счет исключения из ядра преобразования изображений среднеквадратического отклонения по окрестности. Качество обработки при этом повышается.

3. Модифицированная оценка качества изображений позволяет учитывать некоторые особенности человеческого зрения и особенности функционирования алгоритма.

4. Адаптивное масштабирование изображений в ряде случаев позволяет значительно сократить время обработки изображений без существенных потерь качества обработки.

Автор выражает глубокую благодарность научному руководителю, доктору технических наук В.Г. Спицыну за всестороннюю помощь в написании работы, анализе получаемых результатов, ценные замечания и конструктивную критику. Также автор благодарит за плодотворные дискуссии, консультации в различных областях и помощь в организации работ доктора технических наук, профессора, заведующего кафедрой вычислительной техники Н.Г. Маркова, доцентов Томского политехнического университета кандидатов технических наук Ю.Я. Кацмана, А.Н. Осокина, кандидата физико-математических наук Ю.Б. Буркатовскую, а также всех членов научной группы профессора В.Г. Спицына. Отдельную благодарность за ценные замечания и всестороннюю помощь в выполнении работ автор выражает доценту Томского политехнического университета, кандидату технических наук Ю.Р. Цою.

4.3. Основные результаты и выводы по главе 4

1. Приведено описание задачи металлографии, в которой применяется анализ и обработка цифровых изображений. Описаны проблемы, возникающие при анализе снимков макро- и микроструктуры металлических шлифов.

2. Произведена адаптация разработанного алгоритма для обработки снимков микроструктуры металлических шлифов. В результате адаптации добавлена возможность игнорирования черной рамки вокруг информативной части снимка.

3. Проведено исследование тестирование алгоритма и его сравнение с алгоритмами автонастройки уровней и Multi-Scale Retinex. В результате тестирования установлено, что среднее время обработки изображений

147 размером до 800x800 точек составляет 3.9 секунды, а комплексная оценка качества при этом увеличивается в среднем в 23.83 раза. При сравнении с другими алгоритмами улучшения изображений было установлено, что разработанный алгоритм проигрывает по оценке VIF, однако имеет лучшие значения обратной оценки VIF и значение комплексной оценки.

ЗАКЛЮЧЕНИЕ

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

В результате выполнения диссертационной работы были получены следующие основные научные и практические результаты и сделаны следующие выводы:

1. Разработана модифицированная комплексная оценка качества изображений. Исследования показали, что данная оценка учитывает как основные критерии качества изображений (такие, как контрастность и полнота использования возможных градаций яркости), так и особенности восприятия человека (уровень адаптации к зрению человека по яркости). Кроме того, учитываются некоторые особенности функционирования алгоритма.

2. Предложено использовать в качестве основы для проектирования генетического алгоритма модель Генитор с однородным оператором кроссинговера. В результате экспериментов установлено, что данная модель наиболее точно удовлетворяет особенностям решаемой задачи ввиду максимально широкого пространства поиска.

3. Обосновано использование выравнивания гистограмм и 1-Я алгоритма в качестве предварительных этапов при обработке изображений. Применение таких предварительных этапов позволило отказаться от использования среднеквадратического отклонения по окрестности в ядре преобразования изображений, и в результате сократить время обработки изображений более чем на 40 % при одновременном повышении качества обработки.

4. Исследована возможность адаптивного применения сжатия изображений для сокращения времени работы алгоритма. Установлена зависимость между снижением качества обработки и энтропией исходного изображения. Показано, что масштабирование может применяться без значительных потерь качества результирующего изображения в тех случаях, когда энтропия исходного изображения не менее 6,22.

5. Предложен комплексный метод улучшения изображений, включающий I-R обработку, выравнивание гистограмм, адаптивное масштабирование изображений и обработку генетическим алгоритмом. Исследования предложенного алгоритма показало, что он позволяет достаточно быстро и эффективно повышать визуальное качество изображений. Сравнение с алгоритмами автонастройки уровней и Multi-Scale Retinex показало, что по ряду оценок качества обработки предложенный алгоритм превосходит аналоги, хотя и проигрывает им в скорости обработки.

6. Спроектирована и реализована библиотека обработки изображений на базе генетического алгоритма. Гибкая архитектура библиотеки позволяет вносить изменения и добавлять дополнительные этапы обработки с минимальными трудозатратами и изменениями исходного кода библиотеки. Также разработана дополнительная библиотека для параллельной обработки массивов данных, использующая технологию ОрепМР. Разработаны программные средства для исследователей и обычных пользователей, использующие функции библиотеки.

7. Исследована возможность применения предложенного эволюционного метода обработки изображений в металлографии. Разработанный метод адаптирован для обработки снимков макро- и микроструктуры металлических шлифов. В результате применения комплексного алгоритма на этапе подготовки изображений к металлографическому анализу удалось значительно повысить информативность снимков.

1. Батищев, Д.И. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов Текст . / Батищев Д.И., Исаев С.А. -ВГТУ, 1997.

2. Белоусов, A.A. Применение генетических алгоритмов и вейвлет-преобразований для повышения качества изображений Текст . / A.A. Белоусов, В.Г. Спицын, Д.В. Сидоров // Известия Томского политехнического университета, Т. 309. № 7. 2006. - С. 21-26.

3. Бунин, К. П. Металлография Текст . / К.П. Бунин, Л.А. Баранов. М.: Металлургия, 1970. - 253 с.

4. Бурцев, М.С. Эволюция кооперации в многоагентной системе Текст. / М.С. Бурцев // Научная сессия МИФИ-2005. VII Всероссийская научно-практическая конференция «Нейроинформатика-2005»: Сборник научных трудов. В 2-х частях. 4.1. М.: МИФИ, 2005. - С.217-224

5. Вороновский, Г.К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности Текст . / Г.К. Вороновский, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. Харьков: Основа, 1997 // http://neuroschool.narod.ru/books/gannvirt.html

6. Гамма, Э. Приемы объектно-ориентированного проектирования. Паттерны проектирования Текст . / Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. СПб: Питер, 2003.

7. Гладков, Л.А. Генетические алгоритмы / Л.А. Гладков, В.В. Курейчик, В.М.Курейчик. -М : Физматлит, 2006 г. -402 с.

8. Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. М.: Техносфера, 2005. - 1072 с.

9. Гуляев А. П. Металловедение. 5-е изд. Текст . / А.П. Гуляев. -М.: Металлургия, 1977. 664 с.

10. Емельянов, В.В. Теория и практика эволюционного моделирования Текст . / В.В. Емельянов, В.В. Курейчик, В. М. Курейчик. — М.: ФИЗМАТЛИТ, 2003. 432 с.

11. Журавель И.М. Краткий курс теории обработки изображений Электронный ресурс. // http://matlab.exponenta.ru/imageprocess/ Ьоок2/^ех.р11р

12. Ивахненко А.Г. Самонастраивающиеся системы автоматического регулирования Текст . / А.Г. Ивахненко. К.: Гостехиздат УССР, 1957.

13. Исследования по генетическим алгоритмам в Мичиганском университете Электронный ресурс . // http://garage.cps.msu.edu

14. Исследования по генетическим алгоритмам в университете штата Колорадо Электронный ресурс . // http://www.cs.colostate.edu

15. Карманов, В.Г. Математическое программирование Текст .: Учеб. пособие. 5-е изд., стереотип. / В.Г. Карманов. - М.: Физматлит, 2001.

16. Каширина, И.Л. Введение в эволюционное моделирование. Учебное пособие Текст . / И.Л. Каширина. Воронеж: ВГУ, 2007.

17. Курейчик, В.М. Параллельный генетический алгоритм. Модели и проблемы построения Текст . / В.М. Курейчик, Кныш Д.С. Таганрог: Технологический ин-т ЮФУ, 2010.

18. Курейчик, В.М. Эволюционные вычисления: генетическое и эволюционное программирование Текст . / В.М. Курейчик, С.И. Родзин // Новости искусственного интеллекта. 2003. - № 5(59).

19. Курейчик, В.М. Генетические алгоритмы Текст . / Л.А. Гладков, В.М. Курейчик, В.В. Курейчик. М.: Физматлит, 2006.

20. Курейчик В. М. Генетические алгоритмы и их применение Текст . / В.М. Курейчик. Таганрог: Изд-во ТРТУ, 2002.

21. Лахтин, Ю. М. Материаловедение. Второе издание Текст . / Ю.М. Лахтин, В. П. Леонтьеваю М:Машиностроение, 1980. - 494 с.

22. Линдли, К. Практическая обработка изображений на языке Си Текст. / К. Линдли ; [пер. с англ. A.A. Брюзгина] М.: Мир, 1996.

23. Майерс, С. Эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов: Пер. с англ. Текст. / С. Майерс. М.: ДМК Пресс; Спб: Питер, 2006.

24. Официальный сайт OpenMP Architecture Review Board Электронный ресурс. // http://www.openmp.org/

25. Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие Текст . / Т.В. Панченко; под ред. Ю.Ю. Тарасевича. Астрахань: Издательский дом «Астраханский университет», 2007. - 87 с.

26. Прэтт У. Цифровая обработка изображений Текст . / У.Прэтт. -М.: Мир, 1982.

27. Растригин JI.A. Статистические методы поиска Текст . / JI.A. Растригин. М: Наука, 1968.

28. Редько, В.Г. К теории эволюции. Модель возникновения "программ жизнедеятельности" Текст . / Редько В.Г. // Журнал общей биологии. 1991. - № 3. - С. 334-342.

29. Редько, В.Г. Оценка эффективности эволюционных алгоритмов Текст. / В.Г. Редько, Ю.Р. Цой // Доклады АН. 2005. - Т. 404, №3. - С. 312315.

30. Фогель, JI. Искусственный интеллект и эволюционное моделирование Текст . / JI. Фогель, А. Оуенс, М. Уолш. М.: Мир, 1969. -230 с.

31. Цой, Ю.Р. Нейроэволюционный алгоритм и программные средства для обработки изображений. Диссертация на соискание ученой степени кандидата наук Текст . / Ю.Р. Цой. Томск, 2007

32. Цой, Ю.Р. Применение генетического алгоритма для аппроксимации функций. Методические указания Текст . / Ю.Р. Цой, В.Г. Спицын. Томск, 2002.

33. Цой, Ю. Р. Применение искусственных нейронных сетей для решения задач классификации и аппроксимации функций. Методические указания Текст . / Ю.Р. Цой, В.Г. Спицын. Томск, 2003.

34. Цой, Ю.Р. Нейроэволюционное улучшение качества изображений Текст . / Ю.Р. Цой, В.Г. Спицын, A.B. Чернявский // Труды VIII Всероссийской научно-технической конференции «Нейроинформатика-2006», Москва, 2006. М.: МИФИ, 2006.

35. Цой, Ю.Р. Нейроэволюционное улучшение качества изображений Текст . / Ю.Р. Цой, В.Г. Спицын, A.B. Чернявский // Труды VIII Всероссийской научно-технической конференции «Нейроинформатика-2006». Москва, 2006.

36. Шеков А.Ю. Разработка метода улучшения изображений на основе модели "Освещенность-Отражающая способность". Выпускная квалификационная работа / А.Ю. Шеков. Томский политехнический университет, 2010.

37. Akashi, Т. Using Genetic Algorithm for Eye Detection and Tracking in Video Sequence Текст . / Т. Akashi, Y. Wakasa, K. Tanaka. // Systemics, Cybernetics and Informatics. 2007. - Vol. 5, no. 2.

38. Baeck, T. An overview of parameter control methods by self-adaptation in evolutionary algorithms Текст . / Т. Baeck // Fund. Inform. 1998. -Vol. 35, no. 1-4.-P. 51-66.

39. Baeck, T. Evolutionary computation Текст . / Т. Baeck, D. Fogel, Z. Michalewicz. Berlin Heidelberg: Springer-Verlag, 2000.

40. Baeck, T. Self-adaptation Текст . / Т. Baeck // Handboook of Evolutionary Computation. Bristol: Institute of Physics Publishing; New York: Oxford University Press, 1997. - C7.1:1-15.

41. Baker, J.E. Adaptive selection methods for genetic algorithms Текст. / J.E. Baker // Proceedings of the International Conference on Genetic Algorithms and Their Applications, 1985. P. 101-111.

42. Belousov, A.A. Applying wavelets and evolutionary algorithms to automatic image enhancement Текст . / A.A. Belousov, V.G. Spitsyn, D.V. Sidorov // Proceedings of SPIE, 2006. Vol. 6522. P. 652210-1-652210-9.

43. Beyer, H.-G. An alternative explanation for the manner in which genetic algorithms operate Текст . / H.-G. Beyer // BioSystems. 1997. - No. 41.-P. 1-15.

44. Biesbroek, R. Genetic Algorithm Tutorial. 4.1 Mathematical foundations Текст . / R. Biesbroek, 1999.

45. Booch, G. Object Solutions Текст . // G. Booch. Menio Park, California: Addison-Wesley, 1996

46. Bovik, A.C. Meditations on video quality invited Distinguished Position Paper Текст . / A.C. Bovik // IEEE Multimedia Communications E-Letter. 2009. - Vol. 4, no. 4. - P. 4-10

47. Chernyavskii, A.V. Image processing using evolving neural network Текст. / A.V. Chernyavskii, Yu.R. Tsoy, V.G. Spitsyn // XIII International Symposium "Atmospheric and Ocean Optics. Atmospheric Physics", Tomsk, July 2-6, 2006.-P. 104.

48. Cliff, D. Explorations in evolutionary robotics Текст . / D. Cliff, I. Harvey, P. Husbands // Adaptive Behavior. 1993. - No. 2. - P. 73-110.

49. Davis, L. Adapting operator probabilities in genetic algorithms Текст. / L. Davis // Proceedings of Third International Conference on Genetic Algorithms and their Applications. 1989. - P. 61-69.

50. De Jong, K.A. A formal analysis of the role of multi-point crossover in genetic algorithms Текст . / K.A. De Jong, W.M. Spears // Annals of Mathematics and Artificial Intelligence. 1992. - Vol. 5, no.5. - P. 1-26.

51. De Jong, K.A. An analysis of the behavior of a class of genetic adaptive systems Текст . : Unpublished PhD thesis / K. De Jong. University of Michigan, Ann Arbor, 1975. - Also University microfilms No. 76-9381 // http://www.cs.gmu.edu/~eclab

52. De Jong, K.A. An Analysis of the Interacting Roles of Population Size and Crossover Текст . / K.A. De Jong, W.M. Spears // Proceedings of the International Workshop Parallel Problem Solving from Nature. 1990. - P. 38-47.

53. De Jong, K.A. Generation gaps revisited Текст . / K.A. De Jong, Sarma J. // Foundations of Genetic Algotihms 2. 1993. - P. 19-28.

54. Deb, K. Self-adaptive genetic algorithms with simulated binary crossover Текст . / К. Deb, H.-G. Beyer // Evolutionary Computation. 2000. -Vol. 9, no. 2.-P. 197-221.

55. Deb, K. Simulated binary crossover for continuous search space Текст . / К. Deb, R.B. Agrawal // Complex Systems. 1995. - No. 9. - P. 115148.

56. DeMarco, T. Structured Analysis and System Specification Текст . / Т. DeMarco. Englewood Cliff, New Jersey: Yourdon Press Computing Series, 1979.

57. Dougherty, E. R. Introduction to Morphological Image Processing, Vol. TT09 Текст . / Dougherty, E. R. SPIE Press, Bellingham, WA, 1992.

58. Dougherty, . E.R. Image Processing Continuous to Discrete. Geometric, Transform, and Statistical Methods. Vol. 1 Текст . / E. R. Dougherty and C. R. Giardina. Englewood Cliffs, NJ: Prentice Hall, 1987.

59. Ekstrom, M.P. Digital Image Processing Techniques Текст . / M.P. Ekstrom. New York: Academic Press, 1984.

60. Elad, M. Reduced complexity Retinex algorithm via the variational approach Текст . / M. Elad, R.Kimmel, D. Shaked, R. Keshet // J. Vis. Commun. ImageR.-2003.-No. 14.-P. 369-388.

61. Eshelman, L.J. Biases in the crossover landscape Текст . / L.J. Eshelman, R.A. Caruana, J.D. Schaffer // Proceedings of the Third International Conference on Genetic Algorithms. 1989. - P. 10-19.

62. Fogel, D.B. Meta-evolutionary programming Текст . / D.B. Fogel, L.J. Fogel, J.W. Atmar // Proceedings of 25th Asilomar Conference on Signals, Systems and Computers / ed. R.R. Chen. Pacific Grove, CA, 1991. - P. 540-545.

63. Gagne, С. Genericity in evolutionary computation software tools: principles and case-study Текст . / С. Gagne, M. Parizeau // International Journal on Artificial Intelligence Tools. 2006. - Vol. 15, no. 2. - P. 173-174.

64. Gatlin, K.S. OpenMP and С++ Электронный ресурс . / K.S. Gatlin, P. Isensee // http://www.viva64.com/go.php7urHl 13

65. Goldberg, D.E. A comparative analysis of selection schemes used in genetic algorithms Текст . / D. Goldberg, K. Deb // Foundations of Genetic Algorithms.- 1991. P.69-93.

66. Goldberg, D.E. Genetic algorithms in search, optimization and machine learning Текст . / D.E. Goldberg. Addison-Wesley, 1989.

67. Goldberg, D.E. Genetic algorithms, noise, and the sizing of populations Текст . / D.E. Goldberg, K. Deb, J.H. Clark // Complex Systems. -1992. No.6. - P. 333-362.

68. Gonzalez, R.C. Digital Image Processing Using MATLAB Текст . / R.C. Gonzalez, R.E. Woods, S.L. Eddins. Prentice Hall, 2004

69. Harik, G.R. A parameter-less genetic algorithm Текст . / G.R. Harik, F.G. Lobo // Proceedings of the Genetic and Evolutionary Computation Conference. Vol.1. Morgan Kaufmann, 1999. - P.258-265.

70. Hinterding, R. Adaptation in evolutionary computation: A survey Текст . / R. Hinterding, Z. Michalewicz, A.E. Eiben // Proceedings of the 4th IEEE International Conference on Evolutionary Computation. Indianapolis, 1997. - P.65-69.

71. Hinterding, R. Adaptation in evolutionary computation: A survey Текст . / R. Hinterding, Z. Michalewicz, A.E. Eiben // Proceedings of the 4th IEEE International Conference on Evolutionary Computation. Indianapolis, 1997. - P.65-69.

72. Hinterding, R. Gaussian mutation and self-adaptation in numeric genetic algorithms Текст . / R. Hinterding // IEEE International Conference on Evolutionary Computation. IEEE Press, 1995. - P. 384-389.

73. Holland, J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence Текст . / J. H. Holland. — The MIT Press, Cambridge, 1992.

74. Holland, J.H. Adaptation in natural and artificial systems Текст . / J.H. Holland. Michigan: The University of Michigan Press, 1975.

75. Holland, J.H. Building blocks, cohort genetic algorithms, and hyperplanedefined functions Текст . / J.H. Holland // Evolutionary Computation.- 2000. Vol. 8, no. 4. - P. 373-391.

76. Itzkowitz, M. An OpenMP Runtime API for Profiling Электронный ресурс. / M. Itzkowitz, О. Mazurov, N. Copty, Y. Lin. Sun Microsystems, Inc. // http://www.compunity.org/fiitures/omp-api.html

77. Jacobson, I. Object-Oriented Software Engeneering Текст . / I. Jacobson. Reading. MA: Addison-Wesley, 1992.

78. Jahne, B. Digital Image Processing Текст . / В. Jahne. Berlin: Springer-Verlag, 2002.

79. Jain, A. K. Fundamentals of Digital Image Processing Текст . / A.K. Jain. Englewood Cliffs, NJ: Prentice Hall, 1989.

80. Karkavitsas, G. Object localization in medical images using genetic algorithms Текст . / G. Karkavitsas, M. Rangoussi. World Academy of Science, Engineering and Technology, 2005

81. Kita, H. A comparison study of self-adaptation in evolution strategies and real-coded genetic algorithms Текст . / H. Kita // Evolutionary Computation.- 2000. Vol. 9, no. 2. - P. 223-241.

82. Koljonen, J. Genetic algorithm for optimizing fuzzy image pattern matching Текст . / J. Koljonen, J.T. Alander // Proceedings of the Ninth

83. Scandinavian Conference on Artificial Intelligence (SCAI 2006), Espoo, Finland, October 25-27, 2006.

84. Koza, J. R. Genetic Programming Текст . / J. R. Koza. — Cambridge: The MIT Press, 1998. 609 c.

85. Laboratory for Image and Video Engineering, официальный сайт Электронный ресурс . // http://live.ece.utexas.edu/

86. Li, С. Content-partitioned structural similarity index for image quality assessment Signal Processing Текст . / С. Li, A. C. Bovik // Image Communications. 2010. - Vol. 25, no. 7. - P. 517-526

87. Liskov, B. Data Abstraction and Hierarchy Текст . / В. Liskov. -SIGPLAN Notices, 1988.

88. Martin, R.C. Agile Software Development: Principles, Patterns, and Practices / R.C. Martin. Prentice Hall, 2002. - 529 p.

89. Meyer, B. Object-Oriented Software Construction Текст . / В. Meyer. Upper Saddle River. New Jersey: Prentice Hall, 1997.

90. Mitchell, M. An Introduction to Genetic Algorithms Текст . / M. Mitchell. Cambridge, MA: The MIT Press, 1996.

91. Mitra, S.K. Nonlinear Image Processing Текст . /S.K. Mitra, Sicuranza G.L. NY: Academic Press, 2000.

92. Munteanu, C. Gray-Scale Image Enhancement as an Automatic Process Driven by Evolution Текст . / С. Munteanu, A. Rosa // IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics. - Vol. 34. -2004.-P. 1292-1298.

93. Niblack, W. An Introduction to Digital Image Processing Текст . / W. Niblack. Englewood Cliffs, NJ: Prentice Hall, 1986.

94. Page-Jones, M. The Practical Guide to Structured Systems Design. 2d ed. Текст . / M. Page-Jones. Englewood Cliff, New Jersey: Yourdon Press Computing Series, 1988.

95. Pavlidis, T. Algorithms for Graphics and Image Processing Текст . // Т. Pavlidis. Rockville, MD: Computer Science Press, 1982.

96. Petrou, M. Image Processing: The Fundamentals Текст . / M. Petrou, P. Bosdogianni. John Wiley & Sons, UK, 1999.

97. Prugel-Bennett, A. The mixing rate of different crossover operators Текст. / A. Prugel-Bennett // Foundations of Genetic Algorithms 6. 2001. - P. 261-274. // http://citeseer.ist.psu.edu/

98. Rahman, Z. Retinex Processing for Automatic Image Enhancement Текст. / Z. Rahman, D.J. Jobson, G.A. Woodell // Journal of Electronic Imaging. January, 2004. - P. 100-110.

99. Rahman, Z. Image enhancement, image quality and noise Текст . / Z. Rahman, D.J. Jobson, G.A. Woodell, G.D. Hines // Proc. of SPIE Photonic Devices and Algorithms for Computing VII. 2005.

100. Rechenberg, I. Evolutionsstrategie: Optimierung technischer systeme nach prinzipien der biologischen evolution Текст . / I. Rechenberg // Werkstatt Bionik und Evolutionstechnik. Stuttgart: Frommann-Holzboog, 1973.

101. Rizzi A. From Retinex to ACE: Issues in developing a new algorithm for unsupervised color equalization Текст . / A. Rizzi, C. Gatta, and D. Marini // Journal of Electronic Imaging, vol. 13, no. 1, pp. 75-84, 2004.

102. Russ, J.C. The Image Processing Handbook, 3rd ed. Текст . / J.С. Russ. CRC Press, Boca Raton, FL, 1999.

103. Schwefel, H.P. Numerical Optimization of Computer Models Текст. / H.P. Schwefel. John Wiley&Sons, 1981.

104. Schwefel, H.-P. Numerische Optimierung von computer-modellen mittels der evolutionsstrategie Текст . / H.-P. Schwefel // Interdisciplinary Systems Research. 1977. Vol. 26.

105. Sestoft, P. Numeric Performance in C, C# and Java. Working Note Электронный ресурс. / P. Sestoft. IT University of Copenhagen, 2010 // http://www.itu.dk/people/sestoft/papers/numericperformance.pdf

106. Sheikh, H.R. An Information Fidelity Criterion for Image Quality Assessment Using Natural Scene Statistics Текст . / H.R. Sheikh, A. C. Bovik, and G. de Veciana // IEEE Transactions on Image Processing. May 2005.

107. Sobol R. Improving the Retinex algorithm for rendering wide dynamic range photographs Текст . / R. Sobol. Proc. SPIE 4662. - 2002. - pp. 341-348.

108. Spitsyn, V.G. Application of Evolving Artificial Neural Network for Image Processing Текст . / V.G. Spitsyn, Y.R. Tsoy // USNC/URSI National Radio Science and AMEREM Meetings. 9-14 July 2006, Albuquerque, New Mexico, USA.-P. 745.

109. Syswerda, G. Uniform crossover in genetic algorithms Текст . / G. Syswerda // Proceedings of Third International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann, 1989. - P.2-9.

110. Tao, L. An Efficient Illuminance-Reflectance Nonlinear Video Stream Enhancement Model Текст . / L. Tao, V.K. Asari // SPIE-IS&T Electronic Imaging. Vol. 6063. 2006. - P. 606301-1-606301-12.

111. Wang, Z. Image Quality Assessment: From Error Visibility to Structural Similarity Текст . / Z. Wang, A.C. Bovik, H.R. Sheikh, E.P. Simoncelli // IEEE Transactions on Image Processing. Vol. 13, no. 4. - 2004.

112. Whitley, D. A Genetic Algorithm Tutorial. Technical Report CS-93-103 (Revised) Текст . / D. Whitley. Department of Computer Science, Colorado State University, Fort Collins, US, 1993.

113. Whitley, D. An Overview of Evolutionary Algorithms: Practical Issues and Common Pitfalls Текст . / D. Whitley // Journal of Information and Software Technology. 2001.

114. Whitley, D. Genetic Algorithms and Neural Networks: Optimizing Connections and Connectivity Текст . / D. Whitley, T. Starkweather, C. Bogart // Parallel Computing, 1990, Vol. 14, pp. 341-361. // http://www.cs.colostate.edu/~genitor/

115. Whitley, D. Genitor: A different genetic algorithm Текст . / D. Whitley, J. Kauth // Proceedings of the Rocky Mountain Conference on Artificial Intelligence. Denver, CO, 1988. - P. 118-130.

116. Wolberg, G. Digital Image Warping Текст . / G. Wolberg. New York: IEEE Computer Society Press, 1990.

117. Yang, J. Feature subset selection using genetic algorithm Текст . / J. Yang, V. Honavar // Genetic Programming 97. San Francisco, Morgan Kaufmann Publishers, 1997. - P. 380-385.

118. Young, T.Y. Handbook of Pattern Recognition and Image Processing / T.Y. Young, K. S. Fu. San Diego, CA: Academic Press, 1986.