K-Means Based Matching Algorithm for Multi-Resolution Feature Descriptors

Authors: Shao-Tzu Huang, Chen-Chien Hsu, Wei-Yen Wang

Abstract:

Matching high dimensional features between images is computationally expensive for exhaustive search approaches in computer vision. Although the dimension of the feature can be degraded by simplifying the prior knowledge of homography, matching accuracy may degrade as a tradeoff. In this paper, we present a feature matching method based on k-means algorithm that reduces the matching cost and matches the features between images instead of using a simplified geometric assumption. Experimental results show that the proposed method outperforms the previous linear exhaustive search approaches in terms of the inlier ratio of matched pairs.

Keywords: Feature matching, k-means clustering, scale invariant feature transform, linear exhaustive search.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1131573

References:

[1] L. Juan and O. Gwun. “A Comparison of SIFT, PCA-SIFT and SURF,” International Journal of Image Processing, Vol. 65, pp. 143-152, 2009.
[2] D. G. Lowe. “Distinctive image features from scale-invariant keypoints,” International journal of computer vision, vol. 60, No. 2, pp. 91-110, 2004.
[3] H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool. “Speeded-up robust features (SURF),” Computer vision and image understanding, vol. 110, No. 3, pp. 346-359, 2008.
[4] Y. Ke and R. Sukthankar. “PCA-SIFT a more distinctive representation for local image descriptors,” Proc. International Conference on Computer Vision and Pattern Recognition, 2004, Vol. 2, pp. 506-513.
[5] B. C. Song and J. B. Ra, “Multiresolution descriptor matching algorithm for fast exhaustive search in norm-sorted databases,” Journal of Electronic Imaging, vol. 14, No.4, pp. 043019-043019, 2005.
[6] B. C. Song, M. J. Kim, and J. B. Ra.” A fast multiresolution feature matching algorithm for exhaustive search in large image databases,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 11, No. 5, pp. 673-678, 2001.
[7] C.-Y. Tsai, A.-H. Tsao, and C.-W. Wang. "Real-time feature descriptor matching via a multi-resolution exhaustive search method," Journal of Software, vol. 8, no. 9, pp. 2197-2201, 2013.
[8] D. G. Lowe. “Object recognition from local scale-invariant features,” In Computer vision, The proceedings of the seventh IEEE international conference on IEEE, 1999, Vol. 2, pp. 1150-1157.
[9] C. Silpa-Anan and R. Hartley. “Optimised KD-trees for fast image descriptor matching,” In Proc. Computer Vision and Pattern Recognition, CVPR 2008. IEEE Conference on IEEE, June, 2008, pp. 1-8.
[10] M. Muja and D. G. Lowe. "Scalable nearest neighbor algorithms for high dimensional data," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 36, No.11, pp. 2227-2240, 2014.
[11] J. A. Hartigan and M. A. Wong, "Algorithm AS 136: A k-means clustering algorithm." Journal of the Royal Statistical Society. Series C (Applied Statistics), Vol. 28, No. 1, pp. 100-108, 1979.
[12] K. Wagstaff, C. Cardie, S. Rogers, and S. Schrödl. “Constrained k-means clustering with background knowledge,” In ICML, June, 2001, Vol. 1, pp. 577-584.
[13] V. Hautamäki, S. Cherednichenko, I. Kärkkäinen, T. Kinnunen, and P. Fränti. “Improving k-means by outlier removal,” In Scandinavian Conference on Image Analysis. Springer Berlin Heidelberg, 2005, pp. 978-987.
[14] D. Nister and H. Stewenius, “Scalable recognition with a vocabulary tree,” Proc. International Conference on Computer Vision and Pattern Recognition, 2006, Vol. 2, pp.2161-2168.
[15] K. Mikolajczyk and C. Schmid, "A performance evaluation of local descriptors," IEEE transactions on pattern analysis and machine intelligence, vol27, No.10, pp. 1615-1630, 2005.