Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
=-=.LỜI CẢM ƠN
Tôi xin bày tỏ lòng biết ơn sâu sắc đến TS. Bùi Thế Hồng đã tận tình
hƣớng dẫn, chỉ bảo và hết lòng giúp đỡ để tôi có thể hoàn thành luận văn của
mình.
Xin cảm ơn Khoa Công nghệ thông tin – Đại học Thái Nguyên đã tạo
điều kiện giúp đỡ tôi trong suốt quá trình làm luận văn nghiên cứu.
Thái Nguyên, ngày tháng năm 2009
Tác giả luận văn
NGUYỀN HỒNG NGỌC
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄNC HỒNG NGỌC
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN HỒNGN NGỌC NGHIÊN CỨU MỘT SỐ 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 MÁY ẢNH KỸ THUẬT SỐ
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iii
CÁC HÌNH VẼ, BẢNG BIỂU TRONG LUẬN
VĂN
DWT
EZW
IDWT
JPEG
JPEG2000
MRA
MSE
PCM
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
Trong thời đại của Internet, thông tin ngày càng đƣợc sử dụng rộng rãi
và lƣợng thông tin đƣợc trao đổi qua mạng càng lớn mạnh. Tuy nhiên, với
lƣợng thông tin lớn nhƣ vậy thì nguy cơ truy cập dữ liệu trái phép cũng tăng
lên. Vì thế, nhu cầu đảm bảo an toàn và bảo vệ bản quyền và sở hữu trí tuệ
sản phẩm đang là một nhu cầu cấp thiết. Một trong những giải pháp hữu hiệu
cho vấn đề này là giấu thông điệp vào những phƣơng tiện chứa. Phƣơng tiện
chứa đƣợc dùng phổ biến là các bức ảnh.
Ngày nay, hầu hết các bức ảnh đều đƣợc chụp bằng các máy ảnh kỹ
thuật số. Để thu gọn độ lớn của các files ảnh, ngƣời ta đã sử dụng các kỹ
thuật nén dữ liệu khác nhau và phát sinh ra các định dạng ảnh tƣơng ứng.
Các kỹ thuật này có thể đƣợc nhúng trực tiếp vào trong ảnh và là một khâu
trong qui trình tạo ảnh.
Luận văn này nghiên cứu và đề xuất một kỹ thuật thủy vân các bức ảnh
số ngay trong qui trình tạo ảnh đƣợc nén bằng kỹ thuật sóng nhỏ rời rạc
DWT nhƣ là một minh chứng cho bản quyền tác giả khi cần thiết. So với các
kỹ thuật nén sử dụng phép biến đổi 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.
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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
Cơ sở nghiên cứu và mục đích của luận văn
Wavelet rời rạc (DWT).
Chƣơng 2, 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ý thuyết nền tảng cho các ứng dụng Wavelet.
Chƣơng 3, giới thiệu tổng quan về chuẩn nén JPEG2000 dựa trên
biến đổi Wavelet. Và trong chƣơng này, trình bầy tóm tắt các bƣớc thực
hiện nén ảnh theo JPEG200 và so sánh nó với chuẩn JPEG và các chuẩn nén
ảnh tĩnh khác.
Chƣơng 4, trình bày ứng dụng thủy vân trong máy ảnh kỹ thuật số. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
CHƢƠNG 1
TỔNG QUAN VỀ CÁC KỸ THUẬT NÉN ẢNH
1.1. Giới thiệu chung về nén ảnh số
Nén ảnh số là một đề tài nghiên cứu rất phổ biến trong lĩnh vực xử lý
dữ liệu đa phƣơng tiện. Mục đích là làm thế nào để lƣu trữ bức ảnh dƣới
dạng có kích thƣớc nhỏ hơn hay dƣới dạng biểu diễn mà chỉ yêu cầu số bít
mã hoá ít hơn so với bức ảnh gốc. Nén ảnh thực hiện đƣợc là do một thực
tế: thông tin trong bức ảnh không phải là ngẫu nhiên mà có trật 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.
khả năng nén của hệ thống, công thức đƣợc tính nhƣ sau:
Tỉ số nén = Kích thước dữ liệu gốc / Kích thước dữ liệu nén
Đối với ảnh tĩnh, kích thước chính là số bít để biểu diễn toàn bộ bức
ảnh. Đối với ảnh video, kích thước chính là số bít để biểu diễn một
khung hình video (video frame).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
1.2. Phân loại các kỹ thuật nén
Các kỹ thuật nén chủ yếu đƣợc phân loại nhƣ sau:
1.2.1. Nén tổn hao và không tổn hao
Trong các kỹ thuật nén không tổn hao (losses compression), ảnh
khôi phục giống hoàn toàn so với ảnh gốc. Tuy nhiên, nén không tổn hao
chỉ đạt đƣợc hiệu quả nén rất nhỏ. Trái lại, các kỹ thuật nén có tổn hao (lossy
compression) có thể đạt đƣợc hiệu quả nén cao hơn rất nhiều mà ở điều
kiện cảm nhận hình ảnh thông thƣờng sự mất mát thông tin không cảm
nhận đƣợc và vì thế vẫn đảm bảo chất lƣợng ảnh. Một số kỹ thuật nén có tổn
hao gồm: điều xung mã vi sai – DPCM, điều xung mã – PCM, lƣợng tử hoá
véctơ – VQ, mã hoá biến đổi và băng con. Ảnh khôi phục trong hệ thống nén
có tổn hao luôn có sự suy giảm thông tin so với ảnh gốc bởi vì: 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.
1.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:
1.4.1. Kỹ thuật mã hoá băng con
Tƣ tƣởng chính của kỹ thuật mã hoá băng con là: các ảnh đƣợc lấy mẫu
ở đầu vào đƣợc phân ly thành các băng tần khác nhau (gọi là các tín hiệu băng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
con). Yêu cầu của kỹ thuật này là làm thế nào các băng con không bị chồng
chéo lên nhau. Để có thể phân ly tín hiệu ở bộ mã hoá (encoder) thành các
băng con, ảnh đƣợc cho qua một bank lọc (filter bank) gọi là bank lọc phân
tích và mỗi đầu ra của bank lọc băng con đƣợc lấy mẫu xuống hệ số 2. Các
đầu ra băng con tần số đƣợc lẫy mẫu xuống sẽ lần lƣợt đƣợc: lƣợng tử hoá độc
lập bằng các bộ lọc vô hƣớng khác nhau, mã hoá entropy, lƣu trữ và truyền đi.
Ở phía bộ giải mã (decoder), quá trình đƣợc thực hiện ngƣợc lại: giải lƣợng tử
băng con tần số, lấy mẫu lên với hệ số 2, cho đi qua bank lọc băng con tổng
hợp rồi cộng tất cả các đầu ra của bộ lọc để khôi phục lại ảnh.
Hình 1.2 dƣới đây là sơ đồ tổng quát giải thích kỹ thuật mã hoá băng
con.
Hình 1.2. Sơ đồ minh hoạ kỹ thuật mã hoá băng con – M băng con
Trong các hệ thống mã hóa băng con hai chiều thực tế, ngƣời ta chia
miền tần số - không gian hai chiều của ảnh gốc thành các băng khác nhau ở
bất kỳ mức nào.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
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
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. Sơ đồ khối bộ mã hoá và giải mã của JPEG nhƣ
sau:
Hình 1.3. Sơ đồ bộ mã hoá theo chuẩn JPEG
1.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
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.
Trên cơ sở cách tiếp cận biến đổi STFT, biến đổi Wavelet đƣợc phát
triển để giải quyết vấn đề về độ phân giải tín hiệu mà STFT vẫn còn hạn chế.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Biến đổi Wavelet đƣợc thực hiện theo cách: tín hiệu đƣợc nhân với hàm
Wavelet rồi thực hiện biến đổi riêng rẽ cho các khoảng tín hiệu khác nhau
trong miền thời gian tại các tần số khác nhau. Cách tiếp cận nhƣ vậy còn
đƣợc gọi là: phân tích đa phân giải – MRA (Multi Resolution Analysis): phân
tích tín hiệu ở các tần số khác nhau và cho các độ phân giải khác nhau.
MRA khi phân tích tín hiệu cho phép: phân giải thời gian tốt và phân giải
tần số kém ở các tần số cao; phân giải tần số tốt và phân giải thời gian kém ở các
tần số thấp.
* Biến đổi Wavelet rời rạc – DWT
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
CHƢƠNG 2
CƠ SỞ LÝ THUYẾT CỦA BIẾN ĐỔI WAVELET
2.1. Cơ sở toán học.
2.1.1. Biến đổi Wavelet liên tục.
Biến đổi Wavelet liên tục (Continuous Wavelet Transform - CWT)
của một
hàm f
t
đƣợc bắt đầu từ một hàm Wavelet mẹ (mother
Wavelet)
t
. Hàm
Wavelet mẹ
t
có thể là bất kỳ một hàm số thực hoặc phức liên tục nào thoả mãn
các tính chất sau đây:
- Tích phân suy rộng trên toàn bộ trục t của hàmt là bằng 0.
- Tích phân năng lƣợng của hàm trên toàn bộ trục t là một số hữu
hạn.
Hình 2.1. Minh hoạ lƣới nhị tố dyadic với các giá trị của m và n
2.1.3. Tính chất của biến đổi Wavelet.
Biến đổi Fourier là một biến đổi đã và đang đƣợc áp dụng rộng rãi
trong nhiều ngành khoa học và kỹ thuật khác nhau. Biến đổi Fourier
chuyển một hàm tín hiệu từ miền thời gian
sang miền tần số. Sử dụng biến
đổi Fourier ta có thể biết đƣợc trong tín
hiệu f(t)có các thành phần tần số
nào. Tuy nhiên biến đổi Fourier có một nhƣợc điểm cơ bản là với một tín
hiệu f(t) ta không thể biết đƣợc rằng tại một thời điểm t thì tín hiệu có các
thành phần tần số nào. Một phép biến đổi tốt hơn biến đổi Fourier phải là
phép biến đổi có đầy đủ
tính năng của biến đổi Fourier và có khả năng xác
định xem tại một thời
điểm t bất kỳ trong tín hiệu f(t) có thành phần tần số
nào. Phép biến đổi Wavelet ra đời đã khắc phục đƣợc các nhƣợc điểm của
biến đổi Fourier trong phân tích tín hiệu. Biến đổi Wavelet dù chỉ làm việc
với các tín hiệu một chiều (liên tục hoặc rời rạc) nhƣng sau khi biến đổi
xong ta thu đƣợc một hàm số hai biến hoặc một tập các cặp giá trị W
a, b
minh họa các thành phần tần số khác nhau của tín hiệu xảy ra tại thời
điểm t . Các giá
trị W
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
thông tin).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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.
Copyright: Tài liệu đại học ©