Phân đoạn bằng thuật toán RANSAC

   Các phương pháp phân đoạn dữ liệu đám mây điểm là chủ đề đã được nghiên cứu trong thời gian dài. Một cảnh ảnh P được thu thập từ cảm biến RGB- D sẽ thể hiện các vật thể được quét qua dưới dạng đám mây điểm. Trong điều kiện lý tưởng, với các mô hình vật thể đều đã có trong cơ sở dữ liệu thì tập dữ liệu P sau khi thu thập từ cảm biến sẽ có thể được đơn giản hóa đi đáng kể: Các điểm trong P thể hiện một mô hình (hay một phần của mô hình) sẽ được thay thế bởi mô hình đó với các thông số thể hiện vị trí, tư thế (hay góc nhìn) và kích cỡ thực tế. Điều này được thực hiện với tất cả các điểm trong tập dữ liệu P và sau đó dẫn đến một kết quả rằng thay vì lưu trữ một đám mây điểm P thì ta chỉ cần lưu trữ một bộ các thông số thể hiện những mô hình xuất hiện trong P với vị trí, góc nhìn và kích cỡ của chúng.

 Tuy nhiên một cảnh ảnh quét từ cảm biến (2.5D hoặc 3D) bao giờ cũng xuất hiện nhiễu. Nhiễu lượng tử tác động lên cảm biến khiến cho từng điểm bị lệch đi so với giá trị thực tế của chúng một khoảng σ dao động tùy theo các loại cảm biến, khoảng cách từ vật đến cảm biến. Hơn nữa, với những khung cảnh phức tạp, chứa nhiều đồ vật thì việc các đồ vật che khuất nhau hay gây ra các hiện tượng vật lý như phản xạ, tán xạ ánh sáng làm cho việc kết hợp ảnh RGB và ảnh Depth được thực hiện không chính xác tại một số nơi. Các khung cảnh phức tạp còn khiến cho đa số các vật thể không xuất hiện đầy đủ dưới cảm biến mà chỉ xuất hiện một phần, một phía.

Hình 1. Phân đoạn trong đám mây điểm. 

Kỹ thuật phổ biến nhất trong việc phân đoạn đám mây điểm là đơn giản hóa dữ liệu bằng việc thay thế các điểm bằng các hình 3D cơ bản như mặt phẳng, mặt trụ, mặt cầu, mặt nón, hoặc thậm chí là các hình 3D với các đa thức bậc cao.

Việc thay thế (hay xấp xỉ) các điểm trong đám mây điểm bằng các bề mặt hình học 3D đơn giản là khả thi trong đa số các trường hợp thực tế. Khi sử dụng cảm biến RGB-D quét các khung cảnh trong nhà hay ngoài trời, ta có thể thấy rằng đa số những vật thể xuất hiện đều là sự kết hợp của các hình 3D cơ bản: bức tường hay sàn nhà, mặt tủ đều là các mặt phẳng; chướng ngại vật hay đồ đạc trong nhà lại là các mặt trụ, mặt nón hay mặt cầu kết hợp…

 Chi tiết hơn về tác dụng của quá trình thay thế này cũng có thể được hiểu trong các trường hợp cụ thể. Ví dụ như xét bài toán robot di chuyển trong nhà, tránh vật cản và tính toán đường đi hợp lý. Nếu môi trường xung quanh được cung cấp dưới dạng đám mây điểm với hàng ngàn điểm, thì việc tính toán khoảng cách đến từng điểm trong số này là công việc nặng và tiêu tốn tài nguyên. Tuy nhiên khi đơn giản hóa môi trường bằng các mô hình với các hình khối 3D thì việc tính toán khoảng cách và xác định vị trí robot trở nên đơn giản hơn nhiều với các phép tính khoảng cách từ điểm đến các bề mặt, với số bề mặt được giới hạn. Phương pháp phân đoạn được trình bày ở đây là phương pháp RANSAC (Random Sample Consensus). Thuật toán RANSAC là thuật toán lặp với mục đích ước lượng các thông số của một mô hình toán học từ một bộ dữ liệu thu thập được bao gồm cả các điểm trong và ngoài. Các điểm trong là những điểm trong bộ dữ liệu phù hợp (hay nằm trong) mô hình toán học đó, còn điểm ngoài là những điểm không nằm trong mô hình.

Thuật toán RANSAC được công bố lần đầu bởi Fischler và Bolles, với nguyên tắc ước lượng các thông số bằng cách chọn ngẫu nhiên các mẫu trong dữ liệu thu thập được. Với tập dữ liệu đầu vào bao gồm cả các điểm trong và ngoài mô hình, thuật toán RANSAC sử dụng nhiều lần thử để tìm ra mô hình có kết quả tốt nhất. Về cơ bản, thuật toán RANSAC lặp đi lặp lại hai quá trình:

-             Chọn ngẫu nhiên một số lượng tối thiểu dữ liệu từ đầu vào (điểm mẫu), sau đó tính toán các thông số của mô hình chứa các điểm mẫu này.

-             Thuật toán kiểm tra tất cả các điểm còn lại xem chúng nằm trong hay nằm ngoài mô hình. Một điểm được coi là nằm trong mô hình nếu sai số của nó so với mô hình nhỏ hơn sai số qui định.

-             Thuật toán RANSAC lặp lại quá trình trên cho đến khi bộ các điểm trong đủ lớn hoặc đạt giá trị lớn nhất sau một số lần lặp lại cho trước.

(a): Dữ liệu đầu vào

(b): Mô hình được ước lượng với các điểm màu xanh là điểm trong và màu đỏ là điểm ngoài

                         Hình 2. Thuật toán RANSAC ước lượng mô hình đường thẳng.

Thuật toán RANSAC có đầu vào là bộ dữ liệu thu thập được, phương pháp để khớp dữ liệu thu thập vào mô hình và các thông số tin cậy (như sai số cho phép, số lần lặp tối đa). Quá trình thực hiện của RANSAC như sau:

-             Chọn một bộ nhỏ nhất các điểm mẫu bất kì từ dữ liệu đầu vào, giả thiết các điểm này đều là điểm trong.

-             Tính toán các thông số của mô hình chứa các điểm đó.

-             Kiểm tra tất cả các điểm còn lại trong dữ liệu đầu vào xem chúng nằm trong hay nằm ngoài mô hình dựa vào mô hình vừa tính được và sai số cho phép.

-             Mô hình vừa xấp xỉ là tốt nếu số điểm trong thỏa mãn yêu cầu.

-             Quá trình này được lặp lại để phát hiện các mô hình tốt hơn.

-             Các tham số tin cậy quan trọng trong việc thực hiện thuật toán RANSAC là ngưỡng sai số cho phép ε và số lần lặp lại N. Ngưỡng sai số cho phép ε là giá trị khoảng cách lớn nhất từ một điểm đến mô hình để điểm đó còn được coi là điểm trong. Việc xác định ε với từng trường hợp cụ thể thường dựa trên kinh nghiệm và ước lượng thực tế.

-             Số lần lặp lại N cũng có thể được ước lượng hợp lý để cân bằng giữa kết quả và thời gian tính toán. Số lần lặp N có thể được tính bằng phương pháp thống kê.

Giả sử p là xác suất thành công của thuật toán (thông thường p = 0.99). Gọi u là xác suất để một điểm trong tập dữ liệu thu được là điểm trong, v là xác suất để điểm đó là điểm ngoài, ta có                 .

Gọi m là số điểm trong để mô hình thu được là tốt, khi đó xác suất để thu được một mô hình tốt là .

Trong mỗi lần thử, thuật toán thất bại khi không tìm được mô hình nào đủ tốt, tức là không có mô hình nào có đủ m điểm trong.

Xác suất để điều này xảy ra là  1-u^m

Sau N lần lặp lại, xác suất thất bại là : (1-u^m)^n=1-p

Qua đó ta có thể tính được số lần lặp lại tối ưu với xác suất thành công   :

Ưu điểm của thuật toán RANSAC là độ bền vững, nói cách khác là RANSAC có thể tìm ra mô hình thích hợp với độ chính xác rất cao trong bộ dữ liệu thu thập được mặc dù bộ dữ liệu đó chứa nhiều điểm ngoài.

Nhược điểm của RANSAC là ở chỗ không có giới hạn về thời gian tính toán các thông số mô hình. Khi số lần lặp lại bị giới hạn, giải thuật có thể không đưa ra được mô hình tối ưu. Do đó khi thực hiện RANSAC, người sử dụng phải cân bằng giữa thời gian tính toán và chất lượng mô hình ước lượng được. Với số lần lặp lại càng tăng, xác suất để RANSAC đưa ra các mô hình tốt hơn cũng tăng.

Một nhược điểm khác của RANSAC là giải thuật chỉ có thể ước lượng được một mô hình với mỗi bộ dữ liệu đầu vào. Nếu tập dữ liệu đầu vào chứa nhiều mô hình cần tìm (ví dụ như một đám mây điểm chứa hai hay nhiều mặt phẳng), RANSAC chỉ có thể tìm ra mặt phẳng lớn nhất, hay mặt phẳng chứa nhiều điểm nhất.