СПОСОБ И СИСТЕМА ЭФФЕКТИВНОЙ ПОДГОТОВКИ СОДЕРЖАЩИХ ТЕКСТ ИЗОБРАЖЕНИЙ К ОПТИЧЕСКОМУ РАСПОЗНАВАНИЮ СИМВОЛОВ
METHOD AND SYSTEM OF PREPARING TEXT-CONTAINING IMAGES TO OPTICAL RECOGNITION OF SYMBOLS

ОБЛАСТЬ ТЕХНИКИ
Настоящий документ относится к обработке изображений и оптическому распознаванию символов и, в частности, к способу и системе, позволяющим выпрямлять искажения, вызванные искривленной поверхностью страницы, и перспективные искажения в содержащих текст изображениях при подготовке к применению способов автоматизированного оптического распознавания символов на содержащих текст изображениях.
УРОВЕНЬ ТЕХНИКИ
Печатные документы на естественном языке до сих пор являются широко распространенным средством, используемым для коммуникации между людьми в рамках организаций, а также для распространения информации среди ее потребителей. С появлением повсеместно используемых мощных вычислительных ресурсов, включая персональные вычислительные ресурсы, реализованные в смартфонах, планшетах, ноутбуках и персональных компьютерах, а также с распространением более мощных вычислительных ресурсов облачных вычислительных сервисов, центров обработки данных и корпоративных серверов организаций и предприятий, шифрование и обмен информацией на естественном языке все чаще выполняется в виде электронных документов. В отличие от печатных документов, которые по своей сути представляют собой изображения, электронные документы содержат последовательности цифровых кодов символов и знаков естественного языка. Поскольку электронные документы имеют перед печатными документами преимущества по стоимости, возможностям передачи и рассылки, простоте редактирования и изменения, а также по надежности хранения, за последние 50 лет развилась целая отрасль, поддерживающая способы и системы преобразования печатных документов в электронные. Вычислительные способы и системы оптического распознавания символов, совместно с электронными сканерами, являются надежными и экономичными средствами получения изображений печатных документов и компьютерной обработки получаемых цифровых изображений содержащих текст документов с целью создания электронных документов, соответствующих печатным.
Раньше электронные сканеры представляли собой крупногабаритные настольные или напольные электронные устройства. Однако с появлением смартфонов, оснащенных камерами, а также других мобильных устройств получения изображения с процессорным управлением, появилась возможность получения цифровых изображений содержащих текст документов с помощью широкого диапазона различных типов широко распространенных портативных устройств, включая смартфоны, недорогие цифровые камеры, недорогие камеры видеонаблюдения, а также устройства получения изображений, встроенные в мобильные вычислительные приборы, включая планшетные компьютеры и ноутбуки. Получаемые при помощи таких портативных устройств и приборов цифровые изображения, содержащие текст документов, могут обрабатываться вычислительными системами оптического распознавания символов, в том числе приложениями оптического распознавания символов в смартфонах, для создания соответствующих электронных документов.
К сожалению, содержащие текст изображения, полученные с помощью портативных средств получения изображений документов, часто бывают искажены наличием шума, оптического размытия, искривлений линейных текстовых строк, вызванных изогнутой поверхностью страниц и перспективным искажением, а также другими дефектами и недостатками. Даже изображения, полученные с помощью специальных устройств сканирования документов, могут содержать перспективные искажения текстовых строк, когда книга при сканировании раскрывается и кладется лицевой стороной вниз на прозрачную сканирующую поверхность. Эти дефекты и недостатки могут значительно снизить производительность вычислительного оптического распознавания символов и значительно увеличить частоту ошибочного распознавания символов и неспособности способов и систем оптического распознавания символов обеспечить точное кодирование текста, содержащегося на цифровых изображениях. По этой причине проектировщики и разработчики устройств и приборов получения изображений, способов и систем оптического распознавания символов, а также пользователи данных устройств, приборов и систем оптического распознавания символов, продолжают искать способы и системы, позволяющие устранить дефекты и недостатки, присущие многим содержащим текст цифровым изображениям (включая содержащие текст цифровые изображения, полученные с помощью мобильных устройств), которые затрудняют дальнейшую вычислительную обработку содержащих текст цифровых изображений.
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
Настоящий документ относится к способам и системам выпрямления искривлений текстовых строк содержащих текст цифровых изображений, включая содержащие текст цифровые изображения, полученные из двух страниц раскрытой книги. При первоначальной обработке содержащего текст изображения определяется контур содержащей текст страницы. Далее создаются контуры, соответствующие каждой строке текста. Определяются центроиды и углы наклона звеньев или векторов, которые соответствуют линиям контуров. Строится модель для перспективного искажения в изображении текста. В одном из вариантов реализации модель, которая по сути является картой углов наклона, позволяет присваивать пикселям на изображении страницы значения локального смещения, которые затем используются для выпрямления строк текста в содержащем текст изображении. В другом варианте реализации модель, которая по сути является картой смещения пикселей, используется для выпрямления строк текста в содержащем текст изображении.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
На Фиг. 1 показана высокоуровневая архитектурная схема вычислительной системы, в которой для исправления перспективного искажения текстовой строки применяется способ настоящего изобретения.
На Фиг. 2A-D показаны два различных типа портативных устройств получения изображений.
На Фиг. 3 показано типовое изображение с цифровым кодированием.
На Фиг. 4 показан один вариант цветовой модели RGB.
На Фиг. 5 показана другая цветовая модель, называемая цветовой моделью "оттенок-насыщенность-светлота" (HSL).
На Фиг. 6 изображено формирование полутонового или бинаризованного изображения из цветного.
На Фиг. 7 показано дискретное вычисление градиента яркости.
На Фиг. 8 показан градиент, рассчитанный для некой точки на непрерывной поверхности.
На Фиг. 9 показан ряд примеров градиента яркости.
На Фиг. 10 показано применение ядра к изображению.
На Фиг. 11 показана свертка ядра с изображением для получения преобразованного изображения.
На Фиг. 12 показан пример ядра и методик обработки изображений на основе ядра.
На Фиг. 13А-В показан один вариант реализации способа, к которому относится настоящий документ.
На Фиг. 14A-D показана первоначальная обработка изображения страницы с целью подготовки к выравниванию вертикальных границ страницы, как описано выше со ссылкой на Фиг. 13В.
На Фиг. 15А-В показан один подход к выравниванию границ страницы, который описан выше со ссылкой на Фиг. 13В.
На Фиг. 16A-D показан один из подходов к определению ориентации строк текста на изображении страницы, или, протекающего аналогичным образом, определения угловой ориентации изображения страницы, при котором строки текста будут горизонтальны.
На Фиг. 17A-D показаны морфологические операции, которые использовались в некоторых вариантах реализации для создания на бинаризованной карте однородных полос пикселей, соответствующих строкам текста.
На Фиг. 18А-С показано создание линий контура.
На Фиг. 19А-В показано формирование модели искривления текстовых строк на изображении страницы.
На Фиг. 20 показан альтернативный способ согласования данных, который преобразует извлеченные исходные данные об искривлении, сведенные в таблицу 1912 на Фиг. 19А, в полиномиальную функцию.
На Фиг. 21-24 показано формирование контуров для текстовых строк, указанное на Фиг. 18А как шаг 1809.
На Фиг. 25 показаны особенно сильно искривленные области изображений страниц и вычисление коэффициентов корректировки.
На Фиг. 26A-F показано выпрямление изогнутых текстовых строк на изображении страницы для получения прямолинейных текстовых строк с использованием карты углов наклона, в которой с каждым пикселем на изображении страницы соотнесен некий угол наклона.
На Фиг. 26G показан альтернативный способ выпрямления текстовых строк на изображении страницы.
На Фиг. 27A-U представлены блок-схемы, иллюстрирующие один из вариантов реализации способа исправления перспективного искажения текстовых строк на изображениях текста, снятых мобильными устройствами и другими видами оборудования, приборами получения содержащего текст изображения.
ПОДРОБНОЕ ОПИСАНИЕ
Настоящий документ относится к способам и системам, позволяющим выпрямлять искривленные строки текста на содержащих текст изображениях при подготовке содержащих текст изображений к точному оптическому распознаванию символов. В первом подразделе ниже со ссылкой на Фиг. 1-12 приводится краткое введение в архитектуру вычислительной системы, цифровые изображения и способы обработки цифровых изображений. Во втором подразделе со ссылкой на Фиг. 13А-26G приводится подробное описание способов и систем настоящего изобретения. В заключительном подразделе со ссылкой на Фиг. 27A-U с помощью блок-схем иллюстрируется один из вариантов реализации способа настоящего изобретения.
Обзор архитектуры вычислительной системы, цифровых изображений и способов обработки цифровых изображений
На Фиг. 1 показана высокоуровневая схема архитектуры вычислительной системы, такой как вычислительная система, в которой для исправления искривления текстовой строки, вызванного искажением перспективы, применяется способ настоящего изобретения. Мобильные устройства получения изображений, включая смартфоны и цифровые камеры, могут быть представлены схематически аналогичным образом и также могут содержать процессоры, память и внутренние шины. Тем, кто знаком с современной наукой и технологиями, будет понятно, что программы управления или подпрограмма управления, включающая команды в машинном коде, которые хранятся в физической памяти устройства с процессорным управлением, представляют собой компонент управления данным устройством и являются настолько же физическими, реальными и важными, насколько и любой другой компонент электромеханического устройства, включая устройства получения изображений. Компьютерная система содержит один или более центральных процессоров (ЦП) 102-105, один или более электронных модулей памяти 108, взаимосвязанных с ЦП через шину подсистемы ЦП/память 110 или несколько шин, первый мост 112, который соединяет шину подсистемы ЦП/память 110 с дополнительными шинами 114 и 116, либо другие виды средств высокоскоростного соединения, в том числе множественные высокоскоростные последовательные соединения. Данные шины или последовательные межсоединения в свою очередь соединяют ЦП и память со специализированными процессорами, такими как графический процессор 118, и с одним или более мостами 120, которые соединены по высокоскоростным последовательным каналам или несколькими контроллерами 122-127, такими как контроллер 127, которые предоставляют доступ к всевозможным видам съемных накопителей 128, электронных дисплеев, устройств ввода и прочих подобных компонентов, подкомпонентов и вычислительных ресурсов.
На Фиг. 2A-D показаны два различных типа портативных устройств получения изображения. На Фиг. 2А-С показана цифровая камера 202. Цифровая камера содержит объектив 204, кнопку спуска затвора 205, нажатие которой пользователем приводит к получению цифрового изображения, которое соответствует отраженному свету, поступающему в объектив 204 цифровой камеры. С задней стороны цифровой камеры, которая видна пользователю, когда он держит камеру при съемке цифровых изображений, находится видоискатель 206 и жидкокристаллический дисплей видоискателя 208. С помощью видоискателя 206 пользователь может напрямую просматривать создаваемое объективом 204 камеры изображение, а с помощью жидкокристаллического дисплея 208 - просматривать электронное отображение создаваемого в настоящей момент объективом изображения. Обычно пользователь камеры настраивает фокус камеры с помощью кольца фокусировки 210, смотря при этом через видоискатель 206 или на жидкокристаллический экран видоискателя 208, чтобы выбрать требуемое изображение перед тем, как нажать на кнопку 205 спуска затвора для получения цифрового снимка изображения и его сохранения в электронной памяти цифровой камеры.
На Фиг. 2D показан типовой смартфон с передней стороны 220 и задней стороны 222. На задней стороне 222 имеется объектив 224 цифровой камеры и датчик приближения и(или) цифровой экспонометр 226. На передней стороне смартфона 220 под управлением приложения может отображаться получаемое изображение 226, аналогично работе жидкокристаллического дисплея 208 видоискателя цифровой камеры, а также сенсорная кнопка 228 спуска затвора, при прикосновении к которой происходит получение цифрового изображения и сохранение его в памяти смартфона.
На Фиг. 3 показано типовое изображение с цифровым кодированием. Кодированное изображение включает двумерный массив пикселей 302. На Фиг. 3 каждый небольшой квадрат, например, квадрат 304, является пикселем, который обычно определяется как наименьшая часть детализации изображения, для которой предусматривается цифровая кодировка. Каждый пиксель представляет собой место, обычно представленное парой цифровых значений, соответствующих значениям на осях прямоугольной системы координат х и у, 306 и 308 соответственно. Таким образом, например, пиксель 304 имеет координаты х, у (39,0), а пиксель 312 - координаты (0,0). Оси выбираются произвольно. Оси х и у могут быть взаимозаменены, например, в соответствии с другим правилом. В цифровой кодировке пиксель представлен числовыми значениями, указывающими на то, как область изображения, соответствующая пикселю, представляется при печати, отображается на экране компьютера или ином дисплее. Обычно для черно-белых изображений для представления каждого пикселя используется единичное значение в интервале от 0 до 255 с числовым значением, соответствующем уровню серого, на котором передается пиксель. Согласно общепринятому правилу значение «0» соответствует черному цвету, а значение «255» - белому. Для цветных изображений может применяться любое из множества различных числовых значений, указывающих на цвет. В одной из стандартных цветовых моделей, показанной на Фиг. 3, каждый пиксель связан с тремя значениями или координатами (r,g,b), которые указывают на яркость красного, зеленого и синего компонента цвета, отображаемого в соответствующей пикселю области.
На Фиг. 4 показан один из вариантов цветовой модели RGB. Тремя координатами основных цветов (r,g,b) представлен весь спектр цветов, как было показано выше со ссылкой на Фиг. 3. Цветовая модель может считаться соответствующей точкам в пределах единичного куба 402, в котором трехмерное цветовое пространство определяется тремя осями координат: (1) r 404; (2) g 406; и (3) b 408. Таким образом, координаты отдельного цвета находятся в интервале от 0 до 1 по каждой из трех цветовых осей. Например, чистый синий цвет максимально возможной яркости соответствует точке 410 по оси b с координатами (0,0,1). Белый цвет соответствует точке 412 с координатами (1,1,1), а черный цвет - точке 414, началу системы координат с координатами (0,0,0).
На Фиг. 5 показана другая цветовая модель, называемая цветовой моделью «оттенок-насыщенность-светлота» (HSL). В этой цветовой модели цвета содержатся в трехмерной бипирамидальной призме 500 с шестигранным сечением. Оттенок (h) связан с доминантной длиной волны излучения света, воспринимаемого наблюдателем. Значение оттенка находится в интервале от 0° до 360°, начиная с красного цвета 502 в точке 0°, проходя через зеленый 504 в точке 120°, синий 506 в точке 240°, и заканчивая красным 502 в точке 660°. Насыщенность (s), находящаяся в интервале от 0 до 1, обратно связана с количеством белого и черного цвета, смешанного при определенной длине волны или оттенке. Например, чистый красный цвет 502 является полностью насыщенным при насыщенности s=1,0, в то же время розовый цвет имеет насыщенность менее 1,0, но более 0,0, белый цвет 508 является полностью ненасыщенным с s=0,0, а черный цвет 510 также является полностью ненасыщенным с s=0,0. Полностью насыщенные цвета находятся на периметре среднего шестигранника, содержащего точки 502, 504 и 506. Шкала оттенков серого проходит от черного 510 до белого 508 по центральной вертикальной оси 512, представляющей полностью ненасыщенные цвета без оттенка, но с различными пропорциями черного и белого. Например, черный 510 содержит 100% черного и не содержит белого, белый 508 содержит 100% белого и не содержит черного, а исходная точка 513 содержит 50% черного и 50% белого. Светлота , представленная центральной вертикальной осью 512, указывает на уровень освещенности в интервале от 0 для черного 510, при , до 1 для белого 508, при . Для произвольного цвета, представленного на Фиг. 5 точкой 514, оттенок определяется как угол θ 516, между первым вектором из исходной точки 513 к точке 502 и вторым вектором из исходной точки 513 к точке 520, в которой вертикальная линия 522, проходящая через точку 514, пересекает плоскость 524, включающую исходную точку 513 и точки 502, 504 и 506. Насыщенность представлена отношением расстояния представленной точки 514 от вертикальной оси 512 d' к длине горизонтальной линии, проходящей через точку 520 от исходной точки 513 к поверхности бипирамидальной призмы 500, d. Светлота представлена вертикальным расстоянием от контрольной точки 514 до вертикального уровня точки 510, представляющей черный цвет. Координаты конкретного цвета в цветовой модели HSL  могут быть получены на основе координат цвета в цветовой модели RGB (r,g,b) следующим образом:
,
, и
,
max
min
max
min
где значения r, g и b соответствуют яркости красного, зеленого и синего первичных цветов, нормализованных на интервале [0, 1]; C представляет нормализованное значение яркости, равное максимальному значению из r, g и b; C представляет собой нормализованное значение яркости, равное минимальному значению из r, g и b; а Δ определяется как C-C.
На Фиг. 6 изображено формирование полутонового или бинаризованного изображения из цветного изображения. В цветном изображении каждый пиксель обычно связан с тремя значениями: а, b и с 602. В разных цветовых моделях для представления конкретного цвета используются разные значения а, b и с. Полутоновое изображение содержит для каждого пикселя только одно значение яркости 604. Бинаризованное изображение является частным случаем полутонового изображения, которое имеет только два значения яркости «0» и «1». Обычно полутоновые изображения могут иметь 256 или 65 536 разных значений яркости для каждого пикселя, представленного байтом или 16-битным словом соответственно. Таким образом, чтобы преобразовать цветное изображение в полутоновое, три значения а, b и с в каждом цветном пикселе необходимо преобразовать в одно значение яркости для соответствующего пикселя полутонового или бинаризованного изображения. На первом этапе три значения цвета а, b и с, преобразуются в значение яркости L, обычно в интервале [0,0, 1,0] 606. Для определенных цветовых моделей к каждому из цветовых значений 608 применяется нетривиальная функция, и результаты суммируются 610, давая значение яркости. В других цветовых моделях каждое цветовое значение умножается на коэффициент, и полученные результаты суммируются 612, давая значение яркости. В некоторых цветовых системах одно из трех цветовых значений является, фактически, значением 614 яркости. Наконец, в общем случае к трем цветовым значениям 616 применяется функция, которая дает значение яркости. Затем значение яркости квантуется 618, позволяя получить значение яркости оттенков серого в требуемом интервале, обычно [0, 255] для полутоновых изображений и одно из двух значений яркости (0,1) для бинаризованных изображений.
На Фиг. 7 показано дискретное вычисление градиента яркости. На Фиг. 7 показан небольшой квадратный участок 702 цифрового изображения. Каждая клетка, например, клетка 704, представляет пиксель, а числовое значение в клетке, например, значение «106» в клетке 704, представляет яркость серого цвета. Допустим, пиксель 706 имеет значение яркости «203». Этот пиксель и четыре смежных с ним пикселя показаны на крестообразной схеме 708 справа от участка 702 цифрового изображения. Рассматривая левый 710 и правый 712 соседние пиксели, изменение значения яркости в направлении х, Δx можно дискретно вычислить как:
.
Рассматривая нижний 714 и верхний 716 соседние пиксели, изменение значения яркости в вертикальном направлении Δy можно вычислить как:
.
Вычисленное значение Δx является оценкой частного дифференциала непрерывной функции яркости относительно оси л: в центральном пикселе 706:
.
Частный дифференциал функции F яркости относительно координаты у в центральном пикселе 706 рассчитывается по Δy:
.
Затем градиент яркости в пикселе 706 может быть рассчитан следующим образом:
где i и j представляют собой единичные векторы в направлениях x и y. Модуль вектора градиента и угол вектора градиента далее рассчитываются следующим образом:
.
Направление вектора 720 градиента яркости и угол θ 722 показаны наложенными на участок 702 цифрового изображения на Фиг. 7. Следует учесть, что вектор градиента направлен в сторону наиболее резкого увеличения яркости от пикселя 706. Модуль вектора градиента указывает на ожидаемое увеличение яркости на единицу приращения в направлении градиента. Конечно же, поскольку градиент оценивается исключительно с помощью дискретных операций, в вычислении, показанном на Фиг. 7, направление и модуль градиента представлены исключительно оценками.
На Фиг. 8 показан градиент, рассчитанный для некой точки на непрерывной поверхности. На Фиг. 8 представлена непрерывная поверхность z=F(x,y). Непрерывная поверхность 802 строится относительно трехмерной декартовой системы координат 804 и имеет похожую на шляпу форму. Для отображения непрерывного множества точек с постоянным значением z на поверхности могут быть построены контурные линии, например, контурная линия 806. В конкретной точке 808 на контуре, построенном на поверхности, вектор градиента 810, рассчитанный для точки, расположен перпендикулярно к контурной линии и точкам в направлении максимально резкого наклона вверх на поверхности от точки 808.
Обычно вектор градиента яркости расположен перпендикулярно к границе яркости, причем чем больше модуль градиента, тем данная граница более четкая. Граница имеет различия в яркости пикселей на любой из сторон границы с общими признаками, или, другими словами, яркость в соседних строках пикселей, перпендикулярных границе, меняется сходным образом. На Фиг. 9 показан ряд примеров градиента яркости. Каждый пример, такой как пример 902, содержит центральный пиксель, для которого рассчитывается градиент, и четыре прилегающих пикселя, которые используются для расчета Δx и Δy. Границы с наибольшей яркостью показаны в первой колонке 904. В этих случаях модуль градиента составляет не менее 127,5, а в третьем случае 906 - 180,3. При относительно небольшой разности по границе, показанной в примере 908, получается градиент величиной всего 3,9. Во всех случаях вектор градиента расположен перпендикулярно очевидному направлению границы яркости, проходящей через центральный пиксель.
n
Многие методы обработки изображений включают применение ядер к сетке пикселей, составляющей изображение. На Фиг. 10 показано применение ядра к изображению. На Фиг. 10 небольшая часть изображения I 1002 представлена в виде прямоугольной сетки пикселей. Ниже изображения I 1002 показано небольшое ядро 3×3 k 1004. Для выполнения в отношении изображения операции обработки на основе ядра ядро обычно применяется к каждому пикселю изображения. В случае ядра 3×3, такого как ядро k 1004, показанное на Фиг. 10, для пикселей на границе можно использовать модифицированное ядро, также изображение можно раздвинуть, скопировав значения яркости для пикселей границы в описывающий прямоугольник из пикселей, чтобы иметь возможность применять ядро к каждому пикселю исходного изображения. Чтобы применить ядро к пикселю изображения, ядро 1004 численно накладывается на окрестность пикселя 1006 на изображении с такими же размерами в пикселях, что и у ядра. Применение ядра к окрестности пикселя, к которому применяется ядро, позволяет получить новое значение для пикселя в преобразованном изображении, полученном при выполнении операции на основе ядра. Для некоторых типов ядер и операций на основе ядра новое значение пикселя, к которому применяется ядро, I, вычисляется как сумма произведений значения ядра и пикселя, соответствующего значению 1008 ядра. В других случаях новое значение пикселя является более сложной функцией окрестности для пикселя и ядра 1010. В некоторых других типах обработки изображений новое значение пикселя генерируется функцией, применяемой к окрестностям пикселя без использования ядра 1012.
На Фиг. 11 показана свертка ядра с изображением с получением преобразованного изображения. Как правило, ядро последовательно применяется к каждому пикселю изображения. В некоторых случаях ядро применяется только к каждому пикселю изображения, не принадлежащему границе изображения. На Фиг. 11 ядро 3×3, выделенное штриховкой 1102, было последовательно применено к первой строке пикселей, не принадлежащих границе изображения 1104. Каждое новое значение, созданное в результате применения ядра к пикселю в исходном изображении 1106, было перенесено в преобразованное изображение 1107. Другими словами, ядро последовательно применяется к исходным окрестностям каждого пикселя на исходном изображении для получения преобразованных значений пикселей, включенных в преобразованное изображение. Данный процесс называется «сверткой» и отчасти связан с математической операцией свертки, которая выполняется путем умножения изображений, к которым применено преобразование Фурье, с последующим обратным преобразованием Фурье по произведению.
x
y
На Фиг. 12 показан пример ядра и методик обработки изображений на основе ядра. В процессе, называемом «медианной фильтрацией», значения яркости некого пикселя и пикселей в окрестности данного пикселя в исходном изображении 1202 сортируются 1204 по возрастанию величины, и медианное значение 1206 выбирается в качестве значения 1208 для данного пикселя в преобразованном изображении. Гауссово сглаживание и очистка от шумов включают применение гауссова ядра 1210 ко всем окрестностям 1214 исходного изображения для создания значения для центрального пикселя окрестности 1216 в соответствующей окрестности обработанного изображения. Значения в гауссовом ядре рассчитываются по выражению, например, по выражению 1218 для создания дискретного представления гауссовой поверхности над окрестностью, образованного вращением кривой нормального распределения вокруг вертикальной оси, совпадающей с центральным пикселем. Горизонтальные и вертикальные компоненты градиента изображения для каждого пикселя оцениваются применением соответствующих ядер градиента G 1220 и G 1222. Были указаны только три из множества различных типов методик обработки изображения на основе свертки.
Способы и системы, к которым относится настоящий документ
На Фиг. 13А-В показан один вариант реализации способа, к которому относится настоящий документ. Данный вариант реализации специально направлен на исправление искривления текстовых строк на разворотах книг. Тем не менее, тот же способ либо аналогичные ему способы могут использоваться для исправления широкого диапазона искривлений текстовых строк, которые встречаются во многих видах содержащих текст цифровых изображений.
На Фиг. 13А показан разворот книги. Разворот книги 1302 содержит две страницы 1304 и 1306. Так как данные страницы соединены по корешку книги 1308, то при ее открытии и помещении на поверхность обложкой вниз поверхность страниц принимает форму дуги, направленной вверх и от корешка. Таким образом, на изображении разворота книги, полученном с помощью цифровой камеры, текстовые строки, такие как текстовая строка 1310, являются изогнутыми не только потому, что фактически изогнуты поверхности страниц, но и ввиду искривления, вызванного искажением перспективы. Тем не менее, если разгладить страницу и смотреть на нее сверху вниз, текстовые строки будут линейными, а символы и слова, содержащиеся в тексте, будут расположены в знакомой форме прямоугольника. При изгибании и искривлении текстовых строк из-за искажения перспективы и изгиба страниц раскрытой книги буквы и символы в текстовых строках искажаются и нелинейно сжимаются, что существенно усложняет задачу автоматизированного оптического распознавания символов и букв на содержащем текст изображении.
На Фиг. 13В показаны этапы, выполняемые в рамках способа настоящего изобретения при обработке изображения раскрытой книги, как описано выше со ссылкой на Фиг. 13А. На первом этапе изображение разворота книги 1320 обрабатывается с целью обособить только ту часть изображения, которая соответствует двум страницам данной книги 1322. На следующем этапе для каждой из двух страниц 1324 и 1326 подготавливаются отдельные изображения. На каждом из этих двух изображений одной страницы страница, если она не ориентирована вертикально на исходном изображении 1320, вращается до достижения вертикальной ориентации. На следующем этапе, выполняемом в отношении каждого из двух изображений 1324 и 1326, изображение одной страницы обрабатывается таким образом, чтобы граница страницы, не прилегающая к корешку, была также ориентирована вертикально либо параллельно к прилегающей к корешку границе, с получением изображений 1328 и 1330. На окончательном этапе изогнутые верхняя и нижняя границы каждого изображения выпрямляются вместе с текстовыми строками на странице с получением окончательных обработанных изображений 1332 и 1334, на каждом из которых страница представлена в виде прямоугольника, так словно ее изображение было получено из точки непосредственно над центроидом страницы при расположении оптической оси устройства получения изображения перпендикулярно к данной странице. Существует множество дополнительных операций, включая изменение масштаба, повышение контурной резкости и прочие операции обработки изображений, которые могут быть выполнены для дальнейшего улучшения изображения страницы для оптического распознавания символов.
x
y
На Фиг. 14A-D показана первоначальная обработка изображения страницы для подготовки к выравниванию границ страницы параллельно корешку, как описано выше со ссылкой на Фиг. 13В. Как показано на Фиг. 14А, исходное изображение страницы 1402 свертывается с помощью Гауссова ядра, либо в отношении изображения применяется метод медианной фильтрации с получением сглаженного изображения 1404 без шумов. Затем к сглаженному изображению без шумов применяются два ядра градиента G и G для получения двух карт компонентов градиента, из которых формируется карта градиентов 1406, как описано выше со ссылкой на Фиг. 7-9. На карте градиента каждый пиксель, такой как пиксель 1408, соотносится с направлением градиента и модулем градиента. По карте градиентов могут быть определены границы, такие как контур страницы на изображении страницы, представленные в виде строки или кривой пикселей с соотнесенными с ними векторами градиента, имеющими сходную ориентацию, и направление, перпендикулярное данной строке или кривой и имеющее относительно большое значение модуля. Например, как показано на Фиг. 14А, вертикальная граница 1410 на изображении будет соответствовать столбцу 1412 пикселей на карте градиентов с векторами с большими значениями модуля, указывающими в одном и том же направлении и перпендикулярными данной границе. Для извлечения границ из карты градиентов, соответствующих границам яркости на исходном изображении, может быть применена пороговая фильтрация значений модуля градиента и различные методики на основе анализа непрерывности. Другие хорошо известные способы, предназначенные для определения границ на изображении страницы, применяются (в альтернативных вариантах реализации) аналогичным образом.
Как показано на Фиг. 14В, для сужения границ так, чтобы из изображения страницы можно было извлечь четко очерченные границы, используется методика подавления немаксимумов, применяемая как функция k окрестностям пикселей на карте градиентов. На Фиг. 14В для принятия решения о том, нужно ли сохранять значение центральной ячейки или элемента 1422 преобразованного изображения 1424, используется окрестность 3×3 1420 вокруг центральной ячейки или элемента 1422 карты градиентов. Если центральный пиксель имеет максимальную величину по направлению градиента в данной окрестности 1426, то значение сохраняется 1428 в преобразованной карте градиентов, полученной посредством подавления немаксимумов. Таким образом, немаксимальные величины градиента, перпендикулярные границе, подавляются или устанавливаются в значение 0, чтобы утончить многопиксельную границу 1430 в исходной карте градиентов до однопиксельной границы 1432 в преобразованной карте градиентов.
На Фиг. 14С показан общий вид ядра подавления немаксимумов ("ядра NMS"), на котором может выполняться свертка изображения. Ядро NMS 1436 содержит три области: (1) центральный пиксель 1438; (2) непосредственная окрестность 1440; (3) расширенная окрестность 1442. Применение ядра NMS для пикселей подразумевает такое наложение ядра NMS, чтобы область центрального пикселя 1438 ядра NMS накладывалась на пиксель, к которому применяется ядро. При наложении ядра определяется, передается ли яркость пикселя, к которому применяется ядро, соответствующему пикселю или клетке итогового изображения или карте, или на итоговую карту или изображение передается значение низкой яркости, соответствующее изображению или карте, которое может быть любым в числовом выражении. Если яркость пикселя, находящегося под центральным пикселем ядра NMS, выше яркости пикселя, находящегося в непосредственной окрестности ядра NMS, и если яркость пикселя под областью центрального пикселя выше или равна яркости любого пикселя, лежащего в расширенной окрестности, то на итоговое изображение или карту передается значение яркости центрального пикселя. В противном случае, на итоговое изображение или карту передается значение низкой интенсивности. Процесс принятия решения формально выражен 1444 на Фиг. 14С. При свертке ядра NMS с изображением или картой выбираются пиксели или клетки изображения или карты с локальной максимальной яркостью для передачи на итоговую карту или изображение.
Разумеется, над изображением в любой из двух возможных ориентаций могут быть произведены такие операции, как подавление немаксимумов. Например, подавление немаксимумов может рассматривать значение интенсивности серого 255 как максимум, а значение интенсивности серого 0 как минимум, или значение интенсивности серого 0 как максимум, а значение интенсивности серого 255 как минимум. Обычно соответствие между числовыми значениями пикселей и минимальным и максимальным значением легко может быть выведено из контекста, например, белых символов на черном фоне или черных символов на белом фоне.
Как показано на Фиг. 14D, к карте градиентов 1406 применяются подавление немаксимумов и фильтрация длин границ с получением карты границ 1446, из которой, используя границы, а также дополнительные геометрические характеристики и характеристики яркости страниц, может быть извлечен контур страницы 1448. Дополнительные характеристики могут включать информацию о цветах из исходного изображения разворота книги, используемую для дифференциации текстовых пикселей от фоновых пикселей, ожидаемых формах и размерах книг и страниц книг, а также другую информацию, используемую для фильтрации границ страниц от других дополнительных границ яркости, которые встречаются при операции обработки для определения границ, описанной выше со ссылкой на Фиг. 14А-В.
На Фиг. 15А-В показан один из подходов к процессам выравнивания вертикальной границы страницы или исправления вертикальной перспективы страницы, показанной выше со ссылкой на Фиг. 13В. Как показано на Фиг. 15А, контур страницы, извлеченный из карты градиентов с подавленными немаксимумами, накладывается на исходное изображение страницы для формирования страницы 1502 на изображении страницы 1504. Затем изображение страницы вращается, с тем чтобы прилегающая к корешку граница 1506 страницы была вертикальной. На данном этапе процесса верхняя 1508 и нижняя 1512 границы страницы обычно являются изогнутыми, граница страницы, параллельная корешку 1510, но не прилегающая к нему, может быть отклонена от вертикального направления на угол α 1511, а нижняя граница 1512 страницы может быть расположена с уклоном по отношению к границе 1510 на угол β 1513 и отклонена от вертикального направления на угол γ 1514. На первом этапе для корректировки положения неприлегающей к корешку границы до вертикальной ориентации осуществляется смещение пикселей на изображении, как показано на промежуточном изображении 1516, а на втором этапе осуществляется реорганизация пикселей на изображении для корректировки положения нижней границы 1512 до горизонтального 1518.
На Фиг. 15В показан один из способов корректировки ориентации границы страницы. На Фиг. 15В показан процесс корректировки положения границы, параллельной корешку, но не прилегающей к нему, так чтобы она имела вертикальную ориентацию. Проводится корректировка каждой горизонтальной строки пикселей на изображении. Для горизонтальной строки пикселей 1520 на Фиг. 15В приведен ряд значений, полученных на основе геометрических характеристик границы 1510 на содержащем текст изображении. Верхний угол страницы 1522 имеет координаты (x,y). Пересечение 1524 горизонтальной строки пикселей 1520 и границы 1510 имеет координаты (х', у'). Ширина страницы имеет значение X 1526. Точка 1524 делит горизонтальную строку пикселей на два фрагмента, один длиной х' 1527, а другой длиной Х - х' 1528. Чтобы исправить положение горизонтальных строк пикселей 1520 для приведения границы 1510 в вертикальное положение, необходимо удалить пиксели х-х' 1530 из второй части 1528 горизонтальной строки и добавить то же самое число пикселей в первую часть 1527 горизонтальной строки пикселей. Горизонтальная строка пикселей 1532 снова показана в правой верхней части Фиг. 15В. В скопированном изображении 1534 небольшие вертикальные стрелки, помеченные буквой "d", такие как стрелка 1536, указывают на пиксели, которые дублируются в первой части строки пикселей, а небольшие вертикальные стрелки, помеченные буквой "r", такие как стрелка 1538, указывают на пиксели, подлежащие удалению из второй части строки пикселей. Более длинные стрелки, такие как стрелка 1540, иллюстрируют преобразование пикселей в исходной горизонтальной строке пикселей 1532 в пиксели в преобразованной горизонтальной строке пикселей 1542 после совершения операций дублирования и удаления пикселей. Как можно увидеть, сравнив исходную горизонтальную строку пикселей 1534 с преобразованной горизонтальной строкой пикселей 1542, значение яркости пикселей в положении х' в исходной строке пикселей, обозначенное заштрихованной областью 1544, сместилось в преобразованной горизонтальной строке пикселей 1542 вправо 1546. Значения яркости пикселей, добавленных к первой части строки пикселей, и значения яркости двух пикселей, прилегающих к каждому пикселю, удаленному из второй части строки пикселей, могут быть изменены во избежание резких разрывов в градиентах яркости пикселя. Как показано на Фиг. 15В, во избежание локальных искажений пиксели дублируются и удаляются в строке пикселей через фиксированные интервалы. В других вариантах реализации для корректировки ориентации границы страницы на изображении страницы или для исправления вертикальной перспективы страницы могут использоваться многие другие методики и разновидности методики, проиллюстрированной на Фиг. 15В. Так, в некоторых случаях граница страницы может не быть видна на исходном изображении, поэтому для выполнения эквивалентной операции без использования данной границы страницы могут применяться другие указатели или ориентиры на изображении. Показанный способ немного изменяется при корректировке границы, параллельной корешку, но не прилегающей к нему, на изображении разворота книги, состоящего из двух страниц.
После распознавания подызображения каждой страницы, которое в дальнейшем будет называться "изображением страницы", следующий шаг во многих вариантах реализации будет состоять в определении направления строк текста на странице. В дальнейшем обсуждении предполагается, что строки текста приводятся на английском, немецком, русском или других европейских языках, причем символы расположены в горизонтальных строках текста последовательно от левой границы к правой. Сходные способы могут использоваться и для языков, в которых строки символов имеют вертикальную ориентацию. Следует также отметить, что кроме выравнивания изображения разворота книг, способы и системы настоящего изобретения могут использоваться для выравнивания строк текста в изображениях одностраничных документов и других типах изображений, содержащих текст. Во многих из подобных случаев стадия начальной обработки будет заключаться в определении границ одной страницы, а не двух страниц.
На Фиг. 16A-D показан один из подходов к определению ориентации строк текста на изображении страницы, или, протекающего аналогичным образом, определения угловой ориентации изображения страницы, при котором строки текста будут горизонтальны. На Фиг. 16А показано упрощенное изображение 1602 страницы, содержащей строки 1604-1606 текста. Для наглядности строки текста преувеличенно искажены. Также для упрощения понимания вместо символов конкретного языка текстовые строки содержат различные фигуры темного цвета. В рассматриваемом здесь способе выполняются вычисления каждого из возможных поворотов изображения страницы для определения того поворота, который наилучшим образом ориентирует строки текста в предполагаемой горизонтальной ориентации.
На Фиг. 16В показаны вычисления для первого поворота изображения страницы. На строки текста накладывается сетка или решетка 1610, образуя матрицеподобную текстуру ячеек, таких как ячейка 1611, шаблон сетки включает столбцы ячеек и строки ячеек. Столбцы пронумерованы под схемой, начиная со столбца 1 (1612 на Фиг. 16В) и заканчивая столбцом 16 (1614 на Фиг. 16В). Сетка размещается поверх основной части символов страницы, однако может быть кадрирована таким образом, чтобы не включать пустые и по большей части пустые поля. В способе по настоящему изобретению полутоновое исходное изображение копируется во временное изображение, которое бинаризуется таким образом, чтобы пиксели символов были темными, с бинарным значением "0," а не входящие в символы пиксели фона были белыми, со значением пикселей "1". Однако подобный способ может быть реализован без копирования и бинаризации. Так, как показано в таблице 1616, под страницей текста с наложенной сеткой, количество ячеек, содержащих символы, и ячеек фона в каждом столбце сводится в таблицу вместе с вычисленным соотношением количества фоновых ячеек к количеству ячеек, содержащих символы. Например, в столбце 1 ячейки 1618-1623 не содержат пикселей символов, а значит являются фоновыми ячейками, тогда как оставшиеся ячейки 1624-1630 в столбце 1 содержат как минимум один пиксель символа. Таким образом, в столбце 1 имеется шесть фоновых ячеек 1632 и семь ячеек 1634, содержащих символы, и вычисленное отношение фоновых ячеек к ячейкам, содержащим символы, составляет 0,86 (1636 на Фиг. 16В). Оставшиеся столбцы сводятся в таблицу аналогичным образом. Вычисленные отношения фоновых ячеек к ячейкам, содержащим символы, сводятся в гистограмму 1638, вычисляется среднее значение 1640 и дисперсия 1642 для множества отношений фоновых ячеек к ячейкам, содержащим символы. На Фиг. 16С показаны аналогичные вычисления для другой ориентации страницы, которые дают другое среднее значение 1644 и дисперсию 1646. Гистограмма 1648 демонстрирует больший диапазон отношений фоновых ячеек к ячейкам, содержащим символы, чем гистограмма 1638 на Фиг. 16В. На Фиг. 16D показаны те же самые вычисления, выполненные для другой ориентации страницы, отличающейся от ориентации страниц на Фиг. 16В и 16С. Гистограмма 1650, вычисленное среднее значение 1652 и вычисленная дисперсия 1654 также отличаются от значений для ориентации страниц на Фиг. 16С и 16В.
В вычисленных дисперсиях наблюдается общая тенденция. Требуемая ориентация страницы, которая позволяет получить приблизительно горизонтальные текстовые строки, показанная на Фиг. 16В, имеет значительно меньшую вычисленную дисперсию для отношений фоновых ячеек к ячейкам, содержащим символы, чем ориентации, показанные на Фиг. 16С и 16D, с ростом дисперсии по мере перехода от требуемой ориентации, показанной на Фиг. 16В, до ортогональной ориентации на странице, приведенной на Фиг. 16D. Эта тенденция, разумеется, является очевидной. При правильной ориентации, показанной на Фиг. 16В, каждый столбец содержит несколько ячеек с пикселями символов для каждой из текстовых строк и несколько ячеек без пикселей символов, которые соответствуют горизонтальным пустым местам между строками текста. В противоположность этому при ортогональной ориентации страницы, показанной на Фиг. 16D, некоторые столбцы, например, столбец 1656, практически не содержат ячеек с пикселями символов, а другие, например, столбец 1658, содержат в основном ячейки с символами. Таким образом, аппроксимация правильной ориентации страницы, которая позволяет получить горизонтальные строки текста, должна представлять собой одну из двух ориентаций с минимальной вычисленной дисперсией для вычисленных отношений фоновых ячеек к ячейкам, содержащим символы. Эти две ориентации обычно соответствуют правильной ориентации, представленной на Фиг. 16В, и обратной ориентации, полученной поворотом изображения в правильной ориентации на 180°. Последний вариант ориентации будет содержать перевернутые символы текста. Эти две ориентации с минимальной дисперсией можно различить с помощью множества различных способов. В одном из способов можно применить методы оптического распознавания символов к нескольким выбранным символам для обоих ориентаций, при этом ориентация, которая позволит получить наилучшее распознавание выбранных символов, выбирается в качестве правильной. Это лишь один способ из множества подходов к определению ориентации изображения страницы с горизонтальными строками текста, который включает символы в порядке слева направо.
На Фиг. 17A-D показаны морфологические операции, которые использовались в некоторых вариантах реализации для создания на бинаризованной карте однородных полос пикселей, соответствующих строкам текста. Эти морфологические операции включают операции дилатации, эрозии, замыкания и размыкания (открытия). На всех Фиг. 17A-F используются одни и те же правила иллюстрации, далее описанные применительно к Фиг. 17А. На левой стороне Фиг. 17А показана малая часть содержащего текст изображения 1702. Это бинаризованное изображение, в котором значение "0" обозначает черный или текстовый пиксель, а значение "1" - пустое пространство. Посредством свертки изображения 1702 с горизонтальным ядром 1704 выполняется операция 1703 горизонтальной дилатации. Если центральный пиксель ядра перекрывает пиксель на изображении, то пиксель на изображении, полученный в результате свертки, получает значение минимального значения пикселей на изображении, перекрытого пикселями ядра. Это ведет к эффекту дилатации, или горизонтального расширения, содержащих темные пиксели областей изображения. Результатом применения трехпиксельного ядра 1704 горизонтальной дилатации к изображению 1702 является дилатированное изображение 1705. На Фиг. 17В показана операция горизонтальной эрозии. Операция горизонтальной эрозии в некотором смысле имеет действие, противоположное действию операции горизонтальной дилатации. В операции горизонтальной эрозии трехпиксельное горизонтальное ядро 1710 свертывается с исходным изображением 1702, при этом пиксель изображения, перекрытый центральным пикселем в ядре 1710, получает на изображении, образованном в результате свертки, максимальное значение из всех пикселей на изображении, перекрытых пикселями в ядре. Это ведет к эффекту эрозии, или сужению, всех содержащих черные пиксели областей на изображении. На Фиг. 17В применение ядра эрозии через процесс свертки к исходному изображению 1702 ведет к формированию эродированного изображения 1712. Следует отметить, что примеры, приведенные на Фиг. 17A-F, являются искусственными, так как характеристики символов на страницах текста обычно имеют ширину более одного пикселя.
Как показано на Фиг. 17С, в случае эрозии изначально дилатированного изображения 1705, полученного в результате свертки исходного изображения с оператором горизонтальной дилатации, посредством свертки дилатированного изображения с оператором горизонтальной эрозии, получается замкнутое изображение 1714. Операция замыкания, таким образом, - это двухэтапная операция, при которой изображение сначала дилатируется, а затем эродируется.
На Фиг. 17D-E показана операция размыкания(открытия). Операция размыкания противоположна по действию операции замыкания и заключается в применении эрозии к изображению с последующей его дилатацией. На Фиг. 17D замкнутое изображение 1714, полученное посредством эрозии дилатированного изображения, как описано выше со ссылкой на Фиг. 17С, подвергается эрозии с получением промежуточного изображения 1716. На Фиг. 17Е промежуточное изображение 1716 дилатируется с получением открытого изображения 1718. Общее описание методики, применяемой в описываемом варианте реализации способа настоящего изобретения, приводится на Фиг. 17F, на котором исходное изображение 1702 дилатируется, эродируется, снова эродируется и затем дилатируется, то есть сначала замыкается, а следом размыкается с получением замкнутого, а затем открытого изображения 1718. Как понятно из Фиг. 17F, операция замыкания с последующим размыканием заменяет символы в строке текста на закрашенный контур 1720 строки текста.
Как обсуждается ниже, в альтернативных реализациях используются различные сочетания одной или более морфологических операций над однородными полосами пикселей с одинаковыми бинарными значениями, соответствующими строкам текста, на фоне пикселей с другими бинарными значениями. Исходные пиксели для создания линий контура выбираются из пикселей каждой полосы. Эти морфологические операции могут использоваться для создания полос пикселей со значением 1 на фоне из пикселей со значением 0, или полос пикселей со значением 0 на фоне из пикселей со значением 1, и могут использоваться для создания полос светлых символов на темном фоне или темных символов на светлом фоне.
На Фиг. 18А-С показано создание линий контура. На Фиг. 18А показан один из подходов к определению положения и размеров строк на изображении страницы. Фиг. 18А содержит пример текстовой строки 1802. На первом шаге, указанном направленной вниз вертикальной стрелкой 1803, для заполнения или полного затенения текстовой строки 1804 используется один или более морфологических операторов, обычно ядер, на которых выполняется свертка изображения страницы. Они могут включать операцию дилатации, обсуждавшуюся ранее со ссылкой на Фиг. 17А, с предположением, что символы ассоциируются с пикселями со значением 0, а фон без символов ассоциируется с пикселями со значением 1. Также может быть использована серия операций дилатации, эрозии, эрозии и дилатации, как обсуждалось ранее со ссылкой на Фиг. 17F. Кроме того, могут быть использованы и другие одиночные или комбинированные морфологические операторы. В описанном ниже варианте реализации создается и бинаризуется копия изображения страницы, после чего к бинаризованной копии применяются указанные морфологические операторы. В результате создается растровое изображение строк текста. На следующем шаге 1805, к бинаризованной копии изображения применяется вертикальный оператор сглаживания, например, гауссово ядро для сглаживания по вертикали, чтобы удалить оставшиеся изолированные пиксели со значением 0 между затемненных текстовых строк и оставить затемненными на изображении страницы только содержащие текст полосы.
Скопированное бинаризованное изображение содержит полосы пикселей со значением 0, соответствующие строками текста на исходном изображении текста. В одном из вариантов реализации серые пиксели, соответствующие этим полосам, копируются в два изображения с белым фоном, и в результате получаются два изображения, содержащие только текстовые строки, для создания затравочных (начальных) точек (пикселей) и контуров. Однако в других реализациях поиск областей текстовых строк может производиться и без операций копирования страницы.
К первому из изображений, содержащих только текстовые строки, применяется 1806 оператор подавления немаксимумов, чтобы получить небольшое количество затравочных пикселей 1808-1810 для каждой текстовой строки. В одном из способов реализации для создания затравочных пикселей на ядре NMS, обсуждавшемся выше со ссылкой на Фиг. 14С, выполняется свертка изображения, содержащего только текстовые строки. Для каждой из затемненных полос текста могут использоваться различные ядра NMS с различными параметрами, например, непосредственной и расширенной окрестностью разного размера, чтобы получить набор затравочных пикселей в рамках требуемой области значений. Также могут использоваться ядра NMS с дополнительными настраиваемыми параметрами.
Затравочные пиксели используются для инициирования линий контуров, которые наращиваются с помощью способа создания контура, применяемого 1811 ко второму из двух изображений, содержащих только текстовые строки, для создания непрерывного контура 1812, определяющего текстовую строку. Способ создания контура будет рассмотрен ниже. Как показано на Фиг. 18В, линии контуров наращиваются в виде последовательности векторов или звеньев, или сегментов 1813-1816 во всех направлениях от каждого затравочного пикселя 1817-1818 строки текста 1819. Как показано на Фиг. 18С, когда два растущих сегмента линии контура 1820 и 1822 сближаются на минимальное расстояние d 1824 один от другого, два сегмента контура могут объединиться 1826 посредством поворота концевых звеньев двух сегментов, образуя единую линию контура.
Далее линии контура, созданные для отображения строк текста на изображении страницы, используются для создания математической модели искривления или угла направления текстовых строк и каждой точки изображения страницы. На Фиг. 19А-В показано формирование модели искривления текстовых строк на изображении страницы.
а
а
a
1
2
8
На Фиг. 19А показано создание первого типа математической модели искривления для изображения страницы. В левой половине Фиг. 19А показано представление 1902 представления линий контура текстовых строк. Каждый контур состоит из небольших векторов или звеньев. Часть линии контура 1904, показанная на вставке 1905, увеличена на вставке 1906 для демонстрации отдельных звеньев. Для каждого звена вычисляется угол α 1907. Угол а представляет собой угол наклона вектора или сегмента относительно горизонтали, которая представлена пунктирной линией 1908 на вставке 1909. Также для каждого звена вычисляется средняя точка 1910. Вычисленные координаты (x,y) средней точки и угол наклона α для каждого звена помещаются в таблицу 1912, которая содержит исходные данные для создания модели искривления страницы. Эти исходные данные обрабатываются 1914 способом согласования данных, который обсуждается ниже, для получения функции ƒ(x,y) 1916, которая обеспечивает оценку угла наклона для каждой точки (x,y) страницы. В одном из вариантов реализации эта функция представляет собой полином 1918 от х и y с восемью коэффициентами , , …, .
1
2
8
i
с
n
с
ƒ
c
1
2
n
n
c
n
На Фиг. 19 В показан один из способов (именуемый "метод Гаусса-Ньютона") согласования угла наклона и данных о координатах, полученных из звеньев линии контура в полиномиальной функции ƒ(x,y). Сначала на Фиг. 19 В заново формулируется задача согласования данных. Коэффициенты β, β, … β могут рассматриваться как вектор β 1922. Для значений данных коэффициентов строится некое предположение с формированием исходного вектора β. Разница между тангенсами, возвращенными функцией ƒ(x,y) с текущими значениями β, и тангенсами наблюдаемых углов наклона выражается как множество n невязок r 1924, где n - это число пикселей с присвоенными углами наклона α. Каждая невязка означает разницу между тангенсом угла наклона α, присвоенного пикселю, и угла наклона, вычисленного для данного пикселя функцией ƒ(x,y) с предположением текущих значений коэффициентов β. Новое значение вектора коэффициентов β может быть вычислено из текущих значений вектора коэффициентов β, из вычисленных невязок и определителя матрицы Якоби J для функции ƒ(x,y) 1926, как показано в выражении 1928. Следует отметить, что метод Гаусса-Ньютона минимизирует сумму возведенных в квадрат невязок 1930. Метод Гаусса-Ньютона иллюстрируется небольшой блок-схемой 1932. Выполнение данного способа начинается с исходного β, функции ƒ(x,y) и набора данных 1934. В итерационном цикле при выполнении данного способа из набора данных и функции ƒ(x,y), делающей предположение о текущих коэффициентах β, на этапе 1936 вычисляются невязки r, r, …, r, где r - это вектор невязок. Затем с использованием выражения 1928 на этапе 1938 вычисляется новое множество коэффициентов β. Если разница между новыми и предыдущими коэффициентами меньше порогового значения, которое определяется на этапе 1940, новые коэффициенты возвращаются как коэффициенты для функции ƒ(x,y) 1942. В противном случае на этапе 1944 β присваивается β и выполняется другая итерация. Данная блок-схема является в некоторой степени упрощенной, так как метод Гаусса-Ньютона не обеспечивает гарантированную сходимость. Таким образом, помимо проверки на разность, выполняемой на этапе 1940, данный метод обычно применяет отсечку числа итераций и другие методики, позволяющие избежать бесконечной итерации метода. В альтернативных вариантах реализации могут использоваться другие способы согласования данных, такие как нелинейный метод сопряженных градиентов, разновидности многих других методик согласования искривлений, включая нелинейные способы согласования искривлений, такие как метод Левенберга-Марквардта.
0
с
1
2
8
а
а
а
На Фиг. 20 показан более простой альтернативный способ согласования данных, который преобразует извлеченные исходные данные об искривлении, сведенные в таблицу 1912 на Фиг. 19А, в полиномиальную функцию. В этом способе разница D вычисляется 2050 как сумма взвешенных квадратов разностей для каждой точки данных между наблюдаемым углом наклона α и углом наклона α, вычисленным для точки данных с помощью исходного полиномиального выражения 2052 с исходными коэффициентами. Легко вычислить частный дифференциал разности относительно каждого из коэффициентов полинома, как показано в уравнениях 2054-2056 на Фиг. 20. Чтобы свести к минимуму вычисленную разность, значения этих частных дифференциалов приравниваются к 0. Затем частные дифференциалы можно преобразовать в набор уравнений m 2058. Определив матрицу K 2060 и два вектора столбцов 2061 и 2062, как показано на Фиг. 20, набор уравнений 2058 можно выразить в матричной форме как уравнение 2063. Это уравнение решается для оценки значений коэффициентов , , …,  посредством обращения матрицы, как показано на шагах 2064 и 2065. Обращение матрицы в некоторых вариантах реализации изобретение производится с помощью исключения методом Гаусса.
На Фиг. 21-24 показано формирование контуров для текстовых строк, указанное на Фиг. 18А как шаг 1809. На Фиг. 21 показан выбор первого звена для затравочного пикселя. Как показано на Фиг. 21, для каждого затравочного пикселя 2102 исходное звено выбирается из набора возможных звеньев, таких как звено 2104. На Фиг. 21 все возможные звенья имеют фиксированную длину L, но могут иметь различные возможные направления или ориентации. Для выбора одного из возможных звеньев 2108 в качестве исходного звена контура, начинающегося от затравочного пикселя 2102, используется процесс 2106 выбора направления границы.
α
α
α
α
На Фиг. 22 показано, как выбирается возможное звено для следующего звена контура. На Фиг. 22 затемненный пиксель 2202 представляет собой конечную точку последнего звена. Звено 2204 r выходит из конечной точки 2202 с углом наклона α 2206 относительно горизонтали, указанной пунктирной линией 2208. Средняя величина этого возможного звена 2210 вычисляется как сумма яркости пикселей, лежащих в основе звена, разделенная на количество пикселей, лежащих в основе звена. Звено r выбирается в качестве следующего звена сегмента контура, если 2212 средняя величина яркости r больше, чем у других возможных звеньев, а все пиксели, лежащие в основе r, являются пикселями текстовой строки и содержатся в затемненной полосе текстовой строки (1804 на Фиг. 18А), созданной посредством применения одного или более морфологических операций бинаризованного варианта изображения страницы, и если рассмотреть предыдущее звено 2214, угол β 2216 имеет значение в градусах или радианах меньше порогового значения. Сходный способ используется для выбора направления исходного звена для затравочной точки (2106 на Фиг. 21) с вероятным звеном, имеющим выбранное максимальное среднее значение, хотя здесь могут существовать дополнительные ограничения на угол α, в результате чего будет рассматриваться только подмножество звеньев, соответствующих всем возможным углам α, показанным на Фиг. 21.
Как показано на Фиг. 23, начиная с заданного затравочного пикселя 2302, звенья 2304 и 2305 создаются вправо от затравочной точки, а звенья 2306 и 2307 - влево от затравочной точки. Другими словами, звенья успешно добавляются в обе стороны от затравочной точки для создания образующегося сегмента линии контура от затравочной точки. В обсуждаемом ниже варианте реализации выбирается исходное звено, начало и конец этого звена рассматриваются как активные конечные точки, к которым добавляются дополнительные звенья, наращивая сегмент линии контура.
α
α
На Фиг. 24 показаны условия окончания линии контура. На Фиг. 24 пиксель 2402 является конечной точкой последнего звена 2404 растущего сегмента линии контура. Возможный сегмент продолжения должен попадать в диапазон углов 2406 наклона, определяемый углом наклона последнего сегмента 2404 линии контура. В одном из вариантов реализации пиксель 2402 определяется как конечный пиксель сегмента линии контура, если отсутствуют возможные сегменты продолжения r, имеющие среднее значение яркости больше, чем среднее значение яркости следующего наиболее вероятного сегмента продолжения как минимум для предельной величины 2408, или если отсутствуют возможные сегменты продолжения r, имеющие среднее значение яркости больше второго порогового значения 2410. В других вариантах реализации могут использоваться дополнительные или другие критерии завершения.
Как показывает практика, область изображения страницы, параллельная границам корешка двух страниц разворота книги и примыкающая к ним, подвержена значительно большему перспективному искажению и искривлению страницы, чем остальные части изображения страницы. На Фиг. 25 показаны особенно сильно искривленные области изображений страниц и вычисление коэффициентов корректировки. На Фиг. 25 показаны два изображения страницы 2502 и 2504 под соответствующим изображением разворота книги 2506. Особенно сильно искаженные области 2508 и 2510 двух изображений страниц 2502 и 2504 находятся на узкой полосе пикселей шириной  Для исправления дополнительного перспективного искажения на данных узких полосках углы наклона, вычисленные моделью ƒ(x,y) для пикселей в данных узких областях, изменяются путем умножения на коэффициент левой страницы 2512 и коэффициент правой страницы 2514. Данные коэффициенты имеют значения, которые зависят от горизонтального положения пикселя в узкой области, при этом значение коэффициента увеличивается с 1,0 вдоль пунктирных линий 2516 и 2518 до 2,0 вдоль прилегающей к корешку границе изображения. Таким образом, модель ƒ(x,y) и(или) исходная карта углов наклона изменяется, чтобы принять во внимание особенно сильно искаженные области 2508 и 2510.
На Фиг. 26A-F показано выпрямление изгибов текстовых строк на изображении страницы для получения прямолинейных текстовых строк с использованием карты углов наклона, в которой с каждым пикселем на изображении страницы соотнесен некий угол наклона. На Фиг. 26А показана информация, получаемая в результате выполнения описанных ранее этапов обработки. Данная информация включает выровненное изображение 2602 страницы, как в оттенках серого, так и в цвете, если исходное изображение было получено в цвете, а также карту углов наклона 2604. Эта информация используется для формирования исправленного изображения, в котором текстовые строки и знаки и символы в текстовых строках имеют нормальную организацию плоской прямоугольной страницы. Как показано на Фиг. 26В, на заключительных этапах выпрямления искривленных текстовых строк информация о яркости и координаты пикселя на изображении 2606 страницы и угол наклона для данного пикселя а 2608 совмещаются 2610 вместе с получением координат нового положения пикселя 2612 на исправленном изображении. Этот пиксель затем переносится или копируется на данное новое положение 2614 на исправленном изображении. Перенос пикселя означает, что значение яркости данного пикселя копируется на новое местоположение на исправленном изображении страницы.
i
i
x,y
i
i
i
i
i
i
i
i
На Фиг. 26C-F приведено более подробное описание того, как изображение страницы и карта углов наклона используются для определения положений на исправленном изображении, на которое переносятся пиксели из изображения страницы. Как показано на Фиг. 26С, на первом этапе осуществляется вычисление локальных смещений Δx и Δy каждой ячейки g в прямоугольной сетке, наложенной на сетку пикселей изображения страницы. Прямоугольная сетка 2620 обычно имеет ячейки шириной и высотой g, где g - это четный делитель ширины и высоты пикселя. Другими словами, локальные смещения вычисляются на более высоком уровне дробления, чем сетка пикселей. Конечно, в альтернативных вариантах реализации вместо этого для пикселей могут вычисляться локальные смещения. На Фиг. 26С показан квадратный пиксель 2622 с более темными линиями границ, чем линии границ ячеек в прямоугольной сетке 2620. Смещения для ячейки i 2624 вычисляются в примере, показанном на Фиг. 26С. Ячейка 2624 имеет координаты (x,y) по отношению к сетке ячеек 2620 и координаты (х',y') по отношению к сетке ячеек в пределах области пикселя 2622. Угол наклона  ячейки 2624 может быть вычислен непосредственно с помощью модели 2626, либо, в качестве альтернативного варианта, ей может быть присвоен угол наклона пикселя 2622, внутри которого она находится. Промежуточное значение Δy' для Δy вычисляется как g tan  2628. Наконец, функция k(), предоставляемая вместе с аргументом x=gx+х' 2630, вычисляет смещение Δx, и с помощью значения, возвращаемого функцией k() и умноженного на промежуточное значение Δy', которое было вычислено из угла наклона 2632, получается смещение Δy. Вычисления, показанные на Фиг. 26С, повторяются по каждой ячейке в прямоугольной сетке ячеек 2620 с формированием карты смещений, при этом каждой ячейке i в прямоугольной сетке ячеек присваивается два смещения: Δx и Δy.
а
top
bottom
i
i
На Фиг. 26D показан один из вариантов реализации функции k(), используемой для формирования смещений ячеек, как описано со ссылкой на Фиг. 26С. Как показано на Фиг. 26D, функция k вычисляет значение k() для ячейки i 2636. Данная ячейка находится в колонке ячеек 2638, проходящей по всему изображению страницы. Верхняя ячейка 2640 и нижняя ячейка 2642 данной колонки используются функцией k() для вычисления значения, возвращаемого функцией k(). Углы наклона, вычисленные для данных верхней и нижней ячеек, используются для построения сходящихся векторов  и b 2644-2645 или сходящихся векторов 2646 и 2647, которые формируют треугольник на правой стороне колонки ячеек, соответственно, с углом β 2648. Для правостороннего либо левостороннего треугольника с помощью выражения 2650 вычисляется косинус данного угла. Следует отметить, что в показанном примере α является отрицательным углом, α является положительным углом. Правосторонний треугольник подходит для левой страницы разворота книги, а левосторонний треугольник - для правой страницы разворота книги. Затем функция k() возвращает дробь ширины g ячейки, разделенной на ширину Р пикселя, умноженную на максимальное значение из косинуса угла β и 0,4 (2652 на Фиг. 26D). Значение, возвращаемое функцией k(), отражает степень сжатия символов в изогнутых текстовых строках, которое наиболее выражено в наиболее изогнутых частях текстовых строк, расположенных ближе всего к границам страницы. Таким образом, смещения Δx и Δy, вычисленные на Фиг. 26С, учитывают как искривление текстовых строк, так и сжатие текстовых строк из-за данного искривления. Если векторы не сходятся, функция возвращает 1/g.
r
r
r
r
r
r
r
На Фиг. 26Е показано, как вычисленные смещения используются для переноса пикселя в исходном местоположении на изображении страницы на, как правило, другое местоположение на исправленном изображении. Прямоугольник 2656 представляет собой изображение страницы, а прямоугольник 2658 - исправленное изображение. На изображении 2656 страницы выбирается одна или более опорных точек 2660-2662 и соответствующие опорные точки 2664-2666 на исправленном изображении 2658. Опорные точки - это точки, для которых могут быть вычислены координаты на исправленном изображении. В качестве одного из возможных примеров в качестве опорной точки может быть выбрана центральная точка на изображении страницы возле определенного знака или символа на исходном изображении, так как можно легко найти соответствующую ей точку на исправленном изображении. В примере, показанном на Фиг. 26Е, опорная точка 2660 имеет координаты X,Y, а соответствующая опорная точка 2664 имеет координаты на исправленном изображении (X', Y'). Рассмотрим пиксель 2668 с координатами (x,y) справа от опорной точки 2660. Для пикселя 2668 с помощью выражения 2670 могут быть вычислены относительные координаты x и y. Это относительные координаты данного пикселя по отношению к опорной точке на исправленной изображении. Из-за вызванного искривлением сжатия пиксель необходимо переместить правее. Затем пиксель 2668 помещается в свое положение 2672 на исправленном изображении относительно опорной точки 2664 на исправленном изображении в координатах (X'+x, Y'+y). В выражениях 2670 относительное положение пикселя по отношению к опорной точке на исправленном изображении (x, y) вычисляется как относительное положение данного пикселя по отношению к опорной точке на изображении страницы 2656 (x-X, y-Y) плюс смещение (Δx, Δy). Вычисление данных смещений показано в нижних частях Фиг. 26Е 2674. Две опорные точки 2660 и 2664 показаны на сетке 2676 ячеек большей степени дробления, описанной выше со ссылкой на Фиг. 26С. Смещение Δx 2678 вычисляется как сумма локальных смещений, соотнесенных с каждой из ячеек между опорной точкой 2660 и опорной точкой 2664. Смещение Δy 2680 вычисляется аналогичным образом. Для пикселей слева от опорной точки в формуле для x Δx вычитается, а не прибавляется.
На Фиг. 26F показан процесс переноса пикселя в целом. Из каждой опорной точки 2660-2662 на изображении страницы пиксели переносятся из указывающих направо 2682 и указывающих налево 2684 горизонтальных векторов пикселей, исходящих от опорной точки, на исправленное изображение 2658 способом, описанным выше со ссылкой на Фиг. 26Е. Затем на исправленное изображение переносятся следующие пиксели выше 2680 и ниже 2688 в опорной точке и затем переносится горизонтальная строка пикселей, включающая эти следующие два пикселя, способом, описанным выше со ссылкой на Фиг. 26Е. Данный подход применяется ко всем опорным точкам 2660-2662 до тех пор, пока не будут перенесены все пиксели. В качестве альтернативного варианта может использоваться одна опорная точка, и перенос пикселей из изображения страницы на исправленное изображение может осуществляться исходя из векторов от единственной опорной точки к каждому из пикселей на изображении страницы, при этом смещения вычисляются вдоль векторов положения пикселей с учетом длины пути грубых ячеек сетки ячеек. Как правило, карта смещений, будь то фактически сформированная или рассматриваемая теоретически, содержит достаточную информацию для переноса пикселей из изображения страницы в исправленное изображение, так чтобы в результате данного переноса перспективные искажения текстовых строк на изображении страницы были исправлены на исправленном изображении, при этом символы и знаки на исправленном изображении имели нормальную организацию прямоугольной матрицы с прямыми неизогнутыми текстовыми строками.
На Фиг. 26G показан альтернативный способ выпрямления текстовых строк на изображении страницы. На Фиг. 26G используются те же самые иллюстрации, что и на рассмотренной ранее Фиг. 19А. При использовании альтернативного способа, из линий контура, представляющих текстовые строки на изображении страницы, извлекаются данные другого типа. На Фиг. 26G линии контура создаются из затравочных пикселей на изображении страницы, показанных на изображении 2664 страницы. Как показано на вставке 2666, для данной линии контура 2668 вычисляется максимальное значение у 2669 и минимальное значение у 2670, из которых вычисляется медианное или среднее значение у, medianY 2672, как сумма минимального значения у и разности между максимальным значением у и минимальным значением у, деленной на 2. Затем может быть вычислено смещение d(x,y) центроида 2674 для каждого звена 2676, как разность между значением у для средней точки звена и вычисленного медианного значения у для линии контура, содержащей это звено. Таблица 2676 с данными содержит координаты (x,y) средних точек и вычисленное смещение для каждого звена. Затем применяется согласование данных, аналогичное примененному для извлеченных данных, обсуждавшихся ранее со ссылкой на Фиг. 19А, для создания функции ƒ(x,y), которая возвращает вычисленное смещение для каждой точки (x,y) на изображении страницы 2678. И снова, как и в предыдущем способе согласования данных, эта функция представляет собой полиномиальную функцию 2680.
Иллюстрация блок-схемы одного из вариантов реализации способов и систем настоящего изобретения
На Фиг. 27A-U представлены блок-схемы, иллюстрирующие один из вариантов реализации способа исправления перспективного искажения текстовых строк на изображениях текста, снятых мобильными устройствами и другими видами оборудования, приборами получения содержащего текст изображения. Данный способ может быть реализован на базе мобильных вычислительных приборов, в том числе смартфонов, а также на других вычислительных платформах с целью обработки содержащих текст изображений при их подготовке к оптическому распознаванию символов. Следует вновь подчеркнуть, что машинные команды, которые вместе представляют собой вариант реализации данного способа в определенных устройствах, приборах и вычислительных платформах, являются полностью иллюстрированными физическими компонентами данных устройств, приборов и вычислительных платформ, в которые они включены. Хранящиеся в физической памяти машинные команды представляют собой большинство систем управления машинами в современном мире, вытеснив устаревшие схемные и электромеханические системы управления. Сейчас трудно найти электронное устройство, которое работало бы на каком-либо функциональном уровне без хранящихся в его памяти машинных команд, выполняемых на одном или более микропроцессорах или процессорах. Способы настоящего изобретения, реализованные в различных видах устройств, приборов и вычислительных платформ, тесно интегрированы с аппаратным обеспечением получения цифровых изображений и компонентами управления, модулями физической памяти и многими другими внутренними компонентами данных устройств, приборов и вычислительных систем, и могли бы выполняться вручную или в любом другом контексте, помимо таких устройств, приборов и вычислительных систем, в которые они включены.
На Фиг. 27А приведена блок-схема одного из вариантов реализации общего способа обработки изображений страниц книг и других содержащих текст изображений. На этапе 2702а осуществляется получение изображения разворота книги вместе со ссылками на место хранения изображений двух страниц Р1 и Р2. На этапе 2702b вызывается подпрограмма "начальная обработка", которая осуществляет операции удаления шума, определения границ, определения контуров страниц и вертикального выравнивания границ двух изображений страниц, созданных из полученного изображения разворота книги, как описано выше со ссылкой на Фиг. 14А-15В. В случае неудачи начальной обработки, что определяется на этапе 2702 с, на этапе 2702d возвращается значение false (ложь). В противном случае в цикле for на этапах 2702е-2702i каждое из изображений страницы Р1 и Р2, сформированных подпрограммой начальной обработки, обрабатываются посредством вызова подпрограммы "обработать страницу" на этапе 2702f.
На Фиг. 27В показана блок-схема подпрограммы "начальная обработка", вызываемой на этапе 2702b на Фиг. 27А. На этапе 2704а подпрограмма получает изображение книги и ссылки на участки памяти, отведенные для изображений страницы Р1 is.P2. Если полученное изображение является цветным, что определяется на этапе 2704b, данное цветное изображение преобразуется на этапе 2704 с в монохромное изображение способом, описанным выше со ссылкой на Фиг. 6. На этапе 2704d данное изображение сглаживается с помощью Гауссова ядра или медианного фильтра, описанных выше со ссылкой на Фиг. 10-12. На этапе 2704е из сглаженного изображения формируется карта градиентов, как описано выше со ссылкой на Фиг. 14А-С. Карта градиентов фильтруется с помощью методики подавления немаксимумов, описанной выше со ссылкой на Фиг. 14В, а также посредством фильтрации установленных границ, исходя из длины и других геометрических параметров с получением карты границ на этапе 2704f. На этапе 2704g из границ в карте границ, сформированной на шаге 2704f с использованием дополнительных характеристик страниц книги, распределения цветов на изображении и других геометрических данных, строится контур страницы. Если на изображении не удается установить две страницы, что определяется на этапе 2704h, то на этапе 2704i возвращается значение false (ложь). В противном случае на этапе 2704j каждое из подызображений страницы, установленных на этапе 2704g, преобразуется в изображение страницы Р1 и Р2, затем на этапе 2704k изображения вращаются, так чтобы прилегающая к корешку граница совпадала с вертикальной осью изображения страницы. Затем в цикле for этапов 2704l-2704n вызывается подпрограмма "выровнять изображение страницы" на этапе 2704m, которая осуществляет обработку каждого из двух изображений страницы Р1 и Р2.
На Фиг. 27С приведена блок-схема подпрограммы "выровнять изображение страницы", вызываемой на этапе 2704m на Фиг. 27В. Данная подпрограмма выполняет процедуру, описанную выше со ссылкой на Фиг. 15В. На этапе 2706а подпрограмма определяет угол наклона α не прилегающей к корешку границы страницы. Если α меньше порогового угла, что определяется на этапе 2706b, то дальнейшая обработка не требуется, и на этапе 2706с подпрограмма завершается. В противном случае на этапе 2706d подпрограмма определяет точку пересечения между границей страницы, параллельной корешку, но не прилегающей к нему, и верхней границей страницы (точка 1522 на Фиг. 15В). На этапе 2706е подпрограмма определяет ширину и высоту изображения страницы в пикселях. В цикле for этапов 2706f-2706n осуществляется обработка каждой горизонтальной строки пикселей на части изображения страницы, которая представляет собой данную страницу. На этапе 2706g определяется точка, в которой граница страницы, параллельная корешку, но не прилегающая к нему, пересекается с данной строкой пикселей (1524 на Фиг. 15В). Затем на этапе 2706i или 2706j определяются длины трех сегментов горизонтальной строки, описанной со ссылкой на Фиг. 15В. На этапе 2706k определяется число пикселей, подлежащих удалению из области страницы. Затем, на этапе 2706l и 2706m дублируются определенные пиксели в не относящейся к странице части горизонтальной строки пикселей и удаляются определенные пиксели в относящейся к странице части горизонтальной строки пикселей, как показано на Фиг. 15В.
На Фиг. 27D приведена блок-схема подпрограммы "обработать страницу", вызываемой на этапе 2702f на Фиг. 27А. На шаге 2705а процедура "обработать страницу" получает ссылку на изображение страницы р. На шаге 2705b процедура "обработать страницу" вызывает функцию "определить ориентацию текстовых строк" для определения правильной ориентации страницы, как обсуждалось ранее со ссылкой на Фиг. 16A-D. На шаге 2705 с процедура "обработать страницу" вызывает процедуру "нормализовать границы страницы и строки текста" для изменения ориентации текста на изображении страницы в соответствии с определенным углом поворота, полученным из функции "определить ориентацию текстовых строк". Сюда может относиться поворот содержимого изображения страницы внутри границ страницы, а также некоторое кадрирование, выравнивание границ страницы и другие настройки для получения нормализованного изображения страницы с приблизительно горизонтальными строками текста. На шаге 2705d процедура "обработать страницу " вызывает процедуру "определить текстовые строки" для получения темных полос (1804 на Фиг. 18А) в бинаризованной копии изображения страницы для обозначения формы и области каждой из текстовых строк на изображении страницы или, что аналогично, создания описания границ каждой области, содержащей текст. На шаге 2705е процедура "обработать страницу" вызывает процедуру "создать контуры" для создания линий контуров (1810 на Фиг. 18А) для каждой полосы или области, содержащей текст, на изображении страницы. На шаге 2705f процедура "обработать страницу" вызывает процедуру "создать карту углов" для создания математической модели для углов наклона на изображении страницы, как обсуждалось ранее со ссылкой на Фиг. 19А-С. На шагах 2705g-2705i процедура "обработать страницу" вызывает процедуры "карта смещений" и "завершить" для преобразования изображения страницы в изображение страницы с прямыми горизонтальными строками текста.
1
2
1
2
На Фиг. 27Е-F приведены блок-схемы, иллюстрирующие один из вариантов реализации процедуры "определить ориентацию текстовых строк", вызываемой на шаге 2705b Фиг. 27D. Эта реализация в общем обсуждалась выше со ссылкой на Фиг. 16A-D. На шаге 2706а переменная bestAngle получает значение "0", а локальная переменная bestVariance получает значение некоторого большого целого числа. Далее в цикле for на шагах 2706b-2706f каждый из n углов рассматривается в качестве угла, представляющего правильную ориентацию страницы, как обсуждалось со ссылкой на Фиг. 16A-D. На шаге 2706с вычисляется дисперсия для изображения страницы, ориентированной по текущему вычисленному углу наклона. Если вычисленная дисперсия меньше значения, хранящегося в локальной переменной bestVariance, что определяется на шаге 2706d, то на шаге 2706е локальная переменная bestAngle получает значение текущего рассматриваемого угла наклона, а локальная переменная bestVariance получает значение дисперсии, вычисленной на шаге 2706с. На шаге 2706g изображение страницы поворачивается на наилучший угол наклона, определенный в цикле for на шагах 2706b-2706f. На шаге 2706h к нескольким выбранным символам из текстовых строк в изображении страницы применяется метод OCR (оптического распознавания символов) и вычисляется отношение r, как отношение числа распознанных символов к общему количеству символов, к которым был применен метод OCR. На шаге 2706i страница поворачивается на 180°, и на шаге 2706j к выбранным символам снова применяется метод OCR для вычисления второго отношения r числа распознанных символов к общему числу символов. Если r больше, чем r, что определяется на шаге 2706k, на шаге 2706l возвращается угол, сохраненный в локальной переменной bestAngle. В противном случае на шаге 2706m возвращается угол, сохраненный в локальной переменной bestAngle, минус 180°. Следует учитывать, что во всех блок-схемах предполагается, что для углов используются только значения по модулю, то есть в арифметических операциях, таких как вычитание одного угла из другого, участвуют только положительные углы со значением от 0° до 359°. Кроме того, если параметры не передаются явным образом, предполагается, что вызываемая процедура выполняется в области видимости вызывающей процедуры, и поэтому имеет доступ к переменным, объявленным в вызывающей процедуре или в ее области видимости.
На Фиг. 27F приведена блок-схема подпрограммы "вычислить дисперсию", вызываемой на шаге 2706с на Фиг. 27Е. На шаге 2707а изображение страницы поворачивается на текущий рассматриваемый угол наклона, определенный в цикле for на шагах 2706b-2706f на Фиг. 27Е. На шаге 2707b инициализируется таблица данных, например, таблица данных 1616 на Фиг. 16В. Во вложенном цикле for на шагах 2707c-2707j таблица данных заполняется с учетом того, что содержится в каждом блоке каждого столбца -пиксели символов или только пиксели фона. Блоки, содержащие только пиксели фона, считаются блоками фона, а остальные блоки считаются блоками, содержащими символы, как обсуждалось ранее со ссылкой на Фиг. 16В. После оценки всех блоков столбца на шаге 2707i вычисляется отношение b/c для этого столбца. После создания всех данных для двух первых строк таблицы данных, во вложенном цикле for на шагах 2707с-2707h на шаге 2707k вычисляется среднее значение и дисперсия вычисленных отношений блоков фона к блокам, содержащим символы для каждого столбца. Дисперсия возвращается на шаге 2707l.
На Фиг. 27G приведена блок-схема подпрограммы "определить текстовые строки", вызываемой на шаге 2705d на Фиг. 27D. На шаге 2708а подпрограмма "определить текстовые строки " копирует изображение страницы р в страницу tl_page и бинаризует страницу tl_page. На шаге 2708b, процедура "определить текстовые строки" применяет к странице tl_page последовательность из одной или более морфологических операций для генерации темных полос, соответствующих строкам текста, как обсуждалось ранее со ссылкой на Фиг. 16А. На шаге 2708 с процедура "определить текстовые строки " применяет операцию вертикального сглаживания, которая обсуждалась ранее со ссылкой на Фиг. 16. И наконец, в некоторых вариантах реализации на шаге 2708d страница tl_page используется как растровое изображение текстовых строк, в других вариантах реализации границы областей текстовых строк создаются на базе содержимого страницы tl_page. Для растрового изображения текстовых строк любой заданный пиксель на изображении страницы р может быть определен, исходя из страницы tl_page, как пиксель текстовой строки или пиксель фона.
На Фиг. 27Н приведена блок-схема подпрограммы "создать контуры", вызываемой на этапе 2705е на Фиг. 27D. На шаге 2710а локальная переменная numSeeds получает значение "0," переменная множества seeds устанавливается в пустое множество, и на странице s_page все пиксели получают значение "1". На шаге 2710b вызывается процедура "получить затравочные пиксели" для создания затравочных пикселей для каждой текстовой строки. На шаге 2710 с локальные переменные множеств active, term и non_term устанавливаются в нулевые множества, а локальные переменные numActive, numTerm и numNon_term получают значение "0". На шаге 2710d вызывается процедура "инициировать контуры" для инициирования создания линии контура из каждого затравочного пикселя. В цикле for на шагах 2710е-2710g вызывается процедура "наращивать контуры", вызов производится итеративно до тех пор, пока не останется активных сегментов линий контуров, которые можно продлить. Затем на шаге 2710h вызывается процедура "сократить число контуров", чтобы выполнить сокращение числа звеньев контуров и дополнительно обработать линии контура, созданные при продлении сегментов линий контура в цикле for на шагах 2710е-2710g.
На Фиг. 271 приведена блок-схема подпрограммы "получить затравочные пиксели", вызываемой на этапе 2710b на Фиг. 27Н. В цикле for на шагах 2712а-2712d рассматривается каждая область текстовой строки, обнаруженная на странице tl_page. Для каждой рассматриваемой области строки текста пиксели копируются из изображения страницы р на страницу s_page. Значения пикселей имеют определенные границы, так что пиксели символов имеют значение "0", а пиксели, не входящие в символы, имеют значение "1". Затем на шаге 2712 с вызывается процедура "создать затравочные пиксели для текстовой строки" для создания некоторого количества затравочных пикселей для рассматриваемой в настоящий момент текстовой строки.
На Фиг. 27J приведена блок-схема подпрограммы "создать затравочные пиксели для текстовой строки"", вызываемой на этапе 2712 с на Фиг. 271. В цикле for на шагах 2714а-2714f каждое из n различных ядер NMS применяется к странице s_page, до тех пор, пока все ядра NMS не будут исчерпаны, или применение ядер NMS не позволит сформировать требуемое количество затравочных пикселей для строки текста. На шаге 2714b рассматриваемое в настоящий момент ядро NMS применяется к рассматриваемой в настоящий момент строке текста в цикле for на шагах 2712а-2712d на Фиг. 271. На шаге 2714 с определяется множество пикселей со значением 0, оставшихся в тексте, и мощность r множества пикселей со значением 0, оставшихся в тексте. Если r больше первого порога или меньше второго порога, что определяется на шаге 2714d, и если еще остались не рассмотренные ядра NMS, что определяется на шаге 2714е, строка текста, скопированная на страницу s_page, восстанавливается на шаге 2714f со страницы tl_page, и производится очередная итерация цикла for на шагах 2714а-2714f. Если не осталось неиспользованных ядер NMS, что определяется на шаге 2714е, то при условии, что r больше первого порогового значения, что определяется на шаге 2714g, на шаге 2714h из оставшихся пикселей со значением 0 выбираются пиксели со значением 0 в количестве, равном первому пороговому значению, в качестве затравочных пикселей для строки текста. В противном случае на шаге 2714i из оставшихся пикселей со значением 0 выбираются пиксели со значением 0 в количестве, равном второму пороговому значению, в качестве затравочных пикселей для строки текста. Множество пикселей со значением 0, полученное в цикле for на шагах 2714а-2714f, на шаге 2714j добавляется к множеству seeds.
На Фиг. 27K приведена блок-схема процедуры «первое звено». Эта процедура создает первое звено для затравочного пикселя. На шаге 2716а процедура "первое звено" получает координаты (x,y) затравочного пикселя. На шаге 2716b процедура "первое звено" задает значение локальной переменной range для диапазона углов от 0° до 359°. На шаге 2716 с процедура "первое звено" вызывает процедуру "найти звено" для создания исходного звена для затравочного пикселя. Если процедура "найти звено" не в состоянии вернуть правильные координаты (x,y) конечной точки следующего звена, что определяется на шаге 2716d, процедура "первое звено" прекращает работу. После окончания процедура "первое звено" исключает полученный затравочный пиксель из дальнейшей обработки. В противном случае на шаге 2716е локальная переменная а получает значение угла для исходного звена, возвращенное процедурой "найти звено". Если возвращаемый угол указывает на то, что звено направлено вправо, что определяется на шаге 2716f, активные конечные точки правого звена на шагах 2716g и 2716i-2716k добавляются в множество active. В противном случае на шагах 2716g и 2716i-2716k в множество active добавляются активные конечные точки левого звена. На иллюстрации активная конечная точка представлена в виде записи в множестве active, которая содержит координаты x,y конечной точки, угол наклона звена, содержащего эту конечную точку, и его направление.
На Фиг. 27L показана блок-схема процедуры "найти звено", вызываемой на шаге 2716с на Фиг. 27K. Процедура "найти звено" выполняет попытку определения нового звена для пикселя с исходными координатами (x,y), получаемыми на шаге 2718а, в диапазоне углов наклона, передаваемом через аргумент процедуры range, получаемый на шаге 2718а. На шаге 2718b процедура "найти звено" задает значения локальных переменных besta, равное - 10, bestC, равное (-1, -1) и bestVal, равное 0. Локальная переменная besta содержит угол наклона лучшего вероятного звена, обнаруженного к этому моменту процедурой "найти звено", локальная переменная bestC содержит координаты конечной точки лучшего вероятного звена, обнаруженного к этому моменту процедурой "найти звено", а локальная переменная bestVal содержит среднее значение яркости лучшего вероятного звена, обнаруженного к этому моменту процедурой "найти звено". В цикле for на шагах 2718с-2718i оценивается каждое вероятное звено с углом наклона в диапазоне range. В цикле for на шагах 2718с-2718i оценивается набор вероятных звеньев с углами наклона в диапазоне range. Оценка включает вычисление координат конечной точки вероятного звена на шаге 2718d, проверку того, что все пиксели, принадлежащие звену, относятся к одной текстовой строке, что определяется по растровому изображению текстовой строки tl_page на шаге 2718е, и вычисление среднего значения яркости I пикселей, относящихся к вероятному звену, по изображению страницы р. Если вычисленное среднее значение яркости I больше, чем значение, хранящееся в локальной переменной bestVal, рассматриваемое в данный момент вероятное звено является наилучшим вероятным звеном из рассмотренных, и поэтому на шаге 2718h значения, сохраненные в локальных переменных besta, bestC и bestVal обновляются, чтобы описывать рассматриваемое в данный момент вероятное звено. После того, как цикл for на шагах 2718с-2718i заканчивается, возвращаются значения, сохраненные в переменных bestα и bestC. Следует учитывать, что при отсутствии вероятного звена, удовлетворяющего требованиям для следующего звена, возвращаемые значения будут представлять собой некорректные значения, которыми локальные переменные были инициализированы на шаге 2718b.
На Фиг. 27М приведена блок-схема подпрограммы "инициировать контуры, вызываемой на этапе 2710d на Фиг. 27Н. В цикле for на шагах 2720а-2720с вызывается процедура "первое звено", описанная выше со ссылкой на Фиг. 27K, для добавления исходного звена к каждому затравочному пикселю в переменной множества seeds.
а
а
а
а
а
а
а
а
а
а
а
а
На Фиг. 27N показана блок-схема процедуры "наращивать контуры", вызываемой на этапе 2710f на Фиг. 27Н. Процедура "наращивать контуры" рассматривает каждую активную конечную точку  в множестве active в цикле for на шагах 2722а-2722u, и делает попытку добавить новое звено к каждой из активных конечных точек. Если направление текущей рассматриваемой точки  – right (вправо), что определяется на шаге 2722b, на шагах 2722с-2722h определяется диапазон углов наклона для вероятного звена, добавляемого для добавления к активной конечной точке . Этот диапазон вычисляется в настоящем варианте реализации, чтобы убедиться, что активная точка  будет продолжена вправо. В альтернативных вариантах реализации диапазон углов наклона может вычисляться в соответствии с альтернативными критериями. Если направление текущей рассматриваемой точки  - left (влево), что определяется на шаге 2722b, на шагах 2722i-2722m определяется диапазон углов наклона для вероятного звена, добавляемого для добавления к активной конечной точке . На шаге 2722о вызывается процедура "найти звено", описанная ранее со ссылкой на Фиг. 27L, для поиска наилучшего звена для продления рассматриваемой в настоящий момент активной конечной точки . Если процедура "найти звено" возвращает правильные параметры следующего звена, что определяется на шаге 2722р, на шаге 2722q звено, соответствующее рассматриваемой в данный момент активной конечной точке , добавляется в множество non_term, а на шаге 2722r рассматриваемая в данный момент активная конечная точка  в множестве active обновляется, меняясь на конечную точку нового звена. На шаге 2722s вызывается процедура "проверить соединение" для присоединения нового звена к конечному звену другого сегмента линии контура, если конечная точка этого конечного звена находится на расстоянии меньше порогового расстояния от конечной точки нового звена. Если процедура "найти звено" не в состоянии вернуть корректные параметры нового звена, что определяется на шаге 2722р, рассмотрение текущей активной конечной точки  прекращается на шаге 2722t, посредством добавления текущей активной конечной точки  в множество term и удаления текущей активной конечной точки  из множества active.
а
а
а
а
На Фиг. 27O показана блок-схема процедуры "проверить соединение", вызываемой на шаге 2722s на Фиг. 27N. Во многих реализациях изобретения эта процедура может отсутствовать, поскольку на страницах с текстом, расположенным в несколько столбцов, объединение контуров может привести к образованию контуров, охватывающих несколько столбцов. Однако в некоторых реализациях может использоваться соединение контуров, описанное со ссылкой на Фиг. 27O. На шаге 2724а процедура "проверить соединение" производит поиск последнего звена на предельном расстоянии от текущей активной конечной точки  в цикле for на шагах 2722а-2722u на Фиг. 27N. Если найдено активное звено, которое имеет направление, противоположное текущей активной конечной точке , что определяется на шагах 2724b-2724с, текущая активная точка  присоединяется к найденному активному звену в ходе шагов 2724d-2724f. Иллюстрируемый вариант реализации предполагает, что для этого потребуется дополнительное соединяющее звено с. Однако в случае, подобном приведенному на Фиг. 18С, звено, соответствующее текущей активной конечной точке , и найденное звено могут быть соединены посредством поворота одного или обоих звеньев без необходимости создания соединительного звена с.
На Фиг. 27Р показана блок-схема процедуры "сократить число контуров", вызываемой на этапе 2710h на Фиг. 27Н. Процедура "сократить число контуров" на шаге 2726а преобразует звенья из множеств term и non_term в связные списки звеньев, так что каждый связный список содержит линию контура и представляет, а также содержит, строку текста с изображения страницы р. В описываемой реализации выделяется массив Cntr ссылок на эти связные списки, причем количество ссыпок хранится в переменной num_text. Это преобразование получается непосредственно при рассмотрении каждого конечного звена с направлением left (влево) в множестве term и продляет звено звеньями из множества non_term, после чего продляет последнее звено конечным звеном с направлением right (вправо) из множества term. В альтернативных реализациях изобретения для хранения звеньев, соответствующих строкам текста, вместо связных списков могут использоваться массивы записей о звеньях. На шаге 2726b определяются пары линий контуров, представленных связными списками, которые приближаются друг к другу на расстояние меньше предельного, и более короткий из двух контуров извлекается из массива Cntr и удаляется. Обычно рассматривается одна линия контура для каждой текстовой строки на изображении страницы р. В альтернативных реализациях может производиться дополнительная обработка. Например, с помощью сплайн-функций или другими способами для создания полных линий контуров из сегментов линий контуров могут присоединяться не присоединенные ранее сегменты линии контура. Кроме того, над линиями контура могут выполняться операции сглаживания, так, чтобы они представляли собой сглаженные непрерывные кривые без резких поворотов или разрывов.
На Фиг. 27Q приведена блок-схема процедуры "создать карту углов". Эта процедура реализует логику создания модели искривления, обсуждавшуюся выше со ссылкой на Фиг. 19А-С. На шаге 2728а выделяется и инициализируется таблица данных (1912 на Фиг. 19А). В цикле for на шагах 2728b-2728е вычисляются и сохраняются в таблице данных углы наклона и средние точки звеньев контура для контуров, находящихся в массиве Cntr. На шаге 2728g к данным в таблице данных применяется способ согласования данных для создания полиномиального выражения, которое вычисляет тангенс угла наклона для каждой точки изображения страницы р. На шаге 2728h подготавливается карта углов посредством вычисления тангенса угла наклона для каждой точки изображения страницы р. Затем на шаге 2728i производится настройка углов наклона для отдельной области, как обсуждалось выше со ссылкой на Фиг. 25.
i
i
На Фиг. 27R приведена блок-схема процедуры "карта смещений", вызываемой на этапе 2705g на Фиг. 27D. На шаге 2734а процедура получает ссылку на пустую карту смещений и карту углов, созданную процедурой "создать карту углов". Как описано выше со ссылкой на Фиг. 26С, карта смещений может иметь прямоугольную сетку с более высоким уровнем разбиения, чем у сетки пикселей изображения страницы. В цикле for этапов 2734b-2734h для каждой ячейки i на карте смещений вычисляется значение смещения. Данная операция вычисления выполняется в соответствии со способом, описанным выше со ссылкой на Фиг. 26С и 26D. На этапах 2734с-2734f для рассматриваемой в текущий момент ячейки i вычисляется коэффициент к, как описано выше со ссылкой на Фиг. 26D. На этапе 2734g для ячейки i, в соответствии со способом, описанным выше со ссылкой на Фиг. 26С, вычисляются локальные смещения Δx и Δy.
На Фиг. 27S приведена блок-схема процедуры "завершить", вызываемой на шаге 2705h Фиг. 27D. Эта процедура реализует способ переноса пикселей, описанный со ссылкой на Фиг. 26E-F, для создания исправленного изображения из изображения страницы и карты смещений, полученной в процедуре "карта смещений". На шаге 2736а производится получение изображения страницы и карты смещений. На этапе 2736b назначается пустая страница tPage, и не относящиеся к странице пиксели на изображении страницы копируются в tPage. На этапе 2736с определяется множество опорных точек, а на этапе 2736d определяются их местоположения на изображении страницы, а также страница tPage, которая будет содержать исправленное изображение страницы, как описано выше со ссылкой на Фиг. 26Е. В трижды вложенных циклах for этапов 2736е-2736k осуществляется перенос пикселей из изображения страницы на исправленное изображение, как описано со ссылкой на Фиг. 26F. Для переноса пикселей из изображения страницы на исправленное изображение страницы каждая точка в вертикальном диапазоне, или вертикальной окрестности, вокруг каждой опорной точки расширяется вправо и влево. Каждый пиксель переносится посредством вызова подпрограммы "перенести пиксели" на этапе 2736h.
На Фиг. 27Т приведена блок-схема подпрограммы "перенести пиксели", вызываемой на этапе 2736h на Фиг. 27S. На этапе 2738а подпрограмма получает ссылки на изображение страницы и исправленное изображение tPage, координаты пикселя i на изображении страницы, координаты соответствующего пикселя k на исправленном изображении, направление, в котором осуществляется прослеживание вокруг опорной точки или точки в вертикальной окрестности опорной точки для переноса пикселя, а также карту смещений. Локальные переменные sum_y и sum_x на этапе 2738b принимают значение 0. Затем в цикле for этапов 2738с-2738g каждый пиксель j в горизонтальной строке пикселей (начиная с пикселя i и до границы страницы) в направлении d переносится из изображения страницы на исправленное изображение tPage. На этапе 2738е вычисляется локальное смещение пикселя j посредством добавления локальных смещений к локальным переменным sum_y и sum_x, а затем на этапе 2738f вычисляется положение данного пикселя на исправленном изображении, и значение яркости данного пикселя переносится из изображения страницы на исправленное изображение.
На Фиг. 27U приведена блок-схема процедуры "карта смещений". Эта процедура представляет альтернативный подход к выпрямлению текстовых строк на изображении страницы, обсуждавшийся ранее со ссылкой на Фиг. 26G, и заменяет шаги 2705f-2705h на Фиг. 27D. На шагах 2740а-2740h посредством извлечения данных из линий контуров и согласования данных аналогично обсуждавшейся ранее карте углов, вычисляется карта смещения, аналогично шагам 2728а-2728h на Фиг. 27Q. Однако, перенос пикселей с изображения страницы р на новое изображение страницы для создания выпрямленного изображения страницы на шагах 2740i-2740k значительно проще, чем способы переноса пикселей, обсуждавшиеся ранее со ссылкой на Фиг. 26А-F. Смещения на карте смещения используются для непосредственного вычисления нового положения на выпрямленном изображении страницы для каждого пикселя изображения страницы р. Разумеется, может выполняться дополнительная обработка для изменения ориентации выпрямленного изображения и заполнения пустот или удаления перекрывающихся областей по краям страницы.
Хотя настоящее изобретение описывается на примере конкретных вариантов реализации, предполагается, что оно не будет ограничено только этими вариантами реализации. Специалистам в данной области техники будут очевидны возможные модификации в пределах сущности настоящего изобретения. Например, любые из множества различных параметров реализации и проектирования, в том числе модульная организация, язык программирования, аппаратная платформа, структуры управления, структуры данных и прочие параметры реализации и проектирования могут варьироваться для получения альтернативных вариантов реализации способов и систем настоящего изобретения. Как говорилось выше, существуют альтернативные способы, которые могут использоваться для многих, если не всех, этапов обработки, участвующих в исправлении искривления текстовых строк. Кроме того, величины различных пороговых значений, значений ширины ядра, значения степени разбиения карты изображения и другие параметры могут отличаться в различных вариантах реализации.
Следует понимать, что представленное выше описание вариантов реализации изобретения приведено для того, чтобы дать возможность любому специалисту в данной области техники воспроизвести или применить настоящее изобретение. Специалистам в данной области техники будут очевидны возможные модификации представленных вариантов реализации, при этом общие принципы, представленные здесь без отступления от сущности и объема настоящего изобретения, могут быть применены в рамках других вариантов реализации. Таким образом, подразумевается, что настоящее изобретение не ограничено представленными здесь вариантами реализации. Напротив, в его объем входят все возможные варианты реализации, согласующиеся с раскрываемыми в настоящем документе принципами и новыми отличительными признаками.