Đồ án Xây dựng ứng dụng phát hiện mặt người dựa trên màu da

hiện mặt người trong ảnh màu. Do thời gian ngắn, nên phương pháp được đưa ra tương đối đơn giản, do đó, độ chính xác cũng không cao. Nhưng bù lại, nó cũng có những ưu điểm là: Tốc độ nhanh. Có thể phát hiện được những khuôn mặt mờ (ảnh mờ, các chi tiết trên khuôn mặt không rõ). Không phụ thuộc vào hướng và kích thước khuôn mặt, tức là phương pháp không có sự giả định trước về hướng cũng như kích thước khuôn mặt. Nó có thể phát hiện các khuôn mặt trong ảnh với các hướng khác nhau và với các kích thước khác nhau. Không phụ thuộc vào độ sáng của ảnh. Không phụ thuộc vào số lượng các khuôn mặt trong ảnh. Các bước của phương pháp như sau: Bước 1: Phát hiện màu da. Đây là bước quan trọng then chốt là bước chính trong thuật toán, vì nếu không phát hiện được màu da thì sẽ không phát hiện được các khuôn mặt. Ngoài các điểm màu da trên cơ thể người như mặt, cổ, tay, chân, thì trong nền của ảnh cũng có nhiều điểm có màu tương tự màu da. Số lượng các điểm đó mà nhiều thì sẽ ảnh hưởng tới xác định các khuôn mặt sau này. Đầu vào của bước này là ảnh màu, đầu ra là ảnh nhị phân. Những điểm 1 (điểm trắng) là những điểm màu da. Bước 2: Lọc nhiễu. Do trong quá trình xác định màu da có thể phát hiện nhầm một số điểm gây ra những nhiễu điểm trong ảnh nhị phân. Do đó, khâu này sẽ loại bỏ những nhiễu điểm đó, để việc xác định các vùng trắng được thuận lợi và nhanh chóng. Đầu vào là ảnh nhị phân màu da ở trên, đầu ra là ảnh nhị phân được lọc nhiễu. Bước 3: Xác định các vùng trắng. Các điểm trắng trong ảnh nhị phân liên kết với nhau tạo thành các vùng trắng (dựa trên quan hệ 8 hàng xóm). Trong bước này ta sẽ phải xác định các vùng đó. Đầu vào của bước này là: ảnh nhị phân đã lọc nhiễu, và đầu ra là danh sách các vùng trắng tìm được. Mỗi vùng trắng được xác định bằng các tham số sau: Tọa độ: mỗi vùng trắng sẽ được bao bằng một hình chữ nhật. Do đó, tọa độ của vùng trắng là tọa độ của hình chữ nhật bao nó, bao gồm: tọa độ góc trái trên (x,y) và chiều rộng, chiều cao. Số điểm trắng trong vùng. Bước 4: Phân loại các vùng trắng. Ở bước 3 ta đã xác định được danh sách các vùng trắng. Trong bước cuối cùng này, ta sẽ phải phân loại các vùng trắng đó dựa trên một số tiêu chí để xác định xem vùng trắng nào là mặt. Đầu vào của bước này là danh sách các vùng trắng, đầu ra là danh sách các tọa độ vùng mặt (nếu 1 vùng trắng được xác định là vùng mặt, thì trong đầu ra, ta chỉ giữ lại tọa độ của vùng trắng đó (hình chữ nhật bao vùng trắng), còn tham số “số điểm trắng” sẽ không cần phải giữ lại trong đầu ra). Sơ đồ khối của phương pháp như sau: Hình 2.1: Sơ đồ khối của phương pháp Sau đây ta sẽ đi vào chi tiết các bước trong phương pháp. 2.2. Chi tiết các bước 2.2.1. Phát hiện màu da Trong bước này ta sẽ phải duyệt qua các điểm trong ảnh vào. Tại mỗi điểm, ta sẽ phải xác định xem nó có phải là màu da hay không? Nếu là màu da, ta sẽ gán cho giá trị tại điểm đó bằng 1, nếu không ta sẽ gán giá trị 0. Kết quả ta có 1 ảnh nhị phân, với các điểm 1 (điểm trắng) là các điểm màu da. Sơ đồ khối của bước này như sau: Hình 2.2: Vị trí của khâu trong phương pháp Để xác định điểm màu da, dựa trên 2 tiêu chí: Công thức màu da Histogram Một điểm trên ảnh màu vào sẽ được coi là màu da nếu thỏa mãn cả 2 tiêu chí trên. 2.2.1.1. Công thức màu da Công thức này đã được giới thiệu ở chương 1 (mục 1.3.4.1). Công thức được các tác giả C. Garcia, G. Zikos, G. Tziritas đưa ra. Công thức được xây dựng trên cả hệ màu YCrCb và HSV. Trong phương pháp của ta chỉ sử dụng công thức trên hệ màu YCrCb. Công thức như sau: Hình sau minh họa sự phân bố của các điểm màu da trong không gian màu YCrCb: Hình 2.3: Sự phân bố các điểm màu da trong không gian YCrCb Qua hình vẽ, ta thấy ngay, các điểm màu da phân bố rất gọn trong không gian màu YCrCb. Đó là lý do vì sao ta chọn công thức trên hệ màu này. So sánh với trên không gian màu HSV: Hình 2.4: Sự phân bố các điểm màu da trong hệ màu HSV Rõ ràng trên không gian màu HSV, các điểm màu da rất phân tán. Trở lại với công thức, ta đã biết, khi chuyển sang hệ màu YCrCb từ RGB, trong công thức chuyển đổi có các tham số là Kr và Kb. Các giá trị của các tham số này phụ thuộc vào chuẩn được chọn (như BT601, BT709). Vậy trong công thức các tác giả sử dụng chuẩn nào? Đó là chuẩn cũ BT601, với Kb=0,114; Kr=0,299. Công thức chuyển đổi: Trong đó: R, G, B thuộc [0,1]. Y thuộc [0,1]. Pr, Pb thuộc [-0,5;0,5]. Sau khi xác định được chuẩn chuyển đổi rồi thì cũng mới chỉ tính được các giá trị analog còn gọi là YPrPb, với Y thuộc [0; 1]; Pr, Pb thuộc [-0.5; 0.5], còn trong công thức là các giá trị số YCrCb (các số nguyên), tức là phải thêm 1 bước rời rạc hóa nữa. Ở đây, ta sẽ chuyển đổi giải giá trị cho các thành phần Y, Pr, Pb bằng cách nhân chúng với 256. Như vậy, Y sẽ có giá trị trong đoạn [0; 256]; Cr, Cb sẽ có giá trị trong đoạn [-128; 128]. Tóm lại, các bước thực hiện như sau: với mỗi điểm trong ảnh màu, ta sẽ lấy về các giá trị R, G, B của nó. Sau đó, tính các giá trị YPrPb theo chuẩn BT601. Tiếp theo nhân các giá trị YPrPb vừa tính được với 256, được các giá trị YCrCb tương ứng. Cuối cùng áp dụng công thức ở trên. 2.2.1.2. Histogram Phương pháp xác định màu da dựa trên histogram được lấy theo ý tưởng của K. Sandeep và A.N. Rajagopalan trong mục 1.3.2. Histogram được tổng hợp trên một tập ảnh màu da (tập ảnh mẫu được chuẩn bị trước), nhưng không phải trên hệ màu RGB mà là trên hệ màu HSV và trên 2 thành phần H và S (histogram 2 chiều). Hệ màu HSV đã được trình bày trong chương 1. Công thức chuyển đổi từ RGB sang HSV: Trong đó: max=max(r,g,b). min=min(r,g,b). các thành phần màu r,g,b có giá trị nằm trong đoạn [0,1]. Các giá trị H, S tính được trong công thức này là các số thực (analog), H nằm trong đoạn [0; 360), còn S nằm trong đoạn [0; 1]. Nhưng trong tổng hợp histogram, yêu cầu các giá trị H, S phải là các số nguyên. Do đó, ta cần chuyển đổi dải giá trị của chúng. Với H ta giữ nguyên giải giá trị, chỉ đưa về số nguyên bằng thao tác cắt (không làm tròn). Còn với S ta nhân với 100 để đưa về dải giá trị [0; 100]. Lý do tại sao không xây dựng trên hệ màu RGB, vì hệ màu này phụ thuộc vào độ sáng. Ví dụ, cùng 1 điểm trên 1 khuôn mặt, khi ánh sáng thay đổi thì giá trị RGB ứng với điểm đó sẽ thay đổi. Còn trong hệ màu HSV, khi ánh sáng thay đổi thì chỉ có thành phần V (đặc trưng cho độ sáng) thay đổi, còn 2 thành phần HS không đổi. Ví dụ: với RGB = (10; 20; 30) và RGB = (40; 80; 120), cùng là 1 màu nhưng màu sau sáng hơn, đều cho cùng 1 giá trị HS là: (210; 0.67). Điều đó có nghĩa là việc tổng hợp histogram màu da này sẽ không phụ thuộc vào ánh sáng. Một số ảnh được sử dụng trong tổng hợp histogram như: Hình 2.5: Một số mặt người được dùng trong tổng hợp histogram màu da Trong các ảnh này không phải tất cả các điểm đều là điểm màu da nhưng các điểm màu da chiếm phần lớn, nên trong histogram, các cột ứng với điểm màu da vẫn sẽ cao vọt hơn so với các điểm khác. Sau khi tổng hợp xong histogram từ tập ảnh, histogram đó sẽ được chuẩn hóa, tức là chia chiều cao của các cột cho tổng số điểm được xét (tổng số điểm trong toàn tập ảnh) để đưa các giá trị trên histogram về dải [0; 1). Việc xác định màu da sẽ được thực hiện như sau: với mỗi điểm trong ảnh vào, ta tính các thành phần H, S (giá trị nguyên) của nó. Sau đó kiểm tra xem cột (H,S) đó trong histogram có lớn hơn 1 giá trị ngưỡng cho trước không. Nếu có thì đó là màu da. Giá trị ngưỡng là bao nhiêu được xác định qua thực nghiệm và tùy theo histogram được tổng hợp cụ thể (tùy theo tập ảnh mẫu sử dụng). Có giá trị ngưỡng này thì tốt cho ảnh này nhưng lại không tốt cho ảnh khác. Do đó không có giá trị ngưỡng tốt cho mọi ảnh. Chỉ có giá trị ngưỡng tốt cho nhiều ảnh. Việc thực nghiệm là để tìm ra giá trị ngưỡng tốt cho nhiều ảnh này. 2.2.1.3. Kết hợp 2 tiêu chí Một điểm trong ảnh vào sẽ được coi là màu da nếu thỏa mãn cả 2 tiêu chí trên: thỏa mãn công thức màu da và thỏa mãn histogram. Một số ảnh minh họa việc phát hiện màu da: Hình 2.6: Một số kết quả minh họa trong phát hiện màu da Tại sao lại phải kết hợp 2 tiêu chí. Vì qua thực nghiệm thấy rằng: khi áp dụng công thức màu da cũng như histogram thì đều có những phát hiện nhầm (điểm không phải là màu da lại bị phát hiện là màu da), nhưng sự nhầm lẫn này không giống nhau, tức là những điểm mà dùng công thức phát hiện nhầm thì dùng histogram lại không phát hiện nhầm và ngược lại những điểm mà dùng histogram phát hiện nhầm thì dùng công thức lại không phát hiện nhầm. Đồng thời những điểm đúng là màu da thì cả 2 cùng phát hiện đúng. Do đó việc kết hợp chúng lại sẽ giảm thiểu sai xót trong phát hiện màu da và không làm triệt tiêu sự phát hiện đúng của mỗi phương pháp. Hình 2.7:Minh họa phát hiện màu da theo từng tiêu chí. Từ trái sang phải: ảnh vào, ảnh màu da theo công thức, ảnh màu da theo histogram 2.2.2. Lọc nhiễu Vị trí của khâu này trong hệ thống xử lý: Hình 2.8: Vị trí của khâu lọc nhiễu trong phương pháp Đầu vào của khâu này là ảnh nhị phân, và đầu ra là ảnh nhị phân đã được lọc nhiễu. Trong quá trình phát hiện màu da ta có thể phát hiện nhầm các điểm gây ra các nhiễu điểm trắng trên ảnh nhị phân. Do đó ta cần loại bỏ các nhiễu điểm này, sẽ tốt cho bước sau: xác định vùng trắng, vì nếu không loại bỏ các điểm này thì mỗi nhiễu điểm sẽ bị phát hiện là 1 vùng trắng và như vậy sẽ làm tăng số lượng vùng trắng lên rất nhiều gây, tốn kém trong lưu trữ và xử lý. Như ta đã biết, để loại bỏ nhiễu thì có thể dùng bộ lọc trung bình hoặc trung vị. Dùng bộ lọc trung bình làm xuất hiện các giá trị mới (ngoài 0 (đen) và 255 (trắng)) và không hoàn toàn đưa giá trị của điểm nhiễu trắng đó về 0 mà chỉ làm nhỏ đi. Do đó, nếu sau đó ta duyệt lại ảnh sau khi lọc nhiễu mà chỉ kiểm tra điều kiện khác 0 thì điểm đó vẫn bị coi là trắng. Nếu không muốn bị nhầm lẫn này thì ta phải đặt ra giá trị ngưỡng thích hợp. Như vậy dùng bộ lọc trung bình trong trường hợp này không phù hợp. Do đó, ta dùng bộ lọc trung vị. Dùng bộ lọc này vừa không làm xuất hiện giá trị mới, lại vừa làm giá trị của điểm nhiễu trắng về 0 hoàn toàn. Kích thước của bộ lọc trung vị là bao nhiêu? Nếu dùng bộ lọc trung vị kích thước lớn thì khả năng loại nhiễu cũng sẽ tăng, không chỉ loại những nhiễu điểm mà còn loại những nhiễu to (nhiễu vùng), nhưng thời gian thực hiện sẽ lâu hơn rất nhiều. Do đó, để cân đối về mặt thời gian thực hiện, hướng tới phương pháp phát hiện mặt nhanh, nên ta sẽ sử dụng bộ lọc trung vị kích thước 3 x 3. Lý thuyết về bọ lọc trung vị sẽ không trình bày ở đây. Sau đây là một số kết quả lọc nhiễu. Hình 2.9: Minh họa kết quả lọc nhiễu Qua hình trên ta thấy, lọc nhiễu là 1 mũi tên trúng 2 đích. Nó không chỉ loại bỏ các nhiễu do phát hiện nhầm (những điểm trắng lác đác trên nền ảnh) mà còn loại bỏ các nhiễu do không phát hiện ra màu da (loại bỏ các điểm đen trên nền trắng). Tức là trên cánh tay hoặc trên mặt (nói chung là trên những vùng da) có những điểm không được phát hiện là màu da (nó trở thành điểm đen). Cũng có thể là do các điểm đó bị nhiễu giá trị, nên mặc dù nó nằm trên vùng da nhưng không có giá trị phù hợp là màu da. Nhưng nhờ lọc nhiễu mà ta đã biến nó thành trắng, nhờ đó tạo thành 1 vùng trắng nhất quán. 2.2.3. Xác định các vùng trắng Vị trí của khâu này trong hệ thống xử lý: Hình 2.10: Vị trí của khâu xác đinh vùng trắng trong phương pháp Đầu vào của khâu này là ảnh nhị phân (đã lọc nhiễu), đầu ra là danh sách các vùng trắng (mỗi vùng trắng được xác định bằng tọa độ và số điểm trắng trong vùng). Để xác định các vùng trắng, thuật toán cơ bản là gán nhãn hay còn gọi là thuật toán duyệt (có thể tìm hiểu về thuật toán này trong môn Toán rời rạc). Để duyệt thì thường có 2 kiểu là: duyệt theo chiều rộng và duyệt theo chiều sâu. Duyệt theo chiều sâu sử dụng đệ quy. Còn duyệt theo chiều rộng thì sử dụng hàng đợi. Nhưng vì ta xử lý trên điểm ảnh, mà 1 ảnh có kích thước rất lớn, vì thế mức đệ quy sẽ rất sâu, và qua thử nghiệm đã gây tràn stack. Vì thế, ta sẽ sử dụng tìm kiếm theo chiều rộng, cấp phát bộ nhớ sẵn có cho hàng đợi. Trong phần này ta sẽ trình bày 2 thuật toán phân vùng, một thuật toán phân vùng cơ bản, một thuật toán phân vùng nâng cao. 2.2.3.1. Thuật toán phân vùng cơ bản Như đã nói ở trên, ta sử dụng thuật toán gán nhãn cho các điểm trắng để phân vùng. Nhãn của mỗi điểm chính là chỉ số của vùng trắng mà nó thuộc vào. Ta có 1 ảnh nhị phân (đen và trắng). Trong ảnh có 1 tập các vùng trắng tách rời. Mỗi vùng trắng sẽ được đánh một con số nguyên, quá trình đánh số là liên tiếp (1,2,3...). Và mọi điểm trong vùng sẽ được gán nhãn bằng chỉ số nguyên của vùng đó. Chi tiết thực hiện thuật toán như sau: * Đầu vào: Ảnh nhị phân. * Đầu ra: Danh sách các vùng trắng tìm được trong ảnh nhị phân vào. * Xử lý: Về cấu trúc dữ liệu: Ta có một ảnh nhị phân vào, ta sẽ biểu diễn nó như một mảng 2 chiều nguyên, với giá trị 0 là điểm đen và khác 0 là điểm trắng. Ta đặt tên là Anh. Ta cần định nghĩa 1 cấu trúc lưu các tham số vùng trắng. Ta đặt tên là: VungTrang. Nó có các trường sau: Tọa độ của vùng trắng. Mỗi vùng trắng sẽ được bao bọc bằng 1 hình chữ nhật. Tọa độ của vùng trắng chính là tọa độ của hình chữ nhật bao nó. Tọa độ này bao gồm: tọa độ góc trái trên (x,y), chiều rộng, chiều cao của hình chữ nhật. Số điểm trắng trong vùng. Ta cần có 1 danh sách để chứa các vùng trắng tìm được. Ta đặt tên là DSVT. Bên cạnh danh sách có 1 biến đếm số lượng vùng trắng tìm được hiện tại. Biến đếm này cũng được sử dụng để đánh chỉ số cho vùng luôn. Các vùng sẽ được đánh chỉ số theo trình tự tìm được. Ta gọi biến này là: SLVT. Ta cũng cần có 1 hàng đợi để thực hiện duyệt, đặt tên là: HangDoi. Và cũng có 1 mảng 2 chiều chứa nhãn của các điểm trong ảnh. Ta gọi là Nhan. Khởi tạo: Khởi tạo mảng Nhan để đảm bảo các điểm đều chưa được gán nhãn. DSVT rỗng. SLVT = 0. HangDoi rỗng. Thực hiện: Duyệt qua các điểm trong ảnh nhị phân vào từ trái sang phải và từ trên xuống dưới. Với mỗi điểm ta kiểm tra xem điểm đó có phải là điểm trắng và chưa được gán nhãn không? Nếu không thỏa mãn thì bỏ qua, xét điểm tiếp theo. Nếu thỏa mãn, có nghĩa là ta đã tìm ra 1 vùng trắng mới. Điểm đang xét chính là điểm đầu tiên của vùng trắng này. Ta thực hiện xác định vùng trắng đó như sau: Tạo một biến cấu trúc VungTrang để chứa vùng trắng này, gọi là vt. Tăng biến đếm số lượng SLVT lên 1. Cập nhật biến cấu trúc vt khi biết thêm 1 điểm trắng thuộc vùng. Gán nhãn cho điểm đó bằng SLVT (giá trị hiện tại của SLVT là chỉ số của vùng trắng vừa tìm được). Đưa điểm đang xét vào HangDoi. Thực hiện vòng lặp. Chừng nào mà HangDoi còn chưa rỗng: Lấy 1 điểm ra khỏi HangDoi. Duyệt qua 4 điểm xung quanh nó: trái, phải, trên, dưới. Tại mỗi điểm, xét xem nó có phải là điểm trắng và chưa được gán nhãn không? Nếu không thỏa mãn thì bỏ qua, xét điểm tiếp theo. Nếu thỏa mãn thì: Gán nhãn cho nó bằng SLVT. Cập nhật biến cấu trúc vt khi biết thêm 1 điểm trắng thuộc vùng. Đưa vào HangDoi. Thêm vùng trắng vừa tìm được vào DSVT. Trả về DSVT Lưu đồ thuật toán: Begin End Điểm đang xét là điểm trắng và chưa gán nhãn? DSVT = Ø, SLVT ß 0, HangDoi = Ø Khởi tạo cho mảng nhãn Đưa con trỏ về điểm đầu tiên trong ảnh Chuyển sang điểm tiếp theo Tạo một vùng trắng mới SLVT ß SLVT + 1 Nhãn điểm đó = SLVT Đưa điểm vào vùng trắng, vào hàng đợi HangDoi khác rỗng? Lấy điểm ra khỏi hàng đợi Hàng xóm có phải là điểm trắng và chưa gán nhãn? Gán nhãn SLVT cho điểm đó Đưa vào vùng trắng, vào hàng đợi Thêm vùng trắng vào DSVT Hết ảnh? Lặp cho 4 hàng xóm (trái, phải, trên, dưới) Đ S S Đ Đ S Đ Hình 2.11: Thuật toán phân vùng cơ bản Trong các bước thực hiện trên, ta cần làm rõ thêm một số bước, đó là: cập nhật biến cấu trúc vt khi biết thêm 1 điểm trắng thuộc vùng. Thao tác này gồm 2 hành động: Tăng số lượng điểm trắng trong vùng lên 1. Cập nhật lại tọa độ của vùng. Để cập nhật lại tọa độ vùng trắng, ta phải xét xem điểm mới vào có vị trí như thế nào với hình chữ nhật bao vùng trắng hiện tại. Ta có 9 vị trí tương đối của điểm đang xét với hình chữ nhật bao vùng như sau: Hình 2.12: Vị trí tương đối của 1 điểm trắng so với vùng trắng hiện tại Nếu nó nằm trong hình chữ nhật thì không cần cập nhật. Nhưng nếu nằm ngoài (8 vị trí còn lại) thì tùy từng vị trí mà cập nhật lại tọa độ (x,y) hoặc chiều rộng, chiều cao. Hàng đợi được tổ chức xoay vòng để tiết kiệm bộ nhớ. Và còn 1 điểm nữa trong thuật toán là tại sao ta chỉ xét 4 điểm hàng xóm (trên, dưới, trái, phải) mà không xét cả 8 điểm. Bởi vì với việc xét 4 điểm ta vẫn duyệt qua được tất cả các điểm trắng trong vùng, bảo đảm không bỏ xót. Đồng thời nó còn giúp ta giảm bớt sự xét trùng lặp. Ví dụ như hình vẽ sau: Hình 2.13: Duyệt qua các điểm hàng xóm Nếu xét 8 điểm thì 2 điểm (1) và (2) sẽ xét trùng lặp các điểm (3), (4), (5), (6). Còn nếu xét 4 điểm thì nếu điểm (2) được duyệt trước thì khi duyệt tới điểm (1) thì điểm (1) chỉ duyệt lại duy nhất điểm (2). Nó sẽ tiết kiệm hơn về thực hiện và về cả số dòng lệnh. Sau đây là một số kết quả minh họa: Hình 2.14: Kết quả minh họa thuật toán phân vùng cơ bản Thuật toán này có ưu điểm là đơn giản, nhưng có một số tình huống nó không đạt được như mong muốn, đó là không loại bỏ được sự liên kết yếu. Liên kết yếu tức là 2 vùng trắng dính nhau theo 1 giao diện nhỏ. Ví dụ: Hình 2.15: Minh họa các liên kết yếu giữa các vùng trắng Khi phát hiện màu da đưa về ảnh nhị phân, sự dính nhau giữa các khuôn mặt hay xảy ra. Đây là 1 ví dụ: Hình 2.16: Ví dụ về liên kết yếu gặp phải trong phát hiện mặt Trong hình trên ta để ý thấy, có 1 đường nhỏ nối từ tai của người này sang mặt của người kia làm 2 vùng khuôn mặt bị gộp làm 1. Sự dính nhau này làm ta không phát hiện được. Sự dính nhau có thể là mạnh, cũng có thể là yếu. Ta cố gắng loại bỏ các liên kết yếu để phát hiện được nhiều nhất số khuôn mặt có thể. Do đó ta sẽ cải tiến thuật toán cơ bản này thành thuật toán phân vùng nâng cao với mục đích cắt đứt các liên kết yếu giữa các vùng. 2.2.3.2. Thuật toán phân vùng nâng cao Sự khác nhau của thuật toán này với thuật toán trên là ở chỗ: trong thuật toán này ta có cài đặt để loại bỏ các liên kết yếu giữa 2 vùng, tức là trong thuật toán trước, 2 vùng liên kết yếu sẽ được phát hiện là 1 vùng, còn trong thuật toán này chúng sẽ được coi là 2 vùng. Mục tiêu của ta là xóa bỏ khỏi ảnh nhị phân các liên kết yếu giữa các vùng (xóa bỏ tức là gán cho nó giá trị 0 (đen)). Làm sao để phát hiện các liên kết yếu. Ta hãy xét hình liên kết yếu trên (hình có 1 đường nối 2 hình elip), nếu ta dùng 1 đường thẳng cắt nó thì ta sẽ thu được 1 tiết diện là 1 dãy điểm trắng ngắn. Như vậy, nếu tại 1 điểm trắng đang xét, ta xét theo phương thẳng đứng, nếu dãy điểm trắng theo phương đó có số lượng điểm nhỏ hơn 1 giá trị định trước thì ta sẽ coi đó là điểm nằm trên liên kết yếu, và sẽ gán nó bằng 0. Tương tự, ta có thể xét theo các phương ngang và phương chéo nữa. Cách xác định dãy điểm trắng theo 1 phương như sau: ví dụ ta xét theo phương thẳng đứng, khi đó, ta duyệt lên phía trên, đến khi gặp điểm đen thì dừng, đánh dấu vị trí dừng đó. Sau đó, lại duyệt từ điểm đang xét xuống phía dưới, cũng gặp điểm đen thì dừng. Cũng đánh dấu lại vị trí này. Từ đó, ta xác định được số điểm trắng theo phương đó. Tuy nhiên, nếu điểm trắng đang xét mà nằm sâu trong vùng thì sao? Khi đó, việc duyệt lên trên hoặc xuống dưới sẽ phải chạy qua rất nhiều điểm, rất tốn kém. Do đó, ta phải có điều kiện kiểm tra số lượng điểm trong khi duyệt. Nếu số lượng điểm đã lớn hơn giá trị ngưỡng định trước kia thì dừng luôn, và kết luận ngay nó không phải là điểm nằm trên liên kết yếu. Cụ thể như sau: với điểm trắng đang xét: Gán biến đếm số lượng sl = 0. Duyệt lên phía trên: Nếu gặp điểm đen thì dừng. Nếu gặp điểm trắng thì: Tăng sl lên 1. Kiểm tra giá trị của sl. Nếu lớn hơn giá trị ngưỡng thì dừng. Kiểm tra giá trị sl. Nếu lớn hơn giá trị ngưỡng thì kết luận nó không nằm trên liên kết yếu. Nếu nhỏ hơn, ta duyệt xuống bên dưới. Thao tác tương tự như duyệt lên trên. Khi dừng cũng kiểm tra giá trị của sl để quyết định. Nếu vẫn nhỏ hơn ngưỡng thì nó là điểm nằm trên liên kết yếu và gán nó bằng 0 (đen). Khi duyệt lên trên hoặc xuống dưới ta có thể lao ra khỏi ảnh. Khi đó ta cũng phải dừng quá trình duyệt lại ngay. Vì vậy ta sẽ coi điểm nằm ngoài ảnh là điểm đen. Lưu đồ thuật toán: Đ S Begin End sl ß 0 Điểm trắng and sl <= Nguong? sl <= Nguong? Là điểm trắng và sl <= Nguong? sl ß sl + 1, Nhảy lên điểm tiếp theo sl ß sl + 1, Nhảy xuống điểm tiếp theo Đưa con trỏ về vị trí điểm ngay dưới điểm đang xét sl <= Nguong? Gán điểm đang xét thành đen Đ S S Đ Đ S Hình 2.17: Lưu đồ thuật toán phát hiện liên kết yếu theo chiều dọc Tương tự ta cũng có thể xét theo các phương khác như phương ngang hoặc chéo 45 độ. Trong cài đặt ta kiểm tra theo cả 2 chiều: thẳng và ngang. Đưa khâu này vào thuật toán phân vùng cơ bản như sau: ta đưa vào 2 chỗ. Một là khi kiểm tra 1 điểm thấy nó là điểm trắng và chưa gán nhãn thì ta sẽ không tạo 1 vùng trắng để chứa ngay, mà ta sẽ kiểm tra xem nó có nằm trên đường liên kết yếu không? Nếu có thì ta sẽ xóa nó (gán thành đen) và chuyển sang xét điểm tiếp theo, không tạo vùng mới. Nếu không thì lúc đó mới tạo vùng trắng mới để lưu trữ và tiếp tục thực hiện như trước. Hai là khi lấy 1 điểm ra khỏi hàng đợi, khi xét 4 điểm hàng xóm của nó, tại mỗi điểm hàng xóm nếu là điểm trắng và chưa gán nhãn thì ta cũng không gán nhãn, đưa vào hàng đợi và vùng trắng ngay mà ta cũng phải kiểm tra xem có nằm trên đường liên kết yếu không. Nếu nằm trên đường liên kết yếu thì ta sẽ xóa nó và chuyển sang kiểm tra hàng xóm tiếp theo mà không làm gì hơn. Nếu không nằm trên đường liên kết yếu thì lúc đó mới gán nhãn, đưa vào vùng trắng và hàng đợi. Tóm lại chỉ sửa trong 2 vị trí đó thôi. Sau đây là một kết quả minh họa (lấy lại ví dụ dính nhau trên): Hình 2.18: Kết quả minh họa phân vùng nâng cao Ta thấy ngay, 2 khuôn mặt đã được nhận ra tách rời, mặc dù có 1 đường liên kết yếu giữa chúng. Việc làm này cũng giúp loại bỏ các vùng có kích thước nhỏ (nhỏ hơn giá trị ngưỡng xác định điều kiện liên kết yếu), giúp đỡ tốn lưu trữ và xét duyệt. Để ý các hình chữ nhật khung thấy rằng nó không bao trọn vẹn vùng đó mà cắt vào trong một chút. Đó là hiệu ứng phụ trong thuật toán của ta. Nó không chỉ cắt đứt các cầu liên kết yếu giữa 2 vùng mà còn bào mòn các cạnh nhọn đâm ra của vùng. Việc này sẽ làm tỉ lệ số điểm trắng trong vùng giảm xuống. 2.2.4. Phân loại các vùng trắng Vị trí của khâu này trong hệ thống xử lý: Hình 2.19: Vị trí của khâu phân loại vùng trắng trong phương pháp Phân loại các vùng trắng tức là xác định xem vùng trắng nào là mặt. Đầu vào của khâu này là danh sách các vùng trắng đã được tìm ra từ khâu trước, đầu ra là tọa độ các vùng mặt lọc ra từ danh sách vùng trắng đó. Để xác định một vùng trắng có phải là mặt không dựa trên 2 tiêu chí: Tỉ lệ kích thước của vùng. Tỉ lệ số điểm trắng trên tổng số điểm trong vùng. * Tỉ lệ kích thước: Qua nghiên cứu, người ta thấy rằng tỉ lệ kích thước giữa chiều cao và chiều rộng của khuôn mặt con người là xấp xỉ nhau giữa những người khác nhau, và xấp xỉ một giá trị đặc biệt, đó là tỉ lệ vàng: 1,618. Tất nhiên không thể chính xác hoàn toàn. Do đó ta phải đặt ra một sai số cho phép delta đối với tỉ lệ vàng. Khi đó, tỉ lệ thỏa mãn nếu rơi vào dải: tỉ lệ vàng ± delta. Giá trị delta được xác định từ thực nghiệm. Không có giá trị delta tốt cho mọi ảnh, giá trị delta này có thể tốt cho ảnh này (giúp phát hiện ra khuôn mặt), nhưng lại không tốt cho ảnh khác. Do đó, ta sẽ chọn ra giá trị delta tốt cho nhiều ảnh nhất. * Tỉ lệ số điểm trắng: Nếu chỉ căn cứ vào tỉ lệ kích thước vùng trắng thì có thể phát hiện nhầm. Ví dụ: Hình 2.20: Trường hợp phát hiện nhầm nếu chỉ dựa vào tỉ lệ kích thước Ta thấy ngay, vùng này (vùng gồm 2 đoạn thẳng) thỏa mãn về tỉ lệ kích thước cao/rộng, nhưng nó không phải là khuôn mặt. Do đó, ta cần thêm tiêu chí về tỉ lệ số điểm trắng để loại bỏ những trường hợp này. Tiêu chí này như sau: yêu cầu tỉ lệ số điểm trắng trong vùng phải lớn hơn 1 giá trị ngưỡng cho trước. Cũng như giá trị delta ở trên, giá trị này cũng được xác định bằng thực nghiệm và ta sẽ chọn giá trị tốt trong nhiều trường hợp nhất. Tuy nhiên vẫn còn tình huống nữa như: Hình 2.21: Trường hợp phát hiện nhầm nếu không có cận trên của tỉ lệ điểm trắng Rõ ràng vùng trắng trên thỏa mãn cả về tỉ lệ kích thước lẫn tỉ lệ số điểm trắng, nhưng nó không phải là mặt. Bởi vì ta biết rằng mặt người có dạng hình elip (bao bằng đường cong) nên không thể chiếm đầy toàn bộ hình chữ nhật bao nó được, có nghĩa là giá trị tỉ lệ số điểm trắng của vùng khuôn mặt cũng có giới hạn trên. Vì vậy, ta cũng đặt thêm một giá trị cận trên trong tiêu chí về tỉ lệ số điểm trắng. Sau đây là 1 kết quả minh họa: Hình 2.22: Kết quả phân loại vùng trắng. Từ trái sang phải: danh sách vùng trắng, phân loại theo tỉ lệ kích thước, phân loại theo cả kích thước và tỉ lệ điểm trắng Hình thứ 3 là kết quả khi ta chọn detal = 0,6 và cận dưới của tỉ lệ điểm trắng là 0,6; cận trên là 1 (không giới hạn trên). Hình thứ 2 là kết quả nếu ta chỉ căn cứ vào tỉ lệ kích thước mà không căn cứ vào tỉ lệ điểm trắng, ta thấy ngay rất nhiều cá