Descriptors

Another concept that cuts across several areas of computer vision is that of the descriptor (Visual Descriptor). A descriptor is used in several contexts: to compare feature points or generate a disparity map in stereo vision, to provide a compact representation of an image region so as to speed up its detection or retrieval, and, because this compact representation preserves much of the information, to generate the feature space for classification algorithms.

Depending on the transformation undergone by the image from which the points are to be characterized, the descriptor must satisfy several invariance principles:

translation

This is the simplest case and is handled automatically by the feature-point extractor;

scale

This transformation is also normally handled by the feature-point extractor;

brightness

Images may undergo changes in brightness;

rotation

Images may represent the same scene after rotation;

perspective

Changes in perspective deform the observed portion of the scene in a complex manner.

Before the concept of a compact descriptor was introduced, the standard method for comparing two feature points was correlation between the regions surrounding the points:

$$d(\mathbf{p}_1,\mathbf{p}_2)=\sum_{\boldsymbol\delta \in \O... ...\bar {I_1})(I_2(\mathbf{p}_2 + \boldsymbol\delta) - \bar{I_2})$$ (7.1)

where $\Omega$ is a fixed-size window centered on the point in the two images, and $\bar{I}_n$ is the mean image value within the window $\Omega$. $w_{\delta}$ is an optional weight (for example, a Gaussian) used to assign different contributions to pixels near to and far from the point. Correlation is invariant to changes in brightness but has a high computational cost. In this case, the descriptor is exactly the image region surrounding the detected point (Mor80). A correlation-like approach that is not invariant to brightness but is more computationally efficient is SAD (Sum of Absolute Differences):

$$d(\mathbf{p}_1,\mathbf{p}_2)=\sum_{\boldsymbol\delta \in \O... ...oldsymbol\delta) - I_2(\mathbf{p}_2 + \boldsymbol\delta) \vert$$ (7.2)

To make SAD invariant to brightness, comparisons are normally performed not on the original image but on the horizontal and vertical derivative images. This idea is very simple but can be generalized further by performing the comparison not on the original image, but between one or more images extracted using different kernels, which provide the descriptor with several levels of invariance.

It should also be noted that comparing pixels between images is still an algorithm of type $O(n^2)$: performing these comparisons for each point nevertheless requires substantial computational effort and numerous memory accesses. Modern approaches seek to overcome this limitation by extracting a descriptor from the point's neighborhood that is smaller than the number of pixels represented while maximizing the information it contains.

Both SIFT (Section 6.3) and SURF (Section 6.4) extract their descriptors by exploiting scale and rotation information obtained from the image (these properties can also be extracted independently, and therefore applied to any class of descriptor to make it invariant to scale and rotation). The descriptors obtained from SIFT and SURF are different versions of the same concept: the histogram of gradient orientations (Section 7.2), an example of how to compress the variability around a point into a lower-dimensional space.

None of the descriptors currently in use directly uses the image pixels as the descriptor; however, it is easy to see that a sufficiently well-distributed subset of the pixels is enough to produce an accurate description of the point. In (RD05), a descriptor is created from the 16 pixels located along the discrete circle of radius 3. This description can be made even more compact by converting it to the binary form of the Local Binary Pattern described below, or by using a form not constrained to the circle, as in Census or BRIEF. Another approach is to sample the kernel space appropriately (GZS11), extracting from $m$ coordinates around the keypoint the values produced by convolutions of the original image (horizontal and vertical Sobel filters), thereby creating a descriptor with only $2m$ values.

It should be noted that, for purely computational reasons related to resource reuse, a specific descriptor extractor is often associated with each feature-point extractor.

This introduction makes it clear that describing a keypoint using fewer data while retaining sufficient descriptive power is also useful in classification. The concept of a descriptor arose from the attempt to extract local image information while preserving a substantial part of the original information. This makes it possible to perform relatively fast comparisons between points in images or to use such descriptors as features on which to train classifiers.