Bernstein Polynomial and B´ezier-Bernstein Spline - Bezier and Splines in Image Processing and Machine Vision - page 14

Bresenham's Algorithm

Given two end points, restricted to an octant, Bresenham's algorithm [29]
for generating points for a straight line segment between them checks the
proximity of the actual line to the desired grid location. Let ( x 1 ,y 1 )and
( x 2 ,y 2 ) be the two points through which a discrete straight line segment is
needed. Intercept of the line segment with the line at x = x 1 +1 ,x 1 +2 ,

,x 2
is first considered. If the intercept with the line at x = x 1 + 1 is closer to the
line at y = y 1 +1 , then the point ( x 1 +1 ,y 1 + 1) better approximates
the line segment in question than the point ( x 1 +1 ,y ). This means if the
intercept is greater than or equal to half the distance between ( x 1 +1 ,y )and
( x 1 +1 ,y 1 + 1), then the point ( x 1 +1 ,y 1 + 1) is selected for approximation;
otherwise, the point ( x 1 +1 ,y ) is selected. Next, intercept of the line segment
with the line at x = x 1 + 2 is considered, and the same logic is applied for the
selection of points.
Now instead of finding the intercept, an error term e is used for the se-
lection purpose. Initially, e =

···

1

−

2 , and the initial point ( x 1 ,y 1 ) is selected.

The slope of the line, y

x , is added to e , and the sign of the current value of

e = e + y

x is tested. If it is negative, then the point is selected along the hor-
izontal line, i.e., x is incremented by one and y remains the same. The error
term is then updated by adding the slope to it. However, if the error term is
positive (or two) then the point is selected along the vertical line, i.e., both x
and y are incremented by one. The error term is the n updated by decreasing
it by one. For integer c alculation, e is initialized to e =2

y − x because

2 x = e (say). The flow chart as shown in Figure 1.3 provides

details of the algorithm for the first octant.

y − x =2 e

1.5 Key Pixels and Contour Approximation

1.5.1 Key Pixels

In the analytic plane, contours of an object may exhibit sharp maxima and
minima, and we can detect these points almost accurately without much dif-
ficulty. However, when a contour is digitized in a two dimensional array space
of M

N points or pels or pixels, the sharpness in the curvature of the contour
is destroyed due to the information loss inherent in the process of digitization.
The error is known as the digitization error. Consequently, it becomes rather
dicult and complicated to estimate the points of maxima and minima. We
can always seek an approximate solution to this problem. We define a set of
pixels and call them key pixels, which are close to the points of maxima and
minima.
Consider, for example, a function f ( x ) in the discrete plane. When f ( x )is
constant in an interval [ k 1 ,k 2 ], the corresponding function f a ( x ) may exhibit

×