Báo cáo Nghiên cứu ứng dụng thủy ký bảo vệ bản quyền tài liệu số

TRƯỜNG …………………. KHOA………………………. -----[\ [\----- Báo cáo tốt nghiệp Đề tài: Nghiên cứu ứng dụng thủy ký bảo vệ bản quyền tài liệu số TÓM TẮT NỘI DUNG: Khóa luận trình bày về những kết quả đạt đƣợc trong nghiên cứu ứng dụng thủy vân số vào việc bảo vệ bản quyền tài liệu số hóa. Khóa luận đƣợc trình bày thành bốn chƣơng, với nội dung nhƣ sau: Chƣơng 1: tóm tắt các kiến thức cơ bản về bảo vệ an toàn dữ liệu, bảo mật thông tin cũng nhƣ tổng quan về thủy vân số trên các tài liệu số. Chƣơng 2: trình bày về thủy vân số trên ảnh số, cùng các thuật toán và các phép biến đổi, là nội dung quan trọng và có nhiều ứng dụng thực tiễn hiện nay. Chƣơng 2 có trình bày về các phép biến đổi và xử lý ảnh, rất quan trọng trong việc thực hiện thủy vân số đối với ảnh. Chƣơng 3: trình bày về thủy vân số trên các tài liệu đa phƣơng tiện khác, nhƣ trên các file audio hoặc video. Chƣơng 3 có trình bày một thuật toán thủy vân số trên audio sử dụng công nghệ trải phổ. Chƣơng 4: chƣơng trình thử nghiệm thuật toán thủy vân số trên ảnh. Cuối cùng là kết luận và hƣớng nghiên cứu tiếp theo. MỤC LỤC: MỞ ĐẨU ............................................................................................................ 1 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN ............................................................. 3 1.1. KHÁI NIỆM TRONG TOÁN HỌC.......................................................... 3 1.1.1.Khái niệm trong số học. ...................................................................... 3 1.1.1.1. Tính chia hết, quan hệ đồng dƣ và số nguyên tố. ......................... 3 1.1.1.2. Không gian Zn và cấu trúc nhóm. ................................................ 4 1.1.1.3. Dãy số giả ngẫu nhiên. ................................................................ 5 1.1.2. Khái niệm độ phức tạp thuật toán. ...................................................... 5 1.2. KHÁI NIỆM MÃ HÓA. ........................................................................... 7 1.2.1. Hệ mã hóa. ......................................................................................... 7 1.2.2. Mã hóa khóa đối xứng. ...................................................................... 8 1.2.3. Mã hóa khóa công khai. ................................................................... 12 1.3. KHÁI NIỆM CHỮ KÝ SỐ. .................................................................... 15 1.3.1. Sơ đồ ký số: ..................................................................................... 15 1.3.2. Sơ đồ ký số RSA. ............................................................................. 16 1.4. MỘT SỐ CÔNG CỤ BẢO VỆ BẢN QUYỀN KHÁC. ........................... 17 1.4.1. Hàm băm. ........................................................................................ 17 1.4.2. Truy vết. .......................................................................................... 18 1.5. THỦY VÂN SỐ. .................................................................................... 19 1.5.1. Khái niệm thủy vân số. .................................................................... 19 1.5.1.1. Lịch sử thủy vân số. .................................................................. 19 1.5.1.2. Quá trình nghiên cứu thủy vân số. ............................................. 21 1.5.1.3. Một số hệ thống thủy vân. ......................................................... 24 1.5.2. Các ứng dụng của thủy vân số. ......................................................... 25 1.5.3. Các đặc tính của thủy vân. ............................................................... 26 1.5.4. Phân loại thủy vân............................................................................ 27 1.5.5. Quy trình thực hiện thủy vân. ........................................................... 28 Chƣơng 2. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN ẢNH ............ 29 2.1. CÁC ĐỊNH DẠNG ẢNH. ...................................................................... 29 2.1.1. Định dạng ảnh BMP......................................................................... 29 2.1.2. Định dạng ảnh PNG. ........................................................................ 31 2.1.3. Định dạng ảnh GIF. ......................................................................... 33 2.1.4. Định dạng ảnh JPEG. ....................................................................... 37 2.1.4.1. Kỹ thuật nén ảnh JPEG. ............................................................ 37 2.1.4.2. Mã hoá biến đổi DCT. ............................................................... 39 2.1.5. Định dạng ảnh JPEG2000. ............................................................... 47 2.1.6. Định dạng ảnh PGM. ....................................................................... 49 2.2. CÁC PHÉP BIẾN ĐỔI ẢNH. ................................................................. 50 2.2.1. Các toán tử không gian. .................................................................. 50 2.2.1.1. Toán tử tuyến tính. .................................................................... 50 2.2.1.2. Toán tử nhân chập. .................................................................... 51 2.2.1.3. Các kỹ thuật lọc số. ................................................................... 52 2.2.2. Các toán tử tần số. ............................................................................ 57 2.2.2.1. Phép biến đổi Fourier. ............................................................... 57 2.2.2.2. Phép biến đổi Cosine rời rạc. ..................................................... 59 2.2.2.3. Phép biến đổi sóng con rời rạc. ................................................. 60 2.3. CÁC THUẬT TOÁN THỦY VÂN TRÊN ẢNH. ................................... 61 2.3.1. Thuật toán giấu thủy vân vào các bit có trọng số thấp. ..................... 61 2.3.2. Thuật toán thủy vân ghép nối. .......................................................... 63 2.3.3. Thuật toán thủy vân ảnh trên miền DCT. ......................................... 64 2.3.4. Thuật toán thủy vân ảnh trên miền DWT. ........................................ 66 2.3.5. Thuật toán thủy vân sử dụng biến đổi Karhunen – Loeve. ................ 68 2.3.6. Thủy vân dễ vỡ. ............................................................................... 70 2.3.7. Thủy vân giòn. ................................................................................. 72 2.4. TẤN CÔNG THỦY VÂN. ..................................................................... 73 Chƣơng 3. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN CÁC TÀI LIỆU SỐ KHÁC ........................................................................................................ 75 3.1. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN AUDIO. .............. 75 3.1.1. Giới thiệu audio số. .......................................................................... 75 3.1.2. Tổng quan về thủy vân trên audio. ................................................... 76 3.1.2.1. Thủy vân dựa trên miền dữ liệu. ................................................ 76 3.1.2.2. Thủy vân dựa trên miền tần số: ................................................. 77 3.1.2.3. Thủy vân dựa trên miền thời gian thực. ..................................... 78 3.1.3. Một thuật toán thủy vân trên audio sử dụng kỹ thuật trải phổ. ......... 79 3.1.3.1. Mô hình giả lập hệ thính giác. ................................................... 79 3.1.3.2. Thuật toán thủy vân. .................................................................. 81 3.2. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN VIDEO. .............. 84 3.3. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN PHẦN MỀM. ..... 85 CHƢƠNG IV: CHƢƠNG TRÌNH THỬ NGHIỆM. .......................................... 87 4.1. THỦY VÂN HIỆN. ................................................................................ 87 4.1.1. Microsoft Word 2007. ...................................................................... 87 4.1.2. Fast Watermark. ............................................................................... 90 4.1.3. Watermark Master. .......................................................................... 91 4.2. THỦY VÂN ẨN. .................................................................................... 92 4.2.1. Sử dụng chƣơng trình. ...................................................................... 92 4.2.2. Một số kết quả thử nghiệm. .............................................................. 95 4.2.3. Thử nghiệm các phép tấn công. ........................................................ 99 4.2.1.1. Phép co hình. ........................................................................... 99 4.2.1.2. Nén ảnh JPEG. ....................................................................... 101 4.2.1.3. Phép xoay ảnh. ........................................................................ 101 4.2.1.4. Phép cắt ảnh. ........................................................................... 102 4.2.1.5. Thực hiện thủy vân lên một ảnh đã đƣợc thủy vân. ................. 103 KẾT LUẬN ..................................................................................................... 104 PHỤ LỤC ....................................................................................................... 105 TÀI LIỆU THAM KHẢO ............................................................................... 107 DANH MỤC CÁC HÌNH VẼ TRONG KHÓA LUẬN: Hình 1. Sơ đồ hệ mã hóa DES ........................................................................... 10 Hình 2. Thủy vân trên đồng dollar của Mỹ ........................................................ 19 Hình 3. Số lƣợng các bài báo nghiên cứu về thủy vân số trong cơ sở dữ liệu của IEEE .......................................................................................................................... 23 Hình 4. Một số phƣơng pháp phân loại thủy vân tiêu biểu ................................. 27 Hình 5. Quy trình thực hiện thủy vân ................................................................ 28 Hình6. Sơ đồ khối một hệ thống nén ảnh điển hình ........................................... 38 Hình 7. Sơ đồ mã hóa và giải mã dùng biến đổi DCT ........................................ 39 Hình 8. Các bƣớc của quá trình mã hóa biến đổi DCT đối với một khối ............ 40 Hình 9. Ma trận lƣợng tử ................................................................................... 41 Hình 10. Cây mã Huffman. ............................................................................... 44 Hình 11. Bảng zigzag của các thành phần ảnh JPEG ......................................... 46 Hình 12. Lấy tổ hợp các điểm ảnh lân cận. ........................................................ 53 Hình 12. Biến đổi Fourier cho một tín hiệu........................................................ 57 Hình 13. Mô hình nhúng thủy vân của Cox. ...................................................... 64 Hình 14. Biến đổi DWT ba mức ........................................................................ 66 Hình 15. Thủy vân tín hiệu bằng điều biến cơ số thời gian. ............................... 78 Hình 16. Sự sai khác thời gian của tín hiệu gốc và tín hiệu đã nhúng thủy vân .. 78 Hình 17. Mô hình giả lập hệ thính giác. ............................................................. 79 Hình 18. Thành phần tín hiệu sau khi thủy vân. ................................................. 81 Hình 19. Sơ đồ tạo thủy vân .............................................................................. 81 Hình 20. Sơ đồ nhúng thủy vân. ........................................................................ 82 Hình 21. Sơ đồ tách thủy vân............................................................................. 83 Hình 22. Thủy vân hiện trên góc trái của hình ảnh truyền hình .......................... 84 Hình 23. Chọn chức năng Watermark trong Word 2007 .................................... 88 Hình 24. Cửa sổ Custom watermark. ................................................................. 89 Hình 26. Ví dụ chèn thủy vân bằng Microsoft Word 2007. ................................ 89 Hình 27. Giao diện phần mềm Fast Watermark. ................................................ 90 Hình 28. Giao diện phần mềm Watermark Master ............................................. 91 Hình 27. Các tham số của câu lệnh gen_cox_sig ............................................... 93 Hình 28. Ảnh lena ............................................................................................. 95 Hình 29. Ảnh sau khi đƣợc nhúng thủy vân bằng thuật toán Cox với tham số tạo thủy vân mặc định. ..................................................................................................... 96 Hình 30. So sánh ảnh trƣớc và sau khi nhúng thủy vân ...................................... 97 Hình 31. Ảnh sau khi đƣợc nhúng thủy vân bằng thuật toán của Corvi với tham số tạo thủy vân mặc định ........................................................................................... 98 Hình 32. Ảnh sau khi đã đƣợc nhúng thủy vân và thay đổi kích thƣớc. .............. 99 Hình 33. Ảnh sau khi phục hồi lại kích thƣớc gốc. .......................................... 100 Hình 34. Ảnh sau khi nén JPEG với chất lƣợng 10%. ...................................... 101 Hình 35. Ảnh nhúng thủy vân và bị cắt. ........................................................... 102 Hình 36. Ảnh sau khi đƣợc nhúng thêm thủy vân 2 lần liên tiếp. ..................... 103 DANH MỤC CÁC BẢNG BIỂU TRONG KHÓA LUẬN: Bảng 1. Cấu trúc định dạng ảnh BMP ................................................................ 29 Bảng 2. Định dạng tổng quát ảnh GIF ............................................................... 33 Bảng 3. Cấu trúc khối bản đồ màu tổng thể ảnh GIF ......................................... 34 Bảng 4. Cấu trúc bộ mô tả ảnh GIF ................................................................... 35 Bảng 5. Bảng tần suất ký tự. .............................................................................. 43 Bảng 6. Bảng từ mã gán cho các ký tự bởi mã hoá Huffman. ............................ 45 Bảng 7. So sánh một số định dạng ảnh nén. ....................................................... 48 BẢNG VIẾT TẮT THUẬT NGỮ: Từ viết tắt Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt DFT Discrete Fourier Transform Biến đổi Fourier rời rạc DCT Discrete Cosine Transform Biến đổi Cosine rời rạc DWT Discrete Wavelet Transform Biến đổi sóng con rời rạc IDFT Inverse Discrete Fourier Transform Biến đổi Fourier rời rạc ngƣợc PCA Pricipal Component Analysis Phân tích các thành phần quan trọng LSB Least Significant Bit Bit ít quan trọng nhất LỜI CẢM ƠN Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành và sâu sắc nhất tới PGS.TS Trịnh Nhật Tiến, ngƣời thầy đã trực tiếp hƣớng dẫn tôi hoàn thành khóa luận này. Tôi cũng xin cảm ơn các thầy, cô giáo của Khoa Công nghệ Thông tin, Trƣờng Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tận tình dạy dỗ, chỉ bảo tôi trong suốt những năm học ở trƣờng. Tôi xin gửi lời cảm ơn tới gia đình, chính là nguồn lực động viên tôi phấn đấu trong học tập và cuộc sống. Tôi cũng xin gửi lời cảm ơn tới các bạn sinh viên trong lớp K50CA, cũng nhƣ lớp K50 Các Hệ thống thông tin, Khoa Công nghệ Thông tin, Trƣờng Đại học Công nghệ, Đại học Quốc gia Hà Nội đã cho tôi một môi trƣờng rất tốt để học tập và nghiên cứu. Cuối cùng, tôi xin gửi lời cảm ơn tới PGS.TS Hà Quang Thụy, cũng nhƣ các anh chị trong phòng thí nghiệm SISLab, Trƣờng Đại học Công nghệ, đã dạy tôi rất nhiều điều quý giá về nghiên cứu khoa học. Hà Nội, ngày 10 tháng 5 năm 2009. 1 MỞ ĐẨU Bƣớc vào thế kỷ XXI, loài ngƣời đã chứng kiến một cuộc bùng nổ thật sự, sau cuộc cách mạng phát minh ra máy tính điện tử, đó là Internet. Chỉ trong vòng có vài năm ngắn ngủi, Internet đã nhanh chóng len lỏi vào từng ngóc ngách của đời sống, và càng ngày càng đóng những vai trò quan trọng trong cuộc sống của con ngƣời. Từ khi loài ngƣời bƣớc ra khỏi thời kỳ công xã nguyên thủy, và chủ nghĩa cá nhân xuất hiện, thì nhu cầu bảo vệ dấu ấn cá nhân trong cộng đồng ngày càng trở nên bức bách. Các nghệ sỹ đua nhau sáng tạo ra những trƣờng phái mới, chỉ với mục đích làm cho tác phẩm của mình không bị lẫn lộn với những tác phẩm của ngƣời khác. Những ngƣời giàu có sẵn sàng bỏ ra nhiều triệu đô la, chỉ để sở hữu một chiếc điện thoại di động không có gì độc đáo về mặt tính năng nhƣng là duy nhất trên thế giới. Bƣớc vào thời kỳ kinh tế tri thức, khi tri thức ngày càng trở nên đắt giá, đồng thời với đó, các tài liệu đƣợc lƣu ở dạng số hóa ngày càng nhiều và phổ biến, thì vấn đề bảo vệ bản quyền cho tri thức của con ngƣời ngày càng trở nên quan trọng, bởi những đặc trƣng sau của tài liệu số: Dễ dàng sao chép: nhờ sự phát triển của máy vi tính, các tài liệu số hóa có thể đƣợc sao chép một cách đơn giản và nhanh chóng. Chỉ cần một vài thao tác đơn giản, nhƣ click chuột, một cuốn tiểu thuyết dày hàng nghìn trang, hay một tác phẩm trị giá nhiều triệu đô la của danh họa Picasso có thể đƣợc sao chép chỉ trong vài giây. Điều quan trọng hơn nữa là khi sao chép tài liệu số thì chất lƣợng bản sao chép đƣợc giữ nguyên so với bản gốc. Dễ dàng phát tán: những năm gần đây, Việt Nam chứng kiến cuộc chay đua về nâng cấp hạ tầng đƣờng truyền Internet giữa các nhà cung cấp dịch vụ. Điều này giúp cho khách hàng có đƣợc dịch vụ tốt hơn, nhƣng đồng nghĩa với đó là việc phát tán thông tin cũng nhƣ tài liệu qua mạng Internet càng trở nên dễ dàng hơn bao giờ hết. Ngày nay, chỉ sau vài phút tìm kiếm trên mạng, ngƣời sử dụng có thể dễ dàng tìm và tải về những bộ phim mới nhất còn chƣa đƣợc trình chiếu ở rạp. Cùng với đó, một ngƣời sử dụng bình thƣờng có thể trở thành một nguồn phát tán tài liệu cũng rất dễ dàng, thông qua các tin nhắn tức thời (IM – Instant Message), email hay các dịch vụ chia sẻ file trực tuyến (online file sharing service). Điều này có thể gây nên một hiệu ứng lan truyền nhƣ hiệu ứng virus, khiến tài liệu đƣợc phát tán nhanh và rộng khắp. Ví dụ, đoạn clip về Susan Boyle đƣợc đƣa lên mạng vào tháng 4.2009 vừa qua đã đạt đƣợc hơn 200 triệu ngƣời xem chỉ trong có 2 tuần. 2 Dễ dàng lƣu trữ: dung lƣợng ổ cứng ngày càng lớn, giá thành các thiết bị lƣu trữ ngày càng rẻ đã khiến cho việc lƣu trữ các tài liệu số hóa trở nên đơn giản hơn bao giờ hết. Một chiếc đĩa CD mà giờ đây ngày càng trở nên lỗi thời, đã có thể chứa hàng trăm cuốn sách điện tử. Một thiết bị nghe nhạc MP3 giá vài trăm nghìn đồng có thể lƣu đƣợc hàng vạn bài hát. Những ổ cứng với dung lƣợng lên tới hàng trăm GB, thậm chí hàng TB khiến cho một máy tính cá nhân dễ dàng biến thành một rạp chiếu phim. Tất cả những điều đó đã khiến cho việc lƣu trữ các tài liệu số hóa trở nên dễ dàng hơn bao giờ hết. Ở Việt Nam, tình hình vi phạm bản quyền vẫn đang diễn biến rất nghiêm trọng, mặc dù đã có sự cố gắng của nhiều cơ quan chức năng, cũng nhƣ của cộng đồng. Tình trạng sử dụng phần mềm không có bản quyền, download những file video lậu trên các trang web chia sẻ file, tìm nghe những album mới nhất trên những diễn đàn mà không muốn mua đĩa, v.v… là những hiện tƣợng hết sức phổ biến. Để đảm bảo cho nhu cầu giữ bí mật thông tin liên lạc cũng nhƣ đảm bảo an toàn dữ liệu, từ lâu con ngƣời đã phát minh ra một công cụ hết sức hiệu quả, đó là mã hóa. Mã hóa là một công cụ mạnh, và có lịch sử lâu đời, đã có nhiều kết quả nghiên cứu thành công và có ứng dụng rất lớn trong việc đảm bảo an toàn thông tin liên lạc. Tuy nhiên, mã hóa gặp phải một vấn đề rất lớn, đó là bản thân công cụ mã hóa không gắn liền với tài liệu đƣợc bảo vệ, mà chỉ nhƣ một dạng vỏ bọc (cover) của tài liệu mà thôi. Do đó, mã hóa không thể đƣợc sử dụng nhƣ là một công cụ an toàn để bảo vệ bản quyền tài liệu số khi phát hành trên mạng, vì sau khi kẻ gian đã giải mã đƣợc tài liệu, thì có toàn quyền đối với tài liệu đó. Thủy vân (watermarking) là một ứng dụng đã có từ lâu đời để bảo vệ bản quyền cho các cuốn sách. Tuy nhiên, thủy vân số (digital watermarking) lại là một lĩnh vực mới, đang nhận đƣợc nhiều sự quan tâm cũng nhƣ nghiên cứu của chuyên gia trên thế giới. Sử dụng thủy vân số có thể thay đổi và tác động vào chất lƣợng của tài liệu số nhƣ ý muốn, đồng thời với đó là thủy vân số có thể gắn liền với tài liệu, đảm bảo tài liệu đƣợc bảo vệ bản quyền cho tới khi bị hủy hoại. Trong nội dung khóa luận này, tôi xin tập trung trình bày những kết quả nghiên cứu đã đạt đƣợc trong việc ứng dụng thủy vân số để bảo vệ bản quyền tài liệu điện tử, đặc biệt là ảnh số. Ngoài ra khóa luận cũng trình bày những ứng dụng của thủy vân số trong việc bảo vệ bản quyền tài liệu một số file đa phƣơng tiện khác, nhƣ audio hay video, cũng là những vấn đề đang rất đƣợc quan tâm hiện nay. 3 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN 1.1. KHÁI NIỆM TRONG TOÁN HỌC. 1.1.1.Khái niệm trong số học. 1.1.1.1. Tính chia hết, quan hệ đồng dư và số nguyên tố. 1/.Tính chia hết. Xét 2 số nguyên a và b. Ta gọi a chia hết cho b   số nguyên n thỏa mãn a=b*n. Khi đó a đƣợc gọi là bội số của b, b đƣợc gọi là ƣớc số của a. Ký hiệu a|b. a đƣợc gọi là chia cho b dƣ r   số nguyên k và r thỏa mãn a = k.b + r. Khi đó r gọi là số dƣ của phép chia a cho b. Xét dãy số (a1,a2, …, an). Nếu b là ƣớc số chung của tất cả các số trong dãy số trên, và tất cả các ƣớc số chung khác của dãy đều là ƣớc số của b, thì ta gọi b là ƣớc số chung lớn nhất của dãy. Ký hiệu b = USCLN (a1,a2, …, an) = gcd (a1,a2, …, an). Nếu b là bội số chung của tất cả các dãy trong dãy số trên, và tất cả các bội số chung khác của dãy đều là bội số của b, thì ta gọi b là bội số chung nhỏ nhất của dãy. Ký hiệu b = BSCNN (a1,a2, …, an) = lcm (a1,a2, …, an). Ta có: gcd (a, b) = 1  a và b nguyên tố cùng nhau. 2/.Quan hệ đồng dƣ. a và b đồng dƣ theo modulo n  (a - b)|r. Ký hiệu a  b (mod n). 3/.Số nguyên tố. Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Các số tự nhiên không phải là số nguyên tố thì gọi là hợp số. Số nguyên tố đóng một vai trò rất quan trọng trong lĩnh vực an toàn thông tin. 4 Số lƣợng các số nguyên tố là vô hạn, đồng thời cho đến nay ngƣời ta vẫn chƣa tìm ra đƣợc quy luật của dãy số nguyên tố. Số nguyên tố đã đƣợc nghiên cứu từ trƣớc Công nguyên. Hiện nay, đã có rất nhiều thuật toán đƣợc nghiên cứu nhằm xác định một số có phải là số nguyên tố hay không. Gần đây nhất, vào tháng 8 năm 2008, đã tìm ra số nguyên tố có gần 13 triệu chữ số, là một số nguyên tố dạng Mersenne. 1.1.1.2. Không gian Zn và cấu trúc nhóm. 1/.Không gian Zn và các phép tính cơ bản: Zn đƣợc định nghĩa là tập hợp các số tự nhiên nhỏ hơn n. Zn = {1, 2, … n - 1}. Zn* đƣợc định nghĩa là tập hợp các số tự nhiên nhỏ hơn n và nguyên tố cùng nhau với n. Zn* = {x|x  N, x < n, gcd (x, n) = 1}. Trong không gian Zn, các phép toán đều đƣợc thực hiện theo modulo n. Phép cộng, phép trừ và phép nhân đƣợc thực hiện bình thƣờng nhƣ trong không gian Z, tuy nhiên kết quả cuối cùng phải đƣợc tính lại theo modulo n. Phép chia trong không gian Zn liên quan tới khái niệm phần tử nghịch đảo. Phần tử nghịch đảo của a  Znđịnh nghĩa là b  Zn thỏa mãn a.b=1(mod n), ký hiệu b = a-1(mod n). Vì vậy, phép chia a cho b trong không gian Zn chỉ có nghĩa nếu b có phần tử nghịch đảo, bởi vì a/b = a.b-1. 2/.Cấu trúc nhóm: Nhóm là một bộ hai phần tử (G, *), trong đó G là tập hợp khác rỗng, * là phép toán hai ngôi thỏa mãn: - Tính kết hợp: (a * b) * c = a * (b * c)  a,b,c  G. - Tồn tại phần tử trung lập e  G thỏa mãn: e * x = x * e = e  x  G. -  x  G,  phần tử nghịch đảo x‟ của x thỏa mãn: x * x‟ = x‟ * x = e. 5 Nhóm con của nhóm (G, *) là nhóm (S, *) thỏa mãn: - S  G. - Phần tử trung lập e của G nằm trong S. - S khép kín đối với phép * và lấy nghịch đảo trong G. Nhóm đƣợc gọi là nhóm cyclic nếu nó đƣợc sinh ra từ một trong các phần tử của nó. Phần tử đó gọi là phần tử nguyên thủy. 1.1.1.3. Dãy số giả ngẫu nhiên. Khái niệm “ngẫu nhiên” đóng một vai trò hết sức quan trọng trong đời sống và trong lĩnh vực an toàn thông tin. Một dãy bit đƣợc coi là ngẫu nhiên hoàn toàn, tức là nếu ta biết toàn bộ các bit từ 0 tới bit n, thì ta cũng không có thêm thông tin gì để đoán nhận bit n+1 là 0 hay 1. Nhƣ vậy, ta không có cách nào đoán nhận một dãy bit là ngẫu nhiên hay không, vả lại, trong máy tính, ta bắt buộc phải sinh ra dãy bit theo một số hữu hạn các quy tắc nào đó, thì không thể coi là ngẫu nhiên đƣợc nữa. Vì vậy, trong thực tế, chúng ta chỉ có thể sử dụng các dãy số giả ngẫu nhiên (pseu-random number) mà thôi. Các chuỗi giả ngẫu nhiên đƣợc hiểu là, nếu ta biết các bit từ 0 tới n, thì vẫn “khó” đoán đƣợc bit n+1. Một số thuật toán sinh dãy số giả ngẫu nhiên nhƣ thuật toán sinh dãy giả ngẫu nhiên RSA, thuật toán Blum Blum Shud, v.v… 1.1.2. Khái niệm độ phức tạp thuật toán. Thuật toán đƣợc định nghĩa là một dãy hữu hạn các chỉ thị mô tả một quá trình tính toán nào đó. Một bài toán đƣợc gọi là “giải đƣợc” nếu tồn tại một thuật toán giải quyết bài toán đó. Ngƣợc lại bài toán gọi là “không giải đƣợc”. Tuy nhiên, không phải bài toán nào thuộc lớp bài toán “giải đƣợc” cũng có thể giải đƣợc trong thực tế. Do đó, ngƣời ta đƣa ra khái niệm chi phí để giải một bài toán, chi phí này liên quan mật thiết tới thuật toán giải bài toán đó, phụ thuộc vào bốn tiêu chí sau: 6  Thuật toán có dễ hiểu không.  Thuật toán có dễ cài đặt không.  Số lƣợng bộ nhớ cần sử dụng.  Thời gian thực hiện chƣơng trình. Trong các tiêu chí đó, tiêu chí thời gian thực hiện đƣợc đánh giá là quan trọng nhất. Độ phức tạp thời gian của thuật toán, thƣờng đƣợc hiểu là số các phép tính cơ bản mà thuật toán phải thực hiện, trong trƣờng hợp xấu nhất. Với cỡ dữ liệu đầu vào là n, thời gian thực hiện thuật toán là t(n) đƣợc gọi là tiệm cận tới hàm f(n) nếu với n đủ lớn thì tồn tại số c thỏa mãn t(n)  c.f(n). Nếu f(n) là một hàm đa thức thì thuật toán đƣợc gọi là có độ phức tạp thời gian đa thức. Hiện nay, hầu hết các bài toán giải đƣợc trong thực tế đều là các bài toán có độ phức tạp thời gian đa thức. Các bài toán có độ phức tạp số mũ thực tế là khó thể giải đƣợc (có thể mất nhiều triệu tới nhiều tỷ năm). Lý thuyết độ phức tạp tính toán là lý thuyết quan trọng của khoa học máy tính. Nó cũng là cơ sở cho các phép toán gần đúng và xấp xỉ, hiện đang có nhiều ứng dụng trong khoa học. Từ lý thuyết độ phức tạp tính toán, xuất hiện một khái niệm rất quan trọng trong lĩnh vực an toàn thông tin: hàm một phía và hàm một phía có cửa sập. Hàm một phía (one way function): hàm số y = f(x) đƣợc gọi là hàm một phía, nếu khi biết giá trị của x thì ta dễ dàng tính đƣợc giá trị của y, nhƣng ngƣợc lại, nếu biết giá trị của y, ta “khó” tính đƣợc giá trị của x. Hàm một phía có cửa sập (trapdoor one way function): hàm một phía có cửa sập là hàm một phía, mà nếu biết “cửa sập” thì ta có thể dễ dàng tính ra giá trị của x khi biết giá trị của y. 7 1.2. KHÁI NIỆM MÃ HÓA. 1.2.1. Hệ mã hóa. Mã hóa đƣợc hiểu là thay đổi hình dạng thông tin gốc, khiến ngƣời khác “khó” nhận ra, tức là giấu đi ý nghĩa của thông tin gốc. Hệ mã hóa đƣợc định nghĩa là bộ năm phần tử (P, C, K, E, D) trong đó:  P là tập hữu hạn các bản rõ có thể.  C là tập hữu hạn các bản mã có thể.  K là tập hữu hạn các khóa có thể.  E là tập các hàm mã hóa.  D là tập các hàm giải mã. Với khóa lập mã ke  K, có hàm lập mã eke  E, eke: P → C. Với khóa giải mã kd  K, có hàm giải mã dkd  D, dkd: C → P. Thỏa mãn: dkd(eke(x)) = x,  x  P. Năm 1949, Claude Shannon (1916 - 2001) đã đƣa ra khái niệm hệ mã hóa an toàn tuyệt đối. Theo Shannon, một hệ mã hóa đƣợc coi là an toàn tuyệt đối khi biết đƣợc bản mã sẽ không cung cấp thêm thông tin gì về bản rõ. Nói một cách khác, bản mã và bản rõ là độc lập với nhau. Thông thƣờng, khi nghiên cứu các hệ mã hóa, ngƣời ta coi rằng bản mã đƣợc truyền trên đƣờng truyền không an toàn, và thuật toán mã hóa đã đƣợc công khai. Căn cứ theo đặc trƣng của khóa, hiện nay mã hóa đƣợc chia làm hai loại mã hóa chính là mã hóa khóa đối xứng và mã hóa khóa công khai. 8 1.2.2. Mã hóa khóa đối xứng. Mã hóa khóa đối xứng là hệ mã hóa mà nếu biết đƣợc khóa lập mà thì ta dễ dàng tính đƣợc khóa giải mã, và ngƣợc lại. Hệ mã hóa khóa đối xứng còn đƣợc gọi là hệ mã hóa khóa bí mật, hay hệ mã hóa khóa riêng. Đặc trƣng của hệ mã hóa khóa đối xứng:  Khóa phải đƣợc thỏa thuận và giữ bí mật giữa hai bên truyền tin. Khóa phải đƣợc truyền trên kênh an toàn giữa hai bên truyền tin. Điều này làm phức tạp quá trình thiết lập khóa. Hơn nữa, nếu giữa hai bên truyền tin không có kênh an toàn nào thì không thể thiết lập đƣợc quá trình truyền tin.  Nếu bên tấn công biết đƣợc khóa giải mã thì hệ mã hóa sẽ không còn bí mật.  Tốc độ tính toán nhanh. Một số hệ mã hóa khóa đối xứng điển hình: Các hệ mã hóa khóa đối xứng đƣợc chia thành hai loại lớn, đó là mã hóa khóa đối xứng cổ điển và mã hóa khóa đối xứng hiện đại. Mã hóa khóa đối xứng hiện đại chủ yếu sử dụng các khối lƣợng tính toán lớn nhờ vào sức mạnh tính toán của máy tính. 1/.Hệ mã hóa dịch chuyển: Mã hóa dịch chuyển (shift cipher) là hệ mã hóa khóa đối xứng cổ điển nhất còn đƣợc biết cho tới nay. Mã hóa dịch chuyển mã hóa trên từng ký tự, hay còn đƣợc biết với cái tên mã hóa dòng (stream cipher). Bản mã là tập hợp các ký tự đã đƣợc mã hóa. Tập bản rõ và tập bản mã là giống nhau, là các chữ cái trong bảng chữ cái. Mã hóa dịch chuyển có khóa lập mã và khóa giải mã giống nhau, là một số trong Zn với n là số lƣợng các ký tự có thể của bảng chữ cái (với tiếng Anh thì n = 26, với tiếng Việt thì n = 89, v.v…). Hàm lập mã cho ký tự rõ x với khóa k nhƣ sau: ek(x) = (x + k) mod n. Hàm giải mã cho ký tự mã x‟ với khóa k nhƣ sau: ek(x‟) = (x „– k) mod n. Tƣơng truyền rằng, hệ mã hóa dịch chuyển với khóa k = 3 đã đƣợc Julius Caesar (100TCN – 44TCN) sử dụng để truyền tin trong quân đội. 9 Độ an toàn của hệ mã hóa dịch chuyển là thấp, bởi chỉ có (n - 1) khóa có thể. Hệ mã hóa dịch chuyển có thể dễ dàng bị phá bằng phƣơng pháp thủ công theo nguyên tắc “thử và sai”. 2/.Hệ mã hóa thay thế: Hệ mã hóa thay thế (subsitution cipher) cũng là hệ mã hóa từng ký tự. Tập bản rõ và tập bản mã cũng giống nhau, là tập các ký tự trong bảng chữ cái. Tập các khóa có thể có là mọi hoán vị của Zn, với n là số lƣợng ký tự trong bảng chữ cái. Hàm lập mã: ek(x) =  )x( . Hàm giải mã: ek(x) =  -1 )x( . Số lƣợng khóa của hệ mã hóa thay thế là n!, là một con số rất lớn (26! > 1026) so với các phƣơng pháp tấn công vét cạn cổ điển. Tuy nhiên hệ mã hóa thay thế thƣờng bị tấn công dựa vào phân tích đặc trƣng ngôn ngữ. 3/.Hệ mã hóa Vigerene: Hệ mã hóa Vigenere khác với hai hệ mã hóa trình bày ở trên vì nó là hệ mã hóa khối (block cipher), mã hóa từng khối ký tự liên tục có chiều dài cố định. P = C = K = (Zn) m . Bản rõ x = (x1,x2 … xm). Khóa k = (k1,k2 … km). Mã hóa: y = (y1,y2 … yn) = x + k = (x1 + k1, x2 + k2, …, xn + kn) với lƣu ý rằng các phép toán đƣợc thực hiện trong không gian Zn. Giải mã: x = y – k. Mã hóa Vigenere quan trọng, bởi vì mã hóa Vigenere là hệ mã hóa an toàn tuyệt đối theo định nghĩa của Shannon, nếu chiều dài khóa không nhỏ hơn chiều dài văn bản, và các phần tử của khóa là ngẫu nhiên và độc lập hoàn toàn. Ngoài ra, hệ mã hóa khóa đối xứng cổ điển còn một vài hệ mã hóa khác nhƣ hệ mã hóa Affine, mã hóa Hill, mã hóa hàng rào, mã hóa Playfair, v.v…. 4/.Hệ mã hóa DES: 10 Hệ mã hóa DES (Data Encryption Standard – Chuẩn mã hóa dữ liệu) đƣợc công bố tại Mỹ vào năm 1977 nhƣ là một chuẩn mã hóa quốc gia. DES là một hệ mã hóa khối, mã hóa từng khối 64 bit. DES sử dụng khóa có chiều dài 64 bit, tuy nhiên do có 8 bit dùng để kiểm tra chẵn lẻ, nên chiều dài thực của khóa chỉ có 56 bit. Hệ mã hóa DES là một hệ mã hóa Feistel, chạy qua 16 vòng lặp để tạo ra từng khối bản mã 64 bit. Hình 1. Sơ đồ hệ mã hóa DES Hệ mã hóa DES từng gây rất nhiều tranh cãi về độ an toàn, cũng nhƣ những nghi ngại xung quanh việc tồn tại các cửa sập đối với hệ mã hóa này. Tuy nhiên, sau nhiều 11 năm tìm kiếm và nghiên cứu, vẫn chƣa có công bố nào về tình trạng thiếu an toàn của DES do nguyên nhân từ phía IBM, là công ty đã đề xuất DES. Năm 1997, lần đầu tiên có công bố chính thức về việc hệ mã hóa DES đã bị tấn công. Đến nay thì DES đã trở nên lỗi thời, và chủ yếu đƣợc sử dụng để nghiên cứu. Ngoài hệ mã hóa DES, thì cũng đã có nhiều hệ mã hóa khóa đối xứng hiện đại đƣợc nghiên cứu và công bố nhƣ: 3DES: đƣợc biết đến nhƣ một cải tiến của DES, bằng cách chạy DES 3 lần, và chiều dài khóa lên tới 168 bit. Tuy nhiên tốc độ thực hiện rất chậm. AES (Advanced Encryption Standard – Chuẩn mã hóa tiên tiến): đƣợc đƣa ra vào năm 2001, đƣợc khuyến nghị là sử dụng thay cho hệ mã hóa DES. Ngoài ra còn có các hệ mã hóa Blowfish, CAST – 128, v.v… 12 1.2.3. Mã hóa khóa công khai. Ý tƣởng về mã hóa khóa công khai lần đầu tiên đƣợc đề xuất vào năm 1976, thực sự là một cuộc cách mạng trong lĩnh vực mã hóa. Mã hóa khóa công khai sử dụng khái niệm hàm một chiều, khi biết đƣợc khóa giải mã thì dễ dàng tính ra đƣợc khóa lập mã, nhƣng ngƣợc lại, nếu biết khóa lập mã, lại “khó” tính đƣợc khóa giải mã. Hệ mã hóa khóa công khai làm đơn giản quá trình thiết lập và trao đổi khóa. Ngƣời gửi tin bây giờ sẽ mã hóa bằng khóa công khai của bên nhận, và tiến hành truyền tin. Bên nhận sẽ nhận tin, và sử dụng khóa bí mật của mình để giải mã bản tin. Kẻ tấn công trên đƣờng truyền cho dù có đƣợc bản mã và khóa công khai cũng không thể tính ra đƣợc bản rõ. Đặc trƣng của hệ mã hóa khóa công khai:  Thuật toán chỉ đƣợc viết một lần, công khai cho nhiều ngƣời sử dụng.  Mỗi ngƣời chỉ cần giữ khóa bí mật của riêng mình, do đó khả năng bị lộ khóa sẽ ít hơn.  Khi có đƣợc các tham số đầu vào của hệ mã hóa, thì việc tính toán phải trong thời gian đa thức.  Phƣơng pháp tấn công vét cạn là không khả thi, bởi số trƣờng hợp là rất lớn.  Tốc độ tính toán rất chậm.  Cần phải có chứng nhận của bên thứ ba có thẩm quyền (CA), bởi có thể xảy ra tình trạng giả mạo khóa công khai.  Độ an toàn của hệ mã hóa khóa công khai phụ thuộc vào khái niệm hàm một chiều, tuy nhiên đến bây giờ vẫn chƣa chính thức chứng minh đƣợc là có tồn tại hàm một chiều hay không, vì vậy độ an toàn của hệ mã hóa khóa công khai vẫn chƣa đƣợc đảm bảo về mặt lý thuyết. Các hệ mã hóa khóa công khai tiêu biểu: 13 1/.Hệ mã hóa RSA: Hệ mã hóa RSA đƣợc Rivest, Shamir và Adleman đề xuất năm 1977. Quy trình mã hóa RSA: Tạo khóa: Chọn 2 số nguyên tố lớn p và q. Tính n = p.q. Đặt P = C = Zn. Tính ф(n) = (p - 1).(q - 1). Chọn b  Zф(n). Tính a = b -1 mod ф(n). a, p, q đƣợc giữ bí mật. b,n đƣợc công khai. Mã hóa: y=ek(x)=x b( mod n). Giải mã: x = dk(y) = y a mod n. Mã hóa RSA dựa vào độ khó của bài toán phân tích một số lớn thành các thừa số nguyên tố. Theo khuyến nghị, thì độ dài của p và q tối thiểu phải từ 512 tới 1024 bit mới đảm bảo an toàn cho hệ mã hóa. 14 2/.Hệ mã hóa Elgamal: Hệ mã hóa Elgamal đƣợc Taher Elgamal (1955 - ) đề xuất năm 1984. Quy trình mã hóa Elgamal nhƣ sau: Tạo khóa: Chọn số nguyên tố p sao cho bài toán logarith rời rạc trong Zp là “khó”. Gọi g là phần tử nguyên thủy của Zp*. Đặt P = Zp*, C = Zp* x Zp*. Chọn a  Zp*. Tính h = g a mod p. Giữ bí mật a, công khai p,g và h. Lập mã: Chọn ngẫu nhiên r  Zp-1. Bản mã: y = ek(x) = (y1, y2) với y1 = g r mod p và y2 = x.h r mod p. Giải mã: x = dk(y) = y2.(y1 a ) -1 mod p. Hệ mã hóa Elgamal dựa vào độ khó của bài toán logarith rời rạc. Khuyến nghị độ dài khóa của hệ mã hóa Elgamal cũng nên từ 512 tới 1024 bit. Ngoài ra còn có nhiều hệ mã hóa khóa công khai khác nhƣ hệ mã hóa Rabin, v.v… 15 1.3. KHÁI NIỆM CHỮ KÝ SỐ. 1.3.1. Sơ đồ ký số: Chữ ký số (digital signature), hay còn đƣợc gọi là chữ ký điện tử, là một khái niệm đƣợc ra đời cùng với hệ mã hóa khóa công khai. Trƣớc đây, với những tài liệu giấy truyền thống, để chứng thực tác giả một văn bản, ngƣời ta phải ký vào văn bản đó. Chữ ký tay nhƣ vậy sẽ gắn vật lý với văn bản, và có đặc điểm là giống nhau (tƣơng đối) giữa các văn bản khác nhau, nếu cùng một ngƣời ký. Để xác thực chữ ký đó, ngƣời ta sẽ nhờ tới các chuyên gia giám định, và trong nhiều trƣờng hợp vẫn gây nên tranh cãi. Đối với các tài liệu số, thì chữ ký điện tử không thể theo mô hình nhƣ vậy, do đặc tính dễ sao chép của các tài liệu số. Nếu chữ ký điện tử giống nhau qua các văn bản, ngƣời ta có thể dễ dàng sao chép chữ ký điện tử này và gắn vào các văn bản giả mạo. Do đó, chữ ký điện tử ngoài việc gắn liền với tác giả, còn phải gắn liền với văn bản. Chữ ký điện tử có tƣ tƣởng gần giống với hệ mã hóa khóa công khai. Để ký lên một tài liệu, ngƣời ký sẽ sử dụng khóa bí mật của mình. Để kiểm chứng chữ ký, ngƣời kiểm chứng sẽ sử dụng khóa công khai của ngƣời ký. Nhƣ vậy, những ai không biết khóa bí mật thì không thể giả mạo chữ ký. Sơ đồ ký số đƣợc định nghĩa là một bộ năm phần tử (P, A, K, S, V) trong đó:  P là tập hữu hạn các văn bản có thể.  A là tập hữu hạn các chữ ký có thể.  K là tập hữu hạn các khóa.  S là tập các thuật toán ký.  V là tập các thuật toán kiểm thử. Với mỗi khóa k  K, có thuật toán ký sigk  S và thuật toán kiểm thử verk  V. Ký lên văn bản x  P: s = sigk(x). Kiểm thử: verk(x, s) = true s = sigk(x). 16 1.3.2. Sơ đồ ký số RSA. Tạo khóa: Chọn số nguyên tố p, q lớn. Tính n = p.q, đặt P = C = Zn. Tính ф(n) = (p - 1).(q - 1). Chọn b  Zф(n)*. a = b -1 mod ф(n). Giữ bí mật a, công khai b. Ký: Chữ ký trên x  P là y = sigk (x) = x a mod n. Kiểm thử chữ ký: verk(x, y) = true  x = y b mod n. Ngoài ra còn có nhiều hệ chữ ký điện tử khác, nhƣ chữ ký Elgamal, chữ ký DSS, chữ ký dùng một lần, chữ ký chống chối bỏ, v.v… 17 1.4. MỘT SỐ CÔNG CỤ BẢO VỆ BẢN QUYỀN KHÁC. 1.4.1. Hàm băm. Hàm băm (hash function) là một công cụ để đảm bảo toàn vẹn dữ liệu, cũng nhƣ tạo ra đại diện cho một tài liệu nào đó. Nhƣ trên chúng ta đã thấy, chữ ký điện tử đƣợc ký trên từng bit của tài liệu, do đó độ dài của chữ ký số ít nhất cũng bằng độ dài của tài liệu, thậm chí có trƣờng hợp còn dài gấp đôi tài liệu nhƣ chữ ký DSS. Nếu gặp trƣờng hợp văn bản quá dài, ta bắt buộc phải chia văn bản thành từng khối, ký trên các khối đó và ghép các chữ ký lại với nhau. Nhƣ vậy có rất nhiều điều bất tiện: độ dài của chữ ký sẽ bằng hoặc lớn hơn độ dài của văn bản, do đó sẽ tốn dung lƣợng để lƣu trữ chữ ký, nhƣng quan trọng hơn, là sẽ tốn thời gian để ký, và thời gian truyền chữ ký trên mạng. Ngƣời ta mong muốn, chữ ký số sẽ có khả năng nhƣ chữ ký tay, đó là chỉ cần một đoạn văn bản nhỏ, cho dù độ dài của tài liệu có lớn đến mức nào đi chăng nữa. Nhƣng đặc trƣng của chữ ký điện tử, đó là ký trên từng bit của tài liệu đƣợc ký, nên chỉ có cách thu gọn tài liệu mới mong làm giảm độ dài chữ ký. Nhƣng bản thân tài liệu thì không thể thu gọn, vậy chỉ có cách tạo ra một đại diện của tài liệu, và ký lên đại diện tài liệu đó. Hàm băm là một công cụ giải quyết yêu cầu trên. Hàm băm là một ánh xạ, từ không gian tài liệu có thể vào một không gian tài liệu có độ dài cố định, tức là h: (0, 1)* → (0, 1)n với n là độ dài của hàm băm. Hàm băm phải thỏa mãn các tính chất sau:  Với mỗi giá trị tài liệu, hàm băm chỉ cho ra một giá trị băm duy nhất.  Với hai giá trị tài liệu khác nhau, giá trị băm của chúng cũng khác nhau. Nhƣ vậy, khi truyền trên mạng, chỉ cần giá trị của tài liệu bị thay đổi 1 bit thì giá trị hàm băm cũng sẽ bị thay đổi.  Hàm băm là hàm một chiều, tức là tính giá trị băm từ giá trị tài liệu thì dễ, nhƣng ngƣợc lại thì “khó”.  Hàm băm phải không va chạm mạnh. Hàm băm có rất nhiều ứng dụng trong lĩnh vực an toàn thông tin: Để tạo chữ ký điện tử, bây giờ ta không cần ký trên toàn văn bản nữa, mà chỉ cần ký trên giá trị băm của tài liệu. Do mỗi tài liệu có một giá trị băm duy nhất, nên điều này hoàn toàn khả thi. 18 Hàm băm dùng để bảo vệ toàn vẹn dữ liệu. Do dữ liệu chỉ cần thay đổi 1 bit là giá trị băm cũng sẽ thay đổi, nên ta có thể xác định dữ liệu có toàn vẹn sau khi truyền tin hay không. Hàm băm đƣợc ứng dụng trong việc bảo vệ truy cập. Khi ngƣời sử dụng gõ mật khẩu (password) để đăng nhập vào hệ thống, giá trị băm của mật khẩu này sẽ đƣợc so sánh với giá trị băm của mật khẩu lƣu trong cơ sở dữ liệu. Điều đó giúp mật khẩu truyền qua mạng đƣợc an toàn. 1.4.2. Truy vết. Truy vết (tracing traitor) là khái niệm đƣợc sử dụng trong bảo vệ bản quyền các tài liệu đƣợc phát tán theo dạng quảng bá (broadcast). Ví dụ, một nhà cung cấp dịch vụ truyền hình thông thƣờng sẽ không thể kiểm soát đƣợc rằng có bao nhiêu khán giả xem chƣơng trình của họ. Cũng nhƣ vậy, một công ty phần mềm sẽ khó mà kiểm tra đƣợc rằng ngƣời sử dụng sau khi mua sản phẩm có bản quyền rồi thì có giữ bí mật bản quyền đó hay không, hay là đem chia sẻ hoặc bán lại cho ngƣời khác. Các công cụ truy vết sẽ giúp các nhà cung cấp theo dõi, xác định đƣợc là thiết bị thu nào là thiết bị thu trái phép, cũng nhƣ xác định đƣợc ngƣời sử dụng nào đã để lộ khóa bí mật của mình cho ngƣời khác sử dụng. Các công cụ truy vết cũng có rất nhiều ứng dụng. Gần đây ở Việt Nam, Đài truyền hình kỹ thuật số VTC đã áp dụng các thuật toán truy vết để ngăn chặn các thiết bị thu bất hợp pháp thu đƣợc tín hiệu truyền hình của họ. 19 1.5. THỦY VÂN SỐ. 1.5.1. Khái niệm thủy vân số. 1.5.1.1. Lịch sử thủy vân số. Khái niệm thủy vân đã ra đời từ lâu. Năm 1282, thủy vân đã đƣợc các công nhân nhà máy giấy sử dụng ở Italia. Các tờ giấy sẽ mỏng hơn và có hoa văn trên đó. Điều này giúp các xƣởng sản xuất giấy đánh dấu bản quyền trên tờ giấy của họ làm ra. Đến thế kỷ XVIII, thủy vân đã có nhiều ứng dụng ở châu Âu và Mỹ trong việc xác thực bản quyền hay chống tiền giả. Thuật ngữ thủy vân bắt nguồn từ một loại mực vô hình và chỉ hiện lên khi nhúng vào nƣớc. Hình 2. Thủy vân trên đồng dollar của Mỹ Thủy vân số (digital watermarking) là một công cụ giúp đánh dấu bản quyền hay những thông tin cần thiết vào tài liệu điện tử. Thuật ngữ thủy vân số đƣợc cộng đồng thế giới chấp nhận rộng rãi vào đầu thập niên 1990. Khoảng năm 1995, sự quan tâm đến thủy vân bắt đầu phát triển nhanh. Năm 1996, hội thảo về che dấu thông lần đầu tiên đƣa thủy vân vào phần trình nội dung chính. Đến năm 1999, SPIE đã tổ chức hội nghị đặc biệt về Bảo mật và thủy vân trên các nội dung đa phƣơng tiện. Cũng trong khoảng thời gian này, một số tổ chức đã quan tâm đến kỹ thuật watermarking với những mức độ khác nhau. Chẳng hạn CPTWG thử nghiệm hệ thống thủy vân bảo vệ phim trên DVD. SDMI sử dụng thủy 20 vân trong việc bảo vệ các đoạn nhạc. Hai dự án khác đƣợc liên minh châu Âu ủng hộ, VIVA và Talisman đã thử nghiệm sử dụng thủy vân để theo dõi phát sóng. Vào cuối thập niên 1990, một số công ty đƣa thủy vân vào thƣơng trƣờng, chẳng hạn các nhà phân phối nhạc trên internet sử dụng Liqid Audio áp dụng công nghệ của Verance Corporation. Trong lĩnh vực thủy vân ảnh, Photoshop đã tích hợp một bộ nhúng và bộ dò thủy vân tên là Digimarc. 21 1.5.1.2. Quá trình nghiên cứu thủy vân số. Thủy vân số đƣợc coi là ra đời từ năm 1954, với bằng sáng chế của Emile Hembrooke. Tuy nhiên, nghiên cứu thủy vân vẫn chƣa đƣợc đặt ra nhƣ là một lĩnh vực nghiên cứu độc lập cho tới những năm 1980. Tuy nhiên khái niệm thủy vân chỉ đƣợc hoàn thiện vào giữa những năm 90 của thế kỷ trƣớc. Những nghiên cứu đầu tiên về thủy vân đều tập trung vào nghiên cứu "thủy vân mù" (blind watermark). Thủy vân mù là thủy vân đƣợc nhúng mà không cần quan tâm tới nội dung của môi trƣờng nhúng. Tƣơng tự nhƣ vậy, các thuật toán tách thủy vân mù đều độc lập với những thành phần dữ liệu không chứa thủy vân. Có thể ví thủy vân mù nhƣ chữ ký tay, nội dung của thủy vân không thay đổi với các môi trƣờng nhúng khác nhau. Vào năm 1999, đã có một sự thay đổi lớn diễn ra. Trong một bài báo đăng trên IEEE, Cox và các đồng nghiệp đã nhận ra, chất lƣợng thủy vân sẽ tốt hơn rất nhiều nếu nhƣ thủy vân có quan tâm tới nội dung của môi trƣờng nhúng. Các thủy vân này đƣợc gọi là các thủy vân giàu (informed watermark), khi đó nội dung của thủy vân đƣợc hiểu là một hàm của nội dung môi trƣờng nhúng. Có thể so sánh ý tƣởng này với ý tƣởng về chữ ký điện tử. Đi xa hơn nữa, vào năm 2000, hai đội ngũ tác giả B.Chen, G.W.Wornell và J. Chou, Pradhan, Ghaoui, Ramchandran đã phát triển từ bài báo của M.Costa năm 1983 "Writing on diry paper" để phát triển một hƣớng nghiên cứu rất mới. Ý tƣởng chính của Costa là, có hai loại nhiễu sẽ tác động lên nội dung bản tin truyền đi. Loại nhiễu thứ nhất, là loại nhiễu xảy ra tại bên gửi, do các tác vụ biến đổi và xử lý tài liệu. Loại nhiễu này có thể kiểm soát. Loại nhiễu thứ hai là loại nhiễu xảy ra trên đƣờng truyền, và chúng ta không thể kiểm soát đƣợc chúng. Costa lý luận rằng, các thuật toán thủy vân trƣớc đây chỉ cố gắng nhúng thủy vân vào trong loại nhiễu thứ nhất, cho nên dung lƣợng tin giấu đƣợc là rất nhỏ. Costa cũng đã chỉ ra, dung lƣợng tin cần giấu là độc lập với loại nhiễu thứ nhất. Do đó, nếu ta coi toàn bộ tài liệu số là nhiễu thứ nhất, chúng ta sẽ có một phƣơng pháp để nhúng một lƣợng thông tin rất lớn vào tài liệu. Thủy vân có một ứng dụng rất quan trọng là bảo vệ sự toàn vẹn của tài liệu và chống xuyên tạc. Để thỏa mãn đƣợc yêu cầu này của thủy vân, các nghiên cứu trƣớc kia đều cố gắng áp dụng một mô hình tổng quát lên toàn bộ tài liệu. Tuy nhiên, vào năm 1995, Cox và các đồng nghiệp đã nhận ra, họ có thể sử dụng mô hình tri giác 22 (perceptual model) để giảm dung lƣợng thủy vân cần giấu. Thay vì cố gắng áp dụng một mô hình tổng quát lên toàn bộ tài liệu, thực ra chỉ cần áp dụng thủy vân lên một số phần quan trọng của tài liệu mà thôi. Đây có thể coi là một dạng đặc biệt của mô hình thủy vân giàu, vì nội dung thủy vân cũng bị phụ thuộc vào tài liệu. Nhƣ một chân lý của cuộc sống, luôn tồn tại sự thống nhất và đấu tranh giữa các mặt đối lập. Với sự ra đời của thủy vân, thì khoảng từ năm 1990 trở về sau, đã có nhiều nghiên cứu về tấn công cũng nhƣ chống tấn công đối với thủy vân. Những nghiên cứu này đã thúc đẩy quá trình nghiên cứu thủy vân đạt đƣợc nhiều kết quả mới. Thủy vân sử dụng công nghệ trải phổ (spread spectrum) đƣợc giới thiệu cùng thời điểm với mô hình tri giác, là một nỗ lực nhằm cân bằng giữa tính bền vững (robustness) và tính tin cậy (fidelity) của thủy vân số. Công nghệ trải phổ sẽ trải một băng tần hẹp vào một băng tần rông hơn, do đó tỷ lệ nhiễu trên mỗi tần số trở nên rất nhỏ. Phía bên ngƣời gửi sẽ tổng hợp lại các tín hiệu này, và lúc này nhiễu trở nên lớn. Công nghệ trải phổ là một hƣớng đi có nhiều triển vọng của kỹ thuật thủy vân. Chất lƣợng tài liệu điện tử sau khi giấu tin phải không đƣợc thay đổi nhiều, để cho con ngƣời khó có thể nhận ra bằng các giác quan thông thƣờng. Thủy vân số là một lĩnh vực nghiên cứu mới, có nhiều triển vọng. Những năm gần đây lĩnh vực này có đƣợc sự quan tâm đáng kể của các nhà nghiên cứu. 23 Hình 3. Số lượng các bài báo nghiên cứu về thủy vân số trong cơ sở dữ liệu của IEEE 24 1.5.1.3. Một số hệ thống thủy vân. Ngày nay, các công ty chuyên kinh doanh các hệ thống thủy vân đã tăng đáng kể, dƣới đây là một số ví dụ về các công ty và sản phẩm trong lĩnh vực thủy vân: 1/.Các hệ thống thủy vân âm thanh: Blue Spike, Inc: Công nghệ thủy vân của Giovanni, Blue Spike có thể đƣợc dùng để nhận dang, xác nhận và kiểm tra các tài liệu âm thanh. Verance Corporation Verance Corporation - đƣợc sát nhập từ ARIS Technologies, Inc. (Cambridge, Mass) và Solana Technology Development Corporation - sở hữu công nghệ thủy vân g đã có bằng sáng chế Musicode® và Electronic DNA®. 2/.Các hệ thống thủy vân trên ảnh: Signum Technologies: Một công ty Anh phát triển hệ thống thủy vân 'SureSign' dùng cho bảo vệ bản quyền và hệ thống 'VeriData' dùng để xác thực tính toàn vẹn của các ảnh số. Digimarc Các công nghệ có bằng sáng chế của Digimarc cho phép dữ liệu kĩ thuật số đƣợc nhúng trong các tài liệu có giá trị nhƣ giấy tờ tài chính, thị thực, giúp ngăn chặn giả mạo, trộm và sử dụng không đƣợc phép khác. 3/.Các hệ thống thủy vân trên phim: Alpha Tec. Ltd. - AudioMark : Alpha Tec. Ltd. là một công ty Hy Lạp phát triển AudioMark, gói phần mềm thiết kế cho việc nhúng các watermark vào tài liệu âm thanh và phim. MediaSec Technologies : Cung cấp công cụ SysCoP (System for Copyright Protection) để nhúng nhãn hiệu tác quyền vào ảnh và phim (MPEG). Hiện nay, kỹ thuật thủy vân đƣợc áp dụng vào trên Video ở một số công ty để chứng thƣ̣c bản quyền... 25 1.5.2. Các ứng dụng của thủy vân số. Bảo vệ quyền sở hữu (Copyright Protection): Digital watermark có thể đƣợc dùng để bảo vệ quyền sở hữu đối với các sản phẩm digital media. Nội dung của các digital media này sẽ chứa thêm các thông tin về ngƣời sở hữu. Khi các digital media này đƣợc sử dụng bất hợp pháp thì ta có thể dùng bộ watermark detector để phát hiện. Chống sao chép bất hợp pháp (Copy Protection): Các sản phẩm có chứa digital watermark biểu hiện cho việc sản phẩm này không đƣợc sao chép, vì nếu sao chép sẽ phạm luật. Nhà sản xuất sẽ trang bị cho các phƣơng tiện dùng để nhân bản (nhƣ CD writer…) khả năng phát hiện xem digital media có chứa thủy vân hay không, nếu có thì sẽ từ chối không sao chép. Một số phần mềm cũng có chức năng này, ví dụ nhƣ phần mềm xem phim của hãng DivX sẽ từ chối chiếu các bộ phim chứa thủy vân. Theo dõi quá trình sử dụng (Tracking): Digital watermarking có thể đƣợc dùng để theo dõi quá trình sử dụng của các digital media. Mỗi bản sao của sản phẩm đƣợc chứa bằng một watermarked duy nhất dùng để xác định ngƣời sử dụng là ai. Nếu có sự sao chép bất hợp pháp, ta có thể truy ra ngƣời vi phạm nhờ vào watermark đƣợc chứa bên trong digital media. Chống giả mạo (Tamper Proofing): Digital water marking có thể đƣợc dùng để chống sự giả mạo. Nếu có bất cứ sự thay đổi nào về nội dung của các digital media thì watermark này sẽ bị huỷ đi. Do đó rất khó làm giả các digital media có chứa watermark. Theo dõi truyền thông (Broadcast Monitoring): Các công ty truyền thông và quảng cáo có thể dùng kỹ thuật digital watermarking để quản lý xem có bao nhiêu khách hàng đã dùng dịch vụ cung cấp. Truyền tin bí mật (Concealed Communication): bởi vì digital watermarking là một dạng đặc biệt của việc che dấu dữ liệu (steganography) nên ngƣời ta có thể dùng để truyền các thông tin bí mật. 26 1.5.3. Các đặc tính của thủy vân. Để đảm bảo đƣợc những khả năng trên, thì thủy vân phải thỏa mãn đƣợc các yêu cầu sau: Tính ẩn: tính ẩn là khả năng khó bị nhận ra của thủy vân sau khi đã nhúng vào tài liệu điện tử, mà chủ yếu là các giác quan của con ngƣời. Nói cách khác, các tài liệu điện tử phải chịu ít sự thay đổi về mặt chất lƣợng khi nhúng thủy vân. Tính bền vững: tính bền vững đƣợc hiểu tùy vào mục đích của từng loại thủy vân, ví dụ với thủy vân dùng để bảo vệ bản quyền, thì thủy vân phải bền với các phép tấn công hay biến đổi, trong khi với thủy vân dùng để chống xuyên tạc hoặc đảm bảo toàn vẹn dữ liệu, thì thủy vân phải bị phá hủy ngay khi có sự tác động hoặc tấn công. Tính bảo mật: sau khi thủy vân số đã đƣợc nhúng vào tài liệu, thì yêu cầu chỉ cho những ngƣời có quyền mới có thể chỉnh sửa và phát hiện thủy vân. Tính hiệu quả: yêu cầu thuật toán thủy vân phải làm việc đƣợc với một vùng lớn các ảnh có thể. Dung lƣợng giấu: thuật toán thủy vân cho phép giấu càng nhiều thông tin càng tốt. Tuy nhiên, các yêu cầu trên thƣờng là trái ngƣợc nhau, và ngƣời ta phải cân đối giữa các yêu cầu để phù hợp với từng bài toán cụ thể. 27 1.5.4. Phân loại thủy vân. Có nhiều phƣơng pháp để phân loại thủy vân, dƣới đây trình bày những phƣơng pháp phân loại phổ biến nhất: Hình 4. Một số phương pháp phân loại thủy vân tiêu biểu Dựa vào miền tác động, chúng ta có thể phân loại thủy vân thành tác động lên miền không gian ảnh (spatial domain) và tác động lên miền tần số ảnh (frequency domain). Dựa vào kiểu tài liệu đƣợc nhúng thủy vân, chúng ta có thủy vân đƣợc nhúng vào ảnh, vào audio, video hay text. Dựa vào tác động tới thị giác con ngƣời, chúng ta có thủy vân hiện (visible watermark) hoặc thủy vân ẩn (invisible watermark). Thủy vân ẩn lại đƣợc chia thành thủy vân bền (robust watermark) và thủy vân dễ vỡ (fraglie watermark). Thủy vân hiện có ƣu điểm là nhìn đƣợc bằng mắt thƣờng, khiến cho tất cả ngƣời sử dụng đều biết đƣợc bản quyền của ảnh. Tuy nhiên, nó sẽ tác động tới chất lƣợng ảnh và gây mất thẩm mỹ. 28 1.5.5. Quy trình thực hiện thủy vân. Hình 5. Quy trình thực hiện thủy vân Quy trình thực hiện thủy vân đƣợc trải qua bốn bƣớc nhƣ sau: Tạo thủy vân. Nhúng thủy vân. Tách thủy vân. Kiếm tra thủy vân. 29 Chƣơng 2. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN ẢNH Sử dụng thủy vân số để bảo vệ bản quyền tài liệu cho ảnh là lĩnh vực giành đƣợc nhiều sự nghiên cứu nhất trong thủy vân số hiện nay, một phần là do tính lịch sử của nó. Ứng dụng thực tiễn của chúng cũng rất cao, bởi hiện nay, giá trị của các bức ảnh nghệ thuật hoặc tranh vẽ là rất cao, có thể lên tới nhiều triệu dollar. Chƣơng này trình bày về các định dạng ảnh thƣờng gặp, mô hình thị giác ngƣời, các phép biến đổi ảnh phổ biến và các thuật toán thủy vân trên ảnh. 2.1. CÁC ĐỊNH DẠNG ẢNH. 2.1.1. Định dạng ảnh BMP. Định dạng ảnh BMP là định dạng ảnh không nén, khá phổ biến, do Microsoft phát triển. Các file ảnh định dạng BMP thƣờng có phần mờ rộng là .bmp hoặc .dib. File ảnh BMP thƣờng có cấu trúc nhƣ sau: Bảng 1. Cấu trúc định dạng ảnh BMP Bitmap header (14 byte) Lƣu các thông tin chung về file ảnh nhƣ hệ điều hành, phần mềm tạo ra file ảnh, dung lƣợng của file ảnh, v.v…. Bitmap information Lƣu các thông tin chi tiết về file ảnh nhƣ: chiều cao, chiều rộng, độ phân giải, số lƣợng màu và một vài thông tin khác, v.v… Dung lƣợng của bitmap information phụ thuộc vào từng hệ điều hành. Từ hệ điều hành Microsoft Windows 2000 trở đi phần này có dung lƣợng 124 byte. Colour palette Bảng pallete màu, liệt kê các màu đƣợc sử dụng trong ảnh. Ảnh BMP luôn sử dụng hệ màu RGB. Bitmap data Lƣu thông tin thật sự của ảnh 30 File ảnh BMP có những độ sâu màu khác nhau, thể hiện ở việc số bit đƣợc dùng để lƣu trữ màu cho ảnh: 1 bit (ảnh đen trắng), 8 bit (ảnh 256 màu), 16 bit (ảnh 65535 màu), 24 bit (ảnh 16 triệu màu). Tới nay thì ảnh 16 triệu màu vẫn là ảnh có độ trung thực cao nhất. Định dạng ảnh BMP không sử dụng các thuật toán nén, nên dữ liệu lƣu trữ là rất lớn, gây khó khăn cho việc truyền tải thông tin qua mạng. 31 2.1.2. Định dạng ảnh PNG. PNG (từ viết tắt trong tiếng Anh của Portable Network Graphics) là một dạng hình ảnh sử dụng phƣơng pháp nén dữ liệu mới - không làm mất đi dữ liệu gốc. PNG đƣợc tạo ra nhằm cải thiện và thay thế định dạng ảnh GIF với một định dạng hình ảnh không đòi hỏi phải có giấy phép sáng chế khi sử dụng. PNG đƣợc hỗ trợ bởi thƣ viện tham chiếu libpng, một thƣ viện nền tảng độc lập bao gồm các hàm của C để quản lý các hình ảnh PNG. Những tập tin PNG thƣờng có phần mở rộng là PNG and png và đã đƣợc gán kiểu chuẩn MIME là image/png (đƣợc công nhận vào ngày 14 tháng 10 năm 1996). Động cơ thúc đẩy cho việc tạo ra định dạng PNG bắt đầu vào khoảng đầu năm 1995, sau khi Unisys công bố họ sẽ áp dụng bằng sáng chế vào thuật toán nén dữ liệu LZW- đƣợc sử dụng trong định dạng GIF. Thuật toán đƣợc bảo vệ bởi bằng công nhận độc quyền sáng tạo ở trong nƣớc Mỹ và tất cả các nƣớc trên thế giới. Tuy nhiên, cũng đã có một số vấn đề với định dạng GIF khi cần có một số thay đổi trên hình ảnh, nhất giới hạn của nó là 256 màu trong thời điểm máy tính có khả năng hiển thị nhiều hơn 256 màu đang trở nên phổ biến. Mặc dù định dạng GIF có thể thể hiện các hình ảnh động, song PNG vẫn đƣợc quyết định là định dạng hình ảnh đơn (chỉ có một hình duy nhất). Một ngƣời "anh em" của nó là MNG đã đƣợc tạo ra để giải quyết vấn đề ảnh động. PNG lại tăng thêm sự phổ biến của nó vào tháng 8 năm 1999, sau khi hãng Unisys huỷ bỏ giấy phép của họ đối với các lập trình viên phần mềm miễn phí, và phi thƣơng mại. Phiên bản 1.0 của đặc tả PNG đƣợc phát hành vào ngày 1 tháng 7 năm 1996, và sau đó xuất hiện vơi tƣ cách RFC 2083. Nó đƣợc tổ chức W3C khuyến nghị vào ngày 1 tháng 10 năm 1996. Phiên bản 1.1, với một số thay đổi nhỏ và thêm vào 3 thành phần mới, đƣợc phát hành vào ngày 31 tháng 12 năm 1998. Phiên bản 1.2, thêm vào một thành phần mở rộng, đƣợc phát hành vào ngày 11 tháng 8 năm 1999. PNG giờ đây là một chuẩn quốc tế (ISO/IEC 15948:2003), và cũng đƣợc công bố nhƣ một khuyến nghị của W3C vào ngày 10 tháng 11 năm 2003. Phiên bản hiện tại của PNG chỉ khác chút ít so với phiên bản 1.2 và không có thêm thành phần mới nào. Thông tin kỹ thuật: 32 Một tập tin PNG bao gồm 8-byte kí hiệu (89 50 4E 47 0D 0A 1A 0A đƣợc viết trong hệ thống có cơ số 16, chứa các chữ "PNG" và 2 dấu xuống dòng [1], ở giữa là sắp xếp theo số lƣợng của các thành phần, mỗi thành phần đều chứa thông tin về hình ảnh. Cấu trúc dựa trên các thành phần đƣợc thiết kế cho phép định dạng PNG có thể tƣơng thích với các phiên bản cũ khi sử dụng. Các thành phần trong tập tin: PNG là cấu trúc nhƣ một chuỗi các thành phần, mỗi thành phần chứa kích thƣớc, kiểu, dữ liệu, và mã sửa lỗi CRC ngay trong nó. Chuỗi đƣợc gán tên bằng 4 chữ cái phân biệt chữ hoa chữ thƣờng. Sự phân biệt này giúp bộ giải mã phát hiện bản chất của chuỗi khi nó không nhận dạng đƣợc. Với chữ cái đầu, viết hoa thể hiện chuỗi này là thiết yếu, nếu không thì ít cần thiết hơn ancillary. Chuỗi thiết yếu chứa thông tin cần thiết để đọc đƣợc tệp và nếu bộ giải mã không nhận dạng đƣợc chuỗi thiết yếu, việc đọc tệp phải đƣợc hủy. 33 2.1.3. Định dạng ảnh GIF. Định dạng ảnh GIF do hãng ComputServer Incorporated (Mỹ) đề xuất lần đầu tiên vào năm 1990. Với địng dạng GIF, những vƣớng mắc mà các định dạng khác gặp phải khi số màu trong ảnh tăng lên không còn nữa. Khi số màu càng tăng thì ƣu thế của định dạng GIF càng nổi trội. Những ƣu thế này có đƣợc là do GIF tiếp cận các thuật toán nén LZW(Lempel-Ziv-Welch). Bản chất của kỹ thuật nén LZW là dựa vào sự lặp lại của một nhóm điểm chứ không phải loạt dài giống nhau. Do vậy, dữ liệu càng lớn thì sự lặp lại càng nhiều. Dạng ảnh GIF cho chất lƣợng cao, độ phân giải đồ hoạ cũng đạt cao, cho phép hiển thị trên hầu hết các phần cứng đồ hoạ. Tập tin GIF dùng nén dữ liệu bảo toàn trong đó kích thƣớc tập tin có thể đƣợc giảm mà không làm giảm chất lƣợng hình ảnh, cho những hình ảnh có ít hơn 256 màu. Số lƣợng tối đa 256 màu làm cho định dạng này không phù hợp cho các hình chụp (thƣờng có nhiều màu sắc), tuy nhiên các kiểu nén dữ liệu bảo toàn cho hình chụp nhiều màu cũng có kích thƣớc quá lớn đối với truyền dữ liệu trên mạng hiện nay. Định dạng JPEG là nén dữ liệu thất thoát có thể đƣợc dùng cho các ảnh chụp, nhƣng lại làm giảm chất lƣợng cho các bức vẽ ít màu, tạo nên những chỗ nhòe thay cho các đƣờng sắc nét, đồng thời độ nén cũng thấp cho các hình vẽ ít màu. Định dạng tổng quát của ảnh GIF nhƣ sau: Bảng 2. Định dạng tổng quát ảnh GIF Chữ ký của ảnh GIF note Bộ mô tả hiển thị GIF header Bảng màu tổng thể Global pallette Mô tả đối tƣợng của ảnh: Dấu phân cách ảnh Bộ mô tả ảnh Bản đồ màu cục bộ Dữ liệu ảnh Mô tả này đƣợc lập n lần nếu có n đối tƣợng. Header image Phần đầu cuối ảnh GIF terminator 34 - Chữ ký của ảnh GIF có giá trị là GIF87a. Nó gồm 6 ký tự, 3 kí tự đầu chỉ ra kiểu định dạng, 3 ký tự sau chỉ ra version của ảnh. - Bộ hình hiển thị: chứa mô tả các thông số cho toàn bộ ảnh GIF: + Độ rộng hình raster theo pixel: 2 byte; + Độ cao hình raster theo pixel: 2 byte; + Các thông tin về bản đồ màu, hình hiển thị,... + Thông tin màu nền: 1 byte; + Phần chƣa dùng: 1 byte. Bản đồ màu tổng thể: mô tả bộ màu tối ƣu đòi hỏi khi bit M = 1. Khi bộ màu tổng thể đƣợc thể hiện, nó sẽ xác lập ngay bộ mô tả hình hiển thị. Số lƣợng thực thể bản đồ màu lấy theo bộ mô tả hình hiển thị ở trên và bằng 2 m, với m là lƣợng bit trên một pixel khi mỗi thực thể chứa đựng 3 byte (biểu diễn cƣờng độ màu của ba màu cơ bản Red-Green-Blue). Cấu trúc của khối này nhƣ sau: Bảng 3. Cấu trúc khối bản đồ màu tổng thể ảnh GIF Bit Thứ thự byte Mô tả màu Red 1 giá trị màu đỏ theo index 0 màu Green 2 giá trị màu xanh lục theo index 0 màu Blue 3 giá trị màu xanh lơ theo index 0 màu Red 4 giá trị màu đỏ theo index 1 màu Green 5 giá trị màu xanh lục theo index1 màu Blue 6 giá trị màu xanh lơ theo index 0 . . . . . . . . . . . . . . . . . . . . . . . . . 35 - Bộ mô tả ảnh: định nghĩa vị trí thực tế và phần mở rộng của ảnh trong phạm vi không gian ảnh đã có trong phần mô tả hình hiển thị. Nếu ảnh biểu diễn theo ánh xạ bản đồ màu cục bộ thì cờ định nh\ghĩa phải đƣợc thiết lập. Mỗi bộ mô tả ảnh đƣợc chỉ ra bởi ký tự kết nối ảnh. Ký tự này chỉ đƣợc dùng khi định dạng GIF có từ 2 ảnh trở lên. Ký tự này có giá trị 0x2c (ký tự dấu phảy). Khi ký tự này đƣợc đọc qua, bộ mô tả ảnh sẽ đƣợc kích hoạt. Bộ mô tả ảnh gồm 10 byte và có cấu trúc nhƣ sau: Bảng 4. Cấu trúc bộ mô tả ảnh GIF Các bit Thứ thự byte Mô tả 00101100 1 Ký tự liên kết ảnh („) căn trái ảnh 2,3 Pixel bắt đầu ảnh tính từ trái hình hiển thị căn đỉnh trên 4,5 Pixel cuối ảnh bắt đầu tính từ đỉnh trên hình hiển thị độ rộng ảnh 6,7 chiều rộng ảnh tính theo pixel độ cao ảnh 8,9 chiều cao ảnh tính theo pixel MI000pixel 10 Khi bit M = 0 : sử dụng bản đồ màu tổng thể M = 1 : sử dụng bản đồ màu cục bộ I = 0 : định dạng ảnh theo thứ tự liên tục I = 1 : định dạng ảnh theo thứ tự xen kẽ pixel +1: số bit/pixel của ảnh này. - Bản đồ màu cục bộ: bản đồ màu cục bộ chỉ đƣợc chọn khi bit M của byte thứ 10 là 1. Khi bản đồ màu đƣợc chọn, bản đồ màu sẽ chiếu theo bộ mô tả ảnh mà lấy vào cho đúng. Tại phần cuối ảnh, bản đồ màu sẽ lấy lại phần xác lập sau bộ mô tả hình hiển thị. Lƣu ý là trƣờng “pixel “ của byte thứ 10 chỉ đƣợc dùng khi bản đồ màu đƣợc chỉ định. Các tham số này không những chỉ cho biết kích thƣớc ảnh theo pixel mà còn chỉ ra số thực thể bản đồ màu của nó. 36 - Dữ liệu ảnh: chuỗi các giá trị có thứ tự của các pixel màu tạo nên ảnh. Các pixel đƣợc xếp liên tục trên một dòng ảnh, từ trái qua phải. Các dòng ảnh đƣợc viết từ trên xuống dƣới. - Phần kết thúc ảnh: cung cấp tính đồng bộ cho đầu cuối của ảnh GIF. Cuối của ảnh sẽ xác định bởi kí tự “;” (0x3b). Định dạng GIF có rất nhiều ƣu điểm và đã đƣợc công nhận là chuẩn để lƣu trữ ảnh màu thực tế (chuẩn ISO 10918-1). Nó đƣợc mọi trình duyệt Web (Web Browser) hỗ trợ với nhiều ứng dụng hiện đại. Cùng với nó có chuẩn JPEG (Joint Photograph Expert Group). GIF dùng cho các ảnh đồ hoạ (Graphic), còn JPEG dùng cho ảnh chụp (Photographic). 37 2.1.4. Định dạng ảnh JPEG. Do định dạng ảnh JPEG hiện nay rất phổ biến, và đóng vai trò quan trọng trong các lĩnh vực giấu tin cũng nhƣ thủy ký, nên khóa luận xin trình bày sâu hơn về định dạng ảnh JPEG. JPEG viết tắt của Joint Photographic Experts Group, một nhóm các nhà nghiên cứu đã phát minh ra định dạng này năm 1992 để hiển thị các hình ảnh đầy đủ màu hơn (full-colour) cho định dạng di động mà kích thƣớc file lại nhỏ hơn. Giống nhƣ ảnh GIF, JPEG cũng đƣợc sử dụng rất nhiều trên Web. Lợi ích chính của chúng hơn GIF là chúng có thể hiển thị các hình ảnh với màu chính xác true-colour (chúng có thể lên đến 16 triệu màu), điều đó cho phép chúng đƣợc sử dụng tốt nhất cho các hình ảnh chụp và hình ảnh minh họa có số lƣợng màu lớn. Các ảnh JPEG không thể làm trong suốt hoặc chuyển động - trong trƣờng hợp này bạn sẽ sử dụng định dạng GIF (hoặc định dạng PNG để tạo trong suốt). Tạo ảnh JPEG Fast-Loading: Giống nhƣ với các ảnh GIF, để tạo hình JPEG nhỏ đến mức có thể (tính theo bytes) để website tải nhanh hơn. Điều chỉnh chính để thay đổi kích thƣớc file JPEG đƣợc gọi là quality, và thƣờng có giá trị từ 0 tới 100%, khi 0% thì chất lƣợng là thấp nhất (nhƣng kích thƣớc file là nhỏ nhất), và 100% thì chất lƣợng cao nhất (nhƣng kích thƣớc file là lớn nhất). 0% chất lƣợng JPEG sẽ nhìn rất mờ khi so sánh với ảnh gốc. Còn 100% chất lƣợng JPEG thƣờng không phân biệt đƣợc so với ảnh gốc. 2.1.4.1. Kỹ thuật nén ảnh JPEG. Một tính chất chung nhất của tất cả các ảnh số đó là tƣơng quan giữa các pixel ở cạnh nhau lớn, điều này dẫn đến dƣ thừa thông tin để biểu diễn ảnh. Dƣ thừa thông tin sẽ làm cho việc mã hoá không tối ƣu. Do đó công việc cần làm để nén ảnh là phải tìm đƣợc các biểu diễn ảnh với tƣơng quan nhỏ nhất để giảm thiểu độ dƣ thừa thông tin của ảnh. Thực tế, có hai kiểu dƣ thừa thông tin đƣợc phân loại nhƣ sau: - Dư thừa trong miền không gian: tƣơng quan giữa các giá trị pixel của ảnh, điều này có nghĩa rằng các pixel lân cận của ảnh có giá trị gần giống nhau (trừ những pixel ở giáp đƣờng biên ảnh). - Dư thừa trong miền tần số: Tƣơng quan giữa các mặt phẳng màu hoặc dải phổ khác nhau. 38 Trọng tâm của các nghiên cứu về nén ảnh là tìm cách giảm số bit cần để biểu diễn ảnh bằng việc loại bỏ dƣ thừa trong miền không gian và miền tần số càng nhiều càng tốt. Các kỹ thuật nén ảnh đƣợc sử dụng: - Nén ảnh không mất thông tin : với phƣơng pháp này sau khi giải nén ta khôi phục đƣợc chính xác ảnh gốc. Các phƣơng pháp nén này bao gồm mã hoá Huffman, mã hoá thuật toán… - Nén ảnh có mất thông tin: ảnh giải nén có một sự sai khác nhỏ so với ảnh gốc. Các phƣơng pháp này bao gồm: Lƣợng tử hoá vô hƣớng: PCM và DPCM Lƣợng tử hoá vector Mã hoá biến đổi: biến đổi cosin rời rạc (DCT), biến đổi Fourier nhanh (FFT) Mã hoá băng con Hình6. Sơ đồ khối một hệ thống nén ảnh điển hình 39 2.1.4.2. Mã hoá biến đổi DCT. Nguyên tắc chính của phƣơng pháp mã hoá này là biến đổi tập các giá trị pixel của ảnh trong miền không gian sang một tập các giá trị khác trong miền tần số sao cho các hệ số trong tập giá trị mới này có tƣơng quan giữa các điểm ảnh gần nhau nhỏ hơn. Hình 7. Sơ đồ mã hóa và giải mã dùng biến đổi DCT 1/.Biến đổi DCT thuận và nghịch. Vì ảnh gốc có kích thƣớc rất lớn cho nên trƣớc khi đƣa vào biến đổi DCT, ảnh đƣợc phân chia thành các khối vuông, mỗi khối này thƣờng có kích thƣớc 8 x 8 pixel và biểu diễn các mức xám của 64 điểm ảnh, các mức xám này là các số nguyên dƣơng có giá trị từ 0 đến 255. Việc phân khối này sẽ làm giảm đƣợc một phần thời gian tính toán các hệ số chung, mặt khác biến đổi cosin đối với các khối nhỏ sẽ làm tăng độ chính xác khi tính toán với dấu phẩy tĩnh, giảm thiểu sai số do làm tròn sinh ra. Biến đổi DCT là một công đoạn chính trong các phƣơng pháp nén sử dụng biến đổi. Hai công thức (1), (2) minh hoạ cho hai phép biến đổi DCT thuận nghịch đối với mỗi khối ảnh có kích thƣớc 8 x 8. Giá trị x(n1, n2) biểu diễn các mức xám của ảnh trong miền không gian, X(k1, k2) là các hệ số sau biến đổi DCT trong miền tần số. Với và 40 Mỗi khối 64 điểm ảnh sau biến đổi DCT thuận sẽ nhận đƣợc 64 hệ số thực DCT. Mỗi hệ số này có chứa một trong 64 thành phần tần số không gian hai chiều. Hệ số với tần số bằng không theo cả hai hƣớng (tƣơng ứng với k1 và k2 bằng 0) đƣợc gọi là hệ số một chiều DC, hệ số này chính là giá trị trung bình của 64 điểm ảnh trong khối, 63 hệ số còn lại gọi là các hệ số xoay chiều AC. Hệ số một chiều DC tập trung phần lớn năng lƣợng của ảnh. Chú ý rằng bản thân biến đổi DCT không làm mất thông tin vì DCT là một biến đổi tuyến tính chuyển các giá trị của điểm ảnh từ miền không gian thành các hệ số trong miền tần số. Nếu biến đổi DCT thuận và nghịch đƣợc tính toán với độ chính xác tuyệt đối và nếu các hệ số DCT không phải qua bƣớc lƣợng tử và mã hoá thì ảnh thu đƣợc sau biến đổi DCT ngƣợc sẽ giống hệt ảnh gốc. Hình 8. Các bước của quá trình mã hóa biến đổi DCT đối với một khối 2/.Lƣợng tử và giải lƣợng tử. Sau khi thực hiện biến đối DCT, 64 hệ số sẽ đƣợc lƣợng tử hoá dựa trên một bảng lƣợng tử gồm 64 phần tử Q(u, v) với 0≤u, v≤7. Bảng này đƣợc định nghĩa bởi từng ứng dụng cụ thể. Các phần tử trong bảng lƣợng tử có giá trị từ 1 đến 255 đƣợc gọi là các bƣớc nhảy cho các hệ số DCT. Quá trình lƣợng tử đƣợc coi nhƣ là việc chia các hệ số DCT cho bƣớc nhảy lƣợng tử tƣơng ứng, kết quả này sau đó sẽ đƣợc làm tròn xuống số nguyên gần nhất. Công thức (3) thể hiện việc lƣợng tử với F(u, v) là các 41 hệ số DCT, FQ(u, v) là các hệ số sau lƣợng tử, các hệ số này sẽ đƣợc đƣa vào bộ mã hoá Entropy. Hình 9. Ma trận lượng tử Mục đích của việc lƣợng tử hoá là giảm số lƣợng bit cần để lƣu trữ các hệ số biến đổi bằng việc giảm độ chính xác của các hệ số này cho nên lƣợng tử là quá trình xử lý có mất thông tin. Quá trình giải lƣợng tử ở phía bộ giải mã đƣợc thực hiên ngƣợc lại. Các hệ số sau bộ giải mã entropy sẽ nhân với các bƣớc nhảy trong bảng lƣợng tử (bảng lƣợng tử đƣợc đặt trong phần header của ảnh JPEG). Kết quả này sau đó sẽ đƣợc đƣa vào biến đổi DCT ngƣợc. 3/.Mã hóa và giải mã Huffman. Mã hoá là bƣớc cuối cùng trong hệ thống nén ảnh dựa trên biến đổi DCT. Chuẩn nén ảnh JPEG hiện nay dùng phƣơng pháp mã hoá Huffman, đây là phép mã hoá không làm mất thông tin. Phƣơng pháp mã hoá Huffman là phƣơng pháp dựa vào mô hình thống kê. Dựa vào dữ liệu gốc, ngƣời ta tính tần suất xuất hiện của các ký tự. Việc tính tần xuất đƣợc thực hiện bằng cách duyệt tuần tự tệp gốc từ đầu đến cuối. Việc xử lý ở đây tính theo bit. Trong phƣng pháp này, ngƣới ta gán cho các ký tự có tần suất cao một từ mã ngắn, các ký tự có tần xuất thấp từ mã dài. Nói một cách khác, các ký tự có tần xuất càng cao đƣợc gán mã càng ngắn và ngƣợc lại. Rõ ràng với cách thức này, ta đã làm giảm chiều dài trung bình của từ mã hoá bằng cách dùng chiều dài biến đổi. Tuy nhiên, trong một số tình huống khi tần suất là rất thấp, ta có thể không đƣợc lợi một chút nào, thậm chí còn bị thiệt một ít bit. 42 Thuật toán mã hoá bao gồm hai bƣớc chính: - Giai đoạn một tính tần suất của các ký tự trong dữ liệu gốc: Duyệt tệp gốc một cách tuần tự từ đầu đến cuối để xây dựng bảng mã. Tiếp sau đó là sắp xếp lại bảng mã theo thứ tự tần suất giảm dần. - Giai đoạn thứ hai là giai đoạn mã hoá: Duyệt bảng tần suất từ cuối lên đầu để thực hiện ghép hai phần tử có tần suất thấp nhất thành một phần tử duy nhất. Phần tử này có tần xuất bằng tổng hai tần suất thành phần. Tiến hành cập nhật lại bảng và đƣơng nhiên loại bỏ hai phần tử đã xét. Quá trình đƣợc lặp lại cho đến khi bảng chỉ có một phần tử. Quá trình này gọi là quá trình tạo cây mã Huffman vì việc tập hợp đƣợc tiến hành nhờ một cây nhị phân với hai nhánh. Phần tử có tần suất thấp ở bên phải, phần tử kia ở bên trái. Với cách tạo cây này, tất cả các bit dữ liệu/ ký tự là nút lá; các nút trong là các nút tổng hợp. Sau khi cây đã tạo xong, ngƣời ta tiến hành gán mã cho các nút lá. Việc mã hoá rất đơn giản: mỗi lần xuống bên phải ta thêm một bit "1" vào từ mã; mỗi lần xuống bên trái ta thêm một bit "0". Tất nhiên có thể làm ngƣợc lại, chỉ có giá trị mã thay đổi còn tổng chiều dài là không đổi. Cũng chính là lý do này mà cây có tên gọi là cây mã Huffman nhƣ trên đã gọi. Quá trình giải nén tiến hành theo chiều ngƣợc lại khá đơn giản. Ngƣời ta cũng phải dựa vào bảng mã tạo ra trong giai đoạn nén (bảng này đƣợc giữ lại trong cấu trúc đầu của tệp nén cùng với dữ liệu nén). Thí dụ, với một tệp dữ liệu mà tần suất các ký tự cho bởi bảng sau. 43 Bảng 5. Bảng tần suất ký tự. Ký tự Tần suất Xác suất 0 1532 0.2770 6 602 0.1088 . 536 0.0969 “ “ 535 0.0967 3 112 0.0746 5 385 0.0696 2 323 0.0585 _ 315 0.0569 4 226 0.0409 + 220 0.0396 1 152 0.0275 8 112 0.0203 7 92 0.0167 9 87 0.0158 Lƣu ý rằng, trong phƣơng pháp Huffman, mã của ký tự là duy nhất và không mã nào là phần bắt đầu của mã khác. Vì vậy, khi đọc tệp nén từng bit từ đầu đến cuối ta có thể duyệt cây mã cho đến một lá, tức là ký tự đã đƣợc giải nén. 44 Cây mã Huffman tƣơng ứng Hình 10. Cây mã Huffman. 45 Bảng 6. Bảng từ mã gán cho các ký tự bởi mã hoá Huffman. Ký tự Từ mã 0 10 6 010 . 001 “ “ 000 3 1110 5 1100 2 0111 _ 0110 4 11110 + 11011 1 111111 8 111110 7 110101 9 110100 Áp dụng phƣơng pháp trên ngƣời ta tính tần suất xuất hiện các hệ số. Việc tính tần suất đƣợc thực hiện bằng cách duyệt tuần tự từ đầu khối đến cuối khối, sau đó những hệ số có tần suất cao đƣợc gắn cho một từ mã ngắn, các hệ số có tần suất thấp đƣợc gán một từ mã dài. Với cách thức này chiều dài trung bình của từ mã đã giảm xuống. 46 Hình 11. Bảng zigzag của các thành phần ảnh JPEG Các hệ số thu đƣợc sau khi lƣợng tử hoá sẽ đƣợc sắp xếp thành một chuỗi các ký hiệu theo kiểu “zig-zag” (theo đƣờng zig-zag trong bảng 2) để đặt các hệ số có tần số thấp lên trƣớc các hệ số tần số cao. Các hệ số này sẽ đƣợc mã hoá dựa trên bảng mã Huffman sao cho chiều dài trung bình của từ mã là nhỏ nhất. Bảng mã này cũng sẽ đƣợc đặt trong phần mào đầu của ảnh để thực hiện giải nén ảnh. 47 2.1.5. Định dạng ảnh JPEG2000. JPEG 2000 áp dụng một kỹ thuật nén mới để lƣu trữ dữ liệu ảnh, thay thế định dạng nén file hiện thời là DCT (Discrete Cosine Transformation). Nếu DCT nén ảnh theo từng khối vuông nhỏ rồi lƣu chúng dƣới dạng số thì kỹ thuật Wavelet Compression sẽ lƣu file dƣới dạng một dãy dữ liệu (kỹ thuật stream hình) nhằm tạo độ phân giải cao hơn khi file đƣợc mở hoặc tải về. Lợi ích đầu tiên của Wavelet là loại trừ đƣợc những "vết dơ" bao quanh các khối vuông và biến ƣớc mơ hình có độ phân giải cao trên mạng thành hiện thực. Các nhà thiết kế có nhiều khả năng lựa chọn khi lƣu và tải ảnh lên mạng, không hạn chế độ phân giải và dung lƣợng: từ những hình chỉ để xem trên màn hình thông dụng 96dpi cho tới những hình óc độ phân giải đáp ứng nhu cầu in ấn 300 dpi đến 600 dpi - độ phân giải khiến ảnh có thể tái sử dụng ở những mục đích khác mà không ảnh hƣởng tới chất lƣợng. Khả năng ngƣời dùng Internet, chỉ sau vài thao tác chỉnh sửa tuỳ chọn trong Web Browser, có thể tải về hình ở độ phân giải mặc định 96 dpi hoặc 300-600 dpi để dùng cho in ấn. Tất cả những dữ liệu ảnh đó, từ 96 dpi cho đến 600 dpi đều đƣợc lƣu trong cùng một file với định dạng theo kiểu mới: JPEG 2000. Với định dạng mới, các nhà thiết kế có thể cài đặt các đoạn mã về bản quyền, xuất xứ... của ảnh và an tâm rằng khả năng tồn tại của các thông tin này là rất cao - cho dù ảnh có bị chỉnh sửa hay thay đổi kích cỡ đi chăng nữa. Ðây là một điểm mạnh của JPEG 2000 so với các mã truyền thống theo thuật "Watermaking". Khả năng tạo thêm các kênh phụ để lƣu trữ những thông tin nhƣ thông số màu CMYK hay ICC profiles (nhằm loại bỏ sự khác biệt về Gamma màu giữa PC và MAC) đã đƣợc đƣa vào JPEG 2000. Một ảnh JPEG 2000 có thể lƣu giữ đến 256 kênh thông tin khác nhau, một tính năng rất hữu ích cho các nhà sản xuất phần mềm và phần cứng muốn gửi thông tin chuyên biệt đến tay khách hàng. Nhà sản xuất phần mềm có thể muốn cài những thông tin về thƣ viện ảnh cùng dịch vụ liên quan, nhà sản xuất phần cứng cài thông tin về nhà thiết kế và các đại lý phân phối máy ảnh kỹ thuật số... Tuy nhiên JPEG2000 còn một số nhƣợc điểm nhƣ: 1. Chất lƣợng chƣa cao. 2. không có khả năng nén mất mát thông tin. 48 3. Khả năng phục hồi lỗi kém. Bảng 7. So sánh một số định dạng ảnh nén. 49 2.1.6. Định dạng ảnh PGM. Định dạng ảnh PGM (Portable Gray Map) là một định dạng ảnh xám, đƣợc tạo ra chủ yếu phục vụ cho mục đích học tập và nghiên cứu. Cấu trúc của định dạng dảnh PGM đƣợc cho dƣới đây:  Một số ID xác định dạng ảnh, với PGM thì sẽ bắt đầu bằng cặp ký tự P5.  Ký tự phân cách.  Chiều rộng.  Ký tự phân cách.  Chiều cao  Ký tự phân cách.  Giá trị xám nhất (maxVal), tối đa là 16 bit. Giá trị 0 đƣợc hiểu là màu đen, giá trị maxVal đƣợc hiểu là màu trắng  Ký tự xuống dòng.  Dữ liệu thật của ảnh: dữ liệu đƣợc ghi từ trên xuống dƣới, từ trái sang phải. Mỗi điểm ảnh đƣợc ghi bằng 1 hoặc 2 byte, tùy vào giá trị maxVal. Nếu maxVal nhỏ hơn 1 byte, thì mỗi điểm ảnh chỉ cần 1 byte, và ngƣợc lại. 50 2.2. CÁC PHÉP BIẾN ĐỔI ẢNH. Các phép biến đổi ảnh có thể chia làm hai loại chính, tƣơng ứng với hai loại thủy vân, đó là các phép biến đổi dựa vào không gian ảnh và các phép biến đổi trên miền tần số của ảnh. 2.2.1. Các toán tử không gian. Các toán tử không gian chủ yếu tác động trực tiếp vào miền không gian ảnh, dƣới đây trình bày một vài toán tử tiêu biểu: 2.2.1.1. Toán tử tuyến tính. Phần lớn các hệ thống xử lý ảnh có thể mô hình hoá nhƣ một hệ thống tuyến tính hai chiều. Giả sử x(m,n) và y(m,n) biểu diễn các tín hiệu vào và ra tƣơng ứng của hệ thống. Hệ thống hai chiều đƣợc biểu diễn bởi: y(m,n) = H[x(m,n)] Hệ thống này gọi là tuyến tính khi và chỉ khi: tổ hợp tuyến tính của 2 tín hiệu vào x1(m,n), x2(m,n) cũng tạo nên chính tổ hợp tuyến tính tƣơng ứng của đầu ra y1(m,n), y2(m,n), nghĩa là: với 2 hằng số bất kì a và ß, ta có: H[a x1(m,n) + ßx2(m,n)] = aH[x1(m,n)] + ßH[x2(m,n)] = ay1[(m,n)] + ßy2[(m,n)] Phƣơng trình trên gọi là chồng tuyến tính của 2 tín hiệu. Khi tín hiệu vào là hàm đenta Kronecker 2 chiều  (xung đơn vị) tại vị trí (m',n'), tín hiệu ra ở vị trí (m,n) đƣợc định nghĩa: h(m,n ; m',n') = H[d(m-m'; n-n')] Dấu ";" trong các công thức trên để phân biệt toạ độ vào và toạ độ ra. Hàm đenta d(m,n) có dạng: d(m,n) = 1 nếu m = n 0 nếu m  n 51 2.2.1.2. Toán tử nhân chập. Toán tử nhân chập đƣợc định nghĩa nhƣ sau: +Trƣờng hợp liên tục: g(x,y) = h(x,y)  f(x,y) = h x x y y f x y dx dy( ' , ' ) ( ' , ' ) ' '       + Trƣờng hợp rời rạc: y(m,n) = h(m,n)  x(m,n) = h m m n n x m n( ' , ' ) ( ' , ' )       52 2.2.1.3. Các kỹ thuật lọc số. Trong nhiều lĩnh vực kỹ thuật, nhiễu đóng vai trò chủ yếu gây nên những khó khăn khi ta cần phân tích một tín hiệu nào đó, cũng không loại trừ tín hiệu ảnh. Giữa một ảnh thực và ảnh số hoá thu nhận đƣợc khác nhau khá nhiều vì có nhiều quá trình can thiệp vào. Nguyên nhân là do nhiễu điện tử của máy thu hay chất lƣợng kém của bộ số hoá. Ta xem xét biết nhiễu thể hiện trên ảnh thế nào. Giả sử ảnh là một miền có mức xám đồng nhất. Nhƣ vậy các phần tử của ma trận biểu diễn ảnh sau quá trình số hoá phải có cùng giá trị. Nhƣng thực tế quan sát, ta thấy: gần giá trị trung bình của mức xám có những phần tử trội lên khá nhiều. Đó chính là hiện tƣợng nhiễu. Nhƣ vậy, nhiễu trong ảnh số đƣợc xem nhƣ sự dịch chuyển nhanh của tín hiệu thu nhận (tín hiệu ảnh I[m,n]) trên một khoảng cách ngắn. Xem xét một cách tƣơng đƣơng trong không gian tần số, nhiễu ứng với các thành phần tần số cao trong ảnh. Do vậy, ngƣời ta nghĩ đến việc biến đổi có tính đến ảnh hƣởng của các phần tử lân cận bằng cách lấy “tổ hợp “ các điểm lân cận này (trong không gian thực) hay lọc các thành phần tần số cao (trong không gian tần số). Đây chính là kỹ thuật lọc (filtering). Cơ sở lý thuyết của kỹ thuật lọc số là dựa trên tính dƣ thừa thông tin không gian: các pixel lân cận có thể có cùng hoặc gần cùng một số đặc tính. Hơn nữa, nhiễu có thể coi nhƣ sự đột biến của một điểm ảnh so với các điểm lân cận. Trong kỹ thuật này, ngƣời ta sử dụng một mặt nạ và di chuyển khắp ảnh gốc. Tuỳ theo cách tổ hợp điểm đang xét với các điểm lân cận mà ta có kỹ thuật lọc tuyến tính hay phi tuyến. Điểm ảnh chịu tác động của biến đổi là điểm ở tâm mặt nạ. 53 Lọc tuyến tính: Trong kỹ thuật lọc tuyến tính, ảnh thu đƣợc sẽ là tổng trọng số hay là trung bình trọng số các điểm lân cận với nhân cuộn hay mặt nạ. Nguyên tắc lọc theo tổng trọng số đƣợc minh hoạ qua hình 11. Thí dụ tâm mặt nạ là điểm P5, thì điểm P5 mới sẽ đƣợc tính theo công thức sau: P5 = P1K1 + P2K2 + P3K3 + P4K4 + P5K5 + P6K6 + P7K7 + P8K8 + P9K9 Hình 12. Lấy tổ hợp các điểm ảnh lân cận. Nói chung, ngƣời ta sử dụng nhiều kiểu mặt nạ khác nhau: 1 1 1 1 1 1 1 2 1 H1 = 1 9 1 1 1 H2 = 1 10 1 2 1 H3 = 1 16 2 4 2 1 1 1 1 1 1 1 2 1 Mặt nạ H1 là mặt nạ dùng để tính trung bình không trọng số (không ƣu tiên theo hƣớng nào cả). Mặt nạ H2 cho trọng số lớn nhất với điểm ở tâm. Còn mặt nạ H3 ƣu tiên cho 2 hƣớng x, y. Giả sử Ii là ảnh đang xét và If là ảnh thu đƣợc và cả 2 ảnh đều có cùng kích thƣớc p x p. Với mặt nạ trên, mỗi điểm ảnh thu đƣợc If(x,y) sẽ đƣợc tính bởi: If = 1 9 { Ii(x-1,y-1) + Ii(x-1,y) + Ii(x-1,y+1) + Ii(x,y-1) + Ii(x,y) + Ii(x,y+1) + Ii(x+1,y-1) + Ii(x,y) + Ii(x+1,y+1) } 54 = 1 9 ji   1 1 1 1 H1(i+1,j+1) Ii(x+i,y+j) Nếu H là bộ lọc kích thƣớc (n+1) x (n+1), n chẵn và tổng các hệ số là K, If sẽ đƣợc tính bởi: If = 1 K j n n i n n   / / / / 2 2 2 2 H1(i+n/2,j+n/2) Ii(x+i,y+j) Công thức trên chính là tích chập giữa mặt nạ H và ảnh gốc I: If = H  Ii. Chú ý rằng vừa rồi ta chƣa xét đến biên của ảnh khi sử dụng kỹ thuật lọc. Giả sử ta áp mặt nạ H vào điểm tại gốc toạ độ (0,0), rõ ràng là điều này không thể đƣợc. Do vậy, chỉ có thể hoặc lọc phần trong của ảnh từ n/2 đến p-n/2 và trong trƣờng hợp này ta thu đƣợc ảnh cỡ (p+1-n) x (p+1-n) hoặc là tạo thêm một nữa cỡ n/2 bằng cách sao. Ngoài các bộ lọc trên, ngƣời ta cũng hay dùng bộ lọc Gauss. Bộ lọc này có ƣu điểm là dễ cài đặt và cho chất lƣợng cao. Bộ lọc Gauss gồn tích chập của một ảnh If với mặt nạ Gauss G(x,y,): If = G  Ii với G(x,y,) = 1 2 2 2 2 2  exp( ) x y G là mặt nạ hình vuông mà các hệ số của nó là các phần tử rời rạc của phân bố Gauss. Vì mặt nạ có kích thƣớc (n+1) x (n+1) hữu hạn, còn đƣờng cong G định nghĩa trên toàn miền thực, do vậy ta cần chọn một khoảng hữu hạn. Thƣờng ngƣời ta chọn khoảng là 4(95%) hay 6 (99.9%). Ngƣời ta cũng chứng minh đƣợc rằng với mặt nạ N x N cần N2 phép nhân và N2- 1 phép cộng. Các phƣơng pháp lọc nói trên, nhìn chung làm giảm mức nhiễu trắng đi Nw lần, với Nw là số phần tử của mặt nạ và hạn chế nhoè sau khi lọc. 55 Lọc phi tuyến: Khác với lọc tuyến tính, kỹ thuật lọc phi tuyến coi một điểm ảnh kết quả không phải là tổ hợp tuyến tính của các điểm lân cận. Bộ lọc phi tuyến thƣờng dùng là lọc trung vị (median filtering) mang tên Tuckey. Trong trƣờng hợp một chiều, trung vị xa của một chuỗi n phần tử {xn} đƣợc định nghĩa: - Nếu n lẻ: có (n-1)/2 phần tử lớn hơn xa và (n-1)/2 nhỏ hơn hay bằng xa. - Nếu n chẵn: xa là trung bình cộng của 2 phần tử xi và xj  {xn} sao cho có (n- 2)/2 phần tử nhỏ hơn hay bằng xi và (n-2)/2 phần tử lớn hơn hay bằng xj. Thuật toán lọc trung vị đƣợc dùng để lọc nhiễu bằng cách trƣợt trên mặt phẳng ảnh, mỗi lần trƣợt di chuyển một cột điểm. Những phần tử trong cửa số đƣợc xem nhƣ là 1 chuỗi {xn} và điểm quan tâm đƣợc thay thế bởi giá trị xa của chuỗi. Thí dụ nhƣ chuỗi {1,2,9,5,4}, điểm trung tâm sẽ đƣợc thay thế bởi giá trị 4 dƣợc tính theo nguyên tắc ở trên. Rõ ràng trong ví dụ này gía trị 9 có thể là nhiễu nhọn trong dãy tăng dần. Lọc trung vị thƣờng sử dụng cửa sổ kích thƣớc 3. Tuy nhiên, nếu không có dấu hiệu quan trọng nào bị mất, kích thƣớc cửa sổ có thể tăng lên 5, 7, v...v và sẽ kết thúc khi quá trình lọc không làm thay đổi kết quả. Khái niệm lọc trung vị dễ dàng mở rộng cho trƣờng hợp hai chiều. Giả sử đầu vào là X(m,n) và đầu ra bộ lọc là Y(m,n). Lọc trung vị hai chiều đƣợc định nghĩa: Y(m,n) = Median(X(m-k,n-l) với k,l  [1, L] Lƣu ý rằng công thức Lc = (L+1)/2 còn gọi là bán kính bộ lọc. Do vậy, ta có cách viết khác tƣơng đƣơng (k,l)  (-r,r) với 2r + 1 = L. Khi đó trung vị của cửa sổ vuông n x n có thể đƣợc tính nhƣ những phần tử của chuỗi một chiều. Ta tiến hành sắp xếp dãy đó rồi thay thế phần tử tâm cửa sổ bằng trung vị của dãy vừa tìm đƣợc. Với lọc trung vị, số lƣợng tính toán khá lớn (có thể bằng số mũ của kích thƣớc cửa sổ lọc). Vì vậy, để khắc phục nhƣợc điểm này, ngƣời ta dùng một phƣơng pháp khác: lọc giả trung vị (Pseudo-Median Filter). Lọc giả trung vị có nhiều điểm giống nhƣ lọc trung vị. Dãy lấy ra không cần sắp xếp và giá trị gọi là trung vị lại đƣợc tính theo trung bình cộng của Max của min và min của max. Hai loại mặt nạ hay dùng là mặt nạ vuông và mặt nạ chữ thập. Thực tế, ngƣời ta thích loại mặt nạ vuông hơn vì nó không làm biến dạng ảnh mà lại hiệu quả. Tuy nhiên 56 trong lọc giả trung vị, ngƣời ta lại thấy dùng cửa sổ chữ thập cho kết quả khả quan hơn nhiều. 57 2.2.2. Các toán tử tần số. 2.2.2.1. Phép biến đổi Fourier. Biến đổi Fourier do nhà toán học Joseph Fourier (1768 - 1830) đƣa ra. Ông đã chứng minh rằng bất cứ một hàm số tuần hoàn nào cũng có thể biến đổi thành tổng vô hạn hoặc hữu hạn các hàm sin (hoặc cos). Do ảnh số chỉ là một phần của tín hiệu số, và bản chất tín hiệu ảnh số là tín hiệu rời rạc do quá trình lấy mẫu từ môi trƣờng, nên ta sử dụng biến đổi Fourier rời rạc (Discrete Fourier Transform - DFT) trong xử lý ảnh. Biến đổi Fourier cho một tín hiệu có thể đƣợc hình dung bằng hình vẽ sau: Hình 12. Biến đổi Fourier cho một tín hiệu. Khóa luận chỉ trình bày về phép biến đổi Fourier rời rạc với các tín hiệu hai chiều, tƣơng ứng là các ảnh số, các kiến thức chuyên sâu hơn có thể tìm đƣợc ở các tài liệu tham khảo. DFT hai chiều của một ảnh M x N : {u(m,n) } là một biến đổi tách đƣợc và đƣợc định nghĩa : v(k,l) = u m n n N m N ( , )      0 1 0 1 WN km WN ln 0 = l, k = N-1 và biến đổi ngƣợc: u(m,n) = 1 2 0 1 0 1 N v k l l N k N ( , )      WN -km WN -ln 0 = m, n = N-1 Cặp DFT đơn vị hai chiều đƣợc định nghĩa: v(k,l) = 1 0 1 0 1 N u m n n N m N ( , )      WN km WN ln 0 = l, k = N-1 u(m,n) = 1 0 1 0 1 N v k l l N k N ( , )      WN -km WN -ln 0 = m, n = N-1 Viết lại hai công thức đầu tiên, ta có: 58 v(k,l) = 1 0 1 0 1 N u m n n N m N ( , )      WN (km + ln) 0 = l, k = N-1 u(m,n) = 1 0 1 0 1 N v k l l N k N ( , )      WN -(km + ln) 0 = m, n = N-1 Ở đây, WN (km+ln) là ma trận ảnh cơ sở. Nhắc lại rằng ej = cos() +jsin() (công thức Ơle). Do vậy: WN (km+ln) = e -j2(km+ln)/N = cos(2(km+ln)/N) - j sin (2(km+ln)/N). Nhƣ vậy, các hàm cơ sở trong ma trận ảnh cơ sở của biến đổi Fourier là các hàm cosine và hàm sine. Theo tính toán trên, ta thấy biến đổi Fourrier biểu diễn ảnh trong không gian mới theo các hàm sin và cos. 59 2.2.2.2. Phép biến đổi Cosine rời rạc. Phép biến đổi Cosine rời rạc (Discrete Cosine Transform - DCT) là một phép biến đổi có nhiều ứng dụng trong nén ảnh, và đã đƣợc sử dụng trong định dạng ảnh JPEG. Phép biến đổi Cosin rời rạc (DCT) đƣợc Ahmed đƣa ra vào năm 1974. Kể từ đó đến nay nó đƣợc ứng dụng rất rộng rãi trong nhiều phƣơng thức mã hoá ảnh khác nhau nhờ hiệu suất gần nhƣ tối ƣu của nó đối với các ảnh có độ tƣơng quan cao giữa các điểm ảnh lân cận. Biến đổi Cosin rời rạc đƣợc sử dụng trong chuẩn ảnh nén JPEG và định dạng phim MPEG. Phép biến đổi Cosine một chiều: Phép biến đổi Cosin rời rạc một chiều đƣợc định nghĩa bởi: Trong đó:        ]1,1[ 0 0 2 1 Nk k khi khi k Khi dãy đầu vào x(n) là thực thì dãy các hệ số X(k) cũng là số thực. Tính toán trên trƣờng số thực giảm đi một nửa thời gian so với biến đổi Fourier. Phép biến đổi Cosin ngƣợc đƣợc định nghĩa bằng công thức: Với           00 0 2 1 kkhi kkhi k             2N 1)kΠ(2n1N 0n x(n)cos N k 2ε X(k) ( 8.10)      1 0 2 )12( )()( N k N nk Cos k kXn  60 2.2.2.3. Phép biến đổi sóng con rời rạc. Phép biến đổi sóng con rời rạc (Discrete Wavelet Transform - DWT) là một phép biến đổi mới và hứa hẹn có nhiều ứng dụng trong xử lý ảnh số. DWT đã đƣợc sử dụng trong định dạng ảnh JPEG2000. Không giống với biến đổi Fourier, vốn thích hợp với các tín hiệu ổn định, DWT thích hợp cho các tín hiệu không ổn định, có đáp ứng tần số thay đổi theo thời gian. Để giải quyết vấn đề của DFT, biến đổi Fourier thời gian ngắn (Short Time Fourier Transform - STFT) đã đƣợc đề xuất. Ý tƣởng của STFT là chia tín hiệu thành từng khoảng thời gian đủ nhỏ để có thể coi là ổn định trong từng khoảng. Dựa trên ý tƣởng đó thì DWT đã ra đời. Wavelet là các hàm đƣợc định nghĩa trong khoảng giá trị hữu hạn và có giá trị trung bình bằng 0. Các hàm này đƣợc lấy từ một hàm nguyên mẫu gọi là hàm wavelet mẹ (mother wavelet). Trong thực tế, DWT thuận và nghịch thƣờng đƣợc tính toán theo hai công thức: Trong đó, ψ(t) là hàm wavelet mẹ, và các giá trị a0 và b0 thƣờng đƣợc chọn là 2 và 1. Hàm wavelet mẹ phải thỏa mãn hai tính chất sau: Tích phân suy rộng trên toàn miền t của hàm ψ(t) phải bằng 0. Tích phân năng lƣợng trên toàn miền t của hàm ψ(t) phải hữu hạn Trong nhiều ứng dụng thực tế, DWT tỏ ra có ƣu thế hơn so với DFT. 61 2.3. CÁC THUẬT TOÁN THỦY VÂN TRÊN ẢNH. Các thuật toán thực hiện thủy vân hiện trên ảnh là tƣơng đối dễ dàng, và đã đƣợc nghiên cứu nhiều trong môn xử lý ảnh số. Các yêu cầu về tính thẩm mỹ đƣợc đề cao. Tất nhiên cũng cần có yêu cầu là khó sử dụng các công cụ xử lý ảnh để loại bỏ thủy vân. Nhƣ đã trình bày ở trên, các thuật toán thủy vân ẩn trên ảnh có thể chia ra làm hai loại chính, đó là thủy vân dựa vào biến đổi miền không gian ảnh, và biến đổi miền tần số ảnh. 2.3.1. Thuật toán giấu thủy vân vào các bit có trọng số thấp. Một ý tƣởng tự nhiên của thủy vân với ảnh số, cũng giấu nhƣ giấu tin, đó là sẽ sử dụng các bit có trọng số thấp (Least Significant Bit - LSB) để giấu thủy vân. Các bit có trọng số thấp đƣợc hiểu là các bit mà nếu thay đổi giá trị của chúng sẽ ít làm thay đổi đến chất lƣợng ảnh. Ví dụ, với ảnh bitmap 256 màu, màu của mỗi điểm ảnh đƣợc biểu diễn bằng 8 bit, nếu ta thay đổi giá trị bit thứ tám của mã màu, thì mã màu cũng chỉ thay đổi giá trị có 1 đơn vị, nên nhìn chung thì cả bức ảnh không bị ảnh hƣởng nhiều. Ta có thể minh họa thuật toán nhƣ sau: Xét thủy vân là chuỗi bit 0111. Xét bức ảnh là chuỗi bit: 11001101 11000001 11110000 11110010. Để nhúng thủy vân vào bức ảnh, ta sẽ chia bức ảnh thành các khối 8 bit, và đặt giá trị bit cuối cùng của khối bằng giá trị của bit thủy vân tƣơng ứng. Với minh họa trên, chúng ta có bức ảnh sau khi nhúng thủy vân là: 11001100 11000001 11110001 11110011 Để tách thủy vân, đơn giản ta chỉ làm ngƣợc lại quy trình trên, tức là tách ra các bit cuối của từng khối 8 bit, ta sẽ thu đƣợc thủy vân ban đầu. Muốn tăng tính an toàn của hệ thống, có thể nhúng liên tiếp thủy vân vào các khối 8 bit liền nhau, bởi thƣờng thì dung lƣợng bức ảnh sẽ lớn hơn nhiều lần so với độ dài của thủy vân. Ƣu điểm của thuật toán trên là đơn giản, và dung lƣợng giấu cao. 62 Tuy nhiên, nhƣợc điểm là do quá đơn giản nên rất dễ bị tấn công. Kẻ tấn công chỉ cần thay đổi ngẫu nhiên giá trị của các bit có trọng số thấp là thủy vân đã bị phá hủy. 63 2.3.2. Thuật toán thủy vân ghép nối. Thuật toán đƣợc trình bày bởi Bender và đồng nghiệp năm 1996. Xét một bức ảnh, ta sẽ chia bức ảnh thành hai tập con có số lƣợng phần tử bằng N, gọi là hai tập con A và B. Mỗi phần tử trong tập con A đƣợc cộng thêm một lƣợng d, ngƣợc lại mỗi phần tử trong tập B bị trừ đi một lƣợng d. Gọi E(A) và E(B) là các giá trị trung bình của tập A và tập B. Ta sẽ có E(A)≈E(B) ≈E(A u B) và E(A) – E(B) ≈ 0. Gọi a và b là 2 tập có n phần tử, lấy ngẫu nhiên trong A và B. 1 ( [ ] [i])S a i b N   Theo luật thống kê, ta sẽ có: E(S) = 2d nếu dữ liệu có thủy vân. E(S) = 0 nếu dữ liệu không có thủy vân. Nhƣ vậy, để kiểm tra xem dữ liệu có thủy vân hay không, ta sẽ sử dụng luật thống kê. Nếu E(S) lớn hơn một ngƣỡng nào đó thì có thể coi là dữ liệu có thủy vân. 64 2.3.3. Thuật toán thủy vân ảnh trên miền DCT. Khác với các phép thủy vân dựa trên biến đổi không gian ảnh, tƣơng đối dễ bị tấn công và phát hiện, năm 1995, Cox đã đƣa ra một mô hình khác, đó là nhúng thủy vân vào miền tần số. Hình 13. Mô hình nhúng thủy vân của Cox. Trong mô hình của Cox, một chuỗi các giá trị c0 = c0[1], c0[2], …, c0[n] đƣợc trích xuất từ ảnh. Các giá trị này đƣợc gọi là các giá trị mang, và chúng sẽ chứa thủy vân. Thủy vân là một chuỗi số thực w = w[1], w[2], …, w[n]. Theo Cox đề xuất, thủy vân có thể đƣợc nhúng theo một trong ba công thức: Trong đó tham số α đặc trƣng cho tính bền vững của thủy vân, và đƣợc thay đổi tùy từng bài toán cụ thể. Để kiểm tra thủy vân, ngƣời ta cũng phải dùng tới thống kê. Dựa trên mô hình của Cox, năm 1998, Burgett đã đề xuất một thuật toán thủy vân ảnh dựa vào biến đổi DCT với định dạng ảnh JPEG. Thuật toán của Burgett sẽ chia ảnh JPEG thành các khối (block) có kích thƣớc 8x8 điểm ảnh. Mỗi khối sẽ đƣợc biến đổi DCT. Thuật toán sẽ chọn ngẫu nhiên các khối để nhúng thủy vân. Thủy vân đƣợc nhúng trên mỗi khối bằng cách đổi chỗ một cặp hệ số của biến đổi DCT. 65 Năm 2002, GS.TSKH Nguyễn Xuân Huy có đề xuất một thuật toán thủy vân ảnh trên miền DCT nhƣ sau: 1/.Quá trình nhúng thủy vân: Chia ảnh có kích thƣớc m x n thành (m x n)/64 khối, mỗi khối có kích thƣớc 8x8. Biến đổi DCT cho từng khối. Xét một khối bất kỳ B sau khi biến đổi DCT thu đƣợc khối B‟, ta chọn hai hệ số bất kỳ trong miền tần số giữa của B‟, gọi hai hệ số là b‟(i, j) và b‟(p, q). Gọi a là tham số của thuật toán, thỏa mãn a = 2 (2t + 1) với t là số nguyên dƣơng. Tính d = ||b‟(i, j)| - |b‟(p, q)|| mod a. Bit si sẽ đƣợc nhúng sao cho thỏa mãn điều kiện sau: d ≥ 2t + 1 nếu si = 1. d < 2t + 1 nếu si = 0. Nếu d < 2t + 1 và si = 1, thì một trong hai hệ số DCT có giá trị tuyệt đối lớn hơn sẽ bị thay đổi theo công thức sau để thỏa mãn d ≥ 2t + 1: max(|b‟(i,j)|, |b‟(p,q)|) = max(|b‟(i,j)|, |b‟(p,q)|) + ([0,75 *a] - d) với phép toán [] là phép toán lấy phần nguyên. Hoặc cũng có thể thay đổi theo công thức sau: min(|b‟(i,j)|, |b‟(p,q)|) = min(|b‟(i,j)|, |b‟(p,q)|) - ([0,25 *a] + d) Tƣơng tự, nếu d ≥ 2t + 1 và si = 0, thì ta áp dụng hai công thức sau để thay đổi hệ số DCT: max(|b‟(i,j)|,|b‟(p,q)|) = max(|b‟(i,j)|,|b‟(p,q)|) - (d – [0,25*a]) hoặc: min(|b‟(i,j))|,|b‟(p,q)|) = min(|b‟(i,j))|,|b‟(p,q)|) + [1,25*a] – d 2/.Quá trình tách thủy vân: Đọc khối DCT từ ảnh chứa thủy vân và vị trí hai hệ số đã biến đổi, sau đó tính: d = ||b‟(i,j)|-|b‟(p,q)|| mod a Nếu d ≥ 2t + 1 thì gán si = 1, ngƣợc lại gán si = 0. 66 2.3.4. Thuật toán thủy vân ảnh trên miền DWT. Tƣơng tự nhƣ thuật toán thủy vân ảnh trên miền DCT, trong biến đổi DWT, thủy vân đƣợc nhúng vào các dải tần số cao nhất, theo công thức sau: Mô hình của biến đổi DWT đƣợc cho trong hình sau: Hình 14. Biến đổi DWT ba mức Năm 2004, hai tác giả Lê Tiến Thƣờng và Nguyễn Thanh Tuấn tại Đại học Bách khoa TP Hồ Chí Minh có đề xuất một giải pháp sử dụng DWT để nhúng thủy vân vào ảnh. Thuật toán đƣợc phát biểu nhƣ sau: thực hiện DWT cho ảnh. Một tập các hệ số lớn nhất có chiều dài bằng chiều dài watermark trong băng tần thích hợp đƣợc trích ra và cộng với watermark theo công thức: Cw = C + αW Quá trình tách thủy vân đƣợc thực hiện ngƣợc lại: W = (Cw‟ - C)/α Trong đó Cw‟ là các hệ số lớn nhất của ảnh. Do ảnh có thể bị tấn công nên có thể Cw ≠ Cw‟. 67 Khi tách đƣợc thủy vân, chúng ta sẽ so sánh nó với thủy vân gốc bằng hệ số tƣơng quan d: Giá trị của d nằm trong khoảng từ -1 tới 1, nếu d càng gần 1 thi càng có cơ sở xác nhận là ảnh có đƣợc nhúng thủy vân. Thuật toán cho kết quả tốt hơn so với thuật toán nhúng thủy vân trên miền DCT của Cox, đồng thời thủy vân cũng bền với các phép tấn công nén JPEG2000, lọc, và co dãn ảnh. 68 2.3.5. Thuật toán thủy vân sử dụng biến đổi Karhunen – Loeve. Giáo sƣ Wang Shuozhong (Vƣơng Thừa Trung) tại Đại học Thƣợng Hải có đề xuất một thuật toán thủy vân dựa vào biến đổi Karhunen – Loeve, hay còn gọi là phân tích các thành phần quan trọng (PCA). Thuật toán đƣợc phát biểu nhƣ sau: Xét một chuỗi các vector fk, với k = 1, 2, … K là các mẫu đƣợc lấy từ một quá trình ngẫu nhiên. fk có kích thƣớc Rx1. Biến đổi các thành phần quan trọng, hay biến đổi Karhunen – Loeve, đƣợc định nghĩa nhƣ sau: gk = Afk Trong đó A là ma trận chuyển kích thƣớc RxR, với mỗi cột là vector đặc trƣng (eigenvector) của ma trận thống kê CF đƣợc lấy từ quá trình biến đổi ảnh F. Các cột trong A đƣợc sắp xếp theo thứ tự giảm dần của trị riêng (eigenvalue). Xét một ảnh có kích thƣớc MxN, đƣợc chia thành K = I.J miền, mỗi miền sẽ là một ma trận 2 chiều có kích thƣớc PxQ, với P = M/I và Q = N/J. Các miền cũng có thể đƣợc tổ chức là nhƣ một mảng 1 chiều có kích thƣớc PxQ. Có rất nhiều phƣơng pháp chia ảnh thành các miền nhƣ vậy. Trong [33], GS Vƣơng đề xuất một phƣơng pháp đơn giản nhƣ sau: Nhƣ vậy, bức ảnh ban đầu của chúng ta bây giờ có thể xem nhƣ K mẫu đƣợc lấy từ một quá trình ngẫu nhiên R chiều. Nhƣ vậy, kỹ thuật PCA đƣợc giới thiệu ở trên đã có thể đƣợc sử dụng. Xét ảnh G, theo nhƣ quá trình phân tách ảnh thành các miền đã trình bày ở trên, ta có thể viết lại ảnh G dƣới dạng sau: 69 Sắp xếp lại G theo thứ tự giảm dần của trị riêng, trở thành q1, q2, …, qR. Trị riêng của từng khối qi chính là năng lƣợng của khối. Nhƣ vậy, khối q1 có nhiều năng lƣợng nhất, và sẽ ảnh hƣởng nhiều nhất tới ảnh. Nhƣ vậy, để tăng tính bền vững của thủy vân, thì chúng ta sẽ nhúng thủy vân vào các khối có hệ số nhỏ, trong khi để tăng tính ẩn thì chúng ta sẽ nhúng thủy vân vào các khối có hệ số lớn. 70 2.3.6. Thủy vân dễ vỡ. Thủy vân dễ vỡ (fragile watermark) là một dạng thủy vân đặc biệt, đƣợc sử dụng để bảo đảm tính toàn vẹn thông tin của ảnh số. Đặc điểm của thủy vân dễ vỡ là, chỉ cần ảnh bị thay đổi thì thủy vân sẽ bị phá hủy, do đó chống lại sự xuyên tạc nội dung của ảnh. Thuật toán thủy vân dễ vỡ đầu tiên đƣợc Yeung và Mintzer đƣa ra vào năm 1997. Thuật toán chỉ hoạt động trên các ảnh xám, với thủy vân là một chuỗi bit. Phía bên ngƣời nhận sẽ đọc từng điểm ảnh, trích xuất thủy vân và so nó với thủy vân đƣợc công bố. Nếu có sự khác biệt, thì độ xám của điểm ảnh sẽ đƣợc thay đổi tới khi hai thủy vân thu đƣợc là giống nhau. Thuật toán của Yeung và Mintzer làm việc và bảo toàn tính toàn vẹn dữ liệu cho từng điểm ảnh, cũng nhƣ hỗ trợ khả năng khôi phục ảnh gốc. Một thuật toán khác, đƣợc Wong Ping Wah đƣa ra năm 1998, kết hợp giữa thủy vân số và mật mã hóa công khai. Trong thuật toán của Wong, mức xám của LSB trong ảnh gốc sẽ đƣợc đặt bằng 0. Sau đó, ảnh gốc sẽ đƣợc chia thành các khối (block) có kích thƣớc bằng kích thƣớc thủy vân. Kích thƣớc của ảnh cùng với mỗi khối đó sẽ đƣợc băm, và kết quả thu đƣợc sẽ đƣợc XOR với thủy vân. Kết quả của phép XOR sẽ đƣợc mã hóa bằng hệ mã hóa RSA, sau đó nhúng vào LSB của ảnh gốc. Phía bên nhận, sẽ làm công việc ngƣợc lại. Đầu tiên, ảnh cũng sẽ lại đƣợc chia thành các khối, và thông tin nhúng trong LSB sẽ đƣợc thu hồi và giải mã cũng bằng hệ mã hóa RSA. Cùng với đó, bên nhận cũng sẽ băm các khối của ảnh thu đƣợc cùng kích thƣớc ảnh. Hai kết quả đó đƣợc XOR với nhau để thu lại thủy vân, và so sánh thủy vân thu đƣợc với thủy vân gốc đƣợc lƣu trong cơ sở dữ liệu của bên gửi. Cả hai thuật toán trên đều có nhƣợc điểm, là không tận dụng sự tƣơng quan giữa các khối ảnh