СПОСОБЫ И СИСТЕМЫ ОПТИЧЕСКОГО РАСПОЗНАВАНИЯ СИМВОЛОВ СЕРИИ ИЗОБРАЖЕНИЙ
METHODS AND SYSTEMS OF OPTICAL RECOGNITION OF IMAGE SERIES CHARACTERS

ОБЛАСТЬ ТЕХНИКИ
[0001] Настоящее изобретение в целом относится к вычислительным системам, а точнее - к системам и способам оптического распознавания символов (OCR).
УРОВЕНЬ ТЕХНИКИ
[0002] Оптическое распознавание символов (OCR) представляет собой реализованное вычислительными средствами преобразование изображений, содержащих текст (включая типографский, рукописный или печатный текст), в машиночитаемые электронные документы.
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
В соответствии с одним или более вариантами реализации настоящего изобретения описанный в примере способ выполнения оптического распознавания символов (OCR) набора изображений, содержащих символы определенного алфавита, может содержать: получение обрабатывающим устройством текущего изображения из серии изображений исходного документа, где разметка текста текущего изображения включает координаты четырехугольника текущей последовательности символов, содержащего последовательность символов с текущего изображения; выполнение оптического распознавания символов (OCR) текущего изображения для создания текущей последовательности символов и соответствующей разметки текста, где разметка текста текущего изображения включает координаты четырехугольника текущей последовательности символов, содержащего последовательность символов текущего изображения; связывание с использованием преобразования координат текущей последовательности символов с первым кластером из множества кластеров предыдущих последовательностей символов, где каждая предыдущая последовательность символов в первом кластере получена путем обработки одного из ранее полученных изображений из набора изображений, где каждое из ранее полученных изображений имеет соответствующую предыдущую разметку текста изображения, содержащую координаты четырехугольника предыдущей последовательности символов, который содержит предыдущую последовательность символов; объединение последовательностей символов из первого кластера путем выявления первой медианной строки, представляющей первый кластер последовательностей символов, исходя из первого подмножества изображений в наборе изображений, где первая медианная строка представляет собой итоговый распознанный текст, представляющий как минимум часть исходного документа; вычисление преобразования четырехугольников предыдущих последовательностей символов в текущее изображение для получения преобразованных четырехугольников предыдущих последовательностей символов; определение расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов; выявление медианного четырехугольника последовательности символов для четырехугольников предыдущих последовательностей символов и четырехугольника текущей последовательности символов, исходя из расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов; отображение с использованием медианного четырехугольника последовательности символов итогового распознанного текста, представляющего как минимум часть исходного документа; где расстояние между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов является показателем различия в геометрии четырехугольников последовательностей символов; причем определение расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов включает определение коэффициентов проекции для четырехугольника текущей последовательности символов в единичный квадрат; применение определенного проективного преобразования к преобразованными четырехугольникам предыдущих последовательностей символов для получения конвертированных преобразованных четырехугольников предыдущих последовательностей символов; где определение расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов включает также определение длины отрезков, соединяющих вершины конвертированных преобразованных четырехугольников предыдущих последовательностей символов и вершины единичного квадрата; причем выявление медианного четырехугольника последовательности символов, представляющего собой преобразованный четырехугольник последовательности символов, для которого расстояние до четырехугольника текущей последовательности символов является медианой для других расстояний между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов; где длины отрезков между вершинами преобразованных четырехугольников предыдущих последовательностей символов и вершинами единичного квадрата взвешены; где для каждого распознанного символа текущей последовательности распознанных символов разметка текста на текущем изображении включает координаты четырехугольника текущего символа, содержащего символ текущего изображения; причем определенное расстояние между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов включает нормализацию расстояния между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов по числу символов в последовательностях символов; где отображение с использованием медианного четырехугольника последовательности символов итогового распознанного текста, также включает определение четырехугольников символов для символов первой медианной строки, исходя из медианного четырехугольника последовательности символов; определение базовых линий на основе четырехугольников символов; определение итогового четырехугольника медианной строки на основе четырехугольников символов.
[0003] В соответствии с одним или более вариантами реализации настоящего изобретения пример системы для осуществления оптического распознавания символов (OCR) серии изображений, содержащих символы определенной системы письменности, может включать запоминающее устройство, устройство обработки, подключенное к запоминающему устройству, причем устройство обработки предназначено для выполнения следующих операций: получение обрабатывающим устройством текущего изображения из серии изображений исходного документа, где разметка текста текущего изображения включает координаты четырехугольника текущей последовательности символов, содержащего последовательность символов с текущего изображения; выполнение оптического распознавания символов (OCR) текущего изображения для создания текущей последовательности символов и соответствующей разметки текста, где разметка текста текущего изображения включает координаты четырехугольника текущей последовательности символов, содержащего последовательность символов текущего изображения; связывание с использованием преобразования координат текущей последовательности символов с первым кластером из множества кластеров предыдущих последовательностей символов, где каждая предыдущая последовательность символов в первом кластере получена путем обработки одного из ранее полученных изображений из набора изображений, где каждое из ранее полученных изображений имеет соответствующую предыдущую разметку текста изображения, содержащую координаты четырехугольника предыдущей последовательности символов, который содержит предыдущую последовательность символов; объединение последовательностей символов из первого кластера путем выявления первой медианной строки, представляющей первый кластер последовательностей символов, исходя из первого подмножества изображений в наборе изображений, где первая медианная строка представляет собой итоговый распознанный текст, представляющий как минимум часть исходного документа; вычисление преобразования четырехугольников предыдущих последовательностей символов в текущее изображение для получения преобразованных четырехугольников предыдущих последовательности символов; определение расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов; выявление медианного четырехугольника последовательности символов для четырехугольников предыдущих последовательностей символов и четырехугольника текущей последовательности символов, исходя из расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов; отображение с использованием медианного четырехугольника последовательности символов итогового распознанного текста, представляющего как минимум часть исходного документа; где расстояние между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов является показателем различия в геометрии четырехугольников последовательностей символов; причем определение расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов включает определение коэффициентов проекции для четырехугольника текущей последовательности символов в единичный квадрат; применение определенного проективного преобразования к преобразованными четырехугольникам предыдущих последовательностей символов для получения конвертированных преобразованных четырехугольников предыдущих последовательностей символов; где определение расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов включает также определение длины отрезков, соединяющих вершины конвертированных преобразованных четырехугольников предыдущих последовательностей символов и вершины единичного квадрата; причем выявление медианного четырехугольника последовательности символов, представляющего собой преобразованный четырехугольник последовательности символов, для которого расстояние до четырехугольника текущей последовательности символов является медианой для других расстояний между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов; где длины отрезков между вершинами преобразованных четырехугольников предыдущих последовательностей символов и вершинами единичного квадрата взвешены; где для каждого распознанного символа текущей последовательности распознанных символов разметка текста на текущем изображении включает координаты четырехугольника текущего символа, содержащего символ текущего изображения; причем определенное расстояние между преобразованными четырехугольниками последовательностей символов и текущим четырехугольником последовательности символов включает нормализацию расстояния между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов по числу символов в последовательностях символов; где отображение с использованием медианного четырехугольника последовательности символов итогового распознанного текста также включает определение четырехугольников символов для символов первой медианной строки, исходя из медианного четырехугольника последовательности символов; определение базовых линий на основе четырехугольников символов; определение итогового четырехугольника медианной строки на основе четырехугольников символов.
[0004] В соответствии с одним или более вариантами реализации настоящего изобретения пример постоянного машиночитаемого носителя данных может включать исполняемые команды, которые при исполнении их вычислительным устройством приводят к выполнению вычислительным устройством операций, включающих в себя: получение обрабатывающим устройством текущего изображения из серии изображений исходного документа, где текущее изображение хотя бы частично перекрывается с предыдущим изображением серии изображений; выполнение оптического распознавания символов (OCR) текущего изображения для создания текущей последовательности символов и соответствующей разметки текста, где разметка текста текущего изображения включает координаты четырехугольника текущей последовательности символов, содержащего последовательность символов текущего изображения; связывание с использованием преобразования координат текущей последовательности символов с первым кластером из множества кластеров предыдущих последовательностей символов, где каждая предыдущая последовательность символов в первом кластере получена путем обработки одного из ранее полученных изображений из набора изображений, где каждое из ранее полученных изображений имеет соответствующую предыдущую разметку текста изображения, содержащую координаты четырехугольника предыдущей последовательности символов, который содержит предыдущую последовательность символов; объединение последовательностей символов из первого кластера путем выявления первой медианной строки, представляющей первый кластер последовательностей символов, исходя из первого подмножества изображений в наборе изображений, где первая медианная строка представляет собой итоговый распознанный текст, представляющий как минимум часть исходного документа; вычисление преобразования четырехугольников предыдущих последовательностей символов в текущее изображение для получения преобразованных четырехугольников предыдущих последовательностей символов; определение расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов; выявление медианного четырехугольника последовательности символов для четырехугольников предыдущих последовательностей символов и четырехугольника текущей последовательности символов, исходя из расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов; отображение с использованием медианного четырехугольника последовательностей символов итогового распознанного текста, представляющего как минимум часть исходного документа; где расстояние между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов является показателем различия в геометрии четырехугольников последовательностей символов; причем определение расстояния между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов включает определение коэффициентов проекции для четырехугольника текущей последовательности символов в единичный квадрат; применение определенного проективного преобразования к преобразованными четырехугольникам предыдущих последовательностей символов для получения конвертированных преобразованных четырехугольников предыдущих последовательностей символов; где определение расстояния между преобразованными четырехугольниками предыдущих последовательности символов и четырехугольником текущей последовательности символов включает также определение длины отрезков, соединяющих вершины конвертированных преобразованных четырехугольников предыдущих последовательностей символов и вершины единичного квадрата; причем выявление медианного четырехугольника последовательности символов, представляющего собой преобразованный четырехугольник последовательности символов, для которого расстояние до четырехугольника текущей последовательности символов является медианой для других расстояний между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов; где длины отрезков между вершинами преобразованных четырехугольников предыдущих последовательностей символов и вершинами единичного квадрата взвешены; где для каждого распознанного символа текущей последовательности распознанных символов разметка текста на текущем изображении включает координаты четырехугольника текущего символа, содержащего символ текущего изображения; причем определенное расстояние между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов включает нормализацию расстояния между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов по числу символов в последовательностях символов; где отображение с использованием медианного четырехугольника последовательности символов итогового распознанного текста также включает определение четырехугольников символов для символов первой медианной строки, исходя из медианного четырехугольника последовательности символов; определение базовых линий на основе четырехугольников символов; определение итогового четырехугольника медианной строки на основе четырехугольников символов.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
[0005] Настоящее изобретение иллюстрируется с помощью примеров, а не способом ограничения, и может быть лучше понято при рассмотрении приведенного ниже описания предпочтительных вариантов реализации в сочетании с чертежами, на которых:
[0006] На фиг. 1А-1В схематически показаны примеры четырехугольников символов и четырехугольников последовательностей символов.
[0007] На фиг. 2 показана блок-схема одного из иллюстративных примеров способа определения геометрии символов текста, выявленных при выполнении оптического распознавания символов (OCR) серии изображений, содержащих символы текста, в соответствии с одним или более вариантами реализации настоящего изобретения;
[0008] На фиг. 3А-3В схематически показан пример последовательности из трех изображений, проективные преобразования между парами изображений и соответствующие последовательности символов, полученные при OCR соответствующих изображений, в соответствии с одним или более вариантами реализации настоящего изобретения;
[0009] На фиг. 4 схематически иллюстрируется граф, содержащий множество кластеров вершин, так что каждый кластер представляет две или более совпадающих последовательностей символов, в соответствии с одним или более вариантами реализации настоящего изобретения;
[00010] На фиг. 5А-5С схематически иллюстрируется выявление медианной строки среди множества последовательностей символов, представляющих результаты OCR соответствующих фрагментов изображения, в соответствии с одним или более вариантами реализации настоящего изобретения;
[00011] На фиг. 6А-6В схематически иллюстрируется серия четырехугольников последовательностей символов и их проективное преобразование в одну систему координат.
[00012] На фиг. 6С иллюстрируется преобразование четырехугольника текущей последовательности символов в единичный квадрат.
[00013] На фиг. 6D показаны различия между единичным квадратом и конвертированными преобразованным четырехугольником предыдущей последовательности символов.
[00014] На фиг. 7 схематично показан пример способа определения расстояния между конвертированным преобразованным четырехугольником предыдущей последовательности символов и единичным квадратом.
[00015] На фиг. 8 приведена схема иллюстративного примера вычислительной системы, в которой реализованы способы настоящего изобретения.
ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ РЕАЛИЗАЦИИ
[00016] В данном документе описаны способы и системы для осуществления оптического распознавания символов (OCR) серии изображений, содержащих символы определенной системы письменности с возможным дополнительным извлечением данных. Алфавиты, символы которых могут быть обработаны с помощью систем и способов, описанных в этом документе, включают алфавиты с отдельными символами, или глифами, соответствующими отдельным звукам, а также иероглифические системы письменности с отдельными символами, соответствующими более крупным блокам, таким как слоги или слова.
[00017] В приведенном ниже описании термин «документ» должен толковаться широко, как относящийся к широкому спектру носителей текста, включая, помимо прочего, печатные или написанные от руки бумажные документы, баннеры, постеры, знаки, рекламные щиты и (или) другие физические объекты, несущие видимые символы текста на одной или более поверхностях. В приведенном ниже описании термин «изображение документа» относится к изображению как минимум части исходного документа  (например, страницы бумажного документа).
[00018] Система оптического распознавания символов (OCR) может получать изображение документа и преобразовывать полученное изображение, содержащее текст, в машиночитаемый формат, допускающий поиск и содержащий оцифрованную текстовую информацию, извлеченную из изображения бумажного документа. Затем оцифрованная текстовая информация может быть представлена пользователю. Для представления текста пользователю система OCR также выявляет геометрию текста внутри документа.
[00019] В следующем описании термины «геометрия текста», «геометрия последовательности символов», «геометрия символа» внутри документа следует понимать как описание четырехугольника, охватывающего этот текст, последовательность символов или символ. Описание этих четырехугольников включает координаты каждой из их вершин в системе координат документа. Геометрия текста также включает верхнюю и нижнюю базовые линии. Нижняя базовая линия - это линия, над которой находится большинство букв, а ниже располагаются только нижние выносные элементы. Верхняя базовая линия - это линия, ниже которой располагается большинство строчных букв, а выше - только прописные буквы, диакритические знаки и верхние выносные элементы. В идеале верхняя и нижняя базовые линии параллельны друг другу, и охватывающий четырехугольник становится прямоугольником.
[00020] Когда камера захватывает изображение документа под углом к поверхности документа, интересующие нас объекты, такие как последовательности символов (символы) и их соответствующие охватывающие прямоугольники внутри документа, проецируются на плоскость изображения в соответствии с принципами перспективной проекции. В перспективной проекции двухмерные проекции двух параллельных линий в трехмерном пространстве пересекаются в точке на плоскости изображения (точка схода). Таким образом, прямоугольники последовательностей символов/символов, описанные ранее, будут искажены и представлены в виде четырехугольников, у которых продолжения противоположных сторон пересекаются в определенных точках схода.
[00021] Процесс OCR может быть затруднен различными дефектами изображения, такими как визуальный шум, расфокусировка или низкая резкость изображения, блики и т.д., которые обычно вызваны дрожанием камеры, недостаточным освещением, неправильно выбранной выдержкой или диафрагмой и (или) другими условиями и затрудняющими обстоятельствами. Из-за этих дефектов, которые могут отличаться для разных изображений серии изображений, результаты OCR этих изображений могут значительно отличаться по типу распознанных символов, а также по количеству распознанных символов в последовательностях символов, объединенных в один и тот же кластер, количеством слов в символьных последовательностях, объединенных в один и тот же кластер (два слова в результатах распознавания одного изображения могут соответствовать одному слову в результатах распознавания другого изображения). Такое несоответствие в результатах OCR создает неопределенность в геометрии медианной строки, определенной для кластера. Описанные в настоящем документе системы и способы могут значительно повысить точность геометрии для медианной строки за счет анализа серии изображений (например, последовательности видеокадров или фотоснимков) документа, как более подробно описано ниже.
[00022] Кроме того, при определенных обстоятельствах исходный документ не может быть помещен в одно изображение без существенной потери качества изображения. Потеря качества изображения может быть уменьшена путем получения серии частично перекрывающихся изображений нескольких фрагментов исходного документа, которые, однако, могут не подходить для последующей обработки OCR с помощью общих способов распознавания. Системы и способы, описанные в настоящем изобретении, могут эффективно комбинировать результаты распознавания символов и обнаружения геометрии символов, выполняемые для нескольких фрагментов документа, для получения текста исходного документа с его полной исходной геометрией, которая включает в себя координаты четырехугольников для всех символов в тексте и базовые линии для каждой последовательности символов в системе координат изображения серии изображений.
[00023] В некоторых вариантах осуществления текст, полученный с помощью систем и способов OCR, описанных в этом документе, может подвергаться дополнительной обработке, например, для извлечения конкретных данных, верификации и сбора данных.
[00024] В иллюстративном примере вычислительная система, в которой реализованы способы настоящего изобретения, может получить серию изображений (например, последовательности видеокадров или неподвижных кадров изображения) исходного документа. Изображения могут отображать, по меньшей мере, частично перекрывающиеся фрагменты документа и могут отличаться масштабом изображения, ракурсом, выдержкой, диафрагмой, яркостью изображения, наличием бликов, наличием внешних объектов, которые по меньшей мере частично покрывают исходный текст и (или) другие элементы изображения, визуальными артефактами и параметрами процесса обработки изображений.
[00025] Компьютерная система может выполнять OCR по меньшей мере выбранных изображений полученной серии изображений для получения соответствующего текста и геометрии распознанного текста. Геометрическая информация может связывать распознанные символы и (или) группы символов с координатами их соответствующих описывающих четырехугольников в исходном изображении. Чтобы объединить результаты распознавания символов и обнаружения геометрии, выполненные для последовательно полученных изображений, компьютерная система может сравнивать текст и геометрию, создаваемые OCR полученного текущего изображения, с текстом и геометриями, создаваемыми OCR одного или нескольких ранее обработанных изображений.
[00026] В соответствии с одним или более вариантами реализации настоящего изобретения вычислительная система может выявлять кластеры последовательностей символов, которые, вероятно, соответствуют одному и тому же фрагменту исходного документа. Эти аспекты настоящего изобретения подробно описаны в заявке на патент США (U.S. Patent Application) №15/168,548, с названием «ОПТИЧЕСКОЕ РАСПОЗНАВАНИЕ СИМВОЛОВ В СЕРИИ ИЗОБРАЖЕНИЙ» Алексея Калюжного, поданной 31 мая 2016 года.
[00027] Для каждого кластера совпадающих последовательностей символов может быть определена медианная строка, представляющая результат OCR соответствующего фрагмента изображения. В некоторых вариантах реализации медианная строка может быть выявлена как последовательность символов, имеющая минимальную сумму расстояний редактирования до всех последовательностей символов кластера. Расстояние редактирования, которое в одном из иллюстративных примеров может быть представлено расстоянием Левенштейна, между первой последовательностью символов и второй последовательностью символов может быть равно минимальному количеству редактирований единичных символов (например, вставок, удалений или замен), необходимых для преобразования первой последовательности символов во вторую последовательность символов.
[00028] Тексты, полученные при OCR каждого отдельного изображения, могут отличаться одним или более словами, присутствующими или отсутствующими в каждом из результатов OCR, вариациями в последовательностях символов, представляющих слова исходного текста, порядком последовательностей символов и (или) наличием так называемых «мусорных» символов, то есть артефактов, созданных системой из-за дефектов изображений, которые отсутствуют в документе.
[00029] Геометрия текстов, созданных OCR каждого отдельного изображения, может быть определена с неточностями и, следовательно, отличается расположением соответствующих четырехугольников, их размером, углом их сторон, точками схода и т.д. Такие причины для подобных различий могут быть проиллюстрированы на фиг. 1А.
[00030] На фиг. 1А изображено представление двух символов 100 и 102 на двух разных изображениях, которые соответствуют одному и тому же символу в документе. Для символа 100 из-за искажения изображения верхняя базовая строка 110 и нижняя базовая строка 115 не параллельны. Они пересекаются в точке схода 106. Символ 102 отличается от символа 100 артефактом 104. Такой артефакт может быть создан системой OCR из-за шума изображения, бликов, плохого освещения и т.д. Из-за этого артефакта 104 верхняя линия 120 и нижняя базовая линия 125 символа 102 пересекаются в другой точке схода 108. Другими словами, из этих двух изображений невозможно определить верхнюю и нижнюю базовые линии для символа 100, 102.
[00031] Когда серия совпадающих последовательностей символов объединяется, мы находим медианную строку или результирующий распознанный текст для такой серии последовательностей символов. Для ряда четырехугольников, соответствующих этим последовательностям символов, нам также необходимо определить медианный четырехугольник последовательности символов, наиболее подходящий четырехугольник, на основе которого может быть идентифицирован лучший четырехугольник, описывающий медианную строку. Поиск такой наилучшей геометрии последовательности символов, наиболее подходящей для медианной последовательности символов, является одной из целей настоящего изобретения.
[00032] Различные аспекты упомянутых выше способов и систем подробно описаны ниже в этом документе с помощью примеров, не с целью ограничения.
[00033] На фиг. 2 показана блок-схема одного из иллюстративных примеров способа 200 выполнения OCR серии кадров изображений, содержащих символы текста, в соответствии с одним или более вариантами реализации настоящего изобретения. Способ 200 и (или) каждая из его отдельно взятых функций, процедур, подпрограмм или операций могут осуществляться с помощью одного или более процессоров вычислительной системы (например, вычислительной системы 800 на фиг. 8), реализующей этот способ. В некоторых реализациях способ 200 может быть реализован в одном потоке обработки. Кроме того, способ 200 может выполняться, используя два или более потоков обработки, причем каждый поток выполняет одну или более отдельных функций, процедур, подпрограмм или операций способа. В качестве иллюстративного примера потоки обработки, в которых реализован способ (200), могут быть синхронизированы (например, с использованием семафоров, критических секций и (или) других механизмов синхронизации потоков). В качестве альтернативы реализующие способ 200 потоки обработки могут выполняться асинхронно по отношению друг к другу. Таким образом, несмотря на то, что фиг. 2 и соответствующее описание содержат список операций для способа 200 в определенном порядке, в различных вариантах реализации способа как минимум некоторые из описанных операций могут выполняться параллельно и (или) в случайно выбранном порядке.
[00034] Для ясности и краткости настоящее описание предполагает, что обработка каждого изображения исходного документа начинается после получения изображения вычислительной системой, реализующей способ, и что эта обработка в значительной степени завершается до получения следующего изображения. Однако в различных альтернативных реализациях изобретения обработка последовательных изображений может совпадать по времени (например, может выполняться в различных потоках или процессах, которые выполняются на одном или более процессорах). Кроме того, два или более изображений могут быть помещены в буфер и обрабатываться асинхронно с учетом получения других изображений из множества изображений, поступающих в вычислительную систему, реализующую способ.
[00035] В настоящем изобретении упоминается «пара изображений» серии изображений (например, последовательность видеокадров или неподвижных изображений) исходного документа. Изображения могут отображать, по меньшей мере, частично перекрывающиеся фрагменты документа и могут отличаться масштабом изображения, ракурсом, выдержкой, диафрагмой, яркостью изображения, наличием бликов, наличием внешних объектов, которые по меньшей мере частично покрывают исходный текст и (или) другие элементы изображения, визуальными артефактами и параметрами процесса обработки изображений. В иллюстративном примере пара изображений может быть выбрана из двух или более последовательных изображений полученной серии изображений. Два изображения индивидуально упоминаются здесь как «текущее изображение» (также называемое «i-м изображением» на фиг. 2) и «предыдущее изображение» (также называемое «i-1)-м изображением» на фиг. 2).
[00036] На шаге 210 компьютерная система, реализующая этот способ, может принимать текущее изображение серии изображений.
[00037] На шаге 215 компьютерная система может выполнять оптическое распознавание символов текущего изображения, создавая, таким образом, распознанный текст и информацию о геометрии текста. Информация геометрии текста может содержать координаты для вершин четырехугольников, описывающих распознанные символы и (или) последовательности символов в системе координат изображения. На фиг. 1В показан иллюстративный пример ограничивающего четырехугольника 128 последовательности символов "Olga" 124. Символ «О» 122 вписан в четырехугольник 126. Четырехугольники 126 и 128 представляют собой проекции первоначально параллельных базовых линий этих четырехугольников на плоскость 120 изображения. Противоположные стороны этих четырехугольников 126 и 128 пересекаются в соответствующих точках схода 130 и 132.
[00038] На шаге 220 вычислительная система может создавать преобразование координат, конвертирующее координаты одного изображения в паре изображений в координаты второго изображения в паре изображений. Описанный в настоящем документе способ предполагает, что как минимум для выбранных пар изображений, координаты произвольной выбранной точки на первом изображении могут быть получены применением проективного преобразования к координатам той же точки на втором изображении. Способ определения опорных точек в серии изображений, подробно описанный в патентной заявке США №15/168,548, с названием «ОПТИЧЕСКОЕ РАСПОЗНАВАНИЕ СИМВОЛОВ В СЕРИИ ИЗОБРАЖЕНИЙ» Алексея Калюжного, поданной 31 мая 2016 года, которая включена здесь полностью.
[00039] Под «проективным преобразованием» здесь подразумевается преобразование, которое отображает линии в линии, но не обязательно сохраняет параллельность. Проективное преобразование может быть описано следующими уравнениями:
1
2
3
4
1
2
3
4
где (x, y) и (X, Y) представляют собой координаты случайно выбранной точки на первом изображении и втором изображении, соответственно. Коэффициенты преобразования Ax, Ах, Ах, Ах, Ay, Ay, Ay и Ay могут определяться, исходя из известных координат не менее чем четырех опорных точек на каждом из двух изображений, которые должны создавать систему из восьми уравнений с восемью неизвестными. После определения коэффициентов преобразования уравнения (1) и (2) можно применить к координатам случайно выбранной точки первого изображения, чтобы получить координаты той же точки на втором изображении.
[00040] На фиг. 3А схематически показан пример последовательности из трех изображений 302, 304 и 306, такой, что координаты первого изображения 302 могут быть преобразованы в координаты второго изображения 304 с помощью проективного преобразования 308, и координаты второго изображения 304 могут быть преобразованы в координаты третьего изображения 306 с помощью проективного преобразования 310.
[00041] На шаге 225 вычислительная система может связывать одну или более последовательностей символов, полученных с помощью OCR текущего изображения, с кластером совпадающих последовательностей символов, полученных при OCR ранее обработанных изображений. Вычислительная система может использовать преобразования координат, указанные выше, чтобы сравнить положения распознанной последовательности символов на текущем и предыдущем изображении и таким образом определить группы последовательностей символов, которые, вероятно, представляют один и тот же фрагмент исходного документа.
[00042] В одном из иллюстративных примеров для случайно выбранной последовательности символов из текста, полученного при оптическом распознавании символов текущего изображения, этот способ может выявить один или более совпадающих последовательностей символов, полученных при оптическом распознавании символов на других изображениях из серии изображений. Следует заметить, что «совпадающие последовательности символов» в настоящем документе соответствуют как точно совпадающим, так и нестрого совпадающим последовательностям символов. На иллюстративном примере на фиг. 3В три совпадающие последовательности символов 312, соответствующие изображениям 302, 304 и 306, представлены тремя различными последовательностями, которые нестрого совпадают в рамках методов настоящего изобретения.
[00043] В некоторых вариантах реализации компьютерная система может создавать граф, вершины которого соответствуют последовательностям символов из множеств изображений, а дуги соединяют последовательности символов, определенные как совпадающие (то есть соответствующие одному и тому же фрагменту исходного текста), путем применения указанного выше преобразования координат между изображениями. Как схематически показано на фиг. 4, полученный граф может содержать множество кластеров вершин, таких, что каждый кластер соответствует двум или более совпадающим последовательностям символов. Вершины в каждом кластере соединены соответствующими ребрами, при этом отдельные кластеры могут быть изолированы или слабо связаны друг с другом. На фиг. 4 показаны два кластера (402, 404), представляющие последовательности символов, создаваемые OCR, для двух исходных строк: «ядро» и «способ».
[00044] Обращаясь снова к фиг. 2, на шаге 230 компьютерная система может увеличивать счетчик, ссылающийся на текущее изображение в серии изображений. Примечательно, что операции шага 230 представлены на фиг. 2 для удобства чтения связанного описания и могут быть опущены в различных реализациях способа.
[00045] На шаге 245 вычислительная система может определить, существует ли следующее изображение. Если это так, способ возвращается обратно к шагу 210.
[00046] На шаге 250 вычислительная система может выявлять медианную строку одного или более кластеров совпадающих последовательностей символов такую, что выявленная медианная строка должна соответствовать результату OCR соответствующего фрагмента изображения.
[00047] Как схематически показано на фиг. 5А, каждый кластер 502 может содержать множество совпадающих последовательностей символов 504, а результат OCR соответствующего фрагмента изображения может быть представлен медианной строкой 506. В некоторых вариантах реализации медианная строка может быть выявлена как последовательность символов, имеющая минимальную сумму расстояний редактирования до всех последовательностей символов кластера. Расстояние редактирования, которое в одном из иллюстративных примеров может быть представлено расстоянием Левенштейна, между первой последовательностью символов и второй последовательностью символов может быть равно минимальному количеству редактирований единичных символов (например, вставок, удалений или замен), необходимых для преобразования первой последовательности символов во вторую последовательность символов.
[00048] В некоторых вариантах реализации вычислительная сложность выявления медианной строки может быть уменьшена за счет применения определенных эвристических методов. В одном из иллюстративных примеров вычислительная система может эвристически выявить аппроксимацию нулевого порядка медианной строки. Затем вычислительная система может выровнять последовательности символов, используя строго совпадающие символы внутри каждой последовательности, как схематически показано на фиг. 5В. В другом иллюстративном примере система распознавания может связывать с каждой последовательностью символов кластера весовой коэффициент, отражающий положение последовательности символов в изображении или показатель уверенности OCR. Как схематически показано на фиг. 5С, кластер 512 содержит четыре последовательности символов: TOP, TOP, TORRENT, TORRENT. Первые две последовательности символов соответствуют частям слов, так как расстояние от границы минимального описывающего прямоугольника последовательности символов до края изображения меньше, чем ширина пробела. Поэтому значение показателя уверенности распознавания для первых двух последовательностей символов значительно меньше, чем значение показателя уверенности распознавания для оставшихся двух последовательностей символов, и поэтому последовательность символов TORRENT будет выбрана в качестве медианной строки методом, который принимает во внимание значения уверенности распознавания.
[00049] Обращаясь к фиг. 2, на шаге 255 компьютерная система может определять проективные преобразования четырехугольников предыдущих последовательностей символов в общую систему координат. В некоторых реализациях система координат текущего изображения используется как общая система координат. Чтобы определить такие проективные преобразования для конкретного кластера, система определяет множество четырехугольников последовательностей символов, связанных с последовательностями символов, представляющими этот кластер на текущем и предыдущих изображениях. Как описано на шаге 215, для каждой из этих последовательностей символов система OCR определяет свою геометрию, то есть координаты для вершин четырехугольников, описывающих последовательности символов в системе координат соответствующего изображения. Используя формулы проективного преобразования (1) и (2), система пересчитывает четырехугольники последовательностей символов из предыдущих изображений в систему координат текущего изображения (или в зависимости от того, какое изображение выбрано для общей системы координат).
[00050] В качестве иллюстративного примера на фиг. 6А изображены четырехугольники последовательностей символов 606, соответствующие последовательностям символов 602. Последовательности символов 602 представляют собой разные результаты OCR из четырех предыдущих изображений, соответствующих одному и тому же кластеру. Настоящее изобретение направлено на определение геометрии для медианной строки 604 этого кластера. На фиг. 6В изображены четырехугольники последовательностей символов 606 после того, как они были перенесены в общую систему координат (например, в систему координат текущего изображения). Как вы можете видеть, все четырехугольники немного отличаются друг от друга. Как объяснялось выше, эти различия обусловлены ошибками в определении геометрии последовательностей символов в предыдущих изображениях, различиями в распознанных последовательностях символов на этих изображениях.
[00051] Каждый из этих преобразованных четырехугольников последовательностей символов представляет собой гипотезу четырехугольника медианной строки, то есть четырехугольника, который нам необходим вычислить для медианной строки. Чтобы определить наилучшую гипотезу, нам нужно определить медианный четырехугольник последовательности символов для этого множества четырехугольников последовательностей символов. Чтобы вычислить такую медиану, нам нужно определить меру расстояния между четырехугольниками последовательностей символов. Здесь расстояние между двумя четырехугольниками последовательностей символов представляет собой меру различия в геометрии этих двух четырехугольников.
[00052] На шаге 260 система определяет расстояния между четырехугольниками последовательностей символов.
[00053] В некоторых вариантах реализации расстояние между двумя четырехугольниками последовательностей символов определяется первым конвертированием четырехугольника текущей последовательности символов в единичный квадрат, затем применяя ту же конвертацию к преобразованным четырехугольникам предыдущих последовательностей символов и затем уже определяя различия между такими конвертированными преобразованными четырехугольниками предыдущих последовательностей символов.
[00054] Прямая конвертация в единичный квадрат может быть рассчитана с использованием следующих формул:
[00055]
[00056]
[00057] где (x, y) - координаты вершин четырехугольника последовательности символов (которые определены на шаге 255);
[00058] (X, Y) - координаты вершин единичного квадрата (которые также известны как (0, 1), (1, 1), (1, 0), (0, 0));
[00059] А, b, с, d, n, m - неизвестные коэффициенты.
[00060] Чтобы вычислить координаты четырехугольника, конвертированного в единичный квадрат, вычислим неизвестные коэффициенты а, b, с, d, n, m путем решения системы уравнений с 6 переменными. После определения коэффициентов формулы (3) и (4) могут быть использованы для преобразования координат любой вершины преобразованного четырехугольника последовательности символов в единичный квадрат.
[00061] На фиг. 6С показана конвертация четырехугольника последовательности символов 608 в соответствующий единичный квадрат 610.
[00062] После того, как коэффициенты а, b, с, d, n, m определены для четырехугольника текущей последовательности символов, формулы (3) и (4) используются с этими коэффициентами для конвертации преобразованных ранее четырехугольников предыдущих последовательностей символов в систему координат единичного квадрата. Эти конвертированные преобразованные четырехугольники предыдущих последовательностей символов будут отличаться от единичного квадрата из-за различий между четырехугольником текущей последовательности символов и преобразованными четырехугольниками предыдущих последовательностей символов. На фиг. 6D показаны различия между единичным квадратом 602 (преобразованным из четырехугольника последовательности символов) и конвертированным преобразованным четырехугольником последовательности символов 604.
[00063] Далее система может определять расстояния между конвертированными преобразованными четырехугольниками предыдущих последовательностей символов и единичным квадратом. В некоторых реализациях это расстояние измеряется путем вычисления суммы длин отрезков между вершинами конвертированных преобразованных предыдущих четырехугольников последовательностей символов и соответствующих вершин единичного квадрата с использованием следующей формулы:
[00064] ,
[00065] где  - расстояние между конвертированным преобразованным четырехугольником последовательности символов и единичным квадратом;
[00066]  - длина отрезка между i-й вершиной конвертированного преобразованного четырехугольника последовательности символов и соответствующей вершиной единичного квадрата.
[00067] Фиг. 7 иллюстрирует вычисление расстояния между конвертированным преобразованным предыдущим четырехугольником последовательности символов 704 и единичным квадратом 702. Длины отрезков между вершинами конвертированного преобразованного четырехугольника последовательности символов и соответствующими вершинами единичного квадрата , , ,  обозначены как 706, 708, 710, 712.
[00068] В других реализациях расстояния между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов определяются другими способами. Например, расстояние может быть измерено площадью непересекающихся частей четырехугольников.
[00069] В некоторых реализациях расчетные расстояния между преобразованными четырехугольниками последовательностей символов и четырехугольником текущей последовательности символов также нормализуются количеством символов в соответствующей последовательности символов. В этом случае расстояние между четырехугольниками последовательностей символов определяется путем вычисления суммы различий между соответствующими четырехугольниками символов и затем нормирования суммы этих различий количеством символов в каждой конкретной последовательности символов.
[00070] На шаге 265 после определения расстояний между четырехугольниками последовательностей символов система определяет наиболее подходящий четырехугольник последовательности символов или медианный четырехугольник последовательности символов, на основе которого может быть рассчитан наилучший четырехугольник медианной строки, описывающий медианную строку. В некоторых реализациях система выбирает в качестве наиболее подходящего преобразованного четырехугольника последовательности символов преобразованный четырехугольник последовательности символов, расстояние которого от четырехугольника текущей последовательности символов является медианой для других расстояний между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов.
[00071] В некоторых реализациях весовые коэффициенты используются при расчете расстояний между преобразованными четырехугольниками предыдущих последовательностей символов и четырехугольником текущей последовательности символов. Например, такие расстояния могут быть умножены на коэффициент, который зависит от количества кадров между предыдущим изображением, для которого рассчитывается расстояние, и текущим изображением.
[00072] В некоторых реализациях после определения медианного четырехугольника последовательности символов на шаге 268 система может вычислять четырехугольник медианной строки, т.е. четырехугольник, описывающий медианную строку. Во-первых, для каждого символа из медианной строки (определенной на шаге 250 на Фиг. 1) система может определить четырехугольник символа, наиболее совместимый с медианным четырехугольником последовательности символов. В одном из вариантов реализации изобретения наиболее совместимый четырехугольник символа для символа может представлять собой четырехугольник символа, связанный с изображением, характеризующимся самым близким положением к изображению, которое соответствует медианному четырехугольнику последовательности символов в серии изображений (определенных на шаге 265 на Фиг. 1), спрямленный в соответствии с геометрией медианного четырехугольника последовательности символов. В другом варианте реализации изобретения наиболее совместимый четырехугольник символа может представлять собой взвешенный средний четырехугольник символа, преобразованный в систему координат изображения, которое соответствует медианному четырехугольнику последовательности символов в серии изображений (определенных на шаге 265 на Фиг. 1). Затем система определяет средние базовые линии и определяет четырехугольник медианной строки, как сумму этих наиболее совместимых четырехугольников символов.
[00073] На шаге 270 система создает результаты OCR, представляющие исходный документ. Это представление основано на медианной строке и четырехугольнике медианной строки, то есть медианная строка, определенная на шаге 250, отображается как вписанная в четырехугольник медианной строки, определенный на шаге 268.
[00074] В различных реализациях настоящего изобретения операции, описанные на шаге 250-265, могут выполняться в обратной последовательности или параллельно. Кроме того, в некоторых реализациях настоящего изобретения некоторые операции, описанные на шаге 250-265, могут быть пропущены.
[00075] На Фиг. 8 представлена более подробная схема компонентов примера вычислительной системы 800, внутри которой исполняется набор инструкций, которые вызывают выполнение вычислительной системой любого из одного или более способов настоящего изобретения. Вычислительная система 800 может быть соединена с другой вычислительной системой по локальной сети, корпоративной сети, сети экстранет или сети Интернет. Вычислительная система 800 может работать в качестве сервера или клиента в сетевой среде клиент-сервер, либо в качестве однорангового вычислительного устройства в равноправной (или распределенной) сетевой среде. Вычислительная система 800 может быть представлена персональным компьютером (ПК), планшетным ПК, телевизионной приставкой (STB), карманным ПК (PDA), сотовым телефоном или любой вычислительной системой, способной выполнять набор команд (последовательно или иным образом), определяющих операции, которые должны быть выполнены этой вычислительной системой. Кроме того, несмотря на то, что показана только одна вычислительная система, термин «вычислительная система» также может включать любую совокупность вычислительных систем, которые отдельно или совместно выполняют набор (или несколько наборов) команд для выполнения одной или более методик, обсуждаемых в настоящем документе.
[00076] Пример вычислительной системы 800 включает процессор 802, основное запоминающее устройство 804 (например, постоянное запоминающее устройство (ПЗУ) или динамическое оперативное запоминающее устройство (ДЗУ)) и устройство хранения данных 818, которые взаимодействуют друг с другом по шине 830.
[00077] Процессор 802 может быть представлен одним или более универсальными устройствами обработки данных, например микропроцессором, центральным процессором и т.д. В частности, процессор 802 может представлять собой микропроцессор с полным набором команд (CISC), микропроцессор с сокращенным набором команд (RISC), микропроцессор с командными словами сверхбольшой длины (VLIW), процессор, реализующий другой набор команд или процессоры, реализующие комбинацию наборов команд. Процессор 802 также может представлять собой одно или более устройств обработки специального назначения, например заказную интегральную микросхему (ASIC), программируемую пользователем вентильную матрицу (FPGA), процессор цифровых сигналов (DSP), сетевой процессор и т.п. Процессор 802 выполнен с возможностью исполнения инструкций 826 для выполнения операций и функций способа 100 для выполнения OCR серии изображений, содержащих символы текста, как описано выше в этом документе.
[00078] Вычислительная система 800 может дополнительно включать в себя устройство сетевого интерфейса 822, устройство визуального отображения 810, устройство ввода символов 812 (например, клавиатуру) и устройство ввода в виде сенсорного экрана 814.
[00079] Устройство хранения данных 818 может включать машиночитаемый носитель данных 824, в котором хранится один или более наборов инструкций 826, в которых реализован один или более методов или функций, описанных в данном варианте реализации изобретения. Инструкции 826 во время выполнения их в вычислительной системе 800 также могут находиться полностью или по меньшей мере частично в основном запоминающем устройстве 804 и (или) в процессоре 802, при этом основное запоминающее устройство 804 и процессор 802 также представляют собой машиночитаемый носитель данных. Инструкции 826 дополнительно могут передаваться или приниматься по сети 816 через устройство сетевого интерфейса 822.
[00080] В некоторых вариантах реализации инструкции 826 могут включать в себя команды способа 100 для выполнения OCR серии изображений, содержащих символы текста, как описано выше в этом документе. В то время как машиночитаемый носитель 824, показанный на примере на фиг. 8, является единым носителем, термин «машиночитаемый носитель» должен распространяться на один или более носителей (например, централизованную или распределенную базу данных и (или) соответствующие кэши и серверы), в которых хранятся один или более наборов команд. Термин «машиночитаемый носитель данных» также следует понимать как включающий любой носитель, который может хранить, кодировать или переносить набор команд для выполнения машиной и который обеспечивает выполнение машиной любой одной или более методик настоящего изобретения. Поэтому термин «машиночитаемый носитель данных» относится, помимо прочего, к твердотельным запоминающим устройствам, а также к оптическим и магнитным носителям.
[00081] Способы, компоненты и функции, описанные в этом документе, могут быть реализованы с помощью дискретных компонентов оборудования либо они могут быть встроены в функции других компонентов оборудования, например ASICS (специализированная заказная интегральная схема), FPGA (программируемая логическая интегральная схема), DSP (цифровой сигнальный процессор) или аналогичных устройств. Кроме того, способы, компоненты и функции могут быть реализованы с помощью модулей встроенного программного обеспечения или функциональных схем аппаратного обеспечения. Способы, компоненты и функции также могут быть реализованы с помощью любой комбинации аппаратного обеспечения и программных компонентов либо исключительно с помощью программного обеспечения.
[00082] В приведенном выше описании изложены многочисленные детали. Однако любому специалисту в этой области техники, ознакомившемуся с этим описанием, должно быть очевидно, что настоящее изобретение может быть осуществлено на практике без этих конкретных деталей. В некоторых случаях хорошо известные структуры и устройства показаны в виде блок-схем без детализации, чтобы не усложнять описание настоящего изобретения.
[00083] Некоторые части описания предпочтительных вариантов реализации изобретения представлены в виде алгоритмов и символического представления операций с битами данных в запоминающем устройстве компьютера. Такие описания и представления алгоритмов представляют собой средства, используемые специалистами в области обработки данных, что обеспечивает наиболее эффективную передачу сущности работы другим специалистам в данной области. В контексте настоящего описания, как это и принято, алгоритмом называется логически непротиворечивая последовательность операций, приводящих к желаемому результату. Операции подразумевают действия, требующие физических манипуляций с физическими величинами. Обычно, хотя и необязательно, эти величины принимают форму электрических или магнитных сигналов, которые можно хранить, передавать, комбинировать, сравнивать и выполнять другие манипуляции. Иногда удобно, прежде всего для обычного использования, описывать эти сигналы в виде битов, значений, элементов, символов, терминов, цифр и т.д.
[00084] Однако следует иметь в виду, что все эти и подобные термины должны быть связаны с соответствующими физическими величинами и что они являются лишь удобными обозначениями, применяемыми к этим величинам. Если не указано дополнительно, принимается, что в последующем описании термины «определение», «вычисление», «расчет», «получение», «установление», «изменение» и т.п. относятся к действиям и процессам вычислительной системы или аналогичной электронной вычислительной системы, которая использует и преобразует данные, представленные в виде физических (например, электронных) величин в реестрах и запоминающих устройствах вычислительной системы, в другие данные, аналогично представленные в виде физических величин в запоминающих устройствах или реестрах вычислительной системы или иных устройствах хранения, передачи или отображения такой информации.
[00085] Настоящее изобретение также относится к устройству для выполнения операций, описанных в настоящем документе. Такое устройство может быть специально сконструировано для требуемых целей, либо оно может представлять собой универсальный компьютер, который избирательно приводится в действие или дополнительно настраивается с помощью программы, хранящейся в памяти компьютера. Такая компьютерная программа может храниться на машиночитаемом носителе данных, например, помимо прочего, на диске любого типа, включая дискеты, оптические диски, CD-ROM и магнитно-оптические диски, постоянные запоминающие устройства (ПЗУ), оперативные запоминающие устройства (ОЗУ), СППЗУ, ЭППЗУ, магнитные или оптические карты и носители любого типа, подходящие для хранения электронной информации.
[00086] Следует понимать, что приведенное выше описание призвано иллюстрировать, а не ограничивать сущность изобретения. Специалистам в данной области техники после прочтения и уяснения приведенного выше описания станут очевидны и различные другие варианты реализации изобретения. Исходя из этого область применения изобретения должна определяться с учетом прилагаемой формулы изобретения, а также всех областей применения эквивалентных способов, на которые в равной степени распространяется формула изобретения.