Vedci zrýchlili Fourierovu transformáciu, zrýchli sa kompresia videa

DSL.sk, 19.1.2012

Výskumníci z Massachusettského technologického inštitútu, MIT, v stredu informovali o vyvinutí nového algoritmu implementujúceho tzv. Fourierovu transformáciu, ktorý je rýchlejší ako doterajšie algoritmy.

Fourierova transformácia respektíve jej zjednodušená podoba kosínusová transformácia je využívaná v mnohých stratových kompresných algoritmoch, ktorých úlohou je komprimovať prirodzené dáta ako sú napríklad hudba, zvuk, obraz a video reálnych scén.

Pri tzv. diskrétnej Fourierovej transformácii sa navzorkovaný signál vyjadrí ako vážený súčet rovnakého počtu kosínusových a sínusových funkcií s rozličnou frekvenciou ako je vzoriek nameraných dát.

U prirodzených signálov ako je napríklad zvuk a obraz reálnych scén väčšina frekvencií ale vplýva na výsledný signál málo a dostatočne presne je ho možné vyjadriť súčtom výrazne menšieho počtu významných frekvencií, napríklad u blokov obrázkov o veľkosti 8x8 pixelov používaných vo viacerých algoritmoch je to podľa výskumníkov priemerne pomocou 7 frekvencií namiesto 64.

Dáta je tak následne možné komprimovať uložením iba parametrov tohto menšieho počtu frekvencií a dosiahnuť tak významnú úsporu.

Pre Fourierovu transformáciu sa doteraz používal algoritmus Fast Fourier Transform, FFT, ktorého zložitosť pri dátach o veľkosti n prvkov je O (n * log n).

Nový algoritmus vyvinutý na MIT je výrazne rýchlejší najmä pri malom počte významných frekvencií k, výrazne menšom ako počet prvkov n. Pri signále zloženom presne iba z k alebo menej ako k frekvencií a vôbec žiadnych ďalších dosahuje zložitosť algoritmu O (k * log n), pri hľadaní k významných zložiek v signále zloženom aj z ďalších menej významných zložiek zložitosť O (k * log n * log (n / k)). Algoritmus pracuje rozdelením frekvencií na také pásma, aby sa v každom nachádzala pravdepodobne iba jedna významná frekvencia, s následným rýchlym identifikovaním tejto jednej významnej frekvencie.

Návrhy algorimov lepších ako FFT pre signály s malým počtom významných frekvencií už existovali aj doteraz, žiadny nebol ale efektívnejší ako FFT pre ľubovolné signály a väčšina bola príliš zložitá pre praktické implementácie.

Na MIT vyvinutý algoritmus podľa výskumníkov môže mať aj v praktických implementáciách vyššiu rýchlosť ako FFT a to v niektorých prípadoch až desaťnásobne a špeciálne užitočný môže byť pri kompresii obrázkov a videa.


Najnovšie články:



Diskusia:

som zvedavy Od reg.: Gyrxiur | Pridané: 19.1.2012 9:45 kto pochopil uplne vsetko v clanku? Odpovedať Známka: 3.8 Hodnotiť:

Re: som zvedavy Od: rouen | Pridané: 19.1.2012 9:50 kazdy student FEI, FIIT, a MatFyzu, ktory to nepresiel na tahakoch :) Odpovedať Známka: 8.6 Hodnotiť:

Re: som zvedavy Od: igor8 | Pridané: 19.1.2012 10:05 Ja som prešiel na ťahákoch a bombách a pochopil som. Odpovedať Známka: -2.4 Hodnotiť:

Re: som zvedavy Od reg.: ccccc | Pridané: 19.1.2012 10:43 ich trosku precenujes .. kosinusova tranformacia sa uci este na strednej skole Odpovedať Známka: -7.7 Hodnotiť:

Re: som zvedavy Od: ... | Pridané: 19.1.2012 11:18 transformacie sotva. vsak uz nevedia na strednych skolach pomaly derivovat a integrovat, komplexne cisla im nic nehovoria a nie to este rady a transformacie. Odpovedať Známka: 8.6 Hodnotiť:

Re: som zvedavy Od: ľščľč | Pridané: 19.1.2012 11:29 derivacie a integrali sa skor neucia ako ucia. mozno nekde na gymploch Odpovedať Známka: 6.6 Hodnotiť:

Re: som zvedavy Od: ... | Pridané: 19.1.2012 11:40 Zavisi od skoly, na gymploch to kedysi platilo, uz teraz nemusi a niektore priemyslovky su omnoho dalej v matike nez gymple. Odpovedať Známka: 5.5 Hodnotiť:

Re: som zvedavy Od: drahomiiira | Pridané: 19.1.2012 14:10 tak tak.. napr. mi sme sa derivacie ucili uz v 1. rocniku na priemyslovke co si pamatam.. Odpovedať Známka: -0.7 Hodnotiť:

Re: som zvedavy Od: Ujo_ja | Pridané: 19.1.2012 14:33 A co gramatika, tu ste sa ucili? Odpovedať Známka: 7.6 Hodnotiť:

Re: som zvedavy Od: drahomira | Pridané: 19.1.2012 19:41 gramatika sme sa ucili na zakladnej skole, na strednej nie, normalne by som tu chybu nespravil, ale ked pisem rychlo a po po nejakom tom case na nete zacne asi akzdy vynechavat troska, a ano hambim sa za to Odpovedať Známka: 0.0 Hodnotiť:

Re: som zvedavy Od: pica | Pridané: 19.1.2012 19:46 je to riadna ohamba. Odpovedať Známka: 5.4 Hodnotiť:

Re: som zvedavy Od: 255.255.255.0 | Pridané: 20.1.2012 6:49 A este povedz ci sa naozaj hambis, alebo hanbis? Odpovedať Známka: 6.0 Hodnotiť:

Re: som zvedavy Od: čľčšľ | Pridané: 19.1.2012 12:53 A jak pozeram, tak aj garamatika sa skuor neuci, ako uci. Odpovedať Známka: 3.8 Hodnotiť:

Re: som zvedavy Od: xxxmisko | Pridané: 19.1.2012 13:20 ja som na gymnáziu so zameraním na cudzie jazyky matematiku štvrtého ročníka nemal. Teda žiadne integrály, derivácie, funkcie, rady. Odpovedať Známka: 4.0 Hodnotiť:

Re: som zvedavy Od: andkoo | Pridané: 19.1.2012 23:52 ja som na gymnaziu so zameranim na cudzie jazyky integraly a derivacie mal, ale Fourier na FEIke bol omnoho zabavnejsi:) Odpovedať Známka: 7.1 Hodnotiť:

Re: som zvedavy Od: zbytocne | Pridané: 19.1.2012 11:39 podla mna je uplne zbytocne ucit stredoskolakov dif a int, komp cisla. Zo strednej skoly idu vacsinou bud na urady prace alebo do zahranicia a tam pracuju aj bez toho... Odpovedať Známka: 1.0 Hodnotiť:

Re: som zvedavy Od: pseudo inteligent | Pridané: 19.1.2012 17:30 nemas pravdu, tato problematika by sa mala ucit uz na zakladke, pretoze sa kazdemu urcite hodi! Odpovedať Známka: 1.1 Hodnotiť:

Re: som zvedavy Od: b2un0 | Pridané: 20.1.2012 12:45 skús nejaký príklad zo života, kde by sa dali využiť derivácie, integrály... Odpovedať Známka: 1.1 Hodnotiť:

Re: som zvedavy Od: asdfhh | Pridané: 20.1.2012 22:22 Derivacie napr pri zistovani pri akej produkcii dosahujes maximalny zisk. Integral napr pri vypocte obsahu Odpovedať Známka: 10.0 Hodnotiť:

Re: som zvedavy Od reg.: Pjetro de | Pridané: 19.1.2012 10:54 niekto nebol ani student FEI, FIIT, MatFaz a tiez pochopil :) Odpovedať Známka: 8.3 Hodnotiť:

Re: som zvedavy Od: kubiik | Pridané: 19.1.2012 14:34 zjavne vsak nepochopil logiku toho prispevku ;) Odpovedať Známka: -2.6 Hodnotiť:

Re: som zvedavy Od: drahy drahomire | Pridané: 19.1.2012 11:10 Na informatike na matfyze sa fourierova transformacia spomina len okrajovo pokial viem. Ale pochopil som vsetko. Odpovedať Známka: 8.7 Hodnotiť:

Re: som zvedavy Od: lub | Pridané: 19.1.2012 13:03 a niekto to ani necital a presiel rovno na komentare :D Odpovedať Známka: 9.6 Hodnotiť:

Re: som zvedavy Od: Kveri_ | Pridané: 19.1.2012 11:41 +1 fiitkar ;) Odpovedať Známka: 6.0 Hodnotiť:

Re: som zvedavy Od: Satko | Pridané: 19.1.2012 12:02 +2 fiit fiit Odpovedať Známka: 7.6 Hodnotiť:

Re: som zvedavy Od: FEInoMORE | Pridané: 19.1.2012 13:35 Laci rulezz ;) Odpovedať Známka: 8.2 Hodnotiť:

Re: som zvedavy Od: FEI-KAR | Pridané: 19.1.2012 14:31 http://goo.gl/TQTfW Odpovedať Známka: 10.0 Hodnotiť:

Re: som zvedavy Od: FEInoMORE | Pridané: 19.1.2012 13:40 Furieraky mastia uz prvaci na FEI v letnom semestri so Satkom ;) Odpovedať Známka: 10.0 Hodnotiť:

Re: som zvedavy Od: jelito | Pridané: 19.1.2012 13:48 Par rokov dozadu sa brali v druhom rocniku ale asi zavisi od odboru. Odpovedať Známka: 10.0 Hodnotiť:

Re: som zvedavy Od: andkoo | Pridané: 19.1.2012 23:53 cely druhy rocnik to bolo furt dokola Odpovedať Známka: 10.0 Hodnotiť:

Re: som zvedavy Od: _ISIIS | Pridané: 20.1.2012 15:57 A FI MUNI si nespomenul. Odpovedať Známka: 10.0 Hodnotiť:

Re: som zvedavy Od: Andrejjj | Pridané: 21.1.2012 1:41 ešte aj FRIčkári rozumeli... Odpovedať Hodnotiť:

Re: som zvedavy Od: e!! | Pridané: 31.1.2012 13:26 a studenti FIT a FI :-P Odpovedať Hodnotiť:

Re: som zvedavy Od: asdddd | Pridané: 19.1.2012 9:54 ja nie, ale pametam si co tam je napisane. a ked to vytiahnem zajtra pri pive a budem to rozpravat s prizmurenym okom, tak budem cavo :)) Odpovedať Známka: 8.3 Hodnotiť:

Re: som zvedavy Od: pica | Pridané: 19.1.2012 9:59 ja som raz skusil v krcme maxwellove rovnice a malo to ohromny uspech. Odpovedať Známka: 9.6 Hodnotiť:

Re: som zvedavy Od: trololoman | Pridané: 19.1.2012 10:31 Bernouliho rovnice o prudeni kvapalin budu mat isto este vacsi uspech. Odpovedať Známka: 9.4 Hodnotiť:

Re: som zvedavy Od reg.: Pjetro de | Pridané: 19.1.2012 10:58 Ja by som zakazala vsetky tie integralne a diferencialne pocty, diferencialy, diferencie, vsakovate diferencialne rovnice a diferencne rovnice, limity postupnosti ci funkcii, ci vobec celu realnu analyzu, najlepsie aj komplexnu. Jiřina Soukupová, 37 let, pokladní, prodejna Billa, Praha 4 Odpovedať Známka: 7.0 Hodnotiť:

Re: som zvedavy Od: johan1215 | Pridané: 19.1.2012 11:37 :DDD nice one :) Odpovedať Známka: 7.5 Hodnotiť:

Re: som zvedavy Od: Roland-zee | Pridané: 19.1.2012 20:50 :D :p :D však nech si Jiřina Soukupová, 37 let, pokladní, prodejna Billa, nech si Jiřina už dokončí tú vš matfyz, a nemusí zakazovať (a sedeť za kasou za 10 tis Kcs, 10hod., dokladať :o :D :( :/ ) Odpovedať Známka: -3.3 Hodnotiť:

Re: som zvedavy Od: 100 rocny dedo | Pridané: 19.1.2012 10:34 vsak aj tricko s maxwellovymi rovnicami je vacsinou uspech :D Odpovedať Známka: 10.0 Hodnotiť:

Re: som zvedavy Od: fdfsfd | Pridané: 19.1.2012 16:33 mam spoluziaka ktory ich ma ako kerku Odpovedať Známka: 8.3 Hodnotiť:

Re: som zvedavy Od: tsss | Pridané: 19.1.2012 11:55 too long, didnt read Odpovedať Známka: -5.0 Hodnotiť:

Re: som zvedavy Od: hadraplan | Pridané: 19.1.2012 12:01 tl;dr chuju :) Odpovedať Známka: 4.3 Hodnotiť:

Re: som zvedavy Od: pjetrik_69 | Pridané: 19.1.2012 15:30 ja, ja! naviac som algoritmus prepisal do html5 a pridal search bar pre rychle hladanie mojho oblubeneho gej pornicka, jupiii Odpovedať Známka: -6.9 Hodnotiť:

..... Od: xvzf | Pridané: 19.1.2012 9:58 wow Odpovedať Známka: 10.0 Hodnotiť:

Re: ..... Od: Slavius | Pridané: 19.1.2012 10:11 +(1 * log n) Odpovedať Známka: 10.0 Hodnotiť:

Skúška Od: p@jon | Pridané: 19.1.2012 10:27 V pondelok máme z toho skúšku na FIIT Odpovedať Známka: 7.6 Hodnotiť:

Re: Skúška Od: trololoman | Pridané: 19.1.2012 10:33 Vidis, teraz jaky cavo budes ked tam prides s takouto novinkou. Odpovedať Známka: 9.5 Hodnotiť:

Re: Skúška Od: myname | Pridané: 19.1.2012 11:35 zdravim, kolega :) Odpovedať Známka: 6.7 Hodnotiť:

Re: Skúška Od: anon | Pridané: 19.1.2012 12:06 FIIT info druhak ? :D Odpovedať Známka: 6.0 Hodnotiť:

Re: Skúška Od: p@jon | Pridané: 19.1.2012 12:08 tak tak :D Odpovedať Známka: 5.0 Hodnotiť:

Re: Skúška Od: qwerty/z | Pridané: 19.1.2012 14:28 chodte sa ucit PIS... :D Odpovedať Známka: 7.8 Hodnotiť:

Ja tomu celkom nerozumiem Od: Element2 | Pridané: 19.1.2012 10:41 "pri malom počte významných frekvencií k a pri známom zvolenom k" Tak čo je teda "k" - počet významných frekvencií alebo nejaké volené číslo? Pri malom "k" sa zrejme nebude O (k * log n * log (n / k)) približovať k O (k * log n), ale naopak. Či? Odpovedať Známka: 6.7 Hodnotiť:

Re: Ja tomu celkom nerozumiem Od: gger | Pridané: 19.1.2012 10:52 Nutne spomenut, ze log je dvojkovy logaritmus. Ale to nebude nic menit na fakte, ze to je mensie. Ber to tak, ze vstup je veeelky obrazok a teda n je velke cislo a k je velkost komprimovaneho obrazku. Teda k<<n zvacsa a urcite k nie je vacsie ako n. Odpovedať Známka: 10.0 Hodnotiť:

Re: Ja tomu celkom nerozumiem Od: qqqqqqqqqqqqqqqq | Pridané: 19.1.2012 11:16 Je uplne jedno, aky je zaklad logaritmu. Akykolvek logaritmus vies zapisat ako podiel logaritmu s inym zakladom a konstanty (log z). To znamena, ze vo vyjadreni zlozitosti nema zmysel uvadzat zaklad logaritmu (o nicom to nevypoveda). Odpovedať Známka: 10.0 Hodnotiť:

Re: Ja tomu celkom nerozumiem Od reg.: Pjetro de | Pridané: 19.1.2012 14:12 Tak veru :) Odpovedať Známka: 10.0 Hodnotiť:

Re: Ja tomu celkom nerozumiem Od: McUH | Pridané: 20.1.2012 10:00 No neviem. Do detailu algoritmy tej komprimacie nepoznam, ale clanok naznacuje ze sa komprimuju matice 8x8 (nezavislo od seba) - mozno z toho je to zname stvorcekovanie. Potom ale n=64 a k=7 (cca). V tomto pripade ale log(64)=6, cize moc by sa nezmenilo. V praxi sa zrejme koduju i vacsie matice. Klucove asi bude ci na skomprimovanie staci pocet frkvencii k ktory je asymptoticky mensi ako log(n). A zrejme aj na konstante konkretneho algoritmu. Odpovedať Hodnotiť:

GORILA.. FUCK YOU HASCAK.. Od reg.: Peterkal | Pridané: 19.1.2012 11:14 http://gorila.tym.sk Odpovedať Známka: -1.8 Hodnotiť:

Re: GORILA.. FUCK YOU HASCAK.. Od: Jaroslav Haščák | Pridané: 19.1.2012 12:34 Moji právnici Vás kontaktujú v najbližších dňoch. Odpovedať Známka: 7.6 Hodnotiť:

Re: GORILA.. FUCK YOU HASCAK.. Od: Ivan Mikloš | Pridané: 19.1.2012 12:50 môj účtovník Vás kontaktuje tiež v najbližších dňoch. Odpovedať Známka: 8.2 Hodnotiť:

Re: GORILA.. FUCK YOU HASCAK.. Od: EDUARD MATÁK | Pridané: 19.1.2012 13:26 A ja vam o tom pridem porozpravat na sme, ako ma dsl.sk sklamalo. Odpovedať Známka: 5.7 Hodnotiť:

Re: GORILA.. FUCK YOU HASCAK.. Od reg.: marha | Pridané: 19.1.2012 14:22 a ja to cele potom preposlem do jankinho pda nech si to vytlaci vo velkom kancli Odpovedať Známka: 5.6 Hodnotiť:

FEI TUKE forever Od: Ujo_ja | Pridané: 19.1.2012 14:38 Ked sa to dozvie ing. Zavacky tak ani nezaspi. Odpovedať Známka: 10.0 Hodnotiť:

XDXDXD Od: RO_SO | Pridané: 19.1.2012 15:23 Včera som mal z toho skúšku... :D A pokial dostudujem bude mi to prd platné :D Odpovedať Známka: 6.7 Hodnotiť:

Re: XDXDXD Od: dumec | Pridané: 19.1.2012 17:51 presne môj názor Odpovedať Známka: 5.6 Hodnotiť:

Re: XDXDXD Od: dnes je Dalibor | Pridané: 20.1.2012 9:10 Ked myslis. Neviem naco potom studujes, ked su ti veci co sa naucis prd platne. Fourier sa realne pouziva a v multimediach skoro stale. Odpovedať Známka: 6.0 Hodnotiť:

Re: XDXDXD Od reg.: weiss | Pridané: 20.1.2012 23:33 Lenze malokedy to musis implementovat ty. Odpovedať Hodnotiť:

Re: XDXDXD Od: Dalibor dnes neni | Pridané: 21.1.2012 12:10 Ale ved jasne ale ide o to, ze vies co to je a na to pouzit a nemusis potom objavovat teplu vodu a dokazes pracovat samostatne bez toho, a by ti niekto hovoril co mas robit. Oni velmi dobre vedia, preco to prednasaju. Okrem toho vela veci, co sa ucis musis malokedy implementovat ty. Odpovedať Hodnotiť:

XDXDXD Od: RO_SO | Pridané: 19.1.2012 15:24 Ing Zavacky je paaan. džejziiiii... Odpovedať Známka: 6.4 Hodnotiť:

Re: XDXDXD Od: ružový fenomén | Pridané: 19.1.2012 16:50 nie nie, iba kokot z piešťan je pán! Odpovedať Známka: 0.8 Hodnotiť:

Re: XDXDXD Od: pica | Pridané: 19.1.2012 16:57 ano. ten z Pistan je pán kokot ej kej ej pupkaty sedlak ze zlatu klobasu na krku. Odpovedať Známka: 4.0 Hodnotiť:

Re: XDXDXD Od: imirka | Pridané: 19.1.2012 18:35 ej kej ej serem si do huby ej kej ej primitivne texty ej kej ej idol slabomyselnych ej kej ej 12+ music production.. ale inak ja caaavo Odpovedať Známka: -3.3 Hodnotiť:

furierr Od: FRI | Pridané: 22.1.2012 12:57 komprimacia toho videjka alebo hocicoho ineho patri pod analyzu procesov :P Odpovedať Hodnotiť:

Pridať komentár