TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN ──────── * ─────── ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC NGÀNH CÔNG NGHỆ THÔNG TIN TÌM HIỂU CÁC PHƯƠNG PHÁP VÀ XÂY DỰNG ỨNG DỤNG PHÁT HIỆN KHUÔN MẶT NGƯỜI DỰA TRÊN ADABOOST Sinh viên thực hiện : Họ tên sinh viên Lớp Tin? - K45 Giáo viên hướng dẫn: [GS/PGS/GVC/TS/ThS] Tên giáo viên Hà nội 5-2007 PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP 1. Định hướng đề tài tốt nghiệp Tìm hiểu các phương pháp phát hiện khuôn mặt người và xây dựng ứng dụng phát hiện khuôn mặt dựa trên giải thuật AdaBoost 2. Các nhiệm vụ cụ thể của đồ án tốt nghiệp - Tìm hiểu các phương pháp phát hiện khuôn mặt - Xây dựng thư viện - Xây dựng ứng dụng 3. Lời cám đoan của sinh viên: Tôi – Mai Anh Tuấn - cam kết đồ án tốt nghiệp là công trình nghiên cứu của bản thân tôi dưới sự hướng dẫn của Ths. Lê Đức Trung. Các kết quả nêu trong đồ án tốt nghiệp là trung thực, không phải là sao chép toàn văn của bất kỳ công trình nào khác. Hà Nội, ngày tháng năm Tác giả đồ án tốt nghiệp Họ và tên sinh viên 4. Xác nhận của giáo viên hướng dẫn về mức độ hoàn thành của đồ án tốt nghiệp và cho phép bảo vệ Lời cảm ơn Trong quá trình thực hiện đồ án, tôi đã nhận được sự giúp đỡ của rất nhiều người. Trước tiên, xin gửi lời cảm ơn chân thành tới thầy giáo Ths Lê Đức Trung đã hướng dẫn, chỉ bảo và tận tình giúp đỡ trong suốt quá trình nghiên cứu và xây dựng đồ án. Xin gửi lời cảm ơn đến các thấy giáo Ths Lương Mạnh Bá, Ths Lê Tấn Hùng, công ty Avasys Việt nam và cá nhân anh Nguyễn Văn Thành vì sự giúp đỡ tận tình trong quá trình thực hiện thực tập tốt nghiệp. Những sự giúp đỡ quý báu này đã góp phần định hướng nội dung nghiên cứu của đồ án. Xin cảm ơn gia đình tôi và những người bạn đã luôn ở bên, động viên, giúp đỡ và tạo mọi điều kiện tốt nhất về mọi mặt trong quá trình thực hiện đồ án. Sự giúp đỡ này là động lực lớn để tôi hoàn thành đồ án tốt nghiệp này. Sinh viên thực hiện Mai Anh Tuấn TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP Nhận dạng khuôn mặt người là một lĩnh vực quan trọng và có nhiều ứng dụng thực tế, như trong các hệ thống bảo mật, xác minh nhân dạng, phương thức giao tiếp người máy mới, hay trong lĩnh vực giải trí,… và bước đầu tiên và cũng là quan trọng nhất để có thể nhận dạng được khuôn mặt chính là phải định vị được khuôn mặt trong hình. Đây chính là đối tượng nghiên cứu của lĩnh vực phát hiện khuôn mặt người. Những năm trở lại đây đánh dấu những tiến bộ lớn cả về tốc độ và độ chính xác của các phương pháp và kỹ thuật phát hiện khuôn mặt. Nội dung chính của báo cáo sẽ trình bày những vấn đề lý thuyết cơ bản của lĩnh vực phát hiện khuôn mặt cũng như những thành công mà các nhà nghiên cứu đã đạt được trong những năm gần đây. Báo cáo nhằm mục đích có được cái nhìn tổng quát về lĩnh vực phát hiện khuôn mặt, nắm bắt được những hướng tiếp cận giải quyết bài toán chính và tập trung tìm hiểu một trong những giải thuật phát hiện khuôn mặt nhanh nhất hiện nay, giải thuật AdaBoost do hai nhà nghiên cứu Viola và Jones đề xuất. Bào cáo gồm 2 phần chính. Phần 1 của báo cáo sẽ trình bày những cơ sở lý thuyết cơ bản của lĩnh vực phát hiện khuôn mặt. Phần này gồm 3 chương: Chương 1 giới thiệu chung về lĩnh vực phát hiện khuôn mặt, mô hình bài toán phát hiện khuôn mặt cũng như tư tưởng chung của các phương pháp hiện nay. Chương 2 đưa ra cái nhìn tổng quát về lĩnh vực phát hiện khuôn mặt, những hướng tiếp cận chính trong những nghiên cứu hiện nay. Với môi hướng tiếp cận, một số phương pháp nổi bật như Eigenface, biệt thức tuyến tính Fisher, mạng Nơron, máy vector hỗ trợ (SVM), mô hình Markov ẩn (HMM),… sẽ được trình bày sơ lược. Chương 3 sẽ tập trung tìm hiểu về phương pháp phát hiện khuôn mặt nhanh sử dụng giải thuật AdaBoost. Những vấn đề và khái niệm cơ bản gắn liền với phương pháp bao gồm những chi tiết Haar, ảnh tích phân, kỹ thuật Boosting, kỹ thuật xây dựng bộ phân lớp xếp tầng,… sẽ được nói đến. Cơ sở lý thuyết của giải thuật AdaBoost cũng sẽ được trình bày chi tiết. Ngoài ra, chương 3 còn đi kèm với một ví dụ minh họa cụ thể của giải thuật AdaBoost, qua đó cung cấp cái nhìn trực quan nhất tư tưởng của phương pháp. Phần 2 sẽ trình bày về việc thiết kế và xây dựng thư viện và chương trình. Phần này gồm 4 chương: Chương 4 trình bày sơ lược cơ sở kiến thức xử lý ảnh được sử dụng trong quá trình xây dựng chương trình. Nội dung chính đề cập đến những không gian mầu khác nhau, chuyển đổi qua lại giữa những không gian mầu và một số bộ lọc và kỹ thuật xử lý được sử dụng trong chương trình. Chương 5 giải quyết bài toán phát hiện khuôn mặt trên hình ảnh tĩnh. Chương này đưa ra một thiết kế và xây dựng một thư viện phục vụ phát hiện các khuôn mặt trên hình ảnh tĩnh. Chương 6 giải quyết bài toán phát hiện khuôn mặt trên hình ảnh động, đề cập đến những vấn đề như việc thu nhận hình ảnh động (từ những thiết bị camera và từ các tệp video), tích hợp thư viện phát hiện khuôn mặt trên hình ảnh tĩnh đã đề cập trong chương 5. Chương này cũng đề cập đến vấn đề về phát hiện khuôn mặt trong thời gian thực, những trở ngại về tốc độ và chất lượng ảnh, và những kỹ thuật đã sử dụng để tăng tốc độ phát hiện bao gồm kỹ thuật quét lân cận và kỹ thuật phát hiện chuyển động. Chương 7 thiết kế và xây dựng một ứng dụng sử dụng các thư viện đã xây dựng trong chương 5 và 6. Chương này trình bày về việc phân tích, thiết kế chức năng, thiết kế giao diện, cài đặt và kiểm thử chương trình. ABSTRACT OF THESIS In this report, the theory of face detection is presented. Face detection is an extremely difficult task in image analysis which has each day more and more applications. The existing methods of face detection can be divided into two main approaches: image-based methods and feature-based methods. This report is focused on the fastest face detection algorithm nowadays, the AdaBoost algorithm which was introduced and implemented by Viola and Jones. The main motivation for choosing the algorithm is its simplicity but also its capability of detecting faces very fast while remaining high detection rates. AdaBoost is an aggressive learning algorithm which produces a strong classifier by choosing visual features in a family of simple classifiers and combining them linearly. It uses rectangular Haar feature, which can be computed very fast on a new image representation called Integral Image, to build simple classifiers. To improve the detection speed and the detection efficiency, a number of classifiers with an increasingly complexity are trained and combined sequentially to create a strong cascaded classifier. The final classifier allows real-time face detection for many real-world applications. A sample program is built to demonstrate the algorithm and results are presented at the end of the report. MỤC LỤC MỤC LỤC 5 DANH SÁCH HÌNH 8 DANH SÁCH THUẬT NGỮ 8 Phần I 10 CƠ SỞ LÝ THUYẾT 10 Chương 1 11 Giới thiệu chung về lĩnh vực phát hiện khuôn mặt 11 Giới thiệu 1.1 11 Bài toán 1.2 11 Những tham số của hình ảnh khuôn mặt 1.3 11 Phân loại bài toàn 1.4 11 Tư tưởng chung của các phương pháp 1.5 11 Kết chương 1.6 11 1.1 Giới thiệu 12 1.2 Bài toán 12 1.3 Những tham số của hình ảnh khuôn mặt 13 1.4 Phân loại bài toán 13 1.5 Ý tưởng chung của các phương pháp 13 1.6 Kết chương 14 Chương 2 15 Tìm hiểu một số phương pháp 15 Những phương pháp dựa trên hình ảnh khuôn mặt 2.1 15 Những phương pháp dựa trên cấu trúc khuôn măt 2.2 15 Đánh giá chất lượng các phương pháp 2.3 15 Kết chương 2.4 15 2.1 Những phương pháp dựa trên hình ảnh khuôn mặt 16 2.1.1 Phương pháp Eigenface [6] 16 2.1.1.1 Tư tưởng của phương pháp 16 2.1.1.2 Xác định các eigenface 16 2.1.1.3 Biểu diễn khuôn mặt dựa trên cơ sở eigenface 18 2.1.1.4 Phát hiện khuôn mặt sử dụng các eigenface 18 2.1.1.5 Đánh giá phương pháp: 19 2.1.2 Biệt thức tuyến tính Fisher 19 2.1.3 Mạng nơron 20 2.1.4 Máy vector hỗ trợ 21 2.1.5 Mô hình Markov ẩn 22 2.1.6 Mạng Winnows thưa (SNoW) 23 2.2 Những phương pháp dựa trên cấu trúc hình học của khuôn mặt 23 2.2.1 Giới thiệu 23 2.2.2 Những phương pháp từ trên xuống (top-down) 24 2.2.3 Những phương pháp từ dưới lên (bottom-up) 25 2.3 Đánh giá chất lượng các phương pháp 25 2.4 Kết chương 26 Chương 3 27 Phát hiện khuôn mặt nhanh sử dụng giải thuật AdaBoost 27 Giới thiệu chung 3.1 27 Lý do lựa chọn phương pháp 3.2 27 Giải thuật AdaBoost 3.3 27 Xếp tầng các bộ phân lớp 3.4 27 So sánh giữa những phương pháp dựa trên 3.5 27 giải thuật Boosting 27 3.1 Giới thiệu chung 28 3.2 Lý do lựa chọn phương pháp 29 3.3 Giải thuật Adaboost 29 3.3.1 Cơ sở giải thuật Boosting 30 3.3.2 Chi tiết Haar 31 3.3.3 Ảnh tích phân 33 3.3.4 Bộ phân lớp yếu 34 3.3.5 Xây dựng bộ phân lớp yếu từ những chi tiết Haar 34 3.3.6 Giá trị ngưỡng tối ưu 35 3.3.7 Chi tiết giải thuật 35 3.3.8 Ví dụ áp dụng thuật toán AdaBoost để giải bài toán phân lớp 36 3.4 Xếp tầng các bộ phân lớp 39 3.5 So sánh giữa những phương pháp dựa trên giải thuật Boosting 41 3.6 Kết chương 41 Phần II 42 THIẾT KẾ XÂY DỰNG 42 THƯ VIỆN VÀ CHƯƠNG TRÌNH 42 Chương 4 43 Cơ sử lý thuyết Xử lý ảnh 43 Không gian mầu và 4.1 43 chuyển đổi giữa những không gian mầu 43 Kỹ thuật trừ ảnh 4.2 43 Kỹ thuật cắt theo mức 4.3 43 Bộ lọc ăn mòn 4.4 43 Kết hợp các bộ lọc 4.5 43 để xây dựng bộ phát hiện chuyển động 43 4.1 Không gian mầu và chuyển đổi giữa các không gian mầu 44 4.1.1 Không gian mầu RGB 44 4.1.2 Không gian mầu HSL 44 4.1.3 Không gian mầu YCbCr 46 4.1.4 Ứng dụng các không gian mầu trong việc lọc mầu da (Skin color filtering) 47 4.2 Kỹ thuật Trừ ảnh [8] 47 4.3 Kỹ thuật cắt theo mức [8] 48 4.4 Phép co (Erosion) [8] 48 4.5 Kết hợp các bộ lọc để xây dựng một bộ phát hiện chuyển động 48 Chương 5 50 Phát hiện khuôn mặt trên ảnh tĩnh 50 Bài toán 5.1 50 Bộ phát hiện khuôn mặt 5.2 50 Cấu trúc dữ liệu lưu trữ kết quả huấn luyện 5.3 50 Biểu diễn ảnh bằng kỹ thuật ảnh tích phân 5.4 50 5.1 Bài toán 51 5.1.1 Khó khăn của bài toán 51 5.1.2 Giới hạn phạm vi bài toán 51 5.2 Bộ phát hiện khuôn mặt 52 5.3 Cấu trúc dữ liệu lưu trữ kết quả huấn luyện 54 5.3.1 Cấu trúc tệp tin XML 54 5.3.2 Thiết kế những lớp dữ liệu tương ứng 55 5.3.3 Đọc dữ liệu từ tên tin XML 56 5.4 Biểu diễn ảnh bằng kỹ thuật ảnh tích phân 57 Chương 6 58 Phát hiện khuôn mặt trên hình ảnh động 58 Bài toán 6.1 58 Thu nhận hình ảnh 6.2 58 Những kỹ thuật tăng tốc độ phát hiện 6.3 58 6.1 Bài toán phát hiện khuôn mặt trên hình ảnh động 59 6.2 Thu nhận hình ảnh 59 6.2.1 Thu nhận hình ảnh từ thiết bị camera 59 6.2.2 Đọc hình ảnh từ tệp tin AVI 60 6.3 Những kỹ thuật tăng tốc độ phát hiện 60 6.3.1 Kỹ thuật quét cục bộ 60 6.3.2 Kỹ thuật phát hiện chuyển động 60 6.3.3 Kết hợp hai kỹ thuật 62 Chương 7 63 Thiết kế và xây dựng ứng dụng 63 Xác định yêu cầu 7.1 63 Thiết kế chức năng 7.2 63 Thiết kế giao diện 7.3 63 Cài đặt chương trình 7.4 63 7.1 Xác định yêu cầu 64 7.2 Thiết kế chức năng 64 7.2.1 Chức năng phát hiện khuôn mặt 64 7.2.1.1 Chức năng phát hiện khuôn mặt trên ảnh tĩnh 65 7.2.1.2 Chức năng phát hiện khuôn mặt trên hình ảnh động đọc từ file AVI 65 7.2.1.3 Chức năng phát hiện khuôn mặt trên hình ảnh động thu nhận từ thiết bị Camera 65 7.2.1.4 Chức năng lưu kết quả phát hiện 66 7.2.2 Chức năng tích hợp thư viện nhận dạng khuôn mặt của tác giả Nguyễn Thùy Liên 66 7.2.2.1 Chức năng huấn luyện khuôn mặt 66 7.2.2.1 Chức năng nhận dạng khuôn mặt 66 7.3 Thiết kế giao diện 67 7.3.1 Giao diện cho chức năng phát hiện khuôn mặt 67 7.3.2 Giao diện cho chức năng nhận diện khuôn mặt 68 7.4 Cài đặt chương trình 71 7.4.1 Lựa chọn công nghệ và môi trường cài đặt 71 7.4.2 Giao diện chương trình 71 7.4.2.1 Giao diện chính của chương trình 72 7.4.2.2 Giao diện chức năng quản lý file và thiết bị 73 7.4.2.3 Giao diện chức năng phát hiện khuôn mặt 74 7.4.2.4 Giao diện chức năng quản lý ảnh khuôn mặt 75 7.5 Kiểm thử 76 KẾT LUẬN và 85 HƯỚNG PHÁT TRIỂN TIẾP THEO 85 TÀI LIỆU THAM KHẢO 86 DANH SÁCH HÌNH Hình 1 – Biểu diễn khuôn mặt dựa trên cơ sở eigenface 18 Hình 2 – Phép chiếu trên không gian mặt 19 Hình 3 – Bộ phát hiện khuôn mặt dựa trên mạng nơron 21 Hình 4 – Ranh giới giữa hai lớp mặt và không-phải-là mặt xác định bởi máy vector hỗ trợ 22 Hình 5 – Phương pháp phát hiện khuôn mặt dựa trên mô hình Markov ẩn 23 Hình 6 - Giá trị ngưỡng tối ưu làm cực tiểu số những mẫu mặt và không-phải-là-mặt bị phân lớp sai 35 Hình 7 – Giải thuật xây dựng bộ phân lớp xếp tầng 40 Hình 8 – Biểu diễn khối hộp của không gian mầu RGB 44 Hình 9 – Biểu diễn của không gian mầu HSL 44 Hình 10 – Phân bố của các thành phần H và S của mầu da người trong không gian mầu HLS 47 Hình 11 – Mô hình bài toán phát hiện khuôn mặt trực tiếp từ Camera. 59 DANH SÁCH THUẬT NGỮ AdaBoost Adaptive Boost – phiên bản phổ biến và có nhiều ứng dụng nhất của giải thuật Boosting. Boosting Một giải thuật cho phép cải thiện chất lượng của những giải thuật học máy khác. Cascaded Classifier Bộ phân lớp xếp tầng, mỗi tầng là một bộ phân lớp mạnh được xếp từ đơn giản đến phức tạp. Classifier Bộ phân lớp có nhiệm vụ xác định ảnh đầu vào có phải là khuôn mặt hay không-phải-là-mặt. Detection rate Tỷ lệ giữa số khuôn mặt phát hiện đúng so với số khuôn mặt thực sự hiện diện trong ảnh Face detection Phát hiện khuôn mặt nhằm tìm ra vị trí và kích thước của những khuôn mặt hiện diện trong ảnh. False detection hoặc False positive detection [...]... hướng tiếp cận hiện nay Trong chương tiếp theo, một số phương pháp sẽ được trình bày cụ thể Chương 2 Tìm hiểu một số phương pháp Những phương pháp dựa trên hình ảnh khuôn mặt 2.1 Những phương pháp dựa trên cấu trúc khuôn măt 2.2 Đánh giá chất lượng các phương pháp 2.3 Kết chương 2.4 2.1 Những phương pháp dựa trên hình ảnh khuôn mặt Tư tưởng chung của các phương pháp Những phương pháp này tìm cách huấn... Những phương pháp dựa trên cấu trúc hình học của khuôn mặt 2.2.1 Giới thiệu Những phương pháp thông kê được giới thiệu ở trên đều dựa trên một phương pháp học máy nào đó để xây dựng nên một mô hình khuôn mặt từ tập ảnh mẫu những ảnh không mặt và không-phải-là -mặt Với cách tiếp cận dựa trên cấu trúc hình học của khuôn mặt, các nhà nghiên cứu tìm cách giải quyết bài toán phát hiện khuôn mặt dựa trên những... và phát hiện khuôn mặt đa góc nhìn • Nếu xét về yếu tố đầu vào, ta có bài toán phát hiện khuôn mặt trên hình ảnh đơn lẻ và phát hiện khuôn mặt trên chuỗi hình ảnh động • Xét về kích thước khuôn mặt, ta có bài toán phát hiện khuôn mặt kích thước cố định và phát hiện khuôn mặt đa kích thước • … 1.5 Ý tưởng chung của các phương pháp Việc giải quyết bài toán tổng quát là vô cùng khó khăn và hiện tại chưa... giữa người và máy tính, và nhiều ứng dụng quan trọng khác Mục tiêu của việc phát hiện khuôn mặt là xác định và chỉ ra vị trí và kích thước của những khuôn mặt người trong hình ảnh tĩnh hoặc hình ảnh động Phát hiện khuôn mặt là một công nghệ cho phép xác định được vị trí và kích thước của các khuôn mặt người hiện diện trong một bức ảnh số Công nghệ này có thể phát hiện ra những chi tiết khuôn mặt và. .. cụ thể, và hiện nay cũng chưa có một chuẩn nào để đánh giá chất lượng của các phương pháp phát hiện khuôn mặt Một số tiêu chí thường được sử dụng như: Tỷ lệ khuôn mặt phát hiện đúng là tỷ lệ giữa số khuôn mặt phát hiện được so với số khuôn mặt thực sự hiện diện trong hình Về nguyên tắc, tỷ lệ này càng gần 1 càng tốt Tỷ lệ khuôn mặt không phát hiện được, là tỷ lệ giữa số khuôn mặt mà bộ phát hiện bỏ... với nhau để xây dựng mô hình khuôn mặt • Một phương pháp khác sử dụng dấu hiệu mầu sắc do Cai và Goshtasby đề xuất Họ phát hiện khuôn mặt bằng cách kiểm tra sự hiện diện của những chi tiết có mầu khác với mầu da thịt trên những vùng da thịt đã được tìm thấy 2.3 Đánh giá chất lượng các phương pháp Việc so sánh giữa những phương pháp khác nhau rất khó thực hiện, bởi mỗi phương pháp được xây dựng nhằm giải... Những tham số của hình ảnh khuôn mặt 1.3 Phân loại bài toàn 1.4 Tư tưởng chung của các phương pháp 1.5 Kết chương 1.6 1.1 Giới thiệu Phát hiện khuôn mặt là một ứng dụng cơ bản thiết yếu của lĩnh vực phát hiện đối tượng (objects detection) nói chung và là khâu đầu tiên của bất kỳ hệ thống phát hiện và nhận dạng khuôn mặt tự động nào Ngoài ra, phát hiện khuôn mặt còn được ứng dụng rộng rãi trong những... bị camera) Tốc độ phát hiện khuôn mặt là một tiêu chí quan trọng hàng đầu, tuy nhiên tỷ lệ phát hiện đúng của phương pháp cũng phải được bảo đảm ở một mức nhất định Do đó phương pháp lựa chọn cần có tốc độ phát hiện nhanh mà vẫn bảo đảm được mức độ chính xác cần thiết Phương pháp phát hiện khuôn mặt nhanh dựa trên giải thuật AdaBoost đáp ứng tốt nhất những yêu cầu này Phương pháp AdaBoost có thể đạt... phương pháp này không thể theo kịp phương pháp phát hiện khuôn mặt nhanh sử dụng giải thuật AdaBoost Giải thuật này sẽ được tập trung tìm hiểu trong chương tiếp theo Chương 3 Phát hiện khuôn mặt nhanh sử dụng giải thuật AdaBoost Giới thiệu chung 3.1 Lý do lựa chọn phương pháp 3.2 Giải thuật AdaBoost 3.3 Xếp tầng các bộ phân lớp 3.4 So sánh giữa những phương pháp dựa trên 3.5 giải thuật Boosting 3.1... trưng của khuôn mặt hiện diện trong hình ảnh, sau đó kết hợp thành từng nhóm chi tiết để biểu diễn nên khuôn mặt dựa vào những kiến thức cho trước về cấu trúc khuôn mặt Các nhà nghiên cứu Leung và Sumi đã xây dựng hệ thống của họ theo cách này 2.2.2 Những phương pháp từ trên xuống (top-down) Phần lớn trong số những phương pháp này sử dụng dấu hiệu về mầu sắc của da thịt con người để tìm kiếm khuôn mặt trong . nghiệp Tìm hiểu các phương pháp phát hiện khuôn mặt người và xây dựng ứng dụng phát hiện khuôn mặt dựa trên giải thuật AdaBoost 2. Các nhiệm vụ cụ thể của đồ án tốt nghiệp - Tìm hiểu các phương pháp. của khuôn mặt, ta có bài toán phát hiện khuôn mặt trực diện và phát hiện khuôn mặt đa góc nhìn. • Nếu xét về yếu tố đầu vào, ta có bài toán phát hiện khuôn mặt trên hình ảnh đơn lẻ và phát hiện. ÁN TỐT NGHIỆP ĐẠI HỌC NGÀNH CÔNG NGHỆ THÔNG TIN TÌM HIỂU CÁC PHƯƠNG PHÁP VÀ XÂY DỰNG ỨNG DỤNG PHÁT HIỆN KHUÔN MẶT NGƯỜI DỰA TRÊN ADABOOST Sinh viên thực hiện : Họ tên sinh viên Lớp Tin? - K45 Giáo