Dynamic programming algorithms for picture comparison

AbstractTwo-dimensional arrays can be compared by a generalization of dynamic programming algorithms for string comparison. Earlier algorithms have computational complexity O(N6) for comparison of two N × N arrays. The computational complexity is reduced to O(N4) in general and O(N2) algorithms are 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 open