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