Chương 2. MỘT SỐ PHƯƠNG PHÁP NHẬN DẠNG VÀ THEO DÕI CHUYỂN ĐỘNG CỦA MẮT NGƯỜI
2.3 Phương pháp phát hiện khuôn mặt
Hai phương pháp khác nhau được thực hiện trong luận văn. Đó là:
(1) Phương pháp phát hiện khuôn mặt dựa trên đặc trưng Haar-like sử dụng AdaBoost
(2) Phương pháp phát hiện khuôn mặt dựa trên dịch chuyển trung bình thích nghi liên tục
2.3..1 Phương pháp phát hiện khuôn mặt dựa trên đặc trưng Haar-like sử dụng AdaBoost
2.3.1.1. Giới thiệu
Hơn một thập kỷ qua, có rất nhiều công trình nghiên cứu về bài toán xác định khuôn mặt người từ ảnh đen trắng, ảnh xám, đến ảnh màu như ngày nay.
Các nghiên cứu đi từ bài toán đơn giản là ảnh chỉ chứa một khuôn mặt người nhìn thẳng vào thiết bị thu hình và đầu ở tư thế thẳng đứng, cho đến ảnh màu với nhiều khuôn mặt người trong cùng ảnh, khuôn mặt có quay một góc nhỏ, hay bị che khuất một phần, và với ảnh nền của ảnh phức tạp (ảnh chụp ngoài thiên nhiên) nhằm đáp ứng nhu cầu thật sự cần thiết của con người.
Bài toán xác định khuôn mặt người là một kỹ thuật máy tính để xác định các vị trí và các kích thước của khuôn mặt trong ảnh bất kỳ (ảnh kỹ thuật số).
Kỹ thuật này nhận biết các đặc trưng khuôn mặt và bỏ qua những thứ khác như:
toà nhà, cây cối, cơ thể...
Một số ứng dụng của bài toán xác định khuôn mặt là: hệ thống tương tác giữa người và máy (điều kiển máy tính qua các cử động của khuôn mặt), hệ thống nhận dạng người (giúp cho các cơ quan an ninh quản lý con người), hệ thống quan sát theo dõi, hệ thống quản lý việc ra vào cho các cơ quan và công ty, hệ thống kiểm tra người lái xe có ngủ gật hay không, hệ thống phân tích cảm xúc trên khuôn mặt, và hệ thống nhận dạng khuôn mặt cho các máy ảnh kỹ thuật số...
Hiện nay có rất nhiều phương pháp nhận dạng khuôn mặt người, dựa vào các tính chất của các phương pháp, ta có thể chia ra làm bốn hướng tiếp cận chính như sau:
- Hướng tiếp cận dựa trên tri thức: mã hoá hiểu biết của con người về các loại khuôn mặt và tạo ra các tập luật để xác định khuôn mặt.
- Hướng tiếp cận dựa trên đặc tả không thay đổi: mục tiêu các thuật toán tìm ra các đặc trưng mô tả cấu trúc khuôn mặt người (các đặc trưng không thay đổi với tư thế, vị trí đặt thiết bị thu hình, độ sáng tối thay đối...).
- Hướng tiếp cận dựa trên đối sánh mẫu: dùng các mẫu chuẩn hay các đặt trưng của khuôn mặt người.
- Hướng tiếp cận dựa trên diện mạo: phương pháp học từ một tập ảnh huấn luyện mẫu để xác định khuôn mặt người.
Trong chương này chúng tôi xác định vị trí khuôn mặt người sử dụng hướng tiếp cận dựa trên diện mạo, dựa trên các đặc trưng Haar-like sử dụng kỹ thuật Boosting để xác định khuôn mặt. Mã nguồn được dựa trên thư viện mã nguồn mở OpenCV.
2.3.1.2. Trích chọn đặc trưng cho AdaBoost
Hệ thống phát hiện đối tượng trên hình ảnh dựa trên các đặc trưng đơn giản. Có nhiều lý do để chọn việc xử lý dựa trên đặc trưng mà không thực hiện
với xử lý trực tiếp trên các điểm ảnh. Lý do phổ biến nhất là các đặc trưng có thể dựa trên các tri thức hữu hạn của các dữ liệu huấn luyện để mã hóa ra các tri thức nhận dạng. Ngoài ra một hệ thống phát hiện đối tượng sử dụng đặc trưng thì xử lý sẽ nhanh hơn so với hệ thống dựa trên xử lý điểm ảnh.
Một loại đặc trưng đơn giản được sử dụng là đặc trưng Haar-like, là một loại đặc trưng thường được dùng cho bài toán nhận dạng trên ảnh. Đặc trưng Haar-like được xây dựng từ các hình chữ nhật có kích thước bằng nhau, dùng để tính độ chênh lệch giữa các giá trị điểm ảnh trong các vùng kề nhau. Có các tập hợp miền hình học chính như sau:
Hình 2.3. Các đặt trưng Haar-like cơ bản
Để áp dụng các đặt trưng này vào việc bài toán xác định mặt người, 4 đặt 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:
2. Đặc trưng đường:
3. Đặc trưng tâm:
Hình 2.4. Các miền hình học đặc trưng Haar-like
Lợi ích của đặ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.
Giả sử miền đen là dương và miền trắng là âm thì đặc trưng Haar-like 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):
ii(x,y) = ∑𝑥′≤𝑥∑𝑦′≤𝑦𝑖(𝑥′, 𝑦′) (2.3)
Hình 2.5. Ý 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 lũy tích như sau:
s(x,y) = s(x,y-1) + i(x,y) (2.4) ii(x,y) = ii(x-1,y) + s(x,y) (2.5)
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)) (2.6)
Hình 2.6. Cách tính giá trị ô đặ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.
2.3.1.3. Thuật toán AdaBoost
Các thuật toán học là một trong những phương pháp học máy, kết quả của nó có thể được cải thiện bằng cách kết hợp các thuật toán học cơ sở. Boosting là một trong những phương pháp đó, nó là một thuật toán hỗ trợ mạnh mẽ các kết quả thực nghiệm. Thuật toán đã được phân tích cẩn thận và đã được kiểm tra thực nghiệm bằng nhiều nghiên cứu trong cộng đồng. Một số thuật ngữ liên quan đến thuật toán mà trong chương này sử dụng đó là:
Bộ phân loại yếu: Một bộ phân loại yếu là một thuật toán học, nó chỉ cần thực hiện phân loại đúng các mẫu với tỷ lệ đủ lớn hơn 50%. Một giả thuyết được tạo ra bằng một bộ phân loại yếu được gọi là giả thuyết yếu và ký hiệu hm(x).
Bộ phân loại mạnh: Cho một tập hợp gồm N bộ phân loại yếu, một bộ phân loại mạnh được tạo ra bằng cách kết hợp tuyến tính các bộ phân loại yếu.
) ( . )
(
1
x h sign
x
H m
M
m
m
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:
HM(𝑥) = ∑𝑀𝑚−1ℎ𝑚(𝑥) (2.7)
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 số. Trong quá trình học, các trọng số 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 số chỉ cần thiết đối với thuật toán AdaBoost trước đâ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. 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) = ∑ 𝑒−𝑦,𝐻𝑀(x𝑖) (2.8) Thuật toán AdaBoost xây dựng hàm h(x) bằng cách giảm tối đa (2.8) Cho
HM-1(𝑥) = ∑𝑀−1𝑚−1ℎ𝑚(𝑥),
HM(𝑥) tốt nhất cho phân loại mạnh HM(𝑥) = HM-1(𝑥) + hm(𝑥) Là hàm dẫn tới giá trị nhỏ nhất:
Hm = arg min J(H(x)h(x)) (2.9) và hàm có giá trị nhỏ nhất được chứng minh là:
hM(𝑥) = 1
2 log𝑃(𝑦=+1|𝑥,𝜔
(𝑀−1))
𝑃(𝑦=−1|𝑥,𝜔(𝑀−1)) (2.10) Với 𝜔(𝑀−1) là trọng số tại thời điểm M.
Dùng công thức P(y|x, 𝜔) = P(x|y, 𝜔) P(y) và cho LM(𝑥) = 1
2 log𝑃(𝑥|𝑦=+1,𝜔)
𝑃(𝑥|𝑦=−1|,𝜔) (2.11) T = 1
2 [𝑙𝑜𝑔𝑃(𝑦=+1)
𝑃(𝑦=−1)] (2.12)
chúng ta có được LM(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 đó.
Ta có một phương pháp để tính phương trình (2.11), ứ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, 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 tín hiệu vi ba. 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)}.
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ể 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 của Z(1), Z(2), ..., Z(M-1) đã được chọn và trọng số cho là ωM−1, chúng ta có xấp xỉ p(x|y, ωM−1) bằng cách dùng phân bố của M đặc điểm:
p(x|y, ωM−1) ≈ p(z(1), z(2), …, z(M-1)), zk |y, ωM−1) = 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)
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(1)|y, ω(1))…
p(z(M-1)|y, ωM−2) p(zk|y, ω(M−1))
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ừ biểu đồ tính được qua đánh giá công nhận trọng số của các ví dụ huấn luyện sử dụng các trọng số ω(M−1).
Cho:
L(M)k (𝑥) = 𝑃(𝑧𝑘|𝑦=+1,ω(M−1))
𝑃(𝑧𝑘|𝑦=−1,ω(M−1)), và hk(M)(𝑥) = 1
2{L(M)k (x) − T}
chúng ta rút ra được tập hợp các phân lớp yếu hơn như sau:
Γ𝑀(𝑥) = {ℎ𝑘(𝑀)(𝑥)|∀k}
Các bước cơ bản của thuật toán được nêu như sau:
Cho một tập dữ liệu huấn luyện Z = {(x1, y1), (x1, y2),…, (xn, yn)} với X
xi là các mẫu huấn luyện và Y 1,1 là các nhãn (−1) chỉ rõ không phải là đối tượng hoặc (+1) là đối tượng, các nhãn này gán cho các mẫu huấn luyện tương ứng, một phân phối trọng số được khởi tạo đồng bộ 𝜔1(𝑖) = 1
𝑚 cho các mẫu. Dựa vào tập huấn luyện Z và trọng số 𝜔1(𝑖), một bộ phân loại yếu hm(x) được huấn luyện bằng cách áp dụng một thuật toán học, kết quả đầu ra là một giá trị nhị phân hoặc một giá trị thực cho biết độ tin cậy của quyết định. Trọng số m chỉ rõ độ quan trọng của hm(x) trong kết quả của bộ phân loại mạnh, trọng số này được tính toán dựa vào lỗi em của nó trên tập dữ liệu huấn luyện:
m m
m e
e ln 1 2.
1 . Cuối cùng trọng số 𝜔1(𝑖) được điều chỉnh sao cho các mẫu bị phân loại sai bởi hm(x)trở nên quan trọng hơn (trọng số tăng lên) so với các mẫu khác. Quá trình xử lý này được lặp lại, bộ phân loại yếu tiếp theo sẽ tập trung xử lý các mẫu bị phân loại sai bởi bộ phân loại hiện tại dựa trên các trọng số này.
Thuật toán dừng khi là một số lượng nhất định các bộ phân loại được huấn luyện hoặc đạt đến một tiêu chí nào đó (chẳng hạn như lỗi đã thấp hơn ngưỡng).
Thuật toán 2.1. Thuật toán AdaBoost
Đầu vào: Tập Z = {(x1, y1), (x1, y2),…, (xn, yn)} với
xi ϵ X là các mẫu huấn luyện và yi ϵ Y={-1,+1} là các nhãn chỉ đối tượng hay không phải đối tượng.
Số lớp yếu tối đa Mmax được kết hợp Đầu ra: H(𝑥) = sign|∑𝑀𝑚−1 ∝𝑚 ℎ𝑚(𝑥)| Phương pháp:
Bước 1: Khởi tạo giá trị 𝜔1(𝑖) = 1
𝑚
Bước 2: Suy diễn tiến While M < Mmax
(1) M M+1
(2) Chọn bộ phân loại yếu hm: X→{-1,+1} với lỗi 𝜀𝑚 = {ℎ𝑘(𝑀)(𝑥)|∀k} //Độ tốt của giả thuyết yếu được đo bằng hệ số lỗi của nó
(3) Chọn
m m
m
.ln 1 2 1
(4) Cập nhật 𝜔𝑖(𝑚) ← exp[𝑦𝑖𝐻𝑀(𝑥𝑖)] và phân phối 𝜔𝑖(𝑚) để ∑ 𝜔𝑖(𝑚) = 1
Một khi bộ phân loại yếu đã được nhận, AdaBoost sẽ chọn một tham số như trên. Dễ dàng thấy m quan trọng được gán cho hm. Chú ý rằng m 0
(chúng ta có thể giả định mà không mất tính tổng quát).
Phân phối 𝜔1(𝑖) ở bước cập nhất tiếp theo sẽ dùng các luật như trình bày giải thuật của thuật toán ở trên, tác dụng của các luật này là làm tăng trọng số của các mẫu chưa được phát hiện bởi hm và giảm trọng số của các mẫu phát hiện chính xác vì vậy trọng số tập trung vào các mẫu khó.
Phát hiện thu được cuối cùng H là tập hợp của Z bộ phân loại yếu trong đó mlà trọng số được gán cho hm.
Hình 2.7. Ví dụ minh họa cho thuật toán AdaBoost
2.3.2. Phương pháp phát hiện khuôn mặt dựa trên dịch chuyển trung bình thích nghi liên tục
Thuật toán dịch chuyển trung bình thích nghi liên tục xuất phát dựa trên nền tảng của thuật toán dịch chuyển trung bình, do vậy việc tính trọng tâm của đối tượng và dịch chuyển cửa sổ tìm kiếm sẽ thực hiện bằng thuật toán dịch chuyển trung bình [6] và Moment ảnh. Ý tưởng chính của thuật toán dịch chuyển trung bình thích nghi là tính trọng tâm của đối tượng dựa vào khung ảnh trước đó và kích thước của cửa sổ tìm kiếm được thay đổi chuyển động theo đối tượng. Những khuôn mặt được theo dõi trong chuỗi video, thuật toán dịch
chuyển trung bình thích nghi được thay đổi để đáp ứng với các vấn đề thay đổi xác suất phân bố màu. Sơ đồ khối của thuật toán được đưa ra dưới đây:
Hình 2.8. Sơ đồ giải thuật dịch chuyển trung bình thích nghi liên tục theo vết chuyển động
Ý tưởng chính của thuật toán dịch chuyển trung bình thích nghi liên tục có nghĩa là thuật toán thay đổi. Sự thay đổi của thuật toán có ý nghĩa sử dụng cho việc tiến bộ của một phân bố xác suất để tìm ra cao điểm chi phối gần nhất. Thuật toán chuyển đổi trung bình có thể được tóm tắt như sau;
Đúng Sai
Ảnh HSV
Tìm biểu đồ màu trong vùng tính
Tìm xác suất phân bố màu Tìm trọng tâm của khối
lượng cửa sổ tìm kiếm
Đưa trọng tâm cửa sổ tìm kiếm về trọng tâm
của khối
Hội tụ?
Chọn vùng màu đặc trưng ban đầu
Hiệu chỉnh kích thước vùng tính
Hiệu chỉnh kích thước cửa sổ tìm kiếm
Xuất giá trị tọa độ trọng tâm và góc xoay
Thuật toán 2.2. Thuật toán dịch chuyển trung bình
Đầu vào: Tập ảnh gồm N với kích thước của mỗi ảnh là m x n.
Đầu ra: Hội tụ các vị trí của ảnh.
Phương pháp
Bước 1: Chọn một kích thước cửa sổ tìm kiếm Bước 2: Chọn vị trí ban đầu của cửa sổ tìm kiếm
Bước 3: Tính toán vị trí trung bình trong các cửa sổ tìm kiếm
Bước 4: Trung tâm của cửa sổ tìm kiếm ở vị trí trung bình được tính trong bước 3
Bước 5: Lặp lại các bước 3 và 4 cho đến khi hội tụ (hoặc cho đến khi các vị trí trung bình di chuyển ít hơn một ngưỡng)
Có nghĩa là vị trí (trọng tâm) trong cửa sổ tìm kiếm có thể được tính như sau;
1) Tìm các thời điểm 0 M00 = ∑ ∑ I(xy)x y
2) Tìm những thời điểm đầu tiên cho x và y M10 = ∑ ∑ xI(xy)x y ; M01 = ∑ ∑ yI(xy)x y
3) Sau đó, vị trí cửa sổ tìm kiếm trung bình (trọng tâm) là 𝑥𝑐 = M10
M00 𝑎𝑛𝑑 𝑦𝑐 = M01 M00
Vị trí I(x, y) là giá trị các điểm ảnh (xác suất) tại vị trí (x, y) trong hình ảnh và x và y trên phạm vi cửa sổ tìm kiếm.
Thuật toán dịch chuyển trung bình này không thể được sử dụng để theo dõi một mình vì một kích thước cửa sổ làm việc ở một quy mô phân phối là không phù hợp với quy mô khác như các đối tượng màu sắc di chuyển hướng và
đi từ máy ảnh. Cửa sổ kích thước cố định nhỏ có thể bị mất hoàn toàn cho dịch đối tượng lớn trong bối cảnh đó. Cửa sổ có kích thước cố định lớn có thể bao gồm phụ tá(người khác hoặc bàn tay) và quá nhiều tiếng ồn.
Vì vậy, thay vì kích cỡ cửa sổ tìm kiếm cố định CAMSHIFT sử dụng một cửa sổ tìm kiếm liên tục thích ứng dựa trên những thông tin thời điểm 0. Thời điểm 0 là khu vực tìm thấy dưới cửa sổ tìm kiếm. Như vậy chiều cao và chiều rộng cửa sổ được thiết lập với chức năng của các thời điểm 0, được tìm thấy trong quá trình tìm kiếm. Ngoài ra kích thước ban đầu cửa sổ tìm kiếm không phải là một vấn đề đối với CAMSHIFT như kích thước cửa sổ sẽ được điều chỉnh theo sự phân bố xác suất. Tóm tắt của thuật toán được đưa ra dưới đây;
Thuật toán 2.3. Thuật toán dịch chuyển trung bình thích nghi liên tục Đầu vào: Ảnh có kích thước m x n
Đầu ra: Vị trí các mục tiêu Phương pháp
Bước 1: Chọn vị trí ban đầu của cửa sổ tìm kiếm
Bước 2: Thay đổi vị trí ở trên(có thể có một hoặc nhiều lần lặp lại); lưu trữ các thời điểm 0
Bước 3: Thiết lập kích thước cửa sổ tìm kiếm bằng một hàm của thời điểm 0 được tìm thấy trong bước 2
Bước 4: Lặp lại bước 2 và 3 cho đến khi hội tụ (có nghĩa là vị trí di chuyển ít hơn một ngưỡng)
Hình 2.9. Cửa sổ tìm kiếm của Camshift