Luận văn Phát hiện mặt người trong ảnh và ứng dụng

iê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. 13  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 14  để 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. 15  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 16  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à khuơn mặt. Các đặc tính đã được học ở trong hình thái các mơ hình phân bố hay các tham 17  số của một hàm số nên cĩ thể dùng các đặc tính này để xác định khuơn mặt người. Đồng thời, bài tốn giảm số chiều thường được quan tâm để tăng hiệu quả tính tốn cũng như 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. a. 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 18  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%. b. 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à 19  khơng phải khuơn mặt). Chất lượng của siêu phẳng này phụ thuộc vào khoảng cách giữa các vector, tức là phụ thuộc vào các đặc trưng của ảnh. Support Vector Machine đã được Osuna [5] áp dụng đầu tiên (để xác định khuơn mặt người). SVM được xem như là một kiểu phân loại mới vì trong khi hầu hết các phương pháp phân loại khác (như Mạng Bayes, Nueral, RBF) đều dùng tiêu chí tối thiểu lỗi huấn luyện (rủi ro do kinh nghiệm), trong khi SVM dùng quy nạp (được gọi là tối thiểu rủi ro cấu trúc). Phân loại SVM là một phân loại tuyến tính, do đĩ nĩ cũng dùng một siêu phẳng để tách dữ liệu. Dựa trên một số kết hợp cĩ các trọng số của một tập con nhỏ các vector huấn luyện, các vector này được gọi là support vector. Ước lượng siêu phẳng trong SVM thì tương đương giải một bài tốn tuyến tính bậc hai. Osuna [5] đã phát triển phương pháp SVM một cách hiệu quả cho bài tốn xác định khuơn mặt người. Ơng dùng 10,000,000 mẫu cĩ kích thước 19x19 pixel, hệ thống của ơng cĩ tỷ lệ lỗi ít hơn và nhanh hơn rất nhiều. d. Mơ hình Markov ẩn Mơ hình Markov ẩn ( Hidden Markov Model – HMM ) là một mơ hình thống kê trong đĩ hệ thống được mơ hình hĩa được cho là một quá trình Markov với các tham số khơng biết trước và nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được, dựa trên sự thừa nhận này. Các tham số của mơ hình được rút ra sau đĩ cĩ thể sử dụng để thực hiện các phân tích kế tiếp, ví dụ cho các ứng dụng nhận dạng mẫu. Một giả thuyết quan trọng của mơ hình Markov ẩn là các mẫu cĩ thể được đặc tính hĩa 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, đây là một trong những định nghĩa rõ ràng. 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. Để hình dung về HMM, ta xét ví dụ cụ thể sau: Giả sử A cĩ một người bạn B sống ở rất xa. Hàng ngày thì B đều gọi điện cho A để kể về những việc mà B đã làm trong ngày. 20  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. Hình 4: các vector quan sát để huấn luyện cho HMM 21  Hình 5: Các trạng thái ẩn Đố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. Hình 6: Xác định khuơn mặt bằng HMM Mỗi trạng thái lại cĩ những trạng thái nhỏ bên trong: trạng thái trán cĩ ba trạng thái nhỏ bên trong; trạng thái mắt cĩ năm trạng thái nhỏ bên trong. 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. 22  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. 23  Chương 3 CƠ SỞ LÝ THUYẾT 1. 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. 24  Tiếp theo, chúng ta sẽ xây dựng tập D3 từ những mẫu khơng được phân loại tốt bởi sự kết hợp giữa C1 và C2: những mẫu cịn lại trong D mà C1 và C2 cho kết quả khác nhau. Như vậy, D3 sẽ gồm những mẫu mà C1 và C2 hoạt động khơng hiệu quả. Sau cùng, 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 Hình 7: Boosting 1.2. 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. 25  Để 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 đĩ chưa 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) k: ngưỡng 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: 26  Sơ đồ khối: 1. Cho một tập gồm n mẫu cĩ đánh dấu (x1,y1), (x2,y2),… (xn,yn) với xk = (xk1, xk2, … , xkm) là vector đặc trưng và yk {-1, 1} là nhãn của mẫu (1 ứng với object, -1 ứng với background). 2. Khởi tạo trọng số ban đầu cho tất cả các mẫu: với m là số mẫu đúng (ứng với object và y = 1) và l là số mẫu sai (ứng với background và y = -1). 3. Xây dựng T weak classifiers Lặp t = 1, …, T • Với mỗi đặc trưng trong vector đặc trưng, xây dựng một weak classifier hj với ngưỡng θj và lỗi εj. • Chọn ra hj với εj nhỏ nhất, ta được ht: • Cập nhật lại trọng số: • Trong đĩ: : Hệ số dùng để đưa về đoạn [0,1] (normalization factor) 4. Strong classifier được xây dựng : 27  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: Bắt đầu huấn luyện Khởi tạo tập đặc trưng ban đầu Xác định các đặc trưng trong từng mẫu, xây dựng các bộ phân loại yếu tương ứng Đặc trưng haar-like Tính tốn giá trị lỗi cho mỗi đặc trưng (false alarm) Xác định ngưỡng Chọn weak classifier cĩ giá trị lỗi bé nhất Lưu weak classifier được chọn False alarm ≤ max false alarm Tập các mẫu và trọng số Tập các mẫu Mẫu sai Mẫu đúng Cập nhật lại trọng số Sai Kết thúc, strong classifier đuợc xây dựng Đúng 28  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. 1.3. 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 trư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: Hình 8 : 4 đặt trưng Haar-like cơ bản Để á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 đặt 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: 1. Đặc trưng cạnh (edge features): 2. Đặc trưng đường (line features): 29  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- like 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. P(x,y) 30  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: Hình 11:Ví dụ cách tính nhanh tổng các điểm ảnh của vùng D trên ảnh Hình 12: Ví dụ cách tính nhanh tổng điểm ảnh của vùng D trên ảnh với các đặc trưng xoay 45o 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: RSAT(x,y) B A C 2 4 1 3 D (a) (b) A C B D P1  P2  P3  P4  31  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 1.4. 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: 32  Minh họa thuật tốn Cascade training: Hình 13: cascade of classifiers 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.      h h h 1-f 1-f 1-f 1-f stage 1 2 N-1 N…… hitrate = hN falsealarms = fN Input pattern classified as a non-object 1. Gọi: F là giá trị false alarm và d là độ chính xác của weak classifier ở mỗi stage Ftarget: Giá trị max false alarm. P, N là số lượng mẫu positive và negative. Pi, Ni là tập positive và negative cho bộ phân lớp ở tầng thứ i. Fi, Di: Giá trị false alarm và độ chính xác của cascade trước khi đến tầng thứ i. 2. Khởi tạo i=0; F0=1.0; D0 = 1.0 3. Lặp: while Fi>Ftarget • i = i+1; • Huấn luyện bộ phân loại hi từ tập Pi và Ni với detection rate d và max false alarm f. Thêm hi vào cây phân lớp. • Dùng cây phân lớp hiện cĩ để tính Fi: Duyệt qua N mẫu negative cho đến khi nào tìm đủ n mẫu mà cây phân lớp hiện cĩ phân loại sai. ( • N := • Nếu Fi >Ftarget N = { số mẫu sai ở stage hiện tại phân loại sai }. P = { số mẫu positive mà stage hiện tại phân loại dúng } 33  1.5. 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. Hình 14: Cascade of boosting classifiers 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. I Y Y Y N N N N C L A S S NON-CLASS 34  Chương 4 XÂY DỰNG ỨNG DỤNG 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. 1. 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. Hình 15: Cấu trúc cơ bản của OpenCV 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ơ CV Các hàm về xử lý ảnh và giải thuật về thị giác máy tính CXCORE Các cấu trúc dữ liệu cơ bản, cấu trúc XML, các hàm về đồ họa … MLL Các thuật tốn học máy, bao gồm các bộ phân cụm, phân loại thống kê HighGUI Các hàm và thủ tục làm việc với file ảnh và file video 35  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 …). 2. Tổng quan về một hệ thống phát hiện mặt người trong ảnh Hình 16: Tổng quan về 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. 3. Phân tích – thiết kế hệ thống phát hiện mặt người 3.1. 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 gốc Tính các đặc trưng nhanh từ nhiều tỉ lệ Integral Image Các hàm Haar cơ bản Ước lượng các đặc trưng Điều chỉnh thơng số Adaboost Chọn đặc trưng Số lượng lớn các đặc trưng Cấu trúc phân tầng (Cascade of classifier) Một tập nhỏ các đặc trưng Quyết định kết quả  C1  C2 Cn I Y Y N N N C L A S S NON-CLASS 36  Hình 17: Biểu đồ ngữ cảnh của hệ thống 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. 3.2. 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. a. Xử lý đầu vào: Đầu vào (ảnh, video hoặc webcam) Phát hiện nhanh khuơn mặt bằng Adaboost Lưu khuơn mặt vào CSDL Cĩ khuơn mặt 0 HỆ THỐNG PHÁT HIỆN MẶT NGƯỜI TRONG ẢNH NGƯỜI DÙNG Capture ảnh Khuơn mặt đã được phát hiện 37  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. b. 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. c. 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 … 38  Hình 18: Biểu đồ phân rã chức năng. 3.3. 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. 3.2.Lưu ảnh vào CSDL 2.Phát hiện nhanh khuơn mặt bằng Adaboost 1.Xử lý đầu vào 1.1. Capture ảnh 3. Xử lý đầu ra HỆ THỐNG PHÁT HIỆN MẶT NGƯỜI TRONG ẢNH 3.1. Lưu ảnh vào thư mục thích hợp trên máy 39  - 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). Hình 19: Sơ đồ thực thể quan hệ ( ERM ). 3.4. 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. IMAGES ID Name Image ỦRL FACES ID Name Image ỦRL Image_ID 40  Phần 1, dành cho người dùng chọn đầu vào, cĩ thể là ảnh, video hoặc webcam. 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. Hình 20: Giao diện của chương trình 41  KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. 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. Đối với webcam, thì hiệu xuất của chương trình cịn tùy theo chất lượng của loại webcam được sử dụng, tuy nhiên cũng tương tự như với phát hiện khuơn mặt trong ảnh, chương trình sẽ khơng thể phát hiện mặt người trong điều kiện độ sáng quá yếu và gĩc quay nghiêng quá 20o. 2. 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 42  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.  b  Tài liệu tham khảo. [1] A. Lanitis, C.J. Taylor, and T.F. Cootes, “An Automatic Face Identification System Using lexible Appearance Models”, Image and Vision Computing, vol. 13, no. 5, pp. 393-401, 1995. [2] Andrew King, “A Survey of Methods for Face Detection”, 2003 [3] A. Yuille, P. Hallinan, and D. Cohen, “Feature Extraction from Faces Using eformable Templates”, Int’l J. Computer Vision, vol. 8, no. 2, pp. 99-111, 1992. [4] D.G. Kendall, “Shape Manifolds, Procrustean Metrics, and Complex Projective Shapes”, Bull. London Math. Soc., vol. 16, pp. 81-121, 1984. [5] E. Osuna, R. Freund, and F. Girosi, “Training Support Vector Machines: An Application to Face Detection” Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 130-136, 1997. [6] Fuzhen Huang and Jianbo Su, “Multiple Face Contour Detection Using adaptive Flows”, Sinobiometrics 2004, LNCS 3338, pp. 137-143, Springer-Verlag Berlin eidelberg, 2004. [7] G. Yang and T. S. Huang, “Human Face Detection in Complex Background”, Pattern Recognition, vol. 27, no. 1, pp. 53-63, 1994. [8] H.P. Graf, T. Chen, E. Petajan, and E. Cosatto, “Locating Faces and Facial Parts”, Proc. First Int’l Workshop Automatic Face and Gesture Recognition, pp. 41-46, 1995. [9] J. Canny, “A Computational Approach to Edge Detection”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, June 1986. [10] J. Sobottka and I. Pitas, “Segmentation and Tracking of Faces in Color Images”, Proc. Second Int’l Conf. Automatic Face and Gesture Recognition, pp. 236-241, 1996.  c  [11] K. Lam and H. Yan, “Fast Algorithm for Locating Head Boundaries,” J.Electronic Imaging, vol. 3, no. 4, pp. 351-359, 1994. [12] K.V. Mardia and I.L. Dryden, “Shape Distributions for Landmark Data”, Advanced Applied Probability, vol. 21, pp. 742-755, 1989. [13] Ming-Hsuan Yang, David Kriegman, and Narendra Ahuja, "Detecting Faces in Images: A Survey", IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 24, no. 1, pp. 34-58, 2002. [14] M. Kirby and L. Sirovich, “Application of the Karhunen-LoeveProcedure for the Characterization of Human Faces”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 1, pp. 103-108, Jan. 1990 [15] P. Sinha, “Object Recognition via Image Invariants: A Case Study”, Investigative Ophthalmology and Visual Science, vol. 35, no. 4, pp. 1735-1740, 1994. [16] P. Sinha, “Processing and Recognizing 3D Forms,” PhD thesis, Massachusetts Inst. of Technology, 1995. [17] P. Viola and M. J. Jones, “Robust Real-Time Face Detection”, International Journal of Computer Vision 57(2), 137-154, Kluwer Academic Publishers, Netherlands, 2004. [18] T.F. Cootes and C.J. Taylor, “Locating Faces Using Statistical Feature Detectors”, Proc. Second Int’l Conf. Automatic Face and Gesture Recognition, pp. 204-209, 1996. [19] T.K. Leung, M.C. Burl, and P. Perona, “Finding Faces in Cluttered Scenes Using Random Labeled Graph Matching”, Proc. Fifth IEEE Int’l Conf. Computer Vision, pp. 637-644, 1995. [20] T. Sakai, M. Nagao, and S. Fujibayashi, “Line Extraction and Pattern etection in a Photograph”, Pattern Recognition, vol. 1, pp. 233-248, 1969. [21] Robin Hewitt, “Seeing with OpenCV: A Five-Part Series”, 2007