Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

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

ИФ РИНЦ = 0,940

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Хачумов М.В. 1, 2

---

1 Федеральный исследовательский центр «Информатика и управление» Российской академии наук (ФИЦ ИУ РАН)

2 Российский университет дружбы народов (РУДН)

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

Статья в формате PDF

0 KB

ригидный объект

контур

цепной код

сжатие

линии положения

инвариантные моменты

1. Hameed V.A. Determination of the Appropriate Geometric Moment Invariant Functions for Object Recognition. Indian Journal of Science and Technology. 2016. Vol. 21. no. 9. P. 1–6. DOI: 10.17485/ijst/2016/v9i21/95209.

2. Freeman H. On the encoding of arbitrary geometric configurations. Electronic Computers, IRE Transactions. 1961. Vol. EC-10. no. 2. P. 260–268.

3. Бутаков Е.А., Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ. М.: Радио и связь, 1987. 240 с.

4. Клестов Р.А., Столбов В.Ю. Гибридный метод распознавания контуров на изображении на основе технологий компьютерного зрения // 27 Международная конференция GraphiCon (г. Пермь, 24?28 сентября 2017 г.). Пермь: Пермский государственный национальный исследовательский университет, 2017. С. 208–211.

5. Виноградов А.А. Инструменты описания контуров в задачах распознавания изображений // Вестник ПНИПУ. Электротехника, информационные технологии, системы управления. 2015. № 13. C. 34–39.

6. Kabir S., Azad T., Alam A. Freeman Chain Code with Digits of Unequal Cost. Eighth International Conference on Software, Knowledge, Information Management and Applications. 2014. P. 1–6. DOI: 10.1109/SKIMA.2014.7083531.

7. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM PC. М.: Унитех, 1992. 320 с.

8. Klein S.T., Shapira D. Huffman Coding with Non-Sorted Frequencies. Mathematics in Computer Science. 2011. no. 5. P. 171–178.

9. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. 3-е изд. М.: Вильямс, 2019. 1328 с.

10. Трушков В.В., Хачумов В.М. Определение ориентации объектов в трехмерном пространстве // Автометрия. 2008. № 3. С. 75–79.

11. Arafah M., Moghli Q.A. Efficient Image Recognition Technique Using Invariant Moments and Principle Component Analysis. Journal of Data Analysis and Information Processing. 2017. Vol. 5. P. 1–10. DOI: 10.4236/jdaip.2017.51001.

12. Нгуен З.Т. Инварианты в задачах распознавания графических образов // Вестник Российского университета дружбы народов. Серия: Математика, Информатика, Физика. 2016. № 1. С. 76–85.

13. Хачумов М.В. Нгуен З.Т. Задача распознавания лиц по фотографиям на основе инвариантных моментов // Современные проблемы науки и образования. 2015. № 2–2. [Электронный ресурс]. URL: http://www.science-education.ru/ru/article/view?id=23235 (дата обращения: 22.06.2020).

Ригидные объекты являются наиболее распространенными в задачах распознавания образов, в частности при поиске данных дистанционного зондирования Земли (ДЗЗ), печатных символов или анализе других устойчивых геометрических фигур. Фундаментальное свойство объектов не менять своей формы при выполнении поворотов и изменении масштаба позволяет упростить задачу их распознавания. Наиболее информативными устойчивыми признаками ригидных объектов являются их контуры, которые фактически служат инвариантами по отношению ко многим преобразованиям [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-мк) и Программы фундаментальных исследований Президиума РАН «Перспективные физико-химические технологии специального назначения» (проект «Разработка и исследование методов и технологии высокопроизводительного сжатия целевой информации, передаваемой по каналам космической связи в интересах национальной безопасности Российской Федерации»).

Библиографическая ссылка