Áp dụng AdaBoost và LBP cho bài toán phát hiện mặt người

12 Chương 3. Áp dụng AdaBoost và LBP cho bài toán phát hiện mặt người 3.1 AdaBoost 3.1.1 Tổng quan về AdaBoost AdaBoost là một thuật toán boosting, ý tưởng cơ bản của AdaBoost là kết hợp các bộ phân loại yếu để xây dựng bộ phân lớp mạnh. 3.1.2 Áp dụng AdaBoost cho bài toán phát hiện khuôn mặt Để phát hiện khuôn mặt, các tiếp cận dựa trên AdaBoost gồm hai giai đoạn chính. Trong giai đoạn đầu, các bộ phân lớp mạnh được xây dựng từ các bộ phân lớp yếu. Trong giai đoạn hai, các bộ phân lớp mạnh sẽ được kết hợp tuần tự để tạo thành cascade of boosted classifier (cascade tree). 3.1.2.1 Xây dựng các bộ phân lớp mạnh Đầu vào: dữ liệu huấn luyện X, X = {x1, …, xn}. Với { } Xxxxx mkkkk ∈= ,...,, 21 là một vector đặc trưng. { }1,1 +−=∈Yyk là một nhãn tương ứng (+1 tương ứng với khuôn mặt, -1 tương ứng với không phải khuôn mặt). T các phân lớp yếu hj: X → {-1, +1}. Chúng tôi sử dụng thuật toán AdaBoost để xây dựng một bộ phân lớp mạnh. Đầu ra: Bộ phân lớp mạnh: ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= ∑ = T j jj xhsignxH 1 )()( α (1) 13 Các bộ phân lớp yếu hj(x) là các đặc trưng Haar – like đơn giản. Một tập rất lớn các bộ phân lớp yếu được sử dụng để phân lớp một cửa sổ ảnh là face hoặc non face. Viola và Jones đề xuất 4 mẫu đặc trưng vô hướng cơ bản cho phát hiện khuôn mặt. Sau đó Rainer Lienhart mở rộng thành 14 mẫu đặc trưng [3]. Trong [1], Viola và Jones đã đề xuất một sự biễu diễn ảnh gọi là “hàm ảnh”, đề xuất này cho phép các đặc trưng Haar – like được tính toán cực kì nhanh. Tuy nhiên, để đạt kết quả tốt, một hệ thống dựa trên AdaBoost cần một số lượng khổng lồ các đặc trưng. Ví dụ, trong một cửa số quét kích thước 20 × 20, có khoảng 10.000 các đặc trưng cho các hình dáng, kích thước và vị trí khác nhau. Điều này làm giảm đáng kể tốc độ của bộ phát hiện nếu chúng ta sử dụng nhiều strong classifier trong cascade tree. Hơn nữa, sự chính xác của bộ phân lớp cuối cùng phụ thuộc vào các bộ phân lớp yếu (các đặc trưng Haar – like). Vì vậy nếu khả năng phân tách (face/nonface) các mẫu background khó của các đặc trưng Haar – like không tốt thì kết quả phát hiện thường có nhiều phát hiện sai. 3.1.2.2 Xây dựng cascade của các bộ phân lớp mạnh Hầu hết các bộ phân lớp tốt cần nhiều thời gian để có các kết quả phân lớp bởi vì chúng cần xem xét đến một số lượng lớn các đặc trưng của mẫu. Cấu trúc cascade của các bộ phân lớp mạnh đã được đề xuất để giảm thời gian thực thi và giảm tỉ lệ phát hiện sai. Hình 1 minh họa cấu trúc cascade của các bộ phân lớp mạnh. 14 Hình 1. Cascade của các bộ phân lớp mạnh. Nơi một vùng ứng viên có thể bị loại tại bất kì giai đoạn nào Cascade tree có một số thuận lơi. Mỗi giai đoạn là một bộ phân lớp mạnh. Trong suốt quá trình phát hiện khuôn mặt. Mỗi cửa sổ được phân tích tuần tự bởi mỗi bộ phân lớp giai đoạn. Một cửa số có thể bị loại (kết luận non face) hoặc đi qua bộ phân lớp giai đoạn này. Trong suốt quá trình huấn luyện, mỗi bộ phân lớp được huấn luyện bởi các mẫu bị phân lớp sai ở bộ phân lớp trước. Nghĩa là chúng sẽ tập trung để học các mẫu background khó. Vì vậy sự kết hợp của các bộ phân lớp trong cascade sẽ giảm tỉ lệ phát hiện sai. Hơn nữa với cấu trúc này, các bộ phân lớp dễ dàng nhận ra các background dễ và loại bỏ chúng ở các bộ phân lớp đầu. Vì vậy cấu trúc cascade giải quyết được bài toán thời gian thực thi. Một cách tổng quát, cấu trúc cascade cải tiến đáng kể thời gian thực thi và các kết quả phát hiện phụ thuộc hoàn toàn vào các bộ phân lớp yếu hay các đặc trưng Haar – like. 3.2 Local Binary Pattern(Mẫu nhị phân cục bộ) 3.2.1 Local Binary Pattern LBP là một toán tử kernel 3×3, nó tổng quát hóa cấu trúc không gian cục bộ của một ảnh. Ojala và các đồng nghiệp [8] đã giới thiệu phương pháp LBP và chỉ ra khả năng phân tách cao của chúng cho sự phân lớp vân. Tại một vị trí pixel (xc, yc) cho trước, LBP được định nghĩa như một chuỗi nhị phân có trật tự dựa trên sự so sánh giá trị độ xám của pixel trung tâm (xc, yc) và 8 pixel lân cận của nó. Như vậy mỗi pixel sẽ được biểu diễn bởi một chuỗi nhị phân, giá trị thập phân của chuỗi nhị phân này chính là giá 15 trị của pixel trung tâm trong sự biểu diễn bởi toán tử LBP. Hình 2 minh họa sự tính toán giá trị LBP. Hình 2. Ví dụ sự tính toán LBP Giá trị thập phân của của chuỗi LBP có thể được biểu diễn như sau: ( ) ( )∑ = −= 7 0 2, n n cncc ggsyxLBP (2) Với gc là giá trị độ xám của pixel trung tâm (xc, yc), gn là giá trị độ xám của pixel thứ n trong lân cận 8 của pixel trung tâm. Hàm sn được định nghĩa như sau: ( ) ⎩⎨ ⎧ < ≥= 00 01 xif xif xs (3) Bằng cách định nghĩa này, toán tử LBP bất biến đối với bất kỳ sự biến đổi độ sáng đều và bảo toàn trật tự mật độ các pixel trong một lân cận cục bộ. Sau đó, Ojala và các đồng nghiệp [10] đã mở rộng toán tử LBP cũ đến một lân cận tròn với các bán kính khác nhau. LBPP, R kí hiệu sự xem xét đến P pixels lân cận trên một vòng tròn có bán kính R. Hình 3 minh họa toán tử LBPP,R. 16 Hình 3. Minh họa toán tử LBP mở rộng với các giá trị P và R khác nhau Giá trị các pixel được nội suy cho các điểm không nằm trong tâm của một pixel. Nếu tọa độ của pixel tâm là (xc, yc) thì tọa độ của P pixel lân cận trên đường tròn tâm (xc, yc) bán kính R (tính theo đường tròn lượng giác) là: ( ) ( ) 1}-P ,1, {0, p,/2sin /2cos …=Π+= Π+= PpRyy PpRxx cp cp (4) Để xác định giá trị giá trị của các pixel lân cận không nằm trong tâm của một pixel, chúng tôi sử dụng phép nội suy song tuyến tính. (Chi tiết được trình bày trong phụ lục B). Trong [10] các tác giả đã kết luận rằng: hầu hết các thông tin vân (texture) trong ảnh được chứa trong một tập con của các mẫu LBP. Các mẫu này được gọi là các mẫu đồng nhất (uniform patterns). Các mẫu đồng nhất chứa tối đa hai sự chuyển đổi bit từ 0 đến 1 hoặc từ 1 đến 0. 11111111, 00000110 hoặc 10000111 là ví dụ cho các mẫu đồng nhất. Toán tử LBPP,R đồng nhất được kí hiệu là 2.u RPLBP . Với chuỗi LBP có chiều dài P thì số mẫu có tối đa hai sự chuyển đổi (mẫu đồng nhất là) P(P-1). Có hai mẫu không có sự chuyển đổi nào là mẫu toàn 0 hoặc 1. Việc sử dụng mẫu LBP đồng nhất có hai lợi điểm quan trọng. Thứ nhất là tiết kiệm bộ nhớ, vì trường hợp LBP tổng quát chúng ta có 2P mẫu có thể, nhưng nếu chỉ xét mẫu đồng nhất thì chúng ta có tối đa là P(P+1) + 2 17 nếu chúng ta sử dụng toán tử 2.u RPLBP . Lợi điểm thứ hai là LBP u2 chỉ phát hiện những mẫu vân cục bộ quan trọng như các điểm, các điểm cuối đường thẳng, biên cạnh và các góc. Hình 4 minh họa một số mẫu vân quan trọng có thể được phát hiện bởi LBPu2. Hình 4. Từ trái sang phải, các mẫu vân cơ bản: điểm chấm, điểm chấm nhạt, điểm cuối đường thẳng, biên cạnh, góc được phát hiện bởi 2uLBP Bởi vì khả năng phân tách và chi phí tính toán thấp, LBP trở nên rất phổ biến trong nhận dạng mẫu LBP đã được áp dụng cho phát hiện khuôn mặt [2,17], nhận dạng khuôn mặt [2, 15], xác thực khuôn mặt [18], truy vấn ảnh [16]. 3.2.2 Áp dụng LBP cho bài toán phát hiện khuôn mặt Trong [2], A. Hadid và các đồng nghiệp đã đề xuất một hệ thống phát hiện mặt người dựa trên sự biểu diễn của LBP cho khuôn mặt. Họ đã đề xuất một cách biểu diễn mới hiệu quả cho các ảnh có độ phân giải thấp. Sự đặc biệt của cách biểu diễn này là sử dụng các vùng chồng lấp và toán tử LBP trong một lân cận 4 - 1,4LBP được tính toán trong các vùng chồng lấp này. Thêm vào đó, họ tăng cường sự mô tả đặc trưng (vân) của toàn bộ khuôn mặt bằng cách tính toán histogram 21,8uLBP toàn cục trên toàn bộ ảnh khuôn mặt. Trong cách biểu diễn này, đặc trưng vân của toàn bộ ảnh khuôn mặt được mã hóa bởi LBP trong khi đặc trưng hình dáng của khuôn mặt được phục hồi bởi sử kết hợp các histogram LBP cục bộ. Trong luận văn này, chúng tôi xem xét một ảnh kích thước 20×20 như độ phân giải chuẩn. Sự biểu diễn khuôn mặt trong luận văn dựa trên ý tưởng chính trong [2], tuy nhiên chúng tôi phân chia ảnh 20×20 thành 9 vùng chồng lấp, mỗi vùng có kích thước 10×10 pixels (kích thước chồng lấp = 5 pixel). Từ mỗi vùng, chúng tôi tính toán 16 bin histogram (histogram có 16 thành phần) sử dụng toán 18 tử 1,4LBP , kết hợp các histogram của từng vùng chúng tôi được một histogram có 144 thành phần. Sau đó, chúng tôi áp dụng toán tử 21,8uLBP đến toàn bộ ảnh 20×20 và tính toán được 58 bin histogram cho các mẫu đồng nhất, các giá trị không đồng nhất chứa trong bin thứ 59. Như vậy ta có histogram có 59 thành phần. Kết hợp histogram 144 thành phần và histogram toàn cục 59 thành phần đã tính toán chúng tôi được histogram có 59+144 = 203 thành phần. Histogram này được sử dụng như sự biễu diễn khuôn mặt. Hình 5 minh họa cách sử dụng LBP để biểu diễn khuôn mặt trong luận văn. Hình 5. Sự biễu diễn khuôn mặt: histogram đặc trưng được tạo bằng cách kết hợp histogram LBP cục bộ và histogram LBP toàn cục. 3.3 Phân tích và đánh giá phát hiện mặt người sử dụng AdaBoost và LBP 3.3.1 Cơ sở dữ liệu cho huấn luyện phát hiện khuôn mặt với phương pháp AdaBoost Để huấn luyện bộ phát hiện AdaBoost, một tập các ảnh khuôn mặt và không khuôn mặt được sử dụng. Tập ảnh để huấn luyện khuôn mặt, chúng tôi lựa chọn 11000 ảnh từ 14051 ảnh khuôn mặt của cơ sở dữ liệu chuẩn FERET [13] và tập ảnh khuôn mặt của MIT [24]. Với mỗi ảnh được lựa chọn, chúng tôi chọn vùng ảnh chứa khuôn mặt trong ảnh và scale vùng ảnh này về độ phân giải chuẩn 20×20 pixel. Một vài ảnh huấn huyện trong tập khuôn mặt được minh họa trong hình 6. 19 Hình 6. Ví dụ của các ảnh khuôn mặt được sử dụng để huấn luyện AdaBoost Tập các ảnh huấn luyện non – face sử dụng để huấn luyện bộ phát hiện AdaBoost được tạo từ 5717 ảnh mà không chứa bất kì khuôn mặt nào. Có khoảng 950 triệu cửa số kích thước 20×20 trong tập các ảnh non – face. Mỗi bộ phân lớp mạnh trong cascade tree được huấn luyện với 11000 ảnh khuôn mặt và 5000 ảnh non – face bị phân lớp sai từ các bộ strong classifier trước nó (kích thước 20×20 pixel). Để huấn huyện AdaBoost, chúng tôi sử dụng thư viện mã nguồn mở OpenCv [26] được tạo bởi Rainer Lienhart [3]. Tuy nhiên kết quả đạt được sau khi huấn luyện không tốt bằng thư viện của OpenCv. Vì vậy, trong luận văn này, các kết quả thống kê của AdaBoost được tính từ kết quả của bộ phát hiện AdaBoost của OpenCv. 3.3.2 Kết quả thực nghiệm của phương pháp AdaBoost Chúng tôi sử dụng mô hình cascade của các bộ phân lớp mạnh với số phân lớp mạnh (số giai đoạn) lần lượt là 20 và 25. Hiệu suất của hệ thống được kiểm tra trên tập dữ liệu MIT + CMU [7]. Đây là tập dữ liệu kiểm tra chuẩn được sử dụng để kiểm tra hiệu năng của hầu hết các thuật toán phát hiện mặt người [1][2]. Bộ dữ liệu MIT + CMU chứa 130 ảnh với 507 khuôn mặt. Bảng 1 chỉ ra kết quả của bộ phát hiện khuôn mặt AdaBoost. 20 Bảng 1. HIỆU SUẤT CỦA BỘ PHÁT HIỆN ADABOOST TRÊN TẬP DỮ LIỆU MIT – CMU Phương pháp Số phân lớp mạnh Tổng số đặc trưng Haar – like đã sử dụng Số khuôn mặt phát hiện chính xác Số khuôn mặt phát hiện sai Tỉ lệ phát hiện chính xác Tổng thời gian xử lí 130 ảnh (giây) Thời gian trung bình để xử lí một ảnh AB20 20 1925 467 202 92.11% 23.325 0.179 AB25 25 2913 452 40 89.15% 25.337 0.202 Trên bộ xử lí 2.0 GHz Pentium IV, RAM 1Gb, bộ phát hiện AdaBoost có thể xử lí một ảnh kích thước 276×343 khoảng 0.172 giây. Tỉ lệ tăng và kích thước dịch chuyển của cửa số trượt lần lượt là 1.2 và 2. Hình 7 minh họa một số kết quả từ bộ phát hiện AdaBoost. Trong hình 7B, AB25 phát hiện chính xác 11 khuôn mặt (sót 3 khuôn mặt). Thời gian để xử lí ảnh này là 0.278 giây. Trong khi đó, trong hình 7A, với AB20, số khuôn mặt phát hiện chính xác là 12 (2 khuôn mặt bị sót), thời gian để xử lí ảnh với AB20 là 0.230 giây < 0.278 giây của AB25. Trong cả hai trường hợp, số ảnh phát hiện sai là 0. Trong hình 7D, mặt dù được xử lí với AB25 nhưng vẫn còn 2 phát hiện sai, điều này có thể giải thích là do các đặc trưng Haar – like quá đơn giản để có thể phân tách các background khó này. 21 22 23 Hình 7. Kết quả phát hiện khuôn mặt trên tập MIT + CMU. Nếu một số lượng lớn bộ phân lớp mạnh được sử dụng trong cascade tree thì thời gian xử lí sẽ tăng và một số khuôn mặt bị sót. Một vài background khó bị phân lớp sai là khuôn mặt (false positive) 3.3.3 Cơ sở dữ liệu cho huấn luyện phát hiện khuôn mặt với phương pháp LBP Tập ảnh khuôn mặt dùng để huấn luyện phương pháp LBP chứa 11000 ảnh từ 14501 ảnh khuôn mặt trong cơ sở dữ liệu FERET và tập ảnh khuôn mặt của MIT [24], (tương tự như tập ảnh khuôn mặt dùng huấn luyện AdaBoost). Để thu thập các mẫu non – face chúng tôi sử dụng thuật toán “boot trap” [12] trong 5 lần lặp. Đầu tiên, chúng tôi thực 24 thi bộ phát hiện được huấn luyện bởi thuật toán AdaBoost (mục 3.3.1) và thu thập 3000 mẫu non – face bị phân lớp sai (bị phân lớp là face). Kết hợp 3000 mẫu non – face này với 3000 mẫu non – face được rút trích ngẫu nhiên từ tập các ảnh không chứa khuôn mặt (minh họa trong hình 8). Hình 8. Vài cửa sổ kích thước 20×20 được rút trích ngẫu nhiên từ một ảnh không chứa khuôn mặt nào để tạo các mẫu non – face cho bộ phát hiện LBP Như vậy, chúng tôi có 6000 mẫu non – face cho lần huấn luyện đầu tiên cho LBP. Sau đó, tại mỗi lần lặp, chúng tôi huấn luyện hệ thống, chạy bộ phát hiện LBP và thu thập 3000 mẫu non – face bị phân lớp sai và sử dụng chúng cho lần huấn luyện tiếp theo. Cuối cùng chúng tôi có 6000 + 15000 mẫu non – faces cho huấn luyện LBP. Để huấn luyện và kiểm tra bộ phát hiện LBP, chúng tôi sử dụng phương pháp Artifical Neral Network (ANN) (lí do sử dụng ANN sẽ được trình bày trong chương 4, mục 4.1). ANN được sử dụng là mạng truyền thẳng 3 lớp với thuật toán học lan truyền ngược. Số node nhập của ANN là 203; tương đương với số bin của histogram được trút trích bởi phương pháp LBP. Số node xuất của ANN là 1; nó sẽ trả về 1 nếu cửa số quét chứa khuôn mặt và trả về 0 trong trường hợp ngược lại. Số node ẩn của ANN được lựa chọn 25 dựa trên thực nghiệm; trong luận văn chúng tôi chọn là 12. Hàm truyền được chọn là hàm Tanh. ( ) ( )( ) xx xx ee ee x xx − − + −== cosh sinhtanh (5) Tốc độ học cho mạng nơ ron là 0.3. Giá trị này được chọn dựa trên các kết quả thực nghiệm. Để phát hiện các khuôn mặt trong ảnh, một cửa số quét kích thước 20×20 quét qua ảnh tại tất cả các tỉ lệ và các vị trí khác nhau. Tỉ lệ và độ dịch chuyển của cửa sổ lần lượt là 1.2 và 2 pixels. Tại mỗi lần lặp, biễu diễn LBP tính toán được từ cửa số quét sẽ là đầu vào cho bộ phân lớp ANN để quyết định là face hoặc non – face. Trong [2], A. Hadid và các đồng nghiệp đã thực hiện việc kiểm tra phương pháp rút đặc trưng LBP của họ trên một phần tập dữ liệu CMU + MIT (227 khuôn mặt trong 80 ảnh), kết quả báo cáo là LBP đạt hiệu suất phát hiện chính xác là 97.4%, số phát hiện sai là 0. Từ kết quả của A. Hadid chúng ta có thể nhận thấy khả năng phân tách face – nonface rất tốt của LBP. AdaBoost là thuật toán phát hiện mặt người nhanh nhất tính cho đến thời điểm hiện tại. Tuy nhiên, cascade của các bộ phân lớp mạnh phụ thuộc hoàn toàn vào các bộ phân lớp yếu (các đặc trưng Haar – like) do đó các kết quả phát hiện thường có nhiều phát hiện sai. Trong số số lượng các bộ phân lớp mạnh trong cascade mà luận văn ước lượng, AdaBoost đạt tỉ lệ phát hiện chính xác cao nhất với 92.11% khi sử dụng cascade của 20 bộ phân lớp mạnh. Tuy nhiên số phát sai quá nhiều với 202. Nếu chúng ta tăng số phân lớp mạnh trong cascade tree lên 25, số lượng phát hiện sai sẽ giảm xuống nhưng thời gian thực thi có thể tăng lên và quan trọng hơn là tỉ lệ phát hiện đúng có thể bị giảm xuống. Mỗi cửa quét nên thông qua tất cả các bộ phân lớp mạnh trong cascade tree để đưa ra quyết định là khuôn mặt. Các bộ phân lớp mạnh ở phía sau của cascade tree sẽ 26 tập trung vào các mẫu khó (difficult positive), do đó nếu một mẫu là khó, trong nhiều trường hợp, nó rất có thể bị loại bởi các bộ phân lớp cuối trong cascade tree. Nghĩa là nếu chúng ta sử dụng nhiều bộ phân lớp mạnh trong cascade tree thì tỉ lệ phát hiện chính xác sẽ giảm xuống. Chúng tôi đã thực nghiệm với 15 bộ phân lớp mạnh trong cascade tree, tỉ lệ phát hiện chính xác là 92.50% nhưng số phát hiện sai rất lớn: 1472. Bộ phát hiện LBP trong thực nghiệm của chúng tôi tốn tới 27635 giây để xử lí tất cả các ảnh trong tập MIT + CMU, và trung bình bộ phát hiện LBP cần 212.58 giây để xử lí một ảnh. Tốc độ xử lí của LBP là rất chậm nếu so sánh với bộ phát hiện AdaBoost. Do đó, nếu chỉ sử dụng LBP để phát hiện khuôn mặt thì chúng ta không thể áp dụng trong ứng dụng yêu cầu thời gian thực. Để thừa hưởng các thuận lợi của phương pháp AdaBoost về tốc độ xử lí; phương pháp LBP về độ chính xác, và để giải quyết khuyết điểm của hai phương pháp, trong luận văn chúng tôi đề xuất một mô hình kết hợp của AdaBoost và LBP trong chương 4.