А.Н. Каркищенко, А.Е. Лепский, А.В. Безуглов

1.Введение

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

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

2. Алгоритм прослеживания контура и выявления контрольных точек

Рассмотрим дискретное бинарное изображение  на фоне . Считаем, что , где  - контур изображения,  - внутренность изображения ,  - может, в частности, содержать другие контуры. Кроме того, считаем, что изображение  является сглаженным и не содержит висячих точек. Введем матрицу   Будем рассматривать следующие параметры: , 0, - начальный порог отбора контрольных точек; , >0 - изменение порога отбора контрольных точек; , >0 - размер окрестности контрольной точки. Нам потребуется вычислять расстояние между элементами, задающими изображение и фон, т.е. необходимо ввести некоторую метрику  на дискретной плоскости. В качестве метрики  можно использовать , ,  и др. Алгоритм, позволяющий проследить контур изображения и сформировать массив контрольных точек, состоит из следующих шагов.

 Просматриваем элементы матрицы  слева - направо, сверху - вниз и находим первый элемент . Полагаем ,

. Здесь  - номер отслеживаемой точки контура;  - точка начала обхода вокруг последней отслеживаемой точки контура с целью отслеживания текущей точки.

 Рассмотрим -окрестность точки   . Подсчитаем количество точек , принадлежащих фону  и не принадлежащих ему: , , где  - мощность (количество точек) окрестности .

 Вычисляем вес  -й точки:   .

 Если , то  - контрольная точка. В этом случае добавляем  в вектор ,  - в вектор ,  - в вектор .

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

 Если , то обход контура изображения окончен и переходим к пункту 80., в противном случае - к пункту 30.

 Пусть  - длина вектора  (число контрольных точек). Если  (т.е. число контрольных точек невелико), то  и переходим к пункту 10 (осуществляем новый обход контура). Если , то массив контрольных точек построен.

Данный алгоритм был реализован и апробирован в системе Borland Delphi.

На рис. 1 и 2 представлены результаты векторизации бинарного изображения. Результаты работы программы сведены в таблицу 1.

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

где  - символ симметрической разности множеств.

                   

                   Рис. 1                                            Рис. 2

Табл. 1

	Окрестность	Число контрольных точек	Весовой порог	R
Рисунок 1	Квадрат 5*5	6	0.56	16.55%
Рисунок 2	Квадрат 5*5	14	0.52	1.38%

На рис. 3 приведены графики изменения числа контрольных точек и их прироста в зависимости от выбранного порога h.

Рис. 3.

Прирост точек количественно равен уменьшению числа контрольных точек при увеличениях весового порога. Оптимальное пороговое значение следует выбирать из интервала от (h?, h??), где h? - значение весового порога, соответствующее максимуму прироста числа контрольных точек, h- значение, начиная с которого число контрольных точек равно нулю. Следует отметить, что в литературе имеется указание на то, что оптимальным для распознавания изображений считается получение приблизительно 40 контрольных точек [4].

3. Формирование векторного представления контура

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

центр масс контрольных точек , где , ;

длины радиус-векторов контрольных точек относительно центра масс: , ,  а  также длины нормированных радиус-векторов , где ;

косинусы углов между соседними радиус-векторами контрольных точек: ,  ( считая ,  )

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

Теорема 1. Если к нормированному векторному представлению  добавить контрольную точку с весом , то для евклидова расстояния между новым центром тяжести  и старым  справедлива оценка , где - точки скелета изображения . В частности, если , то .

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

4.Функция изображения

Вместо анализа векторного представления  в ряде задач (одна из которых будет рассмотрена в следующем разделе) удобней изучать свойства некоторой функции, связывающей векторы из представления . Например, рассмотрим функцию ,
где  (). Эту функцию можно рассматривать как обобщение дескриптора Фурье [5]. По функции  коэффициенты  (а, следовательно, и ) будут определяться однозначно, как коэффициенты частичной суммы ряда Фурье. По дискретным значениям этой функции  , коэффициенты  можно найти из линейной системы ,, если значения , , такие, что определитель матрицы  отличен от нуля, где , где - целая часть числа. Множество функций изображения будем рассматривать вместе с нормой . Следующая теорема говорит об устойчивости функции изображения к изменению весов (и, следовательно, к изменению центра масс).

Теорема 2. Пусть  и  два скелета изображения  такие, что . Тогда, если и  соответствующие этим скелетам функции изображения, то , где .

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

5.Распознавание симметрий

Изображение  называется -осесимметричным [6], если оно переводится само в себя после поворота на любой угол, кратный  вокруг своего центра масс. Симметрия является важной в задачах распознавания характеристикой изображаемого объекта. Подробный обзор существующих методов обнаружения симметрий и определения ориентации объекта, в том числе и с помощью дескрипторов Фурье, можно найти в работе [6]. Распознавать симметрию можно непосредственно анализируя векторное представления , если оно достаточно точно отражает характер симметрии (не содержит «лишних» контрольных точек). Векторное представление  назовем  -осесимметричным, если построенный по этому векторному представлению многоугольник будет  -осесимметричным. С другой стороны, для распознавания симметрии можно использовать и функцию изображения . В этом случае лучше перейти к комплексной форме записи функции изображения. Обозначим через , где . Тогда  и справедлива

Теорема 3.  является  -осесимметричным векторным представлением изображения  тогда и только тогда, когда найдется такое , что ,  где.

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

Список литературы

Hecker Y.C., Bolle R.M. On geometric hashing and the generalized Hough transform, IEEE Trans. Syst., Man and Cybern. 24, N9, 1994, p.1328-1338.

Dufresne T.E., Dhawan A.P., Chord-tangent transformation for object recognition, Pattern Recogn. 28, N9, 1995, p.1321-1332.

Bolles R., Cain R.A., Recognizing and locating partiavisible objects: The local-feature-focus method, Robot Vision A.Publ. Ed., 1984.

Liu H.C., Srinath M.D., Partial Shape Classification Using Contour Matching in Distance Transformer; IEEE Trans. Pattern Anal. and Mach. Intell, 12, N11, p.1072-1079.

Zahn C.T., Roskies R.S., Fourier descriptors for plane closed curves, IEEE Trans. Comput. C-21, March, 1972, p.269-281.

Pei S.C., Liov L.G., Automatic symmetry determination and normalization for rotationally symmetric 2D shapes and 3D solid objects, Pattern Recogn, 27, N9, 1994, p.1193-1208. последовательностей".- Таганрог, изд. ТРТУ, 1996 г.