Дипломная (вкр): Оптическое распознавание символов

1.5.1 Структурные методы

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

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

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

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

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

1.5.2 Шаблонные методы

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

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

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

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

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

1.5.3 Признаковые методы

Данные методы базируются на том, что изображению ставится в соответствие N-мерный вектор признаков. Распознавание заключается в сравнении его с набором эталонных векторов той же размерности. Принятие решения о принадлежности образа тому или иному классу, на основании анализа вычисленных признаков, имеет целый ряд строгих математических решений в рамках вероятностного подхода. Тип и количество признаков в немалой степени определяют качество распознавания. Формирование вектора происходит во время анализа изображения. Данную процедуру называют извлечением признаков. Эталон для каждого класса получают путем аналогичной обработки символов обучающей выборки.

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

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

1.5.4 Нейросетевые методы

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

Достоинствами метода являются: способность к обобщению, высокая скорость работы.

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

1.6 Tesseract OCR

 - модуль оптического распознавания образов с открытым исходным кодом, был разработан HP в промежутке между 1984 и 1994 годами. В 1995 был представлен как инновация на The Fourth Annual Test of OCR Accuracy - тест точности решений OCR, и показал выдающиеся результаты. После этого проект был заморожен[20].

Поскольку HP обладает технологией анализа содержимого страницы, которая используется в продуктах компании, Tesseract никогда не нуждался в своей системе подобного анализа. Tesseract предполагает, что получает на вход бинаризацию изображения с заданными регионами текста[10, 12]. Распознавание происходит в 2 шага. На первом, происходит попытка распознать каждое слово по очереди. Каждое слово передается классификатору являясь его обучающими данными. Благодаря этому адаптивный классификатор получает возможность более точно распознать текст, лежащий ниже на странице. Чтобы сделать распознавание более точным в начале страницы, второй прогон следует за первым из-за того, что классификатор способен обучиться полезной информацией завершения первого шага. В этой ситуации, слова, которые были недостаточно хорошо распознаны, обрабатываются повторно. Финальный этап удаляет случайные пробелы, и находит текст, написанный малыми прописными. Основная часть данной работы состоит в разработке приложения с использованием системы OCR Teseract.

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

.        Обладает открытым исходным кодом

.        Показывает прекрасные результаты при работе с чёрно-белым текстом

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

.        Обладает обширной документацией.

.        Способен к тесной интеграции с библиотеками компьютерного зрения (openCV).

Ниже будут рассмотрены методы работы Tesseract подробнее.

1.6.1 Метод обнаружения линий

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

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

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

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

1.6.2 Метод выбора базовой линии

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

Рис. 6. Определенные линии

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

.6.3 Определение фиксированного шага и сегментация слов

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

Рис. 8. Слово, сегментированное с определённым шагом

1.6.4 Обнаружение слов

Не фиксированные шаги, или пропорциональные пробелы - очень нетривиальная задача. Рисунок 8 демонстрирует типичные проблемы. Разрыв между десятками и единицами в «11.9%» похож на обычный пробел, и является больше чем разрыв между «erated» и «junk». Здесь нет горизонтального разрыва между «of» и «financial». Tesseract решает большинство этих проблем измеряя пробелы в фиксированном вертикальном пределе между базовой линией, и центральной линией строки. Пробелы, которые слишком близки к порогу на этой стадии становятся нечеткими, поэтому финальное решение может быть совершено другим после распознания слов.

Рис.9. Строки со сложными для обработки разрывами

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

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

1.6.6 Разделение соединенных символов

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

Рис. 10. Возможные точки сегментации

Рисунок демонстрирует набор точек разделения со стрелками, и выбранный участок разделения, как линию на границе, где «r» касается «m».

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

1.6.7 Распознавание поврежденных символов

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

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

Рис. 11. Пример легко распознанного слова

Когда «А*» поиск был впервые разработан в 1989 году, точность Tesseract для обработки искаженных символов была наголову выше, чем коммерческие разработки того времени. Значительная часть успеха работы заключается в классификаторе образов, который способен с легкостью распознавать поврежденные элементы.

1.6.8 Статический классификатор символов

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

Рис. 12. Четкий, искаженный и совпадающий по признакам прототип

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