Luận văn Nghiên cứu và xây dựng hệ thống nhận dạng mặt người dựa trên fsvm và adaboost

KH OA C NT T – Đ H KH TN ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC LU BOUN VINH – HOÀNG PHƯƠNG ANH NGHIÊN CỨU VÀ XÂY DỰNG HỆ THỐNG NHẬN DẠNG MẶT NGƯỜI DỰA TRÊN FSVM VÀ ADABOOST LUẬN VĂN CỬ NHÂN TIN HỌC TP. HỒ CHÍ MINH - 07/2004 KH OA C NT T – Đ H KH TN ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC LUẬN VĂN TỐT NGHIỆP CỬ NHÂN TIN HỌC ĐỀ TÀI: NGHIÊN CỨU VÀ XÂY DỰNG HỆ THỐNG NHẬN DẠNG MẶT NGƯỜI DỰA TRÊN FSVM VÀ ADABOOST GIÁO VIÊN HƯỚNG DẪN TS. LÊ HOÀI BẮC SINH VIÊN THỰC HIỆN LU BOUN VINH 0012129 HOÀNG PHƯƠNG ANH 0012005 TP. HỒ CHÍ MINH - 07/ 2004 KH OA C NT T – Đ H KH TN 1 Lời cảm ơn X W Xin chân thành cảm ơn các thầy, các cô thuộc khoa Công Nghệ Thông Tin, trường Đại Học Khoa Học Tự Nhiên đã tận tình dạy dỗ, truyền đạt cho chúng tôi nhiều kiến thức quý báu. Xin tỏ lòng biết ơn sâu sắc đến thầy Lê Hoài Bắc, người đã tận tình giúp đỡ và truyền đạt nhiều kinh nghiệm để đề tài có thể được thực hiện và hoàn thành. Xin chân thành cảm ơn thầy Dương Anh Đức, thầy Trần Đức Duẩn, thầy Nguyễn Đức Hoàng Hạ, anh Trần Phước Long, bạn Hà Giang Hải và bạn Trần Công Nghĩa đã giúp đỡ, động viên chúng tôi rất nhiều trong quá trình thực hiện đề tài. Lời cảm ơn sâu sắc nhất xin dành cho bố mẹ vì ơn sinh thành và giáo dưỡng. Xin cảm ơn tất cả. TP. Hồ Chí Minh tháng 07 năm 2004. Lu Boun Vinh Hoàng Phương Anh KH OA C NT T – Đ H KH TN 2 Lời mở đầu X W Trong những năm gần đây, các ứng dụng về nhận dạng mặt người ngày càng phát triển và được đánh giá cao. Đã có các hệ thống nhận dạng mặt người dựa trên các phương pháp dò tìm nơron, SVM.v.v… và nhận dạng mặt người dựa trên phương pháp nơron, HMM, SVM v.v… Các ứng dụng vừa nêu trên mặc dù được dựa trên các lý thuyết khá cổ điển như HMM, nơron nhưng ứng dụng thực tế thì chưa được nhiều vì giới hạn về tốc độ. Hệ thống nhận dạng khuôn mặt người vốn có phạm vi ứng dụng lớn nên việc phát triển hệ thống nhận dạng khuôn mặt người theo các phương pháp mới có ý nghĩa hết sức quan trọng. nếu Đó là lý do chúng tôi chọn đề tài : “NGHIÊN CỨU VÀ XÂY DỰNG HỆ THỐNG NHẬN DẠNG MẶT NGƯỜI DỰA TRÊN FSVM VÀ ADABOOST” Để có hệ thống nhận dạng khuôn mặt với chất lượng tốt trong thời gian khá nhanh, chúng tôi đã tiếp cận bằng các mô hình xử lý được đánh giá là mạnh và xử lý tốc độ nhanh trong lĩnh vực trí tuệ nhân tạo, đó là mô hình phân cách với thuật toán FSVM và mô hình học AdaBoost làm công cụ xử lý chính cho việc nhận dạng và dò tìm người dựa vào thông tin khuôn mặt trên ảnh. KH OA C NT T – Đ H KH TN 3 Đề tài được tổ chức thành tám chương với nội dung : ¾ Chương 1: Phát biểu bài toán. ¾ Chương 2: Mô tả dữ liệu. ¾ Chương 3: Dò tìm khuôn mặt theo phương pháp AdaBoost. ¾ Chương 4: Rút trích đặc trưng từ khuôn mặt theo các phương pháp PCA toàn cục – PCA cục bộ. ¾ Chương 5: Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt. ¾ Chương 6: Thiết kế chương trình và hướng dẫn sử dụng. ¾ Chương 7: Thực nghiệm và kết quả. ¾ Chương 8: Nhận xét và hướng phát triển. KH OA C NT T – Đ H KH TN 4 Mục lục Lời cảm ơn.............................................................................................................................1 Lời mở đầu.............................................................................................................................2 Mục lục ..................................................................................................................................4 Danh sách các hình ................................................................................................................9 Danh sách các bảng..............................................................................................................10 Chương 1 .............................................................................................................................11 Phát biểu bài toán................................................................................................................11 1.1. Tổng quan và các khái niệm liên quan đến nhận dạng khuôn mặt ...........................11 1.1.1. Hệ thống sinh trắc học .......................................................................................11 1.1.2. Hệ thống nhận dạng khuôn mặt .........................................................................11 1.1.3. Hệ thống xác minh.............................................................................................11 1.1.4. Hệ thống nhận dạng tĩnh-tĩnh, tĩnh-động, động-động .......................................11 1.1.4.1. Hệ thống nhận dạng tĩnh tĩnh......................................................................11 1.1.4.2. Hệ thống nhận dạng tĩnh-động....................................................................12 1.1.4.3. Hệ thống nhận dạng động-động..................................................................12 1.2. Những thách thức trong bài toán nhận dạng khuôn mặt ...........................................12 1.3. Các hướng tiếp cận chính trong lĩnh vực nhận dạng khuôn mặt ..............................13 1.3.1. Các công trình nghiên cứu về phương pháp dò tìm và nhận dạng khuôn mặt...13 1.3.2. Hướng tiếp cận được thử nghiệm trong luận văn ..............................................15 Chương 2 .............................................................................................................................17 Mô tả dữ liệu.......................................................................................................................17 2.1. Thu thập dữ liệu........................................................................................................17 2.2. Biểu diễn dữ liệu khuôn mặt trong máy tính ............................................................17 Chương 3 .............................................................................................................................19 Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost .....................................................19 3.1. Giới thiệu ..................................................................................................................19 3.1.1. Các vấn đề trong việc dò tìm khuôn mặt nhanh ................................................19 3.1.2. Các hướng tiếp cận dò tìm khuôn mặt nhanh ....................................................20 3.1.3. Hướng tiếp cận theo phương pháp AdaBoost....................................................20 3.2. Phương pháp chọn đặc trưng cho AdaBoost ............................................................21 3.3. Phương pháp AdaBoost ............................................................................................23 KH OA C NT T – Đ H KH TN 5 3.3.1. Giới thiệu ...........................................................................................................23 3.3.2. Thuật toán AdaBoost .........................................................................................23 3.4. Bộ dò tìm phân tầng AdaBoost.................................................................................28 3.5. Dò tìm khuôn mặt với AdaBoost ..............................................................................32 3.5.1. Huấn luyện bộ dò tìm khuôn mặt.......................................................................32 3.5.2. Quá trình dò tìm khuôn mặt ...............................................................................32 3.6. Đánh giá và hướng phát triển....................................................................................34 3.6.1. Đánh giá.............................................................................................................34 3.6.1.1. Ưu điểm ......................................................................................................34 3.6.1.2. Khuyết điểm................................................................................................34 3.6.2. Hướng phát triển ................................................................................................34 3.6.2.1. Về mặt thuật toán học .................................................................................34 3.6.2.2. Về mặt thuật toán học .................................................................................34 Chương 4 .............................................................................................................................35 Rút trích đặc trưng từ khuôn mặt theo các phương pháp PCA toàn cục– PCA cục bộ ......35 4.1. Sơ lược toán đại số tuyến tính trong thống kê ..........................................................35 4.1.1. Vector riêng, trị riêng và sự chéo hoá của ma trận ............................................35 4.1.2. Kì vọng và phương sai trong thống kê đa chiều ................................................36 4.1.2.1. Kì vọng .......................................................................................................36 4.1.2.2. Ma trận hiệp phương sai .............................................................................37 4.2. Phương pháp phân tích thành phần chính (Principal Component Analysis hay PCA) .........................................................................................................................................37 4.2.1. Yêu cầu ..............................................................................................................37 4.2.2. Trích đặc trưng bằng phương pháp PCA...........................................................37 4.2.3. Kỹ thuật trích đặc trưng bằng PCA ...................................................................41 4.3. Phương pháp PCA toàn cục và cục bộ......................................................................43 4.3.1. Phương pháp PCA toàn cục...............................................................................43 4.3.2. Phương pháp PCA cục bộ..................................................................................43 4.4. Đánh giá....................................................................................................................44 4.4.1. Các đánh giá quan trọng về rút trích đặc trưng bằng phương pháp PCA..........44 4.4.2. So sánh phương pháp PCA toàn cục và PCA cục bộ ........................................45 Chương 5 .............................................................................................................................46 Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt............................46 KH OA C NT T – Đ H KH TN 6 5.1. Sơ lược lý thuyết SVM .............................................................................................46 5.1.1. Giới thiệu ...........................................................................................................46 5.1.2. Sơ lược lý thuyết SVM ......................................................................................46 5.1.2.1. SVM tuyến tính...........................................................................................46 5.1.2.2. SVM phi tuyến............................................................................................49 5.2. FSVM – SVM mờ (Fuzzy SVM) .............................................................................50 5.2.1. FSVM ................................................................................................................50 5.2.1.1. Các vấn đề nảy sinh của SVM....................................................................50 5.2.1.2. Mờ hóa tập dữ liệu......................................................................................51 5.2.1.3. FSVM .........................................................................................................51 5.2.2. Thuật toán mờ hóa dữ liệu .................................................................................53 5.2.2.1. Mờ hóa tập dữ liệu áp dụng KNN – ODM .................................................54 5.2.2.1.1. Xác định tập mẫu vượt.........................................................................54 5.2.2.1.2. Hàm thành viên....................................................................................58 5.2.2.2. Mờ hóa tập dữ liệu áp dụng phương pháp Kernel ......................................59 5.2.2.3. Mờ hóa tập dữ liệu áp dụng phương pháp SVM ........................................60 5.2.3. Phân tích các phương pháp FSVM nhiều lớp ....................................................61 5.2.3.1. Phân tích cơ chế 1 đối tất cả .......................................................................61 5.2.3.2. Phân tích phương pháp phân lớp theo cặp..................................................66 5.3. Nhận dạng khuôn mặt người với FSVM ..................................................................70 5.3.1. Nhận dạng đa lớp dùng FSVM với cây nhị phân ..............................................70 5.3.2. Nhận dạng đa lớp dùng FSVM với phương pháp bầu cử ..................................71 5.3.3. Nhận dạng khuôn mặt dùng FSVM với phương pháp bầu cử ...........................71 5.3.3.1. Giai đoạn huấn luyện hệ thống ...................................................................71 5.3.3.1.1. Huấn luyện FSVM phi tuyến cho bài toán nhận dạng khuôn mặt .......71 5.3.3.1.2. Véctơ hóa tập mẫu khuôn mặt thô .......................................................72 5.3.3.1.3. Rút trích đặc trưng khuôn mặt .............................................................73 5.3.3.1.4. Tạo các bộ phân loại nhị phân cho phương pháp bầu cử.....................76 5.3.3.1.5. Huấn luyện cho mỗi bộ phân loại FSVM nhị phân từ các tập mẫu nhị phân hóa hai lớp khuôn mặt với nhau..................................................................76 5.3.3.2. Giai đoạn nhận dạng khuôn mặt .................................................................77 5.3.3.2.1. Nhận dạng khuôn mặt dùng FSVM .....................................................78 5.3.3.2.2. Véctơ hoá khuôn mặt thô.....................................................................78 KH OA C NT T – Đ H KH TN 7 5.3.3.2.3. Rút trích đặc trưng khuôn mặt .............................................................78 5.3.3.2.4. Đưa mẫu thử nghiệm khuôn mặt x vào cấu trúc nhị phân và thực hiện đối sánh trên từng mô hình nhị phân FSVM .......................................................78 5.3.4. Nhận xét và hướng phát triển tương lai .............................................................79 5.3.4.1. Ưu điểm ......................................................................................................79 5.3.4.2. Nhược điểm ................................................................................................79 5.3.4.3. Hướng phát triển .........................................................................................80 5.3.4.3.1. Về mặt thuật toán học ..........................................................................80 5.3.4.3.2. Về chương trình ứng dụng ...................................................................81 Chương 6 .............................................................................................................................82 Thiết kế chương trình và hướng dẫn sử dụng .....................................................................82 6.1. Giới thiệu ..................................................................................................................82 6.2. Thiết kế và cài đặt chương trình ...............................................................................82 6.3. Giao diện màn hình và hướng dẫn sử dụng ..............................................................83 Chương 7 .............................................................................................................................91 Thực nghiệm và kết quả......................................................................................................91 7.1. Thử nghiệm bộ dò tìm khuôn mặt ............................................................................91 7.1.1. Dữ liệu ...............................................................................................................91 7.1.2. Thực nghiệm trên từng bộ tham số ....................................................................91 7.1.3. Nhận xét.............................................................................................................93 7.2. Thử nghiệm bộ nhận dạng khuôn mặt ......................................................................93 7.2.1. Dữ liệu ...............................................................................................................93 7.2.2. Phương pháp FSVM ..........................................................................................93 7.2.2.1. Tham số Heuristic Fuzzy Kernel sau khi huấn luyện .................................94 7.2.2.2. Phương pháp FSVM so sánh các Kernel ....................................................94 7.2.2.3. Phương pháp FSVM so sánh cách trích đặc trưng .....................................95 7.2.2.4. Phương pháp FSVM so sánh các tập ảnh 44 người và tập ảnh 10 người ...96 7.2.2.5. Phương pháp FSVM so sánh các đoạn videoclip .......................................98 7.2.3. Nhận xét.............................................................................................................99 Chương 8 ...........................................................................................................................100 Nhận xét và hướng phát triển............................................................................................100 8.1. Thuận lợi .................................................................................................................100 8.2. Khó khăn.................................................................................................................101 KH OA C NT T – Đ H KH TN 8 8.3. Hướng phát triển .....................................................................................................102 8.4. Tổng kết ..................................................................................................................103 TÀI LIỆU THAM KHẢO .................................................................................................104 KH OA C NT T – Đ H KH TN 9 Danh sách các hình Hình 1-Sơ đồ hệ thống nhận dạng khuôn mặt .....................................................................16 Hình 2-Các miền hình học đặc trưng Haar-like...................................................................21 Hình 3-Ý nghĩa hình học của đạo hàm ảnh .........................................................................22 Hình 4-Cách tính giá trị một ô đặc trưng.............................................................................23 Hình 5-Hình vẽ minh hoạ thuật toán AdaBoost ..................................................................28 Hình 6-Hình vẽ minh hoạ bộ dò tìm phân tầng ...................................................................29 Hình 7-Hình vẽ các đặc trưng Haar-let được sử dụng.........................................................32 Hình 8-Hình vẽ minh hoạ hướng của véctơ riêng ...............................................................40 Hình 9-hình vẽ minh họa nhược điểm về điểm vượt của SVM...........................................50 Hình 10-Sơ đồ diễn tả cách mờ hoá tập học ...........