Image Processing Reference
In-Depth Information
Definition 4.2. The concatenation of two fractions a
1
/b
1
and a
2
/b
2
is given
by (a
1
/b
1
)⊗(a
2
/b
2
) = a/b, where a = (a
1
+ a
2
)/c and b = (b
1
+ b
2
)/c for an
integer c such that gcd(a,b) = 1.
€
We can use the splitting formula to recursively split and concatenate the
slope a/b = [q
1
,q
2
,...,q
n
] into atomic slopes ([q] = 1/q with chain code =
0
q−1
1) as follows.
8
<
[q
1
,q
2
,...,q
n−1
+ 1]⊗(q
n
−1)[q
1
,q
2
,...,q
n−1
]
if n is even;
[q
1
,q
2
,...,q
n
] =
(4.5)
:
(q
n
−1)[q
1
,q
2
,...,q
n−1
]⊗[q
1
,q
2
,...,q
n−1
+ 1].
if n is odd.
Note that Eq. 4.5 can be obtained from Eq. 4.4 by using the following fact for
n > 1.
−β
n
γ
n
= (−1)
n
.
α
n
δ
n
(4.6)
Example: On finding the period of a DSL with slope =
3
87
, using Eq. 4.5.
38
87
=
1
2+
1
3+
1
2+
1
5
= [2,3,2,5] ⇒ n = 4 is even
= [2,3,3]⊗4·[2,3,2] ⇒ n = 3 is odd
= 2·[2,3]⊗[2,4]⊗4([2,3]⊗[2,4]) ⇒ n = 2 is even
= 2([3]⊗ 2·[2])⊗([3]⊗3·[2])⊗4([3]⊗2·[2]⊗[3]⊗3·[2])
⇒ atomic slopes
and hence the period
= (001(01)
2
)
2
001(01)
3
(001(01)
2
001(01)
3
)
4
= (001)(0101)(001)(0101)(001)(010101)(001)(0101)(001)(010101)(001)
(0101)(001)(010101)(001)(0101)(001)(010101)(001)(0101)(001)(010101).
See the following example that demonstrates the operation of concatenation.
We have seen that
3
87
= [2,3,2,5] = [2,3,3]⊗4·[2,3,2]. Now,
1
=
10
23
1
7
16
.
[2,3,3] =
and [2,3,2] =
=
1
3+
3
1
3+
2
2 +
2 +
Thus,
[2,3,3]⊗4·[2,3,2] =
10
23
⊗4·
7
23 + 4×16
=
38
10 + 4×7
16
=
87
.
