Fourier-transformeren van data

[BaatZ]

Ik heb ooit eens iemand horen zeggen dat je data kan weergeven als golf.
Dat klinkt logisch; zet alle bits op een rijtje (als x) en hun waarde als y. Hiermee kan je een 2d vlak vullen.
Mochten er patronen in die data zitten (i.e., niet random, dus informatie bevattend) dan kan je dat patroon als een zekere functie zien. Zijn de patronen periodiek, dan kan je dat als een golffunctie beschouwen.
Het leuke is nu, dat je elke functie, en zeker golffuncties kan fourier-transformeren. Die transformatie levert dan op uit welke frequenties het signaal is opgebouwd; terugtransformeren leidt tot de data zelf, mits de transformatie perfect is.
Dat dit datareductie oplevert is vanzelfsprekend: Sin(x) heeft voor elk punt x een waarde y, terwijl de transformatie hiervan alleen de hoekfrequentie (1) oplevert; een oneinde set data gerepresenteerd door één parameter.

Wat mij benieuwde was het volgende:
Kunnen we deze methode werkelijk toepassen ? Stel we nemen een (monochrome) bitmap, maken 'm binary, doen een fouriertransformatie daarop en kijken of dat kleiner is dan de bitmap. Dat moet niet een moeilijk doel zijn. Ik wilde dat eigenlijk in Matlab gaan maken.
Zijn er mensen die zin hebben om hierover mee te denken of eens samen zo'n app te schrijven ?

[JJJ]

Je hebt eigenlijk al ongeveer beschreven hoe jpeg (en vast andere formaten) deels werkt
Als je een fouriertransformatie doet van een signaal dan krijg je inderdaad frequentiecomponenten. Compressie wordt bereikt door oa. de hoogfrequente componenten van het signaal weg te gooien.

Dat een sinusfunctie in "real space" 1 piek wordt in Fourierspace klopt. Vergeet echter niet dat de meeste signalen opgebouwd zijn uit een heel continuum aan frequenties en dat Fourierspace vaak niet zo simpel is als het hierboven wordt voorgesteld

[BaatZ]

JJJ schreef op woensdag 10 juni 2009 @ 22:40:
Je hebt eigenlijk al ongeveer beschreven hoe jpeg (en vast andere formaten) deels werkt
Als je een fouriertransformatie doet van een signaal dan krijg je inderdaad frequentiecomponenten. Compressie wordt bereikt door oa. de hoogfrequente componenten van het signaal weg te gooien.

Dat een sinusfunctie in "real space" 1 piek wordt in Fourierspace klopt. Vergeet echter niet dat de meeste signalen opgebouwd zijn uit een heel continuum aan frequenties en dat Fourierspace vaak niet zo simpel is als het hierboven wordt voorgesteld

oh Ik dacht dat jpeg meer interpretatief ging, zo van: das wel ongeveer dezelfde kleur dus hoppa, wordt 1 kleur. Maar nu je 't zegt, contrast is iets hoogfrequents en kan je dus zo wegfilteren. Toch zou ik wel een compressie zoals ik die beschreef willen zien werken. Bestaat daar dan al code van ? ben best benieuwd !

[Lord Daemon]

Dat dit datareductie oplevert is vanzelfsprekend: Sin(x) heeft voor elk punt x een waarde y, terwijl de transformatie hiervan alleen de hoekfrequentie (1) oplevert; een oneinde set data gerepresenteerd door één parameter.

Dit klopt natuurlijk niet! Er bestaat geen algoritme dat altijd compressie oplevert. Een Fourier-transformatie bijvoorbeeld levert wel compressie op als de oorspronkelijke dataset inderdaad te schrijven is als de som van relatief weinig sinussen + een laag-frequente ruis. Maar als dit niet het geval is zal er geen compressie optreden.

Dat geen enkel algoritme altijd compressie oplevert, is gemakkelijk in te zien. Laten we de verzameling van alle mogelijke data-strings (dus van alle rijen 0-en en 1-en, welke lengte dan ook) S noemen. Een compressie-algoritme is een algoritme waar je een element van S in doet, er waar ook weer een element van S uitkomt. Wat hierbij essentieel is, is dat nooit twee verschillende inputs op dezelfde output worden afgebeeld: dan krijg je immers je input niet meer terug als je gaat decomprimeren. (Ik heb het hier dus over lossless compressie; als je loss wel accepteert is compressie natuurlijk heel gemakkelijk.)

Het is nu gemakkelijk in te zien dat voor elke data-string die gecomprimeerd wordt door je algoritme, er ook een data-string moet zijn die juist groter wordt door je algoritme. Zie het bijvoorbeeld als volgt. Begin met het algoritme dat elke string op zichzelf afbeeldt. Je kan nu elk ander compressie-algoritme bouwen door twee afbeeldingen te verwisselen: als je eerst I1 op O1 en I2 op O2 afbeeldt, dan ga je nu I1 op O2 afbeelden en I2 op O1. Met een aantal (potentieel oneindig) van die stappen kan je elk compressie-algoritme krijgen dat je maar wil. Maar wat we zien is dat als deze wisseling de compressie voor I1 verbetert, dan moet hij tegelijkertijd de compressie voor I2 verslechteren.

Wat je in jouw geval zult zien is dat een monochrome bitmap die is opgebouwd uit sinussen heel goed comprimeert; maar dat een willekeurige bitmap gemiddeld juist groter zal worden door je Fourier-compressie. Het is simpelweg onmogelijk om daar onderuit te komen.

[BaatZ]

Lord Daemon schreef op donderdag 11 juni 2009 @ 00:32:
[...]

Dit klopt natuurlijk niet! Er bestaat geen algoritme dat altijd compressie oplevert. Een Fourier-transformatie bijvoorbeeld levert wel compressie op als de oorspronkelijke dataset inderdaad te schrijven is als de som van relatief weinig sinussen + een laag-frequente ruis. Maar als dit niet het geval is zal er geen compressie optreden.

True, das hiermee wel ondervangen toch:

Mochten er patronen in die data zitten (i.e., niet random, dus informatie bevattend) dan kan je dat patroon als een zekere functie zien

't Was maar een korte intro. Ik ben gewoon benieuwd naar hoe en of dit toegepast wordt op data die niet niet audio is of zo. Dat 't voor deltafuncties en ruis misgaat is zeker zo, maar kan 't bijvoorbeeld in grote statistische bulkdata ? Of kan je 't gebruiken voor analyse ? Het viel me gewoon op dat ik er nog nooit verder over gehoord had, ook niet bij de colleges data-analyse of datastructuren bij de vu

[vanaalten]

Een fouriertransformatie is alleen een middel om een lading data op een andere manier te bekijken.

Vergelijk het met bijvoorbeeld kleur in een tekenprogramma: je kan kiezen om pixels te maken met rood/groen/blauw combinaties, helderheid en twee kleurtypes (U en V) en er zijn vast nog wel andere opties. Qua hoeveelheid data verandert er niets, maar doordat je het op een andere manier bekijkt kan je er wel interessante optimalisaties op los laten (helderheid is een belangrijke component, maar kleur kan je vaak wel wat minder gedetailleerd opslaan, bijvoorbeeld). Simpelweg zorgt het ervoor dat je andere karakteristieken van je data bekijkt. Een plaatje dat alleen maar rood-componenten bevat, dat zie je heel goed als je 'm als RGB-data analyseert, maar niet als YUV. Aan de andere kant: een plaatje dat alles op 1 helderheidsniveau beschrijft zie je perfect in YUV, maar niet in RGB.

Zo is het ook met een fouriertransformatie: het laat je data zien als een verzameling frequenties, in plaats van volumes op tijdmomenten. Als een stuk muziek weinig lage tonen bevat, dan zie je dat niet als je de WAV-file in een geluidbewerkingspakket bekijkt - maar juist perfect als je het in frequenties laat beschrijven door een fouriertransformatie.

Algemeen gesteld: de hoeveelheid data na fouriertransformatie is net zoveel als voor transformatie. Het is de bewerking die je erna doet, met nieuwe inzichten over de karakteristiek van die data, waar je je compressiewinst mee kunt behalen.

[caipirinha]

JPG (o.a.) maakt gebruik van disctrete cosinus transformatie (DCT) wat in feite een FFT voor real numbers is.
Compressie met een FFT of DCT is altijd lossy, je moet alleen vooraf besluiten wat je weg wilt gooien.
Bij JPG worden bijvoorbeeld de harde overgangen tussen contrasten en kleuren vervaagd op basis van de pixels/data die eromheen te vinden zijn.
Dat verklaart ook dat een zwart wit tekening niet te comprimeren is met JPG en er alleen een lading artefacten ontstaan nabij de zwart wit overgangen.

Eigenlijk is de FFT of DCT alleen een analysetool die je gebruikt om later te bepalen wat wel of niet weg te gooien is en geen compressiealgorithme an sich.

edit: ik moet sneller typen, zie vorige post

[ Voor 3% gewijzigd door caipirinha op 11-06-2009 09:17 ]

[Matis]

Ik wil niemand bashen, maar dat YUV verhaal is niet waar. Een YUV formaat bevat voor elke pixel 1 Y component en voor elke twee pixels 1 U en 1 V component. Daarmee kom je dus op 2 x het aantal bytes per pixel en niet 3 x het aantal voor RGB. (er vanuitgaande dat er 1 byte per component gebruikt wordt).
Je hebt dus YUV 422P en RGB24. Het YUV bestand is maar 2/3 van het RGB bestand. Dus in theorie zul je daar al *winnen*
Daarnaast kun je YUV makkelijker comprimeren omdat de Y component niets zegt over de kleur en ook niet zo heel hard verloopt.

[Confusion]

vanaalten schreef op donderdag 11 juni 2009 @ 08:59:
Een fouriertransformatie is alleen een middel om een lading data op een andere manier te bekijken.
[..]
Algemeen gesteld: de hoeveelheid data na fouriertransformatie is net zoveel als voor transformatie.

De hoeveelheid informatie is even groot. De hoeveelheid data die je nodig hebt om die hoeveelheid informatie uit te drukken kan veel kleiner zijn. Anders zou iets als zip compressie ook niet kunnen bestaan.

[BaatZ]

vanaalten schreef op donderdag 11 juni 2009 @ 08:59:
Algemeen gesteld: de hoeveelheid data na fouriertransformatie is net zoveel als voor transformatie. Het is de bewerking die je erna doet, met nieuwe inzichten over de karakteristiek van die data, waar je je compressiewinst mee kunt behalen.

Dat ligt er volgens mij maar net aan hoeveel termen je meeneemt in de transformatie. Als je sommeert tot oneindig heb je de data perfect terug en is 't goed mogelijk (blokgolven) dat de getransformeerde data groter is dan de originele data. Niemand sommeert echter tot oneindig voor praktische toepassingen. Dus 't is meer wat Confusion inderdaad zei: de hoeveelheid informatie is even groot met minder data.
Dat dit niet voor alles werkt lijkt me wel duidelijk, we gaan ook geen post-it briefjes knippen met een motorzaag.

[vanaalten]

Matis schreef op donderdag 11 juni 2009 @ 09:20:
Ik wil niemand bashen, maar dat YUV verhaal is niet waar. Een YUV formaat bevat voor elke pixel 1 Y component en voor elke twee pixels 1 U en 1 V component. Daarmee kom je dus op 2 x het aantal bytes per pixel en niet 3 x het aantal voor RGB. (er vanuitgaande dat er 1 byte per component gebruikt wordt).

Dat is 1 mogelijk YUV formaat, ja.

Je hebt dus YUV 422P en RGB24.

... en YUV444. Daarbij is per pixel een Y, U en V waarde. Gewoon simpelweg omrekenen van RGB naar YUV met standaard formules - zie ook de Wikipedia info.

Daarnaast kun je YUV makkelijker comprimeren omdat de Y component niets zegt over de kleur en ook niet zo heel hard verloopt.

... waarmee je precies bevestigd wat ik schreef: het is een andere manier om dezelfde informatie te bekijken en er op die manier achterkomen hoe je het beter kan comprimeren.

[MSalters]

Om nog even in te gaan op BaatZ vraag over daadwerkelijk gebruik: Ook muziekcompressie zoals MP3 is gebaseerd op een (digitale) fouriertransformatie. Het blijkt namelijk dat je de fourier-getransformeerde muziek beter kunt analyseren. Welke tonen zijn onhoorbaar? De hoge, de lage, de zachte en de tonen die vlak tegen een hardere toon aanzitten. Door deze onhoorbare tonen eruit te gooien kunnen we een grote compressie bereiken.

[BaatZ]

Ok eigenlijk heb ik dit topic geopend zonder duidelijke doelstelling voor mezelf
't Zijn wel nuttige replies en zeker ook aanscherpingen, maar ik was van die dingen wel op de hoogte
Wat ik eigenlijk wilde is een stukje code zien in matlab of mathematica die dat gewoon doet met een array, desnoods C ofzo, maar da's nog niet zo makkelijk te vinden met google
Dus wat dat betreft nog iets ?

[Confusion]

Wat je denk ik zoekt is het Fast Fourier Transform algoritme. Hier staat een Matlab voorbeeld: http://www.mathworks.com/...help/techdoc/ref/fft.html

[Verwijderd]

BaatZ schreef op vrijdag 12 juni 2009 @ 03:05:
Ok eigenlijk heb ik dit topic geopend zonder duidelijke doelstelling voor mezelf
't Zijn wel nuttige replies en zeker ook aanscherpingen, maar ik was van die dingen wel op de hoogte
Wat ik eigenlijk wilde is een stukje code zien in matlab of mathematica die dat gewoon doet met een array, desnoods C ofzo, maar da's nog niet zo makkelijk te vinden met google
Dus wat dat betreft nog iets ?

Mathematica heeft gewoon een ingebouwde functie voor discrete fourier transformaties namelijk "Fourier" en voor DCT heeft ie "FourierDCT".

[Grijze Vos]

Je kunt kijken naar FFTW, de MIT Fourier transformer.

[Keneo]

http://code.google.com/p/dctlab/

dctlab is een tootle dat je een beetje laat experimenteren met bepaalde parameters in een dct (discrete cosine transformation)

Het is open source, dus kijk even in de source code