Dùng RANSAC để loại bỏ nhiễu trong mô hình
Computer Vision
11
White

Ngoc Dao viết ngày 23/03/2016

Giả sử Việt Nam có 19 người nghèo và 1 tỉ phú. Mỗi người nghèo có thu nhập 5 đồng, tỉ phú có thu nhập 1 tỉ. Nếu tính theo kiểu trung bình cộng, thì thu nhập trung bình của dân Việt Nam vào khoảng 50 triệu. Nếu tính theo kiểu trung vị, thì ra 5 đồng. Cách tính thứ 2 cho phép giảm nhiễu, và nhiễu ở đây chính là ngài tỉ phú.

Phương pháp trung vị thật ra chỉ hạn chế chứ vẫn bao gồm cả nhiễu. Nếu loại bỏ luôn được nhiễu thì quá hay. Hầu hết giải thuật lập trình viên bình thường biết chỉ liên quan đến dữ liệu hoàn hảo, chính xác tuyệt đối, không chứa nhiễu (nói cách khác, coi nhiễu cũng là dữ liệu chính xác). Bài viết này giới thiệu giải thuật khử nhiễu RANSAC, có tính ứng dụng cao mà không khó hiểu lắm. Thông qua tìm hiểu RANSAC, ta cũng sẽ hiểu được khái niệm sơ khai về dân chủ.

Mô hình là gì?

Về mặt toán học, mô hình là hình thức biểu diễn một cách tổng quát quan hệ giữa các thuộc tính của cùng một phần tử, thường bằng đẳng thức. Ví dụ để biểu diễn tập hợp các điểm (x, y) nằm trên đường tròn tâm (a, b) bán kính r, ta dùng mô hình (x - a)^2 + (y - b)^2 = r^2. Mô hình trên được tham số hoá bởi bộ ba (a, b, r). Tuỳ cách hiểu mà có mô hình khác nhau, ví dụ chỉ cần thay đổi hệ qui chiếu là ta có bộ ba (a, b, r) mới.

Việc tìm ra mô hình tổng quát dựa vào thuộc tính của các phần tử của tập hợp hữu hạn là nội suy, vì ta suy từ những cái cụ thể ra cái tổng quát, từ trong ra. Sau khi suy ra mô hình, không nhất thiết tất cả các phần tử đều phải khớp ngược trở lại vào mô hình. Ví dụ mô hình suy ra từ 19 người nghèo và tỉ phú là: Thu nhập = 5 [đồng], nhưng tỉ phú không khớp vào mô hình này.

Về mặt xác suất thống kê, khi kiểm tra phần tử có khớp vào mô hình hay không, ta không dùng dấu =, mà dùng dấu gần bằng, nghĩa là có xét đến nhiễu. Phần tử không khớp gọi là phần tử gây nhiễu, tiếng Anh là outlier (cẩn thận viết nhầm thành outliner).

RANSAC là gì?

Bài toán

Để dễ hiểu, phần tiếp theo sử dụng bài toán cụ thể. Từ cụ thể ta suy ra tổng quát.

  • Cho toạ độ của N điểm trên mặt phẳng.
  • Giả sử có một số điểm nằm trên đường thẳng, còn các điểm khác là nhiễu (nghĩa là biết chắc có 2 tập hợp con, còn gọi là cluster).
  • Hãy tìm phương trình đường thẳng, và cho biết những điểm nào được coi là nằm trên đường thẳng, những điểm nào được coi là nhiễu.

Người ta phân biệt 2 loại cách giải: theo xác suất thống kê cổ điển (classical statistics) và theo xác suất thống kê chống nhiễu (robust statistics). Đặc điểm của các phương pháp theo xác suất thống kê cổ điển là luôn gồm luôn cả nhiễu, nên đáp số bị ảnh hưởng bởi nhiễu.

Giải bằng phương pháp bình phương tối thiểu

Cách giải thuộc loại xác suất thống kê cổ điển nổi bật nhất có lẽ là phương pháp bình phương tối thiểu. Nó cho phép tìm ra một đường khớp nhất cho tất cả các điểm, với tổng các khoảng cách (sai số) từ từng điểm đến đường thẳng là nhỏ nhất. Tuy nhiên nếu dữ liệu chứa quá nhiều outlier (ví dụ một nửa số điểm), thì tất cả cách giải thuộc loại xác suất thống kê cổ điển đều cho kết quả sai bét.

Giải bằng RANSAC

Bí quyết của các cách giải thuộc loại xác xuất thống kê chống nhiễu là làm sao loại bỏ outlier, để không sử dụng outlier khi tính toán mô hình.

RANSAC là viết tắt của RANdom SAmple Consensus (cẩn thận viết nhầm thành concensus). Giải thuật như sau:

Đầu vào:
data - tập hợp các điểm
k - số lần lặp
t - ngưỡng (threshold) sai số để xác định điểm nào đó có khớp mô hình không

Đầu ra:
best_model - mô hình tốt nhất
best_consensus_set - tập hợp các điểm khớp với best_model

best_model = nil
best_consensus_set = nil
best_num_points = 0

loop k lần
consensus_set = tập hợp 2 điểm ngẫu nhiên thuộc data
model = mô hình đường thẳng suy ra từ 2 điểm trên

với mỗi điểm point thuộc data nhưng không thuộc consensus_set
distance = khoảng cách từ point đến đường thẳng
if distance < t (point được coi là khớp với model nếu sai số nhỏ hơn t)
thêm point vào consensus_set

num_points = số lượng phần tử trong consensus_set
if num_points > best_num_points
best_model = model
best_consensus_set = consensus_set
best_num_points = num_points

return best_model và best_consensus_set

Trong giải thuật, ta chọn ra 2 điểm ngẫu nhiên, vì 2 là số lượng điểm tối thiểu để có thể tính toán mô hình đường thẳng. Với bài toán tổng quát, ta cần chọn ra số phần tử tối thiểu để có thể tính toán mô hình.

Như vậy, ý tưởng của RANSAC giống như bầu phiếu dân chủ:

  • Từ các cá thể, có thể suy ra nhiều mô hình
  • Đặt ra nguỡng nào đó
  • Bỏ phiếu: đối với mỗi mô hình, tính khoảng cách của mỗi cá thể đối với mô hình, cá thể nào có khoảng cách vượt quá ngưỡng coi như nhiễu, nằm ngoài mô hình
  • Kiểm phiếu: mô hình hợp với nhiều cá thể nhất là mô hình tốt nhất

Chương trình ví dụ

Dựa vào giải thuật trên, ta thử viết chương trình xem sao.

Trước hết để chuẩn bị cần ôn lại kiến thức toán cấp 2:

Tiếp đó cần chuẩn bị dữ liệu: từ tấm ảnh trên cần trích ra toạ độ các điểm. Nếu có sức khoẻ, có thể mở ảnh trên bằng chương trình xem ảnh cho phép xem toạ độ chuột (PaintBrush trên Windows chẳng hạn), rồi dò tọa độ từng điểm. Nếu lười, có thể viết chương trình dò giá trị màu của từng pixel để tính ra.

Bây giờ đến bước viết chương trình. Chỉ cần dựa vào giải thuật và bước chuẩn bị là viết được ngay.

Cuối cùng sau khi có kết quả, cần trực quan hoá kết quả thành tập tin ảnh để xác nhận bằng mắt.

Đây là chương trình viết bằng Ruby:

  • Mô hình đường thẳng: ax + by = 1, có hạn chế là không thể chứa điểm có toạ độ (0, 0).
  • Dùng thư viện RMagick để đọc ảnh đầu vào và xuất kết quả ra ảnh.

Tham khảo: Bài viết về RANSAC trên Wikipedia

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Ngoc Dao

102 bài viết.
284 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
62 8
Làm thế nào để nâng cấp trang web mà không làm gián đoạn dịch vụ? Đây là câu hỏi phỏng vấn các công ty lớn thường hỏi khi bạn xin vào vị trí làm lậ...
Ngoc Dao viết hơn 2 năm trước
62 8
White
40 1
Bài viết này giải thích sự khác khác nhau giữa hai ngành khoa học máy tính (computer science) và kĩ thuật phần mềm (software engineering), hi vọng ...
Ngoc Dao viết hơn 2 năm trước
40 1
White
34 1
Nếu là team leader, giám đốc công ty hay tướng chỉ huy quân đội, vấn đề cơ bản bạn gặp phải là “hướng mọi người đi theo con đường bạn chỉ ra”. Thử...
Ngoc Dao viết hơn 2 năm trước
34 1
Bài viết liên quan
White
1 2
Kĩ thuật chụp ảnh ra đời từ khoảng 2 thế kỉ trước. Nếu để ý, sẽ thấy tất cả ảnh giấy tồn tại được cho đến ngày nay đều là ảnh sepia. Sepia là từ ti...
Ngoc Dao viết hơn 2 năm trước
1 2
White
0 1
Có ảnh mẫu của một vật thể (ví dụ: ô tô), và ảnh thật chứa một vài vật thể ấy (ví dụ: các ô tô trong bãi đỗ xe). Làm sao để nhận dạng được vị trí c...
Ngoc Dao viết hơn 2 năm trước
0 1
White
10 5
(Ảnh) Ai đã tìm hiểu qua về xử lí ảnh (ví dụ dùng thư viện nổi nhất hiện nay là (Link)), chắc đều từng bắt gặp tấm ảnh này. Tuy nhiên có lẽ không ...
Ngoc Dao viết hơn 2 năm trước
10 5
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
102 bài viết.
284 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!