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

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

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

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

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

изображений.

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

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

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

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

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

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

поверхности.

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

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

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

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

На Фиг. 13-14 показан общий подход к определению контура, используемый в раскрываемых в данном документе способах и системах.

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

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

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

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

Обзор

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

Функция atan2(y, х) определена как: (1) arctan(y/x), где х>0; (2) arctan(y/x)+π, где х<0 и у≥0; (3) arctan(y/x) - π, где х<0 и у<0; (4) π/2, где х=0 и у>0; (5) -π/2, где х=0 и у<0; и (6) не определено, где х=0 и у=0. Направление вектора 720 градиента яркости и угол θ 722 показаны наложенными на участок 702 цифрового изображения на Фиг. 7. Следует учесть, что точки вектора градиента расположены в направлении резкого увеличения яркости от пикселя 706. Модуль вектора градиента указывает на ожидаемое увеличение яркости на единицу приращения в направлении градиента. Конечно же, поскольку градиент оценивается исключительно с помощью дискретных операций, в вычислении, показанном на Фиг. 7, направление и модуль градиента представлены исключительно оценками.

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

Обычно вектор градиента яркости направлен перпендикулярно границе яркости, при этом чем больше модуль градиента, тем острее граница, т.е. тем больше разность в яркости пикселей с двух сторон границы. На Фиг. 9 показан ряд примеров градиента яркости. Каждый пример, например, пример 902, содержит центральный пиксель, для которого рассчитывается градиент, и четыре прилегающих пикселя, которые используются для расчета Δх и Δу. Наиболее резкие границы яркости показаны в первой колонке 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 примере существует множество границ яркости на исходном изображении, соответствующих текстуре пунктирных линий на обоях на стене 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»). Ядро 1702 NMS содержит три области: (1) центральный пиксель 1704; (2) непосредственная окрестность 1706; и (3) расширенная окрестность 1708. Применение ядра NMS для пикселей подразумевает такое наложение ядра NMS, чтобы область 1704 центрального пикселя ядра NMS накладывалась на пиксель, к которому применяется ядро. При наложении ядра решается, передается ли яркость пикселя, к которому применяется ядро, соответствующему пикселю или клетке итогового изображения или карте, или на итоговую карту или изображение передается значение яркости 0. Если яркость пикселя, находящегося под центральным пикселем ядра NMS, выше яркости пикселя, находящегося в непосредственной окрестности ядра NMS, и если яркость пикселя под областью центрального пикселя выше или равна яркости любого пикселя, лежащего в расширенной окрестности, то на итоговое изображение или карту передается значение яркости центрального пикселя. В ином случае на итоговое изображение или карту передается значение 0. Процесс принятия решений формально выражен 1710 на Фиг. 17. При свертке изображения или карты с ядром NMS для передачи на итоговое изображение или карту выбираются пиксели или клетки изображения или карты с максимальными локальными значениями яркости.

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

При наличии карты точек, отсортированной карты точек или иной структуры данных, содержащей затравочные точки, процесс определения контуров продолжается как описано выше со ссылкой на карту или изображение 1408 на Фиг. 14 для начала построения контура от затравочных пикселей или точек. На Фиг. 19 показан общий процесс построения контура. Из заданного затравочного пикселя или точки на карте