Image Processing Reference
In-Depth Information
3.4 Digital Plane Segments
Planes come next after straight lines in geometry. Naturally, digitization
and characterization for digital planes have already been the focus of many
researchers [110, 85]. The digital plane segment (DPS) is the digitization of a
plane segment in continuous space. Thus, a DPS is a set of discrete points in
3-D that could have been resulted by the digitization of a plane segment.
Definition 3.7. A support face or (support) of a DPS is a plane P that goes
through one or more points of the DPS so that all other points of the DPS lie
on one side of P.
Forchhammer has mapped the problem of finding the domain of a digital
plane segment (DPS) to the problem of computing the intersection of n half-
spaces in 3-D in [85]. Though Forchhammer's algorithm runs in optimal time,
it is considerably complex for implementation. On the other hand, a simple
algorithm from Kim [110] constructs a support face that, by definition, is a
reconstruction of a digital plane segment. It is not true that a support face
always exists for a DPS. However, most often such a support face is likely to
exist. In this section we outline an optimal algorithm to compute a support
face of a DPS, if it exists, exploiting ideas from both Kim and Forchhammer.
We also present other important characterizations of a digital plane segment.
Another equally fundamental problem regarding a DPS is the estimation of
the area of the original predigitized plane segment. The problem of estimating
the surface area of 3-D objects has been discussed in [81] for grey images. We
discuss here a net code representation of a digital plane segment [42], and
based on this representation, a number of area estimators for discrete planes
are described.
3.4.1 Digitization and Netcode Representation
A plane, P(a,b,c) is expressed by the equation z = ax+by +c where a, b,
and c are any real number. By suitable axes transformation and translation
of the origin, any plane may be equivalently given by z = ax+by+c, 0 ≤b ≤
a ≤ 1. In the latter case, the plane is said to be in the standard situation. In
subsequent discussion, all planes are assumed to be in the standard situation.
We define a digital plane with respect to a model of digitization as defined
below.
Definition 3.8. Digitization D(p) of a plane segment P (P : z = ax+by+c,
0 ≤ b ≤ a ≤ 1), in 0 ≤ x,y ≤ n,is defined as follows: D(P) = {(i,j,k)|i,j,k
integers, 0 ≤i,j ≤n and k = ⌊ai + bj + c⌋}
Clearly, D(p) contains (n + 1) 2 points, which are represented by an (n +
1) × (n + 1) matrix v where v(i,j) = k. Therefore, every row v i (or column
Search WWH ::




Custom Search