Iterative Continuous Convolution for 3D Template Matching and Global Localization

Vitor Guizilini, Fabio Ramos

Abstract

Template matching in 3D space is a critical task for robotics, particularly in global localization and object recognition. Traditional discrete methods, such as voxel-based cross-correlation, suffer from exponential computational growth and sensitivity to sensor noise and data sparsity. This paper introduces Iterative Continuous Convolution (ICC), a framework that treats point clouds as continuous functions using Hilbert Maps. By deriving a closed-form solution for convolution in a Reproducing Kernel Hilbert Space (RKHS), the proposed method achieves superior efficiency and robustness. Evaluation on large-scale real-world datasets shows that ICC provides a 100% convergence rate for global localization with high precision, significantly outperforming state-of-the-art discrete alternatives.

Introduction

Finding a specific 3D pattern within a larger scene—template matching—is fundamental to solving the "kidnapped robot" problem. However, 3D LiDAR data is inherently sparse and noisy. Discretizing this data into high-resolution voxel grids for convolution (e.g., via FFT) requires massive memory and often fails due to "gaps" in the sampled geometry. To address these limitations, we propose moving away from discrete approximations toward a continuous representation that scales effectively with dimensionality and kernel size.

Methodology

The core of our approach lies in performing convolution directly within a continuous functional space.

Hilbert Maps for Occupancy Representation

Instead of a rigid grid, the environment is modeled using Hilbert Maps. This technique projects raw 3D points into a high-dimensional feature space, where a linear classifier determines occupancy probabilities. The scene is represented by a set of anchor points (clusters) characterized by weights, means, and covariances.

Overview of the ICC pipeline: (a) Original pointcloud, (b) Extracted clusters, (c) 3D Reconstruction, (d) Reconstructed convolution mask, (e-f) Examples of convolution activations.

Continuous Convolution and Optimization

By employing Gaussian kernels, we derive a closed-form mathematical solution for convolving the "scene" and "mask" Hilbert Maps. The resulting activation function can be queried at any resolution in $O(\log M)$ time using kd-tree structures. To handle unknown orientations, we introduce a cluster alignment technique that ensures rotational invariance.

The global maximum of the activation function is found through an iterative three-step process:

  1. Sampling: Identifying global extrema candidates.
  2. Refinement: Converging on local maxima via gradient descent.
  3. Resolution Scaling: Gradually decaying cluster distance to fine-tune the estimate.

Experimental Evaluation

The ICC method was benchmarked against virtual and large-scale real-world datasets, including a structured corridor ($n \approx 475,000$ points) and an outdoor area ($n \approx 670,000$ points).

Key Results

  • Computational Efficiency: The method is orders of magnitude faster than sliding window or FFT-based approaches for large kernels and high resolutions. Memory usage is drastically reduced; a scene requiring 370 million voxels was represented by only 2,000 clusters.
  • Localization Robustness: In global localization tests, ICC achieved a 100% convergence rate, whereas standard techniques like Generalized ICP (GEN-ICP) and Particle Filters (AOS-PF) frequently diverged in sparse environments.
  • Precision: The system maintained high accuracy, with linear errors of approximately 10cm and angular errors of 3°, even under significant downsampling or rotation.

Conclusion

Iterative Continuous Convolution offers a mathematically elegant and computationally efficient alternative to discrete 3D template matching. By bypassing the limitations of voxel grids, the method provides robust performance in sparse, real-world environments. Future work will explore the use of non-Gaussian kernel functions and the integration of this continuous framework into deep learning architectures for 3D object classification.

Summary updated

Abstract

This paper introduces a novel methodology for 3D template matching that is scalable to higher-dimensional spaces and larger kernel sizes. It uses the Hilbert Maps framework to model raw pointcloud information as a continuous occupancy function, and we derive a closed-form solution to the convolution operation that takes place directly in the Reproducing Kernel Hilbert Space defining these functions. The result is a third function modeling activation values, that can be queried at arbitrary resolutions with logarithmic complexity, and by iteratively searching for high similarity areas we can determine matching candidates. Experimental results show substantial speed gains over standard discrete convolution techniques, such as sliding window and fast Fourier transform, along with a significant decrease in memory requirements, without accuracy loss. This efficiency allows the proposed methodology to be used in areas where discrete convolution is currently infeasible. As a practical example we explore the key problem in robotics of global localization, in which a vehicle must be positioned on a map using only its current sensor information, and provide comparisons with other state-of-the-art techniques in terms of computational speed and accuracy.
BibTeX
@inproceedings{guizilini2018iterative,
  author = {Vitor Guizilini and Fabio Ramos},
  title = {{Iterative Continuous Convolution for 3D Template Matching and Global Localization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12098},
}
Figure