Computer Vision

[Binary Descriptor] BRISK, ORB và FREAK

Xin chào, trong các bài viết trước chúng ta đã tìm hiểu về ORB Keypoint Detector và BRISK Keypoint Detector, nhưng không chỉ có thế, ORB và BRISK còn có thể đóng vai trò là các Binary Descriptor. Trong bài viết này chúng ta sẽ tìm hiểu về 3 bộ Binary Descriptor là ORB, BRISK và FREAK.


BRISK BINARY DESCRIPTOR

BRISK descriptor thực hiện sampling pattern một cách thủ công với mẫu hình sau:

brisk_sampling_pattern
Hình 1 – BRISK sampling pattern

Tại khu vực xung quanh keypoint, N đường tròn đồng tâm sẽ được xây dựng, trong đó, các đường tròn màu xanh biểu diễn các pixel được lựa chọn, các đường tròn màu đỏ với kích thước nhỏ dần về trung tâm biểu diễn độ lớn của giá trị Standard Deviation \sigma của Gaussian kernel để giảm nhiễu tại vị trí pixel đó. Từ N pixels được chọn, chúng ta sẽ nhận được N.(N-1)/2 cặp pixel.

BRISK descriptor chia các cặp pixels thành long-distance pairsshort-distance pairs, trong đó long-distance pairs được sử dụng để xác định sự định hướng của keypoint, còn short-distance pairs được sử dụng để so sánh cường độ giữa các pixel, từ đó xây dựng Local Feature Vectors, hình 2.

Bằng cách tính tổng Gradient Magnitude G_x, G_y của tất cả long-distance pairs chúng ta có thể tính góc định hướng \theta=arctan(G_y/G_x) của image patch.

binary_descriptors_bit_test
Hình 2 – So sánh cường độ hai pixels

Theo tiêu chuẩn, Local Feature Vector của BRISK descriptor có kích thước 512-dims, được lưu trong 64 bytes.


ORB BINARY DESCRIPTOR

ORB descriptor thực hiện sampling pattern với một thuật toán Machine Learning, chúng ta sẽ không đi sâu tìm hiểu về thuật toán này.

Vùng pixel xung quanh từng keypoint sẽ được khảo sát để tìm ra “Trọng tâm của cường độ” (intensity centroid).

Moments: M_{p,q}=\sum_{x,y}x^py^qI(x,y)

Center of mass: C=(\frac{M_{10}}{M_{00}},\frac{M_{01}}{M_{00}})

Orientation angle: \theta=arctan2(M_{01},M_{10})

Với orientation angle, chúng ta có thể xoay các image patch về một góc đồng nhất, nhờ đó mà các image patch có góc quay khác nhau vẫn được xử lý tương tự nhau.

Local Feature Vector của ORB descriptor có kích thước 256-dims, được lưu trong 32 bytes.


FREAK BINARY DESCRIPTOR

FREAK descriptor rất đặc biệt vì nó mô phỏng cấu trúc tế bào của võng mạc để thực hiện sampling pattern, hình 3.

freak_receptive-fields
Hình 3 – Mật độ tế bào của võng mạc

Theo đó, các tế bào trên võng mạc được phân bố dày đặc hơn về phía trung tâm. FREAK descriptor thực hiện sampling pattern với mẫu hình sau:

freak_sampling_pattern
Hình 4 – FREAK sampling pattern

Chúng ta có thể thấy rằng tại khu vực xung quanh keypoint, các đường tròn chồng lấn nhau được xây dựng và tập trung dày đặc hơn về phía trung tâm với kích thước nhỏ dần. Bán kính của các đường tròn này chính là giá trị Standard Deviation \sigma của Gaussian kernel để giảm nhiễu tại vị trí pixel đó.

FREAK áp dụng một thuật toán Machine Learning (tương tự như ORB descriptor) để thực hiện sampling pairs và thu được 512 cặp pixels, hình 5.

freak_sampling_pairs
Hình 5 – FREAK sampling pairs

Để xác định góc định hướng của image patch, FREAK descriptor tính toán Gradient Magnitude G_x, G_y\theta=arctan(G_y/G_x) dựa trên 45 cặp pixel đối xứng, hình 6.

freak_orientation_pairs
Hình 6 – 45 cặp pixels được sử dụng để tính góc định hướng

Sau cùng, cường độ của các pixel được so sánh và xây dựng thành Local Feature Vector, hình 2.

Local Feature Vector của FREAK descriptor có kích thước 512-dims, được lưu trong 64 bytes.


IMPLEMENTATION

OpenCV 3 đã cung cấp các function dành cho ORB, BRISK và FREAK.

Functions:

+ Tạo instance BRISK descriptor:

extractor = cv2.BRISK_create()

+ Tạo instance ORB descriptor:

extractor = cv2.ORB_create()

+ Tạo instance FREAK descriptor:

extractor = cv2.xfeatures2d.FREAK_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 keypoints đã phát hiện được trong bức ảnh;
  • 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.

SUMMARY

Trong 3 bộ descriptor đã tìm hiểu ở trên thì FREAK cho kết quả tốt nhất, tiếp theo là BRISK và ORB. Trên thực tế, chúng ta sẽ cần thử nghiệm trên từng descriptor để chọn ra descriptor phù hợp nhất bộ dữ liệu đang có.

Cảm ơn các bạn đã theo dõi bài viết.

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

Reference:
[1] BRISK: Binary Robust Invariant Scalable Keypoints
[2] ORB: an efficient alternative to SIFT or SURF
[3] FREAK: Fast Retina Keypoint

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