Image Processing Reference
In-Depth Information
From the symmetry of such conics, it is su
cient to concentrate on the first
quadrant only, though the results can be extended easily over other quadrants
too. In the following discussion, all conics are assumed to be in canonical form
unless otherwise stated.
The OBQ scheme as discussed in Section 3.1 of Chapter 3 has been chosen
for digitizing conics in canonical form. For the sake of illustration, let us
consider an ellipse in canonical form E(a,b) where a and b denote the semi-
major and semi-minor axes, respectively. In Fig. 5.1, we have shown the OBQ
contour of an ellipse whose a = 12.5 and b = 10.5.
Let D
∗
denote the OBQ image of any curve for the ellipse with a = 12.5
and b = 10.5.
D
∗
= {(0,10),(1,10),(2,10),(3,10),(4,9),(5,9),(6,9),(7,8),(8,8),(9,7),
(10,6),(10,5),(11,4),(11,3),(12,2),(12,1),(12,0)}.
Definition 5.2. We define the Y-digitization D
Y
= D
Y
(E) of an ellipse as
follows (in the first quadrant only).
D
Y
= {(i,y
i
) : i,y
i
∈ Z integer, 0 6 i 6
⌊a⌋ and y
i
= max{y|y ∈ Z and
i
2
/a
2
+ y
2
/b
2
6 1)}. That is, y
i
= ⌊b
(1−i
2
/a
2
)⌋,0 6 i 6
⌊a⌋.
€
Since for every i,y
i
is unique, an alternative notion for D
Y
lists (⌊a⌋+ 1)
y
i
values only, as D
Y
= (y
0
,y
1
,y
2
,...,y
⌊a⌋
). We shall use both these notations
interchangeably. We can similarly quantize E along the Y-axis and define the
X- digitization D
X
. Finally, the total digitization is denoted by D = D(E) =
D
X
∪D
Y
. Note that D
X
and D
Y
may not be disjoint.
Example 5.1. In Fig. 5.1,
D
X
= (12,12,12,11,11,10,10,9,8,6,3) or
{(12,0),(12,1),(12,2),(11,3),(11,4),(10,5),(10,6),
(9,7),(8,8),(6,9),(3,10)}
D
Y
= (10,10,10,10,9,9,9,8,8,7,6,4,2) or
{(0,10),(1,10),(2,10),(3,10),(4,9),(5,9),(6,9),(7,8),
(8,8),(9,7),(10,6),(11,4),(12,2)}
D = {(0,10),(1,10),(2,10),(3,10),(4,9),(5,9),(6,9),(7,8),
(8,8),(9,7),(10,6),(10,5),(11,4),(11,3),(12,2),
(12,1),(12,0)}.
In digitization of an ellipse, we may note that both D
X
and D
Y
are re-
quired. This is so because digitization results in grid points having multiple
x-coordinate values for the same y-coordinate and multiple y-coordinate val-
ues for the same x-coordinate.
It is easy to see in this example that D = D
∗
. This is not a coincidence
and holds in general for every ellipse. The formal discussions leading to the
proof is presented later in Theorem 5.12.
