Bài giảng Xử lý ảnh số - Các phép biến đổi ảnh (Phần 2) - Nguyễn Linh Giang

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
Các phép biến đổi ảnh
• Biến đổi đơn nguyên ( unitary )
• Biến đổi Fourier
• Biến đổi sin, cosin
• Biến đổi Hadamar
• Biến đổi Haar
• Biến đổi K-L
Biến đổi đơn nguyên ( unitary )
• Ma trận Unitar và ma trận trực giao
– Ma trận A là trực giao nếu
A-1 = AT hay AAT = I
• Ví dụ:
– Ma trận A là ma trận đơn nguyên ( unitary ) nếu
A-1 = A*T hay AA*T = I
• Ví dụ:
– Ma trận A là thực thì A = A*, tính trực giao và tính đơn
nguyên trùng nhau.
– Ma trận A*T còn gọi là AH – ma trận Hermitian
11
11
2
1
−=A
11
11
2
1
−=A 1
1
2
1
j
j
A =
Biến đổi đơn nguyên ( unitary )
• Biến đổi unitar một chiều ( 1D-unitary )
– A ma trận đơn nguyên, AA*T=I
– s(n) = { s(0), s(1), ..., s(n-1)}
– S = (s0, s1, ..., sn-1)T
– Biến đổi đơn nguyên một chiều:⎩⎨
⎧
=
=
VAS
ASV
T*
S = A-1 V = A*T V = Σiai*T vi trong đó
ai*T = (a*i,0, , a*i,N-1)T – là cội thứ i của ma trận A*T
và là hàng thứ i của ma trận A*
– ai*T gọi là vector cơ sở của phép biế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ới vector hệ số phân tích là V
Biến đổi đơn nguyên ( unitary )
– Ví dụ: 
• với A = I = ( ..., Ei, ... ),
ta có s = ∑iaivi = ∑iEivi , trong đó Ei
là vector đơn vị cơ sở và bằng: 
Ei = ( 0, ..., 0, 1, 0, ..., 0 )
• Tính chất của phép biến đổi đơn nguyên:
– Là phép biến đổi tuyến tính:
S1⇒ V1
S2⇒ V2
a, b: const
S = aS1 + bS2⇒ V = aV1+bV2
– Định thức và các giá trị riêng của A 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ục tọa độ quanh gốc tọa độ trong
không gian;
Biến đổi đơn nguyên ( unitary )
– Bảo toàn năng lượng ( đẳng thức Parseval ):
||s||2 = ||v||2
– Năng lượng tập trung:
• Đối với ảnh thông thường, năng lượng phân bố không đều;
• Các thành phần biến thiên nhanh chiếm năng lượng nhỏ trong tín
hiệu;
• Nhiều phép biến đổi đơn nguyên tập trung năng lượng ảnh vào một
vài thành phần hệ số biến đổi;
– Giải tương quan ( decorrelation )
• Đầu vào là vector có các thành phần tương quan mạnh, qua phép
biến đổi nhận được các thành phần tương quan yếu;
• Ma trận hiệp biến: E[ ( x – E(x))( x – E(x))*T ]
– Các thành phần nhỏ cách xa đường chéo có tương quan yếu.
Biến đổi đơn nguyên ( unitary )
• Biến đổi đơn nguyên hai chiều(2D unitary transform )
– A - ma trận đơn nguyên: AA*T = I
– s(m, n ): ma trận ảnh S;
– v(k, l): ma trận hệ số biến đổi V;
– Biến đổi đơn nguyên hai chiều:
– Điều kiện trực chuẩn: 
– Điều kiện đầy đủ của
hệ cơ sở:
– Khai triển biến đổi hai chiều:
⎩⎨
⎧
=
=
** VAAS
ASAV
T
T
∑∑−
=
−
=
−−=
1
0
1
0
''*
,, ),(),(),( ''
N
m
N
n
lklk llkknmanma δ
∑∑−
=
−
=
−−=
1
0
1
0
*
,, )','()','(),(
N
k
N
l
lklk nnmmnmanma δ
⎪⎪⎩
⎪⎪⎨
⎧
=
=
∑∑
∑∑
−
=
−
=
−
=
−
=
1
0
1
0
*
,
1
0
1
0
,
),(),(),(
),(),(),(
N
k
N
l
lk
N
m
N
n
lk
nmalkvlks
nmanmslkv
Biến đổi đơn nguyên ( unitary )
– Độ phức tạp:
• Cần N2 phép toán nhân số phức;
• Cần N2 phép cộng số phức;
• Độ phức tạp O(N4) đối với ảnh NxN
– Khi ma trận A có các phần tử 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ập hợp đầy đủ các vector cơ sở trực chuẩn 1-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)|
• Áp dụng vào các hàng và cột của V , ta có: V = A X BT
• Trong nhiều trường hợp, A và B được chọn trùng nhau.
• Đối với ảnh vuông NxN: V = AXAT; S = AHYA*
• Đối với ảnh chữ nhật MxN: V = AMXANT; S = AMHYAN*
• Độ phức tạp tính toán: ~ O(N3)
Biến đổi đơn nguyê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ưới dạng ma trận:
• a*k cột thứ k của ma trận AH
• a*l cột thứ l của ma trận AH
• Ak,l = a*k(a*l)T: ma trận hình ảnh cơ sở
• S = ∑k ∑l Ak,lv(k, l): khai triển hình ảnh S thành tổ hợp
tuyến tính các hình ảnh cơ sở với các hệ số khai triển bằng
phần tử tương ứng của ma trận V.
Biến đổi đơn nguyên ( unitary )
Phép biến đổi Fourier đơn nguyên
• Phép biến đổi Fourier đơn nguyên một chiều:
– S = (s0, s1, ..., sN-1)T: vector tín hiệu
– Ma trận Fourier đơn nguyên
trong đó WN=e-j2kπn/N: vector cơ sở
– Biến đổi Fourier đơn nguyên 1D: 
– Khai triển phép biến đổi Fourier đơn nguyên 1D:
NN
kn
NWN
F ×=
1
⎩⎨
⎧
=
=
VFS
FSV
T*
⎪⎪⎩
⎪⎪⎨
⎧
=
=
∑
∑
−
=
−
−
=
1
0
1
0
)(1)(
)(1)(
N
k
nk
N
N
n
nk
N
Wkv
N
ns
Wns
N
kv
Phép biến đổi Fourier đơn nguyên
– Ví dụ: s(n) = 1 với 0≤ n ≤64 các hệ số Fourier N=128 điểm:
Phép biến đổi Fourier đơn nguyên
• Phép biế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*
– Khai triển phép biến đổi
2D Fourier đơn nguyên
⎪⎪⎩
⎪⎪⎨
⎧
=
=
∑∑
∑∑
−
=
−−−
=
−
=
−
=
1
0
ln
1
0
1
0
ln
1
0
),(1),(
),(1),(
N
l
N
km
N
N
k
N
m
N
km
N
N
n
WWlkv
N
nms
WWnms
N
lkv
k
l
Phép biến đổi Fourier 
đơn nguyên
• Tính chất của phép biến
đổi Fourier đơn nguyên
– Tính tuyến tính;
– Biến đổi Fourier của tín
hiệu bị dịch
– Phép quay: khi tín hiệu bị
quay một góc θ, phổ của tín
hiệu cũng bị quay đi cùng
một góc;
– Khai triển:
pnm
otherwise
p
n
p
mfnmg M,,
,0
,)','(
⎪⎩
⎪⎨
⎧
⎟⎟⎠
⎞⎜⎜⎝
⎛
=
)],(),0,0[(),(),mod,mod(),( nNnNvuNlNkFlkG ∈=
Phép biến đổi Fourier đơn nguyên
• 2D UDFT của một
số ảnh đơn giản
– Hàm hình sin
– Tín hiệu chữ nhật
– Hàm Gauss
– Lọc thông thấp
Phép biến đổi Fourier đơn nguyên