BF、FLANN 特征匹配原理与 OpenCV 实现

本文最后更新于：2024年8月30日下午

在使用特征提取算法提取了描述子后，需要对不同图像之间的特征进行匹配，本文记录 FLANN 以及相关内容。

简介

一般我们用 SIFT、SURF或者 ORB 方法提取到图像关键点的特征描述子之后，需要进行匹配（不然提取了干嘛的呢）。

匹配的方法最直观来看是使用欧式距离，两两相互匹配，对距离排序，也就是蛮力（Brute-Force）匹配。

Brute-Force 匹配

蛮力匹配器很简单。首先在第一幅图像中选取一个关键点然后依次与第二幅图像的每个关键点进行（描述符）距离测试，最后返回距离最近的关键点。

OpenCV 实现

1	`cv.BFMatcher([normType, crossCheck])`

normType

对于BF匹配器，首先我们必须使用 cv.BFMatcher() 创建一个BFMatcher对象。它需要两个可选的参数，第一个是 normType，它指定要使用的距离测量，默认情况下，它是 cv.NORM_L2，它适用于 SIFT，SURF 等（ cv.NORM_L1也在那里）。对于基于二进制字符串的描述符，如 ORB，BRIEF，BRISK 等，应使用cv.NORM_HAMMING，它使用汉明距离作为度量。如果 ORB 使用 WTA_K==3或4，则应使用 cv.NORM_HAMMING2。
crossCheck

第二个参数是布尔变量crossCheck，默认为 false。如果为真，则 Matcher 仅返回具有值 $(i，j)$ 的那些匹配，使得集合 A 中的第 $i$ 个描述符具有集合 B 中的第$j$ 个描述符作为最佳匹配，反之亦然。也就是说，两组中的两个特征应该相互匹配。它提供了一致的结果，是 D.Lowe 在 SIFT 论文中提出的比率测试的一个很好的替代方案。

一旦创建，两个重要的方法是 BFMatcher.match() 和 BFMatcher.knnMatch()。第一个返回最佳匹配。第二种方法返回k个最佳匹配，其中k由用户指定。当我们需要做更多的工作时，它可能是有用的。

就像我们使用 cv.drawKeypoints() 来绘制关键点一样，cv.drawMatches() 帮助我们绘制匹配项。它水平堆叠两个图像，并从第一个图像到第二个图像绘制线条，显示最佳匹配。还有 cv.drawMatchesKnn，它绘制了所有k个最佳匹配。如果 $k = 2$，它将为每个关键点绘制两条匹配线。因此，如果我们想要有选择地绘制它，我们必须传递一个 mask。

DMatch 对象

BFMatcher.match() 方法返回的是 DMatch 对象的列表，此DMatch对象具有以下属性：

DMatch.distance - 描述符之间的距离。越低越好。
DMatch.trainIdx - 训练描述符中描述符的索引
DMatch.queryIdx - 查询描述符中描述符的索引
DMatch.imgIdx - 训练图像的索引。

ORB 特征 BF 匹配示例

在这里，我们将看到一个关于如何匹配两个图像之间的特征的简单示例。在这种情况下，我有一个查询图像和一个目标图像。我们将尝试使用特征匹配在目标图像中查找查询图像。（图片为OpenCV 示例图片中的 /samples/c/box.png 和 /samples/c/box_in_scene.png）

我们使用ORB描述符来匹配功能。所以让我们从加载图像，查找描述符等开始。

import numpy as np
import cv2 as cv
import matplotlib.pyplot as plt

img1 = cv.imread('box.png',0)          # queryImage
img2 = cv.imread('box_in_scene.png',0) # trainImage

# Initiate ORB detector
orb = cv.ORB_create()

# find the keypoints and descriptors with ORB
kp1, des1 = orb.detectAndCompute(img1,None)
kp2, des2 = orb.detectAndCompute(img2,None)

接下来，我们使用距离测量cv.NORM_HAMMING创建一个BFMatcher对象（因为我们使用的是ORB）,并且启用了crossCheck以获得更好的结果。然后我们使用Matcher.match()方法在两个图像中获得最佳匹配。我们按照距离的升序对它们进行排序，以便最佳匹配（低距离）出现在前面。然后我们只绘制前10场比赛（太多了看不清，如果愿意的话你可以多画几条）

# create BFMatcher object
bf = cv.BFMatcher(cv.NORM_HAMMING, crossCheck=True)

# Match descriptors.
matches = bf.match(des1,des2)

# Sort them in the order of their distance.
matches = sorted(matches, key = lambda x:x.distance)

# Draw first 10 matches.
img3 = cv.drawMatches(img1,kp1,img2,kp2,matches[:10], flags=2)

plt.imshow(img3),plt.show()

结果如下图所示：

SIFT 特征 BF 匹配示例

这一次，我们将使用BFMatcher.knnMatch()来获得最佳匹配。在这个例子中，我们将采用k = 2，以便我们可以在他的论文中应用D.Lowe解释的比率测试。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt

img1 = cv.imread('box.png',0)          # queryImage
img2 = cv.imread('box_in_scene.png',0) # trainImage

# Initiate SIFT detector
sift = cv.SIFT()

# find the keypoints and descriptors with SIFT
kp1, des1 = sift.detectAndCompute(img1,None)
kp2, des2 = sift.detectAndCompute(img2,None)

# BFMatcher with default params
bf = cv.BFMatcher()
matches = bf.knnMatch(des1,des2, k=2)

# Apply ratio test
good = []
for m,n in matches:
    if m.distance < 0.75*n.distance:
        good.append([m])

# cv.drawMatchesKnn expects list of lists as matches.
img3 = cv.drawMatchesKnn(img1,kp1,img2,kp2,good,flags=2)

plt.imshow(img3),plt.show()

结果如下图所示：

FLANN匹配

FLANN 是快速最近邻搜索包（Fast_Library_for_Approximate_Nearest_Neighbors）的简称。它是一个对大数据集和高维特征进行最近邻搜索的算法的集合，而且这些算法都已经被优化过了。在面对大数据集时它的效果要好于 BFMatcher。

算法的选择

随机k-d树算法 (The Randomized k-d TreeAlgorithm)

Classick-d tree

找出数据集中方差最高的维度，利用这个维度的数值将数据划分为两个部分，对每个子集重复相同的过程。
Randomizedk-d tree

建立多棵随机k-d树，从具有最高方差的N_d维中随机选取若干维度，用来做划分。在对随机k-d森林进行搜索时候，所有的随机k-d树将共享一个优先队列。

增加树的数量能加快搜索速度，但由于内存负载的问题，树的数量只能控制在一定范围内，比如20，如果超过一定范围，那么搜索速度不会增加甚至会减慢

优先搜索k-means树算法（The Priority Search K-MeansTree Algorithm）

随机k-d森林在许多情形下都很有效，但是对于需要高精度的情形，优先搜索k-means树更加有效。 K-means tree 利用了数据固有的结构信息，它根据数据的所有维度进行聚类，而随机k-d tree一次只利用了一个维度进行划分。

算法描述

步骤1 建立优先搜索k-means tree:

建立一个层次化的 k-means 树；
每个层次的聚类中心，作为树的节点；
当某个cluster内的点数量小于K时，那么这些数据节点将做为叶子节点。

步骤2 在优先搜索k-means tree中进行搜索：

(1) 从根节点N开始检索；

(2) 如果是N叶子节点则将同层次的叶子节点都加入到搜索结果中，count += |N|；

(3) 如果N不是叶子节点，则将它的子节点与query Q比较，找出最近的那个节点 Cq，同层次的其他节点加入到优先队列中；

(4) 对Cq节点进行递归搜索；

(5) 如果优先队列不为空且 count<L，那么从取优先队列的第一个元素赋值给N，然后重复步骤(1)。

聚类的个数K，也称为branching factor 是个非常主要的参数。

建树的时间复杂度 = $O( ndKI ( log(n)/log(K) )) $

n为数据点的总个数
I 为K-means的迭代次数。

搜索的时间复杂度 = $O( L/K * Kd * ( log(n)/(log(K) ) ) = O(Ld ( log(n)/(log(K) ) )$。

层次聚类树（The Hierarchical ClusteringTree）

层次聚类树采用 k-medoids 的聚类方法，而不是 k-means。即它的聚类中心总是输入数据的某个点，但是在本算法中，并没有像 k-medoids 聚类算法那样去最小化方差求聚类中心，而是直接从输入数据中随机选取聚类中心点，这样的方法在建立树时更加简单有效，同时又保持多棵树之间的独立性。

同时建立多棵树，在搜索阶段并行地搜索它们能大大提高搜索性能（归功于随机地选择聚类中心，而不需要多次迭代去获得更好的聚类中心）。建立多棵随机树的方法对k-d tree也十分有效，但对于k-means tree却不适用。

遍历次数

它用来指定递归遍历的次数。值越高结果越准确，但是消耗的时间也越多。如果想修改这个值，可以传入参数。

OpenCV Flann

用例一

对于基于FLANN的匹配器，我们需要传递两个字典，指定要使用的算法和其他相关参数等。首先是IndexParams。对于各种算法，要传递的信息在FLANN文档中进行了解。总而言之，对于像SIFT，SURF等算法，你可以传递以下内容：

1 2	`FLANN_INDEX_KDTREE = 1 index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)`

但使用 ORB 时，我们要传入的参数如下。注释掉的值是文献中推荐使用的，但是它们并不适合所有情况，其他值的效果可能会更好。

FLANN_INDEX_LSH = 6
index_params= dict(algorithm = FLANN_INDEX_LSH,
                   table_number = 6, # 12
                   key_size = 12,     # 20
                   multi_probe_level = 1) #2

第二个字典是SearchParams。它指定应递归遍历索引中的树的次数。值越高，精度越高，但也需要更多时间。如果要更改该值，请传递search_params = dict(checks = 100)。

有了这些信息，我们就可以开始工作了。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt

img1 = cv.imread('box.png',0)          # queryImage
img2 = cv.imread('box_in_scene.png',0) # trainImage

# Initiate SIFT detector
sift = cv.SIFT()

# find the keypoints and descriptors with SIFT
kp1, des1 = sift.detectAndCompute(img1,None)
kp2, des2 = sift.detectAndCompute(img2,None)

# FLANN parameters
FLANN_INDEX_KDTREE = 1
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
search_params = dict(checks=50)   # or pass empty dictionary

flann = cv.FlannBasedMatcher(index_params,search_params)

matches = flann.knnMatch(des1,des2,k=2)

# Need to draw only good matches, so create a mask
matchesMask = [[0,0] for i in xrange(len(matches))]

# ratio test as per Lowe's paper
for i,(m,n) in enumerate(matches):
    if m.distance < 0.7*n.distance:
        matchesMask[i]=[1,0]

draw_params = dict(matchColor = (0,255,0),
                   singlePointColor = (255,0,0),
                   matchesMask = matchesMask,
                   flags = 0)

img3 = cv.drawMatchesKnn(img1,kp1,img2,kp2,matches,None,**draw_params)

plt.imshow(img3,),plt.show()

结果如下图所示：

用例二

图像1（原始图像）

图像2（缩放、旋转、错切）

尝试在图像中找到SIFT特征并应用比率测试来找到最佳匹配。

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt

MIN_MATCH_COUNT = 10

img1 = cv.imread('test.jpg',0)          # queryImage
img2 = cv.imread('test2.jpg',0) # trainImage

# Initiate SIFT detector
sift = cv.xfeatures2d.SIFT_create()

# find the keypoints and descriptors with SIFT
kp1, des1 = sift.detectAndCompute(img1,None)
kp2, des2 = sift.detectAndCompute(img2,None)

FLANN_INDEX_KDTREE = 1
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
search_params = dict(checks = 50)

flann = cv.FlannBasedMatcher(index_params, search_params)
matches = flann.knnMatch(des1,des2,k=2)

# store all the good matches as per Lowe's ratio test.
good = []
for m,n in matches:
    if m.distance < 0.7*n.distance and m.distance < 60:
        good.append(m)

if len(good)>MIN_MATCH_COUNT:
    src_pts = np.float32([ kp1[m.queryIdx].pt for m in good ]).reshape(-1,1,2)
    dst_pts = np.float32([ kp2[m.trainIdx].pt for m in good ]).reshape(-1,1,2)

    M, mask = cv.findHomography(src_pts, dst_pts, cv.RANSAC,5.0)
    matchesMask = mask.ravel().tolist()

    h,w = img1.shape
    pts = np.float32([ [0,0],[0,h-1],[w-1,h-1],[w-1,0] ]).reshape(-1,1,2)
    dst = cv.perspectiveTransform(pts,M)

    img2 = cv.polylines(img2,[np.int32(dst)],True,0,3, cv.LINE_AA)
else:
    print( "Not enough matches are found - {}/{}".format(len(good), MIN_MATCH_COUNT) )
    matchesMask = None

draw_params = dict(matchColor = (0,255,0), # draw matches in green color
                   singlePointColor = None,
                   matchesMask = matchesMask, # draw only inliers
                   flags = 2)

img3 = cv.drawMatches(img1,kp1,img2,kp2,good,None,**draw_params)

plt.imshow(img3, 'gray'),plt.show()

右图的黑色边界为左图变换后的结果

参考资料

文章链接：
https://www.zywvvd.com/notes/study/image-processing/feature-match/flann-match/

“觉得不错的话，给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信支付

支付宝支付

Image_Processing > Feature_Match

#Image_Processing #Feature_Match

BF、FLANN 特征匹配原理与 OpenCV 实现

https://www.zywvvd.com/notes/study/image-processing/feature-match/flann-match/

作者

Yiwei Zhang

发布于

2024年7月9日

许可协议

OpenCV 单应性矩阵计算函数 findHomography 上一篇

ORB 特征下一篇

简介

Brute-Force 匹配

OpenCV 实现

DMatch 对象

ORB 特征 BF 匹配示例

SIFT 特征 BF 匹配示例

FLANN匹配

算法的选择

随机k-d树算法 (The Randomized k-d TreeAlgorithm)

优先搜索k-means树算法（The Priority Search K-MeansTree Algorithm）

层次聚类树 （The Hierarchical ClusteringTree）

遍历次数

OpenCV Flann

用例一

用例二

参考资料

层次聚类树（The Hierarchical ClusteringTree）