Vlákno názorů k článku Modifikovaný algoritmus RWA a algoritmus MPA od r0b0t - "První nevýhodou tohoto algoritmu je nutnost hledat pro...
-
r0b0t (neregistrovaný)"První nevýhodou tohoto algoritmu je nutnost hledat pro každý vypočítaný pixel jeho protějšek ve frontě, nebo v rastrovém obrazu."
Ja tomu nejak nerozumim ...
Spoctu pixel, kouknu na prislusne misto v bitmape jestli je tam porad defaultni barva, pokud ne - strcim do fronty, pokud ano - zahodim. Kde je tu nejake hledani?
Abych mel frontu kratsi, muzu se divat i do ni, jestli tam uz spocteny pixel nemam. Ale to neni nutne. Kdyz to delat nebudu, zvysi se mi pametove naroky na frontu a celkovy pocet iteraci v nejhorsim pripade na dvojnasobek. Coz by mohlo (a pro nektere IFS urcite je) byt rychlejsi a prumerne zhorseni by mohlo byt dost male na to, aby se to vyplatilo.
Adresou pixelu se asi mysli jeho souradnice v rastru. Pokud bych zpetne neprohledaval frontu, mohl bych si misto toho do fronty ukladat souradnice bodu v rovine a usetrit tak jednu konverzi a navic zvysit presnost tim, ze by nedochazelo ke konverzi E2 -> rastr -> E2.
A dalsi vyhoda nesahani do fronty je lepsi paralelizovatelnost ;-) -
Pavel TišnovskýZlatý podporovatelDobry den,
nejprve k te adrese pixelu. Tou je opravdu myslena adresa v bitmape, presneji receno offset od zacatku bitmapy. Druhou moznosti (IMHO lepsi) je ulozeni souradnic x,y v jednom 32bitovem slove, napriklad tak, ze hornich 16 bitu je pro x a dolnich 16 bitu pro y. "Extrakce" souradnic je potom velmi rychla, v podstate staci jeden bitovy posun a jedno maskovani (AND) a na x86 dokonce ani to ne :-), pokud se napriklad vhodne pouzije MMX (zcela idealni vec prave pro IFS, kde se provadi maticove zapasne linearni transformace).
Problem s frontou je ten, ze delka fronty muze prerust kapacitu RAM na ruznych embedded zarizenich - autori tohoto algoritmu pomoci IFS kodeku prenaseli video v realnem case a predpokladali vyuziti (dekoderu) prave v embedded zarizenich (enkoder je samozrejme mnohem slozitejsi). Pokud by se napriklad pracovalo s polovicnim rozlisenim videa, tj. 352x288 pixelu, muze dvojnasobna maximalni delka fronty znamenat nutnost pouziti RAM s dvojnasobnou kapacitou; (i kdyz tady by se dalo optimalizovat, protoze pro ulozeni souradnice pixelu by stacilo mene nez 32 bitu).
Mimochodem, podobny problem se resil s MPEG 1, 2 a 3 a naroky na pamet v prehravacich (to je dost podstatne, ceny prehravacu jsou citlive na ceny RAM). Tady slo o pocet snimku, ktere musi byt ulozeny v pameti kvuli pouziti I a B framu.
