Statistical Physics Approach to the Optimal Transport Problem

Originally defined for the optimal allocation of resources, optimal transport (OT) has found many theoretical and practical applications in multiple domains of science and physics. In this Letter we develop a new method for solving the discrete version of this problem using techniques derived from statistical physics. We derive a strongly concave free energy function that captures the constraints of the OT problem at a finite temperature. Its maximum defines an optimal transport plan, or registration between the two discrete probability measures that are compared, as well as a pseudodistance between those measures that satisfies the triangular inequalities. The computation of this pseudodistance is fast and numerically stable. The temperature dependent OT pseudodistance is shown to decrease monotonically with respect to the inverse of the temperature and to converge to the standard OT distance at zero temperature, providing a robust framework for temperature annealing. We illustrate applications of this framework to the problem of image comparison.

Figure 1

Optimal transport distance matrix between all images in the JAFFE facial expression database. The distance $D(\infty )(k,l)$ is the converged transport energy between the SURF key points of the two images $k$ and $l$ (see text for details). The different images for the same model appear closer to each other than to images of other models. Interestingly $D(\infty )$ shows similarity between models 3, 8, and 10; those are the only 3 models whose hair covers their ears.

Figure 2

Discriminative power of the temperature-based OT pseudodistances for images in the JAFFE database. The probability of correct classification using the pseudodistance measure $d_{\beta }$ (see text for details) is plotted against $\beta =1/T$. The solid line corresponds to the arithmetic means computed over 10000 classification experiments (see text for details). Shaded areas represent standard deviations.

Figure 3

The average running times for FreeOT without (black circles) and with reset (red circles) and for EntropyOT used for comparing two images is plotted against the number of key points in the images (see text for details).