18.4.2. ТОПОЛОГИЧЕСКИЕ ХАРАКТЕРИСТИКИ

Топологические характеристики формы - это свойства, инвариантные по отношению к преобразованию «резинового листа» [11, 26-28]. Такое преобразование или отображение можно представить себе как растяжение резинового листа с нарисованным объектом заданной формы, в результате которого происходит некоторое пространственное искажение фигуры. Преобразования, требующие разрывов резинового листа или соединения одной его части с другой, не допустимы. Ясно, что расстояние не является топологическим свойством, поскольку оно может изменяться при растяжении резинового листа. Такие понятия, как перпендикулярность и параллельность линий, также не являются топологическими свойствами. На рис. 18.4.1, а представлена двоичная фигура, состоящая из двух связных компонент, а на рис. 18.4.1, б изображена та же фигура, подвергнутая растяжению. Понятно, что нет таких операций растяжения, которые смогли бы увеличить или уменьшить связность фигуры. Связные компоненты изображения могут содержать дыры (рис. 18.4.1, в). Количество дыр, очевидно, не изменяется при топологическом отображении. Фундаментальное соотношение между количеством связных компонент  и числом дыр  на фигуре, называемое числом Эйлера, имеет вид

.                                                                     (18.4.4)

Число Эйлера - также топологическое свойство, поскольку  и  - топологические свойства.

Рис. 18.4.1. Примеры топологических свойств: а – объекты, ; б – объекты на резиновом листе, подвергнутом растяжению; в – объекты с дырами, .

Объекты неправильной формы можно описать как совокупность их топологических составляющих. Рассмотрим трубчатый объект, сечение которого напоминает букву R, изображенную на рис. 18.4.2, а, и представим, что на объект натянута резиновая лента. Область, ограниченная резиновой лентой, называется выпуклой оболочкой объекта. Множество точек внутри выпуклой оболочки, не принадлежащих объекту, образует дефицит выпуклости объекта. Имеются два типа дефицита выпуклости: области, полностью ограниченные объектом, которые названы озерами, и области, лежащие между периметром выпуклой оболочки и объектом, которые названы заливами. Для некоторых применений проще описать объект непосредственно с использованием понятий выпуклой оболочки и дефицита выпуклости. Для объектов, представленных на прямолинейных решетках, определение выпуклой оболочки необходимо несколько видоизменить с тем, чтобы оставался прежний смысл. Такие объекты, как окружности и треугольники, на дискретном растре следует рассматривать как выпуклые, даже если их границы имеют ступенчатый вид. Эту кажущуюся трудность можно обойти, рассматривая резиновую ленту, натянутую на дискретизованный объект. Элементы, полностью лежащие внутри объема, ограниченного резиновой лентой, и не принадлежащие объекту, образуют дефицит выпуклости. Скланский и др. [29, 30] разработали практические алгоритмы для вычисления характеристик выпуклости дискретизованных объектов.

Рис. 18.4.2. Средства описания выпуклой формы: а - фигура; б - выпуклая оболочка, заливы и озера.

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

,                                                         (18.4.5)

где  - число совпадений с указанным в скобках эталоном. Если объект полностью окружен белыми элементами, то его периметр равен

.                        (18.4.6)

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

,                                                           (18.4.7а)

,      (18.4.7б)

,       (18.4.7в)

,         (18.4.7г)

,                                                             (18.4.7д)

.                                       (18.4.7е)

Площадь и периметр изображения можно связать с количеством входящих в него двоичных четверок формулами

,          (18.4.8а)

.                                                        (18.4.8б)

Эти формулы могут давать значительную ошибку, если вычисленные по ним значения периметра и площади использовать как оценки этих параметров для непрерывного объекта, который был подвергнут дискретизации. Более точные формулы для таких оценок были получены Дудой [31]:

,                              (18.4.9а)

.                                                   (18.4.9б)

Подсчет двоичных четверок позволяет очень просто определить число Эйлера изображения. Грэй [28] установил, что в соответствии с определением четырехсвязности число Эйлера можно вычислить следующим образом:

,           (18.4.10а)

а для восьмисвязности

.           (18.4.10б)

Если на изображении имеется много связных компонент и мало дыр, то число Эйлера можно принять в качестве оценки числа компонент. Тогда среднюю площадь и средний периметр связных компонент можно выразить как [28]

,                                         (18.4.11а)

.                                         (18.4.11б)

Для изображений, содержащих тонкие объекты, например машинописные или рукописные буквы, приближенные значения средней длины и средней ширины объекта можно вычислить по формулам [28]

,                                          (18.4.12а)

.                                     (18.4.12б)

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