Luận văn Một số thử nghiệm các kỹ thuật ẩn dữ liệu trên ảnh tĩnh và mô hình ba chiều

Luận văn Một số thử nghiệm các kỹ thuật ẩn dữ liệu trên ảnh tĩnh và mô hình ba chiều Kh oa C NT T - Ð H KH TN TP .H CM -i- MỤC LỤC LỜI MỞ ĐẦU..................................................................................................... 1 CHƯƠNG 1 : MỞ ĐẦU..................................................................................... 3 1.1 Lý do chọn đề tài: ................................................................................. 4 1.2 Mục đích nghiên cứu: ........................................................................... 5 1.3 Đối tượng nghiên cứu:.......................................................................... 5 1.4 Phạm vi nghiên cứu:............................................................................. 6 CHƯƠNG 2 : TỔNG QUAN............................................................................. 7 2.1 Giới thiệu:............................................................................................. 8 2.2 Mô tả hệ thống ẩn dữ liệu:.................................................................. 11 2.3 Phân loại các kỹ thuật ẩn dữ liệu: ....................................................... 13 2.4 Các ứng dụng của ẩn dữ liệu: ............................................................. 15 2.5 Các hướng nghiên cứu về ẩn dữ liệu: ................................................. 16 2.5.1 Trên văn bản:.................................................................................. 16 2.5.2 Trên ảnh tĩnh: ................................................................................. 16 CHƯƠNG 3 : LÝ THUYẾT VỀ ẨN DỮ LIỆU ............................................. 18 3.1 Các yếu tố ảnh hưởng đến quá trình ẩn dữ liệu: ................................. 19 3.1.1 Sự thay đổi trên đối tượng chứa là tối thiểu: .................................. 19 3.1.2 Mức độ tránh các thao tác biến đổi trên đối tượng chứa:................ 19 3.1.3 Số lượng dữ liệu nhúng: ................................................................. 20 3.1.4 Sự khó phát hiện bởi tri giác của con người - sự vô hình: .............. 21 Kh oa C NT T - Ð H KH TN TP .H CM -ii- 3.1.5 Không thể giải mã dữ liệu nhúng từ đối tượng chứa – Tính bảo mật: ........................................................................................................ 22 3.2 Các mức độ ảnh hưởng của các yếu tố trong các ứng dụng của ẩn dữ liệu: ............................................................................................................ 22 3.3 Các kỹ thuật ẩn dữ liệu trên văn bản: ................................................. 23 3.3.1 Các kỹ thuật của Brassil: ................................................................ 23 3.3.1.1 Nhúng dữ liệu bằng cách dịch chuyển dòng: .......................... 24 3.3.1.2 Nhúng dữ liệu bằng cách dịch chuyển từ:............................... 25 3.3.1.3 Nhúng dữ liệu đặc trưng: ........................................................ 26 3.3.2 Các kỹ thuật của Bender:................................................................ 26 3.3.2.1 Phương pháp khoảng trắng mở (open space methods): .......... 27 3.3.2.2 Phương pháp cú pháp (syntactic methods): ............................ 29 3.3.2.3 Phương pháp ngữ nghĩa (semantic methods):......................... 30 3.4 Các kỹ thuật ẩn dữ liệu trên ảnh tĩnh:................................................. 30 3.4.1 Các hướng tiếp cận của các kỹ thuật ẩn dữ liệu trên ảnh tĩnh:........ 31 3.4.1.1 Hướng tiếp cận chèn vào bit LSB:.......................................... 31 3.4.1.2 Phương pháp ngụy trang và lọc: ............................................. 32 3.4.1.3 Các thuật toán và phép biến đổi:............................................. 33 3.4.2 Các kỹ thuật ẩn dữ liệu trên ảnh tĩnh:............................................. 33 3.4.2.1 Ẩn dữ liệu với tỉ lệ bit thấp:.................................................... 34 3.4.2.2 Mã hóa với dữ liệu bit cao – Mã hóa affine:........................... 39 3.5 Các kỹ thuật ẩn dữ liệu trên mô hình ba chiều: .................................. 53 3.5.1 Lý thuyết của ẩn dữ liệu trên mô hình ba chiều:............................. 53 3.5.1.1 Các yêu cầu của ẩn dữ liệu trong mô hình ba chiều: .............. 53 Kh oa C NT T - Ð H KH TN TP .H CM -iii- 3.5.1.2 Mục đích của ẩn dữ liệu: ........................................................ 55 3.5.1.3 Các đối tượng nhúng trong mô hình ba chiều:........................ 55 3.5.1.4 Sự sắp xếp các đối tượng nhúng: ............................................ 57 3.5.2 Các kỹ thuật ẩn dữ liệu:.................................................................. 59 3.5.2.1 Thuật giải dựa trên sự biến đổi các đối tượng hình học:......... 59 3.5.2.2 Thuật giải dựa trên sự thay đổi hình dạng lưới tam giác: ....... 68 CHƯƠNG 4 : CÁC THỬ NGHIỆM TRÊN STEGANOGRAPHY ............. 72 4.1 Giới thiệu:........................................................................................... 73 4.2 Lịch sử phát triển:............................................................................... 74 4.3 Các phần mềm ứng dụng:................................................................... 77 4.3.1 Hide and Seek:................................................................................ 78 4.3.2 StegoDos: ....................................................................................... 79 4.3.3 White Noise Storm: ........................................................................ 79 4.3.4 S-Tools: .......................................................................................... 79 4.3.5 Jpeg-Jsteg v4: ................................................................................. 79 4.4 Lý do đề tài chọn ứng dụng Steganography là các thử nghiệm trên các kỹ thuật ẩn dữ liệu:........................................................................................ 79 4.5 Steganography trên ảnh tĩnh:.............................................................. 80 4.5.1 Phát biểu bài toán: .......................................................................... 80 4.5.2 Phương án giải quyết:..................................................................... 81 4.6 Steganography trên mô hình ba chiều: ............................................... 82 4.6.1 Phương pháp áp dụng thuật giải TSQ:............................................ 82 4.6.1.1 Phát biểu bài toán: .................................................................. 83 Kh oa C NT T - Ð H KH TN TP .H CM -iv- 4.6.1.2 Phương án giải quyết: ............................................................. 83 4.6.2 Phương pháp áp dụng thuật giải TVR: ........................................... 91 4.6.2.1 Phát biểu bài toán: .................................................................. 91 4.6.2.2 Phương án giải quyết: ............................................................. 91 4.7 Hướng dẫn sử dụng chương trình: ...................................................... 94 CHƯƠNG 5 : KẾT QUẢ THỰC NGHIỆM VÀ HƯỚNG PHÁT TRIỂN 101 5.1 Kết quả thực nghiệm: ....................................................................... 102 5.1.1 Kết quả thực nghiệm trên ảnh tĩnh: .............................................. 102 5.1.2 Kết quả thực nghiệm trên mô hình ba chiều: ................................ 107 5.2 Các khó khăn khi thực hiện luận văn:............................................... 113 5.3 Hướng phát triển: ............................................................................. 113 5.3.1 Hướng phát triển trên ảnh tĩnh:..................................................... 113 5.3.2 Hướng phát triển trên mô hình ba chiều: ...................................... 113 TÀI LIỆU THAM KHẢO ............................................................................. 115 Kh oa C NT T - Ð H KH TN TP .H CM -v- DANH SÁCH CÁC HÌNH Hình 1. Quá trình nhúng dữ liệu......................................................................... 11 Hình 2. Quá trình rút trích dữ liệu...................................................................... 12 Hình 3. Quá trình nhúng và rút trích dữ liệu ...................................................... 12 Hình 4. Sơ đồ phân cấp các kỹ thuật ẩn dữ liệu ................................................. 13 Hình 5. Biểu đồ liên hệ giữa số lượng dữ liệu nhúng và tính bền vững ............. 21 Hình 6. Phương pháp khoảng trắng mở khai thác các khoảng trắng sau mỗi dòng. Hình (a) là đoạn văn bản trước khi nhúng, hình (b) là đoạn văn bản sau khi nhúng.................................................................................................................. 28 Hình 7. Đoạn văn bản chứa dữ liệu nhúng sử dụng các khoảng trắng sau mỗi từ. ........................................................................................................................... 29 Hình 8. Các cặp từ đồng nghĩa. .......................................................................... 30 Hình 9. Vòng lặp đơn trong thuật giải Patchwork.............................................. 35 Hình 10. Hình dáng các mảnh ............................................................................ 37 Hình 11. Sự sắp xếp các mảnh ........................................................................... 38 Hình 12. Một ví dụ về phương pháp mã hóa kết cấu khối.................................. 38 Hình 13. Nhúng 3 bit vào ảnh 6 x 6 ................................................................... 44 Hình 14. Ảnh F, ma trận khóa K và ma trận trọng lượng W. ............................. 50 Hình 15. Ảnh F sau khi thực hiện toán tử XOR và ảnh chứa bị thay đổi dữ liệu51 Hình 16. Các phương pháp sắp xếp các đối tượng nhúng. (a) sắp xếp toàn cục, (b) sắp xếp cục bộ, (c) sắp xếp theo chỉ số ......................................................... 58 Hình 17. Các đặc trưng đồng dạng trong tam giác ............................................. 60 Hình 18. Cấu trúc một MEP............................................................................... 62 Hình 19. Lưới tam giác và các MEP với dữ liệu nhúng là "data hiding"............ 63 Kh oa C NT T - Ð H KH TN TP .H CM -vi- Hình 20. Cạnh xác định tứ diện chính là bốn đỉnh của hai tam giác có cạnh này là cạnh chung ......................................................................................................... 65 Hình 21. Quá trình tạo chuỗi tỉ số thể tích.......................................................... 66 Hình 22. Mô tả các bước của thuật giải TSPS.................................................... 70 Hình 23. Chuỗi tam giác S tương ứng với dữ liệu nhúng "10101101011". Nếu bit cuối cùng là "1" thì tam giác cuối trong dãy là tam giác nét đứt ........................ 71 Hình 24. Ma trận K 5x5 trong thuật giải LSB1bit và LSB2bit........................... 81 Hình 25. Ma trận W 5x5 trong thuật giải LSB2bit với r=3 ................................ 82 Hình 26. Ví dụ về một thao tác chèn bit............................................................. 85 Hình 27. Tam giác trong không gian hai chiều .................................................. 87 Hình 28. Biến đổi trên tam giác Mark ................................................................ 88 Hình 29. Biến đổi trên tam giác Subscript, Data1 và Data2 ............................... 89 Hình 30. Quá trình biến đổi một tứ diện............................................................. 93 Hình 31. Giao diện ảnh tĩnh ............................................................................... 94 Hình 32. Giao diện 3D ....................................................................................... 95 Hình 33. Hộp thoại tham số của thuật giải LSB1bit .......................................... 96 Hình 34. Hộp thoại tham số của thuật giải LSB2bit ........................................... 96 Hình 35. Hộp thoại thông tin của thao tác nhúng dữ liệu trên ảnh ..................... 97 Hình 36. Hộp thoại thông tin của thao tác rút trích dữ liệu ................................ 98 Hình 37. Hộp thoại thông tin nhúng trên mô hình 3D........................................ 98 Hình 38. Hộp thoại thông tin về ảnh .................................................................. 99 Hình 39. Hộp thoại thông tin về mô hình 3D ................................................... 100 Hình 40. Thử nghiệm thuật giải TSQ trên mô hình con mèo với sự thay đổi trên d ....................................................................................................................... 109 Kh oa C NT T - Ð H KH TN TP .H CM -vii- Hình 41. Thử nghiệm thuật giải TSQ trên mô hình con chó với sự thay đổi trên c ......................................................................................................................... 110 Hình 42. Thử nghiệm thuật giải TVR trên mô hình con mèo với sự thay đổi trên d ....................................................................................................................... 111 Hình 43. Thử nghiệm thuật giải TVR trên mô hình con chó với sự thay đổi trên c ......................................................................................................................... 112 Kh oa C NT T - Ð H KH TN TP .H CM -viii- DANH SÁCH CÁC BẢNG Bảng 1. Số lượng các ấn phẩm về kỹ thuật ẩn dữ liệu.......................................... 9 Bảng 2. So sánh giữa Watermarking và Steganography về các yếu tố............... 23 Bảng 3. Mối quan hệ giữa n và độ tin cậy .......................................................... 36 Bảng 4. Đối tượng nhúng và tính chất bất biến của chúng với các phép biến đổi ........................................................................................................................... 56 Bảng 5. Thời gian nhúng và rút trích trong thuật toán TSQ trên mô hình con mèo ......................................................................................................................... 108 Kh oa C NT T - Ð H KH TN TP .H CM -1- LỜI MỞ ĐẦU WW XX Thế kỷ XXI còn được gọi là thế kỷ của nền kinh tế tri thức, thế kỉ của thông tin số hóa. Vấn đề bảo vệ bản quyền của các dạng thông tin số hiện đang được sự quan tâm của các nhà sản xuất, phân phối thông tin kỹ thuật số và kỹ thuật ẩn dữ liệu là kỹ thuật được sử dụng trong các ứng dụng bảo vệ bản quyền, nhúng dấu hiệu đặc trưng, truyền thông mật,… Tuy nhiên, tại Việt Nam, các ứng dụng trên chưa có nhiều. Luận văn này được thực hiện với sự mong muốn được thử nghiệm các kỹ thuật ẩn dữ liệu trong truyền thông mật. Trong phạm vi một luận văn có sự giới hạn về thời gian, một đề tài tương đối mới tại Việt Nam, một nguồn tài liệu không nhiều, tôi thực hiện luận văn này chắc hẳn không thiếu sự sai sót, tôi mong muốn được thử nghiệm các kỹ thuật mới và mong muốn sự chỉ dạy của các thầy cô và các ý kiến của các bạn. Luận văn được trình bày theo cấu trúc sau: Chương 1 trình bày tổng quan về nội dung của luận văn, các đối tượng và các phạm vi nghiên cứu trong luận văn. Chương 2 bao gồm khái niệm về ẩn dữ liệu, các ứng dụng của ẩn dữ liệu và phân loại các kỹ thuật ẩn dữ liệu. Đồng thời chương 2 còn giới thiệu một số hướng nghiên cứu trên văn bản và ảnh tĩnh của các nhà nghiên cứu tại các phòng thí nghiệm nổi tiếng trên thế giới. Chương 3 đi sâu vào lý thuyết của các kỹ thuật ẩn dữ liệu, giới thiệu một số kỹ thuật ẩn dữ liệu trên văn bản, ảnh tĩnh và mô hình ba chiều. Các yếu tố trong ẩn dữ liệu cũng được đề cập trong chương 3. Kh oa C NT T - Ð H KH TN TP .H CM -2- Lịch sử và các phần mềm ứng dụng của Steganography được tìm hiểu trong chương 4. Chương 4 còn bao gồm các phương pháp được đề nghị để áp dụng thực tế các kỹ thuật ẩn dữ liệu trong Steganography, các vấn đề phát sinh và hướng giải quyết. Một phần hướng dẫn sử dụng sẽ giúp người dùng sử dụng chương trình thực nghiệm dễ dàng hơn. Các kết quả thực nghiệm không thể thiếu trong một luận văn, kết quả thực nghiệm này được mô tả trong chương 5. Sự nhận xét trên các kỹ thuật ẩn dữ liệu, các hướng phát triển, cải tiến được tôi đề cập trong phần cuối chương 5. Và tài liệu tham khảo sẽ kết thúc phần báo cáo của luận văn này. Kh oa C NT T - Ð H KH TN TP .H CM -3- CHƯƠNG 1 : MỞ ĐẦU Chương mở đầu trình bày về lý do chọn đề tài này, mục đích của đề tài, các vấn đề, các đối tượng được luận văn đề cập đến, đồng thời nói rõ phạm vi nghiên cứu trong đề tài. Kh oa C NT T - Ð H KH TN TP .H CM -4- 1.1 Lý do chọn đề tài: Ngày nay, cùng với sự phát triển của Internet và sự xuất hiện của các phương tiện thông tin đại chúng, các định dạng lưu trữ số hóa như ảnh số, âm thanh,..., cùng với các thiết bị lưu trữ dung lượng cao như CD-ROM, DVD- ROM, thì những sự xâm phạm trên hình thức sở hữu trí tuệ ngày càng nhiều và càng tinh vi. Các hình thức xâm phạm hiện nay là giả mạo, ăn cắp tác phẩm, sử dụng các tác phẩm của tác giả mà không có bản quyền... Hàng ngày trên mạng Internet truyền thông vô số các tập tin ảnh, âm thanh, hay video không rõ nguồn gốc. Các thao tác sao chép một bản sao giống hệt bản chính được thực hiện rất dễ, và chỉ cần chứa trong một đĩa mềm, đĩa CD_ROM, hay tải lên mạng là có thể di chuyển khắp nơi. Với các vấn đề trên, kỹ thuật ẩn dữ liệu (data hiding) còn được gọi là ẩn thông tin (ìnformation hiding) ra đời như một cứu cánh cho các nhà kinh doanh, phân phối thông tin kỹ thuật số. Kỹ thuật ẩn dữ liệu là kỹ thuật đưa một lượng dữ liệu có giá trị vào thông tin dạng số cần phổ biến. Lượng dữ liệu này không thể dễ dàng bị hủy bỏ, nhưng lại phải dễ dàng được rút trích với các yếu tố phù hợp. Không chỉ để giải quyết các vấn đề về xâm phạm quyền sở hữu trí tuệ, kỹ thuật ẩn dữ liệu còn hỗ trợ một số nhu cầu thiết yếu cho các định dạng thông tin số như ứng dụng nhúng một đoạn chú thích vào một đoạn video, đưa một hình mờ vào một ảnh... Một nhiếp ảnh gia có thể giám sát các bức ảnh của mình lưu thông trên mạng bằng cách nhúng dấu hiệu đặc trưng vào các ảnh và nhờ một trình duyệt Web kiểm tra các ảnh lưu thông trên mạng để nhận dạng được các ảnh của mình nhờ vào dấu hiệu đặc trưng có trong ảnh. Kh oa C NT T - Ð H KH TN TP .H CM -5- Các kỹ thuật ẩn dữ liệu xuất hiện vào thập niên 90 cua thế kỷ XX, và ngày nay đã trở nên phổ biến. Một dạng quan trọng của ẩn dữ liệu, Steganography, là một dạng của mã hóa, còn được gọi là mã hóa vô hình, nó đã được phát triển rất lâu, trước Công Nguyên, nhưng việc ứng dụng Steganography trên dữ liệu số chỉ mới xuất hiện gần đây. Steganography là một ứng dụng quan trọng trong truyền thông mật (anonymous communication), đây là phương pháp truyền thông tin trên các phương tiện thông tin đại chúng nhưng vẫn bảo đảm được tính bảo mật của thông tin. Truyền thông mật được sử dụng chủ yếu trong các hệ thống truyền thông trong quân đội. Ở Việt Nam, các kỹ thuật và ứng dụng của ẩn dữ liệu chưa được sự quan tâm thích đáng của các nhà nghiên cứu. Với nhu cầu bảo mật thông tin, truyền thông các thông điệp mà người trung gian không nhận biết và không thể giải mã, tôi thực hiện luận văn này nhằm thử nghiệm các kỹ thuật ẩn dữ liệu nói chung và Steganography nói riêng hiện đang còn là các kỹ thuật khá mới tại Việt Nam. 1.2 Mục đích nghiên cứu: Mục đích nghiên cứu của luận văn này nhằm tìm hiểu và đánh giá các kỹ thuật ẩn dữ liệu và đi sâu vào các kỹ thuật Steganography - kỹ thuật hiện nay đang được quan tâm trong lĩnh vực truyền thông mật. Để minh họa và khảo sát các ưu khuyết điểm của các kỹ thuật Steganography, tôi tiến hành cài đặt một số kỹ thuật Steganography trên ảnh tĩnh và mô hình ba chiều. 1.3 Đối tượng nghiên cứu: Các đối tượng hiện nay đang phổ biến để nhúng dữ liệu vào là văn bản, ảnh tĩnh, âm thanh và video vì các dạng thức số này được phổ biến trên Internet Kh oa C NT T - Ð H KH TN TP .H CM -6- và trong đời sống hằng ngày. Tùy vào từng loại đối tượng mà có các kỹ thuật khác nhau. Các định dạng ảnh trong chương trình ứng dụng là BMP, TIFF, PCX với 1 bit màu, 8 bit màu, ảnh xám và 24 bit màu. Định dạng của mô hình ba chiều là MS3D, được thể hiện dưới dạng lưới tam giác. Luận văn nghiên cứu đi sâu vào các kỹ thuật Steganography trên ảnh tĩnh và mô hình ba chiều. Mặc dù mô hình ba chiều không phải là đối tượng phổ biến trong ẩn dữ liệu, nhưng là hướng phát triển trong tương lai vì hiện nay đồ họa ba chiều rất phát triển và tràn ngập trong các trò chơi, trong kỹ xảo điện ảnh, trong các đồ họa ứng dụng như trong xây dựng (CAD), kiến trúc, trang trí nội thất... Vì thế có thể nói ẩn dữ liệu trong mô hình ba chiều là một hướng sẽ rất phát triển trong tương lai. 1.4 Phạm vi nghiên cứu: Đề tài này nghiên cứu các kỹ thuật ẩn dữ liệu truyền thống và hiện đại, tiến hành so sánh các kỹ thuật về các yếu tố như tỉ lệ nhúng, khả năng chống lại các biến đổi trên đối tượng chứa và khả năng vô hình. Do có sự giới hạn trong phạm vi một luận văn, tôi chỉ tiến hành cài đặt thử nghiệm một số kỹ thuật và đưa ra một số điều chỉnh, phát kiến trên các kỹ thuật. ------------------------------------------------ Kh oa C NT T - Ð H KH TN TP .H CM -7- CHƯƠNG 2 : TỔNG QUAN Chương 2 giới thiệu tổng quan về ẩn dữ liệu, phân loại của các kỹ thuật ẩn dữ liệu. Chương 2 trình bày các hướng nghiên cứu về ẩn dữ liệu của các nhà nghiên cứu và các ứng dụng của ẩn dữ liệu. Kh oa C NT T - Ð H KH TN TP .H CM -8- 2.1 Giới thiệu: Hiện nay, các kỹ thuật ẩn dữ liệu trở nên quan trọng trong một số các lĩnh vực ứng dụng. Ảnh, âm thanh và video được cung cấp các dấu hiệu phân biệt, các dấu hiệu này vô hình, có chứa một thông tin bản quyền hoặc con số đăng ký (serial number) để bảo vệ bản quyền. Các hệ thống truyền thông trong quân đội đang gia tăng việc sử dụng các kỹ thuật truyền thông bảo mật đường truyền hơn là che dấu nột dung của một thông điệp bằng cách sử dụng mật mã, hướng đến việc che dấu người gửi, người nhận và sự tồn tại của thông điệp. Cho đến gần đây, các nghiên cứu trong truyền thông và trong công nghiệp tập trung nhiều vào mật mã, kỹ thuật ẩn dữ liệu ít nhận được sự quan tâm hơn, nhưng điều này đã thay đổi nhanh chóng (bảng 1) và hội nghị đầu tiên về ẩn dữ liệu được tổ chức vào năm 1996. Động lực chính của sự quan tâm đến kỹ thuật ẩn dữ liệu là sự lo âu về bản quyền của các nhà sản xuất, phân phối các định dạng số. Âm thanh, video và nhiều dạng khác đã được tích hợp vào dạng số, việc dễ dàng sao chép các định dạng số có thể dẫn đến một tỉ lệ cao về các bản chép không bản quyền. Và sự lo lắng lớn nhất tập trung trong công nghiệp xuất bản là âm nhạc, phim ảnh, sách và phần mềm. Gần đây đã có các nghiên cứu về Watermarks (thông điệp về bản quyền) và Fingerprints (số đăng ký ẩn), Fingerprints nhằm giúp đỡ việc nhận dạng các sản phẩm không bản quyền và Watermarks nhằm để điều tra, kiểm tra, theo dõi chúng. Kh oa C NT T - Ð H KH TN TP .H CM -9- Năm 1992 1993 1994 1995 1996 1997 1998 Số lượng xuất bản 2 2 4 13 29 64 103 Bảng 1. Số lượng các ấn phẩm về kỹ thuật ẩn dữ liệu Ẩn dữ liệu (data hiding) là thao tác nhúng dữ liệu vào các dạng lưu trữ số hóa như tập tin văn bản, tập tin ảnh nhị phân, các tập tin âm thanh,..., nhằm mục đích nhận diện, chú thích, bảo vệ bản quyền tác giả và truyền thông mật. Ẩn dữ liệu bao gồm hai quá trình: nhúng dữ liệu (embedding) vào đối tượng nhúng và rút trích dữ liệu (extracting) từ đối tượng chứa. Quá trình nhúng dữ liệu và quá trình rút trích dữ liệu còn được gọi là quá trình mã hóa và quá trình giải mã. Đối tượng nhúng là đối tượng được chọn để nhúng dữ liệu vào, đối tượng nhúng có ký hiệu Cover , trong đó data type là loại đối tượng (văn bản, ảnh tĩnh, âm thanh,...). Đối tượng chứa là đối tượng sau khi đã được nhúng vào một lượng dữ liệu, đối tượng chứa có ký hiệu Stego . Dữ liệu được nhúng vào đối tượng chứa có thể là các ký hiệu, thông điệp hay các mẫu (pattern), dữ liệu này được gọi là dữ liệu nhúng. Các kỹ thuật ẩn dữ liệu nói chung còn có một hay nhhiều khóa gọi là stego-key, stego-key là tham số điều khiển quá trình nhúng dữ liệu nhằm hạn chế khả năng dữ liệu nhúng bị phát hiện hay nhằm lấy lại dữ liệu nhúng từ đối tượng chứa. Mỗi ứng dụng cụ thể có các ràng buộc riêng trên các yếu tố tác động đến quá trình nhúng dữ liệu. Các yếu tố đó có thể là số lượng dữ liệu nhúng, mức độ bất biến của dữ liệu nhúng khi đối tượng chứa bị thao tác bởi các phép biến đổi, mức độ bảo toàn dữ liệu nhúng trong các chuẩn nén mất dữ liệu (như JPEG – Kh oa C NT T - Ð H KH TN TP .H CM -10- Joint Photograghic Experts Group ), mức độ ngăn chặn, thay đổi, di chuyển hay rút trích dữ liệu nhúng của một người khác. Những tác động không mong muốn trong việc truy cập dữ liệu dễ dàng là sự gia tăng khả năng xâm phạm bản quyền tác giả, việc giả mạo có hay không có thay đổi nội dung dữ liệu. Mục đích của các phương pháp ẩn dữ liệu là bảo vệ quyền sở hữu trí tuệ, cung cấp phương tiện chú thích và truyền thông mật. Các dữ liệu nhúng, thường là thông tin về bản quyền, được nhúng vào các dạng truyền thông như văn bản, ảnh, âm thanh với số lượng tín hiệu bị suy biến tối thiểu để không ảnh hưởng nhiều đến đối tượng chứa. Đối với ứng dụng truyền thông mật, dữ liệu còn phải vô hình với các hệ thống tri giác của người, ví dụ dữ liệu nhúng trong ảnh phải vô hình với hệ thống thị giác HVS (Human Visuality System), với âm thanh phải không bị hệ thống thính giác HAS (Human Auditory System) nhận ra. Các phương pháp này ngăn chặn hay điều chỉnh việc truy cập đến dữ liệu nhúng trong tín hiệu chứa, và trên hết là phải bảo đảm dữ liệu nhúng không bị xâm phạm và có thể phục hồi lại. Tín hiệu chứa là tín hiệu, dữ liệu của đối tượng chứa. Các ứng dụng của ẩn dữ liệu phụ thuộc vào số lượng dữ liệu được nhúng và sự cần thiết của việc các dữ liệu nhúng không bị biến đổi qua các thao tác trên đối tượng chứa. Bất cứ vị trí nào trong tín hiệu chứa đều có thể là mục tiêu của sự di chuyển hay phá hủy trong các chuẩn nén mất dữ liệu. Để có hiệu quả lớn, các kỹ thuật ẩn dữ liệu phải nhúng dữ liệu vào các vị trí mà không bị thuật toán nén xén mất. Kh oa C NT T - Ð H KH TN TP .H CM -11- 2.2 Mô tả hệ thống ẩn dữ liệu: Quá trình nhúng dữ liệu của một hệ thống ẩn dữ liệu thông thường có các đầu vào là đối tượng chứa (giả sử là ảnh) I, một dấu hiệu M và một khóa K (thường được phát sinh từ dãy số giả ngẫu nhiên – pseudoramdom). Quá trình nhúng dữ liệu là một ánh xạ có dạng như sau: I K M I ¢´ ´ ® và đầu ra là một đối tượng chứa (ảnh chứa). Hình 1 là cấu trúc một quá trình ẩn dữ liệu thông thường. Thuaät toaùn nhuùng Mark (M) Cover image (I) Key (K) Stego Image (I’) Hình 1. Quá trình nhúng dữ liệu Quá trình rút trích dữ liệu được mô tả qua ví dụ trog hình 2. Trong đó đầu vào là một đối tượng chứa cần kiểm tra, dấu hiệu M, khóa K, có thể có thêm đối tượng gốc tùy từng loại kỹ thuật. Đầu ra là dấu hiệu thật sự được nhúng và giá trị tin cậy trên sự tồn tại của dấu hiệu đó. Kh oa C NT T - Ð H KH TN TP .H CM -12- Thuaät toaùn ruùt trích M and/or I Test image I” Key (K) M hay ñoä tin caäy Hình 2. Quá trình rút trích dữ liệu Quá trình từ nhúng dữ liệu sang rút trích dữ liệu ẩn từ đối tượng chứa được mô tả bằng sơ đồ sau: Quaù trình nhuùng döõ lieäu Döõ lieäu ñöôïc nhuùng Döõ lieäu ñöôïc nhuùng Chöõ caùi, con soá, caùc maãu,... Vaên baûn, aûnh tónh, moâ hình 3D, aâm thanh,... Quaù trình ruùt trích döõ lieäu Phaân phoái qua caùc phöông tieän truyeàn thoâng Stego Cover Stego Hình 3. Quá trình nhúng và rút trích dữ liệu Kh oa C NT T - Ð H KH TN TP .H CM -13- 2.3 Phân loại các kỹ thuật ẩn dữ liệu: Theo B. Pflitzmann[1], ẩn dữ liệu được phân chia như sơ đồ sau: Data hiding Steganography AnonymityCovert channels Copyright marking Linguistics steganography Technical steganography Robust copyright marking Fragile watermarking Fingerprinting Watermarking Imperceptible watermarking Visible watermarking Hình 4. Sơ đồ phân cấp các kỹ thuật ẩn dữ liệu Trong đó mục đích của Steganography là che dấu sự truyền thông giữa người gửi và người nhận, không để người thứ ba biết được, người thứ ba tấn công vào hệ thống thành công khi sự truyền thông đó đã bị phát hiện. Copyright marking có các yêu cầu thêm về tính bền vững, chống lại các xâm phạm trên đối tượng chứa. Dấu hiệu bản quyền không cần thiết phải vô hình, một số các hệ thống sử dụng các dấu hiệu trực quan là nhúng các dấu hiệu logo vào sản phẩm. Thông thường trong Watermarking, đối tượng chứa được gọi là đối tượng được đánh dấu. Các dấu hiệu yếu ớt (trong Fragile watermarking) sẽ bị hủy diệt Kh oa C NT T - Ð H KH TN TP .H CM -14- bởi các thay đổi lớn trên đối tượng chứa.. Các dấu hiệu bền vững (trong Robust copyright marking) khó bị hủy diệt và nếu dấu hiệu bị hủy đi thì đối tượng chứa không còn sử dụng được nữa, điều này có nghĩa là các dấu hiệu được nhúng vào các vị trí đặc biệt trong đối tượng chứa như phần header. Robust copyright marking được chia thành hai loại Fingerprinting và Watermarking. Fingerprints còn được gọi là các nhãn, thường là các số đăng ký. Nhờ vào các nhãn này mà người chủ sỡ hữu đặc tính trí tuệ có thể biết được khách hàng nào đã vi phạm bản quyền bằng cách cung cấp số đăng ký cho một người khác. Trong khi đó dấu hiệu bản quyền cho phép chúng ta biết được ai là người chủ sở hữu đặc tính trí tuệ của sản phẩm đó. Hệ thống Robust copyright marking được chia thành các loại sau: ™ Hệ thống kín (private system): đầu vào của quá trình rút trích cần phải có đối tượng gốc. Hệ thống bán kín (semi-private system) tương tự như hệ thống kín nhưng đầu vào của quá trình rút trích không cần đối tượng gốc mà phải được cung cấp thêm một số thông tin. Hệ thống kín và bán kín thường được sử dụng cho mục đích chứng minh quyền sở hữu và điều khiển việc sao chép trong các ứng dụng như DVD, khi người sử dụng cần được biết nơi nào cho phép sao chép nội dung, nơi nào không. Hệ thống kín và bán kín còn được gọi là hệ thống non-blind. ™ Hệ thống công khai (public system): còn được gọi là hệ thống blind, đầu vào của quá trình rút trích dữ liệu không cần cả đối tượng gốc lẫn dấu hiệu M. Hệ thống công khai được sử dụng nhiều hơn hệ thống kín và bán kín, các thuật giải trong hệ thống công khai còn được sử dụng trong hệ thống kín và bán kín. Kh oa C NT T - Ð H KH TN TP .H CM -15- ™ Hệ thống không đối xứng (asymmetric system): còn được gọi là hệ thống khóa công khai (public key system), mọi người dùng đều có thể đọc được dấu hiệu nhưng không thể xóa nó. 2.4 Các ứng dụng của ẩn dữ liệu: Dưới đây là một số các ứng dụng hấp dẫn của ẩn dữ liệu: ™ Các cơ quan quân sự và tình báo có nhu cầu truyền thông không bị đột nhập - truyền thông mật. Ngay cả trong trường hợp nội dung đã được mã hóa, sự phát hiện một tín hiệu trên một chiến trường hiện đại có thể dẫn đến một cuộc tấn công nhanh chóng lên nơi phát ra tín hiệu. Vì lý do này, các truyền thông trong quân đội sử dụng các kỹ thuật như điều biến phổ dãy rộng hoặc kỹ thuật nổi tiếng là truyền thông phân tán để làm tín hiệu khó bị kẻ thù phát hiện và ngăn chặn. ™ Các tội phạm cũng sử dụng sự truyền thông không bị đột nhập. Các tội phạm sử dụng các kỹ thuật trên điện thoại di động trả tiền trước, điện thoại di động sẽ được thay đổi thường xuyên và được sử dụng để đột nhập vào các tổng đài điện thoại. ™ Gần đây, các chính phủ sử dụng kỹ thuật ẩn dữ liệu để giới hạn các lời nói tự do trực tuyến trên mạng và mật mã được sử dụng trong dân chúng đã khuyến khích người dân quan tâm đến quyền tự do phát triển kỹ thuật cho truyền thông mật trên mạng bao gồm các thư nặc danh và các Web proxy. ™ Các hệ thống bầu cử điện tử và giao dịch tiền điện tử có nhu cầu về truyền thông mật. Kh oa C NT T - Ð H KH TN TP .H CM -16- ™ Các nhà kinh doanh sử dụng các kỹ thuật giả mạo email để gửi một số lượng lớn các thông điệp quảng cáo đến người dùng và có khả năng tránh sự phản ứng từ các người dùng giận dữ. 2.5 Các hướng nghiên cứu về ẩn dữ liệu: Có thể nói ẩn dữ liệu là một vấn đề đang được các nhà khoa học quan tâm rất nhiều, nhất là các trung tâm nghiên cứu và các công ty điện tử, điển hình là phòng nghiên cứu của IBM, phòng nghiên cứu của Panasonic, phòng nghiên cứu của MIT,...Sau đây là một số kỹ thuật đã được áp dụng: 2.5.1 Trên văn bản: Các nhà nghiên cứu kỹ thuật ẩn dữ liệu trên văn bản nổi bật là Bender của viện MIT – USA [3][4], ông sử dụng số lượng khoảng trắng giữa các từ, phương pháp ngữ nghĩa của từ và cú pháp trong câu để nhúng dữ liệu. Tuy nhiên, các phương pháp ẩn dữ liệu trên văn bản của ông không nhúng được nhiều dữ liệu và dễ gây chú ý cho người khác. Ngoài ra còn có nhà nghiên cứu Brassil [5] của phòng thí nghiệm Bell, chuyên nghiên cứu về các kỹ thuật ẩn dữ liệu trên văn bản, Brassil sử dụng khoảng cách giữa các từ, các câu và các đặc trưng của ký tự để nhúng dữ liệu. Các phương pháp này có nhược điểm trong trường hợp văn bản được canh lề và sắp chữ lại. 2.5.2 Trên ảnh tĩnh: Adelson[3][4] nghiên cứu một phương pháp ẩn dữ liệu bằng cách khai thác sự nhạy cảm của mắt người đối nghịch với các vùng dữ liệu có tần số xuất hiện cao. Thực hiện trên ảnh tĩnh được mã hóa theo hình chóp, Adelson thay thế Kh oa C NT T - Ð H KH TN TP .H CM -17- những dữ liệu ảnh nơi có tần số xuất hiện cao bằng những dữ liệu nhúng. Bằng cách này có thể nhúng hiệu quả một số lượng lớn dữ liệu, nhưng phương pháp này không cung cấp một phương tiện nào để tránh khỏi sự dò tìm và sự xóa bỏ dữ liệu nhúng khi thực hiện các thao tác cơ bản trên ảnh như lọc ảnh hay biến đổi tỉ lệ. Stego, một trong những phần mềm đóng gói, chỉ đơn giản là mã hóa dữ liệu tại những bit thấp nhất của tín hiệu chứa. Phương pháp này cũng gặp phải vấn đề như Adelson, nhưng nó lại chịu sự suy biến chất lượng ảnh hay chất lượng truyền thông. Bender bổ sung thêm phương pháp của Adelson bằng cách sử dụng các hình thái hỗn loạn (chaos) như một phương tiện để mã hóa dữ liệu nhúng, nhưng nó cũng không cung cấp một cải tiến nào để tránh được các biến đổi trên tín hiệu chứa. Lippman[3] ẩn dữ liệu trong kênh thành phần màu của của tín hiệu tivi NTSC (National Television Standard Committee). Phương pháp này sẽ nhúng một số lượng lớn dữ liệu, nhưng dữ liệu nhúng sẽ bị mất đi sau các qui trình ghi lại, nén và chuyển mã. Những kỹ thuật khác như Hecht’s Data-Glyph[3][4], thêm một mã kẻ sọc vào ảnh, được bố trí để xác định trước một tập hợp các biến đổi hình học. Luồng, một kỹ thuật hứa hẹn trong lĩnh vực ẩn dữ liệu, khó bị ngăn chặn và di chuyển dữ liệu, nhưng tín hiệu chứa dễ bị phát hiện và suy biến. ------------------------------------------------ Kh oa C NT T - Ð H KH TN TP .H CM -18- CHƯƠNG 3 : LÝ THUYẾT VỀ ẨN DỮ LIỆU Chương 3 trình bày phần lý thuyết của các kỹ thuật của ẩn dữ liệu, giới thiệu một số kỹ thuật ẩn dữ liệu trên văn bản, ảnh tĩnh và mô hình ba chiều, mô tả các yếu tố, tham số trong ẩn dữ liệu. Kh oa C NT T - Ð H KH TN TP .H CM -19- 3.1 Các yếu tố ảnh hưởng đến quá trình ẩn dữ liệu: Các kỹ thuật ẩn dữ liệu nói chung đều phải đáp ứng một số các yếu tố, các yếu tố này thay đổi tùy theo từng ứng dụng cụ thể. Sau đây là các yếu tố chung cho các kỹ thuật ẩn dữ liệu. 3.1.1 Sự thay đổi trên đối tượng chứa là tối thiểu: Mục đích của ẩn dữ liệu là nhúng dữ liệu vào đối tượng chứa nhằm các mục đích riêng cho từng ứng dụng. Tuy nhiên, ẩn dữ liệu không thể làm thay đổi giá trị sử dụng của đối tượng chứa vì: ™ Nếu ứng dụng của ẩn dữ liệu là bảo vệ quyền sở hữu trí tuệ thì đối tượng chứa – tác phẩm của tác giả không thể bị suy biến vì như thế thì tác phẩm đó mất đi giá trị và không cần bảo vệ bản quyền nữa. ™ Nếu ứng dụng của ẩn dữ liệu là thêm thông tin chú thích thì đối tượng chứa quan trọng hơn, thông tin chú thích chỉ là phần chú thích thêm, vì vậy đối tượng chứa phải bảo đảm được chất lượng. ™ Nếu ứng dụng ẩn dữ liệu là truyền thông mật, thì sự khác nhau giữa đối tượng gốc và đối tượng chứa phải rất nhỏ để tránh được sự nghi ngờ của người khác. ™ Yêu cầu cần thiết của kỹ thuật ẩn dữ liệu là đối tượng chứa bắt buộc không được có sự gia tăng hay giảm đi về dung lượng so với đối tượng gốc. 3.1.2 Mức độ tránh các thao tác biến đổi trên đối tượng chứa: Còn gọi là tính bền vững của dữ liệu nhúng, đây là mức độ của dữ liệu nhúng không bị mất đi khi đối tượng chứa bị biến đổi bởi các thao tác. Tính năng này là bắt buộc với tất cả các ứng dụng của ẩn dữ liệu. Tuy nhiên, không có kỹ Kh oa C NT T - Ð H KH TN TP .H CM -20- thuật nào có thể bất biến với tất cả các thao tác, mỗi kỹ thuật chỉ hỗ trợ cho tính bất biến đối với một số thao tác mà thôi. Các thao tác trên đối tượng chứa có thể liệt kê như sau: ™ Văn bản: dịch chuyển từ, chia lại khoảng cách giữa các từ,... ™ Ảnh tĩnh: các phép biến đổi affine, nhiễu, các phép biến đổi phi hình học, lọc nhiễu,... ™ Mô hình ba chiều: các phép biến đổi affine, biến đổi hình học, biến đổi phi hình học, sắp xếp lại lưới đa giác,... ™ Âm thanh: lọc nhiễu,... 3.1.3 Số lượng dữ liệu nhúng: Tùy thuộc vào từng ứng dụng cụ thể mà yêu cầu về số lượng dữ liệu nhúng là nhiều hay ít. Một số ứng dụng chỉ cần nhúng một bit đơn vào đối tượng chứa (ví dụ như ứng dụng đánh dấu đối tượng), một số ứng dụng lại yêu cầu số lượng dữ liệu nhúng phải lớn (các đoạn chú thích). Tính năng này luôn tỉ lệ nghịch với tính bền vững của dữ liệu nhúng. Một kỹ thuật nếu hỗ trợ tính năng bền vững của dữ liệu nhúng cao thì số lượng dữ liệu nhúng lại giảm đi đáng kể, và ngược lại nếu nâng cao số lượng dữ liệu nhúng thì dữ liệu nhúng đó lại ít có khả năng tránh được các thao tác trên đối tượng chứa, tín hiệu chứa càng bị nhiễu. Các kỹ thuật hiện đại đều quan tâm đến hai tính năng này và muốn đồng thời nâng cao cả hai tính năng này. Biểu đồ của sự liên hệ giữa số lượng dữ liệu nhúng và tính bền vững của dữ liệu nhúng được mô tả trong hình 5. Kh oa C NT T - Ð H KH TN TP .H CM -21- Hình 5. Biểu đồ liên hệ giữa số lượng dữ liệu nhúng và tính bền vững 3.1.4 Sự khó phát hiện bởi tri giác của con người - sự vô hình: Tính năng này gần giống với tính năng thay đổi tối thiểu trên đối tượng chứa, tuy nhiên lại có sự khác nhau rõ ràng: một đối tượng chứa có thể thay đổi ít nhưng dữ liệu nhúng lại trực quan, ngược lại dữ liệu nhúng có thể khó bị phát hiện trong khi thay đổi trên đối tượng chứa khá nhiều. Một số ứng dụng không cần tính năng này (ví dụ ứng dụng nhúng các lời chú thích, các logo vào đối tượng chứa), tuy nhiên đối với ứng dụng truyền thông mật thì đây là một trong số các tính năng quan trọng nhất. Steganography phải bảo đảm không để cho một người trung gian phát hiện, nghi ngờ đối tượng chứa có chứa thông tin thêm vào. Đối với Steganography, việc phát hiện có dữ liệu nhúng trong đối tượng chứa gây ra một sự thất bại hoàn toàn: người trung gian có thể giải mã thông điệp, làm suy biến thông điệp hay chỉ đơn giản là hủy thông điệp đi. Trong Steganography, tính năng này cùng với hai tính năng số lượng dữ liệu nhúng và tính bền vững của dữ liệu nhúng, cả ba luôn tỉ lệ nghịch với nhau. Kh oa C NT T - Ð H KH TN TP .H CM -22- Nếu ứng dụng nhúng quá nhiều dữ liệu, thì khả năng bị phát hiện tăng cao và ngược lại, số lượng dữ liệu nhúng ít thì khả năng bị phát hiện giảm xuống. 3.1.5 Không thể giải mã dữ liệu nhúng từ đối tượng chứa – Tính bảo mật: Tính năng này đặc biệt quan trọng đối với ứng dụng Steganography, vì mục đích chính của Steganography là không để người thứ ba giải mã được thông điệp truyền đi. ™ Tóm lại: không phải bất kỳ một ứng dụng của ẩn dữ liệu nào cũng phải tuyệt đối tuân theo tất cả các tính năng trên. Mỗi ứng dụng chỉ quan tâm đặc biệt đến một số tính năng phù hợp với mục đích của ứng dụng đó. 3.2 Các mức độ ảnh hưởng của các yếu tố trong các ứng dụng của ẩn dữ liệu: Sau đây là bảng so sánh các mức độ ảnh hưởng của các yếu tố lên hai loại kỹ thuật phổ biến nhất là Watermarking và Steganography: Watermarking Steganography Sự thay đổi trên đối tượng chứa Sự thay đổi phải ít. Điều này nhằm bảo đảm được giá trị sử dụng của đối tượng chứa. Sự thay đổi cũng phải ít. Nhưng mục đích là nhằm ít gây ra sự chú ý, nghi ngờ. Tính bền vững của dữ liệu nhúng Càng cao càng tốt. Càng cao càng tốt. Số lượng dữ liệu nhúng Không bắt buộc phải nhiều. Ví dụ như đối với việc nhúng một dấu hiệu Càng nhiều càng tốt. Nhưng đây không hẳn là yếu tố quan trọng nhất. Kh oa C NT T - Ð H KH TN TP .H CM -23- đặc trưng vào đối tượng chứa nhằm theo vết chúng trên mạng Internet thì không cần thiết là số lượng dữ liệu phải nhiều. Sự vô hình Không cần thiết. Có hai dạng dấu hiệu: dấu hiệu vô hình và dấu hiệu trực quan. Đây là yếu tố quan trọng đối với ứng dụng này. Khó giải mã dữ liệu nhúng Không hoàn toàn bắt buộc, một số ứng dụng cho phép người dùng rút trích dấu hiệu nhưng dấu hiệu không thể bị xoá đi. Bắt buộc. Đây cũng là yếu tố quan trọng. Mức độ quan trọng cao hơn trong Watermarking. Bảng 2. So sánh giữa Watermarking và Steganography về các yếu tố Ta nhận thấy rằng Steganography có các yêu cầu về các tính năng trên rất khắc khe, trong khi đó Watermarking có một số tính năng không cần thiết. 3.3 Các kỹ thuật ẩn dữ liệu trên văn bản: 3.3.1 Các kỹ thuật của Brassil: Brassil[5] và một số nhà nghiên cứu khác đã xác định một vấn đề cần giải quyết là sự phân phối bất hợp pháp các văn bản qua các phương tiện điện tử hiện Kh oa C NT T - Ð H KH TN TP .H CM -24- đại, ví dụ như thư điện tử. Các phương tiện như trên cho phép các xâm phạm trên các bản sao chép văn bản mà chưa có sự đồng ý của tác giả hay không trả tiền bản quyền. Để chống lại sự xâm phạm bản quyền này, Brassil đã đưa ra một phương pháp đánh dấu trên các văn bản với một từ mã duy nhất mà người đọc không thể phát hiện, nhưng có thể sử dụng để xác định người nhận hợp lệ văn bản đó chỉ bằng cách thao tác trên văn bản đó. Kỹ thuật của Brassil là sử dụng một từ mã (có thể là một số nhị phân) được nhúng vào văn bản bằng cách thay đổi các đặc trưng riêng của văn bản. Bằng cách gắn mỗi bit của từ mã vào các đặc trưng của văn bản, ta có thể mã hóa từ mã đó. Dạng đặc trưng xác định một phương pháp mã hóa riêng. Brassil đưa ra ba đặc trưng trong văn bản sau : 3.3.1.1 Nhúng dữ liệu bằng cách dịch chuyển dòng: Trong phương pháp này, các dòng trong văn bản sẽ được dịch chuyển để nhúng dữ liệu. Phương pháp này được áp dụng cho dạng tập tin văn bản hay hình ảnh của trang văn bản. Phương pháp này di chuyển mỗi hai dòng của văn bản hoặc lên hoặc xuống 1/300 inch. Brassil thấy rằng phương pháp này làm việc đặc biệt tốt, và dữ liệu nhúng trong văn bản vẫn được rút trích hoàn chỉnh được, ngay cả sau khi văn bản đã bị sao chép ra 10 lần. Tuy nhiên, phương pháp này là kỹ thuật ẩn dữ liệu trên văn bản dễ thấy nhất đối với người đọc. Hơn nữa, phương pháp có thể bị đánh bại sau khi văn bản được đo khoảng cách giữa hai dòng, việc chia khoảng cách giữa hai dòng ngẫu nhiên hay đồng nhất đều có thể gây ra nguy hiểm, mất từ mã. Kh oa C NT T - Ð H KH TN TP .H CM -25- Tuy nhiên, nếu một văn bản được đánh dấu với phương pháp ẩn dữ liệu này, văn bản khó bị mất từ mã nếu nó ở trên giấy hay ở dạng hình ảnh. 3.3.1.2 Nhúng dữ liệu bằng cách dịch chuyển từ: Từ mã được nhúng vào một văn bản bằng cách dịch chuyển vị trí của các từ trong các dòng văn bản, trong khi vẫn giữ nguyên khoảng cách các dòng. Phương pháp này cũng được áp dụng cả trên tập tin văn bản và ảnh bitmap của trang văn bản. Phương pháp này chỉ hữu dụng cho các văn bản có sự biến động về khoảng cách giữa hai từ cạnh nhau, ví dụ như một văn bản có sắp chữ. Quá trình rút trích cần phải có một văn bản gốc, hay ít nhất cũng biết được giá trị khoảng cách giữa các từ. Phương pháp thực hiện như sau: với mỗi dòng văn bản, tìm ra các khoảng cách lớn nhất và bé nhất, khoảng cách lớn nhất được giảm xuống một lượng, và khoảng cách bé nhất cũng được tăng thêm một lượng như trên, như vậy sẽ giữ nguyên chiều dài của dòng văn bản và gây ra ít thay đổi nhận thấy được trên văn bản. Nhúng dữ liệu bằng cách dịch chuyển từ ít bị người đọc nhận biết hơn phương pháp dịch chuyển dòng, vì khoảng cách giữa hai từ kế nhau trong một dòng thường bị dịch chuyển để hỗ trợ cho sự sắp chữ trong văn bản. Tuy nhiên, phương pháp dịch chuyển từ có thể bị phát hiện và bị đánh bại bằng hai phương pháp sau: ™ Nếu một người biết được thuật toán sử dụng trong định dạng sắp xếp chữ văn bản, khoảng cách thật sự giữa hai từ có thể được đo và so sánh với khoảng cách trong văn bản gốc. Sự khác biệt trong khoảng cách sẽ chứa dữ liệu nhúng. Kh oa C NT T - Ð H KH TN TP .H CM -26- ™ Bằng cách chia lại khoảng cách giữa các từ được dịch chuyển, hay dịch chuyển ngẫu nhiên các từ trong văn bản, một người khác có thể làm mất đi từ mã. 3.3.1.3 Nhúng dữ liệu đặc trưng: Đây là phương pháp thứ ba của Brassil. Giống như hai phương pháp trên, phương pháp này cũng hỗ trợ cả trên ảnh nhị phân của văn bản hay trên tập tin định dạng văn bản. Đặc trưng của văn bản có thể bị thay đổi hay không bị thay đổi phụ thuộc vào từ mã. Việc nhúng các bit vào văn bản có thể bằng cách kéo dài hay cắt ngắn các nét trên cùng của các kí tự như b, d, h,... Trước khi mã hóa, các dòng trên của các kí tự được kéo dài hay cắt ngắn, sau đó sẽ bị thay đổi một lần nữa để mã hóa dữ liệu đặc biệt. Điều này tránh được sự rút trích dữ liệu công khai, vì chiều cao các kí tự trong văn bản gốc không được biết. Và dĩ nhiên, quá trình giải mã cần phải có các ảnh gốc. Phương pháp mã hóa đặc trưng có thể thực hiện trên một lượng dữ liệu nhúng lớn, vì một văn bản có nhiều đặc trưng. Phương pháp này có thể bị đánh bại bằng cách điều chỉnh lại chiều dài các kí tự theo một giá trị cố định. 3.3.2 Các kỹ thuật của Bender: Các văn bản ở dạng số rất khó chứa dữ liệu ẩn (trong khi văn bản trên giấy thì dễ hơn). Các văn bản ở dạng số ít có các thao tác biến đổi như trên ảnh, nhưng nếu văn bản xuất hiện một từ hay một câu lạ thì dễ dàng bị người đọc phát hiện. Bender[3][4] đưa ra ba phương pháp chính sử dụng cho ẩn dữ liệu trên văn bản: (1) phương pháp khoảng trắng mở sử dụng các khoảng trắng không được sử Kh oa C NT T - Ð H KH TN TP .H CM -27- dụng trong các trang in, (2) phương pháp cú pháp sử dụng các dấu câu và (3) phương pháp ngữ nghĩa thao tác dựa trên nghĩa của các từ. 3.3.2.1 Phương pháp khoảng trắng mở (open space methods): Bender đưa ra hai lý do của việc sử dụng khoảng trắng để mã hóa. Thứ nhất, khi thay đổi số lượng các khoảng trắng thì nghĩa của câu ít bị ảnh hưởng. Thứ hai, người đọc tình cờ sẽ không chú ý đến sự thay đổi của các khoảng trắng. Trong phương pháp này lại có ba phương pháp nhỏ: phương pháp khai thác khoảng trắng giữa các câu, giữa các từ và giữa các dòng trong các văn bản được sắp chữ. ™ Phương pháp khai thác khoảng trắng giữa các câu: mã hóa một chuỗi nhị phân vào văn bản bằng cách đặt một hay hai khoảng trắng sau mỗi kí tự kết thúc, ví dụ như một câu trong văn xuôi, một dấu chấm phẩy (;) trong ngôn ngữ C,... Một khoảng trắng mã hóa 0, hai khoảng trắng mã hóa 1. Phương pháp này không hiệu quả, nó cần phải có một văn bản lớn để mã hóa một lượng bit nhỏ (một bit trên một câu tương ứng với tỉ lệ dữ liệu là 1bit/160 byte với giả thuyết một câu trung bình có 80 kí tự). Phương pháp này cũng phụ thuộc vào cấu trúc của văn bản. Hầu hết các trình xử lý văn bản đều xử lý khoảng trắng sau mỗi câu. ™ Phương pháp khai thác khoảng trắng sau mỗi dòng: dữ liệu mã hóa cho phép xác định số khoảng trắng sau mỗi dòng. Hai khoảng trắng mã hóa một bit, bốn khoảng trắng mã hóa hai bit, tám khoảng trắng mã hóa ba bit,... Phương pháp này có thể thực hiện trên mọi loại văn bản, vì nó không bị người đọc phát hiện do những khoảng trắng thêm vào nằm ngoài phạm vi của văn bản. Nó còn mã hóa được số lượng bit nhiều hơn phương pháp trên. Trong phương pháp khai Kh oa C NT T - Ð H KH TN TP .H CM -28- thác khoảng trắng sau mỗi câu, văn bản sau khi đã nhúng dữ liệu, qua các chương trình như thư điện tử có khả năng bị cắt mất khoảng trắng. Vấn đề duy nhất của phương pháp khai thác khoảng trắng sau mỗi dòng là không thể lấy lại dữ liệu nhúng được sau khi văn bản chứa đã qua các thao tác sao chép trên giấy. ™ Phương pháp khai thác các khoảng trắng ngay sau các từ: một khoảng trắng mã hóa bit 0, hai khoảng trắng mã hóa bit 1. Phương pháp này cho kết quả vài bit trên một dòng. Để xác định khoảng trắng nào là của dữ liệu nhúng, khoảng trắng nào là của văn bản, Bender sử dụng phương pháp mã hóa giống như phương pháp của Manchester. Manchester sử dụng một nhóm bit để đại diện cho một bit. “01” được giải mã thành 1, “10” là 0, “00” và “11” là rỗng. Ví dụ, chuỗi được mã hóa là “1000101101” thì được giải mã thành “001”, trong khi chuỗi “110011” là rỗng. Phương pháp khoảng trắng hiệu quả trong các văn bản định dạng ASCII. Một số dữ liệu có khả năng bị mất khi văn bản được in ra. Hình 6 là ví dụ nhúng dữ liệu vào đoạn văn bản theo phương pháp khai thác các khoảng trắng sau mỗi dòng. Hình 6. Phương pháp khoảng trắng mở khai thác các khoảng trắng sau mỗi dòng. Hình (a) là đoạn văn bản trước khi nhúng, hình (b) là đoạn văn bản sau khi nhúng Kh oa C NT T - Ð H KH TN TP .H CM -29- Trong đoạn văn bản đã được nhúng dữ liệu, cuối dòng 2 có 2 khoảng trắng nhúng được 1 bit, cuối dòng 3 có 4 khoảng trắng nên đó là 2 bit được nhúng. Hình 7 là ví dụ nhúng dữ liệu vào văn bản, khai thác khoảng trắng sau các từ. Đoạn văn bản trên chứa dữ liệu nhúng “010110010011010”. Hình 7. Đoạn văn bản chứa dữ liệu nhúng sử dụng các khoảng trắng sau mỗi từ. 3.3.2.2 Phương pháp cú pháp (syntactic methods): Hai phương pháp cú pháp và ngữ nghĩa có thể kết hợp song song. Trong nhiều tình huống sau khi mã hoá, văn bản có số lượng dấu câu nhiều hay có dấu câu sai, nhưng lại không ảnh hưởng lớn đến ngữ nghĩa trong văn bản. Ví dụ cụm từ “bread, butter, and milk” và “bread, butter and milk” cả hai đều dùng dấu phẩy đúng. Bất cứ khi nào trong câu sử dụng dạng thứ nhất thì mã hóa 1, dạng thứ hai thì mã hóa 0. Trong một số ví dụ còn sử dụng các từ viết tắt, viết gọn. Phương pháp này chỉ mã hóa được vài bit trên 1Kb văn bản. Phương pháp cú pháp còn bao gồm cả cách thay đổi trong cách thức diễn đạt và cấu trúc văn bản mà không làm thay đổi ngữ nghĩa. Ví dụ, từ câu “Before the night is over, I will have finished” chuyển thành câu “I will have finished Kh oa C NT T - Ð H KH TN TP .H CM -30- before the night is over ”. Phương pháp này rõ ràng có hiệu quả hơn phương pháp khoảng trắng, nhưng khả năng khai thác của nó bị giới hạn. 3.3.2.3 Phương pháp ngữ nghĩa (semantic methods): Phương pháp này cũng tương tự như phương pháp cú pháp. Phương pháp ngữ nghĩa dùng giá trị chính hay phụ đồng nghĩa. Ví dụ từ “big” có thể thay bằng “large” (Hình 8). Khi giải mã, từ có ý nghĩa chính sẽ đại diện cho giá trị 1, từ có ý nghĩa phụ sẽ đại diện cho giá trị 0. Tuy nhiên phương pháp này có thể làm thay đổi ngữ nghĩa của câu, mặc dù từ thay thế cùng nghĩa, nhưng sắc thái của câu đã bị thay đổi (các từ được dùng thích hợp trong từng ngữ cảnh). Hình 8. Các cặp từ đồng nghĩa. 3.4 Các kỹ thuật ẩn dữ liệu trên ảnh tĩnh: Ảnh tĩnh là một đối tượng rất thích hợp cho ẩn dữ liệu, nhất là trong Steganography vì các yếu tố sau đây: Một ảnh chứa rất nhiều dữ liệu, giả sử một ảnh có kích thước 600 × 400 được mỗi pixel được biểu diễn bởi 3 byte RGB thì có dung lượng là 720000 byte. Kh oa C NT T - Ð H KH TN TP .H CM -31- Một ảnh có chứa dữ liệu nhúng sẽ ít gây chú ý hơn là một văn bản. Sự khác biệt giữa ảnh gốc và ảnh sau khi nhúng rất khó nhận ra được bằng mắt thường. Thông tin có thể được ẩn trong ảnh tĩnh bằng nhiều cách. Thông điệp được mã hóa từng bit vào ảnh. Các kỹ thuật mã hóa phức tạp hơn là kỹ thuật ẩn thông điệp vào những vùng nhiễu của ảnh, như vậy sẽ ít gây sự chú ý hơn. Thông điệp cũng có thể được rải ngẫu nhiên trên ảnh chứa. 3.4.1 Các hướng tiếp cận của các kỹ thuật ẩn dữ liệu trên ảnh tĩnh: ™ Chèn vào bit thấp nhất LSB (Least Significant Bit). ™ Các kỹ thuật lọc và mặt nạ. ™ Các thuật toán và các phép biến đổi. 3.4.1.1 Hướng tiếp cận chèn vào bit LSB: Phương pháp chèn bit vào LSB là phương pháp được biết nhiều nhất trong kỹ thuật ẩn dữ liệu. Đây là một hướng tiếp cận thông dụng, đơn giản để nhúng thông tin vào ảnh. Nhưng phương pháp này có nhược điểm là dễ bị tấn công bởi các thao tác trên ảnh. Một sự chuyển đổi từ dạng GIF hay BMP sang dạng nén mất dữ liệu (ví dụ như JPEG) có thể hủy hết thông tin ẩn trong ảnh. Khi sử dụng kỹ thuật LSB cho ảnh 24 bit màu, mỗi pixel có 3 bit được dùng để mã hóa dữ liệu (vì mỗi pixel được biểu diễn bằng 3 byte). Sự thay đổi trên pixel khó bị mắt người nhận ra. Ví dụ, kí tự A có thể được ẩn trong 3 pixel. Giả sử 3 pixel của ảnh gốc có giá trị nhị phân như sau: ( 00100111 11101001 11001000 ) ( 00100111 11001000 11101001 ) ( 11001000 00100111 11101001 ) Kh oa C NT T - Ð H KH TN TP .H CM -32- Giá trị nhị phân của kí tự A là (10000011). Sau đây là kết quả sau khi nhúng giá trị nhị phân của A vào 3 pixel trên, bắt đầu từ byte đầu tiên bên trái trên cùng: ( 00100111 11101000 11001000 ) ( 00100110 11001000 11101000 ) ( 11001000 00100111 11101001 ) Chỉ có các bit LSB in đậm bị thay đổi. Các kỹ thuật chèn vào bit LSB cải tiến là dữ liệu có thể được ẩn trong bit thấp nhất và bit thấp thứ hai trong byte mà mắt người vẫn không thể nhận ra sự thay đổi. Sử dụng kỹ thuật LSB trong ảnh 8 bit màu phải cẩn thận hơn đối với ảnh 24 bit màu vì sự thay đổi màu sắc rõ hơn. 3.4.1.2 Phương pháp ngụy trang và lọc: Kỹ thuật ngụy trang và lọc ẩn thông tin bằng cách đánh dấu một ảnh bằng một ký hiệu mờ. Các kỹ thuật nhúng dấu hiệu thích hợp với ảnh hơn, các kỹ thuật đó có thể được áp dụng trên ảnh tĩnh mà không sợ ảnh hưởng của định dạng ảnh nén mất dữ liệu. Bằng cách che phủ, hoặc ngụy trang một tín hiệu mờ, hệ thống thị giác của người HVS không thể nhận biết được sự thay đổi trên ảnh. Về mặt kỹ thuật, nhúng dấu hiệu không phải là một dạng của Steganography. Trong khi Steganography dấu dữ liệu trong ảnh, nhúng dấu hiệu mở rộng thông tin của ảnh và trở thành một thuộc tính của ảnh chứa, cung cấp các chi tiết về bản quyền, giấy phép, quyền sỡ hữu. Các kỹ thuật ngụy trang thích hợp hơn cho các ảnh nén dạng JPEG hơn là các kỹ thuật LSB vì chúng có thể miễn dịch trước các thao tác nén hay xén ảnh. Kh oa C NT T - Ð H KH TN TP .H CM -33- 3.4.1.3 Các thuật toán và phép biến đổi: Hiện nay trên Internet, ảnh JPEG đã trở nên phong phú vì là chuẩn nén tốt, chất lượng cao và tỉ lệ nén cao. Nguyên lý cơ bản trong chuẩn nén JPEG là phép biến đổi cosin rời rạc DCT (Discrete Cosine Transform). DCT là phép biến đổi nén mất dữ liệu, vì giá trị cosin không thể tính toán chính xác được và các lỗi trong tính toán có thể xuất hiện. Sự khác biệt giữa dữ liệu của ảnh gốc và dữ liệu của ảnh sau khi nén phụ thuộc vào các giá trị và các phương pháp sử dụng trong tính toán DCT. Các ảnh cũng có thể tiến hành bằng các phép biến đổi Fast Fourier và biến đổi Wavelet. Hệ HVS có độ nhạy rất thấp với các thay đổi nhỏ trên độ chói. Các hệ thống hiện đại sử dụng truyền thông phổ rộng để truyền một tín hiệu dãy tần số thấp trên một băng thông lớn hơn, vì thế mật độ của tín hiệu trên kênh truyền chỉ giống như nhiễu. Hai kỹ thuật phổ rộng khác nhau được gọi là dãy trực tiếp và nhảy tần số. Kỹ thuật dãy trực tiếp dấu thông tin bằng cách thay đổi pha của tín hiệu dữ liệu với một chuỗi số giả ngẫu nhiên[15] mà cả người gửi và người nhận đều biết. Kỹ thuật nhảy tần số phân chia băng thông có sẵn thành nhiều kênh truyền và nhảy giữa các kênh truyền đó (cũng được chèn bằng một dãy số giả ngẫu nhiên). 3.4.2 Các kỹ thuật ẩn dữ liệu trên ảnh tĩnh: Các kỹ thuật ẩn dữ liệu trên ảnh tĩnh được chia thành hai loại theo kích thước dữ liệu nhúng: (1) ẩn dữ liệu với tỉ lệ bit thấp, lượng dữ liệu được nhúng trong ảnh rất ít, có kỹ thuật chỉ nhúng một bit vào ảnh vì thế tính bền vững của dữ liệu nhúng cao và (2) ẩn dữ liệu với tỉ lệ bit cao, lượng dữ liệu được nhúng cao hơn nhiều và do đó tính bền vững cũng thấp hơn. Kh oa C NT T - Ð H KH TN TP .H CM -34- 3.4.2.1 Ẩn dữ liệu với tỉ lệ bit thấp: Hai kỹ thuật điển hình là Patchwork và mã hóa kết cấu khối. Patchwork nhúng một bit đơn vào ảnh với một giá trị tin cậy cao dựa trên phân phối Gaussian. Mã hóa kết cấu khối dựa trên các vùng đồng nhất trên ảnh. 3.4.2.1.1 Patchwork- cách tiếp cận thống kê: Patchwork là một hướng tiếp cận theo phương pháp thống kê, dựa trên các dãy số giả ngẫu nhiên[15]. Patchwork nhúng vào ảnh chứa một số thống kê đặc thù, chứa một hàm phân phối Gaussian sao cho mắt người không thể nhận ra. Hình 9 mô tả một phương pháp Patchwork dùng một vòng lặp đơn. Hai mảnh A, B được chọn ngẫu nhiên, mảnh A có màu sáng trong khi mảnh B có màu tối. Một số liệu thống kê duy nhất sẽ cho biết dấu hiệu có xuất hiện hay không. Patchwork có đặc điểm là không phụ thuộc vào nội dung của ảnh chứa và kỹ thuật này có khả năng tránh được các biến đổi phi hình học. Để minh họa, ảnh chứa trong ví dụ này có mức sáng 256, hệ thống lượng tử tuyến tính sẽ bắt đầu từ 0 và tất cả các mẫu không phụ thuộc vào các mẫu khác, hay nói chính xác hơn là các mẫu độc lập với nhau. Kh oa C NT T - Ð H KH TN TP .H CM -35- Hình 9. Vòng lặp đơn trong thuật giải Patchwork Nguyên lý thuật giải: ™ Sử dụng lý thuyết thống kê, hàm phân phối Gaussian để mã hóa. ™ Chọn một khóa để tạo một dãy số ngẫu nhiên. ™ Dựa vào các số trên dãy số ngẫu nhiên, chọn ra mỗi lần hai mảnh trên ảnh chứa, một mảnh có giá trị sáng (A-ai) và một mảnh có giá trị tối hơn (B-bi). ™ Trừ vào ai một lượng δ và cộng vào bi một lượng δ . Đối với mức sáng 256 thì δ có giá trị từ 1 đến 5. ™ Lặp lại quá trình n lần (thông thường n≈10000). ™ Tính S=∑ = − n i ii ba 1 . ™ Sử dụng hàm phân phối Gaussian để tính S với độ tin cậy tốt. Nếu S dương thì giá trị mã hóa là 1, nếu S âm thì mã hóa 0. Sau đây là bảng số liệu mô tả mối quan hệ giữa n và độ tin cậy, với 2δ = : Kh oa C NT T - Ð H KH TN TP .H CM -36- STT Độ tin cậy n 0 50.00% 0 1 84.13% 679 2 97.87% 2713 3 99.87% 6104 Bảng 3. Mối quan hệ giữa n và độ tin cậy Vì n hoặc δ tăng, nên đồ thị hàm phân bố của nS ′ dịch chuyển qua phải. Sau đây là một số cải tiến của phương pháp Patchwork: ™ Các mảnh bao gồm nhiều pixel tốt hơn các mảnh chỉ có một pixel. ™ Kết hợp với mã affine hay các thông tin heuristic dựa trên đặc điểm nhận biết sẽ làm phương pháp này mạnh hơn. Mã hóa Patchwork nhạy với các phép biến đổi affine, nếu các điểm trên ảnh chứa bị dịch chuyển bới các phép tịnh tiến hay biến đổi tỉ lệ thì dữ liệu nhúng sẽ bị mất. ™ Patchwork có khả năng chống lại các thao tác xén ảnh, nếu các mảnh không nằm trong phạm vi bị xén thì dữ liệu nhúng vẫn giữ nguyên. Hình dáng của mảnh: Hình 10 mô tả ba loại hình dáng mảnh và sự phân bố tương ứng với mảnh đó. Hình 10a) mảnh nhỏ, cạnh sắc, kết quả là phần lớn năng lượng của mảnh tập trung ở phần tần số cao của mảnh: dễ bị mất dữ liệu khi qua thao tác nén mất dữ liệu. Hình 10b) thì năng lượng tập trung ở phần tần số thấp. Hình 10c) phân phối năng lượng đều ở phần tần số cao và tần số thấp. Kh oa C NT T - Ð H KH TN TP .H CM -37- Hình 10. Hình dáng các mảnh Lựa chọn hình dáng mảnh tối ưu nhất phụ thuộc vào từng loại ảnh và các thao tác trên ảnh. Nếu ảnh chứa có định dạng là JPEG thì mảnh có dạng như hình 10b) là tối ưu nhất vì năng lượng phân bố tại phần tần số thấp. Nếu trên ảnh chứa có thao tác tăng độ tương phản thì mảnh như hình 10a) là tốt nhất. Nếu trong trường hợp không biết các thao tác trên ảnh thì chọn mảnh như hình 10c) là tốt nhất. Sự sắp xếp các mảnh cũng ảnh hưởng đến hiệu quả của phương pháp. Hình 11 mô tả ba phương pháp sắp xếp mảnh. Hình 11a) là sắp xếp theo dạng lưới thẳng, phương pháp này ít được sử dụng khi n lớn vì HSV rất nhạy với dạng này. Hình 11b) là sắp xếp theo dạng lục giác đều. Hình 11c) là sắp xếp theo ngẫu nhiên. Kh oa C NT T - Ð H KH TN TP .H CM -38- Hình 11. Sự sắp xếp các mảnh Phương pháp Patchwork có vài giới hạn: thứ nhất là tỉ lệ dữ liệu mã hóa thấp, chỉ phù hợp cho các ứng dụng mã hóa với tỉ lệ dữ liệu thấp, thứ hai là các pixel trong ảnh chứa phải được ghi nhớ và không được di chuyển. 3.4.2.1.2 Mã hóa kết cấu khối (texture block coding)-Cách tiếp cận trực quan: Phương pháp này ẩn dữ liệu trong những mẫu kết cấu ảnh ngẫu nhiên và liên tiếp. Kỹ thuật này được thực hiện bằng cách sao chép một vùng ảnh từ một mẫu kết cấu ngẫu nhiên trên ảnh đến một vùng khác có kết cấu tương tự. Hình 12. Một ví dụ về phương pháp mã hóa kết cấu khối Kh oa C NT T - Ð H KH TN TP .H CM -39- Quá trình giải mã: ™ Tự động đặt hai ảnh tương quan chồng lên nhau (ảnh gốc và ảnh sau khi nhúng dữ liệu). Việc này sẽ làm hiện ra các đỉnh mà ở đó có các vùng chồng chéo lên nhau. ™ Dịch chuyển ảnh. Sau đó trừ giá trị ảnh gốc với ảnh sao chép của nó. Gán giá trị 0 cho mép bìa ảnh nếu cần thiết. ™ Điều chỉnh kết quả và giới hạn nó để nó chỉ gồm những giá trị gần 0. Ảnh chứa dữ liệu sẽ thấy được các giá trị đó. Nếu ảnh chứa dữ liệu ẩn bị thao tác bằng các phép biến đổi thì cả hai vùng sẽ bị thay đổi như nhau vì chúng là hai vùng đồng nhất có kết cấu giống nhau. Nếu chọn lựa vùng có kích thước hợp lý, phần bên trong của khối thay đổi như nhau qua hầu hết các phép biến đổi phi hình học. Mã hóa kết cấu khối không phải là không có bất lợi. Hiện nay, kỹ thuật này cần có các thao tác của con người để chọn lựa vùng nguồn và vùng đích có kích thước thích hợp và ước lượng ảnh hưởng trực quan của các biến đổi trên ảnh. Thật ra có thể tự động hóa quá trình này bằng cách sử dụng một máy tính nhận dạng kết cấu các vùng sao chép và dán lên ảnh. Tuy nhiên, kỹ thuật này không có tác dụng với ảnh thiếu vùng có kích thước kết cấu vừa phải và kết cấu liên tiếp. 3.4.2.2 Mã hóa với dữ liệu bit cao – Mã hóa affine: Mã hóa dữ liệu với tỉ lệ bit cao có thể có rất ít tác động lên ảnh chứa, nhưng nó không có khuynh hướng tránh được các biến đổi trên ảnh chứa. Hình thức thông thường nhất là thay thế bit thấp nhất của độ chói bằng dữ liệu nhúng. Kh oa C NT T - Ð H KH TN TP .H CM -40- Không có một kỹ thuật đã biết nào tránh được tất cả các phép biến đổi hay tổ hợp các phép biến đổi. Đối với tổ hợp các phép biến đổi, thường người ta sử dụng thêm một kỹ thuật khác để hỗ trợ. Kỹ thuật hỗ trợ này rất quan trọng đối với các phép biến đổi affine, và nó giữ lại sự đồng bộ cho luồng dữ liệu mã hóa. Sau đây là hai phương pháp của Yu –Yuan Chen , Hsiang – Kuang Pan và Yu – Chee Tseng ở khoa Khoa học máy tính trường Đại học Trung tâm quốc gia Đài Loan[9]. Hai phương pháp này nhúng dữ liệu bằng cách thay thế các bit trong dữ liệu ảnh, chúng không tránh được các phép biến đổi affine, nhưng số lượng dữ liệu được nhúng lớn và khả năng một người thứ ba giải mã được là rất khó, tuy nhiên cả hai phương pháp đều sử dụng ảnh nhị phân làm đối tượng nhúng. 3.4.2.2.1 Phương pháp nhúng dữ liệu vào các khối, mỗi khối chứa tối đa một bit dữ liệu: Phương pháp này nhúng dữ liệu bằng cách chia ảnh ra thành các khối kích thước bằng nhau, mỗi khối được nhúng tối đa một bit dữ liệu. Dữ liệu của mỗi khối là các bit LSB của từng pixel trong ảnh. Ký hiệu: ™ B: ma trận 0,1 . ™ Với B1 và B2 là hai ma trận cùng kích thước: ™ 1 2B BÙ : AND từng phần tử tại vị trí i,j của B1 với từng phần tử i,j tương ứng của B2. ™ [B]i,j : phần tử của B tại vị trí hàng i, cột j. ™ SUM ( B ): tổng tất cả các thành phần trong B. Kh oa C NT T - Ð H KH TN TP .H CM -41- ™ F: ma trận điểm ảnh, là ma trận sẽ chứa dữ liệu được nhúng. Có kích thước là bội số các khối m × n . ™ K: ma trận 0,1 có kích thước m × n, còn gọi là ma trận khóa. Thuật giải: Nguyên lý: thay đổi giá trị trong các Fi thành iF¢ sao cho: ( ) mod 2iSUM F K b¢Ù = (3.1) Với b là bit cần nhúng. Bước 1: Chia F thành nhiều khối, mỗi khối có kích thước m n´ . Bước 2: Với mỗi khối Fi nhận được, xét điều kiện: 0 ( ) ( )iSUM F K SUM K< Ù < (3.2) - Nếu TRUE: nhảy đến bước 3 để nhúng 1 bit vào Fi. - Nếu FALSE: trong khối Fi sẽ không có dữ liệu được nhúng. Bước 3: Giả sử bit cần được nhúng là b. (a) If ( ( ) mod 2iSUM F K bÙ = ) then Giữ nguyên Fi. (b) Else if ( ) 1iSUM F KÙ = then Chọn ngẫu nhiên một bit [Fi]j,k =0 với [K]j,k =1 và đổi [Fi]j,k =1. (c) Else if ( ) ( ) 1iSUM F K SUM KÙ = - then Chọn ngẫu nhiên một bit [Fi]j,k =1 với [K]j,k =1 và đổi [Fi]j,k = 0. (d) Else Kh oa C NT T - Ð H KH TN TP .H CM -42- Chọn ngẫu nhiên một bit [Fi]j,k với [K]j,k =1 và lấy phần bù của [Fi]j,k. End if. Cơ sở toán học: Sau khi thực hiện các bước ta được các iF¢, là các khối Fi sau khi bị thay đổi. Với điều kiện: 0 ( ) ( )iSUM F K SUM K< Ù < thì b mới được nhúng vào Fi Þ 0 ( ) ( )iSUM F K SUM K¢< Ù < (3.3) Gọi ,[ ]i j kF ¢ là phần bù của ,[ ]i j kF , thì , ,([ ] )i j k j kF K¢Ù là phần bù của , ,([ ] )i j k j kF KÙ với Kj,k =1. Và ( ) ( ) 1iSUM F K SUM F K¢Ù = Ù ± . Dấu + xảy ra trong trường hợp ,[ ]i j kF =0, dấu – xảy ra trong trường hợp ,[ ]i j kF = 1. Biểu thức liên quan: 0 ( ) ( ) ( ) mod 2i iSUM F K SUM K SUM F K b¢ ¢< Ù < Þ Ù º hay: ( ) mod 2iSUM F K b¢Ù = Đặt ( )ic SUM F K= Ù . Ta có 4 trường hợp tương quan giữa c và b xảy ra: TH1: c=0, b=0; TH2: c=1,b=1; TH3: c=1,b=0; TH4: c=0,b=1. Kh oa C NT T - Ð H KH TN TP .H CM -43- Xét TH1 và TH2, b =c nên ( ) mod 2i i ic SUM F K b F F¢= Ù = Þ = ứng với trường hợp (a). Xét TH3,TH4: c=!b nên cần biến đổi ,[ ]i j kF : { },[ ] \ ( ) ( ) 1i j k i iF SUM F K SUM F K¢Ù = Ù ± . Þ ,[ ]i j kF ¢ phải là phần bù của ,[ ]i j kF . Xét 3 giá trị của ( )iSUM F KÙ : ™ ( ) 1iSUM F KÙ = : thì ( ) ( ) 1i iSUM F K SUM F K¢Ù = Ù + , phải tăng ( )iSUM F KÙ thêm một giá trị để thỏa điều kiện (3.2). Nên ta chọn ngẫu nhiên một i j,k[F ] 0= với , 1j kK = và thay đổi ,[ ] 1i j kF = . ™ ( ) ( ) 1iSUM F K SUM KÙ = - : ( ) ( ) 1i iSUM F K SUM F K¢Ù = Ù - , phải giảm ( )iSUM F KÙ đi một giá trị để thỏa điều kiện (3.2). Nên chọn ngẫu nhiên một ,[ ] 1i j kF = với , 1j kK = và thay đổi ,[ ] 0i j kF = . ™ Với các giá trị còn lại của ( )iSUM F KÙ nếu tăng hay giảm ( )iSUM F KÙ một giá trị thì vẫn thỏa điều kiện (3.2). Chọn ngẫu nhiên một ,[ ]i j kF với , 1j kK = và ,[ ]i j kF ¢ là phần bù của ,[ ]i j kF . Ví dụ: Hình 13. ™ F: ma trận 6 × 6. ™ K: ma trận 3 × 3. ™ Chia F thành F1, F2, F3, F4 mỗi Fi có kích thước 3 × 3. ™ Xét 1( ) ( ) 5SUM F K SUM KÙ = = : không có bit nào được nhúng vào F1, 1 1F F¢º . Kh oa C NT T - Ð H KH TN TP .H CM -44- ™ Xét 2( ) 3SUM F KÙ = thỏa (3.1), b1 = 0 thỏa (b), lấy ngẫu nhiên [F2]2,3 = 0 với K2,3 =1 và đổi 2 2,3 2 2,3[ ] 1 [ ]F F ¢= = . ™ Xét 3( ) 3SUM F KÙ = thỏa (3.1), b2=1 thỏa (a) nên giữ nguyên F3. ™ Xét 4( ) 4SUM F KÙ = thỏa (3.1), và 4( ) ( ) 1SUM F K SUM KÙ = - thỏa (c), lấy ngẫu nhiên [F2]2,3 = 1 với K2,3 =1 và đổi 2 2,3 2 2,3[ ] 0 [ ]F F ¢= = . Hình 13. Nhúng 3 bit vào ảnh 6 x 6 Đánh giá thuật giải: ™ Do sử dụng toán tử logic AND nên: ( )iSUM F KÙ không bao giờ vượt quá SUM (K). ™ So sánh giữa F và F¢ tại những vị trí hàng i, cột j tương ứng, nếu hai giá trị khác nhau thì tại đó Ki,j =1 và ngược lại Ki,j =0. Như vậy, khi so sánh tất cả các phần tử của F và F¢ thì ta có thể suy ra toàn bộ ma trận K, K không còn là bí mật nữa. ™ Nếu K có nhiều giá trị 1 thì sự khác nhau giữa F và F¢ gia tăng, gây nên sự nghi ngờ có chứa dữ liệu. Nhưng nếu K có nhiều giá trị 0 thì thuật giải cũng không hoàn toàn khả thi. ™ Nếu F có tất cả các giá trị hoàn toàn là 1 thì khả năng nghi nghờ chứa dữ liệu gia tăng và suy luận ra K dễ dàng. Nhưng nếu F có nhiều giá trị 0 thì tỉ lệ ẩn dữ liệu không cao. Kh oa C NT T - Ð H KH TN TP .H CM -45- Tóm lại, việc chọn K và F phù hợp là điều quan trọng. Phương pháp mã hoá dữ liệu này không an toàn cao, số lượng dữ liệu được chứa không nhiều. 3.4.2.2.2 Phương pháp nhúng dữ liệu vào các khối, mỗi khối chứa tối đa hai bit dữ liệu: Phương pháp này là phương pháp cải tiến phương pháp trên. Nó bảo đảm tỉ lệ ẩn của dữ liệu cao hơn, do dùng một ma trận trọng lượng W. Phương pháp này cũng dựa trên phép toán mod và toán tử logic Å . Ở mỗi khối m n´ , sẽ có r bit được nhúng với 2 1r mn- £ , nhưng chỉ làm thay đổi tối đa 2 bit trên ma trận chứa. Ký hiệu: ™ F: ma trận điểm ảnh, sẽ chứa dữ liệu được nhúng, giả sử là F được chia thành k khối Fi có kích thước m n´ . Sau các bước thực hiện, F sẽ bị thay đổi thành ma trận F ¢. ™ K: ma trận khóa. Nó là một ma trận m n´ , được chọn ngẫu nhiên phù hợp theo từng trường hợp. Các giá trị trong K là 0 hoặc 1. ™ W: ma trận trọng lượng m n´ , với [W]i,j ∈ {1.. 2r –1}. Cách sắp xếp các giá trị được chọn ngẫu nhiên. ™ r: số lượng bit được nhúng vào một khối m n´ , r thỏa 2 1r mn- £ . ™ B: các thông tin được nhúng, B gồm kr bit, k là số lượng khối của F. ™ A1, A2 là hai ma trận m n´ , toán tử A1 ⊗ A2 là toán tử mà " i,j i=1...m, j=1..n thì 1 , 2 ,[ ] [ ]i j i jA A´ .. Ma trận trọng lượng: Ma trận trọng lượng W m n´ thỏa các điều kiện sau: ™ 2 1r mn- £ . (3.4) Kh oa C NT T - Ð H KH TN TP .H CM -46- ™ Các phần tử [W]i,j Î {1.. 2r –1}. (3.5) ™ " k Î {1… 2r –1}, k phải xuất hiện ít nhất một lần trong W. (3.6) Ma trận W được chọn ngẫu nhiên thỏa điều kiện và theo từng trường hợp. Với m hàng n cột, W có thể có các lựa chọn sau: ™ Có 2r –1 giá trị, vì thế để chọn giá trị cho mn phần tử có: 2 1r mnC - ™ Ta có thể sắp xếp ngẫu nhiên các giá trị: (2r –1)! cách. ™ Với mn - 2r –1 giá trị còn lại có thể sắp xếp ngẫu nhiên: (2 1)(2 1)r mn r− −− Vậy: số lần chọn lựa W : 2 1 2 1 *(2 1)!*(2 1) r r mn r r mnC - - - - - . Ví dụ: m = n = 8 và r = 5. Ta có 3164C 31!*31 33 cách chọn W. Vì thế tỉ lệ bảo mật thông tin rất cao nếu W không được công bố. Vì phương pháp này dùng toán tử mod: 1 2... (( ) ) mod 2r ib b b SUM F K W= Å Ä . và 0 (( ) ) 2 1riSUM F K W£ Å Ä < - nên W phải thỏa điều kiện 3 điều kiện trên. Nếu 2r –1> mn thì { } { } { },1...2 1 \ [ ] 1... , 1...r i jk k W i m j n$ Î - ¹ " Î Î ⇒ (3.6) sai. Thuật giải: Fi sẽ được chuyển thành iF¢ bằng cách lấy phần bù của một giá trị nào đó trong Fi để thỏa công thức sau: 1 2(( ) ) ... (mod 2 ) r i rSUM F K W b b b¢Å Ä º (3.7) 1 2(( ) ) mod 2 ... r i rSUM F K W b b b¢Û Å Ä = Bước 1: Chia F thành các khối Fi kích thước m × n. Tính Fi ⊕ K. Kh oa C NT T - Ð H KH TN TP .H CM -47- Bước 2: Tính (( ) )iSUM F K WÅ Ä . Bước 3: Với w={1…2r-1}. Từ ma trận kết quả Fi ⊕ K, tính: { }, , , ,( , ) \ ([ ] [ ] 0) ([ ] 2 [ ] 1)rw j k i j k j k i j kS j k W w F K W w F K= = Ù Å = Ú = - Ù Å = (3.8) Theo (3.8), Sw là tập hợp các bộ (j,k) sao cho nếu lấy phần bù của [Fi]j,k thì (( ) )iSUM F K WÅ Ä sẽ tăng thêm w. Có hai trường hợp: , ,[ ] [ ] 0j k i j kW w F K= Ù Å = : Ta thấy nếu lấy phần bù , ,[ ] [ ] 1 ( )i j k i j k iF F K SUM F K WÞ Å = Þ Å Ä tăng thêm w. , ,[ ] 2 [ ] 1 r j k i j kW w F K= - Ù Å = : Nếu lấy phần bù của ,[ ] (( ) )i j k iF SUM F K WÞ Å Ä giảm đi 2 r-w, Û tăng w khi lấy (( ) ) mod 2iSUM F K WÅ Ä . Bước 4: Ta có công thức: 1 2( ... ) (( ) )(mod 2 ) r r id b b b SUM F K Wº - Å Ä (3.9) Đây là biểu thức chênh lệch giữa tổng và giá trị được nhúng, để giải mã theo công thức (3.8) ta phải tăng tổng thêm một giá trị d. Đặt w wS S ¢= với mod 2rw w¢º . Khi d=0 không cần thay đổi Fi. Nếu d ≠ 0, thực hiện các bước sau: Chọn ngẫu nhiên một h Î {0,1…,2r-1} với điều kiện hdS ¹ Æ và S-(h-1)d ≠ Æ. Kh oa C NT T - Ð H KH TN TP .H CM -48- Chọn ngẫu nhiên một bộ (j,k) Î Shd và lấy phần bù của [Fi]j,k. Chọn ngẫu nhiên một bộ (j,k) Î S-(h-1)d và lấy phần bù của [Fi]j,k. Để tăng tổng thêm một lượng d, ta dùng hai tập khác rỗng Shd và S-(h-1)d. Tổng sẽ tăng thêm hd + (- (h-1)d) = d. Tuy nhiên ta phải gán giá trị cho các tập S0, S2.r, S2.2r, S3.2r… luôn rỗng. Cơ sở toán học: ™ Bổ đề 1: Chứng minh: Giả sử Sw =Æ . Theo điều kiện của W, phải có tối thiểu một [W]j,k = w. Nếu [ ] [ ], , 0j k j kFi K∧ = thì lấy phần bù của [Fi]j,k sẽ làm tăng tổng thêm w , như vậy ≠ ∅wS . Như vậy , ,[ ] [ ] 1i j k j kF KÙ = , thì khi lấy phần bù [Fi]j,k sẽ làm giảm tổng đi w, hay tăng tổng lên 2r-w (mod 2r), như vậy tập 2 wr S - ¹ Æ, với w ¹ 2r-1 vì w= 2r-w lúc đó 2 wr S - ¹ Æ. ™ Bổ đề 2: Với w=1…2r-1 và w ¹ ≠ 2r-1 thì mệnh đề sau đây đúng: 2 ( ) ( )rw wS S -= Æ Þ ¹ Æ 12r S - ¹ Æ Kh oa C NT T - Ð H KH TN TP .H CM -49- Chứng minh: Theo điều kiện của W, phải có tối thiểu một [W]j,k = 2r-1. Vì 1 12 2 mod 2r r r- -º - . Nếu , ,[ ] [ ] 0j k i j kW w F K= Ù Å = thì khi lấy phần bù của [Fi]j,k thì tổng tăng thêm 2r-1. Nếu , ,[ ] [ ] 1j k i j kW w F K= Ù Å = thì khi lấy phần bù của [Fi]j,k thì tổng giảm đi 2r-2r-1 hay tương đương tổng tăng thêm 2r-1. Như vậy cả trong 2 trường hợp 12rS - ¹ Æ. ™ Bổ đề 3: Chứng minh: Ta sẽ kiểm tra lần lượt các giá trị của h: Đầu tiên h=1, nếu dS ¹ Æ thì h=1là giải pháp được chọn, nếu trái lại thì dS- ¹ Æ theo bổ đề 1. h=2, nếu 2dS ¹ Æ thì h=2 được chọn, ngược lại 2dS- ¹ Æ theo bổ đề 1. Tiếp tục kiểm tra, nếu tất cả Si đều là rỗng thì 12rS - ¹ Æ theo bổ đề 2. Và với 2r-1, $ h sao cho 2r-1 là bội số của d. Như vậy luôn tìm được một h cho vấn dề. Ví dụ: Hình 14 và hình 15. Giả sử F là ma trận 8 8´ . F được chia thành 4 khối 4 4´ từ F1…F4. K ma trận khóa 4 4´ . Bước 4 luôn cho kết quả, và có tối đa 2 bit của Fi bị thay đổi để nhúng r bit dữ liệu. Kh oa C NT T - Ð H KH TN TP .H CM -50- W ma trận trọng lượng 4 4´ . B = 001010000001. r = 3. Các ma trận được mô tả như hình dưới đây. Thực hiện các bước: F1: 1(( ) ) 0(mod8)SUM F K WÅ Ä º . Và dữ liệu nhúng là 001, ta phải tăng tổng thêm 1. Vì 1 2,4[ ] 0F KÅ = và [W]2,4 = 1 ta có thể lấy phần bù của [F1]2,4. F2: 2(( ) ) 2SUM F K WÅ Ä º , dữ liệu nhúng là 010, không cần phải thay đổi F2. F3: 3(( ) ) 2SUM F K WÅ Ä º , dữ liệu nhúng là 000, ta phải tăng tổng thêm 6 bằng cách lấy phần bù của [F3]4,4. F4: 4(( ) ) 4SUM F K WÅ Ä º , dữ liệu nhúng là 001, ta phải tăng tổng thêm 5 bằng cách lấy phần bù của [F4]2,2 và [F4]3,2. Vì không có một bộ chỉ số nào trong F4 để lấy phần bù và tăng 5, nên ta chọn h=2. S10 = S2b = {(2,2)} và S-5= S3 = {(1,3),(2,1),(3,2),(3,4)}. Hình 14. Ảnh F, ma trận khóa K và ma trận trọng lượng W. Kh oa C NT T - Ð H KH TN TP .H CM -51- Hình 15. Ảnh F sau khi thực hiện toán tử XOR và ảnh chứa bị thay đổi dữ liệu 3.4.2.2.3 Phân tích khả năng che dấu và kết quả thực nghiệm: ™ Chi phí và khả năng bị phát hiện: Giả sử là chi tiết thuật toán, ma trận F, giá trị r, kích thước khối m × n và ma trận F ¢đã bị phát hiện, thì cũng khó có khả năng xảy ra trường hợp dữ liệu bị rút trích vì có 2mn cách chọn K và 2 1 2 1 *(2 1)!*(2 1) r r mn r r mnC - - - - - cách chọn W. Giả sử cả một phần B đã bị giải mã, và có phương pháp để làm giảm khả năng chọn lựa W. Nếu người trung gian đã tìm được khối Fi đã bị thay đổi thành iF ′ khi nhúng các bit Bi, và khối Fj đã bị thay đổi thành jF ′ khi nhúng các bit Bj thì khả năng tiếp tục phát hiện các bit khác cao. Nếu Fi = Fj, thì sự khác nhau của iF′ và jF ′ sẽ phản ánh mối quan hệ của trọng số tại vị trí iF ′ khác Fi và jF ′ khác Fj. Giả sử Fi = iF′và chỉ có một vị trí (a,b) trên Fj bị thay đổi, thì [W]a,b phải là Bj-Bi hay Bi-Bj mod 2r . Các giá trị của W sẽ có thể bị phát hiện, và khả năng chọn lựa W sẽ giảm xuống 2mn. Nếu W đã bị phát hiện, thì khả năng tìm ra K rất dễ xảy ra. Nếu i i jF F F′= = và jF ′ chỉ khác Fj tại một vị trí (a,b), thì [K]a,b có thể tìm được. Nếu Bj-Bi = Kh oa C NT T - Ð H KH TN TP .H CM -52- [K]a,b ≠2r-1, thì [Fj⊗K]a,b=0, nghĩa là [K]a,b = [Fj]a,b. Ngược lại, Bj-Bi = -[K]a,b ≠2r-1, thì j a,b[F K] 1Å = , nghĩa là [K]a,b là phần bù của [Fj]a,b. Để phát hiện dữ liệu, người trung gian phải tốn chi phí cao, vì m × n lớn, K và W được bảo mật. ™ So sánh giữa hai phương pháp: • Ma trận F có các khối cùng kích thước: hình ảnh sau khi đã có dữ liệu được nhúng bằng phương pháp 2 lộn xộn hơn bằng phương pháp 1. Nhưng phương pháp 2 có thể chứa dữ liệu nhiều gấp 4 đến 10 lần hơn phương pháp 1. • Chất lượng hình ảnh như nhau: để hai ảnh sau khi đã nhúng dữ liệu có chất lượng bằng nhau, ta thay đổi kích thước các khối. Phương pháp 1 có số bit trung bình bị thay đổi là 0.5, kích thước là 16 16× , trong phưong pháp 2 ta lấy kích thước của khối lớn gấp 4 lần phương pháp 1 để số bit trung bình bị thay đổi cũng bằng 0.5, kích thước 32 32´ . Trong phương pháp 1, số bit dữ liệu tối đa được nhúng là 1, số dữ liệu được nhúng trong phương pháp 2 là 2log(32 1) 10ê ú+ =ê úë û bit trong mỗi khối 32 32× . Phương pháp 2 có tỉ số ẩn dữ liệu tối thiểu là 10 4 cao hơn phương pháp 1. • Số lượng dữ liệu được nhúng bằng nhau: để số lượng dữ liệu bằng nhau, kích thước các khối của hai phương pháp phải chênh lệch. Và vì phưong pháp 1 cần chọn ma trận điểm ảnh thích hợp nên số lượng ma trận thích hợp ít hơn trong phương pháp 2. Kh oa C NT T - Ð H KH TN TP .H CM -53- 3.5 Các kỹ thuật ẩn dữ liệu trên mô hình ba chiều: Trong khi vấn đề ẩn dữ liệu trong văn bản, ảnh tĩnh, âm thanh và video đã phát triển rộng rãi thì mô hình ba chiều vẫn còn là một đối tượng xa lạ. Ẩn dữ liệu trong mô hình ba chiều chỉ mới xuất hiện gần đây và một trong các phòng thí nghiệm đi tiên phong là phòng thí nghiệm của IBM Nhật Bản với đề tài nghiên cứu vào năm 1997 của Ryutarou Ohbuchi, Hirosi Masuda và Masaki Aono, kéo theo nhiều đề tài nghiên cứu của các phòng thí nghiệm khác. Có thể nói mô hình ba chiều trở thành một đối tượng tiềm năng trong ẩn dữ liệu vì hiện nay đồ họa ba chiều đang phát triển mạnh, đồ họa ba chiều được ứng dụng trong nhiều lĩnh vực như game, các hệ đồ họa hỗ trợ cho xây dựng, kiến trúc và trang trí nội thất. 3.5.1 Lý thuyết của ẩn dữ liệu trên mô hình ba chiều: Ẩn dữ liệu trên mô hình ba chiều có một số khác biệt so với ẩn dữ liệu trên ảnh tĩnh: (1) các đối tượng trong mô hình ba chiều không theo một dạng sắp xếp nào trong khi trên mỗi ảnh tĩnh, các pixel được sắp xếp theo vị trí của chúng trên ảnh, (2) sự biến đổi các giá trị định lượng (tọa độ đỉnh) trong mô hình ba chiều sẽ gây ra một sai số trong phép tính toán trên số chấm động, sai số này có thể làm cho quá trình rút trích dữ liệu đưa ra một kết quả sai. 3.5.1.1 Các yêu cầu của ẩn dữ liệu trong mô hình ba chiều: Cũng như ẩn dữ liệu trong văn bản, ảnh tĩnh, âm thanh và video, ẩn dữ liệu trong mô hình ba chiều cũng có các yêu cầu tương tự. Sau đây là các yêu cầu chung cho ẩn dữ liệu trong mô hình ba chiều, các yêu cầu này có tầm quan trọng ít hay nhiều tùy thuộc vào từng ứng dụng cụ thể. Kh oa C NT T - Ð H KH TN TP .H CM -54- Sự vô hình: việc nhúng dữ liệu vào mô hình ba chiều không được làm thay đổi quá nhiều mô hình, và không được ảnh hưởng đến mục đích sử dụng của mô hình. Tính bền vững: đây là yêu cầu quyết định đến sự thành công hay thất bại của các phương pháp ẩn dữ liệu. Việc làm cho dữ liệu nhúng không thể bị hủy diệt là điều không tưởng, việc này hoàn toàn khác với việc làm cho dữ liệu nhúng không thể rút trích ra được đối tượng chứa. Bất cứ một ai có kiến thức hoàn chỉnh về ẩn dữ liệu đều có khả năng xóa bỏ dữ liệu nhúng đi. Với kiến thức về thuật toán ẩn dữ liệu sử dụng trong một mô hình ba chiều, rất khó khăn trong việc xóa bỏ dữ liệu nhúng sao cho không làm ảnh hưởng đến mục đích sử dụng của mô hình và chi phí cho việc xóa không phải là ít. Sự chuyển đổi định dạng dữ liệu của mô hình là thường xuyên, sự chuyển đổi đó làm thay đổi thứ tự các đỉnh, các tam giác, các đối tượng hình học trong mô hình và làm phát sinh lỗi trong việc tính toán các số chấm động. Những biến đổi hình học trong mô hình thường là các phép quay, tịnh tiến, biến đổi tỉ lệ đồng nhất, các phép biến đổi affine. Các biến dạng cục bộ thường được phát sinh bởi phép phục hồi một phần trong mô hình. Các biến dạng tôpô được phát sinh bởi sự cắt bỏ một phần mô hình. Dữ liệu nhúng bị tấn công thường là do mục đích hủy bỏ hay làm biến dạng chúng. Một trong các phương tiện tấn công là thêm các giá trị ngẫu nhiên hay các giá trị có hệ thống vào tọa độ các đỉnh. Tính bền vững của dữ liệu phải chống chọi được một số các phép biến đổi, số lượng các phép biến đổi, các phương pháp mà tính bền vững có thể chống lại càng nhiều thì mô hình chứa và phương pháp ẩn dữ liệu tương ứng có giá trị càng cao. Kh oa C NT T - Ð H KH TN TP .H CM -55- Số lượng dữ liệu nhúng: số lượng dữ liệu nhúng phải đủ lớn để đáp ứng cho một ứng dụng cụ thể nào đó. 3.5.1.2 Mục đích của ẩn dữ liệu: Một mô hình ba chiều có thể chứa nhiều đối tượng dữ liệu khác nhau. Ví dụ như một tập tin VRML 2.0 bao gồm các đối tượng hình học là đa giác, đường thẳng, hay các đối tượng được xác định trước (hình trụ, hình cầu, hình nón,...). Các đối tượng đó có các thuộc tính riêng như độ bóng, màu của mặt hay màu của đỉnh, vectơ chuẩn của mặt hay của đỉnh, tọa độ kết cấu của đỉnh, ngoài ra còn có các liên kết đến một tài nguyên khác như là một tập tin âm thanh. Các mô hình không thuộc dạng VRML thì các đối tượng hình học được thể hiện bởi các mặt cong bao quanh như là các mảnh Bezier, bằng voxel và bằng nhiều phương tiện khác. Ryutarou Ohbuchi, Hirosi Masuda và Masaki Aono[7][8] cho rằng đối tượng hình học chính là đối tượng tốt nhất trong ẩn dữ liệu vì khả năng xóa bỏ dữ liệu nhúng trên các đối tượng hình học là không lớn. Trong luận văn này cũng xem đối tượng hình học là đối tượng chính cho ẩn dữ liệu. Ngoài ra còn có các đối tượng khác phù hợp cho ẩn dữ liệu như các tọa độ kết cấu và hình dạng của lưới đa giác trong mô hình nhưng việc xóa dữ liệu nhúng dễ dàng hơn khi mô hình sử dụng các đối tượng này để ẩn dữ liệu. 3.5.1.3 Các đối tượng nhúng trong mô hình ba chiều: Các giá trị hình học ví dụ như giá trị của các đỉnh có thể được thay đổi để nhúng vào chúng một giá trị dữ liệu, tuy nhiên thông tin được nhúng trực tiếp vào các giá trị này dễ bị tấn công bởi các phép biến đổi hình học thông thường. Vì thế cần có một sự cải tiến trong phương pháp ẩn dữ liệu sử dụng giá trị hình học để dữ liệu nhúng có tính bền vững cao để có thể chống lại một lớp các phép Kh oa C NT T - Ð H KH TN TP .H CM -56- biến đổi hình học. Sau đây là một bảng các đối tượng sử dụng trong ẩn dữ liệu được kế thừa từ tọa độ đỉnh, các đối tượng này có khả năng chống lại một lớp các phép biến đổi hình học. Bất biến với các phép biến đổi Đối tượng nhúng Tịnh tiến Quay Biến đổi tỉ lệ đồng nhất Biến đổi Affine Phép chiếu Tọa độ điểm Chiều dài của đoạn thẳng 9 9 Diện tích đa giác 9 9 Thể tích đa diện 9 9 Hai thuộc tính định nghĩa tập các tam giác đồng dạng 9 9 9 Tỉ số diện tích hai đa giác 9 9 9 Tỉ số chiều dài của hai đoạn thẳng 9 Tỉ số thể tích hai đa diện 9 Tỉ số chéo bốn điểm trên một đoạn thẳng 9 Bảng 4. Đối tượng nhúng và tính chất bất biến của chúng với các phép biến đổi Kh oa C NT T - Ð H KH TN TP .H CM -57- Phép biến đổi tỉ lệ đồng nhất là phép biến đổi cùng một tỉ lệ trên ba trục tọa độ Ox, Oy, Oz. Một đối tượng khác của ẩn dữ liệu là hình dạng trong mô hình. Dữ liệu nhúng sẽ được ẩn bằng cách thay đổi các sắp xếp trong mô hình. Đối tượng này được gọi là đối tượng topology. 3.5.1.4 Sự sắp xếp các đối tượng nhúng: Để nhúng được nhiều dữ liệu vào một mô hình, các đối tượng ẩn dữ liệu phải được sắp xếp theo một thứ tự nhất định. Sự sắp xếp cũng có tính chất quan trọng trong việc làm tăng tính bền vững của dữ liệu. Sắp xếp các đối tượng ẩn dữ liệu trong mô hình ba chiều được chia thành hai phương pháp: ™ Sắp xếp theo hình dạng: sắp xếp các đối tượng theo sự liền kề của chúng, ví dụ như hai tam giác kề. Phương pháp sắp xếp này được áp dụng cho cả hai loại đối tượng: đối tượng hình học và đối tượng topology. Đồng thời phương pháp này có khả năng chống lại các phép biến đổi hình học nhưng không thể chống lại các phép biến đổi topology. ™ Sắp xếp theo chất lượng: dựa vào các giá trị của các đối tượng (ví dụ như thể tích của đa diện) để sắp xếp các đối tượng theo thứ tự. Trong cả hai phương pháp sắp xếp, bao giờ cũng cần một điều kiện ban đầu, điều kiện ban đầu là đối tượng đầu tiên của một dãy một chiều có thứ tự của các đối tượng, điều kiện ban đầu này là đối tượng khởi tạo một dãy. Cả dãy sắp xếp và điều kiện khởi tạo phải có khả năng chống lại các sự suy biến trong mô hình. Phương pháp sắp xếp theo chất lượng được phân loại dựa theo vị trí của chúng: sắp xếp toàn cục, sắp xếp cục bộ và sắp xếp theo chỉ số. Kh oa C NT T - Ð H KH TN TP .H CM -58- ™ Sắp xếp toàn cục: sắp xếp tất cả các đối tượng theo một dãy cho một mục đích nhúng. ™ Sắp xếp cục bộ: sắp xếp các tập con phân biệt thành một dãy cho một mục đích nhúng, mỗi tập con chứa một số lượng các đối tượng hình học. ™ Sắp xếp theo chỉ số: tương tự như sắp xếp cục bộ nhưng kích thước của mỗi tập con rất nhỏ, các tập con được gọi là các MEP (Macro – Embedding – Primitive). Mỗi MEP liên kết với một dạng dữ liệu đặc biệt được gọi là chỉ số, chỉ số này là duy nhất cho mỗi MEP. Các chỉ số ánh xạ một tập các đối tượng ẩn dữ liệu vào một dãy có thứ tự. Hình 16 là các ví dụ về cách sắp xếp các đối tượng nhúng. Hình 16. Các phương pháp sắp xếp các đối tượng nhúng. (a) sắp xếp toàn cục, (b) sắp xếp cục bộ, (c) sắp xếp theo chỉ số Các phương pháp ẩn dữ liệu trong mô hình ba chiều được chia thành hai loại theo định dạng dữ liệu nhúng: Kh oa C NT T - Ð H KH TN TP .H CM -59- ™ Phương pháp nhúng chuỗi các ký hiệu: nhúng một dãy các ký hiệu có thứ tự, các ký hiệu đó có thể là ký tự. Nhúng chuỗi các ký hiệu sử dụng một dãy một chiều các đối tượng. ™ Phương pháp nhúng các mẫu: các mẫu được nhúng trực quan vào mô hình. Các mẫu có thể là hình dáng của ký tự. 3.5.2 Các kỹ thuật ẩn dữ liệu: Kỹ thuật ẩn dữ liệu trên mô hình ba chiều bao gồm các thuật giải dựa trên sự biến đổi đối tượng hình học (ví dụ như tọa độ đỉnh, tam giác) và thuật giải dựa trên sự biến đổi các đối tượng topology (hình dạng lưới đa giác). 3.5.2.1 Thuật giải dựa trên sự biến đổi các đối tượng hình học: Các thuật giải này đều sử dụng mô hình lưới tam giác. Biến đổi tọa độ đỉnh để nhúng dữ liệu. Hai thuật giải TSQ và TVR đều cho lượng dữ liệu nhúng không cao nhưng lại miễn dịch với một số phép biến đổi. 3.5.2.1.1 Thuật giải TSQ (Triangle Similarity Quadruple): Thuật giải này sử dụng các đặc tính đồng dạng của tam giác có tính bất biến về các phép tịnh tiến, quay và biến đổi tỉ lệ đồng nhất. Trong hình 17, tập các tam giác đồng dạng được định nghĩa bằng các đặc tính {b/a, h/c} hay {1, 2}. Khi thực thi các phép biến đổi trên các tam giác, các tỉ số đồng dạng không thay đổi, chính tính chất này làm cho dữ liệu nhúng chống lại được các phép biến đổi trên. Thuật giải này được gọi là thuật giải Bộ bốn tam giác đồng dạng TSQ (Triangle Similarity Quadruple). Thuật giải sử dụng các đối tượng nhúng là các cặp giá trị vô hướng. Các đối tượng nhúng được sắp xếp theo phương pháp chỉ số. Kh oa C NT T - Ð H KH TN TP .H CM -60- Hình 17. Các đặc trưng đồng dạng trong tam giác Nguyên lý thuật giải: TSQ chỉ áp dụng trên lưới tam giác, sử dụng phương pháp sắp xếp theo chỉ số, dùng bốn tam giác liền kề với nhau tạo thành một MEP. Một tam giác làm tam giác trung tâm, ba tam giác còn lại mỗi tam giác có một cạnh chung với tam giác trung tâm. Tam giác trung tâm gọi là Mark (M), tam giác này dùng để đánh dấu bộ bốn này có chứa dữ liệu nhúng. Tam giác có cạnh chung với cạnh đáy của Mark là tam giác Subscript (S), tam giác này chứa chỉ số xác định thứ tự của MEP trong dãy MEP. Hai tam giác còn lại Data1 (D1) và Data2 (D2) có cạnh chung với hai cạnh bên mới đúng là hai tam giác chứa dữ liệu cần nhúng. Thứ tự các tam giác D1 và D2 theo chiều ngược kim đồng hồ. Thuật giải này sử dụng phương pháp sắp xếp theo chỉ số và bộ bốn tam giác liền kề nhằm mục đích khi lưới tam giác bị thay đổi trong cách thức lưu trữ thì dữ liệu nhúng vẫn không bị thay đổi, nói chính xác hơn là thuật giải không lệ thuộc vào thứ tự lưu trữ các tam giác trong tập tin. Quá trình giải mã không cần mô hình lưới tam giác gốc, phương pháp này được gọi là blind, phương pháp ẩn dữ liệu có sử dụng đối tượng gốc trong quá trình giải mã được gọi là non-blind. Như đã nói trên, thuật giải này chống đươc các phép quay, tịnh tiến và biến đổi tỉ lệ đồng nhất, nhưng sẽ bị thất bại trước Kh oa C NT T - Ð H KH TN TP .H CM -61- thao tác thay đổi ngẫu nhiên giá trị tọa độ của các tam giác trong lưới và thao tác tạo lại lưới tam giác (là thao tác tạo một lưới tam giác khác, gồm các tam giác khác, nhưng hình dạng của mô hình vẫn giống như mô hình ban đầu), ngoài ra thuật giải còn thất bại với một lớp các phép biến đổi hình học thông thường. Thuật giải nhúng một thông điệp vào mô hình lưới tam giác theo các bước sau: Bước 1: Duyệt trên lưới tam giác ban đầu, tìm dãy các MEP. Không được sử dụng lại các đỉnh đã có trong MEP khác và các tam giác có tỉ số đồng dạng quá nhỏ hay quá lớn, điều này sẽ làm giảm đi sự biến đổi trên lưới tam giác sau khi nhúng. Bước 2: Nhúng một giá trị đánh dấu vào tam giác M bằng cách thay đổi giá trị trong cặp tỉ số {e14 /e24, h4 /e12} và tọa độ ba đỉnh v1,v2,v4 bị thay đổi theo một lượng giá trị tuỳ thuộc vào dữ liệu nhúng. MEP được mô tả như hình 18. Bước 3: Nhúng chỉ số và hai ký hiệu trong thông điệp vào ba tam giác còn lại S, D1 và D2 nhưng chỉ được thay đổi giá trị tọa độ ba đỉnh v0, v3, v5. Chỉ số được nhúng vào cặp tỉ số {e02/e01, h0/e12}, hai ký hiệu được nhúng vào {e13/e34, h3/e14} và {e45/e25, h5/e24} tương ứng. Bước 4: Lặp lại bước 1 đến bước 3 cho đến khi thông điệp đã được nhúng hết. Để gia tăng tính bền vững của dữ liệu nhúng, quá trình nhúng thông điệp được lặp lại nhiều lần, như thế một thông điệp sẽ được nhúng nhiều bản, khi mô hình bị xén mất một phần lưới tam giác thì bản sao thông điệp vẫn có khả năng còn tồn tại trong mô hình. Lượng thay đổi trong các cặp tỉ số phải không lớn để sự thay đổi trên mô hình không thể nhận biết bằng mắt được nhưng không quá nhỏ để không bị mất đi khi bị nhiễu hay bị mất đi bởi các lỗi sai số trong các thao tác của phép biến Kh oa C NT T - Ð H KH TN TP .H CM -62- đổi. Lượng thay đổi này phải được giới hạn tùy theo ưu tiên về tính bền vững hay tính vô hình của dữ liệu nhúng của từng ứng dụng riêng biệt. Hình 18. Cấu trúc một MEP Sau đây là các bước trong quá trình rút trích dữ liệu nhúng từ mô hình lưới tam giác: Bước 1: Duyệt trên lưới tam giác, xác định các tam giác có dấu hiệu Mark, từ đó xác định các MEP tương ứng. Bước 2: Rút trích giá trị chỉ số và hai ký hiệu trong từng MEP. Bước 3: Lặp lại bước 2 cho đến khi tất cả các MEP đã được rút trích dữ liệu. Bước 4: Sắp xếp các ký hiệu theo chỉ số. Hình 19 là một ví dụ nhúng một thông điệp “data hiding” vào lưới tam giác. Các MEP có vị trí ngẫu nhiên. Kh oa C NT T - Ð H KH TN TP .H CM -63- Hình 19. Lưới tam giác và các MEP với dữ liệu nhúng là "data hiding" Đánh giá về thuật giải: thuật giải có khả năng chống lại các phép quay, tịnh tiến và biến đổi tỉ lệ đồng nhất, quá trình giải mã không cần mô hình gốc. Ngoài ra, thuật giải không phụ thuộc vào thứ tự lưu trữ các tam giác trong tập tin. Tuy nhiên việc tính toán trên số thực sẽ gây ra nhiều sai số có thể dẫn đến việc suy thoái của dữ liệu nhúng. Số lượng dữ liệu nhúng không nhiều lắm, chỉ khoảng 0.15 – 0.18 byte/ tam giác. 3.5.2.1.2 Thuật giải TVR (Tetrahedral Volumn Ratio): TVR sử dụng đối tượng nhúng là các cặp tỉ số thể tích của hai tứ diện. Tỉ số này bất biến với các phép biến đổi affine nhưng thất bại với các phép biến đổi topology như là tạo lại lưới tam giác, thay đổi ngẫu nhiên giá trị tọa độ của đỉnh Kh oa C NT T - Ð H KH TN TP .H CM -64- và các phép biến đổi hình học thông thường. Thuật giải này được gọi là thuật giải Tỉ số thể tích tứ diện TVR (Tetrahedral Volumn Ratio), sử dụng phương pháp sắp xếp toàn cục hay sắp xếp cục bộ. Thuật giải cũng thao tác trên lưới tam giác. Quá trình giải mã cũng không cần có lưới tam giác gốc, vì thế TVR là thuật giải blind. Nguyên lý thuật giải: yếu tố chính trong thuật giải là thành lập một dãy sắp xếp cục bộ các đối tượng nhúng và tiến hành nhúng dữ liệu vào các đối tượng nhúng. Sau đây là các bước của thuật giải: Bước 1: Từ một điều kiện ban đầu, duyệt trên lưới tam giác tạo một cây mở rộng các đỉnh Vt. Từ cây mở rộng các đỉnh Vt tạo dãy các tam giác. Cây mở rộng được thành lập như sau: điều kiện ban đầu là một cạnh khởi tạo trên lưới tam giác Tris, chiều của cạnh (đỉnh ngọn, đỉnh gốc) và chiều duyệt (theo chiều kim đồng hồ hay ngược chiều kim đồng hồ). Từ cạnh và chiều duyệt đó bắt đầu duyệt các đỉnh trong lưới: chọn một đỉnh liền kề và là đỉnh đầu tiên theo chiều duyệt thêm vào cây mở rộng, quá trình cứ tiếp tục cho đến khi đã duyệt hết các đỉnh. Sau khi đã có cây mở rộng, tạo một dãy các cạnh Tbe (Triangle Bounding Edge), ban đầu Tbe và dãy Tris rỗng, bắt đầu duyệt từ gốc cây theo chiều sâu, ở mỗi đỉnh xét các cạnh nối với đỉnh ấy nếu chưa có trong Tbe thì thêm cạnh đó vào Tbe. Nếu tồn tại lần đầu tiên trong Tbe ba cạnh của một tam giác thì thêm tam giác đó vào Tris. Cạnh ban đầu được chọn là cạnh xác định tứ diện có thể tích lớn nhất trong mô hình lưới tam giác. Tứ diện có thể tích lớn nhất này không được sử dụng trong các bước tiếp theo để bảo toàn tọa độ các đỉnh. Một cạnh xác Kh oa C NT T - Ð H KH TN TP .H CM -65- định một tứ diện được mô tả như hình 20, mỗi cạnh xác định một tứ diện chính là bốn đỉnh của hai tam giác có chung cạnh đó: Hình 20. Cạnh xác định tứ diện chính là bốn đỉnh của hai tam giác có cạnh này là cạnh chung Bước 2: Tạo một dãy các tứ diện Tets từ dãy các tam giác Tris: tính một đỉnh chung cho tất cả các tam giác trong Tris bằng cách tính trọng tâm của các đỉnh của một số tam giác trong Tris, các tam giác đã sử dụng để tính trọng tâm sẽ bị loại ra khỏi Tris và tọa độ đỉnh của các tam giác đó không bị thay đổi trong quá trình nhúng. Đỉnh chung này được xem là đỉnh thứ tư của các tứ diện có tam giác đáy là tam giác trong Tris. Bước 3: Chuyển dãy các tứ diện Tets thành dãy các tỉ số thể tích tứ diện Vrs tương ứng: chọn một thể tích tứ diện làm mẫu số, các thể tích tứ diện còn lại làm tử số, tứ diện có thể tích là mẫu số bị loại ra khỏi Tets và các tọa độ đỉnh của nó không bị thay đổi trong quá trình nhúng. Quá trình tạo dãy tỉ số thể tích được mô tả bằng hình 21: Kh oa C NT T - Ð H KH TN TP .H CM -66- Hình 21. Quá trình tạo chuỗi tỉ số thể tích Bước 4: Nhúng một ký hiệu vào mỗi tỉ số bằng cách thay đổi thể tích tử số. Các đỉnh bị thay đổi tọa độ phải chưa được sử dụng để nhúng một ký hiệu trong giai Kh oa C NT T - Ð H KH TN TP .H CM -67- đoạn trước. Ngoài thông điệp cần nhúng còn có thêm một dãy các ký hiệu nhận biết, dãy các ký hiệu nhận biết được nhúng đầu tiên, dãy này hữu dụng trong quá trình rút trích dữ liệu. Quá trình rút trích dữ liệu sử dụng phương pháp thử và sai. Mỗi cạnh trong lưới đa giác được xem là cạnh khởi tạo, được thao tác hai lần theo hai chiều duyệt: cùng chiều kim đồng hồ và ngược chiều kim đồng hồ. Ban đầu chọn một chiều là chiều duyệt. Từ cạnh này tạo cây mở rộng Vt, dãy tam giác Tris, dãy tứ diện Tets và dãy tỉ số thể tích, sau đó rút trích dữ liệu từ dãy tỉ số thể tích. Nếu các ký hiệu ban đầu đúng với dãy các ký hiệu nhận biết thì cạnh này đúng là cạnh khởi tạo và chiều duyệt này chính xác, quá trình rút trích dữ liệu sẽ tiếp tục cho đến khi nhận được thông điệp. Nếu các ký hiệu không đúng với các ký hiệu nhận biết thì quá trình dừng và chọn chiều kia làm chiều duyệt. Nếu cả hai chiều đều không đúng thì chuyển sang cạnh kế tiếp và tiếp tục cho đến khi rút trích được chính xác dãy ký hiệu nhận biết và thông điệp. Đánh giá về thuật giải: thuật giải có khả năng chống lại các phép biến đổi affine, quá trình giải mã không cần lưới tam giác gốc. Cũng như TSQ, thuật giải không phụ thuộc vào thứ tự lưu trữ các tam giác trong tập tin và việc tính toán trên số thực sẽ gây ra nhiều sai số có thể dẫn đến việc suy thoái của dữ liệu nhúng. Vì TVR sử dụng phương pháp thử và sai trên tất cả các cạnh trong lưới tam giác, điều này tốn không ít thời gian nhất là trong trường hợp lưới tam giác lớn, số lượng tam giác lên đến vài chục ngàn. Số lượng dữ liệu nhúng ít, khoảng 0.05 – 0.2 byte/ tam giác. 3.5.2.1.3 Cơ sở toán học của hai thuật giải TSQ và TVR: Kh oa C NT T - Ð H KH TN TP .H CM -68- Hai thuật giải trên dựa vào cơ sở toán học về các phép biến đổi đồng dạng trên tam giác và trên tứ diện[11]. Các phép quay, tịnh tiến và biến đổi tỉ lệ đồng nhất đều là các phép biến đổi affine. Ta có tính chất về phép biến đổi affine và ánh xạ affine như sau: ™ Hình tam giác là một khái niệm affine. ™ Ánh xạ affine biến một tam giác thành một tam giác, một tứ diện thành một tứ diện. ™ Các phép biến đổi: quay, tịnh tiến và biến đổi tỉ lệ đồng nhất là các phép biến đổi đồng dạng. Phép biến đổi đồng dạng biến một tam giác thành một tam giác đồng dạng với nó. Và các cặp tỉ số {cạnh đáy/đường cao, cạnh bên/cạnh bên} là các đặc trưng của lớp các tam giác đồng dạng. 3.5.2.2 Thuật giải dựa trên sự thay đổi hình dạng lưới tam giác: 3.5.2.2.1 Thuật giải TSPS (Triangle Strip Peeling Symbol sequence): Thuật giải TSPS là thuật giải ẩn dữ liệu dựa trên sự thay đổi các đối tượng nhúng là hình dáng lưới tam giác. Nguyên lý thuật giải: thuật giải dựa trên sự liền kề trong chuỗi các tam giác, mỗi cạnh kề mã hóa một bit dữ liệu. Các đối tượng nhúng được sắp xếp theo dãy một chiều. Sau khi đã nhúng dữ liệu, chuỗi các tam giác có dữ liệu nhúng được tách ra khỏi lưới tam giác. Các đối tượng nhúng là các đối tượng topology và cách sắp xếp cũng theo cách sắp xếp topology nên thuật giải này tránh được các biến đổi hình học. Ngoài ra bằng cách nhúng nhiều lần bản sao của dữ liệu nhúng, thuật giải còn có thể chống lại phép cắt một phần lưới tam giác. Tuy nhiên, dữ liệu nhúng sẽ bị hủy hoàn toàn khi lưới tam giác bị thao tác bởi các phép biến đổi topology. Kh oa C NT T - Ð H KH TN TP .H CM -69- Thuật giải có đầu vào là lưới tam giác, dãy các bit dữ liệu và một hướng duyệt (cùng chiều kim đồng hồ hay ngược chiều kim đồng hồ) ví dụ như hướng cùng chiều kim đồng hồ là xác định bit 1, hướng ngược chiều kim đồng hồ xác định bit 0. Sau đây là các bước của thuật giải: Bước 1: Từ lưới tam giác M, chọn một cạnh ban đầu e, mở rộng một chuỗi tam giác S trên M bằng cách sử dụng dãy các bit dữ liệu để định hướng chọn tam giác kế tiếp. Cạnh e chính là điều kiện khởi tạo. Nhận thấy rằng tam giác cuối cùng trong chuỗi tam giác luôn có hai cạnh tự do (hai cạnh không kề với các tam giác còn lại trong chuỗi tam giác). Tam giác kế tiếp là tam giác có cạnh kề với một trong hai cạnh sẽ được xác định dựa vào hướng duyệt và giá trị kế tiếp trong dãy bit dữ liệu. Bước 2: Tách rời chuỗi tam giác S khỏi M bằng cách tách tất cả các cạnh và các đỉnh trên đường biên của S, chỉ để lại duy nhất cạnh ban đầu e. Chuỗi tam giác S chỉ còn liên kết với phần còn lại của lưới tam giác M chỉ duy nhất cạnh e. Kh oa C NT T - Ð H KH TN TP .H CM -70- Hình 22. Mô tả các bước của thuật giải TSPS Kh oa C NT T - Ð H KH TN TP .H CM -71- Ví dụ: nhúng chuỗi các bit “10101101011” vào chuỗi 12 tam giác. Hình 23. Chuỗi tam giác S tương