Chu.o.ng 8
˜
˙’
ˆ˙’ U DIE
ˆ N VA
` MIEU
ˆ TA
BIE

Sau khi a˙’nh d¯u.o..c phˆan d¯oa.n th`anh c´ac v`
ung bˇ`a ng nh˜
u.ng phu.o.ng ph´ap tr`ınh b`ay
trong Chu.o.ng 7, tˆa.p ho..p c´ac pixel thu.`o.ng d¯u.o..c biˆe˙’u diˆ˜en v`a miˆeu ta˙’ o˙’. da.ng th´ıch
`e sau. Vˆ
`e co. ba˙’n, c´o hai c´ach biˆe˙’u diˆ˜en v`
ung: (1) biˆe˙’u
ho..p cho c´ac tiˆe´n tr`ınh xu˙’. l´
y vˆ
diˆ˜en du..a trˆen c´ac d¯ˇa.c tru.ng bˆen ngo`ai (biˆen), hoˇa.c (2) du..a trˆen c´ac d¯ˇa.c tru.ng bˆen
trong v`
ung (c´ac pixel ta.o th`anh v`
ung). Viˆe.c cho.n phu.o.ng ph´ap biˆe˙’u diˆ˜en th´ıch ho..p
`an cu˙’a tiˆe´n tr`ınh xu˙’. l´
u.c
chı˙’ l`a mˆo.t phˆ
y khiˆe´n cho d˜
u. liˆe.u h˜
u.u ´ıch. Kˆe´ tiˆe´p l`a miˆeu ta˙’ (t´
ung) v`
ung du..a trˆen biˆe˙’u diˆ˜en d¯u.o..c cho.n. Chˇa˙’ng ha.n, mˆo.t
l`a t´ach c´ac d¯ˇa.c tru.ng cu˙’a v`

v`
ung c´o thˆe˙’ d¯u.o..c biˆe˙’u diˆ˜en bo˙’.i biˆen cu˙’a n´o v´o.i biˆen d¯u.o..c miˆeu ta˙’ bo˙’.i c´ac d¯ˇa.c tru.ng
nhu. d¯ˆo. d`ai biˆen, hu.´o.ng cu˙’a d¯oa.n thˇa˙’ng nˆo´i c´ac d¯iˆe˙’m cu..c tri., v`a sˆo´ c´ac cung l˜om trˆen
biˆen.
N´oi chung, cho.n biˆe˙’u diˆ˜en ngo`ai khi ta muˆo´n tˆa.p trung v`ao c´ac d¯ˇa.c tru.ng h`ınh
d´ang; v`a cho.n biˆe˙’u diˆ˜en trong khi ta muˆo´n tˆa.p trung v`ao nh˜
u.ng t´ınh chˆa´t nˆo.i ta.i cu˙’a
d¯ˆo´i tu.o..ng nhu. m`au sˇa´c v`a kˆe´t cˆa´u. Trong ca˙’ hai tru.`o.ng ho..p, c´ac d¯ˇa.c tru.ng d¯u.o..c cho.n
`an ´ıt nha.y ca˙’m nhˆa´t d¯ˆo´i v´o.i nh˜
d¯ˆe˙’ miˆeu ta˙’ cˆ
u.ng biˆe´n d¯ˆo˙’i nhu. thay d¯ˆo˙’i k´ıch thu.´o.c,
`au hˆe´t c´ac t´ınh chˆa´t
ti.nh tiˆe´n, quay. C´ac miˆeu ta˙’ trong chu.o.ng thoa˙’ m˜an mˆo.t hay hˆ
n`ay.

8.1

˜
ap biˆ
e˙’u diˆ
en
C´
ac phu.o.ng ph´

C´ac k˜
y thuˆa.t phˆan d¯oa.n trong Chu.o.ng 7 cho ta d˜
u. liˆe.u thˆo o˙’. da.ng c´ac pixel do.c theo
biˆen hoˇa.c c´ac pixel d¯u.o..c ch´
u.a trong mˆo.t v`
ung. Mˇa.c d`

u nh˜
u.ng d˜
u. liˆe.u n`ay d¯ˆoi khi
231


1

2

.....................................................................

..
......
....
...
...
...
....
..
...
....
..
....
.
...
...
...
...
...

...
..
...
...
...
...
...
..
........
..

3...

.....................................................................

0

4

..........
....
....
.....
....
....
.....
....
.....
....
....

.....
....
.....
....
.....................................................................
...
....
....
.....
.
.
.
....
....
....
....
....
.
.
.
....
....
....
......
........

5

3


(a)

2

1

..
.......
.........
....
...
.....
....
...
....
.
...
.
..
....
....
..
....
...
...
....
.
.
....
.

...
..
...
.... .......
. ..
.....................................................................
.. ....
.... ......
....
..
....
....
....
...
....
...
...
....
....
....
...
....
...
....
....
...
........
...
....
..

.......
..

6

0

7

(b)

H`ınh 8.1: C´ac hu.´o.ng su˙’. du.ng trong m˜a x´ıch 4-hu.´o.ng (a) v`a 8-hu.´o.ng (b).
d¯u.o..c su˙’. du.ng tru..c tiˆe´p d¯ˆe˙’ nhˆa.n d¯u.o..c c´ac miˆeu ta˙’ (chˇa˙’ng ha.n khi x´ac d¯.inh kˆe´t cˆa´u
ung), trong thu..c tˆe´ su˙’. du.ng phu.o.ng ph´ap biˆe˙’u diˆ˜en d˜
cu˙’a v`
u. liˆe.u da.ng th´ıch ho..p cho
`an n`ay tr`ınh b`ay mˆo.t sˆo´
ph´ep gia˙’m khˆo´i lu.o..ng t´ınh to´an khi miˆeu ta˙’ d¯ˆo´i tu.o..ng. Phˆ
phu.o.ng ph´ap biˆe˙’u diˆ˜en v`
ung.

8.1.1

M˜
a x´ıch

M˜a x´ıch d¯u.o..c su˙’. du.ng d¯ˆe˙’ biˆe˙’u diˆ˜en biˆen bˇa` ng mˆo.t d˜ay liˆen tiˆe´p c´ac d¯oa.n thˇa˙’ng (x´ac
- ˇa.c biˆe.t, biˆe˙’u diˆ˜en n`ay du..a trˆen t´ınh 4- hay 8-liˆen thˆong
d¯i.nh bo˙’.i d¯ˆo. d`ai v`a hu.´o.ng). D
cu˙’a c´ac d¯oa.n thˇa˙’ng. Hu.´o.ng cu˙’a mˆo˜i d¯oa.n thˇa˙’ng d¯u.o..c m˜a ho´a bˇ`a ng c´ach su˙’. du.ng so.

u. v`a xu˙’. l´
d¯`ˆo d¯´anh sˆo´ nhu. trong H`ınh 8.1. C´ac a˙’nh sˆo´ thu.`o.ng d¯u.o..c lu.u tr˜
y o˙’. da.ng lu.´o.i
v´o.i khoa˙’ng c´ach bˇ`a ng nhau theo c´ac hu.´o.ng x v`a y. M˜a x´ıch d¯u.o..c ta.o ra bˇ`a ng c´ach
`an theo biˆen, chˇa˙’ng ha.n theo chiˆ
`eu kim d¯ˆ
`ong hˆ
`o v`a g´an mˆo.t hu.´o.ng cho d¯oa.n nˆo´i cˇa.p
lˆ
c´ac pixel. Phu.o.ng ph´ap n`ay c´o hai nhu.o..c d¯iˆe˙’m: (1) m˜a x´ıch d¯u.o..c xˆay du..ng thu.`o.ng
rˆa´t d`ai; v`a (2) bˆa´t k`
y mˆo.t thay d¯ˆo˙’i nho˙’ do.c theo biˆen do nhiˆ˜eu hoˇa.c do phˆan d¯oa.n
khˆong tˆo´t s˜e l`am thay d¯ˆo˙’i m˜a m`a khˆong nhˆa´t thiˆe´t c´o liˆen quan d¯ˆe´n h`ınh d´ang cu˙’a
d¯u.`o.ng biˆen.
- ˆe˙’ vu.o..t qua kh´o khˇan n`ay, tru.´o.c hˆe´t ngu.`o.i ta thu.`o.ng lˆa´y mˆa˜u la.i d¯u.`o.ng biˆen
D
bˇa` ng c´ach cho.n mˆo.t lu.´o.i v´o.i khoa˙’ng c´ach l´o.n ho.n nhu. trong H`ınh 8.2(a). Sau khi
ut cu˙’a lu.´o.i l´o.n nˆe´u n´
ut
d¯u.`o.ng biˆen d¯u.o..c duyˆe.t, mˆo.t d¯iˆe˙’m biˆen d¯u.o..c g´an v´o.i mˆo˜i n´
.
.
.
.
.
.
.
.
`an v´o i d¯u `o ng biˆen c˜
n`ay gˆ

u nhu H`ınh 8.2(b). Du `o ng biˆen d¯u o. c lˆa´y mˆa˜u la.i theo c´ach
.
.
n`ay c´o thˆe˙’ d¯u o. c biˆe˙’u diˆ˜en bˇa` ng 4− hay 8−m˜a x´ıch nhu. trong c´ac H`ınh 8.2(c) v`a (d)
232


•

•

•

•

•

•

•

•

•

•

•

•

•

•
•

(a)

(b)

- u.`o.ng biˆen v`a lˆa´y mˆa˜u la.i; (b) kˆe´t qua˙’ cu˙’a lˆa´y mˆa˜u la.i; (c) m˜a x´ıch
H`ınh 8.2: (a) D
4-hu.´o.ng; (d) m˜a x´ıch 8-hu.´o.ng.
- iˆe˙’m bˇa´t d¯`ˆau trong H`ınh 8.2(c) tu.o.ng u
´.ng. D
´.ng dˆa´u chˆa´m v`a d¯u.`o.ng biˆen l`a
tu.o.ng u
4-d¯u.`o.ng d¯i bˆen ngo`ai ngˇa´n nhˆa´t trong lu.´o.i cu˙’a H`ınh 8.2(b). Biˆ˜eu diˆ˜en biˆen trong
H`ınh 8.2(c) l`a m˜a x´ıch 0033 . . . 01 v`a trong H`ınh 8.2(d) l`a m˜a x´ıch 076 . . . 12. Hiˆe˙’n
nhiˆen rˇa` ng d¯ˆo. d`ai cu˙’a m˜a x´ıch phu. thuˆo.c v`ao khoa˙’ng c´ach cu˙’a lu.´o.i lˆa´y mˆa˜u la.i.

C´
ac ph´
ep to´
an trˆ
en m˜
a x´ıch
Du.´o.i d¯ˆay l`a mˆo.t sˆo´ ph´ep to´an trˆen m˜a x´ıch d¯.inh ngh˜ıa theo 8 liˆen thˆong. Dˆ˜e d`ang mo˙’.
rˆo.ng cho 4 liˆen thˆong (b`ai tˆa.p).
−1
−1

1. [Nghi.ch d¯a˙’o] Nghi.ch d¯a˙’o cu˙’a x´ıch a = a1a2 . . . an l`a x´ıch a−1 = a−1
1 a2 . . . an
x´ac d¯.inh bo˙’.i

a−1
i = (an−i + 4) mod 8,

i = 1, 2, . . . , n.

`eu kim
`eu kim d¯ˆ
`ong hˆ
`o th`ı x´ıch nghi.ch d¯a˙’o a−1 ngu.o..c chiˆ
Nˆe´u x´ıch a thuˆa.n chiˆ
`o v`a ngu.o..c la.i.
d¯`ˆong hˆ
- ˆo. d`ai cu˙’a x´ıch a = a1a2 . . . an x´ac d¯.inh bo˙’.i
- ˆo. d`ai cu˙’a x´ıch] D
2. [D
√
l(a) := ne +

2no ,

trong d¯´o ne v`a no l`a sˆo´ c´ac gi´a tri. chˇa˜n v`a le˙’ tu.o.ng u
´.ng trong d˜ay a1 , a2, . . . an .
Gia˙’ su˙’. d¯iˆe˙’m xuˆa´t ph´at cu˙’a x´ıch a ta.i pixel (x0, y0 ). Khi d¯´o to.a d¯ˆo. cu˙’a pixel
233



tu.o.ng u
´.ng mˇa´t x´ıch ai trong x´ıch a l`a
i

xi =

ajx + x0,
j=1
i

yi =

ajy + y0,
j=1

`an cu˙’a vector ai . (Chˇa˙’ng
trong d¯´o k´
y hiˆe.u ajx v`a ajy tu.o.ng u
´.ng l`a c´ac th`anh phˆ
ha.n ai = 3 th`ı ajx = −1, ajy = 1).
- ˆo. rˆo.ng v`a d¯ˆo. cao cu˙’a chu tuyˆe´n d¯´ong] D
- ˆo. rˆo.ng w(a) v`a d¯ˆo. cao h(a) cu˙’a chu
3. [D
tuyˆe´n d¯´ong x´ac d¯i.nh bo˙’.i x´ıch a l`a
w(a) = max xj − min xj ,
j

j

h(a) = max yj − min yj .

j

j

`en
4. [Khoa˙’ng c´ach gi˜
u.a hai d¯iˆe˙’m] X´et hai pixel p v`a q d¯u.o..c nˆo´i bo˙’.i mˆo.t dˆay chuyˆ
´.ng m˜a x´ıch a. Khi d¯´o khoa˙’ng c´ach (Euclid) gi˜
u.a hai pixel n`ay l`a
µ tu.o.ng u


d(p, q) = 

2

n

ajx
j=1

2

n

+

ajy
j=1


2

 .

Nˆe´u biˆe´t tˆa´t ca˙’ c´ac to.a d¯ˆo. cu˙’a c´ac pixel trˆen chu tuyˆe´n ta c´o thˆe˙’ t´ınh d¯u.o..c
moment cu˙’a chu tuyˆe´n. Tuy nhiˆen m˜a x´ıch cu˙’a chu tuyˆe´n d¯´ong khˆong cho thˆong
`e v`
tin h`ınh ho.c vˆ
ung d¯u.o..c gi´o.i ha.n bo˙’.i d¯u.`o.ng biˆen l`a chu tuyˆe´n n`ay. Ngo`ai ra
c˜
ung kh´o c´o thˆe˙’ thu..c hiˆe.n d¯ˆo´i v´o.i c´ac ph´ep to´an co gi˜an.
ung ta c´o
M˜a x´ıch cu˙’a d¯u.`o.ng biˆen phu. thuˆo.c v`ao d¯iˆe˙’m xuˆa´t ph´at. Tuy nhiˆen ch´
thˆe˙’ chuˆa˙’n ho´a bˇa` ng thu˙’ tu.c sau: V´o.i mˆo.t m˜a x´ıch c´o d¯iˆe˙’m xuˆa´t ph´at tu`
yy
´, ta xem
.
.
.
.
.
.
.
`om c´ac sˆo´ tu o ng u
m˜a n`ay nhu mˆo.t d˜ay kh´ep k´ın gˆ
´ ng v´o i hu ´o ng di chuyˆe˙’n v`a d¯i.nh
´.ng mˆo.t sˆo´ nguyˆen c´o gi´a tri.
ngh˜ıa la.i d¯iˆe˙’m xuˆa´t ph´at sao cho d˜ay thu d¯u.o..c tu.o.ng u
nho˙’ nhˆa´t.
Ch´

ung ta c˜
ung c´o thˆe˙’ chuˆa˙’n ho´a d¯ˆo´i v´o.i ph´ep quay bˇ`a ng c´ach su˙’. du.ng hiˆe.u th´
u.
nhˆa´t cu˙’a m˜a x´ıch thay cho m˜a ban d¯`ˆau. Hiˆe.u n`ay nhˆa.n d¯u.o..c bˇ`a ng c´ach d¯ˆe´m (ngu.o..c
`eu kim d¯ˆ
`ong hˆ
`o) sˆo´ c´ac hu.´o.ng t´ach hai phˆ
`an tu˙’. kˆ
`e nhau cu˙’a m˜a. Chˇa˙’ng ha.n, hiˆe.u
chiˆ
.
.
ung ta xem m˜a nhu. d˜ay
d¯`ˆau tiˆen cu˙’a m˜a x´ıch 4-hu ´o ng 10103322 l`a 3133030. Nˆe´u ch´
`an tu˙’. d¯`ˆau tiˆen cu˙’a hiˆe.u ch´ınh l`a sˆo´ lˆ
`an chuyˆe˙’n di.ch cu˙’a c´ac th`anh
kh´ep k´ın, th`ı phˆ
`an d¯ˆ
`au tiˆen v`a cuˆo´i c`
phˆ
ung cu˙’a x´ıch. Do d¯´o kˆe´t qua˙’ l`a 33133030. K´ıch thu.´o.c cu˙’a
234


x´ıch chuˆa˙’n ho´a phu. thuˆo.c v`ao k´ıch thu.´o.c trong qu´a tr`ınh lˆa´y mˆa˜u. Tˆo˙’ng qu´at, gia˙’ su˙’.
a = a1a2 . . . an l`a m˜a x´ıch theo d−liˆen thˆong (d = 4 hoˇa.c 8) v`a b = b1 b2 . . . bn l`a hiˆe.u
d¯`ˆau tiˆen cu˙’a m˜a x´ıch a. Khi d¯´o
b1 = an − a1

(mod d),


bi = ai − ai−1 (mod d), i = 2, 3, . . . , n.
C´ac chuˆa˙’n n`ay chı˙’ ch´ınh x´ac nˆe´u c´ac d¯u.`o.ng biˆen bˆa´t biˆe´n v´o.i c´ac thay d¯ˆo˙’i cu˙’a
`eu n`ay hiˆe´m xa˙’y ra trong thu..c tˆe´. Chˇa˙’ng ha.n, c`
ph´ep quay v`a co gi˜an. Nhu.ng d¯iˆ
ung
mˆo.t d¯oˆ´i tu.o..ng d¯u.o..c sˆo´ ho´a theo hai hu.´o.ng kh´ac nhau s˜e ta.o ra c´ac h`ınh da.ng kh´ac
nhau, v´o.i m´
u.c d¯ˆo. sai kh´ac tı˙’ lˆe. v´o.i d¯ˆo. phˆan gia˙’i cu˙’a a˙’nh.

8.1.2

Xˆ
a´p xı˙’ d
¯a gi´
ac

Mˆo.t d¯u.`o.ng biˆen sˆo´ c´o thˆe˙’ xˆa´p xı˙’ bo˙’.i mˆo.t d¯a gi´ac v´o.i d¯ˆo. ch´ınh x´ac t`
uy y
´. V´o.i mˆo.t
d¯u.`o.ng cong d¯´ong, xˆa´p xı˙’ l`a ch´ınh x´ac khi sˆo´ c´ac ca.nh trong d¯a gi´ac bˇ`a ng sˆo´ c´ac d¯iˆe˙’m
`e nhau x´ac d¯i.nh mˆo.t ca.nh trong d¯a gi´ac. Trong thu..c tˆe´,
biˆen trong d¯´o mˆo˜i cˇa.p pixel kˆ
mu.c d¯´ıch cu˙’a xˆa´p xı˙’ d¯a gi´ac l`a gi˜
u. la.i d´ang d¯iˆe.u cu˙’a d¯u.`o.ng biˆen v´o.i sˆo´ ca.nh d¯a gi´ac ´ıt
`eu th`o.i gian thu..c
`am thu.`o.ng v`a c´o thˆe˙’ tˆo´n nhiˆ
nhˆa´t. B`ai to´an n`ay, n´oi chung, khˆong tˆ
hiˆe.n viˆe.c t`ım kiˆe´m. Tuy nhiˆen, phu.o.ng ph´ap biˆe˙’u diˆ˜en biˆen bˇa` ng c´ach xˆa´p xı˙’ d¯a gi´ac
ph`

u ho..p v´o.i mˆo.t sˆo´ u
´.ng du.ng trong xu˙’. l´
y a˙’nh.
u.ng tiˆeu chuˆa˙’n kh´ac
C´ac phu.o.ng ph´ap ho..p du..a trˆen tiˆeu chuˆa˙’n sai sˆo´ hay nh˜
d¯u.o..c ´ap du.ng v´o.i b`ai to´an xˆa´p xı˙’ d¯a gi´ac. Ch´
ung ta c´o thˆe˙’ ho..p c´ac d¯iˆe˙’m do.c theo
biˆen cho d¯ˆe´n khi d¯u.`o.ng thˇa˙’ng kh´o.p c´ac d¯iˆe˙’m d¯u.o..c ho..p v´o.i sai sˆo´ b`ınh phu.o.ng nho˙’
`eu kiˆe.n n`ay thoa˙’ m˜an, c´ac tham sˆo´ cu˙’a
nhˆa´t vu.o..t qu´a mˆo.t ngu.˜o.ng cho tru.´o.c. Khi d¯iˆ
`e 0, v`a thuˆa.t to´an d¯u.o..c lˇa.p la.i, ho..p c´ac d¯iˆe˙’m
d¯u.`o.ng thˇa˙’ng d¯u.o..c lu.u tr˜
u., sai sˆo´ d¯ˇa.t vˆ
m´o.i do.c theo biˆen cho d¯ˆe´n khi lˆo˜i la.i vu.o..t qu´a ngu.˜o.ng cho ph´ep. Kˆe´t th´
uc thuˆa.t
to´an, giao cu˙’a c´ac d¯u.`o.ng thˇa˙’ng sinh ra c´ac d¯ı˙’nh cu˙’a d¯a gi´ac. Kh´o khˇan ch´ınh cu˙’a
thuˆa.t to´an n`ay l`a c´ac d¯ı˙’nh n´oi chung khˆong tu.o.ng u
´.ng v´o.i nh˜
u.ng chˆo˜ uˆo´n (chˇa˙’ng ha.n
c´ac g´oc) cu˙’a biˆen do mˆo.t d¯u.`o.ng thˇa˙’ng m´o.i chı˙’ d¯u.o..c kho˙’.i ta.o khi sai sˆo´ vu.o..t gi´a tri.
ngu.˜o.ng. Nˆe´u chˇa˙’ng ha.n, mˆo.t d¯oa.n thˇa˙’ng d`ai d¯i ngang qua g´oc, mˆo.t sˆo´ (phu. thuˆo.c
v`ao ngu.˜o.ng) d¯iˆe˙’m qua g´oc s˜e d¯u.o..c ch´
uy
´ tru.´o.c khi sai sˆo´ vu.o..t ngu.˜o.ng. Tuy nhiˆen,
viˆe.c t´ach c`
ung v´o.i ho..p c´o thˆe˙’ gia˙’i quyˆe´t kh´o khˇan n`ay.
`an cho d¯ˆe´n
Phu.o.ng ph´ap t´ach d¯oa.n biˆen l`a chia mˆo.t d¯oa.n liˆen tiˆe´p th`anh hai phˆ
.
.

khi thoa˙’ tiˆeu chuˆa˙’n cho tru ´o c. V´ı du., ta c´o thˆe˙’ d¯`oi ho˙’i khoa˙’ng c´ach t`
u. mo.i d¯iˆe˙’m
235