1D Minima and Maxima

Figure 1.9: Construction of the parabolic model and localization of the maximum with sub-pixel precision.

If the point under examination is the maximum or minimum of a one-dimensional sequence, its immediate neighborhood can be approximated by a quadratic function of equation $a x^2 + b x + c = y$. The quadratic is the lowest-degree function that permits the localization of local minima or maxima.

Let $y_{-1}$, $y_0$, and $y_{+1}$ therefore be the function values at offsets $-1$, $0$, and $+1$ from the minimum/maximum located with pixel-level precision. The equation of the quadratic passing through these three points takes the notable form

$$a = \frac{y_{+1} - 2 y_0 + y_{-1}}{2} \quad b = \frac{y_{+1} - y_{-1}}{2} \quad c = y_0$$ (1.131)

This curve has its notable maximum/minimum at

$$\hat{\delta}_x = -\frac{b}{2 a} = - \frac{y_{+1} - y_{-1}}{2 (y_{+1} - 2 y_0 + y_{-1} ) }$$ (1.132)

$\hat{\delta}_x$ is to be understood as the offset from the previously identified maximum/minimum, that is, it represents only its sub-pixel component.

This equation also provides another notable result: if $y_0$ is a local maximum/minimum, then by definition this value is always less/greater than both $y_{+1}$ and $y_{-1}$. From this observation, it follows easily that $\hat{\delta}_x$ always lies between $-1/2$ and $1/2$.

There is an alternative formulation: denoting by $\delta_{+}=y_{+1}-y_{0}$ and $\delta_{-}=y_{-1}-y_{0}$, the equation of the parabola becomes

$$a = \frac{\delta_{+} + \delta_{-}}{2} \quad b = \frac{\delta_{+} - \delta_{-}}{2}$$ (1.133)

and the minimum is located at

$$\hat{\delta}_x = - \frac{\delta_{+} - \delta_{-}}{2 (\delta_{+} + \delta_{-}) }$$ (1.134)

where it is clear that the position of the minimum is obviously independent of $y_0$ and depends only on the deltas.