Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Графика -> Гонсалес Р. -> "Цифровая обработка изображений" -> 275

Цифровая обработка изображений - Гонсалес Р.

Гонсалес Р., Вудс Р. Цифровая обработка изображений — М.: Техносфера, 2005. — 1072 c.
ISBN 5-94836-028-8
Скачать (прямая ссылка): cifrovayaobrabotkaizobrajeniy2005.djvu
Предыдущая << 1 .. 269 270 271 272 273 274 < 275 > 276 277 278 279 280 281 .. 349 >> Следующая

Можно проиллюстрировать, как только что введенные понятия могут применяться к задаче обнаружения контуров; для этого воспользуемся изображением 3x3, приведенным на Рис. 10.23(a). Номера по периметру суть координаты изображения, а числа в квадратных скобках представляют значения яркости пикселей. Каждому элементу контура, заданному пикселями pnq. припишем стоимость, которую определим как
c(p,q) = H-[f(p)-f(q)], (10.2-6)
где Н — максимальный уровень яркости в изображении (в данном случае 7), a f{p) и /(q) представляют собой значения яркости пикселей р и q соответственно. По соглашению, точкар находится справа от направления обхода элемента контура. Например, на Рис. 10.23(6) элемент контура (1, 2)(2, 2) находится между точками (1, 2) и (2, 2). Если проходить этот элемент слева направо, то точка р будет иметь координаты (2, 2), а точка g — координаты (1,2); следовательно, стоимость элемента контура составит с(р, q) = 7 — [7 — 6] = 6. Это значение записано в рамке под элементом контура. Напротив, если проходить по тому же элементу влево, то точкой р будет точка (1, 2), а точкой
2 3
Рис. 10.23. (а) Область изображения размерами 3x3. (б) Элементы контура и а б В их стоимости, (в) Контур, соответствующий пути с минимальной стоимостью в графе, показанном на Рис. 10.24.
848 Глава 10. Сегментация изображений
Рис. 10.24. Граф для изображения на Рис. 10.23(a). Пунктирной линией выделен путь минимальной стоимости.
q — (2, 2). В этом случае стоимость будет равна 8, как записано на Рис. 10.23(6) в рамке над элементом контура. Для простоты рассуждений предположим, что контуры начинаются в верхней строке изображения и заканчиваются в нижней, так что первый элемент контура может находиться только или между точками (1, 1) и (1, 2) или между точками (1, 2) и (1, 3). Аналогично, последним элементом контура может быть или находящийся между точками (З, 1) и (3, 2), или между точками (3, 2) и (3, 3). Напомним, что точки/? и g должны быть 4-соседями.
На Рис. 10.24 показан граф, относящийся к обсуждаемой задаче. Каждая вершина графа (обозначенная прямоугольником) соответствует какому-то элементу контура на Рис. 10.23. Между двумя вершинами имеется дуга, если соответствующие два элемента контура, будучи соединенными подряд, могут являться участком контура. Как и на Рис. 10.23(6), стоимость каждого элемента контура, вычисленная согласно (10.2-6), показана в рамке рядом с дугой, ведущей к соответствующей вершине. Целевые вершины графа, в которых может закон-
10.2. Связывание контуров и нахождение границ
читься контур, обозначены темным цветом. Существует множество различающихся по стоимости путей из начальной вершины в каждую из целевых вершин. Путь минимальной стоимости (по всем целевым вершинам) показан пунктирной линией; этому пути соответствует контур, изображенный на Рис. 10.23(b).
Вообще говоря, задача отыскания на графе пути минимальной стоимости является нетривиальной по вычислительной сложности, и зачастую приходится жертвовать оптимальностью в пользу скорости вычислений. Приводимый ниже алгоритм является представителем класса процедур, в которых для уменьшения объема перебора используются различные эвристики. Пусть г(п) — оценка минимальной стоимости пути из начальной вершины s в любую из целевых вершин, при условии, что этот путь проходит через вершину п. Эту стоимость можно выразить в виде суммы оценки минимальной стоимости пути из s в п и опенки минимальной стоимости пути из п в целевую вершину, т.е.
r(n) = g(n)+h(n). (10.2-7)
Здесь в качествеg(n) можно выбрать стоимость найденного к этому моменту минимального пути из s в п, а h(n) получают с использованием любых имеющихся эвристических соображений (например, исходя из стоимости пути, ведущего в текущую вершину, далее прослеживаются только определенные вершины). Для проведения поиска на графе с учетом оценки г(п) используется следующий алгоритм:
Шаг 1: Отметить начальную вершину как «открытую» и установить g(s) = 0.
Шаг 2: Если не осталось ни одной «открытой» вершины, то аварийное завершение; в противном случае продолжить выполнение.
Шаг 3: Отметить как «закрытую» ту из «открытых» вершин п, для которой оценка г{п), вычисленная согласно (10.2-7), является минимальной. В случае неоднозначности минимума выбор осуществляется произвольно, но всегда в пользу целевой вершины, если таковая есть.
Шаг 4: Если п является целевой вершиной, то завершение работы; путь, являющийся решением, находится обратным прослеживанием по ранее запомненным указателям. В противном случае продолжить выполнение.
Шаг 5: Расширить вершину «, т.е. построить все выходящие из нее дуги к вершинам-потомкам. Если таковых нет, то перейти к шагу 2.
Шаг 6: Если вершина-потомок «, еще не отмечена, то установить
850 Глава 10. Сегментация изображений
g(ni) = g(n) + c(n,ni).
отметить вершину пj как «открытую» и запомнить указатель от нее обратно к п. Перейти к шагу 2.
Шаг 7: Если вершина-потомок и,- отмечена как «открытая» или «закрытая», то обновить для нее значение стоимости минимального пути из начальной вершины:
Предыдущая << 1 .. 269 270 271 272 273 274 < 275 > 276 277 278 279 280 281 .. 349 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.