Содержание к диссертации
Введение
Глава 1. Методы классификации в системах обработки аудиовизуальной информации 26
1.1. Модель систем обработки аудиовизуальной информации 26
1.2. Систематизация методов классификации аудиовизуальной информации
1.2.1. Систематизация методов классификации при наличии репрезентативной обучающей выборки 31
1.2.2. Систематизация методов классификации при наличии малого числа эталонов 34
1.2.3. Систематизация методов повышения вычислительной эффективности классификации аудиовизуальной информации для больших баз данных
1.3. Вероятностная модель кусочно-однородного объекта 43
1.4. Выводы 52
Глава 2. Построение классификаторов на основе посегментного анализа однородности 54
2.1. Методы классификации с посегментным анализом однородности 54
2.2. Модификация методов классификации с посегментным анализом однородности для дискретных значений признаков 62
2.3. Теоретико-информационный анализ процесса принятия решений 69
2.4. Выводы 76
Глава 3. Методология посегментного анализа однородности в системах обработки и классификации аудиовизуальной информации 78
3.1. Последовательный иерархический трехпороговый метод классификации 78
3.2. Метод максимально правдоподобного направленного перебора 87
3.3. Методология посегментного анализа однородности 97
3.4. Выводы 99
Глава 4. Примеры применения методологии посегментного анализа однородности в системах обработки аудио и видеоинформации 101
4.1. Технология классификации изображений на видео 101
4.2. Распознавание речи в системах голосового управления 108
4.3. Технология голосового управления на основе метода фонетического кодирования
4.3.1. Метод фонетического кодирования слов 115
4.3.2. Технология голосового управления 119
4.3.3. Алгоритм аудиовизуального распознавания команд 121
4.4. Выводы 125
Глава 5. Программный комплекс классификации аудиовизуальной информации 127
5.1. Структура программного комплекса 127
5.1.1. Программа классификации людей на видео 127
5.1.2. Программа распознавания изолированных слов для русского языка 130
5.1.3. Программа дистанционного обучения произношению слов 135
5.2. Результаты экспериментальных исследований технологии классификации изображений. 140
5.2.1 Оценка точности и вычислительной эффективности классификации с посегментным анализом однородности 140
5.2.2. Последовательный иерархический трехпороговый метод классификации 154
5.2.3. Метод максимально правдоподобного направленного перебора 163
5.3. Результаты экспериментальных исследований технологии голосового управления 174
5.3.1. Посегментный анализ однородности 174
5.3.2. Иерархический трехпороговый метод классификации 185
5.3.3. Алгоритм аудиовизуального распознаваний команд 189
5.4. Выводы 193
Заключение 195
Обозначения и сокращения 199
Список литературы
- Систематизация методов классификации при наличии малого числа эталонов
- Модификация методов классификации с посегментным анализом однородности для дискретных значений признаков
- Методология посегментного анализа однородности
- Технология голосового управления на основе метода фонетического кодирования
Систематизация методов классификации при наличии малого числа эталонов
Научная новизна работы заключается в развитии методологии посегментного анализа однородности, позволяющей повысить точность и вычислительную эффективность систем классификации аудиовизуальной информации в условиях малых выборок и большого числа классов. Данная методология основана на следующих новых научных результатах.
1. Предложен новый подход к построению классификаторов с посегментным анализом однородности признаков входного и эталонных объектов на основе вероятностной модели кусочно-однородного объекта как последовательности выборок независимых одинаково распределенных векторов признаков. В представленном подходе, в отличие от известных реализаций байесовского классификатора, для повышения точности оценки распределения вектора признаков класса используется объединенная выборка значений признаков сегментов входного и эталонного объектов. На основе этого подхода разработаны новые асимптотически минимаксные параметрические (для экспоненциального семейства) и непараметрические (для ядерных оценок Парзена) методы классификации аудиовизуальной информации.
2. Разработана модификация предложенного непараметрического метода классификации для случая дискретных конечных значений признаков на основе сопоставления их гистограмм. В отличие от известных частных случаев (метод ближайшего соседа с мерами близости хи-
квадрат и Йенсена–Шеннона) в предложенной модификации появляется возможность повышения точности за счет настройки параметров ядерной функции. Приведены оценки алгоритмической сложности разработанных методов. Показано, что представленная модификация позволяет на несколько порядков повысить вычислительную эффективность классификатора на основе посегментного анализа однородности.
3. На основе модели кусочно-однородного объекта и связи посегментного анализа однородности с критерием максимального правдоподобия разработан новый иерархический трехпо-роговый метод классификации с последовательной детализацией, в котором на каждом уровне иерархии реализуется отбраковка ненадежных решений, досрочный останов перебора и выбор наиболее надежного решения по правилу Чоу. Получена оценка алгоритмической сложности разработанного метода. Показано, что, в отличие от известных иерархических методов, в которых информация обрабатывается на всех уровнях иерархии, предложенный подход приводит к повышению вычислительной эффективности классификации.
4. Разработан новый метод приближенного ближайшего соседа – максимально правдоподобного направленного перебора, основанный на асимптотических свойствах предложенных методов классификации. Доказано, что, в отличие от известных процедур быстрого поиска ближайшего соседа, разработанный метод является оптимальным (в смысле выбора на каждом этапе максимально правдоподобного эталона) среди класса «жадных» алгоритмов для предложенного подхода к классификации с посегментным анализом однородности. Проанализированы алгоритмическая сложность синтезированного метода и его асимптотические свойства. Предложен параллельный вариант его реализации, основанный на новом алгоритме разделения обучающего множества, в котором каждому выполняемому потоку на вход подается множество из достаточно удаленных друг от друга эталонных объектов.
5. В отличие от известных классификаторов для методов посегментного анализа однородности получена асимптотическая оценка вероятности ошибочной классификации. С использованием этой оценки в рамках теоретико-информационного представления системы обработки аудиовизуальной информации в виде канала связи с шумами, на вход которого поступает некоторый эталон, а на выходе появляется классифицируемый объект, предложено оценить неопределенность доступного обучающего множества как условную энтропию такого канала связи. Показано, что полученная оценка неопределенности может применяться для повышения точности классификации, если существует возможность дополнить базу данных эталонов.
6. На основе методологии посегментного анализа однородности разработаны новый метод фонетического кодирования слов и основанный на нем алгоритм аудиовизуального распознавания команд для систем голосового управления, отличающиеся от известных методов автоматического распознавания речи тем, что классификация гласных фонем осуществляется с помощью последовательной иерархической процедуры обработки аудиоинформации. Показано, что такой подход позволяет повысить вычислительную эффективность классификации за счет сопоставления каждого сегмента только с ограниченным числом фонем-эталонов.
Практическая значимость работы определяется применимостью разработанных методов посегментного анализа однородности для решения широкого круга прикладных задач классификации аудио и визуальной информации при наличии малого числа эталонных объектов для каждого класса. Представленная методология посегментного анализа однородности может быть использована в системах обработки аудиовизуальной информации для повышения точности и вычислительной эффективности классификации в условиях малых выборок и наличии тысяч альтернативных классов. Все предложенные методы реализованы в программном комплексе, который состоит из подсистем классификации лиц на видео, голосового управления персональным компьютером и дистанционного обучения произношению. Комплекс может являться прототипом широкого спектра промышленных систем обработки аудиовизуальной информации.
Технология классификации изображений на видео внедрена в проектно-конструкторскую деятельность ООО «Биорг» (г. Москва) при модернизации технологии сканирования и обработки заполненных от руки анкет и бланков (приложение А) и в систему видеонаблюдения в компании «Эффективная энергетика» (приложение Б). Разработанный программный комплекс использован при создании системы распознавания и обучения речи в ЗАО «ИстраСофт» (приложение В). Результаты работы внедрены в учебный процесс Нижегородского государственного технического университета им. Р.Е. Алексеева (НГТУ) по направлению подготовки бакалавров 11.03.02 «Инфокоммуникационные технологии и системы связи» (приложение Г). Прикладная программа VoiceController, реализующая предложенную технологию голосового управления персональным компьютером, доступна в Интернет-магазинах AllSoft и SoftKey.
Разработанные методы классификации использованы при выполнении в 2012–2013 гг. под руководством автора НИР по Государственному контракту № 07.514.11.4137, которая по результатам экспертного анализа была включена в программу выставки и конференции, посвященных итогам реализации ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007–2013 годы». Основные результаты работы реализованы в проекте РНФ № 14-41-00039 (2014–2015 гг.), в проектах фонда содействия развитию малых форм предприятий в научно-технической сфере № 9771р/16570 (2011–2013 гг.), № 20958 (2013–2014 гг.) и № 10287 (2010–2011 гг.), в индивидуальных исследовательских проектах Высшей школы экономики (НИУ ВШЭ) № 15-01-0019 (2015–2016 гг.) и № 12-01-003 (2013–2014 гг.).
Модификация методов классификации с посегментным анализом однородности для дискретных значений признаков
Предложенная в настоящей подразделе ВНС ПАО (рисунок 2.1) является обобщением классической ВНС для классификации аудиовизуальной информации [322]. Выражение (2.3) обладает всеми преимуществами ВНС [349] над другими нейросетевыми классификаторами. Прежде всего, это высокая скорость обучения по сравнению с традиционным алгоритмом обратного распространения ошибки. А дополнительное обучение может быть выполнено в режиме реального времени. Кроме того, структура сети (рисунок 2.1) не содержит рекурсивных связей, поэтому она допускает полную реализацию в параллельном варианте. Наконец, основное достоинство предложенного классификатора заключается в том, что при увеличении размера обучающих выборок решение (2.3) сходится к оптимальному байесовскому решению [13]. При этом ожидается, что точность классификации существенно превосходит точность традиционной ВНС в особенно актуальном для обработки аудиовизуальной информации случае, когда объем обучающей выборки для каждого класса близок к объему входной выборки пг п .
К сожалению, синтезированный метод классификации (2.3) обладает также и известными недостатками сетей ВНС [349] - использование достаточно большого объема памяти для хранения всех обучающих выборок и относительно низкая скорость классификации, обусловленная полным перебором всего множества альтернатив [320]. Более того, вычислительная сложность критерия (2.3) в два раза превосходит сложность традиционной ВНС (1.9). Однако это обстоятельство не должно служить препятствием к практической реализации (2.3) в системах обработки аудиовизуальной информации, т.к. в них зачастую объем обучающих выборок (количество эталонов) относительно невелик.
Предлагаемый в настоящем разделе метод классификации с посегментным анализом однородности сводится к следующей процедуре. После выполнения традиционных для систем классификации аудиовизуальной информации шагов (рисунок 1.2), таких как детектирование объекта, предварительная обработка, сегментация и выделение примитивных признаков сегментов. Далее для описания входного объекта и всех эталонов применяется модель кусочно-однородного объекта (раздел 1.3). Наконец, выполняется полный перебор множества эталонных объектов и для каждого эталона X определяется степень его сходства с классифицируемым объектом X. Решение принимается в пользу класса того эталона, который характеризуется наибольшей степенью сходства с входным объектом. В зависимости от способа оценивания закона распределения - параметрического (для экспоненциального семейства) и непараметрического (для ядерных оценок Парзена) - выделены несколько реализаций метода (2.1) и (2.3). Таким образом, в настоящем разделе предложены методы классификации аудиовизуальной информации (2.1), (2.3) в условиях малых выборок на основе сведения задачи к анализу однородности сегментов входного и эталонного объектов. Показано, что, в отличие от известных методов, рассмотренных в предыдущей главе, такой подход позволяет синтезировать асимптотически минимаксные критерии (2.1), (2.3) проверки сложных гипотез об однородности. Более того, меры близости в предложенных методах (2.1), (2.3), в отличие от реализаций (1.7), (1.9) классического байесовского подхода, являются симметричными. Действительно, в задаче проверки однородности выборки считаются равнозначными. А в статистической классификации наблюдается асимметрия между распределением, заданным обучающей выборкой, и оценкой распределения входного объекта. Это обстоятельство может служить дополнительным обоснованием критериев (2.1), (2.3), т.к. симметрия является желательным свойством [362] рассогласования между объектами для многих алгоритмов распознавания образов (таких, как кластеризация).
Серьезным недостатком предложенного непараметрического метода (2.3), обусловленным использованием ядерных оценок распределения анализируемого объекта вида (1.8), является требование к хранению и обработке всех элементов всех обучающих выборок (memory-based approach [171]), что приводит к отмеченным выше при анализе алгоритмической сложности реализаций большим затратам при реализации этих алгоритмов. В то же время параметрический подход, реализуемый в критериях (1.7) и (2.1), оказывается недостаточно точным из-за несправедливости в общем случае предположения об экспоненциальном семействе закона распределения значений признаков. Поэтому далее приведем упрощенную версию критерия (2.3), которую можно использовать для классификации дискретных объектов [130] при наличии ограничений на максимальное время принятии решений ґ0 в ЦК (1.1), например, при обработке информации в режиме (мягкого) реального времени.
Методология посегментного анализа однородности
В настоящей главе на основе связи методов посегментного анализа однородности и критерия максимального правдоподобия предложен новый иерархический трехпороговый метод классификации с последовательной детализацией, который позволяет повысить вычислительную эффективность систем обработки аудиовизуальной информации за счет досрочного останова поиска на каждом уровне иерархии и перехода к более детализированному уровню описания только при получении недостаточно надежных решений на предыдущем уровне.
Разработан новый метод приближенного ближайшего соседа – МПНП, основанный на асимптотических свойствах представленных методов классификации и досрочном останове поиска в иерархическом трехпороговом методе. Показано, что, в отличие от известных эвристических алгоритмов приближенного поиска ближайшего соседа, разработанный метод является оптимальным (в смысле выбора на каждом этапе максимально правдоподобного эталона) среди класса «жадных» алгоритмов для предложенного подхода к классификации с посегментным анализом однородности. Проанализированы алгоритмическая сложность синтезированного метода и его асимптотические свойства. Предложен параллельный вариант его реализации, основанный на новом алгоритме разделения базы данных эталонов, в котором каждому выполняемому потоку на вход подается множество из достаточно удаленных друг от друга эталонов.
В заключительном разделе главы представлена итоговая методология посегментного анализа однородности, позволяющей повысить точность и вычислительную эффективность систем классификации аудиовизуальной информации в условиях малых выборок и большого числа классов. Ее применение для модификации существующих интеллектуальных систем распознавания аудиовизуальной информации с помощью как низкоуровневой обработки для определения меры близости анализируемых объектов на основе проверки однородности и выравнивания сегментов, так и высокоуровневой организации процесса принятия решений в рамках последовательного иерархического трехпорогового метода классификации и максимально правдоподобного поиска приближенного ближайшего соседа.
В настоящей главе для нескольких практических приложений систем обработки аудио-и видеоинформации рассматриваются технологии, реализующие представленную методологию классификации в условиях малых выборок (рисунок 3.4).
В последние десятилетия стало появляться все большее число интеллектуальных систем классификации объектов на видео [341, 377]. Несмотря на широкую коммерциализацию рынка программных продуктов классификации визуальной информации (Google Picasa, Apple iPhoto, Face.com, FaceFINDER, FaceIt, TrueFace), интенсивность исследований в этой области отнюдь не снижается, практические потребности в них только нарастают. И хотя в последние годы в области АРИ были достигнуты значительные успехи [208, 274], реализация существующих методов на практике в автоматизированных системах вызывает ряд трудностей. С одной стороны, все еще нерешенной остается задача АРИ для вариативных условий наблюдения (освещение, ракурс, низкое разрешение). Именно эти проблемы являются центральными для анализа и понимания видеоизображений. А, с другой стороны, чересчур сложные алгоритмы АРИ не могут быть реализованы при обработке видео в режиме реального времени [319]. Тем не менее, было бы ошибкой утверждать, что классификация объектов на видеоизображении существенно сложнее классической задачи АРИ. Действительно системы видеонаблюдения [377] могут использовать дополнительную информацию, связанную с тем, что в течение нескольких секунд с видеокамеры можно получить более 100 фотографий классифицируемого объекта в динамике.
Объекты для классификации поступают на вход системы с видеокамеры [193, 194]. С фиксированной частотой (10-25 раз в секунду) из видеоканала выбираются изображения - изолированные кадры, в которых с помощью стандартных методов, в которых, например, с помощью метода Виолы-Джонса [372], происходит детектирование классифицируемого объекта, описание которого сохраняется в полутоновом изображении X(t), t є {1,...,Г}, и осуществляется его предварительная обработка (нормирование по освещенности, эквализация гистограмм, медианная фильтрация и т.п.) [342]. Здесь t - номер кадра (фрейма), Т - количество кадров, каждый фрейм задается в виде матрицы яркостей [х (ґ)], и є {1,...,U}, VG{1,...,V} с высотой U и шириной V, x uv (t) є 1,2,...,x max ) - интенсивность точки изображения с координатами (u,v); m - максимальное значение интенсивности. Далее предполагается, что в модуле предварительной обработки классифицируемый объект был предварительно детектирован, и последовательность \Х(ґ)} содержит только его изображение. Задача обнаружения объекта на изображении, хоть и достаточно сложна, но имеет несколько удовлетворительных решений (см., например, [372]). Для упрощения дальнейших выкладок предполагается, что последовательность (Х(ґ)} состоит из изображений только одного распознаваемого объекта. Задача классификации объектов на видеоизображении (stillo-video) [377] состоит в том, чтобы отнести последовательность \Х(ґ)} к одному из С классов, заданных базой данных эталонных изображений
Технология голосового управления на основе метода фонетического кодирования
По результатам проведенных экспериментов (таблица 5.12) можно сделать следующие выводы. Во-первых, точность классификации критериев (4.8), основанных на анализе однородности сегментов существенно превосходит как детерминированный подход (4.9), так и традиционной реализации байесовского классификатора в виде ВНС (4.10) и принципа минимума информационного рассогласования Кульбака–Лейблера (2.15). Во-вторых, применение приближенных равенств (2.18), (2.19) сопровождается не только резким повышением вычислительной эффективности (что неудивительно, см. таблицы 5.2, 5.4, 5.6), но и, зачастую, снижением вероятности ошибочной классификации по сравнению с оригинальными критериями (4.8) и (2.17), соответственно. В-третьих, качество АРИ для предложенных критериев (4.8) и (2.18) с гауссовским ядром Парзена–Розенблатта оказалась в среднем выше по сравнению с широко применяющейся дивергенцией Йенсена–Шеннона [163, Nonextensive entropic ... , 2008]. Таким образом, можно сделать основной вывод – использование подхода, согласно которому задача классификации визуальной информации сводится к статистической проверке однородности позволяет строго обосновать недостаточную точность известных реализаций (4.10), (2.15) байесовского классификатора, в котором задача решается с помощью проверки простых гипотез, а неизвестные распределения классов оцениваются по обучающим выборкам. А предложенная в разделе 2.2 модификация метода ПАО позволяет на 5-6 порядков снизить вычислительную сложность непараметрического классификатора без статистически значимых потерь в точности. 5.2.2. Последовательный иерархический трехпороговый метод классификации
Рассмотрим применение предложенного иерархического метода (рисунок 3.1) [107, 129] для задачи классификации лиц. В первом эксперименте для тестирования использовались множества фотографий лиц Yale [382] и AT&T. Для базы данных Yale в обучающее множество эталонов помещались 15 изображений (по одной фотографии каждого человека), а тестирование качества распознавания проводилось на остальных 181 фотографиях тех же людей. Для базы AT&T в качестве множества эталонов использовались 110 изображений 40 различных людей, а тестирование качества распознавания проводилось на других 291 фотографиях тех же людей.
Гистограммы ориентированных градиентов (4.4)-(4.7) при иерархической обработке на каждом j-м уровне вычислялись для разбиений классифицируемых объектов на сетку различного размера (в эксперименте применялись квадратные сетки 5х5, 10х10, 15х15 и 20х20). Предлагаемый подход (3.1), (3.4), (3.11), (3.12) фактически позволяет осуществить автоматический выбор наилучших для каждого входного объекта размеров сетки [ 109].
В качестве мер близости в критерии (4.7) используются традиционная метрика L2 (4.9) и ВНС (4.10) и ВНС ПАО (4.8). Оценки вероятности ошибки классификации для фиксированного размера сетки сведены в таблице 5.13.
Далее в таблице 5.14 приведены вероятности ошибки для комбинирования результатов классификации, полученных для всех выбранных размеров сетки [109]. Проводится сравнение предложенного подхода на основе принципа максимума апостериорной вероятности (3.12) с известным усреднением решений в КРП [362], полученных по алгоритму агрегирования [104,
Выбор рассогласования Кульбака-Лейблера обусловлен здесь тем [111], что, во-первых, оно является несимметричным I(i;j) I(J;i), по ыбора одного из двух критериев (J=2). А, во-вторых, решение, основанное на принципе минимума информационного рассогласования (5.2), имеет тенденцию к выбору того критерия //, для которого выполняется условие р )(Х,Х ) « р )(Х,X ),г Ф г (/и), г (JU) которое на практике зачастую справедливо для надежных решений, наиболее удаленных от остальных альтернатив. По результатам этому (5.2) может быть использован даже для в проведенного эксперимента можно сделать следующие выводы [109]. Во-первых, традиционный способ сопоставления пирамид HOG за счет усреднения результатов распознавания гистограмм для различных значений размеров сетки недостаточно эффективен по сравнению с выбранными заранее наилучшими значениями параметров. И, во-вторых, осно ванный на принципе максимума апостериорной вероятности критерий (3.12) показал высокую эффективность, причём не только для метода классификации с посегментным анализом однородности (4.8), для которой может быть получена строгая оценка апостериорной вероятности, но и для традиционной метрики L2 (Евклида).
Проиллюстрируем действие предлагаемого подхода на примере классификации изображения (рисунок 5.10а) из базы данных Yale [109].
Несмотря на то, что в целом для Yale точность критерия с большой сеткой (20х20) в среднем существенно лучше остальных (таблица 5.13), в этом случае для этого размера сетки было получено неверное решение (рисунок 5.10б). Здесь рассогласование (4.7), (4.8) между входным объектом (рисунок 5.10а) и эталонами (рисунок 5.10б) и (рисунок 5.10в) практически совпадает: 0,266 и 0,269 соответственно. Поэтому и апостериорная вероятность (3.9) принадлежности объекта (рисунок 5.10а) к эталону (рисунок 5.10б) не велика. В то же время, для сетки (10х10) решение в пользу эталона (рисунок 5.10в) принято верно. Действительно, в данном случае рассогласования между распознаваемым объектом и эталонами (рисунок 5.10б и в) заметно различаются: 0,254 и 0,212 соответственно, поэтому апостериорная вероятность (3.9) максимальна.
Во втором эксперименте рассмотрим подробнее применение правила отбраковки ненадежных решений (3.11) [114] для базы данных FERET. В качестве эталонов использовались R=1288 фронтальных изображений 994 различных людей, а точность классификации оценивалась на других 1432 фотографиях тех же людей. Для принятия решения (3.11) использовалась оценка апостериорной вероятности (3.9), которая является частным случаем так называемых ядерных правил (kernel rules) [248, 349]. Наиболее часто (в контексте классификации с отказом) в качестве ядерной функции используется мера близости из алгоритма кластеризации fuzzy c-means [183]