Geodesic
Parallel algorithms for effective correspondence problem solution in computer vision
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 6 (2017) no. 2, pp. 49-68 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We propose new parallel algorithms for correspondence problem solution in computer vision. We develop an industrial photogrammetric system that uses artificial retroreflective targets that are photometrically identical. Therefore, we cannot use traditional descriptor-based point matching methods, such as SIFT, SURF etc. Instead, we use epipolar geometry constraints for finding potential point correspondences between images. In this paper, we propose new effective graph-based algorithms for finding point correspondences across the whole set of images (in contrast to traditional methods that use 2-4 images for point matching). We give an exact problem solution via superclique and show that this approach cannot be used for real tasks due to computational complexity. We propose a new effective parallel algorithm that builds the graph from epipolar constraints, as well as a new fast parallel heuristic clique finding algorithm. We use an iterative scheme (with backprojection of the points, filtering of outliers and bundle adjustment of point coordinates and cameras’ positions) to obtain an exact correspondence problem solution. This scheme allows using heuristic clique finding algorithm at each iteration. The proposed architecture of the system offers a significant advantage in time. Newly proposed algorithms have been implemented in code; their performance has been estimated. We also investigate their impact on the effectiveness of the photogrammetric system that is currently under development and experimentally prove algorithms’ efficiency.
Keywords: computer vision, photogrammetry, correspondence problem, parallel algorithms, epipolar geometry.
Mots-clés : maximum clique problem 
@article{VYURV_2017_6_2_a3,
     author = {S. A. Tushev and B. M. Sukhovilov},
     title = {Parallel algorithms for effective correspondence problem solution in computer vision},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {49--68},
     year = {2017},
     volume = {6},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2017_6_2_a3/}
}
TY  - JOUR
AU  - S. A. Tushev
AU  - B. M. Sukhovilov
TI  - Parallel algorithms for effective correspondence problem solution in computer vision
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2017
SP  - 49
EP  - 68
VL  - 6
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURV_2017_6_2_a3/
LA  - en
ID  - VYURV_2017_6_2_a3
ER  - 
%0 Journal Article
%A S. A. Tushev
%A B. M. Sukhovilov
%T Parallel algorithms for effective correspondence problem solution in computer vision
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2017
%P 49-68
%V 6
%N 2
%U http://geodesic.mathdoc.fr/item/VYURV_2017_6_2_a3/
%G en
%F VYURV_2017_6_2_a3
S. A. Tushev; B. M. Sukhovilov. Parallel algorithms for effective correspondence problem solution in computer vision. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 6 (2017) no. 2, pp. 49-68. http://geodesic.mathdoc.fr/item/VYURV_2017_6_2_a3/

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

[2] D. Baggio, Mastering OpenCV with Practical Computer Vision Projects, Packt Publishing, 2012

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

[4] D. G. Lowe, “Object recognition from local scale-invariant features”, Proceedings of the Seventh IEEE International Conference on Computer Vision, 2 (1999), 1150–1157 | DOI

[5] C. S. Fraser, “Innovations in automation for vision metrology systems”, Photogrammetric Record, 15:90 (1997), 901–911

[6] B. M. Sukhovilov , E. A. Grigorova, “Development of a Photogrammetric System for Measuring the Spatial Coordinates of Structural Elements of the Frame of a Low-Floor Tram”, Science of SUSU. Materials of the 67th Scientific Conference. Section of Economics, Management and Law, Publishing of the South Ural StateUniversity, Chelyabinsk, 2015, 458–463

[7] S. A. Tushev, B. M. Sukhovilov, “Some Ways to Improve the Performance of Automatic Calibration of Digital Cameras”, Young Researcher: Materials of the 2nd Scientific Exhibition-Conference of Scientific, Technical and Creative Works of Students, Publishing of the South Ural State University, Chelyabinsk, 2015, 434–439

[8] W. Hartmann, M. Havlena, K. Schindler, “Recent developments in large-scale tie-point matching”, ISPRS Journal of Photogrammetry and Remote Sensing. International Society for Photogrammetry and Remote Sensing, 115 (2016), 47–62 | DOI

[9] F. Remondino, “State of the art in high density image matching”, The Photogrammetric Record, 29:146 (2014), 144–166 | DOI

[10] S. Leutenegger, M. Chli, R. Y. Siegwart, BRISK : Binary Robust Invariant Scalable Keypoints | DOI

[11] R. Ortiz, A. Alahi, P. Vandergheynst, “FREAK: Fast retina keypoint”, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2012., 510–517 | DOI

[12] C. S. Fraser, S. Cronk, “A hybrid measurement approach for close-range photogrammetry.”, ISPRS Journal of Photogrammetry and Remote Sensing. Elsevier B.V, 64:3 (2009), 328–333

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

[14] 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, 37 (2008), 111–114

[15] 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

[16] 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

[17] Z. Zhang, “A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry”, Artificial Intelligence, 78:1–2 (1995), 87–119 | DOI

[18] J. T. Arnfred, S. Winkler, “A general framework for image feature matching without geometric constraints”, Pattern Recognition Letters. Elsevier B.V, 73 (2016), 26–32 | DOI

[19] R. Y. Takimoto, “Epipolar geometry estimation, metric reconstruction and error analysis from two images”, IFAC Proceedings Volumes (IFAC PapersOnline), 14:1 (2012), 1739–1744 | DOI

[20] C. Fraser, “Advances in Close-Range Photogrammetry”, Photogrammetric Week 2015, 2015, 257–268

[21] V-STARS - Geodetic Systems, Inc } {\tt https://www.geodetic.com/

[22] Agisoft PhotoScan } {\tt http://www.agisoft.com

[23] H. G. Maas, “Automatic DEM generation by multi-image feature based matching”, International Archives of Photogrammetry and Remote Sensing, 31 (1996), 484–489

[24] B. Bhowmick, “Divide and conquer: A hierarchical approach to large-scale structurefrom-motion”, Computer Vision and Image Understanding. Elsevier Inc, 157 (2017), 190–205 | DOI

[25] D. Forsyth, J. Ponce, Computer Vision: A Modern Approach., Pearson, 2011

[26] 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 Object”, Procedings of the 2nd International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM), Publishing of the South Ural State University, Chelyabinsk, 2016, 363–366

[27] I. Bomze, M. Budinich, P. Pardalos, M. Pelillo, “The Maximum Clique Problem”, Handbook of Combinatorial Optimization, 1999, 1–74

[28] B. Triggs, P. McLauchlan, R. Hartley, A. Fitzgibbon, “Bundle Adjustment - A Modern Synthesis”, Vision Algorithms: Theory Practice, 1883 (2000), 298–372 | DOI

[29] 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), Publishing of the South Ural StateUniversity, Chelyabinsk, 2016, 464–468 | DOI

[30] OpenCV (Open Source Computer Vision Library) } {\tt http://opencv.org

[31] Eigen: C++ template library for linear algebra } {\tt http://eigen.tuxfamily.org

[32] J. Konc, D. Janezic, “An improved branch and bound algorithm for the maximum clique problem”, MATCH Communications in Mathematical and in Computer Chemistry, 2007, 569–590

[33] J. Konc, D. Janezic, New C++ source code of the MaxCliqueDyn algorithm } {\tt http://insilab.org/

[34] E. Tomita, A. Tanaka, H. Takahashi, “The worst-case time complexity for generating all maximal cliques and computational experiments”, Theoretical Computer Science, 363:1 (2006), 28–42 | DOI

[35] A. Conte, Review of the Bron-Kerbosch algorithm and variations } {\tt http://www.dcs.gla.ac.uk/

[36] C. Bron, J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph”, Communications of the ACM, 16:9 (Sep 1973), 575–577 | DOI

[37] K. Ozaki, smly:find cliques - a pivoting version of Bron-Kerbosch algorithm } {\tt https://gist.github.com/smly/

[38] Boost C++ libraries } {\tt http://www.boost.org