ओपनसीवी लाइन फिटिंग एल्गोरिदम

Question

मैं ओपनसीवी fitLine() एल्गोरिदम को समझने की कोशिश कर रहा हूं।

यह OpenCV से कोड का टुकड़ा है: icvFitLine2D समारोह - icvFitLine2D

मैं देख रहा हूँ कुछ यादृच्छिक समारोह है कि सन्निकटन के लिए अंक चुनता है कि वहाँ है, तो अंक से दूरी सज्जित लाइन के लिए (चुना अंकों के साथ) की गणना करता है, तो अन्य बिंदुओं का चयन करें और distType चुनने के साथ दूरी को कम करने की कोशिश करता है।

क्या कोई स्पष्ट कर सकता है कि this moment से कठिन गणित के बिना क्या होता है और कोई महान सांख्यिकीय ज्ञान नहीं लेता है? ओपनसीवी कोड टिप्पणियां और परिवर्तनीय नाम इस कोड को समझने में मेरी सहायता नहीं करते हैं।

Answer 1

(यह एक पुरानी सवाल है, लेकिन विषय मेरी जिज्ञासा भी खफा)

OpenCV FitLine implemements दो अलग तंत्र।

यदि पैरामीटर distTypeCV_DIST_L2 पर सेट है, तो standard unweighted least squares fit का उपयोग किया जाता है।सबसे 20 बार में

• दोहराएँ:

  • तो अन्य distTypes में से एक प्रयोग किया जाता है (CV_DIST_L1, CV_DIST_L12, CV_DIST_FAIR, CV_DIST_WELSCH, CV_DIST_HUBER) तो प्रक्रिया RANSAC फिट के कुछ प्रकार है 10 यादृच्छिक बिंदु चुनें, कम से कम वर्ग केवल उनके लिए फिट करें

  • अधिकतम 30 बार दोहराएं:
    • सभी बिंदुओं के लिए वजन की गणना, वर्तमान पाया लाइन और चुने हुए distType
    • का उपयोग कर एक भारित कम से कम वर्गों सभी बिंदुओं
    • के लिए फिट
(यह एक Iteratively reweighted least squares fit या M-Estimator है) करते हैं
• सबसे अच्छा पाया गया लाइनफ़िट

यहां पार्स में एक और विस्तृत विवरण दिया गया है 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 

वजन the manual के अनुसार, चुने हुए distType के आधार पर गणना कर रहे हैं कि के लिए सूत्र weight[Point_i] = 1/ p(distance_between_point_i_and_line), जहां पी है:

distType = CV_DIST_L1

distType = CV_DIST_L12

distType = CV_DIST_FAIR

distType = CV_DIST_WELSCH

distType = CV_DIST_HUBER

दुर्भाग्य से मैं नहीं जानता कि जो distType सबसे उचित होगा जो डेटा की तरह के लिए, शायद किसी और कुछ है कि पर कुछ प्रकाश डाला सकता है।

---

कुछ दिलचस्प मैंने देखा: चुने हुए आदर्श केवल पुनरावृत्ति reweighting के लिए प्रयोग किया जाता है, पाया लोगों के बीच सबसे अच्छा समाधान हमेशा एल 2 आदर्श (लाइन के अनुसार चुना जाता है जो अनिर्धारित कम से कम की राशि के लिए वर्ग न्यूनतम है)। मुझे यकीन नहीं है कि यह सही है।