Bitmap pattern recogination

Question

Describe and analyze an algorithm that finds the maximum-area rectangular pattern that appears more than once in a given bitmap. Specifically, given a two-dimensional array M[1 .. n, 1 .. n] of bits as input, your algorithm should output the area of the largest repeated rectangular pattern in M. For example, given the bitmap shown on the left in the figure below, your algorithm should return the integer 195, which is the area of the 15 x 13 doggo. (Although it doesn’t happen in this example, the two copies of the repeated pattern might overlap.) Image: enter image description here

Answer 1

Using term rectangle instead of sub-matrix.

Brute Force Approach O(n^8)
Take two distinct positions A and B in matrix. Then consider all rectangles in the matrix with A as top left corner. Similarly consider all rectangles with B as top left corner. Suppose we have a rectangle with top-left corner A of length l and breadth b, then take corresponding rectangle with top left corner B, length l, breath b (Assuming both such rectangles exist). If every bit of both rectangles match, then we have a pattern of area of lb repeating and if lb is greater than previously seen maximum area, update the maximum area.
Repeat this procedure for all pairs of A and B.

Time Complexity : Without making analysis complex, let us assume that for every point P in matrix,for all rectangles with P as top left corner, possible maximum length of rectangle is n (But this is not true, for example consider point in the last row and last column of matrix). Let us make similar assumption for maximum possible breath of rectangle.
Then from product rule in counting, there are n^2 possible rectangles with point P as their top left corner.
This estimate is not so bad because according to this, there are total n^4 rectangles possible, as there are n^2 points in the rectangle and we have n^2 rectangles per point.
Actual answer is ( (n+1) Choose 2 ) * ( (n+1) Choose 2 ), which is in the order of n^4

So in total, for each pair, we'd compare n^2 rectangles. And similar to above, let us estimate that there are n^2 points in each rectangle for easy calculations. So for a pair of points A and B, we'll have O(n^4) comparisons because for each rectangle, we need to check all of their corresponding points.

And there are ( n^2 Choose 2 ) pairs of points in total, which is of order n^4. So we'd have overall time complexity of O(n^8).

Avoiding Repeated Calculations O(n^6)
We see that we are repeatedly checking same area again and again. For example consider two rectangles with top-left corners at A and B respectively, with length l and breadth b. Again when we check another corresponding rectangles with top-left corners at A and B with length (l+1) and breadth b, we are again checking rectangle of length l and breadth b.

So we use memoization to avoid repeated calculations.
Assume length of a rectangle is measured horizontally and breadth vertically measured.
Consider rectangles of length l+1 and breadth b with top-left corners at A and B. Now we need to compare if all values of corresponding points in rectangles match. A_r, B_r be points to right of A and B respectively. Then if rectangles have same values for all corresponding points, rectangles of length l, breadth b with top left corners A and B must repeat. Similarly rectangles of length l and breadth b with top-left corners at A_r and B_r must match.
Consider below figure :

Time Complexity By above procedure, it'd take O(1) time to compare two rectangles. So compared to above case, time complexity is reduced by a factor of n^2 (which was time required to compare rectangles in earlier case). So O(n^6) time in this case.

Let us represent (P, m, n) as rectangle with top-left corner P, length m and breadth m.

Removing unnecessary calculations O(n^5)
In the above approach, even if we know that if rectangles (A, l, b) and (B, l, b) do not match we again compare the rectangles (A, l+1, b) and (B, l+1, B).
So suppose now we have rectangles with top-left corners A and B each of length l, then what is maximum possible breadth of the rectangles?
If all the corresponding elements in top row of each rectangle do not match, then answer is 0. But if all corresponding rows match, then the answer is 1 + (max.breadth of rectangles of length l but with top-left corners below A and B).

And similar to above approach this calculation would take O(1) time, as we need breadth that of (A, B, l-1) and that of below rectangles with length l.

Refer to this answer Largest Square Block for more clarity.

Time Complexity For each pair of points in the matrix, we have to store max. breadth for length 1, 2, ...n. And there are order of n^4 such pairs. And we can check obtain each value in O(1) time. So overall time complexity is O(n^5). And finding max. area for each length of rectangle for each pair is obvious here.

Further Optimization O(n^4)
Imagine you have two copies of bitmaps. One is glued to the ground and other can move on top the glued one. Let us call fixed one as base and other one as moving bitmap.
Now top-left corner of moving bitmap can be on one of (n^2 - 1) points of base, except the case where moving bitmap sits on top of base. Now in each case, there are some points left-out i.e for some points on base bitmap, there will not be a point of moving one on top of it and vice-versa. Assume top-left corner of moving bitmap needs to have an element of base bitmap below it.

Now take one instance of these (n^2 - 1) configurations. And for all points on moving bitmap which have a point of base bitmap below them, let us construct a new matrix such that it contains "Y" if top and bottom element of both the bitmaps are same, else it'd contain "N". And remember, the size of matrix is same as no of elements on moving bitmap which have an element of base bitmap below them.

Then, maximum area of repeated pattern for that portions of base and moving bitmaps would be maximum solid block area containing all Y's, which can be done in O(n^2) time.
Our required answer is maximum of answers in all these (n^2 - 1) configurations.

Refer to Largest rectangle containing all Y's for further clarity

Time Complexity For each configuration, constructing new matrix of "Y" and "N"'s would take O(n^2) time and maximum area calculation also O(n^2) time. And there are (n^2- 1) such configurations, so overall O(n^4) time.

Further Optimization O(n^3 polylog(n))

Consider in above bitmap :

• For length : 1, a rectangle with length : 1 and breadth 3 is repeating twice. (1st and 2nd columns are same in bitmap). So maxBreadth(1) is 3.
  

• For length : 2, a rectangle with length : 2 and breadth 2 is repeating twice. So maxBreadth(2) is 2.
  The rectangle is :
  

0	0
0	0

• For length : 3, a rectangle with length : 3 and breadth 1 is repeating twice. So maxBreadth(3) is 1.
  

• For lengths : 4, no rectangle with length : 4 is repeating in the bitMap, so maxBreadth(4) is 0.
  

Consider you have a method named maxBreadth which takes a bitmap matrix and length L as input and returns to you the maximum breadth B for which there is a repeating rectangle of with length L and breadth B in the bitmap.

Using this, can you find the area of largest repeating rectangle in a bitmap?? Iterate over each length. We now know that there is a rectangle repeating in the bitmap with area length * maxBreadth(bitMap, length). Update the corresponding maximum area encountered till now.

So now let's focus on maxBreadth method.
Observations :

• If a rectangle of length 3 and breadth 5 is not repeating in given bitmap then a rectangle of length 3 and breadth 6 definitely will not be repeating in the bitmap. Generally if a rectangle of length l and breadth b does not repeat in bitMap, any rectangle of length l and breadth > b does not repeat in bitMap. Same goes for length also.
  

So based on above observation, you can do binary search to find maxBreadth of given length.

If rectangle of length L breadth B is

• repeating, then check for breadth 2B

• not repeating, then check for breadth B/2

Ok, now how to check if any rectangle of dimensions (l, b) is repeating in a bitMap? There are n^2 such rectangles, so will you compare each with all the others?
What will you do if you asked if an array of numbers is having a repeated element efficiently? Answer is to sort them and check
So take all the n^2 rectangles and sort them and check if there is any repeating one. And how to compare two 2D rectangles, just divide the rectangle into 4 quadrants and compare them individually. In this way we only need to store sorted indices for breadths 1, 2, 4, 8, ... n. and also for lengths 1, 2, 4, 8, ....n.

Each sorting takes O(n^2 log(n)) time for given (length, breadth) And for each length we perform this operation log(n) times, so total O((n.logn)^2) time complexity for maxBreadth operation.

Finally we call the method maxBreadth n times, so overall time complexity is O(n^3 log(n)^2) and space complexity is O((n.logn)^2)

Note : This O(n^3 log(n)^2) method not only works for bitMaps but also for matrices containing any number of distinct arbitrary numbers to search for maximum repeating sub-matrix