®¹i häc B¸ch khoa Hanoi<br />
<br />
Khoa C«ng nghÖ th«ng tin<br />
<br />
Ch−¬ng 4<br />
<br />
C¸c Ph−¬ng ph¸p c¬ së xö lý sè h×nh ¶nh<br />
1. Giíi thiÖu chung vÒ c¸c ph−¬ng ph¸p xö lý sè h×nh ¶nh<br />
2. C¸c phÐp to¸n ®iÓm ¶nh (Points Operations)<br />
• Histogram : BiÓu ®å ph©n bè møc x¸m, biÓu ®å cét x¸m : h i = ni<br />
MN<br />
<br />
pour 0 ≤ i ≤ L<br />
<br />
• PhÐp to¸n ®iÓm ¶nh<br />
- C«ng thøc chung cña c¸c phÐp to¸n ®iÓm ¶nh :<br />
<br />
Y (m, n) = f (X (m, n)), ∀m ∈[1, M ], n ∈[1, N ]<br />
trong ®ã f(X(m,n)) lµ hµm to¸n häc cã thÓ lµ :<br />
liªn tôc/ rêi r¹c, tuyÕn tÝnh/ phi tuyÕn, hµm sè, , hµm ng−ìng, hµm logic ....<br />
<br />
- Kü thuËt thùc hiÖn c¸c phÐp to¸n ®iÓm ¶nh : LUT (Look-Up-Table)<br />
<br />
3. C¸c to¸n tö tuyÕn tÝnh kh«ng gian, nh©n chËp vµ xÕp chång<br />
M N<br />
To¸n tö tuyÕn tÝnh - To¸n tö Kernel : Y (k ,l ) = ∑ ∑ X (m, n).ϕ (m, n; k , l ) , k ∈ [1, K ], l ∈ [1, L]<br />
m=1n=1<br />
<br />
ϕ (m, n; k ,l ) lµ c¸c hÖ sè cña to¸n tö Kernel phô thuéc vµo 4 biÕn (m,n ; k, l).<br />
• PhÐp to¸n nh©n chËp hai chiÒu (Bi-dimension Convolution)<br />
Xö lý ¶nh<br />
<br />
NguyÔn ThÞ Hoµng Lan<br />
<br />
®¹i häc B¸ch khoa Hanoi<br />
<br />
Khoa C«ng nghÖ th«ng tin<br />
<br />
- §Þnh nghÜa phÐp nh©n chËp ®èi víi 2 hµm hai biÕn liªn tôc :<br />
∞ ∞<br />
g ( x, y = f ( x, y ) ∗ h( x, y ) = ∫ ∫ f (α,β)h( x − α, y − β)dαdβ<br />
−∞ −∞<br />
- PhÐp nh©n chËp ®èi víi hµm rêi r¹c (tÝn hiÖu sè):<br />
∞<br />
∞<br />
g ( x, y ) = f*h = ∑<br />
∑ f ( x − k , y − l )h ( k , l )<br />
k =−∞ l =−∞<br />
<br />
K<br />
<br />
g ( x, y ) = ∑<br />
<br />
L<br />
<br />
∑ f ( x − k , y − l )h ( k , l )<br />
<br />
k =− K l =− L<br />
<br />
- C¸c tÝnh chÊt cña phÐp nh©n chËp<br />
<br />
• PhÐp to¸n nh©n chËp ¸p dông cho ¶nh sè :<br />
- C«ng thóc c¬ b¶n :<br />
<br />
L−1 L −1<br />
<br />
Y (m, n) = X (m, n) ∗ H (k , l ) = ∑ ∑ h(k , l ) X (m − k , n − l )<br />
k =0 l =0<br />
<br />
C«ng thøc th−êng dïng :<br />
r<br />
r<br />
Y (m, n) = X (m, n) ∗ H (k , l ) = ∑ ∑ h(k , l ) X (m − k , n − l )<br />
k =− r l =− r<br />
<br />
X(m, n) lµ ¶nh kÝch th−íc(M,N) vµ H(k,l) est lµ ma trËn h¹t nh©n hay cßn gäi lµ mÆt n¹<br />
Y(m,n) lµ ¶nh kÕt qu¶ cña phÐp nh©n chËp gi÷a ¶nh X vµ H.<br />
<br />
Xö lý ¶nh<br />
<br />
NguyÔn ThÞ Hoµng Lan<br />
<br />
®¹i häc B¸ch khoa Hanoi<br />
<br />
Khoa C«ng nghÖ th«ng tin<br />
<br />
- Nh©n chËp vµ xÕp chång<br />
n<br />
<br />
1<br />
<br />
N<br />
<br />
1<br />
<br />
m<br />
<br />
i<br />
f<br />
<br />
h<br />
<br />
g<br />
<br />
e<br />
<br />
d<br />
<br />
c<br />
<br />
b<br />
<br />
a<br />
<br />
*<br />
<br />
a<br />
<br />
b<br />
<br />
c<br />
<br />
d<br />
<br />
e<br />
<br />
f<br />
<br />
g<br />
<br />
h<br />
<br />
i<br />
<br />
H(k l)<br />
N<br />
X(m,n)<br />
<br />
Y(m,n)<br />
<br />
4. C¸c phÐp läc ¶nh (Image Filtering)<br />
• Kh¸i qu¸t vÒ phÐp läc ¶nh : läc tuyÕn tÝnh (läc sè), läc phi tuyÕn<br />
• C¸c bé läc sè (Digital Filters) ®èi víi ¶nh sè<br />
- M« h×nh chung - ®Þnh nghÜa vÒ c¸c bé läc sè : Y(m, n) = X(m, n)*H(k, l)<br />
X(m,n)<br />
<br />
H(k,l)<br />
H(u,v)<br />
H(z1,z2)<br />
<br />
Y(m,n)<br />
<br />
H(k,l) lµ ®¸p øng xung cña bé läc<br />
Xö lý ¶nh<br />
<br />
NguyÔn ThÞ Hoµng Lan<br />
<br />
®¹i häc B¸ch khoa Hanoi<br />
<br />
Khoa C«ng nghÖ th«ng tin<br />
<br />
- C¸c d¹ng biÓu diÔn c¸c bé läc sè : H(k, l), H(u, v), H(z1, z2)<br />
- Ph©n lo¹i c¸c bé läc sè : ph©n lo¹i theo ®¸p øng xung, 2 lo¹i : FIR vµ IIR<br />
- Bé läc cã ®¸p øng xung h÷u h¹n FIR<br />
K L<br />
H ( z1, z 2) = ∑ ∑ bkl z1−k z 2−l<br />
k =0 l = 0<br />
<br />
r<br />
<br />
r<br />
<br />
Y (m, n) = X (m, n) ∗ H (k , l ) = ∑ ∑ h(k , l ) X (m − k , n − l ) avec 2r +1 = L = K<br />
k =− r l =− r<br />
<br />
⎡1 1 1 ⎤<br />
⎥<br />
⎢<br />
1 ⎢<br />
⎥<br />
H (k , l ) = ⎢1 2 1⎥<br />
10<br />
⎥<br />
⎢<br />
⎢1 1 1 ⎥<br />
⎦<br />
⎣<br />
<br />
⎡1<br />
⎢<br />
1 ⎢<br />
H ( k , l ) = ⎢2<br />
16<br />
⎢<br />
⎢⎣1<br />
<br />
- Bé läc cã ®¸p øng xung v« h¹n IIR<br />
H ( z 1 , z 2) =<br />
<br />
− p −q<br />
∑ a pq z1 z 2<br />
<br />
q =0<br />
p + q ≠0<br />
P<br />
<br />
Y (m, n) = ∑ ∑ b(k , l ).X (m − k , n − l ) − ∑<br />
k =0 l =0<br />
<br />
1⎤<br />
⎥<br />
⎥<br />
1⎥<br />
⎥<br />
1⎥<br />
⎦<br />
<br />
k =0 l =0<br />
Q<br />
P<br />
<br />
p =0<br />
<br />
L<br />
<br />
⎡1 1<br />
⎢<br />
⎢<br />
H (k , l ) = ⎢1 − 9<br />
⎢<br />
⎢1 1<br />
⎣<br />
<br />
K L<br />
− k −l<br />
∑ ∑ bkl z1 z 2<br />
<br />
∑<br />
<br />
K<br />
<br />
⎡<br />
⎤<br />
⎢0 − 1 0 ⎥<br />
⎢<br />
⎥<br />
H (k , l ) = ⎢− 1 − 4 − 1⎥<br />
⎢<br />
⎥<br />
⎢0 − 1 0 ⎥<br />
⎢⎣<br />
⎥⎦<br />
<br />
1 ⎤⎥<br />
⎥<br />
4 2⎥<br />
⎥<br />
2 1⎥<br />
⎦<br />
2<br />
<br />
p =0<br />
<br />
Q<br />
<br />
∑ a( p, q).Y (m − p, n − q)<br />
q =0<br />
p + q ≠0<br />
<br />
Xö lý ¶nh<br />
<br />
NguyÔn ThÞ Hoµng Lan<br />
<br />
®¹i häc B¸ch khoa Hanoi<br />
<br />
Khoa C«ng nghÖ th«ng tin<br />
<br />
5. C¸c phÐp biÕn ®æi ¶nh (Image Transforms)<br />
•<br />
-<br />
<br />
C¸c phÐp biÕn ®æi tuyÕn tÝnh ®¬n vÞ<br />
Kh¸i niÖm vÒ c¸c phÐp biÕn ®æi ¶nh, phÐp biÕn ®æi tuyÕn tÝnh / phi tuyÕn<br />
PhÐp biÕn ®æi ®¬n vÞ (unitary transform), ma trËn cña phÐp biÕn ®æi, ma trËn c¬ së<br />
C¸c phÐp biÕn ®æi ®¬n vÞ : PhÐp biÕn ®æi Fourier, phÐp biÕn ®æi cosine, sine, Hartley,<br />
Hadamard, Haar, Slant, Karhunen Loeve (KL).<br />
- TÝnh chÊt cña c¸c phÐp biÕn ®æi ®¬n vÞ : b¶o toµn n¨ng l−îng, tËp trung n¨ng l−îng, gi¶i<br />
t−¬ng quan<br />
<br />
• PhÐp biÕn ®æi Fourier<br />
<br />
- §Þnh nghÜa phÐp biÕn ®æi Fourier vµ phÐp biÕn ®æi Fourier rêi r¹c ¸p dông cho ¶nh (DFT)<br />
M −1N −1<br />
⎛<br />
⎞<br />
X (u, v) = ∑ ∑ X (m, n) exp⎜⎜ − j2π⎛⎜ um + vn ⎞⎟ ⎟⎟<br />
M N<br />
m =0 n =0<br />
<br />
⎝<br />
<br />
⎝<br />
<br />
⎠⎠<br />
<br />
M −1N −1<br />
⎛<br />
⎞<br />
X (m, n) = 1 ∑ ∑ X (u, v) exp⎜⎜ j 2π ⎛⎜ um + vn ⎞⎟ ⎟⎟<br />
MN u =0 v =0<br />
N ⎠⎠<br />
⎝M<br />
⎝<br />
<br />
- TÝnh chÊt cña phÐp biÕn ®æi Fourier<br />
- ý nghÜa phÐp biÕn ®æi Fourier vµ phæ cña ¶nh : phæ biÕn biªn ®é, phæ n¨ng l−îng, phæ pha<br />
- BiÓu diÔn phæ cña ¶nh vµ ý nghÜa cña phæ trong xö lý ¶nh<br />
- §é phøc t¹p cña phÐp biÕn ®æi Fourier DFTvµ thuËt to¸n biÕn ®æi Fourier nhanh FFT :<br />
§é phøc t¹p O(N4). PhÐp ®æi ph©n t¸ch ®−îc. §iÒu kiÖn cña FFT. §é phøc t¹p cña FFT.<br />
Xö lý ¶nh<br />
<br />
NguyÔn ThÞ Hoµng Lan<br />
<br />