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

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

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 г.


еще рефераты
Еще работы по информатике