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.