Смекни!
smekni.com

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

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

1.Введение

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

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

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

Рассмотрим дискретное бинарное изображение

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

Просматриваем элементы матрицы

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

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

Рассмотрим

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

Вычисляем вес

-й точки:
.

Если

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

Продолжаем обход контура. Пусть

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

Если

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

Пусть

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

Данный алгоритм был реализован и апробирован в системе 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.