Blog cộng đồng về Công nghệ thông tin

Giới thiệu

Xin đọc Wikipedia. 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.

Thư viện

OK. Nếu bạn là kĩ thuật viên hoặc kĩ sư phần mềm chứ không phải cử nhân khoa học máy tính thì cũng chẳng cần biết chi tiết giải thuật, chỉ cần hiểu ý tưởng và đặc điểm trình bày ở trên, rồi kiếm thư viện có sẵn mà dùng phải không?

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

Xem đề bài năm nay của cuộc thi giải thuật về nhận dạng ảnh của tổ chức PRMU. Vấn đề là tìm ra vị trí trong ảnh thật có chứa ảnh mẫu. Có 3 độ khó:

1. Ảnh mẫu bị phóng to/thu nhỏ
   
2. Ảnh mẫu bị phóng to/thu nhỏ và xoay
   
3. Ả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

Vì cuộc thi trên chú trọng về giải thuật, mà SIFT nói chung đã phổ biến, nên nếu dùng SIFT thì không được ban giám khảo đánh giá cao. Tuy vậy, ta thử giải bằng SIFT xem sao:

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ả.

Tham khảo

• Loạt bài giải thích chi tiết giải thuật SIFT
• Giải thuật ASIFT nhận dạng được nhiều điểm hơn