Digital Geometry in Image Processing

Digital Straight Lines and Planes 99

In the following, we use m

o

and c

o

to denote possible original values of m

and c, respectively, so that digitization of l : y = m

o

x + c

o

yields D

o

. That is,

D(l : y = m

o

x + c) = D

o

.

Theorem 3.6. (The I

R Algorithm) If the upper and lower bounds of m and

c are defined by the following algorithm: [38]

For k ≥ 0,

c

k+1

l

= max

i

{y

i

− m

k

u

.i}, 0 ≤ i ≤ n,

c

k+1

u

= min

i

{y

i

+ 1 − m

k

l

.i}, 0 ≤ i ≤ n,

m

k+1

l

= max

i

{(y

i

− c

k

u

)/i}, 1 ≤ i ≤ n, and

m

k+1

u

= min

i

{(y

i

+ 1 − c

k

l

)/i}1 ≤ i ≤ n

and c

0

l

= y

0

, c

0

u

= y

0

+ 1, m

0

l

= −(1/n), m

0

u

= (n + 1)/n, then, there exist

c

l

, c

u

, m

l

, m

u

such that,

lim

k→∞

m

k

l

= m

l

, lim

k→∞

c

k

u

= c

u

, lim

k→∞

m

k

u

= m

u

, lim

k→∞

c

k

l

= c

l

........(a) ...