Модели теории графов для выделения контуров по градиентному изображению

А.Г. Броневич, Н.С. Зюзерова

1.Введение

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

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

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

2. Основные определения

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

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

если точка принадлежит контуру, то (обратное утверждение в общем случае неверно);

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

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

Для математического описания таких требований введем в рассмотрение неориентированный граф градиентного изображения. Вершинами этого графа является ЭИ с координатами , для которых . Будем считать, что вершины , этого графа являются смежными, если найдутся такие числа , не равные нулю одновременно, что =. Различные варианты смежных вершин показаны на рис.1 а), б), в), г).

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

.

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

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

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

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

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

.

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

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

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

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

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

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

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

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

E(V1) - окрестность вершины V1 = (i1 , j1), E(V1) = ;

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

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

Найти вершину , имеющую наименьшую стоимость на графе Gg. Положить Gс(0)=, т.е. на шаге 10 граф Gс(0) состоит из одной вершины

Пусть уже построен граф G(i) для некоторого . Тогда, если E(G(ic)) Gg = Gg , то перейти к шагу 4.

Найти вершину графа Gg, имеющую наименьшую стоимость, причем V E(G(ic)). Построить путь, имеющий наименьшую стоимость, от вершины до множества (графа) G(i). (Это можно сделать с помощью волнового алгоритма). Вершины, принадлежащие этому пути, необходимо добавить к графу G(i). В результате мы получим граф контурного изображения Gс(i+1) на следующем итерационном шаге, , перейти к шагу 2.

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

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

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.