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

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

1.Введение

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

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

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

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

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

/>

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

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

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

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

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

/>

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

/>.

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

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

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

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

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

/>.

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

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

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

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

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

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

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

 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<sub/> = Gg<sub/>, то перейти  кшагу 4.

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

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

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

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

David L. Copingwith Discontinuities in Computer Vision: Their Detection, Classification, andMeasurement// 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 PatternAnalysis and Machine Intelligence, vol.13, №.5, 1991.

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