Оптическое распознавание символов серии изображений

Оптическое распознавание символов серии изображений

Иллюстрации

Показать все

Реферат

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

[0001] Настоящее изобретение в общем относится к вычислительным системам, более конкретно к системам и способам оптического распознавания символов (OCR).

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

[0002] Оптическое распознавание символов (OCR) представляет собой осуществляемое на компьютере преобразование изображений текста (включая машинописный, написанный от руки или напечатанный текст) в электронные документы в машинной кодировке.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[0003] В соответствии с одним или более аспектами настоящего раскрытия изобретения описанный в примере способ оптического распознавания символов (OCR) серии изображений с символами некоторого алфавита может включать получение текущего изображения из серии изображений исходного документа, причем текущее изображение хотя бы частично перекрывает предыдущее изображение из серии изображений; выполнение оптического распознавания символов (OCR) текущего изображения для получения распознанного текста и соответствующей ему разметки текста; определение с использованием распознанного текста и соответствующей ему разметки текста множества текстовых артефактов для каждого текущего изображения и предыдущего изображения, причем каждый текстовый артефакт представлен символьной последовательностью, которая обладает частотой встречаемости в распознанном тексте ниже пороговой частоты; определение для каждого текущего и предыдущего изображений соответствующего множества опорных точек, причем каждая опорная точка ассоциируется с по крайней мере одним текстовым артефактом из множества текстовых артефактов; вычисление с использованием координат соответствующих опорных точек текущего и предыдущего изображений параметров преобразования координат предыдущего изображения в координаты текущего изображения; связывание с помощью преобразования координат как минимум части распознанного текста с кластером из множества кластеров символьных последовательностей, причем распознанный текст создается путем обработки текущего изображения, а символьные последовательности создаются путем обработки одного или более ранее полученных изображений из серии изображений; определение для каждого кластера строки-медианы, представляющей кластер символьных последовательностей; и получение с использованием этой строки-медианы итогового распознанного текста, соответствующего хотя бы части исходного документа.

[0004] В соответствии с одним или более аспектами настоящего раскрытия изобретения описанная в примере система оптического распознавания символов (OCR) серии изображений с символами некоторого алфавита может включать память, устройство обработки, подключенное к памяти, причем устройство обработки предназначено для получения текущего изображения из серии изображений исходного документа, причем текущее изображение хотя бы частично перекрывает предыдущее изображение из серии изображений; выполнения оптического распознавания символов (OCR) текущего изображения для получения распознанного текста и соответствующей ему разметки текста; определения с использованием распознанного текста и соответствующей ему разметки текста множества текстовых артефактов для каждого текущего изображения и предыдущего изображения, причем каждый текстовый артефакт представлен символьной последовательностью, которая обладает частотой встречаемости в распознанном тексте ниже пороговой частоты; определения для каждого текущего и предыдущего изображений соответствующего множества опорных точек, причем каждая опорная точка ассоциируется с по крайней мере одним текстовым артефактом из множества текстовых артефактов; вычисления с использованием координат соответствующих опорных точек текущего и предыдущего изображений параметров преобразования координат предыдущего изображения в координаты текущего изображения; связывания с помощью преобразования координат как минимум части распознанного текста с кластером из множества кластеров символьных последовательностей, причем распознанный текст создается путем обработки текущего изображения, а символьные последовательности создаются путем обработки одного или более ранее полученных изображений из серии изображений; определения для каждого кластера строки-медианы, представляющей кластер символьных последовательностей; и получения с использованием этой строки-медианы итогового распознанного текста, соответствующего хотя бы части исходного документа.

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

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

[0006] Настоящее изобретение иллюстрируется с помощью примеров, но не ограничивается только ими, и может быть лучше понято при рассмотрении приведенного ниже описания предпочтительных вариантов реализации в сочетании с чертежами, в которых:

[0007] На Фиг. 1 показана блок-схема одного иллюстративного примера способа выполнения оптического распознавания символов (OCR) серии изображений, содержащих текстовые символы, в соответствии с одним или более аспектами настоящего изобретения;

[0008] На Фиг. 2А-2В схематически показана фильтрация обнаруженных опорных точек с помощью инвариантных геометрических признаков группировок опорных точек в соответствии с одним или более аспектами настоящего изобретения;

[0009] На Фиг. 3 схематически показан пример обхода векторов, соединяющих случайно выбранную точку (например, начало координат координатной плоскости, связанной с изображением) и каждую из опорных точек в порядке их числовых обозначений, в соответствии с одним или более аспектами настоящего изобретения;

[00010] На Фиг. 4 схематически показан пример топологии геометрических фигур, образованных линиями, соединяющими случайно выбранный набор опорных точек, в соответствии с одним или более аспектами настоящего изобретения;

[00011] На Фиг. 5А-5В схематически показан пример серии из трех изображений, проективное преобразование между парами изображений и соответствующие символьные последовательности, полученные при оптическом распознавании соответствующих изображений, в соответствии с одним или более аспектами настоящего изобретения;

[00012] На Фиг. 6 схематически показан пример графа, состоящего из множества кластеров вершин, где каждый кластер представляет две или более совпадающих символьных последовательностей, в соответствии с одним или более аспектами настоящего изобретения;

[00013] На Фиг. 7А-7С схематически показано определение строки-медианы среди множества символьных последовательностей, представляющих результаты оптического распознавания символов соответствующих фрагментов изображений, в соответствии с одним или более аспектами настоящего изобретения; а также

[00014] На Фиг. 8 приведена схема иллюстративного примера вычислительной системы, в которой реализованы способы настоящего изобретения.

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

[00015] В настоящем документе описываются способы и системы для оптического распознавания символов (OCR) серии изображений с символами некоторого алфавита. Алфавиты, символы которых могут обрабатываться с помощью систем и способов, описанных в настоящем документе, включают истинные символьные алфавиты, которые содержат отдельные символы или глифы, соответствующие отдельным звукам, а также иероглифические алфавиты, которые содержат отдельные символы, соответствующие более крупным блокам, таким как слоги или слова.

[00016] В приведенном ниже описании термин «документ» должен толковаться широко, как отсылка к разнообразным типам текстовых носителей, включая, помимо прочего, печатные и написанные от руки документы, баннеры, постеры, знаки, рекламные щиты и (или) другие физические объекты, несущие видимые текстовые символы на одной или более поверхностях. «Изображение документа» в настоящем документе означает изображение как минимум части исходного документа (например, страницы бумажного документа).

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

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

[00019] В некоторых вариантах реализации изобретения текст, полученный системами и способами оптического распознавания, описанными в этом документе, может быть дополнительно обработан, например, способами машинного перевода, для перевода исходного текста на другой естественный язык.

[00020] В иллюстративном примере компьютерная система, реализующая способ, описанный в этом документе, может получать серию изображений (например, серию видеокадров или фотоснимков) исходного документа. Эти изображения могут отображать как минимум частично перекрывающиеся фрагменты документа и могут отличаться масштабом изображения, ракурсом, выдержкой, диафрагмой, яркостью изображения, наличием бликов, наличием внешних объектов, которые как минимум частично закрывают исходный текст, и (или) других элементов изображения, визуальных артефактов и параметров способа получения изображения.

[00021] Эта компьютерная система может выполнять оптическое распознавание символов как минимум выбранных изображений полученной серии изображений для получения соответствующей информации о тексте и его разметки. Информация о разметке может связывать распознаваемые символы и (или) группы символов с их положением на исходном изображении. Для объединения результатов распознавания символов, выполняемого для последовательно полученных изображений, компьютерная система может сравнивать текст и разметку, полученные при оптическом распознавании текущего изображения с текстом и разметкой, полученными при оптическом распознавании одного или более ранее обработанных изображений.

[00022] В соответствии с одним или более аспектами настоящего изобретения компьютерная система может сопоставлять текстовые артефакты в результатах оптического распознавания символов, соответствующих паре изображений (например, паре следующих друг за другом кадров в серии изображений), с целью определения опорных точек для построения взаимного преобразования координат изображений, где каждое преобразование координат пересчитывает координаты предыдущего изображения в координаты следующего за ним изображения из пары изображений, что будет более подробно описано ниже. Текстовые артефакты, которые используются для определения опорных точек, могут быть представлены символьными последовательностями (например, словами), имеющими низкую частоту встречаемости в тексте, полученном в результате оптического распознавания символов (например, частоту, которая не превышает определенный порог).

[00023] Информация о разметке, связанная с обнаруженными текстовыми артефактами, позволяет определить как минимум одну опорную точку, соответствующую каждому текстовому артефакту в каждой паре изображений. В иллюстративном примере опорная точка может соответствовать центру и (или) углам минимального описывающего прямоугольника уникальной или редко встречающейся символьной последовательности.

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

[00025] Для каждого кластера совпадающих символьных последовательностей может быть определена строка-медиана, представляющая результат оптического распознавания символов соответствующего фрагмента изображения. В некоторых вариантах реализации изобретения строка-медиана может быть определена как символьная последовательность, имеющая минимальную сумму расстояний редактирования до всех символьных последовательностей кластера. Расстояние редактирования, которое в иллюстративном примере может быть представлено расстоянием Левенштейна, между первой символьной последовательностью и второй символьной последовательностью может быть равно минимальному числу односимвольных преобразований (т.е. вставок, удалений или замещений), необходимых для преобразования первой символьной последовательности во вторую символьную последовательность.

[00026] Тексты, полученные в результате оптического распознавания символов каждого отдельного изображения, могут отличаться одним или более словами, присутствующими или отсутствующими в каждом результате оптического распознавания символов, вариациями в символьных последовательностях, соответствующих словам исходного текста, и (или) порядком символьных последовательностей. Для восстановления правильного порядка символьных последовательностей исходного документа можно проанализировать множество перестановок символьных последовательностей, которые соответствуют обнаруженным кластерам, для определения медианы, которая имеет минимальную сумму тау-расстояний Кенделла до всех прочих перестановок. Тау-расстояние Кенделла между первой и второй перестановками может быть равно минимальному количеству операций по обмену, необходимых для алгоритма пузырьковой сортировки для преобразования первой перестановки во вторую перестановку.

[00027] Различные аспекты упомянутых выше способов и систем подробно описаны ниже в этом документе с помощью примеров, но не ограничиваются только ими.

[00028] На Фиг. 1 показана блок-схема одного иллюстративного примера способа 100 выполнения оптического распознавания серии изображений, содержащих текстовые символы, в соответствии с одним или более аспектами настоящего изобретения. Способ 100 и (или) каждая из его отдельных функций, стандартных программ, подпрограмм или операций может выполняться с помощью одного или более процессоров компьютерного устройства (например, примера вычислительной системы 800 на Фиг. 8), в котором реализован этот способ. В некоторых вариантах реализации изобретения способ 100 может выполняться в одном потоке обработки. Кроме того, способ 100 может выполняться, используя два или более потоков обработки, причем каждый поток выполняет одну или более отдельных функций, процедур, подпрограмм или операций способа. В иллюстративном примере потоки обработки, в которых реализован способ 100, могут быть синхронизированы (например, с использованием семафоров, критических секций и (или) других механизмов синхронизации потоков). Кроме того, потоки обработки, реализующие способ 100, могут выполняться асинхронно друг относительно друга. Таким образом, в то время как Фиг. 1 и соответствующее описание содержат операции по способу 100 в определенном порядке, различные реализации способа могут выполнять как минимум некоторые из указанных операций параллельно и (или) в случайно выбранном порядке.

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

[00030] Настоящее раскрытие изобретения ссылается на «пару изображений» из серии изображений (например, серии видеокадров или фотоснимков) исходного документа. Эти изображения могут отображать как минимум частично перекрывающиеся фрагменты документа и могут отличаться масштабом изображения, ракурсом, выдержкой, диафрагмой, яркостью изображения, наличием бликов, наличием внешних объектов, которые как минимум частично закрывают исходный текст, и (или) других элементов изображения, визуальных артефактов и параметров способа получения изображения. В иллюстративном примере пара изображений может выбираться из двух или более следующих друг за другом изображений из полученной серии изображений. В этом документе два изображения по отдельности указываются как «текущее изображение» (также обозначенное как «i-тое изображение» на Фиг. 1) и «предыдущее изображение» (также обозначенное как «(i-1)-тое изображение» на Фиг. 1).

[00031] В блоке 110 компьютерная система реализует способ, позволяющий получить текущее изображение из серии изображений.

[00032] В блоке 115 компьютерная система может выполнить оптическое распознавание символов текущего изображения с получением распознанного текста и информации о разметке. Информация о разметке может связывать распознанные символы и (или) группы символов с их положением на исходном изображении.

[00033] В блоке 120 компьютерная система может идентифицировать совпадающие текстовые артефакты в результатах оптического распознавания символов пары изображений. Текстовые артефакты могут быть представлены в виде символьной последовательности (например, слов), имеющей низкую частоту встречаемости в тексте, полученном в результате оптического распознавания символов (например, частоту, не превышающую определенный порог, который может быть установлен равным 1 для указания на уникальную символьную последовательность). В иллюстративном примере редко встречающееся слово может быть обнаружено путем сортировки слов, полученных в результате оптического распознавания символов, по их частоте и выбора слова, имеющего минимальную частоту встречаемости. В некоторых вариантах реализации изобретения в способе могут использоваться только символьные последовательности, относительная длина которых превышает определенную минимальную длину, поскольку более короткие символьные последовательности дают менее надежные опорные точки.

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

[00035] В блоке 130 вычислительная система может проверять обнаруженные опорные точки и исключать как минимум некоторые из них, принимая во внимание выбранный критерий фильтрации. В иллюстративном примере компьютерная вычислительная система может проверять, что случайно выбранные группы совпадающих опорных точек демонстрируют определенные геометрические признаки, которые инвариантны относительно выбранных изображений. Как схематически показано на Фиг. 2А-2В, такой инвариантный геометрический признак может быть представлен направлением обхода как минимум трех совпадающих опорных точек. В примере на Фиг. 2А три редко встречающихся слова («distance», «core» и «method») используются для получения соответствующих опорных точек 1, 2 и 3. Центры минимальных описывающих прямоугольников, соответствующих символьный последовательностей каждого из изображений документов, позволяют получить прямоугольники 102 и 104. В примере на Фиг. 2А на каждом из двух изображений направление обхода треугольников по опорным точкам в порядке их числовых обозначений остается одинаковым (по часовой стрелке), и поэтому опорные точки 1, 2 и 3, вероятно, соответствуют совпадающим символьным последовательностям на двух изображениях, а значит, могут быть использованы для выполнения последующих операций способа.

[00036] И наоборот, в примере на Фиг. 2В для прямоугольника 106, соответствующего первому изображению документа, обход треугольников по опорным точкам в порядке их числовых обозначений производится по часовой стрелке, а для прямоугольника 108, соответствующего второму изображению документа, обход треугольников по опорным точкам в порядке их числовых обозначений производится против часовой стрелки, поэтому опорные точки 1, 2 и 3, вероятно, соответствуют различным символьным последовательностям на двух изображениях, а значит, должны быть исключены.

[00037] Как схематически показано на Фиг. 3, дополнительный или альтернативный инвариантный геометрический признак может быть представлен направлением обхода векторов, соединяющих случайно выбранную точку (например, начало координат координатной плоскости, связанной с изображением) и каждую из опорных точек в порядке их числовых обозначений. Как схематически показано на Фиг. 4, дополнительный или альтернативный инвариантный геометрический признак может быть представлен топологией геометрических фигур, образованных линиями, соединяющими случайно выбранный набор опорных точек.

[00038] В различных вариантах реализации изобретения можно использовать альтернативные способы определения признаков изображений, формирования опорных точек и (или) фильтрации опорных точек.

[00039] Рассмотрим снова Фиг. 1: в блоке 135 вычислительная система может строить преобразование координат, преобразуя координаты одного изображения из пары изображений в координаты другого изображения из пары изображений. Предложенный способ предполагает, что как минимум для выбранной пары изображений координаты случайно выбранной точки первого изображения можно получить, применив проективное преобразование к координатам той же точки второго изображения.

[00040] «Проективное преобразование» в этом документе означает преобразование, отображающее линии на линии, но не обязательно сохраняющее параллельность. Проективное преобразование может быть выражено следующими уравнениями:

где (х,у) и (X,Y) - координаты случайно выбранной точки на первом и втором изображениях соответственно. Коэффициенты преобразования Ax₁, Ах₂, Ах₃, Ах₄, Ay₁, Ау₂, Ау₃ и Ау₄ могут быть вычислены исходя из известных координат как минимум четырех опорных точек на каждом из двух изображений, что позволит получить систему из восьми уравнений с восемью переменными. После вычисления коэффициентов преобразования уравнений (1) и (2) можно применить к координатам случайно выбранных точек первого изображения и вычислить координаты той же самой точки на втором изображении.

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

[00042] На Фиг. 5А схематически показана серия из трех изображений (402, 404 и 406), где координаты первого изображения 402 могут быть преобразованы в координаты второго изображения 404 путем применения проективного преобразования 408, а координаты второго изображения 404 могут быть преобразованы в координаты третьего изображения 406 путем применения проективного преобразования 410.

[00043] Вернемся снова к Фиг. 1: в блоке 140 вычислительная система может ассоциировать одну или более символьных последовательностей, полученных в результате оптического распознавания символов текущего изображения, с кластером совпадающих символьных последовательностей, полученных в результате оптического распознавания символов ранее обработанных изображений. Вычислительная система может использовать указанные ранее преобразования координат для сравнения положения распознанных символьных последовательностей на текущем и предыдущих изображениях и распознавать таким образом группы символьных последовательностей, которые, вероятно, соответствуют одному и тому же фрагменту исходного документа.

[00044] В иллюстративном примере для случайно выбранных символьных последовательностей в тексте, полученном в результате оптического распознавания символов текущего изображения, этот способ может обнаруживать одну или более совпадающих символьных последовательностей, полученных при оптическом распознавании символов других изображений из серии изображений. Отметим, что «совпадающие символьные последовательности» в этом документе обозначают как точно совпадающие, так и приблизительно совпадающие символьные последовательности. В иллюстративном примере на Фиг. 5В три совпадающие символьные последовательности 412, соответствующие изображениям 402, 404 и 406, представляют собой три разные серии, которые приблизительно совпадают в результате применения способов, описанных в этом документе.

[00045] В некоторых вариантах реализации изобретения компьютерная система может создавать граф, вершины которого представляют символьные последовательности из множества изображений, а ребра соединяют символьные последовательности, которые были определены как совпадающие (то есть соответствующие одному и тому же фрагменту исходного текста) путем применения описанного выше взаимного преобразования координат изображений. Как схематически показано на Фиг. 6, полученный граф будет содержать множество кластеров вершин, где каждый кластер соответствует двум или более совпадающим символьным последовательностям. Вершины внутри каждого кластера соединены соответствующими ребрами, причем отдельные кластеры могут быть изолированы или слабо связаны друг с другом. На Фиг. 6 показаны два кластера (602, 604), соответствующие символьным последовательностям, полученным при оптическом распознавании двух исходных строк: «the core» и «method».

[00046] Еще раз рассмотрим Фиг. 1: в блоке 145 вычислительная система может увеличивать значение счетчика, указывающее на текущее изображение в серии изображений. Отметим, что операции в блоке 145 представлены на Фиг. 1 для улучшения читаемости соответствующего описания и во многих реализациях способа могут быть удалены.

[00047] В блоке 150 вычислительная система может определить, существует ли следующее изображение серии; если это так, способ может вернуться к блоку 110.

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

[00049] Как схематически показано на Фиг. 7А, каждый кластер 702 может содержать множество совпадающих символьных последовательностей 704, а результат оптического распознавания символов соответствующего фрагмента изображения может быть представлен строкой-медианой 706. В некоторых вариантах реализации изобретения строка-медиана может быть определена как символьная последовательность, имеющая минимальную сумму расстояний редактирования до всех символьных последовательностей кластера. Расстояние редактирования, которое в иллюстративном примере может быть представлено расстоянием Левенштейна, между первой символьной последовательностью и второй символьной последовательностью может быть равно минимальному числу односимвольных преобразований (т.е. вставок, удалений или замещений), необходимых для преобразования первой символьной последовательности во вторую символьную последовательность.

[00050] В некоторых вариантах реализации изобретения вычислительная сложность определения строки-медианы может быть уменьшена путем применения некоторых эвристических способов. В иллюстративном примере компьютерная система может эвристически определять аппроксимацию строки-медианы нулевого порядка. Затем компьютерная система может выравнивать символьные последовательности, используя точно совпадающие символы каждой последовательности, как схематично показано на Фиг. 7В. В другом иллюстративном примере вычислительная система может связывать с каждой символьной последовательностью кластера весовой коэффициент, отражающий положение символьной последовательности в изображении или величину уверенности оптического распознавания символов. Как схематично показано на Фиг. 7С, кластер 712 содержит четыре символьных последовательности: ТОР, ТОР, TORRENT, TORRENT. Первые две символьные последовательности соответствуют частям слов, поскольку расстояние от границы минимального описывающего прямоугольника символьной последовательности до границы изображения меньше ширины пробела. Поэтому значение показателя уверенности оптического распознавания символов для первых двух символьных последовательностей значительно ниже значения показателя уверенности оптического распознавания символов для двух других символьных последовательностей, и в качестве строки-медианы способ, принимающий во внимание значение показателя уверенности оптического распознавания символов, выберет символьную последовательность TORRENT.

[00051] Обратимся еще раз к Фиг. 1: в блоке 160 вычислительная система может определить порядок, в котором символьные последовательности, представляющие вышеуказанные кластеры, должны следовать в итоговом тексте. Как было указано выше в этом документе, изображения, соответствующие исходному документу, могут отображать как минимум частично перекрывающиеся фрагменты документа и могут отличаться масштабом изображения, ракурсом, выдержкой, диафрагмой, яркостью изображения, наличием бликов, наличием внешних объектов, которые как минимум частично закрывают исходный текст, и (или) других элементов изображения, визуальных артефактов и параметров способа получения изображения. Поэтому тексты, полученные в результате оптического распознавания символов каждого отдельного изображения, могут отличаться одним или более словами, присутствующими или отсутствующими в отдельных результатах оптического распознавания символов, вариациями символьных последовательностей, соответствующих словам исходного текста, и (или) порядком символьных последовательностей, как схематично показано на Фиг. 5В.

[00052] В некоторых вариантах реализации изобретения вычислительная система может сравнивать множество перестановок символьных последовательностей, которые представляют обнаруженные кластеры. Медианная перестановка может быть определена как перестановка, имеющая минимальную сумму тау-расстояний Кенделла до всех прочих перестановок. Тау-расстояние Кенделла между первой и второй перестановками может быть равно минимальному количеству операций перестановки, необходимых для алгоритма пузырьковой сортировки для преобразования первой перестановки во вторую перестановку символов. В указанном выше иллюстративном примере на Фиг. 5В медианная перестановка представлена последовательностью ABCD.

[00053] Как указывалось выше в этом документе, исходный документ невозможно вместить в одно изображение без значительных потерь качества изображения. Риск потери качества изображения может быть сокращен путем получения последовательности частично перекрывающихся изображений различных фрагментов исходного документа, которые тем не менее нельзя будет использовать для последующего проведения распознавания обычными способами оптического распознавания. Описанная выше операция определения медианной перестановки может быть использована для объединения результатов распознавания символов, выполненного для нескольких фрагментов документа, то есть для эффективного «сшивания» результатов оптического распознавания символов отдельных изображений для получения текста исходного документа.

[00054] В различных вариантах реализации изобретения операции, описанные в блоках 155 и 160, могут выполняться в обратной последовательности или параллельно. Кроме того, в некоторых вариантах реализации изобретения определенные операции, описанные в блоках 155 и (или) 160, могут быть пропущены.

[00055] Обратимся еще раз к Фиг. 1: в блоке 165 вычислительная система может использовать упорядочивание символьных последовательностей, представляющие вышеуказанные кластеры, для получения итогового текста исходного документа.

[00056] Как было указано выше в этом документе, текст, полученный системами и способами оптического распознавания символов, опи