Об одном способе векторного и аналитического представления контура изображения
А.Н. Каркищенко, А.Е. Лепский, А.В. Безуглов
Предварительная обработка оцифрованного изображения объекта включает выделение, сглаживание и векторизацию контура. Под векторизацией будем понимать процесс сопоставления контуру последовательности конечномерных векторов, характеризующих изображение объекта. Все способы векторизации можно разделить на векторизацию по контрольным точкам и пошаговую векторизацию. К последним относится широкий класс методов, использующих так называемое преобразование Хау (см. [1], [2]). В качестве контрольных точек могут быть угловые точки [3], точки экстремума функции кривизны [4], точки перегиба и др.
В статье рассмотрен простой алгоритм выделения контрольных точек и построения инвариантного векторного представления изображения объекта. Кроме того, предложен способ функционализации векторного представления изображения. Результатом функционализации является некоторая функция изображения, по которой частично или полностью может быть восстановлено векторное представление. В ряде задач, например, при распознавании симметрий, анализ функции изображения позволяет получить дополнительную информацию об изображении. Обсуждаются вопросы устойчивости функции изображения к изменению центра масс векторного представления, к появлению новой контрольной точки и т.д.
Рассмотрим дискретное бинарное изображение на фоне . Считаем, что , где - контур изображения, - внутренность изображения , - может, в частности, содержать другие контуры. Кроме того, считаем, что изображение является сглаженным и не содержит висячих точек. Введем матрицу Будем рассматривать следующие параметры: , 0, - начальный порог отбора контрольных точек; , >0 - изменение порога отбора контрольных точек; , >0 - размер окрестности контрольной точки. Нам потребуется вычислять расстояние между элементами, задающими изображение и фон, т.е. необходимо ввести некоторую метрику на дискретной плоскости. В качестве метрики можно использовать , , и др. Алгоритм, позволяющий проследить контур изображения и сформировать массив контрольных точек, состоит из следующих шагов.
Просматриваем элементы матрицы слева - направо, сверху - вниз и находим первый элемент . Полагаем ,
. Здесь - номер отслеживаемой точки контура; - точка начала обхода вокруг последней отслеживаемой точки контура с целью отслеживания текущей точки.
Рассмотрим -окрестность точки . Подсчитаем количество точек , принадлежащих фону и не принадлежащих ему: , , где - мощность (количество точек) окрестности .
Вычисляем вес -й точки: .
Если , то - контрольная точка. В этом случае добавляем в вектор , - в вектор , - в вектор .
Продолжаем обход контура. Пусть - элементы матрицы , расположенные вокруг элемента по часовой стрелке, причем . Осуществляем поиск первого ненулевого матричного элемента из окружающих его элементов . Если такой элемент, то полагаем и .
Если , то обход контура изображения окончен и переходим к пункту 80., в противном случае - к пункту 30.
Пусть - длина вектора (число контрольных точек). Если (т.е. число контрольных точек невелико), то и переходим к пункту 10 (осуществляем новый обход контура). Если , то массив контрольных точек построен.
Данный алгоритм был реализован и апробирован в системе Borland Delphi.
На рис. 1 и 2 представлены результаты векторизации бинарного изображения. Результаты работы программы сведены в таблицу 1.
Очевидно, что в контрольных точках граница изображения претерпевает наиболее существенные изломы. Поэтому многоугольник , полученный путем последовательного соединения контрольных точек отрезками прямых линий, является аппроксимацией исходного изображения. При этом чем больше число контрольных точек, тем точнее аппроксимация. В качестве оценки относительной погрешности такого представления изображения можно использовать величину ,
где - символ симметрической разности множеств.
Рис. 1 Рис. 2
Табл. 1
