МИРЭА / Методичка_2010 / Методичка_2010

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

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

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

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

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

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

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

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

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

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

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

Присвоение признака оставление истинного значения.
While признак оставление имеет истинное значение do шаги 3—12. Begin
Присвоение признаку оставление ложного значения. {Никакие изменения не производились.}
For j=0, 2, 4 и 6 do шаги 5—12. Begin
For всех пикселей р изображения I do шаги 6—10. Begin
If значение р равно I and if значение его j-соседа равно 0 then do шаги 7—10. Begin
Присвоение признаку ост ложного значения.
For всех конфигураций окрестностей, входящих в Р do шаг 9.
If конфигурация окрестности пикселя р соответствует одной из конфигураций Р, then присвоение признаку ост истинного значения и выход из цикла. End.
If признак ост имеет истинное значение, then присвоение пикселю р значения 2 {остовный пиксель}, else присвоение пикселю р значения 3 {удаляемый пиксель} и, кроме того, присвоение признаку оставление истинного значения. End. End.
For всех пикселей р изображения I do шаг 12.
If значение пикселя р равно 3, then присвоение пикселю р значения 0. End.

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

Содержание