# Max-Clique Approximation cv::Mat summation

I have a visual odometry routine where I am attempting to perform inlier detection.

I have an nxn square cv::Mat consistency matrix, where cell ij is 1 if the absolute distance difference between the matches in their unique 3D frames (prior and current) is below some threshold. See "Real-Time Stereo Visual Odometry for Autonomous Ground Vehicles" by Andrew Howard, JPL (2008) for more details.

Anyway,

I want to find the node (match) of this matrix with the maximum degree. My matrix is upper triangular and this means that for every ij where i = j, I need the sum of row i + col j (or equivalently, degree i = sum row i + sum col i).

This can certainly be accomplished with some loops, but my question is, are there built in OpenCV functions that I can make use of to create cleaner code, without having to write my own?

edit retag close merge delete

On a related note, the solution to the problem as a vector of indices whether an approximation or the true max-clique very justifiably ought to be a function in this library.

( 2015-11-05 08:22:31 -0600 )edit

Sort by » oldest newest most voted

This code does just what you want and is fairly efficient. I welcome any feedback on making it more efficient and more general. To be clear, this finds the max-clique seeded by the node with the maximum degree. This also assumes that ptsA and ptsB have identical scale, otherwise, the distance threshold isn't meaningful (and yes, it could be an argument to the function).

template< typename T>
static std::vector<int> getMaxClique( const std::vector<T>& ptsA, const std::vector<T>& ptsB )
{
Timer::Instance().start( "getMaxClique" );

assert( ptsA.size() == ptsB.size() );

const int32_t numMatches = ptsA.size();

cv::Mat  consistencyMatrix    = cv::Mat::zeros( numMatches, numMatches, CV_8U );
uint8_t* consistencyMatrixPtr = consistencyMatrix.ptr<uint8_t>();

static const double distanceThreshold = 5.0;

std::vector<int> nodeDegrees( numMatches, 0 );

for( int i = 0; i < numMatches; ++i )
{
for( int j = i+1, index = (i*numMatches)+j; j < numMatches; ++j, ++index )
{
const double absDistance = abs( cv::norm( ptsA[i] - ptsA[j] ) -
cv::norm( ptsB[i] - ptsB[j] ) );

if( absDistance <= distanceThreshold )
{
consistencyMatrixPtr[index] = 1;
++nodeDegrees[i];
++nodeDegrees[j];
}
}
}

// Fnd the largest set of mutually consistent matches:
//
// This is equivalent to ﬁnding the maximum clique on a graph with
// adjacency matrix W. Since the maximum clique problem is known to
// be NP-complete, we use the following sub-optimal algorithm:
//
// 1) Initialize the clique to contain the match with the largest
//    number of consistent matches (i.e., choose the node with the
//    maximum degree).
// 2) Find the set of matches compatible with all the matches already
//    in the clique.
// 3) Add the match with the largest number consistent matches.
//
// Repeat (2) and (3) until the set of compatible matches is empty.

const int maxNodeIndex = std::distance( nodeDegrees.begin(),
std::max_element( nodeDegrees.begin(), nodeDegrees.end() ) );

// We need to make this matrix not just upper triangular and so we
// must 'complete' the Consistency Matrix:
consistencyMatrix += consistencyMatrix.t();

std::vector<int> candidates = consistencyMatrix.row( maxNodeIndex );

std::vector<int> candidatesIndices;
candidatesIndices.reserve( nodeDegrees[ maxNodeIndex ] );

for( int i = 0; i < numMatches; ++i )
{
if( candidates[i] > 0 )
{
candidatesIndices.push_back( i );
}
}

std::vector<int> maxClique;
maxClique.reserve( nodeDegrees[ maxNodeIndex ] );
maxClique.push_back( maxNodeIndex );

while( !candidatesIndices.empty() )
{
// Find the candidate with largest 'consistent' degree:
int maxIndex  = -1;
int maxDegree = -1;
for( int i = 0; i < candidatesIndices.size(); ++i )
{
const int degree = cv::countNonZero( consistencyMatrix.row( candidatesIndices[i] ) );

if( degree > maxDegree )
{
maxIndex  = candidatesIndices[i];
maxDegree = degree;
}
}

maxClique.push_back( maxIndex );

// New clique addition at consistencyMatrix(maxIndex,maxIndex) is now and
// always zero, so it'll be erased:
candidatesIndices.erase( std::remove_if( candidatesIndices.begin(), candidatesIndices.end(),
[=]( const int index )
{
return consistencyMatrixPtr[ index*numMatches + maxIndex ] == 0;
} ),
std::end( candidatesIndices ) );

}

Timer::Instance().end( "getMaxClique" );

return maxClique;
}

more

Official site

GitHub

Wiki

Documentation