PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Naive Bayes Nearest Neighbor for Image Classification

Sancho McCann, David G. Lowe

arXiv:1112.0059v1cs.CV

TL;DR

NBNN must improve classification while scaling beyond small numbers of object classes. Local NBNN merges reference data into one index and updates only locally represented classes, improving performance and scalability while remaining competitive with, but not surpassing, recent spatial pyramid methods.

  • Problem

    The original NBNN approach requires class-specific searches and updates, creating scalability concerns as the number of visual classes grows.

  • Method

    Local NBNN merges all class reference data into one search structure and adjusts scores only for classes represented among the nearest descriptors.

  • Results

    Local NBNN improves on original NBNN and the original spatial pyramid model, while remaining competitive with recent state-of-the-art spatial pyramid variants.

  • Takeaways & Limitations

    The method provides improved classification performance and scalability, with runtime growing sublinearly rather than linearly with the number of classes.

  • Takeaways & Limitations

    Local NBNN does not outperform the recent spatial pyramid model of Liu et al., whose soft assignment and discriminative training provide additional benefits.

Abstract

from arXiv · show

We present Local Naive Bayes Nearest Neighbor, an improvement to the NBNN image classification algorithm that increases classification accuracy and improves its ability to scale to large numbers of object classes. The key observation is that only the classes represented in the local neighborhood of a descriptor contribute significantly and reliably to their posterior probability estimates. Instead of maintaining a separate search structure for each class, we merge all of the reference data together into one search structure, allowing quick identification of a descriptor's local neighborhood. We show an increase in classification accuracy when we ignore adjustments to the more distant classes and show that the run time grows with the log of the number of classes rather than linearly in the number of classes as did the original. This gives a 100 times speed-up over the original method on the Caltech 256 dataset. We also provide the first head-to-head comparison of NBNN against spatial pyramid methods using a common set of input features. We show that local NBNN outperforms all previous NBNN based methods and the original spatial pyramid model. However, we find that local NBNN, while competitive with, does not beat state-of-the-art spatial pyramid methods that use local soft assignment and max-pooling.

1 Introduction

NBNN classifies images by comparing each unquantized query descriptor with class-specific reference descriptors. Local NBNN merges those references into one index and updates only nearby classes, targeting higher accuracy and better scalability.

  • NBNN motivation: NBNN retains visual descriptors in their original form instead of quantizing them into visual words.This contrasts with bag-of-words pipelines that reduce the high-dimensional feature space to a limited vocabulary.
  • Original NBNN: The original NBNN searches for each query descriptor’s nearest neighbor separately within every class.Its class-specific search structures support class-wise nearest-neighbor queries.
  • Local NBNN: Local NBNN merges reference datasets and adjusts scores only for classes nearest to each query descriptor.The method changes the question from testing every class to identifying which class descriptors resemble the query descriptor.
  • Contribution: The paper reports increased classification accuracy and a significant speed-up when scaling to many object classes.It presents the modification as an improvement to the original NBNN algorithm.
  • Evaluation: The paper provides a head-to-head comparison of NBNN-based and spatial-pyramid methods using a common feature set.Earlier comparisons used published figures while extracting different feature sets.

2 Relation to previous work

The paper situates NBNN among bag-of-words, spatial-pyramid, and other local-coding approaches while focusing on its nearest-neighbor search bottleneck. It also notes the independence assumption and the lack of prior common-feature head-to-head comparisons.

  • NBNN limitations: Naive Bayes assumes image descriptors provide independent evidence for an object category, an assumption the paper calls unrealistic.Prior work argues naive Bayes can still classify well when this assumption is violated.
  • Computational limitations: A major practical limitation of NBNN is the time required for nearest-neighbor searches.The paper addresses this computational bottleneck directly.
  • Computational limitations: Original NBNN search time scales linearly with the number of categories because each category has a separate search structure.Even approximate searches can remain slow under this arrangement.
  • Local methods: Local coding methods restrict coding to nearby dictionary elements, with prior work hypothesizing that distant Euclidean distances poorly estimate codeword membership.The paper presents local NBNN as a local nearest-neighbor modification in this broader context.
  • Spatial pyramids: State-of-the-art spatial-pyramid variants combine local coding with max pooling, but prior work lacked a head-to-head comparison with NBNN using common features.The paper addresses that comparison gap.

3 Naive Bayes Nearest Neighbor

Original NBNN derives a class decision from descriptor likelihoods under a uniform prior and an independence assumption. It then approximates those likelihoods with nearest-neighbor distances and selects the class with minimum total distance.

  • Classification setup: NBNN classifies a query image by selecting the most probable class from all descriptors extracted from that image.Each class stores descriptors from labelled training images in structures supporting nearest-neighbor searches.
  • Probabilistic derivation: Under a uniform class prior, Bayes’ rule and descriptor independence reduce image classification to combining descriptor-level likelihoods.The independence assumption treats descriptors in the query image as independent evidence.
  • Likelihood estimation: A Parzen window estimator approximates each descriptor likelihood using class-training descriptors and kernel K.The class training set contains L descriptors, with dC_j denoting the j-th nearest descriptor in class C.
  • Nearest-neighbor approximation: The likelihood approximation can use only the r nearest neighbors, and NBNN takes this further by retaining only the single nearest neighbor.For a Gaussian kernel, this yields a distance-based classification rule.
  • Decision rule: NBNN selects the class with the minimum summed distance between query descriptors and their class-specific nearest neighbors.This is the classification rule identified as Equation 9.

4 Towards local NBNN

The paper reframes each descriptor’s contribution as a log-odds update, enabling selective posterior adjustments. Restricting updates to positive evidence preserves classification accuracy in the reported experiment.

  • Log-odds formulation: Each query descriptor contributes a log-odds increment determined by posterior odds relative to prior odds.The increment is positive, zero, or negative when posterior odds exceed, equal, or fall below prior odds.
  • Selective updates: Table 1 evaluates positive-increment restriction on a downsampled 128x128 Caltech 101 dataset, reporting variability with one standard deviation.
  • Log-odds formulation: The alternative classification rule selects the class using accumulated log-odds increments.
  • Selective updates: Selective updating adjusts only class posteriors receiving positive evidence from a descriptor.This avoids applying every possible increment while retaining the significant updates.
  • Selective updates: Restricting updates to positive increments does not affect classification accuracy in the reported experiment.

5 Local NBNN

Local NBNN replaces per-class nearest-neighbor searches with one merged search over all reference descriptors, updating only classes represented in each descriptor’s local neighborhood. This reduces scaling from linear to logarithmic in the number of classes, subject to the chosen search structure.

  • Local search strategy: Local NBNN searches a single merged dataset for the nearest few descriptors instead of searching every class separately.The merged index contains features from all labelled training data, and one approximate k-nearest-neighbor search identifies the local neighborhood.
  • Complexity: The merged-search strategy is faster because approximate search time grows sublinearly with the size of the indexed data.The implementation uses FLANN approximate nearest-neighbor structures.
  • Local search strategy: For each query descriptor, only classes represented among its k nearest descriptors receive nearest-neighbor updates.Classes absent from that neighborhood are treated as background classes rather than searched individually.
  • Complexity: Logarithmic scaling replaces linear scaling with the number of classes, avoiding a prohibitive runtime increase as class count grows.This analysis depends on the nearest-neighbor search structure used.
  • Algorithm: The local NBNN procedure uses one all-descriptor index, a class lookup, k + 1 neighbors, and distance-total updates for neighborhood categories.

6 Experiments and results

Experiments evaluate local NBNN on Caltech 101 and 256, tuning its neighborhood cutoff, computation, scaling, and comparisons with NBNN and spatial-pyramid methods. Local NBNN improves accuracy and substantially reduces runtime, but remains only competitive with the latest spatial-pyramid variant.

  • Experimental setup: Experiments use Caltech 101 and 256 with dense, multi-scale SIFT descriptors and 15 or 30 training images per class.Performance is measured by average per-class classification accuracy.
  • Tuning Local NBNN: Using a relatively low neighborhood cutoff k improves performance, while too few neighbors hurt and many neighbors approach original NBNN performance.The figure identifies about 10 local neighbors as optimal, although its absolute accuracies use fewer descriptors than the final experiments.
  • Computation and scaling: Local NBNN achieves higher accuracy with less computation because one merged index replaces separate class indices and restricts score adjustments to nearby classes.On Caltech 101, localized merged-index search remained faster than checking one leaf node in each of 101 separate indices, even with 1000–4000 merged-index checks.
  • Computation and scaling: 100 times faster runtime at 256 classes results from local NBNN’s logarithmic growth versus the original method’s linear growth with the number of classes.The merged search traverses from root to leaf once, whereas the original requires a separate best-bin-first traversal for each class.
  • Comparisons with other methods: Local NBNN consistently improves over original NBNN and previous single-descriptor NBNN results, outperforming the original spatial pyramid but not Liu et al.’s latest variant.The comparison uses a common base feature set for NBNN and spatial-pyramid methods.
  • Comparisons with other methods: The comparison is limited by feature-set differences in higher published results and by an unresolved discrepancy between the authors’ NBNN accuracy and Boiman et al.’s result.The authors report 63.2 ± 0.9 versus 65.0 ± 1.14 and attribute the disparity to unresolved feature-extraction parameter differences.

7 Conclusion

Local NBNN improves upon original NBNN in classification performance and scalability by adjusting only nearby classes and searching a merged index. It outperforms early spatial pyramid models but remains competitive with, rather than better than, recent state-of-the-art variants.

  • Local NBNN improves classification performance and scales better to large numbers of object classes than original NBNN.
  • Adjusting only classes in each descriptor’s local neighborhood improves performance while reducing unnecessary class-wise computation.
  • Merged-index search examines only the closest few neighbors instead of searching separately for each class, making the method much faster.
  • NBNN outperforms early spatial pyramid models, while recent state-of-the-art variants remain competitive through additional discriminative training.
  • Scalability becomes increasingly important as recognition systems target very large visual-class inventories such as web-search categories and ImageNet concepts.
Loading 1112.0059v1…