nach oben

International Journal of Computer Vision

Erschienen in:

01.06.2019

Efficient Feature Matching via Nonnegative Orthogonal Relaxation

verfasst von: Bo Jiang, Jin Tang, Bin Luo

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Feature matching problem that incorporates pair-wise constraints can be formulated as an Integer Quadratic Programming (IQP) problem with one-to-one matching constraint. Since it is NP-hard, relaxation models are required. One main challenge for optimizing IQP matching is how to incorporate the discrete one-to-one matching constraint in IQP matching optimization. In this paper, we present a new feature matching relaxation model, called Nonnegative Orthogonal Relaxation (NOR), that aims to optimize IQP matching problem in nonnegative orthogonal domain. One important benefit of the proposed NOR model is that it can naturally incorporate the discrete one-to-one matching constraint in its optimization and can return a desired sparse (approximate discrete) solution for the problem. An efficient and effective update algorithm has been developed to solve the proposed NOR model. Promising experimental results on several benchmark datasets demonstrate the effectiveness and efficiency of the proposed NOR method.

Vorheriger Artikel Click Carving: Interactive Object Segmentation in Images and Videos with Point Clicks

Nächster Artikel Repetition Estimation

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

This is because if \(\mathbf u {} \mathbf v ^{{{\,\mathrm{T}\,}}} = \sum ^n_{i=1} \mathbf u _i\mathbf v _i =0\), then \(\mathbf u _i\mathbf v _i =0\), which implies that for any index i, if \(\mathbf u _i \ne 0\), then \(\mathbf v _i\) must be zero. Thus if \(\Vert \mathbf u \Vert _0 = k\), then there are at least k elements in vector \(\mathbf v \) equal to zero.

Since the nonnegativity of the update is always guaranteed, the nonnegative constraint can be dropped in Lagrangian function.

http://www.pascalnetwork.org/challenges/VOC/voc2007/workshop/index.html.

http://www.ee.cuhk.edu.hk/xgwang/CUHK-identification.html.

Adamczewski, K., Suh, Y., & Lee, K. M. (2015). Discrete tabu search for graph matching. In IEEE international conference on computer vision (pp. 109–117).

Albarelli, A., Rodolà, E., & Torsello, A. (2012). Imposing semi-local geometric constraints for accurate correspondences selection in structure from motion: A game-theoretic perspective. International Journal of Computer Vision, 97(1), 36–53.CrossRef

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

Caelli, T., & Kosinov, S. (2004). An eigenspace projection clustering method for inexact graph matching. IEEE Transactions on PAMI, 26(4), 515–519.CrossRef

Caetano, T. S., McAuley, J. J., Cheng, L., Le, Q. V., & Smola, A. J. (2009). Learning graph matching. IEEE Transactions on PAMI, 31(6), 1048–1058.CrossRef

Cho, M., Lee, J., & Lee, K. M. (2010). Reweighted random walks for graph matching. In European conference on computer vision (pp. 492–505).

Collins, T., Mesejo, P., & Bartoli, A. (2014). An analysis of errors in graph-based keypoint matching and proposed solutions. In European conference on computer vision (pp. 138–153).

Cour, T., Srinivasan, P., & Shi, J. (2006). Balanced graph matching. In Neural information processing systems (pp. 313–320).

Ding, C., Li, T., Peng, W., & Park, H. (2006). Orthogonal nonnegative matrix t-factorizations for clustering. In ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 126–135).

Egozi, A., Keller, Y., & Guterman, H. (2013). A probabilistic approach to spectral graph matching. IEEE Transactions on PAMI, 35(1), 18–27.CrossRef

Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1–2), 95–110.MathSciNetCrossRef

Gold, S., & Rangarajan, A. (1996). A graduated assignment algorithm for graph matching. IEEE Transactions on PAMI, 18(4), 377–388.CrossRef

Hamid, R., Decoste, D., & Lin, C. J. (2013). Dense non-rigid point-matching using random projections. In IEEE conference on computer vision and pattern recognition (pp. 2914–2921).

Jiang, B., Tang, J., Ding, C. H., & Luo, B. (2017). Nonnegative orthogonal graph matching. In AAAI (pp. 4089–4095).

Leordeanu, M., & Hebert, M. (2005). A spectral technique for correspondence problem using pairwise constraints. In International conference on computer vision pp. 1482–1489

Leordeanu, M., Hebert, M., & Sukthankar, R. (2009). An integer projected fixed point method for graph macthing and map inference. In Neural information processing systems (pp. 1114–1122).

Leordeanu, M., Sukthankar, R., & Hebert, M. (2012). Unsupervised learning for graph matching. International Journal of Computer Vision, 96(1), 28–45.MathSciNetCrossRefMATH

Lin, L., Zeng, K., Liu, X., & Zhu, S. C. (2009). Layered graph matching by composite cluster sampling with collaborative and competitive interactions. In IEEE conference on CVPR (pp. 1351–1358).

Lin, W., Shen, Y., Yan, J., Xu, M., Wu, J., Wang, J., et al. (2017). Learning correspondence structures for person re-identification. IEEE Transactions on Image Processing, 26(5), 2438–2453.MathSciNetCrossRefMATH

Ling, H., & Jacobs, D. W. (2007). Shape classification using inner-distance. IEEE Transactions on PAMI, 29(2), 286–299.CrossRef

Liu, C. L., Yin, F., Wang, D. H., & Wang, Q. F. (2011). Casia online and offline Chinese handwriting databases. In International conference on document analysis and recognition (pp. 37–41).

Liu, Z. Y., & Qiao, H. (2014). GNCCP-graduated nonconvexityand concavity procedure. IEEE Transactions on PAMI, 36(6), 1258–1267.MathSciNetCrossRef

Liu, Z. Y., Qiao, H., & Xu, L. (2012). An extended path following algorithm for graph-matching problem. IEEE Transactions on PAMI, 34(7), 1451–1456.CrossRef

Liu, Z. Y., Qiao, H., Yang, X., & Hoi, S. C. (2014). Graph matching by simplified convex–concave relaxation procedure. International Journal of Computer Vision, 109(3), 169–186.MathSciNetCrossRefMATH

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.MathSciNetCrossRefMATH

Maciel, J., & Costeira, J. P. (2003). A global solution to sparse correspondence problems. IEEE Transactions on PAMI, 25(2), 187–199.CrossRef

Scott, G. L., & Longuet-Higgins, H. C. (1991). An algorithm for associating the features of two images. Proceedings of the Royal Society of London, 244(1309), 21–26.CrossRef

Shapiro, L. S., & Brady, J. M. (1992). Feature-based correspondence: An eigenvector approach. Image and Vision Computing, 10(5), 283–288.CrossRef

Sinkhorn, R., & Knopp, P. (1967). Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2), 343–348.MathSciNetCrossRefMATH

Tian, Y., Yan, J., Zhang, H., Zhang, Y., Yang, X., & Zha, H. (2012). On the convergence of graph matching: Graduated assignment revisited. In European conference on computer vision (pp. 821–835).

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

Umeyama, S. (1988). An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on PAMI, 10(5), 695–703.CrossRefMATH

van Wyk, B. J., & van Wyk, M. A. (2004). A POCS-based graph matching algorithm. IEEE Transactions on PAMI, 26(11), 1526–1530.CrossRef

Wang, T., & Ling, H. (2017). Gracker: A graph-based planar object tracker. IEEE Transactions on PAMI, 40(6), 1494–1501.CrossRef

Wang, T., Ling, H., Lang, C., & Feng, S. (2018). Graph matching with adaptive and branching path following. IEEE Transactions on PAMI, 40(12), 2853–2867.CrossRef

Zaslavskiy, M., Bach, F., & Vert, J. P. (2009). A path following algorithm for the graph matching problem. IEEE Transactions on PAMI, 31(12), 2227–2242.CrossRef

Zass, R., & Shashua, A. (2008). Probabilistic graph and hypergraph matching. In IEEE conference on CVPR (pp. 1–8).

Zhang, Z., Shi, Q., McAuley, J., Wei, W., Zhang, Y., & Van Den Hengel, A. (2016). Pairwise matching through max-weight bipartite belief propagation. In IEEE conference on CVPR (pp. 1202–1210).

Zhou, F., & De la Torre, F. (2012). Factorized graph matching. In IEEE conference on CVPR (pp. 127–134).

Zhou, Q., Fan, H., Zheng, S., Su, H., Li, X., Wu, S., & Ling, H. (2018). Graph correspondence transfer for person re-identification. In AAAI conference on artificial intelligence.

Titel: Efficient Feature Matching via Nonnegative Orthogonal Relaxation
verfasst von: Bo Jiang
Jin Tang
Bin Luo
Publikationsdatum: 01.06.2019
Verlag: Springer US
Erschienen in: International Journal of Computer Vision / Ausgabe 9/2019
Print ISSN: 0920-5691
Elektronische ISSN: 1573-1405
DOI: https://doi.org/10.1007/s11263-019-01185-1

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 9/2019

Repetition Estimation

Which and How Many Regions to Gaze: Focus Discriminative Regions for Fine-Grained Visual Categorization

Deep Learning Approach in Aerial Imagery for Supporting Land Search and Rescue Missions

Predicting How to Distribute Work Between Algorithms and Humans to Segment an Image Batch

Deep Supervised Hashing for Fast Image Retrieval

Unsupervised Learning of Foreground Object Segmentation