=Paper=
{{Paper
|id=Vol-2667/paper63
|storemode=property
|title=Conformed estimates of histograms of oriented gradients
|pdfUrl=https://ceur-ws.org/Vol-2667/paper63.pdf
|volume=Vol-2667
|authors=Kirill Pugachev
}}
==Conformed estimates of histograms of oriented gradients ==
https://ceur-ws.org/Vol-2667/paper63.pdf
Conformed estimates of histograms of oriented
gradients
Kirill Pugachev
Samara National Research University
Samara, Russia
pugachev_k.g@mail.ru
Abstract—In this paper, we propose a new image matching results of experiments show that the proposed OS-SIFT
algorithm based on the scene feature points matching. The algorithm gives a robust registration result for optical-to-
algorithm is based on the well-known HOG descriptor, which SAR images and outperforms other state-of-the-art
divides the image into small areas and calculates histogram for algorithms in terms of registration accuracy.
each gradient direction. The idea is to use a proximity measure
based on the conformity principle as a proximity criterion for The performance of image detection and matching using
the feature descriptors instead of the traditionally used SIFT-method and RANSAC with Euclidean metric was
Euclidean distance. The efficiency of this measure of proximity researched in paper [10]. It was shown that the best results
in image matching problem based on image fragments’ are archived using threshold value of 0.6. Evaluation of the
intensity was researched in our previous papers. We use the SIFT-method in image recognition task using various
ratio of correctly found feature points’ number after cross- proximity measures was presented in paper [11].
checking to the total number of correctly found feature points
as a quality criterion of image matching results. Improved SIFT-BRISK algorithm was proposed in paper
[12]. This algorithm allows using the advantages of both
Keywords—image matching, conformity principle, proximity algorithms. A distinctive and robust weighted local intensity
measures, descriptors, histograms of oriented gradients binary SIFT descriptor (WLIB-SIFT) was proposed in paper
[13].
I. INTRODUCTION
To present these features, the descriptors are formed, and
The image matching task is to find the corresponding then image matching is performed using some measure of
point for every point of the first image in the second image fragments proximity. Sum of absolute differences [14, 15], a
of the same scene. Image matching process consists of three sum of squared differences [16, 17], value normalized cross-
main stages. Firstly, image preprocessing is performed, for correlation of fragments [18, 19] and etc. are widely used in
example, using methods [1]. Then, images are matched. both approaches as a criterion of proximity.
Finally, matching errors are corrected. Both direct and
indirect matching methods are used. We have presented and implemented an area-based
matching method, based on the principle of fragments
Direct methods use values of image pixel intensity or its conformity in papers [20, 21]. We have shown that
gradients directly. For example, area-based image matching conformity criterion allows performing more accurate image
methods are direct methods. In this case, image fragments fragments matching in these papers. This is due to the fact
with a center at this point are formed for every point of both that the method of conformed estimates performs many
images. To find corresponding points, search area in the more comparisons than other proximity measures.
second image is specified for every point of the first image.
The corresponding point is the point in the search area, In this paper, we develop this line of research. Some
where the value of fragment proximity criterion is maximum scenes can contain similar objects. In this case, uniqueness
or minimum. of features can be very important. So, to improve it, we
propose a new image matching criterion based on the
Indirect methods [2–5] are based on the matching of the conformity principle as a measure of proximity of the
scene features, for example, feature points, object edges and histogram of oriented gradients.
etc.
One of the most commonly used features are SIFT- II. PROBLEM STATEMENT
features [2]. These features have good invariance on Let us state that F1 and F2 are two images, which
rotation, scale scaling, brightness, and a certain degree of are obtained by multi-view shooting of the same scene.
stability on changes in perspective, affine transformation,
Let us also state that some features of the scene were
and noise.
detected on both images, for example, feature points.
There are many variations of this method. In paper [6] To describe these features, we form descriptor
SIFT-method was evaluated in various color spaces.
Evaluation of SIFT-like algorithm’s performance was vectors fi1 and f j2 , i 1, N , j 1, M . N and M are
presented in paper [7]. count of feature points, which were found for first and
Development of the SIFT-method is continued even in
second images correspondingly. Every descriptor
our days. So, new SIFT algorithm based on the adaptive contains K elements. The task is to find the
contrast threshold was presented in paper [8]. The proposed corresponding point with descriptor f j2 of the second
algorithm has higher efficiency and accuracy. It realized the image for every point with descriptor fi1 of the first
efficient control of a feature point number in multi-scene
matching. image.
As stated above, the sum of absolute differences or
A new high-resolution optical-to-SAR image registration sum of squared differences of vector components are
algorithm was presented in paper [9]. The experimental
Copyright © 2020 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
Data Science
most often used during descriptor matching. These 4
proximity measures are commonly used to compare Wi , j Wi ,qj,r ,
q 1
elements, which present values of image pixel r 1
intensity or values of intensity gradient. Hamming where
distance is also used to compare binary descriptors, 8
Wi ,qj,r (f si , j ,q ,r f pi , j ,q ,r )2 .
which are used, for example, to represent ORB- s 1
features. p s 1
Let us take a look at the problem of descriptor Wi ,qj,r is the value of proximity measure of qth,rth
vectors matching using a proximity measure based on part of descriptor vectors for ith and jth feature points
the principle of conformity. An important feature of correspondingly, f si , j ,q,r and f pi , j ,q ,r are sth and pth
this measure of proximity is that not only the
comparison of descriptor vectors elements, but also all elements of difference vector Δf i , j ,q,r fi1,q,r f j2,q,r , fi1,q ,r
its possible combinations are performed. Wherein a and f j2,q ,r are qth,rth histograms of oriented gradients of
big number of values is formed even with small ith and jth feature points of first and second images
fragment size. It allows increasing informativity of correspondingly. In this case K 8 , because
data and the probability of correct feature points histograms contain 8 elements.
matching. It can be easily checked, that in case of this size of
Let’s fi1 and f j2 , i 1, N , j 1, M , are two descriptor vectors using of component proximity
descriptor vectors of points of first and second images measure (2) allows reducing computational efforts in
correspondingly. If every descriptor is a vector with more than 36 times. Of course, due to reliability
K elements, conformed measure of proximity is reduction, question about changes in the accuracy of
defined as: this measure is stated. In the next section we show
K results of experimental research of accuracy for this
Wi , j (f si , j f pi , j ) 2 , feature points matching method.
s 1
p s 1
IV. RESULTS OF EXPERIMENTS
where f si , j and f are sth and pth elements of
i, j
p
The efficiency of the proposed algorithm, which is
difference vector Δf i , j : based on using of conformity function as proximity measure
Δf i , j fi1 f j2 . of descriptor vectors, was tested on images [22] presented
Values of the conformity function (1) of feature on Figure 1.
points obtained from the first image are calculated for
every feature point of the second image. jth feature
point of the second image is chosen as the
corresponding point for ith point of the first image if its
value of the function Wi , j is minimum. The task is to
construct an image matching algorithm by feature
points, which uses a conformity function value as a
measure of proximity for descriptors based on
histograms of oriented gradients (HOG). Fig. 1. Test images.
III. CONFORMING MATCHING OF HOG-DESCRIPTORS Feature points were detected for both images, and
To construct the algorithm, we based on the descriptors were formed using functions from computer
popular implementation of HOG-descriptors in SIFT vision library OpenCV [23]. Then, corresponding points
method [3]. We form descriptors using image were found for every point of the first image using two
fragments with a size of 16 16 pixels. According to methods: component proximity measure (2) and Euclidean
metric.
paper [3], we divide fragment into 16 subfragments
with a size of 4 4 pixels. For every subfragment we We performed the same operations for every point of the
form a histogram of oriented gradients with 8 blocks, second image: feature point detection and matching. Then,
which are related to 8 descriptor elements. Thus, every to exclude incorrectly found points, cross-check of obtained
descriptor contains 4 4 8 128 elements. points was performed.
The use of a conformed measure of proximity for The results of experiments are presented in Table 1. The
descriptor vectors with the size of 128 1 need a lot of number of correctly found feature points (first row) and the
computational resources. To reduce calculational number of correctly found feature points after cross-check
efforts, we propose a new algorithm calculating (second row) were counted. We use the ratio of number of
measures of proximity for every of 16 descriptor correctly found feature points before and after cross-check
as measure of accuracy. In the third row of Table 1 relative
subareas based on the values of its histograms of values of accuracy for both methods are presented.
oriented gradients. A modified conformed measure of
proximity is defined as: Table 1 shows that the low number of points is found
correctly when a conformed measure of proximity (3) was
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 285
Data Science
used. At the same time, the relative value of correctly found [7] I. Abadi, A. Moussa and N. El-Sheimy, "Evaluation of feature points
feature points is higher for this measure. In many descriptors' performance for visual finger printing localization of
smartphones," IEEE/ION Position, Location and Navigation
applications of computer vision, this factor may be critical Symposium (PLANS), Monterey, CA, pp. 1002-1008, 2018. DOI:
because even the low number of incorrect points can disrupt 10.1109/PLANS.2018.8373478.
the work of technologies based on image matching using. [8] J. Xu, S. Lin and A. Teng, "Improved SIFT algorithm based on
adaptive contrast threshold," 4th International Conference on
TABLE I. RESULTS OF RESEARCH Computer and Technology Applications (ICCTA), Istanbul, pp. 151-
155, 2018. DOI: 10.1109/CATA.2018.8398673.
Proximity measure
[9] Y. Xiang, F. Wang and H. You, "OS-SIFT: A Robust SIFT-Like
Measure of proximity Euclidean Conformity Algorithm for High-Resolution Optical-to-SAR Image Registration in
distance function Suburban Areas," IEEE Transactions on Geoscience and Remote
Total number of correctly found 571 535 Sensing, vol. 56, no. 6, pp. 3078-3090, 2018. DOI: 10.1109/TGRS.
feature points 2018.2790483.
Number of correctly found feature 396 377 [10] F. Guo, J. Yang, Y. Chen and B. Yao, "Research on image detection
points after cross-check
and matching based on SIFT features," 3rd International Conference
Relative number of correctly found 0.693 0.70 on Control and Robotics Engineering (ICCRE), Nagoya, pp. 130-134,
feature points 2018. DOI: 10.1109/ICCRE.2018.8376448.
[11] L. Păvăloi and C. D. Niţă, "Iris recognition using SIFT descriptors
V. CONCLUSION with different distance measures," 10th International Conference on
The proposed modification of the image matching Electronics, Computers and Artificial Intelligence (ECAI), Iasi,
algorithm using component conformity function as a Romania, pp. 1-4, 2018. DOI: 10.1109/ECAI.2018.8678987.
measure of proximity allows reducing computational efforts [12] B. Zhong and Y. Li, "Image Feature Point Matching Based on
Improved SIFT Algorithm," IEEE 4th International Conference on
more than 36 times. It was determined that the constructed Image, Vision and Computing (ICIVC), Xiamen, China, pp. 489-493,
algorithm has a high accuracy. Although the number of 2019. DOI: 10.1109/ICIVC47709.2019.8981329.
correctly found feature points was slightly lower, when [13] M. Wei and P. Xiwei, "WLIB-SIFT: A Distinctive Local Image
criterion based on component conformity function was used, Feature Descriptor," IEEE 2nd International Conference on
the relative number of correctly found feature points was Information Communication and Signal Processing (ICICSP),
higher. This can be important in some applications of Weihai, China, pp. 379-383, 2019. DOI: 10.1109/ICICSP48821.2019.
8958587.
computer vision.
[14] S.H. Lee and S. Sharma, "Real-time disparity estimation algorithm for
ACKNOWLEDGMENT stereo camera systems," IEEE Transactions on Consumer Electronics,
vol. 57, no. 3, pp. 1018-1026, 2011. DOI: 10.1109/TCE.2011.
This work was financially supported by the Russian 6018850.
Foundation for Basic Research under grant #18-07-01390, [15] R.K. Gupta and S. Cho, "Window-based approach for fast stereo
and by the Ministry of Science and Higher Education correspondence," IET Computer Vision, vol. 7, no. 2, pp. 123-134,
2013. DOI: 10.1049/iet-cvi.2011.0077.
(project).
[16] A. Fusiello, U. Castellani and V. Murino, "Relaxing Symmetric
Multiple Windows Stereo Using Markov Random Fields," Lecture
REFERENCES Notes in Computer Science, pp. 91-105, 2001. DOI: 10.1007/3-540-
[1] V. Fursov, "Constructing a quadratic-exponential FIR-filter with an 44745-8_7.
extended frequency response midrange," Computer Optics, vol. 42, [17] R. Yang and M. Pollefeys, "Multi-resolution real-time stereo on
no. 2, pp. 297-305, 2018. DOI: 10.18287/2412-6179-2018-42-2-297- commodity graphics hardware," IEEE Computer Society Conference
305. on Computer Vision and Pattern Recognition, Madison, WI, USA, pp.
[2] D. Lowe, "Distinctive Image Features from Scale-Invariant I-I, 2003. DOI: 10.1109/CVPR.2003.1211356.
Keypoints," International Journal of Computer Vision, vol. 60, no. 2, [18] S. Satoh, "Simple low-dimensional features approximating NCC-
pp. 91-110, 2004. DOI: 10.1023/b:visi.0000029664.99615.94. based image matching," Pattern Recognition Letters, vol. 32, no. 14,
[3] H. Bay, T. Tuytelaars and L. Van Gool, "SURF: Speeded Up Robust pp. 1902-1911, 2011. DOI: 10.1016/j.patrec.2011.07.027.
Features," Computer Vision – ECCV, pp. 404-417, 2006. DOI: [19] F. Cheng, H. Zhang, D. Yuan and M. Sun, "Stereo matching by using
10.1007/11744023_32. the global edge constraint," Neurocomputing, vol. 131, pp. 217-226,
[4] E. Rublee, V. Rabaud, K. Konolige and G. Bradski, "ORB: An 2014. DOI: 10.1016/j.neucom.2013.10.022.
efficient alternative to SIFT or SURF," International Conference on [20] V. Fursov, A. Gavrilov, Y. Goshin and K. Pugachev, "The technology
Computer Vision, Barcelona, pp. 2564-2571, 2011. DOI: 10.1109/ of image matching by the criterion of conformity of image fragments
ICCV.2011.6126544. samples," Journal of Physics: Conference Series, vol. 1096, 012084,
[5] P. Alcantarilla, J. Nuevo and A. Bartoli, "Fast Explicit Diffusion for 2018. DOI: 10.1088/1742-6596/1096/1/012084.
Accelerated Features in Nonlinear Scale Spaces," Procedings of the [21] V. Fursov, Y. Goshin and K. Pugachev, "Adaptive algorithm of
British Machine Vision Conference, 2013. DOI: 10.5244/c.27.13. conforming image matching," CEUR Workshop Proceedings, vol.
[6] K. van de Sande, T. Gevers and C. Snoek, "Evaluating Color 2416, pp. 26-33, 2019. DOI: 10.18287/1613-0073-2019-2416-26-33.
Descriptors for Object and Scene Recognition," IEEE Transactions on [22] "Middlebury Stereo Datasets," Vision.middlebury.edu, 2020 [Online].
Pattern Analysis and Machine Intelligence, vol. 32, no. 9, pp. 1582- URL: https://vision.middlebury.edu/stereo/.
1596, 2010. DOI: 10.1109/TPAMI.2009.154.
[23] "OpenCV," 2020 [Online]. URL: https://opencv.org/.
VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 286