Apriltags 101

Use cases

Apriltags are one of the most popular fiducial markers used in computer vision. They allow you detect and localize a tag(s) in 3D space using just a camera. Apriltags are like QRCodes in that they encode information and can localize. Compared to QRCodes they provide more robust localization but encode less information (just a tag id). 

Apriltags are commonly used in robotics and AR/VR to identify and localize objects in an environment. This can enable inside out tracking/localization or bring physical objects into the virtual world for human or robot interaction. 

See a demo below that demonstrates the detection and localization capabilities of Apriltags with nice AR overlay.

Lexicode and Hamming Distance

The payload encoded in Apriltags is a modified Lexicographical code or lexicodes. Lexicodes are a form of error correcting codes that guarantee a minimum hamming distance from all other codes in a set. Hamming distance is the measure of how many bits need to be changed to get from one code to another.

Take for example a 3 bit coding system:

hamming_distance( 0b001, 0b100 ) = 3    # Because you have to flip 3 bits to get from 0b001 to 0b100

hamming_distance( 0b001, 0b010 ) = 2    # Because you have to flip 2 bits to get from 0b001 to 0b010

hamming_distance( 0b001, 0b000 ) = 1    # Because you have to flip 1 bits to get from 0b001 to 0b000

To generate a lexicode set you start from 0 and increment your way through all possible numbers in the bit range. For a 3 bit code that's 8 numbers. For each number you check its a hamming distance to all the existing codes in the lexicode set. If the hamming distance is greater than or equal to some user defined threshold then the code gets added to the set. 

For a lexicode of 3 bits and hamming distance of 2 this is the process:

Rotation Tolerant

Since Apriltag bits are encoded into a square (vs a flat vector), their lexicodes need to be rotation tolerant. This requires a minor modification to the lexicode generation process. When checking a candidate code, the code is rotated to all possible rotations (0, 90, 180, 270 degrees) and checked against all the codes in the set. If the code maintains the minimum hamming distance through all rotations then it is added to the set. 

Geometric Complexity

Another modification made to lexicode generation for Apriltags is a complexity metric. The idea is that a code of 0 will just be black square. This is common is nature and not very robust against false positives. To combat simple geometries, like a black square, the Apriltag generation algorithm counts all the non overlapping rectangles in a candidate code (the complexity) and compares it to a threshold value (10). If the complexity is below the threshold then the candidate code is thrown out.

Code Entropy

The final modification to the lexicode generation process is incorporating more entropy into the process to reduce the false positive rate. As shown above, lexicode generation typically is done in sequential order. The modified sequence follows this order (b, b+1p, b+2p, b+3p, ...) where b is an arbitrary number, p is a large prime, and the lowest n bits (n being the bit length of the code) are used as the candidate code. This increases entropy but tends to favor smaller code values. A disadvantage of this method is that the codes aren't as tightly packed together compared to the dense sequential search. This results in a smaller set of available ids. 

Additional Reading / References

If you want to learn more about Apriltags, like how the detection and localization algorithm works, check out the amazing Apriltag papers. If you want me to break down the Apriltag algorithms, leave a comment below.

Apriltag gen 1 paper: AprilTag: A robust and flexible visual fiducial system

Apriltag gen 2 paper: AprilTag 2: Efficient and robust fiducial detection

Apriltag gen 3 paper: Flexible Layouts for Fiducial Tags

Also see our other blog posts on Apriltags for continued learning