jeremykawahara/cloudtogrid

Example of converting a 2d point cloud to a 2d grid via the assignment problem.

CloudToGrid

This repo shows how to map one point cloud to another; for example, creating a 2d grid embedding of a t-SNE point cloud.

This repo uses lapjv wrapper for Jonker's implementation of the Jonker-Volgenant algorithm as well as hungarian, which are both solutions to the "assignment problem", a combinatorial optimization problem that asks: how do you assign workers to tasks in a way that minimizes the overall cost? For CloudToGrid, the "task" is point correspondence, and the cost of each correspondence is the squared distance between the original and destination point. The Jonker-Volgenant algorithm is a less tolerant but more efficient solution than the traditional Hungarian Algorithm.

The Jonker-Volgenant algorithm implementation used here can fail when the difference between two costs is very small, and both algorithms can fail when the costs are all small.

Installation and Usage

First, install numpy, scipy, sklearn, matplotlib, lapjv and hungarian using the requirements file:

$ pip install -r requirements.txt

Then clone this repository and run the example:

$ git clone https://github.com/kylemcdonald/CloudToGrid.git
$ cd CloudToGrid
$ jupyter notebook

Acknowledgement

This repository is inspired by Mario Klingemann's Raster Fairy work.