algorithm - OpenCV ラインフィッティングアルゴリズム

Question

OpenCV fitLine()アルゴリズムを理解しようとしています。

これは OpenCV のコードの一部です: icvFitLine2D関数 - icvFitLine2D

近似のためにポイントを選択し、ポイントから適合線までの距離を計算し(選択したポイントで)、他のポイントを選択し、choosen で距離を最小化しようとするランダム関数があることがわかりますdistType。

この瞬間から何が起こるかを、難しい数学や優れた統計的知識を前提とせずに説明できる人はいますか?. OpenCV コードのコメントと変数名は、このコードを理解するのに役立ちません。

score 28 · Accepted Answer

（これは古い質問ですが、主題は私の好奇心を刺激しました）

OpenCVFitLineは、2つの異なるメカニズムを実装しています。

パラメータdistTypeがに設定されている場合CV_DIST_L2、標準の重み付けされていない最小二乗近似が使用されます。

他のいずれかdistTypesが使用されている場合（、、、、、） CV_DIST_L1、手順はある種のCV_DIST_L12RANSAC適合です。CV_DIST_FAIRCV_DIST_WELSCHCV_DIST_HUBER

最大20回繰り返します。
- ランダムな点を10個選び、それらにのみ適合する最小二乗法を実行します
- 最大30回繰り返します。
  - 現在見つかった線と選択した線を使用して、すべての点の重みを計算しますdistType
  - すべての点に加重最小二乗法を適用します
  - （これは、反復再重み付け最小二乗近似または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その式はです。ここで、pは次のとおりです。weight[Point_i] = 1/ p(distance_between_point_i_and_line)