NNRMatcher.cpp
Go to the documentation of this file.
00001 /*******************************************************************************
00002  *  NNRMatcher.cpp
00003  *
00004  *  (C) 2007 AG Aktives Sehen <agas@uni-koblenz.de>
00005  *           Universitaet Koblenz-Landau
00006  *
00007  *  Additional information:
00008  *  $Id: $
00009  *******************************************************************************/
00010 
00011 #include "NNRMatcher.h"
00012 
00013 #include "Architecture/Singleton/Clock.h"
00014 
00015 #include "Workers/Math/vec2.h"
00016 
00017 #include <assert.h>
00018 #include <map>
00019 #include <list>
00020 #include <math.h>
00021 
00022 using namespace std;
00023 
00024 #define THIS NNRMatcher
00025 
00026 THIS::THIS ( std::vector< KeyPoint >* keyPointsA, std::vector< KeyPoint >* keyPointsB )
00027 {
00028     m_KeyPointsA = keyPointsA;
00029     m_KeyPointsB = keyPointsB;
00030     m_Log << "NNRMatcher created\n";
00031     m_Log << "Number of keypoints (scenePoints/objectImagePoints): " << m_KeyPointsA->size() << " / " << m_KeyPointsB->size() << endl;
00032 }
00033 
00034 THIS::~THIS()
00035 {
00036 }
00037 
00038 void THIS::match ( float maxDistRatio )
00039 {
00040     if ( ( m_KeyPointsA->size() ==0 ) || ( m_KeyPointsB->size() ==0 ) || ( m_Matches.size() !=0 ) ) { return; }
00041 
00042     int startTime = Clock::getInstance()->getTimestamp();
00043 
00044     int size1=m_KeyPointsA->size();
00045     int size2=m_KeyPointsB->size();
00046 
00047     float maxDistRatioSquared=maxDistRatio*maxDistRatio;
00048 
00049     vector< unsigned > indPos;
00050     vector< unsigned > indNeg;
00051     indPos.reserve( m_KeyPointsB->size() );
00052     indNeg.reserve( m_KeyPointsB->size() );
00053 
00054     //sort keypoints2 by their sign
00055     for ( int index2=0; index2 < size2; index2++ )
00056     {
00057       if ( (*m_KeyPointsB)[index2].sign > 0 )
00058       {
00059         indPos.push_back( index2 );
00060       }
00061       else
00062       {
00063         indNeg.push_back( index2 );
00064       }
00065     }
00066 
00067     for ( int index1=0; index1 < size1; index1++ )
00068     {
00069         //index in second keypoint list corresponding to minimal distance
00070         int minIndexB=-1;
00071         //minimal distance found
00072         double minDist=1e10;
00073         //second-minimal distance
00074         double secondMinDist=1e10;
00075 
00076         //select list of indices of keypoints with positive or negative sign, according to currently matche keypoint
00077         vector< unsigned >& indices2 = (*m_KeyPointsA)[index1].sign > 0 ? indPos : indNeg;
00078 
00079         for ( unsigned k=0; k < indices2.size(); k++ )
00080         {
00081           int index2 = indices2[ k ];
00082           double distance = (*m_KeyPointsA)[index1].squaredDistance ( (*m_KeyPointsB)[index2] );//, secondMinDist );
00083             //new minimum found:
00084             if ( distance < minDist )
00085             {
00086                 secondMinDist=minDist;
00087                 minDist=distance;
00088                 minIndexB=index2;
00089             }
00090             else
00091             if ( distance < secondMinDist )
00092             {
00093                 secondMinDist=distance;
00094             }
00095         }
00096         if ( ( minIndexB != -1 ) && ( minDist/secondMinDist < maxDistRatioSquared ) )
00097         {
00098             KeyPointMatch match={ index1, minIndexB, minDist, 0, 0 };
00099             m_Matches.push_back ( match );
00100             m_Log << index1 << "->" << minIndexB << " (d" << minDist << "/r" << minDist/secondMinDist << ")  ";
00101         }
00102 
00103     }
00104     m_Log << "\n--- " << m_Matches.size() << " keypoints matched in first phase in " << ( Clock::getInstance()->getTimestamp() - startTime ) << "ms\n";
00105 
00106     eliminateMultipleMatches();
00107 
00108 }
00109 
00110 
00111 void THIS::eliminateMultipleMatches()
00112 {
00113     //It is possible that more than one ipoint in First has been matched to
00114     //the same ipoint in Second, in this case eliminate all but the closest one
00115 
00116   int startTime = Clock::getInstance()->getTimestamp();
00117 
00118     //maps keypoints in Second to their closest match result
00119     //first: index in m_KeyPointsB
00120     //second: iterator in m_Matches
00121     map< unsigned, MatchElem > bestMatch;
00122 
00123     m_Log << "deleting ";
00124 
00125     MatchElem currentMatch=m_Matches.begin();
00126     while ( currentMatch != m_Matches.end() )
00127     {
00128         unsigned index2=currentMatch->index2;
00129 
00130         //check if a match with this keypoint in Second was found before
00131         map< unsigned, MatchElem >::iterator previous=bestMatch.find ( index2 );
00132 
00133         //this is the first match found which maps to current second index
00134         if ( previous == bestMatch.end() )
00135         {
00136             bestMatch[ index2 ] = currentMatch;
00137             currentMatch++;
00138             continue;
00139         }
00140 
00141         MatchElem previousMatch = previous->second;
00142         //a match mapping to this index in second has been found previously, and had a higher distance
00143         //so delete the previously found match
00144         if ( currentMatch->distance < previousMatch->distance )
00145         {
00146             m_Log << previousMatch->index1 << "->" << previousMatch->index2;
00147             m_Log << " (better:" << currentMatch->index1 << "->" << currentMatch->index2 << ")  ";
00148             m_Matches.erase ( previousMatch );
00149             bestMatch[ index2 ] = currentMatch;
00150             currentMatch++;
00151             continue;
00152         }
00153         //otherwise, the previously found best match is better than current,
00154         //so delete current
00155         m_Log << currentMatch->index1 << "->" << currentMatch->index2;
00156         m_Log << " (better:" << previousMatch->index1 << "->" << previousMatch->index2 << ")  ";
00157         currentMatch=m_Matches.erase ( currentMatch );
00158     }
00159     m_Log << "\n--- " << m_Matches.size() << " remaining after multiple match elimination in " << ( Clock::getInstance()->getTimestamp() - startTime ) << "ms\n";
00160 
00161 }
00162 
00163 string THIS::getLog()
00164 {
00165     return m_Log.str();
00166 }
00167 
00168 #undef THIS


or_libs
Author(s): Viktor Seib
autogenerated on Tue Jan 7 2014 11:24:03