Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
----------------
LUẬN VĂN THẠC SỸ KHOA HỌC

NÉN ẢNH SỬ DỤNG BIẾN ĐỔI WAVELET VÀ
ỨNG DỤNG TRONG CÁC DỊCH VỤ DỮ LIỆU ĐA
PHƯƠNG TIỆN DI ĐỘNG
NGHÀNH: ĐIỆN TỬ VIỄN THÔNG ĐỖ NGỌC ANH Người hướng dẫn khoa học: PGS.TS. Nguyễn Đức Thuận
HÀ NỘI 2006
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
MỤC LỤC

CÁC HÌNH VẼ, BẢNG BIỂU TRONG LUẬN VĂN ..............................5

THUẬT NGỮ TIẾNG ANH ......................................................................7

2.4.2.1. Kỹ thuật mã hoá dựa trên phép biến đổi DCT.................19

2.4.2.2. Kỹ thuật mã hoá dựa trên phép biến đổi DWT ...............25

CHƯƠNG 3:CƠ SỞ LÝ THUYẾT BIẾN ĐỔI WAVELET...................30

3.1. Cơ sở toán học ...............................................................................30

3.1.1. Biến đổi
Wavelet
liên tục........................................................30

3.1.2. Biến đổi Wavelet rời rạc .........................................................32

3.2. Tính chất của biến đổi Wavelet......................................................33

3.3. Giới thiệu một số họ Wavelet ........................................................37

3.3.1. Biến đổi Wavelet Haar............................................................37

3.3.2. Biến đổi Wavelet Meyer .........................................................38

Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
3.3.3. Biến đổi Wavelet Daubechies .................................................38

3.4. Một số ứng dụng nổi bật của Wavelet ...........................................39

3.4.1. Nén tín hiệu.............................................................................39


CHƯƠNG 5:ỨNG DỤNG WAVELET TRONG CÁC DỊCH VỤ DỮ
LIỆU ĐA PHƯƠNG TIỆN TRONG THÔNG TIN DI ĐỘNG...............54

5.1. Nén ảnh bằng
Wavelet
...................................................................54

5.2.1. Sơ đồ khối tổng quát...............................................................54

5.1.2. Biến đổi Wavelet.....................................................................55

5.1.3. Tính toán năng lượng tiêu hao................................................56

5.2. Thuật toán nén ảnh bằng Wavelet hiệu năng - EEW .....................58

5.2.1. Hiệu năng của các kỹ thuật loại bỏ.........................................60

5.3.2. Các kết quả thực nghiệm ........................................................62

5.3.2.1. Ảnh hưởng đến năng lượng tính toán và chất lượng ảnh 62

Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
5.3.2.2. Ảnh hưởng đến năng lượng truyền thông và chất lượng
ảnh.................................................................................................62

5.4. Các tham số nén ảnh bằng Wavelet ...............................................62

5.4.1. Thay đổi mức biến đổi Wavelet..............................................62



Hình 2.6. Sắp xếp Zigzag các hệ số DCT ở bộ mã hoá............................23

Hình 2.7. Sơ đồ khối bộ giải mã theo chuẩn JPEG..................................23

Hình 2.8. Bank lọc khôi phục lý thuyết sử dụng DWT 1D ......................28

Hình 2.9. Minh hoạ
DWT
hai chiều cho ảnh ............................................28

Hình 2.10(a). Minh hoạ DWT kiểu dyadic mức 3 để nén ảnh..................28

Hình 2.10(b). Minh hoạ DWT kiểu dyadic mức 3 để nén ảnh..................29

Hình 3.1. Minh hoạ lưới nhị tố dyadic với các giá trị của m và n............33

Hình 3.2. Phân tích đa phân giải áp dụng cho biểu diễn tín hiệu .............36

Hình 3.3. Hàm
()
t
ψ
của biến đổi Haar ....................................................38

Hình 3.4: Hàm
( )
t
ψ
của biến đổi Meyer..................................................38

Hình 5.2. (a) Biến đổi Wavelet 2D mức 3 và (b) Minh hoạ bằng ảnh
“CASTLE”................................................................................................56

Hình 5.3. Phân bố số học các hệ số thông cao sau phép biến đổi Wavelet
mức 2.........................................................................................................59

Hình 5.4: Dữ liệu sau phép biến đổi Wavelet với hai kỹ thuật loại bỏ HH
và H*.........................................................................................................61Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
THUẬT NGỮ TIẾNG ANH

CWT Biến đổi Wavelet liên tục
(Continuous Wavelet Transform)

DCT Biến đổi Cosine rời rạc
(Discrete Cosine Transform)

DFT Biến đổi Fourier rời rạc
(Discrete Fourier Transform)

DPCM Điều xung mã vi sai
(Differized Pulse Code Modulation)

DWT Biến đổi Wavelet rời rạc
(Discrete Wavelet Transform)

EZW Wavelet cây zero

(Short Time Fourier
Transform)

Wavelet Biến đổi băng con Wavelet
Wavelet Decomposition
Tree
Cây phân giải Wavelet
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh

LỜI GIỚI THIỆU

Trong những năm gần đây, nhu cầu các dịch vụ dữ liệu trên mạng
di động, nhất là dữ liệu đa phương tiện là rất lớn. Cùng với nhu cầu đó,
vấn đề đặt ra là làm thế nào tìm được một kỹ thuật mã hoá dữ liệu then
chốt (chuẩn), có hiệu quả để truyền các dữ liệu này trên mạng di động.
Mục đích của luận văn là trình bầ
y một kỹ thuật nén ảnh sử dụng
biến đổi Wavelet cho ảnh tĩnh và đặc biệt là ảnh tĩnh trong các dịch vụ dữ
liệu đa phương tiện trong mạng di động. So với các kỹ thuật nén sử dụng
phép biến đổi trước đây như biến đổi Fourier (FT), biến đổi cosine rời rạc
(DCT), biến đổi xếp chồng (LT),.., biế
n đổi Wavelet (DWT) có nhiều ưu
điểm không chỉ trong xử lý ảnh mà còn nhiều ứng dụng khác. Bằng
chứng là sự ra đời của chuẩn nén JPEG2000 (dựa trên DWT) có tính năng
vượt trội so với JPEG (DCT). Tuy nhiên chuẩn JPEG, MPEG hay ngay
cả JPEG2000 cũng chỉ tập trung vào hiệu quả nén (tỉ số nén) và chất
lượng ảnh mà không chú ý đến năng lượng tiêu hao trong quá trình xử lý
và truyền trên mạ
ng. Trong luận văn đã trình bầy một kỹ thuật nén ảnh

Mặc dù cho đến nay có rất nhiều kỹ thuật nén dữ liệu đa phương
tiện như: chuẩn JPEG (dựa trên biến đổi DCT), chuẩn JPEG2000 (dựa
trên biến đổi Wavelet) và chuẩn MPEG, tuy nhiên nhữ
ng kỹ thuật này chỉ
tập trung vào hiệu quả nén và cố gắng đánh mất chất lượng ảnh ít vì thế
chúng bỏ qua vấn đề tiêu hao năng lượng trong quá trình nén và truyền
RF (trong thông tin động). Luận văn này trình bầy một kỹ thuật hiệu quả
để khắc phục những khó khăn trên cho loại dữ liệu đa phương tiện điển
hình trong thông tin di động là ảnh tĩnh. Đó là kỹ thu
ật nén ảnh sử dụng
biến đổi Wavelet thích nghi và hiệu năng cho dữ liệu đa phương tiện
trong thông tin di động.
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
1.2. Tổ chức luận văn
Luận văn được trình bầy thành 5 chương và 1 phụ lục. Chương 1,
tác giả trình bày tóm tắt cơ sở nghiên cứu và mục đích cũng như tổ chức
của luận văn.
Chương 2 trình bầy khái quát các kỹ thuật nén ảnh, phân loại các
nguyên lý nén và định nghĩa một số thuật ngữ được sử dụng rộng rãi như
MSE, PSNR và SNR. Chương này cũng trình bầ
y cơ sở lý thuyết của các
nguyên lý nén có tổn hao điển hình như: mã hoá băng con; mã hoá dựa
trên biến đổi cosine rời rạc (DCT), biến đổi xếp chồng (LT), biến đổi
Wavelet rời rạc (DWT).
Chương 3 trình bầy cơ sở toán học, tính chất của biến đổi Wavelet.
Nội dung của chương này là lý thuết nền tảng cho các ứng dụng Wavelet.
Chương này cũng đư
a ra một số họ Wavelet phổ biến và giới thiệu một số
ứng dụng nổi bật của Wavelet ngoài ứng dụng để nén ảnh.

tự, có tổ chức. Vì thế nếu bóc tách được tính trật tự, cấu trúc đó thì sẽ biết
được phần thông tin nào quan trọng nhất trong bức ảnh để biểu diễn và
truyền đi với số lượng bít ít hơn so với ảnh gốc mà vẫn đảm bảo tính đầy
đủ thông tin. Ở phía thu, quá trình giải mã sẽ tổ
chức, sắp xếp lại được
bức ảnh xấp xỉ gần chính xác so với ảnh gốc nhưng vẫn thoả mãn chất
lượng yêu cầu, đảm bảo đủ thông tin cần thiết.
Tóm lại, tín hiệu ảnh, video hay audio đều có thể nén lại bởi chúng
có những tính chất như sau:
• Có sự tương quan (dư thừa) thông tin về không gian: Trong phạm
vi một bức ảnh hay một khung video tồn tại sự
tương quan đáng kể
(dư thừa) giữa các điểm ảnh lân cận.
•
Có sự tương quan (dư thừa) thông tin về phổ: Các dữ liệu thu được
từ các bộ cảm biến của thiết bị thu nhận ảnh tồn tại sự tương quan
đáng kể giữa các mẫu thu, đây chính là sự tương quan về phổ.
• Có sự tương quan (dư thừa) thông tin về thời gian: Trong m
ột
chuỗi ảnh video, tồn tại sự tương quan giữa các điểm ảnh của các
khung video (frame). Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
Sơ đồ của một hệ thống nén dữ liệu tổng quát như sau:

Hình 2.1 Sơ đồ bộ khái quát hệ thống nén ảnh
Trong hình 2.1, bộ mã hoá dữ liệu thực hiện quá trình nén bằng
cách giảm kích thước dữ liệu ảnh gốc đến một mức phù hợp với việc lưu

phương pháp nén này đã lo
ại bỏ những thông tin dư thừa không cần thiết.
2.2.2. Mã hoá dự đoán và mã hoá dựa trên phép biến đổi
Đối với mã hoá dự đoán (predictive coding) các giá trị mang thông tin đã
được gửi hay đang sẵn có sẽ được sử dụng để dự đoán các giá trị khác, và
chỉ mã hoá sự sai lệch giữa chúng. Phương pháp này đơn giản và rất phù
hợp với việc khai thác các đặc tính cục bộ của bức ảnh. Kỹ thu
ật DPCM
chính là một ví dụ điển hình của phương pháp này. Trong khi đó, mã hoá
dựa trên phép biến đổi (transform based coding) thì lại thực hiện như sau:
trước tiên thực hiện phép biến đổi với ảnh để chuyển sự biểu diễn ảnh từ
miền không gian sang một miền biểu diễn khác. Các phép biến đổi
thường dùng là: DCT - biến đổi Cosine rời rạc, DWT - biến đổi Wavelet
rời rạc, LT - biến đổi trồng (lapped) , tiếp đó thực hiện mã hoá đối với các
hệ sộ biến đổi. Phương pháp này có hiệu suất nén cao hơn rất nhiều so
với phương pháp nén dự đoán bởi vì chính các phép biến đổi (sử dụng
các thuộc tính nén năng lượng của mình) đã gói gọn toàn bộ năng lượng
bức ảnh chỉ bằng một số ít các hệ s
ố, số lớn các hệ số còn lại ít có ý nghĩa
hơn sẽ bị loại bỏ sau khi lượng tử hoá và như vậy lượng dữ liệu phải
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
truyền nhỏ đi rất nhiều. Trong phương pháp mã hoá dự đoán, sai lệch
giữa ảnh gốc và ảnh dự đoán vẫn có ý nghĩa (còn sử dụng ở bước tiếp
theo) sau khi lượng tử hoá, chính điều này làm cho phương pháp mã hoá
dự đoán có nhiều dữ liệu được truyền đi hơn so với phương pháp mã hoá
biến đổi.
2.2.3. Mã hoá băng con
Bản chất của kỹ thuật mã hoá băng con
(subband coding) là chia băng tần

(2.1)
Trong đó tổng lấy theo j, k tính cho tổng tất cả các điểm ảnh trong ảnh và
N là số điểm ảnh trong ảnh. Còn PSNR giữa hai ảnh (b bít cho mỗi điểm
ảnh, RMSE là căn bậc 2 của MSE) đước tính theo công thức dB như sau:
12
log20
10
−
−=
b
RMSE
PSNR
(2.2)
Thông thường, nếu PSNR ≥ 40dB thì hệ thống mắt người gần như không
phân biệt được giữa ảnh gốc và ảnh khôi phục.
Một tham số khác hay sử dụng trong các hệ thông viễn thông đó là tỉ số
tín hiệu trên nhiễu - SNR , tuy vậy SNR sử dụng cho một hệ thống né ảnh
cũng có công thức dB như sau:
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
10
10log

Encoder input energy
SNR
Noise energy
=
(2.3)

2.4.Các kỹ thuật nén có tổn hao

trong thực tế, sự tương quan tổng không bao giờ đạt được do những bộ
lọ
c này chỉ xấp xỉ với các bộ lọc lý tưởng.
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
Hình 2.2 dưới đây là sơ đồ tổng quát giải thích kỹ thuật mã hoá băng con.

Hình 2.2. Sơ đồ minh hoạ kỹ thuật mã hoá băng con – M băng con

Các bộ lọc sử dụng trong mã hoá băng con là các
bộ lọc gương tứ
phương – QMF (quardrature mirror filters)
, do vậy chúng ta chỉ cần
thiết kế các bộ lọc thông thấp có đáp ứng H(
ω
) còn đáp ứng của các bộ
lọc thông cao là H(
ω
+
π
)

chỉ là sự dịch pha 180
o
so với bộ lọc thông thấp.
Sự chính xác của bộ lọc phụ thuộc vào số các hệ số của bộ lọc.
Một trong các phương pháp mã hoá băng con đó là áp dụng sự phân ly
cây bát phân để phân ly dữ liệu ảnh thành các băng tần khác nhau. Ý
tưởng của phương pháp này là: trước tiên lọc và lược bỏ ảnh để phân ly
ảnh thành các băng con tần số cao và thấp, sau đó tiếp tục phân ly nhưng

được hiệu suất cao nhất. Một trong những cách thực hiện là sử dụng ý
tưởng cấp phát bít tối ưu cho mỗi đầu ra băng con đã được lượng tử hoá.
Tuy nhiên cách này chủ yếu thích hợp cho trường hợp tốc độ cao
(
≥1bít/mẫu).
Trước khi đi vào nghiên cứu kỹ thuật mã hoá dựa trên phép biến
đổi, chúng ta sẽ tổng kết một số nhược điểm của kỹ thuật mã hoá băng
con như sau:
Kỹ thuật mã hoá băng con không xác định được hệ thống mã hoá tối ưu
cho các ứng dụng tốc độ bít thấp.
Việc cấp phát bít tối ưu sẽ thay đổi khi tốc độ bít tổng thay đổi,
đi
ều này làm quá trình mã hoá phải lặp lại hoàn toàn cho mỗi tốc độ bít
xác định.
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
Không hoàn toàn giải tương quan cho tất cả các băng tần, đấy là do
các bộ lọc không phải là lý tưởng và có sự chồng chéo nhỏ giữa các băng
tần liền kề. Do vậy luôn luôn tồn tại một sự tương quan nhỏ giữa các
băng tần kề nhau và dữ liệu sẽ không được nén hoàn toàn.
Kỹ thuật mã hoá băng con không hiệu quả khi thực hiện bù chuyển động
trong video vì rất khó để thực hiện đ
ánh giá chuyển động ở các băng con
(sai số dự đoán là rất lớn).

2.4.2. Kỹ thuật mã hoá dựa trên phép biến đổi
Một phép biến đổi là một hàm toán học được sử dụng để biến đổi
một tập các giá trị này thành một tập giá trị khác và tạo ra một cách biểu
diễn mới cho cùng một nguồn tin. Tất cả các phép biến đổi mà chúng ta
định trình bầy dưới đây đều là không tổn hao (lossless); với sự chính xác

đổi). Tuy nhiên ở một thời điểm bất kỳ chỉ tồn tại một miền thông tin
được thể hiện. Nghĩa là tín hiệu trong miền không gian không có sự xuất
hiện thông tin về tầ
n số và tín hiệu sau biến đổi Fourier không có sự xuất
hiện thông tin về thời gian.
FT cho biết thông tin tần số của tín hiệu, cho biết những tần số nào
có trong tín hiệu, tuy nhiên nó không cho biết tần số đó xuất hiện khi nào
trong tín hiệu. Nếu như tín hiệu là ổn định (stationary – có các thành
phần tần số không thay đổi theo thời gian) thì việc xác định các thành
phần tần số xuất hiện khi nào trong tín hiệu là không cầ
n thiết.
Phép biến đổi FT thuận và nghịch được định nghĩa như sau:
X(f) =
∫
∞
∞−
−
dtetx
ftj
π
2
)(
(2.4)
x(t) =
∫
∞
∞−
dfefX
ftj
π

Wnx
, k=0,………., N-1 (2.6)
Trong đó
W
N
= e
Nj
/2
Π−
= cos (2
π
/N) – j sin (2
π
/N)
, còn chuỗi
{x(n)}
có thể
khôi phục bằng DFT ngược như sau:
x(n) =
N
1

∑
−
=
−
1
0
)(
N

cos)(
N
n
N
kn
nx
π
, k= 0,1,………,N-1 (2.8)
IDCT = x(n) =
N
2
∑
−
=
⎥
⎦
⎤
⎢
⎣
⎡
+
1
0
2
)12(
cos)(
N
k
k
N

ụng biến đổi IDCT ở bộ giải mã.
Biến đổi DCT và IDCT 8 mẫu tạo thành các ma trận 8x8 theo công thức:
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
2-D DCT = X
k,l
=
4
)()( lckc

∑∑
==
⎟
⎠
⎞
⎜
⎝
⎛
+
⎟
⎠
⎞
⎜
⎝
⎛
+
7
0
7
0

⎝
⎛
+
7
0
7
0
lk,

16
1)l(2n
cos
16
1)k(2m
cosX
4
)()(
kl
lckc
ππ
(2.11)
Trong đó m,n = 0,1,………..,7
và c(k),c(l)

=
⎪
⎩
⎪
⎨
⎧

, để áp dụng kỹ thuật nén này, trước
hết phải chuyển sang chế độ
màu YUV (Y là thành phần chói, U và V là 2
thành phần màu). Thành phần độ chói là ảnh đơn sắc xám. Hai thành
phần màu còn lại chứa thông tin về màu. Việc mã hoá và giải mã ảnh
trong JPEG ở được thực hiện cho thành phần chói rồi màu.
Sơ đồ khối bộ mã hoá và giải mã của JPEG như sau:
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh

Hình 2.5. Sơ đồ bộ mã hoá theo chuẩn JPEG

Hình 2.6. Sắp xếp Zigzag các hệ số DCT ở bộ mã hoá

Hình 2.7. Sơ đồ khối bộ giải mã theo chuẩn JPEG

Quá trình xử lý thành phần độ chói ở phía mã hoá được giải thích như
sau:
(a) Ảnh gốc được chia thành các khối ảnh (block) nhỏ kích thước 8x8
không chồng chéo lên nhau. Tiếp theo, giá trị của mỗi điểm ảnh ở
Luận văn cao học ĐTVT 2004 – 2006
Đỗ Ngọc Anh
mỗi khỗi khối ảnh sẽ được trừ đi 128. Lý do là do giá trị các điểm
ảnh có giá trị từ 0 đến 255 (được mã hoá bởi 8 bít không dấu), áp
dụng biến đổi DCT sẽ tạo ra các hệ số AC có dải giá trị từ -1023 đến
+1023 (có thể được mã hoá bởi 11 bít có dấu). Nhưng hệ số DC lại có
giải giá trị từ 0 đến 2040 (được mã hoá bởi 11 bít không dấu) và cần
cách xử lý khác ở phần c
ứng hoặc phần mềm so với các hệ số AC.
Chính vì thế việc trừ giá trị mỗi điểm ảnh đi 128 là để sau khi biến

theo hình Zigzag tạo thành mảng một chiều. Cách sắp xếp này cho
phép giảm thiểu năng lượng tổn hao trung bình và tạo ra dãy các giá
trị bằng 0 liên tiếp. Cũng theo cách sắp xếp này, các hệ số DC
được
tách khỏi các hệ số AC và sử dụng kỹ thuật mã hoá điều xung mã vi
sai – DPCM.
(e) Bước cuối cùng của bộ mã hoá là sử dụng mã hoá entropy chẳng hạn
mã hoá Huffman cho các AC và DC (sau khi đã mã hoá DPCM) để
tăng thêm hiệu quả nén cũng như giảm thiểu lỗi.
Ở phía giải mã, luồng bít mã hoá được giải mã entropy, sau đó mảng hai
chiều các hệ số DCT đã được lượng tử hoá được giải sắp xếp Zigzag và
giải l
ượng tử. Mảng hai chiều các hệ số DCT kết quả sẽ được biến đổi
IDCT rồi cộng mỗi giá trị với 128 để xấp xỉ tạo thành các khối ảnh con
kích thước 8x8. Chú ý là bảng lượng tử hoá và mã hoá entropy ở cá phía
mã hoá và giải mã là đồng nhất.
Hai thành phần màu cũng được mã hoá tương tự như thành phần chói
ngoại trừ khác biệt là chúng được lấy mẫu xuống hệ số 2 hoặc 4
ở cả
chiều ngang và dọc trước khi biến đổi DCT. Ở phía giải mã , thành phần
màu sẽ được nội suy thành kích thước gốc.
2.4.2.2. Kỹ thuật mã hoá dựa trên phép biến đổi DWT
Mối quan hệ giữa biến đổi Wavelet và Fourier
Không giống như biến đổi Fourier chỉ thích hợp khi phân tích những tín
hiệu ổn định (stationary),Wavelet là phép biến đổi được sử dụng để phân
tích các tín hiệu không ổn định (non-stationary) – là những tín hiệu có
đáp ứng tần số thay đổi theo thời gian.
Để khắc phục những hạn chế của biến đổi FT, phép biến đổi Fourier thời
gian ngắn – STFT được đề xuất. Ch
ỉ có một sự khác biệt nhỏ giữa STFT