Методы и алгоритмы сравнения форм бинарных растровых изображений на основе скелетизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Кушнир Олеся Александровна

• Кушнир Олеся Александровна
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Кушнир Олеся Александровна

СОДЕРЖАНИЕ Введение

1 Описание формы бинарных растровых изображений на основе скелетизации

1.1 Понятие скелета изображения

1.2. Дискретный подход к скелетизации

1.3. Непрерывный подход к скелетизации

1.4 Проблема неустойчивости скелетного описания

1.4.1 Регуляризация (стрижка) скелета

1.4.2 Аппроксимация

1.4.3 Склейка

1.5 Алгоритмы поиска диаметра минимальной описанной около скелета окружности

1.6 Выводы

2 Автоматическая стабилизация скелетного представления фигур бинарных изображений

2.1 Обзор методов автоматической стабилизации скелетов бинарных изображений

2.1.1 Усечение скелета путём нахождения компромисса между его простотой и ошибкой восстановления

2.1.2 Усечение скелета путём нахождения компромисса между его простотой и ошибкой восстановления c ограничениями

2.2 Стабилизация скелета на основе интервалов стабилизации

2.2.1 Определение интервалов стабилизации скелета по его ключевым характеристикам

2.2.2 Автоматический подбор множества адекватных параметров обработки скелетов

2.2.3 Автоматический подбор единственного параметра каждой из процедур обработки скелетов

2.3 Выводы

3 Построение функции парного сравнения скелетов, заданных цепочками примитивов

3.1 Обзор существующих методов сравнения бинарных растровых изображений

3.2 Постановка задачи исследования

3.3 Описание скелета цепочкой примитивов

3.4 Постановка проблемы учета радиальной функции скелета в задачах сравнения бинарных изображений

3.5 Учет значений радиальной функции в вершинах скелета

3.6 Параметрическое описание радиальной функции скелета бинарного изображения многочленами Лежандра

3.7 Восстановление бинарного изображения по цепочке примитивов с параметрическим описанием радиальной функции многочленами Лежандра

3.8 Парно-сепарабельная критериальная функция для поиска выравнивания двух цепочек примитивов

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

3.10 Выводы

4 Параллельные реализации алгоритма сравнения бинарных изображений на основе описания скелетов цепочками примитивов

4.1 Обоснование необходимости ускорения работы алгоритма сравнения бинарных изображений

4.2 Проблема циклических сдвигов цепочки примитивов в методе сравнения бинарных изображений

4.3 Распараллеливание алгоритма сравнения бинарных изображений на основе описания скелетов цепочками примитивов

4.4 Обоснование выбора технологий параллельного программирования

4.5 Выводы

5 Экспериментальные исследования методов сравнения форм бинарных растровых изображений на основе скелетизации

5.1 Экспериментальные исследования алгоритмов стабилизации скелетов

бинарных изображений

5.1.1 Исследование интервалов стабилизации для параметров регуляризации и аппроксимации

5.1.2 Экспериментальное исследование способа автоматического определения параметров регуляризации и аппроксимации

5.1.3 Выводы по экспериментальным исследованиям методов определения параметров регуляризации и аппроксимации

5.2 Экспериментальные исследования метода сравнения цепочек примитивов без учета радиальной функции скелета

5.2.1 Эксперименты на модельных данных

5.2.2 Описание базы данных листьев растений Flavia и результаты классификации без учета радиальной функции скелета

5.2.3 Выводы по экспериментальным исследованиям метода сравнения форм бинарных изображений без учета радиальной функции скелета

5.3 Экспериментальные исследования метода сравнения цепочек примитивов с учетом радиальной функции скелета

5.3.1 Экспериментальные исследования параметрического описания радиальной функции коэффициентами Лежандра на модельных данных

5.3.2 Экспериментальные исследования на реальных данных функции сравнения с использованием коэффициентов Лежандра

5.3.3 Выводы по экспериментальным исследованиям метода сравнения форм бинарных изображений с учетом радиальной функции скелета

5.4 Экспериментальные исследования выполнения параллельных версий алгоритма сравнения бинарных изображений

5.4.1 Общая характеристика эксперимента

5.4.2 Экспериментальное исследование выполнения параллельного алгоритма с четырьмя потоками

5.4.3 Экспериментальное исследование выполнения параллельного

алгоритма с двумя потоками

5.4.2 Выводы по экспериментальному исследованию работы параллельного алгоритма сравнения цепочек примитивов

Заключение

Список литературы

Приложение А

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы сравнения форм бинарных растровых изображений на основе скелетизации»

ВВЕДЕНИЕ

Актуальность темы исследования. Задачи компьютерного зрения, как правило, состоят из нескольких подзадач. Одной из таких подзадач является сопоставление двух объектов, представленных на изображении, между собой. Для решения применяется множество подходов, и наиболее подходящий из них выбирается, как правило, индивидуально для каждой прикладной задачи согласно имеющейся априорной информации об объектах, входных данных и требуемого результата. Тем не менее, общей идеей большинства подходов является получение некоторого представления (описания) объектов с учётом специфики конкретной задачи и сопоставление не самих объектов, а их представлений. В задачах, где важным дискриминантным признаком объекта является его форма, таким представлением может служить скелет объекта, построенный по его бинаризованному образу [33,48].

Распознавание формы бинарных растровых изображений на основе скелетного описания является важной и актуальной задачей компьютерного зрения, о чем свидетельствуют многочисленные публикации в этой области, и поиск решений этой задачи ведется на протяжении последних десятилетий. Проблема прямого сравнения двух произвольных бинарных растровых изображений на сегодняшний день однозначно не решена, хотя для систем технического зрения, биоидентификации и распознавания актуальна потребность в таком решении. В качестве его практических приложений можно указать сортировку различных объектов на высокопроизводительных конвейерах, идентификацию личности по силуэту ладони, исследование биологических объектов, определение типа цели в многоканальных телевизионных автоматах. Существующие методы сравнения изображений на основе скелетного описания имеют свои достоинства и недостатки. Как правило, предлагаются эмпирические подходы, основанные либо на формировании вектора фиксированных признаков [31], либо существенно опирающиеся на априорные предположения о форме сравниваемых объектов [33]. Тем не менее, под-

ходы к распознаванию бинарных растровых изображений, основанные на порождении признаков, сильно зависят от решаемой прикладной задачи и требуют от исследователя определённой доли фантазии в изобретении всё новых и новых характеристик форм. Наиболее перспективными видятся подходы, основанные на вычислении степени похожести (или различия) пары фигур.

Степень разработанности. Скелет является одним из наиболее удачных способов описания формы фигуры, представленной бинарным растровым изображением [48]. Проблема точного и быстрого построения скелета в значительной мере решена в работах Л.М. Местецкого и его школы [32,33,34,70] и не является задачей данной работы. Недостатком скелетного описания формы является чрезвычайная чувствительность скелета к шумам на границе фигуры. Поэтому, для применения в задачах анализа изображений скелет должен быть предварительно регуляризован и аппроксимирован, т.е. приведен к устойчивому виду. Иначе говоря, в скелете должен быть выделен его базовый подскелет. Методы регуляризации и аппроксимации скелетов хорошо известны (работы Л.М. Местецкого [33], И.А. Рейера [34], Л.Г. Домахиной [6,7], А.А. Рогова и М.Ю. Быстрова [36]), но процедура подбора параметров аппроксимации и регуляризации, необходимых для получения базового скелета класса изображений или одного конкретного изображения, изучена недостаточно. В данной работе предложен способ автоматического подбора параметров аппроксимации и регуляризации.

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

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

Наиболее очевидный подход - описать скелет через систему признаков, релевантных конкретной прикладной задаче, представить каждый скелет как точку в векторном пространстве, и сравнивать такие точки по расстоянию между ними (см., например, работы [42,46]). Этот подход не обладает достаточной универсальностью, поскольку для каждого конкретного класса прикладных задач актуален свой набор признаков.

В зарубежной литературе имеются работы, посвященные сравнению скелетов через вычисление редакционного расстояния для скелетных графов (M. Neuhaus, H. Bunke [71]), построение кернела (функции ядра) на основе кратчайшего пути при обходе графа (F.-X. Dupe, L. Brun [53]), вычисление сходства между формами, основанное на поиске кратчайших расстояний между всеми вершинами скелета (M.F. Demirci [72]) и между терминальными вершинами скелета (X. Bai, L.J. Latecki [45]). В этих работах скелеты интерпретируются преимущественно с точки зрения теории графов, а не как описатели формы с шириной.

В российской литературе (Н.А. Ломов, С.В. Сидякин, Ю.В. Визиль-тер [30]) в качестве дескриптора формы фигуры предлагается использовать скелетно-геодезическую гистограмму толщин-расстояний. Гистограммы парных геодезических расстояний между точками фигуры обладают устой-

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

А.А. Роговым и М.Ю. Быстровым был предложен способ кодирования скелета цепочкой примитивов (состоящих из длины ребра и угла между данным ребром и соседним) и построение функции различия пары скелетов на основе сравнения таких цепочек [36]. Такой способ кодирования скелета никак не учитывает радиальную функцию скелета, являющуюся серьезным дискриминантным признаком при решении большого класса задач. Кроме того, сама функция различия пары скелетов не была детально разработана и протестирована. При этом сама идея кодирования скелета цепочкой примитивов представляется многообещающей, поскольку таким образом можно учитывать топологические особенности скелета, и, следовательно, более точно кодировать форму. Этот подход и положен в основу данного диссертационного исследования.

Цели и задачи. Целью данного исследования является разработка методов и алгоритмов сравнения форм бинарных растровых изображений на основе скелетизации.

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

1 автоматический подбор адекватных параметров аппроксимации и регуляризации скелета с целью получения базового скелета бинарного растрового изображения,

2 описание базового скелета цепочкой примитивов с учетом радиальной функции скелета,

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

4 ускорение сравнения двух изображений посредством технологий распараллеливания.

Научная новизна. В данной работе впервые систематизируются и уточняются сведения о параметрах стабилизации непрерывного скелета: коэффициенте сокращения общего числа ребер (коэффициент регуляризации или «стрижки» скелета), коэффициенте аппроксимации кривизны ветвей скелета и коэффициенте сокращения числа коротких нетерминальных ребер (коэффициент склейки скелета). Предлагается алгоритм вычисления диаметра минимальной описанной вокруг скелета окружности, являющегося масштабным множителем для параметров стабилизации скелета. Проводятся экспериментальные исследования влияния регуляризирующих коэффициентов на топологию скелета, выдвигаются предложения по определению их адекватных значений для выделения в исходном скелете его базового подскелета, предлагается способ автоматического подбора параметров аппроксимации и регуляризации.

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

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

пени различия цепочек на его основе. Разработана и параллельная версия такого алгоритма для ускорения работы при решении реальных задач.

Теоретическая и практическая значимость. Разработаны методы и алгоритмы сравнения форм бинарных растровых изображений на основе ске-летизации. Данное диссертационное исследование существенно расширяет аппарат математической морфологии для исследования свойств бинарных изображений. Результаты работы были использованы при выполнении НИОКТР по гранту РФФИ 14-07-31271 «Методы и алгоритмы беспризнакового анализа скелетных графов бинарных изображений» [35], в котором соискатель являлся руководителем, и по грантам РФФИ 14-07-00527 «Методы комбинирования детекторов в анализе сигналов и изображений», 16-57-52042 «Методы и алгоритмы обнаружения событий, опасных для пожилых людей, на основе видеоанализа в беспроводной системе удаленного мониторинга», 18-07-00942 «Методы и алгоритмы построения математически корректных функций сравнения бинарных изображений на основе скелетной морфологии».

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

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

Методология и методы исследования. При выполнении диссертационного исследования использовались методы математического моделирова-

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

Более конкретно стоит отметить, что при решении задачи описания радиальной функции скелета использовался численный метод аппроксимации функции ортогональными многочленами Лежандра; а для решения задачи сравнения и вычисления степени различия форм фигур был разработан метод, основанный на парном выравнивании цепочек примитивов, моделирующих скелеты. Идея парного выравнивания берет начало в биоинформатике, где применяется для цепочек символов, кодирующих последовательности аминокислот. Оптимальное парное выравнивание вычисляется при помощи численного метода динамического программирования, для которого в данной работе определены оптимизационные критерии сходства цепочек примитивов.

При решении всех задач диссертационного исследования применялись системы имитационного моделирования MathCAD и Wolfram Mathematica. Программный комплекс методов и алгоритмов сравнения форм бинарных растровых изображений реализован на языке программирования высокого уровня C++ в соответствии с принципами объектно-ориентированного программирования и принципом свободной последовательности подпрограмм, управляемых событиями, что позволяет расширять существующий функционал в связи с перспективами дальнейшей разработки темы. Для ускорения работы программного комплекса был предложен параллельный алгоритм вычисления функции парного сравнения цепочек примитивов, для реализации которого применялись технологии параллельного программирования OpenMP и библиотеки для работы с потоками C++11.

Положения, выносимые на защиту:

1 способ автоматического подбора адекватных параметров аппроксимации и регуляризации скелета с целью получения базового скелета бинарного растрового изображения,

2 метод описания базового скелета цепочкой примитивов с учетом радиальной функции скелета,

3 алгоритм вычисления оптимального парного выравнивания цепочек примитивов и определение функции сравнения двух изображений,

4 параллельный алгоритм вычисления оптимального парного выравнивания цепочек примитивов.

Степень достоверности и апробация результатов. Основные положения работы докладывались автором лично и обсуждались на научных конференциях, семинарах и международных стажировках в 2012-2018 гг.

Конференции:

«Интеллектуализация обработки информации»: 9-я международная конференция (Черногория, г. Будва, 2012 г.), 10-я международная конференция (Греция, о. Крит, 2014 г.), 11-я международная конференция (Испания, г. Барселона, 2016 г.);

«Техническое зрение в системах управления»: 4-я, 5-я, 6-я научно-техническая конференция (г. Москва, 2013, 2014, 2015 г.);

«Conference of the International Federation of Classification Societies IFCS-2013»: международная конференция (г. Тилбург, Нидерланды, 2013 г.);

«Математические методы распознавания образов»: 16-я всероссийская конференция (г. Казань, октябрь 2013 г.), 17-я всероссийская конференция с международным участием (г. Светлогорск, Калининградская область, 2015 г.), 18-я всероссийская конференция с международным участием (г. Таганрог, 2017 г.);

«International Conference on Image and Signal Processing ICISP-2014»: международная конференция по анализу сигналов и изображений (г. Шербур, Франция, 2014 г.);

«7th International Conference on Pattern Recognition Applications and Methods ICPRAM 2018»: 7-я международная конференция приложений и методов распознавания образов (г. Фуншал, о. Мадейра, Португалия, 2018 г.);

«Анализ изображений, сетей и текстов - АИСТ» ("Analysis of Images Social Networks and Texts - AIST"): 4-я и 5-я международная конференция (Россия, г. Екатеринбург, 2015, 2016 г.);

«International Conference on Computing for Physics and Technology CPT-2015»: международная конференция (г. Пущино, Московская область, 2015 г.);

«Ломоносов-2013»: XX Международная научная конференция студентов, аспирантов и молодых ученых (г. Москва, МГУ, 2013 г.);

«Молодёжные инновации»: VII и IX региональная молодёжная научно-практическая конференция Тульского государственного университета (г. Тула, 2013, 2015 г.);

VII магистерская научно-техническая конференция (Тула, ТулГУ, 2012 г.);

XII Региональная заочная магистерская научная конференция (Тула, ТулГУ, 2017 г.).

Стажировки:

Институт обработки изображений и прикладной информатики (IBaI) (г. Лейпциг, Германия, 2013 г.);

Тайбэйский национальный технологический университет (г. Тайбей, Тайвань, 2014 г.);

Международная летняя школа по компьютерному зрению (International Computer Vision Summer School - ICVSS, о. Сицилия, Италия, 2014, 2016 г.).

Семинары:

Миддлсекский университет (г. Лондон, Великобритания, 2015 г.).

Личный вклад автора. Представленные в диссертации результаты исследований получены лично автором. В публикациях [21-28,37,63,64], выполненных в соавторстве, соискателю принадлежат основные результаты. В

публикациях [5,9,10,12,38,65], выполненных в коллективе соавторов, результаты исследований соискателя используются как составная часть более общего метода.

Публикации. По теме диссертации опубликовано 26 работ, в том числе 5 статей в изданиях, входящих в Перечень ВАК рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёной степени кандидата наук, 4 статьи в изданиях, входящих в международную систему цитирования Scopus, 3 статьи и 12 публикаций тезисов докладов в сборниках трудов международных, всероссийских и региональных конференций, получено 1 свидетельство о государственной регистрации программы для ЭВМ, выполнен 1 отчёт о НИОКТР.

Структура и объем работы. Диссертация состоит из введения, 5 глав с выводами, заключения, списка литературы, включающего 90 наименований. Общий объем диссертации составляет 129 страниц машинописного текста, содержит 56 рисунков, 8 таблиц и 1 приложение.

1 ОПИСАНИЕ ФОРМЫ БИНАРНЫХ РАСТРОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ СКЕЛЕТИЗАЦИИ

1.1 ПОНЯТИЕ СКЕЛЕТА ИЗОБРАЖЕНИЯ

Описание формы является важной задачей компьютерного зрения, которая может решаться на основании различных подходов. Один из таких подходов - скелетное представление бинарной растровой фигуры. Если аппроксимировать черные точки бинарного растрового изображения непрерывной замкнутой областью, то скелетом замкнутой области называется геометрическое место точек области, являющихся центрами максимальных по включению вписанных окружностей [33,48] (см. рисунок 1).

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

1.2. ДИСКРЕТНЫЙ ПОДХОД К СКЕЛЕТИЗАЦИИ

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

Рисунок 1 - Скелет замкнутой области

Дискретный подход к скелетизации использует определение скелета, основанное на метафоре «пожара в прерии». Предполагается, что по границе области одновременно вспыхивает огонь, который распространяется внутри нее по всем направлениям с постоянной скоростью. Те точки области, в которых сходятся два или более огненных фронта, являются по определению точками скелета. Точка схода фронтов равноудалена от ближайших точек возгорания на границе. «Пожар в прерии» служит основой для определения и построения скелета в терминах бинарных растровых изображений. Подмножество черных точек растра рассматривается как дискретный образ некоторой замкнутой области, граничные точки растрового пятна - как образ границы области, а непрерывное распространение огня моделируется дискретным процессом последовательного «сжигания» соседних черных точек растра.

Процесс построения скелета дискретного образа реализуется в различных алгоритмах «утончения» [4,33], в алгоритме «дистанционных карт» [33], в «волновом» алгоритме [11]. Последовательное «сжигание» соседних черных точек растра на примере метода топологического утончения приведен на рисунке 2 (рисунок взят из источника [33]).

оооооооооооооо оооооооооооооо

•• оо»оо ••• •••

эооос

»

оооооооос оооооооос

// • •••••---

• ••• • ••• • • • • •

оооооооооооооо

• •• • ••

б)

оооооооооооооо оооооооооооооо

ЭОСОООФОО

/• •• ••••• ••

соо/«*«м*оооо

Э0000»0®000<

ооооо#о#оо

О О • О • чО о о <

оооооооооооооо

ооооооооооо ооооооооооо ооооооооооо

оооо#оо

•••••••

оооо оооо

ООО ООО ООО

ООС ОООС

• •

ОООООООООООООО

ЭООСОФОО • • ••

••••• •• ••••••••

• «оооо

эооооооооооо эооооооооооо

ЭООФОО

Э0900 ••

• ••••

• • • • • •

эооооооооооо

й)

Рисунок 2 - Метод топологического утончения

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

Следует отметить, что дискретные скелеты обладают следующими недостатками. Во-первых, расстояние между точками растра при их построении

измеряется не в евклидовой метрике, а, в зависимости от используемой 4-х или 8-связности точек растра, в метрике /1 («манхэттенской») или /ю («шахматной»). Это значит, что в качестве вписанной в область окружности выступает квадрат. Неевклидовы метрики приводят к неустойчивости получаемых скелетов по отношению к простым преобразованиям исходного изображения.

Во-вторых, дискретный скелет вычисляется неоднозначно и зависит от последовательности анализа граничных точек образа. Успешное построение дискретных аналогов скелета возможно, как правило, если дискретные фигуры имеют простую структуру.

1.3. НЕПРЕРЫВНЫЙ ПОДХОД К СКЕЛЕТИЗАЦИИ

Непрерывный подход к построению скелета растрового изображения хорошо исследован и проработан в трудах школы Л.М. Местецкого [32,33,34,39,70]. Подход состоит в аппроксимации границы дискретной фигуры многоугольником минимального периметра и построении скелета области, ограниченной этим многоугольником, в соответствии с формальным его определением, что скелет - это множество тех точек фигуры, для которых существует не менее двух равноудаленных ближайших точек границы области. Итогом применения этого подхода к растровому изображению является математическое описание скелета «непрерывной» замкнутой области, аппроксимирующей данное изображение.

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

Поэтому после построения скелета фигуры проводится выделение в скелете части, которая называется базовым скелетом, и удаление элементов,

появление которых обусловлено шумовыми эффектами. Метод получения этой информативной части скелета называется регуляризацией скелета с контролируемой точностью.

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

На рисунке 3 (рисунок взят из источника [33]) показан многоугольник минимального периметра, скелет (слева), базовый скелет и итоговое циркулярное представление фигуры (справа).

Рисунок 3 - Многоугольник минимального периметра, скелет (слева), базовый скелет и итоговое циркулярное представление фигуры (справа)

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

Недостатком же является существенное усложнение алгоритмов с точки зрения их математического содержания и программной реализации по сравнению с алгоритмами дискретной скелетизации.

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

1.4 ПРОБЛЕМА НЕУСТОЙЧИВОСТИ СКЕЛЕТНОГО

ОПИСАНИЯ

Существенным недостатком скелетного описания формы бинарного изображения является чувствительность к шумам (см. рисунок 4, взятый из источника [51]). Так, скелет чрезвычайно восприимчив к локальным свойствам края объекта: с каждой точкой локального максимума кривизны границы связана отдельная ветвь скелета. Получается, что две области, имеющие сходную форму, но разную изрезанность края, принципиально различны в смысле топологической структуры их скелетов. Следовательно, скелет является неустойчивым дескриптором, который нельзя без дополнительных преобразований использовать для описания и сравнения форм [6,33,80].

Список литературы диссертационного исследования кандидат наук Кушнир Олеся Александровна, 2018 год

СПИСОК ЛИТЕРАТУРЫ

1. Вержбицкий В.М. Численные методы (математический анализ и обыкновенные дифференциальные уравнения): Учеб. пособие для вузов. 2-изд., испр. М.: ООО «Издательский дом «ОНИКС 21 век», 2005. 400 с.

2. Визилътер Ю.В., Сидякин С.В. Использование морфологических спектров для классификации двумерных фигур и бинарных изображений // Вестник компьютерных и информационных технологий, №7, 2013. С. 20-28.

3. Гасфилд Д. Строки, деревья и последовательности в алгоритмах // Информатика и вычислительная биология. СПб: Невский диалект; БХВ-Петербург, 2003. 654 с.

4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2005. 1072 с.

5. Грачева И.А., Копылов А.В., Середин О.С., Кушнир О.А., Ларин А.О. Метод детектирования кисти руки на основе одноклассового классификатора и скелетных графов // Интеллектуализация обработки информации: Тезисы докладов 11-й Международной конференции (Москва, Россия - Барселона, Испания). М.: Торус Пресс, 2016. С.102-103.

6. Домахина Л.Г. Регуляризация скелета для задачи сравнения формы // Математические методы распознавания образов: 14-я Всероссийская конференция, Владимирская обл., г. Суздаль, 21-26 сентября 2009г. Сборник докладов. М.: МАКС Пресс, 2009. С.342-345.

7. Домахина Л.Г., Охлопков А.Д. Изоморфные скелеты растровых изображений // Труды 18 межд. конференции ГРАФИКОН, 2008.

8. Жукова К.В., Рейер И.А. Параметрическое семейство базовых скелетов многоугольной фигуры // Машинное обучение и анализ данных. 2012. Т. 1. №4. С. 391-410.

9. Зенин Д.Г., Середин О.С., Кушнир О.А., Ларин А.О. Детектирование кисти руки на основе одноклассовой цветовой сегментации и сравне-

ния скелетов бинарных изображений // Техническое зрение в системах управления-2015, тезисы научно-технической конференции, Москва, ИКИ РАН, 17-19 марта 2015. С. 97-98.

10.Зенин Д.Г., Середин О.С., Кушнир О.А., Ларин А.О. Комбинирование одноклассовой цветовой сегментации и скелетизации бинарных изображений для детектирования кисти руки // Математические методы распознавания образов: Тезисы докладов 17-й Всероссийской конференции с международным участием, г. Светлогорск, 2015 г. М.: Торус Пресс, 2015. С.176-177.

11.Клубков И.М. Применение волнового алгоритма для нахождения скелета растрового изображения // Вестник Донского государственного технического университета. 2001. Т. 1. №. 1 (7). С. 126-133.

12.Копылов А.В., Середин О.С., Кушнир О.А., Грачева И.А., Ларин А.О. Устойчивое детектирование ладони на изображениях на основе комбинирования информации о цвете и форме // Известия Тульского государственного университета. Технические науки. Вып.11. Ч.1. Тула: Изд-во ТулГУ, 2016. С. 24-40.

13.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ = Introduction to Algorithms, 2-e изд. М.: Вильямс, 2005. 1296 с.

14.Кушнир О.А. Вычисление меры парного различия скелетных графов посредством выравнивания цепочек примитивов // Ломоносов-2013: XX Международная научная конференция студентов, аспирантов и молодых ученых; секция «Вычислительная математика и кибернетика»: Москва, МГУ им. М.В. Ломоносова, 9-12 апреля 2013 г. : Сб. тезисов / Сост. Месяц А.И., Шевцова И.Г. - М.: МАКС Пресс, 2013. С. 50-52.

15.Кушнир О.А. Параметрическое описание радиальной функции скелета бинарного изображения для задачи сравнения форм // Вестник компьютерных и информационных технологий, № 2, 2016. С. 3-12.

16.Кушнир О.А. Параметрическое описание радиальной функции скелета бинарного изображения коэффициентами Лежандра // IX региональная

молодёжная научно-практическая конференция Тульского государственного университета «Молодёжные инновации»: сборник докладов. Ч.П. Тула: Изд-во ТулГУ, 2015. С.298-300.

17.Кушнир О.А. Поиск метрики в пространстве скелетных графов для решения задачи сравнения бинарных растровых изображений // VII магистерская научно-техническая конференция: доклады статей, часть вторая. Тула: Издательство ТулГУ, 2012. С. 18.

18.Кушнир О.А. Применение функции парного сравнения скелетных графов для распознавания лекарственных растений // VII региональная молодёжная научно-практическая конференция Тульского государственного университета «Молодёжные инновации»: сборник докладов, Ч. II. Тула: Изд-во ТулГУ, 2013. С.176-178.

19.Кушнир О.А. Скелет бинарного растрового изображения как основа метода определения зеркальной симметричности // XXI Региональная заочная магистерская конференция (22-26 мая 2017 года): сб. докладов / под научной редакцией канд. техн. наук, доц. Г.Е. Мишуниной. В двух частях. Часть I. Тула: Изд-во ТулГУ, 2017. С.184-185.

20.Кушнир О.А. Сравнение формы бинарных растровых изображений на основе скелетизации // Машинное обучение и анализ данных, т. 1, №3. М.: Вычислительный центр им. А.А. Дородницына Российской Академии Наук, 2012. С. 128-140.

21.Кушнир О.А., Середин О.С. Определение зеркальной симметрии фигур на основе цепочек скелетных примитивов // Математические методы распознавания образов: Тезисы докладов 17-й Всероссийской конференции с международным участием, г. Светлогорск, 2015 г. М.: Торус Пресс, 2015. С.180-181.

22.Кушнир О.А., Середин О.С. Параллельные реализации алгоритма сравнения бинарных изображений на основе описания скелетов цепочками примитивов // Вестник компьютерных и информационных технологий, № 1, 2018. С. 24 - 33.

23.Кушнир О.А., Середин О.С. Построение функции ширины скелета бинарного изображения на основе параметрического описания многочленами Лежандра // Математические методы распознавания образов: 16-я Всероссийская конференция, г. Казань, 6-12 сентября 2013 г.: Тезисы докладов. М.: Торус Пресс, 2013. С.73.

24.Кушнир О.А., Середин О.С. Программа сравнения бинарных растровых изображений на основе скелетного описания формы, представленного цепочками примитивов // Свидетельство о государственной регистрации программы для ЭВМ №2018611213, 25.01.2018.

25.Кушнир О.А., Середин О.С. Процедура оптимального парного выравнивания для сравнения скелетных графов, заданных цепочками примитивов // Интеллектуализация обработки информации: 9-я международная конференция. Черногория, г. Будва, 2012 г. Москва: ТОРУС ПРЕСС, 2012. С. 437-440.

26.Кушнир О.А., Середин О.С. Распараллеливание алгоритма сравнения бинарных изображений, представленных цепочками скелетных примитивов // Математические методы распознавания образов: Тезисы докладов 18-й Всероссийской конференции с международным участием, г. Таганрог, 2017 г. М.: Торус Пресс, 2017. С.114-115.

27.Кушнир О.А., Середин О.С. Функция парного сравнения скелетных графов, заданных цепочками примитивов // Известия Тульского государственного университета. Технические науки, вып. 2. Тула: Издательство ТулГУ, 2013. С. 197-207.

28Кушнир О.А., Середин О.С., Степанов А.В. Экспериментальное исследование параметров регуляризации и аппроксимации скелетных графов бинарных изображений // Машинное обучение и анализ данных. 2014. Т. 1, № 7. С. 817-827.

29.Ланге М. М., Ганебных С. Н., Ланге А. М. Многоклассовое распознавание образов в пространстве представлений с многоуровневым разрешением //Машинное обучение и анализ данных, 2016, Т. 2, №. 1. С. 70-88.

30.Ломов Н.А., Сидякин С.В., Визилътер Ю.В. Классификация двумерных фигур с использованием скелетно-геодезических гистограмм толщин-расстояний // Компьютерная оптика, 2017, 41(2). С. 227-236.

31.Макарова Е.Ю. Классификация лекарственных растений по форме листа на основе скелетного представления // Математические методы распознавания образов: 15-я Всероссийская конференция, г. Петрозаводск, 11-17 сентября 2011 г. Сборник докладов. М.: МАКС Пресс, 2011. С. 412-415.

32.Местецкий Л.М. Компьютерная графика на основе жирных линий // Труды межд. конф. «Графикон-2000», М.: МГУ, 2000. С. 165-173.

33.Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. М.: ФИЗМАЛИТ, 2009. 288 с.

34.Местецкий Л.М., Рейер И.А. Непрерывная гранично-скелетная модель дискретного изображения с контролируемой точностью аппроксимации. // Доклады Всероссийской конференции «Математические методы распознавания образов» (ММРО-11). Москва, 2003. С. 367-371.

35. Методы и алгоритмы беспризнакового анализа скелетных графов бинарных изображений: отчет о НИОКТР (заключ.) / ФГБОУ ВО «Тульский государственный университет»; рук. Кушнир О.А. - Тула, 2015. - 19 с. -Исполн.: Кушнир О.А. - № ГР 01201454718.

36.Рогов А.А., Быстров М.Ю. Структурное распознавание бинарных изображений с использованием скелетов // Математические методы распознавания образов: 15-я Всероссийская конференция, г. Петрозаводск, 11-17 сентября 2011г. Сборник докладов. М.: МАКС Пресс, 2011. С. 420-423.

37.Степанов А.В., Середин О.С., Кушнир О.А. Автоматический подбор адекватных значений параметров регуляризации, аппроксимации и склейки скелетных графов бинарных изображений // Интеллектуализация обработки информации: 10-я международная конференция. Греция,

о. Крит, 4-11 октября 2014 г.: Тезисы докладов. Москва: ТОРУС ПРЕСС, 2014. С. 156-157.

38. Федотова С.А., Середин О.С., Кушнир О.А. Алгоритмы уточнения оси зеркальной симметрии, найденной методом сравнения подцепочек скелетных примитивов // Известия Тульского государственного университета. Технические науки. Вып.11. Ч.1. Тула: Изд-во ТулГУ, 2016. С.99-111.

39.Цискаридзе А.К. Восстановление пространственных циркулярных моделей по силуэтным изображениям: Диссертация на соискание ученой степени кандидата физико-математических наук. МФТИ, 2010.

40.A comparative experiment of several shape methods in recognizing plants / Kadir, A. [et al.] // arXiv preprint arXiv: 1110.1509, 2011.

41.A tree-edit-distance algorithm for comparing simple, closed shapes / Klein, P. [et al.] // Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2000. P. 696-704.

42.An image skeletonization based tool for pollen tube morphology analysis and phenotyping / Wang, C. [et al.] // Journal of integrative plant biology, 55(2), 2013. P. 131-141.

43.Amdahl G. M. Validity of the single processor approach to achieving large scale computing capabilities // Proceedings of the AFIPS Conference Proceedings (30). ACM, 1967. P. 483-485.

44.Attali D., Sanniti di Baja G., Thiel E. Skeleton simplification through non significant branch removal // Image Processing and Communications 3.3-4, 1997. P. 63-72.

45.Bai X., Latecki L.J. Path similarity skeleton graph matching // Pattern Analysis and Machine Intelligence, IEEE Transactions on 30 (7), 2008. P. 12821292.

46.Balfer J., Scholer F., Steinhage V. Semantic skeletonization for structural plant analysis // International Conference on Functional-Structural Plant Models, 2013. P. 42-44.

47.Belongie S., Malik J., Puzicha J. Shape matching and object recognition using shape contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence 24 (4), 2002. P.509-522.

48.Blum H. A transformation for extracting new descriptors of shape // Models for the perception of speech and visual form 19 (5), 1967. P. 362-380.

49.Butenhof D.R. Programming with POSIX threads. Addison-Wesley Professional, 1997.

50. Chapman B., Jost G., Van Der Pas R. Using OpenMP: portable shared memory parallel programming. MIT press, 2008, 384 pp.

51. Choi S.W., Lee S.W. Stability analysis of medial axis transform under relative Hausdorff distance // 15th International Conference on Pattern Recognition Proceedings, IEEE, 2000. Vol. 3. P. 135-138.

52.Computer-aided plant species identification (CAPSI) based on leaf shape matching technique / Du, J.X. [et. al.] // Transactions of the Institute of Measurement and Control 28(3), 2006. P. 275-285.

53.Dupé F.X., Brun L. Shape classification using a flexible graph kernel // International Conference on Computer Analysis of Images and Patterns. Springer, Berlin, Heidelberg, 2009. P. 705-713.

54.Elzinga J., Hearn D.W. The minimum covering sphere problem // Management Science, Vol. 19, Issue 1, 1972. P. 96-104.

55.Faloutsos C., Lin K.-I. FastMap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets // ACM SIGMOD, International Conference on Management of Data, 1995. P. 163-174.

56. Giuliani D.A. Contour- and Skeleton-based Analysis of Biological Shapes // Biological Shape Analysis: Proceedings of the 4th International Symposium. 2017. P. 113-133.

57.Janichen S., Perner P. Aligning concave and convex shapes // Yeung, D.-Y., Kwok, J.T., Fred, A., Roli, F., de Ridder, D. (eds.) SSPR 2006 and SPR 2006. LNCS, vol. 4109, Springer, Heidelberg 2006. P. 243-251.

58.ImageCLEF, Plant Identification, 2012. http: //imageclef. org/2012/plant

59.Intelligent Computing Laboratory, Chinese Academy of Sciences Homepage. http: //www.intelengine.cn/English/dataset

60.Kamani M., Farhat F., Wistar S., Wang J.Z. Skeleton Matching with Applications in Severe Weather Detection // Applied Soft Computing Journal. Elsevier, 2017. https://doi.org/10.1016Zj.asoc.2017.05.037

61.Kopylov A., Seredin O., Kushnir O., Gracheva I. and Larin A. Background-Invariant Robust Hand Detection based on Probabilistic One-Class Color Segmentation and Skeleton Matching // Proceedings of the 7th International Conference on Pattern Recognition Applications and Methods (ICPRAM 2018). P. 503-510.

62.Kurnianggoro L. et al. A survey of 2D shape representation: Methods, evaluations, and future research directions // Neurocomputing, 300, 2018. P. 116.

63.Kushnir O., Seredin O. Parametric Description of Skeleton Radial Function by Legendre Polynomials for Binary Images Comparison // A. Elmoataz et al. (Eds.): ICISP 2014, LNCS 8509, Springer International Publishing Switzerland, 2014. P. 520-530.

64.Kushnir O., Seredin O. Shape Matching Based on Skeletonization and Alignment of Primitive Chains. // M.Yu. Khachay, N. Konstantinova, A. Panchenko, D.I. Ignatov, G.V. Labunets (Eds.): Analysis of Images, Social Networks and Texts. Fourth International Conference, AIST 2015, Yekaterinburg, Russia, April 9-11, 2015, Revised Selected Papers. Communications in Computer and Information Science, Vol. 542, 2015. Springer. P. 123-136.

65.Kushnir O., Fedotova S., Seredin O., Karkishchenko A. Reflection Symmetry of Shapes Based on Skeleton Primitive Chains // Fifth International

Conference, AIST 2016, Yekaterinburg, Russia, April 7-9, 2016, Revised Selected Papers, CCIS, Vol. 661. P. 293-304. Springer International Publishing Switzerland, 2016.

66.Lange M., Ganebnykh S. Tree-like data structures for effective recognition of 2-D solids. // Proceedings of 17th International Conference on Pattern Recognition. ICPR 2004. Vol. 1. P. 592-595.

67.LEAF - Tree Leaf Database, Inst. of Information Theory and Automation ASCR, Prague, Czech Republic, http://zoi.utia.cas.cz/tree_leaves

68.Mallah C., Cope J., Orwell J. Plant leaf classification using probabilistic integration of shape, texture and margin features // Computer Graphics and Imaging/798: Signal Processing, Pattern Recognition and Applications (CGIM2013), Acta Press, 2013. 10.2316/P.2013.798-098.

69.Maragos P. Pattern spectrum and multiscale shape representation // Pattern Analysis and Machine Intelligence, IEEE Transactions on 11 (7), 1989. P. 701-716.

70.Mestetskiy L., Semenov A. Palm Shape Comparison Based on Fat Curves. // Proceedings of 7th Internetional conerence on Pattern recognition and image analysis: new information technologies, St. Petersburg, 2004. P. 788-791.

71.Neuhaus M., Bunke H. Edit distance-based kernel functions for structural pattern classification // Pattern Recognition 39(10), 2006. P.1852-1863.

72.Object recognition as many-to-many feature matching / Demirci, M. F. [et. al.] // International Journal of Computer Vision, 69(2), 2006. P. 203-222.

73. Ogniewicz R. Automatic medial axis pruning by mapping characteristics of boundaries evolving under the Euclidean geometric heat flow onto Voronoi skeletons // Harvard Robotics Laboratory Technical Report, 1995. P. 95114.

74.Optimization techniques on pixel neighborhood graphs for image processing / Mottl, V.V. [et al.] // Jolion, J.-M., Kropatsch, W.G. (eds.) Graph-Based Representations in Pattern Recognition Computing Supplement, Vol. 12. Springer, Wien, 1998. P. 135-145.

75.Reier I.A. Plane figure recognition based on contour homeomorphism // Pattern Recognition and Image Analysis c/c of Raspoznavaniye obrazov i analiz izobrazhenii 11(1), 2001. P. 242-245.

76.Ritter J. An efficient bounding sphere // Graphics gems / Ed. Andrew S. Glassner. Boston, MA: Academic Press, 1990. P. 301-303.

77.Sebastian T.B., Kimia B.B. Curves vs. skeletons in object recognition // Signal Processing 85(2), 2005. P. 247-263.

78.Sederberg T.W., Greenwood E. A physically based approach to 2-D shape blending // Comput. Graphics 26(2), 1992. P. 25-34.

79.Serra J. Image Analysis and Mathematical Morphology. Acad. Press, London, 1982.

80.Shaked D., Bruckstein A.M. Pruning medial axes // Computer Vision and Image Understanding, 1998. Vol. 69, no. 2. P. 156-169.

81.Shape and texture based plant leaf classification / Beghin, T. [et. al.] // Blanc-Talon, J., Bone, D., Philips, W., Popescu, D., Scheunders, P. (eds.) ACIVS 2010, Part II. LNCS, vol. 6475, Springer, Heidelberg, 2010. P. 345353.

82.Shen W., Bai X., YangX., Latecki L.J. Skeleton pruning as trade-off between skeleton simplicity and reconstruction error // Science Chine Information Sciences, 2013, 56(4), pp. 1-14.

83.Shen, W., Jiang, Y., Gao, W., Zeng, D., Wang, X. Shape recognition by bag of skeleton-associated contour parts // Pattern Recognition Letters, 83, 2016. P. 321-329.

84. Shen W., Wang X., Yao C., Bai X. Shape Recognition by Combining Contour and Skeleton into a Mid-Level Representation. Pattern Recognition, Springer Berlin Heidelberg, 2014. P. 391-400.

85.Söderkvist O. Computer vision classification of leaves from Swedish trees. Diss. Linköping, 2001.

86. Tax D. One-class classification; Concept-learning in the absence of counterexamples. // Ph.D thesis. Delft University of Technology, ASCI Dissertation Series, 2001. 146 p.

87. Tian B. Bouncing Bubble: A fast algorithm for Minimal Enclosing Ball problem // Scholarly Essay, 2012. 21 p.

88. Wang Z., Chi Z., Feng D. Shape based leaf image retrieval // IEEE Proceedings of Vision, Image and Signal Processing, vol. 150(1), 2003. P. 34-43.

89. Wu S. G. et al. A leaf recognition algorithm for plant classification using probabilistic neural network // 2007 IEEE international symposium on signal processing and information technology. IEEE, 2007. P. 11-16.

90. Yang C., Feinen C., Tiebe O., Shirahama K., Grzegorzek M. Shape-based object matching using interesting points and high-order graphs // Pattern Recognition Letters, 83, 2016. P. 251-260.

ПРИЛОЖЕНИЕ А

Акт об использовании результатов диссертационной работы в учебном процессе