d-touch Markers

I’ve been using something called d-touch recently, which could be described roughly as “barcodes that can look interesting”, and it doesn’t require expensive or specialist equipment, just a webcam and a capable CPU.

A program running on the computer monitors the feed from the webcam, and when it sees one or more of the “markers”, it can be instructed to respond appropriately.

As I attempted to explain in a presentation recently using this wonderful animation, blown up to huge proportions by projector, the markers are identified using their region adjacency graphs.

Adjacent regions

So unlike barcodes, they can be made to look super interesting.

However, when you need a couple of hundred such markers, coming up with images (which quite honestly is hard enough on its own given the requirements) that each have a unique graph, can get a bit tedious if not impossible.

Luckily, d-touch has some clever stuff built into it, where as long as the marker has a single empty white region and the remaining white regions are sensibly laid out, the graphs don’t actually have to be unique. If the same graph is defined in the configuration multiple times, d-touch will start at that empty white region, or at the lowest valued (on how many regions it contains)  white region, and select the next region as the one with the closest central point to that first region. So in other words, the position of regions can become relevant.

One of the applications on the d-touch site comes with 24 markers, all based on permutations of the 1,2,3,4 graph.

I’ve taken that design, and extended it in order to create a bigger set of markers.

After some sketching and calculating, I wrote the following Perl script to do the hard work for me. It generates the images, saves them to a folder, and generates the sequence file for use with the DTServer application.

As you may have noticed, this goes up to 26 region markers, which gives 25! (factorial) unique markers. 25 factorial, thanks to Wolfram Alpha, is apparently 15 septillion, 511 sextillion, 210 quintillion, 43 quadrillion, 330 trillion, 985 billion, 984 million ..I think that counts as an unnecessarily large number of markers. Of course at that number of leaf-level regions, it probably wouldn’t be a terribly effective marker.

Here are two markers from the script, one with it set as above with 7 total regions, one set at 26.

Now, I haven’t actually looked into the exact ins and outs of d-touch, but from my testing these markers do seem to actually work, which is great.

Having modified the code several (hundred) times, I’ve decided that ultimately, it needs to ask how many markers are required and handle the rest itself. It would work out the squarest, most skew-resistant marker it could, using the least empty space. This will require it to shape and position the white regions. The code in the current form can either generate correct filenames xor generate markers where dimensions are kept nice.

As an additional lump of code, this batch file will rename the files to their IDs without re-running the perl script. GeSHi apparently doesn’t like delayed expansion in batch files so it isn’t syntax highlighted because it breaks the HTML.