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

На правах рукот 0046тю?

КАРЦЕВА АЛЕКСАНДРА СЕРГЕЕВНА

АЛГОРИТМЫ ОЦЕНИВАНИЯ ЛОКАЛЬНЫХ

ПАРАМЕТРОВ МОДЕЛЕЙ С СОХРАНЕНИЕМ НЕОДНОРОДИОСТЕЙ В ЗАДАЧАХ АНАЛИЗА СИГНАЛОВ И ШОБРАЖЕНИЙ

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

АВТОРЕФЕРАТ

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

Тула, 2010

004600499

Работа выполнена в ГОУ ВПО «Тульский государственный университет».

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

доцент Копылов Андрей Валериевич

Официальные оппоненты доктор физико-математических наук,

профессор Толоконникоз Лев Алексеевич

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

Ведущая организация Институт проблем управления

им. В. А. Трапезникоиа.РАН, г. Москва.

Защита диссертации состоится «30» марта 2010 г. в 14:00 ч. на заседании диссертационного совета Д 212.271.05 Тульского государственного университета по адресу: 300600, г. Тула., пр. Ленина, 92.

Отзывы на автореферат просим высылать по адресу 300500, г. Тула, пр. Ленина, 92, ученому секретарю диссертационного совета.

С диссертацией можно ознакомиться в библиотеке Тульского государственного университета по адресу: 300600, г. Тула, пр. Ленина, 92.

Автореферат разослан • февраля 2010 г.

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

диссертационного совета ■^й5"1"'" В.М. Панарин

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

Актуальность работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Создание параметрической процедуры оптимизации целевой функции с модулем разности значений параметров в соседних узлах модели.

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

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

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

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

Положения, выносимые на защиту.

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

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

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

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

Достоверность полученных результатов подтверждается доказанными математическими утверждениями и модельными экспериментами.

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

Связь с плановыми научными исследованиями. Работа выполнена при поддержке Государственной научно-технической программы РФ «Перспективные информационные технологии», грантов Российского фонда фундаментальных исследований №08-01-99003-р_офи, 04-01-0803 8-офи_а, 06-07-89249-офи_а, 06-01-00412-офи_а.

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

Апробация работы. Основные положения и результаты диссертации докладывались на международных конференциях «Интеллектуализация обработки информации 2006» (Алушта, Украина, 2006), Pattern Recognition and Image Processing 2007 (Минск, Беларусь, 2007), на ежегодных научных конференциях профессорско-преподавательского состава ТулГУ (Тула, 2004-2006 гг.), на заседаниях кафедры ATM ТулГУ (Тула, 2008 г.).

Публикации. По тематике исследований опубликовано 5 статей из них 4 на русском языке, из них 1 статья в издании, рекомендованном ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, основных выводов, списка литературы и приложений. Материал изложен на 97 сграницах, содержит 18 рисунков, список литературы из 85 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассмотрена задача оценивания параметров моделей

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

В основе оптимизационного подхода лежит идея представления исходного массива данных Y как экспериментально зарегистрированной функции y = (vI,reT), принимающей значения из некоторого множества у,sY, где значения индехса te Т соответствуют отдельным элементам массива.

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

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

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

Задачу анализа исходного массива данных будем рассматривать как задачу преобразования его в некоторый другой массив, представляющий собой оценку некоторой скрытой модели исходного массива данных, которая определена на том же множестве элементов. С помощью модели также выражается априорное предположение о том, какова природа скрытого сигнала. Задачу же анализа исходного сигнала, или изображения, будем понимать как задачу поиска оценок параметров it,eX локальных моделей для всех элементов массива ieT, в совокупности образующих общую модель массива данных X =(*,, 1еТ) из некоторого класса моделей X € X и принимающих значения из множества, специфичного цля каждой конкретной задачи.

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

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

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

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

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

Рисунок 1. Графы отношения соседства между элементами массивэв данных: цепь (а), двумерная решетка (5), трехмерная решетка (в) и дерево (г).

Если гипотеза о сравнительно медленном характере изменения оцениваемого параметра х: верна не полностью, и он претерпевает одиночные скачкообразные изменения на некоторых парах соседних точек /-1 и I, то алгоритм оценивания неизбежно подавит эти скачки, сблизив оценки и х,, как это хорошо видно на рисунке 2.

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

в за 1ва ив а» 250 же эва т «п мп 550 000

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

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

В рамках оптимизационного принципа, интенсивно разрабатываемого в последние годы и призванного преодолеть проблему разрозненности терминологии при решении различных задач, задача оценивания параметров модели сводится к минимизации целевой функции ](Х I У), аргументом которой является модель сигнала или изображения X =(хп(е Т). Целевая функция оценивает несоответствие между каждой допустимой версией модели X и исходным массивом данных У к представляет собой компромисс между двумя противоречивыми требованиями, которые были рассмотрены выше.

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

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

5Д) = агЕпшц/Д*, |У,), 1еТ, (1)

л;еХ

в качестве окончательного решения о скрытой модели Х(У) = ' е Т-),

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

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

возрастающих при увеличении взаимного рассогласования их значений в том

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

При такой интерпретации структуры массива каждой вершине графа соседегва его элементов соответствует одна целевая пepev[eннaя х1 и, следовательно, одна локальная оценочная фушсция IК), а совокупность его ребер отображает представление о непосредственных связях между переменными, которые и должны быть учтены в процессе согласования локальных решений.

Для заданного массива данных У значения модели Х=(л:(,ге Т) следует искать как компромисс между двумя взаимно противоречивыми требованиями: минимизировать одновременно и узловые функции, и функции связи. Естественно принять сумму

У(Х1У) = 2>,(*,1У,) + Е •(*,,*/) (2)

iет (;•,/')£&•

в качестве комбинированного критерия принятия решения:

Х(У) = агятт-/(Х | К). (3)

дг,еХ

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

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

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

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

В работе дач краткий обзор оптимизационных методов оценивания параметров моделей, применяемых в различных прикладных задачах.

Существующие методы многомерной оптимизации имеют обширную классификацию по различным критериям. Наиболее универсальными и в то же время наименее эффективными методами, которые могли бы быть использованы для решения поставленной задачи, являются стохастические; к ним относят метод моделируемого отжига (Simulated annealing), метод случайных блужданий (Random walk). Их основными недостатками является итеративный характер поиска минимума способность «скатываться» в локальный минимум, так что в общем случае глобальный минимум может быть не найден.

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

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

Дапее в первой главе показано существование проблемной ситуации, сформулированной выше в данном автореферате в разделе «Актуальность работы», и поставлены основные задачи исследования.

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

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

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

t = 1.....N. Тогда множество этих значений 7,={1,...,,¥} можно понимать как

множество индексов элементов упорядоченного массива данных

y = (y(,f = 1...../У). Соответственно, граф смежности переменных целевой функции

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

J(xv...,xN\Y) = jy,{x, I)") + £ГЛх,(4) 1=1 (=2

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

о-о-о-о-а-о-о-о 1 /6 т "

Рисунок 3. Граф смежности переменных в виде цепи дли сигналов

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

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

Очевидным случаем естественной параметризации является частный случай конечного множества значений модели Х={1,...,т}.

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

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

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

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

1=1 («2

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

Значение функции Беллмана на очередном шаге процедуры динамического программирования находится следующим образом:

7,(х,) = у1 (х,) + тт[у<1М О,,*,.!) + 7М (*,„!)]. (6)

х<-1

В работе доказана следующая теорема:

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

71(х1,1---~-7,(х1) - монотонно возрастающая функция, которая определяется сЬс/

своими параметрами и 2Д:

(.*,)-и,.«, <Х[Д Г,(х,) ----- \/,(д+ <х, <Х,"_1 =у',(х,) +

х/Ддг^+и.л^З

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

-и, х, ^ к, Х[ а 1

(7)

где и ,т/1] определяются как решение уравнений Т^\{Х,1[) = -и и

(:«■"_!) = и соответственно.

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

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

Критери й вида

+-tMl->min (8)

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

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

д: с двумя компонентами х, = *2М , Г = 1,...,л/2.

В этом случае узловые функции и функции связи также являются векторными и имеют вид:

Y, ) = |хы "*,]-[*,-*M]|=|*,tl-2.x, + *м|

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

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

Задачи анализа визуальных изображений образуют, пожалуй, наиболее очевидный класс задач анализа многомерных массивов данных. Исходный массив данных, т.е. исходное изображение, представляет собой числовую функцию J'' = (yl,t = (r1,i2)e7'), которая обычно принимает значения на непрерывной или дискретной оси уровня яркости у, e Y и определена на дискретном множестве элементов изображения Т ={t = (',,'2)}, называемых пикселами. Обычно элементы изображения упорядочены на плоскости в порядке возрастания дискретных значенийихкоординаг 7'={t = (i1,/2):i1 =1,...,^,, г2 = 1,...,Л?2}.

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

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

пхin«i^j+tS^-i.^i+iii;/^.^^,) (9)

/,=1 r2= 1 r,=l l:-2 l,=2 f2=l

Класс алгоритмов поиска глобального оптимума парно-сепарабельных функций на графе соседства в виде решетки ограничивается процедурами итерационного случайного поиска, такими как моделируемый отжиг (Simulated Annealing), стохастические алгоритмы, требующих больших вычислительных мощностей. Итерационные процедуры такого рода сходятся особенно медленно и имеют свойство останавливаться: в локальных минимумах. Большинство авторов

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

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

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

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

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

X = по полному критерию (2).

х

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

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

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

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

Одной из областей приложения разработанного алгоритма сглаживания

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

Пусть капитал инвестиционной компании целиком вложен в ценные бумаги п типов в пропорциях х=(д(1>.....Х^х1" = 1, х(,1>0. Список наименований

ценных бумаг или их классов, для которых х',] ^0, называют портфелем компании, а вектор долевого распределения капитала внутри портфеля - его составом.

Отношение г''-(г^-г^')/^1 принято называть доходностью портфеля за период владения (portfolio return), а отношения '■(0=(z,('>-4'))/zo> ~ доходностями ценных бумаг (returns of assets), где 4'1 и z,1'1 - стоимости ценных бумаг в начальный и конечный момент некоторого интервала времени, называемого периодом владения, zhP> и z}'' - стоимость портфеля в целом. Если рассматриваются классы ценных бумаг, то их ожидаемые доходности г'1' обычно оцениваются специальными аналитическими компаниями в виде индексов доходности.

Согласно предложенной У.Шарпом модели доходность портфеля определяется как линейная комбинация доходностей составляющих его классов ценных бумаг, в которой в роли вектора коэффициентов выступает долевое распределение стоимости портфеля по видам инвестиций:

г"> = 5^лтг(П=хгг. (10)

где r°\ i = l.....п являются оценкой основных рыночных индексов (generic market

indexes), отслеживаемой в течение некоторого времени с определенным периодом, например, ежедневно, еженедельно и т.д.

Долевой состав портфеля x=(*(',,...,jt<")), являясь внутренней информацией инвестиционной компании, представляет большой интерес для внешнего наблюдателя.

Уильям Шарп в 1970 гг предложил следующий принцип оценивания состава

портфеля, приводящий к задаче квадратичного программирования:

tf".....(П)

хи) > о.

Итоговую доходность портфеля, определяемую комбинацией доходностей большого множества ценных бумаг, Шарп предложил аппроксимировать небольшим числом рыночных индексов, каждый из которых представляет определенный стиль инвестиций. Принцип аппроксимации (11), использованный Шарпом именно для этой цели, широко изиестен в современном анализе инвестиций под названием Return Based Style Analysis (RBSA).

Модель Шарпа имеет существенный недостаток: она основана на малореалистичном предположении о неизменяемом составе портфеля инвестора.

В отличие от статической модели Шарпа (10), рассматривается динамическая модель с изменяющимся долевым составом портфеля А=(х,,/еТ), х,=(л1"),...д,("'), где Т- интервал наблюдения. Для каждого элементарного интервала времени (<-1, 0 справедливо уравнение, аналогичное статическому уравнению (10) при тех же условиях:

02)

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

Задача заключается в оценивании последовательности коэффициентов регрессии А' = (х,,/ = 1,..,,ЛГ) в предположении, что их первые разности

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

Для решения задачи оценивания коэффициентов воспользуемся процедурой динамического программирования с критерием, содержащим модуль разности значений оцениваемых коэффициентов х,,х,+1. Исходный массив данных У состоит из значений доходностей портфеля у,° = г((,,) и индексов доходности, определенных для каждого класса ценных бумаг у,1 = л;"' в моменты времени /.

Узловые функции имеют следующий вид • Функции

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

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

Еще одним примером является задача совмещения стерео пар изображений, которая может быть формально записана в следующем виде. Пусть два изображения X' =(х'(Д€Г), Хг ==(х[, 1е 7') заданы на равномерной

дискретной сетке 7" = (1 = Г,, Г2; и =1, 2,3.....Л',, г2 = 1. 2,3,...,М>) и образуют

исходную пару изображений X =(Х',ХГ) для которой должно быть найдено

соответствие. Это означает, что для каждого элемента 1е Т одного из изображений, условно принятом как базовое, должен быгь найден, в общем случае действительнозначный веетор смещения V, = (у,1, V,2), V, е Кг, который определяет

координатный сдвиг между рассматриваемым элементом 1 и соответствующим ему элементом другого изображения в составе пары, условно принятом как

связи

— Оценка значений первого актива

— Оценка значений второго актива

—Истинные значения первого актива

— Истинные зн ачения второго актива

Рисунок 4 - Оцененный состав тестового портфеля

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

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

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

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

Для решения задачи совмещения изображений воспользуемся разработанным алгоритмом динамического программирования. Е!ыберем такие узловые функции, которые принимали бы тем большие значения, чем более очевидно противоречие между гипотезой, что хе X есть как раз то самое «правильное» локальное значение, которое мы ищем, и текущими массивами данных. Наиболее естественным представляется выбор квадратичных узловых функций. Функции связи будем представлять в виде модуля значений соседних переменных искомой карты диспаратности у(х1,,хг) = и\х1.в предположении, что талой выбор функций связи позволит построить относительно гладкую карту диспаратности для видимых областей двух стерео изображений и в то же время избежать ошибок для тех областей изображений, где присутствуют загораживания объектов друг другом.

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

а) б) в)

Рисунок 5 - Пара исходных стер«» изображений и результат обработки: левое (а) н пряное (б) изображения "уепив", карта сдвигов (в).

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

В заключении представлены основные результаты работы.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

! Баи данных стерео изображений М^йсИеЬш'у Со11е$е доступна на Интернет-ресурсе vision.middleburv.edu.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Копылов A.B., Карцева A.C. Оптимизационные критерии и алгоритмы сглаживания сигналов и изображений, // Математические методы в технике и технологиях - ММТТ-19: сб. трудов XIX международной конференции. В 10 т. Т.2. Секция 2 / под об. ред. B.C. Балакирева. - Воронеж, Воронеж, гос. технол. акад., 2006, С. 167-170

2. Kopylov A., Karceva A. Optimization Criteria for Signal and Image Smoothing Algorithms. Pattern recognition and Information Processing: Proceedings of the Ninth International Conference (22-24 may 2007, Minsk, Republic of Belarus, vol.1. - Minsk: United Institute of Informatics problems of National Academy of Sciences of Belarus, 2007. -pp 208-212

3. Копылов A.B., Карцева A.C. Оптимизационные критерии со штрафом в виде модуля для сглаживания сигналов и изображений. // Математические методы в технике и технологиях - ММТТ-20: сб. трудов XX международной конференции. В 10 т. Т.2. Секция 2 / по д об. ред. B.C. Балакирева. - Ярославль, Изд-во Яросл. гос. техн. ун-та, 2007, С. 25-28

4. Копылов A.B., Карцева A.C. Оптимизационные критерии и алгоритмы сглаживания сигналов и изображений с сохранением границ. // Искусственный интеллект. 1П1Ш МОП I HAH Украши «Наука i сювгга», № 2,2006, С. 80-84

5. Копылов A.B., Карцева A.C. Сглаживание сигналов и изображений с сохранением границ методом динамического программирования // Известия ТулГУ. Технические науки, вып.З. - Тула: Изд-во ТулГУ, 2008, С.211-217.

Изд. лиц. ЛР № 020300 от 12.02.97. Подписано в печать 18.02.2010. Формат бумаги 60x84 1/16. Бумага офсетная. Усл. печ. л. А^ Уч.-изд. л. Тираж /¿?&ю. Заказ <)&/

Тульский государственный университет. 300600, г. Тула, просп. Ленина, 91

Отпечатано в Издательстве ТулГУ 300600, г. Тула, просп. Ленина, 9:5.

ВВЕДЕНИЕ.

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

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

1.1.1 Задача сглаживания сигналов и изображений.

1.1.2 Задача оценивания нестационарной регрессии.

1.1.3 Спектрально-временной анализ.

1.1.4 Задача оценивания портфеля инвестиционной компании.

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

1.1.6 Задача восстановления карты высоты по паре стерео снимков с учетом резких перепадов высот и наложения объектов.

1.1.7 Локальный текстурный анализ изображений.

1.2 Оптимизационный подход к сглаживанию данных.

1.3 Общий алгоритм динамического программирования.

1.4 Основные задачи исследования.

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

2.1 Оптимизационные критерии в задаче динамического программирования.

2.1.1 Оптимизационный критерий с модулем разности значений двух локальных параметров модели.

2.1.2 Функции связи для трех соседних параметров модели.

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

2.2.1 Дискретная процедура.

2.2.2 Параметрическая процедура.

2.3 Процедура оценивания параметров сигналов для критерия с функцией связи трех аргументов.

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

3.1 Оптимизационные критерии для изображений в задаче динамического программирования.

3.2 Алгоритм динамического программирования «вперед и навстречу».

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

4.1 Критерии качества изображения.

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

4.3 Экспериментальное исследование алгоритмов в задаче совмещения изображений.

4.4 Экспериментальное исследование алгоритмов в задаче оценивания нестационарной регрессии.

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

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

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

Изображения при компьютерной обработке определены на дискретном множестве элементов Т = ^ = (¿,5/,)} > называемых пикселами, которые в отличие от сигналов упорядочены вдоль двух дискретных осей Т = {1 = : Г, = 1г = .

Многие современные задачи обработки сигналов и изображений можно рассматривать как задачи оценивания параметров соответствующих моделей X еХ. Для сигналов примерами моделей могут служить регрессионная модель нестационарных сигналов [1,2, 3], модель в виде последовательности мгновенных спектров и т.п. Для изображений - авторегрессионная или спектральная модель текстуры [4, 5, 6, 7], модель на основе законов стереопроецирования для пары изображений [8, 10, 11, 12, 13].

Формально задача может быть поставлена следующим образом: для всех элементов исходных данных У-(у1,(еТ) стоит задача найти оценку параметров х е X некоторой локальной модели х[ , которые в свою очередь образуют в совокупности общую модель сигнала или изображения Х-{хп1&Т). Далее будем считать, что модель определена на том же множестве элементов массива данных / е Т и принимает значения л*, е X из множества, специфичного для каждой конкретной задачи.

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

Универсальный способ построения моделей сигналов и изображений дает оптимизационный подход [15, 18, 21, 23, 26, 27], получивший широкое распространение, который позволяет представить ряд задач из самых разных областей обработки данных в единых терминах, в отличие от ситуации, когда исследователи вынуждены создавать свои методы и алгоритмы для каждой отдельной задачи, основываясь на специфических свойствах и эвристиках, что усложняет использование результатов в смежных областях анализа данных. В данной работе диссертационное исследование проводится в рамках оптимизационного подхода к анализу данных.

Суть оптимизационного принципа заключается в поиске модели из заданного семейства путем минимизации подходящей функции J{X\Y), играющей роль несоответствия между исходным массивом У и моделью X, и называемой оптимизационным, или целевым, критерием. Важной характеристикой критерия является то, что число оптимизационных переменных равно, как правило, количеству отсчетов сигнала или числу пикселей изображения, что переводит задачу оптимизации в ранг многомерной.

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

Основным противоречием представляется то, что оптимизационный критерий, как правило, является гладкой функцией, что приводит к сглаживанию неоднородностей модели, и поэтому когда предполагается 6 наличие явных скачков или разрывов, которые необходимо оставить, данный вид критерия становится неадекватным решаемой задаче. Так, например, эффективный оптимизационный алгоритм, основанный на принципе динамического программирования, «вперед и навстречу» [25, 31, 38, 42] использует семейство квадратичных функций. Обладая линейной вычислительной сложностью относительно числа целевых переменных, такой алгоритм позволяет при минимальных затратах вычислительных ресурсов получить относительно корректную карту высот в задаче стереопроецирования [38, 42], однако в силу особенностей квадратичных функций в тех областях, где предполагается резкие перепады высот, полученная оценка будет неадекватной [85].

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

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

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

Для разрешения этого противоречия был разработан метод оценивания параметров модели анализируемого сигнала или изображения на основе принципа динамического программирования для случая, когда целевая функция является суммой функций трех упорядоченных аргументов. Критерий такого типа называется ленточно-сепарабельным, а в работе предложена процедура оптимизации подобных критериев, именуемая процедурой ленточно-сепарабельного динамического программирования, в основе которой лежит идея преобразования графа соседства к сериальному виду, в частности, к цепочечному путем объединения двух и более переменных в одну. Такой критерий содержит меньшее число векторных аргументов и, как будет показано далее, для его оптимизации можно-использовать процедуру, основанную на принципе динамического программирования [29, 36].

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

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

В третьей главе рассматриваются критерии и алгоритмы оценивания параметров моделей изображений, построенные на основе оптимизационного подхода, и реализации алгоритмов с использованием принципа динамического программирования; показано, что разработанный ранее принцип разбиения графа в виде решетки на последовательность поддеревьев [42, 48] также может быть применен при решении задачи оптимизации предложенного критерия, сохраняющего неоднородности модели.

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

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

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

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

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

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

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

1. Носко В.П. Эконометрика: Введение в регрессионный анализ временных рядов. Электронный ресурс. Москва. - 2002. - 254 с.

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

3. Kiiveri Н.Т., Campbell N.A. Allocation of remotely sensed data using Markov models for spectral variables and pixel labels. Technical report. Perth: Division of Mathematics & Statistics, CSIRO, 1986.

4. Ripley B.D. Statistics, images and pattern recognition (with discussion). Canad. J. Statist., 1986, 14, pp. 83-111.

5. Paar, and W. Polzleitner, "Robust disparaty estimation in terrain modeling for spacecraft navigation", Proceedings of the 11th International Conference on Pattern Recognition. International Association for Pattern Recognition, 1992.

6. M.J. Hannah, "A system for digital stereo image matching", Photogrammetric Engineering & Remote Sensing, Vol. 55, № 12, pp. 17651770, December, 1989.

7. Kittler J., Fuglein J. Contextual classification of multispectral pixel data. Image Vision Comput., 1984, 2, 13-29.

8. J.J. Rodriguez, and J.K. Aggraval, "Matching aerial images to 3-D terrain maps", IEEE Transactions on Pattern Analysis and Machine Intelligens, Vol. 12, № 12, Desember, 1990, pp. 1138-1149.

9. T.C. Pong, R.M. Haralick, and L.G. Shapiro, "Matching topographic structures in stereo vision", Pattern Recognition Letters, Vol. 9, February, 1989, pp. 127-136.

10. Sage, and J.T. Melse, Estimation Theory and Application to Communication and Control, McGraw Hill, N.Y., 1972.

11. Катыс Г.П. Оптические информационные системы роботов-манипуляторов. М.: Машиностроение, 1977, 272 с.

12. Гиммельфарб Г.Л., Залесный А.В. Цифровая обработка изображений,представляемых моделями марковских случайных полей. Киев,

13. Балакришнан А. Теория фильтрации Калмана: Пер. с англ. М.: Мир, 1988. 168 с., ил.

14. Terzopoulos D., Multilevel Computation Processes for Visual Surfase Reconstruction, Computer Vision, Graphics and Image Processing, 24, No. 1, 52-96 (1983).

15. Mottl V.V., Blinov А.В., Kopylov A.V., Zheltov S.U. Quasi-statistical approach to the problem of stereo image matching. // SPIE Proceedings, 1994, Vol. 2363, pp. 50-61.

16. Mottl V.V., Blinov А.В., Kopylov A.V., Zheltov S.U. Processing stereoscopic images on the basis of random field interpolation. 5th International Workshop on Digital Image Processing and Computer Optic "Image Processing and Computer Optic"

17. Mottl V.V., Kopylov A.V. Algorithms of image matching for raster disturbances. // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications, 1996, Vol. 6, № 1, P. 164-167

18. Mottl V.V., Kopylov A.V. Algorithms for matching images with raster distortions. // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications, 1996, Vol. 6, № 4. P. 697-703

19. Mottl V.V., Kopylov A.V., Kostin A.A. Edge-preserving in generalized smoothing of signals and images. // Proceedings of the 14th International Conference on Pattern Recognition. Brisbane, Australia, August 16-20, 1998. Volume II, pp. 1579-1581.

20. Моттль В.В., Двоенко С.Д. , Блинов А.Б., Копылов А.В. Случайные марковские поля с древовидной структурой в задачах анализа массивов упорядоченных данных. Известия Тульского государственого университета, серия «Вычислительная техника. Автоматика.

21. Управление.» Том 2., выпуск 3 «Управление».:- Тульский государственный университет, 2000 г. стр. 109 -121.

22. Копылов А.В., Ермаков А.С., Киттлер Дж., Моттль В.В. Измерение сходства фотопортретов для безпризнаковой идентификации личности. Доклады 10-й Всероссийской конференции «Математические методы распознавания образов» (ММРО-Ю), Москва, 2001, с. 221-225.

23. Mottl V., Blinov A., Kopylov A., Zabusky N., Muchnik I. Variational approach to the evaluation of motion of coherent structures in fluid dynamic massive data sets. Pattern Recognition and Image Analysis, Vol. 11, 2001, No.3, pp. 583-596.

24. Harry М. Markowitz, Portfolio Selection, Journal of Finance,- 7, no. 1 (March 1952), pp. 77-91.

25. Уильям Ф. Шарп, Гордон Дж. Александер, Джеффри В. Бейли, Инвестиции: Пер. с англ. М.: ИНФРА-М, 2003.

26. Krasotkina O.V., Mottl V.V., Kopylov A.V. Algorithms of Estimation of Nonstationary Regression in Signal Analysis. Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003, pp. 127-131.

27. Ermakov A. S., Kostin A. A., Kopylov A. V., Mottl V. V., Kittler J. Elastic kernel functions for image recognition. Pattern Recognition and Image Analysis, Vol. 13, No. 1, 2003, pp. 98-100.

28. A.V. Kopylov, D.A. Dmitriev, V.V. Mottl Algorithms of Approximate Pairwise Separable Optimization for Image Processing. Pattern Recognition and Image Analysis, Vol. 1.3, № 1, 2003, pp. 90-94.

29. Bellman Functions on Trees for Segmentation, Generalized Smoothing, Matching and MultiAlignment in Massive Data Sets. DIMACS Technical Report 8-15. / Rutgers University, USA. 1998. - P.63

30. Джонс Т. Программирование искусственного интеллекта в приложениях. Пер. с англ. Осипов А.И. М.:ДМК-Пресс. - 2004. -С.245

31. Пожуева И. С. Эволюционная оптимизация многомерных функций / И. С. Пожуева, С. А. Субботин, А. А. Олейник // HoBi матер!али i технологи в металургн та машинобудувамнi. 2006. - № 1. - С. 70-72.

32. Розанов Ю.А. Теория вероятностей, случайные процессы и математическая статистика. / Розанов Ю.А. М.: Наука. - 1989. - С. 495

33. Журавель И.М. Краткий курс теории обработки изображений. / Электронный ресурс. / Консультационный центр MATLAB / http://matlab.exponenta.ru/.

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

35. Сойфер В.А., Гашников М.В., Глумов Н.И. и др. Методы компьютерной обработки изображений. М.: Физ- матлит, 2001. 784 с.

36. Власенко В.А., Лаппа Ю.М., Ярославский Л.П. Методы синтеза быстрых алгоритмов свертки и спектрального анализа. М.: Наука, 1990.- 180 с.

37. Цифровая обработка изображений в среде MATLAB Комплект. / Р. Гонсалес, Р. Вудс, С. Эддинс ; пер. с англ. В. В. Чепыжова. М. : Техносфера, 2006. - 615 с.

38. Winkler G. Noise Reduction in Images: Some Recent Edge-Preserving Methods. / Technical report. Institute of Biomathematics and Biometrics GSF, Germany. 1998. - P. 68.

39. A. Gotchev, Finland K. Egiazarian, J. Vesma, T. Saramaki. Edge-preserving image resizing using modified B-splines. // Proceedings of the Acoustics, Speech, and Signal Processing, 2001. on IEEE International Conference -Volume 03.-2001.-P. 1865-1868.94

40. Geman S., and Geman D. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans, on PAMI, Vol. 6, November 1984, pp. 721-741.

41. Robin Pemantle. A survey of random processes with reinforcement Электронный ресурс. I Robin Pemantle. // Probability Surveys. Volume 4.-2007.

42. Dron, Lisa. The multiscale veto model: A two-stage analog network for edge detection and image reconstruction / Электронный ресурс, статья. / http://www.springerlink.com/ . 2006.

43. Sylvain Paris, Pierre Kornprobst, Jack Tumblin, Fredo Durand. A Gentle Introduction to Bilateral Filtering and its Applications / Электронный источник, статья. / http://people.csail.mit.edu/- 2008.

44. Li Weibin, Liu Fang, Jiao Licheng, Zhang Shuling, Li Zongling. Improved MLV filter to remove multiplicative noise / Электронный ресурс, статья. / http://www.springerlink.com/. 2006.

45. Kopylov. Parametric dynamic programming procedures for edge preserving in signal and image smoothing // Proceedings of the 7th International Conference on Pattern Recognition.and Image Analysis, St.Petersburg October 18-23, 2004. Volume I, pp. 281-284.

46. Kopylov A.V. Parametric dynamic programming procedures for edge preserving in signal and image smoothing. Pattern Recognition and Image Analysis, Vol. 15, No. 1, 2005. P. 227-230

47. Kopylov A.V. Dynamic programming procedures for image analysis. Proceedings of the Eight IASTED International Conference INTELLIGENT SYSTEMS AND CONTROL, October 31 November 2, 2005, Cambridge, USA.: ACTA Press, pp. 404-409.- 515 p.

48. Копылов А.В. Алгоритмы обработки изображений на основе древовидных марковских моделей. Искусственный интеллект. ТТТТТТТ МОНI НАН Украши «Наука i освгга», № 2, 2006, С. 164-168

49. Kopylov. Row-wise aggregation of variables in dynamic programming algorithm for image processing. //7th Open German/Russian Workshop on Pattern Recognition and Image Understanding. August 20—23, 2007. Ettlingen, Germany.

50. Melnikov P.A., Kopylov A.V. Row-wise aggregation of variables in dynamic programming algorithm for image processing // PRIA-8-2007, 8th International Conference, Yoshkar-Ola, RF, October, 8-13, 2007

51. Кориков A.M., Ангелов М.П., Сырямкин В.И. //Корреляционно-экстремальные системы обработки информации и управления. Томск, 1980, №5, С. 218-229.

52. Levine M.D., O'Handley D.A., Yagi G. M. Computer Determination of Depth Maps, Computer Graphics and Image Processing, 2, No. 2, 1973, pp. 131-150.

53. Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М.: Наука, 1977.

54. Моттль В.В., Мучник И.Б. Сегментация и оценивание параметров случайных полей со скачкообразно изменяющимися свойствами. Статистические проблемы управления, 1988, вып. 83. Вильнюс, Институт математики и кибернетики АН Лит. ССР, с. 252-257.

55. Pincus М. A closed form solution of certain programming problems. Oper. Res., 1968, 16, pp. 690-694.

56. Pincus M. A Monte-Carlo method for the approximate solution of certain types of constrained optimization problems. Oper. Res., 1970, 18, 12251228.

57. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing. Science, 1983, 220, 671-680.,

58. Щербина O.A. Методологические аспекты динамического программирования. //Динамические системы. Вып. 22. — 2007. — С. 2136.

59. Копылов А.В., Карцева А.С. Оптимизационные критерии и алгоритмы сглаживания сигналов и изображений с сохранением границ. // Искусственный интеллект. 1ПШ1 МОН I НАН Украши «Наука i освгга», № 2, 2006, С. 80-84

60. Копылов А.В., Карцева А.С. Сглаживание сигналов и изображений с сохранением границ методом динамического программирования // Известия ТулГУ. Технические науки, вып.З. Тула: Изд-во ТулГУ, 2008, С.211-217.