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

Ta b l e 1 . 1 Definitions of the
graph functions used by the
edge circle filter

d cw (d) ccw (d) Opposite (d)

Left Up Down Right

Up Right Left Down

Right Down Up Left

Down Left Right Up

tions cw (d) (clockwise), ccw (d) (counter-clockwise), and opposite (d) are defined
according to Table 1.1 .

Edge Circle Filter The filter is implemented as a mark-and-sweep algorithm. In
the first run, all corner candidates are marked which are part of at least one circle
of length 4. The second run eliminates all candidates that are not marked. The cir-
cle check is performed as follows: A vertex

S x which either fulfils the conditions

in ( 1.74 )-( 1.78 )

e 1 = S x , S x 1 ,d ∈ E

for all d ∈ D (1.74)

e 2 = S x 1 , S x 2 ,d 1 = cw (d) ∈ E (1.75)

e 3 = S x 2 , S x 3 ,d 2 = cw (d 1 ) ∈

E (1.76)

e 4 = S x 3 , S x 4 ,d 3 = cw (d 2 ) ∈ E (1.77)

S x S x 4

=

(1.78)

or ( 1.79 )-( 1.83 )

e 1 = S x , S x 1 ,d ∈

E for all d ∈ D (1.79)

e 2 = S x 1 , S x 2 ,d 1 = ccw (d) ∈

E (1.80)

e 3 = S x 2 , S x 3 ,d 2 = ccw (d 1 ) ∈ E (1.81)

e 4 = S x 3 , S x 4 ,d 3 = ccw (d 2 ) ∈

E (1.82)

S x S x 4

= (1.83)

is marked.

Edge Length Filter For each vertex with edges oriented in opposite directions,
i.e. (s, t 1 ,d) ∈ E and (s, t 2 , opposite (d)) ∈ E , the lengths l 1 =

S x s − S x t 1

and

S x s − S x t 2

l 2 = are determined. If the condition of ( 1.84 ) is not fulfilled, the

lengths of the edges are assumed to be so strongly different that this difference
cannot be explained as a result of lens distortion or a slanted calibration rig. The
threshold δ (default value: 0 . 6) depends on the expected lens distortion. The larger
the distortion, the smaller should be the threshold value:
min (l 1 ,l 2 )
max (l 1 ,l 2 ) >δ.

(1.84)