Báo cáo Định vị robot di động ngoài trời bằng camera đa hướng kết hợp Global Positioning System (GPS) (Phần 1)

Nội dung text: Báo cáo Định vị robot di động ngoài trời bằng camera đa hướng kết hợp Global Positioning System (GPS) (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 ÐỊNH VỊ ROBOT DI ÐỘNG NGOÀI TRỜI BẰNG CAMERA ÐA HƯỚNG KẾT HỢP GLOBAL POSITIONING SYSTEM (GPS) MÃ SỐ: 2015-39TÐ S KC 0 0 5 3 3 0 Tp. Hồ Chí Minh, tháng 03/2016
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 Đ NH V ROBOT DI ĐỘNG NGOÀI TRỜI BẰNG CAMERA ĐA HƯỚNG KẾT HỢP GLOBAL POSITIONING SYSTEM (GPS) Mã số: 2015-39TĐ Chủ nhiệm đề tài: TS. Lê Mỹ Hà TP. HCM, 3/2016
3. 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 4 1.2. Mục tiêu và đối tượng nghiên cứu 6 1.2.1. Mục tiêu nghiên cứu 6 1.2.3. Đối tượng nghiên cứu 6 1.3. Nhiệm vụ của đề tài và phạm vi nghiên cứu 6 1.3.1. Nhiệm vụ của đề tài 6 1.3.2. Phạm vi nhiên cứu 7 1.4. Phương pháp nghiên cứu 7 Chương 2: Những công trình liên quan và đề xuất phương pháp định vị dùng omni-directional camera kết hợp GPS Error! Bookmark not defined. 2.1. Tìm cặp điểm đặc trưng tương đồng 9 I
4. 2.1.1. Các loại đặc trưng 9 2.1.2. Đặc trưng SIFT 12 2.2. Thông số nội camera Error! Bookmark not defined. 2.3. Thuật toán RANSAC 17 2.4. Định vị camera dựa trên điểm tương đồngError! Bookmark not defined. 2.4.1. Hình học Epipolar và ma trận cơ bản Error! Bookmark not defined. 2.4.2. Ma trận thiết yếu và thông số ngoại camera Error! Bookmark not defined. 2.5. Giải thuật 8 điểm kết hợp RANSAC Error! Bookmark not defined. 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 Error! Bookmark not defined. Chương 3: THỰC NGHIỆM GIẢI THUẬT 32 3.1. Cân chỉnh camera tìm bộ thông số nội cameraError! Bookmark not defined. 3.2. Trích rút đặc trưng SIFT Error! Bookmark not defined. 3.3. Mô tả cặp đặc trưng tương đồng Error! Bookmark not defined. 3.4. Ước lượng ma trận cơ bản F và ma trận thiết yếu E Error! Bookmark not defined. Chương 4: KẾT LUẬN 36 PHỤ LỤC A 37 TÀI LIỆU THAM KHẢO 38 II
5. 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 đồ Error! Bookmark not defined. Hình 2.1: Phương pháp tính DoG. 13 Hình 2.2: Tìm điểm đặc trưng từ các giá trị DoG. 13 Hình 2.3. Mô tả điểm đặc trưng 16 Hình 2.4: Mô hình Pinhold camera Error! Bookmark not defined. Hình 2.5: Hệ tọa độ tương đương mô hình PinholdError! Bookmark not defined. Hình 2.6: Quan hệ giữa tọa độ camera và tọa độ không gianError! Bookmark not defined. Hình 2.7: Quan hệ giữa tọa độ camera và tọa độ không gianError! Bookmark not defined. Hình 2.8: Tập dữ liệu đường thẳng 18 Hình 2.9: Tìm đường thẳng dùng thuật toán RANSAC 18 Hình 2.10: Mô tả hình học Epipolar Error! Bookmark not defined. 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 Error! Bookmark not defined. Hình 3.1: Lưu đồ thực hiện tìm vị trí Error! Bookmark not defined. Hình 3.2: Tập ảnh bàn cờ dùng cân chỉnh camera Error! Bookmark not defined. Hình 3.3: Ảnh qua bộ lọc Gaussian Error! Bookmark not defined. Hình 3.4: Ảnh thể hiện sau khi tinh DoG. Error! Bookmark not defined. Hình 3.5: Điểm đặc trưng của ảnh Error! Bookmark not defined. IV
6. Hình 3.6: Hình thể hiện các đặc trưng SIFT Error! Bookmark not defined. Hình 3.7: Cặp điểm đặc trưng tương đồng Error! Bookmark not defined. Hình 3.8. Trích điểm đặc trưng SIFT và đối sánh Error! Bookmark not defined. Hình 3.9. Tọa độ vị trí camera trong hai khung ảnh đầu tiênError! Bookmark not defined. Hình 3.10. Kết quả mô phỏng vị trí robot dùng 372 ảnh.Error! Bookmark not defined. Hình 3.11. Kết quả thực nghiệm đám mây điểm 3D và vị trí robot Error! Bookmark not defined. V
7. DANH SÁCH CÁC CHỮ VIẾT TẮT SFM: Structure from motion. DOF: degrees of freedom IMU: inner measurement unit SLAM: Simutaneous Localization and Mapping BA: Bundle Adjustment RANSAC: Random sample consensus. SIFT: Scale invariant feature transform. IR: Infrared radiation GPS: Global Positioning System VI
8. 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 Đề tài này đề xuất một phương pháp định vị cho các thiết bị di chuyển ngoài trời dùng thuật toán một điểm kết hợp với một vùng tương đồng đường biên của hệ thống thị giác đơn trong môi trường đô thị rộng lớn. Việc định vị 5 bậc tự do (five degrees of freedom-5 DOF) ước lượng bởi camera đơn-đa hướng sẽ cải thiện được những giả định di chuyển trong mặt phẳng của hầu hết các nghiên cứu trước đây. Trong những năm gần đây mô hình di chuyển tựa như xe hơi với giả định chuyển động trong mặt phẳng thì thường được nghiên cứu để giảm bớt những yêu cầu về điểm tương đồng cho đến còn một điểm. Tuy nhiên, trong những ứng dụng thực tế của việc di chuyển xa ở ngoài trời, những di chuyển này hầu như không thỏa mãn điều kiện này. Điều này dẫn đến sự không chính xác trong việc định vị. Trong phương pháp đề xuất này, mô hình tựa như xe hơi được tận dụng cho việc định vị 5 bậc tự do, tuy nhiên những yêu cầu về những điểm đặc trưng tương đồng thì được giảm xuống chỉ còn một điểm kết hợp với một vùng đối sánh, phương pháp này thì đơn giản hơn rất nhiều so với phương pháp 5 –điểm RANSAC. Những sai số tích lũy của hệ thống đo lường bằng hình ảnh sẽ được loại bỏ bằng cách kết hợp với hệ thống định vị GPS dưới dạng ước lượng cực đại hàm xác suất trong phương pháp lọc Kalman mở rộng. Những ứng dụng thực tế trên vùng đồi núi sẽ cho thấy độ chính xác của việc định vị theo phương pháp này. Việc điều hướng cho các thiết bị tự hành hay rô bốt là một hướng nghiên cứu quan trọng có thể áp dụng trong nhiều lĩnh vực khác nhau như định vị, hoạch Trang 1
9. định đường đi và đối sánh với bản đồ. Mặc dù một vài thành quả đã đạt được trong lĩnh vực này nhưng vẫn chưa có phương pháp nào thỏa mãn yêu cầu về độ chính xác cao cũng như là tính bền vững khi khoảng cách di chuyển xa trong các điều kiện địa hình hay môi trường khác nhau. Trong những năm gần đây, nhiều phương pháp đã được phát triển cho việc điều hướng các thiết bị di chuyển có thể tạm chia ra một số phương pháp như sau: Phương pháp sử dụng chỉ những thiết bị điện từ (ví dụ như hệ thống định vị toàn cầu GPS, đơn vị đo lường bên trong (IMU), dụng cụ đo vòng quay của bánh xe, cảm biến laze), phương pháp chỉ dựa trên quan sát (camera đơn, sterio camera, camera đa hướng phản xạ qua gương) và phương pháp kết hợp giữa các thiết bị điện từ và hệ thống quan sát bằng hình ảnh. Trong nhóm đầu tiên, thiết bị GPS gắn trên thiết bị di chuyển nhận tín hiệu từ các vệ tinh và sau đó cho ra tín hiệu tuyệt đối về vị trí trên bản đồ. Độ chính xác của phương pháp này thường là thấp, tín hiệu từ vệ tinh thường bị dịch đi so với giá trị thực, hơn nữa các tòa nhà trong vùng đô thị thường gây nên hiện tượng làm mất hay nhảy tín hiệu từ vệ tinh vì vậy thiết bị di chuyển có thể bị mất thông tin. Để cải thiện phương pháp này một số cảm biến khác được sử dụng bổ sung, hệ thống sẽ trở thành hệ thống đa cảm biến. Ví dụ như việc bổ sung thêm thiết bị đo lường vòng bánh xe có thể cải thiện độ chính xác trong dich chuyển nhưng nó có thể gây ra sai số nếu bánh xe bị trượt hay di chuyển trên những con đường gồ ghề. Loại thiết bị khác cũng được xem xét đến đó là IMU. Thiết bị này được dùng cho việc đo lường gia tốc và hướng. Tuy nhiên, giá thành của các loại thiết bị này khá là đắt tiền. Cảm biến laser cũng là một lựa chọn tốt trong những trường hợp này , tuy nhiên tín hiệu có thể bị yếu khi đối tượng xuất hiện ở khoảng cách xa hoặc không có phản xạ. Nhìn chung, tín hiệu GPS thì chính xác về hình dạng trong việc di chuyển rộng, toàn cục nhưng sẽ không chính xác trong các vị trí cục bộ. Đặc tính này rất quan trọng có thể được tận dụng cho việc định vị. Trong nhóm thứ hai, hệ thống thị giác được gắn trên các thiết bị di chuyển và thu thập hình ảnh/ Video từ các cảnh vật xung quanh cho các bước xử lý sau Trang 2
10. đó. Thông thường những ràng buộc về góc quay và tịnh tiến của những khung hình liên tục thì được phân tích trước tiên. Một số những đặc trưng bền vững được xem như là điểm mốc ví dụ như những điểm, đường thẳng, mặt phẳng. Sau khi hệ thống tìm ra sự tương đồng của những đặc trưng này, sự dịch chuyển của đối tượng được tính toán. Ở đây sự không rõ ràng về tính tỷ lệ rất quan trọng. Với những thiết bị hình ảnh đã được cân chỉnh, tỷ lệ của mô hình và cảnh vật thật sự sẽ được biết một cách rõ ràng. Tuy nhiên, tỷ lệ ban đầu phải được ước lượng dùng các thiết bị bổ trợ ví dụ cảm biến laser kết hợp với camera đơn. Nhìn chung, những loại hệ thống như thế này có thể tạo ra kết quả chính xác trong khoảng di chuyển ngắn hay môi trường không có tín hiệu GPS. Vấn đề lớn ở đây là sai số tích lũy khi thiết bị di chuyển làm việc trong môi trường rộng lớn thì sai số tích lũy này sẽ lớn dần, Vì vậy, quy đạo cuối cũng sẽ bị phân kỳ khi so sánh với giá trị thực. Tuy nhiên một ưu điểm rõ ràng của phương pháp này là những sai số cục bộ trong khoảng di chuyển nhỏ là rất nhỏ. Đặc trưng này sẽ được tân dụng trong đề tài nghiên cứu này. Trong một nhóm thứ ba, sự kết hợp của thiết bị điện từ và những phương pháp dựa trên thị giác được đề xuất. Những phương pháp loại này thì tận dụng ưu điểm của mỗi loại cảm biến. Tín hiệu toàn cục từ GPS được dùng làm thông tin tham khảo về vị trí của cảm biến thị giác. Hơn nữa, sự dịch chuyển của hệ thống thị giác được ước lượng một cách dễ dàng trong môi trường ngoài trời giàu thông tin (ví dụ như rất nhiều vật mốc là tự nhiên và nhân tạo). Hệ thống thị giác này có thể dùng thông tin toàn cục từ GPS để điều chỉnh lại vị trí hiện tại. Bên cạnh đó những cảm biến này có thể bù trừ lẫn nhau trong trường hợp mất một trong hai tín hiệu. Ví dụ như khi thiết bị di chuyển trong các đường hầm hay các thành phố có mật độ tòa nhà dày đặc, khi đó tín hiệu GPS có thể bị mất hoặc dao động, khi đó hệ thống thị giác có thể hoạt động độc lập. Mặc khác hệ thống thị giác có thể chỉnh định lại tính hiệu GPS bị sai. Công trình nghiên cứu này được tiến hành dựa trên những nhận định đó. Trang 3
11. 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ô. 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. Chế độ tự định vị là một trong những hướng nghiên cứu quan trọng của robot làm việc ngoài trời có thể ứng dụng trong việc tự hành, xây dựng bản đồ, hoạch định đường đi. Mặc dù nhiều nghiên cứu đã được tiến hành trong thời gian qua nhưng hầu như chưa có giải pháp nào tối ưu và bền vững khi robot làm việc lâu dài ngoài trời với khoảng cách xa và môi trường làm việc khác nhau. Sự kết hợp giữa hệ thống thị giác và những thiết bị điện từ có thể xem như là giải pháp hiện hữu giải quyết vấn đề sai số tích lũy trong những năm gần đây. Về cơ bản những giải pháp này có thể tạm chia thành 3 nhóm như sau: Nhóm thứ nhất chỉ dung hệ thống thị giác, nhóm thứ hai dung GPS kết hợp với các cảm biến điện từ. Nhóm thứ ba kết hợp hệ thống thị giác và GPS. Trong nhóm thứ nhất, những nghiên cứu sớm về hệ thống tính toán đường đi robot dung camera truyền thống được tiến hành đầu tiên bởi Nister [1] và Royer [2], trong khi một số nhóm nghiên cứu khác như [3], [4] dùng hệ thống camera đôi. Bởi vì sự hạn chế trong góc nhìn của camera, một số tác giả khác đề xuất dùng camera đa hướng (Omnidirectional camera). Hệ thống định vị dùng camera đa hướng tiêu biểu có thể kể đến trong [5-7]. Nguyên lý chính trong phương pháp này là tìm sự tương quan đặc trưng của chuỗi hình ảnh thu được, sau đó tính toán những ràng buộc này để tìm ra được sự dịch chuyển của robot. Vấn đề khó khan gặp phải trong giả pháp này là khi số lưỡng đặc trưng tương đồng quá ít, khó tìm được những đặc trưng tương đồng chính xác khi loại bỏ những tương đồng sai. Chính điều này dẫn tới sai số lớn trong một số khu vực dịch chuyển đặc biệt của robot. Tuy nhiên trong những vùng làm việc với khoảng cách ngắn, quỹ đạo có thể đúng. Nhưng Trang 4
12. khi Robot làm việc với khoảng di chuyển xa thì quỹ đạo hầu như sẽ phân kì nếu so sánh với đường đi thực tế. Đây cũng là thách thức lớn trong vấn đề định vị robot bằng phương pháp tang dần. Trong nhóm phương pháp thứ hai, Những cảm biến điện từ được kết hợp thành một hệ thống cảm biến để định vị cho robot như trong [8], [9]. Thông thường GPS sẽ được dùng để định vị quỹ đạo dịch chuyển chung toàn cục và cảm biến IMU hoặc thiết bị đo dịch chuyển bánh được dùng để tính toán di chuyển cục bộ. Phương pháp này cho quỹ đạo toàn cục gần đúng, hầu như đều bị trược đi so với quỹ đạo thực. Đây cũng là thách thức trong phương pháp định vị mà không dùng thị giác. Trong những năm gần đây, phương pháp kết hợp hai giải pháp bên trên được xem như giải pháp tốt hơn để khắc phục những nhược điểm đã nêu. Một số nhóm tác giả tiêu biểu như [10-12] đề xuất phương pháp kết hợp thị giác và GPS. Kết quả cho thấy độ chính xác được cải thiện khá nhiều. Tuy nhiên các phương pháp này dựa trên tương quan đặc trưng trong hầu hết các bước xử lý. Đều này làm tang thời gian xử lý đáng kể. Hơn nữa những nghiên cứu này đề giả định mặt di chuyển là phẳng hoàn toàn, điều này không đúng trong các ứng dụng thực tế. Khi Robot di chuyển trên đường dốc, quỹ đạo hoặc vị trí của robot sẽ không còn đúng nữa như trong hình 1. Hình 1. Sai số vị trí của robot di chuyển trong đường dốc Trang 5
13. Theo thống kê của tác giả hiện nay chưa có nhiều công trình trong nước nghiên cứu về định vị robot di động ngoài trời. Một số nhóm tác giả trong nước nghiên cứu vấn đề định vị cho robor di động dựa trên camera nhưng hầu hết các di chuyển này là ngắn hoặc trong nhà. Những đề tài đạ thực hiện có thể liệt kê [13-20]. 1.2. Mục tiêu, đố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 tối ưu các đặc trưng trên ảnh omni. 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. Đồng thời kết hợp với thông tin từ GPS để chỉnh sửa lại nhưng vị trí sai số do bị nhiễu tác động. 1.2.2. Đối tượng nghiên cứu - Robot hoặc xe chuyên dụng - Hệ thống thị giác máy, GPS 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 Trích xuất đặc trưng về đường biên trong ảnh 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 Trang 6
14. - 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 có kết hợp hệ thống GPS. 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 7
15. Chương 2 Những công trình liên quan và đề xuất phương pháp định vị dùng omni-directional camera kết hợp GPS Dựa trên những phân tích trên, phương pháp kết hợp camera đa hướng và thiết bị GPS tiêu chuẩn được đề xuất. Nhiều thông tin của môi trường xung quanh sẽ thu nhận được bằng camera có góc quan sát 3600, thậm chí khi thiết bị thực hiện một góc quay lớn thì điểm mốc vẫn được theo dõi. Đây là một ưu điểm rất lớn trong việc sử dụng camera cầu đa hướng với việc sử dụng thông tin dẫn đường từ GPS, quỹ đạo di chuyển được duy trì một cách chính xác vừa cục bộ từ hệ thống thị giác và hình dạng toàn cục từ hệ thống GPS. Sơ đồ tổng quát của phương pháp đề xuất như trên được trình bày trong hình số 2. Trong khung hình đầu tiên, hướng di chuyển của đối tượng được xác định. Sau đó những ma trận ràng buộc giữa các khung hình liên tục sẽ được tính toán. Những đặc trưng về đường biên và những điểm then chốt được kết hợp cho việc tính toán góc quay, ở đây là góc ngang và góc đứng. Phương pháp đối sánh Chamfer được sử dụng để tính toán góc ngang. Việc ước lượng góc ngang này tương tự như một la bàn thị giác. Bởi vì công trình này chỉ dựa trên chuyển động 5 bậc tự do bao gồm 3 chuyển động tịnh tiến và 2 giá trị góc quay nên góc đứng cũng cần phải được tính toán. Tối thiểu 1 điểm đặc trưng tương đồng thì cần thiết cho việc tính toán này. Hơn nữa, khoảng cách tịnh tiến của thiết bị là những giá trị tuyệt đối nhận được từ việc di chuyển đều của đối tương. Khoảng cách tịnh tiến bằng nhau tương ứng với mỗi khoảng khung hình được trích ra. Trong giai đoạn tiếp theo, thiết bị GPS sẽ cung cấp vị trí toàn cục của đối tượng, thông tin này được dùng để hiệu chỉnh lại độ chính xác, Tuy nhiên, vị trí xác định từ GPS có thể không chính xác từ những môi trường có mật độ xây dựng lớn. Như vậy bước xử lý, đánh giá cần phải được thực hiện. Trang 8
16. Phân tích khung ảnh Kết hợp biên Điểm tương đồng Tính toán khoảng tịnh Ước lượng góc ngang Ước lượng góc dọc Bộ thu tín hiệu GPS tiến Đánh giá tín hiệu GPS Ước lượng vị trí Vị trí hiệu chỉnh Định vị vị trí phương tiện di chuyển Hình 2: sơ đồ đề xuất về định vị vị trí phương tiện di chuyển 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 Trang 9
17. 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ó 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 Trang 10
18. 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ự 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. Trang 11
19. 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: 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) Trang 12
20. 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]. 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. Trang 13
21. S K L 0 0 2 1 5 4