Разработка алгоритмов построения морфологических спектров для анализа цифровых изображений и видеопоследовательностей тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Сидякин, Сергей Владимирович

• Сидякин, Сергей Владимирович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Сидякин, Сергей Владимирович

Оглавление

Введение

1 Методы анализа формы изображений, математические морфологии и морфологические спектры

1.1. Современное состояние исследований в области описания и сравнения форм

1.2. Морфология Серра и морфологические спектры Марагоса

1.2.1. Морфологические операции на бинарных и полутоновых изображениях

1.2.2. Морфологические спектры на структурирующих элементах

1.2.3. Известные алгоритмы вычисления морфологических операторов и морфологических спектров

1.2.4. Практические приложения морфологических спектров

1.3. Непрерывная морфология бинарных изображений Л. М. Местедкого

1.4. Критериальная проективная морфология и критериальные морфологические спектры

1.5. Выводы по Главе 1

2 Разработка алгоритмов построения морфологических спектров с использованием непрерывной бинарной морфологии 46 2.1. Вычисление морфологических спектров плоских фигур с использованием непрерывных скелетных представлений

2.1.1. Непрерывно-аналитический подход к вычислению морфологических спектров на основе скелетных представлений

2.1.2. Вычислительно эффективные алгоритмы растеризации ребер непрерывного скелетного представления

2.1.3. Дискретно-непрерывный алгоритм вычисления морфологических спектров на основе скелетных представлений

2.2. Построение морфологических спектров полутоновых изображений

2.2.1. Полутоновая морфология Серра и морфологические спектры полутоновых изображений

2.2.2. Стековый алгоритм вычисления морфологического спектра полутоновых изображений с плоским структурирующим элементом

2.2.3. Примеры построения морфологических спектров полутоновых изображений

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

2.3.1. ЕМЭ-метрики

2.3.2. Устойчивость описаний и робастное сравнение

2.3.3. Схема доказательства устойчивости сравнения морфологических спектров бинарных фигур при помощи ЕМ И метрик

2.3.4. Робастное сравнение гистограмм изображений при помощи ЕМ Б метрик

2.3.5. Преобразование Марагоса и его связь с морфологическими спектрами

2.3.6. Устойчивость дискретных преобразований Марагоса (карт толщин) бинарных изображений

2.3.7. Устойчивость дискретных морфологических спектров фигур

2.3.8. Усеченные спектры. Инвариантность к сдвигу и повороту фигур. Сравнение форм при помощи усеченных морфологических спектров

2.3.9. Экспериментальное исследование алгоритма сравнения морфологических спектров в задачах классификации объектов

по форме

2.4. Выводы по Главе 2

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

3.1. Проективная морфологическая регуляризация контурных многоугольников

3.2. Алгоритм динамического программирования для решения задачи РГСП

3.3. Результаты тестирования процедуры РГСП

3.4. Выводы по Главе 3

4 Разработка алгоритмов построения морфологических спектров по параметру сложности

4.1. Критериальные проективные морфологии и морфологические спектры по параметру сложности

4.2. Алгоритм вычисления дискретного морфологического спектра по параметру сложности

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

4.4. Выводы по Главе 4

5 Практические приложения

5.1. Использование морфологических спектров в задаче проверки подлинности металлографской печати

5.1.1. Морфологическое выделение особенностей формы металлографских усиков

5.1.2. Примеры морфологических спектров металлографской печати

5.1.3. Результаты сравнения быстродействия алгоритмов построения морфологического спектра для изображений металлографской печати

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

5.2.1. Выделение движущегося объекта-кандидата из видеопотока

5.2.2. Построение вектора признаков выделенного движущегося объекта на основе карты толщин

5.2.3. Классификация движущегося объекта

5.2.4. Экспериментальные результаты

5.3. Выводы по Главе 5

Заключение

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

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

Введение

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

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

Как было показано многими исследователями, морфологический спектр является достаточно удобным и востребованным инструментом анализа изображений. В частности, в работах Е Догерти (1992) морфологические спектры успешно применялись для решения задач анализа текстуры и выделения мелкоразмерных объектов различных типов. В работе А Асано (1999) был предложен способ вычисления характеристик текстуры с использованием морфологического спектра. Анализом текстуры применение морфологического спектра не ограничилось М

Вилкинсон и П. Салембиер (2009) использовали морфологические спектры для адаптивной настройки параметров морфологической фильтрации и сегментации изображений (например, изображений магнитно-резонансной ангиографии, изображения галактик высокого разрешения).

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

Высокая вычислительная сложность построения морфологического спектра связана с тем, что его определение, данное Марагосом, требует выполнения одной операции открытия (закрытия) всего изображения на каждый отсчет спектра. "В связи с этим возможность ускорения процедур вычисления спектров традиционно связывались с оптимизацией процедур вычисления базовых морфологических фильтров. В частности, Ван Другенброек и Талбот (1996), Винсент (2000), Гил и Киммел (2002) предложили ряд эффективных алгоритмов вычисления морфологических операторов Серра. Лучший из известных алгоритмов был предложен Е. Урбахом и М. Вилкинсоном (2008). При этом он позволял строить морфологические спектры для произвольного структурирующего элемента. Однако и при использовании этого алгоритма для вычисления спектра традиционным способом требуется слишком много времени. Таким образом, проблема вычисления морфологических спектров в реальном времени остается по-прежнему актуальной.

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

В последние годы появились предпосылки для решения указанных проблем формирования и сравнения морфологических спектров, связанные с алгоритмическими и математическими подходами, развитыми в рамках непрерывной бинарной морфологии, предложенной Л.М. Местецким, и обобщенной критериальной морфологии, предложенной Ю.В. Визильтером на основе работ Ж. Серра и Ю.П. Пытьева. Непрерывная бинарная морфология Местецкого исследует способы описания формы объектов в цифровых бинарных изображениях с помощью

непрерывных моделей (многоугольных границ, скелетов, циркуляров). В отличие от дискретного подхода, данный подход позволяет осуществлять анализ формы фигур в реальном времени. Математический аппарат критериальной проективной морфологии позволяет вскрыть единую математическую природу таких подходов как корреляционный анализ, математическая морфология Серра, морфология разбиений кадра Ю.П. Пытьева, методы голосования, восходящие к преобразованию Хафа, частотные и пространственно-частотные методы фильтрации. При этом многие практические инструменты, созданные в рамках морфологических систем одного типа, могут быть реализованы и для морфологий другого типа. В частности, в работе Визильтера (2008) была указана возможность построения спектра по параметру морфологической сложности. Однако ни для одной конкретной морфологии такие спектры ранее не были построены.

Таким образом, отсутствие эффективных алгоритмов вычисления морфологических спектров Марагоса в рамках морфологии Серра, а также методов вычисления морфологических спектров применительно к другим видам математических морфологий определило выбор темы данной диссертационной работы «Разработка алгоритмов построения морфологических спектров для анализа цифровых изображений и видеопоследовательностей», а также актуальность рассматриваемых в ней проблем.

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

При этом решались следующие задачи:

1) Разработка вычислительно эффективных алгоритмов построения морфологических спектров для бинарной и полутоновой морфологии Серра на основе непрерывной бинарной морфологии;

2) Разработка алгоритмов построения обобщённых морфологических спектров по параметру сложности на основе проективной критериальной морфологии;

3) Разработка алгоритмов сравнения морфологических спектров, применимых в задачах классификации объектов по форме;

4) Разработка прикладных алгоритмов морфологического анализа изображений на основе морфологических спектров и непрерывной бинарной морфологии

Диссертационная работа выполнена в подразделении 3000 «Системы интеллектуального анализа данных, технического зрения, улучшенного и синтезированного видения» Федерального государственного унитарного предприятия «Государственный научно-исследовательский институт авиационных систем» на основе исследований, проводившихся при поддержке РФФИ в рамках грантов №09-07-13551-офи ц, №11-08-01114-а, №11-08-01039-а, №12-07-31218-мол а.

Методы исследования. Теоретические исследования выполнены на основе методов компьютерного зрения, обработки изображений, математической морфологии, вычислительной геометрии, методов динамического программирования. Экспериментальные исследования проводились на реальных и синтезированных цифровых изображениях в средах Pisoft, Borland Delphi 7, Microsoft Visual Studio. Для реализации алгоритмов использовались языки Object Pascal и С++. Достоверность полученных результатов подтверждена программным моделированием.

Научная новизна диссертационной работы состоит в следующем:

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

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

3) Разработан новый подход к сравнению морфологических спектров, отличающийся использованием EMD метрики. Для случая EM D — L1 метрики (расстояния Вассерштейна 1-го порядка) доказана устойчивость сравнения морфологических спектров при помощи EMD метрик к сочетанию площадных и контурных искажений формы фигур.

4) Предложен оригинальный алгоритм проективной морфологической регуляризации гранично-скелетных представлений формы плоских многоугольных фигур.

5) Предложены алгоритмы вычисления дискретных и непрерывных критериальных морфологических спектров по параметру морфологической

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

На защиту выносятся следующие положения:

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

2) Доказана устойчивость сравнения морфологических спектров при помощи ЕМ И — Ь1 метрики (расстояния Вассерштейна 1-го порядка) к сочетанию площадных и контурных искажений формы фигур, характеризуемых расстояниями Ь1 и Хаусдорфа между сравниваемыми фигурами.

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

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

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

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

времени.

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

1. 2-ая конференция молодых учёных и специалистов московского отделения международной общественной организации "Академия навигации и управления движением". - г. Москва, 2009;

2. 10-th International Conference Pattern Récognition and Image Analysis: New Information Technologies (PMA-10-2010). - г. Санкт-Петербург. 2010;

3. 15-я Всероссийская конференция "Математические методы распознавания образов". - г. Петрозаводск, 2011;

4. Юбилейная научно-техническая конференция "Моделирование авиационных систем". - г. Москва, 2011;

5. Научно-технические конференции "Техническое зрение в системах управления". - г. Москва, 2012, 2013;

6. 9-я Международная конференция "Интеллектуализация обработки информации". - Черногория, г. Будва, 2012;

Публикации. Основные результаты диссертационной работы опубликованы в 8 статьях в журналах, входящих в перечень ВАК [1] - [8], в сборниках трудов [9]

- [13].

Объем и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы (94 наименования). Работа содержит 163 станицы, 71 рисунок и 6 таблиц.

Во введении описана актуальность и цели работы.

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

Вторая глава посвящена разработке алгоритмов построения и сравнения

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

Рассматриваемый в первом разделе подход к вычислению морфологических спектров с дисковым структурирующим элементом основан на использовании непрерывных скелетных представлений плоских фигур. Этот подход позволяет формировать дискретно-непрерывные морфологические спектры плоских фигур в реальном времени, что делает их пригодными для использования в прикладных задачах машинного зрения.

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

В разделе три рассматривается проблема использования морфологических спектров для классификации двумерных фигур и бинарных изображений. При этом предлагается сравнивать морфологические спектры при помощи ЕМО метрик, введённых в работе [37] и используемых для сравнения гистограммо-подобных описаний. Для случая ЕМ£> — Ь1 метрики (расстояния Вассерштейна 1-го порядка) доказана устойчивость сравнения морфологических спектров при помощи ЕМ И — Ь1 метрик к сочетанию площадных и контурных искажений формы фигур. Экспериментально показано, что ЕМО — Ь1 расстояния между морфологическими спектрами могут успешно использоваться для решения задач классификации объектов по форме. Экспериментально оценено время работы алгоритмов скелетизации, построения морфологического спектра и ЕМИ — Ь1 метрики.

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

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

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

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

Алгоритм построения непрерывных критериальных морфологических спектров заключается в построении непрерывной зависимости критерия морфологического риска от параметра морфологической сложности. При этом используются алгоритмы параметрической оптимизации, аналогичные описанным в [28], [29].

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

1. Методы анализа формы изображений, математические морфологии и морфологические

спектры

1.1. Современное состояние исследований в области описания и сравнения форм

При описании методов сравнения форм можно выделить две основные составляющие

- способ описания формы,

- способ сравнения описаний (метрика или мера сходства)

Рассмотрим сначала способы описания форм Достаточно полный обзор таких дескрипторов формы содержится, например, в известной работе [17] Можно выделить следующие основные методы описания геометрической формы

- Методы, основанные на глобальных преобразованиях изображений При этом могут использоваться преобразование Фурье, различные вейвлет-преобразования (Jacobs et al , 1995, J Z Wang et al , 1997), преобразование Радона,

- Методы, основанные на измерении геометрических характеристик фигур и интегральных моментах Здесь используются такие характеристики как площадь, периметр, формат, диаметр число связных областей, число дыр, число Эйлера и т п , а также интегральные моменты и различные построенные на них инварианты (Ни 1962 Flusser, 2000),

- Методы, основанные на разложении по собственным векторам и собственным функциям (всего образа или его части) (Sclaroff, 1997; Günsel, 1998);

- Методы основанные на многомасштабных контурных описаниях (curvature scale space) (Mokhtarian et.al., 1996);

- Методы, основанные на выделении, запоминании и последующем голосовании элементов формы - обобщенное преобразование Хафа (Ballard, 1981), pose clastering (Stockman, 1987) и т.п. К этой же группе примыкают такие популярные в последнее время методы, основанные на выделении опорных элементов формы алгоритмами машинного обучения, как метод Виолы-Джонса с хаароподобными признаками и обучением на основе Adaboost, а также более современные версии этого подхода типа Codebook и ряд других;

- Методы, основанные на геометрических примитивах и вычислительной геометрии (Mulmuley, 1993; Boissonnat, Yvinec, 1998). В этих методах строятся и сравниваются геометрические модели в терминах точек, линий, многоугольников, многогранников;

- Методы, основанные на анализе групп преобразований (Veitkamp, Hagedoorn, 2001). В рамках такого подхода под формой понимается орбита группы, то есть множество образов, замкнутое относительно некоторой группы преобразований. (Данный подход близок к морфологическому, однако под преобразованиями здесь, как правило, понимаются только геометрические преобразования);

- Методы, основанные на параметрических описаниях кривых (контуров) (Veitkamp, 1998; Cohen, Guibas, 1997; Borgefos, 1988). При этом могут использоваться дискретные цепные коды, аналитические аппроксимации многоугольниками, функции поворотов, контурные сигнатуры, функции размера (size functions), символьные описания, основанные на особых точках контура и ряд других;

- Методы, основанные на описании формы областей. К этой группе принадлежат методы морфологии Серра (Serra, 1982), дискретные скелеты, серединные линии (Chin et.al, 1995), карты расстояний (distance transform) и т.п.

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

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

- какие расстояния между точками (элементами) формы в данном методе рассматриваются;

- какие статистики от этих расстояний рассчитываются.

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

В качестве дескриптивных статистик в различных работах используются:

- полные матрицы парных расстояний;

- гистограммы всех парных расстояний (Shape distributions) (Osada, Funkhouser et. al., 2001)";

- гистограммы расстояний от каждой точки до всех остальных (Shape contexts) (Belongie, Malik, 2000);

- среднее расстояние от каждой точки до всех остальных (Ben Hamza, Hamid Krim, 2005).

Достаточно полный обзор и экспериментальное сравнение таких методов описания формы можно найти, например, в работе (Mahmoudi, Sapiro, 2009).

В последние годы в отдельное и быстро развивающееся направление также выделились дескрипторы формы, основанные на «тепловых ядрах» и диффузных преобразованиях, а также их спектральных и других производных характеристиках (Lafon, 2004; Coifman, Lafon, 2006). Инвариантные описания форм как точечных множеств, представляющие собой диагональ теплового ядра (Heat Kernel Signature, HKS), были предложены в (Sun, Ovsjanikov, Guibas, 2009; Gebal et.al., 2009). Схожие описания использовались в работах (F. de Goes, 2008; M. Gori et.al., 2005; X. Bai, 2007) для геометрических моделей, описываемых графами. Сравнение форм как многообразий в пространстве диффузных отображений было предложено в (Lieu, Saito, 2008; Lafon et.al., 2006). В известной работе (М. Reuter, F. Е. Wolter, N. Peinecke, 2006) в качестве дескрипторов формы было предложено использовать наборы собственных значений тепловых ядер (точнее, соответствующих операторов Лапласа-Бельтрами), то есть тепловые спектры, названные ShapeDNA (генетический код формы). В литературе также рассматриваются

такие статистики как распределение HKS (heat kernel signature distribution, HKSD) и тепловой след (heat trace). Существует и множество других модификаций этого подхода, часто называемого также «спектральным» подходом к описанию формы. В работе (Memoli, 2011) проведена последовательная классификация этих методов и дано их описание в едином математическом ключе.

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

Для сравнения форм как многообразий, а также их различных описаний в литературе используется широкий набор известных метрик, таких как евклидово расстояние L2, расстояния Минковского Lp и в частности манхэттенское расстояние L1 и максимальное отклонение L°° (для сигнатур), расстояния Канторовича-Вассерштейна и их частный случай EMD метрика (для распределений), расстояния Хэмминга и Левенштейна (для символьных описаний), мера симметричной разности, расстояния Хаусдорфа и Громова-Хаусдорфа (непосредственно для многообразий).

В последние годы наилучшие результаты в области сравнения форм и изображений обеспечивает группа методов, основанных на метриках, связанных с решением т.н. транспортной задачи (mass transportation). В литературе они имеют много различных названий, но чаще всего используются термины Earth Mover's Distance (EMD, экскаваторные метрики), метрики Монжа-Канторовича-Мэллоуза или Канторовича-Рубинштейна-Вассерштейна. В работах Мемоли (Memoli, 2009, 2011) описан оригинальный вариант обобщения таких метрик под названием «метрики Громова-Вассерштейна», причем эти метрики были получены как («смягчение») метрики Громова-Хаусдорфа. В последующих работах Мемоли в качестве дальнейшего развития были предложены «спектральные метрики Громова-Вассерштейна» (spectral notion of Gromov-Wasserstein distance). Суть

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

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

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

1.2. Морфология Серра и морфологические спектры Марагоса

Описанный в данном разделе морфологический математический формализм предложен в работе Ж. Серра [23].

Пусть дано евклидово пространство EN, на множестве объектов (подмножеств) которого введены отношения включения (с), объединения (и) и пересечения (п). Рассмотрим некоторое преобразование Ф : EN —> EN (оператор Ф). Оператор Ф называется увеличивающим (increasing), если

Список литературы диссертационного исследования кандидат наук Сидякин, Сергей Владимирович, 2013 год

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

1. Сидякин С.В., Визилътер Ю.В. Регуляризация гранично-скелетных представлений формы бинарных фигур методом динамического программирования // Вестник компьютерных и информационных технологий, 2011, № 9, С. 9-16.

2J Vizilter Yu., Sidy akin S., Rubis_ A., Gorbazevich V. Morphological shape comparison based on skeleton representations // Pattern Recognition and Image Analysis, 2012, vol. 22, № 3. pp. 412-418.

3. Визилътер Ю.В., Сидякин С. В. Построение морфологических спектров полутоновых изображений // Вестник компьютерных и информационных технологий, 2012, № 4, С. 8-17.

4. Визилътер Ю.В., Сидякин С. В. Построение спектров морфологической сложности // Вестник компьютерных и информационных технологий, 2012, № 11, С. 3-8.

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

6. Визилътер Ю.В., Сидякин С. В. Бициклические каркасы двумерных фигур // Вестник компьютерных и информационных технологий, N10, 2012, С. 17-21.

7. Vizilter Yu., Sidy akin S., Rubis A., Gorbazevich V. Skeleton-based morphological shape comparison // Pattern Recognition and Image Analysis, 2011, vol. 21, № 2, pp. 357-360.

8. Сидякин С.В., Рубис А.Ю., Горбацевич B.C. Построение и использование морфологических коэффициентов корреляции в задачах анализа изображений

// Вопросы оборонной техники. Сер. 9. Специальные системы управления, следящие приводы и их элементы, 2010, выпуск 3(244) — 4(245), С. 53-59.

9. Визилътер Ю.В., Сидякин C.B., Рубис А.Ю. Вычисление морфологических спектров плоских фигур с использованием непрерывных скелетных представлений // Математические методы распознавания образов: 15-я Всероссийская конференция. г.Петрозаводск, 11-17 сентября 2011 г.: сборник докладов. -М.: МАКС Пресс, 2011, С. 416-419.

10. Визилътер Ю. В., Сидякин С. В. Построение обобщенных скелетов многоугольных бинарных фигур с многоугольными выпуклыми структурирующими элементами // 9-я международная конференция. «Интеллектуализация обработки информации», Черногория, г. Будва, 2012: Сборник докладов. - М.-: Торус Пресс, С. 414-418.

11. Визилътер Ю.В., Сидякин C.B. Бициклические каркасы двумерных фигур // Техническое зрение в системах управления - 2012. Труды научно-технической конференции. Москва, ИКИ РАН, 2012, С. 258-264.

12. Визилътер Ю.В., Сидякин C.B. Морфологические спектры // Техническое зрение в системах управления - 2012. Труды научно-технической конференции. Москва, ИКИ РАН, 2012, С. 234-241.

13. Горбацевич B.C., Визилътер Ю.В., Рубис А.Ю., Сидякин C.B. Морфологические методы анализа изображений земной поверхности // Юбилейная научно-техническая конференция «Моделирование авиационных систем». г.Москва, 12-14 апреля 2011 г.: сборник докладов. - М.: ФГУП «ГосНИИАС», С.269-278.

14. Maragos P. Pattern Spectrum, Multiscale Shape Representation // IEEE Trans.on pattern analysis, machine intelligence, Vol, II, No 7, 1989.

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

16. Визилътер Ю. В. Обобщенная проективная морфология // Компьютерная оптика, Том 32, № 4. 2008.

17. R. С. Veltkamp, M. Hagedoorn State of the art in shape matching // Principles of visual information retrieval, Springer-Verlag, London, pp. 87 - 119, 2001.

18. Визилътер Ю.В., Желтое С.Ю., Ларетина H.A. Проективные морфологии на базе операторов фильтрации и сегментации изображений, вычислимых методом динамического программирования //' Вестник компьютерных и информационных технологий, 2009, № 6.

19. Домахина Л. Г. Регуляризация скелета для задачи сравнения формы // Математические методы распознавания образов: доклады XIV Всерос. конф. М., 2009, С. 342-346.

20. Местецкий Л. М., Рейер И. А. Непрерывное скелетное представление изображения с контролируемой точностью // Труды 15 международной конференции ГРАФИКОН-2003, С. 246-249.

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

22. Домахина, Л. Г. Скелетная сегментация и циркулярная морфология многоугольников // Диссертационная работа, Москва, МГУ, 2012, С. 147.

23. Serra J. Image Analysis and Mathematical Morphology // Academic Press, London, 1982, P. 610.

24. Dougherty E.R. . The dual representation of gray-scale morphological filters // IEEE Trans. PAMI, 1989.

25. Препарата Ф., Шеймос M. Вычислительная геометрия: Введение // М.: Мир 1989, С. 478.

26. Yeong-Chyang Shih F., Mitchell O.R. Threshold Decomposition of gray Scale Morphology into Binary Morphology // IEEE trans, on pattern analysis, machine intelligence, vol. II, No 1, 1989.

27. Тихонов A. H. Теория восстановления сигналов // M.: Наука, 1983, С. 225.

28. Kolmogorov V., Boykov Y., Rother C. Applications of parametric maxflow in computer vision // IEEE International Conference on Computer Vision (ICCV), 2007.

29. Dinkelbach W. On nonlinear fractional programming // Manage. Sci., 13:492-498, 1967.

30. Eisner M. J., Severence D. G. Mathematical techniques for efficient record segmentation in large shared databases //J. ACM, 23(4):619-635, 1976.

31. Gusfield D. Sensitivity analysis for combinatorial optimization // PhD thesis, UC Berkeley, 1980.

32. Вишняков Б.В., Визилътер Ю. В.,-Выголов О. В. Построение кратнорегресси-онных псевдоспектров для выделения и прослеживания объектов в системах видеонаблюдения // Математические методы распознавания образов: 15-я Всероссийская конференция, г. Петрозаводск, 11-17 сентября 2011г.: Сборник докладов,- М.: МАКС Пресс, 2011

33. Вишняков Б.В., Визилътер Ю.В., Лагутенков А.В. Использование модифицированного метода оптических потоков в задаче обнаружения и межкадрового прослеживания движущихся объектов // Вестник компьютерных и информационных технологий, 2007, No 5, С. 3-8.

34. Ни М. К. Visual pattern recognition by moment invariants. // IRE Trans. Information Theory, 1962, Vol. IT-8.

35. Flusser J. On the independence of rotation moment invariants // Pattern recognition, vol. 33, 2000, C. 1405-1410.

36. Виноградов И. M. Устойчивости теория // Математическая энциклопедия, Т. 5, 1977. С. 551-553.

37. Yossi Rubner, Carlo Tomasi, Leonidas J. Guibas The Earth Mover's Distance as a Metric for Image Retrieval // International Journal of Computer Vision, 2000, № 40(2), pp. 99-121.

38. Пытьев Ю.П., Чуличков А. И. Методы морфологического анализа изображений // М.: ФИЗМАТЛИТ, 2010, С. 336.

39. J. Darbon and S. Peyronnet. A Vectorial Self-Dual Morphological Filter based on Total Variation Minimization // Proceedings of the 1st International Symposium on Visual Computing (ISVC 2005), LNCS Series vol. 3804,2005, pp. 388-395.

40. J. Darbon and M. Sigelle. Image Restoration with Discrete Constrained Total Variation Part I: Fast and Exact Optimization // Journal of Mathematical Imaging and Vision (JMIV), Vol 26 n.3, 2006, pp. 261-276.

41. A.Asano Texture Analysis Using Morphological Pattern Spectrum and Optimization of Structuring Elements //Proc. 10th International Conference on Image Analysis and Processing (ICIAP '99), pp. 209-214.

42. P. Salembier and M.H.F. Wilkinson Connected Operators: A review of region-based morphological image processing techniques // IEEE Signal Processing Magazine (2009), 26(6):136-157.

43. С. С. Валландер Вычисление расстояния no Вассерштейну между распределениями вероятностей на прямой // ТВП, 18:4 (1973), С. 824—827.

44. С. Т. Рачев Задача Монжа-Канторовича о перемещении масс и ее применение в стохастике // ТВП, 29:4 (1984), С. 625-653.

45. Деза Е.И., Деза М.М. Энциклопедический словарь расстояний // М.: Наука, 2008, С. 444.

46. Datasets // URL: http://tosca.cs.technion.ac.il/book/resources_data.html

47. Ghosh P., Chanda В. Bi-Variate Pattern Spectrum // Proc. IEEE CS Brazilian Symp. Computer Graphics and Image Processing (SIBGRAPI '98), pp. 476-483.

48. Athreya G., Ghosh D.: Trivariate pattern spectrum: A shape-size descriptor for gray scale images // Proc. 8th Natl. Conf. Communications, Mumbai, India, 2002, pp. 40-44.

49. Wilkinson M.H.F. Generalized pattern spectra sensitive to spatial information // Proc. 16th Int. Conf. Pat. Rec., Vol. 1, Quebec City, Canada, 2002, pp. 21-24.

50. Urbach E. R., Wilkinson M. H. Efficient 2-d grayscale dilations and erosions with arbitrary flat structuring elements // Proc. Int. Conf. Image Processing, 2006, pp. 1573-1576.

51. Urbach E. R., Wilkinson M. H. Efficient 2-D gray-scale morphological transformations with arbitrary flat structuring elements // IEEE. Trans. Image Processing, 2008.

52. Gil J. and R. Kimmel Efficient dilation, erosion, opening and closing algorithms // IEEE Trans. Pattern Anal. Mach. Intell., Vol. 24, no. 12, 2002 ,pp. 1606-1617.

53. Vincent L. Granulometries and opening trees // Fundam. Inf., vol. 41, 2000, pp. 57-90.

54. Van Droogenbroeck M., Talbot H. Fast computation of morphological operations with arbitrary structuring elements // Pattern Recognit. Lett., vol. 17, 1996, pp. 1451-1460.

55. Suruliandi A., Ramar K. Local Texture Patterns - A Univariate Texture Model for Classification of Images // 16th International Conference: Advanced Computing and Communications, pp. 32-39, 2008.

56. Tchangou Toudjeu Ignace Pattern spectra algorithms for pattern recognition // Tshwane University of Technology, 2006, P. 208.

57. Gomez-Gil P., M. Ramirez-Cortes et al A Feature Extraction Method Based on Morphological Operators for Automatic Classification of Leukocytes // MICAI '08 Proceedings of the 2008 Seventh Mexican International Conference on Artificial Intelligence,pp. 227-232, 2008.

58. Zingman I., Meir R., El-Yaniv R. Size-Density Spectra and their Application to Image Classification // Pattern Recognition, Volume 40 Issue 12, December, 2007, pp. 3336-3348.

59. Barnich O., Jodogne S., Van Droogenbroeck M. Robust Analysis of Silhouettes by Morphological Size Distributions // Advanced Concepts for Intelligent Vision Systems, 8th International Conference, ACIVS 2006, 2006, Proceedings. Volume 4179 of Lecture Notes in Computer Science, pages 734-745, Springer, 2006.

60. Jalba А.С, Roerdink J.В.T.M., Wilkinson M.H.F. Morphological hat-transform scale spaces and their use in texture Image Processing, vol. 1, 2003, pp. 329-332.

61. Bagdanov A., Worring M. Granulometric analysis of document images // IEEE, ed.: Proceedings of the International Conference on Pattern Recognition, Volume I. (2002). pp. 478-481.

62. Lefevre S. Beyond morphological size distribution // Journal of Electronic Imaging, Vol. 18(01), 013010.

63. Batman S., Dougherty E. R. Size distributions for multivariate morphological granulometries: texture classification and statistical properties // Optical Engineering, Vol.36, Iss. 5, pp. 1518:1529, 1997.

64. Bronskill J.F., Venetsanopoulos A. N. Multidimensional shape description and recognition using mathematical morphology // Journal of Intelligent and Robotic Systems 1988, Volume 1, Issue 2, pp 117-143.

65. Dougherty E. R., Newell J. T., and Pelz J. B. Morphological Texture-Based Maximum-Likelihood Pixel Classification Based on Local Gramulometric Moments // Pattern Recognition, vol. 25, no. 10, pp. 1181-1198, 1992.

66. Alois Zingl. A Rasterizing Algorithm for Drawing Curves // Multimedia und Softwareentwicklung, Technikum-Wien, Wien, 2012, [Электронный ресурс], URL: http : //members. chello. at/ easyfilter/Bresenham .pdf

67. Radke, R.J., Andra, S., Al-Kofahi, O., Roysam, В Image change detection algorithms: A systematic survey. // IEEE transactions on image processing 14 (2005), 294-307.

68. Facundo Memoli A spectral notion of Gromov-Wasserstein distance and related methods // Appl. Comput. Harmon. Anal. 30, (2011), 363-401.

69. База данных видеозаписей Video Understanding Evaluation project ETISEO // [Электронный ресурс], URL: http://www-sop.inria.fr/orion/ETISEO.

70. Гонсалес P., Вудс P. Цифровая обработка изображений //М.:Техносфера, 2006, С. 1072.

71. L. J. van Vliet and B. J. Verwer A contour processing method for fast binary neighborhood operations 11 Pattern Recognit. Lett., no. 7, pp. 27—36, Jan. 1988.

72. L. Ji, J. Piper, and J.-Y. Tang Erosion and dilation of binary images by arbitrary structuring elements using interval coding // Pattern Recognit. Lett., vol. 9, no. 3, pp. 201-209, 1989.

73. L. Vincent Morphological transformations of binary images with arbitrary structuring elements // Signal Process., vol. 22, no. 1, pp. 3—23, 1991.

74. M. van Herk A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels // Pattern Recognit. Lett., vol. 13, pp. 517-521, 1992.

75. E.-H. Liang and E. K.Wong Hierarchical algorithms for morphological image processing // Pattern Recognit., vol. 26, no. 4, pp. 511—529, 1993.

76. H. Park and R. T. Chin Decomposition of arbitrarily shaped morphological structuring elements // IEEE Trans. Pattern Anal. Mach. Intell., vol. 17, no. 1, pp. 2-15, Jan. 1995.

77. P. Soille, E. Breen, and R. Jones Recursive implementation of erosions and dilations along discrete lines at arbitrary angles // IEEE Trans. Pattern Anal. Mach. Intell., vol. 18, no. 5, pp. 562-567, May 1996.

78. G. Anelli, A. Broggi, and G. Destri Decomposition of arbitrarily shaped binary morphological structuring elements using genetic algorithms // IEEE Trans. Pattern Anal. Mach. Intell., vol. 20, no. 2, pp. 217-224, Feb. 1998.

79. N. Nikopoulos and I. Pitas A fast implementation of 3-d binary morphological transformations // IEEE Trans. Image Process., vol. 9, no. 2, pp. 283-286, Feb. 2000.

80. M. Van Droogenbroeck and M. Buckley Morphological erosions and openings: Fast algorithms based on anchors // J. Math. Imag. Vis., vol. 22, pp. 121-142, 2005.

81. P. Soille and H. Talbot Directional morphological filtering // IEEE Trans. Pattern Anal. Mach. Intell, vol. 23, no. 11, pp. 1313-1329, Nov. 2001.

82 Bresenham J E Algorithm for computer control of a digital plotter // IBM Systems Journal 4 (1) 25-30

83 Free High Quality Silhouette Sets // [Электронный ресурс], http //www hongkiat com/blog/85-free-high-quality-silhouette-sets/

84 Шилдт Г Си для профессиональных программистов // М , 1989

85 Корн Г, Корн Т Справочник по математике для научных работников и инженеров // М Наука, 1968, С 47

86 Navneet Dalai, Bill Triggs Histogram of Oriented Gradients for Human Detection // CVPR, 2005 pp 886-893

87 Lowe, David G Object recognition from local scaleinvanant features // Proceedings of the International Conference on Computer Vision, 1999 pp 1150-1157

88 Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool Speeded-Up Robust Features (SURF) // Computer Vision and Image Understanding, Vol 110, No 3, 2008, pp 346-359

89 Geurts P , Ernst D , Wehenkel L Extremely randomized trees // Machine Learning Journal, volume 63, issue 1, apnl 2006, pp 3-42

90 Maree R , Geurts P , Plater J , Wehenkel L Random subwmdows for robust image classification // IEEE Conference on Computer Vision and Pattern Recognition Volume 1 , San Diego (CA, USA) ,2005, pp 34-40

91 Breiman L Bagging predictors // Machine Learning, 26, 1996, pp 123-140

92 Breiman L Random forests // Machine Learning, 45, 2001, pp 5-32

93 Nene S , Nayar S , Murase H Columbia object image library Coil-100 // Technical report, 1996

94 Czyza J, Risticb В , Macqa В A particle filter for joint detection and tracking of color objects // Image and Vision Computing Volume 25, Issue 8, 1 August 2007, pp 1271-1281