Глава 6 (Учебник в электронном виде), страница 17

Простейшие дифференциальные операторы работают в программном окне размерностью 22, и самый простой из них использует только два элемента окна, кроме анализируемого элемента l_ij.

Норма градиента Г_ij определяется выражением:

или, чтобы избежать операций возведения в степень и извлечения корня и ускорить счет:

Г_ij = l_ij - l_i+1,j + l_ij - l_i,j+1

Вид градиента освещенности зависит от формы границы, или, точнее от вида сопрягаемых поверх­ностей, образующих границу (рис. 6.50). Цифрой 1 обозначена граница, образованная двумя плоскостями, цифрой 2 - выпуклая поверхность, цифрой - 3 сопряжение выпуклой поверхности и плоскости.

Самыми популярными дифференциальными операторами являются операторы Робертса и Собеля.

О ператор Робертса (рис. 6.51) позволяет точнее вычислить норму градиента по сравнению с простым дифферен­ци­альным оператором 22, поскольку использует все элементы программного окна. Имеем:

Г_ij = l_ij - l_i+1,j+1 + l_i+1,j - l_i,j+1

Значение Г_ij можно определить с помощью маски, определя­емой выражением:

(В обоих случаях операторы с модулями разности дают большую погрешность определения нормы градиента, чем исходные формулы).

О ператоры пространственного дифференцирования, работающие в программном окне размерностью 33, позволяют не только определить норму градиента (т.е. величину перепада яркости), но и проследить линию или контур изображения. Данный оператор обеспечивает одновременно фильтрацию и выделение контура и носит название «око­н­туриваю­щего фильтра ».

Оператором Собеля (рис. 6.52) норма градиента Г_ij находится следующим образом:

Г_ij = Гx_ij + Гy_ij,

причем предварительно вычисляются нормы градиента по координатам X и Y кадра:

Гx_ij = (l_i+1,j-1 +2l_i+1,j +l_i+1,j+1) - (l_i-1,j-1 + 2l_i-1,j + l_i-1,j+1),

Гy_ij = (l_i-1,j+1 +2l_i,j+1 +l_i+1,j+1) - (l_i-1,j-1 +2l_i,j-1 + l_i+1,j-1).

Направление контуров и линий оценивается по соотношению значений Гx_ij и Гy_ij.

Используя маски для определения Гx_ij и Гy_ij получим для нормы градиента Г_ij следующее выражение:

После применения данного оператора, на выходе алгоритма образуется массив, каждый элемент которого соответствует величине градиента в данной точке изображения. (На рис. 6.50 и 6.51 для наглядности изображения объекта инвертированы).

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

Вторая производная изображения определяется с помощью преобразования Лапласа. Оператор Лап­ласа _ij является оператором производных второго порядка. Он представляется в виде процедуры:

; или в виде маски

6.6.2. Сегментация

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

А лгоритмы сегментации, как правило, основываются на двух фундаментальных принципах: разрывности и подобия. Наиболее распространено использование первого принципа, в соответствии с которым, производится программный обход контура по установленному закону. На практике, соединение точек контура осуществляется при анализе характеристик пикселей в некоторой окрестности (33, 55) каждой точки (x, у) образа, который уже подвергся процедуре обнаружения контура. Таким образом, процедура сегментации (называемая иногда анализом связности) может реализовываться вслед за выделением контура, и использовать алгоритмы, подобные фильтрующим. В то же время, на практике использование сегментации одновременно с фильтрацией затруднено, особенно для контуров с резкими вырезами. Под анализом связности элементов дискретного изображения понимают поиск ближайших соседей, расстояние между которыми не превышает одного пикселя. Если считать, что каждый пиксель связан только с четырьмя соседними элементами, то говорят о четырехсвязной области, если с восемью, включая диагональные - то восьмисвязной (рис. 6.53а и 6.53б соответственно). Обычно, во избежание неоднозначности, пользуются методом восьмисвязности. Неоднозначен, например, объект представленный на рис. 6.52в. Действительно, при четырехсвязном представлении его можно интерпретировать как четыре отдельных объекта, касающиеся друг друга. При восьмисвязном представлении удается локализовать разрывы в контуре, и тем самым обозначить на изображении отдельные сегменты. Если эти сегменты принадлежат замкнутому контуру, то считается, что обнаруженный контур является контуром объекта. Наиболее простой алгоритм обхода контура представленный на рис. 6.52г пред­полагает перемещение сканирующего окна (33) от точки к точке, в процессе которого производится нумерация точек контура и определя­ется его замкнутость. В результате описанной процедуры все точки замкнутого контура получают привязку к абсолютной системе координат. Подобное представление изображения занимает значительный объем в памяти, т.к. каждая точка характеризуется двумя координатами. Размерность выходного массива оказывается равной раз­мерности массива исходного изображения. (При размерности простейшего бинарного изображения 256256 этот массив занимает 4К 16-ти разрядных слов).

Для более компактного представления данных в СТЗ часто используется кодирование изображений.

6.6.3. Кодирование изображений

Под кодированием изображения понимается обычно обратимое преобразование информации, позволя­ющее по­лучить компактный («сжатый») мас­сив чисел, однозначно описывающий это изображение в удобной для данной вычислительной структуры форме.

В СТЗ различают три типа кодирования:

• кодирование собственно изображения с помощью кодов длин серий (КДС);

• кодирование контура кодами Фримана;

• частотное кодирование с использованием Фурье-преобразований.

Процедура кодирования изображений в СТЗ обычно представляет собой упаковку контура. Она реализуется одновременно с обходом контура и заключается в присвоении каждой его точке некоторого значения.

В общем случае, эффективность того или иного метода упаковки можно оценить с помощью коэффициента сжатия информации С_к:

С_к = V_и/V_к,

где V_и - объем исходного массива изображения; V_к - объем памяти, необходимый для записи закодированного изображения.

Для увеличения коэффициента сжатия изображение преобразуется из пространства абсолютных координат в некоторое пространство относительных (обобщенных) координат.

С ущность кодирования методом длин серий (известного в компьютерной обработки изображений как метод RLE) заключается в представлении изображений од­нородными отрезками строки развертки, где уро­вни яркости (или цвет элементов) одинаковы. При этом каждая серия характеризуется уровнем яркости и длиной (числом пикселей). Исследования, проведенные для бинарных изображений, показали, что использование КДС обеспечивает сжатие информации в 4 ... 7 раз. Приведем при­мер записи в КДС, объекта представленного на рис. 6.54а: 4,7,6; 3,6,1; 9,6,1; 3,5,1; 10,5,1; 3,4,2; 11,4,1; 4,3,1; 10,2,1; 5,2,6.

КДС наиболее удобны для упаковки «не­изрезан­ных» изображений (т.е. изображений с гладким контуром).

Весьма распространенным методом кодирования непосредственно контуров изображения является использование цепных кодов Фримана (рис. 6.54б). При кодировании по Фриману, контур, начиная с некоторой точки, задается последовательностью векторов, принимающих дискретные значения с углом наклона модуля кратного 45⁰. Значение модуля равно 2, если угол наклона вектора составляет 45⁰ и 1, при вертикальном или горизонтальном его положении. Изменение направления векторов при переходе от одной точки кривой к другой отражает характер изменения моделируемой кривой.

(Цепной код для той же фигуры имеет вид: 0, 0, 0, 0, 0, 6, 7,7, 5, 6, 4, 4, 4, 4, 4, 3, 2, 4, 2, 2, 1)

Запись в цепных кодах эффективна для контурных изображений с «изрезанной» линией.

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

6.6.4. Описание изображений

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

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

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

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

При вычислении признаков, рассматриваются изображения объектов, контуры которых уже выделены. Практически всегда используются инвариантные к повороту и трансляции признаки - площадь $ и периметр изображения P, а также, зависящий от них коэффициент формы K_ф или пераунд, равный: K_ф = $/P².

Полярные моменты изображения определяются формулами: