i

LỜI CAM ĐOAN
Tôi xin cam đoan: Luận văn này là công trình nghiên cứu thực sự của cá
nhân, được thực hiện dưới sự hướng dẫn khoa học của PGS.TS. Nguyễn Bá Tường.
Các số liệu, những kết luận nghiên cứu được trình bày trong luận văn này
trung thực và chưa từng được công bố dưới bất cứ hình thức nào. Các thông
tin, tài liệu trích dẫn trong luận văn đã được ghi rõ nguồn gốc.
Tôi xin chịu trách nhiệm về nghiên cứu của mình.
Học viên

Phạm Quốc Sơn


ii

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./.


iii

2.2.1.2. Khái niệm tích chập .............................................................................. 21


iv

2.2.1.3. Lấy mẫu lên và lấy mẫu xuống ............................................................. 21
2.2.1.4. Phép biến đổi wavelet rời rạc và phân tích đa phân giải ........................ 22
2.2.2. Phương pháp biểu diễn trên Ma trận ........................................................ 25
2.2.2.1. Biến đổi Wavelet một chiều bằng ......................................................... 25
2.2.2.2. Biến đổi Wavelet hai chiều bằng ma trận .............................................. 26
2.3. Phép biến đổi Wavelet Haar......................................................................... 27
2.4. Phép biến đổi Wavelet Daubechies .............................................................. 29
2.5. Khai triển Wavelet nhiều mức ..................................................................... 30
2.6. Wavelet động................................................................................................. 31
CHƯƠNG 3. THỦY VÂN BỀN VỮNG TRÊN MIỀN DWT ............................ 37
3.1. Thủy vân số ................................................................................................... 37
3.2. Khai triển SVD ............................................................................................. 38
3.2.1. Khái niệm về khai triển SVD ................................................................... 38
3.2.2. Một số tính chất của khai triển SVD ........................................................ 39
3.2.3. Ví dụ minh họa khai triển SVD................................................................ 40
3.2.4. Thủy vân trên miền SVD ......................................................................... 41
3.3. Khai triển QR ............................................................................................... 45
3.3.1. Phép biến đổi QR..................................................................................... 45
3.3.2. Xét ví dụ .................................................................................................. 45
3.4. Lược đồ thủy vân DWT-SVD....................................................................... 46
3.4.1. Thuật toán nhúng thủy vân DWT- SVD ................................................... 46
3.4.2. Thuật toán trích thủy vân DWT- SVD ..................................................... 48
3.4.3. Cài đặt thử nghiệm .................................................................................. 49
3.4.4. Kết quả nhúng dấu thủy vân .................................................................... 50
3.4.5. Khảo sát tính bền vững của lược đồ DWT-SVD ...................................... 51

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

FFT


Hình 1.1

Hàm

( ) của

biến đổi Haar Wavelet

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


Hình 3.4

Kết quả phân tích QR đối với ma trận A của Hình 3.3


1
MỞ ĐẦU
Một trong những sự kiện trọng đại của những thập niên cuối thế kỷ 20,
đầu thế kỷ 21 là sự ra đời phát triển của mạng internet. Ngày nay, thông tin
trở lên sẵn sàng kết nối trực tuyến, mọi người đều có thể truy cập internet
để tìm kiếm thông tin một cách dễ dàng thông qua nhà cung cấp dịch vụ.
Người dùng có thể đọc các thông tin mới nhất, tra cứu các thư viện số, tìm
thông tin lĩnh vực mình quan tâm. Bên cạnh đó các nhà cung cấp sản phẩm
cũng sẵn sàng cung cấp dữ liệu của mình cho người dùng thông qua mạng
internet.
Tuy nhiên, với lượng thông tin được truyền qua mạng ngày càng nhiều
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

,

,… để xây dựng các lược đồ

thủy vân. Trong luận văn này tìm hiểu các lược đồ thủy vân đã được đề
xuất trên cơ sở đó cải tiến, phát triển lược đồ thủy vân mới dựa trên phép
biến đổi Wavelet đối với miền không gian ảnh. So với các lược đồ thủy vân
dựa trên phân tích

,

đã được đề xuất thì lược đồ mới bền vững hơn

trước một số phép tấn công, biến đổi ảnh, ngoài ra lược đồ mới còn có
thêm một số ưu điểm là: Số lượng phép tính ít hơn, tính bảo mật cao hơn,
chất lượng ảnh thủy vân tốt hơn.
Luận văn tập trung vào nghiên cứu một số kỹ thuật thủy vân trong ảnh
đã được công bố, sau đó mở rộng, phát triển một số lược đồ thủy vân bền
vững ứng dụng phép biến đổi Wavelet trên dữ liệu ảnh số.
Nội dung của luận văn ngoài chương mở đầu, kết luận bao gồm các
chương sau:
Chương 1: Tổng quan về phép biến đổi Wavelet
Chương 2: Phép biến đổi Wavelet rời rạc
Chương 3: Thủy vân bền vững trên miền DWT


3

CHƯƠNG 1. TỔNG QUAN VỀ PHÉP BIẾN ĐỔI WAVELET
Phép biến đổi Wavelet có vai trò quan trọng trong xử lý tín hiệu. Nội


1
2

( ) và

( )

(1.2)

=

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

Mỗi phép biến đổi có những thuận lợi và khó khăn riên, tùy vào trường
hợp cụ thể để lựa chọn phép biến đổi nào cho phù hợp. Sau khi biến đổi các
tín hiệu và miền giá trị rời rạc trong miền biến số mới này, nếu cần thiết có
thể dùng phép biến đổi ngược lại để đưa ảnh về miền biến số độc lập.


5
Phương pháp biến đổi gián tiếp làm đơn giản rất nhiều các công việc
gặp phải khi dùng phương pháp biến đổi trực tiếp trong miền biến số độc
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]⊂



=

[ ]

=

∈

(1.4)

( )

∈

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

[ ]=

,

=

1

( )

( )

( )



7
1.2. Phép biến đổi Wavelet liên tục
Wavelet (sóng nhỏ) là một phương pháp quan trọng trong việc khắc
phục nhược điểm của phép biến đổi FT trong xử lý tín hiệu, phương pháp
này cho phép thay đổi kích thước và so sánh tín hiệu ở mỗi giai đoạn riêng
biệt. Phương pháp 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 được so sánh với tín hiệu phân tích để có một
bức tranh toàn cục của tín hiệu ở độ phân giải thô. Sau đó sóng nhỏ được
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à

Wavelet

tín hiệu 1

, phép biến đổi liên tục của

( ) sử

dụng hàm


) 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
, 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

= ‖

1
√

(1.8)

( )

1.2.1. Hàm Wavelet cơ sở
Biến đổi Wavelet liên tục (CWT) của một hàm ( ) bắt đầu từ hàm của
Wavelet mẹ ký hiệu là: ( ) hàm của Wavelet mẹ (morther Wavelet) ký
hiệu

( ) có thể là hàm số thực, hàm số phức, hay hàm bất kỳ thỏa mãn

tính chất sau:
Tích phân suy rộng trên toàn bộ trục t của hàm ( ) bằng 0, tức là:
( )

=0

Tích phân năng lượng của hàm trên ∫
hữu hạn thỏa mãn điều kiện.

(1.9)
( ) toàn bộ trục

là một số


9


(1.11)

| |

Chúng ta có thể viết được thành:
( . )=

( )

,

( )

(1.12)

Theo toán học ta gọi đây là tích vô hướng của hai hàm

( ) và

( ) giá trị 1 gọi là hệ số chuẩn hóa để đảm bảo tích phân năng của

,

a

hàm

,


1
| |

Điều đó cho thấy rằng a chính là tham số tỷ lệ. Khi

> 1 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
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:
1

( )=

( , )

( , ) ( )

,

( )


đổi Wavelet ở trên có thể trình bày dưới dạng:
( ), ( ) =

( )

( )

=

( )

( , )(

⇒

( ),

( , )(

)

)

(1.16)

1.2.2. Họ các hàm Wavelet
Trong triển khai Wavelet, hai chỉ số được dùng nhằm biểu diễn của tín
hiệu tính địa phương tốt cho cả hai lĩnh vực thời gian và tần số.
Giả sử
mọi


được gọi là biến đổi Wavelet rời rạc của

.
Họ

( , )

dùng 2 chỉ số để có thể biểu diễn được tính địa phương trên

cả hai lĩnh vực thời gian và tần số của tín hiệu, chỉ số
phương theo tần số, chỉ số
Một họ

( , )

được tính địa

định tính theo thời gian.

như trên được gọi là hệ thống Wavelet và nó thỏa mãn ba

điều kiện là: một hệ thống Wavelet là tập các hàm cơ sở để có thể biểu diễn
tín hiệu, khai triển tín hiệu; khai triển Wavelet cho biểu diễn có tính địa
phương theo thời gian – tần số; việc tính toán các hệ số được thực hiện hiệu
quả với độ phức tạp thấp.
1.2.2.1. Biến đổi Wavelet Haar
Biến đổi Haar Wavelet là biến đổi đơn giản nhất trong họ Wavelet. Do
tính chất đơn giản của phép biến đổi Haar, nên phép biến đổi này thường
được ứng dụng nhiều trong nén ảnh. Khi áp dụng phép biến đổi Haar trong



12
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ị

( )=0

= 0, , 1.

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:
( )=

0,
1,

0

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
đổ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 ) với biến đổi Meyer cho hình vẽ sau:

Hình 1.2. Hàm

( ) của

biến đổi Meyer

1.2.2.1. Biến đổi Wavelet Daubechies
Giống với Meyer, Daubechies cũng có công rất lớn trong việc phát
triển phép biến đổi Wavelet. Biến đổi Daubechies là phép biến đổi có tính
chất phức tạp nhất trong các phép biến đổi Wavelet. Họ biến đổi này được
áp dụng rất rộng rãi, biến đổi Wavelet được áp dụng trong JGPEG 2000 là
một biến đổi quan trọng trong họ biến đổi Wavelet Daubechies. Dưới đây
hình biểu diễn một số hàm  (t ) trong họ biến đổi Wavelet Daubechies:


14

Hình 1.3. Hàm  (t ) của họ biến đổi Daubechies n với

= 2, 4, 7, 8

1.3. Một số phép biến đổi Wavelet liên tục

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
Phép biến đổi Wavelet thường được áp dụng nhiều trong xử lý dữ liệu
đa phương tiện, đặc biệt trong xử lý tín hiệu, xử lý ảnh, tín hiệu. Việc sử
dụng các phép mã hóa, lọc tần số nhiều nhịp và biến đổi Wavelet rời rạc
tương ứng với từng loại tín hiệu cần phân tích mang lại hiệu quả rõ rệt
trong nén tần số ảnh. Do tích chất chỉ tồn tại trong thời gian rất ngắn khi
phân tích tín hiệu trong miền tần số, mà các hệ số của biến đổi Wavelet có
khẳ năng tập trung năng lượng rất tốt vào các hế số biến đổi. Các hệ số
chứa thông tin chi tiết của biến đổi Wavelet rất nhỏ và có thể bỏ qua mà
không ảnh hưởng đến việc mã hóa dữ liệu.
Đối với nén ảnh, ngoài tỷ lệ nén cao, Wavelet còn cho chất lượng ảnh
tốt. Chất lượng của ảnh được đánh giá qua hệ số PSNR giữa ảnh gốc I và
ảnh nén I’ theo công thức :
= 20.
Trong đó,
xám thì

√

(1.23)

là giá trị cực đại của điểm ảnh. Đối với ảnh đa cấp
= 255, ảnh nhị phân


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
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.
Thủy vân số

Thủy vân bền vững

Thủy vân ẩn

Thủy vân hiện

Thủy vân dễ vỡ

Thủy vân ẩn


Còn đối với thủy vân dễ vỡ là kỹ thuật nhúng thủy vân vào trong ảnh
sao cho sản phẩm khi phân phối, truyền tải trong các môi trường nếu có bất
kỳ một phép biến đổi nào làm thay đổi đối thượng sản phẩm gốc thì thủy
vân đã được giấu trong đối tượng đó sẽ không còn nguyên vẹn như thủy
vân gốc. Các tính chất của kỹ thuật thủy vân này thường được sử dụng
trong các ứng dụng xác thực thông tin và phát hiện thông tin bị xuyên tạc.
Đó chính là nguyên nhân vì sao các ứng dụng loại này rất cần đến kỹ thuật
thủy vân dễ vỡ. Ví dụ như để bảo vệ chống bị xuyên tạc một ảnh nào đó,
người ta nhúng một thủy vân vào đó và sau đó quảng bá, phân phối đối
tượng này. Khi cần kiểm tra lại người ta sử dụng hệ thống đọc thủy vân,
nếu không đọc được thủy vân hoặc thủy vân đã bị sai lệch nhiều so với
thủy vân ban đầu đã được nhúng vào đối tượng thì có nghĩa là bức ảnh đó
đã bị thay đổi, chỉnh sửa.


19
CHƯƠNG 2. PHÉP BIẾN ĐỔI WAVELET RỜI RẠC
Dựa trên kiến thức cơ sở trong Chương 1, nội dung chương này trình
bày một số khái niệm, phương pháp Wavelet được dùng phổ biến trong nén
dữ liệu, phát hiện ảnh giả mạo, thủy vân số. Nội dung chính của chương
gồm:
Nội dung chính của chương bao gồm:
- Phép biến đổi Wavelet rời rạc
- Phép biến đổi Wavelet Haar
- Phép biến đổi Wavelet Daubechies
- Wavelet nhiều mức
- Wavelet động
2.1. Khái niệm Wavelet rời rạc
Cơ sở của phép biến đổi wavelet rời rạc (DWT, Discrete Wavelet
Transform) từ năm 1976 khi Croiser, Esteban và Galand đưa ra kỹ thuật