автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Разработка метода направленного перебора альтернатив в задачах классификации объектов на основе теоретико-информационного подхода

Савченко Андрей Владимирович

РАЗРАБОТКА МЕТОДА НАПРАВЛЕННОГО ПЕРЕБОРА АЛЬТЕРНАТИВ В ЗАДАЧАХ КЛАССИФИКАЦИИ ОБЪЕКТОВ НА ОСНОВЕ ТЕОРЕТИКО-ИНФОРМАЦИОННОГО ПОДХОДА

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 5 НОЯ 2010

Москва-2010

004614394

Работа выполнена на кафедре информационных систем и технологий Нижегородского филиала Государственного университета - Высшей школы экономики

Научный руководитель:

кандидат технических наук, доцент Бабкин Эдуард Александрович

Официальные оппоненты:

доктор технических наук, доктор экономических наук профессор Орлов Александр Иванович, кандидат технических наук, доцент Акатьев Дмитрий Юрьевич

Ведущая организация:

Институт прикладной физики Российской Академии Наук

Защита состоится " 25 " ноября 2010 г. в 12.00 часов на заседании диссертационного совета Д 212.048.09 при Государственном университете - Высшей школе экономики по адресу: 105679, Москва, ул. Кирпичная, д. 33, ауд. 503.

С диссертацией можно ознакомиться в библиотеке Государственного университета-Высшей школы экономики по адресу: 101990, Москва, ул. Мясницкая, д. 20.

Автореферат разослан " " октября 2010 г.

Ученый секретарь диссертационного совета доктор технических наук

В.А. Фомичев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Классификация объектов как направление исследований и одновременно теоретическая база для решения прикладных задач распознавания образов активно развивается с середины XX века. Большой вклад в его развитие внесли отечественные ученые В.Н. Вапник, В.М. Глушков, A.JI. Горелик, Ю.И. Журавлёв, Н.Г. Загоруйко, A.A. Харкевич, Я.З. Цыпкин, А.Я. Червоненкис и др. За рубежом одними из основоположников классификации применительно к распознаванию образов считаются Ф. Розенблатт и Б. Уидроу. В дальнейшем их идеи были развиты J1. Рабинером, К. Фукунагой, П. Хартом, Дж. Хопфилдом и др.

Среди систем классификации особенно широкое распространение в настоящее время получили системы автоматического распознавания изображений. Действительно, цифровые изображения являются одним из основных способов представления информации в промышленности, медицине, и, конечно, в экономическом анализе (диаграммы, таблицы, графики и т.п.). Одной из наиболее актуальных прикладных задач в этой области считается ([Eickeler et al, 2000]') распознавание людей по фотографиям их лиц. Идентификация по фотографиям признана наиболее приемлемой для применения, т.к. может использоваться незаметно для окружающих в местах массового скопления людей.

Несмотря на широкую коммерциализацию рынка программных продуктов распознавания изображений, интенсивность исследований отнюдь не снижается, т.к. хотя цена существующих систем весьма высока, их надежность не достаточна. И связано это, прежде всего, с острейшей проблемой вариативности. Отдельные изображения одного объекта могут существенно варьироваться в зависимости от условий наблюдения: ракурса, расстояния, освещения. Проблема точности особенно усиливается, если объем базы эталонных данных составляет тысячи единиц, что приводит, к усложнению методов распознавания и, как следствие, невозможности реализации существующих алгоритмов ([Cover, Hart, 1968]2) в ре-

1 Eickeler S., Jabs M., Rigoll G. Comparison of Confidence Measures for Face Recognition // Fourth IEEE International Conference on Automatic Face and Gesture Recognition (FG'OO). 2000. P.257-263.

2Cover T.M., Hart P.E. Nearest Neighbor Pattern Classification. IEEE Trans. Information Theory. 1968. Vol. 13. P.21 -27.

3

жиме реального времени. Без применения современных моделей изображений новых вычислительных методов их классификации данная проблема больш] баз эталонов ([Tse, Lam, 2008]3) не может быть преодолена.

Общепринятой моделью здесь служит понятие образа ([Цыпкин, 1968]4) изображения группируются по принципу их близости (в некотором смысле) в н бор кластеров. Система распознавания тогда решает задачу классификации из бражений на наборе наиболее информативных эталонов из каждого класте] ([Орлов, 2009]5). К сожалению, такая редукция базы эталонов к центрам кластер* зачастую не позволяет преодолеть отмеченную проблему, т.к. число выделеннь кластеров может быть велико. А многочисленные методы, основанные на матсм тическом аппарате деревьев решении ([Zhang, Srihari, 2004]6), оказываются эс фективными лишь в тех редких случаях, когда группы однородных изображен« в пределах каждого кластера сходны между собой, но резко отличаются от объе! тов из других кластеров. Поэтому на практике классификация в реальном времен осуществляется за счет потерь в точности классификации ([Hastie et al, 2009]7).

Со всех перечисленных точек зрения несомненный интерес представляе моделирование распознавания изображений на основе теоретико-информационного подхода ([Zhao, Chellappa, 2005]8) и общесистемного принципа минимума информационного рассогласования (МИР) в метрике Кульбака-Лейблера ([Кульбак, 1967]9). Основанная на этом принципе информационная теория восприятия речи показала высокие результаты ([Савченко, 2007]10) в задаче

3 Tse S.-H., Lam К.-М. Efficient face recognition with a large database // 10th IEEE International Conference on Control, Automation, Robotics and Vision. 200S. P.944-949

4 Цыпкин Я.З. Адаптация и обучение в автоматических системах. - М: Наука, 1968. - 400 с.

5Орлов А.И.О развитии математических методов теории классификации//Заводская лаборатория. - 2009. - №75(7).-С.51-63

6 Zhang В., Srihari S.N. Fast k-Nearest Neighbor Classification Using Cluster-Based Trees. IEEE Trans, on Pattern Analysis and Machine Intelligence. 2004. Vol.26. №4. P. 525-528.

' Hastie, Т., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer-Verlag, 2009. 746 p.

8 Zhao W., Chellappa R. ed. Face Processing: Advanced Modeling and Methods. Elsevier/Academic Press, 2005. 768 p.

5 Кульбак С. Теория информации и статистика / Пер. С англ. М.: Наука, 1967. - 408 с.

10 Савченко В.В. Информационная теория восприятия речи//Известия вузов. Радиоэлектроника.-2007. - №6. - с.3-9.

4

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

1. Выбор и обоснование теоретико-вероятностной модели изображения.

2. Разработка нового, теоретико-информационного критерия оптимальности решения задачи автоматического распознавания изображений на основе теоретико-вероятностной модели изображений.

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

4. Реализация предложенного вычислительного метода в виде комплекса программ для проведения экспериментальных исследований его эффективности в реальных задачах распознавания изображений с базой эталонов большого объёма.

5. Исследование возможностей и перспектив применения метода направленного перебора в других актуальных задачах классификации.

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

1. Предложена новая теоретико-вероятностная модель полутонового изображения с целью применения к задаче распознавания на основе принципа минимума

информационного рассогласования в метрике Кульбака-Лейблера.

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

3. Разработана модификация метода направленного перебора с обучением режиме «без учителя», основанная на принципах группирования данных в класт ры по критерию минимума информационного рассогласования, благодаря чег* достигается максимальный выигрыш по быстродействию при классификации ср ди большого количества альтернатив.

4. На основе метода направленного перебора предложен новый алгоритм ра^ познавания речи, позволяющий в несколько раз сократить объем выполняемь: вычислений по сравнению с современными методами полного перебора. Практическая ценность работы состоит в том, что метод направленного переб< ра и его модификации предназначены для решения задач классификации в услс виях больших баз данных эталонов, когда известные методы характеризуются н< достаточным быстродействием. При этом предложенный метод может быть и< пользован как на основе существующих информационных систем, так и путе включения в них вспомогательных блоков подготовки данных в режиме обучения и их обработки в режиме распознавания. Достигаемый эффект - сокращение объема и времени вычислений - главное с точки зрения практики качество метода.

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

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

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

1. Метод направленного перебора альтернатив как эффективный (в смысле вычислительной сложности) метод решения задачи автоматического распознавания полутоновых изображений.

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

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

Структура и объем работы. Диссертация изложена на 152 страницах, состоит из введения, четырех глав основного текста, заключения, списка используемой литературы, включающего 117 наименований, и шести приложений.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении содержится обоснование актуальности темы диссертаци описываются объект, предметы и методы ее исследования. Отмечена научная н визна и практическая значимость результатов, приведены основные положен! диссертационной работы, выносимые на защиту, а также сведения об апробаци реализации и внедрении результатов работы.

В первой главе для решения «Задачи распознавания полутоновых из браженнй» применяется статистический подход и принцип МИР. Задача состо! в том, чтобы отнести вновь поступающее (на вход) изображение Х=|хИ1,|,

и = \,и,у = \,У к одному из Я классов, заданных эталонами ЛТ, г = 1,7?

Здесь и - высота изображения, V— его ширина; х^ е {1,2,...,хтах} - интенсивное: точки с координатами (иу)\ хтах - максимальное значение интенсивности.

Для случайной величины - интенсивности г-го изображения - оценим г матрице Хг ее распределение

4=1 1

где 5(х) - дискретная дельта-функция. Такая же процедура выборочной оцень распределения Н применяется и для входного изображения X. Как известно, неш средственно сравнение гистограмм наталкивается на проблему вариативности 01 вещения - если затемнить/осветлить изображение, то его гистограмма измените. Именно поэтому после вычисления гистограмм Нг и Н зачастую применяется и динамическое выравнивание, что существенно увеличивает объем вычислений.

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

от освещения гистограмме Нг = | путем сортировки элементов Нг п

убыванию: 1 > /21' ^ >....>/г^ >0 и существует такая перестановка (г,,...,/ ) 41

сел (\,2,...^стах), что Т1? =17^),х = 1,хтах . В результате, Нг можно рассматриват

8

как распределение некой случайной величины. Применение этой теоретико-вероятностной модели изображения позволяет свести задачу распознавания к проверке Я гипотез о распределении Н,, г = \,Я изображения на входе Я.

Теорема 1. Оптимальный в байесовском смысле минимума вероятности ошибки критерий распознавания изображений задается выражением

Статистика рк^Х/Х,) здесь определяет информационное рассогласование (направленное расхождение) по Кульбаку-Лейблеру между наблюдаемым изображением Хи г-м эталоном. Справедливость теоремы 1 вытекает из более общей теоремы.

Теорема 2. При распознавании Я случайных дискретных объектов, заданных эмпирическими оценками законов распределения, критерий минимума информационного рассогласования эквивалентен методу максимального правдоподобия.

В отличие от распространенного в задачах статистической классификации метода максимального правдоподобия, критерий МИР позволяет отбраковывать сомнительные с точки зрения надежности решения за счет использования метрических свойств решающей статистики (1). В результате добавляется информационный (К+1)-й элемент - дополнительный выход, сигнализирующий об отказе одновременно от всех возможных Я альтернатив при выполнении условия

Пороговое значение р; для величины информационного рассогласования

при классификации дискретных объектов определяется как р, = (2и)~' хЬ-\\-а >

где J- количество состояний классифицируемых объектов, п - число выборок, по которым оцениваются эмпирические распределения входного объекта и эталонов, а - заданная вероятность ошибки первого рода. В задачах распознавания изображений порог р; определяется экспериментально на основе критерия Неймана-Пирсона. Если после перебора всех альтернатив выполняется (2), то принимается решение о том, что объект X не принадлежит ни одному из заданных классов.

(1)

(2)

Проведено экспериментальное исследование эффективности критерия (1) задаче распознавания людей по фотографиям лиц из большой базы данных". Из 6500 фотографий отобраны в качестве эталонов 11=5500 изображений. Оставшиеся 1000 фотографий использовались для тестирования классификации. В результате применения критерия (1) в 98,9% случаев получено правильное решение. Среднее время распознавания одного изображения составило 1,4 с. на компьютере Реп1:шт-1У (2,9ГГц, 1Гб ОЗУ), что не удовлетворяет требованию к реальному времени. При обычном сравне-

áflHn |й||ВИИ| • "'"¡Трнии гистограмм яркости без сортировки

.аИШам ■■

¡¿Р|| 1 * классификация осуществлялась с точно-

Щ Ж: ' ^ЙЙ*!»

ЛШт> ЯжЬЙ? . стью 99,2%. Однако, если немного изме-

а) б) в) нять освещение входного изображения,

Рис. 1. Результат АРИ по кпитешпо МИР

точность (1) составит 98,7%. Для иллюстрации на рис.1 показаны две фотографии одного человека: первая - эталон (рис. 1а), вторая — изображение на входе (рис 1.в). Решение по (1) принято безошибочно притом, что входное фото затемнено и отличается ракурсом.

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

Во второй главе синтезируется «Метод направленного перебора альтернатив». Воспользовавшись метрическими свойствами критерия (1), сведем задачу

ЖУ(Х): Рк1(Х!Х„)^тт (3)

к упрощенному (в ее практической реализации) виду

ЖЛХ): Рк1(Х/Х„)<Ро (4)

Здесь ро - порог для допустимого рассогласования на множестве объектов одного класса за счет известной их вариативности. Значение такого порога определяется опытным путем при фиксировании ошибки второго рода. Заметим, что в общем

" Face Recognition Data: [сайт]. URL: http://cswww.essex.ac.uk/mv/ailfaces/index.htm] (дата обращения: 05.09.2010)

10

случае справедливо неравенство робрь Применение выражений (2) и (4) является обобщением последовательного анализа Вальда на критерий МИР.

Принятие решения на основе (4) требует вычисление рассогласований до тех пор, пока оно не будет меньше порогового уровня ро, что позволит сократить объем перебора в среднем на 50%. Естественным развитием идеи останова (4) служит предложенный ниже метод направленного перебора, в котором метрические свойства статистики (1) используются в наиболее полной степени.

Наугад выбирается первая выборка из N<11 эталонов Х1,...,Х1^. Среди них определим ближайший к X эталон Если р^Х/Х^рд, то перебор на этом

эталоне и завершается. В противном случае, для выделенного изображения-эталона X] по предварительно вычисленной (один раз для конкретного множества эталонов) матрице Р = |/?..|| значений рассогласований р^рш^/х^ найдем множество из М<Я эталонов Х(М) = {А!'!1>...ЛГг}, < Я, находящихся от Х1 на расстоянии, не превышающем порогового значения р^Х/Х):

(V*, й х^)(чх] 6 X(М)) Др(Х,)> Ар{Х;) (5)

Здесь = (¿Г,/*,) ' отклонение рассогласования между

входным изображением X и локальным оптимумом X, относительно расхождения между X) и Х{. Добавим к Х(М) еще один, (М+1)-й элемент Xиз числа не попавших в состав контрольной выборки по результатам предыдущего этапа вычислений. Этим в поисковую процедуру вносится элемент случайности. В результате получаем вторую контрольную выборку изображений-эталонов

для анализа. Далее все вычисления первого этапа повторяются до тех пор, пока на некотором К-м этапе для элемента Ху не будет выполнено условие останова (4). В худшем случае, после перебора всех элементов {Хг}, но в отсутствие решения из (4), делается вывод о том, что входное изображение X нельзя отнести ни к одной из альтернатив. В результате, суммарное число Ы+(М+1)К выполняемых согласно (4) проверок может существенно выигрывать по сравнению с объемом базы эталонов. Этот выигрыш "обусловлен, в частности, тем, что для рассогласования

Кульбака-Лейблера (как, впрочем, и для других непрерывных расстояний) вероятность р того, что искомый эталон X принадлежит множеству Хг^, значительн; выше вероятности того, что X будет одним из Мнаудачу выбранных эталонов:

р = р{х' еХт}»р0 =М/Я. (6)

В этом и состоит эффект направленного перебора. А отличия в количестве К этапов алгоритма объясняются тем, что вероятность (6) зависит не только от используемой метрики, но и от входного изображения и множества эталонов.

Проиллюстрируем метод с помощью •'"■■, . ■ диаграммы (рис.2). Здесь звездочками обозна-

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

Рис.2. Диаграмма траектории поиска по МНП

близких к оптимуму изображений Х- после

нескольких подряд этапов вычислений. Радиу- | сы окружностей определяются согласно (5). Траектория поиска отображается на рис. 2 ломаной направленной линией и имеет вид скручивающейся спирали.

В развитие МНП разработан двухэтапный алгоритм распознавания как его наиболее перспективная (в смысле количества вычислений рассогласований) модификация. На подготовительном этапе выполняется редукция (кластеризация) базы эталонов, а на втором - собственно классификация входного изображения. На первом этапе база эталонов объема Ь разбивается на непересекающиеся кластеры Хг = [Хг. < такие, что либо X, состоит ровно из одного эталона, либо

(ЗХГ1 е Х„г, * г,)Рк1(Хп !ХГ])< р0 (7)

После этого на основе критерия минимума суммы рассогласований в пределах г-го кластера (хк €ХГ) определяется его информационный центр-эталон вида

Х;=агВшш (8)

к Х,еХг

В эталоне X* содержится существенная информация обо всем классе Хг. Поэтому далее выполняется редукция первоначального множества эталонов {X,}, l = \,L к множеству =

Вследствие сходства выражений (7) и (4), МНП (1), (4) - (6) может быть применен и для самообучения (7), (8). Действительно, при адаптивном подходе классы формируются постепенно следующим образом. Вначале число классов R=0, далее для каждого изображения-эталона X,,l = \,L ищется класс г, для которого выполняется условие (4), то есть решается задача классификации изображения Xi. Если такой класс v найден, то объект Х\ добавляется в класс Х„, а далее согласно (9) вычисляется его новый информационный центр. И только если (V v) pKL{Xl /X*v)> /7q, to создается новый, (R+1)-Pl класс Хл+1 = - Х( .

Для МНП (4)-(8) в работе сформулированы и доказаны следующие теоремы.

Теорема 3. Если классифицируемым объектом является один из эталонов, то количество вычислений рассогласований, выполняемых методом направленного перебора, не зависит от числа эталонов R.

Теорема 4. Если пространство классифицируемых объектов представляет собой иерархию непересекающихся и удаленных друг от друга кластеров («дерево решений»), то количество вычислений рассогласований, выполняемых методом направленного перебора, логарифмически зависит от числа эталонов R.

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

В третьей главе «Разработка информационной системы» представлена комплекс программ, реализующий критерий (1) и метод (4)...(8). Программная часть системы реализована на современном языке Java SE 6, что расширяет возможности ее дальнейшего практического использования. Приведена общая схема автоматической системы распознавания людей по фотографиям лиц, описан ее интерфейс, сформулированы назначение и принципы работы. Подробно рассмотрены функциональные возможности системы, приведены блок-схемы новых алго-

ритмов: МНП, редукции базы эталонов (7),(8) и определения порогов рассогласований р0 и р1. На рис. 3 показана структурная схема распознавания изображений на основе МНП. Принципиальное отличие этой схемы от всех известных аналогов заключается в том, что блок выбора эталонов для проверки управляется новым блоком экстраполяции расстояний (5).

АЦП

Вютокамера

Блок. выделения признаков У Блок измерения сходства

Елок

юрттощян

ЦХ1Х,-)

Оперативная ШЛ1

Блок Блок Бгок принятия

экстраполяции —•> выбора решении об i

расстоянии эталонов останове

Ах/х,) С т

БЭД Блок

выдачи решения

Рис. 3. Структурная схема устройства для распознавания изображений на основе МНП.

Для решения задачи распознавания людей по фотографиям из главы 1 средствами созданной системы определены оптимальные (в смысле среднего количества вычислений рассогласований) значения параметров МНП: размер начальной выборки N=5, число попыток М=64. Вначале, задав ошибку второго рода равной 5%, был подобран порог досрочного прекращения перебора р0=О,О97. Далее, используя алгоритм редукции на основе МНП, все множество из 5500 изображений сгруппировано в К=960 кластеров. Количество вычислений рассогласований составило 29,5% по сравнению с традиционным группированием полным перебором. Однако гораздо важнее сокращение вычислений на втором этапе алгоритма -этапе распознавания. Результаты применения здесь МНП и генетического алгоритма (ГА), реализующего случайный поиск, показаны на рис. 4.

1,00 075 0,50 0,25 0,00

0,00 0,25 0,50 0,75 Ш 0,00 0,25 0.50 0,75 1,00 Рис.4. Гистограммы количества вычислений рассогласований относительно объема базы

Здесь среднее количество вычислений рассогласовании по млн составили примерно 11,9% от числа эталонов. С вероятностью 65% количество вычисления рассогласований (I) не превысило 5% от /?. При этом в 96,8% случаев было получено точное решение. Среднее время распознавания одного изображения на том же компьютере составило 25 мс, что уже позволяет реализовать подобную систему в режиме реального времени. Для сравнения, при использовании с МНП традиционной //-метрики, вероятность ошибки составила 2,5%, при этом проверялось 18,5% эталонов. Таким образом, МНП существенно сокращает вычислительную трудоемкость классификации изображений и для традиционных критериев.

В четвертой главе рассматривается «Перспективы применения метода направленного перебора в других задачах классификации», для которых актуальна проблема большого числа эталонов. В двух первых разделах главы исследуется задача распознавания изолированных слов, для которой проблема вариативности не может быть преодолена без введения модели «образа». Решение задачи сводится к двухэтапной проверке статистических гипотез. На первом этапе классифицируются элементарные речевые единицы типа отдельных фонем, а на втором -слова как структурированные последовательности разных фонем. Фонема здесь определяется в строгом, теоретико-информационном смысле, как множество типа кластера (7),(8) речевых единиц, объединенных по критерию МИР.

На первом этапе используется линейная авторегрессионная модель формирования речевого сигнала, обоснованная предположением о гауссовом законе распределения, и теорией «акустической трубы» Гельмгольца. Тогда критерий МИР

г

Ркь

- 1 -> шш (9)

будет оптимальным в байесовском смысле. Здесь Схф и оценки (на основе рекурсивной процедуры Берга-Левинсона) спектральной плотности мощности сигнала х и /--ого эталона хг из фонетической базы данных; F - верхняя граница частоты сигнала. В результате речевой сигнал разбивается на последовательность фонем. Рассогласование между словами на втором этапе вычисляется как сумма рассогласований (9) между составляющими их фонемами. Для выравнивания слов по темпу

речи применяется динамическое программирование и алгоритм Левенштейна.

В ходе эксперимента вначале, используя запись диктором отрывка из «Капитанской дочки», алгоритмом (7)...(9) выявлено множество из 20 элементарных речевых единиц. На его основе путем перебора разных сочетаний фонем сформировано множество^} объема И=10000. В ней каждое слово представлялось последовательностью сочетающихся случайным образом фонем, чем достигались наиболее жесткие условия для последующей классификации. На основе некоторого (каждый раз разного) слова-эталона Хг путем дублирования или удаления части его фонем формировалось распознаваемое слово. Среднее количество вычислений рассогласований при точности 99% составило примерно 20,6% от количества альтернатив. Этот эксперимент убедительно показал, что МНП может успешно применяться и в такой сложной задаче классификации, как распознавание речи.

В заключительном, третьем разделе главы рассмотрена задача многоальтернативного планирования биржевой игры на фондовом рынке по принципу аналогии текущего состояния рынка с его состояниями в прошлом. Задача сводится к многоальтернативной классификации в режиме «без учителя», в пределах нескольких тысяч альтернатив в ретроспективе рынка глубиной в несколько лет. Вначале задаются размер и периода, на котором курс цен считается однородным, и набор параметров {с^ф}, v = l,У, наиболее адекватно, по мнению исследователя, характеризующих конъюнктуру рынка. План игры зависит от знака приращений параметров х(у)(г)=см(1)-см(и1) - положительное приращение соответствует росту цен, отрицательное - спаду. Предположим, что каждая торговая сессия в

момент времени / > I/ определяет изображение Хг = е {1,2} с двумя ком-

понентами цветности

%у,1

{ео}

= шах

г(г) _ „(V)

и х% = шах

{-х<:\0}, где г=(-и и

> же

Рис. 5.Графическая модель рынка цепных бvмaг

= х("'(г + «). Тем самым задана математическая модель фондового рынка в виде изображения приращений цен для данного финансового инструмента на данный момент времени. Текущая рыночная ситуация описывается аналогичным изображением

X. Для иллюстрации на рис. 5 показаны модели-изображения акций General Electric на период длиной в одну неделю на 20.02.2001 и 22.09.2009. Несмотря на значительный временной сдвиг между ними, рассматриваемые состояния весьма близки по геометрии рисунка. Эффект от сказанного еще более усиливается рис. 6, где сопоставлены временные диаграммы рынка для тех же (рис.5) состояний, причем как в ретро, так и перспективе.

15---

14 -,-,-,-

22.09.09 26.09.09 30.09.09 04.10.09

Рис. 6. Временные диаграммы рыночных цен

Реальная ретроспектива рынка содержит в себе большое число R »1 изображений-эталонов {Хг}, которые можно сгруппировать в несколько состояний-кластеров. Предположив, что Хг представляет собой спектральную плотность некоего (гипотетического) двумерного случайного сигнала, сведем задачу к проверке R гипотез о спектральной плотности мощности сигнала - текущего состояния рынка X, тогда основанное на принципе МИР (9) решение примет вид

PKL{X/Xr) = {2UV)~l Z I Z fcv,* /xrwk)~ /<v J)-1 -> min. (10)

k=\u-\v = \

Для многоальтернативного планирования игры достаточно привести критерий (10) к виду (4). Действительно, при надлежащем выборе порога р0 условию (4) могут удовлетворить сразу несколько эталонов.

В процессе экспериментальных исследований рассмотрено несколько примеров из истории акций компании General Electric и индекса высокотехнологичного сектора американского рынка Nasdaq-100. Использовались стандартные параметры: цены открытия, закрытия, а также минимальная и максимальная цена. Исторические данные (ретроспектива) взяты за период с января 1995г по сентябрь 2009г. Количество ближайших альтернатив задано равным А=4. Для их нахождения использовалась описанная в главе 3 система распознавания изображений. Среднее число вычислений по МНП составило здесь 24,8% от объема ретроспективы для акций General Electric и 33,4% - для индекса Nasdaq-100. Для

сравнения, случайный поиск потребовал соответственно 66,7% и 80,2% вычислений рассогласований. Полученные результаты подтверждают ожидания в отношении перспектив применения метода направленного перебора в задачах классификации произвольных объектов, заданных в виде таблиц данных.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Исследована новая теоретико-вероятностная модель полутонового изображения в задаче классификации среди большого количества альтернатив; на основе этой модели синтезирован новый алгоритм распознавания изображений по критерию минимума информационного рассогласования в метрике Кульбака-Лейблера. Доказано, что критерий минимума информационного рассогласования является оптимальным в байесовском смысле для задач классификации дискретных случайных объектов, в том числе, цифровых изображений. Показано, что точность распознавания изображений с варьирующейся освещенностью на основе предложенного критерия существенно выше точности традиционных методов.

2. Исследованы метрические и направленные свойства решающей статистики информационного рассогласования. На их основе разработан новый вычислительный метод направленного перебора альтернатив. Показано, что предложенный метод сокращает перебор множества эталонов не только для метрики Куль-бака-Лейблера, но и при использовании традиционных метрик.

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

4. На основе метода направленного перебора разработан алгоритм автомата ческого распознавания речи по критерию минимума информационного рассогла-

сования. Показано, что этот алгоритм обладает более высокими (в 3-5 раз) динамическими свойствами, чем известные аналоги, реализующие сплошной перебора множества эталонов.

5. Исследована перспектива применения метода направленного перебора для задачи классификации объектов, заданных таблицами данных. На примере классификации состояний фондового рынка показано, что применение предложенного метода позволяет в 3-4 раза ускорить процедуру поиска в ретроспективе состояния, наиболее близкого по динамике к текущему состоянию рынка.

СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ Работы в изданиях, входящих в Перечень ВАК:

1. Савченко A.B. Метод направленного перебора альтернатив в задаче автоматического распознавания полутоновых изображений // Автометрия. - 2009. -Т.45, №3. - с.90-98. 0,5 п.л.

2. Савченко A.B. Распознавание изображений методом направленного перебора с применением редукции множества альтернатив // Системы управления и информационные технологии. - 2009. - Т.37, №3. - С.40-47. 0,5 п.л.

3. Савченко A.B. Метод направленного перебора словаря в задаче автоматического распознавания речи на основе принципа минимума информационного рассогласования // Системы управления и информационные технологии. -2009. - Т.35, №1. - С.83-91. 0,75 п.л.

4. Савченко A.B. Распознавание изображений методом направленного перебора на основе принципа минимума информационного рассогласования // Вестник Нижегородского Университета им. Н.И. Лобачевского. - 2010. - №2. - С.211-216. 1,0 п.л.

5. Савченко В.В., Савченко A.B. Принцип минимального информационного рассогласования в задаче распознавания дискретных объектов // Известия вузов России. Радиоэлектроника. - 2005. - №3. - С.10-18. 1,0 п.л. (вклад автора 0,3 п.л.)

Работы в других изданиях:

6. Савченко A.B. Распознавание фотографий лиц методом направленного перебо-

pa на основе принципа минимума информационного рассогласования //Тр. Конгресса по интеллектуальным и информационным технологиям «AIS-IT'09». - М. Физматлит. - 2009. - T.3.-C.314-315. 0,1 п.л.

7. Савченко A.B. Метод направленного перебора альтернатив в задаче планирования биржевой игры. // Материалы XVI международной научно-технической конференции «Информационные системы и технологии-2010». НГТУ, Нижний Новгород. - 2010. - С.245-247. 0,1 п.л.

8. Савченко A.B. Распознавание образов методом направленного перебора. // Искусственный интеллект: философия, методология, инновации. Материалы III всероссийской конференции студентов, аспирантов и молодых ученых. - М.: Связь-принт. - 2009. - С.312-315. 0,3 п.л.

9. Савченко A.B. Группирование фотографий лиц методом направленного перебора на основе принципа минимума информационного рассогласования // Тр. XIV Нижегородской сессии молодых ученых. Математические науки. Н.Новгород. - 2009. - С.24-25. 0,1 п.л.

lO.Savchenko A.V. Image retrieval using minimum information discrimination criterion // The IASTED International Conference on Control, Diagnostics, and Automation (ACIT-CDA). Novosibirsk. 2010. pp. 345-349. 0,6 п.л.

П.Савченко A.B. Распознавание образов на основе принципа минимума информационного рассогласования // Тр. XII Всероссийской научно-технической конференции «Нейроинформатика-2010». - Москва. - 2010. - Т.2. - С.201-202. 0,1 п.л.

12.Патент РФ №2009127049/22, 27.10.2009. Савченко A.B. Устройство для распознавания изображений/Патент России №88171. 2009. Бюл. №30. 0,2 п.л.

13.Савченко A.B. Автоматизированная система распознавания людей по фотографиям лиц - Программа для ЭВМ. / Свид-во о гос. регистрации № 2009616508 по заявке 2009615314 от 28.09.2009. 0,1 п.л.

Лицензия ЛР № 020832 от 15 ноября 1993 г. Подписано в печать октября 2010 г. Формат 60 х 84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1 Тираж 100 экз. Заказ № ¿243 Типография издательства Государственного университета - Высшей школы экономики, 125319, г. Москва, Кочновский проезд, д.З

Введение.

Глава 1. Задача распознавания полутоновых изображений.

1.1. Статистический подход.

1.2. Критерий минимума информационного рассогласования.

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

1.4. Выводы.

Глава 2. Метод направленного перебора альтернатив.

2.1. Метрические свойства статистики МИР.

2.2. Синтез алгоритма.

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

2.4. Выводы.

Глава 3. Разработка информационной системы.

3.1. Архитектура информационной системы.

3.2. Интерфейс информационной системы.

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

3.4. Выводы.

Глава 4. Перспективы применения метода направленного перебора в других задачах классификации.

4.1. Задача автоматического распознавания речи.

4.2. Распознавание изолированных слов методом направленного перебора.

4.3. Задача прогнозирования рынка ценных бумаг.

4.4. Выводы.

Актуальность темы исследований. Задача классификации (диагностики, распознавания) [1] как направление исследований и одновременно теоретическая база для решения многих прикладных задач [2] активно развивается с середины XX века. Большой вклад в его развитие внесли отечественные ученые С.А. Айвазян, М.А. Айзерман, М.М. Бонгард, Э.М. Браверманн, В.Н. Вапник, К.В. Воронцов, В.М. Глушков, A.JT. Горелик, Ю.И. Журавлев, Н.Г. Загоруйко, А.Г. Ивахненко, В.А. Ковалевский, Г.С. Лбов, ЛИ. Розоноэр, К.В. Рудаков, В.А. Скрипкин, A.A. Харкевич, Я.З. Цыпкин, А .Я. Червоненкис, М.И. Шлезингер и др. За рубежом одними из основоположников современной теории классификации применительно к распознаванию образов считаются Ф. Розенблатт, предложивший в 1958г. первую математическую модель деятельности человеческого мозга - персептрон [3]. В дальнейшем их идеи были продолжены и развиты в работах ученых более позднего периода: Ф. Гонсалеса, Р. Дуды, Дж. Ту, К. Фукунаги, К. Фу, П. Харта, Дж. Хопфилда, Б.Уидроу и др.

Среди систем классификации особенно широкое распространение в настоящее время получили системы автоматического распознавания изображений (АРИ) [4]. Это объясняется тем, что информация о многих объектах и явлениях окружающего нас мира регистрируется, хранится и обрабатывается именно в виде изображений. И данное направление исследований сейчас бурно развивается - синхронно с распространением в самых разных сферах человеческой деятельности цифровой вычислительной техники. Цифровые изображения на данный момент являются одним из основных способов представления информации в научных исследованиях, промышленности, медицине, экологии и, конечно же, в экономическом анализе (разного рода диаграммы, таблицы, графики, базы данных и т.п.).

Исюрически первые системы АРИ разрабатывались для читающих автоматов, в которых классифицировались монохромные изображения: буквы и цифры [5]. Здесь обработка изображений сводится к их сегментации на элементарные участки типа отдельных пикселей с последующим сравнением состава одноименных пикселей в анализируемом изображении и в каждом из эталонов-альтернашв из некоторой конечной базы данных. Решение принимается в пользу эталонного изображения по принципу совпадения набора его пикселей с наблюдаемым в анализируемом изображении набором. Проблемы возникают, однако, при распознавании сложных, полутоновых или цветных, изображений, когда не годится сам принцип совпадения пикселей [6]. И связано это, прежде всего, с острейшей проблемой вариативности изображений. Отдельные изображения даже одного и того же объекта могут существенно варьироваться между собой в зависимости от условий его наблюдения: ракурса [7], расстояния или освещения [8]. В указанном случае естественным образом возникает идея группирования анализируемых изображений по принципу их близости друг другу в определенный набор классов, или, говорят, образов. Система АРИ в таком случае решает стандартную задачу классификации изображений на заданном наборе образов [9].

Известно [10, И], что универсальным способом решения поставленной задачи может служить статистический подход. Его наиболее ярким представителем является группа методов, объединенных общим понятием «скрытых Марковских моделей» (СММ-методы) [12, 13]. В качестве альтернативы этим методам могут рассматриваться методы и алгоритмы обработки информации на основе многослойных искусственных нейронных сетей (ИНС) [3, 14, 15, 16]. В них реализуется детерминистский подход к задачам классификации. Ключевой проблемой в этом направлении является проблема «переобучения» ИНС [17, 18]. По сути, данная проблема сводит все направление в тупик: чем больше объем данных для обучения, тем ниже качество работы ИНС. Напротив, в рамках статистического подхода главная проблема - это проблема точности СММ [19]. Особенно актуальной она становится в задачах распознавания изображений из больших множеств альтернатив. Здесь каждому отдельному изображению для обучения (адаптации) СММ требуются десятки и даже сотни независимых образцов. А это, в свою очередь, еще более обостряет проблему вариативности изображений и вслед за ней проблему больших баз эIалойных данных (БЭД) [20].

Естественный способ ее преодоления состоит в радикальной редукции (сжатии) данных [21, 22]. Однако далеко не всегда кластеризация БЭД является эффективным средством решения указанной проблемы. Действительно, в первую очередь проблема больших БЭД обусловлена повышением вариативности образов при увеличении числа эталонов, и, как следствие, резким ростом вероятности ошибки распознавания. А применение более совершенных (и более трудоемких) методов классификации приводит, в свою очередь, к обострению рассматриваемой проблемы. Именно на ее ослабление и нацелена, главным образом, представленная диссертация. И это первый довод в подтверждение актуальности ее темы. Наряду с ним нужно указать на еще один важный, практический аспект.

В последние годы повышенное внимание со стороны исследователей и практиков АРИ уделяется задаче распознавания людей по фотографиям их лиц [23]. С одной стороны, распознавание лиц является одним из наиболее сложных приложений классификации, с другой, сказывается бурный рост спроса на автоматические системы видеоконтроля и видеонаблюдения. Современные информационные технологии видео идентификации людей по их фотографиям признаны наиболее приемлемыми для массового применения [24], так как они не требуют физического контакта объекта (человека) с устройством наблюдения и, в потенциале, характеризуется высокой надежностью ввиду известной уникальности лица каждой отдельной личности. Кроме того, указанный подход выгоден и по той причине, что может использоваться незаметно (без санкции) для окружающих в местах массового скопления людей.

Несмотря на широкую коммерциализацию рынка программных продуктов распознавания (Facelt компании Visionics, TrueFace компании Miros, разработки компания Viisage) и доступность ряда работающих технологий, интенсивность исследований в области АРИ отнюдь не снижается, практические потребности в них только нарастают. Актуальность этого направления подтверждается также продолжающимся ростом числа представительных научно-прикладных конференций таких как ICAFGR (International Conference on Automatic Face and Gesture Recognition) или AVBPA (Audio- and Video-based Biomctric Person Authentication), созданием систематических эмпирических тестов для проверки качества распознавания, таких как FERET (Face Recognition Technology) или FRVT (Face Recognition Vendor Test) и др.

К сожалению, уровень надежности существующих систем АРИ пока еще не достаточен [25]. А проблема больших БЭД, которая для идентификации людей стоит наиболее остро, решается либо' еще большим снижением надежности, либо повышением требований к аппаратной среде, в которой эти системы могут работать в режиме реального времени. Как следствие, резко возрастает стоимость таких программно-аппаратных комплексов АРИ. Поэтому разработка алгоритмов, позволяющих сократить объем вычислений АРИ без потери в качестве распознавания, является, на сегодняшний день, наиболее приоритетным в исследованиях по распознаванию образов.

Состояние исследований. Одним из самых первых подходов к решению задачи распознавания образов является способ классификации изображений, основанный на вычислении мер близости между ними [26], основанный на математическом аппарате статистики объектов нечисловой природы [27]. Экспериментальные исследования различных методов распознавания, использующих эту идею, подтверждают ее эффективность. Часто такие эксперименты для задачи АРИ осуществляются в пространстве яркостей отсчетов цифрового изображения [3, 28]. В рамках данного направления наиболее широко используются следующие меры близости: евклидово расстояние, метрика Манхэттена, расстояние Махаланобиса и т.п. Сравнительные исследования показывают [11], что эффективность систем АРИ может существенно и, главное, неконтролируемым образом, варьироваться в зависимости от применяемой меры близости. Более того, указанные различия зависят также от конкретных особенностей задачи (характера искажений, случайной освещенности и др.). Проблемы резко возрастают в условиях больших БЭД. Например, в упомянутой выше задаче идентификации личностей по фотографиям лиц современные базы данных содержат тысячи изображений. Поэтому их полный перебор требует недопустимо больших затрат по времени и, как результат, не может быть реализован в режиме реального времени [29].

Традиционный подход для преодоления указанной проблемы основан на разбиении классов на подклассы (кластеризация) образов [9,

20] и последующем сохранении в базе данных только наиболее информативных эталонов из каждого кластера. К сожалению, в настоящее время подобное решение на практике зачастую признается неудовлетворительным ввиду недостаточно сильного достигаемого с его помощью аффекта редукции данных. А многочисленные методы, основанные на математическом аппарате деревьев решений [30], оказываются эффективными лишь в тех редких случаях, когда группы однородных изображений в пределах каждого кластера сходны между собой и одновременно резко отличаются от изображений из других кластеров [31].

Поэтому чаще всего на практике ускорение вычислений для больших БЭД производится за счет потерь в качестве АРИ. Например, в работе [32] все изображения на этапе предварительной обработки приводятся к масштабу 4x4 пикселя.

К числу известных способов сокращения вычислительных затрат без существенных потерь в качестве распознавания изображений, помимо отмеченных выше алгоритмов кластеризации, можно указать на устройство мгновенного распознавания изображений [33]. Однако недостатком этого устройства является жесткое ограничение на полноту множества распознаваемых изображений. На практике же распознаваемое изображение, как правило, не дублирует ни один из эталонов. Проблема вычислительной сложности алгоритмов АРИ в этом случае еще более обостряется.

Со всех перечисленных точек зрения несомненный интерес представляет общесистемный принцип минимума информационного рассогласования (МИР) в метрике Кульбака-Лейблера [34], Основанная на этом принципе информационная теория восприятия речи (ИТВР) [35] показала высокие результаты в одном из наиболее актуальных направлений статистической классификации — в задаче автоматического распознавания речи (АРР) [36]. Высокая чувствительность к информационным различиям в сигналах при относительно высокой степени помехозащищенности их обработки и, главное, .радикальное решение проблемы вариативности через строгое определение понятия речевого кластера данных и его информационного центра-эталона -далеко не полный перечень достоинств ИТВР. Между тем, не все преимущества и возможности принципа МИР на данный момент получили необходимое освещение и развитие в научных исследованиях. В частности, до настоящего времени практически не исследовались возможность его применения в задачах АРИ, для которых проблема больших БЭД особенно актуальна. Исследования в этом направлении и составляют главное содержание представленной диссертационной работы.

Объект и предмет исследования. Вычислительные методы классификации изображений и таблиц данных в задачах с большими объёмами баз данных.

Цель диссертационного исследования. Основная цель диссертационной работы состоит в разработке методов ускорения вычислительной процедуры классификации в условиях большого количества альтернатив — на основе принципа минимума информационного рассогласования и предлагаемого метода направленного перебора альтернатив (МНИ). Для достижения этой цели в диссертации решались следующие задачи:

1. Выбор и обоснование теоретико-вероятностной модели изображения.

2. Разработка нового, теоретико-информационного критерия оптимальности решения задачи АРИ на основе теоретико-вероятностной модели изображений;

3. Разработка и исследование нового метода классификации с направленным перебором (МНП) и редукцией БЭД как одной из альтернатив традиционным методам, основанным на принципе полного перебора конкурирующих гипотез;

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

5. Исследование возможностей и перспектив применения МНП в других актуальных задачах классификации.

Методы исследования. Для решения поставленных задач в работе использовались современные методы теории распознавания образов, теории вероятностей и математической статистики, математического моделирования, теории информации, теории сигналов, а также информационной теории восприятия речи [35].

Научная новизна работы состоит в следующем.

1. Предложена новая теоре гико-вероятностная модель полутонового изображения с целью применения к задаче распознавания принципа минимума информационного рассогласования в метрике Кульбака-Лейблера.

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

3. Разработана модификация метода направленного перебора с обучением в режиме «без учителя», основанная на принципах группирования данных в кластеры по критерию минимума информационного рассогласования, благодаря чему достигается максимальный выигрыш по быстродействию при классификации среди большого количества альтернатив;

4. На основе метода направленного перебора предложен новый алгоритм распознавания речи, позволяющий в несколько раз сократить объем выполняемых вычислений по сравнению с современными методами полного перебора.

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

Результаты диссертационного исследования были использованы в проекте НФ ГУ-ВШЭ №09-03 от 04.06.2009 «Разработка информационной системы для автоматической группировки и распознавания фотографий лиц методом направленного перебора альтернатив на основе принципа минимума информационного рассогласования» под руководством автора. Разработанная в рамках данного проекта «Автоматизированная система распознавания людей по фотографиям лиц» зарегистрирована в государственном реестре программ для ЭВМ под № 2009616508 - по заявке 2009615314 от 28.09.2009 [37]. Созданная автоматизированная система использована в качестве прототипа при разработке системы биометрической идентификации в отделе исследовательских и перспективных проектов ООО «Теком» (г.Н.Новгород). Результаты диссертационной работы внедрены также в учебный процесс НФ ГУ-ВШЭ по направлению подготовки бакалавров «Бизнес-информатика» (080700.62).

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на IX Международной научно-технической конференции «Интеллектуальные системы» в рамках Международного конгресса по интеллектуальным системам и информационным технологиям (Дивноморск, ТТИ ЮФУ,

2009), на XVI Международной научно-технической конференции «Информационные системы и технологии» (Нижний Новгород, НГТУ,

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

Публикации. Основные результаты диссертации опубликованы в одиннадцати работах автора [38-46] в том числе пять - в журналах их Перечня ВАК, а именно: «Автометрия» СО РАН, «Системы управления и информационные технологии», «Вестник Нижегородского университета им. Н.И. Лобачевского» и «Известия вузов России. Радиоэлектроника». Кроме того, автором получен патент на полезную модель «Устройство для распознавания изображений» [47], а также зарегистрирована в Роспатенте программа для ЭВМ «Автоматизированная система распознавания людей по фотографиям лиц» [37].

Основные положения, выносимые на защиту:

1. Метод направленного перебора альтернатив как эффективный вычислительный метод в задаче автоматического распознавания полутоновых изображений;

2. Комплекс проблемно-ориентированных программ для ЭВМ, реализующий метод направленного перебора и предназначенный для проведения вычислительного эксперимента;

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

Структура и объем работы. Диссертация включает в себя введение, четыре главы основного текста, заключение, список используемой литературы и приложения. Вся работа изложена на 152 страницах текста, включающих 44 рисунка, 3 таблицы, 6 страниц приложения. Количество библиографических ссылок - 117.

4.4. Выводы

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

Заключение

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

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

Сама идея введения направления перебора для решения оптимизационных задач в последнее время нашла отражение в особой разновидности генетических алгоритмов - роевой оптимизации [114,

115]. Но только применение предложенного метода, основанного на априорной информации о рассогласованиях между эталонами из БЭД, позволяет в ряде случаев сократить вычислительную сложность АРИ в 20 раз по сравнению с классическими методами сплошного перебора альтернатив, такими как методы «ближайших соседей» [25]. При этом практически не утрачивается, и это очень важно отметить, и качество результирующего решения [116]. Более того, МНП столь же эффективен в предельных случаях, как и его известные аналоги, такие как деревья решений [79, 117] или система «мгновенного распознавания изображений» [33]. Но, в отличие от них, предложенный метод характеризуется повышением быстродействия и для задач классификации без существенных ограничений на БЭД.

Проведенные исследования наглядно показывают, что МНП может давать хорошие результаты в смысле сокращения перебора альтернатив на основе не только информационной метрики Кульбака-Лейблера, но и существенно более простой в реализации метрики /1. А выражение

2.2.10) позволяет в таком случае сделать обоснованный выбор в пользу одной из модификаций МНП при учете особенностей каждой конкретной БЭД. Указанная характеристика МНП является определяющей для его применения с различными метриками для конкретных задач АРИ.

Благодаря проведенным исследованиям получены следующие основные результаты:

1. Исследована новая теоретико-вероятностная модель полутонового изображения в задаче классификации среди большого количества альтернатив; на основе этой модели синтезирован новый алгоритм распознавания изображений по критерию минимума информационного рассогласования в метрике Кульбака-Лейблера.

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

2. Исследованы метрические и направленные свойства решающей статистики информационного рассогласования. На их основе разработан новый вычислительный метод направленного перебора альтернатив. Показано, что предложенный метод сокращает перебор множества эталонов не только для метрики Кульбака-Лейблера, но и при использовании традиционных метрик;

3. В условиях натурных испытаний с использованием разработанного комплекса программ исследована эффективность метода направленного перебора в задачах классификации изображений с большими базами данных эталонов. Показано, что применение метода направленного перебора в предложенном двухэтапном алгоритме позволяет на порядок увеличить скорость вычислений по сравнению с известными современными методами «ближайших соседей»;

4. На основе метода направленного перебора разработан алгоритм автоматического распознавания речи по критерию минимума информационного рассогласования. Показано, что этот алгоритм обладает более высокими (в 3-5 раз) динамическими свойствами, чем известные аналоги, реализующие сплошной перебора множества эталонов;

5. Исследована перспектива применения метода направленного перебора для задачи классификации объектов, заданных таблицами данных. На примере классификации состояний фондового рынка показано, что применение предложенного метода позволяет в 3-4 раза ускорить процедуру поиска в ретроспективе состояния, наиболее близкого по динамике к текущему состоянию рынка.

На- основании полученных результатов сделаны следующие выводы:

1. Предложенная общая теоретико-вероятностная модель изображений вполне оправдала себя как способ преодоления проблемы вариативности образов в задаче АРИ;

2. При прочих равных условиях в задачах статистической классификации объектов нечисловой природы, включая цифровые изображения, применение критерия МИР существенно более обоснованно по сравнению с классическим критерием максимального правдоподобия с точки зрения дополнительных возможностей по гарантии надежности принимаемых решений;

3. Разработанный МНП способен в значительной степени ослабить, а в ряде случаев и преодолеть проблему больших БЭД в задачах распознавания образов;

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

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

1. Орлов А.И. Математические методы исследования и диагностика материалов //Заводская лаборатория. 2003. - Т.69, №3. - С.53-64.

2. Горелик A.JL, Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания: некоторые аспекты. М.: Радио и'связь. -1985. -160с.

3. Rosenblatt F. The Perceptron: A probabilistic model for information storage and organization in the brain // Psychological Review, 1958. vol. 58. p. 386-408

4. Завалишин H.B., Мучник И.Б. Модели зрительного восприятия и алгоритмы анализа изображений. М. Наука. - 1974г. - 344с

5. Харкевич А.А. О принципах построения читающих машин // Радиотехника. 1960. - т.15, №2.

6. Zhao W. Face recognition: A Literature Survey. CS-TR-4167. University of Maryland. Oct. 2000.

7. Beymer DJ. Face recognition under varying pose. Technical report 1461. MIT A1 Laboratory. 1993.

8. Adini Y, Moses Y, Ullman S Face recognition: the problem of compensating for changes in illumination direction // IEEE Trans Pattern Anal Mach Intcll 19. 1997. p.721-732.

9. Аркадьев А. Г., Браверманн Э. M. Обучение машин классификации объектов. М.: Наука. -1974.

10. Rabiner L., Juang. B.H. An introduction to hidden Markov models //IEEE ASSP Magazine. 1986. Vol. 3. p.4-16.

11. Eickelcr S., Muller S., Rigoll G. High Performance Face Recognition Using Pseudo 2-D Hidden Markov Models // Gerhard-Mercator-University Duisburg, Germany. 1998. — 6 p. ;

12. Хайкин С. Нейронные сети: полный курс, 2-у изд., испр.: М.:000 «И.Д.Вильяме», - 2006. - 1104 с.

13. LeCun Y., Bengio Y. Convolutional networks for images, speech and time series, in M.A.Arbib, ed., The Handbook of Brain Theory and Neural Networks. Cambridge, MA: MIT Press, 1995.

14. Уоссермен Ф. Нейрокомпыотерная техника. M.: Мир. - 1992.

15. Amari S., Murata N., Muller K.-R., Finke M., Yang H. Statistical theory of overtraining Is cross-validation asymptotically effective // Advances in Neural Information Processing systems. 1996. Vol.8. P.176-182.

16. Komanski R., Macukow B. Problems Connected with Application of Neural Networks in Automatic Face Recognition // ICAISC 2004, LNAI 3070. 2004. P.736-741.

17. Rabiner L. A tutorial on hidden Markov models // Proceedings of the IEEE. 1989. Vol. 73. P.1349-1387.

18. Винцюк, Т. К. Организация вычислений при распознавании больших словарей // Автоматическое распознавание и синтез речевых сигналов: Сб. науч. тр. Киев. 1989.

19. Мандель И.Д. Кластерный анализ.-М.: Финансы и статистика. 1988.

20. Савченко В.В., Акатьев Д.Ю., Шерстнев С.Н., Метод оптимального обучающего словаря в задаче распознавания речевых сигналов покритерию минимального информационного рассогласования // Известия вузов России. Радиоэлектроника. 2006. - Выи.5. - С. 10-14

21. Eickeler S., Jabs М., Rigoll G. Comparison of Confidence Measures for Face Recognition // Gerhard-Mercator-University Duisburg, Germany. 2000. 6 p.

22. Козин H.E. Показатели сопряженности и мультиколлинеарносги в задачах анализа и распознавания изображений: Дисс.канд. тех. наук. 05.13.17 / Н.Е.Козин. Самара. 2008.

23. Zhao W., Chellappa R. ed. Face Processing: Advanced Modeling and Methods. Elsevier/Academic Press, 2005. 768 p.

24. Dasarathy B.V. ed. Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. Los Alamos, CA: IEEE Computer Society Press, 1991.

25. Раушенбах Г.В. Анализ нечисловой информации в социологических исследованиях. М.: Наука. - 1985. - С.169-203.

26. Самаль Д., Старовойтов В. Выбор признаков для распознавания на основе статистических данных // Цифровая обработка изображений. -Минск: ИТК, 1999. - С.105-114.

27. Хазен Э.М. Методы оптимальных статистических решений и задачи оптимального управления. М. Советское Радиою -1968. - 256 с.

28. Breiman L., Friedman J., Olshen R., Stone C. Classification and Regression Trees. New York: Chapman and Hall. 1984

29. Фано P.M. Эвристическое обсуждение вероятностного декодирования // Сб. «Теория кодирования». М.:Мир.-1964.-С.166-198.

30. Утробин В.А. Информационные модели системы зрительного восприятия для задач компьютерной обработки изображений. Н. Новгород: Изд-во НГТУ. - 2001.

31. Патент РФ №2004125680/09, 10.10.2007. Ченлашкин В.М. Система мгновенного компьютерного распознавания объектов и способ распознавания ./Патент России №2308081. 2007.

32. Кульбак С. Теория информации и статистика / Пер. С англ. М.: Наука.-1967.-408 с.

33. Савченко В.В. Информационная теория восприятия речи. // Известия вузов России. Радиоэлектроника. 2007. - Вып.6. - С.3-9.

34. Галунов В.И., Соловьев А.Н. Современные проблемы распознавания речи // Информационные технологии и вычислительные системы. -2004.-№2.

35. Савченко А. В. Автоматизированная система распознавания людей по фотографиям лиц Программа для ЭВМ. / Свид-во о гос. регистрации № 2009616508 по заявке 2009615314 от 28.09.2009.

36. Савченко A.B. Распознавание изображений методом направленного перебора с применением редукции множества альтернатив // Системы управления и информационные технологии 2009. - Т.37, №3. - С.40-47.

37. Савченко В.В., Савченко A.B. Принцип минимального информационного рассогласования в задаче распознавания дискретных объектов // Известия вузов России. Радиоэлектроника. . 2005. - №3. -С.10-18.

38. Савченко A.B. Распознавание образов методом направленного перебора. // Искусственный интеллект: философия, методология, инновации. Материалы III всероссийской конференции студентов, аспирантов и молодых ученых. М.:Связь-принт». 2009. - С.312-315.

39. Савченко A.B. Группирование фотографий лиц методом направленного перебора на основе принципа минимума информационного рассогласования // Тр. XIV Нижегородская сессии молодых ученых. Математические науки. Н.Новгород. 2009 - с. 24-25.

40. Савченко A.B. Распознавание образов на основе принципа минимума информационного рассогласования // Тр. XII Всероссийской научно-технической конференции «Нейроинформатика-2010», Сборник научных трудов, часть 2 МИФИ. Москва, янв. 2010. с. 201-207.

41. Патент РФ №2009127049/22, 27.10.2009. Савченко A.B. Устройство для распознавания изображений/Патент России №88171. 2009. Бюл. №30.

42. Jain A. Fundamentals of digital image processing. Prentice Hall, Englewood Cliffs. 1989.

43. Цыпкин Я.З. Адаптация и обучение в автоматических системах. -М.:Наука. 1968. - 400 с.

44. Devroye L., Gyorfi L., Lugosi G. A Probabilistic Theory of Pattern Recognition. Springer. New York. 1996.

45. Vapnik V. The Nature of Statistical Learning Theory. Springer-Verlag, New York. 1995.i

46. Маамяги A.B. Некоторые задачи статистического анализа классификаций. Таллинн: Изд-во АН ЭССР. - 1982. - 24 с.

47. Papoulis A. Probability, Random Variables and Stochastic Processes, 2nd edition. New York: McGraw-Hill. 1984.

48. Chien J.-T., Chen J.-C. Recursive bayesian regression modeling and learning // Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. 2007. Vol. 2. p.557-560.

49. Moghaddam В., Jebara Т., Pentland A. Bayesian face recognition // Pattern Recognition. 2000. Vol. 33 (11). p. 1771-1782.

50. Rhee P.K., Jeon I., Jeong E.S. Adaptive normalization based highly efficient face recognition under uneven environments // Lecture Notes in Computer Sciencc. 2005. Vol. 3611.

51. Moghaddam В., Pentland A. Maximum likelihood detection of faces and hands // International Conference on Automatic Face and Gesture Recognition. 1996.

52. Gray R. Entropy and Information Theory. Springer-Verlag. New York. 1990.

53. Colmenarez A. J., Huang T. S. Pattern detection with information-based maximum discrimination and error bootstrapping // Proc. Intl. Conf. on Pattern Recognition. 1998.

54. Antonio J., Colmenarez T. S., Huang T.S. Face detection with information based maximum discrimination // Proc. Computer Vision and Pattern Recognition. 1997.

55. Linsker R. An application of the principle of maximum information preservation to linear systems// Advances in Neural Information Processing Systems. 1989. Vol. 1. p.186-194.

56. Toussaint G. On the divergence between two distributions and the probability of misclassification of several decision rules // Proc. 2nd Int. Joint conf on Pattern Recognition. 1974. p.27-34.

57. Kullback S., Leibler R.A., On information and sufficiency, Ann. Math. Statist., 1951. Vol.22, p.79-86.

58. Акатьев Д.Ю., Савченко В.В. Принцип минимального информационного рассогласования при различении случайных сигналов/ЛРадиоэлектроника. Изв. вузов. 2004. - №1. - С.12-17.

59. Савченко В. В. Различение случайных сигналов в частотной области // Радиотехника и электроника. 1997. - Т.42, №4. - С.426.

60. Боровков А.А. Математическая статистика. Дополнительные главы. -М.: Наука, 1984.-615с.

61. Вальд А. Последовательный анализ: Пер. с англ. М.: Физматгиз. -1960.-260 с.

62. Duda R.O, Hart P.E. Pattern Classification and Scene Analysis. New York: Wiley. 1966.

63. Kohonen, Т. Self Organizing Maps. Springer. Berlin Heidelberg New York. 1995.

64. Патент РФ №99115239/09, 10.12.2000. Яхно В.Г., Нуйдель И.В., Тельных A.A., Бондаренко Б.Н., Сборщиков И.Ф., Хилько,А.И. Метод адаптивного распознавания информационных образов и система для его осуществления /Патент России №2160467. 2000. Бюл. №34. •

65. Тельных A.A. Математические модели нейроноподобных сред для разработки систем обнаружения и распознавания объектов заданных классов: Дисс.канд. тех. наук. 05.13.18 / Тельных A.A. -Н. Новгород. 2009.

66. Goldberg, D. Genetic Algorithms in search, optimization, and machine learning. Addison-Wesley, 1989.

67. Воскобойников Ю.Е., Литвинов Л.А. Выбор момента останова в итерационных алгоритмах восстановления сигналов и изображений // Автометрия. 2004. - №4. - С. 3-10.

68. Джонсон Н., Лион Ф., Статистика и планирование эксперимента в технике и науке: Методы планирования эксперимента. М.: Мир. - 1981. - 520 с.

69. Ширяев А. Н. Статистический последовательный анализ. Серия: Оптимизация и исследование операций. М.: Наука. - 1969. - 232 с.

70. Савченко В. В. Автоматическое распознавание речи методом дерева на основе информационного (7? +1)-элемента // Известия вузов России. Радиоэлектроника. 2006. - Вып.4. - С. 13-22.

71. Савченко В. В. Теория вероятностей и математическая статистика: конспект лекций. Н.Новгород: Нижегородский государственный лингвистический университет им. H.A. Добролюбова. - 2005. - 141 с.

72. Марпл, С.Л.-мл. Цифровой спектральный анализ и его приложения. -М.: Мир. 1990.

73. Levinson, S.C. Mathematical models for speech technology. // Chichester, England: John Wiley & Sons Ltd. 2005. 261 p.

74. Минь H.K., Исследование эффективности адаптивных линейных предсказателей речи для низкоскоростных кодеков: Дис.канд. тех. наук 05.13.17. М., 1997.

75. Shonkwiler R. W. Explorations in Monte Carlo methods. Springer, 2009-ISBN 978-0-387-87949-9.85.http: //www.eclipse.org. (дата обращения: 05.09.2010) :

76. Хемраджани А. Гибкая разработка приложений на Java с помощью Spring, Hibernate и Eclipse. М.:Вильямс. - 2008. - 352с.

77. Шилдт Г. Полный справочник по Java SE 6. М:Вильямс, - 2008. -1040 с.88.http: //www.jfree.org/jfrecchart/ (дата обращения: 05.09.2010)

78. Acharya. Ray Image Processing: Principles and Applications // Wiley-Interscience, 2005. 428 p.

79. Савченко В.В. Автоматическая обработка речи по критерию минимума информационного рассогласования на основе метода обеляющего фильтра // Радиотехника и электроника. 2005. - Т.50(3). -С.309-314.

80. Потапова Р.К. Речь: коммуникация, информация, кибернетика: Учебное пособие: Изд. 2-е доп. М.: Эдиториал УРСС. - 2001.

81. Widrow В. Adaptive sampled-data systems. A statistical theory of adaptation. WESCON Convention Record, 1959. pt.4.

82. Савченко В.В., Акатьев Д.Ю., Карпов Н.В. Автоматическое распознавание элементарных речевых единиц методом обеляющего фильтра. // Известия вузов. Радиоэлектроника. 2007. - Вып.4. - С.11-19.

83. Уидроу Б, Стирнз С. Адаптивная обработка сигналов // Пер. с англ. -М.: Радио и связь. 1989. - 440 с.

84. Helmholtz H. Die Lehre von der Tonempfindungen als physiologische Graudlage fur die Theorie der Musik, Brounschweig. 1870.

85. Goh Z., Tan K.-C., Tan B. Kalman filtering speech enhancement method based on voiced/unvoiced speech model // IEEE Trans. Speech Audio Proces. 1999. Vol.7. P.510-525.

86. Gannot S., Burnstein D., Weinstein E. Iterative and sequential Kalman filter-based speech enhancement algorithms // IEEE Trans. Spcech Audio Proces. 1998. Vol.6. P. 373-385.

87. Кисляков С.В. Разработка и исследование метода распознавания фонем русского языка на основе аппарата линейного предсказания: Дис.канд. тех. наук 05.12.13. СПб. 2004.

88. Кильдишев Г.С. Анализ временных рядов и прогнозирование. Серия: Математическая статистика для экономистов / М.: Статистика, 1973.- 104 с.

89. Мерков А.Б. О статистическом обучении. URL: http://www.recognition.mccme.ru/pub/RecognitionLab.html/slt.html (дата обращения: 01.09.2010).

90. Ченцов Н. Н. Статистические решающие правила и оптимальные выводы. М.: Наука, 1972.

91. Савченко В.В., Акатьев Д.Ю. Теоретико-информационное обоснование метода обеляющего фильтра в задачах автоматическогораспознавания речи. // Системы управления и информационные технологии. 2008. - №1 (31). - С.21-30.

92. Акатьев Д.Ю., Губочкин И.В., Савченко В.В. Автоматическое распознавание изолированных слов методом обеляющего фильтра с сегментированием и амплитудным ограничением сигналов переспросом // Изв. вузов России. Радиоэлектроника. 2007. - Вып. 5. - С.11-18.

93. Савченко В.В., Карлов Н.В. Анализ фонетического состава речевого сигнала методом переопределенного дерева. '// Системы управления и информационные технологии. 2008. - Т,32,№2. - С.297-303.

94. Bellman R. Dynamic Programming. Princeton, NJ: Princeton University Press, 1957.

95. Элдер A.A. Как играть и выигрывать на бирже. М.: Крон-пресс, 1996.

96. Швагер Д. Технический анализ: Полный курс Technical Analysis. -М., 2009. -С.804.

97. Савченко В.В. Использование линейной авторегрессионной модели для прогнозирования динамики биржевых котировок // Автометрия. 2004. - № 4. - Т.40. - С.117-128.

98. Baier D., Decker R., Schmiedt-Thieme L. cd. Data Analysis and Decision Support. Springer-Verlag Berlin Heidelberg New York.

99. Шевяков С.Б. Методы анализа текстур на изображении: Дисс.канд. тех. наук. 05.13.17 / С.Б.Шевяков. Н. Новгород. 2002.

100. Савченко В.В., Пономарев Д.А. Автоматическая периодизация случайных временных рядов с использованием метода обеляющего фильтра // Автометрия. Т.45, №1. - 2009. - С.56-64.

101. Ebcrhart R., Kennedy J. A New Optimizer Using Particle Swarm Theory // Proc. Int. Sym. Micro Machine and Human Science, Nagoya Japan. 1995. P.39-43.

102. Chen C.C. Hierarchical Particle Swarm Optimization for Optimization Problems // Tamkang Journal of Science and Engineering. 2009, Vol.12, №3. P.289-298.

103. Foon N. IT, Jin A.T.B., Ling D. N. C. Face Recognition Using Wavelet Transform and Non-negative Matrix Factorization // Proc. 7th Australian Joint Conference on Artificial Intelligence, Caims. 2004. P.192-202.

104. Wilking D., Rofer T. Realtime Object Recognition Using Decision Tree Learning // Robot World Cup VIII, Lecture Notes in artificial Intelligence. 2004. 3276. P.556-563.