Báo cáo Tìm hiểu các đặc trưng sinh trắc ảnh khuôn mặt, nghiên cứu ứng dụng của phép biến đổi KL và phân tích thành các thành phần chính PCA trong trích chọn

ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ---------- BÀI TẬP LỚN MÔN XỬ LÝ ẢNH ĐỀ TÀI: Tìm hiểu các đặc trưng sinh trắc ảnh khuôn mặt, nghiên cứu ứng dụng của phép biến đổi KL và phân tích thành các thành phần chính PCA trong trích chọn đặc trưng khuôn mặt Giảng viên hướng dẫn : PGS.TS Nguyễn Thị Hoàng Lan Sinh viên thực hiện : Nguyễn Văn Thành SHSV : 20072604 Lớp: Hệ thống thông tin và truyền thông – KSCLC-K52 Hà Nội, 12/2011 BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 2 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 MỤC LỤC LỜI NÓI ĐẦU .......................................................................................................................................... 3 I. ĐẶC TRƯNG SINH TRẮC ẢNH KHUÔN MẶT ...................................................................... 4 II. NGHIÊN CỨU ỨNG DỤNG CỦA PHÉP BIẾN ĐỔI KL ...................................................... 7 1. Phép biến đổi KL ........................................................................................................................ 7 2. Ứng dụng của phép biến đổi KL ............................................................................................... 9 III. PHÂN TÍCH THÀNH CÁC THÀNH PHẦN CHÍNH PCA TRONG TRÍCH CHỌN ĐẶC TRƯNG KHUÔN MẶT ....................................................................................................................... 14 1. Phép biến đổi PCA.................................................................................................................... 14 2. Phân tích thành chính PCA trong trích chọn đặc trưng khuôn mặt ................................... 14 2.1. Tính toán các vector riêng ............................................................................................... 14 2.2. Biểu diễn khuôn mặt theo cơ sở tìm được ...................................................................... 17 IV. KẾT LUẬN ............................................................................................................................... 18 TÀI LIỆU THAM KHẢO .......................................................................................................... 19 BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 3 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 LỜI NÓI ĐẦU “Xử lý ảnh” là môn học quan trọng đối với sinh viên ngành công nghệ thông tin. Đây là môn học khó đối với hầu hết nhiều sinh viên do yêu cầu kiến thức về toán và xác suất. Với mục tiêu có thêm kiến thức cơ bản trong lĩnh vực về xử lý ảnh, em chọn đề tài “Tìm hiểu các đặc trưng sinh trắc ảnh khuôn mặt, nghiên cứu ứng dụng của phép biến đổi KL và phân tích thành các thành phần chính PCA trong trích chọn đặc trưng khuôn mặt”. Qua bài tập lớn, em đã có thêm được cái nhìn chung về hệ thống nhận dạng khuôn mặt, các đặc trưng sinh trắc khuôn mặt giúp phát hiện và trích rút được các đặc trưng cho việc nhận dạng. Đồng thời em được củng cố thêm về kiến thức toán và xác suất thông kê, có được hiểu biết tốt hơn về ứng dụng của kiến thức cơ bản trong các bài toán thực tế. Dù rất cố gắng trong việc tìm hiểu tài liệu, nhưng do thiếu sót về kiến thức cơ bản, hạn chế tầm hiểu biết mà bài báo cáo còn rất nhiều thiếu khuyết. Kính mong nhận được những ý kiến góp ý để em hoàn thiện hơn. Nhân dịp này, em xin gửi lời cảm ơn chân thành tới PGS.TS Nguyễn Thị Hoàng Lan đã nhiệt tình hướng dẫn góp ý giúp em hoàn thành báo cáo môn học này. Em xin chân thành cảm ơn! Hà Nội, ngày 12 tháng 12 năm 2011 BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 4 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 I. ĐẶC TRƯNG SINH TRẮC ẢNH KHUÔN MẶT Các đặc trưng khuôn mặt bao gồm: - Đặc trưng hình học: cấu trúc, hình dạng và các thành phần trên khuôn mặt: miệng, mắt, mũi, lông mày. Khoảng cách giữa mắt, mũi, miêng và hàm; đường bao các hốc mắt; các cạnh của miệng; vị trí của mũi, hai mắt và các vùng xung quanh.Các thành phần khuôn mặt được trích rút để hình thành vector đặc trưng biểu diễn hình học khuôn mặt. BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 5 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Hình 1.1. Minh họa đặc trưng hình học của khuôn mặt - Đặc trưng về diện mạo biểu diễn sự thay đổi vẻ bề ngoài: kết cấu da như các nếp nhăn trên khuôn mặt; biểu đồ nhiệt của khuôn mặt: các mẫu nhiệt khuôn mặt là duy nhất với mỗi người và đặc trưng về nụ cười. Các đặc trưng về diện mạo có thể được trích rút trên cả khuôn mặt hoặc phần nào đó trên khuôn mặt. - BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 6 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Hình 1.2. Minh họa đặc trưng về diện mạo khuôn mặt BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 7 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 II. NGHIÊN CỨU ỨNG DỤNG CỦA PHÉP BIẾN ĐỔI KL 1. Phép biến đổi KL Xét không gian mẫu S = {x} gồm n vector dữ liệu mẫu. Trong đó x là vector các biến ngẫu nhiên N chiều: x = [ x1 x2 … xN ] T Phép biến đổi KL đối với các vector x được định nghĩa như sau: y = W T x (1.1) Trong đó x = [ x1 x2 … xN ] T , y = [ y1 y2 … yM ] T và ma trận W là ma trận phép biến đổi với kích thước NxM (M ≤ N) có dạng:              MNM N T i T ww ww wW ... ......... ... 1 111 Ta định nghĩa ma trận hiệp tương quan của các vector x: [C]x = E[xxT] (1.2) Ma trận tương quan được ước lượng từ n mẫu trong không gian dữ liệu quan sát được xác định bởi biểu thức:    n i T iix xx n C 1 1 Phép biến đổi KL là bài toán tìm một ma trận biến đổi W thỏa mãn (1.1) Mỗi cột            iN i i w w w ... 1 của W là vector cơ sở trực giao của không gian mới hay: 1. Tkj ww nếu j = k (1.3) BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 8 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Vì vậy mỗi phần tử yi của y sẽ được tính: NiNii T ii xwxwxwxwy  ...2211 (1.4) Do wi là các vector cơ sở trực giao theo (1.3) nên W là ma trận trực chuẩn thỏa mãn: W T W = I = WW T (I là ma trận đơn vị) (1.5) Từ đó: WT = W-1 và ta có dạng biến đổi ngược của (1.1): x = Wy (1.6) Đặt Cy là ma trận đường chéo mong muốn của vector biến ngẫu nhiên y: Cy =             N  ................0 ..... 1  Trong đó các phần tử đường chéo là các phương sai của dữ liệu được biến đổi. Ma trận đường chéo này có thể tính toàn từ ma trận hiệp tương quan gốc như sau: Cy =  TyyE =    TTT xWxWE =   WxxWE TT = WCW xT Hay yWC = WCx (1.7) Cy là ma trận đường chéo nên biểu thức (1.7) được đưa về sạng Cxwi = i wi (1.8) Từ (1.8) ta thấy λi và wi là cặp giá trị riêng và vector riêng của ma trận tương quan Cx trong biểu thức (1.2). Hay các cột wi của ma trận W là các vector riêng của ma trận Cx. Để đảm bảo W là trực chuẩn cần áp dụng trực giao và chuẩn hóa Gram-Schmidt với các vector riêng tìm được. Như vậy, phép biến đổi KL chính là tìm các vector riêng wi ứng với M giá trị riêng lớn nhất của ma trận hiệp tương quan của các vector ngẫu nhiên quan sát được. Phép biển đổi KL là cách tối ưu nhằm giảm thứ nguyên từ không gian dữ liệu có số chiều lớn BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 9 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 thành không gian mới có số chiều bé hơn rất nhiều với sai số là bé nhất nằm ở các vector riêng ứng với các giá trị riêng nhỏ nhất. 2. Ứng dụng của phép biến đổi KL Hình 2.1 biểu diễn một ảnh đa mức xám kích thước 512 x 512 với giá trị mức xám của mỗi điểm ảnh được biểu diễn bằng 8 bit (giá trị trong [0 – 255]). Giá trị mức xám của các điểm ảnh kề nhau có xu hướng tương tự nhau. Hình 2.2 minh họa giá trị mức xám của các cặp điểm ảnh liền kề. Hình 2.1. Ảnh đa mức xám kích thước 512 x 512 Trong hình 2.2, mỗi chấm biểu diễn một điểm ảnh trong bức ảnh hình 2.1 với hoành độ x là giá trị của điểm ảnh đó và tung độ y là giá trị của điểm ảnh liền kề bên phải nó.Từ đồ thị, ta thấy quan hệ x = y thể hiện độ tương quan mạnh giữa các điểm ảnh liền kề. Chia bức ảnh thành các khối 1x2 rời nhau như hình 2.3, chúng ta biểu diễn BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 10 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 một bức ảnh thành tập các vector 2 chiều xi. Phân bố giá trị mức xám của mỗi thành phần được vẽ như hình 2.4. Chúng ta thấy rằng phân bố mức xám của mỗi thành phần tương đối rộng và phủ hầu hết dải 0 – 255. Hơn nữa, hai phân bố này khá giống với phân bố chung của mỗi điểm ảnh trong bức ảnh hình 2.1. Hình 2.2. Đồ thị biểu diễn các cặp giá trị mức xám của các điểm ảnh BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 11 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Hình 2.3. Chia bức ảnh ban đầu thành các khối điểm ảnh 1 x 2 BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 12 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Hình 2.4. Phân bố giá trị mức xám của mỗi thành phần trong các khối Bây giờ, chúng ta quay phân bố trong hình 2.2 đi một góc 45o. Kết quả trong hình 2.5 cho thấy, hai thành phần mới không tương quan nghĩa là biết giá trị của thành phần thứ nhất sẽ không giúp ta xác định được giá trị của thành phần thứ hai. Phân bố của hai thành phần mới được vẽ như hình 2.6. Thành phần thứ nhất vẫn khá giống với phân bố trước, tức là phân bố rộng, trải hầu hết khoảng giá trị. Tuy nhiên thành phần thứ hai thì khác, nó hẹp hơn rất nhiều và giá trị đỉnh tại 0. Do nó có khoảng biến đổi nhỏ hơn nhiều nên chúng ta cần ít số bit để mã hóa giá trị của nó. Vì vậy, chúng ta có thể giảm số bit cần thiết để mã hóa một một ảnh khi giải tương quan. Hình 2.5. Đồ thị các cặp mức xám khi quay 45o BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 13 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Hình 2.6. Phân bố mức xám của hai thành phần khi xoay tương ứng với hình 2.5 Hầu hết các bức ảnh đều chứa sự tương quan ngẫu nhiên về dữ liệu do đó dẫn đến sự dư thừa dữ liệu. Phép biến đổi KL loại bỏ được sự dư thừa dữ liệu nhờ việc giải tương quan dữ liệu và giảm số chiều vì vậy ảnh có thể được lưu trữ hiệu quả hơn. Đó là ứng dụng của phép biển đổi KL. BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 14 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 III. PHÂN TÍCH THÀNH CÁC THÀNH PHẦN CHÍNH PCA TRONG TRÍCH CHỌN ĐẶC TRƯNG KHUÔN MẶT 1. Phép biến đổi PCA Tương tự như phép biến đổi KL, ta có không gian dữ liệu quan sát S = {x} gồm n vector dữ liệu mẫu N chiều. Dữ liệu thô tồn tại sự tương quan ngẫu nhiên giữa các thành phần do đó có sự dư thừa dữ liệu. Ý tưởng của phép biến đổi PCA là phân tích dữ liệu thành các thành phần không tương quan (gọi là các thành phần chính) để giảm độ dư thừa dữ liệu. Phép biến đổi PCA được định nghĩa như sau: xu T (2.1) Trong đó x = [ x1 x2 … xN ] T , u = [ u1 u2 … uN ] T – các thành phần thứ i và j không tương quan trong không gian mới. Và ma trận Ψ là ma trận phép biến đổi với kích thước N2 có dạng:              NNN N T i T v    ... ......... ... 1 111 (2.2) Ở đó vi là các vector riêng tương ứng với ma trận hiệp phương sai của các x quan sát được.    TxxEC   (2.3) Trong đó            N   ... 1 và    n k iki x n 1 1  2. Phân tích thành chính PCA trong trích chọn đặc trưng khuôn mặt 2.1. Tính toán các vector riêng Giả sử chúng ta một tập luyện gồm M bức ảnh khuôn mặt I1, I2…IM. Các bức ảnh này có cùng kích thước và đã được chỉnh tâm. BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 15 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Chúng ta biểu diễn mỗi bức ảnh Ii kích thước NxN bằng một vector  có kích thước N2 chiều. Bước 1: Tính vector trung bình BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 16 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Bước 2: Tính  ii với i = 1, 2…N2 Bước 3: Tính ma trân hiệp phương sai C của các vector quan sát: T M i T ii AA M C   1 1 (ma trận C có kích thước N2xN2) (2.4) Trong đó  MA  ...21 (kích thước N2xM) Bước 4: Tìm các vector riêng ui của ma trận hiệp phương sai C hay của AA T . Tuy nhiên kích thước của ma trận này là N2xN2 quá lớn nên việc tìm vector riêng của ma trận này là không khả thi. Chúng ta xem xét ma trận ATA có kích thước MxM Tìm các vector riêng vi của ma trận A T A, ta có: iii T vAvA  (2.5) Quan hệ giữa ui và vi: iiiiii T iii T AvCAvAvAvAAvAvA   (2.6) Từ đó suy ra ui = Avi Vì vậy, AAT và ATA có cùng các giá trị riêng và các vector riêng của chúng quan hệ với nhau theo ui = Avi Chú ý: - ATA có thể có M giá trị riêng và vector riêng. - AAT có thể có N2 giá trị riêng và vector riêng. - M giá trị riêng của ATA cùng với các vector riêng tương ứng với M giá trị riêng lớn nhất của AAT. BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 17 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 Sau đó tính M vector riêng ứng với M giá trị riêng lớn nhất của AAT: ui = Avi đồng thời chuẩn hóa vector ui sao cho 1iu Bước 5: Chọn K vector riêng ứng với K giá trị riêng lớn nhất. 2.2. Biểu diễn khuôn mặt theo cơ sở tìm được Mỗi vector biểu diễn khuôn mặt (trừ đi vector trung bình) i trong tập luyện có thể được biểu diễn bằng một tổ hợp tuyến tính của K giá trị riêng tính ở trên.    K j jji uwmean 1 ˆ i=1,2…M. Trong đó i T jj uw  chính là thành phần chính thứ j trong không gian mới. Và uj gọi là các ảnh riêng. Mỗi ảnh được chuẩn hóa trong tập luyện sẽ được biểu diễn trong cở sở này bởi vector:                i K i i i w w w ... 2 1 trong đó i = 1, 2… M BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 18 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 IV. KẾT LUẬN Như vậy, em đã trình bày về các đặc trưng sinh trắc ảnh khuôn mặt, gồm các đặc trưng hình học và các đặc trưng về diện mạo khuôn mặt, cùng với đó là lý thuyết và ứng dụng của phép biến đổi KL và phân tích thành các thành phần chính PCA trong trích chọn đặc trưng khuôn mặt. Phép biến đổi KL ứng dụng trong bài toán giảm số chiều của không gian dữ liệu số lớn thành không gian có số chiều nhỏ hơn nhằm giảm giá tính toán và tăng hiệu quả của các kỹ thuật trong xử lý ảnh. Trong khi PCA giải tương tương quan dữ liệu và phân tích thành các thành phần chính ứng dụng trong trích chọn đặc trưng khuôn mặt. BÀI TẬP LỚN MÔN XỬ LÝ ẢNH 2011 19 Nguyễn Văn Thành – HTTT&TT – KSCLC-K52 TÀI LIỆU THAM KHẢO [1]. Bài giảng môn Xử lý ảnh – PGS.TS Nguyễn Hoàng Lan – Đại học Bách Khoa Hà Nội, 2010. [2]. Digital Image Processing – William K. Pratt- Wiley, 2007. [3]. Fundamental of Image Processing – Ian T. Young et al., 1998. [4]. Principal Component Analysis – I.T.Jolliffe – Springer, 2002. [5]. R.D. Dony “Karhunen-Lòeve Transform” - The Transform and Data Compression Handbook, 2001.