Luận văn Định vị robot dựa trên kỹ thuật xử lý hình ảnh (Phần 1)

Nội dung text: Luận văn Định vị robot dựa trên kỹ thuật xử lý hình ảnh (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH LUẬN VĂN THẠC SĨ NGÔ THANH ĐÔNG ĐỊNH VỊ ROBOT DỰA TRÊN KỸ THUẬT XỬ LÝ HÌNH ẢNH NGÀNH: KỸ THUẬT ĐIỆN TỬ - 60520203 S K C0 0 4 6 4 4 Tp. Hồ Chí Minh, tháng 10/2015
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH LUẬN VĂN THẠC SĨ NGÔ THANH ĐÔNG ĐỊNH VỊ ROBOT DỰA TRÊN KỸ THUẬT XỬ LÝ HÌNH ẢNH NGÀNH: KỸ THUẬT ĐIỆN TỬ - 60520203 Hƣớng dẫn khoa học: TS LÊ MỸ HÀ Tp. Hồ Chí Minh, tháng 10 năm 2015
3. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà LÝ LỊCH KHOA HỌC I. LÝ LỊCH SƠ LƢỢC: Họ & tên: Ngô Thanh Đông Giới tính: Nam Ngày, tháng, năm sinh: 19/03/1984 Nơi sinh: Quảng Ngãi Quê quán: Quảng Ngãi Dân tộc: Kinh Chỗ ở riêng hoặc địa chỉ liên lạc: A10/26A9, khu phố 2, Xã Bình Hƣng, Bình Chánh, TP.HCM Điện thoại cơ quan: Điện thoại di động: 0974903612 Fax: E-mail: thanhdong_ngo@yahoo.com II. QUÁ TRÌNH ĐÀO TẠO: 1. Trung học chuyên nghiệp: Không học 2. Đại học: Hệ đào tạo: Chính quy Thời gian đào tạo từ 2003 đến 2008 Nơi học (trƣờng, thành phố): Trƣờng Đại học Sƣ phạm Kỹ thuật TP.HCM Ngành học: Kỹ thuật Điện – Điện tử Tên đồ án, luận án hoặc môn thi tốt nghiệp: Giám sát và điều khiển nhiệt độ dùng WINCC. Ngày & nơi bảo vệ đồ án, luận án hoặc thi tốt nghiệp: Trƣờng Đại học Sƣ phạm Kỹ thuật TP.HCM Ngƣời hƣớng dẫn: Ths. Nguyễn Tấn Đời III. QUÁ TRÌNH CÔNG TÁC CHUYÊN MÔN KỂ TỪ KHI TỐT NGHIỆP ĐẠI HỌC: Thời gian Nơi công tác Công việc đảm nhiệm Trƣờng Cao đẳng nghề Việt 2009 đến nay Giáo viên Nam – Singapore Trang I
4. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác. Tp. Hồ Chí Minh, ngày 18 tháng 10 năm 2015 (Ký tên và ghi rõ họ tên) Ngô Thanh Đông Trang II
5. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà LỜI CẢM ƠN Tôi xin chân thành cảm ơn Ban giám hiệu trƣờng Đại học SPKT TP.HCM đã tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập nâng cao trình độ và thực hiện đề tài luận văn tốt nghiệp này. Tôi cũng xin trân trọng cảm ơn TS. Lê Mỹ Hà đã tận tình giúp đỡ, truyền đạt kiến thức và đề xuất hƣớng giải quyết các vấn đề khó khăn phát sinh trong quá trình nghiên cứu. Và cuối cùng tôi xin cảm ơn các bạn bè, đồng nghiệp, đã ủng hộ tôi, cộng tác với tôi, tạo mọi mọi điều kiện thuận lợi nhất cho tôi hoàn thành luận văn này. Ngô Thanh Đông Trang III
6. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà TÓM TẮT LUẬN VĂN Định vị robot là đề tài đƣợc nhiều nhà khoa học trong nƣớc và thế giới quan tâm. Ngƣời ta thƣờng dùng các loại cảm biến để tính toán khoảng cách, hƣớng, vận tốc để xác định vị trí robot. Vì các loại cảm biến vẫn còn sai số, những yếu tố khách quan nhƣ robot bị trƣợt trong quá trình di chuyển, đã làm cho vấn đề định vị robot vẫn chƣa đƣợc giải quyết triệt để. Các nhà nghiên cứu đã đƣa ra nhiều giải pháp khác nhau nhƣ là định vị robot bằng cách phát hiện vật mốc RFID, sử dụng camera Kinect, stereo camera, GPS Để đạt đƣợc kết quả tốt hơn, trong đề tài này tác giả định vị robot sử dụng camera kết hợp GPS. Đề tài thực hiện định vị robot sử dụng camera. Robot đƣợc trang bị một camera thƣờng, trong quá trình di chuyển nó sẽ thu thập những ảnh 2D, xử lý tập ảnh này, tính toán xác định vị trí và lập quỹ đạo của robot. Tuy nhiên định vị robot sử dụng camera thì chƣa thể xác định vị trí chính xác của robot trên tọa độ mặt đất. Đề tài cũng thực hiện định vị robot sử dụng Module GPS để thu thập dữ liệu kinh độ và vĩ độ. Từ đó xác định vị trí của robot trên bản đồ mặt đất. Nhƣng định vị robot sử dụng GPS cho kết quả chƣa mịn. Kết hợp hai kết quả trên, định vị robot sử dụng camera kết hợp GPS cho kết quả tốt hơn. Robot xác định đƣợc vị trí của mình trên tọa độ mặt đất, quỹ đạo di chuyển của robot đƣợc xác định mịn hơn. Trang IV
7. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà ABSTRACT Location for robot is a subject which is interested by many researchers. They often use sensors to measure the distance, orientation and velocity to determine navigation of robot. Because sensors still have errors and many external factors such as slipping during moving, the problem of locating robot has not solved thoroughly. Researchers gave many various methods for locating robot such as: RFID, using Kinect camera, stereo camera, GPS, In order to gain better result, in this thesis, navigation of robot fusing camera and GPS is used. Locating robot using camera in this thesis, camera is attached on robot, during the movement, it will collect a set of 2D images. Processing this set of pictures, counting location and mapping the trajectory of robot. But the result of this process cannot give the global location Locating robot using Module GPS is also implemented in this thesis to getting longitude and latitude. From that global location of robot is determined. But this result is not smooth. Fusing camera and GPS gives better result. Robot is located its navigation on glocal map, trajectory of robot is smoother. Trang V
8. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà MỤC LỤC ABSTRACT V MỤC LỤC VI DANH SÁCH CÁC HÌNH IX DANH SÁCH CÁC CHỮ VIẾT TẮT XI Chƣơng 1. 1 TỔNG QUAN 1 1.1. Tổng quan về lĩnh vực nghiên cứu, các kết quả nghiên cứu trong và ngoài nƣớc đã công bố 1 1.1.1. Tổng quan về định vị robot 1 1.1.2. Kết quả nghiên cứu trong và ngoài nƣớc 2 1.2. Mục tiêu, khách thể và đối tƣợng nghiên cứu 3 1.2.1. Mục tiêu nghiên cứu 3 1.2.2. Khách thể nghiên cứu 3 1.2.3. Đối tƣợng nghiên cứu 4 1.3. Nhiệm vụ của đề tài và phạm vi nghiên cứu 4 1.3.1. Nhiệm vụ của đề tài 4 1.3.2. Phạm vi nghiên cứu 4 1.4. Phƣơng pháp nghiên cứu 4 Chƣơng 2. 6 CƠ SỞ LÝ THUYẾT 6 2.1. Tìm cặp điểm đặc trƣng tƣơng đồng 6 2.1.1. Các loại đặc trƣng 6 Trang VI
9. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà 2.1.2. Harris Laplace 6 2.1.3. SIFT 6 2.1.4. SURF 11 2.1.5. Moravec corner 11 2.1.6. Harris corner 12 2.2. Thông số nội camera 15 2.3. Thuật toán RANSAC 19 2.4. Định vị camera dựa trên điểm tƣơng đồng 21 2.4.1. Hình học Epipolar và ma trận cơ bản 21 2.4.2. Ma trận thiết yếu và thông số ngoại camera 22 2.5. Hệ thống định vị toàn cầu GPS 23 2.5.1. Tổng quan về GPS 23 2.5.2. Các thành phần của hệ thống định vị GPS 23 2.5.3. Chuẩn NMEA 25 Chƣơng 3. 29 ĐỊNH VỊ ROBOT DI ĐỘNG NGOÀI TRỜI 29 3.1. Xác định vị trí robot dựa vào camera 29 3.1.1. Tìm thông số nội camera 30 3.1.2. Trích rút đặc trƣng 32 3.1.3. Mô tả cặp đặc trƣng tƣơng đồng 33 3.1.4. Ƣớc lƣợng vị trí camera 34 3.2. Xác dịnh vị trí robot dùng GPS 36 3.2.1. Thu thập dữ liệu GPS 36 Trang VII
10. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà 3.2.2. Xác định vị trí robot dựa trên dữ liệu GPS 40 3.3. Xác định vị trí robot dùng camera kết hợp GPS 42 Chƣơng 4. 43 KẾT QUẢ MÔ PHỎNG VÀ THỰC NGHIỆM 43 4.1. Kết quả định vị robot dùng camera 43 4.2. Kết quả định vị robot dùng GPS 45 4.3. Kết quả định vị robot kết hợp camera và GPS 46 Chƣơng 5. 50 KẾT LUẬN 50 5.1. Kết quả đạt đƣợc 50 5.2. Hạn chế của đề tài 50 5.3. Hƣớng phát triển của đề tài 51 TÀI LIỆU THAM KHẢO 56 Trang VIII
11. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà DANH SÁCH CÁC HÌNH Hình 1.1: Dùng xe ô tô đƣợc trang bị thiết bị định vị GPS để lập bản đồ 2 Hình 2.1: Phƣơng pháp tính DoG 7 Hình 2.2: Tìm điểm đặc trƣng từ các giá trị DoG. 8 Hình 2.3: Mô hình Pinhold 15 Hình 2.4: Hệ tọa độ tƣơng đƣơng mô hình Pinhold 16 Hình 2.5: Quan hệ giữa tọa độ camera và tọa độ không gian 18 Hình 2.6: Tập dữ liệu đƣờng thẳng 20 Hình 2.7: Tìm đƣờng thẳng dùng thuật toán RANSAC 20 Hình 2.8: Mô tả hình học Epipolar 21 Hình 2.9: Các thành phần của hệ thống định vị GPS 23 Hình 2.10: Bố trí vệ tinh trên không gian 24 Hình 2.11: Vị trí các trạm điều khiển và giám sát GPS 25 Hình 3.1: Lƣu đồ định vị robot dựa vào camera 29 Hình 3.2: Tập ảnh bàn cờ 31 Hình 3.3: Bộ phát hiện đốm và bộ phát hiện góc 32 Hình 3.4: Ảnh sau khi thực hiện lọc đốm và lọc góc 32 Hình 3.5: Điểm đặc trƣng đốm và đặc trƣng góc 33 Hình 3.6: Bộ lọc Sobel 34 Hình 3.7: Cặp điểm đặc trƣng tƣơng đồng 34 Hình 3.8: Module SIM968 [19] 36 Hình 3.9: Sơ đồ mạch cung cấp nguồn chân VBAT [19] 37 Trang IX
12. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà Hình 3.10: Thời gian mở SIM968 [19] 37 Hình 3.11: Kết nối giao tiếp nối tiếp [19] 38 Hình 3.12: Ảnh chụp mặt đất từ 4 điểm P1P2P3P4 40 Hình 3.13: Hệ trục tọa độ ảnh mặt đất 41 Hình 4.1: Ô tô thu thập dữ liệu 43 Hình 4.2: Cặp điểm đặc trƣng tƣơng đồng của hai ảnh liên tiếp 44 Hình 4.3: Tọa độ vị trí camera trong hai khung ảnh đầu tiên 45 Hình 4.4: Bản đồ 2D dùng tập ảnh camera 45 Hình 4.5: Kết quả định vị robot trong quá trình di chuyển dùng GPS 46 Hình 4.6: Sai số toàn cục của định vị dùng camera 47 Hình 4.7: Sai số toàn cục của định vị dùng GPS 47 Hình 4.8: Định vị robot dùng camera kết hợp GPS 48 Hình 4.9: Quỹ đạo của robot bị mất một phần do tín hiệu từ camera 48 Hình 4.10: Quỹ đạo robot sau khi đƣợc bổ sung bởi tín hiệu GPS 49 Hình 5.1: Sai số định vị trong khuôn viên có nhiều đối tƣợng di chuyển 51 Trang X
13. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà DANH SÁCH CÁC CHỮ VIẾT TẮT SFM: Structure from motion RANSAC: Random sample consensus SIFT: Scale invariant feature transform IR: Infrared radiation GPS: Global Positioning System NMEA: National Marine Electronics Association DCE: Data Communication Equipment DTE: Data Terminal Equipment RFID: Radio Frequency Identification SAD: Sum of Absolute Differences Trang XI
14. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà Chƣơng 1. TỔNG QUAN 1.1. Tổng quan về lĩnh vực nghiên cứu, các kết quả nghiên cứu trong và ngoài nƣớc đã công bố 1.1.1. Tổng quan về định vị robot Định vị cho robot di động nhằm xác định chính xác vị trí của robot trên bản đồ đƣợc nghiên cứu từ rất lâu và đã đạt đƣợc nhiều thành công lớn. Phƣơng pháp định vị cổ điển là dựa vào các loại cảm biến để tính toán khoảng cách, hƣớng, gia tốc trên cơ sở đó ƣớc lƣợng và quyết định quỹ đạo di chuyển của robot. Bên cạnh những thành tựu đó, những nhƣợc điểm khách quan do sai số từ các cảm biến đƣa về cho robot cũng không thể loại bỏ, vì thế mục tiêu trên vẫn chƣa đƣợc giải quyết triệt để. Việc điều khiển robot chỉ dựa vào các cảm biến trên robot thôi vẫn chƣa đủ để giải quyết vấn đề trên. Dần dần, các nhà nghiên cứu nhận thấy rằng cần phải phối hợp, tƣơng tác với môi trƣờng xung quanh, giúp robot thêm nhiều thông tin có thể trả lời đúng câu hỏi “tôi đang ở đâu?”. Định vị robot sử dụng GPS, robot đƣợc gắn thêm thiết bị định vị toàn cầu GPS. Thiết bị giúp robot xác định khoảng cách tới 3 hoặc 4 vệ tinh đã xác định trƣớc ngoài vũ trụ, để từ đó tính toán vị trí của robot. Tuy nhiên kết quả này chỉ phù hợp với khu vực có quy mô lớn. Độ chính xác định vị dùng GPS không cao, sai số có thể lên vài mét. Định vị robot sử dụng thiết bị Kinect. Thiết bị Kinect có một camera RGB và một camera IR, robot vừa thu thập hình ảnh nhờ camera RGB vừa thu thập độ sâu của ảnh nhờ camera IR. Từ đó robot tính toán khoảng cách từ robot đến vật cản trong môi trƣờng xung quanh và xác định vị trí của robot trong môi trƣờng. Bài toán lập bản đồ và định vị cho robot đƣợc chia làm 2 loại: định vị cho robot trong nhà và ngoài trời. Lập bản đồ và định vị cho robot ngoài trời gặp Trang 1
15. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà nhiều khó khăn hơn trong nhà vì địa hình gồ ghề hơn, môi trƣờng phức tạp hơn và quy mô rộng lớn hơn. Robot ngày càng đƣợc trang bị những cảm biến nhƣ con ngƣời, thị giác robot là camera gắn trên robot nhằm thu thập và xử lý hình ảnh. Robot tự hành đơn giản chỉ đƣợc trang bị một camera mà không cần bất kỳ cảm biến nào đã có thể tự quyết định đƣợc hành vi di chuyển của robot và hoạt động trong môi trƣờng mới mà hoàn toàn chƣa biết trƣớc bản đồ. 1.1.2. Kết quả nghiên cứu trong và ngoài nƣớc Lập bản đồ có nhiều cách thức khác nhau nhƣ dùng thiết bị định vị toàn cầu GPS gắn trên ô tô nhƣ Hình 1.1. Khi ô tô di chuyển, tọa độ hiện tại của ô tô luôn đƣợc cập nhật gửi về máy chủ. Từ đó máy chủ sẽ tính toán và vẽ đƣợc bản đồ 2D của môi trƣờng mà ô tô di chuyển. Tuy nhiên, độ chính xác của thiết bị GPS không tốt, sai số từ vài mét cho đến vài chục mét. Do đó, phƣơng pháp định vị dùng GPS chỉ thích hợp với việc lập bản đồ ở quy mô lớn. Hình 1.1: Dùng xe ô tô đƣợc trang bị thiết bị định vị GPS để lập bản đồ Trong bài viết của tác giả Nguyễn Minh Thức, định vị cho robot di động sử dụng GPS [1], robot di chuyển và định vị dựa vào tín hiệu GPS, tuy nhiên trong đề tài còn hạn chế là robot không thể tránh nhiều vật cản gần nhau. Lập bản đồ 3D và 2D sử dụng stereo camera [2], tác giả dùng stereo camera gắn trên xe lăn để xây dựng bản đồ 3D, từ đó phát hiện vật cản, điều khiển xe lăn di chuyển an toàn mà không cần sự điều khiển của ngƣời tàn tật. Định vị robot dựa trên cơ sở xử lý ảnh stereo camera và có tích hợp GPS [3], tác giả dựa vào GPS để định vị vị trí robot trên mặt đất trong khoảng không Trang 2
16. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà gian rộng lớn. Mỗi lúc robot di chuyển với khoảng cách nhỏ, tác giả ƣớc lƣợng sự di chuyển này dựa vào xử lý cặp ảnh chụp từ stereo camera. Một mô hình định vị và lập bản đồ thời gian thực đối với đối tƣợng 3D [4]. Tác giả tạo một tập dữ liệu các đối tƣợng 3D. Bản đồ đƣợc xây dựng từng bƣớc trực tiếp dựa vào đối tƣợng. Một máy ảnh chụp nhiều ảnh của đối tƣợng, giải thuật nhận diện đối tƣợng 3D và tạo ra bản đồ 3D thể hiện vị trí các đối tƣợng liên quan trong tập dữ liệu. Bản đồ đƣợc tối ƣu hóa liên tục các phép đo mới và luôn cập nhật các dự đoán của phép đo camera kế tiếp. 1.2. Mục tiêu, khách thể và đối tƣợng nghiên cứu 1.2.1. Mục tiêu nghiên cứu Mục tiêu đề tài này là xác định vị trí và lập bản đồ robot trong quá trình di chuyển. Đề tài chƣa làm đến điều khiển robot nên robot đƣợc xem nhƣ một phƣơng tiện di chuyển cụ thể là một ô tô. Robot/ô tô sẽ dùng camera chụp các ảnh 2D trong quá trính di chuyển để ƣớc lƣợng vị trí camera đƣợc gắn trên nó, sau đó tính toán vị trí và hƣớng của nó trong không gian đang tƣơng tác. GPS cho biết vị trí của đối tƣợng trên bản đồ mặt đất, nhƣng sai số lớn. Kết hợp hai thiết bị có thể xác định vị trí của robot chính xác hơn hoặc trong trƣờng hợp một trong hai thiết bị mất tín hiệu thì tín hiệu còn lại đƣợc bổ sung để đảm bảo tính liên tục của tín hiệu. 1.2.2. Khách thể nghiên cứu Đề tài nghiên cứu dựa vào các thuật toán để trích đặc trƣng của hai ảnh liên tiếp. Dùng giải thuật 8 điểm để tìm ma trận cơ bản từ hai tập dữ liệu đặc trƣng. Dựa trên cơ sở hình học Epipolar để xác định khoảng cách và hƣớng camera của hai ảnh. Bên cạnh đó kết hợp sử dụng GPS để xác định vị trí của đối tƣợng trên tọa độ trái đất. Trang 3
17. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà 1.2.3. Đối tƣợng nghiên cứu Robot đƣợc trang bị camera và GPS thu thập dữ liệu trong quá trình di chuyển. Tập ảnh 2D đƣợc trích từ camera kết hợp với dữ liệu GPS để xác định vị trí của robot. 1.3. Nhiệm vụ của đề tài và phạm vi nghiên cứu 1.3.1. Nhiệm vụ của đề tài Để đạt đƣợc mục tiêu nghiên cứu cần thực hiện các nhiệm vụ sau: - Tìm hiểu lý thuyết về lập bản đồ và định vị robot - Tìm hiểu về xử lý ảnh: các phép toán trong xử lý ảnh, trích đặt trƣng từ ảnh, loại bỏ những đặt trƣng yếu - Thuật toán trích đặt trƣng đốm và góc từ một hình ảnh - Thuật toán RANSAC loại bỏ các đặc trƣng yếu của một hình ảnh - Xác định vị trí và góc quay camera để tìm vị trí và hƣớng của robot dựa vào phƣơng pháp visual odometry - Tìm hiểu về module SIM968 để thu thập dữ liệu GPS 1.3.2. Phạm vi nghiên cứu Đề tài này tập trung nghiên cứu trên tập ảnh 2D và dữ liệu GPS. Tập dữ liệu này đƣợc thu thập dùng camera và GPS đƣợc trang bị trên ô tô trong quá trình di chuyển trong khuôn viên trƣờng Đại Học Sƣ Phạm Kỹ Thuật Thành Phố Hồ Chí Minh. Trên tập dữ liệu này đề tài mô phỏng tính toán và định vị vị trí xe trong bản đồ trái đất. 1.4. Phƣơng pháp nghiên cứu Phƣơng pháp nghiên cứu của đề tài là tạo tập dữ liệu gồm nhiều ảnh liên tiếp nhau trong quá trình di chuyển trên một bản đồ biết trƣớc. Từ những ảnh thu đƣợc thực hiện qua bộ lọc đốm và góc để tìm đặc trƣng của ảnh, với hai bộ đặc Trang 4
18. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà trƣng của hai ảnh tìm các cặp điểm đặc trƣng tƣơng đồng của hai ảnh. Từ cặp điểm đặc trƣng tƣơng đồng dựa vào cơ sở toán hình học Epipolar tìm ma trận cơ bản, ma trận thiết yếu và từ đó tìm ma trận thông số ngoại (thể hiện vị trí và hƣớng) camera để xác định vị trí cục bộ robot. Kết hợp với dữ liệu GPS xác định vị trí robot trên bản đồ trái đất. Trang 5
19. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà Chƣơng 2. CƠ SỞ LÝ THUYẾT Nội dung chƣơng 2 trình bày về xử lý ảnh trích đặc trƣng, giải thuật RANSAC để loại bỏ những đặc trƣng yếu, cách xác định các thông số camera. Trình bày về tổng quan hệ thống định vị GPS. 2.1. Tìm cặp điểm đặc trƣng tƣơng đồng 2.1.1. Các loại đặc trƣng Để tìm vị trí robot từ nhiều ảnh, việc tìm đặc trƣng của ảnh cho phù hợp là việc quan trọng và then chốt. Việc lựa chọn các đặc trƣng sẽ giúp tăng độ chính xác của vị trí, hƣớng và tốc độ xử lý của robot. Những năm gần đây việc sử dụng các đặc trƣng cục bộ đã trở thành một hƣớng mới trong định vị robot bằng kỹ thuật xử lý ảnh. Các điểm đặc trƣng này là bất biến trong phép biến đổi hình học, phép biến đổi affine. 2.1.2. Harris Laplace Harris Laplace là thuật toán tìm điểm đặc trƣng cải tiến từ thuật toán tìm điểm đặc trƣng Harris. Thuật toán đƣợc đƣa ra nhằm giải quyết vấn đề biến đổi theo tỉ lệ mà thuật toán Harris corner chƣa khắc phục đƣợc. Harris Laplace đƣa ra giải pháp có thể lựa chọn tỉ lệ tự động trong quá trình trích điểm đặc trƣng từ ảnh. Thuật toán thực hiện dựa vào hai bƣớc chính. Bƣớc 1, thuật toán dùng hàm Harris Laplace để phát hiện điểm tỉ lệ. Bƣớc 2, lựa chọn các điểm mà hàm Laplace of Gaussian đạt giá trị cực đại. Đặc trƣng Harris Laplace tuy giải quyết đƣợc vấn đề co giãn của ảnh, nhƣng sự biến đổi affine vẫn còn hạn chế. 2.1.3. SIFT SIFT [5] đƣợc trình bày đầu tiên bởi David G. Lowe năm 1999, đến năm 2004 chính David G. Lowe hoàn thiện giải thuật SIFT [6]. Thí nghiệm về thuật Trang 6
20. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà toán SIFT của ông về một hình ảnh sau khi co giãn, xoay hay biến đổi trong không gian affine thì đặt trƣng SIFT hầu nhƣ không thay đổi. Thuật toán SIFT đƣợc mô tả qua những bƣớc chính sau: tìm cực trị của không gian tỉ lệ, lọc và trích xuất điểm đặc trƣng, gán hƣớng cho điểm đặc trƣng và mô tả điểm đặc trƣng. 2.1.3.1. Tìm cực trị của không gian tỉ lệ Đầu tiên, chúng ta xây dựng các mức của ảnh bằng phép biến đổi Gaussian của ảnh với các giá trị độ lệch chuẩn thay đổi liên tiếp nhau (gọi là ảnh Gaussian). Theo phƣơng trình sau: 1 xy2 2 /2 2 G x,, y e (2.1) 2  2 L x,,,,*, y G x y I x y (2.2) Trong đó, dấu * là nhân chập trong miền x và y. Tỉ lệ (mức kế tiếp) Tỉ lệ (mức đầu tiên) Khác biệt của Guassian Guassian (DoG) Hình 2.1: Phƣơng pháp tính DoG Trang 7
21. HVTH: Ngô Thanh Đông GVHD: TS. Lê Mỹ Hà Sự khác biệt của Gaussian (DoG) trong mỗi cấp đƣợc tính bằng cách trừ hai ảnh Gaussian liền kề nhau. D x,,,,,, y L x y k  L x y  (2.3) Trong Hình 2.1 ảnh bên trái thể hiện ảnh biến đổi Gaussian với các hệ số lệch chuẩn thay đổi, ảnh bên phải là kết quả trừ hai ảnh Gaussian kế nhau. Sau mỗi mức ảnh đƣợc giảm kích thƣớc còn một nửa và lặp lại quá trình [6]. Hình 2.2: Tìm điểm đặc trƣng từ các giá trị DoG. So sánh giá trị DoG từng điểm ảnh trong lân cận 3x3 của mức tỉ lệ hiện tại, tức là 26 pixels xung quanh, chúng ta tìm giá trị lớn nhất hoặc nhỏ nhất giữa chúng. Điểm này đƣợc coi là điểm đặc trƣng. Trong Hình 2.2 điểm đánh dấu x đƣợc so sánh với 26 điểm lân cận, nếu nó có giá trị lớn nhất hoặc nhỏ nhất thì đƣợc chọn làm điểm đặc trƣng. 2.1.3.2. Lọc và trích xuất điểm đặc trƣng Sau khi tìm đƣợc điểm đặc trƣng trong bƣớc 2.1.1, không phải điểm đặc trƣng nào cũng tốt nhất, vì vậy ta cần loại bỏ điểm đặc trƣng yếu và trích xuất các điểm đặc trƣng mạnh. Để thực hiện điều này ta cần thực hiện 3 bƣớc sau: xác định đúng vị trí của điểm đặc trƣng, loại bỏ điểm đặc trƣng có tính tƣơng phản thấp, loại bỏ điểm đặc trƣng dƣ thừa theo biên. Trang 8
22. S K L 0 0 2 1 5 4