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

На правах рукописи

Корчагин Данил Николаевич

Быстрый проекционный метод обработки мультимедиа информации

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2005

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

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

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

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

кандидат физико-математических наук, А.С. Крылов

доктор физико-математических наук, И.В. Кочиков

кандидат физико-математических наук, Д.В. Юрин

Институт прикладной математики им. М.В. Келдыша РАН

Защита диссертации состоится " " мая 2005 г. в 14:30 часов на заседании диссертационного совета К 501.001.07 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, Москва, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, второй учебный корпус, ауд. 685.

С диссертацией можно ознакомиться в научной библиотеке факультета ВМиК МГУ им. М.В. Ломоносова.

Автореферат разослан

Марта 2005 г.

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

В.М. Говоров

Общая характеристика работы Актуальность темы

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

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

Цель Диссертационной работы

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

Научная новизна работы

• Разработан быстрый проекционный метод Чебышёва-Эрмита, основанный на ускорении проекционного метода Чебышёва-Эрмита с помощью квадратуры Гаусса-Эрмита.

• Составлено ядро динамического распределения точности аппроксимации (фовеации) для проекционного метода Чебышёва- Эрмита, предложена иерархическая схема для программной реализации проекционной фовеации.

• Разработан проекционный метод для поиска картин по базе данных, основанный на обработке запроса по цифровому фотоснимку.

• Разработан проекционный метод индексации говорящих.

Теоретическая и практическая значимость работы

• Проведён сравнительный анализ эффективности предложенного быстрого проекционного метода, оптимизированного проекционного метода и дискретного преобразования Фурье.

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

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

Апробация работы

Основные результаты диссертации докладывались на

1. Международной конференции "Graphicon 2002", г. Нижний Новгород, 2002.

2. Конференции "Лазеры. Измерения. Информация", г. Санкт-Петербург, 2003.

3. Международной конференции "Gгaphicon 2003", г. Москва, 2003.

4. Международной конференции "Gгaphicon 2004", г. Москва, 2004.

5. Заседании кафедры математической физики факультета ВМиК МГУ им. М.В. Ломоносова, г. Москва, 2005.

Публикации

По теме диссертации опубликовано девять научных работ, список публикаций приведён в конце автореферата.

Структура и объём работы

Диссертация состоит из введения, четырех глав, заключения, списка таблиц, списка иллюстраций и библиографического списка использованной литературы. Общий объём работы 180 страниц. Список литературы включает 60 наименований.

Содержание работы

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

Первая глава посвящена описанию математического аппарата и реализации основных оптимизированных и быстрых проекционных схем, базирующихся на разложении по функциям Чебышёва-Эрмита: одномерной и двумерной, иерархической одномерной и двумерной, фовеационной одномерной и двумерной.

В разделе 1.1 приведено описание функций Чебышёва-Эрмита, являющихся собственными функциями преобразования Фурье и образующих полную в

°°'С0) ортонормированную систему функций:

(-1)ие*2/2 ¿"(е-*1)

л/2

Ахп

Каждая из функций Чебышёва-Эрмита локализована с вычислительной точки зрения на конечном отрезке. Из известных предельных оценок для полиномов Чебы-шёва-Эрмита с помощью формулы Стирлинга в этом же разделе выводятся предельные оценки для функций Чебышёва-Эрмита:

В разделе 12 рассматриваются двумерные функции Чебышёва-Эрмита, тоже являющимися собственными функциями преобразования Фурье:

У„т(х,У) =

НУ

п+т х2 П+у1 /2

¿"(е-х) с1т(е-у)

4т*т п\т\п ¿х"

¿У

В разделе 1.3 приведено описание проекционных методов Чебышёва-Эрмита. основанных на разложении исходной функции интенсивности (в случае обработки изображений) или амплитуды (в случае обработки речи) в ряд Фурье по функциям Чебышёва-Эрмита. Разложение исходной функции в ряд ведётся на интервале, соответствующем выбранному числу членов разложения.

В разделе 1.4 описывается и обосновывается представление двумерного проекционного метода Чебышёва-Эрмита как суперпозиции одномерных проекционных методов Чебышёва-Эрмита.

В разделе 1.5 построены методы оценки числа функций Чебышёва-Эрмита, локализованных с вычислительной точки зрения на заданном интервале.

В разделе 1.6 описывается программная реализация оптимизированного алгоритма кодирования /декодирования. Приводится сравнение производительности с дискретным преобразованием Фурье.

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

В разделе 1.8 рассматривается адаптация алгоритмов кодирования / декодирования для многопроцессорных вычислительных комплексов.

В разделе 1.9 рассказывается об ускорении проекционного метода Чебышё-ва-Эрмита с помощью применения квадратуры Гаусса-Эрмита к вычислению коэффициентов Чебышёва-Эрмита:

Для обхода факта сильного возрастания значений факториала и полиномов Чебы-шёва-Эрмита с ростом N автором было предложено выразить полученное для коэффициентов выражение в следующей форме:

где ) - массив констант {*„, )-Ч/„(хт)1 )

Ошибка при использовании квадратуры Гаусса-Эрмита имеет вид

В связи с тем, что при кодировании массивов (f(x)- дискретная функция) с помощью быстрого кодирования Чебышева-Эрмита часть данных игнорируется, для улучшения качества кодирования было предложено заменить исходную функцию

Дхт) на ее среднее арифметическое в £т -окрестности точки Хт (что эквивалентно наложению сглаживающего фильтра на исходную функцию) Ниже приведен график ускорения, полученного при быстром кодировании 512-ти массивов каждый по 512 элементов, от числа функций В качестве единицы измерения была выбрана скорость работы оптимизированного алгоритма кодирования (0 089 секунды при 32 функциях на процессоре Pentium-M 1500MHz)

В разделе 1.10 рассматривается задача фовеации сигнала - динамического распределения точности аппроксимации сигнала. В общем случае оператор фо-веации Т функции имеет следующий вид:

где - ядро оператора.

Ниже на рисунке приведён пример фовеации функции с точкой фовеации У = 0.

Для фовеации дискретного сигнала [ 0, IV — 1 ] в точке У по П функциям Че-

бышёва-Эрмита локализованным на отрезках шагов с

коэффициентом уменьшения области фовеации между слоями было предложено следующее ядро

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

В разделе 2.1 приведён алгоритм разделения низкочастотной и высокочастотной частей изображения с помощью одномерной и двумерной проекционных схем, основанных на разложении в ряд по функциям Чебышёва-Эрмита, а также рассмотрено их сопоставление с дискретным преобразованием Фурье.

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

В разделе 2.3 рассматривается задача увеличения / уменьшения изображений на базе двумерной проекционной схемы. Основная идея применения проекционного метода фильтрации к увеличению / уменьшению изображений сводится к переводу изображений с дискретного пространства в двумерное пространство коэффициентов Чебышёва-Эрмита с последующим отображением результата на дискретную сетку нужного разрешения.

В разделе 2.4 рассмотрена устойчивость коэффициентов Чебышёва-Эрмита при сжатии изображений форматом JPEG.

В разделе 2.5 рассмотрена задача параметризации информации с помощью двумерной проекционной схемы для поиска картин по базе данных. В качестве исходных данных выступали цифровые фотоснимки картин и гравюр. Тестовая база данных содержала информацию о 4100 цифровых изображениях. Каждое изображение перед обработкой проходило нормализацию - в автоматическом режиме удалялись фон и эффекты поворота, сдвига, параллелограмма, перспективы, освещённости. Для параметризованного поиска нормализованных изображений было проведено сравнительное тестирование для быстрого проекционного метода Чебышёва-Эрмита, проекционного метода Чебышёва-Эрмита и дискретного преобразования Фурье. Проекционные методы показали лучшую устойчивость к шуму, а быстрый проекционный метод показал 11 -кратное ускорение кодирования.

В разделе 2 6 рассмотрена задача фовеации изображений с помощью двумерной фовеационной проекционной схемы, а также приведено её сопоставлении с наиболее известными схемами фовеации. Для проекционной фовеации изображений используется иерархическая схема фовеации: к изображению применяется последовательность двумерных проекционных методов Чебышёва-Эрмита вокруг точки фовеации с постепенным уменьшением области фовеации, а при декодировании происходит наложение дополнительного сглаживающего фильтра для стирания границ между областями фовеации на разных слоях. При этом, при фовеации изображения с использованием К слоев происходит сжатие полезной информации в К раз. Более того, скорость кодирования / декодирования тоже возрастает приблизительно в К раз для оптимизированного алгоритма кодирования и приблизительно в 2К раз для быстрого алгоритма кодирования Ниже приведены примеры фовеации изображения «Лена», где точкой фовеации У выступает правый глаз Предложенный алгоритм проекционной фовеации изображений показывает достаточную гибкость для выбора наиболее подходящего режима сжатие / скорость / качество, а также для задач, связанных с принудительной фокусировкой объектов.

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

Четвертая глава посвящена описанию программного обеспечения, созданного на базе быстрого проекционного метода для решения задач фильтрации и увеличения / уменьшения изображений, динамического распределения точности аппроксимации (фовеации) изображений, поиска изображений из класса картин по базе данных и индексации говорящих с использованием средств пакета проектирования Rational XDE 2003 (приводятся упрощённая диаграмма классов и основные диаграммы последовательности и состояний) и пакета программирования MS Visual C++.NET 2003.

В Заключении сформулированы основные результаты диссертации.

Основные результаты

В результате написания диссертационной работы были получены следующие основные результаты:

1. Разработан быстрый проекционный метод Чебышёва-Эрмита.

2. Построены алгоритмы поиска изображений из класса картин по базе данных, динамического распределения точности аппроксимации (фовеации) изображений и индексации говорящих, основанные на проекционном методе Чебышёва-Эрмита.

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

Публикации по теме диссертации

[1] Andrey Krylov, Danil Kortchagine, "Projection filtering in image processing", Proceedings Int. Conference Graphicon 2000, Moscow, 2000, pp. 42-45.

[2] A.O. Жирков, Д.Н. Корчагин, А.С. Лукин, А.С. Крылов, Ю.М. Баяковский, "Нейросетевой анализ и сопоставление частотно-временных векторов на основе краткосрочного спектрального представления и адаптивного преобразования Эрмита", препринт №87 ИПМ, 2001.

[3] A. Krylov, D. Kortchagine, A. Lukin, "Streaming waveform data processing by Hermite expansion for text-independent speaker indexing from continuous speech", Proceedings Int. Conference Graphicon 2002, Nizhny Novgorod, 2002, pp. 91-98.

[4] A.O. Жирков, Д.Н. Корчагин, А.С. Лукин, А.С. Крылов, Ю.М. Баяковский, "Графический метод представления и нейросетевое распознавание частотно-временных векторов речевой информации", журнал "Программирование", 2003, стр. 41-52.

(A.O. Zhirkov, D.N. Kortchagine, A.S. Lukin, A.S. Krylov, Yu.M. Bayakovski, "Graphic Representation Method and Neural Network Recognition of Time-Frequency Vectors of Speech Information", journal "Programming and Computer Software", vol. 29, no. 4, 2003, pp. 210-218.)

[5] M. Najafi, A. Krylov, D. Kortchagine, "Image deblocking with 2-D Hermite transform", Proceedings Int. Conference Graphicon 2003, Moscow, 2003, pp. 180183.

[6] Vitaliy F. Barybin, Andrey S. Varavva, Marina U. Gerasimenko, Danil N. Kort-chagine, Andrey S. Krylov, Vladimir Y. Mendeleev, Sergey N. Skovorod'ko, "Structure comparison of images of laser emission passing through tissue in vivo and fluoroplastic", proc. SPIE vol. 5066, Lasers for Measurements and Information Transfer 2002,2003, 7 pages, pp. 113-119.

[7] Andrey S. Varavva, Sergey N. Skovorod'ko, Vladimir Y. Mendeleev, Vitaliy F. Barybin, Marina U. Gerasimenko, Danil N. Kortchagine, Andrey S. Krylov, "Estimation of biological mediums structure", proc. SPIE vol. 5138, Photon Migration and Diffuse-Light Imaging, 2003, 9 pages, pp. 342-350.

[8] Andrey S. Varavva, Sergey N. Skovorod'ko, Vladimir Y. Mendeleev, Vitaliy F. Barybin, Marina U. Gerasimenko, Danil N. Kortchagine, Andrey S. Krylov, "Particularities of diffraction filtration by tissues in coherent and incoherent illumination", proc. SPIE vol. 5381, Lasers for Measurements and Information Transfer 2003,2004, 8 pages, pp. 313-321.

[9] A. Krylov, D. Kortchagine, "Hermite Foveation", Proceedings Int. Conference Graphicon 2004, Moscow, 2004, pp. 166-169.

Тираж 100 экз

913

Введение.

Глава 1. Описание проекционных методов.

1.1. Определение одномерных функций Чебышёва-Эрмита.

1.2. Определение двумерных функций Чебышёва-Эрмита.

1.3. Одномерный и двумерный проекционные методы Чебышёва-Эрмита

1.4. Двумерный проекционный метод Чебышёва-Эрмита как суперпозиция одномерных проекционных методов Чебышёва-Эрмита.

1.5. Выбор оптимального отрезка интегрирования.

1.6. Оптимизированный алгоритм кодирования/декодирования информации.

1.7. Иерархическое кодирование.

1.8. Адаптация алгоритма для многопроцессорных вычислительных комплексов.

1.9. Быстрый проекционный метод Чебышёва-Эрмита.

1.10. Фовеация.

Глава 2. Анализ и обработка изображений.

2.1. Разделение высокочастотной и низкочастотной частей изображения

2.2. Фильтрация изображений.

2.3. Увеличение/уменьшение изображений.

2.4. Устойчивость коэффициентов Чебышёва-Эрмита при сжатии изображений форматом JPG.

2.5. Параметризация информации для поиска картин в базе данных

2.6. Фовеация изображений.

Глава 3. Индексация говорящих.

3.1. Структура базы данных.

3.2. Алгоритм.

3.3. Пример индексации беседы 3-х человек.

3.4. Полученные результаты.

Глава 4. Структура и описание реализующей программы.

4.1. Диаграммы последовательности.

4.2. Диаграммы состояний.

4.3. Описание интерфейса и внешний вид.

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

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

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

Научная новизна работы:

• Разработан быстрый проекционный метод Чебышёва-Эрмита, основанный на ускорении проекционного метода Чебышёва-Эрмита с помощью квадратуры Гаусса-Эрмита.

• Составлено ядро динамического распределения точности аппроксимации (фовеации) для проекционного метода Чебышёва-Эрмита, предложена иерархическая схема для программной реализации проекционной фовеации.

• Разработан проекционный метод для поиска картин по базе данных, основанный на обработке запроса по цифровому фотоснимку.

• Разработан проекционный метод индексации говорящих.

Теоретическая и практическая значимость работы:

• Проведён сравнительный анализ эффективности предложенного быстрого проекционного метода, оптимизированного проекционного метода и ДПФ.

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

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

Основные результаты диссертации докладывались на международных конференциях "Graphicon" в 2000, 2002, 2003 и 2004 годах, на конференции "Лазеры. Измерения. Информация" в 2003 году, на заседании кафедры математической физики факультета ВМиК МГУ им. М.В. Ломоносова в 2005 году.

По теме диссертации опубликовано девять научных работ.

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

Разложение сигнала в ряд по функциям Чебышёва-Эрмита позволяет производить анализ сигнала и его преобразование Фурье одновременно, так как функции Чебышёва-Эрмита являются собственными функциями преобразования Фурье. Также необходимо подчеркнуть, что совместная локализация функций Чебышёва-Эрмита в частотном и временном пространствах [1] делает рассмотренные методы достаточно устойчивыми к информационным ошибкам. Более того, функции Чебышёва-Эрмита образуют полную ортонормированную в L2(-go, со) систему функций. Всё это делает применимость рассмотренных в диссертационной работе методов к обработке мультимедиа информации конкурентоспособной с наиболее популярными на сегодняшний момент методами обработки изображений и речи.

Функции Чебышёва-Эрмита широко используются в математике, где разложение по функциям Чебышёва-Эрмита также называют рядами Грамма-Шарлье [2], [3]. Эти разложения также используются в обработке изображений [4], [5], [6] и речи [7], [8], [9]. Однако, эти ряды часто "ограничены первыми несколькими членами". Та же ситуация типична для использования функций Чебышёва-Эрмита в физике [10]. В последнее время разложение по функциям Чебышёва-Эрмита находит применение в медицине как для сопоставления полученных результатов [11], [12], [13], так и для выявления скрытых особенностей [14], [15], а также в других областях науки.

Основная часть данной работы разделена на четыре главы: описание методов проекционной фильтрации (первая глава), анализ и обработка изображений (вторая глава), индексация говорящих (третья глава) и структура и описание реализующего программного комплекса (четвёртая глава).

В первой главе, наряду с рассмотрением оптимизированных и быстрых схем проекционной фильтрации, основанных на разложении по функциям Чебышёва-Эрмита, приведена адаптация некоторых алгоритмов для многопроцессорных комплексов.

Ещё в 70-х годах XX века функции Чебышёва-Эрмита казались потерянными среди полиномов Чебышёва-Эрмита и функций параболического Цилиндра [16]. Это было какое-то историческое злоключение, что дифференциальное уравнение, которому удовлетворяют функции параболического цилиндра, было стандартизовано Вебером (Weber) как у" + (п + 1/2-х2/4)у = 0 а не в виде уравнения у" + (2п + \-х2 )у = 0, соответствующего функциям Чебышёва-Эрмита. Разница может показаться тривиальной, но эффект такой стандартизации оставлял туманным свойство, что функции Чебышёва-Эрмита являются собственными функциями преобразования Фурье. Даже несмотря на важность этого факта, осознанного Винером (Wiener) в его книге [17] в 1933 году, Эберлейн (Eberlein) [16] не смог найти эту информацию в справочнике того времени.

Долгое время применение функций Чебышёва-Эрмита было ограничено всего несколькими членами как, например, в методе, основанном на преобразовании Эрмита [4], [5], и только в последнее время количество используемых функций возросло (алгоритмы, представленные в данной работе могут использовать до 750 функций Чебышёва-Эрмита, хотя при необходимости и это ограничение может быть снято). Стоит подчеркнуть, что предложенная в диссертационной работе методика ускорения проекционного метода может быть эффективно использована и для ускорения преобразования Эрмита.

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

Идея сопоставления с образцами в той или иной форме широко применяется в различных коммерческих приложениях. Средства распознавания рукописного ввода позволяют пользователям карманных компьютеров Palm преобразовывать свои записи в текстовые документы. Почтовая служба США с их помощью производит автоматическую сортировку писем. Сегодня в мире разрабатывается очень много весьма интересных исследовательских проектов, цель которых заключается в повышении устойчивости и точности технологии распознавания образов. Эти методы планируется применять для идентификации человека по его фотографии, а в более общем случае - для осуществления распознавания, классификации и выборки образов на основании заложенной в компьютере информации. Такие решения, например, позволят отказаться от ненадежной методики cookie-файлов и идентифицировать посетителей сайтов при помощи размещенных повсюду Web-камер.

Технология распознавания образов базируется на сложных математических уравнениях, с помощью которых из исходных данных вычленяются некоторые блоки, которыми можно манипулировать. Эти блоки классифицируются и сравниваются с эталонной моделью. Сложность заключается в том, что процент ошибки пока весьма велик, а практическое применение разработанных приложений в бизнесе возможно, если вероятность ошибки не выходит за пределы 2-3%. В процессе дальнейшего развития, несомненно, появятся более сложные и точные алгоритмы, пересекающиеся с другими дисциплинами (в частности, с обработкой изображений, распознаванием речи и робототехникой). Рост процессорной мощи, подкрепленный совершенствованием специализированных алгоритмов, должен обеспечить дальнейшее развитие технологии.

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

Люди воспринимают пространство как "глубину" и изображения, формируемые мысленным взором, представляются им трехмерными. Однако в точных дисциплинах редко применяется обработка трехмерных изображений, что объясняется очевидными техническими трудностями работы с ними, а также недостаточным пониманием природы процесса восприятия изображений. В большинстве практических приложений исследователи имеют дело с квазитрехмерными изображениями, когда по двум известным параметрам, например частоте и времени, строится некая двумерная матрица, значения которой определяются значениями третьего известного параметра, например мощностью или амплитудой рассчитанного мгновенного спектра. Особенно это касается слухового восприятия, которое, как было показано в ряде исследований еще со времён X. Гельмгольца, может быть описано моделью спектрального анализатора.

Рассмотрим историю развития методов автоматического распознавания речи более подробно [18].

Первым устройством, предназначенным для распознавания речи, была электронная игрушка "Радио Рекс", выпушенная в 1920 году. Целью распознавания было реагирование на имя "Рекс". Критерием произнесения этого имени был энергетический всплеск звуковой волны, с частотой более 500 Гц.

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

В 40-е - 50-е года большое внимание исследователей уделялось анализу структур, полученных в процессе обработки выходных сигналов линейки аналоговых фильтров.

Следующим исторически значимым событием было создание изобретателями из Bell Labs в 1952 году первой системы, ориентированной на диктор-зависимое распознавание цифр. В основе устройства было заложено измерение двух формант, полученных из спектра.

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

В 1959 году Денес ввёл вероятностную грамматическую модель, идея которой заключается в зависимости вероятности появления того или иного слова от предыдущих слов.

В 60-х в ряде физиологических исследований была подтверждена целесообразность "скользящего" спектрального анализа речевых сигналов. В работах Д. Розе отмечено, что каждые 60 - 100 мкс слуховая система человека как бы опрашивает состояние "гребенки" физиологических фильтров [19].

В 1963 году Виндроу применил нейронные сети к распознаванию цифр, а в 1964 Мартин применил нейронные сети к распознаванию фонем.

Большой шаг на пути к дискретному, компьютерному анализу речи дала работа [20] 1965 года по эффективному алгоритму дискретного преобразования Фурье (ДПФ), названному алгоритмом быстрого преобразования Фурье (БПФ).

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

Альтернативным методу кепструма является кодирование коэффициентов БПФ методом линейного предсказывающего кодирования (LPC), которое было известно до появления методов распознавания речи и поэтому явилось одним из первых методов её анализа [22].

Разные произношения одного и того же слова имели разные продолжительности по времени, одно из предложенных решений соотнесения образов, полученных на этапе тренировки и полученных на этапе эксплуатации - использование динамического программирования [23].

В 1969 Джон Пирс (директор отдела научных исследований в Bell Labs) написал письмо "Куда движется Распознавание речи?", в котором утверждал, что нужно заниматься не распознаванием, а пониманием речи, как это делают люди.

Большая часть первых исследований в области применения скрытых Марковских моделей (СММ) в области распознавания речи, принадлежит исследовательской группе IBM, которая сделала ряд публикаций, начиная с 1971 года. Одна из первых хороших разработок была система "Дракон", вышедшая в 1975 году [24], акустическая модель которой базировалась на LPC коэффициентах.

Большой проект по пониманию речи был организован ARPA, которая выделила на это 15 млн. долларов. Ею была поставлена задача: размер словаря - 1000 слов, тип речи - слитная, детерминированная грамматика, независимость от типа голоса, критерий достижения -процент ошибок < 10%. Множество институтов было подключено к этой программе, достиг цели только университет Карнеги-Меллона, в котором усовершенствовали систему "Дракон" внедрением синтаксической и грамматической информации [25].

В 80-х большинство усилий было сосредоточено на увеличении количества слов и на ужесточении к свойствам систем без сильных изменений в методологии распознавания. В 1986 вышла первая версия общей тестовой базы, со следующими параметрами: 61 фонема, 630 голосов по 10 фраз, две из которых были одинаковые у всех говорящих. Сегментация происходила автоматически, но затем проверялась и исправлялась вручную.

В 1984 году был создан CD-ROM с тестовой базой, который получала любая исследовательская группа, желающая принять участие в соревновании, а результаты тестов афишировались. В результате с 60-тысячным словарём речь распознавалась в реальном времени с ошибкой менее 10% (результат, достигнутый в 1998 году). Такой процент распознавания достигнут при чтении текста, для разговорной речи результаты значительно хуже.

После статьи 1969 года, где говорилось о неспособности персептрона представить операцию исключающего "или", об искусственных нейронных сетях долго не писали. Взрыв интереса к нейронным сетям произошёл в 80-х в связи с методами обратного распространения ошибки в многослойных персептронах. Появились статьи по распознаванию звонких и шипящих [26], гласных и согласных звуков [27].

В последнее время много работ посвящено гибридным схемам СММ (Скрытые Марковские Модели) + нейронные сети, где сети используются для вычисления вероятности той или иной фонемы, а СММ для отыскания возможных словосочетаний, составленных из фонем.

В 90-х годах ARPA перевёл своё внимание с чтения журнала на распознавания текста из радионовостей. Это ещё более сложная задача: разные стили разговора, начиная от равномерного чтения до разговорной речи; различные акустические условия, от студии до шумных улиц. Однако лучшим системам распознавания такая задача оказалась не под силу.

Продолжаются работы, начатые ещё в 70-ые, где речь рассматривается не как совокупность коротких фреймов одинаковой длины, а как совокупность сегментов, представляющих собой набор фонем [28].

Системы, разрабатывающиеся в 80-х, были сильно зависимы от линейных (по времени) фильтраций сигнала. Последние работы направлены на уменьшение этой зависимости, в том числе на уменьшение зависимости от типа микрофона и акустических шумов [29]. Исследуются работы в направлении уменьшения влияния выразительности стиля произношения, влияния расстояния от микрофона и других параметров.

В конце 2001 года компании Intel и Cognitive Technologies анонсировали результаты реализации инвестиционного проекта по развитию систем распознавания русской речи. Впервые в России был создан обширный инструментарий для разработки систем распознавания речи, который включает крупный речевой корпус русского языка RuSpeech объемом 15 Гбайт. RuSpeech - речевая база данных, содержащая как отдельные фонемы, так и их последовательности. В состав RuSpeech вошло более 50 тыс. предложений с фонетической разметкой каждой произнесенной фразы.

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

• Фильтрация с помощью алгоритмов blur [32].

• Структурно-зависимое удаление квадрируемости.

• Использование ДПФ и БПФ.

• Поиск по цветовому раскладу, соответствующему исходному изображению.

• Поиск по процентному содержанию основных цветов (красный, зеленый, синий).

• Поиск по заданной цветовой маске.

• Текстурный поиск.

• Поиск по заданному эскизу.

• Контурный поиск [33].

• Поиск лиц.

• Объектный поиск.

• Поиск фиксированных изображений с использованием Вейвлет преобразований. для обработки речи:

• Скрытые Марковские модели.

• Искусственные нейронные сети.

• Использование БПФ.

• Анализ кепструма.

• Линейное предсказывающее кодирование (LPC).

• Сведение распознавания речи к распознаванию образов.

Заключение

В результате написания диссертационной работы были получены следующие основные результаты:

• Разработан быстрый проекционный метод Чебышёва-Эрмита.

• Построены алгоритмы поиска изображений из класса картин по базе данных, динамического распределения точности аппроксимации (фовеации) изображений и индексации говорящих, основанные на проекционном методе Чебышёва-Эрмита.

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

Рассмотренные в данной работе проекционные схемы могут использоваться как для кодирования и сжатия изображений и речи, так и для их фильтрации, трассировки контуров, определения структур и свойств объектов. Иерархические схемы могут использоваться как для повышения устойчивости кодирования, так и для ускорения обработки запросов по большим базам данных. Фовеационные схемы могут использоваться для сжатия данных с потерей информации для online конференций при использовании «узких» каналов связи, а также в задачах, связанных с принудительной фокусировкой требуемых объектов. Быстрые схемы позволяют значительно сократить время кодирования информации, благодаря применению квадратуры Гаусса-Эрмита к вычислению коэффициентов Чебышёва-Эрмита, но при этом немного уступают в качестве кодирования оптимизированным проекционным схемам.

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

Для задач фильтрации, увеличения и уменьшения изображений рассмотренный подход стоит в одном ряду с другими распространёнными алгоритмами решения данных задач. Выделить фаворитов здесь достаточно сложно, так как каждый из алгоритмов справляется с поставленными задачами достаточно хорошо, но со своими особенностями, положительность или отрицательность которых зависит от предпочтений восприятия конкретным индивидуумом. Хотя стоит отметить, что рассмотренные схемы проекционного кодирования также как и дискретное преобразование Фурье подвержены эффекту Гиббса, проявление которого в некоторых случаях может свести все плюсы на нет.

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

В задаче фовеации изображений полученные результаты тоже можно считать положительными, так как качество получаемых на выходе изображений не хуже, а иногда и значительно лучше, чем у изображений, полученных при фовеации другими методами. Что касается сжатия, то предложенный подход позволяет менять его в достаточно широких пределах, причём даже при коэффициентах сжатия порядка 144 раз, результат фовеации остается вполне приемлемым.

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

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

1. D. Gabor, "Theory of Communication", J. IEE, vol. 93, part III, no. 26, London, 1946, pp. 429-457.

2. Szego Gabor, "Orthogonal Polynomials", American Mathematical Society Colloquium Publications, vol. 23, NY, 1959.

3. Jeckson Dunham, "Fourier Series and Orthogonal Polynomials", Cams Mathematical Monographs, No. 6, Chicago, 1941.

4. Jean-Bernard Martens, "The Hermite Transform Theory", IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 38, 1990, pp. 1595-1606.

5. Jean-Bernard Martens, "The Hermite Transform Applications", IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 38, 1990, pp. 1607-1618.

6. Andrey Krylov, Danil Kortchagine, "Projection filtering in image processing", Proceedings Int. Conference Graphicon 2000, Moscow, 2000, pp. 42-45.

7. A.O. Жирков, Д.Н. Корчагин, A.C. Лукин, A.C. Крылов, Ю.М. Баяковский, "Нейросетевой анализ и сопоставление частотно-временных векторов на основе краткосрочного спектрального представления и адаптивного преобразования Эрмита", препринт №87 ИПМ, 2001.

8. А.О. Жирков, Д.Н. Корчагин, А.С. Лукин, А.С. Крылов, Ю.М. Баяковский, "Графический метод представления и нейросетевое распознавание частотно-временных векторов речевой информации", журнал "Программирование", 2003, стр. 41-52.

9. Andrey Krylov, Anton Liakishev, "Numerical Projection Method for Inverse Fourier Transform and its Application", Numerical Functional Analysis and Optimization, vol. 21, 2000, pp. 205-216.

10. W.F. Eberlein, "A New Method for Numerical Evaluation of the Fourier Transform", Journal of Mathematical Analysis and Application 65, 1978, pp. 80-84.

11. H. Винер, "Интеграл Фурье и некоторые его приложения", М.: Физматгиз, 1963.

12. Ben Gold, Nelson Morgan, "Speech And Audio Signal Processing", John Wiley & Sons Inc, 2000, pp. 9-65.

13. B.H. Плотников, A.B. Белинский, В.А. Суханов, Ю.Н. Жигулевцев, "Цифровые анализаторы спектра", М.: Радио и связь, 1990.

14. J. Cooley, J. Tukey, "An algorithm for the machine computation of complex Fourier series", Math. Comput. 19, 1965, pp. 297-301.

15. A. Oppenheim, R. Schafer, T. Stockham, "Nonlinear filtering of multiplied and convolved signals", Proc. IEEE 56, 1968, pp. 1264-1291.

16. B. Atal, S. Hanauer, "Speech analysis and synthesis by prediction of the speech wave", Acoust. Soc. Am. 50, 1971, pp. 637-655.

17. T. Vintsyuk, "Element-wise recognition of continuous speech composed of words from a specified dictionary", Kibernetica 7, 1971, pp. 133143.

18. J. Baker, "The DRAGON system an overview", IEEE Trans. Acoust. Speech Signal Process. 23, 1975, pp. 24-29.

19. H. Sakoe, S. Chiba, "Dynamic programming algorithm optimization for spoken word recognition", IEEE Trans. Acoust. Speech Signal Process. 26, 1978, pp. 43-49.

20. A. Gevins, N. Morgan, "Ignorance-based system", in Proc. IEEE Int. Conf. Acoust. Speech Signal Process., San Diego, 1984, pp. 39A.5.1-39A.5.4.

21. R. Lippmann, B. Gold, "Neural classifiers useful for speech recognition", Proc. IEEE First Int. Conf. Neural Net., San Diego, 1987, pp. 417422.

22. M. Ostendorf, I. Bechwati, O. Kimball, "Context modeling with the stochastic segment model", Proc. IEEE Intl. Conf. Acoust. Speech Signal Process., San Francisco, 1992, pp. 389-392.

23. M. Gales, S. Young, "Robust speech recognition in additive and convolutional noise using parallel model combination", Comput. Speech Lang. 9, 1995, pp. 289-307.

24. Shapiro, Stockmane, "Content-Based Image Retrieval", Computer Vision 2000 Conference proceedings, pp. 249-274.

25. Simone Santini, Ramesh Jain, "Similarity is a Geometer", Multimedia Tools and Applications 1997 Conference proceedings, pp. 277-306.

26. Mario Bertero, Patrizia Boccacci, "Introduction to Inverse Problems in Imaging", IOP Publishing Ltd, 1998, pp. 50-75.

27. John P. Boyd, "Chebyshev and Fourier Spectral Methods", Second Edition, University of Michigan, 2000.

28. Andrey S. Krylov, Andrey V. Vvedenskii, "Software package for radial distribution function calculation", J.Non-Crystalline Solids 192-193, 1995, pp. 683-687.

29. А.С. Крылов, А.В. Лякишев, "Неравенство для норм функций Эрмита на конечном интервале".

30. Г. Сеге, "Ортогональные многочлены", М.: Физматгиз, 1962.

31. А.Ф. Никифоров, В.Б. Уваров, "Основы теории специальных функций", М.: Наука, 1974.

32. Г. Бейтмен, А. Эрдейи, "Высшие трансцендентные функции", М.: Наука, 1974, Т.П.

33. C.V.L. Charlier, "Application de la Theorie des Probabilites a PAstronomie", Gauthier-Villars, Paris, 1931.

34. M. Абрамовича, И. Стиган, "Справочник по специальным функциям", М.: Наука, 1979.

35. Л.П. Ярославский, "Введение в цифровую обработку изображений", М.: Сов. радио, 1979, стр. 106-116.

36. В.И. Крылов, "Приближённое вычисление интегралов", М.: Наука, 1967, стр. 116-147.

37. Zhou Wang and Alan Conrad Bovik, "Embedded Foveation Image Coding", IEEE Transactions on Image Processing, vol. 10, No. 10, October 2001.

38. Ee-Chien Chang, Chee Yap, "A Wavelet Approach to Foveating Images", Proc. 13th ACM Symp. Computational Geometry, 1997, pp. 397-399.

39. Ee-Chien Chang, Stephane Mallat and Chee Yap, "Wavelet Foveation", J. Applied and Computational Harmonic Analysis, vol. 9, No. 3, 2000, pp. 312-335.

40. A. Krylov, D. Kortchagine, "Hermite Foveation", Proceedings Int. Conference Graphicon 2004, Moscow, 2004, pp. 166-169.

41. Graham Saxby, "The Science of Imaging: An Introduction", IOP Publishing Ltd, 2002, pp. 65-78.

42. Д.С. Ватолин, "Алгоритмы сжатия изображений", Москва, МГУ,ВМиК, 1999.

43. M. Najafi, A. Krylov, D. Kortchagine, "Image deblocking with 2-D Hermite transform", Proceedings Int. Conference Graphicon 2003, Moscow,2003, pp. 180-183.

44. Roberto Castango, Stefano Marsi, Giovanni Ramponi, "A Simple Algorithm For The Reduction of Blocking Artefacts in Image and Implementation", IEEE Trans, on Consumer Electronics, vol. 44, No. 3, 1998, pp. 1062-1070.

45. T. Meier, King N. Ngan, Greg Gerbin, "Reduction of Coding Artifacts at Low Bitrates", SPIE International Conference on Communications and Image Processing, San Jose, U.S.A., 1998, pp. 241-251.

46. А. Разумовский, "Компьютерная обработка звука", Москва, Нолидж, 2000.

47. A. Krylov, D. Kortchagine, A. Lukin, "Streaming waveform data processing by Hermite expansion for text-independent speaker indexing from continuous speech", Proceedings Int. Conference Graphicon 2002, Nizhny Novgorod, 2002, pp. 91-98.

48. Wendy Boggs, Michael Boggs, "Mastering UML with Rational Rose", Sybexlnc., 1999.

49. IBM Corp., "IBM Rational Rose XDE Developer", IBM Corp.,2004.

50. Microsoft Corp., "MSDN", http://msdn.microsoft.com/, 2005.

51. B.B. Яишин, Г.А. Калинин, "Обработка изображений на языке Си для IBM PC: Алгоритмы и программы", М.: Мир, 1994, стр. 10-15.

52. IBM Corp., "Develop fast, reliable code with IBM Rational PurifyPlus", IBM Corp., 2003.

53. Дейл Роджерсон, "Основы COM", 2-ое издание, М.: Русская Редакция, 2000.