Algoritmo de ajuste de línea OpenCV

Question

Estoy tratando de comprender el algoritmo OpenCV fitLine().

Este es un fragmento de código de OpenCV: icvFitLine2D función - icvFitLine2D

veo que hay alguna función aleatoria que elige puntos de aproximación, a continuación, calcula las distancias desde los puntos a la línea de módulos (con puntos seleccionadas), entonces elije otros puntos e intenta minimizar la distancia con el número distType elegido.

¿Alguien puede aclarar qué pasa desde this moment sin matemáticas duras y suponiendo que no hay un gran conocimiento estadístico ?. Los comentarios del código OpenCV y los nombres de las variables no me ayudan a entender este código.

Answer 1

(Esto es una vieja pregunta, pero el tema despertó mi curiosidad)

El OpenCV FitLine implemements dos mecanismos diferentes.

Si el parámetro distType se establece en CV_DIST_L2, se utiliza un standard unweighted least squares fit.

Si se utiliza uno de los otros distTypes (CV_DIST_L1, CV_DIST_L12, CV_DIST_FAIR, CV_DIST_WELSCH, CV_DIST_HUBER) entonces el procedimiento es una especie de RANSAC ajuste:

• Repita en la mayoría de 20 veces:
  • Elija 10 puntos aleatorios, haga un ajuste de mínimos cuadrados solo para ellos
  • Repita como máximo 30 veces:
    • Calcular los pesos para todos los puntos, utilizando la línea encontrado actual y el elegido distType
    • hacer un ponderados ajuste por mínimos cuadrados para todos los puntos
    • (Esta es una Iteratively reweighted least squares fit o M-Estimator)
• Volver encontrado la mejor linefit

He aquí una descripción más detallada en el 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 

Los pesos se calculan en función de la distType elegido, de acuerdo con the manual la fórmula para que sea weight[Point_i] = 1/ p(distance_between_point_i_and_line), donde p es:

distType = CV_DIST_L1

distType = CV_DIST_L12

distType = CV_DIST_FAIR

distType = CV_DIST_WELSCH

distType = CV_DIST_HUBER

Desafortunadamente no sé lo que distType es el más adecuado para los que tipo de datos, tal vez alguna otra manera se puede arrojar alguna luz sobre eso.

---

algo interesante me di cuenta: La norma elegida sólo se utiliza para la nueva ponderación iterativa, la mejor solución entre las encontradas siempre se escoge de acuerdo a la norma L2 (La línea para la que el no ponderado suma de menos cuadrados es mínimo). No estoy seguro de que esto sea correcto.