色彩变换的PS神器是怎样炼成的？

撰文

顾险峰（纽约州立大学石溪分校终身教授）

引言

依随智能手机的大规模普及，数字摄影已经成为很多人生活中不可或缺的习惯。随着数字图像处理技术的蓬勃发展，PS作为数字图像处理的代名词（photoshop），在普罗大众中早已耳熟能详。数字图像处理中，最为基本的算法非“色彩变换”（Color Transfer）莫属。

图1. 直方图均衡化结果（histogram equalization）。

直方图均衡化是提高灰度图像对比度的常见算法。如图1所示，左侧输入图像的灰度分布在一个狭窄区域，朦胧昏暗；右侧是直方图均衡化的结果，清晰明亮，对比鲜明。我们设输入图像像素的灰度为一随机变量，其取值范围为单位区间，其概率测度为，直方图均衡化算法的核心就是求灰度空间（单位区间）到自身的一个映射，这一映射将变换成均匀分布。

图2. 基于最优传输的色彩变换。

数据驱动的色彩变换可以视作是直方图均衡化的直接推广。图2显示了一个算例，左侧是输入图像，阴霾遍布下的麦地，阴郁苍凉，中间是范例图像，晴空下的麦穗，右图是输出图像，一扫阴霾，麦浪金黄，明媚爽朗。我们将图像中的每个像素颜色表示成（红，绿，蓝）三元组，所有可能的颜色空间表示成单位立方体，像素为矢量值的随机变量，取值于颜色空间。输入图像的颜色分布的概率测度为，范例图像的颜色分布的概率测度为。我们寻找颜色空间的自映射，将概率测度映成概率测度。将输入图像每个像素的颜色进行变换，从而生成输出图像。

图3. 输入图像。

图4. 范例图像。

图5. 输出图像。

图3至图5展示了另外一个例子，输入图像颜色的概率测度变换成范例图像颜色的概率测度，从而生成了输出图像。图6的鹦鹉图像也进行了颜色变换。

图6. 输入的鹦鹉图像。

图7. 示例图像。

图8. 输出图像。

这些颜色变换的算法是基于最优传输理论（Optimal Mass Transportation）。最近，最优传输理论被广泛应用于工程和医疗中的诸多领域，例如直接应用于图像颜色变换、图像注册、曲面保面积参数化和体的保体元参数化、曲面或体的注册。特别是在机器学习中，最优传输理论起到了至关重要的作用。下面我们简单介绍最优传输理论梗概。

蒙日关于最优传输问题的提法

假设和是完备，可分的度量空间，和是分别定义在和空间上的概率测度。传输代价函数为光滑函数，代表从点传输单位质量到点所花费的代价。令为从空间到空间的映射，将推前为空间上的概率测度，其定义如下：令为任意的波莱尔集，则

。

历史上，法国数学家蒙日（Monge）早在1781年就提出了最优传输问题，我们在这里称之为蒙日问题：求保测度的具有最小传输代价的映射，

。

这一问题的提法非常具有普适性，特别是它具有天然的经济学意义。

我们可以用下面的例子来理解最优传输问题的提法：假设空间和都是美国的疆域，是某一年马铃薯的亩产率，在点，是当年每英亩出产马铃薯的吨数；是当年马铃薯的每英亩消耗率，在点，是当年每英亩消耗掉的马铃薯的吨数。美国政府需要制定一个马铃薯传输方案，，将马铃薯从生产地点运输到消费地点，使得全国达到供需平衡，即
，同时使得总的传输代价最小。这恰恰就是最有传输问题。

蒙日提出的传输代价是距离，，数学分析相对困难。因此最优传输问题的理论发展一直停滞不前，岁月蹉跎了一百五十多年，直至1940年代。

康塔洛维奇的提法

蒙日的提法中，保测度的映射所构成的空间不具备紧性，这为问题的解决带来了本质的难度。1939年，俄罗斯数学家康塔洛维奇（Kantorovich）将传输映射（transportation map）推广为传输方案（transportation plan），从而巧妙地将问题转化，带来实质性的突破。

在蒙日的传输映射中，任意一点处生产的所有马铃薯，只能运送到唯一的像点。但是在实际生活中，一点处生产的马铃薯可以运送到多个像点，甚至是多个区域，这就是所谓的传输方案。换句话说，传输映射每点的像是一个点，传输方案每点的像是一个集合。

为了表达传输方案，康塔洛维奇在空间上定义了一个概率测度，代表点处生产的马铃薯有多少运送到了点。那么显然，处所生产的所有马铃薯为，点处所收到的所有马铃薯为。我们定义投影映射如下：

,

那么如上边际概率条件可以表示为:

。

康塔洛维奇关于最优传输问题的提法如下：。

我们可以看到可容许概率测度的泛函空间是一个凸集合，关于的能量泛函是一个线性泛函，紧凸集合上的线性函数达到最大和最小值，如此，康塔洛维奇的最优传输方案的存在性得以保证。

康塔洛维奇将空间和表示成离散点集，和；将概率测度和离散成狄拉克测度，和; 同时将传输方案离散成狄拉克测度。这样，最优传输方案问题就被转换成经典的线性规划问题，

虽然理论上线性规划问题的复杂度为NP，实际中，我们可以用经典的单纯形法或者内点法快速解出。

鉴于最优传输问题的巨大经济价值，康塔洛维奇获得了1975年度的诺贝尔经济学奖。

对偶提法

康塔洛维奇的提法将最优传输问题转化成凸限制下的线性优化问题，这个问题存在对偶的提法。我们可以从对偶问题上看出更多的几何直觉。我们将边际概率测度的限制条件换种方式表达，考察下面的泛函：

这里是有界连续函数。显然，联合概率分布，则泛函值为0；否则，泛函值为。由此，康塔洛维奇问题可以等价表述为：

注意，在这里测度没有任何限制，其在总空间上的积分也可以不等于1。

在特定条件下，我们可以交换极小，极大算子，从而得到：

我们再考察后一项

如果在某一点处，成立严格的不等式：，我们取，则上式趋于。反之，如果，并且在某点处等号成立，则上式为0。由此，我们可以得到对偶问题的提法：

,

这里是有界连续函数。

通常情况下，蒙日泛函，对偶泛函和康塔洛维奇泛函满足不等式，

,

问题的核心在于：何时等号成立？何时最优传输方案称为最优传输映射？

勒让德变换-包络

对偶问题具有非常直观的几何洞察，为此我们先考察凸几何中的勒让德变换(Legendre transform)。

图9. 勒让德变换。

如图9所示，假设是一个凸函数，亦即其图为一凸曲线。则的图，是其所有切线的包络（envelope）。斜率为的切线记为，方程表示为

，

这里截距定义为：

就是的勒让德变换，它们互为勒让德共轭，换言之，。几何上，的勒让德变换给出了的所有切线，这些切线的包络给出了。每一个对应着唯一的，这里。

图10. c-变换。

我们可以将勒让德变换进行推广，如图10所示，假设是单参数曲线族，以变元为参数，曲线族的包络为。这里，曲线由传输代价函数所决定，其方程表示为：

这里，我们称为的c-变换（c-transform），

。

如果，则我们说为c-凸函数（c-convex）。

对偶问题（DP）可以进一步表示成如下形式：

。

扭曲条件

根据以上的讨论，我们看到对于最优传输方案，其质量主要集中于集合

,

换言之。如果是n维流形，对于任意，由唯一决定，则最优传输方案成为最优传输映射。

根据包络的几何特征，假设在处，和相切，我们得到必要条件：

,

图11. 扭曲条件。

我们得到映射 ，如果这一映射对任意都是单射，则我们说代价函数满足扭曲条件（twist condition）。可以看出，如果代价函数满足扭曲条件，则对于任意的，满足相切条件的唯一，因此映射就是最优传输映射。

图11展示了一个不满足扭曲条件的例子，在处，存在同时满足相切条件。

假如，代价函数，这里是一个严格的凸函数，那么它满足扭曲条件，，则传输映射有表达式：

这里，我们再一次用到了勒让德变换。

作为这套理论的应用，我们给出两个在日常生活中最为常见的例子。

蒙日-安培方程

考察代价函数为距离，

则h为严格凸的函数，最优传输映射存在。如果我们考虑距离情形，，则其勒让德变换为恒同变换，最优传输映射公式为：

我们令，则得到所谓的Brenier定理：距离的最优传输映射由一个函数的梯度给出。

我们再考虑保持测度的性质：，我们就会得到著名的蒙日-安培方程。梯度映射的雅克比行列式为海森矩阵，

因此，最优传输映射和蒙日-安培方程具有非常亲密的血缘关系，而后者也和传统的闵科夫斯基问题（Minkowski Problem）有很深的渊源^[5]。

加权Voronoi图

从计算角度讲，最优传输映射和计算几何中的加权Voronoi图（Power Voronoi Diagram）是彼此等价的。我们在这里进行一番推导。

我们设是欧式空间中的紧凸集，为离散点集，

，

配备狄拉克测度：

。

考察对偶问题，则为离散函数，定义在离散点集上，设，则

，

我们在考察的c-变换，得到

,

固定,函数关于为凹函数。由此，我们得到Power Voronoi图，

我们得到

这里是相应的Voronoi胞腔的-体积。

由此，我们得到对偶问题为：最大化如下能量

这一能量为凹函数，其梯度为

我们可以用爬山法来进行优化。图12,13显示了保面元和保体元的同胚映射，其计算就是基于这个算法。更多的计算工具，数据测试集合可以在^[2]中找到。

图12. 曲面保面积参数化^[4]。

图13. 保体元的参数化^[3]。

小结

一个黎曼流形上的所有概率测度构成一个无穷维的流形，即所谓的Wasserstein空间。任意两个概率测度之间存在最优传输映射，这个映射的传输代价给出了两个概率测度之间的距离，被称为是Wasserstein距离。因此，Wasserstein空间是一个黎曼流形。

在工程和医学的诸多领域，算法的核心是寻找一个概率测度，例如机器学习算法。Wasserstein距离给出了衡量概率测度相似程度的严密方法，这是为什么近几年来最优传输理论异常火热的根本原因。

但是，计算最优传输本身并不容易，目前计算机视觉、图形学、机器学习、医学图像的研究者都努力用各种优化方法，工程技巧来提高计算效率。我们可以预见在不久的将来，最优传输理论将会在更多的实际工程中大放异彩。

（丘成桐先生邀请杜克大学的刘建国教授在清华大学数学科学中心，于2016年暑期学校，讲述最优传输理论课程^[1]。本文根据课堂笔记整理而成。笔者鸣谢丘成桐先生和刘建国教授。）

参考资料

[1] Fillipo Santambrogio, Optimal Transport for Applied Mathematicians - Calculus of Variations, PDEs and Modeling

[2] http://www3.cs./~gu/software/omt/index.html

[3] Kehua Su, Wei Chen, Na Lei, Junwei Zhang, Kun Qian and Xianfeng Gu, Volume Preserving Mesh Parameterization based on Optimal Mass Transportation, Journal of Computer-Aided Design (CAD), 2016.

[4] Xin Zhao, Zhengyu Su, Xianfeng David Gu, Arie Kaufman, Jian Sun, Jie Gao, Feng Luo, Area-preservation Mapping using Optimal Mass Transport, IEEE TVCG, 19（12）, Pages 2838-2847, 2013.

[5] Xianfeng Gu, Feng Luo, Jian Sun and Shing-Tung Yau, Variational Principles forMinkowski Type Problems, Discrete Optimal Transport, and Discrete Monge-Ampere
Equations, Vol. 20, No. 2, pp. 383-398, Asian Journal of Mathematics (AJM), April 2016.