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

На правах рукописи

ХМЕЛЕВ Ростислав Викторович

00346425Э

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

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата технических наук

САМАРА-2009

003464259

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ им. академика С.П. Королева и в Учреждении Российской академии наук ИНСТИТУТ СИСТЕМ ОБРАБОТКИ ИЗОБРАЖЕНИЙ РАН (г. Самара)

Научный руководитель: доктор физико-математических наук,

профессор Казанский Николай Львович

Официальные оппоненты: доктор технических наук, профессор

Кузнецов Павел Константинович

кандидат технических наук, доцент Гашников Михаил Валерьевич

Ведущая организация: ГОУ ВПО Уфимский государственный

авиационный технический университет

Защита состоится 27 марта 2009 г. в 12 часов

на заседании диссертационного совета Д 212.215.05, созданного при ГОУВПО Самарский государственный аэрокосмический университет имени академика С.П. Королева

по адресу: 443086, Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО Самарский государственный аэрокосмический университет имени академика С.П. Королева

Автореферат разослан 25 февраля 2009 г.

Ученый секретарь

диссертационного совета, Qj&Jf)

д.т.н., профессор Калентьев A.A.

Общая характеристика работы

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

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

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

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

Большинство объектов реального мира можно отнести к каким-либо классам, причем объекты внутри класса различаются мелкими деталями, а объекты разных классов - крупными, чтобы классифицировать объект, нужно построить его упрощенную модель, состоящую только из крупных деталей. Существует несколько популярных подходов к построению упрощенных моделей контуров, например, основанные на поиске изломов в контуре (Розенфельд, 1973), на аппроксимации фрагментов контура аналитическими кривыми (Хох, 1962, Розенфельд, 1969, Дуда, Харт, 1972) и полигональной аппроксимации (Рэймер, 1972;

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

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

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

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

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

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

В пункте 1.1 описан базовый принцип сравнения объекта и эталона с помощью модификаций расстояния Хаусдорфа (для множеств А и Z): H(A,Z) = max(h(A,Z), h(Z,A)), где h(A,Z) = maxp(a,Z) - направленное pac-

ae А

стояние Хаусдорфа от множества А до множества Z, а

p(a, Z) = min p(a, z) - расстояние от точки до множества. Данный принцип в об-

ЛЕ 7.

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

¡TW1

использовалась среднеквадратическая модификация: h„(A,z}= r-¡¿ p2(a¡.Z).

У|А| „о

Рис. 1. а) Эталон, б) Объект, в) Совмещение объекта и эталона (совпадающие точки черные), каждой точке объекта поставлена в соответствие ближайшая к ней точка эталона (отношения соответствия обозначены линиями, кроме совпадающих точек), г) Каждой точке эталона поставлена в соответствие ближайшая к ней точка объекта.

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

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

Сходство фрагмента объектного изображения с шумом обнаруживается по близости Cr (с.к. отклонение части объекта, попавшей в значимую область шириной R) к с. к. отклонению равномерного случайного распределения на отрезке [-R, R]: op=R N3 , а формула признака имеет вид d(oR,R)= 1- aR/ap = 1- <trV3/R.

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

О}) 62) (Ii)

Рис. 2. а и) Эталон и его фрагмент. 61.2) Объектное изображение и его фрагмент, в и) Шумовое изображение и его фрагмент.

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

В пункте 1.2 описывается модификация алгоритма сравнения объекта и эталона но взаимному отклонению, учитывающая направления обхода контуров и допускающая привязку контурных точек одного множества только к близким по направлению обхода контурным точкам другого множества, что повышает точность и надежность распознавания (Олсон, Хатгенлохер, 1997). Для повышения помехоустойчивости этого модифицированного алгоритма в диссертации была предложена модификация технологии значимых областей эталона, описанной в пункте 1.1. В модификации значимые области строятся также с учетом направлений обхода - для каждого эталона используется восемь значимых областей, каждая из которых строится вокруг пикселов эталона с тремя смежными направлениями нормалей к контуру, определяемых таблично по двухшаговым переходам цепи (рис. За), при этом точки объектного контура с каждым из восьми возможных вариантов нормали (рис. 36) учитываются только если попадают в соответствующую значимую область, в противном случае игнорируются.

Рис. 3. ais) Значимые области эталона (светло-серые), строящиеся вокруг пикселов с тремя смежными

направлениями нормали (черные).

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

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

Рис. 4. Графики ошибок классификации в тесте обнаружения символов шрифта Arial с помощью ориентир, и неориентир, значимых областей и с.к. признака локального увеличения плотности. Абсцисса - пороговое значение d, ордината - процент ошибок. Шум - кружки диаметром б пикселов со случайными координатами центров, среднее отношение сигнал / шум -3,94 дБ. Кривая пропуска символов без учета направлений Кривая ложных обнаружений символов без учета направлений Кривая пропуска символов с учётом направлений

Кривая ложных обнаружений символов с учетом направлений не показана (везде 0).

® /У и I__' J® /У // GTjj ч/ и 1—J 1

а,) а:) а,) а4) а,) аб) a?) as)

ffl о е ■'/ 7 G / о у 0 у ;.:; © / i о /

б,) б¡) б3) б,) 6¡) б,) б,) б,)

тггг-гггтп

in ю rv аэ ei о Ö O Ö Q Ö

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

В оптимизациях с накапливаемыми суммами для матрицы преобразования расстояния объектного изображения А(ш,п) m=0,..,M-l, n=0,..,N-l создаются матрицы горизонтальных и вертикальных накапливаемых сумм -

m ч

Sh(m,n) = X A(i,n) и sv(m,n)= £ A(m,j); с помощью которых для горизонтального

¡.О fO

и вертикального сегмента любой длины можно найти сумму элементов в одно

л2 П;

действие: I A(i,n)= Sjm2,n)-Sh(m,- 1,п] Д A(m,j) = Sv(m,nJ-Sv(m,n,-l).

i-m, >n(

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

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

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

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

С помощью максимизации периметра можно находить близкое к истинному положение углов в растровых представлениях многоугольников (рис. 5).

Рис. 5. а) Многоугольник Р и его растровое представление, многоугольник R. б) Поиск вершин многоугольника Р в его растровом представлении R с помощью вариации вершин аппроксимирующего многоугольника А, для которого следует добиться максимума периметра.

На основе принципа максимизации периметра было разработано три алгоритма со сложностью 0(N4), 0(N log N) и 0(N)-0(N log N), где N число вершин исходного многоугольника, первые два являются модификациями и отличаются от ранее известных критерием оптимизации, третий - оригинальный. Первый алгоритм, называемый «алгоритм максимального периметра» (пункт 2.3), дает истинный максимум периметра для каждого возможного количества узлов аппроксимации от 2 до N-1, при условии, что узлы аппроксимации лежат на контуре исходного N-уголышка. Как показали тесты, данный алгоритм дает самую субъективно хорошую аппроксимацию заданным числом узлов (т. е. наиболее адекватно описывающую форму объекта), даже если явно выраженных изломов в контуре нет (рис. 6).

Рис. 6. Примеры работы алгоритма максимального периметра. Вверху - контур окружности, аппроксимируемой 3,4, 5 и 6узлами. Внизу — контур буквы «У», аппроксимируемый 4, 5, 6и9 узлами.

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

Рис. 7. Важность узла А (Ба) выражается через неравенство треугольника:

8А = Ь + с-а>0.

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

о

Рис. 8. Результаты работы алгоритма треугольного слияния для растровой окружности (3, 4, 5, 6 узлов) и контура буквы «У» (4, 5, 6, и 9узлов).

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

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

Таблица 1. Статистика выигрышей (ШЗ) и проигрышей (О) по целевым числовым критериям. ТО - процент выигрышей треугольного слияния по глобальным минимумам

МО - процент выигрышей минимаксного слияния по глобальным минимумам ПО - процент выигрышей среднеквадратич. слияния по глобальным минимумам Ед - процент одинаковых результатов (Ш)

Длша периметра Еср 2Ч®%

Мака погрешность

12

%

С.к. погрешность

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

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

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

В пункте 2.7 предложен метод вычисления соответствия изломов контура аппроксимирующим углам. Основными отличиями от известных методов анализа контурных цепей являются, во-первых, соединение технологии полигональной аппроксимации с технологией обнаружения изломов, во-вторых, принципиально другая постановка задачи, а именно, не обнаружение изломов (т.е., получение бинарного ответа, где есть излом, а где нет), а нахождение меры соответствия изломов и аппроксимирующих углов. От большинства алгоритмов поиска изломов данная технология принципиально отличается, во-первых, тем, что не игнорирует тупые изломы контура, во-вторых, тем, что количество анализируемых изломов не зависит от произвольно выбираемых параметров (всегда 2Ы-4, где М- число поворотов при обходе контурной цепи).

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

Рис. 9. Для каждого фрагмента контура АС1С1В вычисляются максимумы отклонения в обе стороны от аппроксимирующей хорды (¡г1 и И; в точках С/ и С2 соответственно), по максимумам отклонения и хорде определяются оценочные окружности и четыре касательные /, в точках А и В.

Рис. 10. (Х- аппроксимирующий угол, в узле аппроксимации В имеем четыре угла Д между касательными к оценочным окружностям и аппроксимирующими хордами АВ и ВС:

тс-а я- а-2шах(р,,р4)

г с

С,

л- а+ 2шах(р2,р,)

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

н

а,) а г) а,) б,) б2) в,) в

Рис. 11. Примеры вычисления соответствия излома контура аппроксимирующему углу. Кружки -узлы аппроксимации, числа - значения соответствия р

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

Метод оценок соответствия сравнивался с алгоритмом Бо-Сингера (2001) в задаче локализации выраженных изломов в растровых представлениях многоугольников. Оба метода показали почти идентичные результаты локализации (положение обнаруженных изломов различается не более чем на один пиксел) и близкие значения времени вычислений: Бо-Сингер- 100%, метод оценок с алгоритмом треугольного слияния по локальным минимумам - 55% (лучший), метод оценок с алгоритмом треугольного слияния- 161%. Однако более принципиальна разница в том, что метод оценок дает более конкретную информацию о характере локализованных особенностей контура.

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

В пункте 3,1 описывается задача системы - максимально быстрое получение информации о цистернах (рис. 12) и передача данных в систему контроля верхнего уровня. Из-за сильного загрязнения многих цистерн задача стопроцентного автоматического распознавания не ставилась, требовалось лишь максимально увеличить количество распознанных номеров.

Рис. 12. Информация о цистерне: восьмизначный номер, тип (62) и код принадлежности стране (20). Номер распознается автоматически (если удается), тип и код принадлежности берутся из базы данных по вагонам.

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

1 - железнодорожные пути; 2а, 26 - видеокамеры; За, 36-блоки питания камер; 4а, 4б - фоновые щиты; 5а, 56 - ночная подсветка фоновых щитов; 6а, 66- ночная боковая подсветка поезда; 7а. 76 - сигнальный кабель от видеокамеры к компьютеру;

8 - компьютер, управляющий камерами и формирующий отчеты о поездах;

9 - локальная компьютерная сеть;

10 - компьютер оператора для просмотра и редактирования отчетов

Рис. 13. Аппаратная схема си- 0 поездах;

11а, 116 - питание осветителей на щитах; стемы технического зрения |2 _ выключатели питания для камер и освещения (-220 В).

Площадка видеонаблюдения

и »маеод»мны« упраеЛ«пие Л

Генератор отчетов

Модуль управления вводом

Модуль распознавания

Программный комплекс управления системой (рис. 14) состоит из двух программ: а) генератор отчетов - программа, устанавливаемая на компьютере (8), управляет камерами, осуществляет запись и распознавание поездов и создание отчетов распознавания; б) редактор отчетов - стандартная \Vindows-npo-грамма просмотра и редактирования отчетов, устанавливаемая на компьютере (10), передает отчеты в вышестоящую систему.

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

Управление камерами

Записч поезда * разбиение на вагоны

Локализация области мкаекса!

Сканирование »талом*

I Про»*р<» структуры инде*

Исправленный отчет (в систему контроля мрхиетоуроеняу

И

Проверка результатов распознавания, редактирование базы данных

Редактор отчетов

м

г/

База данных дополнительной информации о вагонах

Рис. 14. Структурная схема программного комплекса системы технического зрения

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

1 - общая информация по отчету;

2 — список вагонов;

3 - поля редактирования данных; 4а, 46 - изображения вагонов от первой и второй камер;

5 — управление просмотром изображений для текущего вагона;

6 - заголовок редактора и главное меню.

Рис. 15. Интерфейс редактора отчетов

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

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

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

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

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

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

В лабораторных тестах вагоны распознавались с одной стороны (таблица 2). Среди «чистых» цистерн правильно распознается 96,0 % номеров, среди «умеренно грязных» - 69,7%, среди «грязных» - 14,6%, всего - 75,1 %. Часть результатов помечается признаком недостоверности.

Таблица 2. Результаты распознавания тестовой выборки

Группа - «1И- «умерен? «о гряшыс» «грязные

етыо» . »

Нсего цистерн 426 271 123

Распознано ВЕРНО, 409- 189 18

шннх с призшком:

Достоверно 247 54 3

Недостоверно 162 135 15

Отказ 0 0 0

Распознано НЕВЕР-

НО, ит них с призна- 11 82 105 ' -

ком;

Достоверно 0 0 0

Недостоверно 6 27 17

Отказ 11 55 88

Сентябрь 2004 -Июнь 2006

Всего вагонов 8187 51239

Резуштаты распознавания

Выс. достовер. 43.4% 48.0 %

Сомнительные 46.5 % 42.0%

Отказ 10.1 % 10.0%

;: / г: Результаты проверки диспетчерами

Подтверждено 84.1% | 84.0%

Ошибочные 15.9% | 16.0%

■ Проверка распознанных С фдагом' вые. достовер

Подтверждено 48.6% 99.2 %

Ошибочные 1.4 % 0.8 %

;;! Проверка распознанных сфлагом сЪмтггельносш

Подтверждено 88.8 % 86.7 %

Ошибочные 11.2% 13.3 %

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

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

Качество распознавания сравнивалось с последней доступной на август 2007 года версией популярной программы FineReader 8.0 Professional, для него результаты распознавания следующие: «чистые»— 61,5%, «умеренно грязные» - 4,4 %, «грязные» - 0, всего - 33,4 %.

На той же выборке было проведено тестирование двух алгоритмов быстрой локализации области номера: а) по цветовому контрасту; б) сочетание цветового контраста и выраженных изломов.___

Таблица 4. Тесты быстрой локализации Хорошие Средние Плохие

Цветовой контраст 99,3% 88,2% 69,9%

Цветовой контраст и выраженные изломы 100% 92,9% 71,5%

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

битная оптимизация с накапливаемыми суммами по строкам и столбцам.

Система была введена в эксплуатацию в мае 2004 года, статистика по

обработанным диспетчерами составам снималась дважды - в сентябре 2004 и в

июне 2006 года (таблица 3).

Заключение

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

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

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

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

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

Основные публикации в изданиях, рекомендованных ВАК:

1. Казанский Н.Л., Хмелев Р.В. Сравнение объекта и эталона по отклонению контуров // Компьютерная оптика, 2000, № 20 - с. 134-139.

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

3. Kazanskii N.L., Khmelev R.V. Algorithms of Searching for a Standard on Binary Images // Pattern Recognition and Image Analysis, 2001, Vol. 11, № 1 -p.187-188.

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

5. Хмелев Р.В. Совместное использование структурного анализа и метрики Хаусдорфа при сравнении объекта и эталона. // Компьютерная оптика, 2005, № 27 - с. 174-176.

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

7. Volotovskii S.G., Kazanskü N.L., Popov S.B., Khmelev R.V. Machine Vision System for Registration of Oil Tank Wagons // Pattern Recognition and Image Analysis, 2005, Vol. 15, №2-p.461-463.

8. Буланое А.П., Волотоеский С.Г., Казанский Н.Л., Попов С.Б., Хмелев Р.В., Шумаков СМ. Система технического зрения для регистрации железнодорожных составов цистерн // Автоматизация в промышленности, 2005, № 6 -с. 57-59.

9. Хмелев Р.В. Итеративная аппроксимация последовательностей по максимуму периметра и с использованием неравенства треугольника. // Компьютерная оптика, 2005, №27-с. 155-164.

10. Хмелев Р.В. Сравнительный анализ быстрых алгоритмов слияния для итеративной полигональной аппроксимации контурных цепей при различных критериях оптимизации // Компьютерная оптика, 2006, №29 -с. 135-140.

Прочие публикации:

11. Казанский H.H., Хмелев Р.В. Алгоритм поиска эталона на бинарных изображениях // Труды 5-ой Международной конференг\ии «Распознавание образов и анализ изображений: новые информационные технологии (РОАИ-5-2000)», Самара, 16-22 октября 2000 г. Самара: ИПО СГАУ, 2000, Том 2 - с.288.

12. Khmelyoff R. V. Comparison of Standard and Object by Contour Deviation // Proceedings of the LASTED International Conference ACIT-2002, Новосибирск, 10-13 июня 2002. ACTA Press, Calgaiy, Canada, 2002 - c. 549-554.

13. Волотоеский C.B., Казанский Н.Л., Попов С.Б., Хмелев Р.В. Распознавание номеров железнодорожных цистерн с использованием быстрой локализации и модификации алгоритма сравнения объекта с эталоном по среднеквадратической метрике Хаусдорфа. // Обозрение прикладной и промышленной математики, 2005, том 12, № 3-е. 714.

14. Хчелев Р.В., Казанский Н.Л., Попов С.Б. Система регистрации железнодорожных составов цистерн Н Свидетельство об официальной регистрации программ для ЭВМ № 2004611971 по заявке № 2004611383 от 29 июня 2004 года. Зарегистрировано в Реестре программ для ЭВМ 26 августа 2004 года.

15. Хмелев Р.В. Итеративная аппроксимация многоугольников по критерию максимального периметра и одномерных последовательностей по критерию максимальной средней кинетической энергии П Обозрение прикладной и промышленной математики, 2005, том 12, № 3 - с. 779.

16. Хмелев Р.В. Получение информации об изломах контура с помощью полигональных аппроксимаций II Сборник трудов Всероссийского семинара по моделированию, дифракционной оптике и обработке изображений, июль 2006. Самара, ИСОИ РАН, 2006-е. 46-53.

Подписано в печать 10.02.2009. Усл. печ. л. 1.00. Тираж 100 экз.

Отпечатано с готовых оригинал-макетов.

443086, Самара, СГАУ, Московское шоссе, 34

Введение

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

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

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. В.В.Митрофанов .С.Арифуллин