< Home

How Many Unique AR Tags Exist? A Formula

January 2, 2016 | Adam Allevato

Click here to skip the derivation and see the results.

In our robotics lab at UT Austin, we often use augmented reality (AR) tags to determine the position and orientation of an object. UT professor Scott Niekum made this possible by developing the ar_track_alvar ROS package while he was still a PhD student. The package makes detecting AR tags as easy as running a roslaunch file (with some slight configuration tweaks).

But as we started placing AR tags on every item in our mock nuclear storage vault, we asked: just how many possible AR tag permutations are possible? If we want to put a unique tag on 10,000 different items, how large does the tag have to be? Is 4×4 enough? 5×5? And so began my mini math-quest for the answer.

Problem statement

We want to find the number of unique, identifiable AR tags. AR tags are a square grid of cells which can be either black or white. The entire tag has a black border, which we will ignore when calculating tag size. The picture below shows 18 unique 6×6 tags.

Some AR tags as provided in the ar_track_alvar ROS package
Some AR tags as provided in the ar_track_alvar ROS package.

A tag may not be rotationally symmetric with itself, nor can it be mirror-symmetric with itself. This requirement ensures that the algorithm can always calculate an unambiguous 6DOF pose for the marker, and it’s also what makes it tricky to come up with a formula for the number of possible tags for a given size. Also, note that for odd-numbered sizes (like 5×5), there is a single middle square. In even-numbered sizes, there is no single center square. This means that the formulas for the odd-numbered and even-numbered sizes will be slightly different.

Solution

We want a formula for the number of unique orientable AR tags that can be represented by an n x n grid of black-and-white squares (each square can store one bit). The easiest way to derive a formula is to look at the odd- and even-numbered sizes separately.

Even

First, calculate the number of squares in the tag’s grid. This is easy, it’s n2. Now, the number of possible combinations of black and white bits in the tag is 2n2. Simple so far, right?

Now we have to subtract off the mirror-symmetric tags. For each possible half of the tag (let’s call it A), there is a full tag that has a top half A and a bottom half that is the mirror image of A. So we need to subtract one for each possible upper half of the tag. The number of possible upper halves is 2(n2)/2. I’m going to switch to copy-pasted equations to save your eyes. The new formula is

2^(n^2)-2^((n^2)/2)

Finally we have to take out rotational symmetry. For each possible non-mirror symmetric correct AR tag, there are 3 more (90, 180, and 270 degree rotations) which look exactly the same, but rotated. A robot can’t tell the difference between a tag that’s rotated 90 degrees and a tag that looks like another tag rotated 90 degrees, so all the rotations will have to go. Just divide by 4.

The number of unique nxn AR tags where n is even.
Equation 2: The number of unique nxn AR tags where n is even.

We’re done now, right? Right?

Odd

Nope, we forgot about odd-numbered sizes, like 5×5! Thankfully, this one is almost exactly the same. We just have to think about the middle square when looking at the “half-tags.”

The number of unique nxn AR tags where n is odd.
Equation 2: The number of unique nxn AR tags where n is odd.

Finally

We can do some fancy math using (-1)n to combine the odd and even formulas into a single formula! Thankfully, my fellow researcher Ben Ebersole already did this for you, and also cleaned up some of the fractions we all know and hate.

Results

For an n x n AR tag (disregarding the black border), the number of unique tags for 6DOF pose estimation is given by

The number of unique nxn AR tags for n > 1.
Equation 3: The number of unique nxn AR tags for n > 1.

Here is a copy-paste version if you want to incorporate this into a program:

permutations = 2^(n^2-2)-2^((2*n^2-(-1)^n-7)/4)

And here are the permutations for common sizes:

nxn Permutations
2×2 3
3×3 120
4×4 16,320
5×5 8,386,560