Об одном способе векторного и аналитического представления контура изображения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В В В В В В В В В В В В В В В В В В В 

В В В В В В В В В В В В В В В В В В  Р РёСЃ. 1В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В В  Р РёСЃ. 2

Табл. 1

На рис. 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 г.