cvpr cvpr2013 cvpr2013-162 cvpr2013-162-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Simon Korman, Daniel Reichman, Gilad Tsur, Shai Avidan
Abstract: Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sublinear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results. To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations.
[1] B. Alexe, V. Petrescu, and V. Ferrari. Exploiting spatial overlap to efficiently compute appearance distances between image windows. NIPS, 2011.
[2] S. Baker and I. Matthews. Lucas-kanade 20 years on: A unifying
[3]
[4]
[5]
[6]
[7]
[8] framework. IJCV, 56(3):221–255, 2004. M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge 2010 (VOC2010) Results. M.A. Fischler and R.C. Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381– 395, 1981. K. Fredriksson. Rotation Invariant Template Matching. PhD thesis, University of Helsinki, 2001 . C.S. Fuh and P. Maragos. Motion displacement estimation using an affine model for image matching. Optical Engineering, 30(7):881 887, 1991. H. Kim and S. de Ara u´jo. Grayscale template-matching invariant to rotation, scale, translation, brightness and contrast. AIVT, pages 100–1 13, 2007. I. Kleiner, D. Keren, I. Newman, and O. Ben-Zwi. Applying property testing to an image partitioning problem. PAMI, 33(2):256–265, 2011.
[9] S. Korman, D. Reichman, G Tsur, and S Avidan. Fast-Match webpage. www . eng .t au . ac . i / ˜s imonk / F a stMat ch. l
[10] D.G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–1 10, 2004.
[11] B. D. Lucas and T. Kanade. An iterative image registration technique with an application to stereo vision. In IJCAI, pages 674–679, 1981 .
[12] K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. PAMI, 27(10): 1615–1630, 2005.
[13] K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir, and L.V. Gool. A comparison of affine region detectors. IJCV, 65(1):43–72, 2005.
[14] J.M. Morel and G. Yu. Asift: A new framework for fully affine invariant image comparison. SIAM Journal on Imaging Sciences, 2(2):438–469, 2009.
[15] W. Ouyang, F. Tombari, S. Mattoccia, L. Di Stefano, and W. Cham. Performance evaluation of full search equivalent pattern matching
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23] algorithms. PAMI, (99): 1–1, 2012. O. Pele and M. Werman. Accelerating pattern matching or how much can you slide? ACCV, pages 435–446, 2007. S. Raskhodnikova. Approximate testing ofvisual properties. In RANDOM, pages 370–381, 2003. D. Ron and G. Tsur. Testing properties of sparse images. In FOCS, pages 468–477. IEEE Computer Society, 2010. H. Shao, T. Svoboda, and L. Van Gool. Zubudzurich buildings database for image based recognition. Tech. Report, 2003. Y. Tian and S.G. Narasimhan. Globally optimal estimation of nonrigid image distortion. IJCV, 98(3):279–302, 2012. D.M. Tsai and C.H. Chiang. Rotation-invariant pattern matching using wavelet decomposition. Pattern Recognition Letters, 23(1): 191 201, 2002. A. van der Schaaf and J.H. van Hateren. Modelling the power spectra of natural images: statistics and information. Vision Research, 36(17):2759–2770, 1996. C.H. Yao and S.Y. Chen. Retrieval of translated, rotated and scaled color textures. Pattern Recognition, 36(4):913–929, 2003. 222333333866