基于高维点云分布的最优传输问题的研究

阮一鸣

摘 要：最优传输问题是寻求相对于给定的代价函数，把一种分布转化為另一种分布的最有效的方式，其具有较为深远的价值，其中基于点云的最优传输问题更是得到广泛的关注。针对高维的点云分布的最优传输问题，利用了分片最优传输的理论及其对应的优化模型，提出一个改进梯度迭代的算法，以二维、三维点云分布为例进行数值实验，并将其与经典的方法进行比较，验证模型与算法的有效性。实验结果表明，本文模型及其算法在标准差、峰值信噪比、平均梯度等指标均有更高的性能。

关键词：最优传输;Wasserstein距离;点云分布;随机梯度迭代

中图分类号：O212.4      文献标识码：A

Research on Optimal Transport Problem Based 

on High Dimensional Point Cloud Distribution

RUAN Yiming

（School of Science， Hohai University， Nanjing，Jiangsu 211100，China）

Abstract：The problem of optimal transport is to find the most effective way to transform one distribution into another relative to a given cost function. It has farreaching value， among which the problem of optimal transport based on point cloud has gained wide attention. Aiming at the problem of optimal transport of highdimensional point cloud distribution， using the theory of piecewise optimal transport and its corresponding optimization model， this paper proposes an improved gradient iterative algorithm. Taking twodimensional and threedimensional point cloud distribution as examples， numerical experiments are carried out and compared with classical methods to verify the effectiveness of the model and algorithm. Experimental results show that the model and its algorithm have higher performance in Standard Deviation， Peak Signal to Noise Ratio， Average Gradient and other indicators.

Key words：optimal transport; Wasserstein distance; point cloud distribution; random gradient iteration

最优传输问题是寻求相对于给定的代价函数，把一种分布转化为另一种分布的最有效的方式，其具有较为深远的价值，其中基于点云的最优传输问题更是得到广泛的关注，例如运输问题、颜色迁移等，其中最为常见的便是二维、三维点云分布的应用问题，在计算机图形学、计算机视觉、医学图像处理以及深度学习等方面都有显著的效果[1-4]。

最优传输问题的核心是Wasserstein距离，近年来，关于Wasserstein距離的计算得到了蓬勃的发展，但关于Wasserstein距离的计算尤其是高维点云分布仍然具有一定的局限性，目前可以进行显式计算的只有一维分布或者高斯分布的情形[4]，因此如何准确快速求解高维的点云分布的最优传输问题是最优传输领域的一个难点。关于一维情形点云分布的最优传输问题，已经涌现了许多算法及理论，例如匈牙利算法[5]、拍卖算法[6]、经典的线性规划算法[7]、熵正则化算法[8]等，但对于较为常见的高维的点云分布的最优传输问题的研究仍然较少，Rabin[9]等首次提出了用分片Wasserstein距离来求解高维的概率分布及Wasserstein重心，结果也表明了算法的有效性，但其收敛性能有时仍然较不稳定;Paulin[10]等利用分片最优传输重构相应的点云样本任意维样本分布，以提高蒙特卡罗积分的精度;Bonneel[11]等将分片Wasserstein距离与拉东变换应用于求解任意测度的Wasserstein重心; Xiao[12]等探讨了在三维颜色空间中的点云分布的颜色传输，其主要考虑对三维像素点云进行颜色迁移的计算;Reinhard[13]等探讨了三维点云分布在不同色彩空间的传输过程，其所考虑在经典的颜色空间中进行颜色的迁移探究，虽然输入输出是RGB像素值，但是中间进行算法处理时很少直接更改RGB值，因此对结果仍然具有一定的影响。文献[14]、[15]则介绍主流的梯度算法及其改进算法的基本理论，给出相应的介绍及其理论的分析证明。

本文则针对高维情形下点云分布的最优传输问题进行探究，具体以二维、三维点云分布为例，受文献[9]的启发，同时基于文献[14]、[15]的基本理论，利用分片Wasserstein距离的相应理论，将其投影成一维分布，其积分形式选用相应的离散和进行近似，考虑利用随机梯度下降迭代更新相应的分布，同时，鉴于传统的随机梯度下降法容易收敛到局部最优[16]，并且容易被困在鞍点，收敛性能较差，故本文对传统的随机梯度下降法进行了改进，在其中加入Nesterov Momentum项[14-15]以保证更新的时候在一定程度上保留之前更新的方向，同时利用当前部分的梯度微调最终的更新方向以在一定程度上增加稳定性，并且还有一定摆脱局部最优的能力，最后利用数值实验验证本文算法及其模型的有效性。

1 分片Wasserstein距离理论

1.1 一维最优传输

考虑如下的两个点云分布μ，v，其所对应的数据X=（x1，x2，…，xn），Y=（y1，y2，…，yn），假定其满足下式：

即每个点云的概率权重相等，不失一般性。假定每个点云的具体位置距离已预先做好排序即x1≤x2≤…≤xn，y1≤…≤yn，即可得到如下简单的形式，点云分布所对应的s维Wasserstein距离为：

1.2 分片Wasserstein距离

在实践应用中，对Wasserstein距离的计算仍然有较高的要求，且Ws在优化包含Wasserstein距离的函数点云的问题中较难处理，鉴于这些原因，我们现在考虑分布之间的替代度量即基于一维投影之间的运输成本，同时为了将高维的点云分布转化为一维点云分布从而更好地计算Wasserstein距离，这里我们引入分片Wasserstein距离的概念，其基本的思想是针对两个高维分布随机找不同的方向进行投影，然后计算两个一维的投影点云的Wasserstein距离，最后将从不同投影方向所得到的一维分布的Wasserstein距离进行求和，即得到了相应的分片Wasserstein距离。首先给出分片Wasserstein距离的定义：

其中θ表示一个模长为1的线性投影， 它将原本高维（d维）的X或者Y投影到了一维空间。根据上述定义叙述，可以将分片Wasserstein距离用一维的最优分配来表示：

其中SW2指代上述的度量为分片Wasserstein距离。 

2 理论与算法

2.1 基于梯度优化的算法

在许多机器学习任务中，为了求解方便可将机器学习算法模型简化为经验风险，即求解最优化模型：

是第l个样本关于参数x的损失函数。当样本容量足够大时，经验风险最小化能保证有良好的学习效果，因此在实际应用广泛中被采用[14-15]。

2.1.1 随机梯度下降算法

随机梯度下降法（SGD）算法及其众多变种算法都是机器学习中应用最广泛的优化算法，是求解大规模学习问题的一种有效方法。SGD算法以基本的梯度下降形式更新迭代，在每轮更新参数时，仅选择一个或几个样本计算其梯度，并以此梯度作为全局梯度的估计值，极大降低了算法复杂度。其参数更新公式为：

2.1.2 标准动量法

随机梯度下降法可广泛应用于解诸多优化问题，但其依然存在很多缺陷，例如该算法有时达到最优解的速度很慢。对上述问题进行优化，标准动量方法增加一个动量项的方式使得目标函数加速收敛，通过累计参数之前梯度指数衰减的平均值，防止梯度计算时过度震荡，使目标函数更快达到局部最优。其算法更新迭代规则如下：

2.1.3 Nesterov Momentum动量法

带有Nesterov Momentum项的随机梯度下降算法是一阶优化方法，用于提高常规下降的稳定性和收敛性。Nesterov动量是Momentum的变种，即在计算参数梯度之前，前瞻一步，超前一个动量单位处xl+ηvl，可理解为往Momentum算法中加入一个校正因子。迭代过程中更新规则如下所示：

其中，xl表示模型参数，νl表示动量，η∈[0，1]表示动量系数，τl表示当前迭代的学习率，f（x）是目标函数。

与标准动量项不同的是，Nesterov动量是对某个位置的参数向量xl更新，取决于当前参数位置ηνl的最后一次动量更新。Nesterov动量相比标准动量项可以更有效地修正每次迭代较大且不适当的速度，这使得它比标准动量法更快，并且可以进一步降低损失函数的误差率。

2.2 算法基本理论

对于高维的情形，要得到相应的正交投影，对一些常用的算法例如线性规划算法、熵正则化算法来说则较难处理。受文献[9]、[14]、[15]的启发，本文则考虑利用随机梯度下降法来计算分布之间的分片Wasserstein投影，即随机寻找相应的投影方向将高维概率分布投影下来，将其转化为一维点云分布，然后计算两个一维情况下概率分布的Wasserstein距离。

首先计算关于μY局部最小的分片Wasserstein距离：

E（t）=W2（μt，μY）（10）

利用计算结果逼近，其中上式与分布X足够逼近且E是Cl连续函数。为得到逼近X的点云分布，数据考虑对E使用梯度下降法，从X开始进行迭代：

X（0）=X，X（l+1）=X（l）-τl

EΘ（X（l）+η×v（l））

X（l+1）=X（l）+v（l+1）（17）

其中η表示衰减因子，表示对先前方向的依赖程度，通常取值为0.9。且根据式（15），则式（17）迭代更新规则如下所示：

v（l+1）=η×v（l）-τl×（X（l）+η×v（l）-（l））

X（l+1）=X（l）+v（l+1）（18） 

综上，可得本文算法。

算法1 基于NMSGD的分片Wasserstein距离的计算算法

Require：点云分布数据X，Y，学习率τl，衰减因子η

Require：初始点云分布X（0）=X，初始动量v（0）

While 不满足停止准则 do

1：对X进行随机梯度法迭代， 初值迭代X（0）=X

2：计算上述投影算子P

3： 更新v（l+1）∶v（l+1）←η×v（l）-τl×EΘ（X（l）+η×v（l））

4：更新X（l+1）∶X（l+1）←X（l）+v（l+1）

end while

Output：Xl+1

3 数值实验

3.1 二维点云分布的最优传输问题

本文考虑对二维与三维点云分布数据进行数值实验。首先随机给出两组二维点云数据即d=2，点云数据个数为200，点云分布见图1。根据上述算法，对上述两组点云进行迭代计算P直至满足收敛。其中niter=1，3，10，100传输过程与最终的结果见图2与图3。

3.2 三维点云分布的最优传输问题

3.2.1 数值实验

对于三维情形的离散分布的最优传输问题即d=3，本文考虑对应的三维彩色图像，则其像素对应的离散分布即是三维的点云分布。给出两组两幅128*128的三维彩色图像见图4。

故对于上述三维点云分布数据，基于上述算法，利用随机梯度下降法最小化分片Wasserstein距離计算迭代次数niter=1，3，10，100的目标传输图像，具体迭代传输过程与结果见图5。

为验证本文算法，接下来将对其与图像迁移领域中几种有代表性的算法进行比较。文献[9]中，Rabin等人提出随机梯度算法，并将其应用于Wasserstein 重心，本节则将其应用于三维点云分布的最优传输问题;文献[12]中Xiao等提出了一种在三维颜色空间中对像素进行传输的算法;文献[13]中 Reinhard等人根据lαβ颜色空间中各通道互相不关联的特点，提出了一组适用于各颜色分量的色彩迁移算法。文献[12]、[13]所考虑在经典的颜色空间中进行颜色的迁移探究，本文则将其考虑在Wasserstein空间进行应用，同时基于文献[9]进行改进。以上方法及其所得的最终结果见图6。

3.2.2 评价指标

接下来利用标准差、峰值信噪比和平均梯度三个评价指标对结果图像进行评价。

（1）标准差

图像的均值表示图像的亮度，均值越大图像越亮，其中均值计算公式为：

u=1W×H∑Wi=1∑Hj=1f（i，j）（19）

而图像标准差反映了图像像素值与均值的离散程度，标准差越大说明图像的对比度越高.标准差计算公式为：

δ=1W×H∑Wi=1∑Hj=1[f（i，j）-u]2（20）

其中，W×H表示图像中像素点的个数，f（i，j）为（i，j）点处的灰度值。

（2）峰值信噪比

峰值信噪比（PSNR）是用于评价图像失真度的客观指标，峰值信噪比数值越大表示失真度越小，图像质量越好，其主要通过最大可能像素值fmax和均方误差（MSE）来定义，其中均方误差和峰值信噪比的计算公式为：

MSE=∑Wi=1∑Hj=1-f0（i，j）]2W×H（21）

PSNR=10lg10f2maxMSE （22）

其中，W×H表示圖像中像素点的个数，f（x，y）代表目标图像的像素点，f0（x，y）代表结果图中的像素点。

（3）平均梯度（Average gradient）

平均梯度反映图像的清晰程度，平均梯度越大，图像越清晰，图像层次越丰富，图像的平均梯度（AG）计算公式为：

AG=1W×H∑Wi=1∑Hj=1fx2+fy22（23）

其中，W×H表示图像中像素点的个数，fx表示水平方向的梯度，fy表示垂直方向的梯度。不同方法在两组实验中的不同指标结果及其比较见表1与表2。

从两组实验可以看出本文算法评价指标结果。MSE略低于文献[9]方法、PSNR略低于文献[13]方法外，其余指标结果均优于其他算法。综上，本文算法可较好地应用于求解点云分布的最优传输问题。

4 结 论

研究了高维点云分布数据的最优传输问题及其相关应用。基于一维点云分布的最优传输问题的基本理论，给出高维的点云分布的传输问题的计算理论及算法，以经典的二维、三维情形为例进行相应的数值实验，对于三维的情形也将其与经典的方法进行比较，验证模型与算法的有效性。

参考文献

[1] PEYRЁ G， CUTURI M. Computational optimal transport： with applications to data science [J]. Foundations and Trends in Machine Learning， 2019， 11（5-6）： 355-607. 

[2] PANARETOS V M， ZEMEL Y. Statistical aspects of  Wasserstein distances[J]. Annual review of statistics and its application， 2019， 6（1）： 405-431.

[3] 马丽涛， 边 伟. 最优传输理论及其在图像处理中的应用[J]. 运筹学学报， 2019， 23（3）： 109-125.

[4] VILLANI C. Optimal transport： old and new[M]. Berlin： Springer， 2009. 

[5] KUHN H W. The Hungarian method for the assignment  problem[J] .Naval Research Logistics Quarterly， 1995， 2（1-2）：83-97.

[6] BERTSEKAS D P. The auction algorithm： a distributed relaxation method for assignment problem[J]. Annals of Operations Research，1998， 14（1）： 105-123. 

[7] AURICCHIO G， BASSETTI F， GUALANDI S， et al. Computing Wasserstein barycenters via linear programming[C]. International Conference on Integration of Constraint Programming， Artificial Intelligence， and Operations Research. Springer， Cham， 2019： 355-363.

[8] CUTURI M.Sinkhorn distances： lightspeed computation of optimal transport[J]. Advances in Neural Information Processing Systems， 2013， 26： 2292-2300.

[9] RABIN J， PEYRЁ G， DELON J， et al.Wasserstein barycenter and its application to texture mixing[C]//In International Conference on Scale Space and Variational Methods in Computer Vision. Springer， Berlin， Heidelberg， 2011， 435-446. 

[10]PAULIN L， BONNEL N， COEURJOLLY D， et al. Sliced optimal transport sampling[J]. ACM Trans. Graph， 2020， 39（4）： 99-115.

[11]BONNEEL N， RABIN J， PEYRЁ G， et al. Sliced and radon wasserstein barycenters of measures[J]. Journal of Mathematical Imaging and Vision， 2015， 51（1）： 22-45.

[12]XIAO X， MA L. Color transfer in correlated color space[C]//Proceedings of the 2006 ACM International Conference on Virtual Reality Continuum and Its Applications. 2006： 305-309.

[13]REINHARD E， ADHIKHMIN M， GOOCH B， et al. Color transfer between images[J]. IEEE Computer Graphics and Applications， 2001， 21（5）： 34-41.

[14]SUTSKEVER I， MARTENS J， DAHL G， et al. On the importance of initialization and momentum in deep learning[C]//International Conference on Machine Learning. PMLR， 2013： 1139-1147.

[15]LOIZOU N， RICHTRIK P. Momentum and stochastic momentum for stochastic gradient， newton， proximal point and subspace descent methods[J]. Computational Optimization and Applications， 2020， 77（3）： 653-710.

[16]BOTTOU L. Online learning and stochastic approximations[J]. Online Learning in Neural Networks， 1998， 17（9）： 142-176.