Triangulation-Based Approaches to Three-Dimensional Scene Reconstruction - 3D Computer Vision: Efficient Methods and Applications - page 32

they are fast enough for real-time processing. The limit of usability is the assump-
tion that the straight lines through the corners appear approximately straight in the
image. Once the lens distortion effects are comparable to the corner spacing in the
image, this assumption is not valid, since it is only true for lenses with weak distor-
tion. If it is required to cope with wide angle lenses, lens distortion increases. In the
image, lens distortion makes straight lines appear bent. This effect directly leads to
blurring in the Hough accumulator of the first sorting stage when compared to a lens
with weak distortion. In the blurred Hough accumulator, maxima cannot be detected
precisely, such that false positive lines appear or existing lines remain undetected.
Obviously, this behaviour is directly related to the fact that the Hough transform is
a global algorithm. One way to cope with the distortion is to change from a global
approach to a local approach.
1.4.7.3 A Graph-Based Rig Extraction Algorithm
Outline of the Rig Finding Algorithm The proposed algorithm is based on the
previously mentioned features, i.e. the cross-correlation coefficient between the im-
age and a corner mask. The local extrema are identified, and their position is de-
termined at subpixel accuracy by means of weighted mean or bivariate quadratic
interpolation.
The major difference from the existing approaches is the integration of these lo-
cal extrema to a complete rig. Both the Hough transform and the proposed algorithm
are bottom-up algorithms: Starting with atomic features, more complex entities are
constructed, cumulating in the complete rig. The integration in this algorithm is
done using topological methods. This approach is guided by a general principle: It
is preferable to discard the whole image rather than accept a false positive identi-
fication of the corners. This strategy results from the fact that images are easy to
acquire, while errors are hard to cope with during subsequent processing stages.
One observes that positive and negative correlation coefficient peaks interchange.
Each positive peak has four negative neighbours directly connected along the
black/white edges of the squares and vice versa. This effect is shown in Fig. 1.6 .The
first step is to identify this neighbourhood relation, which is illustrated in Fig. 1.7 a
showing a close-up of the image in Fig. 1.6 .
The next steps verify the resulting directed graph according to a few simple rules
that eliminate the edges to false positive corners and cut the graph such that the rig
becomes a single graph component, where each corner candidate contains the edges
to the four neighbours, labelled with the respective directions (left, right, up, down).
The first filter is used to eliminate non-bidirectional graph edges. Figures 1.7 a
and b illustrate a situation where a false positive is eliminated this way.
The second filter checks for circles of length 4. These circles in the graph map
directly to the edges of the squares. Figure 1.7 illustrates incomplete circles (e.g.
Fig. 1.7 b, top row, leftmost corner) and complete circles only (cf. Fig. 1.7 c).
The third filter eliminates graph edges that have an exceptional difference in
length. The lengths are compared along one axis only, i.e. left/right and up/down.