Đề tài Nghiên cứu các kỹ thuật dò biên áp dụng trong trích chọn các bộ phận khuôn mặt

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lưu Xuân Thế NGHIÊN CỨU CÁC KỸ THUẬT DÒ BIÊN ÁP DỤNG TRONG TRÍCH CHỌN CÁC BỘ PHẬN KHUÔN MẶT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI – 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lưu Xuân Thế NGHIÊN CỨU CÁC KỸ THUẬT DÒ BIÊN ÁP DỤNG TRONG TRÍCH CHỌN CÁC BỘ PHẬN KHUÔN MẶT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: ThS. Ma Thị Châu HÀ NỘI – 2010 i LỜI CẢM ƠN Lời đầu tiên em xin bày tỏ lòng biết ơn tới các thầy, cô giáo trong trường Đại học Công nghệ - Đại học Quốc gia Hà Nội. Các thầy cô đã dạy bảo, chỉ dẫn chúng em và luôn tạo điều kiện tốt nhất cho chúng em học tập trong suốt quá trình học đại học đặc biệt là trong thời gian làm khoá luận tốt nghiệp. Em xin bày tỏ lòng biết ơn sâu sắc tới cô giáo ThS. Ma Thị Châu, cô đã hướng dẫn em tận tình trong cả học kỳ vừa qua, cô đã góp ý và chỉnh sửa thường xuyên cho khóa luận của em. Tôi cũng xin cảm ơn những người bạn của mình, các bạn đã luôn ở bên tôi, giúp đỡ và cho tôi những ý kiến đóng góp quý báu trong học tập cũng như trong cuộc sống. Hà nội, ngày 2010 Lưu Xuân Thế ii TÓM TẮT Kỹ thuật dò biên là bài toán mới chỉ xuất hiện cách đây không lâu, chỉ khoảng vài thập niên, nhưng đã có rất nhiều nghiên cứu về nó. Các nghiên cứu ban đầu rất đơn giản, ảnh là đen trắng và chỉ có một khuôn mặt chụp thẳng, sau này mở rộng ra cho ảnh màu, ảnh có nhiều khuôn mặt với nhiều góc, môi trường xung quanh cũng đi từ đơn giản đến rất phức tạp. Từ khóa: edge detection, edge filter. iii MỤC LỤC LỜI CẢM ƠN........................................................................................................................... i TÓM TẮT................................................................................................................................ii MỤC LỤC ..............................................................................................................................iii Chương 1. GIỚI THIỆU...................................................................................................... 5 1.1 Giới thiệu về tìm biên trong nhận dạng khuôn mặt ................................................. 5 1.2 Bài toán nghiên cứu kỹ thuật dò biên áp dụng trong trích chọn khuôn mặt............ 2 1.3 Nội dung và cấu trúc khóa luận ............................................................................... 2 Chương 2. CÁC KỸ THUẬT DÒ BIÊN ............................................................................ 4 2.1 Quy trình phát hiện biên .......................................................................................... 4 2.2 Kỹ thuật phát hiện biên trực tiếp ............................................................................. 4 2.2.1 Kỹ thuật Gradient ................................................................................................. 5 2.2.2 Toán tử la bàn .................................................................................................... 8 2.2.3 Kỹ thuật Laplace.............................................................................................. 10 2.2.4 Tách sườn theo ảnh Canny .............................................................................. 11 2.2.5 Dò biên theo quy hoạch động.......................................................................... 12 2.3 Kỹ thuật phát hiện biên gián tiếp ........................................................................ 15 2.4 Một số phương pháp khác ..................................................................................... 15 ................................................................................................................................... 16 2.5 Tổng kết ................................................................................................................. 16 Chương 3. CÁC KỸ THUẬT DÒ BIÊN ĐƯỢC ÁP DỤNG .............................................. 18 3.1 Các kỹ thuật được dùng ......................................................................................... 18 3.1.1 Lấy biên theo trục X ........................................................................................ 19 3.1.2 Lấy biên theo trục Y ........................................................................................ 21 3.1.3 Lấy biên theo Gradient .................................................................................... 21 3.1.4 Lấy biên theo Thresholding............................................................................. 21 iv 3.1.5 Lấy biên theo Thinning ................................................................................... 21 3.2 Chương trình và kết quả ........................................................................................ 23 3.3 Biến thành ảnh đa cấp xám ................................................................................... 24 3.2.1 Lấy biên theo trục X ........................................................................................ 24 3.2.2 Lấy biên theo trục Y ........................................................................................ 25 3.2.3 Lấy biên theo Gradient .................................................................................... 26 3.2.4 Lấy biên theo Thresholding............................................................................. 26 3.2.5 Lấy biên theo Thinning ................................................................................... 27 3.3 Tổng kết ................................................................................................................. 28 Chương 4. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN......................................................... 30 4.1 Kết luận.................................................................................................................. 30 4.2 Hướng phát triển.................................................................................................... 30 4.2.1 Đặt vấn đề ........................................................................................................... 30 4.2.2 Phương pháp thực hiện.................................................................................... 31 TÀI LIỆU THAM KHẢO………………………………………………………….............32 v Chương 1. GIỚI THIỆU 1.1 Giới thiệu về tìm biên trong nhận dạng khuôn mặt Kỹ thuật dò biên là bài toán mới chỉ xuất hiện cách đây không lâu, chỉ khoảng vài thập niên, nhưng đã có rất nhiều nghiên cứu về nó. Các nghiên cứu ban đầu rất đơn giản, ảnh là đen trắng và chỉ có một khuôn mặt chụp thẳng, sau này mở rộng ra cho ảnh màu, ảnh có nhiều khuôn mặt với nhiều góc, môi trường xung quanh cũng đi từ đơn giản đến rất phức tạp. Bài toán phát hiện biên nói chung và phát hiện biên khuôn mặt nói riêng có rất nhiều hướng để phát triển, nhưng có thể kể ra hai hướng chính sau: - Thứ nhất là nhận diện (face recognition) một khuôn mặt, tức là giả sử ta có bức ảnh một khuôn mặt, ta sẽ tìm một bức ảnh có khuôn mặt giống với khuôn mặt trong ảnh. Ứng dụng của nó là truy tìm tội phạm, các hệ thống an ninh xác đinh dựa vào khuôn mặt. - Thứ hai là xác định vị trí những khuôn mặt trong một bức ảnh (face detection), các bức ảnh có thể có nhiều khuôn mặt, có kích thước và góc khác nhau. Ứng dụng của nó như trong các máy chụp hình có khả năng nhận dạng mặt người để chỉnh độ sáng nơi đó. Biên là vấn đề chủ yếu trong phân tích ảnh, vì các đặc điểm trích chọn trong quá trình phân tích ảnh chủ yếu dựa vào biên. Một điểm được gọi là điểm biên nếu ở đó có sự thay đổi đột ngột về mức xám. Tập hợp các điểm biên tạo thành biên hay đường bao của ảnh. Về mặt toán học người ta xem biên là nơi có sự thay đổi đột ngột về mức xám, trên cơ sở đó người ta thường sử dụng hai phương pháp phát hiện biên sau: - Phương pháp phát hiện biên trực tiếp - Phương pháp phát hiện biên gián tiếp Xuất phát từ thực tế đó, mục tiêu của luận văn là nghiên cứu các phương pháp biểu diễn biên, hệ thống hóa kiến thức về các phương pháp phát hiện biên, tìm hiểu các kỹ thuật phân vùng ảnh, một bước trước trong quá trình dò biên và ứng dụng của nó trong xử lý ảnh và xử lý ảnh văn bản là một trong những nhiệm vụ quan trọng trong việc tự động hóa công việc văn phòng. 2 1.2 Bài toán nghiên cứu kỹ thuật dò biên áp dụng trong trích chọn khuôn mặt Trong thực tế, chúng ta gặp nhiều bài toán liên quan đến nhận dạng đối tượng. Thông thường, việc nhận ra các đối tượng thường dựa vào đường biên của chúng. Ở Việt Nam hiện nay đã có một số hệ thống nhận dạng đối tượng như: MapScan, VnDOCR, MarkREAD của Viện Công nghệ thông tin hay VecMap của DolSoft, nhìn chung những ứng dụng và tài tiệu có tính chất hệ thống về các phương pháp biểu phát hiện biên và ứng dụng của nó vẫn là một phần thiếu vắng. Xuất phát từ thực tế đó, mục tiêu của luận văn là nghiên cứu các phương pháp biểu diễn biên, hệ thống hóa kiến thức về các phương pháp phát hiện biên, tìm hiểu các kỹ thuật phân vùng ảnh, tìm hiểu quá trình dò biên và ứng dụng của nó trong xử lý ảnh và xử lý ảnh văn bản, là một trong những nhiệm vụ quan trọng trong việc tự động hóa công việc văn phòng. Trong khóa luận này biên khuôn mặt sẽ được hiển thị thông qua một chương trình mã đơn giản. Với 5 kỹ thuật được áp dụng biên khuôn mặt sẽ được đưa ra với 5 kiểu khác nhau. Mỗi kiểu sẽ là một đặc điểm và khía cạnh riêng. 1.3 Nội dung và cấu trúc khóa luận Khóa luận được tổ chức theo cấu trúc như sau: Chương 1: Giới thiệu Giới thiệu sơ lược về các kỹ thuật dò biên nói chung và kỹ thuật dò biên áp dụng với khuôn mặt và áp dụng cho việc trích chọn các bộ phận của khuôn mặt. Bài toán phát hiện biên được phân tích dưới khía cạnh toán học giúp ta chọn hướng giải quyết tốt nhất cho bài toán là sử dụng các kỹ thuật tìm kiếm biên cổ điển. Chương này giới thiệu những gì mà khóa luận nghiên cứu từ đó thông qua việc trình bày về nội dung và cấu trúc của khóa luận. Chương 2: Các kỹ thuật dò biên Chương hai đi vào giới thiệu giới thiệu các kỹ thuật dò biên. Với 2 kỹ thuật dò biên trực tiếp và gián tiếp, nhưng ta chủ yếu đi xâu vào kỹ thuật dò biên trực tiếp được dùng rộng rãi và thường xuyên. Chương 3: Kỹ thuật dò biên được áp dụng Chương này giới thiệu vào các kỹ thuật dò biên được áp dụng trong chương trình. Bằng cách sử dụng hàm Gauss để làm trơn ảnh sau đó dùng các kỹ thuật tìm kiếm trực tiếp 3 để đưa ra 5 kiểu biên khác nhau với một bức ảnh nói chung và khuôn mặt trong chương trình này. Chương 4: Kết luận và hướng phát triển Chương này tổng kết lại những gì đã đạt được và chưa đạt được. Từ đó nêu lên những kết quả hướng tới, hướng nghiên cứu và phát triển tiếp theo. 4 Chương 2. CÁC KỸ THUẬT DÒ BIÊN 2.1 Quy trình phát hiện biên ảnh đầu vào output H2.1. Quy trình phát hiện biên B1: Do ảnh ghi được thường có nhiễu, bước một là phải lọc nhiễu B2: Làm nổi biên sử dụng các toán tử phát hiện biên. B3: Định vị biên. Chú ý rằng kỹ thuật nổi biên gây tác dụng phụ là gây nhiễu làm một số biên giả xuất hiện do vậy cần loại bỏ biên giả. B4: Liên kết và trích chọn biên. 2.2 Kỹ thuật phát hiện biên trực tiếp Phương pháp này chủ yếu dựa vào sự biến thiên độ sáng của điểm ảnh để làm nổi biên bằng kỹ thuật đạo hàm. - Nếu lấy đạo hàm bậc nhất của ảnh: ta có phương pháp Gradient Định nghĩa: Gradient là một vector f(x, y) có các thành phần biểu thị tốc độ thay đổi mức xám của điểm ảnh (theo hai hướng x, y trong bối cảnh xử lý ảnh hai chiều) tức: Trong đó dx, dy là khoảng cách giữa 2 điểm kế cận theo hướng x, y tương ứng (thực tế chọn dx=dy=1). Đây là phương pháp dựa trên đạo hàm riêng bậc nhất theo hướng x, y. Lọc nhiễu Làm nổi Định vị biên trích chọn biên 5 Gradient trong gốc tọa độ góc (r, θ), với r là vector, θ là góc 2.2.1 Kỹ thuật Gradient Theo định nghĩa về Gradient, nếu áp dụng nó vào xử lý ảnh, việc tính toán sẽ rất phức tạp. Để đơn giản mà không mất tính chất của phương pháp Gradient, người ta sử dụng kỹ thuật Gradient dùng cặp mặt nạ H1, H2 trực giao (theo 2 hướng vuông góc). Nếu định nghĩa g1, g2 là Gradient theo hai hướng x, y tương ứng thì biên độ g(m, n) tại điểm (m, n) được tính: Đặt A0 = g(m,n); Để giảm độ phức tạp tính toán, A0 được tính gần đúng như sau: Xét một số toán tử Gradient tiêu chuẩn như toán tử Robert, Sobel, Prewitt, đẳng hướng (Isometric), 4-lân cận dưới đây. H2.2. Vector gradient 6 Toán tử Robert (1965). Robert áp dụng công thức tính Gradient tại điểm (x, y) như hình trên Wij với mỗi điểm ảnh I(x, y) đạo hàm theo x, y được ký hiệu tương ứng gx, gy: Các công thức kể trên được cụ thể hóa bằng các mặt nạ theo chiều x và y tương ứng như sau: Mặt nạ Robert Toán tử (mặt nạ) Sobel Toán tử Sobel được Duda và Hart [5] đặt ra năm 1973 với các mặt nạ tương tự như của Robert nhưng cấu hình khác như sau: H2.3. Toán tử 4 lân cận 7 Hướng ngang (x) Hướng dọc (y) Mặt nạ Prewitt Toán tử Prewitt đưa ra năm 1970 có dạng: Hướng ngang (x) Hướng dọc (y) Mặt nạ đẳng hướng: Một mặt nạ khác cũng được nêu như dưới đây gọi là mặt nạ đẳng hướng (Isometric). Hướng ngang (x) Hướng dọc (y) Toán tử 4-lân cận (4-Neighbour Operator). Toán tử 4-lân cận được Chaudhuri và Chandor (1984) nêu ra trong đó mặt nạ có kích thước 3x3 được thay cho mặt nạ 2x2 của toán tử Robert. Các mặt nạ này được cho: H3. Mặt nạ 4 lân cận 8 H2.4. Mặt nạ 8 hướng theo Kirsh. Một vài nhận xét: Toán tử Prewitt có thể tách sườn tốt hơn toán tử Sobel, trong khi đó toán tử Sobel tách các sườn trên các đường chéo tốt hơn. Mặt khác, các toán tử Robert và các toán tử 4-lân cận có nhược điểm là nhạy với nhiễu. Các toán tử Gradient và Sobel giảm nhiễu do tác dụng của lọc trung bình các điểm lân cận. Như vậy, để đạt được kết quả mong muốn các toán tử Gradient thường được dùng trước để làm sạch nhiễu. Các mặt nạ của các toán tử trên có kích thước 2x2 hoặc 3x3 chiều. Các mặt nạ có số chiều lớn hơn cũng được sử dụng. Ví dụ trong kỹ thuật phát hiện biên người ta dùng mặt nạ 5x5 cho toán tử Sobel: Toán tử Sobel 5x5. Các toán tử kể trên đều sử dụng các mặt nạ theo hai chiều (x, y) tức là 4 hướng (-x, y- y, y) với mục đích cho kết quả chính xác hơn(khi mà tốc độ và bộ nhớ máy tính tốt. ) 2.2.2 Toán tử la bàn Kirsh đã đã đề xuất mặt nạ 8 hướng như 8 hướng của La bàn(Compass). Hình dưới là mô hình 8 hướng và được đặt tên theo hướng địa lý và theo chiều kim 9 đồng hồ: Đông, Đông – Nam, Nam, Nam – Tây, Tây, Tây – Nam, Tây – Bắc, Bắc, Đông – Bắc; mỗi hướng lệch nhau 45 độ. Toán tử la bàn Kirsh: Có nhiều toán tử la bàn khác nhau. Ta xem xét toán tử la bàn Kirsh đặc trưng bởi tám mặt nạ với kích thước 3x3 như sau: Ký hiệu là Gradient theo 8 hướng như 8 mặt nạ kể trên, khi đó biên độ Gradient tại điểm ảnh (x, y) được tính theo - Nếu lấy theo đạo hàm bậc hai của ảnh: ta có phương pháp Laplace Hai phương pháp này gọi chung là phương pháp dò biên cục bộ. Toán tử la bàn khác: Ngoài toán tử la bàn Kirsh, một số toán tử la bàn khác sử dụng bộ mặt nạ 8 hướng khác như: 10 Hoặc: Trường hợp tổng quát, người ta có thể mở rộng các mặt nạ với n hướng cách đều tương ứng với các mặt Wi; i=1, 2, …, n. Khi đó, biên độ tại hướng thứ i với mặt nạ Wi được xác định: 2.2.3 Kỹ thuật Laplace Để khắc phục hạn chế và nhược điểm của phương pháp Gradient, trong đó sử dụng đạo hàm riêng bậc nhất người ta nghĩ đến việc sử dụng đạo hàm riêng bậc hai hay toán tử Laplace. Phương pháp dò biên theo toán tử Laplace hiệu quả hơn phương pháp toán tử 11 Gradient trong trường hợp mức xám biến đổi chậm, miền chuyển đổi mức xám có độ trải rộng. Toán tử Laplace được đĩnh nghĩa như sau: Toán tử Laplace dùng một số mặt nạ khác nhau nhằm tính gần đúng đạo hàm riêng bậc 2. Các dạng mặt nạ theo toán tử Laplace bậc 3x3 có thể: Ghi chú: Mặt nạ H1 còn cải biên bằng việc lấy giá trị ở tâm bằng 8 thay vì giá trị 4. Để thấy rõ việc xấp xỉ đạo hàm riêng bậc 2 trong không gian 2 chiều với mặt nạ H1 làm ví dụ, ta có thể tính gần đúng như sau: Do đó: Tóm lại: Kỹ thuật theo toán tử Laplace tạo đường biên mảnh (có độ rộng 1 pixel). Nhược điểm của kỹ thuật này rất nhạy với nhiễu, do vậy đường biên thu được thường kém ổn định. 2.2.4 Tách sườn theo ảnh Canny Bộ tách sườn ảnh theo Canny (1986) dựa trên cặp đạo hàm riêng bậc nhấtvới việc làm sạch nhiễu. Mục này được để riêng vì đây là phương pháp tách đường biên khá phổ biến được dùng theo toán tử đạo hàm. Như đã nói, phương pháp đạo hàm chịu ảnh hưởng lớn của nhiễu. Phương pháp đạt hiệu quả cao khi xấp xỉ đạo hàm bậc nhất của Gauss. Với fx, fy là đạo hàm riêng theo x,y của f. 12 Do vậy: Lấy đạo hàm riêng theo x và y của G ta được: H2.5. Mô hình tính của phương pháp Canny. Do bộ lọc Gauss là tách được, ta có thể thực hiện riêng biệt các tích chập theo x và y: Từ đó ta có: Với biên độ và hướng tính theo công thức trên, thuật toán được minh họa như hình H2.5 trên. 2.2.5 Dò biên theo quy hoạch động Như trên đã nói, dò biên theo phương pháp Gradient là xác định cực trị cục bộ của Gradient theo các hướng; còn phương pháp Laplace dựa vào các điểm không của đạo hàm bậc hai. Phương pháp dò biên theo quy hoạch động là phương pháp tìm cực trị tổng thể theo nhiều bước. Nó dựa vào nguyên lý tối ưu của Bellman. Nguyên lý này phát biểu như sau: “Con đường tối ưu giữa 2 điểm cho trước cũng là tối ưu giữa 2 điểm bất kỳ nằm trên đường tối ưu đó”. 13 Thí dụ, nếu C là một điểm trên con đường tối ưu giữa A và B thì đoạn CB cũng là còn đường tối ưu từ C đến B không kể đến ta đến C bằng cách nào. H2.6. Minh họa nguyên lý Bellman Trong kỹ thuật này, giả sử bản đồ biên đã được xác định và được biểu diễn dưới dạng đồ thị liên thông N chặng. Giả sử hàm đánh giá được tính theo công thức: Với: • Xk, k=1,...,N: Biểu diễn các đỉnh đồ thị của đồ thị trong chặng thứ k; • D(x, y): Khoảng cách giữa 2 đỉnh x và y tính theo các định nghĩa tương ứng về khoảng cách; • |g(xk)| và θ(xk) Gradient biên độ và Gradient hướng ở đỉnh xk. • α và β các hằng số không âm. Đường bao tối ưu sẽ nhận được bằng cách nối các đỉnh xk, k=1,..., N nào đó sao cho S(x1,..., xN, N) đạt cực đại. Định nghĩa hàm ф như sau: Bây giờ ta có: 14 Lấy N = k. Như vậy: Với cách này, thay vì tìm tối ưu toàn cục phức tạp của S(x1, …,xN, N), ta tìm tối ưu của N chặng theo tối ưu 2 biến. Trong mỗi chặng, với mỗi xk tìm tối ưu, ( k x k φ. Để dễ hình dung, xét ví dụ sau: Giả sử có bản đồ biểu diễn bởi đồ thị liên thông. Theo phương pháp trên có 5 ) 1, ( = A φ, với k =2 có . ) 2, ( 12 max(11,12) D = = φ Điều đó có nghĩa là đường từ A đến D đi qua C và ACD là biên được chọn với k=2. Tương tự, với k=4, có hai đường được chọn là ACDEF và AGHJ. Tuy nhiên, với k=5 thì đoạn JB bị loại và chỉ tồn tại đường duy nhất với cực đại là 28. Như vậy, biên được xác định là ADEFB. a. Đồ thị liên thông biểu diễn biên b. Quá trình dò biên theo quy hoạch động H2.7. Dò biên theo phương pháp quy hoạch động Trên hình những đường nét đứt đoạn biểu thị cung bị loại; đường nét liền có mũi tên biểu thị đường đi hay biên của ảnh. 15 2.3 Kỹ thuật phát hiện biên gián tiếp Nếu bằng cách nào đấy, chúng ta thu được các vùng ảnh khác nhau thì đường phân cách giữa các vùng đó chính là biên. Nói cách khác, việc xác định đường bao của ảnh được thực hiện từ ảnh và được phân vùng. Phương pháp dò biên gián tiếp khó cài đặt nhưng áp dụng tốt khi sự biến thiên độ sáng nhỏ. 2.4 Một số phương pháp khác Ngoài các phương pháp trên, người ta cũng áp dụng một số phương pháp khác cải tiến như tiếp cận bởi mô hình mặt, cách tiếp cận tối ưu hóa. Cách tiếp cận theo mô hình mặt dựa vào việc thực hiện xấp xỉ đa thức trên ảnh gốc hay ảnh đã thực hiện phép lọc Laplace. Cách tiếp cận tối ưu nhằm xác định một hàm (một bộ lọc), là