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

Изображение называется -осесимметричным [6], если оно переводится само в себя после поворота на любой угол, кратный вокруг своего

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

Информация

Компьютеры, программирование

Другие материалы по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией

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

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

1.Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1 Рис. 2

Табл. 1

ОкрестностьЧисло контрольных точекВесовой порогRРисунок 1Квадрат 5*560.5616.55%Рисунок 2Квадрат 5*5140.521.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 determinat

Похожие работы

1 2 >