Open pete-machine opened 6 years ago
pete-machine
commented
6 years ago After some researching... Is it because I should use the hamming difference between the two best matches (2NN)? Rather than simply finding a match below a certain threshold?
komrad36
commented
6 years ago Hey Pete,
Thanks for checking out my CV stuff! Unfortunately I really do not have an abundance of time at the moment, but I can take a look every once in a while.
I'd have a look at my K2NN matcher. Its description says,
"2NN mode, i.e., a match is returned if the best match between a query vector and a training vector is more than a certain threshold number of bits better than the second-best match.
Yes, that means the DIFFERENCE in popcounts is used for thresholding, NOT the ratio. This is the CORRECT approach for binary descriptors."
So there are two issues here: how do you compare two descriptors, and how do you threshold?
Comparing two binary descriptors, despite what plenty of literature says, is best done by the DIFFERENCE (i.e. the Hamming distance as you mention), not a ratio, of bit differences.
Thresholding is best done by whether the BEST match is more than some amount better than the SECOND-BEST match, which you can think about as a signal-to-noise ratio of sorts. This is way more robust than just seeing how good the best match is - consider a blur or lighting change that uniformly makes every match 10 bits worse. You'd get exactly the same results with this best-second-best system, whereas a simple match-if-fewer-than-n-bits-different would suddenly change its response.
Please try K2NN (or do your own matching but with these two things in mind) and let me know how it goes!
pete-machine
commented
6 years ago Thank you for your elaborated responds! For the above code I simply use the best match (the hamming distance). In the above examples, I set the threshold for both ORB and LATCH, so they will return (roughly) the same number of matches. As demonstrated in the first post, I have consistently seen that ORB performs better. I have later - actually in your K2NN readme - found that for matching it is generally better to use the difference between the best and second-best match (as you have elaborated even further).
However, after further considerations, I have realized that I would still assume LATCH to work better than ORB, when I use the simple best-match approach (match-if-fewer-than-n-bits-different) for both... However, it could be that some internal property of the descriptors (LATCH vs ORB), causes ORB to perform better than LATCH for first-order matching (my sample code above) and LATCH to perform better than ORB for the best-second-best system. I will try it out. I will write you back with the results.
pete-machine
commented
6 years ago I ended up using the knn-matcher from opencv, because it was faster to implement. I have provided the code below. The threshold of ORB and LATCH is selected to provide (roughly) the same number of matches. ORB 49, LATCH 53. Again it seems that ORB (top) performs better than LATCH (bottom)... However, it is still probable that I am doing something wrong elsewhere in the code. I guess I should also try your K2NN...
/*******************************************************************
* main.cpp
* LATCH
*
* Author: Kareem Omar
* kareem.omar@uah.edu
* https://github.com/komrad36
*
* Last updated Sep 12, 2016
*******************************************************************/
//
// Fastest implementation of the fully scale-
// and rotation-invariant LATCH 512-bit binary
// feature descriptor as described in the 2015
// paper by Levi and Hassner:
//
// "LATCH: Learned Arrangements of Three Patch Codes"
// http://arxiv.org/abs/1501.03719
//
// See also the ECCV 2016 Descriptor Workshop paper, of which I am a coauthor:
//
// "The CUDA LATCH Binary Descriptor"
// http://arxiv.org/abs/1609.03986
//
// And the original LATCH project's website:
// http://www.openu.ac.il/home/hassner/projects/LATCH/
//
// See my GitHub for the CUDA version, which is extremely fast.
//
// My implementation uses multithreading, SSE2/3/4/4.1, AVX, AVX2, and
// many many careful optimizations to implement the
// algorithm as described in the paper, but at great speed.
// This implementation outperforms the reference implementation by 800%
// single-threaded or 3200% multi-threaded (!) while exactly matching
// the reference implementation's output and capabilities.
//
// If you do not have AVX2, uncomment the '#define NO_AVX_PLEASE' in LATCH.h to route the code
// through SSE isntructions only. NOTE THAT THIS IS ABOUT 50% SLOWER.
// A processor with full AVX2 support is highly recommended.
//
// All functionality is contained in the file LATCH.h. This file
// is simply a sample test harness with example usage and
// performance testing.
//
#include <bitset>
#include <chrono>
#include <iostream>
#include <opencv2/opencv.hpp>
#include <vector>
//#include <Eigen/Core>
#include "LATCH.h"
#define VC_EXTRALEAN
#define WIN32_LEAN_AND_MEAN
using namespace std::chrono;
void remove_outside( std::vector<cv::KeyPoint>& keypoints,const int width, const int height) {
keypoints.erase(std::remove_if(keypoints.begin(), keypoints.end(), [width, height](const cv::KeyPoint& kp) {return kp.pt.x <= 36 || kp.pt.y <= 36 || kp.pt.x >= width - 36 || kp.pt.y >= height - 36; }), keypoints.end());
}
int main(int argc, char **argv) {
// ------------- Configuration ------------
constexpr int numkps = 2000;
constexpr bool multithread = true;
int threshold_orb = 50;
int threshold_latch = 100;
int diff_2NN_orb = 0;
int diff_2NN_latch = 0;
float imresize = -1;
bool second_order = false;
// --------------------------------
/*//------------- Image Read0 ------------
constexpr char name0[] = "test.jpg";
cv::Mat image = cv::imread(name0, CV_LOAD_IMAGE_GRAYSCALE);
cv::Rect roi0(0, 0, image.cols/3, image.rows/3);
cv::Rect roi1(100, 100, image.cols/3-100, image.rows/3-100);
cv::Mat image0 = image(roi0);
cv::Mat image1 = image(roi1);
if (!image0.data || !image1.data) {
std::cerr << "ERROR: failed to open image. Aborting." << std::endl;
return EXIT_FAILURE;
}
// -------------------------------- */
//------------- Image Read0 ------------
constexpr char name0[] = "box.png";
constexpr char name1[] = "box_in_scene.png";
//constexpr char name0[] = "000000.jpg";
//constexpr char name1[] = "000005.jpg";
cv::Mat image0 = cv::imread(name0, CV_LOAD_IMAGE_GRAYSCALE);
cv::Mat image1 = cv::imread(name1, CV_LOAD_IMAGE_GRAYSCALE);
if (!image0.data || !image1.data) {
std::cerr << "ERROR: failed to open image. Aborting." << std::endl;
return EXIT_FAILURE;
}
// --------------------------------
int print_keypoint_idx = 0; // keypoints_class.size()
std::cout << "argc:" << argc << std::endl;
if (argc == 4) {
threshold_orb = std::atoi(argv[1]);
threshold_latch = std::atoi(argv[2]);
imresize = std::atof(argv[3]);
}
if (argc == 5) {
second_order = std::atoi(argv[1])>0;
diff_2NN_orb = std::atoi(argv[2]);
diff_2NN_latch = std::atoi(argv[3]);
imresize = std::atof(argv[4]);
}
if(imresize>0) {
cv::resize(image1,image1,cv::Size(0,0),imresize,imresize,cv::INTER_CUBIC);
}
// ------------- Detection ------------
std::cout << std::endl << "Detecting..." << std::endl;
int borderDistance = 36;
cv::Ptr<cv::ORB> orb = cv::ORB::create(numkps, 1.2f, 8, borderDistance, 0, 2, cv::ORB::HARRIS_SCORE, 31, 20);
std::vector<cv::KeyPoint> keypoints0;
std::vector<cv::KeyPoint> keypoints1;
orb->detect(image0, keypoints0);
orb->detect(image1, keypoints1);
remove_outside(keypoints0,image0.cols, image0.rows);
remove_outside(keypoints1,image1.cols, image1.rows);
// --------------------------------
// ------------- ORB feature descriptor (OpenCV) ------------
cv::Mat cv_desc0_orb, cv_desc1_orb;
orb->compute(image0, keypoints0,cv_desc0_orb);
orb->compute(image1, keypoints1,cv_desc1_orb);
// MATCHING ORB
//cv::BFMatcher matcher(cv::NORM_HAMMING,true);
std::vector< cv::DMatch > good_matches_orb;
if(second_order){
cv::BFMatcher matcher(cv::NORM_HAMMING);
std::vector< std::vector<cv::DMatch> > nn_matches;
matcher.knnMatch(cv_desc0_orb, cv_desc1_orb, nn_matches, 2);
//std::vector<cv::KeyPoint> matched1, matched2, inliers1, inliers2;
for (size_t i = 0; i < nn_matches.size(); i++) {
//cv::DMatch first = nn_matches[i][0];
float dist1 = nn_matches[i][0].distance;
float dist2 = nn_matches[i][1].distance;
bool state = (dist2-dist1)>=diff_2NN_orb;
if (state) {
std::cout << "Sample ORB, trainIdx: " << nn_matches[i][0].trainIdx << ", queryIdx: " << nn_matches[i][0].queryIdx << ", Distance: " << nn_matches[i][0].distance << ", diff: " << dist2-dist1 << ", use? " << state << std::endl;
good_matches_orb.push_back(nn_matches[i][0]);
}
/*if( dist1 <= threshold_orb){
bool state = (dist2-dist1)>=diff_2NN_orb;
std::cout << "Sample ORB, trainIdx: " << nn_matches[i][0].trainIdx << ", queryIdx: " << nn_matches[i][0].queryIdx << ", Distance: " << nn_matches[i][0].distance << ", diff: " << dist2-dist1 << ", use? " << state << std::endl;
if (state) {
good_matches_orb.push_back(nn_matches[i][0]);
}
}*/
}
std::cout << "ORB: Descriptors size: " << cv_desc0_orb.size() << ", Good matches: " << good_matches_orb.size() << "(treshold " << diff_2NN_orb << ")" << std::endl;
}
else{
cv::BFMatcher matcher(cv::NORM_HAMMING,true);
// LATCH
std::vector< cv::DMatch > matches_orb;
matcher.match( cv_desc0_orb, cv_desc1_orb, matches_orb );
std::vector< cv::DMatch > test_matches;
for(unsigned int i = 0; i < matches_orb.size(); i++ ) {
if( matches_orb[i].distance < threshold_orb){
good_matches_orb.push_back( matches_orb[i]);
//std::cout << "Sample ORB, trainIdx: " << matches_orb[i].trainIdx << ", queryIdx: " << matches_orb[i].queryIdx << ", Distance: " << matches_orb[i].distance << std::endl;
}
}
std::cout << "ORB: Descriptors size: " << cv_desc0_orb.size() << ", Good matches: " << good_matches_orb.size() << "(treshold " << threshold_orb << ")" << std::endl;
}
// ------------- LATCH feature descriptor ------------
// IMPORTANT! Convertion between OpenCV and the latch descriptor.
// The opencv bruteforce matching requires the data to be in a cv::Mat format.
// A cv::Mat with dimenstions [n_keypoints x 64] of type char/uint8_t is initialized. (A single row correspond to a keypoints with a (64x8=) 512 bits descriptor).
cv::Mat cv_desc0_latch = cv::Mat::zeros(keypoints0.size(),64,CV_8UC1);
cv::Mat cv_desc1_latch = cv::Mat::zeros(keypoints1.size(),64,CV_8UC1);
// A pointer is created to point to the data of the cv::Mat.
uint64_t* desc0_latch = (uint64_t*)(cv_desc0_latch.data);
uint64_t* desc1_latch = (uint64_t*)(cv_desc1_latch.data);
std::vector<KeyPoint> kps0_latch;
std::vector<KeyPoint> kps1_latch;
for (auto&& kp : keypoints0) kps0_latch.emplace_back(kp.pt.x, kp.pt.y, kp.size, kp.angle * 3.14159265f / 180.0f);
for (auto&& kp : keypoints1) kps1_latch.emplace_back(kp.pt.x, kp.pt.y, kp.size, kp.angle * 3.14159265f / 180.0f);
//for(int i = 0; i < 10; i++) {
LATCH<multithread>(image0.data, image0.cols, image0.rows, static_cast<int>(image0.step), kps0_latch, desc0_latch);
LATCH<multithread>(image1.data, image1.cols, image1.rows, static_cast<int>(image1.step), kps1_latch, desc1_latch);
//}
// LATCH ORIGINAL //////////////////////////////////////////////
std::cout << "Descriptor (LATCH original): " << print_keypoint_idx << "/" << keypoints0.size()-1 << std::endl;
int shift = print_keypoint_idx*8;
for (int i = 0; i < 8; ++i) {
std::cout << std::bitset<64>(desc0_latch[i+shift]) << std::endl;
}
std::cout << std::endl;
// LATCH CLASS ( FLIPPED!!!) /////////////////////////////////////////////////
std::cout << "Descriptor (LATCH cv_mat FLIPPED!!!): " << print_keypoint_idx << "/" << keypoints0.size()-1 << std::endl;
for (int i = 0; i < 8; ++i) {
for (int ii = 0; ii < 8; ++ii) {
std::cout << std::bitset<8>(cv_desc0_latch.at<unsigned char>(print_keypoint_idx,i*8+7-ii));
}
std::cout << std::endl;
}
std::cout << std::endl;
// MATCHING LATCH
std::vector< cv::DMatch > good_matches_latch;
if(second_order){
cv::BFMatcher matcher(cv::NORM_HAMMING);
std::vector< std::vector<cv::DMatch> > nn_matches;
matcher.knnMatch(cv_desc0_latch, cv_desc1_latch, nn_matches, 2);
//std::vector<cv::KeyPoint> matched1, matched2, inliers1, inliers2;
for (size_t i = 0; i < nn_matches.size(); i++) {
//cv::DMatch first = nn_matches[i][0];
float dist1 = nn_matches[i][0].distance;
float dist2 = nn_matches[i][1].distance;
bool state = (dist2-dist1)>=diff_2NN_latch;
if (state) {
std::cout << "Sample Latch, trainIdx: " << nn_matches[i][0].trainIdx << ", queryIdx: " << nn_matches[i][0].queryIdx << ", Distance: " << nn_matches[i][0].distance << ", diff: " << dist2-dist1 << ", use? " << state << std::endl;
good_matches_latch.push_back(nn_matches[i][0]);
}
/*if( dist1 < threshold_latch){
bool state = (dist2-dist1)>=diff_2NN_latch;
std::cout << "Sample Latch, trainIdx: " << nn_matches[i][0].trainIdx << ", queryIdx: " << nn_matches[i][0].queryIdx << ", Distance: " << nn_matches[i][0].distance << ", diff: " << dist2-dist1 << ", use? " << state << std::endl;
if (state) {
good_matches_latch.push_back(nn_matches[i][0]);
}
}*/
}
std::cout << "LATCH: Descriptors size: " << cv_desc0_latch.size() << ", Good matches: " << good_matches_latch.size() << "(treshold " << diff_2NN_latch << ")" << std::endl;
}
else{
cv::BFMatcher matcher(cv::NORM_HAMMING,true);
// LATCH
std::vector< cv::DMatch > matches_latch;
matcher.match( cv_desc0_latch, cv_desc1_latch, matches_latch );
std::vector< cv::DMatch > test_matches;
for(unsigned int i = 0; i < matches_latch.size(); i++ ) {
if( matches_latch[i].distance < threshold_latch){
good_matches_latch.push_back( matches_latch[i]);
std::cout << "Sample LATCH, trainIdx: " << matches_latch[i].trainIdx << ", queryIdx: " << matches_latch[i].queryIdx << ", Distance: " << matches_latch[i].distance << std::endl;
}
}
std::cout << "LATCH: Descriptors size: " << cv_desc0_latch.size() << ", Good matches: " << good_matches_latch.size() << "(treshold " << threshold_latch << ")" << std::endl;
}
/*cv::BFMatcher matcher2(cv::NORM_HAMMING,true);
std::vector< cv::DMatch > matches_latch;
matcher2.match( cv_desc0_latch, cv_desc1_latch, matches_latch);
std::vector< cv::DMatch > good_matches_latch;
for(unsigned int i = 0; i < matches_latch.size(); i++ ) {
if( matches_latch[i].distance < threshold_latch) {
good_matches_latch.push_back( matches_latch[i]);
std::cout << "Sample LATCH, trainIdx: " << matches_latch[i].trainIdx << ", queryIdx: " << matches_latch[i].queryIdx << ", Distance: " << matches_latch[i].distance << std::endl;
}
}*/
// Visualize ORB matches
cv::Mat img_matches_orb;
cv::drawMatches( image0, keypoints0, image1, keypoints1,
good_matches_orb, img_matches_orb, cv::Scalar::all(-1), cv::Scalar::all(-1),
std::vector<char>(), cv::DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS );
// Visualize LATCH matches
cv::Mat img_matches_latch;
cv::drawMatches( image0, keypoints0, image1, keypoints1,
good_matches_latch, img_matches_latch, cv::Scalar::all(-1), cv::Scalar::all(-1),
std::vector<char>(), cv::DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS );
/*//-- Show detected matches
cv::namedWindow( "Good Matches (ORB)", CV_WINDOW_NORMAL );
cv::imshow( "Good Matches (ORB)", img_matches_orb );
//-- Show detected matches
cv::namedWindow( "Good Matches (LATCH)", CV_WINDOW_NORMAL );
cv::imshow( "Good Matches (LATCH)", img_matches_latch );*/
// Visualize BOTH matches
cv::Mat both;
both.push_back(img_matches_orb);
both.push_back(img_matches_latch);
cv::namedWindow( "ORB (TOP), LATCH (BUTTOM)", CV_WINDOW_NORMAL );
cv::imshow( "ORB (TOP), LATCH (BUTTOM)", both );
cv::imwrite("TestImage"+std::to_string(diff_2NN_orb)+".png",img_matches_orb);
cv::waitKey(0);
}
shamiul110107
commented
6 years ago Very helpful and very nice explanation. But I want to know the procedure of remove_outside() method. Why you used 36 in (kp.pt.x <= 36 ). Can I use 36 in my detection.
Please help me. Thanks in advance.
pete-machine
commented
6 years ago Thank you. Yes, I guess, it would be possible to simply use 36 in the detection step... However, it is a long time ago, and it puzzles me, that I didn't simply do this myself.
Will you try it and report back the result?
manhofer
commented
5 years ago I observed similar issues. I think there is something wrong with the feature scale. In order to make it work properly I had to take the feature size that OpenCV stores in its keypoints and divide it by 7 before passing it on to this LATCH implementation as the scale parameter. Since inside it is dividing by 7 again (or actually multiplying by 0.142857142857), the feature size apparently has to be divided by 49 (7x7) which is the area of one comparison patch. For me it then works much better than ORB for rotation as well as scale differences.
I have used both a ORB and LATCH feature descriptor for the same interest points. However, for a simple matching between two images it is clear that ORB performs better. So I guess something is wrong?
To demonstrate that the code is (somewhat) working, I will first match two crops from the same images. For this use case ORB and LATCH performs equivalent (See image) . A max threshold is set to only 1 in the matching. I use the following command for the provided code in the bottom.
In the next test, one of the crops is resized by a factor of 2. The hamming distance threshold is increased to 20 for ORB and 110 for LATCH, because this will provide roughly the same number of matches. In this use case it is clear that ORB performs better than LATCH (See image, ORB in top and LATCH in bottom). I use the following command for the provided code.
Finally, I wanna show the result of two opencv samples (from /OpenCV/samples/data/box and /OpenCV/samples/data/box_in_scene). The example clear shows that ORB works better than LATCH for roughly the same number of matches.
I use the following command for the provided code.
I are the samples.
