FAST corner detector

Segment-Test + Decision Tree

According to the paper, real-time video tracking (augmented reality) is the primary goal of devising FAST.
The method involves training a decision tree with attribute vector of 16 elements. Each one is a point around a circle. The center of the circle is the candidate feature-point (corner). The candidate is classified as a 'corner' or 'non-corner' with the resulting tree.

• Segment-Test: Put a Bresenham circle, of 3-pixel-radius (r=3), around our study point. There will be 16 perimeter pixels. The study point is a corner if there are 12 (N=12) consecutive pixels from the perimeter that are consistently brighter than the center (study pixel) by a threshold 't'. This case is dark-in-center. It would also count if those N pixels are darker than the center (bright-in-center).
• Classify all the training images by finding out all the corner points using Segment-Test.
• Build the decision tree in two phases
• Choose an attribute, let's say pixel-5 from the perimeter. Classify the current center as either 'Brighter', 'Similar' or 'Darker' with respect to this point. Repeat this for all pixels as center. At the end of this round, the pixels will be divided into 3 groups. Brighter, Similar or Darker. 
• The choice of pixel-5 is based on that fact that it would reduce the most entropy (highest information gain). That would like to introduce the most uneven split of classifications going into the next level. This is ID3 Decision Tree. Each node is split 3-ways. There are 2 classifications (corner - yes , no).
• Repeat the above with other perimeter pixels to grow the decision tree until all the leave nodes have 100% yes-no corner (entropy of 0).
• Apply non-maxima suppression to detected corners to eliminate overlapping features. Compare absolute sum of the intensity-difference from the circle to find the the local maxima.
• The Rosten paper suggests that it takes on average 2.2 questions (tree-level?) to classified a point.

It is able to generalize the 'corner' with this supervised learning method.

Code

• Probably need a DetectorParam struct to group together separate 'threshold' and 'nonMaxSuppression' argument.

Sample

• The FAST implementation in OpenCV performs a 9-point segment test. It is not a learned method. Meaning that it does not build a decision tree. It uses Segment Test only.
• It's very fast even with the large Obama picture, taking less than 1 second to detect 5000+ corners.
• Using default threshold (intensity-difference), it detects 4 times as much corners as SURF.
• Higher threshold, fewer detected points and vice-versa.

Readings

• Machine learning for high-speed corner detection, Edward Rosten and Tom Drummond
• (see resources)

Resources

• Edward Rosten Page: http://mi.eng.cam.ac.uk/~er258/work/fast.html.
  A few iPhone projects is using FAST.
  Edward has submitted a newer and FAST-er method.
• On ID3 Decision Tree http://www.cse.unsw.edu.au/~billw/cs9414/notes/ml/06prop/id3/id3.html

SURF Detector

FAST-Hessian Detector + SURF Descriptor

Key Point Detection

• Build Integral Image
• Uses Pyramid of Filter (not image) to approximate Laplace of Gaussian (LoG), supposedly run faster than SIFT, which uses DoG for approximation.
• Filters will span several octaves and with fixed number of scales in each, similar to SIFT. This type of process is Scale-Space Analysis.
• Integral image helps to keep the running speed constant as it is insensitive to increasing filter sizes.
• Uses discrete Box Filter to calculate Hessian determinant. Box size in multiples of its current scale.
• All filters run on the the original image instead of iterative like SIFT, allowing parallel execution.
• Feature points are maxima of the determinants in the adjacent scale and points (3x3x3), similar to SIFT.

Orientation Assignment

• The responses from 2 first-order Haar wavelet filters (1, -1), in dx and dy orientations, are collected on each feature point. The responses are put on a 2D plane as vectors [dx, dy].
• Again, the Integral Image would help with this box filter.
• An orientation-window of 60-degree-angle is slided around the origin at x-y plane.  Each angle will have a corresponding sum of magnitudes for every vectors inside that window.
• The dominant orientation would be the angle of the largest sum.

Descriptor Extraction

• The descriptor is 64-element vector, half the size of SIFT. Each represents the intensity property of a 4x4 square within the "interest region". The intensity property is 4-element tuple [ Sum(dx), Sum(abs(dx)),  Sum(dy),  Sum(abs(dy)) ]. The Sum is calculated from the Haar wavelet response of a 5x5 sample window.
• 4x4x4 = 64
• Implying that there are more than 1 4x4 square at each key-point location. I suppose the size of the region is related to the associated scale.

Matching

• The sign (+ive/-ive) of the Trace of Laplacian (Hessian Matrix) is used in matching phase, speeding up the process.

Code

• It is credited to Liu Liu with modifications by Ian Mahon. The authors state the current gotchas and gives a good overview of the code at the file (surf.cpp) header.
• The code did try to exploit parallelism using OpenMP (cv::parallel_for).
• Define some parameter structure and default values similar SIFT in the future (start with cvSURFParams?).
• The 'extended' parameter changes the descriptor size from 64 to 128. It is default to '1' in the code, but it has default argument value of 'false' at the SURF::SURF(...) constructor.
• Why not integrate OpenSURF by Chris Evans? (With hyperlink to CMU CV site with Image Databases and other CV resources).

Sample

• With default parameters, SIFT takes 3-4 seconds and detect 872 points on Kobe Bryants picture. SURF takes less than 1 second to detect 413 points.
• SURF is able to handle the Obama picture at its original resolution, unlike SIFT. Takes 11 seconds to detect 2690 points.
• Decrease/Increase the number of detected points by increasing/lowering the threshold argument. Only the points with Hessian response higher than thresholds are considered.

Commercial Application (academic spin-off)

• Kooaba - visual search

Readings

• Speeded-Up Robust Features (SURF). Herbert Bay et al.
• CPSC 643 Presentation of SURF, Herbert Bay et al.
• Non-Maxima Suppression Demo
• Wavelets in Multiresolution Analysis by Tom Germano
• A Tutorial on Wavelets and their Applications by Martin J. Mohlenkamp at the University of Colorado, Boulder
• WAVELETS FOR KIDS - A Tutorial Introduction by B. Vidakovic, P. Mueller at Duke University.
• Wavelets: A Tutorial by Zhuming Lam (Apr-2002)

Repeatability

• The term 'repeatability' (seen on SIFT and SURF papers) is a measure of the ability to detect the same set of key-point from various viewpoints. For example, the rotation of Van Gogh image (Fig 3 of the SURF paper by Bay et al.).
• Origin of this term: See "Evaluation of Interest Point Detectors" paper by Shmid et al

Edge Detection introductions

Came across some decent introductory materials on edge detection.

• www.cfar.umd.edu/~fer/cmsc426/lectures/edge1.ppt 
• Lecture 7 - Basic Algorithms for Digital Image Analysis by Dmitrij Csetverikov of Eotvos Lorand University

SIFT

Attempt to summarize the feature point detection method:

• Locate key-points
• Find candidate key-points with a Pyramid of DoG from several octaves (1 octave = rho x 2).
• Calculate precise locations of key-points
• Remove candidates on edges or low-contrast area
• Assign orientation to each key-point. Create new key-points at the same location, scale which have similar and significant orientations.
• Now each key-point has location, scale, orientation information.
• Define descriptor for each key-point
• Each sample point now has a gradient magnitude and orientation from previous steps.
• For each key-point, make orientation histogram for its neighborhood 4x4 regions.
• The histogram bins (r) width is 360 / r. If r = 8, width = 40.
• Value of each bin is the sum of gradient magnitudes in that orientation, weighted inversely to the distance from the key-point.
• The orientation is specified relative to the feature point orientation.
• The n-by-n neighborhood could be 4x4 as used [ Lowe2004]. 
• Number of elements for each descriptor is now r times n times n. 8 x 4 x 4 = 128.

** Works for single color channel images only **

Code

• Part of VLFEAT implementation by Andrea Vedaldi: http://www.vlfeat.org/api/index.html
• KeyPoint::size is a function of Sigma where Sigma corresponds to the scale of that key-point. Given DrawMatchesFlags::DRAW_RICH_KEYPOINTS flag, drawKeyPoints()  will draw a circle centering at the feature point location. The KeyPoint::size is used to determine that diameter.

Sample

• Fewer results (keypoints) by increasing the contrast threshold and decrease the edge threshold (difference between biggest 2 gradients).
• Background aside, feature points mostly located around the eyes, eyebrows, where the hair-lines meet the face, hair (brunette), lips, teeth, cheek, nose-tip from looking straight.
• Fewer points when the face turns a little to one side, with half of the face is shaded. In this case, the default thresholds give better results.
• Works fine with Obama portrait. Although, the original sized picture (1916x2608) is causing memory failure at Sift::prepareBuffers().

Readings

• Local Features Tutorial Nov 8 2004, F. Estrada & A. Jepson & D. Fleet
• CS 664 Lecture #21 "SIFT, object recognition, dynamic programming", Cornell University
• Distinctive Image Feature from Scale-Invariant Keypoints, David Lowe 2004
• Implementing the Scale Invariant Feature Transform(SIFT) Method, YU MENG, Dr. B Tidderman

Corner Detection

GoodFeatureToTrack

• Default use Shi-Tomasi 94 method ("Texturedness" section): Store per-pixel 2 eigenvalues of a 2x2 matrix. It's a corner if both values above some threshold.
• Option to use Harris method: Store Corner and Edge Response value for each pixel. It is a corner if the value is a local maxima of the surroundings (8-connected).

* Only works for single channel images *

GFTT sample (my own)

•  Shi-Tomasi method return more keyPoints than Harris. Decrease the 'k' parameter increase the number of keyPoints detected, but still no match for Shi-Tomasi.
• Increase the 'k' parameter to 0.3 detects no keyPoints, using stanley.png and person2.bmp.
• Pass 'HARRIS' to FeatureDetector::create() to get Harris corner method
• Perhaps make a generic feature param class that FeatureDetector::create() would accept.
• Cannot detect any points on human face except teeth and eye-glasses, using person1.jpg and person2.bmp.

Readings

• Good Features to Track, Shi, Tomasi
• A combined corner and edge detector, Chris Harris & Mike Stephens (1988)

GrabCut

GrabCut is an iterative process that in cutting out foreground object after user specify the approximate region(rectangle) surrounding it. It uses K components of Gaussian Mixture Models to model the color of foreground and background pixels separately. The Graph-Cut technique is used to classify pixels as background / foreground. The factors affecting the classification is the neighborhood color gradients and fitness into existing GMM foreground/background models. The iteration begins with updating the 2K GMMs from the newly classified pixels (Learning), followed by detecting the foreground pixels with Graph Cut.

Sample

• OpenCV supports 4 types of classifications: BG, FG, Likely-BG and Likely-FG in user-edit mode.
• FG pixels are classified by GrabCut as Likely-FG, not FG (by experiment).
• Require manual iteration to observe convergence.
• It looks like the iterations are trying to make better GMMs (scissors.jpg).
• person1.jpg takes 5 seconds on each iteration; after 6 iterations there is no much improvements.
• Hard to get the narrow 'stem' classified as FG after putting a rectangle around the plant (besides the pot) from bush.jpg. Is it because the relatively small area to accummulate a significant weight in GMMs?

Readings

• "GrabCut" - Interactive Foreground Extraction using Iterated Graph Cuts
• Implementing GrabCut
• Image segmentation using GrabCut

Berkeley Image Database (CalPhoto)

Downloaded Ground truth photos for grabcut sample. Could be a source for test images, well, mostly about nature (classified with various plants, animal species). Permission must be granted from the owner even for storing it on a computer.