Anti-aliasing: modi di determinare la frequenza massima preferita?

Question

Ho letto un po 'anti-aliasing e sembra avere un senso, ma c'è una cosa che non sono troppo sicuro di. Esattamente come si fa a trovare la massima frequenza di un segnale (nel contesto della grafica).

Mi rendo conto che c'è più di un caso in modo da suppongo ci sia più di una risposta. Ma prima lasciatemi dire un semplice algoritmo che credo rappresenti la massima frequenza in modo qualcuno può dirmi se sto concettualizzare nel modo sbagliato.

Diciamo che è un 1 dimensionale immagine, finita, e scala di grigi (in pixel). Sono corretto supponendo che potrebbe semplicemente eseguire la scansione di tutta la linea di pixel (nel dominio spaziale) alla ricerca di una per l'oscillazione minimo e l'inverso di quella più piccola oscillazione sarebbe la frequenza massima?

I valori Ex {23,26,28,22,48,49,51,49}

Frequenza: pertinenza set {}

(1/2) = 0,5: {28,22}

(1/4) = .25: {22,48,49,51}

Quindi sarebbe .5 essere la massima frequenza?

E quale sarebbe il modo ideale per calcolare questo per una linea di pixel simile a quello di cui sopra?

E su una nota più teorico, che cosa se il vostro input di campionamento era infinita (più simile al mondo reale)? Sarebbe un processo valida essere un po 'come:

Predetermine a decent interval for point sampling
Determine max frequency from point sampling
while(2*maxFrequency >  pointSamplingInterval)
{
pointSamplingInterval*=2
Redetermine maxFrequency from point sampling (with new interval)
}

So che questi algoritmi sono carichi di inefficienze, quindi quali sono alcuni dei modi preferiti? (Non ho bisogno di qualcosa di folle-ottimizzato, solo concetti fondamentalmente migliori)

Answer 1

Il modo corretto per affrontare questo sta usando una trasformata di Fourier (in pratica, una FFT, o Fast Fourier Transform )

La teoria funziona nel modo seguente: se si dispone di un insieme di pixel con colori / in scala di grigi, allora possiamo dire che l'immagine è rappresentata da pixel nel "dominio spaziale"; cioè, ogni singolo numero specifica l'immagine in una particolare posizione spaziale.

Tuttavia, ciò che realmente vogliamo è una rappresentazione dell'immagine nel "dominio della frequenza". Invece di ogni singolo numero specificando ciascun pixel, ciascun numero rappresenta l'ampiezza di una particolare frequenza nell'immagine nel suo complesso.

Lo strumento che converte dal "dominio spaziale" al "dominio della frequenza" è la trasformata di Fourier. L'uscita del FT sarà una sequenza di cifre che specificano il contributo relativo di frequenze diverse.

Al fine di trovare la frequenza massima, si esegue il FT, e guardano le ampiezze che si ottiene per le alte frequenze -, allora è solo una questione di ricerca dalla frequenza più alta verso il basso fino a colpire il vostro "ampiezza minima significativa "soglia.

è possibile codificare il proprio FFT, ma è molto più facile, in pratica, di utilizzare una libreria di pre-confezionati come FFTW

Answer 2

Non si esegue la scansione di un segnale per la frequenza più alta e quindi scegliere la frequenza di campionamento: Si sceglie una frequenza di campionamento che è abbastanza alto per catturare le cose che si desidera catturare, e poi si Filtro il segnale per rimuovi alte frequenze. Si butta via tutto superiore alla metà della frequenza di campionamento prima di assaggiare esso.

  

Ho ragione nel ritenere si potrebbe   semplicemente scansione dell'intera linea di pixel (in   il dominio spaziale) alla ricerca di un per   l'oscillazione minimo e la   inversa di quella più piccola oscillazione   sarebbe la frequenza massima?

Se si dispone di una linea di pixel, quindi il campionamento è già fatto. E 'troppo tardi per applicare un filtro antialiasing. La frequenza più elevata che potrebbe essere presente è la metà della frequenza di campionamento ( "1 / 2px", immagino).

  

E su una nota più teorico, cosa   se l'input di campionamento era infinita   (Più simile al mondo reale)?

Sì, questo è quando si utilizza il filtro. In primo luogo, si dispone di una funzione continua, un'immagine di vita reale (frequenza di campionamento infinito) come. Poi si filtra per rimuovere tutto sopra fs / 2, allora si campionarlo a fs (digitalizzare l'immagine in pixel). Telecamere in realtà non fanno alcun filtro, che è il motivo per cui si ottiene modelli Moire quando si fotografa mattoni, ecc.

Se siete anti-aliasing computer grafica, si deve pensare al continuo funzione matematica ideale prima, e pensare a come si potrebbe filtrare e digitalizzarlo per produrre l'output sullo schermo.

Per esempio, se si desidera generare un'onda quadra con un computer, è possibile non solo ingenuamente si alternano tra i valori massimi e minimi. Sarebbe proprio come il campionamento di un segnale di vita reale senza filtrare prima. Le armoniche superiori avvolgono indietro nella banda base e causano un sacco di picchi spuri nello spettro. È necessario generare i punti come se fossero state campionate da una funzione matematica continua filtrata:

Answer 3

Credo che questo articolo dal sito di O'Reilly potrebbe anche essere utile a voi ... http://www.onlamp.com/pub/a/python/2001/01/31/numerically.html ... in là stanno facendo riferimento alla frequenza analisi dei file audio, ma si ti dà l'idea.

Answer 4

Credo che quello che vi serve è un'applicazione di analisi di Fourier ( http://en.wikipedia.org / wiki / Fourier_analysis ). Ho studiato questo, ma mai usato in modo da prendere con un pizzico di sale, ma credo che se lo si applica correttamente al set di numeri si otterrà un insieme di frequenze, che sono componenti della serie e poi si può scegliere fuori più alto.

Non si può puntare ad un pezzo di codice che fa questo, ma sono sicuro che sarebbe stato là fuori da qualche parte.