Способы и системы обработки изображений математических выражений

Способы и системы обработки изображений математических выражений

Иллюстрации

Показать все

Реферат

СПОСОБЫ И СИСТЕМЫ ОБРАБОТКИ ИЗОБРАЖЕНИЙ МАТЕМАТИЧЕСКИХ ВЫРАЖЕНИЙ

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

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

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

На Фиг. 1А-В проиллюстрирован печатный документ.

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

На Фиг. 3 проиллюстрировано функционирование оптических компонентов настольного сканера, изображенного на Фиг. 2.

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

На Фиг. 5 проиллюстрированное цифровое представление отсканированного документа.

На Фиг. 6А-С проиллюстрирован один подход к преобразованию изображения документа в электронный документ, который используется в некоторых доступных в настоящее время OCR-системах.

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

На Фиг. 10А-В проиллюстрирован подход к распознаванию символов, используемый OCR-системой, путем наложения эталона.

На Фиг. 11А-В проиллюстрированы различные аспекты объектов множеств символов для естественных языков.

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

На Фиг. 13А-В проиллюстрирован тип классификатора, который можно использовать для порождения гипотез в отношении разбиения изображения текстовой строки в последовательность изображений символов.

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

На Фиг. 15A-F проиллюстрирован один из способов разбиения на блоки математического выражения, который разделяет изображение или фрагмент изображения, содержащий математическое выражение, на блоки или разбиения более низкого уровня.

На Фиг. 16А-В проиллюстрированы рекурсивно-блочный и основанный на графе подходы к распознаванию математических формул в процессе OCR-обработки изображения документа.

На Фиг. 17А-С представлены блок-схемы, иллюстрирующие один из способов обработки изображения документа, содержащего математическое выражение, к которому относится настоящий документ.

На Фиг. 18А-С проиллюстрировано применение обработки на основе графа для распознавания фрагментов математических выражений и полных математических выражений.

На Фиг. 19 представлены результаты анализа в форме дерева, сгенерированные с помощью рекурсивно-блочного подхода, исходно представленного на Фиг. 16В, с дугами правильного пути для математического выражения 1406, изображенного на Фиг. 14А.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

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

Изображения отсканированных документов и электронные документы

На Фиг. 1А-В проиллюстрирован печатный документ. На Фиг. 1А представлен первоначальный документ с текстом на японском языке. Печатный документ 100 включает фотографию 102 и пять разных содержащих текст участков (104-108), включающих японские символы. Данный пример документа используется в представленном ниже описании способа и систем для определения ориентации, к которым относится настоящий документ. Текст на японском языке может быть написан слева направо, вдоль горизонтальных строк, как текст на английском языке, но альтернативно может быть написан способом сверху вниз в пределах вертикальных столбцов. Например, участок 107 явно содержит вертикально написанный текст, тогда как текстовый блок 108 включает текст, написанный горизонтальными строками. На Фиг. 1В печатный документ, проиллюстрированный на Фиг. 1А, показан переведенным на английский язык.

Печатные документы можно преобразовать в оцифрованные изображения отсканированных документов с помощью различных средств, включая электронные оптико-механические устройства сканирования и цифровые камеры. На Фиг. 2 проиллюстрированы типичный настольный сканер и персональный компьютер, которые вместе используются для преобразования печатных документов в оцифрованные электронные документы, которые можно хранить на запоминающих устройствах и/или в модулях электронной памяти. Настольное сканирующее устройство 202 включает прозрачный стеклянный планшет 204, на который лицевой стороной вниз помещают документ 206. Активация сканера приводит к генерированию оцифрованного изображения отсканированного документа, которое можно передать на персональный компьютер (ПК) 208 для хранения на запоминающем устройстве. Программа отображения отсканированного документа может отобразить оцифрованное изображение отсканированного документа на дисплей 210 устройства отображения ПК 212.

На Фиг. 3 проиллюстрировано функционирование оптических компонентов настольного сканера, изображенного на Фиг. 2. Оптические компоненты данного ПЗС-сканера находятся под прозрачным стеклянным планшетом 204. Фронтально перемещаемый источник яркого света 302 освещает фрагмент сканируемого документа 304, свет от которого, в свою очередь, повторно излучается и отражается вниз. Свет повторно излучается и отражается от фронтально перемещаемого зеркала 306 на неподвижное зеркало 308, которое отражает излучаемый свет на массив ПЗС-элементов 310, порождающих электрические сигналы пропорционально интенсивности света, падающего на каждый из ПЗС-элементов. Цветные сканеры могут включать три отдельных строки или массива ПЗС-элементов с красным, зеленым и синим фильтрами. Фронтально перемещаемый источник яркого света и фронтально перемещаемое зеркало перемещаются вместе вдоль документа для генерирования изображения отсканированного документа. Другой тип сканера, в котором используется контактный датчик изображения, называется CIS-сканером. В CIS-сканере подсветка документа осуществляется перемещаемыми цветными светодиодами (LED), причем отраженный свет светодиодов воспринимается массивом фотодиодов, который перемещается вместе с цветными светодиодами.

На Фиг. 4 представлена общая архитектурная схема различных типов компьютеров и других устройств, управляемых процессором. Архитектурная схема высокого уровня может описывать современную компьютерную систему, такую как ПК, изображенный на Фиг. 2, в которой программы отображения отсканированного документа и программы оптического распознавания символов хранятся на запоминающих устройствах для передачи в модуль электронной памяти и исполнения одним или более процессорами. Компьютерная система содержит один или несколько центральных процессоров (ЦП) 402-405, один или более модулей электронной памяти 408, взаимно соединенных с ЦП с помощью шины подсистемы ЦП/память 410 или нескольких шин, первый мост 412, который соединяет шину подсистемы ЦП/память 410 с дополнительными шинами 414 и 416, или другими средствами высокоскоростного взаимодействия, включая несколько высокоскоростных последовательных соединений. Эти шины или последовательные соединения, в свою очередь, соединяют ЦП и модуль памяти со специализированными процессорами, такими как графический процессор 418, а также с одним или более дополнительными мостами 420, взаимно соединенными с высокоскоростными последовательными каналами или с несколькими контроллерами 422-427, такими как контроллер 427, которые обеспечивают доступ к многообразию типов устройств памяти 428, электронным дисплеям, устройствам ввода и другим таким компонентам, подкомпонентам и вычислительным ресурсам.

На Фиг. 5 проиллюстрировано цифровое представление отсканированного документа. На Фиг. 5 небольшой дискообразный фрагмент 502 примера печатного документа 504 представлен в увеличенном виде 506. Соответствующий фрагмент оцифрованного изображения отсканированного документа 508 также представлен на Фиг. 5. Оцифрованный отсканированный документ включает данные, которые представляют двухмерный массив кодировок значений пикселей. В представлении 508 каждая ячейка сетки под символами, такая как ячейка 509, представляет квадратную матрицу пикселей. Небольшой фрагмент 510 сетки представлен с еще большим увеличением (512 на Фиг. 5), на котором отдельные пиксели представлены в виде элементов матрицы, таких как элемент матрицы 514. При таком уровне увеличения края символов кажутся зазубренными, поскольку пиксель является наименьшим элементом детализации, который можно контролировать для излучения света указанной интенсивности. В файле оцифрованного отсканированного документа каждый пиксель представлен фиксированным количеством бит, причем кодирование пикселей осуществляется последовательно. Файл содержит заголовок с информацией, указывающей тип кодирования пикселя, размеры отсканированного изображения и другую информацию, позволяющую программе отображения оцифрованного отсканированного документа извлекать данные кодировки пикселя и отдавать команды на устройство отображения или принтер для воспроизведения кодировок пикселей в виде двухмерного представления первоначального документа. В оцифрованных изображениях отсканированного документа по монохромной шкале оттенков серого широко используют 8-разрядную или 16-разрядную кодировки пикселя, тогда как в цветных изображениях отсканированного документа можно использовать 24 бита или более для кодирования каждого пикселя в соответствии с множеством стандартов кодирования цвета. В качестве одного примера, в широко используемом стандарте RGB для представления интенсивности красного, зеленого и синего света используют три 8-битных значения, закодированных в 24-битном значении. Таким образом, оцифрованное отсканированное изображение по существу представляет документ таким же способом, которым цифровые фотографии представляют визуальные образы. Кодировки пикселей представляют информацию об интенсивности света в конкретных крошечных участках изображения, а в цветных изображениях дополнительно представляет информацию о цвете. В оцифрованном изображении отсканированного документа отсутствует какое-либо указание на значение кодировок пикселей, такое как указания на то, что небольшая двухмерная область смежных пикселей представляет текстовый символ.

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

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

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

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

На Фиг. 6А-С проиллюстрирован один из подходов к преобразованию изображения документа в электронный документ, который используется в некоторых доступных в настоящее время OCR-системах. Данный подход является в сущности иерархическим, и его можно понять и реализовать рекурсивно, нерекурсивно или частично рекурсивно. После исходного определения ориентации изображение документа 602 обрабатывают для разбиения изображения документа на фрагменты или элементы высокого уровня 604-606. В примере, представленном на Фиг. 6А, изображение документа включает картинку 610, первый текстовый блок 612 и второй текстовый блок 614. Это элементы изображения документа высокого уровня, из которых в результате разбиения получают соответствующее изображение первого текстового блока 604, соответствующее изображение второго текстового блока 605 и соответствующую картинку 606. В этом случае картинка является основным элементом изображения документа и не может быть дополнительно разбита. Однако на втором уровне разбиения изображение первого текстового блока 604 разбивается на изображения отдельных текстовых строк 616-620, а изображение второго текстового блока 605 дополнительно разбивается на изображения текстовых строк 622-623. На последнем уровне разбиения каждое изображение текстовой строки, такое как изображение текстовой строки 623, дополнительно разбивается на отдельные символы, такие как изображения символов 626-634, соответствующие изображению текстовой строки 623. В некоторых способах реализации разбиение изображений текстовых строк на изображения символов может включать по меньшей мере частичное исходное разбиение изображений текстовой строки на изображения слов для тех языков, в которых символы алфавита объединяются в слова.

Как проиллюстрировано на Фиг. 6А, в некоторых OCR-способах и системах сначала изображение документа 602 разбивается на изображения символов, такие как изображения символов 626-634, до построения электронного документа, соответствующего изображению документа. Во многих из этих систем изображение символа является наименьшим элементом детализации разбиения, выполняемого OCR-способами и системами в отношении изображений текста.

Затем, как представлено на Фиг. 6В, эти OCR-способы и системы порождают электронный документ, соответствующий изображению документа, обратным иерархическим методом. Изображения символов, такие как изображение символа 640, объединяются в слова, такие как слово 642, для тех языков, в которых символы алфавита объединяются в слова. На следующем уровне построения электронного документа слова объединяются с генерированием текстовых строк, таких как текстовая строка 644, содержащая слово 642. На другом дополнительном уровне построения электронного документа текстовые строки объединяются для генерирования текстовых блоков, таких как текстовый блок 646, содержащий текстовую строку 644. И, наконец, все элементы документа высшего уровня, такие как картинка 606, текстовый блок 648 и текстовый блок 650, объединяются для генерирования электронного документа 652, соответствующего изображению документа 602. Как описано выше, электронный документ по существу содержит представления символов алфавита, знаков и различных типов управляющих последовательностей для порождения рамок, границ и других элементов электронного документа в формате Юникод. Таким образом, символ алфавита 640 по существу представляет оцифрованный символ, такой как символ Юникод, соответствующий изображению символа 633, представленному на Фиг. 6А. Аналогичным образом картинка 645 по существу представляет тип сжатого файла изображения, соответствующего картинке 606, отсканированной в виде части изображения документа. Иными словами, если рассматривать разбиение изображения документа на элементы изображения документа в виде дерева, как показано на Фиг. 6А, то наименьшие возможные элементы дерева преобразуются из отсканированных изображений в соответствующие цифровые представления информации, содержащейся в отсканированных изображениях, а затем цифровые представления повторно объединяются в рамках процесса, представленного на Фиг. 6В, для генерирования оцифрованного электронного документа.

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

На Фиг. 6С представлен один пример порождения нескольких гипотез во время разбиения изображения документа. На Фиг. 6С исходное изображение документа 602 в соответствии с одной гипотезой, представленной стрелкой 660, разбивается на три компонента 604-606 более низкого уровня, описанных выше со ссылкой на Фиг. 6А. Однако в соответствии со второй гипотезой 662 текстовое изображение может быть альтернативно разбито на один текстовый блок 664 и картинку 606. В этом случае граница между первым текстовым блоком 612 и вторым текстовым блоком 614 может быть нечеткой или может полностью отсутствовать, и в этом случае OCR-способам и системам, возможно, потребуется проверять две альтернативные гипотезы. Порождение ветвления с многовариантной гипотезой как на стадии разбиения, так и на стадии построения при преобразовании изображений документа в электронные документы может приводить к буквально тысячам, десяткам тысяч, сотням тысяч, миллионам или более возможных альтернативных вариантов преобразований. Как правило, для ограничения порождения многовариантных гипотез, обеспечения точной и эффективной навигации по потенциально огромному пространству состояний разбиений и построений электронного документа для определения одного наиболее вероятного электронного документа, соответствующего изображению документа, в OCR-способах и системах используется статистическая оценка, широкое множество типов показателей и широкое множество типов автоматических методик проверки гипотезы.

На Фиг. 7 альтернативно представлен способ преобразования изображения документа в электронный документ, используемый множеством доступных в настоящее время OCR-способов и систем. Изображение документа 702 разбивается на множества элементов высшего уровня изображения 704 и 706 с использованием двух альтернативных гипотез 708 и 710 соответственно. На следующем уровне разбиения изображения текстовых блоков в первом исходном разбиении 704 и изображение единственного тестового блока во втором исходном разбиении 706 разбиваются на изображения текстовых строк в соответствии с тремя гипотезами 712-714 для первого разбиения высшего уровня 704 и двумя гипотезами 716-717 для второго разбиения высшего уровня 706. Затем на следующем уровне разбиения происходит дополнительное разбиение каждого из этих пяти разбиений второго уровня на изображения отдельных символов в соответствии с несколькими гипотезами с порождением в итоге 12 разбиений на наименьшие возможные элементы, таких как разбиение на наименьшие возможные элементы 718. На второй стадии преобразования изображения документа в электронный документ каждое разбиение на наименьшие возможные элементы строит по существу несколько возможных электронных документов, таких как электронные документы 722, соответствующие разбиению на наименьшие возможные элементы 718. На Фиг. 7 проиллюстрировано потенциальное множество электронных документов, которое можно сгенерировать с помощью альтернативных гипотез в рамках способа преобразования, хотя фактически различные альтернативные промежуточные гипотезы и альтернативные электронные документы отфильтровываются в рамках процесса таким образом, что итоговый наиболее высоко оцениваемый электронный документ выбирается среди целесообразного количества альтернатив на итоговых стадиях построения электронного документа. Иными словами, хотя потенциальное пространство состояний возможных электронных документов большое, фильтрация и отсечение происходят на протяжении стадий разбиения и построения так, что в процессе преобразования фактически изучается лишь относительно небольшая часть подпространства.

На Фиг. 8-9 проиллюстрирован один вычислительный подход к определению идентичности и ориентации символа в пределах изображения символа. На Фиг. 8 символ 802 представлен наложенным на прямолинейную сетку 804. Как и на участке 508, изображенном на Фиг. 5, каждый элемент сетки или ячейка представляет собой матрицу пиксельных элементов, в результате чего края символа кажутся гладкими. При большем увеличении, как и на участке 512, изображенном на Фиг. 5, края символа будут казаться зазубренными. Как описано выше, этим пикселям присваивается одно из двух битовых значений - «0» или «1», которые указывают на то, соответствует ли пиксель фрагменту фона или фрагменту символа соответственно. Доля пикселей в пределах каждого столбца элементов сетки представлена на гистограмме 806, показанной поверх прямолинейной сетки 804. На данной гистограмме представлено горизонтальное пространственное распределение пикселей символа в пределах прямолинейной сетки, что представляет фрагмент изображения отсканированного документа, содержащего один символ. Аналогичным образом, на гистограмме 808 представлено пространственное распределение пикселей символа в вертикальном направлении. Гистограмма 810 и гистограмма 806 зеркально симметричны; гистограмма 812 и гистограмма 808 так же зеркально симметричны. Данные гистограммы являются сигнатурами или характерными признаками обнаружения и определения ориентации символа.

На Фиг. 9 проиллюстрирован числовой показатель, который можно вычислить на основе двух из четырех гистограмм, представленных на Фиг. 8. На этом чертеже вычисляется показатель ориентации, называемый «гистограммным показателем», или «h-показателем», по верхней гистограмме и правой гистограмме 806 и 808, вычисляемым для конкретного символа в конкретной ориентации. Каждая гистограмма разделена на четыре участка вертикальными пунктирными линиями, такими как вертикальная пунктирная линия 902. Каждому участку присваивается значение «0» или «1» в зависимости от того, достигает ли столбец гистограммы в пределах участка порогового значения, такое как 0,5. Данные битовые значения упорядочивают таким же способом, что и разбиения. Таким образом, например, в случае гистограммы 806 на разбиениях 904 и 906 отсутствует столбец, который превышает пороговое значение или высоту 0,5, тогда как на разбиениях 908 и 910 присутствует по меньшей мере один столбец гистограммы, который превышает пороговое значение или высоту 0,5. Таким образом, битовые значения, присвоенные разбиениям, порождают четырехбитовый полубайт «0110» 912. Аналогичные вычисления для правой гистограммы 808 порождают четырехбитовый полубайт «0011» 914. Данные два четырехбитовых полубайта можно конкатенировать для порождения восьмибитового h-показателя 916.

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

На Фиг. 10А-В проиллюстрирован подход к распознаванию символов, используемый в OCR-системе, путем наложения эталона. На Фиг. 10А-В представлен эталонный символ, наложенный на участок двоичного изображения документа 1002, содержащий изображение символа во множестве ориентаций. Для каждой ориентации доля пикселей в эталонном символе, перекрывающихся с черными пикселями на участке двоичного изображения документа, содержащего изображение символа, генерирует показатель перекрывания, или o-показатель. Перед вычислением o-показателей для разных ориентаций эталонного символа в отношении изображения символа выполняют операцию масштабирования, чтобы обеспечить, что эталонный символ и изображение символа имеют приблизительно одинаковый размер. Заданное изображение символа можно сравнить с множеством эталонных символов во множестве ориентаций и выбрать наилучшим образом совпадающий эталонный символ в качестве эталонного символа с наибольшим сгенерированным значением о-показателя. Например, на Фиг. 10В наложение 1004 генерирует перекрывание 100%. Для большей точности можно вычислить двусторонний о-показатель комбинированного перекрывания эталонного символа в отношении изображения символа и для изображения си