KEYPOINT DETECTOR #2: THUẬT TOÁN HARRIS HOẠT ĐỘNG NHƯ THẾ NÀO?

KEYPOINT DETECTOR #2: THUẬT TOÁN HARRIS HOẠT ĐỘNG NHƯ THẾ NÀO?

Uniduc JSC - 2020-03-20 22:57:57 | 782 lượt xem

Mục lục

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)

 

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

GIỚI THIỆU ĐẾN BẠN SẢN PHẨM KHẨU TRANG Y TẾ WAKAMONO KHÁNG VI RÚT LÊN ĐẾN 99% BẠN CÓ THỂ MUA SẢN PHẨM Ở DƯỚI ĐÂY:

 

 

 

 

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

SÁCH ĐẮC NHÂN TÂM HAY ĐƯỢC NHIỀU BẠN TÌM ĐỌC

 

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

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

Đăng kí nhận tin mới



Đánh giá bài viết

0%

0 Tổng người đánh giá
5
0%
4
0%
3
0%
2
0%
1
0%
THÔNG TIN LIÊN HỆ

Công ty Cổ phần Uniduc

Địa Chỉ: 22 Đường Số 54, Phường Thảo Điền, Quận 2

Hotline: 089 6688 629 (Phòng Kinh Doanh / HTKT)

DĐ: 0903 666 014 (Mr Đức)

Email: [email protected]

Website: https://uniduc.com/vi

 
TỔNG QUAN

Công ty Cổ Phần Uniduc chuyên cung cấp các loại robot phục vụ, Agv Robot, hệ thống tự động. Với kinh nghiệm nghiên cứu lâu năm và đội ngũ kỹ sư năng động sáng tạo. Hi vọng Uniduc là điếm đến công nghệ là nơi khách hàng luôn gửi trọn niềm tin. Chúng tôi sẽ luôn luôn phấn đấu cung cấp cho bạn giải pháp, máy móc, dịch vụ tốt nhất.

WEB SITE CÙNG HỆ THỐNG

ĐĂNG KÝ NHẬN TIN

Nhận bản tin thường xuyên để cập nhật giá bán và các chương trình khuyến mãi.


©2018 - 2021 Copyright Uniduc., Jsc. Sitemap