Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде Matlab (2006) (1246139), страница 80
Текст из файла (страница 80)
Параметр Жг обозначает направление выходного кода: если он равен 'ваше ', то код имеет то же направление, что и у точек Ь. Если йуг равен 'гечегве', то выбрано противоположное направление. По умолчанию принимается значение 'ваше'. Значит, при выполнении команды с = ХсЬсоае(Ь, сопл) направление выбирается по умолчанию, а команда с = 1сЬсоае(Ь) определяет по умолчанию и направление,и связность.
Пример 11.3. Цепной код Фримана и некоторые его вариации. На рис. 11.2, а) приведено изображение ~ замкнутого обхода, на которое наложен некоторый шум. Целью этого примера является построение цепного кода и первой разности для границы объекта. При взгляде на рис. 11.2, а) становится очевидно, что шумовые фрагменты, касающиеся интересующего нас объекта, приводят к весьма нерегулярной границе, которая не будет правильно отражать общие формы объекта. Сглаживание является обычным процессом при работе с зашумленной границей.
На рис. 11.2, б) приведен результат 8 применения усредняющей маски 9х9 к исходному изображению: (4$6 1: иии!1. Прийтиеаиии~ и оии~июп й = 1аресаа11'аиетаае', 9) П.й. ~ д (Д Если строить цепной код непосредственно для Ь, то это приведет к длинной последовательности с малыми изменениями, которые не обязательно полезны для общего представления формы объекта. Поэтому в качестве естественной и типичной процедуры при построении цепных кодов совершается укрупняющая подвыборка границы с использованием функции ЬвиЬвашр, которая вводилась в предыдущем параграфе: » [в, вп] = ЬвпЬвашр(Ь, 50); Здесь мы воспользовались разделяющей сеткой с шагом примерно в 10% от ширины изображения, которое в нашем случае имеет размеры 570х570 пикгелов.
Полученный результат отображен в виде белых точек на рис. 11.2, д): » я2 = Ьопп621ш(в, М, М, штп(в(:, 1)), ш1п(в(:, 2))); илн в виде соединяющих их отрезков на рис. 11.2, е7', который получен командами » сп = соппессро1у(в(:, 1), в(:, 2)); » я2 = Ьопп421ш(сп, И, И, штп(сп(:, 1)), ш1п(сп(:, 2))); Преимущество такого представления с точки зрения цепного кодирования становится очевидным при сравнении рис, 11.2, г) и е). Цепной код получается из укрупненной последовательности вп: » с = йсЬсойе(вп); Эта команда дает следующие резулы нрующие выводы: » с.
хбуО апв 7 3 » с.(сс 2 2 О 2 2 О 2 О О О О 6 О 6 6 6 6 6 6 б 6 4 4 4 4 4 4 2 4 2 2 2 » с. шш О О О О 6 О 6 6 б 6 б б б б 4 4 4 4 4 4 2 4 2 2 2 2 2 О 2 2 О 2 » с.дЬГМ О 6 2 О б 2 6 О О О 6 2 б О О О О О О О б О О О О О б 2 б О О О » с.61ХХшш О О О б 2 6 О О О О О О О 6 О О О О О б 2 б О О О О б 2 О 6 2 6 Проверяя с. асс, рис. 11.2, е) и с, хбуО, видим, что код начинается слева от изображения и обрабатывается в направлении по часовой стрелке, что совпадает с направлением координат границы. П (458 Глава ! !. Представление и описание 11.2.2.
Приближение ломаной линией минимальной длины Некоторые основы Основную идею аппроксимации мы рассмотрим на простом примере. Предположим, что граница области заключена внутри множества соединенных в цепочку ячеек, как показано на рис. 11.3, о). Это позволяет визуально представить границу области как резиновую ленту, находящуюся между двумя стенками, соответствующими внутренней и внешней границам указанной цепочки ячеек. При стягивании ленты она примет форму, приведенную на рис. 11.3, б), образуя многоугольник с минимальным периметром, который отвечает геометрической форме данной цепочке ячеек.
Рнс. 11.3. а) Граница объ- екта, заключенная е клетки. б) Ломаная лнння мнннмаль- ноя длины а) б) Подход Склански основан на так называемом клеглочном комплексе (или клеточной мозаике), который в нашем случае является множеством квадрагпных Дискретная граница может быть сколь угодно точно приближена ломаной линией. В случае замкнутой границы аппроксимация является точной, когда число отрезков ломаной равно числу точек границы, и каждую пару соседних точек соединяет свой отрезок. Па практике цель аппроксимации ломаной состоит в том, чтобы с помощью как можно меньшего числа отрезков приблизить «самое существенное» в форме границы.
Хороший практический метод приближения заключается в нахождении ломаной линии минимальной длины МРР (М1п1шиш-Рег1ше1ег Ро1уйоп) для границы области. Теоретическое обоснование, а также алгоритм нахождения МРР имеются в классической книге 1ЯЫапв1гу ес а!., 1972) (см, также (К1ш, БЫапз1«у, 1982)). В этом параграфе мы рассмотрим основы этого метода, а также приведем реализацию алгоритма в виде М-функции. Метод ограничивается поиском прост»ах ломаных линий (т.е., не имеющих самопересечений). Кроме того, яз рассмотрения исключаются области, имеющие выступы и отростки шириной в один пиксел.
Такие аномалии можно отделить от области с помощью морфологических методов, а затем добавить к построенной аппроксимирующей линии в соответствующих местах. 1460 ю .и д которые лежат вне или внутри границы ломаной линии, заданной своими вершинами. Полезно разрабатывать процедуру построения МРР, имея перед глазами некоторую иллюстрацию. Для этого мы воспользуемся рис.
11.3 и 11.4. Построение 4-связной границы затемненной области на рис. 11.4, а) будет обсуждаться несколько позже в этом параграфе. После того, как эта граница установлена, следующий шаг заключается в нахождении ее вершин. Эта процедура делается построением их цепного кода Фримана. Изменения кодовых направлений указывают на углы границы. Анализируя изменения направлений, мы двигаемся по часовой стрелке вдоль границы. Тогда достаточно несложно установить и разметить выпуклые и вогнутые вершины, как это сделано на рис. 11.4, б).
Особый способ построения этих маркеров задокументирован в М-функции ш1прегро1у, которая будет обсуждаться далее в этом параграфе. Разметка вершин таким способом также отражена на рис. 11.4, б), которую мы повторяем на рис. 11.5, а). Затемненная область, а также линии квадратной решетки добавлены для наглядности. Граница области не показана, чтобы избежать путаницы при построении ломаных границ на остальных схемах рис. 11.5. Теперь строим исходную ломаную линию, используя для этого только выпуклые вершины (черные кружки), как показано иа рис. 11.5, б). Из свойства 2 мы знаем, что множество выпуклых вершин МРР является подмножеством этого исходного множества выпуклых вершин. Видно, что все вогнутые вершины (белые кружки), лежащие вне начального многоугольника, не образуют вогнутости многоугольника.
Чтобы эти особые вершины стали выпуклыми на следующих стадиях алгоритма, ломаная должна пройти через эти точки. Но мы знаем, что они никогда не смогут стать выпуклыми, поскольку все возможные выпуклые вершины уже учтены к этому моменту (может случиться, что позже их углы могут стать равными 180', но это не скажется на форме многоугольника). Следовательно, все белыс кружки, расположенные вне исходного многоугольника. можно удалить перед дальнейшем анализом, что и сделано на рис. 11.5, в).
Вогнутые вершины (белые кружки), расположенные внутри многоугольника, ассоциированы с вогнутостями на границе, которые были проигнорированы на первом проходе процедуры. Следовательно, их нужно добавить к ломаной, что сделано на рис. 11.5, г). К этому моменту имеются черные вершины, которые перестали быть выпуклыми в новом многоугольнике ~они отмечены стрелками на рис.
11.5, гЯ. Имеется две причины для этого. Первая причина состоит в том, что эти вершины являлись частью исходного многоугольника на рис. 11.5, 6), в который были включены все выпуклые (черные) вершины. Другая причина состоит в том, что черные вершины стали вогнутыми в результате добавления (белых) вершин, как это произошло на рис. 11.5, г).
Значит, все черные кружки многоугольника необходимо проверить, чтобы выяснить, не счали ли величины соответствующих внутренних углов болыпе 180~. Все такие вершины необходимо удалить, а затем повторить процедуру. На рис. 11.5, д) показана лишь одна черная вершина, которая потеряла выпуклость на втором шаге обработки. Процедуру проверки и удаления следует остановить, как только все вершины перестанут менять выпуклость. После этого все вершины с углами 180' можно также удалить, поскольку они лежат на сторонах !~. '. Пред~п~пе'гни 461)) ~~ 462 О .П д ломаной и не влияют на форму окончательного многоугольника.
Граница, изображенная на рис. 11.5, е), представляет собой ломаную минимальной длины МРР нашего примера. Она же приведена на рис. 11.3, б). Наконец, на рис. 11.5, ж) представлена МРР с наложением на исходный клеточный комплекс. Предыдущие рассуждения суммируются в следующих шагах построения МРР области: 1. Построить клеточный комплекс (метод построения будет изложен далее в этом параграфе). 2. Выделить внутреннюю область комплекса. 3. Построить для выделенной на шаге 2 области ее границу с помощью функции Ьоовааг1ев,представив границу в виде 4-связной последовательности координат с направлением обхода по часовой стрелке.
4. Для этой 4-связной последовательности получить цепной код Фримана с помощью функции 1сЬсоде. 5. Отметить выпуклые (черные кружки) и вогнутые (белые кружки) вершины на цепном коде. 6. Построить исходный многоугольник, используя все черные кружки как его вершины. Удалить из дальнейшего анализа все белые кружки, лежащие вне этого многоугольника (сохраняя белые кружки, лежащие на границе многоугольника). 7. Построить многоугольник из оставшихся черных и белых кружков-вершин. 8.
Удалить все черные кружки, которые стали вогнутыми. 9. Повторять шаги 7 и 8 до тех пор, пока не прекратятся изменения выпуклости вершин. После этого удалить все вершины с величиной угла 180~. Оставшиеся вершины образуют ломаную минимальной длины МРР. Некотпорые М-функции, используемые в алгоритпме МРР Функция с(саесошр, рассмотренная в З 10.4.2, используется на первом шаге при построении клеточного комплекса, покрывающего гранину. Как обычно, мы рассматриваем область В, которая составлена из 1-иц и фоновых 0-ей.
Мы воспользуемся следующей формой вызова функции <~сйесошр: Ц = Цспесошр(В, СЬгевЬо14, (ш1пбйш шах41ш)), где Ц вЂ” это разреженная матрица, содержащая структуру квадродерева. Если ЦОг, ш) не равно нулю, то (Ь, ш) является верхним левым углом блока разложения и размер блока равен Ц(Ь, ш). Блок разделяется, если максимальное значение элементов блока минус их минимальное значение больше, чем ьЬтевЬо14.
Величина этого параметра заключена межпу 0 и 1 независимо от класса входного изображения. При указанном синтаксисе функция цсдесошр не производит блоки с размерами меньше, чем ш1п41ш и больше, чем шах41ш. Блоки, размеры которых превосходят шах41ш разделяются, даже если они не удовлетворяют пороговому условию. Частное шах41ш/ш1п41ш должно быть степенью числа 2, Если в аргументе функции Цсдесошр в конце присутствует лишь одна величина (без квадратных скобок), то она считается равной шах41ш. В таком виде ».д. !У д * ддддд1 эта функция используется в данном параграфе. Изображение В должно иметь размеры КхК, так что частное К)ш1п41ш является степенью числа 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
