Способы и устройства, которые преобразуют изображения документов в электронные документы с использованием trie-структуры данных, содержащей непараметризованные символы для определения слов и морфем на изображении документа

Способы и устройства, которые преобразуют изображения документов в электронные документы с использованием trie-структуры данных, содержащей непараметризованные символы для определения слов и морфем на изображении документа

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

На Фиг. 1А-В показан печатный документ.

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

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

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

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

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

На Фиг. 7 показано вращение в горизонтальной плоскости.

На Фиг. 8-10 показан подход к определению исходной ориентации области, содержащей текст.

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

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

На Фиг. 13А-Е в виде блок-схем приведен пример доступных в настоящее время на рынке способов преобразования документов, применяемых в системах OCR.

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

На Фиг. 15-17 показан один вычислительный подход к идентификации символа на изображении символа и определению его ориентации.

На Фиг. 18-19В показана другая метрика, которая может применяться для распознавания символа на изображении отсканированного документа.

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

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

На Фиг. 22 показаны определенные характеристики текста на языке, напоминающем арабский.

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

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

На Фиг. 25 показана еще одна дополнительная особенность текста на языке, напоминающем арабский.

На Фиг. 26 показана еще одна дополнительная особенность текста на языке, напоминающем арабский.

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

На Фиг. 28А-В и 29 показан и обоснован подход, представленный раскрываемыми в настоящей заявке методами OCR, который может найти применение в отношении языков, напоминающих арабский.

На Фиг. 30А-В приведен пример способов OCR, в которых строки текста раскладываются на знаки или символы, к которым относится изобретение и которые особенно применимы в отношении текстов на языке, напоминающем арабский.

На Фиг. 31А-М показано преобразование морфемы или слова, извлеченного из изображения строки текста, в последовательность параметризованных символов.

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

На Фиг. 33 показана простая trie-структура данных.

На Фиг. 34 показаны непараметризованные символы (далее - SFS), используемые для кодирования записей в trie-структуре данных, а также соответствие между параметризованными символами (далее - FSWAP), описанными выше со ссылкой на Фиг. 31А-М и 32, а также непараметризованные символы в одном варианте реализации.

На Фиг. 35 приведено детальное описание преобразования на основе параметров, показанного на Фиг. 34.

На Фиг. 36A-G показано использование trie-структуры, описываемой со ссылкой на Фиг. 33, при идентификации слов словарного состава, аналогичных или идентичных введенному слову.

На Фиг. 37А-В показаны фрагменты таблицы штрафов, используемых при поиске слов и морфем, аналогичных введенной последовательности параметризованных символов, в trie-структуре с записями, закодированными в виде непараметризованных символов.

На Фиг. 38 показаны источники морфем и слов, используемых для создания структуры данных о морфемах и словах, закодированных в виде непараметризованных символов (3022 на Фиг. 30), которые используются для определения потенциальных точек разделения знаков согласно способу и устройству, к которым относится изобретение.

На Фиг. 39A-D приведены блок-схемы, на которых показан один вариант реализации способов и устройств, к которым относится изобретение.

ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ РЕАЛИЗАЦИИ

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

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

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

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

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

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

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

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

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

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

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

Следует пояснить, что исходная ориентация определяется поворотами содержащей текст области в горизонтальной плоскости. На Фиг. 7 показано вращение в горизонтальной плоскости. На Фиг. 7 квадратная область изображения отсканированного документа (702) располагается горизонтально с вертикальной осью вращения (704), проходящей по центру области. При вращении квадратной области по часовой стрелке на 90° получается ориентация (706), показанная на правой стороне Фиг. 7.

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

На Фиг. 8-10 показан подход к определению исходной ориентации области, содержащей текст. На Фиг. 8 показано формирование гистограммы, соответствующей одной ориентации содержащей текста области. На Фиг. 8 содержащая текст область (802) имеет вертикальную ориентацию. Содержащая текст область разделяется на колонки, разграничиваемые вертикальными линиями, такими как вертикальная линия (804). В каждой колонке подсчитывается количество битов со значением «1» на битовой карте, соответствующей содержащей текст области, которое используется для формирования гистограммы (806), показанной над содержащей текст областью. Колонки в содержащей текст области, не содержащие фрагментов символов или, что то же самое, содержащие только биты со значением «0», не имеют соответствующих колонок в гистограмме, тогда как колонки, содержащие фрагменты символов, соотносятся с колонками в гистограмме высотой, соответствующей пропорции битов в колонке со значением «1». В качестве альтернативы высота колонок гистограммы может масштабироваться с учетом абсолютного количества битов со значением «1» или представлять часть битов в колонке со значением «1» или часть количества битов со значением «1» в колонке в отношении общего количества битов со значением «1» в содержащей текст области.

На Фиг. 9 показаны гистограммы, сформированные для колонок и строк надлежащим образом ориентированной содержащей текст области. На Фиг. 9 содержащая текст область (902) выравнивается по границам страницы, строкам текста, параллельного верхней и нижней части страницы, и колонкам текста, параллельного сторонам страницы. Способ формирования гистограмм, описанный выше со ссылкой на Фиг. 8, был применен ко всей содержащей текст области (902) для формирования гистограмм для вертикальных колонок в содержащей текст области (904) и для горизонтальных строк в содержащей текст области (906). Следует отметить, что гистограммы показаны в виде слитных кривых, пики которых, такие как пик (908) в гистограмме (904) соответствуют центральным фрагментам колонок и строк текста, таких как текстовая колонка (910), которой соответствует пик (908), а впадины, такие как впадина (912), соответствуют колонкам и строкам пробелов между колонками и строками текста, таким как колонка пробела (914) между колонками текста (916) и (918). Сетка стрелок (920) на Фиг. 9 указывает на направление вертикальных и горизонтальных разделов, используемых для формирования гистограммы колонок (904) и гистограммы строк (906).

На Фиг. 10 показана та же содержащая текст область изображения, что показана на Фиг. 9, но с другой угловой ориентацией. В случае содержащей текст области с другой ориентацией (1002) применяется тот же метод, что был описан выше со ссылкой на Фиг. 9, когда гистограммы колонок (1004) и гистограммы строк (1006) формируются с помощью разделов колонок и строк в направлении вертикальных и горизонтальных стрелок (1008). В данном случае гистограммы обычно не имеют объектов и не имеют равноудаленных пиков и впадин, как на гистограммах, показанных на Фиг. 9. Причину этому можно легко понять, рассмотрев вертикальную колонку (1010), показанную на Фиг. 10 пунктирными линиями. Данная вертикальная колонка проходит через текстовые колонки (1012-1015) и колонки пробелов (1016-1020). Почти каждая вертикальная колонка и горизонтальная строка, кроме находящихся на крайних концах гистограмм, проходит как через текст, так и через пробел, в результате чего каждая из вертикальных колонок и горизонтальных строк, как правило, содержит биты со значением «1» и биты со значением «0».

Таким образом, программы оптического распознавания символов (OCR) могут изначально определить ориентацию содержащей текст области путем поворота данной области в пределах 90° и вычисления гистограмм колонок и строк на определенных угловых интервалах, в результате чего получается как минимум одна гребневидная гистограмма, а чаще всего две гребневидные гистограммы, как показано на Фиг. 9, с наилучшими соотношениями пик-впадина. Следует также отметить, что о пробелах между символами в строках и колонках можно судить по пробелам (922) и (924) между пиками в гистограммах колонок и строк.

Доступные в настоящее время на рынке способы и устройства OCR

На Фиг. 11А-С показан один подход к преобразованию изображения документа в электронный документ, применяемый в определенных системах OCR, которые доступны в настоящее время на рынке. Это иерархический по сути подход, который может интерпретироваться и реализовываться рекурсивно, хотя также возможны и нерекурсивные или частично рекурсивные способы определения ориентации. После определения начальной ориентации изображение документа (1102) обрабатывается путем разложения изображения документа на высокоуровневые фрагменты или элементы (1104-1106) изображения документа. В примере, приведенном на Фиг. 11А, изображение документа включает рисунок (1110), первый фрагмент текста (1112) и второй фрагмент текста (1114). Это высокоуровневые элементы изображения документа, которые раскладываются на соответствующие им изображение первого текстового блока (1104), изображение второго текстового блока (1105) и рисунок (1106). В данном случае рисунок является фундаментальным элементов изображения документа и не подлежит дальнейшему разложению. Однако на втором уровне разложения изображение первого текстового блока (1104) раскладывается на отдельные изображения текстовых строк (1116-1120), а изображение второго текстового блока (1105) далее раскладывается на изображения текстовых строк (1122-1123). На последнем уровне каждое изображение текстовой строки, такое как изображение текстовой строки (1123) далее раскладывается на отдельные символы, такие как изображения символов (1126-1134), соответствующие изображению текстовой строки (1123). В определенных вариантах реализации в случае языков, в которых слова образуются путем сочетания знаков алфавита, разложение изображений текстовых строк на изображения символов может включать по крайней мере частичное начальное разложение изображений текстовых строк на изображения слов.

Как показано на Фиг. 11А, определенные способы и устройства OCR сначала раскладывают изображение документа (1102) на изображения символов, такие как изображения символов (1126-1134), а затем конструируют электронный документ, соответствующий изображению документа. Во многих из таких устройств изображение символа является окончательной степенью разложения, выполняемого способами и устройствами OCR в отношении текстовых изображений. Способы и устройства OCR далее применяют множество различных методов преобразования изображений отдельных знаков в соответствующую кодировку данных знаков по стандарту Юникод. Конечно, для получения всевозможных видов кодировок символов могут применяться различные преобразования.

Наконец, как показано на Фиг. 11В, данные способы и устройства OCR формируют электронный документ, соответствующий изображению документа, в обратном иерархическом порядке, начиная с кодировок одинарных символов и нетекстовых элементов нижнего уровня. В случае языков, в которых слова образуются путем сочетания символов алфавита, кодировки символов, такие как кодировка символа (1140), сочетаются в слова, такие как слово (1142). На следующем уровне построения электронного документа слова сочетаются в текстовые строки, такие как текстовая строка (1144), содержащая слово (1142). На еще одном уровне построения электронного документа текстовые строки сочетаются во фрагменты текста, такие как фрагмент текста (1146), содержащий строку текста (1144). Наконец, все из элементов документа высшего уровня, таких как рисунки (1106), фрагмент текста (1148) и фрагмент текста (1150), складываются в электронный документ (1152), соответствующий изображению документа (1102). Электронный документ, как описывалось выше, может содержать Юникод-представления символов или знаков алфавита и различные виды контрольных последовательностей для образования рамок, границ и прочих объектов электронного документа. Таким образом, алфавитный символ (1140), как правило, является закодированным в цифровом виде символом, таким, например, как Юникод-символ, который соответствует изображению символа (1133) на Фиг. 11А. Аналогичным образом, как правило, рисунок (1145) является неким видом сжатого файла изображения, соответствующего рисунку (1106), отсканированного как часть изображения документа. Другими словами, если рассматривать разложение изображения документа на элементы изображения документа как древовидный процесс, как показано на Фиг. 11А, тупиковые узлы дерева преобразуются из отсканированных изображений в надлежащие цифровые кодировки, которые представляют информацию, содержащуюся в отсканированных изображениях, и затем цифровые кодировки собираются воедино в рамках процесса, показанного на Фиг. 11В, для создания закодированного в цифровом виде электронного документа.

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

На Фиг. 11С показан один пример формирования нескольких гипотез в ходе разложения изображения документа. На Фиг. 11С исходное изображение документа (1102) согласно одной гипотезе, представленной стрелкой (1160), раскладывается на три компонента более низкого уровня (1104-1106), описанных выше со ссылкой на Фиг. 11А. Однако согласно второй гипотезе (1162) изображение текста может, напротив, быть разложено на один фрагмент текста (1164) и рисунок (1106). В данном случае граница между первым фрагментом текста (1112) и вторым фрагментом текста (1114) может быть нечеткой или полностью отсутствовать, в случае чего способам и устройствам OCR может понадобиться провести проверку двух альтернативных гипотез. Возникновение разветвления многовариантных гипотез, как на этапе разложения, так