1
Số hóa bởi Trung tâm Học liệu
ĐẠ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 KIM
THỦY VÂN THUẬN NGHỊCH SỬ DỤNG
PHÉP BIẾN ĐỔI MỞ RỘNG HIỆU
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 NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. Phạm Văn Ất
Thái Nguyên - 2014
3
Số hóa bởi Trung tâm Học liệu LỜI CAM ĐOAN
Tôi xin cam đoan Những nội dung trong luận văn “Thủy vân thuận
nghịch sử dụng phép biến đổi mở rộng hiệu” là do tôi thực hiện dưới sự
hướng dẫn trực tiếp của Thầy PGS.TS. Phạm Văn Ất.
Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng tên
Xin chân thành cảm ơn quý Thầy Cô trong khoa Sau đại học Trường
Đại học Công nghệ Thông tin và Truyền thông – ĐH Thái Nguyên đã nhiệt
tình giảng dạy, trang bị cho tôi những kiến thức quý báu trong suốt thời
gian học tập tại trường.
Tôi xin tỏ lòng biết ơn sâu sắc tới các thầy cô, bạn bè đã dìu dắt,
giúp đỡ tôi tiến bộ trong suốt quá trình làm khóa luận tốt nghiệp.
Xin gửi lời cảm ơn tới gia đình, những người bạn của tôi đã động
viên, giúp đỡ tôi trong suốt quá trình học tập và hoàn thành luận văn. 5
Số hóa bởi Trung tâm Học liệu MỤC LỤC
LỜI CAM ĐOAN i
LỜI CẢM ƠN ii
MỤC LỤC iii
DANH MỤC CHỮ VIẾT TẮT v
DANH MỤC BẢNG, HÌNH VẼ vi
LỜI NÓI ĐẦU 9
CHƢƠNG 1TỔNG QUAN VỀ KỸ THUẬT GIẤU TIN VÀ THỦY VÂN 11
1.1. Một số vấn đề cơ bản về giấu tin 11
1.1.1. Khái niệm giấu tin 11
1.1.2. Phân loại các kỹ thuật giấu tin và ứng dụng 11
1.1.3. Mô hình kỹ thuật giấu tin 12
1.2. Một số vấn đề cơ bản về thủy vân 15
1.2.1. Khái niệm về thủy vân 15
3.4. Mã nguồn chương trình 59
KẾT LUẬN 67
TÀI LIỆU THAM KHẢO 68
7
Số hóa bởi Trung tâm Học liệu DANH MỤC CHỮ VIẾT TẮT, TIẾNG ANH
Chữ viết tắt
Diễn giải
Ý nghĩa
Watermarking
8
Số hóa bởi Trung tâm Học liệu DANH MỤCHÌNHVẼ
Tênhình
Ýnghĩa
Hình1.1
Phân loại các kỹ thuật giấu tin
Hình1.2
Mô hình thuật toán nhúng tin
Hình1.3
Mô hình trích tin
Hình1.4
Phân loại thủy vân theo mục đích ứng dụng
Hình1.5
Biểu đồ histogram của ảnh màu Pepper
Số hóa bởi Trung tâm Học liệu LỜI NÓI ĐẦU
Một trong những thành tựu quan trọng 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. Mọi người đều
có thể kết nối vào 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ụ Internet. 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.
Tuy nhiên việc phân phối một cách phổ biến các tài nguyên trên mạng
hiện nay luôn gặp phải vấn nạn sao chép và sử dụng không hợp pháp.Kỹ
thuật thuỷ vân đang được xem là một trong những giải pháp quan trọng
trong việc bảo vệ bản quyền và xác thực tính toàn vẹn của dữ liệu số.
Trong nhiều ứng dụng ngoài việc trích thủy vân người ta còn muốn khôi
phục lại ảnh gốc. Vì vậy những năm gần đây xuất hiện một hướng nghiên
cứu mới là thủy vân thuận nghịch. Trong giấu tin và thủy vân thuận nghịch
thường sử dụng các phép biến đổi nguyên khả nghịch như dịch chuyển
Histogram, Wavelet nguyên, phép biến đổi tương phản, phép biến đổi mở
rộng hiệu, ….Trong số đó kỹ thuật giấu tin và thủy vân dựa trên phép biến
đổi mở rộng hiệu đạt được hiệu quả cao nên đang được nhiều người quan
tâm.Chính vì vậy em chọn đề tài “Thủy vân thuận nghịch sử dụng phép
biến đổi mở rộng hiệu”làm luận văn tốt nghiệp của mình.
Bố cục của Luận văn gồm 3 chương như sau:
Chương 1: Tổng quan về kỹ thuật giấu tin và thuỷ vân.
Chương 2: Một số lược đồ giấu tin và thuỷ vân thuận nghịch.
Chương 3: Chương trình thử nghiệm.
10
trung vào các kỹ thuật giấu tin sao cho người khác rất vất vả, khó khăn mới
phát hiện được đối tượng có chứa thông tin mật bên trong.
1.1.2. Phân loại các kỹ thuật giấu tin và ứng dụng
Dựa theo mục đích sử dụng, ta có chia các lược đồ giấu tin thành hai
nhóm chính giấu tin và thủy vân:
- Thủy vân số: Là nhúng một lượng thông tin có ích vào các sản phẩm số.
Có thể chia thành hai loại thủy vân như sau: Thủy vân bền vững và
thủy vân dễ vỡ. Thủy vân bền vững nghiên cứu đến việc nhúng những mẩu
tin với yêu cầu độ bền vững cao của thông tin được giấu trước những biến
đổi của môi trường dữ liệu. Còn thủy vân dễ vỡ quan tâm đến thông tin
giấu sẽ bị sai lệch nếu có bất kỳ sự thay đổi nào trên dữ liệu chứa thông tin giấu.
12
Số hóa bởi Trung tâm Học liệu - Giấu tin mật: Với kỹ thuật giấu tin mật này luôn quan tâm đến tính
che giấu thông tin, với mục đích nhằm làm sao cho việc phát hiện được đối
tượng có chứa thông tin mật ở bên trong hay không; nếu phát hiện có giấu
tin thì việc giải mã thông tin mật cũng sẽ mất rất nhiều thời gian và rất khó
thực hiện được. Các kỹ thuật giấu tin cũng rất quan tâm đến lượng tin có
thể giấu được.
Như vậy, kỹ thuật giấu tin có thể được phân loại như hình sau:
Giấu tin
Giấu tin mật Thủy vân số
Hình 1.1. Phân loại các kỹ thuật giấu tin
1.1.3. Mô hình kỹ thuật giấu tin
Giống như các lược đồ mã hóa thông tin, một kỹ thuật giấu tin gồm
thuật toán nhúng tin và thuật toán trích tin. Theo [5], sơ đồ của thuật toán
Trong hình 1.3 đã chỉ ra các nhiệm vụ của quá trình giải mã thông tin
đã được giấu.Quá trình giải mã này phải được thực hiện thông qua một bộ
giải mã tương ứng với bộ nhúng thông tin và kết hợp với khóa để giải mã
tin. Khóa để giải mã tin này có thể giống hay khác với khóa đã nhúng tin.
Kết quả thu được bao gồm môi trường gốc và thông tin đã được che giấu.
Tùy theo các trường hợp cụ thể, thông tin tách được ra có thể phải cần xử
lý, kiểm định và so sánh với thông tin đem giấu ban đầu. Thông qua dữ liệu
được tách ra từ môi trường chứa thông tingiấu, người ta có thể biết được
trong quá trình truyền tải, phân phát dữ liệu có bị xâm phạm, tấn công hay không.
Đối với các hệ thống giấu thông tin mật này rất quan tâm đến tính an
toàn và bảo mật thông tin của dữ liệu cần giấu. Hệ thống giấu tin mật có độ
bảo mật cao nếu có độ phức tạp của các thuật toán thám mã khó có thể thực
hiện được trên máy tính. Tuy nhiên, cũng có các hệ thống chỉ quan tâm đến
số lượng thông tin có thể được che giấu, hay quan tâm đến sự ảnh hưởng
của thông tin mật đến các môi trường chứa dữ liệu.
15
Số hóa bởi Trung tâm Học liệu 1.2. Một số vấn đề cơ bản về thủy vân
1.2.1.Khái niệm về thủy vân
Thuỷ vân (Watermarking) là kỹ thuật nhúng thông tin vào dữ liệu môi
trường (đa phương tiện) như: tệp ảnh, tệp video, tệp âm thanh… nhằm bảo
vệ dữ liệu đa phương tiện trong quá trình trao đổi không an toàn. Thông tin
nhúng (dấu thủy vân) được dùng để xác định tính toàn vẹn, phát hiện vị trí
bị thay đổi hoặc chứng minh quyền tác giả đối với dữ liệu chứa dấu thủy vân.
1.2.2.Phân loại thủy vân
Dựa vào mục đích sử dụng, thủy vân số có thể được phân loại như hình sau :
đổi định dạng dữ liệu hoặc các lỗi đường truyền. Các lược đồ thủy vân bán
dễ vỡ thường sử dụng trong bài toán phát hiện sự giả mạo nội dung, xuyên
tạc thông tin.
1.2.3. Các ứng dụng của thuỷ vân với ảnh số
Các ứng dụng của thuỷ vân đối với ảnh số bao gồm các lĩnh vực như
bảo vệ bản quyền, xác thực ảnh và bảo toàn dữ liệu, giấu dữ liệu và gán
nhãn ảnh, ta sẽ lần lượt đề cập từng ứng dụng.
a) Bảo vệ bản quyền
Mục đích của thuỷ vân với bảo vệ bản quyền là gắn một “dấu hiệu” vào
dữ liệu ảnh mà có thể xác định được người nắm giữ bản quyền. Và ta cũng
có thể gắn thêm một dấu hiệu khác gọi là vân tay để xác định người dùng
của sản phẩm. Dấu hiệu có thể là một dãy số như mã hàng hoá quốc tế, một
message hoặc một logo… Thuật ngữ thuỷ vân xuất phát từ phương thức
đánh dấu giấy tờ với một logo từ thời xa xưa với mục đích tương tự.
b) Xác thực ảnh và bảo toàn dữ liệu
Một ứng dụng khác của thuỷ vân là xác thực ảnh và phát hiện giả mạo.
Ảnh số ngày càng được sử dụng như các bằng chứng trước pháp luật ngày
nay. Vấn đề là cần xác thực được tính hợp pháp của ảnh này. Thuỷ vân
17
Số hóa bởi Trung tâm Học liệu được sử dụng ở đây để xác định xem ảnh là nguyên bản hay đã chịu tác
động của con người, bằng các ứng dụng xử lý ảnh. Thuỷ vân được dấu lúc
đầu phải mang tính chất không bền vững, để bất kỳ sự thay đổi nhỏ nào tới
ảnh cũng có thể làm hỏng thuỷ vân hoặc phát hiện được thay đổi đối với
thuỷ vân này. Tuy vậy, thuỷ vân vẫn phải tồn tại với các phép biến đổi ảnh
thông thường như chuyển đổi định dạng, lấy mẫu, nén…
c) Giấu dữ liệu và gán nhãn ảnh
Khả năng mang tin cao: Với yêu cầu này, lượng tin cần thêm vào ảnh phải
đủ dùng trong ứng dụng mà không làm thay đổi quá nhiều chất lượng ảnh.
Tuy vậy, việc làm tốt cả ba yêu cầu trên là một điều rất khó. Để dấu
thuỷ vân trong ảnh thì ta bắt buộc phải thay đổi dữ liệu ảnh. Ta có thể tăng
tính bền vững cho thuỷ vân bằng cách tăng lượng thay đổi ảnh cho mỗi đơn
vị tin cần dấu. Nhưng, nếu thay đổi quá nhiều thì tính ẩn không còn được
đảm bảo nữa. Còn nếu thay đổi ảnh quá ít thì các yếu tố dùng để xác định
thuỷ vân trong ảnh sau các phép tấn công có thể không đủ để xác định thuỷ
vân. Nếu thông tin được dấu quá nhiều thì cũng dễ làm thay đổi chất lượng
ảnh, và làm giảm tính bền vững. Vì vậy, lượng thay đổi ảnh lớn nhất có thể
chấp nhận và tính bền vững là hai nhân tố quyết định cho khối lượng tin
được dấu trong ảnh.
Còn đối với các ứng dụng để phát hiện giả mạo ảnh gốc thì thuỷ vân
nhúng vào phải có tính giòn (fragile) nghĩa là sẽ bị vỡ nếu chịu sự biến đổi
mất thông tin. Một cách thực hiện điều này mà vẫn đảm bảo tính ẩn của
thuỷ vân là dấu nó vào các phần dữ liệu ít đáng chú ý về mặt trực giác
(perceptual insignificant). Đối với ảnh, đó có thể là các bít thấp của các
điểm ảnh (LSB).
Loại thuỷ vân nửa giòn (semi-fragile) được dùng trong việc phân biệt
các loại biến đổi mất thông tin đã được sử dụng: Biến đổi mất thông tin
nhưng không thay đổi nội dung và biến đổi mất thông tin gây thay đổi nội
19
Số hóa bởi Trung tâm Học liệu dung. Ví dụ, với các ứng dụng xác thực thì cần có loại thuỷ vân phân biệt
giữa các biến đổi mất thông tin như nén nhưng vẫn đảm bảo tính nguyên
vẹn dữ liệu và biến đổi làm thay đổi tính toàn vẹn dữ liệu như các việc xử
lý ảnh có mục đích. Và yêu cầu đối với loại ứng dụng này là phải chỉ ra
1.3.2. Histogram của ảnh
Histogram là khái niệm cơ bản trong xử lý ảnh. Histogram là bảng
thống kê tần số giá trị cường độ sáng của các điểm ảnh. Đối với ảnh màu,
cường độ sáng của một điểm ảnh được xác định theo công thức:
trong đó: là giá trị các thành phần màu và là cường độ sáng của
điểm ảnh.
Ví dụ: từ ảnh màu pepper ta có thể dễ dàng xác định được biểu đồ
histogram tương ứng như hình 1.5. (a) ảnh pepper.bmp
(b) Biểu đồ histogram
Hình 1.5. Biểu đồ histogram của ảnh màu Pepper
21
Số hóa bởi Trung tâm Học liệu 1.3.3. Chất lƣợng ảnh
Như đã đề cập ở trên, chất lượng ảnh chứa tin là một trong những yếu
tố quan trọng trong giấu tin mật, đặc biệt là thủy vân số. Chất lượng ảnh
chứa tin có thể được đánh giá bằng hệ số (Peak Signal-to-Noise
Ratio). Lược đồ có hệ số càng lớn thì chất lượng ảnh chứa tin càng
cao. Hệ số của ảnh chứa tin so với ảnh gốc kích thước
được tính theo công thức:
trong đó, là giá trị cực đại của điểm ảnh và (Mean Square
Error) được xác định theo công thức:
giữ bí mật
- F B
m*n
và là ma trận môi trường để giấu tin
- F B
m*n
là ma trận khóa và giá trị của ma trận K phải được giữ bí mật
- b là bít nhị phân cần giấu ( b=0 hoặc b=1)
Output
Nếu thuật toán thực hiện thành công, thì kết quả thu được là ma trận G
( G B
m*n
) được biến đổi tối đa một phần tử từ ma trận F và G thỏa mãn
hai bất biến sau:
+ 0<SUM(G K) < SUM(K) (1.1)
+ SUM(G K) mod 2 = b (1.2)
Theo đầu ra của thuật toán, khi nhận được G để kiểm tra ma trận G có
giấu thông tin hay không chúng ta sẽ cần phải kiểm tra G có thỏa mãn bất
biết (1.1) hay không. Với bất biến (1.2) thì quá trình giải mã thông tin trong
ma trận G có thể dễ dàng xác định được G chứa giá trị bit đã giấu bằng 0
hay bằng 1 theo (1.3)
23
Số hóa bởi Trung tâm Học liệu B = SUM(G K) mod 2 (1.3)
Nội dung thuật toán:
Bƣớc 1: Đặt s = SUM(F K)
- G = F
Trường hợp 3:
Nếu và thì
- Chọn ngẫu nhiên phần tử (i,j) thỏa mãn =1
-
- G = F
Dựa vào thuật toán nhúng tin của Wu-Lee, ta dễ dàng nhận thấy, kết
thúc thuật toán nhúng tin, nếu khối ảnh G thỏa mãn điều kiện:
Thì khối ảnh G có chứa một bít tin mật. Và việc khôi phục bít tin mật
khi biết ma trận khóa bí mật K được thực biện theo công thức:
Như vậy, theo thuật toán Wu-Lee, mỗi khối gồm điểm ảnh, thuật
toán có thể nhúng 1 bít bằng cách thay đổi tối đa một phần tử của khối.
Tính bảo mật của thuật toán Wu-Lee là . Dựa trên ý tưởng này, trong
[6] trình bày lược đồ giấu tin trên ảnh nhị phân (THA) có khả năng nhúng
và tính bảo mật cao hơn so với lược đồ Wu-Lee.
Ví dụ minh hoạ:
Giả sử ta cần giấu dãy bit b
1
b
2
b
3
= 011 vào một ảnh kích thước 6x6
với ma trận khóa K có kích thước 3 như trong hình vẽ. Ta chia ảnh F
thành 4 khối ảnh nhỏ với mỗi khối kích thước là 3 ta thu được F1, F2,
F3, F4.
25
0
1
Dữ liệu cần giấu: b
1
b
2
b
3
=011
0
0
0
1
0
1
1
0
1
1
0
0
0
1
0
0
1
0
1
1
0
0
1
0 0
1
0
1
1
0
1
1
1
0
1 0
0
0
0
1
0
F3 F4
K G3
chất (2) và (3). Do SUM(F4 K) = SUM(K) -1 nên chúng ta chọn ngẫu
nhiên phần tử (i,j) mà F4
(i,j)
= 1 mà K
i,j
= 1 và thay đổi F4
(i,j)
= 0. Giả sử ta
chọn phần tử (3,3) kết quả sẽ thu được như G4.
Copyright: Tài liệu đại học ©