Computer Vision

[Keypoint Detector] Harris và GFTT

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về Harris Keypoint Detector và Good Features To Track, hai detector được sử dụng phổ biển để xác định các “corner” có trong bức ảnh với tốc độ tính toán cao và chính xác.


TÌM HIỂU VỀ HARRIS KEYPOINT DETECTOR

Giả sử chúng ta có một vùng pixel 2×2 như hình 1:

harris_2x2_corner_nodetection

Hình 1 – Một vùng pixel 2×2

Chúng ta thấy rằng các pixel top-left và bottom-right có cường độ thấp hơn các pixel top-right và bottom-left, do đó phần trung tâm của vùng pixel này sẽ được coi là một “corner” (vùng được khoanh đỏ ở hình 2).

harris_2x2_corner

Hình 2 – Một “corner” được đánh dấu

Vậy làm thế nào chúng ta xác định được “corner” đó? Câu trả lời là Harris Corner Detection Algorithm.

  • Bước 1: tính Gradient của vùng pixel G_{x}, G_{y};
  • Bước 2: tính các tổng bình phương của Gradient: \sum G_{x}^{2}, \sum G_{y}^{2}, \sum G_{x}G_{y};
  • Bước 3: xây dựng ma trận M=\begin{bmatrix}\sum G_{x}^{2} & \sum G_{x}G_{y} \\ \sum G_{x}G_{y} & \sum G_{y}^{2} \end{bmatrix} và tính giá trị R = det M - k(trace M)^2.

Trong đó: det M = \lambda_1\lambda_2 là định thức của ma trận M; trace M = \lambda_1+\lambda_2 là vết của ma trận M với \lambda_1, \lambda_2 là trị riêng của ma trận M; k là “Harris detector free parameter”, thường có giá trị 0,04-0,06.

Khi đã có được giá trị R, chúng ta sẽ xác định xem vùng pixel này có phải “corner” không:

  • Nếu giá trị |R| nhỏ thì vùng pixel đó không chứa thông tin có giá trị, còn gọi là “flat” region;
  • Nếu R < 0, tức là khi \lambda_1 >> \lambda_2 hoặc \lambda_2 >> \lambda_1, thì vùng pixel đó chỉ chứa “edge”;
  • Nếu giá trị R lớn, tức là khi \lambda_1 >> 1, \lambda_2 >> 1\lambda_1 \simeq \lambda_2, thì vùng pixel này chứa “corner”, xem hình 3.

harris_eigenvalues

Hình 3 – Xác định “corner” dựa vào \lambda


ÁP DỤNG HARRIS KEYPOINT DETECTOR

OpenCV đã cung cấp các function cần thiết để thực hiện Harris Corner Detection Algorithm.

Function:

+ Tính toán Harris Detector Response:

R = cv2.cornerHarris(inputImage, blockSize, apetureSize, k)

Trong đó:

  • R – ma trận có kích thước tương ứng input image, chứa tất cả các giá trị R tính toán được từ giải thuật Harris;
  • inputImage – ảnh input ở grayscale;
  • blockSize – kích thước của từng vùng pixel, thường là 2;
  • apetureSize – kích thước của Sobel kernel, thường là 3;
  • k – Harris detector free parameter, thường là 0,04-0,06.

+ Tạo KeyPoint:

kpObj = cv2.KeyPoint(x, y, size)

Trong đó:

  • x, y – tọa độ của keypoint;
  • size – đường kính của keypoint;
  • kpObj– đối tượng chứa thông tin của keypoint, có các thuộc tính sau: kpObj.pt, kpObj.size.

Example 1: Xác định “corner” với Harris Detector.

Input: chessboard.jpg

chessboard

Hình 4 – input image

Source code: harris.py

import numpy as np
import cv2

def harris(gray, blockSize=2, apetureSize=3, k=0.05, T=0.02):
    gray = np.float32(gray)
    H = cv2.cornerHarris(gray, blockSize, apetureSize, k)

    kps = np.argwhere(H > T*H.max())
    kps = [cv2.KeyPoint(pt[1], pt[0], 3) for pt in kps]

    return kps

image = cv2.imread("chessboard.jpg")
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
kps = harris(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), 2)

cv2.imshow("Image",image)
cv2.waitKey(0)

Giải thích:
– Dòng 6: tính toán các giá trị Harris Response cho bức ảnh input;
– Dòng 8,9: tìm ra các giá trị thỏa mãn yêu cầu R > T*Rmax từ ma trận H. Vị trí của các giá trị đó trong ma trận H chính là tọa độ của các keypoint trong input image.

Output:
Capture


TÌM HIỂU VỀ GFTT DETECTOR

Good Feature To Track (GFTT) là một bản “mod” của Harris Detector. Trong Harris algorithm chúng ta tính toán giá trị R = det M - k(trace M)^2 = \lambda_1\lambda_2 - k(\lambda_1+\lambda_2)^2 để đánh giá xem vùng pixel đó có chứa “corner” hay không. Tuy nhiên, tác giả của GFTT cho rằng có cách tốt hơn để đánh giá một vùng pixel và đã đề xuất tính giá trị R = min(\lambda_1,\lambda_2). Nếu R lớn hơn một giá trị threshold T thì có thể coi vùng pixel này chứa “corner”.

gftt_regions

  • Ở Region #1, #2 và #3: \lambda_1 < \lambda_{min} và/hoặc \lambda_2 < \lambda_{min} nên các vùng này không thể chứa “corner”;
  • Ở Region #4: \lambda_1 > \lambda_{min}\lambda_2 > \lambda_{min} nên vùng này chứa “corner”.

Sự thay đổi nhỏ từ Harris Detector này giúp cho GFTT hoạt động ổn định và nhanh hơn.


ÁP DỤNG GFTT DETECTOR

OpenCV 3 cung cấp function cv2.goodFeaturesToTrack() để áp dụng GFTT algorithm.

Function:

+ Tìm ra tọa độ của các “corners” có trong bức ảnh:

kps = cv2.goodFeaturesToTrack(inputImage, maxCorners, qualityLevel, minDistance[, corners[, mask[, blockSize[, useHarrisDetector[, k]]]]]

Trong đó:

  • kps – một ndarray chứa tọa độ của tất cả n “corner” được phát hiện, có kích thước shape=[n,1,2];
  • inputImage – bức ảnh input ở grayscale;
  • maxCorners – số lượng maximum “corner” được lưu vào kps; maxCorners = 0: không giới hạn số lượng “corner”;
  • qualityLevel – đặc trưng cho chất lượng của “corner”. Chỉ những “corners” có giá trị R > qualityLevel*Rmax mới được chấp nhận;
  • minDistance – khoảng cách Euclidean nhỏ nhất được cho phép giữa hai “corners”;
  • mask – mask cho bức ảnh input;
  • blockSize – kích thước của từng vùng pixel;
  • useHarrisDetector – True: sử dụng function cornerHarris; False: sử dụng function cornerMinEigenVal;
  • k – tham số tự do của Harris Detector.

Example 2: Xác định “corner” với GFTT

Input: chessboard.jpg ở example 1.

Source code: GFTT.py

import numpy as np
import cv2

def gftt(gray, maxCorners=0, qualityLevel=0.01, minDistance=1,
        mask=None, blockSize=3, useHarrisDetector=False, k=0.04):
    kps = cv2.goodFeaturesToTrack(gray, maxCorners, qualityLevel, minDistance, mask=mask, blockSize=blockSize,
    useHarrisDetector=useHarrisDetector,k=k)

    return [cv2.KeyPoint(pt[0,0], pt[0,1], 3) for pt in kps]

image = cv2.imread("chessboard.jpg")
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
kps = gftt(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), 2)

cv2.imshow("Image",image)
cv2.waitKey(0)

Output:
gftt


SUMMARY

Như vậy chúng ta đã tìm hiểu về Harris Keypoint Detector và GFTT Detector. Cảm ơn các bạn đã theo dõi bài viết.

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

Reference:
[1] OpenCV: Feature Detection – cornerHarris.
[2] OpenCV: KeyPoint class.
[3] Harris Corner Detector.

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