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

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

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

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

Изображения при компьютерной обработке определены на дискретном множестве элементов Т = ^ = (?, 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{XY), играющей роль несоответствия между исходным массивом У и моделью X, и называемой оптимизационным, или целевым, критерием. Важной характеристикой критерия является то, что число оптимизационных переменных равно, как правило, количеству отсчетов сигнала или числу пикселей изображения, что переводит задачу оптимизации в ранг многомерной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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