SuperGlue中的最优传输算法详解

一、问题背景

  在SuperGlue中，作者将两图像中寻找对应特征点的问题看做是一个传输问题，即找到一个分配矩阵$P$，使得两个图像的特征集合$A$和$B$中的点尽可能多的正确对应。这与求解最优传输问题的过程不谋而合。

二、最优传输问题

  最优传输问题是以最小代价将一种概率分布变换成另一种概率分布。在图像特征点匹配的例子中，就是将第一幅图像的特征点与第二幅图像的特征点进行关联，使得正确关联的数量尽可能地多。可能存在的方案是：
U ( r , c ) = { P ∈ R > 0 m × n ∣ P 1 M = r , P 1 N = c } (1) U(\mathbf r,\mathbf c)=\{\mathbf P \in \mathbb R^{m \times n}_{>0}|\mathbf P \mathbf 1_M=\mathbf r,\mathbf P \mathbf 1_N=\mathbf c\}\tag{1} U(r,c)={ P∈R>0m×n​∣P1M​=r,P1N​=c}(1)
其中，$1_M$为$M$维全1向量；$\mathbf{r}$为第一个分布中的值，$\mathbf{c}$为第二个分布中的值。代价函数为：
$$d_M(r,c)=\underset{P\in U(\mathbf{r},\mathbf{c})}{\min }\sum _{i,j}{P}_{ij}{M}_{ij}\text{\hspace{1em}(2)}$$
其中，将第一个分布的第$i$个值与第二个分布的第$j$个值进行关联的代价为 M = { M i j } M=\{M_{ij}\} M={ Mij​}。
式（2）也称为Wasserstein metric 或earth mover distance（EMD）代价函数。
  若增加正则项，则代价函数表示为：
d M λ ( r , c ) = min ⁡ P ∈ U ( r , c ) < P , M > F − 1 λ h ( P ) (3) d_M^{\lambda}(r,c)=\min\limits_{P\in U(\mathbf r,\mathbf c)}<P,M>_F-\fra