Xử lý ảnh số - Các phép biến đổi part 4

Chia sẻ: Adfgajdshd Asjdaksdak | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

88
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Toàn bộ file được ghi ra DVD cho khách hàng. 1 CD-ROM chứa file JPEG cho nhỏ để dễ sử dụng. Bởi tôi cho phép khách hàng toàn quyền sử dụng hình ảnh của họ, nên chẳng cần thiết phải để chữ ký (watermark) làm gì. Tôi sử dụng phần mềm iPhoto để tạo slide phim với nhạc. khoảng 100 hình với nhạc mà tôi được phép sử dụng hạn chế.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Xử lý ảnh số - Các phép biến đổi part 4

Phu.o.ng tr`nh (3.14) c˜ng c´ thˆ’ khai triˆ’n nhu. sau ˙ ˙ ı u oe e M −1 ux G(x, 0)e−2πi M , F (u, 0) = x=0 M −1 ux G(x, 1)e−2πi M , F (u, 1) = x=0 . . . M −1 ux G(x, N − 1)e−2πi M . F (u, N − 1) = x=0 C´c phu.o.ng tr`nh trˆn d u.a dˆn thu tuc FFT hai chiˆu: ´ ` ˙. ’ a ı e¯ ¯e e Bu.´.c 1. Biˆn d o’i FFT 1D mˆi h`ng v` lu.u tr˜. v`o mang trung gian. ˙ ˜ ´ ˙ ’ o e ¯ˆ oa a ua Bu.´.c 2. Chuyˆ’n vi mang trung gian. ˙ e.˙ ’ o Bu.´.c 3. Biˆn d o’i FFT 1D mˆi h`ng cua mang trung gian. Kˆt qua cuˆi c`ng l` ˙ ˜ ´ ´ ´ ˙ ’ ˙ ’ ˙ ou ’ o e ¯ˆ oa e a chuyˆ’n vi cua mang FFT 2D. ˙ e .˙ ’ ˙ ’ Ch´ng ta c˜ng c´ thˆ’ viˆt lai (3.14) nhu. sau ˙´ u u oee. N −1 M −1 1 vy ux f (x, y )e−2πi M e−2πi N . F (u, v ) = (3.16) MN y =0 x=0 -a Dˇt . M −1 1 ux f (x, y )e−2πi M . G(u, y ) := M x=0 Th` ı N −1 1 vy G(u, y )e−2πi N . F (u, v ) = N y =0 Diˆu n`y d .a d e n thu tuc FFT hai chiˆu: -` ´ ` ˙. ’ e a ¯u ¯ˆ e Bu.´.c 1. Chuyˆ’n vi tˆp tin anh. ˙ ˙ ’ o e .a . Bu.´.c 2. Biˆn d o’i FFT 1D mˆi h`ng cua anh d .o.c chuyˆ’n vi v` lu.u tr˜. v`o mang ˙ ˙ ˜ ´ ˙˙ ’’ ˙ ’ o e ¯ˆ oa ¯u . e .a ua trung gian. Bu.´.c 3. Chuyˆ’n vi mang trung gian. ˙ e.˙ ’ o Bu.´.c 4. Biˆn d o’i FFT 1D mˆi h`ng cua mang trung gian. Kˆt qua l` FFT 2D. ˙ ˜ ´ ´ ˙ ’ ˙ ’ ˙a ’ o e ¯ˆ oa e 58
Biˆn d ˆ’i FFT ngu.o.c ˙ ´ 3.4.2 e ¯o . Thuˆt to´n biˆn d o’i thuˆn c´ thˆ’ cai biˆn d e’ nhˆn d .o.c biˆn d o’i ngu.o.c. Thˆt vˆy, ˙ ˙ ’ e ¯ˆ a ¯u . ˙. ˙ ´ ´ a o e˙ a a e ¯ˆ e ¯ˆ aa . . . .. .p ph´.c hai vˆ v` chia cho N cua ´ ´ ˙ ’ lˆ y liˆn ho ae u ea . N −1 ux F (u)e2πi N f ( x) = u=0 ta d .o.c ¯u . N −1 1¯ 1 ux ¯ F (u)e−2πi N . f ( x) = (3.17) N N u=0 So s´nh v´.i a o N −1 1 ux f (x)e−2πi N F ( u) = N x=0 ta thˆ y vˆ phai cua (3.17) c´ dang cua ph´p biˆn d o’i Fourier thuˆn. Do d ´ su. dung ˙ ´´˙˙ ´ ’’ ˙ ’ ¯o ˙ . ’ ae o. e e ¯ˆ a . thuˆt to´n n`y v´.i d˜. liˆu nhˆp l` F (u) dˆ’ t´nh f (x)/N. T`. d ´ dˆ d`ng suy ra f (x). ¯ a a¯ ˙ u ¯o ˜ a a a a oue ¯e ı e . . . Tu.o.ng tu. cho 2D, t`. (3.4) dˆ d`ng suy ra ˜a u e . M −1 N −1 1¯ 1 vy ux F (u, v )e−2πi( M + N ) . ¯ f (x, y ) = MN MN u=0 v =0 Biˆ’u th´.c bˆn vˆ phai c´ dang biˆn d o’i Fourier 2D thuˆn. Do d o nhˆp F (u, v ) v` a¯ ˙ ˙ ´ ´ ˙o. ’ e uee e ¯ˆ a ¯´ a . . . d ´ suy ra f (x, y ). Ch´ y rˇ ng, 1¯ d`ng thuˆt to´n biˆn d o’i thuˆn ta c´ M N f (x, y ). T` ¯o ˙ ` ´ u a a e ¯ˆ a o u u´ a . . nˆu f thu.c th` ph´p to´n liˆn ho.p ph´.c l` khˆng cˆn thiˆt. ´ ` ´ e ıe ae uao a e . . Nhˆn x´t 3.4.1 Thuˆt to´n FFT 2D d .o.c tr`nh b`y trˆn liˆn quan dˆn b`i to´n ´a a e a a ¯u . ı a e e ¯e a . . - ˆ’ giam b´.t th`.i gian thu.c hiˆn trong tiˆn tr`nh n`y, ch´ng ta c´ chuyˆ’n vi ma trˆn. De ˙ ˙ ˙’ ´ e. a o o e e ı a u o . . . . dung phu.o.ng ph´p chuyˆ’n vi ma trˆn cua Eklundh (xem [19]). thˆ’ su . ˙’ ˙ e˙ ˙ ’ a e. a . C´c ph´p biˆn d o’i kh´c ˙ ´ 3.5 a e e ¯ˆ a Biˆn d o’i Fourier mˆt chiˆu l` mˆt trong nh˜.ng ph´p biˆn d o’i c´ dang ˙ ˙ ´ `ao ´ e ¯ˆ o e u e e ¯ˆ o . . . N −1 T (u) := f (x)g (x, u), x=0 59
trong d ´ T (u) l` ph´p biˆn d o’i, g (x, u) l` hat nhˆn biˆn d o’i thuˆn v` gi´ tri u thay ˙ ˙ ´ ´ ¯o ae e ¯ˆ a. a e ¯ˆ aaa. . .o.ng tu., ph´p biˆn d o’i ngu.o.c d ˆ’i trong pham vi {0, 1, . . . , N − 1}. Tu ˙ ˙ ´ ¯ˆ ¯o e e . . . N −1 f ( x) = T (u)h(x, u), u=0 trong d o h(x, u) l` hat nhˆn biˆn d ˆ’i ngu.o.c v` gi´ tri x thay d ˆ’i trong pham vi ˙ ˙ ´ ¯´ a. a e ¯o aa. ¯o . . {0, 1, . . . , N − 1}. C´c t´ chˆ t cua hat nhˆn biˆn d o’i x´c d .nh t´nh chˆ t cua ph´p ˙ ´’ ´ ´’ a ınh a ˙ a˙ a e ¯ˆ a ¯i ı e . biˆn d o’i. ˙ ´ e ¯ˆ Cˇp biˆn d o’i hai chiˆu r`.i rac thuˆn v` ngu.o.c tˆ’ng qu´t c´ dang ˙ ˙ ´ `o. a e ¯ˆ e aa .o ao. . .  N −1 N −1    T (u, v ) :=  f (x, y )g (x, y, u, v ),   x=0 y =0 (3.18)  N −1 N −1    f (x, y ) :=  T (u, v )h(x, y, u, v ),  u=0 v =0 trong d ´ g, h d u.o.c goi l` c´c hat nhˆn biˆn d o’i thuˆn v` ngu.o.c. C´c hat nhˆn n`y ˙ ´ ¯o ¯. .aa . a e ¯ˆ aa a. aa . . ˙’. chı phu thuˆc v`o x, y, u, v, m` khˆng phu thuˆc v`o f v` T. oa ao oa a . . . Hat nhˆn biˆn d o’i thuˆn l` t´ch d .o.c nˆu ta c´ thˆ’ viˆt ˙ ˙´ ´ ´ a e ¯ˆ a a a ¯u . e oee . . g (x, y, u, v ) = g1 (x, u)g2(y, v ). Hat nhˆn biˆn d ˆ’i thuˆn t´ch d .o.c goi l` d ˆi x´.ng nˆu g1 ≡ g2 . Tu.o.ng tu. ta c˜ng c´ ˙ ´ ´ ´ a e ¯o a a ¯u . . a ¯o u e u o . . . .o.c, d ˆi x´.ng cho hat nhˆn biˆn d o’i ngu.o.c. ˙ ´ ´ c´c kh´i niˆm t´ch d . ¯o u a ae a ¯u a e ¯ˆ . . . Biˆn d o’i Fourier 2D l` tru.`.ng ho.p d ac biˆt c´ hat nhˆn biˆn d o’i ˙ ˙ ´ ´ e ¯ˆ a o . ¯ˇ eo. a e ¯ˆ . . 1 −2πi( ux + vy ) g (x, y, u, v ) := e N N NN t´ch d u.o.c v` d oi x´.ng. (Hat nhˆn biˆn d o’i Fourier 2D ngu.o.c c˜ng t´ch d .o.c v` d ˆi ˙ ´ ´ ´ a ¯ . a ¯ˆ u a e ¯ˆ .u a ¯u . a ¯o . x´.ng). u Ph´p biˆn d o’i v´.i nhˆn t´ch d .o.c c´ thˆ’ d u.o.c t´nh thˆng qua hai bu.´.c, mˆi ˙ ˙ ˜ ´ e e ¯ˆ o a a ¯u . o e ¯ . ı o o o bu.´.c su. dung ph´p biˆn d o’i 1D nhu. d u.o.c chı ra du.´.i d ay. ˙ ´ o˙. ’ ˙ ’ e e ¯ˆ ¯. o ¯ˆ Thuˆt to´n a a . Bu.´.c 1. D` u tiˆn biˆn d o’i 1D doc theo mˆi h`ng cua anh f : -ˆ ˙ ˜ ´ ˙˙ ’’ o a e e ¯ˆ oa . N −1 T (x, v ) := f (x, y )g2 (y, v ), y =0 v´.i x = 0, 1, . . . , N − 1, v = 0, 1, . . . , N − 1. o 60
Bu.´.c 2. Kˆ tiˆp, lˆ y biˆn d o’i 1D doc theo mˆi cˆt cua T (x, v ) (d ˜ d .o.c t´nh theo ˙ ˜. ´´ ´ ´ oo˙ ’ o ee a e ¯ˆ ¯a ¯u . ı . .´.c 1): Bu o N −1 T (u, v ) := T (x, v )g1(x, u), x=0 v´.i u = 0, 1, . . . , N − 1, v = 0, 1, . . . , N − 1. o Ta c˜ng c´ thˆ’ x´c d .nh T (u, v ) bˇ ng c´ch: (1) biˆn d o’i mˆi cˆt cua f dˆ’ nhˆn ˙ ˙˜.’ ˙. ` ´ e ¯ˆ o o ˙ u o e a ¯i a a ¯e a d u.o.c T (y, u); (2) sau d o biˆn d o’i doc theo mˆi h`ng. Tu.o.ng tu. cho biˆn d o’i ngu.o.c ˙ ˙ ˜ ´ ´ ¯. ¯´ e ¯ˆ . oa e ¯ˆ . . nˆu h t´ch d u.o.c. ´ e a ¯. Nˆu hat nhˆn g t´ch d u.o.c v` d ˆi x´.ng, th` (3.18) c´ thˆ’ viˆt lai du.´.i dang ma ˙´ ´. ´ e a a ¯ . a ¯o u ı oee. o. trˆn a . T = AfA, (3.19) trong d ´ f l` ma trˆn anh N × N ; A := (aij ) l` ma trˆn biˆn d ˆ’i d ˆi x´.ng cˆ p N × N, ˙´ ´ ´ a˙ .’ ¯o a a a e ¯o ¯o u a . v´.i aij := g1 (i, j ); v` T l` ma trˆn kˆt qua. ´ ˙ ’ o a a ae . Dˆ’ c´ biˆn d o’i ngu.o.c, nhˆn tru.´.c v` sau (3.19) v´.i ma trˆn biˆn d o’i ngu.o.c B, - e o e ¯ˆ ˙ ˙ ˙ ´ ´ a oa o a e ¯ˆ . . . .o.c ta d . ¯u BT B = BAF AB. (3.20) Nˆu B = A−1 , th` ´ e ı f = BT B (3.21) cho biˆt anh sˆ f c´ thˆ’ khˆi phuc ho`n to`n t`. biˆn d o’i n`y. Nˆu B = A−1 , ta d`ng ˙ ˙ ´’ ´ ´ ´ e˙ o oeo a a u e ¯ˆ a e u . (3.20) dˆ’ c´ mˆt xˆ p xı v´.i f : ˙ .´’ ¯e o o a ˙ o ˆ f = BAf AB. Nhiˆu loai biˆn d ˆ’i (Fourier, Walsh, Hadamard, cosin r`.i rac, Haar, Slant) c´ thˆ’ biˆ’u ˙ ˙˙ ` ´ e e ¯o o. oee . diˆn du.´.i dang (3.19) v` (3.21). Mˆt t´nh chˆ t quan trong cua c´c ma trˆn biˆn d o’i ˙ ˜ ´ ´ ˙a ’ e o. a oı a a e ¯ˆ . . . l` ch´ng c´ thˆ’ t´ch d u.o.c th`nh t´ c´c ma trˆn v´.i ´t phˆn tu. kh´c khˆng ho.n ma ˙ ` a˙ ’ au o ea ¯. a ıch a a oı a o . trˆn gˆc. Kˆt qua n`y l`m giam d o du. th`.a v` sˆ ph´p t´ cˆn thiˆt cho biˆn d o’i ˙ ´ ´ u a o e ınh ` ´ ´ ´ ˙aa ’ ˙ ¯ˆ ’ ao e a e e ¯ˆ . . 2D. Biˆn d ˆ’i Walsh ˙ ´ 3.5.1 e ¯o Gia su. N = 2n , n ∈ N. Biˆn d o’i Walsh cua h`m r`.i rac f (x, y ) c´ hat nhˆn biˆn d o’i ˙ ˙ ´ ´ ˙˙ ’’ ˙a ’ e ¯ˆ o. o. a e ¯ˆ .o.c cho bo.i ˙ ’ thuˆn ngu . a . 61
 n −1   g (x, y, u, v ) := 1 (−1)[bi (x)bn−1−i (u)+bi (y)bn−1−i (v)] ,    N i=0  n −1   h(x, y, u, v ) := 1  (−1)[bi (x)bn−1−i (u)+bi (y)bn−1−i (v)] ,  N i=0 trong d o bk (z ) l` bit th´. k trong biˆ’u diˆn nhi phˆn cua z. Chˇng han, nˆu n = 3 v` ˙ ˜ ˙ ’ ´ ˙ ’ ¯´ a u e e .a a e a . z = 6 = (110)2 th` b0 (z ) = 0, b1 (z ) = 1, b2 (z ) = 1. ı Biˆn d o’i Walsh thuˆn ngu.o.c ˙ ´ e ¯ˆ a . .  N −1 N −1 n −1    W (u, v ) := 1 f (x, y ) (−1)[bi (x)bn−1−i (u)+bi (y)bn−1−i (v)] ,    N x=0 y =0 i=0  N −1 N −1 n −1   f (x, y ) := 1  (−1)[bi (x)bn−1−i(u)+bi (y)bn−1−i (v)].  W (u, v )  N u=0 v =0 i=0 Nhˆn x´t rˇ ng, hat nhˆn biˆn d ˆ’i Walsh l` t´ch d .o.c v` d ˆi x´.ng. Do d o ˙ ` ´ ´ a ea a e ¯o aa ¯u . a ¯o u ¯´ . . .o.c cua n´ c´ thˆ’ d u.o.c t´nh bˇ ng thuˆt to´n tr`nh b`y trˆn. W (u, v ) v` biˆn d o’i ngu . ˙ ˙ ` ´ ˙ o o e¯ . ı ’ a e ¯ˆ a a a ı a e . Ho.n n˜.a, biˆn d ˆ’i Walsh c´ thˆ’ d u.o.c t´nh bˇ ng thuˆt to´n nhanh nhu. FFT. Chˆ kh´c ˙ ˙ ` ˜ ´ u e ¯o o e¯ . ı a a a oa . biˆt duy nhˆ t l` tˆ t ca c´c l˜y th`.a WN d u.o.c d ˇt bˇ ng 1 trong tru.`.ng ho.p FWT. ¯ . ¯a ` ´ ´’ a aa ˙a u e u .a o . . Biˆn d ˆ’i Hadamard ˙ ´ 3.5.2 e ¯o Hat nhˆn biˆn d o’i thuˆn ngu.o.c cua biˆn d o’i Hadamard cho bo.i ˙ ˙ ´ ´ ˙ ’ ˙ ’ a e ¯ˆ a e ¯ˆ . . .   g (x, y, u, v ) := 1 (−1) n=01 [bi (x)bi(u)+bi (y)bi (v)] % 2 , −  i N   h(x, y, u, v ) := 1 (−1) n=01 [bi (x)bi(u)+bi (y)bi (v)] % 2 . − i N Ta c´ cˇp biˆn d o’i Hadamard 2D ˙ ´ oa e ¯ˆ .  N −1 N −1    H (u, v ) := 1 n−1 f (x, y )(−1) i=0 [bi (x)bi (u)+bi (y)bi (v)],    N x=0 y=0  N −1 N −1   f (x, y ) := 1  n−1 i=0 [bi (x)bi (u)+bi (y )bi (v )]  H (u, v )(−1) .  N u=0 v =0 T`. d inh ngh˜ dˆ d`ng suy ra hat nhˆn biˆn d o’i Hadamard t´ch d .o.c v` d oi x´.ng. ˙ ıa ˜ a ´ ´ u ¯. e a e ¯ˆ a ¯u . a ¯ˆ u . Nhˆn x´t 3.5.1 Nˆu N = 2n th` sau mˆt sˆ ho´n vi h`ng v` cˆt, ta c´ thˆ’ chuyˆ’n ma ˙ ˙ ´ .´ a e e ı o o a .a ao oe e . . . kh´c nhau trˆn biˆn d o’i Walsh vˆ ma trˆn biˆn d o’i Hadamard. Nˆu N = 2 th` c´ su a ˙ ˙ n ´ ` ´ ´ a e ¯ˆ e a e ¯ˆ e ıo. . . 62