The C++ Augmented Reality Toolkit

5. Marker Detection

A 2D marker or fiducial, as it often called, must be designed in such a way that can be easily detected and be unique enough to be easily identified from other markers. Each marker must also provide some kind of unique binary code so that its ID can determined. Most markers use black and white designs, however in [EPFL 2004] a technique is described that can be used on detailed coloured markers by using classification trees for identification.

In ARLib, black and white markers were used and were based initially on the design in [LIU et al 2002], however as will be shown, this design did not perform well at acute angles.

The marker design uses a 5x5 matrix where each cell represents a single bit in the marker’s identification code, see figure 5.1.

This marker represents a 25 bit binary code. 12 of the bits are used for the actual marker ID. The four corners are used to determine the orientation and the remaining bits are used for error detection. The error detection bits enable falsely detected markers to be rejected.

5.1 Detecting Markers

Detecting a potential marker in ARLib involved finding the location and colour of each cell within the image. Because the corners of the marker were available, the problem was simplified to mapping a square to a quadrilateral, see figure 5.2.

A solution is described in [HECKBERT 1995] and is commonly called projective mapping. The technique is often used in computer graphics when performing texture mapping. Projective mappings can be performed in 3D, but for the purposes of ARLib, 2D projections were used.

5.2 2D-to-2D Projection Mappings

The main principle behind projective mapping is to take points from one plane and project them onto another.

The general form for a projective mapping is:

These previous two equations can be represented in homogeneous form as:

By solving the above unknowns a-i, then by specifying u and v coordinates in the reference square, the x and y coordinates in the quadrilateral can be calculated, see figure 5.3.

In the homogeneous matrix of the problem, assuming i=1, then there are eight unknowns. By using the four corners of the reference square and the four corners of the quadrilateral, then eight equations can be defined. Each corner mapping produces the following equations:

The eight equations can be written using an 8x8 system for k=0 to 3:

The linear solution can be solved using Gaussian elimination or by calculating the inverse of the 8x8 matrix. The downside of solving the above solution is that it it computationally expensive, however this solution handles the mapping of a general quadrilateral to another quadrilateral. For ARLib, all that was required was to map a square to a quadrilateral therefore the solution could be simplified.

Assuming the square to quadrilateral vertex correspondences were as follows:

x	y	u	v
x0	y0	0	0
x1	y1	1	0
x2	y2	1	1
x3	y3	0	1

Then the eight equations could be reduced to:

Using the solved projection mapping equation, it was now a straight forward task to determine the colours of the cells within the potential marker.

The u and v coordinates were divided up into the number of columns and rows and then the central position of each column and row was used to locate the point in the image, see figure 5.4.

5.3 Detection Problem

The marker design described above had some problems in that detection performed poorly as the marker was moved away from the camera, which was amplified when the marker was also at an angle. After a variety of experiments, the markers were redesigned to use large circles instead of square cells. The bits used for error detection were removed to allow more space for the larger circles, see figure 5.5. Using a circle improved marker detection, even at acute angles.

In the original marker design, all cells were scanned during the detection process, whereas in the new design only cells that should be definitely black or white were tested, for example figure 5.6 shows how the marker shown in figure 5.5 was defined.

Using this new approach, in the example above a maximum of 7 checks were needed.

<< 4. Feature Extraction

6. Camera Orientation >>