Computer-Implemented Method for Calculating Geodetic Distances in Particular Between Data Points, Computer Program, Computer-Readable Medium and Device

Simple SummaryContent extracted from patent full text and abstract with AI.

This invention is a computer-implemented method for efficiently calculating distances between data points, with a particular focus on geodesic distances (shortest paths along a surface or through a data manifold). The method works by splitting a large input dataset into smaller sub-datasets, constructing a Minimum Spanning Tree (MST) for each sub-dataset independently, and then aggregating the edges from all resulting MSTs into a single final graph. This divide-and-aggregate strategy makes it practical to compute geodesic distances on large datasets that would otherwise be computationally prohibitive to handle in one pass.

Use CasesContent extracted from patent full text and abstract with AI.

• Computing geodesic distances on large 3D point clouds in autonomous vehicle perception pipelines, where surface-aware distances are needed for object segmentation.
• Dimensionality reduction and manifold learning tasks in machine learning (e.g., Isomap), where accurate geodesic distances between high-dimensional data points are required.
• Medical imaging analysis, such as measuring anatomical distances along curved surfaces like the brain cortex or bone structures from scan data.
• Geographic information systems (GIS) for calculating shortest-path distances across terrain models represented as dense point datasets.
• Robotics path planning on uneven surfaces, where geodesic distances over a point-cloud map of the environment guide navigation decisions.

BenefitsContent extracted from patent full text and abstract with AI.

• Scales to large datasets by dividing the input into smaller sub-datasets, reducing the memory and computational load compared to processing the full dataset at once.
• Parallelizable by design, since MSTs for independent sub-datasets can be constructed simultaneously across multiple processors or compute nodes.
• Retains accuracy of geodesic distance approximation by aggregating edges from all sub-MSTs into a unified final graph that captures global connectivity.
• Reduces algorithmic complexity compared to computing a single MST or full distance matrix over the entire dataset in one step.
• Flexible enough to accept either raw data or pre-processed input datasets, making it adaptable to diverse data acquisition pipelines.

Technical Classifications (CPCs)

Inventors & Applicants

Patent Abstract

The present invention relates to a computer-implemented method for calculating in particular geodetic distances between data points (S), wherein S1) an input data set (2) or a raw data set (1) is received and an input data set (2) is calculated therefrom, S2) multiple sub-input data sets (3) are created from the input data set (2), wherein each sub-input data set (3) comprises a portion of the data of the input data set (2), S3) for the resulting sub-input data sets (3) a minimal spanning tree (MST) is respectively constructed, S4) at least edges (5) of the obtained minimal spanning trees (MST) are aggregated and based on the result of the aggregation a final graph (6) is created.