Báo cáo Xây dựng môi trường 3D và tự định vị cho robot (Phần 1)

Nội dung text: Báo cáo Xây dựng môi trường 3D và tự định vị cho robot (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 CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG XÂY DỰNG MÔI TRƯỜNG 3D VÀ TỰ ĐỊNH VỊ CHO ROBOT S K C 0 0 3 9 5 9 MÃ SỐ: T2014-07TĐ S KC 0 0 4 8 0 9 Tp. Hồ Chí Minh, 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 BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƯỜNG TRỌNG ĐIỂM XÂY DƯṆ G MÔI TRƯỜ NG 3D VÀ TỰ ĐỊNH VỊ CHO ROBOT Mã số: T2014-07TĐ Chủ nhiệm đề tài: TS. Lê Mỹ Hà TP. HCM, 04/2015
3. DANH SÁCH NHỮNG THÀNH VIÊN THAM GIA NGHIÊN CỨU ĐỀ TÀI Đơn vị công tác và Nội dung nghiên cứu Stt Họ và tên lĩnh vực chuyên Chữ ký cụ thể được giao môn Nghiên cứu lý thuyết và thực nghiệm trên hệ Trường Đại học Sư thống 1 TS. Lê Mỹ Hà Phạm Kỹ Thuật Kiểm tra và chỉnh sửa TP.HCM giải thuật Viết báo cáo Trường Đại học Sư Xây dựng giải thuật và 2 TS. Ngô Văn Thuyên Phạm Kỹ Thuật mô phỏng TP.HCM
4. MỤC LỤC MỤC LỤC I DANH SÁCH CÁC HÌNH III DANH SÁCH CÁC CHỮ VIẾT TẮT V Chương 1: TỔNG QUAN 1 1.1.Tổng quan chung 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 chung 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 4 1.2.1.Mục tiêu nghiên cứu 4 1.2.2.Khách thể nghiên cứu 4 1.2.3.Đối tượng nghiên cứu 5 1.3.Nhiệm vụ của đề tài và phạm vi nghiên cứu 5 1.3.1.Nhiệm vụ của đề tài 5 1.3.2.Phạm vi nhiên cứu 5 1.4.Phương pháp nghiên cứu 5 Chương 2: XÂY DỰNG ĐÁM MÂY ĐIỂM TRONG KHÔNG GIAN 3D VÀ ĐỊNH VỊ ROBOT 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 2.1.2.Đặc trưng SIFT 8 I
5. 2.2.Thông số nội camera 13 2.3.Thuật toán RANSAC 17 2.4.Định vị camera dựa trên điểm tương đồng 20 2.4.1.Hình học Epipolar và ma trận cơ bản 20 2.4.2.Ma trận thiết yếu và thông số ngoại camera 21 2.5.Giải thuật 8 điểm kết hợp RANSAC 21 2.6.Thuật toán tối ưu xây dựng không gian đám mây điểm và vị trí robot 22 Chương 3: THỰC NGHIỆM GIẢI THUẬT 24 3.1.Cân chỉnh camera tìm bộ thông số nội camera 24 3.2.Trích rút đặc trưng SIFT 30 3.3.Mô tả cặp đặc trưng tương đồng 33 3.4.Ước lượng ma trận cơ bản F và ma trận thiết yếu E 33 Chương 4: KẾT LUẬN 39 PHỤ LỤC A 40 TÀI LIỆU THAM KHẢO 40 II
6. 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 đồ 3 Hình 2.1: Phương pháp tính DoG. 9 Hình 2.2: Tìm điểm đặc trưng từ các giá trị DoG. 10 Hình 2.3. Mô tả điểm đặc trưng 13 Hình 2.4: Mô hình Pinhold camera 14 Hình 2.5: Hệ tọa độ tương đương mô hình Pinhold 14 Hình 2.6: Quan hệ giữa tọa độ camera và tọa độ không gian 16 Hình 2.7: Quan hệ giữa tọa độ camera và tọa độ không gian 17 Hình 2.8: Tập dữ liệu đường thẳng 19 Hình 2.9: Tìm đường thẳng dùng thuật toán RANSAC 19 Hình 2.10: Mô tả hình học Epipolar 20 Hình 2.11: Mô tả hình học của 3 frame liên tục với những đặc trưng tương đồng 23 Hình 3.1: Lưu đồ thực hiện tìm vị trí 24 Hình 3.2: Tập ảnh bàn cờ dùng cân chỉnh camera 29 Hình 3.3: Ảnh qua bộ lọc Gaussian 30 Hình 3.4: Ảnh thể hiện sau khi tinh DoG. 30 Hình 3.5: Điểm đặc trưng của ảnh 31 Hình 3.6: Hình thể hiện các đặc trưng SIFT 32 Hình 3.7: Cặp điểm đặc trưng tương đồng 33 Hình 3.8. Trích điểm đặc trưng SIFT và đối sánh 35 III
7. Hình 3.9. Tọa độ vị trí camera trong hai khung ảnh đầu tiên 36 Hình 3.10. Kết quả mô phỏng vị trí robot dùng 372 ảnh. 37 Hình 3.11. Kết quả thực nghiệm đám mây điểm 3D và vị trí robot 38 IV
8. DANH SÁCH CÁC CHỮ VIẾT TẮT SFM: Structure from motion. SLAM: Simutaneous Localization and Mapping BA: Bundle Adjustment RANSAC: Random sample consensus. SIFT: Scale invariant feature transform. IR: Infrared radiation GPS: Global Positioning System V
9. Chương 1 TỔNG QUAN 1.1. Tổng quan chung 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 chung 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 để tính toán, 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 để robot có thể trả lời đúng câu hỏi “tôi đang ở đâu?”. Định vị robot sử dụng GPS, trên 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ừ 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àimet. Định vị robot sử dụng thiết bị Kinect, nhờ thiết bị Kinect có một camera RGB và một camera IR. Thiết bị Kinect vừa thu thập hình ảnh, vừa thu thập độ sâu của ảnh nhờ camera IR, giúp cho robot tính toán khoảng cách từ robot đến vật cản trong môi trường xung quanh, từ đó xác định vị trí của robot trong môi trường. Trang 1
10. 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à định vị cho robot ngoài trời. Lập bản đồ và định vị cho robot ngoài trời gặp nhiều khó khăn hơn robot 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 hình ảnh và xử lý. 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à chưa biết 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. Trang 2
11. 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 mobile robot sử dụng GPS [1], robot di chuyển và định vị dựa và 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. Trang 3
12. 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 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 mức đố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 theo hướng đối tượng. Một máy ảnh chụp một cảnh nhiều đối tượng, thông tin các đối tượng được lặp đi lặp lại 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. Biểu đồ được tối ưu hóa lên tục như các phép đo mới và cho phép luôn cập nhập, các dự đoán liên tục và chính xác 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à định vị robot dựa vào thuật toán SFM. Robot 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 robot, sau đó tính toán vị trí và hướng của robot trong không gian robot đang tương tác. 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 SIFT để trích đặc trưng của ảnh và tìm những đặc trưng tương đồng trong các ảnh liên tiếp nhau. Những tương đồng sai sẽ bị loại bỏ thông qua thuật toán RANSAC. Đồng thời ma trận thông số nội camera cũng được tính toán theo bước cân chỉnh trước đó. Những đám mây điểm của môi trường và vị trí robot được khôi phục lại và tính toán chính xác dựa trên giải thuật tối ưu. Trang 4
13. 1.2.3. Đối tượng nghiên cứu Đề tài nghiên cứu dựa trên dữ liệu đầu vào là tập ảnh 2D, được thu thập trong quá trình di chuyển trên đường đi của robot hoặc hệ thống di chuyển cần xác định vị trí tương ứng trong môi trường làm việc. 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 hoặc sai Thuật toán trích đặt trưng SIFT từ một hình ảnh Thuật toán RANSAC loại bỏ các đặt trưng yếu của một hình ảnh - Thuật toán tối ưu tái cấu trúc 3D xây dựng bản đồ 3D, xác định vị trí và góc quay camera để tìm vị trí và hướng của robot. 1.3.2. Phạm vi nhiên cứu Đề tài nghiên cứu trên thiết bị di chuyển có người lái, tập ảnh 2D được tác giả thu thập trong quá trình di chuyển trên đường đi. Trên tập dữ liệu ảnh 2D đề tài mô phỏng tính toán xây dựng bản đồ 3D và định vị vị trí camera trong bản đồ này. 1.4. Phương pháp nghiên cứu Cách tiếp cận của nghiên cứ u này là khảo sát cơ sở lý thuyết những phương pháp hiện có, phân tích ưu nhược điểm. Tiến hành đề xuất phương pháp mới cải tiến. Thực hiện mô phỏng giải thuật trên phần mềm. Khi thu được sai số cho phép sẽ tiến hành thưc̣ nghiêm trên phần cứ ng và môi trường thưc̣ tế . Tóm lại,phương pháp nghiên cứu của đề tài là trước tiên tiên hành nghiên cứu lý thuyết, sau đó kiểm chứng bằng thực tế và rút ra kết luận. Trang 5
14. Chương 2 XÂY DỰNG ĐÁM MÂY ĐIỂM TRONG KHÔNG GIAN 3D VÀ ĐỊNH VỊ ROBOT Nội dung chương 2 trình bày cách trích đặc trưng SIFT, cách tìm những đặc trưng tương đồng từ 2 hình ảnh thu được kế tiếp nhau. Đồng thời giới thiệu giải thuật RANSAC để loại bỏ những đặc trưng yếu hoặc sai. Ma trận thông số nội của camera được tính toán bằng cách cân chỉnh camera dựa trên vật mẫu là chessboard. Giải thuật tối ưu được dùng để xây dựng đám mây điểm của không gian làm việc và vị trí của robot cũng sẽ được trình bày trong chương này. 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à thành phần quan trọng và thăng chốt. Việc lựa chọn các đặc trưng sẽ giúp cho việc tăng độ chính xác vị trí, hướng của robot 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. Harris corner Harris corner là đặc trưng phát hiện góc, hoặc một thuật ngữ tổng quát hơn là phát hiện điểm quan tâm (interest point detection) là một hướng tiếp cận được sử dụng trong các hệ thống thị giác máy tính để trích chọn các loại đặc trưng và suy luận ra các nội dung của một ảnh. Việc phát hiện góc được dùng thường xuyên trong phát hiện, theo dõi chuyển động, mô hình 3D và nhận dạng đối tượng. Một góc được xác định bởi nơi giao nhau của hai cạnh. Một góc cũng có thể được xác định như một điểm có hai hướng khác nhau trong một vùng cục bộcủa điểm đó. Một điểm quan tâm là một điểm trong một ảnh mà điểm này có Trang 6
15. vị trí được xác định tốt và có thể được phát hiện nhanh chóng. Điều này có nghĩa là một điểm quan tâm có thể là một góc nhưng cũng có thể là một điểm đơn có giá trị cường độ cực đại hoặc cực tiểu cục bộ, các điểm kết thúc của đường thẳng hoặc một điểm trên một đường cong mà ở đó độ cong là tối đa cục bộ. Trên thực tế, hầu hết các phương pháp phát hiện góc phát hiện các điểm hơn là các góc nói riêng. Phương pháp phát hiện góc Harris[5] là một phương pháp phát hiện điểm quan tâm phổ biến vì nó bất biến đối với phép quay, thay đổi độ sáng và tạp nhiễu ảnh. Phương pháp này dựa trên hàm tương quan tự động cục bộ của một tín hiệu; ở đó hàm tương quan tự động cục bộ đo các thay đổi cục bộ của tín hiệu với các mảnh ảnh được dịch chuyển một lượng nhỏ theo các hướng khác nhau. Tuy nhiên, phương pháp này chưa giải quyết được vấn đề biến đổi co, giãn ảnh hay những phép biến đổi affine. 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ế. SURF SURF là một phương pháp phát hiện và mô tả hình ảnh tốt, do Herbert Bay đưa ra lần đầu vào năm 2006, có thể được sử dụng trong các nhiệm vụ tầm nhìn của máy tính như nhận dạng đối tượng, phục hồi 3D. Nó dựa trên mô tả SIFT. Phiên bản tiêu chuẩn của SURF nhanh hơn nhiều so với SIFT và nó chống lại sự Trang 7
16. biến đổi hình ảnh khác nhau tốt hơn SIFT. SURF dựa trên tổng xấp xỉ các đặc trưng Haar Wavelet 2D và sử dụng hiệu quả cho các ảnh tích hợp (integral image). Phương pháp này dựa trên các ma trận Hessian, nhưng sử dụng một xấp xỉ cơ bản, cũng giống như DoG là một phát hiện cơ bản dựa trên Laplacian. Nó dựa trên hình ảnh tích hợp để giảm thời gian tính toán và được gọi nó là phát hiện 'Fast-Hessian'. Mặt khác, mô tả này mô tả một phân bố các đặc trưng Haar- Wavelet trong các lân cận của điểm quan tâm. Hơn nữa, chỉ sử dụng kích thước 64, để giảm thời gian tính toán các đặc trưng và mô tả bộtương đồng, đồng thời tăng độ tin cậy. Nó không chỉ làm tăng tốc độ tương đồng, mà còn tang độ tin cậy của bộ mô tả đặc trưng này. SIFT SIFT [6] đượ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 [7]. Thí nghiệm về thuật 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. SIFT cho số lượng đặc trưng tốt hơn các giải thuật còn lại, nên tác giả lựa chọn làm cơ sở để tìm điểm đặc trưng trong nghiên cứu này. 2.1.2. Đặc trưng SIFT 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. 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: Trang 8
17. 1 xy2 2 /2 2 Gxy ,,,,,,*, e Lxy  Lxy  Ixy (2.1) 2  2 Trong đó, dấu * là nhân chập trong miền x và y. 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. x,,,,,, y L x y k  L x y  (2.2) Tỉ lệ (mức kế tiếp) Tỉ lệ (mức đầu tiên) Khác biệt của Gaussian Gaussian (DoG) Hình 2.1:Phương pháp tính DoG. 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 với tỉ lệ hệ số 2 và lặp lại quá trình[7]. Trang 9
18. Hình 2.2: Tìm điểm đặc trưng từ các giá trị DoG. So sánh từng điểm ảnh trong tỉ lệ hiện tại với tỉ lệ trên, dưới trong lân cận 3x3, tức là 26 pixel 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. 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. Xác định đúng vị trí của điểm đặc trưng Vì điểm đặc trưng tìm được có thể chưa phải là điểm chính xác có giá trị cực đại hoặc cực tiểu. Ta dùng khai triển Taylor của hàm không gian tỉ lệ để dịch đến vị trí điểm lấy mẫu gốc. DDT 1 2 DXDXX T (2.3) XX2 2 Trang 10
19. Trong đó: D và đạo hàm của nó được tính tại điểm đặc trưng và = ( , , 휎) là độ lệch của điểm nàu. Vị trí của điểm cực trị được tính bằng cách lấy đạo hàm của hàm trên theo X và cho nó tiến về 0. 21DD Xˆ (2.4) XX2 Loại bỏ điểm đặc trưng có tính tương phản thấp Trong bước này ta sẽ loại bỏ những điểm đặc trưng có độ tương phản thấp. Để loại điểm đặc trưng có độ tương phản thấp ta so sánh giá trị ( ) với giá trị ngưỡng. Với giá trị ( ) được xác định bằng cách thế phương trình (2.5) vào phương trình (2.4), ta được: 1 D 1 DXDXˆˆ (2.5) 2 X Nếu giá trị Dx ˆ thấp hơn ngưỡng thì điểm này bị loại trừ. Loại bỏ điểm đặc trưng dư thừa theo biên Sau khi dùng bộ lọc Gaussian sẽ làm cho đường biên không còn rõ, các giá trị DoG ở dọc góc đường biên không thể hiện chính xác điểm đặc trưng, vì vậy chúng ta cần loại bỏ bớt các điểm đặc biệt trên biên. Chúng ta sử dụng ma trận Hessian 2x2 tính ở vị trí và hệ số tỉ lệ của điểm đặc trưng để tìm độ góc. Với công thức tỉ lệ của nguyên tắc góc: DDxx xy H (2.6) DDxy yy 2 2 DDxx yy r 1 (2.7) 2 r DDDxx yy xy Nếu bất đẳng thức (2.8) không thỏa thì điểm đặc trưng bị loại bỏ[8]. Trang 11
20. Gán hướng cho điểm đặc trưng Mỗi điểm đặc trưng được mô tả bởi hướng chính dựa vào vị trí của ảnh để biểu diễn đặc trưng này không biến đổi trong trạng thái xoay. Bước này được mô tả bởi hai phương trình sau: 22 mxy , Lx 1, yLx 1, y Lxy , 1 Lxy , 1 (2.8) 1 L x, y 1 L x , y 1 xy, tan (2.9) L x 1, y L x 1, y Hai phương trình trên thể hiện độ lớn của Gradient và hướng của điểm pixel(x,y) tại L(x,y). Trong tính toán thực tế người ta xây dựng một Histogram Gradient xung quanh điểm đặc trưng từ các giá trị hướng của Gradient. Lượt đồ này gồm 36 mức, thể hiện cho phạm vi 3600, vì vậy mỗi hướng có 10o, ta có tất cả 36 hướng. Mỗi mẫu thì được thêm vào trọng số của Histogram được tính từ độ lớn Gradient và tỉ lệ của điểm đặc trưng. Nếu Histogram nào có giá trị lớn hơn 80% của những giá trị khác thì được chọn làm hướng chính của điểm đặc trưng. Một điểm đặc trưng có thể có nhiều hướng chính [8]. Mô tả điểm đặc trưng Tạo lại bảng mô tả 2D cho những giá trị trước đó thể hiện 3 thông số vị trí, tỉ lệ và hướng được dùng để mô tả một vùng của ảnh mà các giá trị này không thay đổi. Trong bước này tính toán bộ mô tả điểm đặc trưng. Mỗi điểm đặc trưng được mô tả bởi một vùng ô vuông 16x16. Sau đó được chia làm 4 vùng nhỏ có kích thước 4x4, tính giá trị Histogram với 8 mức hướng chính. Sau đó thêm vào giá trị độ lớn của gradient của vùng 4x4 vào cho các Histogram của hướng. Mỗi điểm đặc trưng chứa 8 vector, do đó một bộ mô tả sẽ chứa tổng cộng 4x4x8 yếu tố. Trang 12
21. Hình 2.3. Mô tả điểm đặc trưng. (a) Gradient của ảnh, (b) mô tả điểm đặc trưng Đối sánh điểm đặc trưng Những điểm đặc trưng tương đồng này được tìm ra bằng cách so sánh khoảng cách Eclidian của những vector đặc trưng. Điểm đặc trưng tương đồng là điểm có khoảng cách nhỏ nhất. Tuy nhiên khi số lượng điểm đặc trưng rất lớn hoặc phải so sánh với nhiều dữ liệu hình ảnh số lượng điểm đối sánh và phép so sánh sẽ rất lớn. Để khắc phục điều này, phương pháp cải tiến giải thuật cây so sánh K-D được áp dụng để giảm thời gian tính toán và so sánh. Trong phương pháp đối sánh này vẫn còn những lỗi do nhiễu của hình ảnh, phương pháp khác phục dựa trên thuật toán RANSAC được trình bày ở phần sau. 2.2. Thông số nội camera Quá trình tìm thông số camera còn được gọi là camera calibration. Camera calibration là phương pháp tính toán và thực nghiệm nhằm tìm ra các thông số của camera cho việc tái tạo không gian 3D của một cảnh nào đó trong thực tế bằng những ảnh mà camera đó chụp lại được. Để có được những thông số đó, các tính toán sau chủ yếu dựa vào mô hình camera thông dụng nhất hiện nay: mô hình Pinhold. Về mặt hình học, mô hình này bao gồm một mặt phẳng ảnh I (Image plane) và một tâm điểm C (Eyepoint) nằm trên mặt phẳng tiêu cự F (Focal plane) Trang 13
22. S K L 0 0 2 1 5 4