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

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

1.Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

На рис. 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. Если к нормированному векторному представлению добавить контрольную точку с весом , то для евклидова расстояния между новым центром тяжести и старым справедлива оценка , где - точки скелета изображения . В частности, если , то .

--> ЧИТАТЬ ПОЛНОСТЬЮ <--