Qualcuno conosce un algoritmo di filtraggio mediano veloce per array a 16 bit (unsigned short) in C++?Fast Median Filter in C++
questo sembra abbastanza promettente, ma sembra solo a lavorare con array di byte. Qualcuno sa o come modificarlo per funzionare con i cortometraggi o un algoritmo alternativo?
Here (PDF) è qualcosa per C, è una carta con il titolo "Ricerca mediana veloce: un'implementazione ANSI C". L'autore afferma che è O (log (n)), fornisce anche del codice, forse ti aiuterà. Non è migliore del tuo codice suggerito, ma forse vale la pena dare un'occhiata.
La carta collegata nella domanda è O (1) che è migliore di O (log n). –
Sì, ma questo forse dà alcuni altri impulsi, ma hai decisamente ragione. Ho fatto una piccola modifica, chiarendo la mia intenzione. –
@MarkRansom: O (1) non significa automaticamente migliore di O (log (n)) poiché c'è sempre una costante che nasconde la notazione O. In questo caso, l'algoritmo O (1) è molto più lento dell'algoritmo O (log (n)) (per valori diversi da quelli a 2-bit o forse a 4-bit). La carta O (1) funziona con gli istogrammi, il che rende il tempo di esecuzione per pixel proporzionale a 2^b, dove b è il numero di bit per canale, che per 8 bit è 256 e per 16 bit è 65536 (anche se questi numeri sono costanti, quindi O (1)). Questo rende rapidamente l'algoritmo O (1) _ estremamente lento_ più bit si aggiungono ai valori del canale. – HelloGoodbye
La tecnica nella carta si basa sulla creazione di un istogramma con 256 bin per un canale di pixel da 8 bit. La conversione a 16 bit per canale richiederebbe un istogramma con 65536 bin e un istogramma è richiesto per ogni colonna dell'immagine. Gonfiare i requisiti di memoria di 256 rende questo un algoritmo meno efficiente in generale, ma ancora probabilmente fattibile con l'hardware di oggi.
L'utilizzo dell'ottimizzazione proposta per suddividere l'istogramma in sezioni grossolane e fini dovrebbe ridurre ulteriormente il tempo di esecuzione a soli 16x.
Per valori di raggio ridotto penso che i metodi tradizionali di filtraggio mediano saranno più performanti.
Vedere le equazioni 4 e 5 nel seguente documento. La complessità è O (N * W) dove W è la larghezza del filtro e N è il numero di campioni.
So che questa domanda è un po 'vecchio, ma ho anche avuto interessati a filtraggio mediano. Se si sta lavorando con segnali o immagini, allora ci sarà una grande sovrapposizione di dati per la finestra di elaborazione. Questo può essere sfruttato.
ho postato un certo codice di riferimento qui: 1D moving median filtering in C++
Si modello basato così dovrebbe funzionare con la maggior parte dei tipi di dati POD.
Secondo i miei risultati std::nth_element ha scarse prestazioni per una mediana in movimento, in quanto ogni volta deve ordinare la finestra dei valori.
Tuttavia, utilizzando un pool di valori che viene mantenuto ordinato, è possibile eseguire la mediana con 3 operazioni.
La mediana ora è il valore medio nella piscina.
Spero che qualcuno trovi questo interessante e contribuisca alle loro idee!
Questo articolo descrive un metodo per il filtraggio mediano di immagini che viene eseguito in O (log r) tempo per pixel, dove r è il raggio del filtro, e funziona per qualsiasi tipo di dati (che si tratti di 8 bit interi o doppie):
hai provato std :: nth_element? È O (n) rispetto a O (n log n) per un quicksort. – smocking
Non si desidera modificare questo algoritmo per farlo funzionare a breve poiché il tempo di esecuzione per pixel è proporzionale a 2^n, dove n è il numero di bit nel tipo di dati utilizzato. 256 per gli array a 8 bit è già abbastanza doloroso, non si vuole passare a 65536 per gli array a 16 bit. Vedi la mia risposta per un algoritmo più veloce, anche se è O (log r) per pixel invece di O (1). – HelloGoodbye
Se non si desidera eseguire il filtraggio mediano, che è quello che si fa per l'elaborazione dell'immagine ad esempio dove si trova una mediana per ogni pixel, ma si vuole trovare solo una mediana, il commento di @ smocking è rilevante. – HelloGoodbye