Теоретико-вероятностная модель полутонового изображения для задачи распознавания образов без учителя на основе метода направленного перебора

Несмотря на широкую коммерциализацию и большое число программных продуктов автоматического распознавания изображений (АРИ), интенсивность исследований в этой области отнюдь не снижается, т.к., хотя цена существующих систем весьма высока, их надёжность всё ещё не достаточна. И связано это, прежде всего, с острейшей проблемой вариативности [1] – отдельные изображения одного объекта могут существенно варьироваться в зависимости от условий наблюдения: ракурса, расстояния, освещения. Проблема особенно усиливается, если объём базы данных (БД) эталонов составляет тысячи единиц, что приводит к усложнению методов распознавания и, как следствие, невозможности реализации существующих алгоритмов [1, 2] в режиме реального времени. Со всех перечисленных точек зрения несомненный интерес представляет моделирование распознавания изображений на основе теоретико-информационного подхода [3] и общесистемного принципа минимума информационного рассогласования (МИР) Кульбака-Лейблера [4]. Основанная на нём информационная теория восприятия речи показала высокие результаты [5] в задаче автоматического распознавания речи. Между тем, не все преимущества принципа МИР получили необходимое освещение и развитие. В частности, до настоящего времени почти не рассматривалась возможность разработки новых математических моделей изображений, рассчитанных на применение принципа МИР. Исследования в этом актуальном направлении и составляют главное содержание настоящей работы. В ней предложенная модель полутонового изображении сочетается с классическим байесовским подходом для распознавания без учителя, что позволило использовать метод направленного перебора альтернатив (МНП) [6] для сокращения вычислительной трудоёмкости АРИ. Полученные результаты и сделанные по ним выводы рассчи- таны на широкий круг специалистов в области распознавания изображений.

Задача автоматического распознавания изображений

Пусть задано множество из L >  1 полутоновых изображений X_f =| x V ⁾|| , I = 1, L , u = 1, U , v = 1, V . Здесь U – высота изображения, V – его ширина; x UV) e { 1,2, ^ , x max } - интенсивность точки изображения с координатами ( u,v ); x _max – максимальное значение интенсивности, l – номер эталона в БД. Задача распознавания состоит в том, чтобы отнести вновь поступающее (на вход) изображение X = || x_uv || к одному из классов, заданных эталонами X_r . Каждый класс характеризуется тем, что принадлежащие ему объекты обладают некоторой общностью или сходством в характеристиках. То общее, что объединяет объекты в класс, и называют образом. Предполагается, что несколько эталонов могут определять один класс (содержать изображение одного и того же объекта), однако априори не задано, к какому классу какой эталон принадлежит. Либо, что более вероятно, известна лишь неполная информация об отношении эталона к классу (например, двум фотографиям одного человека присвоена одинаковая метка, однако сами фотографии отличаются по времени создания на несколько лет). Это типичный пример задачи распознавания образов без учителя.

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

UV р. (XI Xi )=,,EExuv - xu V’I ^ min.       (1)

^U • ^V u = 1 V = 1                       ¹

К сожалению, подобный подход не всегда позволяет получить удовлетворительные результаты. Это обстоятельство связано, во-первых, с известной вариативностью зрительных образов, а во-вторых, с наличием во входном изображении X помех, таких как неопределённая заранее интенсивность источников освещения или просто случайное искажение некоторых точек изображения.

Теоретико-вероятностная модель полутонового изображения

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

Выполнив предварительную нормировку [10] освещения изображений из базы (например, используя гамма-коррекцию [8]), поставим каждому эталону X l в соответствие гистограмму распределения интенсивности H _i = |^ h¹ ), h 2¹),..., h x ')x J :

UV h"=     EE S( x'■-x )•

^U • V u = 1 V = 1

где 8 ( x ) - дискретная дельта-функция. Такая же процедура построения гистограммы интенсивности H = |^ h , h ₂, ..., h x mx J применяется и для входного изображения X .

Традиционным подходом по сравнению гистограмм считается так называемый метод слияния гистограмм (merge histogram) [11, 12]

x max

Z min { hx¹ ) , h x } ^ max.                        ⁽²⁾

x = 1

Как известно [13], непосредственно сопоставление гистограмм (2) наталкивается на проблему вариативности освещения – если затемнить/осветлить изображение, то его гистограмма изменится. А традиционная нормировка освещённости [8] зачастую приводит к небольшим сдвигам интенсивности точек изображения, хоть и не заметных человеку, но оказывающих влияние на гистограмму. Именно поэтому после вычисления гистограмм H l и H применяется их динамическое выравнивание [13], что существенно увеличивает объём вычислений.

В настоящей работе предлагается кардинальный способ преодоления указанного недостатка. Можно предположить, что Hl определяет собой распределение одномерной дискретной случайной величины – интенсивности I точки изображения Xl. Задача сводится в таком случае к проверке L гипотез о распределении Hi, I = 1,L , сигнала изображения на входе H:

W_i : H = H .

Оптимальное решение тогда даёт классический байесовский подход [1,7] – критерий максимума апостериорной вероятности P { W_i IX } того, что справедлива гипотеза W l при появлении на входе объекта X , то есть изображение X принадлежит классу, заданному эталоном X l . Эта вероятность вычисляется по формуле Байеса

P W . } = L^{P {} X ^{1 W } P W} ^ max.     (3)

Ep { xIwbP {W}   i i=1

Здесь P { W_i } - априорная вероятность появления i -го класса, P { XI W i } - априорная вероятность принадлежности объекта X классу . В большинстве задач АРИ предполагается, что появление каждого класса равновероятно (полная априорная неопределённость). Поэтому, делая традиционное «наивное» предположение о независимости признаков всех пикселей, критерий (3) сводится к упрощённому виду

UV

P { X/W } = ПП P { I = x uv W i } ^ max.     (4)

u = 1 V = 1

С учётом нашего предположения о том, что гистограмма H является оценкой распределения интенсивности I для класса , условная вероятность

P { I = x uv I W } = h xUV-                              (5)

Или, используя аппарата дискретных дельта-функций Дирака S( •), условная вероятность xmax

^P { I = x uV ^{1 W} } = E h x^{i )} -8 ( x ^- x uV ) .

x = 1

После несложных преобразований (4) получаем xmax            t t iz L

P { XI W i } = n ( h x^{i )} ) x ^ max.

x = 1

Удалив из показателя степени константу U•¥, определяемую площадью (в пикселях) входного изображения X, запишем окончательное решение АРИ по критерию максимального правдоподобия xmax        h

П ( h x^{i )} )' ^ ^ma x.                             ⁽⁶⁾

x = 1

К сожалению, непосредственное сравнение гистограмм (5) наталкивается на очевидную проблему, а именно: близкие значения интенсивности воспринимаются человеком одинаково [9]. Однако если перейти от задачи АРИ к задаче статистической классификации, то, например, компоненты h1 и h2 не будут иметь ничего общего, так как события I = 1 и I = 2 в такой «наивной» статистической модели изображения никак между собой не связаны. Безусловно, отмеченное обстоятельство игнорирования схожести близких значений интенсивности ухудшит качество распознавания, так как ввиду неизбежного применения процедуры нормировки освещения невозможно добиться точного совпадения нормированной интенсивности тестового изображения и эталона из БД, даже если с точки зрения человека эти изображения полностью идентичны.

На практике эта проблема обычно решается дискретизацией значений интенсивности [1, 9]. Очевидно, что это решение может привести к снижению точности распознавания. Эта проблема особенно актуальна, если в качестве признаков используется не интенсивность, а текстура или форма.

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

( ||F ( x ₁)- F ( x 2)||) нормирующий коэффициент exp -------------- ,

I       ° F      )

зависящий от расстояния Ц-Ц между ними. Здесь F ( x ₁) , F ( x 2 ) - значение признака, о _F - стандартное отклонение признака (обычно задаваемый пользователем параметр). В рассматриваемом случае распознавания изображений по интенсивности F ( x ) = x и ||^{F (} x j ) ^{- F (} x 2)|| = 1 x 1 ^- x ₂| •

В результате значения интенсивности в тестовом изображении определяются не только идентичной интенсивностью в эталоне, но и близкими (в смысле расстояния Ц-Ц) значениями. С точки зрения статистического подхода можно предположить, что условная вероятность P{I = xuv / Wl} определяется не только h(l) , но и h(l) со значениями интенсивности xuv               x x, близкими к xuv. Более формально, xmax

P { I = ^ / W } = Z P { I = х_ш 1 1 = x } - h Xl ) •      (7)

X = 1

Здесь набор условных вероятностей P {I = xuv /1 = x} определяет вероятность того, что пиксель эталона с интенсивностью x в ходе предварительной обработки изображения принял значение xuv. Тогда критерий максимального правдоподобия (4) может быть записан в аналогичной (6) форме hx xmax f xmax

ПIZP{xi/x}-hxl) I ^max.

xj=1 f x =1

Вероятности P { x ₁ / x } = P { I = x ₁ / 1 = x } должны задаваться исследователем для каждой конкретной задачи АРИ с учётом очевидных ограничений – условия регулярности

^{V x} j , ^x e { ^j , ..., ^x max } ,

P { I = x ₁/ 1 = x } > 0,                            (9)

P {I = x /1 = x}> P {I = x1/1 = x} и условия нормировки xmax

V x e { 1,..., x max } Z P { I = x j / 1 = x } = 1.        (10)

x j = 1

Тогда подход по традиционному сравнению гистограмм (6) эквивалентен определению этих вероятностей как

P { I = x ₁ / 1 = x } = S ( x ₁ - x ).

Если же применять упомянутый выше подход, используемый для сегментации изображений [14], основываясь на свойствах (9) и (10), получим следующее выражение r .     exp(-k\xx - x|)

P { I = x / 1 = x } =  ---     --- ^.         (11)

x max

Z exp ( ^- k l ^x 1 ^- i |)

i = 1

Здесь k = O F * >  0 - параметр, конфигурируемый для конкретной задачи.

Таким образом, процедура распознавания в данном случае реализуется по схеме многоканальной обработки, в которой число каналов определяется количеством изображений-эталонов L . Решение принимается по критерию минимума статистики из выражения вида (1) – для традиционных методов или из выражения (8) – при использовании метода максимального правдоподобия совместно с предложенной теоретико-вероятностной моделью полутонового изображения (7), (9)-(11).

Кластеризация базы данных эталонов

Рассмотрим наиболее актуальный и для теории, и для практики случай L ≫ 1 , когда решается задача автоматического распознавания изображений с объёмом БД в сотни и даже тысячи изображений [15]. В указанных условиях практическая реализация оптимального решающего правила (8) по схеме L -канальной обработки наталкивается на очевидную проблему его вычислительной сложности и даже практической реализуемости. В поиске путей решения указанной проблемы за счёт отказа от сплошного перебора всего множества альтернатив (обучающих выборок) и состоит центральная идея настоящей работы.

Зачастую объём БД L значительно превышает количество классов изображений R . Например, в БД может храниться несколько фотографий человека. Конечно, сходные изображения могут быть отобраны экспертом вручную. Однако для большого числа эталонов ручное разделение БД является неприемлемым в силу своей трудоёмкости. Кроме того, это решение не является правильным и с точки зрения статистического подхода.

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

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

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

Учесть указанную особенность АРИ – зависимость изображений одновременно от многих факторов – можно только с помощью надлежащего выбора обучающих выборок (БД эталонов), обеспечивая максимально полное покрытие пространства объектов, что приводит к взрывному росту количества эталонов L . К сожалению, использование здесь математического аппарата факторного анализа невозможно, так как вид функции изображения от отмеченных факторов неизвестен. А непосредственное применение к базе эталонов алгоритмов машинного обучения зачастую приводит к неудовлетворительным результатам. Действительно, такие алгоритмы основаны на сведении классификации к задаче аппроксимации. Но, как известно, аппроксимация неоднородных данных приводит к резкому росту ошибки классификации.

В результате, практически безальтернативным решением здесь будет предварительная редукция БД с применением известных алгоритмов кластеризации [7], таких как k-means или карты Кохонена [16] для выделения центроидов кластеров с последующим перебором в ходе АРИ только выбранных центроидов.

Итак, предполагаем, что множество всевозможных изображений X , из которого взяты эталоны X_l , разбивается на R непересекающихся классов X r , r = 1, R со свойствами

R

• i)    x = U x r ;

r = 1

• 2)    X r n X r ₂ =0 при r * r₂;

• 3)    (V1)(3r) X e Xr.

Предварительная задача состоит в том, чтобы на основе множества изображений-эталонов { X l } сформировать классы X _r . Это типичный пример задачи самообучения (обучение без учителя) [17].

Классические алгоритмы кластеризации [1] основаны на том, что число однородных кластеров R заранее известно. Для большинства практических приложений задачи распознавания указанное предположение не выполняется, так как в каждом классе имеется большое число эталонов для различных условий съёмки и обычно неизвестно, какие факторы оказывают основное влияние на выбранную математическую модель изображения. Поэтому количество классов требуется определять, используя только информацию, содержащуюся в множестве { X , } . Решение указанной задачи самообучения проведём на основе подхода информационной теории восприятия речи [5].

Информационная теория восприятия

Как правило, в математических задачах кластеризации и группировки основное – выбор метрики, расстояния между объектами, меры близости, сходства, различия [1, 18]. Поэтому предварительно преобразуем критерий (8) к виду, приемлемому для применения алгоритмов самообучения. Для этого прологарифмируем левую часть (8) и умножим её на (–1):

^maX |                 / Xmax

El- hx • log IeP {xi/x} hx1) Il ^ m/n.

Xi =1 ^             ^ x=1

Добавив к (12) не зависящее от l слагаемое hx' log hx, окончательно получим критерий, основанный на минимизации величины xmax р KL (X / X ) = E hx' log xmax-----x-------.     (13)

• ^{X 1} = 1          E P { * 1 / x } ' h x¹ )

x = 1

Статистика р KL ( X / X l ) здесь определяет информационное рассогласование по Кульбаку-Лейблеру [4] между наблюдаемым сигналом изображения X и l -м эталоном из БД.

Прежде всего, отметим метрические свойства решающей статистики МИР р _KL ( X / X , ) >  0 с равенством её нулю лишь в идеальном случае совпадения входного и эталонного сигналов. Основываясь на этом, множество образов X разбивается на R непере-секающихся классов X _r = { X r , r <  L } , таких, что либо X _r состоит ровно из одного эталона X_{r i} , либо

( H X r e X r , r j ^ r , ) р kl ( Xi I X_rj ) <р ₀.           (14)

Здесь р ₀ = const - порог для допустимой величины рассогласований на множестве одноимённых изображений за счёт известной их вариативности. Значение такого порога нетрудно установить опытным путём.

На основе критерия минимума суммы информационных рассогласований [5] в пределах каждого r -го кластера ( X k е X r )

p K ( X k ) = Z p KL ( X k / X ),

X i e X r определяется его информационный центр-эталон вида

^X* = argmin p K ( X k ) .                       ⁽ 1 ⁵⁾

X k , X k e X r

В информационной теории восприятия предполагается [5], что в эталоне X_r ^* содержится существенная информация обо всём классе X _r . Поэтому последний этап связан с редукцией всего множества эталонов { X , } , I = 1, L к множеству информационных центров { X * } , r = 1, R , R <  L .

После такого решения задачи самообучения второй этап – распознавание – производится на основе критерия МИР

P kl ^{( X} / ^X* ) ^ min.                          ⁽¹⁶⁾

r

С учётом определения (14) класса X _r последнюю формулу можно преобразовать к упрощённому (в её практической реализации) виду [6]

P KL ( X / X * )

o .                              (17)

По своей сути выражение (17) определяет условие останова при переборе альтернатив в рамках проверочной процедуры по критерию МИР (16).

Заметим, что если рассматривать самообучение как адаптивный процесс [17], то нетрудно заметить эквивалентность выражений (14) и (17). Действительно, при адаптивном подходе классы формируются постепенно следующим образом. Вначале число классов R = 0. Далее для каждого изображения-эталона X , , I = 1, L ищется тот класс r , для которого выполняется условие (17), то есть решается обычная задача распознавания изображения X = X, . Если такой класс υ найден, то объект X_l добавляется в класс X _v , а далее согласно (15) вычисляется его новый центр. И только если ( Vv ) р _KL ( X , / X * ) >р ₀, то создаётся новый, ( R + 1)-й класс X R _{+ 1} = { X, } , X R * _{+ 1} = X, .

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

Для решения этой задачи используется предложенный ранее [6] метод направленного перебора, в котором метрические свойства решающей статистики МИР (13) используются в наиболее полной степени.

Метод направленного перебора

В качестве предварительного этапа составим (R х R)-матрицу Р = ||рJ| попарных рассогласова ний между эталонами рi = рKL(X* / X*). Эту весьма сложную в вычислительном отношении процедуру требуется выполнить лишь раз: на предварительном этапе вычислений и для каждой конкретной БД. Однако отметим, что в контексте решения задача самообучения (14) эта матрица всё равно должна быть вычислена, так как объединение объектов в кластер основывается на попарных расстояниях между ними.

Следуя общей схеме вычислений (16), (17) сведём задачу распознавания изображений X к проверке N первых вариантов X1*,..., XN* из заданного R-мно- жества альтернатив {X*} при условии N « R . Сре ди этих N вариантов определим эталон X*, ц< N, ближайший к входному изображению X. Если, он отвечает требованию условия останова (17), процесс поиска оптимального решения по критерию МИР (16) на нём и завершается. Однако в общем случае можно предположить, что ни одна из первых N альтернатив проверку (17) на первом шаге не проходит.

Поместим изображения из нашей первой контрольной выборки X ₁^*, ..., X_N ^* в очередь с приоритетом Q . Выбор значения приоритета для каждого эталона X_r ^*, r = 1, R можно осуществить различными способами [6, 18]. В наших экспериментах [18] хорошие результаты показал приоритет р _KL ( X / X * ) (ср. с Best-Bin First [19]). На этом завершается первый этап вычислений.

На втором этапе циклически повторяется следующая процедура. Если очередь Q пуста, то в неё добавляется один наугад выбранный не проверявшийся ранее эталон из БД. Если такой эталон не найден, то алгоритм завершается.

Далее из очереди Q извлекается эталон Xi* с наименьшим приоритетом. Если р KL (X / X*) <р KL (X / X*).                   (18)

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

Затем для выделенного изображения-эталона X_i ^* по матрице Р найдем множество из M < R изображений X ⁽ M ) = { X * , „. , X * ], такое, что:

• [ iN +1 ’ ’ i N + M J ’ ’

( V _y e { 1, ^ , L } )( V X k e X ( M ) )

( X * й X ⁽ M ) ) ^ ( Ар ( X * ) >Ар ( X k ) ) .

Здесь

Ар ( Xj ) =

p„ J X ./ X. I-p_ X / X.

rKL( j i) rKL \     i / отклонение рассогласований между входным изображением X и локальным оптимумом относительно рассогласований между парой изображений Xi и

X_i ^* . После этого добавляем в очередь Q все непроверенные ранее эталоны из X ^{( M )} .

Все вычисления второго этапа повторяются до тех пор, пока на некотором K -м этапе для элемента X * не будет выполнено условие

^P KL

Ц J < ^p 0

Решение задачи АРИ принимается в пользу класса с информационным центром X * . В худшем случае, после перебора всех альтернатив из БД { X * } , но в отсутствие решения (20), можно либо сделать вывод о том, что входное изображение X нельзя отнести ни к одному классу, либо принять решение в пользу найденного «ближайшего соседа» X * с оговоркой на его недостаточную надёжность.

Следуя построению предложенного метода (18) - (20), нетрудно показать, что справедливы следующие теоремы.

Теорема 1 . Предложенный МНП всегда сходится, причем результат - эталон X * - либо является «ближайшим соседом» к входному объекту X , либо удовлетворяет условию останова (20).

Теорема 2 . Если классифицируемым объектом является один из эталонов X = X _v , ve { 1,..., R } и

( V i e { 1,..., N } , V j e { 1,..., R } )

( i * j ) ^ ( p kl ( X v / X ) *p _K L ( X v / X ) ) .

то количество вычислений рассогласований, выполняемых МНП, не зависит от размера базы данных эталонов.

В общем же случае, суммарное число C = N + ( M + 1) • K <  R выполняемых согласно (20) проверок может существенно выигрывать по сравнению с объёмом R редуцированной БД. Этот выигрыш обусловлен, в частности, тем обстоятельством, что для рассогласования Кульбака-Лейблера (как, впрочем, и для многих других расстояний, в частности, метрики l ₁ ) вероятность p того, что ближайший к X эталон X ^* принадлежит множеству X ^{( M )} , как правило, существенно превышает вероятность того, что X ^* будет одним из M наудачу выбранных эталонов:

p = P { X * e X ⁽ M ) } » p ₀ = ( M/R ) . (22)

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

Результаты экспериментальных исследований

Для проведения экспериментального исследования эффективности предложенной теоретико-вероятностной модели изображения рассмотрим задачу распознавания людей по фотографиям лиц [20,21]. В качестве их предварительной обработки для выделения лиц использовалась библиотека OpenCV. Для вычисления рассогласований все фотографии предварительно разбивались на 16 (4×4) фрагментов. Общее рассогласование между двумя фотографиями рассчитывалось как сумма рассогласований между фрагментами, вычисленными по формуле (13). Подобная фрагментация позволяет учесть неоднородное освещение изображений – каждый фрагмент нормировался по яркости [9] для ослабления проблемы вариативности освещения входных объектов. Распознавание проводились на компьютере Pentium-IV (2,9ГГц, 1Гб ОЗУ) средствами системы распознавания людей по фотографиям [22] на базе виртуальной машины Java Runtime Environment 1.6

Исходя из наших исследований [18], параметр МНП N может выбираться практически произвольно, не оказывая значимое влияние на эффективность метода, если выполнено отмеченное выше условие N ≪ R . В то же время параметр M значительно важнее. После ряда экспериментов [18] для нескольких БД фотографий лиц наилучшие (с точки зрения наименьшего объёма вычислений) значения параметров предложенного метода были выбраны следующим образом: N = 1, M = 64.

Вначале воспользуемся большой БД фотографий людей Essex [23]. Из 5187 фотографий 400 различных людей с помощью алгоритма самообучения (14), (15) на основе метрики Кульбака-Лейблера (13) были отобраны в качестве эталонов R = 954 наиболее различающиеся изображения. Для алгоритма самообучения без использования МНП количество вычислений расстояний (13) составило чуть более 2,5 млн. Если же, наряду с (14),(15), использовался МНП (18) - (20), то общий объём вычислений снизился на 68% и составил чуть более 0,5 млн. вычисления рассогласований (13). Порог p ₀ = 0,125 был подобран экспериментально. При этом вероятность того, что в один класс X _r попали изображения разных людей, составила 1%.

После этого для тестирования точности распознавания по принципу МИР (7), (11). (13) были взяты другие 1200 фотографий тех же людей. Параметр k (11) был выбран равным 0,125. В результате, в 96,8% случаев было получено точное решение

X = X_r . Здесь в среднем вычислялись рассогласований до 114 эталонов (11,9% от количества эталонов в редуцированной БД или 2,1% от объёма первоначальной БД – до этапа самообучения). Если же для указанной задачи применять только случайный поиск (без использования МНП) на основе критерия останова (17), то в среднем проверяются 55,3% эталонов.

Для критерия (2) точность АРИ оказалась аналогичной предложенной модели и критерию МИР (11), (13) – оценка вероятности ошибки составила 3,1%, в среднем по МНП вычислялись рассогласования (2) до 12% эталонов.

Для сравнения при использовании МНП совместно с метрикой l ₁ в среднем вычислялись расстояния (1) до 390 эталонов (23% от объёма редуцированной БД или 7,5% от объёма БД до этапа самообучения). При этом точность классификации составила 94%

Среднее время распознавания одного изображения с помощью метода ближайшего соседа в среднем на распознавание одного изображения составило 1,4 с для полной (нередуцированной БД) и 210 мс для полного перебора редуцированной БД. Среднее же время распознавания одного изображения по МНП на том же компьютере составило 27 мс. Вероятность ошибки полного перебора нередуцированной базы несколько ниже (1,9%), чем для МНП (3,1% - 3,2%). Это обстоятельство вызвано тем, что при оценке по обучающей выборке порога ρ ₀ досрочного останова (17) ошибка первого рода (False Reject Rate, FRR) была зафиксирована равной 5%. Её уменьшение приведёт к уменьшению ошибки классификации, но и к увеличению ошибки второго рода (False Accept Rate, FAR) и, в свою очередь, к росту объёма вычислений по МНП.

Все результаты для первого эксперимента сведены в табл. 1.

Таблица 1. Результаты АРИ для критериев (2) и (13) и БД Essex

		(2)	(13)
Сокращение БД за счёт редукции (в %)		17%	18%
Количество вычислений рассогласований при самообучении по МНП (в % от полного перебора)		31%	32%
Оценка вероятности ошибки (в %)	полный перебор БД	1,9%	1,9%
	полный перебор редуцированной БД	2,6%	2,7%
	МНП для редуцированной БД	3,1%	3,2%
Количество вычислений рассогласований при классификации по МНП (в % от полного перебора редуцированной БД)		12%	11%
Среднее время классификации (в мс)	полный перебор БД	1350	1400
	полный перебор редуцированной БД	200	210
	МНП для редуцированной БД	26	27

Для критерия (2) сопоставления гистограмм качество АРИ также несколько ниже, чем для предложенной модели. Точность АРИ упала до 93% при аналогичных показателях быстродействия МНП – 26,5% вычислений (2) по сравнению с полным перебором редуцированной БД.

		(2)	(13)
Сокращение БД за счёт редукции (в %)		36%	37%
Количество вычислений рассогласований при самообучении по МНП (в % от полного перебора)		49%	48%
Оценка вероятности ошибки (в %)	полный перебор БД	6,9%	4,4%
	полный перебор редуцированной БД	5,9%	4,0%
	МНП для редуцированной БД	7%	4,2%
Количество вычислений рассогласований при классификации по МНП (в % от полного перебора редуцированной БД)		26%	27%
Среднее время классификации (в мс)	полный перебор БД	60	63
	полный перебор редуцированной БД	19	21
	МНП для редуцированной БД	9	10

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

Заключение

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

Изложенный теоретико-вероятностный подход в задачах АРИ, по-видимому, не имеет серьёзных альтернатив ввиду острейшей проблемы вариативности изображений, связанной с зависимостью одновременно от многих факторов (как признаков изображённого объекта, так и условиями наблюдения). Однако обеспечение достаточно полного покрытия пространства объектов, в свою очередь, наталкивается на другую проблему – недостаточно высокой вычислительной эффективности традиционных методов ближайших соседей. Естественное приемлемое решение – кластеризация БД изображений по критерию МИР, заимствованная из информационной теории восприятия речи, оказалась не только продуктивной в задачах АРИ, но и одновременно послужила своеобразной точкой опоры для разработки нового критерия, основанного на методе направленного перебора альтернатив, с высокими динамическими характеристиками.