Способ нахождения соответствия особых точек цифровых изображений
Владельцы патента RU 2614494:
Российская Федерация, от имени которой выступает Министерство обороны Российской Федерации (RU)
Изобретение относится к цифровой обработке изображений. Техническим результатом является сокращение времени нахождения соответствия особых точек двух изображений за счет уменьшения размерности дескриптора особой точки цифрового изображения. В способе выделяют особые точки цифрового изображения, вычисляют дескриптор каждой особой точки первого и второго цифровых изображений при помощи вейвлет-преобразования, формируют окрестность особой точки цифрового изображения из пикселей цифрового изображения, осуществляют вейвлет-преобразование окрестности особой точки цифрового изображения, составляют дескриптор в виде вектора значений основных коэффициентов вейвлет-преобразования цифрового изображения, вычисляют евклидово расстояние между векторами дескрипторов особых точек первого и второго цифровых изображений, сравнивают дескрипторы особых точек первого и второго цифровых изображений, для каждой особой точки первого цифрового изображения находят единственную предварительно соответствующую особую точку второго цифрового изображения и для каждой особой точки второго цифрового изображения находят единственную предварительно соответствующую особую точку первого цифрового изображения; если особой точке А первого цифрового изображения предварительно поставлена в соответствие особая точка Б второго цифрового изображения, такая что этой особой точке Б второго цифрового изображения предварительно поставлена в соответствие особая точка А первого цифрового изображения, то считают особую точку А первого цифрового изображения соответствующей особой точке Б второго цифрового изображения, а особую точку Б второго цифрового изображения соответствующей особой точке А первого цифрового изображения. 5 ил.
Областью техники, к которой относится предлагаемый способ, является цифровая обработка изображений.
Известными аналогами предлагаемого способа являются нижеперечисленные способы.
Известен способ SIFT (Scale Invariant Feature Transform), в котором осуществляют выделение особых точек при помощи вычисления лапласиана гауссиана, вычисляют дескриптор каждой особой точки первого и второго цифровых изображений при помощи гистограммы ориентации градиентов, осуществляют сравнение каждого дескриптора особой точки первого цифрового изображения для нахождения соответствий особых точек цифрового изображения (Патент США 6711293, МПК G06K 9/46, оп. 23.03.2004).
Известен дескриптор PCA-SIFT (Ke Y., Sukthankar R. PCA-SIFT: A more distinctive representation for local image descriptors // Computer Vision and Pattern Recognition (CVPR'04), Vol. 2, 2004. - pp. 506-513), являющийся модификацией способа SIFT. На начальном этапе вычисляются значения магнитуды и ориентации градиента. Для каждой особой точки рассматривается окрестность размером 41*41 пиксель с центром в точке, которая является особой. Строится карта градиентов вдоль вертикального и горизонтального направлений. Далее выполняется построение SIFT-дескриптора. Для результирующего набора SIFT-дескрипторов осуществляется снижение размерности векторов до 32 элементов посредством анализа главных компонент (Principal Component Analysis, РСА).
Дескрипторы семейства HOG (Histograms of Oriented Gradients), включающие дескрипторы SHOG, PHOG, OHOG, GHOG (Dalal N., Triggs B. Histograms of Oriented Gradients for Human Detection // INRIA. - 2005), основаны на вычислении гистограммы градиентов интенсивности небольших участков изображения и объединении их в единую гистограмму.
Дескриптор GLOH (Gradient location-orientation histogram) (Mikolajczyk K., Schmid С.A Performance Evaluation of Local Descriptors // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 10, 2005. - pp. 1615-1630) является модификацией SIFT-дескриптора, который построен с целью повышения надежности. Вычисляется SIFT дескриптор, далее используется полярная сетка разбиения окрестности на бины: 3 радиальных блока с радиусами 6, 11 и 15 пикселей и 8 секторов. В результате получается вектор, содержащий 272 компоненты, который проецируется в пространство размерности 128 посредством использования анализа главных компонент (РСА).
Детектор DAISY (Tola Е., Lepetit V., Fua P. A Fast Local Descriptor for Dense Matching // IEEE Conference on Computer Vision and Pattern Recognition (CVPR'08), 2008. - pp. 1-8) изначально вводится для решения задачи сопоставления изображений в случае значительных внешних изменений, т.е. данный дескриптор в отличие от ранее рассмотренных работает на плотном множестве пикселей всего изображения. При этом показано, что дескриптор DAISY работает быстрее, чем SIFT, запущенный на плотном множестве пикселей. В DAISY использованы идеи построения SIFT-и GLOH- дескрипторов. Так, аналогично GLOH выбирается круговая окрестность особой точки, при этом бины представляются не частичными секторами, а окружностями.
Известен способ SURF (Speeded Up Robust Features), который отличается от способа SIFT тем, что дескрипторы особых точек цифрового изображения вычисляют при помощи нахождения матрицы Гессе, а вычисление дескрипторов осуществляется при помощи фильтров Хаара (Патент США 8670619, МПК G06K 9/46, оп. 11.03.2014).
Локальные бинарные шаблоны (ЛБШ) (Local Binary Patterns, LBP) (Ojala Т., M., Harwood D. (1996), "A Comparative Study of Texture Measures with Classification Based on Feature Distributions", Pattern Recognition, vol. 29, pp. 51-59) представляет собой описание окрестности пикселя изображения в двоичной форме. Оператор ЛБШ, который применяется к пикселю изображения, использует восемь пикселей окрестности, принимая центральный пиксель в качестве порога. Пиксели, которые имеют значения больше, чем центральный пиксель (или равное ему), принимают значения "1", те, которые меньше центрального, принимают значения "0". Таким образом, получается восьмиразрядный бинарный код, который описывает окрестность пикселя. Этот подход используется для описания текстуры областей.
Дескриптор LESH (Local Energy based Shape Histogram) (Sarfraz, S., Hellwich, O.: "Head Pose Estimation in Face Recognition across Pose Scenarios", Proceedings of VISAPP 2008, Int. conference on Computer Vision Theory and Applications, Madeira, Portugal, pp. 235-242, January 2008) основан на построении локальной энергетической модели при помощи фильтров Табора. Дескриптор используется только для задач распознавания лиц.
BRIEF-дескриптор (Binary Robust Independent Elementary Features) (Calonder M., Lepetit V, Strecha C., Fua P. BRIEF: Binary Robust Independent Elementary Features // 11th European Conference on Computer Vision (ECCV), 2010) предназначен для распознавания одинаковых участков изображения. Алгоритм распознавания сводится к построению случайного леса или наивного байесовского классификатора на некотором тренировочном множестве изображений и последующей классификации участков тестовых изображений. Небольшое количество операций обеспечивается за счет представления вектора признаков в виде бинарной строки, и как следствие, использования в качестве меры сходства расстоянии Хэмминга. На основе дескриптора BRIEF также базируется дескриптор ORB (Rublee E., Rabaud V., Konolige K., Bradski G "ORB: an efficient alternative to SIFT or SURF", Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011). Однако, только на некоторых тестовых изображениях точность детектирования с помощью BRIEF превышает точность SURF-дескрипторов.
Основным недостатком вышеперечисленных способов является большой размер дескриптора особой точки цифрового изображения, размерность которых составляет 64-128 элементов (чисел).
Задача, на решение которой направлено предлагаемое решение, является сокращение времени нахождения соответствий между точками двух цифровых изображений и уменьшение количества операций сравнения.
Поставленная задача решается тем, что в способе нахождения соответствия особых точек цифровых изображений для двух цифровых изображений выделяют особые точки цифрового изображения, вычисляют дескриптор каждой особой точки первого и второго цифровых изображений при помощи вейвлет-преобразования, для чего формируют окрестность особой точки цифрового изображения из пикселей цифрового изображения, осуществляют вейвлет-преобразование окрестности особой точки цифрового изображения с заданным конечным уровнем вейвлет-преобразования цифрового изображения, составляют дескриптор в виде вектора значений основных коэффициентов вейвлет-преобразования цифрового изображения, вычисляют евклидово расстояние между векторами дескрипторов особых точек первого и второго цифровых изображений, сравнивают дескрипторы особых точек первого и второго цифровых изображений, для каждой особой точки первого цифрового изображения находят единственную предварительно соответствующую особую точку второго цифрового изображения и для каждой особой точки второго цифрового изображения находят единственную предварительно соответствующую особую точку первого цифрового изображения; если особой точке А первого цифрового изображения предварительно поставлена в соответствие особая точка Б второго цифрового изображения, такая что этой особой точке Б второго цифрового изображения предварительно поставлена в соответствие особая точка А первого цифрового изображения, то считают особую точку А первого цифрового изображения соответствующей особой точке Б второго цифрового изображения, а особую точку Б второго цифрового изображения соответствующей особой точке А первого цифрового изображения.
Техническим результатом, достигаемым предлагаемым решением является то, что нахождение соответствия особых точек двух изображений осуществляется быстрее в 4 раза по сравнению с методом SIFT и в 8 раз по сравнению с методом SURF вследствие уменьшения количества операций сравнения за счет уменьшения размерности дескриптора особой точки цифрового изображения до 16 элементов.
Под цифровым изображением в данном случае понимают цветное растровое цифровое изображение, которое представляет собой двумерную дискретную функцию f(x, у) дискретных величин x, y, которая представляет собой цифровой сигнал значений интенсивности цвета, представленного в каком-либо цветовом пространстве, в точках плоскости, где x и y - координаты пикселя. Пиксель - это наименьший логический элемент двумерного цифрового изображения в растровой графике.
Особыми точками называют те точки цифрового изображения, которые содержат основную информацию о цифровом изображении. Особые точки обычно располагаются в местах сильного перепада яркости пикселей цифрового изображения, на границах и краях объектов. Особой точкой x' изображения называется точка, чья окрестность отличается от окрестностей близлежащих точек по выбранной мере, т.е. 
, где Ωx - окрестность точки х.
На фиг. 1 представлено устройство, с помощью которого может быть осуществлен предлагаемый способ. Устройство содержит: 1 - центральный процессор, 2 - блок оперативной памяти, 3 - накопитель на магнитном диске, 4 - видеомонитор, 5 - компьютерную мышь, 6 - клавиатуру. Входы центрального процессора 1 соединены с выходами блока оперативной памяти 2, накопителя на магнитном диске 3, компьютерной мыши 5 и клавиатуры 6. Выходы центрального процессора 1 соединены с входами блока оперативной памяти 2, накопителя на магнитном диске 3 и видеомонитора 4.
Осуществление предлагаемого способа нахождения соответствия особых точек цифровых изображений выполняют следующим образом. Сначала производят включение устройства, блок-схема которого приведена на фиг. 1, в сеть питания. Затем осуществляют загрузку программы, являющейся инструкцией для центрального процессора 1 по выполнению действий для осуществления нахождения соответствия особых точек цифровых изображений согласно алгоритма в блок оперативной памяти 2 при помощи сигналов от компьютерной мыши 5 и клавиатуры 6. Программу нахождения соответствия особых точек цифровых изображений предварительно сохраняют также на накопителе на магнитном диске 3.
В качестве входных данных для нахождения соответствия особых точек цифровых изображений используют цифровые растровые изображения, которые предварительно получены с любого цифрового устройства получения цифровых растровых изображений и сохранены на накопителе на магнитном диске 3. Далее при помощи выполнения инструкций загруженной программы нахождения соответствия особых точек цифровых изображений на центральном процессоре 1 осуществляют загрузку первого цифрового изображения, например, как на фиг. 2, с накопителя на магнитном диске 3 в блок оперативной памяти 2 при помощи управляющих сигналов от компьютерной мыши 5 и клавиатуры 6. После этого при помощи выполнения инструкций загруженной программы нахождения соответствия особых точек цифровых изображений на центральном процессоре 1 осуществляют загрузку второго цифрового изображения, например, как на фиг. 3, с накопителя на магнитном диске 3 в блок оперативной памяти 2 при помощи управляющих сигналов от компьютерной мыши 5 и клавиатуры 6. Далее посредством центрального процессора 1 в блоке оперативной памяти 2 осуществляют выделение особых точек цифрового изображения на первом и втором цифровых изображениях при помощи метода выделения особых точек вейвлет-преобразования (Ляшева С.А., Медведев М.В., Шлеймович М.П. Распознавание объектов на местности в системе управления БЛА // Научно-технический журнал «Авиационная техника», №3, 2014, с. 64-66).
После этого для каждой особой точки первого цифрового изображения осуществляют построение цифрового изображения окрестности особой точки цифрового изображения, формируя его из 16*16 пикселей, соседних с пикселем особой точки цифрового изображения.
Затем каждое полученное цифровое изображение окрестности особой точки первого цифрового изображения подвергают вейвлет-преобразованию цифрового изображения до заданного конечного уровня вейвлет-преобразования цифрового изображения.
Вейвлет-преобразование цифрового изображения - это его представление в виде обобщенного ряда Фурье по системе базисных масштабирующих функций согласно формуле (1)
и направленных вейвлет-функций по формуле (2)
где ϕ - масштабирующая функция,
ψ - вейвлет-функция,
Н - направление вейвлетов по горизонтали,
V - направление вейвлетов по вертикали,
D - направление вейвлетов по диагонали,
j, m, n - целые числа, m определяет положение функции на оси x, n - положение функции ϕj,m,n(x,y) на оси y, j определяет ширину функции, индекс i служит для идентификации направления вейвлетов по горизонтали, вертикали и диагонали (Гонсалес Р., Вудс. Р., Цифровая обработка изображений, 2005).
В данном способе в качестве базиса вейвлет-преобразования используются вейвлеты Хаара (Гонсалес Р., Вудс. Р., Цифровая обработка изображений, 2005). В этом случае масштабирующая и вейвлет-функции запишутся в виде формул (3-6)
где
Тогда дискретное вейвлет-преобразование изображения ƒ(x,y) определяется следующим образом (11)
где
где М - размер цифрового изображения по горизонтали,
N - размер цифрового изображения по вертикали,
j0 - целое число, задающее произвольный начальный масштаб,
Wϕ - коэффициенты, образующие усредненное изображение, например, как на фиг. 4 усредненное цифровое изображение 7 для второго уровня вейвлет-преобразования цифрового изображения фиг. 2,
коэффициенты 
определяют горизонтальные, вертикальные и диагональные детализирующие коэффициенты масштабов j вейвлет-преобразования цифрового изображения. Например, на фиг. 4 представлены горизонтальные детализирующие коэффициенты 8, вертикальные детализирующие коэффициенты 9 и диагональные детализирующие коэффициенты 10 второго уровня вейвлет-преобразования цифрового изображения фиг. 2, горизонтальные детализирующие коэффициенты 11, вертикальные детализирующие коэффициенты 12 и диагональные детализирующие коэффициенты 13 первого уровня вейвлет-преобразования цифрового изображения фиг. 2.
Исходное цифровое изображение ƒ(x,y) может быть восстановлено по данным коэффициентам Wϕ и 
при помощи обратного дискретного вейвлет-преобразования цифрового изображения.
Полученное усредненное цифровое изображение Wϕ подвергают повторному вейвлет-преобразованию заданное количество раз и, таким образом, получают разложение цифрового изображения на вейвлет-коэффициенты вейвлет-преобразования цифрового изображения на нескольких уровнях детализации вейвлет-преобразования цифрового изображения. Например, осуществляют вейвлет-преобразование цифрового изображения фиг. 2 до второго уровня детализации вейвлет-преобразования цифрового изображения и получают цифровое изображение как на фиг. 4.
В результате для каждой окрестности особой точки первого цифрового изображения получают основные коэффициенты вейвлет-преобразования цифрового изображения согласно формуле (14).
где u - конечный масштаб вейвлет-преобразования изображения.
Затем те же самые действия выполняют для второго цифрового изображения.
После этого по формуле (15) для каждой особой точки первого и второго цифровых изображений составляют дескриптор особой точки цифрового изображения в виде вектора значений основных коэффициентов вейвлет-преобразования окрестности особой точки цифрового изображения.
После этого при помощи центрального процессора 1 осуществляют вычисление евклидова расстояния между каждым вектором дескриптора особой точки первого цифрового изображения и каждым вектором дескриптора особой точки второго цифрового изображения.
При этом для каждой особой точки первого цифрового изображения в качестве предварительно соответствующей особую точку второго цифрового изображения с минимальным расстоянием.
После этого осуществляют вычисление евклидова расстояния между каждым вектором дескриптора особой точки второго цифрового изображения и каждым вектором дескриптора особой точки первого цифрового изображения.
При этом для каждой особой точки второго цифрового изображения в качестве предварительно соответствующей выбирают особую точку первого цифрового изображения с минимальным расстоянием.
Если особой точке А первого цифрового изображения предварительно соответствующей является особая точка Б второго цифрового изображения, такая что этой особой точке Б второго цифрового изображения предварительно соответствующей является особая точка А первого цифрового изображения, то считают особую точку А первого цифрового изображения соответствующей особой точке Б второго цифрового изображения, а особую точку Б второго цифрового изображения соответствующей особой точке А первого цифрового изображения.
Для визуального отображения результата при помощи центрального процессора 1 формируют цифровое изображение, состоящее из первого (фиг. 2) и второго цифровых изображений (фиг. 3), на нем отмечают особые точки первого и второго цифровых изображений, линиями соединяют соответствующие особые точки первого и второго цифрового изображения, например, как на фиг. 5, и выводят на видеомонитор 4.
Предлагаемый способ позволяет осуществлять получение дескриптора особой точки цифрового изображения размерностью в 16 элементов (чисел), что приводит к сокращению времени нахождения соответствий между точками двух цифровых изображений и уменьшению количества операций сравнения.
Способ нахождения соответствия особых точек цифровых изображений, при котором для двух цифровых изображений выделяют особые точки цифрового изображения, вычисляют дескриптор каждой особой точки первого и второго цифровых изображений при помощи вейвлет-преобразования, для чего формируют окрестность особой точки цифрового изображения из пикселей цифрового изображения, осуществляют вейвлет-преобразование окрестности особой точки цифрового изображения с заданным конечным уровнем вейвлет-преобразования цифрового изображения, составляют дескриптор в виде вектора значений основных коэффициентов вейвлет-преобразования цифрового изображения, вычисляют евклидово расстояние между векторами дескрипторов особых точек первого и второго цифровых изображений, сравнивают дескрипторы особых точек первого и второго цифровых изображений, для каждой особой точки первого цифрового изображения находят единственную предварительно соответствующую особую точку второго цифрового изображения и для каждой особой точки второго цифрового изображения находят единственную предварительно соответствующую особую точку первого цифрового изображения; если особой точке А первого цифрового изображения предварительно поставлена в соответствие особая точка Б второго цифрового изображения, такая что этой особой точке Б второго цифрового изображения предварительно поставлена в соответствие особая точка А первого цифрового изображения, то считают особую точку А первого цифрового изображения соответствующей особой точке Б второго цифрового изображения, а особую точку Б второго цифрового изображения соответствующей особой точке А первого цифрового изображения.
