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 ........................................................................53 Hình 11-Đồ thị diễn tả 3 luật mờ xác định độ đo thành viên...............................................54 Hình 12-Hình minh họa lỗi của SVM 1-tất cả.....................................................................62 Hình 13-Hình minh họa trục độ đo thành viên ....................................................................63 Hình 14-Hình minh họa cách khắc phục của FSVM...........................................................64 Hình 15-Hình minh họa lỗi của SVM 1 đối 1 .....................................................................67 Hình 16- Hình minh họa đồ thị DDAG SVM 1 đối 1 .........................................................68 Hình 17-Hình minh họa hướng giải quyết của FSVM cho SVM 1 đối 1............................68 Hình 18-Hình minh họa bộ phân loại đa lớp dạng cây........................................................71 Hình 19-Sơ đồ huấn luyện FSVM đa lớp ............................................................................72 Hình 20 –Cách véctơ hóa ảnh để nhận dạng........................................................................73 Hình 21-Sơ đồ nhận dạng khuôn mặt dùng FSVM .............................................................78 Hình 22-Màn hình chính......................................................................................................84 Hình 23-Màn hình cỏ sở dữ liệu ..........................................................................................85 Hình 24-Màn hình chọn thông số ........................................................................................85 Hình 25-Màn hình nhận dạng ảnh tĩnh ................................................................................86 Hình 26-Màn hình nhận dạng Video ...................................................................................87 Hình 27-Màn hình nhận dạng webcam................................................................................88 Hình 28-Màn hình test ảnh tĩnh ...........................................................................................89 Hình 29-Màn hình huấn luyện FSVM .................................................................................90 KH OA C NT T – Đ H KH TN 10 Danh sách các bảng Bảng 1-Thuật toán Adaboost ...............................................................................................27 Bảng 2-Thuật toán huấn luyện bộ dò tìm phân tầng............................................................31 Bảng 3-Bảng kết quả detect với tập dữ liệu CBCL .............................................................91 Bảng 4-Bảng kết quả detect với tập dữ liệu 44 người .........................................................92 Bảng 5-Bảng kết quả detect các ảnh to trên Internet ...........................................................92 Bảng 6-Bảng kết quả detect khuôn mặt trong webcam - video ...........................................93 Bảng 7-Bảng kết quả các tham số Fuzzy Kernel được huấn luyện .....................................94 Bảng 8-Bảng kết quả so sánh các kernel khác nhau với FSVM..........................................95 Bảng 9-Bảng kết quả so sánh các cách trích đặc trưng .......................................................96 Bảng 10-Bảng kết quả so sánh hai tập dữ liệu 44 người và 10 người .................................98 Bảng 11-Bảng kết quả so sánh các đoạn video clip.............................................................99 KH OA C NT T – Đ H KH TN Phát biểu bài toán 11 Chương 1 Phát biểu bài toán 1.1. Tổng quan và các khái niệm liên quan đến nhận dạng khuôn mặt 1.1.1. Hệ thống sinh trắc học Hệ thống sinh trắc học là một hệ thống được thiết kế để xác minh và nhận dạng một người dựa vào những đặc trưng sinh học duy nhất của người đó. 1.1.2. Hệ thống nhận dạng khuôn mặt Hệ thống nhận dạng khuôn mặt là một hệ thống được thiết kế để tìm thông tin của một người. Kĩ thuật nhận dạng là kiểm tra sự phù hợp dựa trên phép so sánh một-nhiều cụ thể là tìm ra một người là ai trong số những người đã được lưu trữ trong hệ thống dựa vào thông tin khuôn mặt. 1.1.3. Hệ thống xác minh Hệ thống xác minh/xác thực khuôn mặt là một hệ thống được thiết kế để xác minh thông tin của một người . Kĩ thuật xác minh là kiểm tra sự phù hợp trên phép so sánh một-một cụ thể là đối chiếu thông tin mới nhận về một người với thông tin đã lưu trữ về người này có khớp hay không dựa trên thông tin khuôn mặt. 1.1.4. Hệ thống nhận dạng tĩnh-tĩnh, tĩnh-động, động-động 1.1.4.1. Hệ thống nhận dạng tĩnh tĩnh Hệ thống nhận dạng tĩnh-tĩnh là hệ thống được thiết kế bằng cách sử dụng một số ảnh tĩnh làm mẫu để nhận dạng khuôn mặt người trong ảnh tĩnh. Kĩ thuật KH OA C NT T – Đ H KH TN Phát biểu bài toán 12 nhận dạng này kiểm tra sự phù hợp dựa trên phép so sánh một nhiều như hệ thống nhận dạng nói chung ở trên. 1.1.4.2. Hệ thống nhận dạng tĩnh-động Hệ thống nhận dạng tĩnh-động là hệ thống được thiết kế bằng cách sử dụng một số ảnh tĩnh làm mẫu để nhận dạng khuôn mặt người trong ảnh động. Kĩ thuật nhận dạng này kiểm tra sự phù hợp dựa trên phép so sánh một nhiều như hệ thống nhận dạng nói chung ở trên, song ảnh cần kiểm tra là các khung ảnh động trong các đoạn phim từ các máy camera. Kĩ thuật này dĩ nhiên không thể chính xác vì chuyển động của mặt người trong đoạn phim khá phức tạp song thể hiện trong ảnh tĩnh để huấn luyện lại ít. 1.1.4.3. Hệ thống nhận dạng động-động Hệ thống nhận dạng động-động là hệ thống được thiết kế bằng cách sử dụng các ảnh động làm mẫu để nhận dạng khuôn mặt người trong ảnh động. Kĩ thuật nhận dạng này kiểm tra sự phù hợp dựa trên phép so sánh một nhiều như hệ thống nhận dạng nói chung ở trên. Tuy nhiên, kĩ thuật này chính xác hơn kĩ thuật sử dụng trong hệ thống nhận dạng tĩnh-động do sự chuyển động phức tạp của khuôn mặt người cũng được huấn luyện bằng các khung ảnh động. 1.2. Những thách thức trong bài toán nhận dạng khuôn mặt Những biến đổi quá lớn giữa các ảnh khuôn mặt khác nhau từ một người cần nhận dạng gồm trạng thái cảm xúc trên khuôn mặt, ánh sáng, và các thay đổi vị trí của khuôn mặt..vv. Giới hạn về số ảnh cần thiết cho việc nhận dạng, tập học không thể bao quát được tất cả các biến đổi có thể có trên khuôn mặt của một người cần nhận dạng trong thế giới thực. KH OA C NT T – Đ H KH TN Phát biểu bài toán 13 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 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 Bài toán nhận dạng khuôn mặt cần xác định hai vấn đề chính: dùng thông tin nào để nhận dạng: chân mày, cặp mắt, mũi, môi, tai, hay kết hợp các thông tin trên. Và dùng phương pháp nào để huấn luyện cho máy nhận dạng dùng nguồn thông tin đó. Nhận dạng khuôn mặt trên máy tính đã trãi qua nhiều bước thăng trầm với các kết quả như sau: ¾ Wenyi Zhao, Arvindh Krishnaswamy, Rama Chellappa, Danie L.Swets, John Weng (1998)[1] sử dụng phương pháp PCA (phân tích thành phần chính) kết hợp LDA (phân tích độc lập tuyến tính). Bước 1, chiếu ảnh khuôn mặt từ không gian ảnh thô sang không gian các không gian khuôn mặt (Mỗi lớp khuôn mặt được nhận dạng sẽ được mô hình hóa bằng một không gian khuôn mặt) dùng PCA. Bước 2, sử dụng phương pháp LDA để tạo bộ phân loại tuyến tính có khả năng phân lớp các lớp khuôn mặt. ¾ Emmanuel Viennet và Francoise Fogelman Soulie (1998),[3] sử dụng phương pháp mạng neural nhân tạo để xử lý và nhận dạng khuôn mặt. ¾ Antonio J.Colmenarez và Thomas S.Huang (1998),[4] sử dụng kỹ thuật học thị giác và phù hợp mẫu 2-D. Ông quan niệm bài toán dò tìm khuôn mặt là thao tác phân loại khuôn mặt trong đó khuôn mặt thuộc về một lớp và các đối tượng khác thuộc về lớp còn lại bằng cách ước lượng mô hình xác suất cho mỗi lớp, và việc dò tìm sử dụng luật quyết định Maximum-likelihood. ¾ Kazunori Okada, Johannes Steffens, Thomas Maurer, Hai Hong, Egor Elagin, Hartmut Neven, and Christoph (1998),[5] nhận dạng khuôn mặt dựa vào sóng Gabor và phương pháp phù hợp đồ thị bó. Với ý tưởng dùng đồ thị KH OA C NT T – Đ H KH TN Phát biểu bài toán 14 để biểu diễn khuôn mặt, ảnh khuôn mặt được đánh dấu tại các vị trí đã được xác định trước trên khuôn mặt, gọi các vị trí này chính là các vị trí chuẩn. Khi thực hiện thao tác so khớp đồ thị với một ảnh, các điểm chuẩn (Jets) sẽ trích ra từ ảnh và so sánh các điểm chuẩn này với tất cả các điểm chuẩn tương ứng trong các đồ thị khác nhau, và đồ thị nào phù hợp nhất với ảnh sẽ được chọn. ¾ Jeffrey Huang, Chengjun Liu, và Harry Wechsler (1998)[8], đề xuất thuật toán căn cứ trên tính tiến hóa (Evolutionary computation) và di truyền (Genetic) cho các tác vụ nhận dạng khuôn mặt. Đối với cách tiếp cận này, hai mắt sẽ được dò tìm trước tiên và thông tin này được xem là vết để quan sát khuôn mặt, trình xử lý dò tiếp mắt bằng cách sử dụng một thuật toán lai để kết hợp thao tác học và tiến hóa trong quá trình học. ¾ Oi Bin Sun, Chian Prong Lam và Jian Kang Wu (1998)[10], sử dụng phương pháp tìm vùng hai chân mày, hai mắt, mũi, miệng và cằm. Ảnh khuôn mặt thẳng ban đầu được chiếu theo chiều ngang để tìm các giá trị điểm ảnh thỏa ngưỡng cho trước, đồ thị biểu diễn theo trục ngang sẽ định vị vị trí biên trên và biên dưới của hình chữ nhật bao các đặc trưng cục bộ khuôn mặt. Tương tự với chiều đứng để tìm ra đường biên bên trái và phải cho các vùng đặc trưng. ¾ Ara V.Nefian và Monson H.Hayes III (1998)[12] trình bày hướng tiếp cận theo mô hình mô hình Markov ẩn (HMM) trong đó ảnh mẫu khuôn mặt được lượng hóa thành chuỗi quan sát trên khuôn mặt theo quan niệm dựa trên thứ tự xuất hiện các đặc trưng khuôn mặt {hai chân mày, hai lông mi, mũi, miệng, cằm}. Trong chuỗi quan sát đó, mỗi quan sát lại là một vector nhiều chiều và mỗi vector quan sát này được sử dụng để đặc trưng cho mỗi trạng thái trong chuỗi trạng trạng thái của HMM. Mỗi người được ước lượng bằng một mô hình của HMM. KH OA C NT T – Đ H KH TN Phát biểu bài toán 15 ¾ Guodong Guo, Stan Z.Li, Kap Luk Chan (17 January 2001) [13], dùng phương pháp SVM để nhận dạng khuôn mặt. Sử dụng chiến lược kết hợp nhiều bộ phân loại nhị phân để xây dựng bộ phân loại SVM đa lớp. ¾ Hichem Sahbi (7 April 2003) [14] sử dụng phương pháp SVM để dò tìm khuôn mặt, áp dụng các chiến lược đa cấp để tối ưu hóa tốc độ. ¾ ZhenQiu Zhang, Long Zhu, Stan Z.Li, và HongJiang Zhang (2001) [15] sử dụng phương pháp AdaBoost để dò tìm khuôn mặt trong thời gian thực với nhiều góc nhìn khác nhau. ¾ Trần Phước Long – Nguyễn Văn Lượng (2003)[27], nhận dạng khuôn mặt dựa vào thông tin xuất hiện trên ảnh bằng phương pháp SVM và HMM. 1.3.2. Hướng tiếp cận được thử nghiệm trong luận văn Trong đề tài này chúng tôi thử nghiệm phương pháp nhận dạng FSVM (Fuzzy SVM). Phương pháp PCA (phân tích thành phần chính) được sử dụng ở dạng PCA-toàn cục (Global PCA) và dạng cải tiến cải tiến PCA-cục bộ (Local PCA) để rút ra các vector đặc trưng làm đầu vào cho bộ nhận dạng trên nhằm tăng tốc độ xử lý. Việc cô lập khuôn mặt trong ảnh đầu vào (ảnh chứa khuôn mặt) được thực hiện với phương pháp dò tìm khuôn mặt trong ảnh dùng AdaBoost. Sơ đồ hệ thống nhận dạng khuôn mặt được minh họa trong hình sau: KH OA C NT T – Đ H KH TN Phát biểu bài toán 16 Hình 1-Sơ đồ hệ thống nhận dạng khuôn mặt ? phương pháp dò tìm AdaBoost Trích đặc trưng sử dụng PCA –PCA cục bộ phương pháp nhận dạng FSVM Ảnh tĩnh Webcam Video KH OA C NT T – Đ H KH TN Mô tả dữ liệu 17 Chương 2 Mô tả dữ liệu 2.1. Thu thập dữ liệu Cơ sở dữ liệu ảnh khuôn mặt gồm nhiều người được thu thập từ nhiều nguồn khác nhau. Tập ảnh để huấn luyện bộ dò tìm khuôn mặt được lấy từ trang web của trung tâm CBCL thuộc trường đại học MIT. Tập ảnh gồm hai bộ ảnh như sau : ảnh huấn luyện (2.429 mặt người, 4.548 không phải mặt người) và ảnh thử nghiệm (472 mặt người, 23,573 không phải mặt người). Cơ sở dữ liệu ảnh để nhận dạng khuôn mặt gồm 44 người, trong đó mỗi người bao gồm 10-15 ảnh khác nhau. 25 người đâu tiên có ảnh được trích từ nguồn dữ liệu ORL của AT&T. ( Nguồn dữ liệu này chuyên phục vụ cho các ứng dụng nhận dạng khuôn mặt. 19 người tiếp theo có ảnh được chụp từ webcam. Ngoài ra, còn có tập dữ liệu do chúng tôi tạo ra trong lúc thực hiện đề tài. Đó là dữ liệu được thu thập bằng webcam gồm 10 người khác nhau. Chính sự chủ động trong việc tạo mẫu nên số lượng ảnh trung bình khoảng trên 15 ảnh / 1 người.. Nhận xét về tập mẫu dữ liệu: Hầu hết các khuôn mặt xuất hiện trong ảnh là khuôn mặt trực diện với mặt phẳng ảnh và mỗi khuôn mặt đều đầy đủ thông tin đặc trưng như {Hai chân mày, hai mắt, mũi, miệng, cằm}. Một số khuôn mặt quay với một góc không đáng kể và có các sắc thái vui,buồn, cười khác nhau. Kích thước chuẩn hoá của mỗi mẫu trong tập huấn luyện 30×30 (pixels) 2.2. Biểu diễn dữ liệu khuôn mặt trong máy tính KH OA C NT T – Đ H KH TN Mô tả dữ liệu 18 Dữ liệu ảnh biểu diễn bên trong máy tính là cường độ sáng của điểm ảnh, tại vị trị x và y: (I(x,y)). Để biểu diễn dữ liệu cho các thuật toán học nhận dạng, ta dùng cách tổ chức dữ liệu như sau: Đọc từng dòng ảnh theo thứ tự từ trên xuống, mỗi dòng ảnh được bố trí liên tục nhau trên một mảng số thực một chiều. Như vậy từ ảnh có kích thước 30×30 (pixels) ta biểu diễn thành mảng vector một chiều trong máy tính x=(x1,x2,….,x900). Đây là cách bố trí để thí nghiệm cho phương pháp PCA và FSVM. KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 19 Chương 3 Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 3.1. Giới thiệu Dò tìm đối tượng là bài toán cơ bản và quan trọng trong lĩnh vực thị giác máy tính. Các kỹ thuật đã được áp dụng có thể chia thành một trong hai tiếp cận: so khớp các mô hình hình học hai, ba chiều vào ảnh [Seutens at al., 1992, Chin và Dyer, 1986, Besl và Jain, 1985], hay phương pháp so khớp các mô hình khung vào ảnh có chứa khuôn mặt cần dò tìm. Các nghiên cứu trước đây cho thấy rằng các phương pháp dựa trên khung nhìn có thể dò tìm các khuôn mặt thẳng trong nền phức tạp một cách hiệu quả. Bài toán dò tìm khuôn mặt nhanh trên ảnh là bài toán quan trọng vì là quá trình nhận dạng đối tượng sẽ thiếu chính xác nếu như thiếu bước dò tìm và định vị được đối tượng. Bài toán dò tìm khuôn mặt nhanh có ý nghĩa rất quan trọng trong việc nhận dạng, theo vết các đối tượng chuyển động trong các đoạn video hay camera. 3.1.1. Các vấn đề trong việc dò tìm khuôn mặt nhanh Bản thân việc dò tìm khuôn mặt trên ảnh đã có nhiều vấn đề như o Biến đổi mặt phẳng ảnh (quay, hướng.v.v.. của khuôn mặt) o Biến đổi độ sáng và ngữ cảnh o Biến đổi nền o Biến đổi hình dáng (các sắc thái khuôn mặt khác nhau) Ngoài ra việc dò tìm khuôn mặt nhanh còn chịu ràng buộc về thời gian xử lý. Tuy nhiên, nếu như việc dò tìm được tiến hành trên các đoạn video hay KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 20 camera ta có thể áp dụng các phương pháp xử lý các khung hình liên tục cùng một lúc như theo vết đối tượng, trừ ảnh v.v…. 3.1.2. Các hướng tiếp cận dò tìm khuôn mặt nhanh ¾ Hướng dò tìm khuôn mặt trên ảnh màu dựa trên sự phân tích màu sắc của vùng da. Mặc dù việc xử lý khá nhanh nhưng hướng này có giới hạn chỉ xử lý trên ảnh màu và thường nhạy cảm với ánh sáng, thường chỉ sử dụng làm các bước tiền xử lý cho các hướng khác. ¾ Hướng dò tìm khuôn mặt dựa trên đặc trưng chủ yếu dựa vào các đặc trưng của khuôn mặt người được quy định trước. Thành công nhất trong dò tìm khuôn mặt người trong thời gian thực là phương pháp ASM (Active shape Models). ¾ Hướng dò tìm khuôn mặt dựa trên thông tin hình ảnh gồm mạng nơron, các hướng thống kê (SVM, AdaBoost…). Phương pháp SVM và mạng nơron cũng đạt được kết quả cao trong thời gian khá nhanh song cũng chỉ vài ảnh trong một giây nên khó có thể áp dụng trong việc nhận dạng thời gian thực. Riêng phương pháp AdaBoost cho kết quả khả quan vì có thể xử lý đến khoảng 15-20 khung hình trong một giây. 3.1.3. Hướng tiếp cận theo phương pháp AdaBoost Chúng tôi tiến hành dò tìm khuôn mặt người theo phương pháp AdaBoost với các lý do như sau: ¾ Phương pháp dò tìm AdaBoost dựa trên ý tưởng xây dựng các bộ dò tìm yếu mặc dù độ chính xác không cao nhưng có thời gian xử lý rất nhanh. Tuy nhiên khi kết hợp các bộ dò tìm lại có thể đạt độ chính xác cao. ¾ Phương pháp AdaBoost sử dụng kết hợp các đặc trưng vốn dĩ tính toán rất nhanh, thích hợp cho việc dò tìm trong thời gian thực. KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 21 ¾ Các bộ phân loại AdaBoost có thể xây dựng phân tầng với độ phức tạp xử lý từ thấp đến cao, nhằm loại nhanh các ứng viên xấu (không phải mặt người) vốn dĩ nhiều hơn nhiều các ứng viên là mặt nguời để đến bộ phân loại phức tạp hơn (chỉ còn lại ít ứng viên chưa bị loại). 3.2. Phương pháp chọn đặc trưng cho AdaBoost Một phương pháp chọn đặc trưng thích hợp cho AdaBoost là phép biến đổi Haar-like. Phép biến đổi Haar-like dựa trên ý tưởng rất đơn giản, đặc trưng được tính bằng độ chênh lệch giữa tổng các miền hình học. Có 3 tập hợp miền hình học chính như sau: Hình 2-Các miền hình học đặc trưng Haar-like Giả sử miền đen là dương và miền trắng là âm thì đặc trưng Haar-let tính bằng tổng giá trị pixel các ô đen trừ cho tổng giá trị các pixel các ô trắng. Cách tính nhanh phương pháp Haar-like dựa trên đạo hàm ảnh bậc nhất ii(x,y) của ảnh i(x,y). Đạo hàm ii(x,y) của ảnh i(x,y) chính là tổng giá trị các pixel tính từ góc trái trên đến (x,y) : ∑∑ ≤ ≤ = xx yy yxiyxii ' ' )','(),( KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 22 Hình 3-Ý nghĩa hình học của đạo hàm ảnh Việc tính toán đạo hàm ảnh được thực hiện rất nhanh bằng việc cộng tích lũy như sau: Sau khi có được đạo hàm ảnh, việc tính toán trên một khối hình chữ nhật được tính như sau: s(x,y) = s(x,y-1) + i(x,y) ii(x,y) = ii(x-1,y) + s(x,y) trong đó s(x,y) là tổng của cột x tính từ đầu dòng đến vị trí (x,y). Sau khi có được đạo hàm ảnh, ta chỉ việc tính giá trị một ô chữ nhật bằng cách như sau: chẳng hạn ô chữ nhật D ta có val(D) = val(ABCD) – val(AC) – val(AB) + val(A) , do đó nếu tính theo tọa độ (x,y) ta có phương trình sau: sr = (ii(x,y) + ii(x-W,y-L)) – (ii(x-W,y) + ii(x,y-L)) KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 23 Hình 4-Cách tính giá trị một ô đặc trưng Cuối cùng, việc tính các đặc trưng Haar-like chỉ còn là trừ giá trị tổng các ô chữ nhật được tính như trên. Chú ý, với cái nhìn đại số tuyến tính về phương pháp tính giá trị tổng của một ô trong ảnh, giá trị tổng một ô r(trong ô có giá trị 1, ngoài ô có giá trị 0) của ảnh i chính là phép nhân vô hướng ’* trong đó chính là ma trận có được bằng cách chuyển ma trận A kích thước mxn thành ma trận kích thước 1x(m.n) và A’ là ma trận chuyển vị của A. 3.3. Phương pháp AdaBoost 3.3.1. Giới thiệu Cho hai tập ảnh, một là khuôn mặt người và một không phải là mặt người. Sau khi áp dụng phương pháp trích đặc trưng như trên, có tất cả trên 50.000 đặc trưng dựa trên 5 đặc trưng cơ bản trong ảnh kích thước 24x24. Mặc dù việc xử lý từng đặc trưng là rất nhanh song số lượng đặc trưng lớn nên áp dụng tất cả các đặc trưng là không thể. Phương pháp AdaBoost dựa trên ý tưởng kết hợp tuyến tính các bộ phân loại, trong đó mỗi bộ phân loại bao gồm các đặc trưng trên. Vấn đề còn lại là huấn luyện từng bộ phân loại. 3.3.2. Thuật toán AdaBoost Xét bài toán hai lớp, mẫu huấn luyện bao gồm M bộ (xi,yi) đã được gán nhãn, với i∈ {1,2,..,M} trong đó yi ∈ {+1,-1} là nhãn và xi ∈Rn là các mẫu huấn luyện. Trong AdaBoost, một bộ phân loại mạnh hơn được xây dựng dựa trên sự kết hợp tuyến tính giữa M bộ phân loại yếu hơn: ∑ = = M m mM xhxH 1 )()( (1) KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 24 Các bộ phân loại yếu hơn có thể mang các giá trị thực, hm(x) ∈ R. Phân loại của x được quyết định bằng hàm H(x) = sign[HM(x)], trong đó độ lớn |HM(x)| cho ta độ tin cậy. Mỗi mẫu được kết hợp với một trọng lượng. Trong quá trình học, các trọng lượng sẽ được cập nhật động nhấn mạnh các phân loại mạnh trước đó bị phân loại sai. Tuy nhiên, quá trình cập nhật trọng lượng chỉ cần thiết đối với thuật toán AdaBoost nguyên thủy. Đối với các thuật toán AdaBoost cải tiến gần đây, quá trình này có thể được thay thế bằng một hàm tối ưu hóa trong quá trình boost. Lỗi xảy ra khi H (x) ≠ y hay yHM(x) < 0. Lề của mẫu (x, y) qua hàm h(x) ∈ R trên tập các mẫu huấn luyện được định nghĩa là yh(x). Lề có thể được xem là số đo độ tin cậy của giá trị đoán trước của h. Lỗi phân lớp của HM có biên trên là: J(HM) = ∑ − i xHy iMie )( (2) Thuật toán AdaBoost xây dựng hảm h(x) bằng cách giảm tối đa (2). Cho HM – 1(x) = )( 1 1 xhM m m∑ −= , hM(x) tốt nhất cho phân lớp mạnh H M (x) = H M-1 (x) + hm (x) là hàm dẫn tới giá trị nhỏ nhất: (x))h (x)J(H minarg 1-Mht τ+=Mh (3) và hàm có giá trị nhỏ nhất được chứng minh là: ),|1( ) x,|1 P(y log 2 1 (x)h )1( )1( M − − −= +== M M xyP ω ω (4) với ω(M-1) là trọng lượng tại thời điểm M. Dùng công thức P(y| x,ω) = P(x| y,ω) P(y) và cho ),1|( ),1|(log 2 1 (x)LM ω ω −= +== yxP yxP (5) ⎥⎦ ⎤⎢⎣ ⎡ −= +== )1( )1(log 2 1 yP yPT (6) chúng ta có được hM (x) = LM(x) – T. LM được học ra từ các mẫu của cả hai phân lớp. Ngưỡng T được xác định bằng tỉ lệ log của các xác suất trước đó. KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 25 Ta có một phương pháp để tính phương trình (6), ứng dụng khi học các bộ phân lớp tối ưu. Vì rút ra một bộ phân loại yếu trong một miền không gian nhiều chiều là công việc quan trọng, xin được đưa ra sau đây một mô hình thống kê học theo từng giai đoạn dựa trên vài đặc điểm vô hướng. Một đặc điểm vô hướng j của x được tính bằng một phép biến đổi từ không gian dữ liệu n chiều thành đường thẳng thực, zj(x) ∈ Z. Một đặc điểm có thể là hệ số, hay nói trong xử lý ảnh là phép biến đổi vi ba tín hiệu. Nếu phương pháp tìm kiếm ước lượng được sử dụng như phép biến đổi, zj(x) đơn giản được xem là toạ độ thứ j của x. Một danh sách K đặc điểm ứng cử viên có thể được tạo, Z ={ zj(x), …, zK(x)}. Trong phần sau, chúng ta sử dụng z(m) để biểu diễn cho đặc điểm được chọn trong giai đoạn m, và zk(x) là đặc điểm được tính toán từ x, sử dụng phép biến đổi thứ k. Giả sử Z là một tập rất hoàn chỉnh, tập các phân lớp yếu có thể có cho bài toán phân lớp yếu tối ưu có thể được lập như sau: Trước tiên, tại giai đoạn M, khi M-1 đặc điểm z(1), z(2), …, z(M-1) đã được chọn và trọng lượng được cho là ωM-1, chúng ta xấp xỉ p(x|y, ωM-1) bằng cách dùng phân phối của M đặc điểm: p(x|y, ωM-1) ≈ p(z(1), z(2), …, z(M-1), zk, |y, ωM-1) (7) = p(z(1)|y, ωM-1) p(z(2) |y, z(1), ωM-1)… p(z(M-1)|y, z(1), z(2), …, z(M-2), ωM-1) p(zk, |y, z(1), z(2), …, z(M-1), ωM-1) (8) Bởi vì Z là tập rất hoàn chỉnh, phép xấp xỉ vẫn tốt đối với tập M đủ lớn khi M đặc điểm được chọn thích hợp. Ghi chú: p(zm|y, z(1), z(2), …, z(m-1)) thực ra là p(zm|y, ω(m-1)) bởi vì ω(m) chứa thông tin về toàn bộ quá trình tạo ω và bao gồm các thành phần lệ thuộc trên z(1), z(2), …, z(m-1). Vì vậy, chúng ra có: p(x|y, ωM-1) ≈ p(z(1)| y, ω(0)) p(z(2)| y, ω(1))… p(z(M-1)| y, ω(M-2)) p(zk| y, ω(M-1)) (9) KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 26 Trong vế phải của phương trình trên, mọi mật độ điều kiện đều không thay đổi, ngoại trừ thành phần cuối p(zk| y, ω(M-1)). Học bộ phân lớp yếu nhất ở giai đoạn M tức là chọn đặc trưng tốt nhất zM cho zk để tối tiểu hoá J theo phương trình (3) Mật độ xác suất p(zk| y, ω(M-1)) cho phân lớp dương y = +1 và phân lớp âm y = -1 có thể phỏng đoán được từ histogram tính được qua đánh giá công nhận trọng lượng của các ví dụ huấn luyện sử dụng các trọng lượng ω(M-1). Cho ) 1,- y | ( ) 1, y | ( )( )1( )1( )( − − = +== M k M kM k zP zPxL ω ω và })({ 2 1)( )()( TxLxh Mk M k −= , chúng ta rút ra được tập hợp các phân lớp yếu hơn như sau: }|)({)( )()( kxhx MkM ∀=Γ (10) Và hM(x) tốt nhất trong số các phần tử thuộc Г(M-1) cho phân lớp mới mạnh hơn HM(x) = HM-1(x)+ hM(x) được cho trong biểu thức (3) trong số các hτ ∈ Г(M-1) . KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 27 Bảng 1-Thuật toán Adaboost Sau đây là ví dụ minh họa cho thuật toán AdaBoost: Thuật toán AdaBoost: 0. Đầu vào (1) Tập Z = {(x1, y1), .., (xN, yN)} với: N = a + b a là số mẫu thuộc phân lớp yi = +1 b là số mẫu thuộc phân lớp yi = -1 (2) Số lớp yếu tối đa Mmax sẽ được kết hợp. 1. Khởi tạo giá trị ai 2 1)0( =ω với các mẫu thuộc lớp yi = +1 bi 2 1)0( =ω với các mẫu thuộc lớp yi = -1 M = 0 2. Suy diễn tiến While M < Mmax (1) M Å M + 1 (2) Chọn hm dựa theo biểu thức (4) (3) Cập nhật )(Miω Å exp[-yiHM(xi)] và chuẩn hóa )(Miω để 1)( =∑i Miω 3. Đầu ra ])([)( 1∑ == Mm m xhsignxH KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 28 Hình 5-Hình vẽ minh hoạ thuật toán AdaBoost 3.4. Bộ dò tìm phân tầng AdaBoost Với một bộ dò tìm c do phương pháp AdaBoost huấn luyện được, ta có thể dò tìm với một độ chính xác nhất định và một tốc độ nhất định. Nếu như cần phải chính xác cao thì bộ dò tìm phải bao gồm nhiều đặc trưng, điều đó kéo theo tốc độ dò tìm sẽ giảm. Nếu sử dụng bộ dò tìm kết hợp F={ci} với nhiều bộ dò tìm cơ bản fi khác nhau cũng rơi vào tình trạng tương tự. Để có được độ chính xác cao, hoặc cần phải có số lượng lớn các bộ dò tìm, hoặc mỗi bộ dò tìm cần phải có nhiều đặc trưng, hoặc cả hai. Do đó cũng kéo theo tốc độ sẽ giảm. Một hướng khắc phục nhược điểm này là bộ dò tìm phân tầng T={ti}. Bộ dò tìm phân tầng bao gồm nhiều tầng, mỗi tầng ti = {cj} là một bộ dò tìm kết hợp với số lượng các bộ dò tìm khác nhau nên có tốc độ và độ chính xác khác nhau. Khi dò tìm tất cả các khuôn mặt trong ảnh, tất cả các cửa sổ con W0={wi,j,s} với các kích thước s khác nhau tại các tọa độ (i,j) sẽ được kiểm tra xem có phải là mặt người hay KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 29 không. Qua mỗi tầng ti, Wi = ti(Wi-1) trong đó |Wi|<<|Wi-1| do qua mỗi tầng, các cửa sổ không phải ứng viên sẽ bị loại sớm. Điều này cho phép chúng ta xây dựng các tầng sao cho, càng về sau độ phúc tạp (số lượng các bộ dò tìm cơ bản với các đặc trưng) càng lớn trong khi các tầng càng thấp thì độ phức tạp càng đơn giản và phải loại được nhiều ứng viên càng tốt nhưng tỷ lệ loại sai phải thấp. Hình 6-Hình vẽ minh hoạ bộ dò tìm phân tầng Xét mỗi tầng tk = {ci} ta có tỷ lệ loại sai của tk được tính như sau: ∏ = = K i ifF 1 trong đó fi chính là tỷ lệ loại sai ứng với bộ dò tìm ci và K chính là số bộ dò tìm của tầng tk. Tương tự, độ chính xác của tầng tk được tính như sau : ∏ = = K i idD 1 trong đó di là độ chính xác của ứng với bộ dò tìm ci. Đồng thời cũng với cách tính này, ta có thể tính được độ chính xác của toàn bộ các tầng T={ti} là ∏∏∏ = == == || 1 || 1 || 1 T i t j i j T i i i cDG Vậy khi cho trước một tỷ lệ loại sai D và độ chính xác là F, ta có thể huấn luyện tầng bộ phân loại t sao cho t có tỷ lệ loại sai là D và đô chính xác là F. Và lặp KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 30 lại quá trình huấn luyện tầng ta được bộ huấn luyện gồm nhiều tầng với độ chính xác G hoặc số tầng n như mong muốn. Dưới đây là thuật toán huấn luyện một tầng với tỷ lệ loại sai f và độ chính xác d cho trước: KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 31 Bảng 2-Thuật toán huấn luyện bộ dò tìm phân tầng 0. Đầu vào: f (tỉ lệ nhận sai mẫu dương tối đa chấp nhận được) d (tỉ lệ nhận đúng tối thiểu trong lớp) Ftarget (tỉ lệ nhận sai mẫu dương) P=tập mẫu dương N=tập mẫu âm 1. Khởi tạo: F0=1.0 D0=1.0 i=0 2. Trong khi (Fi>Ftarget) i Å i + 1 ni = 0; Fi = Fi-1 trong khi (Fi > f × Fi-1 ) ni = ni + 1 Sử dụng P và N để huấn luyện một phân loại H với ni đặc trưng, dùng Adaboost Thêm bộ phân loại hiện thời vào C Tính Fi và Di cho bộ phân loại C hiện thời trên tập hợp lệ Giảm ngưỡng cho lớp thứ i cho đến khi bộ phân loại C hiện thời đạt tỉ lệ dò tìm tối thiểu là d × Di-1 (điều này cũng ảnh hưởng Fi) N Å ∅ Nếu Fi > Ftarget thì định giá bộ dò tìm C hiện thời trên tập ảnh không phải mặt người và đưa các mẫu dò tìm bị lỗi vào tập N 3. Đầu ra: bộ dò tìm đa tầng C KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 32 3.5. Dò tìm khuôn mặt với AdaBoost 3.5.1. Huấn luyện bộ dò tìm khuôn mặt ¾ Dữ liệu huấn luyện : cơ sở dữ liệu CBCL của trường đại học MIT gồm 2.429 mặt người (nhìn thẳng), 4.548 không phải mặt người. ¾ Tập hợp các đặc trưng : FEA = {feai} trong đó feai sẽ rơi vào một trong các cách sau với các kích thước khác nhau tại các vị trí khác nhau: (ước tính có trên 50.000 đặc trưng) Hình 7-Hình vẽ các đặc trưng Haar-let được sử dụng ¾ Chọn số tầng và kích thước của sổ khuôn mặt: 3 bộ tham số thử nghiệm : o 25 tầng với kích thước của sổ (24x24) o 22 tầng với kích thước cửa sổ (20x20) o 20 tầng với kích thước của sổ (20x20) ¾ Tiến hành tiền xử lý tập ảnh huấn luyện bằng các phương pháp histogram và nhận dạng biên CANNY. ¾ Áp dụng thuật toán huấn luyện bộ phân tầng trên ứng với 3 tham số trên. 3.5.2. Quá trình dò tìm khuôn mặt KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 33 Việc dò tìm khuôn mặt trong ảnh qua bộ phân tầng đã huấn luyện gặp một vấn đề là số sửa sổ với các kích thước khác nhau quá lớn. Để khắc phục vấn đề này, phương pháp dò theo kiến trúc tháp được áp dụng như sau: xét ảnh s kích thước (wxh) , step = 0 , hệ số co scale = 1.2 ¾ Lặp trong khi kích thước (w x h) còn lớn hơn cửa sổ ảnh mặt người huấn luyện (w0 x h0) o Duyệt toàn bộ các vị trí (x,y) cửa sổ với kích thước (w0 x h0) , với mỗi vị trí tiến hành: ƒ Áp dụng bộ dò tìm phân tầng để xác định có phải mặt người hay không ƒ Nếu là mặt người tại vị trí (x,y) thì thực tế mặt người tại vị trí (x*scalestep, y*scalestep) và kích thước cửa sổ là (w0*scalestep, h0*scalestep) o Gán w1 = w / scale và h1 = h / scale o hu nhỏ ảnh từ kích thước (w x h) đến (w1 x h1) o Gán w = w1 và h = h1 o step = step + 1 Nhận xét : ¾ Hệ số co scale quyết định độ mịn của các cửa sồ dò tìm, nếu như scale càng nhỏ (≥1 ) thì càng có nhiều cửa sổ dò tìm nên càng chính xác hơn. ¾ Áp dụng thuật toán dò theo kiến trúc tháp như trên ta có thể dò tìm tất cả các khuôn mặt ở tất cả các vị trí, song kích thước dò tìm ở mỗi bước như sau : ƒ Bước 1 : kích thước từ (w0, h0) đến (w0*scale,h0*scale) ƒ Bước 2 : kích thước từ (w0*scale,h0*scale) đến (w0*scale2,h0*scale2) ƒ …………. KH OA C NT T – Đ H KH TN Dò tìm khuôn mặt nhanh theo phương pháp AdaBoost 34 ƒ Bước n : kích thước từ (w0*scalen-1,h0*scalen-1) đến (w0*scalen,h0*scalen) ƒ …………. 3.6. Đánh giá và hướng phát triển 3.6.1. Đánh giá 3.6.1.1. Ưu điểm ¾ Phương pháp cho độ chính xác tương đối (trên 90%) nhưng lại dò tìm khá nhanh, thích hợp trong việc dò tìm trong thời gian thực, trong video. ¾ Thích hợp với việc huấn luyện dữ liệu bị nhiễu. ¾ Phương pháp chọn trích đặc trưng thực hiện khá nhanh. 3.6.1.2. Khuyết điểm ¾ Thuật toán huấn luyện quá chậm do tổ hợp các bộ phân loại yếu rất lớn. ¾ Chỉ dò tìm được các khuôn mặt nhìn thẳng và góc quay nhỏ ¾ Không ít các tính chất của AdaBoost mang tính chất nhận đính và chưa được chứng minh chặt chẽ. 3.6.2. Hướng phát triển 3.6.2.1. Về mặt thuật toán học ¾ Kết hợp các phương pháp khác như SVM ở tầng cuối cùng để tăng độ chính xác. ¾ Sử dụng các mô hình cải tiến của AdaBoost như FloatBoost để tăng độ chính xác. 3.6.2.2. Về mặt thuật toán học ¾ Dò tìm khuôn mặt trong thời gian thực kết hợp theo vết khuôn mặt trong các đoạn video – camera để tăng độ chính xác mà giảm thời gian dò tìm. KH OA C NT T – Đ H KH TN 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 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ộ 4.1. Sơ lược toán đại số tuyến tính trong thống kê 4.1.1. Vector riêng, trị riêng và sự chéo hoá của ma trận Xét một toán tử tuyến tính f trong không gian Rn với các vector cơ sở: ei = [0...1...0]T (với giá trị 1 nằm tại vị trí thứ i) (1) Toán tử tuyến tính này sẽ được biểu diễn bởi một ma trận vuông T kích thước n×n. Nếu tồn tại một đại lượng vô hướng λ và một vector x, x ≠ 0, sao cho thỏa điều kiện : f(x) = λx (2) hay T*x = λx. (3) Khi đó λ được gọi là trị riêng của f , và vector x được gọi là vector riêng của f, hay của T, ứng với trị riêng λ. Ma trận T với kích thước n×n sẽ có tối đa n trị riêng và n vector riêng tương ứng. Một ma trận T khả nghịch đảo sẽ có đủ n trị riêng (kể cả trị riêng bội) và n vector riêng tương ứng. Nếu tồn tại một cơ sở trong không gian Rn sao cho ma trận T biểu diễn trong cơ sở đó có dạng chéo (các phần tử ngoài đường chéo bằng 0) thì ma trận T (biểu diễn trong không gian Rn với các vector cơ sở ei nêu trên) sẽ chéo hóa được. Ví dụ: Khảo sát trên không gian R5 với ma trận chéo 5×5 KH OA C NT T – Đ H KH TN 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ộ 36 T = 1 2 3 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 λ λ λ λ λ ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ Giả sử C là ma trận các vector cơ sở mới {ui}được biểu diễn trong cơ sở {ei}. Ở đây, ma trận T được chuyển từ cơ sở {ei} sang cơ sở mới {ui} nên ma trận chuyển đổi cơ sở từ {ei} sang {ui} cũng là C. Nếu T chéo hóa được tức là tồn tại ma trận C khả nghịch (tức là C tạo được một cơ sở trong Rn) sao cho : Tc = C-1 T C (4) có dạng chéo. Nếu ta có C là một ma trận có các cột là các vector cơ sở đã được chuẩn hóa của không gian Rn thì CT = C-1, khi đó từ (4.1.4 ) ta có thể suy ra : Tc = CT T C. (5) Ta có thể tìm được ma trận C để chéo hóa một ma trận T bằng cách tìm các vector riêng của ma trận T. Lúc đó ma trận C chính là ma trận có các cột là các vector riêng của T. 4.1.2. Kì vọng và phương sai trong thống kê đa chiều 4.1.2.1. Kì vọng Đối với thống kê đa chiều, mỗi một mẫu thống kê là một vector đa chiều. Giả sử ta có một biến ngẫu nhiên X trong không gian tuyến tính n chiều. X = [x1 x2 ... xn]T (6) Khi đó kỳ vọng của biến ngẫu nhiên X cũng là một vector n chiều, trong thống kê, kỳ vọng E[X] của một biến ngẫu nhiên X có thể được ước lượng bằng trung bình mẫu X , và được tính bằng công thức: X = ∑ = M i iXM 1 1 . (7) Trong đó M là tổng số mẫu có trong thống kê. KH OA C NT T – Đ H KH TN 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ộ 37 4.1.2.2. Ma trận hiệp phương sai Giá trị phương sai trong thống kê một chiều là độ đo mức độ phân tán của một biến ngẫu nhiên xung quanh giá trị kỳ vọng. Trong thống kê đa chiều, khái niệm này được mở rộng thành ma trận hiệp phương sai : TXEXXEXEC ]][]][[[ −−= (8) Ma trận hiệp phương sai là một ma trận đối xứng. Mỗi phần tử cij của ma trận là hiệp phương sai giữa hai thành phần xi và xj trong vector X. Nếu cij = 0 ta nói hai thành phần xi và xj là độc lập hay không phụ thuộc lẫn nhau. Nếu cij ≠ 0, ta nói xi và xj không độc lập hay chúng phụ thuộc lẫn nhau. Trong thống kê, ma trận hiệp phương sai được tính bằng công thức như sau : C = ∑ = −−− M i T ii XXXXM 1 ))(( 1 1 (9) 4.2. Phương pháp phân tích thành phần chính (Principal Component Analysis hay PCA) 4.2.1. Yêu cầu ¾ Vấn đề được đặt ra khi thực hiện việc nhận dạng trong không gian đa chiều (với số lượng chiều rất lớn) ¾ Sẽ đạt được một sự cải thiện đáng kể bằng cách sắp xếp dữ liệu vào một không gian đa chiều, nhưng với số chiều nhỏ hơn. → ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = Na a a x ... 2 1 giảm chiều ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ =→ Kb b b y ... 2 1 4.2.2. Trích đặc trưng bằng phương pháp PCA KH OA C NT T – Đ H KH TN 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ộ 38 Mục tiêu của phương pháp PCA là giảm số chiều của một tập các vector sao cho vẫn đảm bảo được tối đa thông tin quan trọng nhất của tập dữ liệu huấn luyện . Có thể nói phương pháp PCA tìm cách giữ lại những thành phần thống kê quan trọng nhất của tập mẫu. Giả sử ta cần giảm số chiều của tập mẫu huấn luyện từ n chiều NN vavavax +++= ...2211 v1, v2, ..., vN là cơ sở trong không gian N chiều xuống còn k chiều (k<n ) KKubububy +++= ...2211 u1, u2, ..., uK là cơ sở trong không gian K chiều nghĩa là ta cần tìm một ánh xạ từ không gian n chiều xuống không gian nhỏ hơn chỉ có k chiều (k<n). Gọi x là một vector trong không gian n chiều, y là một vector trong không gian k chiều. Ta có trung bình bình phương lỗi MSE (mean square error) ||x-y|| khi loại bỏ một số thành phần trong x để thu được y sẽ bằng tổng phương sai của những thành phần bị loại bỏ. Phương pháp PCA sẽ tìm một phép biến đổi tuyến tính T, thỏa : y = T*x T là ma trận kxn (10) sao cho trung bình bình phương lỗi là bé nhất. Nnatatatb 12121111 ...+++= Nnatatatb 22221212 ...+++= …. Nknkkk atatatb +++= ...2211 hay y=Tx trong KH OA C NT T – Đ H KH TN 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ộ 39 ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = KNKK N N ttt ttt ttt T ... ............ ... ... 21 22221 11211 Gọi M là vector trung bình của các vector x trong tập huấn luyện X. ∑ = = M k kxM M 1 1 , M là số phần tử trong tập huấn luyện (11) Gọi C là ma trận hiệp phương sai của các các phần tử trong tập X. ∑ = −−−= M k T kk MxMxM C 1 ))(( 1 1 , C là ma trận đối xứng nxn (12) Người ta chứng minh được rằng nếu T là một ma trận mà mỗi hàng là một vector riêng của C và m vector riêng này (m hàng của ma trận T) ứng với m trị riêng lớn nhất thì T chính là phép biến đổi tuyến tính thỏa mãn điều kiện để MSE nhỏ nhất. Gọi Φ là ma trận vuông n×n mà mỗi cột là một vector riêng của C đã được chuẩn hóa với phép biến đổi : y = ΦT*x y = (y1, y2, ..., yn) (13) được gọi là phép biến đổi Hotelling. Xét theo quan điểm của nhận dạng thì mỗi thành phần yi của vector y được xem như là một đặc trưng của vector mẫu x. Các đặc trưng này là các đặc trưng độc lập với nhau vì ma trận hiệp phương sai của y là Cy = ΦT C Φ (14) là một ma trận chéo (đã đề cập tới trong phần : Vector riêng, trị riêng và sự chéo hóa ma trận). Tóm lại, phương pháp phân tích thành phần chính ánh xạ một vector từ không gian n chiếu xuống không gian k chiều sẽ đi tìm các trị riêng và vector riêng KH OA C NT T – Đ H KH TN 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ộ 40 của ma trận hiệp phương sai C của tập X và giữ lại k vector riêng ứng với k trị riêng lớn nhất làm cơ sở cho không gian k chiều này. ¾ Sự diễn giải bằng hình học : o PCA chiếu dữ liệu theo hướng mà ở đó dữ liệu khác nhau nhiều nhất. o Những hướng này được xác định bằng các vector riêng của ma trận hiệp phương sai o Số lượng các trị riêng tương ứng với sự khác biệt của dữ liệu theo các hướng của vector riêng Hình 8-Hình vẽ minh hoạ hướng của véctơ riêng o Như chúng ta đã thấy ở trên rằng vector gốc x có thể được xây dựng lại bằng cách sử dụng những thành phần chính của nó : ∑ = =− K i iiubxx 1 ˆ hay xubx K i ii += ∑ =1 ˆ o Điều đó cho thấy rằng cơ sở trong không gian có số chiều ít được dựa trên những thành phần chính sẽ làm tối thiểu hóa lỗi trong quá trình xây dựng lại : xxe ˆ−= o Điều đó cho thấy rằng số lỗi sẽ tương đương : KH OA C NT T – Đ H KH TN 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ộ 41 ∑ += = N Ki ie 1 2/1 λ 4.2.3. Kỹ thuật trích đặc trưng bằng PCA Giả sử Nxxx ,...,, 21 là các vector Nx1 ¾ Bước 1 : ∑ = = M i ixMx 1 1 ¾ Bước 2: trừ hai giá trị trung bình xxii −=Φ ¾ Bước 3: tạo thành ma trận NxM [ ]MA ΦΦΦ= ...21 sau đó tính T M n Tnn AAMC ∑= =ΦΦ= 11 ¾ Bước 4: tính tóan các trị riêng của C Nλλλ >>> ....21 ¾ Bước 5: tính tóan các vector riêng của C Nuuu ,....,, 21 Vì C đối xứng (NxN) nên u1, u2, . . . , uN hợp thành một cơ sở (bất kể một vector x nào hay thậm chí (x x) cũng đều có thể viết dưới dạng một tổ hợp tuyến tính của các vector riêng ) ∑ = =+++=− N i iiNN ububububxx 1 2211 ... ¾ Bước 6 (bước giảm số chiều): chỉ giữ lại những thuộc tính tương ứng với các trị riêng lớn nhất ∑ = =− K i iiubxx 1 ˆ trong đó K<<N KH OA C NT T – Đ H KH TN 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ộ 42 Do đó, sự biểu diễn của xx −ˆ trong Kuuu ,....,, 21 là: ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ Kb b b ... 2 1 Phép biến đổi tuyến tính KN RR → nhằm làm giảm số chiều sẽ là : )()( ...... 2 1 2 1 xxUxx u u u b b b T T K T T K −=− ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ = ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ ™ Lưu ý : Khi số lượng mẫu M trong tập X nhỏ hơn số chiều n, thay vì tính trực tiếp các vector riêng từ ma trận hiệp phương sai C, ta có thể tính các vector riêng theo phương pháp sau : 9 Bước 1 : Tính ma trận kích thước M×M, C’ như sau : C’ = YT.Y với Yn×M = [x1, x2, ..., xM] mỗi cột của ma trận là một phần tử xi, i=1..m 9 Bước 2 : Tính M vector riêng EMi và các trị riêng tương ứng của ma trận C’. Chọn m vector riêng ứng với m trị riêng lớn nhất để tiếp tục bước 3. 9 Bước 3 : Chiếu các vector riêng M chiều này về lại không gian n chiều của các mẫu xi bằng cách như sau : Eni = ∑ = M k kk xEM 1 (15) KH OA C NT T – Đ H KH TN 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ộ 43 Các vector Eni thu được chính là các vector riêng cần tìm của ma trận C. ™ Cách xác định số thành phần chính hiệu quả nhất − Có hai phương pháp hữu ích giúp cho chúng ta lấy số lượng thành thành phần chính sao cho hiệu quả . Tất cả hai phương pháp này đều dựa trên mối quan hệ giữa các giá trị đặc trưng. ¾ Sắp xếp lại các giá trị đặc trưng tìm được theo thứ tự giảm dần về mặt giá trị (1,eigenvalue[1]), (2,eigenvalue[2]), …,(p,eigenvalue[p]) và Thứ tự này vẫn đảm bảo được thứ tự của các vector đặc trưng tương ứng. Theo dõi sự biến thiên của chuỗi giá trị đặc trưng vừa được xếp lại, khi sự biến thiên này tiến đến một điểm ngưỡng (thông thường xấp xỉ bằng không). Thông thường đó chính là lúc mà ta chọn được đủ số lượng thành phần chính cần thiết . ¾ Để chọn K, sử dụng tiêu chuẩn sau đây : nguongN i i K i i > ∑ ∑ = = 1 1 λ λ Với phương châm làm sao số lượng thành phần chính là thấp nhất đủ để giải thích khả năng phân tán tập mẫu học thành các lớp mẫu riêng cần thiết nhất. 4.3. Phương pháp PCA toàn cục và cục bộ 4.3.1. Phương pháp PCA toàn cục Phương pháp PCA toàn cục chính là phương pháp trích đặc trưng truyền thống trên toàn bộ dữ liệu đã cho. Kỹ thuật trích tham khảo trong phần 4.2.3 4.3.2. Phương pháp PCA cục bộ KH OA C NT T – Đ H KH TN 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ộ 44 Giả sử ta có ảnh tập ảnh S = niis 1}{ = gồm n ảnh với kích thước 30x30 cần trích đặc trưng. Phương pháp PCA cục bộ cho phép ta trích các đặc trưng cục bộ trong các thành phần của ảnh. Với mỗi ảnh si ∈ S, ta chia ảnh si ra làm 9 ảnh con 9 1}{ =jijs kích thước 10x10. Với mỗi i ∈ [1,9] ta tiến hành áp dụng phương pháp PCA cho từng bộ ảnh con nkkis 1}{ = . Đến đây có hai hướng chọn đặc trưng khác nhau cho tập S: ¾ Hướng độc lập : vai trò của 9 ô trong mỗi ảnh là như nhau, do đó, mỗi ô trong 9 ô có quyền chọn đặc trưng riêng cho mình một cách độc lập. Chẳng hạn, mỗi ô trong 9 ô sẽ chọn 10 đặc trưng, do đó sau khi huấn luyện tập S, ta được 9x10 đặc trưng. ¾ Hướng lệ thuộc : hướng này đòi hỏi số đặc trưng n cho ảnh toàn cục phải được biết trước, ta chọn từ trên xuống các đặc trưng của các véctơ đặc trưng của tất cả 9 ô. Tiêu chuẩn chọn dựa trên giá trị đặc trưng của từng đặc trưng. Nhận xét : - Dễ dàng nhận thấy hướng lệ thuộc cho kết quả tốt hơn do có thể một số ô, các đặc trưng không quan trọng. Chẳng hạn trên khuôn mặt người, ô ngay đỉnh trán thường có ít đặc trưng hơn ô có chứa mũi, mắt hay miệng. - Tuy nhiên, việc chọn đặc trưng theo hướng phụ thuộc sẽ gặp phải các vấn đề các giá trị đặc trưng của các ô ngang hàng, tiêu chí về số lượng n phải được nới lỏng và xét đến, vì nếu ta bỏ sót các đặc trưng có cùng giá trị đặc trưng, kết quả sẽ không tốt. 4.4. Đánh giá 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 KH OA C NT T – Đ H KH TN 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ộ 45 ¾ Khi lấy số đặc trưng càng về sau thì khả năng biến động càng thấp , có nghĩa nối quan hệ giữa các phần tử càng cao , thì sự giao nhau giữa các lớp mẫu trong tập mẫu càng lớn ¾ Nhưng nếu lấy không đủ số lượng thành phần chính , thì khả năng phân tán của tập mẫu càng cao (Có thể tăng vượt ngoài số lớp mẫu cần thiết trong tập mẫu ) 4.4.2. So sánh phương pháp PCA toàn cục và PCA cục bộ ¾ Rõ ràng phương pháp PCA cục bộ cho tốc độ tính toán nhanh hơn. Việc nhân ma trận kích thước 2n với ma trận kích thước 2nm∗ sẽ chậm hơn nhiều so với nhân s ma trận kích thước 2)( s n với 2 ⎟⎠ ⎞⎜⎝ ⎛∗ s n s m vì 44 42 2)(* nm s nm s n s m s ns ∗<∗=⎟⎠ ⎞⎜⎝ ⎛∗∗ . Do đó việc nhận dạng sử dụng PCA cục bộ trích đặc trưng sẽ cho tốc độ xử lý nhanh hơn. ¾ Xét về đặc trưng thì : PCA cục bộ hướng lệ thuộc cho kết qua tốt nhất, còn PCA cục bộ hướng độc lập cho kết quả cao hơn PCA toàn cục một chút, song thường chênh lệch không nhiều. KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 46 Chương 5 Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 5.1. Sơ lược lý thuyết SVM 5.1.1. Giới thiệu SVM là phương pháp nhận dạng do Vladimir N. Vapnik đề xuất năm 1995. SVM là phương pháp nhận dạng dựa trên lý thuyết học thống kê ngày càng được sử dụng phổ biến trong nhiều lĩnh vực, đặc biệt là lĩnh vực phân loại mẫu và nhận dạng mẫu. Đồng thời có nhiều tính năng ưu việt so với các phương pháp cổ điển khác: dễ dàng xử lý, xử lý với tính ổn định cao trên dữ liệu phức tạp, có thể có số chiều lớn và quan trọng hơn cả là khả năng xử lý tổng quát. Chi tiết về phương pháp SVM có thể tham khảo các bài báo và luận văn trong phần tham khảo. Dưới đây là phần tóm tắt sơ lược về lý thuyết SVM nhằm làm nền tảng để nói đến SVM mờ (Fuzzy SVM) ở phần sau. 5.1.2. Sơ lược lý thuyết SVM 5.1.2.1. SVM tuyến tính Giả sử cho tập học niii yxS 1},{ == (1) trong đó xi ∈ Rn và yi ∈ {+1,-1}. Mục đích của SVM là tìm ra siêu mặt phân cách thỏa 1≥+bxw iT khi 1+=iy 1−≥+bxw iT khi 1−=iy (2) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 47 trong đó w ∈ Rn và cũng là vectơ pháp tuyến của siêu mặt. Nếu như các thành phần của tập học S thỏa bất phương trình (2) thì ta nói đây là trường hợp phân cách tuyến tính. Trong việc huấn luyện siêu mặt, SVM tìm cách cực đại khỏang cách bờ ρ giữa hai lớp với || 2 w =ρ . Do đó trong trường hợp tuyến tính, việc tìm siêu mặt phân cách cũng chính là giải hệ sau: cực tiểu ww Tw 2 1)( =Φ (3) với ràng buộc 1)( ≥+bxwy iTi , i=1,2,…,n (4) Nếu như bất phương trình (2) không đúng với một số phần tử trong tập học, ta nói đây không phải là trường hợp phân cách tuyến tính. Trong trường hợp này ta bờ mặt phân cách là “mềm”( soft margin) nếu như có một vài phần tử không thỏa (2) như trên. Để giải quyến trường hợp này, tập nii 1}{ =ξ được thêm vào (2) như sau: nibxwy ii T i ,....,2,1,1)( =−≥+ ξ (5) và ξi được gọi là các biến slack (lỏng). Khi 0<ξi <1 thì các điểm rơi đúng vào hần ngăn cách của bờ ngăn cách. Khi có lỗi xuất hiện tức có điểm rơi vào bờ bên kia, ξi tương ứng sẽ lớn hơn 1. Do đó mục đích SVM bây giờ là tìm siêu phằng phân cách sao cho lỗi phân loại ít nhất và khoảng cách bờ lớn nhất. trong trường hợp không thể phân cách tuyến tính, bài toán trở thành: cực tiểu ∑ = +=Φ n i iT Cwww 12 1),( ξξ (6) với điều kiện (iy 1) ≥+ bxw iT nii ,....,2,1, =−ξ (7) và ni ,...,2,1,0 =≥ξ (8) trong đó C chính là tham số do người dùng chọn cân bằng giữa độ phức tạp của hệ và số lượng lỗi, và C càng lớn thì tỉ lệ lỗi sẽ càng thấp. Một cách để giải quyết bài toán là dùng hàm Largange. Có hai lý do cho điều này. Thứ nhất là ràng buộc (7 - 8) sẽ được thế bằng ràng buộc trên hệ số nhân KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 48 Lagrange, để dễ làm việc hơn. Thứ hai là dữ liệu huấn luyện sẽ chỉ xuất hiện dưới dạng phép nhân vô hướng giữa các vector. Điều này cho phép tổng quát hoá cho trường hợp phi tuyến. Đưa ra các hệ số nhân Lagrange không âm αi, và βi , cho các ràng buộc bất đẳng thức (7-8). Bài toán đối ngẫu trở thành : cực đại ∑ ∑∑ = = = −= n i n i n j j T ijijii xxyyQ 1 1 12 1)( αααα (9) với ràng buộc 0 1 =∑ = n i ii yα (10) và niCi ,...,2,1,0 =≤≤ α (11) Trong bài toán đối ngẫu hàm lượng giá Q(α) cực đại chỉ phụ thuộc vào dữ liệu dưới dạng tích vô hướng { }n jijTi xx 1),( = . Do đó các hệ số nhân Lagrange có thể tính được dựa trên các ràng buộc (10-11). Điều kiện Karush-Kuhn-Tucker (KKT) có vai trò quan trọng đối với bài toán tối ưu ràng buộc. Với bài toán trên, điều kiện KKT có thể phát biểu: [ ] nibxwy iiTii ,...,2,1,01)( ==+−+ ξα (12) niii ,...,2,1,0 ==ξβ (13) trong đó βi = C - αi Có hai dạng tham số αi, nếu như 0<αi ≤C thì mẫu tương ứng là véctơ hỗ trợ. Véctơ lời giải cho bài toán chính là véctơ xác định bởi: ∑ = = s N i iii xyw 1 0 α (14) trong đó Ns chính là số lượng các véctơ hỗ trợ. Tuy nhiên trong trường hợp 0<αi <C chúng ta có ξi = 0 theo phương trình (13) của điều kiện KKT. Do đó có thể lấy điểm huấn luyện bất kỳ thỏa 0 < αi < C để dùng công thức (12) (với ξi = 0) để tính b0. Cuối cùng có thể lấy trung bình b0 trên toàn tập mẫu S. KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 49 Một khi (w0,b0) được xác định, ta có hàm quyết định chính là ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ += ∑ = sN i T iii bxxysignxg 1 0)( α (15) đồng thời siêu mặt phân cách chính là g(x) = 0. Trường hợp khác xảy ra nữa là khi αi =C (ξi>0 có thể tính được bằng(12)) và αi = 0 (mẫu i đã được phân loại đúng). 5.1.2.2. SVM phi tuyến Trong trường hợp phi tuyến, ta chỉ cần ánh xạ véctơ dữ liệu vào không gian đặc trưng có số chiều cao hơn nhiều. Bằng cách sử dụng hàm ánh xạ MRx ∈)(ϕ , trong đó M>N, chúng ta có thể xây dựng siêu mặt phân cách trong không gian mới này. Hàm xử lý chính tích vô hướng K(x,xi) ánh xạ không gian phi tuyến vào không gian đặc trưng )()(),(),( i T ii xxxxKxxK ϕϕ== (16) Do đó bài toán đối ngẫu trở thành Cực đại ∑ ∑ ∑ = = = −= n i n i n j jijijii xxKyyQ 1 1 1 ),( 2 1)( αααα (17) với cùng ràng buộc (10-11). Điều kiện duy nhất chính là hàm xử lý chính K(x,xi) phải thỏa điều kiện Mercer(có thể tham khảo điều kiện Mercer trong các bài báo và luận văn về SVM). Bằng cách sử dụng các hàm xử lý chính, dữ liệu có thể được phân loại như sau (18) trong đó g(x) là hàm quyết định như sau ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= ∑ sN iii xxKysignxg ),()( α (19) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 50 5.2. FSVM – SVM mờ (Fuzzy SVM) 5.2.1. FSVM 5.2.1.1. Các vấn đề nảy sinh của SVM Với SVM, quá trình huấn luyện khá nhạy cảm với các mẫu cách qua xa lớp. Nếu như hai lớp có thể phân cách tuyến tính thì SVM có thể tìm ra siêu mặt phân cách mà không có mẫu nào bị phân loại sai bất kể hai hai tập mẫu có độ đo compact nhỏ đến mức nào. Tuy nhiên xét trường hợp hai lớp không thể phân cách tuyến tính, việc chọn đúng giá trị C có ý nghĩa khá quan trọng. Vế phải của (6) quyết định tính hiệu quả của C. C càng lớn thì lỗi phân cách mẫu càng nhỏ nhưng ngược lại C càng nhỏ thì càng bỏ qua nhiều các mẫu phân cách sai, song bờ phân cách càng lớn. dù C lớn hay nhỏ thì giá trị C vẫn cố định trong quá trình huấn luyện. Do đó các mẫu được huấn luyện ngang nhau, nên cuối cùng bớ phân cách sẽ nhạy cảm với những mẫu vượt biên. Việc xem vai trò các mẫu ngang nhau sẽ dẫn đến việc huấn luyện SVM “quá thích nghi” (overfit) Hình 9-hình vẽ minh họa nhược điểm về điểm vượt của SVM Trong hình trên là ví dụ của việc huấn luyện mẫu hai chiều không thể phân cách tuyến tính được. vùng ít quan trọng hơn là vùng chứa mẫu không tham gia vào việc hình thành các véctơ hỗ trợ thỏa mãn phương trình (2). Ngược lại những mẫu KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 51 tham gia vào hình thành véctơ hỗ trợ sẽ thuộc vùng quan trọng hơn. Với cùng giá trị C, nếu như tồn tại các mẫu vượt biên của lớp 1, siêu mặt phân cách sẽ hướng về lớp 2. Do đó độ dốc của siêu mặt cũng thay đổi do tập các véctơ hỗ trợ thay đổi theo phương trình (14). Điều đó kéo theo việc nhận dạng các mẫu của lớp 2 có nhiều lỗi hơn do việc huấn luyện “quá thích nghi”(overfit) gây ra bởi các phần tử vượt biên. 5.2.1.2. Mờ hóa tập dữ liệu Như đã thấy, việc xem các mẫu ngang hàng nhau có thể gây lỗi cho SVM như trên. Do đó ý tưởng của FSVM là tương ứng với mỗi mẫu xi, ta gọi px(xi) là xác xuất xi là mẫu vượt biên, ta có thể sửa lại hàm lỗi thành i n i ix xp ξ∗∑ =1 )( . Tuy nhiên với từng mẫu trong tập mẫu ban đầu, nếu được với một giá trị µi là độ đo thành viên. Khi đó tương ứng với xác xuất gây lỗi chính là độ đo thành viên µi xác độ gắn kết thành viên với cả tập mẫu ban đầu. Tập mẫu ban đầu trở thành tập mờ Sf như sau : { }niiiif yxS 1,, == µ (20) Với các mẫu dương(yi = +1) giá trị độ đo thành viên được gán là µi+ và ngược lại là giá trị µi-. Chúng được gán độc lập với nhau. 5.2.1.3. FSVM Giả sử ta đã có tập mẫu đã mờ hóa, ta bắt đầu bằng việc hình thành hàm lượng giá. FSVM vừa cực đại bờ ngăn cách và cực tiểu lỗi ngay cả với các mẫu vượt biên. Không giống như SVM, FSVM giảm ảnh hưởng của các mẫu ít quan trọng hơn bằng độ đo thành viên. Bài toán ràng buộc của FSVM trở thành: Cực tiểu ∑ = +=Φ n i i m i T Cwww 12 1),,( ξµµξ (21) với điều kiện nibxwy ii T i ,...,2,1,1)( =−≥+ ξ (22) ni ,...,2,1,0 =≥ξ (23) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 52 trong đó m là độ mờ của hàm lượng giá. Hàm Lagrange trở thành [ ]∑ ∑ ∑ = = = −+−+−+= n i n i n i iiii T iii m i T bxwyCwwbwQ 1 1 1 1)( 2 1),,,,,( ξβξαξµµβαξ (24) trong đó αi và βi là các hệ số nhân Lagrange không âm, việc giải các phương trình đạo hàm riêng Q theo w,b, và ξi sẽ cho ta kết quả, do đó ta có các phương trình sau: ∑ = =−=∂ ∂ n i iii xyww bwQ 1 0),,,,,( αµβαξ (25) ∑ = =−=∂ ∂ n i ii yb bwQ 1 0),,,,,( αµβαξ (26) 0),,,,,( =−−=∂ ∂ ii m i i CbwQ βαµξ µβαξ (27) Thay (25-26-27) vào (24), hàm Lagrange là hàm theo α , bài toán đối ngẫu trở thành Cực đại ∑ ∑∑ = = = −= n i n i n j jijijii xxyyQ 1 1 1 , 2 1)( αααα (28) Với điều kiện ∑ = = n i ii y 1 0α (29) niC mii ,...,2,1,0 =≤≤ µα (30) Dễ thấy sự khác biệt duy nhất giữa SVM và FSVM chính là chặn trên của hệ số nhân αi trong bài toán đối ngẫu. Nếu như với SVM, chặn trên cố định với giá trị hằng số C, thì FSVM linh động hơn với độ đo thành viên của từng mẫu. Độ đo của mẫu xi càng nhỏ thì vùng khả thi dọc theo trục αi càng hẹp. Cuối cùng điều kiện KKT của FSVM trở thành: [ ] nibxwy iiTii ,...,2,1,01)( ==+−+ ξα (31) niC ii m i ,...,2,1,0).( ==− ξαµ (32) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 53 5.2.2. Thuật toán mờ hóa dữ liệu Quá trình mờ hóa dữ liệu gồm hai bước chính theo hình vẽ sau. Truớc tiên, phải xác định được tập các mẫu vượt viên, gọi là mẫu vượt biên, tập còn lại là mẫu chính. Sau đó hai tập đuợc mờ hóa bằng độ đo thành viên. Điều đáng chú ý là việc xác định độ đo cho hai tập mẫu dương và mẫu âm được tiến hành độc lập với nhau. Cuối cùng kết hợp hai tập mờ của mẫu dương và mẫu âm lại, ta được tập mẫu đã mờ hóa. Tuy nhiên có thể áp dụng các hàm heuristic (kernel, KNN, SVM) để bỏ qua bước xác định mẫu vượt biên mà áp dụng cho mọi mẫu với hệ số khác nhau. Hình 10-Sơ đồ diễn tả cách mờ hoá tập học Gọi h(x) là một hàm heuristic sao cho h(xi) gần với µi, để xác định độ đo thành viên µi, ta sử dụng các luật mờ cho hàm heuristic như sau: Luật 1 : Nếu h(xi) > hc thì µi = 1 Luật 2 : Nếu hc ≥ h(xi) ≥ ht thì d tc t i hh hxh ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − −∗−+= )()1( σσµ Xác định tập mẫu vượt Mờ hóa tập mẫu vượt Mờ hóa tập mẫu chính s+ O+ M+ sf+ Xác định tập mẫu vượt Mờ hóa tập mẫu vượt Mờ hóa tập mẫu chính s- O- M- sf- s sf KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 54 Luật 3 : Nếu h(xi) < ht thì µi = σ trong đó hc và ht tương ứng là độ tin cậy và độ “bỏ đi”, σ chỉ mức độ tham gia của các phần tử vượt biên vào quá trình huấn luyện. Cả 4 tham số hc, ht, σ và d đều phải học từ tập mẫu. Hình 11-Đồ thị diễn tả 3 luật mờ xác định độ đo thành viên 5.2.2.1. Mờ hóa tập dữ liệu áp dụng KNN – ODM Phương pháp heuristic đơn giản nhất cho KNN. Hàm heuristic h(x) trong trường hợp KNN chính là số mẫu lân cận x và cùng lớp với x. Tham số cần học chính là số k láng giềng gần nhất. Một phương pháp khác phức tạp hơn là ODM cho kết quả phân cụm chính xác hơn KNN do đó độ đo được tính chính xác hơn. Dưới đây là phần trình bày về phương pháp ODM. 5.2.2.1.1. Xác định tập mẫu vượt Phương pháp xác định tập mẫu vượt sử dụng ở đây được Yi-Hung Liu đề xuất và đặt tên là ODM (outlier detection method) dựa trên các phương pháp SOM(self-organizing map) của Kohenen và gom cụm FCM(fuzzy-C-means). Việc h(x) hc ht σ 1 d=1 KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 55 áp dụng cho tập mẫu âm và tập mẫu dương là như nhau, do đó thuật toán ODM trình bày dưới đây dành cho mẫu dương. Gọi { } 1== Piic xX là tập mẫu dương (âm) với xi ∈ RN , thuật toán gồm các bước sau: ¾ Bước 1: Xây dựng tập đại diệnYc: Sau khi sử dụng SOM 1 chiều để cập nhật trọng số của nối đầy đủ các nút nhập và nút xuất, mỗi mẫu được ánh xạ vào một giá trị xác định bởi tiêu chuẩn cực tiểu khoảng cách Euclid sau: ljWxy jii ,...,2,1,minarg =−= (33) Quy tắc cập nhật trọng tại thời điểm t là : )]()()[()()()1( tWtxthttWtW jjj −+=+ η (34) trong đó η là hệ số học, h là hàm lân cận được thay đổi trong quá trình học, l là số nút xuất. Sau quá trình học, tập mẫu Xc được đại diện bởi tập piic yY 1}{ == với yi ∈ R. ¾ Bước 2: Xây dựng tập ảo Yv từ tập đại diện Yc : Chọn ngẫu nhiên tập ảo Yv (yv∈R) thỏa các điều kiện sau: o |Yv| = |Yc| o Yv ∩Yc = φ o Yv và Yc tách biệt đủ lớn (*) o Độ đo compact của Yv đủ lớn (**) Để tính độ tách biệt SI(*) và độ đo CI (**), ta dùng chỉ số mờ FI để ước lượng độ nhập nhằng của tập nội và tập ngoại được tính như sau: (35) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 56 trong đó y là tâm và A là tập bổ sung của A, với khoảng cách được chuẩn hóa trong khỏang[0,0.5] yy yy yyd jj i i − −= max.2 ),( (36) Hàm thành viên của A được định nghĩa là (37) Rõ ràng khi SI càng lớn và CI càng nhỏ thì độ tách biệt giữa Yv và Yc càng lớn. Do đó có thể căn cứ vào hai chỉ số trên để làm tiêu chuẩn chọn tập Yv. Cuối cùng hợp hai tập Yc và Yv thành tập Y cho bước kế tiếp. ¾ Bước 3 : Áp dụng thuật toán FCM (fuzzy C mean) để gom cụm tập Y FCM được sử dụng để tìm tâm vi của từng cụm và giá trị thành viên uij∈{0, 1} để diễn tả độ gán kết của phần tử yj với cụm thứ i ∑∑ == == p j j e ijep j ij i ciyu u v 2 12 1 ,...,2,1,)( )( 1 (38) pjci vy vy u c k e kj e ij ij 2..1,,...,1, )/1( )/1( 1 )1( 12 )1( 12 == − −= ∑ = − − (39) trong đó e là trọng số ảnh hưởng đến độ mờ của ma trận [uij]. Có 2 ràng buộc của giá trị uij pju c i ij 2,...,2,1,1 1 =∀=∑ = (40) ∑ = =∀<< p j ij cipu 2 1 ,...,2,1,20 (41) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 57 c là số cụm. Để tìm số cụm đáng tin cậy nhất trong các cụm, ta căn cứ vào chỉ số độ hỗn tạp phân hoạch H(U, e). Vì vậy, số cụm tốt nhất cbest được xác định bằng cách cực tiểu hóa độ hỗn tạp phân hoạch. })],(min[{minarg 12 2 cU p cbest cUHc Ω∈ − == (42) và độ hỗn tạp phân họach được định nghĩa như sau: ∑ ∑ = = = p j c i ijij uup cUH 2 1 1 ln 2 1),( (43) trong đó Ωc là tập các giải pháp tối ưu ứng với giá trị c. ¾ Bước 4 : Khử mờ các phân hoạch mờ Áp dụng luật sau : bestc i ijc uP 1 maxarg* = = (44) Không phụ thuộc vào phân hoạch ảo Pv, tập lớp Yc hình thành một tập phân hoạch }1,..,2,1|{ −== besti ciPP (45) ¾ Bước 5 : Quyết định tập chính lớn nhất Cho 1 1 1 maxarg − = = best c i im PP (46) (Tập chính lớn nhất có nhiều mẫu nhất) IF 2=bestc THEN 1 mPP = END ODM ← ELSEIF 2>bestc THEN Tạm thời bỏ phân hoạch chính lớn nhất 1mP KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 58 P = {Pi|i=1, 2, .., cbest-2} Khởi tạo : c*=cbest-2, q=1, r=0 Nhảy tới bước 6 END ¾ Bước 6 : Cho i c ii T PP * 1 maxarg = = (PT là phân hoạch tạm thời). Tìm những phân hoạch chính và những phân hoạch vượt như sau: IF qaPP amT ,...,1,./1 =≤ γ ,THEN r=r+1 },...,0|{ rbPP PP b oo T r o == = với ( 0 0 =oP ) ELSE q=q+1; },...,1|{; qaPPPP ammT q m === END Loại bỏ phân hoạch PT Gán },...,1|{,1 *** ciPPcc i ==−= Lặp bước 6 cho đến khi c* = 0. Sau đó dừng thuật toán ODM 5.2.2.1.2. Hàm thành viên Giá trị thành viên được tính dựa vào tầm quan trọng của các mẫu trong lớp chứa nó. Để có được tập mẫu mờ Sf, chúng ta xác định 2 hàm mờ dành cho tập chính và dành cho tập vượt. Nếu xi ∈ M thì độ đo thành viên so với tập chính được tính như sau: KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 59 Mx xx xx j jj i i ∈+− −−= , max 1 εµ (47) trong đó, || . || là khoảng cách Euclide, ε là một số dương đủ nhỏ và x là tâm của tập mẫu M. Đồng thời, độ đo µi của những mẫu thuộc tập chính thì thuộc khoảng [ε, 1]. Đối với những mẫu vượt Oxii ∈∀= ,σµ (48) trong đó, 0<σ<ε là số dương đủ nhỏ để giảm ảnh hưởng của các phần tử vượt trong quá trình huấn luyện FSVM. 5.2.2.2. Mờ hóa tập dữ liệu áp dụng phương pháp Kernel Các kernel K(xi,xj) thường được sử dụng bao gồm : ƒ Kernel RBF : ||||),( ji xxji exxK −−= γ (các mẫu dữ liệu nằm trên bề mặt siêu cầu của không gian đặc trưng.) ƒ Kernel Cosin : )()(),( jiji xxxxK Φ∗Φ= chỉ góc cosin giữa )( ixΦ và )( jxΦ Với mỗi hàm kernel K(xi,xj) ta tính được heuristic h(x) ∑ = = n j jijii xxKyyxh 1 ),()( (49) Đối với phương pháp Kernel, các tham số của Kernel phải được học, cách đơn giản nhất là huấn luyện và sử dụng chính bản thân FSVM để đánh giá cho h(x). Các bước bao gồm như sau: Bước 1 : Chọn hàm Kernel K(xi,xj) với thông số Kernel (gamma chẳng hạn). Bước 2 : Xây dựng h(x) dựa trên 49 Bước 3 : Học bộ tham số Kernel và với quá trình lặp như sau như sau: ƒ Thay đổi thông số Kernel (như gamma) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 60 ƒ Chọn ngẫu nhiên hc∈[0.1,1] > ht∈[0.1,1], d, 0<σ<1 ƒ Xây dựng tập độ đo thành phần {µi} cho tập mẫu X Luật 1 : Nếu h(xi) > hc thì µi = 1 Luật 2 : Nếu hc ≥ h(xi) ≥ ht thì d tc t i hh hxh ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − −∗−+= )()1( σσµ Luật 3 : Nếu h(xi) < ht thì µi = σ ƒ Sử dụng tập {µi} xây dựng FSVM, nếu hàm lỗi ∑ = ∗ n i ii 1 ξµ < ε ( quy định) thì dừng. 5.2.2.3. Mờ hóa tập dữ liệu áp dụng phương pháp SVM ¾ Bước 1: Huấn luyện SVM phi tuyến: Xây dựng siêu phẳng phân cách 2 lớp k và k’ bằng phương pháp SVM phi tuyến với bài toán ràng buộc Cực đại ∑ ∑∑ = = = −= n i n i n j jijijii xxKyyQ 1 1 1 ),( 2 1)( αααα (50) với điều kiện ∑ = = n i ii y 1 0α (51) niCi ,..,2,1,0 =≤≤α (52) trong đó, tập mẫu { }niii yxS 1, == , và nếu yi = +1 thì xi thuộc lớp k, ngược lại thuộc lớp k’. Khi tập các vector hỗ trợ SVs = {xi| 0 < αi ≤ C} được xác dịnh thì hàm phân loại chính là ⎟⎠ ⎞⎜⎝ ⎛= ∑ SVs iii xxKysignxg ),()( α (53) ¾ Bước 2 : Áp dụng SVM phi tuyến để tính độ đo thành viên KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 61 Gán độ đo thành viên cho từng mẫu thuộc lớp k và k’ dựa trên kết quả phân loại. Với mỗi mẫu xj ∈ lớp k ∈ S. Kết quả phân loại xác định bởi hàm SVsxxxKysignxg i SVs ijiij ∈⎟⎠ ⎞⎜⎝ ⎛= ∑ ,),()( α (54) Độ đo thành viên µj của xj được tính theo luật sau: Luật 1: Nếu g(xj) > 0, µj = 1 (54.a) Luật 2: Nếu g(xj) < 0, µj = ε (54.b) Trong luật (55.a), giá tri dưong ε nên nhỏ hơn 1. Sau khi n mẫu huấn luyện trong S đã được tính độ đo, tập mờ Sf được xác định bởi { }niiiif yxS 1,, == µ 5.2.3. Phân tích các phương pháp FSVM nhiều lớp 5.2.3.1. Phân tích cơ chế 1 đối tất cả Đối với SVM truyền thống, cho hàm quyết định thứ i, bằng cách cực đại hóa bờ, thỏa mãn lớp i và các lớp còn lại sẽ là : i t it bwxD +=)( (55) trong đó wi là vector m chiều. Siêu mặt Di(x) = 0 tạo thành siêu mặt phân cách tối ưu và, nếu dữ liệu huấn luyện là tuyến tính và có thể phân cách được, thì các vector hổ trợ thuộc về lớp i thoat mãn Di(x) = 1 và những vector thuộc vào các lớp còn lại thỏa mãn Di(x) = −1. Đối với SVM truyền thống, nếu đối với vector x 0)( >xDt (56) thỏa mãn vector i, thì x được phân vào lớp i. Vì chỉ có dấu hiệu của hàm quyết định được sử dụng, nên quyết định sẽ rời rạc. Nếu (56) thỏa mãn cho nhiều i, hoặc không có i nào thỏa mãn (56), thì x sẽ không thể xếp lớp được (vùng đổ bóng trong Hình 12 là những vùng không thể phân lớp được ). Để tránh điều này, dữ liệu đã biết x được xếp vào lớp )(maxarg xDtt (57) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 62 bởi vì giá trị liên tục của hàm quyết định xác định sự phân lớp nên sự quyết định đó là liên tục. Hình 12-Hình minh họa lỗi của SVM 1-tất cả Với FSVM, trong lớp i chúng ta định nghĩa các hàm thành phần một chiều theo đường chéo góc với siêu mặt phân cách tối ưu như sau : ¾ trường hợp i = j (58) ¾ trường hợp ji≠ (59) KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 63 Hình 13-Hình minh họa trục độ đo thành viên Hình 13 biểu diễn hàm thành phần ).(xmii . Bởi vì lớp i, lớp huấn luyện dữ liệu, chỉ tồn tại khi Di(x) ≥ 1, chúng ta giả thiết rằng bậc của lớp i thành phần là 1, và mặt khác là )(xDj− Đến đây, chúng ta cho phép các thành phân có bậc âm để cho các dữ liệu không có giới hạn có thể được phân loại Ttrong trường hợp ji≠ , lớp i nằm trong phía âm của Dj(x) = 0. Trong trường hợp này, các vector hổ trợ có thể không cần bao gồm dữ liệu của lớp i khi Di(x) ≤ −1, chúng ta giả thiết là bậc của lớp i, bậc của thành phần, là 1 và nếu không là )(xD j− . Bằng cách sử dụng toán tử nhỏ nhất cho ),..,1)(( njxmij = , chúng ta có thể định nghĩa hàm thành phần thuộc lớp i của x. KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 64 nj iji xmxm ,...,1 )(min)( = = (60) Hình dạng của hàm thành phần kết quả là hình tháp đa diện bị cắt trong không gian đặc trưng trong Hình 14.. Bây giờ dữ liệu x được xếp vào lớp : )(maxarg ,..,1 xmini= (61) Dựa vào công thức ở trên, những vùng chưa phân loại như trong hình trên được giải như trong hình dưới đây. Hình 14-Hình minh họa cách khắc phục của FSVM Tại đây chúng ta chứng tỏ rằng những FSVM mờ dạng một đối tất cả với toán tử nhỏ nhất tương đương với những SVM một đối tất cả với hàm quyết định liên tục. Nếu x thỏa : KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 65 (62) Từ (58) và (59), 0)( ≥xm i và ),..,1,(0)( niijxm i =≠< đúng. Do vậy, x được xếp vào lớp i. Điều này tương đương với điều kiện rằng (56) thỏa cho mỗi i và tương đương với (57). Bây giờ chúng ta giả thiết, không mất tính tổng quát, là (56) thỏa khi k=1,…,l(l>1).Chúng ta cũng giả thiết là }),...,1{)(( lsxDs ∈ nhận giá trị cực đại trong số ),..,1)(( nkxDk = Khi đó : 0)( >xD k , với k=1,..,l (63) ,0)( ≤xD k với k=l+1,…,n (64) do đó từ (58) và (60), mk(x) được cho như sau : ¾ Với mỗi k = 1,..,l , do ⎪⎩ ⎪⎨ ⎧ +=≥− ≠=<− => = nljkhixD kjljkhixD kjkhixD xm j j k kj ,..,10))(,1min( ,,..,10)( 0))(,1min( )( (65) 0)(min)( ,,...,1 <−= ≠= xDxm jkjljk nên ms(x) là giá trị lớn nhất trong số :),,...,1)(( sklkxmk ≠= )()(min)( ,,..,1 xmxDxm kjsjljs >−= ≠= (66) ¾ Với mối k = l+i ,... ,n, vì ⎪⎩ ⎪⎨ ⎧ ≠+=≥− =<− =≤ = kjnljkhixD ljkhixD kjkhixD xm j j k kj ,,..,10))(,1min( ,..,10)( 0)( )( (67) 0)(min),(min)( ,...,1 <⎟⎠ ⎞⎜⎝ ⎛ −= = xDxDxm jljkk KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 66 0)(min),(min)( ,...,1 <⎟⎠ ⎞⎜⎝ ⎛ −= = xDxDxm jljkk (68) do đó nếu : )(min)( ,...,1 xDxD jljk −< = )()( xDxm kk = đúng , và nếu )(min)( ,...,1 xDxD jljk −≥ = )()( xDxm kk −= đúng do đó, từ trường hợp 1 và 2, ms(x) nhận giá trị lớn nhất trong , x được xếp vào lớp s. điều này tương đương với (57). Cho (56) không thỏa bất kể lớp nào. Theo đó, 0)( ≤xD i với j=1,…,n (69) do đó (60) được cho bởi : )()( xDxm ii = do đó, bậc cao nhất của thành phần tướng ứng với giá trị lớn nhất của . Diều kiện tương đương với (57). Bởi vậy, các FSVM tương đương với các SVM có hàm quyết định liên tục. 5.2.3.2. Phân tích phương pháp phân lớp theo cặp Trong phương pháp phân lớp theo cặp, chúng ta xác định n(n−1)/2 hàm quyết định cho tất cả các cặp trong lớp. cho hàm quyết định của lớp i đối với lớp j, với bờ cực đại là : ij t ijij bxwxD +=)( (70) trong đó wij là vector m chiều, bij thì vô hướng và . Đối với vector đầu vào x, chúng ta tính KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 67 ∑ =≠ = n jij iji xDsignxD 1, ))(()( (71) và xếp lớp x vào lớp : )(maxarg ,..,1 xD ini = (72) nhưng nếu (72) được thỏa cho nhiều i, x không xếp lớp được. Trong vùng tô đậm trong Hình 15 Di(x) = 1(i = 1, 2, và 3). Do đó vùng tô đậm không xếp lớp được. Hình 15-Hình minh họa lỗi của SVM 1 đối 1 Để giải những vùng không xếp lớp thành xếp lớp theo cặp, Platt, Cristianini và J. Shawe-Taylor đề xuất phương pháp xếp loại theo cặp bằng cách dựa vào cây quyết định cho 3 lớp gọi là Decision Directed Acyclic Graph (DDAG). Hình dưới biểu diễn cây quyết định cho 3 lớp trình bày ở Hình 15. KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 68 Hình 16- Hình minh họa đồ thị DDAG SVM 1 đối 1 Trong Hình 16, i cho thấy rằng lớp liên quan không phải là i. Trong phân loại cấp cao, chúng ta có thể chọn bất kỳ cặp lớp nào. Và ngoại trừ những nút lá nếu 0)( >xD ij , chúng ta xem rằng x không thuộc vào lớp j. Nếu 0)(12 >xD , x không thuộc vào lớp 2. Do đó nó thuộc vào lớp 1 hoặc 3 và cặp phân loại tiếp theo sẽ là 1 và 3. Hình 17-Hình minh họa hướng giải quyết của FSVM cho SVM 1 đối 1 KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 69 Các vùng tổng quát hóa biến đổi như trong Hình 17. các vùng chưa xếp lớp được giải nhưng rõ ràng các vùng tổng quát hóa phụ thuộc vào sự thành lập của cây. Pontil and Verri đề xuất sử dụng quy luât của cuộc thi đấu quần vợt để giải các vùng chưa phân loại. Không biết đồ án của họ, Kijsirikul và Ussivakul đề xuất một phương pháp tương tự. Tương tự SVM một đối tất cả, chúng ta giới thiệu các hàm thành phần để giải các vùng không phân lớp trong khi nhận diện các kết quả phân loại giống như sự phân loại theo cặp thông thường. Để làm được điều này, cho siêu mặt phân cach tối ưu ijxDij ≠= ,0)( chúng ta định nghĩa các hàm thành phần một chiều )(xmij theo chiều chéo góc với 0)( =xDij như sau : (73) Bằng cách sử dụng ),..,1,)(( njijxmij =≠ , chúng ta hàm thành phần lớp i của x sử dụng tóan tử cực tiểu. )(min)( ,..,1 xmxm ijnji == (74) bây giờ dữ liệu x chưa biết được xếp vào lớp )(maxarg ,..,1 xm ini= (75) phương trình (24) tương đương với : ⎟⎠ ⎞⎜⎝ ⎛= =≠ )(min,1min)( ,..,1, xDxm ijnjiji (76) bởi mi(x) = 1 đúng cho duy nhất 1 lớp, (26) giảm thành )(min)( ,..,1, xDxm ijnjiji =≠= (77) giải thiết rằng mi(x) nhận giá trị lớn hơn 1. Vùng không thể phân loại biểu diễn trong Hình 15 được giải như biểu diễn trong Hình 17. KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 70 Tổng quát, SVM mờ giải các vùng không phân lớp theo cách không ưu tiên bất kỳ lớp nào, nhưng SVM dựa theo cây quyết định ưu tiên cho một hoặc nhiều lớp. 5.3. Nhận dạng khuôn mặt người với FSVM 5.3.1. Nhận dạng đa lớp dùng FSVM với cây nhị phân Hệ thống nhận dạng mẫu đa lớp có thể có được bằng cách dùng FSVM tương tự như sử dụng SVM . Có hai chiến lược cho mụch đích này: (1) chiến lược one-against-all (một đối tất cả) để phân loại mỗi lớp với mọi lớp còn lại; (2) chiến lược một đối một để phân loại giữa từng cặp. Chiến lược đầu tiên thường cho kết qủa phân loại nhập nhằng. Ta theo chiến lược thứ hai cho bài toán nhận dạng đa lớp. Giả sử có tám lớp trong tập dữ liệu, cây quyết định được biểu diễn như trong hình dưới đây, trong đó các số 1-8 mã hoá các lớp. Các số mã hoá các lớp là tuỳ ý không có nghĩa theo thứ tự. Bằng cách so sánh từng cặp, chọn ra một lớp biểu diễn “phần thắng” của hai lớp hiện hành. Các lớp được chọn (từ cấp thấp nhất của cây nhị phân) sẽ lên cấp trên với vòng thử nghiệm khác. Cuối cùng một lớp duy nhất sẽ xuất hiện ở đỉnh của cây. Khi c không là bội số của 2, ta phân tích: 1 22 2 ... 2 In n nc = + + + , với 1 2 ... In n n≥ ≥ ≥ . Nếu c lẻ thì 0In = và nếu c chẵn thì 0In > . Cách phân tích c không duy nhất. Sau khi phân tích, vịêc nhận dạng được thực hiện trong từng cây nhị phân, các lớp đầu ra của các cây nhị phân này được dùng lại để tạo ra cây nhị phân khác. Quá trình này được lặp lại cho đến khi chỉ còn một đầu ra. FSVM học ( 1) / 2c c− hàm phân biệt trong giai đoạn huấn luyện, và thực hiện 1c − phép so sánh dưới cấu trúc cây nhị phân đã tạo ra. KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 71 Hình 18-Hình minh họa bộ phân loại đa lớp dạng cây 5.3.2. Nhận dạng đa lớp dùng FSVM với phương pháp bầu cử Phương pháp bầu cử chính là phương pháp phân lớp theo cặp như đã trình bày trong phần phân tích FSVM nhiều lớp ở trên. Trước hết ta thực hiến tiến hành sử dụng tất cả n(n-1)/2 bộ FSVM để lượng giá phiếu bầu cử cho từng lớp theo (71) và lớp quyết định được chọn chính là lớp i thỏa (72). 5.3.3. Nhận dạng khuôn mặt dùng FSVM với phương pháp bầu cử 5.3.3.1. Giai đoạn huấn luyện hệ thống 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 KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 72 Hình 19-Sơ đồ huấn luyện FSVM đa lớp 5.3.3.1.2. Véctơ hóa tập mẫu khuôn mặt thô Đây chính là một bước biểu diễn ảnh khuôn mặt vào máy tính, hình thức biểu diễn này chúng tôi đã có đề cập trong phần mô tả dữ liệu nhận dạng khuôn mặt. Chi tiết vector hoá một mẫu khuôn mặt được trình bày trong hình dưới đây. Véctơ hóa tập mẫu Trích đặc trưng Ánh xạ tập mẫu vào không gian đặc trưng Các véctơ đặc trưng Chuẩn hóa lớp i lớp j Huấn luyện SVM (i,j) Độ đo thành viên(mờ) Huấn luyện FSVM (i,j) n(n-1)/2 bộ phân loại FSVM KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 73 Hình 20 –Cách véctơ hóa ảnh để nhận dạng ¾ Tách ảnh mẫu khuôn mặt 30×30(pixels) thành 30 dòng ảnh theo thứ tự từ trên xuống dưới, mỗi dòng ảnh bao gồm 30 (điểm ảnh). ¾ Vector hoá mẫu khuôn mặt được thực hiện bằng cách nối liên tiếp các dòng ảnh theo thứ tự này liên tiếp nhau và kết quả từ một ma trận ảnh hai chiều 30×30 thành một vector có số chiều bằng 900. 5.3.3.1.3. Rút trích đặc trưng khuôn mặt Giai đoạn rút trích đặc trưng khuôn mặt bao gồm ba bước chính đó là thực hiện phép phân tích thành phần chính, Ánh xạ tập mẫu vào không gian đặc trưng, và chuấn hoá không gian mẫu. Trong tất cả các hệ nhận dạng mà đặc biệt là các hệ nhận dạng tự động nói riêng, mức độ thành công không những phụ thuộc vào các thuật toán nhận dạng tốt mà còn phụ thuộc rất nhiều vào tập mẫu dữ liệu huấn luyện. Việc chọn tập mẫu huấn luyện sao cho phù hợp với mục đích ứng dụng yêu cầu và vừa đảm bảo được tính tổng quát cho một hệ nhận dạng là rất khó. Bởi vì ta không thể lường trước mọi biến thể có thể tác động đến đối tượng quan tâm trong lúc thu nhận ảnh. ¾ Môi trường lấy mẫu biến động rất phức tạp như điều kiện thời tiết trong lúc lấy mẫu, điều kiện độ sáng, môi trường có nhiều đối tượng khác tương tự như đối tượng quan tâm. KH OA C NT T – Đ H KH TN Phương pháp FSVM (Fuzzy SVM) và ứng dụng nhận dạng khuôn mặt 74 ¾ Các biến thể nội tại trong đối tượng ta quan tâm (các biến đổi không bình thường của mẫu ), sự khác nhau về khoảng cách lấy mẫu, mặt phẳng quan sát đối tượng trong lúc lấy mẫu … đó là một trong những vô số nhập nhằng mà một hệ thống nhận dạng phải đối mặt. ¾ Chất lượng thiết bị thu ảnh cũng như giới hạn khả năng tính toán của thiết bị xử lí nhận dạng. Ở đây phương pháp phân tích thành phần chính (PCA) được chọn để tiền xử lí và rút trích đặc trưng từ dữ liệu. PCA là một phương pháp rút trích đặc trưng tự động, không giám sát. Tính ưu việt của phương pháp xử lí này không những khử nhập nhằng tốt mà còn giảm được đáng kể khối lượng dữ liệu luu trữ và xử lí cho hệ thống nhận dạng sau này). Hai tập học PCA bao gồm A=10 lớp và B=44 lớp và mỗi lớp của A gồm 45 đề tài được xử lý từ 5 đề tài nguyên thủy nhờ phép mirror, dịch chuyển ảnh sang các vị trí trái-phải-trên-dưới, còn mỗi lớp của lớp B bao gồm 10 đề tài được xử lý từ 5 đề tài nguyên thủy nhờ phép mirror. Bậy toàn bộ mẫu cho việc huấn luyện PCA gồm 450 véctơ lớp A và 440 véctơ lớp B, mỗi véctơ 900 chiều.. Chi tiết phương pháp trích đặc trưng bằng PCA và PCA cục bộ ở chương