Feature Detection and Matching

Types of features:

• Keypoint - A single point, or a region of pixels surrounding a point.
• Edges - A line segment indicating a visual boundary.

Each keypoints is typically either a:

• Corner - the point of intersection of two or more edges; or
• Blob (patch) - a pattern differing from its immediate neighbourhood in terms of colour and intensity.

Feature matching - independently finding features in all images, then match individual features between images Feature tracking - finding features in one image, then tracking them across other images in similar regions.

Feature Detection Algorithms §

FAST Feature Detection §

A common method for corner detection is the Features from Accelerated Segment Test (FAST) algorithm. The FAST algorithm returns that a given pixel $p$ in an image is a keypoint at a threshold $t$ if and only if there exists a set of $n$ contiguous pixels in a $16$-pixel circle surrounding $p$ which are all either brighter than $I_p+t$ or dimmer than $I_p-t$, where $I_p$ is the intensity of $p$.

Scale Invariant Feature Transform §

xyz

Feature Description §

Once a set of features has been detected, the region around each feature is converted into a compact descriptor which can then be matched against other descriptors. A very simple descriptor may be based on the intensity of pixels in the region surrounding a feature. Standard error metrics such as the sum of squared differences can then be used to compare intensities. This method of feature description is not invariant to scale and orientation.

SIFT Descriptors §

The Scale Invariant Feature Transform (SIFT) Descriptor considers a $16\times 16$ pixel patch surrounding a feature. The orientation and magnitude of the gradient of intensity is calculated at each pixel in the patch. An eight-bin (cardinal+ordinal directions) histogram is computed for each $4\times 4$ sub-region in the patch. This leads to a $16\times 8$, or $128$-value array.

Feature matching strategies §

Matching strategies:

Distance thresholding §

The euclidean distance between two vectors of $n$ dimensions is defined as:

$$d(p,q)=\sqrt{\sum _{i=1}^n(p_i-q_i{)}^2}$$

We determine two features $p$ and $q$ to be a match if $d(p,q)<t$ for some defined threshold $t$.

Nearest Neighbour §

A distance function is used to compute the distance between possible matches, and the single closest feature (nearest neighbour) is determined to be the match.

Nearest Neighbour Distance Ratio (NNDR) §

The nearest neighbour for each feature is computed as above. However, any matches failing to meet the distance ratio test are removed. The distance ratio is defined as

$$\frac{d_1}{d_2}$$

where $d_1$ is the distance between the target descriptor and its nearest neighbour, and $d_2$ is the distance between the target descriptor and its 2nd nearest neighbour. Only matches for which $\frac{d_1}{d_2}<t$ (for a given threshold $t$) are accepted.

Evaluating matching strategies §

For a set of potential matches, correctly labelled as matches or not, we can evaluate a matching algorithm on these. We can determine the number of true positives (TP), true negatives (TN), false positives (FP) and false negatives (FN). We define

• Precision as $\frac{TP}{TP+FP}$,
• Recall as $\frac{TP}{TP+FN}$. Precision is sometimes also called positive predictive value (PPV).

The F1-score is the harmonic mean of precision and recall:

$$F1=\frac{2PR}{P+R}$$

We can also calculate rates for each category:

• True positive rate $\mathrm{TPR}=\frac{TP}{TP+FN}$
• False positive rate $\mathrm{FPR}=\frac{FP}{FP+TN}$
• True negative rate $\mathrm{TNR}=\frac{TN}{TN+FP}$
• False negative rate $\mathrm{FNR}=\frac{FN}{FN+TP}$