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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ РИСУНКОВ

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

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

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

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

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

На рисунке 6 показан гипотетический набор символов.

На рисунках 7А-В показаны различные аспекты наборов символов для естественных языков.

На рисунках 8А, В показаны параметры и значения параметров, рассчитанные для изображений символов.

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

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

На рисунках 11А, В показаны символы, содержащиеся в каждом из кластеров, представленных точками трехмерного пространства, изображенного на рисунке 10.

На рисунке 12А показан отдельный параметр, который можно использовать в комбинации с тремя параметрами, соответствующими каждому из измерений трехмерного пространства параметров, изображенного на рисунке 10, для полного распознавания каждого из символов в кластере 8 (позиции 1212 и 1214 - фрагменты псевдокода компьютерной программы не переводятся на русский язык).

На рисунке 12В показано значение дополнительного параметра для каждого символа из кластера 8, которое следует рассматривать со ссылкой на рисунок 12А.

На рисунке 13 показано небольшое изображение, содержащее текст, которое было изначально обработано системой OCR для получения сетки окон символов 1300, в каждом из которых содержится изображение символа.

На рисунке 14 показан общий подход к обработке сетки окон символов, показанной на рисунке 13 (1404 на рисунке 14 компьютерная программа не переводится на русский язык).

На рисунке 15 показан первый подход к реализации подпрограммы «process» (компьютерная программа не переводится на русский язык).

На рисунках 16А, В показан второй вариант осуществления подпрограммы «process» (компьютерная программа не переводится на русский язык).

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

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

На рисунках 19А-З показана предварительная обработка изображения символа с использованием структур данных, рассмотренных выше со ссылкой на рисунок 18.

На рисунках 20А-П показана мультикластерная OCR-обработка документа, содержащего изображения символов.

На рисунках 21А-Г с помощью блок-схемы показан один из вариантов осуществления способа мультикластерной 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 небольшой круглый фрагмент изображения 502 печатного документа 504, используемого в качестве примера, показан в увеличенном виде 506. Соответствующий фрагмент оцифрованного изображения отсканированного документа 508 также представлен на рисунке 5. Оцифрованный отсканированный документ включает в себя данные, которые представляют собой двухмерный массив значений пикселей. В представлении 508 каждая ячейка сетки под символами (например, ячейка 509) представляет собой квадратную матрицу пикселей. Небольшой фрагмент 510 сетки показан с еще большим увеличением (512 на рисунке 5), при котором отдельные пиксели представлены в виде элементов матрицы (например, элемента матрицы 514). При таком уровне увеличения края символов выглядят зазубренными, поскольку пиксель является наименьшим элементом детализации, который можно использовать для излучения света заданной яркости. В файле оцифрованного отсканированного документа каждый пиксель представлен фиксированным числом битов, при этом кодирование пикселей осуществляется последовательно. Заголовок файла содержит информацию о типе кодировки пикселей, размерах отсканированного изображения и другую информацию, позволяющую программе отображения оцифрованного отсканированного документа получать данные кодирования пикселей и передавать команды устройству отображения или принтеру с целью воспроизведения двухмерного изображения исходного документа по этим кодировкам. Для представления оцифрованного отсканированного документа в виде монохромных изображений с оттенками серого обычно используют 8-разрядное или 16-разрядное кодирование пикселей, в то время как при представлении цветного отсканированного изображения может выделяться 24 или более бит для кодирования каждого пикселя, в зависимости от стандарта кодирования цвета. Например, в широко применяемом стандарте RGB для представления интенсивности красного, зеленого и синего цветов используются три 8-разрядных значения, закодированных с помощью 24-разрядного значения. Таким образом, оцифрованное отсканированное изображение, по существу, представляет собой документ в той же степени, в какой цифровые фотографии представляют визуальные образы. Каждый закодированный пиксель содержит информацию о яркости света в определенных крошечных областях изображения, а для цветных изображений в нем также содержится информация о цвете. В оцифрованном изображении отсканированного документа отсутствует какая-либо информация о значении закодированных пикселей, например информация, что небольшая двухмерная зона соседних пикселей представляет собой текстовый символ. Фрагменты изображения, соответствующие изображениям символов, могут обрабатываться для получения битов изображения символа, в котором биты со значением «1» соответствуют изображению символа, а биты со значением «0» соответствуют фону. Растровое отображение удобно для представления как полученных изображений символов, так и эталонов, используемых системой OCR для распознавания конкретных символов.

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

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

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

Пример методов и систем OCR

Для перехода к конкретному обсуждению различных методов оптического распознавания символов в качестве примера будет использоваться набор символов для некоторого гипотетического языка. На рисунке 6 показан гипотетический набор символов. На рисунке 6 показаны 48 различных символов, расположенных в 48 прямоугольных областях, таких как прямоугольная область 602. В правом верхнем углу каждой прямоугольной области указан числовой индекс или код символа, вписанный в круг; например, индекс или код «1» 604, соответствует первому символу 606, показанному в прямоугольной области 602. Данный пример выбран для демонстрации работы как существующих в настоящее время способов и систем OCR, так и новых способов и систем, описанных в настоящем документе. Фактически для письменных иероглифических языков, включая китайский и японский языки, для печати и письма могут использоваться десятки тысяч различных символов.

На рисунках 7А-В показаны различные аспекты наборов символов для естественных языков. На рисунке 7А в столбце показаны различные формы изображения восьмого символа из набора, показанного на рисунке 6. В столбце 704 для восьмого символа 702 из набора символов, показанного на рисунке 6, представлены разные формы написания, встречающиеся в разных стилях текста. Во многих естественных языках могут использоваться различные стили текста, а также различные варианты написания каждого символа.

На рисунке 7В показаны разные подходы к распознаванию символов естественного языка. На рисунке 7В конкретный символ естественного языка представлен узлом 710 на схеме 712. Конкретный символ может иметь множество различных общих письменных или печатных форм. В целях оптического распознавания символов каждая из этих общих форм представляется в виде отдельной графемы. В некоторых случаях определенный символ может содержать две или более графем. Например, китайские иероглифы могут содержать комбинацию из двух или более графем, каждая из которых присутствует в других иероглифах. Корейский язык, на самом деле, основан на алфавите, при этом в нем используются корейские морфо-слоговые блоки, содержащие ряд буквенных символов в различных позициях. Таким образом, корейский морфо-слоговой блок может представлять собой символ более высокого уровня, состоящий из множества компонентов графем. Для символа 710, показанного на рисунке 7В, существуют шесть различных графем 714-719. Кроме того, есть одна или более различных печатных или письменных форм начертания графем, каждая из которых представлена соответствующим эталоном. На рисунке 7В каждая из графем 714 и 716 имеет два возможных варианта начертания, представленных эталонами 720-721 и 723-724 соответственно. Каждая из графем 715 и 717-719 связана с одним эталоном 722 и 725-727 соответственно. Например, восьмой символ из набора, показанного в качестве примера на рисунке 6, может быть связан с тремя графемами, первая из которых соответствует начертаниям 702, 724, 725 и 726, вторая - 728 и 730, а третья - 732. В этом примере к первой графеме относятся начертания, в которых используются прямые горизонтальные элементы, ко второй графеме относятся начертания, в которых используются горизонтальные элементы и короткие вертикальные элементы с правой стороны, а к третьей графеме относятся начертания, включающие в себя изогнутые (а не прямые) элементы. В альтернативном варианте осуществления все начертания восьмого символа 702, 728, 724, 732, 725, 726 и 730 можно представить в виде эталонов, связанных с единственной графемой для восьмого символа. В определенной степени выбор графем осуществляется произвольно. В некоторых типах иероглифических языков много тысяч разных графем. Эталоны можно рассматривать в качестве альтернативного представления или изображения символа, при этом они могут быть представлены в виде набора пар «параметр - значение параметра», как описано ниже.

Хотя отношение между символами, графемами и эталонами показано на рисунке 7Б как строго иерархическое, при котором каждая графема связана с одним конкретным родительским символом, фактические отношения не могут быть так просто структурированы. На рисунке 7В показан несколько более сложный набор отношений, когда два символа 730 и 732 являются родительскими для двух разных графем 734 и 736. В качестве еще одного примера можно привести следующие символы английского языка: строчная буква «о», прописная буква «О», цифра «0» и символ градусов «°», которые могут быть связаны с кольцеобразной графемой. Отношения могут быть альтернативно представлены в виде графов или сетей. В некоторых случаях графемы (в отличие от символов или в дополнение к ним) могут отображаться на самых высоких уровнях в рамках выбранного представления отношений. В сущности, идентификация символов, графем, выбор эталонов для конкретного языка, а также определение отношений между ними осуществляются в большой степени произвольно.

На рисунках 8А-В показаны параметры и значения параметров, рассчитанные для изображений символов. Следует заметить, что словосочетание «изображение символа» может описывать печатный, рукописный или отображаемый на экране символ или графему. В следующем примере параметры и значения параметров рассматриваются применительно к изображениям символов, но в фактическом контексте реального языка параметры и значения параметров часто применяются для характеристики и представления изображений графем. На рисунке 8А показано изображение прямоугольного символа 802, полученное из содержащего текст изображения, которое соответствует 22-му символу из набора, показанного в качестве примера на рисунке 6. На рисунке 8В показано изображение прямоугольного символа 804, полученное из содержащего текст изображения, которое соответствует 48-му символу из набора, показанного в качестве примера на рисунке 6. При печати и письме на гипотетическом языке, соответствующем набору символов, приведенному в качестве примера, символы размещаются в середине прямоугольных областей. Если это не так, системы OCR выполнят стадию начальной обработки изображений, изменив ориентацию, масштаб и положение полученных изображений символов относительно фоновой области для нормализации полученных изображений символов для дальнейших стадий обработки.

На рисунке 8А показаны три разных параметра, которые могут использоваться системой OCR для характеристики символов. Следует заметить, что область изображения символа, или окно символа, характеризуется вертикальным размером окна символа 806, обозначаемым сокращенно «vw», и горизонтальным размером окна символа 808, обозначаемым сокращенно «hw». Первым параметром является самый длинный в изображении символа непрерывный горизонтальный отрезок линии, обозначаемый «h» 810. Это самая длинная последовательность смежных темных пикселей на фоне по существу белых пикселей в окне символа. Вторым параметром является самый длинный в изображении символа непрерывный вертикальный отрезок линии 812. Третий параметр представляет собой отношение количество пикселей изображения символа к общему числу пикселей в окне символа, выраженное в процентах; в данном примере это процент черных пикселей в по существу белом окне символа. Во всех трех случаях значения параметров могут быть непосредственно рассчитаны сразу после того, как будет создано растровое отображение окна символа. На рисунке 8В показаны два дополнительных параметра. Первым параметром является число внутренних горизонтальных белых полос в изображении символа; изображение символа, показанного на рисунке 8В, имеет одну внутреннюю горизонтальную белую полосу 816. Вторым параметром является число внутренних вертикальных белых полос в изображении символа. В 48-м символе из набора, представленном изображением в окне символа 804 на рисунке 8В, имеется одна внутренняя вертикальная белая полоса 818. Число горизонтальных белых полос обозначается как «hs», а число внутренних вертикальных белых полос - «vs».

На рисунке 9 показана таблица значений параметров, рассчитанных для всех символов из набора, изображенного в качестве примера на рисунке 6. В каждой строке таблицы 902, показанной на рисунке 9, представлены значения параметров, рассчитанные для конкретного символа. Следующие параметры включают в себя: (1) отношение самого длинного непрерывного горизонтального отрезка линии к окну символа, , 904; (2) отношение самого длинного непрерывного вертикального отрезка линии к вертикальному размеру окна символа, , 906; (3) выраженная в процентах общая площадь, соответствующая изображению символа или черной области, b, 908; (4) количество внутренних вертикальных полос, vs, 910; (5) количество внутренних горизонтальных полос, hs, 912; (6) общее количество внутренних вертикальных и горизонтальных полос, vs+hs, 914; и (7) отношение самого длинного непрерывного вертикального отрезка к самому длинному непрерывному горизонтальному отрезку, , 916. Как и следовало ожидать, в первой строке 920 таблицы 902, представленной на рисунке 9, первый символ набора (606 на рисунке 6) представляет собой вертикальную черту, и численное значение параметра , равное 0,6, значительно больше численного значения параметра , равного 0,2. Символ 606 занимает всего 12 процентов всего окна символа 602. У символа 606 нет ни внутренних горизонтальных, ни внутренних вертикальных белых полос, поэтому значения параметров vs, hs и vs+hs равны 0. Соотношение равно 3. Поскольку используемые в качестве примера символы имеют относительно простую блочную структуру, то значения каждого из параметров в таблице 902 отличаются незначительно.

Несмотря на то что значения каждого из параметров, рассмотренных выше в отношении рисунке 9, имеют относительно небольшие отличия для используемых в качестве примера 48 символов, всего трех параметров достаточно для разделения всех этих символов на 18 частей, или кластеров. На рисунке 10 показан трехмерный график для символов из набора, изображенного в качестве примера на рисунке 6, на котором каждое из измерений представляет значения одного из трех разных параметров. На рисунке 10 первая горизонтальная ось 1002 представляет параметр (916 на рисунке 9), вторая горизонтальная ось 1004 представляет параметр vs+hs (914 на рисунке 9), а третья вертикальная ось 1006 представляет параметр b (908 на рисунке 9). На графике есть 18 различных точек (таких как нанесенная точка 1008), каждая из которых показана в виде небольшого черного диска с вертикальной проекцией на горизонтальную плоскость, проходящую через оси 1002 и 1004; эта проекция представлена в виде вертикальной пунктирной линии, такой как вертикальная пунктирная линия 1010, соединяющая точку 1008 с ее проекцией на горизонтальную плоскость 1012. Код или номер последовательности символов, которые соответствуют определенной точке на графике, перечислены в скобках справа от соответствующей точки. Например, символы 14, 20 и 37 (1014) соответствуют одной точке 1016 с координатами (1, 0, 0,32) относительно осей 1002, 1004 и 1006. Каждая точка связана с номером части или кластера, который указан в небольшом прямоугольнике слева от точки. Например, точка 1016 связана с кластером под номером «14» 1018. На рисунках 11А-В показаны символы, содержащиеся в каждом из кластеров, представленных точками трехмерного пространства, изображенного на рисунке 10. Рассмотрев символы, входящие в состав этих кластеров или частей, можно легко заметить, что три параметра, используемые для распределения символов в трехмерном пространстве, показанном на рисунке 10, эффективно разбивают 48 символов, используемых в качестве примера, на связанные наборы символов.

Можно использовать дополнительные параметры для однозначного распознавания каждого символа в каждом кластере или части. Рассмотрим, например, кластер 8 (1102), показанный на рисунке ПА. Этот кластер символов включает в себя четыре угловых (L-образных) символа, отличающихся углом поворота и имеющих коды 26, 32, 38 и 44, а также Т-образный символ с кодом 43 и крестообразный символ с кодом 45. На рисунке 12А показан отдельный параметр, который можно использовать в комбинации с тремя параметрами, соответствующими каждому из измерений трехмерного пространства параметров, изображенного на рисунке 10, для полного распознавания каждого из символов в кластере 8. Как показано на рисунке 12А, окно символа 1202 делится на четыре квадранта: Q1 1204, Q2 1205, Q3 1206 и Q4 1207. После этого в каждом квадранте вычисляется площадь, занимаемая изображением символа, которая указывается рядом с квадрантом. Например, в квадранте Q1 1204 часть изображения символа занимает 13,5 единиц площади 1210. Затем вычисленные значения единиц площади каждого квадранта присваиваются переменным Q1, Q2, Q3 и Q4. Следовательно, в примере, представленном на рисунке 12А, переменной Q1 присвоено значение 13,5, переменной Q2 присвоено значение 0, переменной Q3 присвоено значение 18, а переменной Q4 присвоено значение 13,5. Затем согласно небольшому фрагменту псевдокода 1212, представленному на рисунке 12А под окном символа, рассчитывается значение нового параметра р. Например, если все четыре переменные Q1, Q2, Q3 и Q4 имеют одинаковые значения, то параметру p будет присвоено значение 0 (1214), что указывает на равенство четырех квадрантов в окне символа относительно количества единиц площади, занимаемой изображением символа. На рисунке 12 В показано значение дополнительного параметра для каждого символа из кластера 8, которое следует рассматривать со ссылкой на рисунок 12А. Как можно увидеть из значений параметров, связанных с символами на рисунке 12В, новый параметр, описанный выше касательно рисунка 12А, имеет разное значение для каждого из шести символов в кластере 8. Другими словами, можно использовать комбинацию трех параметров, используемых для создания трехмерного графика, показанного на рисунке 10, и дополнительного параметра, рассмотренного выше на рисунке 12А, для однозначной идентификации всех символов в кластере 8.

На рисунке 13 показано небольшое изображение, содержащее текст, которое было изначально обработано системой OCR для получения сетки окон символов 1300, в каждом из которых содержится изображение символа. Для большей наглядности на рисунке 13 показана сетка окон символов 1300, не содержащая изображений символов. Для упорядочивания окон символов используется вертикальный индекс i 1302 и горизонтальный индекс j 1304. Для облегчения понимания примера, рассматриваемого ниже, в нем будет идти речь о символах и изображениях символов, а не о графемах. В этом примере предполагается, что существует однозначное соответствие между символами, графемами и эталонами, используемыми для идентификации изображений символов в окнах символов. Кроме сетки окон символов 1300, на рисунке 13 также показан массив, или матрица, 1306 эталонов, каждая ячейка которой (например, ячейка 1308) включает в себя эталон. Эталоны представляют собой наборы пар «параметр-значение параметра», где параметры выбираются для однозначного распознавания изображений символов, как было описано выше со ссылкой на рисунки 8А-12В. На рисунке 13 также показан массив параметров 1310, представленный в виде набора пар фигурных скобок, таких как пара фигурных скобок 1312. Каждая пара фигурных скобок представляет собой функционал, который рассчитывает значение параметра относительно изображения символа.

На рисунке 14 показан общий подход к обработке сетки окон символов, показанной на рисунке 13. На самом высоком уровне обработка может рассматриваться как вложенный цикл for 1402, в котором вызывается подпрограмма «process» 1404 для анализа каждого окна символа 1406 с целью формирования соответствующего кода символа 1408. Другими словами, в примере с псевдокодом сетка окон символов представляет собой двухмерный массив «page_of_text», а система OCR формирует двухмерный массив кодов символов «processed_text» на основе двухмерного массива окон символов «page_of_text». На рисунке 14 дугообразные стрелки, такие как дугообразная стрелка 1410, используются для демонстрации порядка обработки первой строки двухмерного массива или сетки окон символов 1300, а горизонтальные стрелки, такие как стрелка 1412, показывают обработку следующих строк, осущес