Microsoft Tag: CMYK or bust?

As I mentioned previously, the Microsoft Tag HCCB format - which is CMYK by default - has been tested in various monochrome formats. Since then, however, I read about the 'palette symbols' - the final four triangles which are the same in every Tag and therefore enable the decoder to handle many color reproductions (once it figures out the bounds and orientation of the tag).


To test out the palette's influence on the decoder, the tag shown to the left has been recolored and then "read" with the Tag Reader application for iPhone.

Each of these versions: Red, White & Blue; Purple, Yellow & White; Blue, Lime & White was decoded successfully. Admittedly the conditions were 'perfect' (represented on screen, photo taken square-on and filling the viewfinder, etc) but it does suggest the format is less sensitive to specific colors than it seems.



I'm sure Microsoft put a lot of thought into standardizing on CMYK though - probably not a great idea to put one of these 'custom color' tags into the wild...

[EDIT] Interestingly, there is some sort of error correction or extraneous symbols in the current implementation too - a couple of my Tags (including the one shown above) work with the bottom row 'blacked out' (but not the 'palette' symbols) like this:

Weird.

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:

Monitoring iPhone web traffic (with Fiddler)

For reasons that will become apparent in a future post, I wanted to 'sniff' the web traffic coming from my iPhone. If you are already familiar with Fiddler (web debugging proxy) you probably already know how easy that is to do. For everyone else, here's a brief rundown of the steps involved:

1. Get Fiddler
Download Fiddler and install it on your PC (with Windows 2000 / XP / 2003 / Vista and Microsoft .NET Framework v2.0 or later)

2. Set-up Fiddler
Start Fiddler then open the Fiddler Options... window


and in the General tab, ensure Allow remote computers to connect is checked.


In the Connections tab, check Act as system proxy on startup and verify what port is set (eg. 8888).

Once you've saved those settings you need to stop and re-start Fiddler.

3. Ensure Fiddler is 'listening'
Once Fiddler has re-started, verify that the Capture Traffic menuitem is ticked.


4. Check the 'listening' IP
You need to know your computer's wireless-network IP address to configure the iPhone. This screenshots shows the Command Prompt > ipconfig output:


5. Set-up iPhone Settings
With the computer IP address and Fiddler port, go to your iPhone's Wifi Settings and scroll down to the HTTP Proxy, choose Manual and input the Fiddler proxy info:

(remember to switch back to Off when you're done)

6. 'sniff' away
If everything has been setup right, anything you do in Safari or other internet applications (like, say Microsoft Tag Reader) will be logged in the Fiddler window.


It's extremely useful for testing/debugging - have fun!

Don't forget to UNDO the iPhone settings when you're finished!!

DeepZoom "Viewer" 1.1

Deep Zoom Viewer has been updated to version 1.1!


It is still only beta-grade software (bug reports welcome) but a few new features have been added:

1. Easier to install
There is now a ClickOnce installer (with the .NET 3.5 SP1 Client Profile set as a pre-requisite). The ClickOnce installer also creates file associations on .DZI and .DZC - double-clicking on these should open them directly in Deep Zoom Viewer.
You can also just download a ZIP file (v1.2) if you prefer.

2. Loading of PhotoZoom by username
Just type a PhotoZoom username (like Craig) to explore the Deep Zoom images created on Microsoft's server-based Deep Zoom site.


3. Image attributes and metadata
Depending on whether you are viewing 'local' or internet-hosted Deep Zoom files, different file information (size, date) and metadata (if created in Deep Zoom Composer) is visible. Clicking on the underlined Location will open the image or tile in a new window.


4. Recent Files menu
Minor convenience...


Hope somebody finds it useful.

EDIT [29-Jan-09] v1.2 released (ZIP only) links updated. ClickOnce is still 1.1 as there seem to be some network connectivity issues when the application is started via ClickOnce...

Calculating distance in C# (with SqlServer.Types)

WiredPrairie's post on Calculating the distance between two Zip Codes in C# starts with the line

Unfortunately, there are many classes built into the .NET framework, but a zip code distance calculator isn’t included.

which is true -- however with the release of SQL Server 2008 Microsoft has made available the redistributable Microsoft.SqlServer.Types assembly that contains the SqlGeography and SqlGeometry types. Within SQL Server 2008 this enables the new geospatial functions, but these types can also be used in C#. I thought I'd add the SQL Server types to his example, just for fun...

I've modified WiredPrairie's code to use Microsoft.SqlServer.Types.SqlGeography in place of manually calculating Radians and using the Haversine formula... only a few minor changes were required (view source):

0. Reference Microsoft.SqlServer.Types assembly


1. Replace the Distance() method completely
I haven't implemented miles here - just kilometres

The important bits being:

string lineString = String.Format("LINESTRING({0} {1}, {2} {3})"
    , compare.Longitude, compare.Latitude
    , this.Longitude, this.Latitude);
var g = Microsoft.SqlServer.Types.SqlGeography.STGeomFromText(
        new System.Data.SqlTypes.SqlChars(new System.Data.SqlTypes.SqlString(
            lineString
        ))
    , 4326); // IMPORTANT for distance calc
geoDistance = Convert.ToDouble(g.STLength().ToString()) / 1000; // to kilometers

2. Remove the conversion to Radians
The SqlGeography type uses Latitude and Longitude in degrees.


3. Minor text changes (miles to kilometres)


4. and finally, change the input from '25 miles' to '40 kilometres'
Here is a comparison of the results -- there appears to minor differences in the calculation results - I assume due to rounding...


Of course, WiredPrairie's solution would run anywhere (including Silverlight) whereas adding a dependency to Microsoft.SqlServer.Types means you can only use this code where the SqlServer Types redistributable has been installed. It's still interesting to see the additional features provided by SQL Server 2008 - I hope some spatial types (without the SQL dependency) make their way into a future core .NET Framework release (and Silverlight 3.0??).

Great Circles!

No, I'm not over-excited about a shape... Great Circles are a 'geographic concept' (via The Map Room).

A great circle is defined as any circle drawn on a globe (or other sphere) with a center that includes the center of the globe. Thus, a great circle divides the globe into two equal halves.

The post reminded me that some additional work on Geoquery 2008 is long overdue. Until then, it prompted me to blog my 'great circle drawing algorithm' as used in Geoquery 2008 to draw lines like this (a 'straight line' between two points, which looks curved on a Mercator projection but is clearly straight when viewed from above on a globe):

The above example uses SQL Server 2008's STBuffer() geography function - notice how the shaded area looks kidney-shaped on the 'flat' Mercator projection (the curve is more pronounced further north) but on the globe the sides are straight.

You can read the C# code to calculate a Great Circle arc or see it below. Given two System.Windows.Points on a Mercator grid (following the Virtual Earth 'scaling' pattern - notice the hardcoded zoomlevel 2 in the LatLongToPixel method calls) it will calculate a Great Circle between them and plot 10 points along that path (notice the hardcoded 0.1 in the for clause). It returns a System.Windows.Shapes.Polyline ready to draw!


It references Virtual Earth Tile System, and the algorithm itself is based on the work by Ed Williams on Aviation Formulary in particular calculating intermediate points on a great circle.

For those who are really paying attention, you may guess this isn't exactly the code used in Geoquery 2008... for a start 10 divisions was too coarse so Geoquery uses a variable number of points based on the length of the line and its proximity to the poles (where the 'curve' is more pronounced). Geoquery ALSO needs to stop/start drawing lines that cross Longitude 180° (so they wrap nicely on Mercator, and join when projected on a globe)... which is done by calculating the intersection of two great circles because SQL Server 2008 couldn't do it (but that's another story...)

P.S. there are some previous posts on the 'straight line' problem that might be an interesting read...

DeepZoom "Viewer"

My MIX09 Silverlight entry - exploDZ hasn't exactly set the voting world on fire :)

However I still think it's a useful concept, so a Wpf version is now available for download at deepzoompublisher.com/Viewer (zip).



It's pretty simple - open local or remote Deep Zoom Composer Xml output and browse around its contents. You can always try the Silverlight version too - here's a test Url to get started http://deepzoompublisher.com/ClientBin/Cities/dzc_output.xml

DeepZoomTools.dll

Deep Zoom Publisher is currently getting 'upgraded' to use DeepZoomTools.dll instead of the rather clumsy "old way":

// the old way
System.Diagnostics.Process p = new Process();
p.StartInfo.FileName = 
  @"C:\Program Files\Microsoft Corporation\Deep Zoom Composer\sparseimagetool.exe";
p.StartInfo.WindowStyle = ProcessWindowStyle.Hidden;
p.StartInfo.Arguments = String.Format(
                        @"CreateCollection  ""{0}"" ""{1}"" ", 
                        filename, sdiname);

It works a lot better, however I was initially stumped by an error message from the Microsoft.DeepZoomTools.CollectionCreator.Create() method:
Invalid character in the given encoding. Line 1, position 1.
at System.Xml.XmlTextReaderImpl.Throw(Exception e) ...
at System.Xml.XmlTextReaderImpl.InvalidCharRecovery(Int32& bytesCount, Int32& charsCount)
at System.Xml.XmlTextReaderImpl.GetChars(Int32 maxCharsCount)
at System.Xml.XmlTextReaderImpl.Read() ...
at Microsoft.DeepZoomTools.CollectionCreator.Create(ICollection`1 images, String destination)

My initial attempt at the code was as follows:

var cc = new Microsoft.DeepZoomTools.CollectionCreator();
var imgs = new List();
var sdiname = proj.GetSdiFilename(); // custom
foreach (var f in proj.ImageList)
{
    imgs.Add(new Image(f.File));
}
cc.Create(imgs, sdiname);

but the error is thrown on the cc.Create line.

Turns out to be a case of RTFM... the Expression blog specifically says

one thing that confused me was what CollectionCreator expected as its “image path”. It isn’t a string of paths to raw JPG, PNG, etc. files. It is actually a path to the Deep Zoom Image created via ImageCreator/SparseImageCreator. SparseImageCreator does take in a list of paths to the source image, so passing in a list of image files will work for generating sparse images (aka Compositions)

Bryant also had it figured out in his example... although it seems to me like the API is a little inconsistent (as the quote says). It is a preview release, so I expect this API will change soon enough...

This code works:

var cc = new Microsoft.DeepZoomTools.CollectionCreator();
var ic = new ImageCreator();
var imgs = new List();
var sdiname = proj.GetSdiFilename(); // custom
foreach (var f in proj.ImageList)
{
    string fn = Path.GetDirectoryName(sdiname) 
             + @"\" + 
             GetFileNameWithoutExtension(f.File) + ".xml";
    ic.Create(f.File, fn);
    imgs.Add(new Image(fn));
}
cc.Create(imgs, sdiname);

More Deep Zoom Publisher to come...

OT: of course before DeepZoomTools.dll there was Berend's CodeProject article...