СПОСОБ И УСТРОЙСТВО ДЕТЕКТИРОВАНИЯ ЛОКАЛЬНЫХ ОСОБЕННОСТЕЙ НА ИЗОБРАЖЕНИИ
METHOD AND APPARATUS FOR DETECTING LOCAL FEATURES ON IMAGE

Изобретение относится к способам обработки цифровых изображений и может быть использовано в системах регистрации и наблюдения, мультимедийных приложениях работающих с визуальными данными.
i,j,k
i,j
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>I</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>J</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>k</mi><mo>=</mo><mover accent="true"><mrow><mn>1.3</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
Упрощенная математическая модель изображения представляет собой модель в цветовом пространстве RGB в виде массива S, где
,
- столбцы и строки изображения,
- цветовой канал. При реализации метода поиска локальных особенностей используется изображение в градациях серого, т.е. каждая точка представлена уровнем яркости в диапазоне от 0 (черный) до 255 (белый), с промежуточными значениями, представляющими различные уровни серого. Соответственно такое изображение обозначим, как S.
Основная решаемая задача - детектирование локальных особенностей на изображении с определенными текстурными свойствами.
Несмотря на то что изображение представляет простую структуру - матрицу двумерных чисел в ней содержится больше количество информации о наблюдаемой сцене. Извлечь структурированную информацию из этой сцены довольно сложная задача. Когда речь идет о последовательности изображений, то задача становится еще более сложной, так как появляются пространственно-временные связи между кадрами. Таким образом, требуются устройства и методы, которые позволят извлекать и анализировать заложенную в видеопоследовательность информацию. Одним из таких подходов является поиск, отслеживание и сопоставление точечных особенностей на последовательности кадров. Это один из простых способов извлечь информацию о динамике сцены. Несколько точек, отслеживаемых в видеопоследовательности, могут давать огромное количество информации.
Упрощенно способы детектирования локальных особенностей на изображении можно разделить на следующие группы:
1) Способы обнаружения углов.
2) Способы обнаружения точек.
3) Способы обнаружения пятен.
4) Способы обнаружения краев.
Анализ существующих способов детектирования показывает, что данные способы работают только с определенным типом локальных особенностей, что является основным их недостатком. Использование способов обнаружения углов на основе метода Моравека приводит к тому, что если угол не направлен в сторону соседней, то он не будет обнаружен как точечная особенность. Детектор Харриса не инвариантен к изменению масштаба изображения и алгоритм поиска углов Ши-Томаси очень чувствителен к шуму и к выбору масштабного уровня. Применение способов на основе обнаружения точек показывает, что метод SURF (Speeded Up Robust Features) не работает с объектами простой формы и без выраженных границ, а метод SIFT (Scale Invariant Feature Transform) не работает с зеркальными поверхностям и чувствителен к изменению освещения. Для использования способов обнаружения краев на основе оператора Кирша требуется больших вычислительных затрат, что ограничивает его использование в масштабе реального времени. Способы обнаружения пятен (областей) на основе детектора областей MSER (Maximally Stable Extremal Regions) приводит к тому, что он не инвариантен к масштабу при слабой контрастности, но нормализует все 6 параметров аффинных преобразований. Детектор областей FAST (Features accelerated segment testing) определяет локальные особенности достаточно быстро.
Известен способ и устройство для обнаружения объекта на изображении [Патент US №6711293, МПК G06K 9/68]. Изобретение относится к способам распознавания объектов в системах машинного зрения.
Основная техническая задача состоит в распознавании объектов на изображении, с использованием инвариантной функции масштаба. На первом этапе выполняется свертка изображения с функцией Гаусса, далее используется пирамида Гаусса для построения разностного изображения. На втором этапе находят локальные экстремумы путем сравнения каждого пикселя изображения с несколькими соседними данного масштаба. На следующем этапе выделяют область вокруг точек экстремума. На четвертом вычисляется направление градиентов некоторой окрестности и на пятом этапе для каждой точки экстремума вычисляется локальный дескриптор.
Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- инвариантность к изменению масштаба;
- нахождение локальных экстремумов.
Недостатками известного способа и устройства его реализующего являются:
- низкая точность определения локальных дескрипторов.
Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:
- так как функция Гаусса обладает ограниченным набором инвариантных функций, характеризующих особенности изображения, описываемые векторами-признаками, и тем самым данные вектора являются менее информативными.
Известен способ распознавания объектов [Патент №2438174 С1, МПК G06K 9/68]. Изобретение относится к способам распознавания объектов в системах машинного зрения, телевизионных системах наблюдения, информационно-управляющих системах робототехнических комплексов.
Основная техническая задача, решаемая заявляемым изобретением, состоит в создании способа, позволяющего повысить точность распознавания за счет повышения стабильности работы детекторов ключевых областей на изображении и увеличения количества инвариантных характеристик данных детекторов. Способ осуществляется следующим образом: входное изображение сворачивается с заданной функцией Грина:
<mrow><mi>U</mi><mrow><mo>(</mo><mrow><mi>y</mi><mo>,</mo><mi>τ</mi><mrow><mo>|</mo><mrow><msub><mi>y</mi><mn>0</mn></msub><mo>,</mo><msub><mi>τ</mi><mn>0</mn></msub></mrow></mrow></mrow><mo>)</mo></mrow><mo>=</mo><mfrac><mrow><msqrt><mi>λ</mi></msqrt></mrow><mrow><msqrt><mrow><mi>D</mi><mi>π</mi><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>e</mi><mrow><mo>−</mo><mn>2</mn><mi>λ</mi><mrow><mo>(</mo><mrow><mi>τ</mi><mo>−</mo><msub><mi>τ</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow></msup></mrow><mo>)</mo></mrow></mrow></msqrt></mrow></mfrac><mo>*</mo><mi>exp</mi><mrow><mo>[</mo><mrow><mo>−</mo><mfrac><mrow><msqrt><mi>λ</mi></msqrt></mrow><mrow><mi>D</mi><mi>π</mi><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>e</mi><mrow><mo>−</mo><mn>2</mn><mi>λ</mi><mrow><mo>(</mo><mrow><mi>τ</mi><mo>−</mo><msub><mi>τ</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow></msup></mrow><mo>)</mo></mrow></mrow></mfrac><msup><mrow><mrow><mo>(</mo><mrow><mi>y</mi><mo>−</mo><msub><mi>y</mi><mn>0</mn></msub><msup><mi>e</mi><mrow><mo>−</mo><mi>λ</mi><mrow><mo>(</mo><mrow><mi>τ</mi><mo>−</mo><msub><mi>τ</mi><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow></msup></mrow><mo>)</mo></mrow></mrow><mn>2</mn></msup></mrow><mo>]</mo></mrow></mrow>
для эволюционного оператора процесса Орнштейна-Уленбека при различных значениях параметров τ, λ.
<mrow><msub><mo>∂</mo><mi>τ</mi></msub><mi>U</mi><mrow><mo>(</mo><mrow><mi>y</mi><mo>,</mo><mi>τ</mi></mrow><mo>)</mo></mrow><mo>=</mo><msub><mo>∂</mo><mi>y</mi></msub><mrow><mo>(</mo><mrow><mi>λ</mi><mi>y</mi><mi>U</mi><mrow><mo>(</mo><mrow><mi>y</mi><mo>,</mo><mi>τ</mi></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mo>+</mo><mfrac><mi>D</mi><mn>2</mn></mfrac><msub><mo>∂</mo><mrow><mi>y</mi><mi>y</mi></mrow></msub><mi>U</mi><mrow><mo>(</mo><mrow><mi>y</mi><mo>,</mo><mi>τ</mi></mrow><mo>)</mo></mrow></mrow>
,
где τ, λ - параметры, используемые для определения сверток на различных масштабах;
D - константа, которая подбирается опытным путем для различных категорий изображений;
y=(a, b) - пространственная временная функция, суть координаты (a,b) пикселя на изображении.
Полученные свертки вычитают друг из друга для получения конечно-разностной аппроксимации первой производной свертки входного изображения с фильтром. При поиске локального экстремума данной свертки приравнивают к нулю соответствующие первые производные. Находят все локальные экстремумы и проводят адаптивную пороговую фильтрацию для отсечения незначительных особенностей. Выделенные таким способом точки служат центрами окрестностей, для которых строят произвольные дескрипторы.
Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- изменяя набор симметрии выбором соответствующей функции Грина, получать для одного и того же изображения векторы-признаки, отражающие различные свойства изображения, повышая тем самым информативность представления изображения.
Недостатками известного способа и устройства его реализующего являются:
- детектирование особенностей в виде локальных областей экстремума.
Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:
- использование способа свертки с функцией Грина не позволяет детектировать различные типы текстур.
Известен способ выделения контуров движущихся объектов [Патент №2466456 С2, МПК G06K 9/50]. Изобретение относится к области распознания образов и может быть использовано в системах технического зрения при решении задач предварительной обработки изображения.
Основная техническая задача, решаемая заявляемым изобретением, состоит в повышении точности определения областей движущихся объектов и повышения скорости выделения контуров изображения.
Структурная схема устройства включает в себя:
- выделение контуров движущихся объектов, включая обнаружение движущихся пикселей по принципу межкадрового вычитания;
- определение направления движения обнаруженных пикселей с учетом направления движения смежных пикселей;
- формирование движущихся объектов путем объединения смежных пикселей с одним направлением и наличия пикселей в восьмисвязной окрестности;
- пространственное дифференцирование обнаруженных объектов оператором Собела:
<mtable columnalign="left"><mtr><mtd><msub><mi>G</mi><mi>r</mi></msub><mo>=</mo><mrow><mo>〈</mo><mrow><mi>G</mi><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow><mo>,</mo><mi>v</mi><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mo>〉</mo></mrow><mo>=</mo><msub><mi>f</mi><mrow><mi>e</mi><mi>d</mi></mrow></msub><mrow><mo>(</mo><mrow><mi>S</mi><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow><mo>,</mo><mi>I</mi><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mo>=</mo></mtd></mtr><mtr><mtd><mrow><mo>〈</mo><mrow><msqrt><mrow><msup><mrow><mrow><mo>(</mo><mrow><mfrac><mrow><mi>δ</mi><mi>I</mi><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mrow><mo>∂</mo><mi>x</mi></mrow></mfrac></mrow><mo>)</mo></mrow></mrow><mn>2</mn></msup></mrow></msqrt><mo>+</mo><msup><mrow><mrow><mo>(</mo><mrow><mfrac><mrow><mi>δ</mi><mi>I</mi><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mrow><mo>∂</mo><mi>y</mi></mrow></mfrac></mrow><mo>)</mo></mrow></mrow><mn>2</mn></msup><mo>,</mo><mi>a</mi><mi>r</mi><mi>c</mi><mi>t</mi><mi>g</mi><mrow><mo>(</mo><mi>α</mi><mo>)</mo></mrow></mrow><mo>〉</mo></mrow></mtd></mtr></mtable>
<mrow><mi>α</mi><mo>=</mo><mrow><mo>(</mo><mrow><mfrac bevelled="true"><mrow><mrow><mo>(</mo><mrow><mfrac><mrow><mo>∂</mo><mi>I</mi><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mrow><mo>∂</mo><mi>y</mi></mrow></mfrac></mrow><mo>)</mo></mrow></mrow><mrow><mrow><mo>(</mo><mrow><mfrac><mrow><mo>∂</mo><mi>I</mi><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mrow><mo>∂</mo><mi>x</mi></mrow></mfrac></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow><mo>,</mo><mo>∀</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow><mo>∈</mo><mi>S</mi><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow>
- скелетизация контурных линий на градиентном изображении методом подавления точек немаксимальной яркости, пороговая обработка скелетного градиентного изображения на основе максимума и минимума энтропии.
Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- выделение контуров объектов на изображении.
Недостатками известного способа и устройства его реализующего являются:
- низкая точность определения локальных дескрипторов.
Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:
- пространственное дифференцирование оператором Собела при наличии текстурированных объектов приводит к значительным ложным детектированиям.
Известен способ детектирования особых точек и устройство, реализующее его [Патент US №2007/0071289 А1, МПК G06K 9/00]. Изобретение относится к детектированию точечных особенностей и способу детектирования локальных особенностей лица.
Основная техническая задача, решаемая заявляемым изобретением, состоит в создании устройства и способа корректного детектирования локальных особенностей на изображении лица одной точечной нормализацией и многоточечной нормализацией распознавания образов.
Структурная схема устройства для обнаружения локальных особенностей включает в себя:
- запоминающее устройство, настроенное на хранение первого шаблона для первой локальной точки объекта, второго шаблона для второй локальной точки, а третий шаблон для комбинации первой и второй локальной точки;
- устройство ввода изображений;
- блок кандидат;
- первый блок распознавания образов, извлекает множество третьих кандидатов из множества первых кандидатов на основе сходства между первым кандидатом и первым шаблоном, а также извлекает множество четвертого кандидата из множества вторых кандидатов на основе сходства между каждым вторым кандидатом и вторым шаблоном;
- второй блок распознавания образов, создает множество первых комбинаций каждого третьего кандидата, а каждый четвертый кандидат извлекается второй комбинацией из множества первых сочетаний, основанных на третьем сходстве между первой комбинацией и третьим шаблоном.
Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- детектирование особенностей в виде локальных областей экстремума.
Недостатками известного способа и устройства его реализующего являются:
- изобретение предназначено только для детектирования точечных особенностей локальных особенностей лица.
Известен способ обнаружения углов на основе метода Моравека [Moravec Н (1980). "Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover"]. Данный способ проверяет каждый пиксель в изображении, чтобы определить является ли тот углом, рассматривая участки в области пикселя. Сходство определяется путем принятия суммы квадратов разностей между двумя участками. Меньшее число указывает на большее сходство.
Способ осуществляется следующим образом:
1. Используется тот факт, что однородные и реберные участки изображения самоподобны.
2. В каждом пикселе считается функция самоподобности окрестностей с различным радиусом у этого пиксела.
3. Строится карта самоподобности.
4. Выбираются локальные максимумы рассогласования различных окрестностей пиксела.
5. Если величина локального максимума больше порога, то точка классифицируется как угловая:
<mrow><msub><mi>E</mi><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow></msub><mo>=</mo><mstyle displaystyle="true"><msub><mo>∑</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi></mrow></msub><mrow><msub><mi>w</mi><mrow><mi>u</mi><mo>,</mo><mi>v</mi></mrow></msub><msup><mrow><mrow><mo>[</mo><mrow><msub><mi>I</mi><mrow><mi>x</mi><mo>+</mo><mi>u</mi><mo>,</mo><mi>y</mi><mo>+</mo><mi>u</mi></mrow></msub><mo>−</mo><msub><mi>I</mi><mrow><mi>u</mi><mo>,</mo><mi>v</mi></mrow></msub></mrow><mo>]</mo></mrow></mrow><mn>2</mn></msup></mrow></mstyle></mrow>
,
где I - обозначается интенсивность изображения; w - окно, которое определяет область изображения с коэффициентом единица.
Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- детектирование локальных особенностей в виде углов.
Недостатками известного способа являются:
- если угол не направлен в сторону соседней, то он не будет обнаружен, как точечная особенность.
Известен способ обнаружения углов с помощью преобразования Хафа [Шапиро Л., Дж. Стокман. Компьютерное зрение; Пер с англ. - М.: БИНОМ. Лаборатория знаний, 2006. - С.413]. Данный способ преобразования Хафа использует аккумуляторный массив, размерность которого соответствует количеству неизвестных параметров в уравнении семейства искомых кривых. Области углов на изображении можно обнаружить посредством поиска пар выделенных краевых сегментов E1 и Е2, удовлетворяющих перечисленным ниже условиям:
- аппроксимирующие прямые для множеств краевых точек E1 и Е2 пересекаются в точке [u,v], координаты которой определены в действительной системе координат изображения;
- точка [u,v] лежит близко от крайних точек множеств E1 и Е2;
- направления градиентов E1 и Е2 симметричны относительно оси симметрии двух этих краев.
Исходные краевые сегменты выделяются с помощью преобразования Хафа путем прослеживания границ и последующей аппроксимации прямыми или каким-либо другим подходящим алгоритмом. Для каждой пары отрезков ([d1,θ1], [d2,θ2]), удовлетворяющей перечисленным условиям, четверка элементов (d1,θ1], [d2,θ2], [u,v], α) добавляется в множество кандидатов на углы (где α - это величина угла). Сформированное множество угловых характерных признаков применяется в различных целях, например для построения каких-либо высокоуровневых описаний.
Аккумуляторный массив А используется в алгоритме Хафа для проверки каждого пиксела изображения и его окрестности. Определяется, присутствует ли в данном пикселе достаточно выраженный край. Если присутствует, то вычисляются параметры искомой кривой, проходящей через данный пиксел. После оценки параметров прямой в данном пикселе они дискретизируются для получения соответствующих значений М и В и значение элемента массива А[М,В] увеличивается. После обработки пикселов выполняется поиск локальных максимумов в аккумуляторном массиве. Точки локальных максимумов соответствуют параметрам наиболее вероятных прямых на изображении.
Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- детектирование локальных особенностей в виде углов.
Недостатками известного способа являются:
- приведенные условия определяют только углы типа 'L';
- второе условие исключает из рассмотрения углы типа 'T', 'X' и 'Y';
- аккумуляторный массив позволяет определить параметры бесконечно протяженных прямых или кривых линий, но с его помощью нельзя определить, где именно на изображении начинаются и заканчиваются отрезки линий.
Известен способ Blob обнаружения на основе Лапласиан Гауссиан [Lindeberg Т. (1998). "Feature detection with automatic scale selection". International Journal of Computer Vision 30 (2): pp.77-116], который основан на выполнении одноразовой цифровой операции полосовой фильтрации пространственной функции изображения с использованием оператора лапласиана гауссиана.
Данный способ использует свойство коммутативности линейных операторов Гаусса и Лапласа:
<mrow><mi>L</mi><mo>×</mo><mrow><mo>(</mo><mrow><mi>G</mi><mo>×</mo><mi>I</mi></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mo>(</mo><mrow><mi>L</mi><mo>×</mo><mi>G</mi></mrow><mo>)</mo></mrow><mo>×</mo><mi>I</mi><mo>=</mo><mi>L</mi><mi>o</mi><mi>C</mi><mo>×</mo><mi>I</mi></mrow>
,
где × - оператор свертки и возможности объединения их в один путем изменения порядка выполнения операций дифференцирования и сглаживания. Объединенный оператор получил название оператора лапласиана гауссиана LoG (LoG - Laplacian of Gaussian) и представляет собой свертку операторов Лапласа и Гаусса.
Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- детектирование локальных особенностей в виде областей.
Недостатками известного способа являются:
- операторы Гаусса и Лапласа являются ненаправленными;
- чувствительность к изменению яркости в параллельном направлении, что уменьшает соотношение сигнал/шум.
Известен способ детектирования краев методом Кирша [Шапиро Л., Дж. Стокман. Компьютерное зрение; Пер с англ. - М.: БИНОМ. Лаборатория знаний, 2006. - С.413]. Оператор Кирша - нелинейный детектор края, который находит максимальную толщину края в нескольких направлениях. Взяв маску, оператор вращает ее в 8 основных направлениях компаса: север, северо-запад, запад, юго-запад, юг, юго-восток, восток, северо-восток.
Способ осуществляется следующим образом:
Метод Кирша работает с двумерной апертурой 3×3 следующего вида:
А0
A1
A2
А7
F
A3
А6
A5
A4
i
i
Сначала находятся все значения переменных S и T, где i изменяется от 0 до 7, производится вычисление двух сумм, одна из которых содержит 3 элемента, последовательно выбранные при обходе «по кругу» крайних элементов, вошедших в окно, вторая сумма включает оставшиеся пять элементов:
<mrow><msub><mi>S</mi><mi>i</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mi>i</mi></mrow><mrow><mrow><mo>(</mo><mrow><mi>i</mi><mo>+</mo><mn>2</mn></mrow><mo>)</mo></mrow><mi>mod</mi><mn>8</mn></mrow></munderover><mrow><msub><mi>A</mi><mi>j</mi></msub></mrow></mstyle></mrow>
<mrow><msub><mi>T</mi><mi>i</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mi>i</mi><mo>+</mo><mn>3</mn></mrow><mrow><mrow><mo>(</mo><mrow><mi>i</mi><mo>+</mo><mn>7</mn></mrow><mo>)</mo></mrow><mi>mod</mi><mn>8</mn></mrow></munderover><mrow><msub><mi>A</mi><mi>j</mi></msub></mrow></mstyle></mrow>
Далее значения сумм подвергаются сравнению при помощи взвешенной разности по модулю, что определяет наличие либо отсутствие контраста в рассматриваемом направлении:
<mrow><msub><mi>Y</mi><mi>i</mi></msub><mo>=</mo><mrow><mo>|</mo><mrow><mn>5</mn><msub><mi>S</mi><mi>i</mi></msub><mo>−</mo><mn>3</mn><msub><mi>T</mi><mi>i</mi></msub></mrow><mo>|</mo></mrow></mrow>
Выбирается максимальный перепад контраста из всех направлений, направление изменяется за счет вычисления всех возможных разностей, последовательно меняя стартовую позицию начального элемента (i):
<mrow><mi>F</mi><mo>'</mo><mo>=</mo><munder><mrow><mi>max</mi><mrow><mo>{</mo><mrow><msub><mi>Y</mi><mi>i</mi></msub></mrow><mo>}</mo></mrow></mrow><mrow><mi>i</mi><mo>=</mo><mn>0,7</mn></mrow></munder></mrow>
В точку со значением F записывается полученное значение, фильтр сдвигается вправо.
Признаки устройства-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- детектирование локальных особенностей в виде границ.
Недостатками известного способа являются:
- требуется большое количество времени для расчета локальных особенностей.
Известен способ детектирования точек методом SIFT (Scale Invariant Feature Transform) [David G. Lowe «Distinctive image features from scale-invariant keypoints» International Journal of Computer Vision, 60, 2(2004), pp.91-110]. Главным этапом в детектировании особых точек является построение пирамиды гауссианов (Gaussian) и разностей гауссианов (Difference of Gaussian, DoG).
Способ осуществляется следующим образом: точка считается особой, если она является локальным экстремумом разности гауссианов. Для поиска экстремумов будем использовать следующий метод. В каждом изображении из пирамиды DoG ищутся точки локального экстремума. Каждая точка текущего изображения DoG сравнивается с ее восьмью соседями и с девятью соседями в DoG, находящимися на уровень выше и ниже в пирамиде. Если эта точка больше (меньше) всех соседей, то она принимается за точку локального экстремума.
Следующим шагом будет пара проверок пригодности точки экстремума на роль ключевой. Первым делом определяются координаты особой точки с субпиксельной точностью. Это достигается с помощью аппроксимирования функции DoG многочленом Тейлора второго порядка, взятого в точке вычисленного экстремума.
<mrow><mi>D</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>=</mo><mi>D</mi><mo>+</mo><mfrac><mrow><mo>∂</mo><msup><mi>D</mi><mi>T</mi></msup></mrow><mrow><mo>∂</mo><mi>x</mi></mrow></mfrac><mi>x</mi><mo>+</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><msup><mi>x</mi><mi>T</mi></msup><mfrac><mrow><msup><mo>∂</mo><mn>2</mn></msup><mi>D</mi></mrow><mrow><mo>∂</mo><msup><mi>x</mi><mn>2</mn></msup></mrow></mfrac><mi>x</mi></mrow>
,
здесь D - функция DoG, X=(x,y,sigma) - вектор смещения относительно точки разложения, первая производная DoG - градиент, вторая производная DoG - матрица Гессе.
Экстремум многочлена Тейлора находится путем вычисления производной и приравнивания ее к нулю. В итоге получим смещение точки вычисленного экстремума относительно точного
<mrow><mover><mi>x</mi><mo>^</mo></mover><mo>=</mo><mo>−</mo><mfrac><mrow><msup><mo>∂</mo><mn>2</mn></msup><msup><mi>D</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup></mrow><mrow><mo>∂</mo><msup><mi>x</mi><mn>2</mn></msup></mrow></mfrac><mtext> </mtext><mfrac><mrow><mo>∂</mo><mi>D</mi></mrow><mrow><mo>∂</mo><mi>x</mi></mrow></mfrac></mrow>
,
<mrow><mover><mi>X</mi><mo>^</mo></mover></mrow>
Все производные вычисляются по формулам конечных разностей. Если одна из компонент вектора
больше 0.5*шаг сетки в этом направлении, то это означает, что на самом деле точка экстремума была вычислена неверно и нужно сдвинуться к соседней точке в направлении указанных компонент. Для соседней точки все повторяется заново. Если таким образом выходим за пределы октавы, то следует исключить данную точку из рассмотрения.
Когда положение точки экстремума вычислено, то значение DoG сравнивается с порогом в точке по формуле:
<mrow><mi>D</mi><mrow><mo>(</mo><mrow><mover><mi>x</mi><mo>^</mo></mover></mrow><mo>)</mo></mrow><mo>=</mo><mi>D</mi><mo>+</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><mtext> </mtext><mfrac><mrow><mo>∂</mo><msup><mi>D</mi><mi>T</mi></msup></mrow><mrow><mo>∂</mo><mi>x</mi></mrow></mfrac><mover><mi>x</mi><mo>^</mo></mover></mrow>
Если эта проверка не проходит, то точка исключается из рассмотрения, как точка с малым контрастом.
Признаки способа-аналога, совпадающие с признаками заявляемого технического решения, следующие:
- детектирование локальных особенностей в виде областей.
Недостатками известного способа являются:
- не работает с отражающими поверхностями.
Наиболее близким к изобретению относится способ SURF (Speeded Up Robust Features) [Bay H., Tuytelaars T. (2006) Ess A. Speeded-Up Robust Features (SURF) in LNCS 3951 (ECCV'06), vol. 1, 2006, pp.404-417]. Способ SURF позволяет находить локальные точки с помощью матрицы Гессе и хорошо детектирует пятна и углы. Гессиан инвариантен относительно вращения, но не инвариантен масштабу. Поэтому метод SURF использует разномасштабные фильтры для нахождения гессианов.
Для каждой локальной точки считается направление максимального изменения яркости (градиент) и масштаб, взятый из масштабного коэффициента матрицы Гессе. Градиент в точке вычисляется с помощью фильтров Хаара. Обнаружение особых локальных точек в методе SURF использует бинаризированную аппроксимацию лаплассиана-гауссиана.
Признаки способа-прототипа, совпадающие с признаками заявляемого технического решения, следующие:
- детектирование локальных особенностей в виде областей и углов.
Недостатками известного способа являются:
- частично инвариантен к освещению и положению оптических камер;
- не работает с отражающими поверхностями и сильно выраженной геометрической структурой.
Наиболее близким к изобретению является способ и система для обнаружения лиц [Патент №2008145913/28, МПК G06K 9/00]. Рассматриваемое устройство-прототип предполагает выполнение следующих операций:
1) Выполняется построение карт градиентов входящего изображения, результатом работы которого является вычисление изменений интенсивности (или цветных компонент) соседних пикселей или групп и оценка направления наибольшего изменения в каждой точке изображения;
2) Проводится поиск дуг окружностей на картах градиентов, основным результатом работы которого является получение многомерной весовой карты возможных местоположений лица с учетом геометрических параметров дуг: радиусов, длины и расположения;
3) Проводится поиск локальных особенностей на входящем изображении и градиентных картах, результатом работы будет являться набор выделенных локальных особенностей с их геометрическими характеристиками;
4) Выполняется построение набора гипотез возможных положений лиц, выходной информацией служит набор гипотез, каждая из которых определяет возможное положение лица на исходном изображении, с учетом его размеров и ориентации;
5) Осуществляется верификация построенных гипотез.
Устройство для обнаружения лиц включает: блок регистрации (памяти) входящего изображения; блок построения карт градиентов входящего изображения; блок поиска дуг окружностей на картах градиентов; блок поиска локальных особенностей на входящем изображении и градиентных картах; блок построения набора гипотез возможных положений лиц; блок предобработки; блок-детектор лица; блок верификации построения гипотез.
Недостатками известного устройства-прототипа являются:
- детектирование определенных локальных особенностей с целью обнаружения местоположения лица на изображении.
Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:
- в качестве детектирования локальных особенностей может выступать метод SURF, соответственно такой метод обнаруживает только локальные особенности в виде областей.
Суть предлагаемого способа детектирования локальных особенностей на изображении состоит в следующем (фиг.1).
На первом шаге исходное изображение, которое представлено моделью в цветовом пространстве RGB, преобразуется в градации серого для реализации метода поиска локальных особенностей.
На втором шаге происходит выбор интересующей локальной особенности с помощью обработки текстурными энергетическими характеристиками Лаве (Laws) [Laws К. Textured image segmentation, Ph.D. dissertation, University of Southern California. 130 pp. - 1980].
Для вычисления энергетических характеристик используется набор из 22 масок размерами 5x5. Затем энергетические характеристики каждого пиксела анализируемого изображения представляются в виде вектора и 9 чисел. Для вычисления масок используются следующие векторы:
<mrow><mi>L</mi><mn>5</mn><mrow><mo>(</mo><mrow><mi>L</mi><mi>e</mi><mi>v</mi><mi>e</mi><mi>l</mi></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>4</mn></mtd><mtd><mn>6</mn></mtd><mtd><mn>4</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mrow><mo>]</mo></mrow></mrow>
<mrow><mi>E</mi><mn>5</mn><mrow><mo>(</mo><mrow><mi>E</mi><mi>d</mi><mi>g</mi><mi>e</mi></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mo>−</mo><mn>1</mn></mrow></mtd><mtd><mrow><mo>−</mo><mn>2</mn></mrow></mtd><mtd><mn>0</mn></mtd><mtd><mn>2</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mrow><mo>]</mo></mrow></mrow>
<mrow><mi>S</mi><mn>5</mn><mrow><mo>(</mo><mrow><mi>S</mi><mi>p</mi><mi>o</mi><mi>t</mi></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mo>−</mo><mn>1</mn></mrow></mtd><mtd><mn>0</mn></mtd><mtd><mn>2</mn></mtd><mtd><mn>0</mn></mtd><mtd><mrow><mo>−</mo><mn>1</mn></mrow></mtd></mtr></mtable></mrow><mo>]</mo></mrow></mrow>
<mrow><mi>E</mi><mn>5</mn><mrow><mo>(</mo><mrow><mi>R</mi><mi>i</mi><mi>p</mi><mi>p</mi><mi>l</mi><mi>e</mi></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mrow><mo>−</mo><mn>4</mn></mrow></mtd><mtd><mn>6</mn></mtd><mtd><mrow><mo>−</mo><mn>4</mn></mrow></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mrow><mo>]</mo></mrow></mrow>
<mrow><mi>E</mi><mn>5</mn><mrow><mo>(</mo><mrow><mi>W</mi><mi>a</mi><mi>v</mi><mi>e</mi></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mo>−</mo><mn>1</mn></mrow></mtd><mtd><mn>2</mn></mtd><mtd><mn>0</mn></mtd><mtd><mrow><mo>−</mo><mn>2</mn></mrow></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mrow><mo>]</mo></mrow></mrow>
Название вектора описывает их назначение. Вектор L5 предназначен для вычисления симметричного взвешенного локального среднего значения. Вектор Е5 предназначен для обнаружения краев, S5 - для обнаружения пятен, R5 - для обнаружения образа в виде ряби, a W5 - для обнаружения волн. Двумерные маски вычисляются умножением пар векторов. Например, для получения маски E5L5 надо умножить вектор Е5 на L5:
<mrow><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mo>−</mo><mn>1</mn></mrow></mtd></mtr><mtr><mtd><mrow><mo>−</mo><mn>2</mn></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>2</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>×</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>4</mn></mtd><mtd><mn>6</mn></mtd><mtd><mn>4</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mrow><mo>]</mo></mrow><mo>=</mo><mrow><mo>[</mo><mrow><mtable><mtr><mtd><mrow><mo>−</mo><mn>1</mn></mrow></mtd><mtd><mrow><mo>−</mo><mn>4</mn></mrow></mtd><mtd><mrow><mo>−</mo><mn>6</mn></mrow></mtd><mtd><mrow><mo>−</mo><mn>4</mn></mrow></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mrow><mo>−</mo><mn>2</mn></mrow></mtd><mtd><mrow><mo>−</mo><mn>8</mn></mrow></mtd><mtd><mrow><mo>−</mo><mn>12</mn></mrow></mtd><mtd><mrow><mo>−</mo><mn>8</mn></mrow></mtd><mtd><mrow><mo>−</mo><mn>2</mn></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>2</mn></mtd><mtd><mn>8</mn></mtd><mtd><mrow><mn>12</mn></mrow></mtd><mtd><mn>8</mn></mtd><mtd><mn>2</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>4</mn></mtd><mtd><mn>6</mn></mtd><mtd><mn>4</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable></mrow><mo>]</mo></mrow></mrow>
Каждая текстурная энергетическая карта является полноразмерным изображением, которое представляет результаты обработки входного изображения с использованием k-й маски.
После получения 22 энергетических карт некоторые симметричные пары комбинируются и в результате строятся 13 окончательных карт. Каждая симметричная пара карт заменяется усредненной картой. Например, маска E5L5 характеризует содержание горизонтальных краев, L5E5 - вертикальных. Среднее двух этих карт будет характеризовать наличие на изображении краев обоих этих типов. Перечислим 13 окончательных энергетических карт: L5E5/E5L5, L5S5/S5L5, W5W5, L5W5/W5L5, L5R5/R5L5, Е5Е5, ESWSIWSES, E5S5/S5E5, E5R5/R5E5, RSWSIW5RS, S5S5, S5R5/R5S5, R5R5.
Таким образом, используя фильтры Лавса, для любого пикселя получаем описание характеристик текстуры в некоторой окрестности выбранного пикселя.
На третьем шаге полученное изображение обрабатывается методом SURF. Метод SURF позволяет находить локальные точки с помощью матрицы Гессе и хорошо детектирует пятна, углы и края линий. Гессиан инвариантен относительно вращения, но не инвариантен масштабу. Поэтому метод SURF использует разномасштабные фильтры для нахождения гессианов.
Для каждой локальной точки считается направление максимального изменения яркости (градиент) и масштаб, взятый из масштабного коэффициента матрицы Гессе. Градиент в точке вычисляется с помощью фильтров Хаара.
Для эффективного вычисления фильтров Гессе и Хаара используется интегральное представление изображений.
Интегральное представление является матрицей, размерность которой совпадает с размерностью исходного изображения, а элементы считаются по формуле:
<mrow><mi>I</mi><mi>I</mi><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0,</mn><mi>y</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>i</mi><mo>≤</mo><mi>x</mi><mo>,</mo><mi>j</mi><mo>≤</mo><mi>y</mi></mrow></munderover><mrow><mi>I</mi><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow></mstyle></mrow>
где I(i,j) - яркость пикселов исходного изображения.
Имея интегральную матрицу, можно очень быстро вычислять сумму яркостей пикселов произвольных прямоугольных областей изображения по формуле:
<mrow><mi>S</mi><mi>u</mi><mi>m</mi><mi>O</mi><mi>f</mi><mtext> </mtext><mi>Re</mi><mtext> </mtext><mi>c</mi><mi>t</mi><mo>=</mo><mi>I</mi><mtext> </mtext><mi>I</mi><mrow><mo>(</mo><mi>A</mi><mo>)</mo></mrow><mo>+</mo><mi>I</mi><mtext> </mtext><mi>I</mi><mo stretchy="false">(</mo><mi>C</mi><mo stretchy="false">)</mo><mo>−</mo><mi>I</mi><mtext> </mtext><mi>I</mi><mo stretchy="false">(</mo><mi>B</mi><mo stretchy="false">)</mo><mo>−</mo><mi>I</mi><mtext> </mtext><mi>I</mi><mo stretchy="false">(</mo><mi>D</mi><mo stretchy="false">)</mo></mrow>
где ABCD - интересующий прямоугольник.
Обнаружение особых локальных точек в методе SURF использует бинаризированную аппроксимацию лапласиана гауссиана:
<mrow><mi>det</mi><mrow><mo>(</mo><mrow><mi>H</mi><msub><mtext> </mtext><mrow><mi>a</mi><mi>p</mi><mi>p</mi><mi>r</mi><mi>o</mi><mi>s</mi></mrow></msub></mrow><mo>)</mo></mrow><mo>=</mo><msub><mi>D</mi><mrow><mi>x</mi><mi>x</mi></mrow></msub><msub><mi>D</mi><mrow><mi>y</mi><mi>y</mi></mrow></msub><mo>−</mo><msup><mrow><mrow><mo>(</mo><mrow><mn>0.9</mn><msub><mi>D</mi><mrow><mi>x</mi><mi>y</mi></mrow></msub></mrow><mo>)</mo></mrow></mrow><mn>2</mn></msup></mrow>
.
Предлагаемый способ позволяет детектировать различные типы локальных особенностей за счет предварительной обработки энергетическими характеристиками Лавса.
Устройство детектирования локальных особенностей на изображении (фиг.2) содержит 2D камеру 1, выход которой подключен к входу блока регистрации изображения 2, выход которого подключен к следующим входам: входу блока построения карт градиентов 3, выход которого подключен к входу блока свертки изображения с ядром обнаружения краев 4.1, к входу блока свертки изображения с ядром обнаружения образа в виде ряби 4.2, к входу блока свертки изображения с ядром обнаружения пятен 4.3, к входу блока свертки изображения с ядром обнаружения волн 4.4, выходы которых подключены к входам блоков поиска локальных особенностей 5.1, 5.2, 5.3, 5.4 соответственно в каждом канале, выходы которых подключены к входам блоков хранения 6.1, 6.2, 6.3, 6.4; синхронность работы устройства обеспечивается генератором тактовых импульсов 7.
Устройство детектирования локальных особенностей на изображении реализуется следующим образом. Изображение с камеры поступает в блок регистрации изображения, который выполняет роль памяти, далее изображение преобразуется в градации серого в блоке построения карт градиентов и поступает параллельно в четыре канала, в каждом из которых матрица изображения сворачивается с различными ядрами, которые характеризуют текстурные признаки изображения. Полученные текстурные энергетические карты, в свою очередь, поступают параллельно на входы блоков поиска локальных особенностей, в которых происходит поиск локальных особенностей изображения способом детектирования SURF. Результатом работы блоков будет являться набор выделенных локальных особенностей с их геометрическими характеристиками.
Устройство детектирования локальных особенностей на изображении работает следующим образом. Изображение с 2D камеры 1 передается на блок регистрации изображения 2, из которого изображение поступает в блок построения карт градиентов 3, результатом работы в котором является изменение цветного изображения в градации серого. Полученное изображение в градациях серого параллельно поступает на: вход блока 4.1, результатом которого является текстурная энергетическая карта свертки изображения с ядром обнаружения краев; на вход блока 4,2, результатом которого является текстурная энергетическая карта свертки изображения с ядром обнаружения образа в виде ряби; на вход блока 4.3, результатом которого является текстурная энергетическая карта свертки изображения с ядром обнаружения пятен; на вход блока 4.4, результатом которого является текстурная энергетическая карта свертки изображения с ядром обнаружения волн. Полученные текстурные энергетические карты, в свою очередь, поступают параллельно на входы блоков поиска локальных особенностей 5.1, 5.2, 5.3, 5.4 соответственно, в которых происходит поиск локальных особенностей изображения способом детектирования SURF. Набор выделенных локальных особенностей с различными текстурными и геометрическими характеристиками хранится в блоках 6.1, 6.2, 6.3, 6.4.
Технический результат - детектирование локальных особенностей на изображении с определенными текстурными свойствами.