Автореферат (Разработка метода направленного перебора альтернатив в задачах классификации объектов на основе теоретико-информационного подхода), страница 2

При этом предложенный метод может быть использован как на основе существующих информационных систем, так и путемвключения в них вспомогательных блоков подготовки данных в режиме обученияи их обработки в режиме распознавания. Достигаемый эффект – сокращение объема и времени вычислений – главное с точки зрения практики качество метода.Полученные в диссертации результаты использованы в отчете по проектуНФ ГУ-ВШЭ №09-03 от 04.06.2009 «Разработка информационной системы дляавтоматической группировки и распознавания фотографий лиц методом направленного перебора альтернатив на основе принципа минимума информационногорассогласования». Разработанная в рамках этого проекта «Автоматизированнаясистема распознавания людей по фотографиям лиц» зарегистрирована в государственном реестре программ для ЭВМ под №2009616508.

Эта система использована в качестве прототипа при разработке системы биометрической идентификациив отделе исследовательских и перспективных проектов ООО «Теком». Результаты6диссертационной работы внедрены в учебный процесс НФ ГУ-ВШЭ по направлению подготовки бакалавров «Бизнес-информатика» (080700.62).Апробация диссертации. Основные результаты работы докладывались на IXМеждународной научно-технической конференции «Интеллектуальные системы»в рамках Международного конгресса по информационным технологиям (Дивноморск, ТТИ ЮФУ, 2009), на XVI Международной научно-технической конференции «Информационные системы и технологии» (Нижний Новгород, НГТУ, 2010),на III Всероссийской конференции студентов, аспирантов и молодых ученых «Искусственный интеллект: философия, методология, инновации» (Москва, МИРЭА,2009), на 14-й Нижегородской сессии молодых ученых по математическим наукам(министерство образования Нижегородской области, 2009).Публикации.

По теме диссертации опубликованы 11 работ, которые приведены вконце автореферата, в том числе 5 – в журналах из Перечня ВАК; автором получен патент на полезную модель «Устройство для распознавания изображений», атакже зарегистрирована в Роспатенте программа для ЭВМ «Автоматизированнаясистема распознавания людей по фотографиям лиц».Основные положения, выносимые на защиту.1. Метод направленного перебора альтернатив как эффективный (в смыслевычислительной сложности) метод решения задачи автоматического распознавания полутоновых изображений.2.

Комплекс проблемно-ориентированных программ, реализующий метод направленного перебора и предназначенный для проведения вычислительного эксперимента.3. Оценки вычислительной трудоемкости метода направленного перебора всравнении с генетическим алгоритмом по результатам комплексного исследования проблемы больших баз эталонных данных в задаче автоматического распознавания изображений.Структура и объем работы. Диссертация изложена на 152 страницах, состоит извведения, четырех глав основного текста, заключения, списка используемой литературы, включающего 117 наименований, и шести приложений.7ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫВо введении содержится обоснование актуальности темы диссертации,описываются объект, предметы и методы ее исследования.

Отмечена научная новизна и практическая значимость результатов, приведены основные положениядиссертационной работы, выносимые на защиту, а также сведения об апробации,реализации и внедрении результатов работы.В первой главе для решения «Задачи распознавания полутоновых изображений» применяется статистический подход и принцип МИР. Задача состоитв том, чтобы отнести вновь поступающее (на вход) изображение X = xuv ,(r )u = 1,U , v = 1,V к одному из R классов, заданных эталонами X r = xuv, r = 1, R .(r )∈ {1,2,K, xmax } - интенсивностьЗдесь U – высота изображения, V – его ширина; xuvточки с координатами (u,v); xmax - максимальное значение интенсивности.Для случайной величины – интенсивности r-го изображения – оценим по[]r):матрице Xr ее распределение H r = h1( r ) , h2( r ) ,K, hx(maxhx( r )= (U ⋅ V )−1∑∑ δ (xuv( r ) − x ),U Vu =1 v =1где δ(x) - дискретная дельта-функция.

Такая же процедура выборочной оценкираспределения H применяется и для входного изображения X. Как известно, непосредственно сравнение гистограмм наталкивается на проблему вариативности освещения - если затемнить/осветлить изображение, то его гистограмма изменится.Именно поэтому после вычисления гистограмм Hr и H зачастую применяется ихдинамическое выравнивание, что существенно увеличивает объем вычислений.В работе предлагается кардинальный способ преодоления указанного недостатка. Так как основная информация об изображении заключается не в цвете еготочек, а в количестве точек с одинаковой освещенностью, перейдем к независимой[(r )(r )]от освещения гистограмме H r = h1 ,K, h xmax путем сортировки элементов Hr по(r )((r ))убыванию: 1 ≥ h1 ≥ K ≥ h xmax ≥ 0 и существует такая перестановка i1 ,K, i xmax чи(r )сел (1,2,…,xmax), что h x = hi(xr ) , x = 1, xmax . В результате, H r можно рассматривать8как распределение некой случайной величины.

Применение этой теоретиковероятностной модели изображения позволяет свести задачу распознавания кпроверке R гипотез о распределении H r , r = 1, R изображения на входе H .Теорема 1. Оптимальный в байесовском смысле минимума вероятностиошибки критерий распознавания изображений задается выражениемρ KL ( X / X r ) =(xmax(r )∑ h x ln h x / h xx =1)→ min .(1)Статистика ρKL(X/Xr) здесь определяет информационное рассогласование (направленное расхождение) по Кульбаку-Лейблеру между наблюдаемым изображениемX и r-м эталоном.

Справедливость теоремы 1 вытекает из более общей теоремы.Теорема 2. При распознавании R случайных дискретных объектов, заданныхэмпирическими оценками законов распределения, критерий минимума информационного рассогласования эквивалентен методу максимального правдоподобия.В отличие от распространенного в задачах статистической классификацииметода максимального правдоподобия, критерий МИР позволяет отбраковыватьсомнительные с точки зрения надежности решения за счет использования метрических свойств решающей статистики (1). В результате добавляется информационный (R+1)-й элемент - дополнительный выход, сигнализирующий об отказе одновременно от всех возможных R альтернатив при выполнении условия∀r ∈ {1...R} ρ KL ( X / X r ) ≥ ρ1 = const(2)Пороговое значение ρ1 для величины информационного рассогласованияпри классификации дискретных объектов определяется как ρ1 = (2n )−1 χ J2 −1,1−α ,где J – количество состояний классифицируемых объектов, n – число выборок, покоторым оцениваются эмпирические распределения входного объекта и эталонов,α – заданная вероятность ошибки первого рода.

В задачах распознавания изображений порог ρ1 определяется экспериментально на основе критерия НейманаПирсона. Если после перебора всех альтернатив выполняется (2), то принимаетсярешение о том, что объект X не принадлежит ни одному из заданных классов.9Проведено экспериментальное исследование эффективности критерия (1) взадаче распознавания людей по фотографиям лиц из большой базы данных11. Из6500 фотографий отобраны в качестве эталонов R=5500 изображений. Оставшиеся 1000 фотографий использовались для тестирования классификации. В результате применения критерия (1) в 98,9% случаев получено правильное решение. Среднее время распознавания одного изображения составило 1,4 с.

на компьютере Pentium-IV (2,9ГГц, 1Гб ОЗУ), что не удовлетворяет требованию к реальному времени. При обычном сравнении гистограмм яркости без сортировкиклассификация осуществлялась с точностью 99,2%. Однако, если немного измеа)б)в)Рис. 1. Результат АРИ по критерию МИРнять освещение входного изображения,точность(1)составит98,7%.Дляиллюстрации на рис.1 показаны две фотографии одного человека: первая – эталон (рис.1а), вторая – изображение на входе (рис 1.в).

Решение по (1) принятобезошибочно притом, что входное фото затемнено и отличается ракурсом.Для обычного сравнения гистограмм вероятность ошибки повысилась до26%. Если же выравнивать гистограммы динамически, то точность повысится до98,9%, однако среднее время распознавания превышает 2,5 с. Таким образом,предложенный критерий в формулировке (1) превосходит традиционные подходыв задачах распознавания изображений с варьирующейся освещенностью.Во второй главе синтезируется «Метод направленного перебора альтернатив».

Воспользовавшись метрическими свойствами критерия (1), сведем задачуWν ( X ) : ρ KL ( X / X ν ) → min(3)к упрощенному (в ее практической реализации) видуWν ( X ) : ρ KL ( X / X ν ) < ρ 0(4)Здесь ρ0 - порог для допустимого рассогласования на множестве объектов одногокласса за счет известной их вариативности. Значение такого порога определяетсяопытным путем при фиксировании ошибки второго рода. Заметим, что в общем11Face Recognition Data: [сайт]. URL: http://cswww.essex.ac.uk/mv/allfaces/index.html (дата обращения: 05.09.2010)10случае справедливо неравенство ρ0≤ρ1.