Thủy vân thuận nghịch dựa trên dự báo, sắp xếp phương sai và độ lệch tâm - Nguyễn Kim Sao

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 135 THỦY VÂN THUẬN NGHỊCH DỰA TRÊN DỰ BÁO, SẮP XẾP PHƯƠNG SAI VÀ ĐỘ LỆCH TÂM Nguyễn Kim Sao, Cao Thị Luyên* Tóm tắt: Bài báo đề xuất một lược đồ thủy vân thuận nghịch dựa trên mở rộng hiệu và không sử dụng bản đồ định vị bằng cách sử dụng phương pháp sai số dự báo để nhúng dữ liệu vào ảnh số. Chúng tôi đề xuất thuật toán sắp xếp dựa trên phương sai địa phương và độ lệch giữa tâm ngữ cảnh dự báo và tâm miền điểm ảnh. Kết quả thử nghiệm cho thấy lược đồ được đề xuất cho chất lượng ảnh thủy vân tốt hơn và khả năng nhúng cao hơn các lược đồ liên quan. Từ khóa: Thủy vân thuận nghịch, Sai số dự báo, Mở rộng hiệu. 1. MỞ ĐẦU Thủy vân được xem như một trong những giải pháp hữu hiệu cho bài toán bảo vệ bản quyền, xác thực nội dung và phòng chống giả mạo. Thủy vân là kỹ thuật nhúng thông tin quan trọng (thủy vân- watermark) vào một đối tượng đa phương tiện (ảnh số, tệp âm thanh, tệp video,...) nhằm bảo vệ đối tượng này khỏi sự truy cập bất hợp pháp trước khi nó được phân phối trên môi trường mạng [1]. Dấu thủy vân sau đó có thể được khôi phục, làm bằng chứng xác định bản quyền tác giả hoặc kiểm định đối tượng có bị biến đổi trái phép hay có phải là sản phẩm giả mạo. Trong một số ứng dụng như y tế, quân sự, an ninh – quốc phòng, ảnh gốc cần được khôi phục lại nguyên vẹn bên cạnh việc phục hồi thủy vân gốc là yêu cầu bắt buộc. Loại thủy vân có tính chất trên được gọi là thủy vân thuận nghịch. Mô hình thủy vân thuận nghịch được mô tả như hình sau: Hình 1. Mô hình thủy vân thuận nghịch. Thủy vân thuận nghịch được nghiên cứu nhiều gần đây bởi nó có nhiều ứng dụng cũng như có hàm lượng toán học cao. Năm 2002, J. Fridrich [4] là người đầu tiên ra phương pháp thuận nghịch dựa vào phương pháp nén bảo toàn bằng cáchnén các bít thấp của điểm ảnh nhằmtạo ra các khoảng trốngđể nhúng thủy vân theo kỹ thuật chèn bít thấp. Khoảng trống thu được chính là khả năng nhúng. Như vậy, khả năng nhúng của các lược đồ thủy vân phụ thuộc nhiều vào phương pháp nén. Trong thực tế, các bít thấp của dữ liệu hình ảnh và âm thanh thường có xu hướng ngẫu nhiên nên tỉ lệ nén không cao. Do đó, khả năng nhúng tin của phương pháp này là thấp. Một hướng tiếp cận thuận nghịch khác là dựa vào đặc trưng nén Jpeg [3]. Các lược đồ này nhúng 1 đến 2 bít thủy vân trên 9 đường chéo song song với đường chéo chính của các khối DTCLT. Song, các lược đồ thủy thuận nghịch sử dụng đặc trưng nén jpeg có khả năng nhúng chưacao. Năm 2006, Ni [13] đề xuất phương pháp thủy vân thuận nghịch dựa trên phép dịch chuyển histogram. Ý Công nghệ thông tin N. K. Sao, C. T. Luyên, “Thủy vân thuận nghịch sắp xếp phương sai và độ lệch tâm.” 136 tưởng là chọn cặp điểm (peak, zero) trên biểu đồ histogram, peak, zero lần lượt là giá trị điểm ảnh có tần xuất cực đại và cực tiểu (giả sử zero < peak) để tạo ra các khoảng trống để nhúng tin. Tiếp theo, dịch chuyển các điểm ảnh có giá trị trong khoảng [zero+1, peak-1] sang bên trái bằng cách trừ 1. Khi đó, tạo một khoảng trống tại peak-1 (khoảng trống tức là h(x)=0). Số bít nhúng được là h(peak). Ưu điểm của phương pháp này là độ biến đổi ảnh ít (tối đa một đơn vị) nên chất lượng ảnh tốt. Tuy nhiên, khả năng nhúng chưa thực sự cao. Cho đến nay, phương pháp thuận nghịch được đánh giá là hiệu quả phải kể đến là phương pháp mở rộng hiệu do Tian[5] đề xuất. Theo Tian, đầu tiên ảnh gốc thành được phân hoạch thành các cặp giá trị điểm ảnh kí hiệu là (x,y). Mỗi cặp (x,y) sẽ được nhúng một bít trên hiệu h =x-y, nếu cặp điểm ảnh này khả mở. [2, 6, 10, 12] mở rộng Tian bằng cách tạo ra nhiều hiệu hay các lược đồ giảm kích thước của bản đồ để nâng cao khả năng nhúng. Thủy vân thuận nghịch dựa theo phương pháp dự báo do Thodi [9] đề xuất và được nhiều nhà nghiên cứu và mở rộng [8, 11, 14] bởi khả năng nhúng cao mà chất lượng ảnh thủy vân tốt. Các hướng nghiên cứu mở rộng như phương pháp này là: Giảm thiểu độ biến đổi nhằm tăng cường chất lượng ảnh thủy vân, nâng cao độ chính xác của phương pháp dự báo, kết hợp phương pháp dự báo với các phương pháp khác. Với phương pháp nhúng tin dựa trên mở rộng hiệu, việc lưu trữ bản đồ định vị không những làm giảm mà còn khó kiểm soát khả năng nhúng. Chính vì vậy, nhiều công trình sau này đều tìm cách giảm hoặc loại bỏ bản đồ ra khỏi lược đồ thủy vân. Sachnev và cộng sự [14] đã sử dụng nhận xét về sự tương đồng giữa phương sai địa phương nhỏ và khả năng khả mở của điểm ảnh để xây dựng lược đồ nhúng mà không cần đến bản đồ định vị. Tuy nhiên, ở lược đồ của Sachnev mới chỉ quan tâm đến phương sai địa phương mà chưa xem xét đến điểm ảnh đang xét có nằm giữa miền điểm ảnh hay không, bởi nếu điểm ảnh nằm gần biên của ảnh (giá trị 0 hoặc 255) việc điểm ảnh sau khi nhúng thủy vân có thể tràn ra khỏi miền điểm ảnh. Phương pháp đề xuất cải tiến phương pháp sắp xếp dựa trên phương sai địa phương và độ lệch tâm nhằm hội tụ những điểm khả mở về đầu dãy, loại bỏ bản đồ ra khỏi lược đồ thủy vân. Bằng thực nghiệm đã chứng tỏ phương pháp đề xuất có khả năng nhúng tin cao hơn so với các phương pháp của Sachnev và cộng sự (SKNSS) [14] và phương pháp gần đây của Manoj Kumar and Smita Agrawal (MS) [8]. Nội dung tiếp theo của bài báo được tổ chức như sau: mục 2 giới thiệu các công trình liên quan. Mục 3 trình bày phương pháp đề xuất. Mục 4 đánh giá so sánh phương pháp đề xuất với các phương pháp liên quan, cuối cùng là kết luận ở mục 5. 2. NHỮNG CÔNG TRÌNH LIÊN QUAN 2.1. Phương pháp mở rộng hiệu của J.Tian Phương pháp mở rộng hiệu do J.Tian đề xuất,theo phương pháp này, một bức ảnh được chia thành các cặp điểm ảnh rời nhau. Từ các giá trị hiệu và trung bình cộng ℎ để xác định xem cặp điểm vừa xét có nhúng tin được hay không, với các cặp điểm nhúng tin được theo phương pháp mở rộng hiệu, ta gọi chúng là cặp điểm khả mở, với những cặp điểm không nhúng tin được theo phương pháp mở rộng hiệu song có thể nhúng tin được theo phương pháp chèn bít thấp, ta gọi chúng là Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 137 cặp khả biến, còn lại ta gọi chúng là cặp điểm không khả mở. Dưới đây là các khái niệm và phương thức nhúng cũng như khôi phục thông tin: 2.1.1. Khái niệm khả mở, khả biến Cặp điểm ảnh (, ) (, ∈ [0,255]) được gọi là khả mở nếu sau khi giấu một bít ∈ {0,1} vào (, ) theo phương pháp mở rộng hiệu mà thu được cặp điểm ảnh giấu tin (′, ′) cũng nằm trong miền giá trị điểm ảnh (tức là (, ∈ [0,255])). Cặp điểm ảnh (, ) được gọi là khả biến nếu sau khi giấu một bít ∈ {0,1} vào (, ) theo phương pháp chèn bít thấp thì cặp điểm ảnh sau khi giấu thu được (′, ′) cũng nằm trong miền giá trị điểm ảnh. 2.1.2. Khái niệm bản đồ định vị Bản đồ định vị là dãy bít nhị phân nhằm phân biệt điểm (cặp) khả mở với những cặp không khả mở. Cặp điểm ảnh khả mở tương ứng là bít 1 ngược lại là bít 0. Độ dài của bản đồ chính bằng một nửa kích thước của ảnh. Bản đồ được nén lại và được nhúng vào trong ảnh phục vụ quá trình khôi phục. 2.1.3. Giấu tin theo phương pháp mở rộng hiệu Bít ∈ {0,1} được nhúng vào cặp(, ) nếu cặp này khả mở như sau: - Tính: ℎ = − ; = . - Giấu bít b bằng cách mở rộng h: ℎ = 2ℎ + . - Xác định cặp điểm ảnh chứa tin (, ): = + ; = − . 2.1.4. Giấu tin bằng phương pháp chèn bít thấp - Để nhúng bít vào (, ) khả biến thì đầu tiên tính ℎ = − , = ; Sau đó, lưu lại bít thấp của ℎ: (ℎ) = ℎ 2. Cuối cùng, bít được nhúng vào cặp (, ) nếu cặp này khả biến bằng cách chèn vào bít thấp của ℎ: ℎ = 2 + - Cặp điểm ảnh chứa tin (’, ’) được xác định như sau: - ′ = + ; = − 2.1.5. Trích tin và khôi phục ảnh gốc Từ cặp điểm ảnh (, ′) có thể trích được bít và khôi phục lại được (, ) theo công thức sau: ℎ = − ; = ℎ 2, ℎ = , = . Giá trị ảnh gốc được khôi phục bởi: = + , = − . 2.2. Phương pháp SKNSS Đầu tiên, Sachnev và cộng sự [14] tiến dành dự báo theo phương pháp hình thoi, điểm ảnh , được dự báo bởi 4 điểm ảnh lân cận ,; ,; ,; , tạo thành hình thoi. , , , , , Hình 2. Dự báo hình thoi. Công nghệ thông tin N. K. Sao, C. T. Luyên, “Thủy vân thuận nghịch sắp xếp phương sai và độ lệch tâm.” 138 Sau đó, tác giả tính phương sai địa phương cho mỗi điểm ảnh trong ngữ cảnh dự báo: , = ∑ − ̅ (1) với = , − ,, = , − ,, = , − ,, = |, − ,| và ̅ = ∑ Sachvev và cộng sự tiến hành sắp xếpdãy ,theo theo chiều tăng dần. Với mỗi điểm, xác định tính chất khả mở của chúng. Thực hiện nhúng tin lần lượt trên các điểm ảnh có phương sai địa phương nhỏ hơn, đến khi hết tin nhúng hoặc khi gặp điểm không khả mở đầu tiên. Mục đích của việc sắp thếp sai địa phương là mối liên hệ giữa phương nhỏ và khả năng khả mở của điểm ảnh cao hơn. 2.3. Phương pháp MS (Manoj Kumar and Smita Agrawal) Phương pháp MS thực hiện dựa báo cho điểm , dựa trên hai điểm lân cận của , và , bằng cách tính trung bình cộng của chúng. Bản đồ được xây dựng cũng tương tự như của J.Tian, những điểm khả mở sẽ được đánh dấu là “1”, điểm không khả mở là “0”, sau đó, dãy được nén lại và được đưa vào dãy bít nhúng. MS thực hiện nhúng trước tiên trên các dãy chẵn, sau khi nhúng hết dãy chẵn sẽ tiến hành nhúng trên dãy lẻ. Tuy nhiên, tác giả không nêu rõ làm sao phân biệt được một điểm là khả mở khi chưa thể trích được bản đồ. 3. PHƯƠNG PHÁP ĐỀ XUẤT Lược đồ SKNSS chỉ quan tâm đến phương sai địa phương, điều đó chỉ thể hiện được ngữ cảnh dự báo của điểm xét có phẳng hay không, tuy nhiên, ngữ cảnh phẳng chưa đảm bảo được điểm ảnh là khả mở. Trong phương pháp đề xuất, chúng tôi quan tâm thêm một yếu tố nữa đó là độ lệch tâm nhỏ, tức là vùng ngữ cảnh càng gần tâm miền điểm ảnh (127) thì khả năng điểm ảnh đó khả mở càng cao. 3.1. Thuật toán nhúng thủy vân Để đơn giản trong trình bày, chúng tôi chỉ xem xét trên các điểm chấm () như hình dưới đây Thực hiện nhúng thủy vân trên ảnh có kích thước × . Bước 1: Bức ảnh được phân loại theo hai dạng điểm, các điểm chấm () và các điểm gạch (). Lượt đầu, thực hiện nhúng thủy vân trên lượt chấm, lượt thứ 2 sẽ nhúng thủy vân trên lượt gạch. Thực hiện nhúng trên các phần tử {(, )|1 < < ; 1 < < }                                                                 Hình 3. Phân loại điểm ảnh. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 139 Bước 2: Xác định ngữ cảnh cho điểm , theo phương pháp dự báo hình thoi như phần 2.2. Bước 3: Xác định phương sai địa phương , theo công thức (1) và độ lệch tâm miền điểm ảnh và tâm ngữ cảnh , − 127 cho các điểm ,, với , = ,,,, . Bước 4: Sắp xếp , theo thứ tự tăng dần, với những điểm , bằng nhau, sắp xếp ưu tiên độ lệch tâm , − 127. Bước 5: Kiểm tra điểm , không khả mở, đánh dấu những điểm này (bằng thứ tự , hoặc tọa độ (, )). Bước 6: Xác định dãy bit nhúng: B=H+W - H: phần lưu thông tin về điểm khả mở cuối cùng - W: các bít thủy vân Bước 7: Nhúng dữ liệu: - Dự báo điểm ảnh ,: , = ,,,, - Tính sai số dự báo , = , − , - Nhúng bít trên sai số dự báo: ′, = 2, + - Giá trị điểm ảnh sau khi nhúng: , = , + , 3.2. Thuật toán trích thủy vân và khôi phục ảnh gốc Thực hiện khôi phục dấu thủy vân và ảnh I trên ảnh được thủy vân ′ có kích thước × . Bước 1: Chia ảnh thành 2 phần gồm các điểm chấm () và các điểm gạch () giống như thuật toán nhúng. Thực hiện trích riêng biệt các điểm gạch và sau đó là các điểm chấm. Bước 2: Xác định phương sai địa phương , và độ lệch tâm của miền điểm ảnh và ngữ cảnh , − 127 cho các điểm ′,. Bước 3: Sắp xếp ,, tại các điểm , trùng nhau, sắp xếp ưu tiên độ lệch tâm , − 127 theo thứ tự tăng dần. Bước 4: Khôi phục thủy vân và ảnh gốc: - Dự báo điểm ảnh ′,: , = , , , , - Tính sai số dự báo ′, = ′, − , - Trích bít: = , 2 - Tính sai số ban đầu: , = , 2 - Khôi phục giá trị ảnh gốc , = , + 4. THỬ NGHIỆM VÀ SO SÁNH Để minh họa các kết quả phân tích, chúng tôi tiến hành thử nghiệm trên bộ ảnh mẫu trong [16]. Kết quả thử nghiệm cho thấy, phương pháp đề xuất có khả năng nhúng cao hơn và chất lượng cũng ảnh được cải thiện. Chương trình viết bằng ngôn ngữ MatLab R2012a và chạy trên máy tính Lenovo Ideapad S410p. 140 4.1 xuât và các phương pháp liên quan đư B STT phương pháp SKNSS và 4.2 . So sánh kh K ảng 1. 1 2 3 4 5 6 Từ . So sánh v ết qu b N. K. Sao, C. T. Luyên ả K Ả nghi ảng 1 cho th th hả nh th a b c d e f Tổng ử năng nhúng tin ử ệm ề ả năng nhúng tin nghi ch a d ệ ấ ất lư B m đ y, phương pháp đ ợ ảng Ảnh b d Hình 4. ể MS. ng 2. a c , “Th đánh giá v c SKNSS ảnh So sánh ch ủy vân thuận nghịch sắp xếp ph ủa phương pháp SKNSS, MS và phương SKNSS 62.4123 55.3628 62.0236 60.2497 3725 3427 4091 1878 4271 17866 Các ợ 474 ả ề c th ề ất l b e nh th khả ể Kh xu ư 32.6538 33.1306 32.2624 29.7849 ử năng nhúng tin c hi ả ất cho ợng ảnh MS nghi ện năng nhúng tin ở b MS kh ệm ảng 1 dư ả củ Đ 62.4504 55.0957 62.0511 60.4034 . 400 300 450 100 500 1755 năng nhúng tin cao hơn các a phương pháp SKNSS, MS ề 5 và phương pháp đ xu ương sai và đ ủ ới đây. ất Công ngh c f a phương pháp đ Đ pháp đ ề ệ thông tin ộ lệch tâm xu ề ất 4970 5325 5337 2965 1016 5110 24723 ề xu xu .” ề ất. ất. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 141 e 67.9223 35.6073 67.8048 f 61.5991 32.2170 61.4941 Bảng trên cho thấy chất lượng ảnh của phương pháp đề xuất tương đương với phương pháp SKNSS và lớn hơn nhiều so với phương pháp MS. 5. KẾT LUẬN Thủy vân thuận nghịch cho phép khôi phục nguyên vẹn ảnh gốc bên cạnh việc phục hồi thủy vân ngày càng trở lên phổ biến bởi nó được ứng dụng trong nhiều lĩnh vực quan trọng như quân sự, an ninh, y tế... Một trong những phương pháp hiệu quả đã đang và sẽ được mở rộng là phương pháp rộng hiệu. Hai hướng chính nghiên cứu chính là cải tiến bản đồ và tăng số cặp khả mở nâng cao khả năng nhúng cũng như tăng cường chất lượng ảnh thủy vân. Bài báo này đề xuất một phương pháp thủy vân thuận nghịch không sử dụng bản đồ định vị dựa trên sự sắp xếp phương sai địa phương và độ lệch tâm miền điểm ảnh của phương sai địa phương. Thực nghiệm cho thấy, phương pháp đề không chỉ cho chất lượng ảnh tốt và còn có khả năng nhúng cao hơn các lược đồ liên quan. TÀI LIỆU THAM KHẢO [1]. Khan, A. Siddia, S. Munib and S.A. Malik, “A recent survey of reversible watermarking techniques”, Elsevier, 2014. [2]. M. Alattar, “Reversible Watermarking Using the Difference Expansion of A Generalized Integer”, IEEE transactions on image processing, vol 13, pp 1147–1156,2004. [3]. C.Chang, C.C. Lin, C.S.Tseng and W.L.Tai, “Reversible hiding in DCT-based compressed images”, Information Sciences, Vol.177, pp.2768-2786, 2007. [4]. J. Fridrich, M. Goljan and R.Du, “Lossless data embedding--new paradigm in digital watermarking”, EURASIP Journal on Advances in Signal Processing, 2002. [5]. J. Tian, “Reversible data embedding using a difference expansion”, IEEE Trans. Circuits Syst. Video Technol, pp. 890–896, 2003. [6]. K. Y. Mohammad and A.J.Ahmed, “Reversible Watermarking Using Modifiled Difference Expansion”, International Journal of Computing & Information Sciences, Vol.4, No.3, pp.134-142, 2006. [7]. M. Khodaei, K.Faez, “Reversible Data Hiding By Using Modified Difference Expansion”. 2nd International Confference on Signal Processing Systems, pp.31-34, 2010. [8]. M. Kumar and S. Agrawal, "Reversible data hiding based on prediction error expansion using adjacent pixels", Security and Communication Networks, Vol. 9, pp3703-3712, 2016. [9]. Thodi DM, Rodriguez JJ, “Expansion embedding techniques for reversible watermarking”, IEEE transactions on image processing, vol 16, pp 721– 730,2007. [10]. S. Weng, C.C. Chu, N.Cai and R. Zhan, “Invariability of mean value based reversible watermarking”, Jounal of information Hiding and Multimedia Signal Processing, vol 4, 2013. Công nghệ thông tin N. K. Sao, C. T. Luyên, “Thủy vân thuận nghịch sắp xếp phương sai và độ lệch tâm.” 142 [11]. X. Li, B. Yang and T. Zeng, “Efficient ReversibleWatermarking Based on Adaptive Prediction-Error Expansion and Pixel Selection”, IEEE Trans, Vol. 20, No. 12, 2011. [12]. X. Wang, X. Li, Bin Yang, and Zongming Guo, “Efficient Generalized Integer Transform for Reversible Watermarking”, IEEE signal processing letters, vol. 17, 2010. [13]. Z. Ni, Y. Shi, N. Ansari, and W. Su, “Reversible Data Hiding”, IEEE Transactions on Circuits and System for Video Technology, Vol. 16, No. 3, 2006. [14]. V. Sachnev and H. Kim, "Reversble watermarking algorithm using sorting and prediction", Vol. 19, No. 7, 2009. [15]. Taubman, David S. "Image compression fundamentals, standards and practice." JPEG-2000 (2002). [16]. Test images ABSTRACT A REVERSIBLE-WATERMARKING METHOD BASED ON PREDICTION, SORTING VARIANCE AND CENTRE DIFFERENCE In the article, a reversible-watermarking method based on differrent expansion without using location map is proposed. This algorithm embed data into digital image by using prediction errors. A sorting technique which is based on local variance and difference between centre of prediction context and centre of image value range is proposed. The experiment result indicates clearly that the proposed scheme can embed more data with less distortion than the related schemes. Keywords: Reversible watermarking, Prediction error, Difference expansion. Nhận bài ngày 15 tháng 08 năm 2017 Hoàn thiện ngày 26 tháng 11 năm 2017 Chấp nhận đăng ngày 28 tháng 11 năm 2017 Địa chỉ: Khoa Công nghệ thông tin, Trường Đại học Giao thông Vận tải. * Email: caoluyengt@gmail.com.