Serve aiuto per vettorizzare questo codice

Question

Ho un'immagine a 8 bit. Per ogni pixel, ho bisogno di calcolare la sua posizione ordinale nella riga corrente. Ad esempio, se la riga è:

32 128 16 64, 

poi bisogno il risultato:

1 3 0 2, 

poiché 32 è il primo valore più alto nella riga, 128 è 3 ° posto, 16 è 0th alta e 64 è il 2 ° più alto.

Ho bisogno di ripetere la procedura sopra per tutte le righe dell'immagine. Ecco il codice non vettorizzati:

for (int curr = 0; curr < new_height; ++curr) 
{ 
    vector<pair<unsigned char, char> > ordered; 
    for (char i = 0; i < 4; ++i) 
    { 
     unsigned char val = luma24.at<unsigned char>(curr, i); 
     ordered.push_back(pair<unsigned char, char>(val, i)); 
    } 
    sort(ordered.begin(), ordered.end(), cmpfun); 
    for (int i = 0; i < 4; ++i) 
     signature.at<char>(curr, ordered[i].second) = i; 
} 

luma24 è l'immagine a 8 bit che sto leggendo da, e ha new_height righe e 4 colonne. signature è un'immagine firmata della stessa dimensione (ignora la differenza di segno per ora, poiché non è rilevante) - è dove sto memorizzando il risultato. cmpfun è una funzione comparativa banale.

ho cercato di vettorizzare il codice di cui sopra e ha ottenuto questo:

Mat ordinal; 
luma24.convertTo(ordinal, CV_16UC1, 256, 0); 
Mat sorted = ordinal.clone(); 
for (int i = 0; i < 4; ++i) 
    ordinal(Range::all(), Range(i, i+1)) += i; 
cv::sort(ordinal, sorted, CV_SORT_EVERY_ROW | CV_SORT_ASCENDING); 
bitwise_and(sorted, Scalar(0x00ff), ordinal); 
Mat ordinal8; 
ordinal.convertTo(ordinal8, CV_8SC1, 1, 0); 
ordinal8.copyTo(signature(Range::all(), Range(0, 4))); 

ho dovuto mettere in valigia il valore a 8 bit e l'ordinale 8-bit in un singolo canale a 16 bit poiché OpenCV non esegue ordina per immagini multicanale. Questo è quasi ciò di cui ho bisogno, ma non del tutto. Per l'ingresso ad esempio, mi dà:

2 0 3 1 

in quanto il valore più basso si trova nella seconda colonna, di prossima più basso è nella colonna 0, ecc Come posso fare per convertire questo per il risultato che ho bisogno, senza accedere a ciascun pixel individualmente?

In sostanza, ho bisogno di vettorizzare in qualche modo questo:

uint8_t x[] = {2, 0, 3, 1}; 
uint8_t y[4]; 
for (uint8_t i = 0; i < 4; ++i) 
    y[x[i]] = i; 

dove x è il risultato intermedio mio attuale codice vettorializzare mi dà e y è il risultato che voglio.

Si può fare?

Answer 1

Credo che questo farà il trucco per voi. Non richiede allocazioni o stack o ordinamenti, ma assume che il tuo intervallo sia 0-255 (ad esempio uint8). La più grande ipotesi: sarà performante solo se hai file larghe. Se sono veramente larghi 4 pixel, che io sono il < 256 è un pò brutto. Ci sono modi per farlo andare via, ma suppongo che i 4 pixel siano solo un "es." per semplicità.

void processRow (int* rowpos, uint8_t* pixelsForRow, int w) { 
    uint32_t i, pv, v=0, hist[256]={0}; 
    for (i=0; i<w; i++)  hist[pixelsForRow[i]]++; 
    for (i=0; i<256; i++) {pv=hist[i]; hist[i]=v; v+=pv;} 
    for (i=0; i<w; i++)  rowpos[i] = hist[pixelsForRow[i]]++; 
} 

OK, quindi come funziona?
la riga 1 in questa funzione dichiara e svuota una tabella di istogramma.
riga 2 calcola un istogramma.
riga 3 lo trasforma in un tipo conteggiato - ed è per questo che hist utilizza dimensioni di elemento maggiori di uint8
riga 4 applica la posizione ordinata.

Ci sono 2 prese; Innanzitutto, nella riga 3, gli istogrammi sono "spostati di 1 indice", in modo che il primo valore sia sempre "0", non qualunque esso sia, e il secondo valore è ciò che il primo conteggio sarebbe stato, e così via. Il secondo trucco è il "++" nella riga 4 - assicura sempre che il valore ordinale sia unico.

Consente di provare sul proprio input:
[32 128 16 64]
riga 2: [0 ... 1 .... 1 .... 1 ... 0 ...] agli indici [0, 16, 32, 64, 128, 255] rispettivamente
riga 3: [0 ... 0 .... 1 .... 2 ... 3 ... 0] agli indici [0, 16 , 32, 64, 128, 255] rispettivamente
linea 4: [1, 3, 0, 2] ... sembra proprio

Consente provare sull'ingresso leggermente diverso:
[32 128 16 32]
riga 2: [0 ... 1 .... 2 .... 0 ... 1 ... 0] agli indici [0, 16, 32, 64, 128, 255] rispettivamente
riga 3: [0 ... 0 .... 1 .... 3 ... 3. ..0] agli indici [0, 16, 32, 64, 128, 255] rispettivamente
riga 4: [1, 3, 0, 2] ... perfetto


ma non sono abbastanza sicuro se soddisfa il tuo bisogno di vettorizzazione - :)

Answer 2

Un altro modo che posso pensare è, Per ogni riga, creare un albero di ricerca binario. Mentre facciamo l'inorder traversal possiamo ottenere il rank di ogni pixel.

Ogni elemento del nodo è una struttura

// Members of struct explained here. 
// row_pos: stores position of that pixel in that row. 
//  we populate this while creating binary search tree. 
// 
// rank: stores its rank in that row.() 
// while doing in-order traversal, we come to know rank of that pixel. At that point only, we update that pixel location with its rank. 

typedef struct node 
{ 
    int row_pos, rank; 
    node *left, *right; // left and right nodes. 
}; 

sequenza delle fasi per ogni riga sarebbe:

a) O (w): creare un albero binario di ricerca memorizzando la posizione di ogni pixel anche nel nodo.

b) O (w): iniziare l'attraversamento in ordine. Per ogni nodo, riempire la posizione dei pixel di quel nodo con rango (iniziare a contare con il primo nodo come 0).