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