СПОСОБЫ И СИСТЕМЫ АВТОМАТИЧЕСКОГО РАСПОЗНАВАНИЯ СИМВОЛОВ С ИСПОЛЬЗОВАНИЕМ ДЕРЕВА РЕШЕНИЙ

1. Система оптического распознавания символов, содержащая:
один или более процессоров;
один или более модулей памяти;
одно или более запоминающих устройств; и
команды в машинном коде, хранящиеся в одном или более из одного или более запоминающих устройств при выполнении одним или более из одного или более процессоров управляют системой оптического распознавания символов для обработки содержащего текст отсканированного изображения документа за счет:
идентификации изображений символов в отсканированном изображении документа;
для каждого выявленного изображения символа,
начиная с корневого узла дерева решений, хранящегося в системе оптического распознавания символов, рекурсивного обхода дерева решений до тех пор, пока классификатор в узле дерева решений не распознает изображение символа; и
представления изображение символа с помощью кода символа, связанного с классификатором, и
подготовки обработанного документа, содержащего коды символов, которые представляют собой изображения символов в изображении отсканированного документа и хранение обработанного документа в одном или более из одного или более накопителей данных и устройствах памяти.
2. Система оптического распознавания символов по п. 1, отличающаяся тем, что дерево решений содержит:
корневой узел, который содержит классификатор;
несколько узлов промежуточного уровня, каждый из которых содержит классификатор; и
несколько конечных узлов, каждый из которых содержит несколько классификаторов.
3. Система оптического распознавания символов по п. 2, отличающаяся тем, что строящееся дерево решений в каждом корневом узле и узле промежуточного уровня, каждый из которых связан с двумя или более дочерними узлами, содержит классификатор, выбранный из еще не выбранных классификаторов на основании расчетного показателя, отражающего одну или более целей, которые содержат:
при обходе дерева решений распознание максимального количества изображений символов;
при обходе дерева решений направление максимально возможного количества нераспознанных изображений символов, которые соответствует одному классу символов, в один дочерний узел; и
во время обхода дерева решений, передача аналогичного количества нераспознанных изображений символов в каждый дочерний узел.
4. Система оптического распознавания символов по п. 2, отличающаяся тем, что каждый корневой узел и промежуточный узел дерева решений имеет левую линию связи с первым дочерним узелом более низкого уровня и правую линию связи со вторым дочерним узелом более низкого уровня.
5. Система оптического распознавания символов по п. 2, отличающаяся тем, что каждый классификатор, содержащийся в узле дерева решений, содержит:
количество кортежей, причем каждый кортеж, содержит ссылку на структуру данных эталона и ожидаемое значение;
указание количества кортежей, содержащихся в классификаторе;
код символа или ссылку на код символа, для символа, распознанного классификатором; и
несколько значений порогов.
6. Система оптического распознавания символов по п. 5, отличающаяся тем, что каждый классификатор в корневом узле или в узле промежуточного уровня получает в качестве входных данных изображение символа и возвращает в качестве выходных данных решение.
7. Система оптического распознавания символов по п. 6, отличающаяся тем, что каждый классификатор в корневом узле или в узле промежуточного уровня после получения введенного изображения символов:
вычисляет значение веса из весов, полученных структурой данных эталона, на которую ссылается каждый кортеж, и ожидаемого значения, содержащегося в каждом кортеже; и
определяет решение о выходе на основе одного или более из нескольких пороговых значений и расчетного значения веса.
8. Система оптического распознавания символов по п. 7, отличающаяся тем, что значение веса рассчитывается:
для каждого кортежа
путем вычитания значения веса, полученного структурой данных эталона, на которую имеется ссылка, содержащаяся в кортеже, и ожидаемого значения, содержащегося в кортеже для получения разности,
путем вычисления абсолютного значения разности,
путем масштабирования вычисленного абсолютного значения и
путем добавления масштабированного расчетного абсолютного значения к накопителю; и
путем деления значения в накопителе на количество кортежей, содержащихся в классификаторе.
9. Система оптического распознавания символов по п. 7, отличающаяся тем, что решение, возвращаемое каждым классификатором корневого узла и узла промежуточного уровня, в который во время обхода дерева решений поступает изображение символа с целью распознавания символа, выбирается из решений:
«найдено», возвращаемого классификатором, если расчетный вес меньше низкого порога;
«левый», возвращаемого классификатором, если расчетный вес меньше левого/правого порога и больше или равен низкому порогу; и
«правый», возвращаемого классификатором, если расчетный вес больше левого/правого порога.
10. Система оптического распознавания символов по п. 7, отличающаяся тем, что решение, возвращаемое каждым классификатором корневого узла и узла промежуточного уровня, для которого во время построения и одновременного обучения дерева решений вводится изображение символа с целью распознавания символа, выбирается из решений:
«найдено», возвращаемого классификатором, если расчетный вес меньше низкого порога;
«левый», возвращаемого классификатором, если расчетный вес меньше «левого серого» порога и больше или равен нижнему порогу;
«левый и правый», возвращаемого классификатором, если расчетный вес меньше правого серого порога и больше или равен левому серому порогу; и
«правый», возвращаемого классификатором, если расчетный вес больше или равен правому серому порогу.
11. Система оптического распознавания символов по п. 5, отличающаяся тем, что каждый классификатор в конечном узле в качестве входных данных принимает изображение символа и возвращает в качестве выхода решение и вес.
12. Система оптического распознавания символов по п. 11, отличающаяся тем, что каждый классификатор в конечном узле после получения введенного изображения символа:
рассчитывает значение веса из весов, полученных структурой данных эталона, на которую ссылается кортеж, и ожидаемого значения, содержащегося в каждом кортеже;
выводит расчетное значение веса и решение «найдено», если расчетный вес меньше нижнего порога; и
в противном случае выводит расчетный вес и решение, отличное от решения «найдено».
13. Система оптического распознавания символов по п. 5, отличающаяся тем, что каждая структура данных эталона, содержащаяся в каждом классификаторе, включает:
количество кортежей, причем каждый кортеж содержит ссылку на функцию признака и ожидаемое значение; и
указание на количества кортежей, содержащихся в структуре данных эталона.
14. Система оптического распознавания символов по п. 13, отличающаяся тем, что структура данных эталона получает вес для изображения символа:
для каждого кортежа
путем вычитания значения веса, полученного функцией признака, на которую имеется ссылка, содержащаяся в кортеже, обрабатывающей изображение символа из ожидаемого значения, содержащегося в кортеже для получения разности,
путем вычисления абсолютного значения разности,
путем масштабирования вычисленного абсолютного значения и
путем добавления масштабированного расчетного абсолютного значения к накопителю; и
путем деления значения накопителя на количество кортежей, содержащихся в структуре данных эталона.
15. Система оптического распознавания символов по п. 1, отличающаяся тем, что начиная с корневого узла дерева решений, хранящегося в системе оптического распознавания символов, обход дерева решений, до тех пор, пока классификатор в узле дерева решений не распознает изображение символа, дополнительно включает:
рекурсивный обход, начиная с корневого узла дерева решений, который считается рассматриваемым в настоящее время узлом,
ввод изображения символа в классификатор рассматриваемого в настоящий момент узла;
если классификатор возвращает решение «найдено», возвращение кода символа, содержащегося в классификаторе или на который классификатор ссылается, в качестве кода символа, соответствующего изображению символа;
если классификатор возвращает решение «левый», и левый дочерний узел рассматриваемого узла является узлом промежуточного уровня, принятие левого дочернего узла рассматриваемого узла в качестве следующего рассматриваемого узла для следующей рекурсии;
если классификатор возвращает решение «правый», а правый дочерний узел рассматриваемого узла является узлом промежуточного уровня, принятие правого дочернего узла рассматриваемого узла в качестве следующего рассматриваемого узла для следующей рекурсии; и
если классификатор возвращает решение «левый» или решение «правый», а дочерними узлами рассматриваемого являются конечные узлы, выполнение обхода классификаторов в пределах указанного оконечного узла для определения кода символа, соответствующего изображению символа.
16. Система оптического распознавания символов по п. 15, отличающаяся тем, что обход классификаторов в пределах указанного конечного узла для определения кода символа, соответствующего изображению символа, дополнительно включает:
ввод изображения символа для каждого последующего классификатора в конечном узле, пока либо классификатор не вернет решение «найдено», и в этом случае код символа, содержащийся в классификаторе или на который ссылается классификатор, идентифицируется как код символа, соответствующий изображению символа, либо до тех пор, пока не останется классификаторов, в которые можно вводить код символа, в этом случае код символа, содержащиеся в классификаторе или на который ссылается классификатор, который возвратил самое малое значение веса, идентифицируется как код символа, соответствующий изображению символа.
17. Способ, встроенный в систему оптического распознавания символов, использующую один или более процессоров, один или более устройств памяти, один из более накопителей данных, и дерево решений, хранящееся в одном или более из одного или более устройств памяти и одном из более накопителей данных, причем этот способ реализован с помощью машинных команд, хранящихся в одном или более из одного или более накопителей данных, которые при их выполнении одним или более из одного или более процессоров, управляют системой оптического распознавания символов для идентификации кода символа, соответствующего символу изображения, отличающийся тем, что способ содержит:
рекурсивный обход дерева решений, начиная с корневого узла дерева решений, до тех пор, пока классификатор в узле дерева решений не распознает изображение символа; и
хранение ассоциации изображения символа с кодом символа, которая представляет изображение символа, распознанного классификатором в одном или более из одного или более устройств памяти и одном или более накопителе данных.
18. Способ по п. 17,
отличающийся тем, что дерево решений содержит
корневой узел и несколько узлов промежуточного уровня, каждый из которых содержит классификатор, и каждый такой узел содержит правую линию связи с правым дочерним узлом и левую линию связи с левым дочерним узлом, а также несколько конечных узлов, каждый из которых содержит несколько классификаторов; и
отличающийся тем, что каждый классификатор ссылается на несколько структур данных эталона и для каждой структуры данных эталона содержит ожидаемое значение, при этом каждая структура данных эталона, на которую имеются ссылки из классификатора, ссылается на несколько функций признаков и содержит ожидаемое значение для каждой функции признака, на которую имеется ссылка.
19. Способ по п. 18, отличающийся тем, что классификатор в корневом узле или в узле промежуточного уровня в дополнение к ссылке на структуры данных эталона и соответствующим ожидаемым значениям содержит:
указание на количество структур данных эталона, на которые ссылается этот классификатор;
код символа или ссылку на код символа, для символа, распознанного классификатором; и
несколько пороговых значений.
20. Способ по п. 19, отличающийся тем, что каждый классификатор в корневом узле или в узле промежуточного уровня принимает в качестве входных данных изображение символа и возвращает в качестве выходных данные решение следующим образом:
для каждой структуры данных эталона, на которую имеется ссылка:
путем вычитания веса, полученного с помощью структуры данных эталона для изображения символа, и ожидаемого значения, соответствующего ссылочной структуре данных эталона для получения разности;
путем вычисления абсолютного значения разности,
путем масштабирование вычисленного абсолютного значения и
путем добавления масштабированного расчетного абсолютного значение к накопителю; и
путем деления значения в накопителе на количество структур данных эталона, на которые ссылается классификатор для получения расчетного веса;
если расчетный вес меньше нижнего порога, то возвращается решение «найдено»;
если расчетный вес меньше левого/правого порога и больше или равен нижнему порогу, то возвращается решение «левый»; и
если расчетный вес больше, чем левый/правый порог, то возвращается решение «правый».
21. Способ по п. 18, отличающийся тем, что каждый классификатор в конечном узле принимает в качестве входных данных изображение символа и возвращает в качестве выходных данных решение и вес следующим образом:
для каждой структуры данных эталона, на которую имеется ссылка:
путем вычитания веса, полученного структурой данных эталона для изображения символа, и ожидаемого значения, соответствующего структуре данных эталона, на которую имеется ссылка, для получения разности,
путем вычисления абсолютного значения разности,
путем масштабирование вычисленного абсолютного значения и
путем добавления масштабированного расчетного абсолютного значение к накопителю; и
путем деления значения в накопителе на количество структур данных эталона, на которые ссылается классификатор для получения расчетного веса;
если расчетный вес меньше нижнего порога, то возвращается решение «найдено» и расчетный вес; и
если расчетный вес больше или равен нижнему порогу, то возвращается решение, отличное от «найдено» и расчетный вес.
22. Способ по п. 17, отличающийся тем, что начиная с корневого узла дерева решений, выполняется рекурсивный обход дерева решений до тех пор, пока классификатор в узле дерева решения не распознает изображение символа, дополнительно включающий:
рекурсивный обход, начиная с корневого узла дерева решения, как рассматриваемого узла,
ввод изображения символа в классификатор рассматриваемого узла;
если классификатор возвращает решение «найдено», возврат кода символа, содержащегося в классификаторе или на который классификатор ссылается в качестве кода символа, соответствующего изображению символа;
если классификатор возвращает решение «левый», а левый дочерний узел рассматриваемого узла является узлом промежуточного уровня, принятие левого дочернего узла рассматриваемого узла в качестве следующего рассматриваемого узла для следующей рекурсии;
если классификатор возвращает решение «правый», а правый дочерний узел рассматриваемого узла является узлом промежуточного уровня, принятие правого дочернего узла рассматриваемого узла в качестве следующего рассматриваемого узла для следующей рекурсии; и
если классификатор возвращает решение «левый» или решение «правый», а дочерними узлами рассматриваемого являются конечные узлы, выполнение обхода классификаторов в пределах указанного конечного узла, в зависимости от принятого решения, для определения кода символа, соответствующего изображению символа.
ввод изображения символов в каждый последующий классификатор внутри указанного оконечного узла до тех пор, пока классификатор не возвратит решение «найдено», и в этом случае код символа, содержащийся в классификаторе или на который ссылается классификатор, идентифицируется как код символа, соответствующий изображению символа, или до тех пор, пока больше не будет классификаторов, в которые можно ввести код символа, и в этом случае код символа, содержащийся в классификаторе или на который ссылается классификатор, который возвратил наименьшее значение веса, считается кодом символа, соответствующим изображению символа.
23. Машинные команды, хранящиеся в физическом накопителе данных, реализующие способ, встроенный в систему оптического распознавания символов, имеющую один или более процессоров, одно или более устройств памяти, один из нескольких накопителей данных, а также дерево решений, которое хранится в одном или более из одного или более устройств памяти и одном или более накопителей данных, причем этот способ реализуется с помощью компьютерных команд, хранящихся в одном или более из одного или более накопителей данных, которые при их выполнении одним или более из одного или более процессоров управляют системой оптического распознавания символов для определения кода символа, соответствующего изображению символа, причем этот способ содержит следующее:
рекурсивный обход дерева решений, начиная с корневого узла дерева решений, до тех пор, пока классификатор в узле дерева решений не распознает изображение символа; и
хранение ассоциации изображения символа с кодом символа, которая представляет изображение символа, распознанного классификатором в одном или более из одного или более устройств памяти и одном или более накопителе данных.