Computer Vision

[Keypoint Detector] Local Features. FAST, BRISK and ORB.

LOCAL FEATURES

Trong các bài viết về Image Descriptor, chúng ta đã tìm hiểu về Hu Moment, Haralick Texture, LBP hay HOG. Tất cả những Image Descriptor này đều là Global Image Descriptors, vì chúng trích xuất vector đặc trưng của toàn bộ bức ảnh. Đặt vào trường hợp chúng ta có bức ảnh như hình 1.

bienbao
Hình 1

Đối tượng chúng ta cần quan tâm trong hình 1 là cái biển báo giao thông, những đối tượng còn lại như các tòa nhà, xe cộ, cây cối, đường xá,… không có ý nghĩa trong việc xác định vị trí của cái biển báo. Nếu áp dụng Global Image Descriptors, chúng ta sẽ nhận được một Feature Vector mô tả toàn bộ bức ảnh (gồm cái biển báo giao thông và tất cả mọi thứ khác). Vì Feature Vector có chứa các thành phần thừa nên nó không thể mô tả chính xác đặc điểm của cái biển báo giao thông được.

Trong tình huống này chúng ta sẽ phải áp dụng Local Feature Descriptors nhằm mô tả một vùng hình ảnh nhỏ chứa đối tượng cần quan tâm thay vì toàn bộ bức ảnh. Những vùng hình ảnh này phải dễ dàng nhận biết so với phần còn lại và chứa đựng ý nghĩa liên quan đến nội dung của bức ảnh. Local Feature ở đây chính là vùng hình ảnh chứa cái biển báo giao thông, chúng ta có thể mô tả nó như sau: hình tròn, viền đỏ, nền trắng [hình 2].

bienbao
Hình 2 – Vùng hình ảnh chứa biển báo giao thông được đánh dấu

Với Local Feature Descriptor, chúng ta sẽ nhận được nhiều Local Feature Vector thay vì chỉ một Feature Vector như các Image Descriptors.

Quá trình xác định và mô tả các vùng hình ảnh được chia thành Keypoint DetectionFeature Extraction. Trong đó:

  1. Keypoint Detection: xác định vị trí của vùng hình ảnh chứa keypoint;
  2. Feature Extraction: mô tả đặc trưng của vùng hình ảnh chứa keypoint mà chúng ta đã xác định được.

Trong phần tiếp theo chúng ta sẽ tìm hiểu về FAST Keypoint Detector.


FAST KEYPOINT DETECTOR

Đây là bộ Keypoint Detector đơn giản, trực quan và nhanh nhất. FAST được sử dụng để xác định các corners (góc) của trong bức ảnh.

Giả thuyết của FAST detector là, để một pixel P được coi là “corner” thì cần có ít nhất n pixel liền kề cùng thuộc một đường tròn tâm P bán kính R có cường độ lớn hơn hoặc nhỏ hơn center pixel P một giá trị T.

fast_raw_example-865x412
Hình 3 – Giả thuyết của FAST detector

Trong hình 3 chúng ta có center pixel P và đường tròn bán kính R=3 gồm 16 pixels.

Trên thực tế, chúng ta thường chọn R=3, tương ứng với đường tròn chứa 16 pixel và n=9 hoặc n=12. Hãy xem một ví dụ ở hình 4.

fast_example_pass-865x865
Hình 4 – Ví dụ về FAST descriptor

Chúng ta có pixel trung tâm P=32, đường tròn tâm P bán kính R=3 gồm 16 pixel. Để pixel P được coi là “corner” cần ít nhất n=12 pixels có cường độ lớn hơn (hoặc nhỏ hơn) P một giá trị threshold T=16. Trong số 16 pixels này có đến 14 pixels có cường độ lớn hơn P (màu xanh lá), như vậy có thể kết luận rằng P là một “corner”.


BRISK KEYPOINT DETECTOR

Binary Robust Invariant Scalable Keypoint (BRISK) Detector là một bản nâng cấp của FAST, cho phép detector hoạt động tốt khi space scale thay đổi (space scale invariance). Thay vì chỉ làm việc trên một bức ảnh duy nhất như FAST, BRISK sẽ resize bức ảnh input thành nhiều bức nhỏ hơn, xem hình 5.

brisk_pyramid_example
Hình 6 – Kim tự tháp chứa các bức ảnh đã được resize

Với mỗi bức ảnh trong kim tự tháp trên, chúng ta sẽ áp dụng thuật toán của FAST detector để tìm ra “corner”. Vì không yêu cầu tài nguyên tính toán lớn nên BRISK rất phù hợp cho các ứng dụng real-time.


ORB KEYPOINT DETECTOR

ORB Detector là một bản nâng cấp của BRISK, cho phép nó hoạt động tốt ngay cả khi keypoint bị xoay (rotation invariance).

Sau khi đã tìm ra tất cả “corner” trong tất cả các bức ảnh trong kim tự tháp, ORB sẽ chọn ra tối đa 500 “corner” tốt nhất. Vùng pixel xung quanh từng “corner” này 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}})

Keypoint dù có xoay một góc \theta = arctan2(M_{01},M_{10}) cũng sẽ được phát hiện.

Tương tự như FAST và BRISK, ORB detector rất phù hợp cho các ứng dụng real-time.


ÁP DỤNG FAST KEYPOINT DETECTOR

Để áp dụng FAST, BRISK và ORB Detector, OpenCV 3 cung cấp các function sau:

+ Tạo một instance FAST detector:

detector = cv2.FastFeatureDetector_create([, threshold[, nonmaxSuppression]])

Trong đó:

  • threshold – giá trị threshold để so sánh cường độ giữa center pixel và các pixel trên đường tròn bao quanh nó, mặc định là 10;
  • nonmaxSuppression – cài đặt nonmax suppression, mặc định là True;

+ Tạo một instance BRISK detector:

detectorcv2.BRISK_create([, threshold[, octaves]])

Trong đó:

  • threshold – giá trị threshold để so sánh cường độ giữa center pixel và các pixel trên đường tròn bao quanh nó, mặc định là 30;
  • octave – số lượng rescale, 0 = single scale, mặc định là 3.

+ Tạo một instance ORB detector:

detectorcv2.ORB_create()

+ Xác định các Keypoints có trong bức ảnh grayscale:

keypoints= detector.detect(image, [mask=None])

Trong đó:

  • image – ảnh grayscale cần xác định keypoints;
  • mask – chọn mask cho vùng hình ảnh trong image, mặc định là None.
  • keypoints – một List chứa tất cả các keypoint có trong image.

Example: Áp dụng FAST detector để tìm các “corners” có trong bức ảnh.

Input image: bookcover.jpg

Bia_Chinh xac

Source code: FAST.py

import numpy as np
import cv2
import argparse

ap = argparse.ArgumentParser()
ap.add_argument('-i','--image')
args = vars(ap.parse_args())

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

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

print("# of keypoints:{}".format(len(kps)))

for kp in kps:
    r = int(0.5*kp.size)
    x,y = np.int0(kp.pt)
    cv2.circle(image,(x,y),r,(0,255,0),1)

cv2.imshow("Result", np.hstack([orig,image]))
cv2.waitKey(0)

Giải thích:
– Dòng 13,14: tạo instance của FAST detector và xác định các keypoints có trong image;
– Dòng 19,20: các keypoint có các thuộc tính như size (đường kính của đường tròn chứa các pixel lân cận) và pt (tọa độ của keypoint).

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

Output:
# of keypoints: 1781

result


SUMMARY

Qua bài viết này chúng ta đã có cái nhìn cơ bản về sự khác biệt giữa Local Feature Descriptor và Global Image Descriptor, cũng như cách áp dụng FAST, BRISK và ORB detector để xác định các “corners” có trong bức ảnh. Cảm ơn các bạn đã theo dõi bài viết.

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

Reference:
[1] FAST Algorithm for Corner Detection.
[2] cv::FastFeatureDetector Class Reference.

One thought on “[Keypoint Detector] Local Features. FAST, BRISK and ORB.

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