Содержание к диссертации
Введение
1. Проблема оценивания параметров моделей сигналов и изображений с сохранением локальных особенностей 10
1.1 Примеры прикладных задач оценивания параметров моделей сигналов и изображений 11
1.1.1 Задача сглаживания сигналов и изображений 11
1.1.2 Задача оценивания нестационарной регрессии 12
1.1.3 Спектрально-временной анализ 14
1.1.4 Задача оценивания портфеля инвестиционной компании 16
1.1.5 Выделение контуров объектов и сегментация изображений в задачах распознавания образов и анализа сцен 18
1.1.6 Задача восстановления карты высоты по паре стерео снимков с учетом резких перепадов высот и наложения объектов 20
1.1.7 Локальный текстурный анализ изображений 21
1.2 Оптимизационный подход к сглаживанию данных 23
1.3 Общий алгоритм динамического программирования 36
1.4 Основные задачи исследования 41
2. Алгоритмы оценивания параметров сигналов на основе принципа динамического программирования 43
2.1 Оптимизационные критерии в задаче динамического программирования 43
2.1.1 Оптимизационный критерий с модулем разности значений двух локальных параметров модели 46
2.1.2 Функции связи для трех соседних параметров модели 47
2.2 Процедура оценивания параметров сигналов для критерия, содержащего функцию связи двух аргументов 48
2.2.1 Дискретная процедура 48
2.2.2 Параметрическая процедура 49
2.3 Процедура оценивания параметров сигналов для критерия с функцией связи трех аргументов 55
3 Алгоритм оценивания параметров моделей в задачах анализа изображений на основе принципа динамического программирования 59
3.1 Оптимизационные критерии для изображений в задаче динамического программирования 59
3.2 Алгоритм динамического программирования «вперед и навстречу». 70
4 Экспериментальное исследование алгоритмов оценивания параметров модели в прикладных задачах 74
4.1 Критерии качества изображения 74
4.2 Экспериментальное исследование алгоритмов в задаче сглаживания изображений 76
4.3 Экспериментальное исследование алгоритмов в задаче совмещения изображений 77
4.4 Экспериментальное исследование алгоритмов в задаче оценивания нестационарной регрессии 81
Основные выводы и результаты работы 86
Список использованной литературы 88
- Выделение контуров объектов и сегментация изображений в задачах распознавания образов и анализа сцен
- Задача восстановления карты высоты по паре стерео снимков с учетом резких перепадов высот и наложения объектов
- Процедура оценивания параметров сигналов для критерия, содержащего функцию связи двух аргументов
- Алгоритм динамического программирования «вперед и навстречу».
Введение к работе
Актуальность работы.
Многие современные задачи обработки сигналов и изображений могут быть представлены как задачи оценивания параметров соответствующих моделей, выбранных исходя из условий конкретной задачи и априорных предположений о ее природе. Для сигналов примерами таких моделей могут служить регрессионная модель нестационарных сигналов, модель в виде последовательности мгновенных спектров и т.п. Для изображений – авторегрессионная или спектральная модель текстуры, модель на основе законов стереопроецирования для пары изображений и т.д.
Решение практических задач, таких как оценивание нестационарной регрессии или построение плотной карты сдвигов в стереопроецировании, часто требует резких изменений параметров модели, чтобы сохранить локальные особенности, возможно скрытые шумом в анализируемых данных. Однако существующие методы оценивания параметров моделей, в которых ограничения на класс используемых моделей часто выражаются в виде предположений о гладкости, либо не способны сохранять локальные неоднородности, либо используют специфические методы и модели, усложняющие использование результатов в смежных задачах анализа данных. Таким образом, задача разработки алгоритмов оценивания локальных параметров моделей с сохранением неоднородностей является актуальной для обработки сигналов и изображений.
Универсальный подход к оцениванию параметров моделей сигналов и изображений дает оптимизационный принцип, заключающийся в поиске модели из заданного семейства путем минимизации подходящей функции, играющей роль несоответствия между исходным массивом и моделью, и называемой оптимизационным, или целевым, критерием.
Проблемная ситуация заключается в том, что оптимизационный критерий часто является гладкой функцией, что приводит к сглаживанию неоднородностей модели, и поэтому когда предполагается наличие явных скачков или разрывов, которые необходимо оставить, данный вид критерия становится неадекватным решаемой задаче.
Разрешение противоречия состоит в том, чтобы найти такой критерий, чей вид лучше всего соответствовал бы априорным предположениям о наличии локальных особенностей в модели, и, таким образом, не запрещал бы перепады значений там, где они необходимы для согласования значений параметров модели с исходной информацией, то же время обеспечивая требуемую гладкость во всех оставшихся точках сигнала или растра изображения.
Важным требованием является также то, что процедура оптимизации критерия должна быть эффективной с вычислительной точки зрения, поэтому в работе предложена процедура на основе динамического программирования для оптимизации критериев специального вида, называемых сепарабельными, и показано, что выбор модуля разности значений соседних элементов модели в качестве локальных оценочных функций в составе оптимизационного критерия позволяет решить поставленную задачу.
Другая проблемная ситуация заключается в том, что в некоторых практических задачах, например задаче анализа инвестиционного портфеля, необходимо сохранять локальные особенности первой разности значений соседних параметров модели. Однако в этом случае в критерий перестает быть сепарабельным, а задача его оптимизации не может быть решена в рамках классической процедуры динамического программирования.
Для разрешения этого противоречия был разработан метод оценивания параметров модели анализируемого сигнала или изображения на основе принципа динамического программирования для случая, когда целевая функция является суммой функций более чем двух упорядоченных аргументов. Критерий такого типа называется ленточно-сепарабельным, а в работе предложена процедура оптимизации подобных критериев, именуемая процедурой ленточно-сепарабельного динамического программирования.
Объект исследования: сигналы и изображения в задачах анализа данных, где возникает необходимость отслеживать и сохранять локальные особенности модели, например, перепады значений сигналов и границы яркости для изображений.
Предмет исследования: методы оценивания локальных параметров модели в рамках оптимизационного подхода к анализу сигналов и изображений.
Цель работы. Целью диссертационной работы является разработка алгоритмов оценивания параметров модели в задачах обработки сигналов и изображений, обеспечивающих повышенную точность и быстродействие.
Задачи исследования. Для достижения поставленной цели в диссертации сформулированы и решены следующие задачи:
-
Формальная постановка задачи оценивания локальных параметров модели с сохранением неоднородностей в задачах анализа сигналов и изображений как задачи сепарабельной оптимизации с критерием, содержащим модуль разности значений соседних параметров модели.
-
Исследование свойств оптимизационного критерия, содержащего модуль разности локальных параметров модели в соседних точках.
-
Создание параметрической процедуры оптимизации целевой функции с модулем разности значений параметров в соседних узлах модели.
-
Разработка неитерационной дискретной процедуры оптимизации целевой функции с модулем второй разности.
-
Применение разработанных процедур для решения практических задач анализа данных, в частности задачи анализа инвестиционного портфеля и задачи реконструкции трехмерных объектов по плоским изображениям.
Методы исследования базируются на использовании методов динамического программирования, методов парно-сепарабельной оптимизации.
Научная новизна состоит в том, что предложена параметрическая процедура оптимизации целевой функции с модулем разности значений в соседних точках модели на основе принципа динамического программирования, разработан метод оптимизации ленточно-сепарабельной целевой функции, который распространен на класс прикладных задач обработки данных, где необходимо сохранять локальные особенности массива данных.
Положения, выносимые на защиту.
-
Формальная постановка задачи согласования локальных значений модели с сохранением неоднородностей как задачи динамического программирования с критерием, содержащим модуль разности значений соседних целевых переменных.
-
Неитерационный алгоритм оценивания локальных значений параметров модели сигнала путем решения задачи парно-сепарабельной оптимизации с сохранением локальных особенностей на основе процедуры динамического программирования.
-
Неитерационная дискретная процедура оптимизации целевой функции с модулем второй разности локальных значений модели.
-
Применение неитерационной процедуры обработки сигналов и изображений с сохранением границ для решения практических задач.
Достоверность полученных результатов подтверждается доказанными математическими утверждениями и модельными экспериментами.
Практическая значимость. Разработанные концепции и методы позволяют строить линейные по вычислительной сложности алгоритмы решения широкого класса прикладных задач анализа сигналов и изображений.
Связь с плановыми научными исследованиями. Работа выполнена при поддержке Государственной научно-технической программы РФ «Перспективные информационные технологии», грантов Российского фонда фундаментальных исследований №08-01-99003-р_офи, 04-01-08038-офи_а, 06-07-89249-офи_а, 06-01-00412-офи_а.
Реализация и внедрение результатов работы. Результаты исследования применены для создания новой методики анализа данных.
Апробация работы. Основные положения и результаты диссертации докладывались на международных конференциях «Интеллектуализация обработки информации 2006» (Алушта, Украина, 2006), Pattern Recognition and Image Processing 2007 (Минск, Беларусь, 2007), на ежегодных научных конференциях профессорско-преподавательского состава ТулГУ (Тула, 2004-2006 гг.), на заседаниях кафедры АТМ ТулГУ (Тула, 2008 г.).
Публикации. По тематике исследований опубликовано 5 статей из них 4 на русском языке, из них 1 статья в издании, рекомендованном ВАК.
Структура и объем работы. Диссертация состоит из введения, четырех глав, основных выводов, списка литературы и приложений. Материал изложен на 97 страницах, содержит 18 рисунков, список литературы из 85 наименований.
Выделение контуров объектов и сегментация изображений в задачах распознавания образов и анализа сцен
Теория распознавания образов разрабатывает методы построения формальных правил соотнесения поступающего сигнала или изображения с одним из источников. Для того, чтобы можно было применить данную теорию, необходимо прежде указать, какие свойства сигнала или изображения существенны для принятия решения о его источнике и в каких единицах эти свойства должны измеряться. После того, как такие свойства выбраны, каждый конкретный сигнал или изображение характеризуется конкретным набором их значений или, как говорят, оказывается представленным в виде точки в просгранстве полезных признаков.
Таким образом, прежде чем обратиться к теории построения правил распознавания в некотором уже зафиксированном пространстве признаков, необходимо решить несравненно более сложную проблему их выбора, то есть представления исходного массива данных в виде, удобном для принятия окончательного решения. К тому же, в очень многих прикладных задачах результат предварительной обработки массива данных имеет самостоятельную ценность.
В то же время вопросы предварительной обработки сигналов и изображений теоретически разработаны существенно слабее. Несмотря на тот факт, что разнообразным задачам и алгоритмам первичного анализа посвящена обширная литература, каждая из таких задач рассматривалась отдельно от других независимыми исследователями для решения конкретных прикладных задач. Методы обработки сигналов и изображений, разработанные для каждой частной задачи, используют специфические системы понятий и специфический математический аппарат. В публикациях, посвященных этим методам, как базовые теоретические положения, так и результирующие алгоритмы излагаются с использованием специальной терминологии, часто не пересекающейся с терминологией, используемой для изложения подходов к решению других задач.
В задаче сегментации исходного изображения на однородные области заданного числа классов принадлежность каждого пиксела к тому или иному классу естественным образом выражается переменной, принимающей значения из конечного числа индексов классов X = {1, }. Сегментацию некоторого изображения естественно строить как совокупность индексов классов для каждого пиксела X = (xt,teT), xt єХ = {1,...,/77}, фактически в виде модельного дискретнозначного изображения.
Поскольку сегментация обычно используется не самостоятельно, а как часть некоторой системы (например, системы машинного зрения), то с практической точки зрения, качество работы метода оценивается исходя из работы системы в целом. Поэтому один и тот же метод сегментации может оказаться хорошим для одной задачи и плохим для другой. Более общий подход к оценке качества работы метода, не учитывающий конкретного приложения, состоит в тестировании методов на общей базе изображений, для которых известна «правильная» сегментация.
Рассмотрим задачу сегментации изображений в градациях серого. Исходное изображение представляет собой массив оттенков серого Y = ( ),ieT на растре изображения T = (i =(.}. = 1,...,7V,,/2 =l,...,yV2).
Сегментацию изображения выразим в виде последовательности индексов классов X = (XJ), определенных для каждой точки растра изображения, в случае сегментации на два класса х, = {0,1}, например, объект и фон.
Задача восстановления карты высоты по паре стерео снимков с учетом резких перепадов высот и наложения объектов
Рассмотрим в качестве примера задачу совмещения изображений, которая особенно актуальна при построении объемных моделей по паре двумерных снимков, а также почти неизбежно возникает при построении алгоритмов распознавания образов, когда необходимо сравнить предъявленное изображение с эталоном. Как правило, это нельзя сделать, непосредственно сравнивая одноименные элементы двух массивов даже одинакового размера, поскольку фактически эквивалентные элементы почти всегда по-разному расположены на оси переменной или на плоскости растра.
Исходный массив состоит из двух изображений Y и Y" условно первого и второго, а в качестве результата анализа в каждой точке, например, первого изображения, должно быть определено значение так называемой локальной диспаратности в виде двумерного вектора xt=(xt Л\ ), = (АЛ), указывающего сдвиг координат между соответствующими точками в первом t и втором t + xt изображениях. Удобно рассматривать искомые величины сдвигов как действительные числа или векторы, допуская тем самым межпиксельную интерполяцию при установлении соответствий. В качестве результата анализа X = (xt,teT) выступает карта диспаратности, то есть совокупность значений локальных сдвигов х{єХ-Ш2, принимающих значения из множества действительных двумерных векторов, или непосредственно карта высот х, єУ = Е.
Локальный текстурный анализ изображений играет роль аналога спектрально-временного анализа сигналов. Требуется количественно оценить текстуру в окрестности каждой точки растра в виде значения вектора параметров некоторой подходящей математической модели. В качестве такой оценки могут выступать двумерный локальный спектр, отражающий пространственные спектральные свойства изображения, совокупность обычных одномерных спектров сигналов, образованных сечениями картинки в разных направлениях от текущей точки, либо даже просто одномерный спектр в каком-нибудь одном выбранном направлении, однако чаще используют более специальные модели текстуры. В любом случае локальные текстурные свойства изображения в каждой точке J = ( :) характеризуются вектором параметров подходящей модели Х(- Л »—» t ), принимающим значения, аналогично мгновенному спектру сигнала, из множества X = Ш" действительных конечномерных векторов. Совокупность значений параметров по всем точкам растра изображения =(xt,teF) образует результат его локального текстурного анализа.
Много общего с текстурными изображениями имеют массивы данных сейсмической разведки полезных ископаемых, так называемые сейсмические разрезы, состоящие из синхронных записей отраженных сейсмических сигналов, зарегистрированных после инициирующего импульса на земной или водной поверхности большим числом датчиков, обычно расположенных вдоль прямой линии.
Различие локальных текстурных свойств сейсмического разреза объясняется различием механических характеристик породы в соответствующих областях исследуемой подземной толщи. В частности, плохо различимые глазом пространственные спектральные свойств текстуры характеризуют трещиноватость монолитных пород, определяющую их так называемые коллекторские свойства, т.е. способность вмещать нефть или газ.
Космический фотоснимок земной поверхности после выравнивания яркости и цветовое представление его локальных текстурных особенностей. Интенсивности смешиваемых красного, зеленого и синего цветов в каждой точке плоскости изображения отображают значения трех параметров локальной модели текстуры.
Процедура оценивания параметров сигналов для критерия, содержащего функцию связи двух аргументов
Как уже было сказано, частным случаем параметризации является случай конечного множества значений модели X . Тогда оказывается, что на каждом шаге процедуры динамического программирования функции Беллмана можно представить и хранить в памяти вычислительной машины в виде таблицы значений. Такой способ может представлять универсальный способ решения для задач обработки сигналов, в которых иные способы параметризации невозможны.
Рассмотрим общую процедуру динамического программирования для оценивания параметров сигнала. Исходный сигнал Y = (y),t = l,...,N представляет собой действительнозначный вектор, упорядоченный вдоль одной оси дискретных аргументов Т. Модель сигнала X = [x),t - 1,..., iV, как уже было сказано, определена на том же множестве аргументов, чьи локальные параметры могут принимать конечные значения из некоторого множества действительных чисел х( є R .
Процедура оценивания параметров сигнала делает два прохода по всем значениям аргумента. На ходе вперед необходимо вычислить и хранить функции Беллмана. Обратный ход дает окончательную оценку параметров модели. Укажем общий алгоритм работы процедуры динамического программирования: 1. Вычисляется функция Беллмана «/,( ,) на первом шаге, которая согласно общему алгоритму динамического программирования (раздел 1.4) равна узловой функции у/{ (х, J в первом узле графа соседства переменных G. 2. Для всех последующих узлов графа на ходе вперед t = 2,...,N вычислим и запомним функции Беллмана согласно (10). 3. Обратный ход алгоритма начинается с вычисления оптимального значения последнего локального параметра JC модели. 4. Для всех узлов глава соседства / = /V-1,...1 вычислим с помощью обратного рекуррентного соотношения оптимальные значения локальных параметров х , требуемых для решения задачи.
Используя тот такт, что граф соседства имеет вид цепи, для подобных графов соседства значение функции Беллмана на каждом шаге процедуры динамического программирования [40] находится следующим образом:
Теорема 1. Если функция связи yt ,_,( ,, х_,) в целевой функции (5) имеет вид yt ,_, ( ,? ,_,) = "(- xt_x , и 0, а узловые функции и функция Беллмана /,_,( ,_,) выпукла и дифференцируема всюду в области определения, то обратное рекуррентное соотношение #,_,( ,) имеет следующий вид: Один из способов решения задачи с несепарабельным критерием -сведение задачи оптимизации к задаче квадратичного программирования за счет добавления служебных переменных и введения ограничений на них. Получающаяся при этом целевая функция, есть сумма функций не более чем одной векторной переменной, связанной с очередным моментов времени, а ограничения (типа неравенств) наложены лишь на не более чем тройки смежных переменных. Такие задачи оптимизации называются сепарабельными задачами.
Поскольку сам принцип динамического программирования не говорит ничего о том, каким способом необходимо искать минимум при вычислении функций Беллмана, а лишь дает общее направление поиска глобального минимума с помощью разложения задачи на ряд подзадач, можно предложить обобщенную процедуру, основанную на принципе динамического программирования. Подобный подход к несериальному динамическому программированию аналогичен процедуре [40].
Предлагаемый подход к решению задачи оптимизации критерия на графе в виде цепи состоит в попарном перегруппировании исходных скалярных переменных х , t = 1,...,п и их преобразовании в векторные х с двумя компонентами, как показано на рисунке 12.
В этом случае узловые функции и функции связи также являются векторными и связаны со скалярными функциями следующими соотношениями:
Оптимизационный критерий (5) представляет собой сумму функций не более чем двух, но уже векторных переменных, а, следовательно, является парно-сепарабельным, что позволяет применять процедуру, аналогичную рассмотренной выше процедуре динамического программирования. Функции Беллмана будут определяться следующими соотношениями:
Алгоритм динамического программирования «вперед и навстречу».
В этом разделе рассмотрена альтернативная версия процедуры динамического программирования, обеспечивающая независимое определение оптимальных значений отдельных целевых переменных для критерия, содержащего модуль разности соседних локальных параметров модели изображения. Эта процедура названа процедурой «вперед и навстречу» [3], поскольку она опирается на два вида функций Беллмана, левую и правую, рекуррентно пересчитываемых независимо друг от друга в двух противоположных направлениях с последующим поиском оптимального значения целевой переменной в точке встречи на оси аргумента.
Ее центральным понятием, является понятие последовательности функций Беллмана Jt{xt) (8), связанных с частичными целевыми функциями (9) /(Cv,,...,.T17 )=Z v=ovl/s( )+E =J x-i -v где ґ =(y s 0 - фрагмент сигнала слева от текущей точки t. Функция Беллмана для каждого / определяется как минимальное значение соответствующего частичного критерия по всем переменным, кроме последней х, играющей роль ее аргумента J (.г )= min Jt(x ,...)Х(\У ). В данном случае частичные целевые функции «вырезаются» из полной целевой функции в порядке возрастания индекса t, т.е. слева направо, поэтому их естественно назвать левыми частичными критериями, а образуемые ими функции Беллмана — левыми функциями Беллмана. Чтобы подчеркнуть, что такие частичные целевые функции и функции Беллмана формируются с левой стороны от текущей точки оси аргумента сигнала, т.е. со стороны меньших значений индекса t, будем использовать в их обозначении верхний индекс «минус»:
Наряду с левыми частичными критериями, которые определяются слева направо с первого отсчета сигнала, вполне естественно рассматривать симметричные по отношению к ним правые частичные критерии, определяемые с конца сигнала, и соответствующие им правые аналоги функций Беллмана: где Y = (ys, s t) - фрагмент сигнала справа от точки /.
Левые функции Беллмана вычисляются последовательно для t = 1, ...,7V согласно рекуррентному соотношению (53) начиная с ./,( :,) = 11/,( ,). Нетрудно понять, что правые функции Беллмана удовлетворяют совершенно аналогичному рекуррентному соотношению в противоположном направлении начиная с последней правой функции Беллмана J+N(xN) = уN{xN).
Произвольная парно-сепарабельная целевая функция с цепочечной смежностью переменных допускает следующее представление для любого узла цепи:
Соответственно, маргинальная функция переменной л:, определяется выражением Это непосредственно указывает способ построения процедуры для определения оптимального значения одной переменной .v в заданной точке t оси аргумента сигнала для разных вариантов узловой функции у/ (х) в этой точке и разных вариантов пары смежных с ней функций связи у (х ,х ) и у х(х,х ) независимо от оптимальных значений других переменных. Такая процедура состоит в рекуррентном вычислении и запоминании левых функций Беллмана J t{xt) в прямом направлении t = l,... N по рекуррентному правилу (16), начиная с J{{хх) - ц/х{хх), и независимом вычислении правых функций Беллмана J (xt) во встречном направлении / = //,...,1 по правилу (17), начиная с J+N(хд ) = у/N(xN) в последнем узле t = N. Встреча в каждой точке t левой J _x{xt_,) и правой функций Беллмана J (x/+1) непосредственно дает маргинальную функцию в этой точке (58) и оптимальное значение соответствующей целевой переменной:
В работе данная процедура используется для оптимизации критериев, содержащих модуль разности соседних параметров модели изображения. Маргинальные функции представлены параметрически аналогично функциям Беллмана.
Качество изображения определяется большим количеством технических характеристик системы: соотношением сигнал/шум и статистическими характеристиками шума, градационными характеристиками, спектральными (цветовыми) характеристиками, интервалами дискретизации и т.д.
Одним из параметров, которые определяют качество изображений, является контраст. Поскольку изображение имеет сложный сюжетный характер, то это порождает необходимость при определении его контрастности выходить из контраста отдельных комбинаций элементов изображения. При этом все элементы считаются равнозначными, и контраст каждой их пары вычисляется по формуле где Ln L. - яркости элементов сюжетного изображения.
Сюжетность изображения предполагает возможность его использования человеком. Поэтому при оценке контраста, как одного из параметров качества изображения, необходимо учитывать ряд особенностей зрительного восприятия человека.
Далее, применяя правило суммирования контрастов, вычисляют набор величин, которые определяют восприятие каждой пары элементов изображения. Проводя усреднение матрицы локальных контрастов, получают суммарный контраст. Полученный результат может быть использован как один из параметров оценки визуального качества изображения.
Существует еще один метод оценки качества изображения. Его суть состоит в следующем. Экспериментально было установлено, что оптимальное, с точки зрения субъективного восприятия, изображение имеет нормальное распределение яркостей его элементов. Для удобства дальнейших расчетов был применен критерий нормального распределения. По степени отклонения реального распределения яркостей от нормального проводилась оценка качества изображения. Кроме количественной оценки качества изображения, данный метод позволяет получить информацию о наличии и весовом соотношении яркостных градаций изображения. Результаты оценки качества изображения, полученные по данному методу, хорошо коррелируют с субъективной оценкой визуального качества изображения.
Рассмотрим еще один известный эмпирический подход к оценке визуального качества изображения. Для формирования этой оценки рассматриваются такие параметры изображения как среднеарифметическое значение яркостей, полнота использования градаций яркостей, резкость изображения и его обобщенный контраст.
