Giới thiệu giải thuật SIFT để nhận dạng ảnh

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ủa các vật thể trong ảnh thường? Đây là vấn đề rất căn bản trong xử lí ảnh. Giải được vấn đề này, mở rộng ra ta có thể làm được rất nhiều thứ: nhận dạng chữ viết, nhận dạng khuôn mặt, nhận dạng biển số xe, đăng nhập bằng hình ảnh thay cho mật khẩu, theo dõi quĩ đạo của vật thể v.v.

Có nhiều cách để giải quyết vấn đề trên. Bài viết này giới thiệu SIFT, giải thuật siêu mạnh áp dụng được cho hầu hết các tình huống.

Giới thiệu

SIFT là phát minh đã được đăng kí bản quyền của David Lowe, muốn dùng cho mục đích thương mại thì phải xin phép.

Ý tưởng:

• Từ ảnh tìm ra các điểm ảnh đặc biệt, gọi là feature point hay keypoint. Đầu vào và đầu ra của phép biến đổi SIFT: ảnh -> SIFT -> các keypoint
• Để có thể phân biệt keypoint này với keypoint khác cần tìm ra tham số gì đó, gọi là descriptor. 2 keypoint khác nhau thì phải descriptor khác nhau. Thường thì descriptor là chuỗi số gồm 128 số (vector 128 chiều).
• Sau khi áp dụng biến đổi SIFT, ứng với mỗi keypoint, thu được (1) toạ độ keypoint (2) scale và orientation của keypoint (3) descriptor. Các mũi tên trong hình dưới vẽ nhờ vào scale và orientation.
  
  

Đặc điểm:

• Keypoint phụ thuộc rất ít vào cường độ sáng, nhiễu, che khuất (một phần ảnh bị che), góc xoay (ảnh bị xoay trong mặt phẳng 2D), thay đổi của tư thế (pose thay đổi trong không gian 3D).
• Nhanh, tốc độ xử lí gần như thời gian thực (realtime).

Như vậy việc khớp ảnh mẫu với ảnh thường chính là việc khớp các keypoint trong 2 ảnh với nhau:

• Áp dụng SIFT cho từng tấm.
• So sánh descriptor của keypoint trong ảnh này với descriptor của keypoint trong ảnh kia. Nếu 2 keypoint có descriptor gần giống nhau thì coi như 2 điểm trên 2 tấm ảnh cùng thuộc về một vật (hoặc vật giống nhau).
• Dựa vào thương của scale và hiệu của orientation của 2 keypoint, có thể biết thêm vật trong hình này to hơn vật trong hình kia bao nhiêu, vật trong hình này xoay bao nhiêu độ so với vật trong hình kia bao nhiêu.

Trang web của MIT có liệt kê vài thư viện cho một số ngôn ngữ: MATLAB, C/C++, C#, Java.

Đề bài tập áp dụng

Tìm ra vị trí trong ảnh thật có chứa ảnh mẫu. Có 3 độ khó:

1. Trong ảnh thật, ảnh mẫu bị phóng to/thu nhỏ
2. Trong ảnh thật, ảnh mẫu bị phóng to/thu nhỏ và xoay
3. Trong ảnh thật, ảnh mẫu bị phóng to/thu nhỏ, xoay và khuất một phần

Giải bài tập bằng SIFT

1. Áp dụng SIFT cho 2 ảnh.
2. Dùng khoảng cách Euclid giữa các descriptor để tìm keypoint khớp nhau (gần giống nhau, nghĩa là khoảng cách bé hơn giá trị THRESHOLD nào đó) trong 2 ảnh. Đây là bài toán tìm "hàng xóm" (ví dụ biết tọa độ của N điểm trong mặt phẳng 2D, hãy tìm 2 điểm gần nhau nhất), có nhiều cách tốt hơn nhưng phức tạp hơn nhiều.
3. Ở vị trí của keypoint nào khớp, thì dựa vào scale và orientation để dán mask của ảnh mẫu vào ảnh thật vào vị trí đó, để đánh dấu khu vực quanh vị trí khớp đã được kiểm tra (search). Keypoint nào nằm trong khu vực này sẽ bị xoá khỏi danh sách keypoint của ảnh thật, để tránh bị lấy ra xử lí tiếp.
4. Lặp lại bước 3 đến khi nào không còn keypoint khớp nhau. Ở mỗi lần lặp ở bước 3 ta đều thu được vị trí, chính là lời giải cần tìm.

Ngoài ra, đọc kĩ đề bài ta thấy ảnh mẫu chỉ bị phóng to thu nhỏ và xoay chứ không bị thay đổi màu sắc hay độ sáng. Do đó để tăng độ chính xác của SIFT, trước bước 1 có thể dùng thêm color filter như sau:

1. Liệt kê tất cả các màu có trong ảnh mẫu (nghĩa là tính color histogram). Có thể dùng không gian màu RGB hoặc HSV.
2. Xoá (bôi đen) tất cả các điểm ảnh trong ảnh thật nếu màu của chúng quá khác (khi phóng to thu nhỏ và xoay, màu của điểm ảnh có thể thay đổi chút ít tuỳ vào phương pháp phóng to thu nhỏ và xoay) màu trong ảnh mẫu.

Ở trên là giải thuật. Việc dùng thư viện để viết thành chương trình cụ thể xin dành cho độc giả.