Разработка и исследование модели знакового представления данных в задачах распознавания образов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Гончаров, Александр Владимирович

• Гончаров, Александр Владимирович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Гончаров, Александр Владимирович

Введение

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. Разработан комплекс программ для исследования алгоритмов детекции и идентификации лиц, а также обнаружения нечетких дубликатов в больших коллекциях изображений:

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Гончаров, Александр Владимирович, 2010 год

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. Каркищенко, А.Н. Геометрия знакового представления изображений