3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ What is "subimage trees"? I couldn't find information of this by searching. $\endgroup$
    – pcpthm
    Feb 24 at 9:57
  • $\begingroup$ 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. $\endgroup$ Feb 24 at 11:25

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.