Understanding Keypoints and ORB algorithm

Source: Deep Learning on Medium

Keypoint in detail

A keypoint is calculated by considering an area of certain pixel intensities around it. Keypoints are calculated using various different algorithms, ORB technique uses the FAST algorithm to calculate the keypoints. FAST stands for Features from Accelerated Segments Test. FAST calculates keypoints by considering pixel brightness around a given area. Consider a pixel area in an image and lets test if a sample pixel p becomes a keypoint

Image representing keypoint pixel p and the circular area around it

Considering an area of 16 pixels around the pixel p. In the image, the intensity of pixel p is represented as ip and predefined threshold as h. A pixel is brighter if the brightness of it is higher than ip+h and it is of lower brightness if its brightness falls lower than ip-h and the pixel is considered the same brightness if its brightness is in the range ip+h and ip-h.

FAST decides the point p as keypoint if at least 8 pixels have higher brightness than the pixel p in 16 pixels intensities marked in a circle around it or the same result can be achieved by comparing 4 equidistant pixels on the circle i.e., pixels 1,5,9 and 13. This reduces the time taken to calculate keypoints by 4 times

Keypoints provide us the locations where the pixel intensities are varying. We get the prominent corners of an object from which we can identify an object from opposed to any other object in an image.

We can see that keypoints are present around the eyes, lips and nose. we can use the keypoint and its surround pixel area to create a numerical feature that can be called a feature descriptor. ORB uses the BRIEF algorithm which stands for Binary Robust Independent Elementary Features. Consider reading OpenCV page for more details

To achieve the scale invariance ORB constructs an image pyramid with different versions of the same image by scaling it to different levels

By calculating keypoints on different scales of the same object, ORB effectively calculates the object features at different scales and ORB assigns an orientation for each image based on the direction of the image gradients. This effectively works when an object is presented with different scales or orientations

Alternate algorithms

  1. Speeded-up Robust features(SURF)
  2. Scale Invariant Feature Transform(SIFT)

Using ORB to detect keypoints

We can use the ORB class in the OpenCV library to detect the keypoints and compute the feature descriptors. First keypoints are identified and then it computes binary feature vectors and groups them all in ORB descriptor. we shall consider a sample image shown below to detect the key points

sample face image to detect key points
Python OpenCV implementation of detecting keypoints using ORB

It’s a good idea that we normalize the image using the standard normalization techniques and then convert it to grayscale and pass it to ORB class for keypoint detection. The output obtained is shown below

Image with keypoints
image with key points identified at different scales

ORB is a good alternative to the SURF and the SIFT algorithms.

Playing with the ORB

Once you have the keypoints and ORB descriptor try matching it with some test images by scaling, Rotating and increasing the brightness of the image and by adding the random noise.

I observed that ORB is clearly able to recognize the face with all the conditions applied