Geodesic
Polynomial point matching algorithm based on epipolar geometry
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 4, pp. 83-104 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Point correspondence problem is one of the key problems in computer vision. There are several approaches for solving this problem, such as descriptor-based approach, an approach that is based on epipolar geometry, as well as hybrid methods. This article reviews point matching by the means of epipolar geometry. These methods are intended to be used with a photogrammetric system that is currently under development. The system uses artificial circular retroreflective targets. We propose to use multipartite weighted undirected graph as a mathematical model of the point correspondence problem. Its vertices represent images of the circle targets in the photos, while its edges define the set of images that satisfy mutual epipolar constraint. We show the exact solution of the point correspondence problem via superclique, and show that the exact solution has exponential time complexity. We also review various heuristic approaches to point matching. Heuristic algorithms do not always provide an exact solution of the problem, but they have much lower time complexity. The architecture of our photogrammetric systems makes it possible to use such fast heuristic point matching algorithms: all the discrepancies will be automatically determined and filtered out in the further stages of photogrammetric reconstruction. This allows to iteratively find an exact reconstruction of the scene in reasonable time. We propose a new polynomial point matching algorithm, and estimate its time complexity as O($n^4$). We also estimate its efficiency and performance in comparison to other in-house algorithms, as well as in comparison to H.-G. Maas’s algorithms. Our new algorithm outperforms all competitors.
Keywords: photogrammetry, computer vision, point matching, correspondence problem, epipolar geometry, stereo vision.
Mots-clés : maximum clique prob- lem, polynomial algorithm 
@article{VYURV_2018_7_4_a5,
     author = {S. A. Tushev and B. M. Sukhovilov},
     title = {Polynomial point matching algorithm based on epipolar geometry},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {83--104},
     year = {2018},
     volume = {7},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2018_7_4_a5/}
}
TY  - JOUR
AU  - S. A. Tushev
AU  - B. M. Sukhovilov
TI  - Polynomial point matching algorithm based on epipolar geometry
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2018
SP  - 83
EP  - 104
VL  - 7
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VYURV_2018_7_4_a5/
LA  - ru
ID  - VYURV_2018_7_4_a5
ER  - 
%0 Journal Article
%A S. A. Tushev
%A B. M. Sukhovilov
%T Polynomial point matching algorithm based on epipolar geometry
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2018
%P 83-104
%V 7
%N 4
%U http://geodesic.mathdoc.fr/item/VYURV_2018_7_4_a5/
%G ru
%F VYURV_2018_7_4_a5
S. A. Tushev; B. M. Sukhovilov. Polynomial point matching algorithm based on epipolar geometry. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 4, pp. 83-104. http://geodesic.mathdoc.fr/item/VYURV_2018_7_4_a5/

[1] R. Hartley, A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed, Cambridge University Press, 2004

[2] S. A. Tushev, B. M. Sukhovilov, E. M. Sartasov, “Architecture of Industrial Close-Range Photogrammetric System with Multi-Functional Coded Targets”, Procedings of the 2017 2nd International Ural Conference on Measurements (UralCon) (Chelyabinsk, Russia, 2017), IEEE Xplore Digital Library, 2017, 435–442 | DOI

[3] S. A. Tushev, B. M. Sukhovilov, “Efficiency Analysis of Photogrammetric System by Simulation Modelling. Bulletin of the South Ural State University. Ser”, Mathematical Modelling, Programming Computer Software (Bulletin SUSU MMCS), 11:1 (2018), 109–123 | DOI

[4] S. A. Tushev, B. M. Sukhovilov, “Parallel Algorithms for Effective Correspondence Problem Solution in Computer Vision”, Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering, 6:2 (2017), 49–68 | DOI

[5] D. G. Lowe, “Distinctive Image Features from Scale Invariant Keypoints”, International Journal of Computer Vision, 60 (2004), 91–110 | DOI

[6] H. Bay, T. Tuytelaars, G. o. van, “SURF: Speeded Up Robust Features”, Computer Vision and Image Understanding, 110:3 (2008), 346–359 | DOI

[7] C. Harris, M. A. Stephens, “A Combined Corner and Edge Detector”, Proceedings of the 4th Alvey Vision Conference, 1988, 147–151 | DOI

[8] S. A. Tushev, B. M. Sukhovilov, “Effective Graph-Based Point Matching Algorithms”, Procedings of the 2nd International Conference on Industrial Engineering, Applications and Manufacturing, ICIEAM (Chelyabinsk, Russia, 2016.), IEEE Xplore Digital Library, 1–5 | DOI

[9] B. M. Sukhovilov, E. M. Sartasov, E. A. Grigorova, “Improving the Accuracy of Determining the Position of the Code Marks in the Problems of Constructing Three-dimensional Models of Objects”, Procedings of the 2nd International Conference on Industrial Engineering, Applications and Manufacturing, ICIEAM (Chelyabinsk, Russia, 2016), IEEE Xplore Digital Library, 1–4 | DOI

[10] H. -G. Maas, “Complexity Analysis for the Establishment of Image Correspondences of Dense Spatial Target Fields”, International Archives of Photogrammetry and Remote Sensing, 29 (1992), 102–107

[11] J. Dold, H. -G. Maas, “An Application of Epipolar Line Intersection in a Hybrid Close Range Photogrammetric System”, International Archives of Photogrammetry and Remote Sensing, 30:5 (1994), 65–70

[12] H. -G. Maas, A. Gruen, “Digital Photogrammetric Techniques for High-Resolution ThreeDimensional Flow Velocity Measurements”, Optical Engineering, 34:7 (1995), 1970–1976

[13] Z. Zhu, et al., “et al. Automatic Three-Dimensional Measurement of Large-Scale Structure Based on Vision Metrology”, Scientific World Journal, 2014:Article ID 185269 (2014), 10 pages | DOI

[14] D. V. Yurin, “A Modern Review of the Structure of Automatic Systems for 3D Reconstruction from Images”, Proceedings of International Scientific Conference Dedicated to the 80th Anniversary of Academician V.A. Melnikov, 2009, 118–121

[15] Z. Zhang, et al., “et al. A Robust Technique for Matching Two Uncalibrated Images through the Recovery of the Unknown Epipolar Geometry”, Artificial Intelligence, 78:1 (1995), 1–2 | DOI

[16] V. Kolmogorov, R. Zabih, “Computing Visual Correspondence with Occlusions Using Graph Cuts”, Proceedings Eighth IEEE International Conference on Computer Vision, ICCV 2001 (Vancouver, British Columbia, Canada, July 7–14), v. 2, 2001, 508–515 | DOI

[17] A. Y. Tuzhilkin, A. A. Zaharov, A. L. Zhiznyakov, “Finding Matches on Images Using Eigendecomposition of Graphs for 3D Reconstruction Tasks”, Polzunov Bulletin, 2:4 (2015), 37–39

[18] T. A. Clarke, et al., “et al. Automated Three Dimensional Measurement Using Multiple CCD Camera Views”, The Photogrammetric Record, 15:85 (1995), 27–42

[19] C. Leung, B. C. Lovell, “3D Reconstruction through Segmentation of Multi-View Image Sequences”, Proceedings of the 2003 APRS Workshop on Digital Image Computing, 2003, 87–92

[20] F. Qiqiang, L. Guangyun, “Matching of Artificial Target Points Based on Space Intersection”, The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XXXVII (2008), 111–114

[21] C. S. Fraser, S. Cronk, “A Hybrid Measurement Approach for Close-Range Photogrammetry”, ISPRS Journal of Photogrammetry and Remote Sensing, 64:3 (2009), 328–333 | DOI

[22] B. Triggs, et al., “et al. Bundle Adjustment – A Modern Synthesis”, Vision Algorithms: Theory and Practice, 1883 (2000), 298–372 | DOI

[23] A. P. Züge, R. Carmo, “On Comparing Algorithms for the Maximum Clique Problem”, Discrete Applied Mathematics. Elsevier B.V., 2018. No, 2, no. 2, 1–13 | DOI

[24] J. W. Moon, L. Moser, “On Cliques in Graphs”, Israel Journal of Mathematics, 3:1 (1965), 3–28 | DOI

[25] J. M. Robson, Finding a Maximum Independent Set in Time O(2\^{ }(n/4)), Technical Report of the Universite de Bordeaux I } {\tt https://www.labri.fr/perso/robson/mis/techrep.html

[26] Concurrency Runtime } {\tt https://msdn.microsoft.com/en-us/library/dd504870.aspx