依隨智能手機(jī)的大規(guī)模普及，數(shù)字?jǐn)z影已經(jīng)成為很多人生活中不可或缺的習(xí)慣。隨著數(shù)字圖像處理技術(shù)的蓬勃發(fā)展，PS作為數(shù)字圖像處理的代名詞（photoshop），在普羅大眾中早已耳熟能詳。數(shù)字圖像處理中，最為基本的算法非“色彩變換”（Color Transfer）莫屬。

圖1. 直方圖均衡化結(jié)果（histogram equalization）。

直方圖均衡化是提高灰度圖像對(duì)比度的常見算法。如圖1所示，左側(cè)輸入圖像的灰度分布在一個(gè)狹窄區(qū)域，朦朧昏暗；右側(cè)是直方圖均衡化的結(jié)果，清晰明亮，對(duì)比鮮明。我們?cè)O(shè)輸入圖像像素的灰度為一隨機(jī)變量，其取值范圍為單位區(qū)間，其概率測(cè)度為，直方圖均衡化算法的核心就是求灰度空間（單位區(qū)間）到自身的一個(gè)映射，這一映射將變換成均勻分布。

圖2. 基于最優(yōu)傳輸?shù)纳首儞Q。

數(shù)據(jù)驅(qū)動(dòng)的色彩變換可以視作是直方圖均衡化的直接推廣。圖2顯示了一個(gè)算例，左側(cè)是輸入圖像，陰霾遍布下的麥地，陰郁蒼涼，中間是范例圖像，晴空下的麥穗，右圖是輸出圖像，一掃陰霾，麥浪金黃，明媚爽朗。我們將圖像中的每個(gè)像素顏色表示成（紅，綠，藍(lán)）三元組，所有可能的顏色空間表示成單位立方體，像素為矢量值的隨機(jī)變量，取值于顏色空間。輸入圖像的顏色分布的概率測(cè)度為，范例圖像的顏色分布的概率測(cè)度為。我們尋找顏色空間的自映射，將概率測(cè)度映成概率測(cè)度。將輸入圖像每個(gè)像素的顏色進(jìn)行變換，從而生成輸出圖像。

圖3. 輸入圖像。

圖4. 范例圖像。

圖5. 輸出圖像。

圖3至圖5展示了另外一個(gè)例子，輸入圖像顏色的概率測(cè)度變換成范例圖像顏色的概率測(cè)度，從而生成了輸出圖像。圖6的鸚鵡圖像也進(jìn)行了顏色變換。

圖6. 輸入的鸚鵡圖像。

圖7. 示例圖像。

圖8. 輸出圖像。

這些顏色變換的算法是基于最優(yōu)傳輸理論（Optimal Mass Transportation）。最近，最優(yōu)傳輸理論被廣泛應(yīng)用于工程和醫(yī)療中的諸多領(lǐng)域，例如直接應(yīng)用于圖像顏色變換、圖像注冊(cè)、曲面保面積參數(shù)化和體的保體元參數(shù)化、曲面或體的注冊(cè)。特別是在機(jī)器學(xué)習(xí)中，最優(yōu)傳輸理論起到了至關(guān)重要的作用。下面我們簡(jiǎn)單介紹最優(yōu)傳輸理論梗概。

假設(shè)和是完備，可分的度量空間，和是分別定義在和空間上的概率測(cè)度。傳輸代價(jià)函數(shù)為光滑函數(shù)，代表從點(diǎn)傳輸單位質(zhì)量到點(diǎn)所花費(fèi)的代價(jià)。令為從空間到空間的映射，將推前為空間上的概率測(cè)度，其定義如下：令為任意的波萊爾集，則

。

歷史上，法國(guó)數(shù)學(xué)家蒙日（Monge）早在1781年就提出了最優(yōu)傳輸問題，我們?cè)谶@里稱之為蒙日問題：求保測(cè)度的具有最小傳輸代價(jià)的映射，

。

這一問題的提法非常具有普適性，特別是它具有天然的經(jīng)濟(jì)學(xué)意義。

我們可以用下面的例子來理解最優(yōu)傳輸問題的提法：假設(shè)空間和都是美國(guó)的疆域，是某一年馬鈴薯的畝產(chǎn)率，在點(diǎn)，是當(dāng)年每英畝出產(chǎn)馬鈴薯的噸數(shù)；是當(dāng)年馬鈴薯的每英畝消耗率，在點(diǎn)，是當(dāng)年每英畝消耗掉的馬鈴薯的噸數(shù)。美國(guó)政府需要制定一個(gè)馬鈴薯傳輸方案，，將馬鈴薯從生產(chǎn)地點(diǎn)運(yùn)輸?shù)较M(fèi)地點(diǎn)，使得全國(guó)達(dá)到供需平衡，即
，同時(shí)使得總的傳輸代價(jià)最小。這恰恰就是最有傳輸問題。

蒙日提出的傳輸代價(jià)是距離，，數(shù)學(xué)分析相對(duì)困難。因此最優(yōu)傳輸問題的理論發(fā)展一直停滯不前，歲月蹉跎了一百五十多年，直至1940年代。

蒙日的提法中，保測(cè)度的映射所構(gòu)成的空間不具備緊性，這為問題的解決帶來了本質(zhì)的難度。1939年，俄羅斯數(shù)學(xué)家康塔洛維奇（Kantorovich）將傳輸映射（transportation map）推廣為傳輸方案（transportation plan），從而巧妙地將問題轉(zhuǎn)化，帶來實(shí)質(zhì)性的突破。

在蒙日的傳輸映射中，任意一點(diǎn)處生產(chǎn)的所有馬鈴薯，只能運(yùn)送到唯一的像點(diǎn)。但是在實(shí)際生活中，一點(diǎn)處生產(chǎn)的馬鈴薯可以運(yùn)送到多個(gè)像點(diǎn)，甚至是多個(gè)區(qū)域，這就是所謂的傳輸方案。換句話說，傳輸映射每點(diǎn)的像是一個(gè)點(diǎn)，傳輸方案每點(diǎn)的像是一個(gè)集合。

為了表達(dá)傳輸方案，康塔洛維奇在空間上定義了一個(gè)概率測(cè)度，代表點(diǎn)處生產(chǎn)的馬鈴薯有多少運(yùn)送到了點(diǎn)。那么顯然，處所生產(chǎn)的所有馬鈴薯為，點(diǎn)處所收到的所有馬鈴薯為。我們定義投影映射如下：

,

那么如上邊際概率條件可以表示為:

。

康塔洛維奇關(guān)于最優(yōu)傳輸問題的提法如下：。

我們可以看到可容許概率測(cè)度的泛函空間是一個(gè)凸集合，關(guān)于的能量泛函是一個(gè)線性泛函，緊凸集合上的線性函數(shù)達(dá)到最大和最小值，如此，康塔洛維奇的最優(yōu)傳輸方案的存在性得以保證。

康塔洛維奇將空間和表示成離散點(diǎn)集，和；將概率測(cè)度和離散成狄拉克測(cè)度，和; 同時(shí)將傳輸方案離散成狄拉克測(cè)度。這樣，最優(yōu)傳輸方案問題就被轉(zhuǎn)換成經(jīng)典的線性規(guī)劃問題，

雖然理論上線性規(guī)劃問題的復(fù)雜度為NP，實(shí)際中，我們可以用經(jīng)典的單純形法或者內(nèi)點(diǎn)法快速解出。

鑒于最優(yōu)傳輸問題的巨大經(jīng)濟(jì)價(jià)值，康塔洛維奇獲得了1975年度的諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。

康塔洛維奇的提法將最優(yōu)傳輸問題轉(zhuǎn)化成凸限制下的線性優(yōu)化問題，這個(gè)問題存在對(duì)偶的提法。我們可以從對(duì)偶問題上看出更多的幾何直覺。我們將邊際概率測(cè)度的限制條件換種方式表達(dá)，考察下面的泛函：

這里是有界連續(xù)函數(shù)。顯然，聯(lián)合概率分布，則泛函值為0；否則，泛函值為。由此，康塔洛維奇問題可以等價(jià)表述為：

注意，在這里測(cè)度沒有任何限制，其在總空間上的積分也可以不等于1。

在特定條件下，我們可以交換極小，極大算子，從而得到：

我們?cè)倏疾旌笠豁?xiàng)

如果在某一點(diǎn)處，成立嚴(yán)格的不等式：，我們?nèi)?/span>，則上式趨于。反之，如果，并且在某點(diǎn)處等號(hào)成立，則上式為0。由此，我們可以得到對(duì)偶問題的提法：

,

這里是有界連續(xù)函數(shù)。

通常情況下，蒙日泛函，對(duì)偶泛函和康塔洛維奇泛函滿足不等式，

,

問題的核心在于：何時(shí)等號(hào)成立？何時(shí)最優(yōu)傳輸方案稱為最優(yōu)傳輸映射？

對(duì)偶問題具有非常直觀的幾何洞察，為此我們先考察凸幾何中的勒讓德變換(Legendre transform)。

圖9. 勒讓德變換。

如圖9所示，假設(shè)是一個(gè)凸函數(shù)，亦即其圖為一凸曲線。則的圖，是其所有切線的包絡(luò)（envelope）。斜率為的切線記為，方程表示為

，

這里截距定義為：

就是的勒讓德變換，它們互為勒讓德共軛，換言之，。幾何上，的勒讓德變換給出了的所有切線，這些切線的包絡(luò)給出了。每一個(gè)對(duì)應(yīng)著唯一的，這里。

圖10. c-變換。

我們可以將勒讓德變換進(jìn)行推廣，如圖10所示，假設(shè)是單參數(shù)曲線族，以變?cè)?/span>為參數(shù)，曲線族的包絡(luò)為。這里，曲線由傳輸代價(jià)函數(shù)所決定，其方程表示為：

這里，我們稱為的c-變換（c-transform），

。

如果，則我們說為c-凸函數(shù)（c-convex）。

對(duì)偶問題（DP）可以進(jìn)一步表示成如下形式：

。

根據(jù)以上的討論，我們看到對(duì)于最優(yōu)傳輸方案，其質(zhì)量主要集中于集合

,

換言之。如果是n維流形，對(duì)于任意，由唯一決定，則最優(yōu)傳輸方案成為最優(yōu)傳輸映射。

根據(jù)包絡(luò)的幾何特征，假設(shè)在處，和相切，我們得到必要條件：

,

圖11. 扭曲條件。

我們得到映射 ，如果這一映射對(duì)任意都是單射，則我們說代價(jià)函數(shù)滿足扭曲條件（twist condition）。可以看出，如果代價(jià)函數(shù)滿足扭曲條件，則對(duì)于任意的，滿足相切條件的唯一，因此映射就是最優(yōu)傳輸映射。

圖11展示了一個(gè)不滿足扭曲條件的例子，在處，存在同時(shí)滿足相切條件。

假如，代價(jià)函數(shù)，這里是一個(gè)嚴(yán)格的凸函數(shù)，那么它滿足扭曲條件，，則傳輸映射有表達(dá)式：

這里，我們?cè)僖淮斡玫搅死兆尩伦儞Q。

作為這套理論的應(yīng)用，我們給出兩個(gè)在日常生活中最為常見的例子。

考察代價(jià)函數(shù)為距離，

則h為嚴(yán)格凸的函數(shù)，最優(yōu)傳輸映射存在。如果我們考慮距離情形，，則其勒讓德變換為恒同變換，最優(yōu)傳輸映射公式為：

我們令，則得到所謂的Brenier定理：距離的最優(yōu)傳輸映射由一個(gè)函數(shù)的梯度給出。

我們?cè)倏紤]保持測(cè)度的性質(zhì)：，我們就會(huì)得到著名的蒙日-安培方程。梯度映射的雅克比行列式為海森矩陣，

因此，最優(yōu)傳輸映射和蒙日-安培方程具有非常親密的血緣關(guān)系，而后者也和傳統(tǒng)的閔科夫斯基問題（Minkowski Problem）有很深的淵源^[5]。

從計(jì)算角度講，最優(yōu)傳輸映射和計(jì)算幾何中的加權(quán)Voronoi圖（Power Voronoi Diagram）是彼此等價(jià)的。我們?cè)谶@里進(jìn)行一番推導(dǎo)。

我們?cè)O(shè)是歐式空間中的緊凸集，為離散點(diǎn)集，

，

配備狄拉克測(cè)度：

。

考察對(duì)偶問題，則為離散函數(shù)，定義在離散點(diǎn)集上，設(shè)，則

，

我們?cè)诳疾?/span>的c-變換，得到

,

固定,函數(shù)關(guān)于為凹函數(shù)。由此，我們得到Power Voronoi圖，

我們得到

這里是相應(yīng)的Voronoi胞腔的-體積。

由此，我們得到對(duì)偶問題為：最大化如下能量

這一能量為凹函數(shù)，其梯度為

我們可以用爬山法來進(jìn)行優(yōu)化。圖12,13顯示了保面元和保體元的同胚映射，其計(jì)算就是基于這個(gè)算法。更多的計(jì)算工具，數(shù)據(jù)測(cè)試集合可以在^[2]中找到。

圖12. 曲面保面積參數(shù)化^[4]。

圖13. 保體元的參數(shù)化^[3]。

一個(gè)黎曼流形上的所有概率測(cè)度構(gòu)成一個(gè)無窮維的流形，即所謂的Wasserstein空間。任意兩個(gè)概率測(cè)度之間存在最優(yōu)傳輸映射，這個(gè)映射的傳輸代價(jià)給出了兩個(gè)概率測(cè)度之間的距離，被稱為是Wasserstein距離。因此，Wasserstein空間是一個(gè)黎曼流形。

在工程和醫(yī)學(xué)的諸多領(lǐng)域，算法的核心是尋找一個(gè)概率測(cè)度，例如機(jī)器學(xué)習(xí)算法。Wasserstein距離給出了衡量概率測(cè)度相似程度的嚴(yán)密方法，這是為什么近幾年來最優(yōu)傳輸理論異?；馃岬母驹颉?br>

但是，計(jì)算最優(yōu)傳輸本身并不容易，目前計(jì)算機(jī)視覺、圖形學(xué)、機(jī)器學(xué)習(xí)、醫(yī)學(xué)圖像的研究者都努力用各種優(yōu)化方法，工程技巧來提高計(jì)算效率。我們可以預(yù)見在不久的將來，最優(yōu)傳輸理論將會(huì)在更多的實(shí)際工程中大放異彩。

（丘成桐先生邀請(qǐng)杜克大學(xué)的劉建國(guó)教授在清華大學(xué)數(shù)學(xué)科學(xué)中心，于2016年暑期學(xué)校，講述最優(yōu)傳輸理論課程^[1]。本文根據(jù)課堂筆記整理而成。筆者鳴謝丘成桐先生和劉建國(guó)教授。）