Bài giảng Xử lý ảnh số - Các phép biến đổi ảnh (Tiếp theo)

Nội dung text: Bài giảng Xử lý ảnh số - Các phép biến đổi ảnh (Tiếp theo)

1. Xử lý ảnh số Các phép biến đổi ảnh Chương trình dành cho kỹ sư CNTT Nguyễn Linh Giang
2. Các phép biến đổi ảnh •Biến đổi đơn nguyên ( unitary ) •Biến đổi Fourier •Biến đổisin, cosin •Biến đổi Hadamar •Biến đổiHaar •Biến đổiK-L
3. Biến đổi đơn nguyên ( unitary ) •Ma trận Unitar và ma trậntrựcgiao –Ma trậnA làtrựcgiaonếu A-1 = AT hay AAT = I 1 1 1 •Vídụ: A = 21− 1 –Ma trận A là ma trận đơn nguyên ( unitary ) nếu A-1 = A*T hay AA*T = I •Vídụ: 1 1 1 1 1 j A = A = 21− 1 2 j 1 –Ma trậnA làthực thì A = A*, tính trực giao và tính đơn nguyên trùng nhau. –Ma trậnA*T còn gọilàAH –ma trận Hermitian
4. Biến đổi đơnnguyên( unitary ) •Biến đổi unitar mộtchiều ( 1D-unitary ) – A ma trận đơn nguyên, AA*T=I – s(n) = { s(0), s(1), , s(n-1)} T –S = (s0, s1, , sn-1) V⎧ = AS –Biến đổi đơn nguyên mộtchiều: ⎨ *T SAV⎩ = -1 *T *T S = A V = A V = Σiai vi trong đó *T * * T *T ai = (a i,0, , a i,N-1) – là cộithứ i củama trậnA và là hàng thứ i củama trậnA* *T – ai gọilàvector cơ sở củaphépbiến đổi đơn nguyên A – Phép biến đổi đơn nguyên A phân tích vector S thành tổ hơp tuyến tính của các vector cơ sở vớivector hệ số phântíchlàV
5. Biến đổi đơnnguyên( unitary ) –Vídụ: , •với A = I = ( , Ei, ) ta có s = ∑iaivi = ∑iEivi , trong đóEi là vector đơnvị cơ sở và bằng: Ei = ( 0, , 0, 1, 0, , 0 )
6. Biến đổi đơnnguyên( unitary ) •Tínhchấtcủa phép biến đổi đơn nguyên: –Làphépbiến đổituyến tính: S1 ⇒ V1 S2 ⇒ V2 a, b: const S = aS1 + bS2 ⇒ V = aV1+bV2 – Định thứcvàcácgiátrị riêng củaA bằng 1; – Phép quay: phép biến đổi đơn nguyên là phép quay vector trong không gian N chiều hay nói cách khác là phép quay hệ trụctọa độ quanh gốctọa độ trong không gian;
7. Biến đổi đơnnguyên( unitary ) –Bảotoànnăng lượng ( đẳng thứcParseval): ||s||2 = ||v||2 –Năng lượng tập trung: • Đốivới ảnh thông thường, năng lượng phân bố không đều; •Cácthànhphầnbiến thiên nhanh chiếmnăng lượng nhỏ trong tín hiệu; •Nhiều phép biến đổi đơn nguyên tậptrungnăng lượng ảnh vào một vài thành phầnhệ số biến đổi; –Giảitương quan ( decorrelation ) • Đầu vào là vector có các thành phầntương quan mạnh, qua phép biến đổinhận được các thành phầntương quan yếu; •Ma trậnhiệpbiến: E[ ( x – E(x))( x – E(x))*T ] –Cácthànhphầnnhỏ cách xa đường chéo có tương quan yếu.
8. Biến )đổ yi rđơ a t i n u n( ê y u g nn i •Bến đổi đơn nguyên hai chiều(2D unitary transform ) r t a m - –Aận đơn nguyên: AA*T = I – s(m, n ): ma trận ảnh S; T – v(k, l): ma trậnhệ số biến đổi V; V⎧ = ASA ⎨ T i –Bến đổi đơn nguyên hai chiều: S⎩ = A VA N −1 N −1 * '' – Điềi ukệr ntựu h ccẩan: m(,)(,)(,) n a'' m= nδ − k − k l l ∑∑ k, l k, l m=0 n=0 N −1 N −1 – Điềi ukện đầy đủ của * a m∑∑(,)(',')(',') nk, l ak, m l = nδ − m −m n n hệ cơ sở: k =0 l=0 ⎧ N −1 N −1 i r ti a hểi –K nbến đổi haiv chiề k(,)(,)(,)u: l⎪ = ∑∑ s m nk, l a m n ⎪ m=0 n=0 ⎨ N −1 N −1 ⎪ * s k(,)(,)(,) l= ∑∑ v k lk, a l m n ⎩⎪ k =0 l=0
9. Biến đổi đơnnguyên( unitary ) – Độ phứctạp: •CầnN2 phép toán nhân số phức; •CầnN2 phép cộng số phức; • Độ phứctạpO(N4) đốivới ảnh NxN – Khi ma trận A có các phầntử phân tách được: •ak,l(m,n) = ak(m) bl(n) , hay là ak,l(m,n) = a(k,m) b(l,n) •{ak(m)}k và {bl(n)}l là tậphợp đầy đủ các vector cơ sở trựcchuẩn1-D –Sử dụng các vector này làm các hàng của các ma trận đơn nguyên A=|a(k,m)| và B=|b(l,n)| •Ápdụng vào các hàng và cộtcủa V , ta có: V = A X BT • Trong nhiềutrường hợp, A và B đượcchọn trùng nhau. • Đốivới ảnh vuông NxN: V = AXAT; S = AHYA* T H * • Đốivới ảnh chữ nhậtMxN: V = AMXAN ; S = AM YAN • Độ phứctạptínhtoán: ~ O(N3)
10. Biến đổi đơnnguyên( unitary ) • Các hình ảnh cơ sở –S = AHVA*, sau khi khai triển, ta sẽ có: s(m, n) =∑k ∑la*(k,m)a*(l,n)v(k,l) –Dướidạng ma trận: H •a*k cộtthứ k củama trậnA H •a*l cộtthứ l củama trậnA T •Ak,l = a*k(a*l) : ma trậnhìnhảnh cơ sở •S = ∑k ∑l Ak,lv(k, l): khai triểnhìnhảnh S thành tổ hợp tuyến tính các hình ảnh cơ sở vớicáchệ số khai triểnbằng phầntử tương ứng củama trậnV.
11. Phép biến đổiFourier đơn nguyên •Phépbiến đổi Fourier đơn nguyên mộtchiều: T –S = (s0, s1, , sN-1) : vector tín hiệu 1 F = W kn –Ma trận Fourier đơn nguyên N N NN× trong đóW=e-j2kπn/N: vector cơ sở N V⎧ = FS –Biến đổi Fourier đơn nguyên 1D: ⎨ *T SFV⎩ = –Khaitriểnphépbiến đổi Fourier đơn nguyên 1D: N −1 ⎧ 1 nk ⎪v() k = s∑ () nN W ⎪ N n=0 ⎨ N −1 ⎪ 1 −nk s() n = v∑ () kN W ⎩⎪ N k=0
12. Phép biến đổiFourier đơnnguyên –Vídụ: s(n) = 1 với0≤ n ≤64 các hệ số Fourier N=128 điểm:
13. Phép biến đổiFourier đơnnguyên •Phépbiến đổi Fourier đơn nguyên hai chiều –Ma trận đơn nguyên: F = FT; F* = F*T; F* = F-1 – V = FSF –S = F*VF* –Khaitriểnphépbiến đổi 2D Fourier đơn nguyên N−1 N−1 k ⎧ 1 km ln ⎪v(,) k= l ∑s m(,) ∑ nN WN W ⎪ N n=0 m=0 ⎨ N−1 N−1 ⎪ 1 −km ln − s(,) m= n∑v k(,) ∑ l WN N W ⎩⎪ N k=0 l=0 l
14. Phép biến đổi Fourier đơn nguyên •Tínhchấtcủaphépbiến đổi Fourier đơn nguyên –Tínhtuyến tính; –Biến đổi Fourier của tín hiệubị dịch – Phép quay: khi tín hiệubị quay mộtgócθ, phổ củatín hiệucũng bị quay đi cùng một góc; –Khaitriển: ⎧ ⎛ m n ⎞ ⎪ f ⎜ , ⎟ g(',') m n= ⎨ ⎝ p p ⎠ m,, nM p ⎩⎪ ,0 otherwise ( , )G ( k mod l F= , k mod N l ), N (∈ , u )nN v [( 0 nN , 0 ), ( , )]
15. Phép biến đổiFourier đơnnguyên • 2D UDFT củamột sốảnh đơngiản – Hàm hình sin –Tínhiệuchữ nhật – Hàm Gauss –Lọc thông thấp
16. Phép biến đổiFourier đơn nguyên