Luận án Nghiên cứu và phát triển một số kỹ thuật định vị dựa trên hình ảnh, ứng dụng trợ giúp dẫn đường cho người khiếm thị

LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. TS. Trần Thị Thanh Hải 2. PGS.TS. Nguyễn Quang Hoan Hà Nội −2016 LỜI CAM ĐOAN Tôi xin cam đoan luận án: “Nghiên cứu phát triển một số kỹ thuật định vị dựa trên hình ảnh, ứng dụng trợ giúp dẫn đường cho người khiếm thị” là công trình nghiên cứu của riêng tôi. Một phần các số liệu, kết quả trình bày trong luận án là trung thực, đã được công bố trên các tạp chí khoa học chuyên ngành, kỷ yếu hội nghị khoa học trong nước và quốc tế. Phần còn lại của luận án chưa được công bố trong bất kỳ công trình nghiên cứu trong và ngoài nước. Hà Nội, ngày 20 tháng 7 năm 2016 NGHIÊN CỨU SINH Nguyễn Quốc Hùng TẬP THỂ HƯỚNG DẪN KHOA HỌC TS. Trần Thị Thanh Hải PGS.TS. Nguyễn Quang Hoan i LỜI CẢM ƠN Luận án tiến sĩ được thực hiện tại Viện Nghiên cứu Quốc tế MICA, trường Đại học Bách khoa Hà Nội dưới sự hướng dẫn khoa học của TS. Trần Thị Thanh Hải và PGS.TS. Nguyễn Quang Hoan. Nghiên cứu sinh xin bày tỏ lòng biết ơn sâu sắc tới các thầy, cô về định hướng khoa học trong suốt quá trình nghiên cứu. Nghiên cứu sinh xin được trân trọng cảm ơn các nhà khoa học, tác giả các công trình công bố đã được trích dẫn và cung cấp nguồn tư liệu quý báu trong quá trình hoàn thành luận án. Nghiên cứu sinh xin trân trọng cảm ơn Viện Nghiên cứu Quốc tế đa phương tiện MICA; Viện Đào tạo sau Đại học Trường Đại học Bách Khoa Hà Nội; GS.TS. Phạm Thị Ngọc Yến; GS.TS. Eric Castelli; đề tài KHCN tiềm năng mã số: KC.01.TN19/11-15, đề tài VLIR mã số: ZEIN2012RIP19; đề tài hợp tác Việt - Bỉ mã số: FWO.102.2013.08; Quỹ phát triển KH&CN quốc gia Việt Nam; Trường THCS Nguyễn Đình Chiểu Hà Nội; nhóm nghiên cứu IPI Đại học GENT Vương quốc Bỉ...đã tạo điều kiện thuận lợi về thời gian, địa điểm thực tập, trang thiết bị, hỗ trợ về mặt nhân lực để NCS thực hiện việc thu thập dữ liệu, thực nghiệm các kết quả nghiên cứu. Cuối cùng nghiên cứu sinh xin bày tỏ sự biết ơn tới Ban giám hiệu Trường Cao đẳng Y tế Thái Nguyên; gia đình và đồng nghiệp đã động viên khích lệ, tạo mọi điều kiện thuận lợi để NCS yên tâm công tác và học tập. Hà Nội, ngày 20 tháng 7 năm 2016 NGHIÊN CỨU SINH Nguyễn Quốc Hùng ii MỤC LỤC LỜI CAM ĐOAN i LỜI CẢM ƠN ii MỤC LỤC vi DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT vii DANH MỤC CÁC BẢNG ix DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ xv MỞ ĐẦU 1 1 TỔNG QUAN VỀ HỆ THỐNG TRỢ GIÚP NGƯỜI KHIẾM THỊ 4 1.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Các nghiên cứu trên thế giới . . . . . . . . . . . . . . . . . . . . 4 1.2.1.1 Siêu âm . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1.2 Hồng ngoại . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1.3 Laser . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1.4 Camera . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1.5 Đa cảm biến . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Các nghiên cứu trong nước . . . . . . . . . . . . . . . . . . . . . 10 1.2.3 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Mục tiêu nghiên cứu và phương pháp đề xuất . . . . . . . . . . . . . . 12 1.3.1 Mục tiêu và phạm vi nghiên cứu . . . . . . . . . . . . . . . . . . 12 1.3.2 Phương pháp đề xuất . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Kết luận chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 BIỂU DIỄN MÔI TRƯỜNG VÀ ĐỊNH VỊ 14 2.1 Giới thiệu chung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Những nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.1 Hướng tiếp cận sử dụng bản đồ số liệu . . . . . . . . . . . . . . 15 2.2.2 Hướng tiếp cận sử dụng bản đồ topo . . . . . . . . . . . . . . . 17 2.2.3 Hướng tiếp cận lai . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.4 Thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 iii 2.3 Đề xuất hướng tiếp cận lai ngữ nghĩa biểu diễn môi trường . . . . . . . 22 2.4 Phương pháp xây dựng bản đồ môi trường . . . . . . . . . . . . . . . . 23 2.4.1 Xây dựng bản đồ số liệu . . . . . . . . . . . . . . . . . . . . . . 23 2.4.1.1 Phương pháp đo hành trình bằng hình ảnh sử dụng mô hình không chắc chắn . . . . . . . . . . . . . . . . . . 24 2.4.1.2 Thích nghi VO cho môi trường trong nhà . . . . . . . 27 2.4.2 Xây dựng bản đồ topo . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.2.1 Giải thuật FAB-MAP . . . . . . . . . . . . . . . . . . 30 2.4.2.2 Thích nghi và cải thiện FAB-MAP xây dựng bản đồ topo 39 2.4.3 Bổ sung thông tin đối tượng vật cản tĩnh trên bản đồ . . . . . . 44 2.5 Phương pháp định vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.6 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.6.1 Môi trường đánh giá . . . . . . . . . . . . . . . . . . . . . . . . 45 2.6.2 Thu thập dữ liệu đánh giá . . . . . . . . . . . . . . . . . . . . . 46 2.6.2.1 Hệ thống thu thập dữ liệu . . . . . . . . . . . . . . . . 46 2.6.2.2 Thu thập dữ liệu . . . . . . . . . . . . . . . . . . . . . 47 2.6.3 Kết quả đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.6.3.1 Đánh giá phương pháp xây dựng bản đồ số liệu . . . . 48 2.6.3.2 Đánh giá phương pháp định vị hình ảnh . . . . . . . . 53 2.7 Kết luận chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3 PHÁT HIỆN VÀ ƯỚC LƯỢNG KHOẢNG CÁCH VẬT CẢN 60 3.1 Định nghĩa bài toán và các thách thức . . . . . . . . . . . . . . . . . . 60 3.2 Những nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . 61 3.2.1 Các phương pháp sử dụng 01 camera . . . . . . . . . . . . . . . 61 3.2.1.1 Hướng nghiên cứu sử dụng stereo camera . . . . . . . 62 3.2.1.2 Hướng nghiên cứu sử dụng cảm biến Kinect . . . . . . 64 3.2.1.3 Phân tích và đánh giá các phương pháp . . . . . . . . 65 3.3 Đề xuất phương pháp phát hiện và ước lượng khoảng cách . . . . . . . 66 3.4 Phát hiện vật cản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.4.1 Phát hiện vật cản cố định . . . . . . . . . . . . . . . . . . . . . 67 3.4.1.1 Đối sánh các điểm đặc trưng . . . . . . . . . . . . . . 68 3.4.1.2 Phát hiện vật cản từ kết quả đối sánh . . . . . . . . . 71 3.4.1.3 Xác định vùng chứa đối tượng . . . . . . . . . . . . . . 74 3.4.2 Phát hiện vật cản động . . . . . . . . . . . . . . . . . . . . . . . 75 3.4.2.1 Trích chọn đặc trưng HoG . . . . . . . . . . . . . . . . 75 3.4.2.2 Bộ phân loại SVM . . . . . . . . . . . . . . . . . . . . 76 3.5 Uớc lượng khoảng cách vật cản . . . . . . . . . . . . . . . . . . . . . . 77 3.5.1 Nguyên lý ước lượng khoảng cách . . . . . . . . . . . . . . . . . 77 iv 3.5.2 Xây dựng bản đồ chênh lệch . . . . . . . . . . . . . . . . . . . . 79 3.5.2.1 Thu thập dữ liệu . . . . . . . . . . . . . . . . . . . . . 80 3.5.2.2 Hiệu chỉnh hình ảnh . . . . . . . . . . . . . . . . . . . 80 3.5.2.3 Đối sánh hình ảnh . . . . . . . . . . . . . . . . . . . . 84 3.5.2.4 Tính toán độ sâu . . . . . . . . . . . . . . . . . . . . . 86 3.6 Kết quả đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.6.1 Xây dựng cơ sở dữ liệu vật cản . . . . . . . . . . . . . . . . . . 88 3.6.2 Đánh giá giải thuật phát hiện đối tượng . . . . . . . . . . . . . 90 3.6.3 Đánh giá giải thuật ước lượng khoảng cách vật cản . . . . . . . 93 3.7 Kết luận chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4 PHÁT TRIỂN VÀ THỬ NGHIỆM HỆ THỐNG DẪN ĐƯỜNG 99 4.1 Hệ thống tích hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.1.1 Tích hợp phần cứng . . . . . . . . . . . . . . . . . . . . . . . . 99 4.1.2 Kiến trúc tổng thể . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.2 Phát triển hệ thống dẫn đường sử dụng robot . . . . . . . . . . . . . . 102 4.2.1 Tìm đường cho robot . . . . . . . . . . . . . . . . . . . . . . . . 102 4.2.2 Điều khiển robot . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.2.2.1 Điều khiển trực tiếp dựa trên đường đi xác định . . . . 103 4.2.2.2 Điều khiển theo dự báo và hiệu chỉnh vị trí của bộ lọc Kalman . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.2.3 Tương tác người-robot . . . . . . . . . . . . . . . . . . . . . . . 111 4.3 Thử nghiệm và đánh giá hệ thống dẫn đường . . . . . . . . . . . . . . 112 4.3.1 Môi trường và quy trình thử nghiệm . . . . . . . . . . . . . . . 112 4.3.1.1 Môi trường thử nghiệm . . . . . . . . . . . . . . . . . 112 4.3.1.2 Quy trình thử nghiệm . . . . . . . . . . . . . . . . . . 115 4.3.2 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 116 4.3.2.1 Đánh giá khả năng xác định vị trí xuất phát của robot 116 4.3.2.2 Đánh giá khả năng điều khiển robot . . . . . . . . . . 117 4.3.2.3 Đánh giá khả năng tương tác người-robot . . . . . . . 119 4.3.2.4 Đánh giá hệ thống dẫn đường trợ giúp NKT bằng robot 121 4.3.3 Bàn luận hệ thống robot dẫn đường . . . . . . . . . . . . . . . . 130 4.4 Kết luận chương 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 133 TÀI LIỆU THAM KHẢO 136 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 148 PHỤ LỤC 151 v A MỘT SỐ PHƯƠNG PHÁP TRÍCH CHỌN ĐẶC TRƯNG 151 A.1 Đặc trưng Harris Corner . . . . . . . . . . . . . . . . . . . . . . . . . . 151 A.2 Đặc trưng SIFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A.3 Đặc trưng SURF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 A.4 Đặc trưng GIST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 A.5 Đặc trưng HoG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 A.6 Đặc trưng Haar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 B ĐÁNH GIÁ HIỆU NĂNG NHẬN DẠNG TRÊN MỘT SỐ CSDL 173 B.1 Giới thiệu 3 CSDL thử nghiệm . . . . . . . . . . . . . . . . . . . . . . 173 B.2 Khung nhận dạng đối tượng tổng quát . . . . . . . . . . . . . . . . . . 177 B.3 Độ đo đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 B.4 Kết quả đánh giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 C THIẾT KẾ HỆ THỐNG THU THẬP DỮ LIỆU 188 C.1 Xe camera thu thập dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . 188 C.2 Hiệu chỉnh camera góc rộng . . . . . . . . . . . . . . . . . . . . . . . . 191 C.3 Robot PC-Bot914 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 vi DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT TT Viết tắt Nghĩa đầy đủ (tiếng Việt/tiếng Anh) 1 AM Appearance based Mapping 2 AP Average Precision 3 BOW Bag of Words 4 CSDL Cơ sở dữ liệu 5 ED Euclidean Distance 6 FAB-MAP Fast Appearance Based Mapping 7 FLANN Fast Library for Approximate Nearest Neighbors 8 FN False Negative 9 FP False Positive 10 GPS Global Positioning System 11 HOG Histogram of Oriented Gradients 12 HSI Hue Saturation and Intensity 13 KF Kalman Filter 14 KH&CN Khoa học và Công nghệ 15 k-NN K-Nearest Neighbors 16 LASER Light Amplification by Stimulated Emission of Radiation 17 LATS Luận án tiến sĩ 18 LIDAR Light Detection And Ranging 19 MICA Multimedia, Information, Communication & Applications 20 MUT Motion Uncertainty Tetragon 21 NCS Nghiên cứu sinh 22 NĐC Nguyễn Đình Chiểu 23 NKT Người khiếm thị 24 PUT Perspective Uncertainty Tetragons 25 RANSAC RANdom SAmple Consensus 26 RFID Radio Frequency Identification 27 RGB Red Green and Blue 28 RMSE Root Mean Square Error 29 SAD Sum of Absolute Differences 30 SIFT Scale Invariant Feature Transforms 31 SLAM Simultaneous Localization and Mapping 32 SURF Speeded Up Robust Features 33 SVM Support Vector Machine 34 TP True Positive 35 TQB Tạ Quang Bửu 36 VO Visual Odometry 37 WIFI Wireless Fidelity vii DANH MỤC CÁC BẢNG Bảng 2.1 Bảng tổng hợp thông tin về 03 môi trường thử nghiệm . . . . . . 46 Bảng 2.2 Tốc độ lấy mẫu (fps) của các camera tại các môi trường thử nghiệm 47 Bảng 2.3 Dữ liệu thu thập tại E1:NĐC . . . . . . . . . . . . . . . . . . . . 47 Bảng 2.4 Dữ liệu thu thập tại E2:TQB . . . . . . . . . . . . . . . . . . . . 47 Bảng 2.5 Dữ liệu thu thập tại E3:MICA . . . . . . . . . . . . . . . . . . . 47 Bảng 2.6 Kết quả đánh giá RMSE tại E1:NĐC . . . . . . . . . . . . . . . . 48 Bảng 2.7 Kết quả đánh giá độ sai số tiêu chuẩn RMSE tại E2:TQB . . . . 50 Bảng 2.8 Kết quả đánh giá độ sai số tiêu chuẩn RMSE tại E3:MICA . . . . 52 Bảng 2.9 So sánh khả năng định vị của giải thuật FAB-MAP* tại E1:NĐC 54 Bảng 2.10 Kết quả đánh giá so sánh giải thuật định vị FAB-MAP* tại E2:TQB 56 Bảng 2.11 Kết quả đánh giá so sánh giải thuật định vị FAB-MAP* tại E3:MICA 57 Bảng 3.1 Kết quả thu nhận dữ liệu khung cảnh/đường đi phục vụ đánh giá 88 Bảng 3.2 Thu thập dữ liệu đánh giá phát hiện và ước lượng khoảng cách vật cản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Bảng 3.3 Kết quả phát hiện đối tượng theo phương pháp đề xuất . . . . . 91 Bảng 3.4 Kết quả phát đánh giá so sánh với phương pháp Haar-AdaBoost 91 Bảng 3.5 Kết quả dự đoán độ sai số ước lượng khoảng cách vật cản . . . . 93 Bảng 4.1 Danh sách tham gia thử nghiệm dẫn đường tại E1:NĐC . . . . . 112 Bảng 4.2 Danh sách tham gia đánh giá hệ thống dẫn đường tại E2:TQB . 113 Bảng 4.3 Danh sách tham gia đánh giá hệ thống dẫn đường tại E3:MICA . 114 Bảng 4.4 Kết quả đánh giá điểm xuất phát của robot . . . . . . . . . . . . 117 Bảng 4.5 Kết quả đánh giá vai trò lọc Kalman trong điều khiển robot . . . 118 Bảng 4.6 Kết quả sai số định vị sử dụng sai số trung vị . . . . . . . . . . . 118 viii Bảng 4.7 Kết quả sai số định vị sử dụng sai số trung bình . . . . . . . . . . 119 Bảng 4.8 Bảng câu hỏi phỏng vấn trước và sau khi sử dụng hệ thống . . . 119 Bảng 4.9 Tổng hợp kết quả tần số rung (Hz) phản hồi thông tin môi trường 121 Bảng 4.10 Kết quả đánh giá độ sai số RMSE khi robot chuyển động tịnh tiến 122 Bảng 4.11 Kết quả đánh giá hiệu năng robot dẫn đường chuyển động tịnh tiến122 Bảng 4.12 Kết quả đánh giá robot dẫn đường chuyển động tịnh tiến . . . . 123 Bảng 4.13 Kết quả đánh giá độ sai số RMSE với kịch bản robot chuyển động tịnh tiến và quay tại E1:NĐC . . . . . . . . . . . . . . . . . . . . . . . 123 Bảng 4.14 Kết quả robot dẫn đường chuyển động quay và tịnh tiến tại E1:NĐC124 Bảng 4.15 Đánh giá các lần thử nghiệm hệ thống dẫn đường tại E1:NĐC . . 125 Bảng 4.16 Kết quả sai số RMSE robot phát hiện vật cản xuất hiện bất ngờ tại E1:NĐC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 Bảng 4.17 Kết quả đánh giá hiệu năng dẫn đường robot phát hiện vật cản . 126 Bảng 4.18 Kết quả đánh giá robot dẫn đường chuyển động quay và tịnh tiến 127 Bảng 4.19 Kết quả đánh giá độ sai số RMSE tại E2:TQB . . . . . . . . . . 127 Bảng 4.20 Kết quả đánh giá hiệu năng dẫn đường robot tại E2:TQB . . . . 128 Bảng 4.21 Tổng hợp kết quả robot dẫn đường tại E2:TQB . . . . . . . . . . 129 Bảng 4.22 Kết quả đánh giá độ sai số RMSE tại E3:MICA . . . . . . . . . . 129 Bảng 4.23 Kết quả đánh giá hiệu năng dẫn đường của robot tại E3:MICA . 129 Bảng 4.24 Tổng hợp kết quả robot dẫn đường tại E3:MICA . . . . . . . . . 130 Bảng 4.25 Bảng tổng hợp thông số kỹ thuật . . . . . . . . . . . . . . . . . . 131 Bảng B.1 Quy định thang tính điểm phần thi nhận dạng RobotVision2013 182 Bảng B.2 Kết quả nhận dạng tượng CSDL Naiscorp 2012 . . . . . . . . . . 183 Bảng B.3 Kết quả điểm nhận dạng đối tượng CSDL Robot Vision 2013 . . 185 ix DANH MỤC CÁC HÌNH ẢNH, ĐỒ THỊ Hình 1.1 Các thành phần chính của hệ thống đề xuất Robot trợ giúp NKT 13 Hình 2.1 Mô hình biểu diễn môi trường theo hướng tiếp cận lai ngữ nghĩa . 22 Hình 2.2 Minh họa di chuyển của robot với vận tốc v và góc lái α . . . . . 24 Hình 2.3 Các bước giải thuật đo hành trình bằng thông tin hình ảnh VO . 25 Hình 2.4 Một số trường hợp lỗi tích lũy khi xây dựng bản đồ . . . . . . . . 26 Hình 2.5 Một số cấu trúc mặt nền thử nghiệm thuật toán VO . . . . . . . 27 Hình 2.6 Tạo các điểm đánh dấu dọc hành trình . . . . . . . . . . . . . . . 28 Hình 2.7 Minh họa số điểm đặc trưng phát hiện trên mặt sàn . . . . . . . . 28 Hình 2.8 Minh họa phương pháp thử nghiệm khi tạo các mẫu đánh dấu . . 29 Hình 2.9 Các bước của giải thuật FAB-MAP [29] . . . . . . . . . . . . . . 30 Hình 2.10 Xây dựng từ điển và biểu diễn quan sát theo mô hình túi từ . . . 32 Hình 2.11 Một số những thách thức khi nhận dạng vị trí trong môi trường . 33 Hình 2.12 Cây nhị phân Chow liu theo hướng đồ thị có hướng . . . . . . . . 34 Hình 2.13 Biểu diễn các quan sát cùng xuất hiện tại một thời điểm . . . . . 34 Hình 2.14 Biểu diễn vị trí Li thành phần quan sát eq và quan sát có nhiễu zq 35 Hình 2.15 Xác định khung cảnh phân biệt: (a) Chuỗi hình ảnh khung cảnh; (b) Khung cảnh đại diện . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Hình 2.16 Xác định các khung cảnh có cấu trúc giống nhau . . . . . . . . . 41 Hình 2.17 Minh họa các bước trích chọn đặc trưng GIST . . . . . . . . . . . 42 Hình 2.18 Minh họa kết quả loại bỏ khung cảnh có cấu trúc giống nhau . . 42 Hình 2.19 Minh họa các bước thực hiện giải thuật FAB-MAP* . . . . . . . . 43 Hình 2.20 Minh họa bước thực hiện cập nhật điểm mốc quan trọng . . . . . 44 Hình 2.21 Mô hình định vị sử dụng thông tin hình ảnh sử dụng robot . . . . 45 x Hình 2.22 Hệ thống thu thập dữ liệu . . . . . . . . . . . . . . . . . . . . . . 46 Hình 2.23 Biểu đồ so sánh RMSE giữa VO và VO* tại E1:NĐC . . . . . . . 49 Hình 2.24 Minh họa giá trị ngưỡng θV O quyết định số điểm đặc trưng . . . . 49 Hình 2.25 Kết quả xây dựng bản đồ sử dụng VO và VO* tại E1:NĐC . . . . 50 Hình 2.26 Biểu đồ so sánh RMSE giữa VO và VO* tại E2:TQB . . . . . . . 51 Hình 2.27 Kết quả xây dựng bản đồ sử dụng VO và VO* tại E2:TQB . . . . 51 Hình 2.28 Biểu đồ so sánh sai số RMSE giữa VO và VO* tại E3:MICA . . . 52 Hình 2.29 Kết quả xây dựng bản đồ sử dụng VO và VO* tại E3:MICA . . . 53 Hình 2.30 Biểu đồ so sánh giải thuật định vị FAB-MAP* tại E1:NĐC . . . . 55 Hình 2.31 Minh họa kết quả định vị FAB-MAP* tại E1:NĐC . . . . . . . . 55 Hình 2.32 Biểu đồ so sánh giải thuật định vị FAB-MAP* tại E2:TQB . . . . 56 Hình 2.33 Minh họa kết quả định vị FAB-MAP* tại E2:TQB . . . . . . . . 57 Hình 2.34 Biểu đồ so sánh hai phương pháp định vị FAB-MAP* tại E3:MICA 58 Hình 2.35 Minh họa kết quả định vị giải thuật FAB-MAP* tại E3:MICA . . 58 Hình 3.1 Định nghĩa bài toán phát hiện và ước lượng khoảng cách . . . . . 61 Hình 3.2 Mô hình phát hiện và ước lượng khoảng cách vật cản . . . . . . . 66 Hình 3.3 Sơ đồ các bước thực hiện phát hiện vật cản cố định . . . . . . . . 68 Hình 3.4 Kết quả trích chọn đặc trưng SIFT . . . . . . . . . . . . . . . . . 69 Hình 3.5 Minh họa giải thuật đối sánh các điểm đặc trưng . . . . . . . . . 70 Hình 3.6 Kết quả đối sánh các điểm đặc trưng phát hiện . . . . . . . . . . 70 Hình 3.7 Kết quả loại bỏ một số cặp điểm đối sánh (matching) yếu . . . . 71 Hình 3.8 Lưu đồ giải thuật tính ma trận H . . . . . . . . . . . . . . . . . . 72 Hình 3.9 Minh họa kết quả xác định vùng chứa đối tượng . . . . . . . . . . 74 Hình 3.10 Sơ đồ các bước phát hiện người sử dụng HoG-SVM . . . . . . . . 75 Hình 3.11 Mô hình ước lượng khoảng cách vật cản từ hai quan sát . . . . . 77 Hình 3.12 Hình ảnh của đối tượng (cây) quan sát từ hai góc thu nhận . . . 78 xi Hình 3.13 Sơ đồ các bước tính bản đồ chênh lệch và ước lượng khoảng cách 80 Hình 3.14 Minh họa hai quan sát khi camera chuyển động . . . . . . . . . . 81 Hình 3.15 Kết quả tìm đường eplipolar trên mô hình camera chuyển động . 82 Hình 3.16 Minh họa hiệu chỉnh hình ảnh trên cùng mặt phẳng ngang . . . . 82 Hình 3.17 Kết quả hiệu chỉnh hình ảnh . . . . . . . . . . . . . . . . . . . . . 84 Hình 3.18 Dò tìm khối dữ liệu trên hai ảnh được hiệu chỉnh . . . . . . . . . 85 Hình 3.19 Kết quả đối sánh ảnh sử dụng giải thuật SAD . . . . . . . . . . . 85 Hình 3.20 Minh họa phương pháp tính bản độ chênh lệch . . . . . . . . . . 86 Hình 3.21 Kết quả phát hiện & ước lượng khoảng cách vật cản trên ảnh độ sâu 87 Hình 3.22 Minh họa hình ảnh thu nhận dữ liệu tại khung hình 289 . . . . . 88 Hình 3.23 Minh họa chuẩn bị dữ liệu đánh giá phát hiện đối tượng . . . . . 89 Hình 3.24 Minh họa phương pháp đo khoảng cách vị trí vật cản trên thực địa 89 Hình 3.25 Biểu đồ đánh giá so sánh hai phương pháp phát hiện đối tượng . 92 Hình 3.26 Một số hình ảnh phát hiện đối tượng của hai phương pháp. Hình chữ nhật màu xanh là kết quả phát hiện bằng tay, màu đỏ là kết quả phát hiện tự động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Hình 3.27 Các vị trí phát hiện và dự đoán khoảng cách thuộc lớp Chậu hoa 94 Hình 3.28 Minh họa dự đoán khoảng cách lớp đối tượng chậu hoa . . . . . . 94 Hình 3.29 Các vị trí phát hiện và dự đoán khoảng cách thuộc lớp Bình cứu hỏa 95 Hình 3.30 Minh họa dự đoán khoảng cách lớp đối tượng bình cứu hỏa . . . . 95 Hình 3.31 Các vị trí phát hiện và dự đoán khoảng cách thuộc lớp thùng rác 96 Hình 3.32 Minh họa dự đoán khoảng cách lớp đối tượng thùng rác . . . . . 96 Hình 3.33 Các vị trí phát hiện và dự đoán khoảng cách thuộc lớp người . . . 97 Hình 3.34 Minh họa dự đoán khoảng cách lớp đối tượng người . . . . . . . . 97 Hình 4.1 Tích hợp các thiết bị phần cứng lên robot . . . . . . . . . . . . . 100 Hình 4.2 Mô hình tổng quát của hệ thống đề xuất . . . . . . . . . . . . . . 101 Hình 4.3 Minh họa đường đi từ hai điểm biết trước trên bản đồ môi trường 103 xii Hình 4.4 Lược đồ điều khiển robot . . . . . . . . . . . . . . . . . . . . . . 104 Hình 4.5 Các bước tính toán chính của giải thuật của lọc Kalman . . . . . 106 Hình 4.6 Minh họa các bước điều khiển sử dụng lọc Kalman . . . . . . . . 107 Hình 4.7 Lược đồ điều khiển robot sử dụng lọc Kalman . . . . . . . . . . . 109 Hình 4.8 Minh họa tương tác giữa người-robot . . . . . . . . . . . . . . . 111 Hình 4.9 Bản đồ tầng 2 khu nội trú Trường THCS Nguyễn Đình Chiểu . . 112 Hình 4.10 Bản đồ thử nghiệm robot dẫn đường hành lang tầng 5 tại E2:TQB 113 Hình 4.11 Kịch bản thử nghiệm robot dẫn đường tại E3:MICA . . . . . . . 114 Hình 4.12 Kết quả đánh giá việc xác định vị trí xuất phát của robot . . . . 116 Hình 4.13 Vai trò của lọc Kalman trong điều khiển robot . . . . . . . . . . . 117 Hình 4.14 Một số học sinh khiếm thị tham gia đánh giá tương tác người-robot120 Hình 4.15 Thử nghiệm các tần số rung trên điện thoại di động với NKT . . 121 Hình 4.16 Một số hình ảnh robot chuyển động tịnh tiến tại E1-NĐC . . . . 122 Hình 4.17 Hình ảnh thử nghiệm robot dẫn đường gặp sự cố tại E1-NĐC . . 123 Hình 4.18 Minh họa robot chuyển động quay và tịnh tiến tại E1:NĐC . . . . 124 Hình 4.19 Một số hình ảnh robot chuyển động quay và tịnh tiến tại E1-NĐC 125 Hình 4.20 Kịch bản robot phát hiện vật cản tại E1:NĐC . . . . . . . . . . . 126 Hình 4.21 Minh họa trường hợp vật cản xuất hiện bất ngờ E1:NĐC . . . . . 127 Hình 4.22 Minh họa hình ảnh robot dẫn đường tại E2:TQB . . . . . . . . . 128 Hình 4.23 Minh họa hình ảnh robot dẫn đường tại E3:MICA . . . . . . . . . 130 Hình 4.24 Lược đồ thời gian trung bình vận hành điều khiển robot dẫn đường131 Hình 4.25 Một số hình ảnh trong phóng sự “cuộc sống tươi” đẹp phát trên kênh VTV4 - Đài truyền hình Việt Nam . . . . . . . . . . . . . . . . . 149 Hình A.1 Minh họa phát hiện các điểm đặc trưng Harris-Corner . . . . . . 151 Hình A.2 Một số trường hợp phát hiện đặc trưng Harris-Corner . . . . . . . 152 Hình A.3 Một số trường hợp phát hiện đặc trưng Harris-Corner . . . . . . . 152 xiii Hình A.4 Minh họa đặc trưng biểu diễn các điểm đặc biệt trong ảnh . . . . 154 Hình A.5 Mô tả tạo bộ mô tả các điểm đặc trưng (nguồn [87]) . . . . . . . 157 Hình A.6 Minh họa đặc trưng SURF biểu diễn các điểm đặc biệt trong ảnh 158 Hình A.7 Minh họa xấp xỉ đạo hàm cấp 2 hàm Gaussian [5] . . . . . . . . . 158 Hình A.8 Minh họa giảm không gian không gian trong biểu diễn đặc trưng 159 Hình A.9 Minh họa các điểm quan tâm được phát hiện quanh tâm . . . . . 160 Hình A.10 Phép lọc Haar wavelet: x (trái) và y hướng (phải). Vùng đen trọng số -1 và vùng trắng trọng số +1 . . . . . . . . . . . . . . . . . . . . . . 161 Hình A.11 Gán hướng: một cửa sổ kích thước pi 3 . . . . . . . . . . . . . . . . 161 Hình A.12 Xác định ô 4× 4 hình vuông con xung quanh điểm đặc trưng . . 162 Hình A.13 Các mô tả của miền đại diện cho tính chất của mẫu . . . . . . . . 163 Hình A.14 Một số trường hợp so khớp giữa các đặc trưng . . . . . . . . . . . 163 Hình A.15 Minh họa các tính chất của khung cảnh . . . . . . . . . . . . . . 164 Hình A.16 Bộ lọc Gabor 4 tỉ lệ, 8 hướng . . . . . . . . . . . . . . . . . . . . 165 Hình A.17 Minh họa quá trình trích chọn đặc trưng HoG . . . . . . . . . . . 166 Hình A.18 Thứ tự các Histogram với các góc khác nhau (0o đến 180o) . . . . 167 Hình A.19 Hai loại hình học khối chính của đặc trưng HoG . . . . . . . . . . 168 Hình A.20 Ví dụ minh họa các bước trích chọn đặc trưng HoG . . . . . . . . 169 Hình A.21 Tính góc và biên độ theo Gradient-X và Gradient-Y . . . . . . . . 169 Hình A.22 Một số ứng dụng phát hiện đối tượng sử dụng đặc trưng Haar . . 170 Hình A.23 Các kiểu cơ bản của đặc trưng Haar . . . . . . . . . . . . . . . . 171 Hình A.24 Cách tính tổng các điểm ảnh trong một hình chữ nhật bất kì . . . 171 Hình B.1 Minh họa cơ sở dữ liệu Robot Vision 2013 . . . . . . . . . . . . . 173 Hình B.2 Minh họa 20 lớp đối tượng trong Pascal VOC . . . . . . . . . . . 174 Hình B.3 Những khó khăn thách thưc trên 3 CSDL đề xuất . . . . . . . . . 175 Hình B.4 Các lớp đối tượng trong CSDL Naicorp 2012 . . . . . . . . . . . . 176 xiv Hình B.5 Khung làm việc tổng quát phát hiện và nhận dạng đối tượng . . . 177 Hình B.6 Minh họa giải thuật Adaboost . . . . . . . . . . . . . . . . . . . . 178 Hình B.7 Mô hình phân tầng CascadeAdaboost . . . . . . . . . . . . . . . . 179 Hình B.8 Siêu phẳng tách với khoảng cách lề cực đại SVM . . . . . . . . . 180 Hình B.9 Phân tách theo siêu phẳng (w,b) trong không gian 2 chiều tập mẫu 181 Hình B.10 Minh họa các bước tính toán k-NN . . . . . . . . . . . . . . . . . 181 Hình B.11 Một số kết quả nhận dạng đúng/sai CSDL Naicorp 2012 . . . . . 184 Hình B.12 Một số kết quả nhận dạng đúng/sai CSDL RobotVision2013 . . . 184 Hình B.13 Đồ thị AP của 20 lớp đối tượng CSDL PascalVOC 2007 . . . . . 186 Hình B.14 Đồ thị AP từng lớp đối tượng CSDL PascalVOC 2007 . . . . . . 186 Hình B.15 Kết quả nhận dạng đối tượng trong CSDL Pascal VOC 2007 . . . 187 Hình B.16 Kết quả nhận dạng đối tượng trong CSDL Pascal VOC 2007 . . . 187 Hình C.1 Một số giải pháp thu thập dữ liệu từ 2 camera . . . . . . . . . . . 188 Hình C.2 Một số lỗi khi xây dựng bản đồ tại môi trường trong nhà . . . . . 189 Hình C.3 Một số lỗi khi xây dựng bản đồ tại môi trường ngoài trời . . . . . 189 Hình C.4 Thiết kế xe camera thu thập dữ liệu . . . . . . . . . . . . . . . . 190 Hình C.5 Mô hình thu nhận ảnh của camera . . . . . . . . . . . . . . . . . 191 Hình C.6 Các loại biến dạng khi thu nhận ảnh . . . . . . . . . . . . . . . . 192 Hình C.7 Quá trình hiệu chỉnh méo hình ảnh từ camera góc nhìn rộng . . . 193 Hình C.8 Các phiên bản của robot PC-Bot 914 . . . . . . . . . . . . . . . . 194 Hình C.9 Vị trí lắp các cảm biển hồng ngoại IR . . . . . . . . . . . . . . . 195 Hình C.10 Cơ cấu bánh xe điều khiển của robot PC-Bot 914 . . . . . . . . . 195 xv MỞ ĐẦU Tính cấp thiết, ý nghĩa khoa học của luận án Năm 2013, theo công bố của Tổ chức Y tế thế giới (WHO) trên thế giới có khoảng 285 triệu người suy giảm thị lực, trong đó 246 triệu người có thị lực kém ở mức độ vừa phải đến mức độ nặng và 39 triệu người mù [107]. Tại Việt Nam, theo số liệu của Viện mắt Trung ương cung cấp, có khoảng 1.2 triệu NKT, trong đó 820.503 người không còn khả năng nhìn thấy ánh sáng. Nếu tính cả những người bị các tật về mắt như cận hoặc viễn thì con số này còn lớn hơn rất nhiều. Số lượng NKT lớn, bản thân NKT gặp nhiều khó khăn trong cuộc sống cũng như nắm bắt các cơ hội việc làm. Chính vì vậy, trợ giúp NKT là vấn đề thu hút sự quan tâm của nhiều nhà khoa học trong thời gian gần đây. Trong số các yêu cầu trợ giúp, trợ giúp định hướng là cần thiết và chỉ dẫn để giúp họ tránh các vật cản trên đường đi hay đưa ra các thông báo về môi trường xung quanh. Trên thực tế, nhiều phương pháp đã được nghiên cứu và triển khai nhằm hỗ trợ định hướng cho NKT, như sử dụng gậy [32], chó dẫn đường [32], hay thiết bị điện tử [14]. Mỗi phương pháp có những ưu nhược điểm riêng: gậy dẫn đường bị hạn chế phạm vi phát hiện vật cản theo kích thước của gậy; chó dẫn đường thường có chi phí cao và gây trở ngại về tâm sinh lý đối với người dùng; thiết bị điện tử như các điện cực đặt trên lưỡi có thể gây tâm lý ngại ngần khi sử dụng. Trong bối cảnh này, nghiên cứu và phát triển một hệ thống trợ giúp dẫn đường hiệu quả và thân thiện trợ giúp NKT vẫn là chủ đề đầy thách thức, động lực để NCS thực hiện đề tài: “Nghiên cứu phát triển một số kỹ thuật định vị dựa trên hình ảnh, ứng dụng trợ giúp dẫn đường cho người khiếm thị”. Mục tiêu và những thách thức Xuất phát từ ý tưởng tạo ra một hệ thống hỗ trợ giống như một người bạn đồng hành có khả năng giao tiếp thân thiện và hiệu quả. Luận án hướng đến phát triển một hệ thống trợ giúp định hướng và cảnh báo vật cản cho NKT sử dụng robot di động. Để đạt được mục tiêu này, robot cần có khả năng nhận biết và di chuyển giữa các vị trí trong môi trường và nhận dạng được các vật cản trên đường đi. Do vậy, chúng tôi chia các mục tiêu đạt được thành ba bài toán cụ thể: 1 1. Biểu diễn môi trường và định vị: Với mục tiêu dẫn đường cho NKT đi từ vị trí hiện tại đến vị trí mong muốn trong môi trường, robot phải biết mình đang ở đâu trong môi trường và đường đi đến vị trí đích như thế nào. Để giải quyết vấn đề này, bản đồ môi trường phải được xây dựng từ trước và robot phải có khả năng định vị từ một vị trí bất kỳ trên bản đồ. Mặc dù có nhiều phương pháp đã được đề xuất, hướng tiếp cận tổng quát và bền vững với các yếu tố môi trường đang là những mục tiêu mà...thứ hai chỉ cho phép dẫn hướng cho robot nhưng không cho phép tìm đường đi giữa hai vị trí trong môi trường. Trong khi ngữ cảnh bài toán đặt ra là robot dẫn đường từ hai vị trí biết trước, vì vậy phải có một bản đồ môi trường được xây dựng ở pha ngoại tuyến và được sử dụng ở pha trực tuyến để định vị và tìm đường. Trong khuôn khổ luận án, chúng tôi đi theo hướng tiếp cận xây dựng bản đồ môi trường ở pha ngoại tuyến và định vị sử dụng nguồn thông tin hình ảnh thu thập được từ camera. Ưu điểm chính của việc sử dụng camera là giá thành rẻ hơn rất nhiều so với các cảm biến khác trong khi cung cấp nguồn thông tin hình ảnh có giá trị phục vụ cho nhiều bài toán khác nhau như xây dựng bản đồ, định vị và phát hiện vật cản. 14 Đặc biệt có thể sử dụng các thiết bị thông thường để thu thu thập xử lý dữ liệu như camera cầm tay, camera gắn trên điện thoại hay camera mạng có vùng quan sát rộng. Sử dụng camera dễ lắp đặt và triển khai ở các môi trường khác nhau như trong nhà hay ngoài trời. Tuy nhiên việc sử dụng camera phải đối mặt với nhiều thách thức như đòi hỏi tính toán lớn vì bản thân cảm biến không cho phép xác định một cách trực tiếp đối tượng quan tâm; chuyển động của robot không chính xác, độ phức tạp và biến động của môi trường, yêu cầu đáp ứng thời gian thực. 2.2 Những nghiên cứu liên quan Phần dưới đây chúng tôi chia các hướng tiếp cận biểu diễn môi trường theo ba nhóm: i) hướng tiếp cận sử dụng bản đồ số liệu; ii) hướng tiếp cận sử dụng bản đồ topo; iii) hướng tiếp cận lai. 2.2.1 Hướng tiếp cận sử dụng bản đồ số liệu Bản đồ số liệu loại bản đồ mô tả thế giới theo khoảng cách (theo đơn vị mét); khoảng cách trên bản đồ tương ứng với khoảng cách trên thế giới thực. Các loại bản đồ số liệu chia thành hai nhóm chính [65]: bản đồ lưới (grid map) và bản đồ đặc trưng (feature map). − Bản đồ dựa theo đặc trưng: thường được sử dụng bởi các nhà nghiên cứu trong lĩnh vực robot di động. Ý tưởng cơ bản của hướng tiếp cận là sử dụng các đặc trưng như tường, góc, cạnh trong không gian để tái tạo lại bản đồ thường được sử dụng trong bài toán điều khiển, tự động định vị và xây dựng bản đồ môi trường được phát triển trong thời gian khá dài. Phần dưới đây là các nghiên cứu tiêu biểu John Leonard và đồng nghiệp 1991 [83] trình bày phương pháp vừa định vị vừa xây dựng bản đồ môi trường sử dụng tường và góc cạnh là đặc trưng biểu diễn. Robot di động được trang bị cảm biến siêu âm thu thập thông tin môi trường phục vụ cho việc xây dựng bản đồ từ vị trí robot đến các vị trí tiếp theo trên hành trình di chuyển. W.D Rencken 1994 [116] đề xuất phương pháp sử dụng cảm biến siêu âm tự động điều hướng trong môi trường không có cấu trúc, và không biết sử dụng robot. Bản đồ môi trường được xây dựng nhờ vào các đặc trưng của môi trường như góc, cạnh và mặt sàn. Với mô hình robot sử dụng bộ lọc Kalman mở rộng đề cập nhật và dự đoán vị trí của nó trên bản đồ. Các cảm biến siêu âm sẽ trả về giá trị đo lường, đối với mỗi lần đo có nhiều cách cách biểu diễn như: đặc trưng đã 15 biết của mặt sàn, góc, cạnh; đặc trưng không biết của mặt sàn, góc, cạnh; đặc trưng không phân loại được. Robot điều khiển di chuyển xung quanh một văn phòng có cấu trúc không đổi bên trong là bàn ghế, vách ngăn. Robot di chuyển với tốc độ 12cm/s, thời gian tính toán là 1.5 giây thực hiện định vi với độ sai số là 2.66m. Jorge Gasós và Alejandro Martín 1996 [51] đề xuất giải thuật hệ mờ xây dựng bản đồ cho robot di động sử dụng thông tin thu thập từ cảm siêu âm để phác thảo môi trường bằng việc tính toán xấp xỉ đa giác 2D. Hệ mờ sử dụng để đại diện cho sự không chắc chắn về các vị trí ranh giới thực sự của đối tượng. Phần thực nghiệm được triển khai biểu diễn bản đồ trong môi trường văn phòng chứa các tập đối tượng như bàn, vách ngăn, ô làm việc, kệ để sách, máy in, bàn làm việc, ghế. Dulimart 1997 [40] trình bày sử dụng bản đồ môi trường dựa theo đặc trưng là biển số của cửa và ánh sáng đèn trần nhằm xây dựng bài toán định vị robot di dộng trong nhà. Phần thử nghiệm được tiến hành đánh giá trên 3 tầng của tòa nhà cho robot chuyển động 0.3-0.4m/s thu nhận hình từ camera gắn trên robot xử lý theo mô hình máy chủ/máy trạm. Kết quả độ sai số định vị từ 0.6-1m, thời gian phát hiện biển số cửa và đèn 50ms/ảnh. − Bản đồ lưới: được định nghĩa là bản đồ 2D trong đó không gian được chia thành lưới các ô có kích thước nhất định. Tọa độ của các ô trên lưới được xác định theo một hệ quy chiếu đã định nghĩa từ trước. Mỗi ô (x, y) trên lưới có một giá trị thể hiện xác suất mà ô đó có chứa vật cản. Nói cách khác, giá trị đó thể hiện khả năng mà robot có nên di chuyển qua ô đó trong môi trường hay không. Giá trị này được xác định thông qua việc phân tích dữ liệu từ cảm biến. Cụm từ bản đồ lưới được đề cập đầu tiên bởi Nilsson 1969 [102] nơi bản đồ lưới được định nghĩa bởi một lưới kích thước (4× 4). Nếu một ô lưới được xem là sử dụng thì nó được chia thành 16 tế bào mới bằng một giải thuật đệ quy. Elfes và Moreavec 1985 [94] trình bày lần đầu tiên một phương pháp sử dụng cảm biến siêu âm và cảm biến laser sử dụng nhiều phép đo góc rộng các khu vực là rỗng, bị chiếm dụng hoặc chưa định nghĩa nhằm xây dựng bản đồ lưới và hướng di chuyển xung quanh robot. Borenstein 1991 [12] đề xuất phương pháp xây dựng bản đồ HIMM (Histogramic In-Motion Mapping) trong thời gian thực cho robot tự hành, biểu diễn bởi một mảng hai chiều hay còn lưới tần suất lược đồ màu được cập nhật nhanh thông việc lấy mẫu chuyển động của cảm biến siêu âm nhằm biểu diễn thông tin môi trường như vị trí vật cản, đường đi của robot. HMIMM triển khai trên robot di động với tính năng kép như biểu diễn vật cản chưa biết trên bản đồ môi trường 16 được tạo ra và đồng thời robot di chuyển tránh vật cản với vận tốc 0.78m/s. Cyrill Stachniss và Wolfram Burgard 2003 [127] trình bày phương pháp xây dựng bản đồ lưới với tỷ lệ che phủ trên các ô đại diện bao phủ bởi vật cản trong môi trường. Lilienthal và Duckett 2004 [84] đề xuất phương pháp lập bản đồ lưới sử dụng cảm biến laser và siêu âm để thu thập thông tin môi trường. Kỹ thuật xây dựng bản đồ sử dụng hàm trọng số Gauss để mô hình hóa khả năng suy giảm đại diện cho khoảng cách trên bản đồ xây dựng tính từ điểm đo. Phần thực nghiệm tiến hành tại trong phòng thí nghiệm kích thước (10.6× 4.5m2) robot xây dựng bản đồ môi trường, các chiến lược khác nhau tổng thời gian là 70h. 2.2.2 Hướng tiếp cận sử dụng bản đồ topo Bản đồ topo mô tả mối liên hệ giữa các điểm (vị trí) hay các đối tượng liên quan với nhau để mô tả cấu trúc của môi trường. Bản đồ topo không bao gồm thông tin số liệu, thông tin khoảng cách giữa các điểm trên bản đồ. Thay vào đó, các thông tin chính đại diện trong bản đồ topo là quan hệ giữa các địa điểm, nơi mà robot có thể di chuyển trực tiếp từ nơi này đến nơi khác. Brooks 1984 [16] biểu diễn môi trường sử dụng thông tin thị giác nhằm xây dựng một bản đồ topo trong đó vị trí như xa lộ được định nghĩa là các khối, đường cao tốc là các cạnh và đồng cỏ là các nút của bản đồ. Ý tưởng này có thể được kết hợp trong biểu diễn bản đồ bằng cách tránh việc sử dụng một hệ tọa độ 2-D. Thay vào đó, chỉ có các mối quan hệ giữa các phần của bản đồ được lưu trữ, trong một đại diện đồ thị. Các mối quan hệ bao gồm phần dự đoán trên các thành phần không chắc chắn (uncertainty). Để hiểu và di chuyển trong môi trường dễ dàng, thì robot di động phải có được một mô hình thông nhất. Chatila 1985 [23] đề xuất phương pháp biểu diễn môi trường với khái niệm vị trí được định nghĩa là một vùng của bản đồ topo như là một đơn vị riêng biệt. Trong đó phương pháp biểu diễn môi trường được thực hiện làm 2 pha: thứ nhất, việc sử dụng một hệ thống cảm biến, ưu tiên các dữ liệu thu thập bởi các cản biến có độ chính xác trong một số tình huống cụ thể, trung bình của các phép khác nhau nhưng nhất quán của cùng một đối tượng không chắc chắn; thứ hai, phương pháp cho phép robot di động để xác định mốc tham chiếu trong việc khám phá môi trường khi di chuyển. Trong khi đó Kuipers và Byun 1991 [77] lại định nghĩa các nút của bản đồ như một phòng hoặc một hành lang, các cửa ra vào và lối đi được định nghĩa là các cạnh. Các tác giả đã phát triển một phương pháp định tính trong bài toán biểu diễn môi trường, lập bản đồ ngữ nghĩa và điều hướng cho robot di dộng trong môi trường có 17 không gian quy mô lớn. Bằng phương pháp thực nghiệm định lượng, các tác giả của bài báo đã xây dựng một bản đồ trong môi trường biết trước với độ chính xác cao. Phương pháp thực hiện bằng việc mô tả mạng topo được hình thành bằng các liên kết những vị trí đặc biệt khi di chuyển qua các cạnh. Bản đồ số liệu sau đó tăng dần đồng hóa thông tin của các vị trí và các cạnh. Cuối cùng một bản đồ ngữ nghĩa được trồng ghép thành bản đồ ngữ nghĩa của môi trường. Với những phương pháp được công bố trên các tạp chí và hội nghị uy tín thì bài toán biểu diễn môi trường cho robot di động thu hút được các nhà nghiên cứu lớn như Kortenkamp 1994 [75] đề xuất sử dụng kết hợp hai luồng thông tin siêu âm và hình ảnh nhằm biểu diễn môi trường, trong đó nguồn dữ liệu siêu âm không đủ dồi dào và phạm vi bị giới hạn tại các góc dẫn tới sự phân biệt khó khăn tại các địa điểm đặc biệt. Việc sử dụng cảm biến hình ảnh cho phép nhận dạng các vị trí mà cảm biến siêu âm không thực hiện được, thông tin của hai luồng dữ liệu này được kết hợp lại bằng mạng Bayes đơn giản. Hay Simmons 1995 [125] phát triển một phương pháp sử dụng mô hình Markov để biểu diễn môi trường , giám sát và theo vết vị trí di chuyển của robot, trong đó ba nguồn thông tin được sử dụng để xây dựng mô hình Markov bao gồm: bản đồ topo môi trường, thông tin đã biết về môi trường và những thông tin gần đúng liên quan đến độ dài môi trường. Ngoài ra phương pháp này tích hợp các thông tin bản đồ topo và thông tin số liệu gần đúng giải quyết các tình huống dự đoán không chắc chắn trong bài toán mô tả thông tin môi trường. Năm 1996 Thrun [130] xây dựng bản đồ phân vùng sau đó ánh xạ vào một đồ thị đẳng cấu. Đây là phương pháp áp dụng kỹ thuật cấu trúc đồ thị liên thông đại diện cho môi trường, trong đó các nút đồ thị tương ứng với địa điểm, đường nối giữa các địa điểm là các cạnh. Vào đầu thế kỷ XXI, Ulrich 2000 [134] trình bày kỹ thuật định vị dựa trên bản đồ topo môi trường sử dụng thông tin hình ảnh trong bài toán nhận dạng vị trí, phương pháp biểu diễn môi trường sử dụng một hệ thống hình ảnh toàn cảnh (Panoramic) để mô hình hóa môi trường, hình ảnh được thu thập và phân loại trong thời gian thực bằng phương pháp láng giềng gần nhất kết hợp với biểu đồ sắc tố màu và một cơ chế bình chọn quyết định vị trí trong môi trường. Cũng cùng năm đó E.Fabrizi và A. Saffiotti 2000 [46] đề xuất xây dựng bản đồ topo dựa trên việc biểu diễn mới của không gian làm việc cho robot di động, bản đồ này tự động trích xuất thông từ một bản đồ lưới từ các dữ liệu hình ảnh thu thập từ camera. Tiếp theo sử dụng hệ mờ để định nghĩa các vị trí trên môi trường, với cách tiếp cận này bản đồ môi trường được biểu diễn tạo ra có khẳng năng xử lý nhiễu thu thập và các thay đổi trong môi trường nhỏ hẹp. Duckett 2003 [37] đề xuất một hệ thống mà một nút mới trên bản đồ được đặt 18 sau khi robot đã đi qua vị trí đó, tác giả đã sử dụng một thuật toán học nhanh trực tuyến cho tập bản đồ hình học sử dụng thông tin số liệu cục bộ. Thuật toán hoạt động bằng cách sử dụng kỹ thuật giảm thiểu năng lượng thu nhận thông qua một hàm năng lượng qua nhiều bước nhỏ. Các thí nghiệm được thực hiện trong môi trường lớn, phức tạp đã ánh xạ được vị trí robot lên bản đồ xây dựng trong thời gian thực. 2.2.3 Hướng tiếp cận lai Ý tưởng chính bản đồ lai nhằm biểu diễn môi trường hiệu quả trong những năm gần đây xu hướng tạo ra bản đồ lai tận dụng những ưu điểm của hai loại bản đồ số liệu và bản đồ topo giải quyết các vấn đề trong lĩnh vực robot di động thường tập trung vào 3 kiểu lai: lai đầu, lai song song, lai chắp vá. − Bản đồ lai đầu: Giralt 1979 [56] và Chatila và Laumond 1985 [23] trình bày tổng quan về bản đồ lai, ngoài việc phân tích các ưu nhược điểm của bản đồ số liệu và bản đồ topo các tác giả còn đưa thêm khái niệm về bản đồ ngữ nghĩa với khái niệm ràng buộc mối quan hệ về không gian và đối tượng. Đây cũng là tiền đề xây dựng các bài toán SLAM cho robot di động. Kuipers và Byun 1991 [77] đã chứng minh được để xây dựng hiệu quả một bản đồ lai thì một bản đồ topo được xây dựng bằng cách sử dụng các phương pháp phân biệt cho các nút của đồ thị, mỗi nút của bản đồ được gắn các thông tin số liệu, do đó bản đồ số liệu sẽ thực hiện lai sau bản đồ topo. Cùng với nghiên cứu kết hợp giữa bản đồ topo và bản đồ số liệu còn có các nghiên cứu tiêu biểu, như: Kuipers và Benjamin 2000 trình bày phương phương biểu diễn môi trường cho bài toán robot di động sử dụng bản đồ lai toàn diện nhất [76], tác giả đã đề xuất tính tổng quát của không gian SSH (Spatial Semantic Hierarchy) là một mô hình quy mô lớn bao gồm nhiều đại diện tương tác cả về định tính và định lượng. Bản đồ lai được xây dựng từ phép lai giữa bản đồ hình học tham chiếu đến bản đồ topo nhằm xây dựng một tham chiếu phục vụ mức độ kiểm soát các luật cấu thành nên các thành phần của môi trường, SHH là cơ sở cho một số hướng nghiên cứu sau này. Kuipers 2004 [78] mô tả phương pháp xây dựng bản đồ lai từ việc chiết xuất thông tin bản đồ cục bộ số liệu kết hợp với không gian SSH để tạo ra bản đồ topo trong điều khiển robot di động. Phương pháp Metrical SLAM được sử dụng để xây dựng bản đồ cục bộ với không gian quy mô nhỏ, trong khi đó phương pháp topo được sử dụng để đại diện cho cấu trúc không gian quy mô lớn. Với cách làm này, bản đồ được tạo ra phù hợp hơn với giả thuyết khi thực hiện việc khai phá dữ liệu trong môi trường. Beeson 2005 [6] trình bày phương pháp biểu diễn môi trường bằng hướng tiếp cận bản đồ lai trên cơ sở hệ mở rộng của đồ thị Voronoi được sử dụng trong bài toán phát hiện vị trí. Các tác giả đã đề xuất 19 một thuật toán tin cậy phát hiện các vị trí từ các cảm biến trên các vùng độc lập. − Bản đồ lai song song: được xây dựng từ ít nhất hai bản đồ khác nhau thực hiện trên cùng một môi trường, điều này thích hợp cho tình huống cụ thể được sử dụng. Hầu hết các bản đồ được xây dựng tự động hoặc được xây dựng từ việc chiết xuất thông tin từ một bản đồ khác như trường hợp bản đồ topo được chiết xuất ra khỏi bản đồ số liệu. Ví dụ như trong nghiên cứu của Thrun và Bu¨cken 1996 [130] và Thrun 1998 [129] xây dựng bản đồ lai từ việc chiết xuất thông tin từ đồ thị Voronoi của phần thông tin trống trên bản đồ số liệu được chia thành các phân đoạn mà cực đại có thể tìm thấy trong sơ đồ. Poncela 2002 [112] bản đồ số liệu được chia thành các ô trong bản đồ lưới và được định nghĩa thành 3 loại (rỗng, chiếm dụng, chưa khai phá), tất cả các những bản đồ topo được trích xuất có thể sử dụng trong bài toán xây dựng đường đi tối ưu. Ngược lại để trích xuất các bản đồ số liệu trên bản đồ topo ít thực hiện được trình bày trong Duckett và Saffiotti 2000 [38]. Lập và tìm đường đi hiệu quả là trọng tâm chính trong bản đồ lai song song trong Fernández-Madrigal 2004 [47]; Galindo 2004 [50] đưa ra khái niệm AH-graph (Annotated Hierarchical-graph) sắp xếp theo chiều dọc khi thực hiện mức độ gia tăng các điểm trên bản đồ topo và kết hợp với bản đồ số liệu cục bộ hỗ trợ cho việc định vị. − Bản đồ lai chắp vá: thực chất là bản đồ số liệu hình thành từ bản đồ topo bao gồm toàn bộ khu vực cộng với tập hợp các bản vá lỗi số liệu nhỏ cho mỗi nút topo, với ưu điểm là cấu trúc được thu nhỏ khi làm việc ở môi trường lớn. Tiêu biểu như nghiên cứu của Dudek 1996 đã mô tả bản đồ lai bao gồm một số loại bản đồ ở mức độ trừu tượng khác nhau như: cảm quan, hình học (số liệu), quan hệ cục bộ, topo và ngữ nghĩa [39]. Theo hướng tiếp cận khác, bản đồ lai được xây dựng từ đồ thị Voronoi được đề cập trong Nagatani 1999 [99] có nghĩa các nút tương ứng trong bản đồ topo kết hợp với một đặc trưng của bản đồ số liệu. Tomatis 2002 [132] và Tomatis 2003 [131] trình bày về phương pháp xây dựng bản đồ lai nơi các nút trong bản đồ topo tương ứng với khe hở giữa hai phòng hoặc hành lang, mỗi phòng đều có một bản đồ số liệu liên quan, các cạnh có thông tin về điểm mốc có thể được phát hiện từ hai nút. “The Hierarchical Atlas” định nghĩa cấu trúc của bản đồ được trình bày trong Lisien 2005 [85] là một dạng bản đồ lai giữa số liệu và topo nhắm tới mục tiêu xây dựng hệ thống SLAM trong điều khiển và khai phá thông tin môi trường. 20 2.2.4 Thảo luận Để lựa chọn phương pháp biểu diễn môi trường phù hợp với ngữ cảnh của bài toán đặt ra, chúng tôi tiến hành đánh giá ưu nhược điểm của từng phương pháp cụ thể như sau: − Về ưu điểm: + Đối với bản đồ số liệu: thường được sử dụng cho các bài toán xác định vị trí, định tuyến và tìm đường tối ưu. Cung cấp thông tin chính xác về khoảng cách. Hỗ trợ bài toán tìm đường ngắn nhất. Bản đồ số liệu dễ dàng xây dựng, biểu diễn và bảo trì cho các môi trường phạm vi nhỏ hẹp. + Đối với bản đồ topo: dễ dàng mở rộng bản đồ đối với các môi trường có phạm vi lớn hơn. Đây là loại bản đồ phù hợp cho bài toán tìm đường đi tối ưu khi biết trước hai điểm. Không cần một mô hình cấu trúc dữ liệu tin cậy và dự đoán chính xác vị trí khi xây dựng bản đồ môi trường. + Đối với bản đồ lai : phù hợp với các bài toán robot tự hành, có khả năng kết hợp nhiều loại bản đồ phục vụ một mục đích chung. Có khả năng mở rộng và thu nhỏ phạm vi biểu diễn môi trường với nhiều chiều nhìn tại các góc khác nhau. − Về nhược điểm: + Đối với bản đồ số liệu: rất khó mở rộng đối với môi trường có quy mô lớn, bài toán tìm đường tối ưu tính toán lâu, chiếm dụng nhiều bộ nhớ. Cần có một mô hình số liệu tin cậy và xác định chính xác vị trí khi xây dựng bản đồ môi trường. + Đối với bản đồ topo: độ chính xác không cao, cung cấp các đường đi dưới mức tối ưu. Khó khăn khi xây dựng và duy trì. + Đối với bản đồ lai : không đưa ra được nguyên tắc chung để kết hợp các bản đồ khác nhau. Khó khăn khi đánh giá và so sánh với các hệ thống khác. Căn cứ vào các phân tích đánh giá phía trên, luận án lựa chọn hướng tiếp cận thứ ba theo hướng tiếp cận lai và bổ sung thêm các thành phần của môi trường với mục đích biểu diễn được các thông tin của môi trường phục vụ cho các bài toán định vị, dẫn đường cho robot, phần tiếp theo sẽ trình bày chi tiết của phương pháp đề xuất. 21 2.3 Đề xuất hướng tiếp cận lai ngữ nghĩa biểu diễn môi trường Xuất phát từ mục tiêu của luận án nghiên cứu phương pháp định vị sử dụng hình ảnh hỗ trợ cho bài toán trợ giúp dẫn đường cho NKT, chúng tôi đề xuất mô hình biểu diễn môi trường theo hướng tiếp cận lai ngữ nghĩa. Ý nghĩa của cụm từ lai, ngữ nghĩa được giải thích như sau. Bản đồ của môi trường được cấu thành từ bản đồ số liệu và bản đồ topo. Ngoài ra, các thông tin vật cản tĩnh của môi trường ở từng vị trí trên bản đồ cũng được xác định và đưa vào mô hình biểu diễn môi trường như mô tả trong Hình 2.1 dưới đây: bb b bbb Li = {Mi, Z i, Oi} b b b L1 LN b LN = {L1, L2, ..., LN} ◦ Bản đồ được biểu diễn theo cấu trúc topo gồm một tập N điểm trong môi trường sao cho tồn tại đường đi giữa hai điểm kề cận: Li Điểm mốcbb ◦ Mỗi điểm Li với i = 1, N chứa các thông tin sau: Trong đó: 1. Mi = {xi, yi, zi} tọa độ điểm mốc trong hệ quy chiếu đã được định nghĩa. Tọa độ được tính theo đơn vị (m) 2. Zi: Mô hình quan sát tại vị trí Li 3. Oi = {Oi1 , Oi2 .., Oij}: Tập vật cản xuất hiện trên ảnh Ii thu nhận tại vị trí Li ĐỊNH NGHĨA CÁC THÀNH PHẦN: Phòng ngủ Phòng ngủ Phòng ngủ Phòng ngủ Phòng họpWC WC Ii b b b b b b b b b số 6 số 5 số 4 số 3 x(m) (0, 0) y(m) Hội trường Hình 2.1 Mô hình biểu diễn môi trường theo hướng tiếp cận lai ngữ nghĩa Để biểu diễn môi trường theo mô hình này, các nhiệm vụ sau cần thực hiện: 1. Xác định các vị trí mốc trong môi trường Li với i = 1, N 2. Xác định tọa độ các vị trí mốc trong môi trường Mi = (xi, yi, zi). 3. Xác định các vật cản Oi = {Oi1, Oi2...Oij} trên ảnh Ii thu tại vị trí Li. Tập vật 22 cản Oi thuộc lớp đối tượng đã định nghĩa từ trước và hình dạng vật cản không ảnh hưởng đến mô hình biểu diễn, chi tiết phương pháp xác định vật cản được trình bày tại CHƯƠNG III của luận án. Như đã trình bày ở các phần trước, luận án đi theo hướng tiếp cận chỉ sử dụng thông tin hình ảnh để biểu diễn môi trường và định vị. Với bài toán xác định vị trí mốc trong môi trường nhằm tạo bản đồ topo thì các phương pháp xây dựng bản đồ topo dựa trên hình ảnh AM (Appearance based Mapping) thường được sử dụng. Với bài toán xác định tọa độ các vị trí mốc nhằm tạo thông tin số liệu, các phương pháp đo hành trình sử dụng hình ảnh VO thường được sử dụng. Thông thường, góc nhìn của camera hướng mặt đường đối với các bài toán VO trong khi các bài toán AM camera thường quan sát khung cảnh phía trước. Để giải quyết đồng thời cả hai bài toán trong một khung làm việc đồng nhất, chúng tôi thiết kế hệ thống thu thập dữ liệu gồm hai camera lắp vuông góc (một nhìn xuống mặt đường, một nhìn về phía trước). Chi tiết kỹ thuật thiết kế hệ thống thu thập dữ liệu để biễu diễn môi trường trình bày trong PHỤ LỤC C của luận án. Trong các phần trình bày tiếp theo, chúng tôi sử dụng hình ảnh thu thập từ camera nhìn xuống mặt đường phục vụ cho bài toán đo hành trình để tạo bản đồ số liệu. Hình ảnh thu được từ camera nhìn về phía trước phục vụ cho bài toán xác định các vị trí mốc trong môi trường để tạo bản đồ topo. Việc sử dụng tương ứng các khung hình thu tại cùng một thời điểm cho phép ánh xạ các vị trí mốc trên bản đồ topo sang bản đồ số liệu để có được vị trí thực của điểm mốc trên hệ quy chiếu. 2.4 Phương pháp xây dựng bản đồ môi trường 2.4.1 Xây dựng bản đồ số liệu Bài toán đo hành trình sử dụng hình ảnh được phát biểu như sau: Cho trước chuỗi hình ảnh liên tiếp thu thập từ camera I = {I1, I2, ..., IN} trong đó N là tổng số ảnh thu thập được. Xác định vị trí camera của trong quá trình di chuyển P = {P1, P2, ...PN}. Nếu vị trí ban đầu được biết trước, vị trí tiếp theo được xác định bởi một phép biến đổi T trừ đi vị trí trước đó đến vị trí hiện tại, trong đó T cấu thành từ chuyển động tịnh tiến tii−1 và chuyển động quay R i i−1 của camera giữa thời điểm hiện tại i và thời điểm trước đó i− 1. T ii−1 = [ Rii−1 t i i−1 0 1 ] (2.1) trong đó T ii−1 ∈ ℜ3×3, tii−1 ∈ ℜ1×3, Rii−1 ∈ ℜ2×3. 23 bα α b b I1 I2 v [R|t] P1(x1, y1) P2(x2, y2) Hình 2.2 Minh họa di chuyển của robot với vận tốc v và góc lái α Như vậy, nếu xe chỉ chuyển động trên mặt phẳng (z=0) như minh họa Hình 2.2 thì việc xác định được các vị trí Pi chỉ cần xác định hai tham số là vận tốc v và góc lái α, hai tham số này được tính toán bởi một phép biến đổi T gồm ma trận quay R và vector dịch chuyển t trong công thức (2.1). Trong số rất nhiều các kỹ thuật sử dụng hình ảnh để xây dựng bản đồ số liệu, phương pháp đo hành trình bằng thông tin thị giác do Van Hamme và các đồng nghiệp đề xuất năm 2011 [57] chỉ sử dụng 01 camera thông thường cho phép tái tạo lại quỹ đạo camera nhanh chóng và chính xác phù hợp với ngữ cảnh của bài toán. Vì vậy chúng tôi dựa trên phương pháp này đề xây dựng bản đồ số liệu. Phương pháp [57] được đánh giá trong môi trường ngoài trời với camera lắp đặt trên xe chạy với tốc độ 70km/h. Khi áp dụng vào môi trường trong nhà với camera gắn trên robot đi với tốc độ chậm, phương pháp này gặp một số khó khăn và thách thức. Trong phần dưới đây, chúng tôi sẽ trình bày phương pháp của Van Hamme và các đồng nghiệp, sau đó là các thích nghi của phương pháp. 2.4.1.1 Phương pháp đo hành trình bằng hình ảnh sử dụng mô hình không chắc chắn Ý tưởng của giải thuật VO đề xuất trong [57] sử dụng mô hình không chắc chắn của chuyển động của camera và chuyển động của xe, để tính toán các tứ giác tương ứng với các điểm đặc trưng tại khung hình hiện tại, cũng như chuyển động của các điểm đặc trưng trong khung hình trước. Sau đó chuyển động của camera giữa hai khung hình liên tiếp được ước lượng từ sự chồng lấp của các tứ giác. 24 Với chuỗi hình ảnh liên tiếp thu thập được I = {I1, I2, ..., IN}, thuật toán VO gồm N − 1 bước lặp minh họa như trong Hình 2.3. Bước lặp thứ i: Ii,MUTi−1,k k = 1,Mi−1 Ii Trích chọn đặc trưng Harris trên ảnh Ii KPij j = 1,Mi Tính các PUT trên ảnh Ii Tính các MUT trên ảnh Ii KeyPoint(Harris corners) PUTi MUTi PUTij j = 1,Mi MUTij j = 1,Mi Tính ảnh tương đồng từ PUTij j = 1,Mi và MUTi−1 i = 1,Mi−1 Xếp chồng PUTi và MUTi Ảnh tương đồng -60 -50 -40 -30 -20 -10 0 10 -10 0 10 20 30 40 50 60 70 80 90 Hành trình đo được Ước lượng tham số góc lái α; vận tốc v PUT: Perspective Uncertainty Tetragons MUT: Motion Uncertainty Tetragon Hình 2.3 Các bước giải thuật đo hành trình bằng thông tin hình ảnh VO Tại bước lặp thứ i với i = 2, N thực hiện các bước: 1. Trích chọn đặc trưng Harris Corner[59] trên khung hình Ii tính toán như sau: − Với mỗi điểm (x, y), cho trước một cửa sổ W quanh tâm (x, y), tính ma trận đạo hàm M tại vị trí này:[ M = ∑ W (Ix(xi, yi)) 2 ∑ W Ix(xi, yi)Iy(xi, yi)∑ W Ix(xi, yi)Iy(xi, yi) ∑ W (Iy(xi, yi)) 2 ] = [ A C C B ] (2.2) − Tính Det(M) = A+B; Tr(M) = AB − C2 25 − Tính đáp ứng góc tại (x, y) : R(x, y) = Det(M)− k ∗ Tr(M)2 − So sánh đáp ứng góc R với giá trị ngưỡng θV O. Nếu R > θV O thì kết luận (x, y) là điểm đặc trưng. Kết quả thu được là tập Mi điểm đặc trưng {KPij} với j = 1,Mi. Như vậy số điểm đặc trưng trích chọn được phụ thuộc vào θV O. Cách tính R và các giá trị λ1 và λ2 được trình bày chi tiết trong PHỤ LỤC A.1 của luận án. 2. Tính toán các PUTij tương ứng với các đặc trưng KPij dựa trên mô hình không chắc chắn của camera. Cụ thể mỗi PUTij là một hình tứ giác bao quanh điểm KPij. Mỗi góc của tứ giác được xác định từ một tổ hợp của bộ (góc ngẩng, góc nghiêng) của camera. 3. Tính toán cácMUTij tương ứng với các đặc trưng Harris KPij dựa trên mô hình chuyển động không chắc chắn của robot. Cụ thể mỗi MUTij là một hình tứ giác bao quanh điểm KPij. Mỗi góc của tứ giác được xác định từ một tổ hợp của bộ (vận tốc, góc lái) của robot. 4. Tạo ảnh tương đồng giữa các PUTij ở thời điểm i với các MUTi−1j ở thời điểm trước đó i − 1. Ảnh này thể hiện mức độ tương đồng trong không gian của góc lái và vận tốc, Giá trị điểm ảnh lớn nhất biểu thị tọa độ sự tương đồng giữa PUT và MUT lớn nhất, tương ứng với giá trị góc lái α và vận tốc v cần xác định cho phép ước lượng tham số chuyển động của camera, từ đó tái tạo lại hành trình. Giải thuật VO gốc đã được thử nghiệm thành công ở môi trường ngoài trời, trong điều kiện ánh sáng tốt, mặt phẳng đường có cấu trúc. Khi triển khai giải thuật VO ở một số môi trường trong nhà khác nhau (hành lang của tòa nhà) thì hành trình tái tạo được bị sai số nhiều so với thực tế, nhất là tại một số vị trí khi robot thực hiện phép quay (xem Hình 2.4). 140 120 100 80 60 40 20 5025 y(m) Thöïc ñòa Baûn ñoà (a) Tröôøng THCS Nguyeãn Ñình Chieåu 0-25-50 x(m) 120 100 80 60 40 20 5025 y(m) 0-25-50 x(m) (b) Thö vieän Taï Quang Böûu – ÑHBK Haø Noäi 140 140 60 50 40 30 20 10 10 y(m) 0-30-40 x (m) -10-20 (c) Vieän nghieân cöùu MICA – ÑHBK Haø Noäi Thöïc ñòa Baûn ñoà Thöïc ñòa Baûn ñoà RMSE
= 1.23 m RMSE
= 1.78 m RMSE
= 0.68 m Hình 2.4 Một số trường hợp lỗi tích lũy khi xây dựng bản đồ 26 Chúng tôi đã nghiên cứu và phân tích kỹ nguyên nhân dẫn đến các sai số và nhận thấy với các môi trường có cấu trúc mặt đường nhẵn bóng, hoặc trải thảm, một số trường hợp độ chiếu sáng yếu, số điểm đặc trưng trích chọn được rất ít (xem Hình 2.5) dẫn đến sai số lớn trong việc tái tạo hành trình. (a) Maët neàn boùng – Soá ñieåm ñaëc tröng :4 (Tröôøng THCS Nguyeãn Ñình Chieåu) (b) Maët ñoä chieáu saùng yeáu– Soá ñieåm ñaëc tröng :3 (Thö vieän Taï Quang Böûu) (d) Maët neàn traûi thaûm – Soá ñieåm ñaëc tröng : 3 (Tröôøng Ñai hoïc Gent – Vöông quoác Bæ) (c) Maët neàn nhaün– Soá ñieåm ñaëc tröng : 2 (Vieän nghieân cöùu quoác teá MICA) Hình 2.5 Một số cấu trúc mặt nền thử nghiệm thuật toán VO * Nhận xét : Độ chính xác của hành trình tái tạo lại bởi giải thuật VO phụ thuộc rất nhiều vào số đặc trưng trích chọn được trên mỗi khung hình. Trong điều kiện ánh sáng không tốt, mặt đường đồng đều, số lượng đặc trưng trích chọn bị hạn chế dẫn đến sai số trong việc ước lượng các tham số dịch chuyển của camera. Do vậy, luận án trình bày giải pháp thích nghi VO tại môi trường trong nhà ở mục dưới đây. 2.4.1.2 Thích nghi VO cho môi trường trong nhà Để nâng cao độ chính xác của bản đồ tái tạo, chúng tôi đề xuất một giải pháp đơn giản dễ thực hiện để nâng số điểm đặc trưng phát hiện được trên mỗi khung hình. Cụ thể chúng tôi tạo các điểm đánh dấu trên đường đi (xem Hình 2.6) với quy trình tạo các điểm đánh dấu trên mặt sàn như sau: − Số lượng điểm đánh dấu trên mặt sàn diện tích S = 1m2 có từ 16-20 điểm đánh dấu dán cách đều nhau từ 15-20 cm (xem Hình 2.7). 27 (b) Phóng to vùng đánh dấu(a) Tạo các điểm đánh dấu trên dọc hành trình Hình 2.6 Tạo các điểm đánh dấu dọc hành trình − Hình dáng của điểm đánh dấu là hình có góc cạnh chữ nhật, hình vuông, bình hành (do ưu điểm của đặc trưng Harris Corner [59] phát hiện góc). Các mẫu khác như hình tròn, elip...không khuyến khích sử dụng vì số phát hiện trên các điểm đánh dấu này là rất ít (xem Hình 2.8d) − Không phân biệt màu sắc của các điểm đánh dấu như trắng, đen, vàng, đỏ...(xem Hình 2.8b) − Tạo các điểm đánh dấu quá dày (số điểm đánh dấu > 100 điểm/1m2) hoặc quá thưa (số điểm đánh dấu <= 3 điểm /1m2) đều ảnh hưởng đến việc đối sánh ảnh liên tiếp (xem Hình 2.8c), nếu giải ngẫu nhiên khó kiểm soát phân bố đặc trưng (xem Hình 2.8a). Dưới đây là kết quả khi thực hiện thích nghi giải thuật VO* trong nhà với phương pháp tạo điểm đánh dấu. (a) Chưa đánh dấu (b) Đã tạo các điểm đánh dấu Hình 2.7 Minh họa số điểm đặc trưng phát hiện trên mặt sàn 28 Hình 2.7 (a) minh họa khi chưa tạo các điểm đánh dấu thì số lượng điểm đặc trưng rất í...giá trị điểm ảnh trong vùng D được tính toán như sau: + P1 =A; + P2 = A+B; + P3=A+C; + P4= A+B+C+D + Khi đó, tổng các điểm ảnh trong một hình chữ nhật bất kì có thể tính nhanh dựa trên ảnh tích phân tại 4 đỉnh được tính theo công thức: SUM(D) = P4 + P1 − P2− P3 (A.32) 172 PHỤ LỤC B ĐÁNH GIÁ HIỆU NĂNG NHẬN DẠNG ĐỐI TƯỢNG TRÊN MỘT SỐ CƠ SỞ DỮ LIỆU TRONG VÀ NGOÀI NƯỚC B.1 Giới thiệu 3 CSDL thử nghiệm Để xây dựng được bộ CSDL vật cản hiệu quả nhằm phục vụ việc phát hiện nhận dạng các đối tượng và dự đoán được khoảng cách, chúng tôi tiến hành khảo sát và đánh giá trên 03 CSDL nhằm tìm ra được các vật cản có khả năng nhận dạng tốt nhất có trong môi trường thực, bao gồm: • Robot Vision 2013 [90] [19] được chia làm 2 tập dữ liệu chính như mô tả ở Hình B.1. 01. Haønh lang 02. Saûnh 03. Phoøng giaùo sö 04. Phoøng sinh vieân 05. Phoøng thieát bò 06. Nhaø veä sinh 07. Phoøng thö kyù 08. Phoøng hoäi thaûo 09. Kho löu tröõ 10. Thang maùy (a). Cô sôû döõ lieäu 10 lôùp khung caûnh (b). Cô sôû döõ lieäu 08 lôùp ñoái töôïng 01. Bình cöùu hoûa 02. Maùy tính 03. Gheá 04. Maùy in 05. Boàn tieåu 06. Maøn hình 07. Thuøng raùc 08. Tuû laïnh Hình B.1 Minh họa cơ sở dữ liệu Robot Vision 2013 − Dữ liệu khung cảnh: 01. Hành lang; 02. Sảnh; 03. Phòng Giáo sư; 04. Phòng 173 sinh viên; 05. Phòng thiết bị; 06. Phòng thư ký; 07. Phòng hội thảo; 08. Thang máy; 09. Kho; 10. Nhà vệ sinh. − Dữ liệu đối tượng : 01. Ghế; 02. Máy tính; 03.Bình chữa cháy; 04. Tủ lạnh; 05. Máy in; 06. Màn hình; 07. Thùng rác; 08. Bồn tiểu. Tổng số 5263 ảnh cho 2 lần thu (Visual-1 và Visual-2) bao gồm ảnh màu (RGB) và ảnh độ sâu (Depth- Point Cloud Data) được chia làm 02 phần: 1947 ảnh (Visual-1) huấn luyện tách được 2363 đối tượng, 3515 ảnh (Visual-2) phục vụ cho thử nghiệm. • PascalVOC 2007 [44] [45] [43]: gồm có 20 lớp đối tượng được chia làm 04 nhóm chính như mô tả trong Hình B.2: 01. Maùy bay 02. Xe buyùt 03. OÂ toâ 04. Xe ñaïp 05. Xe maùy 06. Thuyeàn 07. Xe löûa 08. Chaäu caây 09. Chai loï 10. Gheá 11. Baøn aên 12. Gheá Soâ-pha 13. Tivi/maøn hình 14. Chim 15. Meøo 16. Boø 17. Choù 18. Ngöïa 19. Cöøu 20. Ngöôøi Hình B.2 Minh họa 20 lớp đối tượng trong Pascal VOC − Nhóm phương tiện giao thông : 01. Máy bay; 02. Xe buýt; 03. Ô tô; 04. Xe đạp; 05. Xe máy; 06. Tàu thuyền; 07. Xe lửa − Nhóm các đối tượng trong nhà : 08. Chai lọ; 09. Ghế; 10. Bàn ăn; 11. Chậu cây; 12. Ghế sô-pha; 13. Tivi/Màn hình − Nhóm đối tượng con người : 20. Người 174 − Nhóm các đối tượng động vật : 14. Chim; 15. Mèo; 16. Bò; 17.Chó; 18. Ngựa; 19. Cừu Tổng số 7453 ảnh chứa 15 509 đối tượng chia ra làm 02 loại: 2501 ảnh huấn luyện và 4952 ảnh thử nghiệm. • Naiscorp 2012: xây dựng dịch vụ quảng cáo trực tuyến nằm trong khuôn khổ đề tài tiền năng của Bộ Khoa học và Công nghệ mã số: KC.01.TN19/11-15, bao gồm 10 lớp đối tượng, mỗi đối tượng có 500 ảnh, tổng số ảnh trong cơ sở dữ liệu là 5000 ảnh, trong đó 2500 ảnh cho phần thử nghiệm, 2500 ảnh cho phần huấn luyện và được tổ chức theo các thư mục được chỉ ra trong Hình B.4. − Nhóm các đối tượng trong nhà : 00. Hoa; 01. Điện thoại; 02. Đồng hồ; 03. Giày dép; 04. Kính; 08. Máy tính xách tay; − Nhóm đối tượng con người : 05. Người; − Nhóm phương tiện giao thông : 09. Xe máy; 06. Ô tô; 07. Thuyền; Nhận xét: Cả ba CSDL Naiscorp 2012, Pascal VOC 2007 và Robot Vision 2013 phải đảm bảo yêu tố đặt ra như các CSDL đủ lớn, đa dạng về góc chụp, kiểu dáng, về phông nền, về hướng, về khoảng cách, về điều kiện chiếu sáng thu nhận ảnh của đối tượng mô tả Hình B.3 (a) Söï ña daïng trong Naicorp 2012 (b) Söï thay ñoåi goùc nhìn trong Robot Vison 2013 (c) Ñoä chieáu saùng trong Pascal VOC 2007 Hình B.3 Những khó khăn thách thưc trên 3 CSDL đề xuất 175 Hoa Ñieän thoaïi Ñoàng hoà Giaày deùp Kính Ngöôøi OÂ toâ Thuyeàn Maùy tính xaùch tay Xe maùy Hình B.4 Các lớp đối tượng trong CSDL Naicorp 2012 176 B.2 Khung nhận dạng đối tượng tổng quát Trong khuôn khổ luận án, chúng tôi đề xuất nghiên cứu và thử nghiệm các phương pháp kết hợp giữa đặc trưng và bộ phân loại nhằm tăng hiệu năng nhận dạng đối tượng như mô tả Hình B.5: Tröôït cöûa soå Haar, HoG, Gist Cô sôû döõ lieäu Tieàn xöû lyù Trích choïn ñaëc tröng Huaán luyeän (Adaboost, SVM, k-NN) Moâ hình huaán luyeän Pha huaán luyeän Pha nhaän daïng Trích choïn ñaëc tröng Nhaän daïng (Adaboost, SVM, k-NN) Ñaàu vaøo Aûnh/Video Keát quaû Hình B.5 Khung làm việc tổng quát phát hiện và nhận dạng đối tượng Quá trình nhận dạng bao gồm 2 pha: • Huấn luyện: Cơ sở dữ liệu mẫu được đưa vào bộ tiền xử lý để làm sạch (màu sắc, ánh sáng, kích thước, dung lượng...) sau đó chuyển sang phần trích chọn đặc trưng. Tại đây, các đặc trưng đề xuất Haar, HoG, GIST được trích chọn đưa vào phần huấn luyện. Kết quả cho ta một tập các vector đặc trưng sử dụng cho pha nhận dạng. • Nhận dạng: Ảnh/Video cần nhận dạng đưa qua bộ trượt cửa sổ, dữ liệu được quét với nhiều kích thước khác nhau. Mỗi cửa sổ được trích chọn ra các đặc trưng và đưa vào phần nhận dạng. Tại đây mô hình nhận dạng sẽ thực hiện việc đánh giá so sánh với mô hình đã học theo một ngưỡng cho trước, ngưỡng này quyết định kết quả nhận dạng các đối tượng. Hình B.5 đưa ra mô hình khung nhận dạng kết hợp các phương pháp nhận dạng đối tượng, dưới đây chúng tôi sẽ trình bày tóm tắt các phương pháp nhận dạng đối tượng kết hợp bao gồm: − Kết hợp giữa Haar- AdaBoost : Haar [135] là một loại đặc trưng thường 177 được dùng cho bài toán nhận dạng đối tượng trên ảnh, xây dựng từ các hình chữ nhật có kích thước bằng nhau, để tính độ chênh lệch giữa các giá trị mức xám của các điểm ảnh trong các vùng kề nhau. Đặc trưng này có ưu điểm là tính toán nhanh thông qua việc sử dụng kỹ thuật ảnh tích phân, chi tiết có trong PHỤ LỤC A.6 của luận án. Đặc trưng Haar thường được sử dụng trong giải thuật học Boosting để lựa chọn ra một số đặc trưng tiêu biểu để biểu diễn đối tượng. Adaboost (Adaptive Boost): là một tiếp cận boosting [49] đượ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 bộ phân loại yếu để có một bộ phân loại mạnh mô tả như Hình B.6. Là một cải tiến của tiếp cận boosting, Adaboost sử dụng thêm khái niệm trọng số (weight) để đánh dấu các mẫu khó nhận dạng. H(x) = sign( T∑ t=1 αtht(x)) (B.1) T số lượng bộ phân loại yếu ht(x) tại thời điểm t; hệ số αt = 12 ln( 1−εj εj ); εj lỗi. Trong quá trình huấn luyện, cứ mỗi bộ phân loại yếu được xây dựng, thuật toá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 bộ phân loại yếu kế tiếp: 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 bộ phân loại yếu vừa xây dựng. h ; (x) h < (x) h = (x) H(x) Boä phaân loaïi yeáu Boä phaân loaïi yeáu Boä phaân loaïi yeáu Boä phaân loaïi maïnh Hình B.6 Minh họa giải thuật Adaboost Bằng cách này, các bộ phân loại yếu sau có thể tập trung vào các mẫu mà các bộ phân loại yếu trước nó chưa làm tốt. Các bộ phân loại yếu sẽ được kết hợp tùy theo mức độ tốt của chúng để tạo dựng nên bộ phân loại mạnh. Mô hình Cascade Adaboost [135]: được xây dựng chính là nhằm rút ngắn thời gian xử lý, giảm thiểu tỉ lệ nhận dạng sai cho bộ phân loại. Cascade gồm nhiều 178 tầng (stage), mỗi tầng của cây sẽ là một bộ phân loại. Một mẫu để được phân loại là đối tượng thì cần phải đi qua hết tất cả các tầng của cây. Caùc vuøng aûnh khoâng chöùa ñoái töôïng phaùt hieän Caùc vuøng aûnh chöùa ñoái töôïng phaùt hieän Boä phaân lôùp 1 Taát caû caùc vuøng aûnh S Ð T S S ÑBoä phaân lôùp 2 Boä phaân lôùp 3 Ð Ð Boä phaân lôùp 3 S Hình B.7 Mô hình phân tầng CascadeAdaboost Các bộ phân loại ở tầng sau được huấn luyện bằng những mẫu Negative mà bộ phân loại ở tầng trước nhận dạng sai, tức là sẽ tập trung học từ các mẫu không phải đối tượng khó hơn. Do đó sự kết hợp các bộ phân loại ở các tầng khác nhau sẽ giúp bộ phân loại giảm thiểu tỉ lệ nhận dạng sai. − Kết hợp giữa HoG- SVM : Ý tưởng đặc trưng HOG xuất phát từ hình dạng và trạng thái của đối tượng có thể được đặc trưng bằng sự phân bố về cường độ và hướng của cạnh. Đặc trưng HOG gồm một số loại như: RHoG, R2-HoG và C-HoG cho phép mô tả tốt cho các loại đối tượng khác nhau. Vì vậy, chúng tôi sử dụng HoG để trích chọn các đặc trưng cho thao tác nhận dạng các đối tượng, chi tiết phương pháp trích chọn có trong PHỤ LỤC A.5 của luận án. SVM [26] được xây dựng trên cơ sở hai ý tưởng chính. Ý tưởng thứ nhất: ánh xạ dữ liệu gốc sang một không gian mới gọi là không gian đặc trưng với số chiều lớn hơn sao cho trong không gian mới có thể xây dựng một siêu phẳng cho phép phân chia dữ liệu thành hai phần riêng biệt, mỗi phần bao gồm các điểm có cùng nhãn phân loại. Ý tưởng thứ hai: trong số những siêu phẳng như vậy cần lựa chọn siêu phẳng có lề lớn nhất. Lề ở đây là khoảng cách từ siêu phẳng tới các điểm gần nhất nằm ở hai phía của siêu phẳng (mỗi phía tương ứng với một nhãn phân loại). Lưu ý rằng siêu phẳng nằm cách đều các điểm gần nhất với nhãn khác nhau Xét tập r mẫu huấn luyện {(x1, y1), (x2, y2), . . . (xr, yr)}, trong đó xi là một vector đầu vào được biểu diễn trong không gian X ( Rn , yi là một nhãn lớp; yi{1,−1}. 179 Siêu phẳng tối ưu phân tập dữ liệu này thành hai lớp là siêu phẳng có thể tách rời dữ liệu thành hai lớp riêng biệt với lề lớn nhất. Tức là, cần tìm siêu phẳng H0 : y = w.x + b = 0 và hai siêu phẳng H+, H− hỗ trợ song song với H0 và có cùng khoảng cách đến H0. Với điều kiện không có phần tử nào của tập mẫu nằm giữa H+ và H− khi đó: H+ : w.x+ b ≥ +1 với y = +1 H− : w.x+ b ≥ −1 với y = −1 (B.2) Khoảng cách của siêu phẳng H+ và H− đến H0 là 1‖w‖ cần tìm siêu phẳng H0 với lề lớn nhất, là giải bài toán tối ưu tìm w và b sao cho 2 ‖w‖ đạt cực đại với ràng buộc yi(w.xi + b) >= 1. Support vectors −b ‖w‖ −ξi ‖w‖ Support vectors Hình B.8 Siêu phẳng tách với khoảng cách lề cực đại SVM Hình B.8 mô tả khả năng vượt trội của SVM về tính hiệu quả, độ chính xác, khả năng xử lý các bộ dữ liệu một cách linh hoạt, việc sử dụng phương pháp SVM đã và đang là sự lựa chọn tối ưu nhất trong việc giải quyết các bài toán phát hiện và nhận dạng. Siêu phẳng có khoảng cách với dữ liệu gần nhất là lớn nhất (biên lớn nhất) được gọi là siêu phẳng tối ưu, minh họa ở Hình B.9. − Kết hợp giữa GIST- kNN : Đặc trưng GIST [114], [106] việc trích chọn từ ảnh tập hợp các đặc trưng quan trọng như tính tự nhiên, mở rộng, độ nhám, độ chắc chắn, cho phép trình bày cấu trúc không gian của một cảnh. Chi tiết cách tính toán đặc trưng này có trong nội dung PHỤ LỤC A.4 của luận án. Bộ phân lớp k-NN (k-Nearest Neighbors)[73]: Học dựa trên láng giềng gần nhất 180 bc bc bc bc bc bc bc bc + + + + + + + + + + bc Lớp I Lớp II Biên lớn nhất Siêu phẳng tối ưu Một siêu phẳng Hình B.9 Phân tách theo siêu phẳng (w,b) trong không gian 2 chiều tập mẫu là một giải thuật phân lớp trên một tập đóng các ví dụ trong một không gian đặc trưng. Ý tưởng của phương pháp là xếp vào lớp có k hàng xóm gần với nó nhất, minh họa ở Hình B.10. Khoaûng caùch Nhaõün lôùp D1 1 D1 1 D5 5 D8 81 5 2 6 1 7 8 9 4 Aûnh thöû nghieäm Aûnh huaán luyeän Lôùp 1 Hình B.10 Minh họa các bước tính toán k-NN Các hàm tính khoảng cách k-NN đóng vai trò quan trọng trong phương pháp học, dựa trên các láng giềng gần nhất và thường được xác định trước không thay đổi trong suốt quá trình học và phân lớp. + Các hàm tính khoảng cách hình học: dành cho các bài toán có các thuộc 181 tính đầu vào là kiểu số thực (xi ∈ R) o Hàm Minkowski: d(x, z) = ( n∑ i=1 |xi − zi| p)1/p (B.3) o Hàm Manhattan: d(x, z) = n∑ i=2 |xi − zi| (B.4) o Hàm Euclid: d(x, z) = √√√√ n∑ i=1 (xi − zi)2 (B.5) + Hàm khoảng cách Hamming: dành cho các bài toán có các thuộc tính đầu vào là kiểu nhị phân (xi ∈ {0, 1}) d(x, z) = n∑ i=1 Difference(xi, zi) (B.6) Trong đó: Difference(x, z) = { 1, nếu (x 6= z) 0, nếu (x = z) B.3 Độ đo đánh giá Trong 03 CSDL đề xuất thử nghiệm, chúng tôi sử dụng các độ đo đánh giá khác nhau cụ thể như sau: • CSDL Naiscorp 2012: Sử dụng độ đo chính xác (Precision) tính theo công thức (2.26) để đánh giá hiệu năng của hệ thống nhận dạng. • CSDL Robot Vision 2013: Cung cấp bảng điểm cho việc nhận dạng 10 khung cảnh và 08 đối tượng như Bảng B.1, điểm cuối cùng là tổng điểm của tất cả các điểm thu được. Bảng B.1 Quy định thang tính điểm phần thi nhận dạng RobotVision2013 Các lớp đối tượng/Class Khung cảnh Đối tượng Nhận dạng chính xác 1.0 0.125 Nhận dạng sai -0.5 -0.125 Không nhận dạng 0.0 0.000 • CSDL PascalVOC 2007: sử dụng độ đo chính xác trung bình AP (Average Precision) thể hiện bằng giá trị tích phân đồ thị ROC (Receiver Operating Char- acteristic) bởi hai giá trị độ đo triệu hồi (recall) và độ đo chính xác (Precision) 182 B.4 Kết quả đánh giá Kết quả đánh giá trên 03 CSDL thực nghiệm là cơ sở để chúng tôi lựa chọn các lớp đối tượng đạt hiệu năng cao nhất nhằm xây dựng CSDL vật cản phù hợp với môi trường thực tế mà NKT thường gặp phải. Cụ thể như sau: - CSDL Naiscorp 2012: Trong Bảng B.2 Haar-AdaBoost là phương pháp tốt cho lớp điện thoại, đồng hồ, hoa, ô tô và Thuyền, điều này là do tính năng Haarlike đại diện với chi tiết của các đối tượng. Còn GIST và k-NN là phương pháp nhận dạng tốt cho lớp Giày dép, Kính, Máy tính xách tay, Xe máy. Độ chính xác trung bình CSDL Naiscorp 2012 trên 80%. Bảng B.2 Kết quả nhận dạng tượng CSDL Naiscorp 2012 TT Lớp đối tượng Haarlike-Adaboost HoG-SVM GIST-kNN 00 Điện thoại 97% 67% 88% 01 Đồng hồ 98% 95% 81% 02 Giày dép 34% 67% 73% 03 Hoa 90% 76% 75% 04 Kính 91% 87% 98% 05 Máy tính 62% 78% 99% 06 Người 91% 90% 77% 07 Ô tô 100% 85% 91% 08 Thuyền 100% 78% 92% 09 Xe máy 56% 88% 96% Trung bình 82% 81% 87% Hình B.11 các đối tượng trong ảnh được khoanh vùng và gán nhãn, kết quả nhận dạng phụ thuộc vào CSDL huấn luyện. Hình B.11(a) nhận dạng đúng đồng hồ bởi đặc tính của ảnh đưa vào nhận dạng khác nhiều so với bộ huấn luyện. Hình B.11(b) cho thấy nhận dạng nhầm từ lớp đồng hồ sang lớp máy tính xách tay bởi một số đặc trưng được trích chọn trên ảnh đồng hồ là phím bấm tương đối giống với các đặc trưng được trích chọn trên lớp máy tính xách tay, nên xảy ra trường hợp nhận dạng nhầm. Hình B.11(c) cho thấy lớp đồng hồ được nhận dạng đúng, tuy nhiên do đặc trưng trích chọn của lớp đồng hồ là hình tròn, phía trong có các họa tiết giống như một bông hoa nên nhận nhầm sang lớp hoa. Cuối cùng tại Hình B.11(d) có tình trạng nhận dạng nhập nhằng, nhận dạng tại lớp máy tính nhưng trong máy tính chứa hình ảnh giày dép nên cũng có thể hiểu nhận dạng sai hoặc nhận dạng đúng. Thuật toán nhận dạng đối tượng chạy trên máy tính cấu hình (CHIP Intel(R) Core(TM) 183 (b) Phaùt hieän nhaàm (d) Phaùt hieän nhaäp nhaèng(a) Phaùt hieän ñuùng (c) Phaùt hieän ñuùng, thöøa Hình B.11 Một số kết quả nhận dạng đúng/sai CSDL Naicorp 2012 i5-2520M CPU @ 3.2 GHz x 2, RAM 8GB). Kích thước trung bình của ảnh 600×400, tốc độ tính toán đạt 88.12 ms/ ảnh. - CSDL Robot Vision 2013: Đã có 16 kết quả của các đội thi đến từ các nhóm nghiên cứu trên thế giới gửi tới cuộc thi Robot Vision, trong đó nhóm MICA gửi 03 kết quả dự thi, cụ thể như sau. Phương pháp nhận dạng được đề xuất sử dụng giải thuật kết hợp GIST k-NN để nhận dạng khung cảnh trước khi nhận dạng các đối tượng. Kết quả nhận dạng minh họa ở Hình B.12. (b) Phaùt hieän nhaàm(a) Phaùt hieän ñuùng Hình B.12 Một số kết quả nhận dạng đúng/sai CSDL RobotVision2013 Nhóm nghiên cứu MICA đứng thứ 9/16 kết quả đạt số điểm 4497.875 điểm, kết quả xếp hạng có trong Bảng B.3. Kết quả này chưa cao do một số nguyên nhân như nhóm nghiên cứu chưa sử dụng đến hình ảnh độ sâu (Depth) được cung cấp, các đặc trưng khi trích chọn ảnh huấn luyện chưa đủ nhiều, bao hết các trường hợp trên tập thử nghiệm. Với những nguyên nhân 184 Bảng B.3 Kết quả điểm nhận dạng đối tượng CSDL Robot Vision 2013 TT Đội thi Tổng điểm Kết quả tham dự 1 MIAR ICT 6033.5 1367338469342_result5.txt 2 MIAR ICT 5924.25 1367337521811_result1.txt 3 MIAR ICT 5924.25 1367338031442_result3.txt 4 MIAR ICT 5867.5 1367338141275_result4.txt 5 MIAR ICT 5867 1367337920393_result2.txt 6 NUDT 5722.5 1367330362498_Submission_zy.results 7 SIMD* 5004.75 1366035468189_exampletest.results 8 REGIM 4638.875 1367938209005_results2 (1).results 9 MICA 4497.875 1367489769671_MICA_RobotVision_2.txt 10 REGIM 3763.75 1367937984977__results1 (1).results 11 MICA 3316.125 1367487985297_MICA_RobotVision_1.txt 12 MICA 2680.625 1368014381988_MICA_RobotVision_3.txt 13 GRAM -487 1368038785876_gram_3dspmk_l2_k400.txt 14 GRAM -497 1368090179987_gram_3dspmk_l2_k800.txt 15 GRAM -497 1368090208187_gram_3dspmk_l2_k1000.txt 16 NUDT -866.25 1367376643434_Submission_yl.results đó chúng tôi đề xuất kết hợp 02 nguồn dữ liệu màu sắc (RGB) và ảnh độ sâu (Depth) để nhận dạng chính xác có trong khung cảnh đề xuất. Thuật toán chạy cấu hình máy tính (CHIP Intel(R) Core(TM) i5-2520M CPU @ 3.2 GHz x 2, RAM 8GB), kích thước ảnh trung bình 640 × 480, thời gian tính toán trêm một ảnh 90.3 ms/ ảnh. - CSDL PascalVOC 2007: Với đồ thị AP trong Hình B.13 có thể thấy rằng đặc trưng GIST và bộ phân lớp k-NN khi chạy với CSDL Pascal VOC 2007 cho kết quả trung bình, với AP=0.164, trong đó các đồ thị AP các lớp đối tượng trong Hình B.14 thấy rõ vai trò đặc trưng GIST được sử dụng nhận dạng đối tượng cho kết quả tốt nhất trong các lớp người, ô tô, xe buýt, màn hình ti vi và không tốt đối với các lớp còn lại. Lý do các đối tượng trong CSDL rất đa dạng, số lượng lớn đặc biệt một ảnh chứa nhiều đối tượng. Tuy nhiên, GIST, k-NN cần phối hợp với các đặc trưng khác để cho kết quả tốt hơn. Một số hình ảnh về kết quả nhận dạng trên CSDL Pascal VOC 2007: Hình B.15(a) khoanh vùng được đối tượng ô tô, người (ngồi trong ô tô), đặc biệt với kỹ thuật quét cửa sổ trên toàn ảnh khoanh vùng được khóm cây bên đường, giống như đối tượng chậu hoa có trong CSDL. Tuy nhiên, phương pháp này cũng cho kết 185 Hình B.13 Đồ thị AP của 20 lớp đối tượng CSDL PascalVOC 2007 Hình B.14 Đồ thị AP từng lớp đối tượng CSDL PascalVOC 2007 186 (b) Phaùt hieän ñuùng, thöøa(a) Phaùt hieän ñuùng Hình B.15 Kết quả nhận dạng đối tượng trong CSDL Pascal VOC 2007 quả phát hiện thừa như Hình B.15(b) và Hình B.15(c). (b). Nhaän nhaàm sang lôùp choù (c) Nhaän nhaàm sang lôùp Boø (a) Lôùp cöøu Hình B.16 Kết quả nhận dạng đối tượng trong CSDL Pascal VOC 2007 Thuật toán nhận dạng đối tượng trên cơ sở dữ liệu PascalVOC 2007 chạy trên máy tính cấu hình (CHIP Intel(R) Core(TM) i5-2520M CPU @ 3.2 GHz x 2, RAM 8GB). Kích thước trung bình của ảnh (380× 470) điểm ảnh, tốc độ tính toán đạt 150 ms/ảnh. 187 PHỤ LỤC C THIẾT KẾ HỆ THỐNG THU THẬP DỮ LIỆU C.1 Xe camera thu thập dữ liệu - Ý tưởng thử nghiệm: sử dụng 02 camera bố trí vuông góc, thu dữ liệu đồng thời: camera thứ nhất chiếu xuống đất thu hình ảnh mặt đường, camera thứ hai hướng về phía trước thu thập dữ liệu khung cảnh, camera được gắn trên gậy; cầm tay; gắn trên ghế; gắn trên xe đẩy hàng; gắn trên xe đạp mô tả trong Hình C.1. (d) Gaén treân gaäy ngöôøi ñi boä (c) Gaén xe ñaïp(a) Gaén treân gheá (b) Gaén xe ñaåy haøng (e) Caàm treân tay ngöôøi ñi boä Hình C.1 Một số giải pháp thu thập dữ liệu từ 2 camera Với các thiết kế đã đề xuất trong Hình C.1, chúng tôi tiến hành đánh giá 02 kịch bản trong nhà và ngoài trời như sau: + Kịch bản 1 (trong nhà): tại khu thực nghiệm - Đại học Gent - Vương quốc Bỉ, định nghĩa 06 địa điểm (A, B, C, D, E, G) xuất phát từ A đi thành một vòng tròn khép kín qua các điểm rồi quay trở lại về A, chiều dài hành trình là d = 89.4m như Hình C.2(a). Phương pháp thu thập dữ liệu sử dụng ghế và xe đẩy hàng mô 188 tả như Hình C.1(a-b). Kết quả lệch so với thực địa được môi tả như Hình C.2(b) A B C D E G A B C G D E Thöïc ñòa Ñuùng Sai (a). Kòch baûn thöû nghieäm (b). Keát quaû veõ baûn ñoà Xuaát phaùt Keát thuùc Xuaát phaùt Keát thuùc Hình C.2 Một số lỗi khi xây dựng bản đồ tại môi trường trong nhà do cấu trúc mặt sàn không đồng nhất, số lượng đặc trưng không đồng đều gây ra lỗi tích lũy. + Kịch bản 2 (ngoài trời): tại khuôn viên Đại học Gent - Vương quốc Bỉ, định nghĩa 06 địa điểm (A, B, C, D, E, G) xuất phát từ A qua các điểm rồi quay lại A, chiều dài d = 320m như Hình C.3(a). Phương pháp thu thập dữ liệu sử dụng gậy, xe đạp và người đi bộ mô tả như Hình C.1(c-d-e). A B C D E G A BC G D E Thöïc ñòa Ñuùng Sai (a). Kòch baûn thöû nghieäm (b). Keát quaû veõ baûn ñoà Xuaát phaùt Keát thuùc Xuaát phaùt Keát thuùc Hình C.3 Một số lỗi khi xây dựng bản đồ tại môi trường ngoài trời Kết quả lệch với thực địa như Hình C.3(b) do tại những điểm có mật độ các đặc trưng ít dẫn tới việc sai số tích lũy làm thay đổi hành trình. - Nhận xét và đánh giá: Kết quả không đạt được những tiêu chí đặt ra như hình ảnh bị rung, nghiêng. Đặc biệt khi số lượng camera lớn hơn 2, thì việc lắp đặt trở lên 189 khó khăn hay khó để xác định một khoảng cách cụ thể để cố định camera theo các hướng yêu cầu. - Mục đích thiết kế xe camera: Hệ thống định vị và xây dựng bản đồ môi trường trong luận án dựa trên 2 giải thuật cơ bản là VO* và FAB-MAP*, trong đó: + Giải thuật xây dựng bản đồ môi trường VO*: sử dụng 01 camera gắn trên xe với một góc nhìn nào đó trúc xuống mặt đường. Nguyên lý trong VO là chỉ xem xét đến các điểm đặc trưng trích chọn trên mặt phẳng để đơn giản phép tính homography và phép ánh xạ ngược 2D-3D. + Giải thuật định vị hình ảnh FAB-MAP*: sử dụng 1 camera góc rộng (camera IP) thu thập các hình ảnh khung cảnh phía trước, nguyên lý của FAP-MAP* sử dụng xác suất có điều kiện Bayes giữa một quan sát hiện thời với một loạt các quan sát trước đó để quyết định vị trí đã được định nghĩa trên bản đồ môi trường. Do vậy cần có một nguồn dữ liệu được thu thập, đồng thời phục vụ cho pha huấn luyện của hai giải thuật có chất lượng hình ảnh tốt. Chúng tôi đã đề xuất thiết kế và chế tạo xe camera không phụ thuộc nhiều vào nguồn điện và truyền thông, được mô tả như Hình C.4. (a) Baûn veõ thieát keá (b) Xe hoaøn chænh Hình C.4 Thiết kế xe camera thu thập dữ liệu Hình C.4(a) mô tả chi tiết thiết kế xe camera kích thước: dài 1.3 m, rộng 0.6m, cao 1m (độ cao này có thể thay đổi 1.2m nhờ 4 khóa định vị); cơ cấu bánh 4 bánh (02 bánh hơi giảm sóc, 02 bánh nhựa chuyên động quay); mặt sàn được khoan các lỗ (cách nhau 20 cm, đường kính lỗ Φ = 0.5mm) giúp cố định nhiều thiết bị thu thập; thanh chữ L (chiều dài 50cm) cố định camera theo các hướng; bảng bàn cờ (độ cao cách sàn 60 cm) di chuyển ngang giúp việc hiệu chỉnh các tham số trong và ngoài của camera; 190 vật liệu sử dụng innox chống gỉ sét. Hình C.4(b) thiết kế xe hoàn chỉnh gắn 2 camera thu dữ liệu. C.2 Hiệu chỉnh camera góc rộng - Mục đích quá trình hiệu chỉnh: Thu thập được hình ảnh có chất lượng tốt, ổn định phục vụ cho cho một loạt các bài toán như định vị, xây dựng bản đồ, tìm đường, phát hiện vật cản... Do vậy các bước tiền xử lý hiệu chỉnh camera là rất quan trọng giúp cho các thuật toán chạy nhanh hơn, loại bỏ được các lỗi ngoại lai khó phát hiện. Quá trình hiệu chỉnh là việc xác định được 2 ma trận: ma trận nội tại (Intrinsic Matrix) và ma trận biến dạng (Distortion Matrix). Trong [15] các camera thông dụng hoạt động theo nguyên lý thu ảnh đối xứng như ở Hình C.5. Do vậy, nếu q là điểm thu được từ Camera và Q là điểm trong thực tế, thì ta có: Maët phaúng aûnh Ñieåm thu nhaän aûnh Truïc quang hoïc Hình C.5 Mô hình thu nhận ảnh của camera q = MQ , trong đó q =  xy ω   ,M =  fx 0 00 fy 0 0 0 1   và Q =  XY W   (C.1) Trong đó: fx và fy lần lượt là chiều dài tiêu cựu của camera, (Z, Y, Z) là tọa độ của điểm Q. Tuy nhiên, tọa độ của camera không phải lúc nào cũng thẳng mà đôi khi bị lệch. Để khắc phục điều này người ta cần thêm vào 2 hệ số cx và cy để đưa góc thu nhận ảnh về vị trí ở trung tâm. Do đó công thức (C.1) trở thành: q = MQ , trong đó q =  xy ω   ,M =  fx 0 cx0 fy cy 0 0 1   và Q =  XY W   (C.2) Ma trậnM trong công thức (C.2) được gọi là ma trận nội tại. Trong thực tế không 191 có camera nào hoàn hoản nên khi làm việc với camera luôn phải giải quyết vấn đề biến dạng hình ảnh. [15] đưa ra 2 loại: biến dạng bán kính (Radial Distortion), ảnh thu nhận được từ ống kính thường bị biến dạng ở những chỗ gần cạnh và biến dạng tiếp tuyến (Tangential Distortion) xảy ra khi không song song với ống kính như Hình C.6. OÁng kính AÛnh meùo Camera thoâng duïng OÁng kính Ñieåm baùn dính Chíp caûm bieán Maët phaúng aûnh Ñoái töôïng hình vuoâng 6 4 2 0 -2 -4 -6 -8 -10 (b). Bieán daïng tieáp tuyeán(a). Bieán daïng baùn kính -10 -8 -6 -4 -2 0 2 4 6 8 10 Hình C.6 Các loại biến dạng khi thu nhận ảnh Qua thực nghiệm, biến dạng thường không lớn và có thể chuẩn hóa bằng cách sử dụng một vài hệ số đầu tiên trong triển khai Taylor xung quanh bán kính r = 0. Để hiệu chỉnh loại biến dạng này người ta thường thêm 02 hệ số k1 và k2 đối với méo thông thường, còn trường hợp méo lớn sử dụng thêm hệ số k3. Do vậy, biến dạng bán kính của một điểm được hiệu chỉnh bởi cặp phương trình sau: xcorrected = x(1 + k1r 2 + k2r 4 + k3r 6) ycorrected = y(1 + k1r 2 + k2r 4 + k3r 6) (C.3) Trong đó (x, y) là tọa độ của điểm thu nhận bởi camera, (xcorrected, ycorrected) là tọa độ sau khi đã khử biến dạng. Bằng cách làm tương tự đối với biến dạng tiếp tuyến thì hai hệ số p1 và p2 được bổ sung vào hệ tọa độ (x, y) của camera được điều chỉnh bằng cặp phương trình sau: xcorrected = x+ [2p1y + p2(r 2 + 2x2)] ycorrected = y + [p1(r 2 + 2y2) + 2p2x] (C.4) Năm hệ số ở công thức (C.3) và công thức (C.4) được gom lại thành một ma trận (5× 1) và gọi là ma trận biến dạng trong công thức (C.5). Distortioncoefficients = (k1 k2 p1 p2 k3 ) (C.5) Trong khuôn khổ của luận án, chúng tôi sử dụng phương pháp ô bàn cờ (chess- 192 board) [15] bao gồm các ô hình vuông đen trắng giao nhau, quá trình hiệu chỉnh được thực hiện khi biết được vị trí giao nhau giữa các ô đen trắng để tính ra các bộ tham số méo của ảnh. Sau đó kết hợp với tọa độ ảnh thu thập tìm ra tọa độ trong không gian theo công thức (C.4), trong đó (xcorrected, ycorrected) tọa độ không gian, (x, y) tọa hộ ảnh thu thập, (r, p1, p2) bộ tham số lấy được từ quá trình hiệu chỉnh camera. Công thức chuyển tọa độ ảnh sang hệ tọa độ không gian:  xy ω   =  fx 0 cx0 fy cy 0 0 1    XY Z   (C.6) Trong đó (fx, fy) là tiêu cựu của ống kính, (cx, cy) điểm tâm quang, (ω = Z) hệ quy chiếu thế giới thực. Quá trình hiệu chỉnh Camera phục vụ việc sửa méo hình ảnh được thực hiện tuần tự và được mô tả Hình C.7 (a) Hình aûnh chöa hieäu chænh (c) Hình aûnh ñaõ hieäu chænh(b) Hieäu chænh treân chessboard Hình C.7 Quá trình hiệu chỉnh méo hình ảnh từ camera góc nhìn rộng Hình C.7 minh họa kết quả hiệu chỉnh camera tại môi trường thử nghiệm của luận án. Đây là một bước tiền xử lý quan trọng, phục vụ cho các bài toán liên quan đến hình ảnh như: định vị, phát hiện và ước lượng khoảng cách vật cản... C.3 Robot PC-Bot914 PC-Bot 914 là robot được nghiên cứu và chế tạo bởi WhiteBox robotic. Đây là một robot dịch vụ đa chức năng với nền tảng xử lý mạnh bao gồm các thành phần: - Khối xử lý trung tâm: Được sử dụng là một máy tính chủ (host computer), có cấu hình iGoLogic i3899 Mini-ITX motherboard, bộ xử lý intel Core 2 DUO 2 GHz, 1 Gbyte, PC3200 DDR 400MHz DIMM (có thể nâng cấp lên 2x1 GB DDR 667MHz), ổ cứng 80 GB SATA. Cung cấp sức mạnh xử lý và lưu trữ dữ liệu đa phương tiện và cho phép nâng cấp dễ dàng. ROBOT dùng hệ điều hành Windows. Trên mỗi hệ điều 193 C0189168#06 C0189168#10 C0189168#07 C0189168#08 Hình C.8 Các phiên bản của robot PC-Bot 914 hành đều có cung cấp các môi trường phát triển. Trên windows với khá nhiều phần mềm như BRAIN, Microsoft Robotic Studio hay là Visual Studio vì 914 PC-Bot đã hỗ trợ dot Net. Ngoài ra trên một số diễn đàn đã có những chương trình phát triển với java hay C++. Đối với các phiên bản cài Linux (Ubuntu) thì có công cụ Players. - Khối điều khiển trung tâm (M3): Hạt nhân của khối là 2 vi điều khiển CM3410 của hãng Power machine device. Bên cạnh đó là mạch điều khiển động cơ và mạch giao tiếp. Nhiệm vụ của khối M3 là nhận tín hiệu thiết lập từ Host Computer (qua cổng USB), tín hiệu từ các cảm biến hồng ngoại (qua mạch giao tiếp) và thực hiện tất các cả công việc liên quan đến việc chuyển động như điều khiển 2 động cơ bước. Phần giao tiếp của M3 gồm 8 cổng vào tương tự (Analog_In1 à Analog_In8) để nhận tín hiệu từ 8 cảm biến hồng ngoại, 8 cảm biến này sẽ cho 8 bit dữ liệu sau khi tín hiệu được đi qua một bộ ADC. Ngoài ra còn nhiều cổng chưa được sử dụng, như: 8 cổng vào số; 8 cổng ra số; 2 cổng USB; 1 cổng IDC; 10 chân dùng để kết nối với bo mạch chủ. Ngoài ra còn 30 pin Samtec Conn dùng để kết nối với mạch khối điều khiển M3 . Trong thế hệ mới thì chỉ có một mạch I/O board Interface vì chỉ cần 1 mạch là đủ đáp ứng các nhu cầu khác nhau. Tuy nhiên ta có thể chọn 1 hoặc 2 tùy thuộc vào nhu cầu cụ thể. - Khối thu thập dữ liệu: 8 cảm biến hồng ngoại phục vụ cho các bài toán liên quan đến robot di động như: phát hiện và tránh vật cản được bố trí thành 2 phần: 3 cảm biến nằm ở phần thân robot, khoang 8×5.25 trên cùng (ở độ cao khoảng 370 mm). Góc nhìn hơi cúi xuống cho phép 914 PC-BOT có cái nhìn toàn cảnh với 5 cảm biến nằm ở phần chân đế với góc nhìn nằm ngang, mô tả Hình C.9 - Khối chấp hành: Bao gồm 2 động cơ một chiều điều khiển bộ bánh xe 4 bánh xe robot trong đó, 2 bánh lớn dẫn hướng, 2 bánh phụ giảm sóc cho robot Hình C.10. 194 (IR1) (IR2) (IR3) (IR4) (IR5) 90> 25> 0> -25> -90> (a). 05 caûm bieán hoàng ngoaïi phaùt hieän vaät caûn phía döôùi (IR 2, IR3, IR4) (IR 1 & IR5) (b). Vò trí laép caùc caûm bieán hoàng ngoaïi (IR 6, IR7, IR8) Hình C.9 Vị trí lắp các cảm biển hồng ngoại IR Hình C.10 Cơ cấu bánh xe điều khiển của robot PC-Bot 914 195