СПОСОБ И СИСТЕМА ОПРЕДЕЛЕНИЯ ПРОТЯЖЕННЫХ КОНТУРОВ НА ЦИФРОВЫХ ИЗОБРАЖЕНИЯХ Российский патент 2017 года по МПК G06T1/00 G06T7/181 G06K9/46 

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

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

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

Печатные документы на естественном языке до сих пор являются широко распространенным средством коммуникации между людьми, в организациях и используются для донесения информации до ее потребителей. С появлением повсеместно используемых мощных вычислительных ресурсов, включая персональные вычислительные ресурсы, реализованные в смартфонах, планшетах, ноутбуках и персональных компьютерах, а также с распространением более мощных вычислительных ресурсов облачных вычислительных сервисов, центров обработки данных и корпоративных серверов организаций и предприятий, шифрование и обмен информацией на естественном языке все более часто выполняются в виде электронных документов. Печатные документы по своей сути представляют собой изображения, в то время как электронные документы содержат последовательности цифровых кодов символов и знаков на естественном языке. Поскольку электронные документы имеют перед печатными документами преимущества по стоимости, возможностям передачи и рассылки, простоте редактирования и изменения, а также по надежности хранения, за последние 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 показан общий процесс построения контура. Из заданного затравочного пикселя или точки на карте точек 1902 начальный контур может иметь одно из возможных направлений, показанных стрелками, например, стрелкой 1904. На этапе 1906 выбора исходного направления контура выбирается определенное направление для начального контура и создается вектор 1908 длины L, конец которого соответствует затравочному пикселю 1902, а направление - выбранному направлению. При этом начальный контур представляет собой отрезок с двумя конечными точками, соответствующими концу и началу построенного вектора. В приведенном ниже описании векторы также могут называться «отрезками», поскольку, как описано ниже, контур представлен последовательностью векторов «голова к хвосту». Эти элементы представления контура могут быть закодированы как векторы с начальной точкой, модулем или углом направления или в виде отрезков с координатами начальной и конечной точки отрезка.

На Фиг. 20 представлен расчет величины проекции градиента пикселя р по вектору начального контура r, исходящего из затравочного пикселя или затравочной точки i. Как показано на Фиг. 20, предполагаемый исходный вектор r 2002 для контура, совпадающего с затравочным пикселем i 2004, рассматривается в процессе выбора направления начального контура. Пиксель р 2006 расположен вдоль вектора r 2002. Имеется вектор градиента 2008, связанный с пикселемр на карте градиента. Этот вектор градиента имеет угол направления θ_р 2010, который также присутствует на карте градиента. Угол 2012, θ_r, является углом направления для вектора r. Угол Ψ 2014 является углом между вектором градиента для пикселя р и вектором r 2002. Вектор pr 2016 является проекцией вектора градиента 2008 на вектор r 2002. В показанных на Фиг. 20 конструкциях угол Ψ легко рассчитывается 2018 на основе углов наклона θ_р и θ_r. Отношение модулей векторов pr и вектора градиента для пикселя р равно косинусу угла Ψ 2220. Таким образом, модуль вектора проекции pr вычисляется как произведение косинуса Ψ и модуля вектора градиента, исходящего из пикселя р 2222. Как вариант, для расчета модуля вектора проекции pr 2224 может использоваться скалярное произведение вектора градиента 2202 и вектора r. Замена результата 2222 на выражение скалярного произведения дает выражение для определения модуля вектора проекции pr 2226. Аналогичные конструкции могут быть сгенерированы для всех возможных относительных положений вектора градиента для пикселя р и начального вектора контура r.

На Фиг. 21 показано создание промежуточных вычисляемых значений, которые используются в процессе выбора направлений границы для затравочных пикселей. На Фиг. 21 показан затравочный пиксель с координатами (х,у) 2102 вместе с кандидатом вектора начального контура 2104. Для кандидата вектора границы создаются два промежуточных результата 2108 и Н_(х,у,r) 2110, где r является вектором 2104 и также называется направлением начальной границы, при этом фактически имеется в виду угол направления вектора r. Имеется 10 пикселей, включая затравочный пиксель 2102, которые находятся под вектором 2104, представляющим кандидата начального контура. Значение вычисляется как сумма модулей проекций векторов, связанных с пикселями i₁-i₁₀, разделенные на количество элементов множества пикселей под начальным контуром. H_(х,у,r) представляет собой гистограмму 2112, на которой направление градиента пикселей под вектором начального контура представлено в виде бинов гистограммы. Как показано в выражении 2114, количество пикселей, зарегистрированных в каждом бине H_i гистограммы, соответствует количеству пикселей с направлением градиента в интервале представленных бином направлений. Бин 2116 с максимальным значением соответствует общему направлению градиента пикселей под начальным контуром. При правильном направлении начального контура направление вектора 2104 должно быть в целом перпендикулярно направлениям градиента пикселей под вектором 2104.

На Фиг. 22 представлена блок-схема процесса выбора направления границы, в которой выбирается направление начального контура для затравочного пикселя. На этапе 2202 процесс получает координаты затравочного пикселя. На этапе 2204 происходит инициализация пустого множества кандидатов. Множество кандидатов является множеством структур данных кандидатов, каждое из которых включает направление r и значение . В цикле for этапов 2206-2213 рассматривается каждое из направлений r от 0° до 360°. Следует, опять же, отметить, что r в настоящем описании считается как вектором, так и направлением, где направление представляет собой направление ориентации вектора r. На этапе 2207 для рассматриваемого направления вычисляется гистограмма H_(x,y,r). На этапе 2208 для бина с максимальным значением в H_(х,у,r) устанавливается индекс j. На этапе 2209 определяется, является ли направление r перпендикулярным углу в диапазоне углов, соответствующих бину с максимальным значением и его ближайшим соседям. Если направление r является перпендикулярным углу в этом диапазоне, то на этапе 2210 определяется, превышает ли значение или число пикселей, назначенное бину с максимальным значением, пороговое значение В. Если да, то на этапе 2211 рассчитывается значение для рассматриваемого направления и, на этапе 2212, в множество кандидатов добавляется запись для рассматриваемого направления. После завершения цикла for этапов 2206-2213, если количество элементов в множестве кандидатов меньше 0, как определено на этапе 2214, то на этапе 2215 возвращается вектор со значением 0 для указания на то, что предпочтительное направление контура для затравочного пикселя не может быть установлено. В ином случае на этапе 2216 выбирается один кандидат из множества кандидатов с наибольшим значением . Если значение для выбранного кандидата превышает пороговое значение , как определено на этапе 2218, то на этапе 2220 возвращается направление r, содержащееся в выбранном кандидате. В противном случае на этапе 2215 возвращается нулевой вектор, указывающий на невозможность определения направления для затравочного пикселя. Таким образом, выбор исходного направления контура для затравочного пикселя включает выбор направления, согласованного с направлениями векторов градиента для пикселей в окрестности начального контура, когда в окрестности имеется консенсус относительно направления градиента.

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

На Фиг. 23 и 24 представлен выбор направления для продления контура. Процесс выбора направления продления контура в целом аналогичен процессу выбора исходных направлений контура для затравочных пикселей, описанному выше со ссылкой на Фиг. 20-22. Однако в процессе продления контура следующий вектор длины L продлевается из конечного пикселя строящегося контура, а не путем построения двух векторов из затравочной точки в двух противоположных направлениях. На Фиг. 23 показан следующий вектор-кандидат 2302, продленный из конечного пикселя 2304 формируемого контура. В этом случае в качестве направлений кандидатов рассматриваются только направления с углом 2α 2306. Иными словами, следующий отрезок контура 2302 может быть наклонен относительно направления предыдущего уже существующего отрезка контура 2308 на угол α. В ином случае процесс выбора направления аналогичен процессу выбора направления для начальных векторов, соответствующих начальному контуру для затравочного пикселя.

На Фиг. 25 показан процесс построения контура. Этот процесс начинается в затравочном пикселе 2502. Исходный вектор 2504 строится для образования начального контура с направлением, выбранным согласно приведенному выше описанию со ссылкой на Фиг. 20-22. Затем начальный вектор продлевается в каждом направлении за счет последовательного добавления продлевающих векторов, например, векторов 2506-2508 для каждого конца контура. Если направление следующего продления из конкретной конечной точки контура определить невозможно, то продление контура в этом направлении оканчивается в этой конечной точке.

На Фиг. 26 представлено соединение двух контуров для образования единого результирующего контура. На Фиг. 26 первый многосегментный контур 2602 заканчивается в конечной точке 2604, а второй многосегментный контур 2606 заканчивается в конечной точке 2608. Первый и второй контуры 2602 и 2606 могут представлять две дискретных и различных границы яркости в пределах изображения или могут представлять две части одной границы яркости с разрывом, разделяющим эти две части. В последнем случае обе части соединяются для формирования единого непрерывного контура. В процессе объединения оба контура продлеваются из соответствующих конечных точек, на что указывают пунктирные векторы 2610 и 2612, продолжающиеся из конечных отрезков 2614 и 2616 первого 2602 и второго 2606 контуров. В качестве направления продления может быть выбрано направление конечного отрезка каждого контура, включающего одну или две конечных точки, или может определяться путем использования аппроксимации, исходя из направлений n конечных отрезков каждого контура. Может использоваться множество различных способов, в том числе способы линейной регрессии, при которых конечная часть контуров выражается с помощью линейной и квадратичной или кубической аппроксимации, если конечные части контуров, по всей видимости, криволинейные. Продления в примере на Фиг. 26 пересекаются в точке 2620. Угол пересечения β 2622 и перпендикулярные расстояния d₁ 2624 и d₂ 2626 вычисляются, чтобы определить, следует ли объединять эти два контура. Если угол β не превышает порогового значения, и если минимальное из двух расстояний d₁ и d₂ не превышает минимальное расстояние, то строится связующий отрезок 2630 для объединения двух контуров с целью создания единого результирующего контура.

Блок-схемы

В настоящем подразделе рассматривается серия блок-схем, которые иллюстрируют один из вариантов реализации раскрываемых в настоящем документе способов и систем. Эти блок-схемы частично основаны на рассмотренных ранее Фиг. 13-26, которые иллюстрируют многие процессы и подпроцессы, входящие в определение контура.

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

На Фиг. 27А представлена блок схема процедуры «найти контуры», которая описывает один из вариантов реализации раскрываемого в данном документе способа определения контуров на цифровом изображении. На этапе 2702 происходит получение цифрового изображения, а также выделение и инициализация массива контуров из структур данных контуров. На этапе 2703 определяется минимальный коэффициент сжатия C_min, необходимый для сжатия полученного изображения так, чтобы разница между высотой и шириной сжатого изображения была ниже указанного порогового числа пикселей. На этапе 2704 определяется максимальный используемый коэффициент сжатия C_max. В цикле for этапов 2705-2707 итеративно вызывается подпрограмма «определить контуры» для сжатия исходного изображения с коэффициентом сжатия в интервале [C_min, C_max] и определения контуров в сжатом изображении. Количество сжатых изображений, сформированных в цикле for, может зависеть от параметризованной итерации интервала коэффициента сжатия, от размеров полученного цифрового изображения и от других факторов. В некоторых случаях формируется только одно сжатое изображение. В других случаях контуры определяются без сжатия на исходном изображении, если диспропорция размеров исходного изображения меньше порогового числа пикселей. На этапе 2708 вызывается подпрограмма «объединить определенные контуры» для совмещения контуров, выявленных в цикле for этапов 2705-2707. На этапе 2709 вызывается подпрограмма «выбрать итоговые контуры» для выбора итогового множества контуров в качестве идентифицированных контуров для использования в последующих процессах обработки цифрового изображения.

На Фиг. 27В представлена структура данных, использующаяся в описанном варианте реализации. Структура данных контуров 2712 представляет собой массив данных контуров, каждый из которых включает массив cs 2713, в котором хранится начальная точка и конечная точка 2714 для индивидуальных контуров, выявленных в конкретном сжатом изображении или, в определенных случаях, исходном изображении. Помимо того, структура данных контуров содержит указание на количество выявленных контуров 2716 и ссылку 2717 на сжатое изображение или, в определенных случаях, на исходное изображение 2718, в котором определены контуры. Это, конечно же, только одна из возможных структур данных, используемых в одном из возможных способов для представления контуров, выявленных в одном или более цифровых изображениях.

На Фиг. 27С показана блок-схема подпрограммы «определить контуры», вызываемой на этапе 2706 на Фиг. 27А. На этапе 2720 принимается изображение (обычно сжатое изображение C) и ссылка на структуру данных контуров. На этапе 2721 устанавливаются значения для ряда параметров, которые управляют определением контуров. К ним относятся: (1) L, длина отрезков, используемых для построения контуров; (2) α, максимальный угол изгиба следующего отрезка по отношению к текущему, конечному отрезку контура; (3) h, количество бинов в гистограмме Н_(х,у,r); (4) В, минимальное значение бина гистограммы с максимальным значением; (5) , минимальное значение начального отрезка; и (6) R_e, радиус окрестности контура. Эти значения могут быть жестко заданы, поступать из файла конфигурации или указываться через интерфейс пользователя.

На этапе 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.

На Фиг. 27D показана блок-схема подпрограммы «построить контуры», вызываемой на этапе 2734 на Фиг. 27С. На этапе 2736 подпрограмма получает сжатое изображение С, карту точек с индексом и ссылку на структуру данных контуров. В цикле for этапов 2737-2751 рассматриваются все затравочные точки на карте точек в порядке убывания значений модуля градиента, при этом используется индекс, связанный с картой точек. На этапе 2738 вызывается подпрограмма «выбрать направление границы для затравочной точки» с целью определения направления начального контура, включая совмещение построенного вектора с затравочной точкой. Следует отметить, что подпрограмма «выбрать направление границы для затравочной точки» описана выше со ссылкой на Фиг. 22. Если направление не возвращается, текущая итерация цикла for этапов 2737-2751 заканчивается, и рассматривается следующая затравочная точка. В противном случае на этапе 2740 из затравочной точки создается исходный вектор в соответствии с заданным направлением, как описано выше со ссылкой на Фиг. 19. Во внутреннем цикле for этапов 2741-2749 начальный контур продлевается в обоих направлениях через вызванную на этапе 2745 подпрограмму «выбрать направление границы для продления». Эта подпрограмма описана выше со ссылкой на Фиг. 24, а процесс построения контуров в целом описан выше со ссылкой на Фиг. 25. После завершения контура все затравочные точки в окрестности контура, определенной радиусом R_e, удаляются с карты точек и из индекса для предотвращения инициации новых контуров в чрезмерной близости к установленному текущему контуру. Наконец, после завершения внешнего цикла for этапов 2737-2751, на этапе 2752 заполняется структура данных контура в массиве контуров.

На Фиг. 27Е показана блок-схема подпрограммы «объединить определенные контуры», вызываемой на этапе 2708 на Фиг. 27А. На этапе 2754 размещается структура данных результатов и принимается ссылка на структуру данных контуры. В цикле for этапов 2756-2759 рассматриваются структура данных каждого контура в структуре данных контуров. Структура данных каждого контура в структуре данных контуров соответствует конкретному сжатому изображению или в определенных случаях исходному изображению. На этапе 2757 вызывается подпрограмма «соединить контуры» для объединения любых частей более длинных контуров, разделенных разрывом, как описано выше со ссылкой на Фиг. 26, и контуров, выявленных для рассматриваемого сжатого изображения. На этапе 2758 вызывается подпрограмма «изменить масштаб контуров» для изменения масштаба определенных в сжатом изображении контуров до масштаба исходного изображения. На этапе 2760 вызывается подпрограмма «выполнить слияние контуров» для слияния всех контуров, обнаруженных во всех сжатых изображениях, а на этапе 2761 производится объединение контуров, переданных в структуру данных результатов, путем вызова подпрограммы «соединить контуры». Следует отметить, что подпрограмма «соединить контуры» считается полиморфной и принимает ссылку на структуру данных контуров и на индекс сжатого изображения, как описано на этапе 2757, или принимает один аргумент, ссылающийся на структуру данных результатов.

На Фиг. 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.

На Фиг. 27G показана блок-схема подпрограммы «выполнить слияние контуров», вызываемой на этапе 2760 на Фиг. 27Е. На этапе 2776 подпрограмма получает ссылку на структуру данных результатов и на структуру данных контуров. Затем в цикле do-while этапов 2777-2785 определенные на сжатом изображении контуры объединяются со структурой данных результатов. На этапе 2778 локальной переменной прогресс присваивается значение false (ложь). На этапе 2779 в определенных контурах на сжатом изображении выполняется поиск следующего контура, не совпадающего с любым контуром, уже имеющимся в структуре данных результатов, найденный контур сохраняется в структуре данных контуров. Если в соответствии с определением на этапе 2780 такой контур обнаружен, то на этапе 2781 определяются все контуры, совпадающие с найденным контуром среди контуров, определенных в сжатом изображении. На этапе 2782 выбирается лучший из этих контуров, который и добавляется к структуре данных результатов. Для выбора лучшего контура могут использоваться различные критерии, в том числе длина. Два контура могут считаться совпадающими, если они совместно используют количество пикселей, превышающее пороговое количество пикселей, если их совпадающая часть больше пороговой доли общего числа пикселей в контурах или при иных условиях. Затем, на этапе 2783 из структуры данных контуров удаляются изначально обнаруженный контур и совпадающие контуры. На этапе 2784 локальной переменной прогресс присваивается значение true (истина). Цикл do-while повторяется до тех пор, пока на этапе 2785 локальной переменной прогресс не будет присвоено значение false (ложь).

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

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

Изобретение относится к области обработки изображений. Технический результат – обеспечение определения на цифровых изображениях криволинейных и прямолинейных контуров. Подсистема обработки изображений включает: отдельный аппаратный уровень или аппаратный уровень, используемый совместно с устройствами, приборами или системами, включающий один или более процессоров и один или более модулей памяти; и команды, хранящиеся в одном или более физических устройствах хранения данных, которые при выполнении одним или более из процессоров управляют подсистемой обработки изображений для: получения цифрового изображения, и применения многочисленных значений параметров, регулирующих определение контуров путем определения затравочных пикселей в пределах цифрового изображения, совпадающих с границами яркости, и для каждого из множества затравочных пикселей построение начального контура, который включает затравочный пиксель, итеративное продление обоих концов начального контура вдоль границы яркости для создания выявленного контура и сохранение выявленного контура в структуре данных в памяти. 3 н. и 20 з.п. ф-лы, 36 ил.

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

отдельный аппаратный уровень или аппаратный уровень, используемый совместно с устройствами, приборами или системами, включающий один или более процессоров, один или более модулей памяти; и

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

получение цифрового изображения, и

применение многочисленных значений параметров, регулирующих определение контуров путем

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

для каждого из множества затравочных пикселей

построение начального контура, который включает затравочный пиксель,

итеративное продление обоих концов начального контура вдоль границы яркости для создания выявленного контура и

сохранение выявленного контура в структуре данных в памяти.

2. Подсистема обработки изображений по п. 1, отличающаяся тем, что значения параметров включают:

длину отрезка L;

максимальный угол изгиба линии α;

количество бинов в гистограмме h;

минимальное допустимое число точек в бине гистограммы В;

значение минимальной суммы модулей проекций; и радиус контура R_e.

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

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

сглаживание каждого сжатого цифрового изображения;

создание карты градиента для каждого сглаженного сжатого цифрового изображения; и

определение затравочных пикселей с использованием созданной карты градиента.

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

медианная фильтрация;

свертка с гауссовым ядром; и

свертка с ядром усреднения.

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

размещение карты градиента в памяти;

для каждого пикселя сглаженного сжатого цифрового изображения,

по каждому из трех цветовых каналов,

вычисление модуля градиента для пикселя;

выбор цветового канала, для которого вычисленный модуль градиента максимален; и

помещение указания на модуль градиента и на направление градиента для выбранного цветового канала в соответствующую клетку или элемент карты градиента.

6. Подсистема обработки изображений по п. 5, отличающаяся тем, что вычисление модуля градиента для пикселя также включает:

свертку ядра G_x с цветовым каналом сглаженного сжатого цифрового изображения для получения карты горизонтальной компоненты градиента;

свертку ядра G_y с цветовым каналом сглаженного сжатого цифрового изображения для получения карты вертикальной компоненты градиента; и

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

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

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

8. Подсистема обработки изображений по п. 3, отличающаяся тем, что определение затравочных пикселей с помощью созданной карты градиента также включает:

свертку значений модуля градиента созданной карты с ядром подавления немаксимумов для создания карты промежуточных точек; и

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

9. Подсистема обработки изображений по п. 8, отличающаяся тем, что определение затравочных пикселей с помощью созданной карты градиента также включает:

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

10. Подсистема обработки изображений по п. 1, отличающаяся тем, что построение начального контура, который включает затравочный пиксель, также включает:

определение направления контура для начального контура;

создание первого вектора с концом, совпадающим с затравочным пикселем, направлением ориентации, аналогичным определенному направлению контура, и длиной, равной значению параметра отрезка; и

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

11. Подсистема обработки изображений по п. 10, отличающаяся тем, что определение направления контура для начального контура также включает:

для каждого из множества кандидатов направлений

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

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

определение гистограммы градиентов пикселей, совпадающих с первым вектором;

выбор в качестве итогового направления контура кандидата направления, для которого средний модуль проекций имеет наибольшее значение; и

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

выбор в качестве направления контура итогового направления контура.

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

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

итеративные для каждого конца контура, пока конец контура не прервется,

попытки определить направление границы яркости на конце контура,

если направление границы яркости определено, построение вектора на конце контура в направлении определенного направления границы яркости, и

прерывание конца контура в противном случае, до прерывания обоих концов контура.

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

15. Подсистема обработки изображений по п. 14, отличающаяся тем, что направление контура на конце контура определяется как:

направление отрезка, совпадающего с концом контура; и

направление, определяемое среднеквадратичной аппроксимацией для итогового числа отрезков на конце контура.

16. Подсистема обработки изображений по п. 1, также включающая:

последующее определение контуров для каждого сглаженного сжатого изображения,

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

объединение контуров, обнаруженных на нескольких сглаженных и сжатых изображениях.

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

получение цифрового изображения;

применение многочисленных значений параметров, регулирующих определение контуров;

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

для каждого из множества затравочных пикселей

построение начального контура, который включает затравочный пиксель,

итеративное продление обоих концов начального контура вдоль границы яркости для создания выявленного контура и

сохранение выявленного контура в структуре данных в памяти.

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

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

сглаживание каждого сжатого цифрового изображения;

создание карты градиента для каждого сглаженного сжатого цифрового изображения; и

определение затравочных пикселей с использованием созданной карты градиента.

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

размещение карты градиента в памяти;

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

вычисление модуля градиента для пикселя;

выбор цветового канала, для которого вычисленный модуль градиента максимален; и

помещение указания на модуль градиента и на направление градиента для выбранного цветового канала в соответствующую клетку или элемент карты градиента.

20. Способ по п. 18, отличающийся тем, что определение затравочных пикселей с помощью созданной карты градиента также включает:

свертку значений модуля градиента созданной карты с ядром подавления немаксимумов для создания карты промежуточных точек; и

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

21. Способ по п. 17, отличающийся тем, что создание начального контура, который включает затравочный пиксель, также включает:

определение направления контура для начального контура;

создание первого вектора с концом, совпадающим с затравочным пикселем, направлением ориентации, аналогичным определенному направлению контура, и длиной, равной значению параметра отрезка; и

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

22. Способ по п. 21, отличающийся тем, что определение направления контура для начального контура также включает:

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

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

определение гистограммы градиентов пикселей, совпадающих с первым вектором;

выбор в качестве итогового направления контура кандидата направления, для которого средний модуль проекций имеет наибольшее значение; и

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

выбор в качестве направления контура итогового направления контура.

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

получение цифрового изображения;

применение многочисленных значений параметров, регулирующих определение контуров;

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

для каждого из множества затравочных пикселей

построение начального контура, который включает затравочный пиксель,

итеративное продление обоих концов начального контура вдоль границы яркости для создания выявленного контура и

сохранение выявленного контура в структуре данных в памяти.