Fast Template Matching Based on Normalized Cross Correlation with Centroid Bounding

In this paper, we propose a fast pattern matching algorithm based on normalized cross correlation (NCC) with centroid bounding to achieve very efficient search. The algorithm will calculate histogram around centroid within maximum circle with radius R. After dividing the image into blocks by R×R size, calculating the similarity between the color histograms of the image block and centroid around circle to get potential blocks that the centroid of the template might be in, then by applying NCC to get the final result. Experimental results show the proposed algorithm is very efficient comparing with full-search NCC. The results has broad applications in the fields of object detecting, image retrieval and etc.