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.
Given a binary matrix, how to find the starting coordinates of a sub matrix?
computer vision;matrices;encoding scheme
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.