algorithm - OpenCV线拟合算法

我正在尝试了解OpenCV fitLine()算法。

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

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

如果没有严格的数学知识并且没有丰富的统计知识，有人可以阐明this moment会发生什么吗？ OpenCV代码注释和变量名称并不能帮助我理解此代码。

最佳答案

(这是一个古老的问题，但是这个话题激起了我的好奇心)

OpenCV FitLine实现了两种不同的机制。

如果参数distType设置为CV_DIST_L2，则使用standard unweighted least squares fit。

如果使用其他distTypes之一(CV_DIST_L1，CV_DIST_L12，CV_DIST_FAIR，CV_DIST_WELSCH，CV_DIST_HUBER)，则该过程适合某种RANSAC的情况:

最多重复20次:

随机选择10个点，对它们进行最小二乘拟合

最多重复30次:

使用当前找到的线和所选的distType

计算所有点的权重

对所有点进行加权最小二乘拟合

(这是Iteratively reweighted least squares fit或M-Estimator)

返回找到的最佳线性拟合

这是伪代码的更详细描述:

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，根据the manual的公式为weight[Point_i] = 1/ p(distance_between_point_i_and_line)，其中p为:



不幸的是，我不知道哪种distType最适合哪种数据，也许其他一些可以阐明这一点。

我注意到了一些有趣的事情:所选范数仅用于迭代加权，找到的范数总是根据L2范数(最小平方的未加权和的线)来选择。我不确定这是正确的。