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

• Хмелёв, Ростислав Викторович
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Хмелёв, Ростислав Викторович

Введение

Иерархия использовавшихся моделей и методов

1. Методы сравнения объекта и эталона с помощью модификаций расстояния Хаусдорфа.

1.1. Метод сравнения объекта и эталона как простых множеств с помощью модификаций расстояния Хаусдорфа

1.1.1. Основная идея метода

1.1.2. Обнаружение объекта, близкого к эталону, в присутствии шума

1.1.3. Алгоритм вычисления среднеквадратической модификации расстояния Хаусдорфа.

1.1.4. Поиск эталона путем полного сканирования с заданными шагами по размеру и углу ориентации эталона

1.2. Учет структуры контура при сравнении объекта и эталона с помощью модификаций расстояния Хаусдорфа

1.2.1. Сравнение бинарных контурных изображений с учетом направлений обхода контурной цепи

1.2.2. Использование значимых областей для повышения помехоустойчивости

1.3. Низкоуровневые оптимизации алгоритма сравнения объекта и эталона по взаимному отклонению контуров для процессоров архитектуры х

1.3.1. Преобразование координат точек импульсной характеристики в смещения

1.3.2. Использование набора машинных команд ММХ для оптимизации горизонтальных сегментов

1.3.3. Оптимизация горизонтальных и вертикальных сегментов с помощью накапливаемых сумм и ММХ

1.3.4. Сравнительное тестирование оптимизаций вычисления прямых бинарных корреляций

Выводы к главе

2. Итеративная аппроксимация многоугольников по критерию максимума периметра

2.1. Задача полигональной аппроксимации

2.2. Принцип максимизации периметра аппроксимирующего многоугольника

2.3. Алгоритм максимального периметра (0(N4)).

2.4. Алгоритм треугольного слияния (0(N log N)).

2.5. Алгоритм треугольного слияния по локальным минимумам (0(N) - 0(N log N)).

2.6. Сравнение критериев максимума периметра и минимума погрешности в алгоритмах полигональной аппроксимации

2.6.1. Сравнение критериев оптимизации в алгоритмах сложности 0(N4).

2.6.2. Сравнение пригодности быстрых алгоритмов для локализации изломов

2.6.3. Сравнение по числовым критериям

2.6.4. Сравнение вычислительной сложности

2.7. Получение информации об изломах контура с помощью полигональных аппроксимаций

2.7.1. Сравнительное тестирование

Выводы к главе

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

3.1. Постановка задачи

3.2. Программно-аппаратная структура системы регистрации и распознавания номеров железнодорожных цистерн

3.2.1. Описание площадки и аппаратной части системы технического зрения

3.2.2. Программный комплекс системы технического зрения

3.2.2.1. ReportMaker - программа регистрации составов и распознавания номеров вагонов

3.2.2.2. ReportEditor - редактор отчетов о прохождении поездов

3.3. Технология распознавания номеров цистерн

3.3.1. Обзор проблем распознавания номеров и методов их решения

3.3.2. Вычисление локального контраста и локального порога для бинаризации.

3.3.3. Локализация области номера

3.3.4. Поиск эталонов в области локализации

3.3.5. Обработка результатов сканирования

3.3.6. Оптимизации поиска эталонов

3.3.7. Результаты.

Выводы к главе 3 . 111 Заключение . 112 Библиографический указатель

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

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

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

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

К другой группе относятся алгоритмы, использующие инварианты, например, моментные [1, 10]. Достоинством данных алгоритмов является возможность быстрого расчета числовых характеристик, недостатком является то, что сложные объекты представляются небольшим набором чисел, часто не имеющих ясной геометрической интерпретации, и совершенно не похожие с точки зрения человека объекты могут иметь одинаковые значения инвариантов.

К третьей группе (самой популярной в настоящее время) относятся алгоритмы, использующие нейронные сети [4-8]. Недостатком их является то, что для настройки алгоритма требуется большая обучающая выборка, и даже при этом обычно удается удовлетворительно распознавать лишь изображения, очень близкие к тем, что использовались в обучающей выборке. При небольшом изменении геометрии входных изображений качество распознавания значительно падает.

В диссертации рассматривался четвертый подход, использующий модификации расстояния Хаусдорфа для сравнения взаимной близости множеств [11-16]. В этом подходе изображения рассматриваются или как простые множества точек в двумерном евклидовом пространстве, или как множества более сложных элементов, для этих множеств различными способами вычисляется некоторая мера взаимной близости, чаще всего используются геометрические расстояния между точками. Модификации расстояния Хаусдорфа в распознавании изображений используются с 1993 года, обладают интуитивно понятным принципом работы, явной связью с геометрией объектов и не требуют обучающей выборки, тем не менее, этот подход мало известен по сравнению с нейронными сетями, хотя в последние годы появляется все больше публикаций на эту тему [23-45].

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

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

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

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

Один из способов построения упрощенной модели плоского объекта со сложным контуром состоит в использовании особых точек контура и связей между этими точками, в частности, точками изломов. На сегодняшний день известно множество алгоритмов поиска изломов в замкнутых контурах [75-87], к недостаткам этих алгоритмов можно отнести сложности настройки параметров, а также неискоренимые ошибки — пропуск изломов и/или обнаружение ложных изломов. Вариация параметров увеличивает количество ошибок либо первого, либо второго рода. Связано это с тем, что, несмотря на кажущуюся очевидность понятия излома, нет строгого математического определения излома для контуров растровых изображений. Кроме того, многие объекты реального мира, хотя и обладают заметной человеческому глазу структурой, не содержат ярко выраженных изломов, и алгоритмы поиска изломов в принципе не могут давать для таких объектов хороших результатов.

Другой популярный подход к анализу формы контуров - аппроксимация фрагментов контура набором аналитических функций [1, 3, 89, 90]. Главной трудностью в реализации данного подхода является то, что реальные растровые контурные цепи часто не очень хорошо описываются ограниченным набором аналитических функций, кроме того, есть трудности использования разнородных кривых.

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

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

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

Задачи работы:

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

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

3. Разработка программного комплекса для распознавания номеров в системах технического зрения.

Научная новизна работы:

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

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

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

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

Практическая ценность результатов работы. Разработаны низкоуровневые технологические оптимизации вычисления модификаций расстояния Хаусдорфа, существенно повышающие скорость вычислений. Технология повышения помехоустойчивости может использоваться в реальных задачах обнаружения объектов. Алгоритмы итеративной аппроксимации многоугольников могут использоваться для выявления структурных геометрических элементов в широком спектре задач анализа контурных изображений. Программный комплекс системы технического зрения для распознавания номеров железнодорожных цистерн внедрен и успешно эксплуатируется с июня 2004 года на предприятии ООО «Самара-терминал», г. Сызрань.

Основные положения диссертации, выносимые на защиту:

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

2. Семейство алгоритмов итеративной аппроксимации многоугольников, использующих критерий максимума периметра.

3. Метод получения оценок соответствия углов аппроксимирующего многоугольника и изломов контура.

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

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

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

• 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 источников.

Иерархия использовавшихся моделей и методов

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

Полутоновые или полноцветные цифровые изображения

Бинарные изображения

Множества точек в двумерном евклидовом пространстве

Сравнение множеств с помощью модификаций расстояния Хаусдорфа

ГП

Бинарные контурные изображения

Набор множеств контурных точек с учетом направления обхода

Контурные многоугольники

Сравнение ориентированных контуров с помощью модификаций расстояния Хаусдорфа у---------------Y------У—

Модель значимой области фрагмента контура для геометрического отсечения шума vу

---N

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

Полигональная аппроксимация контурных цепей и многоугольников

У У

Полигональная аппроксимация многоугольников, ориентированная на локализацию выра

PHHhlX М7ППМПЯ

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

Оценка соответствия изломов контура и аппроксимирующих углов г

Модель сцены исходного изображения

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

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

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

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Хмелёв, Ростислав Викторович

Выводы к главе 3

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

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

3. Из трех протестированных низкоуровневых оптимизаций вычисления прямой бинарной корреляции (НогММХ16- 16-битная оптимизация ММХ, AccumLineSegl6 и AccumLineSeg32 - 16-и и 32-битная оптимизации с накапливаемыми суммами по строкам и столбцам) наилучший выигрыш по времени вычислений дала оптимизация AccumLineSegl6 - размеры сканируемых областей оказались наиболее подходящими именно для этой оптимизации. AccumLineSeg32 сильнее нагружает подсистему памяти, а НогММХ16 - блок арифметических вычислений процессора, в то время как AccumLineSegl6 дает наилучший баланс (в данной конкретной задаче).

4. Было протестировано четыре варианта вычисления взаимной близости объекта и эталона - а) по бинарным образам, б) по контурам без учета направлений, в) по контурам с учетом направлений и г) смешанная схема (контура с учетом направлений и бинарные образы). Наихудшие суммарные результаты показали бинарные образы; контура без учета направлений показали наихудшие результаты при распознавании «чистых» цистерн за счет влияния контуров соседних цифр; учет направлений лучше всего проявил себя при распознавании «умеренно грязных» изображений за счет использования узких значимых областей и лучшего отсечения шумов; смешанная схема выиграла при распознавании «чистых» изображений за счет меньшей чувствительности к геометрическим искажениям.

5. При распознавании некоторых шрифтов, в которых цифры «6» и «9» похожи на цифру «8», проявилось свойство помехоустойчивых модификаций расстояния Хаусдорфа игнорировать мелкие структурные особенности объектов, важные с точки зрения человека, что приводит к ошибкам распознавания.

Заключение

В диссертации получены следующие основные результаты:

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

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

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

4. Разработана автоматизированная система технического зрения с комплексом программ для распознавания номеров железнодорожных цистерн. Основным методом распознавания в системе является вариант среднеквадратической модификации расстояния Хаусдорфа, в котором отклонение эталона от объекта вычисляется по контурной цепи с учетом ориентации, а отклонение объекта от эталона - по бинарному образу. Вспомогательным методом обнаружения области номера является процедура быстрой локализации, использующая цветовой контраст и поиск выраженных изломов контура. Система повышает удобство и оперативность ввода информации о входящих поездах, и встроена в технологический цикл работы нефтебазы ООО «Самара-терминал», г. Сызрань.

Список литературы диссертационного исследования кандидат технических наук Хмелёв, Ростислав Викторович, 2009 год

1.ДудаР., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976

2. ТуДэ/с., Гонсапес Р. Принципы распознавания образов. М.: Мир, 1978. - 412 с.

3. Методы компьютерной обработки изображений. // под ред. Сойфера В.А. М.: ФИЗ-МАТЛИТ, 2001.-784 с.

4. S. Haykin. Neural Networks: A Comprehensive Foundation // МасМШап College Publishing Co., New York, 1994.

5. Нейронные сети: история развития теории // под ред. А.И. Галушкина, Я.З. Цыпкина. — М.: ИПРЖР, 2001 -840 с.

6. Нейрокомпьютеры в системах обработки изображений. Кн. 7: Коллективная монография // Общая ред. А. И. Галушкина. М.: Радиотехника, 2003. - 192 с.

7. Осовский С. Нейронные сети для обработки информации // Пер. с польского И.Д. Ру-динского. М.: Финансы и статистика, 2002. - 344 с.

8. Шустов В.А. Ускорение обучения нейронной сети с отбором обучающих примеров // Сб. науч. тр. // Институт систем обработка изобраэ/сений РАН. — 2002. Вып. 24. - С. 160- 163.

9. М. Шлезингер, В. Главач. Десять лекций по статистическому и структурному распознаванию // Киев, Наукова думка, 2004. 536 с.

10. Глумов Н.И. Построение и применение моментных инвариантов для обработки изображений в скользящем окне // Компьютерная оптика N° 14-15, ч.1, 1995, с. 46-54

11. Huttenlocher D.P., Klanderman G.A., Ruckligde W.J. Comparing images using the Hausdorff-distance // IEEE Transactions on pattern Analysis and machine Intelligence, 1993. Vol. 15. P. 850-863.

12. Olson C.F., Huttenlocher D.P. Automatic Target Recognition by Matching Oriented Edge Pixels, IEEE Transactions on Image Processing, vol. 6, no. 1, pp. 103-113, 1997 (with C.).

13. Huttenlocher D., Lilien R„ Olson C. Object Recognition Using Subspace Methods // IEEE Trans, on Pattern Analysis and Machine Intelligence, vol. 21, no. 9, pp. 951-956, 1999.

14. A. Ruckligde W.J. Efficiently Locating Objects Using the Hausdorff Distance // International Journal of Computer Vision 24(3), 251-270, 1997

15. H.JI. Казанский, P.B. Хмелев. Сравнение объекта и эталона по отклонению контуров // Компьютерная оптика №20,2000. с. 134-139

16. Khmelyoff R.V. Comparison of Standard and Object by Contour Deviation // Новосибирск, Proceedings of the IASTED International Conference ACIT-2002, c. 549-554.

17. M.P. Dubuisson, A.K. Jain. A modified Hausdorff distance for object matching // In: Conference A: Computer Vision & Image Process., Proc. 12th IAPR Internat. Conf on 9-13 October 1, 1994. Pattern Recogn. 1, 566-568.

18. J. Paumard, E. Aubourg. Adjusting astronomical images using a censored Hausdorff distance // In: Proc. Internat. Conf Image Process., on 26-29 October 3, 1997, 3, 232-235.

19. D.G. Sim, O.K. Kwon, R.H. Park. Object matching algorithms using robust Hausdorff distance measures // IEEE Trans. Image Process., 1999, 8 (3), 425-429.

20. Y.R. Tsai. Rapid and Accurate Computation of the Distance Function Using Grids // Technical report, Department of Mathematics, University of California, Los Angeles, 2000.

21. F. Leymarie and M. D. Levine. Simulating the Grassfire Transform Using an Active Contour Model // IEEE-PAMI, Vol. 14(1), pp. 56-75, Jan. 1992.

22. Felzenszwalb P.F., Huttenlocher D.P. Distance Transforms of Sampled Functions // Cornell Computing and Information Science Technical Report TR2004-1963, 2004.

23. Alhichiri H.S., Kamel. M. Multi-resolution image registration using multi-class Hausdorff fraction // Pattern Recognition Letters 23 (2002), pp. 279-286.

24. Alhichiri H.S., Kamel. M. Virtual circles: a new set of features for fast image registration // Pattern Recognition Letters 24 (2003), pp. 1181 -1190.

25. Yongsheng Gao, Maylor K.H. Leung. Line segment Hausdorff distance on face matching // Pattern Recognition 35 (2002), pp. 361-371.

26. Jingying Chen, Maylor К Leung, Yongsheng Gao. Noisy logo recognition using line segment Hausdorff distance // Pattern Recognition 36 (2003), pp. 943-955.

27. Ioannis Fudos, Leonidas Palios. An efficient shape-based approach to image retrieval // Pattern Recognition Letters 23 (2002), pp. 731-741.

28. Concettina Guerra, Valerio Pascucci. Line-based object recognition using Hausdorff distance: from range images to molecular secondary structures // Image and Vision Computing 23 (2005), pp. 405-415.

29. Baofeng Guo, Kin-Man Lam, Kwan-Ho Lin, Wan-Chi Sin. Human face recognition based on spatially weighted Hausdorff distance // Pattern Recognition Letters 24 (2003), pp. 499-507.

30. Kwan-Ho Lin, Kin-Man Lam, Wan-Chi Silt. Spatially eigen-weighted Hausdorff distances for human face recognition // Pattern Recognition 36 (2003) pp. 1827 1834.

31. Benoit Huet, Edwin R. Hancock. Relational object recognition from large structural libraries // Pattern Recognition 35 (2002), pp. 1895-1915.

32. Sukhamay Kundu. Conflating two polygonal lines // Pattern Recognition 39 (2006) pp. 363-372.

33. Oh-Kyu Kwon, Dong-Gyu Sim, Rae-Hong Park. Robust Hausdorff distance matching algorithms using pyramidal structures // Pattern Recognition 34 (2001) pp. 2005-2013.

34. Sang-Cheol Park, Sung-Hoon Lim, Bong-Kee Sin, Seong-Whan Lee. Tracking non-rigid objects using probabilistic Hausdorff distance matching // Pattern Recognition 38 (2005) pp. 2373-2384.

35. Yue Lu, Chew Lim Tan. Document retrieval from compressed images // Pattern Recognition 36 (2003) pp. 987 996.

36. Carlos Orrite and J. Elias Herrero. Shape matching of partially occluded curves invariant under projective transformation // Computer Vision and Image Understanding 93 (2004), pp. 34-64.

37. Xiaoming Peng, Mingyue Ding, Chengping Zhou, Qian Ma. A practical two-step image registration method for two-dimensional images // Information Fusion 5 (2004) pp. 283-298.

38. Ediz Polat, Mohammed Yeasin, Rajeev Sharma. A 2D/3D model-based object tracking framework // Pattern Recognition 36 (2003) pp. 2127-2141.

39. Peer Stelldinger, Ullrich Kothe. Towards a general sampling theory for shape preservation // Image and Vision Computing 23 (2005) pp. 237-248.

40. Vivek A. Sujan, Michael P. Mulqueen. Fingerprint identification using space invariant transforms // Pattern Recognition Letters 23 (2002) pp. 609-619.

41. Zhenfeng Zhu, Ming Tang, Hanqing Lu. A new robust circular Gabor based object matching by using weighted Hausdorff distance // Pattern Recognition Letters 25 (2004), 515523

42. Yingjie Wang, Chin-Seng Chua. Face recognition from 2D and 3D images using 3D Gabor filters // Image and Vision Computing 23 (2005) pp. 1018-1028.

43. Yingjie Wang, Chin-Seng Chua. Robust face recognition from 2D and 3D images using structural Hausdorff distance // Image and Vision Computing 24 (2006) pp. 176-185.

44. Chunjiang Zhao, Wenkang Shi, Yong Deng. A new Hausdorff distance for image matching // Pattern Recognition Letters 26 (2005) pp. 581-586.

45. Jindan Zhou, Mohamed Abdel-Mollaleb. A content-based system for human identification based on bitewing dental X-ray images // Pattern Recognition 38 (2005) pp. 2132-2142.

46. H.JI. Казанский, В.В. Мясников, Р.В. Хмелев. Алгоритмы поиска расстояний до объектных пикселов на бинарных изображениях // Компьютерная оптика Ш 20,2000. с. 128133

47. Е. Thiel, A. Montanvert. Chamfer masks: Discrete distance functions, geometric properties and optimization // in Proc. 11th Int. Conf. Pattern Recognition, The Hague, The Netherlands, Apr. 1992, pp. 244-247.

48. D.E. Johnson andE. Cohen. A Framework for Efficient Minimum Distance Computations // In Proc. IEEE Intl. Conf. Robotics & Automation, Leuven, Belgium, pp. 3678-3684, May 1998.

49. L. Shapiro, J.M. Brady. Feature-based correspondence: an eigenvector approach // Image and Vision Computing 10 (5) (1992), 283-288.

50. S. Osher and J.A. Sethian. Fronts Propagating with Curvature-Dependent Speed: Algorithms Based on Hamilton-Jacobi Formulations // Journal of Computational Physics, 79:12-49, 1988.

51. C.B. Волотовский, H.JI. Казанский, С.Б. Попов, Р.В. Хмелев. Система технического зрения для распознавания номеров железнодорожных цистерн с использованием модифицированного коррелятора в метрике Хаусдорфа. // Компьютерная оптика № 27, 2005.

52. Mikhlyaev S. V. Relaxation technique for stereo images matching // Proceedings of the IASTED international conference AC1T-2002, p. 376-381

53. Хмелев Р.В. Поиск впадин в замкнутом невыпуклом контуре // Компьютерная оптика №24, 2002. -с. 164-172.

54. Sklansky J., Gonzalez V. Fast polygonal approximation of digitized curves // Pattern Recognition, 12: 327-331, 1980.

55. Zhao Z, SaalfeldA. A linear-time sleeve-fitting polyline simplification algorithms // Proc. 13,hint. Conf. AutoCarto, ACSM/ASPRS'97 Technical Papers, 5: 214-223, 1997.

56. Kurozumi Y., Davis W.A. Polygonal approximation by the minimax method // Computer Vision, Graphics and Image Processing, 19: 248-264, 1982.

57. Ray B.K., Ray K.S. A non-parametric sequential method for polygonal approximation of digital curves // Pattern Recognition Letters, 15: 161-167, 1994.

58. Gritzali E, Papakonstantinou G. A fast piecewise linear approximation algorithm // Signal Processing, 5: 221-227, 1983.

59. Aoyama H., Kawagoe M. A piecewise linear approximation method preserving visual feature points of original figures // Computer Vision, Graphics and Image Process.: Graphical Models and Image Process, 53: 435-446, 1991.

60. Douglas D.H., Peucker Т.К. Algorithm for the reduction of the number of points required to represent a line or its caricature // The Canadian Cartographer, 10 (2): 112-122, 1973.

61. Ramer U. An iterative procedure for polygonal approximation of plane curves // Computer Graphics and Image Processing, 1: 244-256, 1972.

62. Hershberger J., SnoeyinkJ. Speeding up the Douglas-Peucker line simplification algorithm // Proc. 5th Int. Symp. on Spatial Data Handling, 134-143, 1992.

63. Hershberger J., Snoeyink J. An О(n log n) implementation of the Douglas-Peucker algorithm for line simplification // Proc. 10th Annu. ACM Symp. On Comput. Geom., 383-384, 1994.

64. Leu J.G., Chen L. Polygonal approximation of 2d shapes through boundary merging // Pattern Recognition Letters, 7(4): 231-238, 1988.

65. Latecki L.J., Lakamper R. Convexity rule for shape decomposition based on discrete contour evolution // Computer Vision and Image Understanding, 73: 441-454, 1999.

66. Ku K.M., Chiu K.M. Polygonal approximation of digital curve by graduate iterative merging // Electronics Letters, 31: 444-446, 1995.

67. Fahn C.-S., WangJ.-E, Lee J.-Y. An adaptive reduction procedure for the piecewise linear approximation of digitized curves // IEEE Trans. Pattern Analysis and Machine Intelligence, 11: 967-973, 1989.

68. Wu J.-S., Leou J.-J. New polygonal approximation schemes for object shape representation // Pattern Recognition, 26: 471-484, 1993.

69. Boxer L., Chang C.-S., Miller R., Rau-Chaplin A. Polygonal approximation by boundary reduction // Pattern Recognition Letters, 14: 111-119, 1993.

70. Visvalingam M., Whyatt J. Line generalization by repeated elimination of points // Cartographic Journal, 30(1): 46-51, 1993.

71. Pikaz A., Dinstein I. An algorithm for polygonal approximation based on iterative point elimination // Pattern Recognition Letters, 16 (6): 557-563, 1995.

72. Pavlidis Т., Horovitz S.L. Segmentation of plane curves // IEEE Trans. Computers, 23(8): 860-870, 1974.

73. Wu J.-S., Leou J.-J. New polygonal approximation schemes for object shape representation // Pattern Recognition, 26: 471-484, 1993.

74. Park R.-H., Jee Y.H. Multistep polygonal approximation // J. Electronic Imaging, 3(3): 232-244, 1994.

75. H. Asada and M. Brady. The curvature primal sketch. // IEEE Trans. Pattern Analysis and Machine Intelligence, 8:2-14, 1986.

76. H.L. Beus and S.S.H. Tiu. An improved comer detection algorithm based on chain-coded plane curves. // Pattern Recognition, 20:291-296, 1987.

77. H. Freeman and L.S. Davis. A comer finding algorithm for chain-coded curves. // IEEE Trans. Computers, 26:297-303, 1977.

78. H.-C. Liu and M.D. Srinath. Corner detection from chain-code. // Pattern Recognition, 23:51-68, 1990.

79. A. Rosenfeld and E. Johnston. Angle detection on digital curves. // IEEE Trans. Computers, 22:875-878, 1973.

80. A. Rosenfeld andJ.S. Weszka. An improved method of angle detection on digital curves. // IEEE Trans. Computers, 24:940-941, 1975.

81. B. Kruse and С. V. K. Rao. A matched filtering technique for corner detection // 4th Int. Joint Conf. Pattern Recognition, Kyoto, Japan, 642-644 (1978).

82. M. A. Fischler and R. C. Bolles. Perceptual organization and curve partitioning // IEEE Trans. Pattern Analysis Mack Intell. PAMI-8, 100-105 (1986).

83. С. H. Teh, and R. T. Chin. On the detection of dominant points on digital curves // IEEE Trans. Pattern Analysis Mach Intell. PAMI-11, 859-872 (1989).

84. Ansari N., Delp E.J. On detecting dominant points // Pattern Recognition, 24:441-450, 1991.

85. S.-C. Pei and J.-H Horng. Corner point detection using nest moving averages // Pattern Recognition 27, 1533-1537 (1994).

86. F. Mokhtarian and A.K. Mackworth. A theory of multiscale, curvature-based shape representation for planar curves. // IEEE Trans. Pattern Analysis and Machine Intelligence, 14:789-805, 1992.

87. F. Mokhtarian. Automatic Spline Fitting of Digital Contours at Multiple Scales // Proc. Eurographics-2000 and Proc. ICASSP-2000.

88. Y.J. Ahn. Conic approximation of planar curves // Computer Aided Design 33, 2001, 867872.

89. Введение в контурный анализ // под ред. Фурмана Я.А. М.: ФИЗМАТЛИТ, 2002. - 592 с.

90. Kolesnikov A., Frtinti P. Reduced-search dynamic programming for approximation of polygonal curves // Pattern Recognition Letters, 24(14): 2243-2254, 2003.

91. Vallone U. Bidemensional shapes polygonalization by ACO // Proc. 3rd Int. Workshop on Ants Algorithms, Brussels, Belgium, pp. 296-297, September 2002.

92. Tin P.-Y. Ant colony search algorithms for optimal approximation of plane curve // Pattern Recognition, 36(8): 1783-1797, 2003.

93. Dorigo N. Optimization, Learning, and Natural Algorithms // PhD Thesis, Dip. Elettronica e Informazione, Politecnico di Milano, Italia, 1992.

94. Dorigo M., G. Di Саго & L. M. Gambardella. Ant Algorithms for Discrete Optimization // Artificial Life, 1999 5(2): 137-172.

95. Tin P.-Y. Genetic algorithms for polygonal approximation of digital curves, // Int. J. Pattern Recognition and Artificial Intelligence 13:1061-1082, 1999

96. Huang S.-C., Sim Y.-N. Polygonal approximation using genetic algorithms // Pattern Recognition, 32: 1409-1420, 1999.

97. Recatala G., IhestaJ.M. Polygonal approximation through genetic algorithms // Proc. 11th Scandinavian Conf on Image Analysis, pp. 707-714, June 1999.

98. Ho S.-Y., Chen Y.-C. An efficient evolutionary algorithm for accurate polygonal approximation // Pattern Recognition, 34: 2305-2317, 2001.

99. Katsaggelos A.K., Kondi L.P., Meier F.W., Oslerman J., Schuster G.M. MPEG-4 and rate-distortion-based shape-coding techniques // Proc. of IEEE, 86(6): 1126-1154, 1998.

100. Chung J-W., Lee J.-H., Moon J.-H., Kim J.-K. A new vertex-based binary shape coder for high coding efficiency // Signal Processing: Image Communications, 15: 655-684, 2000.

101. Yun B.-J., Lee S.-W., Kim S.-D. Vertex adjustment method using a geometric constraint for polygon-based shape coding // Electronic Letters, 37 (9): 754-755, 2001.

102. Stone H. Approximation of curves by line segments // Math. Comput., 15: 40-47, 1961.

103. Bellman R. Dynamic Programming // Princeton University Press, New Jersey, 1957.

104. Bellman R. On the approximation of curves by line segments using dynamic programming // Comm. ACM, 4(6): 284, 1961.

105. Gluss B. Further remarks on line segment curve-fitting using dynamic programming // Comm. ACM, 5: 441-443, 1962.

106. Cox M.G. Curve fitting with piecewise polynomials // J. Inst. Math. Appl., 8: 36-52, 1971.

107. Cantoni A. Optimal curve fitting approximation with piecewise linear functions // IEEE Trans. Computers, 20: 54-67, 1971.

108. A M. N. Fu, H. Yan, and K. Huang. A curve bend function based method to characterize contour shapes // Pattern Recognition 30, 1661-1671 (1997).

109. У. M. Inesta, M. Baendia and M. A. Sart. Reliable polygonal approximations of imaged real objects through dominant point detection // Pattern Recognition 31, 685-697 (1998).

110. Vincent Beau, Mark Singer. Reduced resolution and scale space for dominant feature detection in contours // Pattern Recognition 34(2), pp. 287-297 (2001).

111. L. B. Kara and T. F. Stahovich. An image-based, trainable symbol recognizer for hand-drawn sketches // Computers & Graphics, Volume 29, Issue 4, August 2005, pp. 501-517.

112. C. Gope and N. Kehtarnavaz. Affine invariant comparison of point-sets using convex hulls and hausdorff distances // Pattern Recognition, Volume 40, Issue 1, January 2007, pp. 309-320.

113. Prosenjit Bose, Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc van Kreveld and Bettina Speckmann. Area-preserving approximations of polygonal paths // Journal of Discrete Algorithms, Volume 4, Issue 4, December 2006, pp. 554-566.

114. Yong Chen. An accurate sampling-based method for approximating geometry // Computer-Aided Design, Volume 39, Issue 11, November 2007, pp. 975-986.4

115. НЕФТЯНАЯ КОМПАНИЯ «ЮКОС» Общество с ограниченной ответственность «САМАРА-ТЕРМИНАЛ»

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

117. СТЗ находится в эксплуатации с мая 2004 года, обеспечивает правильное распознавание порядка 84% номеров, с ее помощью удалось добиться существенного ускорения и увеличения удобства обработки данных о составах цистерн.

118. Председатель комиссии: Гл.метролог Члены комиссии: Гл.механик

119. Гл.специалист по нефтебазному хозяйст^-—£1. С.П.Бадаев

120. В.В.Митрофанов .С.Арифуллин