Динамическое программирование и способы описания двумерных изображений

Материал из Техническое зрение
Перейти к: навигация, поиск

Как известно, строгое обобщение метода динамического программирования на случай оптимизации функционалов от функций, имеющих более одного аргумента, сталкивается с серьезными проблемами, поскольку уже координаты точек из ${R}^{2}$, в отличие от точек ${R}^{1}$, не являются полностью упорядоченными. По этой причине $\textit{граф структурных связей}$ между элементами (пикселами) изображения, в отличие от аналогичного графа для элементов одномерных функций, имеет вид не $\textit{цепи}$, а $\textit{решетки}$, то есть включает множество $\textit{циклов}$. Между тем, как известно из теории динамического программирования, этот метод работает только для таких структур, граф структурных связей между элементами которых имеет вид $\textit{ациклического графа}$ (ACG) или $\textit{дерева}$ , поскольку только для таких графов существует возможность в любой точке разделить все влияющие на результат вычислений элементы на две группы: те, что находятся "выше" по дереву, и те, что "ниже". Таким образом, растровое изображение (прямоугольная решетка пикселов) оказывается неподходящей структурой данных для непосредственного строгого применения методов динамического программирования.

Эта проблема породила, с одной стороны, ряд работ, предлагающих другие вычислительные техники для оптимизации целевых критериев на дискретных двумерных функциях, среди которых выделяется, в частности, группа подходов, основанных на технике "имитационного отжига" , а с другой стороны - стремление к разработке таких структурных моделей двумерных объектов, которые бы достаточно адекватно описывали яркостно-геометрическую и/или топологическую структуру изображения, но при этом, в отличие от решетки пикселов, имели искомый вид ациклического графа. Однако методы $\textit{распространения состояний}$ (evidence propagation) типа имитационного отжига являются существенно итеративными и, как и большинство других итеративных методов оптимизации, не гарантируют сходимости решения к искомому глобальному оптимуму. С практической точки зрения получаемые этими методами квазиоптимальные решения во многих случаях являются "достаточно хорошими", однако с точки зрения реализации проективных морфологических проекторов их квазиоптимальность является принципиальным недостатком. Поскольку все доказательства проективности тех или иных операторов по необходимости основаны на том, что соответствующие критерии являются выпуклыми, что и обеспечивает единственность оптимального решения, квазиоптимальный вычислительный метод сразу превращает хорошо обоснованный критерий в плохо или неопределенно обоснованный, что автоматически делает реализованный таким образом оператор непроективным (негарантированно проективным). Следовательно, необходимо двигаться по второму пути и искать адекватные каждой конкретной задаче способы реализации методов динамического программирования для двумерных и трехмерных данных. Таких попыток известно множество, причем наиболее успешными, как и следовало ожидать, они оказываются при описании изображений объектов "высокого" уровня - например, структурных остовов в методе двумерных и трехмерных $\textit{обобщенных цилиндров}$ . Однако чем ближе мы оказываемся к уровню растровых данных, тем труднее описать их ациклическими графами так, чтобы не были потеряны какие-то существенные характерно двумерные свойства изображения. Впрочем, для некоторых частных задач такие решения найдены. Так, для анализа бинарных двумерных образов хорошо известна техника построения $\textit{морфологических остовов}$ (skeletons) с последующим разрывом циклов в наиболее "напряженных" узлах. Для другой специфической задачи - стереоотождествления - во многих работах используется граф, представляющий изображение в виде строковых цепочек, связанных между собой только по одному опорному столбцу. Такое представление в виде "дерева строк" достаточно адекватно задаче анализа ректифицированных стереопар, в которых строки двух изображений действительно попарно соответствуют друг другу, но вряд ли может быть признано в качестве общей структуры, универсально пригодной для решения основных типовых задач анализа изображений. Таким образом, вопрос о выборе структуры представления двумерных и трехмерных растровых данных в методе динамического программирования остается на сегодня открытым и является предметом интенсивных исследований.

Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты