1.3. ВТОРИЧНОЕ ОПИСАНИЕ ИЗОБРАЖЕНИЙ

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

Полный обзор вторичных способов представления изображений содержится в [50]. В соответствии с этой работой разделим множество вторичных кодов на три класса: позиционные, структурные и комбинированные. Характерным отличием позиционных кодов является то, что вся плоскость изображения разбивается на квадраты, как это сделано в матричном коде. В качестве элемента изображения рассматривается некоторая характеристика одного или нескольких соседних квадратов. Взаимное расположение элементов определяется взаимным расположением квадратов На плоскости. Различные позиционные способы кодирования отличаются друг от друга способом объединения квадратов в отдельные элементы изображения.

При структурном описании элементы изображения выделяются не обязательно по критерию их территориальной близости, а

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

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

Представление изображений в виде экспоненциальной пирамиды. Пирамидальная структура данных имеет целью сократить время обработки изображения. Принцип описания изображения поясняется рис. 1.3.

Рис. 1.3. Представление изображений в виде пирамиды

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

Емкость памяти V, требуемая для хранения пирамиды, несколько превосходит емкость памяти требуемую для хранения исходного естественного представления: Это увеличение емкости окупается ускорением процессов обработки. Ускорение обработки достигается за счет того, что вначале обрабатываются более высокие уровни пирамиды, имеющие относительно небольшие размеры. Результаты такой «грубой» обработки используют для выделения участков рецепторного представления, заслуживающих более детального рассмотрения. Такие алгоритмы пригодны, например, для выделения отдельных объектов изображения, их контуров, анализа текстуры. На основе пирамидальной структуры данных ее авторы предложили структуру процессоров для обработки изображений, названную конусом обработки.

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

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

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

Дерево квадрантов можно построить как для двухградационных, так и для полутоновых изображений. Приведем описание такого представления на примере двухградационных изображений, т. е. таких изображений, для которых . Дерево квадрантов можно получить разделением массива на квадранты с последующим разделением каждого квадранта на подквадранты до тех пор, пока не получим поля изображения, все элементы которых имеют одинаковые значения (в данном случае 0 или 1). Изображение представляется деревом с полустепенью исхода, равной четырем. Каждая вершина соответствует определенному квадранту поля, сопоставленного вершине предыдущего яруса. Листья дерева соответствуют полям, имеющим одинаковую яркость. Пример построения дерева квадрантов приведен на рис. 1.4. Листья дерева отмечены символами соответствующих полей и обозначены

Рис. 1.4. Представление изображений в виде дерева квадрантов: а — двухградациоииое изображение в поэлементной форме; б — разбиение изображения на поля; в — дерево квадрантов

черными квадратами, если поле состоит из единичных элементов, и белыми, если из нулевых.

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

Структурное представление изображений.

Структурное описание изображений сводится к представлению формы составляющих его объектов и описанию отношений между ними.

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

Оригинальный метод кодирования граничных точек был предложен X. Фрименом [57]. Метод получил название цепного кодирования. Суть его поясняется рис. 1.5. Соседние точки соединяются между собой прямолинейными отрезками, имеющими горизонтальное, вертикальное или диагональное направление. Способ кодирования отрезка в зависимости от направления движения к соседней точке определяется рис. 1.5, а. Кривая представляется начальной точкой и последовательностью восьмеричных цифр.

Рис. 1.5. Цепное кодирование контуров фнгур: а — коды направлений движения по контуру; б — пример кодирования контура

Например, контур, изображенный на рис. 1.5, б, может быть представлен цепным кодом: начальная точка описание кривой . Код удобен тем, что допускает довольно простые процедуры вычисления метрических характеристик фигуры (площади, высоты, длины) и ее преобразования (поворота или перемещения на плоскости)

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

Приведенные выше способы представления кривой могут применяться не только для описания множества граничных точек, но и для кодирования осевых скелетов, получаемых в результате процедуры утоньшения (см. гл. 3). В некоторых случаях осевой скелет позволяет однозначно восстановить форму объекта или содержит достаточно полную информацию, необходимую для целей классификации.

В ряде практических применений в структурном представлении изображений описание формы объектов заменяется их параметрическим описанием. При этом наиболее часто используются параметры, описывающие форму и размеры объектов. Для описания размеров объектов используют такие параметры, как площадь 5 и периметр Р. Для объектов, имеющих полые области (отверстия), различают отдельно площадь объекта, ограниченную его внешним контуром, без отверстий, и суммарную площадь отверстий: Аналогично различают периметр внешнего контура и контура, ограничивающего внутренние области. Размеры объекта и его форму характеризует также максимальная длина L (диаметр Мартина) — максимальное расстояние между параллельными касательными к его внешним границам. Также определяется ширина Н — наименьшее расстояние между параллельными касательными к внешним границам, не пересекающими изображение самого объекта. Для описания формы определяют вторичные характеристики как функции от измеренных первичных. К их числу можно отнести еледующие параметры [15]: — эксцентриситет; — мера круглости; — мера вытянутости; — средняя длина хорды; — пористость.

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

с описываемым объектом выбирают так, чтобы минимизировать функцию близости. Некоторые алгоритмы кусочно-линейной и параметрической аппроксимации контуров приведены в § 1.5.

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

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

В качестве перспективного направления в области представления визуальной информации рассматривают использование для этих целей формальных языков. Пример достаточно простого языка описания стандартизированных символов будет рассмотрен в гл. 3.

Комбинированное представление.

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