llenado del acumulador para la transformada Hough

Question

Escribí un código que debe optimizarse. Solo me apetecía consultar con la comunidad para ver si ese código es realmente óptimo. Llena el acumulador para la transformada Hough. De hecho, copié la mayoría del código de la biblioteca de OpenCV. ¡Gracias!

---

int i,j,n,index; 
for (i = 0;i<numrows;i++) 
{ 
    for (j = 0;j<numcols;j++) 
    { 
      if (img[i*numcols + j] == 100) 
     { 
      for (n = 300;n<600;n++) 
      { 
       index = cvRound(j*tabCos[n] + i * tabSin[n]) + (numrho-1)/2; 
       accum[(n+1) * (numrho+2) + index+1]++; 
      } 
     } 
    } 
} 

Answer 1

, no lo es. Reemplace la mayor cantidad posible de los usos de [] con aritmética de puntero simple para iterar las matrices en cuestión. Resume expresiones invariantes en variables locales.

Sin embargo, la primera pregunta es, ¿su perfil muestra que este código es un cuello de botella en el contexto de toda su aplicación. Si no, ¿por qué molestarse micro-optimizando esto?

EDIT: bucle micro-optimización - prefieren la segunda ya que no requiere la indexación de matrices (mult frente añadir)

int ints[100]; 
int i; 
int *pi; 

for (i = 0; i < 100; ++i) 
{ 
    printf("%d", ints[i]); 
} 

for (pi = ints; pi < ints + 100; ++pi) 
{ 
    printf("%d", *pi); 
} 

Answer 2

Hay una gran y repetitivo transformada de Hough en un trozo de código que estoy vagamente adjunto demasiado . El responsable de esa parte del código ha estado experimentando con matrices dispersas (en realidad, un C++ std::map introducido en el índice de la celda si entendí bien su presentación) para el acumulador con cierto éxito.

Supongo que la velocidad se relaciona con problemas de localidad de caché, y ciertamente depende de que los datos sean escasos.

---

Actualización: El software que se hace referencia anteriormente está destinado a servir para muchos experimentos de física de partículas, pero se utilizó originalmente en un proyecto de banco de pruebas (es decir, a pequeña escala). Como nos tomamos en serio la tarea de hacer proyectos más grandes y comenzamos a hacer Monte Carlo para ellos, la transformada Hough ha vuelto a ser una especie de cuello de botella incluso con la matriz dispersa.

Todavía no tenemos una solución, pero uno de los colegas encontró Gandalf que incluye "fast hough transform", que parece evaluar la transformación en forma de árbol cuádruple (en 2D, presumiblemente se usa un octárbol en 3D) para reducir el orden del trabajo. Probablemente vamos a experimentar con esto.

Otra actualización: Un colega finalmente implementó una transformación Hough progresiva y probabilística en nuestro código que actualmente parece ser la versión más rápida que tenemos. Funciona mejor si no requiere que cada punto se asigne a una línea.

Answer 3

Dependiendo de su aplicación, hay numerosas formas de optimizar la Transformación de Hough y es posible que el último código sea de bajo nivel. Comenzaría con HT aleatorizado o HT multirresolución, seguido de la fusión de aproximaciones híbridas. Creo que es mejor optimizar el algoritmo primero. El último paso sería utilizar la optimización del hardware como la memoria CAD.