Системы распознавания текста
Обзор систем оптического распознавания изображений: ABBYY Finereader, SimpleOCR, FreeOCR, Microsoft Office Document Imaging. Алгоритм распознавания образов: захват кадра; предварительная обработка (предобработка); локализация и распознавание объекта.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 08.06.2019 |
| Размер файла | 583,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство образования Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования
Воронежский государственный технический университет
Кафедра систем информационной безопасности
РЕФЕРАТ
на тему:
«Системы распознавания текста»
Выполнил: студент гр. КБ-11
Чупраков А. Р.
Воронеж 2018
1. История развития
В 1929 году Gustav Tauschek получил патент на метод оптического распознавания текста в Германии, а в 1935 в США. Машина Таушека представляла собой механическое устройство, которое использовало шаблоны и фотодетектор.
В 1950 году David H. Shepard, криптоаналитик из агентства безопасности вооружённых сил Соединённых Штатов, проанализировав задачу преобразования печатных сообщений в машинный язык для обработки компьютером, построил машину, решающую данную задачу. После того как он получил патент США, он сообщил об этом в «Вашингтон Дэйли Ньюз» (27 апреля 1951) и в «Нью - Йорк Таймс» (26 декабря 1953). Затем Шепард основал компанию, разрабатывающую интеллектуальные машины, которая вскоре выпустила первые в мире коммерческие системы оптического распознавания символов.
Первая коммерческая система была установлена на «Ридерс Дайджест» в 1955 году. Вторая система была продана компании «Стандарт Ойл» для чтения кредитных карт для работы с чеками. Другие системы, поставляемые компанией Шепарда, были проданы в конце 1950 - х годов, в том числе сканер страниц для национальных воздушных сил США, предназначенный для чтения и передачи по телетайпу машинописных сообщений. IBM позже получила лицензию на использование патентов Шепарда.
Примерно в 1965 году «Ридерс Дайджест» и «Ар-Си-Эй» начали сотрудничество с целью создать машину для чтения документов, использующую оптическое распознавание текста, предназначенную для оцифровки серийных номеров купонов «Ридерс Дайджест», вернувшихся из рекламных объявлений. Для печати на документах барабанным принтером «Ар-Си-Эй» был использован специальный шрифт OCR - A. Машина для чтения документов работала непосредственно с компьютером RCA 301 (одна из первых полупроводниковых ЭВМ). Скорость работы машины была 1500 документов в минуту: она проверяла каждый документ, исключая те, которые она не смогла обработать правильно.
Почтовая служба Соединённых Штатов с 1965 года для сортировки почты использует машины, работающие по принципу оптического распознавания текста, созданные на основе технологий, разработанных исследователем Яковом Рабиновым. В Европе первой организацией, использующей машины с оптическим распознаванием текста, был британский почтамт. Почта Канады использует системы оптического распознавания символов с 1971 года. На первом этапе в центре сортировки системы оптического распознавания символов считывают имя и адрес получателя и печатают на конверте штрих-код. Он наносится специальными чернилами, которые отчётливо видимы в ультрафиолетовом свете. Это делается, чтобы избежать путаницы с полем адреса, заполненным человеком, которое может быть в любом месте на конверте.
В 1974 году Рэй Курцвейл создал компанию «Курцвейл Компьютер Продактс», и начал работать над развитием первой системы оптического распознавания символов, способной распознать текст, напечатанный любым шрифтом. Курцвейл считал, что лучшее применение этой технологии -- создание машины чтения для слепых, которая позволила бы слепым людям иметь компьютер, умеющий читать текст вслух. Данное устройство требовало изобретения сразу двух технологий -- ПЗС планшетного сканера и синтезатора, преобразующего текст в речь. Конечный продукт был представлен 13 января 1976 во время пресс-конференции, возглавляемой Курцвейлом и руководителями национальной федерации слепых.
В 1978 году компания «Курцвейл Компьютер Продактс» начала продажи коммерческой версии компьютерной программы оптического распознавания символов. Два года спустя Курцвейл продал свою компанию корпорации «Ксерокс», которая была заинтересована в дальнейшей коммерциализации систем распознавания текста. «Курцвейл Компьютер Продактс» стала дочерней компанией «Ксерокс», известной как «Скансофт».
Первой коммерчески успешной программой, распознающей кириллицу, была программа «AutoR» российской компании «ОКРУС». Программа начала распространяться в 1992 году, работала под управлением операционной системы DOS и обеспечивала приемлемое по скорости и качеству распознавание даже на персональных компьютерах IBM PC/XT с процессором Intel 8088 при тактовой частоте 4,77 МГц. В начале 90-х компания Hewlett - Packard поставляла свои сканеры на российский рынок в комплекте с программой «AutoR». Алгоритм «AutoR» был компактный, быстрый и в полной мере «интеллектуальный», то есть по-настоящему шрифтонезависимый. Этот алгоритм разработали и испытали ещё в конце 60-х два молодых биофизика, выпускники МФТИ -- Г. М. Зенкин и А. П. Петров. Свой метод распознавания они опубликовали в журнале «Биофизика» в номере 12, вып. 3 за 1967 год. В настоящее время алгоритм Зенкина-Петрова применяется в нескольких прикладных системах, решающих задачу распознавания графических символов. На основе алгоритма компанией Paragon Software Group в 1996 была создана технология PenReader. Г.М Зенкин продолжил работу над технологией PenReader в компании Paragon Software Group. Технология используется в одноименном продукте компании.
В 1993 году вышла технология распознавания текстов российской компании ABBYY. На её основе создан ряд корпоративных решений и программ для массовых пользователей. В частности, программа для распознавания текстов ABBYY FineReader, приложения для распознавания текстовой информации с мобильных устройств, система потокового ввода документов и данных ABBYY FlexiCapture. Технологии распознавания текстов ABBYY OCR лицензируют международные ИТ-компании, такие как Fujitsu, Panasonic, Xerox, Samsung, EMC и другие.
2. Обзор систем оптического распознавания изображений
Оптическое распознавание символов (OCR) - перевод изображений рукописного, машинописного или печатного текста в текстовые данные, использующие для представления символов в компьютере (например, в текстовом редакторе).
Распознавание широко используется для конвертации книг и документов в электронный вид, автоматизации систем учёта в бизнесе или публикации текста в интернете. Распознанный текст может быть отредактирован, его удобно хранить, осуществлять поиск слов или фраз, демонстрировать или распечатывать материал, не теряя качества, анализировать информацию, а также применять к тексту электронный перевод, форматирование или преобразование в речь. Оптическое распознавание изображений, содержащих текст, является широко исследуемой проблемой на стыке областей распознавания образов, искусственного интеллекта и компьютерного зрения.
На стадии подготовки и обработки информации, особенно при компьютеризации предприятия, автоматизации бухучета, возникает задача ввода большого объема текстовой и графической информации в персональный компьютер. Основными устройствами для ввода графической информации являются: сканер, факс - модем, реже, цифровая фотокамера. Кроме того, используя программы оптического распознавания текстов, можно вводить в компьютер (оцифровывать) также и текстовую информацию. Современные программно - аппаратные системы позволяют автоматизировать ввод больших объемов информации в компьютер, используя, например, сетевой сканер и параллельное распознавание текстов на нескольких компьютерах одновременно.
2.1 ABBYY Finereader
ABBYY Finereader - программа для распознавания текста, позволяет быстро и точно (до 98% на «чистых» изображениях) переводить изображения документов и PDF - файлы в электронные редактируемые форматы без необходимости перепечатывания.
Программа позволяет переводить изображения документов (фотографий, результатов сканирования, PDF - файлов) в электронные редактируемые форматы. В частности, в Microsoft Word, Microsoft Excel, Microsoft Powerpoint, Rich Text Format, HTML, PDF/A, searchable PDF, CSV и текстовые (plain text) файлы. Начиная с 11 версии файлы можно сохранять в формате djvu. Версия 12 поддерживает распознавание текста на 190 языках и имеет встроенную проверку орфографии для 48 из них.
2.2 SimpleOCR
SimpleOCR - это популярное бесплатное программное обеспечение для распознавания текста на английском и французском языках. Стоит отметить, что если документы содержать разметку с несколькими колонками, нестандартные шрифты, цветные изображения или изображения в низком качестве, в таком случае потребуется скачать одно из четырех платных приложений для программы распознавания.
Программа может работать с документами на английском и французском языках, но не сможет распознать символы с различными надстрочными и подстрочными знаками (например, ц, д, й и т.д.), используемые только в других языках.
SimpleOCR - простая программа для распознавания текста, но, к сожалению, программа не рассчитана на работу с русским языком. При необходимости получения более широкого функционала потребуется приобретение платных дополнений.
2.3 FreeOCR
FreeOCR - бесплатная программа для распознавания отсканированного текста. Она работает только с файлами изображений, но и с PDF - файлами и непосредственно со сканером. Для сканирования необходим только подключенный сканер. Для установки данной утилиты необходим доступ к интернету, т.к. запускаемое приложение весит около 150 Кб, дополнительные базы и словари скачиваются во время работы из сети Интернет. В общей сложности программа займет на жестком диске не более 11 Мб. Основным плюсом программы является ее полная автоматизация и отсутствие каких - либо настроек. Поддерживаются форматы JPG, GIF, TIFF BMP и PDF (только первая страница, в скором времени обещают поддержку первых 10 страниц). Так же существует лимит на 10 изображений в час. Утверждается, что система способна распознавать большинство восточноевропейских языков, в том числе русский и украинский. Поддержка русского языка была анонсирована в октябре 2010 года для движка Tesseract 3.0.
2.4 Microsoft Office Document Imaging
Microsoft Office Document Imaging (MODI) - компонент, входящий в состав пакета Microsoft Office и служащий для распознавания и редактирования документов, отсканированных в Microsoft Office Document Scanning. Впервые появился в Microsoft Office XP и включается в последующие версии пакета, в том числе Office 2007. Не доступен, начиная с Office 2010. Для установки Document Imaging в Office 2010 Microsoft выпустила пакет SharePoint Designer 2007.
MODI может читать и писать небольшие изображения формата TIFF. Он также может сохранять распознанный текст в оригинальный TIFF - файл. По умолчанию движок OCR требует правильной ориентации страницы при распознавании. Если вызвать метод objectname.save (), он может записать исправленное положение страницы в исходный файл.
Имеет невысокую точность распознавания символов, кроме того, предъявляет высокие требования к качеству входных изображений.
2.5 OCRFeeder
OCRFeeder -- программа, предоставляющая графический интерфейс пользователя для нескольких систем оптического распознавания символов, таких как CuneiForm, Tesseract, GOCR и Ocrad. OCRFeeder является свободно распространяемой программой для операционной системы Linux.
Используемые компоненты:
1) PIL -- библиотека Python для работы с изображениями.
2) Unpaper -- для обработки изображений.
3) ReportLab -- для импорта PDF - файлов.
4) PyGTK и Libgnome -- для графического интерфейса.
5) PyeEnchant («привязка» Enchant для Python) и PyGtkSpell («привязка» GtkSpell для Python) -- для проверки орфографии.
Функции:
1. Графические форматы ввода данных: PNG, JPEG, BMP, TIFF, GIF, Portable anymap (PNM, PGM, PBM, PPM) и другие. Импорт PDF - файлов.
2. Форматы вывода данных: текстовый файл, , ODT, HTML, PDF.
3. Обработка изображений для улучшения качества распознавания - фильтры шумов, чёрного цвета и оттенков серого; и другие виды обработок, доступных для Unpaper (компонента для обработки изображений).
4. Ручное выделение блоков на странице.
5. Проверка орфографии.
6. Получение изображений со сканера посредством программы SANE.
7. Распознавание нескольких изображений по порядку за один проход
(пакетное распознавание).
3. Сравнение систем оптического распознавания изображений
Представленные OCR - системы являются наиболее популярными и известными, однако ввиду активного развития области распознавания, подобных систем существует очень мало. Проведем сравнительный анализ по приведенным выше системам оптического распознавания символов.
Для оценки качества OCR - систем существуют различные критерии оценки качества. Поток всех операций, входящий в процесс оптического распознавания, можно разделить на два этапа, которые с большой значимостью влияют на конечный результат: это структурный анализ и распознавание текста. Для каждого этапа существуют собственные оценки качества.
1) Оценка результатов структурного анализа документов;
2) Оценка результатов распознавания по эталоном;
3) Оценка результатов распознавания без эталонов.
Имеется ряд существенных проблем, связанных с распознаванием рукописных и печатных символов. Наиболее важные из них:
1. Разнообразие форм начертания символов;
2. Искажение изображения символов;
3. Вариации размеров и масштаба символов.
В таблице 1 представлено сравнение систем по приведенным проблемам и с учётом способов оценки качества:
Таблица 1 - Сравнение систем на предмет решения типовых проблем
|
Система |
Форма и начертания символов |
Искажение изображений |
Вариации размеров и масштаба |
|
|
Finereader |
Да |
Нет |
Да |
|
|
SimpleOCR |
Да |
Нет |
Да |
|
|
FreeOCR |
Да |
Нет |
Нет |
|
|
MODI |
Нет |
Да |
Да |
|
|
OCRFeeder |
Да |
Да |
Нет |
Из таблицы 1 видно, что ни одна из систем наиболее полно не решает приведенные проблемы. При передаче в обработку изображения низкого качества, имеющего символы с искаженной формой велика вероятность ошибочного распознавания.
Так как OCR - системы обладают и техническими характеристиками, как и любое другое ПО, следует провести сравнение по данным параметрам (Таблица 2) . Некоторые из приведенных программ уже сравнивались раннее.
Таблица 2 - Сравнение OCR - систем по техническим параметрам
|
Название |
Последний релиз |
Лицензия |
ОС |
Количество языков |
Выходной формат |
|
|
Finereader |
2014 |
Требуется покупка |
Windows, Linux, Mac OS X Online |
198 |
DOC, DOCX, XLS, XLSX, PPTX, RTF, PDF, HTML, CSV, TXT, ODT, DjVu, EPUB, FB2 |
|
|
SimpleOCR |
2008 |
Бесплатная |
Windows |
20+ |
- |
|
|
FreeOCR |
2012 |
Бесплатная |
15+ |
- |
||
|
MODI |
2007 |
Требуется покупка |
Windows |
30+ |
OmniPage |
|
|
OCRFeeder |
2009 |
Бесплатная |
Linux |
20+ |
- |
Представленные системы, как уже было сказано ранее, относятся к списку наиболее известных и широко распространенных OCR - систем. Существует ряд рейтингов, определяющих лучшие системы распознавания изображений. Согласно данным рейтингам, одной из лучших программ считается ABBYY FineReader. Так же, в списки попадали MODI, FreeOCR, SimpleOCR.
4. Анализ методов распознавания
Общий алгоритм распознавания образов состоит из следующих этапов:
1) захват кадра;
2) предварительная обработка (предобработка);
3) локализация объекта;
4) распознавание объекта.
оптический распознавание обработка кадр
Рисунок 1 - Общий алгоритм распознавания образов
На первом этапе происходит разделение видеопоследовательности на кадры (сцены) для дальнейшей обработки. На этапе предобработки происходит коррекция освещенности полученного изображения, устранение смазывания, бинаризация. При выполнении этапа 3 под локализацией (детектированием, обнаружением) понимают анализ изображения с целью обнаружения объекта и определения его координат. Детектирование объекта является частным случаем распознавания, но при этом решается задача двухклассовой классификации, где один класс - «объект», второй - «не объект».
Детектирование от распознавания отличается тем, что детектирование - это этап выделения искомого объекта на изображении, а распознавание - идентификация содержимого. На последнем этапе область, содержащую объект, необходимо распознать, то есть отнести ее к одному из множества классов. Например, идентифицировать детектированное лицо или распознавать символы в детектированном документе, удостоверяющем личность. Отметим, что в памяти компьютера изображение представляется двумерной матрицей пикселей A размером mЧn, в которой каждый пиксель представлен некоторым неотрицательным числом:
* от 0 до 255, если изображение в градациях серого;
* (от 0 до 255)Ч3, если изображение цветное (компоненты R, G, B).
По кадру видеопоследовательности требуется определить, если он есть, список прямоугольников, содержащих объекты a:
rectanglei = {x, y, w, h, б},
где x, y - координаты центра i - го прямоугольника, w - ширина, h - высота, б - угол наклона прямоугольника к вертикальной оси изображения.
Таким образом, можно выделить основные методы для решения общей задачи распознавания данных:
1. методы, основанные на шаблонах;
2. методы с использованием контурных моделей;
3. нейросетевые методы;
4. метод Виолы - Джонса;
5. k ближайших соседей.
4.1 Методы, основанные на шаблонах
Наиболее распространенным методом, основанном на шаблонах, является метод, основанный на вычислении коэффициента корреляции между двумя матрицами. Рассмотрим метод распознавания объектов на изображении на основе использования коэффициента корреляции. В данном случае необходимо кроме исходного изображения иметь также изображение распознаваемого объекта. Такое изображение будем называть эталонным. Как было сказано ранее, изображение представлено в памяти компьютера матрицей. Пусть A - матрица исходного изображения, B - матрица эталона, размеры матриц mЧn, тогда коэффициент корреляции вычисляется по формуле:
где и - средние значения элементов матриц. Необходимо помнить, что корреляция вычисляется для матриц одинакового размера, поэтому из большей матрицы исходного изображения необходимо вырезать части, которые равны матрице эталонного изображения. Этот подход получил довольно широкое распространение. Однако при распознавании реальных объектов корреляционный метод характеризуется большой вычислительной сложностью. Связано это с масштабированием и поворотами распознаваемого изображения. Еще одним подходом может быть применение цветовой сегментации. На практике этот метод применяется в задаче поиска цвета кожи человека на изображении. Здесь в качестве шаблона выступает образец цвета. Цвет, как известно, есть не физическое свойство объекта, а свойство человеческого восприятия, поэтому строгого математического определения понятия “цвет кожи” не существует, что представляет собой некоторую трудность при построении систем автоматического распознавания кожи. В компьютерном представлении изображения цвет пикселя задается в качестве координат в некотором цветовом пространстве. Было установлено, что в глазе человека присутствует три типа светочувствительных клеток, настроенных на различные распределения энергии по видимому спектру. Исходя из этого факта любой цвет, воспринимаемый человеческим глазом, можно представить в виде трехмерного вектора.
Выделим основные недостатки цветовой сегментации:
1. Зависимость цвета от условий съемки (например, освещения);
2. Зависимость получаемых цветовых значений объектов от конкретной камеры;
3. Многообразие оттенков кожи.
Таким образом, методы данной категории не могут являться полноценным решением задачи распознавания образов в документах удостоверяющих личность. На практике их используют для модификации существующих методов с целью получения дополнительных признаков на этапе предобработки.
4.2 Методы с использованием контурных моделей
Самым популярным методом выделения контуров является метод пространственного дифференцирования, основанный на оценке скорости изменения (градиента) яркости для каждой точки наблюдаемого изображения. Если яркость меняется достаточно быстро, то точка находится на границе двух областей разной яркости, то есть принадлежит контуру. Операторы пространственного дифференцирования являются, по существу, высокочастотными фильтрами. Чаще всего используются маски операторов Собеля, Превитта или Робертса, которые для случая выделения горизонтальных перепадов (вычисления gy (i, j)) имеют вид:
Оператор Собеля - это дискретный дифференциальный оператор, вычисляющий приближенное значение градиента яркости изображения. Маски операторов Собеля и Превитта для выделения вертикальных перепадов яркости (вычисления gx(i, j)) получаются из одноименных масок для выделения горизонтальных перепадов путем транспонирования, а маска оператора Робертса - поворотом на 90є по часовой стрелке. Получаемый в результате массив g(i, j) называют градиентным изображением. Далее осуществляется пороговая обработка градиентного изображения по правилу:
где Т - постоянный или меняющийся в зависимости от локальных свойств изображения порог. В результате получается бинарное изображение b(i, j), единичные точки которого соответствуют потенциальным граничным точкам исходного изображения. Главной причиной популярности методов, основанных на использовании масок пространственного дифференцирования, является простота их реализации на ЭВМ. Также, следует выделить преобразования Робертса и Собеля, которые так же основаны на использовании классификатора Хаара, которые будут использоваться на этапе сегментации (выделения текстовых блоков) и секторизации (выделения символов на текстовых блоках).
4.3 Нейросетевые методы
В отличие от методов первой и второй категории, нейросетевые методы предлагают иной подход к решению задачи распознавания образов. Архитектура и функционирование нейронных сетей (НС) имеют биологические прообразы.
Веса в нейронной сети не вычисляются путём решения аналитических уравнений, а подстраиваются различными оптимизационными методами (например, разновидностями градиентного спуска) при обучении. Обучаются нейронные сети на наборе обучающих примеров. В процессе обучения НС происходит автоматическое извлечение ключевых признаков, определение их важности и построение взаимосвязей между ними. Обученная НС может успешно применять опыт, полученный в процессе обучения, на неизвестные образы за счёт хороших обобщающих способностей. Под нейронными сетями (НС) подразумеваются вычислительные структуры, которые моделируют простые биологические процессы, обычно ассоциируемые с процессами человеческого мозга. Адаптируемые и обучаемые, они представляют собой распараллеленные системы, способные к обучению путем анализа положительных и отрицательных воздействий.
Элементарным преобразователем в данных сетях является искусственный нейрон или просто нейрон, названный так по аналогии с биологическим прототипом. С математической точки зрения искусственный нейрон -- это сумматор всех входящих сигналов, применяющий к полученной взвешенной сумме некоторую простую, в общем случае, нелинейную функцию, непрерывную на всей области определения. Обычно данная функция монотонно возрастает. Полученный результат посылается на единственный выход. Искусственные нейроны (в дальнейшем нейроны) объединяются между собой определенным образом, образуя искусственную нейронную сеть. Каждый нейрон характеризуется своим текущим состоянием по аналогии с нервными клетками головного мозга, которые могут быть возбуждены или заторможены. Он обладает группой синапсов - однонаправленных входных связей, соединенных с выходами других нейронов, а также имеет аксон - выходную связь данного нейрона, с которой сигнал поступает на синапсы следующих нейронов.
Как правило, в задачах распознавания объектов используются следующие архитектуры НС: многослойный персептрон; вероятностные нейронные сети; сети Кохонена; сверточные нейронные сети. При этом выбор той или иной архитектуры зависит от специфики распознаваемого объекта.
4.4 Метод Виолы - Джонса
На данный момент метод Виолы - Джонса является основополагающим для поиска объектов на изображении в реальном времени (РВ) и обладает низкой вероятностью ложного обнаружения. Данный метод успешно применяется для поиска следующих объектов: человеческих лиц, губ, глаз и т.д. Ранее считалось, что его нельзя применять для обнаружения текста. Данное утверждение было опровергнуто.
Метод Виолы - Джонса основан на следующих принципах:
1) используются изображения в интегральном представлении;
2) используются признаки Хаара;
3) используется бустинг для выбора наиболее подходящих признаков для искомого объекта на данной части изображения;
4) все признаки поступают на вход классификатора, который даёт результат «верно» либо «ложь»;
5) используются каскады признаков для быстрого отбрасывания окон.
Несмотря на то, что данный метод является основополагающим для поиска объектов на изображении в реальном времени, его основной недостаток состоит в том, что результат работы сильно зависит от обучающей выборки. Это объясняется тем, что в качестве входных данных выступает яркостное изображение, которое чувствительно к освещенности. В данной работе данный алгоритм используется при нахождении фотографии на документе на этапе сегментации исходного изображения, при выделении (детектировании) фотографии на документе.
4.5 Алгоритм k ближайших соседей
Основным принципом метода k ближайших соседей является то, что объект присваивается тому классу, который является наиболее распространённым среди соседей данного элемента. Соседи берутся, исходя из множества объектов, классы которых уже известны, и, исходя из ключевого для данного метода значения k, высчитывается, какой класс наиболее многочислен среди них. Каждый объект имеет конечное количество атрибутов (размерностей). Предполагается, что существует определенный набор объектов с уже имеющейся классификацией.
Рассмотрим алгоритм k ближайших соседей подробнее. Пусть имеется n наблюдений, каждому из которых соответствует запись в таблице. Все записи принадлежат какому - либо классу. Необходимо определить класс для новой записи. На первом шаге алгоритма следует задать число k - количество ближайших соседей. Если принять k = 1, то алгоритм потеряет обобщающую способность (то есть способность выдавать правильный результат для данных, не встречавшихся ранее в алгоритме) так как новой записи будет присвоен класс самой близкой к ней. Если установить слишком большое значение, то многие локальные особенности не будут выявлены. На втором шаге находятся k записей с минимальным расстоянием до вектора признаков нового объекта (поиск соседей).
Функция для расчета расстояния должна отвечать следующим правилам:
1. d(x, y) ? 0;
2. d(x, y) = 0 тогда и только тогда, когда x = y;
3. d(x, y) = d(y, x);
4. d(x, z) ? d(x, y) + d(y, z), при условии, что точки x, y, z не лежат на одной прямой.
Для упорядоченных значений атрибутов находится Евклидово расстояние:
где n - количество атрибутов.
Для строковых переменных, которые не могут быть упорядочены, может быть применена функция отличия, которая задается следующим образом:
Часто перед расчетом расстояния необходима нормализация. Приведем некоторые полезные формулы.
Минимаксная нормализация:
Нормализация с помощью стандартного отклонения:
где уx - стандартное отклонение, Xср - среднее значение.
При нахождении расстояния иногда учитывают значимость атрибутов. Она определяется экспертом или аналитиком субъективно, полагаясь на собственный опыт. В таком случае при нахождении расстояния каждый i - ый квадрат разности в сумме умножается на коэффициент Zi. Например, если атрибут A в три раза важнее атрибута B (ZA = 3, ZB = 1), то расстояние будет находиться следующим образом:
Подобный прием называют растяжением осей (stretching the axes), что позволяет снизить ошибку классификации. Следует отметить, что если для записи B ближайшем соседом является А, то это не означает, что В - ближайший сосед А. Данная ситуация представлена на рисунке 2. При k = 1 ближайшей для точки B будет точка A, а для A - X. При увеличении коэффициента до k = 7, точка B так же не будет входить в число соседей точки A.
Рисунок 2 - Ближайшие соседи А и B
На следующем шаге, когда найдены записи, наиболее похожие на новую, необходимо решить, как они влияют на класс новой записи. Для этого используется функция сочетания (combination function). Одним из основных вариантов такой функции является простое невзвешенное голосование (simple unweighted voting).
Простое невзвешенное голосование
Вначале, определив число k, мы узнали, сколько записей будет иметь право голоса при определении класса. Затем мы выявили эти записи, расстояние от которых до новой оказалось минимальным. Теперь можно приступить к простому невзвешенному голосованию. Расстояние от каждой записи при голосовании здесь больше не играет роли. Все имеют равные права в определении класса. Запись отдает предпочтение тому классу, к которому она принадлежит, а тот, который наберет наибольшее количество голосов, присваивается новой записи. Но что делать в случае, если несколько классов набрали равное количество голосов? Эту проблему снимает взвешенное голосование (weighted voting).
Взвешенное голосование
В такой ситуации учитывается также и расстояние до новой записи. Чем меньше расстояние, тем более значимый вклад вносит голос. Голоса за класс находятся по следующей формуле:
где d2(X, Yi) - квадрат расстояния от известной записи Yi до новой X;
n - количество известных записей класса, для которого рассчитываются голоса; class - наименование класса.
Класс, набравший наибольшее количество голосов, присуждается новой записи. При этом вероятность того, что несколько классов наберут одинаковые голоса, гораздо ниже. Совершенно очевидно, что при k = 1 новой записи присваивается класс самого ближайшего соседа.
5. Заключение по аналитическому обзору
Представленные ранее существующие OCR - системы являются хорошими и качественными продуктами в своей области использования. Однако специфика предметной области данной работы требует более узкоспециализированного программного обеспечения. Изображения документов необходимо получать путем сканирования через веб - камеру либо с помощью загрузки в систему через браузер. На текущий момент времени рассмотренные системы не позволяют решать данную задачу. Решение задачи имеет смысл разделить на несколько этапов: сегментацию изображения (определение фотографии, выделение текстовых блоков), секторизацию текстовых блоков (выделение символов в словах) и распознавание (определение символа) текста.
Что касается методов, как правило, проблемой является низкая устойчивость алгоритмов к воздействию внешних условий, затрудняющих качество распознавания: уровень освещения; качество изображения; наличие наклона изображения. При этом алгоритмы, устойчивые к внешним условиям, зачастую оказываются требовательны к аппаратным и вычислительным ресурсам, что затрудняет применение их в системах, работающих в реальном времени. Несомненно, из представленного списка лучшей можно считать ABBYY FineReader. Но это система широкого профиля, кроме того, она является платной. Она поддерживает массу ненужных в данной предметной области сканирования документов, удостоверяющих личность, функций. В работе будет использоваться алгоритм k ближайших соседей для решения задачи распознавания символов на текстовых блоках.
Данный алгоритм обучения с учителем (существует обучающая выборка) достаточно прост в понимании и отлично подходит для решения задачи распознавания символов. В рамках данного проекта рассматривается как раз такая ситуация: требуется извлекать текст из выделенных текстовых блоков на отсканированном документе. Обучающая выборка присутствует. В отличии от нейронных сетей данный алгоритм на узких задачах быстрее, а его точность зависит от подбора параметров. Так как скорость распознавания документа имеет важное значение в разработке системы, то нейронная сеть здесь не подходит.
Программная реализация алгоритма относительно проста. Результат работы алгоритма легко поддаётся интерпретации. Экспертам в различных областях вполне понятна логика работы алгоритма, основанная на нахождении схожих объектов. Возможность модификации алгоритма, путём использования наиболее подходящих функций сочетания и метрик позволяет подстроить алгоритм под конкретную задачу. Тема распознавания символов на текущий момент времени во многом изучена и с каждым годом в этой области появляются все более совершенные алгоритмы.
6. Алгоритм распознавания текста
6.1 Общее решение задачи
Процесс решения задачи распознавания документов можно представить в виде последовательности шагов, изображенных на рисунке 3.
В данной работе предлагается алгоритм распознавания предварительно выделенных текстовых блоков на сканируемом изображении документа. Задача захвата изображения с камеры или его загрузки в систему, а также выделения документа на изображении, не рассматривается. В работе рассматриваются задачи получения изображения, его сегментация, секторизация, распознавание текста и подготовка итогового отчета по результатам распознавания.
Рисунок 3 - Общая схема решения задачи распознавания документов
6.2 Структурная схема и описание алгоритма
Краткая структурная схема алгоритма представлена на рисунке 4.
Разрабатываемый алгоритм распознавания документов можно представить в виде следующей последовательности шагов:
Шаг 1. Захват изображения (получение).
Шаг 2. Конвертация изображения в градации серого.
Шаг 3. Бинаризация изображения.
Шаг 4. Выделение фотографии.
Шаг 5. Выделение границ текстовых блоков.
Шаг 6. Секторизация текстовых блоков.
Шаг 7. Выделение границ символов на текстовых блоков.
Шаг 8. Классификация изображений полученных символов, определение значений.
Шаг 9. Объединение результатов в отчет.
Рисунок 4 - Структурная схема алгоритма
6.3 Методы цифровой обработки изображений
6.3.1 Преобразование в оттенки серого
Оттенки серого (Grayscale) -- цветовой режим изображений, которые отображаются в оттенках серого цвета, размещённые в виде таблицы в качестве эталонов яркости белого цвета. Чаще всего используют ступенчатое изображение равномерного ряда оптических плотностей нейтрально-серых полей. Широко применяется в цветоведении и колористике, для оценки и измерений качества тонопередачи при фотографической съемке, сканировании, при копировальных и печатных процессах (полиграфия).
6.3.2 Пороговая обработка и бинаризация
Операция порогового разделения, которая в результате дает бинарное изображение, называется бинаризацией. Целью операции бинаризации является радикальное уменьшение количества информации, содержащейся на изображении. В процессе бинаризации исходное полутоновое изображение преобразуется в черно - белое, пиксели которого имеют только два значения - 0 и 1 .
6.3.3 Выделение контуров
Наиболее известными и часто используемыми методами выделения контуров являются методы Робертса, Превитта и Собеля. Все указанные методы основываются на одном из базовых свойств сигнала яркости - разрывности. Наиболее общим способом поиска разрывов является обработка изображения с помощью скользящей маски, называемой также фильтром, ядром, окном или шаблоном, которая представляет собой некую квадратную матрицу, соответствующую указанной группе пикселей исходного изображения. Элементы матрицы принято называть коэффициентами. Оперирование такой матрицей в каких - либо локальных преобразованиях называется пространственной фильтрацией.
Алгоритмы Робертса и Собеля больше подходят для задачи выделения контуров, однако метод Собеля - это усовершенствованный метод Робертса и он дает более качественный результат выделения границ изображения т.к. является изотропным и позволяет выделять перепады яркостей любых направлений, поэтому в работе выбран данный метод. В задаче присутствует два этапа, когда происходит выделение контуров: сегментация исходного изображения и секторизация текстовых блоков. В первой задаче используется фильтр Собеля, во второй - фильтр Робертса. Такой выбор обусловлен тем, что опытным путем был выявлен тот, факт, что фильтр Робертса на небольших изображениях отрабатывает с высокой точностью, при этом фильтр Собеля не позволяет выделить символы в текстовых блоках.
6.3.4. Поиск контуров
После применения всех необходимых фильтров к изображению, можно выделить на изображении области, содержащие текстовые блоки или символы. На рисунке 2.9 можно посмотреть пример сегментированного изображения, где текстовые блоки отрисованы после этапа поиска контуров.
6.4 Выделение фотографии
Для поиска портретной фотографии человека используется каскадный классификатор Хаара. Библиотека OpenCV содержит готовые реализации многих алгоритмов машинного обучения, однако для корректной их работы, классификаторы следует предварительно обучить. Обучающая выборка для каскадного классификатора Хаара также реализована в рамках данной библиотеки.
6.5 Сегментация изображения
На оставшемся изображении после выделения фотографии так же требуется выделить текстовые блоки. Текстовый блок - это одна конкретная строка (слово) в документе. Путем преобразования изображения сначала в оттенки серого, затем после применения фильтров морфологической обработки дилатации и замыкания, производится выделение границ текстовых блоков. Полученные контуры выделяются на исходном изображении и для дальнейшей работы «вырезаются» в отдельные самостоятельные изображения для дальнейших преобразований.
6.6 Секторизация текстовых блоков
Секторизация (выделение символов (букв, цифр)) в каждом текстовом блоке, распознавание текста, сохранение результата в базе. Когда документ разбит на блоки, эти блоки в цикле перебираются и к каждому применяется секторизация, а затем распознавание. В процессе секторизации используются те же методы и алгоритмы, что и при сегментации. По сути, процесс секторизации - это сегментация сегмента исходного документа. В процессе секторизации изображения к изображению применяются следующие алгоритмы в указанном порядке:
1. преобразование в оттенки серого;
2. бинаризация изображения;
3. применение алгоритма Робертса;
4. выделение контуров с помощью порогового преобразования к бинарному изображению;
6.7 Классификация сегментов текстовых блоков
Задача классификации сегментов текстовых блоков - задача распознавания символа, изображенного в секторе. На данном этапе набор секторов текстового блока подвергается обработке через алгоритм k ближайших соседей и на выходе получаем распознанный текст. Внутри алгоритма распознается каждая буква. Когда каждая буква распознана, собирается готовое слово. Также должна быть обучающая выборка всех букв и цифр.
Рисунок 5 - Обучающая выборка
Эта выборка используется для поиска похожих символов на те, что пытаемся распознать. На рисунке 5 представлен пример такой выборки.
Обучающая выборка состоит из 53 изображении, размером 100Ч100.
42 буквы, 10 цифр, 1 знак препинания.
Для распознавания символов был выбран алгоритм k ближайших соседей.
7. Распознавание символов онлайн
Распознавание символов онлайн иногда путают с оптическим распознаванием символов. Последний -- это офлайн - метод, работающий со статической формой представления текста, в то время как онлайн - распознавание символов учитывает движения во время письма. Например, в онлайн - распознавании, использующем PenPoint OS или планшетный ПК, можно определить, с какой стороны пишется строка: справа налево или слева направо.
Онлайн - системы для распознавания рукописного текста «на лету» в последнее время стали широко известны в качестве коммерческих продуктов. Алгоритмы таких устройств используют тот факт, что порядок, скорость и направление отдельных участков линий ввода известны. Кроме того, пользователь научится использовать только конкретные формы письма. Эти методы не могут быть использованы в программном обеспечении, которое использует сканированные бумажные документы, поэтому проблема распознавания рукописного «печатного» текста по-прежнему остаётся открытой. На изображениях с рукописным «печатным» текстом без артефактов может быть достигнута точность в 80 % -- 90 %, но с такой точностью изображение будет преобразовано с десятками ошибок на странице. Такая технология может быть полезна лишь в очень ограниченном числе приложений.
Ещё одной широко исследуемой задачей является распознавание рукописного текста. В данное время достигнутая точность даже ниже, чем для рукописного «печатного» текста. Более высокие показатели могут быть достигнуты только с использованием контекстной и грамматической информации. Например, в ходе распознания искать целые слова в словаре легче, чем пытаться выявить отдельные знаки из текста. Знание грамматики языка может также помочь определить, является ли слово глаголом или существительным. Формы отдельных рукописных символов иногда могут не содержать достаточно информации, чтобы точно (более 98 %) распознать весь рукописный текст.
Для решения более сложных задач в области распознавания используются, как правило, интеллектуальные системы распознавания, такие, как искусственные нейронные сети.
Список использованной литературы
Квасников В.П., Дзюбаненко А.В. Улучшение визуального качества цифрового изображения путем поэлементного преобразования // Авиационно - космическая техника и технология 2009 г., 8, стр. 200-204
Арлазаров В.Л., Куратов П.А., Славин О.А. Распознавание строк печатных текстов // Сб. трудов ИСА РАН «Методы и средства работы с документами». -- М.: Эдиториал УРСС, 2000. -- С. 31-51.
Проект СПбГУ Открытый код: распознавание текстовых изображений [Электронный ресурс] -- Режим доступа: ocr.apmath.spbu.ru
Багрова И. А., Грицай А. А., Сорокин С. В., Пономарев С. А., Сытник Д. А. Выбор признаков для распознавания печатных кириллических символов // Вестник Тверского Государственного Университета 2010 г., 28, стр. 59-73
Панфилов С. А. Методы и программный комплекс моделирования алгоритмов управления нелинейными динамическими системами на основе мягких вычислений. Диссертация на соискание ученой степени кандидата технических наук. Тверь, 2005.
Размещено на Allbest.ru
Подобные документы
Необходимость в системах распознавания символов. Виды сканеров и их характеристики. Оптимальное разрешение при сканировании. Программы распознавания текста. Получение электронного документа. FineReader - система оптического распознавания текстов.
презентация [469,2 K], добавлен 15.03.2015Оптико-электронная система идентификации объектов подвижного состава железнодорожного транспорта. Автоматический комплекс распознавания автомобильных номеров. Принципы и этапы работы систем оптического распознавания. Особенности реализации алгоритмов.
дипломная работа [887,3 K], добавлен 26.11.2013Понятие системы распознавания образов. Классификация систем распознавания. Разработка системы распознавания формы микрообъектов. Алгоритм для создания системы распознавания микрообъектов на кристаллограмме, особенности его реализации в программной среде.
курсовая работа [16,2 M], добавлен 21.06.2014Обзор задач, возникающих при разработке систем распознавания образов. Обучаемые классификаторы образов. Алгоритм персептрона и его модификации. Создание программы, предназначенной для классификации образов методом наименьшей среднеквадратической ошибки.
курсовая работа [645,2 K], добавлен 05.04.2015Оптическое распознавание символов как механический или электронный перевод изображений рукописного, машинописного или печатного текста в последовательность кодов. Компьютерные программы для оптического распознавания символов и их характеристика.
презентация [855,2 K], добавлен 20.12.2011Основные понятия теории распознавания образов и ее значение. Сущность математической теории распознавания образов. Основные задачи, возникающие при разработке систем распознавания образов. Классификация систем распознавания образов реального времени.
курсовая работа [462,2 K], добавлен 15.01.2014Теоретические основы распознавания образов. Функциональная схема системы распознавания. Применение байесовских методов при решении задачи распознавания образов. Байесовская сегментация изображений. Модель TAN при решении задачи классификации образов.
дипломная работа [1019,9 K], добавлен 13.10.2017Условия применения и технические требования для работы программно-аппаратной платформы. Система распознавания лиц VOCORD Face Control. Система распознавания текста ABBYY FineReader. Алгоритмы и методы, применяемые в программе. Алгоритм хеширования MD5.
дипломная работа [1,8 M], добавлен 19.01.2017Методы распознавания образов (классификаторы): байесовский, линейный, метод потенциальных функций. Разработка программы распознавания человека по его фотографиям. Примеры работы классификаторов, экспериментальные результаты о точности работы методов.
курсовая работа [2,7 M], добавлен 15.08.2011Появление технических систем автоматического распознавания. Человек как элемент или звено сложных автоматических систем. Возможности автоматических распознающих устройств. Этапы создания системы распознавания образов. Процессы измерения и кодирования.
презентация [523,7 K], добавлен 14.08.2013
