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

ВВЕДЕНИЕ

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

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

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

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

Цель работы: разработка алгоритма повышенной точности для оптического распознавания символов с изображений паспортов за счет комбинирования методов предварительной обработки с использованием библиотеки OCR Tesseract и словарного контроля полученных результатов.

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

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

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

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

4. Реализовать рабочий прототип приложения, способный распознавать данные с паспортов граждан

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

Глава 1. Материалы и методология

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

1.1 Оптическое распознавание символов

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

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

1.2 Процесс распознавания символов

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

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

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

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

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

Шаблонные и структурные алгоритмы распознавания[12,13], применяемые во многих современных системах, малоэффективны при зашумленности изображения, а также из-за отсутствия поддержки русского языка. Поэтому была сделана попытка создания подобного приложения путем комбинирования собственных методов предобработки с использованием библиотеки OCR (tesseract, CuneiForm, и д.р).

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

Рис.1 Процесс обработки поступающего документа

Учитывая перечисленные выше недостатки исходных изображений, перед непосредственным распознаванием графического файла алгоритмами распознавания необходимо провести как можно более тщательную предварительная обработка входящего документа, направленную на улучшение качества изображения[16, 23, 26]. Данная процедура включает в себя ротацию изображения, преобразование в используемый системой формат (в основном это 8-битное изображение переведенное градации серого), последующую фильтрацию изображения от шумов, локальное повышение резкости и контрастности необходимых участков. Подготовленное изображение отправляется на вход модуля сегментации областей интереса. Задачей данного модуля является нахождение и определение основных структурных единиц текста - строк и слов. Выделение фрагментов наивысших уровней, таких как строки и слова, может быть осуществлено на основе анализа промежутков между тёмными областями на бинаризованном изображении. Однако такой подход не может быть успешно применен для выделения отдельных букв в силу особенностей написания или различных искажений. Изображения соседних букв могут объединяться в одну компоненту связанности как показано на рисунке 2, в данной ситуации велика вероятность того, что «нн» будет принято за «м», или за «ии».

Рис. 2. Объединение нескольких букв в одну компоненту связанности

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



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

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

1.3 Обзор существующих приложений по оптическому распознаванию символов

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

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

1.3.1 Abbyy FineReader

FineReader - коммерческий продукт для оптического распознавания символов разработанный российской компанией ABBYY и безусловный лидер в сфере оптического распознавания символов. В основе FineReader запатентованная технология оптического распознавания символов ABBYY OCR, которую лицензируют такие мировые гиганты как Fujitsu, Panasonic, Xerox и Samsung. Программа позволяет переводить изображения печатных документов во множество электронных редактируемых форматов. Начиная с версии 12, она поддерживает распознавание текста на 190 языках, имеет встроенную проверку орфографии для 48 из них, способна сохранять исходное форматирование документа, имеет большой набор функций для предварительной обработки изображения, позволяет проводить настройку множества параметров. Но основным ее преимуществом является почти безукоризненная точность распознавания. По некоторым данным, после тщательного обучения система может распознавать рукописный текст, однако ее нужно будет учить под почерк каждого конкретного пользователя. На данный момент программа насчитывает более 20 миллионов пользователей по всему миру.

1.3.2 CuneiForm

CuneiForm - система оптического распознавания текстов российской компании CognitiveTechnologies. Изначально программа CuneiForm была разработана компанией CognitiveTechnologies как коммерческий продукт. CuneiForm поставлялся в комплекте с некоторыми моделями сканеров. Однако после нескольких лет перерыва в разработке, 12 декабря 2007 года анонсировано открытие исходных текстов программы, которое состоялось 2 апреля 2008 года. На данный момент CuneiForm позиционируется как шрифтонезависимая система преобразования электронных копий бумажных документов и графических файлов в редактируемый вид с возможностью сохранения структуры и гарнитуры шрифтов оригинального документа в автоматическом или полуавтоматическом режиме. Система включает в себя две программы для одиночной и пакетной обработки электронных документов.

1.3.3 OCRopus

OCRopus - система оптического распознавания символов, изначально направленная на преобразование в электронный вид большого объема документов на базе собственного распознающего ядра, начиная с версии 0.4. Это программный пакет для распознавания текста, развивающийся по принципам OpenSource и распространяющийся под лицензией ApacheLicense 2.0. Программа позволяет подключать дополнительные модули для анализа макета содержимого, предварительного улучшения изображения. По задумке разработчиков, с помощью OCRopus станет возможным определять текстовое содержимое на графических файлах построчно и переводить его в обычный текстовый формат для дальнейшего редактирования. Помимо печатного текста, программа сможет распознавать и рукописные материалы. По состоянию на альфа-релиз, OCRopus использует код языка моделирования из другого проекта, поддерживаемого Google - OpenFST. OCRopus в настоящее время доступна только для GNU/Linux. В настоящее время OCRopus использует только интерфейс командной строки, принимая указания на входные изображения с текстом, и выводя данные в формате hOCR (открытый формат на основе HTML), TXT.

1.3.4 Tesseract

Tesseract - одноименная со своим ядром распознавания, свободно распространяемая программа для распознавания текстов, разрабатывавшаяся Hewlett-Packard с середины 1980-х по середину 1990-х, а затем на 10 лет проект был приостановлен.[10,20] В августе 2006 года компания Google выкупила ее и открыла исходные тексты под лицензией Apache 2.0 для продолжения работы над перспективным проектом. В настоящий момент программа работает с UTF-8, поддержка языков (включая, русский с версии 3.0) осуществляется с помощью установки и настройки дополнительных модулей. Использует интерфейс командной строки. Начиная с версии 3.04, выпущенной в 2015 году работает с более чем 100 языками.

1.3.5 Выявленные недостатки приложений

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

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

2. Приложения не способны работать в фоновом режиме, кроме FineReader(добавлено в последней версии 12)

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

4. Отсутствие графического интерфейса пользователя у некоторых решений

5. Ни одна из программ не демонстрирует 100% результата и идеального сохранения форматирования

1.4 Основные трудности распознавания символов

Существуют различные проблемы, связанные с распознаванием символов. Наиболее существенны следующие:

1. Разнообразие языков, символов, и способов изображать их. Многие языки обладают похожими буквами: «N» и «И», «R» и «Я» и др. В каждом языке имеются символы, обладающие схожими чертами друг с другом и цифрами. Например, в русском языке: «М», «Н», «И» и «О» и «0», и т.д.

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

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

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

Искажения цифровых изображений текстовых символов могут быть вызваны следующими причинами[26]:

1. Шумами печати, в частности, непропечаткой (разрывами слитных черт символов), «слипанием» соседних символов, пятнами и ложными точками на фоне вблизи символов и т. п.

2. Смещением символов или частей символов относительно их ожидаемого положения в строке

3. Изменением наклона символов

4. Искажением формы символа за счет оцифровки изображения с «грубым» дискретом

5. Эффектами освещения (тени, блики и т. п.) при съемке камерой.

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

Многие проблемы, описанные выше, можно устранить на этапе предобработки(1, 2, 3)[23, 26].

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

1.5 Методы распознавания символов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.6 Tesseract OCR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.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, короткие, тонкие линии - это признаки, извлеченные из неизвестного символа, а тонкие длинные линии являются сегментами полигональной аппроксимации, используемой в прототипе обученных данных. Один прототип не совпадает с двумя связанными признаками, но в этом прототипе находит свое отражение каждое из этих свойств по отдельности. Получается, что при сравнении малых признаков с более крупными прототипами, можно добиться хороших результатов при обработке поврежденных символов. Основная проблема данного подхода в том, что это требует высоких вычислительных мощностей для сравнения неизвестного элемента и прототипа.

Признаки, извлеченные из неизвестного символа, определяются тремя направлениями (xposition, yposition, angle), с 50-100 признаками на символ, а признак прототипа определяется 4-мя направлениями (xposition, yposition, angle, length), с 10-20 свойствами на конфигурацию прототипа.

1.6.9 Классификация

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

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

1.6.10 Обучение данных

В виду того, что классификатор способен различать поврежденные символы, классификатор не был обучен с использованием искаженных символов. Для обучения применялось объединение 20 образцов по 94 символах одного размера в 8 различных шрифтах, но с 4 атрибутами (жирный, обычный, курсивный, жирный курсивный). Таким образом, было 60160 образцов для обучения. Разительное отличие от других классификаторов, таких как Calera, с более чем миллионом образцов и Baird - 100 шрифтовый классификатор с 1175000 элементами для обучения.

1.6.11 Лингвистический анализ

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

1.6.12 Адаптивный классификатор

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

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

Рис. 13. Слово в базовых линия, и нормализованные по моменту буквы

1.7 Фильтр Гаусса (gaussianblurring)

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

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

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

Уравнение распределения Гаусса в N измерениях имеет вид:

,

Шумоподавление при помощи прямоугольного фильтра имеет существенный недостаток: пиксели на расстоянии «r» от обрабатываемого оказывают на результат тот же эффект, что и соседние.

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

,

где «r» -- это радиус размытия, «r2» = «u2» + «v2» , «у» -- стандартное отклонение распределения Гаусса. В случае двух измерений - эта формула задает поверхность, имеющей вид концентрических окружностей с распределением Гаусса от центральной точки. Пиксели, где распределение отлично от нуля используются для построения матрицы свертки, которая применяется к исходному изображению. Значение каждого пикселя становится средне взвешенным для окрестности. Исходное значение пикселя принимает наибольший вес (имеет наивысшее Гауссово значение), и соседние пиксели принимают меньшие веса, в зависимости от расстояния до них. В теории, распределение в каждой точке изображения будет ненулевым, что потребовало бы вычисление весовых коэффициентов для каждого пикселя изображения. Но, на практике, когда рассчитывается дискретное приближение функции Гаусса, не учитывают пиксели на расстоянии свыше 3у, т.к. они достаточно малы. Таким образом, программе, фильтрующей изображение, достаточно рассчитать матрицу d6уeЧd6уe, чтобы гарантировать достаточную точность приближения распределения Гаусса.

Для применения данного фильтра используется свертка по функции:

Параметр у задает степень размытия. На графике функция с у = 5



Рис. 13

Результаты свертки по функции Гаусса и по константной функции (усреднения).

Рис. 14

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

1.8 Алгоритм Канни

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

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

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

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

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



Рис. 15

Точка «А» - грань (вертикальное направление). Направление градиента - нормаль для этой грани. Точки «В» и «С» лежат на векторе градиента. Поэтому т. «А» сравнивается с ними, чтобы проверить, является ли она локальным максимумом. Если да, то переходят к следующей стадии, иначе она обнуляется.

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

min_Val = 0.66*[среднее значение],

max_Val = 1.33*[среднее значение],

где «cреднее значение» - это усредненная величина интенсивности пикселей для вашего изображения в «оттенках серого».

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

Рис. 16. Верхний и нижний пороги интенсивности

Рис. 16а. Верхний и нижний пороги интенсивности

Грань «А» выше «max_Val» - она точно является гранью. Грань «C» ниже максимума, но соединена с гранью «А», поэтому тоже является гранью - мы получили полную кривую. Грань «В» же лежит ниже максимума, но не соединена ни с гранью «А», ни с гранью «C», поэтому она не является гранью. Для получения корректного результата, весьма важно, правильно выбрать эти пороги. На этой стадии, также удаляются шумы на краях граней



Рис. 17. Пример обработки изображания алгоритмом Канни

Глава 2. Описание разработанной системы

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

2.1 Общее описание приложения и принципа его работы

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

· Номер

· Ф.И.О.

· Дата и место рождения

· Пол

· Дата регистрации

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

· Пользовательский интерфейс

· Модуль ротации изображения;

· Модуль локализации данных

· Модуль распознавания;

· Внешняя база данных

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

2.2 Tesseract

Для решения задачи распознавания образов предлагаю использовать OCR модуль для Python: Tesseract.Python-tesseract это обертка для Tesseract-OCR выкупленного Google. Данный модуль может принимать на вход все типы изображений поддерживаемые PythonImagingLibrary, включая jpeg, png, bmp, tiff. В то время как tesseract-OCR по умолчанию поддерживает только tiff и bmp.

2.3 Исходные данные

Данная программа работает с изображением скана паспорта (см. рис. 10)



Рис.18. Исходное изображение

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

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

1. Переводим изображение в оттенки серого



Рис. 19. Изображение в оттенках серого

2. Сглаживаем шум на границах при помощи фильтра Гаусса

3. Находим границы изображения при помощи алгоритма Канни

Рис. 20. Результат работы алгоритма Канни

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

5. Находятся все необходимые линии(как на самом изображении паспорта, так и на границах: изображение подложка)



Рис. 21. Результат обнаружения линий на изображении

6. Находим углы для всех линий

7. Кластеризируем углы по двум центрам

8. Выбираем кластер с большим количеством элементов

9. Находим угол для ротации (подразумеваем, что изображение обладало отклонением от 0 до 90 градусов)

10. После предыдущего пункта могут появиться неотфильтрованные области (не содержащие изображения паспорта) - отрезаем их



11. Получаем финальное изображение

Рис. 22. Финальное изображение

2.5 Распознавание данных

2.5.1 Выделение границ нахождения данных

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

Обнаружение зон интересующей информации:

1. Бинаризация изображения[5]

Рис. 23. Бинаризация изображения

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



Рис. 24 Получение контуров

3. Сортировка областей интереса (предполагаемое место нахождения информации) в паспорте

Рис. 25 Области интереса

4. Группировка областей по линиям, сортировка по площадям, высотам и расстояниям между областями

5. Разделение областей в поля

Рис. 26 Необходимые поля

2.5.2 Алгоритм локальной адаптивной бинаризации

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

2. Порог «T» в центральном пикселе окна вычисляется по формуле:

T = m - kб(m - M), б = 1 - , R = max(s),

где «m» - минимальное значение интенсивности пикселя изображения в «оттенках серого» в окне, «k» - константа, установленная равной 0.2, «M» - минимальное значение интенсивности пикселя во всем изображении в «оттенках серого», «S» - стандартное отклонение, «R» - максимальное из стандартных отклонений по всем окрестностям.