nach oben

International Journal of Computer Vision

Erschienen in:

22.09.2018

Locality Preserving Matching

verfasst von: Jiayi Ma, Ji Zhao, Junjun Jiang, Huabing Zhou, Xiaojie Guo

Erschienen in: International Journal of Computer Vision | Ausgabe 5/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Seeking reliable correspondences between two feature sets is a fundamental and important task in computer vision. This paper attempts to remove mismatches from given putative image feature correspondences. To achieve the goal, an efficient approach, termed as locality preserving matching (LPM), is designed, the principle of which is to maintain the local neighborhood structures of those potential true matches. We formulate the problem into a mathematical model, and derive a closed-form solution with linearithmic time and linear space complexities. Our method can accomplish the mismatch removal from thousands of putative correspondences in only a few milliseconds. To demonstrate the generality of our strategy for handling image matching problems, extensive experiments on various real image pairs for general feature matching, as well as for point set registration, visual homing and near-duplicate image retrieval are conducted. Compared with other state-of-the-art alternatives, our LPM achieves better or favorably competitive performance in accuracy while intensively cutting time cost by more than two orders of magnitude.

Vorheriger Artikel Kernel Cuts: Kernel and Spectral Clustering Meet Regularization

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

https://sites.google.com/site/jiayima2013/home.

The distribution of initial inlier percentages on the test data can be seen from the precision curve at \(\lambda =1\) in Fig. 2 as in this case all putative matches are considered as inliers.

For real-world tasks such as multiple view stereo and SLAM, a better metric would be to use the inliers to retrieve the camera pose from stereo images and evaluate their accuracy (Bian et al. 2017). However, such camera pose estimation usually relies on an additional robust estimator such as RANSAC, which may not directly characterize the matching performance. Therefore, for the purpose of general feature matching, we only use precision and recall to characterize the performance.

http://www.ti.uni-bielefeld.de/html/research/avardy/index.html.

As different feature extraction used in this paper, the performance of HiSS (Churchill and Vardy 2013) and SSVS (Liu et al. 2013) is not exactly the same as reported in the original papers. In addition, the reimplemented SSVS method in this paper does not contain the mismatch removal introduced in (Liu et al. 2013).

Aanæs, H., Jensen, R. R., Vogiatzis, G., Tola, E., & Dahl, A. B. (2016). Large-scale data for multiple-view stereopsis. International Journal of Computer Vision, 120(2), 153–168.MathSciNetCrossRef

Adamczewski, K., Suh, Y., Mu Lee, K.: Discrete tabu search for graph matching. In: Proceedings of the 10th European conference on computer vision, pp. 109–117 (2015)

Bai, X., Yang, X., Latecki, L. J., Liu, W., & Tu, Z. (2010). Learning context-sensitive shape similarity by graph transduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(5), 861–874.CrossRef

Belongie, S., Malik, J., & Puzicha, J. (2002). Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(24), 509–522.CrossRef

Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509–517.MATHMathSciNetCrossRef

Besl, P. J., & McKay, N. D. (1992). A method for registration of 3-d shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2), 239–256.CrossRef

Bian, J., Lin, W. Y., Matsushita, Y., Yeung, S. K., Nguyen, T. D., Cheng, M. M.: GMS: Grid-based motion statistics for fast, ultra-robust feature correspondence. In: Proceedings of the 10th European conference on computer vision pattern Recognition, pp. 2828–2837 (2017)

Boughorbel, F., Koschan, A., Abidi, B., & Abidi, M. (2004). Gaussian fields: A new criterion for 3d rigid registration. Pattern Recognition, 37(7), 1567–1571.CrossRef

Chen, J., Wang, Y., Luo, L., Yu, J. G., & Ma, J. (2016). Image retrieval based on image-to-class similarity. Pattern Recognition Letters, 83, 379–387.CrossRef

Cho, M., Lee, K. M.: Mode-seeking on graphs via random walks. In: Proceedings of the European conference on computer vision pattern recognition, pp. 606–613 (2012)

Cho, M., Lee, K. M.: Progressive graph matching: Making a move of graphs via probabilistic voting. In: Proceedings of the European conference on computer vision pattern recognition, pp. 398–405 (2012)

Chui, H., & Rangarajan, A. (2003). A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding, 89, 114–141.MATHCrossRef

Chum, O., Matas, J.: Matching with PROSAC - progressive sample consensus. In: Proceedings of the European conference on computer vision pattern recognition, pp. 220–226 (2005)

Churchill, D., & Vardy, A. (2013). An orientation invariant visual homing algorithm. Journal of Intelligent and Robotic Systems, 71(1), 3–29.

Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus: A paradigm for model fitting with application to image analysis and automated cartography. Communications of the ACM, 24(6), 381–395.MathSciNetCrossRef

Gao, Y., Ma, J., & Yuille, A. L. (2017). Semi-supervised sparse representation based classification for face recognition with insufficient labeled samples. IEEE Transactions on Image Processing, 26(5), 2545–2560.MathSciNetMATHCrossRef

Guo, X., & Cao, X. (2012). Good match exploration using triangle constraint. Pattern Recognition Letters, 33(7), 872–881.CrossRef

Horaud, R., Forbes, F., Yguel, M., Dewaele, G., & Zhang, J. (2011). Rigid and articulated point registration with expectation conditional maximization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(3), 587–602.CrossRef

Hu, Y. T., Lin, Y. Y., Chen, H. Y., Hsu, K. J., & Chen, B. Y. (2015). Matching images with multiple descriptors: An unsupervised approach for locally adaptive descriptor selection. IEEE Transactions on Image Processing, 24(12), 5995–6010.MathSciNetMATHCrossRef

Huber, P. J. (1981). Robust statistics. New York: John Wiley & Sons.MATHCrossRef

Jian, B., & Vemuri, B. C. (2011). Robust point set registration using gaussian mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(8), 1633–1645.CrossRef

Jiang, J., Chen, C., Ma, J., Wang, Z., Wang, Z., & Hu, R. (2017). Srlsp: A face image super-resolution algorithm using smooth regression with local structure prior. IEEE Transactions on Multimedia, 19(1), 27–40.CrossRef

Jinda-Apiraksa, A., Vonikakis, V., Winkler, S.: California-ND: An annotated dataset for near-duplicate detection in personal photo collections. In: QoMEX, pp. 142–147 (2013)

Kim, V. G., Lipman, Y., & Funkhouser, T. (2011). Blended intrinsic maps. ACM Transactions on Graphics, 30(4), 79.CrossRef

Leordeanu, M., Hebert, M.: A spectral technique for correspondence problems using pairwise constraints. In: Proceedings IEEE international conference on computer vision, pp. 1482–1489 (2005)

Li, X., & Hu, Z. (2010). Rejecting mismatches by correspondence function. International Journal of Computer Vision, 89(1), 1–17.CrossRef

Lin, W. Y., Cheng, M. M., Lu, J., Yang, H., Do, M. N., Torr, P.: Bilateral functions for global motion modeling. In: Proceedings IEEE International Conference on Computer Vision, pp. 341–356 (2014)

Lin, W. Y., Cheng, M. M., Zheng, S., Lu, J., Crook, N.: Robust non-parametric data fitting for correspondence modeling. In: Proceedings IEEE International Conference on Computer Vision, pp. 2376–2383 (2013)

Lin, W. Y., Wang, F., Cheng, M. M., Yeung, S. K., Torr, P. H., Do, M. N., et al. (2018). CODE: Coherence based decision boundaries for feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(1), 34–47.CrossRef

Lipman, Y., Yagev, S., Poranne, R., Jacobs, D. W., & Basri, R. (2014). Feature matching with bounded distortion. ACM Transactions on Graphics, 33(3), 26.MATHCrossRef

Liu, H., Yan, S.: Common visual pattern discovery via spatially coherent correspondence. In: IEEE conference on computer vision and pattern recognition, pp. 1609–1616 (2010)

Liu, M., Pradalier, C., & Siegwart, R. (2013). Visual homing from scale with an uncalibrated omnidirectional camera. IEEE Transactions on Robotics, 29(6), 1353–1365.CrossRef

Liu, Y., Dominicis, L., Wei, B., Chen, L., & Martin, R. (2015). Regularization based iterative point match weighting for accurate rigid transformation estimation. IEEE Transactions on Visualization and Computer Graphics, 21(9), 1058–1071.CrossRef

Lowe, D. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2), 91–110.CrossRef

Ma, J., Jiang, J., Liu, C., & Li, Y. (2017). Feature guided gaussian mixture model with semi-supervised em and local geometric constraint for retinal image registration. Information Sciences, 417, 128–142.MathSciNetCrossRef

Ma, J., Jiang, J., Zhou, H., Zhao, J., & Guo, X. (2018). Guided locality preserving feature matching for remote sensing image registration. IEEE Transactions on Geoscience and Remote Sensing, 56(8), 4435–4447.CrossRef

Ma, J., Zhao, J., Guo, H., Jiang, J., Zhou, H., Gao, Y.: Locality preserving matching. In: Proceedings of the international joint conference on artificial intelligence, pp. 4492–4498 (2017)

Ma, J., Zhao, J., Jiang, J., Zhou, H.: Non-rigid point set registration with robust transformation estimation under manifold regularization. In: Proceedings of AAAI conference artificial intelligence, pp. 4218–4224 (2017)

Ma, J., Zhao, J., Jiang, J., Zhou, H., Zhou, Y., Wang, Z., Guo, X.: Visual homing via guided locality preserving matching. In: Proceedings of IEEE international conference on robotics and automation, pp. 7254–7261 (2018)

Ma, J., Zhao, J., Ma, Y., & Tian, J. (2015). Non-rigid visible and infrared face registration via regularized gaussian fields criterion. Pattern Recognition, 48(3), 772–784.CrossRef

Ma, J., Zhao, J., Tian, J., Tu, Z., Yuille, A.: Robust estimation of nonrigid transformation for point set registration. In: Proceedings of IEEE conference computer vision pattern recognition, pp. 2147–2154 (2013)

Ma, J., Zhao, J., Tian, J., Yuille, A. L., & Tu, Z. (2014). Robust point matching via vector field consensus. IEEE Transactions on Image Processing, 23(4), 1706–1721.MathSciNetMATHCrossRef

Ma, J., Zhao, J., & Yuille, A. L. (2016). Non-rigid point set registration by preserving global and local structures. IEEE Transactions on Image Processing, 25(1), 53–64.MathSciNetMATHCrossRef

Ma, J., Zhou, H., Zhao, J., Gao, Y., Jiang, J., & Tian, J. (2015). Robust feature matching for remote sensing image registration via locally linear transforming. IEEE Transactions on Geoscience and Remote Sensing, 53(12), 6469–6481.CrossRef

Maier, J., Humenberger, M., Murschitz, M., Zendel, O., Vincze, M.: Guided matching based on statistical optical flow for fast and robust correspondence analysis. In: Proceedings of European conference on computer vision, pp. 101–117 (2016)

Micchelli, C. A., & Pontil, M. (2005). On learning vector-valued functions. Neural Computation, 17(1), 177–204.MathSciNetMATHCrossRef

Mikolajczyk, K., Tuytelaars, T., Schmid, C., Zisserman, A., Matas, J., Schaffalitzky, F., et al. (2005). A comparison of affine region detectors. International Journal of Computer Vision, 65(1), 43–72.CrossRef

Möller, R., & Vardy, A. (2006). Local visual homing by matched-filter descent in image distances. Biological Cybernetics, 95(5), 413–430.MathSciNetMATHCrossRef

Myronenko, A., & Song, X. (2010). Point set registration: Coherent point drift. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(12), 2262–2275.CrossRef

Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial optimization: Algorithms and complexity. North Chelmsford: Courier Corporation.MATH

Pele, O., Werman, M.: A linear time histogram metric for improved SIFT matching. In: Proceedings of European conference on computer vision, pp. 495–508 (2008)

Rusu, R. B., Blodow, N., Beetz, M.: Fast point feature histograms (FPFH) for 3d registration. In: Proc. IEEE International conference on robotics and automation, pp. 3212–3217 (2009)

Schroeter, D., & Newman, P. (2008). On the robustness of visual homing under landmark uncertainty. Intelligent Autonomous Systems, 10, 278–287.

Tola, E., Lepetit, V., & Fua, P. (2010). DAISY: An efficient dense descriptor applied to wide-baseline stereo. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(5), 815–830.CrossRef

Torr, P. H. S., & Zisserman, A. (2000). MLESAC: A new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding, 78(1), 138–156.CrossRef

Torresani, L., Kolmogorov, V., Rother, C.: Feature correspondence via graph matching: Models and global optimization. In: Proceedings of the European conference on computer vision, pp. 596–609 (2008)

Vedaldi, A., Fulkerson, B.: VLFeat - An open and portable library of computer vision algorithms. In: Proceedings of the ACM international conference on multimedia, pp. 1469–1472 (2010)

Wang, C., Wang, L., Liu, L.: Progressive mode-seeking on graphs for sparse feature matching. In: Proceedings of the 10th European conference on computer vision, pp. 788–802 (2014)

Wang, G., Wang, Z., Chen, Y., Liu, X., Ren, Y., & Peng, L. (2016). Learning coherent vector fields for robust point matching under manifold regularization. Neurocomputing, 216, 393–401.CrossRef

Wang, G., Wang, Z., Chen, Y., Zhou, Q., Zhao, W.: Context-aware gaussian fields for non-rigid point set registration. In: Proceedings of the IEEE conference on computer vision pattern recognition, pp. 5811–5819 (2016)

Wang, G., Wang, Z., Chen, Y., Zhou, Q., & Zhao, W. (2016). Removing mismatches for retinal image registration via multi-attribute-driven regularized mixture model. Information Sciences, 372, 492–504.CrossRef

Yang, K., Pan, A., Yang, Y., Zhang, S., Ong, S. H., & Tang, H. (2017). Remote sensing image registration using multiple image features. Remote Sensing, 9(6), 581.CrossRef

Yang, Y., Ong, S. H., & Foong, K. W. C. (2015). A robust global and local mixture distance based non-rigid point set registration. Pattern Recognition, 48(1), 156–173.CrossRef

Zhao, J., Ma, J.: Visual homing by robust interpolation for sparse motion flow. In: Proc. IEEE/RSJ International conference on intelligent robots and systems, pp. 1282–1288 (2017)

Zheng, Y., & Doermann, D. (2006). Robust point matching for nonrigid shapes by preserving local neighborhood structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(4), 643–649.CrossRef

Titel: Locality Preserving Matching
verfasst von: Jiayi Ma
Ji Zhao
Junjun Jiang
Huabing Zhou
Xiaojie Guo
Publikationsdatum: 22.09.2018
Verlag: Springer US
Erschienen in: International Journal of Computer Vision / Ausgabe 5/2019
Print ISSN: 0920-5691
Elektronische ISSN: 1573-1405
DOI: https://doi.org/10.1007/s11263-018-1117-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 5/2019

Deep Appearance Models: A Deep Boltzmann Machine Approach for Face Modeling

Robust and Optimal Registration of Image Sets and Structured Scenes via Sum-of-Squares Polynomials

Kernel Cuts: Kernel and Spectral Clustering Meet Regularization

Understanding Image Representations by Measuring Their Equivariance and Equivalence