3dVOT

3D Variational Optimal Transportation

VOT is a computational algorithm to solve the optimal transportation (OT) problem. It is based on the theorems of Brenier and Gu et al. VOT relates the solution of OT to power Voronoi diagram. Below shows an example. Suppose we are solving for an optimal transportation plan from grey dots to red dots. Each dot carries a weight, or measure. The total weight of all the grey/red dots is one. The goal is to find such a plan that the total weight of the grey dots that are mapped to a specific red dot is equal to the weight of that red dot. Suppose the domain is convex. Then, VOT initializes a Voronoi diagram by using the red dots with their own weights and then adjusts the size of each Voronoi cell to obtain the optimal transportation plan. In the following picture, on the left is the initial condition and on the right is the resulting diagram. Each cell corresponds to a red dot and all the grey dots in a cell are mapped to the corresponding red dot. In this page, grey dots are referred to as empirical measures and red dots Dirac measures.

3dVOT solves the optimal transportation in 3D spaces. Below shows an example. In this example, the domain is a unit ball.

Download this demo for Windows machines. This demo generates the 2nd picture.

Unzip the package. There is a binary executable, 3dVOT_plot, Dirac measure, mni152_56.p, and empirical measure, mni152_lh.tp. In addition, there are 56 files whose names start with ‘P_mni152_56_TP_mni152_lh_CellsFinal’. Those are pre-computed Voronoi cells. A gnuplot script to plot them is included, plotMni15256mni152.dat.

To run 3dVOT Enter the following command:3dVOT_plot.exe mni152_56.p mni152_lh.tp 1 1000 0.0001 1 1 13dVOT_plot.exe [Dirac measure] [Empirical measure] [Max outter iteration] [Max inner iteration] [Threshold] [Step] [Method] [Plot scale] The latest release of 3dVOT assumes all the measures are within a unit ball. The output is in gnuplot format. Download gnuplot from http://www.gnuplot.info/. Use the following command to visualize the 3D power diagram.gnuplot -p plotMni15256mni152.datDirac measures can also be visualized in a similar manner. ReferenceMi, Liang, Wen Zhang, Junwei Zhang, Yonghui Fan, Dhruman Goradia, Kewei Chen, Eric M. Reiman, Xianfeng Gu, and Yalin Wang. “An Optimal Transportation Based Univariate Neuroimaging Index.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 182-191. 2017.

Computing optimal transportation on brain images with 3dVOT

1 Extract brain volumes and surfaces with Freesurfer (or other tools such as FSL).

2 [Optional] Smooth surfaces using Meshlab (or other equivalence).

3 Tetrahedralize brain volumes with Tetgen given surfaces.

4 Map tetrahedral meshes to unit balls via volumetric harmonic map.

5 Project brain image onto tetrahedral meshes.

6 Compute 3dVOT.

Here provides software package. In the package, go to “Scripts” and run pipeline.m on Matlab. The “pipeline” will automatically call all the necessary files to run from step 1 to step 5. From there, we can compute the 3D VOT following the previous tutorial.For the latest version of the code, please visit the Github repository.