Aliasing
Izvor: Wikipedija
Alias (engl. prilog: inače zvan; imenica: Krivo ime, ['eiliaes]) Aliasing je pojam koji opisuje posebnu pojavu pri analogno-digitalnoj konverziji, poslijedica je nedovoljne učestalosti uzorkovanja nekog analognog signala, a očituje se kao pojava lažnog nisko-frekventnog signala. S aliasingom se iznimno često susrećemo u svakodnevnom životu; primjerice pri gledanju starih «western» filmova možemo uočiti prividno kretanje zavora kotača kočija u suprotnom smjeru od prirodnog smjera okretanja, ili istu stvar uočavamo pri prijenosu nekih auto-moto trka. Ovaj efekt nastaje zbog toga što je frame-rate kamere nedovoljan za praćenje kutne brzine kotača. Kada vozilo usporava, kotači prividno promijene smjer obrtanja, ubrzaju, uspore i ostanu stajati na mjestu dok kamera ponovno ne uhvati prirodno okretanje kotača. Strogo govoreći ovo se zove vremenski (temporalni) aliasing. Prostorni aliasing je, primjerice, pojava nazubljenih linija koja se javlja pri iscrtavanju računalne grafike. Akord odsviran na glazbenom instrumentu također je primjer aliasinga, ugodnog uhu, ako je pravilno izveden. Ovdje će isključivo biti riječ o aliasingu koji se javlja u računalnoj grafici.
Uz već spomenutu nazubljenost linija, kao primjer aliasinga treba spomenuti i interferenciju koja se javlja na područjima u kojima se sastavni objekti izmijenjuju visokom frekvencijom. Ta pojava naziva se Moire interferencijom.
Većina signala u zbilji jest kontinuirana, dok današnja digitalna računala raspolažu isključivo s konačnim diskretnim vrijednostima. To znači ako se neki signal želi obrađivati na računalu on mora biti uzorkovan, odnosno vrijednosti signala se pohranjuju u diskretnim vremenskim ili prostornim točkama. U većini slučajeva ovaj proces se odvija zadovoljavajuće, no postoje signali koji se ne mogu točno predstaviti računalom. Prikazivanje kontinuirane slike ( ili bilo kojeg signala u tom pogledu) sastoji se od dva koraka: uzorkovanje slike (sliku možemo gledati kao niz scan linija) i rekonstrukcija uzorkovanih vrijednosti za njihovo prikazivanje na zaslonu. U praksi se problemi mogu javiti u oba koraka i za primijetiti je da slika koja se uzorkuje može potjecati, ili iz izvora izvan računala, ili kao rezultat nekog od algoritama za renderiranje. Najjednostavniji postupak uzorkovanja jest točkasto (point sampling). To znači da se vrijednosti slike određuju na mjestu pojedinog pixela ( ili nekih X-Y koordinata unutar pixela). Međutim, ova metoda će često podbaciti u bilježenju sitnih detalja koji upadaju između pojedinih točaka uzorkovanja. Točkasto uzorkovanje se može poboljšati uzimanjem više uzoraka unutar samog pixela i interpoliranjem vrijednosti za konačnu boju pixela. Ovom metodom, zvanom višestruko uzorkovanje ili naduzorkovanje, u konačnici više detalja doprinosi vrijednosti pixela. Nažalost, ova metoda ima i svoje nedostatke: Prvo, zahtjeva više izračunavanja i postavlja mnogo veće memorijske zahtjeve na sustav. Drugo, računalna grafika nerijetko sadrži beskonačno visoke frekvencije koje se ne mogu točno reproducirati bez obzira na gustoću uzorkovanja. Primjeri beskonačno visokih frekvencija bili bi oštri rubovi (nagle promjene u intenzitetu ekvivalentne su beskonačnim frekvencijama), vrhovi mnogokuta ili beskonačna šahovska ploča promatrana iz kuta (ovakav aliasing ispravlja se anizotropnim filtriranjem).
Bez obzira koliko gusto uzorkovali signal uvijek ćemo previdjeti informaciju sadržanu između točaka uzorkovanja. Dakle, povećanjem rezolucije prikaza aliasing se nikada ne uklanja.
Drugi pristup uzorkovanju, površinsko uzorkovanje (area sampling), izbjegava problem previđanja detalja između točaka uzorkovanja. U površinskom uzorkovanju, izračunava se površina svakog lika koji upada unutar pixela i ove se vrijednosti interpoliraju za dobivanje konačne vrijednosti pixela. Ovo se zove netežinsko površinsko uzorkovanje, jer se čitavo područje pixela smatra jednako doprinosećim. Problem se javlja, kada bi na primjer, mali objekt ušao u područje pixela - njegovo kretanje ne bi uzrokovalo promjenu boje pixela. Promjena bi se zbivala samo pri prijelazu granice iz jednog pixela u drugi. Odgovor na taj problem je u težinskom prostornom uzorkovanju, koje koristi težinsku funkciju za naglašavanje objekata u blizini središta pixela. Ovim pristupom objekt iz prethodnog primjera svojim kretanjem izaziva postupnu promjenu boje pixela. Međutim i ova metoda ima manu, u tome što na boju pixela utjecaj imaju objekti koji strogo upadaju unutar površine pixela. Poslijedica toga nagla je promijena u boji pixela, pri ulaženju i izlaženju objekta iz područja pixela, a manifestira se kao treperenje. Riješenje je u korištenju filtra s preklapanjem koji je učvršćen u pixelu, ali ima veću površinu, i u obzir dolaze i objekti izvan samog pixela. Na ovaj se način izbjegava nagla promijena u vrijednosti pixela, čak i pri prijelazu objekta iz jednog pixela u drugi.
[uredi] Teorija uzorkovanja
Signale osim u vremenskoj, odnosno prostornoj domeni poput pixela na ekranu, možemo promatrati i u frekvencijskom području. Fourierov teorem kaže da se svaki periodični signal može prikazati kao beskonačna suma (red) sinusnih valova različitih frekvencija (osnovna frekvencija signala i njeni višekratnici), amplituda i faza. Također, i neperiodični signali (poput slika) mogu se promatrati na ovaj način ako ih cijele uzmemo kao jedan period periodičnog signala. Postupak prebacivanja signala iz vremenskog u frekvencijsko područje, i obrnuto, naziva se Fourierova i inverzna Fourierova transformacija. Poznavanje samog postupka nije važno za razumijevanje pojmova antialiasinga, već je važnije imati na umu da se neke operacije mogu jednostavnije obavljati u frekvencijskom nego li u vremenskom području, dok su opet, neke druge prikladnije obradi u prostornoj domeni. Nyquistov teorem uzorkovanja kaže da je za uspješno rekonstruiranje signala potrebno uzorkovanje barem dvostruko veće frekvencije od najviše frekvencije toga signala. Ova se minimalna frekvencija uzorkovanja naziva Nyquistovom. Primjerice zapis Audio Cd-ova uzorkovan je na 44 KHz da bi mogao obuhvatiti mehaničke valove frekvencije do 22 KHz koji predstavljaju gornju granicu ljudskog sluha. Promatranjem signala u frekvencijskom području lako se vidi, da pravokutni impuls u vremenskom području sadrži komponente beskonačnih frekvencija u svom frekvencijskom području. Primjerice, uzorkovanjem bijelog mnogokuta na crnoj pozadini, stvara se slična pravokutna funkcija za svaku scan liniju koja siječe poligon – ako je gustoća uzorkovanja dovoljna da uhvati detalje poligona. Frekvencija uzorkovanja morala bi biti beskonačna ako bi se željelo točno zapisati granice poligona, što naravno nije realno ostvarivo.
Da bi smo uspješno uzorkovali i rekonstruirali neki analogni kontinuirani signal, njegove najviše frekvencije ne smiju prelaziti Nyquistovu, ili se te frekvencije moraju ukloniti korištenjem nisko-pojasnog (low band) filtera. Idealni nisko-pojasni filter ( Pravokutnik – za |f|<fg fja je 1, inače 0) uklanja sve frekvencije iznad određenog praga (fg)bez ikakvog utjecaja na propuštene. Da bi smo izvršili nisko-pojasno filtriranje sliku iz prostorne domene moramo prebaciti u frekvencijsku. Srećom, množenje signala sa pravokutnim nisko-pojasnim filtrom u frekvencijskoj domeni jednako je konvoluciji signala sa inverznom Fourierovom transformacijom pravokutnog filtra u prostornoj domeni. Konvolucija je fundamentalna operacija u obradbi signala i teoriji informacije No ono što je zanimljivije, u razmatranju antialiasinga, jeste odabir filtra za operaciju. Inverzna Fourierova transformacija pravokutnog impulsa jeste fja sinc, definirana kao sin(x)/x. Nažalost ova fja divergira u beskonačnosti, odnosno ne teži k nuli, a uz to poprima i negativne vrijednosti. Pomislili bi smo možda, da bi odrezivanje filtra bila dobra ideja, s obzirom da sa udaljenjem od ishodišta vrijednosti fje bivaju sve manje i da time neće mnogo utjecati na rezultat. Međutim, ovaj pristup stvara probleme u obliku «zvonjave» u slici, također poznate kao Gibbs fenomen. Ovo uzrokuje da Fourierova transformacija odrezanog pravokutnog filtra ima nabore okolo diskontinuiteta pravokutnog impulsa. (Vidi sliku dolje). Povećanjem praga odrezivanja, ovaj efekt biva manje vidljiv, ali amplituda poremećaja ostaje jednaka. Negativne vrijednosti stvaraju novi problem: mogu unijeti negativne vrijednosti u filtriranu sliku, koje se naravno ne mogu vizualizirati, i moraju se svesti na nulu.
Završna faza u ovom procesu jest rekonstrukcija, što znači obnavljanje izvornog signala iz uzorkovanog diskretnog oblika. U praksi se rekonstrukcijska faza objedinjuje s nisko-pojasnim filtriranjem, stoga što je konačni signal digitalan i samo je potrebno da bude definiran u diskretnim točkama prostora (prikaznim elementima na zaslonu).
Antialiasing metode mogu se kategorizirati na više načina, od kojih nijedan nije savršen. Jedna od kategorizacija jest između pre- i post- metoda filtriranja. Zbog toga što su novija istraživanja isljučivo orijentirana ka hardveru, složenije i sporije metode pred-filtriranja postale su sve više zanimljive. Druga kategorizacija razmatra analitičke metode, edge antialiasing i naduzorkovanje, i ona će se ovdje primjenjivati. Neki u potpunosti zanemaruju pre-filtering i analitičke metode, i isključivo govore o A-bufferingu i naduzorkovanju Sve u svemu, razvidno je da globalna taksonomija metoda antialiasinga još uvijek nije uspostavljena. Pred-filtriranje se odnosi na uklanjanje frekvencija iz slike koje nadilaze Nyquistovu, prije obavljanja uzorkovanja. U osnovi, ovo znači primjenu nisko-pojasnog filtra na sliku i nakon toga uzorkovanje. U praksi, ovo znači izračunavanje područja doprinosa pojedinih poligona za svaki pixel. Ovo je jedina metoda koja u potpunosti uklanja efekte aliasinga. Predfiltriranje se mora obaviti prije rasterizacije (uzorkovanja), i stoga ju nije tako jednostavno dodati standarnom rendereru, poput primjerice višestrukog uzorkovanja ili naduzorkovanja.
Metode post-filtriranja razmatraju prekrivenost pixela samo u diskretnim točkama, umjesto izračunavanja točne površine. Ovo dovodi do metoda koje se lakše hardverski implementiraju, a i dovoljno su brze za real-time renderiranje. No, zbog njihove diskretne naravi, one nikada u potpunosti ne mogu ukloniti aliasing. Sve što one mogu jest pomaknuti prag aliasinga više u frekvenciji dodavanjem subpixel uzoraka, i po mogućnosti zamijeniti vidljivi aliasing za šum (pseudoslučajnim uzorkovanjem subpixela) ili zamućenjem (blurring- interpoliranjem više subpixela u jednu vrijednost).
[uredi] Višestruko uzorkovanje
U daljnjem dijelu teksta pozabaviti ćemo se s supersamplingom i multisamplingom - tehnologijama koje svoju primjenu nalaze u aktualnom real-time rendering grafičkom hardveru, poput onog Nvidia-e i ATI-ja. Riječ je o najjednostavnijim antialiasing metodama, čija je međusobna razlika često nejasna, a za neke bi se implementacije moglo reći da potpadaju pod obje kategorije. Međutim, obje metode pripadaju postfiltriranju, s obzirom da se filtriranje obavlja nakon renderiranja. U naduzorkovanju slika se prvo renderira u većoj rezoluciji, a zatim skalira nazad u konačnu veličinu. U višestrukom uzorkovanju, svaki pixel uzorkovan je iz podpixel lokacija, i ti se uzorci koriste za rekonstrukciju konačne vrijednosti pojedinog pixela. (Nije ni čudo što ljudi stalno miješaju ova dva pojma) U naduzorkovanju proces općenito izgleda ovako:
- Stvori virtualnu sliku više rezolucije nego one konačne
- Primjeni nisko-propusni filter
- Obnovi filtriranu sliku
Korak 1. je jednostavan, ali zahtjeva velike količine memorije i memorijske propusnosti. U vidu daljnje optimizacije, koraci 2. i 3. se objedinjuju stoga što rekonstrukcija u analogni signal nije potrebna. Kao što je već prije ukazano, sinc fja nije pogodna za praktičnu primjenu filtriranja. Pravokutni filter, jednak je jednostavnoj usrednjenoj vrijednosti uzoraka ( zapamtimo riječ je o konvoluciji u prostornoj domeni – diskretnoj, naravno), također poznat kao netežinsko površinsko uzorkovanje, bio bi jednostavniji za primjenu. Nažalost, on je veoma loš kao filtar stoga što propušta beskonačno visoke frekvencije i atenuira one željene. U praksi sinc2 i Gaussov filter su daleko bolji. Sinc2 je Fourierova transformacija trokutne fje, a Gaussova fja je Fourierova transformacija same sebe. Obje brzo opadaju, i stoga se lakše izračunavaju. Korištenje sinc2 fje poznatije je kao bilinearno filtriranje. U svakoj dimenziji koriste se 2 uzorka, dakle, za bilinerano filtriranje potrebno je 4 uzorka.
