What is the time complexity of determining maximal overlaps between bitmap images?

Question

Given two bitmap images (two arbitrarily sized two-dimensional matrices of integer values ranging from 0 to some maximum number), I want to determine their maximum overlaps.

An overlap is a relative positioning of the images (a translation of the second image) producing a nonempty intersection on which both images are the same.

For instance, the images $\left\langle \begin{bmatrix}0 & 1\\0 & 1\end{bmatrix}, \begin{bmatrix}1 & 1\\1 & 1\end{bmatrix} \right\rangle$ have overlaps $\{ (1,-1), (1,0), (1,1) \}$, with intersection sizes $1,2,1$, respectively, so only $(1,0)$ is maximal.

It seems to me we can create a fast algorithm based on generalizing suffix trees to "subimage trees", built with a floodfill algorithm.

Is this a viable approach? Is it better than alternatives?

Is this problem discussed in the literature? What is its time complexity?

(My apologies for asking several related questions at once.)

Answer 1

For a pair of matrices $A, B$, $B$ maximally overlaps $A$ at a position if and only if certain two rectangular sub-matrices of $A$ and $B$ match.

It is not clear how to use the two-dimensional suffix tree for this problem, because this data structure can only process square sub-matrix matching queries.

An answer is to use the fingerprinting-based algorithm. By generalizing Rabin-Karp algorithm, any rectangular sub-matrix pattern matching query can be answered in constant time.

More specifically, a matrix $A \in \mathbb{Z}^{n \times m}$ is represented by a fingerprint $h(A) = \sum_{i=1}^n \sum_{j=1}^m A_{i,j} X^{i-1} Y^{j-1}$ in two randomly-chosen variables $X, Y$ in a big enough finite field. By pre-computing all "prefix" values of forms $h(A[1:i,1:j])$ and $X^iY^j$, any fingerprint of a rectangular sub-matrix can be computed in constant time.