Localization Pattern

Symbol Choice

Although a visual pattern may consist of any set of symbols (such micro-dots of various offsets), binary pixel blocks were the obvious choice for this particular application, primarily because they can be sampled using very low resolution images, in turn significantly reducing real-time processing requirements.

Uniqueness

For a pattern to be usable for positioning, the minimum requirement is that every local window of that pattern must be unique, otherwise the mapping from local pattern to position will not be 1-to-1 leading to ambiguities.

De Bruijn Sequences

In the 1-D case, a valid positioning sequence can be defined as any string where every substring of length n is unique. The longest of such strings for a given code length n are called De Bruijn Sequences, which are cyclic sequences of length 2^n that contain every possible code as substring once. There exist various methods to construct De Bruijn Sequences that will not be detailed here. The significant takeaway is that 2^n is established as the theoretical maximum number of positions that can be decoded from a n-bit code.

A 2D generalization also exists called the De Bruijn Torus, which are of size 2^(n^2) and densely contain every matrix of size n x n uniquely. It would seem that this makes the ideal basis for a 2D positioning pattern, but in practice, there are no known algorithm to efficiently decode them. Another shortcoming is that because the pattern is maximally dense, it has no buffer to detect or correct decoding errors, since every single bit flip will map to another position.

1D Separable Pattern

The structure of the 2D pattern is primarily inspired from a method by Bruckstien et al, where the Outer Product of two 1D sequences are taken using XOR as the composition operator. For example:

		1	0	0	1
1		0	1	1	0
0		1	0	0	1
1		0	1	1	0
0		1	0	0	1

This mapping provides a simple and efficient way to convert between 1D sequences and 2D patterns while preserving the uniqueness property necessary for localization. Aside from the native performance of XOR operations, a massive benefit is that the problem of decoding a 2D pattern is reduced to separate 1D problems for each axis, which is individually much simpler. With this scheme, 2^2n positions can be decoded from a (n x n)-bit block, which is much less than the theoretical maximum density, but allows for error correction via redundancy across rows and columns. However since the XOR operator is only invert-able up to a parity, 2D to 1D conversion leaves the ambiguity of whether the resultant 1D codes are bit-wise inverted. This will later be addressed by extending the uniqueness property of the source sequence to bit-wise inversions as well.

XOR Binary Matrix Factorization

To obtain 1D codes from a 2D block generated as mentioned above, it is sufficient to simply take any pair of row and column, which will directly be the solution (up to an unknown parity). In practice however, the 2D block will be corrupted by errors, and it is desirable to account for all rows and columns to produce the most likely output.

Decoding Another benefit the XOR operation used in decoding is fast.

However, parity information is lost.

Decode is trivial, To decode, any pair of row or column is.