Содержание к диссертации
Введение ... 4
Иерархия использовавшихся моделей и методов ... 9
1. Методы сравнения объекта и эталона с помощью модификаций расстояния Хаусдорфа... 11
1.1. Метод сравнения объекта и эталона как простых множеств с помощью
модификаций расстояния Хаусдорфа ... 12
Основная идея метода ... 12
Обнаружение объекта, близкого к эталону, в присутствии шума ... 14
Алгоритм вычисления среднеквадратической модификации расстояния Хаусдорфа... 22
Поиск эталона путем полного сканирования с заданными шагами по размеру и углу ориентации эталона ... 24
1.2. Учет структуры контура при сравнении объекта и эталона с помощью
модификаций расстояния Хаусдорфа ... 27
Сравнение бинарных контурных изображений с учетом направлений обхода контурной цепи ... 28
Использование значимых областей для повышения помехоустойчивости ... 31
1.3. Низкоуровневые оптимизации алгоритма сравнения объекта и эталона по
взаимному отклонению контуров для процессоров архитектуры х8б ... 36
Преобразование координат точек импульсной характеристики в смещения ... 36
Использование набора машинных команд ММХ для оптимизации горизонтальных сегментов ... 37
Оптимизация горизонтальных и вертикальных сегментов с помощью накапливаемых сумм и ММХ ... 38
Сравнительное тестирование оптимизаций вычисления прямых бинарных корреляций ... 40
Выводы к главе 1 ... 44
2. Итеративная аппроксимация многоугольников по критерию максимума периметра ... 45
Задача полигональной аппроксимации ... 46
Принцип максимизации периметра аппроксимирующего многоугольника ... 50
Алгоритм максимального периметра (0(N4)) ... 55
Алгоритм треугольного слияния (0(N log N)) . . . 58
Алгоритм треугольного слияния по локальным минимумам (0(N) - 0(N log N)) . . . 61
2.6. Сравнение критериев максимума периметра и минимума погрешности в
алгоритмах полигональной аппроксимации ... 63
Сравнение критериев оптимизации в алгоритмах сложности 0(N4)... 63
Сравнение пригодности быстрых алгоритмов для локализации изломов ... 64
Сравнение по числовым критериям ... 66
Сравнение вычислительной сложности ... 71
2.7. Получение информации об изломах контура с помощью полигональных
аппроксимаций ... 72
2.7.1. Сравнительное тестирование ... 80
Выводы к главе 2 ... 84
3. Система распознавания номеров железнодоролшых цистерн с использованием быстрой локализации и сравнения объекта с эталоном по среднеквадратической модификации расстояния Хаусдорфа... 85
Постановка задачи ... 86
Программно-аппаратная структура системы регистрации и распознавания номеров железнодорожных цистерн ... 87
Описание площадки и аппаратной части системы технического зрения... 87
Программный комплекс системы технического зрения ... 89
ReportMaker - программа регистрации составов и распознавания номеров вагонов ... 90
ReportEditor - редактор отчетов о прохождении поездов ... 92
3.3. Технология распознавания номеров цистерн ... 96
Обзор проблем распознавания номеров и методов их решения ... 96
Вычисление локального контраста и локального порога для бинаризации ... 98
Локализация области номера ... 99
Поиск эталонов в области локализации ... 102
Обработка результатов сканирования ... 107
Оптимизации поиска эталонов . .. 108
Результаты... ПО
Выводы к главе 3 ... 111
Заключение ... 112
Библиографический указатель ... 113
Приложение. Акт о внедрении результатов кандидатской диссертационной работы ... 119
Введение к работе
Диссертация посвящена разработке методов обнаружения и анализа, объектов на бинарных контурных изображениях, выделяющихся из окружающего контекста благодаря своим геометрическим свойствам. Методы, рассматриваемые в диссертации, сводятся к измерениям геометрических расстояний между точками изображений. Исследуются два основных подхода к решению поставленной задачи - а) обнаружение с помощью модификаций расстояния Хаусдорфа объектов, геометрически близких к произвольным эталонам, задаваемым битовыми масками, и б) построение и анализ полигональных аппроксимаций контура объекта.
Актуальность проблемы. С начала эпохи цифровой обработки информации и до наших дней актуальной остается проблема распознавания изображений. Известно, что самая важная информация о форме содержится в контурах объектов. Многие объекты реального мира могут быть узнаны по изображениям их контуров, без использования исходных полутоновых изображений, поэтому алгоритмы распознавания чаще всего ориентированы на работу с контурными изображениями или бинарными изображениями, близкими к контурным (с толщиной линий много меньше размеров исследуемых особенностей).
Первый вопрос, исследовавшийся в диссертации - обнаружение на бинарных или контурных изображениях объектов, геометрически близких к произвольным эталонам (без каких-либо специальных ограничений формы), задаваемым битовыми масками. Существует несколько популярных подходов к решению задачи поиска эталонов. Самыми простыми являются алгоритмы поточечного сравнения эталонного и объектного изображений (например, простейший корреляционный метод [1,2, 3]). Данные алгоритмы удовлетворительно работают при сравнении широких полутоновых областей, при условии, что объектное изображение слабо зашумлено, а яркость и контраст эталона и объекта слабо отличаются. Однако поточечные алгоритмы крайне мало пригодны для распознавания контурных изображений, поскольку контура, как правило, являются узкими, и даже если формы контуров эталона и объекта похожи с точки зрения человека, из-за неточного совпадения пикселов алгоритм сочтет их непохожими.
К другой группе относятся алгоритмы, использующие инварианты, например, моментные [1, 10]. Достоинством данных алгоритмов является возможность быстрого расчета числовых характеристик, недостатком является то, что сложные объекты представляются небольшим набором чисел, часто не имеющих ясной геометрической интерпретации, и совершенно не похожие с точки зрения человека объекты могут иметь одинаковые значения инвариантов.
К третьей группе (самой популярной в настоящее время) относятся алгоритмы, использующие нейронные сети [4-8]. Недостатком их является то, что для настройки алгоритма требуется большая обучающая выборка, и даже при этом обычно удается удовлетворительно распознавать лишь изображения, очень близкие к тем, что использовались в обучающей выборке. При небольшом изменении геометрии входных изображений качество распознавания значительно падает.
В диссертации рассматривался четвертый подход, использующий модификации расстояния Хаусдорфа для сравнения взаимной близости множеств [11-16]. В этом подходе изображения рассматриваются или как простые множества точек в двумерном евклидовом пространстве, или как множества более сложных элементов, для этих множеств различными способами вычисляется некоторая мера взаимной близости, чаще всего используются геометрические расстояния между точками. Модификации расстояния Хаусдорфа в распознавании изображений используются с 1993 года, обладают интуитивно понятным принципом работы, явной связью с геометрией объектов и не требуют обучающей выборки, тем не менее, этот подход мало известен по сравнению с нейронными сетями, хотя в последние годы появляется все больше публикаций на эту тему [23-45].
Главным недостатком алгоритмов, использующих модификации расстояния Хаусдорфа, является высокая вычислительная сложность (в 2-3 раза выше, чем у простейших корреляционных алгоритмов), неинвариантность к повороту и масштабу, что при отсутствии априорной информации об ориентации и размерах распознаваемых объектов вынуждает использовать сканирование множеством вариантов эталона с разными углами поворота и масштабом, поэтому одной из актуальных проблем является разработка технологии оптимизации вычислений в данных алгоритмах.
Особенностью метода является возможность геометрического отсечения шума, окружающего объект, однако для решения этого вопроса не было предложено формальных правил, соответственно, актуальной проблемой является также формализация методики построения геометрических отсечений.
Область применения алгоритмов обнаружения эталонов ограничена главным образом распознаванием плоских искусственных объектов с фиксированной формой или с незначительными вариациями формы (типа машинописных шрифтов), в то время как большинство объектов реального мира не являются плоскими и имеют варьируемую форму, следовательно, могут эффективно распознаваться только методами структурного анализа. Поэтому еще одним актуальным направлением в распознавании образов является обнаружение структурных геометрических элементов изображений, и вторым вопросом, рассматриваемым в диссертации, был анализ геометрии контуров, представляемых в виде контурных цепей.
Большинство объектов реального мира можно отнести к каким-либо классам, причем объекты внутри класса различаются мелкими деталями
структуры, а объекты разных классов - крупными. Таким образом, чтобы классифицировать объект, необходимо найти его упрощенную модель, состоящую из одних крупных деталей.
Один из способов построения упрощенной модели плоского объекта со сложным контуром состоит в использовании особых точек контура и связей между этими точками, в частности, точками изломов. На сегодняшний день известно множество алгоритмов поиска изломов в замкнутых контурах [75-87], к недостаткам этих алгоритмов можно отнести сложности настройки параметров, а также неискоренимые ошибки — пропуск изломов и/или обнаружение ложных изломов. Вариация параметров увеличивает количество ошибок либо первого, либо второго рода. Связано это с тем, что, несмотря на кажущуюся очевидность понятия излома, нет строгого математического определения излома для контуров растровых изображений. Кроме того, многие объекты реального мира, хотя и обладают заметной человеческому глазу структурой, не содержат ярко выраженных изломов, и алгоритмы поиска изломов в принципе не могут давать для таких объектов хороших результатов.
Другой популярный подход к анализу формы контуров - аппроксимация фрагментов контура набором аналитических функций [1, 3, 89, 90]. Главной трудностью в реализации данного подхода является то, что реальные растровые контурные цепи часто не очень хорошо описываются ограниченным набором аналитических функций, кроме того, есть трудности использования разнородных кривых.
В диссертации рассматривается третий подход к построению упрощенных моделей контуров - аппроксимация контура многоугольником со сравнительно небольшим числом сторон, при этом ищутся не изломы, а некие узлы аппроксимации, наиболее важные для описания формы контура, а будут эти узлы с точки зрения человека похожи на изломы или нет - неважно.
Алгоритмы полигональной аппроксимации контуров традиционно решают одну из двух задач — минимизации ошибки аппроксимации при фиксированном числе узлов (min-s задача) или минимизации числа узлов при заданной максимально допустимой ошибке (min-# задача), главный недостаток этих алгоритмов - они могут неточно локализовывать даже явно заметные изломы контура, хотя человек предпочел бы расставить узлы аппроксимации по возможности в изломах. Представляется, что это связано главным образом с неудачным выбором критерия оптимизации, который, однако, был очевиден, и который можно было легко посчитать, а именно, минимизации погрешности аппроксимации. Требовалось найти другой критерий оптимизации, который был бы более ориентирован на локализацию изломов, в диссертации в качестве такого критерия исследовался максимум периметра аппроксимирующего многоугольника.
Цель работы: разработка методов обнаружения и анализа объектов на бинарных изображениях с использованием модификаций расстояния Хаус-дорфа и полигональной аппроксимации контуров.
Задачи работы:
Разработка информационной технологии обнаружения с помощью модификаций расстояния Хаусдорфа объектов на бинарных изображениях с высоким уровнем шума.
Разработка эффективных методов построения полигональных аппроксимаций контура объекта, оптимизируемых для наилучшей локализации изломов контура.
Разработка программного комплекса для распознавания номеров в системах технического зрения.
Научная новизна работы:
Разработана информационная технология обнаружения объектов на изображениях с высоким уровнем шума, сочетающая использование модификаций расстояния Хаусдорфа и близких к эталону значимых областей, формализована методика построения значимых областей.
Разработано две модификации алгоритмов итеративной аппроксимации замкнутых контурных цепей, использующие в качестве критерия оптимизации максимум периметра аппроксимирующего многоугольника.
Разработан оригинальный алгоритм слияния по локальным минимумам для итеративной аппроксимации замкнутых контурных цепей, использующий в качестве критерия оптимизации максимум периметра аппроксимирующего многоугольника.
На основе алгоритмов слияния и трех алгоритмов локализации изломов контура разработан метод получения оценки соответствия углов аппроксимирующего многоугольника и изломов контура, позволяющий обнаруживать тупые изломы контура с разной степенью детализации.
Практическая ценность результатов работы. Разработаны низкоуровневые технологические оптимизации вычисления модификаций расстояния Хаусдорфа, существенно повышающие скорость вычислений. Технология повышения помехоустойчивости может использоваться в реальных задачах обнаружения объектов. Алгоритмы итеративной аппроксимации многоугольников могут использоваться для выявления структурных геометрических элементов в широком спектре задач анализа контурных изображений. Программный комплекс системы технического зрения для распознавания номеров железнодорожных цистерн внедрен и успешно эксплуатируется с июня 2004 года на предприятии ООО «Самара-терминал», г. Сызрань.
Основные положения диссертации, выносимые на защиту:
Технология повышения помехоустойчивости обнаружения с помощью модификаций расстояния Хаусдорфа объектов, геометрически близких к эталонам, задаваемым битовыми масками.
Семейство алгоритмов итеративной аппроксимации многоугольников, использующих критерий максимума периметра.
Метод получения оценок соответствия углов аппроксимирующего многоугольника и изломов контура.
Программный комплекс системы технического зрения для распознавания номеров железнодорожных цистерн.
Реализация результатов работы. Технология применения значимых областей, оптимизации вычисления бинарно-целочисленных корреляций, алгоритмы итеративной аппроксимации и метод оценок соответствия углов и изломов применялись в задаче распознавания номеров железнодорожных цистерн.
Апробация работы. Основные результаты работы докладывались на следующих конференциях:
5-я международная конференция «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-5), Самара, 2000.
Международная конференция "Automation, Control and Information Technology", (ACIT-2002), Новосибирск, 2002.
7-я международная конференция «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-7), Санкт-Петербург, 2004.
6-ой всероссийский симпозиум по прикладной и промышленной математике, Сочи, октябрь 2005.
Всероссийский семинар по моделированию, дифракционной оптике и обработке изображений, Самара, июль 2006.
Публикации. По теме диссертации опубликовано 12 статей (из них 10 в изданиях, рекомендованных ВАК), 3 тезиса докладов на российских и международных конференциях и 1 свидетельство об официальной регистрации программ для ЭВМ.
Объем и структура диссертации. Диссертация состоит из 3 глав, изложена на 118 страницах, содержит 88 рисунков и библиографический указатель из 116 источников.
Похожие диссертации на Обнаружение и анализ объектов на бинарных изображениях с использованием модификаций расстояния Хаусдорфа и полигональной аппроксимации контуров
