两种图对应关系的共识及Volgenant-Jonker算法优化

### 两种图对应关系的共识及Volgenant - Jonker算法优化 #### 1. 两种图对应关系的共识方法 在处理图对应关系时，我们提出了一种共识方法。这里涉及到扩展成本矩阵 \(C_a\) 和 \(C_b\)，以及扩展对应矩阵 \(F_a\) 和 \(F_b\)，还有全为 1 的矩阵 \(1\)。这四个矩阵都被扩展为 \(n_{a,b} \times n_{a,b}\) 的单元格，以确保所有节点的替换、删除和插入组合都是可能的，同时扩展时要考虑节点之间的映射 \(\zeta\) 和 \(\zeta'\)。 我们提出的共识方法基于应用线性求解器，如匈牙利方法或 Jonker - Volgenant 方法来获得 \(f_{a,b}^{\lambda *}\)（如方程 3 所定义），使用的矩阵如下： \[H = C_a + C_b + \lambda \cdot [2 - (F_a + F_b)]\] 其中 \(2\) 是全为 2 的矩阵。 为了证明该方法的有效性，我们需要证明： \(EditCost(\hat{G}_a, \hat{G}'_a, f_{a,b}) + EditCost(\hat{G}_b, \hat{G}'_b, f_{a,b}) + \lambda \cdot [dH(\hat{f}_a, f_{a,b}) + dH(\hat{f}_b, f_{a,b})]\) 等于 \(C_a^{f_{a,b}} + C_b^{f_{a,b}} + \lambda \cdot [(1_{f_{a,b}} - F_a^{f_{a,b}}) + (1_{f_{a,b}} - F_b^{f_{a,b}})]\)。 通过构造可知 \(EditCost(\hat{G}_a, \hat{G}'_a, f_{a,b}) + EditCost(\hat{G}_b, \hat{G}'_b, f_{a,b}) = C_{f_{a,b}}^a + C_{f_{a,b}}^b\) 且 \(1_{f_{a,b}} = n_{a,b}\)，所以我们只需证明： \[dH(\hat{f}_a, f_{a,b}) + dH(\hat{f}_b, f_{a,b}) = 2 \cdot n_{a,b} - F_a^{f_{a,b}} - F_b^{f_{a,b}}\] 考虑对应关系 \(f_{a,b}\)、\(\hat{f}_a\) 和 \(\hat{f}_b\) 之间的关系，我们将节点集 \(\Sigma_{v}^{a,b}\) 分为四种情况，如下表所示： | 相对于 \(\hat{f}_a\) | 相对于 \(\hat{f}_b\) | \(\Sigma_{v}^{a,b}\) 中的节点 | \(dH(\hat{f}_a, f_{a,b})\) | \(dH(\hat{f}_b, f_{a,b})\) | \(F_a^{f_{a,b}}\) | \(F_b^{f_{a,b}}\) | | --- | --- | --- | --- | --- | --- | --- | | \(\hat{f}_a(v_i^a) \neq f_{a,b}(v_i^a)\) | \(\hat{f}_b(v_i^b) \neq f_{a,b}(v_i^b)\) | A | 0 | 0 | A | A | | \(\hat{f}_a(v_i^a) \neq f_{a,b}(v_i^a)\) | \(\hat{f}_b(v_i^b) = f_{a,b}(v_i^b)\) | B | 0 | B | 0 | B | | \(\hat{f}_a(v_i^a) = f_{a,b}(v_i^a)\) | \(\hat{f}_b(v_i^b) \neq f_{a,b}(v_i^b)\) | C | C | 0 | C | 0 | | \(\hat{f}_a(v_i^a) = f_{a,b}(v_i^a)\) | \(\hat{f}_b(v_i^b) = f_{a,b}(v_i^b)\) | D | 0 | 0 | D | D | | 总计 | | \(n_{a,b}\) | A + B | A + C | C + D | B + D | 从表中第三列和第四列可以推出 \(dH(\hat{f}_a, f_{a,b}) + dH(\hat{f}_b, f_{a,b}) = 2A + B + C\)，从最后两列可得 \(F_a^{f_{a,b}} + F_b^{f_{a,b}} = 2D + B + C\)。因此，\(2 \cdot n_{a,b} - F_a^{f_{a,b}} - F_b^{f_{a,b}} = 2A + 2B + 2C + 2D - 2D - B - C = 2A + B + C\)，与 \(dH(\hat{f}_a, f_{a,b}) + dH(\hat{f}_b, f_{a,b})\) 相等，从而证明了使用方程 4 解决问题的有效性。 #### 2. 实验验证 为了验证我们的方法，使用了 “Tarragona Exteriors” 数据集，它由五个公共图像数据库 “BOAT”、“EAST_PARK”、“EAST_SOUTH”、“RESIDENCE” 和 “ENSIMAG” 定义。这些数据库包含从同一对象不同位置和不同缩放拍摄的图像序列，同时提供将集合中的第一张图像（img00）转换为其他图像（img01 到 img10）的单应性估计 \(h_i\)。 从每张图像中，使用 5 种方法（FAST、HARRIS、MINEIGEN、SURF（Matlab 2013b 原生库）和 SIFT（自有库））提取 50 个最可靠的显著点。基于这些显著点集，为每张图像构建五个代表性图，节点表示显著点的位置，边使用 Delaunay 三角剖分方法构建。 在序列的第一张图像（img00）和其他十张图像（img01 到 img10）之间，使用五种不同的提取结构和四种不同的匹配函数计算对应关系： 1. 使用 Matlab 的 MatchFeatures 函数进行显著点匹配（Matlab 2013b 原生库）。 2. 使用 FastBipartite 函数进行图匹配，分别基于节点、度和团的局部子结构（自有库）。 对于 MatchFeatures 函数，将 MaxRatio 参数设置为 1 以找到尽可能多的映射，并去除非双射标记。数据库共有 \(5\) 个序列 \(\times 10\) 对图像 \(\times 5\) 种提取方法 \(\times 4\) 种匹配选项 = 1000 个四元组 \(Q_i = \{S_i^1, S_i^2, f_i, h_i\}\)，其中 \(i \in [1 \ldots 1000]\)。 实验结果如下表所示： | 数