why is FAST/ORB bad at finding keypoints near the edge of an image

Question

ORB doesn't find keypoints near the edge of an image and I don't understand why. It seems worse that SIFT and SURF and I would expect the opposite.

If I understand correctly then SIFT/SURF use a 16x16 and 20x20 square block respectedly around the test-point so I would expect them not to find keypoints 8 and 10 pixels from an edge. FAST/ORB uses a circle of diameter 7 around the test-point so I expected it to find keypoints even closer to the edge, perhaps as close as 4 pixels (though I think the associated algorithm, BRIEF, to describe keypoints uses a larger window so this would remove some keypoints).

An experiment makes nonsense of my prediction. The minimum distance from the edge in my experiments vary with the size and spacing of the squares but examples are

• SIFT .. 5 pixels
• SURF .. 15 pixels
• ORB .. 39 pixels

Can anyone explain why?

The code I used is below. I drew a grid of squares and applied a Gaussian blur. I expected the algorithms to latch onto the corners but they found the centres of the squares and some artifacts.

import numpy as np
import cv2

size = 501; border = 51; step = 10
image = np.zeros( (size,size), np.uint8 )
# fill with disjoint squares
def drawsquare(img,i,j):
    restsize = step//5
    cv2.rectangle(img,(i-restsize,j-restsize),(i+restsize,j+restsize),255,-1)
for i in range(0,size,step):
    for j in range(0,size,step):
        drawsquare(image,i,j)
# blank out the middle
image[border:size-border,border:size-border] = 0
# and blur
image = cv2.GaussianBlur(image,(5,5),0)
imgcopy = image.copy()

descriptor = cv2.xfeatures2d.SIFT_create(nfeatures=2000)
kps = descriptor.detect(image)
minpt = min([p for k in kps for p in k.pt ])
print("#{} SIFT keypoints, min coord is {} ".format(len(kps),minpt))
imgcopy = cv2.drawKeypoints(imgcopy,kps,imgcopy,(0,0,255))
cv2.imshow( "SIFT(red)", imgcopy )
cv2.waitKey()

descriptor = cv2.xfeatures2d.SURF_create()
kps, descs = descriptor.detectAndCompute(image,None)
minpt = min([p for k in kps for p in k.pt ])
print("#{} SURF keypoints , min coord is {}".format(len(kps),minpt))
imgcopy = cv2.drawKeypoints(imgcopy,kps,imgcopy,(0,255,255))
cv2.imshow( "SIFT(red)+SURF(yellow)", imgcopy )
cv2.waitKey()

descriptor = cv2.ORB_create(nfeatures=800)
kps = descriptor.detect(image)
minpt = min([p for k in kps for p in k.pt ])
print("#{} ORB keypoints, min coord is {} ".format(len(kps),minpt))
imgcopy = cv2.drawKeypoints(imgcopy,kps,imgcopy,(0,255,0))
cv2.imshow( "SIFT(red)+SURF(yellow)+ORB-detect(green)", imgcopy )
cv2.waitKey()
kps, descs = descriptor.compute(image,kps)
minpt = min([k.pt[0] for k in kps]+[k.pt[1] for k in kps])
print("#{} ORB described keypoints, min coord is {} ".format(len(kps),minpt))
imgcopy = cv2.drawKeypoints(imgcopy,kps,imgcopy,(255,0,0))
cv2.imshow( "SIFT(red)+SURF(yelow)+ORB-compute(blue)", imgcopy )
cv2.waitKey()


cv2.imwrite("/tmp/grid-with-keypoints.png",imgcopy)

Output of program is

#2000 SIFT keypoints, min coord is 5.140756607055664 
#1780 SURF keypoints , min coord is 15.0
#592 ORB keypoints, min coord is 39.60000228881836 
#592 ORB described keypoints, min coord is 39.60000228881836 

and the image is

Addendum

Grillteller answered my question and gave me an extra parameter in the creation-code for an ORB detector. If I write

descriptor = cv2.ORB_create(nfeatures=800,edgeThreshold=0)

then I get output

#950 ORB keypoints, min coord is 9.953282356262207 

Answer 1

Usually, keypoints at the edge of the image are not useful for most applications. Consider e.g. a moving car or a plane for aerial images. Points at the image border are often not visible in the following frame. When calculating 3D reconstructions of objects most of the time the object of interest lies in the center of the image. Also the fact you mentioned, that most feature detectors work with areas of interest around pixels is important since these regions could give unwanted effects at the image border.

Going into the source code of OpenCV ORB (848-849) uses a function with an edgeThreshold that can be defined using cv::ORB::create() and is set to a default value of 31 pixels. "This is size of the border where the features are not detected. It should roughly match the patchSize parameter."

// Remove keypoints very close to the border
KeyPointsFilter::runByImageBorder(keypoints, img.size(), edgeThreshold);

The function is defined as:

void KeyPointsFilter::runByImageBorder( std::vector<KeyPoint>& keypoints, Size imageSize, int borderSize )
{
    if( borderSize > 0)
    {
        if (imageSize.height <= borderSize * 2 || imageSize.width <= borderSize * 2)
            keypoints.clear();
        else
            keypoints.erase( std::remove_if(keypoints.begin(), keypoints.end(),
                                       RoiPredicate(Rect(Point(borderSize, borderSize),
                                                         Point(imageSize.width - borderSize, imageSize.height - borderSize)))),
                             keypoints.end() );
    }
}

and removes keypoints close to the edge using keypoints.erase().

For SIFT the relevant line (92-93) can be found here:

// width of border in which to ignore keypoints 
static const int SIFT_IMG_BORDER = 5;

I assume that SURF uses a similar parameter (=15?) but as far as I know these parameters in SIFT and SURF can not simply be changed in a function call like for ORB.