Глава 9. АЛГОРИТМЫ ПРОРЕЖИВАНИЯ

9.1. ВВЕДЕНИЕ

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

Рис. 9.1. Пример, иллюстрирующий необходимость использования алгоритмов прореживания

Штриховой рисунок или текст должны быть подвергнуты квантованию с достаточно высоким разрешением с тем, чтобы можно было гарантировать отсутствие разрывов линий и сохранение концов последовательностей (см. гл. 7). Использование такого разрешения приводит к появлению в других частях изображения участков шириной более двух пикселов. Чтобы сохранить линейчатую структуру, свойственную исходному изображению, не нарушая его связности, необходимо использовать процедуру прореживания. В разд. 7.6 и 7.7 мы уже обсуждали, каким образом можно определить понятие «тонкость» на дискретной сетке. Этот анализ будет использован нами в качестве основы для определения алгоритмов прореживания.

На непрерывной плоскости тонкость можно математически строго определить следующим образом.

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

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

Рис. 9.2. Примеры остовов: а — линейчатая структура силуэта точно соответствует структуре серединной оси; б — между структурой объекта и ребрами остова явного соответствия не имеется; в — наличие небольшого шумового воздействия приводит к резкому изменению формы остова

На рис. 9.2 приведено несколько примеров остовов, которые иллюстрируют и некоторые их основные свойства. Можно убедиться в том, что остовы чрезвычайно чувствительны к шуму, поскольку любое малое возмущение границы не только приводит к возмущению одного из ребер, но, кроме того, порождает новые ребра. Итак, имеет место следующий результат.

Утверждение 9.1. Если Р — центр кривизны границы В плоского множества в той точке границы, где ее кривизна имеет изолированный максимум, то соответствующий остов содержит ребро, оканчивающееся в точке Р.

Доказательство. Наличие изолированного максимума кривизны означает, что радиус некоторой окружности, соприкасающейся с границей в этой точке меньше, чем окружности, соприкасающейся с границей в соседних точках. Более того, по определению касания кривых, данная окружность имеет более одной общей точки с кривой и, следовательно, ее центр входит в остов. Всякая окружность с большим радиусом будет иметь соприкосновение в двух точках, расположенных в окрестности точки М, и, следовательно, ее центр входит в остов, но будет отстоять от точки Р.

Анализ рис. 9.2 позволяет прийти еще к одному выводу: если исходный объект является тонким (узким), то остов содержит

щественную информацию о его форме. Как показывает рис. 9.2, б, в случае толстых (широких) объектов это не так.

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

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

Читатель, которого раздражает «кругообразность» этого определения, может вместо «остовный» поставить «кратный». Проверка пиксела на кратность требует изучения лишь его непосредственной окрестности, и, следовательно, преобразования, предусмотренные определением 9.2, могут быть реализованы с помощью локальных операций (см. подразд. 7.6.2). Существенным является допущение о том, что для каждого множества можно установить, какие пикселы принадлежат остову, и соответственно оставить их, а какие явно не принадлежат ему, и их соответственно можно исключить из дальнейшего рассмотрения. Напомним также, что это может быть определено без использования какой-либо заранее известной информации о принадлежности или непринадлежности пиксела контуру, поскольку все такие пикселы должны располагать н-соседом с нулевым значением метки.