О распознавании образов методом ближайшего элемента в условиях единичного эталона

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

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

E-mail: andrey.golubev@vlsu.ru

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

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

E-mail: muz1953@yandex.ru

On the pattern recognition by nearest element in case of one sample restriction

Andrey Golubev

Candidate of Technical Sciences, Associate Professor of VlSU, Vladimir

Mikhail Zvyagin

Candidate of Physical and Mathematical Sciences,  Associate Professor of VlSU, Vladimir

Аннотация

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

Abstract

A problem of threshold values selection in pattern recognition of compact sets with one sample per object using algorithms based on estimate evaluation, is considered. We study an option to extend the set of base samples (namely etalons) by ad-hoc set of reference samples (namely quazi-etalons).

Ключевые слова: распознавание образов; единичный эталон; порог; ближайший элемент, квази-эталоны.

Keywords: pattern recognition; one sample problem; threshold, quasi-samples.

Исследования проведены в рамках работ по госзаданию «Наука», рег. номер 8.3303.2011.

Классификация в задаче распознавания объекта по единичному эталону [1, с. 161] может быть выполнена в рамках двух различных подходов. «Классический» подход предполагает построение функции , отображающей универсальное множество распознаваемых образов  в метрическое множество признаков  и введении порога распознавания . Пусть  — множество эталонных образов, причем любой паре эталонных образов соответствуют попарно различные классы распознаваемых объектов (единственность эталонов). Распознаваемому образу (тесту)  ставится в соответствие эталонный образ (распознанный объект) , обладающий наименьшим расстоянием до  в метрике множества . При этом расстояние должно быть меньше некоторого фиксированного порога , иначе тест не считается распознанным. Необходимость введения порога обусловлена требованием выявления объектов, для которых эталонные образы отсутствуют. Выбор значения  представляет основную трудность в рамках классического подхода, т. к. это значение может быть задано только эмпирически. Кроме того, заметим, что данный подход подразумевает жесткие требования к функции  в отношении сопоставления образам одного и того же объекта как можно более «близких» элементов множества  (гипотеза компактности образов).

Другой подход заключается в использовании принципа многофакторного принятия решения. В теории распознавания такие методы известны под названием алгоритмов вычисления оценок (АВО) [3, с. 67]. Применительно к задаче распознавания изображений по единичному эталону этот подход продемонстрирован в [4]. Вместо одной «универсальной» функции  предлагается использовать ансамбль функций . Таким образом, каждая функция  задает отношение частичного порядка на множестве , и для любого теста  можно выбрать  последовательностей эталонных образов , состоящих из  ближайших к  эталонов (в соответствующей метрике). Решение об отнесении  к тому или иному объекту производится на основании анализа этой выборки — например, путем простого голосования. Значение  может варьироваться пределах от 1 до , в зависимости от решающего правила. Успех метода основан на предположении о независимости вычисления результата каждой из функций ансамбля .

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

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

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

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

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

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

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

Как показывают наши исследования, подобные оценки позволяют с успехом решать проблему распознавания на небольшом множестве . Для иллюстрации данного утверждения приведем результаты простого эксперимента, проведенного нами при помощи алгоритма распознавания лиц людей [2]. Исходными данными послужили фотографии, заимствованные из базы Color FERET [5], наборы «A» и «B». С введением множества , при небольшом увеличении ошибки первого рода (с 9,2 % до 13 %,), метод приводит к сокращению ошибки второго рода на порядок, с 37 % до менее 3 %.

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

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

1)  Синтез изображений на основе обобщенной параметрической модели распознаваемых объектов.

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

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

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

1.Анисимов, Б.В. Распознавание и цифровая обработка изображений: Учеб. пособие для студентов вузов. / Анисимов Б.В., Курганов В.Д., Злобин В.К. — М.: Высш. шк., 1983. — 295 с.

2.Голубев, А.С. Аппаратно-программный комплекс автоматической регистрации и биометрической идентификации людей. / Голубев А.С., Звягин М.Ю., Квасов Д.С., Кокорин И.Г., Зиновьев И.И., Шамин П.Ю. // Материалы XVII Всероссийской научно-методической конференции "Телематика 2010". — СПб., 2010. — С. 261—262. — ISBN 978-5-7577-0354-1.

3.Журавлев, Ю.И., Распознавание. Математические методы. Программная система. Практические применения. / Ю.И. Журавлев, В.В. Рязанов, О.В. Сенько — М.: Фазис, 2005. — 159 с.

4.Рожков, М.М. Проблема автоматического распознавания лиц с одним эталонным изображением / В.Г. Прокошев, М.М. Рожков, П.Ю. Шамин // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Серия «Информатика. Телекоммуникации. Управление». — СПб., 2010. — № 5. — С. 13—18.

5.The Color FERET Database [Электронный ресурс] — Режим доступа: http://www.nist.gov/itl/iad/ig/colorferet.cfm