Computer Vision

[Local Feature Descriptor] SIFT và RootSIFT

Sau khi xác định được các keypoint có trong bức ảnh, chúng ta cần trích xuất đặc trưng của vùng ảnh xung quanh các keypoint đó, quá trình này được gọi là Local Feature Extraction. Trong bài viết này chúng ta sẽ tìm hiểu về Scale Invariant Feature Transform (SIFT), một Local Feature Descriptor được sử dụng phổ biến nhất.


TÌM HIỂU VỀ SIFT DESCRIPTOR

SIFT Descriptor nhận các keypoint có trong bức ảnh là input. Đối với mỗi keypoint, vùng ảnh 16×16 pixel xung quanh nó sẽ được chọn để trích xuất đặc trưng. Vùng ảnh này lại được chia thành 16 vùng 4×4 pixel, xem hình 1.

4x4
Hình 1 – 16 vùng 4×4 pixel

Với từng ô trong 16 vùng này, chúng ta sẽ tính toán Histogram of Oriented Gradients, với 8 bins trên mỗi Histogram. Ghép tất cả 16 Histogram lại với nhau, như vậy Feature Vector sẽ là 16×8=128-d. Cuối cùng chúng ta thực hiện L2-normalizing cho Feature Vector vừa nhận được. Nếu bức ảnh có N keypoint thì chúng ta sẽ nhận được N Feature Vector.


ÁP DỤNG SIFT DESCRIPTOR

Các function để áp dụng SIFT Descriptor được cung cấp bởi OpenCV 3.

Function:

+ Tạo instance của SIFT Descriptor:

extractor = cv2.xfeatures2d.SIFT_create()

+ Trích xuất đặc trưng của các keypoints:

keypoints, descriptors = extractor.compute(image, keypoints)

Trong đó:

  • image – bức ảnh input ở grayscale;
  • keypoints – một List chứa các keypoint đã phát hiện được trong image;
  • descriptors – một ndarray có kích thước M x N chứa các vector đặc trưng trích xuất được từ các Image Patch, trong đó: M là số lượng keypoint, N là kích thước của vector đặc trưng.

Example:

Source code: SIFT.py

import numpy as np
import cv2

image = cv2.imread("chessboard.jpg")
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

detector = cv2.FastFeatureDetector_create()
kps = detector.detect(gray)

extractor = cv2.xfeatures2d.SIFT_create()
kps, descs = extractor.compute(gray, kps)

print("[INFO] # of keypoints: {}".format(len(kps)))
print("[INFO] Feature Vector shape: {}".format(descs.shape))

Input: chessboard.jpg
chessboard

Output:
[INFO] # of keypoints: 308
[INFO] Feature Vector shape: (308, 128)


TÌM HIỂU ROOTSIFT DESCRIPTOR

RootSIFT là một phiên bản mở rộng của SIFT giúp tăng độ chính xác khi giải quyết các vấn đề cần áp dụng SIFT descriptor (chẳng hạn như Object Recognition) vì RootSIFT cho phép các Feature Vector được so sánh bằng Hellinger distance. Chính vì hiệu quả hơn nên RootSIFT được ưu tiên hơn SIFT.

Mình sẽ giới thiệu qua về Hellinger distance. Trong xác xuất thống kê, khoảng cách Hellinger được dùng để biểu diễn sự khác biệt giữa hai phân bố xác suất.

Giả sử cho hai tập hợp P = {p_1,p_2,...,p_k}; Q = {q_1,q_2,...,q_k}. Khoảng cách Hellinger giữa hai tập hợp P và Q là:

H(P,Q) = \frac {1}{\sqrt{2}}\sqrt{\sum_{i=1}^{k}{(\sqrt{p_i}-\sqrt{q_i})^2}}

Vì khoảng cách Hellinger khá tương đồng với khoảng cách Euclidean d(P,Q) = \sqrt{\sum_{i=1}^{k}{(p_i-q_i)^2}} nên chúng ta chỉ cần tinh chỉnh một chút ở các Feature Vector của các keypoint và vẫn có thể sử dụng SIFT descriptor như bình thường.

Giải thuật của RootSIFT như sau:

  1. Trích xuất SIFT Feature Vectors cho tất cả keypoints, chẳng hạn như sử dụng function SIFT_create() của OpenCV;
  2. Thực hiện L1-normalizing cho từng SIFT Feature Vector;
  3. Tính căn bậc hai cho từng phần tử trong SIFT Feature Vector đó.

TRIỂN KHAI ROOTSIFT DESCRIPTOR

Source code: rootSIFT.py

import numpy as np
import cv2
import imutils

class RootSIFT:
	def __init__(self):
		self.extractor = cv2.xfeatures2d.SIFT_create()

	def compute(self, image, kps, eps=1e-7):
		kps, descs = self.extractor.compute(image, kps)

		if len(kps) == 0:
			return ([], None)

		descs /= (descs.sum(axis=1, keepdims=True) + eps)
		descs = np.sqrt(descs)

		return (kps, descs)

image = cv2.imread("chessboard.jpg")
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

detector = cv2.FastFeatureDetector_create()
kps = detector.detect(gray)

extractor = RootSIFT()
kps, descs = extractor.compute(gray, kps)

print("[INFO] # of keypoints detected: {}".format(len(kps)))
print("[INFO] Feature Vector shape: {}".format(descs.shape))

Giải thích:
– Dòng 7 và 10: khởi tạo và trích xuất Feature Vector cho các keypoint;
– Dòng 15: thực hiện L1-normalizing cho từng Feature Vector;
– Dòng 16: lấy căn bậc hai của từng giá trị trong từng Feature Vector.

Output:
[INFO] # of keypoints detected: 308
[INFO] Feature Vector shape: (308, 128)


SUMMARY

Qua bài viết này chúng ta đã tìm hiểu về SIFT descriptor và phiên bản mở rộng RootSIFT của nó. Vì hiệu quả cao nên RootSIFT được ưu tiên sử dụng hơn SIFT descriptor. Cảm ơn các bạn đã theo dõi bài viết.

Thân ái và quyết thắng.

Reference:
[1] Gentle Introduction to Vector Norms in Machine Learning.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s