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

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

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

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.

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.

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ì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

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à

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

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.

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



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.


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

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


12


Hàn Ngọc Đức

1.2.2. Mô hình dữ liệu Raster
1.2.2.1 Trường raster đơn giản
Mô hình dữ liệu raster (còn gọi là lưới tế bào) hình thành nền cho một số hệ thống
thông tin địa lý. Các hệ thống này hiển thị, định vị và lưu trữ dữ liệu đồ họa nhờ sử
dụng các ma trận hay lưới tế bào. Tiến trình xây dựng lưới tế bào như sau: Giả sử
phủ một lưới lên bản đồ gốc, dữ liệu raster được lập bằng cách mã hóa mỗi tế bào
bằng một giá trị mang dựa theo các đặc trưng trên bản đồ (hình vẽ). Trong ví dụ này
đặc trưng đường mã hóa là 2, điểm mã hóa là 1 và vùng được mã hóa bởi 3. Mỗi
đặc trưng là tập tế bào có cùng giá trị.
Hình dạng tế bào được gọi là khảm (tessellation), người ta có thể dùng các
khảm có dạng hình vuông, lục giác, tam giác.
Lợi thế lớn nhất của hệ thống raster là dữ liệu hình thành bản đồ trong bộ nhớ
máy tính. Cũng như mô hình vector, mô hình raster có các tầng bản đồ cho các mục
đích mô hình khác nhau. Tuy nhiên do cách xử lý thông tin thuộc tính khác nhau
nên mô hình raster thường có nhiều tầng bản đồ hơn.
1.2.2.2 Cấu trúc dữ liệu raster
Lượng dữ liệu được thu thập ngày càng lớn, chúng đòi hỏi phải có kỹ thuật để quản
lý khối lượng lớn của dữ liệu này. Các phương pháp hay được sử dụng là phân
hoạch dữ liệu và xây dựng chỉ số xâm nhập nhanh.
Phương pháp đơn giản nhất là raster được lưu trữ và xâm nhập theo trật tự
từng hàng. Phương pháp này kém hiệu quả khi nén và xâm nhập các tế bào. Các tế
bào gần nhau thường có giá trị tương tự nhau. Do vậy có nhiều đề xuất phương
pháp xây dựng các trật tự xâm nhập và mã hóa tế bào khác nhau. Đường dẫn của
trật tự duyệt tế bào phải thỏa mãn các điều kiện sau:

Hilbert hay còn gọi là trật tự Pi.
1.2.3. Mô hình dữ liệu vector
Mô hình dữ liệu vector coi hiện tượng là tập các thực thể không gian cơ sở và tổ
hợp giữa chúng. Trong mô hình 2D thì thực thể sơ cấp bao gồm điểm, đường và
vùng; mô hình 3D còn áp dụng bề mặt ba chiều và khối.
Điểm là thành phần sơ cấp của dữ liệu địa lý ở mô hình này. Các điểm được
nối với nhau bằng các đoạn để thạo thành các thực thể khác nhau như đường hay
vùng. Loại thực thể sơ đẳng được sử dụng phụ thuộc vào tỷ lệ quan sát. Với tỷ lệ
14


Hàn Ngọc Đức

nhỏ thì thành phố được biểu diễn thành điểm, sông và đường đi là đường. Khi tăng
tỷ lệ thì phải quan tâm tới tính chất vùng của hiện tượng. Khác với mô hình raster,
mô hình dữ liệu vector có thể cho biết "nơi mà mọi thứ xảy ra".
Điểm chung của mô hình dữ liệu bản đồ raster và vector là chúng được lưu trữ
theo nhiều tầng (layer), mỗi tầng có ý nghĩa cũng như cách biểu diễn có thể khác
nhau. Tư tưởng của việc phân tầng giúp cho quản lý thông tin địa lý cũng như lưu
trữ cơ sở dữ liệu về không gian rất thuận tiện.

Đường biên
hành chính

Sông

Các công trình
công cộng

Hình 1-3. Các tầng bản đồ

ứng dụng cụ thể mà lựa chọn công cụ phần mềm GIS cho phù hợp.
Bảng 1-2. So sánh mô hình raster và vector
Mô hình vector

Mô hình raster
Mô hình hiệu quả
Dễ tổ hợp, nạp chồng
Hướng ảnh vệ tinh
Dễ phân tích dữ liệu
Có khả năng mô phỏng

Chất lượng đồ họa hạn chế
Khó mô hình hóa mạng
Biến đổi phi tuyến phức tạp

Ưu điểm
Thuận tiện biểu diễn hiện tượng tự
nhiên
Mô hình cô đọng
Có khả năng tạo lập topo lưới
Thao tác hình học dễ, chính xác
Có khả năng tổng quát hóa, dễ sửa đổi
Hạn chế
Cấu trúc dữ liệu phức tạp

16