×

Efficient feature matching via nonnegative orthogonal relaxation. (English) Zbl 1477.68376

Summary: 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.

MSC:

68T45 Machine vision and scene understanding
90C10 Integer programming
90C20 Quadratic programming

Software:

CASIA; Gracker
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adamczewski, K., Suh, Y., & Lee, K. M. (2015). Discrete tabu search for graph matching. In IEEE international conference on computer vision (pp. 109-117).
[2] 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. · doi:10.1007/s11263-011-0432-4
[3] Belongie, S., Malik, J., & Puzicha, J. (2002). Shape matching and object recognition using shape contexts. IEEE Transactions on PAMI, 24(4), 509-522. · doi:10.1109/34.993558
[4] Caelli, T., & Kosinov, S. (2004). An eigenspace projection clustering method for inexact graph matching. IEEE Transactions on PAMI, 26(4), 515-519. · doi:10.1109/TPAMI.2004.1265866
[5] 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. · doi:10.1109/TPAMI.2009.28
[6] Cho, M., Lee, J., & Lee, K. M. (2010). Reweighted random walks for graph matching. In European conference on computer vision (pp. 492-505).
[7] 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).
[8] Cour, T., Srinivasan, P., & Shi, J. (2006). Balanced graph matching. In Neural information processing systems (pp. 313-320).
[9] 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).
[10] Egozi, A., Keller, Y., & Guterman, H. (2013). A probabilistic approach to spectral graph matching. IEEE Transactions on PAMI, 35(1), 18-27. · doi:10.1109/TPAMI.2012.51
[11] Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2), 95-110. · doi:10.1002/nav.3800030109
[12] Gold, S., & Rangarajan, A. (1996). A graduated assignment algorithm for graph matching. IEEE Transactions on PAMI, 18(4), 377-388. · doi:10.1109/34.491619
[13] 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).
[14] Jiang, B., Tang, J., Ding, C. H., & Luo, B. (2017). Nonnegative orthogonal graph matching. In AAAI (pp. 4089-4095).
[15] Leordeanu, M., & Hebert, M. (2005). A spectral technique for correspondence problem using pairwise constraints. In International conference on computer vision pp. 1482-1489
[16] 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).
[17] Leordeanu, M., Sukthankar, R., & Hebert, M. (2012). Unsupervised learning for graph matching. International Journal of Computer Vision, 96(1), 28-45. · Zbl 1235.68274 · doi:10.1007/s11263-011-0442-2
[18] 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).
[19] 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. · Zbl 1409.94359 · doi:10.1109/TIP.2017.2683063
[20] Ling, H., & Jacobs, D. W. (2007). Shape classification using inner-distance. IEEE Transactions on PAMI, 29(2), 286-299. · doi:10.1109/TPAMI.2007.41
[21] 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).
[22] Liu, Z. Y., & Qiao, H. (2014). GNCCP-graduated nonconvexityand concavity procedure. IEEE Transactions on PAMI, 36(6), 1258-1267. · doi:10.1109/TPAMI.2013.223
[23] 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. · doi:10.1109/TPAMI.2012.45
[24] 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. · Zbl 1328.68186 · doi:10.1007/s11263-014-0707-7
[25] 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. · Zbl 1374.94246 · doi:10.1109/TIP.2014.2307478
[26] Maciel, J., & Costeira, J. P. (2003). A global solution to sparse correspondence problems. IEEE Transactions on PAMI, 25(2), 187-199. · doi:10.1109/TPAMI.2003.1177151
[27] 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. · doi:10.1098/rspb.1991.0045
[28] Shapiro, L. S., & Brady, J. M. (1992). Feature-based correspondence: An eigenvector approach. Image and Vision Computing, 10(5), 283-288. · doi:10.1016/0262-8856(92)90043-3
[29] Sinkhorn, R., & Knopp, P. (1967). Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2), 343-348. · Zbl 0152.01403 · doi:10.2140/pjm.1967.21.343
[30] 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).
[31] 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).
[32] Umeyama, S. (1988). An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on PAMI, 10(5), 695-703. · Zbl 0678.05049 · doi:10.1109/34.6778
[33] van Wyk, B. J., & van Wyk, M. A. (2004). A POCS-based graph matching algorithm. IEEE Transactions on PAMI, 26(11), 1526-1530. · doi:10.1109/TPAMI.2004.95
[34] Wang, T., & Ling, H. (2017). Gracker: A graph-based planar object tracker. IEEE Transactions on PAMI, 40(6), 1494-1501. · doi:10.1109/TPAMI.2017.2716350
[35] 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. · doi:10.1109/TPAMI.2017.2767591
[36] 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. · doi:10.1109/TPAMI.2008.245
[37] Zass, R., & Shashua, A. (2008). Probabilistic graph and hypergraph matching. In IEEE conference on CVPR (pp. 1-8).
[38] 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).
[39] Zhou, F., & De la Torre, F. (2012). Factorized graph matching. In IEEE conference on CVPR (pp. 127-134).
[40] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.