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

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.)

• What is "subimage trees"? I couldn't find information of this by searching. Feb 24 at 9:57
• What I mean is a 2D version of a suffix tree. Instead of mapping each substrings of a string to the positions in the string where they occur, it would map subimages of the original images to the 2D positions where they occur. I'm being vague because I haven't actually tried to implement it. Feb 24 at 11:25

## 1 Answer

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.

• You're right, the linked problem is different. I've removed the reference. I am looking for exact matching, not approximate matching. Feb 23 at 16:05
• I have rewritten the answer for the updated question. Feb 24 at 10:42
• Thanks for the update, this looks very useful. Feb 24 at 11:28