Image Processing Reference
In-Depth Information
The (0-1) chain code (C) representation of L is a sequence of 2-tuples
where the i-th tuple, C
i
, is given by,
C
i
= (C
i,1
= (y
i+1
−y
i
),C
i,2
= (z
i+1
−z
i
)) for 0 ≤i ≤ n−1.
′
′
1
, then the
chain code representation of the 3-D line y = px + y
1
and z = qx + z
1
is the
same as that of y = px + y
′
It is interesting to note that if y
1
= ⌊y
1
⌋+ y
1
and z
1
= ⌊z
1
⌋+z
1
and z = px + z
′
1
.
Before concluding this section, we observe the relationship between the
digitization procedure described and the one proposed by Kim [4] which was
later refined by [201]. In fact we see that the scheme discussed so far and the
schemes from [4, 201] are very close to each other and the difference between
them is the same as that between OBQ and GIQ in 2-D.
3.3.1.2
Characterization of a 3-D DSLS
Theorem 3.12 enables us to decompose the discrete image of a line segment
in its projections without losing any information. This also motivates us to
characterize and analyze the discrete line segment D(L) in terms of its projec-
tions. Using Theorem 3.12, we can easily define an algorithm (see Algorithm
5) to determine the straightness of a 3-D digital arc that runs in O(n) time.
Algorithm 5: To Check a DSLS in 3-D (adapted from [201])
Algorithm Check 3D DSLS
Input: The Set S of n points p
i
: (x
i
,y
i
,z
i
) for 1 ≤i ≤ n.
Output: true/false if S is/is not a 3-D DSLS.
1: Compute S
Y
and S
Z
, the projections of S onto XZ and XY planes
respectively.
2: Determine for each projection S, whether S
Y
and S
Z
are 2D-DSLSs in
the two-dimensional planes XZ and XY planes respectively. If any
test fails, then return false. Otherwise, return true.
End Check 3D DSLS
Step 1 of Algorithm 5 can be clearly performed in O(3n) time, given a set
of n points in the plane. There also exists an O(n) algorithm to determine
whether or not the set is a 2-D DSLS. This test is applied 2 times, leading to
O(2n) time for Step 2.
3.3.2 Characterization of Chain Codes of 3-D DSLS
In this section, we have used the OBQ digitization scheme for a 3-D CSLS.
From the 3-D DSLS, we compute the chain codes of its projections on two