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

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

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

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.
300 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
66 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
66 8
White
42 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
42 1
White
38 2
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
38 2
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
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
White
2 0
Hệ thống thị giác của con người rất phức tạp. Có 2 bộ phận chính: mắt, phần dễ hiểu, và nhận thức về tín hiệu do mắt nhận được được xử lí bởi não b...
Ngoc Dao viết hơn 2 năm trước
2 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

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


White
{{userFollowed ? 'Following' : 'Follow'}}
102 bài viết.
300 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á!