i

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN
THÔNG






PHẠM QUỐC SƠN
TÌM HIỂU CÁC PHÉP BIẾN ĐỔI WAVELET
ỨNG DỤNG TRONG THỦY VÂN BỀN VỮNG



PHẠM QUỐC SƠN
TÌM HIỂU CÁC PHÉP BIẾN ĐỔI WAVELET
ỨNG DỤNG TRONG THỦY VÂN BỀN VỮNG
Chuyên ngành : Khoa học máy tính
Mã số : 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH


iv

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ LỜI CẢM ƠN
Trước hết tôi chân thành cảm ơn Ban giám hiệu, phòng Đào tạo, các thầy cô
giáo trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
đã quan tâm, tạo điều kiện thuận lợi, nhiệt tình giảng dạy và hướng dẫn tôi trong
suốt quá trình học tập ở trường. Đặc biệt tôi gửi lời cảm ơn chân thành nhất tới
PGS.TS. Nguyễn Bá Tường và PGS.TS. Phạm Văn Ất đã hướng dẫn, chỉ bảo và
động viên trong suốt quá trình thực hiện luận văn.
Cuối cùng tôi xin cảm ơn người thân, đồng nghiệp những người đã luôn ủng
hộ, hỗ trợ tôi trong suốt quá trình thực hiện luận văn.
Mặc dù đã có nhiều cố gắng, tuy nhiên luận văn của tôi không thể tránh khỏi
những thiếu sót, do đó tôi rất mong nhận được những ý kiến đánh giá, bổ sung để
tôi có thể hoàn thiện luận văn của mình./.


MỞ ĐẦU 1
CHƢƠNG 1. TỔNG QUAN VỀ PHÉP BIẾN ĐỔI WAVELET 3
1.1. Phép biến đổi Fourier 3
1.1.1. Miền thời gian và miền tần số 3
1.1.2. Nhược điểm của phép biến đổi Fourier 5
1.2. Phép biến đổi Wavelet liên tục 7
1.2.1. Hàm Wavelet cơ sở 8
1.2.2. Họ các hàm Wavelet 10
1.2.2.1. Biến đổi Wavelet Haar 11
1.2.2.1. Biến đổi Wavelet Meeyer 12
1.2.2.1. Biến đổi Wavelet Daubechies 13
1.3. Một số phép biến đổi Wavelet liên tục 14
1.3.1. Phép biến đổi Morlet 14
1.3.2. Phép biến đổi mũ Mexico 14
1.4. Một vài ứng dụng trong phép biến đổi Wavelet 15
1.4.1. Nén ảnh 15
1.4.2. Trích chọn đặc trưng 16
1.4.3. Thủy vân số 16
CHƢƠNG 2. PHÉP BIẾN ĐỔI WAVELET RỜI RẠC 19
2.1. Khái niệm Wavelet rời rạc 19
2.2. Một số phƣơng pháp biểu diễn Wavelet rời rạc 21
2.2.1. Phương pháp biểu diễn bằng bộ lọc 21
2.2.1.1. Khái niệm bộ lọc 21
vi

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 2.2.1.2. Khái niệm tích chập 21
2.2.1.3. Lấy mẫu lên và lấy mẫu xuống 21

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ KẾT LUẬN 56
DANH MỤC VIẾT TẮT

Chữ viết tắt
Diễn giải
Ý nghĩa
DCT
Discrete Cosine Transform
Biến đổi Cosin rời rạc
IDCT
Invert Discrete Cosine Transform
Biến đổi ngược DCT
DFT
Discrete Fourier Transform
Biến đổi Forier rời rạc
IDFT
Invert Discrete Fourier Transform
Biến đổi ngược DFT
DWT
Discrete Wavelet Transform
Biến đổi Wavelet rời rạc
IDWT
Invert Discrete Wavelet Transform
Biến đổi ngược DWT
PN
Pseudo Noise
Giả nhiễu

DANH MỤC HÌNH VẼ

Tên hình
Ý nghĩa
Hình 1.1
Hàm của biến đổi Haar Wavelet

1999 )
Hình 1.2
Hàm của biến đổi Meyer
Hình 1.3
Hàm
()t

của họ biến đổi Daubechies n với n=2, 4, 7, 8

Hình 2.1
Phân tích đa phân giải sử dụng Wavelet rời rạc
Hình 2.2
Miền DWT một chiều
Hình 2.3
Miền DWT hai chiều
Hình 2.4
Ma trận biến đổi Haar cấp 8x8
Hình 2.5
Một khối dữ liệu của ảnh Lena
Hình 2.6

thì vấn nạn sao chép và sử dụng không hợp pháp dữ liệu số ngày một tăng.
Để hạn chế vấn nạn trên, thủy vân số được xem là một trong những giải
pháp quan trọng.
Thủy vân ảnh là kỹ thuật nhúng thông tin vào dữ liệu ảnh trước khi ảnh
được phân phối trên môi trường trao đổi không an toàn. Việc nhúng thông
tin vào ảnh sẽ làm giảm chất lượng ảnh, tuy nhiên thông tin đã nhúng sẽ là
dấu vết để nhận biết sự tấn công trái phép, hoặc để xác định thông tin về
chủ sở hữu.
Dựa vào mục đích sử dụng, các lược đồ thủy vân có thể được chia
thành hai nhóm chính: thủy vân dễ vỡ và thủy vân bền vững. Thủy vân dễ
vỡ là những kỹ thuật nhúng tin nhằm phát hiện ra sự biến đổi dù chỉ vài bít
trên dữ liệu số. Do vậy, thủy vân dễ vỡ thường được ứng dụng trong bài
toán xác thực tính toàn vẹn của dữ liệu trên môi trường trao đổi công khai.
Trái với thủy vân dễ vỡ, thủy vân bền vững yêu cầu dấu thủy vân phải
tồn tại (bền vững) trước những phép tấn công nhằm loại bỏ dấu thủy vân,
hoặc trong trường hợp loại bỏ được dấu thủy vân thì ảnh sau khi bị tấn
2

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ công cũng không còn giá trị sử dụng. Do vậy, những lược đồ thủy vân bền
vững thường được ứng dụng trong bài toán bảo vệ quyền chủ sở hữu.
Các phép biến đổi (Singular Value Decomposition:
T
VDUA 
)
và ( Decomposition: ) cũng giống như , đều là
các phép biến đổi ma trận trực giao và có cùng một tính chất quan trọng là
tập trung năng lượng ảnh vào một số phần tử cố định của miền biến đổi.


1.1. Phép biến đổi Fourier
Cho hàm phép biến đổi Fourier của hàm f là hàm:

Nếu và , phép biến đổi Fourier ngược của f là f
’
. Khi đó và
Khi phép biến đổi Fourier và phép biến đổi ngược tồn tại ta dùng ký
hiệu: để chỉ F là phép biến đổi Fourier của ; là phép biến đổi
Fourier ngược của F.
Nếu ) ta có = 0

Qua phép biến đổi Fourier cho thấy mọi tín hiệu ở miền tần số đều có
thể chuyển về thời gian và ngược lại tín hiệu ở thời gian chuyển về tín hiệu
miền tần số.
1.1.1. Miền thời gian và miền tần số
Miền thời gian ảnh là miền dữ liệu của ảnh gốc, tác động đến miền
không gian ảnh chính là tác động trực tiếp đến các điểm ảnh, làm thay đổi
4

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ giá trị của điểm ảnh. Đây là phương pháp trực quan được tập trung khai
thác trong quá trình thủy vân trong ảnh, khi nói đến việc thủy vân trong ảnh
chính là nhằm thay đổi giá trị các điểm ảnh gốc. Phương pháp này tập trung
tác động ở những bít ít quan trọng của mỗi điểm ảnh nhằm đảm bảo cho

lập. Có một số phương pháp biến đổi phổ biến hiện nay như: Fourier, Cosin
rời rạc (DCT), Wavelet là những phép biến đổi được sử dụng phố biến
trong các kỹ thuật xử lý dữ liệu đa phương tiện, đặc biệt trong xử lý ảnh số.
Ngoài ra các phép biến đổi này còn dùng nhiều trong lĩnh vực giấu tin, thủy
vân số.
1.1.2. Nhƣợc điểm của phép biến đổi Fourier
Mọi hàm tuần hoàn chu kỳ đều có thể khai triển thành chuỗi trong
không gian các hàm tuần hoàn chu kỳ .
Trên [-T⁄2,T⁄2], ta định nghĩa tích vô hướng:

Vì [-T⁄2,T⁄2] [-T⁄2,T⁄2] Nên tích vô hướng trên cũng được áp
dụng cho mọi [-T⁄2,T⁄2] đặt

Dễ dàng kiểm chứng tạo thành một cơ sở trực chuẩn trên [-
T⁄2,T⁄2]

Với các hệ số Fourier:

6

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Phép biến đổi Fourier là công cụ toán học quan trọng, là cầu nối trong
việc biểu diễn tín hiệu giữa miền không gian và miền tần số. Việc biểu diễn
tín hiệu ở miền tần số đôi khi có lợi hơn miền không gian.
Tuy nhiên phép biến đổi Fourier chỉ cung cấp thông tin có tính toàn cục
và chỉ thích hợp cho những tín hiệu tuần hoàn, không chứa các đột biến
hoặc thay đổi không được dự báo trước. Biến đổi Fourier là phép biến đổi
thuận nghịch giữa miền không gian và miền tần số và tín hiệu được xử lý.

nén lại để nâng cao dần tần số dao động. Quá trình này làm thay đổi tỉ lệ
phân tích (Scale), khi thực hiện tiếp bước so sánh tín hiệu sẽ được nghiên
cứu chi tiết ở mức độ tần số cao hơn, giúp phát hiện các thành phần biến
thiên nhanh còn ẩn bên trong tín hiệu.
Trong phép biến đổi Wavelet được chia làm hai nhóm chính là phép
biến đổi Wavelet liên tục và phép ưavelet rời rạc, tùy vào từng bài toán cụ
thể để vận dụng phép biến đổi Wavelet cho phù hợp.
Gọi là tín hiệu , phép biến đổi liên tục của sử dụng hàm
Wavelet được biểu diễn bởi

Trong đó:
- là hệ số biến đổi Wavelet liên tục của với là tỉ lệ (nghịch
đảo của tần số) và là dịch chuyển đặc trưng vị trí của tần số.
- là hàm liên hiệp phức của Wavelet, được gọi là
Wavelet phân tích.
Phương trình (1.6) cho thấy, phép biến đổi Wavelet là một ánh xạ
chuyển từ hàm một biến thành hàm phụ thuộc hai biến số là tỉ lệ
8

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ , biến dịch chuyển . Hệ số trong (1.1) đảm bảo cho sự chuẩn hóa sóng
Wavelet với tỉ lệ phân tích s khác nhau .
Phép biến đổi Wavelet có tính linh động cao hơn so với phép biến đổi
Fourier (sử dụng hàm mũ duy nhất) vì không nhất thiết phải sử dụng hàm
Wavelet cố định, mà có thể lựa chọn các hàm Wavelet khác nhau trong họ
hàm Wavelet sao cho thích hợp với bài toán (hình dạng của hàm Wavelet
phù hợp với tín hiệu cần phân tích) để có kết quả phân tích tốt nhất. Ngày
nay, đã xây dựng được khoảng vài chục các họ hàm Wavelet khác nhau

1
a
gọi là hệ số chuẩn hóa để đảm bảo tích phân năng của
hàm sẽ độc lập với , :

Với mỗi giá trị của a thì là một bản sao của được dịch
đi đơn vị trên trục thời gian. Do đó b gọi là tham số dịch, đặt tham số
dịch thu được.

Điều đó cho thấy rằng a chính là tham số tỷ lệ. Khi thì hàm
Wavelet sẽ được trải rộng còn khi 0 < a < 1 thì hàm sẽ được co lại.
10

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Nếu là biến đổi CWT của bằng hàm Wavelet , thì
biến đổi ngược của CWT được tính như sau:

Với giá trị của C được định nghĩa là:

Biến đổi CWT chỉ tồn tại nếu dương và hữu hạn, do đó gọi là điều
kiện tồn tại của biến đổi Wavelet. Cùng với hai điều kiện trên, đây là điều
kiện thứ ba mà một hàm cần phải thỏa mãn để có thể được lựa chọn làm
hàm Wavelet.
Chúng ta có thể xem biến đổi CWT là ma trận hai chiều các kết quả của
phép tích vô hướng hai hàm và . Các hàng của ma trận ứng
với giá trị của , các cột của ma trận ứng với giá trị . Do đó cách tính biến
đổi Wavelet ở trên có thể trình bày dưới dạng:



Hàm Wavelet Haar thứ hai gọi là Wavelet mẹ

12

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Giá trị của hàm tại những thời điểm rời rạc không quan trọng lắm,
nhưng tương tự trường hợp khai triển Fourier ta quy ước giá trị
tại các giá trị .
Hàm scaling và Wavelet mẹ được mở rộng lên toàn bộ tập
số thực R bằng cách cho nhận giá trị 0 ngoài khoảng cơ bản: Khi đó, biểu đồ của hàm biến đổi Wavelet Haar có dạng như hình sau:

Hình 1.1. Hàm của biến đổi Wavelet Haar

1.2.2.1. Biến đổi Wavelet Meeyer
Yves Meyer là nhà khoa học đặt nền móng cho phép biến đổi Wavelet.
Phép biến đổi Meyer Wavelet cũng là một phép biến đổi thông dụng, biến
13

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ đổi Meyer có khả năng phân tích tín hiệu tốt hơn so với phép biến đổi Haar.
Dạng của hàm
()t

1.3.1. Phép biến đổi Morlet
Năm 1975, Morlet phát triển phương pháp đa phân giải, trong đó ông
sử dụng một xung dao động, được hiểu là Wavelet cho thay đổi kích thước
và so sánh với tín hiệu từng đoạn riêng biệt. Kỹ thuật này bắt đầu với sóng
nhỏ (Wavelet) chứa các dao động tần số khá thấp, sóng nhỏ này so sánh với
tín hiệu phân tích để có được bức tranh toàn cục của tín hiệu ở độ phân giải
thô. Sau đó sóng nhỏ này được nén lại để nâng cao dần dần tần số dao
động. Quá trình này làm thay đổi tỉ lệ phân tích; khi thực hiện bước tiếp so
sánh, tín hiệu sẽ được nghiên cứu chi tiết ở mức độ tần số phân giải cao
hơn, giúp phát hiện những thành phần biến thiên còn ẩn bên trong tín hiệu.
Đó cũng chính là mục đích của phép biến đổi Wavelet.
1.3.2. Phép biến đổi mũ Mexico
Phép biến đổi mũ Mexico là trường hợp đặc biệt của phép biến đổi
Wavelet liên tục. Phép biến đổi này sử dụng phép biển đổi Wavelet liên tục
chuyển đổi được đề xuất bởi Gabor, tính bởi công thức:
15

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
Tổng quát của phép biến đổi Wavelet này còn được gọi là đạo hàm bậc
2 của hàm Gaussian. Do đó có thể tiết kiệm đáng kể thời gian tính toán
trong hai hoặc nhiều chiều.
1.4. Một vài ứng dụng trong phép biến đổi Wavelet
Theo các tài liệu nghiên cứu, phép biến đổi được sử dụng trong rất
nhiều ứng dụng khác nhau như: nén ảnh, trích chọn đặc trưng, phân tích dữ
liệu, thủy vân số Phần này sẽ trình một số hướng ứng dụng chính của
phép biến đổi Wavelet.
1.4.1. Nén ảnh

ứng dụng quan trọng của thủy vân số là bài toán bảo vệ bản quyền. Theo
đó, dấu thủy vân được nhúng vào vùng tập trung năng lượng của ảnh nhằm
tăng cường tính bền vững cho các phương pháp.
Nói đến thủy vân số là nói đến kỹ thuật nhúng tin nhằm đảm bảo an
toàn dữ liệu chứa đối tượng được sử dụng để giấu tin như: Bảo vệ bản
quyền, xác thực thông tin, chống xuyên tạc, điều khiển sao chép, ta có thể
nhận thấy tính ứng dụng của thủy vân rất là lớn, với mỗi ứng dụng lại có
các yêu cầu đặc trưng riêng, do đó các kỹ thuật thủy vân này cũng có
những tính năng khác biệt tương ứng.
Trong kỹ thuật thủy vân số thì thông tin nhúng được gọi là thủy vân.
Thủy vân có thể là một chuỗi ký tự hay là một tệp hình ảnh, biểu tượng.
Thủy vân trên ảnh số là kỹ thuật nhúng một lượng thông tin số vào một
bức ảnh số và thông tin nhúng được gắn liền với bức ảnh chứa và dữ liệu
thủy vân có thể được hiển thị hay ẩn là tùy thuộc vào mỗi kỹ thuật thủy vân
cụ thể.
17

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Có thể chia các kỹ thuật thủy vân theo các nhóm như hình minh họa mô
hình sau. Các kỹ thuật thủy vân theo mô hình trên được phân biệt khác nhau bởi
những đặc trưng, tính chất của từng kỹ thuật và khía cạnh ứng dụng của
những kỹ thuật đó. Trong thực tế, tùy theo mục đích, yêu cầu của bài toán