Luận án Nghiên cứu phát triển một số thuật toán phát hiện và phân loại phương tiện từ dữ liệu video giao thông

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ NGUYỄN VĂN CĂN NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁN PHÁT HIỆN VÀ PHÂN LOẠI PHƯƠNG TIỆN TỪ DỮ LIỆU VIDEO GIAO THÔNG LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI, NĂM 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ NGUYỄN VĂN CĂN NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ THUẬT TOÁN PHÁT HIỆN VÀ PHÂN LOẠI PHƯƠNG TIỆN TỪ DỮ LIỆU VIDEO GIAO THÔNG Chuyên ngành: CƠ SỞ TOÁN HỌC CHO TIN HỌC Mã số: 62 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC 1. PGS. TS. NGUYỄN ĐỨC HIẾU Học viện Kỹ thuật Quân sự 2. TS. PHẠM VIỆT TRUNG Cục Công nghệ thông tin – Bộ Quốc phòng HÀ NỘI, NĂM 2015 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Những nội dung, số liệu và kết quả trình bày trong luận án là hoàn toàn trung thực và chưa có tác giả nào công bố trong bất cứ một công trình nào khác. Tác giả luận án Nguyễn Văn Căn LỜI CẢM ƠN Trước hết tôi xin bày tỏ lòng biết ơn chân thành của tôi với tập thể giáo viên hướng dẫn của tôi, PGS. TS Nguyễn Đức Hiếu, Giám đốc Trung tâm Công nghệ thông tin, Học viện Kỹ thuật Quân sự Việt Nam; TS. Phạm Việt Trung, Phó cục trưởng Cục Công nghệ thông tin - Bộ Quốc phòng trực tiếp hướng dẫn cho tôi thông qua sự tiến bộ nghiên cứu. Tôi muốn cảm ơn tất cả các giảng viên mà tôi đã có vinh dự được cùng làm việc hoặc tham gia các khóa học trong quá trình làm nghiên cứu sinh. Cảm ơn các thầy giáo, cô giáo Viện Công nghệ thông tin, phòng Quản lý đào tạo sau đại học thuộc Viện Khoa học và Công nghệ quân sự - Bộ quốc phòng. Tôi muốn đặc biệt cảm ơn PGS. TS Ngô Quốc Tạo, TS. Nguyễn Đức Dũng, phòng Nhận dạng và Xử lý tri thức, thuộc Viện Công nghệ thông tin, Viện hàn lâm Khoa học Việt Nam; cảm ơn các đồng nghiệp công tác tại Trường Đại học Kỹ thuật – Hậu cần Công an nhân dân đã có những bàn luận, thảo luận hữu ích, cài đặt thử nghiệm trong công việc nghiên cứu của tôi. Cuối cùng, tôi dành luận án này cho gia đình tôi và bạn bè của tôi. Nếu không có sự hỗ trợ của họ đầy đủ, tôi sẽ không có can đảm để đi qua tất cả những khó khăn trong việc nghiên cứu. i MỤC LỤC DANH MỤC CÁC KÝ HIỆU ................................................................................................... iii DANH MỤC CHỮ VIẾT TẮT ................................................................................................. iv DANH MỤC CÁC BẢNG ......................................................................................................... v DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ................................................................................... vi MỞ ĐẦU ............................................................................................................... 1 Chương 1. TỔNG QUAN VỀ PHÁT HIỆN VÀ PHÂN LOẠI PHƯƠNG TIỆN GIAO THÔNG TỪ VIDEO ........................................................................ 8 1.1. Cơ sở lý thuyết và những khái niệm cơ bản ........................................... 8 Dữ liệu video số ............................................................................... 8 1.1.1. Mô-men bất biến ............................................................................ 12 1.1.2. Hình dạng và Khối đối tượng chuyển động ................................... 13 1.1.3. Đường viền đối tượng .................................................................... 13 1.1.4. Nền và đối tượng chuyển động ...................................................... 21 1.1.5. Entropy của khối ............................................................................ 22 1.1.6. Biểu diễn hình dạng đối tượng theo vector khoảng cách .............. 25 1.1.7. 1.2. Một số phương pháp và công trình nghiên cứu liên quan .................... 29 Hệ thống điều khiển giao thông và giám sát an ninh ..................... 30 1.2.1. Hệ thống phát hiện và phân loại xe dựa trên video ....................... 32 1.2.2. Hệ thống giám sát giao thông dựa trên độ dài ............................... 34 1.2.3. Hệ thống giám sát tích hợp phát hiện, theo dõi, phân loại ............ 36 1.2.4. Phát hiện đối tượng ........................................................................ 38 1.2.5. Phân loại đối tượng ........................................................................ 41 1.2.6. 1.3. Hướng tiếp cận của luận án .................................................................. 45 Sơ đồ khái quát hướng tiếp cận xử lý bài toán .............................. 45 1.3.1. Xác định vùng quan tâm và nhiệm vụ của luận án ........................ 47 1.3.2. 1.4. Kết luận chương 1 ................................................................................. 49 Chương 2. PHÁT HIỆN ĐỐI TƯỢNG CHUYỂN ĐỘNG TỪ VIDEO DỰA TRÊN MÔ HÌNH GAUSS HỖN HỢP THÍCH NGHI VỚI THAY ĐỔI ÁNH SÁNG ........................................................................................................ 51 2.1. Một số thuật toán phát hiện chuyển động ............................................. 51 Thuật toán trừ nền cơ bản .............................................................. 51 2.1.1. Thuật toán trừ nền trung bình: ....................................................... 53 2.1.2. Thuật toán Σ-Δ: .............................................................................. 54 2.1.3. Thuật toán Σ-Δ cải tiến: ................................................................. 56 2.1.4. ii Thuật toán thống kê khác biệt cơ bản ............................................ 58 2.1.5. Mô hình Gauss hỗn hợp ................................................................. 61 2.1.6. Đánh giá các thuật toán trừ nền thông qua một số phép đo ........... 66 2.1.7. 2.2. Mô hình và thuật toán đề nghị .............................................................. 72 Mô hình GMM đề nghị .................................................................. 72 2.2.1. Thuật toán trích chọn khối chuyển động (EMB) ........................... 77 2.2.2. 2.3. Phương pháp đếm phương tiện giao thông áp dụng mô hình GMM thích nghi thay đổi ánh sáng kết hợp luồng quang học ............................... 78 Sơ đồ khối tổng quát ...................................................................... 79 2.3.1. Thuật toán phát hiện và gán nhãn cho khối (SLBBI) .................... 82 2.3.2. Thuật toán trích chọn luồng quang học (EBOF) ........................... 83 2.3.3. Kết quả thực nghiệm. ..................................................................... 86 2.3.4. 2.4. Kết luận chương 2. ................................................................................ 91 Chương 3. PHÂN LOẠI PHƯƠNG TIỆN GIAO THÔNG TỪ VIDEO DỰA TRÊN ĐẶC TRƯNG HÌNH DẠNG ........................................................ 93 3.1. Phân đoạn khối phương tiện dựa trên kích thước ................................. 93 Phân tích kích thước phương tiện .................................................. 93 3.1.1. Thuật toán phân loại theo kích thước ............................................ 95 3.1.2. 3.2. Phân loại phương tiện bằng kết hợp kích thước ảnh và hình chiếu hình dạng khối phương tiện ......................................................................... 98 Ý tưởng phương pháp .................................................................... 99 3.2.1. Giai đoạn chuẩn bị CSDL ............................................................ 100 3.2.2. Thuật toán phân loại dựa trên độ dài và hình chiếu đối tượng .... 101 3.2.3. 3.3. Phân loại phương tiện dựa trên đường viền biểu diễn bằng số phức . 103 Sơ đồ khái quát............................................................................. 104 3.3.1. Xấp xỉ độ dài đường viền và thuật toán Douglas Peucker ........... 104 3.3.2. Thuật toán CCAVC ...................................................................... 107 3.3.3. Kết quả thực nghiệm: ................................................................... 111 3.3.4. 3.4. Kết luận chương 3 ............................................................................... 114 PHẦN KẾT LUẬN ........................................................................................... 116 PHỤ LỤC .............................................................................................................. 1 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ ........................................ 118 TÀI LIỆU THAM KHẢO ................................................................................. 119 iii DANH MỤC CÁC KÝ HIỆU Ký hiệu Ý nghĩa  Giá trị ngưỡng cho trước trong trừ nền B(x,y) Giá trị nền cố định tại điểm ảnh (x,y) It(x,y) Giá trị điểm ảnh tại điểm ảnh (x,y) Dt(x,y) Mặt nạ nhị phân của đối tượng tiền cảnh α,,, Hằng số tỷ lệ học cho trước t(x,y) Giá trị tuyệt đối của hiệu giá trị điểm ảnh trừ giá trị nền của điểm ảnh (x,y) tại thời điểm t Vt(x,y) Giá trị điểm ảnh (x,y) của khung hình đang xét thời gian t xy Giá trị trung bình của các điểm ảnh tương ứng của tập hợp điểm ảnh (x,y) theo các khung hình đang xét xy Trung bình độ lệch chuẩn của điểm ảnh (x,y) Mô hình nền thích nghi biến đổi cosin rời rạc Khoảng cách Ơclit giữa các mô hình nền thích nghi P(Xt) Xác suất quan sát của điểm ảnh tại thời điểm t (Xt, , ) Hàm mật độ xác suất tại thời điểm t i,t Ma trận hiệp phương sai của phân bố Gauss thứ i tại thời gian t i,t Giá trị trung bình của các điểm ảnh tại thời điểm t Biến nhận giá trị 1/0 thể hiện sự phù hợp mô hình của điểm ảnh mới k,t Hệ số cập nhật nền K mô hình tại thời điểm t t Hệ số biểu thị mức độ ánh sáng thay đổi Et Giá trị thông tin Entropy của điểm ảnh tại thời điểm t D(t,t-1) Hàm biểu diễn cường độ sáng i Hệ số lựa chọn sự thay đổi ánh sáng I L (x,y) Ảnh điểm ảnh (x,y) biểu diễn mức L trong mô hình kim tự tháp Tập biểu diễn kết quả phát hiện đối tượng tại thời điểm t i Tính chất thứ i của mô-men bất biến  Hằng số xấp xỉ diện tích hai hình đa giác Lrounded Khoảng cách giữa các điểm cơ bản trên biên D(si,c) Khoảng cách giữa điểm mẫu và trọng tâm đa giác SIM(D1,D2) Độ đo tương tự giữa 2 đa giác D1 và D2. iv u Chiều dài đối tượng tính xấp xỉ v Chiều rộng đối tượng tính xấp xỉ  Đường viền Vector  Vector cơ sở đường viền  Tích vô hướng giữa 2 đường viền (m) Hàm tương quan giữa 2 đường viền m đỉnh ( ) ( ) { v DANH MỤC CÁC CHỮ VIẾT TẮT Chữ viết tắt Ý nghĩa ACF Hàm tự tương quan (Auto Correlation Function) BMC Thách thức mô hình trừ nền (Background Models Challenge) BSM Trừ nền (Background Subtraction Method) BGS Thư viện trừ nền (Background Subtraction Library) CA Phân tích đường viền (Contour Analys) CSDL Cơ sở dữ liệu (Database) EV Vector cơ sở (Elementary Vector) FG Tiền cảnh (Foreground) GMM Mô hình hỗn hợp Gauss (Gauss Mixture Model) ICF Hàm tương quan (Intercorrelation Function) NSP Tích vô hướng chuẩn hóa (Normalized Scalar Product) ROI Vùng quan tâm (Region of Interest) TVH Tích vô hướng VC đường viền vector (Vector Contour) VVDC Phát hiện và phân loại phương tiện dựa trên video (Video-based Vehicle Detection and Classification) vi DANH MỤC CÁC BẢNG Bảng 1.1. Phân loại các phương pháp mô hình nền ...................................................... 40 Bảng 1.2. Kết quả sử dụng độ dài đường biên hình chiếu ........................................... 42 Bảng 2.1. Ưu điểm và nhược điểm các thuật toán BSM đã trình bày .......................... 64 Bảng 2.2. Hệ số đánh giá toàn cục các thuật toán BS trong tập dữ liệu BMC [36]. .... 69 Bảng 2.3. Dữ liệu thực nghiệm ..................................................................................... 87 Bảng 2.4. Phản ứng với mật độ xe trên các cung đường .............................................. 90 Bảng 2.5. So sánh thời gian xử lý của thuật toán với mỗi khung hình ......................... 90 Bảng 3.1. Kết quả thực nghiệm thuật toán CVIL ......................................................... 98 Bảng 3.2. Bảng kết quả thực nghiệm thuật toán VCALOS ....................................... 103 vii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Cấu trúc phân đoạn của video ............................................................... 8 Hình 1.2. Các biến đổi hình dáng đối tượng trong không gian 2D. .................... 12 Hình 1.3. Biểu diễn đường viền bằng vector số phức ......................................... 14 Hình 1.4. NSP trên đường viền vector ................................................................ 18 Hình 1.5. Biểu diễn đường viền và lược đồ xám ................................................ 21 Hình 1.6. Mô tả hình dạng hình tròn ................................................................... 26 Hình 1.7. Đa giác xấp xỉ đối tượng có n cạnh ..................................................... 27 Hình 1.8. Điểm mẫu căng đều trên mỗi cạnh biên .............................................. 28 Hình 1.9. Kiến trúc tổng thể hệ thống CadProTMS ........................................... 31 Hình 1.10. Trạm nghiệp vụ xử lý phạt nguội vượt đèn đỏ ngã tư ...................... 32 Hình 1.11. Cấu trúc hệ thống phát hiện và phân loại xe dựa trên video ............. 33 Hình 1.12. Sơ đồ của hệ thống giám sát giao thông tự động .............................. 35 Hình 1.13. Cấu trúc hệ thống tích hợp phát hiện, phân loại, theo dõi đối tượng 36 Hình 1.14. Cấu trúc hệ thống phát hiện đối tượng chuyển động ........................ 37 Hình 1.15. Lược đồ khái quát phân loại đối tượng dựa trên hình chiếu ............. 38 Hình 1.16. Cấu trúc khái quát hệ thống nhận dạng đối tượng chuyển động ...... 46 Hình 1.17. Sơ đồ xác định vùng nghiên cứu ....................................................... 47 Hình 1.18. Hướng tiếp cận xử lý bài toán ........................................................... 49 Hình 2.1. Lược đồ khái quát thuật toán CCA-GMMOF ..................................... 80 Hình 2.2. Minh họa thuật toán gán nhãn cho khối .............................................. 83 Hình 2.3. Dữ liệu video quay trên đường quốc lộ 5, hướng Hải phòng - Hà Nội ............................................................................................................................. 88 Hình 2.4. Một số hình ảnh từ camera đưa vào thực nghiệm ............................... 89 Hình 2.5. Giao diện kết quả thực nghiệm của hệ thống ...................................... 89 Hình 3.1. Phân tích kích thước khối xe ô tô con ................................................. 93 Hình 3.2. Sơ đồ tổng quát phân giải theo độ dài ................................................. 95 Hình 3.3. Sơ đồ tổng quát phân loại theo hình dạng ........................................... 99 Hình 3.4. Sơ đồ khối tổng quát phân loại theo đường viền .............................. 104 Hình 3.5 Đơn giản hóa đường công theo thuật toán Douglas Peucker ............ 105 Hình 3.6. Xấp xỉ hóa đường viền ...................................................................... 106 Hình 3.7. Giao diện hệ thống thực nghiệm thuật toán CCAVC ....................... 111 Hình 3.8. Giao diện hệ thống thực nghiệm thuật toán CCAVC ....................... 112 Hình 3.9. Ví dụ về tập mẫu để so sánh ............................................................. 113 Hình 3.10. Ví dụ kết quả nhận dạng xe ô tô và xe máy .................................... 114 1 MỞ ĐẦU Phần này giới thiệu bài toán phát hiện và phân loại phương tiện giao thông, những vấn đề đặt ra cho bài toán để giải quyết vấn đề tăng độ chính xác với điều kiện giao thông đông đúc và đa dạng ở Việt Nam. Tiếp theo, trình bày mục tiêu, phạm vi, nội dung và phạm vi nghiên cứu của luận án. Cuối cùng là giới thiệu cấu trúc của luận án. 1. Tính cấp thiết của vấn đề nghiên cứu Giám sát và quản lý giao thông đã và đang được các nhà khoa học thế giới và Việt Nam quan tâm nghiên cứu phát triển. Trong điều kiện giao thông Việt Nam, từ các tuyến đường quốc lộ, đường cao tốc, đến giao thông đô thị, giao thông nông thôn mật độ phương tiện rất dày đặc, đa dạng về chủng loại, trong đó hai thành phần chính đó là ô tô và xe máy. Nếu mật độ xe dày đặc, tức là số lượng xe trên một vùng quan sát là lớn, khi đó ảnh giao thông thu được tồn tại các phương tiện trước sau, bên cạnh liên tiếp nhau, các phương tiện tạo thành khối phương tiện, khi đó các đường viền có thể bị che khuất thì việc phân tích đường viền các phương tiện để phát hiện, đếm, phân loại gặp rất nhiều khó khăn. Nhiều nghiên cứu trên thế giới và Việt Nam đã quan tâm đến vấn đề phát hiện và phân loại phương tiện giao thông, tuy nhiên chưa có nghiên cứu đầy đủ nào quan tâm đến mức độ dày đặc của phương tiện trên đường, cũng như quan tâm đặc biệt đến phương tiện giao thông chủ yếu là xe máy và xe ô tô. Việc lựa chọn phương pháp, thuật toán, hay phối kết hợp các thuật toán sử dụng trong hệ thống giám sát tự động, cũng như cải tiến một số thông số kỹ thuật trong thuật toán mang lại lợi ích cho việc phát hiện và phân loại phương tiện giao thông trong bối cảnh Việt Nam là điều cần thiết có ý nghĩa cả về lý thuyết và thực tiễn. Bài toán phát hiện và phân loại phương tiện giao thông dựa trên video là xét xem tại một thời điểm, trong vùng quan tâm, có những loại phương tiện gì, số lượng tương ứng. Về ứng dụng, bài toán thuộc nhóm các ứng dụng liên quan 2 đến giao thông thông minh. Bài toán được ứng dụng nhiều trong lĩnh vực quản lý giao thông, trong nhiều hoạt động an ninh, quốc phòng, kinh tế xã hội, như cảnh báo trộm, cảnh báo cháy, giám sát bảo vệ các mục tiêu quan trọng, thu thập các chứng cứ tại những tình huống nhạy cảm. Yêu cầu cơ bản của bài toán phát hiện và phân loại giao thông là với dữ liệu đầu vào là video giao thông, yêu cầu đầu ra là loại phương tiện tham gia giao thông trong vùng quan sát (ô tô, xe máy và các phương tiện thô sơ khác). Hướng tiếp cận giải quyết bài toán: Thứ nhất, cần xem xét cấu trúc và phương pháp xử lý dữ liệu video. Cấu trúc dữ liệu video được kết cấu từ tập các khung hình, tốc độ hiển thị các khung hình trong một đơn vị thời gian (giây), mỗi khung hình là một ảnh tĩnh,... Phương pháp xử lý dữ liệu video là việc xử lý lưu trữ, trích chọn khung hình, phân đoạn, phân tích, trích chọn đặc trưng dựa trên cơ sở dữ liệu (CSDL) tri thức có sẵn. Từ những tập dữ liệu video, qua quá trình xử lý, mang lại những thông tin hữu ích theo mục đích yêu cầu của con người. Thứ hai, cần xác định tập các đặc trưng riêng có của video giao thông. Các đặc trưng của phương tiện chuyển động trong video được chia thành 2 mức tiếp cận: mức cục bộ và mức toàn cục. Mức toàn cục quan tâm đến các đặc trưng toàn cảnh như nền, đối tượng chuyển động, khối, đốm sáng. Mức cục bộ quan tâm đến các vấn đề xử lý hình dạng, khoảng cách, đường biên,... Đặc trưng tiếp cận ở mức toàn cục gồm:  Vùng quan tâm (ROI), hướng quan sát, khoảng cách quan sát;  Video và khung hình;  Đối tượng chuyển động và nền (Moving Object and Background);  Khối chuyển động (Block);  Đốm sáng (Blob). Đặc trưng ở mức toàn cục ảnh hưởng nhiều đến trích chọn đối tượng chuyển động. ROI ảnh hưởng đến việc xét điểm bắt đầu và điểm kết thúc thời điểm quan sát, hướng quay ảnh hưởng đến hình dạng đối tượng; Video ảnh 3 hưởng đến chất lượng hình ảnh, độ phân giải, tốc độ hình; Khung hình được trích chọn từ video thành ảnh tĩnh để phân tích,... Đặc trưng tiếp cận ở mức cục bộ gồm:  Đối tượng chuyển động và bóng của nó (Moving Object, Shadow);  Độ dài (Visual Length);  Hình dạng đối tượng (Edge, Contour), hình dạng và đường viền;  Mức xám khu vực đèn trước/sau xe;  Mức xám và đặc điểm khu vực biển số xe, kính trước xe;  Các đường biên ngang trên xe. Đặc trưng ở mức cục bộ, đặc biệt là độ dài, hình dạng đ