4.2. СПОСОБЫ КОДИРОВАНИЯ КОНТУРОВ ИЗОБРАЖЕНИЙ

Для дальнейшего рассмотрения методов контурного анализа будем предполагать, что обобщенная структурная схема системы цифровой обработки изображения имеет вид, представленный на рис. 4.1. Все блоки системы общаются через программно-управляемый канал связи. Сформированное датчиком изображение преобразуется в цифровой вид и заносится в одно из цифровых рецепторных полей (ЦРП). В других ЦРП, общее число которых обычно равно 2...10, хранятся изображения, полученные в предшествующие моменты времени. ЦРП представляет собой одну из разновидностей оперативно-запоминающего устройства изображений (ОЗУИ).

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

Рис. 4.1. Структура системы обработки изображений

на основе накопителей на магнитных дисках, магнитной ленте, запоминающих устройств на цилиндрических магнитных доменах и др.

Видеопроцессор (ВП) обрабатывает информацию, поступающую из ЦРП и банка изображений. Промежуточные результаты обработки хранятся в соответствующих ОЗУИ. Среди них необходимо особо отметить ОЗУ для хранения контуров изображений (ОЗУК). Окончательные результаты обработки размещаются в ОЗУ обработанных изображений (ОЗУОИ). Наблюдение изображений, хранящихся в любом из ОЗУИ системы, производится после преобразования в аналоговую форму видеоконтрольным устройством (ВКУ).

ОЗУИ имеет матричную организацию ячеек и содержит строк и столбцов. Обычно N 1X2 равно 256X256 или 512X512, а ячейка является шести- или восьмиразрядной. Адрес каждой ячейки ОЗУИ связан с определенным положением освещенной точки на чувствительном элементе датчика. Чем больше разрядность ячейки и больше формат тем меньше искажено шумами дискретизации и квантования хранящееся в ОЗУИ изображение. Однако выбор значений а также разрядности ячейки ОЗУИ ограничиваются возможностями существующей элементной базы. Кроме того, приводит к быстрому увеличению требуемого количества операций по обработке изображения. Один разряд ОЗУИ будем называть страницей. В каждой такой странице может храниться бинарное по яркости (силуэтное) изображение. На графических иллюстрациях фрагмент страницы будем изображать квадратной сетчаткой,

Рис. 4.2. Силуэтное изображение, заданное на квадратной сетчатке

причем ячейки, в которых хранятся единицы, будут заштрихованными (рис. 4.2).

Рассмотрим некоторые работы по представлению и анализу контуров изображений, заданных на квадратной сетчатке. Наиболее интересные исследования по кодированию контуров и формированию по коду информативных признаков представлены в [17]. Исследования, описанные в ней, направлены на выяснение биологических аспектов процесса распознавания. При этом рассматривается иерархическая система признаков. Первичные признаки отражают геометрические свойства линий: прямая-кривая, выпуклая-вогнутая, плавная-излом.

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

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

Все рассмотренные признаки инвариантны относительно преобразований переноса и поворота.

Оценке степени сложности формы фигуры по ее контуру посвящены работы [91, 93, 99]. Полагается, что основной показатель сложности — количество фрагментов в контуре. Менее важными, но достаточными характеристиками сложности являются коэффициент формы и число углов. Точки нулевой кривизны, удлиненность, найденная по скелету фигуры, — это информативные признаки, определяемые по контуру фигуры. В качестве системы таких признаков принимается совокупность отношений длин и углов наклона прямолинейных отрезков контура [69].

Линии контура обычно кодируются при обходе его по часовой стрелке. С целью введения единой терминологии дадим необходимые определения (рис. 4.3).

Элементарный вектор (ЭB) - вектор, соединяющий центры или узлы соседних контурных ячеек сетчатки, проведенный в направлении обхода [3]; — номер этого ЭВ, отсчитываемый от точки обнаружения контура; количество ЭВ в контуре данного изображения (рис. 4.3, а).

Элементарное направление (ЭН) — аргумент ЭВ. Клетка заполняется, если площадь изображения в ней не менее 50% площади клетки.

На прямоугольной сетчатке возможны восемь различных ЭВ (рис. 4.3, б).

Рассмотрим примеры способов кодирования контуров.

1. Кодирование по трем признакам: длине текущего ЭВ, направлению поворота при переходе к следующему ЭВ и углу между соседними ЭВ [17].

2; Кодирование текущего ЭВ трехразрядным двоичным кодом (числа от 0 до 7) (рис. 4.3, в). Данный код был предложен Фрименом [103] и получил широкое распространение в задачах обработки изображений [21, 43, 68, 97, 104—109].

3. Р — представление контура [77] основано на проведении в области изображений ряда равноотстоящих сечений

Рис. 4.3. К определению элементарных векторов контуров: а) задание контура элементарными векторами; б) виды возможных элементарных векторов на квадратной сетчатке; в) нумерация элементарных векторов по Фримену

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

В то же время Р — представление затрудняет оценку связности соседних контурных точек.

4. Кодирование (рис. 4.4) текущего ЭВ двумя его проекциями на оси координат [3, 101] — двухмерный код. Данное представление, как и кодирование по Фримену, принято в качестве базового для дальнейшего рассмотрения.

5. Полигональное представление контура [77] получается при аппроксимации контура линейными сегментами. Кодирование контуров состоит в фиксации координат концов этих сегментов. Данный способ получил широкое распространение благодаря компактности получаемых описаний. При этом возникает проблема сегментации, сходная с проблемой дискретизации сигналов, и для реальных контуров она обычно связана с потерей информации.

Рис. 4.4. Координаты элементарного вектора контура при двухмерном кодировании

6. Задание точек контура радиус-векторами, приведенными из центра тяжести фигуры. В работе [8] рассмотрены условия, при которых полученный таким образом полярный код инвариантен к группе линейных преобразований изображения. Данный способ кодирования посредством дополнительной статистической обработки позволяет сформировать достаточную статистику для принятия решения о классе изображения по его форме. Следует отметить, что совмещение полюса с центром тяжести изображения носит эвристический характер и вызвано биологическим аспектом восприятия изображения [100]. В этом плане имеются определенные противоречия, например: в работе [102] такая тенденция при исследовании точек фиксации глаза не наблюдалась.

7. Представление линии контура в виде функции комплексного переменного Контур, как непрерывная замкнутая кривая в. комплексной плоскости, задается ее координатой зависящей от текущей длины l [45]. В работе [101] и в ряде других используется инвариантное к группе линейных преобразований аналитическое описание контура угловой функцией. Задание контура в виде зависимости угла касательной от функции текущей длины l инвариантно к переносу, но зависит от поворота и изменения масштаба (рис. 4.5).

Определим кумулятивную функцию как угол между касательными в точках т. е.

Рис. 4.5. Задание линии контура угловыми функциями

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

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

Зададим функцию в виде

Задание контура изображения в виде функции является инвариантным к переносу, повороту и масштабу изображения.

Работы [95, 97, 98, 101] и некоторые другие посвящены вопросам создания на основе коэффициентов Фурье для угловой функции экономного и инвариантного описания контура.

8. Задание ЭВ контура в плоскости квадратной сетчатки (рис. 4.6) комплексными числами [72—74]:

Рис. 4.6. Координаты элементарного вектора при комплекснозначном кодировании

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

В общем случае выражение для элемента кода АГ запишется как

где

С учетом принятых обозначений текущий элемент кода

Фримена запишется как двухмерного а сами коды можно записать следующим образом:

1) код Фримена

2) двухмерный

3) комплекснозначный

Пространство сигналов (кодов) Фримена обозначим через двухмерных кодов комплекснозначных — .