=-=.LI CM N

Đại học Thái Nguyên
Tụi xin by t KHOA
lũng bit
CÔNG
n sõu
NGH
sc
THÔNG
n TS.
TIN
Bựi Th Hng ó tn tỡnh

hng dn, ch bo v ht lũng giỳp tụi cú th hon thnh lun vn ca
mỡnh.
Xin cm n Khoa Cụng ngh thụng tin i hc Thỏi Nguyờn ó to
iu kin giỳp tụi trongnguyễn
sut quỏ hồng
trỡnh lm
lun vn nghiờn cu.
ngọc

nghiên cứu kỹ thuật nén dữ liệu dựa trên phép
biến đổi sóng nhỏ rời rạc và ứng dụng trong
Nguyờn,số
ngy thỏng nm 2009
máy ảnh kỹThỏi
thuật
Tỏc gi lun vn


Viện Công nghệ thông tin, các thầy cô giáo công tác tại Khoa công nghệ
thông tin – ĐHTN, cùng tập thể các bạn học viên lớp cao học Khóa 6 đã luôn
giúp đỡ, động viên và nhiệt tình chia sẻ với tôi những kinh nghiệm học tập,
nghiên cứu trong suốt khoá học.
Xin được cảm ơn Ban lãnh đạo Trường CĐCN Việt đức, cùng toàn thể
các bạn đồng nghiệp trong Khoa CNTT đã nhiệt tình tạo điều kiện giúp đỡ cả
về thời gian, vật chất và tinh thần để tôi hoàn thành được khóa học của mình.
Thái Nguyên, ngày 10 tháng 11 năm 2009

Học viên

Nguyễn Hồng Ngọc


LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung bản luận văn này là do tôi tự sưu
tầm, tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề tài.
Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ
hình thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên
cứu nào.
Tất cả phần mã nguồn của chương trình đều do tôi tự thiết kế và xây
dựng, trong đó có sử dụng một số thư viện chuẩn và các thuật toán được các
tác giả xuất bản công khai và miễn phí trên mạng Internet.
Nếu sai tôi xin tôi xin hoàn toàn chịu trách nhiệm.

Thái Nguyên, ngày 10 tháng 11 năm 2009
Người cam đoan

Nguyễn Hồng Ngọc


2.3.3. Mã hoá nguồn và mã hoá kênh...........................................................................17
CHƯƠNG 3 CHUẨN NÉN ẢNH TĨNH DỰA TRÊN BIẾN ĐỔI WAVELET
JPEG2000.........................................................................................................................18
3.1. Lịch sử ra đời và phát triển chuẩn JPEG2000...........................................................18
3.2. Các tính năng của JPEG2000....................................................................................18
3.3. Các bước thực hiện nén ảnh theo chuẩn JPEG2000..................................................19
3.3.1. Xử lý trước biến đổi...........................................................................................19
3.3.2. Biến đổi liên thành phần.....................................................................................19
3.3.3. Biến đổi riêng thành phần (biến đổi Wavelet)...................................................20
3.3.4. Lượng tử hoá - Giải lượng tử hoá......................................................................20
3.3.5. Mã hoá và kết hợp dòng dữ liệu sau mã hoá......................................................21
3.3.6. Phương pháp mã hoá SPIHT..............................................................................21
3.3.7. Phương pháp mã hoá EZW................................................................................23
3.4. So sánh chuẩn JPEG2000 với JPEG và các chuẩn nén ảnh tĩnh khác......................24
CHƯƠNG 4 ỨNG DỤNG THỦY VÂN TRONG MÁY ẢNH KỸ THUẬT SỐ...........27
4.1. Giới thiệu về máy ảnh kỹ thuật số.............................................................................27
4.2. Kỹ thuật thuỷ vân sử dụng phép biến đổi DWT........................................................28
4.3. Đề xuất qui trình nén và thủy vân ảnh trong máy ảnh số..........................................42


ii

CÁC HÌNH VẼ, BẢNG BIỂU TRONG LUẬN VĂN
Hình 1.1 Sơ đồ bộ khái quát hệ thống nén ảnh
Hình 1.2. Sơ đồ minh hoạ kỹ thuật mã hoá băng con – M băng con
Hình 1.3. Sơ đồ bộ mã hoá theo chuẩn JPEG
Hình 2.1. Minh hoạ lưới nhị tố dyadic với các giá trị của m và n
Hình 3.1: Trình tự mã hoá (a) và giải mã JPEG2000 (b)
Bảng 3.1: So sánh JPEG và JPEG2000
Hình 4.1. Lược đồ chung cho quá trình giấu tin

PSNR
RLC
SPIHT
STFT
Wavelet
Wavelet Decomposition Tree

Biến đổi Wavelet liên tục (Continuous
Wavelet Transform)
Biến đổi Cosine rời rạc (Discrete Cosine
Transform)
Điều xung mã vi sai (Differized Pulse Code
Modulation)
Biến đổi Wavelet rời rạc (Discrete Wavelet
Transform)
Wavelet cây zero (Embedded Zerotree
Wavelet)
Biến đổi Wavelet rời rạc ngược
Chuẩn nén ảnh của ủy ban JPEG quốc tế
(Joint Photographic Experts Group)
Chuẩn nén ảnh JPEG2000
Phân tích đa phân giải (Multi Resolution
Analysis)
Sai số bình phương trung bình (Mean Square
Error)
Điều xung mã (Pulse Code Modulation)
Tỷ số tín hiệu đỉnh trên nhiễu (Peak Signal to
Noise Ratio)
Mã hoá loạt dài (Run Length Coding)
Phương pháp mã hoá phân cấp theo vùng

cả JPEG2000 cũng chỉ tập trung vào hiệu quả nén (tỉ số nén) và chất lượng.
Trong luận văn trình bầy một kỹ thuật nén ảnh sử dụng biến đổi Wavelet
hiệu năng đem lại hiệu quả nén, chất lượng hình ảnh.


2

 Cơ sở nghiên cứu và mục đích của luận văn
Để có thể sử dụng các dịch vụ Internet và các thông tin số rộng rãi cần
có một kỹ thuật, một công nghệ mang lại nhiều hứa hẹn trong ứng dụng bảo
vệ bản quyền, không bị biến dạng, điều khiển truy cập đối với các dữ liệu đa
phương tiện. Phương pháp giảm kích thước dữ liệu bằng các kỹ thuật nén là
một cách tiếp cận hiệu quả giải quyết các khó khăn trên.
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. 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 dữ liệu đa phương tiện. Đó là kỹ thuật nén ảnh sử dụng biến đổi
Wavelet thích nghi, hiệu năng cho dữ liệu đa phương tiện trong thông tin
và kỹ thuật nhúng thủy vân vào sản phẩm mà không ảnh hưởng đến chất
lượng và bảo vệ bản quyền tác giả, đây là ứng dụng cơ bản bản nhất của kỹ
thuật thủy vân số. Một thông tin nào đó mang ý nghĩa quyền sở hữu tác giả
gọi là thủy vân sẽ được nhúng vào trong các sản phẩm, thủy vân đó chỉ một
mình người chủ sở hữu hợp pháp các sản phẩm đó có và được dùng làm minh
chứng cho bản quyền sản phẩm.
 Tổ chức luận văn
Luận văn được trình bầy thành 4 chương và 1 phụ lục.
Chương 1 trình bầy khái quát các kỹ thuật nén ảnh, phân loại các

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


5

khung video (frame).
Sơ đồ của một hệ thống nén dữ liệu tổng quát như sau:

Hình 1.1 Sơ đồ bộ khái quát hệ thống nén ảnh

Trong hình1.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 trữ và
truyền dẫn trên kênh. Tốc độ bít đầu ra của bộ mã hoá được tính là số bít
cho một mẫu (điểm ảnh). Bộ mã hoá kênh thực hiện việc chuyển đổi luồng
bít đã được nén thành dạng tín hiệu phù hợp cả cho việc lưu trữ và truyền
dẫn, thường bộ mã hoá kênh sử dụng các kỹ thuật: mã hoá có độ dài thay
đổi – RLC (Run Length Coding)[4], mã hoá Huffman[4], mã hoá số học

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


7

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á.
1.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 của tín hiệu (ảnh) thành nhiều băng con (subband). Để mã hoá cho mỗi
băng con, chúng ta sử dụng một bộ mã hoá và một tốc độ bít tương ứng với
tính chất thống kê của băng con.

1.3. Tiêu chuẩn đánh giá chất lượng mã hoá ảnh
Để đánh giá chất lượng của bức ảnh (hay khung ảnh video) ở đầu ra của
bộ mã hoá, người ta thường sử dụng hai tham số: Sai số bình phương trung
bình – MSE (mean square error) và tỉ số tín hiệu trên nhiễu đỉnh – PSNR
(peak to signal to noise ratio). MSE thường được gọi là phương sai lượng tử.
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.

1.4. Các kỹ thuật nén có tổn hao
Trong phần này, trình bày hai kỹ thuật nén tổn hao cho nén ảnh tĩnh và


1.4.2. Kỹ thuật mã hóa 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 trình bầy dưới đây đều là
không tổn hao (lossless); với sự chính xác của các phép toán số học thì các
phép biến đổi vẫn bảo tồn được độ chính xác ở bất kỳ mức độ nào. Nhưng hầu
hết các kỹ thuật mã hoá đều có tổn hao ở bước lượng tử hóa do có sự làm tròn
giá trị cho các hệ số phép biến đổi.
1.4.2.1. Kỹ thuật mã hóa dựa trên phép biến đổi DCT
Phép biến đổi cosine rời rạc – DCT (Discrete Cosine Transform) biến
đổi thông tin ảnh từ miền không gian sang miền tần số để có thể biểu diễn
dưới dạng gọn hơn. Để hiểu rõ kỹ thuật này trước hết ta cần tìm hiểu biến đổi
Fourier.
* Biến đổi Fourier – FT
Biến đổi Fourier – FT (Fourier Transform) là một phép biến đổi thuận
nghịch, nó cho phép sự chuyển đổi thuận – nghịch giữa thông tin và tín hiệu
được xử lý. Phép biến đổi FT cũng có thể được áp dụng cho tín hiệu không ổn
định (non-stationary) nếu chỉ quan tâm đến thành phần phổ nào có trong tín
hiệu mà không quan tâm đến khi nào xuất hiện trong tín hiệu. Tuy nhiên, nếu
thông tin về thời gian xuất hiện của phổ trong tín hiệu là cần thiết, thì phép
biến đổi FT không có khả năng đáp ứng được yêu cầu này, đây là hạn chế của
phép biến đổi này.
* Nén và giải nén ảnh dựa theo phép biến đổi DCT trong JPEG
JPEG là chuẩn nén số quốc tế đầu tiên cho các ảnh tĩnh có tông màu
liên tục gồm cả ảnh đơn sắc và ảnh màu. Trong kỹ thuật này các khối ảnh kích


10


tần số thấp.
* Biến đổi Wavelet rời rạc – DWT
Bước này có thể hiểu phép biến đổi DWT như là áp dụng một tập các
bộ lọc: thông cao và thông thấp. Thiết kế các bộ lọc này tương đương như kỹ
thuật mã hoá băng con (subband coding). Tuy nhiên khác với mã hoá băng
con, các bộ lọc trong DWT được thiết kế phải có đáp ứng phổ phẳng,
trơn và trực giao.
Từ biến đổi DWT một chiều có thể mở rộng định nghĩa biến đổi DWT
hai chiều theo cách: Sử dụng các bộ lọc riêng biệt, thực hiện biến đổi
DWT một chiều dữ liệu vào (ảnh) theo hàng rồi thực hiện theo cột. Theo
cách này nếu thực hiện biến đổi DWT ở mức 1, sẽ tạo ra 4 nhóm hệ số
biến đổi.
* Hai thuật toán nén sử dụng DWT điển hình.
Nén ảnh dựa trên biến đổi DWT đã có những cải tiến đáng kể, đó là
bước đột phá sử dụng DWT để nén ảnh bắt đầu là kỹ thuật mã hoá – EZW
(embedded zero-tree wavelet).
Thuật toán EZW dựa trên khả năng khai thác các thuộc tính đa
phân giải của biến đổi Wavelet để đưa ra một thuật toán ít phức tạp trong


12

tính toán mà vẫn cho hiệu quả nén cao. Những cải tiến và nâng cấp của
EZW về sau đã ra đời một số thuật toán tương tự

như: SPIHT

(set

partitationing in hierarchical tree – cây phân cấp phân tập) và ZTE

(dyadic). Một phân tích như trên hoàn toàn có thể thực hiện được nhờ
biến đổi Wavelet rời rạc (DWT). Do đó, việc tính toán biến đổi DWT thực
chất là sự rời rạc hoá biến đổi Wavelet liên tục (CWT); việc rời rạc hoá
được thực hiện với sự lựa chọn các hệ số a và b như sau:

a = 2m ; b = 2m n; m, n∈ Z

(2.1)

Việc tính toán hệ số của biến đổi Wavelet có thể dễ dàng thực hiện bằng
các băng lọc số nhiều nhịp đa kênh, một lý thuyết rất quen thuộc trong xử lý tín


14

hiệu.
m = -2

••••••••••••••••

m = -2

• • • • • • • •

m = -2
m = -2

•

•


15

) tạo thành hàng cho biết tại một thời điểm t của tín hiệu f(t) có các thành
phần tần số nào.
Tham số b trong biến đổi Wavelet cho biết khoảng dịch của hàm
Wavelet mẹ và độ phân giải các tần số khác nhau của f t được minh họa
bởi hệ tỷ lệ chính là a. Biến đổi Wavelet ngày càng được áp dụng rộng rãi đặc
biệt là trong xử lý tiếng nói, xử lý ảnh số. Xử lý tín hiệu ảnh số là xử lý tín
hiệu hai chiều và do đặc điểm của ảnh số là bao giờ cũng có tính định hướng
và tính định vị. Tính định hướng của một ảnh nghĩa là trong ảnh bao giờ cũng
có một số ít các thành phần tần số nhưng các thành phần tần số này trải rộng
trên toàn bộ không gian ảnh còn tính định vị của ảnh chính là tính chất biểu
thị rằng tại một vùng của ảnh có thể có rất nhiều thành phần tần số. Ảnh biểu
thị tính định vị rõ nhất chính là ảnh có nhiều biên vùng phân tách rõ rệt, tại
các đường biên bao giờ cũng có nhiều thành phần tần số khác nhau, còn hầu
hết các ảnh có tông liên tục đều là những ảnh có tính định hướng.

2.2. Giới thiệu một số họ Wavelet.
2.2.1. Biến đổi Wavelet Haar.
Biến đổi Haar Wavelet là biến đổi đơn giản nhất trong các phép
biến đổi Wavelet. Hình vẽ 2.3 cho thấy dạng của hàm Ψ ( t ) với biến đổi
Haar. Do tính chất đơn giản của biến đổi Haar mà nó được ứng dụng
tương đối nhiều trong nén ảnh, khi áp dụng biến đổi này để nén ảnh thì
thuật toán nén ảnh trên máy tính có một số điểm khác với công thức toán
học của biến đổi Haar.
2.2.2. Biến đổi Wavelet Meyer.
Yves Meyer là một trong những nhà khoa học đã đặt nền móng cho
phép biến đổi Wavelet. Phép biến đổi Wavelet mang tên Meyer cũng là



17

2.3.2. Khử nhiễu.
Tính chất của biến đổi Wavelet mà chúng ta đã xét tới trong phần
ứng dụng cho nén tín hiệu được mở rộng bởi Iain Johnstone và David
Donohos trong các ứng dụng khủ nhiễu cho tín hiệu. Phương pháp khử
nhiễu này được gọi là Wavelet Shrinkage Denoising (WSD). Ý tưởng cơ
bản của WSD dựa trên việc tín hiệu nhiễu sẽ lộ rõ khi phân tích bằng biến đổi
Wavelet ở các hệ số biến đổi bậc cao. Việc áp dụng các ngưỡng loại bỏ
tương ứng với các bậc cao hơn của hệ số Wavelet sẽ có thể dễ dàng loại
bỏ nhiễu trong tín hiệu.
2.3.3. Mã hoá nguồn và mã hoá kênh.
Sở dĩ Wavelet được ứng dụng trong mã hoá nguồn và mã hoá kênh vì
trong mã hoá nguồn thì chúng ta cần khả năng nén với tỷ lệ nén cao còn
trong mã hoá kênh thì cần khả năng chống nhiễu tốt. Biến đổi
Wavelet kết hợp với một số phương pháp mã hoá như mã hoá Huffman
hay mã hoá số học có thể thực hiện được cả hai điều trên.


18

CHƯƠNG 3
CHUẨN NÉN ẢNH TĨNH DỰA TRÊN BIẾN ĐỔI
WAVELET JPEG2000
3.1. Lịch sử ra đời và phát triển chuẩn JPEG2000.
Như chúng ta đã biết, sự ra đời của JPEG mang lại nhiều lợi ích to
lớn về nhiều mặt. JPEG có thể giảm nhỏ kích thước ảnh, giảm thời gian
truyền và làm giảm chi phí xử lý ảnh trong khi chất lượng ảnh là khá tốt.
Để việc nén ảnh có hiệu quả hơn, Ủy ban JPEG đã đưa ra một chuẩn nén