9. Image Feature Extractor part 7: SIFT to SURF

Mở đầu

(Speeded-up Robust Feature)

Tiếp sau khi tìm hiểu về SIFT và ứng dụng trong homography, ta tìm hiểu một phiên bản cải tiến phổ biến của SIFT là SURF

Ý tưởng

Giống như SIFT, SURF cũng gồm 2 phần là:

- Feature Extraction: Cũng tìm kiếm trích xuất các interest point

- Feature Description: Giống như SIFT, cũng có phần miêu tả các iterest point để kết hợp thành các match

Feature Extraction

Ở SIFT, ta sử dụng các bộ lọc xếp tầng (Pyramid) để phát hiện các bất biến tỉ lệ ( Scaling Invariance), tức là ta dựa vào thuật toán Difference of Gaussian (DoG) và các hình ảnh tích phân.

SURF tối ưu thời gian xử lí hơn bằng cách xử dụng các bộ lọc hình vuông như một phép gần đúng

Tức thay vì dùng đạo hàm như SIFT, ta sử dụng tổng pixel trong hình chữ nhật

Sau đó, ta dùng Hessian matrix (tối ưu khá tốt trong sử dụng thời gian và độ chính xác):

Vì thêm Gaussian Kernel, Hessian matrix tại một điểm X có scale (kích cỡ) denta là:

L là đạo hàm bậc 2

Nhìn thấy có vẻ khá giống matrix trong thuật toán Harris Corner Detector

Vì sao không dùng mỗi Gaussian?

Gaussian tốt cho sự thay đổi tỉ lệ nhưng không tốt cho góc quay, điển hình như quay 1 góc = pi/4 * "1 số lẻ" thì hình biểu diễn theo pixel sẽ gây nhiều lỗi

Dù vậy detector vẫn hoạt động tốt với lợi ích về tính nhanh covolution layer

Vậy, tóm lại ta đã dùng 1 convolution với 2 bước (gọi là second-order Gaussian derivatives):

- Gaussian kernel

- Đạo hàm bậc 2 (Hessian matrix)

Ta gọi kết quẩ này là D (determination)

Từ đó:

Scale-space representation

Tại SIFT, ta sử dụng image pyramid với mỗi tầng đều dùng filter giống nhau, vì vậy, kích thước thường giảm dần theo cấp số nhân (256x256 -> 128x128 -> 64x64 -> 32x32 ...). Ở SURF, từng tầng này lại dùng các filter không giống nhau, lại khiến kích thước tăng dần (9x9 -> 15x15 -> 21x21 -> 27x27) theo công thức:

Có khả năng output là các điểm gần như trùng nhau, cho nên để tránh việc này, ta có thể dùng thêm Non-maximal Suppression(NMS) 3x3x3

Feature Description
Cũng như SIFT, ý tưởng vẫn là xây dựng 1 vector đặc thù dựa vào độ lớn của các vector chỉ hướng. Ở SURF, ta có 2 bước:

- Tìm hướng chính dựa vào các vùng của 1 hinh tròn bao quanh điểm cần xét (ở SIFT là lưới vuông)

- Xây dựng hình vuông căn chỉnh theo vector hướng đã chọn (cững giống SIFT, đây chính là Descriptor)

Orientation Assignment

Mục đích là tìm rotate invariant (bất biến quay)

- Đầu tiên, ta biến trục tọa độ Oxy thành Haar-Wavelet với hình dạng hình tròn có tâm là keypoint, bán kính 6s với s là độ scale mà điểm keypoint được tìm thấy (đây là tâm tọa độ và khu vực ta dựa vào)
- Ta ban đầu tạo 1 vector (initiation). Ta tính tổng trục tung và trục hoành của các điểm keypoint nằm trong vùng hình tròn có khoảng cách không lớn hơn π/3 với vector ban đầu để tạo thành 1 vector đặc trưng cho các điểm này. Tiếp tục làm như vậy, sau đó ta tìm được vector đặc trưng có độ dài lớn nhất làm main orientation (vector chính) của feature description
Descriptor Component

- Đầu tiên ta tạo một hình vuông theo hướng của main orientation có độ lớn là 20s

- Sau đó ta chia hình vuông này thành 4x4 vùng nhỏ (như grid cell) mỗi vùng là 5x5 kích thước scale. Ta gọi dx, dy là 2 vector gốc của trục tọa độ mới có tâm là keypoint (theo Haar wavelet), vậy mỗi vector gốc có kích cỡ 2s. Để tăng độ hiệu quả (robust) về localization error , ta thêm một lớp Gaussian với weight riêng của dx, dy là σ = 3.3s