Saturday, May 14, 2016

Unique 2D Barcodes with Orientation Detection

A friend of mine is studying to be a teacher and was recently explaining how she uses a service called Plickers to administer multiple choice tests in classes.  Every child gets their own square matrix style barcode on a card approximately 100mm x 100mm (that can vary though).  Each side of the code is labelled with the letters A, B, C, or D and when a question is asked, the kids hold up their card with the letter that corresponds to their answer at the top.  The teacher then uses an app to scan the class, recording each child's answer.  It works because the set of cards provided are unique no matter what orientation they are viewed in.  It's quite a clever idea, not only can the software say "that card belongs to student X", it also knows what side is pointing up.  The cards can be downloaded from the website in sets of up to 63 cards and look like this.

Code 47

When I heard 63 I immediately thought that somehow the number of cards was related to 2^6 - 1, but that was just a hunch.  Let's actually work out how many cards are possible.

Each code is made of a 5x5 grid of black and white squares.  By looking through them, you soon notice that the centre square is always white and the 8 surrounding it are black.  This is most likely similar to the finder pattern in QR codes.  The 4 corner squares are always black as well.  This means that a bounding box for each code can be easily found.  Both of these features make it easier for the the image recognition algorithms to locate and identify each code.  The 12 squares remaining are used to encode data.  These are shown below as blue squares.

Plicker Code Layout
In the image above you can see that each side has three data squares, allowing each set of three to be coloured black or white 8 different ways.  From this point on in the analysis instead of refering to individual squares I'll just refer to the decimal encoding of bits on each side.   For instance, code 47 above can be described as (2,4,5,5) starting at the top, going clockwise and assuming white squares and 0 and black are 1.  As there are 4 different orientations for the card you could also describe it as (4,5,5,2) , (5,5,2,4), or (5, 2, 4, 5).

For this system to work, you need to be able to determine what side of a card is facing up.  If a card looks the same after rotating it either 90, 180, or 270 degrees, it's useless.  What conditions need to be met to ensure this?  Lets take a card with the encoding (a, b,c d) and rotate it 90 degrees to obtain the card (d, a, b, c).  If these two orientations are to be confused (a, b, c, d) is to equal (d, a, c, d).  In the image below you can see that only way that this can happen is if a=b=c=d.  A symmetrical argument can be made for rotation of 270 degrees.

Rotation by 90 degrees

What if the card (a, b, c, d) is rotated 180 degrees to get the card (c, d, a, b)?  This time things are a little different.  The only way the two orientations can be confused is if a=c and b=d.  This can be seen in the image below.

Rotation be 180 degrees

So to make sure that the orientation of a card can be determined, all we need to do is  make sure that the cards aren't rotationally symmetric by 180 degrees.  This covers the cases of rotation by 90, 180, and 270 degrees.  This means the the first two positions can contain any data we want.  This gives rise to an n squared term.  To make sure that the cards aren't rotationally symetrtic, the last two positions can also contain anything we want, except for them being equal to the first two positions.  This gives rise to an n squared minus one term.  This gives rise to an equation of the number of orientations possible.


Dividing this by 4 gives an equation for the number of unique cards possible.  This is because each card covers four different orientations.


In this case n is equal to 8 (2^3) as there are 8 different ways to arrange the squares on each side.  This means there are 1008 different possible cards.  So why do they only use 63 of them?  Your guess is as good as mine.  Maybe they have another condition to make sure that cards have a certain number of differing squares to minimise the chances of cards being misidentified.  Maybe their software only uses one byte to store each scanned card, 6 bits for the card and 2 for the orientation.  Who knows.

I'll just point out that by expanding that equation above, we can easily see that the result will be an integer for any integer input.  If n is even, the n squared term is divisible by 4, if n is odd, (n-1) (n+1) is divisible by 4.


You may also ask why they didn't use QR codes?  Uniqueness of codes is easy and orientation can be determined simply.  A rule of thumb for scanning QR codes with a phone is that you can only scan codes that have a width equal to one tenth of your distance from it.  So lets say a teacher is 5 meters from a student, the code would have to be 50cm wide.  That's too big.  This is because QR codes have a lot of detail.  The Plickers codes are small enough to fit inside the large finder pattern on a QR code.

It'd be interesting to see if it's possible to allow more than 4 options for multiple choice questions.  Maybe holding the card at 45 degrees like a diamond could allow this.  Just a thought.

I've add a small python script that calculates all the possible barcodes just to check the maths.  Everything checks out.
Get the Code!

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.