Luận văn Phát hiện làn đường thời gian thực cho hệ thống điều khiển xe tự động

6 CHƢƠNG 2. TỔNG QUAN Chƣơng này sẽ mô tả các vấn đề lý thuyết về bài toán phát hiện làn đƣờng và các mô hình khác nhau để giải quyết bài toán thông qua mô hình chung nhất của tất cả các phƣơng pháp. Sau đó là phần trình bày tổng quan về các hƣớng tiếp cận dựa trên thông tin thị giác để giải quyết vấn đề. 2.1. Các vấn đề trong bài toán Phát hiện làn đƣờng 2.1.1. Mục tiêu Trong bài toán phát hiện làn đƣờng, tùy thuộc vào nhiều yếu tố khác nhau mà mục tiêu giải quyết có thể khác nhau. Các mục tiêu này đƣợc [14] phân làm 3 loại nhƣ trong Hình 2-1. Hình 2-1. Minh họa các mục tiêu khác nhau trong bài toán phát hiện làn đƣờng a) Mục tiêu khi thay đổi làn đƣờng. b) Mục tiêu hỗ trợ ngƣời điều khiển xe. c) Mục tiêu điều khiển xe tự động. Nguồn: [14] 7 Các loại mục tiêu này nhƣ sau: 1. Hệ thống thông báo khi chuyển làn đường1: Trong mục tiêu này, yêu cầu đặt ra là hệ thống phải thông báo đƣợc khi xe thay đổi làn đƣờng. Vấn đề quan trọng nhất cần giải quyết ở đây là làm sao dự đoán đƣợc chính xác quỹ đạo của xe tƣơng ứng với đƣờng biên của làn đƣờng. 2. Hệ thống hỗ trợ người điều khiển xe2: Trong mục tiêu này, vấn đề quan trọng là giúp ngƣời điều khiển xe chú ý đƣợc làn đƣờng dễ dàng hơn. Hay nói cách khác, ngƣời điều khiển sẽ đƣợc hệ thống gợi ý các làn đƣờng. Hầu hết các nghiên cứu đều tập trung ở mục tiêu này, tiêu biểu nhƣ [1], [3], [7], [10], [11], [17], [18], [21], [22], [23]. 3. Hệ thống hỗ trợ điều khiển xe tự động3: Với mục tiêu hỗ trợ điều khiển xe tự động, yêu cầu đặt ra là hệ thống cần đƣa ra đƣợc làn đƣờng sắp tới mà xe sẽ di chuyển. Vấn đề quan trọng đối với mục tiêu này là hạn chế đƣợc sai số tính toán trong việc ƣớc lƣợng vị trí của xe và làn đƣờng. Hiện tại hƣớng nghiên cứu này đang thu hút đƣợc nhiều sự quan tâm của các nhóm nghiên cứu, trong đó có cả những nhóm lớn nhƣ nhóm của CMU4, hay nhóm của MIT 5 [12] với những cuộc thi lớn nhƣ DARPA. Nghiên cứu của đề tài nằm chủ yếu ở mục tiêu này. Với các mục tiêu khác nhau thì vấn đề tìm ra mô hình, thiết bị thu nhận tín hiệu, giải thuật phù hợp với nhau là cực kỳ quan trọng. Cũng tƣơng tự nhƣ vậy, độ đo sử dụng với các thiết bị thu nhận tín hiệu và thuật toán cũng phải phù hợp với yêu cầu bài toán. Các thiết bị cũng nhƣ phƣơng pháp của một cách tiếp cận với mục tiêu này có thể không phù hợp với mục tiêu kia và ngƣợc lại. 1 Lane-Departure-Warning Systems 2 Driver-Attention Monitoring Systems 3 Automated Vehicle-Control Systems 4 CMU: Carnegie Mellon University 5 MIT: Massachusetts Institute of Technology 8 2.1.2. Môi trường Một trong những điều kiện ảnh hƣởng nghiêm trọng đến kết quả bài toán là yếu tố môi trƣờng. Sự khác biệt về các dấu phân cách trên đƣờng có thể khác nhau ở những vùng khác nhau hay thậm chí trên cùng một đoạn đƣờng. Tiêu biểu có thể thấy trong Hình 2-2 (a) (b) Hình 2-2. Ví dụ về sự khác biệt giữa môi trƣờng a) Làn đƣờng ở trung tâm TTI. b) Làn đƣờng ở thành phố Nagoya Ví dụ cho thấy sự khác biệt về màu sắc giữa cùng các dấu phân cách (vàng và trắng), cũng nhƣ cách thể hiện (đứt nét hoặc liền nét), và cả những ký hiệu giao thông (ví dụ ký hiệu ở hình a là từ chữ tiếng Nhật). Một ví dụ khác có thể thấy rõ nét ở minh họa trong Hình 1-1 ở mục 1.1. Ví dụ này cho thấy sự khác biệt rất rõ giữa các môi trƣờng khác nhau. Vì vậy, đa phần các nghiên cứu sẽ giới hạn lại môi trƣờng mà nghiên cứu có thể áp dụng và giải quyết đƣợc. 2.1.3. Tín hiệu Khá nhiều thiết bị thu nhận tín hiệu đƣợc khảo sát trong bài toán phát hiện làn đƣờng. Một số ví dụ về các thiết bị này có thể kể ra nhƣ sau: 1. Camera và các thiết bị thị giác; 2. Các thiết bị thu nhận trạng thái của xe; 3. Thiết bị cảm ứng đƣờng thẳng (line sensor); 9 4. Thiết bị thu nhận sóng laze và ra-đa1 (LASER và RADAR); 5. Hệ thống định vị toàn cầu (GPS). Trong khi Laser, Radar, GPS và thiết bị cảm ứng đƣờng thẳng có thể giải quyết vấn đề tốt trong một số trƣờng hợp nhất định thì các thiết bị về thị giác có thể hoạt động trong hầu hết các trƣờng hợp. Laser và Radar, theo [14] có thể giải quyết rất tốt trong môi trƣờng khi xe di chuyển ở vùng ngoại ô (ít chƣớng ngại, làn đƣờng ít bị che lấp), đặc biệt hữu hiệu trong việc xác định biên đƣờng. Tuy nhiên, khi đƣờng có nhiều hơn một làn đƣờng, Laser và Radar thƣờng hoạt động không hiệu quả nếu không đƣợc bổ sung thêm thông tin thị giác. Hơn nữa, các thiết bị Laser cũng chỉ chính xác ở một số cự li gần và tốc độ di chuyển của xe không quá cao. Các thiết bị cảm ứng đƣờng thẳng, hoạt động tốt trong việc xác định vị trí ở 2 bên hiện tại của xe, tuy nhiên không thể đƣa ra thông tin ở phía trƣớc (look-ahead) và không thể sử dụng trong việc dự đoán trƣớc quỹ đạo (trajectory), vốn là một thông tin quan trọng, ví dụ nhƣ dùng để xác định thời điểm thay đổi làn đƣờng (TLC). Thiết bị GPS, đặc biệt là thiết bị dGPS (differential GPS) có thể cung cấp rất chính xác vị trí của xe, tuy nhiên để sử dụng đƣợc thiết bị này đòi hỏi phải có một cơ sở hạ tầng trang bị đầy đủ và hiện đại để có thể cung cấp thông tin chính xác. Hơn nữa, việc cập nhật bản đồ cũng phải đƣợc tiến hành thƣờng xuyên và liên tục. Việc này đòi hỏi rất nhiều chi phí để duy trì. Mặt khác, tuy cung cấp vị trí rất chính xác, nhƣng khi vào các công xƣởng và áp dụng cho các thiết bị nhƣ xe COMB2, GPS không thể hoạt động chính xác mà phải thay thế bằng Laser hay Camera. Sử dụng Camera có thể cung cấp đƣợc các thông tin về vị trí một cách chính xác mà không cần phải dựa vào các cơ sở hạ tầng bên ngoài hay các bản đồ thu thập dữ liệu. Trong những trƣờng hợp mà thông tin thu nhận đƣợc từ camera khó có thể giải quyết đƣợc, ví dụ nhƣ khi thời tiết rất xấu hay các dấu phân cách hoàn toàn không có trên đƣờng… thì thông tin thị giác có thể đƣợc bổ sung thêm bằng các thông tin khác, nhƣ Radar hay GPS. Nhờ tất cả những ƣu điểm này, thông tin thị giác tỏ ra rất thích hợp để đƣợc 1 Từ đây trở đi, chúng tôi sử dụng từ gốc Lazer và Radar do tính phổ biến của 2 thuật ngữ này. 2 Xe Comb là loại xe nhỏ, thông thƣờng chạy bằng điện, có các đặc tính giống nhƣ các xe ô-tô thông thƣờng. Xe comb thƣờng đƣợc dùng trong các công xƣởng lớn để chở hàng trong nội bộ công xƣởng. 10 dùng làm thông tin chính xây dựng nên một hệ thống hiệu quả giải quyết bài toán phát hiện làn đƣờng. Bảng 2-1 tóm tắt lại các ƣu nhƣợc điểm của những thông tin kể trên. Bảng 2-1. Tóm tắt các ƣu/nhƣợc điểm của các loại thông tin Thông tin Ƣu điểm Nhƣợc điểm Thị giác Hoạt động hiệu quả trong hầu hết các môi trƣờng. Không đòi hỏi phải có cơ sở hạ tầng trƣớc. Tận dụng đƣợc rất nhiều đặc trƣng về màu sắc. Khó hoạt động đƣợc khi môi trƣờng xung quanh gặp thời tiết rất xấu hoặc mất hoàn toàn các dấu phân cách. Trạng thái chuyển động Dùng làm thông tin bổ trợ cho các thông tin khác. Không sử dụng đƣợc một cách đơn lẻ. Cảm ứng đường thẳng Xác định chính xác đƣợc vị trí 2 bên của xe. Không thể xác định đƣợc vị trí ở trƣớc cũng nhƣ dự đoán đƣợc quỹ đạo của xe. Laser và Radar Tính toán tốt vị trí của đƣờng biên của làn đƣờng. Khó hoạt động trong đƣờng nội thành, hoặc trong môi trƣờng có quá nhiều vật phủ lấp lên nhau. Không thể cảm ứng đƣợc ở khoảng cách xa, hoặc cho xe khi chuyển động với tốc độ cao. GPS Có thể xác định đƣợc chính xác vị trí của xe. Đòi hỏi phải có một hạ tầng mạnh. Không hiệu quả khi hoạt động ở công xƣởng. Phải liên tục và thƣờng xuyên cập nhật bản đồ hệ thống. 11 2.2. Mô hình tổng quát giải quyết vấn đề Kết quả khảo sát chi tiết của McCall [14] cho thấy gần nhƣ tất cả các phƣơng pháp tiếp cận nhằm giải quyết bài toán phát hiện làn đƣờng đều theo lƣợc đồ chung nhƣ ở Hình 2-3. Hình 2-3. Mô hình tổng quát giải quyết bài toán phát hiện làn đƣờng Nguồn: [14] 1. Trƣớc tiên, một mô hình đối với xe và đƣờng đƣợc xây dựng. Mô hình này có thể chỉ đơn giản thể hiện bởi 2 cặp đoạn thẳng nhƣ trong [1] hay bởi các đƣờng cong nhƣ đƣờng B-Spline [22], hoặc đƣờng cong Catmull-Rom Spline nhƣ trong [10], hoặc là đƣờng cong bậc 3 nhƣ ở [11], hoặc cũng có thể là một mô hình toán học phức tạp gồm rất nhiều tham số nhƣ trong [3], [21]… 2. Tiếp theo, các thiết bị thu nhận tín hiệu sẽ gửi thông tin của môi trƣờng bên ngoài đến xe. Tín hiệu có thể là tín hiệu Laser [7], hoặc tín hiệu từ Camera hay GPS [12]. Tuy nhiên, trong đề tài này chỉ tập trung tìm hiểu hƣớng tiếp cận dựa tín hiệu hình ảnh kết hợp với dữ liệu của xe, hay nói cách khác, chỉ 12 chú trọng các phƣơng pháp trên thông tin thị giác kết hợp với thông tin trạng thái xe. Các đặc trƣng đƣợc sử dụng ở đây thông thƣờng là đặc trƣng về cạnh, về màu sắc của dấu phân cách, về vân, về vector chuyển động (motion vector)… 3. Cuối cùng, mô hình của xe (vehicle model) sẽ đƣợc sử dụng để tinh chỉnh lại theo thời gian khi nhận đƣợc thông tin từ các thiết bị thu nhận. Trình tự mô hình này có thể có khác biệt khi áp dụng cho từng mục tiêu khác nhau. Tuy nhiên, về cơ bản các phƣơng pháp hầu hết đều dựa trên mô hình chung này. Phần tiếp theo chúng tôi sẽ trình bày chi tiết tình hình hiện tại của các phƣơng pháp. Phần trình bày sẽ đƣợc chia thành từng vấn đề riêng dựa trên mô hình tổng quát. 2.3. Các phƣơng pháp giải quyết 2.3.1. Mô hình đường Mô hình đƣờng (road model) hay mô hình làn đƣờng (lane model) có thể nâng cao hiệu năng thực thi của ứng dụng bằng cách loại bỏ các thông tin nhiễu. Rất nhiều mô hình khác nhau đã đƣợc áp dụng thử nghiệm. Ở đây, chúng tôi sẽ liệt kê ra một số cách biểu diễn tiêu biểu: 2.3.1.1. Sử dụng đường thẳng Trong phƣơng pháp này, các làn đƣờng đƣợc mô hình nhƣ là hai đoạn thẳng trái và phải ứng với đƣờng biên trái và phải. Bertozzi và cộng sự trong nghiên cứu nổi tiếng GOLD [3] đã giả định làn đƣờng là các cặp đƣờng thẳng song song thông qua phép ánh xạ ngƣợc từ ảnh thu nhận từ camera sang ảnh từ trên nhìn xuống. Hình 2-4 cho ví dụ minh họa trong phƣơng pháp của Bertozzi. Khác với phƣơng pháp Bertozzi, Apostoloff [1] biểu diễn làn đƣờng bằng một hình thang và tiến hành trực tiếp lên ảnh từ camera. Hình 2-5 cho ví dụ về kết quả của nhóm Apostoloff. 13 Hình 2-4. Biểu diễn làn đƣờng bằng các đƣờng thẳng Nguồn: [3] Hình 2-5. Biểu diễn làn đƣờng bằng hình thang. Nguồn: [1] 2.3.1.2. Sử dụng đường cong Ƣu điểm của phƣơng pháp biểu diễn theo đƣờng thẳng là tốc độ xử lý nhanh nhờ mô hình đơn giản, dẫn đến chi phí tính toán nhỏ. Tuy nhiên, phƣơng pháp này gặp phải những khó khăn khi bản thân làn đƣờng bị cong. Mặc dù khi chuyển sang không gian từ trên xuống độ cong của đƣờng có giảm, nhƣng cũng không thể triệt tiêu đƣợc độ cong này. Mặt khác, khi gặp những trƣờng hợp nhƣ làn đƣờng thu nhỏ, hoặc mở rộng, hoặc ghép nối các làn lại với nhau… thì làn đƣờng không phải bao giờ cũng là đƣờng thẳng, hay song song với nhau. Vì vậy, đa số các nghiên cứu gần đây, biểu diễn làn đƣờng bằng đƣờng cong là mô hình đƣợc sử dụng nhiều hơn. Để biểu diễn làn đƣờng theo đƣờng cong, hầu hết các phƣơng pháp đều biểu diễn những đƣờng cong này thông qua một số điểm nhất định, gọi là các điểm kiểm soát hay điểm điều khiển. Tùy thuộc vào loại đƣờng cong đƣợc chọn mà các điểm kiểm soát sẽ đƣợc chọn khác nhau. Số lƣợng điểm kiểm soát tùy thuộc vào mô hình 14 đƣờng cong và độ phức tạp trong thực tế của làn đƣờng. Tuy nhiên, qua hầu hết các phƣơng pháp sử dụng cách biểu diễn này nhƣ [10], [11], [12], [22]… đều dùng từ 3 đến 4 điểm. Điều này không khó lý giải vì nó tƣơng tự nhƣ bài toán hồi quy (Regression), khi chọn quá nhiều điểm, hiệu quả không những không tăng mà còn giảm sút do quá khớp (overfitting). Mặt khác, khi tăng thêm một điểm kiểm soát trên mỗi đƣờng, độ phức tạp tính toán sẽ gia tăng đáng kể. Hình 2-6. Biểu diễn làn đƣờng theo B-Snake Nguồn: [22] Trong kết quả nổi tiếng của mình, Wang và cộng sự [22] biểu diễn đƣờng biên thông qua B-Snake, bản chất toán học chính là dựa trên đƣờng cong B-Spline. Lý do đƣợc đƣa ra khi sử dụng B-Snake, theo Wang là: “B-Snake có thể mô tả được những đường có hình dạng phức tạp, ví dụ hình chữ S hay dạng cua quẹo.” “Mô hình B-Snake sẽ hiệu quả đối với ảnh bị che mờ, bị nhiễu, kể cả mất dấu phân cách hoặc dấu thu nhận bị nhiễu” Ví dụ minh họa về phƣơng pháp của Wang có thể xem trong Hình 2-6, trong hình này tác giả sử dụng 4 điểm kiểm soát cho mô hình đƣờng của mình. ZuWhan Kim với công trình công bố năm 2008 [11] đƣợc đánh giá rất cao cũng biểu diễn làn đƣờng bằng một đƣờng cong, tuy nhiên, đƣờng cong đƣợc chọn ở đây là đƣờng cong bậc 3 (cubic spline) thông thƣờng với các điểm kiểm soát nằm trên 15 chính làn đƣờng. ZuWhan Kim đƣa ra lý do sử dụng cách biểu diễn này thay vì sử dụng B-Snake nhƣ sau: Trong biểu diễn B-spline, các điểm kiểm soát nằm ngoài đường cong, do vậy quá trình tính toán xấp xỉ sẽ cần rất nhiều lần lặp.”, ”Đường cong bậc 3 sẽ được tính toán xấp xỉ nhanh hơn rất nhiều” Tuy nhiên, trong trƣờng hợp dấu phân cách làn đƣờng bị mất hoặc sai lệch, phƣơng pháp của Kim lại tỏ ra không hiệu quả vì phƣơng pháp này đòi hỏi điểm kiểm soát phải nằm trên đƣờng cong. Ở đây ta lại thấy phƣơng pháp của Wang lại tỏ ra tốt hơn. Nghiên cứu mới nhất của Leonard [12] lại sử dụng một loại đƣờng cong bậc 3 khác, nhƣng về bản chất thì khá giống với đƣờng của Kim. Qua kết quả khảo sát ở trên, ta thấy vấn đề chọn loại đƣờng cong nào cũng không phải đơn giản. Trong quá trình nghiên cứu của chúng tôi, chúng tôi đề xuất đƣợc cách giải quyết cho vấn đề giữa hai phƣơng pháp của Wang và Kim nhƣ ở trên nhằm đảm bảo tính đơn giản, tốc độ trong xử lý đồng thời cũng có thể xử lý đƣợc những trƣờng hợp khó nhƣ cách làm của Wang. 2.3.1.3. Sử dụng mô hình toán học phức tạp Nhƣ đã phân tích ở trên, hiện nay phần lớn các nghiên cứu đều tập trung biểu diễn làn đƣờng theo đƣờng cong, tuy nhiên cách làm này vẫn gặp phải những hạn chế nhất định. Tiêu biểu trong số đó là vấn đề về địa hình. Trong thực tế làn đƣờng không đơn giản chỉ là ảnh 2 chiều mà là 3 chiều, do vậy, độ cong đối với các đƣờng trong 2 chiều theo cách biểu diễn nhƣ vậy là chƣa đủ đối với không gian 3 chiều. Hơn nữa, nếu gặp các đƣờng có độ cong tƣơng đối lớn, ví dụ nhƣ vòng xoay, thì với 4 điểm kiểm soát sẽ không thể dự đoán kịp quỹ đạo của làn đƣờng trong thời gian thực (do thông thƣờng độ cong của làn đƣờng là nhỏ), nếu tăng số điểm kiểm soát lên thì lại làm giảm độ chính xác và tăng thời gian xử lý. Vì vậy, một số phƣơng 16 pháp tìm cách tiếp cận xây dựng mô hình làn đƣờng một cách phức tạp và chi tiết hơn. Vacek và cộng sự [21] đƣa ra một mô hình khá phức tạp với các luật bổ sung để xác định đƣợc làn đƣờng. Danescu và cộng sự [7] đƣa ra một mô hình 3 chiều chi tiết cho làn đƣờng, tuy nhiên do tốc độ xử lý còn chậm nên không thể thực thi trong thời gian thực. Lựa chọn tốt nhất cho mô hình làn đƣờng tùy thuộc vào môi trƣờng hoạt động và hệ thống mà thiết bị phát hiện làn đƣờng đƣợc hoạt động. Sẽ thật sự không hiệu quả khi biểu diễn bằng đƣờng cong B-Spline nếu nhƣ môi trƣờng hoạt động của xe đƣợc thiết lập trên đƣờng cao tốc (highway). Mặt khác, theo khảo sát ở [24], phạm vi đƣợc quan tâm thông thƣờng chỉ ở khoảng 10m phía trƣớc xe nếu di chuyển với tốc độ không cao và 30m nếu di chuyển trên đƣờng cao tốc. Do vậy, các mô hình phức tạp nhƣ đƣờng cong hay mô hình 3 chiều đôi khi không nên sử dụng vì tính đơn giản của thị trƣờng ảnh thu nhận đƣợc trong phạm vi quan tâm. Ở mục tiêu cần có hệ thống cảnh báo khi chuyển làn đƣờng, hoặc hệ thống điều khiển xe tự động, quỹ đạo của xe cần đƣợc dự đoán trƣớc trong khoảng thời gian rất hạn chế. Trên đƣờng cao tốc, phạm vi 30m đến 40m phía trƣớc cần đƣợc dự đoán ở độ chính xác cao với các mục tiêu này. Trong những yêu cầu này, biểu diễn làn đƣờng với các mô hình đƣờng cong tỏ ra thích hợp hơn. Điều này đơn giản vì độ cong của các mô hình này cần thiết cho việc dự đoán quỹ đạo của xe. Hình 2-6 cho ta ví dụ về nhận định này. Nếu chỉ quan tâm ở vùng trong cự li gần trƣớc mặt, rõ ràng ta chỉ cần 2 đoạn thẳng, hoặc một hình thang ở khoảng điểm kiểm soát Q2 hƣớng về phía dƣới của ảnh; ngƣợc lại, nếu cần dự đoán trƣớc về quỹ đạo của làn đƣờng, rõ ràng mô hình đƣờng cong tỏ ra phù hợp hơn. 2.3.2. Xác định dấu phân cách Trong quá trình giải quyết bài toán phát hiện làn đƣờng, có thể nói rằng xác định hay rút trích đƣợc dấu phân cách (Lane Marking Extraction) là giai đoạn rất quan trọng. Nếu nhƣ ở mô hình đƣờng, vai trò của mô hình sẽ giúp gia tăng hiệu năng 17 của hệ thống thì ở đây, kết quả của việc trích làn đƣờng sẽ ảnh hƣởng trực tiếp đến toàn bộ kết quả bài toán. Nếu nhƣ kết quả rút trích không tốt, thì mô hình làn đƣờng dù hiệu quả đến đâu cũng sẽ không mang lại kết quả tốt cho bài toán. Ngƣợc lại, nếu rút trích đƣợc dấu phân cách làn đƣờng một cách hoàn hảo thì gần nhƣ không cần phải sử dụng bất kỳ một mô hình đƣờng nào. Dƣới đây chúng tôi trình bày một số hƣớng nghiên cứu trong việc rút trích dấu phân cách làn đƣờng. 2.3.2.1. Dựa trên cạnh Rút trích dựa trên cạnh là một trong những phƣơng pháp tiếp cận đƣợc sử dụng nhiều nhất. Ở phƣơng pháp này đa số các nghiên cứu tập trung vào sự khác biệt về cạnh của các dấu phân cách làn đƣờng so với mặt đƣờng. Mặt đƣờng, thông thƣờng có những đặc trƣng giống nhau và tƣơng phản rõ nét với dấu phân cách. Do vậy, bài toán rút trích làn đƣờng đƣợc đơn giản đƣa về thành bài toán phát hiện cạnh trên ảnh (edge detection) và các giải thuật tìm cạnh nhƣ Sobel, Prewitt… đƣợc áp dụng thử nghiệm. Trong số đó, giải thuật Canny [6] đƣợc sử dụng rộng rãi nhất vì độ hiệu quả cũng nhƣ tốc độ thực thi của nó. Phần lớn các nghiên cứu nhƣ [3], [4], [12], [21], [22] đều tiếp cận theo cách sử dụng Canny để rút trích cạnh rồi phát hiện làn đƣờng. Hình 2-7 cho thấy một ví dụ trong việc sử dụng Canny để trích dấu làn đƣờng. Hình 2-7. Sử dụng Canny để rút trích dấu phân cách làn đƣờng. 18 Tiếp cận này tỏ ra hiệu quả và tốc độ thực thi nhanh trong khá nhiều trƣờng hợp, tuy nhiên trong một số trƣờng hợp phức tạp hơn nhƣ các trƣờng hợp trong ví dụ ở Hình 2-8, kết quả thu nhận đƣợc gặp phải ít nhiều hạn chế. (a) (b) (c) Hình 2-8. Những trƣờng hợp trích dấu phân cách dựa trên cạnh không hiệu quả a) Bị bóng cây xe phủ. b) Bị bóng nắng tƣơng phản với nền. c) Dấu mờ hoặc không có dấu. Nguồn: [12], [14] và [11] 2.3.2.2. Dựa trên tần số Một số phƣơng pháp nhƣ LANA (Lane-finding in ANother domAin) làm việc trên miền tần số thay vì trên miền không gian ảnh thông thƣờng. Một số khác, dựa trên gradient và không gian biên để trích dấu nhƣ của [12]. Trong nghiên cứu của chúng tôi, chúng tôi có tiến hành thử nghiệm phƣơng pháp trích dấu dựa trên phƣơng pháp lƣợc đồ gradient (HOG) trong bài toán phát hiện ngƣời (Human Detection) theo cách làm của McAllester [13], nhƣng kết quả không tốt và thời gian xử lý chậm. (a) (b) Hình 2-9. Trích dấu dựa trên gradient a) Dựa trên Local Maxima. b) Phƣơng pháp Human detection dựa trên HOG Nguồn: [12], [13] 19 Cách làm dựa trên tần số này, có thể đƣợc cải tiến bằng cách giới hạn lại chiều dài của cạnh, hoặc góc cần xem xét… tuy nhiên, về cơ bản do bản chất của phƣơng pháp nên trong một số trƣờng hợp khó, ví dụ nhƣ trƣờng hợp a) trong Hình 2-8 có vân nền phức tạp thì phƣơng pháp này cũng không thể hiệu quả, gặp phải hạn chế tƣơng tự nhƣ phƣơng pháp trích cạnh trình bày ở trên. Mặt khác, độ phức tạp trong tính toán của phƣơng pháp này cũng khá cao, do phải xử lý rất nhiều thông tin. 2.3.2.3. Dựa trên màu sắc và vân Để vƣợt qua hạn chế của phƣơng pháp trích cạnh, một số hƣớng nghiên cứu tiếp cận sử dụng thông tin về màu sắc và vân để làm đặc trƣng so sánh, từ đó trích ra đƣợc dấu phân cách một cách chính xác. ZuWhan Kim [11], sử dụng một tập mẫu đƣợc trích ra từ các dấu đƣờng, sau đó tiến hành các phƣơng pháp học để rút trích đặc trƣng của dấu phân cách. Sau đó, mỗi khi thu nhận đƣợc ảnh, hệ thống sẽ nhận dạng dựa trên dữ liệu đã đƣợc học và cho ra kết quả rút trích. Các thử nghiệm của Kim đều đƣợc làm trên ảnh IPM. Hình 2-10. Ví dụ về tập ảnh huấn luyện để trích dấu làn đƣờng Nguồn: [11] Kim tiến hành thử nghiệm với các phƣơng pháp máy học khác nhau bao gồm: Intensity-Bump Detection, mạng neuron nhân tạo (ANNs), bộ phân lớp Bayes đơn giản (NBCs), máy phân lớp sử dụng vector hỗ trợ (SVM)… và cuối cùng tác giả chọn mạng neuron nhân tạo vì lý do thời gian hiệu quả và độ chính xác cũng chấp nhận đƣợc. Bảng 2-2 và Hình 2-11 cho thấy kết quả về thời gian thực thi và hiệu năng của một số thuật toán phân đoạn. Theo đó, ta có thể thấy sử dụng mạng neuron 20 có độ chính xác cao thứ nhì, sau SVM nhƣng lại có thời gian thực thi chỉ bằng 1/22 so với SVM (100ms so với 2.2s). Vì vậy, Kim đã chọn mạng neuron nhân tạo để làm thuật toán trích dấu làn đƣờng trong nghiên cứu. Bảng 2-2. Thời gian thực thi của một số thuật toán máy học. Nguồn: [11] Thuật toán Thời gian phân lớp Intensive Bump Detector Mạng Neuron nhân tạo (7 nút ẩn) Gaussian NBC NBC rời rạc SVM Cascade ~ 10 ms ~100 ms ~25 ms ~ 60 ms ~ 2.2 s ~ 25 ms trong trƣờng hợp xấu nhất Hình 2-11. Hiệu năng của một số thuật toán máy học Nguồn: [11] Về lý thuyết thì phƣơng pháp này có thể giải quyết đƣợc hầu hết các trƣờng hợp trong trích dấu làn đƣờng. Tuy nhiên, trong thực tế thông tin về dấu của làn đƣờng quá đơn giản, dễ bị nhầm lẫn với các nền khác, ví dụ nhƣ lề đƣờng, màu sắc trên xe khác… Vì vậy, nhiễu xảy ra ở phƣơng pháp này tƣơng đối khá lớn. Mặt khác, tập mẫu huấn luyện cần phải đƣợc chọn rất chi tiết và hợp lý do thời tiết khác nhau (ví 21 dụ ngày và đêm) thì sự thể hiện về màu sắc và vân của dấu làn đƣờng cũng rất khác nhau. Hình 2-12 cho ta một ví dụ về kết quả trích dấu làn đƣờng. Hình a) cho thấy kết quả khi sử dụng phƣơng pháp mạng neuron nhân tạo, các dấu làn đƣờng bị đứt nét và nhiễu khá nhiều. Hình b) cho kết qủa dựa trên cạnh, mặc dù có nhiễu ở 2 bên, nhƣng ta thấy có thể dễ dàng trích ra đƣờng biên của đƣờng. Do vậy ở giai đoạn hậu xử lý, các phƣơng pháp này đôi khi cần phải sử dụng bổ sung thêm một số kỹ thuật, ví dụ nhƣ áp dụng RANSAC [9], sẽ đƣợc trình bày ở 2.3.3. (a) (b) Hình 2-12. Nhiễu trong phƣơng pháp trích dấu làn đƣờng dựa trên màu a) Kết quả dựa trên màu. b) Kết quả dựa trên cạnh 2.3.2.4. Dựa trên nhiều camera Một phƣơng pháp cũng đƣợc sử dụng trong khoảng từ năm 2005 đến nay là sử dụng nhiều camera ghi hình. Trong phƣơng pháp sử dụng 2 camera trái và phải, nhờ biến đổi hình học giữa 2 camera, dấu làn đƣờng sẽ đƣợc rút trích dễ dàng do sự so sánh khác biệt giữa 2 ảnh. Mặt khác, dựa vào 2 camera, kết quả tính toán về khoảng cách cũng sẽ đơn giản và chính xác hơn. Tiêu biểu trong số đó là kết quả của Danescu [7]. Một số khác lại kết hợp 3 camera, một camera nhìn trƣớc, 2 camera ở 2 bên nhƣ trong nghiên cứu của nhóm Leonard [12] ở MIT1. 1 Nhờ phƣơng pháp này, nhóm của Leonard đã giành đƣợc chiến thắng ở cuộc thi DARPA Urban Challenges. 22 Hƣớng tiếp cận này hiện đang đƣợc nghiên cứu và hứa hẹn sẽ phát triển nhiều trong tƣơng lai. Hình 2-13. Ảnh thu đƣợc từ camera trái và camera phải. Hình 2-14. Sử dụng 3 camera trong nghiên cứu của Leonard Nguồn: [12] Tƣơng tự nhƣ xây dựng mô hình làn đƣờng, lựa chọn phƣơng pháp trích dấu làn đƣờng hiệu quả tùy thuộc rất nhiều vào hệ thống và môi trƣờng dự kiến hoạt động. 23 Trong trƣờng hợp sử dụng mô hình cho một số loại đƣờng nhất định, trong những khu vực xác định, đôi khi không cần phải trích xuất tất cả các dấu làn đƣờng. Tƣơng tự nhƣ vậy, trong bài toán điều khiển xe tự động, đôi khi không cần phải tìm hết tất cả các dấu làn đƣờng, mà chỉ cần quan tâm đến những dấu nào cần thiết để thiết bị có thể di chuyển an toàn. 2.3.3. Hậu xử lý Giai đoạn hậu xử lý rất cần thiết để tăng khả năng ƣớc lƣợng dựa vào những tri thức biết trƣớc kết hợp với thông tin thu nhận đƣợc từ quá trình rút trích đặc trƣng. Các kỹ thuật thƣờng đƣợc áp dụng trong giai đoạn này là biến đổi Hough, sử dụng RANSAC [9], và sử dụng luật. Chúng tôi sẽ trình bày một số kết quả tiêu biểu trong những hƣớng tiếp cận này. 2.3.3.1. Sử dụng biến đổi Hough Biến đổi Hough là kỹ thuật phổ biến đƣợc áp dụng trong nhiều nghiên cứu. Ở đây, Hough đƣợc sử dụng để nhận ra các đƣờng thẳng, sau đó sẽ tìm điểm hội tụ của các đƣờng này để từ đó dễ dàng xác định ra làn đƣờng. Các nghiên cứu [17], [18], và [22] đều sử dụng kỹ thuật này. Wang [22] sử dụng kỹ thuật CHEVP (Canny/Hough Estimation of Vanishing Points) kết hợp Canny và Hough để tìm ra các điểm hội tụ, kết quả tỏ ra rất hiệu quả. Hình 2-15 cho ví dụ về thuật toán CHEVP của Wang. 2.3.3.2. Sử dụng RANSAC ZuWhan Kim [11], trong kết quả rất ấn tƣợng của mình đã sử dụng RANSAC [9] kết nối các đoạn thẳng lại với nhau, nhằm giải quyết vấn đề nhiễu khi sử dụng trích dấu làn đƣờng dựa vào màu sắc và vân theo mạng neuron nhân tạo. Hình 2-16 cho ta thấy ví dụ về sử dụng RANSAC. Hình a) cho ta thấy kết quả trích dấu làn đƣờng, còn khá nhiều nhiễu. Ở hình b), tác giả áp dụng lọc Gauss để làm nhòe ảnh, nhằm mục đích kết nối các đoạn thẳng lại với nhau. Ở hình c) là kết quả 24 của việc áp dụng RANSAC, các đoạn thẳng đƣợc nối lại với nhau. Cuối cùng ở hình d) cho thấy kết quả sinh ra bởi Particle Filter mà chúng tôi sẽ trình bày ở mục 2.3.4. Hình 2-15. Kết quả sử dụng CHEVP của Wang Nguồn: [22] Hình 2-16. Kết quả sử dụng RANSAC của Kim Nguồn: [11] 25 2.3.3.3. Sử dụng kết hợp các đặc trưng Apostoloff và Zelinsky [1] sử dụng các luật và đặc trƣng/dấu hiệu (cue) để quyết định chọn các đặc trƣng nào sẽ đƣợc khai thác ở bƣớc tiếp theo. Theo Apostoloff, các đặc trƣng đƣợc sử dụng là những đặc trƣng dễ phát hiện, bản thân mỗi đặc trƣng đều là những luật rất yếu, nhƣng khi kết hợp lại sẽ mang lại hiệu quả cao. Các đặc trƣng đƣợc Apostoloff sử dụng là: 1. Dấu phân cách làn đường: tác giả dùng LoG với nhân (Kernel) theo chiều ngang để trích ra các đặc trƣng này. 2. Đường biên của đường: tác giả sử dụng Canny để trích ra cạnh của đƣờng. 3. Màu của đường: sử dụng hệ màu YUV và trích xuất ra màu của đƣờng. 4. Màu của những gì không phải đường: Dùng để xác định các vùng không phải là đƣờng. 5. Độ rộng của đường: Giúp tăng độ ổn định để xác định làn đƣờng. Tuy nhiên đặc trƣng này nhƣ sẽ phân tích trong phần tiếp theo, có thể làm hạn chế ở một số trƣờng hợp. 6. Độ co dãn của làn đường: Trả lại 1 nếu độ rộng bên hông xe nhỏ hơn một nửa làn đƣờng. Ngƣợc lại trả lại giá trị 0.5. Đặc trƣng này dùng để xác định các trƣờng hợp khi xe chuyển làn đƣờng… Tất cả các đặc trƣng này đƣợc kết hợp với nhau thông qua một mô hình tƣơng đối phức tạp, có kết hợp với Particle Filter. Quá trình này đƣợc trình bày chi tiết trong luận văn tiến sĩ của Apostoloff mà kết quả đƣợc thể hiện vắn tắt ở [1]. Quá trình này đƣợc minh họa ở Hình 2-17. Một cách tổng quát, quá trình hậu xử lý là một trong những bƣớc quan trọng nhất vì nó kết hợp giai đoạn rút trích đặc trƣng với giai đoạn theo vết (tracking). Dựa trên các thông tin có đƣợc từ việc rút trích đặc trƣng trong thực tế, quá trình này sẽ đƣa ra các ƣớc lƣợng quan trọng về vị trí làn đƣờng thật sự. Phần lớn các kỹ thuật này đều phải dựa trên những giả định (giản lƣợc) khác nhau về xe và môi trƣờng hoạt động. Các giả định này sẽ đƣợc trình bày ở 2.3.5. 26 Hình 2-17. Mô hình đặc trƣng kết hợp với Particle Filter của Apostoloff Nguồn: [1] 2.3.4. Mô hình chuyển động và bài toán theo vết Hai mô hình quan trọng trong kỹ thuật theo vết để phát hiện làn đƣờng là lọc Kalman và lọc Particle1. Chi tiết của hai bộ lọc này có thể tìm thấy trong các tài liệu nhƣ [2], [8] và [19]. Để làm việc hiệu quả với các bộ lọc, một số nghiên cứu sử dụng bổ sung thông tin của xe thông qua các mô hình chuyển động khác nhau, mà trong đó nổi bật nhất là mô hình Aukermann. Trong phần này, chúng tôi sẽ trình bày những nghiên cứu giải quyết bài toán phát hiện làn đƣờng có sử dụng mô hình Aukermann và 2 bộ lọc nổi tiếng này. 2.3.4.1. Mô hình Aukermann Mục đích của mô hình chuyển động gồm có 3 phần. Thứ nhất, nó phải tái thể hiện (resample) đƣợc các bộ phận (particle) hay phân bố (đối với Kalman Filter) từ xác suất hậu nghiệm của bƣớc lặp trƣớc. Thứ hai, nó phải di chuyển đƣợc các partile ứng với chuyển động của xe. Cuối cùng, nó phải phân tán đƣợc các particle để có thể phản ánh hết đƣợc các sai số ứng với mô hình độ đo sử dụng. 1 Ví tính phổ biến của 2 thuật ngữ này, chúng tôi sẽ sử dụng từ gốc tiếng Anh là Kalman Filter và Particle Filter. 27 Mô hình chuyển động của thiết bị trong hầu hết các xe (TREV của Apostoloff [1] hoặc xe của Toyota ở luận văn này) đều tuân theo mô hình Aukermann (Aukermann Steering Motion Model). Mô hình này đƣợc mô tả nhƣ trong Hình 2-18 Hình 2-18. Mô hình Aukermann Nguồn: [1] Với mô hình chuyển động này, giai đoạn theo vết sẽ dễ dàng tích hợp mô hình chuyển động này với các bƣớc lặp trong các bộ lọc nhƣ Kalman Filter hay Particle Filter. Chi tiết về các tính toán của mô hình Aukermann có thể xem ở [1]. 2.3.4.2. Kalman Filter Nhờ những đặc tính đơn giản với các giả định tuân theo giả định Markov (Markov Assumption), nên rất nhiều nghiên cứu đã chọn và sử dụng Kalman Filter để có thể giải quyết bài toán đạt hiệu quả về thời gian. Tiêu biểu trong số đó là kết quả nghiên cứu [4], [7], [14]. Tuy hiệu quả về mặt tốc độ cũng nhƣ các điều kiện đƣợc làm giảm để có thể áp dụng Kalman Filter nhƣng trong thực tế làn đƣờng sẽ có những trƣờng hợp phức tạp hơn, đặc biệt những trƣờng hợp nhƣ thay đổi độ cong lớn, mất dấu làn đƣờng… thì 28 phƣơng pháp theo vết chỉ dựa trên những giả định Markov sau một số bƣớc lặp sẽ dẫn đến kết quả kém chính xác. 2.3.4.3. Particle Filter Để khắc phục những khuyết điểm từ mô hình sử dụng Kalman Filter, rất nhiều nghiên cứu sử dụng Particle Filter để tích hợp vào hệ thống của mình. Phần lớn các nghiên cứu hiện nay đều sử dụng Particle Filter vì sự đơn giản trong cài đặt và đặc trƣng có thể “theo vết mọi thứ” [8] của phƣơng pháp này. Các kết quả nghiên cứu nổi bật trong bài toán phát hiện làn đƣờng sử dụng Particle Filter có thể chỉ ra là [1], [10], [11], [17], [18], [23]. Trong đó nghiên cứu [17] và [18] sử dụng Particle Filter để vừa theo vết và phát hiện ra dấu phân cách vừa phát hiện ra làn đƣờng; các nghiên cứu khác sử dụng Particle Filter dựa trên kết quả rút trích đặc trƣng từ những phƣơng pháp ở bƣớc trƣớc để theo vết và xác định làn đƣờng. Tƣơng tự nhƣ việc lựa chọn mô hình làn đƣờng, lựa chọn mô hình theo vết phù hợp tùy thuộc rất nhiều vào mục tiêu bài toán cần giải quyết. Với những mục tiêu nhƣ điều khiển xe tự động, những mô hình phức tạp và phù hợp với thực tế hơn cần đƣợc sử dụng để tăng độ ổn định và chính xác trong di chuyển. Tuy nhiên, khi áp dụng vào các mục tiêu nhƣ thông báo thay đổi làn đƣờng, thƣờng sử dụng ở đƣờng cao tốc, rất ít có sự thay đổi về độ cong của làn đƣờng, thì những mô hình xấp xỉ tuyến tính đơn giản, hay sử dụng lọc Kalman với các giải định Markov sẽ không làm thay đổi kết quả của hệ thống. Tất cả các phần đã trình bày ở trên: mô hình làn đƣờng, kỹ thuật rút trích đặc trƣng, hậu xử lý, mô hình chuyển động và theo vết… đều tùy thuộc rất lớn vào các giả định của bài toán. Hiện tại, với sự phức tạp của bài toán chƣa có một phƣơng pháp nào có thể giải quyết trọn vẹn các tình huống khác nhau. Vì vậy, giả định ban đầu về bài toán có thể sẽ mang lại các phƣơng pháp rất khác nhau. Phần tiếp theo chúng 29 tôi sẽ trình bày về những giả định này cùng với các nghiên cứu tốt nhất tính đến thời điểm thực hiện luận văn. 2.3.5. Các giả định Một trong những phƣơng pháp hiệu quả để nâng cao hiệu năng trong việc giải quyết bài toán phát hiện làn đƣờng là đặt ra một số giả định nhằm hạn chế bớt phạm vi của bài toán. Những giả định phổ biến gồm: 1. Vân (texture) của đƣờng/làn đƣờng là đồng nhất. 2. Độ rộng của làn đƣờng là một hàm hằng từng khúc (locally constant). 3. Các dấu phân cách tuân theo một số quy luật nghiêm ngặt. 4. Mặt đƣờng là phẳng, hoặc nếu có thay đổi sẽ là liên tục từng mảnh. 5. Độ cong của làn đƣờng nằm trong một ngƣỡng giới hạn. Tất cả các giải thuật hiện tại đều dùng một hoặc nhiều giả định kể trên để giải quyết vấn đề. Sử dụng các giả định làm tăng hiệu quả của các thuật toán rất nhiều, tuy nhiên cần phải hiểu rõ vai trò của chúng để có thể sử dụng cho hợp lý. Giả định toàn bộ vân đƣờng đều đồng nhất sẽ giúp ích rất nhiều vì toàn bộ mặt đƣờng khi đó sẽ đƣợc sử dụng làm đặc trƣng thay vì chỉ có thể sử dụng dấu phân cách. Trong trƣờng hợp dấu phân cách cách xa nhau hoặc bị mờ, mất… hoàn toàn có thể suy ra đƣợc thông qua các mô hình cũng nhƣ bộ lọc [1], [11], [14]… Tuy nhiên, trong trƣờng hợp có sự tăng/giảm làn đƣờng, kết quả sẽ bị ảnh hƣởng rõ rệt. Giả định độ rộng của làn đƣờng là hằng số cục bộ làm tăng hiệu quả khá nhiều cho các mô hình sử dụng biên trái và phải cho làn đƣờng nhƣ [10], [11], [17], [18]. Trong mô hình sử dụng làn đƣờng theo 3 chiều, toàn bộ đƣờng có thể tái xây dựng lại nếu sử dụng giả thiết làn đƣờng là hằng số nhƣ trong phƣơng pháp [12]. Giả định này hiệu quả trong phần lớn đƣờng rộng hoặc đƣờng cao tốc. Tuy nhiên, khi áp dụng cho các đƣờng trong thành thị hay khi đƣờng cao tốc gặp phải sự tăng/giảm các làn đƣờng thì độ rộng là 30 hằng số không thể sử dụng đƣợc. Hơn nữa, vấn đề giải quyết bài toán xác định làn đƣờng khi có sự hợp nhất các làn đƣờng thƣờng đƣợc đánh giá rất cao, nên những phƣơng pháp hiện đại đều cần phải giải quyết đƣợc vấn đề này. Dấu phân cách làn đƣờng thƣờng đƣợc giả định là các đƣờng liền nét nhƣ trong [3], tuy nhiên trong thực tế giả định này rất khó sử dụng vì làn đƣờng thƣờng hay thể hiện rời rạc, hoặc bị mất dấu. Hơn nữa, dấu làn đƣờng không phải luôn có dạng hình chữ nhật hoặc có độ rộng cố định mà có thể có những hình dạng khác, hoặc có những ký hiệu khác. Hình 2-19 cho thấy ví dụ về những ký hiệu lạ (tiếng Nhật) trên đƣờng có thể làm nhầm lẫn với dấu phân cách làn đƣờng, hoặc dấu làn đƣờng dạng đặc biệt (hình bên phải). Hình 2-19. Một số dạng dấu phân cách đặc biệt trên đƣờng Giả định toàn bộ đƣờng nằm trên mặt phẳng tỏ ra rất hữu hiệu, phần lớn các nghiên cứu hiện tại đều sử dụng giả định này. [1], [3], [4], [10], [11], [14], [17], [18], [21], [22], [23] đều giả định mặt đƣờng là phẳng. Tuy nhiên, giả định này có thể sai khi mặt đƣờng bị cong hoặc thay đổi độ cao, trƣờng hợp rất hay gặp trong thực tế. Hiện tại có rất ít mô hình tiếp cận theo hƣớng xây dựng mô hình mặt đƣờng nhƣ một mặt cong trên không gian 3 chiều nhƣ của [7] và [12] vì chi phí tính toán cao và sai số vẫn còn rất khó kiểm soát. Giả định độ cong của đƣờng nằm trong một phạm vi nhất định cũng đƣợc hầu hềt các nghiên cứu sử dụng. Trong thực tế, đặc biệt là trên đƣờng cao 31 tốc, hầu nhƣ rất ít khi có sự thay đổi độ cong quá lớn trên đƣờng. Hơn nữa, thị trƣờng quan tâm trƣớc mắt ngƣời điều khiển xe, kể cả trong trƣờng hợp điều khiển xe tự động thƣờng chỉ trong phạm vi từ 10m đến 30m phía trƣớc. Trong phạm vi này, độ cong còn trở nên nhỏ hơn nữa. Đặc biệt, dƣới phép biến đổi IPM, đổi ảnh từ không gian camera sang không gian thực theo từ trên nhìn xuống, độ cong trong thị trƣờng quan tâm càng giảm nhỏ và gần nhƣ đa số các làn đƣờng trong thị trƣờng đều xấp xỉ là các đoạn thẳng. Tuy nhiên, khi gặp một số tình huống thông dụng nhƣ xe thay đổi hƣớng di chuyển ở giao lộ, hoặc xe di chuyển vào vòng xoay, hoặc xe tiến hành quay đầu (u-turn) thì giả định này không thể hoạt động chính xác. Mặt khác, đôi khi bản thân làn đƣờng sẽ suy giảm hoặc gia tăng độ rộng, khi đó không phải làn đƣờng bị cong mà chỉ một trong 2 (hoặc cả 2) đƣờng biên thay đổi độ cong đột ngột. Trong những trƣờng hợp nhƣ vậy, giả định độ cong nhỏ không thể giải quyết đƣợc bài toán một cách hiệu quả. Nếu gia tăng phạm vi độ cong, độ phức tạp tính toán và đôi khi toàn bộ cả mô hình đều phải thay đổi. Từ tất cả khảo sát ở trên, mục tiêu đặt ra của đề tài là thiết kế đƣợc phƣơng pháp hiệu quả để có thể hoạt động đƣợc trong thời gian thực, đồng thời có thể vƣợt qua đƣợc phần lớn những trƣờng hợp phức tạp nhƣ đã kể ở trên. Trong chƣơng tiếp theo, chúng tôi sẽ trình bày chi tiết các phƣơng pháp trong nghiên cứu của luận văn này.