автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы и алгоритмы моделирования векторных локально однородных сцен

005012423

На правах рукописи

КУЛЕЕВ РАМИЛЬ ФУАТОВИЧ

МЕТОДЫ И АЛГОРИТМЫ МОДЕЛИРОВАНИЯ ВЕКТОРНЫХ ЛОКАЛЬНО ОДНОРОДНЫХ СЦЕН

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Казань 2012

005012423

Работа выполнена в Казанском (Приволжском) федеральном университете

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

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

кандидат технических наук, доцент Фофанов Вячеслав Борисович

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

доктор технических наук, профессор Столов Евгений Львович

Марийский государственный технический университет

Защита диссертации состоится 27 января 2012 года в 17.00 часов на заседании диссертационного совета Д 212.079.01 в Казанском национальном исследовательском техническом университете им. А.Н. Туполева - КАИ по адресу: 420111, г.Казань, ул. К.Маркса, 10, зал заседаний Ученого совета.

Автореферат диссертации размещен на сайте КНИТУ им. А.Н. Туполева - КАИ www.kai.ru и отправлен для размещения на официальном сайте ВАК по адресу referat_vak@mon.gov.ru.

С диссертацией можно ознакомиться в библиотеке Казанского национального исследовательского технического университета им. А.Н. Туполева -КАИ.

Автореферат разослан & ъ 2011 г.

Ученый секретарь диссертационного совета, доктор физико-математических наук,

профессор

П.Г. Данилаев

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

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

Работы в области автоматизации дешифрирования изображений интенсивно ведутся с 60-х годов XX века во всех высокоразвитых странах. По данной тематике опубликовано большое количество работ, авторами которых являются К.К. Васильев, Ю.Г. Васин, Ю.В. Визильтер, Р. Вудс, Р. Гонсалес, А.Л. Горелик, И.Б. Гуревич, Р. Дуда, Н.Г. Загоруйко, В.Н. Козлов, В.Р. Крашенинников, Т. Кутс, У. Прэтт, Ю.П. Пытьев, А. Розенфельд, В.В. Сергеев, К. Тейлор, В.Б. Фофанов, Я.А. Фурман, П. Харт и другие. Однако, общей теории дешифрирования пока создать не удалось, несмотря на впечатляющие успехи, достигнутые в распознавании печатных символов, идентификации людей по папиллярным узорам или сетчатке глаза и решении некоторых других прикладных задач.

Одной из задач дешифрирования является поиск на сцене объектов определенного вида. Для ее решения необходимо построить математическую модель сцены, разработать численные методы поиска объектов и исследовать их эффективность. Для возможности экспериментального исследования эффективности методов поиска объектов необходимо разработать методы моделирования изображений сцен. В.Б. Фофановым1 предложены математическая теория и формализация задачи поиска объектов, состоящая из трех последовательных этапов: поиск зон интереса, сегментация и вычисление признаков. Сформулированы условия сходимости решающих правил к оптимальным, с вероятностью ошибки, равной нулю, когда объемы п выборок и их количество в стремятся к бесконечности. Однако на практике приходится работать с конечным числом выборок конечного объема. Поэтому возникает вопрос о зависимости результатов от п и 5.

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

1 В.Б. Фофанов О теоретико-вероятностной формализации задачи дешифрирования аэрокосмических изображений // Автометрия. 2003. №6.- С. 107-118.

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

Для ее достижения были поставлены и решены следующие задачи:

1. Построение математической модели сцены.

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

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

4. Разработка комплекса программ для экспериментального исследования алгоритмов поиска объектов по векторным изображениям.

5. Исследование эффективности алгоритмов поиска объектов по векторным изображениям в зависимости от сложности сцены и параметров алгоритмов.

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

Методы исследований. Для решения поставленных задач используется аппарат теории вероятностей, математической статистики, теории случайных процессов и полей. Программное обеспечение разработано на языке С# в среде Microsoft Visual Studio 2008.

Научная новизна.

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

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

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

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

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

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

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

2. Численные методы моделирования изображений локально однородных сцен.

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

4. Комплекс программ для экспериментального исследования алгоритмов поиска объектов по векторным изображениям.

Апробация работы. Результаты диссертационной работы докладывались на VIII и IX Международных конференциях «Pattern Recognition and Image Analysis: New Information Technologies» (г.Йошкар-Ола, 2007; г. Нижний Новгород, 2008), X Международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Пермь, 2010), IX Международной конференции «Интеллектуальные системы и компьютерные науки» (г. Москва, 2006), XV Международной конференции «Проблемы теоретической кибернетики» (г.Казань, 2008), XVIII Всероссийской межвузовской научно-технической конференции «Электромеханические и внутри-камерные процессы в энергетических установках, струйная акустика и диагностика, приборы и методы контроля природной среды, веществ, материалов и изделий» (г.Казань, 2006), научных семинарах «Перспективные информационные технологии» в НИИММ имени Н.Г. Чеботарева (руководитель д.ф.-м.н., проф. В.Д. Соловьев), «Методы моделирования» при КНИТУ имени А.Н. Туполева (руководитель д.ф.-м.н., проф. В.А. Райхлин).

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

Структура и объем диссертации. Диссертация состоит из Введения, пяти глав, Заключения и Списка использованных источников из 100 наименований. Общий объем диссертации составляет 182 страницы, включая 45 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

В качестве пикселя с координатами г 6 2г рассматривается ¡/-мерная случайная величина = (<^)1<у<„, определенная на некотором (Г2, А, Р) и принимающая значения в У = У", где У - конечное множество значений скалярной случайной величины 1 < ] < V. Семейство называется

векторной сценой. Пусть си € П, тогда х{ = £1(и>), ъ € будет называться j-м скалярным изображением пикселя а х3 = ~ ,?-м скалярным

изображением векторной сцены, 1 < j < v. Изображением векторной сцены (или векторным изображением) называется семейство х = (г3)^^ ее скалярных изображений. Объектом с проекцией А в общем случае будет совокупность векторных случайных величин = (£а)аел, а его изображением - совокупность векторов хл = (ха)аел- Для квадрата <2 на подмножество Рг{0) точек из <5 называется границей квадрата, если каждая точка г € имеет хотя бы одного соседа из Z2 \ ф.

Пусть й - борелевская функция на ВУ х Я", для которой выполняются аксиомы расстояния, а £ и г) - векторные случайные величины на (П,А,Р). В этом случае г]) будем называть случайным расстоянием между £ и г].

Объект на скалярной сцене называется светлым (соответственно, темным) пятном, если, во-первых, существует квадрат С? на Z'1 такой, что А С (<3 \ ^г(<5)), во-вторых, Е£г = тд\А, ъ € Я \ А, и, в-третьих, тА > гпдух (соответственно, тпа < т^л). Пиксели = (£2):ге<з\л называются окрестностью пятна или фоном, а семейство ^ = (£г)ге<? случайных величин -зоной интереса объекта. В общем случае, когда и > 1, первое условие остается без изменения, второе условие принимает вид Е£г = т<з\л, г € <3 \ Л,

третье - ¿(ша, > 0.

Для оценки сложности скалярной сцены предлагается использовать значение к, называемое отношением сигнал/шум и определяемое равенством к = ^^Г^'л1 ■ При условии а' = а3А = 1 < ] < I/, за меру сложности векторной сцены предлагается использовать величину к = у/Щ Н-----1

В пункте 1.3 предлагается формальная постановка задачи поиска заданных объектов на локально однородной сцене. Предполагается, что известны форма, диаметр <1(А) и другие геометрические признаки объектов, а также сторона I зоны интереса. Задача состоит в указании проекций объектов. В качестве критериев эффективности методов поиска зон интереса (первый этап поиска объектов) предлагается использовать вероятность И{А) пропуска зон интереса или вероятность N(<3 \ А) ложных тревог. С формальной точки зрения, сегментацию зоны интереса (второй этап поиска объектов) предлагается рассматривать как классификацию ее пикселей на два класса. Поэтому качество сегментации будет измеряться вероятностями п{А) ошибки классификации пикселей объекта, п{С} \ А) ошибки классификации пикселей фона или п((5) ошибки классификации пикселей всей зоны интереса.

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

Исходными данными метода моделирования изображений локально однородной сцены являются ширина и> и высота к прямоугольного изображения в масштабных единицах, карта проекций объектов, вид распределения (нормальное или равномерное), среднее т.а и дисперсия а\, радиус г'А корреляции объекта, аналогично вид распределения (нормальное или равномерное), среднее тП(2\а и дисперсия радиус корреляции фона. Метод состоит из

следующих этапов:

1) формируется изображение х'А со сторонами ги и к, с независимыми значениями пикселей. Каждый пиксель принимает значение случайной величины с заданным для объекта видом распределения, со средним тА и дисперсией аА (2г 4 + I)2), где гА = г^/лД

2) формируется изображение со сторонами и> и Н, с независимыми значениями пикселей, с заданным для фона видом распределения, со средним тд\А и дисперсией <Гд\А{Щ\А + I)2, где гд\А = г'^/у/2;

3) формируется локально однородное изображение для объектов. Значение каждого пикселя изображения х'А заменяется на среднее арифметическое по его окрестности квадратной формы с центром в х'г и стороной 2гА +1;

4) формируется локально однородное изображение х^А для фона. Значение каждого пикселя изображения х'^, А заменяется на среднее арифметическое по его окрестности квадратной формы с центром в х'Т и стороной 2^ + 1;

5) формируется итоговое изображение х'д со сторонами ю и Л масштабных единиц. Если значение пикселя с координатами ъ на карте равно единице, то яркость соответствующего пикселя изображения х'д принимается равной значению пикселя с координатами г изображения х'А объекта, иначе - значению пикселя с координатами ъ изображения фона.

В качестве примера на рис. 1 приведены фрагменты локально однородных изображений с к = 0.75 и к = 1.5 для г' = у/2. Очевидно, что выявление объектов по первому изображению требует больших усилий.

- > ■ ' ■ * .......

|| щр |Щ ЙЙ» йШШ Щ '

У ' ^ш , л *К \ йЙ ар

анаиг' • V - 1 ■ . <\ ; • • . •...

Рис. 1. Локально однородная модельная сцена (к = 0.75 - слева и к = 1.5 - справа)

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

ние их эффективности и обсуждаются рекомендации по применению методов.

В пункте 2.1 показано, что для любого заданного объекта с диаметром й(А) и стороной зоны интереса I существует семейство СЦ(1, Д) квадратов со стороной I и шагом А, содержащее его зону интереса. Вершины квадратов в С}(1, Д) имеют координаты г = г0 + гДе1 + ^"Де2,г € 2,3 е2,е\ = (1,0),е2 = (0,1), 1 < Д < I - й{А) - 1. При этом количество Д)| квадратов не зависит от количества присутствующих на сцене объектов. Для уменьшения числа квадратов, в которых необходимо проводить сегментацию, на следующем, втором, этапе предлагается проводить классификацию квадратов <2 из (¿(1, Д) на зоны интереса и остальные.

Пункт 2.2 посвящен исследованию эффективности методов и алгоритмов классификации квадратов из (¿(1, Д) на локально однородных сценах. В пункте 2.2.1 рассматривается скалярный случай. Пусть А - проекция светлого пятна <1(А) - его диаметр и В (а, г) - квадрат с центром в а и радиусом г вписанной окружности, лежащий в проекции А. Выберем квадрат (2 со стороной I > 2{(1{А) - г + 1) + 1 и центром в а. Разделим проекцию Ёг((д) границы на 5 непересекающихся связных частей Fí\;•, 1 < з < й, по п = |В(а,г)| = (2г + I)2 точек в каждой. Тогда случайные величины , определяемые равенствами вида хрГ] = Х^е^^ хгЛ < 3 < в, будут являться оценками неизвестного среднего значения т,(}\А фона. С другой стороны, изображение хВ(я,г) = (^)2ев(а,г) квадрата В(а, г) можно использовать для получения оценки ха = Ег£в(а,г)неизвестного среднего тА пят-

на. Если ха > Х]?п, 1 < з < 5, то квадрат ф считается зоной интереса, иначе - пустым квадратом. Известно, что данное решающее правило стремится при г +оо и в +со к байесовскому с нулевой вероятностью ошибки классификации.

Исходными данными алгоритма классификации квадратов являются прямоугольный фрагмент изображения х, радиус г' корреляции изображения, сторона I зоны интереса, шаг Д, радиус г сглаживания, число а фрагментов изображения и знак контраста объекта. Центром квадрата ф с вершиной 2 = (ги г2) и стороной I будем считать точку с координатами (\_г1+1/2\, [г2+1/2\). В алгоритме организуется перебор квадратов 0 из семейства <3(7, Д)- Для классификации квадрата <3 с центром в точке а выполняются следующие операции:

1) для квадрата В(а, г) со стороной 2г + 1 и центром в а вычисляется

2) выбираются фрагменты Ргз,1<1<з, изображения в виде квадратов

со стороной 2г + 1, примыкающих к зоне интереса <2 со внешней стороны и расположенных на расстоянии, не меньшем 2г + 1 друг от друга;

3) вычисляются хрг3 = |-щ еге^г,- 1 < 3 <

4) если ха > хрТ} для светлого пятна (ха < хрг. для темного пятна), 1 < 3 < й, то квадрат <3 считается зоной интереса, иначе - квадратом без объекта.

Для исследования эффективности метода поиска зон интереса были проведены эксперименты с использованием локально однородных сцен с г = 1. Было получено, что увеличение числа й приводит к росту И{А). Разработанные программные средства позволяют рассчитать ЩА) и N(<3 \ А) по 5 и г для любой локально однородной сцены.

В пункте 2.2.2 приводится обобщение рассмотренного ранее метода пятна на векторный случай. Пусть хРг = ^ Eze.Fr хг~ оценка среднего значения тя\а фона. Квадрату <2 сопоставляется отображение /д, определенное на множестве всех изображений сцены при помощи равенства

Квадрат Q относится к зоне интереса, если Jq(x) = s, иначе квадрат Q считается пустым. Известно, что данное решающее правило классификации квадратов стремится при г —> -Ьоо и s +оо к байесовскому с нулевой вероятностью ошибки классификации.

Исходные данные алгоритма обобщенного метода пятна совпадают с параметрами скалярного варианта за исключением того, что добавляется число v скалярных компонент и не указывается знак контраста объекта. Для каждого квадрата Q со стороной I и центром в точке а выполняются следующие операции:

1) для квадрата В(а, г) со стороной 2г + 1 и центром в а вычисляется

2) аналогично п.2 алгоритма для скалярных сцен выбираются фрагменты Рг^ 1 <з < в изображения;

3) вычисляются хрг = ~ Eze.Fr хг и = ЕгеРг^1<3< в;

4) вычисляются расстояния (¿(ха,х^г) и ¿(хрг^хрг), 1 < ] < я;

5) если <1(х.а.хру) > ¿(хрТ^хрг), 1< ^ < в, то квадрат (¡> считается зоной интереса, иначе - квадратом без объекта.

Рис. 2 иллюстрирует зависимость частоты ЛГ(Л) пропуска зон интереса от отношения сигнал/шум к при значениях V = 1,2,3 для г = 1 и в = 10. Как и ожидалось, увеличение значения и снижает частоту пропуска зон интереса. При этом для меньших значений к увеличение V дает больший эффект.

■fq{x) = E^/^+o^Xa.xjcy) - d(xFr.,xFr), 1 <j<s.

1

zeS(a,r)

Сигмы/шум

Рис. 2. Влияние v на частоту пропуска зон интереса

Частота N(Q \ А) ложных тревог возрастает при увеличении v. Это связано с тем, что присутствие любого пятна хотя бы на одной скалярной компоненте классифицируемого квадрата приводит к отнесению квадрата к зоне интереса.

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

Далее в главе рассмотрен вариант метода поиска зон интереса, позволяющий сократить \Q(l, Л)| за счет увеличения величины шага Д. Его использование позволяет снизить N(A) по сравнению с рассмотренным ранее методом. Однако N{Q \ А) при этом значительно возрастает.

В пункте 2.3 анализируются результаты поиска зон интереса на квазиреальных сценах. На таких сценах, как правило, присутствует большое число различных пятен, не являющихся объектами. Поэтому использование нескольких скалярных компонент может приводить к росту N(Q\ А).

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

На основании теоретических результатов разработаны численные методы и программные средства, обеспечивающие поиск зон интереса на локально однородных сценах. Они позволяют для известной сцены (объектов и фона) вычислить N(A) и N(Q\A), а также оценить вероятность ошибки при поиске зон интереса, если известны априорные вероятности появления зон интереса.

Третья глава посвящена разработке последовательных численных методов и программных средств сегментации зон интереса и исследованию их

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

В пункте 3.2 рассматриваются обобщенные на векторный случай методы сегментации квантилей и мод. Пусть площадь объекта известна и равна И, Ха = |в(а,г)| 6 ^ ~ оценка среднего значения т.4 объекта,

Хг = |в(г,г)| ХлеВ(г,г) 2, е <э\ А и Хрг = щщ ^е^г(д) Ъ - оценки среднего значения т^ фона. Если упорядочить «¿(хг,х^г), Рг{0>) по возрас-

танию, то при достаточно большом радиусе сглаживания г на |А| последних местах будут находиться расстояния ¿(ха,х^г), а € Л, соответствующие пикселям объекта. Данный метод сегментации является обобщением известного метода квантилей.

Так же легко обобщается и широкоизвестный метод мод. Пусть снова а е А и г е <5 \ А. Если распределения случайных величин ¿(ха,5сРг) и

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

¿(хч, х^г) = 1А(д)с1(ха, хГг) + хГг).

Предложена реализация методов в виде алгоритмов. Для векторного метода квантилей входными параметрами алгоритма являются изображениех<э зоны интереса, число скалярных компонент и, радиус г сглаживания, ширина /г расширения границы Гг^ и площадь \А\ объекта. Алгоритм состоит из следующих этапов:

1) строится сглаженное с радиусом г изображение х<э сцены в зоне интереса <5 со значениями пикселей в виде х2 = |в(г>г)г^| Etss(z,I•)nQ х4, г € <3;

2) строится расширение границы .Рт-д путем включения в выборку, кроме обязательных граничных пикселей, тех, которые не принадлежат зоне интереса, но находятся от нее на расстоянии, меньшем Н масштабных единиц;

3) вычисляется среднее арифметическое х^г = Ste.Fr ** по расширению границы Рть шириной /г;

4) для каждого пикселя изображения хд вычисляются расстояния Л2 = <1(хх,5срг), % € <5 от вектора средних по окрестности каждого пикселя сцены х2 до вектора средних по границе и их кратности 0 < г < |/|, где |/| - множество различных значений расстояний Л2;

5) вычисляются суммы (¿'¿)1<<<|/| вида Б, = Х^Т*

6) определяется пороговое расстояние Ао:

_ Г V 5< - \А\ < И-Ян Ло_.\г + 1, 54-|А|.> \A\-Sm'

7) пиксели зоны интереса, для которых А2 > Ао относятся к объекту, другие - к фону.

Алгоритм сегментации методом мод имеет следующие входные параметры: изображение Хд зоны интереса, число и скалярных компонент, радиус г сглаживания и ширина к границы. Этапы 1-4 алгоритма совпадают с первыми четырьмя этапами алгоритма метода квантилей. Кратности к, 0 < г < |/| расстояний удобно рассматривать в виде гистограммы, которая отображает зависимость кратности расстояний от их значений.

5) устанавливается начальный радиус сглаживания гистограммы р = 1;

6) гистограмма кратности расстояний сглаживается с радиусом р:

7) определяется множество индексов М максимумов к

М = {г е [1, |7| - 1] : кг-д-1 < к-д = • • • = к = ■ • • = к+д > £г+9+1}и {О : ко = к = ■ ■ ■ = к{ > к+г}и

{г € [1, \1\] : к-1 < к = к+1 =■■•• = кщ-у}' 9 > 0,9 € И;

8) если \М\ > 2, то увеличиваем радиус сглаживания р =р + 1 и возвращаемся к шагу 4 алгоритма;

9) если \М\ <2, то порог сегментации не может быть найден, завершаем выполнение алгоритма;

10) определяется множество индексов М минимумов к

М = {г е [1, |/| - 1] : к-д-1 > к-д = • • • = к = ■ • • = к+д < к+д+1 }и

{О : ко = к = • • • = к < к+г}1> {г б [1, |1|] : к-1 > к = к+1 = • ■ • = кщ-1}, Я > 0,я €

11) вычисляется порог сегментации Ао: находится такое Ао £ М, которое удовлетворяет неравенству тгпМ < Ао < тахМ.

12) пиксели х2, ъ € <3, для которых Аг > Ао, относятся к объекту, остальные - к фону.

Была исследована зависимость эффективности рассмотренных алгоритмов от г и й на сценах различной сложности. Для этого была проведена сегментация в 28-ми зонах интереса с г = 1 и вычислены относительные частоты ошибок классификации по всем зонам интереса. Как и ожидалось, относительная частота п(<3) ошибки классификации для обоих алгоритмов снижается как при увеличении значения отношения сигнал-шум к, так и при увеличении значения и.

Для исследования влияния объема выборок на результаты сегментации были определены зависимости п(А), п(<3 \ А) и п{С2) от к при различных

значениях радиуса г сглаживания и ширины к границы. В качестве примера на рис. 3 представлены зависимости п(А) и п(СЦ\А) от значений к при и = 3, которые отражают снижение относительных частот ошибок при увеличении радиуса г сглаживания. Точки пересечения графиками оси ординат при А: = О определяются значениями п{А) = 1- |§ип(<2\А) = |^|. Полученные для

Рис. 3. Вероятности ошибок классификации пикселей объекта (слева) и фона (справа) в методе квантилей {и = 3)

различных к значения п(А) и п(<2\А) показывают, что при к < 1 увеличение радиуса сглаживания г уменьшает п{А) и п{(2 \ А), а при к > 1 лучше использовать минимальный радиус сглаживания. Это объясняется влиянием пикселей на границе объекта и фона.

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

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

1) аналогично п.2 алгоритмов классификации квадратов при поиске зон интереса, выбираются фрагменты Рг,-, 1 < з < в, границы; ^

2) вычисляются средние х/> = щщ ПхеРг,и = ^-игт,

1 < з < «;

3) для каждого пикселя х2, вычисляется среднее

по окрестности с центром в точке ъ и радиусом г.

4) если й(х2,хГг) > 1 < 3 < а, то пиксель х2 относится к

объекту, в противном случае - к фону;

5) все пиксели найденных объектов, отстоящие от фона на расстоянии не более г масштабных единиц, относятся к фону.

По теории применяемое в п.4 алгоритма решающее правило стремится при г +оо и $ +оо к байесовскому. На практике увеличение числа б фрагментов границы, как и ожидалось, снижает п(С} \ А) и п(С2). Однако увеличение радиуса г сглаживания приводит к росту ошибок классификации пикселей фона, смежных с объектом, в связи с чем 7г(<3 \ А) и п(<2) повышаются. Также из-за влияния граничных пикселей п(<3 \ А) в большинстве случаев растет вместе с увеличением к.

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

Применимость теоретических результатов для решения прикладных задач определяется, главным образом, адекватностью математической модели реальной сцене. Для проверки адекватности в п.3.3 результаты сегментации модельных сцен сравниваются с результатами сегментации реальных сцен с похожими свойствами. Была проведена сегментация методом квантилей квазиреальной и локально однородной сцен с одинаковым отношением к сигнал/шум в зонах интереса. На рис. 4 представлены результаты сегментации в зависимости от величины к отношения сигнал/шум с использованием двух изображений.' Точками обозначены вероятности ошибки в отдельных экспериментах, а штриховой линией тенденция, соответствующие квазиреальной сцене. Для модельной сцены используются ромбы и сплошная линия.

0,2 -

5 * Ю 0,16 -

1 О л 0,12 -

§ X 0,08 -

о

ф ш 0,04 -у = С

у = 0,0707ё°хт'

онае"0^ Г —^

О 1 2 3 4 5 6 7 8 Сигнал/шум

Рис. 4. Адекватность модели реальной сцене в методе квантилей (¡/ = 2)

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

ними не превосходит 0,02. Проверка гипотез о равенстве вероятностей ошибок сегментации модельной и квазиреальной сцен с v - 1,2,3 показала, что для некоторых случаев расхождение не является значимым на уровне 0,05.

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

Четвертая глава посвящена описанию комплекса программ Image-Analyser, разработанного для экспериментального исследования алгоритмов поиска объектов, и программы InsulaVision для диагностики высоковольтных изоляторов по их инфракрасным изображениям. ImageAnalyser является многодокументным приложением, предназначенным для анализа изображений и поиска объектов. Он включает набор инструментов (подпрограмм) для моделирования изображений, предобработки, поиска зон интереса, сегментации, коррекции, вычисления значений признаков и некоторые другие. Его возможности обсуждаются в 4.1. Программное обеспечение написано на языке программирования С# в среде разработки Microsoft Visual Studio 2008.

Моделпр овяшс

Модепнрованпепо карте_

Моделирование без карты

Инструменты

Масштэвпрование

Шверпгрованпе

Контрастирование

Сглаживание

Стат. анализ

Пошк мнпнпрмя

Скалярные ! Методпягна хс

Метод пятна хл

Проверка гипотез

Векторные

Проверка шлете"!

Вычисление признаков

Гобаршные размеры

Мет од пятна хе

Метод пятна Xj I , j

Сегментация

Скалярные

Метод гаанпгл eft

Метод мод

Метод пятна

Байесовская

Векторные

Метод квантилей

Методпягна

Байесовская

По фону

Коррекция

Маркпроека

Пскчючение границы

Псключеннепо площади

Полнаякоррекцня

Слияние' разъединение

Корреидгя грашпньгс пикселе!!

Бинарное ннвд>И1рованг1е

Рис. 5. Структура комплекса программ ImageAnalyser

Программа ImageAnalyser состоит из ядра программы, модулей для ра-

14

боты с изображением и вспомогательных модулей. Модули для работы с изображениями представляют собой библиотеки DLL. Их структура приведена на рис. 5.

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

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

В последнем пункте главы описывается программное обеспечение Insula Vision. Как правило, высоковольтные изоляторы соединяют в гирлянды из 3 < п < 5 штук. Дефектные изоляторы нагреваются сильнее исправных, поэтому их средняя яркость на изображении выше.

Был предложен алгоритм диагностики изоляторов, состоящий из следующих укрупненных этапов:

1) сегментация изображения методом мод (рассмотренным в главе 3);

2) коррекция результатов сегментации для выделения проекции гирлянды изоляторов: разъединив пикселей и исключение ложных объектов;

3) разделение проекции гирлянды на фрагменты, соответствующие отдельным изоляторам;

4) выбор окрестностей на изображениях «чашек» изоляторов и вычисление в них среднего арифметического 5, и среднеквадратического отклонения 0"t, 1 < г < п, для каждого изолятора;

5) вычисление номера j = ar grain {-¿г}, 1 < i < п, самого холодного изолятора;

6) если для всех г, 1 < i < п, Xj — k<Tj < Si < Xj + kcrj, то гирлянда изоляторов считается исправной, иначе - дефектной.

При разработке программы InsulaVision использовались программные модули сегментации и коррекции комплекса программ ImageAnalyser, На рис. 6 приведен пример изображения дефектной гирлянды изоляторов с построенными для вычисления i; и 1 < г < гг., окрестностями.

Для оценки эффективности алгоритма были проведены эксперименты на выборках с исправными и дефектными изоляторами. 80% исправных изоляторов было классифицировано верно, относительная частота правильной классификации дефектных изоляторов составила 96%. Разработанная программа использовалась для проведения работ по диагностике высоковольтных изоляторов на Горьковской железной дороге. Это позволило повысить эффективность диагностики, снизив влияние человеческого фактора.

В пятой главе предлагаются параллельные алгоритмы и соответствующее программное обеспечение для решения задачи поиска объектов. В 5.1 обсуждаются различные архитектуры параллельных вычислительных систем и известные подходы к программированию для них (обмен сообщениями, потоки).

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

Для алгоритмов, рассмотренных в главах 2 и 3 работы, были разработаны параллельные варианты с использованием N процессорных элементов с различной архитектурой параллельной вычислительной системы. Для этого исходное изображение разделялось на N полос. Каждая полоса обрабатывалась выделенным для нее процессорным элементом, затем результаты объединялись. В 5.3-5.5 исследуется эффективность распараллеливания отдельных операций поиска объектов (сглаживания, поиска зон интереса и сегментации) в зависимости от выбранной архитектуры многопроцессорной вычислительной системы и подхода к программированию. С использованием результатов данного исследования были разработаны параллельный алгоритм и соответствующая программа для поиска объектов. Результаты работы параллельного алгоритма описаны в п.5.6 и приведены в таблице.

Результаты работы параллельного алгоритма поиска объектов

N 1 2 3 4

Ьц, с 49,86 32,75 25,00 21,75

5лг 1,00 1,52 1,99 2,29

В первой строке таблицы указано число N используемых процессорных элементов, во второй - время Ьц выполнения, а в третьей - ускорение = ^/Ьн алгоритма.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

7. Разработан комплекс программ для экспериментального исследования алгоритмов поиска объектов на векторных сценах.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В журналах, рекомендованных ВАК:

1. Фофанов В.Б., Демченко А.В., Кулеев Р.Ф. Дешифрирование многозональных изображений: методы и результаты // Оптический журнал. 2007. Т. 74. В. 3. С. 55-59.

2. Fofanov V.B., Kuleev R.F. A Generalization of Segmentation Methods of Quantiles and Modes to the Case of Several Images // Pattern Recognition and Image Analysis, '2008, Vol. 18, No. 4. P. 666-670.

3. Fofanov V.B., Kuleev R.F. An Approach to Estimation of Image Informativeness // Pattern Recognition and Image Analysis, 2009, Vol. 19, No. 3. P. 478-483.

В других изданиях:

4. Fofanov V.B., Kuleev R.F. Generalization of Segmentation Methods of Quantiles and Modes for the Case of Several Images // Proceedings of 8th International Conference «Pattern Recognition and Image Analysis: New Information Technologies», Vol. 2, Yoshkar-Ola, 2007. P. 114-117.

5. Fofanov V.B., Kuleev R.F. One Approach to Evaluation of Image Informativeness // Proceedings of 9th International Conference «Pattern Recognition and Image Analysis: New Information Technologies», Vol. 1, Nizhni Novgorod, 2008. P. 140-143.

6. Кулеев Р.Ф. Об эффективности распараллеливания некоторых алгоритмов дешифрирования изображений // Тезисы X международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (НРС-2010), Пермь, 2010. С. 135-138.

7. Фофанов В.Б., Кулеев Р.Ф. Сегментация зон интереса на основе случайного расстояния // Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки» (23-27 октября 2006 г.), том 2, часть 2. - М.: Изд-во механико-математического факультета МГУ, 2006. С.

8. Кулеев. Р. Ф. Об адекватности модели реальной сцене в задаче поиска объектов по векторным изображениям // Тезисы докладов XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.). Казань: Изд-во «Отечество». С. 118.

9. Алеев P.M., Зарипов Д.К., Кулеев Р.Ф. Аппаратно-программный комплекс дистанционной диагностики высоковольтных изоляторов // Материалы XVIII Всероссийской межвузовской научно-технической конференции «Электромеханические и внутрикамерные процессы в энергетических установках, струйная акустика и диагностика, приборы и методы контроля природной среды, веществ, материалов и изделий», Казань, 2006. С. 73-74.

Свидетельства о регистрации программы для ЭВМ:

10. Кулеев Р.Ф. Обобщенный метод сегментации квантилей - М.: ФГНУ «ЦИТиС» - № 50201000369 от 17.03.2010.

11. Кулеев Р.Ф. Параллельный метод поиска зон интереса на основе признака пятна - М.: ФГНУ «ЦИТиС» - № 50201000684 от 04.05.2010.

293-295.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Печ.л. 1,25. Усл. печ. л. 1,16. Уч.-изд. л. 1,0.

_1___Тираж 100. Заказ 0171.___

Типография Казанского государственного технического университета 420111, Казань, К. Маркса, 10.

61 12-5/1528

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

КУЛЕЕВ РАМИЛЬ ФУАТОВИЧ

МЕТОДЫ И АЛГОРИТМЫ МОДЕЛИРОВАНИЯ ВЕКТОРНЫХ ЛОКАЛЬНО ОДНОРОДНЫХ СЦЕН

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

На правах рукописи

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель: к.т.н., доцент, Фофанов В.Б.

Казань - 2012

Оглавление

Введение 4

1 Математическая модель задачи поиска объектов по векторным изображениям и связанные с ней вопросы 10

1.1 Предварительные соображения................................И

1.2 Модель сцены....................................................14

1.3 Постановка задачи..............................................23

1.4 Моделирование изображений сцен............................27

2 Методы поиска зон интереса 39

2.1 Исходные предпосылки........................................40

2.2 Локально однородные сцены..................................43

2.2.1 Скалярный случай......................................43

2.2.2 Векторный случай......................................54

2.3 Квазиреальные сцены..........................................63

2.4 Бернуллиевские сцены..........................................66

2.4.1 Скалярный случай......................................66

2.4.2 Векторный случай........ .................70

3 Методы сегментации зон интереса 76

3.1 Существующие подходы к сегментации векторных сцен . . 77

3.2 Локально однородные сцены.......................89

3.2.1 Обобщенные методы квантилей и мод................89

3.2.2 Обобщенный метод пятна....................103

3.3 Адекватность модели реальной сцене ............110

3.4 Влияние различных расстояний на результаты сегментации векторных сцен......................115

4 Комплекс программ для поиска объектов 124

4.1 Программа дешифрирования изображений 1т^еАпа1у8ег . 125

4.2 Интерфейс взаимодействия модулей 1т^еАпа1увег.....129

4.3 Поиск зон интереса.......................131

4.4 Сегментация .......1...................134

4.5 Диагностика состояния высоковольтных изоляторов .... 137

5 Параллельное программное обеспечение 141

5.1 Архитектуры и технологии разработки параллельного программного обеспечения .'.................142

5.2 Постановка задачи распараллеливания алгоритма.....145

5.3 Сглаживание . .........................150

5.4 Поиск зон интереса.......................154

5.5 Сегментация ..........................156

5.6 Поиск объектов.........................158

5.7 Зависимость производительности алгоритма от характеристик многопроцессорной системы...............159

Заключение 165

Список литературы 169

Введение

Актуальность работы. Довольно часто источником информации о реальном мире служит изображение. Извлечение нужных сведений из изображения называется, как известно, дешифрированием. По настоящее время основным способом дешифрирования остается визуальный, выполняемый заранее подготовленным специалистом. Однако визуальное дешифрирование имеет ряд существенных ограничений. В частности, для работы человека необходима система жизнеобеспечения. Результаты визуального дешифрирования являются принципиально субъективными. В некоторых случаях скорость поступления информации может превышать психофизические возможности восприятия человека. Одним из способов преодоления перечисленных ограничений является автоматизация дешифрирования изображений. Поэтому работы в этом направлении интенсивно ведутся с 60-х годов XX века во всех высокоразвитых странах. По данной тематике опубликовано большое количество работ, авторами которых являются К.К. Васильев, Ю.Г. Васин, Р. Вудс, Р. Гон-салес, А.Л. Горелик, И.Б. Гуревич, Р. Дуда, Н.Г. Загоруйко, В.Н. Козлов, Т. Кутс, У. Прэтт, Ю.П. Пытьев, Д. Розенфельд, В.В. Сергеев, К. Тейлор, Я.А. Фурман, П. Харт и другие. К сожалению, общей теории дешифрирования пока создать не удалось, несмотря на впечатляющие успехи до-

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

Очевидно, что для автоматизации необходимо теоретическое обоснование. В работах [1]-[3] предложена формализация задачи поиска объектов, состоящая из трех последовательных этапов: поиск зон интереса, сегментация и вычисление признаков. Сформулированы условия сходимости решающих правил к оптимальным, с вероятностью ошибки, равной нулю, когда объемы п выборок и их количество з стремятся к бесконечности [4, 5]. Однако на практике приходится работать с конечным числом выборок конечного объема и с объектами, имеющими конечные размеры. Поэтому возникает вопрос о зависимости результатов отп, яи влияния размеров объектов.

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

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

ны, полученных, например, в результате одновременной съемки сцены в различных спектральных диапазонах. Так как каждый пиксель таких изображений характеризуется вектором значений, то сами изображения в работе называются векторными. Кроме того, предполагается, что все пиксели каждого объекта имеют одинаковую среднюю яркость, которая отличается от средней яркости их окружения. Такие объекты впервые были рассмотрены в работах А. Розенфельда и названы пятнами [6].

Задачи исследования. В ходе работы над диссертацией были поставлены и решены следующие задачи.

1. Построение математической модели сцены.

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

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

4. Разработка комплекса программ для экспериментального исследования алгоритмов поиска объектов по векторным изображениям.

5. Исследование эффективности алгоритмов поиска объектов по векторным изображениям в зависимости от сложности сцены и параметров алгоритмов.

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

Научная новизна.

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

2. Разработаны численные методы моделирования изображений локально однородных сцен с заданными свойствами на основе бернуллиев-ских полей.

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

Методика исследований. Для решения поставленных задач используется аппарат теории вероятностей, математической статистики и теории случайных процессов. Программное обеспечение разработано на языке С# в среде Microsoft Visual Studio 2008.

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

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

Апробация работы. Результаты диссертационной работы докладывались на VIII и IX Международных конференциях «Pattern Recognition and Image Analysis: New Information Technologies» (г.Йошкар-Ола, 2007; г. Нижний Новгород, 2008), X Международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Пермь, 2010), IX Международной конференции «Интеллектуальные системы и компьютерные науки» (г. Москва, 2006), XV Международной конференции «Проблемы теоретической кибернетики» (г.Казань, 2008), а также ряде других научных конференций и семинаров.

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

Структура и объем диссертации. Диссертация состоит из Введения, пяти глав, Заключения и Списка литературы из 109 наименований. Объем диссертации составляет 18.5 страниц, включая 45 рисунков.

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

тель В.Б. Фофанов, к.т.н., без помощи и наставничества которого настоящая работа бы не появилась. Также большое спасибо за постоянный интерес к работе и поддержку бывшим коллегам A.B. Демченко и Р.Г. Сабирову, профессору кафедры экономической кибернетики В.Р. Фазы-лову. За консультации по работе с вычислительным кластером благодарен сотрудникам НИИММ имени Чеботарева при КФУ и аспирантам Института органической химии имени Бутлерова.

Глава 1

Математическая модель задачи поиска объектов по векторным изображениям и связанные с ней вопросы

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

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

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

1.1 Предварительные соображения

Задаче поиска объектов посвящено немало работ как российских, так и зарубежных авторов. Задача такого рода возникает в различных предметных областях. Особенно много работ, посвященных поиску объектов по аэрокосмическим изображениям [7]-[16], выделению проекций органов и обнаружению патологий по медицинским изображениям [17]-[29], поиску лиц [30]-[36] и другим проблемам [37]-[46]. Анализ работ показал, что большинство используемых алгоритмов поиска объектов можно отнести к одной из следующих групп:

1) алгоритмы, использующие шаблоны для объектов, которые необходимо обнаружить;

2) алгоритмы статистического распознавания образов, предусматривающие поиск объектов с учётом их конкретных характерных признаков;

3) алгоритмы технического зрения на основе моделей, с помощью ко-

торых сравниваются характерные признаки объектов с хранящимися в памяти ЭВМ моделями данного;

4) нейросетевые алгоритмы, предполагающие обучение на примерах искусственной нейронной сети, имитирующей структуру мозга человека.

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

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

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

тральных диапазонах. В таком случае для каждого пикселя измеряется вектор признаков, а набор изображений может рассматриваться как векторное отображение. Поэтому будем называть такой набор векторным изображением сцены. На сегодняшний день векторные изображения чаще всего получаются при съемках с космических аппаратов. Наиболее известными спутниками с установленной мультиспектральной аппаратурой являются NOAA, EOS, Terra, Aqua, LANDSAT, SPOT и Ресурс-01.

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

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

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

Таким образом, решение задачи поиска объ