Tài liệu Nghiên cứu một số phương pháp phát hiện giả mạo trên dữ liệu đa phương tiện [tt]

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN ĐĂNG HIÊN NGHIÊN CỨU MỘT SỐ PHƢƠNG PHÁP PHÁT HIỆN GIẢ MẠO TRÊN DỮ LIỆU ĐA PHƢƠNG TIỆN Chuyên ngành: Hệ thống thông tin Mã số: 62 48 01 04 TÓM TẮT LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN Hà Nội – 2015 Công trình đƣợc hoàn thành tại: Trƣờng Đại học Công nghệ, Đại học Quốc gia Hà Nội Ngƣời hƣớng dẫn khoa học: PGS. TS. Phạm Văn Ất PGS. TS. Trịnh Nhật Tiến Phản biện: .................................................................................................. ............................................................................................. Phản biện: .................................................................................................. ............................................................................................. Phản biện: .................................................................................................. ............................................................................................. Luận án sẽ đƣợc bảo vệ trƣớc Hội đồng cấp Đại học Quốc gia chấm luận án tiến sĩ họp tại .................................................................................................................. vào hồi giờ ngày tháng năm Có thể tìm hiểu luận án tại: - Thƣ viện Quốc gia Việt Nam - Trung tâm Thông tin - Thƣ viện, Đại học Quốc gia Hà Nội MỤC LỤC MỤC LỤC.................................................................................................................................................... 1 PHẦN MỞ ĐẦU .......................................................................................................................................... 1 MỤC TIÊU, PHẠM VI NGHIÊN CỨU ........................................................................................................ 1 NHỮNG ĐÓNG GÓP CỦA LUẬN ÁN ........................................................................................................ 1 TỔ CHỨC CỦA LUẬN ÁN ....................................................................................................................... 2 CHƢƠNG 1. TỔNG QUAN VỀ ẢNH GIẢ MẠO, PHÕNG CHỐNG VÀ PHÁT HIỆN GIẢ MẠO ẢNH, CÁC PHÉP BIẾN ĐỔI MA TRẬN.......... ..................................................................................................... 4 1.1 GIỚI THIỆU CHUNG................................................................................................................... 4 1.2 GIỚI THIỆU VÀ DẠNG ẢNH GIẢ MẠO .................................................................................... 4 1.2.1 Giới thiệu ......................................................................................................................... 4 1.2.2 Một số dạng ảnh giả mạo .................................................................................................. 4 1.3 PHƢƠNG PHÁP PHÒNG CHỐNG VÀ PHÁT HIỆN ẢNH GIẢ MẠO ......................................... 4 1.3.1 Phƣơng pháp chủ động ..................................................................................................... 4 1.3.1.1 Giới thiệu và phân loại thủy vân ................................................................................... 4 1.3.1.2 Tính chất của lƣợc đồ thủy vân ..................................................................................... 5 1.3.1.3 Ứng dụng của thủy vân ................................................................................................ 5 1.3.2 Phƣơng pháp thụ động ...................................................................................................... 5 1.4 MỘT SỐ PHÉP BIẾN ĐỔI MA TRẬN.......................................................................................... 5 1.5 KẾT LUẬN CHƢƠNG 1 .............................................................................................................. 5 CHƢƠNG 2. PHÕNG CHỐNG GIẢ MẠO ẢNH BẰNG KỸ THUẬT THỦY VÂN .............................. 6 2.1 KỸ THUẬT THỦY VÂN VÀ PHÒNG CHỐNG GIẢ MẠO ẢNH ................................................. 6 2.2 ĐỀ XUẤT THUẬT TOÁN ĐIỀU CHỈNH CỘNG GIẢI BÀI TOÁN NMF VÀ XÂY DỰNG LƢỢC ĐỒ THỦY VÂN ............................................................................................................................ 6 2.2.1 Điều chỉnh một phần tử của W .......................................................................................... 6 2.2.2 Điều chỉnh một phần tử của H........................................................................................... 7 2.2.3 Thuật toán đề xuất (Ký hiệu aNMF) .................................................................................. 7 2.2.3.1 Điều chỉnh ma trận W và H .......................................................................................... 7 2.2.3.2 Thuật toán aNMF giải bài toán NMF ............................................................................ 8 2.2.4 Xây dựng lƣợc đồ thủy vân sử thuật toán aNMF ............................................................... 8 2.2.4.1 Thuật toán nhúng thủy vân ........................................................................................... 8 2.2.4.2 Thuật toán trích thủy vân .............................................................................................. 8 2.3 ĐỀ XUẤT LƢỢC ĐỒ THỦY VÂN SỬ DỤNG PHÂN TÍCH QR .................................................. 9 2.3.1 Đề xuất lƣợc đồ thủy vân sử dụng phân tích QR ................................................................ 9 2.3.1.1 Lƣợc đồ thủy vân QR-1 ................................................................................................ 9 2.3.1.2 Lƣợc đồ thủy vân QR-N ..............................................................................................10 2.4 KẾT LUẬN CHƢƠNG 2 ............................................................................................................ 10 CHƢƠNG 3. PHÁT HIỆN ẢNH GIẢ MẠO DẠNG CẮT/DÁN ................................................................. 11 3.1 ẢNH GIẢ MẠO DẠNG CẮT/DÁN VÀ MỘT SỐ PHƢƠNG PHÁP PHÁT HIỆN ....................... 11 3.1.1 Ảnh giả mạo dạng cắt/dán ................................................................................................11 3.1.2 Phân loại các phƣơng pháp phát hiện ...............................................................................11 3.1.2.1 Phƣơng pháp đối sánh chính xác .................................................................................11 3.1.2.2 Phƣơng pháp đối sánh bền vững ..................................................................................11 3.2 ĐỀ XUẤT PHƢƠNG PHÁP DỰA TRÊN PHÉP BIẾN ĐỔI DCT ............................................... 11 3.2.1 Thuật toán phát hiện ........................................................................................................11 3.3 ĐỀ XUẤT PHÉP BIẾN ĐỔI DWT VÀ XÂY DỰNG PHƢƠNG PHÁP PHÁT HIỆN .................. 14 3.3.1 Đề xuất xây dựng phép biến đổi DWT động .....................................................................14 3.3.2 Ứng dụng xây dựng thuật toán phát hiện ..........................................................................15 3.4 PHƢƠNG PHÁP DỰA TRÊN PHÉP THỪA SỐ HÓA MA TRẬN KHÔNG ÂM NMF ............... 17 3.5 KẾT LUẬN CHƢƠNG 3 ............................................................................................................ 18 CHƢƠNG 4. PHÁT HIỆN ẢNH GIẢ MẠO DẠNG GHÉP ẢNH............................................................... 19 4.1 PHÁT HIỆN ẢNH GIẢ MẠO DẠNG GHÉP ẢNH DỰA TRÊN TÍNH CHẤT CỦA PHÉP LẤY MẪU LẠI TRÊN ẢNH ................................................................................................................ 19 4.1.1 Tính chất của phép lấy mẫu tăng trên ảnh .........................................................................19 4.1.1.1 Lấy mẫu lại tín hiệu.....................................................................................................19 4.1.1.2 Lấy mẫu lại trên ảnh ....................................................................................................19 4.1.1.3 Tính chất của phép lấy mẫu tăng trên ảnh ....................................................................19 4.1.2 Đề xuất phƣơng pháp phát hiện ảnh giả mạo bằng phép biến đổi hiệu ..............................19 4.1.2.1 Xây dựng phép biến đổi hiệu trên ma trận điểm ảnh ....................................................19 4.1.2.2 Đề xuát phƣơng pháp phát hiện ảnh giả mạo dựa trên phép biến đổi hiệu (ký hiệu BĐH)................. .......................................................................................................................20 4.1.3 Đề xuát phƣơng pháp dựa trên lọc thông cao của phép biến đổi DWT ..............................20 4.1.3.1 Phép biến đổi DWT .....................................................................................................20 4.1.3.2 Đề xuất phƣơng pháp giảm độ phức tạp tính toán (ký hiệu LTC) .................................21 4.2 PHÁT HIỆN GIẢ MẠO ẢNH DẠNG GHÉP ẢNH CÓ NGUỒN GỐC JPEG .............................. 22 4.2.1 Dạng ảnh giả mạo ............................................................................................................22 4.2.2 Cơ sở lý thuyết ................................................................................................................23 4.2.3 Phƣơng pháp phát hiện ....................................................................................................24 4.3 KẾT LUẬN CHƢƠNG 4 ............................................................................................................ 25 KẾT LUẬN ................................................................................................................................................ 26 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN ...................... 27 PHẦN MỞ ĐẦU Ngày nay, ảnh số là phƣơng tiện truyền thông đƣợc sử dụng rộng rãi, đóng vai trò quan trọng trong đời sống con ngƣời, có tác động đến xã hội, tham gia vào các quá trình pháp lý và kinh tế nhƣ: làm bằng chứng trong điều tra, xử án, bảo hiểm, gian lận khoa học, v.v…. Hơn nữa, với sự phổ biến của máy ảnh kỹ thuật số và các phần mềm chỉnh sửa (Photoshop, GIMP, 3D Max), dẫn đến ảnh số có thể dễ dàng đƣợc chỉnh sửa mà không cần đến các kiến thức chuyên gia, và việc chỉnh sửa hầu nhƣ không để lại dấu vết mà mắt thƣờng có thể nhận biết đƣợc. Kết quả là, khi những hình ảnh bị chỉnh sửa đƣợc sử dụng cho mục đích xấu, nó có thể dẫn đến những hậu quả nghiêm trọng. Để giải quyết vấn đề này và trả lời câu hỏi ảnh có độ tin cậy bao nhiêu, ảnh nào là thật, ảnh nào là giả, thì các kỹ thuật xác thực đƣợc phát triển chẳng hạn nhƣ phƣơng pháp chủ động (active method) nhúng dấu thủy vân hay chữ ký số vào trong ảnh, ngƣợc lại phƣơng pháp thụ động (passive method) dựa vào các đặc điểm, tính chất của ảnh giúp phát hiện bị chỉnh sửa mà không cần dấu thủy vân hay chữ ký số đƣợc nhúng vào trƣớc đó. Mục tiêu, phạm vi nghiên cứu Mục tiêu của luận án là nghiên cứu, đề xuất một số phƣơng pháp cho phép đảm bảo tính xác thực (phòng chống giả mạo) của ảnh số và phát hiện ảnh số giả mạo. Việc phòng chống và phát hiện giả mạo trên ảnh số hiện nay có rất nhiều hƣớng khác nhau. Vì vậy, phạm vi nghiên cứu của luận án đƣợc tập trung vào các phƣơng pháp chính sau đây:  Phƣơng pháp chủ đông: Phòng chống giả mạo ảnh số bằng kỹ thuật thủy vân số.  Phƣơng pháp thụ động: Phát hiện ảnh giả mạo dạng cắt/dán và dạng ghép ảnh. Những đóng góp của luận án Để xây dựng các phƣơng pháp với mục tiêu nhƣ trên, luận án tập trung nghiên cứu sâu các công cụ toán học là các phép biến đổi ma trận DCT, DFT, DWT, NMF, SVD, QR,..., từ đó xây dựng các phép biến đổi mới làm cơ sở để cải tiến, đề xuất các phƣơng pháp chủ động và thụ động trong việc phòng chống và phát hiện giả mạo ảnh, (đến nay hƣớng nghiên cứu này vẫn thu hút nhiều sự quan tâm của nhiều nhà nghiên cứu trên thế giới, chẳng hạn nhƣ [17,26,45,46,63,87,88]). Luận án đã đạt đƣợc một số kết quả, đóng góp một phần vào lĩnh vực nghiên cứu, cụ thể nhƣ sau:  Nghiên cứu các phép biến đổi ma trận DCT, DWT, NMF, SVD, QR,... làm cơ sở để xây dựng các phƣơng pháp phòng chống và phát hiện giả mạo ảnh. + Đề xuất thuật toán điều chỉnh cộng cho bài toán thừa số hóa ma trận không âm NMF. Thuật toán đề xuất có ƣu điểm độ phức tạp tính toán thấp và tốc độ hội tụ nhanh hơn. Kết quả đƣợc đăng tài trong kỷ yếu hội thảo lần thứ 16 Asia Pacific Symposium on Intelligent and Evolutionary Systems tại đại học Kyoto, Nhật Bản, năm 2012. Và đƣợc chọn vào số đặc biệt đƣợc đăng lại trong tạp chí New Mathematics and Nature Computing (Scopus index), năm 2015. + Đề xuất phép biến đổi DWT động, phép biến đổi mới này có khả năng tập trung năng lƣợng của ảnh cao hơn vào các phần tử thuộc góc phần tƣ thứ nhất. Các phƣơng pháp phát hiện giả mạo dạng cắt/dán sử dụng phƣơng pháp này để xây dựng các đặc trƣng so sánh sẽ cho hiệu quả phát hiện tốt hơn. Kết quả đƣợc đăng trong Kỷ yếu hội thảo quốc gia lần thứ 7 Nghiên cứu cơ bản và ứng dụng công nghệ thông tin – FAIR, năm 2014. Các phép biến đổi NMF, DWT động này đƣợc dùng để xây dựng lƣợc đồ thủy vân bán dễ vỡ cho phòng chống giả mạo ảnh và phƣơng pháp phát hiện ảnh giả mạo dạng cắt/dán, ghép ảnh.  Nghiên cứu thủy vân bán dễ vỡ phòng chống giả mạo ảnh. 1 + Sử dụng phép biến đổi NMF với thuật toán điều chỉnh cộng đề xuất xây dựng lƣợc đồ thủy vân bán dễ vỡ. + Đề xuất lƣợc đồ thủy vân bán dễ vỡ sử dụng phép phân tích ma trận QR. Kết quả đƣợc đăng trong Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng công nghệ thông tin và truyền thông, Tạp chí Công nghệ thông tin và truyền thông, năm 2013. Các lƣợc đồ thủy vân này đƣợc dùng với mục đích là xác thực, phòng chống giả mạo ảnh.  Nghiêu cứu các phƣơng pháp phát hiện ảnh giả mạo dáng cắt/dán. Từ đó đề xuất đƣợc một số phƣơng pháp mới nhƣ sau: + Phƣơng pháp đối sánh bền vững phát hiện ảnh giả mạo dạng cắt/dán dựa trên phép biến đổi DCT. Kết quả đƣợc đăng trong Kỷ yếu hội thảo quốc gia lần thứ XVI “Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông”, năm 2013. + Phƣơng pháp đối sánh bền vững phát hiện ảnh giả mạo dạng cắt/dán dựa trên phép biến đổi DWT động, Kết quả đƣợc đăng trong Kỷ yếu hội thảo quốc gia lần thứ 7 Nghiên cứu cơ bản và ứng dụng công nghệ thông tin – FAIR, năm 2014. Các phƣơng pháp đề xuất có ƣu điểm là số đặc trƣng ít nên độ phức tạp tính toán thấp và có hiệu quả phát hiện tốt.  Nghiên cứu các phƣơng pháp phát hiện ảnh giả mạo dạng ghép ảnh. Các phƣơng pháp đƣợc xây dựng dựa trên tính chất của phép lấy mẫu lại và nén JPEG. + Đề xuất phƣơng pháp biến đổi hiệu và lọc thông cao của phép biến đổi DWT, hai phƣơng pháp này dựa trên tính phẳng của phép lấy mẫu tăng để phát hiện ảnh giả mạo dạng ghép ảnh. Các phƣơng pháp này có ứu điểm tốc độ tính toán thấp và khả năng phát hiện vẫn bảo đảm và nhiều trƣờng hợp tốt hơn, nên có ý nghĩa khi ảnh giả mạo đƣợc chia thành các khối với số lƣợng lớn. Kết quả đã đƣợc chấp nhận đăng trong Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng công nghệ thông tin và truyền thông, Tạp chí Công nghệ thông tin và truyền thông, số 14(34), tháng 12/2015. + Bƣớc đầu xây dựng phƣơng pháp dựa trên đặc điểm của phép nén JPEG. Ngoài ra, nghiên cứu sinh còn có đƣợc một số kết quả nghiên cứu đƣợc đăng trong các bài báo đƣợc liệt kê trong phần tài liệu tham khảo [1,2,3,11,12,14,15]. Tổ chức của luận án Bố cục của luận án bao gồm phần mở đầu, kết luận và bốn chƣơng nội dung cùng với tài liệu tham khảo. Chƣơng 1: Giới thiệu tổng quan về ảnh giả mạo, một số phƣơng pháp hiện đại phòng chống và phát hiện ảnh giả mạo, và các phép biến đổi ma trận đƣợc dùng để xây dựng các phƣơng pháp phòng chống và phát hiện giả mạo ảnh trong các chƣơng kế tiếp. Chƣơng 2: Trình bày kết quả đề xuất thuật toán điều chỉnh cộng để giải bài toán thừa số hóa ma trận không âm NMF, xây dựng lƣợc đồ thủy vân sử dụng phép biến đổi ma trận NMF này. Trình bày lƣợc đồ thủy vân bán dễ vỡ SVD-1, SVD-N sử dụng phân tích ma trận SVD, đề xuất lƣợc đồ thủy vân QR-1, QR-N sử dụng phân tích QR. Chƣơng 3: Trình bày đề xuất xây dựng phép biến đổi DWT động. Đặc tả chi tiết các phƣơng pháp phát hiện ảnh giả mạo dạng cắt/dán dựa trên phép biến đổi DCT, DWT động, NMF. 2 Chƣơng 4: Trình bày kết quả đề xuất phƣơng pháp dựa trên phép biến đổi hiệu và lọc thông cao của phép biến đổi DWT để phát hiện ảnh giả mạo dạng ghép ảnh. Giới thiệu một số kết quả của phƣơng pháp phát hiện dựa trên tính chất của phép nén JPEG. 3 Chƣơng 1. TỔNG QUAN VỀ ẢNH GIẢ MẠO, PHÕNG CHỐNG VÀ PHÁT HIỆN GIẢ MẠO ẢNH, CÁC PHÉP BIẾN ĐỔI MA TRẬN 1.1 GIỚI THIỆU CHUNG Với sự phát triển của mạng Internet đã giúp cho quá trình phân phối dữ liệu đa phƣơng tiện (image, video, audio, text) nói chung và ảnh số nói riêng giữa những nhà cung cấp và ngƣời dùng trở nên dễ dàng, nhanh chóng. Do vậy nhu cầu bảo mật, xác thực tính toàn ven, bảo vệ quyền tác giả, phát hiện giả mạo đối với ảnh số ngày càng cấp thiết. Lĩnh vực cũng thu hút nhiều nhà nghiên cứu khắp nới trên thế giới, xuất hiện nhiều hội thảo, tạp chí chuyên ngành, chẳng hạn nhƣ International Workshop Digital-Forensics and Watermarking [87], Transactions on Data Hiding and Multimedia Security [88], IEEE Transactions on Forensics and Security,.v.v… 1.2 GIỚI THIỆU VÀ DẠNG ẢNH GIẢ MẠO 1.2.1 Giới thiệu Ảnh giả mạo đƣợc xem là ảnh không có thật, việc có đƣợc ảnh là do sự ngụy tạo bởi các chƣơng trình xử lý ảnh hoặc quá trình thu nhận ảnh. Hiện nay sức mạnh của các chƣơng trình xử lý ảnh số nhƣ PhotoShop, Corel Draw,... giúp việc tạo ra các ảnh giả mạo từ một hay nhiều ảnh khác nhau trở nên dễ dàng. Với các phần mềm này, những ngƣời bình thƣờng không cần các kiến thức chuyên gia cũng có thể có các thao tác nhƣ cắt, dán, thêm, bớt, che, các đối tƣợng trên ảnh hay thay đổi màu sắc, ánh sáng, làm cho ảnh giả nhƣ ảnh thật để đạt mục đích của mình. 1.2.2 Một số dạng ảnh giả mạo Ảnh giả mạo thƣờng chia làm hai loại chính. Ảnh giả nhƣng thật, tức là hiện trƣờng đƣợc dựng thật, và việc thu nhận ảnh là thật. Loại thứ hai là ảnh giả đƣợc tạo lập trên cơ sở các phần của ảnh gốc thật hoặc đƣợc cắt dán để thêm vào hay che đi các chi tiết trên ảnh. Trong luận án này tôi quan tâm đến một số dạng giả mạo thuộc loại thứ hai. Trong dạng ảnh giả mạo thứ hai có thể chia làm 3 loại chính: Ghép ảnh, tăng cƣờng ảnh và cắt/dán (copy/move) trên cùng một ảnh. 1.3 PHƢƠNG PHÁP PHÕNG CHỐNG VÀ PHÁT HIỆN ẢNH GIẢ MẠO Các phƣơng pháp đƣợc chia làm hai hƣớng là phƣơng pháp chủ động (Active Forensic) đƣợc dùng để xác thực/phòng chống giả mạo ảnh và phƣơng pháp thụ động (Passive Forensic) đƣợc dùng để phát hiện ảnh giả mạo. Hai hƣớng này đƣợc mô ta qua sơ đồ sau: 1.3.1 Phƣơng pháp chủ động Các phƣơng pháp này sử dụng kỹ thuật thủy vần và chữ ký số để phòng chống giả mạo ảnh. Luận án này sử dụng kỹ thuật thủy vân nên các các nội dung tiếp theo chỉ đề cập đến kỹ thuật này 1.3.1.1 Giới thiệu và phân loại thủy vân Thủy vân số (Watermarking) là một phƣơng pháp ẩn một số thông tin vào dữ liệu đa phƣơng tiện. 4 Thủy vân số có nhiều ứng dụng, nên các phƣơng pháp thủy vân đƣợc quan tâm và đã có nhiều lƣợc đồ thủy vân đƣợc đề xuất. Các phƣơng pháp thủy vân đƣợc chia làm ba loại chính: thủy vân bền vững (robust watermarking), thủy vân dễ vỡ (fragile watermarking), và thủy vân bán dễ vỡ (semi-fragile watermarking). 1.3.1.2 Tính chất của lược đồ thủy vân Tính ẩn. Tính bền vững. Khả năng mang tin cao. An ninh. 1.3.1.3 Ứng dụng của thủy vân Thủy vân có rất nhiều ứng dụng trong nhiều lĩnh vực. Tuy nhiên có một số ứng dụng chính sau đây: bảo vệ bản quyền, chống sao chép, xác thực nội dung/phòng chống giả mạo. 1.3.2 Phƣơng pháp thụ động Một số phƣơng pháp thụ động giúp phát hiện ảnh bị chỉnh sửa mà không cần dấu thủy vân hay chữ ký số đƣợc nhúng vào trƣớc đó: Phƣơng pháp dựa trên Pixel (Pixel-based methods). Phƣơng pháp dựa trên định dạng (Format-based methods). Dựa trên thiết bị thu nhận (Camera-based methods). Dựa trên đặc tính vât lý (Physics-based methods). Phƣơng pháp dựa trên đặc tính hình học (Geometry-based methods) 1.4 MỘT SỐ PHÉP BIẾN ĐỔI MA TRẬN Mục tiêu của luận án là nghiên cứu các phép biến đổi ma trận từ đò cải tiến, đề xuất các phƣơng pháp phòng chống và phát hiện giả mạo. Phép phân tích SVD. Phép phân tích QR. Phép biến đổi cosine rời rạc (DCT). Phép biến đổi wavelet rời rạc (DWT). Phép phân tích thừa số hóa ma trận không âm (NMF). 1.5 KẾT LUẬN CHƢƠNG 1 Chƣơng này với mục tiêu là giới thiệu chung về tình hình, lĩnh vực nghiên cứu, một số khái niệm, phƣơng pháp đƣợc dùng trong luận án. Nội dung của chƣơng đã trình bày đƣợc một số khái niệm về ảnh giả mạo, phân loại ảnh giả mạo và phƣơng pháp phòng chống và phát hiện. Bên cạnh các khái niệm, chƣơng cũng trình bày một số phép biến đổi ma trận đƣợc sử dụng nhiều để xây dựng các phƣơng pháp phòng chống và phát hiện ảnh giả mạo: Phép biến đổi DCT, DWT, phép phân tích ma trận SVD, QR, phép thừa số hóa ma trận không âm NMF. Các phép biến đổi này sẽ đƣợc sử dụng để xây dựng các phƣơng pháp ở Chƣơng 2, Chƣơng 3 và Chƣơng 4 của luận án. 5 Chƣơng 2. PHÕNG CHỐNG GIẢ MẠO ẢNH BẰNG KỸ THUẬT THỦY VÂN 2.1 KỸ THUẬT THỦY VÂN VÀ PHÕNG CHỐNG GIẢ MẠO ẢNH Ngoài bảo vệ bản quyền, thủy vân còn đƣợc ứng dụng là xác thực/phòng chống giả mạo ảnh. Kỹ thuật thủy vân sử dụng để phòng chống giả mạo ảnh là thủy vân bán dễ vỡ. Nhúng dấu thủy vân: Bƣớc 1. Chia ảnh thành các khối không chờm nhau. Bƣớc 2. Sử dụng lƣợc đồ thủy vân bán dễ vỡ nhúng dấu thủy vân vào từng khối Bƣớc 3. Thu đƣợc ảnh có các khối chƣa dấu thủy vân Xác thực và định vị vùng giả mạo: Bƣớc 1. Chia ảnh thành các khối tƣơng tự nhƣ quá trình nhúng. Bƣớc 2. Trích dấu thủy vân từ các khối. Bƣớc 3. Kiểm tra các dấu thủy vân đƣợc trích từ từng khối Bƣớc 4. Kết luận và khoanh vùng giả mạo + Tồn tại dấu thủy vân nào không nguyên vẹn, kết luận ảnh bị chỉnh sửa + Các vùng có dấu thủy vân bị phá hủy là vùng giả mạo. Hình ảnh bên dƣới ví dụ mô tả kết quả của hai quá trình này: Hình 2.1. Ảnh được chia khối và dấu thủy vân được trích ra. Theo sơ đồ trên nhận thấy lƣợc đồ thủy vân chính là cốt lõi, việc nghiên cứu và phát triển các lƣợc đồ thủy vân bán dễ vỡ chính là nghiên cứu các phƣơng pháp phòng chống giả mạo. 2.2 ĐỀ XUẤT THUẬT TOÁN ĐIỀU CHỈNH CỘNG GIẢI BÀI TOÁN NMF VÀ XÂY DỰNG LƢỢC ĐỒ THỦY VÂN Thừa số hóa ma trận không âm (NMF) là một kỹ thuật đang phát triển, có nhiều ứng dụng tiềm năng trong phân tích, biểu diễn, thu gọn dữ liệu, trích chọn đặc trƣng. Đây là vấn đề hiện đang thu hút nhiều sự quan tâm cả về lý thuyêt lẫn ứng dụng của các nhà nghiên cứu. Thuật toán mới đơn giản trong thực hiện và có các tính chất tối ƣu, hội tụ nhanh hơn so với một số thuật toán đã biết. 2.2.1 Điều chỉnh một phần tử của W Trong mục này, xét thuật toán điều chỉnh một phần tử của ma trận W, trong khi giữ nguyên các phần tử còn lại của W và H. Giả sử Wij đƣợc điều chỉnh bằng cách cộng thêm tham số  : ~ Wij  Wij   ~ Gọi W là ma trận nhận đƣợc, khi đó bằng một số phép biến đổi ma trận, ta có: (2.1)  (WH ) ab , a  i, b  1..m ~ (WH ) ab   (WH )ib  H jb , a  i, b  1..m Nên từ (1.2) suy ra: ~ f (W , H )  f (W , H )  g ( ) trong đó: 6 (2.2) 1 g ( )  ( p 2 )  q 2 (2.3) m p   H 2jb b 1 (2.4) m q   (WH  V ) ib * H jb b 1 (2.5) ~ Để giảm tối đa f (W , H ) cần xác định  sao cho g(  ) đạt giá trị cực tiểu với điều kiện ~ Wij  Wij    0 . Do g(  ) là hàm bậc hai, nên  có thể đƣợc tính nhƣ sau:   0, q  0  q    max( , wij ), q  0 p  q  ,q  0  p  (2.6) Công thức (2.6) luôn có nghĩa vì nếu q  0 thì theo (2.4) sẽ có p > 0. Từ công thức (2.3) và (2.6) , ta có: g ( )  0 , nếu (q = 0) hoặc (q>0 và Wij =0) g ( )  0 , nếu trái lại (2.7.a) (2.7.b) 2.2.2 Điều chỉnh một phần tử của H ~ Gọi H là ma trận nhận đƣợc qua phép điều chỉnh: ~ H ij  H ij   (2.9) Trong đó  đƣợc xác định theo các công thức : n u  Wai2 a 1 (2.10) n v   Wai  (WH  V ) aj a 1 (2.11)   0, v  0  v   max( , H ij ), v  0 u   v  ,v  0  u (2.12) 2.2.3 Thuật toán đề xuất (Ký hiệu aNMF) 2.2.3.1 Điều chỉnh ma trận W và H ~ ~ Trong mục này ta xét phép biến đổi T từ (W, H) sang ( W , H ) nhƣ sau:  Biến đổi các phần tử của W theo 2.1  Biến đổi các phần tử của H theo 2.2 ~ ~ Nói cách khác phép biến đổi: (W , H )  T (W , H ) đƣợc thực hiện nhƣ sau: Bƣớc 1. Khởi gán ~ ~ W W,H  H ~ Bƣớc 2. Điều chỉnh các phần tử của W Với j=1..r và i=1..n ~ ~ Wij  Wij   7  tính theo (2.4)-(2.6) ~ Bƣớc 3. Điều chỉnh các phần tử của H Với i=1..r và j=1..m ~ ~ H ij  H ij    tính theo (2.10)-(2.12) 2.2.3.2 Thuật toán aNMF giải bài toán NMF Thuật toán đƣợc mô tả qua phép biến đổi T nhƣ sau: Bƣớc 1. Khởi tạo W=W1>=0, H=H1>=0 Bƣớc 2. For k=1,2,... W k 1   , H k 1  T W k , H k  2.2.4 Xây dựng lƣợc đồ thủy vân sử thuật toán aNMF 2.2.4.1 Thuật toán nhúng thủy vân Dƣới đây là lƣợc đồ thủy vân bán dễ vỡ đƣợc xây dựng theo [38] sử dụng phân tích NMF của Lee Seung [60], tuy nhiên với ƣu điểm của thuật toán aNMF mới khi áp dụng sẽ có một số ƣu điểm nổi trội hơn. Đầu vào: Ảnh A, dấu thủy vân W, hệ số α. Đầu ra: Ảnh A’ chứa dấu thủy vân W. Bƣớc 1. Chia ảnh A thành các khối có kích thƣớc l×l, ký hiệu mỗi khối là L Bƣớc 2. Áp dụng thuật toán aNMF cho mỗi khối L: L=BlHl Bƣớc 3. Áp dúng phân tích SVD cho ma trận trong số Hl: Hl=UlDlVl’ Bƣớc 4. Áp dụng thuật toán aNMF cho dấu thủy vân: W= BWHW Bƣớc 5. Áp dúng phân tích SVD cho ma trận trong số HW: HW=UWDWVW’ ở đây Dw=diag(λwi). Bƣớc 6. Sửa λmax theo công thức: λid = λmax +αλwi trong đó λmax là phần tử lớn nhất của Dl, α là hệ số, λid là giá trị chỉnh sửa của Dl. Bƣớc 7. Tính: Ld = BlHld trong đó Hld=UlDldVl’, với Dld = diag(λid). Ghép các khối L thu đƣợc ảnh chứa dấu thủy vân A’! 2.2.4.2 Thuật toán trích thủy vân Đầu vào: Ảnh A’ Đầu ra: Dấu thủy vân W Bƣớc 1. Chia ảnh thành các khối kích thƣớc l×l, ký hiệu mỗi khối là K. Bƣớc 2. Áp dụng thuật toán aNMF cho mỗi khối K: K=BkHk Bƣớc 3. Áp dụng SVD cho ma trận Hk Hk=UkDkVk’ 8 Bƣớc 4. Trích các giá trị: λwi* = (λid - λmax) /α trong đó λid là các phần tử trên đƣờng chéo của Dk, λmax là phần tử lớn nhất của Hl đƣợc lƣu trong mỗi khối nhƣ là khóa bí mật. Bƣớc 5. Khôi phục dấu thủy vân: W*=BwHw* trong đó Hw*=UwDw* Vw’, Dw*=diag(λwi*). 2.3 ĐỀ XUẤT LƢỢC ĐỒ THỦY VÂN SỬ DỤNG PHÂN TÍCH QR 2.3.1 Đề xuất lƣợc đồ thủy vân sử dụng phân tích QR 2.3.1.1 Lược đồ thủy vân QR-1 a. Thuật toán nhúng thủy vân Để tiện trình bầy thuật toán, chọn phần tử R(1,1) để nhúng một bít của dấu thủy vân. Đầu vào của  thuật toán là ảnh I, dấu thủy vân W  w1 ,..., wt  và hệ số lƣợng tử q. Đầu ra của thuật toán là ảnh I’ chứa dấu thủy vân W. Các bƣớc của thuật toán nhƣ sau: Bƣớc 1. Chia ảnh I thành t khối không giao nhau từng đôi một và có cùng kích thƣớc m×n, ký hiệu là Ii,i=1,2,...,t. Bƣớc 2. Áp dụng phân tích QR trên mỗi khối Ii: Ii=Qi × Ri Bƣớc 3. Nhúng bít wi vào phần tử Ri(1,1) của ma trận tam giác trên Ri . Bước 3.1: Tính:  R (1,1)  ki   i   q  Bước 3.2: Điều chỉnh Ri(1,1) thành Ri’(1,1): Ri' (1,1)  ki  q  ki mod 2 XOR wi   q Sau khi thực hiện nhúng wi vào Ri(1,1) ta nhận đƣợc Ri’ chỉ khác Ri tại vị trí (1,1). Nếu chọn phần tử khác để nhúng,ví dụ Ri(1,k) , thì Ri’ khác Ri tại vị trí (1,k). Bƣớc 4. Tính I i'  Qi  Ri' , ảnh I’ tạo từ các khối Ii’ là ảnh chứa dấu thủy vân W. b. Thuật toán kiểm tra dấu thủy vân Cho I* là một phiên bản tấn công của I’ và hệ số lƣợng tử q, thuật toán dƣới đây sẽ kiểm tra sự tồn tại của dấu thủy vân trong ảnh I* để kết luận về bản quyền đối với I* của tác giả có ảnh I’. Bƣớc 1. Chia ảnh I* thành t khối nhƣ trong thuật toán nhúng thủy vân, ký hiệu là Ii*, i=1,...,t. Bƣớc 2. Áp dụng phân tích QR cho từng khối Ii* : Ii* = Qi* × Ri* Bƣớc 3. Xác định bít wi* từ Ri*(1,1) nhƣ sau : q  *  R i (1,1)  2  ki    q     * wi*  ki* MOD 2 Bƣớc 4. So sánh dấu thủy vân W *  w1* ,..., wt* trích ra từ I* với dấu thủy vân gốc W  w1 ,..., wt    tƣơng tự bƣớc 4 trong mục 2.3.1.1.b 9  2.3.1.2 Lược đồ thủy vân QR-N a. Thuật toán nhúng thủy vân của lược đồ này cũng gồm 4 bước như thuật toán nhúng thuỷ vân của lược đồ QR-1, chỉ khác ở bước 3 như sau. Bƣớc 3. Nhúng bít wi của dấu thủy vân vào hàng đầu của ma trận Ri. Bước 3.1: Tính: xi=Xi(1)+ Xi(2)+…+Xi(n) x  ki   i  q x'i  ki  q  ki MOD 2  wi   q trong đó véc tơ Xi gồm các phần tử trên hàng đầu của ma trận Ri: Xi= (Ri(1,1), Ri(1,2),…,Ri(1,n)). Nhận xét: Xi là véc tơ dƣơng (xem nhận xét 1, mục 5). Bước 3.2: Điều chỉnh Ri thành Ri’: Xi  ' x 'i xi Xi thu đƣợc ma trận Ri’ với hàng đầu là véc tơ X i' b. Thuật toán kiểm tra dấu thủy vân của lược đồ này cũng gồm 4 bước như thuật toán kiểm tra dấu thuỷ vân của lược đồ QR-1, chỉ khác ở bước 3 như sau. Bƣớc 3. Xác định bít wi* từ hàng đầu của Ri*: Bước 3.1: Tính: xi  X i (1)  X i (2)  ...  X i (n)   q  xi  2  ki     q    * trong đó véc tơ X i* gồm các phần từ trên hàng đầu của ma trận Ri* :   X i*  Ri (1,1), Ri (1,2),..., Ri (1, n) . Bước 3.2: Xác định wi*: wi*  ki* MOD 2 2.4 KẾT LUẬN CHƢƠNG 2 Chƣơng đã trình bày các kết quả nghiên cứu lƣợc đồ thủy vân bán dễ vỡ sử dụng phòng chống giả mạo ảnh. Nội dung đã trình bày đề xuất thuật toán điều chỉnh cộng cho bài toàn thừa số hóa ma trận không âm NMF, thuật toán đề xuất có ƣu điểm là đơn giản, tốc độ tính toán và hội tụ nhanh hơn so với thuật toán ban đầu và một số thuật toán cải tiến sau đó. Từ đó, xây dựng lƣợc đồ thủy vân bán dễ vỡ sử dụng thuật toán mới đề xuất để xây dựng phƣơng pháp phòng chống giả mạo ảnh. Chƣơng này cũng trình bày hai lƣợc đồ thủy vân bán dễ vỡ SVD-1, SVD-N sử dụng phân tích SVD, từ đó xây dựng hai lƣợc đồ thủy vân bán dễ vỡ mới QR-1, QR-N. Các lƣợc đồ đề xuất này có một số ƣu điểm là nhanh hơn và bền vững hơn trƣớc một số phép tấn công ảnh mà không thay đổi nội dung nhƣ: nén JPEG, làm mờ, nhiễu, …. 10 Chƣơng 3. PHÁT HIỆN ẢNH GIẢ MẠO DẠNG CẮT/DÁN 3.1 ẢNH GIẢ MẠO DẠNG CẮT/DÁN VÀ MỘT SỐ PHƢƠNG PHÁP PHÁT HIỆN 3.1.1 Ảnh giả mạo dạng cắt/dán Việc chỉnh sửa nhằm tạo ra ảnh giả mạo có nhiều thao tác khác nhau, trong đó có thao tác phổ biến cắt/dán (copy/move) các vùng trên cùng một ảnh nhằm che giấu hay sao chép một số đối tƣợng trên ảnh, dạng giả mạo này đƣợc gọi là giả mạo dạng cắt/dán (copy/move forgery) hoặc vùng sao chép giả mạo (region duplication forgery). Một ví dụ của hình thức giả mạo này đƣợc cho trong Hình 3.1. (a) (b) Hình 3.1. Ví dụ ảnh giả mạo cắt/dán, (a) là ảnh ban đầu, (b) là ảnh giả với một chú chim được sao chép. 3.1.2 Phân loại các phƣơng pháp phát hiện 3.1.2.1 Phương pháp đối sánh chính xác Ý tƣởng của thuật toán là sử dụng các khối chờm nhau để đối sánh nhằm tìm ra các vùng giống nhau trên toàn bộ bức ảnh. 3.1.2.2 Phương pháp đối sánh bền vững Phƣơng pháp đối sánh bền vững khác phƣơng pháp đối sánh chính xác ở bƣớc xây dựng véc tơ đặc trƣng. Ở phƣơng pháp đối sánh chính xác sử dụng cả khối ảnh làm véc tơ đặc trƣng nên số chiều lớn và không bền vững trƣớc các phép tấn công ảnh (quay, nén, là mờ, nhiễu,…). Trong khi đó phƣơng pháp đối sánh bền sử dụng các công cụ trích chọn đặc trƣng để tạo nên véc tơ đặc trƣng, nên véc tơ đặc trƣng có số chiều ít hơn nhiều và tùy thuộc vào công cụ trích chọn đặc trƣng mà phƣơng pháp có tính bền vững với các phép tấn công ảnh tƣơng ứng. 3.2 ĐỀ XUẤT PHƢƠNG PHÁP DỰA TRÊN PHÉP BIẾN ĐỔI DCT Thuật toán đề xuất có một số ƣu điểm chính sau: - Chiều của vectơ đặc trƣng thấp hơn, nên có tốc độ tính toán nhanh hơn. - Bến vững trƣớc một số thao tác: cắt/dán nhiều vùng, nén ảnh, làm mờ, thêm nhiễu. 3.2.1 Thuật toán phát hiện Trong thuật toán này, đầu vào là một ảnh đa cấp xám A có kích thƣớc m×n (nếu là ảnh màu thì sử dụng công thức I=0.228R+0.587G+0.114B để chuyển sang đa cấp xám) và tham số b là kích thƣớc khối, α1, α2, β, γ là các giá trị ngƣỡng cho trƣớc. Chi tiết của thuật toán đƣợc trình bày ở các bƣớc nhƣ sau: Bƣớc 1. Chia ảnh thành các khối chờm nhau có kích thƣớc bxb, sao cho hai khối liên tiếp chỉ khác nhau một hàng hoặc một cột. Các khối đƣợc định vị theo thƣ tự từ trái qua phải và từ trên xuống dƣới của ảnh. Số khối thu đƣợc là Sb=(m-b+1)(n-b+1) với mỗi khối ký hiệu là Ai (i=1,2,3,…,Sb). Bƣớc 2. Biến đổi cô sin rời rạc DCT cho từng khối, áp dụng phép biến đổi cô sin rời rạc DCT cho từng khối, thu đƣợc ma trận hệ số DCT ký hiệu là Ci có kích thƣớc b×b. Bƣớc 3. Xây dựng vectơ đặc trƣng Bây giờ khối điểm ảnh thứ i đƣợc đại diện bởi ma trận Ci. Ma trận hệ số DCT có đặc điểm là năng lƣợng tập trung vào các hệ số ở vùng tần số thấp (góc trên bên trái), các hệ số tần số thấp này đóng vai trò 11 quan trọng hơn các hệ số khác. Dựa vào đặc điểm này ta đƣa ra cách chọn các hệ số DCT làm đại diện nhƣ sau: Bước 3.1: Đánh số thứ tự các phần tử của ma trận hệ số DCT theo đƣờng zigzag (nhƣ hình vẽ) để đƣợc một dãy số: Hình 3.4. Đánh số thứ tự các phần tử của ma trận hệ số DCT theo đường zigzag Bước 3.2: Chia dãy số thu đƣợc ở Bƣớc 3.1 thành 4 đoạn bằng nhau, lấy 2 đoạn đầu để tính đại diện cho mỗi khối. Ta ký hiệu các phần tử của dãy số ứng với khối i là ci,j với i=1,…,Sb và j=1,…,b×b. Khi đó các đặc trƣng đại diện ei,1, ei,2 đƣợc tính nhƣ sau:  ei ,1  2 c j 1 i, j  , ei , 2   c j  1 i, j  1 (i  1,, Sb),   b  b 4 Với hai đặc trƣng thu đƣợc, kết hợp lại đƣợc một vectơ đặc trƣng có số chiều bằng 2, ký hiệu là: Ei  ei ,1 , ei , 2  Nhƣ vậy, thay vì ma trận có số chiều là b×b làm đại diện thì sử dụng một vectơ với số chiều bằng 2. Số chiều của vectơ đại diện trong [80], [47], [24], [67] lần lƣợt bằng 32, 16, 4 và 7 thì số chiều của vectơ đại diện trong thuật toán đề xuất giảm đáng kể. Cách xác định đặc trƣng ở đây dựa trên nửa đầu số phần tử của ma trận hệ số DCT đƣợc đánh số thứ tự theo đƣờng zigzag, nhƣ tính chất đã nêu thì đây là phần đóng vai trò quan trọng, tập trung năng lƣợng của ảnh. Qua thực nghiệm cho thấy khi ảnh bị biến đổi thì nửa đầu số phần tử này có các giá trị bị thay đổi nhiều, còn nửa sau số phần tử còn lại ít bị thay đổi và biên độ thay đổi nhỏ. Bƣớc 4. Sắp xếp các khối theo thứ tự từ điển Ký hiệu ma trận E với kích thƣớc là Sb×2, chứa tập vectơ đặc trƣng đƣợc xác định trong bƣớc 3.  E1  E   ...   ESb  Sắp xếp các hàng của E theo thứ tự từ điển. Gọi ma trận nhận đƣợc sau khi sắp xếp là G, với hàng thứ i là Gi  ( gi ,1 , gi , 2 ) . Bƣớc 5. Tìm các cặp khối tƣơng tự Định nghĩa khối tƣơng tƣ: Hai khối Gi và Gj là một cặp khối tƣơng tự đƣợc tạo ra bởi thao tác cắt/dán nếu thỏa mãn các điều kiện sau đây. gi ,1  g j ,1  1 (3.1) gi , 2  g j , 2   2 (3.2) 12 Thông thƣờng các vùng đƣợc cắt/dán không chờm lên nhau, nên dùng thêm khoảng cách Euclid giữa các khối để loại bỏ bớt các khối thỏa mãn điều kiện trên nhƣng không phải vùng đƣợc cắt/dán. Khoảng cách Euclid giữa hai khối đƣợc tính nhƣ sau: ( xi  x j )2  ( yi  y j )2   (3.3) Trong đó (xi, yi), (xj,yj) lần lƣợt là tọa độ góc trên bên trái của khối Gi, Gj. Do ma trận G đã đƣợc sắp xếp theo thứ tự từ điển, nên để tìm các cặp khối tƣơng tự chỉ cần xét với các chỉ số i, j có hiệu số |i-j| ≤ k trong đó k là một ngƣỡng nào đó, thông thƣờng lấy bằng 5. Ta có Thuật toán tìm khối tƣơng tự nhƣ sau: For i=1 to Sb-k For j=i+1 to i+k Nếu Gi, Gj thỏa mãn theo điều kiện (3.1), (3.2), (3.3) thì lƣu chúng vào một mảng để dùng trong bƣớc 6. End End For i=(Sb-(m-1)) to (Sb-1) For j=(i+1) to Sb Nếu Gi, Gj thỏa mãn theo điều kiện (3.1), (3.2), (3.3) thì lƣu chúng vào một mảng. End End S Fi S S Fi Fi Fj Fj Fj A A Hình 3.5. Vectơ dịch chuyển của vùng cắt/dán Bƣớc 6. Tính vectơ dịch chuyển cho các cặp khối tƣơng tự Hai khối tƣơng tự Gi, Gj có vectơ dịch chuyển (shift vectơ) đƣợc tính nhƣ sau: S( Gi, Gj)=(xi - xj, yi - yj) Sau đó thống kê tần suất xuất hiện của các vectơ dịch chuyển. Gọi Ω là tập các vectơ dịch chuyển có tần suất xuất hiện lớn hơn một ngƣỡng γ (thƣờng γ bằng 0.85% kích thƣớc của ảnh ). + Nếu Ω là tập rỗng thì có thể kết luận ảnh không giả mạo dạng cắt/dán. + Nếu trái lại chuyển sang bƣớc 7. Bƣớc 7. Xác định vùng giả mạo Với mỗi vectơ dịch chuyển S   sẽ ứng với một vùng giả mạo cắt/dán. Để tìm vùng giả mạo này ta làm nhƣ sau. Xây dựng tập H theo công thức: H  i, j | S (Gi , G j )  S  Sau đó xây dựng các tập A1 và A2 theo công thức A1={Kh(Gi)} và A2={Kh(Gj)} với (i,j)  H, trong đó Kh(Gi), Kh(Gj) - là khối ảnh ứng với Gi, Gj. Bƣớc này đƣợc minh họa trong Hình 3.5. 13 3.3 ĐỀ XUẤT PHÉP BIẾN ĐỔI DWT VÀ XÂY DỰNG PHƢƠNG PHÁP PHÁT HIỆN Trong phần này này luận án trình bày đề xuất một phép biến đổi động kiểu wavelet rời rạc (gọi là phép biến đổi DWT động) trong đó ma trận của phép biến đổi đƣợc thay đổi linh hoạt theo từng ảnh đƣợc xét. Do vậy phép biến đổi này có khả năng tập trung năng lƣợng tốt hơn so với một số phép biến đổi DWT thông dụng nhƣ phép biến đổi DWT Haar và DWT Daubechies D4 [32,70,86]. Sau đó ứng dụng phép biến đổi mới này để xây dựng thuật toán phát hiện ảnh giả mạo dạng cắt/dán. So với các thuật toán [23,53,98], thuật toán đề xuất có tính bền vững cao hơn trƣớc các phép tấn công nén JPEG, thêm nhiễu, làm mời hay kết hợp các phép tấn công. 3.3.1 Đề xuất xây dựng phép biến đổi DWT động Mục này đề xuất một phép biến đổi động kiểu wavelet rời rạc. Xét phép biến đổi từ A sang B: B  PA (3.4) trong đó P có dạng nhƣ ma trận Haar:  p1  0 0  0 P p  2 0 0   0 p2 0 0 0 0 0 0 p3 p4 0 0 0 0 0 0 p5 p6 0 0 0 0 0 0 p7  p1 0 0 0 0 0 0 p4  p3 0 0 0 0 0 0 p6  p5 0 0 0 0 0 0 p8 0   0  0   p8  0   0  0   p 7  (3.5) Các hệ số pi>0 đƣợc xác định theo A sao cho P là ma trận trực chuẩn và năng lƣợng tập trung cao nhất vào nửa trên của B. Từ (3.4) và (3.5) suy ra: B[1]=p1×A[1]+p2×A[2] B[2]=p3×A[3]+p4×A[4] do đó: Sum(B[1])=p1× Sum(A[1])+p2×Sum(A[2]) Sum(B[2])=p3×Sum(A[3])+p4×Sum(A[4]) từ điều kiện trực chuẩn của P suy ra p12  p22  1 , nên có thể đặt: p1=sinα, p2=cosα, khi đó Sum(B[1]) có thể xem nhƣ một hàm của α: Sum(B[1]) = sinα×Sum(A[1]) + cosα×Sum(A[2])  f(α) hàm này đạt cực đại khi: f’(α) = cosα×Sum(A[1]) - sinα×Sum(A[2])=0 hay: tg  Sum( A[1]) Sum( A[2]) từ đó suy ra: p1  sin   p2  cos   Sum( A[1]) Sum 2 ( A[1])  Sum 2 ( A[2]) Sum( A[2]) Sum 2 ( A[1])  Sum 2 ( A[2]) Một cách tổng quát để Sum(B[i]) đạt cực đại, thì p2i-1 và p2i cần xác định theo công thức sau: p2i 1  Sum( A[2i  1]) Sum ( A[2i  1])  Sum 2 ( A[2i]) 2 14 p2 i  Sum( A[2i]) Sum 2 ( A[2i  1])  Sum 2 ( A[2i]) , i=1,2,…,N/2 (3.6) Nhƣ vậy ma trận P xác định theo (3.5) và (3.6) sẽ làm cho năng lƣợng của A qua phép biến đổi (3.4) tập trung năng lƣợng cao nhất vào nửa trên (N/2 hàng đầu) của B. Tiếp theo, xét biến đổi từ B sang C: C  BQ T ở đây Q cũng có dạng ma trận Haar:  q1  0 0  0 Q q  2 0 0   0 q2 0 0 0 0 0 0 q3 q4 0 0 0 0 0 0 q5 q6 0 0 0 0 0 0 q7  q1 0 0 0 0 0 0 q4  q3 0 0 0 0 0 0 q6  q5 0 0 0 0 0 0 q8 0   0  0   q8  0   0  0   q 7  (3.7) Bằng cách lập luận tƣơng tự có thể chỉ ra rằng q2i-1, q2i xác định theo công thức: ~ Sum( B (2i  1)) ~ ~ Sum 2 ( B (2i  1))  Sum 2 ( B (2i)) ~ Sum( B (2i)) q2 i  ~ ~ Sum 2 ( B (2i  1))  Sum 2 ( B (2i)) , i=1,2,…,N/2 q2i 1  (3.8) ~ trong đó B là ma trận cấp N/2×N gồm N/2 hàng đầu của B. Thì năng lƣợng nửa trên của B sẽ tập trung cao nhất vào góc phần tƣ thứ nhất của C. Tóm lại, nếu A là ma trận ảnh cấp N×N, thì phép biến đổi DWT động: C  ( PA)QT trong đó P và Q xác định theo các công thức (3.5), (3.6) và (3.7), (3.8) sẽ tâp trung năng lƣợng của ảnh A một cách cao nhất vào góc phần tƣ thứ nhất của C. 3.3.2 Ứng dụng xây dựng thuật toán phát hiện Việc ứng dụng DWT trong phát hiện ảnh giả mạo dạng cắt/dán thƣờng có hai cách. Cách thứ nhất sử dụng DWT một mức cho toàn ảnh, sau đó sử dụng góc phần tƣ thứ nhất thay cho ảnh để giảm khối lƣợng tính toán [53,98]. Cách thứ hai chia ảnh thành từng khối và áp dụng DWT để xây dựng véc tơ đăc trƣng cho mỗi khối [23]. Cũng có một số nghiên cứu kết hợp DWT với các phép biến đổi khác [61,72]. Theo khảo sát thì cách thứ nhất có thời gian thực hiện thuật toán nhanh hơn trong khi đó cách thứ hai có khả năng phát hiện giả mạo tốt hơn. Các phép biến đổi DWT có thể xem là tĩnh vì ma trận của các phép biến đổi này luôn cố định, không phụ thuộc gì vào ảnh đƣợc xét. Vì vậy, độ tập trung năng lƣợng của chúng thƣờng không cao. Dƣới đây trình bày ứng dụng biến đổi DWT động xây dựng thuật toán đối sánh bền vững phát hiện ảnh giả mạo dạng cắt/dán theo cách thứ hai tức là chia ảnh thành từng khối, sau đó áp dụng DWT động 2 mức cho các khối này để xây dựng véc tơ đặc trƣng. Để tiện theo dõi, ở đây đƣa ra cách xác định cặp khối tƣơng tự: Hai khối ảnh có vectơ đặc trƣng Gi và Gj là một cặp khối tƣơng tự đƣợc tạo ra bởi thao tác cắt/dán nếu thỏa mãn các điều kiện sau đây. g i ,k  g j ,k   (3.9) trong đó k là số phần từ của véc tơ đặc trƣng. 15 Thông thƣờng các vùng đƣợc cắt/dán không chờm lên nhau, nên dùng thêm khoảng cách Euclid giữa các khối để loại bỏ bớt các khối thỏa mãn điều kiện trên nhƣng không phải vùng đƣợc cắt/dán. Khoảng cách Euclid giữa hai khối đƣợc tính nhƣ sau: ( xi  x j )2  ( yi  y j )2   (3.10) trong đó (xi, yi), (xj,yj) lần lƣợt là tọa độ góc trên bên trái của hai khối. Dƣới đây trình bày ứng dụng biến đổi DWT động xây dựng thuật toán đối sánh bền vững phát hiện ảnh giả mạo dạng cắt/dán theo cách thứ hai tức là chia ảnh thành từng khối, sau đó áp dụng DWT động 2 mức cho các khối này để xây dựng véc tơ đặc trƣng. Trong thuật toán này, đầu vào là một ảnh đa cấp xám A có kích thƣớc m×n (nếu là ảnh màu thì sử dụng công thức A=0.299R+0.587G+0.114B để chuyển sang đa cấp xám) và tham số b là kích thƣớc khối, αk, β, γ là các giá trị ngƣỡng cho trƣớc. Chi tiết của thuật toán đƣợc trình bày ở các bƣớc nhƣ sau: Bƣớc 1. Chia ảnh thành các khối chờm nhau có kích thƣớc b×b, sao cho hai khối liên tiếp chỉ khác nhau một hàng hoặc một cột. Các khối đƣợc định vị theo thứ tự từ trái qua phải và từ trên xuống dƣới của ảnh. Số khối thu đƣợc là Sb=(m-b+1)(n-b+1) với mỗi khối ký hiệu là Ai (i=1,2,3,…,Sb). Bƣớc 2. Áp dụng phép biến đổi DWT động hai mức cho từng khối, áp dụng phép biến đổi mức một thu đƣợc bốn vùng (ma trận) lần lƣợt ký hiệu là LLi,1, LHi,1, HLi,1, HHi,1 có kích thƣớc b/2×b/2. Sau đó tiếp tục áp dụng phép biến đổi mức hai cho vùng LLi,1, thu đƣợc bốn vùng ở mức này là LLi,2, LHi,2, HLi,2, HHi,2 có kích thƣớc b/4×b/4. Lấy ma trận LLi,2 làm đại diện cho khối ảnh i. Bƣớc 3. Xây dựng vectơ đặc trƣng Bây giờ khối điểm ảnh thứ i đƣợc đại diện bởi ma trận LLi,2. Ma trận LLi,2 có đặc điểm là tập trung hầu hết năng lƣợng của ảnh, đóng vai trò quan trọng hơn các ma trận còn lại. Dựa vào đặc điểm này chọn các giá trị của LLi,2 làm vectơ đặc trƣng, ký hiệu là:  LLi,2 (1,1), LL i,2 (1,2), ..., LL i,2 (1, b/4),     LLi,2 (2,1), LL i,2 (2,2),..., LL i,2 (2, b/4),  Ei    ....    LL (b/4,1), LL (b/4,2),..., LL (b/4, b/4)  i,2 i,2  i,2  Bƣớc 4. Sắp xếp các khối theo thứ tự từ điển Ký hiệu ma trận E với kích thƣớc là Sb×b2/16, chứa tập vectơ đặc trƣng đƣợc xác định trong bƣớc 3.  E1  E   ...   ESb  Sắp xếp các hàng của E theo thứ tự từ điển. Gọi ma trận nhận đƣợc sau khi sắp xếp là G, với hàng thứ i là Gi  ( gi ,1 , gi , 2 ,...gi ,b2 /16 ) Bƣớc 5. Tìm các cặp khối tƣơng tự Thuật toán tìm khối tƣơng tự nhƣ sau: For i=1 to Sb-k For j=i+1 to i+k Nếu Gi, Gj thỏa mãn theo điều kiện (3.9), (3.10) thì lƣu chúng vào một mảng để dùng trong bƣớc 6. End End 16