Đăng ký Đăng nhập
Trang chủ NGHIÊN CỨU CÁC THUẬT TOÁN ỨNG DỤNG TRONG BẢO VỆ BẢN QUYỀN BẢN ĐỒ SỐ...

Tài liệu NGHIÊN CỨU CÁC THUẬT TOÁN ỨNG DỤNG TRONG BẢO VỆ BẢN QUYỀN BẢN ĐỒ SỐ

.PDF
91
382
145

Mô tả:

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 -

Tài liệu liên quan