Алгоритмы утончения дискретного бинарного изображения

Материал из Техническое зрение
Версия от 21:49, 20 февраля 2020; JIoku (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Рассмотрим проблемы, связанные с переносом идей скелетизации на дискретные изображения.

Содержание

Алгоритмы утончения и остовы

Алгоритмы приблизительной скелетизации бинарных изображений часто называют алгоритмами $\textit{утончения}$, а дискретные скелеты назвают также $\textit{остовами}$.

Как уже было отмечено выше, на непрерывной плоскости скелет можно математически строго определить следующим образом. Пусть $R$ - множество точек плоскости, $B$ - его граница и $P$ - точка множества $R$. Ближайшим соседом точки $P$ на границе $B$ является такая точка $M$, принадлежащая границе $B$, что на этой границе нет никакой другой точки, расстояние от которой до точки было бы меньше расстояния $PM$. Если точка $P$ имеет более одного ближайшего соседа, то $P$ называют $\textit{остовной }$точкой множества $R$. Объединение всех остовных точек называется $\textit{остовом}$, или $\textit{серединной осью}$ множества $R$. Из этого следует, что остовные точки являются центрами окружностей, полностью покрываемых множеством $R$, причем не существует окружностей с тем же центром и большим радиусом, покрываемых множеством $R$. Можно убедиться в том, что остовы чрезвычайно чувствительны к шуму, поскольку любое малое возмущение границы не только приводит к возмущению одного из ребер, но, кроме того, порождает новые ребра. Таким образом, если $P$ - центр кривизны границы $B$ плоского множества $R$ в той точке границы, где ее кривизна имеет изолированный максимум, то соответствующий остов содержит ребро, оканчивающееся в точке $P$. Если исходный объект является тонким (узким), то остов содержит существенную информацию о его форме. В случае толстых (широких) объектов это не так.

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

Остов

Примем следующее определение. $\textit{Остовом}$ множества пикселов $R$ называется множество, формируемое следующим образом. Сначала определяются пикселы остова и пикселы контура, принадлежащие множеству $R$. После этого все пикселы контура, не являющиеся остовными, удаляются и полученное в результате этой процедуры множество заменяет множество $R$. Этот процесс повторяется до тех пор, пока не будет сформировано множество, включающее только остовные пикселы.

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

Такое затруднение можно преодолеть, осматривая пикселы параллельно и обобщая определение посредством добавления в него условия, согласно которому пиксел, отнесенный к категории остовных в процессе одной из итераций, не может быть после этого исключен из рассмотрения. Так, если $Q$ - горизонтально расположенный массив пикселов, то удаление из его середины одного из пикселов приводит к нарушению условия связности. Следовательно, удаляться будут лишь два концевых пиксела массива, а остальные будут считаться элементами окончательного решения. Остается, однако, одна трудность: если массив состоит из пар соседних пикселов, то ни один из них не является определяющим с точки зрения связности, и поэтому все они будут удалены.

Последнее препятствие можно преодолеть, используя сочетание параллельной и последовательной обработок. Одновременной проверке подвергаются не все пикселы контура, а только те, $N$-соседи которых имеют нулевую метку, где $N$ принимает последовательно значения $0$, $2$, $4$ и $6$. Тогда массив, толщина которого равна двум пикселам, будет в первую очередь посредством утончения превращен в массив толщиной в один пиксел, и, таким образом, часть пикселов этого массива будет сохранена. При использовании алгоритмов такого типа разметку остовных пикселов необходимо выполнять специальным образом с тем, чтобы предотвратить их удаление при какой-либо из очередных итераций вследствие их некритичности с точки зрения связности. Этот метод реализован в нижеизложенном алгоритме. Он предназначен для работы с двухуровневым изображением, пикселы которого могут быть снабжены метками $0$ или $1$. Пикселы, составляющие изображения, могут в процессе утончения получать также метки $2$ или $3$, так что при изучении конфигураций окрестностей такие значения меток следует считать индикатором наличия пиксела.

Алгоритм прореживания

Рассмотрим следующий классический алгоритм прореживания. Пусть $I$ - изображение, подаваемое на вход алгоритма, $P$ - множество конфигураций окрестностей остовных пикселов, полученных в результате поворота первой конфигурации (рис. 33) на 90° и трех последовательных поворотов второй на 90°. Истинное значение признака $\textit{оставление}$ используется для обозначения того, что пикселы, не принадлежащие остову, могут быть оставлены. Признак $\textit{ост}$ принимает истинное значение в случаях, когда окрестность пиксела соответствует одной из конфигураций окрестностей, входящих в множество $P$. Единица в описании конфигурации соответствует пикселу окрестности, имеющему ненулевое значение.

6-1-33.jpg

Рис. 33 Конфигурации соседних пикселов при прореживании


Алгоритм имеет следующий вид.

1. Присвоение признака $\textit{оставление}$ истинного значения.

2. $\textbf{While}$ признак $\textit{оставление}$ имеет истинное значение do шаги 3-12.

$\hspace{0.4cm}\textbf{Begin}$

$\hspace{0.6cm}$3. Присвоение признаку $\textit{оставление}$ ложного значения.

$\hspace{1cm}$ {Никакие изменения не производились.}

$\hspace{0.6cm}4. \textbf{For}$ j$\textit{=}$0, 2, 4 и 6$\textbf{ do}$ шаги 5-12.

$\hspace{1.0cm}\textbf{Begin}$

5. $\textbf{For}$ всех пикселов $p$ изображения I$\textbf{ do}$ шаги 6-10.

$\hspace{0.35cm}\textbf{Begin}$

$\hspace{1cm}$6. $\textbf{If}$ значение $p$ равно I$\textbf{ and if}$ значение его j-соседа равно 0 $\textbf{then do}$

$\hspace{1.35cm}$шаги 7-10.

$\hspace{1.35cm}\textbf{Begin}$

$\hspace{1.6cm}$7. Присвоение признаку $\textit{ост}$ ложного значения.

$\hspace{1.6cm}$8. $\textbf{For}$ всех конфигураций окрестностей, входящих в $P\textbf{ do}$ шаг 9.

$\hspace{1.6cm}$9. If конфигурация окрестности пиксела $p$ соответствует одной из

$\hspace{2.0cm}$конфигураций $P$, $\textbf{then}$ присвоение признаку $\textit{ост}$ истинного значения

$\hspace{2.0cm}$и выход из цикла.

$\hspace{2.0cm}\textbf{End.}$

$\hspace{1cm}$10. If признак $\textit{ост}$ имеет истинное значение, $\textbf{then}$ присвоение пикселу $p$

$\hspace{1.5cm}$значения 2 {остовный пиксел},$\textbf{ else}$ присвоение пикселу $p$ значения 3

$\hspace{1.5cm}${удаляемый пиксел} и, кроме того, присвоение признаку $\textit{оставление}$

$\hspace{1.5cm}$истинного значения.

$\hspace{1.5cm}\textbf{End}.$

$\hspace{1.1cm}\textbf{End}.$

11. $\textbf{For}$ всех пикселов $p$ изображения I do шаг 12.

12. If значение пиксела $p$ равно 3,$\textbf{ then}$ присвоение пикселу $p$ значения 0.

$\hspace{0.5cm} \textbf{End}.$

Конец алгоритма.

Полезные ссылки

  1. ☝ К началу
  2. ☜ Математическая морфология (по Ж. Серра)
Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты