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

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

КОПЕНКОВ Василий Николаевич

МЕТОД ПОСТРОЕНИЯ ПРОЦЕДУРЫ ЛОКАЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ИЕРАРХИЧЕСКОЙ РЕГРЕССИИ

Специальность 05.13.17 - Теоретические основы информатики

2 С ОПТ 2011

Автореферат диссертации на соискание ученой степени кандидата технических наук

САМАРА-2011

4857592

4857592

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)» и в Учреждении Российской академии наук «Институт систем обработки изображений РАН».

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

Ведущее предприятие:

доктор физико-математических наук, доцент Владислав Валерьевич Мясников

доктор технических наук, доцент Александр Григорьевич Храмов

доктор технических наук, профессор Павел Константинович Кузнецов

ФГБОУ ВПО «Ульяновский государственный технический университет»

Защита состоится "11" ноября 2011 г. в 12 часов

на заседании диссертационного совета Д 212.215.07 при федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П.Королева (национальный исследовательский университет)» (СГАУ) по адресу: 443086, Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке СГАУ.

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

Ученый секретарь

диссертационного совета ®елоконс

доктор технических наук, профессор /

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Локальная обработка цифровых изображений - одно из наиболее востребованных преобразований в теории и практике цифровой обработки изображений и в теории компьютерного зрения. Под локальной обработкой обычно понимают такое преобразование изображения, в котором каждый отсчет выходного изображения формируются на основе однозначного преобразования множества отсчетов входного изображения, попавших в некоторую его окрестность (по координатам). Исторически первыми для обработки использовались линейные локальные методы, допускающие построение оптимальных в некотором смысле процедур обработки. Математические методы построения и реализации таких вычислительных процедур рассматривались такими российскими и зарубежными учеными, как: R. Gonzales, D. Forsyth, A. Oppenheim, R. Schafer, R. Mersereau, W. Pratt, R. Woods, JIM. Гольденберг, В.Г. Лабунец, B.B. Сергеев, B.A. Сойфер, Л.П. Ярославский и др. Однако, появление новых задач обработки цифровых сигналов (обработка видеоинформации, звука, космических снимков и т.п.), задач обработки больших объемов информации в режиме реального времени, а также требование повышения эффективности обработки привели к необходимости использования нелинейных преобразований. Вопросам построения и реализации локальных нелинейных процедур обработки посвящены работы таких ученых, как: С. Cowan, S. Geiser, Е. Glaser, P. Grant, R. Lucky, S. Haiken, С. Jakowatz, W. Masenten, В. Widrow, А.Н. Горбань, И.С. Грузман, A.A. Ланнэ, В.В. Сергеев, Л.П. Ярославский и др. Один из наиболее распространенных на настоящий момент подходов заключается в реализации кибернетического принципа «черного ящика» (термины других авторов: обработка через распознавание, обработка по прецедентам), когда само преобразование и его параметры определяются на основании анализа входных и выходных сигналов или изображений. Несмотря на обилие в рамках этого подхода частных решений, формализованный регулярный подход к построению вычислительных процедур для конкретной практической задачи до настоящего времени отсутствует. Это позволяет утверждать об актуальности выбранной темы диссертационной работы.

Одним из известных подходов к построению относительно универсальных вычислительных процедур локальной обработки цифровых сигналов и изображений, реализующих принцип «черного ящика», является использование аппарата нейронных сетей (S. Grossberg, К. Fukushima, S. Haykin, T. Kohonen, F. Rosenblatt, В. Widrow, N. Wiener, Ф. Уоссермен, А.И. Галушкин, Г. С. Осипов). Альтернативным, но существенно менее развитым подходом, является использование иерархических вычислительных конструкций (далее - иерархической регрессии), таких как дерево решений и дерево регрессии (Н. Ahn, L. Breiman, J. Friedman, R. Olshen, С. Stone, J. Quinlan, В.В. Сергеев, A.B. Чернов). Настоящая работа лежит в русле последнего из обозначенных подходов, развивая идею разработки универсального механизма построения локальных нелинейных вычислительных процедур обработки, основанных на иерархической конструкции и обеспечивающих максимум качества при заданной вычислительной сложности обработки.

Цель и задачи исследования

Целью работы является разработка и исследование метода автоматического построения вычислительной процедуры локальной обработки изображений по эмпирическим данным на основе иерархической регрессии и алгоритмов локального дискретного вейв-

лет-преобразования. Для достижения поставленной цели в диссертации решаются следующие задачи:

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

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

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

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

5. Экспериментальные исследования разработанного алгоритма и входящих в его состав методов, сравнение алгоритма с традиционными подходами (нейросетевой подход i др.), по критериям качества и вычислительной эффективности, выработка рекомендаци] по использованию результатов диссертации.

Методы исследований

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

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

Предложены новые алгоритмы вычисления локального дискретного вейвлет преобразования в режиме скользящего окна для одномерных и двумерных сигналов. При ведена адаптация разработанных алгоритмов для базиса Хаара и биортогональных поли номиальных сплайн-вейвлетов. Получены области вычислительной «компетентности» дл разработанных алгоритмов.

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

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

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

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

Практическая ценность работы

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

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

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

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

Реализация результатов работы

Результаты диссертации использованы при выполнении 17 госбюджетных и хоздоговорных НИР в Самарском государственном аэрокосмическом университете, Институте систем обработки изображений РАН, Некоммерческом партнерстве «Центр космической геоинформатики» и ОАО «Самара-Информспутник».

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

Основные результаты диссертации были представлены на конференциях:

- на 6-Юй международных конференциях "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ 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 наименований.

На защиту выносятся

1. Алгоритмы вычисления локального дискретного вейвлет-преобразования (ДВП) цифровых сигналов и изображений в режиме скользящего окна, в частности: модифицированный быстрый и рекурсивный алгоритмы локального ДВП. Конкретизация алгоритмов для базиса Хаара и биортогональных полиномиальных сплайн-вейвлетов.

2. Результаты сравнения вычислительной сложности алгоритмов расчета локального ДВП на основе базиса Хаара: существующий алгоритм ортогонального дискретного вейвлет-преобразования, модифицированный алгоритм и рекурсивный алгоритм. Зоны вычислительной «компетентности» алгоритмов в задаче вычисления локального ДВП.

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

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

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Результатом первого раздела является выбор математической модели вычислительной процедуры локальной обработки. Модель предполагает разбиение локального нелинейного преобразования на два этапа: этап формирования описания фрагмента изображения (формирования признаков) и этап вычисления результатов преобразования. Выбранная модель позволяет рассматривать процесс построения вычислительной процедуры обработки как процесс обучения на основе прецедентной информации, представленной в виде набора пар «исходные данные» - «требуемое значение». Общая схема обработки представлена на рисунке 1.

Рисунок 1 - Схема обработки изображений

На первом этапе из некоторых априорных сведений об объекте (фрагменте изображения X) производится формирование определенного набора свойств, описаний или, в терминах распознавания образов, признаков у - (уй,у^—,уКА)Т, у е R* на основе преобразования Ф,: R"1*'"2 -> Ra . Такое преобразование решает две задачи. Во-первых, приведение данных к виду, удобному для обработки. Во-вторых, построение описания вычислительно эффективным образом - в режиме скользящего окна - позволяет существенно повысить вычислительную эффективность методов расчета (С.Н. Lampert, L. Tao, Y. Wei,

Н.И. Глумов, B.B. Мясников, B.B. Сергеев, A.B. Чернов и др.).

Сформированное описание фрагмента изображения на втором этапе используется для вычисления результата преобразования Ф2: R* -»К (построения изображения Z). Весь процесс построения процедуры обработки осуществляется на основе прецедентов

обработки - набора согласованных пар Ыа, , ,z(«i,«2)f (обучающей

1 l0C"i.«2J )(пьп2):е(пьп2)с0

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

- преобразования с вещественным выходом К з R и определением ошибки в виде:

- преобразования с выходом в виде K = {0,l,2,...Z-l} (конечное множество значений) и определением ошибки в виде:

где «!•

0 - область определения изображения, 6 (и,, л2) с0- сужение изображения на фрагмент

размера А/, х Л/2: 0(«,,и2) = {(и, +mt,n2 + m2) =0,M,~l,m2 = 0,M1 -lj.

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

Один из наиболее известных методов построения указанной вычислительной процедуры локальной обработки основан на использовании аппарата нейронных сетей. В диссертационной работе приведено описание нейронных сетей, указаны их достоинства и недостатки. Альтернативным методом построения, выбранным для исследования в диссертационной работе, является использование дерева регрессии (для преобразования первого типа) или дерева решений (для преобразования второго типа). Указанные деревья представляют собой иерархическую структуру, нетерминальные вершины которой определяют разбиение пространства признаков, а терминальные - элементарную функцию преобразования. Двумерная иллюстрация процесса разбиения признакового пространства представлена на рисунке 2.

Процедуры на основе деревьев регрессии - ДР (для сокращения текста изложения будем использовать это понятие для деревьев обоих типов) обладают следующими преимуществами перед нейронной сетью:

• автоматическая коррекция «архитектуры» преобразования;

• автоматическая локальная селекция признаков как следствие процесса разбиения;

• конечность процесса построения и настройки (вычислительная эффективность);

• простота параметрической настройки элементарной регрессии.

Несмотря на универсальность выбранной модели преобразования, она не решает всех проблем, возникающих на практике и имеет ряд особенностей. На этапе построения описания изображения в «окне обработки» основными вопросами являются:

- способ описания, то есть характер и количество признаков;

- возможное сокращение описания (количество и состав признаков);

Рисунок 2 - Схема разбиения признакового пространства

- вычислительная сложность алгоритмов расчета признаков.

На этапе построения иерархической регрессии основными вопросами являются:

- выбор и настройка модели регрессии и параметров древовидной структуры;

- решение проблем недообучения и переобучения, оценка объема обучающей выборки;

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

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

Во втором разделе диссертации решается задача разработки вычислительно эффективных алгоритмов формирования локального описания цифрового сигнала или изображения. Вопросам построения описания - признаков - цифровых изображений посвящено множество работ (М-К. Ни, ]. Пивег и Т. Бик, Н.И. Глумов, В.В. Мясников, В.В. Сергеев, Н.Г. Федотов и др.). Однако, в отличие от задач классификации/распознавания образов, где основным требованием к признакам является их высокая разделяющая/дискриминантная способность, в рассматриваемых в диссертационной работе задачах требования к признакам оказываются иными. В частности, одним из ключевых требований является наличие вычислительно эффективного алгоритма расчета признаков, допускающего последовательное наращивание системы признаков вплоть до полной системы.

В качестве механизма построения локального описания изображений в диссертационной работе выбрано локальное дискретное вейвлет-преобразование (ДВП). Как известно, для одномерного цифрового сигнала х{п) (п>0) с нулевым средним длины Ы, ДВП определяется формулой (I. БаиЬесЫез, в. Ма11а1, М Но15сЬпе1<1ег и др.):

"+' к-1 ( п \

\¥х{к,т) = 2 » ^(и)^^-* 1 (и*<и*0),

где \|/(/) - базисный вейвлет.

Быстрые алгоритмы вычисления ортогонального ДВП (БА ДВП) основаны на теореме в. Ма11а1, согласно которой обобщенное выражение для приведенной вычислительной сложности (количество операций на отсчет) расчета ДВП сигналов для вейвлетов уровня от ¿1 до ¿2 представимо в виде:

их (АЛ,Щ = 2(|А|+КI - - Л - 1)(М-2) - г** (м+2)),

где - Длины фильтров, М-размер окна обработки.

При этом коэффициенты вейвлет-разложения рассчитываются как: <(р)=%Кп-2р)-м>;(п), <+1(/?)=]>>(и-2/>) •<(«), / = 0,1оё2М,

где /г(")>&(") - соответствующие фильтры длинны и

В случае использования базиса Хаара сложность обработки составляет: 1/1(1^,1^) = 2(2^ -1) - в одномерном и = -1) - в двумерном случае.

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

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

Модификации, предложенные для БА ДВП, заключается в следующем: при расчете ДВП использовать коэффициенты -и>{ и и>;~, рассчитанные в предыдущих положениях «окна анализа»;

для уровней / е [1, Ц -1] производится расчет только коэффициентов ; ^ для уровней / е [¿¡,1^] производится вычисление и м/^;

^ для всех уровней / е [1, ¿2 ] рассчитывать столько разложений, сколько допускает ширина вейвлета. С учетом того, что на предыдущем шаге получены все коэффициенты м>/_,, такая процедура правомерна. Обобщенная вычислительная сложность модифицированного БА ДВП имеет вид:

В случае использования базиса Хаара сложность обработки составляет: и'Л^ЬЛ а 2Ьг - X, +1 - одномерный случай;

^-Кс

1]'г 812 -51,-5 - двумерный случай.

Второй предложенный алгоритм вычисления локального ДВП (рекурсивный) допускает представление последовательности дискретных отсчетов базисного вейвлета с использованием неоднородной линейной рекуррентной последовательности (ЛРП) вида:

Ч>(т) = ^1акЧ1(т~к) + <9,(т), / = 0,2,-1, т = 0,М-1,

где ф,{т) - коррекции ЛРП.

Общий вид рекурсивного алгоритма. Шаг 1. Предварительная обработка: у (и) = х (л - /и) ф (и).

те А ЛГ+1

Шаг 2. Постобработка: = +

с инициирующими значениями: }>(/) = О,

где Д = + /7 = 0,^-1.

В случае сплайн-полиномиального представления вейвлетов (ак =скК). Шаг 1: у(п) = ^х(п-т)<р(т).

те А

У*(п) = Ук(п-1) + У,1Лп)> _у(") = Уо(")>

где п = 0,ЛГ-1, к = К-2,0 (£>1).

Следует отметить, что рекурсивный алгоритм можно использовать и в том случае, когда вейвлет-базис не является ортогональным. Вычислительная сложность предложенного рекурсивного алгоритма:

где £ - вычислительная сложность операции «сложение-умножение».

Для базиса Хаара применимо следующее разностное уравнение, позволяющее вычислять коэффициенты разложения для каждой функции независимо и последовательно по мере смещения окна обработки (области анализа):

м>-{п) = м>~(п-\)-х{п + 2'-') + 2х (и) - * (и - 2'"1 -1), / е [Ь,, ¿2 ].

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

Ц\ (11, Ьг) = 3 (¿2 -+1) - одномерный случай. и\ (I,, Ь2) = 13 (12 - +1) - двумерный случай.

(Д, ¿2) = 7 (¿2 -+1) - базис с масштабирующим коэффициентом «3».

Полученные выражения для вычислительной сложности С/, и и\ разработанных быстрых алгоритмов локального ДВП не позволяют однозначно отдать предпочтение одному из них. В работе получены соотношения, позволяющие указать области вычислительной «компетентности» алгоритмов, то есть соотношение между Ц и Ь2, при котором конкретный алгоритм имеет преимущество по вычислительной сложности (см. рисунок 3).

Рисунок 3 - Области «компетентности» быстрых алгоритмов Решающая процедура выбора лучшего по сложности алгоритма локального ДВП: если /,, > 0,512 +1 (А/, > 2^1 М2), то используется рекурсивный алгоритм ДВП, иначе - модифицированный БА ДВП. Дополнительной особенностью рекурсивного алгоритма является то, что в случае представления вейвлета в виде обобщенного дискретного сплайна, удовлетворяющего некоторым ограничениям, возможно использование алгоритма для вычисления локального ДВП для каждого масштаба независимо.

В диссертационной работе также получены области вычислительной «компетентности» алгоритмов локального ДВП для базиса Хаара для вейвлет-разложения двумерного сигнала (изображения) и масштабирующего коэффициента «3». В таблице 1 представлены результаты экспериментального сравнения времени (в виде коэффициента отношения) работы алгоритма Малла и рекурсивного алгоритма для биортогональных сплайн-вейвлетов. Таблица 1. - Коэффициент ускорения при использовании рекурсивного алгоритма.

ы\м 2 4 8 16 32 64 128 256

104 1 2,94 4,58 8,78 9,83 17,65 23,32 38,36

3104 2,03 3,04 5,21 8,82 15,35 22,01 37,8 66,27

5104 2,04 2,88 4,01 8,2 13,34 24,03 44,85 90,97

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

1) определение необходимости деления вершины на основе оценки ошибки в ней. Критерий разбиения - сравнение ошибки в вершине с порогом, который рассчитывается как у-квантиль распределения ошибок;

2) выбор вида регрессионной зависимости в терминальной вершине:

/у(30 = ^кУк+а.к+е, (ук е

к=О

3) определение параметров разбиения вершины, а также выбор «лучшего признака». совокупность которых дает максимальное уменьшение ошибки:

определение «параметра» разбиения:

= аге гшп е А к,а),

ае[0,1] *

- критерий определения «лучшего признака»: k' = are щш_Е,(£,а").

J í-и,К-1 '

2. Настройка (построение) элементарной регрессии в вершине, представляющая собой расчет коэффициентов регрессии на основе метода наименьших квадратов (решение системы линейных алгебраических уравнений - СЛАУ - по всем элементам обучающей выборки, попавшим в вершину):

f(y) = aTy, у = (у0,у1,...,укл,\)Т, Ег = £||агр-£00||, £г = {3TU - Г)7 (aTU - Г), a =(UUTy'uT. В случае, когда элементов выборки, попавших в вершину, недостаточно для расчета коэффициентов регрессии, в диссертационной работе предложено провести регуляризацию, доопределив СЛАУ за счет элементов выборки верхнего уровня и решить систему с ограничениями, гарантирующими нулевую ошибку для точек терминальной вершины.

aTy„=g(yn), n = l,N,

(aTU - f)T (aTU - Г) -» min.

Для решения этой задачи используется метод множителей Лагранжа. Для случая преобразования второго типа (К = {0,1,2,...1-1}) аналогичная регуляризация заключается в использовании результатов классификации вершины «верхнего» уровня для определения номера класса в терминальной вершине:

/ = argmax/j*', где S„ =\l:nj = щах nv,\,

j<=Sr I W-1 ')

здесь v-терминальнаявершина, .. -

v"1 - нетерминальная вершина, предшествующая вершине v, Sv — множество индексов для вершины v,

ríj - количество объектов /-ого класса, попавших в область вершины v.

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

Для решения данной задачи в диссертационной работе была проведена оценка обобщающей способности вычислительной процедуры. _

Выборка: Пг =П°<иП', s + t = T, QsnO' =0, n = {jT,g(.y,)}, j = l,T, где f2* - обучающая часть выборки, fí' - контрольная часть выборки. Качество алгоритма на выборке: v(a, О) = т—г /(cof, a(a>.)),

где a - алгоритм регрессии или классификации (А - семейство алгоритмов), ц - метод (алгоритм) обучения по выборке: ц(П) = а,

= |1, |а(ш,)-Ф(м,)|>5(о,) fl, а(<о,)*Ф(ш,.)

R {О, |а(ш,)-Ф(ш,)|<8(а,)' Io....."> [О, а(<в,) = Ф(и,)'

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

Рея(А) = ?{sup(v(a,r)-v(a,Xs)) >sj.

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

цов К. В.) с функционалом полного скользящего контроля, который инвариантен к произвольным перестановкам выборок:

" 11=0

Кроме того, использование локальной функции роста - А'т (ц,Пг), для оценки:

где Г^.(е,5) - коэффициент (б И) - учитывает все три фактора: особенности распределения объектов, особенности восстанавливаемой зависимости и особенности метода обучения. Поэтому в диссертационной работе использована именно комбинаторная теория. 4. Оптимизация «структуры» процедуры локальной обработки по различным комбинациям обучающей и контрольной выборок.

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

& у . Фч .

'Ж Ж

1 _Т » Ж,

1 2

где т,^ - квантиль распределения ЛГ0Л уровня 1-а/2 (а = 1-у).

Решение о завершении формирования выборок принимается в тот момент, когда достигается непересечение указанных доверительных интервалов на соседних шагах. 5. Оценка вычислительной сложности (количества операций на один отсчет входного сигнала) для построения и применения процедуры обработки на основе иерархической регрессии и признаков, полученных вейвлет-разложением сигнала Сложность процедуры расчета признаков: (К)<4.875-К.

Сложность процедуры при построении ДР, при применении ДР:

для линейной регрессии- иф2(К,Н)<2Н((К+2)2 +2Н), иф2(К,Н)<2К+Н+1; для постоянного значения - и°2 (Я) < (Я +2)2, и®2 (Я) < Я+1,

где Я- количество иерархических уровней (глубина дерева), К-количество признаков.

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

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

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

тупного на момент построения объема обучающих данных).

Алгоритм построения Алгоритм обнови (ц)

Рисунок 4 - Блок-схема алгоритма построения вычислительной процедуры

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

При решении задач фильтрации/восстановления изображений выигрыш по качеству обработки для разработанного метода составляет 15-17% по сравнению с классическим фильтром Винера. При сравнении иерархической регрессии с нейронной сетью в задачах локальной обработки изображений выводы следующие: при незначительном выигрыше по качеству (порядка 5-7%) выигрыш по скорости обработки - в десятки раз. Результаты сравнения качества и вычислительной сложности обработки на этапе применения процедур обработки представлены в таблице 2. На этапе построения процедур выигрыш оказывается еще выше, так как построение функции иерархической регрессии соответствует 3-5 итерациям обучения нейронной сети (для сходимости процесса обучения искусственной нейронной сети обычно необходимы тысячи итераций).

Нейронная сеть Нейронов. 5 10 20 30 40 50 60

Е 10.92 10.78 10.69 10.67 10.63 10.62 10.63

и 54 99 189 279 369 459 549

Дерево регрессии Терм. верш. 100 200 500 1000 1500 2000 2500

£ 11.01 10.89 10.81 10.72 10.63 10.57 10.62

и 38 41 44 46 48 50 52

Результаты экспериментальных исследований позволяют сделать следующие выводы:

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

.2. Получены выражения для вычислительной сложности разработанных алгоритмов локального ДВП. Определены зоны вычислительной «компетентности» алгоритмов локального ДВП на основе базиса Хаара, позволяющие выбрать наилучший алгоритм в зависимости от параметров рассчитываемого локального ДВП и типа решаемой задачи.

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

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

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

6. Проведены экспериментальные исследования предложенных в работе методов и алгоритмов, подтвердившие их работоспособность и эффективность по сравнению с существующими решениями.

Основные положения диссертации отражены в следующих публикациях:

Статьи в ведущих рецензируемых научных журналах и изданиях, входящих в перечень ВАК 1. Глумов, Н.И. Автоматизированное формирование регионального банка космических снимков и его использование в геопорталах [Текст] / Н.И. Глумов, В.Н. Копенков, Е.В. Мясников, A.B. Сергеев, A.B. Чернов, Н.В. Чупшев // Сборник «Современные проблемы дистанционного зондирования Земли из космоса». - 2010. - Том 7, №2. - Москва. - С. 129-138.

2. Копенков, В.Н. Эффективные алгоритмы локального дискретного вейвлет-преобразования с базисом Хаара [Текст] / В.Н. Копенков // Компьютерная оптика. - 2008. - Выпуск 32, № 1. -С. 78-85.

3. Сергеев, В.В. Сравнительный анализ методов аппроксимации функций в задачах обработки изображений [Текст] / В.В. Сергеев, В.Н. Копенков, А.В. Чернов // Компьютерная оптика. -2004.-Выпуск 26.-С. 118-122.

4. Сергеев, В.В. Сравнительный анализ методов нейронных сетей и иерархической аппроксимации в задачах фильтрации изображений [Текст] / В.В. Сергеев, В.Н. Копенков, А.В. Чернов // Научный журнал «Автометрия». - 2006. Том 42, №2. - С. 100-106.

5. Chernov, A.V., Parametric Optimization of Families of Features in Image Reconstruction Methods Based on the Principles of Pattern Recognition Theory [Текст] / A.V. Chernov, V.N. Kopenkov// Pattern Recognition and Image Analysis. - 2003. - Vol. 13, No. 4. - pp. 80-81.

6. Kopenkov, V. Effecient algorithms of local discrete wavelet transform with HAAR-like bases [Текст] / V.N. Kopenkov // Pattern Recognition and Image Analysis. - 2008. - Vol. 18, No. 4 - pp. 654-661.

7. Kopenkov, V.N. Research the Performance of a Recursive Algorithm of the Local Discrete Wavelet Transform [Электр.] / V.N. Kopenkov, V.V. Myasnikov// 20-th International Conference on Pattern Recognition (ICPR-2010). - 2010. Istanbul, Turkey. Abstract book. - p. 317.

8. Kopenkov, V.N. Regression restoration methods as applied to solve the problem of multidimensional indirect measurements [Текст] / V.N. Kopenkov, V.V. Sergeev, E.I. Timbai// Pattern Recognition and Image Analysis. - 2011. - Vol. 21, No. 2 - pp. 480-483.

9. Sergeev, V.V. Comparative analysis of the function approximation methods in image processing tasks [Текст] / V.V. Sergeev, V.N. Kopenkov, A.V. Chernov // Pattern Recognition and Image Analysis. -2005. Vol. 15. - pp. 308-311.

10. Sergeev, V.V. Comparison of the function approximation methods applied to image processing [Текст] / V.V. Sergeev, V.N. Kopenkov, A.V. Chernov// Pattern Recognition and Image Analysis. -2007. Vol. 17, No.2 - pp. 217-221.

Материалы и тезисы конференций, статьи в сборниках

11. Глумов, Н.И. Программная система визуализации и анализа изображений [Текст] / Н.И. Глумов, В.Н. Копенков, Е.В. Мясников, А.В. Сергеев // Научно-техническая конференция с международным участием: «Перспективные информационные технологии в научных исследованиях, проектировании и обучении ПИТ-2006»: Сборник трудов, Том 2/ СГАУ. -Самара. - 2006. - С. 123-127.

12. Глумов, Н.И. Сервисное программное обеспечение для обеспечения учебно-исследовательского процесса обработки изображений [Текст] / Н.И. Глумов, В.Н. Копенков, Е.В. Мясников, А.В. Сергеев II Всероссийский семинар по моделированию, дифракционной оптике и обработке изображений: Сборник трудов / СГАУ. - Самара - 2006. - С. 18-22.

13. Глумов, Н.И. Программная система визуализации и анализа изображений [Текст] / Н.И. Глумов, В.Н. Копенков, Е.В. Мясников, А.В. Сергеев // Всероссийский семинар по моделированию, дифракционной оптике и обработке изображений: Сборник трудов / СГАУ. -Самара. - 2006. - С. 46-51.

14. Копенков, В.Н. Быстрые алгоритмы локального дискретного вейвлет-преобразования с базисом Хаара [Текст] / В.Н. Копенков, В.В. Мясников // Научно-техническая конференция с международным участием: «Перспективные информационные технологии в научных исследованиях, проектировании и обучении ПИТ-2006»: Сборник трудов, Том 2. /СГАУ. - Самара. -2006.-С. 113-118.

15. Копенков, В.В. Современные информационные технологии анализа и обработки данных. Лабораторный практикум: учебное пособие. [Текст] / В.Н. Копенков, В.В. Сергеев // Изд-во Самар. гос. аэрокосм, ун-та. - Самара - 2007. 96 С.

16. Копенков, В.Н. Метод иерархической аппроксимации как решения задачи многомерных косвенных измерений [Текст] / В.Н. Копенков В.Н.ДВ. Сергеев В.В., Е.И. Тимбай // Доклады 8-й Международной конференции «Интеллектуализация обработки информации» (ИОИ-2010) / Республика Кипр, г. Пафос. -2010. -С. 144-148.

17. Копенков, В.Н. Использование иерархически-конструируемой регрессии в задачах локальной обработки изображений [Текст] / В.Н. Копенков // Тезисы докладов Региональной научно-практической конференции, посвященной 50-летию первого полета человека в космос / СГАУ. - Самара. - 2011. - С. 219-221.

18. Чернов, А.В. Параметрическая оптимизация семейств признаков в методах восстановления изображений, основанных на принципах теории распознавания образов [Текст] /А.В. Чернов, В.Н. Копенков // Труды 6-ой международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" / Новгор. гос. университет. - Великий Новгород. - 2002. - С. 602-605.

19. Чичева, М.А. Метод быстрой корреляции с использованием множества шаблонов в задачах анализа изображений [Текст] / М.А. Чичева, Н.И. Глумов, В.Н. Копенков, Е.В. Мясников // 13-я Всероссийская конференция «Математические методы распознавания образов»: Сборник докладов / Ленинградская обл., г. Зеленогорск. - 2007. - С. 559-562.

20. Kopenkov, V. The Effective algorithms of local discrete wavelet transform Based on HAAR-similary bases [Текст] / V.N. Kopenkov // 8-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies. (PRIA-8-2007): Conference proceedings in 3 volumes. Vol. 2 / Mari State Technical University. - Yoshkar-OIa, the Russian Federation. - 2007. pp. 106-110.

21. Kopenkov, V.N. Fast and effective algorithms of local discrete wavelet transform research [Текст] / V.N. Kopenkov, V.V. Myasnikov // 9-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies. (PRIA-9-2008): Conference proceedings in 2 volumes Vol. 1 / Nizhniy Novgorod State University. - Nizhniy Novgorod, the Russian Federation. - 2008. -pp. 321-325.

22. Kopenkov, V.N. Fast and effective algorithms of local discrete wavelet transform research [Текст] / V.N. Kopenkov, A.V. Chernov, N.V. Chupshev // 9-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies. (PRIA-9-2008): Conference proceedings in 2 volumes Vol. 1 / Nizhniy Novgorod State University. - Nizhniy Novgorod, the Russian Federation.-2008.-pp. 317-321.

23. Kopenkov, V.N. Hierarchical approximation method as a solution of multivariate indirect measurements problem [Текст] / V.N. Kopenkov, V.V. Sergeev, E.I. Timbai // 3-th International Conference on «Automation, Control and Information Technology» (ACIT 2010) : Conference proceedings / ACTA Press. - Novosibirsk, Russia. - 2010. - pp 25-28.

24. Kopenkov, V.N. Investigation of the regression reconstruction methods used for the solution of multivariate indirect measurements task [Текст] / V.N. Kopenkov, V.V. Sergeev, E.I. Timbai // 10-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies. (PRIA-10-2010): Conference proceedings / St. Petersburg Electrotechnical University. - St. Petersburg, the Russian Federation. - 2010. - pp. 187-190.

25. Kopenkov, V.N. Investigation of the regression reconstruction methods used for the solution of multivariate indirect measurements task [Текст] / V.N. Kopenkov, V.V. Sergeev, A.V. Chernov // 7-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies (PRIA-7-2004) : Conference proceedings in 2 volumes. Vol. 2 / St. Petersburg Electrotechnical University. - St. Petersburg, the Russian Federation. - 2004. - pp. 376-380.

26. Kopenkov, V.N. Hierarchical approximation method as a solution of multivariate indirect measurements problem [Текст] / V.N. Kopenkov, V.V. Sergeev, A.V. Chernov // Proceedings of 2-th International Conference on Automation, Control and Information Technology - Signal and image processing (ACIT-S1P 2005) / ACTA Press. - Novosibirsk, Russia. - 2005. - pp 71-74.

Подписано в печать 03.10.2011 Формат 60 х 84 1/16. Тираж 100 экз. Отпечатано с готового оригинал-макета СГАУ 443086, Самара, Московское шоссе, 34

Введение.

Раздел 1. Задачи локальной обработки изображений и методы их решения.

1.1 Классы задач локальной нелинейной обработки сигналов и изображений.

1.1.1 Классы задач с линейной локальной функцией регрессии.

1.1.2 Классы задач с нелинейной локальной регрессионной зависимостью

1.1.3 Классы задач с дискретной локальной регрессионной зависимостью

1.2 Локальная нелинейная обработка изображений с использованием дерева регрессии.

1.2.1 Схема локальной обработки изображений.

1.2.2 Классификация деревьев регрессии по типу преобразования, используемого в терминальных вершинах.

1.2.3 Общее описание информационной технологии построения процедуры обработки на основе иерархических структур.

1.3 Существующие подходы к реализации «универсальной» схемы преобразования.

1.3.1 Основные группы признаков.

1.3.2 Общие параметры построения древовидных структур.

1.3.2 Структура данных в узлах дерева.

1.4 Основные проблемы, возникающие при использовании «универсальной» схемы преобразования.

1.4.1 Выбор признаков.

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

1.4.3 Выбор модели регрессии.

1.4.4 Проблемы недообучения и переобучения.

1.4.5 Объемы выборочных данных при обучении.

1.4.6 Вычислительная сложность «универсального» преобразования.

1.4.7 Предлагаемые методы решения обозначенных проблем.

1.5 Выводы и результаты.

Раздел 2. Эффективные локальные признаки на основе локальных дискретных вейвлет-преобразований.

2.1 Эффективный расчет признаков на основе дискретного локального вейвлет-преобразования.

2.1.1 Эффективные алгоритмы расчета локального дискретного вейвлет-преобразования одномерного сигнала на примере вейвлет-базиса Хаара.

2.1.2 Эффективный расчет локального дискретного 2-х мерного вейвлет-преобразования на примере вейвлет-базиса Хаара.

2.3.3 Использование базиса Хаара с масштабирующим коэффициентом «3»

2.1.4 Сравнение вычислительной сложности модифицированного и эффективного алгоритмов вычисления локального дискретного вейвлетпреобразования.

2.3.4 Эффективное вычисление биортогональных полиномиальных сплайн-вейвлетов с конечными носителями.

2.2 Параметрическая настройка признаков.

2.3 Определение оптимального размера окна обработки при вычислении признаков.

2.4 Выводы и результаты.

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

3.2 Анализ обобщающей способности древовидной модели.

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

3.2.2 Комбинаторный подход.

3.2.3 Остановка процесса перебора различных сочетаний обучающей и контрольной выборок.

3.3 Особенности построения дерева регрессии.

3.3.1 Особенности построения элементарной регрессии в узлах.

3.3.2 Зависимость древовидной модели от алгоритмов локального дискретного вейвлет-преобразования.ЮО

3.4 Анализ вычислительной сложности «универсального» алгоритма с признаками на основе дискретного локального вейвлет-преобразования.

3.4.1 Расчет признаков.

3.4.2 Иерархическая регрессия.Ю

3.5 Алгоритм автоматического построения «универсального» преобразования с ограничениями по сложности и качеству исполнения.

3.6 Тестирование алгоритма построения процедуры локальной обработки с ограничениями.

3.7 Выводы и результаты.

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

4.1 Определение достаточного объема выборки.ИЗ

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

4.2.1 Зависимость эффективности фильтрации от соотношения «сигнал/шум».

4.2.2 Сравнение различных типов аппроксимации в терминальных вершинах при фильтрации изображений.

4.2.3 Сравнение метода иерархической регрессии с нейронной сетью в задачах фильтрации изображений.

4.3 Восстановление изображений.

4.4 Задачи классификации отсчетов изображения.

4.5 Задачи выделения контуров.

4.6 Выводы и результаты.12В

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

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

Локальная обработка цифровых изображений - одно из наиболее востребованных преобразований в теории и практике цифровой обработки изображений-и в теории компьютерного зрения. Под локальной обработкой-обычно понимают такое преобразование изображения, в котором каждый отсчет выходного изображения формируется на основании однозначного преобразования множества отсчетов входного изображения, попавших в некоторую его окрестность (по координатам). Исторически, первыми для- обработки использовались линейные локальные методы, допускающие построение оптимальных в некотором* смысле процедур обработки. Математические методы построения! и реализации таких вычислительных процедур рассматривались такими российскими, и зарубежными учеными, как: R. Gonzales, D. Forsyth, A. Oppenheim, R. Schafer, R. Mersereau, W. Pratt, R. Woods, Л.М. Гольденберг, В.Г. Лабунец, B.B! Сергеев, B.A. Сойфер, Л.П. Ярославский. Однако появление новых задач обработки цифровых сигналов (обработка видеоинформации, звука, космических снимков и т.п.), задач обработки больших объемов информации в режиме реального времени, а также требование повышения эффективности обработки привели к необходимости использования i нелинейных преобразований. Вопросам построения и реализации локальных нелинейных процедур обработки посвящены работы таких ученых, как: С. Cowan, S. Geiser, Е. Glaser, P. Grant, R. Lucky, S. Haiken, С. Jakowatz, W. Masenten, В. Widrow,

А.Н. Горбань, И.С. Грузман, A.A. Ланнэ, В.В: Сергеев, Л.П. Ярославский и др. Один из наиболее распространенных на настоящий момент подходов заключается в реализации кибернетического принципа «черного ящика» (термины других авторов: обработка через распознавание, обработка по прецедентам), когда само преобразование и его параметры определяются на основании анализа входных и выходных сигналов или изображений. Несмотря на обилие в рамках этого подхода i частных решений, формализованный регулярный подход к построению вычислительных процедур для конкретной практической задачи до настоящего времени отсутствует. Это позволяет утверждать об актуальности выбранной темы диссертационной работы.

Одним из известных подходов к построению относительно универсальных вычислительных процедур локальной адаптивной обработки цифровых сигналов и изображений, реализующих принцип «черного ящика», является использование аппарата нейронных сетей (S. Grossberg, К. Fukushima, S. Haykin, Т. Kohonen, F. Rosenblatt, В. Widrow, N. Wiener, Ф. Уоссермен, А.И. Галушкин, Г.С. Осипов): Альтернативным, но существенно менее развитым подходом является использование иерархических вычислительных конструкций (далее* - иерархической регрессии), таких как дерево-решений и дерево* регрессии (H.Ahn, L. Breiman, J.Friedman, R. Olshen, С. Stone, J. Quinlan, B.B. Сергеев, A.B. Чернов). Настоящая работа лежит в русле последнего из обозначенных подходов, развивая идею разработки универсального механизма построения локальных нелинейных вычислительных процедур обработки, основанных на* иерархической конструкции и обеспечивающих максимум качества при заданной вычислительной сложности обработки. i

Цель работы

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

Задачи диссертационной работы

Для достижения указанной цели решаются следующие задачи:

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

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

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

4) Разработка алгоритма;автоматического построения вычислительной процедуры локальной обработки изображений; на':' основе иерархической^ регрессии и алгоритмов • локального дискретного вейвлет-преобразования с ограничением по сложности обработки и максимизацией качества и обобщающей • ■ ■ - 1 . способности.

5) Экспериментальные исследования разработанного алгоритма и входящих в его ' I : ' • состав, методов, сравнение алгоритма с традиционными подходами (нейросетевой подход и др.) по критериям качества и вычислительной эффективности, выработка рекомендаций: по: использованию- результатов диссертации.

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

Методы исследований !

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

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

Предложены новые алгоритмы вычисления локального дискретного вейвлет-преобразования в режиме скользящего окна для одномерных и двумерных сигналов. Приведена адаптация разработанных алгоритмов для базиса Хаара и биортогональных полиномиальных сплайн-вейвлетов. Получены области вычислительной «компетентности» для разработанных алгоритмов.

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

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

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

Получены оценки вычислительной сложности разработанных алгоритмов:

Практическая ценность работы ,

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

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

Реализация результатов работы (

Результаты диссертации использованы при выполнении» 17 госбюджетных и хоздоговорных НИР в Самарском Государственном Аэрокосмическом Университете, Институте систем обработки изображений РАН, Некоммерческом партнерстве «Поволжский центр космической геоинформатики» и ОАО «Самара

Информспутник».

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

Основные результаты диссертации были представлены на следующих конференциях:

- на 6-й международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-6), Великий Новгород, 2002;

- на 7-й международной конференции «Распознавание образов и анализ изображений: новые информационные, технологии»" (РОАИ-7), Россия, Санкт-Петербург, 2004;

- на 2-й международной* конференции «Automation, control, and Information technology - Signal and image processing (ACIT-SIP)», Новосибирск, 20-24 июня 2005;

- на Всероссийском семинаре по моделированию, дифракционной оптике и обработке изображений, Самара, 3-7 июля 2006; I

- на Научно-технической конференции с международным участием «Перспективные I информационные технологии в научных исследованиях, проектировании и обучении «ПИТ-2006»», Самара, 2006;

- на 13-й Всероссийской конференции. «Математические методы распознавания образов», Ленинградская обл., г. Зеленогорск, 30 сентября - 6 октября 2007; на 8-й международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-8), Россия, Йошкар-Ола, 2007; на 9-й международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-9), Россия, Нижний-Новгород, 2008; на 7-й всероссийской открытой ежегодной конференции «Современные проблемы дистанционного зондирования Земли из космоса» Москва, ИКИ РАН, 16-20 ноября 2009; I на 3-й международной конференции «Automation, Control and Information Technology» (ACIT-2010), Новосибирск, 15-18 июня 2010, на 20-й международной Конференции Распознавания Образов (ICPR-2010),

Турция, Стамбул, 23-26 августа 2010;

- на Международной конференции с элементами научной школы для молодежи "Перспективные информационные технологии для авиации и космоса «ПИТ-2010»", Самара, 2010;

- на 8-й международной конференции «Интеллектуализация обработки информации» (ИОИ-2010), Республика Кипр, г. Пафос, 17-24 октября 2010;

- на 10-й международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОЛИ-10), Россия, Санкт-Петербург, 5-12 декабря 2010;

- на Региональной научно-практической конференции, посвященной 50-летию первого полета человека в космос, Самара, 14-15 апреля 2011.

Публикации

По теме диссертации опубликовано 26 работ, из них 10 в изданиях, определенных в перечне ведущих рецензируемых научных журналов и изданий-ВАК Минобрнауки России, 4 работы выполнены без соавторов. При участии автора, написано 17 отчетов по НИР.

Краткое содержание диссертации

Диссертация состоит из* введения, четырех разделов, заключения, списка литературы и одного приложения. Она изложена на 139 страницах машинописного текста (без приложений), содержит 43 рисунка, 11 таблиц, список использованных источников из 82 наименований.

4.6 Выводы и результаты

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

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

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

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

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

Заключение

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

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

2) Получены выражения для вычислительной сложности разработанных алгоритмов локального ДВП. Определены зоны «вычислительной компетентности» алгоритмов локального ДВП на основе базиса Хаара, позволяющие выбрать наилучший алгоритм в зависимости от параметров рассчитываемого локального ДВП и типа решаемой задачи.

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

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

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

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

1. Вапник, В.Н. Теория распознавания образов Текст. / В.Н. Вапник, A.B. Червоненкис// -М.: Наука, 1974.

2. Вапник, В. Н. Восстановление зависимостей по эмпирическим данным Текст. / В.Н. Вапник//-М.: Наука, 1979.

3. Воронцов, К.В. Комбинаторные обоснования обучаемых алгоритмов Текст. / К.В. Воронцов // ЖВ-МиМФ. 2004; Т. 44, № 11. С. 2099-2112.

4. Глумов, H.H. Применение полиномиальных базисов для обработки изображений в скользящем окне Текст. / Н.И. Глумов, В.В. Мясников, В.В. Сергеев // Компьютерная оптика. 1995. - Выпуск 14-15, Часть 1. - С. 55-68.

5. Даджион, Д. Цифровая обработка многомерных сигналов Текст. / Д. Даджион, Р. Мерсеро // М.: Мир, - 1998.

6. Демиденко, Е.З. Линейная и нелинейная регрессии Текст. / Е.З. Демиденко// М.: Финансы и статистика. - 1991.

7. Журавлев, Ю.И. Корректные алгебры над множеством некорректных эвристических алгоритмов Текст. / Ю.И. Журавлев// Кибернетика, 1977. № 4. с. 14-21; - 1977. № 6. с. 21-27;- 1978. №2. с. 35-43.

8. Журавлев, Ю.И. Распознавание образов и распознавание изображений Текст. / Ю.И. Журавлев, И.Б. Гуревич// Распознавание, классификация, прогноз: математические методы и их применение. М.:Наука, - 1989; Выпуск 2. с.5-72.

9. Копенков, В.Н. Современные информационные технологии анализа и обработки данных. Лабораторный практикум: учебное пособие. Текст. / В.Н. Копенков, В.В. Сергеев // Изд-во Самар. гос. аэрокосм, ун-та. — Самара. — 2007. 96 С.

10. Копенков, В.Н. Эффективные алгоритмы локального дискретного вейвлет-преобразования с базисом Хаара Текст. / В.Н. Копенков // Компьютерная оптика. -2008. Выпуск 32, № 1. - С. 78-85.

11. Короткий, С., Нейронные сети: алгоритм обратного распространения Электр. // С. Короткий/ 14 С.

12. Лоусон, Ч. Численное решение задач метода наименьших квадратов Текст.// Ч. Лоусон, Р. Хенсон / М. : Наука, - 1986.

13. Майтра, С. Моментные инварианты // С. Майтра / ТИИЭР 1979. № 4 - с. 297-99.

14. Методы компьютерной обработки изображений. Под редакцией В.А. Сойфера / М.В. Гашников, Н.И. Глумов, Н.Ю.Ильясова, В.В. Мясников и др., под общей редакцией В.А. Сойфера. 2-е изд., испр. - М.: Физматлит, 2003. - 784 с.

15. Мясников, В.В. Эффективный алгоритм над множеством алгоритмов вычисления свертки Текст. / В.В. Мясников // Компьютерная оптика. 2006. - Выпуск 29. - С. 78117.

16. Мясников, В.В. Эффективные алгоритмы вычисления локального дискретного вейвлет-преобразования Текст. / В.В. Мясников // Компьютерная оптика. 2007. - Том 31, № 4.- С. 86-94.

17. Мясников, В.В. Сплайны как средство построения эффективных алгоритмов локального линейного преобразования Текст. / В.В. Мясников // Компьютерная оптика. 2007. - Том 31, № 2. - С. 52-68.

18. Оппенгейм, A.B. Цифровая обработка сигналов Текст. / A.B. Оппенгейм, Р.В. Шафер //- М.: Мир. 1979.-416 с.

19. Подкур, П.Н. О построении некоторых типов вейвлетов с коэффициентом масштабирования N Текст./ П.Н. Подкур // Электронный научный журнал «Исследовано в России». 2006. - с. 965-974.

20. Прэтт, У. Цифровая обработка изображений Текст./ У. Прэтт // М.: Мир, т. 1-2, -1982.

21. Сергеев, В.В. Параллельно-рекурсивные КИХ-фильтры для обработки изображений Текст. / В.В. Сергеев // Компьютерная оптика М.: МЦНТИ. - 1992. - Вып.10-11. -с. 186-201.

22. Сергеев, B.B. Применение методологии распознавания образов в задачах цифровой обработки изображений Текст. /В.В. Сергеев // Автометрия. 1998. № 2.

23. Сергеев, В.В. Сравнительный анализ методов аппроксимации функций в задачах обработки изображений Текст. / В.В. Сергеев, В.Н. Копенков, A.B. Чернов // Компьютерная оптика. 2004. - Выпуск 26. - С. 118-122.

24. Сергеев, В.В. Сравнительный анализ методов нейронных сетей и иерархической аппроксимации в- задачах фильтрации изображений Текст. / В.В. Сергеев, В.Н. Копенков, A.B. Чернов // Научный журнал «Автометрия». 2006. Том 42, №2. - С. 100-106.

25. Фукунага К. Введение в статистическую теорию распознавания образов Текст. / К. Фукунага : Пер. с англ //- М.: Наука. 1979. - 368 с.

26. Уоссермен, Ф. Нейрокомпьютерная техника: Теория и практика = Neural Computing. Theory and Practice. Текст. / Ф. Уоссермен»// М.: Мир. - 1992. - 240 с.

27. Цифровая обработка изображений Текст. / Р. Вудс, Р.Гонсалес // М.: Техносфера, -2005.- 1072 с.

28. Чернов, A.B. Быстрое рекурсивное вычисление одномерных и двумерных конечных свертокТекст. / A.B. Чернов // Компьютерная оптика. 2003. Вып. 25. - С. 190-197.

29. Чуй, К. Введение в вейвлеты. Текст. /К. Чуй// М.: Мир. - 2001.

30. Ярославский, Л.П. Введение в цифровую обработку изображений. Текст. / Л.П. Ярославский //-М: Сов. Радио. 1979.

31. Ярославский, Л.П. О возможности параллельной и рекурсивной организации цифровых фильтров Текст. / Л.П. Ярославский // Радиотехника. 1984. - N 3. - С. 8791.

32. Яхъяева, Г.Э. Нечеткие множества и нейронные сети БИНОМ Текст. /Г.Э. Яхъяева// Лаборатория знаний. Интернет-университет информационных технологий ИНТУИТ.ру. 2008.

33. Ahn, Н. Tree-structured exponential regression modeling Текст. / H. Ahn // Biomedical Journal. -2007. Vol. 36. pp. 43-61.

34. Breiman, L. Classification and regression trees Текст. / Breiman, L., J. H. Friedman, R. A. Olshen, and C. J. Stone.// Monterey, Calif., U.S.A.: Wadsworth, Inc. 1984.

35. Beucher, S. The Watershed Transformation Applied to Image Segmentation Текст. / Beucher, S. // Scanning Microscopy International. 1992. Vol 6, - pp. 299-314.

36. Comaniciu, D. Mean Shift Analysis and Applications Текст. / Comaniciu D. and Meer P.// In Proc. Of IEEE Conf. on Comput. Vis. 1999. - pp. 1197-1203.

37. Chan, K.Y. LOTUS: An algorithm for building accurate and comprehensible logistic regression trees. Текст. / Chan K.-Y. and Loh. W.-Y. // Journal of Computational and Graphical Statistics, 2004. Vol. 13. - pp. 826-852.

38. Chernov, A.V. Fast Method for Local Image Processing and Analysis Текст. / A.V.Chernov, V.V.Myasnikov, V.V.Sergeyev // Pattern Recognition and Image Analysis. 1999. - Vol.9, No. 4. - pp.572-577.

39. Chernov, A.V. Image Reconstruction Methods Based on the Principles of Pattern Recognition Theory Текст. / A.V. Chernov, V.V. Sergeev // Pattern Recognition and Image Analysis. -1997. Vol. 6. No.4 - pp. 474-479.

40. Daubechies, I. Ten Lectures on Wavelets Текст. / I. Daubechies // CBMS-NSF Lecture

41. Notes. SIAM. 1992. - 377 p.

42. Ivo, M. Simultaneous determination of relative humidity and ammonia in air employing an optical fibre sensor and artificial neural network. Текст. / Ivo M. Raimundo Jr., R. Narayanaswamy // Sensors and Actuators. 2001. B. 74 - p. 60-68.

43. Glumov, N. I. Detection of the Objects on the Image Using a Sliding Windows Mode. Текст. /N.I. Glemov, E.I. Kolomiec, V.V. Sergeyev// Optic and Laser Technology, 1995. No.4, -pp. 241-249.

44. Glumov, N.I. Recursive Filters with Even Polynomial Impulse Responses for Processing Images by a Sliding Window Текст. / N.I. Glumov, V.V. Myasnikov, V.V. Sergeyev // Pattern Recognition and Image Analysis. 1996. - Vol. 6, No. 1. - pp. 122-123.

45. Kohonen, T. Self-Organizing Maps / T. Kohonen // Berlin — New York: Springer-Verlag. Third extended edition-2001. ISBN 0-387-51387-6, ISBN 3-540-67921-9.

46. Kopenkov, V. Effecient algorithms of local discrete wavelet transform with HAAR-like bases Текст. / V.N. Kopenkov // Pattern Recognition and Image Analysis. 2008. - Vol. 18, No. 4 -pp. 654-661.

47. Kopenkov, V.N. Regression restoration methods as applied to solve the problem of multidimensional indirect measurements Текст. / V.N. Kopenkov, V.V. Sergeev, E.I. Timbai// Pattern Recognition and Image Analysis. 2011. - Vol. 21, No. 2 - pp. 480483.

48. Li, B.C. Fast computation of moment" invariants Текст./ B.C. Li, J. Shen// Pattern Recognition, 1991. Vol.24, No. 8, - pp. 807-813.

49. Mallat, S. A wavelet tour of signal processing Текст. / S. Mallat S. // M.:Academic Press. -1999.-637 p.

50. Myasnikov, V.V. Methods for Designing Recursive FIR Filters Текст. / V.V. Myasnikov // International Conference "Computer Vision and Graphics" (ICCVG 2004): proceedings / Springer. Warsaw, Poland, 2004. - pp. 845-850.

51. Sergeev, V.V. Comparative analysis of the function approximation methods in image processing tasks Текст. / V.V. Sergeev, V.N. Kopenkov, A.V. Chernov // Pattern

52. Recognition and Image Analysis. 2005. Vol. 15. - pp. 308-311.

53. Sergeev, V.V. Comparison of the function approximation methods applied to image processing Текст. / V.V. Sergeev, V.N. Kopenkov, A.V. Chernov// Pattern Recognition and Image Analysis. 2007. Vol. 17, No.2 - pp. 217-221.

54. Widrow, B. 30 Years of Adaptive Neural Networks: Perceptron, Madaline, and Backpropagation Текст. /Bernard Widrow, Michael A. Lehr // Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press. 1992. - p. 327-354.

55. Werbos, P.J. Backpropagation Through Time: What It Does and How to Do It Текст. / Paul J. Werbos //Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press. -1992.-p. 309-319.