Microsoft Tag: how does the High Capacity Color Barcode work?

Microsoft Tag was recently announced at CES 2009. It is a new mobile-camera-reading-barcoding scheme that uses
Microsoft Research's High Capacity Color Barcode (which has been around since at least April 2007).

First interesting point
it works in monochrome, not just CMYK. One of the commenters on that thread seems to have missed the point by 'complaining' about Microsoft's "choice" of colors... If the product is aimed at print media, using the base components of four color process printing seems kinda logical?

Second interesting point
Microsoft Tag itself is not a data-storage format. It's like tinyURL but on paper, in color. The HCCB (barcode) standard allows 'storage' any amount of data, but for the fixed size image that Microsoft Tag uses, it makes more sense to store a 'pointer' or lookup to data - held on Microsoft's servers (of course). So Microsoft Tag is really just a 'brand' for an implementation of Research's HCCB idea.

Third interesting point
Microsoft released the reader software across a wide variety of phone platforms almost simultaneously - from iPhone, Android and Blackberry to J2ME, Symbian, PalmOS and Windows Mobile.

BUT how does it actually work?

As per point #2 above - all Tag barcodes must be created on the Microsoft Tag website (Live ID required) since the barcode itself will only contain a 'pointer' to the actual content it references (either a Url, Vcard or just plain text). The input form for a URL barcode looks like this:

(which produced the tag at the top of this post)

Having generated a barcode, you may then wonder how much data is actually stored? (ie. how big is the pointer? how many tags can we make before we run out? are there enough GUIDs in the world :), etc). The HCCB page has a brief description of how four colors compares to two:


So where Black & White limits us to either 0 or 1 for each symbol, using four colors allows 00, 01, 10 or 11 to be represented by a single symbol. The public documentation doesn't seem to discuss much about the use of triangular symbols as opposed to squares - but it "just looking at it" seems more space efficient (and it possibly has advantages when visual-processing too).

Now assuming each symbol/triangle represents two bits, and a tag has 5 rows of 10 symbols (50 symbols = 100 bits), we might assume 12.5 bytes can be stored. The Wikipedia HCCB page says

Microsoft Tag is an implementation of HCCB using 4 colors in a 5 x 10 grid. This yields 105 bits, or 13 bytes, of raw data

however elsewhere in the description of HCCB it notes that the final four symbols/triangles are always the same - the 'palette' which ensures that even in poor color/lighting/contrast/etc conditions the decoder can still differentiate between Yellow, Magenta, Black and Cyan - so we lose 4 symbols/8 bits/1 byte.

That leaves us with 92 bits, or 2 ^ 92 possible combinations. Windows Calc tells me that's 4951760157141521099596496896 Tags (without using some of the bits for error detection/correction or some other purpose). GUIDs are 128-bit by comparison.

That isn't to say that the bits represented by the symbols are simply encoded and resolved to a URL on Microsoft's server... consider the example below:

Here is an existing Tag created on the Microsoft Tag website to redirect to a URL. Using Fiddler after scanning the tag on an iPhone it's easy to see how the Microsoft Tag application "works" over the Internet...

After photographing and decoding the HCCB, it requests two URLs (shown below), both containing a string like this - L25RKKEP6HTXXCZYBP2X2TIMRBCBDW4V - which appears to be a Base 36 encoded string (but representing much more data than the 92 bits theoretically "in" the barcode). It may be encrypted or signed or something - but given it's the common element between the two, it seems likely to represent the barcode contents somehow.

The first request sends User-Agent: TagReader/2.1.68 CFNetwork/342.1 Darwin/9.4.1 - it's sent by the Tag application itself to retrieve the actual contents of the barcode.
http://rs.tag.microsoft.com/L25RKKEP6HTXXCZYBP2X2TIMRBCBDW4V.aspx?Level=1&VID=5+0&RequestType=1

<PAYLOAD><NAME>ConceptDevelopment</NAME></PAYLOAD>

This NAME is then used in the application History. The response (perhaps by the lack of other <DATA>) then causes the application to 'generate' a second request... which sends User-Agent: Mozilla/5.0 (iPhone; U; CPU iPhone OS 2_2 like Mac OS X; en-us) AppleWebKit/525.18.1 (KHTML, like Gecko) Version/3.1.1 Mobile/5G77 Safari/525.20 indicating it's actually Safari calling...

http://rs.tag.microsoft.com/L25RKKEP6HTXXCZYBP2X2TIMRBCBDW4V.aspx?Level=1&VID=5%2B0&TH=_%2Bxrkqa8CU1GhOgWheA%24&PL=r9gT2kA6Wnk7_odMCmtkGJCExSXvsSjMERpFBSHlqAw6JDB47PPYcevPGKZOOl5NUuuvfXMMUiye6J9Dl4QUhCE5fVsroOcMe14zeZ%2BXrlTJvAzSMT5bFCb4o29PTzQD%2BJraRt3YY6orTVl2JZTMaDUiM2rn5txFv8Y%24

<html><head><title>Object moved</title></head><body>
<h2>Object moved to <a href="http://conceptdev.blogspot.com/">here</a>.</h2>
</body></html>

and getting redirected to http://conceptdev.blogspot.com/!

The other barcode types (Text, vCard, Dialler) only send a single request

http://rs.tag.microsoft.com/I3WC77ROEQOP5AL46TPRSU23BZHWZSG2.aspx?Level=1&VID=5%2B0&TH=_%2Bxokry8Ck1AhMMWheA%24&PL=t6IX2kQ5Jwg79vYxdQkAGoa4py78uwSrEBZcH0eNqnIiXjR46PClAOvHacYxWyJPROnNcGAEVEuf5IZZ8ewW%2BjlDeVsvo5p9e1ZCGeD20lbfvm7fIjZdcyf0unUpJzZ94OHeRtnbHtsrRSgWWvO6aiMgUWf07toivso%24

and get a single (more detailed) response to be decoded by the Tag application.

<PAYLOAD><NAME>ConceptDevelopment services</NAME>
<PIN>0</PIN>
<DATA>
r6QEsUVaVGZOm9MVWDszHo_0vTzeonHOUytWESKQ3gVLLjl5kfK5IsvFGaJYLDsEEK3mM2ESIlGlqJp465U4mm1Za1AEgvYhFgwVEr21nnnhijDNAXsjHRWt9k5pGhpIqryJAvr9IYFRHWZWbNi7GmcbG1KivZ4C_Zwo9XgMcU0K8_InYRJ0FouulAj4nCn6bAZ+BQO+6U0QU0E+pL+ECPaALYhoJn9QatmXbD0dDy2juowX6YFjj2IaA08Ru+l1awZKX6remxSQ2S6IbhtgNwun4CB0CglEvqiYY7WWOIA5WCVWH8zmLRIdAlei9Z95+4kmh2MFJ14JqaYXWC0udfM$
</DATA></PAYLOAD>

which in this case displays the following: