KPB-SIFT: a compact local feature descriptor

Gangqiang Zhao, Ling Chen, Gencai Chen, Junsong YuanACM Multimedia 2010 · DOI

TL;DR

This paper introduces KPB-SIFT, a novel, compact local feature descriptor that achieves competitive performance with state-of-the-art methods like SIFT while being significantly smaller in dimensionality. By employing Walsh-Hadamard kernel projections on orientation gradient patches, KPB-SIFT offers improved speed and scalability for applications like object recognition and image retrieval, without requiring a pre-training phase.

What Problem Does This Paper Address?

Local feature descriptors are crucial for tasks like object recognition, image matching, and registration. While descriptors like SIFT are robust, their high dimensionality (e.g., 128 dimensions for SIFT) poses significant challenges for speed and scalability, especially in large-scale applications involving millions of features. Existing methods to reduce dimensionality, such as PCA-SIFT, often require a computationally expensive pre-training step. This paper aims to address this by proposing a compact descriptor that maintains high distinctiveness and invariance properties without the need for pre-training.

Methods

The proposed KPB-SIFT descriptor builds upon the established SIFT framework for detecting interest points. The core innovation lies in how the feature descriptor itself is constructed. Instead of SIFT's smoothed weighted histograms, KPB-SIFT utilizes kernel projection techniques on orientation gradient patches.

Here's a breakdown of the key steps:

  1. Invariant Feature Detection: The paper adopts the standard SIFT approach for detecting interest points, which involves scale-space peak selection, keypoint localization, and orientation assignment to achieve rotation invariance.
  2. Canonical Patch Construction: Local image patches are extracted around detected keypoints and then transformed into a canonical view by aligning them to the dominant orientation and resizing them to a fixed size (e.g., 32x32 pixels, a power of 2).
  3. Orientation Gradient Patches: For each canonical patch, four orientation gradient patches are computed (horizontal, π/4, vertical, 3π/4). These are then weighted by a Gaussian kernel to emphasize central gradient information.
  4. Kernel Projection: The crucial step is projecting these orientation gradient patches using a Walsh-Hadamard kernel. This kernel is chosen for its efficiency and good discrimination properties. The first few projection vectors are used to create a compact representation. Specifically, the paper uses the first 12 projection values from horizontal and vertical gradients, and the first 6 from the diagonal gradients, resulting in a 36-dimension descriptor.
  5. Normalization: The final descriptor is normalized to unit length to ensure contrast invariance.

The key novelty is the application of Walsh-Hadamard kernel projections to orientation gradient patches, which bypasses the need for pre-training required by PCA-based methods and results in a significantly more compact descriptor.

Datasets

The paper evaluates KPB-SIFT using two main types of datasets:

  • Synthesized Data: Images were subjected to various geometric (rotation, scaling, shearing) and photometric (lighting changes, noise) transformations. This allows for controlled evaluation of the descriptor's robustness.
  • Standard INRIA Dataset: This dataset is specifically designed for evaluating local feature descriptors and contains images with known geometric and photometric transformations, along with ground truth parameters.

The paper does not introduce new datasets but rather uses existing ones to benchmark KPB-SIFT against other descriptors.

Key Insights and Ideas

  • Kernel Projections for Compactness: The paper demonstrates that kernel projection techniques, specifically Walsh-Hadamard kernels, are highly effective for creating compact yet discriminative feature descriptors. This offers a viable alternative to dimensionality reduction methods like PCA that require pre-training.
  • Walsh-Hadamard Kernel Efficiency: The choice of Walsh-Hadamard kernel is justified by its computational efficiency (requiring only additions and subtractions) and its ability to capture significant image information with a small number of projection vectors.
  • Trade-off Between Dimensionality and Performance: KPB-SIFT shows that a significant reduction in descriptor dimensionality (from 128 for SIFT to 36) does not necessarily lead to a proportional drop in performance, and in some cases, can even lead to improvements in speed and scalability.
  • No Pre-training Required: A major advantage highlighted is that KPB-SIFT does not need an offline training phase, making it more readily applicable in scenarios where training data might be scarce or computational resources are limited.

Key Results

  • Compactness: KPB-SIFT produces a 36-dimension descriptor, significantly smaller than SIFT (128 dimensions), GLOH (128 dimensions), and SURF (64 dimensions).
  • Performance: The paper reports that KPB-SIFT achieves competitive performance, often outperforming PCA-SIFT and CDIKP in terms of recall for a given precision level across various geometric and photometric transformations (as shown in Figure 4 and 5).
  • Speed: In object recognition tasks (Figure 6b), KPB-SIFT is shown to be significantly faster than SIFT, requiring less than a third of the time for matching the same number of feature descriptors.
  • Robustness: Evaluations on synthesized and INRIA datasets demonstrate KPB-SIFT's robustness to scale, rotation, shearing, blur, and lighting changes.

Limitations and Future Work

  • Limitations: While KPB-SIFT shows strong performance, the paper acknowledges that it is compared against a limited set of other descriptors. The authors suggest future work to compare KPB-SIFT with other state-of-the-art descriptors like GLOH and SURF.
  • Future Work: The authors plan to explore KPB-SIFT in more applications, particularly mobile and large data-base applications where its compactness and speed are advantageous. They also aim to investigate other compact local descriptors using kernel projection techniques.

Summary updated

BibTeX
@inproceedings{zhao2010kpb,
  author = {Gangqiang Zhao and Ling Chen and Gencai Chen and Junsong Yuan},
  title = {{KPB-SIFT: a compact local feature descriptor}},
  booktitle = {ACM Multimedia},
  year = {2010},
  doi = {10.1145/1873951.1874180},
}
Figure