TL;DR: me rambling on possible directions for the Aztec code. Conclusion: try a lot of things randomly and hope the ECC saves us.
HOW WAS THIS AZTEC CODE POTENTIALLY GENERATED?Suppose that the resulting code can be generated either by
A) rotating the Aztec code 180 degrees, and then overlaying it on the original;
B) rotating the Aztec code 180 degrees, and setting the result using any commutative logical operation (i.e. f(x,y)=f(y,x)) to get a symmetric result (there are 8 possible truth tables that satisfy that requirement);
C) taking half the original Aztec code and adding it's mirror to get a complete one.
D) other?
option Abased on the missing orientation marks, we can cross off option A, or we would have seen them in the result.
option Bthe 8 possible truth tables are
xy a b c d e f g h
00 | 0 0 1 1 0 0 1 1
01 | 0 0 0 0 1 1 1 1
10 | 0 0 0 0 1 1 1 1
11 | 0 1 0 1 0 1 0 1
* the resulting code is not fully white or fully black codes, so possibilities a and h can be ignored.
* overlaying the bottom right orientation marker on the top left orientation marker (
https://en.wikipedia.org/wiki/Aztec_Code#/media/File:Aztec_Code_with_desc.png) means 11->1, given the result (same for the bulls-eye on top of the bulls-eye), hence possibilities c, e and g can be ignored.
This leaves
xy b d f
00 | 0 1 0
01 | 0 0 1
10 | 0 0 1
11 | 1 1 1
* the top right orientation marker on top of the bottom left orientation marker means 10->0, 01->0, 00->0, given the resulting code. Therefore, possibilities d and f can be dismissed.
This leaves only
xy b
00 | 0
01 | 0
10 | 0
11 | 1
* This means that in the resulting code only those pixels that have a mirrored black pixel remain visible. However, that would mean that the top left orientation code would disappear, except for one pixel....which it did not. Hence possibility b can also be dismissed.
Conclusion: no commutative function was used to generate a symmetric Aztec code from the original Aztec code and the original aztec code rotated 180 degrees.
option CThis option is possible if you take a subset of the pixels (
not necessarily half) of the original Aztec code, and then overlay a 180 degree rotated version of that. This is the option analyzed further below.
option DNot sure what other ways there would be to generate a symmetric code. Or perhaps it's not an Aztec code in the first place...
REMOVE THE SYMMETRY, BY REMOVING ONE HALF?Ignoring the 2 extra pixels and the bulls-eye, there is 65 pairs of mirrored pixels and therefore 2^65 ways of removing the symmetry and removing 1 pixel from each pair, and 3^65 possibilities if we also consider the option of keeping both pixels of the pair. Therefore, it's not feasible to go through all possibilities unless a big percentage of those possibilities decode successfully due to the error correction capability of the Aztec code.
Therefore, if removing the symmetry and reading out the result is the right approach, we try assuming a few things to limit the possibilities:
1) that the bulls-eye remains intact
2) a more structured way to leave out half the pixels by requiring that the halves are contiguous areas of pixels (with one of the possibilities given above). Any path from the bulls-eye to the edge of the code, together with its mirrored path defines two such halves that are mirrors of each other.
3) we can further try assuming that the mirrored half contains two correct orientation markers (as shown in
https://en.wikipedia.org/wiki/Aztec_Code#/media/File:Aztec_Code_with_desc.png). Therefore, it must be a half that contains the top-left and bottom-left orientation marker (i.e. the top-right and bottom-right orientation markers are wrong in the Aztec code) that is picked and rotated.
4) the orientation marks of the missing half can be filled in correctly
However, even with these assumptions there are still many ways to do split up the code in two halves and remove one of the halves. We might get lucky though if the error correction level of the original Aztec code is high enough and the exact path does not really matter. Either way, it is probably something we would want to do programmatically.
Alternatively to removing one half completely (which corresponds to flipping all the 1s to 0s in that half), we could randomly guess the missing half of the code and hope the ECC will allow us to read the code .
REMOVE THE SYMMETRY, BY EXPLORING CODES WITHIN A CERTAIN EDIT DISTANCE?Finally, in case we don't make the assumption of the halves being contiguous areas, we could still explore randomly the codes within a certain edit distance of the given code, and hope the ECC will allow us to read the code successfully. So, assume a correct bulls-eye with correct positioning markers, randomly flip up to n pixels in the given code, and attempt to read the result.
ARE WE MISSING SOMETHING?Still:
- the 2 non-symmetric pixels are really bothering me
- we have not used the markings in any way yet.
So, are we missing something here? Did we miss a clue? Or are we just failing to see the forest for the trees?