algorithm - OpenCV 线拟合算法

Question

我试图了解 OpenCV fitLine()算法。

这是来自 OpenCV 的代码片段： icvFitLine2D函数 - icvFitLine2D

我看到有一些随机函数选择近似点，然后计算从点到拟合线的距离（使用选择的点），然后选择其他点并尝试使用 choosen 最小化距离distType。

有人可以澄清从这一刻起会发生什么，而无需经过严格的数学运算并假设没有出色的统计知识吗？OpenCV 代码注释和变量名并不能帮助我理解这段代码。

score 28 · Accepted Answer

（这是一个老问题，但这个话题激起了我的好奇心）

OpenCVFitLine实现了两种不同的机制。

如果参数distType设置为CV_DIST_L2，则使用标准的未加权最小二乘拟合。

如果distTypes使用其中之一（CV_DIST_L1, CV_DIST_L12, CV_DIST_FAIR, CV_DIST_WELSCH, CV_DIST_HUBER），则该过程是某种RANSAC拟合：

最多重复 20 次：
- 选择 10 个随机点，只为它们做一个最小二乘法
- 最多重复 30 次：
  - 使用当前找到的线和选择的线计算所有点的权重distType
  - 对所有点进行加权最小二乘拟合
  - （这是一个迭代重新加权最小二乘拟合或M-Estimator）
返回找到的最佳 linefit

这是伪代码中更详细的描述：

repeat at most 20 times:

    RANSAC (line 371)
     - pick 10 random points, 
     - set their weights to 1, 
     - set all other weights to 0

    least squares weighted fit (fitLine2D_wods, line 381)
     - fit only the 10 picked points to the line, using least-squares

    repeat at most 30 times: (line 382)
     - stop if the difference between the found solution and the previous found solution is less than DELTA  (line 390 - 406)
       (the angle difference must be less than adelta, and the distance beween the line centers must be less than rdelta)
     - stop if the sum of squared distances between the found line and the points is less than EPSILON (line 407)
       (The unweighted sum of squared distances is used here ==> the standard L2 norm)

        re-calculate the weights for *all* points (line 412)
         - using the given norm (CV_DIST_L1 / CV_DIST_L12 / CV_DIST_FAIR / ...)
         - normalize the weights so their sum is 1
         - special case, to catch errors: if for some reason all weights are zero, set all weight to 1

        least squares weighted fit (fitLine2D_wods, line 437)
         - fit *all* points to the line, using weighted least squares

    if the last found solution is better than the current best solution (line 440)
        save it as the new best
        (The unweighted sum of squared distances is used here ==> the standard L2 norm)

        if the distance between the found line and the points is less than EPSILON
             break

return the best solution

权重的计算取决于所选的distType，根据手册的公式是weight[Point_i] = 1/ p(distance_between_point_i_and_line)，其中 p 是：