Исследование алгоритмов распознавания регистрационных номеров автомобилей

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ГОУ ВПО «Северокавказский государственный технический университет»

Факультет информационных технологий и телекоммуникаций

Допустить к защите»

Заведующий кафедрой ЗИ

А.Ф. Чипига

Курсовая работа

на тему:

Исследование алгоритмов распознавания регистрационных номеров автомобилей

Специальность 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем»

Группа БАС-081

Обозначение курсового проекта

КР-СевКавГТУ-081028-11

Проектировал Н.Е. Киселёв

Руководитель работы Р.А. Воронкин

Ставрополь, 2011

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ГОУ ВПО «Северокавказский государственный технический университет»

Факультет информационных технологий и телекоммуникаций

Кафедра «Защита информации»

«УТВЕРЖДАЮ»

Заведующий кафедрой

А. Ф. Чипига

Задание на курсовую работу

Студент Киселёв Никита Евгеньевич группа БАС-081

1. Тема: Исследование алгоритмов распознавания регистрационных номеров автомобилей утверждена приказом по СевКавГТУ №

2 Срок представления проекта к защите « 20 » июня 2011 г..

3 Исходные данные для проектирования:

Компьютер на базе процессора Intel/AMD с тактовой частотой не менее 1.8 ГГц;

оперативная память не менее 256 Мб, рекомендуется 1024 Мб и выше; монитор с экранным разрешением не менее 1024x768, рекомендуется LCD-монитор 17-19”;

операционная система Microsoft Windows XP SP3 и выше

4 Содержание пояснительной записки

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

4.2 Реализация алгоритмов распознавания регистрационных номеров автомобилей

4.3 Рабочая документация программного продукта

4.4 Заключение

4.5 Библиографический список

4.6 Другие разделы проекта: Приложения (по необходимости)

Дата выдачи задания «13» 2011 г.

Руководитель проекта Р.А. Воронкин

Задание принял к исполнению: Н.Е. Киселёв

Содержание

Содержание

Введение

1. Обзор математических методов распознавания

1.1 Распознавание скелетных образов

1.2 Фонтанное преобразование

1.3 Адаптивное распознавание

1.4 Нейронные сети

1.5 Резюме

2. Программа распознавания автомобильного номерного знака

2.1 Общая архитектура

2.2 Детальное описание алгоритмов

2.2.1 Бинаризация изображения

2.2.2 Удаление обрамления

2.2.3 Сегментация символов

2.2.4 Распознавание символов шаблонным методом

2.3 Резюме

Заключение

Список использованных источников

Приложение 1

Введение

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

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

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

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

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

1 Обзор математических методов распознавания

В общем случае, распознавание текста состоит из следующих процедур и методов (рисунок 1.1):

* предобработка;

* сегментация;

* распознавание.

Рисунок 1.1 ? Основные процедуры и методы распознавания текста

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

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

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

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

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

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

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

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

Также существует множество методов, построенных как синтез трех подходов.

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

1.1 Распознавание скелетных образов

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

Метод Щепина

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

Рисунок 1.2 ? Скелетизация буквы «Ф», состоящей из одного внешнего и двух внутренних контуров. а) исходное изображение; б) удаление одного слоя; в) удаление второго слоя

Скелетизация с применением шаблонов

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

Рисунок 1.3 ? Шаблоны скелетизации

Для подготовки к этапу распознавания в полученном скелете выделяем ключевые точки: точки соединения трех или четырех ребер скелета и концевые точки:

1. Создаем пустой стек для хранения координат начала и конца ребер, точек ветвления скелета.

2. Заносим в него любую точку скелета.

3. Пока стек не пуст, продолжаем шаги 4-7.

4. Выбираем точку из стека.

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

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

7. Если произошло ветвление скелета, то мы нашли место соединения ребер, и в массив заносится последовательность ребер. В стек заносим точку ветвления.

8. Переходим к пункту 3.

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

Волновой метод

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

Метод состоит из следующих шагов:

- построение скелета изображения с помощью сферической волны;

- оптимизация полученного скелета.

Отслеживание линий изображения производится путем отслеживания перемещения центра отрезка, образуемого крайними точками генерации волны (рисунок 1.5,а). После отслеживания возможно сглаживание отрезков.

Рисунок 1.4 ? Прохождение сферической волны по изображению

Выявление увеличения «ширины» волны и разделения волны на дочерние позволяет установить точку предполагаемого соединения двух отрезков. Определение увеличения «ширины» волны производится путем сравнения «ширины» очередной генерации волны и ее среднего значения за N предыдущих генераций (N задается заранее). Причем мы получаем две точки (A,B) трассируемого отрезка. После разделения волны на две полуволны, мы получаем еще две пары точек (C,D) и (E,F). Точка соединения отрезков лежит в шестиугольнике ABCDEF и первоначально устанавливается как центр масс этого многоугольника (рисунок 1.5,б). Коррекция возлагается на оптимизацию скелета изображения.

Рисунок 1.5 ? а) отслеживание линий изображения, б) определение места соединения отрезков

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

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

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

Наиболее часто встречающиеся искажения (рисунок 1.6,а) исправляются с помощью анализа прилежащих к выделенной точке (A) отрезков (AB1, B1C1, AB2, B2C2, AB3, B3C3).

Анализ заключается в поиске такой пары отрезков CxBx, CyBy из (B1C1, B2C2, B3C3), что CxBxByCy максимально коррелируются прямой. Тогда необходимо точку (A) переместить в точку пересечения прямых CxCy и AC2, а затем удалить из графа точки B1, B2, B3. (рисунок 1.6,б).

Другим вариантом искажения является случай соединения трех отрезков в одной точке (рисунок 1.6,в). В этом случае невозможно нахождение пары отрезков коррелируемых прямой. Точка (A) должна быть перенесена в центр треугольника, образуемого прямыми B1C1, B2C2 и B3C3.

Затем точки B1, B2, B3 необходимо удалить из графа (рисунок 1.6,г).



Рисунок 1.6 ? Оптимизация точки соединения отрезков

Само распознавание:

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

1. нормированные координаты особой точки (вершина графа);

2. длина ребра до следующей вершины в процентах от длины всего графа;

3. нормированное направление из данной точки на следующую особую точку;

4. нормированное направление входа в точку, выхода из точки;

5. кривизна дуги, точнее "левая" и "правая" кривизна дуги, соединяющей особую точку со следующей вершиной (кривизна слева и справа). Кривизна вычисляется как отношение максимального расстояния от точек дуги (находящихся соответственно слева/справа от прямой) до прямой, соединяющей вершины, к длине отрезка, соединяющего те же вершины.



Рисунок 1.7 ? Пример топологических признаков

На рисунке 1.7 условно показаны некоторые из топологических признаков. Граф имеет пять особых точек - a0, a1, a2, a3, a4. При обходе графа по маршруту a0 ==> a1 ==> a2... в вершине a1 условно показаны следующие признаки: вектор R1 - направление входа в точку, вектор R2 - направление выхода из точки, вектор R3 - глобальное направление на следующую особую точку. Двунаправленный вектор h показывает величину "левого" отклонения дуги (a1,a2) от прямой; "правое" отклонение равно нулю.

Для некоторых кодов число особых точек и, соответственно, число топологических признаков слишком мало. Так, для кода, соответствующего символу "0", топологических признаков вообще нет, т.к. нет ни одной особой точки. Поэтому могут вычисляться и использоваться следующие дополнительные признаки:

1. размеры и положение компонент и дыр,

2. "черная" и "белая" ширина верхней половины символа,

3. модифицированные прямые прогибы.

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

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

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

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

2. склеить точки скелета, находящиеся на минимальном расстоянии одна от другой;

3. отбросить самую короткую линию (дугу графа); излишние короткие дуги (линии) нередко возникают при рукописном написании;

Рисунок 1.8 ? Попытка улучшения изображения символа. а) исходное изображение символа; б) символ со склеенными линиями

1.2 Фонтанное преобразование

Программисты российской компании ABBYY разработали оригинальные технологии, улучшающие качество распознавания. Идея нового способа хранения знаний о букве ? структурно-пятенный эталон ? впервые появилась на свет в студенческих работах Д. Яна, К. Анисимовича и П. Сенаторова. Технология распознавания с помощью структурно-пятенных эталонов получила название "фонтанное преобразование" (от английского font - шрифт).

Фонтанное преобразование совмещает в себе достоинства шаблонного и структурного методов и позволяет избежать недостатков, присущих каждому из них по отдельности. В основе этой технологии лежит использование структурно-пятенного эталона. Он позволяет представить изображения в виде набора пятен, связанных между собой n-арными отношениями, задающими структуру символа. Эти отношения (то есть расположение пятен друг относительно друга) образуют структурные элементы, составляющие символ. Так, например, отрезок - это один тип n-арных отношений между пятнами, эллипс - другой, дуга - третий. Другие отношения задают пространственное расположение образующих символ элементов. Наглядно это можно представить себе в виде теннисных шаров, нанизанных на резиновый жгут (рисунок 1.9). Шары могут сдвигаться относительно друг друга. Такую связку подвижных шаров можно "натянуть" на различные изображения одного символа, и система становится менее зависимой от шрифтов и дефектов.



Рисунок 1.9 ? Структурно-пятенный эталон буквы «А»

В эталоне задаются:

1. имя;

2. обязательные, запрещающие и необязательные структурные элементы;

3. отношения между структурными элементами;

4. отношения, связывающие структурные элементы с описывающим прямоугольником символа;

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

6. атрибуты, используемые для проверки отношений между элементами;

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

8. позиция, с которой начинается выделение элемента (отношения локализации элементов).

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

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

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

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

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

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

1.3 Адаптивное распознавание

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

К недостаткам данного подхода можно отнести следующие факторы:

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

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

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

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

К недостаткам данного подхода можно отнести следующие факторы:

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

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

Достоинства этого подхода тесно связаны с его недостатками. Основными достоинствами являются следующие:

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

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

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

Математическая модель адаптивного распознавания:

В модели приняты следующие допущения:

1. символы обучающей выборки принадлежат единственному шрифту;

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

3. имеется некий готовый шрифтонезависимый алгоритм с определенным качеством распознавания;

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

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

P ? качество распознавания, полученное на этапе первичного распознавания;

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

F ? финальное качество распознавания достижимое с помощью шрифтозависимого алгоритма, адаптированного к данной выборке символов;

V ? надежность распознавания символа: V= f (x, P), где x - расстояние от данного символа до центра кластера (идеального символа). Функция f является частью конкретного алгоритма вычисления расстояния между символом и кластером.

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

(1)

Тогда по заданной минимальной допустимой надежности Vmin вычислим максимальное расстояние Xmax на которое символ может отклониться от кластера и при котором V ? Vmin:

(2)

Далее по определению функции распределения получаем:

(3)

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

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

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

(4)

xб ? квантиль уровня б;

б ? уровень значимости;

N ? количество символов в кластере.

Это неравенство выполняется с вероятностью 1 ? 2б. Упростим неравенство, учитывая, что p(1 ? p) ? 1/4:

, (5)

с вероятностью не меньшей чем 1 ? 2б. Зададимся количеством символов N=121 (смотри оценку количества букв на странице текста) и предположим

| о - p| ? 0,07, тогда xб = 0,07*2*11 = 1,54 это соответствует уровню значимости 0,0618, и в итоге получаем, что наше предположение выполняется с вероятностью не меньшей чем 1-2*0,0618=0,88. В этом рассуждении не накладывается никаких специфических условий на ячейку, следовательно, вывод справедлив для всех ячеек данного кластера. Таким образом, можно утверждать, что при указанном объеме кластера в почти 90% его ячеек абсолютная погрешность отклонения от модели составит не более 0,07. Фактически вероятность будет даже больше, т.к. благодаря упрощению неравенства мы получили лишь оценку снизу.

Схема работы адаптивного распознавания:

Рассмотрим подробнее схему, объединяющую оба подхода:

Рисунок 1.10 ? Схема работы адаптивного распознавания

При разработке объединенного метода распознавания, информационной единицей, над которой должен работать метод, был выбран уровень одной страницы текста. Т.к. это достаточно крупная единица, для того чтобы собранная статистика была вполне представительна. Например, количество символов на обычной машинописной странице текста ? 2000, относительная частота буквы «н» в русском языке ? 0,053; таким образом, на странице текста количество букв «н» в среднем составляет 2000*0,053=106. Этого вполне достаточно для оценки статистических параметров выборки по данной букве, кластеризации и построения двоичных эталонов для дораспознавания.

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

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



Рисунок 1.11 ? Пример работы метода цепной развертки

Теперь для того, чтобы разделить исходное множество на несколько кластеров таким образом, чтобы расстояние между любыми объектами, входящими в разные кластеры, было больше заданного расстояния d, а для любых объектов из одного кластера (p1,p2) можно было найти объекты из того же кластера (обозначим их o[1], o[2],…,o[n]), такие что o[1]=p1, o[n]=p2, и для любого i<n расстояние между соседними объектами d(o[i],o[i+1]) не больше d, достаточно просто просмотреть все приписанные объектам расстояния и пометить те из них, которые больше d. Пусть это будут номера N1,N2,…,Nk. Тогда к первому кластеру следует отнести объекты с номерами меньше N1, ко второму все объекты с номерами от N1 до N2 и т.д.

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

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

Математическая запись для процесса вычисления оценки сравнения растра с эталоном имеет следующий вид:

(6)

pi ? вероятность в i-ой ячейке эталона,

W ? нормирующий коэффициент,

C ? масштабный коэффициент,

a ? порог, управляющий точностью.

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

1.4 Нейронные сети

Как работает биологическая нейронная сеть:

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

Рисунок 1.12 ? Строение биологического нейрона

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

Нетрудно построить математическую модель описанного процесса.



Рисунок 1.13 ? Математическая модель нейрона

На рисунке 1.13 изображена модель нейрона с тремя входами (дендритами), причем синапсы этих дендритов имеют веса w1, w2, w3. Пусть к синапсам поступают импульсы силы веса x1, x2, x3 соответственно, тогда после прохождения синапсов и дендритов к нейрону поступают импульсы w1 x1, w2 x2, w3 x3. Нейрон преобразует полученный суммарный импульс x = w1 x1 + w2 x2 + w3 x3 в соответствии с некоторой передаточной функцией f (x). Сила выходного импульса равна y = f (x) = f (w1 x1 + w2 x2 + w3 x3). Таким образом, нейрон полностью описывается своими весами wk и передаточной функцией f (x). Получив набор чисел (вектор) xk в качестве входов, нейрон выдает некоторое число y на выходе.

Искусственная нейронная сеть

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

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

Таблица 1.1 ? Формулировка задачи распознавания символов

Задача распознавания букв	Формулировка для нейронной сети
Дано	Растровое черно-белое изображение буквы размером, к примеру, 30Ч30 пикселей.	Входной вектор из 900 двоичных символов (900=30Ч30).
Надо	Определить какая это буква (в алфавите 33 буквы).	Построить нейронную сеть с 900 входами и 33 выходами, которые помечены буквами. Если на входе изображение буквы «А», то максимальное значение выходного сигнала достигается на выходе «А». аналогично сеть работает для всех 33 букв.

Построение нейронной сети

Теперь, когда стало ясно, что именно мы хотим построить, мы можем переходить к вопросу "как строить такую нейронную сеть". Этот вопрос решается в два этапа:

1. Выбор типа (архитектуры) нейронной сети.

2. Подбор весов (обучение) нейронной сети.

На первом этапе нужно выбрать следующее:

1. какие нейроны мы хотим использовать (число входов, передаточные функции);

2. каким образом следует соединить их между собой;

3. что взять в качестве входов и выходов нейронной сети.

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

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

Обучение нейронной сети

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

При обучении нейронной сети мы действуем совершенно аналогично. У нас имеется некоторая база данных, содержащая примеры (набор рукописных изображений букв). Предъявляя изображение буквы «А» на вход нейронной сети, мы получаем от нее некоторый ответ, не обязательно верный. Нам известен и верный (желаемый) ответ - в данном случае нам хотелось бы, чтобы на выходе нейронной сети с меткой «А» уровень сигнала был максимален. Обычно в качестве желаемого выхода в задаче классификации берут набор (1, 0, 0, ...), где 1 стоит на выходе с меткой «А», а 0 - на всех остальных выходах.



Рисунок 1.14 ? Процесс обучения нейронной сети

Вычисляя разность между желаемым ответом и реальным ответом сети, мы получаем 33 числа - вектор ошибки. Алгоритм обратного распространения ошибки - это набор формул, который позволяет по вектору ошибки вычислить требуемые поправки для весов нейронной сети. Одну и ту же букву (а также различные изображения одной и той же буквы) мы можем предъявлять нейронной сети много раз. В этом смысле обучение скорее напоминает повторение упражнений в спорте - тренировку.

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

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

Применение нейронной сети

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

Рисунок 1.15 ? Применение нейронной сети

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

1.5 Резюме

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

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

- шаблонный метод имеет высокую скорость обработки данных;

- имеется априорная информация о единственном возможном шрифте:

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

2 Программа распознавания автомобильного номерного знака

2.1 Общая архитектура

Алгоритм распознавания номерного знака состоит из следующих этапов:

1. Предварительная обработка изображения.

2. Сегментация.

3. Распознавание.

На вход алгоритма подается цветное изображение номерной пластины. Ее размеры в среднем составляют 130x30 пикселей. Само же изображение чаще превышает эти размеры на 10-20 пикселей в ширину и высоту. Поэтому первым этапом является обрезание такой «рамки». Также на первом этапе происходит выравнивание изображения по гистограммам для повышения контрастности и обработка фильтром подчеркивания границ.

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

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

2.2 Детальное описание алгоритмов

2.2.1 Бинаризация изображения

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

На первом этапе цветное изображение превращается в черно-белое и представляется в градациях серого (рисунок 2.1). Для каждого пикселя вычисляется его яркость в пределах от нуля до 255. Уровню яркости 0 соответствует черный цвет, уровню 255 ? белый. Таким образом, для хранения изображения приходится один байт на пиксель. Яркость пикселя вычисляется по одной из следующих формул:

, (7)

, (8)

где R, G, B ? нормированный на 256 (один байт) красный, зеленый и голубой компонент цвета пикселя соответственно.

Рисунок 2.1 ? а) цветное изображение, б) черно-белое изображение

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



Рисунок 2.2 ? Бинаризация, а) исходное изображение, б) 25% черных пикселей, в) 50% черных пикселей, г) 75% черных пикселей

Алгоритм бинаризации изображения:

1. Создаем одномерный массив I из 256 элементов (от 0 до 255). Заполняем его нулями.

2. Пробегаем попиксельно все изображение. Увеличиваем на единицу значение в ячейке массива I, соответствующей яркости пикселя i (I[i]++). В итоге, значение каждой ячейки массива I[i] будет равно количеству пикселей яркости уровня i на всем изображении.

3. На этом шаге определяется порог яркости a. Пусть N ? общее количество пикселей (высота, умноженная на ширину), k ? коэффициент, определяющий количество черных пикселей. Тогда kN будет равно желаемому количеству черных пикселей на бинарном изображении. Суммируем значения ячеек массива, начиная с нулевой до тех пор, пока значение этой суммы не превысит kN. Индекс последней суммируемой ячейки и будет порогом a.

4. Повторно пробегаем попиксельно все изображение. Сравниваем уровень яркости каждого пикселя с порогом a. Если этот уровень меньше или равен a, то пиксель становится черным, иначе ? белым.

2.2.2 Удаление обрамления

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

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

Рисунок 2.3 - Бинаризация исходного изображения

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

Алгоритм обрезания вертикальной темной части изображения слева:

1. Начинаем с самой первой левой вертикальной линии пикселей.

2. Подсчитываем количество черных пикселей в линии.

3. Если это количество превышает 75% высоты изображения, то линия удаляется, текущей становится следующая полоса справа, переходим к шагу 2.



Рисунок 2.4. Номерной знак с тенью сверху, а) исходное изображение, б) бинарное изображение

Затем обрезаем темные области сверху и снизу. Если на исходном изображении на номерной пластине есть тень (обычно это тень сверху от бампера, решетки радиатора, «кенгурятника»), то часть символов, на которые падает тень, будет обрезана (рисунок 2.4). Эта проблема решается при распознавании, смещением эталона относительно символа на изображении. Ниже приводится алгоритм для обрезания темной части изображения сверху, аналогичным образом отсекается нижняя темная часть изображения.

Алгоритм обрезания горизонтальной темной части изображения сверху:

1. Исходной является линия пикселей, проходящая ровно через середину изображения по горизонтали.

2. Подсчитываем количество черных пикселей в линии.

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

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

Результатом работы двух, выше описанных, процедур является обрезанное исходное изображение (рисунок 2.5,в).

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

Рисунок 2.5 ? Результат обрезания темной части, а) исходное изображение, б) обрезание бинарного изображения, в) обрезанное исходное изображение

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

Рисунок 2.6 ? Дополнительное обрезание

Алгоритм поиска нижней границы символов:

1. Исходная горизонтальная линия пикселей проходит через середину изображения.

2. Подсчитывается число слитных групп черных пикселей в линии s.

2.1. Начинаем с самого левого пикселя линии, s равно нулю.

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

2.3. Продолжаем движение влево до первого встретившегося белого пикселя, переходим на шаг b. Если достигнем правого края изображения, то переходим на следующий шаг алгоритма

3. Если линия пересекает символы, то s будет порядка десяти, текущей становится следующая линия изображения по направлению вниз, переходим на шаг 2. Иначе, алгоритм добрался до светлой полосы и s резко падает до 0-3, завершаем работу алгоритма.

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

Рисунок 2.7 ? а) исходное изображение, б) вырезанная номерная пластина

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

Полученное число является яркостью соответствующего пикселя в новом изображении (рисунок 2.8).

Рисунок 2.8 ? Фильтрация

Пример фильтрации приведен на рисунке 2.9.

Рисунок 2.9 ? а) исходное изображение, б) обработанное фильтром подчеркивания границ изображение

Профильтрованное изображение подвергается процедуре бинаризации (рисунок 2.10) и передается на сегментацию.

Рисунок 2.10 ? Изображение, готовое к сегментации

2.2.3 Сегментация символов

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