Постановка оптимизационной задачи

3. Постановка оптимизационной задачи

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

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

 Введем числовую характеристику  = , которую будем называть стоимостью вершины графа градиентного изображения. Далее рассмотрим две вершины и V_k и предположим, что эти вершины принадлежат контуру. Очевидно, что любой путь, соединяющий данные вершины можно рассматривать в качестве аппроксимации данного гипотетического контура. Длиной (стоимостью) пути (V₁, V₂, ..., V_m, V_k) будем называть сумму

.

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

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

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

4. Алгоритм выделения контурного изображения

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

4.1. Определения и обозначения

 G_g - граф градиентного изображения;

 G_c - граф контурного изображения;

 E(V₁) - окрестность вершины V₁ = (i₁ , j₁), E(V₁) = ;

) - окрестность графа контурного изображения, E(G⁽ⁱ⁾) =.

4.2. Итерационные шаги алгоритма для связного графа

 Найти вершину , имеющую наименьшую стоимость на графе G_g. Положить G_с⁽⁰⁾=, т.е. на шаге 1⁰ граф G_с⁽⁰⁾ состоит из одной вершины

 Пусть уже построен граф G⁽ⁱ⁾ для некоторого . Тогда, если E(G⁽ⁱ_c⁾) G_g = G_g, то перейти к шагу 4.

 Найти вершину  графа G_g, имеющую наименьшую стоимость, причем V  E(G⁽ⁱ_c⁾). Построить путь, имеющий наименьшую стоимость, от вершины  до множества (графа) G⁽ⁱ⁾. (Это можно сделать с помощью волнового алгоритма). Вершины, принадлежащие этому пути, необходимо добавить к графу G⁽ⁱ⁾. В результате мы получим граф контурного изображения G_с⁽ⁱ⁺¹⁾  на следующем итерационном шаге, , перейти к шагу 2.

 На этом итерационном шаге граф контурного изображения уже будет удовлетворять условию 1. Однако, вполне возможно, условие 3 еще не будет выполняться. Поэтому на шаге 4⁰ алгоритма для всех пар  близко расположенных вершин  = ,  = , удовлетворяющих условию: , необходимо проверить справедливость неравенства . Если это неравенство не выполняется, то для каждой такой пары вершин  необходимо построить путь, имеющий наименьшую стоимость и соединяющий вершины V₁ и V₂ , и добавить вершины, принадлежащие этому пути, к графу G_c.

Список литературы

Spacek L.A. Edge detection of contours and motion detection// Image Vision Compute, vol.4, p.43, 1986.

David L. Coping with Discontinuities in Computer Vision: Their Detection, Classification, and Measurement// IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.13, №5, 1991.

Petrov M., Kittler J. Optimal Edge Detectors for Ramp Edges// IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.13, №.5, 1991.

Дуда Р., Харт П. Распознавание образов и анализ сцен. - М.: Мир, 1976.