«Актуальные проблемы естественных и математических наук»: материалы международной заочной научно-практической конференции. (04 марта 2013 г.)

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

Семин  Лев  Андреевич

аспирант  ВлГУ,

  г.  Владимир

E-mail: 

Голубев  Андрей  Сергеевич

канд.  техн.  наук,  доцент  ВлГУ,

  г.  Владимир

E-mail: 

Звягин  Михаил  Юрьевич

канд.  физ.-мат.  наук,  доцент  ВлГУ,

  г.  Владимир

E-mail:  muz1953@yandex.ru

В  данной  статье  развивается  и  конкретизируется  подход,  применяемый  в  задаче  некооперативного  распознавания  лиц,  предложенный  в  [1].  Его  характеризуют  две  особенности.  Во-первых,  использование  не  одного,  а  набора  алгоритмов  (методик)  анализирующий  один  и  тот  же  образ  (алгоритм  вычисления  оценок,  кратко  ABO  [2,  с.  67]).  Во-вторых,  и  применение  отвлекающих  образов  —  «квазиэталонов».  Под  последним  подразумеваются  эталоны  базы,  не  являющиеся  эталонами  интереса.  Это  означает,  что  соответствующие  им  тесты  заведомо  не  могут  появиться  на  входе  системы. 

Построение  дескрипторов

Основным  понятием,  которое  используется  как  в  [1],  так  и  в  более  ранней  работе  [3]  является  «методика».  Это  понятие  комплексное,  оно  включает  в  себя  последовательность  преобразований  используемого  фото,  которая  заканчивается  построением  некоторого  линейного  объекта  (чаще  всего  вектора).  Этот  объект  является  точкой  метрического  пространства.  Таким  образом,  различные  фото  сравниваются  по  некоторой  метрике;  поскольку  методик  много,  то  и  метрик  применяется  много.  Итак,  «исходный  элемент»  конструкции  это  пара  «фото  +  методика»  (Ф,  М).  Фото,  входящее  в  пару,  по  сути,  и  есть  «квазиэталон»  —  понятие,  используемое  в  [1].  Совокупность  таких  элементов  являются  сырьем  для  дальнейших  построений.

Далее,  создается  большое  множество  тестовых  (обучающих)  пар.  Каждая  пара  маркируется  как  —  1  (чужие),  +1  (свои).  Считается,  что  пары  упорядочены,  то  есть  роли  в  них  распределены;  одно  фото  пары  —  эталон  (Э),  другое  —  тест  (Т).  Предполагается,  что  используемые  тестовые  пары  не  содержат  фото,  входящие  во  множество  «исходных  элементов». 

1.Проводится  элементарный  эксперимент.  Объединяем  фотографию  эталона  (Э)  и  фотографию  (Ф)  из  исходного  элемента,  смотрим,  к  чему  окажется  ближе  тест  в  смысле  методики  М,  взятой  из  того  исходного  элемента,  что  и  Ф.  Если  ближе  оказывается  Э,  то  тестовая  пара  классифицируется  как  +1,  в  противном  случае,  как  –1.  Так  «исходный  элемент»  начинает  играть  роль  индикатора.  В  результате  получаем  две  цифры  —  ту,  которую  дал  элементарный  эксперимент  и  истинную. 

2.Поставим  вопрос  так:  «фото  тестовой  пары  из  одного  класса?»  Ответ:  да,  тогда  X=1,  если  нет  X=0.  Таким  образом,  «исходный  элемент»  превращается  в  булеву  переменную  X.

3.Выделим  некоторый  набор  индикаторов X₁ ,..., X_n Проверим  их  реакцию  на  множество  тестовых  пар.  В  результате  каждая  тестовая  пара  преобразуется  в  дескриптор  длины  n,  состоящий  из  0  и  1. 

Определение  мнения  системы

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

Вариант  1.  Рассмотрим  случай  применения  порога  d;  его  считаем  не  в  процентах,  а  абсолютных  величинах.  Решение  —  «свои»  система  принимает,  когда  количество  индикаторов,  выдавших  значение  1  не  меньше  d.  Это  соответствует  истинности  следующей  булевой  функции ∑x_i1x_i2…x_ia;  логическая  сумма  всех  мономов  длины  d.  Такая  организация  булевой  функции  называется  «каскад».  Он  необученный,  но  его  можно  обучать  при  помощи,  например,  AdaBoost. 

По  этому  варианту  был  проведен  эксперимент  по  базе  изображений  Color  FERET  [4],  наборы  «A»  и  «B».  Из  401  фотографий  набора  «A»  были  составлены  исходные  элементы  путем  сопоставления  фотографии  с  методикой,  выбранной  случайным  образом  из  36  существующих.  Оставшиеся  фотографии  набора  «A»  были  использованы  в  качестве  эталона  при  создании  тестовых  пар,  с  каждым  эталоном  организовывалось  две  тестовых  пары  с  тестовыми  фотографиями  из  набора  «B»  таким  образом,  что  в  одну  тестовую  пару  включалась  фотография  того  же  человека,  что  и  на  фотографии  эталона,  таким  образом  пара  становилась  классом  «+1»,  т.  е.  «своей»,  в  другую  тестовую  пару  включалась  фотография  другого  человека,  выбранная  случайным  образом  из  набора  «В».  Всего  тестовых  пар  получилось  800.  По  вышеописанной  методике  для  каждой  пары  был  сформирован  дескриптор  длинной  в  401  элемент.  Экспериментальным  путем  был  установлен  порог  d  в  320  индикаторов,  выдавших  значение  1.  При  таком  пороге  система  правильно  распознала  395  тестовых  пар  класса  «свои»  и  396  пар  класса  «чужие».  Таким  образом  ошибка  первого  рода  составила  1,25  %,  ошибка  второго  рода  —  1,0  %.  Суммарная  ошибка  составляет  2,25  %.  В  зависимости  от  типа  задачи  можно  уменьшить  ошибку  первого  или  второго  рода,  путем  изменения  порога.  Т.  е.  можно  добиться  результата,  когда  система  будет  определять  правильно  100  %  пар  класса  «свои»,  но  при  этом  в  более  частых  случай  ошибочно  срабатывать  при  определении  пар  класса  «чужие».

Вариант  2.  Рассмотрим  другой  пример  построения  булевой  функции;  для  настройки  используем  класс  «свои».  Пусть  используется,  например,  четыре  индикатора  X₁,...,X₄  Допустим,  пара  из  класса  +1  выдает  дескриптор  (1,1,0,1),  ей  ставится  в  соответствие  моном  x₁x₂x₄;  другая  пара  выдает  дескриптор  (0,1,1,0)  —  ей  ставится  в  соответствие  моном  x₂x₃  и  т.  д.  Булева  функция  —  это  логическая  сумма  всех  дескрипторов,  которые  используются  для  её  построения.  В  итоге  имеем  следующее.  Если  использовать  весь  класс  «свои»,  то  ошибка  1‑го  рода  будет  равна  0,  по  построению.  Ошибка  2-го  рода  определяется  экспериментом.  Если  использовать  часть  класса  +1,  то  обе  ошибки  определяются  экспериментально.  Крайний  случай,  это  когда  используется  один  моном;  например,  x₁x₂x₃x₄.  Эту  булеву  функцию  мы  использовали  раньше  и  называли  её  «капсула».  В  этом  случае  обучение  состоит  просто  в  выборе  подмножества  индикаторов.  Предполагается  придать  булевой  функции  подвижный  характер.  Пусть  на  начальном  этапе  мы  имеем  определенный  объем  обучающего  материала  —  большое  количество.  Мы  хотим  уменьшить,  для  ускорения  оперативной  работы  системы,  их  число,  не  теряя  в  показателях  качества.  Сокращение  не  означает  уничтожение  индикаторов,  не  попавших  в  этот  урезанный  список;  весь  массив  индикаторов  сохраняется.  Пункт  1  предлагает  весьма  грубый  подход,  а  более  гибкий  пункт  2.  Накапливается  новый  материал.  Он  может  привести  к  необходимости  выбора  новой  булевой  функции.  То  есть,  предполагается  наличие  некоторой  программы,  которая  работает  параллельно  программе  оперативного  распознавания.  Она  периодически  меняет  булеву  функцию.  Подобным  образом  устроено  обновление  сигнатур  в  антивирусных  программах.

Приоритет  определяется  типом  решаемой  проблемы.  Пусть  приоритетной  является,  как  это  часто  бывает  на  практике,  задача  —  «не  допустить  ложного  срабатывания»,  то  есть  минимизировать  ошибку  2-го  рода. 

Предположим  (условно),  что  в  памяти  компьютера  есть: 

1.Фотографии  эталонов  интереса  (группа  1). 

2.Фотографии,  используемые  для  построения  индикаторов  (группа  2). 

3.Пусть  у  нас  еще  есть  третья  резервная  группа  фотографий.  Её  назначение  состоит  в  формировании  пары  «чужие».  Такие  пары  формируются  для  настройки  системы  по  схеме,  описанной  ранее:  фото  со  входа  —  тест;  фотография  из  группы  3  —  эталон. 

Напомним,  что  фотографии  групп  2  и  3  таковы,  что  соответствующие  люди  не  могут  появиться  на  входе.  Ключевые  вопросы:  сколько  нужно  индикаторов  и  какие  фотографии  (в  смысле  качества)  следует  для  них  использовать.  На  первый  вопрос  ответ  —  достаточно  большое  количество,  около  1000  различных  индикаторов.  На  второй  вопрос  ответ  неоднозначен;  возможны  варианты. 

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

Вариант  2.  Для  индикаторов  используются  фото  такого  же  типа  (качества),  что  и  группе  1.  В  этом  случае  замысел  состоит  в  следующем:  фото  на  входе  не  принадлежит  ни  индикатору,  ни  эталону  интереса.  Получается  ситуация  подобная  бросанию  монетки;  индикатор  ошибочно  может  сказать  «свои»  с  вероятностью  примерно  50  %.  Здесь  важно,  чтобы  индикаторов  было  много.

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

Настройка  системы

Рассмотрим,вариант  с  настройкой  с  учетом  указанного  приоритета. 

Итак,  в  исходной  постановке  вопрос  ставится  следующим  образом:  «эта  пара  —  свои?»,  если  ответ  не  свои,  то  делается  вывод  —  пара  «чужие».  Изменим  постановку  вопроса.  Предположим,  что  настройка  осуществляется  на  парах  класса  —  1  (чужие).  При  этом  вопрос  задается  наоборот:  «эта  пара  —  чужие?».  При  такой  постановке  вопроса  следует  строить  мономы  по  нулям  дескриптора.  Пусть  проекция  пары  на  индикаторы  дает  нули  в  позициях  i₁,...,i_n;  тогда  строится  моном  x_i1,...,x_in.  Логическая  сумма  таких  мономов  и  дает  булеву  функцию  ∑x_i1x_i2…x_in,  которая  отвечает  на  поставленный  вопрос  о  классе  уже  любой  пары  (не  из  обучающего  множества).  Таким  образом,  если  вернуться  к  первоначальной  постановке  вопроса,  то  надо  взять  отрицание  этой  функции.  В  этом  случае  булева  функция  отрицания  представляется  как  логическое  произведение  (x_i1.+...+x_in ) (...)...(...) Это  означает,  что  формируется  последовательность  групп  индексов  {i₁,…,i_n},{…},….  Все  сведется  к  проверке,  есть  ли  хотя  бы  одна  1  в  каждой  группе,  если  да,  то  пара  относится  к  классу  «свои». 

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

1. Голубев  А.С.  Особенности  распознавания  методом  ближайшего  элемента  в  алгоритмах  вычисления  оценок.  /  Голубев  А.С.,  Звягин  М.Ю.,  Прокошев  В.Г.,  Рожков  М.М.  //  Прикладная  информатика.  —  М.,  2013.  —  №  1.  —  С.  18—25.
2. Журавлев  Ю.И.,  Распознавание.  Математические  методы.  Программная  система.  Практические  применения.  /  Ю.И.  Журавлев,  В.В.  Рязанов,  О.В.  Сенько  —  М.:  Фазис,  2005.  —  159  с.
3. Рожков  М.М.  Проблема  автоматического  распознавания  лиц  с  одним  эталонным  изображением  /  В.Г.  Прокошев,  М.М.  Рожков,  П.Ю.  Шамин  //  Научно-технические  ведомости  Санкт-Петербургского  государственного  политехнического  университета.  Серия  «Информатика.  Телекоммуникации.  Управление».  —  СПб.,  2010.  —  №  5.  —  С.  13—18.
4. The  Color  FERET  Database  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  http://www.nist.gov/itl/iad/ig/colorferet.cfm.