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

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

ду^чо-'"--

Г

Афонасенко Анна Владимировна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И ПРОГРАММНЫЕ СРЕДСТВА РАСПОЗНАВАНИЯ СТРУКТУРИРОВАННЫХ СИМВОЛОВ

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

АВТОРЕФЕРАТ

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

Томск - 2009

003464696

Работа выполнена в Томском государственном университете (ТГУ) и Томском государственном университете систем управления и радиоэлектроники (ТУ СУР)

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

Калайда Владимир Тимофеевич

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

Светлаков Анатолий Антонович (ТУ СУР)

доктор технических наук профессор Сырямкин Владимир Иванович (Томский политехнический университет)

Ведущая организация: Институт вычислительного модели-

рования СО РАН, г. Красноярск

Защита состоится «19» марта 2009г. в 16 ч. 30 м. на заседании диссертационного совета Д 212.268.02 в Томском государственном университете систем управления и радиоэлектроники по адресу: 634050, г. Томск, пр. Ленина, 40, ауд. 203

С диссертацией можно ознакомиться в библиотеке Томского государственного университета систем управления и радиоэлектроники

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

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

диссертационного совета и!л /

к.т.н., доцент <у\/У^/Г Мещеряков Р. В.

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

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

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

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

Исходя из вышеописанного, была сформулирована основная цель диссертации: разработка методов, алгоритмов и программ распознавания символов, инвариантных к аффинным и проективным преобразованиям.

Основные задачи диссертации:

1. Исследование методов построения алгоритмов распознавания структурированных символов.

2. Разработка метода распознавания структурированных символов инвариантного к аффинным и проективным преобразованиям.

3. Реализация и исследование работоспособности и эффективно-

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

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

Научные положения, выносимые на защиту.

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

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

3. Быстрые морфологические преобразования, сокращающие в

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

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

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

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

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

ется в ЗАО «Томский лечебно-диагностический комплекс» как составная часть распределенной системы безопасности «БАЗИС» для оперативного контроля транспортных средств на территории предприятия.

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

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

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

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

Основное содержание диссертации отражено в 9 научных работах (в том числе в 4-х научных статьях в журналах из перечня ВАК, 5 докладах на конференциях различного уровня).

Основные научные результаты работы докладывались и обсуждались на следующих конференциях: X Международная научная конференция, посвященная памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнева, Сибирский гос. аэрокосмический университет имени академика М.Ф. Решетнева (г. Красноярск, 2006); V Международная научная конференция «Информационные технологии и математическое моделирование», ТГУ (Томск, 2006); XLV Международная научная студенческая конференция «Студент и научно-технический прогресс», НГУ (Новосибирск, 2007); Всероссийская конференция молодых ученых «Наука. Технологии. Инновации» НГТУ (Новосибирск, 2007); VII Международная научная конференция «Информационные технологии и математическое моделирование», ТГУ (Томск, 2008).

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

Внедрение результатов. Методы, алгоритмы и программы,

разработанные при выполнении диссертационной работы, использовались при выполнении работ по гранту РФФИ № 06-08-00751 «Методы и средства проектирования, создания и администрирования распределенных вычислительных систем, обработки и анализа изображений».

Результаты работы внедрены в Томском государственном университете, Томском государственном университете систем управления и радиоэлектроники.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 84 наименований. Общий объем работы составляет 106 страниц, в том числе 25 рисунков.

Основное содержание работы

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

В первой главе проведено исследование методов распознавания структурированных символов и существующих в настоящее время программных систем распознавания.

В первом разделе рассмотрены классические и морфологические методы описания символов. К классическим методам относятся структурный, признаковый и шаблонный.

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

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

Признаковые методы базируются на том, что изображению ставится в соответствие N - мерный вектор признаков. Распознава-

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

Морфологический анализ формы изображений был разработан J. Serra и Пытьевым Ю.П. в 60-е годы XX века. Он позволяет дать количественное описание особенностей геометрической структуры.

Пусть R и Z представляют соответственно множества действительных и целых чисел, и пусть Е представляет ¿/-мерное непрерывное пространство R*, (d = 1,2,3, ... ) или дискретное пространство ZJ. Тогда ¿/-мерный сигнал можно представить как функцию области RJ (непрерывной) или zd (дискретной), диапазон, которой составляет либо R - при непрерывном изменении амплитуды, либо Z - при квантованном изменении амплитуды. Двоичные сигналы могут быть представлены с помощью множеств. Например, изображение на рис. 1 представляет двоичный сигнал, в котором область белого фона может быть выражена через 0, а заштрихованная зона через 1. Сигнал может быть также представлен множеством X точек, соответствующих заштрихованной зоне. Сер-ра использует представление действительной ¿/-мерной функции /(х), где х означает ¿/-мерный вектор, с помощью ансамбля его d-мерных пороговых множеств, определяемых как

где амплитуда а полностью перекрывает Л или 2, в зависимости от того, имеет ли сигнал f непрерывный или квантованный диапазон.

Рис. 1 Эрозия, наращение, размыкание и замыкание X с помощью диска В, центрированного относительно начала координат. Штриховые области соответствуют внутренности множеств, сплошная черная линия обозначает границы преобразуемых множеств, а пунктирная линия— границу исходного множества Л".

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

(1)

Исходный сигнал

Эрозия Наращение Размыкание Замыкание

5с£ есть компактное множество малого размера и простой формы (например, ¿/-мерная сфера). Множество В называется структурирующим элементом (СЭ). Пусть X ±Ь = {х±Ь:хеХ} выражает

векторный переносXна ±ЬеЕ . Фундаментальными морфологическими операторами для множеств являются наращение ф и эрозия О X с помощью В, которые определяются как

Х®В = \]Х+Ъ = {х+Ъ:хеХ andbeB),

ЬеВ

XOB = [\X-b = {z\(B + z)<^X}.

bsB

Другие операторы определяются как комбинации эрозии и наращения. Например, два дополнительных фундаментальных оператора - размыкание о и замыкание *Х с помощью В - определяются как

ХоВ = (ХОВ)®В, Х*В = (Х®В)ОВ.

Эрозия приводит к уменьшению множества X, а наращение - к его увеличению (рис. 1). Размыкание подавляет острые выступы и прорезает узкие перешейки в X, тогда как замыкание заполнят узкие заливы и малые отверстия.

Описанный набор операторов может быть разными способами обобщен на многоуровневые сигналы, представляемые действительно-значимыми функциями. Серра использовал представление ¿/-мерной функции /(х) набором ее пороговых множеств (1). При этом операция наращения всех пороговых множеств функции / с помощью одного и того же компактного множества В дает множества Та (/) ® В, которые являются пороговыми множествами новой функции f® В, называемой наращением функции / с помощью В. Эта новая функция может быть вычислена либо из (1) как (/Ф В){х) = max {а :х е Ta(f)@ В}, либо из прямой эквивалентной формулы

(/©B)(*) = max{/(x-j)}. (2)

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

(/О В)(х) = mm {/(*+>>)}. (3)

Размыкание и замыкание функции/с помощью В определяются как f°B = (fOB)®B и /•B = (f@B)OB. Обнаружение пиков, холмов и долин. Вычитание из входного сигнала / его размыкания с помощью множества В дает выход, состоящий из пиков сигнала, опора которого не может содержать В. В этом и состоит введенное Мейером преобразование:

P(f) = f~(f°B). (4)

Поскольку /°B<f, P(f) всегда неотрицательный сигнал, и тем самым гарантируется, что он содержит только пики. Если цель состоит в обнаружении холмов, определяемых как области, где сигнал существенно более интенсивен, чем окружающий фон, то холм можно идентифицировать как двоичную форму или множество В, которое является опорой соответствующего пика в функции, выражающей интенсивность изображения. Форма опоры пика, получаемая с помощью (4), зависит от формы В, тогда как масштаб пика зависит от размера В.

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

у (/) = (/• В)-/ (5)

реализует обобщенный процесс генерирования долин.

Во втором разделе первой главы рассмотрены современные программные системы распознавания печатных символов: системы оптического распознавания текстов и системы оптического распознавания маркировки поверхности различных объектов. Рассмотрены их функциональные возможности и технология распознавания структурированных символов на примере популярных систем ABBYY FineReader и Авто-Инспектор компании ISS. Анализ различных систем показал, что все они обладают одним существенным недостатком - чувствительность к значительным аффинным и проективным искажениям.

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

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

В первом разделе второй главы рассмотрены методы выделения области расположения символов на изображении и предложена модификация метода, основанного на выделении границ.

В качестве оператора выделения границ предложено использовать оператор Собеля, выделяющий вертикальные границы. Преобразование Собеля заключается в использовании окна размером 3x3:

А Л Л

F0J) 4

А А А4

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

/(и)=И'

где Г = [4,+2Д + A2]-[A6+2As + А4],

Д, - значение интенсивности п- го пикселя,

I(i,j) - новое значение интенсивности точки с координатами (;,/).

Затем осуществляется бинаризация полученного изображения, основанная на сравнении интенсивности каждого пикселя с пороговым значением интенсивности; если значение интенсивности пикселя выше значения интенсивности порога, то данному пикселю присваивается значение 255, или в противном случае 0. Порог Р вычисляется по следующей формуле:

2

где 11тп - максимальное значение интенсивности изображения, 1тт - минимальное значение интенсивности изображения.

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

Во втором разделе второй главы рассмотрены методы выделения отдельных символов и предложена модификация метода, основанного на построении графика проекции средней интенсивности (ГПСИ).

Для того, чтобы отделить строку символов от всего изображе-

ния, предлагается вычислить горизонтальный ГПСИ (рис. 2). Т. к. на изображении самой яркой областью является фон номерной пластины, то два наибольших максимума будут соответствовать областям 1 и 2.

Рис. 2 Построение горизонтальной ГПСИ. Заштрихованным областям 1 и 2 соответствуют два наибольших максимума горизонтальной ГПСИ. х - номер строки изображения, у - средняя интенсивность строки изображения.

При регистрации изображение номерных пластин подвергается аффинным и проективным искажениям рис. 3, следовательно, линии, соответствующие областям 1 и 2, будут располагаться не по горизонтали, а под неизвестным углом. В связи, с чем предлагается строить не один ГПСИ, а п ГПСИ, каждый из которых строится не по горизонтали, а под заданным углом.

Рис. 3 Изображение номерной пластины, подверженной аффинным и проективным искажениям.

Необходимое количество ГПСИ определяется условием регистрации изображений. По данным условиям угол разворота изображения не превышает 15° по горизонтали как в правую, так и в левую сторону, следовательно, « = 31. Из п построенных ГПСИ выбирается тот ГПСИ, который содержит наибольшее значение по у, т. к. наибольшее значение будет соответствовать области 1 или 2 (рис. 4). Затем, по ГПСИ находятся два максимума, имеющих наибольшие значения по у и соответствующие им значения по х, между этими значениями будет находиться строка символов на изображении, расположенная под углом, соответствующем полученному ГПСИ (рис. 4).

п=-13

Рис. 4 Изображение номерной пластины, его ГПСИ, построенный под углом -13", и выделенная область изображения по ГПСИ, содержащая строку символов.

Для выделения символов в полученной области изображения применяются операции, выполняемые при построении вертикального ГПСИ, только ГПСИ строится под углом, взаимно перпендикулярным к п. Полученное изображение символа приводится к оп-

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

Для того, чтобы учесть искажения, вносимые аффинными и проективными преобразованиями, в третьем разделе предлагается включить в систему базовых морфологических операторов следующие операторы: верхний залив (ВЗ), правый залив (ПЗ), нижний залив (НЗ), левый залив (ЛЗ) и озеро (О). Данные операторы позволяют получить описание символов в виде топологических особенностей, инвариантных к аффинным и проективным преобразованиям.

Представим изображение символов в виде множества X точек, соответствующих заштрихованной зоне (рис. 5). Применим операцию замыкание к множеству X на рис. 5, а с помощью СЭ В и рассмотрим результат на рис. 5, б. Области, выделенные серым цветом, назовем соответственно, область 1 - верхний залив, 2 - правый залив, 3 - нижний залив, 4 - левый залив и область 5 - озеро. Затем применим операцию генерация долин (5) к исходному множеству X рис. 5, а. Таким образом, области, выделенные серым цветом на рис. 5, б, есть не что иное, как результат операции генерации долин (рис. 5, в). Обозначим заливы двумя штрихами на части контура залива, которая не примыкает к символу (рис. 5, г). Также введем определение пролива (П) как область, которая имеет не примыкающие контуры к символу с нескольких сторон. Таким образом, для ВЗ штрихи будут сверху, для ПЗ - справа, для НЗ - снизу, для ЛЗ - слева, рис. 5, г, для П - с нескольких сторон.

(ей ш

УЖ 1 г'

5

а б в г

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

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

Озеро определяется как долина, полученная в результате применения операции генерация долин с помощью СЭ прямоугольной

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

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

В четвертом разделе второй главы предлагается метод распознавания структурированных символов, основанный на применении введенных морфологических операторов.

В качестве описания структуры каждого символа выбирается шестимерный вектор первичных признаков х, состоящий из следующих признаков: д:, - количество ВЗ, хг - количество ПЗ, х, -количество НЗ, х4 - количество ЛЗ, х5 - количество О, х6 - количество П. Вектор признаков х разбивает набор символов класса на двадцать два отдельных подкласса, указанных в табл. 1.

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

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

Из таблицы видно, что при использовании выше описанных признаков в подклассы класса , находящиеся на строках под номерами 1, 3, 4, 6, 7, 12 ,13 ,14 ,23 попадает несколько символов, полученные подклассы обозначаются соответственно , F¡, ,

р> р' р< р> р> р> 1 6 > '7 ' 1 12 ' МЗ > ги > 1 23 "

Разбиение на подклассы множества прописных букв русского алфавита Таблица!

№ Рг

X Подкласс X Подкласс X Подкласс X Подкласс

1 001010 А,Д 001010 А, Р 001010 А 000000 г, т

2 010010 Б 010010 Б, Ь 010010 Б, Р 100000 ц

3 010020 В 010020 В 010020 В 010000 г, с

4 000000 г.т 001000 Г, П 010000 г, с 001000 г,л,п

5 020000 Е 111110 Д 111110 Д 000100 э

6 212100 Ж 020000 Е 020000 Е 000010 о, Р, ь,ъ

7 010100 3 212100 Ж 212100 Ж 101000 и, н, ч,л

101000 и, н, ч 010100 3 010100 3 100100 У

9 111000 к 101000 и, н, л 101000 и, н, ч 100010 ь

10 001000 л, п 111000 к 111000 к 011000 т

11 102000 м 102000 м 001100 л 010100 3

12 000010 о, Р, ь, ъ 000010 о 102000 м 010010 Б, Р, Ь

13 010000 с 010000 с 000010 О 001100 т, л

14 100100 У 001100 т 001000 п 001010 А, Д,Р

15 000020 ф 100100 У 011000 т 000011 ы

16 111100 X 111120 ф 100100 У 111000 к

17 100000 ц 111100 X 111120 ф 110100 ц

18 200000 ш, щ 110100 ц 111100 X 101010 ю

19 000100 э 200000 ш 201000 ц 010110 ъ

20 000011 ы 210100 щ 200000 ш 001110 я

21 101010 ю 000100 э 301000 щ 111100 X

22 001110 я 000011 ы 000100 э 111110 д

23 010110 ъ 100010 ь 200000 ш,щ

24 101010 ю 000011 ы 020000 Е

25 001110 я 010110 ъ 000020 ф

26 101010 ю 102000 м

27 001110 я 010020 в

28 201000 ц

29 111120 ф

30 210100 Щ

31 212100 ж

32 301000 щ

Для определения, к какой из букв относятся полученные при-

знаки, вводится вторичный вектор признаков у, компоненты которого вычисляются после определения к какому из подклассов класса относится распознаваемый символ, состоящий из следующих признаков:

у{ - отношение площадей НЗ к ВЗ, у, = О при отношении меньшем 0.5, у, =1 при отношении стремящемся к 1, у, =2 при отношении больше 1;

уг - отношение площадей ПЗ к О, у2 = 0 при отношении меньшем

0.5, уг = 1 при отношении большем 0.5;

у3 - отношение площадей НЗ к ЛЗ, д>3 = 0 при отношении меньшем

1, уу = 1 при отношении большем 1;

у4 - отношении высоты О к высоте символа, у4 = 0 при отношении стремящемся к 0.5, у4 = 1 при отношении стремящемся к 1; у5 - количество «заливов» и «озер», после применения операции генерация долин к исходному изображению с использованием СЭ в форме отрезка, длиной равного высоте символа, располагающимися под углами 45 и 135 градусов к оси абсцисс, и проведения логического сложение с результатами выполненной ранее операции генерации долин, у5 принимает значение равное количеству «заливов» и «озер»;

у6 - отношение в ВЗ количества пикселей серого цвета в 1-ой строке к количеству серых пикселей во 2-ой строке, количества пикселей серого цвета во 2-ой строке к количеству серых пикселей в 3-ей строке, и так далее до последней строки, в которой есть серые пиксели ВЗ, у6= 0 при плавном возрастаний отношений, у6 = 1 при резком скачке в отношениях или почти при равных отношениях; у1 - расположение О относительно середины символа, уп = 0 при О, располагающемся в верхней части символа, у7 = 1 при О, располагающемся в нижней части символа;

у% - количество «заливов» и «озер» после применения операции генерация долин к исходному изображению с использованием СЭ в форме отрезка, длиной равного высоте символа, располагающегося под углом 45 градусов к оси абсцисс, у3 принимает значение равное количеству «заливов» и «озер»;

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

градусов к оси абсцисс, у9 принимает значение равное количеству ВЗ;

- отношение площади НЗ к площади прямоугольника описывающего символ, ую = 0 при отношении меньшем или равном 0.5, у]а = 1 при отношении большем 0.5;

уп - отношение площади ПЗ к площади прямоугольника описывающего символ, _>>,,= 0 при отношении меньшем или равном 0.5, уи =1 при отношении большем 0.5.

Данный вектор признаков разбивает набор символов на подклассы символов, указанных в табл. 2, где х - данный признак не вычисляется.

Разбиение символов на подклассы по вторичному вектору признаков у Таблица 2

Класс Подклассы У Класс Подклассы У

р: Г xxxxlxxxxxx F' Г ххххххххххО

Т хххх2хххххх С ХХХХХХХХХХ1

Г ххххххххООх Б xlxxxxxxxxx

F; л xxxxxxxxlxx F' гп Р хОххххОхххх

п ххххххххОЧх Ь xOxxxxlxxxx

О xxxlxxxxxxx F' Т ххОхххххххх

р хххОххОхххх Л xxlxxxxxxxx

F6 ь ххх02х1хххх А XXXXXXX2XXX

ъ ххх03х1хххх F' 14 Д хххххххЗххх

и 1 ххххОххххх Р xxxxxxxlxxx

H 1хххх1ххххх F' Г23 Ш хххх2хххххх

ч Охххххххххх Щ XXXX4XXXXXX

л 2ХХХХХХХХХХ

Из табл. 2 видно, что, вычислив вторичный вектор признаков у, однозначно определяется к какому символу относится распознаваемое изображение.

Из табл. 1 и 2 видно, что такие признаки, как количество, полученных в результате операции генерации долин, «заливов», «озер» и «проливов», их взаимное расположение и отношение являются уникальными признаками для каждого символа. Следовательно, данное описание символов может быть использовано в качестве инвариантных признаков к аффинным и проективным преобразованиям при распознавании символов.

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

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

Так как бинарные изображения представлены только двумя градациями яркости, то выбор минимального или максимального элемента, в пределах окна структурирующего элемента, для каждой точки изображения является неэффективным. В этой связи предлагается модификация алгоритма выполнения базовых морфологических операций эрозии и наращения. Полагаем, что форме принадлежат точки с интенсивностью 1, а фону 0. Структурирующий элемент выбираем размером ЬхЬ, Ь = 3, х и у - координаты точки сканирования, № - ширина изображения, ]Яу - высота изображения, '(х>у) ~ значение интенсивности в точке (х,у). Алгоритм включает следующие шаги:

1. Создается массив, такого же типа как изображение, размером ЫххИу, в котором будет содержаться результат операции.

2. Координатам х и у присваиваем значения равные (Ь -1) / 2.

3. Вычисляем значение ¡(х,у).

4. Если г(х,у) = 0, то точке (х,у) в массиве присваиваем значение 0 и идем на шаг 8.

5. Если )(х,у) = 1, тогда вычисляем по очереди значение интен-сивностей следующих точек: (х-1,;у), 1), (х,>>-1),

(* + 1,>>), (х + \,у + \), (х,>> + 1), (х-1,у + 1).

6. Если одно из значений интенсивностей, вычисленных на шаге 5, равняется 0, то центр окна ЬхЬ располагается в точке (х,у) и всем точкам в массиве, попадающим в это окно, если это операция эрозия присваивается значение 0, или, если это операция наращения -1.

7. Если ни одно из значений интенсивностей, вычисленных на шаге 5, не равняется 0,точке (х,у) в массиве присваиваем значение 1.

8. Если х<№-(Ь-1)/2 и у<Ну-(Ь-Х)12, тогда выполняем

х = х+1 и идем на шаг 2.

9. Если х = /Ух - (6 -1) / 2 и у<Ыу-{Ь-\)12, тогда выполняем х-(Ь-\)!2, у = у+1 иидемнашаг2.

10. Конец алгоритма.

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

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

1. Координатам х и у присваиваем значения равные 0, расстояние между точками одинаковой интенсивности к = 0.

2. Вычисляем значение ¡(х, у).

3. Если /(х, у) = 0, идем на шаг 9.

4. Если ¿(х, у) = 1, вычисляем /(х +1, у).

5. Если /(х +1, у) = 0, выполняем к = к +1, х = х+1 и вычисляем значение г(х,у) до тех пор, пока ¿(х,у) не станет равным 1 или пока х не станет равным Ых.

6. Если х = Л^х, тогда к = 0 и идем на шаг 10.

7. Если ¡(х,у) = \ и к<=Ь, тогда всем точкам от (х-к,у) до (х, у) присваиваем значение 1.

8. к = 0.

9. Если х<Их и у<Ыу, х = х + 1 и идем на шаг 2.

10. Если х = Ых и у<Ыу, х = 0, ^ = + 1 и идем на шаг2.

11. Координатам х и >> присваиваем по значению 0, к = 0.

12. Вычисляем значение Цх,у) .

13. Если ¿(х,у) = 0, идем на шаг 19.

14. Если /(х, .у) = 1, вычисляем /'(х,_у + 1).

15. Если ;'(х, у +1) = 0, выполняем к = к +1, у = у +1 и вычисляем /(х, у) до тех пор, пока /(х, у) не станет равным 1 или пока у не станет равным Ыу\

16. Если у = Ыу, тогда к = 0 и идем на шаг 20.

17. Если /(х,х) = 1 и к<=Ь, тогда всем точкам от (х,у-к) до (х, у) присваиваем значение 1.

18. к = 0.

19. Если у<Ыу и х<Ых, у = у+\ и идем на шаг 12.

20. Если у = и х<Ых, х-0, х = х+1 и идем на шаг 12.

21. Конец алгоритма.

Для операции размыкания выполняются те же самые действия, только вместо нуля единица, а вместо единицы ноль.

Рассмотрим морфологические операции генерация пиков и долин. Из формулы (5) следует, что результатом операции генерации долин является разность между замыканием и исходным изображением, т. е. остаются только те точки, которые появились в результате операции замыкания. Следовательно, для получения результата генерации долин необходимо использовать тот же алгоритм, который используется для получения операции замыкания со следующей модификацией. Дополнительно создается массив такого же размера как входное изображение, в него записываются точки, которым присваивается значение единицы на шагах под номерами 7 и 17. Данный массив будет содержать результат операции генерация долин.

Результатом операции генерация пиков (4) является разность между исходным изображением и результатом операции размыкания, т. е. остаются те точки, которые «стираются» в результате реализации операции размыкания. Следовательно, для получения результата генерации пиков необходимо использовать тот же алгоритм, который используется для получения операции размыкания со следующей модификацией. Дополнительно создается массив такого же размера, как входное изображение, в него записываются точки, которым присваивается значение нуля на шагах под номерами 7 и 17. Данный массив будет содержать результат операции генерация пиков.

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

Третья глава посвящена программной реализации разработан-

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

Вся последовательность предложенной технологии распознавания структурированных символов и разработанных в работе алгоритмов послужила основой для создания программного комплекса «Распознавание государственных регистрационных знаков транспортных средств». Структурная схема программы представлена на рис. 6.

/Ввод /

изображения /

Выделение пласшны номерного знака на изображении

Настройка параметров выделения пластины номерного знака

-► Выделение отдельных символов

Настройка параметров выделения JJ^/ббнаружены все\_ Ч символы yS

Распознавание символов

Настройка параметров распознавания

Сохранение настроек

Вывод результатов

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

Программный комплекс реализован в среде Delphi 7. В качестве базовой библиотеки работы с изображениями выбрана интегрированная с Delphi графическая библиотека Graphics32, содержащая большой набор компонентов для работы с изображением.

Программа, разработанная по предложенным алгоритмам, реализована в виде класса, содержащего набор абстрактных типов данных, описывающих изображение и методы работы с этими данными, по методологии объектно-ориентированного программирования.

Оценка качества распознавания проводилась в два этапа.

На первом этапе экспериментальной проверки в качестве тестовых изображений использовался набор из 300 реальных изображений государственных регистрационных знаков транспортных средств образца соответствующего ГОСТ Р 50577 - 93, первой группы, типа 1, визуально различимых на расстоянии 40 м (т.е. для чистых знаков, удовлетворяющих требованиям Венской Конвенции о дорожном движении от 8.11.68).

Результаты тестирования показали, что разработанные методы обеспечивают вероятность распознавания равную 0.98^'°^ с доверительной вероятностью 0.95.

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

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

Введем следующие обозначения: а - угол отклонения по вертикали регистрирующего устройства от перпендикуляра к плоскости регистрируемого объекта, ß - угол отклонения по горизонтали регистрирующего устройства от перпендикуляра к плоскости регистрируемого объекта, в - угол поворота пластины номерного знака на плоскости.

В результате тестирования установлено, что при максимально возможном горизонтальном угле ß = ±50° для достижения вероятности распознавания равной 100% вертикальный угол регистрации а не должен превышать ±30°, и угол поворота на плоскости в не должен превышать ±5°.

При максимально возможном вертикальном угле а - ±50° для достижения вероятности распознавания равной 100% горизонтальный угол регистрации ß не должен превышать ±30°, угол поворота на плоскости в может принимать любые значении из своего воз-

можного интервала.

При максимально возможном угле поворота на плоскости в = ±15° для достижения вероятности распознавания равной 100% горизонтальный угол регистрации /? не должен превышать ±30°, и вертикальный угол а может принимать любые значении из своего возможного интервала.

В результате тестирования установлено, что программная система на основе разработанных в работе алгоритмов обеспечивает вероятность распознавания не менее 98% при следующих условиях регистрации:

- высота символов должна быть не менее 16 пикселей;

- диапазон изменения освещения от 50лк;

- угол отклонения по горизонтали регистрирующего устройства от перпендикуляра к плоскости регистрируемого объекта ±45°;

- угол отклонения по вертикали регистрирующего устройства от перпендикуляра к плоскости регистрируемого объекта ±50°;

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

В заключении приведена сводка основных результатов работы.

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

По результатам исследований можно сделать следующие выводы:

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

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

преобразованиям и таким аффинным искажениям как изменение масштаба, поворот изображения символа.

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

4. Разработанные методы распознавания символов позволили создать программную систему, которая обеспечивает точность распознавания символов не менее 98% и соответствует техническим требованиям.

Рекомендации:

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

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

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

Основные результаты диссертации опубликованы в работах:

1. Афонасенко, A.B. Быстрые алгоритмы коррекции формы изображения / A.B. Афонасенко // Материалы X Международной научной конференции, посвященной памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнева / Сибирский гос. аэрокосмический ун-т им. академика М.Ф. Решетнева. - 2006. - С. 217 - 218.

2. Афонасенко, A.B. Методика построения систем распознавания автомобильного номера / A.B. Афонасенко, А.И. Елизаров// Известия томского политехнического университета. - 2006. -Т. 309.-№ 8.-С.118-122.

3. Афонасенко, A.B. Быстрые морфологические преобразования для задач коррекции и преобразования бинарных изображений / A.B. Афонасенко // Известия Томского политехнического университета. - 2006. - Т. 309. - №8. - С. 122 - 126.

4. Афонасенко, A.B. Быстрые алгоритмы коррекции формы изображения/ A.B. Афонасенко// Материалы V Международной научной конференции «Информационные технологии и математическое моделирование» / Томский гос. ун-т. - 2006. - Ч. 2. -

С. 65-66.

5. Афонасенко, A.B. Программный комплекс поиска и распознавания автомобильных номеров/ A.B. Афонасенко // Материалы XLV Международной научной студенческой конференции «Студент и научно - технический прогресс» / Новосибирский гос. ун-т. - 2007. - С. 102 - 103.

6. Афонасенко, A.B. Распознавание структурированных символов на основании методов морфологического анализа / A.B. Афонасенко // Известия Томского политехнического университета. -2007. -Т. 311.- №5. -С. 119-123.

7. Афонасенко, A.B. Технология распознавания изображения маркировки номерной пластины автомобилей на основании методов морфологического анализа изображения/ A.B. Афонасенко И Материалы всероссийской конференции молодых ученых «Наука. Технологии. Инновации» / Новосибирский гос. тех. ун-т.-2007.-4.1.-С. 7-10.

8. Афонасенко, A.B. Обзор методов распознавания структурированных символов / A.B. Афонасенко, А.И. Елизаров // Доклады Томского государственного университета систем управления и радиоэлектроники. -2008. - Вып. 2(18). -4.1. - С.83 - 88.

9. Афонасенко, A.B. Распознавание изображений символов на основе признаков инвариантных к аффинным и проективным преобразованиям / A.B. Афонасенко, А.И. Елизаров // Материалы VII Всероссийской научно-практической конференции с международным участием «Информационные технологии и математическое моделирование» / Томский гос. ун-т. - 2008. -Ч. 2.-С. 131-132.

Отпечатано в ООО «НИП» ул. Советская, 47, тел.: 53-14-70 Заказ № 464-44. Тираж 100.

Введение.

1. Анализ методов распознавания структурированных символов.

1.1. Методы описания изображений структурированных символов.

1.1.1. Шаблонный метод распознавания.

1.1.2. Структурный метод распознавания.

1.1.3. Признаковый метод распознавания.

1.1.4. Методы морфологического анализа формы изображения.

1.2. Программные системы распознавания структурированных символов.

1.2.1. Системы оптического распознавания текстов.

1.2.2. Системы оптического распознавания маркировки поверхности различных объектов.

Выводы.

2. Распознавание структурированных символов.

2.1. Выделение области расположения символов на изображении.

2.2. Выделение отдельных символов.

2.3. Расширение базовых морфологических операций.

2.4. Построение векторов признаков изображений символов на основании методов морфологического анализа.

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

Выводы.

3. Программная реализация разработанных алгоритмов.

3.1. Обоснование требований к характеристикам программного обеспечения.

3.2. Реализация программы.

3.3. Структура программы.

3.4. Структура системы.

3.4. Алгоритм распознавания символов.

3.5.1. Выделение области расположения символов на изображении.

3.5.2. Выделение отдельных символов.

3.5.3. Распознавание символов.

3.6. Оценка качества распознавания.

Выводы.

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

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

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

Исходя из вышеописанного, была сформулирована цель диссертации: разработка методов, алгоритмов и программ распознавания символов, инвариантных к аффинным и проективным преобразованиям.

Основные задачи диссертации:

1. Исследование методов построения алгоритмов распознавания структурированных символов.

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

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

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

Научные положения, выносимые на защиту.

1. Последовательность преобразований: бинаризация оконтуренного изображения, локализация области расположения символов, выделение отдельных символов и идентификация, обеспечивающая вероятность распознавания символов на уровне 95-98%.

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

3. Быстрые морфологические преобразования, сокращающие в — ( b - размер структурирующего элемента) количество вычислительных операций алгоритмов обработки и коррекции бинарных изображений.

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

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

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

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

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

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

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

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

Основное содержание диссертации отражено в 9 научных работах (в том числе в 4-х научных статьях из перечня ВАК, 5 докладах на конференциях различного уровня).

Основные научные результаты работы докладывались и обсуждались на следующих конференциях: X Международная научная конференция, посвященная памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнева, Сибирский гос. аэрокосмический университет имени академика М.Ф. Решетнева (Красноярск, 2006); V Международная научная конференция «Информационные технологии и математическое моделирование», ТГУ (Томск, 2006); XLV Международная научная студенческая конференция «Студент и научно - технический прогресс», НГУ (Новосибирск, 2007); Всероссийская конференция молодых ученых «Наука. Технологии. Инновации» НГТУ (Новосибирск, 2007); VII Международная научная конференция «Информационные технологии и математическое моделирование», ТГУ (Томск, 2008).

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

Степень достоверности результатов проведённых исследований.

Достоверность результатов, выводов и положений диссертационной работы обеспечивается:

- тщательной разработкой методики и алгоритмов распознавания структурированных символов;

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

Внедрение результатов. Методы, алгоритмы и программы, разработанные при выполнении диссертационной работы, использовались при выполнении работ по гранту РФФИ № 06-08-00751 «Методы и средства проектирования, создания и администрирования распределенных вычислительных систем, обработки и анализа изображений».

Результаты работы внедрены в Томском государственном университете, Томском государственном университете систем управления и радиоэлектроники.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 84 наименований. Общий объем работы составляет 106 страниц, в том числе 25 рисунков.

Выводы

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

- бинаризация оконтуренного изображения;

- локализация области расположения символов;

- выделение отдельных символов;

- распознавание символов.

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

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

Заключение

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

По результатам исследований можно сделать следующие выводы:

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

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

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

4. Разработанные методы и алгоритмы распознавания символов позволили создать программную систему, которая обеспечивает точность распознавания символов не менее 98% и соответствует техническим требованиям.

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

Рекомендации:

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

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

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

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

1. Багдонас, А. Читающее устройство «РУТА 701» / А. Багдонас, и др. // Автоматизация ввода письменных знаков в электронно-вычислительные машины: доклады научно-технического совещания / Вильнюс, 1968. С. 96 -121.

2. Ковалевский, В.А. О корреляционном методе распознавания / В.А. Ковалевский // Читающие автоматы. Киев, 1965. - С. 46-61.

3. Фу, К. Структурные методы в распознавании образов / К.Фу; под ред. М.А. Азейрмана; пер. с англ. Н.В. Завалишина, С.В. Петрова, Р.Л. Шейнина. М.: Мир,1977. - 320с.

4. Котович, Н.В. Распознавание скелетных образов Электронный ресурс. / Н.В. Котович, О.А. Славин. 2006. -Режим доступа: http://ocrai.narod.ru/ skeletrecognize.html

5. Горлов, Д.В. Распознавание изображений на основе признаков, инвариантных к сдвигу, вращению, масштабированию: автореферат на соиск. уч. степ. канд. тех. наук: 05.13.01 / Д.В. Горлов.- Красноярск, 2002. 20 с.

6. Афонасенко, А. В. Обзор методов распознавания структурированных символов / А.В. Афонасенко, А.И. Елизаров // Доклады Томского государственного университета систем управления и радиоэлектроники. —2008. -Вып. 2(18). -Ч.1.-С.83 88.

7. Роджерс, Д., Адаме Дж. Математические основы машинной графики / Д. Роджерс, Дж. Адаме; под ред. Ю.М. Баяковского, В.А. Галактионова, В.В. Мартынова; пер. с англ. П.А. Монахова, Г.В. Олохтоновой, Д.В. Волкова. -М.: Мир, 2001. 604с.

8. Фоли, Дж. Основы интерактивной машинной графики / Дж. Фоли, А. вэн Дэм; под ред. Ю.М. Баяковского; пер. с англ. В.А. Галактионова, Ю.М. Лазутина, О.Н. Родинко. М.: Мир, 1990. - кн.1.- 368с.

9. Павлидис, Т. Алгоритмы машинной графики и обработки изображений. — М.: Радио и связь, 1991. -400с.

10. Шелестов, А.А. Компьютерная график: учеб. пособие / А.А. Шелестов. — Томск: Томский межвузовский центр дистанционного образования, 2001. — 121с.

11. Гашников, М. В. Методы компьютерной обработки изображений / М.В. Гашников. -М.: ФИЗМАТЛИТ, 2003. 784с.

12. Рахманкулов, В.З. Алгоритм распознавания объемных образов на базе модифицированного метода максимальной клики / В.З. Рахманкулов // Сб. науч. тр. / Институт системного анализа РАН. 2002. - С. 23 - 26.

13. Автоматический анализ сложных изображений / под ред. Э.М. Браверманна М.: Мир, 1969. - 310 с.

14. Pavlidis, Т. Algorithms for Graphics and Image Processing. Computer Science Press, Rockville, MD, 1982.

15. Lam, L. Thinning Methodologies: A Comprehensive Survey / L. Lam, S.W. Lee, C.Y. Suen // IEEE Trans. Pattern Analysis and Machine Intelligence. -1992.-Vol.14.- pp.869-885.

16. Plamondon, R. Methodologies for Evaluating Thinning Algorithms for Character Recognition / R. Plamondon and others. // Int'l. J. Pattern Recognition and Artificial Intelligence, special issue thinning algorithms.— 1993.— Vol. 7.-№5.-pp. 1247-1270.

17. Smith, S.J. Handwritten character classification using nearest neighbor in large databases / S J. Smith and others. // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1994. -Vol.22. - № 9. - pp.915-919.

18. Wakahara, T. Shape machine using LAT and its application to hand-written character recognition / T. Wakahara // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1994. - Vol.16. - № 6. - pp.618-629.

19. Lam, L. An Evaluation of Parallel Thinning Algorithms for Character Recognition / L. Lam, C.Y. Suen // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1995. -Vol. 17. - № 9. -pp. 914-919.

20. Plamondon, R. On-Line and Off-Line Handwriting Recognition: A Comprehensive Survey / R.Plamondon, S.Srinari // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2000. - Vol.22. - № 1. - pp.

21. Бутаков, E.A. Обработка изображений на ЭВМ / Е.А. Бутаков, В.И. Островский, И.Л. Фадеев. М.: Радио и связь, 1987. - 240с.

22. Садыков, С.С. Скелетизация бинарных изображений / С.С. Садыков, И.Р. Самандаров // Зарубежная радиоэлектроника. 1985. - №11. - С. 30-37.

23. Семенков, О.И. Методы обработки и формирования растровых изображений / О.И. Семенков, С.В. Абламейко. Минск: Инст. тех. кибернетики АН БССР, 1986.- 105с.

24. Абрамов, Е.С. Моделирование систем распознавания изображений (на примере печатных текстов): дис. на соиск. уч .степ. канд. тех. наук: 05.13.01 / Е.С. Абрамов. М., 2006. - 234 с.

25. Андреев, С.В. Алгоритмическое обеспечение прототипа устройства считывания паспортов и виз Электронный ресурс. / С.В. Андреев [и др.].— 2003. Режим доступа: http://www.keldysh.ru/papers/2003/prep46/ ргерг2003 46.html

26. Котович, Н.В., Проблемы человеко-машинного интерфейса: ввод печатных символов / Н.В. Котович, А.А. Кравченко // Матеметические методы в распознавании образов и дискретной оптимизации. -М., 1990. С. 84-94.

27. Бредихин, Р.Н. Об одном подходе к распознаванию, оптических образов символов. / Р.Н. Бредихин // Вестн. МЭИ. 2005. - №2. - С. 134-141.

28. Дуда, Р. Распознавание образов и анализ сцен / Р. Дуда, П. Харт; под ред. Р.Л. Стефанюка; пер. с англ. Г.Г. Ванштейна, A.M. Васьковского. М.: Мир, 1976.-512с.

29. Ту, Дж. Принципы распознавания образов / Дж. Ту, Р. Гонсалес; под ред. Ю. И. Журавлева; пер. с англ. И.Б. Гуревича. М.: Мир, 1978. - 413с.

30. Белозерский, С.А. Основы построения систем распознавания образов: курс лекций / С.А. Белозерский. Донецк: Дон. Гос. Инст. искусственного интеллекта, 1997. - 120с.

31. Гашников, М.В. Методы компьютерной обработки изображений / М.В. Гашников. -М.: ФИЗМАТЛИТ, 2003. 784с.

32. Горелик, А.Л. Методы распознавания / А.Л. Горелик, В.А. Скрипкин. — М.: Высшая школа, 1977. 222с.

33. Коробейников, А.П. Методы распознавания образов: учеб. пособие / А.П. Коробейников. Ростов-на-Дону: Издательский центр ДГГУ, 1999. -51с.

34. Загоруйко, Н.Г. Методы распознавания и их применение / Н.Г. Загоруйко. -М.: Сов. радио, 1972. 208с.

35. Журавлев, Ю.И. Распознавание. Математические методы. Программная система. Практические применения / Ю.И. Журавлев, В.В. Рязанов, О.В. Сенько. М.: ФАЗИС, 2006. - 176 с.

36. Фукунага К. Введение в статистическую теорию распознавания образов / К. Фукунага; под ред. Пер. с англ. М.: Наука, 1979. -368с.

37. Марагос, П. Морфологические системы для обработки многомерных сигналов/ П. Марагос // Труды института инженеров по электротехнике и радиоэлектронике. 1990.-Т. 78. - N4. - С. 81 - 89.

38. Пытьев, Ю.П. Морфологический анализ изображений/ Ю.П. Пытьев // Докл. АН СССР. 1983.-Т. 269. - N5. - С. 1061 - 1064.

39. Пытьев, Ю.П. Задачи морфологического анализа изображений/ Ю.П. Пытьев // Математические методы исследования природных ресурсов Земли из космоса / Под ред. В. Г. Золотухина. М.: Наука, 1984.-С. 41-83.

40. Электронный ресурс. Режим доступа: http://www.abbyy.ru/finereader

41. Электронный ресурс. Режим доступа: http://www.irislink.com/c2-532/QCR-Software—Product-list.aspx.

42. Электронный ресурс. Режим доступа: http://www.nuance.com/omnipage.

43. Электронный ресурс. — Режим доступа: http://www.cognitive.ru/ products/cuneiform.htm.

44. Электронный ресурс. Режим доступа: http://www.iss.ru/products/auto/

45. Электронный ресурс. Режим доступа: http://www.com.ua/products/ аи-tointelligence/ techdata.php

46. Электронный ресурс. Режим доступа: http://autotrassir.dssl.ru/products

47. Электронный ресурс. Режим доступа: http://www.iss.ru/products/transit/

48. Электронный ресурс. Режим доступа: http://www.escort-center.ru/ рго-duction/details/index.php?id=:13

49. Электронный ресурс. Режим доступа: http://www.tral.ru/tral-parking/ tral-parking /

50. Электронный ресурс. Режим доступа: http://www.dignum.ru/main.css

51. Электронный ресурс. Режим доступа: http://www.rossi-potok.ru/

52. Электронный ресурс. Режим доступа: www.docflow.ru/ analytic full.asp?param=30387

53. Электронный ресурс. Режим дocтyпa.•http://www.iss.ru/products/auto/ technology/

54. Елизаров, А.И. Методика построения систем распознавания автомобильного номера / А.И. Елизаров, А.В. Афонасенко // Известия томского политехнического университета. 2006. - Т. 309. - № 8. - С.118-122.

55. Гришкин, В.М. Сегментирование графических изображений текстов / В.М. Гришкин // Процессы управления и устойчивость: Труды 35-й межвузовской научной конференции аспирантов и студентов / С.-Петерб. университет. 2004. - С. 408-412.

56. Коваленко, Е.Н. Методы выделения номерного знака на изображении Электронный ресурс. / Е.Н. Коваленко, А.В. Сытник. 2006. - Режим доступа: http://visa.net.ua/content/maketO 15.pdf.

57. Анисимов, Б.В. Распознавание и цифровая обработка изображений / Б.В. Анисимов, В.Д. Курганов, В.К. Злобин. М.: Высшая школа, 1983. -295 с.

58. Прэтт, У. Цифровая обработка изображений / У. Прэтт; под ред. Д.С. Лебедева; пер. с англ. Д.С. Лебедева. М.: Мир, 1982. - Т. 1 - 2.

59. Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, В. Вудс; под ред. П.А. Чочиа; пер. с англ. П.А. Чочиа. — М.: Техносфера, 2005. — 1072 с.

60. Хорн, Б.К.П. Зрение роботов / Б.К.П. Хорн; под ред. Е.И. Кугушева, Ю.А. Садова; пер. с англ. И.М. Бродской, ЕЛО. Зуевой, А.Ю. Каргашина.-М.: Мир, 1989.-487 с.

61. Яншин, В.В. Обработка изображений на языке СИ для IBM PC: Алгоритмы и программы / В.В. Яншин, Г.А. Калинин. М.: Мир, 1994. — 240 с.

62. Хемминг, Р.В. Цифровые фильтры / Р.В. Хемминг; под ред. A.M. Трахтмана; пер. с англ. В.И. Ермишина.- М.: Сов. радио, 1980. -224 с.

63. Сойфер, В.А. Компьютерная обработка изображений// Соровский образовательный журнал- 1996. -№2, С. 110-121.

64. Абламейко, С.В. Обработка изображений: технология, методы, применение / С.В. Абламейко, Д.М. Лагуновский. Минск: Амалфея, 2000. - 304с.

65. Фёдоров, А. Бинаризация чёрно-белых изображений: состояние и перспективы развития // Интеллектуальные технологии и системы Электронный ресурс. / Московский государственный университет печати. М. -2002. —

66. Вып. 4. Режим доступа: http://philippovich.ru/Library/Books/ITS/wwwbook/ i st4b/its4/index2 .htm

67. Семенков, О.И. Методы и алгоритмы обработки растровой графической информации / О.И. Семенков, С.В. Абламейко. Минск: Инст. тех. кибернетики АН БССР, 1984. - 116 с.

68. Афонасенко, А.В. Распознавание структурированных символов на основании методов морфологического анализа / А.В. Афонасенко // Известия Томского политехнического университета. 2007. - Т. 311. - №5. - С. 119 -123.

69. Фаворская, М.Н. Морфологическая обработка контурных изображений в системах распознавания текстовых символов / М.Н. Фаворская, А.С. Зотин, А.Н. Горошкин // Вестник СибГАУ. 2007. - Вып. 1(14). -С. 70-75.

70. Ching-Liang, S. Chinese-seal-print recognition by color image dilating, extraction, and gray scale image geometry comparison / Su Ching-Liang // J. Intell. and Rob. Syst. 2005. - № 4. - pp. 349-359.

71. Ping, Z. Documents filters using morphological and geometrical features of characters / Zang Ping, Chen Lihui // Image and Vision Computing. 2001. — vol. 19. - pp. 847-855.

72. Koskinen L. Morphological filtering of noisy images / L. Koskinen, J. Astola // Proc. SPIE. 1990. -Vol. 1360. - pp. 421-426.

73. Soumyakani, C. Application of logical and morphological operation to edge detection of binary and gray level images / C. Soumyakani, R. Mina // J. Opt. (India). 2001.-Vol. 30.-№ l.-pp. 1-9.

74. Mathematical Morphology: 40 Years On // Proceedings of the 7th International Symposium Mathematical Morphology, April 18-20, 2005 / Springer.- Netherlands. Christian Ronse, Laurent Najman, Etienne Decenciere.

75. Афонасенко, A.B. Быстрые морфологические преобразования для задач коррекции и преобразования бинарных изображений / А.В. Афонасенко // Известия Томского политехнического университета. — 2006. Т. 309. -№8.-С. 122-126.

76. Graphics32 a fast graphics library for Delphi. Электронный ресурс. — Режим доступа: http://www.g32.org.

77. Бежанова, M.M. Практическое программирование: Структуры данных и алгоритмы / М.М. Бежанова, JI.A. Москвина, И.В. Поттосин. М.: Логос, 2001.-276с.

78. УТВЕЕЖДАЮ^^^, npd^KTop^lVcyPjioHR^т.н., профессор с \ JEs^ Н. Г. Ремпе ^j^v^ .jl^Aa,^ 2009г. f.1. Л А