Why do we need multiple layers in each octave and multiple octaves in SIFT?

Question

I skimmed through the SIFT paper. I understand that there are multiple octaves, which are composed of multiple layers. The layer $k$ of an octave (btw, where does this name come from?) corresponds to the image filtered with a Gaussian kernel with a standard deviation of $k\sigma$, so layers higher in the octave correspond to more blurred versions of the original image. From these blurred images, you calculate the difference of Gaussians (DoG), from which you can compute the pixels that are locally higher (compare to a neighborhood around that pixel). The pixels that are locally higher than its neighbours are the potential keypoints. Once this is done, you can downsample the Gaussian-filtered images in the first octave to produce another octave, then you compute the DoGs again. This process can be repeated (for several iterations).

Intuitively, we apply the Gaussian kernel with a progressively higher standard deviation so that we can find keypoints at different scales (or resolutions), but why do we need to further downsample the Gaussian-filtered images in the first octave and repeat the process? Intuitively, this could still help to find keypoints at different resolutions (or scales), but I can't fully understand why would this approach be correct. So, why do we need multiple layers per octave and multiple octaves in SIFT?

Answer 1

As a starter, the 2014 IPOL paper Anatomy of the SIFT Method by Ives Rey Otero and Mauricio Delbracio provides a nice description and decryption of the SIFT method, with step-by-step pseudo-code, caveat and additional C code.

SIFT was meant to be robust to translation, rotation and scaling/zoom, and also to mild noise/blur, contrast variations. For this, the author build a discrete scale-space, to capture differently sampled versions of a continuous 3D scene. It is mostly indexed by two parameters:

• different inter-pixels distances, noted by $\delta$
• different scales, noted by $\sigma$

Their complementarity is depicted in this figure from the above paper:

Starting from the initial image, smoothed and resampled images are obtained (red dots) and additional images are added, notably to get differences (Differences of Gaussian) at all scales. The term octave derives from an interval split into 8 notes (octavus means "eighth" in Latin), separated by a factor of two (from the little I know in Western music). A factor of two is generally the simplest and smallest subsampling you can get from a discrete image, without resorting to interpolation. With the geometric blur inside an octave, a cascade of smoothing produces the correct preprocessing to allow subsampling.

Note, however, that this is higher level interpolation (zero-th root, maxima) in other steps to the SIFT.

To me, octaves emulate simple inter-pixel distance, while layers focus on the inherent scale of objects.

Answer 2

In music theory, an octave is an interval in frequency, from a frequency $f$ to frequency $2f$. For example "an octave higher" means "twice the frequency". Expressed as wavelength inversely proportional to frequency, $\lambda \propto \frac{1}{f}$, an octave would be the interval from a $\lambda$ to $\frac{1}{2}\lambda$. In the SIFT paper's notation, $\sigma$ is the scale, which is analogous to wavelength as it is proportional to the width of the Gaussian kernel.

Downsampling is just to reduce the image size so that there is less computation to do. From the paper (emphasis mine):

Once a complete octave has been processed, we resample the Gaussian image that has twice the initial value of $σ$ (it will be 2 images from the top of the stack) by taking every second pixel in each row and column. The accuracy of sampling relative to $σ$ is no different than for the start of the previous octave, while computation is greatly reduced.

What enables to do this? A Gaussian function has another Gaussian function as its Fourier transform, and that decays faster than can be counteracted by any differential operator such as the Laplace operator. A finite-amplitude low-pass signal filtered by a Gaussian or a Laplacian of Gaussian or its approximation of scale $\sigma$ has in an approximate sense a band limit that is proportional to $\frac{1}{\sigma}$. By increasing the constant of proportionality, the mean square power of the part of the signal that is above the band limit can be made arbitrarily small. This allows to resample the filtered signal with a sampling frequency proportional to $\frac{1}{\sigma}$ while keeping the aliasing error arbitrarily small. A convenient approach is to not sample every signal filtered at scale $\sigma$ by sampling frequency $\frac{\sigma_0}{\sigma}$ with $\sigma_0$ some reference scale that is sampled at sampling frequency $1$, but instead by sampling frequency $2^{\operatorname{ceiling}\left(\log_2(\frac{\sigma_0}{\sigma})\right)}$:

Figure 1. Sampling frequency (red) is the same for all frequencies within an octave. The drawback is that for some scales the sampling frequency is higher than the actual requirement (blue) for that scale. $\sigma$ is the scale and $\sigma_0$ is a reference scale.

This bunches together values of $\sigma$ into a number of octaves such that within each octave the sampling frequency is a power of 2, ensuring that the location of each spatial sample conveniently coincides with a spatial sample one octave higher. The drawback is that the sampling frequency for all scales in an an octave must be chosen based on the lowest scale included in the octave, to keep the aliasing noise within acceptable limits for that scale. The higher scales in the octave will typically have less aliasing.