Fast Coding of Feature Vectors Using Neighbor-to-Neighbor Search

Area of Science:

• Computer Vision
• Machine Learning
• Data Science

Background:

• High-dimensional vector searching is computationally intensive in computer vision.
• Algorithms like bag of visual words (BoW) face significant computational challenges.
• Efficient vector quantization is crucial for many image and video analysis tasks.

Purpose of the Study:

• To propose a computationally efficient method for high-dimensional vector searching.
• To accelerate vector quantization and related algorithms.
• To reduce the computational cost of computer vision tasks without performance degradation.

Main Methods:

• Introduced Neighbor-to-Neighbor (NTN) search, a novel algorithm that optimizes vector matching by skipping calculations based on vector similarity.
• Applied NTN search to vector quantization (NTN-VQ) and Gaussian mixture models (NTN-GMM).
• Evaluated NTN search on image and video benchmarks, including PASCAL VOC 2007 and TRECVID 2010.

Main Results:

• NTN-VQ achieved a 77.4% reduction in coding cost.
• NTN-GMM demonstrated an 89.3% reduction in coding cost.
• Both NTN-VQ and NTN-GMM maintained classification performance without significant degradation.

Conclusions:

• Neighbor-to-Neighbor search offers a significant computational speedup for high-dimensional vector matching.
• The proposed NTN method is effective in accelerating key computer vision components like vector quantization and Gaussian mixture models.
• NTN search provides a practical solution for improving the efficiency of image and video representation extraction.