gri-convolve 0.4.0

Ellipsoid convolution for combining geolocation estimates with outlier detection

Convolve (Ellipsoid Fusion)

Ellipsoid convolution functions for combining geolocation estimates with outlier detection and multi-cluster support.

Overview

gri-convolve provides three functions of increasing sophistication for fusing collections of Ell (ellipsoid) objects into combined position estimates:

• convolve -- combine all input ellipsoids into a single fused result with no outlier rejection
• smart_convolve -- iteratively remove outliers by Mahalanobis distance before fusing
• cluster_convolve -- find multiple clusters within a dataset and fuse each independently

Each function operates on Ell objects from gri-ell, which pair a 3D position with a statistical covariance (or information matrix). The output is one or more fused Ell objects representing the combined position estimate and its uncertainty.

Recursive single-target tracking -- the IMM / SmartSegmentedIMM filters, the motion-model bank, EKF/UKF observable updates, and RTS smoothing -- is provided by the companion gri-kalman package. Convolution is the batch face and the filter is the recursive face of the same estimation problem: the convolver seeds and refines tracks, the filter does the online sequential update. See the gri-kalman README for the tracker API and EKF-vs-UKF guidance.

Requires Python 3.12+.

Mathematical Background

Information matrix fusion. Given N ellipsoids, each with position x_k and information matrix I_k (the inverse of the covariance matrix, in XYZ coordinates, 1/m^2, 1-sigma), the fused position and information matrix are:

S = sum(I_k)              (combined information matrix)
x = S^{-1} sum(I_k x_k)  (fused position)

This is the maximum-likelihood estimator under Gaussian assumptions.

Inflation methods. The raw fusion above underestimates uncertainty when inputs are inconsistent. Three modes control how the output covariance is inflated:

• "none" -- strict information matrix combination (no inflation)
• "std" -- inflate by the sample scatter of input positions in XYZ
• "bart" -- inflate along the semi-major axis direction in ENU (recommended default)

Outlier detection. smart_convolve computes the Mahalanobis distance from each input to the fused point:

d_M = sqrt((x - mu)^T I (x - mu))

where mu is the fused position and I is its information matrix. Distances are normalized to 95% confidence scale. Inputs exceeding max_norm are iteratively removed, worst first.

Reference: Mahalanobis, P.C. (1936). "On the generalized distance in statistics."

Installation

pip install gri-convolve

For development:

git clone https://gitlab.com/geosol-foss/python/gri-convolve.git
cd gri-convolve
uv sync

Quick Start

from gri_convolve import convolve, smart_convolve, cluster_convolve
from gri_ell import Ell
from gri_pos import Pos
import numpy as np

# Create some ellipsoids at nearby positions
e1 = Ell.from_2d(Pos.LLA(40.0, -105.0, 1600), 100, 50, 45)
e2 = Ell.from_2d(Pos.LLA(40.001, -105.001, 1610), 120, 60, 30)
e3 = Ell.from_2d(Pos.LLA(40.0005, -104.999, 1605), 90, 45, 50)

# Simple fusion
fused = convolve([e1, e2, e3])
print(fused.lla)            # Fused position
print(fused.ellipse.sma_95) # Fused semi-major axis (95%, meters)

convolve()

Fuses all input ellipsoids into a single result. No outlier detection.

fused = convolve(ells, inflation="bart")

Parameters:

• ells -- sequence or generator of Ell objects
• inflation -- "none", "std", or "bart" (default: "bart")

Returns: A single fused Ell.

smart_convolve()

Fuses with iterative outlier rejection. Computes the fused point, finds the input with the largest normalized Mahalanobis distance, and removes it if it exceeds max_norm. Repeats until all remaining inputs are within tolerance or fewer than min_pts remain.

result = smart_convolve(ells, max_norm=2.0, min_pts=3)
if result is not None:
    fused_ell, used_indices, discarded_indices = result

Parameters:

• ells -- sequence or generator of Ell objects
• max_norm -- maximum allowed normalized distance (default: 2.0)
• min_pts -- minimum inputs required for a valid result (default: 3)

Returns: (Ell, list[int], list[int]) or None if no valid cluster is found.

Pre-cluster your data before calling smart_convolve. Without pre-clustering, a large group of scattered noise points can cause valid clusters to be discarded first.

cluster_convolve()

Finds multiple clusters within a dataset by iteratively applying smart_convolve. After finding the largest valid cluster, the discarded points are passed back in to find additional clusters.

locations, used_per_location, discarded = cluster_convolve(
    ells,
    max_norm=2.0,
    min_pts=3,
    max_pts=10,
    min_sma_m=50.0,
)

for loc, indices in zip(locations, used_per_location):
    print(f"Cluster at {loc.lla} using {len(indices)} inputs")

Parameters:

• ells -- sequence or generator of Ell objects
• max_norm -- maximum normalized Mahalanobis distance (default: 2.0)
• min_pts -- minimum inputs per cluster (default: 3)
• max_pts -- maximum inputs per cluster; splits larger groups (default: None)
• min_sma_m -- minimum semi-major axis for output ellipsoids in meters (default: 0)
• max_ori_spread -- sort by orientation before splitting for diversity (default: True)
• alt_post_process -- callback for altitude correction (e.g., snap to terrain)

Returns: (list[Ell], list[list[int]], list[int])

Units and Conventions

• Positions are in ECEF XYZ (meters) internally
• Information matrices are in XYZ, 1/m^2, 1-sigma
• Covariance matrices are in ENU, m^2, 1-sigma
• Output ellipse parameters (SMA, SMI, orientation) are at 95% confidence
• Mahalanobis distances are normalized to 95% scale for max_norm comparisons

Dependencies

• gri-ell: Ellipsoid objects with position and covariance
• gri-pos: Position objects (XYZ, LLA coordinates)
• gri-utils: Coordinate conversions and constants
• numpy: Array operations

Other Projects

Current list of other GRI FOSS Projects we are building and maintaining.

License

MIT License. See LICENSE for details.