Đề tài Tìm hiểu một số phương pháp dò tìm, phát hiện sự giả mạo trong ảnh số

………………….13 Dựa vào dấu vết của quá trình điều chỉnh tỷ lệ…………………………...14 Dựa vào phân tích ánh sáng………………………………………………14 Phần 3: PHÁT HIỆN ẢNH GIẢ MẠO DỰA TRÊN SỰ KHÁCH BIỆT HƯỚNG NGUỒN SÁNG……………………………………..15 Giới thiệu…………………………………………………………………….15 Các loại nguồn sáng………………………………………………………….15 Ước lượng hướng chiều nguồn sáng…………………………………………15 Ước lượng hướng chiều của nguồn sáng………………………………..15 Tìm những đường có khả năng là biên khuất……………………………16 Ước lượng hướng chiều sáng cho từng đường biên tìm được…………..17 Sử dụng mạng Bayes tìm ước lượng tốt nhất……………………………17 Nguồn sáng ở vô tận (3-D)…………………………………………………..17 Nguồn sáng ở vô tận (2-D)………………………………………………….18 Nguồn sáng ở gần (bộ phận) (2-D)………………………………………….20 Nhiều nguồn sáng……………………………………………………………20 Phần 4: PHÁT HIỆN ẢNH GIẢ MẠO DỰA TRÊN THUẬT TOÁN EXACTMATCH………..……………………………………………21 Ý tưởng………………………………………………………………………….21 Thuật toán……………………………………………………………………….22 Phát hiện ảnh giả mạo dựa vào kỹ thuật thay đổi kích thước…………………...22 Thuật toán cải tiến Exacta match* ……………………………………………...24 Kết luận…………………………………………………………………………26 Tài liệu tham khảo…………………………………………………………………..27 LỜI MỞ ĐẦU Với sự phát triển của khoa học công nghệ, ngày càng có nhiều kỹ thuật tiên tiến được ứng dụng vào thực tế và ảnh số là một trong những thành quả đó. Với khả năng của các phần mềm biên tập và sử lý ảnh, các bức ảnh có thể dễ dàng bị sửa chữa và hiệu chỉnh. Các chương trình phần mềm có thể thêm vào hay bỏ đi các đặc trưng của ảnh mà không để lại nhiều dấu vết về sự giả mạo. Người ta tạo những bức ảnh giả mạo nhằm vào nhiều mục đích khác nhau như việc vu cáo, tạo ra các tin giật gân, đánh lừa đối thủ, làm sai lệch chứng cứ phạm tội v.v… Người ta tạo những bức ảnh giả mạo nhằm vào nhiều mục đích khác nhau như việc vu cáo, tạo ra các tin giật gân, đánh lừa đối thủ, làm sai lệch chứng cứ phạm tội v.v… Ví dụ: Tháng 8/2006, một bức ảnh minh họa của Hãng tin Reuters xuất hiện trên các trang báo lớn nhỏ trên khắp thế giới. Nội dung của bức ảnh là những cột khói tỏa lên từ một số tòa nhà cao tầng sau một đợt không kích tại Beirut. Nhưng sau đó họ đã phát hiện ra một phần của bức ảnh đã bị người ta sao chép (copy), rồi cắt dán lặp lại nhiều lần trong bức ảnh, có lẽ tác giả ảnh muốn cho người xem cảm nhận được sự tàn phá và hãi hùng vì... khói. Hình 4: Bức ảnh giả chỉnh sửa nhằm tăng độ mạnh của thông tin chiến tranh Một ảnh giả khác được tạo lập từ 3 bức ảnh: Nhà trắng, Bill Clinton và Saddam Hussein. Hình ảnh Bill Clinton và Saddam Hussein được cắt và dán vào bức ảnh Nhà trắng. Các hiệu ứng về bóng và ánh sáng cũng được tạo ra làm cho bước ảnh có vẻ nhìn gần giống như thật, rất khó nhận biết bằng mắt thường. Một bức ảnh khác mô là hình ghép giữa hai bức ảnh khác nhau xuất hiện trong chiến dịch tranh cử tổng thống Mỹ năm 2004, cho thấy ứng viên John Kerry nói chuyện với cựu nữ diễn viên Jane Fonda tại một cuộc biểu tình phản chiến vào những năm 60 của thế kỷ trước, bên dưới có đóng “nhãn hiệu cầu chứng” là The Associated Press. Hình 5: Ảnh giả của John Kerry và Jane Fonda được cắt ghép từ hai ảnh riêng lẻ Một số cựu binh Mỹ thời chiến tranh Việt Nam phản ứng mạnh bằng thái độ giận dữ khi thấy một ứng viên tổng thống lại chia sẻ diễn đàn với một nữ diễn viên tích cực chống chiến tranh Như vậy ảnh hưởng của những thông tin từ những bức ảnh là rất lớn, thông tin hình ảnh luôn có tác động mạnh và trực tiếp tới con người. Do vậy ảnh được coi là công cụ biểu diễn và truyền đạt thông tin rất phổ biến và hữu dụng. Phần 1: GIỚI THIỆU VỀ XỬ LÝ ẢNH 1.1 Biểu diễn ảnh số Đối với ảnh đơn giản (ảnh đen trắng) thì ảnh được biểu diễn bằng một hàm cường độ sáng hai chiều , trong đó là các giá trị toạ độ không gian và hàm giá trị của tại một điểm bất kỳ sẽ tỷ lệ với độ sáng hay mức xám của điểm ảnh tại điểm này. [2,4] * P(X,Y) Hình 1: Biểu diễn ảnh bằng hàm Trong mộ số trường hợp hàm ảnh còn được biểu diễn với một trục thứ 3 gọi là hàm cường độ sáng (với hình 1.1, trục thứ 3 bằng 0). Một ảnh số là một ảnh được gián đoạn theo không gian và cường độ sáng. Một ảnh số được xem như một ma trận với hàng và cột biểu diễn một điểm trong ảnh và giá trị điểm ma trận tương ứng với mức xám tại điểm đó. Các phần tử của một dãy số như thế được gọi là các điểm ảnh. Ánh sáng có dạng năng lượng phải khác 0 và hữu hạn: Con người có khả năng nhận các hình ảnh từ ánh sáng phản xạ qua các vật thể. Cơ sở của được đặc trưng qua hai thành phần: Số lượng ánh sáng nguồn rơi trên cảnh vật được nhìn thấy. Số lượng ánh sáng nguồn phản xạ từ vật thể ( trong cảnh vật). Chúng được gọi gần đúng là sự phát sáng và các thành phần phản xạ, và được biểu diễn tương ứng là và . Bản chất của được xác định bằng nguồn sáng và của được xác định bằng các đặc trưng của vật thể. Hàm và kết hợp với nhau để cho hàm Với: Ở đây ta gọi cường độ sáng của một ảnh đen trắng tại tọa độ là mức xám của ảnh tại điểm đó. Từ , nằm trong khoảng: Trong lý thuyết, chỉ cần và hữu hạn. Trong thực tế: Sử dụng các giá trị chiếu sáng và phản xạ đã được tổng kết qua thực nghiệm hoặc xem là các giá trị cơ bản cho xử lý ảnh. Khoảng được gọi là thang xám. Ta có thể dịch khoảng này đến , trong đó là đen và là trắng trong thang xám. Giá trị tức thời là các dạng mức xám thay đổi liên tục từ đen đến trắng. 1.2 Một số khái niệm cơ sở trong xử lý ảnh Để có thể xử lý bằng máy tính điện tử thì ảnh cần phải được số hóa. Đó là quá trình biến đổi ảnh từ tín hiệu liên tục sang tín hiệu rời rạc thông qua việc lấy mẫu và lượng tử hóa. Trong quá trình này người ta sử dụng khái niệm “pixel”. Mỗi pixel được đặc trưng bởi một cặp tọa độ và màu sắc của nó.[4] Ảnh: Là một tập hợp các pixel có cấu trúc, ta có thể coi ảnh là một mảng hai chiều có dòng và cột, ảnh sẽ có (pixel). Ta ký hiệuđể chỉ điểm ảnh có toạ độ .[4] Mức xám (Gray level): Đó là kết quả của việc mã hóa, cho tương ứng một cường độ sáng của mỗi điểm ảnh với một giá trị số, có thể là 16, 32, 64 mức. Biểu diễn ảnh: Trong biểu diễn ảnh người ta thường sử dụng các phần tử đặc trưng của ảnh là pixel. Một hàm hai biến chứa các thông tin như một biểu diễn ảnh. Một số mô hình thường dùng để biểu diễn ảnh là mô hình toán (biểu diễn ảnh nhờ các hàm cơ sở), mô hình thống kê (ảnh coi như một phần tử của một tập hợp đặc trưng bởi kỳ vọng toán, hiệp biến, phương sai, moment…).[4] Tăng cường ảnh: Đây là một bước quan trọng bao gồm các kỹ thuật lọc độ tương phản, khử nhiễu, nổi màu…. Biến đổi ảnh: Thao tác chủ yếu trên một tập các ma trận và sử dụng các kỹ thuật để biến đổi ảnh qua ma trận: Biến đổi Furie, Sin, Cosin, tích Kronecker. Phân tích ảnh: Liên quan tới việc xác định các độ đo định lượng của một ảnh để đưa ra một mô tả đầy đủ về ảnh. Có những kỹ thuật cơ bản để hỗ trợ phân tích ảnh: Dò biên, lọc vi phân, dò theo quy hoạch động, phân vùng ảnh [4] Nhận dạng ảnh: Quá trình này liên quan đến các mô tả đối tượng mà người ta muốn đặc tả nó. Nhận dạng ảnh thường đi sau các quá trình trích chọn các đặc trưng chủ yếu của đối tượng.[1,4] 1.3 Các giai đoạn trong xử lý ảnh Bài toán xử lý ảnh bao gồm các giai đoạn tổng quát như sau [1,2,4] Scanner, Camera Cơ sở tri thức Nhận dạng và nội suy Phân đoạn Tiền xử lý Biểu diễn Thu nhận ảnh Kết quả Hình 2: Các bước cơ bản trong xử lý ảnh số Bước đầu tiên là thu nhận ảnh, thu ảnh số bằng bộ cảm biến ảnh với khả năng số hóa tín hiệu của bộ cảm biến. Sau khi nhận được một ảnh số, bước tiếp theo là tiền xử lý ảnh. Mục đích chủ yếu của giai đoạn tiền xử lý ảnh là nâng cao khả năng để các quá trình tiếp theo đạt kết quả tốt, như các quá trình khử nhiễu, tăng độ tương phản…. Bước tiếp theo là phân đoạn: Phân đoạn ảnh là tách một ảnh đầu vào thành các phần hoặc các vật thể. Đầu ra của quá trình phân đoạn ảnh thường là số liệu pixel chưa lọc, bao gồm cả các liên kết của vùng hoặc tất cả các điểm ảnh trong vùng đó. Cuối cùng, ảnh sẽ được phân lớp, nhận dạng cho các mục đích khác nhau. Tri thức về phạm vi vật thể được mã hóa thành một hệ thống xử lý trong ảnh dưới dạng cơ sở dữ liệu kiến thức. Để xử lý các quá trình trên thì cần một hệ thống xử lý ảnh bao gồm một số thành phần cơ bản sau đây:[4] Máy in Bộ xử lý ảnh số Bộ nhớ ảnh Màn hình Bàn phím Máy chủ Bộ xử lý tương tự Màn hình đồ họa Camera Bộ nhớ ngoài Hình 3: Các thành phần cơ bản của một hệ xử lý ảnh Bộ xử lý tương tự thực hiện các chức năng: - Chọn Camera thích hợp nếu có nhiều Camera - Chọn màn hình hiển thị tín hiệu - Thu nhận tín hiệu video bởi bộ số hóa. Thực hiện lấy mẫu và mã hóa - Tiền xử lý ảnh khi thu nhận Bộ xử lý ảnh số bao gồm nhiều bộ xử lý chuyên dụng: Xử lý lọc, trích chọn đặc trưng, nhị phân hóa ảnh. Máy chủ đóng vai trò điều khiển các thành phần khác. Bộ nhớ ngoài: Lưu trữ dữ liệu ảnh cũng như các kiểu dữ liệu khác để có thể chuyển giao cho các quá trình có nhu cầu. Phần 2: BÀI TOÁN PHÁT HIỆN ẢNH GIẢ MẠO 2.1 Bài toán phát hiện ảnh giả mạo Ảnh giả mạo được chia làm 2 loại: Thứ nhất, đó là ảnh giả mạo nhưng thật, được dàn dựng một cách có ý đồ sau đó thu nhận ảnh và không thực hiện thao tác chỉnh sửa trực tiếp trên ảnh thu nhận được. Thứ hai, ảnh giả mạo được tạo ra từ việc có tác động lên ảnh nhằm thay đổi nội dung và bản chất bức ảnh dựa trên các kỹ thuật xử lý ảnh (cắt, dán, ghép, thêm, bớt, chỉnh sửa). Trong đề tài nghiên cứu này chỉ quan tâm xác định những bức ảnh giả mạo thuộc loại thứ 2. 2.2 Hướng tiếp cận bài toán 2.2.1 Dựa vào hình dạng Việc phân tích để xác định tính giả mạo có thể dựa vào hình dạng vì việc cắt dán và ghép ảnh thường được thực hiện dựa theo các đường biên, nơi có sự thay đổi không liên tục của cường độ sáng của các điểm ảnh. 2.2.2 Dựa vào phân tích nguồn sáng Việc ghép các ảnh khác nhau hoặc bổ sung thêm đối tượng không phải thực hiện thao tác copy có thể được thực hiện bằng việc phân tích nguồn sáng đối với từng đối tượng, các đối tượng được ghép thường có hướng của nguồn sáng không cùng với các đối tượng trong ảnh gốc. 2.2.3 Dựa vào biến đổi màu sắc Ảnh gốc thu nhận thường được thực hiện bởi một thiết bị. Do tính chất biến đổi của ống kính bao gồm góc độ chụp, độ mở v.v.. nên ảnh thu được thường bị biến dạng theo các tính chất đặc trưng của các nhà sản xuất. Phần ảnh được ghép vào hay bổ sung thường không có sự biến đổi tương đồng về độ sáng. 2.2.4 Dựa vào cơ sở dữ liệu Việc giả mạo ảnh thường dựa vào các ảnh đã có, tức là các ảnh đã được xuất bản bởi một nơi nào đó như: Báo chí, trang Web, tạp chí v.v.. Các ảnh này đã được lưu trữ nên khi xuất hiện một ảnh nghi là giả mạo người ta có thể tìm ảnh này với các phần trong nguồn ảnh nằm trong cơ sở dữ liệu ảnh. Hình 7: Sơ đồ việc phát hiện giả mạo dựa vào cơ sở dữ liệu 2.2.5 Dựa vào dấu vết của quá trình điều chỉnh tỷ lệ Khi cắt ghép các đối tượng từ hai hay nhiều bức ảnh để được một bức ảnh giả người ta phải quan tâm tới việc điều chỉnh kích thước, màu sắc của các đối tượng trên các bức ảnh gốc được cắt ra để cho phù hợp với nhau khi được ghép trên cùng một bức ảnh. 2.2.6 Dựa vào phân tích ánh sáng Qua phân tích sự đồng đều của ánh sáng phân bố trên các phần khác nhau của bức ảnh có thể thực hiện bằng hai cách. Cách thứ nhất là phân tích bóng đổ để tìm ra hướng của nguồn sáng. Hình 8: Hướng nguồn sáng Cách thứ hai là nghiên cứu các chấm sáng trong con ngươi mắt người. Mắt là một phần tấm gương soi vào thế giới ẩn chứa chủ thể được chụp. Ngoài ra, màu của ánh sáng có thể xác định bóng trắng chính xác của các chấm sáng. Một ảnh tổng hợp từ nhiều ảnh khác nhau sẽ có bóng sắc thay đổi từ người này sang người khác. Phần 3: PHÁT HIỆN ẢNH GIẢ MẠO DỰA TRÊN SỰ KHÁC BIỆT HƯỚNG NGUỒN SÁNG 3.1 Giới thiệu Vấn đề ước lượng hướng nguồn sáng là một lĩnh vực nghiên cứu lớn của thị giác máy tính. Trong phần này sẽ mô tả bài toán, đề xuất giải pháp và sau đó sẽ trình bày cách thức để loại bỏ các yếu tố ngoại cảnh, làm đơn giản hóa các điều kiện để hạn chế những phức tạp trong quá trình xử lý. 3.2 Các loại nguồn sáng Ý tưởng phát hiện ảnh giả mạo ở trên là dựa vào nguồn sáng, tuy nhiên thuật toán này không áp dụng giống nhau cho tất cả các loại nguồn sáng được. Trong nguồn sáng đơn chúng ta lại chia thành hai loại: nguồn sáng ở rất xa (xa vô hạn) và nguồn sáng ở gần. 3.3 Ước lượng hướng chiếu nguồn sáng 3.3.1 Ước lượng hướng chiếu của nguồn sáng Phần này trình bày thuật toán ước lượng tự động hướng chiếu của nguồn sáng đối với một ảnh đơn. Thuật toán gồm ba bước. Đầu tiên tìm ra những đường có khả năng là biên khuất với xác suất cao nhất. Sau đó với mỗi đường biên khuất chúng ta sẽ ước lượng véc-tơ chỉ hướng chiếu của nguồn sáng theo mô hình bóng đổ. Cuối cùng các ước lượng đó được đưa vào mô hình mạng Bayet để tìm một ước lượng thích hợp nhất cho hướng chiếu của nguồn sáng. Điều kiện là đối tượng phải có bề mặt Lambertian, đồng thời toàn bộ bề mặt có hệ số phản chiếu là hằng số. 3.3.2 Tìm những đường có khả năng là biên khuất Nhiệm vụ của bước này là tìm ra những đường có khả năng là biên khuất. Có thể không tìm ra chính xác biên khuất nhưng cũng phải đưa ra những đường đủ tốt cho bước tiếp theo. Thuật toán phát hiện cạnh Canny gồm 6 bước như sau: Bước 1: Bước đầu tiên trong thuật toán phát hiện cạnh Canny là khử nhiễu và làm phẳng ảnh ban đầu trước khi cố gắng xác định và định vị bất kỳ một cạnh nào đó. Bước 2: Sau khi làm phẳng và khử nhiễu ảnh, bước tiếp theo là phải tìm ra độ dài của cạnh bằng việc lấy hướng của ảnh. Bước 3: Tìm hướng của cạnh. Một khi chúng ta đã biết hướng của cạnh theo trục x và trục y thì hướng của cạnh sẽ dễ dàng tính được Bước 4: Khi hướng của cạnh được tìm ra, bước tiếp theo là liên kết hướng đó với một mà có thể lần ra ảnh. Bước 5: Sau khi đã biết hướng cạnh thuật toán tiếp tục như sau: đi dọc cạnh theo hướng cạnh, nếu gặp bất kỳ điểm ảnh nào mà không liên quan đến cạnh thì khử điểm ảnh đó đi (tức là cho giá trị điểm ảnh bằng 0). Việc này sẽ cho chúng ta một đường mảnh ở ảnh kết quả. Bước 6: Cuối cùng là khử sự tạo thành vạch. Sự tạo thành vạch sẽ phá vỡ cạnh, gây ra do sự dao động giữa ngưỡng trên và ngưỡng dưới. Đó là thuật toán phát hiện cạnh Canny. Sau khi đã trích ra được các cạnh, chúng ta sẽ nhóm các cạnh đó thành chuỗi theo luật sau: Vùng tiếp theo cạnh sẽ đồng màu. Màu sẽ giống với màu của cạnh kế trước trong chuỗi. Vùng tiếp theo cạnh không chứa cạnh khác. Trong chuỗi không tạo nên những chỗ gấp khúc. Việc này được thực hiện trên cả các mặt phẳng của các cạnh. 3.3.3 Ước lượng hướng chiếu sáng cho từng đường biên tìm được Sau khi tìm ra các đường biên khuất (có khả năng là biên khuất) chúng sử dụng mô hình bóng đổ cho các đường biên này để tìm ra hướng chiếu sáng cho từng đường biên. Đo cường độ sáng trên biên khuất Theo cách trên muốn ước lượng được hướng chiếu của nguồn sáng chúng ta cần phải có cường độ sáng trên biên khuất. Tất nhiên điều này là không thể, chúng ta không thể đo trực tiếp cường độ sáng trên biên khuất, mà phải ngoại suy từ các điểm ở xa biên. 3.3.4 Sử dụng mạng Bayes tìm ước lượng tốt nhất Sau bước 2 chúng ta có một tập hợp các ước lượng và hiệp phương sai của n chuỗi cạnh mà có thể hoặc không là biên khuất. Để có thể tìm ra biên khuất chính xác từ tập hợp n chuỗi đó ta cần chú ý một điều là đối với đường biên khuất chính xác, nói chung sẽ có hiệp phương sai nhỏ hơn và phù hợp với mô hình hơn là những đường không chính xác. 3.4 Nguồn sáng ở vô tận (3-D) Hướng chuẩn hóa cho việc ước lượng hướng nguồn sáng bắt đầu từ việc xây dựng một số giả thuyết đơn giản: + Bề mặt của đối tượng phản xạ ánh sáng đẳng hướng (bề mặt Lambertian) + Bề mặt của đối tượng có một hằng số phản xạ + Bề mặt được chiếu bởi nguồn sáng điểm ở xa vô hạn + Góc giữa bề mặt và hướng của nguồn sáng trong khoảng từ 0 đến 90 độ Với những giả thuyết như vậy, mật độ ảnh có thể được mô tả bởi: Với: + R là hằng số phản xạ + là véctơ 3 chiều chỉ hướng của nguồn sáng + là véctơ pháp tuyến của bề mặt tại điểm +A là hằng số giới hạn ánh sáng xung quanh 3.5 Nguồn sáng ở vô tận (2-D) Chúng ta có thể ước lượng được hai thành phần ( ) của hướng nguồn sáng chỉ cần dựa trên một bức ảnh duy nhất. Thành phần z của bề mặt chuẩn được giả định bằng 0, . Khi đó các thành phần x, y của bề mặt chuẩn (có thể được ước lượng một cách trực tiếp từ ảnh (hình 12b). Hình 12: Mô hình minh họa cho: Nguồn sáng vô tận (3-D), Nguồn sáng vô tận (2-D), và nguồn sáng cục bộ (2-D). Trong trường hợp 2-D, thành phần z của bề mặt bằng 0. Không giống trường hợp nguồn sáng vô tận, hướng của nguồn sáng ( biến đổi từ bên này qua bên kia của bề mặt hình cầu Đơn giản hóa những giả định về hằng số độ tương phản Thay vì coi toàn bộ bề mặt của đối tượng có cùng hằng số độ tương phản, mỗi phần của bề mặt có độ tương phản là hằng số. Ta sẽ ước lượng hướng của nguồn sáng bộ phận( ) từ việc xem xét từng phần của bề mặt đối tượng. 3.6 Nguồn sáng ở gần (bộ phận) (2-D) Với các phần trên, giả định nguồn sáng xuất phát từ vô tận. Với nguồn sáng bộ phận, các công thức trên trên không còn phù hợp(hình 13.c). Hình 13: Hai đối tượng được chiếu bởi 1 nguồn sáng ở gần. 3.7 Nhiều nguồn sáng Trong những phần trên ta giả định rằng chỉ có ánh sáng phát ra từ một nguồn sáng duy nhất chiếu lên vật thể và các nguồn sáng khác coi không đáng kể và được xem xét với hằng số giới hạn ánh sáng xung quanh (A), điều này thường phù hợp với ánh sáng ngoài trời. Nhưng xảy ra trường hợp đối tượng được chiếu rọi bởi nhiều nguồn sáng. Ánh sáng có thuộc tính rất đặc biệt đó là tuyến tính. Giả sử có 2 nguồn sáng chiếu lên đối tượng, khi đó hàm mật độ ảnh có dạng: Khi đó ta xử lý với giả định rằng hai nguồn sáng đã kết hợp lại và cho ta một nguồn sáng chung duy nhất với phương pháp xác định hướng nguồn sáng tương tự những phần trước. Phần 4: PHÁT HIỆN ẢNH GIẢ MẠO DỰA TRÊN THUẬT TOÁN EXACT MATCH 4.1 Ý tưởng Giả sử bức ảnh có kích thước , với là kích thước nhỏ nhất của khối bao mà người dùng định nghĩa để đối sánh. với mỗi điểm ảnh ta xác định được một khối bao ma trận điểm ảnh. Như vậy với bức ảnh ta xác định được khối bao. Với mỗi khối bao ta lưu các phần tử thuộc khối bao vào một hàng của một ma trận A. Vậy duyệt trên toàn bộ bức ảnh ta sẽ được một ma trận A với hàng và cột. Hai hàng giống nhau trong ma trận A tương đương với 2 khối bao giống nhau trong ảnh. Chúng ta sắp xếp các hàng trong ma trận A theo thứ tự từ điển, yêu cầu này sẽ được thực hiện trên bước. Sau đó ta dễ dàng tìm kiếm bằng cách duyệt hàng của ma trận đã qua sắp xếp A và tìm kiếm hai hàng giống nhau liên tiếp. Kết quả thuật toán sẽ tìm kiếm và đưa ra được tập các vùng bao giống nhau là bằng chứng chứng minh ảnh đã bị cắt dán. Hình 2. Minh họa cho việc tìm kiếm khối bao của thuật toán Extract macth 4.2. Thuật toán Thuật toán Extract match nhằm tìm ra các khối bao giống nhau trên cùng một ảnh, bao gồm các bước sau: Bước 1: Lựa chọn kích thước khối bao nhỏ nhất. Bước 2: Xác định tập các khối bao dựa trên kích thước khối bao nhỏ nhất. Bước 3: Đưa mỗi khối bao vào một hàng của mảng lưu xác định. Bước 4: Sắp xếp các hàng trong mảng lưu ở bước 3 theo thứ tự tăng dần. Bước 5: Kiểm tra hai hàng liên tiếp trong mảng lưu sau khi đã sắp xếp, nếu chúng giống nhau thì đưa ra 2 tập khối bao giống nhau tương ứng. 4.3 Phát hiện ảnh giả mạo dựa vào kỹ thuật thay đổi kích thước Thuật toán Exact match trình bày ở mục 2 thường phát hiện khá tốt với các ảnh giả mạo dạng cắt dán, nhưng không có sự thay đổi về kích thước. Trong trường hợp vùng cắt dán có thay đổi về kích thước thì thuật toán không phát hiện được sự giả mạo. ٭ Các kỹ thuật thay đổi kích thước Việc thay đổi kích thước một vùng ảnh thường sử dụng kỹ thuật nội suy tuyến tính xác định để ánh xạ ảnh từ miền không gian này sang miền không gian khác. Các kỹ thuật nội suy được sử dụng trong trong PhotoShop là: Láng giềng gần nhất (nearest neighbor), nội suy tuyến tính (bilinear interpolation) và Bicubic. (x,y) Hình 4. Mô hình ánh xạ các điểm ảnh từ ảnh gốc sang ảnh đích Nearest-neighbor Kỹ thuật này được diễn tả như sau: với mỗi điểm ảnh từ ảnh gốc sẽ tương ứng với một vị trí phù hợp trong ảnh đích (ảnh đã được thay đổi kích thước). các giá trị màu và tín hiệu của một điểm ảnh trong ảnh mới sẽ được gán bằng giá trị màu của điểm ảnh gần nhất (láng giềng gần nhất) thuộc ảnh gốc tương ứng. Bilinear interpolation Đây là phương pháp phức tạp hơn nearest neighbor. Phương pháp này xác định giá trị của một điểm ảnh mới dựa trên trung bình trọng số của 4 điểm ảnh láng giềng gần nhất 2x-2 của điểm ảnh thuộc ảnh gốc. Chúng ta miêu tả chi tiết phương pháp nội suy bilinear như sau: Giả sử với mỗi điểm (x,y) thuộc ảnh gốc ta xác định được các giá trị ánh xạ tương ứng (X,Y) thuộc ảnh đích theo phép biến đổi sau: Với là các hàm tuyến tính. Giả sử u và v lần lượt là các phần nguyên của X và Y.Thuật toán nội suy bilinear được định nghĩa như sau: Trong đó: Bicubic interpolation Với phương pháp này bức ảnh sẽ được chia làm các khối hình vuông kích thước 4x4. Phương pháp này có thể được tính theo mô hình “hàng-hàng“ (row-by-row) và sau đó là “cột-cột” (column-by-column). Chúng ta giả sử rằng các cường độ tại u-1,u,u+1,u+2 lần lượt là I(u-1), I(u), I(u+1), I(u+2) , Cường độ tại 0<X<1 sẽ được ước lượng từ phương trình sau: Trong đó: , 4.4 Thuật toán cải tiến Exact match* Khi thay đổi kích thước ảnh, PhotoShop thường sử dụng 1 trong các kỹ thuật nội suy được trình bày ở mục 3.1. ở trên. Dựa vào đó ta tìm kiếm các cặp vùng trong ảnh có mối quan hệ tương quan theo một phương pháp nội suy xác định. Một vùng được gọi là vùng tương quan nếu nó tồn tại ít nhất một vùng và một phép biến đổi, tương ứng khác sao cho : Trong đó là hệ số tỷ lệ, và phép ánh xạ theo một phương pháp nội suy xác định là một trong các kỹ thuật nội suy. Khi đó cặp vùng được gọi là cặp tương quan. Thuật toán Exact match * Trên cơ sở ý tưởng trên, thuật toán thực hiện các bước sau: Bước 1: Lựa chọn các thông số đầu vào bao gồm : Kích thước khối bao nhỏ nhất B, các tỷ lệ co giãn theo chiều ngang và chiều dọc là p,q và một phương pháp nội suy f. Bước 2: Xác định 2 tập hợp các khối bao, bao gồm một tập hợp các khối bao có kích thước tối thiểu B ´ B và một tập hợp các khối bao có kích thước pB ´ qB trên toàn bộ ảnh. Bước 3: Biến đổi tập các khối bao có kích thước B ´ B sang tập các khối bao mới theo phép biến đổi nội suy và các thông số về tỷ lệ co giãn theo chiều ngang và chiều dọc đã cho trong bước 1. Bước 4: Đối sánh các cặp khối bao, mỗi cặp khối bao gồm một khối bao thuộc tập hợp các khối bao sau khi biến đổi ở bước 3 và một khối bao thuộc tập hợp các khối bao có kích thước pB ´ qB trong bước 2. Nếu chúng giống nhau thì đưa ra được cặp hai khối bao tương ứng gồm : một khối bao thuộc tập các khối bao có kích thước B ´ B tạo ra ở bước 2 và một khối bao thuộc tập các khối bao có kích thước pB ´ qB tạo ra trong bước 2. 4.5 Kết luận Với sự phát triển của khoa học công nghệ, ngày càng có nhiều kỹ thuật của khoa học công nghệ được ứng dụng vào thực tế và ảnh số chính là một trong những thành quả đó. Ảnh số ngày càng dễ sửa chữa và hiệu chỉnh do sức mạnh của các phần mềm soạn thảo và xử lý ảnh mà điển hình là PhotoShop. Do vậy mà bài toán phát hiện ảnh giả mạo đã trở nên cấp thiết và ngày càng khó khăn. Trên cơ sở nghiên cứu các kỹ thuật nội suy hiện đang được PhotoShop sử dụng trong việc thay đổi kích thước vùng ảnh. Tôi đề xuất một cải tiến cho thuật toán phát hiện ảnh giả mạo Exact match. Thuật toán mà tôi đề xuất có khả năng phát hiện đối với các ảnh giả mạo dạng cắt dán từ chính một ảnh và có sự thay đổi về kích thước đối với các đối tượng bị cắt dán. Đây cũng chính là cách thường được các đối tượng sử dụng trong quá trình tạo ảnh số giả nhờ kỹ thuật cắt dán. Tài liệu tham khảo Ardy Goshtasby (2004), ”Image Resampling”, Wright State University and Image Fusion System Research .june 27.2004 aJessica Fridrich, bDavid Soukal, and aJan Lukáš, ”Detection of Copy-Move Forgery in Digital Images”.. Alin C Popescu and Hany Farid, "Exposing Digital Forgeries by Detecting Duplicated Image Regions", Department of Computer Science Dartmouth College ,Hanover NH 03755. Alin C.Popescu and Hany Farid, "Exposing Digital Forgeries by Detecting Traces of Re-sampling". Fridrich (1999), “Methods for "Methods for Tamper Detection in Digital Images", Proc. ACM Workshop on Multimedia and Security, Orlando, FL, October 30-31, 1999, pp. 19-23. Daniel R. Steinwand1, "A New Approach to Categorical Resampling",USGS EROS Data Center SAIC Sioux Falls, SD 57198 steinwand@usgs.gov E. G. Keys (1981), "Cubic convolution interpolation for digital image processing", IEEE Trans. Acoustics, Speech, and Signal Processing, 29(6):1153–1160 (1981). H. S. Hou and H. C. Andrews (1978), Cubic splines for image interpolation and digital filtering, IEEE Trans. Acoustics, Speech, and Signal Processing, 26(6):508–517 (1978). L. A. Ferrari, P. V. Sankar, J. Sklansky, and S. Leeman (1986), Efficient twodimensional filters using B-spline functions, Computer Vision, Graphics, and Image Processing, 35:152–169 (1986). F. Cheng and A. Goshtasby (1989), A parallel B-spline surface fitt