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

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

Гончаров Александр Владимирович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МОДЕЛИ ЗНАКОВОГО ПРЕДСТАВЛЕНИЯ ДАННЫХ В ЗАДАЧАХ РАСПОЗНАВАНИЯ ОБРАЗОВ

Специальность 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ диссертация на соискание учёной степени кандидата технических наук

4843289

Таганрог 2010

4843289

Работа выполнена в Научно-конструкторском бюро вычислительных систем,

Таганрог

Научный руководитель: доктор физико-математических наук,

профессор Каркищенко Александр Николаевич, Научно-исследовательский институт информатизации, автоматизации и связи

Официальные оппоненты: доктор технических наук,

профессор Белявский Григорий Исаакович, Южный федеральный университет, Ростов-на-Дону

доктор технических наук, профессор Ковалев Сергей Михайлович, Ростовский государственный университет путей сообщения, Ростов-на-Дону

Ведущая организация: Вычислительный Центр Российской Академии наук

им. A.A. Дородницына, Москва.

Защита состоится «/£» /шесгёрл 2010 года в /V ч. 2_сз мин. на заседании Диссертационного совета Д212.208.21 Южного федерального университета по адресу: Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу: Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан /ч&а&ю^ 2010 года.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, Таганрог, пер. Некрасовский, 44, диссертационный совет, Д212.208.21.

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

Актуальность темы. Анализ изображений и распознавание образов — одно из наиболее динамично развивающихся направлений искусственного интеллекта. Интерес к данной области обусловлен, в первую очередь, высокой практической значимостью задач распознавания в различных сферах деятельности человека - в медицине (различные виды диагностики), в системах обеспечения безопасности (видео наблюдение, биометрическая идентификация), на производстве (контроль качества, автоматизированная сборка). Стремительное развитие аппаратных возможностей устройств извлечения, обработки, передачи и хранения информации требует постоянного совершенствования существующих и разработки новых методов анализа изображений и распознавания образов. При этом актуальным является построение систем информативных признаков, на основе которых производится распознавание, исследование устойчивости данных признаков к наличию шумов на изображении, и „ разработка методов их классификации.

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

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

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

детекции и идентификации лиц.

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

]) исследование свойств знакового представления изображений;

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

3) разработка методов классификации изображений, основанных на знаковом представлении;

4) разработка эффективных алгоритмов детекции и идентификации лиц;

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

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

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

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

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

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

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

Практическая ценность. Разработанные в рамках диссертационной работы методы и алгоритмы классификации знаковых представлений могут быть использованы при разработке систем распознавания образов и анализа изображений, комплексов видео наблюдения, систем контроля доступа и биометрической идентификации. В частности, алгоритмы детекции и идентификации лиц, построенные на основе разработанных алгоритмов классификации знаковых представлений, реализованы в виде динамически подключаемых программных модулей на языках С++ и Python для операционной системы GNU/Linux. Построенные алгоритмы обнаружения нечетких дубликатов изображений позволяют повысить качество представления результатов поиска в мультимедийных информационно-поисковых системах посредством объединения в группы схожих результатов, а также в разы сократить объем памяти, необходимой для хранения больших коллекций.

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

Апробация работы. Практические и теоретические результаты диссертации использованы в инициативном научно-исследовательском проекте РФФИ №08-07-00129 «Исследование многомасштабного знакового представления образов в задачах ана^ лиза биометрической информации при разработке систем информационной безопасности», в научно-исследовательском проекте «Поиск портретных изображений по содержанию» в рамках конкурса научных проектов Яндекс «Интернет-математика 2007», при разработке программного комплекса «Модуль интеллектуального анализа данных для систем видео наблюдения» для компании «Деветач».

Основные положения и результаты работы представлялись и обсуждались на международных и Всероссийских конференциях, в том числе на 14-й Всероссийской конференции «Математические методы распознавания образов» (Суздаль, 2009), 9-й международной конференции «Распознавание образов и анализ изображений» (Нижний Новгород, 2008), Российском семинаре по оценке методов информационного поиска (2007, 2008, 2009), конференции молодых ученых в рамках «Российской летней школы но информационному поиску» (Екатеринбург, 2007).

Публикации. По теме диссертации опубликовано 22 работы, из них 5 работ в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утвержденный ВАК.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех тематических глав, заключения, списка литературы и приложений. Общий объем основного текста — 148 страниц, включая 32 рисунка. Список литературы изложен на 16 страницах и содержит 105 наименования.

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

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

Первая глава посвящена введению знакового представления изображений и исследованию его свойств. Под изображением понимается вещественная функция /(ж), х = (х1,х2), заданная в узлах сетки Я = 1ц х 1М — {1,..., ДГ} х {1,..., А/}. Множество всех изображений /: П —» где К,+ = [0,+оо), далее обозначается через Т. Также рассматриваются множества изображений /: П —» [0,1] и /: П —> Ъ+, где Z+ — множество неотрицательных целых чисел.

Определение 1. Отношение т С(I х П называется знаковым представлением изображенья / 6 Т, если выполняются следующие условия: 1) если (ж,-,ж,) 6 г, то /(ж,) < 1(Х]); 3) если 6 т, (ж^-,ж,:) £ т, то /(ж,-) < /(ж^).

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

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

Знаковое представление будем называть полным, если оно содержит все пары точек из П. Если отношение г содержит только пары пикселей, находящиеся на расстоянии, не большем порога е, то г—оконное знаковое представление: г = {(х, У) € П2 I f (в)< / (у), |*i - î/i| + |*i - Уг\ < е}.

При е = 1 оконное знаковое представление является аналогом нсевдотроично-го представления изображения М.В. Харинова. Множество является аналогом понятия формы в морфологии Ю.П. Пытьева. Пусть Ф - множество отображений <р: R+ —» R+, моделирующих условия регистрации изображения. Под формой в морфологии Пытьева понимается множество изображений V/ = {у> о / | <р g Ф}. Если Ф — класс всех строго возрастающих отображений, то Vf g Tr.

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

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

Пусть /: П Z+ — изображение, h/(г) — |{а: е П | /(ж) = г}| — гистограмма изображения /, р(г) = Л/(г)/|П| — оценка вероятности появления пикселя со значением яркости г. Пусть А = {г 6 Z+ | Л/(г) > 0}, определим меру информативности изображений U{f) при помощи энтропии Шеннона следующим образом: U{f) = — c|fî| YlieA РОО 1пр(г), где с — некоторая константа, и множитель |Г2| определяет пропорциональный характер зависимости U(/) от количества пикселей.

Для знакового представления мера информативности U(г) и мера неопределенности Щт) вводятся исходя из следующих свойств. Связь функционалов U(t) и U{t) с U (/) задается с помощью известного в теории информации принципа, предложенного Дж. Клиром, согласно которому информативность и неопределенность связаны между собой и в сумме дают некоторую постоянную величину.

Свойство 1. Пусть Umal{r) = шах/е^г (/(/), тогда U(r) + Û{t) = (/„^(т).

Будем считать изображения /ь/г € Т эквивалентными если существует монотонно возрастающая биекция Т —> Т такая, что /2 = у ° Л-

Свойство 2. Эквивалентные изображения содержат одну и ту же информацию. Если отношение г связно то U(t) = 0 и U(t) = £/moi(T)- '

Свойство S. Пусть rj С тг, тогда U(t\) ^ U{ji).

Свойство 4■ Пусть GT = (fi, г) — граф знакового представления г 6 Т, и множества fii,..., — компоненты связности графа GT. Тогда J2T=i U (TnJ — U(т), где Tnt = т П Qk х Ojt — это сужение т на П*-

На основе свойств 1-4 доказываются следующие утверждения.

Утверждение 1. Пусть т Ç.T, в — т П г-1 и Iя — продолжение отношения г на множество V — {i>i,..., vn) классов эквивалентности, порожденных отношением 6, и р(г) = |v,|/]fil, тогда Um^(г) = -с|П| ]Г)"=1 Р(') 1пр(г).

Утверждение 2. Пусть т еТ, а 6 Eq (г U г-1), где Eq (г U r_i) — множество

б

всех отношений эквивалентности, которые включаются в отношение т U г тогда ¿У (г) ^ U(а).

Утверждение 2 позволяет построить верхнюю оценку меры неопределенности Ü>jp{T) = min I о € Eq (т U г"1) для вычисления.которой предложен алго-

ритм на основе процедуры построения множества по знаковому представлению.

Далее исследуется структура инвариантных преобразований изображений. Знаковое представление инвариантно относительно преобразования ip: Т —> Т, если для любых / € Т и g = <р(/) справедливо т(д) = т(/). Показывается, что знаковое представление г инвариантно относительно строго возрастающих функций

[0,1] -> [0,1], и множество Ф = {</> | rfo>(/)) = г (v»-1(/)) = V/ е Г} с операцией суперпозиции о (/) = Vi (<^2(/)), Vi, V2 € Ф. образует группу инвариантных преобразований. При действии группы Ф множество ТТ распадается на транзитивиые классы — орбиты Orb$(f) = {</'(/) I <Р £ Ф}> образующие разбиение множества Тг. Доказывается, что все NM -мерные орбиты имеют одинаковый jVAi-мерный объем: |ОгЬф(/)| = 1/(NM)\. На основе полученного результата строится оценка меры устойчивости знакового представления.

Под мерой устойчивости Qf(t) знакового представления относительно шума распределенного по закону F понимается вероятность Р{т(/+£) = т(/)}, где / 6 J-.

Будем считать, что изображению /: f,v х —< [0,1] соответствует jVM-мерный вектор / = (/ь... ,/nm) в единичном кубе [0, \\NM, компоненты £ независимы и распределены по закону F с нулевым математическим ожиданием, и F — абсолютно непрерывное распределение, плотность которого отлична от нуля в кубе [0, за исключением, возможно, множеств нулевой меры.

Пусть Orbi — такая орбита группы Ф, все точки которой характеризуются тождественной упорядочивающей перестановкой, т. е. 0 < Л < /г < ••-•■ < /да/ < 1-Соответствующее знаковое представление обозначим через Т\, таким образом, ТТх = Orbi. Пусть r/(J) — плотность вероятности появления изображения / из Orb). Тогда выражение для меры устойчивости знакового представления Т\ имеет вид:

Qv{n) = / rj(f)df V J dfx... dfNM.

Jörbi JOrb, ofl ■ ■ • OJNM

Предположим, что изображение / выбирается из Orbi по равномерному закону и

компоненты £ распределены по нормальному закону ЛА(0, а2). Следующая теорема

дает нижнюю оценку меры гауссовской устойчивости полного знакового представ-

2

ления. Пусть G(x) = Jl^^^dy — функция Лапласа.

Теорема 1. Пусть т — полное знаковое представление изображения /: In х Im —> [0,1]. Тогда мера гауссовской устойчивости Qg{t) при о < ^jj удовлетворяет неравенству: Qg(t) > (2G(3) - 1)'VM(1 - №Mo)nm.

Для меры устойчивости оконного знакового представления Qq(t) построена грубая оценка Q%(t) > Qg(t), которая доказывает, что оконное знаковое представление обладает большей устойчивостью. Справедливость оценок, полученных аналитиче-

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

Вторая глава посвящена разработке общих методов классификации знаковых представлений исходя из следующей постановки задачи. По обучающей выборке X = {(/i,«i)}iii> в которой каждому изображению fi € Т поставлен в соответствие номер класса щ £{!,'..., к}, необходимо построить правило классификации изображений, в соответствии с которым произвольное изображение / € Т можно отнести к одному из классов С1\,...,

Решение о принадлежности изображения некоторому классу принимается по некоторому множеству признаков П = (яу)(¡¿)еа, которое описывается антисимметричным и антирефлексивным отношением а, и признаки 7г/. = sgn(f(xj) — /(ж,)) рассчитываются для каждой пары пикселей (i,j) € а.

Если обучающая выборка X является представительной, по ней можно оценить вероятность pi появления класса Clf pi = \{(f,n) е X | п = 1} \/N. Аналогично можно получить оценку Р{яу = к | / 6 Cli} вероятности того, что признак Яу, / € Cli, примет значение к € {—1,0,1}. Из предположения независимости признаков построим оценку функции правдоподобия того, что изображение / принадлежит классу С If. Р (/ 6 Ck) = Pi П(у)бв Р {"о | С';}- При практической реализации целесообразно прологарифмировать функцию правдоподобия. Мы получим байесовский классификатор, если классификацию проводить по правилу. / 6 Clm, если m = argmax^i,...,* (\n{pi) + £(lj)ea ln (р {"{' I С2'}))-

Также рассматривается классификация знаковых представлений с помощью деревьев решений Бреймена (Breiman). процедура построения которых модифицирована с учетом специфики знаковых представлений.

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

Определение 2. Функцией расстояния на знаковых представлениях будем называть отображение d: !F х Т —> [0, оо), обладающее следующими свойствами: 1) d(f,g) = d{g,f) для всех f,g € Т; 2) d{fi,f2) = d{fhf3) если d{f2,f3) = 0 для всех /ь/г,}з б 3) каждому классу эквивалентности С/ — {<? 6 Т j d(f,g) — 0} соответствует некоторое знаковое представление изображения. Определение 3. Метрикой на знаковых представлениях называется функция-расстояния d: J- х f -» [0, оо), обладающая свойством: d(/b /2) + ¿¿(/г, /з) ^ d{fu /з) Лгя всеж /ь/2, /3 € JF.

Будем считать, что для каждого признака irfj можно указать его информативность, тогда в качестве значения расстояния d(f,g) можно выбрать количество информации, которое мы теряем, предполагая, что знаковые представления изображений / и g являются тождественными.

Пусть afg —.{(i,j) € а | Яу ф 7rfj}, и каждому подмножеству признаков А С П поставлено в соответствие значение информативности р(А) > 0, удовлетворяющее аксиомам неаддитивной меры: a) /i(0) = 0; б) р.(А) ^ /л{В), если А С В. Тогда функцию расстояния определим следующим образом: = ц{а/9).

Я

Утверждение 3. Функция ¿^ является метрикой на знаковых представлениях, определяемых системой признаков П, в том и только том случае, если:

1) ц(А) > 0 для всех А С П при |Л| > О;

2) ц(А) + (г(В) ^ р.{А и В) для всех ДВСП при ЛПВ = 0.

В простейшем случае можно считать, что информативность всех признаков одинаковая и ц(А) — \А\. В этом случае получим метрику Хэмминга: д) —

При анализе реальных коллекций изображений признаки можно считать случайными величинами, и для оценки их информативности можно, например, использовать энтропию Шеннона 5. Тогда меру информативности ц{А), ДСП, можно

определить как энтропию случайного вектора ("у)^- Если признаки е П являются независимыми, то А) = 5 1 и метрика на основе энтропии

Шеннона имеет вид: = - Ещ-1,о,1} = к) 1о2 Р(7Гч = к)-

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

Пусть функции р, д: П —♦ [ОД] — плотности распределения вероятностей на конечном множестве П. Тогда функционал Зк1(р,я) — ]0хеп 'п (р(х)/я(х))р(х) называется энтропией1 распределения р относительно распределения <?.

Пусть случайная величина п^01' описывает наблюдецие признака Яу, / € С1[. Тогда меру информативности /х^, учитывающую различия распределения признаков в классах .Р и <3, где ^ и С? один из классов С1т = Ц^п» 1! С1 = У, С/;.

можно задать с помощью функционалов Ц}\а(А) — Б^ь ({"у^д' -

Функции расстояния на основе относительной энтропии не являются метриками в общем случае. Если признаки в обоих классах Рив являются независимыми, то /(^с является аддитивной мерой на подмножествах П, и ¿рс является метрикой на знаковых представлениях: (1Р,с{/,д) = £(у)еа/,

Для классификации знаковых представлений на классы С1{, I = 1 необ-

ходимо определить функции расстояния и эталонные знаковые представления ¿¡, определяемые системой признаков = а^тах,;Р{7Гу = с | С^}. Правило классификации задается условием: / € С1т, если т = aгg ¿¡) -)- £;), где £/ — числовые параметры, позволяющие регулировать ошибки первого и второго рода.

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

Пусть изображению /: 1ц х 1м —» [0,1] соответствует оконное знаковое представление г = {((г1,л),(г2,^2)) | /(гь л) < /(¿г,¿г), (¿2,^) € 0(гип)}, = {(г,^— 1), (г — 1,7), (г + 1,^), (г,4-1)}, которое при программной реализации описывается матрицей знакового представления Т(г^,к) = н§п(/(0(г,;?')*) — f{i,j)), г € /л?, ^ е Гц, к = 1,...,10(»,Я1- Поскольку 1) = -ТЦ,] - 1,4) и Т(г, 2) = —Т(г — 1,^,3), всю информацию о знаковом представлении можно получить из матрицы Т, построенной по окрестности 0(г,]) = {(г + {1,3 + 1)}.

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

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

Пусть wi(i,j, к) — матрица значений информативности признаков T¡(i,j,k), и p¡(i,j,k,c) = P{Ti(i,j, к) = с} — оценка вероятности того, что признак T¡(i,j,k) примет значение с е {—1,0,1} на изображениях из класса Ch. Алгоритм обучения классификатора на основе функций расстояния состоит из следующих этапов:

1 построение матриц эталонных знаковых представлений T¡(i,j, fe);

2 оценка пороговых величин e¡.

3 оценка информативности признаков одним из способов:

• wi(i,j,k) = 1 (метрика Хэмминга);

• wt(i,j,k) = — J2l=-iPi(hj> к,с) InPí(¿ii. с) (метрика на основе энтропии Шеннона):

• wi{i,j,k) = i (lnpí(i,j,-\npi{i,j,k,c))pi(i, j,k,c) (метрика на основе относительной энтропии);

Изображение / S Clm, если m = arg min; (e¡ + T,(i,mTJ(i.j,k)JtTl(i,j,k) Mi J,*))-

Далее рассматривается задача детекции лиц на изображении, приводится обзор современных подходов к ее решению. В частности, проводится сравнительный анализ методов, основанных на анализе контурного изображения (J. Wang, Т. Tan и др.), анализе интенсивности и цвета (M. Reuvers, A. Albiol, L. Torres и др.), каскадной классификации на основе интегрального (P. Viola, M. Jones) и дифференциального (В. Fröba, С. Kiiblbeck) представлений изображения. Делается вывод о том, что рассмотренные методы слишком чувствительны к изменениям условий регистрации изображения, и для снижения ошибок детекции лиц необходимо применять дополнительные методы нормализации изображений.

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

Основные этапы алгоритма детекции лиц:

1 построение пирамиды изображения;

2 для каждого уровня пирамиды:

• построение матрицы знакового представления;

• сканирование матрицы знакового представления методом скользящего окна, классификация на классы «лицо» и «не лицо»;

3 агрегирование результатов детекции с различных уровней пирамиды (решение проблемы множественной детекции).

Алгоритм детекции лиц параметризуется алгоритмом классификации знаковых представлений, при этом вычислительная сложность алгоритма 0(NM), т. е. линейно зависит от количества пикселей на изображении.

Далее рассматривается задача идентификации лиц, и проводится анализ современных методов ее решения. Рассмотрены метод «собственных лиц» (eigenfaces),

предложенный-M. Turk и A. Pentland, в основе которого лежит метод главных компонент, а также основанный на нем метод «саморазделенных» изображений (Self Quotient Image, SQI), предложенный H. Wang, S. Li, Y. Wang и др. Основной недостаток данного подхода состоит в сильной чувствительности к изменениям условий освещения. В результате, по данному методу оказываются похожими лица, полученные при схожих условиях освещения, а не различные фотографии одного и того же человека, полученные в различных условиях.

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

Основные этапы алгоритма идентификации лиц:

1 индексирование коллекции изображений;

2 оценка информативности признаков;

3 для каждого изображения-запроса:

• детекция лица, построение матрицы знакового представления;

• вычисление расстояния до каждого элемента базы лиц;

4 возвращение нескольких наиболее близких изображений или идентификатора наиболее близкого изображения.

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

Основные этапы алгоритма поиска нечетких дубликатов:

1 индексирование базы изображений:

• построение пирамиды изображения (2-3 масштаба);

• построение знакового представления каждого уровня пирамиды;

2 разбиение базы изображений на большие группы: изображения с совпадающими знаковыми представлениями относятся к одному кластеру;

3 кластеризация каждой групиы на пересекающиеся кластеры.

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

Пусть X — тестовая выборка изображений. Обозначим Xt ç X подмножество изображений, соответствующих некоторому искомому образу q, а ХТ С X — подмножество изображений, найденных по запросу q. Тогда Я — \ХТ Л Xt\l\Xt\ — полнота, а Р — \ХГ П Xt\!\XT\ — точность поиска. В качестве единого показателя используются F-мера: F-, = (1+-у2)РН/{у2Р+ Я), где коэффициент 7 задает приоритет точности над полнотой.

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

В таблице 1 представлены результаты оценки качества предложенного алгоритлт детекции лиц на различных тестовых коллекциях, где — количество изображений в выборке, Л'/асе — количество лиц; — средний горизонтальный размер лица в пикселях (удвоенное расстояние между центрами зрачков).

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

Выборка N- N face Fsz Ош. 1 рода Ош. II рода Полнота Точность

ORL 400 400 64 7.50- ю-* 4.53 • 10'° 0.993 0.993

BioID 1521 1251 110 5.44- Ю-2 1.74 ■ Ю-4 0.946 0.730

Yale В 650 650 184 2.12 • ю-1 5.29 • Ю-5 0.788 0.772

Essex 7200 7200 76 6.25- ю-3 8.33 • 10"5 0.994 0.996

Яндекс-1 20000 553 24 4.88- ю-2 8.23 • Ю-3 0.951 0.025

Яндекс-2 6000 2786 46 7.00- ю-1 4.99 • Ю-6 0.300 0.642

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

Из графиков, приведенных на рисунках 1-2, видно, что разработанные алгоритмы идентификации лиц (Hamming28, Shannon28 и Relative28, где число 28 характеризует ширину и высоту изображения лица в пикселях), обеспечивают примерно одинаковые показатели качества, при это алгоритм на основе относительной энтропии обеспечивает более высокую точность при высоких значениях полноты.

Таблица 2. Результаты РОМИП 2008 и 2009 гг. по дорожке поиска, нечетких дубликатов в больших коллекциях изображений (макроусреднепие)

Алгоритм Ош. I рода Ош. I рода Полнота Точность Fio-мера

SR32 0.616 3.96- 10-ь 0.384 0.976 0.962

SR48 0.680 2.15- ю-6 0.320 0.980 0.960

MLSR 0.551 1.07- Ю-3 0.449 0.812 0.806

Jacobs 0.612 4.19- 10'4 0.388 0.929 0.917

ххххх-1 0.406 2.78- ю-4 0.594 0.569 0.569

ххххх-6 0.474 5.21- ю-5 0.526 0.884 0.878

ххххх-7 0.257 1.07- Ю-3 0.743 0.433 0.435

ххххх-8. í 0.431 1.97- Ю-4 0.569 0.721 0.719

ххххх-9 0.462 8.43- Ю-5 0.538 0.740 0.737

ххххх-10 0.649 5.88- ю-4 0.351 0.777 0.768

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

'РОМИП — Российский семинар по оценко методов информационного поиска, http://romip.tu.

0.1 0.2 0.3 0.4

Recall

с 0.6

I»

£ 0.4

о.з 0.2 0.1

•—• Hamming28

• Shannon28

» Relative28

► PCA20

» PCA+SQ120

»• Hamming28 »-« Shannon28 Relatlve2B >- ► PCA20

PCA+SQS20

Rank

Рис. 1. Результаты оценки качества идентификации лиц с боковой засветкой (база АЛ)

•—• Hammlng28

•f................. »-« Shannon26 -

4................. 4—4 Relative28 I

PCA20

1................. PCA+SQI20 |

20 30 40 50

Rank

•—a

•—■ Shannon28

» Relative28 »-* PCA20

*-» PCA+SQI20

Recall

Рис. 2. Результаты оценки качества идентификации лиц при боковом освещении на подмножестве №1 базы Yale В

лась одним экспертом методом общего пула на 526 группах дубликатов, содержащих 3765 изображений, (РОМИП-2008), и на 466 группах из 3378 изображений (РОМИП-2009). SR32 и SR48 — алгоритм на основе оконного знакового представления с метрикой Хемминга для изображений, приведенных к размеру 32 х 32 и 48 х 48 пикселей; MLSR — алгоритм на основе многоуровневого оконного знакового представления изображений; Jacobs — алгоритм Якобса, основанный на вейвлет-преобразовании изображений; ххххх-1 - ххххх-10 — алгоритмы других участников РОМИП.

Вычислительные эксперименты показали, что байесовский классификатор и деревья решений лучше подходят для задач с небольшим количеством классов и обучающими выборками, содержащими достаточно много представителей каждого из классов (например, для детекции лиц). Если количество классов велико (например, для идентификации лиц), и обучающая выборка содержит лишь несколько представителей каждого из классов, то классификаторы на основе метрик и функций расстояния более предпочтительны. Кроме того, метрика, основанная на относительной энтропии, дает значительно лучшие результаты распознавания, по сравнению с метрикой на основе энтропии Шеннона. С другой стороны, метрика Хэмминга и метрика на основе энтропии Шеннона приводят к приблизительно одинаковым результатам: на одних тестовых выборках можно отметить более качественное рас-

познавание одного из методов, а на других - нет.

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

Алгоритм детекции лиц реализован на языке С++ с использованием библиотек OpenCV, BOOST, OpenMP. Алгоритмы распознавания лиц, поиска нечетких дубликатов изображений, а также модуль статистической оценки показателей качества алгоритмов распознавания реализованы на языке Python с использованием библиотек и модулей OpenCV, Pylab, NumPy, LibXML 11 др. При программной реализации применен объектно-ориентированный подход, все разработанные алгоритмы реализованы в виде динамически подключаемых библиотек и модулей для операционной системы GNU/Linux.

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

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

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

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

3 на основе предложенных методов классификации разработаны общие алгоритмы классификации изображений и их модификации для решения задач распознавания лиц, которые позволяют повысить точность распознавания фронтальных лиц на 15%-50% по сравнению с современными аналогами.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ РАБОТЫ

Работы в изданиях из «Перечня ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утвержденного ВАК

1. Каркищенко А.Н., Гончаров A.B. Исследование устойчивости знакового представления изображений // Автоматика и телемеханика. №9. С. 57-69. 2010.

2. Броневич А.Г,, Гончаров A.B. Аксиоматический подход к измерению информативности знаковых представлений изображений // Известия РАН. Теория

и системы управления. №6. С. 206-218. 2010.

3. Гончаров A.B. Распознавание лиц на основе .многомасштабного знакового представления изображений // Цифровая обработка сигналов. №1. С. 10-13. 2010.

4. Гончаров A.B. Исследование свойств знакового представления изображений в задачах распознавания образов // Известия ЮФУ. Технические науки. Тематический выпуск «Актуальные проблемы математического моделирования». №8(97). С. 178-189. 2009.

5. Гончаров A.B., Каркищенко А.Н. Влияние освещенности иа качество распознав вания фронтальных лиц // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». №4(81). С. 82-92. 2008.

Материалы и тезисы конференций, статьи в сборниках

6. Каркищенко А.Н., Гончаров A.B. Геометрия знакового представления изображений и ее приложение к исследованию устойчивости к шумам // Международная конференция Интеллектуализация обработки информации (ИОИ-8), Кипр, г.Пафос, 17-23 октября 2010 г.: Сборник докладов. М.: МАКС Пресс. С. 335-339. 2010.

7. Броневич А.Г., Гончаров A.B. Функции расстояния для классификации знаковых представлений изображений // Международная конференция Интеллектуализация обработки информации (ИОИ-8), Кипр, г.Пафос, 17-23 октября 2010 г.: Сборник докладов. М.: МАКС Пресс. С. 299-303. 2010.

8. Броневич А.Г., Гончаров A.B. Знаковое представление изображений и его информативность // Математические методы распознавания образов: 14-я Всероссийская конференция. Суздаль, 21-26 сентября 2009 г. МАКС Пресс. С.. 309-312. 2009.

9. Гончаров A.B., Губарев В.В. Выделение характерных признаков лиц на цифровых изображениях с использованием знакового представления // Математические методы распознавания образов: 14-я Всероссийская конференция. Суздаль, 21-26 сентября 2009 г. МАКС Пресс. С. 325-328. 2009.

10. Мельниченко A.C., Гончаров A.B. ЛММИИ на РОМИП-2009: Методы поиска изображений по визуальному подобию и детекции нечетких дубликатов изображений // Российский семинар по оценке методов информационного поиска. Труды РОМИП'2009. СПб.: НУ ЦСИ, С. 108-121, 2009.

11. Goncharov A., Gubarev V. Comparison of high-level and low-level face recognition methods // Pattern recognition and image analysis: new information technologies (PRIA-9-2008), P. 178-181, 2008.

12. Goncharov A., Melnichenko A. Pseudometric approach to content based image retrieval and near duplicates detection // Российский семинар по Оценке Методов Информационного Поиска. Труды РОМИП 2007-2008, С. 120-134, 2008.

13. Гончаров A.B. О новом подходе к задаче детекции лиц на полутоновых изображениях // «Практика и перспективы развития партнерства в сфере высшей школы»: Материалы восьмого международного научно-практического семинара. Донецк. Том 3, С. 60-64. 2007.

14. Гончаров A.B. Применение матрицы изменения яркости в задаче распознавания образов // Материалы Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления». Таганрог: Изд-во ТТИ ЮФУ. С. 100-102. 2007.

15. Гончаров A.B. Поиск портретных изображений но графическому запросу // Тезисы Всероссийской научной школы-семинара студентов и аспирантов «Интеллектуализация информационного поиска, скантехнологии и электронные библиотеки». Таганрог: Изд-во ТТИ ЮФУ. С. 94-96. 2007.

16. Гончаров A.B. Детекция лиц на основе каскадной классификации // Вторая Международная конференция «Системный анализ и информационные технологии» САИТ-2007. 10-14 сентября 2007г. Обнинск. Труды конференции. В 2 т. Т. 1. М.: Изд-во ЛКИ, 2007. С. 204-206. 2007.

17. Гончаров A.B., Горбаиь A.C., Каркищенко А.Н., Лепский А Е. Поиск портретных изображений по содержанию // Интернет-математика 2007: Сборник работ участников конкурса. Екатеринбург. Изд-во Урал, ун-та. С. 56-64. 2007.

18. Гончаров A.B., Горбань A.C. Распознавание лиц на изображениях с низким разрешением // Труды российской конференции молодых ученых по информационному поиску в рамках RuSSIR 2007. Екатеринбург. С. 5-15. 2007.

19. Гончаров A.B. Детекция фронтальных лиц на полутоновых изображениях // Труды Международной научной конференции «Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий» Евпатория, Украина. С. 212-216. 2006.

20. Гончаров A.B. Решение проблемы множественной детекции в задаче обнаружения лиц // Тезисы докладов VIII Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления». Таганрог: Изд-во ТРТУ. С. 214-215. 2006.

21. Гончаров A.B. Исследование алгоритмов поиска изображений, основанных на вей влет-преобразовании // Тезисы докладов студенческой конференции РГУ «Неделя науки» механико-математического факультета. Ростов-на-Дону. С. 56 57. 2005.

22. Гончаров A.B. Алгоритмы содержательного поиска изображений, основанные на вейвлет-преобразовании // Тезисы докладов III Всероссийской научной конференции молодых ученых, аспирантов и студентов. Таганрог: Изд-во ТРТУ. С. 81-82. 2005.

Личный вклад автора в работах, опубликованных в соавторстве

[1,6] исследование свойств знакового представления, оценка меры F-устойчиво-сти, проведение вычислительных экспериментов; [2,8] метод восстановления изображений по знаковому представлению, свойства меры информативности и неопределенности знакового представления, проведение вычислительных экспериментов; ¡5] исследование свойств знакового представления изображений, проведение вычислительных экспериментов; [7] введение метрики на знаковых представлениях, классификация на основе функций расстояния, проведение вычислительных экспериментов; [9,11] метод локализации антропометрических признаков лица на основе знакового представления изображений; [10,12] алгоритмы обнаружения нечетких дубликатов в больших коллекциях изображений, основанные на знаковом представлении; [17,18] введение псевдометрики на изображениях, метод каскадной детекции лиц на основе матрицы изменения яркостей, метод идентификации лиц на изображениях с низким разрешением, основанный на матрице изменения яркостей.

Типография ТТИ ЮФУ. ГСП 17А: Таганрог, ул. Энгельса. 1. Заказ ираж 100 экз. ~~

Введение

1. Знаковое представление изображений и его свойства

1.1. Введение знакового представления изображений.

1.2. Исследование свойств знакового представления изображений

1.2.1. Восстановление множества изображений по знаковому представлению.

1.2.2. Информативность и неопределенность знакового представления

1.2.3. Структура множества инвариантных преобразований изображений.

1.3. Устойчивость знаковых представлений

1.3.1. Определение устойчивости знакового представления изображений.

1.3.2. Выражения для вычисления ^устойчивости полного знакового представления.

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

1.3.4. Устойчивость оконного знакового представления

1.3.5. Численная оценка устойчивости знакового представления

1.4. Выводы.

2. Методы классификации знаковых представлений изображений

2.1. Неметрические методы классификации.

2.1.1. Байесовский классификатор.

2.1.2. Деревья решений.

2.2. Метрические методы классификации.

2.2.1. Введение метрики на знаковых представлениях

2.2.2. Классификация знаковых представлений на основе функций расстояния.

2.2.3. Оценка ошибок классификации знаковых представлений изображений.

2.3. Выводы.

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

3.1. Алгоритмы классификации знаковых представлений

3.1.1. Построение знакового представления по изображению и вычисление расстояния.

3.1.2. Алгоритм классификации знаковых представлений на основе функции правдоподобия

3.1.3. Алгоритм классификации знаковых представлений на основе функций расстояния.

3.2. Детекция лиц.

3.2.1. Обзор современных методов детекции лиц.

3.2.2. Детекция лиц на основе знакового представления

3.3. Идентификация лиц.

3.3.1. Обзор современных-методов идентификации лиц

3.3.2. Распознавание лиц на основе алгоритмов классификации знаковых представлений.

3.3.3. Стратегии идентификации лиц.

3.4. Обнаружение нечетких дубликатов в больших коллекциях изображений.

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

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

3.5. Выводы.

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

4.1. Оценка качества алгоритмов и результаты экспериментов . 118 4.1.1. Методы статистической оценки показателей качества алгоритмов распознавания образов

4.1.2. Оценка показателей качества детекции лиц.

4.1.3. Оценка показателей качества распознавания лиц

4.1.4. Оценка качества поиска нечетких дубликатов

4.2. Экспериментальный комплекс программ

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

Среди задач распознавания образов и анализа изображений можно выделить в отдельный класс задачи, связанные с распознаванием лиц. Данное направление с каждым годом привлекает все большее внимание исследователей, о чем свидетельствуют данные о количестве публикаций по теме распознавания лиц (см. рис. 1), содержащихся в каталоге ScienceDirect1 — одной из ведущих научных библиотек, предлагающей публикации более чем из 2500 рецензируемых журналов и более 11000 книг.

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

1http://www.sciencedirect.com

18000 16000

14000 щ

11111111111|||1Ш

1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009

Рис. 1. Количество публикаций по теме распознавания лиц в каталоге ЗаепсеБпе^ с 1991 по 2009 гг. эффективным — на общедоступных тестовых коллекциях изображений построенные алгоритмы демонстрируют высокие показатели полноты и точности распознавания, которые сопоставимы с современными аналогами, и для некоторых задач превосходят современный уровень.

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

Интерес к задачам идентификации личности по фотографии лица возник достаточно давно, еще в конце XIX века в рамках развития методов криминалистики [100]. Первые подходы к идентификации лиц основывались на сопоставлении отношений расстояний между антропометрическими точками лица. Для их применения требовалось знать ракурс съемки (на практике использовались фотографии модели головы, сделанные для всех возможных ракурсов с заданным шагом по углу визирования по широте и долготе) и точной локализации антропометрических признаков.

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

Одно из первых упоминаний об алгоритме идентификации лиц, разработанного в СССР специально для ЭВМ и не требующего вмешательства человека, приводится в монографии B.C. Файна [104], опубликованной в 1970 году. В монографии рассматривается применение непрерывно-групповой теории, в том числе для идентификации лиц. Для формирования цифровых изображений использовалось устройство ввода, формирующее снимок 108 х 64 элементов (пикселей) при 64 градациях яркости. В качестве информативных признаков использовались координаты локальных экстремумов функции яркости изображения и модуля её градиента.

Большинство современных методов идентификации лиц [45, 26, 65, 39, 52, 13, 50] основаны на работе Matthew Turk и Alex Pentland [59], которые предложили для распознавания лиц метод, называемый "собственные лица" (Eigenfaces), основанный на методе главных компонент (Principal Component Analysis, РСА), известный также как преобразование Карунена-Лоэва (КагЬипеп-Ьое\ге). Суть данного метода заключается в проецьз^^^ вании вектора признаков из исходного пространства большой размернс^^

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

-Т к некоторому классу С/**, если С^*) = пш1»с?(/', С1А, где й — мет^ в пространстве Ф', а /' = Рг& f — проекция вектора признаков на, подпространство Ф'. Как отмечается многими исследователями (см. Не^^-р мер [50]), основным недостатком данного метода является сильная ствительность к изменениям условий регистрации изображения. Пт^-г^ д Достаточно объемных выборках минимальное расстояние в пространств^ соответствует полученным при схожих условиях освещения изображ^^^^ различных персон, а не изображениям одной и той же персоны.

Проблема влияния освещенности на качество идентификации яв^^.^^ общей для всех методов анализа изображений при работе с ФотогР^фи ми, полученными в естественных условиях. Поэтому важным напра^^ ем исследований в данной области является разработка методов, НаЯз^ене чувствительных к изменению условий освещения. Существующие оды можно условно разделить на два подхода. Первый подход заключается предварительной обработке изображения, например, при помощи ц0рМа лизации изображения посредством выравнивания гистограммы яРК;осте1" Второй подход представляется более перспективным и состоит в Гхерехо де от исходного изображения к специальному представлению, Уст°йчивом к изменениям условий освещенности. Примером могут служить РаздР1Чнь1 методы выделения краев на изображении (методы Собеля, Кенни, Превит-та). В работе В. Proba и С. Küblbeck [23] предлагается использовать направления поля градиентов функции яркости изображения для формирования информативных признаков в задаче детекции лиц.

Отметим, что выбор того или иного представления изображения является в большей степени экспериментальным, нежели теоретическим, поскольку на сегодняшний день нет общих моделей, позволяющих учитывать условия регистрации изображения в общем виде. Для задач распознавания лиц наиболее эффективными с точки зрения полноты и точности идентификации являются представление изображения в виде «саморазделенного» изображения (Self Quotient Image, SQI) [65], а также представление изображения при помощи локальных бинарных шаблонов (Local Binary Patterns, LBP) [1]. Данные методы позволяют существенно улучшить показатели качества распознавания лиц; тем не менее, в ряде случаев обеспечиваемый уровень не является удовлетворительным.

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

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

Одним из аналогов знакового представления является описание формы объекта с помощью цепного кода, предложенного впервые Фрименом

H. Freeman) [20]. Цепной код — это способ задания контура с помсь-^ ью последовательности смежных пикселей, т.е. (ж»)^, где двумерные торы Х{ имеют целочисленные координаты, причем если AXi — х-+\ г =

I, т), где г е {1,. -, N - 1}, то ¿, т е {-1, 0,1}. Поэтому в цепно^^ де положение следующего пикселя относительно предыдущего кодир*^^ парой чисел (1,т) или, что эквивалентно, их знаками.

Г.ТСГ СТГ» ТТГТЛГПЛГГ

Ошо

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

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

Учены из исходного изображения действием некоторой функции на заа^ яркости, называется «формой» изображения [75, 62]. В предлагаемо^ ходе рассматривается полное и оконное знаковые представления К/г х божество изображений, соответствующих полному знаковому представ гг

ХеНию, совпадает с понятием формы по Пытьеву в классе строго возрас^а^ преобразований яркости. Однако множество изображений, соответ-о

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

В монографии М.В. Харинова [105] разрабатывается и исследуетСя прии локально-изоморфного образов изображения. В изоморфном обр^ сохраменение псевдотроичиой системы счисления для построения изоморф изображения могут меняться значения яркости пикселей, но при этом няется исходные яркостные отношения порядка (больше/меньше/равно) между пикселями. В локально-изоморфном образе требуется сохранение яркостных отношений порядка только для смежных пикселей. В предлагаемом подходе полное знаковое представление соответствует изоморфному образу изображения, а оконное знаковое представление - локально изоморфному образу.

В монографии М.В. Болдина и соавторов [70] излагается непараметрический подход к анализу статистических данных, согласно которому выводы основываются не на самих данных, а на знаках определенных функций от них. Данный подход является, в некотором смысле, частным случаем анализа ранговых величин.

Якобсом (С. Jacobs) и соавторами [33] предложен подход к поиску изображений по визуальному подобию, основанный на вейвлет-преобразовании Результатом вейвлет-преобразования изображения является матрица коэффициентов такого же размера, как и само изображение, при этом в качестве признаков изображения используются знаки первых п наибольших по модулю коэффициентов вейвлет-преобразования, а также индексы этих коэффициентов в матрице вейвлет-преобразования.

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

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

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

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

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

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

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

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

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

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

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

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

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

1) исследование свойств знакового представления изображений;

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

3) разработка методов классификации изображений, основанных на знаковом представлении;

4) разработка эффективных алгоритмов детекции и идентификации лиц;

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

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

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

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

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

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

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

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

3.5. Выводы

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

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

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

Разработаны новые алгоритмы идентификации лиц, при этом рассмотрены как постановка задачи информационного поиска, так и постановка задачи биометрической идентификации личности.

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

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

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

4.1. Оценка качества алгоритмов и результаты экспериментов

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

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

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

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

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

Отметим, что большинство разработанных в рамках диссертационной работы методов распознавания так или иначе связаны с задачами машинного обучения. Для таких задач понятие качества алгоритма является комплексным и включает в себя такие характеристики алгоритма, как обобщающая способность и стабильность [76]. Обобщающая способность определяется как вероятность ошибки алгоритма, полученного в результате обучения, на некоторой, вообще говоря, неизвестной тестовой выборке. Алгоритм обучения называют стабильным, если небольшие изменения обучающей выборки, например добавление или удаление одного из объектов, приводят к незначительным изменениям параметров алгоритма классификации. Теоретическая оценка качества алгоритмов обучения и классификации является предметом многочисленных исследований [74, 76].

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

Пусть X = и Х^ — тестовая выборка, содержащая как объекты заданного класса Xt} так и элементы X/, не являющиеся объектами заданного класса, Хь П X/ — 0. Рассмотрим нулевую гипотезу Щ = {х е Х*}, состоящую в том, что мы наблюдаем объект заданного класса, и альтернативную гипотезу Н\ = {х G Xf}, состоящую в том, что мы наблюдаем объект из Xj. Тогда вероятность а = Р{Щ \х Е Xt} того, что мы ошибочно примем альтернативную гипотезу при наблюдении объекта заданного класса соответствует ошибке первого рода, а вероятность (3 = Р{Но | х Е X/} того, что мы ошибочно примем нулевую гипотезу, соответствует ошибке второго рода.

Ошибки первого и второго рода связаны между собой, и снижение ошибки первого рода приводит к росту ошибки второго рода, и наоборот. На практике, как правило, фиксируют приемлемый уровень ошибки первого рода и стараются минимизировать ошибку второго рода. Отметим, что точечные значения ошибок сами по себе плохо подходят для сравнения алгоритмов (например, какой из алгоритмов А и В лучше решает задачу, если а(А) = 0.1, (3(A) = 0.2, а а(В) = 0.2 и (3(B) = 0.1?), поэтому для сравнения алгоритмов между собой обычно используются графики зависимости ошибки второго рода от ошибки первого рода.

В задачах информационного поиска для оценки качества принято использовать показатели полноты и точности [102]. Обозначим через Xt подмножество элементов выборки X, релевантных заданному запросу, Xf = X\Xt — подмножество нерелевантных документов, a Xt — подмножество документов, найденных информационно-поисковой системой по заданному запросу. Тогда полнота (recall) и точность (precision) оцениваются следующим образом:

Таким образом, полнота поиска характеризует долю найденных документов среди всех релевантных документов, содержащихся в коллекции, а точrecall = xtnxt\ №1 precision = xtnxt\

Xt\ ность соответствует доле релевантных документов среди всех найденных системой документов. В качестве единого показателя, агрегирующего полноту и точность, принято использовать F-меру [102]: (1 + 72) • precision ■ recall 7 72 • precision + recall ' где коэффициент 7 задает приоритет точности над полнотой.

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

4.1.2. Оценка показателей качества детекции лиц

Оценка качества детекции лиц представляет собой сложную задачу, поскольку само понятие "корректной детекции" зависит от конкретного приложения, и различными исследователями трактуется по-разному. Для определения точности детекции лица на изображении часто используют координаты центров зрачков [44] как наиболее характерные точки лица. В [44] авторы рассматривают подход, основанный на измерении расстояния между центрами зрачков лица, найденного алгоритмом детекции лиц, и центрами зрачков на изображении, отмеченными экспертом вручную при разметке тестовой коллекции. Например, в [40] детекция лица считается корректной, если евклидово расстояние между центром обнаруженного и реального лица не превышает 30% от ширины реального лица, а ширина обнаруженного лица отличается от реальной ширины не более чем на 50%.

Рис. 4.1. Примеры детекции лица: А) содержит большую часть фона, В) охватывает лишь часть лица, С) содержит все лицо и учитывает наклон головы.

В [23] детекция считается корректной, если координаты центров зрачков и ширина лица определены с точностью до 30% от ширины реального лица. Во многих работах, посвященных проблеме детекции лиц, приводятся результаты экспериментов в терминах ошибок первого и второго рода, однако ничего не говорится о том, каким образом было подсчитано количество корректных детекций.

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

Пусть ^ = {(Д, Ек)}к=1 ~ множество изображений размером N х М, с каждым из которых ассоциировано множество лиц Ек = заданных координатами центра лица и шириной лица: ^ = у^ ио3)т. Отметим, что для некоторых к множество Ек может быть пустым, т. е. соответствующее изображение не содержит ни одного лица. Обозначим через Ёк множество лиц, найденных алгоритмом детекции на изображении тогда ошибку локализации лица £ € Ек можно определить следующим образом: О = у/(х - хУ + (у - Уу + (й - V))*

Детекцию можно рассматривать как корректную, если ошибка локализации не превосходит некоторого порога: ^ (при практической реализации будем полагать — 0.3 ). Введение нормировочного множителя необходимо, поскольку в тестовой коллекции изображений могут встречаться лица произвольного размера.

Будем считать, что детекция лица осуществляется путем сканирования изображения окном фиксированного размера, в результате чего анализируется К областей изображения. Тогда, с учетом введенных обозначений, количество лиц на изображении не найденных детектором лиц, соответствует мощности множества € Ек | тт^д, — > при этом количество лиц на изображении, очевидно, соответствует мощности множества Ек. Таким образом, по тестовой выборке .Р можно статистически оценить ошибку а как частоту ошибочного пропуска детектором лиц участков изображения, содержащих лица:

Ек=1^ Ек I Л > а =

Мощность множества £ Ёк | шт^^й^,^ > с/оШу| соответствует количеству областей на изображение Д, которые ошибочно классифицированы как лица. Разделив суммарное количество ложных срабатываний по всем изображениям тестовой выборки на общее количество проанализированных областей, получим частотную оценку ошибки второго рода:

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

Показатели полноты и точности обладают более простой интерпретацией и оцениваются аналогично ошибкам первого и второго рода по выборке изображений ^ = {(//с, следующим образом:

Полнота детекции соответствует доле найденных лиц среди всех лиц, содержащихся в тестовой выборке, а точность детекции отражает долю лиц, precision —

ELi №k\ среди всех результатов детекции. Таким образом, полнота и точность лучше подходят для оценки качества алгоритмов детекции лиц.

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

Заключение

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

В ходе диссертационного исследования получены следующие теоретические и прикладные результаты.

1. Проведено исследование свойств знакового представления изображений и его информативности:

• введены мера информативности и мера неопределенности знакового представления;

• предложен исчерпывающий способ восстановления изображений по знаковому представлению, а также способ построения наименее информативного изображения;

• описана группа инвариантных преобразований над изображениями, аналитически получено выражение объемной меры орбит, получаемых при действии элементов данной группы на изображения;

• описана структура множества изображений, соответствующих некоторому знаковому представлению, и показано, что данные множества представляют собой открытые многогранники;

• введено и исследовано понятие устойчивости знакового представления при воздействии статистически независимого аддитивного шума;

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

• введены понятия функции расстояния и метрики на знаковых представлениях;

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

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

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

• разработаны алгоритмы детекции лиц;

• разработаны алгоритмы идентификации лиц;

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

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

• рассмотрена проблема оценки качества алгоритмов распознавания образов, основные показатели качества и способы их статистической оценки по тестовой выборке;

• на основе объектно-ориентированного подхода разработаны программные модули, предназначенные для решения рассмотренных задач;

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

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

1. Ahonen, T. Face recognition with local binary patterns / T. Ahonen, A. Hadid, M. Pietikainen // ECCV 2004 Proceedings. — Lecture Notes in Computer Science 3021. — Springer, 2004. — Pp. 469-481.

2. Ballard, D.H. Generalizing the hough transform to detect arbitrary shapes / D.H. Ballard // Pattern recognition. — 1981. — Vol. 13, no. 2. — Pp. 111-122.

3. Bao, P. Canny edge detection enhancement by scale multiplication / P. Bao, L. Zhang, X. Wu // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005. - Vol. 8. - Pp. 1485-1490.

4. Bradski, G.R. Learning OpenCV: Computer vision with the OpenCV library / G.R. Bradski, A. Kaehler. O'Reilly Media, 2008.

5. Canny, J. A computational approach to edge detection / J. Canny // IEEE Trans. Pattern Analysis and Machine Intelligence. — 1986. —• Vol. 8. Pp. 679—714.

6. Classification and regression trees / L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone. — Wadsworth L Brooks/Cole Advanced Books & Software, 1984.

7. Duda, R.O. Pattern classification / R.O. Duda, P.E. Hart, D.G. Stork. — Wiley-Interscience, 2001.

8. Escolano, F. Information Theory in Computer Vision and Pattern Recognition / F. Escolano, P. Suau, B. Bonev. — Springer Verlag, 2009.

9. Face Recognition / Ed. by K. Delac, M. Grgic. — I-TECH Education and Publishing, 2007.

10. Face recognition: A literature survey / W. Zhao, R. Chellappa, P.J. Phillips, A. Rosenfeld // ACM Computing Surveys (CSUR).— 2003. Vol. 35, no. 4. - Pp. 399-458.

11. The feret database and evaluation procedure for face-recognition algorithms / P.J. Phillips, H. Wechsler, J. Huang, P.J. Rauss // Image and Vision Computing. — 1998. — Vol. 16, no. 5. — Pp. 295-306.

12. The feret evaluation methodology for face-recognition algorithms / P.J. Phillips, H. Moon, S.A. Rizvi, P.J. Rauss // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2000. — Vol. 22, no. 10. — Pp. 1090-1104.

13. Filtering image spam with near-duplicate detection / Z. Wang, W. Josephson, Q. Lv et al. //In Proceedings of the Fourth Conference on Email and AntiSpam. — 2007.

14. Freeman, H. Computer processing of line-drawing images / H. Freeman // ACM Computing Surveys (CSUR). 1974. — Vol. 6, no. 1. - Pp. 57-97.

15. Freund, Y. A decision-theoretic generalization of on-line learning and an application to boosting / Y. Freund, R.E. Schapire // Journal of Computer and System Sciences. — 1997. — Vol. 55, no. 1. — Pp. 119-139.

16. Froba, B. Audio- and Video-Based Biometric Person Authentication /

17. B. Froba, C. Kiiblbeck. — Springer Berlin / Heidelberg, 2001.— Vol. 2091/2001 of Lecture Notes m Computer Science. — Pp. 78-83.

18. Frvt 2006 and ice 2006 large-scale results: Tech. rep. / J.P. Phillips, T.W. Scruggs, A.J. O'toole et al.: National Institute of Standards and Technology, 2007. — March.

19. Garcia, C. Face detection in color images using wavelet packet analysis /

20. C. Garcia, G. Zikos, G. Tziritas // ICMCS Proceedings.- Vol. 1.1999. — Pp. 703-708. citeseer.ist.psu.edu/614657.html.

21. Georghiades, A.S. From few to many: Illumination cone models for face recognition under variable lighting and pose / A.S. Georghiades, P.N. Belhumeur, D.J. Kriegman // IEEE Trans. Pattern Anal. Mach. Intelligence. 2001. - Vol. 23, no. 6. - Pp. 643-660.

22. Goncharov, A. Comparison of high-level and low-level face recognition methods / A. Goncharov, V. Gubarev // Pattern recognition and image analysis: new information technologies (PRIA-9-2008). — Vol. 1. — 2008.- Pp. 178-181.

23. Grother, P. Face recognition vendor test 2002 performance metrics / P. Grother, R.J. Micheals, P.J. Phillips // Proceedings 4th International Conference on Audio Visual Based Person Authentication. — Springer, 2003.-Pp. 937-945.

24. Grother, P.J. Report on the evaluation of 2d still-image face recognition algorithms: NIST Interagency Report 7709 / P.J. Grother, G.W. Quinn, P.J. Phillips: National Institute of Standards and Technology, 2010.— June 22.

25. Jacobs, C.E. Fast multiresolution image querying / C.E. Jacobs, A. Finkelstein, D.H. Salesin // Computer Graphics. — 1995. — Vol. 29, no. Annual Conference Series. — Pp. 277-286. citeseer.ist.psu.edu/396588.html.

26. Jesorsky, O. Robust face detection using the hausdorff distance / O. Jesorsky, K. Kirchberg, R. Frischholz // Proceedings of the Third International Conference on Audio- and Video-Based Biometric Person Authentication. — 2001. Pp. 90-95.

27. Klir, George J. Uncertainty and Information. Foundations of Generalized Information Theory / George J. Klir. — Wiley-Interscience, 2006.

28. Koschan, A. A comparative study on color edge detection / A. Koschan // In Proceedings of the 2nd Asian Conference on Computer Vision. — Vol. 3. 1995. - Pp. 574-578.

29. Kuncheva, L.I. Combining pattern classifiers: methods and algorithms / L.I. Kuncheva. — Wiley-Interscience, 2004.

30. Lee, K. C. Acquiring linear subspaces for face recognition under variable lighting / K.C. Lee, J. Ho, D. Kriegman // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2005. — Vol. 27, no. 5. — Pp. 684698.

31. Lindeberg, T. Edge detection and ridge detection with automatic scale selection / T. Lindeberg // International Journal of Computer Vision. — 1998.- Vol. 30, no. 2.- Pp. 117-154.

32. Liu, C. Gabor-based kernel pea with fractional power polynomial models for face recognition / C. Liu et al. // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2004. — Vol. 26, no. 5. — Pp. 572581.

33. Martinez, A. M. The AR face Database. CVC technical report: CVC Technical Report 24 / A. M. Martinez, R. Benavente: The Purdue University, USA, 1998.

34. Moon, H. Computational and performance aspects of pea-based face-recognition algorithms / H. Moon, Jonathon P. Phillips // Perception. — 2001. Vol. 30. - Pp. 303-321.

35. Overview of the face recognition grand challenge / P. Phillips, P. Flynn, T. Scruggs et al. // IEEE Computer Society Conference on Computer Vision and Pattern Recognition / Citeseer. — Vol. 1. — 2005. — P. 947.

36. Phillips, P. Face recognition grand challenge / P. Phillips // Biometric Consortium Conference. — 2004.

37. Pratt, W.K. Digital Image Processing / W.K. Pratt. — Wiley, 1978.155

38. Romdhani, S. A mult-iview non-linear active shape model using kernel pea / S. Romdhani, S. Gong, A. Psarrou // 10th British Machine Vision Conference. Vol. 2. — Nottingham: BMVA Press, 1999. — Pp. 483-492.

39. Samaria, F. Parameterisation of a stochastic model for human face identification / F. Samaria, A. Harter // IEEE Workshop on Applications of Computer Vision.— Sarasota (Florida): 1994.— December, citeseer.ist.psu.edu/samaria94parameterisation.html.

40. Saradha, A. A hybrid feature extraction approach for face recognition systems / A. Saradha, S. Annadurai // International Journal on Graphics, Vision and Image Processing. — 2005. — May. — Vol. 5. — Pp. 23-30.

41. Schapire, R.E. The boosting approach to machine learning: An overview / R.E. Schapire // MSRI Workshop on Nonlinear Estimation and Classification. Springer Verlag, 2003. - Pp. 149-172.

42. Seo, N. Tutorial: Opencv haartraining (rapid object detection with a cascade of boosted classifiers based on haar-like features). — http: / / note.sonots.com/SciSoftware/haartraining.html.http://note.sonots.com/SciSoftware/haartraining.html.

43. Shih, F. Y. Automatic extraction of head and face boundaries and facial features / F. Y. Shih, C. Chuang // Information Computer Graphics Science. 2004. - Vol. 158, no. 1. - Pp. 117-130.

44. Reuvers, Martijn. A smart camera for face recognition. citeseer.ist.psu.edu/644244.html.

45. Spacek, L. Collection of facial images. — http: //cswww.essex.ac.uk/mv / allfaces / index.html.

46. Stark, J.A. Adaptive image contrast enhancement using generalizations of histogram equalization / J.A. Stark // IEEE Transactions on Image Processing. 2000. — Vol. 9, no. 5. - Pp. 889-896.

47. Turk, M. Eigenfaces for recognition / M. Turk, A. Pentland // Journal of Cognitive Neuroscience. — 1991. — Vol. 3, no. 1. — Pp. 71-86.

48. Viola, P. Robust real-time face detection / P. Viola, M Jones // International Journal of Computer Vision. — 2004. — Vol. 57, no. 2. — Pp. 137-154.

49. Viola, P. Robust real-time face detection / P. Viola, M. Jones // International Journal of Computer Vision. — 2004. — Vol. 57, no. 2. — Pp. 137-154.

50. Vizil'ter, Yu.V. Projective morphoogies and their application in structural analysis of digital images / Yu.V. Vizil'ter, S.Yu. Zheltov // Journal of Computer and Systems Sciences International. — 2008. — Vol. 47, no. 6. Pp. 944-958.

51. Voorhees, E.M. Overview of tree 2003 / E.M. Voorhees // Text Retrieval Conference. NIST / Citeseer. 2003.

52. Walley, P. Statistical reasoning with imprecise probabilities / P. Walley. — London: Chapman and Hall, 1991.

53. Wang, H. Face recognition under varying lighting conditions using self quotient image / H. Wang, S.Z. Li, Y. Wang // Proc. IEEE Int. Conf. Automatic Face and Gesture Recognition.— IEEE Computer Society, 2004. Pp. 819-824.

54. Wang, J. A new face detection method based on shape information / J. Wang, T. Tan // Pattern Recogn. Lett. — 2000. — Vol. 21, no. 6-7.— Pp. 463-471.

55. Weber, M. Frontal face dataset. — http://www.vision.caltech.edu/html-files/archive.html. — 1999.

56. Xu, L. A new curve detection method: Randomized Hough transform(RHT) / L. Xu, E. Oja, P. Kultanen // Pattern Recognition Letters. 1990. - Vol. 11, no. 5. - Pp. 331-338.

57. Болдин, M. В. Знаковый статистический анализ линейных моделей / М. В. Болдин, Г. И. Симонова, Ю. Н. Тюрин; Под ред. Е.Ю. Ходан. — Наука. Физматлит, 1997. — С. 288.

58. Броневич, А.Г. Аксиоматический подход к измерению информативности знаковых представлений изображений / А.Г. Броневич, A.B. Гончаров // Известия РАН. Теория и системы управления. — 2010. Т. 6. - С. 206-218.

59. Вапник, В.Н. Теория распознавания образов / В.Н. Вапник, А.Я. Червоненкис. — М.: Наука, 1974.

60. Визильтер, Ю.В. Обобщенная проективная морфология / Ю.В. Ви-зильтер // Компьютерная оптика. — 2008. — Т. 32, Ш 4. — С. 384-399.

61. Воронцов, К. В. Математические вопросы кибернетики / К. В. Воронцов / Под ред. О.Б. Лупанов. — М.: Физматлит, 2004.— Т. 13.— С. 5-36.

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

63. Гончаров, A.B. Исследование алгоритмов поиска изображений, основанных на вейвлет-преобразовании / A.B. Гончаров // Тезисы докладов студенческой конференции РГУ "Неделя науки" механико-математического факультета. — 2005. — С. 91-92.

64. Гончаров, A.B. Детекция лиц на основе каскадной классификации / A.B. Гончаров // «Системный анализ и информационные технологии» САИТ-2007. ЛКИ, 2007. - С. 204-206.

65. Гончаров, A.B. Применение матрицы изменения яркости в задаче распознавания образов / A.B. Гончаров // Материалы Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления». ТТИ ЮФУ, 2007. - С. 100-102.

66. Гончаров, A.B. Распознавание лиц на основе многомасштабного знакового представления изображений / A.B. Гончаров // Цифровая обработка сигналов. — 2010. — Т. 1. — С. 10-13.

67. Гончаров, A.B. Распознавание лиц на изображениях с низким разрешением /A.B. Гончаров, A.C. Горбань // Труды российской конференции молодых ученых по информационному поиску в рамках RuSSIR 2007. 2007. - С. 5-12.

68. Гончаров, A.B. Влияние освещенности на качество распознавания фронтальных лиц / A.B. Гончаров, А.Н. Каркищенко // Известия ЮФУ. Технические науки. Тематический выпуск "Интеллектуальные САПР". 2008. - Т. 4(81). - С. 82-92.

69. Каркищенко, А.Н. Исследование устойчивости знакового представления изображений /А.Н. Каркищенко, A.B. Гончаров // Автоматика ' и телемеханика. — 2010. — Т. 9. — С. 57-69.

70. Каркищенко, А.Н. Геометрия знакового представления изображений