Cantag is a free C++ software library which supports the construction of tag-tracking systems by providing various machine vision algorithms and the functionality required to join them together. Cantag is targeted at marker-based machine vision and focusses on algorithms for recovering information from 2D barcodes.
More information on Cantag is available on the DTG research pages and in "Dependable systems for Sentient Computing", Andrew Rice, Ph.D. dissertation, University of Cambridge Computer Laboratory Technical Report UCAM-CL-TR-686, 2007 [pdf].
You can download a snapshot from the subversion repostitory here: Cantag.tar.bz2
The library is currently being used for a number of research projects. If you are using Cantag or if you think it could help your project please let me know.
Optical mark readers have existed for many years and provide a way to recover answers to multiple choice questions from a questionnaire. Digital markers have significant advantages: 1) they can hold a data or an identifier and so the particular type or design of the form can be recognised automatically; 2) recovering the pose of the tag allows any arbitrary portion of the page to be read. Paul is investigating how tags might be added to questionnaires without being overly intrusive and what additional types of response above simple multiple choice could be accommodated.
Location systems have proven their worth within sentient/ubiquitous/pervasive computing and also have the potential to provide fundamentally useful information for apportioning energy consumption to individuals (see the Personal Energy Meter). However, current systems tend to consume a lot of resource and power due to their infrastructure requirements. Marker-based machine vision systems could be an ideal platform to build a low-infrastructure location system because a) the markers themselves are simply printed pieces of paper; and b) we are increasingly carrying cameras around in mobile phones with us for other purposes and so reusing these devices for location too is appealing. Tom is using Cantag to investigate possible marker designs and deployment strategies for building such a system and providing location-based services on top of it.
Most symbolic marker designs are based on square or circular tags and so have an inherent rotational symmetry. This causes a problem when reading a digital code from the tag because it is unclear which way up the tag should be oriented. Designers commonly adopt one of two approaches to circumvent this issue.
The first option is to add asymmetry to the design. This is problematic because it is not possible to quantify how visible (and thus how much tag space) these asymmetric features should occupy—if they are too small then the tag might be misread even if the data bits are actually all visible simply because the additional asymmetric features are obscured or blurred; and if these features are too big we are wasting space which could have been used to carry more data. The popular QR-Code is an example of this approach.
The second option is to rely on an error-detecting coding system to detect when the tag is incorrectly oriented. For this approach to work one must be certain that the permutations in the data read from the tag which are caused by its rotations do not impair the error-detection capability of a code. For example, a CRC code might be capable of detecting an error in any 3 bits of the data. However, if the rotation of the tag causes a permutation of the bits then this could cause an error in all the bits of the payload in the worst case.
In this work we devised coding layouts which are rotationally invariant. This means that a rotation of the tag also causes a rotation in the payload (rather than an arbitrary permutation). When combined with a cyclic-coding scheme it is then possible to guarantee that the Hamming distance of the code is not reduced by rotations of the tag because all rotations of a codeword in a cyclic code are also in the code. We devised a number of schemes which function in this way for both square and circular tag designs.
More information: Andrew Rice, Christopher Cain and John Fawcett. "Dependable Coding for Fiducial Tags (Extended Version)." In Ubiquitous Computing Systems, LNCS 3598, pages 259--274, 2004. [pdf]
There are numerous digital marker systems and numerous tag designs but most are basically either a square or a circular shape. In this work we used Cantag to try to determine the different properties of these designs. Our results demonstrate that square tags are beneficial for large data capacity and that circular tags are beneficial for location recovery due to the behaviour of a circle under perspective distortion.
This analysis also led use to determine the optimal choice of number of rings versus number of sectors and the best ratio between ring sizes for a circular tag.
More information: Andrew C. Rice, Robert K. Harle and Alastair R. Beresford. "Analysing fundamental properties of marker-based vision system designs". In Pervasive and Mobile Computing, 2(4):453–471, 2006. [pdf] and Chapter 3 of "Dependable systems for Sentient Computing", Andrew Rice, Ph.D. dissertation, University of Cambridge Computer Laboratory Technical Report UCAM-CL-TR-686, 2007 [pdf].
A single tag suffers from a number of drawbacks: its data carrying capacity is limited and (for many systems) it must be entirely visible to the camera in order to recover the data. Rob devised a coding scheme for spreading the data payload across multiple tags such that only a subset of the tags needed to be read in order to recover the data.
More information: R. K. Harle, A. Hopper, Cluster Tagging: Robust Fiducial Tracking for Smart Environments. 2nd International Workshop on Location- and Context-Awareness (LoCA 2006), Series LNCS, Number 3987, Springer-Verlag, May 2006. [pdf].
The image processing algorithms in Cantag can also serve a useful purpose for other applications than marker-tracking. In this case the contour follower implementation provided one of the steps required for Jon Davies' algorithm for recovering (topologically correct) road-maps from GPS data.
More information: Jonathan J. Davies, Alastair R. Beresford, Andy Hopper, "Scalable, Distributed, Real-Time Map Generation." IEEE Pervasive Computing, Volume 5, Number 4, Pages 47-54, IEEE, October 2006. [pdf].