依随智能手机的大规模普及,数字摄影已经成为很多人生活中不可或缺的习惯。随着数字图像处理技术的蓬勃发展,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图(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.stonybrook.edu/~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.
投稿、授权等请联系:iscientists@126.com
您可回复"年份+月份"(如201510),获取指定年月文章,或返回主页点击子菜单获取或搜索往期文章。
赛先生由百人传媒投资和创办,文小刚、刘克峰、颜宁三位国际著名科学家担任主编,告诉你正在发生的科学。上帝忘了给我们翅膀,于是,科学家带领我们飞翔。
微信号:iscientists
▲
长按图片识别二维码关注我们