A new fast template matching algorithm is proposed in this work. It extracts the local self-similarity as image feature. Feature matching is based on equal comparison and clustering. Its time complexity reduced to 0(size of search image), the theoretic lower limit for classical image template matching. The new algorithm is generalized to partial matching of two images. By partitioning images into blocks by nona-tree decomposition, it detects the
matching regions between blocks and merges the matching results using first order Markov chain in horizontal direction. In the vertical direction merging is implemented directly according neighbor parts connected and keeping the consistent displacements of correspond parts in two image. The algorithm is robust for the linear
transformation of image grey value and image noise.