Quy hoạch quỹ đạo cho robot di động dựa trên thị giác máy tính

Nội dung text: Quy hoạch quỹ đạo cho robot di động dựa trên thị giác máy tính

1. QUY HOẠCH QUỸ ĐẠO CHO ROBOT DI ĐỘNG DỰA TRÊN THỊ GIÁC MÁY TÍNH PATH PLANNING FOR MOBILE ROBOT BASED ON COMPUTER VISION Ngô Văn Thuyên, Nguyễn Hữu Nam Đại học Sư Phạm Kỹ Thuật Tp. Hồ Chí Minh TÓM TẮT Bài báo giới thiệu thuật toán quy hoạch quỹ đạo cho robot di động trong nhà dựa trên thị giác máy tính. Thuật toán được xây dựng nhằm giải quyết những vấn đề cơ bản mà robot gặp phải trong quá trình di chuyển bao gồm định hướng, định vị trí, tránh vật cản và các bài toán nhận dạng như nhận dạng điểm mốc, cửa và vật thể đích. Các thuật toán xử lý ảnh được hỗ trợ bằng các hàm từ thư viện OpenCV. Kết quả của thuật toán được áp dụng trên một robot thực nghiệm. Chương trình xử lý và điều khiển robot được viết trên nền mã nguồn mở điều khiển robot thông dụng Player. ABSTRACT This paper introduces path planning algorithm for indoor mobile robot based on computer vision. The algorithm is designed to solve basic problems that robot encounter on moving including navigation, localization, obstacles avoidance and recognition such as landmark, door, object. The image processing algorithms are supported by functions from the OpenCV library. The results of the algorithm is applied on an experimental robot. Control commands are sent to the robot based on the protocol in Player, a popular open source code to link with robot. Từ khóa: Robot di động, quy hoạch quỹ đạo, thị giác máy tính, OpenCV, Player 1. Giới thiệu di chuyển được phân chia thành môi trường Camera ngày càng được sử dụng nhiều có cấu trúc và môi trường không có cấu trong các ứng dụng trên robot di động do trúc. khả năng mô tả môi trường chính xác hơn Đối với ứng dụng trong nhà trong môi các loại cảm biến như siêu âm hay laser. trường có cấu trúc, robot sẽ định hướng dựa Camera cung cấp các thông tin về màu sắc, trên bản đồ được cung cấp. Bản đồ về môi ảnh của vật thể, khoảng cách tới vật thể trường thường biểu diễn dưới dạng mô hình trong khi các cảm biến như siêu âm, laser CAD, “Occupancy map” [3] hay S-Map [4]. chỉ cung cấp thông tin về khoảng cách. Robot định vị trí trên bản đồ dựa trên thị Ngoài ra, khả năng tính toán ngày càng giác bằng việc phát hiện các điểm mốc [5] mạnh mẽ của máy tính đã giúp cho quá hoặc kết hợp với thông tin từ encoder. Dữ liệu khoảng cách từ cảm biến được dùng để trình xử lý thông tin trong ảnh nhanh hơn. Hiệu năng của quá trình xử lý thông tin xây dựng biểu đồ Histogram [3] hoặc được tối ưu hóa bằng việc sử dụng các hàm “Ocupancy map” nhằm biểu thị mối tương từ thư viện OpenCV [1]. Những điều này quan giữa robot và môi trường. Robot dựa mang lại cho robot di động khi sử dụng thị vào thông tin từ biểu đồ để phát hiện vật giác máy tính khả năng nhận biết và xử lý cản và tìm vùng an toàn để di chuyển tránh thông tin về môi trường tốt hơn so với vật cản. Một trong những ưu điểm mà thị những phương pháp khác. giác máy tính mang lại cho robot là khả Các nghiên cứu về robot di động dựa năng nhận dạng vật thể thông qua màu sắc trên thị giác chủ yếu tập trung vào hai [6], hình dạng [7], đặc điểm [8]. Nhận dạng hướng ứng dụng là trong nhà và ngoài trời vật thể giúp cho robot linh hoạt hơn trong [2]. Trong cả hai hướng, môi trường robot quá trình di chuyển. 1
2. Trong bài báo này chúng tôi xây dựng di chuyển qua vật cản. Biểu đồ histogram thuật toán quy hoạch quỹ đạo cho robot di thể hiện mối tương quan về khoảng cách động dựa trên thị giác máy tính trong môi giữa robot và các vật thể trong môi trường, trường có cấu trúc. Phần còn lại của bài báo thông tin khoảng cách được thu thập từ cảm được tổ chức như sau: Mục 2 trình bày định biến. hướng di chuyển cho robot dựa trên bản đồ. Giá trị khoảng cách tác động được tính Mục 3 và 4 giới thiệu tóm tắt thuật toán toán theo mỗi một góc hình quạt thứ như tránh vật cản và các thuật toán nhận dạng. minh họa trong hình 1, mỗi góc có độ lớn là 훼 Kết quả thực nghiệm được trình bày trong 휏, số góc hình quạt 푛 = , với 훼 là góc nhìn 휏 mục 5. Mục 6 rút ra các kết luận. của camera. Giá trị khoảng cách tác động 2. Định hướng dựa trên bản đồ được tính theo công thức: Việc định hướng của robot dựa trên mô ℎ = ∗2 − (1) hình hình học hoặc bản đồ tô pô về môi ∗ trường do người sử dụng tạo ra. Robot định : giá trị chắc chắn của ô góc hình quạt vị trí dựa trên encoder kết hợp với những thứ . điểm mốc được gắn trên đường di chuyển. : khoảng cách bé nhất từ robot đến các Robot sử dụng bản đồ được cung cấp sẵn để điểm ảnh trong một góc hình quạt thứ ước lượng vị trí hiện tại của nó bằng cách , : là những hằng số dương so sánh điểm mốc phát hiện và điểm mốc ℎ : giá trị khoảng cách tác động tại góc định sẵn trong bản đồ. Các bước trong việc hình quạt thứ định vị trí của robot được chia như sau: h Lấy thông tin từ cảm biến: đối với định k hướng dựa trên thị giác thì bước này là thu thập và xử lý ảnh từ camera. Phát hiện điểm mốc: việc phát hiện Ngưỡng tác điểm mốc thông qua thị giác máy tính, động vật mốc có thể được phát hiện nhờ nhận dạng về hình dáng, kích thước hoặc màu sắc. So sánh giữa điểm mốc với điểm mốc −훼 0 훼/2 k tương ứng trong bản đồ: sau khi phát /2 0 hiện điểm mốc thì robot sẽ tra tìm trong Hình 1. Biểu đồ histogram. tập dữ liệu trên bản đồ để tìm ra vị trí 3.2 Tính góc lái điểm mốc tương ứng. Việc tính toán góc lái cho robot phải dựa Tính toán vị trí: Khi đã xác định được vào việc xác định vùng an toàn. Vùng an điểm mốc tương ứng thì robot sẽ định vị toàn để robot di chuyển là vùng có số lượng được vị trí của nó trên bản đồ. cung liên tiếp nhiều nhất 푠 mà giá trị ℎ 3. Tránh vật cản không vượt qua ngưỡng tác động. Vùng an toàn được giới hạn bởi hai cung biên là , Thuật toán tránh vật cản được xây dựng 푡 như trong hình 2, trong đó là cung dựa trên thuật toán VHF (Vector Field 푡 Historgram) [3] bao gồm hai bước cơ bản là gần nhất bên trái, cung gần nhất bên xây dựng biểu đồ histogram về môi trường phải xác định bởi công thức: và tính góc lái di chuyển robot. = 푡 + 푠 (2) 3.1 Xây dựng biểu đồ histogram Góc lái của robot được cho bởi công thức: Xây dựng biểu đồ histogram về môi trường là một bước quan trọng làm nền tảng 휃 = 푡 + /2 (3) cho việc xác định vật cản, tính toán góc lái 2
3. 휃 hoặc di chuyển qua các phòng. Phương pháp để xác định được cửa trong ảnh dựa 푡 trên thuật toán phát hiện biên Canny và Vùng an toàn biến đổi Hough. Vật cản Vật cản 4.1.1 Đặc điểm cửa Đối với một cửa ra vào thì có rất nhiều hình dạng khác nhau song đặc điểm chung và dễ nhận biết nhất ở một cánh của đó là khung cửa. Hình dáng khung cửa thường là hình chữ nhật. Thực tế hình dạng khung cửa Hình 2. Góc lái θ của robot. mà robot có thể xác định được là là chữ U 4. Nhận dạng ngược hoặc 2 cạnh bên song song như hình 3. 4.1 Nhận dạng điểm mốc Để có thể xác định một điểm mốc có màu sắc, robot cần tìm được vùng màu sắc của điểm mốc trên hình ảnh thu về từ camera. Đối với ảnh màu RGB thì rất khó có thể xác định do nó dựa trên ba màu cơ bản, ngoài ra trong vùng màu thì cường độ Hình 3. Hình dáng đặc trưng khung cửa tại mỗi điểm lại không đồng nhất nên các (a) dạng U ngược (b) dạng hai cạnh bên giá trị trên mỗi điểm khác nhau. Do đó cần Một khung cửa có 4 đặc điểm cơ bản: chuyển ảnh màu RGB sang ảnh màu HSI, hướng khung cửa là hướng đứng, chiều cao vì đặc điểm của ảnh HSI giống với việc mô khoảng 2,5m so với mặt sàn, dạng hình chữ tả và giải thích màu sắc của con người. Một nhật và kích thước chiều rộng có thể qua điểm màu được mô tả trong không gian được. Robot dễ bị nhầm đặc điểm hướng màu HSI qua ba thành phần chính là màu trục đứng với các thành phần khác trong sắc (hue), độ bão hòa (saturation) và cường môi trường như cạnh tường hoặc đồ vật có độ sáng (intensity).Vì thế việc lựa chọn khung đứng. chiều cao thì robot khó có thể thông số màu mẫu và bước so sánh màu đo được. Nên chỉ có 2 đặc điểm hình dáng phải dựa trên những thuộc tính này, trong và kích thước chiều rộng là dễ nhận biết và đó màu sắc là thành phần lựa chọn chính do tính toán. Khung cửa có 2 thành phần là các thành phần còn lại có thể bị thay đổi khi cạnh trên và 2 cạnh bên, để xác định các nguồn sáng thay đổi. thành phần này cần sử dụng thuật toán Sau khi chọn thông số màu mẫu, thông Canny và biến đổi Hough. Thuật toán số màu sắc ở từng điểm ảnh sẽ được so Canny dùng để phát hiện cạnh và biến đổi sánh với thông số màu mẫu. Nếu điểm ảnh Hough để tìm đường thẳng trong ảnh. có cùng thông số màu với màu mẫu thì thì điểm đó sẽ có độ sáng lớn nhất 255 (tương 4.1.2 Thuật toán phát hiện cửa ứng với mức trắng) ngược lại có độ sáng bé Thuật toán phát hiện cửa bao gồm sáu nhất là 0 (tương ứng với mức tối) trong ảnh bước chính được trình bày trong hình 4. mức xám. Sau quá trình so sánh, trên ảnh so Trong thuật toán phát hiện cửa, ảnh được sánh sẽ xuất vùng điểm ảnh sáng, và đó xử lý qua hai bước phát hiện cạnh Canny và chính là vùng điềm mốc cần tìm. biến đổi hough để tìm ra các đường thẳng. 4.2 Nhận dạng cửa Khung cửa có đặc tính phương đứng đối với hai cạnh bên và phương ngang đối với Phát hiện cửa là một trong những bài cạnh trên nên các đường thẳng không phải toán thường gặp trong những ứng dụng phương ngang và phương đứng sẽ được loại trong nhà. Robot sẽ phải nhận biết và đi qua bỏ. Trong bước tiếp theo, nếu phát hiện cửa trong khi di chuyển trong hành lang 3
4. cạnh trên thì đưa ra giả thiết cửa có ba cạnh, bên thì giả thiết đưa ra là cửa có hai cạnh sau đó tìm hai cạnh bên có vị trí ngay bên bên và nếu không quay lại bước đầu tiên. dưới cạnh trên. Nếu chỉ tìm thấy hai cạnh Start Tải ảnh Phát hiện cạnh Canny Biến đổi Hough Giả thiết cửa có 3 Tìm cạnh trên Đúng cạnh Kiểm chứng giả Sai Sai thiết Sai Đúng Giả thiết cửa có 2 Tìm hai cạnh bên Đúng cạnh bên Xác định vị trí cửa End Hình 4. Thuật toán phát hiện cửa Các giả thiết đưa ra có thể không đúng vì xác định được những điểm nổi bật này thế cần kiểm chứng giả thiết, việc kiểm thì cách thức được sử dụng là đạo hàm chứng dựa trên việc đo chiều dài cạnh trên kết hợp. và độ rộng của hai cạnh bên. Đối với giả Start thiết cửa có ba cạnh thì phải so sánh giữa chiều dài cạnh trên và độ rộng hai cạnh Phát hiện điểm nổi bật bên, còn giả thiết cửa có hai cạnh thì chỉ kiểm tra độ rộng của hai cạnh bên. Khi các Xây dựng bộ mô tả giả thiết được kiểm định, nếu giả thiết đặc điểm đúng thì bước cuối cùng là tìm vị trí của cửa nếu không thì quay lại bước ban đầu. So khớp các bộ mô tả 4.3 Nhận dạng vật thể đích Phương pháp nhận dạng được sử dụng End ở dây là phương pháp nhận dạng SURF Hình 5.Thuật toán nhận dạng SURF (Speeded Up Robust Features) [9]. Phương Trong phương pháp SURF, ma trận pháp này bao gồm ba bước cơ bản được đạo hàm Hessian được sử dụng cho việc trình bày trong hình 5. phát hiện các điểm nổi bật, bởi vì thuật toán có hiệu năng cao về thời gian tính Điểm nổi bật: trong giai đoạn đầu tiên toán và độ chính xác. Xét tại một điểm A các thành phần điểm ảnh nổi bật sẽ được có tọa độ , trên một ảnh I, Ma trận dò tìm và được tập hợp thành tập dữ liệu đạo hàm Hessian ℋ , 휎 tại điểm A với dò tìm, những thành phần này được xem tỷ lệ thay đổi kích thước 휎 được cho bởi như ”vị trí mỏ neo” trong ảnh. Một thành công thức: phần điểm ảnh được gọi là nổi bật khi thành phần này miêu tả một phần vật thể 퐿 , 휎 퐿 , 휎 ℋ , 휎 = (4) và không thay đổi dù cho các thuộc tính 퐿 , 휎 퐿 , 휎 như kích thước, nguồn sáng của ảnh thay Trong đó 퐿 , 휎 , 퐿 , 휎 , 퐿 , 휎 đổi. Thông thường tại những vùng điểm lần lượt là tích chập của đạo hàm bậc hai ảnh đó cường độ sáng bị gián đoạn, Để 4
5. 휕2 휕2 휕2 hàm Gausse 𝑔 휎 , 𝑔 휎 , 𝑔 휎 휕 2 휕 휕 휕 2 với ảnh I tại điểm A. Bộ mô tả: các thành phần đặc điểm cục bộ sau khi dò tìm cần phải xây dựng bộ mô tả các thành phần này. Bộ mô tả biểu thị mối quan hệ về mặt không gian giữa các thành phần đặc điểm cục bộ với các điểm ảnh lân cận nhằm mục đích xác định vị trí của các thành phần này trong ảnh. Yêu cầu cho một bộ mô tả là phải đảm bảo phân biệt được các thành phần Hình 6. Mô hình hệ thống robot. đặc điểm của vật thể trong một tập dữ liệu và không bị ảnh hưởng bởi tập dữ 5.2 Thực nghiệm thuật toán quy hoạch liệu dò tìm. quỹ đạo So khớp: Khi nhận dạng vật thể trong Kết quả thực nghiệm thuật toán quy một ảnh, các đặc điểm cục bộ cũng được hoạch quỹ đạo cho robot di động trình bày phát hiện theo cách thức giống như đối trong hình với ảnh mẫu. Sau đó các bô miêu tả trong ảnh sẽ được so khớp với bộ miêu tả trong cơ sở dữ liệu. Quá trình so khớp là việc tính toán khoàng cách Ơclit hoặc Mahalanobis giữa đặc điểm của ảnh và đặc điểm trong cơ sở dữ liệu, nếu khoảng cách này nằm trong khoảng cho phép thì hai bộ mô tả là tương đồng nhau. 5. Kết quả thực nghiệm 5.1 Mô hình robot di động thực nghiệm Mô hình hệ thống robot di động dùng trong thực nghiệm được trình bày trong hình 6. Đây là mô hình robot được thiết kế Hình 7. Kết quả snapshot từ 0s đến 28s trong [10]. Chương trình điều khiển robot dùng phần mềm mã nguồn mở Player trên nền Linux dạng client/server. Chương trình điều khiển đóng vai trò client trao đổi dữ liệu với robot thông qua phần mềm Player đóng vai trò server. Thư viện mobilerobot trên Player cung cấp các hàm giao tiếp với robot. Phần cứng robot gồm các khối: cơ cấu chuyển động, hệ thống cảm biến gồm 12 sonar, một la bàn số và 2 encoder gắn trên trục động cơ của 2 bánh xe. Một microcontroller làm nhiệm vụ giao tiếp các Hình 8. Kết quả snapshot từ 32s đến 60s thành phần của robot với Player. Robot được trang bị camera Kinect nối với máy tính qua cổng USB. 5
6. [2] G. N. DeSouza, and A. C. Kak, “Vision for mobile robot navigation: a survey,” IEEE trans.on Pattern Analysis and Machine Intelligence, vol. 24, no. 2, pp. 237 - 267, 2002. [3] J. Borenstein, and Y. Koren, “The Vector Field Histogram – Fast Obstacle Avoidance for Mobile Robots,” IEEE Journal of Robotics and Automation, vol. 7, no. 3, pp. 278 - 288, June 1991. [4] D. Kim, and R. Nevatia, “Representation and Computation of Hình 9. Kết quả snapshot từ 64s đến 92s the Spatial Environment for Indoor Navigation,” Proc. Int’l Conf.Computer Vision and Pattern Recognition, pp. 475-482, 1994. [5] S. Atiya, and G. D. Hager, “Real-Time Vision-Based Robot Localization,” IEEE Trans. Robotics and Automation, vol. 9, no. 6, pp. 785 - 800, Dec. 1993. [6] M. J. SWAIN, and D. H. BALLARD, “Color Indexing,” International Journal of Computer Vision, vol. 7, no. 1, pp. 11 - 32, 1991. Hình 10. Kết quả snapshot từ 96s đến 124s [7] H. Murase, and S. Nayar, “Visual Learning and Recognition of 3D 6. Kết luận Objects from Appearance,” Bài báo đã giới thiệu thuật toán quy International Journal of Computer hoạch quỹ đạo cho robot di động dựa trên Vision, vol. 14, pp. 5-24, 1995. thị giác máy tính. Các kết quả thực nghiệm [8] T. Tuytelaars, and K. Mikolajczyk, cho thấy hiệu quả tốt của thuật toán khi áp “Local Invariant Feature Detectors: A dụng trên robot thực nghiệm. Tuy nhiên Survey,” Foundations and Trends in môi trường áp dụng cho robot còn đơn Computer Graphics and Vision, vol. 3, giản và phụ thuộc vào bản đồ được cung no. 3, pp. 177–280, 2007. cấp, vì thế chúng tôi tin rằng với việc cải [9] H. Bay, T. Tuytelaars, and L. V. Gool, thiện thuật toán tốt hơn về sau này sẽ giúp “SURF: Speeded up robust features,” robot di chuyển được trong những môi Proceedings of the Ninth European trường phức tạp hơn, không gian rộng hơn Conference on Computer Vision pp. và robot có khả năng tự xây dựng bản đồ 404–417, 2006. môi trường. [10] N. H. Đông, Xây dựng mô hình robot di động và mã nguồn mở trên chương Tài liệu tham khảo trình Player, Đại học Sư Phạm Kỹ [1] G. Bradski, and A. Kaehler, "Learning Thuật TP HCM, 2011. OpenCV: Computer Vision with the OpenCV Library," O’Reilly, 2008, p. 555. 6
7. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam. Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh. ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN! Thực hiện theo MTCL & KHTHMTCL Năm học 2016-2017 của Thư viện Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh.