Computer Vision

Feature Matching

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về Feature Matching, một kỹ thuật dùng để so sánh Feature Vector của các keypoint có trong bức ảnh.


FEATURE MATCHING

OpenCV 3 cung cấp class DescriptorMatcher để thực hiện Feature Matching.

Function:

+ Tạo instance Feature Matcher:

matcher = cv2.DescriptorMatcher_create(matcherType)

Trong đó:

  • matcherType – kiểu matcher được áp dụng, gồm:
    1. “BruteForce”: cv2.DESCRIPTOR_MATCHER_BRUTEFORCE;
    2. “BruteForce-SL2”: cv2.DESCRIPTOR_MATCHER_BRUTEFORCE_SL2;
    3. “BruteForce-L1”: cv2.DESCRIPTOR_MATCHER_BRUTEFORCE_L1;
    4. “BruteForce-Hamming”: cv2.DESCRIPTOR_MATCHER_BRUTEFORCE_HAMMING, dùng để so sánh các Binary Feature Vectors;
    5. “FlannBased”: cv2.DESCRIPTOR_MATCHER_FLANNBASED.
  • matcher – instance của Feature Matcher.

+ Tìm ra “k best matches” cho từng Feature Vector của query set:

matches = matcher.knnMatch(queryDescriptors, trainDescriptors, k)

Trong đó:

  • queryDescriptors – tất cả Local Feature Vectors có trong bức ảnh query;
  • trainDescriptors –  tất cả Local Feature Vectors có trong bức ảnh training;
  • k – số “best match” tối đa cho từng Local Feature Vector trong query set.
  • matches – một nested List có kích thước N x k chứa các đối tượng DMatch, trong đó: N là số lượng Local Feature Vectors có trong bức ảnh query; k là số “best match” cho từng Local Feature Vector này.

OpenCV cung cấp class DMatch dùng để chứa thông tin giữa hai Feature Vector trong query set và training set được so sánh với nhau.

Tạo instance DMatch:

DMatchObject = cv2.DMatch(queryIdx, trainIdx, distance)

Trong đó:

  • queryIdx – index của Local Feature Vector trong query set;
  • trainIdx – index của Local Feature Vector trong training set;
  • distance – khoảng cách Euclidean giữa hai Local Feature Vectors trong query set và training set.
  • DMatchObject – đối tượng DMatch được tạo, gồm các thuộc tính sau: DMatchObject.queryIdx, DMatchObject.trainIdx, DMatchObject.distance.

TRIỂN KHAI FEATURE MATCHING

Source code: matcher.py

import numpy as np
import argparse
import cv2

ap = argparse.ArgumentParser()
ap.add_argument("-f", "--first", required=True)
ap.add_argument("-s", "--second", required=True)

args = vars(ap.parse_args())

detector = cv2.ORB_create()
extractor = cv2.xfeatures2d.SURF_create()
matcher = cv2.DescriptorMatcher_create(cv2.DESCRIPTOR_MATCHER_BRUTEFORCE)

imageA = cv2.imread(args["first"])
imageB = cv2.imread(args["second"])
grayA = cv2.cvtColor(imageA, cv2.COLOR_BGR2GRAY)
grayB = cv2.cvtColor(imageB, cv2.COLOR_BGR2GRAY)

kpsA = detector.detect(grayA)
kpsB = detector.detect(grayB)

(kpsA, descsA) = extractor.compute(grayA, kpsA)
(kpsB, descsB) = extractor.compute(grayB, kpsB)

rawMatches = matcher.knnMatch(descsA, descsB, 2)
matches = []
src = []
dst = []

if rawMatches is not None:
	for m in rawMatches:
		if (len(m) == 2) and (m[0].distance < m[1].distance*0.7):
			matches.append((m[0].trainIdx, m[0].queryIdx))

	print("# of keypoints from first image: {}".format(len(kpsA)))
	print("# of keypoints from second image: {}".format(len(kpsB)))
	print("# of matched keypoints: {}".format(len(matches)))

	(hA, wA) = imageA.shape[:2]
	(hB, wB) = imageB.shape[:2]

	vis = np.zeros((max(hA,hB), wA+wB, 3), dtype="uint8")
	vis[:hA,:wA] = imageA
	vis[:hB, wA:] = imageB

	for (trainIdx, queryIdx) in matches:
		color = np.random.randint(0,255, size=3)
		color = tuple(map(int, color))

		ptA = (int(kpsA[queryIdx].pt[0]), int(kpsA[queryIdx].pt[1]))
		ptB = (int(kpsB[trainIdx].pt[0]+wA), int(kpsB[trainIdx].pt[1]))

		src.append(kpsA[queryIdx].pt)
		dst.append(kpsB[trainIdx].pt)

		cv2.line(vis, ptA, ptB, color, 2)

	cv2.imshow("Matched", vis)
	cv2.waitKey(0)

	src = np.array(src)
	dst = np.array(dst)

	M, status = cv2.findHomography(src, dst, cv2.RANSAC, 4.0)
	print("status: {}".format(float(status.sum()) * 100 / status.size))

	pts = np.float32([[0,0], [0,hA-1], [wA-1,hA-1], [wA-1,0]]).reshape(-1,1,2)
	result = cv2.perspectiveTransform(pts, M)

	result[..., 0] += wA
	cv2.polylines(vis, [np.int32(result)], True, (0,255,0), 2)
	cv2.imshow("Matched", vis)
	cv2.waitKey(0)

Giải thích:
– Dòng 11-13: Chúng ta sử dụng ORB Keypoint Detector, SURF Feature Descriptor và Brute Force Matcher;
– Dòng 20,21: Xác định các keypoint có trong cả 2 bức ảnh A và B;
– Dòng 23,24: Trích xuất Feature Vector cho các keypoint có trong cả 2 bức ảnh A và B;
– Dòng 26: Áp dụng knnMatch() với k=2 để tìm ra 2 Feature Vectors có trong descsB phù hợp nhất với mỗi Feature Vector có trong descsA. Chúng ta chọn k=2 là để có thể áp dụng Ratio Test giữa 2 “best match”;
– Dòng 33,34: áp dụng Ratio Test để loại bỏ “False Positive”, xem hình 1;
– Dòng 59: hiển thị kết quả Feature Matching;
– Dòng 54,55: tổng hợp các keypoint ở queryImage và trainImage để chuẩn bị cho biến đổi homography;
– Dòng 65: tính ma trận chuyển đổi Homography;
– Dòng 68: chọn ra 4 điểm ở 4 góc của queryImage;
– Dòng 69: với ma trận chuyển đổi Homography đã có, tính toán ra 4 điểm trong trainImage tương ứng với 4 góc của queryImage;
– Dòng 71-74: hiển thị kết quả Object Matching.

ratiotest
Hình 1 – David Lowe’s ratio test

Với việc áp dụng David Lowe’s ratio test và bỏ qua các “matches” có ratio lớn hơn 0.7, chúng ta có thể loại bỏ hoàn toàn False Positive trong khi chỉ để mất ít hơn 15% True Positive.

Query image:
querybook

Traning image:

inputimage

Output:

 

capture

Ở ví dụ trên, chúng ta đã sử dụng combo (ORB detector, SURF descriptor, Brute Force matcher) và nhận được kết quả khá ổn. Tuy nhiên, việc lựa chọn combo phụ thuộc rất nhiều vào dữ liệu, vì vậy hãy thử qua nhiều combo khác nhau trên tập dữ liệu mẫu trước khi chọn ra combo tốt nhất.


SUMMARY

Như vậy chúng ta đã tìm hiểu về kỹ thuật và cách áp dụng Feature Matching + David Lowe’s ratio test. 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 DMatch class.
[2] OpenCV DescriptorMatcher class
[3] Distinctive Image Features from Scale-Invariant Keypoints

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