Đề tài Nghiên cứu kĩ thuật xử lí video số, ứng dụng vào theo vết và phân loại đối tượng

KH OA C NT T – Đ H KH TN ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN DUY NGHĨA - 0012612 NGHIÊN CỨU KĨ THUẬT XỬ LÍ VIDEO SỐ, ỨNG DỤNG VÀO THEO VẾT VÀ PHÂN LOẠI ĐỐI TƯỢNG LUẬN VĂN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN TH.S NGUYỄN TRI TUẤN NIÊN KHÓA 2000 - 2004 PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN LỜI CẢM ƠN Trước tiên tôi xin cảm ơn thầy Nguyễn Tri Tuấn người đã hướng dẫn tôi thực hiện đề tài này. Nhờ có sự tin tưởng, chỉ bảo tận tình của thầy tôi luận văn này đã hoàn thành. Con xin gửi tất cả lòng biết ơn, quý trọng đến ông bà, cha mẹ và các người thân trong gia đình đã hết lòng nuôi con ăn học và luôn luôn ở bên cạnh con động viên con khi con gặp khó khăn Em xin cảm ơn tất cả các thầy cô trong trong trường Khoa Học Tự Nhiên và đặc biệt là các thầy cô trong Khoa Công Nghệ Thông tin đã nhiệt tình giảng dạy và truyền đạt nhiều kiến thức quý báu cho em. Tôi xin chân thành cảm ơn bàn bè trong lớp cũng như các anh chị khóa trước đã cho giúp đỡ chỉ bảo tận tình, đặc biệt là anh Trương Thiên Đỉnh đã giúp đỡ tôi nhiều mặt về thiết bị cũng như tài liệu Đây là một hướng nghiên cứu mới và rất khó, với thời gian tiếp cận khá ngắn trong vòng 6 tháng và năng lực của người làm đề tài cho nên đề tài chắc chắn còn nhiều thiếu sót. Huy vọng sẽ nhận được nhiều lời đóng góp để đề tài này hoàn thiện hơn Tp HCM tháng 7 năm 2004 Sinh viên thực hiện Nguyễn Duy Nghĩa PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN CHƯƠNG 1_____________________________________________ 1 MỞ ĐẦU_________________________________________________ 1 1.1 Tổng quan____________________________________________ 1 1.2 Yêu cầu bài toán ______________________________________ 2 1.3 Bố cục luận văn_______________________________________ 2 C ƯƠNG 2_____________________________________________ 4 TỔNG QUAN VỀ VIDEO VÀ CÁC KĨ THUẬT XỬ LÍ VIDEO CƠ BẢN____________ 4 2.1 Khái niệm về video ______________________________________ 5 2.2 Khái niệm về video tuần tự ____________________________ 5 2.2.1 Tín hiệu video tuần tự _________________________________ 5 2.2.2 Các chuẩn video tương tự ______________________________ 8 2.2.3 Các thiết bị video tương tự _____________________________ 8 2.3 Khái niệm về video số _________________________________ 9 2.3.1 Tín hiệu Video số _____________________________________ 9 2.3.2 Các chuẩn video số ____________________________________ 9 2.3.3 Nhược điểm của video số ______________________________ 11 2.3.4 Ưu điểm của video số _________________________________ 11 PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 2.3.5 Các phương pháp xử lý trên video số ____________________ 12 2.3.5.1 Phát hiện chuyển động ______________________________ 12 2.3.5.2 Ước lượng chuyển động _____________________________ 19 CHƯƠNG 3____________________________________________ 25 THEO VẾT VÀ PHÂN LOẠI ĐỐI TƯỢNG 25 3.1 Bài toán theo vết và phân loại đối tượng_______________ 26 3.2 Mô hình xử lí bài toán________________________________ 27 3.3 Tiền xử lí ____________________________________________ 28 3.4 Phát hiện chuyển động _______________________________ 28 3.5 Theo vết đối tượng ___________________________________ 37 3.5.1 Dự đoán vị trí của đối tượng trong tương lai ______________ 38 3.5.2 So khớp đối tượng____________________________________ 38 3.5.3 Theo vết đối tượng ___________________________________ 41 3.5.4 Cập nhật đối tượng___________________________________ 45 3.6 Phân loại đối tượng __________________________________ 45 CHƯƠNG 4____________________________________________ 48 CÀI ĐẶT CHƯƠNG TRÌNH ____________________ 48 4.1 Môi trường cài đặt ___________________________________ 49 PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 4.2 Cấu trúc chương trình _______________________________ 49 4.2.1 Cấu trúc dữ liệu _____________________________________ 49 4.2.2 Cấu trúc chương trình ________________________________ 51 CHƯƠNG 5____________________________________________ 52 KẾT QUẢ VÀ HƯỚNG PHÁT TRIỂN_______ 52 5.1 Kết quả đạt được ____________________________________ 53 5.1.1 Dữ liệu thử nghiệm___________________________________ 53 5.1.2 Kết quả đạt được ____________________________________ 53 5.2 Hướng phát triển ____________________________________ 54 TÀI LIỆU HAM KHẢO _________________________ 55 PHỤ LỤC 1____________________________________________ 56 MỘT VÀI HÌNH ẢNH VỀ KẾT QUẢ ĐẠT ĐƯỢC ___________________________________________________ 56 1. Một vài mặt nạ chuyển động____________________________ 56 2. Kết quả theo vết đối tượng _____________________________ 63 3. Kết quả theo vết đối tượng là người _____________________ 66 PHỤ LỤC 2____________________________________________ 69 PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN VÀI NÉT VỀ THƯ VIỆN INTEL OPENCV 69 1. OpenCV là gì? _________________________________________ 69 2. Các chức năng của thư viện OpenCV ___________________ 69 2.1 Các kiểu dữ liệu cơ bản _______________________________ 69 2.2 Các hàm xử lí trong OpenCV __________________________ 71 2.2.1 Các hàm xử lí các kiểu dữ liệu cơ bản _____________________ 71 2.2.2 Các hàm về xử lí ảnh __________________________________ 72 2.2.3 Các hàm về phân tích vận động và theo vết đối tượng _________ 73 2.2.4 Các hàm về nhận dạng đối tượng _________________________ 73 2.2.5 Các hàm về giao diện và thu nhận video ___________________ 73 PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 1 CHƯƠNG 1 MỞ ĐẦU 1.1 Tổng quan Hiện nay phần lớn lượng thông tin con người thu vào là dưới dạng hình ảnh. Thông tin dưới dạng hình ảnh là thông tin trực quan nên con người dễ dàng tiếp nhận nó. Với sự ra đời của nhiều máy móc kỹ thuật hiện đại như là máy ảnh số, máy quay số, các máy thu hình, máy vi tính ... thì lượng thông tin con người thu được ngày càng nhiều. Con người không chỉ muốn tiếp thu thông tin một cách thụ động mà phải biết xử lí nó, làm cho nó hữu ích hơn. Do đó con người đã tiến hành nghiên cứu các phương pháp xử lí trên thông tin trực quan này để chúng ta có thể tiếp nhận tối đa lượng thông tin trực quan này. Việc xử lý ảnh số đã ra đời vào những năm 1960 với nhiều hướng khác nhau như là nén ảnh, nhận dạng ..., trong khi đó việc xử lý video chỉ xuất hiện vào các thập kỷ gần đây cùng với sự ra đời của nhiều trang thiết bị kỹ thuật mới và hiện đại. Ngày nay trên thế giới việc nghiên cứu về ảnh số và video số đã phát triển rộng rải. Các trường đại học đều có một ngành riêng để nghiên cứu vấn đề này gọi là ngành thị giác máy tính( computer vision ). Tuy vậy vấn đề này vẫn còn mới ở Việt Nam vì thiếu các thiết bị hỗ trợ và tài liệu, và đây là một hướng phát triển mở nhiều hứa hẹn và cũng nhiều thách thức. Hiện nay ở Việt Nam các hệ thống giám sát ở Việt PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 2 Nam chưa phát triển lắm và chủ yếu vẫn dựa vào con người. Tuy nhiên trong vài năm nữa khi kinh tế và khoa học kỹ thuật phát triển thì các hệ thống giám sát này cũng sẽ phát triển theo. Việc nghiên cứu về xử lí video số ở trong khoa được tiến hành cách đây một năm với các đề tài về giám sát giao thông và theo vết đối tượng bằng lưới... Với mong muốn tham gia vào hướng nghiên cứu còn mới này và giúp các hệ thống giám sát đạt hiệu quả cao hơn và giảm được chi phí con người chúng tôi thực hiện đề tài “nghiên cứu các kĩ thuật xử lí trên video số ứng dụng vào theo vết và phân loại đối tượng” . 1.2 Yêu cầu bài toán Bài toán “theo vết và phân loại đối tượng” được chia thành hai phần. Ở đây chúng tôi tập trung vào nghiên cứu phần một đó là phần theo vết đối tượng. Về theo vết đối tượng ta cần phải thực hiện các phần sau: · Rút trích đối tượng chuyển động. Trong phần này ta phải tách các đối tượng chuyển động ra khỏi khung cảnh. · Theo vết đối tượng. Với từng đối tượng ta phải lưu lại được quỹ đạo của chúng khi chúng vào vùng quan sát của ta Về phân loại đối tượng, chúng ta phải phân biệt được các loại đối tượng trong khung cảnh quan sát của chúng ta. Ở đây là phân loại đối tượng là người đi bộ và các đối tượng khác như là xe... 1.3 Bố cục luận văn Dựa vào các yêu cầu trên chúng tôi chia luận văn thành 5 chương Chương 1: Mở đầu Chương 2: Tổng quan về video và các kĩ thuật xử lí video số: nhằm giúp chúng ta hiểu rõ hơn về video số và các kĩ thuật cơ bản nhất trong xử lí video số. PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 3 Chương 3: Ứng dụng vào bài toán theo vết và phân loại đối tượng: trong phần này ta sẽ áp dụng các kĩ kiến thức đã nghiên cứu được vào giải một bài toán trong xử lí video dó là theo vết đối tượng. Chương 4: Cài đặt thử nghiệm Chương 5: Các kết quả đạt được và hướng phát triển: chương này trình bày các kết quả đạt được trong việc giải quyết bài toán trên và hướng phát triển trong tương lai. PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 4 CHƯƠNG 2 TỔNG QUAN VỀ VIDEO VÀ CÁC KĨ THUẬT XỬ LÍ VIDEO CƠ BẢN PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 5 2.1 Khái niệm về video Video hay còn gọi là chuỗi ảnh( image sequence ) tượng trưng cho thông tin hình ảnh. Đó là một chuỗi các hình ảnh truyền liên tục theo thời gian S = f(x,y,t) trong đó : x,y Î R: là tọa độ của điểm ảnh (thông tin về không gian) t Î R: thông tin về thời gian Dựa trên công thức trên ta thấy ảnh tĩnh là một trường hợp đặc biệt của Video. Khi đó nó là một chuỗi các ảnh không thay đổi theo thời gian. f(x,y,t1) = f(x,y,t2); "i,j Î R, " x,y Î R Video thường được thu, lưu trữ, và chuyển đổi ở dạng tuần tự (analog) nên chúng ta sẽ bắt đầu từ video tuần tự. 2.2 Khái niệm về video tuần tự 2.2.1 Tín hiệu video tuần tự Tín hiệu video tuần tự được xem như là tín hiệu điện 1 chiều theo thời gian f(t) và được lấy mẫu theo chiều dọc. Việc lấy mẫu theo chu kỳ này được gọi là quét( scanning ). Các phương pháp quét thường được sử dụng nhất là quét liên tục (progressive scanning) và quét xen kẽ (interlace scanning) PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 6 Quét liên tục(progressive scanning) H1: Quét liên tục. Các dòng quét bắt đầu từ A đến B, tiếp tục đến C và cứ thế cho đến D rồi quay trở lại D o Mỗi ảnh hay còn được gọi là frame là dữ liệu được lấy mẫu theo thời gian. o Mỗi ảnh này được quét liên tục từng dòng ngang và từ trên xuống dưới với tốc độ là Dt giây. o Phương pháp quét này thường được dùng trong công nghiệp máy tính với tốc độ Dt = 1/72 giây. PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 7 Quét xen kẽ H2: Quét xen kẻ. Dòng quét bắt đầu từ A đến B, chuyển qua C và tiếp tục cho đến khi tới D sẽ trở về E và tiếp tục quét đến F Vì mắt người phát hiện ra hình ảnh chớp khi tần số quét dưới 50Hz nên tần số quét của máy bao giờ cũng phải lớn hơn 50Hz. Tuy nhiên khi áp dụng trong các nghành công nghiệp khác như là nghành truyền thông thì gặp khó khăn về vấn đề băng thông do kích thước quá lớn. Từ đó xuất hiện phương pháp quét xen kẽ. Phương pháp này chia dòng quét thành dòng chẳn và dòng lẻ ( gọi là field ) và quét các dòng chẳn trong khoảng Dt rồi chuyển qua quét các dòng lẻ. Vì thế tần số quét sẽ giảm đi một nữa. Một vài thông số quan trọng của tín hiệu video là : o Độ phân giải theo chiều dọc ( vertical resolution ): thông số này có liên quan đến số dòng quét trên 1 frame. o Tỉ lệ co ( aspect ratio ): tỉ lệ giữa chiều rộng và chiều cao của frame. PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 8 2.2.2 Các chuẩn video tương tự · Component Analog Video: chuẩn video này sử dụng các thành phần màu RGB hoặc là YCrCb( YIQ hoặc là YUV ) · Composite Video: o NTSC ( National Television Standards Committee ): xuất hiện vào năm 1952, hiện tại được sử dụng ở Bắc Mỹ và Nhật. Có 262.5 dòng trên 1 field hay là 525 dòng trên 1 frame, 60 field trên 1 giây và có tỉ lệ co là 4:3 o PAL ( Phase Alternating Line ) và SECAM ( SEquential Color And Memory ): được phát triển vào những năm 1960 và ngày nay thường được sử dụng ở Châu Âu. Ở Việt Nam cũng dùng chuẩn này. Các thông số kỹ thuật: 625 line trên 1 frame, 50 field trên 1 giây. 2.2.3 Các thiết bị video tương tự Các thiết bị video tương tự có thể được chia làm 3 loại. Loại dành cho truyền thông. Loại có chất lượng chuyên nghiệp. Loại dành cho người tiêu dùng. Video được quay bởi máy quay thông thường và được lưu trong băng hoặc được quay bởi các máy quay dùng trong phim trường và tạo thành phim ( 24 frame/giây ). Hầu hết tín hiệu video tương tự được lưu dựa trên kỹ thuật từ ngoại trừ đĩa laser là dùng kỹ thuật quang. PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 9 2.3 Khái niệm về video số 2.3.1 Tín hiệu Video số Tín hiệu video số được lưu trữ dưới dạng số. Do đó chúng được lấy mẫu và lượng tử hóa. Tín hiệu video số là một thông tin 3 chiều gồm 2 chiều không gian và 1 chiều thời gian hay còn được gọi là chuỗi ảnh số với mỗi ảnh số là một ảnh được lấy mẫu và lượng tử hóa. chiều thời gian chiều dọc chiều ngang H3: chuỗi ảnh 2.3.2 Các chuẩn video số Việc trao đổi giữa các ứng dụng và các sản phẩm video số đã đưa ra các chuẩn video số. Các chuẩn này bao gồm : · Chuẩn nén: dùng để trao đổi thông tin trong dạng nén của video · Chuẩn các độ phân giải hiển thị: được dùng trong công nghiệp máy tính. · Chuẩn studio số: được dùng trong ngành công nghiệp ti vi · Chuẩn về giao tiếp mạng được dùng trong công nghiệp truyền thông PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 10 H4: các chuẩn về studio số PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 11 H5: Các chuẩn về ảnh và video số nén 2.3.3 Nhược điểm của video số Nhược điểm của video số đó là nó đòi hỏi khối lượng lưu trữ lớn và băng thông rộng để truyền tải. Chúng ta hãy thử làm một phép tính. Với tín hiệu TV chất lượng tốt ta cần 1440 điểm ảnh trên một dòng, 1050 dòng cho một frame độ sáng, 720 điểm trên một dòng và 525 dòng trên một frame sắc màu. Bởi vì mỗi giây có 30 frame và 8 bit/ pixel nên kết quả cuối cùng là xấp xĩ 545 Mps. Đây là một yêu cấu quá lớn. Do đó hiện nay người ta đang nghiên cứu các phương pháp nén video để giảm kích thước khi truyền tải. 2.3.4 Ưu điểm của video số Tuy có nhược điểm về yêu cầu bộ nhớ lớn nhưng video số lại có nhiều ưu điểm quan trọng. Video tuần tự cung cấp cho chúng ta một số rất giới hạn các hoạt động tương tác như là : chọn kênh, chỉnh tới lui hay là quay chậm trên băng video. Ngoài ra để hiển thị tín hiệu theo chuẩn này ví dụ NTSC trên một hệ máy dùng chuẩn khác ví dụ PAL ta cần có một bộ chuyển đổi tín hiệu đắt tiền. Với tín hiệu số ta không cần phải chuyển đổi các tín hiệu này. Ngoài ra ta còn có thể PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 12 chỉnh sửa, tạo các hiệu ứng đẹp trên tín hiệu video số. Video số không chỉ có vai trò giải trí mà nó còn cung cấp cho chúng ta nhiều thông tin quan trọng trong nhiều lĩnh vực như là các ảnh giám sát quân sự, điều khiển giao thông, và rút trích thông tin từ các dữ liệu ảnh và video. 2.3.5 Các phương pháp xử lý trên video số Video số có nhiều thông tin trực quan hơn là ảnh số. Lý do chính là do video số có chứa thông tin về chuyển động trong khi ảnh số chỉ là ảnh chụp một cảnh tĩnh. Các chuỗi ảnh động luôn hàm chứa các thông tin về chuyển động, các chuyển động này là một tín hiệu nhạy cảm đối với thị giác con người. Con người có thể dễ dàng nhận biết được các đối tượng ngay khi chúng chuyển động thậm chí chúng rất khó thấy khi đứng yên. Vì thế các phương pháp xử lí video số cũng khác so với các phương pháp xử lí ảnh số. Vận động là thông tin quan trọng trong xử lí video số bởi vì vận động mang rất nhiều thông tin về mối quan hệ không gian và thời gian giữa các đối tượng trong ảnh. Các phương pháp cơ bản trong xử lí video số là phát hiện chuyển động và ước lượng chuyển động. Phát hiện chuyển động thường được áp dụng trong các hệ quan sát( phát hiện đối tượng di chuyển hoặc là đứng yên ), còn ước lượng chuyển động thường được áp dụng trong nén video số. Ngoài ra còn có các phương pháp xử lí khác được áp dùng vào mức tiền xử lí như là lọc nhiễu... các phương pháp này áp dụng trên từng frame giống như trong xử lí ảnh số. 2.3.5.1 Phát hiện chuyển động a. Sơ nét về chuyển động Chuyển động theo các khái niệm trong vật lý là sự thay đổi vị trí giữa vật này và vật kia. Tức là khi xét tới sự chuyển động thì ta phải xét là nó chuyển động so với cái gì. Khi xét tới chuyển động ta thường đặt nó vào một hệ PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 13 quy chiếu quán tính. Một vật có thề đứng yên trên hệ quy chiếu này nhưng lại chuyển động khi xét nó với hệ quy chiếu khác. Ví dụ khi ta đứng yên thì có thể coi là ta đứng yên so với hệ quy chiếu gắn với trái đất, nhưng khi đưa vào hệ quy chiếu gắn với mặt trời thì ta lại chuyển động. Điều này có ý nghĩa rất quan trọng khi ứng dụng vào camera động. Chuyển động trong thực tế là chuyển động 3D nhưng khi con người tiếp nhận thì nó trở thành chuyển động 2D. Nói chung hình ảnh mà mắt người nhận được đều là 2D hết. Và phép toán chuyển đổi ảnh 3D thành ảnh 2D mà mắt con người cảm nhận được là phép chiểu phối cảnh. H6 Phép chiếu phối cảnh của một đoạn thẳng Chuyển động trong thế giới thực 3D qua phép chiếu phối cảnh sẽ biến thành chuyển động trong mặt phẳng 2D. Tuy nhiên con người nhận biết chuyển động qua sự thay đổi độ sáng của điểm ảnh. Do đó có những chuyển động mà con người không có cảm nhận được như là chuyển động của quả cầu đồng màu. Từ đó ta có phương pháp phát hiện chuyển động đầu tiên đó là so sánh sự khác biệt theo thời gian. z x y mặt phẳng chiếu P1 P2 O Tâm chiếu PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 14 b. Phương pháp so sánh sự khác biệt Chúng ta xác định độ sai khác Dk,k-1 giữa frame thứ k và thứ k-1 như sau : Dk,,k-1 = Fk – Fk-1 trong đó: Fk là frame tại thời điểm k Nếu camera tĩnh, sự thay đổi ánh sáng rất nhỏ và nhiễu không đáng kể thì một điểm được coi là chuyển động nếu độ khác biệt của nó lớn hơn 0 và ngược lại sẽ đứng yên. Tuy nhiên trong thực tế các điều kiện trên khó có thể xảy ra. Do đó để loại bỏ các điểm mà chúng ta phát hiện sai do nhiễu gây ra, ta có thể dùng một ngưỡng T thích hợp. Mk,k-1( x, y ) = î í ì > laiNguoc neu 0 T | )y x,1(-k,Dk, | 1 Với Mk,k+1 được gọi là mặt nạ chuyển động ở thời điểm k, nếu bằng 1 thì điểm đó được coi là chuyển động và bằng 0 thì điểm đó là đứng yên. T là ngưỡng thích hợp có thể là một giá trị cụ thể được xác định trong quá trình thực nghiệm hoặc dựa trên các thuật toán. Độc giả có thể tham khảo một thuật toán xác định ngưỡng ở phụ lục B của [1]. frame thứ k frame thứ k-1 mặt nạ chuyển động H7: Kết quả của phương pháp so sánh sự khác biệt PDF created with FinePrint pdfFactory Pro trial version KH OA C NT T – Đ H KH TN 15 Ưu điểm của phương pháp này là đơn giản và dễ cài đặt do