Luận văn Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TRẦN LÊ HỒNG DŨ PHÁT HIỆN KHUÔN MẶT DỰA TRÊN ĐẶC TRƯNG LỒI LÕM LUẬN VĂN THẠC SĨ NGÀNH TIN HỌC Thành phố Hồ Chí Minh - 2005 ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TRẦN LÊ HỒNG DŨ PHÁT HIỆN KHUÔN MẶT DỰA TRÊN ĐẶC TRƯNG LỒI LÕM Chuyên ngành: TIN HỌC Mã số: 1.01.10 LUẬN VĂN THẠC SĨ (Chuyên ngành Tin học) NGƯỜI HƯỚNG DẪN KHOA HỌC: GS. DƯƠNG NGUYÊN VŨ Thành phố Hồ Chí Minh - 2005 Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 1 Nội dung Trang Mục lục 1 Lời cám ơn 4 Chương 1. Giới thiệu 5 1.1 Bài toán nhận dạng mặt người và những khó khăn 5 1.1.1 Bài toán nhận dạng mặt người 5 1.1.2 Những khó khăn của nhận dạng khuôn mặt 5 1.2 Các ứng dụng liên quan đến nhận dạng mặt người 6 1.3 Tổng quan kiến trúc của một hệ thống nhận dạng mặt người 7 1.4 Xác định phạm vi đề tài 8 Chương 2. Các công trình liên quan 10 2.1 Các hướng tiếp cận liên quan đến phát hiện và nhận dạng khuôn mặt 10 2.2 Các tiếp cận liên quan đến phân tích đặt trưng lồi lõm 11 2.3 Các hướng tiếp cận sử dụng đặc trựng tựa lồi lõm cho phát hiện khuôn mặt 12 2.4 Nhận xét về các hướng tiếp cận hiện tại 12 Chương 3. Đặc trưng lồi lõm 14 3.1 Lồi và Lõm 14 3.2 Rút trích vùng lồi và vùng lõm 16 Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 2 3.2.1 Điểm lồi và điểm lõm 16 3.2.2 Dò tìm và rút trích vùng lồi và vùng lõm 16 3.2.3 Dò tìm và phát hiện vùng lồi, lõm ở nhiều mức 19 3.2.4 Tối ưu tốc độ của việc dò tìm 21 3.3 Xây dựng cây cấu trúc lồi lõm 22 3.4 Xây dựng hàm tính độ tương đồng giữa hai cây 26 3.4.1 Độ tương đồng giữa 2 nút trên cây 26 3.4.2 Độ tương đồng giữa hai cây 27 3.4.3 Không gian cây và khoảng cách giữa hai cây 28 Chương 4. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm 30 4.1 Tập mẫu học 30 4.2 Mô hình thống kê 31 4.2.1 Gán nhãn 31 4.2.2 Thống kê 32 4.2.3 Đánh giá dùng cho phát hiện khuôn mặt 33 4.2.4 Hậu xử lý 34 4.3 Cơ sở lý thuyết của mô hình 35 Chương 5. Thử nghiệm và kết quả 38 5.1 Thử nghiệm 38 5.2 Kết quả 38 Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 3 5.3 Nhận xét 39 5.4 Một số kết quả tiêu biểu 40 Chương 6. Kết luận và hướng phát triển 46 6.1 Kết luận 46 6.2 Hướng phát triển 46 Danh mục công trình của tác giả 48 Tài liệu tham khảo 49 Phụ lục 53 Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 4 LỜI CẢM ƠN Sau một thời gian học tập và nghiên cứu, cuối cùng tôi cũng đã hoàn thành bài luận nghiên cứu của mình. Đây là thời điểm tốt nhất tôi có dịp được bày tỏ lòng biết ơn của mình đến những người thân đã giúp đỡ động viên tôi trong suốt quá trình tôi thực hiện bài luận này. Trước tiên tôi xin chân thành gởi lời cảm ơn sâu sắc đến thầy tôi, người hướng dẫn khoa học, định hướng nghiên cứu cho tôi trong suốt thời gian thực hiện luận văn này, GS.Dương Nguyên Vũ. Thầy đã dạy cho tôi không chỉ những kiến thức khoa học mà còn cả những bài học về cuộc sống, về tình người. Cám ơn thầy đã mang đến cho tôi những đôi cánh để tôi có thể đến với khoa học thật sự. Xin chân thành cảm ơn thầy Đức, TS. Dương Anh Đức, thầy Bắc, PGS.TS Lê Hoài Bắc đã tận tình giúp đỡ, theo dõi và động viên cho tôi trong suốt quá trình thực hiện luận văn này. Con xin cám ơn bà ngoại, ba, mẹ, anh hai, chị ba đã hết sức thông cảm và chia sẽ với con những khó khăn trong lúc làm luận văn này. Xin cám ơn những người bạn thân yêu, những người đã yêu mến, chia sẽ với tôi trong lúc tôi thực hiện luận văn này. Xin cám ơn các thầy cô, các anh chị và các bạn đồng nghiệp trong Khoa Công nghệ thông tin, ĐH Khoa học tự nhiên đã giúp đỡ, tạo điều kiện tốt nhất để tôi có thể hoàn thành tốt luận văn này. Luận văn này là món quà mà tôi dành tặng cho tất cả mọi người thân yêu của tôi, với tất cả tấm lòng mình! Thành phố Hồ Chí Minh, ngày 10 tháng 11 năm 2005 Trần Lê Hồng Dũ Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 5 CHƯƠNG 1 GIỚI THIỆU 1.1 Bài toán nhận dạng mặt người và những khó khăn 1.1.1 Bài toán nhận dạng mặt người Hệ thống nhận dạng mặt người là một hệ thống nhận vào là một ảnh hoặc một đoạn video (một chuỗi các ảnh). Qua xử lý tính toán hệ thống xác định được vị trí mặt người trong ảnh (nếu có) và xác định là người nào trong số những người hệ thống đã được biết (qua quá trình học) hoặc là người lạ. Hình 1.1 Ví dụ về hệ thống nhận dạng mặt người 1.1.2 Những khó khăn của nhận dạng khuôn mặt Bài toán nhận dạng mặt người là bài toán đã được nghiên cứu từ những năm 70. Tuy nhiên, đây là một bài toán khó nên những nghiên cứu hiện tại vẫn chưa đạt được kết quả mong muốn. Chính vì thế vấn đề này vẫn đang được nhiều nhóm trên Hệ thống nhận dạng mặt người Ảnh input Ảnh output Face ID G. Bush Bin Laden Chưa biết Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 6 thế giới quan tâm nghiên cứu. Khó khăn của bài toán nhận dạng mặt người có thể kể như sau: a. Tư thế, góc chụp: Ảnh chụp khuôn mặt có thể thay đổi rất nhiều bởi vì góc chụp giữa camera và khuôn mặt. Chẳng hạn như: chụp thẳng, chụp xéo bên trái 450 hay xéo bên phải 450, chụp từ trên xuống, chụp từ dưới lên, v.v...). Với các tư thế khác nhau, các thành phần trên khuôn mặt như mắt, mũi, miệng có thể bị khuất một phần hoặc thậm chí khuất hết. b. Sự xuất hiện hoặc thiếu một số thành phần của khuôn mặt: Các đặc trưng như: râu mép, râu hàm, mắt kính, v.v... có thể xuất hiện hoặc không. Vấn đề này làm cho bài toán càng trở nên khó hơn rất nhiều. c. Sự biểu cảm của khuôn mặt: Biểu cảm của khuôn mặt người có thể làm ảnh hưởng đáng kể lên các thông số của khuôn mặt. Chẳng hạn, cùng một khuôn mặt một người, nhưng có thể sẽ rất khác khi họ cười hoặc sợ hãi,v.v... d. Sự che khuất: Khuôn mặt có thể bị che khuất bởi các đối tượng khác hoặc các khuôn mặt khác. e. Hướng của ảnh: Các ảnh của khuôn mặt có thể biến đổi rất nhiều với các góc quay khác nhau của trục camera. Chẳng hạn chụp với trục máy ảnh nghiêng làm cho khuôn mặt bị nghiêng so với trục của ảnh. f. Điều kiện của ảnh: Ảnh được chụp trong các điều kiện khác nhau về: chiếu sáng, về tính chất camera (máy kỹ thuật số, máy hồng ngoại,v.v...) ảnh hưởng rất nhiều đến chất lượng ảnh khuôn mặt. 1.2 Các ứng dụng liên quan đến nhận dạng mặt người Bài toán nhận dạng mặt người có thể áp dụng rộng rãi trong nhiều ứng dụng thực tế khác nhau. Đó chính là lý do mà bài toán này hấp dẫn rất nhiều nhóm nghiên cứu trong thời gian dài. Các ứng dụng liên quan đến nhận dạng mặt người có thể kể như: Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 7 - Hệ thống phát hiện tội phạm: camera được đặt tại một số điểm công cộng như: siêu thị, nhà sách, trạm xe buýt, sân bay,v.v... Khi phát hiện được sự xuất hiện của các đối tượng là tội phạm, hệ thống sẽ gởi thông điệp về cho trung tâm xử lý. - Hệ thống theo dõi nhân sự trong một đơn vị: giám sát giờ ra vào của từng nhân viên và chấm công. - Hệ thống giao tiếp người máy: thay thế việc tương tác giữa người và máy theo những cách truyền thống như: bàn phím, chuột,v.v...Thay vào đó là sử dung các giao tiếp trực quan: biểu cảm khuôn mặt, dấu hiệu, cử chỉ bằng tay (visual input, visual interaction). - Hệ thống tìm kiếm thông tin trên ảnh, video dựa trên nội dung (chỉ mục theo người). Chẳng hạn như: đài truyền hình Việt Nam (VTV) có một kho dữ liệu video tin tức khá lớn cần tìm kiếm nhanh những đoạn video nào có G. Bush hoặc Bin Laden. - Các thệ thống bảo mật dựa trên thông tin trắc sinh học: mặt người, vân tay,v.v... thay vì xác nhận mật khẩu, khóa,v.v... 1.3 Tổng quan kiến trúc của một hệ thống nhận dạng mặt người Một hệ thống nhận dạng mặt người thông thường bao gồm bốn bước xử lý sau: phát hiện khuôn mặt (face detection), phân đoạn khuôn mặt (face alignment hay segmentation), rút trích đặc trưng (feature extraction), và phân lớp khuôn mặt (face classification). Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 8 Hình 1.2 Các bước chính trong một hệ thống nhận dạng mặt người Phát hiện khuôn mặt dò tìm và định vị những vị trí khuông mặt xuất hiện trong ảnh hoặc trên các frame video. Phân đoạn khuôn mặt sẽ xác định vị trí mắt mũi, miệng, và các thành phần khác của khuôn mặt và chuyển kết quả này cho bước rút trích đặc trưng. Từ những thông tin về các thành phần trên khuôn mặt, chúng ta có thể dễ dàng tính được véc-tơ đặc trưng trong bước rút trích đặc trưng. Những véc-tơ đặc trưng này sẽ là dữ liệu đầu vào cho một mô hình đã được huấn luyện trước để phân loại khuôn mặt. Bên cạnh những bước chính nêu trên, chúng ta còn có thể áp dụng thêm một số bước khác như tiền xử lý, hậu xử lý nhằm làm tăng độ chính xác cho hệ thống. Do một số thông số như: tư thế khuôn mặt, độ sáng, điều kiện ánh sáng, v.v…, phát hiện khuôn mặt được đánh giá là bước khó khăn và quan trọng nhất so với các bước còn lại của hệ thống. Trong luận văn này, chúng tôi tập trung chủ yếu vào bước phát hiện khuôn mặt. 1.4 Xác định phạm vi đề tài Trong đề tài này, chúng tôi tập trung tìm kiếm và đề xuất một thuật toán hiệu quả cho việc xác định sự xuất hiện và định vị khuôn mặt nếu có trong ảnh. Do các điều kiện khó khăn của bài toán (nêu trong phần 1.1.2), chúng tôi đưa ra những giả định và ràng buộc sau nhằm giảm độ phức tạp của bài toán phát hiện khuôn mặt: - Thuật toán giải quyết cho ảnh đơn (chưa xử lý cho video) - Ảnh khuôn mặt được chụp thẳng hay góc nghiêng không đáng kể (không quá 100). Phát hiện khuôn mặt (Theo dõi) Phân đoạn khuôn mặt Rút trích đặc trưng Phân lớp khuôn mặt Ảnh/Video Vị trí khuôn mặt Khuôn mặt đã được phân đoạn Véc-tơ đặc trưng Chỉ số khuôn mặt Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 9 - Ảnh được chụp trong điều kiện ánh sáng bình thường (không chụp ngược sáng, chụp bằng máy ảnh kỹ thuật số) Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 10 CHƯƠNG 2 CÁC CÔNG TRÌNH LIÊN QUAN 2.1 Các hướng tiếp cận liên quan đến phát hiện và nhận dạng khuôn mặt Có rất nhiều hướng tiếp cận trước đây đã thực hiện liên quan đến vấn đề phát hiện mặt người. Theo Ming-Hsuan Yang [1], có thể phân loại thành bốn hướng tiếp cận chính: dựa trên tri thức (knowledge-based), đặc trưng bất biến (feature invariant), đối sánh mẫu (template matching), và dựa vào diện mạo (appearance-based) phương pháp này thường dùng một mô hình máy học nên còn được gọi là phương pháp dựa trên máy học (machine learning-based). Các phương pháp dựa trên tri thức: Hướng tiếp cân này chủ yếu dựa trên những luật được định nghĩa trước về khuôn mặt người. Những luật này thường là các mối quan hệ giữa các thành phần trên khuôn mặt. Có một số nghiên cứu từ rất sớm đã áp dụng phương pháp này như của Kanade 1973 [18], G .Yang 1994 [11], và Kotropoulos 1997 [14]. Hướng tiếp cận dựa trên các đặc trưng bất biến: Hướng tiếp cận này cố gắng tìm kiếm những đặc trưng độc lập – những đặc trưng không phụ thuộc vào tư thế khuôn mặt, điều kiện chiếu sáng, và các khó khăn khác. Các đặc trưng như thế được gọi là bất biến và được sử dụng để phát hiện khuôn mặt. Những công trình sử dụng hướng tiếp cận này có thể kể như: K. C. Yow và R. Cipolla 1997 [12], T. K. Leung 1995 [13]. Phương pháp đối sánh mẫu: Trong hướng tiếp cận này, một mẫu khuôn mặt chuẩn được định nghĩa bằng tay trước hoặc được tham số hóa bằng một hàm số. Mẫu này được sử dụng để phát hiện khuôn mặt bằng cách quét nó qua ảnh và tính toán giá trị tương đồng cho mỗi vị trí. Việc xuất hiện một khuôn mặt tại một vị trí nào đó trong ảnh phụ thuộc vào giá trị tương đồng của điểm đó so với mẫu chuẩn. I. Craw Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 11 1992 [17] đã áp dụng một mẫu cứng trong khi A. Lanitis 1995 [15] sử dụng một mẫu có thể biến dạng trong bước phát hiện khuôn mặt. Phương pháp dựa trên máy học: Ngược với phương pháp đối sánh mẫu sử dụng các mẫu được các chuyên gia định nghĩa trước, phương pháp này sử dụng những mẫu được rút trích qua một quá trình học. Nói cách khác, các thuật toán dựa trên máy học dùng các kỹ thuật phân tích thống kê và máy học để xấp xĩ một hàm phân lớp tuyến tính. Có nhiều mô hình máy học được áp dụng trong hướng tiếp cận này: Eigenface (M. Turk và A. Pentland 1991 [16]), Mô hình dựa trên phân phối (K. K. Sung and T. Poggio 1998 [6]), Mạng Nơ-ron (H. Rowley 1998 [7]), Support Vector Machine (E. Osuna et al 1997 [10]), Phân lớp Bayes (H. Schneiderman và T. Kanade 1998 [8]), Mô hình Markov ẩn (A. Rajagopalan et al 1998 [9]), và các mô hình tăng cường (AdaBoost của P. Viola và M. Jones 2001 [4][5]; FloatBoost do Stan Z. Li và Zhen Qiu Zhang 2004 [2][3]). 2.2 Các tiếp cận liên quan đến phân tích đặt trưng lồi lõm Năm 1983, James L. Crowley đã đưa ra khái niệm ridge và peak [19][20]. Ridge là các điểm lồi trên ảnh. Tập các điểm ridge trên ảnh sẽ tạo thành những đường xương sống và các đường này sẽ tạo thành các chùm tia gọi là peak (chùm). James L. Crowley sử dụng phép hiệu của lọc Low Pass để rút ra các điểm ridge (lồi) trên ảnh, và sau đó một thuật toán duyệt để kết chúng lại với nhau thành các đặc trưng ridge và peak. Tiếp sau đó, một số các phương pháp được đề xuất để rút trích các thông tin về ridge và valley (lõm) [23][24][25][26][27][29]. Hầu hết các phương pháp này dùng một bộ lọc để tăng cường thông tin về cạnh trên ảnh sau đó dò tìm quỹ tích các điểm cực trị. Quỹ tích các điểm cực trị này được xem là các đặc trưng lồi và lõm. Trong [23] đặc trưng lồi và lõm được dò tìm trên nhiều độ phân giải khác nhau, cho kết quả đáng kể. Tuy nhiên, chất lượng của các đặc trưng lồi lõm này còn phụ thuộc khá nhiều vào điều kiện chiếu sáng cũng như các mức phân giải được lựa chọn trước. Để giải quyết sự phụ thuộc này, Lindeberg [30] đã đề xuất một phương pháp tự động chọn độ phân giải tốt nhất. Gần đây Hải Trần [21][22] đưa ra một cách tiếp cận sử dụng Laplacian để tăng cường thông tin cạnh sau đó dò tìm ridge và peak dưới nhiều Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 12 mức khác nhau. Trong hướng tiếp cận này, các đặc trưng ridge và peak được biểu diễn dưới dạng các đồ thị quan hệ hoặc các cây cấp bậc với các tầng là các ridge và peak được dò tìm tại các mức khác nhau. 2.3 Các hướng tiếp cận sử dụng đặc trựng tựa lồi lõm cho phát hiện khuôn mặt Áp dụng đặc trưng tương tự cho bài toán phát hiện khuôn mặt, có hướng tiếp cận của Quan Yuan [28]. Quan Yuan đưa ra một khái niệm mới gọi là đặc trưng tựa thung lũng hay có dạng lõm (valley-like feature). Đặc trưng này dựa trên hiệu mức sáng của các điểm xung quanh và điểm đang xét ở trung tâm để xác định xem điểm này có dạng lõm hay không. Các điểm xung quanh được thiết kế hình dạng khá đặc biệt để phát hiện hai mắt và miệng của khuôn mặt. Mặt dù hướng tiếp cận này khá hấp dẫn, tuy nhiên đặc trưng này quá đặc biệt đối với một số điều kiện thu, chụp ảnh cụ thể. 2.4 Nhận xét về các hướng tiếp cận hiện tại Các hướng tiếp cận trình bày trong phần 2.1 cho thấy khá tổng quát và ổn định, nhưng vẫn còn một vài hạn chế nhất định. Hầu hết các hướng tiếp cận nêu trên sử dụng các đặc trưng chủ yếu dựa trên độ sáng điểm ảnh, với mức độ ý niệm ngữ nghĩa thấp. Vì vậy, các mối quan hệ giữa các đặc trưng rút trích được cần phải thêm vào các luật heuristic để phân tích hiệu quả hơn. Mặt khác, nếu không có các tri thức bổ sung được định nghĩa trước, các mô hình có cấp ý niệm thấp này không thể đạt được độ chính xác cao hơn trong nhận dạng mặt người. Vì thế, để đạt độ chính xác cao hơn trong nhận dạng mặt người, chúng ta cần phải hướng đến một loại đặc trưng dựa trên mô hình ý niệm cao hơn như là cấu trúc của khuôn mặt. Để giải quyết khó khăn nêu trên, trong luận văn này chúng tôi đề xuất một đặc trưng có mô hình ý niệm cao hơn: lồi và lõm tại nhiều mức. Theo cách tiếp cận này, cấu trúc khuôn mặt được biểu diễn bằng một cây cấp bậc của các lồi (chỏm) và lõm (thung lũng). Dựa trên đặc trưng này, chúng tôi áp dụng một mô hình thống kê để xác định, phát hiện khuôn mặt. Trong luận văn này, chúng tôi tập trung chính vào bài Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 13 toán phát hiện khuôn mặt mà không giải quyết bài toán nhận dang. Tuy nhiên, trong phần cuối, chúng tôi sẽ thảo luận chi tiết hơn khả năng sử dụng đặc trưng này để nhận dạng khuôn mặt cũng như việc mở rộng đặc trưng này cho bài toán rộng hơn: phân loại đối tượng dựa theo cấu trúc. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 14 CHƯƠNG 3 ĐẶC TRƯNG LỒI LÕM 3.1 Lồi và Lõm Hiểu theo nghĩa thật sự của nó, lồi (chỏm) là các điểm cao nhất trên dãy núi và lõm (thung lũng) là các điểm có độ cao thấp nhất. Trong ảnh vệ tinh, lồi là đường xương sống của dãy núi, còn lõm là đường khe chạy giữa hai dãy núi. Trong ảnh y tế, lồi có thể là các đường mạch máu hay các cơ quan nhô cao và lõm là các thành phần trũng xuống. Còn trong ảnh khuôn mặt, mũi và các phần nhô của hai má được coi như là lồi và các phần hốc mắt được coi là lõm. Trong [21][22], Hải Trần sử dụng một bộ lọc Laplacian-of-Gaussian, sau đó áp dụng một thuật toán để dò tìm quỹ tích của các điểm cực trị. Hình 3.1 và 3.2 biểu diễn các đặc trưng lồi và lõm tương tự như kết quả của Hải Trần. Các điểm lồi được tô màu đỏ và lõm được tô màu xanh. Chúng ta lưu ý rằng các điểm lồi và lõm rút trích được chỉ biểu diễn được các vùng lồi và lõm nhỏ, chi tiết, chẳng hạn như: mắt, chân mày, mũi, và miệng. (a) Ảnh gốc (b) Ảnh ridge và valley Hình 3.1 Dò tìm thông tin lồi và lõm trên ảnh vệ tinh sử dụng LoG với σ = 2 Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 15 Mục tiêu nghiên cứu của chúng tôi là dò tìm các đặc trưng lồi và lõm tại các mức khác nhau. Ví dụ như, tại mức thấp nhất, chúng tôi cần dò tìm các đặc trưng lồi lõm có kích thước nhỏ và chi tiết như mắt, mũi, v.v... Trong những mức độ cao hơn kế tiếp, chúng tôi sẽ dò tìm các vùng lồi và lõm lớn hơn. Đến mức độ lớn nhất, toàn bộ khuôn mặt có thể trở thành một vùng lồi. Nói cách khác, ở mức lớn sẽ dò được vùng lồi và lõm kích thước lớn và ít chi tiết hơn. Ý tưởng nghiên cứu này đến một cách tự nhiên, cũng giống như khi nhìn một người từ rất xa, ta chỉ có thể nhìn được dáng, gần hơn một tí ta có thể nhìn được mặt nhưng không nhìn được các chi tiết mắt, mũi, miệng trên khuôn mặt, và gần hơn nữa ta mới có thể nhìn chi tiết mắt mũi, miệng. Việc này tương ứng với cách tiếp cận phân tích nhiều mức khác nhau của chúng tôi. Do bộ lọc Laplacian-of-Gaussian chỉ có thể sử dụng để phát hiện thông tin cạnh qua các điểm biên (zero crossing), nên nó không thể dùng cho việc phát hiện các vùng lồi và lõm khi các thông tin cạnh biên bị đứt nét. Trong phần tiếp theo chúng tôi sẽ đề xuất một phương pháp đơn giản để rút trích các vùng lồi và lõm. (a) Ảnh gốc (b) Ảnh ridge và valley Hình 3.2 Dò tìm thông tin lồi và lõm trên ảnh khuôn mặt sử dụng LoG với σ = 2 Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 16 3.2 Rút trích vùng lồi và vùng lõm 3.2.1 Điểm lồi và điểm lõm Gọi ),( yxI là một hàm hai biến biểu diễn một ảnh I. Hàm số này thiết lập một mặt )),(,,( yxIyx . Mục tiêu của chúng ta là dò tìm các điểm có khả năng là điểm lồi hoặc điểm lõm trên mặt này. Một cách chính xác theo toán học, điểm lồi và lõm là những điểm mà tại đó cả hai đạo hàm 2 2 x I ∂ ∂ và 2 2 y I ∂ ∂ đạt cực trị. Trên thực tế, do ảnh là một hàm số không liên tục, hàm rời rạc do sự số hóa của máy tính, vì vậy sẽ rất khắt khe nếu chúng ta chỉ dò tìm các điểm cực trị. Và chúng ta sẽ bị mất một số thông tin của các điểm ảnh lồi và lõm cũng như những điểm lân cận chúng. Chúng tôi đưa ra các công thức sau đây nhằm giảm bớt các điều kiện ràng buộc đối với điểm lồi và điểm lõm: }0),(),(),{( >∧≥= yxLoGyxLoGyxRP δ (3.1) }0),(),(),{( <∧≥= yxLoGyxLoGyxVP δ (3.2) Trong công thức 3.1 và 3.2, RP là tập các điểm lồi và VP là tập các điểm lõm. Ký hiệu ),( yxLoG là giá trị của Laplacian-of-Gaussian tại điểm ),( yx . Như đã trình bày trong phần 3.1, mục đích của chúng tôi là rút trích các vùng lồi và lõm chứ không chỉ rút trích điểm lồi và điểm lõm. Vì thế chúng tôi đã mở rộng công thức 3.1 và 3.2 cho phù hợp với bài toán rút trích vùng. 3.2.2 Dò tìm và rút trích vùng lồi và vùng lõm Để đánh giá một vùng có phải là lồi, là lõm hoặc không lồi cũng không lõm, chúng tôi đề xuất một bộ lọc như sau: Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 17 (a) Vùng đang xét trên ảnh (b) một bộ lọc vuông Hình 3.3 Dò tìm vùng trên ảnh Ứng với vùng đang xét – một hình vuông ss× , chúng ta tính giá trị của bộ lọc trên vùng này theo công thức 3.3. Đạt S1, S2, S3, và S4 là các hình chữ nhật đen xung quanh hình vuông R (Hình 3.3b), giá trị lọc F(R) được định nghĩ như sau: ∑ = −= 4 1 )()(2)( i iSsumRsumRF (3.3) Trong công thức 3.3, hàm sum(X) là hàm tổng giá trị độ sáng trong vùng X. Dựa trên giá trị F(R) vừa tính được, chúng ta đánh giá xem vùng R là lồi hay lõm theo công thức sau: ⎪⎩ ⎪⎨ ⎧ <∧≥⇔ >∧≥⇔ = otherwisenormal RFRFvalley RFRFridge R 0)()( 0)()( δ δ (3.4) Công thức 3.4 là công thức mở rộng của 3.1 và 3.2 nhằm để dò tìm các vùng lồi và lõm trên ảnh. Sự khác biệt chủ yếu ở chổ ta sử dụng bộ lọc hiệu trong 3.4 thay vì sử dụng Laplacian-of-Gaussian trong 3.1 và 3.2. Chúng ta để ý rằng, bằng cách thay kích thước S của vùng đang xét, hay nói cách khác là kích thước của lọc, chúng ta có thể dò tìm các vùng lồi và lõm ứng với nhiều kích cở, mức độ khác nhau. Ngoài ra, để dò tìm và rút trích các vùng lồi lõm có hình dạng khác nhau, chúng tôi sử dụng Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 18 một tập các lọc hình học có hình dạng như trong hình 3.4 thay vì chỉ sử dụng một bộ lọc vuông. (a) Lọc hình vuông (b) Lọc chữ nhật ngang (c) Lọc chữ nhật đúng Hình 3.4 Tập các bộ lọc kích thước S Với sự bổ sung tập bộ lọc như trên, công thức 3.3 được viết lại như sau: ∑ = −= 4 1 )()(2)( i iS SsumRsumRF (3.5) ∑ = −= 4 1 )(2)(3)( i iR SsumRsumRF (3.6) )(RFS được sử dụng để tính gia trị lọc vuông còn )(RFR được sử dụng để tính giá trị các lọc hình chữ nhật. Chúng ta dễ dàng nhận thấy rằng các công thức tính lọc đều tương tự với công thức của một Laplacian, nhưng có một chút khác biệt là sử dụng vùng thay vì từng điểm đơn. Trong công thức 3.5 và 3.6, hệ số đứng trước hàm sum(R) có được là do tỷ lệ giữa diện tích vùng ở tâm (vùng đang xét) và tổng diện tích của vùng lân cận. Trong hình 3.4a, tổng diện tích của các vùng đen xung quanh gấp đôi diện tích phần ở giữa, vì vậy chúng ta có hệ số 2. Trong hình 3.4b và 3.4c, tổng diện tích các vùng đen gấp rưỡi diện tích phần hình chữ nhật ở giữa. Một cách chính xác chúng ta phải dùng hệ số 1.5 trước hàm sum(R), nhưng việc tính toán trên số thực rất chậm, do đó để tăng tốc độ tính toán ta dùng 2 hệ số nguyên là 3 và 2 thay vì chỉ dùng 1 hệ số 1.5. Một thông số quan trọng khác trong công thức 3.4 là ngưỡng δ. Ngưỡng δ phải phụ thuộc tuyến tính vào diện tích của vùng đang xét. Chúng tôi sử dụng Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 19 2 1 KS=δ đối với lọc hình vuông có kích thước S và 22 4KS=δ đối với các lọc hình chữ nhật có kích thước S. K là một thông số thực nghiệm. Ngưỡng δ1 là tích của K và S2 – diện tích của lọc vuông. Tương tự, trong 3.6, chúng ta đã gấp đôi giá trị của FR(R) để tránh chuyện tính toán trên số thực. Vì thế, chúng ta cũng phải gấp đôi ngưỡng δ2 để tăng độ chính xác của việc đánh giá. 3.2.3 Dò tìm và phát hiện vùng lồi, lõm ở nhiều mức Chúng tôi giới thiệu một phương pháp sử dụng các lọc hiệu ở nhiều mức khác nhau để dò tìm các vùng lồi và lõm. Các lọc được giới thiệu trong phần trước sẽ được sử dụng với nhiều kích thước khác nhau vì vậy chúng sẽ dò tìm được các vùng lồi lõm ở nhiều mức khác nhau. (a) σ = 10, ảnh sau khi smoth bằng Gaussian 210 (b) Các vùng lồi lõm dò tìm với lọc kích thước 10 Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 20 (c) σ = 20, ảnh sau khi smoth bằng Gaussian 220 (d) Các vùng lồi lõm dò tìm với lọc kích thước 20 (e) σ = 60, ảnh sau khi smoth bằng Gaussian 260 (f) Các vùng lồi lõm dò tìm với lọc kích thước 60 Hình 3.5 Dòm tìm vùng lồi lõm ở nhiều mức khác nhau Đặt 1σ , 2σ ,.. nσ là các mức độ được định nghĩa trước và có độ lớn tăng dần. 1σ là mức độ thấp nhất. Tại mức độ này, chúng ta có thể dò tìm các vùng lồi, lõm có kích thước nhỏ và chi tiết. nσ là mức độ cao nhất mà tại đó chúng ta có thể dò tìm các vùng lồi lõm lớn hơn, ít chi tiết hơn. Tại mỗi mức, trước tiên chúng ta áp dụng một lọc Gaussian với kích thước 2iσ , sau đó chúng ta sử dụng 3 bộ lọc hiệu như hình 3.4 với kích thước S = iσ . Trong hình 3.5, các hình vuông và hình chữ nhật màu đỏ là các vùng lồi, còn các hình vuông và hình chữ nhật màu xanh là các vùng lõm. Trong thực tế, có nhiều vùng lồi lõm khác cũng được dò tìm được, tuy nhiên trong hình 3.5, chúng tôi chỉ tập trung vào các vùng lồi lõm dò tìm được trong vùng ảnh quan tâm – vùng ảnh khuôn mặt. Trong phần 3.3, chúng tôi sẽ trình bày phương pháp cấu trúc các vùng lồi lõm rút trích được này thành các cây cấp bậc. Trong phần tiếp theo, chúng tôi sẽ trình bày ngắn gọn thuật toán của chúng tôi nhằm tối ưu những hàm tính toán phức tạp sử dụng trong việc tính các giá trị lọc trong hình 3.4. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 21 3.2.4 Tối ưu tốc độ của việc dò tìm Trong vùng đang xét, chúng ta phải thường xuyên tính tổng độ sáng điểm ảnh của một vùng hình chữ nhật, một số hình trong chúng có thể chồng lên nhau. Việc này làm cho tính toán chậm đi rất nhiều do phải tính nhiều lần tổng độ sáng cho một vùng. Để giảm độ phức tạp của tính toán này, chúng tôi sử dụng phương pháp tương tự như ảnh tích phân (integral image) của P. Viola [5] và kỹ thuật lập trình quy hoạch động của Đức Dương [31]. Phương pháp này được trình bày như sau: Cho trước một ảnh mức xám ),( yxI , chúng ta định nghĩa một ảnh tích phân ),( yxS sao cho ),( yxS là tổng mức sáng của toàn bộ điểm ảnh trong hình chữ nhật ),,1,1( yxR . Chúng ta có thể dễ dàng tính được ),( yxS theo công thức truy hồi 3.7: ⎩⎨ ⎧ ≠∧≠+−−−−+− =∨== 00),()1,1()1,(),1( 000 ),( yxyxIyxSyxSyxS yx yxS (3.7) Hình 3.6 Ảnh tích phân Từ ảnh ),( yxS , ta dễ dáng tính được tổng độ sáng của một hình chữ nhật bất kỳ ),,,( btrlR theo công thức 3.8 sau: ),(),(),(),( tlSblStrSbrSSR +−−= (3.8) S(i,j) = [1..i]x[1..j] (i,j) (1,1) Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 22 Hình 3.7 Tính tổng độ sáng cho hình chữ nhật R(l,t,r,b) Phương pháp này cải tiến đáng kể tốc độ tính toán bởi vì chúng ta chỉ cần tính một lần ảnh tích phân và sử dụng nó trong tất cả các cửa sổ hình chữ nhật con và đặc biệt độ phức tạp tính toán không phụ thuộc vào kích thước của vùng đang xét. 3.3 Xây dựng cây cấu trúc lồi lõm Từ các vùng lồi lõm rút trích được, chúng ta xây dựng các cây quan hệ cấp bậc. Những vùng được rút trích ở mức cao nhất nσ sẽ trở thành những nút gốc của các cây sẽ tạo. Những vùng rút trích được ở mức thấp nhất 1σ sẽ được chèn vào cây như là những nút lá (xem hình 3.8) Hình 3.8 Tạo cây cấp bậc Công việc chính của việc tạo cây là kết nối các vùng rút trích được tại một mức đến các vùng của mức kế tiếp. Nếu vùng R tại mức iσ bị che khuất hơn hai phần l r t b (1,1) (W,H) Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 23 ba diện tích của nó bởi vùng R’ của mức 1+iσ , R sẽ được gán nhãn là nút con của R’. Bằng cách này chúng ta có thể dễ dàng tạo cây cấp bậc từ các vùng đã rút trích được. Các vùng rút trích được trong hình 3.5 được xây dựng thành cây như sau (xem hình 3.9) Hình 3.9 Một ví dụ về cây rút trích từ khuôn mặt Đối với mỗi nút trong cây, chúng ta cần lưu các thông tin của nút này như: loại (lồi hay lõm), hình dạng (vuông, chữ nhật ngang, chữ nhật đứng), vị trí tương đối của nó so với nút cha của nó (có giá trị từ 0 đến 12, xem hình 3.10), và thông tin về độ sáng của nó. Hình 3.10 Vị trí vùng tương đối của nút con Trong hình 3.10 biểu diễn các vị trí tương đối của nút con trên nút cha lần lượt có dạng vuông, chữ nhật ngang, và chữ nhật đứng. Việc xét một nút con có vị trí 1 2 4 3 1 2 4 3 5 6 7 8 1 2 4 3 9 10 12 11 Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 24 tương đối như thế nào đối với nút cha khá đơn giản. Nếu tâm của nút con (tâm của hình vuông hay hình chữ nhật) rơi vào vùng nào trong hình 3.10 thì chỉ số của vùng đó chính là giá trị vị trí tương đối của nút con trong nút cha. Lưu ý rằng đối với các nút gốc giá trị này sẽ là 0. Bên cạnh đó thông tin về độ sáng cũng rất quan trọng trong các bài toán phát hiện và nhận dang khuôn mặt về sau. Để lưu trữ thông tin này trên cây chúng tôi sử dụng phương pháp phân tích thành phần chính (Principal Component Analysis – PCA) để giảm số chiều của ảnh mức xám trên vùng ảnh của nút đó. Bằng cách này ta giảm được đáng kể thông tin phải lưu trữ về độ sáng của ảnh. Thay vì phải lưu trữ toàn bộ điểm sáng của các vùng lồi lõm (các nút), chúng ta chỉ cần lưu một vector PCA chứa nội dung của các điểm sáng này. Cách này giúp cho giảm thông tin phải lưu trữ, xử lý mà cũng không mất mát quá nhiều thông tin (Xem hình 3.11). Hình 3.11 Cách tính vector đại điện độ sáng cho nút Cụ thể ta thực hiện như sau: dùng một cửa sổ con S kích thước 9x9 quét theo đường zic-zac trên ảnh xám của vùng lồi lõm. Các cửa cổ này có thể chồng lắp lên nhau hai phần ba kích thước của nó. Tại mỗi điểm, ta lưu lại trung bình mức sáng của các điểm ảnh trong cửa sổ S. Như vậy ta lưu được một vector tương ứng cho biểu diễn mức sáng của điểm ảnh tại nút đó. 9 9 S Các khả năng chồng lắp cửa sổ Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 25 Vị trí của nút gốc trên ảnh Nội dung của nút được phóng ra: 1. Kiểu: lõm 2. Hình: vuông 3. Vị trí: 1 4. = (a1, a2,...,an) Hình 3.12 Ví dụ về cây rút trích được và các thông tin trên một nút Bên cạnh đó, chúng tôi sử dụng một số luật để tỉa bớt nhánh cho các cây. Nếu một nút cùng kiểu (lồi hay lõm) so với nút cha của nó thì nó được xem là một nút lập. Trong trường hợp này, nút lập sẽ được tỉa khỏi cây. Nếu nó là một nút lá, chúng ta dễ dàng xóa nó khỏi cây. Ngược lại, nếu nó không phải là nút lá, tất cả các nút con của nó sẽ được gán trở thành con của nút cha nó. Hình 3.5 và 3.9 cho ta một ví dụ về trường hợp này: chúng ta có hai vùng lồi hình chữ nhật đứng ở mức σ2 và σ3. Hai vùng này thật sự chỉ là một. Trong thực thế, do hiệu ứng của phép lọc Gaussian tại các mức khác nhau, chúng được rút trích ra từ ảnh với các kích thước khác nhau vì thế vùng lồi ở mức σ3 đã được xóa khỏi cây trong hình 3.9. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 26 3.4 Xây dựng hàm tính độ tương đồng giữa hai cây Trong phần này chúng tôi xin đề xuất một cách tính độ tương đồng giữa hai cây lồi lõm theo cách biểu diễn như phần trước. Việc xây dựng hàm tương đồng giữa hai cây là rất cần thiết trong tất cả các xử lý liên quan đến đặc trưng này. Nó có tính chất quyết định ảnh hưởng đến độ chính xác của phát hiện và nhận dạng khuôn mặt. 3.4.1 Độ tương đồng giữa hai nút trên cây Để xây dựng hàm tính độ tương đồng giữa hai cây trước hết ta cần xây dựng hàm tính độ tương đồng của hai nút trên hai cây. Với điều kiện rằng hai nút thuộc hai cây khác nhau này cùng mức σi nào đó. Đặt N1 và N2 là hai nút cùng cấp trên hai cây T1 và T2. Khi đó N1 và N2 có những thuộc tính sau: N1, N2 ∈ Node = {(t,s,p,i)} (3.9) Trong đó: t ∈{ridge, valley} : là loại của nút (lồi hay lõm). s = {square, horizontal rectangle, vertical rectangle} là hình dạng của nút (vuông, hình chữ nhật ngang, hình chữ nhật đứng). p ∈ [0..12] : là vị trí tương đối của nút trong nút cha của nó. i ∈ (a1,a2,...,an) : là vector chứa thông tin độ sáng của nút. Trong đó n thay đổi tùy theo cấp của nút. Ở mức σi càng cao, kích thước của vùng lồi lõm tương ứng với nút càng lớn, số chiều n của vector này càng cao. Dựa trên các thuộc tính của node định nghĩa trong công thức 3.9, ta xây dựng công thức tính độ tương đồng giữa 2 nút như sau: ).,.()1().,.().,.().,.(),( 2111121121121121 iNiNEVpNpNEsNsNEtNtNENNNS γβαγβα −−−+++= (3.10) Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 27 Trong công thức 3.10, α1, β1, và γ1 là các thông số thực ngiệm, hàm E(x,y) dùng để xét sự giống nhau giữa 2 thuộc tính được định nghĩa như sau: ⎩⎨ ⎧ ≠ == yx yx yxE 0 1 ),( (3.11) Bên cạnh đó ký hiệu EV(x,y) là hàm tính độ tương đồng giữa 2 vector được chuẩn hóa về đoạn [0,1]. Trong đó x và y là hai vector độ sáng có n chiều (a1,a2,...an). n ayax yxEV n i ii 255 )..( 1),( 1 2∑ = − −= (3.12) Do mỗi thành phần ai trong vector độ sáng có giá trị là độ sáng (ai ∈[0,255]) nên dễ dàng chứng minh được EV(x,y) ∈[0,1]. EV(x,y) đạt giá trị lớn nhất là 1 khi hai vector x và y trùng nhau. Và EV(x,y) đạt giá trị nhỏ nhất là 0 khi hai vector có khoảng cách Euclid xa nhau nhất. Và từ đó ta cũng dễ dàng suy ra được giá trị của ]1,0[),( 21 ∈NNNS với mọi cặp nút N1 và N2. 3.4.2 Độ tương đồng giữa hai cây Trên cơ sở hàm tính độ tương đồng giữa hai nút, ta xây dựng lên hàm tính độ tương đồng giữa hai cây. Gọi T1 và T2 và hai cây đang cần tính độ tương đồng. T1 và T2 có những thuộc tính sau: )},...,,,,{(, 2121 ncccnrTreeTT =∈ (3.13) Trong đó: r : là nút gốc của cây r ∈ Node. n : là số nhánh con của cây n ∈ N. ci : là cây (nhánh) con thứ i của cây ci ∈ Tree và i ∈ [1..n]. ci có thể là một nút là hoặc cũng có thể là một cây khác. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 28 Từ công thức 3.13, ta xây dựng công thức tính độ tương đồng của 2 cây như sau: nnTT cTcTTS rTrTNSTTTS nT i nT j ji .. ).,.( )1().,.(),( 21 . 1 . 1 21 221221 1 2∑∑ = =−+= αα (3.14) Trong đó α2 là thông số thực nghiệm. Các thông số thực nghiệm α1, β1, và γ1 trong công thức 3.10 và α2 trong 3.14 sẽ được thảo luận chi tiết trong phần thực nghiệm nhằm chọn thông số thực nghiệm tốt nhất. Theo công thức 3.14 ta cũng dễ dàng nhận thấy ]1,0[),( 21 ∈TTTS với mọi cặp cây T1 và T2. Giá trị của hàm này càng lớn, hai cây này càng giống nhau càng nhiều hơn. Ngoài ra, trong phần thử nghiệm chúng tôi có thử nghiệm đặc trưng lồi lõm mà không sử dụng đến thông tin độ sáng. Khi đó công thức 3.10 tính độ tương đồng giữa hai nút được đơn giản hóa như sau: ).,.()1().,.().,.(),( 211121121121 pNpNEsNsNEtNtNENNNS βαβα −−++= (3.15) 3.4.3 Không gian cây và khoảng cách giữa hai cây Trong một số trường hợp, hàm tính độ tương đồng giữa hai cây không đủ để tính toán trong một số trường hợp. Để đưa về bài toán không gian, ta xây dựng một “không gian cây” (tree-space), không gian này sẽ là cơ sở để cho các bài toán phát hiện và nhận dạng khuôn mặt về sau. Trong không gian cây này, mỗi cây được xem là một điểm trong không gian. Trên cơ sở đó ta xây dựng hàm tính khoảng cách giữa hai cây như sau: ),(1, 2121 TTTSTT −= (3.16) Dễ dàng nhận thấy, khoảng cách giữa hai cây là một giá trị thuộc đoạn [0,1]. Và khoảng cách tiến dần về bằng không khi hai cây càng giống nhau. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 29 Trên cở sở các công thức tính độ tương đồng, khoảng cách này, chúng tôi xây dựng một mô hình thống kê để dò tìm và phát hiện khuôn mặt. Mô hình có thể dùng cho nhận dạng khuôn mặt cũng như mở rộng cho bài toán phân loại đối tượng. Phần mô hình này sẽ được trình bày trong chương sau. Các phần thảo luận về khả năng mở rộng của mô hình này cho bài toán nhận dạng khuôn mặt và phân loại đối tượng sẽ được trình bài trong chương kết luận và hướng phát triển. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 30 CHƯƠNG 4 PHÁT HIỆN KHUÔN MẶT DỰA TRÊN ĐẶC TRƯNG LỒI LÕM 4.1 Tập mẫu học Trong luận văn này chúng tôi thử nghiệm trên tập dữ liệu ảnh thu thập bởi Markus Weber [32]. Đây là tập dữ liệu chụp các khuôn mặt thẳng, chụp dưới nền phức tạp và đa dạng gồm cả trong nhà và ngoài trời. Điều kiện chiếu sáng khá đa dạng gồm cả các ảnh chụp cùng chiều chiếu sáng và ngược sáng. Ngoài ra còn có các ảnh chụp phức tạp do một phần của khuôn mặt bị che khuất. Ngoài ra, tập ảnh này còn chứa cả ảnh chụp lại từ tranh họa mặt người. (a) Ảnh chụp trong nhà (b) Ảnh chụp ngoài trời (c) Ảnh chụp ngược sáng (d) Ảnh chụp phức tạp do che kuất Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 31 (e) Ảnh chụp phức tạp do biểu cảm (f) Ảnh chụp từ tranh họa Hình 4.1 Một số ảnh trong tập ảnh Weber Trong tập ảnh này có tất cả 450 ảnh. Chúng tôi sử dụng 200 ảnh để học và 250 ảnh còn lại để kiểm thử. 4.2 Mô hình thống kê 4.2.1 Gán nhãn Từ tập ảnh học, chúng tôi dùng phương pháp trình bày trong chương 3 để rút trích các cây lồi lõm trên ảnh. Các cây này được gán nhãn thủ công. Mỗi cây bất kỳ được gán nhãn là mặt (face) hay không phải khuôn mặt (non-face). Như vậy, từ một tập ảnh học ta rút trích được hai tập cây. Tập cây biểu diễn khuôn mặt và tập cây biểu diễn đối tượng không phải là khuôn mặt. Hình 4.2 Mô hình gán nhãn cho tập học Gán nhãn Rút trích câyTập ảnh học Face Non-face Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 32 4.2.2 Thống kê Mục đích của bước này là xấp xĩ được một cấu trúc cây khuôn mặt. Trong bước gán nhãn, chúng tôi tiến hành rút trích cây và gán nhãn. Kết quả thu được 2036 cây thuộc lớp “khuôn mặt”. Các cây này được dùng làm dữ liệu học thống kê. Mô hình thống kê chúng tôi sử dụng như sau: Đặt S(Tx) là tổng khoảng cách của một cây Tx bất kỳ đến tất cả các cây còn lại trong tập học. ∑≠∧= = = xini i ixx TTTSTS 1 ),()( (4.1) Ta có tập học sẽ trở thành: })),(,{( FaceSetTTSTTraining iii ∈∀= (4.2) Trong đó FaceSet là tập các cây được gán nhãn là “khuôn mặt”. Việc học thống kê theo mô hình của chúng tôi khá đơn giản. Trước tiên, chọn trong tập Training ra k cây có giá trị S(T) bé nhất. k cây này sẽ là đại diện tiêu biểu cho một lớp khuôn mặt. Từ kết quả k cây rút trích được, tạm gọi là tập cây chuẩn, chúng ta có thể dùng chúng để phát hiện khuôn mặt theo mô hình như sau: Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 33 Hình 4.3 Mô hìn phát hiện khuôn mặt Trong mô hình này, trước tiên từ ảnh đầu vào ta dùng phương pháp rút trích lồi lõm ta sẽ nhận được một danh sách các cây lồi lõm. Ứng với mỗi cây ta dựa vào tập cây chuẩn để kiểm tra xem liệu đây có phải là cây biểu diễn “khuôn mặt” hay không. Nếu thỏa điều kiện đánh giá nó sẽ trở thành ứng viên khuôn mặt. Trong bước cuồi cùng, hậu xử lý, các ứng viên sẽ được kiểm tra ràng buộc. Và sau cùng là khử trùng lắp khuôn mặt do có một số cây có một phần của nút gốc chồng lên nhau. 4.2.3 Đánh giá dùng cho phát hiện khuôn mặt Dựa trên tập cây chuẩn, một cây bất kỳ được đánh giá có khả năng là khuôn mặt hay không dựa trên trung bình khoảng cách của cây đang xét đến tất cả các cây trong tập cây chuẩn. k Tt tD k i i∑ == 1 , )( (4.3) Trong đó: )(tD : là trung bình khoảng cách của cây t đến các cây trong tập chuẩn t: là cây đang xét Ti: là các cây trong tập k cây chuẩn Đánh giá cây Ảnh input Tập cây chuẩn ứng viên Hậu xử lý Các vị trí khuôn mặt Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 34 Căn cứ vào giá trị D , cây t được đánh giá là ứng viên mặt hay không dựa theo công thức sau: 1)( δ≤⇔∈ tDateFaceCandidt (4.4) Ngưỡng δ1 là ngưỡng thực nghiệm, ngưỡng này sẽ được lấy khoảng 0.2 đến 0.4. Ngoài cách tính trung bình khoảng cách, ta có thể đánh giá ứng viên thông qua việc tính trung bình độ tương đồng của cây ứng viên với tập cây chuẩn. k TtTS tS k i i∑ == 1 ),( )( (4.5) Trong đó: )(tS : là trung bình độ tương đồng của cây t so với các cây trong tập chuẩn t: là cây đang xét Ti: là các cây trong tập k cây chuẩn Tương tự như trường hợp trên, giá trị )(tS sẽ được dùng để đánh xem cây t có khả năng là khuôn mặt hay không. 2)( δ≥⇔∈ tSateFaceCandidt (4.6) Dễ thấy ngưỡng δ2 là số gần với một, có thể nói δ2≅1-δ1. Ngưỡng này sẽ được lấy trong khoảnh từ 0.6 đến 0.8. Tuy nhiên, về bản chất hai cách này hoàn toàn giống nhau. 4.2.4 Hậu xử lý Các kết quả thu được cho thấy rằng có một vùng khuôn mặt được phát hiện có một phần chồng lắp lên nhau. Có thể phát hiện ra nhiều cây ứng viên được đánh giá là “khuôn mặt”, nhưng thật sự chúng là sự chồng lắp của nhiều cây lên một vị trí Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 35 khuôn mặt. Vì vậy, chúng ta cần một thuật toán tốt để giảm những phát hiện các ứng viên trùng này. Trước hết chúng tôi sử dụng một đánh giá đơn giản để liên kết các vùng trùng lấp. Nếu hai ứng viên khuôn mặt có vùng diện tích bị chồng lắp lên nhau quá một phần ba diện tích của nó, chúng được xem là các mặt trùng và được liên kết lại thành một vùng lớn hơn. Vùng điện tích xem xét đó chính là vùng diện tích của nút gốc của cây ứng viên. (a) các vùng khuôn mặt chồng lấp (b) sau khi gom vùng Hình 4.4 Một ví dụ về giảm trùng lắp Sau khi gom nhóm được vùng, chúng tôi thu được một hay nhiều vùng chứa khuôn mặt. Tuy nhiên, do sai số của kích thước của cây và kích thước khuôn mặt, nên chúng tôi luôn có được vùng khuôn mặt phát hiện được lớn hơn khuôn mặt thực tế. Chúng tôi áp dụng tiếp kỹ thuật xác định vùng lồi lõm với mức nhỏ hơn nhằm để phát hiện chính xác vùng. Chúng tôi chỉ áp dụng thuật toán dò tìm đặc trưng lồi lõm trên vùng bao khuôn mặt, sau đó liên kết các vùng lồi lõm cùng loại lại với nhau. Vùng khuôn mặt thật sự sẽ là vùng liên thông lớn nhất trong đó. Với cách như vậy, chúng ta sẽ thu nhỏ, và xác định chính xác hơn vị trí khuôn mặt. Hình 4.5 hậu xử lý 4.3 Cơ sở lý thuyết của mô hình Như đã trình bày trong phần 3.4.3 ở chương 3, mỗi cây có thể được xem là một điểm trong không gian cây, trong đó mỗi cây chứa cấu trúc lồi lõm của các đối Miền liên thông lớn nhất cùng kiểu với các nút gốc của cây Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 36 tượng quan tâm. Trong bài toán này ta quan tâm đến các cây biểu diễn câu trúc khuôn mặt. Từ tập học, gồm các cây được đánh nhãn “khuôn mặt”, ta có thể biểu diễn nó trong một không gian hữu hạn chiều, là các điểm (xem hình 4.6). Hình 4.6 Các cây khuôn mặt trong không gian cây Trong hình trên, các điểm tương ứng với các cây được gán nhãn “khuôn mặt” trong tập học. Việc chọn ra k cây cho tập chuẩn có thể hiểu theo nghĩa là ta chọn k điểm đại diện. k điểm này nằm ngay trung tâm của lớp khuôn mặt (xem hình 4.7). Phương pháp gần giống với phương pháp k người láng giềng gần nhất nhưng có thay đổi cho phù hợp với bài toán phân lớp này nhằm tối ưu tốc độ. Hình 4.7 Chọn k cây chuẩn theo tiêu chí trọng tâm Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 37 Vấn đề ở đây là xác định số k hợp lý để sao cho k cây trung tâm đó đủ tổng quát để đại diện cho cấu trúc khuôn mặt. Sau đó, trên cơ sở tập cây mẫu này, một cây mới được so sánh và tính trung bình khoảng cách đến tất cả các cây trong tập mẫu. Hình 4.7 Đánh giá điểm thuộc lớp “khuôn mặt” hay không Như vậy, xét về mặt toán học đây việc tính khoảng cách trung bình từ điểm đang xét so với điểm chuẩn tương ứng với việc xét vị trí tương đối của nó so với cả nhóm điểm chuẩn. Nếu điểm nằm hoàn toàn bên trong cụm, chắc chắc khoảng cách trung bình sẽ rất nhỏ và sẽ được xếp vào lớp “khuôn mặt”. Ngược lại, nếu điểm đang xét nằm bên ngoài cụm, khoảng cách trung bình sẽ tăng lên và khả năng được xếp vào lớp “khuôn mặt” là rất thấp. Mô hình thống kê này cũng phù hợp cho bài toán phân loại đối tượng cho thị giác robot. Phù hợp với cách học thích ứng, cho các đối tượng được học trước và cho cả đối tượng chưa biết được học tăng cường trong quá trình sống của robot. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 38 CHƯƠNG 5 THỬ NGHIỆM VÀ KẾT QUẢ 5.1 Thử nghiệm Chương trình được cài đặt trên môi trường lập trình Microsoft Visual C++ 6.0. Sử dụng thư viện mã nguồn mở OpenCV [33] và thư viện xử lý ảnh của Intel [34] (Intel Image Processing Library). Máy tính sử dụng có cấu hình Petium IV 1.4 GHz, bộ nhớ 512MB, hệ điều hành Microsoft Windows XP Professional. Tập ảnh sử dụng là tập ảnh chụp khuôn mặt thẳng của Markus Weber [32]. Toàn bộ tập dữ liệu có tổng cộng 450 ảnh. 200 được sử dụng để huấn luyện và 250 ảnh còn lại dùng để kiểm thử. Tập ảnh Huấn luyện Kiểm thử 450 200 250 Bảng 5.1 Phân chia ảnh trong tập ảnh 5.2 Kết quả Chúng tôi thử nghiệm trên hai cách chọn đặc trưng lồi lõm. Cách thứ nhất dùng đặc trưng lồi lõm không dùng kèm đặc trưng độ sáng. Và cách thứ hai, dùng đặc trưng lồi lõm kèm theo đặc trưng độ sáng. Trong hai thử ngiệm này, hai thuật toán hoàn toàn giống nhau. Điểm khác nhau duy nhất là hàm tính độ tương đồng giữa hai nút. Thử nghiệm 1 sử dụng hàm tính độ tương đồng định nghĩa ở công thức 3.15. Còn trong thử nghiệm 2 sử dụng hàm tính độ tương đồng giữa hai nút theo công thức 3.10. Các thử nghiệm dưới đây chỉ rút trích đặc trưng lồi lõm 2 cấp: σ1 = 20 và σ2 = 120. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 39 Kết quả kiểm thử được trình bày trong bảng sau: Thử nghiệm Số ảnh Đúng Sai Tỷ lệ sai Độ chính xác Thời gian 1 250 182 68 27.2% 72.8% 0.6s 2 250 203 47 18.8% 81.2% 0.6s Bảng 5.2 Kết quả thử nghiệm đặc trưng 2 mức Chúng tôi thực hiện tiếp cùng hai thử nghiệm tương tự như trên với các đặc trưng lồi lõm với 3 mức σ1 = 20 , σ2 = 60, và σ3 = 120. Kết quả thu được được trình bày dưới bảng sau: Thử nghiệm Số ảnh Đúng Sai Tỷ lệ sai Độ chính xác Thời gian 1 250 197 53 21.2% 78.8% 0.8s 2 250 224 26 10.4% 89.6% 0.8s Bảng 5.3 Kết quả thử nghiệm đặc trưng 3 mức Ngoài ra, chương trình còn được thử nghiệm trên tập dữ liệu không phải là khuôn mặt, tập dữ liệu loại đối tượng [35]. Tập dữ liệu này gồm các hình ảnh nhà, xe gắn máy, và máy bay. Mỗi loại được kiểm thử trên 112 ảnh. Loại đối tượng Số ảnh Không phát hiện Phát hiện khuôn mặt Tỷ lệ sai Độ chính xác Thời gian Nhà 120 115 5 4.17% 95.83% 0.8s Xe gắn máy 112 111 1 0.9% 99.1% 0.8s Máy bay 115 114 1 0.87% 99.13% 0.8s Bảng 5.4 Kết quả thử nghiệm trên ảnh không chứa khuôn mặt 5.3 Nhận xét Các kết quả cho thấy việc sử dụng đặc trưng cùng với thông tin về độ sáng sẽ cho kết quả tốt hơn. Và việc xây dựng các cây 3 lớp sẽ tăng độ chính xác đang kể so với việc chỉ rút trích đặc trưng cây 2 lớp. Tuy nhiên việc rút trích đặc trưng nhiều lớp làm cho quá trình xử lý tính toán chậm chạp hơn. Phần 5.4 sẽ giới thiệu một số kết quả tiêu biểu của thuật toán. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 40 5.4 Một số kết quả tiêu biểu (a) Ảnh nguồn (b) Ảnh kết quả (c) Gaussian σ = 220 (d) Các vùng lồi lõm ở mức 20 (e) Gaussian σ = 260 (f) Các vùng lồi lõm ở mức 60 (g) Gaussian σ = 2120 (h) Các vùng lồi lõm ở mức 120 Hình 5.1 Một trường hợp đúng Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 41 (a) Ảnh nguồn (b) Ảnh kết quả (c) Gaussian σ = 220 (d) Các vùng lồi lõm ở mức 20 (e) Gaussian σ = 260 (f) Các vùng lồi lõm ở mức 60 (g) Gaussian σ = 2120 (h) Các vùng lồi lõm ở mức 120 Hình 5.2 Một trường hợp phát hiện sai Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 42 Hình 5.3 (a) ảnh khuôn mặt trên nền phức tạp Hình 5.3 (b) ảnh khuôn mặt ngạc nhiên Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 43 Hình 5.3 (c) ảnh khuôn mặt có râu Hình 5.3 (d) ảnh khuôn mặt bị quay 180o Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 44 Hình 5.3 (e) không phát hiện được khuôn mặt nào trong ảnh chụp nhà lấy từ tập [35] Hình 5.3 (f) không phát hiện được khuôn mặt nào trong ảnh chụp máy bay lấy từ tập [35] Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 45 Hình 5.3 (g) không phát hiện được khuôn mặt nào trong ảnh chụp xe gắn máy lấy từ tập [35] Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 46 CHƯƠNG 6 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 6.1 Kết luận Kết quả kiểm thử trên tập dữ liệu ảnh của Weber [32] cho thấy kết quả đạt được tương đối chấp nhận được cho bài toán phát hiện khuôn mặt. Việc áp dụng cây cấp bậc cùng với quan hệ của các đặc trưng lồi lõm ở nhiều mức cho thấy khá phù hợp cho việc phân tích cấu trúc đối tượng nói chung và phân tích cấu trúc khuôn mặt nói riêng. Qua luận văn này, chúng tôi đã đóng góp được một hướng tiếp cận mới cho bài toán phát hiện khuôn mặt. Liên quan đến luận văn này chúng tôi đã có một bài báo được nhận đăng tại hội nghị IEEE ICCS-RIVF06 (xin vui lòng xem phần danh mục công trình của tác giả). Bên cạnh đó, hứa hẹn việc mở ra một loại đặc trưng mới có thể phát triển cho phân loại đối tượng, phát hiện đối tượng tổng quát. Trở lại bài toán về khuôn mặt, chúng tôi cũng nhận thấy rằng việc sử dụng duy nhất đặc trưng lồi lõm thì chưa đủ hiệu quả cho bài toán nhận dạng mặt người (face identification). Chúng tôi đề xuất việc sử dụng thêm một số đặc trưng phụ trợ khác như: độ sáng, quan hệ hình học, khoảng cách giữa các vùng lồi lõm cùng mức. 6.2 Hướng phát triển Hướng tới một mô hình tổng quát và ổn định hơn, chúng tôi đang thử nghiệm việc tìm kiếm một mô hình máy học phù hợp hơn cho cấu trúc cây. Bên cạnh đó chúng tôi đang mở rộng tập các bộ lọc (Hình 3.4, chương 3) thành tập nhiều lọc hơn với các dạng hình học khác nhau, với nhiều góc nghiên khác nhau: 300, 450, 600, -300, -450, -600. Với việc học và rút trích đặc trưng tự động, và Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 47 cấu trúc hình học đa dạng hơn của các bộ lọc, chúng tôi tin rằng mô hình này có thể mở rộng để áp dụng cho bài toán phát hiện và nhận dạng đối tượng tổng quát hơn. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 48 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ [1]. Tran Le Hong Du, Duong Anh Duc, Duong Nguyen Vu, “Ridge and Valley based Face Detection”, IEEE International Conference on Computer Sciences – Research, Innovation, Vision for the Future (RIVF’06), Ho-Chi-Minh city, Vietnam (accepted). [2]. Tran Le Hong Du, Duong Anh Duc, Duong Nguyen Vu, “Ridge and Valley Features for Face Analysis”, International Conference on Computer Vision Theory and Applications (VISAPP’06), Setúbal, Portugal, (in review). Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 49 TÀI LIỆU THAM KHẢO [1]. Ming-Hsuan Yang, David J. Kriegman, Narendra Ahuja, “Detecting Faces in Images: A Survey”, IEEE Transaction on Pattern Analysis and Machine Intelligence (PAMI), Vol. 24, No 1, pp. 34-47, Jan 2002. [2]. Stan Z. Li, Zhen Qiu Zhang, “FloatBoost Learning and Statistical Face Detection”, IEEE Transaction on Pattern Analysis and Machine Intelligence (PAMI), Vol. 26, No, pp. 1-12, Sep 2004. [3]. Stan Z. Li, Juwei Lu, “Face Detection, Alignment and Recognition”, Book Chapter 9, pp. 385-455, Emerging Topics in Computer Vision, Prentice Hall, ISBN 0-13-101366-1, Jul 2004. [4]. P. Viola, M. Jones, “Robust Real Time Object Detection”, Proc. IEEE ICCV Workshop on Statistical and Computational Theories of Vision, Jul 2001. [5]. P. Viola, M. Jones, “Rapid object detection using a boosted cascade of simple features”, Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR’01), pp. 511-518, Dec 2001. [6]. K. K. Sung, T. Poggio, “Example-based learning for view-based human face detection”, IEEE Transaction on Pattern Analysis and Machine Intelligence (PAMI), Vol. 20, No. 1, pp. 39-51, Jan 1998. [7]. H. Rowley, S. Baluja, T. Kanade, “Neural network-based face detection”, IEEE Transaction on Pattern Analysis and Machine Intelligence (PAMI), Vol. 20, No. 1, pp. 23-38, Jan 1998. [8]. H. Schneiderman, T. Kanade, “Probabilistic Modeling of Local Appearance and Spatial Relationships for Object Detection”, Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR’98), pp. 45-51, 1998. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 50 [9]. A. Rajagopalan, K. Kumar, J. Karlekar, R. Manivasakan, M. Patil, U. Desai, P. Poonacha, S. Chaudhuri, “Finding Faces in Photographs”, Proc. 6th IEEE Conf. Computer Vision (ICCV’98), pp. 640-645, 1998. [10]. E. Osuna, R. Freund, F. Girosi, “Training Support Vector Machines: An Application to Face Detection”, Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR’97), pp. 130-136, 1997. [11]. G. Yang, T. S. Huang, “Human Face Detection in Complex Background”, Pattern Recognition, Vol. 27, No. 1, pp. 53-63, 1994. [12]. K. C. Yow, R. Cipolla, “Feature-Based Human Face Detection”, Image and Vision Computing, Vol. 15, No. 9, pp. 713-735, 1997. [13]. T. K. Leung, M.C. Burl, P. Perona, “Finding Faces in Cluttered Scenes Using Random Labeled Graph Matching”, Proc. 5th IEEE Conf. Computer Vision (ICCV’95), pp. 637-644, 1995. [14]. C. Kotropoulos, I. Pitas, “Rule-based Face Detection in Frontal Views”, Proc. Int’l Conf. Acoustics, Speech and Signal Processing, Vol. 4, pp. 2637- 2540, 1997. [15]. A. Lanitis, C. J. Taylor, T. F. Cootes, “An Automatic Face Identification System Using Flexible Appearance Models”, Image and Vision Computing, Vol. 13, No. 5, pp. 393-401, 1995. [16]. M. Turk, A. Pentland, “Eigenfaces for Recognition”, Journal of Cognitive Neuroscience, Vol. 3, No. 1, pp. 71-86, 1991. [17]. I. Craw, D. Tock, A. Bennett, “Finding Face Features”, Proc. 2nd European Conf. Computer Vision (ECCV’92), Vol. 2, pp. 92-96, 1992. [18]. T. Kanade, “Picture Processing Computer Complex and Recognition of Human Faces”, PhD thesis, Kyoto Univ., 1973. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 51 [19]. James L. Crowley, Alice C. Parker, “A Representation for Shape based on Peaks and Ridges in the Difference of Low-Pass Transform”, Technical Report- CMU-RI-TR-83-4, Carnegie-Mellon University, May 1983. [20]. James L. Crowley, Alice C. Parker, “A Representation for Shape based on Peaks and Ridges in the Difference of Low-Pass Transform”, IEEE Transaction on PAMI, pp 156-170, Vol. 6, No. 2, Mar 1984. [21]. Hai Tran, Augustin Lux, “A method for Ridge Extraction”, 6th Asian Conference on Computer Vision 2004 - ACCV’04, Vol. 2, Feb 2004, Korea. [22]. Hai Tran, Augustin Lux, “Toward a ridge and peak based symbolic representation for object recognition”, 3rd International Conference on Computer Science – RIVF’05, pp 64-69, Feb 2005, Vietnam. [23]. John M. Gauch, Stephen M. Pizer, “Multiresolution Analysis of Ridges and Valleys in Grey-Scale Images”, IEEE Transaction on PAMI, pp 635-646, Vol. 15, No. 6, Jun 1993. [24]. Antonio M. Lopez, Felipe Lumbreras, Joan Serrat, Juan J. Villanueva, “Evaluation of Methods for Ridge and Valley Detection”, IEEE Transaction on PAMI, pp 327-335, Vol. 21, No. 4, Apr 1999. [25]. James Damon, “Properties of Ridges and Cores for Two-Dimensional Images”, Journal of Mathematical Imaging and Vision, pp 163-174, Vol. 10, No. 2, Mar 1999. [26]. D. Eberly, R. Gardner, B. Morse, S. Pizer, C. Scharlach, “Ridges for Image Analysis”, Journal of Mathematical Imaging and Vision, pp 353-373, Vol. 4, No. 4, Dec 1994. [27]. J. B. Antoine Maintz, Petra A.V.D. Elsen, Max A. Viergever, “Evaluation of Ridge Seeking Operators for Multimodality Medical Image Matching”, IEEE Transaction on PAMI, pp 353-365, Vol. 18, No. 4, Apr 1996. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 52 [28]. Quan Yuan, Wen Gao, Hongxun Yao, “Robust frontal face detection in complex environment”, International Conference on Pattern Recognition 2002 – ICPR’02, pp 25-28, Aug 2002, Canada. [29]. F. Kanters, B. Platel, L. Florack, Bart M.H. Romeny, “Content Based Image Retrieval Using Multiscale Top Points”, Scale-space 2003, pp 33-43, LNCS 2695, Springer –Verlag 2003. [30]. Tony Lindeberg, “Edge Detection and Ridge Detection with Automatic Scale Selection”, International Journal of Computer Vision, pp 117-154, Vol. 30, No. 2, Nov 1998. [31]. Duc. A. Duong, Du. LH. Tran, Duan D. Tran, “Optimizing Speed for Adaptive Local Thresholding Algorithm Using Dynamic Programming”, International Conference on Electronics, Information, and Communications 2004-ICEIC’04, Vol. 1, pp. 438-441, Aug 2004. [32]. Markus Weber, “Frontal face dataset”, California Institute of Technology, 2003, [33]. Intel Open Source Computer Vision Library-OpenCV phiên bản 4.0 [34]. Intel Image Processing Library phiên bản 2.5 [35]. “Caltech categories”, California Institute of Technology, 2005, Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 53 PHỤ LỤC Phụ lục 1: Laplacian/Laplacian of Gaussian Tên gọi khác: Laplacian, Laplacian of Gaussian, LoG, Lọc Marr Laplacian là một phép đánh giá đẳng hướng của đạo hàm cấp hai trên một ảnh. Laplacian của một ảnh làm nổi bật những vùng có thay đổi lớn về độ sáng và vì thế nên nó thường được sử dụng để dò tìm cạnh. Laplacian rất nhạy cảm với nhiễu nên thường được áp dụng cho các ảnh đã được làm mịn (smoothed) trước đó bằng một số bộ lọc làm mịn như Gaussian (Gaussian smoothing filter) để làm giảm sự nhạy cảm của nó với nhiễu. Phép toán này nhận vào là một ảnh xám và kết quả trả ra cũng là một ảnh xám khác. Tính chất Laplacian L(x,y) của một ảnh có hàm biểu diễn độ sáng là I(x,y) được định nghĩa như sau: 2 2 2 2 ),( y I x IyxL ∂ ∂+∂ ∂= Do ảnh đầu vào được biểu diễn như một tập các pixel rời rạc, chúng ta phải tìm một mặt nạ rời rạc xấp xĩ với đạo hàm cấp hai trong định nghĩa của Laplacian. Ba mặt nạ thông dụng nhất của Laplacian được trình bày trong hình dưới đây. Hình AP.1 Ba xấp xĩ rời rạc cho lọc Laplacian. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 54 Tuy nhiên, do những mặt nạ này xấp xĩ một một đạo hàm cấp hai trên ảnh, chúng rất nhạy cảm với nhiễu. Để giải quyết điều này, ảnh thường được làm mịn bằng lọc Gaussian trước khi áp dụng lọc Laplacian. Bước tiền xử lý này giảm các thành phần nhiễu tần số cao trước khi thực hiện phép lấy vi phân. Thật vậy, do phép tính cuộn có tính kết hợp, cúng ta có thể gộp lọc làm mịn Gaussian với lọc Laplacian trước, sau đó cuộn lọc lai này với ảnh để thu được kết quả mong muốn. Thực hiện cách này chúng ta có hai lợi điểm: • Bởi vì cả hai mặt nạ lọc Gaussian và Laplacian thường nhỏ hơn rất nhiều so với kích thước ảnh, nên phương pháp này thực hiện tiết kiệm được rất nhiều tính toán. • Mặt nạ LoG (Laplacian of Gaussian) có thể được tính toán trước nhờ đó những tính toán phức tạp có thể được thực thi nhanh hơn tại thời điểm run- time. Hàm LoG hai chiều tâm tại 0 và với lọc Gaussian độ lệnh chuẩn σ có dạng sau: 2 22 2 2 22 4 2 11),( σσπσ yx eyxyxLoG +− ⎥⎦ ⎤⎢⎣ ⎡ +−−= và được biểu diễn dưới dạng sau. Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 55 Hình AP.2 Hàm LoG hai chiều. Trục x và y được đánh dấu theo độ lệch chuẩn σ. Một mặt nạ xấp xĩ cho hàm này (với một lọc Gaussian σ = 1.4) được biểu diễn trong hình AP.3. Hình AP.3 Xấp xĩ rời rạc của hàm LoG với lọc Gaussian σ = 1.4 Lưu ý rằng nếu lọc Gaussian được áp dụng với σ hẹp dần, mặt nạ LoG sẽ trở thành mặt nạ Laplacian đơn như trong hình AP.1. Điều này là do việc làm mịn với một lọc Gaussian kích thước nhỏ (σ < 0.5 pixel) trên một lưới rời rạc là không ảnh Phát hiện khuôn mặt dựa trên đặc trưng lồi lõm Trần Lê Hồng Dũ Trang 56 hưởng gì. Vì vậy trên một ảnh rời rạc, Laplacian đơn có thể được xem là một trường hợp giới hạn của LoG cho các lọc mịn Gaussian nhỏ. Phép LoG tính đạo hàm cấp hai trên ảnh. Điều này có nghĩa là ở những chổ ảnh có độ sáng hằng số (biến thiên độ sáng bằng 0), LoG sẽ cho giá trị 0. Trong những vùng lân cận, LoG sẽ cho giá trị dương ở phía tối hơn và giá trị âm ở phía sáng hơn. Điều này có nghĩa là khi áp dụng LoG trên một ảnh có nền thuần nhất, LoG sẽ cho kết quả: • Bằng không tại một điểm ở ngoài xa cạnh. • Lớn hơn không ở một mặt của cạnh. • Nhỏ hơn không ở mặt còn lại của cạnh. • Bằng không tại một số điểm giữa nằm trên cạnh.