Алгоритм полиномиальной сложности для поиска соответствующих точек на основе эпиполярной геометрии
Аннотация
Задача установления соответствий между изображениями точек на различных снимках является основой многих базовых алгоритмов компьютерного зрения. Существуют несколько подходов к решению данной задачи: на основе дескрипторов, на основе эпиполярной геометрии и комбинированные методы. В настоящей статье рассматриваются методы поиска соответствующих точек, основанные на эпиполярной геометрии, применительно к разрабатываемой авторами фотограмметрической измерительной системе (ФИС), использующей искусственные световозвращающие однотипные круговые маркеры (мишени) в роли контрольных точек. В качестве математической модели для задачи нахождения соответствий авторами предлагается использовать взвешенный многодольный неориентированный граф, множество вершин в котором соответствует множеству изображений искусственных маркеров (мишеней) на снимках, а множество ребер определяет множество изображений, взаимно удовлетворяющих эпиполярным ограничениям. Представлено теоретически точное решение задачи на основе суперклики. Выполнена оценка временной сложности решения задачи через суперклику; показано, что данный подход является экспоненциально сложным. Рассмотрены варианты применения различных эвристических алгоритмов установления соответствий между точками. Подобные алгоритмы не всегда приводят к точному результату, однако способны сформировать приближенное решение за практически приемлемое время. Благодаря особой архитектуре разработанной авторами ФИС, становится возможным использование быстрых приближенных алгоритмов; возможные неточности будут автоматически нейтрализованы на дальнейших этапах работы ФИС. Подобный подход позволяет восстанавливать точную трехмерную структуру измеряемой сцены за приемлемое время. Авторами предложен новый полиномиальный параллельный алгоритм поиска соответствующих точек. Оценена временная сложность разработанного алгоритма (полином 4-й степени). Выполнена сравнительная оценка производительности и эффективности нового алгоритма, в качестве алгоритмов сравнения выступают более ранние алгоритмы авторов, а также алгоритм H.-G. Maas. Новый алгоритм превосходит по производительности все конкурирующие алгоритмы.
Ключевые слова
Полный текст:
PDFЛитература
Hartley R., Zisserman A. Multiple View Geometry in Computer Vision, 2nd ed. Cambridge University Press, 2004.
Tushev S.A., Sukhovilov B.M., Sartasov E.M. 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. pp. 435–442. DOI: 10.1109/URALCON.2017.8120748.
Tushev S.A., Sukhovilov B.M. Efficiency Analysis of Photogrammetric System by Simulation Modelling. Bulletin of the South Ural State University. Ser. Mathematical Modelling, Programming & Computer Software (Bulletin SUSU MMCS), 2018, vol. 11, no. 1, pp. 109–123. (in Russian) DOI: 10.14529/mmp180110.
Tushev S.A., Sukhovilov B.M. Parallel Algorithms for Effective Correspondence Problem Solution in Computer Vision. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2017. vol. 6, no 2. pp. 49–68. DOI: 10.14529/cmse170204.
Lowe D.G. Distinctive Image Features from Scale Invariant Keypoints. International Journal of Computer Vision. 2004. vol. 60. pp. 91–110. DOI: 10.1023/B:VISI.0000029664.99615.94.
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.
Harris C., Stephens M. A Combined Corner and Edge Detector. Proceedings of the 4th Alvey Vision Conference, 1988. pp. 147–151. DOI: 10.5244/C.2.23.
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.
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 Objects. 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.
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, no. 5. pp. 65–70.
Maas, H.-G., Gruen A. Digital Photogrammetric Techniques for High-Resolution Three-Dimensional Flow Velocity Measurements. Optical Engineering. 1995. vol. 34, no. 7. pp. 1970–1976.
Zhu Z. et al. Automatic Three-Dimensional Measurement of Large-Scale Structure Based on Vision Metrology. Scientific World Journal. Hindawi Publishing Corporation, 2014. vol. 2014. DOI: 10.1155/2014/185269.
Yurin D.V. A Modern Review of the Structure of Automatic Systems for 3D Recon-struction from Images. Mezhdunarodnaya Nauchnaya konferenciya, posvyashchennaya 80-letiyu so dnya rozhdeniya akademika V.A. Mel'nikova [Proceedings of International Scientific Conference Dedicated to the 80th Anniversary of Academician V.A. Melnikov]. Nekommercheskaya Organizaciya Nauchnyj Fond “Pervaya Issledovatel'skaya Laboratoriya im. akademika V. A. Mel'nikova”. 2009. pp. 118–121. (in Russian)
Zhang Z. et al. A Robust Technique for Matching Two Uncalibrated Images through the Recovery of the Unknown Epipolar Geometry. Artificial Intelligence. 1995. vol. 78, no. 1–2. pp. 87–119. DOI: 10.1016/0004-3702(95)00022-4.
Kolmogorov V., Zabih R. Computing Visual Correspondence with Occlusions Using Graph Cuts. Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001. vol. 2. pp. 508–515. DOI: 10.1109/ICCV.2001.937668.
Tuzhilkin A.Yu., Zaharov A.A., Zhiznyakov A.L. Finding Matches on Images Using Eigendecomposition of Graphs for 3D Reconstruction Tasks. Polzunovskij vestnik. [Polzunov Bulletin]. 2015. vol. 2, no. 4. pp. 37–39. (in Russian)
Clarke T.A. et al. Automated Three Dimensional Measurement Using Multiple CCD Camera Views. The Photogrammetric Record. 1995. vol. 15, no. 85. pp. 27–42.
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.
Qiqiang F., Guangyun L. Matching of Artificial Target Points Based on Space Intersection. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. 2008. vol. XXXVII. pp. 111–114.
Fraser C.S., Cronk S. A Hybrid Measurement Approach for Close-Range Photogrammetry. ISPRS Journal of Photogrammetry and Remote Sensing. Elsevier B.V., 2009. vol. 64, no. 3. pp. 328–333. DOI: 10.1016/j.isprsjprs.2008.09.009.
Triggs B. et al. Bundle Adjustment – A Modern Synthesis. Vision Algorithms: Theory and Practice. 2000. vol. 1883. pp. 298–372. DOI: 10.1007/3-540-44480-7_21.
Züge A.P., Carmo R. On Comparing Algorithms for the Maximum Clique Problem. Discrete Applied Mathematics. Elsevier B.V., 2018. no. 2. pp. 1–13. DOI: 10.1016/j.dam.2018.01.005.
Moon J.W., Moser L. On Cliques in Graphs. Israel Journal of Mathematics. 1965. vol. 3, no. 1. pp. 23–28. DOI: 10.1007/BF02760024.
Robson J.M. Finding a Maximum Independent Set in Time O(2^(n/4)). Technical Report of the Universite de Bordeaux I. Available at: https://www.labri.fr/perso/robson/mis/ techrep.html (accessed: 23.06.2018).
Concurrency Runtime. Available at: https://msdn.microsoft.com/en-us/library/dd504870.aspx (accessed: 23.06.2018).
DOI: http://dx.doi.org/10.14529/cmse180406