# Given a binary matrix, how to find the starting coordinates of a sub matrix?

Say, I have an image of bit depth 1 (i.e. binary matrix) and I cropped the image to form a smaller matrix. From the cropped matrix (of a reasonable size). I need to know the starting coordinates from where the matrix was cropped from.

I encoded some lines at regular intervals. The position of the lines follow the equation $y = x^2$. This way when I find the difference between the distance of two lines i.e. $dy/dx = 2x$, I can calculate the value of x and y. This gives me the position of the pixel at that point. So I can subtract the offset and find the starting coordinates.

The multiple lines are for redundancy sake and colours for illustration.

In this way, I can find the coordinates of cropped images of a reasonable size. My question is, "Is there a proper way of doing it?" Also this technique does not work for lossy file compression techniques like jpeg, does a method exist that is more robust?

I have been reading into Space filling curves but I have no idea how to solve this problem using them.

EDIT: I found a thing called m-sequence. I will add it for future reference.

• If you fill the matrix with random values and the sub-matrix is reasonably big, the probability that it is unique in the source matrix is really high. Oct 25, 2016 at 14:36
• After cropping, I do not have the source matrix. Oct 25, 2016 at 15:16
• What do you mean by lines that follow the equation $y=x^2$? That doesn't match the picture you show.
– D.W.
Oct 26, 2016 at 7:46
• $1 ^ 2 = 1, 2 ^ 2 = 4, 3 ^ 2 = 9$ ... So I am drawing vertical lines at columns 1,4,9,16,25... Then I rotate the image by 90 degrees and do it again. Oct 28, 2016 at 2:12

Here is one approach. It won't survive JPEG compression, though, so probably you can do better.

Let $m$ be an integer large enough that $2^m$ is significantly larger than both the width and height of the matrix. Choose a maximum-period $m$-bit LFSR; this generates a sequence of bits of length $2^m-1$, say $s_1,s_2,s_3,\dots,s_{2^m-1}$, where each $s_i \in \{0,1\}$.

Now, construct the original matrix as follows: at coordinate $(i,j)$, the value will be $s_i \oplus s_j$.

Given a submatrix, we can find coordinates as follows. First note that given a consecutive range of the sequence $s$ of length at least , we can find where in the sequence it was taken from. In other words, given $s_i,s_{i+1},\dots,s_{i+m-1}$, we can recover the value of $i$. (How? Simply trying all possible values of $i$ will work; one property of LFSR sequences is that the map $i \mapsto (s_i,s_{i+1},\dots,s_{i+m-1})$ is bijective, so $i$ will be uniquely determined.)

Now given the submatrix, we'll try to find the coordinates of its upper-left corner, say $(i,j)$. We'll start by looking at the first row of the submatrix, and examine the sequence of values that appear in its grid. This either takes the form $s_i,s_{i+1},s_{i+2},\dots$ or $s_i \oplus 1, s_{i+1} \oplus 1, \dots$ according to whether $s_j=0$ or $s_j=1$. We can try both possibilities for $s_j$, and get two candidates for $i$. Then we look at the first column of the submatrix, and obtain two candidates for $j$ in the same way. This gives us two candidates for $(i,j)$, we can check which one is correct by looking at a few other positions in the submatrix.

Then, you can recover the coordinates of its lower-right corner in the same way.

All in all, this will enable you to recover the coordinates of the submatrix, as long as the submatrix is at least $m$ pixels wide and $m$ pixels high.

There are other ways as well. For instance, one very simple approach is to fill in the original matrix randomly, and remember how you filled it in. Then given a submatrix it is straightforward to find where it came from (e.g., by checking all possibilities; this can be sped up by precomputing a hash table).

In practice, if you plan to print out the original matrix and then take a scan or photo of it, then you might want a different approach that is more robust to the kind of transformations that will typically occur during printing and scanning. That will lead to a very different kind of problem. So if you want to know about how to do that, you should probably ask a separate question focused on those considerations.

• I am having trouble with the JPEG file compression. The linear feedback register is a good idea. I can generate lines of length 8 and embed it into the image in every alternate row for x and y. JPEG would destroy a large part of this data. Then I can do a bit wise majority vote and hopefully, I can recover the original sequence (most of it). I can use that to find the x and y coordinates. Oct 28, 2016 at 2:23
• JPEG compression was mentioned in the original question, below the second diagram. BTW I havent tried it yet, I am otherwise preoccupied. Oct 28, 2016 at 7:17
• Ahh, my fault. Sorry that I missed that -- my mistake.
– D.W.
Oct 28, 2016 at 7:55