Ny algoritme gir raskere komprimering

[Cuneax]

Opptil ti ganger så hurtig komprimering av data.

 

Ny algoritme gir raskere komprimering

[Pjassop]

Hva med patenter?

[Gjest Slettet-Pqy3rC]

An eight-by-eight block of pixels can be thought of as a 64-sample signal, and thus as the sum of 64 different frequencies. But as the researchers point out in their new paper, empirical studies show that on average, 57 of those frequencies can be discarded with minimal loss of image quality.

Jeg misliker prinsippet med å redusere kvalitet for å oppnå hurtighet. Kvantitet over kvalitet har aldri vært min greie.

Endret 25. januar 2012 av Slettet-Pqy3rC

[whitespace]

Jeg misliker prinsippet med å redusere kvalitet for å oppnå hurtighet. Kvantitet over kvalitet har aldri vært min greie.

 

Hvis du skal sammenligne med tapsfrie filer, ja. At det kan forbedre eksisterende komprimeringsteknologi er da bare bra.

Lik kvalitet = mindre plass, eller lik størrelse = bedre kvalitet. En god nyhet for folk med begrenset båndbredde for eksempel...

 

Det jeg lurer på er hvordan man "oppdager" en algoritme. Snublet de over den ved en tilfeldighet, er det et tilfelle av industrispionasje, eller har de funnet et kræsjet romskip med alien-teknologi?

[Gjest Slettet-Pqy3rC]

Hvis du skal sammenligne med tapsfrie filer, ja. At det kan forbedre eksisterende komprimeringsteknologi er da bare bra.

Lik kvalitet = mindre plass, eller lik størrelse = bedre kvalitet. En god nyhet for folk med begrenset båndbredde for eksempel...

Tja... Problemet er at komprimering med tap fort blir så utbredt at det lett blir oppfattet som en nødvendighet. Det er mange som går rundt å tror at MP3 er det eneste/beste musikkformatet.

Komprimering blir dermed ofte benyttet også der hvor det ikke er nødvendig.

Folk er fornøyd med MP3 f.eks fra Spotify (og da mange fordi de ikke vet bedre), mens jeg vil ha tapsfri komprimering (f.eks FLAC).

Det jeg lurer på er hvordan man "oppdager" en algoritme. Snublet de over den ved en tilfeldighet, er det et tilfelle av industrispionasje, eller har de funnet et kræsjet romskip med alien-teknologi?

Litt forskjellig, men oftest er det spin-off. Noen finner opp en eller annen formel og så bringes denne over i et annet bruksområde, kanskje med noen små endringer.

Omtrent som mye annet her i verden.

[daniel_984]

Jeg misliker prinsippet med å redusere kvalitet for å oppnå hurtighet. Kvantitet over kvalitet har aldri vært min greie.

 

Lol, for å erte deg litt, så har du sykt god råd, og kjøper aldri på IKEA, Rema1000, sokker på HM, noe annet elektronikk enn Bang&Olufsen etc??

[Simen1]

An eight-by-eight block of pixels can be thought of as a 64-sample signal, and thus as the sum of 64 different frequencies. But as the researchers point out in their new paper, empirical studies show that on average, 57 of those frequencies can be discarded with minimal loss of image quality.

Dette minner veldig mye om jpeg-komprimering. Der brukes omtrent samme teknikk, noe som er direkte synlig når man skrur kvaliteten langt nok ned. Da kan man se 8x8 blokker med bølgemønster.

 

Jeg misliker prinsippet med å redusere kvalitet for å oppnå hurtighet. Kvantitet over kvalitet har aldri vært min greie.

Mange ganger er det ikke teknisk mulig eller økonomisk forsvarlig å bruke ukomprimerte rådata. F.eks i filmer. Hadde man brukt full rå-output fra et Red-kamera rett på plata så hadde ikke 50 GB rukket mange minuttene. Det handler om å jekke ned ambisjonene til et passe nivå (i tilfellet film: 2 timer per plate) og få det meste ut av det ved hjelp av den komprimeringsteknologien som gir mest mulig kvalitet på den tilgjengelige lagringsplassen.

[indeksregulert]

Evt. så kan en filme med et kamera som har svært lav oppløsning, da kunne man sende ukomprimerte data rett til sluttbruker. Men da spørs det om ikke folk ville foretrukket den komprimerte varianten, filmet i HD.

[Occi]

Folk er fornøyd med MP3 f.eks fra Spotify (og da mange fordi de ikke vet bedre), mens jeg vil ha tapsfri komprimering (f.eks FLAC).

Spotify bruker ikke mp3, men Vorbis q5 eller q9 i henholdsvis 160 kb/s eller 320 kb/s. I tillegg til å gi bitrates vi er vant med så gir også Vorbis angivelig bedre lydkvalitet enn en hel rekke av konkurrentene, som f. eks mp3.

[Torbjørn]

An eight-by-eight block of pixels can be thought of as a 64-sample signal, and thus as the sum of 64 different frequencies. But as the researchers point out in their new paper, empirical studies show that on average, 57 of those frequencies can be discarded with minimal loss of image quality.

Jeg misliker prinsippet med å redusere kvalitet for å oppnå hurtighet. Kvantitet over kvalitet har aldri vært min greie.

 

Når du skal se på en nettside med din smarte telefon tror jeg du vil gjøre det til din greie at bildene er på 50kb istedet for 1500kb når det ikke er synlig forskjell på skjermen.

[Sandwich]

knis komprimering som er mer effektiv med et likt standpunkt? nope. sikkert noe muffins her!

[Thorsen]

Tar på meg oppgaven å oppklare en del ting som kan være uklart i deres fremstilling av saken.

 

Fouriertransform er en matematisk transform (en formel eller egentlig en måte å se data fra et annet observasjonspunkt) som transformerer data som er tidsavhengige (typisk musikksignal) over til frekvensdomenet. Eventuelt kan den også brukes til å transformere romlige data (som bilder) over til frekvensdomenet. Frekvens sier noe om hvor fort ting endres. Det finnes også inverse fouriertransformer som kan transformere et signal tilbake til tidsdomenet.

 

Fouriertransformer brukes fordi en rekke beregninger (signalbehandling) som å forbedre et musikksignal (fjerne støy) eller å legge ulike filtre på et bile (blurring) kan gjøres mye raskere i frekvensdomenet enn tidsdomenet. Det en typisk gjør er å transformere signalet til frekvenser, gjør beregninger, og så transformerer tilbake. For at dette skal gjøres må disse 3 operasjonene være raskere enn å gjøre beregningene direkte i tidsdomenet (rom for bilder).

 

Det finnes mange algoritmer (måter å gå fra et observasjonspunkt(tid/rom) til det andre (frekvens))for å beregne fouriertransformen til et signal. Frem til nå har FFT (Fast Fourier Transform) vært den desidert raskeste og mest brukte. Merk at denne algoritmen i seg selv ikke nødvendigvis er tapsfri, den kan brukes både med stor og liten oppløsning.

 

Det forskerene på MIT har gjort er IKKE å finne opp en ny transform. Det er altså feil det som står i hw.no sin artikkel at: "Likevel har MIT-forskere oppdaget en ny algoritme som skal være bedre enn Fourier." (Bedre er forsåvidt et helt idiotisk ord i denne sammenhengen, at noe er raskere betyr ikke at det er bedre). Det de har gjort er å finne opp en ny algoritme som er raskere enn FFT-algoritmen, men bare på noen typer signaler. En kan si at de har spesialtilpasset algoritmen til de signalene den skal brukes på. Merk spesielt ordlyden til slutt i MITs egen artikkel:

"The MIT researchers’ algorithm, however, “greatly expands the number of circumstances where one can beat the traditional FFT,"

 

Det flere her har kommentert med komprimering er riktig. Nå har ikke jeg sett nøye gjennom algoritmen, men det virker som om at de har kombinert flere operasjoner. En kan i dag få bedre hastighet hvis en gjør f.eks følgende i bildebehandling.

 

Originalbile - Komprimering - FFT - Behandling i frekvensdomenet - Invers FFT - Komprimert behandlet bilde

 

Det ser ut som om de kombinerer både komprimering og fouriertransform i ett ledd.

Endret 25. januar 2012 av Thorsen

[eXclusive1337]

"Algoritmen ble utviklet på 1960-tallet", er ganske ny da ja den er sikkert nylig tatt i bruk i noe nytt, men algoritmen er ikke ny.

[Thorsen]

"Algoritmen ble utviklet på 1960-tallet", er ganske ny da ja den er sikkert nylig tatt i bruk i noe nytt, men algoritmen er ikke ny.

 

Det var FFT algoritmen som ble "utviklet", eller mer riktig tatt i bruk på 1960-tallet.

FFT algoritmen var faktisk oppfunnet lenge før det. En fyr jeg ikke husker navnet på fant på algoritmen mens en ennå regnet for hånd. FFT algoritmen er ikke raskere når en regner for hånd så algoritmen falt i glemmeboken. Så når datamaskiner gjorde sitt inntog på 1960-tallet var det noen oppvakte folk som fant frem FFT algoritmen igjen.

[Raven_Heart]

"Algoritmen ble utviklet på 1960-tallet", er ganske ny da ja den er sikkert nylig tatt i bruk i noe nytt, men algoritmen er ikke ny.

 

Det var FFT algoritmen som ble "utviklet", eller mer riktig tatt i bruk på 1960-tallet.

FFT algoritmen var faktisk oppfunnet lenge før det. En fyr jeg ikke husker navnet på fant på algoritmen mens en ennå regnet for hånd. FFT algoritmen er ikke raskere når en regner for hånd så algoritmen falt i glemmeboken. Så når datamaskiner gjorde sitt inntog på 1960-tallet var det noen oppvakte folk som fant frem FFT algoritmen igjen.

 

Originalen til den mest brukte FFT-algoritmen, Cooley-Tukey FFT, ble visstnok utviklet av Carl Friedrich Gauss tidlig på 1800-tallet for beregning av asteroidebaner. Den gikk så i glemmeboka, før den ble gjenoppdaget av James W. Cooley og John W. Tukey i 1965.

[ATWindsor]

 

Det forskerene på MIT har gjort er IKKE å finne opp en ny transform.

 

Takk for ett godt innlegg, hadde tenkt å skrive noen ord om det samme selv.

 

AtW

[JeffK]

Noen har sagt det før, men her er noen flere nyanser:

 

Forskere ved Massachusetts Institute of Technology (MIT) i USA har forbedret en av de mest betydningsfulle algoritmene innen IT – den såkalte Fourier-transformasjonen.

Fouriertransformasjonen er en matematisk operasjon, ikke en algoritme (jfr. divisjon vs. "long division").

 

Fouriertransformasjonen er operasjon som utføres på kontinuerlige funksjoner/signaler. I datamaskiner opererer man kun på diskrete signaler. Den diskrete fouriertransformasjonen (DFT) tilsvarer fouriertransformasjonen i det diskrete domenet. Den matematiske operasjonen DFT har en (effektiv) algoritme som heter FFT.

 

Fourier-transformasjon blir blant annet brukt til å behandle signaler og komprimere bilder og lydfiler

Ikke så mye behandle som analysere. Man bytter bare representasjon. Mer spesifikt går man fra et koordinatsystem til annet (rettvinklet) koordinatsystem. Man kan se på transformen som en rotasjon i N-dimensjonalt rom. Avhengig av statistikken til signalet vil mange av koordinatene bli små, noe som gjør at de kan droppes uten stor forvrengning. Dette bildet illustrerer dette:

 

Fourier-transformasjonen er med andre ord et av de viktigste fundamentene IT-verdenen bygger på

Digital elektronikk/logikk er ikke avhengig av noen av disse transformene.

 

Med den nye algoritmen skal det være mulig å komprimere et digitalt signal ned til en brøkdel av den opprinnelige størrelsen

DFTen går fra èn N-dimensjonal representasjon til en annen N-dimensjonal representasjon, og gir ikke kompresjon i seg selv. Den er derimot reversibel/tapsfri.

Endret 25. januar 2012 av JeffK

[Matsemann]

Uff, hadde nok fourier i Matte4D nå i høst..

[kasey]

Folk er fornøyd med MP3 f.eks fra Spotify (og da mange fordi de ikke vet bedre), mens jeg vil ha tapsfri komprimering (f.eks FLAC).

Spotify bruker ikke mp3, men Vorbis q5 eller q9 i henholdsvis 160 kb/s eller 320 kb/s. I tillegg til å gi bitrates vi er vant med så gir også Vorbis angivelig bedre lydkvalitet enn en hel rekke av konkurrentene, som f. eks mp3.

 

WOW! Er det virkelig sant det du sier, Occi?? For når jeg sjekket siste offisielle reklame fra Spotify(Altså ikke gjennom Elkjip eller mobilt/bredbånd-leverandører) men ja Spotify mente at de brukte MP3-teknologi. Altså i fra dine ord, trur jeg at Spotify trur at de fleste som kommer til å bruke Spotify er såpass dumme og lite kresne på lyd/musikk idioter at de ikke kommer til å "KJØPE" Spotify vis Spotify annonser Vorbis Q5 /Q9 fremfor MP3. Ser den: Unlimited Vorbis for 9.99USD/Month. Da går de for WiMP, fordi WiMP leverer "Unlimited MP3's(!) for 8.5USD/Month".

 

Ja, jeg bruker kun CD/LP-16-24bit og FLAC/ALAC. Nei jeg er ikke rik, jeg har råd til å kjøpe "Gilde Kjøttkaker" med 60% ekte kjøtt isteden for "First Price Kjøttkaker" Med kun 15% kjøtt og resten skinn/brusk/bein. Det er noen som kjøper seg HTC med Beats og HP Envy med Beats til 20-30 tusen kr og Spotify, sånne individer trur at de er kule og viderekomne i teknologi, de går rundt i byen og "blotter", men jeg syns at de er ynkelige "Amatører i hodet og ører". Betaler ti tusener får mobilt nett og mobil telefon i året og fatter ikke hva de styrer med og hvor amatøriske de er? Er det typisk norsk idag å være en sånn teit person som er amatør i de fleste ting han styrer med og sløser penger, tid og live vekk? Mye penger, trenger ikke å tenke på ting og utforske dimensjon, men drukne i typisk "LIFE's AMATORY"?

[Torbjørn T.]

Folk er fornøyd med MP3 f.eks fra Spotify (og da mange fordi de ikke vet bedre), mens jeg vil ha tapsfri komprimering (f.eks FLAC).

Spotify bruker ikke mp3, men Vorbis q5 eller q9 i henholdsvis 160 kb/s eller 320 kb/s. I tillegg til å gi bitrates vi er vant med så gir også Vorbis angivelig bedre lydkvalitet enn en hel rekke av konkurrentene, som f. eks mp3.

WOW! Er det virkelig sant det du sier, Occi?? [...]

http://www.spotify.com/se/help/faq/tech/codec-quality/