Computer Vision

[Binary Descriptor] BRIEF

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về khái niệm Binary Descriptor và bộ descriptor BRIEF.


BINARY DESCRIPTOR LÀ GÌ?

Các Local Feature Descriptors như SIFT, RootSIFT và SURF mà chúng ta đã tìm hiểu đều rất mạnh mẽ và hiệu quả trong các ứng dụng như Image Classification, Content-Based Image Retrival, v.v.. Tuy nhiên, bởi vì các descriptor này hoạt động dựa trên việc biểu diễn Gradient Magnitude của bức ảnh (yêu cầu thời gian tính toán cao) nên chúng không phù hợp các cho ứng dụng real-time. Để giải quyết vấn đề này chúng ta sử dụng Binary Descriptor.

Với Binary Descriptor, các Local Feature Vectors (còn gọi là Binary Feature Vectors) sẽ được biểu diễn bởi các chuỗi bit 0 và 1, nhờ đó mà thời gian tính toán rất thấp và yêu cầu bộ nhớ được giảm xuống.

Vì sự đơn giản nên Binary Descriptor không có sự chính xác cao như các Real-valued Descriptor (SIFT, SURF), nhưng bù lại nó phù hợp cho các ứng dụng real-time và bị hạn chế về phần cứng. Việc lựa chọn descriptor sẽ tùy thuộc vào từng ứng dụng cụ thể.

Để trích xuất được Binary Feature Vector từ một Image Patch, chúng ta cần thực hiện các bước sau:

  1. Sampling pattern (Lấy mẫu): chọn ra các pixel trong khu vực xung quanh keypoint, mỗi Binary Descriptor có một phương pháp để chọn ra các pixel này;
  2. Sampling pairs (Ghép cặp): các pixel chọn được từ bước #1 sẽ được ghép thành N cặp để so sánh với nhau;
  3. Orientation compensation: bước này nhằm đảm bảo rằng Binary Feature Vector không bị phụ thuộc vào góc quay của đối tượng trong Image Patch (rotation invariance);
  4. Binary feature vector construction (Xây dựng vector đặc trưng): với N cặp pixel có được ở bước #2, chúng ta lần lượt so sánh cường độ của hai pixel v_1, v_2 trong từng cặp (hình 1), từ đó xây dựng vector đặc trưng N-dims (hình 2).

 

binary_descriptors_bit_test
Hình 1 – So sánh cường độ của 2 pixel
binary_descriptors_extraction
Hình 2 – Xây dựng Feature Vector

Việc so sánh giữa hai Binary Feature Vector cũng rất đơn giản, chúng ta sẽ sử dụng Hamming Distance để tính toán sự khác biệt giữa hai vector (hình 3).

binary_descriptors_hamming-865x281
Hình 3 – So sánh hai vector với Hamming Distance

Chúng ta vừa tìm hiểu cách xây dựng một Binary Feature Vector, phần tiếp theo của bài viết sẽ giới thiệu về bộ descriptor BRIEF.


BRIEF BINARY DESCRIPTOR

BRIEF (Binary Robust Independent Elementary Features) là Binary Descriptor đầu tiên được giới thiệu và được sử dụng rất rộng rãi.

BRIEF descriptor thực hiện sampling pattern một cách ngẫu nhiên với Gaussian distribution, nghĩa là các pixel càng gần keypoint sẽ có xác suất được lựa chọn cao hơn các pixel ở xa. Từ các pixel này chúng ta chọn ra N cặp để so sánh (hình 4) và xây dựng Feature Vector (hình 5).

Capture
Hình 4 – Sampling pattern
binary_descriptors_feature_vector
Hình 5 – Binary Feature Vector

Trong OpenCV, Feature Vector của BRIEF mặc định là 256-dims, được lưu trữ ở 32 bytes.


ÁP DỤNG BRIEF DESCRIPTOR

OpenCV 3 đã cung cấp function hỗ trợ việc sử dụng BRIEF Descriptor

Function:

+ Tạo BRIEF Descriptor instance:

extractorcv2.xfeatures2d.BriefDescriptorExtractor_create([, bytes=32])

Trong đó:

  • bytes – kích thước của Binary Feature Vector ở byte, mặc định là 32;

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

keypoints, descs = 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;
  • descs – 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:

Input: bookcover.jpg

querybook

Source code: BRIEF.py

import argparse
import cv2

ap = argparse.ArgumentParser()
ap.add_argument("-i", "--image", required=True)
args = vars(ap.parse_args())

image = cv2.imread(args["image"])
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

detector = cv2.FastFeatureDetector_create()
extractor = cv2.xfeatures2d.BriefDescriptorExtractor_create()

kps = detector.detect(gray)
(kps, descs) = extractor.compute(gray, kps)

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

Execution:
$ python BRIEF.py -i bookcover.jpg

Output:
[INFO] # of keypoints detected: 1524
[INFO] feature vector shape: (1524, 32)


SUMMARY

Qua bài viết này chúng ta đã tìm hiểu về khái niệm Binary Descriptor, nhận biết ưu và nhược điểm của Binary Descriptor với Real-valued Descriptor cũng như làm quen với bộ Descriptor BRIEF. Cảm ơn các bạn đã theo dõi bài viết.

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

Reference:
[1] BRIEF: Binary Robust Independent Elementary Features
[2] cv::xfeatures2d::BriefDescriptorExtractor Class Reference

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