C++帧间位置分析：基于最近邻搜索的新增点低复杂度识别方案咨询

你遇到的本质是一维序列带冗余点的最优匹配问题，完全不需要用通用二分匹配的匈牙利算法（该算法O(n³)复杂度在这个场景下完全没必要），利用一维数据的排序特性可以做到极低复杂度，精度完全满足最小总匹配距离的要求。 #

核心原理 #

首先明确一维匹配的确定性规则：两个升序排列的序列，总距离最小的匹配一定不存在交叉。举个例子，如果当前帧点a < b，上一帧点c < d，不可能出现a配d、b配c的情况，这种配对的总距离一定比a配c、b配d更大。
基于这个规则，不需要暴力枚举所有配对组合，用动态规划就能在线性对数级复杂度下解决问题，天然支持任意数量的新增点。 #

实现步骤 #

1. 预处理 #

先把上一帧、当前帧的位置数组分别做升序排序，排序复杂度为O(nlogn + mlogm)，n是上一帧点数，m是当前帧点数。

以你给出的示例为例，排序后结果：

• 上一帧：[0.09, 0.23, 0.52, 0.8, 0.98]（长度n=5）
• 当前帧：[0.08, 0.19, 0.22, 0.56, 0.7, 0.9]（长度m=6）
  新增点总数k = m - n = 1，和你描述的场景一致。

2. 动态规划匹配 #

定义状态dp[i][j]：用上一帧前i个点，匹配当前帧前j个点（从j个点里选i个完成配对）的最小总距离。
状态转移只有两个合法选项：

• 把当前帧第j个点判定为新增点，不参与匹配：总距离等于dp[i][j-1]
• 把当前帧第j个点和上一帧第i个点配对：总距离等于dp[i-1][j-1] + abs(last[i] - current[j])
  取两个选项里总距离更小的值作为当前状态的最优值即可。
  边界条件：
• dp[0][j] = 0：上一帧没有点时，所有当前帧点都是新增，匹配总距离为0
• dp[i][0] = 无穷大：不可能用0个当前帧点匹配i个上一帧点

3. 回溯找新增点 #

遍历DP的时候同步记录每个状态的转移来源，等DP跑完从最终状态往回遍历：

• 如果当前状态是从「判新增」转移来的，对应的当前帧点就是新增点
• 如果是从「配对」转移来的，两个指针同时往前移

C++参考实现 #

#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

std::vector<float> detect_new_points(std::vector<float> last_frame, std::vector<float> current_frame) {
    int n = last_frame.size();
    int m = current_frame.size();
    if (m <= n) return {}; // 当前帧点数少于等于上一帧，无新增点

    std::sort(last_frame.begin(), last_frame.end());
    std::sort(current_frame.begin(), current_frame.end());

    const float INF = std::numeric_limits<float>::max();
    std::vector<std::vector<float>> dp(n + 1, std::vector<float>(m + 1, INF));
    // 路径标记：1=当前点判新增，2=当前点和上一帧点配对
    std::vector<std::vector<int>> path(n + 1, std::vector<int>(m + 1, 0));

    for (int j = 0; j <= m; ++j) {
        dp[0][j] = 0;
        path[0][j] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        // 剪枝：j至少要等于i（给前面i个上一帧点留够匹配点），最多到m-(n-i)（给后面剩下的上一帧点留够匹配点）
        for (int j = i; j <= m - (n - i); ++j) {
            float cost_new = dp[i][j-1];
            float cost_match = (dp[i-1][j-1] == INF) ? INF : dp[i-1][j-1] + std::abs(last_frame[i-1] - current_frame[j-1]);

            if (cost_new < cost_match) {
                dp[i][j] = cost_new;
                path[i][j] = 1;
            } else {
                dp[i][j] = cost_match;
                path[i][j] = 2;
            }
        }
    }

    // 回溯提取新增点
    std::vector<float> new_points;
    int i = n, j = m;
    while (i > 0 || j > 0) {
        if (path[i][j] == 1) {
            new_points.push_back(current_frame[j-1]);
            --j;
        } else {
            --i;
            --j;
        }
    }
    std::reverse(new_points.begin(), new_points.end());
    return new_points;
}

用你给的示例输入跑这段代码，返回的新增点就是0.19，和你预期的最小总匹配结果完全一致。 #

工程优化建议 #

• 加匹配距离阈值：实际业务里帧间目标移动有速度上限，两个点距离超过阈值就不允许配对，避免出现远距离点强行匹配的误判
• 高性能场景优化：如果单帧点数超过100，可以利用DP的决策单调性用分治把复杂度从O(nm)降到O((n+k)log(n+k))；普通检测场景（单帧几十个点）上面的O(nm)实现完全够用，跑起来延迟可以忽略
• 二维/三维坐标适配：如果你的位置是检测框中心点(x,y)甚至带深度的三维坐标，只需要先按x升序、x相同按y升序排列，不交叉匹配原则依然成立，只需要把距离计算换成欧氏距离即可，核心逻辑不用改

内容的提问来源于stack exchange，提问作者ismaquantum