参考自：VectorMapNet: End-to-end Vectorized HD Map Learning

数据集

nuScenes 我们在 nuScenes (Caesar et al., 2020) 数据集上进行实验，该数据集包含 1000 个自动驾驶汽车采集的记录序列。每个片段都以 2Hz 的频率进行注释，包含 6 幅摄像头图像和激光雷达扫描图像。数据集设置和预处理步骤可与 HDMapNet (Li et al., 2021) 相同，后者包含来自 nuScenes 数据集的三类地图元素：人行横道、分隔线和道路边界。

Argoverse2 我们进一步在 Argoverse2 (Wilson et al., 2021) 数据集上进行实验。与 nuScenes 一样，它包含 1000 个日志（训练集、验证集和测试集分别为 700、150 和 150）。每个片段提供 15 秒的 20Hz 摄像头图像、10Hz 激光雷达扫描图像和矢量化地图。使用与 nuScenes 数据集相同的预处理设置。

指标

与现有生成栅格化结果的方法相比，我们的方法不需要在网格上栅格化曲线。因此，我们选择不使用交并比 (IoU) 作为指标。我们使用基于距离的指标来评估预测曲线与真实曲线之间的相似性。我们遵循 HDMapNet (Li et al., 2021) 提出的实例级评估指标，将我们模型的实例级检测性能与基线方法进行比较。该指标是平均精度 (AP)，其中正/负样本基于几何相似性，更具体地说，是倒角距离 (Chamfer distance) 和 Fr´echet 距离。为清晰起见，我们将基于倒角距离和 Fr´echet 距离的 AP 分别称为倒角 AP 和 Fr´echet AP。

Chamfer距离（Chamfer Distance）和Fréchet距离（Fréchet Distance）是两种常用于评估曲线或多线段相似性的度量方法

1. Chamfer距离

• 定义：Chamfer距离用于量化两个无序点集之间的相似性。其计算公式为：
  $$D_{\text{chamfer}}(S_1,S_2)=\frac{1}{2|S_1|}\sum _{p\in S_1}\underset{q\in S_2}{\min }\Vert p-q{\Vert }^2+\frac{1}{2|S_2|}\sum _{q\in S_2}\underset{p\in S_1}{\min }\Vert q-p{\Vert }^2$$
• 特点：
  • 仅考虑点之间的最近邻距离，忽略点的顺序。
  • 适用于无序点集（如点云、多线段顶点集）的相似性比较。
  • 计算效率较高，常用于3D重建、点云生成等任务中作为损失函数。

Chamfer距离计算（点云相似性）

import numpy as np
from sklearn.neighbors import NearestNeighbors

def chamfer_distance(x, y, metric='l2'):
    """计算两组点云之间的双向Chamfer距离"""
    x_nn = NearestNeighbors(n_neighbors=1, algorithm='kd_tree', metric=metric).fit(x)
    min_y_to_x = x_nn.kneighbors(y)[0]  # y中每个点到x的最近距离
    y_nn = NearestNeighbors(n_neighbors=1, algorithm='kd_tree', metric=metric).fit(y)
    min_x_to_y = y_nn.kneighbors(x)[0]  # x中每个点到y的最近距离
    return np.mean(min_y_to_x) + np.mean(min_x_to_y)

# 示例
x = np.random.rand(100, 3)  # 点云1 (100个3D点)
y = np.random.rand(100, 3)  # 点云2
distance = chamfer_distance(x, y)
print(f"Chamfer距离: {distance:.4f}")

说明：

• 使用sklearn.neighbors高效计算最近邻距离。
• 适用于3D点云重建、形状匹配等任务。

2. Fréchet距离

• 定义：Fréchet距离同时考虑曲线的空间位置和点的顺序。其离散版本定义为：
  δdF(P,Q)=min⁡{∥L∥∣L是P和Q之间的耦合序列}\delta_{dF}(P, Q) = \min \{\|L\| \mid L \text{是}P\text{和}Q\text{之间的耦合序列}\}δdF​(P,Q)=min{∥L∥∣L是P和Q之间的耦合序列}
  其中，$\Vert L\Vert$是耦合序列$L$中最长配对的距离。
• 特点：
  • 需要保证曲线的顺序一致性（如轨迹、多线段的顶点顺序）。
  • 直观理解为“遛狗问题”：主人和狗沿两条路径行走时所需的最短狗绳长度。
  • 计算复杂度较高，通常用于需要严格对齐顺序的场景（如地图匹配、自动驾驶中的车道线检测）。
• 输出：
  • Fréchet距离输出的是两条曲线的最优匹配下的最大局部距离，核心是寻找两条曲线在所有可能匹配方式中最大局部距离的最小值​（即“最短狗绳长度”）
  • “最大局部距离”：在两条曲线的匹配过程中，每一步的匹配点对 $(p_i,q_j)$ 都有一个距离 $d(p_i,q_j)$，所有匹配点对中的最大距离即为当前匹配方案的“最大局部距离”。
  • “最小值”：通过调整匹配顺序（即参数化函数 $\alpha$ 和 $\beta$），寻找所有可能的匹配方案中最小的那个“最大局部距离”。

Fr´echet 距离。折线顶点的顺序无法通过倒角距离来衡量。因此，我们引入 Fr´echet 距离作为附加度量。Fr´echet 距离是一种曲线相似度度量，它同时考虑了曲线上点的位置和顺序。我们的实现基于离散 Fr´echet 距离 (Eiter & Mannila, 1994; Agarwal et al., 2014)。

我们使用离散版本的 Fr´echet 距离 (Eiter & Mannila, 1994; Agarwal et al., 2014) 来评估两条折线 P 和 Q 之间的几何相似性。我们将 σ§ 表示为 P 的线段端点序列。具体来说，σ（P）=（p1，…，pm）是从原始输入折线P均匀采样的具有m个顶点的序列，其中pi和pi + 1之间的P的每个位置都可以通过使用仿射变换来近似，即pi +λ=（1-λ）pi +λpi + 1，并且我们实验中的m设置为100。
该方程表明，离散Fr´echet距离是所有可能耦合的最小范数。为了找到具有最小范数的耦合似然L，我们使用了基于动态规划的算法，如算法1中所述。

Fréchet距离计算（曲线相似性）

import numpy as np
from scipy.spatial.distance import euclidean

def frechet_distance(p, q):
    """动态规划计算离散Fréchet距离"""
    n, m = len(p), len(q)
    ca = np.zeros((n, m))
    ca[0, 0] = euclidean(p[0], q[0])
    for i in range(1, n):
        ca[i, 0] = max(ca[i-1, 0], euclidean(p[i], q[0]))
    for j in range(1, m):
        ca[0, j] = max(ca[0, j-1], euclidean(p[0], q[j]))
    for i in range(1, n):
        for j in range(1, m):
            ca[i, j] = max(min(ca[i-1, j], ca[i-1, j-1], ca[i, j-1]), euclidean(p[i], q[j]))
    return ca[-1, -1]

# 示例
p = np.array([(0, 0), (1, 1), (2, 2)])  # 曲线1
q = np.array([(0, 1), (1, 2), (2, 1)])  # 曲线2
distance = frechet_distance(p, q)
print(f"Fréchet距离: {distance:.4f}")

说明：

• 基于动态规划实现，考虑曲线顶点顺序。
• 适用于轨迹匹配、时间序列对齐等场景。

动态规划（Dynamic Programming，简称DP）是一种用于求解最优化问题的数学方法，其核心思想是通过分解问题为相互重叠的子问题，并存储子问题的解以避免重复计算，从而高效地得到全局最优解。
动态规划的核心思想
​- 最优子结构：问题的最优解包含其子问题的最优解。例如，最短路径问题中，从A到B的最短路径必然包含路径上任意中间点到B的最短路径。
​- 重叠子问题：在递归求解过程中，相同的子问题会被多次计算。动态规划通过存储子问题的解（如表格或数组）来避免重复计算。
​- 无后效性：当前状态一旦确定，后续决策不受之前状态的影

经典应用场景

• ​斐波那契数列（又称“兔子数列”）：避免递归的重复计算。斐波那契数列是动态规划（DP）的经典入门问题，其状态转移方程直接反映了DP的核心思想。
• ​背包问题：在容量限制下最大化物品价值。
• ​最短路径问题：如Dijkstra算法的动态规划变体。

动态规划的步骤

• ​定义状态
  • 用变量（如dp[i]）表示问题的子问题解。例如，dp[i]可表示“爬到第i阶楼梯的方法数”。
• ​状态转移方程
  • 建立子问题之间的关系。例如，斐波那契数列的转移方程为：
  • dp[i]=dp[i−1]+dp[i−2]
• ​初始化边界条件
  • 设置最小子问题的解（如dp[0] = 0，dp[1] = 1）。
• ​计算顺序
  • 通常采用自底向上​（递推）或自顶向下​（记忆化搜索）的方式填充状态表

3. 核心区别

4. 应用示例

• Chamfer距离：在自动驾驶中评估生成的车道线点云与真实数据的局部相似性。
• Fréchet距离：验证车道线的全局几何结构和拓扑关系（如OpenLane-V2数据集中的拓扑推理指标）。

两者常结合使用，Chamfer距离捕捉局部几何相似性，Fréchet距离确保全局结构一致性。