Understanding Keypoints and ORB algorithm
A key point is a region of an image which is particularly distinct and identifies a unique feature
Key points are used to identify key regions of an object that are used as the base to later match and identify it in a new image. Image of the same object can be taken in varying conditions like the varying lighting conditions, angle, scale, and background. A good keypoint is one which is invariant to all these conditions.
Applications
Few applications are listed below
- Real-time face matching
- Object tracking
- Image contouring
- Images stitching
- Motion tracking in robotics
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(Oriented FAST and Rotated BRIEF) 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.
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
- Speeded-up Robust features(SURF)
- 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
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
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
Further Reference
- OpenCV ORB class reference
- OpenCV tutorial
- ORB implementation notebook ORB.ipynb from Udacity CVND nano degree
- Tutorial on keypoints imageMatching
Images used are referenced from CVND nano degree Udacity
