[2]В настоящем документе рассматривается обработка изображений и, в частности, способ и система для определения содержащего документ фрагмента цифрового изображения при подготовке к различным типам последующей автоматизированной обработки цифрового изображения, включая оптическое распознавание символов.
[4]Печатные документы на естественном языке до сих пор являются широко распространенным средством коммуникации между людьми, в организациях и используются для донесения информации до ее потребителей. С появлением повсеместно используемых мощных вычислительных ресурсов, включая персональные вычислительные ресурсы, реализованные в смартфонах, планшетах, ноутбуках и персональных компьютерах, а также с распространением более мощных вычислительных ресурсов облачных вычислительных сервисов, центров обработки данных и корпоративных серверов организаций и предприятий, шифрование и обмен информацией на естественном языке все чаще выполняется в виде электронных документов. Печатные документы по своей сути представляют собой изображения, в то время как электронные документы содержат последовательности цифровых кодов символов и знаков на естественном языке. Поскольку электронные документы имеют перед печатными документами преимущества по стоимости, возможностям передачи и рассылки, простоте редактирования и изменения, а также по надежности хранения, за последние 50 лет развилась целая отрасль, поддерживающая способы и системы преобразования печатных документов в электронные. Компьютерные способы и системы оптического распознавания символов совместно с электронными сканерами обеспечивают надежное и экономичное получение изображений печатных документов и компьютерную обработку получаемых цифровых изображений, содержащих текст, для создания электронных документов, соответствующих печатным.
[6]В настоящем документе рассматриваются автоматизированные способы и системы, управляемые различными ограничениями и параметрами, с помощью которых определяются содержащие документ фрагменты цифрового изображения. Некоторые из параметров ограничивают определение контура и построение гипотез о содержащем документ фрагменте цифрового изображения. С помощью способов и систем настоящего изобретения определяются контуры на цифровом изображении, выявленные контуры делятся на четыре множества контуров, соответствующих четырем различным сторонам в исходном цифровом изображении, на основе этих контуров строятся гипотезы о краях или границах фрагмента цифрового изображения, содержащего документ, и выполняется оценка гипотез для выбора гипотез с самыми высокими оценками для представления границ фрагмента цифрового изображения, содержащего документ, в исходном цифровом изображении.
[7]КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
[8]На Фиг. 1 представлена структурная схема вычислительной системы высокого уровня, например, вычислительной системы, в которой применяется раскрываемый способ определения содержащего документ фрагмента цифрового изображения.
[9]На Фиг. 2A-D показаны два разных типа портативных устройств получения изображений.
[10]На Фиг. 3 показано типовое изображение с цифровым кодированием.
[11]На Фиг. 4 показан один вариант цветовой модели RGB.
[12]На Фиг. 5 показана другая цветовая модель «оттенок-насыщенность-светлота» («HSL»).
[13]На Фиг. 6 показано формирование серого или бинарного изображения из цветного изображения.
[14]На Фиг. 7 показано дискретное вычисление градиента яркости.
[15]На Фиг. 8 показан градиент, рассчитанный для точки на непрерывной поверхности.
[16]На Фиг. 9 показан ряд примеров градиента яркости.
[17]На Фиг. 10 показано применение ядра к изображению.
[18]На Фиг. 11 показана свертка изображения.
[19]На Фиг. 12 показан некоторый пример ядра и методики обработки изображений на основе ядра.
[20]На Фиг. 13 и 14 показан общий подход к определению контура.
[21]На Фиг. 15-26 показан частный вариант реализации способа и подсистемы обнаружения контуров.
[22]На Фиг. 27A-G с помощью блок-схем показан один из вариантов реализации способа и подсистемы обнаружения контуров.
[23]На Фиг. 28 показан пример сценария обработки изображения, в котором автоматизированная система обработки изображений пытается определить содержащий документ фрагмент цифрового изображения.
[24]На Фиг. 29 показан первый этап автоматизированного процесса распознавания документов.
[25]На Фиг. 30 представлены два дополнительных этапа в процессе распознавания изображений документов.
[26]На Фиг. 31 показано построение гипотезы на основе четырех множеств контуров, рассматриваемых на Фиг. 30.
[27]На Фиг. 32 показан ряд соображений и критериев для выбора
[29]На Фиг. 33 и 34 представлен расчет значения показателя веса стороны с целью построения гипотезы.
[30]На Фиг. 35А-Е приведены блок-схемы, на которых показан вариант реализации способа и системы определения документа, к которой относится настоящий документ.
[31]ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ РЕАЛИЗАЦИИ
[32]Настоящий документ относится к способам и системам определения контуров, включая криволинейные контуры, на цифровых изображениях для использования в последующих задачах обработки цифровых изображений, включая оптическое распознавание символов. В первом подразделе ниже приводится краткое введение в архитектуру вычислительной системы, цифровые изображения и способы обработки цифровых изображений со ссылками на Фиг. 1-12. Во втором подразделе приводится подробное описание способов и систем обнаружения контуров со ссылками на Фиг. 13-27G. В итоговом подразделе приводится одна из возможных реализаций способов и систем настоящего изобретения, которая иллюстрируется блок-схемами со ссылками на Фиг. 28-35Е.
[34]На Фиг. 1 приведена схема архитектуры вычислительной системы верхнего уровня, подобной той вычислительной системе, на которой реализован раскрываемый в текущем документе способ определения содержащих документ фрагментов цифрового изображения. Мобильные устройства получения изображений, включая смартфоны и цифровые камеры, могут быть изображены на диаграмме аналогичным образом, а также могут содержать процессоры, память и внутренние шины. Знакомым с современной наукой и технологиями будет понятно, что программы или подпрограммы управления, содержащие машинные команды, которые хранятся в физической памяти устройства под управлением процессора, представляют компонент управления устройством и являются настолько же физическими, материальными и важными, как и любой другой компонент электромеханического устройства, включая устройства получения изображений. Компьютерная система содержит один или более центральных процессоров (ЦП) 102-105, один или более электронных модулей памяти 108, взаимосвязанных с ЦП через шину подсистемы ЦП/памяти 110 или несколько шин, первый мост 112, который соединяет шину подсистемы ЦП/памяти 110 с дополнительными шинами 114 и 116, либо другие виды средств высокоскоростного соединения, в том числе множественные высокоскоростные последовательные соединения. Эти шины или последовательные соединения, в свою очередь, соединяют ЦП и память со специализированными процессорами, такими как графический процессор 118, а также с одним или более дополнительными мостами 120, взаимосвязанными с высокоскоростными последовательными соединениями или несколькими контроллерами 122-127, например с контроллером 127, который предоставляет доступ к различным типам запоминающих устройств большой емкости 128, электронным дисплеям, устройствам ввода и другим подобным компонентам, подкомпонентам и вычислительным ресурсам.
[35]На Фиг. 2A-D показаны два типа портативных устройств получения изображений. На Фиг. 2А-С показана цифровая камера 202. Цифровая камера содержит объектив 204, кнопку спуска затвора 205, нажатие которой пользователем приводит к получению цифрового изображения, которое соответствует отраженному свету, поступающему в объектив 204 цифровой камеры. С задней стороны цифровой камеры, которая видна пользователю, когда он держит камеру при съемке цифровых изображений, находится видоискатель 206 и жидкокристаллический дисплей видоискателя 208. С помощью видоискателя 206 пользователь может напрямую просматривать создаваемое объективом 204 камеры изображение, а с помощью жидкокристаллического дисплея 208 - просматривать электронное отображение создаваемого в настоящей момент объективом изображения. Обычно пользователь камеры настраивает фокус камеры с помощью кольца фокусировки 210, смотря при этом через видоискатель 206 или рассматривая изображение на жидкокристаллическом дисплее 208 для выбора требуемого изображения перед нажатием на кнопку 105 спуска затвора с целью цифрового получения изображения и сохранения изображения в электронной памяти цифровой камеры.
[36]На Фиг. 2D показан типовой смартфон с передней стороны 220 и задней стороны 222. На задней стороне 222 имеется объектив 224 цифровой камеры и датчик приближения и(или) цифровой экспонометр 226. На передней стороне смартфона 220 под управлением приложения может отображаться получаемое изображение 226, аналогично работе жидкокристаллического дисплея 208 видоискателя цифровой камеры, а также сенсорная кнопка 228 спуска затвора, при прикосновении к которой происходит получение цифрового изображения и сохранение его в памяти смартфона.
[37]На Фиг. 3 показано типовое изображение с цифровым кодированием. Кодированное изображение включает двумерный массив пикселей 302. На Фиг. 3 каждый небольшой квадрат, например, квадрат 304, является пикселем, который обычно определяется как наименьшая часть детализации изображения, для которой предусматривается цифровая кодировка. Каждый пиксель представляет собой место, обычно представленное парой цифровых значений, соответствующих значениям на осях прямоугольной систем координат х и у, 306 и 308 соответственно. Таким образом, например, пиксель 304 имеет координаты х, у (39,0), а пиксель 312 - координаты (0,0). В цифровой кодировке пиксель представлен числовыми значениями, указывающими на то, как область изображения, соответствующая пикселю, представляется при печати, отображается на экране компьютера или ином дисплее. Обычно для черно-белых изображений для представления каждого пикселя используется единичное значение в интервале от 0 до 255 с числовым значением, соответствующем уровню серого, на котором передается пиксель. В общепринятом понимании значение «0» соответствует черному цвету, а значение «255» - белому. Для цветных изображений может применяться множество различных числовых значений, указывающих на цвет. В одной из стандартных цветовых моделей, показанной на Фиг. 3, каждый пиксель связан с тремя значениями или координатами (r, g, b), которые указывают на яркость красного, зеленого и синего компонента цвета, отображаемого в соответствующей пикселю области.
[38]На Фиг. 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).
[39]На Фиг. 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, при =0,0, до 1 для белого 508, при =1,0. Для произвольного цвета, представленного на Фиг. 5 точкой 514, оттенок определяется как угол θ 516, между первым вектором из исходной точки 513 к точке 502 и вторым вектором из исходной точки 513 к точке 520, в которой вертикальная линия 522, проходящая через точку 514, пересекает плоскость 524, включающую исходную точку 513 и точки 502, 504 и 506. Насыщенность представлена отношением расстояния представленной точки 514 от вертикальной оси 512 d' к длине горизонтальной линии, проходящей через точку 520 от исходной точки 513 к поверхности бипирамидальной призмы 500, d. Светлота представлена вертикальным расстоянием от представленной точки 514 до вертикального уровня точки 510, представляющей черный цвет. Координаты конкретного цвета в цветовой модели HSL (h, s, ) могут быть получены на основе координат цвета в цветовой модели RGB (r, g, b) следующим образом:
[40]
[41]где значения r, g и b соответствуют яркости красного, зеленого и синего первичных цветов, нормализованных на интервале [0, 1]; Cmax представляет нормализованное значение яркости, равное максимальному значению из r, g и b; Cmin представляет собой нормализованное значение яркости, равное минимальному значению из r, g и b; а Δ определяется как Cmax-Cmin.
[42]На Фиг. 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) для бинарных изображений.
[43]На Фиг. 7 показано дискретное вычисление градиента яркости. На Фиг. 7 показан небольшой квадратный участок 702 цифрового изображения. Каждая клетка, например, клетка 704, представляет пиксель, а числовое значение в клетке, например, значение «106» в клетке 704, представляет яркость серого цвета. Допустим, пиксель 706 имеет значение яркости «203». Этот пиксель и четыре смежных с ним пикселя показаны на крестообразной схеме 708 справа от участка 702 цифрового изображения. Рассматривая левый 710 и правый 712 соседние пиксели, изменение значения яркости в направлении х, Δх можно дискретно вычислить как:
[44]
[45]Рассматривая нижний 714 и верхний 716 соседние пиксели, изменение значения яркости в вертикальном направлении Δу можно вычислить как:
[46]
[47]Вычисленное значение Δх является оценкой частного дифференциала непрерывной функции яркости относительно оси х в центральном пикселе 706:
[48]
[49]Частный дифференциал функции F относительно координаты у в центральном пикселе 706 рассчитывается по Δу:
[50]
[51]Градиент яркости в пикселе 706 может быть рассчитан следующим образом:
[52]
[53]где i и j представляют собой единичные векторы в направлениях х и у. Модуль вектора градиента и угол вектора градиента далее рассчитываются следующим образом:
[54]
[55]Направление вектора 720 градиента яркости и угол θ 722 показаны наложенными на участок 702 цифрового изображения на Фиг. 7. Следует учесть, что точки вектора градиента расположены в направлении резкого увеличения яркости от пикселя 706. Модуль вектора градиента указывает на ожидаемое увеличение яркости на единицу приращения в направлении градиента. Конечно же, поскольку градиент оценивается исключительно с помощью дискретных операций, в вычислении, показанном на Фиг. 7, направление и модуль градиента представлены исключительно оценками.
[56]На Фиг. 8 показан градиент, рассчитанный для точки на непрерывной поверхности. На Фиг. 8 представлена непрерывная поверхность z=F(x,y). Непрерывная поверхность 802 строится относительно трехмерной декартовой системы координат 804 и имеет похожую на шляпу форму. Для отображения непрерывного множества точек с постоянным значением z на поверхности могут быть построены контурные линии, например, контурная линия 806. В конкретной точке 808 на контуре, построенном на поверхности, вектор градиента 810, рассчитанный для точки, расположен перпендикулярно к контурной линии и точкам в направлении максимально резкого наклона вверх на поверхности от точки 808.
[57]Обычно вектор градиента яркости направлен перпендикулярно границе яркости, при этом чем больше модуль градиента, тем острее граница, т.е. тем больше разность в яркости пикселей с двух сторон границы. На Фиг. 9 показан ряд примеров градиента яркости. Каждый пример, например, пример 902, содержит центральный пиксель, для которого рассчитывается градиент, и четыре прилегающих пикселя, которые используются для расчета Δх и Δy. Наиболее резкие границы яркости показаны в первой колонке 904. В этих случаях модуль градиента составляет не менее 127,5, а в третьем случае 906-180,3. Относительно небольшая разность на границе, показанная в примере 908, создает градиент с модулем всего 3,9. Во всех случаях вектор градиента расположен перпендикулярно очевидному направлению границы яркости, проходящего через центральный пиксель.
[58]Многие методы обработки изображений включают применение ядер к сетке пикселей, составляющей изображение. На Фиг. 10 показано применение ядра к изображению. На Фиг. 10 небольшая часть изображения 1002 представлена в виде прямоугольной сетки пикселей. Небольшое ядро 3×3 k 1004 показано ниже изображения I 1002. Ядро применяется к каждому пикселю изображения. В случае ядра 3×3, такого как ядро k 1004, показанное на Фиг. 10, для пикселей на границе можно использовать модифицированное ядро, также изображение можно раздвинуть, скопировав значения яркости для пикселей границы в описывающий прямоугольник из пикселей, чтобы иметь возможность применять ядро к каждому пикселю исходного изображения. Чтобы применить ядро к пикселю изображения, ядро 1004 численно накладывается на окрестности пикселя, к которому применяется 1006 ядро с такими же размерами в пикселях, как у ядра. Применение ядра на окрестностях пикселя, к которому применяется ядро, позволяет получить новое значение для пикселя в преобразованном изображении, полученном применением ядра к пикселям исходного изображения. Для некоторых типов ядер новое значение пикселя, к которому применено ядро, In, вычисляется как сумма произведений значения ядра и пикселя, соответствующего значению 1008 ядра. В других случаях новое значение пикселя является более сложной функцией окрестности для пикселя и ядра 1010. В некоторых других типах обработки изображений новое значение пикселя генерируется функцией, применяемой к окрестностям пикселя без использования ядра 1012.
[59]На Фиг. 11 показана свертка изображения. Обычно ядро свертки последовательно применяется к каждому пикселю изображения, в некоторых случаях к каждому пикселю изображения, не принадлежащему границе, или, в других случаях, для создания новых значений преобразованного изображения. На Фиг. 11 ядро 3×3, выделенное штриховкой 1102, было последовательно применено к первой строке пикселей, не принадлежащих границе в изображении 1104. Каждое новое значение, созданное в результате применения ядра к пикселю в исходном изображении 1106, было перенесено в преобразованное изображение 1107. Другими словами, ядро было последовательно применено к исходным окрестностям каждого пикселя в исходном изображении для создания преобразованного изображения. Этот процесс называется «сверткой» и слабо связан с математической операцией свертки, которая выполняется путем умножения изображений, к которым применено преобразование Фурье с последующим обратным преобразованием Фурье по произведению.
[60]На Фиг. 12 показан некоторый пример ядра и методики обработки изображений на основе ядра. В процессе, называемом «медианной фильтрацией», значения яркости в окрестности исходного изображения 1202 были отсортированы 1204 по возрастанию модулей, и новым значением 1208 для соответствующей окрестности преобразованного изображения было выбрано среднее значение 1206. Гауссово сглаживание и очистка от шумов включают применение гауссова ядра 1210 ко всем окрестностям 1214 исходного изображения для создания значения для центрального пикселя окрестности 1216 в соответствующей окрестности обработанного изображения. Значения в гауссовом ядре рассчитываются по выражению, например, такому, как выражение 1218, и используются для создания дискретного представления гауссовой поверхности над окрестностью, образованной вращением кривой нормального распределения вокруг вертикальной оси, совпадающей с центральным пикселем. Горизонтальная и вертикальная компоненты градиента изображения для каждого пикселя могут быть получены применением соответствующих ядер градиента Gx 1220 и Gy 1222. Были указаны только три из множества различных типов методик обработки изображения на основе свертки.
[61]Способы и система определения контуров в цифровых изображениях
[62]На Фиг. 13 и 14 показан общий подход к определению контура. На Фиг. 13 представлен пример определения контуров, выполненный на примере цифрового изображения. Цифровое изображение 1302 представляет собой фотографию стола 1304, расположенного рядом со стеной с обоями 1306, на которой имеется окно 1308, из которого виден внешний пейзаж. В этом примере цифровое изображение проходит автоматическую обработку для определения интересующих физических объектов. В первой серии шагов обработки цифрового изображения с помощью способов определения контуров, описываемых в настоящем изобретении, определяются контуры, которые, скорее всего, будут соответствовать краям и границам интересующих физических объектов. По результатам определения контуров создается карта контуров 1310, в которой содержатся контуры, соответствующие границам стола 1304, контуры, соответствующие границам документа, лежащего на столе 1312, и контуры, соответствующие части оконной рамы 1314. После этого могут быть выполнены дополнительные шаги по обработке цифрового изображения для использования этих контуров вместе с дополнительной информацией в исходном изображении 1302 для опознания и классификации физических объектов в изображении, включая стол, документ и оконную раму. Описываемый в настоящем документе способ определения контуров подразумевает различные ограничения и параметры для управления определением контуров с целью установления контуров для конкретных целей. В частности, в показанном на Фиг. 13 примере существует множество границ яркости на исходном изображении 1302, соответствующих текстуре пунктирных линий на обоях на стене 1306 за столом. Может быть задан параметр, регулирующий минимальную длину для определяемых контуров, который может иметь значение, исключающее текстуру обоев.
[63]На Фиг. 14 показан общий подход к определению контуров с использованием описываемого в настоящем документе метода. На первом этапе 1402 исходное изображение 1302 обрабатывается с целью определения кандидатов начальных (затравочных) точек, из которых могут быть построены и продлены контуры. Результатом первого этапа может являться карта затравочных точек 1404. На втором этапе 1406 начальные границы продлеваются в двух направлениях из каждой затравочной точки для создания начальных контуров 1408. На окончательном этапе 1410 начальные границы продлеваются и объединяются для создания контуров, которые затем могут быть отфильтрованы для создания множества определенных контуров 1412, которое может использоваться для последующих задач обработки изображения. Как описано подробно ниже, каждый из этапов 1402, 1406 и 1410, показанных на Фиг. 14, включает многочисленные процессы. Эти процессы основаны на формировании и сохранении различных многочисленных типов промежуточных результатов и данных. В различных вариантах реализации способов и систем настоящего изобретения могут использоваться различные типы представления данных и промежуточных результатов. Например, в одном варианте реализации промежуточный результат может быть представлен двумерной картой с элементами, соответствующими пикселям на цифровом изображении, но в другом варианте реализации он может быть представлен сохраненными данными со ссылками на исходное изображение.
[64]На Фиг. 15-26 показан частный вариант реализации способа и подсистемы обнаружения контуров. На Фиг. 15-26 приведены подробные пошаговые иллюстрации, способствующие пониманию блок-схем, а также приводится описание блок-схем с учетом того, какой вариант реализации описан в последующем подразделе.
[65]На Фиг. 15 показан первый этап сжатия. На Фиг. 15 исходное полученное цифровое изображение 1502 имеет высоту 1536 пикселей и ширину 2048 пикселей. Разность между высотой и шириной составляет 512 пикселей 1504. Исходное изображение 1502 сжимается для создания сжатых изображений 1506 и 1507, каждое из которых имеет различный коэффициент сжатия. Первое сжатое изображение 1506 сжимается с коэффициентом сжатия 
и, в результате, имеет высоту 768 пикселей и ширину 1024 пикселей. Разность между шириной и высотой сжатого изображения составляет 256 пикселей 1508. Второе сжатое изображение сжимается с коэффициентом сжатия 
, при этом разность между шириной и высотой второго сжатого изображения составляет 128 пикселей 1510. В описываемом варианте реализации изобретения исходное изображение сжимается с одним или более коэффициентами сжатия для создания одного или более соответствующих сжатых изображений, на которых разность между шириной и высотой изображения ниже порогового числа пикселей, например, ниже 300 пикселей. Для сжатия цифрового изображения могут использоваться различные способы. В одном простом способе для создания сжатых изображений из исходного изображения удаляются равноудаленные строки и столбцы пикселей. При более сложных способах могут выполняться различные операции сглаживания, сдвига и интерполяции для предотвращения непреднамеренного удаления необходимых деталей или их искажения при сжатии.
[66]На Фиг. 16 показан следующий этап обработки при реализации процесса определения контуров. Исходное изображение или сжатая версия исходного изображения 1602 сглаживается 1604 с помощью медианного фильтра или свертки с применением гауссова ядра с целью создания сглаженного изображения 1606. Затем к каждому цветовому каналу сглаженного изображения применяются ядра градиента Gx и Gy для создания трех пар карт горизонтальной компоненты градиента и вертикальной компоненты градиента 1608-1613. Например, ядро горизонтальной компоненты градиента, прошедшее свертку с красным каналом сглаженного изображения 1614, создает карту горизонтальной компоненты градиента для красного канала 1608. Понятие «Gi(X)» используется как для указания на свертку ядра компоненты градиента в направлении i с цветовым каналом X изображения, так и для указания на карту компоненты градиента, создаваемую при свертке. При формировании и сохранении в долговременной памяти шести карт компонент градиента 1608-1613 или, как вариант, при их формировании в оперативной памяти, модули компонент градиента затем используются для создания «карты градиента» 1616. Каждый элемент карты градиента, например, элемент i 1618, содержит модуль градиента 1620 и угол направления градиента 1622. Небольшая блок-схема на Фиг. 16 показывает процесс формирования карты градиента. Сначала на этапе 1624 для каждого цветового канала вычисляется сумма абсолютных значений компонент градиента и сохраняется в переменных Ri, Gi и Bi. Если Ri превышает Gi, в соответствии с определением на этапе 1626, и если Ri превышает Bi, в соответствии с определением на этапе 1628, на этапе 1630 рассчитывается градиент для клетки или пикселя i с использованием компонент градиента для красного канала. Если Ri не превышает ни Gi, ни Bi, то на этапе 1632 определяется, является ли Bi, больше Gi. Если Bi превышает Gi, то на этапе 1634 на основе компонент градиента синего канала рассчитывается модуль и направление градиента для клетки или пикселя i. В ином случае модуль и угол направления градиента рассчитываются по компонентам градиента зеленого канала на этапе 1636. Этот процесс, показанный на блок-схемах 1624, 1626, 1628, 1630, 1632, 1634 и 1636, повторяется для каждого пикселя или клетки i в сглаженном изображении 1606. Следует отметить, что в определенных вариантах реализации свертка выполняется только для пикселей изображения, на которые возможно наложение ядра, при этом в создаваемой с помощью свертки карте имеется меньшее количество столбцов и строк, чем в исходной карте. В других вариантах реализации все исходные изображения расширяются путем копирования, с тем, чтобы ядра могли быть применены ко всем пикселям или клеткам в изображении, или для граничных пикселей и клеток используются модифицированные ядра. В связи с этим карта градиента 1616 представляет собой карту модулей и направлений градиента для каждого пикселя или клетки сглаженного изображения, при этом градиент для каждого пикселя основан на цветовом канале сглаженного изображения, для которого сумма компонент градиента является максимальной.
[67]На Фиг. 17 показано ядро подавления немаксимумов («ядро NMS»). Ядро NMS 1702 содержит три области: (1) центральный пиксель 1704; (2) непосредственная окрестность 1706; и (3) расширенная окрестность 1708. Применение ядра NMS для пикселей подразумевает, как обычно, наложение ядра NMS, чтобы область центрального пикселя 1704 ядра NMS накладывалась на пиксель, к которому применяется ядро. При применении ядра решается, передается ли яркость пикселя, к которому применяется ядро, или наоборот, передается ли на карту или изображение значение яркости 0. Если яркость расположенного ниже центрального пикселя выше яркости расположенного ниже пикселя в непосредственной окрестности и если яркость пикселя под областью центрального пикселя выше или равна яркости любого пикселя, лежащего ниже расширенной окрестности, то на образующееся изображение или карту передается значение яркости центрального пикселя. В ином случае на образующееся изображение или карту передается значение 0. Процесс принятия решений формально выражен 1710 на Фиг. 17. При свертке ядра NMS с изображением или картой выбираются пиксели или клетки изображения, или карты с локальной максимальной яркостью для передачи на образующуюся карту или изображение.
[68]На Фиг. 18 показаны дополнительные шаги процесса обнаружения контура, приводящие к созданию карты точек, которая содержит указания на исходные пиксели, из которых начинаются контуры, что было описано выше со ссылкой на карту точек 1404 на Фиг. 14. Карта градиента 1802, сформированная в ходе описанного выше процесса на Фиг. 16, свертывается с ядром NMS для создания промежуточной карты точек 1804. Ядро NMS рассматривает компоненту модуля градиента для каждой клетки карты градиента, передающую значение локальных максимальных градиентов с карты градиента на промежуточную карту точек 1804. Далее к промежуточной карте точек применяется пороговая фильтрация 1806 для создания окончательной карты точек 1808, содержащей самые большие значения модулей градиента, при этом все другие клетки содержат значение 0 в результате свертки ядра NMS или установления порога. В определенных вариантах реализации создается индекс 1810, содержащий ссылки на затравочные пиксели на карте точек для создания отсортированной карты точек 1812. Индекс сортируется по убыванию модулей градиента, поэтому большая часть перспективных затравочных пикселей обрабатываются с более высоким приоритетом, чем менее перспективные затравочные пиксели. Следует отметить, что в альтернативных вариантах реализации может использоваться сортированный массив структур данных, каждая из которых содержит координаты и модуль градиента для затравочного пикселя, а не сохраняет разреженную карту точек.
[69]При наличии карты точек, отсортированной карты точек или иной структуры данных, содержащей затравочные точки, процесс обнаружения контуров продолжается, как описано выше со ссылкой на карту или изображение 1408 на Фиг. 14, для начала построения контура от затравочных пикселей или точек. На Фиг. 19 показан общий процесс построения контура. Из заданного затравочного пикселя или точки на карте точек 1902 начальный контур может иметь одно из возможных направлений, показанных стрелками, например, стрелкой 1904. На этапе 1906 выбора исходного направления границы выбирается конкретное направление для начального контура и создается вектор 1908 длины L, конец которого соответствует затравочному пикселю 1902, а направление - выбранному направлению. При этом начальный контур представляет собой отрезок с двумя конечными точками, соответствующими концу и началу построенного вектора. В приведенном ниже описании векторы также могут называться «отрезками», поскольку, как описано ниже, контур представлен последовательностью векторов. Эти элементы представления контура также могут быть представлены как векторы с начальной точкой, модулем или углом направления, или в виде отрезков с координатами для начальной и конечной точки отрезка.
[70]На Фиг. 20 представлен расчет модуля проекции градиента пикселя р по вектору начального контура r, исходящего из затравочного пикселя или затравочной точки i. Как показано на Фиг. 20, предполагаемый исходный вектор r 2002 для контура, совпадающего с затравочным пикселем i 2004, рассматривается в процессе выбора направления начального контура. Пиксель р 2006 расположен вдоль вектора r 2002. Имеется вектор градиента 2008, связанный с пикселем р на карте градиента. Этот вектор градиента имеет угол направления θр 2010, который также присутствует на карте градиента. Угол 2012, θr, является углом направления для вектора r. Угол Ψ является углом между вектором градиента для пикселя р и вектором r 2002. Вектор pr 2016 является проекцией вектора градиента 2008 на вектор r 2002. В показанном построении угол Ψ легко рассчитывается на основе углов направлений θр и θr 2018. Отношение модулей векторов pr и вектора градиента для пикселя р равно косинусу угла Ψ 2220. Таким образом, модуль вектора проекции pr вычисляется как произведение косинуса Ψ и модуля вектора градиента, исходящего из пикселя р 2222. Как вариант, для расчета модуля вектора проекции pr 2224 может использоваться скалярное произведение вектора градиента 2008 и вектора r. Замена результата 2222 на выражение скалярного произведения дает выражение для определения модуля вектора проекции pr 2226.
[71]На Фиг. 21 показано создание промежуточных вычисленных значений, которые используются в процессе выбора направления границы. На Фиг. 21 показан затравочный пиксель с координатами (х,у) 2102 вместе с кандидатом вектора начального контура 2104. Для кандидата вектора границы создаются промежуточные результаты, 
2108 и Н(х,у,r) 2110, где r является вектором 2104 и также называется направлением начальной границы, при этом фактически имеется в виду угол направления вектора r. Имеется 10 пикселей, включая затравочный пиксель 2102, которые лежат под вектором 2104, представляющим кандидата начального контура. Значение 
вычисляется как сумма модулей проекций векторов, связанных с пикселями i1-i10, разделенная на количество элементов множества пикселей под начальным контуром. H(х,у,r) представляет собой гистограмму 2112, на которой направление градиента пикселей под вектором начального контура представлено в виде бинов гистограммы. Как показано в выражении 2114, количество пикселей, зарегистрированных в каждом бине Hi, гистограммы, соответствует количеству пикселей направлений градиента в интервале направлений, представленных бином. Бин 2116 с максимальным значением соответствует общему направлению градиента пикселей под начальным контуром. При правильном направлении начального контура направление вектора 2104 должно быть в целом перпендикулярно направлениям градиента пикселей под вектором 2104.
[72]На Фиг. 22 представлена блок-схема процесса выбора направления границ, в котором выбирается направление начального контура для затравочного пикселя. На этапе 2202 процесс получает координаты затравочного пикселя. На этапе 2204 происходит инициализация (установка нулевых значений) множества кандидатов. Множество кандидатов является множеством структур данных кандидатов, каждое из которых включает направление r и значение 
. В цикле for шагов 2206-2213 рассматривается каждое направление r от 0° до 360°. Следует, опять же, отметить, что r в настоящем описании считается как вектором, так и направлением, где направление представляет собой направление ориентации вектора r. На этапе 2207 для рассматриваемого направления вычисляется гистограмма H(х,у,r). На этапе 2208 для бина с максимальным значением в Н(х,у,r) устанавливается индекс j. На этапе 2209 определяется, является ли направление r перпендикулярным углу в диапазоне углов, соответствующих бину с максимальным значением и его ближайшим соседям. Если направление r является перпендикулярным углу в этом диапазоне, то на этапе 2210 определяется, превышает ли значение или число пикселей, назначенное бину с максимальным значением, пороговое значение В. Если да, то на этапе 2211 рассчитывается значение 
для рассматриваемого направления, и на этапе 2212 в множество кандидатов добавляется запись для рассматриваемого направления. В ином случае направление r удаляется из множества направлений кандидатов. После завершения цикла for 2206-2213, если количество кандидатов во множестве составляет меньше 0, как определено на этапе 2214, то на этапе 2215 возвращается вектор со значением 0 для указания на то, что предпочтительное направление контура для затравочного пикселя не может быть установлено. В ином случае на этапе 2216 выбирается один кандидат из множества с максимальным значением Если значение для выбранного кандидата превышает пороговое значение 
, как определено на этапе 2218, то на этапе 2220 возвращается направление r, содержащееся у выбранного кандидата. В ином случае на этапе 2215 возвращается нулевой вектор, указывающий на невозможность определения направления для затравочного пикселя. Таким образом, выбор исходного направления контура для затравочного пикселя включает выбор направления, согласованного с направлениями векторов градиента для пикселей в окрестности начального контура, когда имеется консенсус в окрестности с учетом направления градиента.
[73]На Фиг. 23 и 24 представлен выбор направления для продления контура. Процесс выбора направления продления контура в целом аналогичен процессу выбора исходных направлений контура для затравочных пикселей, описанному выше со ссылкой на Фиг. 20-22. При этом в процессе продления контура следующий вектор длины L продлевается из конечного пикселя строящегося контура, а не из затравочной точки в двух противоположных направлениях. На Фиг. 23 показан следующий кандидат вектора 2302, продленного из конечного пикселя 2304 формируемого контура. В этом случае в качестве направлений кандидатов рассматриваются только направления с углом 2α 2306. Иными словами, следующий отрезок контура 2302 может быть наклонен относительно направления предыдущего уже существующего отрезка контура 2308 на угол до α. В ином случае процесс выбора направления аналогичен процессу выбора направления для начальных векторов, соответствующих начальному контуру для затравочного пикселя.
[74]На Фиг. 25 показан процесс построения контура. Этот процесс начинается в затравочном пикселе 2502. Исходный вектор 2504 строится для образования начального контура с направлением, выбранным согласно приведенному выше описанию со ссылкой на Фиг. 20-22. Затем начальный вектор продлевается в каждом направлении за счет последовательного добавления продлевающих векторов, например, векторов 2506-2508, для каждого конца контура. Если направление следующего продления из конкретной конечной точки контура определить невозможно, то продленный в этом направлении контур оканчивается в этой конечной точке.
[75]На Фиг. 26 представлено соединение двух контуров для образования единого результирующего контура. На Фиг. 26 первый многосегментный контур 2602 заканчивается в конечной точке 2604, а второй многосегментный контур 2606 заканчивается в конечной точке 2608. Первый и второй контуры 2602 и 2606 могут представлять две дискретные и различные границы яркости в пределах изображения или могут представлять две части одной границы яркости с разрывом, разделяющим эти две части. В последнем случае обе части соединяются для формирования единого непрерывного контура. В процессе объединения оба контура продлеваются из соответствующих конечных точек, на что указывают прерывистые векторы 2610 и 2612, продлеваемые из последних отрезков 2614 и 2616 первого 2602 и второго 2606 контуров. Продление может выполняться за счет использования направления последнего отрезка каждого контура, предшествующего конечной точке, или может выполняться за счет использования метода аппроксимации на основе направлений последних n отрезков в каждом контуре. Может использоваться множество различных методов аппроксимации, в том числе методы линейной регрессии, при которых окончательная часть контуров представляется линейной, квадратичной или кубической аппроксимацией, если конечные части контуров представляются искривленными. Продленные контуры пересекаются в точке 2620. Угол пересечения β 2622 и перпендикулярные расстояния d1 2624 и d2 2626 вычисляются для определения, необходимо ли объединять эти два контура. Если угол β не превышает пороговое значение, и если минимальное из двух расстояний d1 и d2 не превышает минимальное расстояние, то строится связующий отрезок 2630 для объединения двух контуров с целью создания единого результирующего контура.
[76]На Фиг. 27A-G с помощью блок-схем и представлений структур данных показан один из вариантов реализации способа и подсистемы обнаружения контуров. На Фиг. 27А приведена блок-схема подпрограммы «найти контуры». На этапе 2702 происходит получение цифрового изображения, а также размещение и инициализация массива контуров структуры данных контуров. На этапе 2703 определяется минимальный коэффициент сжатия Cmin, необходимый для сжатия полученного изображения, чтобы при этом разность между высотой и шириной сжатого изображения была ниже порогового числа пикселей. На этапе 2704 определяется максимальный полезный коэффициент сжатия Cmax. В цикле for этапов 2705-2707 вызывается подпрограмма «определить контуры» для сжатия исходного изображения с коэффициентом сжатия в интервале [Cmin, Cmax] и определения контуров в сжатом изображении. Количество полученных сжатых изображений может зависеть от параметризованной итерации интервала сжатия, от размеров полученного цифрового изображения и от других факторов. В определенных случаях формируется только одно сжатое изображение. В других случаях контуры исходного изображения определяются без сжатия, если диспропорция и размеры исходного изображения меньше порогового значения пикселей. На этапе 2708 вызывается подпрограмма «объединить определенные контуры» для совмещения контуров, выявленных в цикле for 2705-2707. На этапе 2709 вызывается подпрограмма «выбрать итоговые контуры» для выбора итогового множества контуров в качестве выявленных контуров для использования в последующих процессах обработки цифрового изображения.
[77]На Фиг. 27В представлена структура данных, использующаяся в описанном варианте реализации. Структура данных контуров 2712 представляет собой массив данных контуров, каждый из которых включает массив cs 2713, в котором хранится начальная точка и конечная точка 2714 для каждых контуров, выявленных в конкретном сжатом изображении или, в определенных случаях, исходном изображении. Помимо этого, структура данных контуров содержит указание на количество определенных контуров 2716 и ссылку 2717 на сжатое изображение или, в определенных случаях, на исходное изображение 2718, в котором определены контуры. Это, конечно же, только одна из возможных структур данных, используемых в одном из возможных способов для представления контуров, определенных в одном или более цифровых изображениях.
[78]На Фиг. 27С показана блок-схема подпрограммы «определить контуры», вызываемой на этапе 2706 на Фиг. 27А. На этапе 2720 принимается изображение (обычно сжатое изображение С) и поступает ссылка на структуру данных контуры. На этапе 2721 устанавливаются значения для ряда параметров, управляющих определением контуров. К ним относятся: (1) L, длина отрезков, используемых для построения контуров; (2) α, максимальный угол изгиба следующего отрезка по отношению к текущему, окончательному отрезку контура; (3) h, количество бинов в гистограмме H(х,у,r), (4) В, минимальное значение для бина гистограммы с максимальным значением; (5) 
минимальное значение для начального отрезка; и (6) Re, радиус окрестности контура. Эти значения могут быть жестко заданы, поступать из файла конфигурации или быть указаны через интерфейс пользователя.
[79]На этапе 2722, полученное изображение С сглаживается, как описано выше со ссылкой на этап 1604 на Фиг. 16. В цикле for этапов 2723-2725 создаются карты компонент градиента для каждого из трех цветовых каналов в сжатом изображении С, как описано выше со ссылкой на Фиг. 16. На этапе 2726 создаются карта градиента и карта точек с индексом (1802 и 1812 на Фиг. 18). В цикле for этапов 2727-2730, в карту градиента для каждого пикселя i на изображении С вносится запись, как описано выше со ссылкой на Фиг. 16. На этапе 2731 ядро NMS применяется к карте градиента для формирования промежуточной карты точек (1804 на Фиг. 18). На этапе 2732 промежуточная карта точек фильтруется до 0 записей j, при этом модули градиента будут меньше порогового значения (1806 на Фиг. 18). На этапе 2733 на карте точек (1810 на Фиг. 18) создается отсортированный индекс. Наконец, на этапе 2734 вызывается подпрограмма «построить контуры» для построения контуров, совпадающих с определенными затравочными пикселями, на которые указывает карта точек, созданная на этапах 2731-2733.
[80]На Фиг. 27D показана блок-схема подпрограммы «построить контуры», вызываемой на этапе 2734 на Фиг. 27С. На этапе 2736 подпрограмма получает сжатое изображение С, карту точек с индексом и ссылку на структуру данных контуры. В цикле for этапов 2737-2751 каждая затравочная точка на карте точек рассматривается в порядке убывания модуля градиента, при этом используется индекс, связанный с картой точек. На этапе 2738 вызывается подпрограмма «выбрать направление границы для затравочной точки» с целью определения направления начального контура, включая совмещение построенного вектора с затравочной точкой. Следует отметить, что подпрограмма «выбрать направление» границы для затравочной точки» описана выше со ссылкой на Фиг. 22. Если направление не возвращается, текущая итерация цикла for этапов 2737-2751 заканчивается, и рассматривается следующая затравочная точка. В ином случае на этапе 2740 из затравочной точки создается исходный вектор в соответствии с заданным направлением, как описано выше со ссылкой на Фиг. 19. Во внутреннем цикле for этапов 2741-2749 начальный контур продлевается в обоих направлениях через вызванную на этапе 2745 подпрограмму «выбрать направление границы для продления». Эта подпрограмма описана выше со ссылкой на Фиг. 24, а процесс построения контуров в целом описан выше со ссылкой на Фиг. 25. После завершения контура все затравочные точки в окрестности контура, определенные радиусом Re, удаляются с карты точек и из индекса для предотвращения инициации новых контуров в чрезмерной близости к установленному текущему контуру. Наконец, после завершения внешнего цикла for этапов 2737-2751, на этапе 2752 заполняется структура данных контура в массиве контуров.
[81]На Фиг. 27Е показана блок-схема подпрограммы «объединить определенные контуры», вызываемой на этапе 2708 на Фиг. 27А. На этапе 2754 размещается структура данных результатов, и поступает ссылка на структуру данных контуров. В цикле for этапов 2756-2759 рассматриваются структура данных каждого контура в структуре данных контуров. Структура данных каждого контура в структуре данных контуров соответствует конкретному сжатому изображению или, в определенных случаях, исходному изображению. На этапе 2757 вызывается подпрограмма «соединить контуры» для объединения любых частей более длинных контуров, разделенных разрывом, как описано выше со ссылкой на Фиг. 26, и контуров, выявленных для рассматриваемого сжатого изображения. На этапе 2758 вызывается подпрограмма «изменить масштаб контуров» для изменения масштаба определенных в сжатом изображении контуров до масштаба исходного изображения. На этапе 2760 вызывается подпрограмма «выполнить слияние контуров» для слияния всех контуров, найденных во всех сжатых изображениях, и передача контуров, объединенных подпрограммой «объединение контуров» после слияния в структуру данных результатов на этапе 2761. Следует отметить, что подпрограмма «соединить контуры» принимается полиморфной и принимает ссылку на структуру данных контуров и на индекс сжатого изображения, как описано на этапе 2757, или принимает один аргумент, ссылающийся на структуру данных результатов.
[82]На Фиг. 27F показана блок-схема подпрограммы «соединить контуры», вызываемой на этапе 2757 на Фиг. 27. На этапе 2764 подпрограмма получает сжатое изображение С, использующееся в качестве индекса для структуры данных контуров, на которую также поступает ссылка. В цикле do-while этапов 2765-2773 объединяются пары контуров, выявленные в сжатом изображении С. На этапе 2766 локальной переменной прогресс присваивается значение false(ложь). На этапе 2767 для пары контуров с конечными точками на расстоянии D одна от другой выполняется поиск выявленных контуров. Следует отметить, что для D в определенных вариантах реализации могут быть заданы параметры. При обнаружении следующей пары в соответствии с определением на этапе 2768, на этапах 2769-2771 рассматривается с учетом конечных точек и продления двух контуров, что было описано выше со ссылкой на Фиг. 26, следует ли объединять два контура. Если установлено, что два контура должны быть объединены, то на этапе 2772 для локальной переменной прогресс задается значение true(истина), два контура объединяются, как описано выше со ссылкой на Фиг. 26, и один из исходных контуров в паре удаляется, а второй модифицируется для представления двух объединенных контуров. Цикл do-while этапов 2766-2773 продолжает итерации до тех пор, пока локальная переменная прогресс сохраняет значение true(истина), как определено на этапе 2773.
[83]На Фиг. 27G показана блок-схема подпрограммы «выполнить слияние контуров», вызываемой на этапе 2760 на Фиг. 27Е. На этапе 2776 подпрограмма получает ссылку на структуру данных результатов и на структуру данных контуров. Затем в цикле do-while этапов 2777-2785 определенные на сжатом изображении контуры объединяются со структурой данных результатов. На этапе 2778 локальной переменной прогресс присваивается значение false(ложъ). На этапе 2779 в выявленных контурах на сжатом изображении выполняется поиск следующего контура, несовпадающего с любым контуром, уже имеющимся в структуре данных результатов. Если, в соответствии с определением на этапе 2780, такой контур обнаружен, то на этапе 2781 определяются все контуры, совпадающие с найденным контуром, среди контуров, определенных в сжатом изображении. На этапе 2782 выбирается лучший из этих контуров и добавляется к структуре данных результатов. Затем, на этапе 2783 из структуры данных контуров удаляются изначально найденный и совпадающий контуры. На этапе 2784 локальной переменной ход выполнения присваивается значение истина. Цикл do-while повторяется до тех пор, пока на этапе 2785 локальной переменной прогресс не будет присвоено значение false(ложъ).
[84]Способы и системы, к которым относится настоящий документ
[85]На Фиг. 28 показан пример сценария обработки изображения, в котором автоматизированная система обработки изображений пытается определить содержащий документ фрагмент цифрового изображения. На Фиг. 28 на цифровом изображении 2802 содержится документ 2804, лежащий поверх стопки других листов бумаги 2806-2809. Автоматизированная система обработки цифровых изображений может быть, например, подкомпонентом автоматизированной системы распознавания текста, которая направлена на определение содержащих текст документов на цифровых изображениях и на формирование электронных документов, соответствующих содержащим текст документам. Следует сразу же отметить, что способы и системы настоящего изобретения могут определять содержащие документ фрагменты цифрового изображения с нелинейными границами, в том числе документы, искаженные при обработке изображения, в связи с искажением перспективы и иными оптическими эффектами, физическим искажением документов из-за смятия или сгиба, и документы с искривленными границами в их нормальной физической форме. В текущем примере как содержащий текст документ 2804, так и лежащие ниже листы бумаги 2806-2809, для простоты иллюстрации и ясности описания имеют линейные границы, но изображения документов с нелинейными границами уверенно распознаются в ходе описанных ниже процессов распознания документов.
[86]На Фиг. 29 показан первый этап автоматизированного процесса распознавания документов. Способы и системы обнаружения контуров, описанные в предшествующем пункте, применяются к полученному цифровому изображению 2802 для создания карты или структуры данных 2902, которая содержит контуры, соответствующие границам яркости в исходном изображении 2802. Значения входных параметров для способов и систем обнаружения контура регулируются с целью определения контуров, которые наиболее вероятно соответствуют границам документов полностью или частично. В этом случае, например, сильно криволинейные контуры, например, контуры, связанные с искривленными буквами текста, например, буква «s», не определяются в результате применения значений параметров.
[87]На Фиг. 30 представлены два дополнительных этапа в процессе распознавания изображений документов. Контуры, полученные за счет применения процесса обнаружения контуров 2902, разделяются на первое множество контуров 2904, которые имеют преимущественно вертикальное направление, и второе множество контуров 2906, которые имеют преимущественно горизонтальное направление. В качестве примера, эти контуры, имеющие направление ориентации между 45° и 135°, считаются вертикально ориентированными в одном из вариантов реализации, а контуры с направлениями ориентации от 0° до 45° и от 135° до 180° считаются ориентированными горизонтально. Направление ориентации кривых линий можно определить за счет использования многочисленных возможных способов для подбора линии к кривой линии, включая обычно используемые методы линейной регрессии или более простые геометрические способы, например, аппроксимацию кривой с помощью линии, совпадающей с конечными точками кривой или совпадающей с точками рядом с конечными точками кривой линии. После этого направление ориентации для кривой проходит аппроксимацию как направление ориентации для прямой линии, применяемой для кривой.
[88]Далее, как также показано на Фиг. 30, контуры, направленные преимущественно вертикально 2904, разделяются на левые контуры 2908 и правые контуры 2910. Аналогичным образом по большей части горизонтально направленные контуры 2906 разделяются на верхние контуры 2912 и нижние контуры 2914. В одном варианте реализации эти операции не дают строгое разделение, поскольку некоторые контуры могут заканчиваться в обоих разделах. В одном варианте реализации горизонтальная граница карты направленных преимущественно вертикально контуров 2904 разделяется на три вертикальных участка 2916-2918, определенных следующим образом: (1) левый участок 2916 от х=0,0 до 0,4, где х - координата на горизонтальной оси Декартовой системы координат цифрового изображения; (2) центральная область 2917 от х=0,4 до 0.6; и (3) правый участок 2918 от x=0,6 до 1,0. Следует отметить, что координаты x являются относительным координатами относительно ширины цифрового изображения 1.0. Левые контуры 2908 являются преимущественно вертикально направленными в карте контуров 2904, содержащимися в левой и центральной вертикальной области 2916 и 2917. Правые контуры 2910 преимущественно направлены вертикально и появляются в центральной 2917 и правой 2918 области карты 2904 преимущественно вертикально направленных контуров. Например, в результате нестрогого разделения небольшое множество контуров 2920 появляется в карте правых контуров 2908 и в карте левых контуров 2910. Аналогичное разделение вертикальной оси карты преимущественно горизонтально направленных контуров 2906 используется для создания верхней 2912 и нижней 2914 карт контуров из множества преимущественно горизонтально направленных контуров 2906.
[89]Следует отметить, что для простоты иллюстрации и наглядности множества контуров 2904 и 2906, создаваемые при первом разделении контуров, и четыре множества контуров 2908, 2910, 2912 и 2914, создаваемые при втором нестрогом разделении, показаны в виде изображений или карт. При этом они могут быть представлены в электронном виде как структуры данных, включающие координаты конечных точек каждого контура и также могут быть представлены множеством других способов. В последующем описании четыре нестрогих разделения 2908, 2910, 2912 и 2914 называются «множествами контуров» и, в частности, «множеством левых контуров» 2908, «множеством правых контуров» 2910, «множеством верхних контуров» 2912 и «множеством нижних контуров» 2914.
[90]На следующем этапе четыре множества контуров проходят фильтрацию и сортировку по длине контуров или, как вариант, по количеству пикселей, содержащихся в контурах. Верхние n контуров каждого множества контуров сохраняются для последующей обработки, где n является параметром. В одном из вариантов реализации n равно 10. Выбор n верхних контуров-кандидатов может быть основан на длине, количестве пикселей в пределах контура и иных подобных критериях. В определенных вариантах реализации эти критерии объединяются с дополнительными критериями, включая среднюю величину модуля градиента для пикселей в пределах контура, меру равномерности направления градиента в пределах контура и иные подобные критерии. При альтернативном варианте фильтрации также может использоваться информация о цветах исходного цифрового изображения.
[91]На Фиг. 31 показано построение гипотезы на основе четырех множеств контуров, рассматриваемых на Фиг. 30. На Фиг. 31 четыре множества контуров представлены четырьмя картами контуров 3102-3105. Опять же, множества контуров могут быть представлены структурами данных, картами или любыми другими представлениями множества контуров. Также следует подчеркнуть, что контуры могут быть представлены кривыми линиями или прямыми линиями. Гипотеза создается путем выбора одного контура из каждого множества контуров с последующим построением многоугольника из выбранных контуров. На Фиг. 31 кривые стрелки, например, кривая стрелка 3106, указывают на выбор контура из каждого множества контуров для создания расположения контуров 3108-3111, показанной в левой нижней части на Фиг. 31. Затем контуры, по необходимости, продлеваются для образования многоугольника 3112 с четырьмя вершинами 3114-3117. Прерывистые линии, например, прерывистые линии 3117-3121, представляют собой продление контуров для образования многоугольника. Эти продленные контуры могут быть получены различными методиками продления контуров, включая определение наиболее подходящей линии для кривого контура с использованием способов линейной регрессии, геометрического продления, при этом кривой сегмент продлевается по линии, соединяющей две точки в пределах кривого сегмента или иными способами применения линий к кривым. Линейные сегменты продлеваются по прямой в том же направлении, что линейный сегмент с любого одного конца или с обоих концов. Следует отметить, что, несмотря на то, что построенный многоугольник на Фиг. 31 лежит полностью в границах исходного изображения, продление контуров может привести к тому, что полигон будет лежать частично за пределами исходного изображения. Например, продление контуров двух приблизительно перпендикулярных контуров может привести к построению вершины за пределами границы исходного изображения. Многоугольник, в котором часть границ и вершин лежит за пределами границ исходного изображения, является допустимым с учетом описанных ниже ограничений. В целом, способы и системы настоящего изобретения составляют все возможные гипотезы или, иными словами, все возможные сочетания четырех контуров, каждый из которых выбирается из другого множества контуров, и выполняется оценка гипотезы для выбора лучшего контура кандидата для документа.
[92]На Фиг. 32 показан ряд соображений и критериев для выбора кандидатов. Гипотеза-кандидат 3202 представляет собой четырехсторонний многоугольник или четырехугольник со сторонами длиной а 3203, b 3204, с 3205 и d 3206. Многоугольник 3202 имеет две диагонали 3208 и 3209 длиной р и q. Многоугольник имеет четыре угла е 3212, ƒ 3213, g 3214 и h 3215. Гипотеза, или многоугольник 3202, также может быть распрямлен до прямоугольника, имеющего стороны длиной с' 3218 и b' 3220, показанные прерывистыми линиями на Фиг. 32. Прямоугольник из прерывистых линий со сторонами 3222-3225 представляет исходную границу цифрового изображения. Эта исходная граница продлевается в геометрическом представлении, показанном на Фиг. 32, до прямоугольника, показанного прерывистыми линиями 3226-3229 с высотой Не 3230 и шириной We 3232. Для этого продления могут применяться параметры TH 3234 и TW 3236, как показано на Фиг. 32.
[93]С правой стороны на Фиг. 32 перечислены шесть различных критериев для оценки гипотезы. Первый критерий 3240 заключается в том, что углы многоугольника расположены в пределах большого прямоугольника высотой Не и шириной We, со сторонами 3226-3229. Второй критерий 3242 заключается в том, что многоугольник должен быть выпуклым. В выпуклом многоугольнике все внутренние углы имеют значение менее 180°, при этом отрезок линии, соединяющий любые две произвольно расположенные точки на границах многоугольника, не содержит какие-либо точки за пределами многоугольника. Для каждой стороны многоугольника x рассчитывается показатель качества стороны qx 3244. Этот показатель принимает одно из трех значений: 1, 20 
- 2 и 0, в зависимости от отношения 
как показано в выражении 3246 на Фиг. 32. Показатель качества по площади 3248 рассчитывается аналогичным образом, как показано в выражении 3250, из площади многоугольника 3252. Показатель качества по площади qA имеет одно из трех значений 1, 
- 0,75, и 0, в зависимости от значения коэффициента 
Показатель качества по углам qy 3254 рассчитывается для каждого угла у многоугольника в соответствии с выражением 3256. Показатель качества по углам qy может принимать четыре значения, находящиеся в интервале от 1 до 0, при этом для углов ближе к 90° присваиваются более высокие значения. Показатель качества по соотношению сторон qS 3258 рассчитывается в соответствии с псевдокодом 3260, если известно отношение ширины документа к высоте документа 
. По сути, показатель качества по соотношению сторон qS имеет значение 1, когда отношение ширины к высоте распрямленного многоугольника или прямоугольника приближается к известному отношению ширины документа к его высоте, в ином случае отношение равно 0.
[94]На Фиг. 33 и 34 представлен расчет значения показателя веса стороны с целью построения гипотезы. На Фиг. 33 показан расчет веса для пикселя, лежащего в пределах или вдоль одной из сторон гипотезы. Двунаправленная стрелка 3302 представляет направление стороны гипотезы, а прерывистая двунаправленная стрелка 3304 представляет направление р, перпендикулярное стороне 3302. Пиксель i 3306 лежит на стороне 3302 гипотезы. Пиксель связан с вектором градиента gradienti 3308, что было описано в предыдущем разделе. Длина проекции градиента 3308 на вектор р, имеющая направление, равное направлению р, может быть рассчитана как скалярное произведение градиента и р, как показано в выражении 3312 на Фиг. 33. Угол α 3314 между связанным с пикселем градиентом и направлением р рассчитывается по выражению 3314 и служит как числовое указание на то, насколько близко направление градиента пикселя соответствует направлению р, имеющему значение 0, когда градиент и направление р являются взаимно перпендикулярными, и значение 1, когда градиент и направление р параллельны. Затем значение угла α может быть использовано в выражении 3316 для расчета весового значения weighti для заданного пикселя i. Чем ближе связанный с пикселем градиент соответствует направлению, перпендикулярному стороне многоугольника, тем больше вес пикселя.
[95]На Фиг. 34 представлен расчет совокупного весового значения weighthy для гипотезы. На Фиг. 34 сторона гипотезы представлена сплошной двунаправленной стрелкой 3402 и прерывистой двунаправленной стрелкой 3404. Стрелка 3402 представляет контур, а прерывистая стрелка 3404 представляет продление контура для создания гипотезы. Стрелка накладывается на ряд пикселей, показанных прерывистыми линиями, например, пиксель 3406 исходного изображения. Количество пикселей, охватываемых контурной частью стороны, 3402, равно SF 3408 и имеет числовое значение 19 в представленном на Фиг. 34 примере. Количество пикселей, охватываемых продленной частью стороны, FE 3410 имеет значение 11 в представленном на Фиг. 34 примере. Отношение q 3412 является отношением SF к SF+FE. Вес стороны, weightside 3414 рассчитывается по выражению 3416. Показатель weightsideр имеет значение, основанное на весовых значениях пикселей контура Wi и весовых значениях пикселей, связанных с продлением части стороны W0. Показатель веса стороны weighthyp для гипотезы представляет собой сумму весов, рассчитанных для сторон 3418. В качестве варианта для получения значений Wi и W0 может использоваться средний вес пикселя.
[96]На Фиг. 35А-Е приведены блок-схемы, на которых показан один вариант реализации способа определения документа и системы, к которым относится настоящий документ. На этапе 3502 принимается цифровое изображение, являющееся изображением документа или содержащее фрагмент документа. На этапе 3503 устанавливаются значения параметров для выявления контуров в пределах полученного изображения в соответствии со способом обнаружения контуров и системы, описанной в предыдущем подразделе настоящего документа. Затем на этапе 3504 вызывается описанная выше подпрограмма «найти контуры» для обнаружения контуров в цифровом изображении. На этапе 3505 выявленные контуры разделяются на множества вертикальных и горизонтальных контуров (2904 и 2906 на Фиг. 30 соответственно). На этапе 3506 множество вертикальных контуров проходит нестрогое разделение на множество левых и правых контуров (2908 и 2910 на Фиг. 30). На этапе 3507 множество горизонтальных контуров проходит нестрогое разделение на множества верхних и нижних контуров (2912 и 2914 на Фиг. 30). На этапе 3508 множества контуров фильтруются и сортируются по длине, по количеству пикселей, совпадающих с каждым контуром, или по другим дополнительным критериям. Если полученное изображение связано с информацией, указывающей на размер, положение и направление границы документа, как определено на этапе 3509, множество контуров, соответствующее этой границе, на этапе 3510 заменяется известной стороной. В качестве одного примера полученное изображение может быть представлено автоматической фотографией паспорта, в которой паспорт имеет заданное положение в пределах цифрового изображения, при этом верхняя граница паспорта имеет горизонтальную ориентацию в положении с известным относительным расстоянием от верхней границы цифрового изображения. На этапе 3511 вызывается подпрограмма «выбрать документ» для определения изображения или фрагмента изображения, содержащего документ, в пределах полученного цифрового изображения. Если документ выбирается вызовом подпрограммы «выбрать документ», как определено на этапе 3512, то на этапе 3513 возвращается указатель на описание границ документа. В ином случае на этапе 3514 возвращается нулевой указатель.
[97]На Фиг. 35В показана блок-схема подпрограммы «выбрать документ», вызываемой на этапе 3511 на Фиг. 35А. На этапе 3516 подпрограмма «выбрать документ» получает четыре множества контуров, подготовленных на этапах 3504-3510 на Фиг. 35А, и исходное полученное изображение. На этапе 3517 массив из четырех элементов cur_hyp инициализируется нулями, указатель h устанавливается на ноль, а локальная переменная val принимает значение -1. Затем в цикле do-while этапов 3518-3523 подпрограмма «выбрать документ» на этапе 3519 итеративно вызывает подпрограмму «следующая гипотеза» для создания следующей гипотезы. При создании гипотезы в соответствии с определением на этапе 3520 подпрограмма «выбрать документ» выполняет оценку гипотезы через вызов подпрограммы «оценка гипотезы» на этапе 3521 с сохранением на этапе 3523 оценки и указателя для созданной гипотезы, когда оценка, возвращаемая подпрограммой «оценка гипотезы» превышает значение, сохраненное в локальной переменной val, в соответствии с определением на этапе 3522. Если дальнейшие гипотезы не создаются, как определено на этапе 3520, и если текущее сохраненное в локальной переменной val значение превышает пороговое значение, как определено на этапе 3524, на этапе 3525 возвращается указатель на лучшую сформированную гипотезу. В ином случае на этапе 3526 возвращается нулевой указатель. В описываемом варианте реализации лучшая гипотеза имеет оценку с максимальным значением модуля.
[98]На Фиг. 35С показана блок-схема подпрограммы «следующая гипотеза», вызываемая на этапе 3519 на Фиг. 35В. На этапе 3530 подпрограмма «следующая гипотеза» получает четыре множества контуров, исходное изображение и переменную массива cur_ryp. Если в переменной cur_hyp содержатся только нули, в соответствии с определением на этапе 3531, подпрограмма «следующая гипотеза» на этапе 3532 создает гипотезу по умолчанию, состоящую из четырех сторон исходного изображения. Затем переменной массива cur_hyp на этапе 3533 присваивается значение {0,1,1,1}, а на этапе 3534 возвращается указатель на гипотезу по умолчанию. Гипотеза по умолчанию предполагает, что изображение документа составляет все полученное цифровое изображение. Если переменная массива cur_hyp содержит не только нули, как определено на этапе 3531, то, если переменная массива cur_hyp содержит значения {0,1,1,1}, как определено на этапе 3535, и если все множества контуров имеют, по меньшей мере, один член или контур в соответствии с определением на этапе 3536, то для переменной массива cur_hyp на этапе 3537 задаются значения {1,1,1,1} для инициации создания всех возможных гипотез из членов четырех множеств гипотез. В ином случае на этапе 3538 возвращается нулевой указатель. Если в результате получается комбинаторная гипотеза, при которой сохраненные в переменной cur_hyp значения равны {1,1,1,1}, то на этапе 3539 вызывается подпрограмма «создать гипотезу» для создания гипотезы на основе текущих значений переменной массива cur_hyp. Эти четыре значения указывают на определение контура для выбора из каждого множества четырех контуров с целью формирования следующей гипотезы. Поскольку множества контуров проходят сортировку, изначально сформированные гипотезы могут быть наиболее вероятными для представления границ документа, при этом при формировании гипотез в определенных вариантах реализации может происходить «короткое замыкание», если создаются исходные гипотезы достаточного качества. Если подпрограммой «создание гипотезы» на основе значений в массиве cur_typ успешно создается гипотеза, как описано на этапе 3540, то на этапе 3541 возвращается указатель на гипотезу. В ином случае выполняется переход к этапу 3542, первому этапу из серии обусловленных этапов, использующихся для установления значений, хранящихся в массиве cur_hyp для обозначения контуров для следующей гипотезы. Если в четвертом множестве контуров имеется член контура после члена, назначенного текущим значением четвертого элемента в массиве cur_hyp, в соответствии с определением на этапе 3542, то четвертый элемент в массиве cur_hyp на этапе 3543 увеличивается, и на этапе 3539 вызывается подпрограмма «создание гипотезы». В ином случае, если в третьем множестве контуров имеется член, следующий за членом, назначенным по третьему значению в массиве cur_hyp, в соответствии с определением на этапе 3544, то значение, хранящееся в третьем элементе массива cur_hyp, увеличивается, а для четвертого значения в массиве cur_hyp на этапе 3545 задается значение 1, после чего на этапе 3539 вызывается подпрограмма «создание гипотезы». В ином случае, если сохраненное во втором множестве контуров значение содержит член, следующий за членом, определенный по текущему значению второго элемента в массиве cur_hyp, в соответствии с определением на этапе 3546, то второй элемент массива cur_hyp увеличивается, а третьему и четвертому элементам в массиве cur_hyp на этапе 3547 задается значение 1, после чего на этапе 3539 выполняется вызов к подпрограмме «создание гипотезы». В ином случае, если первое множество контуров содержит член, следующий за членом, определенный по текущему значению первого элемента в массиве cur_hyp, в соответствии с определением на этапе 3548, то на этапе 3549 первое значение, сохраненное в массиве cur_hyp, увеличивается, а для оставшихся значений задается значение 1, после чего на этапе 3539 выполняется вызов к подпрограмме «создать гипотезу». В ином случае, дальнейшие гипотезы-кандидаты отсутствуют, и на этапе 3550 возвращается нулевой указатель.
[99]На Фиг. 35D показана блок-схема подпрограммы «создать гипотезу», вызываемой на этапе 3539 на Фиг. 35С. На этапе 3554 подпрограмма «создать гипотезу» получает переменную массива cur_hyp, четыре множества контуров и исходное цифровое изображение. На этапе 3555 значения элементов в массиве cur_hyp используются для выбора соответствующих контуров из четырех множеств контуров, как описано выше со ссылкой на Фиг. 31. Затем на этапе 3556 стороны по необходимости продлеваются для создания четырехстороннего многоугольника, что также описано выше со ссылкой на Фиг. 31. Продление сторон может выполняться путем определения наиболее подходящего отрезка линии, соответствующего кривому контуру и продлевающему этот отрезок или путем продления одного или обоих концов линейного контура. Если на этапах 3555 и 3556 был успешно создан четырехсторонний многоугольник в соответствии с определением на этапе 3557, то на этапе 3558 подпрограмма определяет, продлевается ли четырехсторонний многоугольник далее за пороговое расстояние за пределы границ исходного изображения в соответствии с приведенным выше описанием со ссылкой на Фиг. 32. Если четырехсторонний многоугольник не продлевается более чем на пороговое расстояние за пределы границ исходного изображения, и если четырехсторонний многоугольник является выпуклым, в соответствии с определением на этапе 3559, то на этапе 3560 строится структура данных гипотезы, содержащая координаты вершин многоугольника, а на этапе 3561 возвращается указатель на гипотезу. Конечно же, во многих вариантах реализации, в подпрограмму «создать гипотезу» может поступать пустая структура данных гипотезы для сохранения координат новых вершин, соответствующих создаваемой гипотезе с возвратом булевых значений, указывающих на то, была построена гипотеза или нет. Если четырехсторонний многоугольник не может быть создан, то при превышении многоугольником пороговых расстояний, соответствующих границам цифрового изображения или при невыпуклом создаваемом многоугольнике, на этапе 3562 возвращается нулевой указатель.
[100]На Фиг. 35Е показана блок-схема подпрограммы «оценка гипотезы», вызываемой на этапе 3521 на Фиг. 35В. На этапе 3566 подпрограмма «оценка гипотезы» получает четыре множества контуров, исходное цифровое изображение, массив cur_hyp и ссылку на структуру данных гипотезы. На этапе 3567 подпрограмма «оценка гипотезы» задает четырем локальным переменным q1, q2, q3, и q4 значение 0, вместе с локальной переменной wS. В цикле for на этапах 3568-3571 подпрограмма «оценка гипотезы» рассматривает каждую сторону гипотетического многоугольника, рассчитывая для каждой стороны значение показателя качества стороны qx, что было описано выше со ссылкой на Фиг. 32, и вес для стороны weightside, описанный выше со ссылкой на Фиг. 33-34. На этапе 3570 рассчитанный показатель качества стороны добавляется к локальной переменной q1, а рассчитанный вес для стороны weightside добавляется к локальной переменной wS. В цикле for на этапах 3572-3574 для каждого угла многоугольника рассчитывается показатель качества по углам и добавляется к локальной переменной q3. Показатель качества по углам описан выше со ссылкой на Фиг. 32. На этапе 3575 рассчитываются показатели качества по площади и качества по соотношению сторон qA и qS и добавляются к локальным переменным q2 и qA, соответственно. Показатели качества по площади и качества по соотношению сторон описаны выше со ссылкой на Фиг. 32. На этапе 3576 для назначенной суммы значений четырех локальных переменных q1, q2, q3 и q4 задается значение G. Затем на этапе 3577 рассчитывается гипотетическая оценка в виде взвешенных сумм локальных переменных wS и G, значение сохраняется в локальных переменных G и wS с возможным возведением в интегральную или дробную степень е1 и е2. Если рассчитанная оценка близка к нулю или находится в пределах нулевого порогового расстояния, в соответствии с определением на этапе 3578, то на этапе 3579 возвращается нулевое значение. В противном случае на этапе 3580 возвращается вычисленная оценка.
[101]Хотя настоящее изобретение описывается на примере конкретных вариантов реализации, предполагается, что оно не ограничено только этими вариантами реализации. Специалистам в данной области техники будут очевидны возможные модификации в пределах сущности настоящего изобретения. Например, любые из множества различных параметров реализации и проектирования, в том числе модульная организация, язык программирования, аппаратная платформа, структуры управления, структуры данных и прочие параметры реализации и проектирования могут варьироваться для получения альтернативных вариантов реализации способов и систем настоящего изобретения.
[102]Следует понимать, что представленное выше описание раскрываемых вариантов реализации приведено для того, чтобы оно могло дать возможность любому специалисту в данной области техники воспроизвести или применить настоящее изобретение. Специалистам в данной области техники будут очевидны возможные модификации представленных вариантов реализации, при этом общие принципы, представленные здесь, без отступления от сущности и объема настоящего изобретения могут быть применены в рамках других вариантов реализации. Таким образом, подразумевается, что настоящее изобретение не ограничено представленными здесь вариантами реализации. Напротив, в его объем входят все возможные варианты реализации, согласующиеся с раскрываемыми в настоящем документе принципами и новыми отличительными признаками.
