LSH比BruteForce匹配慢 [英] LSH slower than BruteForce matching

问题描述

我需要在两个图像之间进行相似性匹配。为此，我在C ++中使用OpenCV的ORB关键点检测器和ORB描述符提取器

I need to do similarity matching between two images. For that, I'm using ORB keypoints detector and ORB descriptor extractor from OpenCV in C++

我的问题在于匹配。我决定使用LSH和 BFMatcher 测试两种类型的匹配： FLANNBasedMatcher 。根据文档和两种算法，LSH假设比蛮力更快（第一个不是逐个比较所有描述符而第二个比较）。

My problem is in the matching. I decided to test two types of matching: FLANNBasedMatcher using LSH and BFMatcher. Where, according to documentation and both algorithms, LSH suppose to be faster than brute force (the first one doesn't compare all descriptors one by one and the second one does).

当我尝试两者时，我的BFMatcher比LSH更快（但速度更快），我不知道为什么以及如何解决它。

When I tried both, I got BFMatcher faster than LSH (But much faster), and I have no idea why and how to fix it.

一开始我虽然需要更多关键点才能看到差异，但我决定通过让ORB检测多达70000个关键点来增加这一点：

At the beginning I though it needed more keypoints in order to see a difference, and I decided to increase this by letting ORB detect up to 70000 keypoints:

OrbFeatureDetector detector(70000);

但这让它变得更慢。

我不知道我对LSH的假设是否比蛮力更快是错误的，或者我是否对我的代码做错了。

I don't know if my assumption of LSH being faster than brute force is wrong, or if I'm doing something wrong with my code.

我的代码：

//Detector
    int numKeyPoints = 70000; 
    OrbFeatureDetector detector(numKeyPoints); 
    detector.detect( image, keypoints); 

// Extractor
    OrbDescriptorExtractor extractor;
    extractor.compute(image, keypoints, descriptors); 

// BFMatcher
    BFMatcher matcher(NORM_HAMMING); 
    matcher.radiusMatch(descriptors_1, descriptors_2, matches, 30);


// LSHMatcher
    FlannBasedMatcher matcher(new flann::LshIndexParams(6,12,2));
    matcher.knnMatch(descriptors_1, descriptors_2, matches, 1); 

平均时间：

• 暴力=每张图像0.006秒


• 每张图像LSH = 0.04秒

推荐答案

它是否已知错误。
尝试使用分层聚类 - 它比bruteforce快得多。

Is it known bug. Try to use Hierarchical Clustering - it is much faster than bruteforce.

cv::flann::Index tree(Desriptors,cv::flann::HierarchicalClusteringIndexParams(),FLANN_DIST_HAMMIN‌​G); 
cv::Mat indices, dists; 
tree.knnSearch(Desriptors2, indices, dists, 1, cv::flann::SearchParams());

这篇关于LSH比BruteForce匹配慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！