Analysis of a steepest-descent image-matching algorithm

摘要

Image-matching, the attempt to discover in a picture currently under examination an image found in an earlier picture, is a desirable part of many picture-processing and scene-analysis applications. This paper describes an algorithm consisting of two parts; the first is a steepest-descent method for finding the best match in a given locale. The second is a procedure for selecting starting points for the local search.A special analysis is made of both the reliability and speed of the steepest-descent method leading to a conclusion that its average-time performance is 0(n2). This compares rather favorably with the speed of two other popular algorithms for image-matching, namely direct computation of the entire correlation matrix (0(n2(n − m))) and fast Fourier Transform (0((n + m)2log(n + m))), where n and m are the picture- and window-sizes, respectively, measured in pixels.