Image Processing Reference
FIGURE 3 A Delaunay triangulation example. Considering A , B , C , and D four image
corners, the valid triangulation if formed by the triangles Δ ( A , B , C ) and Δ ( A , C , D ).
Using the geometric mesh, the vertices and triangles are submited to a topological ilter to
exclude those not satisfying the regularity of the patern. The corners (or vertexes) share in-
ternal triangles of diferent colors in a regular manner. Each square of the chessboard patern
is represented by two triangles of the same color. Each triangle has no more than two neigh-
boring triangles that form two squares with different colors alike. The internal vertexes have
in common a maximum of eight triangles. Valid triangles have its interior filled with a single
Even after the projected image plane, the neighborhood relationship between the corners is
still maintained. This restriction allows evaluating if corners really belong to the calibration
pattern. Thus, are considered valid:
1. Those triangles that do not have color transitions in its interior;
2. Only those triangles that have a neighbor with the same color;
3. Those triangles that have only two neighbors of the same color and different color triangle
taken as reference.
This filter is applied to the grid until there are no more invalid triangles. In the end, the ver-
tices that do not form any triangle are also removed.
To avoid the use of thresholds in the comparison of colors, this filter uses a binarized version
of the image. This is an important step to validate the points. If the binarization process fails,
noisy points can be identified and actual points can be disregarded. To minimize these effects,
gorithm handles well with large variations in illumination and runs in linear time for any win-
The binarization phase can be influenced by problems from the acquisition of images due
to lighting variations and also by the fluctuation of the intensities of the pixels. In the regions
linear to the edges, a range of values may be wrongly considered black or white pixels. This be-
havior can generate white triangles with black borders and black triangles with white edges.
In practice, the verification of color transition is made in a region of an innermost triangle,
ignoring the edges. Figure 4 shows intermediate results of the algorithm including detected
x-corners, initial mesh over the binarized image, and after the topological filtering.
FIGURE 4 Mesh generation and topological filter results. (a) Initial x-corners, (b) triangulation
over binarized image, and (c) valid triangles after topological filter.