автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Обнаружение и оценивание границ объектов на изображениях в условиях аддитивного шума и деформирующих искажений
Автореферат диссертации по теме "Обнаружение и оценивание границ объектов на изображениях в условиях аддитивного шума и деформирующих искажений"
На правах рукописи
Соломатин Алексей Иванович
А
ОБНАРУЖЕНИЕ И ОЦЕНИВАНИЕ ГРАНИЦ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ В УСЛОВИЯХ АДДИТИВНОГО ШУМА И ДЕФОРМИРУЮЩИХ ИСКАЖЕНИЙ
Специальность 05.13.01 - «Системный анализ, управление и обработка информации (по отрасли радиотехника, автоматика, связь)»
АВТОРЕФЕРАТ 4847366
диссертации на соискание ученой степени кандидата физико-математических наук
1 9 МАЙ 2011
Воронеж-2011
4847366
Работа выполнена в Воронежском государственном университете.
Научный руководитель доктор технических наук, профессор
СИРОТА Александр Анатольевич
Официальные оппоненты: доктор физико-математических наук,
профессор БАЗАРСКИЙ Олег Владимирович,
кандидат физико-математических наук КУЦОВ Руслан Владимирович
Ведущая организация Саратовский государственный университет
имени Н.Г. Чернышевского
Защита состоится 23 июня 2011 года в 15.10 на заседании диссертационного совета Д 212.038.10 при Воронежском государственном университете по адресу: 394006, г. Воронеж, Университетская пл., 1, ВГУ, физический факультет, ауд. 428.
С диссертацией можно ознакомиться в научной библиотеке Воронежского государственного университета.
Автореферат разослан « » (М^^А^ 2011 г,
Ученый секретарь
диссертационного совета у МАРШАКОВ В. К.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Постоянно совершенствующиеся технические и информационные возможности различных систем дистанционного мониторинга и видеонаблюдения стимулируют потребность в развитии методов и средств автоматической и автоматизированной обработки получаемых цифровых изображений. Основной в них является задача понимания изображений, состоящая в извлечении необходимой для принятая дальнейших решений информации в автоматическом режиме. Данная задача, при отсутствии априорных данных об анализируемых изображениях, является плохо формализуемой. Поэтому на практике рассматриваются частные задачи понимания изображений, ориентированные на извлечение в некотором смысле заранее оговоренной и структурно определенной информации из изображений одинаковой и известной природы. Большинство систем, осуществляющих автоматическое извлечение такой информации из изображения, используют для этого методы обнаружения и классификации объектов или их фрагментов с последующей локализацией области их расположения.
Проблема обнаружения и локализации объектов на изображениях рассмотрена достаточно глубоко. Большой вклад в данную научную область внесли П.А. Бакуг, Р. Брунелли (R. Bruneiii), В.Н. Вапник, Р. Вудс (R. Woods), Р. Гонсалес (R. Gonzalez), А.Л. Горелик, Р. Дуда (R. Duda), А.И. Перов, У. Прэгг (W. Pratt), В.А. Сойфер, Ю.Г. Сосулин, И.В. Терентьев, А.П. Трифонов, К. Фукунага (К. Fukunaga), Я.А. Фурман, П.Харг (P.Hart), M. Хюккель (M. Hueckel), Ш.-К. Чэн (C.K. Chan), А.Я. Червоненкис, Л.П. Ярославский и др.
В тоже время известные алгоритмы имеют ряд ограничений. Одно из них состоит в недостаточном качестве обработки в условиях минимума априорной информации об обнаруживаемых объектах, например, отсутствия информации о яркости и форме границы объекта. При этом эталонные описания объектов отсутствуют, и задача поиска объектов должна ставиться как задача обнаружения и идентификации неодно-родностей, т.е. яркостных «всплесков», относительно которых могут быть известны только примерные размеры и относительный уровень перепада яркости. Другим существенным ограничением имеющихся решений, во многих случаях, является раздельный характер процесса обнаружения объекта и определения границ его локализации.
Однако даже в случае наличия эталонных изображений объектов всегда возникает задача выбора инвариантного и устойчивого описания эталонов. В этом плане, многие известные алгоритмы обработки изображений чувствительны к различным шумовым искажениям, изменениям яркости и ориентации объекта относительно эталонного образа. В связи с этим представляют интерес дальнейшие исследования, направленные на разработку быстродействующих алгоритмов обнаружения, инвариантных к повороту, масштабу и сдвигу, на основе эталонных описаний объектов или их фрагментов в присутствии характерного фона, содержащего дешифрирующие признаки.
Таким образом, тема диссертации, посвященная синтезу и анализу алгоритмов компьютерной обработки изображений в интересах обнаружения и оценивания границ пространственно локализованных объектов при различном уровне априорной неопределенности, представляется актуальной.
Тема диссертации входит в план научно-исследовательских работ Воронежского государственного университета по кафедре информационных систем.
Цель и задачи исследования. Целью исследования является синтез и анализ статистических, нейросетевых и эвристических алгоритмов обнаружения и оценивания параметров локальных неоднородностей (ЛН), а также обнаружения целостных объектов с замкнутыми границами неизвестной или деформированной формы в интересах создания эффективных средств компьютерной обработки цифровых изображений.
Для достижения цели в работе рассматриваются и решаются следующие
задачи.
1. Анализ известных методов обнаружения, классификации и локализации пространственно распределенных объектов и их частей, а также методов контурного анализа изображений.
2. Синтез и анализ статистических и нейросетевых алгоритмов совместного обнаружения и оценивания параметров локальных неоднородностей, представляемых моделью «идеального» перепада яркости, для различных уровней априорной неопределенности.
3. Синтез и анализ двухэтапного алгоритма совместного обнаружения и локализации объектов на основе выделения целостной замкнутой границы случайной формы по результатам вторичной обработки выделенных в ходе первичной обработки изображения локальных неоднородностей.
4. Исследование инвариантных к сдвигу и повороту алгоритмов обнаружения, классификации и локализации объектов и их фрагментов на цифровых изображениях, основанных на применении индексирующего разбиения кадров эталонного и наблюдаемого изображения по группам яркости.
Методы проведения исследования. При решении поставленных в диссертации задач использовались аналитические и вычислительные методы современной теории информационных процессов и систем, а именно: методы теории принятия статистических решений; методы теории вероятностей и математической статистики; методы теории графов; методы статистического имитационного моделирования, а также аппарат искусственных нейронных сетей.
Основные результаты, выносимые на защиту, и их научная новизна.
На защиту выносятся следующие результаты, впервые достаточно подробно развитые или полученные в работе:
1. Квазиправдоподобные и нейросетевой алгоритмы совместного обнаружения и оценивания параметров существенных локальных неоднородностей, представляемых в виде перепада яркости, обеспечивающие возможность использования различного объема априорной информации относительно уровней яркости фона и объекта, а также параметров расположения перепада.
2. Методики оценки безусловных и условных относительно полученных оценок параметров вероятностных характеристик обнаружения перепада яркости в локальном окне наблюдения, результаты численных расчетов и статистического моделирования показателей качества обнаружения для типовых условий наблюдения.
3. Двухэтапный алгоритм обнаружения объектов на изображениях, основанный на реализации вторичной обработки выделенной в ходе первичной обработки совокупности локальных неоднородностей и нахождении замкнутой максимально правдоподобной границы гипотетического объекта с использованием метода динамического программирования, что позволяет оптимизировать решение задачи обнаружения в условиях аддитивных помех и деформирующих искажений формы границ, а также ограничений по времени решения задачи.
4. Алгоритмы обнаружения и классификации множества однородных объектов, основанные на использовании инвариантных к сдвигу и повороту гистограммных описаний яркости и угловых координат элементов изображений, полученных при применении индексирующего разбиения кадров эталонного и наблюдаемого изображения по группам яркости, и обеспечивающий оперативный поиск объектов по информативным фрагментам в сочетании с характерным для них примыкающим фоном.
Научная новизна полученных результатов определяется следующим.
1. Рассмотрена задача совместного обнаружения и оценивания параметров существенной ЛН в элементарном окне наблюдения, описываемой в рамках модели «идеального» перепада яркости, наблюдаемого в присутствии аддитивного гауссовского шума. Получена структура оптимального алгоритма обнаружения и оценивания параметров перепада яркости, основанного на применении обобщенного метода правдоподобия при выборе статистических гипотез. Получены и проанализированы квазиправдоподобные алгоритмы обнаружения и оценивания параметров перепада яркости для различной априорной информации относительно яркости фона и объекта. Впервые предложена реализация нейросетевого алгоритма совместного обнаружения и оценивания параметров ЛН.
2. Предложена методика определения условных относительно полученных оценок параметров ЛН вероятностей ошибок первого и второго рода для каждого конкретного анализируемого локального участка изображения, основанная на полученных выражениях для моментов логарифма отношения правдоподобия при использовании модели обнаружения «идеального» перепада яркости в присутствии аддитивного гауссовского шума. Предложена методика расчета безусловных вероятностей ошибок первого и второго рода, основанная на численном интегрировании условной вероятности ошибок по параметрам перепада яркости.
3. Для объекта, характеризующегося замкнутой границей неизвестной или деформированной формы и наличием различимого перепада яркости на границе, а также диапазоном значений поперечного размера, синтезирован двухэтапный алгоритм обнаружения в присутствии шума, основанный на выделении совокупности локальных перепадов яркости на всем изображении в ходе первичной обработки и применении обобщенного метода максимального правдоподобия при сравнении статистических гипотез о наличии или об отсутствии замкнутой границы перепада яркости в поле всего наблюдаемого изображения в ходе вторичной обработки. Задача нахождения наиболее правдоподобного контура гипотетического объекта сведена к задаче поиска пути минимальной стоимости на графе.
4. Предложенный алгоритм обнаружения и классификации объектов или их фрагментов по эталонным изображениям, основанный на применении индексирующего разбиения сравниваемых кадров эталонного и наблюдаемого изображения на группы по базовому индексирующему признаку (яркость, цветность и т.д.), отличается использованием обобщенного гистограммного описания объектов, инвариантного к сдвигу, повороту и изменению масштаба. Алгоритм позволяет анализировать яркость и положение пикселей в выделенных группах в полярной системе координат и обеспечивает использование различных мер близости при сравнении образов. Предложена методика определения целесообразного количества применяемых при разбиении групп и количества пикселей в них.
Достоверность результатов работы. Результаты исследований, сформулированные в диссертации, получены на основе корректного использования взаимно дополняющих друг друга теоретических и экспериментальных (имитационное моделирование) методов исследований, совпадением результатов, полученных различными методами, между собой, а, в ряде частных случаев, с известными, наглядной физической трактовкой установленных закономерностей и соотношений.
Значимость для науки и практики. Методические и экспериментальные результаты работы отвечают потребностям важного направления - разработки и совершенствованию алгоритмов обнаружения, классификации и локализации объектов в интересах создания эффективных аппаратно-программных средств анализа изображений. Полученные аналитические выражения и зависимости для характеристик синтези-
рованных алгоритмов позволяют обоснованно выбрать необходимый алгоритм в соответствии с требованиями, предъявляемыми к показателям качества обработки информации с учетом существующих ограничений.
Результаты диссертационной работы имеют практическое значение для разработки специального математического и программного обеспечения в интересах автоматической обработки изображений при обнаружении, классификации и локализации образов, а также проведении контурного анализа в системах технической диагностики, пассивной оптической локации, дистанционного аэрокосмического мониторинга, а также в современных системах компьютерной микроскопии.
Реализация научных результатов. Полученные в диссертации результаты реализованы в Воронежском государственном университете в НИР «Кассиопея-ВГУ» при создании программного комплекса для обработки цифровых изображений.
Личный вклад автора. Основные результаты по теме диссертации получены лично автором и опубликованы в соавторстве с научным руководителем. В этих работах автору принадлежит проведение рассуждений и вывод аналитических зависимостей, необходимых для решения поставленных задач, организация экспериментов для обоснования алгоритмов, полученных теоретическим путем, анализ и интерпретация полученных результатов. В работе [2], опубликованной с участием других соавторов, соискателем предложен двухэтапный алгоритм обнаружения объектов на основе первичного контурного анализа изображения и проделаны основные теоретические расчеты для решения поставленной задачи.
Публикации. По теме диссертации опубликовано 10 работ, из них 3 работы - в изданиях, рекомендованных ВАК.
Апробация работы. Результаты диссертационной работы докладывались на XVI Международной научно-технической конференции «Радиолокация, навигация, связь» (Воронеж) в 2010 году; на VII Международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (Воронеж) в 2006 году, на VI, VII, VIII Международных конференциях «Информатика: проблемы, методология, технологии» (Воронеж) в 2006, 2007 и 2008 годах.
Структура и объем работы. Диссертация состоит из введения, четырех разделов, заключения и списка литературы из 106 наименований. Объем диссертации составляет 181 страницу, включая 170 страниц основного текста, содержащего 48 рисунков и 1 таблицу, 11 страниц списка литературы.
СОДЕРЖАНИЕ РАБОТЫ
Во введении к диссертации обоснована актуальность темы, сформулированы цель и задачи работы, ее научная новизна, практическая значимость полученных результатов и положения, выносимые на защиту.
В первой главе определяются основные термины и понятия компьютерной обработки изображений, приводятся общие схемы обнаружения и локализации объектов на изображениях, рассматриваются и анализируются известные подходы к решению указанных задач. Особое внимание уделяется рассмотрению результатов известных исследований, посвященных вопросам контурного анализа изображений.
Во второй главе рассматривается модель ЛН в виде «идеального» перепада яркости S(x,y) (М. Хюккель, А.И. Перов, Г.Г. Соколов), наблюдаемого в локальном окне в присутствии аддитивного гауссовского белого шума N(x,y)
{и, ^cosa + vsina <d,
■ О
u + n,.TCosa+ }>sina >d,
где и - интенсивность фона, u + h - интенсивность объекта, а - угол наклона перпендикуляра, проведенного к линии перепада яркости, относительно оси X , d - расстояние до линии перепада яркости. При этом параметры а и d определяют направление и положение перепада, h - уровень перепада (рис. 1). Чтобы перепад яркости в рамках такой модели можно было считать существенным для обнаружения и оценивания неизвестных
параметров в диссертации предложено ввести ограничения: -► X
\h\ > h и < dp . Первое ограничение связано с заданием ми- Рис. 1.
нимально допустимого уровня перепада h , второе - с тем, что объект и фон в окне наблюдения должны быть представлены существенными по размеру участками.
Для рассматриваемой модели наблюдений с учетом введенных ограничений сформулирована задача обнаружения ЛН (границы фон/объект) как задача выбора из двух альтернативных гипотез: Я, - в локальном окне наблюдения присутствует перепад яркости; Я0 - перепад яркости отсутствует (наблюдается относительно однородный участок изображения). Все параметры модели «идеального» перепада образуют вектор А = (u,h,d,a)T е Л , где Л - множество допустимых значений А , а состояние системы задается параметром в . При гипотезе Я,: в = б,, параметр А = А, удовлетворяет ограничениям |й|> hp и \d\<dp и принадлежит множеству Л'<^Л, при гипотезе
Я0: в = в0, параметр А = А0 принадлежит множеству Л° = Л \ Л1. При этом задача совместного различия гипотез и оценки параметров определяется как задача оценки coll г II7"
ставного вектора у = Ю, Л0 по наблюдению z(x,y). В дальнейшем при синтезе алгоритмов обработки информации рассматриваются различные варианты задания априорной информации:
- изображения с известной яркостью фона (и = а ) и объектов (u + h = b), Л = {а}х {ft-а} X[-£>;£)]*[0;2гг), Л1 = {а} х {b-а}х [~dp,dp] х[0;2л) ;
- изображения с известной яркостью фона (и - а) и неизвестной - объектов,
Л = {а} х [-a; Um - о] х [-Д £>] х [0; 2 л") , Л1 = {а} х ([-a\Um - a],\h\ > hp) x[-dp\dp] х[0;2лг) ;
- изображения с неизвестной яркостью фона и яркостью объектов,
л = i0-,UmM-u;Um-uM-D;DM<yt2^),^ = [0\UJ^{[-u-Um-u},\h\>hp)x[^dp.dp}x[(i-2n).
Решение о выборе гипотезы выносится на основе сравнения логарифма функционала отношения правдоподобия (ФОП) с порогом. При этом неизвестные параметры Я0,Я, определяются с помощью метода максимального правдоподобия. Итоговый алгоритм принятия решения записывается в виде:
1пЛ[я, |Я0] = Д2;Ао,АО 5 с0 , А, = arg inf (ЗДгД) , / = ОД , (2)
L(z;A„,A1) = (G(z,A0)-G(z,A1))/2ct2, G(z,A,) = J(z(x,>>)-S(x,M))2rffi >
a
где a2 - дисперсия шума. Функции G(z,A(), / = 0,1 отражают ошибки представления наблюдаемого участка z(x,y) с использованием модели перепада яркости 5(л,_у,А,-) с параметрами А(.. Т.к. является разрывной функцией, определенной только в
Рис. 2.
локальном участке П , то для поиска минимума функций Л,) внутри областей Л, было применено разложение взвешенных к
(2(х,у) = ехр(-(х2 + у2)/4)/функций г и Я по ор- ......
тонормированному усеченному базису {Ч'} (А.И. Перов, Г.Г.Соколов): = 1, 4>2 = у,
Ч*3 = 0.5[х2 + у2]-1, Ч-4 = 0.5[х2-/], после
которого функция ошибки С представляется в виде
п Р=°
При этом коэффициенты разложения $р , зависящие от и,к,с1 и а , записываются аналитически, а числовые коэффициенты 2р вычисляются по наблюдению г.
На рис. 2 приведен пример аппроксимации «идеального» перепада яркости непрерывной функцией.
Данное представление позволило искать минимум С внутри областей Л0 и Л, на основе получения необходимых условий экстремума путем вычисления первых частных производных указанной функции относительно неизвестных параметров и приравнивания их к нулю. При этом глобальный минимум б выбирается среди всех локальных экстремумов внутри областей Л,-, г = 0,1 и экстремумов на границе областей Л0 и Л, . Рассмотрены способы нахождения минимума для всех приведенных выше случаев априорной неопределенности относительно параметров модели ЛН (1). В случае, например, наличия полной неопределенности о параметрах модели «идеального» перепада яркости для поиска локальных экстремумов внутри Л,-, г = 0,1 аналитическими и численными методами решаются нелинейные уравнения, получаемые после приравнивания к нулю частных производных функции й по неизвестным параметрам, а для поиска на границе областей - аналогичным способом ищутся экстремумы при Ь = к и й = с1р . Далее для принятия решения о наличии ЛН полученные оценки До е Л0 и Л, подставляются в логарифм ФОП (2) для сравнения с порогом с0 .
Исследование квазиправдоподобных алгоритмов обнаружения ЛН производилось для различных вариантов задания априорной информации методом статистического моделирования. Полученные результаты свидетельствуют о том, что оценки параметров угла, уровня перепада яркости и яркости фона являются несмещенными, а оценка параметра расстояния смещена от истинного значения порядка 2-3% от размера окна наблюдения. Среднеквадратичное отклонение (СКО) при оценивании угла ориентации, уровня перепада яркости и яркости фона при ОСШ (определяемого как отношение Щ к а) больше 2 находятся в пределах 5-10% от своих максимальных
значений. Однако СКО оценивания расстояния перепада яркости от центра окна наблюдения уже при средних ОСШ (от 2 до 4) находится в диапазоне от 10% до 15% от своего максимального значения. Наличие смещения и увеличение СКО оценки расстояния обусловлены неточностями непрерывной аппроксимации «идеального» перепада яркости.
Как альтернативный вариант в работе предложен и исследован нейросетевой алгоритм (НСА) совместного обнаружения и оценки параметров ЛИ в рамках модели «идеального» перепада яркости. Нейронная сеть (НС) синтезирована на основе архитектуры двухслойного персептрона. На вход НС подается, развернутое в вектор изображение локального участка наблюдения, размером N х N пикселей. На выходе НС должен формироваться составной вектор параметров у , т.е. номер выбираемой гипотезы 0е{О;1} и основные параметры модели для данной гипотезы вектор Лд = (н,7г,с1,а)т. Для проведения процедуры обучения формировалось множество обучающих примеров - данных, принадлежащих областям значений Л0 и Л,, путем прямого перебора с некоторым шагом так, чтобы охватить все возможные комбинации значений параметров для каждой из гипотез. При обучении добавлялся аддитивный гауссов шум различной интенсивности. Обучение НС было произведено для нескольких стандартных размеров окон наблюдения N = 7,9,11 .
Полученный НСА в ходе модельного эксперимента сравнивался со статистическим алгоритмом (СА). Установлено, что НСА имеет несколько лучшие, нежели СА, показатели качества при больших и умеренных (больше 2) ОСШ (рис. 3). Вероятности ошибок первого и второго рода у НСА на 0.010.03 меньше чем у статистического. СКО определения параметров расстояния, уровня перепада яркости и яркости фона у НСА на 1-3% (от максимального значения соответствующего параметра) меньше, чем у СА. Указанные отличия обусловлены тем, что синтезированный алгоритм является квазиправдоподобным и использует ряд приближений при представлении сигнальной функции, что влечет за собой потерю части информации, по которой принимается решение.
Исследование решений задачи обнаружения и оценивания параметров ЛН различными способами позволило перейти к решению задачи обнаружения объектов, характеризующихся замкнутой границей неизвестной или деформированной формы и наличием различимого перепада яркости на границе, на основе дальнейшей обработки совокупности результатов первичного обнаружения ЛН по всему изображению.
Поэтому в третьей главе основное внимание уделено разработке двухэтапного алгоритма обнаружения объектов, основанного на нахождении замкнутой максимально правдоподобной границы гипотетического объекта. При синтезе данного алгоритма вторичной обработки для выделения целостной границы объектов должны использоваться как конкретные результаты принятия решений в локальных окнах по всему изображению, так и вероятностные характеристики обнаружения отдельных локальных неоднородностей, выделяемых как потенциальные участки целостной границы. С этой целью в главе были первоначально проанализированы безусловные и условные относительно получаемых оценок параметров ЛН вероятности ошибок первого и второго рода.
Для оценки условных вероятностей ошибок еДАоДО = > с0 I Н0,ХаЛ\) и е2(ЯоДО = Р(Ь < с01 ЯрАоДО предложена методика, основанная на полученных в работе выражениях для моментов логарифма ФОП (2) т1. = М[Ь | Я,,АД0Д1],
Рис. 3
сг? = М\]} | Я,.,Я,Яо,Я1]-/я,2, / = 0,1 и оценке их верхних границ путем анализа точечных значений Я в некоторых окрестностях Ф0 и Ф, относительно полученных
значений параметров Ло и Л\ В ходе имитационного моделирования установлено, что апостериорные вероятности ошибок, рассчитываемые по данной методике при больших и умеренных ОСШ (больше 3) отличаются от получаемых экспериментальных значений не более чем на 10-15% в интервале 0..0.1.
Методика расчета безусловных вероятностей ошибок принятия решений <?, = !'(Ь >с0\Нй) и е2 = Р(1 <с0\Н1) основана на численном интегрировании вероятности ошибок по параметрам перепада яркости с равномерным распределением Р(Я | Я() в соответствующих областях значений Л,. Для упрощения расчетов интегрирование по неизвестным оценкам параметров Яо и Х\ заменено на использование фиксированных значений параметров Д^ и Я,", вокруг которых сгруппированы значения Яо , Я] при фиксированном значении Я :
е, « | Р(Ь * с0 I Я,Я0*(Я),Я1*(Я),Я,.)Р(Я I //,)с/Я , / = ол , (3)
леЛ,
где значения Я^ , \ получаются оцениванием параметров Я0, Я, в ходе решения для «идеального» наблюдения без шумового искажения г(х,у) = 5(дг,у,Я).
Кроме того, аналогично оценке верхних границ условных вероятностей ошибок определялись верхние границы безусловных вероятностей ошибок. Проведенное моделирование показало, что безусловные вероятности ошибок, рассчитываемые по данной методике, при больших и средних ОСШ (больше 3) не более чем на 12-17% отличаются от экспериментально получаемых значений в интервале 0..0.1. На рис. 4 показаны графики зависимостей данных ошибок а) - е, и б) - е2, полученные моделированием - М, расчетом по формуле (3) -Фи оцениванием верхних границ - ВГ в зависимости от ОСШ.
а) б)
Рис. 4
Условные относительно полученных оценок параметров ЛН вероятности ошибок целесообразно применять при анализе конкретных окон наблюдения, что позволяет получить более информативные данные для принятия решений по сравнению с безусловными вероятностями ошибок при обнаружении ЛН. Однако такие вероятности необходимо вычислять каждый раз для очередного анализируемого участка изображения, в отличие от безусловных вероятностей ошибок, вычисляемых априорно.
Далее рассматривается непосредственно двухэтапный алгоритм обнаружения объекта на изображении с замкнутой границей неизвестной или деформированной
формы. При этом считается, что возможны две ситуации: 1) на изображении в области Ч'в присутствует объект Ь(х,у), при этом оставшуюся часть области VF занимает фон а(х,у); 2) фон занимает всю область наблюдения, т.е. объект отсутствует. Наблюдаемое изображение представляется в виде
в(х,у) = а(х,у) + у0(Ъ(х,у)-а(х,у))1в(.х,у) + Ы{х,у), (4)
где у0 = 0 , если объекта на изображении отсутствует, у0 = 1, если объект присутствует; 1в(х,у) = 1 при (х,у) е и 1в(х,у) = 0 при (х, у) iyY в - индикаторная функция, описывающая форму объекта; N(x,y) - пространственный белый гауссовский шум. При этом а(х,у) и Ь(х,у) не известны и подразумевается, что на границе объекта и фона имеется различимый перепад яркости (превышающий порог hp). Относительно размеров и формы области заданы минимальное rt и максимальное г2 расстояние относительно геометрического центра фигуры до точек, находящихся на ее границе.
С учетом высокой степени априорной неопределенности при решении задачи в рассматриваемой постановке предложено сначала разбивать изображение на локальные участки наблюдения размером NxN пикселей. После этого каждый такой участок подвергается анализу на предмет наличия или отсутствия J1H с использованием статистического или нейросетевого алгоритмов, рассмотренных во второй главе диссертации. Наблюдения, которые получены после первичной обработки (рис. 5), представляются в виде матриц & = {/,}} и Ep={PiJ], Eq = {q^}, где для участка (i,j),(\<i<K, 1 <j<M): ftj -индекс в принятой гипотезы, - вероятность ошибки первого рода (е,), qtJ - второго рода (е2).
При синтезе алгоритма обнаружения объекта на множество допустимых границ Q = {Г\, /'= {(а,,/>,)), 1 </'< пг, задающихся также матрицами G = {g^}, где g:j= О,
если граница принадлежит участку (i,j) и gi;. =1, в противном случае, накладываются следующие ограничения:
|а,-ак\< 1, \Ь, -Ьк\ < 1 и П < ^-kf+^-hf * г2, где £ = г' + 1,если i<nr и к = 1, если i = nr, (i0,j0) - выбранный некоторым образом центр объекта. Задача обнаружения решается как задача обнаружения объекта, характеризующегося замкнутой границей неизвестной или деформированной формы с различимым перепадом яркости на границе r^Q и формулируется как задача выбора из двух альтернативных гипотез: Н, - в области наблюдения присутствует объект с контуром Г ; Н0 - объект отсутствует и, следовательно, все обнаруженные перепады яркости в локальных окнах наблюдения, являются следствием воздействия шума. Решение в пользу одной из гипотез принимается на основе сравнения логарифма ФОП с порогом:
^i.o • Д-О = In А[Я, | Я0] > с0,гдеЛ[Я||Я0] = Р(Ф|Я1>Г)/Р(Ф|Я0)
N1
/ \
/
Так как истинное местоположение и форма границы Г при выборе гипотез неизвестны, то производится максимизация логарифма ФОП Г = arg sup In Р(Ф | ff,, Г).
Гев
После подстановки выражения /'(Ф | НХ,Г) и упрощения получен итоговый алгоритм:
к м
Я, 0 : КГ) * с0 , Г = arg inf 5(Г), 5(Г) = YLl4 > (5)
r<Eß 7=1
Задача (5) минимизации 5(Г) - NP-полная и требует перебора всех допустимых вариантов Г eQ . Для повышения быстродействия обработки рассмотрен случай объектов, форма границы которых описывается однозначной функцией в полярных координатах г = г(<р), <р g [0,2тт], r(fi) = г(2л) относительно центра объекта. В этом случае
участки наблюдения разбиваются на группы Sk = {(hm,jkm)}, m = \,Nk , k = \,F с одинаковым угловым положением <рк относительно вертикальной оси, где к - номер группы локальных участков Sk, m - внутренний индекс внутри каждой группы. При этом фактически происходит переход нумерации участков от индексов (i,j) к индексам (k,m) = 0tm,jkm) ■ Для рассматриваемого подмножества границ справедливо, что каждый следующий локальный участок при обходе по часовой стрелке имеет большую угловую координату, чем предыдущий. Фиксируя центр объекта участок (ig,j0) и верхний участок контура (ig,j]), j\ < j0, синтезируется граф G = G(i0,j0,j\) = (V,A) допустимых переходов по часовой стрелке участков границы с учетом ограничений на множество контуров Q и начальной и конечной вершиной в участке (i0,y,). Пример такого графа (верхней его части) при отсутствии ограничений на размер объекта (г, = 0, г2 = со) представлен на рис. 6. Для связи, идущей из вершины входящей в группу участков с номером к,, в вершину (х2,у2), входящей в группу участков с номером к2 определяется вес связи v в виде:
= VY =JVU,>1 =[к2,к2>\ = jl,(Wb,)6{(*i^).(W2)}.
"~кh "tu, =1 ' W2 = \F.k2 = 1 ' gi"' " Wwb,)*
Любой путь на построенном графе из начальной в конечную вершину соответствует одной из возможных границ, проходящих через участок (/0, у,), и наоборот. С учетом введенных весов связей сумма S(T) для каждого контура совпадает с суммой весов соответствующего пути графа.
Таким образом, задача минимизации 5(Г) с фиксированными /0,yn, jt в (5) сведена к задаче поиска минимального по сумме весов пути на построенном графе G, которая решается с помощью алгоритма Дейкстры, реализующего метод динамического программирования. На основе перебора индексов г0, j0 и у,, выбирается минимум 5(Г) на всем множестве Q. Далее аналогичным алгоритмом синтезируется попик-сельная граница объекта.
t bis T 1
к t .L *t 4 т »i У[
к t» .к .V к* «ч!*К ?т
V sk \I 'Wo J • • •
Рис. 6
Проведенные эксперименты по обнаружению объектов в присутствии аддитивного шума показали, что при уровне ОСШ более 2 вероятности ошибок первого и второго рода для типовых условий имеют значения менее 0.01. Особенностью разработанного алгоритма является возможность коррекции результатов первичной обработки. Применение синтезированного двухэтапного алгоритма для обработки реальных изображений (изображения кровяных телец и др.) в присутствии шума показало его работоспособность как в случае решения задачи обнаружении одиночного объекта при различных уровнях шума (рис. 7), так и для задачи обнаружения множества однотипных объектов с границей, подвергающейся деформирующим искажениям (рис.8). При обнаружении множества объектов для дальнейшего анализа предварительно эвристически выбираются участки с максимальным количеством обнаруженных перепадов яркости, где потенциально могут находиться объекты.
9 30'О
Рис. 7
Рис. 8
Синтезированные алгоритмы контурного анализа объектов на изображениях могут применяться также в сочетании с другими, в том числе и эвристическими, алгоритмами обнаружения объектов.
Такие алгоритмы рассмотрены в четвертой главе работы, где проводится синтез и анализ алгоритмов обнаружения и классификации множества однородных объектов на основе эталонного описания, реализующего известную идею разбиения изображения на группы пикселей при упорядочивании их по яркости (И.В.Терентьев). В более общем случае при описании изображения объекта S(x,y), заданного на множестве пикселей П , производится разбиение всех N пикселей изображения на группы по некоторому базовому индексирующему признаку (яркости, цветности и т.д.). В этом случае S(x,y) при разбиении изображения на п непересекающихся групп пикселей, содержащих по /)75 пикселей, можно представить в виде
Л A fl, (х,у)е О,
где Iа(х,у) - индикаторная функция на множестве пикселей, соответствующей s -ой группе tis = {{х,,уХ j = 1 ,ms). На рис. 9 представлен пример графической интерпретации функций трех групп Is(x,y) для изображения «самолет».
Для описания эталонного образа предложено использовать гистограммы распределения различных характеристик пикселей в выделенных группах. В частности, в реализованном в диссертации алгоритме анализируются гистограммы яркости Gt, гистограммы расстояний от центра кадра до пикселей Нs и гистограммы углового положения пикселей Fs. Для дальнейшего обнаружения объектов различного размера данные гистограммы строятся на оси относительных значений величин. На основе гистограммы Fs путем циклического сдвига получается матрица £s =(F0s|Fb|...|Fij) угловых положений пикселей, что обеспечивает инвариантность описания к повороту объ-
екта. Полученные характеристики ,Н3,Е3, $ = 1 ,п служат инвариантным к повороту, масштабированию и сдвигу описанием эталонного объекта (фрагмента).
Для сравнения двух образов 5 и 5', заданных своими гистограммами , Н5 ,Е! и в[,Н'5>Е[
вычисляются меры близости Яа , , по каждому из рассматриваемых свойств пикселей. При этом имеется возможность применять различные формулы и меры близости для сравнения векторов-гистограмм, такие как, косинус угла, меру Танимото и т.д. Для вычисления меры ^ происходит перебор всех угловых положений эталона в соответствии с матрицами Е,.. Для итоговой меры близости
двух образов рассматривается ее общий вид Л =/(Лс,Ля,й''), где / некоторая положительно определенная функция, не убывающая по каждому из компонентов. В простейшем случае в качестве / берется среднее геометрическое компонентов. Однако,
могут быть полезны и другие функции, например, /-Лн, / = й'г, / = Я1' . В
частности, применение / =л!ян Я17 позволяет производить сравнение образов лишь по геометрической форме выделенных групп, не учитывая яркость пикселей, достигая при этом лучшего обнаружения однотипных объектов различной освещенности.
Для принятия решения о наличии объекта применяется пороговое правило. Непосредственные значения порогов подбираются исходя из требуемой максимально допустимой частоты пропуска объекта р . В случае решения задачи классификации объектов решение принимается в пользу объекта с максимальной мерой близости локального участка и соответствующего эталона.
Для улучшения качества обнаружения объектов предложена методика определения оптимального количества п используемых для разбиения групп и пикселей т[ в них. Вводится мера близости двух образов одинакового размера и ориентации, основанная на степени взаимного пересечения групп образов. Образы групп представляют собой матрицы = Ци^Ц, гдеи'5.н=1, если пиксель (А,/) принадлежит я -й
группе и = 0 - в противном случае. При этом степень пересечения $ -й группы
м м
эталона и локального участка наблюдения равна р5 = / т3, где ул. = ■ .
к=\1=1
Общая мера близости Я двух образов определяется как среднее арифметическое или среднее геометрическое значений р3 и отображает общую степень похожести групп
двух образов. Для изображения эталонного образа 5 , состоящего из N пикселей, и М вспомогательных образов } данного объекта введен К = К(п; т^в =1,и) - показатель неизменяемости групп вспомогательного набора образов {5;} относительно эталонного образа 5 , определяемый как среднее геометрическое значений мер близости образов и 5 , и предложено правило выбора значений п и т'3:
(п', = 1,и}) = аг% шах_ К{п\ = 1,и), п - 2,ягаах , (7)
п, ¡^.,л=|/;|
которое ориентировано на минимизацию вероятности пропуска вспомогательных образов 5, при обнаружении по эталону S .
На основе описанного подхода был разработан программный комплекс, реализующий алгоритмы обнаружения/классификации и локализации объектов на изображении. При выполнении обработки изображение сканируется небольшим окном наблюдения и рассчитывается функция близости R(x,y) локальных участков и эталонов. Для определения точного местоположения объектов с учетом их взаимного расположения реализуется процедура последовательного поиска. При этом каждый раз выбирается текущий глобальный максимум R(x,у), превышающий порог обнаружения, в тех позициях, которые находятся на расстоянии, большем чем г от объектов, найденных на более ранних этапах. В зависимости от взаимного расположения объектов применяется формула г" = Я-г , где г - радиус эталонного образа.
После обнаружения объектов возможно выделение их границ по алгоритмам, описанным во второй и третьей главах диссертации. На рис. 10 в качестве примера представлены результаты анализа изображений объектов микробиологии. В ходе тестирования предложенного алгоритма для различных типов реальных изображений установлено, что вероятность правильного распознавания объектов составила в среднем порядка 0.96-0.98 в зависимости от качества исходных изображений, по сравнению с алгоритмами корреляционно-экстремального анализа, для которых вероятность правильного распознавания в тех же условиях составила 0.81-0.87.
В заключении сделаны выводы и сформулированы основные результаты диссертационного исследования, которые сводятся к следующему.
1. Сформулирована общая постановка, синтезированы и проанализированы квазиправдоподобный статистический и нейросетевой алгоритмы совместного обнаружения и оценивания параметров локальных неоднородностей, удовлетворяющих введенным ограничениям в рамках модели «идеального» перепада яркости, при различном уровне априорной неопределенности относительно параметров модели.
2. Предложены методики оценки безусловных и условных относительно полученных оценок параметров вероятностных характеристик квазиправдоподобных алгоритмов обнаружения перепада яркости в локальном окне наблюдения, позволяющие, в том числе, использовать данные показатели качества для синтеза алгоритма обнаружения объектов, характеризующихся целостной границей объекта.
3. Синтезирован и исследован двухэтапный алгоритм совместного обнаружения и локализации объектов, основанный на первичном обнаружении совокупности локальных неоднородностей на изображении и выделении замкнутой границы случайной формы по результатам вторичной обработки с использованием метода динамического программирования.
4. Предложены и исследованы алгоритмы обнаружения и классификации объектов, основанные на применении индексирующего разбиения сравниваемых кадров эталонного и наблюдаемого изображения по группам яркости и использовании обобщенного гистограммного описания эталонного изображения объекта, инвариантного к сдвигу, повороту и масштабированию.
Основные результаты диссертации опубликованы в работах:
1. Сирота, A.A. Обнаружение и оценка параметров перепада яркости в задаче контурного анализа объектов / A.A. Сирота, А.И. Соломатин // Автометрия. - 2009. - Т.45. -№5. - С.59-69.
2. Сирота, A.A. Двухэтапный алгоритм обнаружения и оценивания границы объектов на изображениях в условиях аддитивных помех и деформирующих искажений / A.A. Сирота, В.В. Воронова, А.И. Соломатин // Компьютерная оптика. - 2010. - Т.34. -№1,-С. 109-117.
3. Сирота, А.А Поиск множества объектов на основе инвариантных преобразований эталонных фрагментов изображения / А. А Сирота, А.И. Соломатин // Информационно-измерительные и управляющие системы. - 2010. - Т.8. - №6. - С.8-15.
4. Сирота, А. А Статистические алгоритмы обнаружения границ объектов на изображениях / АА. Сирота, А.И. Соломатин // Вестник Воронежского государственного университета, серия: Системный анализ и информационные технологии. - 2008. - №1. -С.58-64.
5. Сирота, АА. Алгоритм совместного обнаружения и оценивания границы объектов на изображениях в условиях аддитивных помех / А.А Сирота, А.И. Соломатин // Сборник докладов XVI международной научно-технической конференции «Радиолокация, навигация, связь». - Воронеж, 2010.-Т.1. - С. 172-183.
6. Сирота, АА. Статистический и нейросетевой алгоритмы обнаружения и оценки параметров перепада яркости в задаче выделения контура объекта / A.A. Сирота, А.И. Соломатин // Материалы шестой международной научно-методической конференции «Информатика: проблемы, методология, технологии». - Воронеж, 2008. - Т.2. - С.251-257.
7. Сирота, АА. Алгоритмы формирования непрерывной границы объектов при решении задач контурной обработки изображений / A.A. Сирога, А.И. Соломатин // Материалы пятой международной научно-методической конференции «Информатика: проблемы, методология, технологии». - Воронеж, 2007. - С.375-379.
8. Сирога, АА. Статистические алгоритмы контурного анализа изображений в условиях шумов / АА Сирота, А.И. Соломатин // Материалы пятой международной научно-методической конференции «Информатика: проблемы, методология, технологии». -Воронеж, 2007. - С.379-382.
9. Сирота, A.A. Сравнительный анализ алгоритмов выделения границы случайных полей при обработке изображений / А.А Сирота, А.И. Соломатин // Сборник докладов VII Международной научно-технической конференции "Кибернетика и высокие технологии XXI века". - Воронеж, 2006. - Т.2. - С.554-561.
10. Сирота, A.A. Определение границы раздела случайных полей при обработке изображений с использованием метода динамического программирования / A.A. Сирота, А.И. Соломатин // Материалы четвертой международной научно-методической конференции «Информатика: проблемы, методология, технологии». - Воронеж, 2006. - С.412-418.
Работы № 1, 2,3 опубликованы в изданиях, рекомендованных ВАК РФ.
Подписано в печать 25.04.11. Формат 60*84 '/|6. Усл. печ. л. 0,93.
Тираж 80 экз. Заказ 537.
Отпечатано с готового оригинал-макета в типографии Издзтельско-полиграфического центра Воронежского государственного университета.
394000, Воронеж, ул. Пушкинская, 3
Оглавление автор диссертации — кандидата физико-математических наук Соломатин, Алексей Иванович
Введение.
Глава 1. Анализ известных методов обнаружения и выделения границ объектов на изображениях.
1.1. Анализ известных методов и алгоритмов поиска объектов на изображениях.
1.1.2. Статистический подход к распознаванию объектов на изображениях.
1.1.3. Геометрический подход к распознаванию объектов на изображениях.
1.1.4. Нейросетевой подход к распознаванию объектов на изображениях.
1.2. Известные методы выделения границ объектов на изображениях.
Выводы по главе.
Глава 2. Синтез и анализ алгоритмов совместного обнаружения и оценивания локальных участков границы объектов на изображении.
2.1. Постановка задачи совместного обнаружения и оценивания параметров локальной неоднородности в рамках модели перепада яркости.
2.2. Статистические алгоритмы обнаружения и оценивания параметров локальной неоднородности в рамках модели перепада яркости.
2.2.1. Алгоритм обнаружения перепада яркости при известной яркости фона и яркости объектов.
2.2.2. Алгоритм обнаружения и оценки параметров перепада яркости при известной яркости фона и неизвестной яркости объектов.
2.2.3. Алгоритм обнаружения и оценки параметров перепада яркости при неизвестной яркости фона и неизвестной яркости объектов.
2.3. Нейросетевой алгоритм совместного обнаружения и оценивания параметров локальной неоднородности в рамках модели перепада яркости. 79 Выводы по главе.
Глава 3. Синтез и анализ алгоритмов совместного обнаружения и оценивания границы объектов с неизвестной формой и местоположением
3.1. Методика оценки эффективности алгоритма обнаружения локальной неоднородности.
3.1.1. Методика расчета условных вероятностей ошибок первого и второго рода
3.1.2. Методика расчета безусловных вероятностей ошибок первого и второго рода.
3.2. Синтез алгоритма вторичной обработки локальных фрагментов для обнаружения объекта, характпризующегося замкнутой границей неизвестной формы.
3.3. Определение целостной границы объекта с использованием метода динамического программирования при реализации обобщенного алгоритма максимального правдоподобия.
Выводы по главе.
Глава 4. Алгоритмы обнаружения объектов на основе инвариантных преобразований эталонных фрагментов изображения.
4.1. Инвариантный к повороту и изменению масштаба алгоритм обнаружения эталонного объекта в локальном участке наблюдения.
4.1.1. Представление изображений объектов с использованием упорядоченного разбиения на группы пикселей.
4.1.2. Формирование описания эталонного объекта, инвариантного к повороту и изменению масштаба.
4.1.3. Определение меры близости наблюдаемого и эталонного изображения. Принятие решения о наличии объекта.
4.1.4. Определение меры близости локального участка изображения и эталона на основе вычисления степени пересечения выделенных групп
4.2. Алгоритмы классификации и локализации объектов на изображении. 147 Выводы по главе.
Введение 2011 год, диссертация по информатике, вычислительной технике и управлению, Соломатин, Алексей Иванович
В настоящее время постоянно совершенствуются технические и информационные возможности различных систем дистанционного мониторинга и видеонаблюдения. Это, в свою очередь, стимулирует потребность в развитии существующих и разработке новых методов и средств автоматической и автоматизированной обработки получаемых исходных графических материалов. Соответствующие задачи постоянно возникают [25,76,80,99] в системах наведения и навигации летательных аппаратов, в самолетных, спутниковых и других системах визуального контроля объектов, в системах экологического мониторинга земной поверхности, в разнообразных устройствах медицинской и технической диагностики и др. К наиболее часто решаемым задачам относятся, например, задачи оцифровки изображений, хранения, передачи и сжатия полученных цифровых эквивалентов, задача фильтрация шумов и т.д. Тем не менее, основной в таких системах является, все-таки, задача автоматического извлечения необходимой для принятия дальнейших решений информации. В самом общем понимании - это задача анализа наблюдаемой сцены [86], т.е. разбор изображения на составные части и интерпретация его по аналогии с тем, как это делает человек [70]. Однако, при отсутствии каких либо априорных данных об анализируемых изображениях, подобная задача сегодня не имеет законченного решения.
В связи с этим на практике рассматриваются [26,35,37,50,54,69,93,105] более частные задачи понимания изображений, ориентированные на извлечение в некотором смысле заранее оговоренной и структурно фиксированной информации из изображений одинаковой и известной природы. Большинство систем, осуществляющих автоматическое извлечение такой информации из изображения, используют для этого методы классификации объектов или их частей с последующей локализацией области их расположения [25,81,86]. Следует отметить, что решаемые при этом задачи также являются плохо формализуемыми и не имеют единых подходов в своем решении.
Проблемами интеллектуального анализа изображений ученые занимаются достаточно давно - с момента появления самих цифровых изображений. В разные годы теоретическими и практическими разработками в области обработки изображений и в частности обнаружения и классификации пространственно локализованных объектов и их частей занимались П.А. Бакут, Р. Брунелли (R. Bruneiii), В.Н. Вапник, Р. Вудс (R. Woods), Р. Гонсалес (R. Gonzalez),
A.JI. Горелик, Р. Дуда (R. Duda), B.K. Злобин, H.Л. Казанский, А.И. Перов, У. Прэтт (W. Pratt), B.B. Сергеев, В.А. Скрипкин, В.А. Сойфер, Ю.Г. Сосулин, И.В. Терентьев, А.П. Трифонов, К. Фукунага (К. Fukunaga), Я.А. Фурман, П. Харт (Р. Hart), M. Хюккель (M. Hueckel), Ш.-К. Чэн (C.K. Chan), А .Я. Червоненкис,
B.М. Чернов, Л.П. Ярославский и др. В настоящее время с каждым годом растет число разработок и публикаций, посвященных анализу изображений.
Одной из стандартных задач обработки цифровых изображений, полученных в различных спектральных областях оптического диапазона длин волн пассивными средствами наблюдения, является задача поиска — обнаружения, локализации и идентификации (распознавания) однородных объектов в присутствии шумов по эталонному образцу или фрагменту, содержащему дешифрирующие признаки. При этом в подобных системах, как правило, используется принцип просмотра изображения скользящим окном заданного размера и анализ локального участка изображения на предмет наличия в нем интересующего объекта [25]. В ходе такого просмотра осуществляется принятие решения о наличии или отсутствии объекта в анализируемом локальном участке изображения. В зависимости от специфики решаемой задачи изображения объектов могут в той или иной мере отличаться от эталонного варианта. Эти отличия могут быть вызваны шумами, незначительными искажениями формы объекта, наличием в непосредственной близости к объекту других объектов, изменением пространственной ориентацией объекта в сравнении с эталоном и другими причинами. Известны различные подходы, применяющие для решения указанной задачи ту или иную меру близости изображений в окне наблюдения и эталонного образца. Например, в [61,81] описаны алгоритмы, использующие
разделяющие функции на пространстве признаков, функции расстояния между образами, методы кластерного анализа, байесовский классификатор, обучаемые классификаторы на основе персептронного подхода. В зависимости от априорных данных о распознаваемых объектах полезными оказываются те или иные методы.
Учитывая, что при работе пассивных оптико-электронных средств наблюдения имеется минимальное количество априорной информации, а также требование реализации решающих правил, инвариантных к повороту и сдвигу объектов на анализируемых изображениях, применение большинства классических алгоритмов поиска, например алгоритмов корреляционно-экстремального анализа в их традиционной форме, не представляется возможным и требуется разработка новых подходов для решения указанной задачи. При этом необходимо рассмотреть две ситуации, в соответствии с которыми далее в диссертации рассматривается два подхода к построению алгоритмов обработки изображений:
- эталонные описания объектов отсутствуют, и задача поиска ставится как задача обнаружения и идентификация неоднородностей, т.е. яркостных «всплесков», относительно которых могут быть известны только примерные размеры и относительный уровень перепада яркости;
- имеется возможность получения эталонного описания объекта или его фрагментов при наблюдении в присутствии характерного фона, содержащие дешифрирующие признаки в интересах последующего решения основной задачи поиска.
Анализ существующих работ [25,61,81,86] также показал, что для обнаружения пространственно локализованных объектов в указанной постановке применяются статистические, эвристические и нейросетевые подходы. К сожалению, общим недостатком, большинства методов является их далеко не универсальный характер. Поэтому на практике в каждом конкретном случае разработчикам приходится применять индивидуальные методы и подходы (выбираемые из числа существующих или разрабатываемые каждый раз заново) с целью наиболее точного учета особенностей задачи, т.е. фактически, использовать имеющуюся априорную информацию об обрабатываемых изображениях. В качестве такой информации [69,85,96,101] может выступать информация о яркости объектов, их форме, размерах и т.д. С другой стороны в случае минимума априорной информации об обнаруживаемых объектах существующие методы зачастую неэффективны, т.к. нет возможности обеспечить настройку параметров их функционирования.
Другим недостатком имеющихся решений является раздельный характер процесса обнаружения объекта и определения границ его локализации. В случае, когда совместно с обнаружением решается задача локализации, то ограничиваются лишь определением координат объекта. При этом границы объектов определяются с помощью отдельных методов и алгоритмов, часто никак не связанных с обнаружением самих объектов. Однако, как отмечается в работе [63], чем контрастнее участок изображения на границе объекта, тем более точно происходит определение координат при его обнаружении. Таким образом, представляет интерес разработка методов обнаружения пространственно локализованных объектов, на основе обнаружения их границ, т.е. методов совместного обнаружения и локализации.
Как отмечается в [37], отличительной чертой областей локализации большого числа объектов является специфическая для данных объектов яркостно-цветовая картина, существенно отличающаяся от фона. При этом возможны различные варианты.
Наиболее распространенным является вариант наличия яркостного перепада на границе объекта и фона. В этом случае объект имеет отличную от фона относительно однородную по уровню яркость. При неизвестной формы границы объекта, его яркости и яркости фона именно по наличию различимого перепада яркости вдоль границы локализации объекта можно судить о его наличии на изображении. Таким образом, в условиях неопределенности о параметрах обнаруживаемых объектов и наличия аддитивного шума перспективным видится подход к обнаружению объектов как локальных неоднородностей на основе обнаружения перепадов яркости вдоль замкнутой границы объекта. При этом существуют различные методы обнаружения перепадов яркости [24,25,34,73,75,89,92,106]. Наиболее удобными и устойчивыми к шумам являются, на наш взгляд, статистические методы и алгоритмы (М. Хюккель, А.И. Перов, Г.Г. Соколов) [34,89], основанные на аппроксимации локального участка на границе объекта моделью «идеального» перепада яркости. Однако в указанных работах параметры перепада яркости в окне наблюдения определяются лишь в случае наличия объекта; при этом задача совместного обнаружения и оценивания параметров перепада яркости в них не решается. Соответственно, в известной автору литературе не проводился анализ показателей качества алгоритмов, основанных на данной модели, что в свою очередь необходимо для последующего синтеза алгоритмов обнаружения объектов с целостной замкнутой границей случайной формы в ходе вторичной обработки результатов обнаружения отдельных перепадов яркости (локальных неоднородностей) на всем изображении. Отдельный интерес представляет разработка и исследование нейросетевых моделей и алгоритмов совместного обнаружения и оценивания параметров локальных неоднородностей, представляемых, в том числе, моделью перепада яркости.
Отметим, что во многих случаях обнаруживаемые объекты и, в большей степени, отдельные фрагменты этих объектов, не характеризуются замкнутой границей, вдоль которой наблюдается ярко выраженный перепад яркости, а внутри присутствует относительно однородная поверхность. Существуют объекты, которые отличаются существенно неоднородной текстурой. В таком случае рассматривать замкнутую границу, отделяющую объект одной яркости от фона с другой яркостью, весьма затруднительно. Отличительным признаком для поиска таких объектов является характерное взаимное расположение и форма участков примерно одинаковой яркости - яркостных пятен. Для указанной ситуации представляет интерес синтез и исследование алгоритмов обнаружения объектов на основе априорной информации, определяемой наличием эталонного образа, о взаимном расположении участков (пятен) с одинаковой и различной яркостью, позволяющей отличать изображения объектов от общего фона. Данный подход был впервые реализован в работе И.В. Терентьева [51], где для описания элементов изображения в интересах классификации предложено использовать индексирующее разбиение изображения по группам яркости, а для сравнения образов с эталонами анализируются гистограммы яркости основных и дополнительных изображений. Однако в предложенном методе возможно использовать лишь два свойства пикселей - яркость и расстояние пикселей от центра кадра, а для принятия решения - разработанный авторами весьма специфический алгоритм многоальтернативного дискретного накопления, основанный на подсчете голосов в пользу того или иного объекта. В целом, данный подход к представлению изображений видится весьма перспективным для решения задач обнаружения и классификации пространственно локализованных объектов. В тоже время он является недостаточно исследованным в части обобщенного описания изображений на основе разбиения пикселей на группы по некоторому базовому индексирующему множеству (яркости, цветности и т.д.), оптимального выбора количества групп и пикселей в них, а также использования различных свойств пикселей в выделяемых группах и различных мер близости двух образов. Кроме того, в [51] рассматривается лишь задача классификации объектов, в то время как задачи обнаружения и локализации, являясь важной частью задачи поиска пространственно локализованных объектов на изображении, не рассмотрены.
Таким образом, тема диссертации, посвященная синтезу и анализу алгоритмов компьютерной обработки изображений в интересах обнаружения и оценивания границ пространственно локализованных объектов при различном уровне априорной неопределенности, представляется актуальной.
Тема входит в план научно-исследовательских работ ВГУ по кафедре информационных систем и непосредственно связана с научным направлением Воронежского государственного университета «Математическое моделирование, программное и информационное обеспечение, методы вычислительной и прикладной математики и их применение к фундаментальным и прикладным исследованиям в естественных науках».
Тема диссертация соответствует специальности 05.13.01 - «Системный анализ, управление и обработка информации» (п.п. 4,5,10,12 паспорта специальности).
Объектом исследования выступают информационно-измерительные системы и процессы, предназначенные для обнаружения, классификации и локализация объектов на цифровых изображениях.
Предметом исследования является математическое и алгоритмическое обеспечение для обнаружения, классификации и локализации объектов на изображениях, базирующееся на использовании статистических, нейросетевых и эвристических методов обработки информации.
Целью работы является синтез и анализ статистических, нейросетевых и эвристических алгоритмов обнаружения и оценивания параметров локальных неоднородностей (ЛН), а также обнаружения целостных объектов с замкнутыми границами неизвестной или деформированной формы в интересах создания эффективных средств компьютерной обработки цифровых изображений
Для достижения цели в работе рассматриваются и решаются следующие задачи.
1. Анализ известных методов обнаружения, классификации и локализации пространственно распределенных объектов и их частей, а также методов контурного анализа изображений.
2. Синтез и анализ статистических и нейросетевых алгоритмов совместного обнаружения и оценивания параметров локальных неоднородностей, представляемых моделью «идеального» перепада яркости, для различных уровней априорной неопределенности.
3. Синтез и анализ двухэтапного алгоритма совместного обнаружения и локализации объектов на основе выделения целостной замкнутой границы случайной формы по результатам вторичной обработки выделенных в ходе первичной обработки изображения локальных неоднородностей.
4. Исследование инвариантных к сдвигу и повороту алгоритмов обнаружения, классификации и локализации объектов и их фрагментов на цифровых изображениях, основанных на применении индексирующего разбиения кадров эталонного и наблюдаемого изображения по группам яркости.
Методы проведения исследования. При решении поставленных в диссертации задач использовались аналитические и вычислительные методы современной теории информационных процессов и систем, а именно: методы теории принятия статистических решений; методы теории вероятностей и математической статистики; методы теории графов; методы статистического имитационного моделирования, а также аппарат искусственных нейронных сетей.
Основные результаты, выносимые на защиту, и их научная новизна. На защиту выносятся следующие результаты, впервые достаточно подробно развитые или полученные в настоящей работе:
1. Квазиправдоподобные и нейросетевой алгоритмы совместного обнаружения и оценивания параметров существенных локальных неоднородностей, представляемых в виде перепада яркости, обеспечивающие возможность использования различного объема априорной информации относительно уровней яркости фона и объекта, а также параметров расположения перепада.
2. Методики оценки безусловных и условных относительно полученных оценок параметров вероятностных характеристик обнаружения перепада яркости в локальном окне наблюдения, результаты численных расчетов и статистического моделирования показателей качества обнаружения для типовых условий наблюдения.
3. Двухэтапный алгоритм обнаружения объектов на изображениях, основанный на реализации вторичной обработки выделенной в ходе первичной обработки совокупности локальных неоднородностей и нахождении замкнутой максимально правдоподобной границы гипотетического объекта с использованием метода динамического программирования, что позволяет оптимизировать решение задачи обнаружения в условиях аддитивных помех и деформирующих искажений формы границ, а также ограничений по времени решения задачи.
4. Алгоритмы обнаружения и классификации множества однородных объектов, основанные на использовании инвариантных к сдвигу и повороту гистограммных описаний яркости и угловых координат элементов изображений, полученных при применении индексирующего разбиения кадров эталонного и наблюдаемого изображения по группам яркости, и обеспечивающий оперативный поиск объектов по информативным фрагментам в сочетании с характерным для них примыкающим фоном.
Научная новизна полученных результатов работы определяется следующим.
1. Рассмотрена задача совместного обнаружения и оценивания параметров существенной ЛН в элементарном окне наблюдения, описываемой в рамках модели «идеального» перепада яркости, наблюдаемого в присутствии аддитивного гауссовского шума. Получена структура оптимального алгоритма обнаружения и оценивания параметров перепада яркости, основанного на применении обобщенного метода правдоподобия при выборе статистических гипотез. Получены и проанализированы квазиправдоподобные алгоритмы обнаружения и оценивания параметров перепада яркости для различной априорной информации относительно яркости фона и объекта. Впервые предложена реализация нейросетевого алгоритма совместного обнаружения и оценивания параметров ЛН.
2. Предложена методика определения условных относительно полученных оценок параметров ЛН вероятностей ошибок первого и второго рода для каждого конкретного анализируемого локального участка изображения, основанная на полученных выражениях для моментов логарифма отношения правдоподобия при использовании модели обнаружения «идеального» перепада яркости в присутствии аддитивного гауссовского шума. Предложена методика расчета безусловных вероятностей ошибок первого и второго рода, основанная на численном интегрировании условной вероятности ошибок по параметрам перепада яркости.
3. Для объекта, характеризующегося замкнутой границей неизвестной или деформированной формы и наличием различимого перепада яркости на границе, а также диапазоном значений поперечного размера, синтезирован двухэтапный алгоритм обнаружения в присутствии шума, основанный на выделении совокупности локальных перепадов яркости на всем изображении в ходе первичной обработки и применении обобщенного метода максимального правдоподобия при сравнении статистических гипотез о наличии или об отсутствии замкнутой границы перепада яркости в поле всего наблюдаемого изображения в ходе вторичной обработки. Задача нахождения наиболее правдоподобного контура гипотетического объекта сведена к задаче поиска пути минимальной стоимости на графе.
4. Предложенный алгоритм обнаружения и классификации объектов или их фрагментов по эталонным изображениям, основанный на применении индексирующего разбиения сравниваемых кадров эталонного и наблюдаемого изображения на группы по базовому индексирующему признаку (яркость, цветность и т.д.), отличается использованием обобщенного гистограммного описания объектов, инвариантного к сдвигу, повороту и изменению масштаба. Алгоритм позволяет анализировать яркость и положение пикселей в выделенных группах в полярной системе координат и обеспечивает использование различных мер близости при сравнении образов. Предложена методика определения целесообразного количества применяемых при разбиении групп и количества пикселей в них.
Достоверность результатов работы. Результаты исследований, сформулированные в диссертации, получены на основе корректного использования взаимно дополняющих друг друга теоретических и экспериментальных (имитационное моделирование) методов исследований, совпадением результатов, полученных различными методами, между собой, а, в ряде частных случаев, с известными, наглядной физической трактовкой установленных закономерностей и соотношений.
Анализ разработанных статистических, нейросетевых и эвристичеаских алгоритмов обработки изображений проводился как с использованием статистических моделей, так и путем экспериментирования с реальными изображениями. Построенные зависимости верхних оценок для различных показателей качества совместных алгоритмов обнаружения перепада яркости хорошо согласуются с результатами, полученными на основе аналитических соотношений, а также с результатами статистического моделирования на ЭВМ.
В целом, полученные в диссертации выводы и рекомендации формулировались на основе всестороннего обсуждения результатов исследований, допускают ясное физическое истолкование, имеют понятную содержательную трактовку и совпадают в ряде частных случаев с известными результатами, полученными другими авторами.
Значимость для науки и практики. Теоретическая значимость результатов диссертационной работы заключается в том, что полученные методические и экспериментальные результаты отвечают потребностям важного направления — разработки и совершенствованию алгоритмов обнаружения, классификации и локализации объектов в интересах создания эффективных аппаратно-программных средств анализа изображений. Полученные аналитические выражения и зависимости для характеристик синтезированных алгоритмов позволяют обоснованно выбрать необходимый алгоритм в соответствии с требованиями, предъявляемыми к показателям качества обработки информации, с учетом существующих ограничений и дестабилизирующих факторов, а также исходя из соображений программной реализации.
Применение предложенной автором двухэтапной процедуры поиска объектов на основе обнаружения их границ позволяет осуществлять поиск объектов в условиях повышенной априорной неопределенности относительно формы границы и уровня яркости объектов. Его характерной особенностью при обнаружении и локализации объектов является важное для практики свойство восстанавливать целостную границу объекта в случае первичного пропуска некоторых участков границы или ошибочного определения перепадов яркости в местах отсутствия границы.
Результаты диссертационной работы имеют практическое значение для разработки специального математического и программного обеспечения в интересах автоматической обработки изображений при обнаружении, классификации и локализации образов, а также проведении контурного анализа в системах технической диагностики, пассивной оптической локации, дистанционного аэрокосмического мониторинга, а также в современных системах компьютерной микроскопии.
Реализация результатов работы. Полученные в диссертации результаты реализованы в полном объеме в Воронежском государственном университете в НИР «Кассиопея-ВГУ», а также Институтом нанотехнологии микроэлектроники РАН (ИНМЭ РАН) в НИР «Кассиопея» при создании программного комплекса для обработки цифровых изображений.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на XVI Международной научно-технической конференции «Радиолокация, навигация, связь» (Воронеж) в 2010 году; на VII Международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (Воронеж) в 2006 году; на VI, VII, VIII Международных конференциях «Информатика: проблемы, методология, технологии» (Воронеж) в 2006, 2007 и 2008 годах.
Публикации. По теме диссертации опубликовано 10 работ [38-47], в том числе 3 статьи [40,41,43] в изданиях, рекомендованных ВАК. Большинство публикаций выполнены в соавторстве с научным руководителем. В совместных работах научному руководителю принадлежит постановка задачи и определение направления исследований, автору - проведение рассуждений, вывод аналитических зависимостей, необходимых для решения поставленных задач, организация экспериментов для обоснования алгоритмов, полученных теоретическим путем, анализ и интерпретация полученных результатов, а также разработка программных модулей для реализации контурного анализа изображений, обнаружения, классификации и локализации объектов. В работе
40], опубликованной с участием других соавторов, соискателем предложен совместный двухэтапный алгоритм обнаружения объектов на основе первичного контурного анализа изображения, проделаны основные теоретические расчеты для решения поставленной задачи обнаружения объекта для общего случая, а также предложен алгоритм синтеза целостной границы объекта с использованием теории графов.
Объем и структура диссертационной работы. Диссертация состоит из введения, четырех разделов, заключения и списка литературы из 106 наименований. Объем диссертации составляет 181 страницу, включая 170 страниц основного текста, содержащего 48 рисунков и 1 таблицу, и 11 страниц списка литературы.
Заключение диссертация на тему "Обнаружение и оценивание границ объектов на изображениях в условиях аддитивного шума и деформирующих искажений"
Выводы- по главе
1. Сформулирована обобщенная постановка задачи описания изображения объектов с существенно неоднородной текстурой на основе разбиения пикселей на группы по некоторому базовому индексирующему множеству (значений яркости, цветности и т.д.). На основе данного представления формируется инвариантное к повороту и изменению масштаба описание эталонного изображения. Данное описание основано на формировании гистограмм определенных базовых характеристик изображения в выделенных группах. Конкретно предложено использовать следующие характеристики - яркость и координаты пикселей в полярной системе — угла и расстояния при разбиении пикселей изображения на группы в порядке возрастания яркости. Для сравнения гистограмм эталонного описания и наблюдаемого изображения по группам пикселей введены различные меры близости векторов в многомерном пространстве, в частности, косинус угла и мера Танимото. На этой основе введена обобщенная мера близости двух изображений, вычисляемая на основе мер близости по каждой характеристике.
Синтезировано пороговое решающее правило для принятия решения о наличии или отсутствии эталонного объекта в локальном участке наблюдения. Для определения количества применяемых групп и количества пикселей в них целесообразно использовать предложенную методику, основанную на использовании степени геометрического пересечения групп двух образов и последующей максимизации показателя неизменяемости групп вспомогательного набора образов относительно имеющегося эталонного образа.
2. В рамках рассматриваемого подхода сформулирована постановка задачи классификации нескольких образов и предложено ее решение, основанного на разбиении пикселей на группы по базовому индексирующему множеству значений яркости. Принятие решения- происходит на основе определения минимальной меры близости наблюдаемого участка с одним из эталонных. При этом задача классификации рассматривается совместно с задачей точного определения координат обнаруживаемых объектов. Для этого рассчитывается функция близости локальных участков и эталонов. Точное определение местоположения объектов основано на глобальном анализе данной функции близости при поиске и отборе ее локальных максимумов, что обеспечивает максимальную точность в позиционировании обнаруженных объектов и позволяет учесть их взаимное расположение. В зависимости от априорной информации о расстояниях между центрами объектов и - их плотности можно устанавливать соответствующие параметры локализации объектов, улучшая при< этом качество обнаружения и локализации объектов.
3. На основе предложенных алгоритмов обнаружения и классификации объектов разработан программный комплекс для исследования указанных алгоритмов. Комплекс позволяет производить весь набор процедур предварительной настройки параметров алгоритмов анализа изображений для обнаружения и классификации объектов. При необходимости после обнаружения объектов в разработанном программном обеспечении имеется возможность производить дальнейшее оценивание границ объектов на основе алгоритмов обнаружения перепадов яркости в соответствии с подходом, изложенным во второй и третьей главах работы. С помощью данного комплекса было произведено тестирование алгоритмов анализа изображений различных классов, в том числе изображений объектов микроэлектроники, аэрофотосъемки, микробиологии, печатного текста. В ходе тестирования разработанного программного обеспечения при распознавании объектов микроэлектроники установлено, что вероятность правильной классификации составляет в среднем порядка 0.96-0.98 в зависимости от качества обрабатываемых изображений. Предложенные алгоритмы показывают лучшие результаты, чем алгоритмы корреляционно-экстремального анализа, для которых вероятность правильного распознавания в тех же условиях составила в среднем 0.81-0.87.
Заключение
В ходе выполнения диссертационной работы поставлены и решены следующие научные задачи:
- рассмотрены и проанализированы результаты ранее выполненных исследований, посвященных вопросам обнаружения, классификации и локализации пространственно распределенных объектов на изображениях, а также контурного анализа изображений;
- сформулирована общая постановка, синтезированы и проанализированы квазиправдоподобный статистический и нейросетевой алгоритмы решения задачи совместного обнаружения и оценивания параметров локальных неоднородностей, в соответствии с моделью «идеального» перепада яркости;
- синтезирован и исследован двухэтапный алгоритм совместного обнаружения и локализации объектов, основанный на первичном обнаружении совокупности локальных неоднородностей на изображении и выделении замкнутой границы случайной формы по результатам вторичной обработки;
- предложены и исследованы алгоритмы обнаружения и классификации объектов, основанные на применении индексирующего разбиения сравниваемых кадров эталонного и наблюдаемого изображения по группам яркости и использовании обобщенного гистограммного описания эталонного изображения объекта, инвариантного к сдвигу, повороту и масштабированию.
В ходе проведенных исследований получены следующие новые результаты и выводы.
1. Сформулирована постановка задачи обнаружения и оценивания параметров, локальной неоднородности, представляемой в рамках модели идеального перепада яркости в текущем окне наблюдения при обработке изображения, позволяющая использовать априорную информацию относительно яркости фона, уровня и параметров локализации перепада яркости. В общем виде получена структура оптимального статистического алгоритма совместного обнаружения и оценивания параметров ЛН, основанного на применении обобщенного метода максимального правдоподобия при выборе статистических гипотез для случая неизвестных значений параметра. В зависимости от имеющейся априорной информации о параметрах локальной неоднородности получены и проанализированы квазиоптимальные реализации указанного алгоритма, основанные на применении аналитических и численных методов решения нелинейных алгебраических уравнений для оценки неизвестных параметров.
В ходе статистического моделирования разработанных алгоритмов установлено, что оценки параметров угла, уровня перепада яркости и яркости фона являются несмещенными, а оценка параметра расстояния перепада яркости от центра окна наблюдения имеет смещение от истинного значения порядка 2-3% от размера окна наблюдения. Полученные в ходе статистического моделирования СКО оценивания параметров перепада яркости находятся в зависимости от конкретного параметра в пределах 5-15% от своих максимальных значений при отношении сигнал/шум больше 2.
При решении задачи синтеза нейросетевого алгоритма совместного обнаружения и оценки параметров локальной неоднородности предложена структура нейронной сети на основе двухслойного персептрона. Для типовых условий в рамках модели идеального перепада яркости в локальном окне наблюдения проведено обучение нейросетевого алгоритма обработки информации. Выполненные эксперименты показали, что при больших и умеренных (больше 2-х) отношениях сигнал/шум вероятности ошибок первого и второго рода полученного нейросетевого алгоритма на 0.01-0.03 меньше чем у статистического, а СКО определения параметров (за исключениям углового положения) у нейросетевого алгоритма на 1-3% (от максимального значения соответствующего параметра) меньше, чем у статистического. Анализ характеристик обработки реальных изображений статистическим и нейросетевым алгоритмами также показал большую робастность нейросетевого алгоритма по отношению к параметрам шумовых искажений, что объясняется используемыми приближениями модели «идеального» перепада яркости при реализации статистически оптимального алгоритма обработки информации.
2. С целью проведения количественного анализа алгоритмов обнаружения локальных неоднородностей, а таюке для последующей оптимизации алгоритмов вторичной обработки для выделения целостной границы объектов на изображении предложены методики расчета вероятностей ошибок первого и второго рода при решении задачи обнаружения ЛН участка границы. Указанные методики основаны на полученных выражениях для моментов логарифма отношения правдоподобия при использовании модели обнаружения идеального перепада яркости в присутствии аддитивного гауссовского шума.
В первой методике для расчета вероятностей ошибок обнаружения используются условные относительно полученных оценок параметров локальной неоднородности вероятности ошибок для каждого конкретного анализируемого локального участка изображения. Проведенное имитационное моделирование показало, что апостериорные вероятности ошибок, рассчитываемые по данной методике при больших и умеренных отношениях сигнал/шум (больше 3), незначительно (порядка 10-15%) отличаются от получаемых экспериментальных значений, находясь в интервале значений 0.0.1. Несмотря на то, что такие оценки необходимо вычислять каждый раз для очередного анализируемого участка изображения, они являются более информативными по сравнению с оценками безусловных вероятностей ошибок принятия решений при обнаружении локальной неоднородности.
На основе второй методики имеется возможность проводить расчет безусловных вероятностей ошибок принятия решений заранее для любого анализируемого участка изображения, что может дать выигрыш во времени при дальнейшей реализации алгоритма выделения целостной границы объекта в ходе вторичной обработки, опирающегося на данные вероятности. Эта методика основана на выполнении численного интегрирования вероятностей ошибок по параметру перепада яркости, имеющему равномерное распределение в своей области определения при соответствующей гипотезе. Проведенное имитационное моделирование алгоритма показало, что безусловные вероятности ошибок, рассчитываемые по данной методике при больших и умеренных отношениях сигнал/шум, не более чем на 12-17% отличаются от экспериментально получаемых значений и находятся в интервале значений 0.0.1.
3. Для предложенной модели объектов, характеризующихся лишь наличием различимого перепада яркости на границе замкнутого контура случайной формы относительно общего фона и диапазоном значений поперечного размера объекта, синтезирован двухэтапный алгоритм совместного обнаружения и оценивания его границы при обработке изображений в условиях шумов. В этом алгоритме после первичного анализа локальных участков на всем изображении в ходе вторичной обработки синтезируется наиболее вероятная граница гипотетического объекта и методом максимума правдоподобия принимается решение о наличии или отсутствии объекта.
Исходная сформулированная оптимизационная задача построения контура в общем случае является ЫР-полной и требует больших затрат времени вычислений. Предложен подход, обеспечивающий существенное сокращение количества перебираемых вариантов расположения границы для объектов, форма границы которых описывается однозначной функцией в полярных координатах относительно геометрического центра объекта. Данный подход позволил разработать алгоритм вторичной обработки информации, который с существенно более высоким быстродействием (за полиномиальное время) находит наиболее правдоподобный контур на основе поиска минимального пути на графе методом динамического программирования. Отличительной особенность данного подхода при построении непрерывной (попиксельной) границы является то, что пропущенные в ходе первичной обработки локальные участки при вторичной обработке корректируются, что обеспечивает восстановление целостной границы.
Применение предложенной двухэтапной процедуры обработки изображения при решении задачи обнаружения объектов в присутствии аддитивного гауссовского шума, позволяет достичь при уровне отношения сигнал/шум более 2 значений вероятностей ошибок первого и второго рода порядка 0.01. Проведенные эксперименты показали, что разработанный алгоритм может применяться при обработке реальных изображений как в случае решения задачи обнаружения одиночного объекта, так и в случае обнаружения совокупностей множества однотипных объектов с границей, подвергающейся деформирующим искажениям.
4. Рассмотрена общая постановка задачи описания изображения объектов с существенно неоднородной текстурой на основе разбиения пикселей на группы по некоторому базовому индексирующему множеству (значений яркости, цветности и т.д.). Предложенное описание изображения основано на вычислении гистограмм различных свойств пикселей в группах и позволяет инвариантно к сдвигу, повороту и изменению масштаба задавать эталонные описания объектов. Описан общий подход к формированию мер близости двух образов, который отличается от имеющихся разработок тем, что может использовать различные меры близости векторов в многомерном пространстве, например, такие как косинус угла и мера Танимото.
На основе введенной в общем случае меры близости двух образов предложено решение задачи классификации (распознавания) нескольких образов, которая рассматривается совместно с задачей точного определения координат обнаруживаемых объектов, что необходимо для решения задачи поиска объектов. Для оптимизации процесса настройки разработанного алгоритма классификации предложены процедура автоматического определения количества применяемых групп и количества пикселей в них, основанная на максимизации показателя неизменяемости групп вспомогательного набора образов относительно имеющегося эталонного образа, а также процедура выбора порогов принятия решения с целью достичь необходимые показатели качества.
Предложенные алгоритмы обнаружения и классификации объектов были реализованы в разработанном программном комплексе анализа изображений, в котором одновременно с обнаружением объектов обеспечивается оценивание границ объектов на основе алгоритмов обнаружения перепадов яркости в соответствии с описанным во второй и третьей главах диссертации подходом. В ходе экспериментальных исследований комплекса было выполнено тестирование предложенных алгоритмов для анализа изображений различных классов, в том числе изображений объектов микроэлектроники, аэрокосмических изображений, объектов микробиологии, печатного текста, которое показало работоспособность и устойчивость предложенных алгоритмов анализа изображений в реальных условиях. В ходе сравнения разработанных алгоритмов с алгоритмами корреляционно-экстремального анализа при обнаружении и распознавании объектов микроэлектроники они показали лучшие результаты, обеспечивая вероятность правильной классификации в среднем порядка 0.96-0.98, которая для алгоритмов корреляционно-экстремального анализа в аналогичных условиях составила в среднем 0.81-0.87.
Библиография Соломатин, Алексей Иванович, диссертация по теме Системный анализ, управление и обработка информации (по отраслям)
1. Акимов, П.С. Теория обнаружения сигналов / П.С. Акимов, П.А. Бакут, В.А. Багданович и др.; под ред. П.А. Бакута. — М.: Радио и связь, 1984. — 440 с.
2. Алгазинов, Э.К. Анализ и компьютерное моделирование информационных процессов и систем / Э.К. Алгазинов, A.A. Сирота. — М.: Диалог-МИФИ, 2009. —416 с.
3. Бакут, П.А. Сегментация изображения: методы выделения границ областей / П.А. Бакут, Г.С. Колмогоров // Зарубежная радиоэлектроника. — 1987. — №10. —С.25-55.
4. Буслов, В.А. Численные методы. 4.2. Решение уравнений: Курс лекций / В.А. Буслов, C.JI. Яковлев. — СПб.: С-Петерб. гос. ун-т, 2001. — 44 с.
5. Введение в контурный анализ; приложения к обработке изображений и сигналов / Под ред. Я.А. Фурмана. — 2-е изд., испр. — М.: Физматлит, 2003.592 с.
6. Вентцель, Е.С. Теория вероятностей / Е.С. Вентцель. — М.: Наука, 1969. — 576 с.
7. Виттих, В.А. Обработка изображений в автоматизированных системах научных исследований / В.А. Виттих, В.В. Сергеев, В.А. Сойфер. — М.: Наука, 1982. —216 с.
8. Глумов, Н.И. Метод быстрой корреляции с использованием тернарных шаблонов при распознавании объектов на изображениях / Н.И. Глумов, Е.В. Мясников, В.Н. Копенков, М.А. Чичева // Компьютерная оптика. — 2008.
9. Т.32. — № 20. — С.277-282.
10. Головко, В.А. Нейронные сети: обучение, организация и применение. Кн. 4: Учеб. пособие для вузов / В.А. Головко, под ред. А.И. Галушкина. — М.: ИПРЖР, 2001. — 256 с.
11. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. —М.: Мир, 1982. — 416 с.
12. Джайн, А.К. Успехи в области математических моделей для обработки изображений / А.К. Джайн // ТИИЭР. — 1981. — Т.69. — №5. — С.9-39.
13. Казанский, Н.Л. Сравнение объекта и эталона по отклонению контуров / Н.Л. Казанский, В.В. Мясников, Р.В. Хмелев // Компьютерная оптика. — 2000. — №20. — С. 134-139.
14. Козин, Н.Е. Распознавание лиц по показателям сопряженности в пространстве суммирующих инвариантов / Н.Е. Козин, В.А. Фурсов // Компьютерная оптика. — 2008. — Т.32. — №4. — С.400-402.
15. Корн, Г. Справочник по математике для научных работников и инженеров / Г. Корн, Т. Корн. — М.: Наука, 2003. — 832 с.
16. Кривенко, М.П. Распознавание элементов изображения, имеющих различные размеры / М.П. Кривенко // Системы и средства информатики. — 2007. — №1.1. С.30-51.
17. Крянев, A.B. Математические методы обработки неопределенных данных / A.B. Крянев, Г.В. Лукин. — М.: Физматлит, 2003. — 216 с.
18. Кудаев, A.B. Квазиправдоподобное обнаружение изображения с неизвестной площадью / А.П. Трифонов, A.B. Кудаев // Материалы XII международной научно-технической конференции «Радиолокация, навигация, связь». — Воронеж, 2006. — Т. 1. — С. 135-143.
19. Кудаев, A.B. Оценка координат изображения с неизвестной интенсивностью / А.П. Трифонов, A.B. Кудаев // Материалы XIV международной научно-технической конференции «Радиолокация, навигация, связь». — Воронеж, 2008. — Т. 1. — С.281-290.
20. Кудаев, A.B. Оценка координат изображения с неизвестными интенсивностью и площадью / А.П. Трифонов, A.B. Кудаев // Известия ВУЗов. Радиоэлектроника. — 2009. — №5. — С.3-14.
21. Кудаев, A.B. Статистический анализ регулярных неоднородностей стохастических гауссовских полей: диссертация канд. физ-мат. наук / A.B. Кудаев. — Воронеж, 2010. — 137 с.
22. Куцов, Р.В. Статистический анализ движущихся пространственных неоднородностей гауссовского случайного поля: диссертация канд. физ-мат. наук / Р.В. Куцов. — Воронеж, 2007. — 185 с.
23. Луценко, М.Т. Автоматизированная система распознавания объектов на микроскопических изображениях биологических образцов. / М.Т. Луценко, Н.В. Ульянычев, Н.П. Семичевская // Бюллетень физиологии и патологии дыхания. — 1999. — №3. — С.83-91.
24. Маслов, О.В. Нейросетевые и статистические алгоритмы выделения неоднородных участков и границ раздела случайных полей: диссертация канд. физ-мат. наук / О.В. Маслов. — Воронеж, 2004. — 176 с.
25. Методы компьютерной обработки изображений / Под ред. В.А. Сойфера: — 2-е изд., испр. —М.: Физматлит, 2003. — 784 с.
26. Миронов, Б.М. Автоматическое обнаружение распределенных объектов на когерентно-локационных изображениях с учетом априорных данных / Б.М. Миронов, А.Н. Малов, В.А. Кузнецов // Компьютерная оптика. — 2008.
27. Т.32. — № 4. — С.417-422*.
28. Медведев, B.C., Нейронные сети. MATLAB 6 / B.C. Медведев, В.Г. Потемкин.
29. М.: Диалог-МИФИ, 2002. — 496 с.
30. Нейроинформатика / А.Н. Горбань и др.. — Новосибирск: Наука. Сибирское предприятие РАН, 1998. — 296 с.
31. Обнаружение изменения свойств сигналов и динамических систем / под ред. М. Бассвиль, А. Банвениста. — М.: Мир, 1989. — 278 с.
32. Осецкая, Г.А. Обнаружение оптического изображения с неизвестной-площадью / Г.А. Осецкая // Радиотехника. — 1994. — №1. — С.64-70.
33. Осецкая, Г.А. Обнаружение оптического изображения с неизвестными интенсивностью и площадью при наличии фона > с неизвестной интенсивностью / Г.А. Осецкая // Автометрия. — 1992. — №4. — С.40-^16.
34. Осовский, С. Нейронные сети для обработки информации / С. Осовский. — М.: Финансы и статистика, 2002. — 344 с.
35. Перетяган, Г.И. Представление изображений гауссовыми случайными полями. / Г.И. Перетяган // Автометрия. — 1984. — №6. — С.42—48.
36. Перов, А.И. Алгоритм последовательного выделения контура объекта на двумерных цифровых изображениях / А.И. Перов, Г.Г. Соколов // Статистический синтез радиосистем. — 1998. — №3. — С.83-87.
37. Садыхов, Р.Х. Система распознавания рукописных символов на базе нейронных сетей и структурных методов / Р.Х. Садыхов, О.Г. Маленко, М.Л. Селингер // Нейрокомпьютеры: разработка и применение. — 2004. — №1. — С.32-39.
38. Семенов, С.М. Распознавание некоторых объектов на изображениях, получаемых со спутников / С.М. Семенов, A.B. Татарников // Солнечно-земная физика. — Иркутск: Институт солнечно-земной физики СО РАН, 2004. — №5. — С.80-83.
39. Сергеев, В.В. Некоторые модификации цифрового коррелятора для обнаружения объектов на изображении / В.В. Сергеев, М.А. Чичева // Компьютерная оптика. — 1989. — № 5. — С.78-84.
40. Сирота, A.A. Двухэтапный алгоритм обнаружения и оценивания границы объектов на изображениях в условиях аддитивных помех и деформирующих искажений / A.A. Сирота, В.В. Воронова, А.И. Соломатин // Компьютерная оптика. — 2010. — Т.34. — №1. — С.109-117.
41. Сирота, A.A. Обнаружение и оценка параметров перепада яркости в задаче контурного анализа объектов / A.A. Сирота, А.И. Соломатин // Автометрия.2009. — Т.45. — №5. — С.59-69.
42. Сирота, A.A. Поиск множества объектов на основе инвариантных преобразований» эталонных фрагментов изображения / A.A. Сирота, А.И. Соломатин // Информационно-измерительные и управляющие системы.2010. — Т.8. — №6. — С.8-15.
43. Сирота, A.A. Статистические алгоритмы обнаружения границ объектов на изображениях / A.A. Сирота, А.И. Соломатин // Вестник Воронежского государственного университета, серия: Системный анализ и информационные технологии. — 2008. — №1. — С.58-64.
44. Сосулин, Ю.Г. Метод инвариантного нейросетевого распознавания двумерных изображений / Ю.Г. Сосулин, Фам Чунг Зунг // Радиотехника и электроника. — 2004. — Т.49. — № 5. — С.595-601.
45. Сосулин, Ю.Г. Теория обнаружения и оценивания стохастических сигналов / Ю.Г. Сосулин. — М.:Сов. радио, 1978. — 320 с.
46. Станкевич, JLA. Классификация объектов с использованием нормализующего фильтра и нечеткой нейросети / JI.A. Станкевич, Н.Д. Хоа // Нейрокомпьютеры: разработка и применение. — 2009. — №3. — С.50-57.
47. Терентьев, И.В. О надежном распознавании объектов на аэрокосмических изображениях земной поверхности / И.В. Терентьев // Исследование земли из космоса. — 1999. — №5. — С.57-64.
48. Террайен, Ч.У. Алгоритмы анализа изображений, основанные на статистических моделях. / Ч.У. Террайен, Т.Ф. Куатьери, Д.Е. Даджон // ТИИЭР. — 1986. — Т.74. — №4. — С.4-25.
49. Тихонов, В.И. Статистическая радиотехника / В.И. Тихонов. — М.: Сов. радио, 1966. — 680 с.
50. Томашевич, Н.С. Система распознавания микробиологических объектов на изображении с помощью нейронных сетей / Н.С. Томашевич, C.B. Коробкова // Нейрокомпьютеры: разработка, применение. — 2005. — №1-2. — С.56-61.
51. Трифонов, А.П. Обнаружение движущегося пространственно протяженного объекта на фоне с неизвестной интенсивностью / А.П. Трифонов, Р.В. Куцов // Автометрия. — 2005. — №1. — С.3-18.
52. Трифонов, А.П. Обнаружение объектов с неизвестной площадью при наличии фона / А.П. Трифонов, Ю.Н. Прибытков // Автометрия. — 2005. — №4. — С.24-39.
53. Трифонов, А.П. Обнаружение случайных изображеий пространственно протяженных объектов, затеняющих фон / А.П. Трифонов, Ю.Н. Прибытков // Автометрия. — 2000. — №4. — С. 14-25.
54. Трифонов, А.П. Обнаружение стохастических сигналов с неизвестными параметрами / А.П. Трифонов, Е.П. Нечаев, В.И. Парфенов; под ред. А.П. Трифонова. — Воронеж: ВГУ, 1991. — 246 с.
55. Трифонов, А.П. Совместное различение сигналов и оценка их параметров на фоне помех / А.П. Трифонов, Ю.С. Шинаков. — М.:Радио и связь, 1986. — 264 с.
56. Уоссерман, Ф. Нейрокомпьютерная техника. / Ф. Уоссерман. — М.: Мир, 1992. —184 с.
57. Фукунага, К. Введение в статическую теорию распознавания образов / К. Фукунага. — М.:Наука, 1979. — 368 с.
58. Хмелев, Р.В. Совместное использование структурного анализа и метрики Хаусдорфа при сравнении объекта и эталона / Р. В. Хмелев // Компьютерная оптика. —2005.—№27. —С. 174-176.
59. Ярославский, Л.П., Введение в цифровую обработку изображений / Л.П. Ярославский. — М.: Сов. Радио, 1979. — 312 с.
60. Ярославский, Л.П., Цифровая обработка сигналов в оптике и голографии: Введение в цифровую оптику / Л.П. Ярославский. — М.: Радио и связь, 1987.296 с.
61. Ans, В. Adaptive neural architectures: detection of primitives / B. Ans, J. Herault, C. Jutten // Proc. of COGNITIVA. — 1985. — pp. 593-597.
62. Autio, I. Using natural class hierarchies in multi-class visual classification / I. Autio.— Pattern Recognition. — 2006.— v.39. — №7.— pp. 1290-1299.
63. Basseville, M. Edge detection using sequential methods for change in level, part I, A sequential edge detection algorithm / M. Basseville, B. Espiau // IEEE Trans. On A.S.S.P., ASSP-29. — 1981. — №1. — pp. 16-31.
64. Bell, A.J. An information-maximization approach to blind1 separation and blind deconvolution / A.J. Bell, J.S. Sejnowski // Neural Computation. — 1995. — 7(6).pp. 1129-1159.
65. Belongia, S. Shape matching and object recognition using shape contexts / S. Belongia, J. Malik, J. Puzicha // IEEE Trans, on Pattern Analysis and Machine Intelligence. — 2002. — №24 — pp.509-522.
66. Biederman, I. Recognition-by-components: A theory of human image understanding / Biederman, L // Psychological Review. — 1987. — №94(2). — pp.115-147.
67. Bishop, C.M. Pattern Recognition and Machine Learning / C.M. Bishop. — Springer, 2006.
68. Brown, M. Invariant features from interest point groups / M. Brown, D. Lowe // In Proc. British Machine Vision Conf. — 2002. — pp.656-665.
69. Canny, J.F. A computational approach to edge detection / J.F. Canny // IEEE Trans, on Pattern Analysis and Machine Intelligence. — 1986. — №6. — 1986. — pp. 679-698.
70. Chandrasekaran, V. Range image segmentation by dynamic neural network architecture / V. Chandrasekaran, M. Palaniswami, T.M. Caellir // Parten Recognition. 1996. — vol.29. — №2. — pp. 315-329.
71. Davis, L.S. A survey of edge detection techniques / L.S. Davis // Computer Graphics and Image Processing. — 1975. — vol.4. — №3. — pp. 248-260.
72. Demant, C. Industrial image processing: visual quality control in manufacturing / C. Demant, B. Streicher-Abel, P. Waszkewitz. — Springer; 1 edition, 1999. — 353 p.
73. Deriche, R. Using Canny's criteria to derive an optimal edge detector recursively implemented / R. Deriche // Int. J. Computer Vision. — 1987. — pp. 167-187.
74. Diamantaras, K.I. Principal Component Neural Networks: Theory and Applications / K.I. Diamantaras, S.-Y. Kung. — John Wiley & Sons, 1996. — 272 p.
75. Dijkstra, E. W. A note on two problems in connexion with graphs / E.W. Dijkstra // Numerische Mathematik. — 1959. — V.l. — pp. 269-271.
76. Dougherty, G. Digital Image Processing for Medical Applications / G. Dougherty.
77. Califonia State University, Channel Islands, 2009. — 462 p.
78. Duda, R.O. Pattern Classification / Richard O. Duda, Peter E. Hart, David G. Stork
79. New York: John Wiley & Sons, 2001, — 654 p.
80. Egmont-Peterson, M. Image processing with neural network a review / M. Egmont-Peterson, D. de Ridder, H. Handels // Pattern Recognition. — 2002. — vol.35. —№10. —pp. 2279-2301.
81. Freeman, W.T. The design and use of steerable filters / W.T. Freeman, E.H. Adelson // IEEE Transactions on Pattern Analysis and Machine Intelligence.1993. — vol.13. — №9. — pp. 891-906.
82. Fussenegger, M. On-line, incremental learning of a robust active shape model / M. Fussenegger, M.P. Roth, H. Bischof, A. Pinz // In Proc. DAGM Symposium. — 2006. —pp. 122-131.
83. Gonzalez, R.C. Digital Image Processing (2 edition) / Rafael C. Gonzalez, Richard E. Woods — Addison-Wesley Pub Co, 2002. — 793 p.
84. Harary, F. Graph Theory / F. Harary — Addison-Wesley Publishing Company, Inc, 1969. —274 p.
85. Harris, C. A combined corner and edge detector / C. Harris, M. Stephens // In Proc. of Alvey Vision Conf. — pp. 147-151.
86. Hueckel, M. An operator which locates edges in digital pictures /M. Hueckel // J. Association for Computing Machinery. — 1971. — vol.18. — №.1. — pp.113125.
87. Introduction to Algorithms, Second Edition / Thomas H. Cormen, Ronald L. Rivest, Charles E. Leiserson, Clifford Stein. — The MIT Press, 2001. — 1180 p.
88. Jahne, B. Digital image processing : with CD-ROM / B. Jahne. — Berlin: Springer, 2002. — 572 p.
89. Lindeberg, T. Edge detection and ridge detection with automatic scale selection / T. Lindeberg // International Journal of Computer Vision. — vol.30. — №2. — pp.-117-154.
90. Lowe, D. Object recognition from local scale-invariant features / D. Lowe // In Proc. IEEE Intern. Conf. on Computer Vision. — 1999. — pp.1150-1157.
91. Marchand-Maillet, S. Binary Digital Image Processing: A Discrete Approach / S. Marchand-Maillet, Y.M. Sharaiha. — Academic Press, 1999. — 368 p.
92. Melzer, T. Generalized Canonical Correlation Analysis for ObjectRecognition / T. Melzer. — PhD thesis, Vienna University of Technology, 2002. — 162 p.
93. Ojala, T. Multiresolution gray-scale and rotation invariant texture classification with local binaryatterns / T. Ojala, M. Pietikinen, T. Menp // IEEE Trans, on Pattern Analysis and Machine Intelligence. — 2002. — №24(7). — pp. 971-987.
94. Pratt, W.K. Digital image processing: PIKS inside, 3rd edition / William K. Pratt. — New York: John Wiley and Sons, 2001. — 656 p.
95. Prewitt, J.M.S. The analysis of cell images / J.M.S. Prewitt, M.L. Mendelsohn // Ann. New York Academy of Science. — 1966. — vol.128. —pp.1036-1053.
96. Rosenfeld, A. From Image Analysis to Computer Vision: An Annotated Bibliography, 1955-1979 / A. Rosenfeld // Computer Vision and Image Undestanding. — 2001. — №84. — pp. 298-324.
97. Simoncelli, E.P. Design of multi-dimensional derivative filters / E.P. Simoncelli // First Int'l Conf on Image Processing, Austin, Texas. — 1994. — pp. 259-269.
98. Takala, V. Block-based methods for image retrieval using local binary patterns / V. Takala, T. Ahonen, M. Pietikainen // In Proc. Scandinavian Conf. on Image Analysis. — 2005. — pp. 882-891.
99. Vichi, M. New Developments in Classification and Data Analysis / M. Vichi, P. Monari, S. Mignani, A. Montanari. — Springer; 1 edition, 2005. — 369 p.
100. Winter, M. Spatial Relations of Features and Descriptors for Appearance Based Object Recognition / M. Winter. — PhD thesis, Graz University of Technology, Faculty of Computer Science, 2007. — 157 p.
101. Wirth, N. Algorithm and Data Structures / N. Wirth. — Prentice Hall Published, 1985. —179 p.
102. Zhang, H. Object detection using spatial histogram features / H. Zhang, W. Gao, X. Chen, D. Zhao // Image and Vision Computing. — 2006. — №24(4). — pp. 327-341.
103. Ziou, D. Edge detection techniques: An overview / D. Ziou, S. Tabbone // International Journal of Pattern Recognition and Image Analysis. — 1998. — pp. 537-559.
-
Похожие работы
- Теория и методы первичной обработки видеоинформации
- Разработка и моделирование псевдоградиентных процедур привязки изображений по информационному критерию
- Оценивание геометрических параметров изображений древовидных структур
- Модели и алгоритмы сегментации и фильтрации аппликативных помех на изображениях
- Моделирование движения сцены по последовательности изображений на основе псевдоградиентной адаптации
-
- Системный анализ, управление и обработка информации (по отраслям)
- Теория систем, теория автоматического регулирования и управления, системный анализ
- Элементы и устройства вычислительной техники и систем управления
- Автоматизация и управление технологическими процессами и производствами (по отраслям)
- Автоматизация технологических процессов и производств (в том числе по отраслям)
- Управление в биологических и медицинских системах (включая применения вычислительной техники)
- Управление в социальных и экономических системах
- Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
- Системы автоматизации проектирования (по отраслям)
- Телекоммуникационные системы и компьютерные сети
- Системы обработки информации и управления
- Вычислительные машины и системы
- Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)
- Теоретические основы информатики
- Математическое моделирование, численные методы и комплексы программ
- Методы и системы защиты информации, информационная безопасность