Содержание к диссертации
Введение
Глава 1. Анализ и классификация основных подходов к проблеме обнаружения объектов на изображениях 16
1.1. Предмет дисциплины "машинное зрение" 16
1.2.Основные требования к алгоритмам обнаружения 22
1.2.1.Робастность 23
1.2.2. Локализация 25
1.2.3.Вычислительная реализуемость 27
1.3. Обнаружение объектов, заданных эталонными изображениями 28
1.3.1.Обнаружение объектов на основе яркостной сегментации и признаковых описаний 28
1.3.2.Корреляционное обнаружение 30
1.3.3.Морфологический подход Ю.П. Пытьева 33
1.4.Обнаружение малоразмерных объектов на изображениях по методу "нормализации фона" 36
1.5,Основные понятия математической морфологии (по Серра), свойства морфологических операторов 43
1.5.1 .Морфологические операции на бинарных изображениях 43
1.5.2.Расширение морфологических операций на случай полутонового изображения 45
1.5.3.Применение морфологических операторов для выделения "черт" и объектов на изображениях 47
1.6.Основные понятия преобразования Hough, обобщенное преобразование Hough, свойства НТ и GHT 50
1.6.1.Преобразование Hough 50
1.6.2,Обобщенное преобразование Hough (GHT) 53
1.6.3.Обнаружение "черт" и объектов в пространстве параметров 56
Выводы по первой главе 57
Глава 2. Исследование различных аспектов классических методов обнаружения 59
2.1.Связь между нормированными обычным и морфологическим коэффициентами корреляции 59
2.2. Исследование вероятностных характеристик аномальных ошибок обнаружения для корреляционного обнаружителя 65
2.3.Анализ свойств метода нормализации фона 72
2.3.1.Задача обнаружения малоразмерных объектов 72
2.3.2.Результаты моделирования 77
2.4.Анализ двумерного поля на наличие характерных черт 88
2.4.1.Выделение характерных точек
2.4.2.Выделение характерных линий 95
2.4.3.Выделение характерных областей 100
2.4.4.Выделение характерных структур 101
2.5.Выводы по второй главе 102
Глава 3. Метод обнаружения объектов, основанный на объединении свидетельств и исследование его различных приложений 104
3.1 .Постановка задачи 108
3.2.Обобщенный подход к детектированию, основанный на анализе свидетельств 112
3.3. Способы повышения вычислительной эффективности алгоритмов детектирования и распознавания 114
3.2.1.Аккумулирование свидетельств 114
3.3.2.Принцип разделения. Декомпозиция и редукция вектора параметров 115
3.3.3.Загрубление модели объекта 117
3.3.4. Использование структурных иерархических моделей 119
3.4.Обобщенная структура алгоритма детектирования 123
3.5. Алгоритмическое обеспечение для устойчивого считывания
штрихкодовой информации в условиях помех и искажений 128
3.5.1.Постановка задачи, характеристика тестовых изображений 129
3.5.2.Анализ возможных методов решения задачи детектирования
штриховых кодов на изображении 132
3.5.3.Модульный алгоритм обнаружения штриховых кодов 139
3.5.3.1.Общая характеристика алгоритма 139
3.5.3.2.0писание алгоритма 142
3.5.3.3.Особенности модифицированного преобразования Hough. 145
3.5.3.4.Результаты тестирования модульного алгоритма 148
З.б.Измерение угловых объектов 151
3.6.1.Постановка задачи измерения угла схождения сварных швов 151
3.6.2.Натуральная параметризация пространства Hough 152
З.б.З.Поиск сопряженной пары прямых 154
3.6.4.Измерение угла с субпиксельной точностью 156
3.7.Выводы по третьей главе 157
Глава 4. Разработка методов эффективного стереоотождествления 160
4.1.Основные проблемы, возникающие при стереоотождествлении... 162
4.1.1.Область поиска 163
4.1.2.Уникальность эталона 165
4.1.3.Начальные приближения 165
4.1.4.Геометрические искажения образов 166
4.1.5.Яркостные различия образов 168
4.1.6.Ложное отождествление 169
4.2.Выбор метода решения задачи стереоотождествления 170
4.3. Определение наиболее устойчивых информативных участков изображения путем локального статистического анализа 172
4.3.1.Показатели информативности фрагмента изображения 176
4.3.2.Анализ наличия сигнала на фрагменте изображения 182
4.4.Корреляционное стереоотождествление с использованием пирамиды стереопар 187
4.5.Обобщенная форма корреляционного стереоотождествления 193
4.6.Выводы по четвертой главе 198
Глава 5. Метод субпиксельной корреляции в задаче высокоточного отождествления соответствующих точек 200
5.1.Анализ существующих методов субпиксельного корреляционного стереотождествления 200
5.2.Линеаризация задачи 204
5.3.Решение задачи на обобщенные собственные значения 206
5.3.1.Решение методом Холецкого 207
5.3.2.Решение методом ортогонализации 209
5.4.Решение задачи максимизации корреляционной функции 211
5.5.Эквивалентность субпиксельной корреляции и корреляции методом наименьших квадратов 213
5.6. Экспериментальное исследование метода субпиксельной корреляции 216
5.6.3.Временные характеристики 216
5.6.3.Описание вычислительного эксперимента 217
5.6.3.Сходимость параметров и коэффициента корреляции 219
5.6.4.Оценка точности 220
5.6.5.Точность отождествления контрольных точек стереопары 220
5.7.Метод субпиксельной корреляции с учетом предварительной сегментации изображений 227
5.7.1.Использование результата сегментации в модели стереоотождествления 227
5.7.2.Линеаризация задачи 228
5.7.3.Преобразование коэффициента кросс-корреляции 229
5.7.4.Преобразование морфологического коэффициента корреляции231
5.7.5.Максимизация коэффициента корреляции 232
5.8.Применение методов автоматизированной стереообработки изображений космической и авиационной съемки в современных
компьютерных технологиях визуализации 233
5.9.Выводы по пятой главе 238
Глава 6. Метод обнаружения трехмерных объектов, основанный на анализе дифференциальных ортофотоизображений 240
6.1.Исследование стереофотограмметрических возможностей метода 242
6.2.Описание алгоритма обнаружения 246
б.З.Выводы по шестой главе 252
Глава 7. Разработка алгоритмов обнаружения препятствий в системе управления транспортным средством 254
7.1.Постановка задачи, технические требования к системе обнаружения 254
7.2.Алгоритм обнаружения продольных линий дорожной разметки 255
7.2.1.Общая характеристика алгоритма 257
7.2.2.Алгоритм первичного выделения сегментов разметки 257
7.2.3.Алгоритм монокулярного обнаружения продольных линий разметки 261
7.2.4.Алгоритм стереоотождествления и локализации положения линий разметки 266
7.2.5.Алгоритм прослеживания линий разметки 269
7.2.6.Алгоритм формирования списка соответствующих сегментов. 275
7.2.7.Результаты тестирования алгоритма 277
7.3.Алгоритмы обнаружения препятствий 278
7.3.1.Логика работы алгоритма обнаружения препятствий 278
7.3.2.Предварительные шаги блока обнаружения препятствий 278
7.3.3.Построение ортофото 281
7.3.4.Построение локальных признаков препятствий 283
7.3.5.Корреляционно-признаковое сравнение ортофото 285
7.3.6.0бнаружение элементов препятствий 288
7.3.7.Работа системы в режиме сопровождения препятствий .289
7.4.Примеры работы системы 291
7.5.Выводы по седьмой главе 293
Глава 8. Создание средств разработки специализированного программного обеспечения для анализа изображений 295
8.1.Требования к средствам разработки систем анализа изображений Программная среда "Pisoft" 295
8.2.Этапы развития и состав пакета Pisoft 296
8.3.Фреймовая архитектура пакета Pisoft 298
8.4.Результаты применения пакета Pisoft 302
8.5.Выводы по восьмой главе 306
Заключение 309
Литература
- Обнаружение объектов, заданных эталонными изображениями
- Исследование вероятностных характеристик аномальных ошибок обнаружения для корреляционного обнаружителя
- Способы повышения вычислительной эффективности алгоритмов детектирования и распознавания
- Определение наиболее устойчивых информативных участков изображения путем локального статистического анализа
Обнаружение объектов, заданных эталонными изображениями
Важное отличие, присущее проблеме обнаружения объектов на изображениях по сравнению с задачами распознавания или интерпретации хорошо сегментированного образа, заключается в том, что обнаружение в практических задачах всегда связано с процедурой поиска объекта.
Именно реализация процедуры поиска объекта связана с угрозой взрывообразного роста необходимого числа вычислений. Проиллюстрируем это на примере простой задачи поиска объекта на основе сравнения с растровым эталоном или шаблоном (template). Если построить какой-либо функционал соответствия между объектом размером МхМ и фрагментом МхМ из изображения NxN, то простой перебор фрагментов требует количества вычислений не менее чем M2N2 операций, что составляет, например, 10 миллиардов операций при размере объекта 50x50, а изображения - 2000x2000 элементов. Даже принимая во внимание значительное увеличение возможностей современных персональных компьютеров, такие объемы вычислений занимают секунды или десятки секунд машинного времени, что далеко выходит за пределы требований систем обнаружения реального времени, предназначенных для таких задач как навигация и наведение, инспекционный контроль, обработка машиночитаемых документов и др.
К сожалению, реальные задачи обработки визуальной информации изобилуют дополнительными степенями свободы, когда искомая яркостно-геометрическая структура на изображении может иметь не только произвольные положение, угловую ориентацию и масштаб, но и подвергаться разным преобразованиям, не только аффинным или проективным, но и гораздо более сложным, таким как различные "резиновые" модели или коробление (warping, искажение напоминающее смятую бумагу). Все это катастрофически увеличивает потребное для перебора время расчетов и требует применения качественно новых идей по организации процесса обнаружения. Наиболее общий подход к возможному решению этой проблемы состоит в применении 26 иерархической стратегии поиска, т.е. декомпозиции объекта на более мелкие части с выраженными особенностями - «характерные черты» - с последующим поиском этих частей.
При этом, бесконечно разнообразные виды зашумлений и искажений, встречающиеся на изображениях, заставляют искать компромисс между двумя малоприятными альтернативами: обнаруживать малое число наиболее характерных черт, рискуя при этом пропустить весь объект, или же пытаться собирать информацию о многих менее значительных характерных чертах, анализируя эту информацию дольше, но комплексно. Возникают вопросы о том, как много этих черт должно быть проанализировано для надежной работы алгоритма, какой апертурный размер черты следует брать, и каковы должны быть их желательные качественные и количественные свойства, и т.д. и т.п. Все эти вопросы так или иначе затрагиваются в данной работе.
Второе важнейшее свойство, которым должны, как правило, обладать алгоритмы обнаружения объектов на изображениях можно определить как точная локализация. Это понятие означает, что необходимо не только обнаружить объект, но и точно указать в системе координат изображения (или сцены) его положение в каком-либо смысле. Несколько неясное толкование локализации данное выше, связано с тем, что по сравнению со своей эталонной моделью объект может быть заметно искажен геометрически, причем аналитическая модель искажения может отсутствовать. Пример тому -штриховой код, находящийся на смятой упаковке, пятно на коже и т.п. В этих случаях локализация объекта является нетривиальной задачей. В более простой ситуации при аналитически заданной с точностью до параметров геометрии искажений под точной локализацией можно понимать знание о положении какой-либо характерной точки объекта и параметрах геометрии искажения (поворот, аффинные коэффициенты, изгибы и др.). При этом, встречающиеся случаи ошибок локализации целесообразно разделить на две группы -нормальные и аномальные ошибки.
Нормальная ошибка в контексте данной работы - это правильная локализация объекта с некоторой позиционной или параметрической неточностью, характеризуемой количественными оценками /16/. Для объектов, характеризуемых габаритными размерами, большими 3x3- 5x5 элементов изображения, позиционные нормальные ошибки могут быть значительно меньше размера элемента изображения, уменьшаясь с величиной объекта. В этом случае принято говорить о субпиксельной локализации. Это особенно важно для задач стерео обнаружения, так при малых параллаксах ЗБ-объектов субпиксельная локализация самым существенным образом определяет точность их пространственного положения.
К аномальным ошибкам следует отнести ситуацию перепутывания объектов или возникновение артефактов, что связано с фатальными количественными ошибками позиционирования или просто ложным обнаружением. Требования по исключению или ограничению уровня аномальных ошибок составляют очень важную часть требований к алгоритмам обнаружения. Однако, анализ возможностей их возникновения на основе теоретического исследования каких-либо их статистических или количественных свойств является, как правило, крайне сложной задачей, и потому в настоящее время редко производится.
Вопросы, связанные количественными и качественными особенностями алгоритмов, в плане их аномальных ошибок также будут рассмотрены в настоящей работе.
Несмотря на колоссальный путь, который прошла в целом вычислительная техника за последние декады XX века, несмотря на создание обширной специализированной процессорной базы для обработки изображений, в основной массе приложений, особенно реального времени, характеристики вычислителей и их свойства все еще далеки от желаемых.
Можно достаточно легко получить приблизительные эмпирические оценки объема потребных вычислений. Если рассмотреть алгоритмы, реализуемые на простейшей апертуре 3x3, то даже в этом случае объем вычислений составляет десятки операций на точку изображения. Как правило, при обработке среднего и высокого уровня необходимый объем расчетов колеблется в пределах от сотен до тысяч операций на пиксел. Оценивая размер изображения, предназначенного для обработки, например, как 1000 на 1000 элементов, что не является чем-то необычным для современных видеодатчиков (можно вспомнить, что бытовые цифровые фотоаппараты к 2000 году давно перешли отметку 2 мегапиксела в ПЗС матрице), получим оценку количества потребных вычислений порядка нескольких гигабайтов операций на кадр. Для приложений же реального времени необходимо выполнять эти вычисления в темпе кадровой развертки, что приводит к оценке быстродействия около 50 Gflop/sec. Сами по себе все эти оценки не являются запредельными для супермощных ЭВМ последнего поколения, однако следует учесть, что основные приложения машинного зрения и, в частности, обсуждаемой в диссертации задачи обнаружения объектов, находятся в областях, где массогабаритные и стоимостные характеристики конструируемых устройств должны быть весьма невелики.
Исследование вероятностных характеристик аномальных ошибок обнаружения для корреляционного обнаружителя
Как будет показано далее в главе 3, один из важнейших подходов к построению методов обнаружения сложных объектов на изображениях базируется на их представлении в виде моделей, состоящих из многих характерных яркостно-геометрических черт-признаков (features), находящихся в определенной взаимосвязи. Общий обзор и исследования автора относительно различных характерных черт, пригодных для использования в алгоритмах обнаружения объектов и сопоставления изображений, будет дан в подразделе 2.4. В то же время эта проблема частично затрагивается в данном параграфе, так как выделение границ и характерных точек на изображении является одной из главных областей применения ММ. В частности, характерными элементами являются "Т", "Y" и "W -соединения (на полутоновых изображениях), острые пики и глубокие впадины "рельефа изображения", мысы и "заливы", ступенчатые разрывы поверхности и т.д.
Определим морфологическую границу Хт для множества X как разность расширения и сжатия X по сферическому структурирующему элементу Вг Xm = (X(+)Br)-(X(-)Br). (1.5.15) С топологической точки зрения, мы получим множество точек, окрестности которых пересекаются как с объектом X так и с фоном (дополнением)X . едем категории точек морфологической границы : Гладкой поверхностью называется связное множество точек в Хт, которые имеют двумерную окрестность в Хт, т.е. в каждой из этих точек существует непрерывная нормаль к поверхности. Сингулярной кривой называется кривая Сс:Хт, представляющая собой связное множество точек, имеющих одномерную окрестность на Хт. Точки границы Хт, не принадлежащие ни гладкой поверхности, ни сингулярной кривой, называются сингулярными точками. Примером сингулярных точек могут служить "T","Y" и "W -узлы.
В /10/ показано, что детектор (1.5.15) обеспечивает хорошее обнаружение узлов и ступенчатых разрывов поверхности полутонового изображения. Однако, для обнаружения пиков, впадин и острых углов необходим другой алгоритм.
Элементарные геометрические соображения показывают, что операции расширения и сжатия позволяют обнаруживать пики и острые углы. Механизм обнаружения прост. Как уже отмечалось ранее, расширение X дисковым (сферическим) структурирующим элементом можно рассматривать как объединение всех дисков (сфер) вписанных в изображение, а сжатие можно рассматривать, как расширение по фону X . Из рисунка 1.8 видно, что в точке острого угла разность между расширенным и сжатым изображением будет максимальна. Поэтому детектор острых углов можно определить как разность между открытием X и закрытием X: gXm = X0B-X B. (1.5.16) Структурирующий элемент, используемый для выделения черт не обя зан быть "сферическим" в точном смысле этого слова, поскольку масштаб изобра 48 p(cosec 8-1) жения по яркостной оси никак не связан с его геометрическим масштабом. Однако, легко показать, что операции выделения "черт" при помощи ММ являются инвариантными к поворотам в том и только том случае, когда структурирующий элемент имеет форму тела вращения вокруг оси, проходящей через точку с координатами (0,0). Поскольку результат применения морфологических операторов зависит только от формы структурирующего элемента, вращение изображения относительно структурирующего элемента эквивалентно повороту на такой же угол (в обратном направлении) структурирующего элемента относительно изображения. Тогда условием инвариантности операторов к повороту является эквивалентность структурирующего элемента самому себе при повороте относительно точки (0,0) на любой угол. Это выполняется только в том случае, когда структурирующий элемент имеет форму тела вращения.
Габаритные размеры такого структурирующего элемента (диаметр носителя и высота) определяют масштаб "черт", выделяемых по описанной выше схеме.
Математическая морфология и ее основные операции создают наиболее реализуемые условия для метода нормализации фона. В этом случае используются два структурирующих элемента ВІ и В2. Элемент Bj конструируется таким образом, чтобы "подходить" даже к самым маленьким размерам объекта на изображении и в тоже время отсекать импульсный шум, элемент В2 имеет большие размеры апертуры и в состоянии подавить любой, 50 даже самый большой по геометрическим размерам отклик объекта. Алгоритм нормализации фона выглядит в этом случае следующим образом: X = ( (Х(-)В1)(+)В1)- ( (Х(-)В1Х+)В1)0В2. Для выбора класса и конкретной реализации алгоритмов предварительной обработки, а также исследования их оптимальных параметров необходимо проведение математического моделирования с учетом характеристик модельной и реальной фоноцелевой обстановки.
Как ранговые, так и морфологические алгоритмы фильтрации допускают чрезвычайно эффективную реализацию в классе "скользящих" алгоритмов Хуанга /69/.
Таким образом, в задачах инвариантного обнаружения на изображении границ, характерных точек и других "черт", а также малоразмерных объектов в сложной шумовой обстановке, могут применяться алгоритмы, основанные на использовании операторов математической морфологии со структурирующими элементами в форме тел вращения. Возможна масштабная настройка таких алгоритмов путем изменения размера структурирующих элементов.
Способы повышения вычислительной эффективности алгоритмов детектирования и распознавания
Многолетняя эволюция методов обнаружения различных объектов на изображениях шла как по пути развития гибких модельных описаний детектируемых структур ("гибкие эталоны", иерархические модели и т.д.), так и по пути обеспечения инвариантности алгоритмов обнаружения к различным регулярным яркостно-геометрическим преобразованиям (афинность, резко ракурс-ность, линейное контрастирование), и их устойчивости (робастности) относительно различного рода неконтролируемых шумов и искажений.
На начальных этапах развития систем обнаружения и идентификации объектов чрезвычайно привлекательными казались т.н. оптимальные вероятностные подходы (см.. например /9, 12, 14, 66/), основанные на максимизации функций (или отношений) правдоподобия или непосредственно на оценках байесовской апостериорной вероятности. Основным достоинством таких методов являлась возможность непосредственной оценки вероятностных характеристик поведения алгоритмов детектирования в зависимости от интенсивности и характера искажений (вероятность ложного обнаружения, вероятность пропуска и т.п.). Эти характеристики позволяли не только судить о качестве предлагаемых алгоритмов вообще, но и получать в каждом конкретном случае оценки достоверности отнесения обнаруженного объекта к тому или иному классу, на основе которых можно принимать различные дальнейшие решения (например, по управлению оперативной обстановкой, по наведению оружия и т.п.).
Однако, методы анализа изображений, развивавшихся в этом направлении, обладали и рядом "генетических" недостатков, основные из которых -следующие: Требование точного вероятностного описания изображения, невозможное без детального физического моделирования каналов получения изо 105 бражений, что снижало общность предлагаемых подходов и ограничивало их робастность. Невозможность адекватного вероятностного описания изображений сложных структурированных (часто - изменчивых) трехмерных объектов на сложном структурированном фоне. Низкая вычислительная эффективность оптимизационных вероятностных процедур при анализе реальных изображений сложных структурированных сцен.
Именно эти ограничения определили существующую в настоящее время тенденцию к отказу от оптимальных вероятностных методик в пользу различных специальных методик анализа изображений, не основанных на вероятностных рассуждениях. Такие методики позволяют гораздо более полно и в то же время более универсально учитывать как специфику яркостно-геометрических отношений между элементами изображений, так и структуру самих объектов, подлежащих детектированию. На этом пути, помимо множества эвристических алгоритмов, был создан и ряд методик, претендующих на значительную общность подхода, в первую очередь это математическая морфология Серра (ММ), математическая морфология Ю.П. Пытьева (МП) кратко рассмотренные в первой главе, методы структурно-лингвистического анализа изображений /62, 67/, методы, основанные на использовании трехмерных моделей /88/, и ряд других. При этом вычислительная эффективность этих методов определяется либо простотой (и соответствующей "дешевизной") базовых операций (как в ММ и МП) либо иерархической методикой анализа изображений, при которой сначала выделяются простейшие смысловые составляющие изображения, а затем -осуществляется их "сборка" согласно заданной модели (как в структурно-лингвистическом подходе) или сравнение полученного структурного описания с модельным структурным описанием (как в методе семантических реляционных графов).
Как ни странно, существенные недостатки этих современных методик определяются именно тем, что они не являются вероятностными. Именно поэтому они не дают непосредственных оценок вероятностных характеристик поведения алгоритмов детектирования, и вообще зачастую крайне чувствительны к шумам и помехам; не позволяют получать оценки достоверности классификации обнаруженных объектов, что делает их малопригодными для использования в системах поддержки принятия ответственных решений (в первую очередь - в области военной техники).
Регулярно предпринимаемые попытки "рандомизации" этих методик пока вряд ли можно признать успешными. Например, "нежесткие" (ранговые) операторы ММ действительно гораздо более устойчивы к присутствию помех типа шума замещения, однако, они уже не обладают теми математическими свойствами, которые и определяли исключительный интерес к исходной морфологической парадигме Серра.
Таким образом, представляется, что в области анализа цифровых изображений назрела необходимость нового синтеза, в результате которого были бы предложены алгоритмы обнаружения и идентификации объектов, обладающие как свойствами оптимальных вероятностных процедур так и способностью полноценно учитывать специфику яркостно-геометрических отношений между элементами изображений и сложную структуру детектируемых объектов.
Между тем, в смежной области искусственного интеллекта давно и успешно развивается методика вероятностной поддержки принятия ответственных решений, которая, с одной стороны, не требует строгого знания вероятностных моделей, а с другой - позволяет вычислять степень достоверности заключений, полученных в результате сложного логического вывода на основе разнородных (и зачастую противоречивых) данных. Речь идет о технике объе 107 динения свидетельств, которая первоначально была развита для оценки достоверности выводов в диагностических экспертных системах /83/. При этом диагнозы рассматривались как набор альтернативных гипотез (составляющих вместе с гипотезой "не знаю" генеральную совокупность), а значения диагностических признаков играли роль событий, свидетельствующих в пользу данных гипотез. Свидетельствующие события (свидетельства) считаются при этом также условно независимыми. Для решения такого рода задач объединения свидетельств первоначально непосредственно использовался байесовский подход (БП), а затем на его основе был разработан подход Демпстера-Шафера ІДШ). Оба эти подхода, вообще говоря, основаны на теореме Байеса.
Определение наиболее устойчивых информативных участков изображения путем локального статистического анализа
Существует множество методов обработки изображений, использующих выделение контурного препарата в качестве начального этапа обработки. На тестовых изображениях были рассмотрены наиболее "быстрые" операторы выделения пикселов края: оператор Робертса (2x2), оператор Собела (3x3) и оператор Марра (7x7) /55, 57/. По результатам тестирования сделан вывод о том, что только операторы Марра и Собела обеспечивают приемлемое качество контурного препарата.
Однако оператор Собела дает больше информации, чем оператор Марра, в том смысле, что кроме положения краевых точек, он в явной форме вычисляет параметры контраста (модуль градиента) направления края (направление градиента) в данной точке края. Известно, что оператор Собела обеспечивает точность вычисления угла ориентации градиента порядка 4.
Оператор Собела используется в предлагаемом модульном алгоритме детектирования штриховых кодов на этапе голосования (после пороговой сегментации). Детектирование коллинеарности
Для того, чтобы использовать внутреннюю структуру штрихового кода, как признак объекта, при его детектировании, необходимо либо описать эту структуру как текстуру и применить какие-либо стандартные методы текстурного анализа, либо - разработать алгоритмы детектирования, специально дня обнаружения такой внутренней структуры объектов,
Основным свойством внутренней структуры штрихового кода, как следу 136 ет из принятой модели, является параллельность штрихов. Другими словами, в пределах кода находится множество точек с примерно коллинеарными градиентами. Таким образом, для детектирования структуры типа штрихового кода, мы должны исследовать локальную окрестность точек-кандидатов с целью проверки степени коллинеарности градиентов. Предполагается, что после анализа локальных "коллинеарностных" свойств небольших областей на изображении, следует этап "сборки" выделенных областей в связные фигуры (объемлющие прямоугольники). Эта группа методов будет рассмотрена чуть позже.
Простейшим детектором линейчатых структур является локальная корреляция строк изображения. Этот метод обладает низкой вычислительной скоростью и не дает удовлетворительных результатов в случае наличия на кодах пятен или бликов.
Также неудачной оказалась попытка применить к локальным фрагментам изображения преобразование Фурье. Не удалось выявить достоверных признаков, характеризующих произвольные непериодические линейчатые структуры в пространстве Фурье, достаточно устойчивые к шуму (пятнам и бликам). Низкую помехоустойчивость таких детекторов можно объяснить тем, что они используют локальные структурные свойства штриховых кодов, не опираясь на их площадные (интегральные) характеристики.
Стандартный метод оценки степени коллинеарности градиентов заключается в сборе и анализе гистограммы ориентации градиента в некоторой локальной области. Основное направление соответствует максимуму (главной моде) гистограммы. Степень коллинеарности соответствует остроте пика главной моды гистограммы. Для оценки остроты пика применялся ряд численных критериев, известных из прикладной математической статистики.
Был также построен оригинальный детектор коллинеарности - отношение аспекта. Пусть вектор градиента в точке (х,у): g(x,y):=(gx(x,y),gy(x,y)). Тогда матрица обобщенной дисперсии градиента g по области А примет вид: E = [(S20,S11),(S11,So2)], eSpq={(gxi)p(gyi)q} Отношение аспекта является отношением собственных значений (Я1Д2) этой матрицы: F =(А,і/А,2), (А,і А,г). Отношение аспекта F будет велико в том случае, когда на области А имеется множество точек с одинаково направленными градиентами, и мало, если распределение градиентов по направлениям приближается к равномерному. Преобладающее направление градиентов на области А соответствует направлению наибольшего собственного вектора матрицы Е.
Эксперименты на тестовых изображениях продемонстрировали хорошее качество сегментации, обеспечиваемое как гистограммными методами так и, в особенности; детектором коллинеарности, использующим отношение аспекта. Однако они также не оказались устойчивыми к бликам, пятнам и текстовым тестам. Необходимо также отметить высокую вычислительную стоимость этих операции при их итеративном использовании.
Детектирование коллинеарности не применялось на этапе обнаружения штриховых кодов. Однако, на окончательном этапе проверки природы обнаруженных объектов, было использовано отношение аспекта, как основной числовой признак объектов типа "штриховой код". Методы, основанные на связности.
Эта группа методов часто используется в системах распознавания текста. На этапе предварительных исследований, было реализовано два базовых подхода, использующих выделение связных областей на изображении. Первый из них заключался в "сборке" связных темных областей (после пороговой сегментации), соответствующих толстым штрихам кода. Второй заключался в прослеживании областей, соответствующих целым штриховым кодам, путем объединения участков изображения с высоким значением отношения аспекта.
Первый путь не привел к успеху из-за наличия ряда тестовых изображений (11,12,13,14), в которых либо связность толстых штрихов кода нарушается бликами, либо несколько раздельных штрихов оказываются связными из-за того, что код перечеркнут. Второй подход показал свою устойчивость и примнимость на большинстве тестовых изображений. Однако, поскольку этот подход не основан на какой-либо параметрической (геометрической) модели обнаруживаемых кодов, он может выделить только область интереса на изображении, т.е. приблизительно определить местонахождение кода но не его точный размер и ориентацию. Следовательно, после сборки областей с высоким значением отношения аспекта, все равно необходима некоторая постобработка, обеспечивающая получение списка искомых координат объемлющих прямоугольников. Таким образом, использование этой группы методов не позволяет добиться желаемой вычислительной эффективности. В то же время, проведенные исследования еще раз подтвердили эффективность применения отношения аспекта в качестве проверочного признака. Преобразование Hough.
Идея использования преобразования Hough при обнаружении штриховых кодов заключается в следующем. Очевидно, что любой штриховой код на изображении, имеющий ориентацию ф и высоту h порождает в сечении аккумулятора А(р,ф) сигнал типа "меандр" шириной h. Таким образом, геометрические параметры кодосодержащей полосы (ф,рі,р2) можно определять в пространстве Hough. Здесь также необходима постобработка для обнаружения точного положения объемлющего прямоугольника в кодосодержащей полосе.
В предварительных экспериментах преобразование Hough применялось непосредственно после пороговой сегментации. Эти эксперименты показали возможность использования этого метода для обнаружения кодосодержащих полос на всех изображениях тестового набора. В то же время, на изображениях с искажениями (блики, дефекты печати, пятна), профиль прямоугольного сигнала в аккумуляторе выглядит в значительной мере зашумленным. Кроме того, присутствие текстовых строк (изображения 9,10) сильно "загрязняет" аккумулятор ложными "меандрами". Скоростные показатели стандартной процедуры голосования также не удовлетворяют требованиям к быстродействию.
Для того чтобы повысить устойчивость и одновременно быстродействие такого алгоритма детектирования, был предложен оригинальный метод, названный Модифицированным преобразованием Hough (МНТ). Основная идея этого алгоритма состоит в том, чтобы использовать в момент голосования не только яркостную информацию о точке, но и направление градиента в ней (по аналогии с обобщенным преобразованием Hough). Этот алгоритм будет подробно описан в подразделе 3.5.3.2
