Ask Your Question

Why is ORB algorithm border reflection necessary?

asked 2016-07-02 15:09:45 -0600

HesNotTheStig gravatar image

So I'm working on an implementation of OpenCV's ORB keypoint algorithm (not the descriptors, just keypoints). My implmentation produces key points VERY close to the original, but something's a bit off and I'm trying to find the problem. One thing that always puzzled me about the OpenCV implementation of the ORB algorithm is that as it is pre-computing the image pyramid, it feels to need to use the "copyMakeBorder" function to relect a mirror image of the border of the image around each level of the pyramid.

// Pre-compute the scale pyramids
for (level = 0; level < nLevels; ++level)
    Rect linfo = layerInfo[level];
    Size sz(linfo.width, linfo.height);
    Size wholeSize(sz.width + border*2, sz.height + border*2);
    Rect wholeLinfo = Rect(linfo.x - border, linfo.y - border, wholeSize.width, wholeSize.height);
    Mat extImg = imagePyramid(wholeLinfo), extMask;
    Mat currImg = extImg(Rect(border, border, sz.width, sz.height)), currMask;

    if( !mask.empty() )
        extMask = maskPyramid(wholeLinfo);
        currMask = extMask(Rect(border, border, sz.width, sz.height));

    // Compute the resized image
    if( level != firstLevel )
        resize(prevImg, currImg, sz, 0, 0, INTER_LINEAR);
        if( !mask.empty() )
            resize(prevMask, currMask, sz, 0, 0, INTER_LINEAR);
            if( level > firstLevel )
                threshold(currMask, currMask, 254, 0, THRESH_TOZERO);

        copyMakeBorder(currImg, extImg, border, border, border, border,
        if (!mask.empty())
            copyMakeBorder(currMask, extMask, border, border, border, border,
        copyMakeBorder(image, extImg, border, border, border, border,
        if( !mask.empty() )
            copyMakeBorder(mask, extMask, border, border, border, border,
    prevImg = currImg;
    prevMask = currMask;

Does this reflected border serve any purpose in terms of generating key points? I've studied the key point section carefully and as far as I can tell, it never gets used. Can I skip that part and save some CPU cycles?

(P.S.: If you're wondering, my implementation is going to be optimized for use on video key frames. In other words, I can calculate most of the buffers once per video since the resolution between frames remains the same. I can also play with background subtraction to restrict the mask to focus only on moving objects.)

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2016-07-26 20:41:57 -0600

HesNotTheStig gravatar image

I've been working on this. I don't know if the reflected border gets used at all in the descriptor's algorithm, but if you're only looking to produce key points (perhaps to feed into another algorithm's compute method), then it is entirely unnecessary to reflect this border.

I confirmed this by tweaking the code to reduce the border to zero and then comparing the keypoints generated. No difference. Perhaps an optimization could be put into place for this.

edit flag offensive delete link more



Are you up for a PR?

StevenPuttemans gravatar imageStevenPuttemans ( 2016-07-27 04:57:01 -0600 )edit

I'm just a tinkerer. I was simply playing with the algorithm and trying to see if I could use it for video. I can't attest to what performance improvement we would see from this. Before it makes it into the code, it should be independently confirmed that setting the border to zero makes no difference for key points.

In my tinkering process, I was also trying to see the cv::resize function could be refactored to reused offset buffers between frames of identical dimensions. Not seeing a performance improvement. No idea why.

On the other hand, my use a a streamlined background subtraction model means I can focus on moving elements in the video and improve descriptor quality without sacrificing much in performance.

HesNotTheStig gravatar imageHesNotTheStig ( 2016-08-02 18:23:23 -0600 )edit

Well the best way to get a critical opinion on your changes is to supply a PR, simply because a core library developer will visit the PR and start discussing it. They will happily reply to any open questions you have remaining!

StevenPuttemans gravatar imageStevenPuttemans ( 2016-08-03 03:15:04 -0600 )edit

Question Tools



Asked: 2016-07-02 15:09:45 -0600

Seen: 658 times

Last updated: Jul 26 '16