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
Search WWH ::




Custom Search