Содержание к диссертации
Введение 4
1. Анализ основных подходов к построению процедур анализа изображений... 19
Неформальная постановка задачи конструирования: процедур идентификации и обнаружения объектов на изображениях 19
Подходы, основанные на использовании библиотек функций 23
1.3- Алгоритмы вычисления оценок 27
Методы автоматизированного конструирования отдельпътх элементов алгоритма распознавания 30
ИспользоБанис баз знаний 32
Генетическое программирование 36
Выводы 44
2. Метод автоматизированного конструирования субоптимальных процедур
идентификации и обнаружения объектов на изображениях 46
Исходные данные 46
Построение субоптимальной процедуры идентификации объектов одного класса 49
Обоснование применения ГА для поиска оптимальных решений 52
Построение субоптималыюй процедуры обнаружения объектов одного класса 54
Построение субоптимальных процедур идентификации и обнаружения объектов нескольких классов 58
Повышение устойчивости конструируемых процедур 61
27, Инвариантность решающих процедур к сдвигу, повороту и
масштабированию объекта на изображении 64
2.8. Выводы - 65
3. Модель генетического алгоритма для поиска субоптимальной процедуры
распознавания объекта на цифровом изображении,,,, 66
^ 3.1. Модель генетического алгоритма для поиска субоптимальных процедур
идентификации и обнаружения объектов одного класса. 66
3.2. Функционал оценки качества процедур идентификации и обнаружения
объектов одного класса 75
3.3, Модель генетического алгоритма для поиска субоптимальпых процедур
идентификации и обнаружения объектов нескольких классов 79
3.4. Выводы 83
4. Система автоматизированного конструирования субоптимальных процедур
анализа изображений 84
Структура системы автоматизированного конструирования субоптимальных процедур анализа изображений 84
Базовые алгоритмы 89
Алгоритм выполнения решающей процедуры 98
Алгоритм оценки качества хромосомы 103
Алгоритм формирования: очередной популяции 105
Алгоритм регенерации популяции 107
Экспериментальная проверка работоспособности метода автоматизированного конструирования субоптималызьтх процедур распознавания объектов на изображениях 109
4.8. Выводы 121
Заключение 122
Список литературы 123
Введение к работе
Актуальность работы. Проблема разработки методой, позволяющих автоматизировать процессы выбора и настройки алгоритмического и программного обеспечения идентификации и обнаружения объектов на цифровых изображениях, является актуальной. Задачи идентификации и обнаружения объектов на цифровых изображениях возникают в самых различных областях пауки я техники [1,3Р6Д8,23,29]> К настоящему времени разработано большое число методов, апгоритмов, моделей, которые позволяют решать различные задачи в этой области. Однако, проблема создания алгоритмов решения вновь возникающих задач идентификации и обнаружения является чрезвычайно трудоемкой, требующей наличия большого опыта в области анализа изображений.
Основное внимание в литературе при освещении вопросов создания
процедур распознавания уделено применению специализированных библиотек
функций [27,31,35,3б.,39,45,51], моделей алгоритмов вычисления оценок
[7,8,9,10..12,13,19,20], методам, основанным на использовании моделей
предметной области [3 3,43,44,47,54], а также теории генетического
программирования [30,32/1-9,53]. Проведенный анализ показал, что
существующие подходы к решению поставленной задачи обладают рядом
недостатков, препятствующих их эффективному применению на практике. В
*< работе предложен новый метод построения процедур идентификации и
обнаружения объектов на цифровых изображениях, основанный на автоматическом выделение характерных локальных свойств объекта и применяющий теорию генетического программирования для конструирования на основе выделенных свойств решающих процедур, которые способны работать в реальном масштабе времени. Данный метод автоматически подстраивается под специфику каждой конкретной решаемой задачи и позволяет учитывать опыт, накопленный исследователями в области анализа изображений.
Цель дыесеутаиии - разработка метода автоматизированного конструирования процедур обнаружения и идентификации объектов на цифровых изображениях, которые удовлетворяют заданным требованиям по времени работы и погрешности распознавания. Процедуры, отвечающие указанным требованиям, будем называть эффективными решающими процедурами.
Практическая цель работы - разработка специализированного
программного обеспечения, реализующего процесс конструирования процедур
идентификации и обнаружения, а также и экспериментальное исследование
у, разработанного метода и соответствующей программной системы.
Задачи. Для достижения поставленной цели требуется:
сформулировать принципы, которые позволили бы автоматизировать
процесс конструирования процедур идентификации и обнаружения
объектов на изображениях;
разработать модели представления процедур идентификации и обнаружения объектов;
разработать критерий оценки эффективности конструируемых
решающих процедур;
разработать метод отбора эффективных процедур идентификации и обнаружения;
разработать программное обеспечение, реализующее данный метод;
провести экспериментальное исследование эффективности предложенного метода.
Научная новизна. Предложен новый метод автоматизированного конструирования процедур идентификации или обнаружения объектов на изображениях. Метод отличается тем, что с целью повышения эффективности создаваемых процедур в нем в автоматизированном режиме формируется набор идентификационных признаков, характерных для объектов заданного класса, а решающие процедуры основываются на выбранных признаках.
Предложен новый подход к автоматизированному выбору идентификационных признаков объектов, который позволяет создавать устойчивые системы признаков. Признаки конструируются по эталонному изображению объекта, которое одновременно содержит разнородную информацию: о контурах, относительном расположении признаков, цвете и т.п. Процесс выбора признаков основывается на применении теории генетических алгоритмов.
Для реализации процесса отбора более эффективных процедур предложены обобщенные критерии оценки их оптимальности. Разработанный функционал объединяет как точностные и временные показатели решающей процедуры в целом, так и индивидуальные характеристики устойчивости идентификации отдельных ее подпроцедур.
Разработаны модели представления процедур идентификации и обнаружения объектов. Модели имеют модульную структуру и отличаются тем, что каждый составляющий ее элемент соответствует одному из выбранных идентификационных признаков, а основу моделей составляет набор атрибутов и связей между составляющими элементами, который характеризует порядок их выполнения, области применения на изображении и ряд свойств, определяющих способность элемента к идентификации объекта.
Практическая значимость. Диссертационная работа направлена на решение задач, имеющих непосредственное практическое значение.
Разработано программное обеспечение конструирования эффективных процедур идентификации и обнаружения, удовлетворяющих заданным требованиям по времени работы и погрешности распознавания. Проведено экспериментальное исследование его работы на задачах с реальными изображениями.
Предложенное программное обеспечение может быть использовано для конструирования процедур распознавания в следующих областях:
автоматические системы принятия решений, основанные на анализе визуальной информации;
робототехника;
системы контроля качества продукции на производстве.
Апуобаиия работы. Результаты работы докладывались и обсуждались
на следующих конференциях и семинарах:
XI Международная научная конференция студентов и аспирантов по фундаментальным наукам "Ломоносов", Россия, Москва, 2002;
12-я Международная конференция по компьютерной графике ГРАФИКОН-2002, Россия, Нижний Новгород, 2002;
6-я Международная конференция "Распознавание образов и анализ изображений: новые информационные технологии" (РОЛИ-6-2002), Россия, Великий Новгород, 2002;
Ломоносовские чтения-2003, Россия, Москва, 2003;
Всероссийская научно-техническая конференция "Методы и средства обработки информации" (МСО-2003), Россия, Москва, 2003;
Семинар по обработке экспериментальных данных при помощи нейронных сетей и генетических алгоритмов под руководством Королева Л.Н. и Поповой Н.Н. (факультет ВмиК МГУ).
Научно-исследовательский семинар по автоматизации
программирования под руководством Шура-Бура М.Р.
Публикации. Основные результаты работы изложены в 8-й научных публикациях [57-64].
Структура а объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 126 страницах. Список литературы включает 64 наименования. В работе содержится 42 рисунка и 5 таблиц.
Содержание работы. Во введении обоснована тема диссертационной работы, ее актуальность и практическая значимость, сформулированы основные задачи, представлено краткое содержание глав диссертации.
В первой главе дана неформальная постановка решаемых задач. С использованием постановки классической задачи распознавания, сформулированы задачи идентификации и обнаружения объектов на цифровых изображениях. Рассмотрена общая схема работы алгоритма распознавания, выделены составляющие ее элементы, обоснованный и корректный выбор которых способствует созданию эффективного решающего алгоритма.
Приведен критический обзор и анализ методов и моделей, наиболее часто используемых при решении задач автоматизированной генерации процедур идентификации и обнаружения объектов на изображении.
Основное внимание в литературе уделяется непосредственному использованию специализированных библиотек функций. Этот подход позволяет решать чрезвычайно широкий круг задач анализа изображений. Его сочетание с технологией визуального программирования существенно облегчает конструирование целевого алгоритма. Однако, подобные системы обеспечивают поддержку процесса разработки алгоритма анализа изображений лишь на этапе его реализации, тогда как его проектирование пользователь вынужден выполнять самостоятельно. Данный недостаток затрудняет получение эффективных процедур решения задач идентификации и обнаружения, а также приводит к значительному увеличению времени, затрачиваемому на их конструирование.
Модели алгоритмов вычисления оценок по одномерной (АВО) и двумерной (ДАВО) информации предлагают необходимый формализм для применения математических методов при построении алгоритмов распознавания. Вместе с гем необходимые компоненты этих моделей построены только для ряда практических задач, а проблема их создания в общем случае является нетривиальной.
Методы автоматизированного конструирования отдельных элементов алгоритма распознавания, таких как систем идентификационных элементов и моделей исследуемых объектов, обеспечивают существенную поддержку при использовании различных подходов к построению процедур анализа
изображений. Однако, область применения данных систем существенно ограничена, т.к. в основе их функционирования лежит поиск низкоуровневых особенностей исследуемой сцены, таких как точки изменения кривизны контура, сегменты прямых линий и окружностей, которые являются эффективными только на изображениях с высоким значением соотношения "сигнал-шум".
Экспертные системы автоматически конструируют процедуру анализа заданного изображения, используя при этом предварительно сформированную модель исследуемой предметной области, которая в большинстве случаев представляет собой Байесовскую семантическую сеть. Они являются эффективными для решения задач в хорошо исследованных областях (таких как анализ медицинских изображений, распознавание отпечатков пальцев), для которых существуют формализованные системы знаний. Для получения такого рода формализованных баз знаний необходим сложный этап предварительного анализа предметной области. Выполнение этого этапа, который является чрезвычайно трудоемким и требует значительного времени, будет оправдано только при разработке крупных промышленных систем машинного зрения.
Подходы, основанные на теории генетического программирования, позволяют автоматически конструировать решающие процедуры, требуя задания лишь множества изображений распознаваемых объектов. Построение решающего алгоритма в этом случае осуществляется через поиск оптимальной комбинации базовых операторов, таких как, доступ к пикселю изображения, вычисление средней яркости в заданной области, вычисление минимального и максимального значения яркости и т.п. В этих подходах не предусмотрено использование базовых операторов, основанных на поиске характерных локальных свойств объекта.
Критический обзор и сравнение методов, проведенные в первой главе, показали, что перспективным направлением в решении задачи построения процедур идентификации и обнаружения объектов на цифровых изображениях является разработка метода, опирающегося на автоматическое выделение характерных локальных свойств объекта и применяющего теорию генетического программирования для конструирования на их основе решающих процедур. Метод должен обладать способностью автоматически подстраиваться под специфику каждой конкретной решаемой задачи, а также учитывать опыт, накопленный исследователями в области анализа изображений.
Вторая глава посвящена разработке основных принципов функционирования предлагаемого метода, а также моделей процедур идентификации и обнаружения объектов нескольких классов.
В рамках метода рассматриваются полутоновые изображения объектов, обладающие следующими свойствами.
Объекты представлены своими проекциями на плоскость.
Объекты одного класса получены путем одного и того же проектирования на плоскость и имеют одинаковую структуру.
Допускается пропорциональное изменение размеров объектов внутри одного класса (масштабирование).
Ориентация и положение объекта в плоскости не фиксированы. Метод оперирует изображениями, представленными в пиксельном виде.
Исходными данными являются:
множество эталонных изображений объектов распознаваемых
классов, по одному для каждого класса;
обучающая выборка, состоящая из множества пар изображение-флаг, где значение флага определяет, объект какого класса присутствует на изображении, в случае решения задачи обнаружения каждый элемент выборки также содержит координаты представленного на изображении объекта;
пороговое значение для меры близости - число из интервала (ОД], такое что, если значение меры близости двух изображений превышает данный порог, то считается, что на изображениях представлены объекты, относящиеся к одному классу;
максимально допустимая погрешность в определении координат расположения объекта на изображении (для задачи обнаружения). Целью метода является построение субоптимальной процедуры, которая
обладает следующими свойствами:
является минимизированной по времени своего выполнения;
идентифицирует объекты заданных классов в соответствии с заданным порогом для меры близости;
определяет координаты расположения объектов на изображениях с погрешностью, не превышающей заданного максимально допустимого значения (в случае решения задачи обнаружения).
Рассмотрим задачу построения эффективной процедуры идентификации объектов одного класса. В этом случае множество эталонных изображений содержит единственный элемент 1т.
В рамках разработанного метода каждая процедура в общем случае представима в виде упорядоченной последовательности: p=(pi,p2,-~,Pm)i где/?; является процедурой идентификации некоторого фрагмента объекта заданного класса. Такие процедуры pi будем называть элементарными процедурами. Элементарная процедура идентифицирует соответствующий ей фрагмент в некоторой позиции на изображении, если значение меры близости между фрагментом и областью изображения в данной позиции превышает заданное пороговое значение. Число элементарных процедур, входящих в последовательность, будем называть длиной процедуры р. Решение об идентификации объекта на изображении принимается па основе результатов последовательного применения к этому изображению каждой из элементарных процедур. Будем считать, что процедура р~(рі,р2,—,Рт) осуществила идентификацию заданного объекта, если на изображении были обнаружены все фрагменты, сопоставленные элементарным процедурам pt. Пусть множество W состоит из всевозможных процедур, отвечающих описанной структуре.
Пусть заданы модели некоторых базовых алгоритмов распознавания, хранящихся в системной базе знаний. Каждый из данных алгоритмов допускает свою настройку на идентификацию определенного изображения. Множество W, которое является подмножеством W, состоит из процедурр~(рі,р2,—,рщї, таких что каждая pt сконструирована путем настройки одной из моделей базовых алгоритмов распознавания. Следовательно, при использовании эффективных базовых алгоритмов оптимальная процедура из множества W является субоптимальной процедурой для множества W.
Задача построения субоптимальной процедуры сводится к задаче ее поиска в подмножестве W процедур идентификации заданного объекта, которое формируется по эталонному изображению 1т и с использованием алгоритмов из базы знаний.
Скорость и точность работы каждой процедуры из данного подмножества определяется по результатам ее применения к изображениям из обучающей выборки.
Для построения процедур, формирующих множество W на эталонном
изображении 1т объекта заданного класса, выбирается ряд фрагментов
Imj (рис. 1). Размеры этих фрагментов, а также их количество определяется при помощи равномерно распределенной случайной величины. Для каждого фрагмента Imj случайным образом выбирается один из заданных алгоритмов, хранящихся а базе знаний системы. Для каждой такой пары фрагмент-алгоритм конструируется элементарная процедура pj, которая выполняет идентификацию данного фрагмента при помощи заданного алгоритма. Из полученных процедур Pi формируется процедура р=(рьРъ —,ргп)> которая вьшолняет идентификацию объектов заданного класса с некоторой точностью. Множество W состоит из всевозможных процедур, построенных по данной схеме и имеющих длину, не превышающую заданного значения.
^2
Рг.
Рис. 1. Конструирование процедуры идентификации.
Поиск оптимальной процедуры идентификации в подмножестве W осуществляется при помощи генетических алгоритмов,
Была разработана модель процедуры идентификации р=(рі,рь...,рт}> которая обладает следующими свойствами.
1.
Каждой элементарной процедуре pj поставлен в соответствие
единственный фрагмент эталонного изображения, идентификацию
которого она выполняет.
2. 3.
Элементарные процедуры pj выполняются последовательно.
Для каждого фрагмента Imj а, следовательно, и соответствующей ему
процедуры pj, определен вектор его геометрического расположения
относительно следующего фрагмента Imj+i. Данная информация
позволяет ограничивать область применения каждой последующей
элементарной процедуры, начиная со второй, это приводит к
увеличению скорости работы всей процедуры идентификации в
целом, а также повышению точности получаемых результатов.
4. Для принятия решения об идентификации объекта заданного класса на входном изображении необходимо, чтобы результирующие значения мер близости для всех pj на данном изображения превышали заданный порог.
Метод, описанный на примере построения процедуры идентификации, служит основой для решения задачи конструирования процедуры обнаружения объекта заданного класса на изображении. При этом возможность присутствия в анализируемой сцене нескольких объектов из предметной области, а также необходимость вычисления координат распознанных объектов обусловили введение в модель и схему функционирования метода ряда новых элементов: вес распознаваемого фрагмента, схема вычисления координат расположения объекта на изображении, "механизм возвратов".
Под понятием вес фрагмента будем понимать количественный показатель, характеризующий степень "уникальности" данного фрагмента эталонного изображения. Принцип его вычисления основывается на подсчете количества позиций эталонного изображения, в которых значение меры близости между данным фрагментом и областью изображения превышает заданный порог. Весовой коэффициент лежит в диапазоне [1,2] и рассчитывается по следующей формуле, полученной эмпирически:
1, loct = 1:
\.\,ІОС;=2\
1.2,/оС; - 3;
wt =
1.3,/ос,=4;
1.4, loct = 5;
ІОС; -1
1.5 + l ,ІОС: >5.
2*(IocMaxj-l)
где Iocj - число позиций на эталонном изображении, в которых значение меры близости между фрагментом и областью изображения превышает заданный порог; ІосМах^ - общее количество позиций на эталонном изображении, где может быть идентифицирован данный фрагмент.
Для вычисления вектора положения U всего объекта па изображении используется выражение:
U = z + v,
где z - вычисленный вектор расположения фрагмента с наименьшим весом, v - вектор относительного расположения этого фрагмента на эталонном изображении.
Присутствие на изображении нескольких объектов или частей объектов из предметной обпасти может привести к ложному обнаружению некоторых характерных признаков, по которым построена решающая процедура. С целью учета данной особенности в модель процедуры обнаружения был введен дополнительный элемент - "механизм возвратов". Логика функционирования "механизма возвратов" предусматривает возможность повторных применений элементарной процедуры рі в случае, если точность работы последующих элементарных процедур не удовлетворяет заданному порогу.
Рассмотренный метод был расширен на случай решения задач идентификации и обнаружения объектов нескольких классов. В основе данного обобщения лежит идея декомпозиции исходной задачи на ряд подзадач, каждая
из которых заключается в независимом определении принадлежности изображенного объекта к каждому из заданных классов, с последующим объединением полученных результатов. Решающая процедура, осуществляющая идентификацию объекта, принадлежащего одному из N классов, имеет следующую структуру;
где р' =(р[,р2,...,р'), i=l,2,...,N - подпроцедура, выполняющая
"Н
идентификацию объектов i-го класса и конструируемая в соответствии с описанным ранее методом.
Выполнение всей процедуры/' заключается в независимом лрименении к
входному изображению каждой из составляющих ее лодпроцедур рг. Принятие решения об идентификации объекта на изображении 1т осуществляется в соответствии со следующей логикой.
1. Если существует единственный номеру, такой что pJ (Imj^TRUE к для всех
i = l,2,.,.,j — l,j + \,...N рг (Im)=FALSE, то объект, изображенный на 1т, является представителем класса/.
2. Если для всех / = 1,2 N pl (Im)=FALSE, то в этом случае представленный
объект не относится ни к одному из заданных классов.
3. В остальных случаях, т.е. когда существуют ji, j?,, ... jk (А>1), таких что
р1' (Im)=TRUE, результат идентификации объекта на изображении 1т не
определен.
Здесь: р1(1т) означает применение подпроцедуры р1 к входному
изображению 1т, при этом р1(1т) возвращает значение TRUE, если на
изображении идентифицирован объект, соответствующий р', FALSE - в противном случае.
Предложенная схема была модифицирована для решения задачи построения субоптимальных процедур обнаружения объектов нескольких классов. В этом случае Результат работы процедуры обнаружения формируется по следующим правилам.
1. Если существуют номера7/,7 jk, такие что ph (Im)=TRUE, и для
всех і = 1,2,..., к \и^—и^\>Ь, где d =1,2,...„г —1,г+ 1,...,4 , то на
изображении присутствует к объектов, являющихся представителями классов7/,7 Jk-
Если для всех z =1,2,.,.,7*/ р1' (Im)=FALSE, то в этом случае На изображении нет объектов, относящихся к заданным классам.
Если существуют номера ji и J2, такие что pJi (Im)=TRJJE, pJl (Im)=TRUE и \Uh ~Uh \
Здесь: Uj - вектор положения объекта, локализованного подпропедурой
pJ; Ъ - заданная максимально допустимая погрешность в определении координат.
Требование к применимости конструируемых решающих процедур к реальным изображениям, в том числе тем, которые обладают низким соотношением сигнал-шум, способствовало разработке дополнительных элементов метода, повышающих его эффективность. К ним относятся: локальный механизм вычисления весов фрагментов и глобальный механизм постпроверки решающих процедур.
Учет весов фрагментов при оценке показателя качества решающих процедур позволяет отбирать уникальные характерные признаки анализируемого объекта и тем самым конструировать более устойчивые и эффективные процедуры распознавания, которые позволяют выполнять корректную идентификацию объектов при низком соотношении сигнал-шум, в том числе при высоком уровне перекрытия объекта распознавания другими элементами сцены.
Основная идея механизма постпроверки заключается в введении в процесс оценки эффективности конструируемых процедур дополнительного этапа, выполняющегося после корректной идентификации объекта. Он заключается в нопиксельном сравнении распознанного и локализованного объекта с эталоном соответствующего класса путем вычисления нормированного коэффициента корреляции:
где: Н - эталонное изображение объекта, S" - фрагмент изображения из
обучающей выборки, содержащий локализованный объект, к , s' - средние значения интенсивности изображений Ни S соответственно.
Полученное значение коэффициента корреляции используется для расчета обобщенной оценки эффективности конструируемых процедур.
Процедуры, конструируемые при помощи данного метода, способны проводить идентификацию и обнаружение объектов независимо от их размеров^ положения и ориентации на изображении. Описанные модели реализуют указанные требования к инвариантности следующим образом.
Инвариантность к сдвигу объекта в плоскости изображения достигается путем использования базовых алгоритмов, способных проводить распознавание характерных признаков независимо от их положения на изображении,
Реализация инвариантности к повороту объекта на изображении также основывается на применении соответствующих базовых алгоритмов, корректно функционирующих независимо от ориентации характерного признака. Кроме этого этап выполнения каждой элементарной процедуры заканчивается оценкой угла поворота локализованного признака относительно эталонного изображения. Полученное значение используется для корректировки области применения следующей элементарной процедуры.
Инвариантность к размерам распознаваемого объекта достигается путем применения традиционного метода обработки по пирамиде. Процедура распознавания применяется последовательно при различных предположениях о масштабе представленного объекта относительно его размера на эталонном изображении. Диапазон возможных предположений указывает пользователь. Решение о распознавании принимается по наилучшему из полученных результатов.
В третьей главе предложена модель генетического алгоритма (ГА) для поиска субоптимальных процедур идентификации и обнаружения объектов на
изображении, а также рассмотрена структура функционала оценки показателя качества конструируемых процедур.
Модель ГА для поиска субоптимальных процедур идентификации объектов одного класса имеет следующую структуру.
Каждому гену сопоставляется элементарная процедура идентификации, таким образом, хромосома, представляющая собой последовательность генов ограниченной, но не фиксированной длины, позволяет кодировать любую процедуру, конструируемую в рамках предложенного метода.
Инициализации начальной популяции решений осуществляется при помощи датчиков равномерно распределенных случайных величин.
В качестве оператора выбора решений для формирования поколения решающих процедур на следующей итерации используется традиционный метод "рулетки", для которого относительный показатель качества решающих процедур вычисляется по следующей формуле:
absFit(p)
relFit(p) =1
2 * mFitip) '
где absFit(p) - значение функционала качества процедуры р, mFit(p) -максимальное значение качества среди всех допустимых процедур.
Операция скрещивания (таблица 1) позволяет конструировать новые подпроцедуры путем перегруппировки составных частей существующих решений. При этом если получившаяся подпроцедура имеет длину больше заданной верхней границы, то лишние гены удаляются. Операция мутации (таблица 2) позволяет настроить новую элементарную процедуру, изменяя положение и/или размер соответствующего фрагмента эталонного изображения.
Таблица 1. Операция скрещивания.
Результат
Исходные данные
Р=Фьр2, -.?») и q=(qi,q2, -,qk> \
Cj=(PhP2,--,Pj-h qu-,qb)> С2=(ЧьЧъ ...,ди, Рї-,Рщ)
Таблица 2. Операция мутации
Исходные данные
Результат
РЧРьР2,-,Рь-.Рк)
й.
* Pi
P^(pLP2,-.p'i,-,Pm)
Условием окончания работы ГА является комплексный критерий, в соответствии с которым функционирование ГА завершается после выполнения заданного числа итераций или если качество найденного решения не улучшается на протяжении заданного интервала времени.
Особенность разработанного ГА, связанная с переменной длиной обрабатываемых им хромосом, может привести к возникновению ситуаций, когда в очередной построенной популяции подавляющее большинство хромосом имеют одинаковую длину. Такие ситуации значительно сужают область проводимого поиска и увеличивают вероятность остановки процесса в локальном экстремуме функции качества. Для решения данной проблемы в модель ГА был введен дополнительный механизм контроля длин процедур в популяции. Принципы его функционирования основываются на вычислении среднего квадратичного отклонения длин решающих процедур в популяции и
перегенерации всего текущего поколения в случае, если полученное значение меньше некоторого заданного пользователем порога.
Общая схема функционирования ГА поиска субоптимальной процедуры идентификации объектов одного класса состоит из следующих основных этапов.
Формирование начальной популяции процедур.
Контроль длин решающих процедур из текущей популяции.
Оценка показателя качества процедур из текущей популяции.
Выбор наиболее эффективной решающей процедуры по значениям показателя качества.
Если не выполнен критерий окончания работы ГА, то формирование новой популяции решающих процедур и переход на этап 2.
Модель ГА для поиска субоптнмальной процедуры обнаружения объектов одного класса имеет аналогичную структуру.
Разработанный функционал оценки качества решающих процедур реализует комплексный критерий минимизации вычислительных затрат процедур распознавания при условии соблюдения требований по точности распознавания. При этом разработанный критерий оценки качества объединяет как точностные и временные показатели всей процедуры в целом, так и индивидуальные характеристики устойчивости идентификации формирующих ее элементарных процедур. Вычисление значения показателя качества процедуры выполняется по значениям времени и точности, полученным по результатам ее применения к каждому изображению из обучающей выборки. Процедура с наименьшим значением показателя качества является искомой субоптимальной решающей процедурой.
Расчет значения показателя качества процедуры р=(рі,рг...,рщ> осуществляется по следующей формуле:
SsLE SzLS
здесь: w - вес процедуры р, вычисляемый как среднее арифметическое значений весов всех элементарных процедур pif входящих в состав р\ gp(p) -минимальное значение среди значений нормированных коэффициентов корреляции, полученных на этапе постпроверки процедуры р на всех изображениях обучающей выборки; f(p,S) - оценка частичного показателя качества процедуры р на отдельном изображении S; суммирование ведется по всем изображениям из обучающей выборки.
Вычисление значения частичного показателя качества процедуры р на каждом изображении S из обучающей выборки зависит от типа S.
В случае если S содержит объект заданного класса, применяется формула:
f(p,S) = KP>S) + A*t(p,S)*[l-ip(p)S)],
иначе:
Г (р, S) = t(p, S) + A* t(p, S) * lp{p, S),
где t(p,S) - вычислительная сложность процедуры p при обработке изображения S; lp(p,S) - оценка меря близости между объектом, идентифицированным процедурой р на изображении S, и объектом на эталонном изображении; А - константа, задаваемая пользователем.
Если хотя бы одна из элементарных процедур, входящая в состав р не отвечает заданному порогу для меры близости, то в качестве оценки показателя качества берется заранее выбранное максимальное значение:
f'(PiS) = MAX Основным принципом, лежащим в основе модели ГА для поиска субоптимальных процедур идентификации и обнаружения объектов N классов, является независимое использование JV популяций, каждой из которых соответствует свой класс объектов. При этом в рамках каждой популяции ГА функционирует по описанной выше схеме и выполняет поиск субоптимальной процедуры распознавания объектов соответствующего класса. Полная идентификационная процедура конструируется путем объединения подпроцедур с наименьшими значениями показателя качества, найденных в каждой из популяций. Схема работы данного ГА состоит из следующих этапов.
Независимое формирование начальных популяций для каждого класса объектов.
Оценка качества решающих процедур в каждой популяции.
Выбор процедуры с минимальным значением показателя качества из каждой популяции.
Построение полной идентификационной процедуры, на основе выбранных подпроцедур, и оценка ее качества.
Если не выполнен критерий окончания работы ГА, то формирование популяций следующего поколения и переход на этап 2.
Оценка показателя качества полной идентификационной процедуры р=(р[, р2, -., pN) выполняется путем суммирования значений показателей качества составляющих ее подпроцедур, вычисляемых по формулам, указанным выше:
/=]
Четвертая глава посвящена вопросам программной реализации разработанного метода и результатам тестирования построенной программной системы при решении задач идентификации и обнаружения объектов на реальных изображениях.
Система спроектирована с использованием объектно-ориентированного подхода. Каждая сущность, входящая в состав предложенного метода, реализована в виде отдельного класса. Общее число программных классов, формирующих архитектуру системы, 78.
Спроектированная структура программных классов и использование механизмов наследования и полиморфизма позволили реализовать абстрактный генетический алгоритм, независимый от типа решаемой задачи. Такая схема позволяет применять его для решения задач поиска как субоптимальных процедур классификации, так и обнаружения.
В качестве базовых алгоритмов, используемых для создания элементарных процедур распознавания, были выбраны:
алгоритм вычисления нормированного коэффициента корреттяции [24];
алгоритм на основе обобщенного преобразования Хафа [38];
алгоритм на основе «структурной» модификации обобщенного преобразования Хафа.
Основное внимание при реализации данных алгоритмов уделялось их быстродействию.
Алгоритм вычисления нормированного коэффициента корреляции основывается на рассмотрении изображений как двумерных функций яркости.
При этом измеряется мера близости двух изображений. В качестве такой меры используется нормированный коэффициент корреляции, вычисляемый по формуле:
Kf g) = (/<*.;y)-/)(g(*,.y)-g)
где: f,g- средние значения интенсивности для изображений / и g соответственно.
Алгоритм вычисления нормированного коэффициента корреляции не является инвариантным к повороту изображения.
Инвариантность алгоритма к масштабированию достигается путем применения традиционного метода обработки по пирамиде. В рамках этого метода пользователь задает уровни масштаба, на которых необходимо проводить распознавание искомого объекта. Основная идея метода заключается в создании нескольких изображений объекта, измененных в соответствии с заданными уровнями масштаба, и вычислении нормированных коэффициентов корреляции для каждого из них с последующим выбором максимального.
Обобщенное преобразование Хафа (GHT) [38] предназначено для обнаружения на изображении произвольных контурных объектов.
Пусть искомый объект задан с помощью просмотровой таблицы (lookup table, LUT):
Ш = {(фиф2,...,фп):фі є RJ = 1,...,п),
где (^,^2,...,^) - вектор значений переменных, которые однозначно
определяют положение точки контура объекта относительно его центра. Например, это могут быть угол между вектором на центр и нормалью к контуру в данной точке, и расстояние от точки до центра. Точка, соответствующая центру объекта, выбирается произвольно.
В основе обобщенного преобразования лежит использование пространства параметров. В качестве параметров будем рассматривать координаты центра искомого объекта. Каждая точка изображения голосует в пользу гипотезы о том, что контур искомого объекта проходит через нее. Для этого для каждой точки изображения, используя значения векторов из просмотровой таблицы, вычисляются все возможные положения центра искомого объекта. Получаемые гипотезы о положении центра аіасумулируюгся в отдельный массив. Локальные максимумы в аккумуляторном массиве соответствуют центрам искомых объектов на изображении. Контуром искомого объекта является множество точек, голосовавших в пользу найденного центра.
Алгоритм, основанный на обобщенном преобразовании Хафа, состоит из нескольких этапов:
Выполнение обобщенного преобразования Хафа и формирование аккумуляторного массива.
Поиск локальных максимумов аккумуляторного массива и формирование множества кандидатов положения центра искомого объекта.
Определение угла ориентации искомого объекта для каждого из сформированных кандидатов с использованием разработанного алгоритма, основанного на голосовании.
Вычисление нормированного коэффициента корреляции заданного изображения объекта и фрагмента на входном изображении для каждого из сформированных кандидатов. При этом учитывается найденный угол ориентации объекта в данной позиции.
Выбор в качестве результата кандидата с максимальным значением коэффициента корреляции.
Как следует из приведенного описания, алгоритм, основанный на обобщенном преобразовании Хафа, является инвариантным к повороту изображения объекта.
Инвариантность алгоритма к масштабированию достигается так же, как для алгоритма вычисления нормированного коэффициента корреляции, т.е. применением традиционного метода обработки по пирамиде. Для данного алгоритма метод реализован через масштабирование просмотровой таблицы исходного изображения.
Алгоритм, основанный на «структурной» модификации обобщенного преобразования Хафа, обладает более высокой скоростью работы и сохраняет большинство свойств обобщенного преобразования Хафа. Основная идея сокращения времени работы GHT на этапе голосования, который является наиболее вычислительно емким, заключается в выполнении просмотра только части записей просмотровой таблицы. В этом случае пользователь задает некоторое целое число А:, и в каждой точке при голосовании сканируется каждая к-я запись таблицы. После выполнения такой модификации обобщенного преобразования Хафа будут выделены объекты, у которых только k-я часть точек контура удовлетворяют описанию искомого объекта. Поиск искомого объекта среди полученных кандидатов осуществляется при помощи механизма проверки гипотез, описанного для случая обобщенного преобразования Хафа.
Основным отличием процедуры обнаружения от процедуры идентификации является применение «механизма возвратов», который допускает повторное выполнение процедур поиска идентифицирующих признаков, В подобных ситуациях прямое использование описанных алгоритмов приведет к существенному увеличению времени работы всей решающей процедуры. Поэтому в случае решения задачи обнаружения используются модификации базовых алгоритмов.
Идея проведенных модификаций заключается в следующем. Базовые алгоритмы, используемые в системе, выбирают объект наиболее «близкий» к искомому среди некоторого множества кандидатов. Причем наибольшие вычислительные затраты требуются для формирования этого множества. В разработанных модификациях базовых алгоритмов после первого запуска сохраняются полученные множества кандидатов без исключенного претендента, который был выбран в качестве результата. В случае повторного выполнения алгоритма поиск объекта наиболее «близкого» к искомому осуществляется среди уже имеющихся множеств. Таким образом, наиболее вычислительно емкий этап по-прежнему выполняется однократно,
В программной реализации базовых алгоритмов минимизирован объем вычислений, использующих операции над вещественными числами, применяются табличные вычисления, сохранение результатов работы наиболее вычислительно емких этапов алгоритмов для их возможного повторного использования. Это позволило существенно уменьшить время работы процедур, реализующих данные алгоритмы, и тем самым повысить их эффективность.
Для проверки работоспособности разработанного метода применительно к реальным изображениям использовалась база оцифрованных фотографий объектов различной структуры. Формат представления изображений - 8 бит на пиксель (256 градаций серого).
Результатами работы метода являлись сконструированные им субоптимальные процедуры распознавания заданных классов объектов. Для проверки эффективности построенных решающих процедур было проведено их тестирование на отдельных выборках изображений. Эти тестовые изображения не участвовали в процессе конструирования решающей процедуры, но были получены в тех же условиях, как изображешгя из обучающих выборок.
Экспериментальные исследования программной системы в целом подтвердили работоспособность предложенного метода автоматизированного конструирования субоптимальных процедур классификации и обнаружения объектов на изображениях. Признаки, автоматически выделяемые методом, опираются на элементы контуров объектов и однозначно классифицируют представленные изображения. Базовые алгоритмы, выбранные методом для реализации процедур распознавания выделенных признаков, являются наиболее эффективными среди имеющихся базовых алгоритмов для обрабатываемых изображений.
В заключении формулируются основные результаты работы.
