Scientific journal

Modern high technologies

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

Ригидные объекты являются наиболее распространенными в задачах распознавания образов, в частности при поиске данных дистанционного зондирования Земли (ДЗЗ), печатных символов или анализе других устойчивых геометрических фигур. Фундаментальное свойство объектов не менять своей формы при выполнении поворотов и изменении масштаба позволяет упростить задачу их распознавания. Наиболее информативными устойчивыми признаками ригидных объектов являются их контуры, которые фактически служат инвариантами по отношению ко многим преобразованиям [1]. Понятие инварианта в математике и в распознавании образов является важнейшим, поскольку непосредственно связано с задачами классификации объектов различной природы. Системы инвариантов позволяют объединять объекты одного класса и, напротив, разделять объекты, принадлежащие разным классам рассматриваемой совокупности. Выделение контуров является одной из важнейших процедур предобработки изображений в задачах распознавания образов.

Наиболее распространенным способом описания контуров служит цепной код Фримена и его модификации [2]. Контур представляется в дискретном поле (решетке) последовательностью отрезков прямых, квантуемых набором из восьми стандартных направлений от 0 до 7 в окрестности 3х3. Длина вектора определяется наклоном и размером ячейки решетки. Для построения кода фиксируется начальная точка отсчета, затем контур обходится в выбранном направлении и описывается последовательностью цифр. С помощью относительно простых численных методов можно проводить масштабирование, повороты или другие преобразования, необходимые для распознавания. Примером использования кода Фримена для распознавания контуров с применением ЭВМ служит работа [3]. Для распознавания контуров можно применять методы сравнения кодов на основе корреляционных функций, линий положения и инвариантных моментов.

Несмотря на относительную простоту, контур сам по себе представляет специфический графический объект, интересный для специального исследования. К возникающим здесь задачам относятся: выделение контуров из фона; получение компактных инвариантных описаний; сжатие путем перехода от растрового к векторному описанию или приведения к коду, удобному для распознавания. Целью настоящей работы является решение некоторых актуальных задач описания контуров ригидных объектов цепными кодами, сжатия, передачи и распознавания контуров ригидных объектов.

Материалы и методы исследования

Рассмотрим способы кодирования направлений и их влияние на процессы описания и сравнение контуров. На рис. 1 представлены две модификации системы кодирования направлений, по Фримену [2; 3]. Рассмотрим особенности систем кодирования применительно к следующим простым примерам, представленным в табл. 1. Примеры содержат исходные и повернутые контуры с обходом по часовой стрелке.

Схемы кодирования, представленные на рис. 1, дают соответственно следующие варианты векторов описаний исходного и повернутого контуров (табл. 2). В рассмотренных случаях сумма всех разностей направлений приводит к нулевому результату, т.к. контур начинается и заканчивается в одной и той же точке.

Кодирование с применением комплексных чисел рассмотрено в работах [4; 5]. Вектор контура представляется комплексным числом Δx + iΔy, где Δx – смещение точки по оси X, а Δy – смещение по оси  Y. Таким образом, контур определяется совокупностью элементарных векторов. Знание размера вектора позволяет восстановить координаты концов. Принцип цепного кодирования представлен на рис. 2. В перечисленных методах кодирование зависит от начальной точки и неустойчиво к зашумлению.

Одной из разновидностей цепного кода является кодирование углами векторов, как это показано на рис. 3 [6]. В табл. 3 представлены примеры построения цепных кодов с применением кодирования углами.

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

Для сравнения и распознавания контуров в условиях возможного смещения начала отсчетов предлагаются три подхода: на основе корреляционных и автокорреляционных функций, линий положения (для разворота и совпадения ориентации векторов) и инвариантных моментов (инвариантных ко всей группе аффинных преобразований).

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

Метод сравнения контуров, описанных комплекснозначными цепными кодами, приведен в работе [4]. Предлагаемый способ сравнения контуров A и B сводится к построению корреляционной функции следующего вида:

где A, B – описания двух контуров; (A, B) – скалярное произведение, A, B – нормы векторов (описаний контуров).  – описание, полученное вычитанием среднего значения из элементов контура. При совпадении контуров имеем максимальное значение γ(A, B) = 1. Однако это возможно только при условии совпадения точек отсчета. Для решения проблемы точки отсчета приходится пользоваться автокорреляционной функцией с параметром циклического сдвига начальной точки. Если A = kB, т.е. векторы контуров, отличаются коэффициентом масштабирования, то . Такой подход приводит к построению автокорреляционной функции. Все необходимые пояснения применительно к комплекснозначным векторам – описаниям контуров, приведены в работе [4].

Рассмотрим возможности сжатия описаний контуров, представленных цепными кодами. Надо отметить, что эти описания являются достаточно экономичными по объему информации. В общем случае каждое направление по Фримену кодируется тремя битами, что делает цепной код интересным для хранения и передачи данных. Тем не менее для передачи и хранения описаний контуров можно применять методы сжатия и оптимизации. В связи с ограниченным количеством различных направлений векторов и двоичных кодов, описания могут быть эффективно сжаты без потерь с применением стандартных алгоритмов LZW и PCX [7].

С другой стороны, для передачи описаний контуров как сообщений могут быть эффективно применены методы кодирования Хаффмана и Фано [8; 9], учитывающие вероятность (частоту) направлений элементарных векторов. Отсутствие этого учета снижает эффективность передачи описания контура как сообщения. В работе [6] определена вероятность (частота) появления двоичных цифр, представляющих углы поворота в описании контуров цепным кодом Фримена.

Таблица 4

Частота встречаемости углов в цепном коде описания контуров

Из таблицы видно, что самая высокая вероятность (0.488) соответствует углам ±450 и является самой низкой (0.003) для отклонений ±1800 от текущей позиции. Знание вероятностей позволяет оценивать и минимизировать информационную емкость кодирования и передачи цепного кода контура как сообщения. Указанные методы используются для сжатия данных без потерь кодами переменной длины, состоящими из целого количества битов. Символам, появляющимся с большей вероятностью, ставятся в соответствие более короткие коды.

Результаты исследования и их обсуждение

Рассмотрим сообщение (90, 0, -45, 45, 0, -90, -90, -135, 180, 180, 135, 90). Общая цена кодирования по Фримену составляет 36 бит. Упорядочим его элементы в соответствии с табл. 4 (-45, -45, 0, 0, 90, -90, -90, 90, -135, 135, 180, 180). Применяя метод Фано, получим следующую систему кодирования углов (табл. 5).

Таблица 5

Кодирование описания контура по Фано

С учетом этого общая цена кодирования без учета знака составит 34 бита. Конечно, эффективность кодирования Фано зависит от вида самого контура. В целом же изменение системы кодирования углов оптимизирует описание, уменьшает общую стоимость хранения/передачи графических объектов в виде контуров.

Если восстановить координаты концов векторов в описании контура, то для нормализации его положения можно применить метод линий положения. Метод подробно описан в работе [10]. Две ортогональные линии положения определяют, находя минимум функционала:

где si – расстояние от точки (xi, yi) с яркостью fi до линии положения объекта, . На рис. 4 показаны примеры построения линий положения для треугольного контура, при fi = 1.

Одна (зеленая) линия является основной. Вторая, вспомогательная линия проходит перпендикулярно главной через центр тяжести контура. Линии положения позволяют вычислить и нормализовать положение контура, т.е. привести его в некоторое стандартное положение. Это позволяет решить проблему начальной точки отсчета и сравнения контуров без перебора.

Рассмотрим возможность применения инвариантных моментов для сжатия и последующего распознавания контуров. Инвариантные моменты для двумерных бинарных и полутоновых изображений описаны в работах [1; 11]. Если восстановить координаты концов векторов, то можно поставить в соответствие контуру алгебраические моменты, инвариантные к аффинным преобразованиям. В табл. 6 приведены результаты кодирования треугольного контура и бинарного изображения буквы.

Видно, что значения инвариантов практически совпадают. Отличия могут быть вызваны при работе с поворотами реальных изображений, которые вносят искажения. Таким образом, каждому контуру вне зависимости от его сложности, поворота и точки отсчета будет поставлен в однозначное соответствие код из семи действительных чисел – по числу уникальных моментов. Этот код можно использовать для распознавания контуров бинарных и полутоновых изображений любым из известных методов.

Представляет отдельный интерес задача построения инвариантных моментов для одномерного случая описания контуров кодами направлений. Пусть имеется описание контура A = (x1, x2,..., xn), где n – размерность вектора. Так как вторая координата отсутствует, то группа центральных моментов определяется в этом случае по сокращенной формуле:

где , т.е. все элементарные отрезки контура одной яркости.

Тогда группа центральных моментов степени p ≤ 3 примет вид:

m0 = n, (свойство контура), , .

Далее выпишем значения моментов:

В этом случае метод инвариантных моментов применим для описаний, полученных изменением точки отсчета. В случае нормализации моментов их значения не зависят и от масштабирования векторов. Примеры практического применения метода инвариантных моментов для распознавания образов содержатся в работах [12; 13].

Заключение

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

Работа выполнена при финансовой поддержке РФФИ (проекты № 20-07-00022-а, № 18-29-03011-мк) и Программы фундаментальных исследований Президиума РАН «Перспективные физико-химические технологии специального назначения» (проект «Разработка и исследование методов и технологии высокопроизводительного сжатия целевой информации, передаваемой по каналам космической связи в интересах национальной безопасности Российской Федерации»).