Bài toán phát hiện mặt người trong ảnh

c trưng khơng thay đổi của khuơn mặt trong ảnh,sau đĩ dùng đồ thị ngẫu nhiên để xác định khuơn mặt. Tư tưởng của phương pháp này đĩ là xem bài tốn xác định khuơn mặt như là bài tốn tìm kiếm với mục tiêu là tìm thứ tự các đặc trưng khơng thay đổi của khuơn mặt. Dùng năm đặc trưng (hai mắt, hai lỗ mũi, phần nối giữa mũi và miệng) để mơ tả một khuơn mặt. Đồng thời tính quan hệ khoảng cách cho tất cả các cặp đặc trưng (như mắt trái, mắt phải), sau đấy dùng phân bố Gauss để mơ hình hĩa. Một mẫu khuơn mặt được đưa ra thơng qua trung bình tương ứng cho một tập đa hướng, đa tỷ lệ của bộ lọc đạo hàm Gauss. Từ một ảnh, các đặc trưng của ứng viên được xác định bằng cách so khớp từng điểm ảnh khi lọc tương ứng với vector mẫu. Hai ứng viên cĩ đặc trưng đứng đầu sẽ được chọn để tìm kiếm cho các đặc trưng khác của khuơn mặt. Từ các đặc trưng khơng thay đổi, các đặc trưng khác sẽ được xác định thơng qua sự đánh giá xác xuất khoảng cách giữa các đặc trưng, hơn nữa phương sai của phép thống kê này cĩ thể được tính tốn trước để xác định các đặc trưng với xác xuất lớn. Tỷ lệ chính xác của phương pháp này là 86%. Bên cạnh tính khoảng cách liên quan để mơ tả quan hệ giữa các đặc trưng như Leung. Kendall [4], Mardia and Dryden [12] dùng lý thuyết xác suất thống kê về hình dáng. Dùng hàm mật độ xác suất (Probility Density Function - PDF) qua N điểm đặc trưng, tương ứng (xi, yi) là đặc trưng thứ i với giả sử là phân bố Gauss cĩ 2N-chiều. Các tác giả áp dụng phương thức cực đại khả năng (Maximum-Likelihood - ML) để xác địnhvị trí khuơn mặt. Một thuận lợi của phương pháp này là các khuơn mặt bị che khuất vẫncĩ thể xác định được. Hạn chế phương pháp này đĩ là khơng xác định được nhiều khuơn mặt trong cùng một ảnh. Khơng dùng phương pháp xác xuất, Sirohey đưa một phương pháp khác xác định khuơn mặt từ một ảnh cĩ hình nền phức tạp [10], gọi là phương pháp dựa trên cạnh. Ơng dùng phương pháp Candy [9] và heuristics loại bỏ các cạnh để cịn lại duy nhất một đường bao xung quanh khuơn mặt. Dùng một hình ellipse để bao khuơn mặt, tách biệt vùng đầu và hình nền. Tỷ lệ chính xác của thuật tốn là 80%. Graf đưa ra một phương pháp khác để xác định đặc trưng, từ đĩ xác định khuơn mặt trong ảnh xám [8]. Dùng bộ lọc để làm nổi các biên, các phép tốn hình thái học (morphology) được dùng để làm nổi bật các vùng cĩ cường độ cao và hình dáng chắc chắn (như mắt). Thơng qua histogram để tìm các đỉnh nổi bật để xác định các ngưỡng chuyển ảnh xám thành hai ảnh nhị phân. Tiếp theo, ơng xác định các ứng viên khuơn mặt nhờ vào các thành phần đều xuất hiện trong cả hai ảnh nhỉ phân, sau đĩ phân loại xem các ứng viên cĩ phải là khuơn mặt khơng. Phương pháp được kiểm tra và cho kết quả tốt trên các ảnh chỉ cĩ đầu và vai của người. Tuy nhiên phương pháp này cịn một vấn đề đấy là sử dụng các phép tốn morphology như thế nào và làm sao xác định khuơn mặt trên các vùng ứng viên. Park dùng Gaze để tìm ứng viên gĩc mắt, miệng và tâm mắt. Ơng xây dựng SVM (Support Vector Machine) đã được học trước đĩ để xác định các vị trí ứng viên cĩ phải là gĩc mắt, miệng, và tâm mắt hay khơng để theo vết con mắt người. Juan và Narciso xây dựng một khơng gian màu mới YCg’Cr’ để lọc các vùng là ứng viên khuơn mặt dựa trên sắc thái của màu da người. Sau khi cĩ ứng viên, hai ơng dùng các quan hệ về hình dáng khuơn mặt, mức độ cân đối của các thành phần khuơn mặt để xác định khuơn mặt người. Tương tự, Chang và Hwang cũng dùng khơng gian mầu Ycg’Cr’ với tỷ lệ chính xác hơn 80% trong ảnh xám. Jin xây dựng một bộ lọc để xác định ứng viên khuơn mặt người theo màu da người Từ ứng viên này tác giả xác định khuơn mặt người theo hình dáng khuơn mặt và các quan hệ đặc trưng về thành phần khuơn mặt, với mắt phải được chọn làm gốc tọa độ để xét quan hệ. Tỷ lệ chính xác cho khuơn mặt chụp thẳng trên 80%. 1.2.2. Kết cấu của khuơn mặt. Khuơn mặt con người cĩ những kết cấu riêng biệt mà cĩ thể dùng để phân loại so với các đối tượng khác. Từ kết cấu của khuơn mặt xây dựng lên một bộ phân loại, gọi là kết cấu giống khuơn mặt (face-like texture). 1.2.3. Mầu sắc da. Thơng thường các ảnh màu khơng xác định trực tiếp trên tồn bộ dữ liệu ảnh mà các tác giả dùng tính chất sắc màu của da người (khuơn mặt người) để chọn ra được các ứng viên cĩ thể là khuơn mặt người (lúc này dữ liệu đã thu hẹp đáng kể) để xác định khuơn mặt người. 1.2.4. Đa đặc trưng. Gần đây cĩ nhiều nghiên cứu sử dụng các đặc trưng tồn cục như: màu da người, kích thước, và hình dáng để tìm các ứng viên khuơn mặt, rồi sau đĩ sẽ xác định ứng viên nào là khuơn mặt thơng qua dùng các đặc trưng cục bộ (chi tiết) như: mắt, lơng mày, mũi, miệng, và tĩc. Tùy mỗi tác giả sẽ sử dụng tập đặc trưng khác nhau. 1.3. Hướng tiếp cận dựa trên so sánh khớp mẫu. 1.3.1. Tư tưởng của so sánh khớp mẫu Trong hướng tiếp cận dựa trên so sánh khớp mẫu, các mẫu chuẩn của khuơn mặt (thường là khuơn mặt được chụp thẳng) sẽ được xác định trước hoặc được biểu diễn thành một hàm với các tham số cụ thể. Từ ảnh đầu vào, ta tính các giá trị tương quan so với các mẫu chuẩn về đường viền khuơn mặt, mắt, mũi và miệng. Thơng qua các giá trị tương quan này mà hệ thống sẽ quyết định cĩ hay khơng cĩ tồn tại khuơn mặt trong ảnh. Hướng tiếp cận này cĩ lợi thế là rất dễ cài đặt, nhưng khơng hiệu quả khi tỷ lệ, tư thế, và hình dáng thay đổi. 1.3.2. Xác định các mẫu. Sakai đã cố gắng thử xác định khuơn mặt người chụp thẳng trong ảnh [20]. Ơng dùng vài mẫu con (sub template) về mắt, mũi, miệng, và đường viền khuơn mặt để mơ hình hĩa một khuơn mặt. Mỗi mẫu con được định nghĩa trong giới hạn của các đoạn thẳng. Các đoạn thằng trong ảnh được trích bằng cách xem xét thay đổi của hệ số gĩc và so khớp các mẫu con. Đầu tiên tìm các ứng viên thơng qua mối tương quan giữa các ảnh con và các mẫu về đường viền. Sau đĩ, so khớp với các mẫu con khác. Hay nĩi một cách khác, giai đoạn đầu xem như là giai đoạn sơ chế để tìm ứng viên, giai đọan thứ hai là giai đoạn tinh chế để xác định ứng viên cĩ phải là khuơn mặt hay khơng. Ý tưởng này được duy trì cho đến các nghiên cứu sau này. Craw đưa ra một phương pháp xác định khuơn mặt người dựa vào các mẫu về hình dáng của các ảnh được chụp thẳng (dùng vẻ bề ngồi của hình dáng khuơn mặt). Đầu tiên dùng phép lọc Sobel (Phép lọc Sobel dựa vào tích vơ hướng của hai vector gradient) để tìm các cạnh. Các cạnh này sẽ được nhĩm lại theo một số ràng buộc. Sau đĩ, tìm đường viền của đầu, quá trình tương tự được lặp đi lặp lại với mỗi tỷ lệ khác nhau để xác định các đặc trưng khác như: mắt, lơng mày, và mơi. Sau đĩ Craw mơ tả một phương thức xác định dùng một tập cĩ 40 mẫu để tìm các đặc trưng khuơn mặt và điều khiển chiến lược dị tìm. Một số nhà nghiên cứu sử dụng hình chiếu như các mẫu để xác định khuơn mặt người. Silhouettes dùng PCA (phân tích thành phần chính – Principal Component Analysis - PCA) để cĩ một tập hình chiếu cơ bản từ các mẫu khuơn mặt, hình chiếu được mơ tả như một mảng các bit. Sau đấy dùng đặc trưng hình chiếu kết hợp biến đổi Hough để xác định khuơn mặt người. Phương pháp này định nghĩa một số giả thuyết để mơ tả các khả năng của các đặc trưng khuơn mặt. Với một khuơn mặt sẽ cĩ một tập giả thuyết, gọi là lý thuyết DepsterShafer. Dùng một nhân tố tin cậy để kiểm tra sự tồn tại hay khơng của các đặc trưng của khuơn mặt, và kết hợp nhân tố tin cậy này với một độ đo để xem xét cĩ hay khơng cĩ khuơn mặt trong ảnh. Sinha dùng một tập nhỏ các ảnh bất biến trong khơng gian ảnh để mơ tả khơng gian các mẫu ảnh [15, 16]. Tư tưởng chính của ơng dựa vào sự thay đổi mức độ sáng của các vùng khác nhau của khuơn mặt (như hai mắt, hai má, và trán), (quan hệ về mức độ sáng của các vùng cịn lại thay đổi khơng đáng kể). Sau đấy xác định các cặp tỷ số của mức độ sáng của một số vùng (một vùng tối hơn hay sáng hơn) cho ta một lượng bất biến khá hiệu quả. Ơng lưu sự thay đổi độ sáng của các vùng trên khuơn mặt trong một tập thích hợp với các cặp quan hệ sáng hơn – tối hơn giữa các vùng nhỏ. Một khuơn mặt được xác định nếu nĩ thỏa mãn tất cả các cặp sáng hơn – tối hơn. Ý tưởng này xuất phát từ sự khác biệt của cường độ giữa các vùng kề cục bộ trên ảnh, sau này nĩ được mở rộng trên cơ sở biến đổi wavelet để xác định người đi bộ, xác định xe hơi, xác định khuơn mặt. Ý tưởng của Sinha cịn được áp dụng trong các nghiên cứu về thị giác của robot. Hình 3 cho thấy mẫu khuơn mặt với 16 cùng và 23 quan hệ. Các quan hệ này được dùng để phân loại, cĩ 11 quan hệ thiết yếu (các mũi tên màu đen) và 12 quan hệ xác thực (các mũi tên mầu xám). Mỗi mũi tên là một quan hệ. Một quan hệ của hai vùng thỏa mãn mẫu khuơn mặt khi tỷ lệ giữa hai vùng vượt qua một ngưỡng và một khuơn mặt được xác đinh khi cĩ 23 quan hệ thỏa mãn điều kiện trên Hình 3: Một mẫu khuơn mặt Mẫu khuơn mặt cĩ kích thước 14 x 16 pixel được sử dụng trong phương pháp định vị khuơn mặt của Sinha. Mẫu gồm 16 vùng trên khuơn mặt và 23 quan hệ ( các mũi tên). Một số phương pháp khác như của Froba và Zink lọc cạnh ở độ phân giải thấp rồi dùng biến đổi Hough để so khớp mẫu theo hướng cạnh để xác định hình dáng khuơn mặt ở dạng chụp hình thẳng ở dạng xám. Tỷ lệ chính xác trên 91%. Ngồi ra Shu và Jain cịn xây dựng ngữ nghĩa khuơn mặt. Ngữ nghĩa xây dựng theo hình dáng và vị trí các thành phần khuơn mặt. Hai ơng từ bộ ngữ nghĩa này tạo một đồ thị quan hệ để dễ dàng so khớp khi xác định khuơn mặt người … 1.3.3. Các mẫu biến dạng Yuille dùng các mẫu biến dạng để mơ hình hĩa các đặc trưng của khuơn mặt [3]. Trong hướng tiếp cận này, các đặc trưng khuơn mặt được mơ tả bằng các mẫu được tham số hĩa và cĩ một hàm năng lượng (giá trị) được để liên kết các cạnh, đỉnh, và thung lũng trong ảnh để tương ứng với các tham số trong mẫu. Mơ hình này tốt nhất khi tối thiểu hàm năng lượng qua các tham số, Mặc dù cĩ kết quả tốt nhưng phương pháp này cĩ một số hạn chế đĩ là các mẫu biến dạng phải được khởi tạo trong phạm vi gần với các đối tượng mà nĩ xác định. Rất nhiều hướng tiếp cận dựa trên dường gấp khúc (snake) và các mẫu để xác định khuơn mặt. Đầu tiên ảnh sẽ được làm xoắn lại bởi một lọc làm mờ rồi dùng phép tốn morphology để làm nổi bật cạnh lên. Tiếp theo dùng một đường gấp khúc cĩ n điểm ảnh (giá trị n nhỏ) để tìm và ước lượng các đọan cong nhỏ. Mỗi khuơn mặt được xấp xỉ bằng một ellipse và biến đổi Hough, rồi tìm một ellipse nổi trội nhất. Các ứng viên sẽ cĩ bốn tham số mơ tả nột ellipse (để xác định khuơn mặt). Với mỗi ứng viên, một phương thức tương tự như phương thức mẫu biến dạng được dùng để xác định các đặc trưng ở mức chi tiết. Nếu tìm thấy số lượng đáng kể các đặc trưng khuơn mặt và thỏa mãn tỷ lệ cân đối thì xem như đã xác định được một khuơn mặt. Lam và Yan cũng dùng đường gấp khúc để xác định vị trí đầu với thuất tốn greedy để cực tiểu hĩa hàm năng lượng [11]. Thay vì dùng đường gấp khúc thì Huang và Su [6] dùng lý thuyết dịng chảy để xác định đường viền khuơn mặt dựa trên đặc tính hình học. Hai ơng dùng lý thuyết tập hợp đồng mức (Level Set) để loang từ các khởi động ban đầu để cĩ được các khuơn mặt người. Lanitis mơ tả một phương pháp biểu diễn khuơn mặt người với cả hai thơng tin: hình dáng và cường độ [12]. Bắt đầu bằng các tập ảnh được huấn luyện với các đường viền mẫu như là đường bao mắt, mũi, cằm/má đã được gán nhãn(phân loại). Ơng dùng một vector các điểm mẫu để mơ tả hình dáng. Sau đĩ dùng một mơ hình phân bố điểm (Point Distribution Model – PDM) để mơ tả vector hình dáng qua tồn bộ các cá thể. Dùng cách tiếp cận như của Kirby và Sirovich [14] để mơ tả cường độ bề ngồi của hình dáng đã được chuẩn hĩa. Để tìm kiếm và ước lượng vị trí khuơn mặt cũng như các tham số về hình dáng ơng sử dụng một mơ hình PDM cĩ hình dáng như khuơn mặt (xác định khuơn mặt bằng mơ hình hình dáng tích cực - Active Shape Model - ASM). Các mảnh của khuơn mặt được làm biến dạng về hình dáng trung bình rồi trích lấy các tham số cường độ. Sau đấy các tham số hình dáng và cường độ được dùng để phân loại và xác định khuơn mặt. 1.4. Hướng tiếp cận dựa trên diện mạo. 1.4.1. Tư tưởng của hướng tiếp cận dựa trên diện mạo Trái ngược với hướng tiếp cận dựa trên so sánh khớp mẫu (các mẫu đã được các nhà nghiên cứu định nghĩa trước), các mẫu trong hướng tiếp cận này được học từ một tập ảnh mẫu. Cĩ thể nĩi hướng tiếp cận dựa trên diện mạo áp dụng các kỹ thuật theo hướng xác suất thống kê và học máy để tìm những đặc tính liên quan của khuơn mặt và khơng phải là hiệu quả xác định. Trong hướng tiếp cận này, phương pháp xác xuất tiếp tục được nhiều nhà nghiên cứu sử dụng. Một bức ảnh hoặc một vector (đặc trưng cho bức ảnh) được xem như một biến ngẫu nhiên. Biến ngẫu nhiên này sẽ được xác định là cĩ mơ tả các đặc tính của khuơn mặt hay khơng thơng qua các xác xuất cĩ điều kiện p(x/face) và p(x/nonface). Cĩ thể dùng bộ phân loại Bayesian để phân loại các ứng viên là khuơn mặt hay khơng phải khuơn mặt. Tuy nhiên, việc cài đặt bộ phân loại Bayesian với số chiều x lớn là một điều khá khĩ khăn, do đĩ cĩ rất nhiều nghiên cứu theo hướng tiếp cận này quan tâm tới việc tham số hĩa hay khơng tham số các xác xuất p(x/face) và p(x/nonface). Một các tiếp cận khác trong hướng tiếp cận dựa trên diện mạo là tìm một hàm biệt số ví dụ như các hàm mơ tả mặt phẳng hay siêu phẳng quyết định (các ranh giới) để phân biệt hai lớp khuơn mặt và khơng phải khuơn mặt. Thơng thường, một bức ảnh được chiếu vào khơng gian cĩ số chiều ít hơn rồi sau đĩ dùng một hàm biệt số (dựa trên các độ đo khoảng cách) để phân loại hoặc xây dựng một mặt quyết định phi tuyến bằng mạng neural đa tầng. Ngồi ra cĩ thể dùng SVM (Super Vector Machine) và các phương thức kernel chiếu các mẫu vào khơng gian cĩ số chiều cao hơn để dữ liệu bị rời rạc hồn tồn và từ đĩ cĩ thể sử dụng mặt phẳng phân loại để phân loại các mẫu là khuơn mặt hay khơng phải là khuơn mặt[5]. 1.4.2. Một số phương pháp cụ thể trong hướng tiếp cận dựa trên diện mạo Cĩ rất nhiều phương pháp học máy được sử dụng trong hướng tiếp cận dựa trên diện mạo. Trong phần này chỉ nêu ra một số phương pháp cùng những nghiên cứu liên quan đến phương pháp đấy. Riêng phương pháp adaboost sẽ được trình bầy trong phần sau của báo cáo. Adaboost Adaboost được đánh giá là phương phát tiếp cận nhanh nhất trong các thuật tốn học máy. Nĩ thường được kết hợp với các mơ hình cascade of classifiers để tăng tốc độ phát hiện khuơn mặt trong ảnh. Tư tưởng của thuật tốn adaboost đấy là kết hợp các bộ phân loại yếu thành một bộ phân loại mạnh. Trong quá trình xây dựng, bộ phân loại yếu tiếp theo sẽ được xây dựng dựa trên các đánh giá về các bộ phân loại yếu trước, cuối cùng các bộ phân loại yếu sẽ được kết hợp để trở thành bộ phân loại mạnh Viola và Jones dùng AdaBoost kết hợp cascade để xác định khuơn mặt người [17] với các đặc trưng dạng Haar-like. Tốc độ xử lý khá nhanh và tỷ lệ chính xác hơn 80%. Ngồi ra Schneiderman và Kanade dùng wavelet để trích đặc trưng, sau đấy cũng xây dựng hệ thống học với Adaboost, dựa trên xác suất để xác định khuơn mặt người. Tỷ lệ chính xác trên của phương pháp này lên đến 90%. Mạng Neural Về cơ bản mạng neural là một mạng các phần tử (gọi là neuron) kết nối với nhau thơng qua các liên kết (các liên kết này được gọi là trọng số liên kết) để thực hiện một cơng việc cụ thể nào đĩ. Khả năng xử lý của mạng neuron được hình thành thơng qua quá trình hiệu chỉnh trọng số liên kết giữa các neuron, nĩi cách khác là học từ tập hợp các mẫu huấn luyện. Mạng neural rất hay được sử dụng trong các bài tốn nhận dạng mẫu, nhận dạng mặt người cũng cĩ thể xem là một bài tốn nhận dạng với hai loại mẫu (mặt người hoặc khơng phải mặt người) và như vậy cĩ thể sử dụng mạng neural khá hiệu quả kể cả khi các mẫu khuơn mặt cĩ độ phức tạp cao. Tuy nhiên, một điều trở ngại đĩ là các kiến trúc mạng đều cĩ tính tổng quát cao, do đĩ, khi áp dụng ta phải tính tốn rõ số lượng tầng, số lượng node, tỷ lệ học … cho từng trường hợp cụ thể. c. Support Vector Machine Support Vector Machine (SVM) được Vladimir Vapnik đưa ra vào năm 1995 để giải quyết vấn đề nhận dạng mẫu hai lớp sử dụng nguyên tắc cực tiểu hĩa rủi ro cấu trúc (Structural Risk Minimization). Đây là phương pháp tiếp cận phân loại văn bản rất hiệu quả. Ưu điểm của SVM là giải thuật này được xây dựng trên ý tưởng cực tiểu rủi ro cấu trúc. Nguồn gốc của SVM dựa trên sự chắc chắn về lỗi chính xác, cĩ thể phân loại ngẫu nhiên các mẫu đối tượng được chọn mà lỗi được giữ sao cho nhỏ nhất. Vì vậy, giải thuật SVM giúp giảm thiểu biên trên các lỗi chính xác và làm cho hệ thống tin cậy hơn Cho trước một tập huấn luyện, các ảnh được biểu diễn dưới dạng vector. Trong khơng gian vector, mỗi vertor được biểu diễn bởi một điểm. Phương pháp SVM sẽ tim một siêu phẳng quyết định để phân chia khơng gian vector thành hai lớp (khuơn mặt và B chỉ cĩ 3 việc mà anh ta thích làm đĩ là: việc thứ nhất là đi dạo, thứ hai là đi chợ và thứ ba là dọn phịng. Và việc anh ta làm việc gì trong ngày phụ thuộc rất lớn vào thời tiết của ngày hơm đấy. Như vậy, dù khơng nhận được thơng tin cụ thể về thời tiết trong ngày ở nơi người B ở, nhưng người A vẫn cĩ thể dựa vào việc B làm trong ngày để đốn về thời tiết hơm đấy. Như vậy nếu coi thời tiết chỉ cĩ hai trạng thái là nắng và mưa thì thời tiết là một chuỗi Markov cụ thể, và nĩ là ẩn đối với người A. Dữ liệu quan sát được ở đây là việc làm trong ngày của người B. Tồn bộ hệ thống này là một mơ hình Mackov ẩn. Một giả thuyết quan trọng của mơ hình Markov ẩn là các mẫu cĩ thể được xem như các tiến trình ngẫu nhiên cĩ tham số và các tham số này được ước lượng chính xác. Khi phát triển HMM để giải quyết bài tốn nhận dạng mẫu, phải xác định rõ cĩ bao nhiêu trạng thái ẩn đầu tiên cho hình thái mơ hình. Sau đĩ, huấn luyện HMM học xác suất chuyển tiếp giữa các trạng thái từ các mẫu, mà mỗi mẫu được mơ tả như một chuỗi các quan sát. Mục tiêu huấn luyện HMM là cực đại hĩa xác suất của quan sát từ dữ liệu huấn luyện bằng cách điều chỉnh các tham số trong mơ hình HMM thơng qua phương pháp phân đoạn Viterbi chuẩn và các thuật tốn Baum-Welch. Sau khi huấn luyện xong, dựa vào xác suất để xác định một quan sát thuơc lớp nào. . Đối với bài tốn phát hiện và nhận dạng mặt người, ta chia khuơn mặt thành các vùng khác nhau như đầu, mắt, mũi, miệng, và cằm. Cĩ thể nhận dạng một mẫu khuơn mặt người bằng cách thực hiện tiến trình xem xét các vùng quan sát theo một thứ tự thích hợp (từ trên xuống dưới, từ trái qua phải). Mục tiêu của hướng tiếp cận này là kết hợp các vùng đặc trưng khuơn mặt với các trạng thái của mơ hình. Thường các phương pháp dựa vào HMM sẽ xem xét một mẫu khuơn mặt như một chuỗi các vector quan sát, với mỗi vector là một dãy các điểm ảnh (hình 4 và hình 6) Trong quá trình huấn luyện và kiểm tra, một ảnh được quét theo một thứ tự và một quan sát được xem như một khối các điểm ảnh (hình 4 và hình 6). Sau đấy, áp dụng một định hướng theo xác suất để chuyển từ trạng thái này sang trạng thái khác ( hình 5 ), dữ liệu ảnh được mơ hình hĩa bằng phân bố Gauss đa biến. Một chuỗi quan sát bao gồm tất cả giá trị cường độ từ mỗi khối. Kết quả xuất ra cho biết quan sát thuộc lớp nào. Một nghiên cứu điển hình trong các tiếp cận này đĩ là của Samaria. Samaria đã dùng năm trạng thái tương ứng năm vùng như trong hình 6 để mơ hình hĩa tiến trình xác định khuơn mặt người. Ơng huấn luyện từng vùng cho HMM. Mỗi trạng thái sẽ phụ trách xem xét một vùng tương ứng để đưa ra quyết định phù hợp. Nếu kết quả xem xét cuối cùng vượt qua một ngưỡng thì quan sát này sẽ là khuơn mặt người. d. Phân loại Bayes Bayes là một bộ phân loại tuyến tính dựa trên xác xuất. Tư tưởng của nĩ là dựa vào xác xuất của các đặc trưng xuất hiện trong khuơn mặt. Đây là phương pháp đơn giản, cài đặt khơng phức tạp, tốc độ nhanh, với tập huấn luyện lớn thì cho kết quả vẫn tương đối chính xác. Một nghiên cứu điển hình dùng phân loại Bayes vào xác định mặt người trong hướng tiếp cận dựa trên diện mạo đĩ là nghiên cứu của Schneiderman và Kanade. Hai ơng đã mơ tả một phân loại Nạve Bayes để ước lượng xác xuất chung của diện mạo cục bộ và vị trí của các mẫu (các vùng trên khuơn mặt) ở nhiều độ phân giải khác nhau. Ứng với mỗi độ phân giải, khuơn mặt người được chia thành bốn vùng chữ nhật, các vùng này được chiếu xuống khơng gian cĩ số chiều bé hơn và được lượng tử hĩa thành tập các mẫu cĩ giới hạn. Sau đấy thống kê các vùng đã được chiếu để mã hĩa diện mạo cục bộ. Nếu xác xuất lớn hơn xác xuất đạt được lớn hơn xác xuất tiền nghiện thì kết luận cĩ khuơn mặt người. Hướng tiếp cận này cịn cho phép xác định các khuơn mặt bị xoay hoặc gĩc nhìn nghiêng. CHƯƠNG 3- NHẬN DẠNG DỰA TRÊN PCA 1.Thuật tốn Khuơn mặt con người cĩ rất nhiều nét để nhận biết , nếu như ta gặp lại một người bạn sau một thời gian dài , ta cĩ thể nhận ra ngay người đĩ dù những chi tiết cụ thể trên mặt cĩ thể thay đổi như da , mái tĩc . Ta nhận ra khơng phải vì nhớ đơi mắt , hay mũi hay mơi hay tĩc , lơng mày người đĩ mà ta nhận ra vì nhớ diện mạo của người đĩ . Tức là trên khuơn mặt tồn tại một nét tổng thể nào đĩ để cĩ thể nhận diện , thuật tốn của ta bắt đầu từ ý tưởng này . Phân tích thành phần chính (Principal Component Analysis ) gọi tắt là PCA là thuật tốn nhận dạng ảnh dựa trên những nét tổng thể của khuơn mặt , ta sẽ áp dụng thuật tốn này để thực hiện hai cơng việc sau : Thứ nhất là tìm một khuơn mặt giống với khuơn mặt cho trước Thứ hai là xác định vị trí những khuơn mặt người trong một bức ảnh . Ban đầu ta cĩ một tập ảnh khuơn mặt gọi là tập ảnh huấn luyện (training set) . Giả sử mỗi ảnh cĩ kích thước M×N , ta coi mỗi bức ảnh này là một vector trong khơng gian M*N chiều . Bây giờ mỗi khuơn mặt là một vector , ta thấy những vector này khơng phân bố ngẫu nhiên trong khơng gian ảnh mà phân bố theo một quy luật tương đối nào đĩ , ta cĩ thể nĩi những vector này nằm trong một khơng gian con gọi là khơng gian khuơn mặt . Từ những vector trong tập huấn luyện , ta sẽ tìm một cơ sở trực chuẩn cho khơng gian khuơn mặt . Những vector thuộc cơ sở này cĩ thể coi là những vector mang những nét tổng thể đặc trưng về khuơn mặt . Giả sử tập huấn luyện cĩ P ảnh , khi đĩ ta sẽ cĩ P vector : T1 , T2 , … , TP . Tính vector ảnh trung bình : m = 1Pi=1PTi . Sự khác biệt giữa những khuơn mặt với ảnh trung bình là những vector : Ai= Ti- m , i=1…P Ý tưởng của việc phân tích thành phần chính là tìm một tập những vector trực chuẩn uk sao cho những vector này mơ tả tốt nhất sự phân bố những vector khuơn mặt trong khơng gian . Những vector uk được chọn sao cho : -ui|uj =1 nếu i=j0 nếu i≠j - λk= i=1Puk|Ai2 lớn nhất . Những vector uk và giá trị vơ hướng λk chính là những vector riêng và trị riêng tương ứng của ma trận AAT. u|v là tích vơ hướng giữa hai vector u , v . A=[A1 A2… AP] Ta thấy ma trận A cĩ kích thước M*N × P , cịn ma trận AAT cĩ kích thước M*N×M*N , do kích thước ma trận này quá lớn nên ta khơng thể tìm được những vector riêng và những trị riêng trực tiếp được , thay vào đĩ ta sẽ tìm những vector riêng của ma trận ATA cĩ kích thước P×P . Nếu v là một vector riêng của ATA và λ là trị riêng tương ứng , khi đĩ ta cĩ : ATAv = λv ĩ AATAv = λAv , tức là Av là một trị riêng của ma trận AAT . Thơng thường ta chỉ lấy một số Q vector riêng ứng với Q trị riêng cĩ giá trị lớn nhất . Sau khi cĩ các vector riêng của ma trận AAT , ta sẽ chuẩn hĩa chúng để thu được một cơ sở trực chuẩn của khơng gian khuơn mặt . Đặt L=ATA , tìm V là tập hợp các vector riêng của L , D là tập hợp các trị riêng tương ứng . V bao gồm Q vector riêng ứng với những trị riêng lớn hơn một giá trị nào đĩ hoặc ứng với Q trị riêng lớn nhất trong D . E = AV là tập các vector riêng của AAT . Do đây là những vector riêng , mà nĩ lại cĩ dạng khuơn mặt nên cịn đuợc gọi là Eigenfaces . E là ma trận M*N×Q , mỗi cột là một vector riêng . Chuẩn hĩa các vector cột trong E ( chia mỗi vector cho độ dài của vector đĩ ) . Bây giờ , ta cĩ thể coi E là một cơ sở trực chuẩn của khơng gian khuơn mặt . Với H là bức ảnh cĩ cùng kích thước với những bức ảnh trong tập huấn luyện . Ta sẽ xét nĩ cĩ phải là bức ảnh khuơn mặt hay khơng , cũng như tìm bức ảnh giống với nĩ nhất trong tập huấn luyện . H được xem là một vector trong khơng gian M*N chiều . Đặt K=H-m với m là vector ảnh trung bình . Cho V là một khơng gian cĩ tích vơ hướng hữu hạn chiều và W là một khơng gian con của V . Giả sử W cĩ một cơ sở trực chuần là {u1, … , uQ} . Khi đĩ hình chiếu trực giao của vector u bất kỳ lên W được xác định như sau : prwu = u0=i=1Qu|uiui Độ dài u-u0 được gọi là khoảng cách từ u đến W . Tập hợp ci=u|ui , i=1,… , Q được gọi là tọa độ của u0 trong khơng gian W . Tìm C=ETK là tọa độ của hình chiếu Kf của K lên khơng gian khuơn mặt . C là vector cột Q×1 Kf = i=1Qci.ei với ci = C( i , 1) ; ei = E( : , i ) . Với Ai là một cột trong ma trận A ( tương ứng với bức ảnh Ti trong tập huấn luyện ) . Ta tính Ci = ETAi là tọa độ của hình chiếu Aif của Ai lên khơng gian khuơn mặt . Ta tính hai đại lượng sau : s = K-Kf xem như khoảng cách từ bức ảnh H đến khơng gian mặt si= C - Ci xem như khoảng cách từ H đến bức ảnh Ti trong tập huấn luyện Xét α và β là hai ngưỡng nào đĩ . s < α thì H là bức ảnh khuơn mặt ( do H đủ gần với khơng gian mặt ) si< β thì Ti là bức ảnh của cùng một người với H . ( H đủ gần với Ti ) Vậy là ta đã cĩ thể tìm bức ảnh trong tập huấn luyện giống với bức ảnh H hay xác định đĩ cĩ phải là bức ảnh khuơn mặt hay khơng . Tuy nhiên ảnh H phải cĩ cùng kích thước với những bức ảnh trong tập huấn luyện . Bây giờ trong một bức ảnh lớn H cĩ nhiều khuơn mặt , ta sẽ xác định vị trí những khuơn mặt trong bức ảnh . Tại mỗi vị trí (x,y) trong H , đặt H(x,y) là một vùng trong ảnh H cĩ kích thước M×N tại (x,y) , ta xem ảnh con H(x,y) là một vector M*N chiều . K(x,y) = H(x,y) – m ; Tìm Kf(x,y) là hình chiếu của K(x,y) lên khơng gian khuơn mặt . Tính s(x,y)=Kx,y- Kf(x,y) . Tập hợp các giá trị s(x,y) tạo thành một bản đồ khuơn mặt (face map) của H , từ đĩ ta cĩ thể xác định vị trí những khuơn mặt trong ảnh . 2.Hình ảnh minh họa Trong ví dụ này ta cĩ một tập huấn luyện gồm những bức ảnh khuơn mặt kích thước 180x200 pixel , dưới đây là một số hình ảnh của những eigenfaces thu được ( lưu ý là đây chỉ là các vector trực giao , những eigenfaces thực sự chính là những vector này được chuẩn hĩa ) . Như ta thấy nếu bức ảnh là khuơn mặt người thì hình chiếu sẽ khá giống với ảnh gốc , cịn khi bức ảnh khơng phải là khuơn mặt thì hình chiếu sẽ khác ảnh gốc rất nhiều , do đĩ khoảng cách từ bức ảnh mặt người tới khơng gian mặt sẽ nhỏ hơn rất nhiều so với khoảng cách từ bức ảnh khơng phải mặt người tới khơng gian mặt . Dưới đây là một ví dụ khác , ta cĩ một tập huấn luyện gồm những bức ảnh kích thước 18x27 pixel , ta cũng tìm các Eigenface và sau đĩ tìm face map của một bức ảnh kiểm tra . Trong ví dụ này thì ảnh con H(x,y) vùng hình chữ nhật cĩ tâm tại (x,y) trên bức ảnh và cĩ kích thước 18x27 pixel . Hình trên là face map của bức ảnh ban đầu . Ta thấy vị trí của mổi khuơn mặt chính là những vùng cực tiểu địa phương trên bức ảnh ( là những đốm đen trong những vùng trắng hình chữ nhật ) . Bây giờ nếu ta cĩ một cơ sở dữ liệu những ảnh khơng phải khuơn mặt ( ta thường tập trung vào những hình ảnh xung quanh khuơn mặt như cổ áo , một phần của khuơn mặt …) . Tìm face map của bức ảnh ban đầu với khơng gian khơng phải khuơn mặt này , ta thu được kết quả sau : Hình trên cũng khá giống với face map ứng với khơng gian khuơn mặt nhưng tại mỗi vùng sáng hình chữ nhật thì khơng hề cĩ tâm ở giữa . Thực ra từ face map ứng với khơng gian khuơn mặt , nếu ta cĩ một thuật tốn tốt để tìm những vị trí cực tiểu địa phương thì đã cĩ thể xác định vị trí các khuơn mặt . Face map ứng với khơng gian khơng phải khuơn mặt chỉ là một cách đơn giản để giúp ta tìm chính xác hơn thơi . Tất cả những điều thu được ở trên chỉ là kết quả hồn tồn dựa trên lý thuyết , trong thực tế những thuật tốn nhận dạng mặt người đã phát triển lên rất nhiều từ ý tưởng của PCA mới cĩ được độ chính xác yêu cầu . 3.Nhận xét PCA là phương pháp dùng để xây dựng đặc trưng khuơn mặt , nĩ là một nền tảng để phát triển những thuật tốn khác . Thực tế cĩ rất nhiều tác giả áp dụng PCA , kết hợp với những phương pháp như mạng neural , xác suất thống kê để xây dựng những thuật tốn cĩ độ chính xác cao . Ưu điểm của PCA là nĩ dễ cài đặt , nếu ta xét bài tốn tìm khuơn mặt giống nhau thì chỉ cần áp dụng hồn tồn theo lý thuyết là đã cĩ độ chính xác khá cao , nếu áp dụng cho bài tốn tìm vị trí khuơn mặt thì cần phải cĩ một thuật tốn nữa để sử dụng face map thu được theo lý thuyết . Khuyết điểm của PCA là các mẫu khuơn mặt hồn tồn phụ thuộc vào tập huấn luyện , cĩ nghĩa là các khuơn mặt trong ảnh kiểm tra phải giống với các ảnh huấn luyện về kích thước , tư thế , độ sáng . Thực tế trong tập huấn luyện thường gồm nhiều nhĩm hình , mỗi nhĩm là hình của một người với tư thế , độ sáng khác nhau . Cĩ rất nhiều thuật tốn nhận dạng mặt người dựa trên những chi tiết của khuơn mặt như đơi mắt , lơng mày , cấu trúc của khuơn mặt , hay màu da …Khác hồn tồn với những thuật tốn trên , PCA nhận dạng dựa trên những nét tổng thể của khuơn mặt . Cịn hơn một thuật tốn , PCA đã cung cấp một cơ sở rất rõ ràng cho việc mơ tả đặc trưng của khuơn mặt , để từ đĩ cĩ thể phát triển những thuật tốn nhận dạng khác . Vì vậy cĩ thể PCA khơng là thuật tốn tốt nhất , nhưng là thuật tốn phổ biến nhất được áp dụng trong bài tốn nhận diện mặt người . CHƯƠNG 4- CƠ SỞ LÝ THUYẾT VỀ ADABOOST VÀ ĐẶC TRUNG HAAR-LIKE Tổng quan về Adaboost Học theo adaboost là một cách trong hướng tiếp cận dựa trên diện mạo, Viola và Jones dùng AdaBoost kết hợp cascade để xác định khuơn mặt người [17] với các đặc trưng dạng Haar wavelet-like. Tốc độ xử lý khá nhanh và tỷ lệ chính xác hơn 80% trên ảnh xám. Thuật tốn học máy Adaboost được phát triển thuật tốn boosting, do đĩ tơi sẽ trình bầy một chút về thuật tốn boosting trước khi trình bầy về adaboost. 1.1. Tiếp cận Boosting Về lịch sử, boosting bắt nguồn từ câu hỏi nổi tiếng được đưa ra bời Kearns vào năm 1989 : “Liệu cĩ thể tạo ra một strong classifier từ một tập các bộ phân loại yếu?”. Năm 1990, Robert Schapire đưa ra thuật tốn boosting đầu tiên, tiếp đến năm 1993 thì nĩ được Drucker, Schapire và Simard kiểm nghiệm trong trong các chương trình nhận dạng ( OCR application ). Freund đã tiếp tục các nghiên cứu của Schaprire, và đến năm 1995 thì ơng cùng với Schapire phát triển boosting thành adaboost. Như vậy, nguyên lý cơ bản của boosting là sự kết hợp các weak classifiers thành một strong classifier. Trong đĩ, weak classifier là các bộ phân loại đơn giản chỉ cần cĩ độ chính xác trên 50%. Bằng cách này, chúng ta nĩi bộ phân loại đã được “boost”. Để hiểu cách hoạt động của thuật tốn boosting, ta xét một bài tốn phân loại 2 lớp (mẫu cần nhận dạng chỉ thuộc một trong hai lớp) với D là tập huấn luyện gồm cĩ n mẫu. Trước tiên, chúng ta sẽ chọn ngẫu nhiên ra n1 mẫu từ tập D (n1<n) để tạo tập D1. Sau đĩ, chúng ta sẽ xây dựng weak classifier đầu tiên C1 từ tập D1. Tiếp theo, chúng ta xây dựng tập D2 để huấn luyện bộ phân loại C2. D2 sẽ được xây dựng sao cho một nửa số mẫu của nĩ được phân loại đúng bởi C1 và nửa cịn lại bị phân loại sai bởi C1. Bằng cách này, D2 chứa đựng những thơng tin bổ sung cho C1. Bây giờ chúng ta sẽ xây huấn luyện C2 từ D2 chúng ta sẽ huấn luyện bộ phân loại C3 từ D3. Bây giờ chúng ta đã cĩ một strong classifier: sự kết hợp C1, C2 và C3. Khi tiến hành nhận dạng một mẫu X, kết quả sẽ được quyết định bởi sự thỏa thuận của 3 bộ C1, C2 và C3: Nếu cả C1 và C2 đều phân X vào cùng một lớp thì lớp này chính là kết quả phân loại của X; ngược lại, nếu C1 và C2 phân X vào 2 lớp khác nhau, C3 sẽ quyết định X thuộc về lớp nào Adaboost Như đã biết, AdaBoost (Adaptive Boost) là một bộ phân loại mạnh phi tuyến phức dựa trên hướng tiếp cận boosting được Freund và Schapire đưa ra vào năm 1995. Adaboost hoạt động trên nguyên tắc kết hợp tuyến tính các weak classifier dựa trên các đặc trưng Haar- Line để hình thành một strong classifier. Để cĩ thể kết hợp các bộ phân loại yếu, adaboost sử dụng một trọng số (weight) để đánh dấu các mẫu khĩ nhận dạng. Trong quá trình huấn luyện, cứ mỗi weak classifier được xây dựng, thuật tốn sẽ tiến hành cập nhật lại trọng số để chuẩn bị cho việc xây dựng weak classifier tiếp theo: tăng trọng số của các mẫu bị nhận dạng sai và giảm trọng số của các mẫu được nhận dạng đúng bởi weak classifier vừa xây dựng. Bằng cách này, các weak classifier sau cĩ thể tập trung vào các mẫu mà các weak classifier trước đĩ thực hiện tốt. Sau cùng các weak classifier sẽ được kết hợp tùy theo mức độ ‘tốt’ của chúng để tạo nên một strong classifier. Các weak classifiers hk(x) là các bộ phân loại yếu, được biểu diễn như sau: Trong đĩ: x : mẫu hay cửa sổ con cần xét (x = (x1,x2,…,xn) là vector đặc trưng của mẫu) fk: giá trị của đặc trưng Haar-like pk: hệ số quyết định chiều của bất phương trình Cơng thức trên cĩ thể diễn giải như sau: Nếu giá trị đặc trưng của mẫu cho bởi hàm đánh giá của bộ phân loại vượt qua một ngưỡng cho trước thì mẫu đấy là khuơn mặt ( gọi là object : đối tượng cần nhận dạng ), ngược lại thì mẫu là background ( khơng phải là đối tượng ). Thuật tốn AdaBoost: Sơ đồ khối Quá trình huấn luyện bộ phân loại được thực hiện bằng một vịng lặp mà ở mỗi bước lặp, thuật tốn sẽ chọn ra weak classifier ht thực hiện việc phân loại với lỗi εt nhỏ nhất (do sẽ là bộ phân loại tốt nhất) để bổ sung vào strong classifier. Mỗi khi chọn được 1 bộ phân loại ht, Adaboost sẽ tính giá trị αt theo cơng thức ở trên. αt cũng được chọn trên nguyên tắc làm giảm thiểu giá trị lỗi εt. Hệ số αt nĩi lên mức độ quan trọng của ht: • Trong cơng thức của bộ phân loại H(x): Ta thấy tất cả các bộ phân loại ht đều cĩ đĩng gĩp vào kết quả của bộ phân loại H(x), và mức độ đĩng gĩp của chúng phụ thuộc vào giá trị αt tương ứng: ht với αt càng lớn thì nĩ càng cĩ vài trị quan trọng trong H(x). • Trong cơng thức tính αt: Dễ thấy giá trị αt tỉ lệ nghịch với εt. Bởi vì ht được chọn với tiêu chí đạt εt nhỏ nhất, do đĩ nĩ sẽ đảm bảo giá trị αt lớn nhất. Sau khi tính được giá trị αt, Adaboost tiến hành cập nhật lại trọng số của các mẫu: tăng trọng số các mẫu mà ht phân loại sai, giảm trọng số các mẫu mà ht phân loại đúng. Bằng cách này, trọng số của mẫu phản ánh được mức độ khĩ nhận dạng của mẫu đĩ và ht- +1 sẽ ưu tiên học cách phân loại những mẫu này. Vịng lặp xây dựng strong classifier sẽ dừng lại sau T lần lặp. Trong thực tế cài đặt thư viện OpenCV của Intel), người ta ít sử dụng giá trị T vì khơng cĩ cơng thức nào đảm bảo tính được giá trị T tối ưu cho quá trình huấn luyện. Thay vào đĩ, người ta sử dụng giá trị max false positive hay max false alarm (tỉ lệ nhận dạng sai tối đa các mẫu background). Tỉ lệ này của bộ phân loại cần xây dựng khơng được phép vượt quá giá trị này. Khi đĩ, qua các lần lặp, false alarm của strong classifier Ht(x) xây dựng được (tại lần lặp thứ t) sẽ giảm dần, và vịng lặp kết thúc khi tỉ lệ này thấp hơn max false alarm. Các đặc trưng Haar-Like Viola và Jones dùng 4 đặc trưng cơ bản [20] để xác định khuơn mặt người. Mỗi đặc rưng Haar–like là sự kết hợp của hai hay ba hình chữ nhật "trắng" hay "đen" như trong hình sau: Để áp dụng các đặt trưng này vào việc bài tốn xác định mặt người, 4 đặc trưng Haar-like cơ bản được mở rộng ra, và được chia làm 3 tập đặc trưng như sau: Đặc trưng cạnh (edge features): Đặc trưng đường (line features): 3. Đặc trưng xung quanh tâm (center-surround features): Hình 9: Các đặc trưng mở rộng của các đặc trưng Haar-like cơ sở Lợi ích của các đặc trưng Haar-like là nĩ diễn đạt được tri thức về các đối tượng trong ảnh (bởi vì nĩ biểu diễn mối liên hệ giữa các bộ phận của đối tượng), điều mà bản thân từng điểm ảnh khơng diễn đạt được. Để tính giá trị các đặc trưng haar-like, ta tính sự chênh lệch giữa tổng của các pixel của các vùng đen và các vùng trắng như trong cơng thức sau: f(x) = Tổngvùng đen(pixel) - Tổngvùng trắng(pixel) Như vậy ta cĩ thể thấy rằng, để tính các giá trị của đặc trưng Haar-like, ta phải tính tổng của các vùng pixel trên ảnh. Nhưng để tính tốn các giá trị của các đặc trưng Haar-ike cho tất cả các vị trí trên ảnh địi hỏi chi phí tính tốn khá lớn, khơng đáp ứng được cho các ứng dụng địi hỏi tính run-time. Do đĩ Viola và Jones đưa ra một khái niệm gọi là Integral Image để tính tốn nhanh cho các đặc trưng cơ bản. Sau này, Lienhart kế thừa Integral Image (SAT) và đưa thêm khái niệm Rotated Summed Area Table (RSAT) dùng để tính tốn nhanh cho các đặc trưng xoay 1 gĩc 45o. Integral Image là một mảng 2 chiều với kích thước bằng với kích của ảnh cần tính các đặc trưng Haar-like, với mỗi phần tử của mảng này được tính bằng cách tính tổng của điểm ảnh phía trên (dịng-1) và bên trái (cột-1) của nĩ. Bắt đầu từ vị trí trên, bên trái đến vị trí dưới, phải của ảnh, việc tính tốn này đơn thuần chỉ đựa trên phép cộng số nguyên đơn giản, do đĩ tốc độ thực hiện rất nhanh. Hình 10: Cách tính Integral Image của ảnh Sau khi đã tính được Integral Image, việc tính tổng điểm ảnh của một vùng bất kỳ nào đĩ trên ảnh thực hiện rất đơn giản theo cách sau: (Giả sử ta cần tính tổng điểm ảnh của vùng D như trong hình 11): D = A + B + C + D – (A+B) – (A+C) + A Với A + B + C + D chính là giá trị tại điểm P4 trên Integral Image, tương tự như vậy A+B là giá trị tại điểm P2, A+C là giá trị tại điểm P3, và A là giá trị tại điểm P1. Vậy ta cĩ thể viết lại biểu thức tính D ở trên như sau: Với các đặc trưng Haar-like xoay 45o Integral Image tại một điểm (x, y) được tính theo cơng thức: Tổng pixel của một vùng bất kỳ trên ảnh vẫn được tính theo cách sau: D = A + B + C + D – (A+B) – (A+C) + A Như vậy tổng các điểm ảnh trong một hình chữ nhật (kể cả trường hợp xoay 45º) bất kì đều cĩ thể được tính nhanh dựa trên integral image tại 4 đỉnh của nĩ : Sum (D ) = .4 - 2 – 3 + 1 Cascade of Classifiers Ta thấy quá trình huấn luyện, bộ phân loại phải duyệt qua tất cả các đặc trưng của các mẫu trong tập training. Việc này tốn rất nhiều thời gian. Tuy nhiên, trong các mẫu đưa vào, khơng phải mẫu nào cũng thuộc loại khĩ nhận dạng, cĩ những mẫu background rất dễ nhận ra (ta gọi đây là những mẫu background đơn giản). Đối với những mẫu này, ta chỉ cần xét một hay vài đặc trưng đơn giản là cĩ thể nhận diện được chứ khơng cần xét tất cả các đặc trưng. Nhưng đối với các bộ phân loại thơng thường thì cho dù mẫu cần nhận dạng là dễ hay khĩ thì nĩ vẫn sẽ xét tất cả các đặc trưng mà nĩ rút ra được trong quá trình học. Do đĩ, chúng tốn thời gian xử lý một cách khơng cần thiết. Cascade of Classifiers được xây dựng chính là nhằm rút ngắn thời gian xử lý, giảm thiểu false alarm cho bộ phân loại. Cascade tree gồm nhiều stage (hay cịn gọi là layer), mỗi stage của cây sẽ là một stage classifier. Một mẫu để được phân loại là đối tượng thì nĩ cần phải đi qua hết tất cả các stages của cây. Các stage classifiers ở stage sau được huấn luyện bằng những mẫu negative mà stage classifier trước nĩ nhận dạng sai, tức là nĩ sẽ tập trung học từ các mẫu background khĩ hơn, do đĩ sự kết hợp các stage classifiers này lại sẽ giúp bộ phân loại cĩ false alarm thấp. Với cấu trúc này, những mẫu background dễ nhận diện sẽ bị loại ngay từ những stages đầu tiên, giúp đáp ứng tốt nhất đối với độ phức tạp gia tăng của các mẫu đưa vào, đồng thời giúp rút ngắn thời gian xử lý. Thuật tốn Cascade training: Minh họa thuật tốn Cascade training: . Hình 13 minh họa sự huấn luyện của một cascade gồm N stages. Ở mỗi stage, weak classifier tương ứng sẽ được huấn luyện sao cho độ chính xác của nĩ là h và false alarm bằng f. Cascade of boosting classifiers Cascade of boosting classifiers là mơ hình cascade of classifiers với mỗi classifier được xây dựng bằng Adaboost sử dụng haar-like. Viola và Jones đã sử dụng rất thành cơng cascade of boosting classifiers cho bài tốn nhận dạng mặt người. Với tập huấn luyện gồm 4196 hình mặt người được đưa về ảnh grayscale kích thước 24x24 và 9500 hình background, hai ơngđã xây dựng cấu trúc cascade tree gồm 38 stage với tổng cộng 6060 đặc trưng haar-like. Thực nghiệm đã cho thấy classifier ở stage đầu tiên sử dụng 2 đặc trưng và loại được khoảng 50% mẫu background (khơng phải mặt người) và cĩ độ chính xác là d = 100%. Classifier ở stage thứ 2 sử dụng 10 đặc trưng loại được 80% mẫu background với độ chính xác vẫn là 100%. Hệ thống này được so sánh với hệ thống của Rowley-Baluja-Kanade (sử dụng mạng neural), Schneiderman-Kanade (sử dụng phương pháp thống kê), và cho thấy tỉ lệ nhận dạng là ngang nhau, trong khi hệ thống của Viola và Jones chạy nhanh hơn đến 15 lần so với hệ thống của Rowley-Baluja-Kanade và nhanh hơn 600 lần hệ thống của Schneiderman-Kanade. Lý do mà cấu trúc cascade đạt tốc độ nhận dạng nhanh chính là nhờ nĩ sớm loại bỏ được các mẫu background đơn giản (thường cĩ số lượng lớn hơn nhiều so với các mẫu chứa object – các mẫu chưa khuơn mặt cần tiến hành nhận dạng). Bên cạnh đĩ, hệ thống của Viola và Jones cũng đạt được độ chính xác khá cao nhờ vào thuật tốn cascade training, các bộ nhận dạng được huấn luyện bằng AdaBoost với đặc trưng Haar-like mơ tả tốt thơng tin đối tượng, cùng với cách Integral Image tính nhanh các đặc trưng, khơng làm giảm tốc độ nhận dạng của hệ thống. Như vậy, mơ hình Cascade of Boosted Classifiers thật sự là một cách tiếp cận tốt cả về tốc độ lẫn khả năng nhận dạng, rất phù hợp với bài nhận dạng mặt người. CHƯƠNG 5- XÂY DỰNG ỨNG DỤNG DỰA TRÊN CƠ SỞ LÝ THUYẾT Phát hiện mặt người trong ảnh cĩ nhiều ứng dụng trong cuộc sống, tuy nhiên, trong khĩa luận này, tơi chỉ xây dựng một chương trình nhỏ để minh họa cho các lý thuyết ở trên. Cụ thể đấy là một chương trình phát hiện mặt người trong ảnh được viết trên nền visual c ++ của Microsoft, sử dụng thư viện mã nguồn mở OpenCV của Intel. Sơ lược về OpenCV Open VC là thư viện mã nguồn mở của intel về thị giác máy tính. Nĩ cung cấp một bộ mã nguồn bao gồm hàng trăm hàm, lớp dựa trên các thuật tốn về xử lý ảnh cũng như Computer vision dùng ngơn ngữ C/C++. Open CV thể hiện sự đa dạng của trí tuệ nhân tạo. Được ứng dụng nhiều trong các bài tốn nhận dạng mặt, dị tìm mặt, phát hiện mặt, lọc Kalman, … Cấu trúc tổng quan của OpenCV bao gồm 5 phần chính. 4 trong 5 phần đĩ được chỉ ra trong hình vẽ dưới. Phần CV bao gồm các thư viện cơ bản về xử lý ảnh và các giải thuật về thị giác máy tính. ML là bộ thư viện về các thuật tốn học máy, bao gồm rất nhiều bộ phân cụm và phân loại thống kê. HighGUI chứa đựng những thủ tục vào ra, các chức năng về lưu trữ cũng như đọc các file ảnh và video. Phần thứ 4, Cxcore chứa đựng các cấu trúc dữ liệu cơ bản ( ví dụ như cấu trúc XML, các cây dữ liệu …). Phần cuối cùng là CvAux, phần này bao gồm các thư viện cho việc phát hiện, theo dõi và nhận dạng đối tượng (khuơn mặt, mắt …). Tổng quan về một hệ thống phát hiện mặt người trong ảnh Về cơ bản, từ ảnh gốc ban đầu, hệ thống sẽ chia ảnh thành vơ số vùng nhỏ để tính các đặc trưng, sau đấy đưa các đặc trưng. Tiếp theo, chương trình sẽ xác định các vùng khả quan (các ứng viên) cĩ thể là khuơn mặt, cuối cùng các ứng viên này sẽ được đưa vào một bộ phân loại để tiến hành xác định ứng viên nào là mặt người. Phân tích – thiết kế hệ thống phát hiện mặt người Phân tích Nhiệm vụ chính của chương trình là dị tìm khuơn mặt từ một bức ảnh, một file video hoặc từ webcam, sau đấy lưu khuơn mặt vào csdl để phục vụ cho các mục đích khác (sẽ được phát triển sau). Như vậy các chức năng chương trình bao gồm: • Kết nối đến webcam, đọc các file ảnh và video. • Phát hiện các nhiều khuơn mặt cĩ trong bức ảnh, video, webcam ... • Lưu ảnh khuơn mặt được phát hiện vào csdl. Thiết kế hệ thống Với các chức năng ở trên, chương trình được chia thành thành 3 phần chính: Phần xử lý đầu vào, phần phát hiện khuơn mặt và phần xử lý đầu ra. Xử lý đầu vào: Chương trình nhận đầu vào là file ảnh, video hoặc webcam, tuy nhiên, việc phát hiện khuơn mặt được thực hiện trên các bức ảnh, do đĩ, với đầu vào là webcam hay file video, ta phải chuyển thành các ảnh tĩnh và xử lý trên từng ảnh tĩnh. Sau khi đã cĩ ảnh đầu vào rồi thì sẽ chuyển ảnh cho giai đoạn xử lý tiếp theo, đĩ là phát hiện các khuơn mặt cĩ trong ảnh. Phát hiện khuơn mặt Phần này xử lý chính nghiệp vụ của hệ thống. Sau khi cĩ ảnh truyền vào, hệ thống sẽ thực hiện chức năng phát hiện khuơn mặt cĩ trong ảnh. Việc phát hiện khuơn mặt được thực hiện nhanh bằng thuật tốn adaboost thơng qua hàm cvHaarDetectObjects() của OpenCV. Hàm này thực hiện việc phát hiện đối tượng dựa trên các đặc trưng haar-like, cụ thể là nhờ vào một bộ Cascade được truyền vào cho hàm. Bộ Cascade được xây dựng theo dạng cây (tree-node) và đã được huấn luyện từ trước. Việc huấn luyện bộ Cascade cĩ thể thực hiện từ những dữ liệu thu thập được để phục vụ cho quá trình nhận dạng. Ví dụ, muốn nhận dạng một người A, ta thu thập các ảnh khuơn mặt của người A với nhiều tư thế, gĩc chụp và điều kiện chụp khác nhau, sau đấy cho bộ nhận dạng học theo thuật tốn Cascade training. Tuy nhiên việc nhận dạng khuơn mặt là một cơng việc khĩ và tốn nhiều thời gian, do đĩ, tơi khơng thực hiện nĩ trong khĩa luận của mình. Xử lý đầu ra. Khuơn mặt sau khi được phát hiện sẽ được tách ra khỏi bức ảnh và lưu dưới dạng ảnh bitmap với phần mở rộng là *.jpg. Đối với đầu vào là các file ảnh, dữ liệu đầu ra cũng là file ảnh đấy nhưng cĩ lưu vị trí khuơn mặt đã được phát hiện trên bức ảnh, đồng thời tách các riêng khuơn mặt và lưu vào cơ sở dữ liệu. Đối với đầu vào là các file video hoặc webcam. Các khuơn mặt sẽ được tách ra và lưu lại thành các file ảnh riêng rẽ, và được đánh số thứ tự theo tên file video. Ví dụ như file video test.avi thì ảnh các khuơn mặt phát hiện được sẽ được đánh số theo thứ tự như sau: test.avi_1.jpg, test.avi_2.jpg … Thiết kế cơ sở dữ liệu Lưu trữ cơ sở dữ liệu là một phần quan trọng của ứng dụng. Việc xây dựng, tổ chức cơ sở dữ liệu ảnh hướng lớn đến tốc độ của chương trình. Do đĩ tơi đã xây dựng và quản cơ sở dữ liệu bằng hệ quản trị cơ sở Oracle, đây là hệ quản trị cơ sở dữ liệu mạnh, đáp ứng được nhiều yêu cầu về quản lý cơ sở dữ liệu của các doanh nghiệp lớn, đặc biệt là các ngân hàng hay kho bạc. Tuy hiện tại, chương trình chỉ dừng lại ở mức phát hiện khuơn mặt trong ảnh, nhưng việc xây dựng một cơ sở dữ liệu tốt sẽ là tiền đề để cĩ thể phát triển chương trình thành các ứng dụng lớn hơn sau này. Hệ thống cần lưu trữ các dữ liệu: Ảnh khuơn mặt sau khi đã được phát hiện. Đối với đầu vào là file ảnh: • Lưu ảnh đầu vào cùng vị trí khuơn mặt đã được phát hiện trên bức ảnh • Lưu từng khuơn mặt được phát hiện. Đối với đầu vào là file video, hoặc webcam: • Lưu các khuơn mặt được phát hiện Như vậy các thơng tin trong cơ sở dữ liệu bao gồm 2 thực thể sau: • ẢNH GỐC ( IMAGES ): Ảnh đầu vào. Các thuộc tính bao gồm: ID: Mã ảnh, kiểu Integer, là khĩa chính và cĩ ràng buộc là tự tăng. Name: Tên của bức ảnh, kiểu dữ liệu varchar2(200). Trong trường hợp đầu vào là video thì tên sẽ được lấy theo tên của file video, cịn nếu đầu vào là webcam thì sẽ đặt là webcam_ID (thêm ID ở trên vào tên). Image: Lưu mã nhị phân của bức ảnh. URL: lưu đường dẫn đến bức ảnh, kiểu giữ liệu varchar2(1000) Lưu ý: Trong trường hợp file đầu vào là video hoặc webcam thì các trường Image, và URL sẽ nhận giá trị null. KHUƠN MẶT ( FACES ): Các khuơn mặt phát hiện được. Các thuộc tính bao gồm: - ID: Mã ảnh, kiểu Integer, là khĩa chính và cĩ ràng buộc là tự tăng. - IMAGE_ID: ID của ảnh gốc, kiểu dữ liệu Interger, là khĩa ngoại tham chiếu đến bảng ẢNH GỐC. - Name: Tên của khuơn mặt, được đặt theo tên ảnh gốc, đồng thời thêm số thứ tự để nhận biết các khuơn mặt của cùng ảnh gốc. - Image: Lưu mã nhị phân của ảnh khuơn mặt. - URL: lưu đường dẫn đến ảnh khuơn mặt, kiểu giữ liệu varchar2(1000). Thiết kế giao diện Giao diện của chương trình được thiết kế thân thiện và đơn giản. Tập trung vào chức năng chính phát hiện khuơn mặt trong ảnh. Bố cục trên giao diện được chia thành 4 phần. Phần 1, chọn đầu vào. Các ảnh hoặc video cĩ thể được lưu tùy ý trong các thư mục trên máy tính của người dùng. Phần thứ hai là danh sách các khuơn mặt đã được phát hiện và được lưu trong cơ sở dữ liệu. Phần thứ 3 là danh sách các Cascade. Cuối cùng là phần xử lý và hiện kết quả (số khuơn mặt phát hiện được, thời gian thực hiện). Người dùng chọn bức ảnh, chọn bộ Cascade, sau đấy nhấn vào nút “Detect” để thực hiện việc xác định khuơn mặt trên ảnh. Giao diện của chương trình được thể hiện như hình dưới. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Kết luận Trên cơ sở nghiên cứu về bài tốn phát hiện mặt người trong ảnh. Đặc biệt là thuật tốn Adaboost, các đặc trưng haar-like và mơ hình Cascade of Classifier. Tơi đã áp dụng thành cơng mơ hình Cascade of Classfier vào bài tốn phát hiện mặt người trong ảnh. Tuy kết quả đạt được chưa cao, nhưng đây là bước đầu để phát triển bài tốn nhận dạng mặt (face recognition) người sau này. Bên cạnh đĩ, trong quá trình xây dựng chương trình demo, tơi đã tìm hiểu về thư viện mã nguồn mở OpenCV, hệ quản trị cơ sở dữ liệu Oracle, qua đĩ biết cách sử dụng các hàm trong thư viện OpenCV và quản lý cơ sở dữ liệu bằng hệ quản trị cơ sở dữ liệu Oracle. Về chương trình demo, sau khi thử nghiệm với tập ảnh lớn và webcam. Chương trình đạt kết quả tốt, thời gian phát hiện nhanh đối với các ảnh mặt người chụp thẳng, chất lượng ảnh tốt (chụp bằng máy kĩ thuật số), tuy nhiên đối với các ảnh chụp nghiêng hay ảnh cĩ mầu sắc quá tối thì chương trình gần như khơng thể phát hiện được khuơn mặt trong bức ảnh đấy. Hướng phát triển Cĩ nhiều hướng phát triển cho chương trình này, cĩ thể phát triển cả về mặt ứng dụng và mặt thuật tốn (để cải thiện hiệu quả phát hiện mặt người). Cĩ thể xây dựng một ứng dụng chỉ cần đến phát hiện mặt người mà khơng cần nhận dạng. Ví dụ như một hệ thống ghép hình, ghép khuơn mặt phát hiện được vào trong một bức ảnh khác (chẳng hạn như ghép khuơn mặt của người sử dụng cho khuơn mặt của người nổi tiếng). Ngồi ra cĩ thể phát triển chương trình theo hướng nhận dạng khuơn mặt, xây dựng một hệ thống để học các đặc trưng của những người cần nhận dạng. Khi thực hiện, đầu tiên ta đưa qua bức ảnh qua chương trình phát hiện mặt người để phát hiện nhanh các khuơn mặt cĩ trong ảnh, sau đấy so sách các khuơn mặt đĩ với các khuơn mặt mà chương trình đã được “học” từ trước, so sánh các đặc trưng của hai khuơn mặt, nếu trùng thì đưa ra thơng tin về khuơn mặt được nhận dạng.