ADVANCBS IN APPLIED MATHEMATICS 6,129-134 (1985): Dynamic Programming Algorithms for Picture Comparison

Two-dimensional arrays can be compared by a generalization of dynamic pre gramming algorithms for string comparison. Earlier algorithms have computational complexity O(N6) for comparison of two N x N arrays. The computational complexity is reduced to O ( N4) in gend and O ( Nz) algorithms arc pointed out for the range limited case. An example is given to illustrate the lack of knowledge of mathematical properties of these algorithms. The problem of finding an algorithm to compute the minimum number of insertions, deletions, and substitutions to transform one array into another remains opcn. 1985 ~uderm 'C Ras. Inc 1