Thuật toán phù hợp với OpenCV

Question

Tôi đang cố gắng hiểu thuật toán OpenCV fitLine().

Đây là đoạn mã từ OpenCV: icvFitLine2D chức năng - icvFitLine2D

tôi thấy rằng có một số chức năng ngẫu nhiên mà chọn điểm cho xấp xỉ, sau đó tính khoảng cách từ điểm đến đường dây được trang bị (với điểm choosen), sau đó chọn các điểm khác và cố gắng giảm thiểu khoảng cách với lựa chọn distType.

Ai đó có thể làm rõ điều gì xảy ra từ this moment mà không có toán học cứng và giả sử không có kiến ​​thức thống kê tuyệt vời ?. Nhận xét mã OpenCV và tên biến không giúp tôi hiểu mã này.

Answer 1

(Đây là một câu hỏi cũ, nhưng đề tài này khơi gợi sự tò mò của tôi)

Các OpenCV FitLine implemements hai cơ chế khác nhau.

Nếu tham số distType được đặt thành CV_DIST_L2 thì sử dụng standard unweighted least squares fit.

Nếu một trong những distTypes khác được sử dụng (CV_DIST_L1, CV_DIST_L12, CV_DIST_FAIR, CV_DIST_WELSCH, CV_DIST_HUBER) thì thủ tục là một số loại RANSAC phù hợp:

• Lặp lại tối đa 20 lần:
  • Chọn 10 điểm ngẫu nhiên, làm một hình vuông nhỏ nhất chỉ phù hợp với chúng
  • Lặp lại tối đa 30 lần:
    • Tính trọng lượng cho tất cả các điểm, sử dụng dòng tìm thấy hiện tại và chọn distType
    • Thực hiện quyền bình phương tối thiểu phù hợp cho tất cả các điểm
    • (Đây là một Iteratively reweighted least squares fit hoặc M-Estimator)
• Trả lại dòng được tìm thấy tốt nhất

Dưới đây là mô tả chi tiết hơn về 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 

Các trọng số được tính tùy thuộc vào lựa chọn distType, theo the manual công thức cho điều đó là weight[Point_i] = 1/ p(distance_between_point_i_and_line), trong đó p là:

distType = CV_DIST_L1

distType = CV_DIST_L12

distType = CV_DIST_FAIR

distType = CV_DIST_WELSCH

distType = CV_DIST_HUBER

Đáng tiếc là tôi không biết đó distType là thích hợp nhất mà loại dữ liệu, có lẽ một số khác có thể làm sáng tỏ về điều đó.

---

Something thú vị tôi nhận thấy: Các tiêu chuẩn lựa chọn chỉ được sử dụng cho các reweighting lặp đi lặp lại, giải pháp tốt nhất trong số những người tìm thấy luôn chọn theo tiêu chuẩn L2 (Điểm mấu mà không trọng số tổng của tối thiểu hình vuông là tối thiểu). Tôi không chắc chắn điều này là chính xác.