einit: Fast and Robust Ellipsoid ICP Initialization

einit is a Python library that provides fast and robust initialization for Iterative Closest Point (ICP) algorithms using ellipsoid analysis. It computes optimal initial transformations between 3D point clouds by analyzing their ellipsoids of inertia.

Features

• Fast Initialization: Compute initial transformations in milliseconds

• Robust Algorithm: Handles various point cloud shapes (spheres, ellipsoids, general shapes)

• Feature Augmentation: Optional per-point features (RGB, LiDAR intensity, normals) break geometric degeneracy for symmetric shapes

• OpenCV Integration: Returns standard 4×4 homogeneous transformation matrices

• Noise Tolerance: Maintains performance even with significant noise

• Partial Overlap: Works with incomplete point cloud correspondences

Quick Start

import numpy as np
from einit import register_ellipsoid

# Create source and destination point clouds
src_points = np.random.randn(100, 3)
dst_points = src_points @ R + t  # Apply some transformation

# Compute initial transformation (geometry only)
T_init = register_ellipsoid(src_points, dst_points)

# T_init is a 4×4 homogeneous transformation matrix
# Compatible with OpenCV and other computer vision libraries

# With per-point features to resolve geometric symmetry
src_rgb = np.random.rand(100, 3)   # e.g. RGB colour
dst_rgb = np.random.rand(100, 3)
T_feat = register_ellipsoid(
    src_points, dst_points,
    src_features=src_rgb,
    dst_features=dst_rgb,
    feature_weight=1.0,
)

Installation

Install directly from GitHub:

pip install git+https://github.com/sashakolpakov/einit.git

For development or testing:

pip install "git+https://github.com/sashakolpakov/einit.git[test]"  # Includes matplotlib, pytest
pip install "git+https://github.com/sashakolpakov/einit.git[all]"   # Everything including docs

Or clone and install locally:

git clone https://github.com/sashakolpakov/einit.git
cd einit
pip install -e .[test]  # Editable install with test dependencies

Requirements: - Python ≥ 3.6 - NumPy ≥ 1.15 - SciPy ≥ 1.0

Contents

Documentation:

• Algorithm Details
  • Overview
  • Step-by-Step Breakdown
  • Mathematical Properties
  • Applications and Use Cases
  • Implementation Notes
• API Reference
  • register_ellipsoid()
  • barycentered()
• Examples
  • Basic Usage
  • Integration with OpenCV
  • Real-World Data
  • Visualization
  • Running Examples and Tests
• OpenCV Integration
  • Transformation Matrix Format
  • Common Integration Patterns
  • Performance Optimization
  • Error Handling
• Integration with Other Libraries

Algorithm Overview

The ellipsoid initialization algorithm works by:

1. Centering: Both point clouds are centered at their respective centroids

2. Ellipsoids of Inertia: Computes ellipsoid matrices and their eigendecompositions (optionally augmented with per-point features)

3. Axis Alignment: Searches through all 8 possible axis orientations (±1 reflections)

4. Optimization: Selects the transformation that minimizes alignment error

5. Output: Returns a 4×4 homogeneous transformation matrix

Mathematical Foundation

Given source points \(P = \{p_1, p_2, \ldots, p_n\}\) and destination points \(Q = \{q_1, q_2, \ldots, q_m\}\), the algorithm:

1. Centers the point clouds:

   \[\bar{p} = \frac{1}{n}\sum_{i=1}^n p_i, \quad \bar{q} = \frac{1}{m}\sum_{j=1}^m q_j\]
   \[P_c = P - \bar{p}, \quad Q_c = Q - \bar{q}\]

2. Computes covariance matrices (geometry-only):

   \[E_P = P_c^T P_c, \quad E_Q = Q_c^T Q_c\]

   Or, when per-point features \(F\) are provided with weight \(\beta\):

   \[E_P^{\text{aug}} = P_c^T P_c + \beta \cdot \frac{\text{tr}(E_P)}{\text{tr}(E_{ff})} \cdot (P_c^T F)(P_c^T F)^T\]

   where \(E_{ff} = (P_c^T F)(P_c^T F)^T\). The cross-covariance term biases the principal axes toward spatial directions where features vary most, breaking eigenvalue degeneracy for symmetric shapes.

3. Performs eigendecomposition:

   \[E_P = U_P \Lambda_P U_P^T, \quad E_Q = U_Q \Lambda_Q U_Q^T\]

4. Finds optimal rotation through reflection search:

   \[R^* = \arg\min_{D \in \{\pm 1\}^{3 \times 3}} \|Q_c - R P_c\|_F\]

where \(R = U_Q D U_P^T\) and \(D\) is a diagonal matrix with ±1 entries.

Performance Characteristics

• Time Complexity: O(n) where n is the number of points

• Space Complexity: O(1) additional memory

• Typical Runtime: < 1ms for 1000 points

• Convergence: Non-iterative, deterministic result

Benchmark Results

Real-world performance with 2% noise and 80% overlap:

• Sphere (500 points): RMSE 0.017 ± 0.014

• Cube (1728 points): RMSE 0.002 ± 0.001

• Stanford Bunny (1000 points): RMSE 0.004 ± 0.001

The algorithm often outperforms traditional ICP refinement, providing excellent results without iteration.

Use Cases

Computer Vision - Point cloud registration - 3D object alignment - Structure from motion - SLAM applications

Robotics - Sensor fusion - Object pose estimation - Navigation and mapping

Scientific Computing - Molecular alignment - Geometric analysis - Shape matching

Indices and Tables

• Index

• Module Index

• Search Page