Khóa luận Phát hiện mặt người trong ảnh và ứng dụng

i  ĐẠI HỌC CƠNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI ----W—X---- Lê Mạnh Tuấn PHÁT HIỆN MẶT NGƯỜI TRONG ẢNH VÀ ỨNG DỤNG KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng Nghệ Thơng Tin Hà Nội – 2009 ii  ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Lê Mạnh Tuấn PHÁT HIỆN MẶT NGƯỜI TRONG ẢNH VÀ ỨNG DỤNG KHỐ 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: TS. Nguyễn Hải Châu HÀ NỘI - 2009 iii  Lời cảm ơn Sau một thời gian dài học tập và nghiên cứu, cuối cùng em cũng đã hồn thành khĩa luận tốt nghiệp này, đây là dịp tốt nhất để em cĩ thể gửi lời cảm ơn đến mọi người. Em xin gửi lời cảm ơn sâu sắc đến Tiến sĩ Nguyễn Hải Châu, đã tận hình hướng dẫn, định hướng cho em trong suốt thời gian thực hiện đề tài. Thầy đã cho em những lời khuyên quý báu giúp em hồn thành tốt khĩa luận. Em xin cảm ơn khoa Cơng Nghệ Thơng Tin trường Đại Học Cơng Nghệ - Đại Học Quốc Gia Hà Nội, cảm ơn các thầy cơ trong khoa đã tận tình giảng dậy, truyền đạt cho em những kiến thức quý báu trong những năm học vừa qua, giúp cho em cĩ một nền tảng kiến thức vững chắc để thực hiện khĩa luận cũng như nghiên cứu học tập sau này. Tơi xin cảm ơn tất cả bạn bè, anh, chị, những người đã giúp đỡ, khích lệ cũng như phê bình, gĩp ý, giúp tơi hồn thành khĩa luận một cách tốt nhất. Cuối cùng, con cảm ơn bố, mẹ, những người luơn luơn quan tâm, chăm sĩc cho con cả về vật chất lẫn tinh thần, luơn tạo điều kiện tốt nhất cho con cĩ thể chuyên tâm học tập, nghiên cứu. Gia đình luơn là nguồn động viên, là chỗ dựa tinh thần vững chắc cho con. Hà nội, ngày 24 tháng 5 năm 2009 Sinh viên Lê Mạnh Tuấn iv  TĨM TẮT Ngày nay các hệ thống nhận dạng mặt người đang được ứng dụng trong nhiều lĩnh vực, đặc biệt là an ninh và bảo mật. Nhận dạng mặt người tức là đưa ra những thơng tin về đối tượng được đưa vào từ một bức ảnh, hay từ camera quan sát. Bước đầu tiên của một hệ thống nhận dạng mặt người là phát hiện khuơn mặt, tức xác định vị trí khuơn mặt trên bức ảnh, sau đấy tách khuơn mặt ra khỏi ảnh để tiến hành nhận dạng. Trong khĩa luận này em xin nêu một trong những phương pháp để phát hiện khuơn mặt trong ảnh, sau đấy mở rộng ra với phát hiện mặt người trong video và webcam. Sau khi đã xem xét các hướng tiếp cận khác nhau, em chọn phương pháp tiếp cận học máy bằng Adaboost và mơ hình Cascade of classifiers. Điểm mạnh của Adaboost là tốc độ phát hiện khuơn mặt khá nhanh. Kết quả thử nghiệm cho thấy chương trình đạt độ chính xác khá cao với các ảnh mặt người được chụp trực diện bằng máy kĩ thuật số. v  MỤC LỤC TĨM TẮT............................................................................................................................iv MỤC LỤC ............................................................................................................................v DANH SÁCH THUẬT NGỮ ............................................................................................vii DANH MỤC HÌNH VẼ ................................................................................................... viii DANH SÁCH TỪ VIẾT TẮT ............................................................................................ix MỞ ĐẦU ..............................................................................................................................1 Chương 1 TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP XÁC ĐỊNH MẶT NGƯỜI ............3 1. Giới thiệu về bài tốn xác định mặt người trong ảnh................................................ 3 2. Định nghĩa bài tốn xác định mặt người. .................................................................. 3 3. Những khĩ khăn và thách thức đối với bài tốn xác định mặt người. ...................... 3 4. Các ứng dụng của xác định mặt người. ..................................................................... 4 4.1. Xác minh tội phạm................................................................................................. 4 4.2. Camera chống trộm................................................................................................ 4 4.3. Bảo mật. ................................................................................................................. 4 4.4. Lưu trữ khuơn mặt ................................................................................................. 4 4.5. Các ứng dụng khác ................................................................................................ 5 5. Xác định phạm vi đề tài............................................................................................. 5 Chương 2 CÁC CƠNG TRÌNH NGHIÊN CỨU ................................................................7 1. Các phương pháp chính để xác định mặt người. ....................................................... 7 1.1. Hướng tiếp cận dựa trên tri thức........................................................................... 8 1.2. Hướng tiếp cận dựa trên đặc trưng khơng thay đổi. ............................................ 10 1.3. Hướng tiếp cận dựa trên so sánh khớp mẫu. ....................................................... 13 1.4. Hướng tiếp cận dựa trên diện mạo....................................................................... 16 Chương 3 CƠ SỞ LÝ THUYẾT .......................................................................................23 1. Tổng quan về Adaboost........................................................................................... 23 1.1. Tiếp cận Boosting ................................................................................................ 23 1.2. Adaboost .............................................................................................................. 24 1.3. Các đặc trưng Haar-Like...................................................................................... 28 1.4. Cascade of Classifiers .......................................................................................... 31 vi  1.5. Cascade of boosting classifiers ............................................................................ 33 Chương 4 XÂY DỰNG ỨNG DỤNG ..............................................................................34 1. Sơ lược về OpenCV ................................................................................................ 34 2. Tổng quan về một hệ thống phát hiện mặt người trong ảnh ................................... 35 3. Phân tích – thiết kế hệ thống phát hiện mặt người .................................................. 35 3.1. Phân tích............................................................................................................... 35 3.2. Thiết kế hệ thống ................................................................................................. 36 3.3. Thiết kế cơ sở dữ liệu........................................................................................... 38 3.4. Thiết kế giao diện................................................................................................. 39 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN..........................................................................41  vii  DANH SÁCH THUẬT NGỮ Thuật ngữ Giải thích Classifier (bộ phân loại) Một bộ phân loại được xây dựng theo một thuật tốn học máy nào đấy, dùng để phân loại các đối tượng (khuơn mặt hay khơng phải khuơn mặt) False alarm Là tỉ lệ nhận dạng sai của các bộ phân loại Feature (đặc trưng) Các thơng tin giúp nhận biết đối tượng. Haar-like feature Các đặc trưng của đối tượng trong ảnh. Các đặc trưng này thường được định nghĩa bằng các tính tốn với tổng điểm ảnh của một vùng nào đĩ trên bức ảnh. Hit rate Là tỉ lệ nhận dạng đúng của bộ phân loại Max false alarm Đạt được tỉ lệ sai này thì bộ phân loại được xây dựng thành cơng, tỉ lệ sai này là một giá trị bé, cĩ thể chấp nhận được trong bài tốn phân loại. Strong classifier (bộ phân loại mạnh) Bộ phân loại được xây dựng từ nhiều bộ phân loại yếu, cĩ độ chính xác cao. Threshold (ngưỡng) Ngưỡng là giá trị ranh giới giữa các lớp, giá trị của ngưỡng cĩ thể điều chỉnh được thường được chọn từ thực nghiệm. (Người ta thử bộ nhận dạng với các giá trị ngưỡng khác nhau để chọn ra ngưỡng cho tỉ lệ nhận dạng đúng tốt nhất) Weak classifier (bộ phân loại yếu) Bộ phân loại đơn giản cĩ độ chính xác khoảng 50%. viii  DANH MỤC HÌNH VẼ Hình 1: Một phương pháp xác định khuơn mặt điển theo hướng tiếp cận top-down. .........8 Hình 2: Phương pháp chiếu ................................................................................................10 Hình 3: Một mẫu khuơn mặt ..............................................................................................15 Hình 4: các vector quan sát để huấn luyện cho HMM .......................................................20 Hình 5: Các trạng thái ẩn....................................................................................................21 Hình 6: Xác định khuơn mặt bằng HMM...........................................................................21 Hình 7: Boosting.................................................................................................................24 Hình 8 : 4 đặt trưng Haar-like cơ bản.................................................................................28 Hình 9: Các đặc trưng mở rộng của các đặc trưng Haar-like cơ sở ...................................29 Hình 10: Cách tính Integral Image của ảnh........................................................................30 Hình 11:Ví dụ cách tính nhanh tổng các điểm ảnh của vùng D trên ảnh...........................30 Hình 12: Ví dụ cách tính nhanh tổng điểm ảnh của vùng D trên ảnh với các đặc trưng xoay 45o ..............................................................................................................................30 Hình 13: cascade of classifiers ...........................................................................................32 Hình 14: Cascade of boosting classifiers............................................................................33 Hình 15: Cấu trúc cơ bản của OpenCV..............................................................................34 Hình 16: Tổng quan về hệ thống phát hiện mặt người trong ảnh.......................................35 Hình 17: Biểu đồ ngữ cảnh của hệ thống ...........................................................................36 Hình 18: Biểu đồ phân rã chức năng. .................................................................................38 Hình 19: Sơ đồ thực thể quan hệ ( ERM )..........................................................................39 Hình 20: Giao diện của chương trình .................................................................................40 ix  DANH SÁCH TỪ VIẾT TẮT STT Kí hiệu Từ tiếng anh Ý nghĩa 1 CSDL Database Cơ sở dữ liệu 2 HMM Hidden Markov Model Mơ hình Markov ẩn 3 ML Maximum-Likelihood Phương thức cực đại khả năng 4 PCA Principal Component Analysis Phân tích thành phần chính 5 PDF Probility Density Hàm mật độ xác xuất 6 RSAT Rotated Summed Area Table Mảng hai chiều dùng để tính nhanh các đặc trưng xoay 45o 7 SAT Summed Area Table Mảng hai chiều dùng để tính nhanh các đặc trưng haar-like cơ bản 1  MỞ ĐẦU Cơng nghệ thơng tin đang được ứng dụng trong mọi lĩnh vực của cuộc sống. Với một hệ thống máy tính, chúng ta cĩ thể làm được rất nhiều việc, tiết kiện thời gian và cơng sức. Điển hình như cơng việc nhận dạng mặt người. Ngày xưa, muốn tìm kiếm một kẻ tình nghi trong siêu thị hay sân bay, các nhân viên an ninh phải tìm kiếm trên từng màn hình camera theo dõi. Ngày nay, cơng việc đấy đã được làm tự động nhờ các hệ thống nhận dạng mặt người. Phát hiện mặt người trong ảnh là một phần quan trọng của hệ thống nhận dạng mặt người đĩ, giải quyết tốt việc phát hiên mặt người sẽ giúp tiết kiệm thời gian và nâng cao độ chính xác của việc nhận dạng khuơn mặt. Phát hiện mặt người cũng là một bài tốn nhận dạng đơn giản, hệ thống chỉ cần phân loại đối tượng đưa vào cĩ phải mặt người hay khơng phải mặt người. Ở mức độ cao hơn, sau khi đã phát hiện được khuơn mặt, các khuơn mặt đĩ sẽ được so sánh với các khuơn mặt cĩ trong dữ liệu để nhận dạng xem khuơn mặt đấy là của ai (thường áp dụng trong nhận dạng khuơn mặt của người nổi tiếng hoặc của tội phạm đang bị truy nã). Bài tốn phát hiện mặt người được bắt đầu nghiên cứu từ những năm 1990s, và đã cĩ rất nhiều cơng trình nghiên cứu về phát hiện khuơn mặt trong ảnh, tuy nhiên cho đến nay, các nhà khoa học vẫn khơng ngừng tìm các hướng tiếp cận mới, các thuật tốn mới nhằm nâng cao hiệu suất của việc phát hiện khuơn mặt cũng như việc nhận dạng mặt người. Với mục tiêu chính là tìm hiểu giải thuật adaboost, các đặc trưng haar-like, mơ hình Cascade of Classifiers, đồng thời áp dụng vào bài tốn phát hiện mặt người trong ảnh, khĩa luân được trình bầy trong bốn chương với bố cục như sau: Chương 1: Tổng quan về các phương pháp xác định mặt người : Giới thiệu tổng quan về bài tốn xác định mặt người trong ảnh, các ứng dụng và những khĩ khăn của bài tốn, đồng thời xác định phạm vi của đề tài. Chương 2: Các cơng trình nghiên cứu : Nêu chi tiết bài tốn phát hiện mặt người, các hướng tiếp cận giải quyết bài tốn, các nghiên cứu và thành quả đạt được của các nhà nghiên cứu trong bài tốn xác định mặt người. 2  Chương 3: Cơ sở lý thuyết : Đi sâu vào hướng tiếp cận dựa theo thuật tốn học máy adaboost. Giới thiệu về các đặc trưng haar-like của khuơn mặt, cách tính các đặc trưng haar-like. Tiếp theo là giới thiệu về mơ hình cascade of classifiers và cách áp dụng vào bài tốn phát hiện mặt người trong ảnh. Chương 4: Xây dựng ứng dụng : Xây dựng một chương trình demo về phát hiện mặt người trong ảnh. Nêu lên các phân tích – thiết kế về chương trình. Cuối cùng là kết luận và hướng phát triển: Tĩm tắt những kết quả đạt được, những hạn chế và nêu lên các hướng phát triển trong tương lai. 3  Chương 1 TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP XÁC ĐỊNH MẶT NGƯỜI 1. Giới thiệu về bài tốn xác định mặt người trong ảnh. Trong nhiều năm qua, cĩ rất nhiều cơng trình nghiên cứu về bài tốn nhận dạng mặt người. Các nghiên cứu đi từ bài tốn đơn giản, từ việc nhận dạng một mặt người trong ảnh đen trắng cho đến mở rộng cho ảnh mầu và cĩ nhiều mặt người trong ảnh. Đến nay các bài tốn xác định mặt người đã mở rộng với nhiều miền nghiên cứu như nhận dạng khuơn mặt, định vị khuơn mặt, theo dõi mặt người hay nhận dạng cảm xúc mặt người… Phát hiện mặt người trong ảnh là phần đầu tiên của một hệ thống nhận dạng mặt người. Các hệ thống nhận dạng khuơn mặt được bắt đầu xây dựng từ những năm 1970, tuy nhiên do cịn hạn chế về các luật xác định mặt người nên chỉ được áp dụng trong một số ứng dụng như nhận dạng thẻ căn cước. Nĩ chỉ được phát triển mạnh mẽ từ những năm 1990 khi cĩ những tiến bộ trong cơng nghệ video và ngày nay thì các ứng dụng của xác định mặt người đã trở nên phổ biến trong cuộc sống. 2. Định nghĩa bài tốn xác định mặt người. 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à kích thước của các khuơn mặt người trong các ảnh bất kì. Kỹ thuật này nhận biết các đặc trưng của khuơn mặt và bỏ qua những thứ khác như: tịa nhà, cây cối, cơ thể … 3. Những khĩ khăn và thách thức đối với bài tốn xác định mặt người. Việc xác định khuơn mặt người cĩ những khĩ khăn nhất định như: • Hướng của khuơn mặt đối với máy ảnh, như: nhìn thẳng, nhìn nghiêng hay nhìn từ trên xuống. Cùng trong một ảnh cĩ thể cĩ nhiều khuơn mặt ở những tư thế khác nhau. • Sự cĩ mặt của các chi tiết khơng phải là đặc trưng riêng của khuơn mặt người, như: râu quai nĩn, mắt kính, …. • Các nét mặt khác nhau trên khuơn mặt, như: vui, buồn, ngạc nhiên, …. • Mặt người bị che khuất bởi các đối tượng khác cĩ trong ảnh. 4  • Sự biểu cảm của khuơn mặt : sự biểu cảm cĩ thể làm thay đổi đáng kể các đặc trưng và thơng số của khuơn mặt, ví dụ như khuơn mặt của cùng một người sẽ rất khác khi người đấy cười, tức giận hay sợ hãi … 4. Các ứng dụng của xác định mặt người. Xác định mặt người thường là một phần của một hệ thống (facial recognition system). Nĩ thường được dùng trong giám sát video, giao tiếp người máy và quản lý cơ sở dữ liệu ảnh… Các ứng cơ bản của xác định mặt người cĩ thể kể đến là: 4.1. Xác minh tội phạm. Dựa vào ảnh của một người, nhận dạng xem người đấy cĩ phải là tội phạm hay khơng bằng cách so sách với các ảnh tội phạm đang được lưu trữ. Hoặc cĩ thể sử dụng camera để phát hiện tội phạm trong đám đơng. Ứng dụng này giúp cơ quan an ninh quản lý con người tốt hơn. 4.2. Camera chống trộm. Các hệ thống camera sẽ xác định đâu là con người và theo dõi xem con người đĩ cĩ làm gì phạm pháp khơng, ví dụ như lấy trộm đồ, xâm nhập bất hợp pháp vào một khu vực nào đĩ. 4.3. Bảo mật. Các ứng dụng về bảo mật rất đa dạng, một trong số đĩ là cơng nghệ nhận dạng mặt người của laptop, cơng nghệ này cho phép chủ nhân của máy tính chỉ cần ngồi trước máy là cĩ thể đăng nhập được. Để sử dụng cơng nghệ này, người dùng phải sử dụng một webcam để chụp ảnh khuơn mặt của mình và cho máy “học” thuộc các đặc điểm của khuơn mặt giúp cho quá trình đăng nhập sau này. 4.4. Lưu trữ khuơn mặt Xác định mặt người cĩ thể được ứng dụng trong các trạm rút tiền tự động (ATM) để lưu trữ khuơn mặt của người rút tiền. Hiện nay cĩ những người bị người khác lấy trộm thẻ ATM và mã PIN, và bị rút tiền trộm, hoặc cĩ những chủ tài khoản đi rút tiền nhưng lại báo với ngân hàng là bị mất thẻ và bị rút tiền trộm. Nếu lưu trữ được khuơn mặt của người rút tiền, ngân hàng cĩ thể đối chứng và xử lý dễ dàng hơn. 5  4.5. Các ứng dụng khác • Điều khiển vào ra: văn phịng, cơng ty, trụ sở, máy tính, Palm, …. Kết hợp thêm vân tay và mống mắt. Cho phép nhân viên được ra vào nơi cần thiết. • An ninh sân bay, xuất nhập cảnh (hiện nay cơ quan xuất nhập cảnh Mỹ đã áp dụng). Dùng camera quan sát để xác thực người nhập cảnh và kiểm tra xem người đấy cĩ phải là tội phạm hay phần tử khủng bố khơng. • Tìm kiếm và tổ chức dữ liệu liên quan đến con người thơng qua khuơn mặt người trên nhiều hệ cơ sở dữ liệu lưu trữ thật lớn, như internet, các hãng truyền hình, …. Ví dụ: tìm các đoạn video cĩ tổng thống Bush phát biểu, tìm các phim cĩ diễn viên Tăng Thanh Hà đĩng, tìm các trận đá bĩng cĩ Cơng Vinh đá, … • Kiểm tra trạng thái người lái xe cĩ ngủ gật, mất tập trung hay khơng, và hỗ trợ thơng báo khi cần thiết. • Tương lai sẽ phát triển các loại thẻ thơng minh cĩ tích hợp sẵn đặc trưng của người dùng trên đĩ, khi bất cứ người dùng khác dùng để truy cập hay xử lý tại các hệ thống sẽ được yêu cầu kiểm tra các đặc trưng khuơn mặt so với thẻ để biết nay cĩ phải là chủ thẻ hay khơng. • Hãng máy chụp hình Canon đã ứng dụng bài tốn xác định khuơn mặt người vào máy chụp hình thế hệ mới để cho kết quả hình ảnh đẹp hơn, nhất là khuơn mặt người. 5. Xác định phạm vi đề tài Trong đề tài này, tơi tập trung vào việc xác định khuơn mặt trong ảnh, video hoặc webcam. Từ đấy lưu khuơn mặt tìm được vào CSDL để phục vụ cho các mục đích khác ( chẳng hạn như nhận dạng mặt người hoặc ghép khuơn mặt vào bức ảnh khác … ). Do các điều kiện khĩ khăn đã nêu ở trên ( mục 3 chương 1) tơi xin đưa ra những giả định và rành buộc sau để giảm độ phức tạp của bài tốn: • Các khuơn mặt được chụp thẳng hoặc gĩc nghiêng khơng đáng kể (bé hơn 10o) • Phơng nền của ảnh khơng quá phức tạp • Ảnh được chụp trong điều kiện ánh sáng bình thường. 6  • Đối với video hoặc webcam, do cĩ thể tách thành các xử lý trên ảnh nên với những video phức tạp hay webcam quá kém, chương trình sẽ khơng thực hiện được tốt nhất cĩ thể. 7  Chương 2 CÁC CƠNG TRÌNH NGHIÊN CỨU 1. Các phương pháp chính để xác định mặt người. Dựa vào tính chất của các phương pháp xác định mặt người trên ảnh, các phương pháp này được chia thành bốn loại chính, tương ứng với bốn hướng tiếp cận khác nhau. Ngồi ra cũng cĩ rất nhiều nghiên cứu mà phương pháp xác định mặt người khơng chỉ dựa vào một hướng mà cĩ liên quan đến nhiều hướng. • Hướng tiếp cận dựa trên tri thức: Dựa vào các thuật tốn, mã hĩa các đặc trưng và quan hệ giữa các đặc trưng của khuơn mặt thành các luật. Đây là hướng tiếp cận theo kiểu top-down. • Hướng tiếp cận dựa trên đặc trưng khơng thay đổi: Xây dựng các thuật tốn để tìm các đặc trưng của khuơn mặt mà các đặc trưng này khơng thay đổi khi tư thế khuơn mặt hay vị trí đặt camera thay đổi. Hướng tiếp cận này là hướng tiếp cận theo kiểu bottom-up. • Hướng tiếp cận dựa trên so sánh khớp mẫu: Dùng các mẫu chuẩn của khuơn mặt (các mẫu này được định nghĩa bằng tay trước hoặc được tham số hĩa bằng mộ hàm số) để mơ tả các khuơn mặt hay các đặc trưng của khuơn mặt. Mẫu này được sử dụng để phát hiện khuơn mặt bằng cách quét nĩ qua ảnh và tính tốn giá trị tương đồng cho mỗi vị trí. Việc xuất hiện một khuơn mặt tại một vị trí nào đĩ trong ảnh phụ thuộc vào giá trị tương đồng của điểm đĩ so với mẫu chuẩn • Hướng tiếp cận dựa trên diện mạo: Trái ngược với hướng tiếp cận dựa trên khuơn mẫu, các mơ hình (hay các mẫu) sẽ được học từ một tập ảnh huấn luyện mà thể hiện tính chất tiêu biểu của sự xuất hiện của mặt người trong ảnh. Sau đĩ hệ thống (mơ hình) sẽ xác định mặt người. Phương pháp này cịn được biết đến với tên gọi tiếp cận theo các phương pháp học máy. 8  1.1. Hướng tiếp cận dựa trên tri thức 1.1.1. Tư tưởng Trong hướng tiếp cận này, các phương pháp xác định mặt người được xây dựng dựa vào các luật, các luật này phụ thuộc vào tri thức của các tác giả nghiên cứu về bài tốn xác định khuơn mặt. Dễ dàng xây dựng các luật cơ bản để mơ tả các đặc trưng của khuơn mặt và các quan hệ tương ứng. Ví dụ, một khuơn mặt thường cĩ hai mắt đối xứng qua trục thẳng đứng giữa khuơn mặt và cĩ một mũi một miệng. Các quan hệ đặc trưng cĩ thể là quan hệ về vị trí và khoảng cách tương đối. Khĩ khăn của hướng tiếp cận này đĩ là làm thế nào để chuyển các tri thức của con người về khuơn mặt sang các luật cho máy tính một cách hiệu quả. Nếu các luật này quá chi tiết, chặt chẽ thì sẽ cĩ thể xác định thiếu các khuơn mặt cĩ trong ảnh, nhưng nếu các luật quá tổng quát thì sẽ dẫn đến xác định sai khu vực khơng phải là khuơn mặt thành khuơn mặt. Ngồi ra cũng khĩ để mở rộng phạm vi của bải tốn để xác định các khuơn mặt cĩ nhiều tư thế khác nhau. 1.1.2. Các nghiên cứu Cĩ nhiều cách để xây dựng chương trình xác định mặt người theo hướng tiếp cận dựa trên tri thức. Thơng thường chương trình sẽ được xây dựng theo hướng dựa vào một phương pháp nào đấy chọn ra các ứng viên trong bức ảnh trước, sau đĩ sẽ áp dụng các luật để xác định ứng viên nào là khuơn mặt, ứng viên nào khơng phải là khuơn mặt. Quá trình này cĩ thể được áp dụng nhiều lần để giảm sai sĩt. Hình 1: Một phương pháp xác định khuơn mặt điển theo hướng tiếp cận top-down. Trên hình 1, Các luật được xây dựng dựa vào tri thức của người nghiên cứu về các đặc trưng của khuơn mặt (ví dụ như cường độ phân phơi và sự khác nhau ) của các vùng trên khuơn mặt 9  Yang và Huang đã sử dụng hướng tiếp cận dựa trên tri thức để xác định khuơn mặt [7]. Hệ thống của hai tác giả bao gồm ba mức luật. Đầu tiên các ơng sử dụng một khung cửa sổ để quét trên bức ảnh và thơng qua một số tập luật để xác định các ứng viên cĩ thể là mặt người, ví dụ như tìm phần trung tâm của khuơn mặt (phần tối hơn trong hình 1). Tiếp theo, dùng một tập luật để mơ tả tổng quát hình dáng khuơn mặt, lọc các ứng viên ở mức một thành một tập các ứng viên mới cĩ xác xuất là khuơn mặt cao hơn. Cuối cùng, các ơng lại dùng một tập luật khác để xem xét ở mức chi tiết các đặc trưng khuơn mặt ( cĩ thể là đặc trưng về mắt, mũi, miệng … ), từ đĩ lọc ra các ứng viên chính xác nhất. Cĩ thể nĩi cách làm của hai ơng là một cách làm mịn dần để đạt được kết quả tốt nhất, mặc dù tỷ lệ chính xác chưa cao, nhưng đây là tiền đề cho nhiều nghiên cứu sau này. Cĩ rất nhiều cơng trình nghiên cứu sử dụng phương pháp chiếu để xác định khuơn mặt. Kotropoulos và Pitas đưa ra một phương pháp gần tương tự với Yang và Huang. Đầu tiên, các vùng của khuơn mặt được định vị bởi phương pháp chiếu (đã được Kanade sử dụng thành cơng) để xác định biên của khuơn mặt. Với I(x,y) là giá trị xám của một điểm trong ảnh cĩ kích thước m x n ở tại vị trí (x,y), các hàm để chiếu ảnh theo phương ngang và thẳng đứng được định nghĩa như sau: Dựa trên biểu đồ hình chiếu ngang, khi xét biểu đồ biến thiên của HI hai ơng tìm được hai cực tiểu địa phương tương ứng với hai đỉnh đầu bên trái và bên phải của khuơn mặt. Cịn theo hình chiếu dọc, xét biến thiên và tìm cực tiểu địa phương của VI cũng cho ta các vị trí của miệng, đỉnh mũi và hai mắt. Các đặc trưng này đủ để xác định khuơn mặt. Hình 2.a cho một ví dụ về cách xác định như trên. Cách xác định này cĩ tỷ lệ xác định chính xác là 86.5% cho trường hợp chỉ cĩ một khuơn mặt trực diện và hình nền khơng phức tạp. Nếu hình nền phức tạp như hình 2.b thì rất khĩ tìm. Cịn nếu ảnh cĩ nhiều khuơn mặt (hình 2.c) thì sẽ khơng xác định được. 10  Hình 2: Phương pháp chiếu (a) Ảnh chỉ cĩ một khuơn mặt và hình nền đơn giản; (b) Ảnh chỉ cĩ một khuơn mặt và hình nền phức tạp; (c) Ảnh cĩ nhiều khuơn mặt 1.2. Hướng tiếp cận dựa trên đặc trưng khơng thay đổi. Tiếp cận dựa trên các đặc trưng khơng thay đổi là tiếp cận theo kiểu bottom up. Dựa trên thực tế, chúng ta cố gắng tìm ra những đặc điểm khơng thay đổi khi của khuơn mặt khi ở các tư thế khác nhau và các điều kiện mơi trường như ánh sáng khác nhau. Đã cĩ rất nhiều nghiên cứu về hướng tiếp cận này, các đặc điểm khơng thay đổi được tìm thấy như lơng mày, mắt, mũi, miệng hay các đường viền trên tĩc … Trên cơ sở các đặc trưng này, các nhà nghiên cứu xây dựng lên một mơ hình thống kê mơ tả quan hệ của các đặc trưng và từ đĩ xác định sự xuất hiện của khuơn mặt trong bức ảnh. Khĩ khăn của hướng tiếp cận này đĩ là phải mơ tả các đặc trưng khơng thay đổi và quan hệ giữa chúng phù hợp với điều kiện ánh sáng, độ nhiễu hay bị che khuất. 1.2.1. Các đặc trưng của khuơn mặt Cĩ rất nhiều nghiên cứu về các đặc trưng của khuơn mặt. Cĩ thể dựa vào các đặc trưng như hai mắt, hai lỗ mũi, miệng, phần nối giữa mũi và miệng … hoặc dựa vào đường viền của khuơn mặt. Leung đã đưa ra một mơ hình xác xuất để xác định khuơn mặt trong ảnh cĩ hình nền phức tạp dựa trên việc tìm kiếm các đặc trưng khơng thay đổi của khuơn mặt trong ảnh, sau đĩ dùng đồ thị ngẫu nhiên để xác định khuơn mặt. Tư tưởng của phương pháp này đĩ là xem bài tốn xác định khuơn mặt như là bài tốn tìm kiếm với mục tiêu là tìm thứ tự các đặc trưng khơng thay đổi của khuơn mặt. Dùng năm đặc trưng (hai mắt, hai lỗ mũi, phần nối giữa mũi và miệng) để mơ tả một khuơn mặt. Đồng thời tính quan hệ khoảng cách cho tất cả các cặp đặc trưng (như mắt trái, mắt phải), sau đấy dùng phân bố Gauss để 11  mơ hình hĩa. Một mẫu khuơn mặt được đưa ra thơng qua trung bình tương ứng cho một tập đa hướng, đa tỷ lệ của bộ lọc đạo hàm Gauss. Từ một ảnh, các đặc trưng của ứng viên được xác định bằng cách so khớp từng điểm ảnh khi lọc tương ứng với vector mẫu. Hai ứng viên cĩ đặc trưng đứng đầu sẽ được chọn để tìm kiếm cho các đặc trưng khác của khuơn mặt. Từ các đặc trưng khơng thay đổi, các đặc trưng khác sẽ được xác định thơng qua sự đánh giá xác xuất khoảng cách giữa các đặc trưng, hơn nữa phương sai của phép thống kê này cĩ thể được tính tốn trước để xác định các đặc trưng với xác xuất lớn. Tỷ lệ chính xác của phương pháp này là 86%. Bên cạnh tính khoảng cách liên quan để mơ tả quan hệ giữa các đặc trưng như Leung. Kendall [4], Mardia and Dryden [12] dùng lý thuyết xác suất thống kê về hình dáng. Dùng hàm mật độ xác suất (Probility Density Function - PDF) qua N điểm đặc trưng, tương ứng (xi, yi) là đặc trưng thứ i với giả sử là phân bố Gauss cĩ 2N-chiều. Các tác giả áp dụng phương thức cực đại khả năng (Maximum-Likelihood - ML) để xác định vị trí khuơn mặt. Một thuận lợi của phương pháp này là các khuơn mặt bị che khuất vẫn cĩ thể xác định được. Hạn chế phương pháp này đĩ là khơng xác định được nhiều khuơn mặt trong cùng một ảnh. Khơng dùng phương pháp xác xuất, Sirohey đưa một phương pháp khác xác định khuơn mặt từ một ảnh cĩ hình nền phức tạp [10], gọi là phương pháp dựa trên cạnh. Ơng dùng phương pháp Candy [9] và heuristics loại bỏ các cạnh để cịn lại duy nhất một đường bao xung quanh khuơn mặt. Dùng một hình ellipse để bao khuơn mặt, tách biệt vùng đầu và hình nền. Tỷ lệ chính xác của thuật tốn là 80%. Graf đưa ra một phương pháp khác để xác định đặc trưng, từ đĩ xác định khuơn mặt trong ảnh xám [8]. Dùng bộ lọc để làm nổi các biên, các phép tốn hình thái học (morphology) được dùng để làm nổi bật các vùng cĩ cường độ cao và hình dáng chắc chắn (như mắt). Thơng qua histogram để tìm các đỉnh nổi bật để xác định các ngưỡng chuyển ảnh xám thành hai ảnh nhị phân. Tiếp theo, ơng xác định các ứng viên khuơn mặt nhờ vào các thành phần đều xuất hiện trong cả hai ảnh nhỉ phân, sau đĩ phân loại xem các ứng viên cĩ phải là khuơn mặt khơng. Phương pháp được kiểm tra và cho kết quả tốt trên các ảnh chỉ cĩ đầu và vai của người. Tuy nhiên phương pháp này cịn một vấn đề đấy là sử dụng các phép tốn morphology như thế nào và làm sao xác định khuơn mặt trên các vùng ứng viên. 12  Park dùng Gaze để tìm ứng viên gĩc mắt, miệng và tâm mắt. Ơng xây dựng SVM (Support Vector Machine) đã được học trước đĩ để xác định các vị trí ứng viên cĩ phải là gĩc mắt, miệng, và tâm mắt hay khơng để theo vết con mắt người. Juan và Narciso xây dựng một khơng gian màu mới YCg’Cr’ để lọc các vùng là ứng viên khuơn mặt dựa trên sắc thái của màu da người. Sau khi cĩ ứng viên, hai ơng dùng các quan hệ về hình dáng khuơn mặt, mức độ cân đối của các thành phần khuơn mặt để xác định khuơn mặt người. Tương tự, Chang và Hwang cũng dùng khơng gian mầu Ycg’Cr’ với tỷ lệ chính xác hơn 80% trong ảnh xám. Jin xây dựng một bộ lọc để xác định ứng viên khuơn mặt người theo màu da người. Từ ứng viên này tác giả xác định khuơn mặt người theo hình dáng khuơn mặt và các quan hệ đặc trưng về thành phần khuơn mặt, với mắt phải được chọn làm gốc tọa độ để xét quan hệ. Tỷ lệ chính xác cho khuơn mặt chụp thẳng trên 80%. 1.2.2. Kết cấu của khuơn mặt. Khuơn mặt con người cĩ những kết cấu riêng biệt mà cĩ thể dùng để phân loại so với các đối tượng khác. Từ kết cấu của khuơn mặt xây dựng lên một bộ phân loại, gọi là kết cấu giống khuơn mặt (face-like texture). 1.2.3. Mầu sắc da. Thơng thường các ảnh màu khơng xác định trực tiếp trên tồn bộ dữ liệu ảnh mà các tác giả dùng tính chất sắc màu của da người (khuơn mặt người) để chọn ra được các ứng viên cĩ thể là khuơn mặt người (lúc này dữ liệu đã thu hẹp đáng kể) để xác định khuơn mặt người. 1.2.4. Đa đặc trưng. Gần đây cĩ nhiều nghiên cứu sử dụng các đặc trưng tồn cục như: màu da người, kích thước, và hình dáng để tìm các ứng viên khuơn mặt, rồi sau đĩ sẽ xác định ứng viên nào là khuơn mặt thơng qua dùng các đặc trưng cục bộ (chi tiết) như: mắt, lơng mày, mũi, miệng, và tĩc. Tùy mỗi tác giả sẽ sử dụng tập đặc trưng khác nhau. 13  1.3. Hướng tiếp cận dựa trên so sánh khớp mẫu. 1.3.1. Tư tưởng của so sánh khớp mẫu Trong hướng tiếp cận dựa trên so sánh khớp mẫu, các mẫu chuẩn của khuơn mặt (thường là khuơn mặt được chụp thẳng) sẽ được xác định trước hoặc được biểu diễn thành một hàm với các tham số cụ thể. Từ ảnh đầu vào, ta tính các giá trị tương quan so với các mẫu chuẩn về đường viền khuơn mặt, mắt, mũi và miệng. Thơng qua các giá trị tương quan này mà hệ thống sẽ quyết định cĩ hay khơng cĩ tồn tại khuơn mặt trong ảnh. Hướng tiếp cận này cĩ lợi thế là rất dễ cài đặt, nhưng khơng hiệu quả khi tỷ lệ, tư thế, và hình dáng thay đổi. 1.3.2. Xác định các mẫu. Sakai đã cố gắng thử xác định khuơn mặt người chụp thẳng trong ảnh [20]. Ơng dùng vài mẫu con (sub template) về mắt, mũi, miệng, và đường viền khuơn mặt để mơ hình hĩa một khuơn mặt. Mỗi mẫu con được định nghĩa trong giới hạn của các đoạn thẳng. Các đoạn thằng trong ảnh được trích bằng cách xem xét thay đổi của hệ số gĩc và so khớp các mẫu con. Đầu tiên tìm các ứng viên thơng qua mối tương quan giữa các ảnh con và các mẫu về đường viền. Sau đĩ, so khớp với các mẫu con khác. Hay nĩi một cách khác, giai đoạn đầu xem như là giai đoạn sơ chế để tìm ứng viên, giai đọan thứ hai là giai đoạn tinh chế để xác định ứng viên cĩ phải là khuơn mặt hay khơng. Ý tưởng này được duy trì cho đến các nghiên cứu sau này. Craw đưa ra một phương pháp xác định khuơn mặt người dựa vào các mẫu về hình dáng của các ảnh được chụp thẳng (dùng vẻ bề ngồi của hình dáng khuơn mặt). Đầu tiên dùng phép lọc Sobel (Phép lọc Sobel dựa vào tích vơ hướng của hai vector gradient) để tìm các cạnh. Các cạnh này sẽ được nhĩm lại theo một số ràng buộc. Sau đĩ, tìm đường viền của đầu, quá trình tương tự được lặp đi lặp lại với mỗi tỷ lệ khác nhau để xác định các đặc trưng khác như: mắt, lơng mày, và mơi. Sau đĩ Craw mơ tả một phương thức xác định dùng một tập cĩ 40 mẫu để tìm các đặc trưng khuơn mặt và điều khiển chiến lược dị tìm. Một số nhà nghiên cứu sử dụng hình chiếu như các mẫu để xác định khuơn mặt người. Silhouettes dùng PCA (phân tích thành phần chính – Principal Component Analysis - PCA) để cĩ một tập hình chiếu cơ bản từ các mẫu khuơn mặt, hình chiếu được mơ tả như một mảng các bit. Sau đấy dùng đặc trưng hình chiếu kết hợp biến đổi Hough 14  để xác định khuơn mặt người. Phương pháp này định nghĩa một số giả thuyết để mơ tả các khả năng của các đặc trưng khuơn mặt. Với một khuơn mặt sẽ cĩ một tập giả thuyết, gọi là lý thuyết DepsterShafer. Dùng một nhân tố tin cậy để kiểm tra sự tồn tại hay khơng của các đặc trưng của khuơn mặt, và kết hợp nhân tố tin cậy này với một độ đo để xem xét cĩ hay khơng cĩ khuơn mặt trong ảnh. Sinha dùng một tập nhỏ các ảnh bất biến trong khơng gian ảnh để mơ tả khơng gian các mẫu ảnh [15, 16]. Tư tưởng chính của ơng dựa vào sự thay đổi mức độ sáng của các vùng khác nhau của khuơn mặt (như hai mắt, hai má, và trán), (quan hệ về mức độ sáng của các vùng cịn lại thay đổi khơng đáng kể). Sau đấy xác định các cặp tỷ số của mức độ sáng của một số vùng (một vùng tối hơn hay sáng hơn) cho ta một lượng bất biến khá hiệu quả. Ơng lưu sự thay đổi độ sáng của các vùng trên khuơn mặt trong một tập thích hợp với các cặp quan hệ sáng hơn – tối hơn giữa các vùng nhỏ. Một khuơn mặt được xác định nếu nĩ thỏa mãn tất cả các cặp sáng hơn – tối hơn. Ý tưởng này xuất phát từ sự khác biệt của cường độ giữa các vùng kề cục bộ trên ảnh, sau này nĩ được mở rộng trên cơ sở biến đổi wavelet để xác định người đi bộ, xác định xe hơi, xác định khuơn mặt. Ý tưởng của Sinha cịn được áp dụng trong các nghiên cứu về thị giác của robot. Hình 3 cho thấy mẫu khuơn mặt với 16 cùng và 23 quan hệ. Các quan hệ này được dùng để phân loại, cĩ 11 quan hệ thiết yếu (các mũi tên màu đen) và 12 quan hệ xác thực (các mũi tên mầu xám). Mỗi mũi tên là một quan hệ. Một quan hệ của hai vùng thỏa mãn mẫu khuơn mặt khi tỷ lệ giữa hai vùng vượt qua một ngưỡng và một khuơn mặt được xác đinh khi cĩ 23 quan hệ thỏa mãn điều kiện trên. 15  Hình 3: Một mẫu khuơn mặt Mẫu khuơn mặt cĩ kích thước 14 x 16 pixel được sử dụng trong phương pháp định vị khuơn mặt của Sinha. Mẫu gồm 16 vùng trên khuơn mặt và 23 quan hệ ( các mũi tên). Một số phương pháp khác như của Froba và Zink lọc cạnh ở độ phân giải thấp rồi dùng biến đổi Hough để so khớp mẫu theo hướng cạnh để xác định hình dáng khuơn mặt ở dạng chụp hình thẳng ở dạng xám. Tỷ lệ chính xác trên 91%. Ngồi ra Shu và Jain cịn xây dựng ngữ nghĩa khuơn mặt. Ngữ nghĩa xây dựng theo hình dáng và vị trí các thành phần khuơn mặt. Hai ơng từ bộ ngữ nghĩa này tạo một đồ thị quan hệ để dễ dàng so khớp khi xác định khuơn mặt người … 1.3.3. Các mẫu biến dạng Yuille dùng các mẫu biến dạng để mơ hình hĩa các đặc trưng của khuơn mặt [3]. Trong hướng tiếp cận này, các đặc trưng khuơn mặt được mơ tả bằng các mẫu được tham số hĩa và cĩ một hàm năng lượng (giá trị) được để liên kết các cạnh, đỉnh, và thung lũng trong ảnh để tương ứng với các tham số trong mẫu. Mơ hình này tốt nhất khi tối thiểu hàm năng lượng qua các tham số, Mặc dù cĩ kết quả tốt nhưng phương pháp này cĩ một số hạn chế đĩ là các mẫu biến dạng phải được khởi tạo trong phạm vi gần với các đối tượng mà nĩ xác định. Rất nhiều hướng tiếp cận dựa trên dường gấp khúc (snake) và các mẫu để xác định khuơn mặt. Đầu tiên ảnh sẽ được làm xoắn lại bởi một lọc làm mờ rồi dùng phép tốn 16  morphology để làm nổi bật cạnh lên. Tiếp theo dùng một đường gấp khúc cĩ n điểm ảnh (giá trị n nhỏ) để tìm và ước lượng các đọan cong nhỏ. Mỗi khuơn mặt được xấp xỉ bằng một ellipse và biến đổi Hough, rồi tìm một ellipse nổi trội nhất. Các ứng viên sẽ cĩ bốn tham số mơ tả nột ellipse (để xác định khuơn mặt). Với mỗi ứng viên, một phương thức tương tự như phương thức mẫu biến dạng được dùng để xác định các đặc trưng ở mức chi tiết. Nếu tìm thấy số lượng đáng kể các đặc trưng khuơn mặt và thỏa mãn tỷ lệ cân đối thì xem như đã xác định được một khuơn mặt. Lam và Yan cũng dùng đường gấp khúc để xác định vị trí đầu với thuất tốn greedy để cực tiểu hĩa hàm năng lượng [11]. Thay vì dùng đường gấp khúc thì Huang và Su [6] dùng lý thuyết dịng chảy để xác định đường viền khuơn mặt dựa trên đặc tính hình học. Hai ơng dùng lý thuyết tập hợp đồng mức (Level Set) để loang từ các khởi động ban đầu để cĩ được các khuơn mặt người. Lanitis mơ tả một phương pháp biểu diễn khuơn mặt người với cả hai thơng tin: hình dáng và cường độ [12]. Bắt đầu bằng các tập ảnh được huấn luyện với các đường viền mẫu như là đường bao mắt, mũi, cằm/má đã được gán nhãn(phân loại). Ơng dùng một vector các điểm mẫu để mơ tả hình dáng. Sau đĩ dùng một mơ hình phân bố điểm (Point Distribution Model – PDM) để mơ tả vector hình dáng qua tồn bộ các cá thể. Dùng cách tiếp cận như của Kirby và Sirovich [14] để mơ tả cường độ bề ngồi của hình dáng đã được chuẩn hĩa. Để tìm kiếm và ước lượng vị trí khuơn mặt cũng như các tham số về hình dáng ơng sử dụng một mơ hình PDM cĩ hình dáng như khuơn mặt (xác định khuơn mặt bằng mơ hình hình dáng tích cực - Active Shape Model - ASM). Các mảnh của khuơn mặt được làm biến dạng về hình dáng trung bình rồi trích lấy các tham số cường độ. Sau đấy các tham số hình dáng và cường độ được dùng để phân loại và xác định khuơn mặt. 1.4. Hướng tiếp cận dựa trên diện mạo. 1.4.1. Tư tưởng của hướng tiếp cận dựa trên diện mạo Trái ngược với hướng tiếp cận dựa trên so sánh khớp mẫu (các mẫu đã được các nhà nghiên cứu định nghĩa trước), các mẫu trong hướng tiếp cận này được học từ một tập ảnh mẫu. Cĩ thể nĩi hướng tiếp cận dựa trên diện mạo áp dụng các kỹ thuật theo hướng xác suất thống kê và học máy để tìm những đặc tính liên quan của khuơn mặt và khơng phải là khuơn mặt. Các đặc tính đã được học ở trong hình thái các mơ hình phân bố hay các tham 17  số của một hàm số nên cĩ thể dùng các đặc tính này để xác định khuơn mặt người. Đồng thời, bài tốn giảm số chiều thường được quan tâm để tăng hiệu quả tính tốn cũng như hiệu quả xác định. Trong hướng tiếp cận này, phương pháp xác xuất tiếp tục được nhiều nhà nghiên cứu sử dụng. Một bức ảnh hoặc một vector (đặc trưng cho bức ảnh) được xem như một biến ngẫu nhiên. Biến ngẫu nhiên này sẽ được xác định là cĩ mơ tả các đặc tính của khuơn mặt hay khơng thơng qua các xác xuất cĩ điều kiện p(x/face) và p(x/nonface). Cĩ thể dùng bộ phân loại Bayesian để phân loại các ứng viên là khuơn mặt hay khơng phải khuơn mặt. Tuy nhiên, việc cài đặt bộ phân loại Bayesian với số chiều x lớn là một điều khá khĩ khăn, do đĩ cĩ rất nhiều nghiên cứu theo hướng tiếp cận này quan tâm tới việc tham số hĩa hay khơng tham số các xác xuất p(x/face) và p(x/nonface). Một các tiếp cận khác trong hướng tiếp cận dựa trên diện mạo là tìm một hàm biệt số ví dụ như các hàm mơ tả mặt phẳng hay siêu phẳng quyết định (các ranh giới) để phân biệt hai lớp khuơn mặt và khơng phải khuơn mặt. Thơng thường, một bức ảnh được chiếu vào khơng gian cĩ số chiều ít hơn rồi sau đĩ dùng một hàm biệt số (dựa trên các độ đo khoảng cách) để phân loại hoặc xây dựng một mặt quyết định phi tuyến bằng mạng neural đa tầng. Ngồi ra cĩ thể dùng SVM (Super Vector Machine) và các phương thức kernel chiếu các mẫu vào khơng gian cĩ số chiều cao hơn để dữ liệu bị rời rạc hồn tồn và từ đĩ cĩ thể sử dụng mặt phẳng phân loại để phân loại các mẫu là khuơn mặt hay khơng phải là khuơn mặt[5]. 1.4.2. Một số phương pháp cụ thể trong hướng tiếp cận dựa trên diện mạo Cĩ rất nhiều phương pháp học máy được sử dụng trong hướng tiếp cận dựa trên diện mạo. Trong phần này chỉ nêu ra một số phương pháp cùng những nghiên cứu liên quan đến phương pháp đấy. Riêng phương pháp adaboost sẽ được trình bầy trong phần sau của báo cáo. a. Adaboost Adaboost được đánh giá là phương phát tiếp cận nhanh nhất trong các thuật tốn học máy. Nĩ thường được kết hợp với các mơ hình cascade of classifiers để tăng tốc độ phát hiện khuơn mặt trong ảnh. Tư tưởng của thuật tốn adaboost đấy là kết hợp các bộ phân loại yếu thành một bộ phân loại mạnh. Trong quá trình xây dựng, bộ phân loại yếu tiếp 18  theo sẽ được xây dựng dựa trên các đánh giá về các bộ phân loại yếu trước, cuối cùng các bộ phân loại yếu sẽ được kết hợp để trở thành bộ phân loại mạnh. Viola và Jones dùng AdaBoost kết hợp cascade để xác định khuơn mặt người [17] với các đặc trưng dạng Haar-like. Tốc độ xử lý khá nhanh và tỷ lệ chính xác hơn 80%. Ngồi ra Schneiderman và Kanade dùng wavelet để trích đặc trưng, sau đấy cũng xây dựng hệ thống học với Adaboost, dựa trên xác suất để xác định khuơn mặt người. Tỷ lệ chính xác trên của phương pháp này lên đến 90%. b. Mạng Neural Về cơ bản mạng neural là một mạng các phần tử (gọi là neuron) kết nối với nhau thơng qua các liên kết (các liên kết này được gọi là trọng số liên kết) để thực hiện một cơng việc cụ thể nào đĩ. Khả năng xử lý của mạng neuron được hình thành thơng qua quá trình hiệu chỉnh trọng số liên kết giữa các neuron, nĩi cách khác là học từ tập hợp các mẫu huấn luyện. Mạng neural rất hay được sử dụng trong các bài tốn nhận dạng mẫu, nhận dạng mặt người cũng cĩ thể xem là một bài tốn nhận dạng với hai loại mẫu (mặt người hoặc khơng phải mặt người) và như vậy cĩ thể sử dụng mạng neural khá hiệu quả kể cả khi các mẫu khuơn mặt cĩ độ phức tạp cao. Tuy nhiên, một điều trở ngại đĩ là các kiến trúc mạng đều cĩ tính tổng quát cao, do đĩ, khi áp dụng ta phải tính tốn rõ số lượng tầng, số lượng node, tỷ lệ học … cho từng trường hợp cụ thể. c. Support Vector Machine Support Vector Machine (SVM) được Vladimir Vapnik đưa ra vào năm 1995 để giải quyết vấn đề nhận dạng mẫu hai lớp sử dụng nguyên tắc cực tiểu hĩa rủi ro cấu trúc (Structural Risk Minimization). Đây là phương pháp tiếp cận phân loại văn bản rất hiệu quả. Ưu điểm của SVM là giải thuật này được xây dựng trên ý tưởng cực tiểu rủi ro cấu trúc. Nguồn gốc của SVM dựa trên sự chắc chắn về lỗi chính xác, cĩ thể phân loại ngẫu nhiên các mẫu đối tượng được chọn mà lỗi được giữ sao cho nhỏ nhất. Vì vậy, giải thuật SVM giúp giảm thiểu biên trên các lỗi chính xác và làm cho hệ thống tin cậy hơn Cho trước một tập huấn luyện, các ảnh được biểu diễn dưới dạng vector. Trong khơng gian vector, mỗi vertor được biểu diễn bởi một điểm. Phương pháp SVM sẽ tim một siêu phẳng quyết định để phân chia khơng gian vector thành hai lớp (khuơn mặt và 19  khơng phải khuơn mặt). Chất lượng của siêu phẳng này phụ thuộc vào khoảng cách giữa các vector, tức là phụ thuộc vào các đặc trưng của ảnh. Support Vector Machine đã được Osuna [5] áp dụng đầu tiên (để xác định khuơn mặt người). SVM được xem như là một kiểu phân loại mới vì trong khi hầu hết các phương pháp phân loại khác (như Mạng Bayes, Nueral, RBF) đều dùng tiêu chí tối thiểu lỗi huấn luyện (rủi ro do kinh nghiệm), trong khi SVM dùng quy nạp (được gọi là tối thiểu rủi ro cấu trúc). Phân loại SVM là một phân loại tuyến tính, do đĩ nĩ cũng dùng một siêu phẳng để tách dữ liệu. Dựa trên một số kết hợp cĩ các trọng số của một tập con nhỏ các vector huấn luyện, các vector này được gọi là support vector. Ước lượng siêu phẳng trong SVM thì tương đương giải một bài tốn tuyến tính bậc hai. Osuna [5] đã phát triển phương pháp SVM một cách hiệu quả cho bài tốn xác định khuơn mặt người. Ơng dùng 10,000,000 mẫu cĩ kích thước 19x19 pixel, hệ thống của ơng cĩ tỷ lệ lỗi ít hơn và nhanh hơn rất nhiều. d. Mơ hình Markov ẩn Mơ hình Markov ẩn ( Hidden Markov Model – HMM ) là một mơ hình thống kê trong đĩ hệ thống được mơ hình hĩa được cho là một quá trình Markov với các tham số khơng biết trước và nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được, dựa trên sự thừa nhận này. Các tham số của mơ hình được rút ra sau đĩ cĩ thể sử dụng để thực hiện các phân tích kế tiếp, ví dụ cho các ứng dụng nhận dạng mẫu. Một giả thuyết quan trọng của mơ hình Markov ẩn là các mẫu cĩ thể được đặc tính hĩa như các tiến trình ngẫu nhiên cĩ tham số và các tham số này được ước lượng chính xác, đây là một trong những định nghĩa rõ ràng. Khi phát triển HMM để giải quyết bài tốn nhận dạng mẫu, phải xác định rõ cĩ bao nhiêu trạng thái ẩn đầu tiên cho hình thái mơ hình. Sau đĩ, huấn luyện HMM học xác suất chuyển tiếp giữa các trạng thái từ các mẫu, mà mỗi mẫu được mơ tả như một chuỗi các quan sát. Mục tiêu huấn luyện HMM là cực đại hĩa xác suất của quan sát từ dữ liệu huấn luyện bằng cách điều chỉnh các tham số trong mơ hình HMM thơng qua phương pháp phân đoạn Viterbi chuẩn và các thuật tốn Baum-Welch. Sau khi huấn luyện xong, dựa vào xác suất để xác định một quan sát thuơc lớp nào. Để hình dung về HMM, ta xét ví dụ cụ thể sau: Giả sử A cĩ một người bạn B sống ở rất xa. Hàng ngày thì B đều gọi điện cho A để kể về những việc mà B đã làm trong ngày. 20  B chỉ cĩ 3 việc mà anh ta thích làm đĩ là: việc thứ nhất là đi dạo, thứ hai là đi chợ và thứ ba là dọn phịng. Và việc anh ta làm việc gì trong ngày phụ thuộc rất lớn vào thời tiết của ngày hơm đấy. Như vậy, dù khơng nhận được thơng tin cụ thể về thời tiết trong ngày ở nơi người B ở, nhưng người A vẫn cĩ thể dựa vào việc B làm trong ngày để đốn về thời tiết hơm đấy. Như vậy nếu coi thời tiết chỉ cĩ hai trạng thái là nắng và mưa thì thời tiết là một chuỗi Markov cụ thể, và nĩ là ẩn đối với người A. Dữ liệu quan sát được ở đây là việc làm trong ngày của người B. Tồn bộ hệ thống này là một mơ hình Mackov ẩn. Một giả thuyết quan trọng của mơ hình Markov ẩn là các mẫu cĩ thể được xem như các tiến trình ngẫu nhiên cĩ tham số và các tham số này được ước lượng chính xác. Khi phát triển HMM để giải quyết bài tốn nhận dạng mẫu, phải xác định rõ cĩ bao nhiêu trạng thái ẩn đầu tiên cho hình thái mơ hình. Sau đĩ, huấn luyện HMM học xác suất chuyển tiếp giữa các trạng thái từ các mẫu, mà mỗi mẫu được mơ tả như một chuỗi các quan sát. Mục tiêu huấn luyện HMM là cực đại hĩa xác suất của quan sát từ dữ liệu huấn luyện bằng cách điều chỉnh các tham số trong mơ hình HMM thơng qua phương pháp phân đoạn Viterbi chuẩn và các thuật tốn Baum-Welch. Sau khi huấn luyện xong, dựa vào xác suất để xác định một quan sát thuơc lớp nào. Hình 4: các vector quan sát để huấn luyện cho HMM 21  Hình 5: Các trạng thái ẩn Đối với bài tốn phát hiện và nhận dạng mặt người, ta chia khuơn mặt thành các vùng khác nhau như đầu, mắt, mũi, miệng, và cằm. Cĩ thể nhận dạng một mẫu khuơn mặt người bằng cách thực hiện tiến trình xem xét các vùng quan sát theo một thứ tự thích hợp (từ trên xuống dưới, từ trái qua phải). Mục tiêu của hướng tiếp cận này là kết hợp các vùng đặc trưng khuơn mặt với các trạng thái của mơ hình. Hình 6: Xác định khuơn mặt bằng HMM Mỗi trạng thái lại cĩ những trạng thái nhỏ bên trong: trạng thái trán cĩ ba trạng thái nhỏ bên trong; trạng thái mắt cĩ năm trạng thái nhỏ bên trong. Thường các phương pháp dựa vào HMM sẽ xem xét một mẫu khuơn mặt như một chuỗi các vector quan sát, với mỗi vector là một dãy các điểm ảnh (hình 4 và hình 6). Trong quá trình huấn luyện và kiểm tra, một ảnh được quét theo một thứ tự và một quan sát được xem như một khối các điểm ảnh (hình 4 và hình 6). Sau đấy, áp dụng một định hướng theo xác suất để chuyển từ trạng thái này sang trạng thái khác ( hình 5 ), dữ liệu ảnh được mơ hình hĩa bằng phân bố Gauss đa biến. Một chuỗi quan sát bao gồm tất cả giá trị cường độ từ mỗi khối. Kết quả xuất ra cho biết quan sát thuộc lớp nào. 22  Một nghiên cứu điển hình trong các tiếp cận này đĩ là của Samaria. Samaria đã dùng năm trạng thái tương ứng năm vùng như trong hình 6 để mơ hình hĩa tiến trình xác định khuơn mặt người. Ơng huấn luyện từng vùng cho HMM. Mỗi trạng thái sẽ phụ trách xem xét một vùng tương ứng để đưa ra quyết định phù hợp. Nếu kết quả xem xét cuối cùng vượt qua một ngưỡng thì quan sát này sẽ là khuơn mặt người. d. Phân loại Bayes Bayes là một bộ phân loại tuyến tính dựa trên xác xuất. Tư tưởng của nĩ là dựa vào xác xuất của các đặc trưng xuất hiện trong khuơn mặt. Đây là phương pháp đơn giản, cài đặt khơng phức tạp, tốc độ nhanh, với tập huấn luyện lớn thì cho kết quả vẫn tương đối chính xác. Một nghiên cứu điển hình dùng phân loại Bayes vào xác định mặt người trong hướng tiếp cận dựa trên diện mạo đĩ là nghiên cứu của Schneiderman và Kanade. Hai ơng đã mơ tả một phân loại Nạve Bayes để ước lượng xác xuất chung của diện mạo cục bộ và vị trí của các mẫu (các vùng trên khuơn mặt) ở nhiều độ phân giải khác nhau. Ứng với mỗi độ phân giải, khuơn mặt người được chia thành bốn vùng chữ nhật, các vùng này được chiếu xuống khơng gian cĩ số chiều bé hơn và được lượng tử hĩa thành tập các mẫu cĩ giới hạn. Sau đấy thống kê các vùng đã được chiếu để mã hĩa diện mạo cục bộ. Nếu xác xuất lớn hơn xác xuất đạt được lớn hơn xác xuất tiền nghiện thì kết luận cĩ khuơn mặt người. Hướng tiếp cận này cịn cho phép xác định các khuơn mặt bị xoay hoặc gĩc nhìn nghiêng. 23  Chương 3 CƠ SỞ LÝ THUYẾT 1. Tổng quan về Adaboost Học theo adaboost là một cách trong hướng tiếp cận dựa trên diện mạo, Viola và Jones dùng AdaBoost kết hợp cascade để xác định khuơn mặt người [17] với các đặc trưng dạng Haar wavelet-like. Tốc độ xử lý khá nhanh và tỷ lệ chính xác hơn 80% trên ảnh xám. Thuật tốn học máy Adaboost được phát triển thuật tốn boosting, do đĩ tơi sẽ trình bầy một chút về thuật tốn boosting trước khi trình bầy về adaboost. 1.1. Tiếp cận Boosting Về lịch sử, boosting bắt nguồn từ câu hỏi nổi tiếng được đưa ra bời Kearns vào năm 1989 : “Liệu cĩ thể tạo ra một strong classifier từ một tập các bộ phân loại yếu?”. Năm 1990, Robert Schapire đưa ra thuật tốn boosting đầu tiên, tiếp đến năm 1993 thì nĩ được Drucker, Schapire và Simard kiểm nghiệm trong trong các chương trình nhận dạng ( OCR application ). Freund đã tiếp tục các nghiên cứu của Schaprire, và đến năm 1995 thì ơng cùng với Schapire phát triển boosting thành adaboost. Như vậy, nguyên lý cơ bản của boosting là sự kết hợp các weak classifiers thành một strong classifier. Trong đĩ, weak classifier là các bộ phân loại đơn giản chỉ cần cĩ độ chính xác trên 50%. Bằng cách này, chúng ta nĩi bộ phân loại đã được “boost”. Để hiểu cách hoạt động của thuật tốn boosting, ta xét một bài tốn phân loại 2 lớp (mẫu cần nhận dạng chỉ thuộc một trong hai lớp) với D là tập huấn luyện gồm cĩ n mẫu. Trước tiên, chúng ta sẽ chọn ngẫu nhiên ra n1 mẫu từ tập D (n1<n) để tạo tập D1. Sau đĩ, chúng ta sẽ xây dựng weak classifier đầu tiên C1 từ tập D1. Tiếp theo, chúng ta xây dựng tập D2 để huấn luyện bộ phân loại C2. D2 sẽ được xây dựng sao cho một nửa số mẫu của nĩ được phân loại đúng bởi C1 và nửa cịn lại bị phân loại sai bởi C1. Bằng cách này, D2 chứa đựng những thơng tin bổ sung cho C1. Bây giờ chúng ta sẽ xây huấn luyện C2 từ D2. 24  Tiếp theo, chúng ta sẽ xây dựng tập D3 từ những mẫu khơng được phân loại tốt bởi sự kết hợp giữa C1 và C2: những mẫu cịn lại trong D mà C1 và C2 cho kết quả khác nhau. Như vậy, D3 sẽ gồm những mẫu mà C1 và C2 hoạt động khơng hiệu quả. Sau cùng, chúng ta sẽ huấn luyện bộ phân loại C3 từ D3. Bây giờ chúng ta đã cĩ một strong classifier: sự kết hợp C1, C2 và C3. Khi tiến hành nhận dạng một mẫu X, kết quả sẽ được quyết định bởi sự thỏa thuận của 3 bộ C1, C2 và C3: Nếu cả C1 và C2 đều phân X vào cùng một lớp thì lớp này chính là kết quả phân loại của X; ngược lại, nếu C1 và C2 phân X vào 2 lớp khác nhau, C3 sẽ quyết định X thuộc về lớp nào Hình 7: Boosting 1.2. Adaboost Như đã biết, AdaBoost (Adaptive Boost) là một bộ phân loại mạnh phi tuyến phức dựa trên hướng tiếp cận boosting được Freund và Schapire đưa ra vào năm 1995. Adaboost hoạt động trên nguyên tắc kết hợp tuyến tính các weak classifier dựa trên các đặc trưng Haar- Line để hình thành một strong classifier. 25  Để cĩ thể kết hợp các bộ phân loại yếu, adaboost sử dụng một trọng số (weight) để đánh dấu các mẫu khĩ nhận dạng. Trong quá trình huấn luyện, cứ mỗi weak classifier được xây dựng, thuật tốn sẽ tiến hành cập nhật lại trọng số để chuẩn bị cho việc xây dựng weak classifier tiếp theo: tăng trọng số của các mẫu bị nhận dạng sai và giảm trọng số của các mẫu được nhận dạng đúng bởi weak classifier vừa xây dựng. Bằng cách này, các weak classifier sau cĩ thể tập trung vào các mẫu mà các weak classifier trước đĩ chưa thực hiện tốt. Sau cùng các weak classifier sẽ được kết hợp tùy theo mức độ ‘tốt’ của chúng để tạo nên một strong classifier. Các weak classifiers hk(x) là các bộ phân loại yếu, được biểu diễn như sau: Trong đĩ: x : mẫu hay cửa sổ con cần xét (x = (x1,x2,…,xn) là vector đặc trưng của mẫu) k: ngưỡng fk: giá trị của đặc trưng Haar-like pk: hệ số quyết định chiều của bất phương trình Cơng thức trên cĩ thể diễn giải như sau: Nếu giá trị đặc trưng của mẫu cho bởi hàm đánh giá của bộ phân loại vượt qua một ngưỡng cho trước thì mẫu đấy là khuơn mặt ( gọi là object : đối tượng cần nhận dạng ), ngược lại thì mẫu là background ( khơng phải là đối tượng ). Thuật tốn AdaBoost: 26  Sơ đồ khối: 1. Cho một tập gồm n mẫu cĩ đánh dấu (x1,y1), (x2,y2),… (xn,yn) với xk = (xk1, xk2, … , xkm) là vector đặc trưng và yk {-1, 1} là nhãn của mẫu (1 ứng với object, -1 ứng với background). 2. Khởi tạo trọng số ban đầu cho tất cả các mẫu: với m là số mẫu đúng (ứng với object và y = 1) và l là số mẫu sai (ứng với background và y = -1). 3. Xây dựng T weak classifiers Lặp t = 1, …, T • Với mỗi đặc trưng trong vector đặc trưng, xây dựng một weak classifier hj với ngưỡng θj và lỗi εj. • Chọn ra hj với εj nhỏ nhất, ta được ht: • Cập nhật lại trọng số: • Trong đĩ: : Hệ số dùng để đưa về đoạn [0,1] (normalization factor) 4. Strong classifier được xây dựng : 27  Quá trình huấn luyện bộ phân loại được thực hiện bằng một vịng lặp mà ở mỗi bước lặp, thuật tốn sẽ chọn ra weak classifier ht thực hiện việc phân loại với lỗi εt nhỏ nhất (do đĩ sẽ là bộ phân loại tốt nhất) để bổ sung vào strong classifier. Mỗi khi chọn được 1 bộ phân loại ht, Adaboost sẽ tính giá trị αt theo cơng thức ở trên. αt cũng được chọn trên nguyên tắc làm giảm thiểu giá trị lỗi εt. Hệ số αt nĩi lên mức độ quan trọng của ht: • Trong cơng thức của bộ phân loại H(x): Ta thấy tất cả các bộ phân loại ht đều cĩ đĩng gĩp vào kết quả của bộ phân loại H(x), và mức độ đĩng gĩp của chúng phụ thuộc vào giá trị αt tương ứng: ht với αt càng lớn thì nĩ càng cĩ vài trị quan trọng trong H(x). • Trong cơng thức tính αt: Bắt đầu huấn luyện Khởi tạo tập đặc trưng ban đầu Xác định các đặc trưng trong từng mẫu, xây dựng các bộ phân loại yếu tương ứng Đặc trưng haar-like Tính tốn giá trị lỗi cho mỗi đặc trưng (false alarm) Xác định ngưỡng Chọn weak classifier cĩ giá trị lỗi bé nhất Lưu weak classifier được chọn False alarm ≤ max false alarm Tập các mẫu và trọng số Tập các mẫu Mẫu sai Mẫu đúng Cập nhật lại trọng số Sai Kết thúc, strong classifier đuợc xây dựng Đúng 28  Dễ thấy giá trị αt tỉ lệ nghịch với εt. Bởi vì ht được chọn với tiêu chí đạt εt nhỏ nhất, do đĩ nĩ sẽ đảm bảo giá trị αt lớn nhất. Sau khi tính được giá trị αt, Adaboost tiến hành cập nhật lại trọng số của các mẫu: tăng trọng số các mẫu mà ht phân loại sai, giảm trọng số các mẫu mà ht phân loại đúng. Bằng cách này, trọng số của mẫu phản ánh được mức độ khĩ nhận dạng của mẫu đĩ và ht- +1 sẽ ưu tiên học cách phân loại những mẫu này. Vịng lặp xây dựng strong classifier sẽ dừng lại sau T lần lặp. Trong thực tế cài đặt (thư viện OpenCV của Intel), người ta ít sử dụng giá trị T vì khơng cĩ cơng thức nào đảm bảo tính được giá trị T tối ưu cho quá trình huấn luyện. Thay vào đĩ, người ta sử dụng giá trị max false positive hay max false alarm (tỉ lệ nhận dạng sai tối đa các mẫu background). Tỉ lệ này của bộ phân loại cần xây dựng khơng được phép vượt quá giá trị này. Khi đĩ, qua các lần lặp, false alarm của strong classifier Ht(x) xây dựng được (tại lần lặp thứ t) sẽ giảm dần, và vịng lặp kết thúc khi tỉ lệ này thấp hơn max false alarm. 1.3. Các đặc trưng Haar-Like Viola và Jones dùng 4 đặc trưng cơ bản [20] để xác định khuơn mặt người. Mỗi đặc trưng Haar–like là sự kết hợp của hai hay ba hình chữ nhật "trắng" hay "đen" như trong hình sau: Hình 8 : 4 đặt trưng Haar-like cơ bản Để áp dụng các đặt trưng này vào việc bài tố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 (edge features): 2. Đặc trưng đường (line features): 29  3. Đặc trưng xung quanh tâm (center-surround features): Hình 9: Các đặc trưng mở rộng của các đặc trưng Haar-like cơ sở Lợi ích của các đặ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. Để tính giá trị các đặc trưng haar-like, ta tính sự chênh lệch giữa tổng của các pixel của các vùng đen và các vùng trắng như trong cơng thức sau: f(x) = Tổngvùng đen(pixel) - Tổngvùng trắng(pixel) Như vậy ta cĩ thể thấy rằng, để tính các giá trị của đặc trưng Haar-like, ta phải tính tổng của các vùng pixel trên ảnh. Nhưng để tính tốn các giá trị của các đặc trưng Haar- like cho tất cả các vị trí trên ảnh địi hỏi chi phí tính tốn khá lớn, khơng đáp ứng được cho các ứng dụng địi hỏi tính run-time. Do đĩ Viola và Jones đưa ra một khái niệm gọi là Integral Image để tính tốn nhanh cho các đặc trưng cơ bản. Sau này, Lienhart kế thừa Integral Image (SAT) và đưa thêm khái niệm Rotated Summed Area Table (RSAT) dùng để tính tốn nhanh cho các đặc trưng xoay 1 gĩc 45o. Integral Image là một mảng 2 chiều với kích thước bằng với kích của ảnh cần tính các đặc trưng Haar-like, với mỗi phần tử của mảng này được tính bằng cách tính tổng của điểm ảnh phía trên (dịng-1) và bên trái (cột-1) của nĩ. Bắt đầu từ vị trí trên, bên trái đến vị trí dưới, phải của ảnh, việc tính tốn này đơn thuần chỉ đựa trên phép cộng số nguyên đơn giản, do đĩ tốc độ thực hiện rất nhanh. P(x,y) 30  Hình 10: Cách tính Integral Image của ảnh Sau khi đã tính được Integral Image, việc tính tổng điểm ảnh của một vùng bất kỳ nào đĩ trên ảnh thực hiện rất đơn giản theo cách sau: (Giả sử ta cần tính tổng điểm ảnh của vùng D như trong hình 11): D = A + B + C + D – (A+B) – (A+C) + A Với A + B + C + D chính là giá trị tại điểm P4 trên Integral Image, tương tự như vậy A+B là giá trị tại điểm P2, A+C là giá trị tại điểm P3, và A là giá trị tại điểm P1. Vậy ta cĩ thể viết lại biểu thức tính D ở trên như sau: Hình 11:Ví dụ cách tính nhanh tổng các điểm ảnh của vùng D trên ảnh Hình 12: Ví dụ cách tính nhanh tổng điểm ảnh của vùng D trên ảnh với các đặc trưng xoay 45o Với các đặc trưng Haar-like xoay 45o Integral Image tại một điểm (x, y) được tính theo cơng thức: RSAT(x,y) B A C 2 4 1 3 D (a) (b) A C B D P1  P2  P3  P4  31  Tổng pixel của một vùng bất kỳ trên ảnh vẫn được tính theo cách sau: D = A + B + C + D – (A+B) – (A+C) + A Như vậy tổng các điểm ảnh trong một hình chữ nhật (kể cả trường hợp xoay 45º) bất kì đều cĩ thể được tính nhanh dựa trên integral image tại 4 đỉnh của nĩ : Sum (D ) = .4 - 2 – 3 + 1 1.4. Cascade of Classifiers Ta thấy quá trình huấn luyện, bộ phân loại phải duyệt qua tất cả các đặc trưng của các mẫu trong tập training. Việc này tốn rất nhiều thời gian. Tuy nhiên, trong các mẫu đưa vào, khơng phải mẫu nào cũng thuộc loại khĩ nhận dạng, cĩ những mẫu background rất dễ nhận ra (ta gọi đây là những mẫu background đơn giản). Đối với những mẫu này, ta chỉ cần xét một hay vài đặc trưng đơn giản là cĩ thể nhận diện được chứ khơng cần xét tất cả các đặc trưng. Nhưng đối với các bộ phân loại thơng thường thì cho dù mẫu cần nhận dạng là dễ hay khĩ thì nĩ vẫn sẽ xét tất cả các đặc trưng mà nĩ rút ra được trong quá trình học. Do đĩ, chúng tốn thời gian xử lý một cách khơng cần thiết. Cascade of Classifiers được xây dựng chính là nhằm rút ngắn thời gian xử lý, giảm thiểu false alarm cho bộ phân loại. Cascade tree gồm nhiều stage (hay cịn gọi là layer), mỗi stage của cây sẽ là một stage classifier. Một mẫu để được phân loại là đối tượng thì nĩ cần phải đi qua hết tất cả các stages của cây. Các stage classifiers ở stage sau được huấn luyện bằng những mẫu negative mà stage classifier trước nĩ nhận dạng sai, tức là nĩ sẽ tập trung học từ các mẫu background khĩ hơn, do đĩ sự kết hợp các stage classifiers này lại sẽ giúp bộ phân loại cĩ false alarm thấp. Với cấu trúc này, những mẫu background dễ nhận diện sẽ bị loại ngay từ những stages đầu tiên, giúp đáp ứng tốt nhất đối với độ phức tạp gia tăng của các mẫu đưa vào, đồng thời giúp rút ngắn thời gian xử lý. Thuật tốn Cascade training: 32  Minh họa thuật tốn Cascade training: Hình 13: cascade of classifiers Hình 13 minh họa sự huấn luyện của một cascade gồm N stages. Ở mỗi stage, weak classifier tương ứng sẽ được huấn luyện sao cho độ chính xác của nĩ là h và false alarm bằng f.      h h h 1-f 1-f 1-f 1-f stage 1 2 N-1 N…… hitrate = hN falsealarms = fN Input pattern classified as a non-object 1. Gọi: F là giá trị false alarm và d là độ chính xác của weak classifier ở mỗi stage Ftarget: Giá trị max false alarm. P, N là số lượng mẫu positive và negative. Pi, Ni là tập positive và negative cho bộ phân lớp ở tầng thứ i. Fi, Di: Giá trị false alarm và độ chính xác của cascade trước khi đến tầng thứ i. 2. Khởi tạo i=0; F0=1.0; D0 = 1.0 3. Lặp: while Fi>Ftarget • i = i+1; • Huấn luyện bộ phân loại hi từ tập Pi và Ni với detection rate d và max false alarm f. Thêm hi vào cây phân lớp. • Dùng cây phân lớp hiện cĩ để tính Fi: Duyệt qua N mẫu negative cho đến khi nào tìm đủ n mẫu mà cây phân lớp hiện cĩ phân loại sai. ( • N := • Nếu Fi >Ftarget N = { số mẫu sai ở stage hiện tại phân loại sai }. P = { số mẫu positive mà stage hiện tại phân loại dúng } 33  1.5. Cascade of boosting classifiers Cascade of boosting classifiers là mơ hình cascade of classifiers với mỗi classifier được xây dựng bằng Adaboost sử dụng haar-like. Hình 14: Cascade of boosting classifiers Viola và Jones đã sử dụng rất thành cơng cascade of boosting classifiers cho bài tốn nhận dạng mặt người. Với tập huấn luyện gồm 4196 hình mặt người được đưa về ảnh grayscale kích thước 24x24 và 9500 hình background, hai ơngđã xây dựng cấu trúc cascade tree gồm 38 stage với tổng cộng 6060 đặc trưng haar-like. Thực nghiệm đã cho thấy classifier ở stage đầu tiên sử dụng 2 đặc trưng và loại được khoảng 50% mẫu background (khơng phải mặt người) và cĩ độ chính xác là d = 100%. Classifier ở stage thứ 2 sử dụng 10 đặc trưng loại được 80% mẫu background với độ chính xác vẫn là 100%. Hệ thống này được so sánh với hệ thống của Rowley-Baluja-Kanade (sử dụng mạng neural), Schneiderman-Kanade (sử dụng phương pháp thống kê), và cho thấy tỉ lệ nhận dạng là ngang nhau, trong khi hệ thống của Viola và Jones chạy nhanh hơn đến 15 lần so với hệ thống của Rowley-Baluja-Kanade và nhanh hơn 600 lần hệ thống của Schneiderman-Kanade. Lý do mà cấu trúc cascade đạt tốc độ nhận dạng nhanh chính là nhờ nĩ sớm loại bỏ được các mẫu background đơn giản (thường cĩ số lượng lớn hơn nhiều so với các mẫu chứa object – các mẫu chưa khuơn mặt cần tiến hành nhận dạng). Bên cạnh đĩ, hệ thống của Viola và Jones cũng đạt được độ chính xác khá cao nhờ vào thuật tốn cascade training, các bộ nhận dạng được huấn luyện bằng AdaBoost với đặc trưng Haar-like mơ tả tốt thơng tin đối tượng, cùng với cách Integral Image tính nhanh các đặc trưng, khơng làm giảm tốc độ nhận dạng của hệ thống. Như vậy, mơ hình Cascade of Boosted Classifiers thật sự là một cách tiếp cận tốt cả về tốc độ lẫn khả năng nhận dạng, rất phù hợp với bài nhận dạng mặt người. I Y Y Y N N N N C L A S S NON-CLASS 34  Chương 4 XÂY DỰNG ỨNG DỤNG Phát hiện mặt người trong ảnh cĩ nhiều ứng dụng trong cuộc sống, tuy nhiên, trong khĩa luận này, tơi chỉ xây dựng một chương trình nhỏ để minh họa cho các lý thuyết ở trên. Cụ thể đấy là một chương trình phát hiện mặt người trong ảnh được viết trên nền visual c ++ của Microsoft, sử dụng thư viện mã nguồn mở OpenCV của Intel. 1. Sơ lược về OpenCV Open VC là thư viện mã nguồn mở của intel về thị giác máy tính. Nĩ cung cấp một bộ mã nguồn bao gồm hàng trăm hàm, lớp dựa trên các thuật tốn về xử lý ảnh cũng như Computer vision dùng ngơn ngữ C/C++. Open CV thể hiện sự đa dạng của trí tuệ nhân tạo. Được ứng dụng nhiều trong các bài tốn nhận dạng mặt, dị tìm mặt, phát hiện mặt, lọc Kalman, … Cấu trúc tổng quan của OpenCV bao gồm 5 phần chính. 4 trong 5 phần đĩ được chỉ ra trong hình vẽ dưới. Hình 15: Cấu trúc cơ bản của OpenCV Phần CV bao gồm các thư viện cơ bản về xử lý ảnh và các giải thuật về thị giác máy tính. ML là bộ thư viện về các thuật tốn học máy, bao gồm rất nhiều bộ phân cụm và phân loại thống kê. HighGUI chứa đựng những thủ tục vào ra, các chức năng về lưu trữ cũng như đọc các file ảnh và video. Phần thứ 4, Cxcore chứa đựng các cấu trúc dữ liệu cơ CV Các hàm về xử lý ảnh và giải thuật về thị giác máy tính CXCORE Các cấu trúc dữ liệu cơ bản, cấu trúc XML, các hàm về đồ họa … MLL Các thuật tốn học máy, bao gồm các bộ phân cụm, phân loại thống kê HighGUI Các hàm và thủ tục làm việc với file ảnh và file video 35  bản ( ví dụ như cấu trúc XML, các cây dữ liệu …). Phần cuối cùng là CvAux, phần này bao gồm các thư viện cho việc phát hiện, theo dõi và nhận dạng đối tượng (khuơn mặt, mắt …). 2. Tổng quan về một hệ thống phát hiện mặt người trong ảnh Hình 16: Tổng quan về hệ thống phát hiện mặt người trong ảnh Về cơ bản, từ ảnh gốc ban đầu, hệ thống sẽ chia ảnh thành vơ số vùng nhỏ để tính các đặc trưng, sau đấy đưa các đặc trưng. Tiếp theo, chương trình sẽ xác định các vùng khả quan (các ứng viên) cĩ thể là khuơn mặt, cuối cùng các ứng viên này sẽ được đưa vào một bộ phân loại để tiến hành xác định ứng viên nào là mặt người. 3. Phân tích – thiết kế hệ thống phát hiện mặt người 3.1. Phân tích Nhiệm vụ chính của chương trình là dị tìm khuơn mặt từ một bức ảnh, một file video hoặc từ webcam, sau đấy lưu khuơn mặt vào csdl để phục vụ cho các mục đích khác (sẽ được phát triển sau). Ảnh gốc Tính các đặc trưng nhanh từ nhiều tỉ lệ Integral Image Các hàm Haar cơ bản Ước lượng các đặc trưng Điều chỉnh thơng số Adaboost Chọn đặc trưng Số lượng lớn các đặc trưng Cấu trúc phân tầng (Cascade of classifier) Một tập nhỏ các đặc trưng Quyết định kết quả  C1  C2 Cn I Y Y N N N C L A S S NON-CLASS 36  Hình 17: Biểu đồ ngữ cảnh của hệ thống Như vậy các chức năng chương trình bao gồm: • Kết nối đến webcam, đọc các file ảnh và video. • Phát hiện các nhiều khuơn mặt cĩ trong bức ảnh, video, webcam ... • Lưu ảnh khuơn mặt được phát hiện vào csdl. 3.2. Thiết kế hệ thống Với các chức năng ở trên, chương trình được chia thành thành 3 phần chính: Phần xử lý đầu vào, phần phát hiện khuơn mặt và phần xử lý đầu ra. a. Xử lý đầu vào: Đầu vào (ảnh, video hoặc webcam) Phát hiện nhanh khuơn mặt bằng Adaboost Lưu khuơn mặt vào CSDL Cĩ khuơn mặt 0 HỆ THỐNG PHÁT HIỆN MẶT NGƯỜI TRONG ẢNH NGƯỜI DÙNG Capture ảnh Khuơn mặt đã được phát hiện 37  Chương trình nhận đầu vào là file ảnh, video hoặc webcam, tuy nhiên, việc phát hiện khuơn mặt được thực hiện trên các bức ảnh, do đĩ, với đầu vào là webcam hay file video, ta phải chuyển thành các ảnh tĩnh và xử lý trên từng ảnh tĩnh. Sau khi đã cĩ ảnh đầu vào rồi thì sẽ chuyển ảnh cho giai đoạn xử lý tiếp theo, đĩ là phát hiện các khuơn mặt cĩ trong ảnh. b. Phát hiện khuơn mặt Phần này xử lý chính nghiệp vụ của hệ thống. Sau khi cĩ ảnh truyền vào, hệ thống sẽ thực hiện chức năng phát hiện khuơn mặt cĩ trong ảnh. Việc phát hiện khuơn mặt được thực hiện nhanh bằng thuật tốn adaboost thơng qua hàm cvHaarDetectObjects() của OpenCV. Hàm này thực hiện việc phát hiện đối tượng dựa trên các đặc trưng haar-like, cụ thể là nhờ vào một bộ Cascade được truyền vào cho hàm. Bộ Cascade được xây dựng theo dạng cây (tree-node) và đã được huấn luyện từ trước. Việc huấn luyện bộ Cascade cĩ thể thực hiện từ những dữ liệu thu thập được để phục vụ cho quá trình nhận dạng. Ví dụ, muốn nhận dạng một người A, ta thu thập các ảnh khuơn mặt của người A với nhiều tư thế, gĩc chụp và điều kiện chụp khác nhau, sau đấy cho bộ nhận dạng học theo thuật tốn Cascade training. Tuy nhiên việc nhận dạng khuơn mặt là một cơng việc khĩ và tốn nhiều thời gian, do đĩ, tơi khơng thực hiện nĩ trong khĩa luận của mình. c. Xử lý đầu ra. Khuơn mặt sau khi được phát hiện sẽ được tách ra khỏi bức ảnh và lưu dưới dạng ảnh bitmap với phần mở rộng là *.jpg. Đối với đầu vào là các file ảnh, dữ liệu đầu ra cũng là file ảnh đấy nhưng cĩ lưu vị trí khuơn mặt đã được phát hiện trên bức ảnh, đồng thời tách các riêng khuơn mặt và lưu vào cơ sở dữ liệu. Đối với đầu vào là các file video hoặc webcam. Các khuơn mặt sẽ được tách ra và lưu lại thành các file ảnh riêng rẽ, và được đánh số thứ tự theo tên file video. Ví dụ như file video test.avi thì ảnh các khuơn mặt phát hiện được sẽ được đánh số theo thứ tự như sau: test.avi_1.jpg, test.avi_2.jpg … 38  Hình 18: Biểu đồ phân rã chức năng. 3.3. Thiết kế cơ sở dữ liệu Lưu trữ cơ sở dữ liệu là một phần quan trọng của ứng dụng. Việc xây dựng, tổ chức cơ sở dữ liệu ảnh hướng lớn đến tốc độ của chương trình. Do đĩ tơi đã xây dựng và quản cơ sở dữ liệu bằng hệ quản trị cơ sở Oracle, đây là hệ quản trị cơ sở dữ liệu mạnh, đáp ứng được nhiều yêu cầu về quản lý cơ sở dữ liệu của các doanh nghiệp lớn, đặc biệt là các ngân hàng hay kho bạc. Tuy hiện tại, chương trình chỉ dừng lại ở mức phát hiện khuơn mặt trong ảnh, nhưng việc xây dựng một cơ sở dữ liệu tốt sẽ là tiền đề để cĩ thể phát triển chương trình thành các ứng dụng lớn hơn sau này. Hệ thống cần lưu trữ các dữ liệu: Ảnh khuơn mặt sau khi đã được phát hiện. Đối với đầu vào là file ảnh: • Lưu ảnh đầu vào cùng vị trí khuơn mặt đã được phát hiện trên bức ảnh • Lưu từng khuơn mặt được phát hiện. Đối với đầu vào là file video, hoặc webcam: • Lưu các khuơn mặt được phát hiện Như vậy các thơng tin trong cơ sở dữ liệu bao gồm 2 thực thể sau: • ẢNH GỐC ( IMAGES ): Ảnh đầu vào. Các thuộc tính bao gồm: - ID: Mã ảnh, kiểu Integer, là khĩa chính và cĩ ràng buộc là tự tăng. 3.2.Lưu ảnh vào CSDL 2.Phát hiện nhanh khuơn mặt bằng Adaboost 1.Xử lý đầu vào 1.1. Capture ảnh 3. Xử lý đầu ra HỆ THỐNG PHÁT HIỆN MẶT NGƯỜI TRONG ẢNH 3.1. Lưu ảnh vào thư mục thích hợp trên máy 39  - Name: Tên của bức ảnh, kiểu dữ liệu varchar2(200). Trong trường hợp đầu vào là video thì tên sẽ được lấy theo tên của file video, cịn nếu đầu vào là webcam thì sẽ đặt là webcam_ID (thêm ID ở trên vào tên). - Image: Lưu mã nhị phân của bức ảnh. - URL: lưu đường dẫn đến bức ảnh, kiểu giữ liệu varchar2(1000) Lưu ý: Trong trường hợp file đầu vào là video hoặc webcam thì các trường Image, và URL sẽ nhận giá trị null. • KHUƠN MẶT ( FACES ): Các khuơn mặt phát hiện được. Các thuộc tính bao gồm: - ID: Mã ảnh, kiểu Integer, là khĩa chính và cĩ ràng buộc là tự tăng. - IMAGE_ID: ID của ảnh gốc, kiểu dữ liệu Interger, là khĩa ngoại tham chiếu đến bảng ẢNH GỐC. - Name: Tên của khuơn mặt, được đặt theo tên ảnh gốc, đồng thời thêm số thứ tự để nhận biết các khuơn mặt của cùng ảnh gốc. - Image: Lưu mã nhị phân của ảnh khuơn mặt. - URL: lưu đường dẫn đến ảnh khuơn mặt, kiểu giữ liệu varchar2(1000). Hình 19: Sơ đồ thực thể quan hệ ( ERM ). 3.4. Thiết kế giao diện Giao diện của chương trình được thiết kế thân thiện và đơn giản. Tập trung vào chức năng chính phát hiện khuơn mặt trong ảnh. Bố cục trên giao diện được chia thành 4 phần. IMAGES ID Name Image ỦRL FACES ID Name Image ỦRL Image_ID 40  Phần 1, dành cho người dùng chọn đầu vào, cĩ thể là ảnh, video hoặc webcam. Các ảnh hoặc video cĩ thể được lưu tùy ý trong các thư mục trên máy tính của người dùng. Phần thứ hai là danh sách các khuơn mặt đã được phát hiện và được lưu trong cơ sở dữ liệu. Phần thứ 3 là danh sách các Cascade. Cuối cùng là phần xử lý và hiện kết quả (số khuơn mặt phát hiện được, thời gian thực hiện). Người dùng chọn bức ảnh, chọn bộ Cascade, sau đấy nhấn vào nút “Detect” để thực hiện việc xác định khuơn mặt trên ảnh. Giao diện của chương trình được thể hiện như hình dưới. Hình 20: Giao diện của chương trình 41  KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. Kết luận Trên cơ sở nghiên cứu về bài tốn phát hiện mặt người trong ảnh. Đặc biệt là thuật tốn Adaboost, các đặc trưng haar-like và mơ hình Cascade of Classifier. Tơi đã áp dụng thành cơng mơ hình Cascade of Classfier vào bài tốn phát hiện mặt người trong ảnh. Tuy kết quả đạt được chưa cao, nhưng đây là bước đầu để phát triển bài tốn nhận dạng mặt (face recognition) người sau này. Bên cạnh đĩ, trong quá trình xây dựng chương trình demo, tơi đã tìm hiểu về thư viện mã nguồn mở OpenCV, hệ quản trị cơ sở dữ liệu Oracle, qua đĩ biết cách sử dụng các hàm trong thư viện OpenCV và quản lý cơ sở dữ liệu bằng hệ quản trị cơ sở dữ liệu Oracle. Về chương trình demo, sau khi thử nghiệm với tập ảnh lớn và webcam. Chương trình đạt kết quả tốt, thời gian phát hiện nhanh đối với các ảnh mặt người chụp thẳng, chất lượng ảnh tốt (chụp bằng máy kĩ thuật số), tuy nhiên đối với các ảnh chụp nghiêng hay ảnh cĩ mầu sắc quá tối thì chương trình gần như khơng thể phát hiện được khuơn mặt trong bức ảnh đấy. Đối với webcam, thì hiệu xuất của chương trình cịn tùy theo chất lượng của loại webcam được sử dụng, tuy nhiên cũng tương tự như với phát hiện khuơn mặt trong ảnh, chương trình sẽ khơng thể phát hiện mặt người trong điều kiện độ sáng quá yếu và gĩc quay nghiêng quá 20o. 2. Hướng phát triển Cĩ nhiều hướng phát triển cho chương trình này, cĩ thể phát triển cả về mặt ứng dụng và mặt thuật tốn (để cải thiện hiệu quả phát hiện mặt người). Cĩ thể xây dựng một ứng dụng chỉ cần đến phát hiện mặt người mà khơng cần nhận dạng. Ví dụ như một hệ thống ghép hình, ghép khuơn mặt phát hiện được vào trong một bức ảnh khác (chẳng hạn như ghép khuơn mặt của người sử dụng cho khuơn mặt của người nổi tiếng). Ngồi ra cĩ thể phát triển chương trình theo hướng nhận dạng khuơn mặt, xây dựng một hệ thống để học các đặc trưng của những người cần nhận dạng. Khi thực hiện, đầu tiên ta đưa qua bức ảnh qua chương trình phát hiện mặt người để phát hiện nhanh các khuơn mặt cĩ trong ảnh, sau đấy so sách các khuơn mặt đĩ với các khuơn mặt mà chương 42  trình đã được “học” từ trước, so sánh các đặc trưng của hai khuơn mặt, nếu trùng thì đưa ra thơng tin về khuơn mặt được nhận dạng.  b  Tài liệu tham khảo. [1] A. Lanitis, C.J. Taylor, and T.F. Cootes, “An Automatic Face Identification System Using lexible Appearance Models”, Image and Vision Computing, vol. 13, no. 5, pp. 393-401, 1995. [2] Andrew King, “A Survey of Methods for Face Detection”, 2003 [3] A. Yuille, P. Hallinan, and D. Cohen, “Feature Extraction from Faces Using eformable Templates”, Int’l J. Computer Vision, vol. 8, no. 2, pp. 99-111, 1992. [4] D.G. Kendall, “Shape Manifolds, Procrustean Metrics, and Complex Projective Shapes”, Bull. London Math. Soc., vol. 16, pp. 81-121, 1984. [5] E. Osuna, R. Freund, and F. Girosi, “Training Support Vector Machines: An Application to Face Detection” Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 130-136, 1997. [6] Fuzhen Huang and Jianbo Su, “Multiple Face Contour Detection Using adaptive Flows”, Sinobiometrics 2004, LNCS 3338, pp. 137-143, Springer-Verlag Berlin eidelberg, 2004. [7] G. Yang and T. S. Huang, “Human Face Detection in Complex Background”, Pattern Recognition, vol. 27, no. 1, pp. 53-63, 1994. [8] H.P. Graf, T. Chen, E. Petajan, and E. Cosatto, “Locating Faces and Facial Parts”, Proc. First Int’l Workshop Automatic Face and Gesture Recognition, pp. 41-46, 1995. [9] J. Canny, “A Computational Approach to Edge Detection”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, June 1986. [10] J. Sobottka and I. Pitas, “Segmentation and Tracking of Faces in Color Images”, Proc. Second Int’l Conf. Automatic Face and Gesture Recognition, pp. 236-241, 1996.  c  [11] K. Lam and H. Yan, “Fast Algorithm for Locating Head Boundaries,” J.Electronic Imaging, vol. 3, no. 4, pp. 351-359, 1994. [12] K.V. Mardia and I.L. Dryden, “Shape Distributions for Landmark Data”, Advanced Applied Probability, vol. 21, pp. 742-755, 1989. [13] Ming-Hsuan Yang, David Kriegman, and Narendra Ahuja, "Detecting Faces in Images: A Survey", IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 24, no. 1, pp. 34-58, 2002. [14] M. Kirby and L. Sirovich, “Application of the Karhunen-LoeveProcedure for the Characterization of Human Faces”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 1, pp. 103-108, Jan. 1990 [15] P. Sinha, “Object Recognition via Image Invariants: A Case Study”, Investigative Ophthalmology and Visual Science, vol. 35, no. 4, pp. 1735-1740, 1994. [16] P. Sinha, “Processing and Recognizing 3D Forms,” PhD thesis, Massachusetts Inst. of Technology, 1995. [17] P. Viola and M. J. Jones, “Robust Real-Time Face Detection”, International Journal of Computer Vision 57(2), 137-154, Kluwer Academic Publishers, Netherlands, 2004. [18] T.F. Cootes and C.J. Taylor, “Locating Faces Using Statistical Feature Detectors”, Proc. Second Int’l Conf. Automatic Face and Gesture Recognition, pp. 204-209, 1996. [19] T.K. Leung, M.C. Burl, and P. Perona, “Finding Faces in Cluttered Scenes Using Random Labeled Graph Matching”, Proc. Fifth IEEE Int’l Conf. Computer Vision, pp. 637-644, 1995. [20] T. Sakai, M. Nagao, and S. Fujibayashi, “Line Extraction and Pattern etection in a Photograph”, Pattern Recognition, vol. 1, pp. 233-248, 1969. [21] Robin Hewitt, “Seeing with OpenCV: A Five-Part Series”, 2007