Iterative Closest Point (ICP) for 2D Points Library

A simple TypeScript library for performing the Iterative Closest Point (ICP) algorithm on 2D point clouds, with zero dependencies. This library works both in the browser and in Node.js and is compatible with JavaScript and TypeScript.

Table of Contents

• Iterative Closest Point (ICP) for 2D Points Library
  • Table of Contents
  • Installation
  • Usage
    • Output
    • Available options
      • Improving Results by Filtering Noise
  • Examples
  • Ideas

Installation

npm install icp2d

Usage

To use the ICP algorithm for aligning 2D point clouds, you can call the icp function, which calculates the transformation between two sets of 2D points (source and target).

import { icp, Point } from 'icp2d';

// Define your source and target point clouds (arrays of 2D Cartesian coordinates)
const source: Point[] = [
  [0, 0],
  [1, 0],
  [0, 1]
];

const target: Point[] = [
  [1, 1],
  [2, 1],
  [1, 2]
];

// Perform the ICP algorithm to align the source point cloud to the target
const res = icp(source, target);
console.log(res.sourceTransformed);
console.log(res.translation);
console.log(res.rotationMatrix)

Output

The output includes the rotation matrix (R), translation vector (t), transformed points, and the rotation in degrees. Example:

import { Result } from 'icp2d';

const res: Result = {
  sourceTransformed: Point[]; // Transformed points
  translation: Point; // t - Translation vector
  rotation: number; // Rotation in degrees
  rotationMatrix: Matrix2x2; // R - Rotation matrix
  err: number; // Error calculated using RMS
};

Available options

import { Options } from 'icp2d';

const options: Options = {
  tolerance: 10e6, // Convergence tolerance
  maxIterations: 500, // Maximum number of iterations
  verbose: true, // Outputs additional logs
  filterOutliers: {
    strategy: 'none' | 'maxDistance' | 'std'; // Strategy options for detecting outliers
    maxDistance: 500; // Optional, used for the max distance strategy
    threshold: 2; // Optional, used for the standard deviation strategy
  }
};

Improving Results by Filtering Noise

Filtering noise can significantly enhance the accuracy of the ICP algorithm. You can see its effects in different examples in test.ipynb. Here are different strategies to filter noise:

• Max Distance Strategy: Removes points that are further than a defined maximum distance from their closest neighbor in the target set.

const options = {
  filterOutliers: {
    strategy: 'maxDistance',
    maxDistance: 500
  }
};

• Standard Deviation Strategy: Excludes points that deviate too much from the mean error using a threshold based on standard deviation.

const options = {
  filterOutliers: {
    strategy: 'std',
    threshold: 2
  }
};

• None: Retains all points, without filtering.

const options = {
  filterOutliers: {
    strategy: 'none'
  }
};

Using these strategies helps to remove outliers that can distort transformation calculations, leading to more stable and accurate results.

Examples

You can find real-world test cases in test.ipynb. verify-transforms.ipynb verifies that the computed transformations are correct.

Ideas

• Add DBSCAN for identifying outliers.