Способ и подсистема определения содержащих документ фрагментов цифрового изображения

Способ и подсистема определения содержащих документ фрагментов цифрового изображения

Иллюстрации

Показать все

Реферат

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

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

В настоящем документе рассматриваются автоматизированные способы и системы, управляемые различными ограничениями и параметрами, с помощью которых определяются содержащие документ фрагменты цифрового изображения. Некоторые из параметров ограничивают определение контура и построение гипотез о содержащем документ фрагменте цифрового изображения. С помощью способов и систем настоящего изобретения определяются контуры на цифровом изображении, выявленные контуры делятся на четыре множества контуров, соответствующих четырем различным сторонам в исходном цифровом изображении, на основе этих контуров строятся гипотезы о краях или границах фрагмента цифрового изображения, содержащего документ, и выполняется оценка гипотез для выбора гипотез с самыми высокими оценками для представления границ фрагмента цифрового изображения, содержащего документ, в исходном цифровом изображении.

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

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

На Фиг. 2A-D показаны два разных типа портативных устройств получения изображений.

На Фиг. 3 показано типовое изображение с цифровым кодированием.

На Фиг. 4 показан один вариант цветовой модели RGB.

На Фиг. 5 показана другая цветовая модель «оттенок-насыщенность-светлота» («HSL»).

На Фиг. 6 показано формирование серого или бинарного изображения из цветного изображения.

На Фиг. 7 показано дискретное вычисление градиента яркости.

На Фиг. 8 показан градиент, рассчитанный для точки на непрерывной поверхности.

На Фиг. 9 показан ряд примеров градиента яркости.

На Фиг. 10 показано применение ядра к изображению.

На Фиг. 11 показана свертка изображения.

На Фиг. 12 показан некоторый пример ядра и методики обработки изображений на основе ядра.

На Фиг. 13 и 14 показан общий подход к определению контура.

На Фиг. 15-26 показан частный вариант реализации способа и подсистемы обнаружения контуров.

На Фиг. 27A-G с помощью блок-схем показан один из вариантов реализации способа и подсистемы обнаружения контуров.

На Фиг. 28 показан пример сценария обработки изображения, в котором автоматизированная система обработки изображений пытается определить содержащий документ фрагмент цифрового изображения.

На Фиг. 29 показан первый этап автоматизированного процесса распознавания документов.

На Фиг. 30 представлены два дополнительных этапа в процессе распознавания изображений документов.

На Фиг. 31 показано построение гипотезы на основе четырех множеств контуров, рассматриваемых на Фиг. 30.

На Фиг. 32 показан ряд соображений и критериев для выбора

кандидатов.

На Фиг. 33 и 34 представлен расчет значения показателя веса стороны с целью построения гипотезы.

На Фиг. 35А-Е приведены блок-схемы, на которых показан вариант реализации способа и системы определения документа, к которой относится настоящий документ.

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

Настоящий документ относится к способам и системам определения контуров, включая криволинейные контуры, на цифровых изображениях для использования в последующих задачах обработки цифровых изображений, включая оптическое распознавание символов. В первом подразделе ниже приводится краткое введение в архитектуру вычислительной системы, цифровые изображения и способы обработки цифровых изображений со ссылками на Фиг. 1-12. Во втором подразделе приводится подробное описание способов и систем обнаружения контуров со ссылками на Фиг. 13-27G. В итоговом подразделе приводится одна из возможных реализаций способов и систем настоящего изобретения, которая иллюстрируется блок-схемами со ссылками на Фиг. 28-35Е.

Обзор

На Фиг. 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 для выбора требуемого изображения перед нажатием на кнопку 105 спуска затвора с целью цифрового получения изображения и сохранения изображения в электронной памяти цифровой камеры.

На Фиг. 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, при =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) следующим образом:

где значения r, g и b соответствуют яркости красного, зеленого и синего первичных цветов, нормализованных на интервале [0, 1]; C_max представляет нормализованное значение яркости, равное максимальному значению из r, g и b; C_min представляет собой нормализованное значение яркости, равное минимальному значению из r, g и b; а Δ определяется как C_max-C_min.

На Фиг. 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 соседние пиксели, изменение значения яркости в направлении х, Δх можно дискретно вычислить как:

Рассматривая нижний 714 и верхний 716 соседние пиксели, изменение значения яркости в вертикальном направлении Δу можно вычислить как:

Вычисленное значение Δх является оценкой частного дифференциала непрерывной функции яркости относительно оси х в центральном пикселе 706:

Частный дифференциал функции F относительно координаты у в центральном пикселе 706 рассчитывается по Δу:

Градиент яркости в пикселе 706 может быть рассчитан следующим образом:

где i и j представляют собой единичные векторы в направлениях х и у. Модуль вектора градиента и угол вектора градиента далее рассчитываются следующим образом:

Направление вектора 720 градиента яркости и угол θ 722 показаны наложенными на участок 702 цифрового изображения на Фиг. 7. Следует учесть, что точки вектора градиента расположены в направлении резкого увеличения яркости от пикселя 706. Модуль вектора градиента указывает на ожидаемое увеличение яркости на единицу приращения в направлении градиента. Конечно же, поскольку градиент оценивается исключительно с помощью дискретных операций, в вычислении, показанном на Фиг. 7, направление и модуль градиента представлены исключительно оценками.

На Фиг. 8 показан градиент, рассчитанный для точки на непрерывной поверхности. На Фиг. 8 представлена непрерывная поверхность z=F(x,y). Непрерывная поверхность 802 строится относительно трехмерной декартовой системы координат 804 и имеет похожую на шляпу форму. Для отображения непрерывного множества точек с постоянным значением z на поверхности могут быть построены контурные линии, например, контурная линия 806. В конкретной точке 808 на контуре, построенном на поверхности, вектор градиента 810, рассчитанный для точки, расположен перпендикулярно к контурной линии и точкам в направлении максимально резкого наклона вверх на поверхности от точки 808.

Обычно вектор градиента яркости направлен перпендикулярно границе яркости, при этом чем больше модуль градиента, тем острее граница, т.е. тем больше разность в яркости пикселей с двух сторон границы. На Фиг. 9 показан ряд примеров градиента яркости. Каждый пример, например, пример 902, содержит центральный пиксель, для которого рассчитывается градиент, и четыре прилегающих пикселя, которые используются для расчета Δх и Δy. Наиболее резкие границы яркости показаны в первой колонке 904. В этих случаях модуль градиента составляет не менее 127,5, а в третьем случае 906-180,3. Относительно небольшая разность на границе, показанная в примере 908, создает градиент с модулем всего 3,9. Во всех случаях вектор градиента расположен перпендикулярно очевидному направлению границы яркости, проходящего через центральный пиксель.

Многие методы обработки изображений включают применение ядер к сетке пикселей, составляющей изображение. На Фиг. 10 показано применение ядра к изображению. На Фиг. 10 небольшая часть изображения 1002 представлена в виде прямоугольной сетки пикселей. Небольшое ядро 3×3 k 1004 показано ниже изображения I 1002. Ядро применяется к каждому пикселю изображения. В случае ядра 3×3, такого как ядро k 1004, показанное на Фиг. 10, для пикселей на границе можно использовать модифицированное ядро, также изображение можно раздвинуть, скопировав значения яркости для пикселей границы в описывающий прямоугольник из пикселей, чтобы иметь возможность применять ядро к каждому пикселю исходного изображения. Чтобы применить ядро к пикселю изображения, ядро 1004 численно накладывается на окрестности пикселя, к которому применяется 1006 ядро с такими же размерами в пикселях, как у ядра. Применение ядра на окрестностях пикселя, к которому применяется ядро, позволяет получить новое значение для пикселя в преобразованном изображении, полученном применением ядра к пикселям исходного изображения. Для некоторых типов ядер новое значение пикселя, к которому применено ядро, I_n, вычисляется как сумма произведений значения ядра и пикселя, соответствующего значению 1008 ядра. В других случаях новое значение пикселя является более сложной функцией окрестности для пикселя и ядра 1010. В некоторых других типах обработки изображений новое значение пикселя генерируется функцией, применяемой к окрестностям пикселя без использования ядра 1012.

На Фиг. 11 показана свертка изображения. Обычно ядро свертки последовательно применяется к каждому пикселю изображения, в некоторых случаях к каждому пикселю изображения, не принадлежащему границе, или, в других случаях, для создания новых значений преобразованного изображения. На Фиг. 11 ядро 3×3, выделенное штриховкой 1102, было последовательно применено к первой строке пикселей, не принадлежащих границе в изображении 1104. Каждое новое значение, созданное в результате применения ядра к пикселю в исходном изображении 1106, было перенесено в преобразованное изображение 1107. Другими словами, ядро было последовательно применено к исходным окрестностям каждого пикселя в исходном изображении для создания преобразованного изображения. Этот процесс называется «сверткой» и слабо связан с математической операцией свертки, которая выполняется путем умножения изображений, к которым применено преобразование Фурье с последующим обратным преобразованием Фурье по произведению.

На Фиг. 12 показан некоторый пример ядра и методики обработки изображений на основе ядра. В процессе, называемом «медианной фильтрацией», значения яркости в окрестности исходного изображения 1202 были отсортированы 1204 по возрастанию модулей, и новым значением 1208 для соответствующей окрестности преобразованного изображения было выбрано среднее значение 1206. Гауссово сглаживание и очистка от шумов включают применение гауссова ядра 1210 ко всем окрестностям 1214 исходного изображения для создания значения для центрального пикселя окрестности 1216 в соответствующей окрестности обработанного изображения. Значения в гауссовом ядре рассчитываются по выражению, например, такому, как выражение 1218, и используются для создания дискретного представления гауссовой поверхности над окрестностью, образованной вращением кривой нормального распределения вокруг вертикальной оси, совпадающей с центральным пикселем. Горизонтальная и вертикальная компоненты градиента изображения для каждого пикселя могут быть получены применением соответствующих ядер градиента G_x 1220 и G_y 1222. Были указаны только три из множества различных типов методик обработки изображения на основе свертки.

Способы и система определения контуров в цифровых изображениях

На Фиг. 13 и 14 показан общий подход к определению контура. На Фиг. 13 представлен пример определения контуров, выполненный на примере цифрового изображения. Цифровое изображение 1302 представляет собой фотографию стола 1304, расположенного рядом со стеной с обоями 1306, на которой имеется окно 1308, из которого виден внешний пейзаж. В этом примере цифровое изображение проходит автоматическую обработку для определения интересующих физических объектов. В первой серии шагов обработки цифрового изображения с помощью способов определения контуров, описываемых в настоящем изобретении, определяются контуры, которые, скорее всего, будут соответствовать краям и границам интересующих физических объектов. По результатам определения контуров создается карта контуров 1310, в которой содержатся контуры, соответствующие границам стола 1304, контуры, соответствующие границам документа, лежащего на столе 1312, и контуры, соответствующие части оконной рамы 1314. После этого могут быть выполнены дополнительные шаги по обработке цифрового изображения для использования этих контуров вместе с дополнительной информацией в исходном изображении 1302 для опознания и классификации физических объектов в изображении, включая стол, документ и оконную раму. Описываемый в настоящем документе способ определения контуров подразумевает различные ограничения и параметры для управления определением контуров с целью установления контуров для конкретных целей. В частности, в показанном на Фиг. 13 примере существует множество границ яркости на исходном изображении 1302, соответствующих текстуре пунктирных линий на обоях на стене 1306 за столом. Может быть задан параметр, регулирующий минимальную длину для определяемых контуров, который может иметь значение, исключающее текстуру обоев.

На Фиг. 14 показан общий подход к определению контуров с использованием описываемого в настоящем документе метода. На первом этапе 1402 исходное изображение 1302 обрабатывается с целью определения кандидатов начальных (затравочных) точек, из которых могут быть построены и продлены контуры. Результатом первого этапа может являться карта затравочных точек 1404. На втором этапе 1406 начальные границы продлеваются в двух направлениях из каждой затравочной точки для создания начальных контуров 1408. На окончательном этапе 1410 начальные границы продлеваются и объединяются для создания контуров, которые затем могут быть отфильтрованы для создания множества определенных контуров 1412, которое может использоваться для последующих задач обработки изображения. Как описано подробно ниже, каждый из этапов 1402, 1406 и 1410, показанных на Фиг. 14, включает многочисленные процессы. Эти процессы основаны на формировании и сохранении различных многочисленных типов промежуточных результатов и данных. В различных вариантах реализации способов и систем настоящего изобретения могут использоваться различные типы представления данных и промежуточных результатов. Например, в одном варианте реализации промежуточный результат может быть представлен двумерной картой с элементами, соответствующими пикселям на цифровом изображении, но в другом варианте реализации он может быть представлен сохраненными данными со ссылками на исходное изображение.

На Фиг. 15-26 показан частный вариант реализации способа и подсистемы обнаружения контуров. На Фиг. 15-26 приведены подробные пошаговые иллюстрации, способствующие пониманию блок-схем, а также приводится описание блок-схем с учетом того, какой вариант реализации описан в последующем подразделе.

На Фиг. 15 показан первый этап сжатия. На Фиг. 15 исходное полученное цифровое изображение 1502 имеет высоту 1536 пикселей и ширину 2048 пикселей. Разность между высотой и шириной составляет 512 пикселей 1504. Исходное изображение 1502 сжимается для создания сжатых изображений 1506 и 1507, каждое из которых имеет различный коэффициент сжатия. Первое сжатое изображение 1506 сжимается с коэффициентом сжатия и, в результате, имеет высоту 768 пикселей и ширину 1024 пикселей. Разность между шириной и высотой сжатого изображения составляет 256 пикселей 1508. Второе сжатое изображение сжимается с коэффициентом сжатия , при этом разность между шириной и высотой второго сжатого изображения составляет 128 пикселей 1510. В описываемом варианте реализации изобретения исходное изображение сжимается с одним или более коэффициентами сжатия для создания одного или более соответствующих сжатых изображений, на которых разность между шириной и высотой изображения ниже порогового числа пикселей, например, ниже 300 пикселей. Для сжатия цифрового изображения могут использоваться различные способы. В одном простом способе для создания сжатых изображений из исходного изображения удаляются равноудаленные строки и столбцы пикселей. При более сложных способах могут выполняться различные операции сглаживания, сдвига и интерполяции для предотвращения непреднамеренного удаления необходимых деталей или их искажения при сжатии.

На Фиг. 16 показан следующий этап обработки при реализации процесса определения контуров. Исходное изображение или сжатая версия исходного изображения 1602 сглаживается 1604 с помощью медианного фильтра или свертки с применением гауссова ядра с целью создания сглаженного изображения 1606. Затем к каждому цветовому каналу сглаженного изображения применяются ядра градиента G_x и G_y для создания трех пар карт горизонтальной компоненты градиента и вертикальной компоненты градиента 1608-1613. Например, ядро горизонтальной компоненты градиента, прошедшее свертку с красным каналом сглаженного изображения 1614, создает карту горизонтальной компоненты градиента для красного канала 1608. Понятие «G_i(X)» используется как для указания на свертку ядра компоненты градиента в направлении i с цветовым каналом X изображения, так и для указания на карту компоненты градиента, создаваемую при свертке. При формировании и сохранении в долговременной памяти шести карт компонент градиента 1608-1613 или, как вариант, при их формировании в оперативной памяти, модули компонент градиента затем используются для создания «карты градиента» 1616. Каждый элемент карты градиента, например, элемент i 1618, содержит модуль градиента 1620 и угол направления градиента 1622. Небольшая блок-схема на Фиг. 16 показывает процесс формирования карты градиента. Сначала на этапе 1624 для каждого цветового канала вычисляется сумма абсолютных значений компонент градиента и сохраняется в переменных R_i, G_i и B_i. Если R_i превышает G_i, в соответствии с определением на этапе 1626, и если R_i превышает B_i, в соответствии с определением на этапе 1628, на этапе 1630 рассчитывается градиент для клетки или пикселя i с использованием компонент градиента для красного канала. Если R_i не превышает ни G_i, ни B_i, то на этапе 1632 определяется, является ли B_i, больше G_i. Если B_i превышает G_i, то на этапе 1634 на основе компонент градиента синего канала рассчитывается модуль и направление градиента для клетки или пикселя i. В ином случае модуль и угол направления градиента рассчитываются по компонентам градиента зеленого канала на этапе 1636. Этот процесс, показанный на блок-схемах 1624, 1626, 1628, 1630, 1632, 1634 и 1636, повторяется для каждого пикселя или клетки i в сглаженном изображении 1606. Следует отметить, что в определенных вариантах реализации свертка выполняется только для пикселей изображения, на которые возможно наложение ядра, при этом в создаваемой с помощью свертки карте имеется меньшее количество столбцов и строк, чем в исходной карте. В других вариантах реализации все исходные изображения расширяются путем копирования, с тем, чтобы ядра могли быть применены ко всем пикселям или клеткам в изображении, или для граничных пикселей и клеток используются модифицированные ядра. В связи с этим карта градиента 1616 представляет собой карту модулей и направлений градиента для каждого пикселя или клетки сглаженного изображения, при этом градиент для каждого пикселя основан на цветовом канале сглаженного изображения, для которого сумма компонент градиента является максимальной.

На Фиг. 17 показано ядро подавления немаксимумов («ядро NMS»). Ядро NMS 1702 содержит три области: (1) центральный пиксель 1704; (2) непосредственная окрестность 1706; и (3) расширенная окрестность 1708. Применение ядра NMS для пикселей подразумевает, как обычно, наложение ядра NMS, чтобы область центрального пикселя 1704 ядра NMS накладывалась на пиксель, к которому применяется ядро. При применении ядра решается, передается ли яркость пикселя, к которому применяется ядро, или наоборот, передается ли на карту или изображение значение яркости 0. Если яркость расположенного ниже центрального пикселя выше яркости расположенного ниже пикселя в непосредственной окрестности и если яркость пикселя под областью центрального пикселя выше или равна яркости любого пикселя, лежащего ниже расширенной окрестности, то на образующееся изображение или карту передается значение яркости центрального пикселя. В ином случае на образующееся изображение или карту передается значение 0. Процесс принятия решений формально выражен 1710 на Фиг. 17. При свертке ядра NMS с изображением или картой выбираются пиксели или клетки изображения, или карты с локальной максимальной яркостью для передачи на образующуюся карту или изображение.

На Фиг. 18 показаны дополнительные шаги процесса обнаружения контура, приводящие к созданию карты точек, которая содержит указания на исходные пиксели, из которых начинаются контуры, что было описано выше со ссылкой на карту точек 1404 на Фиг. 14. Карта градиента 1802, сформированная в ходе описанного выше процесса на Фиг. 16, свертывается с ядром NMS для создания промежуточной карты точек 1804. Ядро NMS рассматривает компоненту модуля градиента для каждой клетки карты градиента, передающую значение локальных максимальных градиентов с карты градиента на промежуточную карту точек 1804. Далее к промежуточной карте точек применяется пороговая фильтрация 1806 для создания окончательной карты точек 1808, содержащей самые большие значения модулей градиента, при этом все другие клетки содержат значение 0 в результате свертки ядра NMS или установления порога. В определенных вариантах реализации создается индекс 1810, содержащий ссылки на затравочные пиксели на карте точек для создания отсортированной карты точек 1812. Индекс сортируется по убыванию модулей градиента, поэтому большая часть перспективных затравочных пикселей обрабатываются с более высоким приоритетом, чем менее перспективные затравочные пиксели. Следует отметить, что в альтернативных вариантах реализации может использоваться сортированный массив структур данных, каждая из которых содержит координаты и модуль градиента для затравочного пикселя, а не сохраняет разреженную карту точек.

При наличии карты точек, отсортированной карты точек или иной структуры данных, содержащей затравочные точки, процесс обнаружения контуров продолжается, как описано выше со ссылкой на карту или изображение 1408 на Фиг. 14, для начала построения контура от затравочных пикселей или точек. На Фиг. 19 показан общий процесс построения контура. Из заданного затравочного пикселя или точки на карте точек 1902 начальный контур может иметь одно из возможных направлений, показанных стрелками, например, стрелкой 1904. На этапе 1906 выбора исходного направления границы выбирается конкретное направление для начального контура и создается вектор 1908 длины L, конец которого соответствует затравочному пикселю 1902, а направление - выбранному направлению. При этом начальный контур представляет собой отрезок с двумя конечными точками, соответствующими концу и началу построенного вектора. В приведенном ниже описании векторы также могут называться «отрезками», поскольку, как описано ниже, контур представлен последовательностью векторов. Эти элементы представления контура также могут быть представлены как векторы с начальной точкой, модулем или углом направления, или в виде отрезков с координатами для начальной и конечной точки отрезка.

На Фиг. 20 представлен расчет модуля проекции градиента пикселя р по вектору начального контура r, исходящего из затравочного пикселя или затравочной точки i. Как показано на Фиг. 20, предполагаемый исходный вектор r 2002 для контура, совпадающего с затравочным пикселем i 2004, рассматривается в процессе выбора направления начального контура. Пиксель р 2006 расположен вдоль в