OpenCV Line Fitting-Algorithmus

Question

Ich versuche OpenCV fitLine() Algorithmus zu verstehen.

Dieses Fragment von Code von OpenCV ist: icvFitLine2D Funktion - icvFitLine2D

sehe ich, dass es eine Zufallsfunktion ist, die Punkte für die Näherung wählt, berechnet dann Entfernungen von Punkten angepasste Linie (mit gewählten Punkten), dann Wählen Sie andere Punkte und versuchen Sie die Entfernung zu minimieren mit distType.

Kann jemand klären, was aus this moment ohne harte Mathematik und unter Annahme von keine große Statistik Wissen ?. OpenCV Code Kommentare und Variablennamen hilft mir nicht, diesen Code zu verstehen.

Answer 1

(Dies ist eine alte Frage, aber das Thema reizte meine Neugier)

Die OpenCV FitLine implemements zwei verschiedene Mechanismen. Wenn der Parameter distType auf CV_DIST_L2 gesetzt ist, wird standard unweighted least squares fit verwendet.

Wenn einer der anderen distTypes verwendet wird (CV_DIST_L1, CV_DIST_L12, CV_DIST_FAIR, CV_DIST_WELSCH, CV_DIST_HUBER), dann ist das Verfahren, eine Art RANSAC fit:

• Wiederholen höchstens 20-mal:
  • Wählen Sie 10 zufällige Punkte, passen Sie die Methode der kleinsten Quadrate nur für diese an
  • Wiederholen Sie höchstens 30 Mal: ​​
    • Berechnen die Gewichte für alle Punkte, die aktuelle Ergebniszeile und die gewählten distType
    • ein gewichteten kleinsten Quadrate für alle Punkte passen
    • (Dies ist ein Iteratively reweighted least squares fit oder M-Estimator)
• Zurück zur besten gefundenen linefit

ist hier eine detailliertere Beschreibung in pse udocode:

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 

Die Gewichte berechnet werden in Abhängigkeit von der gewählten distType nach the manual die Formel für das heißt weight[Point_i] = 1/ p(distance_between_point_i_and_line), wobei p:

distType = CV_DIST_L1

distType = CV_DIST_L12

distType = CV_DIST_FAIR

distType = CV_DIST_WELSCH

distType = CV_DIST_HUBER

Leider weiß ich nicht, welche distType am besten geeignet ist, für die Art von Daten, vielleicht einige sonst etwas Licht auf das werfen kann.

---

Etwas Interessant Ich bemerkte: Die gewählte Norm nur für die iterative Neugewichtung, die beste Lösung unter den gefunden diejenigen wird immer dann verwendet wird gepflückt die L2-Norm entsprechend (Die Linie, für die die ungewichteten Summe von mindestens Quadrate sind minimal). Ich bin mir nicht sicher, ob das stimmt.