A Unified B-Spline Framework for Scale-Invariant Keypoint Detection

Abstract

Scale-invariant keypoint detection is a fundamental problem in low-level vision. To accelerate keypoint detectors (e.g. DoG, Harris-Laplace, Hessian-Laplace) that are developed in Gaussian scale-space, various fast detectors (e.g., SURF, CenSurE, and BRISK) have been developed by approximating Gaussian filters with simple box filters. However, there is no principled way to design the shape and scale of the box filters. Additionally, the involved integral image technique makes it difficult to figure out the continuous kernels that correspond to the discrete ones used in these detectors, so there is no guarantee that those good properties such as causality in the original Gaussian space can be inherited. To address these issues, in this paper, we propose a unified B-spline framework for scale-invariant keypoint detection. Owing to an approximate relationship to Gaussian kernels, the B-spline framework provides a mathematical interpretation of existing fast detectors based on integral images. In addition, from B-spline theories, we illustrate the problem in repeated integration, which is the generalized version of the integral image technique. Finally, following the dominant measures for keypoint detection and automatic scale selection, we develop B-spline determinant of Hessian (B-DoH) and B-spline Laplacian-of-Gaussian (B-LoG) as two instantiations within the unified B-spline framework. For efficient computation, we propose to use repeated running-sums to convolve images with B-spline kernels with fixed orders, which avoids the problem of integral images by introducing an extra interpolation kernel. Our B-spline detectors can be designed in a principled way without the heuristic choice of kernel shape and scales and naturally extend the popular SURF and CenSurE detectors with more complex kernels. Extensive experiments on the benchmark dataset demonstrate that the proposed detectors outperform the others in terms of repeatability and efficiency.

Appendices

Appendix A: Proof of Proposition 1

Proof

It is obvious that the first derivative of the scaled $zero^{th}$ order B-spline $\varphi ^0_s(x)$ is $\varDelta _s(x+\frac{s}{2})$. Using (2), the scaled B-spline of degree n can be expressed as

$$\begin{aligned} \varphi _s^n(x)=\underbrace{\varphi _s^0*\varphi _s^0*\ldots *\varphi _s^0(x)}_{n+1\ times}. \end{aligned}$$

(36)

Thus, the $(n+1)^{th}$ derivative of $\varphi ^n_s(x)$ can be calculated using (36), i.e.,

$$\begin{aligned} D^{n+1}\varphi _s^n(x)&= \underbrace{\left( D\varphi _s^0\right) *\left( D\varphi _s^0\right) *\ldots *\left( D\varphi _s^0\right) (x)}_{n+1\ times} \nonumber \\&= \underbrace{\left( \varDelta _s\left( \cdot +\frac{s}{2}\right) \right) *\left( \varDelta _s\left( \cdot +\frac{s}{2}\right) \right) *\ldots *\left( \varDelta _s\left( \cdot +\frac{s}{2}\right) \right) (x)}_{n+1\ times}\nonumber \\&= \varDelta _s^{n+1}\left( x+s\frac{n+1}{2}\right) , \end{aligned}$$

(37)

where $D^{n+1}$ is the $(n+1)$-fold iteration of the differential operator $Df(x)=\frac{\partial {f(x)}}{\partial {x}}$. Finally, using (37)

$$\begin{aligned} f*\varphi _{s,d}^n(x)&= \left( D^{-(n+1-d)}f\right) *\left( D^{n+1-d}\varphi _{s,d}^n\right) (x)\nonumber \\&= \left( D^{-(n+1-d)}f\right) *\left( D^{n+1}\varphi _s^n\right) (x)\nonumber \\&= \left( D^{-(n+1-d)}f\right) *\varDelta _s^{n+1}\left( x+s\frac{n+1}{2}\right) . \end{aligned}$$

(38)

$\square$

Appendix B: Proof of Theorem 1

Proof

Using (6), the $(n+1)^{th}$ finite difference of the discrete B-spline $\phi _s^n(k)$ can be calculated as

$$\begin{aligned} \varDelta ^{n+1}\phi _s^n(k)&= \underbrace{\left( \varDelta \phi _s^0\right) *\left( \varDelta \phi _s^0\right) *\ldots *\left( \varDelta \phi _s^0\right) }_{n+1\ times}(k)\nonumber \\&= \underbrace{\varDelta _s*\varDelta _s*\ldots *\varDelta _s\left( k+\bigg \lfloor \frac{(s-1)(n+1)}{2}\bigg \rfloor \right) }_{n+1\ times}\nonumber \\&= \varDelta _s^{n+1}\left( k+\bigg \lfloor \gamma \bigg \rfloor \right) . \end{aligned}$$

(39)

Replacing $D^{-(n+1-d)}$ with the $(n+1-d)$-fold iteration of the running-sum operator $\varDelta ^{-(n+1-d)}$, (21) is reformulated as

$$\begin{aligned}&f*h(k)=\left( \varDelta ^{-(n+1-d)}*f\right) *\varDelta _s^{n+1}\left( k+\lfloor \gamma ^{'}\rfloor \right) \nonumber \\&\quad = f*\varDelta ^d*\left( \varDelta ^{-(n+1)}*\varDelta _s^{n+1}\left( \cdot +\lfloor \gamma \rfloor \right) \right) \left( k+\bigg \lfloor \gamma ^{'}\bigg \rfloor -\bigg \lfloor \gamma \bigg \rfloor \right) \nonumber \\&\quad = f*\varDelta ^d*\phi _{s}^n\left( k+\bigg \lfloor \gamma ^{'}\bigg \rfloor -\bigg \lfloor \gamma \rfloor \right) \qquad using~(39)\nonumber \\&\quad = f*\phi _{s,d}^n(k) \qquad using~(10). \end{aligned}$$

(40)

$\square$

Appendix C: Proof of Proposition 2

Proof

From (9), we can establish the relation between $\varphi _{s,d}^n(k)$ and $\phi _{s,d}^n(k)$:

$$\begin{aligned} \varphi _{s,d}^n(k) = \phi _{s,d}^n*\varphi ^{n-d}\left( k+\{\gamma ^{'}\}\right) . \end{aligned}$$

(41)

Similar to the idea of repeated integration, the results remain unchanged if the finite difference operator $\varDelta$ is applied to the kernel and running-sum operator $\varDelta ^{-1}$ is applied to the original signal, i.e.,

$$\begin{aligned} Wf(s,k)&=f*\varphi _{s,d}^n(k) \nonumber \\&=\left( \varDelta ^{-(n+1-d)}f\right) *\left( \varDelta ^{n+1-d}\varphi _{s,d}^n\right) (k)\nonumber \\&=\left( \varDelta ^{-(n+1-d)}f\right) *\varphi ^{n-d}\left( \cdot +\{\gamma ^{'}\}\right) \left( \varDelta ^{n+1-d}\phi _{s,d}^n\right) (k) \nonumber \\&=\left( \varDelta ^{-(n+1-d)}f\right) *\varphi ^{n-d}\left( \cdot +\{\gamma ^{'}\}\right) \nonumber \\&\quad \left( \varDelta ^{n+1}\phi _{s}^n\right) \left( k+\bigg \lfloor \gamma ^{'}\bigg \rfloor -\bigg \lfloor \gamma \bigg \rfloor \right) \nonumber \\&=\left( \varDelta ^{-(n+1-d)}f\right) *\varphi ^{n-d}\left( \cdot +\{\gamma ^{'}\}\right) *\varDelta _s^{n+1}\left( k+\lfloor \gamma ^{'}\rfloor \right) , \end{aligned}$$

(42)

where the third equation derives using (41), and the last equation derives using (39). $\square$