Tiếp nối với series về keypoint detector, hôm nay mình sẽ giới thiệu về thuật toán Harris.

Harris keypoint detetor được Harris và Stephens giới thiệu vào năm 1988 trong bài báo A Combined Corner and Edge Detox. Đây là một trong những thuật toán xác định corners phổ biến nhất mà bạn sẽ gặp rất nhiều trong thế giới computer vision. Thuật toán này khá nhanh (không nhanh bằng FAST keypoint detector), nhưng độ chính xác khi xác định góc lại tốt hơn.

Harris keypoint detector hoạt động như thế nào?

Thuật toán Harris keypoint detector liên quan khá nhiều đến đại số tuyến tính. Tuy nhiên để hiểu được các hoạt động của thuật toán này, trước tiên bản hãy xem hình sau:

Hình bên trái là hình ảnh gốc, hình ở chính giữa  biểu thị cường độ gradient theo hướng dọc, và hình cuối cùng là biểu thị cường độ gradient theo hướng ngang. Mục tiêu của chúng ta là sử dụng các cường độ gradient này để phát hiện các góc trong hình ảnh.

Làm thế nào để làm được điều đó?

Để trả lời câu hỏi này, chúng ta cùng xem qua một ví dụ đơn gianr:

Ví dụ trên là một vùng điểm ảnh 2x2. Trên cùng bên trái và dưới cùng bên phải là màu đen, còn lại là màu trắng. Và điểm chính giữa là chính là corner

Để xác định được điểm chính giữa là corner, chúng ta sẽ lấy tổng các giá trị gradient theo chiều x và theo chiều y trong vùng đó

Nếu cả 2 giá trị này đều đủ lớn, thì chúng ta có thể định nghĩa vùng đó là một corner. Quá trhinhf này được thực hiện cho mọi pixel của hình ảnh. Phương phá này hoạt động vì vùng được bao quanh bên trong vòng tròn màu đỏ sẽ có số lượng lớn gradient theo chiều ngang và gradient theo chiều dọc, và khi điều đó xảy ra, đồng nghĩa với việc chúng ta đã tìm được một góc.

Để mở rộng phương thức này sang các góc tùy ý, trước tiên chúng ta cần tính toán biểu diễn cường độ gradient của hình ảnh, và sau đó sử dụng cường độ gradient này để xây dựng lên một ma trận M:

Sau khi ma trận M được định nghĩa, chúng ta sẽ đi tính eigenvalue decomposition của ma trận M, để lại cho chúng ta một điểm số biểu thị mức độ của các góc.

Theo tác giả của thuật toán, chúng ta có thể xem xét điều kiện sau để xác định vùng có keypoint hay không

      - Nếu |R| nhỏ thì đây là một khu vực phẳng, có nghĩa là không phải keypoint

      - Nếu R < 0 thì đây là một cạnh, và đây cũng không phải keypoint

      - Nếu |R| lớn thì đây chính là một keypoint

Để dễ xác định, chúng ta cùng xem qua một hình sau

Thuật toán Harris trong Python

Thuật toán harris đã được khai triển trong OpenCV, các bạn có thể xem code:

fast_keypoint_detector.py

# import the necessary packages
from __future__ import print_function
import numpy as np
import cv2
import imutils
 
# load the image and convert it to grayscale
image = cv2.imread("next.png")
orig = image.copy()
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
 
# handle if we are detecting FAST keypoints in the image for OpenCV 2.4
if imutils.is_cv2():
	detector = cv2.FeatureDetector_create("FAST")
	kps = detector.detect(gray)
else:
	detector = cv2.FastFeatureDetector_create()
	kps = detector.detect(gray, None)
 
print("# of keypoints: {}".format(len(kps)))
 
# loop over the keypoints and draw them
for kp in kps:
	r = int(0.5 * kp.size)
	(x, y) = np.int0(kp.pt)
	cv2.circle(image, (x, y), r, (0, 255, 255), 2)
 
cv2.imshow("Images", np.hstack([orig, image]))
cv2.waitKey(0)

# import the necessary packages
from __future__ import print_function
import numpy as np
import cv2
import imutils
 
def gftt(gray, maxCorners=0, qualityLevel=0.01, minDistance=1,
	mask=None, blockSize=3, useHarrisDetector=False, k=0.04):
	# compute GFTT keypoints using the supplied parameters (OpenCV 3 only)
	kps = cv2.goodFeaturesToTrack(gray, maxCorners, qualityLevel,
		minDistance, mask=mask, blockSize=blockSize,
		useHarrisDetector=useHarrisDetector, k=k)
 
	# create and return `KeyPoint` objects
	return [cv2.KeyPoint(pt[0][0], pt[0][1], 3) for pt in kps]
 
# load the image and convert it to grayscale
image = cv2.imread("next.png")
orig = image.copy()
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
 
# handle if we're detecting and drawing GFTT keypoints using OpenCV 2.4
if imutils.is_cv2():
	detector = cv2.FeatureDetector_create("GFTT")
	kps = detector.detect(gray)
 
# handle if we're detecting and drawing GFTT keypoints using OpenCV 3+
else:
	kps = gftt(gray)
 
# loop over the keypoints and draw them
for kp in kps:
	r = int(0.5 * kp.size)
	(x, y) = np.int0(kp.pt)
	cv2.circle(image, (x, y), r, (0, 255, 255), 2)
 
print("# of keypoints: {}".format(len(kps)))
 
# show the image
cv2.imshow("Images", np.hstack([orig, image]))
cv2.waitKey(0)

harrs_keypoint_detector.py

# import the necessary packages
from __future__ import print_function
import numpy as np
import cv2
import imutils
 
def harris(gray, blockSize=2, apetureSize=3, k=0.1, T=0.02):
	# convert our input image to a floating point data type and then
	# compute the Harris corner matrix
	gray = np.float32(gray)
	H = cv2.cornerHarris(gray, blockSize, apetureSize, k)
 
	# for every (x, y)-coordinate where the Harris value is above the
	# threshold, create a keypoint (the Harris detector returns
	# keypoint size a 3-pixel radius)
	kps = np.argwhere(H > T * H.max())
	kps = [cv2.KeyPoint(pt[1], pt[0], 3) for pt in kps]
 
	# return the Harris keypoints
	return kps
 
# load the image and convert it to grayscale
image = cv2.imread("next.png")
orig = image.copy()
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
 
# handle if we are detecting Harris keypoints in the image with OpenCV 2.4
if imutils.is_cv2():
	detector = cv2.FeatureDetector_create("HARRIS")
	kps = detector.detect(gray)
 
# otherwise we are detecting Harris keypoints with OpenCV 3+ using the function above
else:
	kps = harris(gray)
 
print("# of keypoints: {}".format(len(kps)))
 
# loop over the keypoints and draw them
for kp in kps:
	r = int(0.5 * kp.size)
	(x, y) = np.int0(kp.pt)
	cv2.circle(image, (x, y), r, (0, 255, 255), 2)
 
# show the image
cv2.imshow("Images", np.hstack([orig, image]))
cv2.waitKey(0)

Sau khi chạy với input đầu vào của mình, mình đã tìm được 881 góc tưởng ứng với 881 keypoint 

Kết luận

Trong bài viết này mình đã trình bày nguyên lý hoạt động của thuật toán harris, một thuật toán được dùng để xác định góc và cạnh. Vì tốc độ tương đối nhanh nên Harris được sử dụng rất rộng rãi trong lĩnh vực Computer Vision. 

Trong bài viết tiếp theo, mình sẽ giới thiệu với các bạn một thuật toán về Keypoint detector mới là GFTT (Good features to track)

Chúc bạn thành đạt trong công việc và hạnh phúc trong cuộc sống !

Hotline / Zalo: 0903 666 014

Website: https://uniduc.com/vi

-------------////--------------------------------------------////------------

HUMANOID ROBOT CỦA CÔNG TY UNIDUC SẢN XUẤT PHÁT TRIỂN.