Eliminare ramificazione quando ritrovamento mediano in un binario {0, 255} immagine

Question

Ho un'immagine di binaria, il binario valore di è 0 o 255. il tipo di dati di immagine è unsigned char. Qui ho bisogno di fare un filtraggio mediano su questa immagine.

Penso che usando un istogramma per trovare la mediana dovrebbe essere veloce. Utilizzando alcuni codici per spiegare:

unsigned int hist[2] = {0, 0}; 

for (int i = 0; i < kernel_h; ++i) { 
    for (int j = 0; j < kernel_w; ++j) { 
      if (image(i,j) == 0) { 
       hist[0]++; 
      } 
      else { 
       hist[1]++; 
      } 
    } 
} 

Quindi, è possibile ottenere il valore medio molto velocemente. Ma a causa di questo caso, i codici ancora potrebbe essere migliorato:

int counter = 0; 

for (int i = 0; i < kernel_h; ++i) { 
    for (int j = 0; j < kernel_w; ++j) { 
      if (image(i,j) == 0) { 
       counter++ 
      } 
      else { 
       counter--; 
      } 
    } 
} 

Ma mi chiedo c'è qualche altro modo per eliminare il ramo if-else, come l'utilizzo di operazioni su bit per mappare {0, 255} a qualcosa di così che potremmo semplicemente aggiornare una bandiera senza diramazioni.

Qualcuno suggerimento?

Answer 1

Tutti i bit di 255 sono 1 in modo da poter semplificare che "se" per:

hist[image(i,j) & 1]++; 

Se si desidera utilizzare il contatore si può fare:

counter += (image(i,j) & 2)-1; 

Answer 2

Questo calcolo può essere fatto MOLTO più veloce e più specificamente O(n) nel numero di pixel e indipendente dalle dimensioni del kernel.

L'idea è di eseguire prima una "conversione di scansione" calcolando uno summed area table in cui il valore di ciascun pixel (x, y) viene sostituito dalla somma di tutti i pixel da (0, 0) a (x, y) .

Dato questo è possibile sapere in tempo fisso il numero di pixel si trovano in qualsiasi rect utilizzando

st(x0, y0) + st(x1, y1) - st(x0, y1) - st(x1, y0) 

e dato che ogni pixel è 0 o 1 la somma che dà il conteggio di quelli.

Il tempo di calcolo totale è O(n) per creare la tabella delle somme e O(n) per eseguire il filtraggio mediano, indipendentemente dalla dimensione dell'area in cui eseguire il conteggio.

Nel caso della mediana filtraggio si potrebbe precompute il risultato a seconda della somma e la formula nel ciclo interno potrebbe essere:

result[x] = res[p0[x] + p1[x+box] - p0[x+box] - p1[x]]; 

Inoltre tabella somma non ha bisogno di essere calcolato completamente (così richiede un numero intero per pixel) ma potrebbe essere calcolato "pigramente" mentre si esegue il risultato ed è necessario solo il numero di righe della tabella rispetto all'altezza del kernel mantenendo il tempo di calcolo O(image_width*image_height) ma richiede solo la memoria kernel_height*image_width.