Введение к работе
Диссертация посвящена разработке и исследованию метода автоматического построения (синтеза) вычислительной процедуры локальной обработки изображений по эмпирическим данным на основе иерархической регрессии и алгоритмов локального дискретного вейвлет-преобразования.
Актуальность темы
Локальная обработка цифровых изображений - одно из наиболее востребованных преобразований в теории и практике цифровой обработки изображений и в теории компьютерного зрения. Под локальной обработкой обычно понимают такое преобразование изображения, в котором каждый отсчет выходного изображения формируются на основе однозначного преобразования множества отсчетов входного изображения, попавших в некоторую его окрестность (по координатам). Исторически первыми для обработки использовались линейные локальные методы, допускающие построение оптимальных в некотором смысле процедур обработки. Математические методы построения и реализации таких вычислительных процедур рассматривались такими российскими и зарубежными учеными, как: R. Gonzales, D. Forsyth, A. Oppenheim, R. Schafer, R. Mersereau, W. Pratt, R. Woods, Л.М. Гольденберг, В.Г. Лабунец, В.В. Сергеев, В.А. Сойфер, Л.П. Ярославский и др. Однако, появление новых задач обработки цифровых сигналов (обработка видеоинформации, звука, космических снимков и т.п.), задач обработки больших объемов информации в режиме реального времени, а также требование повышения эффективности обработки привели к необходимости использования нелинейных преобразований. Вопросам построения и реализации локальных нелинейных процедур обработки посвящены работы таких ученых, как: С. Cowan, S. Geiser, Е. Glaser, P. Grant, R. Lucky, S. Haiken, С Jakowatz, W. Masenten, B. Widrow, A.H. Горбань, И.С. Грузман, A.A. Ланнэ, B.B. Сергеев, Л.П. Ярославский и др. Один из наиболее распространенных на настоящий момент подходов заключается в реализации кибернетического принципа «черного ящика» (термины других авторов: обработка через распознавание, обработка по прецедентам), когда само преобразование и его параметры определяются на основании анализа входных и выходных сигналов или изображений. Несмотря на обилие в рамках этого подхода частных решений, формализованный регулярный подход к построению вычислительных процедур для конкретной практической задачи до настоящего времени отсутствует. Это позволяет утверждать об актуальности выбранной темы диссертационной работы.
Одним из известных подходов к построению относительно универсальных вычислительных процедур локальной обработки цифровых сигналов и изображений, реализующих принцип «черного ящика», является использование аппарата нейронных сетей (S. Grossberg, К. Fukushima, S. Haykin, Т. Kohonen, F. Rosenblatt, В. Widrow, N. Wiener, Ф. Уоссермен, А.И. Галушкин, Г. С. Осипов). Альтернативным, но существенно менее развитым подходом, является использование иерархических вычислительных конструкций (далее - иерархической регрессии), таких как дерево решений и дерево регрессии (Н. Ann, L. Breiman, J. Friedman, R. Olshen, С Stone, J. Quinlan, B.B. Сергеев, A.B. Чернов). Настоящая работа лежит в русле последнего из обозначенных подходов, развивая идею разработки универсального механизма построения локальных нелинейных вычислительных процедур обработки, основанных на иерархической конструкции и обеспечивающих максимум качества при заданной вычислительной сложности обработки.
Цель и задачи исследования
Целью работы является разработка и исследование метода автоматического построения вычислительной процедуры локальной обработки изображений по эмпирическим данным на основе иерархической регрессии и алгоритмов локального дискретного вейв-
лет-преобразования. Для достижения поставленной цели в диссертации решаются следующие задачи:
Анализ современного состояния в области локальной нелинейной обработки изображений, обзор существующих методов и алгоритмов, используемых для построения вычислительно эффективных процедур обработки.
Разработка и исследование алгоритмов вычислительно эффективного формирования локального описания цифрового изображения (расчета локального дискретного вейвлет-преобразования), обоснование выбора описания в зависимости от решаемой задачи. Анализ вычислительной сложности построения локального описания, выработка рекомендаций по выбору оптимального алгоритма в зависимости от глубины рассчитываемых уровней вейвлетов и от типа решаемой задачи.
Разработка вычислительной процедуры локальной обработки изображений на основе дерева регрессии/классификации. Выбор модели регрессии, используемой в терминальных вершинах, параметров процесса разбиения признакового пространства, правила остановки процесса разбиения и оценка достаточного объема обучающих данных. Анализ вычислительной сложности, показателей качества и обобщающей способности конструируемой процедуры обработки.
Разработка алгоритма автоматического построения вьшислительной процедуры локальной обработки изображений на основе иерархической регрессии и алгоритмов локального дискретного вейвлет-преобразования с ограничением по сложности обработки и максимизацией качества и обобщающей способности.
Экспериментальные исследования разработанного алгоритма и входящих в его состав методов, сравнение алгоритма с традиционными подходами (нейросетевой подход и др.), по критериям качества и вьшислительной эффективности, выработка рекомендаций по использованию результатов диссертации.
Методы исследований
В диссертационной работе используются методы линейной алгебры и математического анализа, теории вероятностей и статистического анализа, теории информации, теории цифровой обработки сигналов и изображений, распознавания образов.
Научная новизна работы
Предложены новые алгоритмы вычисления локального дискретного вейвлет-преобразования в режиме скользящего окна для одномерных и двумерных сигналов. Приведена адаптация разработанных алгоритмов для базиса Хаара и биортогональных полиномиальных сплайн-вейвлетов. Получены области вьшислительной «компетентности» для разработанных алгоритмов.
Предложен новый метод настройки параметров элементарной регрессии в терминальных вершинах дерева регрессии, основанный на регуляризации задачи с использованием информации из локальной окрестности вершины.
Предложен алгоритм автоматического построения вьшислительной процедуры локальной обработки изображений по эмпирическим данным на основе иерархической регрессии и признаков в виде локального дискретного вейвлет-разложения изображения, позволяющий избежать проблем перебора признаков, переобучения и недообучения.
Предложена методика остановки процесса построения процедуры локальной обработки на основе интервальной оценки функционала скользящего контроля качества.
Получены оценки вьшислительной сложности разработанных алгоритмов.
Практическая ценность работы
Предложенные в диссертационной работе методы и алгоритмы локальной обработки сигналов и изображений могут быть использованы в системах оперативного дистанцион-
ного зондирования, системах классификации и тематического анализа космических снимков, в геоинформационных системах, базах данных изображений и в других компьютерных системах обработки визуальной информации.
Предложенный в диссертационной работе метод построения процедуры локальной обработки изображений позволяет, с одной стороны, улучшить качество обработки изображений и многомерных сигналов за счет адаптации к локальным свойствам и более полного использования априорных данных и, с другой стороны, при заданном качестве обработки радикально снизить ее вычислительную сложность.
Разработанные алгоритмы быстрого расчета локального дискретного вейвлет-преобразования могут быть использованы для решения задач распознавания образов.
Реализация результатов работы
Результаты диссертации использованы при выполнении 17 госбюджетных и хоздоговорных НИР в Самарском государственном аэрокосмическом университете, Институте систем обработки изображений РАН, Некоммерческом партнерстве «Центр космической геоинформатики» и ОАО «Самара-Информспутник».
Апробация работы
Основные результаты диссертации были представлены на конференциях:
на 6-1 Ой международных конференциях "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ 6-10), Великий Новгород - 2002, Ст. Петербург - 2004 и 2010, Йошкар-Ола - 2007, Н.-Новгород - 2008;
на 2-3-ей международных конференциях "Automation, control, and Information technology - Signal and image processing" (ACIT-SIP), Новосибирск - 2005, 2010;
на Всероссийском семинаре по моделированию, дифракционной оптике и обработке изображений, Самара - 2006;
на Научно-технической конференции с международным участием "Перспективные информационные технологии в научных исследованиях «ПИТ-2006»", Самара - 2006;
на 13-ой Всероссийской конференции "Математические методы распознавания образов", Ленинградская обл., г. Зеленогорск - 2007;
на 7-й всероссийской ежегодной конференции "Современные проблемы дистанционного зондирования Земли из космоса", ИКИ РАН, Москва - 2009;
на 20-ой международной Конференции Распознавания Образов (ICPR-2010), Турция, Стамбул-2010;
на Международной конференции с элементами научной школы "Перспективные информационные технологии для авиации и космоса «ПИТ-2010»", Самара - 2010;
на 8-й международной конференции "Интеллектуализация обработки информации" (ИОИ-2010), Республика Кипр, г. Пафос - 2010;
на Региональной научно-практической конференции, посвященной 50-летию первого полета человека в космос, Самара -2011.
Публикации
По теме диссертации опубликовано 26 работ, из них 10 в изданиях, определенных в перечне ведущих рецензируемых научных журналов и изданий ВАК Минобрнауки России, 4 работы выполнены без соавторов. При участии автора написано 17 отчетов по НИР.
Структура диссертации
Диссертация состоит из введения, четырех разделов, заключения, списка литературы и одного приложения. Она изложена на 139 страницах машинописного текста (без приложений), содержит 42 рисунка, 11 таблиц, список использованных источников из 82 наименований.
На защиту выносятся
Алгоритмы вычисления локального дискретного вейвлет-преобразования (ДВП) цифровых сигналов и изображений в режиме скользящего окна, в частности: модифицированный быстрый и рекурсивный алгоритмы локального ДВП. Конкретизация алгоритмов для базиса Хаара и биортогональных полиномиальных сплайн-вейвлетов.
Результаты сравнения вычислительной сложности алгоритмов расчета локального ДВП на основе базиса Хаара: существующий алгоритм ортогонального дискретного вейвлет-преобразования, модифицированный алгоритм и рекурсивный алгоритм. Зоны вычислительной «компетентности» алгоритмов в задаче вычисления локального ДВП.
Вычислительная процедура, реализующая локальное преобразование цифрового сигнала/изображения на основе иерархической регрессии и алгоритмов локального дискретного вейвлет-преобразования. Оценка вычислительной сложности составляющих элементов и процедуры в целом. Метод регуляризированной настройки элементарной регрессии в терминальных вершинах.
Алгоритм автоматического построения вычислительной процедуры локальной обработки изображений на основе иерархической регрессии с ограничением по вычислительной сложности обработки и максимизацией качества и обобщающей способности. Методика остановки процесса построения процедуры локальной обработки на основе интервальной оценки функционала скользящего контроля качества.
Результаты экспериментальных исследований, подтверждающие работоспособность и эффективность предложенных в работе методов и алгоритмов.
