Chương 1 TỔNG QUAN Tóm tắt Trong chương này chúng tôi sẽ giới thiệu về bài toán phân cụm nói chung và phân cụm khuôn mặt nói riêng cũng như những thách thức của bài toán mà chúng tôi sẽ phải giải quyết. Bên cạnh đó, chúng tôi cũng sẽ nói về mục tiêu mà chúng tôi hướng tới khi thực hiện đề tài "Phân cụm ảnh khuôn mặt sử dụng mạng nơ-ron đô thị phân cấp". Cuối cùng, chúng tôi sẽ tóm tat câu trúc tổng thể của khóa luận. 11 Giới thiệu bài toán Phân cụm là bài toán xử lý dữ liệu không được gán nhãn.
Các dữ liệu này sẽ được phân vào các cụm sao cho những dit liệu tương đồng nhau sẽ thuộc cùng một cụm, khác nhau thì khác cụm. Từ tập dữ liệu không có nhãn, để biết được tập dữ liệu này có tương đồng nhau hay không ta có thể sử dụng các độ đo tương đồng hoặc khoảng cách (Cosine, Euclidean,. Sau đó, dựa vào ngưỡng và điều kiện để hai dữ liệu được coi là tương đồng đã xác định trước để tiến hành phân chia các dtr liệu vào các cum. Sau quá trình phân cụm, dữ liệu trong cùng một cum sẽ có cùng nhãn [20].
TONG QUAN 2 Khóa luận của chúng tôi sẽ chọn tập trung vào nghiện cứu một bài toán con của phân cụm, đó là phân cụm khuôn mặt. Bài toán này tập trung vào đối tượng là ảnh khuôn mặt của con người (ảnh có chứa khuôn mặt). Kết quả của phân cụm khuôn mặt là ảnh của cùng một người thì sẽ cùng một cụm (hình[1. Quá trình phân cụm khuôn mặt sẽ gồm 3 bước: 1.
Nhận điện khuôn mặt: Định vị được khuôn mặt trong các bức ảnh. Trích xuất đặc trưng: Đưa khuôn mặt vừa tìm được về dạng các vector đặc trưng (những vector này sẽ chỉ chứa những đặc trưng quan trọng nhất của các khuôn mặt này, giúp chúng ta không cần phải xét toàn bộ khuôn mặt, bước này cũng giúp chúng ta khái quát hóa được khuôn mặt vì cho dù là ảnh khuôn mặt của cùng một người nhưng nếu xét toàn bộ khuôn mặt thì vẫn sẽ có vài điềm khác, bước này sẽ giúp chúng ta giảm bớt rủi ro khác biệt về hai khuôn mặt của cùng một người). Phân cụm khuôn mặt: phân các vector đặc trưng đó thành từng cụm, sau khi có được cụm thì các ảnh có vector đặc trưng thuộc cùng một cum sẽ có cùng một nhãn, khác cụm thì khác nhãn. Trong khóa luận này, chúng tôi chỉ tập trung vào bước thứ 3 đó là phân cụm khuôn mặt.
Trong thực tế, không một bộ dữ liệu nào chứa hết toàn bộ khuôn mặt của tất cả mọi người trên thé giới. Các bộ dữ liệu khuôn mặt có thể khác nhau một phan hoặc hoàn toàn. Điều này có liên quan đền van dé nhận diện tập mở (Open Set Recognition - OSR [29] [10]). Các phương pháp phân cum hiện tại chủ yếu chỉ làm việc trên một tập nhất định nào đó nên sẽ khó có thể áp dụng một phương pháp đã được học trên tập này cho tập khác.
Nếu có tập dữ liệu mới thì phải phân cụm lại từ đầu. Mặt khác, mỗi lần phân cụm, ta lại phải xác định điều kiện phân cụm, tham số tối ưu của bộ dữ liệu đó. Chúng ta sẽ phải tiêu tồn nhiều tài nguyên và công sức cho mỗi lần như vậy. Chính vì thế, chúng ta cần một phương pháp không chỉ phân cụm được dữ liệu thuộc các lớp đã biết trong quá trình huấn luyện mà hơn thế nữa, từ kết quả phân cum mà học được cách để có thể phân cụm những dir liệu thuộc các lớp khác những lớp đã có trong tập dữ liệu học.
Đồng thời, phương pháp này còn có thể học được điều kiện hội tụ từ chính dữ liệu mà không cần người lập trình phải cài đặt. Mô tả bài toán: ¢ Input: — T: Các vector đặc trưng của tập ảnh khuôn mặt để huấn luyện đã được phân vào k cụm. — E: Các vector đặc trưng của tập ảnh khuô n mặt cần được gom cụm, số cum và nhãn của từng ảnh chưa được biết. s Output: Các vector đặc trưng trong tập E được gom thành n cụm.
TỔNG QUAN 4 Phân cụm khuôn mặt có rất nhiều ứng dụng trong đời sống và đây là hai ứng dụng tiêu biểu nhất: s Ung dung 1: Tự động phân các bức ảnh vào các cụm. Trong thực tế, dữ liệu khuôn mặt vô cùng lớn, các dữ liệu này được thu thập từ các camera giám sát, ảnh chup,. Việc có thể gom cụm ảnh của cùng một người lại có thể giúp chúng ta dễ dàng truy vấn khi muốn tìm kiếm ảnh một người nào đó (Hnh[L1). s Ung dụng 2: Gan nhãn các ảnh khuôn mặt vào các cụm đã có.
Khi chúng ta có những bức ảnh khuôn mặt mới, thay phải tự tay tìm ra định danh của những bức ảnh mới này, mô hình phân cụm có thể giúp chúng ta (Hình[1.2 Mục tiêu khóa luận * Tìm hiểu và khảo sát các phương pháp có thể giải quyết được thách thức của bài toán đưa ra. ® Nghiên cứu về các thuật toán phân cụm khuôn mặt đã công bố, đặc biệt là các thuật toán có sử dụng mạng nơ-ron đồ thị.3 Đóng góp khóa luận ® Khảo sát và nghiên cứu một sỐ phương pháp phân cụm đã được công bồ cho bài toán phân cụm khuôn mặt. ¢ Thực nghiệm các nghiên cứu đã khảo sát trên cùng tập dữ liệu để so sánh hiệu quả giữa các phương pháp. ¢ Thử nghiệm phương pháp chính trên tập dữ liệu mới để kiểm chứng phương pháp đó có thể dùng cho các tập dữ liệu khác nhau được không.4 Câu trúc Khóa luận tot nghiệp Nội dung Khóa luận tốt nghiệp được tổ chức như sau: ¢ Chương ii} Giới thiệu về bài toán phân cụm khuôn mặt, đặc biệt là phân cụm tập mở (học tập này nhưng huấn luyện tập khác), một số ứng dụng khi giải quyết bài toán này, mục tiêu làm khóa luận, những gì đã đóng góp và cấu trúc tổng thể của khóa luận.
° Chương} Tổng quan về cơ sở lý thuyết để thực hiện bài toán và các hướng tiếp cận đã tìm hiểu được. s Chương BỊ Trình bày chỉ tiết hướng tiếp cận chính để giải quyết bài toán phân cụm khuôn mặt. TỔNG QUAN 6 s Chương 4 Trình bày môi trường thực nghiệm, các tập dữ liệu đã được dùng, phương pháp đánh giá và kết quả thực nghiệm. s Chương) BỊ Tổng kết nội dung của khóa luận và những hướng phát triển Sau này.
Chương 2 CƠ SỞ LÝ THUYET VÀ CÁC NGHIÊN CỨU LIÊN QUAN Tóm tắt Trong chương này, chúng tôi sẽ nói về cơ sở lý thuyết của những cầu trúc được sử dụng trong hướng tiếp cận chính. Đồng thời, chúng tôi cũng giới thiệu về những phương pháp phân cụm đã nghiên cứu, và nêu ra những ưu nhược điểm của các phương pháp này.1 Các kiến thức cơ sở 2.1 Lý thuyết đồ thil] Đồ thị (Graph) là một câu trúc dữ liệu gồm một tập các đỉnh V (ver- tice/node) khác rỗng và một tập các cạnh E (edge) nối giữa hai đỉnh, hai đỉnh thuộc hai đầu của cạnh có thể có thứ tự hoặc không có thứ tự. Một đồ thị G có thể được kí hiệu như sau: 1Các định nghĩa, khái niệm trong phan ly thuyết dé thị được trích dẫn và tham khảo tr (431) 29 Chương 2. CƠ SỞ LÝ THUYẾT VA CÁC NGHIÊN CUU LIEN QUAN 8 G=(V,E) Hai đỉnh „ø; với i = 1,2,.|V| được nối bởi cạnh em với m = 1,2,.|E| được gọi là hai đỉnh kê nhau.
Nếu 0¡ = 9; thì cạnh nối giữa hai đỉnh này sẽ được gọi là một vòng (loop) và đỉnh này khi đó sẽ kể với chính bản thân đỉnh đó.1: Trong đồ thi nay, ta có đỉnh A và B được nồi với nhau bởi một cạnh nỗi nên A kể với B, tương tự như vậy, B với C cũng kể nhau. Do A và C không có cạnh nổi nên A không ké C. A có thêm một vòng nên A sẽ kể với chính A. Giữa 2 đỉnh có thể có nhiều cạnh nồi, dé thị chỉ có 1 cạnh nối giữa hai đỉnh và không có vòng được gọi là don do thi.
Đồ thị mà có nhiều cạnh cùng nối hai đỉnh được gọi là đa đô thi. Đồ thị có chứa vòng được gọi là giả dé thị] D6 thị v6 hướng là đồ thị gồm tập đỉnh khác rỗng và tập các cặp cạnh nối giữa hai đỉnh không phân biệt thứ tự. Cạnh nối giữa hai đỉnh u và w có kí hiệu là uw (hoặc wu) (Hình 2. D6 thị có hướng là đồ thị gồm tập đỉnh khác rỗng và tập các cặp cạnh nồi giữa hai đỉnh có phân biệt thứ tự.
Cạnh nồi từ đỉnh u đến đỉnh w có kí hiệu là ib (Hình|2. ?Theo một số tác giả, giả đô thị và đa dé thị có ý nghĩa tương tự nhau Chương 2. CƠ SỞ LÝ THUYẾT VA CÁC NGHIÊN CUU LIEN QUAN 9 °° HINH 2.2: Đồ thịG = (V,E) cóV = {A,B,C} và E = (AB, 5c), ABE BÀ xà BC = CB. „®e LAN BÀ Cải, ab ¿ BÀ.
Ta có thể tạo ra dé thị con của một đồ thị G bằng cách loại bỏ cạnh hoặc đỉnh của G (Hình}2.4: Đồ thi G sau khi loại bỏ đỉnh A và E cùng với các cạnh AB, AE, EC, ED, EF, ta được dé thị con G’ Chương 2. CƠ SỞ LÝ THUYẾT VÀ CÁC NGHIÊN CUU LIEN QUAN 10 Hai đồ thi Gị = (VỊ, Ei) và Gy = (V2, Ez) có thể kết hợp với nhau để tạo thành một đồ thị với tập đỉnh bằng Vị U W2 và tập cạnh bằng E¡ U Ey. Nếu một đồ thị có thể được biểu diễn bằng cách hợp các dé thị lại với nhau thì đồ thị đó là đô thị không liên thông, ngược lại là đô thị liên thông (Minh họa ở hình|2.5: Đồ thi G; là dé thị liên thông vì không thé tìm được các dé thị có thể hợp thành dé thị Gị. Trong khi đó với đồ thị Gp, ta có thể biểu diễn G› bằng hai đỏ thị.
Bậc của đỉnh * Đối với đồ thị vô hướng: Bậc của một đỉnh v là số cạnh nói đến đỉnh đó] ký hiệu là deg(v). Tổng bậc của các đỉnh trong đồ thị luôn là số chan và bằng 2 lần số cạnh vì mỗi cạnh có 2 đầu nên mỗi khi tính bậc 3vì là dé thị vô hướng nên số cạnh nói đến 1 đỉnh cũng chính là số cạnh di ra từ đỉnh đó Chương 2. CƠ SỞ LÝ THUYẾT VÀ CÁC NGHIÊN CỨU LIÊN QUAN 11 của đỉnh, cạnh nói 2 đỉnh sẽ được tính 2 lần. Mỗi vòng được tính là 2 bậc.