Содержание к диссертации
Введение
1. Анализ методов распознавания структурированных символов 9
1.1. Методы описания изображений структурированных символов 9
1.1.1. Шаблонный метод распознавания 10
1.1.2. Структурный метод распознавания 11
1.1.3. Признаковый метод распознавания 14
1.1.4. Методы морфологического анализа формы изображения 18
1.2. Программные системы распознавания структурированных символов . 24
1.2.1. Системы оптического распознавания текстов 25
1.2.2. Системы оптического распознавания маркировки поверхности различных объектов 27
Выводы 31
2. Распознавание структурированных символов 32
2.1. Выделение области расположения символов на изображении 33
2.2. Выделение отдельных символов 37
2.3. Расширение базовых морфологических операций 42
2.4. Построение векторов признаков изображений символов на основании методов морфологического анализа 44
2.5. Быстрые морфологические преобразования для задач коррекции и преобразования бинарных изображений 50
Выводы 57
3. Программная реализация разработанных алгоритмов 58
3.1. Обоснование требований к характеристикам программного обеспечения 58
3.2. Реализация программы 59
3.3. Структура программы 62
3.4. Структура системы 65
3.4. Алгоритм распознавания символов 71
3.5.1. Выделение области расположения символов на изображении 71
3.5.2. Выделение отдельных символов 74
3.5.3. Распознавание символов 77
3.6. Оценка качества распознавания 82
Выводы 95
Заключение 96
Список литературы 98
- Программные системы распознавания структурированных символов
- Расширение базовых морфологических операций
- Быстрые морфологические преобразования для задач коррекции и преобразования бинарных изображений
- Выделение области расположения символов на изображении
Введение к работе
Актуальность работы. Современные технологические, производственные и офисные системы в процессе своего функционирования используют информацию о маркировке объектов. Информация о маркировке грузов, вагонов, контейнеров, изделий позволяет рациональным образом организовывать процесс технологической обработки, вести учет и контроль изделий и материалов, прогнозировать потребность в них. В основе процессов использования маркировки (текстово - цифровых меток) лежит технология автоматизированного распознавания структурированных символов. Потребность в такой технологии вызвала необходимость создания методов, моделей и систем распознавания структурированных символов.
В настоящее время такие технологии реализуются тремя традиционными методами- структурным, признаковым и шаблонным [1 -6]. Каждый из этих методов ориентирован на свои условия применения, для которых они являются эффективными. Вместе с тем, всем этим методам присущи недостатки. Наиболее существенные из них - высокая чувствительность к аффинным и проекционным искажениям.
Эти недостатки особенно ярко проявились при масштабной эксплуатации программно — технологических систем, использующих в своей основе эти методы. Практически у всех систем распознавания структурированных символов точностные характеристики резко падают и становятся ниже технологически приемлемых при искажении аффинными и проекционными преобразованиями. Вместе с тем технологические условия получения информации о маркировке не позволяют полностью устранить эти искажения. В этой связи, задача разработки методов распознавания структурированных символов, нечувствительных (или слабо чувствительных) к аффинным и проективным искажениям, остается актуальной и на сегодняшний момент времени. Исходя из вышеописанного, была сформулирована цель диссертации: разработка методов, алгоритмов и программ распознавания символов, инвариантных к аффинным и проективным преобразованиям.
Основные задачи диссертации:
1. Исследование методов построения алгоритмов распознавания структурированных символов.
2. Разработка метода распознавания структурированных символов, инвариантного к аффинным и проективным преобразованиям.
3. Реализация и исследование работоспособности и эффективности программной системы распознавания структурированных символов, основанной на использовании разработанного метода.
Методы исследования. Для достижения поставленной задачи используется аппарат теории множеств, методы морфологического анализа формы изображения, методы вычислительной математики, а также компьютерные эксперименты для оценки эффективности разработанных алгоритмов.
Научные положения, выносимые на защиту.
1. Последовательность преобразований: бинаризация оконтуренного изображения, локализация области расположения символов, выделение отдельных символов и идентификация, обеспечивающая вероятность распознавания символов на уровне 95-98%.
2. Морфологические операторы заливы и озера, позволяющие получить описание структурированных символов в виде топологических особенностей инвариантных к проективным и аффинным преобразованиям.
3. Быстрые морфологические преобразования, сокращающие в — ( Ъ - размер структурирующего элемента) количество вычислительных операций алгоритмов обработки и коррекции бинарных изображений.
Научная новизна исследований.
1. Обоснована транзитивность задачи распознавания структурированных символов, включающая в себя последовательность задач бинаризации оконтуренного изображения, локализации области расположения символов, выделение отдельных символов и распознавание символов.
2. Впервые введены морфологические операторы заливы и озера, позволяющие получить описание структурированных символов в виде топологических особенностей, инвариантных к проективным и аффинным преобразованиям.
3. Разработаны быстрые морфологические преобразования, позволяющие построить эффективные алгоритмы обработки и коррекции бинарных изображений за счет исключения операции последовательного перебора точек внутри структурирующего элемента.
Практическая значимость. Разработанные метод и алгоритм распознавания структурированных символов на основании методов морфологического анализа формы изображения послужили основой для создания программной системы распознавания государственных регистрационных знаков транспортных средств.
Разработанные быстрые морфологические преобразования позволяют получить эффективные алгоритмы обработки и коррекции бинарных изображений.
Разработанные в диссертации методические, алгоритмические и информационные средства предназначаются для использования в системах безопасности, видеонаблюдения, видеоконтроля и обработки изображений.
Результаты исследований непосредственно используются в учебном процессе Факультета систем управления Томского государственного университета систем управления и радиоэлектроники и Радиофизического факультета Томского государственного университета.
Апробация работы. Результаты исследований докладывались на научных семинарах кафедры автоматизированных систем управления Томского государственного университета систем управления и радиоэлектроники и научных семинарах кафедры Оптико-электронных систем и дистанционного зондирования Томского государственного университета. Основное содержание диссертации отражено в 9 научных работах (в том числе в 4-х научных статьях из перечня ВАК, 5 докладах на конференциях различного уровня).
Основные научные результаты работы докладывались и обсуждались на следующих конференциях: X Международная научная конференция, посвященная памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнева, Сибирский гос. аэрокосмический университет имени академика М.Ф. Решетнева (Красноярск, 2006); V Международная научная конференция «Информационные технологии и математическое моделирование», ТГУ (Томск, 2006); XLV Международная научная студенческая конференция «Студент и научно - технический прогресс», НГУ (Новосибирск, 2007); Всероссийская конференция молодых ученых «Наука. Технологии. Инновации» НГТУ (Новосибирск, 2007); VII Международная научная конференция «Информационные технологии и математическое моделирование», ТГУ (Томск, 2008).
Личный вклад. В диссертации использованы только те результаты, в которых автору принадлежит определяющая роль. Опубликованные работы написаны в соавторстве с сотрудниками научной группы. В совместных работах диссертант принимал участие в непосредственной разработке алгоритмов, теоретических расчетах и вычислительных экспериментов, в интерпретации результатов. Постановка задачи исследований осуществлялась научным руководителем, д.т.н., проф. Калайдой В.Т.
Степень достоверности результатов проведённых исследований.
Достоверность результатов, выводов и положений диссертационной работы обеспечивается:
- тщательной разработкой методики и алгоритмов распознавания структурированных символов;
- экспериментальной оценкой качества распознавания, проведенной на реальных изображениях, подверженных аффинным и проективным преобразованиям; — качественным и количественным сопоставлением полученных результатов с имеющимися современными теоретическими и экспериментальными данными.
Внедрение результатов. Методы, алгоритмы и программы, разработанные при выполнении диссертационной работы, использовались при выполнении работ по гранту РФФИ № 06-08-00751 «Методы и средства проектирования, создания и администрирования распределенных вычислительных систем, обработки и анализа изображений».
Результаты работы внедрены в Томском государственном университете, Томском государственном университете систем управления и радиоэлектроники.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 84 наименований. Общий объем работы составляет 106 страниц, в том числе 25 рисунков.
Программные системы распознавания структурированных символов
Исходя из этих определений, можно показать, что выход оператора наращения представляет собой множество перенесенных точек, такое что перенос отраженного СЭ В = {-Ь:ЬєВ] образует непустое пересечение с входным множеством, т.е. X В = {z :(В + z)f]X Ф (р]. Аналогично, выход оператора эрозии представляет собой множество перенесенных точек, такое что перенесенный СЭ содержится во входном множестве.
Другие операторы могут быть определены как комбинации эрозии и наращения. Например, два дополнительных фундаментальных оператора - размыкание (opening) о и замыкание (closing) Х с помощью В определяются как
Для иллюстрации геометрического поведения этих операторов полезно рассмотреть такие двумерные множества, как множество X и структурирующий элемент В, показанные в верхней части рис. 1.2. Этот рисунок иллюстрирует, что эрозия приводит к уменьшению множества X, а наращение - к его увеличению. Размыкание подавляет острые выступы и прорезает узкие перешейки в X, тогда как замыкание заполнят узкие заливы и малые отверстия, и таким образом XOBczXсі»В. Следовательно, если структурирующий элемент В имеет регулярную форму, размыкание и замыкание можно рассматривать как нелинейную фильтрацию, которая сглаживает контуры входного сигнала.
Описанный набор операторов может быть разными способами обобщен на многоуровневые (т.е. недвоичные) сигналы, представляемые действительно-значимыми функциями. Серра использовал представление tff-мерной функции f{x) набором ее пороговых множеств (1.1). При этом операция наращения всех пороговых множеств функции / с помощью одного и того же компактного множества В дает множества Taif)B, которые являются пороговыми множествами новой функции f В, называемой наращением функции / с помощью В. Эта новая функция может быть вычислена либо из (1.1) как (/ B)ix) = max {а :х є Ta(f) В], или из прямой эквивалентной формулы
Подобно этому операция эрозии всех пороговых множеств функции/с помощью одного и того же множества В и суперпозиции всех выходных множеств посредством (1.1) дает новую функцию, называемую эрозией функции/с помощью В, которая может быть вычислена по эквивалентной формуле
Размыкание о и замыкание функции/с помощью В определяются как foB Эрозия функции /с помощью малого выпуклого множества В уменьшает число пиков и повышает минимумы функции. Наращение функции /с помощью В увеличивает долины и удлиняет максимумы функции. Размыкание с помощью В сглаживает график функции /снизу путем срезания пиков, а замыкание сглаживает его сверху путем заполнения долин функции/ Очевидно, что большее одномерное структурирующее множество будет вызывать более сильное сглаживающее воздействие.
Применения к анализу изображений. Морфологические системы, составленные (на их нижнем уровне) из эрозий и наращений, могут быть использованы для модификации многомерных сигналов методом, аналогичным линейной фильтрации. Определения эрозии и наращения показывают, что эти операции по сложности сходны со сверткой с импульсной характеристикой конечной длительности в том смысле, что выход для данной точки зависит от входных значений в окрестностях данной точки. Однако морфологические фильтры нелинейны, и по своим свойствам и действию существенно отличаются от линейных фильтров.
Улучшение и обнаружение контуров и линий. Если В есть малый двумерный симметричный двоичный структурирующий элемент, тогда разность множеств Х\(ХОВ) дает границу двоичного изображения X, а алгебраическая разность которую мы можем назвать градиентом эрозии, улучшает контуры полутонового изображения f. Аналогичным улучшающим контуры оператором является градиент наращения
Комбинируя эти два оператора, можно получить новые контурные операторы, которые обеспечивают более симметричную обработку изображения и его фона. Приведем примеры: 1. морфологический оператор Бойхера EG(f) + DG(f), 2. морфологические операторы усиления контуров m m[EG(f), DG(f)] и max[EG(f),DG(f)], введенные Ли, 3. нелинейный оператор Лапласа DG(f) - EG(f).
Обнаружение пиков, холмов и долин. Размыкания и замыкания обеспечивают интуитивно простой и математически строгий путь обнаружения пиков и долин. Вычитание из входного сигнала/его размыкания с помощью множества В дает выход, состоящий из пиков сигнала, опора которого не может содержать В. В этом и состоит введенное Мейером [39] преобразование (top-hat) преобразование
Поскольку / о В /, P(f) всегда неотрицательный сигнал, и тем самым гарантируется, что он содержит только пики. Если цель состоит в обнаружении холмов, определяемых как области, где сигнал существенно более интенсивен, чем окружающий фон, то холм можно идентифицировать как двоичную форму, или множество В, которое является опорой соответствующего пика в функции, выражающей интенсивность изображения. Форма опоры пика, получаемая с помощью (1.6), зависит от формы В, тогда как масштаб пика зависит от размера В.
Расширение базовых морфологических операций
Представим изображение символов в виде множества X точек, соответствующих заштрихованной зоне на рис. 2.7. Пусть а - ширина символа, Ъ - высота символа. Применим операцию замыкание (1.3) к множеству ЛГна рис. 2.7, а с помощью СЭ В размером [a, b\ и рассмотрим результат на рис. 2.7, б. Области, выделенные серым цветом, назовем соответственно, область 1 - верхний залив, 2 - правый залив, 3 - нижний залив, 4 - левый залив и область 5 — озеро [70]. Затем применим операцию генерация долин (1.7) к исходному множеству X (рис. 2.7, а). Таким образом, области, выделенные серым цветом на рис. 2.7, б, есть не что иное, как результат операции генерации долин (рис. 2.7, в). Обозначим заливы двумя штрихами на части контура залива, которая не примыкает к символу (рис. 2.7, г) (очевидно, что на контуре озера штрихов не будет). Так же введем определение пролива (П) как области, которые имеют не примыкающие контуры к символу с нескольких сторон. Таким образом, для ВЗ штрихи будут сверху, для ПЗ - справа, для НЗ - снизу, для ЛЗ - слева, (рис. 2.7, г), для П — с нескольких сторон. Залив определяется как долина, полученная в результате применения операции генерация долин с помощью СЭ прямоугольной формы к исходному изображению, наложенная на исходное изображение и имеющая часть контура, не совпадающего с контуром изображения исследуемого объекта. Озеро определяется как долина, полученная в результате применения операции генерация долин с помощью СЭ прямоугольной формы к исходному изображению, наложенная на исходное изображение и имеющая контур, полностью совпадающий с контуром изображения исследуемого объекта.
Таким образом, для изображений одного и того же объекта, находящегося на какой-либо плоской поверхности, получаемых при различных ориентациях поверхности в пространстве относительно регистрирующего устройства, данные заливы, озера и их количество будут оставаться неизменными до тех пор, пока отдельные части объекта на изображении не будут перекрывать друг друга. Что позволяет использовать данное описание изображения при распознава ний изображений символов подверженных как проективным искажениям, так и таким аффинным искажениям как изменение масштаба, поворот изображения символа. Рассмотрим класс неискаженных символов F} (рис. 2.8, а) и соответствующее им изображение с «заливами», «озерами» и «проливами» (рис. 2.8, б), полученными в результате применения генерации долин (1.7) к рис. 2.8, а. В качестве описания структуры каждого символа выберем шестимерный вектор признаков х, состоящий из следующих признаков, х, - количество ВЗ, х2 - количество ПЗ, х3 - количество НЗ, х4 - количество ЛЗ, х5 - количество О, х6 - количество П, который назовем вектором первичных признаков [70]. Век тор признаков х разбивает набор символов класса Fl на двадцать два отдельных подкласса указанных в таблице 2.1. В связи с тем, что при регистрации поверхности содержащей символы угол поворота в плоскости регистрации может изменяться (исходя из технологических условий регистрации, угол поворота при фиксации изображений не превышает 15-ти градусов относительно вертикали), таюке введем еще два класса изображений.
Класс F2 - изображение символов, повернутое на 15 градусов вправо относительно вертикального положения; класс F3 - изображение символов, повернутое на 15 градусов влево относительно вертикального положения. Разбиение данных классов с помощью вектора признаков х на подклассы указано в таблице 2.1. Для неизвестной ориентации изображения символов определим класс F4, следующим образом. Перепишем все значения вектора признаков х из классов Fj, F2, F3 и соответствующие им подклассы в класс F4, затем в классе F4 объединим подклассы, имеющие одинаковые вектор признаки х (табл. 2.1).
Быстрые морфологические преобразования для задач коррекции и преобразования бинарных изображений
Использование методов морфологического анализа изображения для коррекции изображений, искаженных случайной некоррелированной помехой является одним из перспективных направлений в области анализа изображений [39-41,62,72-79]. В технических системах, ориентированных на задачи распознавания номерных знаков автомобилей, распознавание текста, анализ текстуры, топологии печатных плат, возникает необходимость в обработке бинарных изображений. В подобных системах требуется высокая точность и скорость реализации алгоритмов при минимальных затратах памяти. Традиционные методы морфологических преобразований в данном случае являются не эффективными.
Алгоритм реализации базовых морфологических операций эрозии и наращения для полутонового изображения исходя из (1.4 и 1.5) заключается в следующем. Создается массив, такого же типа как изображение, который имеет такие же размеры как исходное изображение. В него записывается результат морфологической операции. Выбирается окно размером структурирующего элемента. Окно перемещается попиксельно по всему изображению и для точки оказавшейся в центре окна выбирается минимальное или максимальное (в зависимости от выполняемой операции, эрозия или наращение) значение из значений пикселей находящихся в окрестности окна и это значение записывается в массив.
Так как бинарные изображения представлены только двумя градациями яркости, например, 0 и 1, то выбор минимального или максимального элемента, в пределах окна структурирующего элемента, для каждой точки изображения является неэффективным. В этой связи предлагается модификация алгоритма выполнения базовых морфологических операций, эрозии и наращения [78, 80]. Полагаем, что форме принадлежат точки с интенсивностью 1, а фону 0. Структурирующий элемент выбираем размером bxb (структурирующий элемент может быть выбран любой формы, в данном случае для упрощения рассмотрения он выбран в форме квадрата), b = 3, х и у - координаты точки сканирования, Nx - ширина изображения, Ny - высота изображения, i(x,y) - значение интенсивности в точке (х,у). Алгоритм имеет следующие шаги: 1. Создается массив, такого же типа как изображение, размером NxxNy, в котором будет содержаться результат операции. 2. Координатам хну присваиваем по значению (Ь -1) / 2. 3. Вычисляем значение і(х,у). 4. Если i(x,y) = 0, то точке (х,у) в массиве присваиваем значение 0 и идем на шаг 8. 5. Если i(x,y) = l, тогда вычисляем по очереди значение интенсивностей следующих точек: (х-1,у), (х-1,у-1), (х,у-ї), (х + \,у-ї), (х + \,у), (х + \,у + 1), (х,у + \), (х-1, + 1) (т.е. вычисляем значение интенсивности точек, попадающих в окрестность точки (х,у) размером СЭ). 6. Если одно из значений интенсивностей, вычисленных на шаге 5, равняется 0, то центр окна bxb располагается в точке (х,у) и всем точкам в массиве, попадающим в это окно, если это операция эрозия присваивается значение 0, или, если это операция наращения 1. 7. Если не одно из значений интенсивностей, вычисленных на шаге 5, не равняется 0,точке (х,у) в массиве присваиваем значение 1. 8. Если x Nx-(b-1)/2 и y Ny-(b-1)/2, тогда выполняем х = х + 1 и идем на шаг 2. 9. Если x = Nx — (b-\)/2 и y Ny-{b-\)l2, тогда выполняем x = (b-1)/2, у-у + 1 и идем на шаг 2. 10. Конец алгоритма.
Таким образом, при реализации алгоритма количество операций присвоения точке значения интенсивности будет пропорционально лишь количеству точек в форме умноженное на размер структурирующего элемента. Отличительной особенностью алгоритма в данном случае является тот факт, что в нем исключены операции поиска минимального или максимального элемента внутри структурирующего элемента.
Аналогичный подход используется для модификации алгоритмов операций размыкания и замыкания [78, 80] для бинарных изображений. Смысл морфологических операций размыкания и замыкания заключается в том, что размыкание подавляет острые выступы и прорезает узкие перешейки вХ(рис. 1.2), а замыкание заполняет узкие заливы и малые отверстия. Эти операции обеспечивает следующая модификация алгоритма выполнения операций размыкания и замыкания для бинарных изображений.
Выделение области расположения символов на изображении
Предлагаемый алгоритм выделения области расположения символов на изображении основывается на выделении границ с помощью оператора Собеля, выделяющего вертикальные границы. Данный алгоритм включает в себя следующие этапы: 1. Выделение на изображении вертикальных границ с помощью оператора Собеля. 2. Бинаризация. 3. Выделение пластины номерного знака автомобиля.
Выделение вертикальных границ на изображении начинается со сканирования входного изображения окном размером 3x3:
Окно перемещается попиксельно слева направо и сверху вниз по всему изображению и для точки, оказавшейся в центре окна, вычисляется новое значение интенсивности по формуле:
Новое значение интенсивности записывается в массив размером равным размеру изображения. Далее осуществляется бинаризация изображения. Бинаризация полученного изображения основывается на сравнении интенсивности каждого пикселя с пороговым значением интенсивности; если значение интенсивности пикселя выше значения интенсивности порога, то данному пикселю присваивается значение 255, или в противном случае 0.
Порог Р вычисляется по следующей формуле: /max, /min вычисляются во время выделения границ на изображении пузырьковым методом: изначально /тах приравнивается -1, /min приравнивается 256. Затем /max, /min каждый раз сравниваются с I(i,j), если Imax I(i,j), то 1так присваивается значение I(i,j), если Imm I(i,j), то /min присваивается значение I(i,j).
Выделение пластины номерного знака автомобиля на полученном изображении начинается со сканирования входного изображения окном размером равным предполагаемому размеру номерной пластины на изображении. Окно перемещается попиксельно слева направо и сверху вниз по всему изображению. Внутри окна вычисляется количество точек с интенсивностью 255, затем вычисляется отношение количества данных точек и площади сканирующего окна и сравнивается с пороговым значением. Если данное отношение превышает заданное пороговое значение, то данная область изображения определяется как область кандидат на содержание пластины номерного знака автомобиля. Экспериментально было установлено, что данный порог равен 0.35. Затем, для уменьшения количества областей кандидатов на содержание пластины номерного знака автомобиля одной и той же номерной пластины, координаты верхнего левого угла определенной области кандидата сравниваются с координатами верхнего левого угла выделенных областей. Если разница между координатами по оси абсцисс или между координатами по оси ординат меньше 1/3, тогда сравнивается количество точек с интенсивностью 255 этих областей и сохраняется область, содержащая наибольшее количество точек. Таким образом, на выходе алгоритма получаем координаты областей кандидатов на содержание пластины номерного знака автомобиля.
Далее для того чтобы исключить возможность неполного захвата номерной пластины, осуществляется увеличение области выделения изображения на 1/20 ширины пластины по ширине в правую и левую стороны и на 1/4 высоты пластины по высоте вверх и вниз.
Затем на исходном изображении по новым координатам выделяется область кандидат на содержание пластины номерного знака автомобиля и передается для выделения отдельных символов и их распознавания.
Предлагаемый алгоритм выделения отдельных символов на изображении основывается на построении ГПСИ в соответствии с подходом, описанным в разделе 2.2. Данный алгоритм включает в себя следующие этапы: 1. Выделение строки символов на пластине номерного знака. 2. Выделение отдельных символов.
Выделение строки символов на пластине номерного знака. Для того, чтобы отделить строку символов от всего изображения строится 31 ГПСИ, каждый из которых строится под заданным углом. По оси ординат ГПСИ откладывается значение средней интенсивности, а по оси абсцисс значение точки пересечения прямой с осью ординат сканируемого изображения. Сканирование осуществляется по пикселям расположенным вдоль прямой проходящей под заданным углом, при этом вычисляется значение средней интенсивности пикселей лежащих вдоль этой прямой. Во время сканирования выбирается и запоминается максимальное значение средней интенсивности и соответствующий угол данному ГПСИ. Затем выбирается наибольшее значение из всех максимальных значений средней интенсивности и по соответствующим этому значению ГПСИ и углу осуществляется выделение строки символов следующим образом
