Bug in surf.cpp's KeypointGreater causes crash (Patch #2149)

I noticed a problem when attempting to extract features from certain images under windows (one such image is attached).

The problem occurs inside surf's fastHessianDetector, when it performs the std::sort on the keypoints vector it has just formed. It attempts to sort the keypoints vector using the comparison function provided (surf's KeypointGreater struct with operator() defined).

While performing this sort it can (and for my image does) occur that this comparison operator (which defines the > operator technically) is passed two keypoints that are identical in all but their x values.
Specifically the keypoints KeyPoint1 and KeyPoint2 are defined:

KeyPoint1:
pt {x=436.70590 y=548.85352 }
size 22.0000
angle -1.0000
response 3198.3408
octave 0
class_id 1

KeyPoint2:
pt {x=188.70592 y=548.85352 }
size 22.0000
angle -1.0000
response 3198.3408
octave 0
class_id 1

For your reference the KeypointGreater struct (from surf.cpp) looks as follows:

struct KeypointGreater
{
    inline bool operator()(const KeyPoint& kp1, const KeyPoint& kp2) const
    {
        if(kp1.response > kp2.response) return true;
        if(kp1.response < kp2.response) return false;
        if(kp1.size > kp2.size) return true;
        if(kp1.size < kp2.size) return false;
        if(kp1.octave > kp2.octave) return true;
        if(kp1.octave < kp2.octave) return false;
        if(kp1.pt.y < kp2.pt.y) return false;
        if(kp1.pt.y > kp2.pt.y) return true;
        return kp1.pt.x < kp2.pt.y;
    }
};

In this case if you call KeypointGreater(KeyPoint1, KeyPoint2) it will get down to the last line of this function and then compares KeyPoint1.pt.x (436.70590) with KeyPoint2.pt.y (548.85352) (note the y not x).
This returns true. If you perform the comparison KeypointGreater(KeyPoint2, KeyPoint1), then the same thing happens, it compares KeyPoint2.pt.x (188.70592) with KeyPoint1.pt.y (548.85352) which also returns true. This violates the strict weak ordering property that should hold for the comparison function. Specifically if KeypointGreater(KeyPoint1, KeyPoint2) returns true, KeypointGreater(KeyPoint2, KeyPoint1) should not (and vice versa).

Under windows (VS 2010) when performing the comparison if the comparison function returns true, it does a check to ensure that the inverse (KeypointGreater(KeyPoint2, KeyPoint1)) doesn't also return true, if it does (like in this case) it throws an error and the program crashes (not sure what happens under linux). This check is performed in \Visual Studio 10.0\VC\include\xutility line 665, this function is called from _Insertion_sort1 in \VC\include\algorithm which is called when std::sort is doing its thing.

xutility's _Debug_lt_pred does the following:

if (!_Pred(_Left, _Right))
    return (false);
else if (_Pred(_Right, _Left))
    _DEBUG_ERROR2("invalid operator<", _File, _Line);
return (true);

Where _Pred is surf's KeypointGreater function. Thus it errors after checking _Pred(_Right, _Left).

Of course this only happens if the two keypoints are identical bar the x value, which is the case for the two features extracted from this image.

Obviously its a bug in that the last line is comparing kp1.pt.x with kp2.pt.y, it should be "kp2.pt.x".
Additionally, presumably it shouldn't be returning true if kp1.pt.x is less than kp2.pt.x as when it compares the y values it only returns true if kp1.pt.y is greater than kp2.pt.y. Therefore the last line of that function should be (IMO):
return kp1.pt.x > kp2.pt.x;

This bug was found in the release version of 2.4.1, I checked the code in 2.4.2 and trunk and the KeypointGreater function is still the same so the bug still exists. I'll call this a patch as its a one line fix.

A unit test around this KeypointGreater function would catch this going forward :)
I'm new to the OpenCV framework so not up to speed on adding one myself.

Not sure who this should be assigned to, no doubt you will figure it out.

Let me know if you need any additional information,
Keep up the good work,
Jason