Parallel Algorithms for Effective Correspondence Problem Solution in Computer Vision

Semen A. Tushev, Boris M. Sukhovilov


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.

Ключевые слова

computer vision; photogrammetry; correspondence problem, parallel algorithms; maximum clique problem; epipolar geometry

Полный текст:

PDF (English)


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

Baggio D. et al. Mastering OpenCV with Practical Computer Vision Projects. Packt Publishing, 2012.

Bay H., Tuytelaars T., van Gool L. SURF: Speeded Up Robust Features. Computer Vision and Image Understanding. 2008. vol. 110, no. 3, pp. 346–359. DOI: 10.1016/j.cviu.2007.09.014

Lowe D.G. Object Recognition from Local Scale-Invariant Features. Proceedings of the Seventh IEEE International Conference on Computer Vision. 1999. vol. 2, pp. 1150–1157. DOI: 10.1109/ICCV.1999.790410

Fraser C.S. Innovations in Automation for Vision Metrology Systems. Photogrammetric Record. 1997. vol. 15, no. 90, pp. 901–911.

Sukhovilov B. M., Grigorova E. A., Development of a Photogrammetric System for Measuring the Spatial Coordinates of Structural Elements of the Frame of a Low-Floor Tram. Nauka JuUrGU. Materialy 67-j Nauchnoj Konferencii. Sekcii Jekonomiki, Upravlenija i Prava. [Science of SUSU. Materials of the 67th Scientific Conference. Section of Economics, Management and Law]. Chelyabinsk, Publishing of the South Ural State University, 2015, pp. 458–463. (in Russian)

Tushev S.A., Sukhovilov B.M.. Some Ways to Improve the Performance of Automatic Calibration of Digital Cameras. Molodoj Issledovatel: Materialy 2-J Nauchnoj Vystavki-Konferentsii Nauchno-Tekhnicheskikh i Tvorcheckikh Rabot Studentov. [Young Researcher: Materials of the 2nd Scientific Exhibition-Conference of Scientific, Technical and Creative Works of Students]. Chelyabinsk, Publishing of the South Ural State University, 2015, pp. 434–439. (in Russian)

Hartmann W., Havlena M., Schindler K. Recent Developments in Large-Scale Tie-Point Matching. ISPRS Journal of Photogrammetry and Remote Sensing. 2016. vol. 115, pp. 47–62. DOI: 10.1016/j.isprsjprs.2015.09.005

Remondino F., Spera M. G., Nocerino E., Menna F., Nex F. State of the Art in High Density Image Matching. The Photogrammetric Record. 2014. vol. 29(146), pp. 144–166. DOI: 10.1111/phor.12063

Leutenegger S., Chli M., Siegwart R. BRISK: Binary Robust invariant scalable keypoints. Proceedings of the 2011 International Conference on Computer Vision (ICCV '11). IEEE Computer Society, Washington, DC, USA, 2011. pp. 2548–2555. DOI: 10.1109/ICCV.2011.6126542

Ortiz R. FREAK: Fast Retina Keypoint. Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (CVPR '12). IEEE Computer Society, Washington, DC, USA, 2012. pp. 510–517. DOI: 10.1109/CVPR.2012.6247715

Fraser C. S., Cronk S. A Hybrid Measurement Approach for Close-Range Photo-grammetry. ISPRS Journal of Photogrammetry and Remote Sensing. 2009, vol. 64(3), pp. 328–333. DOI: 10.1016/j.isprsjprs.2008.09.009

Leung C., Lovell B. C. 3D Reconstruction through Segmentation of Multi-View Image Sequences. Proceedings of the 2003 APRS Workshop on Digital Image Computing. 2003. pp. 87–92. Available at: (accessed: 29.11.2016)

Qiqiang F., Guangyun L. Matching of Artificial Target Points Based on Space Inter-section. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Beijing 2008, vol. XXXVII, part B5, pp. 111–114.

Maas, H.-G. Complexity analysis for the establishment of image correspondences of dense spatial target fields. International Archives of Photogrammetry and Remote Sensing. 1992. vol. 29, pp. 102–107.

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

Zhang Z., Deriche R., Faugeras O., Luong Q. T. A Robust Technique for Matching Two Uncalibrated Images through the Recovery of the Unknown Epipolar Geometry. Artificial Intelligence. 1995. vol. 78(1–2), pp. 87–119. DOI: 10.1016/0004-3702(95)00022-4

Arnfred J. T., Winkler S. A General Framework for Image Feature Matching Without Geometric Constraints. Pattern Recognition Letters. 2016. vol. 73, pp. 26–32. DOI: 10.1016/j.patrec.2015.12.017

Takimoto R.Y., De Castro Martins T., Takase F.K., De Sales Guerra Tsuzuki M. Epipolar Geometry Estimation, Metric Reconstruction and Error Analysis from Two Images. IFAC Proceedings. 2012. vol. 2012;14, pp. 1739–1744. DOI: 10.3182/20120523-3-RO-2023.00098

Fraser C. Advances in Close-Range Photogrammetry. Photogrammetric Week 2015. 2015. pp. 257–268.

V-STARS – Geodetic Systems, Inc. Available at: (accessed: 29.01.2017).

Agisoft PhotoScan. Available at: (accessed: 29.01.2017).

Maas H.-G. Automatic DEM Generation by Multi-Image Feature Based Matching. International Archives of Photogrammetry and Remote Sensing. 1996. vol. 31, pp. 484–489.

Bhowmick B., Patra S., Chatterjee A., Madhav Govindu V., Banerjee S. Divide and Conquer: A Hierarchical Approach to Large-Scale Structure-from-Motion. Computer Vision and Image Understanding. 2017. vol. 157, pp. 190–205. DOI: 10.1016/j.cviu.2017.02.006

Forsyth D., Ponce J. Computer Vision: A Modern Approach. 2nd ed. Pearson, 2011.

Sukhovilov B.M., Sartasov E.M., Grigorova E. A. 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), Chelyabinsk, Russia, 2016. IEEE Xplore Digital Library. pp. 1–4. DOI: 10.1109/ICIEAM.2016.7911682

Bomze I., Budinich M., Pardalos P., Pelillo M. The Maximum Clique Problem. Handbook of Combinatorial Optimization, 1999. pp. 1–74.

Triggs B., McLauchlan P., Hartley R., Fitzgibbon A.. Bundle Adjustment — A Modern Synthesis. Vision Algorithms: Theory & Practice. 2000. Vol 1883. pp. 298–372. DOI: 10.1007/3-540-44480-7_21

Tushev S.A., Sukhovilov B.M.. 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. pp. 1–5. DOI: 10.1109/ICIEAM.2016.7911628

OpenCV (Open Source Computer Vision Library): Available at: (accessed: 29.11.2016).

Eigen: C++ Template Library For Linear Algebra: Available at: (accessed: 29.11.2016).

Konc J., Janežič D. An Improved Branch and Bound Algorithm for the Maximum Clique Problem. MATCH Communications in Mathematical and in Computer Chemistry. 2007. vol. 58, pp. 569–590

Konc J., Janezic D. New C++ Source Code of the MaxCliqueDyn Algorithm: Available at: (accessed: 29.11.2016).

Tomita E., Tanaka A., Takahashi H. The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments. Theoretical Computer Science. 2006. vol. 363, no. 1, pp. 28–42. DOI: 10.1016/j.tcs.2006.06.015

Conte A. Review of the Bron-Kerbosch Algorithm and Variations. Available at: (accessed: 29.11.2016)

Bron C., Kerbosch J. Algorithm 457: Finding All Cliques of an Undirected Graph. Communications of the ACM, 1973. vol. 16, no. 9, pp. 575–577. DOI: 10.1145/362342.362367

Ozaki K. smly:find_cliques – a Pivoting Version of Bron-Kerbosch Algorithm. Available at: (accessed: 29.11.2016)

Boost C++ libraries.: Available at: (accessed: 29.11.2016).