Source-linked AI summary
Learning to Navigate the Energy Landscape
Julien Valentin, Angela Dai, Matthias Nießner, Pushmeet Kohli, Philip Torr, Shahram Izadi, Cem Keskin
TL;DR
The paper addresses the difficulty of minimizing non-convex reconstruction error efficiently in analysis-by-synthesis vision problems. It combines retrieval forests with navigational graphs for gradient-free local search, achieving state-of-the-art results across RGB relocalization, hand pose estimation, and image retrieval. Its results indicate both faster computation and more accurate solutions, including on a new larger-scale relocalization dataset.
Problem
Analysis-by-synthesis optimization is difficult because reconstruction error is typically non-convex, while rendering-based derivatives and repeated evaluations make hybrid local-search pipelines costly.
Method
The method combines discriminatively trained retrieval forests for multiple search seeds with hierarchical navigation graphs for efficient gradient-free refinement.
Results
The method achieves state-of-the-art results across RGB camera relocalization, hand pose estimation, and image retrieval, with improved computation time and solution accuracy.
Takeaways & Limitations
A retrieval forest plus multiscale navigation graph provides a generic discrete optimization framework demonstrated across three distinct computer vision tasks.
Takeaways & Limitations
RGB relocalization accuracy is constrained by inconsistencies between reconstructed 3D models and real-world images caused by tracking errors and artifacts such as motion blur.
Abstract
from arXiv · showhide
In this paper, we present a novel and efficient architecture for addressing computer vision problems that use `Analysis by Synthesis'. Analysis by synthesis involves the minimization of the reconstruction error which is typically a non-convex function of the latent target variables. State-of-the-art methods adopt a hybrid scheme where discriminatively trained predictors like Random Forests or Convolutional Neural Networks are used to initialize local search algorithms. While these methods have been shown to produce promising results, they often get stuck in local optima. Our method goes beyond the conventional hybrid architecture by not only proposing multiple accurate initial solutions but by also defining a navigational structure over the solution space that can be used for extremely efficient gradient-free local search. We demonstrate the efficacy of our approach on the challenging problem of RGB Camera Relocalization. To make the RGB camera relocalization problem particularly challenging, we introduce a new dataset of 3D environments which are significantly larger than those found in other publicly-available datasets. Our experiments reveal that the proposed method is able to achieve state-of-the-art camera relocalization results. We also demonstrate the generalizability of our approach on Hand Pose Estimation and Image Retrieval tasks.
1. Introduction
Analysis by synthesis minimizes reconstruction error but is difficult to optimize because the objective is non-convex and rendering-based evaluation is expensive. The paper proposes retrieval forests and multiscale navigation graphs to enable fast, accurate gradient-free search across several vision tasks.
- Analysis by synthesis finds synthesis-model parameters that minimize reconstruction error, such as the distance between synthesized and query images.
- Hybrid architectures use discriminatively trained Random Forests or CNNs to initialize continuous local search, but robust real-time operation remains difficult.
- Rendering-based derivatives and costly error evaluations make existing local optimization methods computationally expensive, while non-convexity makes good search seeds essential.
- The proposed framework combines retrieval forests for candidate generation with hierarchical navigation graphs for gradient-free local search over parameter space.
- The method is evaluated on RGB camera relocalization, hand pose estimation, and image retrieval using a new dataset of significantly larger 3D environments.
- The composite retrieval tree-navigation architecture produces more accurate solutions while substantially reducing computation time.
2. Related work
Prior work includes hashing, spatial indexes, derivative-free heuristics, and graph-based hill climbing for retrieval and pose problems. The paper differs by learning better search seeds and exploring multiple hypotheses to reduce poor local minima and improve speed.
- Locality-sensitive hashing maps similar items to shared buckets, while pose-sensitive hashing retrieves neighbors in a latent articulated-pose manifold.
- KD-trees recursively partition data with axis-aligned hyperplanes, and related approximate-neighbor methods include hierarchical k-means indexing.
- Particle Swarm Optimization, Cuckoo Search, and Genetic Algorithms perturb candidate solutions to seek lower-error explanations of input images.
- Earlier k-NN graph hill climbing starts from random database points, which can reach poor minima on large and diverse datasets.
- The proposed approach learns retrieval-based seeds closer to post-optimization minima and explores multiple hypotheses instead of following one greedy path.
3. Method Overview
The method performs discrete optimization with a retrieval forest and hierarchical navigation graph. Forest-generated seeds are refined by expanding neighboring candidates, ranking them by reconstruction or surrogate error, and traversing graph levels.
- A retrieval forest generates ranked seed vertices, which initialize search in the highest level of the navigation graph.
- Each search iteration expands candidates with graph neighbors, evaluates reconstruction or surrogate error, and retains top-ranked vertices for further exploration.
- The search proceeds through the graph hierarchy when the candidate set stabilizes or reaches the iteration limit.
4. Retrieval Forests
Retrieval forests act as learned lookup mechanisms that assign queries to leaves and rank stored dataset elements for search initialization. Sparse randomized tree projections improve traversal efficiency before graph-based refinement.
- A retrieval forest assigns each query to a leaf, where stored dataset indices are retrieved and ranked by votes across trees.
- Trees are grown with randomized feature-index pairs and thresholds, optionally combined with bagging.
- Tree-node information gain is optimized using entropy of descriptor-space subsets conditioned on candidate parameters.
- The entropy measure is based on the determinant of the covariance matrix.
- Sparse projections make tree traversal more efficient, after which retrieval-forest results are refined by later pipeline stages.
5. Multiscale Navigation Graph
The multiscale navigation graph rapidly refines retrieval-forest seeds through gradient-free local search over increasingly fine graph levels. Candidates are evaluated by query distance, and neighbor connections provide potential descent directions while reducing exposure to local minima.
- Graph construction: The multiscale graph represents samples as vertices connected to k nearest neighbors across multiple scales, with higher-level vertices retained at every lower level.The top level contains a uniform fraction of samples, while the bottom level contains the full dataset.
- Graph structure: Directed nearest-neighbor edges need not be reciprocal because nearest-neighbor relationships are not symmetric.The sample distance is denoted Dm(p, q), with the metric determined by m.
- Graph traversal: The graph search begins from retrieval-forest seeds and expands each candidate with its neighbors before ranking candidates by distance to the query.The distance used to build the graph need not equal the distance used during query search.
- Multiscale refinement: Search proceeds to the next finer graph when the candidate set stops changing or the iteration limit is reached, using the converged candidates to initialize the next level.The final candidate set from the last graph level is the discrete optimization output.
- Optimization intuition: For a current candidate, neighboring vertices are tested for lower reconstruction error and may serve as potential descent directions.Figure 1 depicts candidate connections in orange and their positions on the solution manifold in blue.
6. Continuous Pose Refinement
Continuous pose refinement optimizes photo-consistency between a raycast scene model and the query image for multiple pose proposals. The procedure uses hierarchical coarse-to-fine Gauss–Newton optimization while discarding invalid-depth pixels.
- Pose refinement: For each of the query image’s top k pose proposals, the method minimizes the photo-consistency objective to produce refined poses.The optimization estimates a rigid-body transform between the scene model rendered from a hypothesis and the query image.
- Photo-consistency: The scene model is raycast from each current pose to produce color and depth images, which are used to optimize the rigid transform against the query.The color and depth projections use camera-specific intrinsics.
- Optimization schedule: The nonlinear least-squares objective is solved with Gauss–Newton optimization using a hierarchical coarse-to-fine strategy.The finest level uses full color resolution, while each subsequent level is subsampled by a factor of 2.
- Data handling: Invalid-depth pixels are discarded before evaluating the refinement objective.
- Search procedure: The graph-traversal procedure takes multiscale adjacency lists, a distance function, seeds, iteration and retention limits, and a requested number of predictions as inputs.Its output is K approximate nearest neighbors of the test sample.
7. Results
Across hand pose estimation, image retrieval, and RGB relocalization, the proposed approach delivers accurate results with efficient search and optimization. Experiments also introduce a substantially larger relocalization dataset while highlighting reconstruction-quality limitations.
- Overall results: Across three vision tasks, the method outperforms baselines in both accuracy and speed.The tasks are hand pose estimation, approximate nearest-neighbor image retrieval, and RGB relocalization.
- Hand pose estimation: Regardless of the number of predicted seeds, the method achieves lower average joint pose error than and extracts seeds an order of magnitude faster.This comparison uses the synthetic hand-pose dataset and average joint pose error.
- Hand pose estimation: On real hand images, the method significantly outperforms Retrieval Forest only and the reinitializer from, including when continuous LM optimization is applied.The experiment generates 10 seeds per frame and treats each frame independently.
- Image retrieval: With a 5ms budget, the image-retrieval method exceeds 70% recall at a 60× speedup over linear search and outperforms FLANN baselines at comparable compute.At 450× speedup, the FLANN hierarchical, k-means, and composite baselines attain half the recall of the proposed method.
- RGB relocalization: 67.4% of relocalization queries fall within 5cm and 5° on average, while 88% fall within 30cm and 10°.The proposed system is evaluated on the new RGB relocalization dataset.
- Limitations: Reconstruction artifacts, including tracking errors and motion blur, leave 3D models inconsistent with the real world and constrain RGB synthesis quality.The authors report that consistency between training and test images would enable more accurate results.
8. Conclusion
The paper’s multiscale navigational graph enables fast, accurate discrete optimization across several vision tasks, with predictions further refined when needed.
- 8. Conclusion: The method uses a multiscale navigational graph to quickly traverse a discrete solution manifold from random-forest seeds.The graph produces fast and accurate predictions by exploring candidate solutions across multiple scales.
- 8. Conclusion: The qualitative results show graph searches producing viewpoints that are relatively robust to missing synthetic-view data and illumination changes.The query image is paired with seeds from the retrieval forest before graph search generates viewpoints.
- 8. Conclusion: Continuous refinement minimizes photometric error from the top 4 predicted viewpoints to obtain the final pose.The top prediction is shown alongside the query and the refined result in the qualitative comparison.
- 8. Conclusion: For RGB relocalization, continuous pose optimization further refines the graph’s predictions into precise 6DOF camera pose estimates.The same refinement strategy also applies to hand pose estimation and image retrieval results.