[發(fā)明專(zhuān)利]一種高效的全離散最優(yōu)傳輸方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201711195311.8
• 申請(qǐng)日: 2017-11-24
• 公開(kāi)（公告）號(hào): CN108022005A
• 公開(kāi)（公告）日: 2018-05-11
• 發(fā)明（設(shè)計(jì)）人: 蘇科華;陳彩玲;焦沖;顧險(xiǎn)峰
• 申請(qǐng)（專(zhuān)利權(quán)）人: 武漢大學(xué)
• 主分類(lèi)號(hào): G06Q10/04
• 分類(lèi)號(hào): G06Q10/04;G06F17/16
• 代理公司: 武漢科皓知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 42222
• 代理人: 魏波

本發(fā)明公開(kāi)了一種高效的全離散最優(yōu)傳輸方法，首先將源區(qū)域和概率測(cè)度離散化表示，輸入目標(biāo)離散點(diǎn)，給每個(gè)目標(biāo)離散點(diǎn)賦予一個(gè)狄拉克測(cè)度；初始化截距向量，將源區(qū)域離散點(diǎn)的坐標(biāo)和截距向量的系數(shù)用矩陣存儲(chǔ)，將目標(biāo)離散點(diǎn)的坐標(biāo)及截距向量用矩陣存儲(chǔ)；每次迭代過(guò)程中，通過(guò)矩陣相乘、根據(jù)行最大值將離散點(diǎn)分類(lèi)的方法構(gòu)造近似離散加權(quán)維諾圖；求全離散最優(yōu)傳輸?shù)哪芰亢瘮?shù)及其梯度；更新截距向量；循環(huán)直到傳輸映射的凸能量達(dá)到極小值，得到最終的全離散最優(yōu)傳輸?shù)慕狻１景l(fā)明簡(jiǎn)單高效，易于實(shí)現(xiàn)，可通過(guò)多線程或CUDA等并行計(jì)算技術(shù)進(jìn)一步加速提高計(jì)算效率，可用于求解大規(guī)模最優(yōu)傳輸問(wèn)題。本發(fā)明與源區(qū)域的維度無(wú)關(guān)，適用于求解任意維度的最優(yōu)傳輸問(wèn)題。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)圖形圖像處理技術(shù)領(lǐng)域，涉及一種高效的全離散最優(yōu)傳輸新方法。

背景技術(shù)

法國(guó)數(shù)學(xué)家Monge最早提出了著名的最優(yōu)傳輸問(wèn)題，即設(shè)計(jì)一個(gè)將某質(zhì)量分布(X,μ)運(yùn)輸?shù)搅硪毁|(zhì)量分布(Y,ν)的最佳方案，滿(mǎn)足質(zhì)量相等∫Xμ(x)dx＝∫Yν(y)dy，同時(shí)使得運(yùn)輸代價(jià)最小。其中X,Y是兩個(gè)有界區(qū)域，μ,ν表示密度函數(shù)。1948年，俄羅斯數(shù)學(xué)家Kantorovich運(yùn)用線性規(guī)劃思想成功求解最優(yōu)傳輸問(wèn)題，并證明了其解的存在性和唯一性，由此獲得了1975年的諾貝爾經(jīng)濟(jì)獎(jiǎng)。如今，Monge-Kantorovich理論已取得大量的研究成果，極大地推動(dòng)了數(shù)學(xué)、經(jīng)濟(jì)學(xué)、醫(yī)學(xué)、人工智能、計(jì)算機(jī)科學(xué)、醫(yī)學(xué)等學(xué)科的發(fā)展。對(duì)于純粹數(shù)學(xué)，最優(yōu)傳輸理論可用于求解曲面等距嵌入問(wèn)題等凸幾何問(wèn)題，如Alexandrov問(wèn)題、Minkowski問(wèn)題；對(duì)于計(jì)算機(jī)數(shù)學(xué)，最優(yōu)傳輸算法可用于求解非線性的橢圓型偏微分方程，如蒙日-安培方程；對(duì)于經(jīng)濟(jì)學(xué)，最優(yōu)傳輸可以應(yīng)用于生產(chǎn)消耗運(yùn)輸、資源配置與調(diào)度等；對(duì)于人工智能，Wasserstein距離給出了衡量?jī)筛怕蕼y(cè)度分布距離的方法，在WGAN模型等深度學(xué)習(xí)領(lǐng)域發(fā)揮了顯著作用；此外，最優(yōu)傳輸理論在計(jì)算機(jī)視覺(jué)、三維模型參數(shù)化、曲面注冊(cè)、醫(yī)學(xué)成像等領(lǐng)域發(fā)揮著重大作用，取得很好的效果。

對(duì)Monge-Kantorovich的研究主要分為三類(lèi)：第一類(lèi)是全離散最優(yōu)傳輸，即源質(zhì)量分布(X,μ)和目標(biāo)質(zhì)量分布(Y,ν)都是離散的；第二類(lèi)是半離散最優(yōu)傳輸，即源質(zhì)量分布(X,μ)是連續(xù)的，而目標(biāo)質(zhì)量分布(Y,ν)是離散的；第三類(lèi)是連續(xù)最優(yōu)傳輸，即源質(zhì)量分布(X,μ)和目標(biāo)質(zhì)量分布(Y,ν)都是連續(xù)的。

最優(yōu)傳輸問(wèn)題的求解方法，歸納起來(lái)主要有三種：線性規(guī)劃方法、熵正則化距離近似方法以及基于計(jì)算幾何的凸優(yōu)化法。Kantorovich最早采用線性規(guī)劃思想求解最優(yōu)傳輸問(wèn)題。線性規(guī)劃的思想是將空間區(qū)域X和Y表示成離散點(diǎn)集，將概率測(cè)度μ,ν離散成狄拉克測(cè)度，進(jìn)而將最優(yōu)傳輸問(wèn)題轉(zhuǎn)換成線性規(guī)劃問(wèn)題來(lái)求解。最優(yōu)傳輸問(wèn)題的等效解決方案是Earth Mover’s Distance，簡(jiǎn)稱(chēng)EMD，也稱(chēng)Wasserstein距離，用于測(cè)量?jī)筛怕蕼y(cè)度分布之間的距離。以測(cè)地距離為基礎(chǔ)內(nèi)核，并用熱核來(lái)進(jìn)行近似，其迭代數(shù)值解方案具有線性收斂性，每次迭代只需要求解高斯卷積。與線性規(guī)劃法相比，該方法極大地提高了計(jì)算性能。但由于采用了近似方法簡(jiǎn)化問(wèn)題，其解并不是真正意義上的最優(yōu)傳輸。法國(guó)數(shù)學(xué)家與1991年Brenier證明，當(dāng)傳輸代價(jià)為L(zhǎng)2距離且傳輸區(qū)域?yàn)橥箙^(qū)域時(shí)，某個(gè)凸函數(shù)的梯度即為最優(yōu)傳輸映射，由此建立了最優(yōu)傳輸與凸幾何的聯(lián)系。近年來(lái)，顧險(xiǎn)峰對(duì)Brenier理論進(jìn)行離散化，基于變分法通過(guò)動(dòng)態(tài)構(gòu)造加權(quán)維諾圖(power diagram)以及采用凸優(yōu)化來(lái)求解最優(yōu)傳輸問(wèn)題。