Автореферат (1137290), страница 3
Текст из файла (страница 3)
Применение выражений (2) и (4) являетсяобобщением последовательного анализа Вальда на критерий МИР.Принятие решения на основе (4) требует вычисление рассогласований дотех пор, пока оно не будет меньше порогового уровня ρ0, что позволит сократитьобъем перебора в среднем на 50%.
Естественным развитием идеи останова (4)служит предложенный ниже метод направленного перебора, в котором метрические свойства статистики (1) используются в наиболее полной степени.Наугад выбирается первая выборка из N<R эталонов X 1 ,..., X N . Среди нихопределим ближайший к X эталон Xi,i≤N. Если ρKL(X/Xi)<ρ0, то перебор на этомэталоне и завершается. В противном случае, для выделенного изображенияэталона Xi по предварительно вычисленной (один раз для конкретного множестваэталонов) матрице Ρ = ρ ij значений рассогласований ρij=ρKL(Xj/Xi) найдем множество из M<R эталонов X ( M ) = {X i1 ,K X iM }, i j ≤ R , находящихся от Xi на расстоянии, не превышающем порогового значения ρKL(X/Xi):(∀ Xi)(∉ X (M ) ∀ X j ∈ X (M ))Δρ ( X i ) ≥ Δρ (X j )(5)Здесь Δρ ( X j ) = ρ KL (X j / X i ) − ρ KL ( X / X i ) - отклонение рассогласования междувходным изображением X и локальным оптимумом Xi относительно расхождениямежду Xj и Xi.
Добавим к X(M) еще один, (M+1)-й элемент X iM +1 из числа не попавших в состав контрольной выборки по результатам предыдущего этапа вычислений. Этим в поисковую процедуру вносится элемент случайности. В результатеполучаем вторую контрольную выборку изображений-эталонов {X i , X i1 ,K X iM +1 },для анализа. Далее все вычисления первого этапа повторяются до тех пор, пока нанекотором K-м этапе для элемента Xν не будет выполнено условие останова (4). Вхудшем случае, после перебора всех элементов {Xr}, но в отсутствие решения из(4), делается вывод о том, что входное изображение X нельзя отнести ни к однойиз альтернатив.
В результате, суммарное число N+(M+1)K выполняемых согласно(4) проверок может существенно выигрывать по сравнению с объемом базы эталонов. Этот выигрыш обусловлен, в частности, тем, что для рассогласования11Кульбака-Лейблера (как, впрочем, и для других непрерывных расстояний) вероятность p того, что искомый эталон X* принадлежит множеству X(M), значительновыше вероятности того, что X* будет одним из M наудачу выбранных эталонов:{}p = P X * ∈ X ( M ) >> p0 = M / R .(6)В этом и состоит эффект направленного перебора. А отличия в количествеK этапов алгоритма объясняются тем, что вероятность (6) зависит не только отиспользуемой метрики, но и от входного изображения и множества эталонов.Проиллюстрируем метод с помощьюдиаграммы (рис.2).
Здесь звездочками обозначены все имеющиеся изображения-эталоны,буквой X – входное изображение, а ромбиком– наиболее близкий к X эталон X*, определяющий искомое решение задачи. Жирными точками обозначена последовательность наиболееРис.2. Диаграмма траекториипоиска по МНПблизких к оптимуму изображений X iN посленескольких подряд этапов вычислений. Радиу-сы окружностей определяются согласно (5). Траектория поиска отображается нарис. 2 ломаной направленной линией и имеет вид скручивающейся спирали.В развитие МНП разработан двухэтапный алгоритм распознавания как егонаиболее перспективная (в смысле количества вычислений рассогласований) модификация. На подготовительном этапе выполняется редукция (кластеризация)базы эталонов, а на втором – собственно классификация входного изображения.На первом этапе база эталонов объема L разбивается на непересекающиеся кла-{}стеры X r = X ri , ri ≤ L , такие, что либо Xr состоит ровно из одного эталона, либо(∃X r j ∈ X r , r j ≠ ri ) ρ KL ( X ri / X r j ) < ρ 0(7)После этого на основе критерия минимума суммы рассогласований в пределах rго кластера ( X k ∈ X r ) определяется его информационный центр-эталон видаX r* = arg mink∑ ρ KL ( X k / X i ).X i ∈X r12(8)В эталоне X r* содержится существенная информация обо всем классе Xr.Поэтому далее выполняется редукция первоначального множества эталонов{X l }, l = 1, L{ }к множеству X r* , r = 1, R .Вследствие сходства выражений (7) и (4), МНП (1), (4) - (6) может бытьприменен и для самообучения (7), (8).
Действительно, при адаптивном подходеклассы формируются постепенно следующим образом. Вначале число классовR=0, далее для каждого изображения-эталона X l , l = 1, L ищется класс r, для которого выполняется условие (4), то есть решается задача классификации изображения Xl. Если такой класс υ найден, то объект Xl добавляется в класс Xυ, а далее согласно (9) вычисляется его новый информационный центр. И только если(∀ν ) ρ KL ( X l / Xν* ) ≥ ρ0 , то создается новый, (R+1)-й классX R +1 = {X l }, X R* +1 = X l .Для МНП (4)-(8) в работе сформулированы и доказаны следующие теоремы.Теорема 3. Если классифицируемым объектом является один из эталонов,то количество вычислений рассогласований, выполняемых методом направленного перебора, не зависит от числа эталонов R.Теорема 4.
Если пространство классифицируемых объектов представляетсобой иерархию непересекающихся и удаленных друг от друга кластеров («дерево решений»), то количество вычислений рассогласований, выполняемых методом направленного перебора, логарифмически зависит от числа эталонов R.Таким образом, МНП столь же эффективен в предельных случаях, как и известные аналоги. Но, в отличие от них, он характеризуется повышением быстродействия без существенных ограничений на множество эталонов.В третьей главе «Разработка информационной системы» представленакомплекс программ, реализующий критерий (1) и метод (4)…(8). Программнаячасть системы реализована на современном языке Java SE 6, что расширяет возможности ее дальнейшего практического использования. Приведена общая схемаавтоматической системы распознавания людей по фотографиям лиц, описан ееинтерфейс, сформулированы назначение и принципы работы.
Подробно рассмотрены функциональные возможности системы, приведены блок-схемы новых алго13ритмов: МНП, редукции базы эталонов (7),(8) и определения порогов рассогласований ρ0 и ρ1. На рис. 3 показана структурная схема распознавания изображенийна основе МНП. Принципиальное отличие этой схемы от всех известных аналоговзаключается в том, что блок выбора эталонов для проверки управляется новымблоком экстраполяции расстояний (5).Рис. 3. Структурная схема устройства для распознавания изображений на основе МНП.Для решения задачи распознавания людей по фотографиям из главы 1 средствами созданной системы определены оптимальные (в смысле среднего количества вычислений рассогласований) значения параметров МНП: размер начальнойвыборки N=5, число попыток M=64. Вначале, задав ошибку второго рода равной5%, был подобран порог досрочного прекращения перебора ρ0=0,097.
Далее, используя алгоритм редукции на основе МНП, все множество из 5500 изображенийсгруппировано в R=960 кластеров. Количество вычислений рассогласований составило 29,5% по сравнению с традиционным группированием полным перебором. Однако гораздо важнее сокращение вычислений на втором этапе алгоритма этапе распознавания. Результаты применения здесь МНП и генетического алгоритма (ГА), реализующего случайный поиск, показаны на рис. 4.Рис.4. Гистограммы количества вычислений рассогласований относительно объема базы14Здесь среднее количество вычислений рассогласований по МНП составилопримерно 11,9% от числа эталонов.
С вероятностью 65% количество вычислениярассогласований (1) не превысило 5% от R. При этом в 96,8% случаев было получено точное решение. Среднее время распознавания одного изображения на томже компьютере составило 25 мс, что уже позволяет реализовать подобную систему в режиме реального времени.
Для сравнения, при использовании с МНП традиционной l1-метрики, вероятность ошибки составила 2,5%, при этом проверялось18,5% эталонов. Таким образом, МНП существенно сокращает вычислительнуютрудоемкость классификации изображений и для традиционных критериев.В четвертой главе рассматривается «Перспективы применения методанаправленного перебора в других задачах классификации», для которых актуальна проблема большого числа эталонов. В двух первых разделах главы исследуется задача распознавания изолированных слов, для которой проблема вариативности не может быть преодолена без введения модели «образа». Решение задачисводится к двухэтапной проверке статистических гипотез. На первом этапе классифицируются элементарные речевые единицы типа отдельных фонем, а на втором –слова как структурированные последовательности разных фонем.
Фонема здесь определяется в строгом, теоретико-информационном смысле, как множество типа кластера (7),(8) речевых единиц, объединенных по критерию МИР.На первом этапе используется линейная авторегрессионная модель формирования речевого сигнала, обоснованная предположением о гауссовом законе распределения, и теорией «акустической трубы» Гельмгольца. Тогда критерий МИРρ KL (x / x r ) = F−1⎛ Gx( f )G (f)⎞⎜⎜⎟ − 1 → min− ln xG r ( f ) ⎟⎠= 1⎝ G r ( f )F∑f(9)будет оптимальным в байесовском смысле. Здесь Gx(f) и Gr(f)- оценки (на основе рекурсивной процедуры Берга-Левинсона) спектральной плотности мощности сигналаx и r-ого эталона xr из фонетической базы данных; F – верхняя граница частотысигнала.
В результате речевой сигнал разбивается на последовательность фонем.Рассогласование между словами на втором этапе вычисляется как сумма рассогласований (9) между составляющими их фонемами. Для выравнивания слов по темпу15речи применяется динамическое программирование и алгоритм Левенштейна.В ходе эксперимента вначале, используя запись диктором отрывка из «Капитанской дочки», алгоритмом (7)…(9) выявлено множество из 20 элементарных речевых единиц. На его основе путем перебора разных сочетаний фонем сформировано множество{Xr} объема R=10000. В ней каждое слово представлялось последовательностью сочетающихся случайным образом фонем, чем достигались наиболеежесткие условия для последующей классификации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
