Автоматика и телемеханика, № 10, 2022
© 2022 г. А.А. ЗАХАРОВ, канд. техн. наук (aa-zaharov@ya.ru)
(Муромский институт (филиал) ФГБОУ ВО
¾Владимирский государственный университет
им. Александра Григорьевича и Николая Григорьевича
Столетовых¿, Муром)
МЕТОД СОПОСТАВЛЕНИЯ ИЗОБРАЖЕНИЙ
С ИСПОЛЬЗОВАНИЕМ ТЕПЛОВЫХ ЯДЕР НА ГРАФАХ1
В работе представлен метод сопоставления изображений на основе теп-
ловых ядер. Метод позволяет выделять на начальном этапе с помощью
тепловых ядер на графах наиболее устойчивые особенности изображений
для последующего сопоставления. Для этого могут использоваться попу-
лярные дескрипторы. При использовании метода значительно сокраща-
ется количество ложных соответствий по сравнению с традиционными
подходами.
Ключевые слова: компьютерное зрение, сопоставление изображений, теп-
ловые ядра на графах.
DOI: 10.31857/S0005231022100063, EDN: AKDWHB
1. Введение
Методы сопоставления изображений часто используются в системах тех-
нического зрения. На точность сопоставления изображений влияют ракурс
съемки, особенности датчиков, освещенность сцены, взаимное перекрытие
объектов, наличие однородных объектов и поверхностей. При сопоставлении
изображений важны следующие показатели: скорость сопоставления; автома-
тизация процесса; робастность к помехам, перекрытиям, эффектам освеще-
ния; инвариантность к изменению ракурса и масштабированию сцены и т.д.
Дескрипторы описывают особенности изображений в некоторой области с
использованием конкретных признаков. Было разработано большое количе-
ство дескрипторов изображений. Все дескрипторы изображений можно раз-
делить на группы: локальные двоичные дескрипторы [1-5], спектральные де-
скрипторы [6-11], дескрипторы базового пространства [12, 13], дескрипторы
формы полигона [14, 15]. Локальные двоичные дескрипторы основаны на би-
нарном сравнении пикселей. Спектральные дескрипторы используют широ-
кий диапазон характеристик: интенсивность света, цвет, градиенты локаль-
ной области, статистические характеристики, моменты локальной области,
нормали поверхности и т.д. Дескрипторы базового пространства кодируют
вектор признаков в набор базовых функций. Дескрипторы формы полигона
используют такие характеристики, как площадь, периметр, центр тяжести и
т.д. Был разработан метод RANSAC, который позволяет уменьшать количе-
ство ошибок [16]. Также в последнее время стали применяться методы глубо-
кого обучения [17, 18] для сопоставления изображений. Слабыми сторонами
1 Работа выполнена при финансовой поддержке Министерства науки и высшего обра-
зования РФ (Госзадание ВлГУ № ГБ-1187/20).
60
методов с использованием глубокого обучения являются высокие вычисли-
тельные затраты, необходимость обучения, высокие требования к качеству и
объему обучающего набора.
Разработаны методы для сопоставления изображений на основе сравнения
структур с применением графов [19-25]. Методы основаны на использовании
спектральной теории графов [26]. Ограничением подобных методов является
то, что часто не принимаются во внимание признаки локальных окрестностей
изображений.
К одним из недостатков методов и алгоритмов нахождения соответствий
можно отнести то, что сопоставления находятся между всеми наборами обна-
руженных особенностей. При этом не учитывается то, что многие особенно-
сти могут пропадать при изменении ракурса, наличии взаимных перекрытий,
бликов. Это обстоятельство увеличивает вероятность нахождения ложных со-
ответствий.
В работе для сопоставления изображений предлагается использовать де-
скриптор SURF и тепловые ядра (heat kernel) на графах. Тепловые ядра опи-
сываются в рамках спектральной теории графов, которая часто используется
при разработке методов компьютерного зрения: сегментации изображений,
обнаружении объектов, распознавании сцен и т.д. [27-30].
В статье представлен новый метод сопоставления изображений, который
позволяет выделять и сопоставлять наиболее устойчивые особенности, при-
сутствующие на снимках. Это позволяет значительно снизить количество
ложных соответствий при сопоставлении снимков.
2. Метод сопоставления изображений
При сопоставлении снимков угол поворота сцены относительно наблюда-
теля может существенно меняться. При этом в сопоставлении могут участво-
вать множества особенностей, которые значительно отличаются. Это приво-
дит к увеличению количества неправильных соответствий. Для устранения
проблемы предлагается выделять на изображениях только самые устойчи-
вые особенности, которые с большей вероятностью будут присутствовать на
снимках.
На основе детектора SURF на сопоставляемых изображениях находятся
точечные особенности. Эти особенности используются для построения графа
Делоне. Для выделения устойчивых особенностей изображений используются
тепловые ядра на графах [31].
Тепловое ядро представляет собой изменение температуры в области во-
круг вершины с начальной тепловой энергией в момент времени t = 0. Для
графа G(V, E) тепловое ядро показывает, как информация проходит через
ребра с течением времени.
Нормализованная матрица Лапласа записывается в следующем виде [26]:
1,
если x = 0,
wuv
Ln =
-√
, если u = v и (u, v) ∈ E,
du,dv
0,
иначе.
61
100
90
80
70
60
50
40
30
20
10
0
5
10
15
20
25
30
35
40
45
50
t
Рис. 1. Изменение количества устойчивых вершин от времени.
Ln можно разложить на ΦΛΦT , где Λ = diag(λ1,λ2,... ,λ|V|) диагональ-
ная матрица, содержащая упорядоченные собственные значения, и Φ =
= (Φ1|Φ2| . . . |Φ|V|)
квадратная матрица с упорядоченными собственными
векторами в столбцах.
Уравнение теплопроводности, связанное с Ln, имеет вид [31, 32]:
dHt
= -LnHt,
dt
где t время, а тепловое ядро Ht решение уравнения теплопроводности.
Выражение теплового ядра имеет вид
Ht = e-tLn .
Тепловое ядро можно также представить следующим образом:
Ht = Φe-tΛΦT .
Тепловое ядро для вершин u и v графа G описывается выражением
|V |
∑
Ht(u,v) =
e-λitΦi(u)Φi(v).
i=1
На основе предыдущего выражения определяются устойчивые вершины
графа. Вершина считается устойчивой, если Ht(u, v) > σ, где σ минималь-
ное значение из p наибольших элементов матрицы Ht. Между особенностями
снимков, которые определены устойчивыми вершинами, будут находиться со-
ответствия.
При увеличении времени t количество устойчивых вершин k уменьшается
(рис. 1). При проведении исследований выбиралось значение t = 10.
Таким образом, алгоритм сопоставления изображений состоит из следую-
щих шагов:
Шаг 1. Выделяются особенности на сопоставляемых изображениях на
основе детектора SURF.
Шаг 2. По выделенным особенностям строится граф Делоне.
62
Шаг 3. На основе тепловых ядер определяются устойчивые вершины.
Шаг 4. На основе дескриптора SURF находятся соответствия между
устойчивыми особенностями сопоставляемых изображений.
3. Исследование разработанного метода
Эксперименты проводились с наборами снимков CMU, COIL-100, MIT-
CBCL. Разработанный метод сравнивался с методом SURF, который часто
используется при сопоставлении изображений и включен в различные биб-
лиотеки компьютерного зрения. При проведении исследований вычислялось
количество ¾выбросов¿ (неправильных соответствий) при изменении ракур-
са одного из изображений. При использовании метода SURF сопоставляется
большее количество особенностей изображения, чем при применении пред-
ставленного в работе метода. Это объясняется тем, что в разработанном ме-
тоде в сопоставлении участвуют только самые устойчивые особенности изоб-
ражения. Подобные особенности практически всегда выделяются при измене-
нии ракурса изображения. На рис. 2 и 3 представлены результаты сопостав-
ления изображений с использованием метода SURF и разработанного метода.
Неправильные соответствия представлены красными линиями.
При проведении исследований выявлено, что при увеличении угла пово-
рота объекта α количество верных соответствий q сокращается. Это про-
исходит как при использовании разработанного метода, так и при исполь-
зовании метода SURF. Однако при сопоставлении изображений с помощью
SURF количество ¾выбросов¿ значительно больше. При использовании ме-
a
b
Рис. 2. Сопоставление изображений (CMU, COIL-100): a метод SURF, b
разработанный метод.
63
a
b
Рис. 3. Сопоставление изображений (MIT-CBCL): a метод SURF, b раз-
работанный метод.
100
80
60
40
20
0
5
10
15
20
25
30
35
40
45
50
55
60
a, °
SURF
SURF + Heat Kernel
Рис. 4. Зависимость количества верных сопоставлений от ракурса изображений.
тода SURF количество неправильных соответствий может превосходить 40%
(рис. 4). При использовании предложенного в работе метода с изменением
ракурса на угол 45◦ количество ¾выбросов¿ не превышает 10%.
4. Заключение
Таким образом, в работе предложен метод сопоставления изображений с
использованием тепловых ядер на графах. Метод позволяет значительно сни-
жать количество ложных соответствий при изменении ракурса изображения.
Также метод не требует этапа предварительного обучения. Метод можно ис-
пользовать при решении различных задач компьютерного зрения: поиска и
отслеживания объектов, реконструкции трехмерных сцен, создания мозаик
и т.д.
64
СПИСОК ЛИТЕРАТУРЫ
1.
Krig S. Computer vision metrics. Survey, taxonomy, and analysis. Berkeley: Apress,
2014.
2.
Ojala T., Pietikainen M., Hardwood D. A comparative study of texture measures
with classification based on feature distributions // Patt. Recognit. 1996. V. 29 (1).
3.
Calonder M., Lepetit V., Strecha C., Fua P. BRIEF-Binary Robust Independent
Elementary Features // ECCV. 2010. P. IV. P. 778-792.
4.
Rublee E., Rabaud V., Konolige K., Bradski G. ORB: an efficient alternative to SIFT
or SURF // ICCV. 2011. P. 2564-2571.
5.
Leutenegger S., Chli M., Siegwart R. BRISK: Binary Robust Invariant Scalable Key-
points // International Conference on Computer Vision (ICCV’11). 2011. P. 2548-
6.
Lowe D.G. Distinctive Image Features from Scale-Invariant Keypoints // Int. J.
Comput. Vision. 2004. V. 60(2). P. 91-110.
7.
Bay H., Ess A., Tuytelaars T., Van Gool L. SURF: Speeded Up Robust Features //
Comput. Vision Image Understand. 2008. V. 110(3). P. 346-359.
8.
Tola E., Lepetit V., Fua P. DAISY: An Efficient Dense Descriptor Applied to Wide-
Baseline Stereo // IEEE Transact. Patt. Anal. Machine Intelligence. 2010. V. 32(5).
9.
Dalal N., Triggs B. Histograms of Oriented Gradients for Human Detection // Com-
put. Vision Patt. Recognit. 2005. V. 1. P. 886-893.
10.
Scharstein D., Szeliski R. A Taxonomy and Evaluation of Dense Two-Frame Stereo
Correspondence Algorithms // Int. J. Comput. Vision. 2002. No. 47. P. 7-42.
11.
Jun B., Kim D. Robust Face Detection Using Local Gradient Patterns and Evidence
Accumulation // Patt. Recognit. 2012. V. 45(9). P. 3304-3316.
12.
Bracewell R. The Fourier Transform and Its Applications. McGraw-Hill Science/
Engineering/Math; 3 edition, 1999.
13.
Ren X., Ramanan D. Histograms of Sparse Codes for Object Detection // Conference
on Computer Vision and Pattern Recognition. 2013.
14.
Matas J., Chum O., Urba M., Pajdla T. Robust Wide Baseline Stereo from Maxi-
mally Stable Extremal Regions // Proceedings of British Machine Vision Conference.
15.
Yang M., Kpalma K., Ronsin J. A Survey of Shape Feature Extraction Techniques //
16.
Szeliski R. Computer Vision: Algorithms and Applications. Springer, 2010.
17.
Ufer N., Ommer B. Deep Semantic Feature Matching // CVPR 2017, 2017. P. 6914-
18.
Gao Q., Wang F., Xue N., Yu J.G., Xia G.S. Deep Graph Matching under Quadratic
Constraint // CVPR 2021, 2021. P. 5069-5078.
65
19.
Scott G., Longuet-Higgins H. An algorithm for associating the features of two im-
ages // Proc. of Royal Soc. 1991. V. 244. P. 21-26.
20.
Zakharov A.A., Zhiznyakov A.L., Titov V.S. A method for feature matching in im-
ages using descriptor structures // Comput. Opt. 2019. V. 43(5). P. 811-818.
21.
Shapiro L.S., Brady J.M. Feature-based correspondence - an eigenvector approach //
Image Vision Comput. 1992. V. 10(5). P. 283-288.
22.
Carcassoni M., Hancock E. Spectral correspondence for point pattern matching //
Patt. Recognit. 2003. V. 36(1). P. 193-204.
23.
Leordeanu M., Hebert M. A spectral technique for correspondence problems using
pairwise constraints // Tenth IEEE International Conference on Computer Vision.
24.
Cour T., Srinivasan P., Shi J. Balanced Graph Matching // Proceedings Conference
Neural Information Processing Systems. 2006.
25.
Delponte E., Isgro F., Odone F., Verri A. SVD-matching using SIFT features //
Graphical Models. 2006. V. 68 (5-6). P. 415-431.
26.
Chung F.R.K. Spectral graph theory. AMS, 1997.
27.
Zakharov A.A., Titov D.V., Zhiznyakov A.L., Titov V.S. Visual attention method
based on vertex ranking of graphs by heterogeneous image attributes // Comput.
28.
Zakharov A.A., Barinov A.E., Zhiznyakov A.L., Titov V.S. Object detection in im-
ages with a structural descriptor based on graphs // Comput. Opt. 2018. V. 42(2).
29.
Zakharov A., Barinov A., Zhiznyakov A. Faces selection in images using the spectral
graph theory and constraints // 2017 International Conference on Industrial Engi-
neering, Applications and Manufacturing. 2017.
30.
Zakharov A., Tuzhilkin A., Zhiznyakov A. Automatic building detection from
satellite images using spectral graph theory // International Conference on Me-
chanical Engineering, Automation and Control Systems (MEACS
2015).
2015.
31.
Bai X., Wilson R.C., Hancock E.R. Characterising graphs using the heat kernel //
British machine vision conference. 2005. P. 315-324.
32.
Ghawalby H., Hancock E.R. Heat kernel embeddings, differential geometry and graph
structure // Axioms. 2015. V. 4. P. 275-293.
Статья представлена к публикации членом редколлегии А.А. Лазаревым.
Поступила в редакцию 01.02.2022
После доработки 20.06.2022
Принята к публикации 29.06.2022
66
