Tài liệu Phát hiện ảnh giả mạo dựa trên mẫu nhiễu cảm biến

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ CÚC PHÁT HIỆN ẢNH GIẢ MẠO DỰA TRÊN MẪU NHIỄU CẢM BIẾN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - Năm 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ CÚC PHÁT HIỆN ẢNH GIẢ MẠO DỰA TRÊN MẪU NHIỄU CẢM BIẾN Ngành : Công nghệ thông tin Chuyên ngành : Hệ thống thông tin Mã số : 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. ĐỖ NĂNG TOÀN Hà Nội - Năm 2014 1 LỜI CẢM ƠN Trước tiên, tôi xin gửi lời cảm ơn Thầy PGS.TS. Đỗ Năng Toàn là người đã định hướng nghiên cứu và tận tình hướng dẫn cho tôi trong suốt quá trình làm luận văn. Nếu không có sự giúp đỡ tận tình của thầy, tôi khó có thể hoàn thành luận văn này. Đồng thời tôi cũng xin chân thành cảm ơn các thầy cô Khoa Công nghệ thông tin – Trường Đại học Công nghệ đã tận tình giảng dạy và cung cấp cho tôi những kiến thức cần thiết trong suốt thời gian học tập tại trường. Cuối cùng xin gửi lời cảm ơn chân thành đến gia đình, cơ quan, bạn bè và đồng nghiệp đã tạo điều kiện, giúp đỡ và động viên tôi trong suốt thời gian học tập cũng như trong thời gian nghiên cứu luận văn. Tuy có nhiều cố gắng nhưng do thời gian và kiến thức của bản thân còn nhiều hạn chế nên trong luận văn không tránh khỏi những thiếu sót. Kính mong nhận được sự góp ý của thầy cô và các bạn để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn ! Phạm Thị Cúc 2 LỜI CAM ĐOAN Tôi xin cam đoan: Bản luận văn tốt nghiệp này là kết quả nghiên cứu thực sự của cá nhân, được thực hiện trên cơ sở nghiên cứu lý thuyết, cài đặt thực nghiệm chương trình. Kết quả của luận văn là cả một quá trình nghiên cứu nghiêm túc các kiến thức được học ở trường và dưới sự hướng dẫn khoa học của PGS.TS Đỗ Năng Toàn. Các số liệu trong luận văn là trung thực, có nguồn gốc rõ ràng, được trích dẫn và có tính kế thừa, phát triển từ các tài liệu, tạp chí, các công trình nghiên cứu đã được công bố, các website,…. Dữ liệu để thực nghiệm có nguồn gốc rõ ràng và không mang tính chất thương mại. Học viên Phạm Thị Cúc 3 MỤC LỤC LỜI CẢM ƠN ............................................................................................................................................ 1 LỜI CAM ĐOAN...................................................................................................................................... 2 DANH MỤC CÁC HÌNH ....................................................................................................................... 5 DANH MỤC CÁC TỪ VIẾT TẮT ...................................................................................................... 6 LỜI NÓI ĐẦU............................................................................................................................................ 7 CHƯƠNG 1: KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ ẢNH GIẢ MẠO.......................................... 9 1.1. Xử lý ảnh và một số vấn đề cơ bản trong xử lý ảnh ........................................................ 9 1.1.1. Một số khái niệm cơ bản .......................................................................................... 9 1.1.2. Một số vấn đề cơ bản trong xử lý ảnh .................................................................... 10 1.1.3. Các giai đoạn trong xử lý ảnh ................................................................................. 15 1.1.3.1. Thu nhận ảnh ................................................................................................... 15 1.1.3.2. Tiền xử lý......................................................................................................... 15 1.1.3.3. Phân đoạn ảnh.................................................................................................. 16 1.1.3.4. Biểu diễn và mô tả ........................................................................................... 17 1.1.3.5. Cơ sở trí thức ................................................................................................... 17 1.1.3.6. Nhận dạng và nội suy ảnh................................................................................ 18 1.1.3.7. Trích chọn đặc trưng........................................................................................ 18 1.2. Ảnh giả mạo và các dạng giả mạo ảnh cơ bản .............................................................. 20 1.2.1. Ảnh giả mạo ........................................................................................................... 20 1.2.2. Các loại ảnh giả mạo cơ bản ................................................................................... 22 1.2.2.1. Ghép ảnh .......................................................................................................... 22 1.2.2.2. Tăng cường ảnh ............................................................................................... 22 1.2.2.3. Sao chép và dịch chuyển vùng trên ảnh .......................................................... 23 CHƯƠNG 2: CÁC KỸ THUẬT PHÁT HIỆN ẢNH SỐ GIẢ MẠO ...................................... 25 2.1. Dựa trên đặc trưng điểm ảnh (Pixel Based)................................................................... 25 2.1.1. Nhân bản (Cloning) ................................................................................................ 25 2.1.2. Lấy mẫu lại (Re-sampling) ..................................................................................... 26 2.1.3. Ghép (Splicing) ...................................................................................................... 26 2.2. Dựa trên định dạng ảnh (Format Based) ....................................................................... 27 2.2.1. Lượng tử hóa JPEG (JPEG quantization) ............................................................... 27 2.2.2. Phần đầu ảnh JPEG (JPEG Header) ...................................................................... 28 2.2.3. Nén kép (Double JPEG) ......................................................................................... 30 2.2.4. Hiệu ứng khối JPEG (JPEG Blocking)................................................................... 30 2.3. Dựa trên đặc điểm máy ảnh (Máy ảnh-Based) .............................................................. 31 2.3.1. Quang sai màu (Chromatic Aberration) ................................................................. 31 2.3.2. Mảng lọc màu (Color Filter Array) ........................................................................ 33 2.3.3. Đáp ứng của máy ảnh (Máy ảnh Response) .......................................................... 33 2.3.4. Mẫu nhiễu cảm biến (Sensor Pattern Noise) .......................................................... 34 2.4. Một số phương pháp trực quan khác ............................................................................. 34 2.4. 1. Nguồn sáng ............................................................................................................ 35 2.4.2. Hướng mắt nhìn và vị trí ........................................................................................ 36 2.4.3. Hình học ................................................................................................................. 36 4 CHƯƠNG 3: PHÁT HIỆN ẢNH GIẢ MẠO DỰA VÀO MẪU NHIỄU CẢM BIẾN ........ 37 3.1. Giới thiệu ....................................................................................................................... 37 3.2. Mẫu nhiễu và các phương thức biểu diễn ...................................................................... 38 3.2.1. Xử lý tín hiệu trong máy ảnh kỹ thuật số ............................................................... 38 3.2.2. Mẫu nhiễu cảm biến ............................................................................................... 39 3.2.3. Dò tìm mẫu nhiễu ................................................................................................... 41 3.3. Thuật toán phát hiện ảnh giả mạo dựa vào mẫu nhiễu cảm biến................................... 43 3.3.1. Tạo các mẫu tham chiếu của máy ảnh .................................................................... 43 3.3.2. Thuật toán nhận dạng ảnh giả ................................................................................. 45 3.4. Chương trình thực nghiệm............................................................................................. 47 3.4.1. Bài toán ................................................................................................................... 47 3.4.2. Công cụ và dữ liệu thử nghiệm .............................................................................. 47 3.4.3. Kết quả thử nghiệm ............................................................................................... 48 KẾT LUẬN............................................................................................................................................... 52 TÀI LIỆU THAM KHẢO .................................................................................................................... 53 5 DANH MỤC CÁC HÌNH Hình 1.1. Quá trình xử lý ảnh ................................................................................................... 10 Hình 1.2. Biểu diễn ảnh bằng hàm f ( X , Y ) ............................................................................ 10 Hình 1.3. Ảnh thu nhận và ảnh mong muốn............................................................................. 12 Hình 1.4. Các bước cơ bản trong xử lý ảnh số ......................................................................... 15 Hình 1.5. Các thành phần cơ bản của một hệ xử lý ảnh ........................................................... 19 Hình 1.6. Minh họa về việc giả mạo ảnh .................................................................................. 20 Hình 1.7. Ảnh giả của John Kerry và Jane Fonda được cắt ghép từ hai ảnh riêng lẻ............... 21 Hình 1.8. Ghép ảnh từ hai ảnh riêng rẽ .................................................................................... 22 Hình 1.9. Ví dụ về tăng cường ảnh ........................................................................................... 23 Hình 1.10. Ảnh che phủ và bỏ đi đối tượng ............................................................................ 24 Hình 1.11. Ảnh bổ sung đối tượng .......................................................................................... 24 Hình 2.1. Mô phỏng sử dụng quang sai để phát hiện ảnh giả .................................................. 32 Hình 2.2. Mô phỏng hướng nguồn sáng tới bề mặt một quả cầu ............................................. 35 Hình 2.3. Mô phỏng việc phân tích nguồn sáng để phát hiện ảnh giả...................................... 35 Hình 3.1. Quy trình xử lý tín hiệu của máy ảnh kỹ thuật số..................................................... 38 Hình 3.2. Mô hình mẫu nhiễu ................................................................................................... 39 Hình 3.3. Minh họa vùng R được chọn và mẫu nhiễu tham chiếu tương ứng của nó.............. 42 Hình 3.4. Hình ảnh minh họa chọn các vùng Qi và mẫu tham chiếu  ................................. 42 Hình 3.5. Mô hình tạo mẫu tham chiếu của máy ảnh ............................................................... 44 Hình 3.6. Sơ đồ bài toán phát hiện ảnh giả mạo ....................................................................... 47 Hình 3.7. Ảnh giả mạo bằng cách cắt ghép và lấy mẫu lại. ..................................................... 49 Hình 3.8. Các hình gốc dùng để tạo ảnh giả ............................................................................. 49 Hình 3.9. Minh họa kết quả chương trình với ảnh giả mạo định dạng TIFF............................ 50 Hình 3.10. Minh họa kết quả chương trình với ảnh giả mạo dạng nén JPEG .......................... 50 Hình 3.11.Minh họa kết quả chương trình với ảnh giả cắt/ghép từ hai ảnh được chụp bởi cùng loại máy ảnh. ............................................................................................................................ 51 6 DANH MỤC CÁC TỪ VIẾT TẮT Viết tắt Đầy đủ - mô tả BAM Blocking Artifact Matrix - Ma trận các khối dấu hiệu CFA Color Filter Array - Mảng lọc màu sắc DCT Discrete Cosine Transform - Dãy biến đổi cosine rời rạc ELA Error Level Analysis - Phân tích mức độ lỗi EM Expectation Maximization - Thuật toán kỳ vọng cực đại EXIF Exchange able Image Tệp format -Tiêu chuẩn xác định định dạng ảnh FPN Fixed Pattern Noise - Mẫu nhiễu có cấu trúc JPEG Joint Photographic Experts Group - Là một phương pháp nén ảnh hiệu quả MAP Maximum A Posteriori Estimation - Ước lượng hậu cực đại PCA Principal Component Analysis - Phân tích thành phần chính PNG Portable Network Graphics-Là một định dạng của ảnh PNU Pixel Non-Uniformity - Điểm ảnh không đồng nhất PRNU TIFF Photo-response non-uniformity noise - Ảnh hưởng không đồng nhất của nhiễu tới điểm ảnh Tag Image File Format –Là một định dạng của ảnh 7 LỜI NÓI ĐẦU Ngày nay, ảnh số là phương tiện truyền thông được sử dụng phổ biến và rộng rãi, nó chứa đựng nhiều thông tin, cũng là cách để biểu diễn thế giới xung quanh ta một cách dễ dàng và cô đọng. Một câu hỏi đặt ra là ảnh này có độ tin cậy bao nhiêu? Rõ ràng, thông tin hình ảnh có tác động quan trọng đến xã hội chúng ta, chúng đóng vai trò cốt yếu trong đời sống con người. Việc xác thực ảnh là bài toán quan trọng trong nhiều lĩnh vực xã hội, chẳng hạn trong phòng xử án, tính thật của một bức ảnh đóng vai trò cốt yếu vì nó chính là một bằng chứng. Mặt khác, hằng ngày các bài báo hay tạp chí đều chứa nhiều hình ảnh, trong vật lý và y học thì có nhiều quyết định đều phải dựa vào các ảnh số,… Hơn nữa, hiện nay do sự tiến bộ của các máy tính hiệu năng cao, giá thành thấp, giao diện người máy thân thiện hơn, cũng như các phần mềm điều khiển và thao tác trên ảnh số là khá mạnh và đơn giản. Sức mạnh của các chương trình xử lý ảnh số như PhotoShop 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. Điều đó, đồng nghĩa với việc phát hiện ảnh giả mạo là bài toán khó khăn và ngày càng trở nên cấp thiết hơn. Từ yêu cầu thực tế đó, tôi lựa chọn đề tài “Phát hiện ảnh giả mạo dựa trên mẫu nhiễu cảm biến” nhằm nghiên cứu kỹ thuật phát hiện ảnh kỹ thuật số giả mạo dựa trên cơ sở dò tìm các mẫu nhiễu tạo ra bởi máy ảnh. Bố cục của luận văn được trình bày như sau: Phần mở đầu Chương 1: Khái quát về xử lý ảnh và ảnh giả mạo: Chương này đề cập đến các khái niệm cơ bản về xử lý ảnh số, quá trình xử lý ảnh. Khái quát một số phương pháp giả mạo ảnh số thường gặp, để từ đó giúp người đọc có cái nhìn tổng quan về lĩnh vực ảnh số giả mạo. Chương 2: Các kỹ thuật phát hiện ảnh số giả mạo: Chương này trình bày các kỹ thuật phát hiện ảnh giả mạo đã được các nhóm nghiên cứu và giới thiệu. Chương 3: Phát hiện ảnh giả mạo dựa trên mẫu nhiễu cảm biến: Chương này nghiên cứu về mẫu nhiễu cảm biến của máy ảnh, từ đó đưa ra 8 phương pháp phát hiện ảnh giả mạo dựa vào mẫu nhiễu cảm biến bao gồm ý tưởng, thuật toán và chương trình thử nghiệm. Phần kết luận 9 CHƯƠNG 1: KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ ẢNH GIẢ MẠO 1.1. Xử lý ảnh và một số vấn đề cơ bản trong xử lý ảnh 1.1.1. Một số khái niệm cơ bản Để 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 độ ( X , Y ) và màu sắc của nó.  Ảnh và điểm ảnh: Ả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 I ( n , p ) có n dòng và p cột, ảnh sẽ có n  p (pixel). Ta ký hiệu I ( X ,Y ) để chỉ điểm ảnh có toạ độ ( X , Y ) . Điểm ảnh (pixel) là một phần tử của ảnh số tại tọa độ (x,y) với độ xám hoặc màu nhất định. Kích thước và khoảng cách giữa các điểm ảnh đó được chọn thích hợp sao cho mắt người cảm nhận sự liên tục về không gian và mức xám (hoặc màu) của ảnh số gần như ảnh thật. Mỗi phần tử trong ma trận được gọi là một phần tử ảnh.  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…).  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. 10 1.1.2. Một số vấn đề cơ bản trong xử lý ảnh  Xử lý ảnh? Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Ảnh Ảnh “tốt hơn" XỬ LÝ ẢNH Kết luận Hình 1.1. Quá trình xử lý ảnh  Cách biểu diễn ảnh Đố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 f ( X , Y ) , trong đó X , Y là các giá trị toạ độ không gian và hàm giá trị của f tại một điểm mức xám của điểm ảnh tại điểm này. ( X , Y ) bất kỳ sẽ tỷ lệ với độ sáng hay * P(X,Y) Hình 1.2. Biểu diễn ảnh bằng hàm f ( X , Y ) Trong một 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.2, trục thứ 3 bằng 0). Một ảnh số là một ảnh f ( X , Y ) đượ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 f ( X , Y ) phải khác 0 và hữu hạn: 0  f ( X ,Y )   (1.1) 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 f ( X , Y ) được đặc trưng qua hai thành phần: 11  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à i ( X , Y ) và r ( X , Y ) . Bản chất của i ( X , Y ) được xác định bằng nguồn sáng và của r ( X , Y ) được xác định bằng các đặc trưng của vật thể. Hàm i ( X , Y ) và r ( X , Y ) kết hợp với nhau để cho hàm f ( X , Y ) f ( X , Y )  i( X , Y ) r ( X , Y ) Với: (1.2) ( 0  i( X , Y )   0  r( X ,Y )  1 ) Ở đây ta gọi cường độ sáng của một ảnh đen trắng tại tọa độ ( X , Y ) là mức xám (l ) của ảnh tại điểm đó. Từ (1.2), (1.3), (1.4) , l nằm trong khoảng: Lmin  l  Lmax (1.3) Trong lý thuyết, chỉ cần Lmin  0 và Lmax hữu hạn. Trong thực tế: Lmin  imin rmin (1.4) Lmax  imax rmax 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 Lmin  0.005, Lmax  100 cho xử lý ảnh. Khoảng  Lmin , Lmax  được gọi là thang xám. Ta có thể dịch khoảng này đến 0, L  , trong đó l  0 là đen và l  L 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. Các điểm 4 láng giềng: Giả sử (i,j) là một điểm ảnh, khi đó các điểm 4 – láng giềng là: N4= {(i-1,j); (i+1,j); (i, j-1); (i, j+1)} Các điểm 8 láng giềng: N8 = N4  {(i-1,j-1); (i-1,j+1); (i+1,j-1); (i+1,j+1)}  Nắn chỉnh biến dạng Ảnh thu nhận thường bị biến dạng do các thiết bị quang học và điện tử. 12 Hình 1.3. Ảnh thu nhận và ảnh mong muốn Để khắc phục người ta sử dụng các phép chiếu, các phép chiếu thường được xây dựng trên tập các điểm điều khiển. Giả sử (Pi, Pi’) i= 1, n có n các tập n điều khiển. Tìm hàm f: Pi → f (Pi) sao cho  f (Pi )  Pi ' 2  min . i 1 Giả sử ảnh bị biến đổi chỉ bao gồm : Tịnh tiến, quay, tỷ lệ, biến dạng bậc nhất tuyến tính. Khi đó hàm f có dạng: f(x,y) = (a1x + b1y + c1, a2x + b2y + c2) Ta có: 2 n n ' i    (f(Pi )  P )   (a1x i  b1 yi  c1  x i' )2  (a 2 x i  b 2 yi  c2  yi' )2  i 1 (1.5) i 1 Để cho →min (1.6) Giải hệ phương trình tuyến tính tìm được a1, b1, c1 Tương tự tìm được a2, b2, c2  Xác định được hàm f  Kỹ thuật phóng to, thu nhỏ ảnh: Khi ảnh quá lớn chúng ta muốn nhìn toàn bộ ảnh thì chúng ta phải thu nhỏ ảnh lại và ngược lại khi ta muốn xem chi tiết một bộ phận nào đó của ảnh thì ta phải phóng to nó lên. 13 - Kỹ thuật phóng to ảnh: Khi phóng to ảnh với một tỉ lệ k nào đó ta thu được ảnh mới to gấp k lần ảnh cũ (k là độ phóng của ảnh) như thế ảnh mới sẽ có kích thước là: Height = Height * k Width = Width * k Việc tính các điểm ảnh tương ứng của ảnh mới sẽ được tính theo công thức: xp=x/k yp=y/k - Kỹ thuật thu nhỏ ảnh: Tương tự như phóng to ảnh, khi thu nhỏ ảnh ta thu được ảnh mới giống ảnh cũ nhưng có kích thước nhỏ hơn ảnh cũ. Kích thước của ảnh mới là: Height = Height / k Width = Width / k Việc tính các điểm ảnh tương ứng của ảnh mới sẽ được tính theo công thức: xp=x*k yp=y*k  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. Nhận dạng tự động (automatic recognition), mô tả đối tượng, phân loại và phân nhóm các mẫu là những vấn đề quan trọng trong thị giác máy, được ứng dụng trong nhiều ngành khoa học khác nhau. Tuy nhiên, một câu hỏi đặt ra là: mẫu (pattern) là gì? Watanabe, một trong những người đi đầu trong lĩnh vực này đã định nghĩa: “Ngược lại với hỗn loạn (chaos), mẫu là một thực thể (entity), được xác định một cách mơ hồ (vaguely defined) và có thể gán cho nó một tên gọi nào đó”. Ví dụ mẫu có thể là ảnh của vân tay, ảnh của một vật nào đó được chụp, một chữ viết, khuôn mặt người hoặc một ký đồ tín hiệu tiếng nói. Khi biết một mẫu nào đó, để nhận dạng hoặc phân loại mẫu đó có thể: Hoặc phân loại có mẫu (supervised classification), chẳng hạn phân tích phân biệt (discriminant analyis), trong đó mẫu đầu vào được định danh như một thành phần của một lớp đã xác định. Hoặc phân loại không có mẫu 14 (unsupervised classification hay clustering) trong đó các mẫu được gán vào các lớp khác nhau dựa trên một tiêu chuẩn đồng dạng nào đó. Các lớp này cho đến thời điểm phân loại vẫn chưa biết hay chưa được định danh. Hệ thống nhận dạng tự động bao gồm ba khâu tương ứng với ba giai đoạn chủ yếu sau đây: - Thu nhận dữ liệu và tiền xử lý - Biểu diễn dữ liệu - Nhận dạng, ra quyết định Bốn cách tiếp cận khác nhau trong lý thuyết nhận dạng là: - Đối sánh mẫu dựa trên các đặc trưng được trích chọn. - Phân loại thống kê. - Đối sánh cấu trúc. - Phân loại dựa trên mạng nơ-ron nhân tạo. Trong các ứng dụng rõ ràng là không thể chỉ dùng có một cách tiếp cận đơn lẻ để phân loại “tối ưu” do vậy cần sử dụng cùng một lúc nhiều phương pháp và cách tiếp cận khác nhau. Do vậy, các phương thức phân loại tổ hợp hay được sử dụng khi nhận dạng và nay đã có những kết quả có triển vọng dựa trên thiết kế các hệ thống lại (hybrid system) bao gồm nhiều mô hình kết hợp. Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trong cuộc sống không chỉ tạo ra những thách thức về thuật giải, mà còn đặt ra những yêu cầu về tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc điểm đặc trưng cần thiết thường là nhiều, không thể do chuyên gia đề xuất, mà phải được trích chọn dựa trên các thủ tục phân tích dữ liệu. 15 1.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: Hình 1.4. Các bước cơ bản trong xử lý ảnh số 1.1.3.1. Thu nhận ảnh Đây là bước đầu tiên trong quá trình xử lý ảnh. Để thực hiện điều này ta cần có các thiết bị nhu nhận ảnh. Các thiết bị thu nhận ảnh có 2 loại chính ứng với 2 loại ảnh thông dụng Raster và Vector. Các thiết bị thu nhận ảnh thông thường Raster là máy ảnh, còn các thiết bị thu nhận ảnh Vector là sensor hoặc bộ số hóa (Digitalizer) hoặc được chuyển đổi từ ảnh Raster. Các thiết bị thu ảnh thông thường gồm máy ảnh cộng với bộ chuyển đổi tương tự số AD (Analog to Digital) hoặc scanner chuyên dụng. Các thiết bị thu nhận ảnh này có thể cho ảnh đen trắng hoặc ảnh màu. Đầu ra của scanner là ảnh ma trận số mà ta quen gọi là bản đồ ảnh (ảnh Bitmap). Bộ số hoá (Digitalizer) sẽ tạo ảnh vector có hướng. Nhìn chung, các hệ thống thu nhận ảnh thực hiện hai quá trình: - Cảm biến : biến đổi năng lượng quang học thành năng lượng điện. - Tổng hợp năng lượng điện thành ảnh. 1.1.3.2. Tiền xử lý Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khử bóng, khử độ lệch, v.v…. với mục đích làm cho chất lượng ảnh trở nên tốt hơn 16 nữa, chuẩn bị cho các bước xử lý phức tạp hơn về sau trong quá trình xử lý ảnh. Quá trình này thường được thực hiện bởi các bộ lọc. Khử nhiễu: Nhiễu được chia thành hai loại: nhiễu hệ thống và nhiễu ngẫu nhiên. Đặc trưng của nhiễu hệ thống là tính tuần hoàn. Do vậy, có thể khử nhiễu này bằng việc sử dụng phép biến đổi Fourier và loại bỏ các đỉnh điểm. Đối với nhiễu ngẫu nhiên, trường hợp đơn giản là các vết bẩn tương ứng với các điểm sáng hay tối, có thể khử nhiễu bằng phương pháp nội suy, lọc trung vị, lọc trung bình. Chỉnh mức xám: Đây là kỹ thuật nhằm chỉnh sửa tính không đồng đều của thiết bị thu nhận hoặc độ tương phản giữa các vùng ảnh. Chỉnh tán xạ: Ảnh thu nhận từ các thiết bị quang học hay điện tử có thể bị mờ, nhòe. Phương pháp biến đổi Fourier dựa trên tích chập của ảnh với hàm tán xạ cho phép giải quyết việc hiệu chỉnh này. Nắn chỉnh hình học: Những biến dạng hình học thường do các thiết bị điện tử và quang học gây ra. Do đó phương pháp hiệu chỉnh hình ảnh dựa trên mô hình được mô tả dưới dạng phương trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tưởng f(x’,y’) như sau: Trong đó x , y là các phương trình tuyến tính (biến dạng do phối cảnh) hay bậc hai (biến dạng do ống kính máy ảnh). 1.1.3.3. Phân đoạn ảnh Phân đoạn ảnh có nghĩa là chia một ảnh đầu vào thành nhiều phần khác nhau hay còn gọi là các đối tượng để biểu diễn phân tích, nhận dạng ảnh. Ví dụ: để nhận dạng chữ (hoặc mã vạch) trên phong bì thư cho mục đích phân loại bưu phẩm, cần chia các câu, chữ về địa chỉ hoặc tên người thành các từ, các chữ, các số (hoặc các vạch) riêng biệt để nhận dạng. Đây là phần phức tạp khó khăn nhất trong xử lý ảnh và cũng dễ gây lỗi, làm mất độ chính xác của ảnh. Kết quả nhận dạng ảnh phụ thuộc rất nhiều vào công đoạn này. Mục đích của phân đoạn ảnh là để có một miêu tả tổng hợp về nhiều phần tử khác nhau cấu tạo nên ảnh thô. Vì lượng thông tin chứa trong ảnh rất lớn, trong khi đa số các ứng dụng chúng ta chỉ cần trích một vài đặc trưng nào đó, 17 do vậy cần có một quá trình để giảm lượng thông tin khổng lồ đó. Quá trình này bao gồm phân vùng ảnh và trích chọn đặc tính chủ yếu. 1.1.3.4. Biểu diễn và mô tả Biểu diễn ảnh: Đầu ra ảnh sau phân đoạn chứa các điểm ảnh của các vùng ảnh (ảnh đã phân đoạn) cộng với mã liên kết với các vùng lân cận. Việc biến đổi các số liệu này thành dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính. Việc chọn các tính chất để thể hiện ảnh gọi là trích chọn đặc trưng (Feature Selection) gắn với việc tách các đặc tính của ảnh dưới dạng các thông tin định lượng hoặc làm cơ sở để phân biệt lớp đối tượng này với đối tượng khác trong phạm vi ảnh nhận được. Ví dụ : trong nhận dạng kí tự trên phong bì, chúng ta miêu tả các đặc trưng của từng kí tự giúp phân biệt kí tự này với kí tự khác. Mô tả ảnh: Ảnh sau khi số hóa sẽ được lưu vào bộ nhớ, hoặc chuyển sang các khâu tiếp theo để phân tích. Nếu lưu trữ ảnh trực tiếp từ các ảnh thô, đòi hỏi dung lượng bộ nhớ cực lớn và không hiệu quả theo quan điểm ứng dụng và công nghệ. Thông thường, các ảnh thô đó đặc tả (biểu diễn) lại (hay đơn giản là mã hóa) theo các đặc điểm của ảnh được gọi là đặc trưng của ảnh như : biên ảnh, vùng ảnh. Một số phương pháp biểu diễn thường dùng: - Biểu diễn bằng mã chạy: Phương pháp này thường biểu diễn cho vùng ảnh và áp dụng cho ảnh nhị phân. - Biểu diễn bằng mã xích: Phương pháp này thường dung để biểu diễn các đường biên ảnh. - Biểu diễn bằng mã tứ phân: Phương pháp này được dùng để mã hóa cho các vùng ảnh. 1.1.3.5. Cơ sở trí thức Ảnh là một đối tượng khá phức tạp về đường nét, độ sáng tối, dung lượng điểm ảnh, môi trường để thu ảnh phong phú kéo theo nhiễu. Trong nhiều khâu xử lý và phân tích ảnh ngoài việc đơn giản hóa các phương pháp toán học đảm bảo tiện lợi cho xử lý, người ta mong muốn bắt chước quy trình tiếp nhận và xử lý ảnh theo cách của con người. Trong các bước xử lý đó, nhiều khâu hiện nay đã xử lý theo phương pháp trí tuệ con người. Vì vậy, ở đây các cơ sở trí thức được phát huy. 18 1.1.3.6. Nhận dạng và nội suy ảnh Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thường thu được bằng cách so sánh với mẫu chuẩn đã được lọc (hoặc lưu) từ trước. Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một loạt chữ số và nét gạch ngang trên phong bì thư có thể được nội suy thành mã điện thoại. Có nhiều cách phân loại khác nhau về ảnh. Theo lý thuyết về nhận dạng, các mô hình toán học được phân loại theo hai loại nhận dạng cơ bản: - Nhận dạng theo tham số - Nhận dạng theo cấu trúc Một số đối tượng nhận dạng khá phổ biến hiện nay đang được áp dụng trong khoa học và công nghệ là: nhận dạng ký tự (chữ in, chữ viết tay, chữ kí điện tử), nhận dạng văn bản (Text), nhận dạng vân tay, nhận dạng mã vạch, nhận dạng mặt người,… 1.1.3.7. Trích chọn đặc trưng Vì lượng thông tin chứa trong ảnh là rất lớn, trong khi đó đa số ứng dụng chỉ cần một số thông tin đặc trưng nào đó, cần có bước trích chọn đặc điểm để giảm lượng thông tin khổng lồ ấy. Việc trích chọn hiệu quả đặc điểm giúp cho việc nhận dạng các đối tượng ảnh chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm. Các đặc điểm của đối tượng được trích chọn tùy theo mục đích nhận dạng. Có thể nêu ra một số đặc điểm của ảnh sau đây: Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm uốn, v.v.. Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc thực hiện lọc vùng (Zonal Filtering). Các bộ vùng được gọi là “mặt nạ đặc điểm” (Feature Mask) thường là các khe hẹp với hình dạng khác nhau (chữ nhật, tam giác, cung tròn,…) Đặc điểm biên và đường biên: Đặc trưng cho đường biên của đối tượng và do rất hữu ích trong việc trích chọn các đặc tính bất biến được dung khi nhận dạng đối tượng. Các đặc điểm này có thể được trích chọn nhờ toán tử Gradien, toán tử Laplace, toán tử chéo không (Zero Crossing).