Способы и системы эффективного автоматического распознавания символов с использованием леса решений

Способы и системы эффективного автоматического распознавания символов с использованием леса решений

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На Фиг. 13В показан полный набор значений параметров для гипотетического набора символов, показанного на Фиг. 6.

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

На Фиг. 18А-В показана классификация изображений символов с помощью леса решений.

На Фиг. 19 показано небольшое содержащее текст изображение, которое первоначально обрабатывалось системой OCR для получения сетки окон символов (1900), в каждом из которых содержится изображение символа.

На Фиг. 20 показан общий подход к обработке сетки окон символов, показанной на Фиг. 19.

На Фиг. 21 показан первый подход к реализации подпрограммы «process» ((2004) на Фиг. 20).

На Фиг. 22А-В показан второй вариант осуществления подпрограммы «process» ((2004) на Фиг. 20).

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

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

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

На Фиг. 26 показаны отношения между символами, изображениями символов, эталонами и графемами.

На Фиг. 27 показан процесс преобразования изображений символов в коды символов.

На Фиг. 28A-G показан процесс обработки символов в мультикластерной структуре данных.

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

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

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

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

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

На Фиг. 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), обозначаемым сокращенно «wc», и горизонтальным размером окна символа (808), обозначаемым сокращенно «hw». Первым параметром является самый длинный в изображении символа непрерывный горизонтальный отрезок линии, обозначаемый «А» (810). Это самая длинная последовательность смежных темных пикселей на фоне по существу белых пикселей в окне символа. Вторым параметром является самый длинный в изображении символа непрерывный вертикальный отрезок линии (812). Третий параметр представляет собой отношение количество пикселей изображения символа к общему числу пикселей в окне символа, выраженное в процентах; в данном примере это процент черных пикселей в по существу белом окне символа. Во всех трех случаях значения параметров могут быть непосредственно рассчитаны сразу после того, как будет создано растровое отображение окна символа. На Фиг. 8В показаны два дополнительных параметра. Первым параметром является число внутренних горизонтальных белых полос в изображении символа; изображение символа, показанного на Фиг. 8В, имеет одну внутреннюю горизонтальную белую полосу (816). Вторым параметром является число внутренних вертикальных белых полос в изображении символа. В 48-м символе из набора, представленном изображением в окне символа (804), показанном на Фиг. 8В, имеется одна внутренняя вертикальная белая полоса (818). Число горизонтальных белых полос обозначается как «hs», а число внутренних вертикальных белых полос - «vs».

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

Несмотря на то, что значения каждого из параметров, рассмотренных выше в отношении Фиг. 9, имеют относительно небольшие отличия для используемых в качестве примера 48 символов, всего трех параметров достаточно для разделения всех этих символов на 18 частей, или кластеров. На Фиг. 10 показан трехмерный график символов для символов из набора, изображенного в качестве примера на Фиг. 6, на котором каждое из измерений представляет значения одного из трех разных параметров. На Фиг. 10 первая горизонтальная ось (1002) представляет параметр v h ((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), показанный на рисунке 11А. Этот кластер символов включает в себя четыре угловых L-образных символа, отличающихся углом поворота и имеющих коды 26, 32, 38 и 44, а также Т-образный символ с кодом 43 и крестообразный символ с кодом 45. На Фиг. 12А показан отдельный параметр, который можно использовать в комбинации с тремя параметрами, соответствующими каждому из измерений трехмерного пространства параметров, изображенного на Фиг. 10, для полного распознавания каждого из символов в кластере 8. В дальнейшем этот параметр называется «p». Как показано на Фиг. 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А под окном символа, рассчитывается значение нового параметра p. Например, если все четыре переменные Q1, Q2, Q3 и Q4 имеют одинаковые значения, то параметру p будет присвоено значение 0 (1214), что указывает на равенство четырех квадрантов в окне символа относительно количества единиц площади, занимаемой изображением символа. На Фиг. 12В показано значение дополнительного параметра для каждого символа из кластера 8, которое следует рассматривать со ссылкой на Фиг. 12А. Как можно увидеть из значений параметров, связанных с символами на Фиг. 12В, новый параметр, описанный выше касательно Фиг. 12А, имеет разное значение для каждого из шести символов в кластере 8. Другими словами, можно использовать комбинацию трех параметров, используемых для создания трехмерного графика, показанного выше на Фиг. 10, и дополнительного параметра, рассмотренного выше на Фиг. 12А, для однозначной идентификации всех символов в кластере 8.

На Фиг. 13А показан дополнительный параметр, используемый для определения характеристик изображений символов. Ниже дополнительный параметр называется параметром «самый длинный отрезок». Этот параметр показывает направление самого длинного отрезка в изображении символа. Если самым длинным отрезком является вертикальное ребро (1302), параметр самого длинного отрезка имеет значение «0» (1304). Если самым длинным отрезком символа является горизонталь (1306), параметр самого длинного отрезка имеет числовое значение «1» (1308). Если самым длинным отрезком символа является диагональ (1310), параметр самого длинного отрезка имеет числовое значение «2» (1312). Наконец, если такой отрезок отсутствует, как в случае символа, показанного в ячейке (1314) на Фиг. 13А, параметр самого длинного отрезка имеет числовое значение «3» (1316).

На Фиг. 13В показан полный набор значений параметров для гипотетического набора символов, показанного на Фиг. 6. Таблица, показанная на Фиг. 13В, идентична таблице (902), ранее изображенной на Фиг. 9, за исключением двух последних колонок (1320) и (1322), которые включают значения параметра p, описанные выше со ссылкой на Фиг. 12А, и параметра самого длинного отрезка, обсуждавшегося выше со ссылкой на Фиг. 13А.

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