18.2. СЖАТИЕ, УТОНЧЕНИЕ И ПОСТРОЕНИЕ ОСТОВА

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

На рис. 18.2.1 приведены примеры, иллюстрирующие обработку объекта прямоугольной формы и области неправильной формы простым алгоритмом сжатия. С помощью этого алгоритма граничные точки, не являющиеся точками дуги (отмеченные на рисунке знаком ), удаляются из области, если удаление элемента не ведет к нарушению связности области согласно определению восьмисвязности. Точки дуги удаляются лишь в том случае, если они являются концевыми точками дуги и их удаление не приводит к исчезновению области. Алгоритм заканчивает свою работу, когда остается единственный элемент.

Работа простого алгоритма утончения иллюстрируется на рис. 18.2.2, а на примере утончения объекта прямоугольной формы. На первом шаге первого этапа работы алгоритма граничные элементы с левой стороны объекта, обозначенные буквой , удаляются, если они не являются точками дуги и их удаление не ведет к нарушению восьмисвязности. На втором шаге удаляются граничные элементы с правой стороны объекта, обозначенные буквой  если соблюдаются такие же условия, как и для левых граничных точек.

Рис. 18.2.1. Примеры работы алгоритма сжатия: а - сжатие объекта прямоугольной формы; б - сжатие области.

Рис. 18.2.2. Примеры работы алгоритма утончения: а - утончение прямоугольника; б - утончение вертикально ориентированной области; в - утончение горизонтально ориентированной области.

Рис. 18.2.3. Примеры преобразований к срединным осям: а - круг; б - прямоугольник.

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

Розенфельд [1, 2, стр. 82] и Престон [5] разработали и проанализировали несколько последовательных алгоритмов сжатия и утончения. К настоящему времени разработаны также алгоритмы для нескольких машин параллельной обработки [6-9].

Чтобы выразить структурные соотношения сложных объектов в сцене, часто оказывается достаточным представление объектов в виде остова, или каркаса. Ясно, что остов большинства объектов, как правило, можно представить значительно эффективнее, чем сам объект. Один из подходов к получению остова заключается в утончении объекта до тех пор, пока не будет получена цепочка элементов с минимальной связностью. Недостаток этого подхода состоит в том, что остов определяется неоднозначно; форма получающейся в результате фигуры обычно сильно зависит от алгоритма утончения.

Блюм [10] предложил остроумный способ получения остова, названный преобразованием к срединным осям, который для каждого заданного объекта дает ознозначный результат. Интуитивное определение такого преобразования основывается на аналогии со «степным пожаром» [11-13]. Рассмотрим изображенные на рис. 18.2.3 области круглой и прямоугольной формы и представим себе, что это участки земли, покрытые высохшей травой. Если бы огонь возник одновременно по всему периметру участков, то он распространялся бы к их центрам до тех пор, пока не сгорела бы вся трава. В случае круглой области огонь распространялся бы к центру круга, который представляет собой точку самогашения огня. Для прямоугольной области огонь распространялся бы с каждой стороны. По мере продвижения огня слева и сверху линии огня будут встречаться и пожар будет затухать. Геометрическое место точек самогашения огня образует линию самогашения. Точки или линии самогашения называются срединными осями или остовом фигуры. Вообще срединноосный остов состоит из множества точек, которые находятся на одинаковом расстоянии от двух ближайших к ним точек на границе фигуры. Это расстояние называется расстоянием самогашения фигуры. Границу фигуры можно восстановить по ее срединноосному остову и расстоянию самогашения. Эта граница есть огибающая окружностей с радиусом, равным расстоянию самогашения, с центрами в каждой точке срединноосного остова.

Применение на практике преобразования к срединным осям дискретных объектов, определенных на прямоугольном растре, связано с определенными трудностями. Чтобы обеспечить однозначность преобразования, необходимо надлежащим образом ввести расстояние. Если объект имеет границу сложной формы, его остов также будет сложным. С целью достижения более компактного представления фигуры Монтанари [14, 15] исследовал влияние упрощения остова объекта. Для многих объектов стирание или сглаживание частей остова приводит к получению приблизительной границы объекта, которая не отличается заметно от истинной.