Quadtree algorithms for template matching on mesh connected computer

The authors present two parallel algorithms to perform template matching of an N × N image with an M × M template on an SIMD mesh connected computer with N × N processors. In the first algorithm, both the image and the template are represented by quadtrees, whereas in the second, the template is represented by a quadtree, and the image is represented by a matrix. The time complexities of the two algorithms are respectively upperbounded by α₁N + β₁M², and β₂M², where α₁, β₁, and β₂ are constants