Hierarchical Encoding of Sequential Data With Compact and Sub-Linear Storage Cost

Huu Le, Ming Xu, Tuan Hoang, Michael Milford

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.

The hierarchical chunking process in HESSL, dividing sequential data into levels of increasing granularity.

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.

Performance summary of HESSL compared to baseline methods across different error tolerances and environmental conditions.

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

Abstract

Snapshot-based visual localization is an important problem in several computer vision and robotics applications such as Simultaneous Localization And Mapping (SLAM). To achieve real-time performance in very large-scale environments with massive amounts of training and map data, techniques such as approximate nearest neighbor search (ANN) algorithms are used. While several state-of-the-art variants of quantization and indexing techniques have demonstrated to be efficient in practice, their theoretical memory cost still scales at least linearly with the training data (i.e., O(n) where n is the number of instances in the database), since each data point must be associated with at least one code vector. To address these limitations, in this paper we present a totally new hierarchical encoding approach that enables a sub-linear storage scale. The algorithm exploits the widespread sequential nature of sensor information streams in robotics and autonomous vehicle applications and achieves, both theoretically and experimentally, sub-linear scalability in storage required for a given environment size. Furthermore, the associated query time of our algorithm is also of sub-linear complexity. We benchmark the performance of the proposed algorithm on several real-world benchmark datasets and experimentally validate the theoretical sub-linearity of our approach, while also showing that our approach yields competitive absolute storage performance as well.
BibTeX
@inproceedings{le2019hierarchical,
  author = {Huu Le and Ming Xu and Tuan Hoang and Michael Milford},
  title = {{Hierarchical Encoding of Sequential Data With Compact and Sub-Linear Storage Cost}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2019},
  doi = {10.1109/iccv.2019.00992},
}
Figure