Разработка метода направленного перебора альтернатив в задачах классификации объектов на основе теоретико-информационного подхода

Актуальность темы

исследований. Задача классификации (диагностики, распознавания) [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 (Audioand 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] все изображения на этапе предварительной обработки приводятся к масштабу 4×4 пикселя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертационного исследования были использованы в проекте НФ ГУ-ВШЭ № 09−03 от 04.06.2009 «Разработка информационной системы для автоматической группировки и распознавания фотографий лиц методом направленного перебора альтернатив на основе принципа минимума информационного рассогласования» под руководством автора. Разработанная в рамках данного проекта «Автоматизированная система распознавания людей по фотографиям лиц» зарегистрирована в государственном реестре программ для ЭВМ под № 2 009 616 508 — по заявке 2 009 615 314 от 28.09.2009 [37]. Созданная автоматизированная система использована в качестве прототипа при разработке системы биометрической идентификации в отделе исследовательских и перспективных проектов ООО «Теком» (г.Н.Новгород). Результаты диссертационной работы внедрены также в учебный процесс НФ ГУ-ВШЭ по направлению подготовки бакалавров «Бизнес-информатика» (80 700.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. Учитывая распространение графических моделей (таблиц, диаграмм, гистограмм) в современных исследованиях, можно рекомендовать разработанный в диссертации МНП для практического применения в задачах анализа и группирования больших массивов данных, например, при статистической обработке информации социально-экономического характера.

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