Giới thiệu về Scale-Invariant Feature Transform

Scale-Invariant Feature Transform (SIFT) là giải thuật trong lĩnh vực Computer Vision, dùng để nhận dạng và miêu tả những điểm đặc trưng(local features) trong ảnh. Giải thuật lần đầu được giới thiệu bởi David Lowe năm 1999. Giải thuật này(cùng với giải thuật anh em là SURF) được ứng dụng rộng rãi trong Nhận dạng đối tượng(object recognition), mô hình hóa 3D(3D modeling),...

Điểm đặc biệt của SIFT nằm ngay trong cái tên của nó Scale-Invariant, tức là nó sẽ đưa ra các kết quả ổn định với những scale của ảnh khác nhau, bên cạnh đó cũng có thể nói giải thuật này có tính rotation-invariant.

Trong bài báo khoa học "Distinctive Image Features from Scale-Invariant Keypoints", SIFT được đặc tả rõ nét dưới bốn giai đoạn(stages) chính sau:

• Scale-space extrema detection.

• Keypoint localization.

• Orientation assignment.

• Keypoint descriptor.

Sau đây, tôi sẽ trình bày tư tưởng chung của từng giai đoạn:

1. Scale-space extrema detection

Chúng ta cùng xem xét ví dụ dưới đây:

Note: Trong computer vision, chúng ta thường định nghĩa kích cỡ các cửa sổ(window) rồi quét ảnh với các cửa sổ đó để tìm những đặc tính(feature) của ảnh.

Phía bên trái chúng ta có 1 góc(corner) với kích thước nhỏ, và cửa sổ(window) có kích thước hợp lý để nhận ra các keypoint, nhưng với cùng kích cỡ cửa sổ và một góc có kích thước lớn thì sẽ trở nên bất hợp lý. Do đó, scale-space filtering được sử dụng để giải quyết vấn đề này. SIFT tính DoG (Difference of Gaussians) trên từng pixel bằng cách lấy diff của Gaussian Blur với 2 sigma khác nhau. Sau khi tính được DoG của toàn ảnh, xét trên từng pixel so sánh với 8 neighbors và 9 pixels tương ứng của scale ảnh ngay trên và 9 pixels tương ứng ở scale dưới, nếu pixel đó là local extrema (lớn nhất) thì nó sẽ được coi như là 1 keypoint ở scale đó. (potiental keypoint).

2. Keypoint localization

Khi đã lấy được tất cả những potential keypoints của ảnh, việc cần làm tiếp theo là lọc để ra những kết quả chính xác hơn, SIFT sử dụng chuỗi Taylor mở rộng để lấy vị trí của extrema chính xác hơn, rồi sau đó xét xem nếu intensity của extrema đó nhỏ hơn giá trị ngưỡng (0.03) thì sẽ loại keypoint đó.

Bên cạnh đó, DoG rất nhạy cảm với edge(đường), để loại bỏ edge keypoint, SIFT dùng concept giống Haris corner detector, nó dùng ma trận Hessian 2x2 để tính ra những đường cong chính. Khi eigen value lớn hơn threshold nào đó thì keypoint đó sẽ bị loại.

Như trên, SIFT có thể loại được keypoints có tương phản thấp, edge keypoint và giữ lại những keypoint hợp lý hơn.

3. Orientation assignment

Một hoặc nhiều orientation (hướng) sẽ được gắn cho từng vị trí keypoint dựa trên image gradient. Các phép tính sau đó trên ảnh sẽ tương ứng với từng orientation, scale và vị trí từng feature.

4. Keypoint descriptor

SIFT sẽ tính Keypoint descriptor bằng cách lấy 16x16 neighborhood(điểm liền kề) của keypoint đó, rồi chia thành 16 sub-blocks với kích thước 4x4. Với mỗi sub-block, ta sẽ tạo được 8 bin oritation (như hình dưới). Do đó tất cả sẽ có 128 bin giá trị tương ứng với 1 vector biểu hiện cho keypoint descriptor.

SIFT trong OpenCV

Trong OpenCV có hỗ trợ của SIFT và SURF (một giải thuật có mục đích giống SIFT, hiệu năng tốt hơn),

SIFT::operator()(InputArray img, InputArray mask, vector<KeyPoint>& keypoints, OutputArray descriptors, bool useProvidedKeypoints=false)

Parameters:

img – Input 8-bit grayscale image

mask – Optional input mask that marks the regions where we should detect features.

keypoints – The input/output vector of keypoints

descriptors – The output matrix of descriptors. Pass cv::noArray() if you do not need them.

useProvidedKeypoints – Boolean flag. If it is true, the keypoint detector is not run. Instead, the provided vector of keypoints is used and the algorithm just computes their descriptors.

References

1. http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_feature2d/py_sift_intro/py_sift_intro.html
2. Distinctive Image Features from Scale-Invariant Keypoints

** Trong bài report lần tới, tôi sẽ tạo ứng dụng thực tế sử dụng SIFT/SURF giới thiệu đến mọi người. **