ОБЛАСТЬ ТЕХНИКИ
Настоящая заявка относится к автоматической обработке изображений отсканированных документов и других изображений, содержащих текст, и, в частности, к способам и системам эффективного преобразования изображений символов, полученных из отсканированных документов, в кодовые комбинации соответствующих символов с использованием множества кластеров эталонов символов и леса решений.
УРОВЕНЬ ТЕХНИКИ
Печатные, машинописные и рукописные документы на протяжении долгого времени используются для записи и хранения информации. Несмотря на современные тенденции отказа от бумажного делопроизводства, печатные документы продолжают широко использоваться в коммерческих организациях, учреждениях и домах. С развитием современных компьютерных систем создание, хранение, поиск и передача электронных документов превратились, наряду с непрекращающимся применением печатных документов, в чрезвычайно эффективный и экономически выгодный альтернативный способ записи и хранения информации. Из-за подавляющего преимущества в эффективности и экономической выгоде, обеспечиваемого современными средствами хранения и передачи электронных документов, печатные документы легко преобразуются в электронные с помощью различных способов и систем, включающих преобразование печатных документов в цифровые изображения отсканированных документов с использованием электронных оптико-механических сканирующих устройств, цифровых камер, а также других устройств и систем, и последующую автоматическую обработку изображений отсканированных документов для получения электронных документов, закодированных в соответствии с одним или более различными стандартами кодирования электронных документов. Например, в настоящее время можно использовать настольный сканер и современные программы оптического распознавания символов («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) отношение самого длинного непрерывного горизонтального отрезка линии к окну символа, 
Несмотря на то, что значения каждого из параметров, рассмотренных выше в отношении Фиг. 9, имеют относительно небольшие отличия для используемых в качестве примера 48 символов, всего трех параметров достаточно для разделения всех этих символов на 18 частей, или кластеров. На Фиг. 10 показан трехмерный график символов для символов из набора, изображенного в качестве примера на Фиг. 6, на котором каждое из измерений представляет значения одного из трех разных параметров. На Фиг. 10 первая горизонтальная ось (1002) представляет параметр 
Можно использовать дополнительные параметры для однозначного распознавания каждого символа в каждом кластере или части. Рассмотрим, например, кластер 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С показано построение четырех деревьев принятия решений из четырех подмножеств гипотетического набора символов, показанного на Фиг. 6. На Фиг. 14А показано 36 символов, выбранных из 48 символов гипотетического набора символов, показанного на Фиг. 6. Этот первый поднабор символов затем используется для построения дерева принятия решений, которое может использоваться для классификации входного символа, который лучше всего соответствует конкретному символу в подмножестве символов, показанному на Фиг. 14А. На Фиг. 14В показана таблица значений параметров для 36 символов из подмножества символов, показанных на Фиг. 14А. Значения этих параметров используются для построения дерева принятия решений. На Фиг. 14С показано дерево принятия решений, построенное для подмножества символов, показанных на Фиг. 14А, на основе значений параметров для символов, показанных на Фиг. 14В. Следует отметить, что значение параметра, показанное на Фиг. 14В, является подмножеством полной таблицы значений параметров, показанной на Фиг. 13В.
Существует много различных типов деревьев принятия решений. Деревья принятия решений, созданные в примере, показанном на Фиг. 14А-17С, являются бинарными деревьями решений. Каждый узел дерева решений, такой как узел (1402) на Фиг. 14С, принимает решение,, на какой из двух узлов нижнего уровня (1404) и (1406), следует перейти при обходе дерева решений на основе набора значения параметров, вычисленных для изображения символа. Дерево принятия решений создается с помощью подмножества символов, показанного на Фиг. 14А, а также значения параметра, показанного на Фиг. 14В. В качестве первого шага при построении дерева принятия решений рассматриваются различные значения параметров для каждого из девяти параметров, рассчитанных для каждого символа изображения в подмножестве символ-изображение, с целью определения конкретного параметра, который наиболее равномерно делит подмножество изображений символов на две части, а также для определения его порогового числового значения. В случае подмножества символов, показанного на Фиг. 14А, параметр 
Опять же, существует много различных типов деревьев решений и методов построения таких деревьев. В данном примере каждый узел включает простое испытание, которое сравнивает значение параметра с пороговым значением. В других типах деревьев решений испытания могут быть более сложными и могут включать несколько параметров. В определенных видах деревьев решений параметры, используемые для испытаний, выбирают из случайных подмножеств параметра с целью введения случайности по отношению к серии деревьев принятия решений, созданных для характеристики определенного набора символов или других объектов. Выбор параметров и пороговых значений может использоваться для минимизации или максимизации некоторой целевой функции, в том числе целевых функций, основанных на информационно-теоретических понятиях энтропии и прироста информации. Как дополнительно обсуждается ниже, несколько деревьев решений, построенных для конкретного набора изображений символов или других объектов, с другим подмножеством объектов, используемым для построения каждого из множества деревьев решений, могут совместно образовать лес решений, что часто обеспечивает более надежную и точную классификацию. По темам деревьев решений, лесов решений и случайных лесов решений было выполнено значительное количество исследований и разработок, в результате которых были получены подробные характеристики и разработаны концепции деревьев решений и лесов решений, а также их применения в конкретных типах предметных областей. Поскольку в настоящем примере используются простые бинарные деревья решений, в соответствии с настоящим документом для обработки изображений символов в системах OCR может использоваться любое дерево решений из широкого спектра различных типов деревьев решений и любой лес решений из широкого спектра различных типов лесов решений.
На Фиг. 14С дерево решений (1400) имеет пять полных уровней узлов (1414)-(1418). Большинство узлов шестого уровня (1420) являются конечными узлами, однако в некоторых случаях на шестом уровне имеются такие узлы (1422)-(1425), которые создают пары конечных узлов на седьмом уровне. Как дополнительно описано ниже, можно классифицировать произвольное изображение символа как соответствующее одному из 36 символов в наборе символов, показанном на Фиг. 14А, путем расчета значений числового параметра для изображения символа, а затем обходя дерево от корневого узла к конечному узлу, используя эти значения параметров и испытания, выполняемые в каждом узле. На Фиг. 15А-С показано построение второго дерева решений (1500) из второго набора из 36 символов, показанного на Фиг. 15А, выбранного из 48 символов гипотетического набора символов, показанного на Фиг. 6. Аналогичным образом на Фиг. 16А-С показано построение третьего дерева решений (1600) из третьего подмножества символов, выбранных из 48 символов гипотетического набора символов, показанного на Фиг. 6. Наконец, на Фиг. 17А-С показано построение четвертого дерева решений (1700) из четвертого подмножества символов, выбранных из набора 48 гипотетических символов, показанных на Фиг. 6. В этом примере каждое из четырех деревьев принятия решений (1400), (1500), (1600), (1700) строится из другого подмножества 36 символов, выбранных из 48 символов гипотетического набора символов, показанных на Фиг. 6. Однако это несколько искусственный пример. В общем случае, когда из обучающей выборки строится лес деревьев решений, для построения каждого дерева решений каждый раз случайным образом с заменой выбирается некоторая относительно большая доля объектов в обучающем наборе. В том случае, когда для построения каждого дерева случайным образом выбираются 90% из объектов, то можно ожидать, что среднее перекрытие обучающих объектов, использующихся для построения любой конкретной пары деревьев, будет превышать 90%, поскольку случайный выбор объектов каждый раз производится из всей совокупности объектов. Тем не менее, этот пример дает простую иллюстрацию построения и использования леса решений.
На Фиг. 18А-В показана классификация изображений символов с помощью леса решений. На Фиг. 18А показаны три изображения символов (1802), (1804) и (1806) вместе с числовыми значениями, рассчитанными для этих изображений символов для девяти рассмотренных выше параметров (1808), (1810) и (1812), соответственно. Символ изображения (1802) - это точное совпадение изображения символа для символа 22 набора гипотетических символов, изображенных на Фиг. 6. Таким образом, параметры (1808), вычисленные для этого изображения символа, идентичны параметрам, показанным в строке (1319) на Фиг. 13В. Изображение символа (1804) аналогично изображению символа (1802), но относительные ширины сегментов были уменьшены, что соответствует несколько более тонкому символу. Изображение символа (1806) представляет собой более тонкий горизонтальный отрезок с двумя обращенными внутрь удлинениями на вершинах вертикальных элементов символа. Значения параметров (1810), вычисленные для изображения символа (1804), и значения параметров (1812), вычисленные для изображения символа (1806), не соответствуют ни одному из значений параметров, показанных на Фиг. 13В, поскольку изображения символов (1804) и (1806) не соответствует ни одному из изображений для символов гипотетического набора символов, показанного на Фиг. 6.
На Фиг. 18 В показано использование небольшого леса решений, включающего деревья решений (1400), (1500), (1600) и (1700), изображенных на Фиг. 14С, 15С, 16С, и 17С, соответственно. Каждая строка текста справа от изображений символов на Фиг. 18В представляет собой обход одного из четырех деревьев принятия решений. Например, строка текста (1820) на Фиг. 18В представляет обход дерева принятия решений (1400) на Фиг. 14С, именуемого «дерево 1», используя параметры (1808), вычисленные для изображения символа (1802). Первый или корневой узел ((1402) на Фиг. 14С) дерева решений (1400) выполняет проверку: 
В рассматриваемом простом примере все три вариации U-образного символа 22 (1802), (1804) и 1806, были охарактеризованы как символы, имеющие код символа 22, или код символа 22 или 45, согласно лесу решений, содержащему деревья решений (1400), (1500), (1600) и (1700). Тем не менее, изображения U-образных символов, которые больше отклоняются от традиционного изображения символа, показанного на Фиг. 6 для кода символа 22, скорее всего будут давать более различающиеся результаты. Лес из четырех деревьев решений в этом примере не очень надежен по многим причинам. Одна из причин этого заключается в том, что большинство решений в четырех деревьях принятия решений содержат проверки, которые составляют лишь небольшую часть от общего числа параметров. Таким образом, деревья принятия решений в основном полагаются на немногие из девяти параметров. Кроме того, числовые значения параметров в примере не обязательно соотносятся со степенью внешнего соответствия изображениям символов, формирующих числовые значения. Например, числовые значения параметра p, обсуждаемые со ссылкой на Фиг. 12А, не имеют численного представления степени сходства между символами. Другая проблема заключается в том, что каждое дерево решений было построено с использованием всего 75% от общего числа символов, причем эти 75% символов не были выбраны случайным образом. Следовательно, существует значительно меньшее перекрытие в наборах символов, используемых для построения дерева, чем обычно используется для получения надежного леса решений. Наконец, практический лес решений, скорее всего, включает большее количество деревьев решений, построенных на основе подмножеств гораздо большего набора лучше распределенных параметров.
На Фиг. 19 показано небольшое содержащее текст изображение, которое первоначально обрабатывалось системой OCR для получения сетки окон символов (1900), в каждом из которых содержится изображение символа. Для большей наглядности на Фиг. 19 показана сетка окон символов (1900), не содержащая изображений символов. Для упорядочивания окон символов используется вертикальный индекс j (1902) и горизонтальный индекс j (1904). Для облегчения понимания примера, рассматриваемого ниже, в нем будет идти речь о символах и изображениях символов, а не о графемах. В этом примере предполагается, что существует однозначное соответствие между символами, графемами и эталонами, используемыми для идентификации изображений символов в окнах символов. Кроме сетки окон символов (1900), на Фиг. 19 также показан массив, или матрица, (1906) эталонов, каждая ячейка которой (например, ячейка 1908) включает в себя эталон. Эталоны представляют собой наборы пар «параметр - значение параметра», где параметры выбираются для однозначного распознавания изображений символов, как было описано выше со ссылкой на рисунки 8А-12В. На Фиг. 19 также показан массив параметров (1910), представленный в виде набора пар фигурных скобок, таких как пара фигурных скобок (1912). Каждая пара фигурных скобок представляет собой функционал, который рассчитывает значение параметра относительно изображения символа.
На Фиг. 20 показан общий подход к обработке сетки окон символов, показанной на Фиг. 19. На самом высоком уровне обработка может рассматриваться как вложенный цикл for (2002), в котором вызывается подпрограмма «process» (2004) для анализа каждого окна символа (2006) с целью формирования соответствующего кода символа (2008). Другими словами, в примере с псевдокодом сетка окон символов представляет собой двухмерный массив «page_of_text» (страница текста), а система OCR формирует двухмерный массив кодов символов «processed_text» (обработанный текст) на основе двумерного массива окон символов «page_of_text». На Фиг. 20 дугообразные стрелки, такие как дугообразная стрелка (2010), используются для демонстрации порядка обработки первой строки двухмерного массива или сетки окон символов (1900), а горизонтальные стрелки, такие как стрелка (2012), показывают обработку следующих строк, осуществляемую в цикле for (2002). Другими словами, сетка окон символов (1900) обрабатывается согласно указанному выше порядку обработки, при этом каждое окно символа в сетке обрабатывается отдельно для формирования соответствующего кода символа.
На Фиг. 21 показан первый подход к реализации подпрограммы «process» ((2004) на Фиг. 20). Изображение символа, находящееся в окне символа (2102), используется в качестве входного параметра для подпрограммы «process». Подпрограмма «process» используется для расчета значений восьми разных параметров p1-p8, используемых в данном примере для получения отличительных признаков изображений символов путем восьмикратного вызова подпрограммы «parameterize» (2104), как показано на Фиг. 21. Подпрограмма «parameterize» использует в качестве аргументов изображение символа и целочисленное значение, указывающее, для какого параметра необходимо рассчитать и вернуть рассчитанное значение. Значения параметров хранятся в массиве значений параметров «p_values». Затем, как показано дугообразными стрелками, такими как дугообразная стрелка (2106), подпрограмма «process» перебирает все эталоны (2108), соответствующие символам языка, сравнивая рассчитанные значения параметров для изображения символа, хранящиеся в массиве «p_values» с предварительно рассчитанными значениями параметров каждого эталона, как показано на иллюстрации операции сравнения (2110) на Фиг. 21. Эталон, параметры которого больше всего соответствуют рассчитанным параметрам для изображения символа, выбирается в качестве эталона соответствия, а код символа, который соответствует этому эталону, используется в качестве возвращаемого значения подпрограммы «process». В качестве примера псевдокода, используемого для этого первого варианта осуществления подпрограммы «process», приведен псевдокод (2112) на Фиг. 21. В первом цикле for (2114) рассчитываются значения параметров для входного символа s. Затем в нескольких вложенных циклах for внешнего цикла for (2116) анализируется каждый эталон из массива или вектора эталонов (2108) согласно порядку, указанному дугообразными стрелками, такими как дугообразная стрелка (2106). Во внутреннем цикле for (2118) вызывается подпрограмма «compare» для сравнения каждого рассчитанного значения параметра изображения символа с соответствующим предварительно рассчитанным значением параметра эталона, а общий результат сравнения записывается в локальную переменную t. Максимальное значение, накопленное в результате сравнения, хранится в локальной переменной score, а индекс эталона, который наиболее точно соответствует изображению символа, хранится в переменной p (2120). Код символа, связанный с эталоном p, возвращается подпрограммой «process» (2120) в качестве результата.
Наконец, на Фиг. 21 показана грубая оценка вычислительной сложности первого варианта осуществления подпрограммы «process» (2122). Количество окон символов для содержащего текст изображения равно N=i×j. В текущем примере N=357. Разумеется, количество изображений символов, которое необходимо обработать, зависит от типа документа и количества изображений в нем, а также от языка и других параметров. Однако обычно количество изображений символов N может изменяться от нескольких десятков до нескольких сотен для каждого изображения документа. Количество эталонов, с которыми сравниваются изображения символов, представлено параметром P. Для многих алфавитных языков, включая большинство европейских языков, количество эталонов может быть относительно небольшим, что соответствует относительно небольшому множеству символов алфавита. Однако для таких языков, как китайский, японский и корейский количество эталонов может изменяться от десятков тысяч до сотен тысяч. Поэтому при обработке таких языков значение параметра P значительно превышает значение параметра N. Количество параметров, используемых для получения отличительных признаков каждого изображения символа и эталона, представлено параметром R. Следовательно, общая вычислительная сложность оценивается как NPR. Коэффициент N берется из внешних вложенных циклов for, показанных на Фиг. 20. Коэффициенты PR берутся из вложенных циклов for (2116) и (2118) варианта осуществления подпрограммы «process» (2112), показанной на Фиг. 21. Другими словами, подпрограмма «process» вызывается один раз для каждого из N изображений символов, при этом каждый вызов или обращение к подпрограмме «process» приводит к R сравнениям с каждым из P эталонов. При таком способе анализа изначально вычисленное значение параметра считается постоянной величиной. Вариант осуществления алгоритма, приведенного на Фиг. 21, можно улучшить различными способами. Например, можно сравнивать только определенное подмножество параметров из общего количества параметров, необходимое для однозначного сопоставления изображения символа с конкретным эталоном. Таким образом, может потребоваться произвести среднее количество сравнений параметров 
На Фиг. 22А-В показан второй вариант осуществления подпрограммы «process» ((2004) на Фиг. 20). Во втором варианте осуществления изображение символа (2202) также используется в качестве входного параметра подпрограммы «process». Однако в данном варианте осуществления алгоритма эталоны группируются в кластеры, такие как кластеры, рассмотренные ранее на примере на Фиг. 11А-В. Подпрограмма «process» используется для расчета определенного количества значений параметров (2204), достаточного для определения наиболее соответствующего кластера при переборе кластеров эталонов (2206). Таким образом, для выбора наиболее подходящего кластера эталонов сначала используется относительно простая операция сравнения (2208). Затем эталоны (2210) из выбранного кластера эталонов (2211) перебираются с помощью второй довольно простой операции сравнения (2212), для которой используются некоторые дополнительные значения параметров (2214), необходимые для определения наиболее подходящего эталона среди относительно малого числа эталонов (2210), содержащихся в кластере. Псевдокод для второго варианта осуществления подпрограммы «process» представлен на Фиг. 22В. В первом вложенном цикле for (2220) выбирается наиболее подходящий или лучший среди имеющихся кластер эталонов, а во втором вложенном цикле for (2222) определяется наиболее подходящий эталон среди представленных в выбранном кластере. Начальный набор параметров, используемых для определения наилучшего кластера, рассчитывается в цикле for (2224), а дополнительные параметры, необходимые для выбора эталона из числа эталонов выбранного кластера, рассчитываются в цикле for (2226). На Фиг. 22В также представлена приблизительная оценка вычислительной сложности второго варианта осуществления подпрограммы «process» (2230). Как указано, оценочная вычислительная сложность для второго варианта осуществления подпрограммы «process» составляет:
N(CR1+P'R2), где:
количество символов на странице = N;
количество кластеров = C;
количество эталонов/кластер = P′;
количество исходных параметров = R;
количество дополнительных параметров = R2.
Поскольку значение P' по существу намного меньше значения P, а значение C еще меньше, то вычислительная сложность второго варианта осуществления подпрограммы «process» вполне приемлема по сравнению с вычислительной сложностью первого варианта осуществления подпрограммы «process».
Другим подходом к улучшению первого варианта осуществления подпрограммы «process», рассмотренного выше со ссылкой на Фиг. 21, является сортировка эталонов в векторе, или массиве, эталонов, чтобы наиболее вероятные эталоны, соответствующие наиболее часто встречающимся символам, рассматривались в самом начале перебора вектора, или массива эталонов. Когда поиск соответствующего эталона прерывается вследствие нахождения эталона, результат сравнения которого превышает некоторое пороговое значение, и когда эталоны отсортированы по частоте употребления, соответствующей вероятности появления символов в обрабатываемом изображении, содержащем текст, вычислительная сложность значительно снижается. Однако частота появления символов в конкретных изображениях, содержащих текст, может сильно варьироваться в зависимости от типа документа или страницы, которые были отсканированы для получения изображения, и неизвестна до обработки системой OCR. Сортировка эталонов, приводящая к значительному снижению вычислительной сложности для одного типа документа, может значительно повысить вычислительную сложность для другого типа документа. Например, общий статистический анализ различных типов текстовых документов на определенном языке, включая романы, рекламные объявления, учебники и другие подобные документы, может позволить получить общий вариант сортировки эталонов по частоте появления символов. Однако в некоторых документах и текстах, относящихся к профильным сферам деятельности, частота появления символов может совершенно отличаться. В этом случае для документов, относящихся к определенным сферам деятельности, наиболее часто встречающиеся символы могут оказаться расположены ближе к концу обрабатываемого вектора, или матрицы, эталонов, отсортированных в соответствии с общей частотой появления символов. Второй вариант осуществления подпрограммы «process», рассмотренный выше со ссылкой на Фиг. 22А-В, по существу приводит к значительному снижению вычислительной сложности и соответствующему увеличению скорости обработки. Как правило, требуется произвести значительно меньше сравнений для нахождения соответствующего эталона для каждого изображения символа. Однако второй вариант осуществления связан с потенциально серьезной проблемой, которая состоит в том, что при неудачном выполнении первого вложенного цикла for, в котором осуществляется выбор кластера, подпрограмма «process» не сможет найти правильный соответствующий символ. В этом случае правильный соответствующий символ будет находиться в другом кластере, который не будет анализироваться во втором вложенном цикле for. Хотя примеры наборов символов и кластеров, представленные выше, являются относительно простыми, как и параметры, используемые для определения их отличительных особенностей, для таких языков, как китайский и японский, подобная задача является более сложной и подверженной ошибкам из-за несовершенства печати, повреждения документа, а также из-за различных типов ошибок, которые могут возникнуть при сканировании и на начальных стадиях процесса OCR. Таким образом, вероятность неправильного выбора кластера в реальных условиях очень высока.
На Фиг. 23 показан третий вариант осуществления подпрограммы «process», рассмотренной в предыдущем подразделе, с использованием тех же иллюстраций и условных обозначений в псевдокоде, которые использовались в предыдущем подразделе. Как показано на Фиг. 23, третий вариант осуществления подпрограммы «process» применяет дополнительную структуру данных (2302), обозначаемую как «голоса» («votes»). Структура данных votes содержит целочисленное значение для каждого эталона. При начальной инициализации эта структура содержит нулевые значения для всех эталонов. После этого на первой стадии предварительной обработки, представленной двойным вложенным циклом for (2304) на Фиг. 23, для каждого изображения символа в текстовом документе (1900) назначается новый набор кластеров, а эталоны в кластерах упорядочиваются согласно голосам, собранным в структуре данных «votes». Другими словами, эталоны упорядочиваются в заново выделенном наборе, или списке, кластеров, благодаря чему эталоны, с наибольшей вероятностью соответствующие изображению текущего символа, встречаются в начале перебора эталонов. Значения набора сравниваемых параметров, рассчитанные для текущего изображения символа, сравниваются со значениями параметров каждого эталона, при этом голоса отдаются тем эталонам, которые (по результатам сравнения) имеют сходство с изображением символа, превышающее установленный порог. В некоторых вариантах осуществления кластеры также могут быть отсортированы в пределах набора кластеров по накопленному сходству их эталонов с изображением символа.
После стадии предварительной обработки, осуществляемой вложенными циклами for-(2304), каждое изображение символа обрабатывается третьим вариантом осуществления подпрограммы «process». Псевдокод для третьего варианта осуществления подпрограммы «process» (2310) представлен на Фиг. 23. В данном варианте осуществления подпрограмма «process» принимает в качестве входных параметров изображение символа и набор кластеров, подготовленный для изображения символа на стадии предварительной обработки и хранящийся в массиве NxtLvlClusters, а возвращает указатель на список потенциально соответствующих эталонов. В первом цикле for (2312) рассчитываются значения параметров, которые используются для определения эталонов, соответствующих принятому изображению символа. Во втором внешнем цикле for (2314) рассматриваются все кластеры, пока не заполнится список потенциально соответствующих эталонов. Другими словами, когда находится максимальное количество потенциально соответствующих эталонов, этот внешний цикл for прерывается. Во внутреннем цикле for (2316) для каждого эталона в кластере вызывается функция «similar», осуществляющая определение того, является ли эталон достаточно похожим на изображение символа, чтобы его можно было добавить в список потенциально соответствующих эталонов. Когда список потенциально соответствующих эталонов заполнен, внутренний цикл for также прерывается. На Фиг. 23 представлена оценка вычислительной сложности третьего варианта осуществления подпрограммы «process» 2320. Поскольку как внешний, так и внутренний циклы for (2314) и (2316) прерываются, когда найдено достаточное количество потенциально соответствующих эталонов, а векторы, или списки, эталонов в каждом кластере отсортированы по частоте появления в обрабатываемом документе, то в третьем варианте осуществления подпрограммы «process» требуется выполнить лишь относительно небольшое количество сравнений по сравнению со вторым вариантом осуществления подпрограммы, что и показано дробью 
Рассмотренная выше информация, включая третий вариант осуществления, представленный на Фиг. 23, создает основу для описания определенного аспекта этого обобщенного третьего варианта осуществления, к которому относится настоящий документ. Следует четко понимать, что описанные выше варианты осуществления представляют собой обобщенные варианты осуществления и что конкретный вариант осуществления системы OCR может применять любой из большого количества возможных альтернативных вариантов осуществления.
Настоящий документ относится к описанию логики управления и структур данных в системе OCR, которые можно использовать как для кластеризации эталонов, так и на стадии предварительной обработки, рассмотренной выше, в ходе которой графемы в эталонах могут быть отсортированы по частоте появления в отсканированном изображении, содержащем текст, или в наборе отсканированных изображений. Эти логика управления и структуры данных применяются в системе OCR для реализации стадий предварительной обработки/кластеризации, в ходе которых фиксированный набор параметров связывается с каждым кластером и применяется при сравнении изображения символа с эталонами, содержащимися в кластере. Кластеры можно использовать в различных локальных операциях или на разных этапах сложной задачи оптического распознавания символов, при этом конкретные параметры (а также количество этих параметров), используемые для сравнения изображения символа с эталонами, содержащимися в кластере, могут отличаться в различных локальных операциях и на разных этапах, а также часто могут быть различными в разных кластерах. В альтернативном варианте реализации кластеры не используются.
На Фиг. 24 показаны структуры данных, обеспечивающие кластеризацию и предварительную обработку в одном варианте осуществления системы OCR, включающей в себя третий вариант осуществления подпрограммы «process», описанный выше. Первой структурой данных является массив, или вектор (2402), обозначенный как «votes» («голоса»). В описанном варианте осуществления массив «votes» содержит один элемент для каждой графемы языка. Массив «votes» индексируется целыми значениями кодов графем. Другими словами, каждой графеме присваивается уникальный целочисленный идентификатор или код графемы, который используется в качестве индекса массива «votes». Как показано на Фиг. 24, массив «votes» может содержать n элементов, где n представляет собой количество графем в языке, а коды графем монотонно возрастают от 0 до n. Разумеется, структура данных «votes» может быть альтернативно реализована в виде разреженного массива, когда коды графем возрастают немонотонно, в виде списка, или с использованием других типов структур данных.
На Фиг. 24 показана вторая структура данных (2404), которая представляется собой массив экземпляров класса «parameter» («параметр»). Как и в случае со структурой данных «votes», массив «parameters» может быть альтернативно реализован с использованием разных структур данных, включая списки, разреженные массивы и другие структуры данных. В текущем рассматриваемом варианте осуществления массив «parameters» включает в себя p записей или элементов, которые проиндексированы с помощью монотонно увеличивающихся чисел 0, 1, 2, …, p. Каждый экземпляр класса "parameter" представляет один из различных параметров, используемых для характеристики изображений символов и эталонов, как описывалось выше.
На Фиг. 24 дополнительно показана структура данных кластера (2406), которая представляет собой кластер или набор эталонов. Структура данных кластера включает в себя массив «clusterParameters» (2408), в котором содержатся параметры, применяемые для определения отличительных признаков эталонов в кластере в определенный момент времени, а также для определения отличительных признаков изображений символов для их сравнения с эталонами, содержащимися в кластере. Каждый элемент в массиве «clusterParameters» содержит индекс для массива «параметры» (2404). Используя индексы в массиве «параметры» (2404), можно легко изменить или переконфигурировать конкретные параметры, а также количество параметров, используемых для сравнения, вследствие чего конфигурация кластера может быть эффективно изменена для различных локальных операций или этапов. Структура данных кластера также включает в себя целочисленный параметр число (2410), который указывает количество индексов параметров, содержащихся в массиве «clusterParameters». Структура данных кластера дополнительно содержит параметр «cutoff» («отсечка») (2412), имеющий формат с плавающей запятой (или формат двойной точности) и содержащий пороговое значение для оценки эталонов, находящихся в кластере, на предмет их соответствия изображению символа. Наконец, структура данных кластера (2406) содержит ряд структур данных эталона (2414)-(2422). Структуры данных эталона обсуждаются ниже.
На Фиг. 25А-Н показана предварительная обработка изображения символа с использованием структур данных, рассмотренных выше со ссылкой на Фиг. 24. На Фиг. 25А показаны «голоса» для структуры данных (2402), рассмотренной выше со ссылкой на Фиг. 24, а также структура данных одного эталона (2502), выбранная из эталонов, содержащихся в структуре данных кластера (2406), которая также обсуждалась выше со ссылкой на Фиг. 24. Каждая структура данных эталона содержит номер эталона (2504) и набор значений параметров (2505), рассчитанных для эталона с помощью параметров, ссылки на которые получены из индексов, содержащихся в массиве «clusterParameters» (2408), который находится в структуре данных кластера (2406). Как отмечалось выше, важно помнить, что изображения символов масштабируются, поворачиваются и преобразуются для создания нормированных изображений символов, чтобы облегчить процедуру сравнения изображений символов и эталонов на основе параметров. Структура данных эталонов дополнительно содержит целочисленный параметр (2506), который указывает количество индексов в структуре данных эталона, а также значения самих индексов (2508). Эти индексы связаны с различными возможными весами, которые могут быть рассчитаны при сравнении с изображения символа с эталоном. В одном варианте осуществления в структуре данных может быть столько индексов, сколько имеется возможных рассчитанных весов, при этом каждый индекс содержит целочисленный индекс и рассчитанный вес, связанный с этим индексом. Возможны и другие варианты осуществления. Вес рассчитывается, когда рассчитываются параметры для изображения символа, и значения параметров изображения символа сравниваются с эталоном, представленным структурой данных эталона. Чем больше значение веса, тем меньше изображение символа соответствует эталону. Этот вес применяется для выбора из указателей соответствующего индекса, который используется для выбора количества графем, соответствующих эталону, за которые необходимо проголосовать на стадии предварительной обработки. Каждая структура данных эталона включает в себя целочисленное значение, указывающее количество графем, соответствующих эталону (2510), а также коды всех графем из набора, соответствующих эталону (2512). Во многих вариантах осуществления эти коды графем сортируются по сходству или близости к эталону в порядке убывания сходства.
На Фиг. 25В-Н показана предварительная обработка одного изображения символа, выбранного из содержащего текст отсканированного изображения. В примере, показанном на Фиг. 25В-Н, изображение символа (2514) представляет собой иероглиф одного из азиатских языков. На Фиг. 25В также показан массив «параметры» (2404), рассмотренный выше со ссылкой на Фиг. 24, и небольшой фрагмент структуры данных кластера (2406), которая включает в себя массив «clusterParameters» (2408) и целочисленный параметр число (2410).
Как показано на Фиг. 25С, для всех параметров число, индексы которых включены в массив «clusterParameters» (2408), индекс параметра (2516) извлекается из массива «clusterParameters» (2408) и используется для доступа к экземпляру класса «parameter» (2518) в массиве «параметры» (2404). Для формирования значения параметра (2520), которое затем хранится в локальной переменной (2522), вызывается метод «parameterize» экземпляра класса «parameter» (2518). На Фиг. 25С показан расчет значения первого параметра для изображения символа. На Фиг. 25D показан расчет значения второго параметра для изображения символа. Когда все экземпляры число класса «parameter» задействованы для формирования значений параметров число для изображения символа, формируется список или массив значений параметров изображения символа (2524), как показано на Фиг. 25Е.
Затем, как показано на Фиг. 25F, из предварительно рассчитанного значения параметра для эталона, представленного структурой данных эталона, вычитается соответствующий параметр для изображения символа с целью получения ряда рассчитанных значений, по одному для каждого параметра. Например, как показано на Фиг. 25F, из первого значения параметра (2526), хранящегося в структуре данных эталона (2502), вычитается первое значение параметра (2522), рассчитанное для изображения символа, с целью получения промежуточного значения (2528). Аналогичным образом из остальных предварительно определенных значений параметров для эталона (2530)-(2533) вычитаются остальные значения параметров для изображения символа (2534)-(2538) для получения дополнительных промежуточных расчетных значений (2540)-(2544). Абсолютные величины этих промежуточных значений (2528) и (2540)-(2544) суммируются (2546) для получения веса (2548), который численно представляет основанное на параметрах сравнение изображения символа и эталона, представленного структурой данных эталона (2502). И в этом случае, чем больше значение рассчитанного веса, тем меньше изображение символа похоже на эталон, поскольку вес представляет собой накопленную разность между значениями параметров для изображения символа и эталона.
Как показано на Фиг. 25G, когда рассчитанный вес (2548) превышает вес отсечки «отсечка» (2412) для кластера, предварительная обработка изображения символа в отношении рассматриваемого эталона, представленного структурой данных эталона (2502), прекращается значением (2550). В противном случае на этапе предварительной обработки изображения символа производится голосование за одну или более графем, соответствующих эталону, представленному структурой данных эталона (2552).
На Фиг. 25Н показан случай, когда рассчитанный вес, представляющий собой сравнение изображения символа с эталоном, представленным структурой данных эталона, меньше или равен весу отсечки для данного кластера. В этом случае для выбора индекса (2554) из набора индексов (2508) используется рассчитанный вес (2548). Как описывалось выше, каждый из индексов (2508) может содержать индекс и связанный с ним вес, что позволяет выбрать один конкретный индекс (2554), который будет выбран с помощью вычисленного веса (2548), из индекса, который является индексом извлекаемых кодов графем. Этот извлеченный индекс (2556) указывает на конкретный код графемы (2558) в наборе кодов графем (2512), хранящемся в структуре данных эталона для представления тех графем, которые соответствуют эталону. Затем для всех кодов графем, начиная с первого кода графемы (2560) и до кода графемы (2558), на который указывает извлеченный индекс (2556), увеличивается соответствующий элемент из структуры данных «голоса» (2402), как показано стрелками (такими как стрелка (2562)), исходящими из элементов, содержащих коды графем между элементами (2560) и (2558) включительно.
Таким образом, если рассчитанный вес, используемый для сравнения с изображения символа с эталоном, меньше значения отсечки, значит изображение символа достаточно похоже на эталон, чтобы по меньшей мере за некоторые из соответствующих эталону графем был отдан голос на стадии предварительной обработки. Графемы, достаточно похожие на изображение символа, выбираются на основе рассчитанного веса с использованием индекса, выбранного из индексов (2508) в соответствии с рассчитанным весом. Затем элементы структуры данных «голоса», соответствующие этим графемам, увеличиваются для отражения количества голосов, отданных этим графемам во время предварительной обработки изображения символа.
Существует множество различных альтернативных подходов к осуществлению стадии предварительной обработки и формированию описанных выше структур данных. Например, вместо использования веса отсечки для всего кластера можно использовать вес отсечки для конкретных эталонов, при этом вес отсечки может включаться в структуру данных эталона. В другом примере хранящиеся в эталоне индексы могут представлять собой экземпляры классов, содержащих списки кодов графем, а не индексы, указывающие на упорядоченный список кодов графем, как это реализуется в описываемом варианте осуществления. Также возможны и многие другие альтернативные варианты осуществления. Например, подпрограмма «vote» может принимать в качестве второго аргумента указатель на массив «params» а в цикле for, в строках 43-44, значения параметров могут вычисляться только в том случае, если они еще не были рассчитаны при обработке изображения символа для других кластеров. В других вариантах осуществления можно применять разные типы расчета веса и сравнения изображения символа с эталоном. В некоторых случаях большее значение веса может указывать на большее сходство изображения символа с эталоном в отличие от приведенного выше примера, когда увеличение значения веса означало уменьшение сходства изображения символа с эталоном. В ряде систем OCR с графемами могут связываться вещественные коэффициенты, позволяющие при голосовании использовать дробные значения и значения больше 1. В некоторых системах OCR графемы, эталоны и/или кластеры можно отсортировать на основании голосов, накопленных в течение предварительной обработки, для более эффективного последующего распознавания символов. В определенных вариантах осуществления структура данных кластера может включать в себя только количество структур данных эталона или ссылок на структуры данных эталона, при этом вес отсечки и эталоны, связанные с кластером, указываются в алгоритме управления, а не хранятся в структуре данных кластера.
На Фиг. 26 показаны отношения между символами, изображениями символов, эталонами и графемами. На Фиг. 26 первый диск (2602) представляет собой набор символов, или кодов символов, второй диск (2604) представляет собой гораздо больший набор возможных изображений символов, третий диск (2606) представляет собой набор структур данных эталона, с которым изображения эталона сравниваются при обработке изображений символов, а четвертый диск (2608) представляет собой набор графем языка, который включает в себя символы или коды символов набора (2602). Как указано точками, например, точкой (2610), представляющей члены наборов, и стрелками, такими как стрелка (1612), которые представляют собой отображения между членами одного набора и членами другого набора, как правило, существует отображение один-ко-многим символов к графемам, как правило, отображение один-ко-многим символов к изображениям символов, как правило, отображение один-ко-многим изображений символов к структурам данных эталонов, и, как правило, отображение один-ко-многим графем к эталонам. В описываемых в настоящем документе методах и системах для эффективного определения соответствия изображений символов эталонам используются леса решений, а для сопоставления эталонов и графем используется голосование на основе веса.
На Фиг. 27 показан процесс преобразования изображений символов в коды символов. Этот процесс используется системами OCR в соответствии с текущим документом для замены изображений символов на коды символов или другие типы идентификаторов символов в документах. Обычно процесс начинается с одного или более изображений документа (2702). Изображение документа обрабатывается для того, чтобы идентифицировать небольшие фрагменты изображения, каждый из которых содержит один символ языка. Показано, что первоначально обрабатываемый документ (2704), получаемый из изображения документа, содержит небольшие фрагменты изображения, такие как фрагмент изображения (2705), который содержит изображение одного символа. Разумеется, первоначально обрабатываемый документ может представлять собой массив ссылок на фрагменты изображений в изображении документа или любой из многих различных типов обрабатываемых документов. Затем первоначально обрабатываемый документ (2704) дополнительно обрабатывается для получения таблицы обработанных изображений символов (2706). В этой таблице каждая запись, или строка, например, запись (2708) содержит указание на фрагмент изображения в первоначально обрабатываемом документе, которому соответствует запись (2710), а затем массив или набор кодов графем (2712)-(2716), которые с наибольшей вероятностью соответствуют изображению символа в конкретном фрагменте изображения. Все записи оканчиваются кодом завершения «0» (2717), который показывает окончание записи. Разумеется, существует много различных возможных способов кодировки таблицы обработанных изображений символов в дополнение к подходу, использованному для получения примера таблицы обработанных изображений символов (2706), показанной на Фиг. 27. Наконец, список кодов графем, которые соответствуют конкретным изображениям символов, используется на более поздних стадиях обработки изображений символов совместно со структурами данных эталонов, которые отдали голоса за коды графем, для получения конкретного кода символа, соответствующего изображению каждого символа, для изображения каждого символа в первоначальном обрабатываемом документе (2704). Затем эти коды символов (2720) могут быть сохранены наряду с несимвольными участками изображения документа, а также подвергнуться дополнительной отдельной обработке, например, машинному переводу на другой естественный язык, или использоваться многими другими способами в зависимости от системы OCR и приложения.
Как обсуждалось выше со ссылкой на Фиг. 24 и 25А-Н, структуры данных эталона и кластера обеспечивают основу для механизма голосования, согласно которому обработка изображения символа приводит к голосованию за графемы, которые, вероятно, связаны с изображением символа, или которые соответствуют ему. Обычно описываемые в настоящее время системы OCR используют относительно большое количество структур данных кластера, каждая из которых связана с сотнями структур данных эталонов. Процесс обработки мультикластерной структуры данных описан ниже со ссылкой на Фиг. 28A-G.
На Фиг. 28А показаны данные и структуры данных, использованные в примере обработки символа с помощью мультикластерной структуры данных. Допущения для изображений, которые использовались на Фиг. 28А, также используются на последующих Фиг. 28B-G. На Фиг. 28А снова показаны многие структуры данных с Фиг. 24 и Фиг. 25A-G. Они содержат массив параметров (2802) (показанный как массив (2404) на Фиг. 24), массив голосов (2804) (показан как массив голосов (2402) на Фиг. 24), три структуры данных кластера (2806)-(2808), каждая из которых идентична структуре данных кластера (2406), показанной на Фиг. 24, и массив рассчитанных значений параметров (2810), аналогичный массиву рассчитанных значений параметров (2524) на Фиг. 25F. Следует отметить, что структурам данных при инициализации присваиваются соответствующие значения, в то время как массиву голосов присваиваются все нулевые значения. Каждая структура данных кластера, такая как структура данных кластера (2806), включает в себя массив параметров (2812), похожий на массив «clusterParameters» (2408), показанный на Фиг. 24, величину число (2814) и величину отсечки отсечка (2816), аналогичные соответственно величинам число и отсечка (2410) и (2412), показанным в кластере (2406) на Фиг. 24, и а также несколько структур данных эталона, таких как структура данных эталона (2818), идентичных структуре данных эталона (2502) на Фиг. 25А. Кроме того, на Фиг. 28А показана структура данных (2820), которая представляет собой отсканированное изображение страницы документа. Эта структура данных является двумерным массивом, каждая ячейка которого, как, например, ячейка (2822), соответствует изображению символа. Также на Фиг. 28А показана переменная (2824), содержащая обрабатываемое в настоящий момент изображение символа.
Структуры данных, показанные на Фиг. 28А, могут быть реализованы различными способами с помощью различных языков программирования и технологий хранения данных. Структуры данных могут включать в себя дополнительные данные и подструктуры данных. Например, в одном из вариантов осуществления каждая структура данных эталона в каждом кластере представляет собой ссылки из отсортированного массива ссылок структуры данных кластера. В других вариантах осуществления каждая структура данных эталона в каждом кластере связывается с числовой последовательностью, что позволяет проходить по структурам данных эталона в определенном порядке. В некоторых осуществлениях структура данных кластера может включать в себя структуры данных эталона, в то время как в других осуществлениях структура данных кластера может ссылаться на структуры данных эталона. В большинстве осуществлений структуры данных могут быть динамически расширены или сжаты, чтобы соответствовать изменениям способов OCR, в которых они используются. Таким образом, несмотря на то что для описания структуры данных голосов применяется термин «массив», данная структура может быть реализована с использованием структур данных, отличных от простых массивов, но позволяющих при этом индексировать элементы как в массивах.
Текстовая структура данных (2820) представляет собой страницу документа, которую необходимо обработать способом мультикластерной обработки документа с применением OCR для преобразования исходного отсканированного документа, содержащего изображения символов, в эквивалентный электронный документ, содержащий коды символов. Термины «документ», «страница» и «изображение символа» могут иметь различные значения в зависимости от контекста. В данном примере документ состоит из нескольких страниц, и каждая страница включает в себя множество изображений символов. Разумеется, тот же самый или схожий способ мультикластерной обработки документов с применением OCR может использоваться для множества различных типов документов вне зависимости от того, содержат ли они страницы с одним или более изображениями символов или нет.
На первой стадии, показанной на Фиг. 28В, переменная текущего изображения символа (2826) считывает в себя или ссылается на первое изображение символа (2824), как это показано фигурной стрелкой (2827). Затем, как показано на Фиг. 28С, каждая вычисляющая параметры функция или подпрограмма из массива параметров (2802), применяется к текущему изображению символа из переменной (2824) для формирования соответствующих значений параметров, которые затем записываются в массив рассчитанных значений параметров (2810), как показывают стрелки (2828)-(2831) и точки (2832)-(2833). Таким образом, в одном из осуществлений массив рассчитанных значений параметров (2810) включает в себя числовые значения параметров, соответствующие каждому из параметров массива (2802), представленных функциями или ссылками на них, и рассчитанные для текущего изображения символа. Вычисление значений параметров ранее описывалось со ссылкой на Фиг. 19C-D.
Затем, как показано на Фиг. 28D, в первой структуре данных кластера (2806) выбирается первая структура данных эталона (2834). Значения параметров, связанных с первой структурой данных эталона, используются вместе с соответствующими значениями параметров из массива рассчитанных значений (2810) для расчета веса W (2835), как было описано выше со ссылкой на Фиг. 25F. Выбор первой структуры данных эталона иллюстрируется фигурной стрелкой (2837). Обратите внимание, что массив параметров структуры данных кластера ((2812) на Фиг. 28А) используется для индексации массива рассчитанных значений параметров. Как было описано выше со ссылкой на Фиг. 25G, затем рассчитанный вес сравнивается с весом отсечки ((2816) на Фиг. 28А) (2836). Это позволит определить, может ли структура данных эталона (2834) из первой структуры данных кластера (2806) проголосовать за графемы, как было описано выше со ссылкой на Фиг. 25Н. В рассматриваемом примере, как показано на Фиг. 28Е, рассчитанный вес (2835) меньше веса отсечки, в результате чего происходит накопление голосов, формируемых первой структурой данных эталона (2834) из первой структуры данных кластера (2806), в массиве голосов (2824). Как было описано выше со ссылкой на Фиг. 19Н, рассчитанный вес (2835) используется для выбора индекса из набора индексов (2838) в первой структуре данных эталона (2834), а содержимое выбранного элемента становится указателем (2839) на некоторый код графемы из первой структуры данных эталона (2840). Голоса формируются для всех графем, соответствующих кодам графем из сегмента кодов графем первой структуры данных эталона, начиная с первого кода и заканчивая кодом графемы, на которую указывает индекс, выбранный из сегмента индексов структуры данных эталона. На Фиг. 28Е голоса, поданные первой структурой данных эталона (2834) из первой структуры данных кластера (2806), показаны фигурными стрелками (2842)-(2846). Пустые значения в массиве голосов ((2804) на Фиг. 28А) представляют собой нулевые значения (0). Начальное голосование для первой структуры данных эталона (2834) из первой структуры данных кластера (2806) увеличивает значения накопленных голосов (2847)-(2851) с 0 до 1 для тех графем в массиве голосов, для которых выбраны соответствующие коды из первой структуры данных эталона. В альтернативных вариантах осуществления при голосовании к значениям элементов массива голосов могут прибавляться числа, отличные от 1.
Процесс, описанный со ссылкой на Фиг. 28С-Е, повторяется для каждой структуры данных эталона, принадлежащей каждой структуре данных кластера для формирования законченного голоса за графему, сохраняемого в массиве голосов (2804). На Фиг. 28F показано окончательное голосование после полного прохождения структуры данных эталона для каждой структуры данных кластера, показанное змеевидной стрелкой (2865), продолжающейся из фигурной стрелки (2837), показывающей выбор первой структуры данных эталона в первом кластере. Так выглядит обработка первого изображения символа, выбранного из текстовой страницы (2820). Далее, как показано на Фиг. 28G, голоса, накопленные в массиве голосов для первого изображения символа, выбранного из текстовой страницы, используются для подготовки отсортированного списка кодов графем, которые чаще всего соответствовали изображению символа в процессе обработки, описанной выше со ссылкой на Фиг 28B-F согласно накопленным голосам для кодов графем в массиве голосов. На Фиг. 28G, массив голосов (2804) показан в верхней части чертежа. Каждая ячейка в массиве голосов содержит количество голосов; индексами ячеек являются коды графем. Голоса и индексы кодов графем затем сортируются в порядке убывания количества голосов, формируя, таким образом, отсортированный массив (2867), в котором каждая ячейка содержит код графемы, а индексы слева направо монотонно возрастают, упорядочивая коды графем по количеству голосов, которые они получили в процессе обработки, описанной на Фиг. 28B-F. Например, наибольшее число голосов, равное 16, получил код графемы «9» (2866), а значит, код графемы «9» будет стоять на первой позиции (2868) в отсортированном массиве кодов графем (2867). Затем отсортированный массив (2867) урезается, формируя усеченный отсортированный массив кодов графем (2869). Усеченный отсортированный массив кодов графем включает в себя отсортированный список кодов графем, которые получили голоса в процессе обработки, описанной выше со ссылкой на Фиг. 28B-F. В процессе, описанном на Фиг. 28B-F, голоса получили только 14 кодов графем, а значит, усеченный отсортированный массив кодов графем (2869) содержит только 14 элементов. Это первые 14 элементов в отсортированном массиве кодов графем (2867). Остальные элементы отсортированного массива кодов графем (2867), следующие за четырнадцатым элементом с индексом 13, содержат коды графем, для которых голоса не были получены. Далее, как показывает фигурная стрелка (2870), усеченный массив кодов графем включается в первый элемент (2871) таблицы обработанных изображений символа (2872). Каждый элемент таблицы обработанных изображений символа включает в себя поле (представлено как первый столбец (2873)), указывающее на число или порядок символа внутри текстовой структуры данных ((2820) на Фиг. 28А). поле с количеством кодов графем, получивших голоса в процессе обработки символа (вторая колонка (2874) в таблице обработанных изображений символа), и отсортированный усеченный массив кодов графем (третья колонка (2875) таблицы обработанных изображений символа (2872)).
В некоторых вариантах осуществления вместо использования таблицы обработанных изображений символов, отсортированный усеченный массив кодов графем немедленно используется в дополнительном алгоритме обнаружения символов, который формирует соответствующий код символа для изображения символа. Этот код символа затем может быть немедленно помещен в обработанную страницу, соответствующую странице, содержащей изображения символов, которые были обработаны вышеописанным способом со ссылкой на Фиг 28A-J. Однако в настоящем осуществлении отсортированные усеченные массивы кодов графем для изображений символов накапливаются в таблице обрабатываемых изображений символа для каждой страницы документа. Отсортированные усеченные массивы кодов графем затем используются совместно со структурами данных эталона на втором этапе для преобразования изображений символов со страницы документа в символы, помещаемые затем на обработанную страницу документа. В любом случае отсортированный усеченный массив кодов графем представляет собой результат начальной мультикластерной обработки, которая определяет набор кодов графем, наиболее вероятно связанных с изображением символа внутри изображения страницы документа. В настоящем варианте осуществления все коды графем, заработавших голоса, включены в отсортированные усеченные массивы кодов графем. В альтернативных вариантах осуществления в отсортированные усеченные массивы кодов графем включаются только те коды графем, число голосов которых превышает заданный порог.
Как только завершается обработка первого изображения символа, извлеченного из страницы документа, и в таблице обработанных изображений символов создается соответствующая запись, второе изображение символа выбирается из текстовой структуры данных ((2820) на Фиг. 28А) и помещается в переменную (2824). Затем рассчитываются значения параметров для следующего символа и сохраняются в массиве рассчитанных значений параметров (2810). Затем обрабатывается второе изображение символа с использованием способа, описанного выше со ссылкой на Фиг. 28C-F. Таким образом, формируется новый набор накопленных голосов в массиве голосов (2804) для второго изображения символа. Накопленные голоса для второго изображения символа (2804) сортируются по количеству полученных голосов с целью получения отсортированного массива графем, который затем урезается для получения усеченного отсортированного массива графем. Этот усеченный массив графем включается как второй элемент таблицы обработанных изображений символов (2872). Аналогичная обработка осуществляется для каждого последующего символа изображения в структуре данных текста ((2820) на Фиг. 28А). В результате обработки изображений символа текстового документа, использующей кластеры, формируется таблица обработанных изображений символа (2872), в которой имеется запись для каждого изображения символа обрабатываемого документа. Каждый элемент таблицы обработанных изображений символа представляет собой начальный набор графем, потенциально соответствующих изображению символа. Набор потенциально соответствующих графем помещается в отсортированный усеченный массив кодов графем, отсортированный в порядке убывания накопленных голосов таким образом, что коды графем, набравших наибольшее количество голосов, располагаются первыми в отсортированном усеченном массиве кодов графем. Набор потенциально соответствующих кодов графем, представленный в виде отсортированного усеченного массива кодов графем, наряду со структурами данных эталона, голосующими за входящие в массив графемы, может в дальнейшем использоваться в дополнительном алгоритме распознавания символов для определения наилучших кодов символов для того изображения символа, для которого был сформирован отсортированный усеченный массив кодов графем в процессе обработки, описанной выше со ссылкой на Фиг. 28B-F.
При подходе к обработке символов с мультикластерной структурой данных, описанной выше со ссылкой на Фиг. 28A-G, графемы-кандидаты, выбранные для каждого обработанного символа изображения, отражают выводы, которые можно сделать из огромной базы данных накопленной информации по совпадениям с эталонами для набора символов естественного языка, содержащимся в структурах данных эталонов и структурах данных кластеров. Тем не менее, когда естественный язык описывается многими десятками или сотнями структур данных кластеров, каждая из которых содержит многие сотни структур данных эталонов, накладные расходы для обработки изображения символа очевидно являются высокими. Несмотря на то, что современные компьютерные системы имеют быстрые процессоры, и в машине часто имеется по меньшей мере несколько процессорных ядер, вычислительные накладные расходы методологии обработки изображений символов, описанной выше со ссылками на Фиг. 24-28G, могут оказаться достаточно большим, чтобы многие задачи оптического распознавания символов стали практически невозможными или нецелесообразными. Настоящий документ вводит выбор структур данных эталона изображений символов на основе леса решений для того, чтобы значительно повысить вычислительную эффективность общего подхода на основе мультикластерной структуры данных к оптическому распознаванию символов.
На Фиг. 29A-D показано использование леса решений для выявления подходящих структур данных для обработки входных изображений символов. На Фиг. 29А входное изображение символа (2902) параметризуется путем вычисления значений числовых параметров для каждого из набора различных параметров, которые затем сохраняются в массив числовых значений параметров (2904). Эти сохраненные параметры, или поднаборы хранимых параметров, затем используются для обхода многочисленных деревьев решений в лесе решений (2906), каждое из которых дает одну или более подходящих структур данных эталона (2908)-(2912), соответствующую входному изображению символа (2902). Во многих случаях каждое дерево принятия решений дает одну подходящую структуру данных эталона. В альтернативных вариантах реализации дерево решений может выбирать несколько подходящих структур данных эталона для входного изображения символа. Деревья решений похожи на схемы принятия решений, описанные выше со ссылкой на Фиг. 14С, 15С, 16С и 17С. Тем не менее, в отличие от описанных ранее деревьев решений, деревья решений в лесу решений (2906) выбирают не коды символов, а идентификаторы, которые указывают на структуры данных эталона, как описано более подробно ниже.
Таким образом, лес решений (2906) используется для выбора набора подходящих структур данных эталонов, каждая из которых независима от других, используемых в контексте одной или более структур данных кластера, чтобы проголосовать за коды графем, которые вероятно будут соответствовать входному изображению символа. Используя лес решений (2906), длительный и вычислительно неэффективный процесс, описанный выше со ссылкой на Фиг. 28A-G, в котором каждая структура данных эталона в каждой структуре данных кластера голосует за коды графем, преобразуется так, чтобы за введенное изображение символа голосовали только подходящие для этого структуры данных эталона, определенные лесом решений. Лес решений анализирует значения параметров, формируемые из входных символов изображении для выявления набора подходящих структур данных, которые, скорее всего, дадут веса меньше, чем значение отсечки в структурах данных кластера, которые включают подходящие структуры данных эталона, тем самым устраняя необходимость вычислять веса выше значения отсечки, которые не приведут к голосованию за коды графем. Кроме того, подходящие структуры данных эталона, выявленные лесом решений, имеют наибольшую вероятность подачи значимых голосов за коды графемы в отношении изображения входного символа.
На Фиг. 29В показаны отношения между деревьями решений в лесу решений ((2906) на Фиг. 29А), структурами данных эталона и структурами данных кластера. Как показано на Фиг. 29В, лес решений ((2906) на Фиг. 29А) состоит из нескольких отдельных деревьев решений (2914)-(2917). Конечные узлы деревьев принятия решений показаны на Фиг. 29В в горизонтальном уровне (2920), причем каждый из них ссылается по меньшей мере на одну структуру данных эталона. На Фиг. 29В структуры данных эталона показаны в виде широкого среднего слоя (2922) с похожими на колонку объектами, такими как похожий на колонку объект (2924), представляющими отдельные структуры данных эталона. Одна или более структур данных кластера может включать или ссылаться на структуру данных эталона. На Фиг. 29В структуры данных кластера показаны на самом нижнем уровне (2926). Например, структура данных эталона (2928) включена в три различные структуры данных кластера (или связана с ними), включая структуры данных кластера (2930) и (2932), обозначенные означающими ссылки стрелками (2934)-(2936). Следует отметить со ссылкой на Фиг 29В, что дерево принятия решений может включать конечные узлы, которые ссылаются на структуры данных эталона, связанные с несколькими структурами данных кластера, поскольку рассматриваемая структура данных эталона может быть связана с несколькими структурами данных кластера. В некоторых вариантах осуществления конечный узел дерева принятия решений может ссылаться на несколько структур данных эталона, а не на одну структуру данных эталона, как на Фиг. 29В.
На Фиг. 29С показан процесс голосования за коды графем подходящими структурами данных эталона, выявленными лесом решений ((2906) на Фиг. 29А). Как показано на Фиг. 29С, подходящие структуры данных эталона (2908)-(2912), выявленные лесом решений, могут быть связаны с несколькими структурами данных кластера. Например, структура данных эталона (2908) связана со структурой данных кластера (2940) и со структурой данных кластера (2942). Структура данных эталона (2908) в контексте структуры данных кластера (2940) подает три голоса за коды графемы, показанные стрелками (2944)-(2946). Структура данных эталона (2908) в структуре данных кластера (2942) подает три голоса за код графемы, что показано стрелками (2948)-(2950). Разумеется, конкретная структура данных эталона может подавать такое количество голосов в одной структуре данных кластера, которое будет отличаться от количества голосов, поданных той же структурой данных эталонов в другой структуре данных кластера. Аналогичным образом, структура данных эталона в контексте одной структуры данных кластера может голосовать за другие графемы, не за те, за которые она же проголосовала в структуре данных эталона в контексте другой структуры данных кластера. Таким образом, вместо того, чтобы предоставлять возможность каждой структуре данных эталона в каждой структуре данных кластера самостоятельно голосовать за графемы, в основанном на лесе решений способе лес решений используется для того, чтобы выбрать набор подходящих структур данных эталонов (2908)-(2912), каждая из которых голосует в контексте структур данных кластера, с которыми эта структура данных эталона связана или в которой структура данных эталона находится.
На Фиг. 29D показан один вариант осуществления основанного на лесе решений способа обработки изображения символа, который обсуждался выше со ссылкой на Фиг. 29А-С. На Фиг. 29D в верхней части рисунка показано одно дерево решений (2960). Каждый конечный узел, например, конечный узел (2962) содержит по меньшей мере один идентификатор эталона (2964). В некоторых вариантах осуществления каждый конечный узел содержит только один идентификатор эталона, в то время как в альтернативных вариантах осуществления конечный узел дерева принятия решений может содержать несколько идентификаторов, указывающих на разные эталоны. Идентификатор эталона используется в качестве индекса (что показано стрелкой (2966)) на индекс эталона (2968). Индекс эталона представляет собой массив указателей на списки идентификаторов кластера. Например, идентификатор эталона, который индексирует первый элемент в индексе эталона (2970), через индекс эталона ссылается на список из трех идентификаторов кластера (2972)-(2974). Эти идентификаторы кластера определяют кластеры, связанные со структурами данных эталона, выявленные идентификатором эталона (2964) или содержащие эти структуры данных. В случае конечного узла (2962) дерева принятия решений (2960) один идентификатор эталона (2964), содержащийся внутри конечного узла, ссылается на список идентификаторов двух кластеров (2976) и (2978). Первый идентификатор кластера используется в качестве указателя на индекс кластера (2982), что показано стрелкой (2980). Индексированная запись индекса кластера содержит указатель или ссылку на структуру данных кластера (2984). Структура данных кластера содержит локальный индекс структуры данных эталона (2986). Идентификатор эталона (2964) используется для индексации записи (2988) в локальном индексе структуры данных эталона (2986), который содержит ссылку на экземпляр структуры данных эталона (2990), соответствующий идентификатору эталона (2964), который содержится в структуре данных кластера (2984) или связан с ней. Могут быть использованы много дополнительных типов структур данных и методов доступа для выявления подходящих структур данных эталона, содержащихся в структурах данных кластера, связанных с каждым конечным узлом каждого дерева принятия решений. В некоторых случаях рассмотренная структура данных эталона может быть представлена несколькими записями в индексе эталона (2968) и, следовательно, она может быть связана с различными списками, содержащими структуры данных кластера, при этом одно дерево принятия решений может определить голосование структурой данных эталона в контексте структур данных кластера, отличающихся от структур, указанных другим деревом принятия решений.
На Фиг. 30A-D с помощью блок-схем показан один из вариантов осуществления способа обработки документа на основе мультикластерной структуры данных, в котором использует лес решений для выбора подходящих структур данных эталона для каждого изображения символа. На Фиг. 30А показан самый верхний уровень способа обработки документов с применением OCR. На этапе (3002) происходит получение документа и инициализация структуры данных, соответствующей обработанному документу (PD), которая будет хранить коды символов, сформированных в процессе обработки документа, для соответствующих изображений символов из полученного документа. Затем на этапе (3004) инициализируются структуры данных, описанные выше со ссылкой на Фиг. 24-25А для подготовки к обработке документа. Затем в цикле for на этапах (3006)-(3012) происходит обработка каждой страницы документа для замены в обработанном документе PD изображений символов из полученного документа на коды символов или другие вычисленные представления символов. На первом этапе внешнего цикла for (3006)-(3012) очищается и повторно инициализируется таблица обработанных изображений символов, описанная выше со ссылкой на Фиг. 27 и 28G. Затем во внутреннем цикле for на этапах (3008)-(3011) каждый символ текущей страницы обрабатывается путем вызова подпрограммы «process symbol image» («обработка изображения символа») (3009). По завершению вложенных циклов for на этапах (3006)-(3012) на этапе (3014) освобождаются память, занятая структурами данных, использованными при обработке полученного документа с применением OCR, и возвращается обработанный документ PD.
На Фиг. 30В показана подпрограмма «инициализация структур данных» («initialized data structures))), вызываемая на этапе (3004) на Фиг. 30А. На этапе (3015) происходит выделение памяти для леса решений и его инициализация. В общем случае лес решений основан на независимом анализе больших объемов текстовой информации на том естественном языке, для которого строится дерево решений. На этапе (3016) происходит выделение памяти для массива параметров и его инициализация ((2002) на Фиг. 20А). На этапе (3018) происходит выделение памяти для массива голосов ((2004) на Фиг. 20А). На этапе (3020) происходит выделение памяти и инициализация структур данных кластеров ((2006)-(2008) на Фиг. 20А) и структур данных, которые содержат в себе или на которые ссылаются структуры данных кластеров, включая массивы локальных параметров ((2012) на Фиг. 20А) и структуры данных эталонов ((2018) на Фиг. 20А). Как уже упоминалось выше, каждая структура данных кластера может включать в себя набор ссылок на параметры, описанные в глобальном массиве параметров ((2002) на Фиг. 20А), а также структуры данных эталонов и вес отсечки, отличные от других структур данных кластеров. Каждая структура данных кластера специализируется на распознавании подмножества или семейства символов конкретного языка или набора родственных языков. Наконец, на этапе (3022) происходит выделение памяти для таблицы обработанных изображений символа ((2706) на Фиг. 27). Кроме того, происходит статическое либо динамическое выделение памяти и для других различных переменных и массивов и их инициализация.
На Фиг. 30С показана блок-схема подпрограммы «обработка изображения символа» («process symbol image»), вызываемой на этапе (3009) на Фиг. 30А. На этапе (3024) подпрограмма вычисляет значения для всех параметров, представленных функциями, рассчитывающими значения параметров, или ссылками на такие функции в массиве параметров (2008). На этапе (3026) рассчитанные параметры или поднаборы рассчитанных параметров вводятся в деревья решений, которые совместно составляют лес решений ((2906) на Фиг. 29А). Затем во вложенных циклах for на этапах (3027)-(3037) подпрограмма «обработка изображения символа» обрабатывает изображение символа, как было описано выше со ссылкой на Фиг 29A-D. Внешний цикл for на этапах (3027)-(3037) выполняется для каждой структуры данных эталона, возвращенной лесом решений. В первом внутреннем цикле for на этапах (3028)-(3036) перебираются все структуры данных эталона внутри текущей структуры данных кластера. На этапе (3029) с помощью текущих значений переменных цикла выявляется следующая структура данных эталона в структуре данных кластера или связанная с ней структура. На этапе (3030) для текущей структуры данных эталона рассчитывается вес W на основе значений параметров эталона, содержащихся в структуре данных эталона, и соответствующих значений параметров, рассчитанных для текущего изображения символа, как было описано выше со ссылкой на Фиг. 28D. Если рассчитанный вес структуры данных кластера больше веса отсечки, как определено на этапе (3031), то обработка текущей структуры данных эталона прекращается и осуществляется переход к этапу (3036), который описан ниже. В противном случае на этапе (3032) рассчитанный вес используется для выбора индекса из сегмента индексов структуры данных эталона, указывающего на код графемы в структуре данных эталона. Затем в самом внутреннем цикле for на этапах (3033)-(3035) происходит добавление голосов к ячейкам массива голосов, на которые указывает каждый код графемы в структуре данных эталона, начиная с первого и заканчивая кодом графемы, индекс которой был выбран на этапе (3033). В описываемом варианте осуществления каждый голос добавляет 1 к числу накопленных голосов за графему. В альтернативных вариантах осуществления голоса могут представлять собой вещественные числа из некоторого диапазона, например, [0,0; 1,0]. В альтернативных вариантах осуществления целочисленные значения голосов из некоторого диапазона целых чисел могут использоваться в качестве значения голосования, характеризующего степень сходства графемы и эталона, представляющего структуру данных эталона. На этапе (3040), как было описано выше со ссылкой на Фиг 28G, коды графем, набравших голоса в процессе обработки текущего изображения символа, сортируются, формируя отсортированный усеченный массив кодов графем ((2869) на Фиг. 28G). Затем на этапе (3042) отсортированный усеченный массив кодов графем добавляется в соответствующий текущему изображению символа элемент таблицы обработанных изображений символа ((2072) на Фиг. 28G).
На Фиг. 30D в виде блок-схемы показана подпрограмма «обработка страницы» («process page»), вызываемая на этапе (3011) на Фиг. 30А. На этапе (3044) происходит инициализация новой структуры данных обработанной страницы, которая будет хранить коды символов или их другие представления для дальнейшей передачи в обработанный документ PD. Затем в цикле for на этапах (3046)-(3050) обрабатывается каждое изображение символа внутри изображения страницы содержащего текст документа, полученного на этапе (3002) на Фиг. 30А. На этапе (3047) осуществляется доступ к записи рассматриваемого в настоящее время изображению символа, хранящемуся в таблице обработанных изображений символов, которое используется на этапе (3048) наряду со структурами данных эталонов, которые подали голоса за графемы в записи для рассматриваемого в настоящее время изображения символа, хранящегося в таблице обрабатываемых символов изображения, чтобы определить символ, который наилучшим образом соответствует изображению символа, с использованием графем, коды которых были связаны с изображением символа во время обработки изображения символа с помощью подпрограммы «обработка символа изображения», показанной на Фиг. 30С. Существует множество способов определения кода символа, наиболее соответствующего изображению символа. На этапе (3049) символ или представляющий его код помещается на место в структуре данных обработанной страницы, соответствующее расположению изображения символа на обрабатываемой в настоящий момент странице полученного документа, содержащего текст. После того как были обработаны все изображения символа, содержимое структуры данных обработанной страницы помещается в обработанный документ PD на этапе (3052), после чего память, занятая структурой данных обработанной страницы, освобождается на стадии (3054).
Хотя настоящее изобретение описывается на примере конкретных вариантов осуществления, предполагается, что оно не будет ограничено только этими вариантами осуществления. Специалистам в данной области будут очевидны возможные модификации сущности настоящего изобретения. Например, любой из множества возможных вариантов осуществления структур данных и методов, используемых для предварительной обработки в соответствии с обобщенным третьим вариантом осуществления системы OCR, описанным выше, может быть достигнута путем изменения любого из различных параметров проектирования и осуществлении, среди которых: структуры данных, структуры управления, модульное исполнение, язык программирования, используемая операционная система и аппаратное обеспечение, а также многие другие подобные параметры проектирования и осуществлении.
Следует понимать, что приведенное выше описание раскрытых вариантов осуществления предоставлено для того, чтобы дать возможность любому специалисту в данной области техники создать или использовать настоящее изобретение. Специалистам в данной области будут очевидны возможные модификации представленных вариантов осуществления, при этом общие принципы, представленные здесь, могут применяться к другим вариантам осуществления без отступления от сущности или объема описания. Таким образом, настоящее описание не ограничено представленными здесь вариантами осуществления, оно соответствует широкому кругу задач, связанных с принципами и новыми отличительными признаками, раскрытыми в настоящем документе.
Изобретение относится к оптическому распознаванию символов. Техническим результатом является оптимизация оптического распознавания символов за счет использования леса решений. Предложенная система включает в себя команды в машинном коде при их исполнении процессором, управляющие системой оптического распознавания символов для обработки содержащего текст отсканированного изображения документа путем выполнения идентификации изображений символов в содержащем текст отсканированном изображении документа. Причем идентификация выполняется для каждой страницы документа и для каждого изображения символа на странице. Выполняют идентификацию набора подходящих структур данных эталона для изображения символа с использованием леса решений. Используют подходящие структуры данных эталона для определения набора подходящих графем и используют идентифицированный набор подходящих графем для выбора кода символа, который соответствует изображению символа. Подготавливают обработанный документ, содержащий коды символов, которые соответствуют изображениям символов из отсканированного изображения документа, и сохраняют обработанный документ в одном или более запоминающих устройств и модулей памяти. 3 н. и 17 з.п. ф-лы, 66 ил.
1. Система оптического распознавания символов, содержащая:
один или более процессоров;
один или более модулей памяти;
одно или более запоминающих устройств; и
команды в машинном коде, хранящиеся в одном или более из одного или более запоминающих устройств при их исполнении одним или более из одного или более процессоров, управляют системой оптического распознавания символов для обработки содержащего текст отсканированного изображения документа путем выполнения:
идентификации изображений символов в содержащем текст отсканированном изображении документа;
для каждой страницы документа,
для каждого изображения символа на странице,
идентификации набора подходящих структур данных эталона для изображения символа с использованием леса решений,
использования подходящих структур данных эталона для определения набора подходящих графем, и
использования идентифицированного набора подходящих графем для выбора кода символа, который соответствует изображению символа; и
подготовки обработанного документа, содержащего коды символов, которые соответствуют изображениям символов из отсканированного изображения документа, и сохранения обработанного документа в одном или более из одного или более запоминающих устройств и модулей памяти.
2. Система оптического распознавания символов по п. 1, отличающаяся использованием подходящих структур данных эталона для определения набора подходящих графем, дополнительно содержащая:
оценку каждой возможно подходящей структуры данных эталона в контексте одной или более структур данных кластера на способность проголосовать за графемы;
голосование отобранными подходящими структурами данных эталона за графемы для одной или более графем;
выявление подходящих графем для распознавания изображения символа как тех графем, которые получают голоса; и
сортировку выявленных графем в усеченном отсортированном массиве графем, который представляет набор подходящих графем.
3. Система оптического распознавания символов по п. 2, отличающаяся тем, что усеченный массив отсортированных графем содержит определенные графемы, имеющие количество голосов, превышающие общий порог.
4. Система оптического распознавания символов по п. 2, дополнительно содержащая набор структур данных, хранящихся в одной или более из одного или нескольких устройств памяти, причем набор структур данных включает:
лес решений;
структуру данных голосов, в которой хранятся накопленные результаты голосования, причем каждый результат связан с кодом графемы, а общее количество результатов в структуре данных голосов соответствует количеству подходящих графем;
структуры данных эталонов, каждая из которых представляет собой эталон символа и каждая из которых содержит упорядоченный набор значений параметров, упорядоченный набор индексов и упорядоченный набор кодов графем; и
две или более структуры данных кластера, причем каждая структура данных кластера включает упорядоченный набор ссылок на параметры и одну из нескольких структур данных эталона или нескольких ссылок на структуры данных эталона.
5. Система оптического распознавания символов по п. 4, дополнительно содержащая упорядоченный набор функций, которые формируют значения параметров из изображений символов.
6. Система оптического распознавания символов по п. 5, отличающаяся тем, что идентификация подходящих графем для распознавания изображения символа как графем, получающих голоса, дополнительно содержит:
инициализацию структуры данных голосов; и
добавление значения голоса к элементу структуры данных голосов, соответствующему графеме, за которую голосует структура данных эталона.
7. Система оптического распознавания символов по п. 4, отличающаяся тем, что определение с помощью леса решений кандидата на набор структур данных эталона для изображения символа дополнительно содержит:
расчет набора значений параметров для изображения символа;
ввод набора значений параметров или подмножества множества значений параметров в каждое дерево решений в лесе решений; и
выявление структур данных эталона, каждая из которых определяется конечным узлом каждого дерева принятия решений, как набора подходящих структур данных эталона.
8. Система оптического распознавания символов по п. 4, в которой оценка каждого кандидата из числа структур данных эталона в контексте одной или более структур данных кластера на способность проголосовать за данную графему дополнительно содержит:
оценку значений параметров из множества значений параметров в каждой определенной структуре данных эталона в отношении значений параметров в связанном с кластером упорядоченном наборе значений параметров для получения значения веса путем суммирования абсолютных значений разности между каждым значением параметра в наборе значений параметров в структуре данных эталона и соответствующим значением параметра в связанном с кластером упорядоченном наборе значений параметров; и
если значение веса меньше значения отсечки, решение о том, что структура данных эталона способна проголосовать за данную графему.
9. Система оптического распознавания символов по п. 8, отличающаяся тем, что голосование с помощью подходящих структур данных эталона, которые были оценены как имеющие возможность проголосовать за графемы, за одну или более графем дополнительно содержит:
использование полученного значения веса для выбора индекса из упорядоченного набора индексов в структуре данных эталона;
использование выбранного индекса для выбора кода графемы из упорядоченного набора кодов графем в структуре данных эталонов; и
для каждого кода графемы в упорядоченном множестве кодов графем в структуре данных эталона, начиная с первого кода графемы и заканчивая выбранным кодом графемы,
индексацию структуры данных голосов в соответствии с кодами графем для накопления общего итога голосования для графему, соответствующего коду графемы, и добавления значения к общему итогу голосования за графемы.
10. Способ, осуществляемый в системе оптического распознавания символов, имеющей один или более процессоров, одно или несколько устройств памяти, одно или более запоминающих устройств и команды в машинном коде, хранящиеся в одном или более из этих устройств одного или более запоминающих устройств, которые выполняются в одном или более из одного или более процессоров, причем этот способ включает:
идентификацию изображений символов в содержащем текст отсканированном изображении документа;
для каждой страницы документа,
для каждого изображения символа на странице,
идентификацию набора подходящих структур данных эталона для изображения символа, используя лес решений,
использование подходящих структур данных эталона для определения набора подходящих графем, и
использование идентифицированного набора подходящих графем для выбора кода символа, который соответствует изображению символа; и
подготовку обработанного документа, содержащего коды символов, которые соответствуют изображениям символов из отсканированного изображения документа, и сохранение обработанного документа в одном или более из одного или более запоминающих устройств и модулей памяти.
11. Способ по п. 10, отличающийся тем, что использование подходящих структур данных эталона для выявления набора подходящих графем дополнительно содержит:
оценку каждой возможно подходящей структуры данных эталона в контексте одной или более структур данных кластера на способность проголосовать за графемы;
голосование отобранными подходящими структурами данных эталона за графемы для одной или более графем;
выявление подходящих графем для распознавания изображения символа как тех графем, которые получают голоса; и
сортировку выявленных графем в усеченном отсортированном массиве графем, который представляет набор подходящих графем.
12. Способ по п. 11, отличающийся тем, что усеченный отсортированный массив графем содержит выявленные графемы, имеющие число голосов больше общего порога голосов.
13. Способ по п. 11, дополнительно содержащий набор структур данных, хранящихся в одном или более из одного или более устройств памяти, причем этот набор структур данных включает:
лес решений;
структуру данных голосов, в которой хранятся накопленные результаты голосования, причем каждый результат связан с кодом графемы, а общее число результатов в структуре данных голосов соответствует количеству кодов графем;
структуры данных эталонов, каждая из которых представляет собой эталон символа и каждая из которых содержит упорядоченный набор значений параметров, упорядоченный набор индексов и упорядоченный набор кодов графем; и
две или более структуры данных кластера, причем каждая структура данных кластера включает упорядоченный набор ссылок на параметры и одну из нескольких структур данных эталона или нескольких ссылок на структуры данных эталона.
14. Способ по п. 13, дополнительно содержащий упорядоченный набор функций, которые формируют значения параметров из изображений символов.
15. Способ по п. 14, отличающийся тем, что определение подходящих графем для распознавания изображения символа как тех графем, которые получают голоса, дополнительно содержит:
инициализацию структуры данных голосов; и
добавление значения голоса к элементу структуры данных голосов, соответствующему графеме, за которую голосует структура данных эталона.
16. Способ по п. 14, отличающийся тем, что определение с использованием леса решений набора подходящих структур данных эталона для изображения символа дополнительно содержит:
расчет набора значений параметров для изображения символа;
ввод набора значений параметров или подмножества множества значений параметров в каждое дерево решений в лесе решений; и
выявление структур данных эталона, каждая из которых определяется конечным узлом каждого дерева принятия решений, как набора подходящих структур данных эталона.
17. Способ по п. 14, отличающийся тем, что оценка каждой возможно подходящей структуры данных эталона в контексте одной или более структур данных кластера на способность проголосовать за графемы дополнительно содержит:
оценку значений параметров из множества значений параметров в каждой определенной структуре данных эталона в отношении значений параметров в связанном с кластером упорядоченном наборе значений параметров для получения значения веса путем суммирования абсолютных значений разности между каждым значением параметра в наборе значений параметров в структуре данных эталона и соответствующим значением параметра в связанном с кластером упорядоченном наборе значений параметров; и
если значение веса меньше значения отсечки, определение того, что структура данных эталона способна подать голос за графемы.
18. Способ по п. 17, отличающийся тем, что голосование подходящей структурой данных эталона за графемы для одной или более графем дополнительно содержит:
использование полученного значения веса для выбора индекса из упорядоченного набора индексов в структуре данных эталона;
использование выбранного индекса для выбора кода графемы из упорядоченного набора кодов графем в структуре данных эталонов; и
для каждого кода графемы в упорядоченном множестве кодов графем в структуре данных эталона, начиная с первого кода графемы и заканчивая выбранным кодом графемы,
индексацию структуры данных голосов в соответствии с кодами графем для накопления общего итога голосования для графему, соответствующего коду графемы, и добавление значения к общему итогу голосования за графему.
19. Команды в машинном коде, хранящиеся в запоминающих устройствах, которые при выполнении одним или более процессорами в системе оптического распознавания символов управляют системой оптического распознавания символов для:
идентификации изображений символов в содержащем текст отсканированном изображении документа;
для каждой страницы документа,
для каждого изображения символа на странице,
идентификации набора подходящих структур данных эталона для изображения символа, используя лес решений,
использования подходящих структур данных эталона для определения набора подходящих графем, и
использования идентифицированного набора подходящих графем для выбора кода символа, который соответствует изображению символа; и
подготовки обработанного документа, содержащего коды символов, соответствующие изображениям символов из отсканированного изображения документа, и сохранения обработанного документа в одном или более из одного или более запоминающих устройств и модулей памяти.
20. Команды в машинном коде, хранящиеся в физическом запоминающем устройстве по п. 19, причем использование подходящих структур данных эталона для определения набора подходящих графем дополнительно содержит:
оценку каждой возможно подходящей структуры данных эталона в контексте одной или более структур данных кластера на способность голосовать за данную графему;
голосование отобранными подходящими структурами данных эталона за графемы для одной или более графем;
выявление подходящих графем для распознавания изображения символа как тех графем, которые получают голоса; и
сортировку выявленных графем в усеченном отсортированном массиве графем, который представляет набор подходящих графем.
| US 5930392 27.07.1999 | |||
| Изложница с суживающимся книзу сечением и с вертикально перемещающимся днищем | 1924 |
|
SU2012A1 |
| Способ обработки целлюлозных материалов, с целью тонкого измельчения или переведения в коллоидальный раствор | 1923 |
|
SU2005A1 |
| Пломбировальные щипцы | 1923 |
|
SU2006A1 |
| Способ приготовления лака | 1924 |
|
SU2011A1 |
| Станок для изготовления деревянных ниточных катушек из цилиндрических, снабженных осевым отверстием, заготовок | 1923 |
|
SU2008A1 |
| RU2010122947 A 20.12.2011. | |||
