riempimento accumulatore per trasformazione Hough

Question

Ho scritto un pezzo di codice che deve essere ottimizzato. Mi sono sentito come se avessi consultato la community per vedere se quel codice fosse davvero ottimale. Riempie l'accumulatore per la trasformazione di Hough. In realtà ho appena copiato la maggior parte del codice dalla libreria OpenCV. Grazie!

---

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 non lo è. Sostituire il maggior numero degli usi di [] il più possibile con una semplice aritmetica del puntatore per iterare gli array in questione. Estrarre le espressioni invarianti in variabili locali.

Tuttavia, la prima domanda è, il tuo profiler mostra che questo codice è un collo di bottiglia nel contesto dell'intera app. Se no, perché preoccuparsi di micro-ottimizzare questo?

EDIT: ciclo micro-ottimizzazione - preferisco la seconda come nessuna indicizzazione matrice richiesto (Mult contro aggiungere)

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

V'è un ampio e ripetitivo trasformata di Hough in un pezzo di codice che sto vagamente attaccato troppo . Il manutentore di quella parte del codice ha sperimentato con array sparsi (in realtà un C++ std::map digitato sull'indice delle celle se ho capito bene la sua presentazione) per l'accumulatore con un certo successo.

Suppongo che la velocità sia correlata ai problemi di localizzazione della cache, e sicuramente dipende dai dati sparsi.

---

Aggiornamento: Il software di cui sopra è destinato a servire molti esperimenti di fisica delle particelle, ma è stato originariamente utilizzato su un progetto banco di prova (cioè piccola scala). Dato che siamo diventati seri nel fare progetti più grandi e abbiamo iniziato a fare Monte Carlo per loro, la trasformazione di Hough è tornata a essere un po 'più complessa anche con la matrice sparsa.

Finora abbiamo non hanno una soluzione, ma uno dei colleghi hanno scoperto Gandalf che comprende "fast hough transform", che sembra valutare il trasformare in un quad-albero come modo (in 2D, presumibilmente si utilizza una struttura ottale in 3D) ridurre l'ordine di lavoro. Probabilmente stiamo andando a sperimentare con questo.

Ulteriore aggiornamento: Un collega ha implementato una trasformazione progressiva e probabilistica di Hough nel nostro codice che attualmente sembra essere la versione più veloce che abbiamo. Funziona meglio se non si richiede che ogni punto venga assegnato a una linea.

Answer 3

A seconda dell'applicazione, esistono numerosi modi per ottimizzare la Trasformazione dell'Hough e il giochetto con codice di basso livello è probabilmente l'ultimo di essi. Vorrei iniziare con Randomized HT o Multiresolution HT, seguito dall'unione di approccio ibrido. Credo che sia meglio ottimizzare l'algoritmo prima. L'ultimo passo sarebbe fare l'ottimizzazione dell'hardware come la memoria CAD.