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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

              Рис. 1                                       Рис. 2

Табл. 1

На рис. 3 приведены графики изменения числа контрольных точек и их прироста в зависимости от выбранного порога h.

Рис. 3.

Прирост точек количественно равен уменьшению числа контрольных точек при увеличениях весового порога. Оптимальное пороговое значение следует выбирать из интервала от (h, h), где h - значение весового порога, соответствующее максимуму прироста числа контрольных точек, h- значение, начиная с которого число контрольных точек равно нулю. Следует отметить, что в литературе имеется указание на то, что оптимальным для распознавания изображений считается получение приблизительно 40 контрольных точек [4].