Supported by the National Natural Science Foundation of China under Grant Nos.60135010, 60321002 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2004CB318108 (国家重点基础研究发展规划(973))
Correlation algorithms based on pixel gray value are very popular and widely used in image template matching. However, these algorithms have high time complexity and are sensitive to the variation of image luminance and scale. To avoid that, a new algorithm based on coding image grey value is proposed. This algorithm divides the image into certain size blocks called R-block, sums the gray value of each R-block pixel, and codes the R-block according to the sorting result among the neighborhood of R-blocks. Image and template are matched by comparing their R-block coding. The R-block is very rapidly and easily coded and only equality comparison is needed. The new algorithm is robust to the linear transformation of pixel grey value and image noise. Its time complexity is reduced to O(M2log(N)), or namely is improved two order of magnitude in contrast to the current correlation algorithms’.