Discrete Splines and Vision - Bezier and Splines in Image Processing and Machine Vision - page 146

from the corollary 1. Similarity between the recurrence relations for α i,k ( j )
in equation (7.25) and B i,k in equation (7.3) hence makes the computation of
d ( j ) very similar to the computation of f ( x ) for some x with f ( x ) as given
below.

n

f ( x )= B i,k ( x ) P i . (7.28)

i =1

7.2.3 Algorithms

We shall now consider two different algorithms to compute discrete B-splines.
We have already seen the discrete B-spline as

n

d ( j )= α i,k ( j ) P i .

i =1

When τ μ ≤ t j <τ μ +1 ,

μ

d ( j )= α i,k ( j ) P i . (7.29)

i = μ−k +1

To compute the spline, we need to compute α i,k ( j ).
Algorithm 1:
For integers k

≥ 2and j, μ let τ μ +2 −k , ··· ,τ μ + k− 1 and t j +1 , ··· ,t j + k− 1 be

given such that

τ μ +2 −k ≤···≤ τ μ <τ μ +1 ≤···≤ τ μ + k− 1

(7.30)

and

τ μ ≤ t j <τ μ +1 . (7.31)

The algorithm 1, computes α ir = α i,r ( j ) as given by equation (7.15) or equa-
tion (7.25), r =1 , 2 , ··· k ; i = μ +1 − r, ··· ,μ . The discrete B-splines here are

of order k that can be nonzero for the given j . Steps in algorithm 1 are

described as follows.
Step 1: α ( μ, 1) = 1; μ 2= μ ;
Step 2: for r =1 , 2 ,

≤

··· k − 1do

begin
β 1 =0; tj = t ( j + r );
for i = μ 2 ,μ 2 +1 , ··· ,μ do

begin
d 1= tj

− τ ( i ); d 2= τ ( i + r ) − tj ;

β = α ( i, r ) / ( d 1+ d 2);
α ( i − 1 ,r +1)= d 2 ∗ β + β 1 ;

β 1 = d 1 ∗ β ;

end