Sự phát triển nhanh chóng của truyền thông máy tính và internet ngày nay làm cho
các dữ liệu trao đổi qua mạng rất thuận tiện và nhanh chóng. Điều đó đồng thời
cũng tạo thuận lợi cho các hành vi sao chép trái phép, vi phạm bản quyền, xuyên tạc
thông tin, giả mạo thông tin các sản phẩm dữ liệu số. Việc bảo vệ bản quyền các tác
phẩm số là một yêu cầu cấp thiết trong các ứng dụng của công nghệ thông tin vào
đời sống.
Đã có nhiều phương pháp cả phần cứng và phần mềm được nghiên cứu và ứng
dụng để bảo vệ bản quyền các sản phẩm số. Các phương pháp sử dụng phần cứng
hiệu quả nhưng thường có chi phí cao trong sản xuất và phân phối, do vậy người ta
thường thay thế hoặc kết hợp với các thuật toán cài đặt phần mềm để có thể bảo vệ
chống lại các hành vi vi phạm bản quyền các dữ liệu này. Thủy vân số được nghiên
cứu trong hơn mười năm trở lại đây đã dần chứng tỏ là một giải pháp khả thi với chi
phí thấp và tính đảm bảo cao cho vấn đề bảo vệ bản quyền số.
Các nhà nghiên cứu đã có một số kết quả mạnh trong thủy vân các loại dữ liệu
đa phương tiện quen thuộc như ảnh tĩnh, nhạc số, video,… Tuy nhiên đối với loại
dữ liệu ảnh vector thì vẫn chưa có nhiều các nghiên cứu so với các loại dữ liệu số
khác, đặc biệt ở nước ta. Mặt khác trên thực tế các bản đồ vector đóng vai trò rất
quan trọng trong các Hệ thống Thông tin Địa lý (GIS). Việc tạo ra các bản đồ vector
số có độ chính xác cao đòi hỏi rất nhiều thời gian và chi phí lớn trong đo đạc, trắc
địa. Vì thế các bản đồ này không thể được phân phối và sử dụng miễn phí. Ngoài ra
có các ứng dụng đòi hỏi tính toàn vẹn cao, chống xuyên tạc, giả mạo như các bản đồ
dùng trong quân sự. Do vậy thủy vân số các bản đồ vector để bảo vệ bản quyền,
chống xuyên tạc giả mạo các bản đồ này là một hướng nghiên cứu mới mẻ và có
tính hữu dụng cao trong các ứng dụng của GIS.
Luận văn này tập trung nghiên cứu các kỹ thuật thủy vân đã và đang được sử
dụng để thủy vân bản đồ vector số, nghiên cứu và đánh giá một số thuật toán cụ thể
và một đề xuất cải tiến. Bố cục của luận văn gồm các Chương sau:
Chương 1: Tổng quan về thủy vân và cấu trúc dữ liệu không gian.
Trình bày về một số khái niệm, lịch sử và phân loại các kỹ thuật thủy vân
trong lĩnh vực giấu tin; một số khái niệm về cấu trúc dữ liệu bản đồ địa lý.
Chương này cũng trình bày tổng quan về các kết quả nghiên cứu gần đây
trên thế giới về thủy vân bản đồ vector số.
Chương 2. Một số lược đồ thủy vân. Mô tả phát biểu hình thức của một
lược đồ thủy vân tổng quát; trình bày một số lược đồ thủy vân cơ sở và một
số lược đồ thủy vân bản đồ vector trên các dữ liệu đặc thù: Dữ liệu vùng
khối và dữ liệu dạng mạng. Một đề xuất cải tiến tính bền vững của lược đồ
thủy vân được trình bày cùng các nhận xét.
Chương 3. Phát triển ứng dụng thực nghiệm. Cài đặt lược đồ thủy vân
đề xuất cùng các kết quả thực nghiệm và các nhận xét nhằm đưa sản phẩm
vào ứng dụng thực tế.
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
-------------------------------------
HÀN NGỌC ĐỨC
NGHIÊN CỨU CÁC THUẬT TOÁN ỨNG
DỤNG TRONG BẢO VỆ BẢN QUYỀN BẢN ĐỒ
SỐ
LUẬN VĂN THẠC SĨ KHOA HỌC
Hà Nội – Năm 2010
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
HÀN NGỌC ĐỨC
NGHIÊN CỨU CÁC THUẬT TOÁN ỨNG DỤNG
TRONG BẢO VỆ BẢN QUYỀN BẢN ĐỒ SỐ
Chuyên ngành:
Đảm bảo Toán học cho Máy tính và các Hệ thống Tính toán
LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. Đặng Văn Đức
Hà Nội - 2010
Hàn Ngọc Đức
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn thạc sĩ khoa học “Nghiên cứu các thuật toán ứng dụng
trong bảo vệ bản quyền bản đồ số” là công trình nghiên cứu của riêng tôi. Mọi số
liệu, bảng biểu, kết quả, trích dẫn trong luận văn là trung thực với các kết quả thực
nghiệm và danh mục tài liệu tham khảo.
Tác giả luận văn,
Hàn Ngọc Đức
i
Hàn Ngọc Đức
MỤC LỤC
LỜI CAM ĐOAN .................................................................................................................. i
MỤC LỤC ............................................................................................................................ ii
CÁC THUẬT NGỮ, TỪ VIẾT TẮT ................................................................................ iv
DANH MỤC BẢNG............................................................................................................. v
DANH MỤC HÌNH ............................................................................................................ vi
CÁC THUẬT TOÁN .........................................................................................................vii
LỜI NÓI ĐẦU ...................................................................................................................... 1
Chương 1.
GIAN
1.1.
Thủy vân.................................................................................................................. 3
1.1.1.
1.1.2.
1.1.3.
1.1.4.
1.1.5.
1.2.
Một số khái niệm .............................................................................................. 3
Lịch sử của Thủy vân ....................................................................................... 4
Các ứng dụng của thủy vân số ......................................................................... 6
Phân loại các kỹ thuật thủy vân ....................................................................... 8
Các yêu cầu của một lược đồ thủy vân .......................................................... 10
Cấu trúc dữ liệu không gian .................................................................................. 11
1.2.1.
1.2.2.
1.2.3.
1.2.4.
1.3.
TỔNG QUAN VỀ THỦY VÂN VÀ CẤU TRÚC DỮ LIỆU KHÔNG
3
Một số khái niệm ............................................................................................ 11
Mô hình dữ liệu Raster .................................................................................. 13
Mô hình dữ liệu vector ................................................................................... 14
So sánh mô hình raster và vector................................................................... 16
Tình hình nghiên cứu hiện nay về thủy vân bản đồ vector ................................... 17
1.3.1.
1.3.2.
1.3.3.
Chương 2.
Bảo vệ bản quyền bản đồ số .......................................................................... 17
Các hướng tiếp cận thủy vân bản đồ vector số .............................................. 17
Các thuật toán thủy vân khác ........................................................................ 23
MỘT SỐ LƯỢC ĐỒ THỦY VÂN ............................................................. 24
2.1.
Lược đồ thủy vân tổng quát .................................................................................. 24
2.2.
Một số thuật toán thủy vân cơ sở .......................................................................... 26
2.2.1.
2.2.2.
2.3.
Thuật toán thủy vân trong miền quan sát ...................................................... 26
Thuật toán thủy vân trong miền tần số .......................................................... 30
Một số lược đồ thủy vân bản đồ vector số ............................................................ 33
2.3.1.
2.3.2.
2.3.3.
2.3.4.
Các đặc trưng khác biệt của thủy vân bản đồ vector .................................... 33
Thủy vân bản đồ vector dạng miền ................................................................ 37
Thuật toán thủy vân mạng đường phố ........................................................... 46
Thuật toán thủy vân đề xuất ........................................................................... 53
ii
Hàn Ngọc Đức
Chương 3.
PHÁT TRIỂN ỨNG DỤNG THỬ NGHIỆM ............................................ 60
3.1.
Giới thiệu ứng dụng .............................................................................................. 60
3.2.
Lựa chọn cấu trúc dữ liệu file bản đồ vector......................................................... 61
3.2.1.
3.2.2.
Các thành phần một shapefile ....................................................................... 62
Cấu trúc file main (.shp) ................................................................................ 62
3.3.
Môi trường phát triển ............................................................................................ 63
3.4.
Kiến trúc ứng dụng................................................................................................ 63
3.4.1.
3.4.2.
3.4.3.
3.4.4.
Chuyển đổi cấu trúc dữ liệu ........................................................................... 63
Tiền xử lý và phân đoạn bản đồ ..................................................................... 65
Nhúng thủy vân .............................................................................................. 65
Trích thủy vân ................................................................................................ 66
3.5.
Giao diện ứng dụng ............................................................................................... 67
3.6.
Kết quả thực nghiệm ............................................................................................. 68
3.6.1.
3.6.2.
3.6.3.
Dữ liệu thực nghiệm....................................................................................... 68
Lựa chọn các tham số thủy vân ..................................................................... 68
Kết quả thực nghiệm ...................................................................................... 69
KẾT LUẬN ......................................................................................................................... 71
TÀI LIỆU THAM KHẢO ................................................................................................. 73
PHỤ LỤC............................................................................................................................ 75
A1. Phép biến đổi Fourier rời rạc ..................................................................................... 75
A1.1. Biến đổi Fourier rời rạc một chiều ..................................................................... 75
A1.2. Biến đổi Fourier rời rạc hai chiều ...................................................................... 75
A2. Phép biến đổi Cosin rời rạc ....................................................................................... 75
A3. Cấu trúc file Shapefile ............................................................................................... 76
A3.1. Main file header .................................................................................................. 76
A3.2. Các header bản ghi ............................................................................................. 78
A3.3. Nội dung bản ghi ................................................................................................. 78
iii
Hàn Ngọc Đức
CÁC THUẬT NGỮ, TỪ VIẾT TẮT
STT
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
Ý nghĩa
Ảnh số tạo bởi các điểm ảnh.
Bản quyền, quyền tác giả.
Mật mã học.
Discrete cosine transform - Phép biến đổi Cosin rời rạc.
Giải mã.
Discrete Fourier transform - Phép biến đổi Fourier rời
rạc.
Dijkstra distance Khoảng cách Dijkstra trên đồ thị.
Douglas Peucker Phép giản lược cấu trúc dữ liệu vector dựa trên một
simplification
ngưỡng xác định do
DWT
Discrete wavelet transform - Phép biến đổi Wavelet rời
rạc.
Embeding
Nhúng.
Encode
Mã hóa.
ESRI
Environmental Systems Research Institute.
Extracting
Trích thông tin.
GIS
Geographic Information System - Hệ thống thông tin địa
lý.
GML
Geography Markup Language.
Key
Khóa mã hóa hoặc giải mã.
LSB
Least significant bit - các bit có trọng số nhỏ nhất.
Morse
Một loại mã do Samuel Morse phát minh năm 1835.
MSE
Mean Square Error - sai số bình phương trung bình.
OEM
Original Equipment Manufacturer - Mã nhà sản xuất
thiết bị gốc.
Pixel
Điểm ảnh.
PRN
Pseudo Random Number - Số giả ngẫu nhiên.
PRNG
Pseudo Random Number Generator - Bộ sinh số giả ngẫu
nhiên.
PRNS
Pseudo Random Number Sequence - Chuỗi số giả ngẫu
nhiên.
PSNR
Peak signal-to-noise ratio, tỷ số tín hiệu trên nhiễu đỉnh.
Raster map
Cấu trúc dữ liệu bản đồ dạng raster.
RMSE
Root mean squared error - căn bậc hai của MSE.
Shapefile
Cấu trúc dữ liệu mở của ESRI để lưu trữ bản đồ số dạng
vector.
Steganography
Giấu thông tin mật.
Vector map
Cấu trúc dữ liệu bản đồ dạng vector.
Watermark
Dấu thủy vân, thủy ấn.
Watermarking
Thủy vân, đánh dấu ẩn.
Từ, thuật ngữ
Bitmap
Copyright
Cryptography
DCT
Decode
DFT
iv
Hàn Ngọc Đức
DANH MỤC BẢNG
Bảng 1-1. Phân biệt Giấu tin mật và Thủy vân số ......................................................4
Bảng 1-2. So sánh mô hình raster và vector .............................................................16
Bảng 3-1. Các bản đồ thực nghiệm khả năng nhúng ................................................70
Bảng A-1. Mô tả của Main file header ......................................................................76
Bảng A-2. Các giá trị của shape type. .......................................................................77
Bảng A-3. Mô tả header bản ghi. ..............................................................................78
Bảng A-4. Nội dung bản ghi biểu diễn điểm. ...........................................................78
Bảng A-5. Nội dung bản ghi biểu diễn đa điểm........................................................79
Bảng A-6. Nội dung bản ghi chi tiết đa đoạn............................................................80
Bảng A-7. Nội dung bản ghi đa giác. ........................................................................82
v
Hàn Ngọc Đức
DANH MỤC HÌNH
Hình 1-1. Phân loại các kỹ thuật giấu thông tin của Pfitzmann[18] ...........................9
Hình 1-2. Tam giác 3 yêu cầu của lược đồ thủy vân tốt ...........................................11
Hình 1-3. Các tầng bản đồ.........................................................................................15
Hình 1-4. Minh họa đơn giản của lược đồ Bill Huber ..............................................19
Hình 2-1. Bộ nhúng thủy vân tổng quát ....................................................................25
Hình 2-2. Bộ tách thủy vân với các đầu vào có thể ..................................................25
Hình 2-3. Mô hình của lược đồ giấu tin CPT [22] ....................................................29
Hình 2-4. Lược đồ xử lý thuật toán CPT cải tiến ......................................................30
Hình 2-5. Phép phân tích ảnh wavelet 3 mức ...........................................................32
Hình 2-6. Các đa giác biểu diễn tòa nhà trên bản đồ ................................................38
Hình 2-7. Nhúng bit bằng phép co giãn đa giác........................................................40
Hình 2-8. Mã hóa bit 1 hoặc 0 vào 𝑥𝑚𝑎𝑥 bằng lượng tử hóa ..................................43
Hình 2-9. Quá trình lược giản bản đồ bằng thuật toán Douglas-Peucker[30] ..........48
Hình 2-10. Bản đồ với các điểm đặc trưng (bậc >2) .................................................49
Hình 2-11. Minh họa quá trình nhúng trên một nhóm của bản đồ đã phân đoạn .....52
Hình 3-1. Tổ chức của một main file ........................................................................62
Hình 3-2. Các lớp điểm, shapefile và đa đoạn ..........................................................64
Hình 3-3. Biểu đồ hoạt động quá trình tiền xử lý và phân đoạn ...............................65
Hình 3-4. Cấu trúc thông tin file lưu khóa 𝒦 ...........................................................66
Hình 3-5. Giao diện chính chương trình ...................................................................67
Hình 3-6. Hiển thị bản đồ sau khi nhúng thủy vân. ..................................................67
Hình 3-7. Hiển thị kết quả trích thủy vân. ................................................................68
Hình 3-8. Khả năng nhúng bit trên bản đồ đường thành phố Hà Nội .......................69
Hình 3-9. So sánh khả năng nhúng của một số bản đồ thực tế .................................70
Hình A-1. Ví dụ một đa giác gồm hai vành. .............................................................81
Hình A-2. Lưu trữ đa giác trong shapefile. ...............................................................82
vi
Hàn Ngọc Đức
CÁC THUẬT TOÁN
Thuật toán 2-1. Thủy vân ảnh nhị phân ....................................................................27
Thuật toán 2-2. Thủy vân bản đồ miền bằng co giãn đa giác ...................................43
Thuật toán 2-3. Trích thủy vân đã nhúng ..................................................................44
Thuật toán 2-4. Thuật toán Douglas-Peucker ...........................................................47
Thuật toán 2-5. Map_Segmentation Algorithm ........................................................49
Thuật toán 2-6. Thuật toán nhúng thủy vân đề xuất .................................................56
vii
Hàn Ngọc Đức
LỜI NÓI ĐẦU
Sự phát triển nhanh chóng của truyền thông máy tính và internet ngày nay làm cho
các dữ liệu trao đổi qua mạng rất thuận tiện và nhanh chóng. Điều đó đồng thời
cũng tạo thuận lợi cho các hành vi sao chép trái phép, vi phạm bản quyền, xuyên tạc
thông tin, giả mạo thông tin các sản phẩm dữ liệu số. Việc bảo vệ bản quyền các tác
phẩm số là một yêu cầu cấp thiết trong các ứng dụng của công nghệ thông tin vào
đời sống.
Đã có nhiều phương pháp cả phần cứng và phần mềm được nghiên cứu và ứng
dụng để bảo vệ bản quyền các sản phẩm số. Các phương pháp sử dụng phần cứng
hiệu quả nhưng thường có chi phí cao trong sản xuất và phân phối, do vậy người ta
thường thay thế hoặc kết hợp với các thuật toán cài đặt phần mềm để có thể bảo vệ
chống lại các hành vi vi phạm bản quyền các dữ liệu này. Thủy vân số được nghiên
cứu trong hơn mười năm trở lại đây đã dần chứng tỏ là một giải pháp khả thi với chi
phí thấp và tính đảm bảo cao cho vấn đề bảo vệ bản quyền số.
Các nhà nghiên cứu đã có một số kết quả mạnh trong thủy vân các loại dữ liệu
đa phương tiện quen thuộc như ảnh tĩnh, nhạc số, video,… Tuy nhiên đối với loại
dữ liệu ảnh vector thì vẫn chưa có nhiều các nghiên cứu so với các loại dữ liệu số
khác, đặc biệt ở nước ta. Mặt khác trên thực tế các bản đồ vector đóng vai trò rất
quan trọng trong các Hệ thống Thông tin Địa lý (GIS). Việc tạo ra các bản đồ vector
số có độ chính xác cao đòi hỏi rất nhiều thời gian và chi phí lớn trong đo đạc, trắc
địa. Vì thế các bản đồ này không thể được phân phối và sử dụng miễn phí. Ngoài ra
có các ứng dụng đòi hỏi tính toàn vẹn cao, chống xuyên tạc, giả mạo như các bản đồ
dùng trong quân sự. Do vậy thủy vân số các bản đồ vector để bảo vệ bản quyền,
chống xuyên tạc giả mạo các bản đồ này là một hướng nghiên cứu mới mẻ và có
tính hữu dụng cao trong các ứng dụng của GIS.
Luận văn này tập trung nghiên cứu các kỹ thuật thủy vân đã và đang được sử
dụng để thủy vân bản đồ vector số, nghiên cứu và đánh giá một số thuật toán cụ thể
và một đề xuất cải tiến. Bố cục của luận văn gồm các Chương sau:
1
Hàn Ngọc Đức
Chương 1: Tổng quan về thủy vân và cấu trúc dữ liệu không gian.
Trình bày về một số khái niệm, lịch sử và phân loại các kỹ thuật thủy vân
trong lĩnh vực giấu tin; một số khái niệm về cấu trúc dữ liệu bản đồ địa lý.
Chương này cũng trình bày tổng quan về các kết quả nghiên cứu gần đây
trên thế giới về thủy vân bản đồ vector số.
Chương 2. Một số lược đồ thủy vân. Mô tả phát biểu hình thức của một
lược đồ thủy vân tổng quát; trình bày một số lược đồ thủy vân cơ sở và một
số lược đồ thủy vân bản đồ vector trên các dữ liệu đặc thù: Dữ liệu vùng
khối và dữ liệu dạng mạng. Một đề xuất cải tiến tính bền vững của lược đồ
thủy vân được trình bày cùng các nhận xét.
Chương 3. Phát triển ứng dụng thực nghiệm. Cài đặt lược đồ thủy vân
đề xuất cùng các kết quả thực nghiệm và các nhận xét nhằm đưa sản phẩm
vào ứng dụng thực tế.
Luận văn được thực hiện nhờ có sự chỉ dẫn tận tình, chu đáo của PGS. TS.
Đặng Văn Đức, cùng với việc tạo điều kiện thuận lợi của Viện Đào tạo Sau đại học,
Viện Công nghệ Thông tin. Tác giả xin gửi lời cảm ơn chân thành và tốt đẹp nhất.
Đồng thời tôi xin bày tỏ sự biết ơn sâu sắc tới gia đình, đồng nghiệp và những
người thân thiết đã động viên giúp đỡ trong suốt quá trình thực hiện luận văn.
Do thời gian thực hiện và kiến thức của tác giả còn hạn chế nên luận văn này
không thể tránh khỏi các thiếu sót về nội dung cũng như hình thức trình bày. Tác
giả mong muốn nhận được sự cảm thông, góp ý, nhận xét của các quý thày cô và
người đọc để tác giả có thể hoàn thiện và tiếp tục theo các hướng nghiên cứu sau
này.
Hà Nội, tháng 10 năm 2010.
Người thực hiện: Hàn Ngọc Đức.
2
Hàn Ngọc Đức
Chương 1.
TỔNG QUAN VỀ THỦY VÂN VÀ CẤU TRÚC
DỮ LIỆU KHÔNG GIAN
1.1. Thủy vân
1.1.1. Một số khái niệm
Lý thuyết giấu tin thường được nghiên cứu theo hai khuynh hướng chính là
watermarking và steganography. Watermark được biết đến với tên gọi tiếng Việt là
thủy vân (còn gọi là thủy ký, thủy ấn). Thủy vân số (digital watermarking) là quá
trình nhúng thông tin vào một tín hiệu số theo cách sao cho khó có thể gỡ bỏ chúng
khỏi vật mang. Thông tin chèn vào có thể dưới dạng ảnh, dạng văn bản, hoặc tổng
quát là một chuỗi bit có ý nghĩa nào đó. Giấu tin mật (steganography) là nghệ thuật
và khoa học ẩn giấu thông tin theo cách mà không ai ngoài người gửi và người nhận
có thể phát hiện sự tồn tại của thông điệp giấu.
Hệ thống thủy vân, hay còn thường được gọi trong nghiên cứu lý thuyết giấu
tin là lược đồ thủy vân, là hệ thống cho phép nhúng thông tin mật và trích thông tin
mật đó theo một phương pháp có cơ sở đáng tin cậy. Về nguyên lý cơ bản thì một
hệ thống thủy vân hiện nay có thể xem như một hệ mã đối xứng do nó sử dụng cùng
khóa để nhúng và trích thủy vân. Nhúng (hay mã hóa) thủy vân là quá trình đưa dấu
thủy vân vào đối tượng mang tin (còn gọi là vật mang, dữ liệu phủ), còn trích (hay
giải mã, phát hiện) thủy vân là quá trình lấy ra hoặc chứng minh sự tồn tại của dấu
thủy vân trong dữ liệu đang xét. Đối tượng mang tin trong nghiên cứu thủy vân số
thường là các dạng dữ liệu đa phương tiện như ảnh tĩnh, âm thanh, video, văn
bản,… và với mỗi dạng dữ liệu với các đặc trưng cụ thể thì thường có các lược đồ
thủy vân hiệu quả cho riêng dạng dữ liệu đó.
Các tham số bí mật (nếu có) được sử dụng trong quá trình nhúng và trích
thông tin được gọi là các khóa bí mật. Chúng được chia sẻ giữa người gửi và người
nhận thông tin (trong giấu tin mật), hoặc được giữ kín bởi người chủ sở hữu để có
thể chứng minh quyền tác giả đối với dữ liệu số (trong thủy vân số).
3
Hàn Ngọc Đức
Hai khái niệm giấu tin mật và thủy vân số đôi khi được coi là đồng nghĩa và
nhiều kỹ thuật có thể được sử dụng trong cả hai nhánh nghiên cứu này của lý thuyết
giấu tin. Tuy nhiên, về tính chất thì các nhà nghiên cứu phân biệt giấu tin mật với
thủy vân số theo Bảng 1-1.
Bảng 1-1. Phân biệt Giấu tin mật và Thủy vân số
Nội dung
Mục đích
Giấu tin
Thủy vân số
"Ký gửi" thông tin trên vật "Nhúng" thông tin vào, coi là
mang để truyền từ nơi này một phần của vật mang.
đến nơi khác.
Thông tin cần Dữ liệu được đem giấu
Chính vật mang (đối tượng
bảo vệ
dùng để giấu tin)
Lượng thông tin Lượng thông tin nhúng lớn, Lượng thông tin nhúng nhỏ đủ
nhúng
đôi khi là cả một file nhạc, để chứng minh sự có mặt của
file ảnh.
nó. VD: Logo công ty
Tính cần tách
Cần tách thông tin ra sau này Nó là một phần của vật mang,
để sử dụng. Thường là không thường để chứng thực bản
biết trước.
quyền nhờ sự có mặt của nó.
Tính chất quan Dung lượng có thể giấu càng Tính bền vững của thủy vân.
trọng nhất
lớn càng tốt.
Tính vô hình
Vô hình với cảm nhận của Có thể vô hình hoặc hữu hình
con người không có khóa
tùy ứng dụng.
Việc truyền thông tin mật đã được nghiên cứu nhiều và là nội dung chính của
lĩnh vực Mật mã học (Cryptography), bản thân đã chứa đựng các phương pháp giấu
và truyền tin mật rất mạnh. Do vậy trong thực tế những ứng dụng của thủy vân số
thường đa dạng hơn các ứng dụng của giấu tin mật.
Tuy các kỹ thuật thủy vân số mới chỉ được nghiên cứu và nở rộ khoảng hơn
chục năm gần đây nhưng chúng đã có rất nhiều ứng dụng hữu ích trong kỹ thuật số
và công nghệ thông tin ứng dụng trong đời sống. Luận văn này tập trung nghiên cứu
các thuật toán thủy vân số, đặc biệt trên dữ liệu phủ là bản đồ vector số với ứng
dụng bảo vệ bản quyền các sản phẩm này.
1.1.2. Lịch sử của Thủy vân
Mặc dù người Trung Quốc phát minh ra giấy từ hơn một nghìn năm trước đây,
nhưng các thủy vân trên giấy chỉ xuất hiện tại Italy vào khoảng năm 1282[4]. Các
4
Hàn Ngọc Đức
dấu vết được tạo ra bằng cách thêm bớt độ dày của giấy để tạo ra hình ảnh "chìm".
Khi đó các chỗ mỏng hơn của tờ giấy sẽ có độ cản sáng ít hơn, và kết hợp với nhau
tạo thành các hình thủy vân. Mục đích của việc thủy vân đó là để đánh dấu nơi sản
xuất giấy, hoặc đánh dấu thương hiệu của hãng giấy. Mặt khác, chúng có thể làm
các chữ ký bí mật, hoặc đơn giản để trang trí.
Đến thế kỷ thứ 18, thủy vân trên giấy được dùng ở Châu Âu và Châu Mỹ
nhiều hơn. Chúng được dùng để đánh dấu thương hiệu, để ghi ngày sản xuất giấy,
để ghi nhận cỡ gốc của tờ giấy, và thời gian này nó cũng được dùng để làm dấu hiệu
chống lại sự giả mạo giấy bạc và các tài liệu quan trọng.
Thuật ngữ thủy vân (watermark) được đưa ra vào cuối thế kỷ 18 và được
chuyển hóa từ thuật ngữ tiếng Đức wassermarke (mặc dù bản thân từ này cũng là từ
tiếng Đức bắt nguồn từ tiếng Anh!). Thuật ngữ này thực ra là một từ không đúng
nghĩa đen vì nước (water) không quan trọng trong việc tạo ra các dấu ẩn. Có thể
thuật ngữ đó được dùng vì có hiệu ứng trên giấy giống như là tạo ra bởi các vân
nước do sóng gây ra.
Đến tận thế kỷ 20 mới bắt đầu xuất hiện các kỹ thuật tương tự như đối với
thao tác trên các dữ liệu số như ngày nay. Vào năm 1954, Emil Hembrooke of
Muzak Corporation sắp đặt một mẫu để "thủy vân" các sản phẩm âm nhạc. Một mã
nhận dạng được chèn vào trong khúc nhạc bằng cách gắn vào từng nhịp một khía
lọc hẹp đặt tại 1kHz. Sự thiếu hụt mức năng lượng tại tần số này chỉ ra rằng khía lọc
đã được áp dụng và thời gian thiếu dùng để mã hoặc một dấu chấm hoặc một dấu
gạch. Tín hiệu nhận dạng được dùng theo mã Morse. Phát minh này được ghi nhận
bằng sáng chế vào năm 1961 tại Mỹ. Hệ thống này được hãng Muzak dùng cho tới
khoảng năm 1984.
Việc xác định khi nào thủy vân số được nghiên cứu lần đầu tiên là rất khó.
Vào năm 1979, Szepanski mô tả một máy phát hiện được mẫu có thể được đặt vào
các văn bản để nhằm chống giả mạo. Chín năm sau, Holt mô tả một phương pháp
nhúng một mã nhận dạng vào tín hiệu số. Tuy nhiên Komatsu và Tominaga vào
năm 1988 là người sử dụng thuật ngữ thủy vân số lần đầu tiên. Cho đến những năm
5
Hàn Ngọc Đức
1990 thì thuật ngữ thủy vân số mới được sử dụng rộng rãi. SPIE bắt đầu tổ chức hội
thảo chuyên ngành về Bảo mật và Thủy vân các dữ liệu đa phương tiện bắt đầu vào
năm 1999.
1.1.3. Các ứng dụng của thủy vân số
Thủy vân số có nhiều ứng dụng hữu hiệu trong việc lưu trữ, phân phối và sử dụng
thông tin số[20]. Một số ứng dụng thường gặp có thể kể ra sau đây.
1.1.3.1 Bảo vệ bản quyền và xác thực
Thủy vân số thường được sử dụng để bảo vệ bản quyền và quyền sở hữu trí tuệ của
các sản phẩm số. Trong ứng dụng này, tác giả hoặc người sáng tạo tích hợp một dấu
thủy vân chứa chữ ký quyền sở hữu trí tuệ của họ vào dữ liệu gốc và phát hành nó
như bình thường. Theo cách đó, họ có thể chứng minh được quyền sở hữu trí tuệ
của mình đối với sản phẩm đó. Chẳng hạn, trong việc kiện tụng hợp pháp và có thể
có quyền khẳng định việc giới hạn phạm vi sử dụng. Một ví dụ điển hình là hình
ảnh của Lena, một trong các bức hình nổi tiếng được dùng trong khoa học xử lý ảnh
số và được dùng trong trong ấn phẩm đầu tiên về thủy vân số mà không được sự
cho phép thật sự của người chủ sở hữu.
1.1.3.2 Ghi dấu ấn và Chữ ký số
Có thể minh họa bằng các dịch vụ kiểu pay-per-view (khách hàng phải trả tiền cho
những dịch vụ cụ thể họ sử dụng). Khách hàng sử dụng các loại dịch vụ như tải ảnh,
video và nhạc qua Internet. Các sản phẩm số được đánh dấu một cách riêng biệt với
một dấu ấn phân biệt giữa các khách hàng. Đó có thể là một số xuất xưởng thiết bị
(OEM) hoặc một mẩu thông tin nào đó. Trong trường hợp này, các phương pháp
mật mã có thể được dùng để làm tăng bảo mật dữ liệu và có thể được kết hợp với
các chữ ký số. Sự kết hợp thủy vân số với chữ ký số có nhiều ứng dụng. Để nhận
diện người sao chép bất hợp pháp hoặc người phân phối lại sản phẩm có giới hạn,
người ta dùng một hệ thống quét tác nhân tự động để theo vết và bắt được kẻ phản
bội. Do tính phổ biến của DivX và các bản quay trộm của các bộ phim mới ra lò,
những "kẻ quay trộm", rạp chiếu phim và người chiếu phim, có thể bị chỉ ra một
cách đích danh các hành động bất hợp pháp như vậy. Bởi vì kỹ thuật analogue sử
6
Hàn Ngọc Đức
dụng trọng rạp chiếu phim trên toàn thế giới, nên thủy vân số phải bền vững qua
việc thay đổi từ tín hiệu tương tự sang miền tín hiệu số. Tuy nhiên các thủy vân như
vậy có thể dễ dàng được tích hợp với sự bảo mật và đáng tin cậy hơn bằng cách sử
dụng máy chiếu số và các thiết bị số.
1.1.3.3 Bảo vệ sao chép và điều khiển thiết bị
Thủy số vân có thể được dùng để cho phép điều khiển quyền sao chép thiết bị.
Trong ứng dụng này, thiết bị ghi quét luồng dữ liệu số cho một thủy vân hiện hữu
và cho phép hoặc không cho phép hành động ghi với một bộ phim hoặc luồng dữ
liệu riêng biệt. Công nghệ như vậy có thể được mở rộng khái niệm pay-per-view và
lấp lỗ hổng giữa cách tiếp cận mật mã học và tính khả dụng của nó. Tuy nhiên, việc
thực thi trên các thiết bị đã bị can thiệp có thể sử dụng cùng thủ tục áp dụng khi
chèn cơ cấu sao chép Macro Vision và CSS DVD. Bằng cách giới hạn các DVD khả
dụng thành các bộ phát DVD tương thích, các nhà sản xuất phải tích hợp các bộ
biên mã (encoder) mới được bảo mật bởi tự điều chỉnh luật sáng chế trong các thiết
bị của họ để duy trì vị trí trên thị trường.
1.1.3.4 Giám sát truyền thông
Chi phí sản xuất các sản phẩm truyền thông như là các tin tức, show diễn, tác phẩm
điện ảnh là rất lớn, có thể tới hàng trăm nghìn USD mỗi giờ. Do đó, vấn đề quan
trọng cho các công ty sản xuất như chẳng hạn Warner Bros. Miramax, Universal
Pictures là bảo đảm quyền sở hữu trí tuệ của họ và không cho phép các hành động
phát lại bất hợp pháp. Trong trường hợp này thủy vân số có thể cho phép các cơ cấu
kỹ thuật như là TALISMAN, để tự động kiểm soát các luồng phát đi ở các node vệ
tinh trên toàn thế giới và nhận dạng các sản phẩm bị phát đi bất hợp pháp. Hơn nữa,
các kênh truyền hình có thể được kiểm soát và việc sử dụng phi pháp có thể bị ghi
vết và ghi nhận một cách cụ thể. Vào năm 1997, hai kênh phát Asian đã bị phát hiện
cố tình khai khống thời gian quảng cáo của họ và bắt các khách hàng phải trả cho
thời gian mà quảng cáo sản phẩm của họ không được phát đi. Các hệ thống máy
tính có thể được dùng để lần vết và kiểm soát các hoạt động quảng cáo trên các
kênh truyền thông và thẩm tra các giao dịch quảng cáo. Nielsen Media Research và
7
Hàn Ngọc Đức
Competitive Media Reporting đã chào hàng các hệ thống máy tính như vậy. Hiện
nay một số công ty đã sử dụng các dịch vụ giám sát truyền thông dựa trên thủy vân,
ví dụ như Teletrax dựa trên công nghệ thủy vân trên dữ liệu video của Phillips.
1.1.3.5 Xác thực dữ liệu
Thủy vân số thường được dùng để chứng minh tính xác thực của một tài liệu số xác
định. Thủy vân số chứa thông tin mà có thể được dùng để chứng minh rằng nội
dung số là không bị thay đổi. Các thao tác làm thay đổi dữ liệu sẽ phá hủy hoặc thay
đổi thủy vân tích hợp trong đó. Nếu thông tin thủy vân có thể được trích ra mà
không bị lỗi thì tính xác thực có thể được bảo đảm. Để thiết kế một thuật toán thủy
vân hiệu quả, dữ liệu thủy vân hoặc thủ tục có thể được kết nối với nội dung của tài
liệu số. Các thủy vân như thế được gọi là thủy vân dễ vỡ hoặc vapormarks.
1.1.3.6 Các ứng dụng khác
Mặc dù ứng dụng chính của thủy vân số là bảo vệ quyền sở hữu trí tuệ các sản phẩm
số, nó cũng còn có thể được dùng trong các lĩnh vực khác như là y học. Người ta sử
dụng các thủy vân số để lưu thông tin về các bệnh nhân, các chuẩn đoán, các ảnh
chụp như là X-ray hoặc ảnh cộng hưởng từ, có thể tự động liên kết với bệnh nhân.
Hơn nữa, thủy vân số cũng có thể dùng để lưu siêu dữ liệu (metadata) về chính các
tài liệu nguồn. Điều này giúp cải thiện thời gian tìm kiếm các tài liệu media dựa trên
thời gian như là âm nhạc, phim ảnh.
1.1.4. Phân loại các kỹ thuật thủy vân
Các kỹ thuật giấu thông tin có thể được phân loại theo nhiều cách khác nhau tùy
thuộc vào góc nhìn của người nghiên cứu. Một số cách phân loại phổ biến là:
Theo tính thấy được đối với người thường: Thủy vân ẩn và thủy vân hiện.
Theo tính bền vững: Thủy vân dễ vỡ; Thủy vân bền vững; thủy vân nửa dễ vỡ.
Theo miền nhúng thủy vân: Thủy vân trên miền dữ liệu không gian và thủy vân
trên miền dữ liệu biến đổi.
Theo vùng nhúng: Thủy vân toàn bộ (vật mang) và thủy vân theo khối.
8
Hàn Ngọc Đức
-
Theo kiểu dữ liệu được nhúng (dữ liệu mang): Thủy vân trong văn bản
(Text), ảnh số (Image), dữ liệu Audio, dữ liệu Video.
Hai cách phân loại các kỹ thuật thủy vân quan trọng nhất đó là:
Theo yêu cầu bản gốc khi trích:
- Thủy vân cần bản gốc: Các lược đồ thủy vân cần phải có bản gốc để có thể
trích được thủy vân.
-
Thủy vân không cần gốc: Các lược đồ mà trong đó có thể trích thủy vân từ
bản nhúng mà không cần sự tồn tại của bản gốc.
Theo miền nhúng:
- Các kỹ thuật trên miền không gian: là các lược đồ thủy vân được thực hiện
nhúng trực tiếp lên dữ liệu biểu diễn ảnh (ví dụ trên pixel trong ảnh bitmap
và dữ liệu điểm trong ảnh vector).
-
Các kỹ thuật trên miền biến đổi: là các lược đồ thủy vân mà việc nhúng và
tách thủy vân được thực hiện trên ảnh đã được biến đổi sang miền tần số theo
một phép biến đổi nào đó như DCT, DWT, DFT.
Hình 1-1 cho một cách phân loại các kỹ thuật giấu thông tin nói chung của
Pfitzmann [18], trong đó thủy vân số là một nhánh trong các kỹ thuật đánh dấu bản
quyền tác giả.
Information Hiding
(Giấu thông tin)
Covert Channels
(Các kênh truyền mật)
Steganography
(Thuật ẩn liệu)
Technical
Steganography
(Ẩn liệu kỹ thuật)
Anonymity
(Nặc danh)
Copyright Marking
(Đánh dấu bản quyền)
Robust Copyright Marking
(Đánh dấu bản quyền bền
vững)
Linguistic
Steganography
(Ẩn liệu ngôn ngữ)
Fingerprinting
(Ghi dấu vân tay)
Imperceptible
Watermarking
(Thủy vân ẩn)
Fragile Watermarking
(Thủy vân dễ vỡ)
Watermarking
(Thủy vân)
Visible
Watermarking
(Thủy vân hiện)
Hình 1-1. Phân loại các kỹ thuật giấu thông tin của Pfitzmann[18]
9
Hàn Ngọc Đức
1.1.5. Các yêu cầu của một lược đồ thủy vân
Một lược đồ thủy vân tốt đòi hỏi một số yêu cầu mà về cơ bản có xu hướng mâu
thuẫn nhau về khả năng đáp ứng [10]:
Tính bảo mật (Security): Hiện nay, tính hiệu quả của một thuật toán thủy vân
không thể dựa trên sự bí mật về phương pháp nhúng, mà thuật toán nhúng phải
được coi là công khai. Các thuật toán này thường sử dụng một khóa mật để sinh
thủy vân cho mục đích bảo mật.
Tính vô hình (Invisibility):
-
Tính vô hình giác quan: Các nhà nghiên cứu thường cố giấu thủy vân sao cho
chúng khó có thể được phát hiện. Yêu cầu này lại mâu thuẫn với các yêu cầu
khác như là tính bền vững, bảo mật. Do vậy các đặc tính của hệ thị giác
người (human visual system - HVS) đối với các ảnh và hệ thính giác người
(human auditory system - HAS) cần được xem xét để thỏa mãn được tính
bền vững trong khi giác quan con người không phân biệt được sự sai khác.
-
Tính vô hình thống kê: Một người không có quyền thì không phát hiện được
thủy vân bằng các phương pháp thống kê. Ví dụ, kẻ gian có thể trích được
dấu nhúng từ một số lượng rất lớn các sản phẩm đã nhúng thủy vân với cùng
một mã, theo cách tấn công thống kê.
Tính bền vững (robustness):
Các ảnh số thường là đối tượng của nhiều loại biến dạng, chẳng hạn như việc
nén có tổn hao, lọc bỏ, thay đổi kích thước, tăng cường độ tương phản, cắt xén,
quay, ... Dấu thủy vân phải được tìm ra sau khi ảnh đã trải qua các biến dạng
như vậy. Thuật toán sẽ bền vững hơn nếu như dấu thủy vân được đặt vào vùng
quan trọng của tín hiệu ảnh. Ví dụ, một thủy vân giấu trong vùng không quan
trọng sẽ không tồn tại được khi bị nén tổn hao. Hơn nữa, khả năng chống chịu
qua các thao tác hình học như là dịch chuyển, thay đổi kích thước, quay, cắt xén,
... vẫn còn đang là vấn đề cần được nghiên cứu, trong khi các thao tác đó là
không thể tránh được trong quá trình sử dụng.
Trích thủy vân: Xác suất bị lỗi.
10
Hàn Ngọc Đức
Khi trích thủy vân thậm chí cả khi không có các tấn công thì tín hiệu trích được
cũng có thể có xác suất lỗi nào đó. Yêu cầu là xác suất này phải nhỏ trong giới
hạn cho phép.
Dung lượng giấu tin (bit rate)
Thuật toán thủy vân phải nhúng được một số lượng bit vào vật mạng. Số lượng
bit phụ thuộc vào từng ứng dụng.
Tính bền vững
Tính bảo mật
Tính vô hình
Hình 1-2. Tam giác 3 yêu cầu của lược đồ thủy vân tốt
Không một thuật toán thủy vân nào có thể thỏa mãn được đồng thời các yêu
cầu trên, vì bản thân các yêu cầu này là mâu thuẫn nhau. Ba yêu cầu chính có thể
được minh họa bởi tam giác như hình vẽ với các yêu cầu ở các đỉnh. Khi một yêu
cầu được thỏa mãn thì các yêu cầu khác sẽ bị vi phạm. Trong các ứng dụng thực tế,
tùy theo ngữ cảnh mà người ta sẽ sử dụng thuật toán ưu tiên thỏa mãn yêu cầu
tương xứng với ngữ cảnh đó.
1.2. Cấu trúc dữ liệu không gian
1.2.1. Một số khái niệm
1.2.1.1 Phép chiếu bản đồ
Việc lưu trữ và xử lý trực tiếp các đối tượng có trên bề mặt trái đất là rất khó khăn,
nên ta phải sử dụng biểu diễn phẳng của bề mặt Trái đất. Phép chiếu bản đồ là phép
chuyển đổi toán học từ hệ trục kinh vĩ độ cầu sang hệ trục tọa độ cực. Phép chiếu
11
- Xem thêm -