Бесплатные рефераты


В мире
Календарь новостей
« Фев.2018
Пн.Вт.Ср.Чт.Пт.Сб.Вс.
   1234
567891011
12131415161718
19202122232425
262728    
ВНИМАНИЕ!!!
УВАЖАЕМЫЕ ПОЛЬЗОВАТЕЛИ!!!
Сайт поменял владельца и на нём грядут большие перемены.
Убедительная просьба не пользоваться покупкой рефератов через смс.
ДАННЫЙ СЕРВИС БОЛЬШЕ НЕ РАБОТАЕТ
Стоит вопрос об его удалении, дабы сделать рефераты бесплатными. Извините за неудобство и спасибо за понимание
Поиск реферата

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

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

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

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

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.


ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо А можно заказать оригинальный реферат
Опубликовано: 20.08.10 | [ + ]   [ - ]  
Просмотров: 133
Загрузок: 0
Рекомендуем
{dnmbottom}
БАНК РЕФЕРАТОВ содержит более 70 000 рефератов, курсовых, контрольных работ, сочинений и шпаргалок.