Tóm tắt Luận á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

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. 6 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ố  :  ijij WW ~ (2.1) 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ó:       mbiaHWH mbiaWH HW jbib ab ab ..1,,)( ..1,,)( ) ~ (  Nên từ (1.2) suy ra: )(),(), ~ ( gHWfHWf  (2.2) trong đó: 7  qpg  )( 2 1 )( 2 (2.3)    m b jbHp 1 2 (2.4)    m b jbib HVWHq 1 *)( (2.5) Để giảm tối đa ), ~ ( HWf cần xác định  sao cho g( ) đạt giá trị cực tiểu với điều kiện 0 ~  ijij WW . Do g( ) là hàm bậc hai, nên  có thể đƣợc tính nhƣ sau:                0, 0),,max( 0,0 q p q qw p q q ij (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ó: 0)( g , nếu (q = 0) hoặc (q>0 và ijW =0) (2.7.a) 0)( g , nếu trái lại (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:  ijij HH ~ (2.9) Trong đó  đƣợc xác định theo các công thức :    n a aiWu 1 2 (2.10)    n a ajai VWHWv 1 )( (2.11)               0, 0),,max( 0,0 v u v vH u v v ij (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: ),() ~ , ~ ( HWTHW  đƣợc thực hiện nhƣ sau: Bƣớc 1. Khởi gán HHWW  ~ , ~ Bƣớc 2. Điều chỉnh các phần tử của W ~ Với j=1..r và i=1..n  ijij WW ~~ 8  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  ijij HH ~~  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,...    kkkk HWTHW ,, 11  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: λi d = λmax +αλwi trong đó λmax là phần tử lớn nhất của Dl, α là hệ số, λi d là giá trị chỉnh sửa của Dl. Bƣớc 7. Tính: L d = BlHl d trong đó Hl d =UlDl d Vl ’ , với Dl d = diag(λi d ). 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 ’ 9 Bƣớc 4. Trích các giá trị: λwi * = (λi d - λmax) /α trong đó λi d 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  twwW ,...,1 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:        q R k ii )1,1( Bước 3.2: Điều chỉnh Ri(1,1) thành Ri’(1,1):    qwXORkqkR iiii  2mod)1,1( ' 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 '' iii RQI  , ả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 q R k i i 2 )1,1(* * 2** MODkw ii  Bƣớc 4. So sánh dấu thủy vân  **1* ,..., twwW  trích ra từ I* với dấu thủy vân gốc  twwW ,...,1 tƣơng tự bƣớc 4 trong mục 2.3.1.1.b 10 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)        q x k ii    qwMODkqkx iiii  2 ' 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’: i i X x x X i i ' '  thu đƣợc ma trận Ri’ với hàng đầu là véc tơ ' i X 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: )(...)2()1( nXXXx iiii                q q x k i i 2* trong đó véc tơ * iX gồm các phần từ trên hàng đầu của ma trận * iR :  ),1(),...,2,1(),1,1(* nRRRX iiii  . Bước 3.2: Xác định wi*: 2** MODkw ii  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, . 11 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ò 12 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:      1 , 1, j ji i c e ,       2 1 , 2, j ji i c e bb 4 1 Sb),,1,(i  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à:  2,1, , iii eeE  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.            SbE E E ... 1 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à ),( 2,1, iii ggG  . 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. 11,1,  ji gg (3.1) 22,2,  ji gg (3.2) 13 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:  22 )()( jiji yyxx (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 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:  SGGSjiH ji  ),(|, 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. Fi Fi Fi Fj Fj Fj A A S S S 14 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: PAB  (3.4) trong đó P có dạng nhƣ ma trận Haar:                                78 56 34 12 87 65 43 21 000000 000000 000000 000000 000000 000000 000000 000000 pp pp pp pp pp pp pp pp P (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 122 2 1  pp , 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: ])2[( ])1[( ASum ASum tg  từ đó suy ra: ])2[(])1[( ])1[( sin 22 1 ASumASum ASum p    ])2[(])1[( ])2[( cos 22 2 ASumASum ASum p    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: ])2[(])12[( ])12[( 22 12 iASumiASum iASum p i    15 ])2[(])12[( ])2[( 22 2 iASumiASum iASum p i   , 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: TBQC  ở đây Q cũng có dạng ma trận Haar:                                78 56 34 12 87 65 43 21 000000 000000 000000 000000 000000 000000 000000 000000 qq qq qq qq qq qq qq qq Q (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: ))2( ~ ())12( ~ ( ))12( ~ ( 22 12 iBSumiBSum iBSum q i    ))2( ~ ())12( ~ ( ))2( ~ ( 22 2 iBSumiBSum iBSum q i   , i=1,2,,N/2 (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: TQPAC )( 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.  kjki gg ,, (3.9) trong đó k là số phần từ của véc tơ đặc trƣng. 16 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:  22 )()( jiji yyxx (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à:                b/4)(b/4,LL .,(b/4,2),..LL(b/4,1),LL .... b/4),(2,LL (2,2),...,LL (2,1),L b/4),(1,LL ..., (1,2),LL (1,1), i,2i,2i,2 i,2i,2i,2 i,2i,2i,2 L LL Ei 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.            SbE E E ... 1 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à ),...,( 16/,2,1, 2biiii gggG  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 17 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.9), (3.10) thì lƣu chúng vào một mảng. End End 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 γ. + 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 các cặp chỉ số H1, H2 sao cho: V(Gi, Gj)=S với 1Hi và 2Hj ở đây V(Gi, Gj) là véc tơ dịch chuyển từ vectơ đặc trƣng Gi đến vectơ đặc trƣng Gj. Gọi Fi =Kh(Gi), Fj=Kh(Gj) là các khối ảnh ứng với véc tơ đặc trƣng Gi, Gj. Xây dựng các tập A1, A2 theo công thức: i Hi FA 1 1    , FjA Hj 2 2    Bƣớc này đƣợc minh họa trong Hình 3.7 dƣới đây. Hình 3.7. Vectơ dịch chuyển của vùng cắt/dán 3.4 PHƢƠNG PHÁP DỰA TRÊN PHÉP THỪA SỐ HÓA MA TRẬN KHÔNG ÂM NMF Phép phân tích thừa số hóa ma trận không