Abstract
Visual localization is a critical component of autonomous navigation, yet traditional methods suffer from linear storage growth relative to the environment size. This paper presents HESSL (Hierarchical Encoding of Sequential data), a novel scheme that leverages the inherent sequentiality of video streams to achieve sub-linear storage and query complexity. By replacing individual image descriptors with a tree-based hierarchy of linear classifiers, the proposed method reduces map storage costs to $O(\log n)$. Experimental results on the Nordland and Brisbane datasets demonstrate that HESSL maintains competitive accuracy while significantly reducing the memory footprint compared to state-of-the-art quantization techniques.
Introduction
In the field of Simultaneous Localization and Mapping (SLAM), visual localization allows robots to determine their pose by matching current camera observations against a pre-built map. Modern systems typically represent images as compact descriptors. However, even with compression techniques like Product Quantization (PQ), these systems face a fundamental scaling bottleneck: they require at least one code per observation. As mapping operations scale to continental levels, the $O(n)$ memory requirement becomes prohibitive.
This research addresses the scaling wall by introducing a hierarchical encoding scheme. Instead of storing a representation for every image, the system stores the decision boundaries (hyperplanes) that partition the sequential data into manageable chunks.
Methodology: Hierarchical Encoding of Sequential Data (HESSL)
The core innovation of HESSL is the transition from "one code per image" to a tree-based classification structure. The method consists of several primary components:
Hierarchical Chunking
Sequential data, such as a video feed from a vehicle, is recursively divided into temporal "chunks." This creates a tree structure where each node represents a specific segment of the sequence. A query image is localized by traversing the tree from the root to a leaf node, which corresponds to a specific frame index.
Learning Separating Hyperplanes
At each node in the hierarchy, the system stores the parameters of a Linear Support Vector Machine (LSVM). These SVMs are trained to distinguish which child "chunk" a query image belongs to. By storing only the SVM weights rather than individual image descriptors, the storage cost scales with the number of nodes in the tree—$O(\log n)$ for a balanced binary tree—rather than the number of images.
Optimal Data Transformation
To ensure linear separability of image descriptors, HESSL learns a linear transformation matrix ($L_j$) and a subspace projection for each level. This transformation "stretches" the feature space, making it easier for the LSVMs to draw accurate boundaries between sequential segments.
Experimental Evaluation
The HESSL framework was evaluated using the Nordland Dataset (10-hour train journey across four seasons) and the Brisbane Day and Night dataset (urban driving under varying illumination).
Storage and Accuracy Trade-offs
Experiments demonstrated that HESSL significantly outperforms standard techniques like PQ and Optimized Product Quantization (OPQ) under tight memory constraints. While traditional methods exhibit strictly linear memory growth, HESSL's footprint remains remarkably flat as the dataset size increases.
Key results include:
- Memory Efficiency: On a 20,000-image dataset restricted to a 10MB budget, HESSL maintained higher accuracy than PQ-based competitors.
- Robustness: The system showed resilience to extreme seasonal changes (Nordland) and lighting shifts (Brisbane), particularly when a small error tolerance (e.g., $\pm 20$ frames) was permitted.
Discussion and Conclusion
HESSL demonstrates that the sequential nature of sensor data is a powerful feature for compression. By treating localization as a hierarchical classification problem rather than a nearest-neighbor search, the system breaks the linear scaling barrier.
While the current implementation relies on linear transformations and sequential data, future work could explore non-linear mappings (e.g., deep neural networks) and more robust temporal filtering. HESSL serves as a proof-of-concept for sub-linear indexing, offering a scalable path forward for long-term, large-scale robotic localization.
Summary updated