đặt vấn đề cho bài toán. Bên cạnh đó, tác giả cũng phân tích: những ƣu, nhƣợc điểm, các khó khăn thách thức của lớp bài toán đã đặt ra trong luận văn. Để giải quyết yêu cầu đặt ra của luận văn, tác giả đi sâu nghiên cứu và giải quyết hai vấn đề chính: Vấn đề thứ nhất, giới thiệu trình tự các bƣớc giải quyết cho lớp bài toán. Vấn đề thứ hai, nghiên cứu và xây dựng ứng dụng hệ thống xác định khuôn mặt chung nhất trong một tập ảnh cho trƣớc.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 18 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT Trong chƣơng này tác giả sẽ trình bày tổng quan lý thuyết để giải quyết bài toán bao gồm lý thuyết thuật toán, phƣơng pháp của các giai đoạn nhƣ phát hiện khuôn mặt, trích rút đặc trƣng, và xác định khuôn mặt chung nhất trong tập ảnh cho trƣớc.1 Phát hiện khuôn mặt 2.1 Các đặc trƣng giống Haar Viola và Jones dùng 4 đặc trƣng cơ bản [18] để xác định khuôn mặt ngƣời. Mỗi đặc trƣng Haar–like là sự kết hợp của hai hay ba hình chữ nhật "trắng" hay "đen" nhƣ trong hình sau: Hình 2.1: Bốn đặc trưng Haar-like cơ bản Để áp dụng các đặc trƣng này vào việc bài toán xác định mặt ngƣời, 4 đặc trƣng Haar-like cơ bản đƣợc mở rộng ra, và đƣợc chia làm 3 tập đặc trƣng nhƣ sau: 1 Đặc trưng cạnh (edge features): 2. Đặc trưng đường (line features): 3. Đặc trưng xung quanh tâm (center-surround features): Hình 2.2: Các đặc trưng mở rộng của các đặc trưng Haar-like cơ sở Lợi ích của các đặc trƣng Haar-like là nó diễn đạt đƣợc tri thức về các đối tƣợng trong ảnh (bởi vì nó biểu diễn mối liên hệ giữa các bộ phận của đối tƣợng), điều mà bản thân từng điểm ảnh không diễn đạt đƣợc.
Để tính giá trị các đặc trƣng haar-like, ta tính sự chênh lệch giữa tổng của các pixel của các vùng đen và các vùng trắng nhƣ trong công thức sau: f(x) = Tổngvùng đen(pixel) - Tổngvùng trắng(pixel) (2.1) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 19 Nhƣ vậy ta có thể thấy rằng, để tính các giá trị của đặc trƣng Haar-like, ta phải tính tổng của các vùng pixel trên ảnh. Nhƣng để tính toán các giá trị của các đặc trƣng Haar-like cho tất cả các vị trí trên ảnh đòi hỏi chi phí tính toán khá lớn, không đáp ứng đƣợc cho các ứng dụng đòi hỏi tính run-time. Do đó Viola và Jones đƣa ra một khái niệm gọi là Integral Image để tính toán nhanh cho khác feature cơ bản. Sau này, Lienhart kế thừa gọi Integral Image là SAT – Summed Area Table và đƣa ra thêm khái niệm RSAT – Rotated Summed Area Table dùng để tính toán nhanh cho các đặc trƣng xoay 1 góc 45o.
Integral Image là một mảng 2 chiều với kích thƣớc bằng với kích của ảnh cần tính các đặc trƣng Haar-like, với mỗi phần tử của mảng này đƣợc tính bằng cách tính tổng của điểm ảnh phía trên (dòng-1) và bên trái (cột-1) của nó. Bắt đầu từ vị trí trên, bên trái đến vị trí dƣới, phải của ảnh, việc tính toán này đơn thuần chỉ đựa trên phép cộng số nguyên đơn giản, do đó tốc độ thực hiện rất nhanh.3: Cách tính Integral Image của ảnh Sau khi đã tính đƣợc Integral Image, việc tính tổng điểm ảnh của một vùng bất kỳ nào đó trên ảnh thực hiện rất đơn giản theo cách sau: (Giả sử ta cần tính tổng điểm ảnh của vùng D nhƣ trong hình 2.4: D = A + B + C + D – (A+B) – (A+C) + A Với A + B + C + D chính là giá trị tại điểm P4 trên Integral Image, tƣơng tự nhƣ vậy A+B là giá trị tại điểm P2, A+C là giá trị tại điểm P3, và A là giá trị tại điểm P1. Vậy ta có thể viết lại biểu thức tính D ở trên nhƣ sau: (2.4: Cách tính nhanh tổng các điểm ảnh của vùng D trên ảnh LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 20 A B C 1 2 D 3 RSAT(x,y) 4 (a) (b) Hình 2.5: Cách tính nhanh tổng điểm ảnh của vùng D trên ảnh với các đặc trưng xoay 45o Với các đặc trƣng Haar-like xoay 45o Integral Image tại một điểm (x, y) đƣợc tính theo công thức: (2.4) Tổng pixel của một vùng bất kỳ trên ảnh vẫn đƣợc tính theo cách sau: D = A + B + C + D – (A+B) – (A+C) + A Nhƣ vậy tổng các điểm ảnh trong một hình chữ nhật (kể cả trƣờng hợp xoay 45º) bất kì đều có thể đƣợc tính nhanh dựa trên integral image tại 4 đỉnh của nó : Sum (D ) = 4 - 2 – 3 + 1 2.2 Phƣơng pháp Adaboost Nhƣ đã biết, AdaBoost [18] ( Adaptive Boost ) là một bộ phân loại mạnh phi tuyến phức dựa trên hƣớng tiếp cận boosting đƣợc Freund và Schapire đƣa ra vào năm 1995. Adaboost hoạt động trên nguyên tắc kết hợp tuyến tính các weak classifier dựa trên các đặc trƣng Haar- Line để hình thành một strong classifier.
Để có thể kết hợp các bộ phân loại yếu, adaboost sử dụng một trọng số (weight) để đánh dấu các mẫu khó nhận dạng. Trong quá trình huấn luyện, cứ mỗi weak classifier đƣợc xây dựng, thuật toán sẽ tiến hành cập nhật lại trọng số để chuẩn bị cho việc xây dựng weak classifier tiếp theo: tăng trọng số của các mẫu bị nhận dạng sai và giảm trọng số của các mẫu đƣợc nhận dạng đúng bởi weak classifier vừa xây dựng. Bằng cách này, các weak classifier sau có thể tập trung vào các mẫu mà các weak classifier trƣớc đó chƣa thực hiện tốt. Sau cùng các weak classifier sẽ đƣợc kết hợp tùy theo mức độ „tốt‟ của chúng để tạo nên một strong classifier.
Các weak classifiers hk(x) là các bộ phân loại yếu, đƣợc biểu diễn nhƣ sau: (2.5) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 21 Trong đó: X : mẫu hay cửa sổ con cần xét ( X = (x1,x2,…,xn) là vector đặc trƣng của mẫu) Ok: ngƣỡng (O = teta) fk: giá trị của đặc trƣng Haar-like pk: hệ số quyết định chiều của bất phƣơng trình Công thức trên có thể diễn giải nhƣ sau: Nếu giá trị đặc trƣng của mẫu cho bởi hàm đánh giá của bộ phân loại vƣợt qua một ngƣỡng cho trƣớc thì mẫu đấy là khuôn mặt ( gọi là object : đối tƣợng cần nhận dạng ), ngƣợc lại thì mẫu là background ( không phải là đối tƣợng ). Thuật toán AdaBoost: 1. Cho một tập gồm n mẫu có đánh dấu (x1,y1), (x2,y2),… (xn,yn) với xk ∈ (xk1, xk2, … , xkm) là vector đặc trƣng và yk ∈ (-1, 1) là nhãn của mẫu (1 ứng với object, -1 ứng với background). Khởi tạo trọng số ban đầu cho tất cả các mẫu: với m là số mẫu đúng (ứng với object và y = 1) và l là số mẫu sai (ứng với background và y = -1).
Xây dựng T weak classifiers Lặp t = 1, …, T Với mỗi đặc trƣng trong vector đặc trƣng, xây dựng một weak classifier hj với ngƣỡng θj và lỗi εj. Chọn ra hj với εj nhỏ nhất, ta đƣợc ht: Cập nhật lại trọng số: Trong đó: : Hệ số dùng để đƣa về đoạn [0,1] (normalization factor) 4. Strong classifier đƣợc xây dựng : Hình 2.6: Thuật toán Adaboost LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 22 Quá trình huấn luyện bộ phân loại đƣợc thực hiện bằng một vòng lặp mà ở mỗi bƣớc lặp, thuật toán sẽ chọn ra weak classifier ht thực hiện việc phân loại với lỗi εt nhỏ nhất (do đó sẽ là bộ phân loại tốt nhất) để bổ sung vào strong classifier. Mỗi khi chọn đƣợc 1 bộ phân loại ht, Adaboost sẽ tính giá trị αt theo công thức ở trên.
αt cũng đƣợc chọn trên nguyên tắc làm giảm thiểu giá trị lỗi εt. Hệ số αt nói lên mức độ quan trọng của ht: Trong công thức của bộ phân loại H(x): (2.6) Ta thấy tất cả các bộ phân loại ht đều có đóng góp vào kết quả của bộ phân loại H(x), và mức độ đóng góp của chúng phụ thuộc vào giá trị αt tƣơng ứng: ht với αt càng lớn thì nó càng có vài trò quan trọng trong H(x). Trong công thức tính αt: (2.7) Dễ thấy giá trị αt tỉ lệ nghịch với εt. Bởi vì ht đƣợc chọn với tiêu chí đạt εt nhỏ nhất, do đó nó sẽ đảm bảo giá trị αt lớn nhất.
Sau khi tính đƣợc giá trị αt, Adaboost tiến hành cập nhật lại trọng số của các mẫu: tăng trọng số các mẫu mà ht phân loại sai, giảm trọng số các mẫu mà ht phân loại đúng. Bằng cách này, trọng số của mẫu phản ánh đƣợc mức độ khó nhận dạng của mẫu đó và ht+1 sẽ ƣu tiên học cách phân loại những mẫu này. Vòng lặp xây dựng strong classifier sẽ dừng lại sau T lần lặp. Trong thực tế cài đặt (thƣ viện OpenCV của Intel), ngƣời ta ít sử dụng giá trị T vì không có công thức nào đảm bảo tính đƣợc giá trị T tối ƣu cho quá trình huấn luyện.
Thay vào đó, ngƣời ta sử dụng giá trị max false positive hay max false alarm (tỉ lệ nhận dạng sai tối đa các mẫu background). Tỉ lệ này của bộ phân loại cần xây dựng không đƣợc phép vƣợt quá giá trị này. Khi đó, qua các lần lặp, false alarm của strong classifier Ht(x) xây dựng đƣợc (tại lần lặp thứ t) sẽ giảm dần, và vòng lặp kết thúc khi tỉ lệ này thấp hơn max false alarm.2 Tổng quan về các phƣơng pháp trích rút đặc trƣng Hiện nay có rất nhiều các phƣơng pháp trích dẫn dữ liệu từ khuôn mặt, mỗi phƣơng pháp có những ƣu nhƣợc điểm và đặc điểm riêng nhƣng theo cách thức mà những phƣơng pháp và hình thức của dữ liệu đƣợc trích dẫn thì chia ra làm 2 hƣớng tiếp cận chính: Thứ nhất, hƣớng tiếp cận dựa trên đặc trƣng hình học là hƣớng tiếp cận dựa vào các bức ảnh trực diện khuôn mặt lấy từ khâu phát hiện khuôn mặt, trích chọn đặc trƣng LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 23 về hình học biểu diễn hình dáng, vị trí các phần của khuôn mặt nhƣ mắt, mũi, miệng, lông mày. Cụ thể xác định một số các điểm đặc trƣng trên khuôn mặt: 2 mống mắt, điểm chính giữa miệng, khóe miệng, một số các điểm khác ở vùng trán, mắt,… Thứ hai, hƣớng tiếp cận dựa trên đặc trƣng diện mạo là hƣớng tiếp cận dựa vào cấu trúc phân bổ của cƣờng độ sáng của điểm ảnh trên bề mặt của bức ảnh để trích chọn các đặc trƣng.
Trong đó trích chọn đặc trƣng diện mạo có ƣu điểm là ít phức tạp hơn phƣơng pháp trích chọn đặc trƣng hình học, các khâu ít hơn nhƣng độ chính xác thƣờng thấp hơn.