[Alg] Waarom 2D wavelet transformaties? *

[Zoijar]

Korte vraag...Ik vroeg me af waarom er altijd een 2D wavelet transform wordt gebruikt, ipv een space filling curve en een 1D transform. Het laatste is sneller en makkelijker te implementeren...en het lijkt me dat de matrix ook ongeveer even sparse wordt.

[XKB]

Kan je voor de niet-experts dit kunnen toelichten? Wat houden deze 2 transforms in ed?

[Zoijar]

Een wavelet transform is net zoiets als een fourier xform, alleen "beter". Bv JPEG2000 gebruikt ze, en eigenlijk alle andere compressie tegenwoordig. Je ziet je image als een 2d functie (NxN -> N) die transformeer je en daar komt dan een grid van 'wavelet' coeficienten uit. Het voordeel is dat veel van die coef. dicht bij nul liggen, en je die weg kunt laten zonder veel kwaliteits verlies.

Een spacefilling curve is een lijn door een grid zoals dit bv:

Je kriijgt dan dus een 1d functie, die localiteit behoudt (pixels dicht bij elkaar liggen dicht bij elkaar op de lijn) en op die lijn kan je een 1d wavelet transform doen.

Na de transform doe iha iets van runlength encoding gevolgd door arithmetic coding. Soort van zip compressie dus.

[ Voor 4% gewijzigd door Zoijar op 12-06-2004 14:34 ]

[Soultaker]

Zoijar schreef op 12 juni 2004 @ 14:15:
Het laatste is sneller en makkelijker te implementeren...en het lijkt me dat de matrix ook ongeveer even sparse wordt.

Makkelijk te implementeren zal nauwelijks een criterium zijn, zeker niet bij algoritmen die gepatenteerd moeten worden. De verschillen tussen beeldcompressiealgoritmen zijn al dermate klein dat er niet zo snel gekozen zal worden voor een te simpele aanpak die een slechtere compressieratio ten gevolg heeft.

De vraag is dus of jouw methode even goed werkt. Jij gaat er zomaar vanuit dat dat wel eens zo zou kunnen zijn; heb je daar ook al statistische gegevens over verzameld?

[Zoijar]

Soultaker schreef op 12 juni 2004 @ 14:49:
Makkelijk te implementeren zal nauwelijks een criterium zijn, zeker niet bij algoritmen die gepatenteerd moeten worden. De verschillen tussen beeldcompressiealgoritmen zijn al dermate klein dat er niet zo snel gekozen zal worden voor een te simpele aanpak die een slechtere compressieratio ten gevolg heeft.

Ok daar zit wel wat in. Hoewel er toch ook vaak wel naar simpele implementaties wordt gezocht, bv met het oog op hardware implementatie, of parallelisme. Verder ging het my om realtime random access decompression, dus snelheid is heel belangrijk.

De vraag is dus of jouw methode even goed werkt. Jij gaat er zomaar vanuit dat dat wel eens zo zou kunnen zijn; heb je daar ook al statistische gegevens over verzameld?

Nee, nog niet, misschien later. Ik wilde eerst sowieso weten of iemand er misschien al een antwoord op kon geven. Ik kan me namelijk indenken dat je bij de 2d xform impliciet correlatie informatie tussen x en y meeneemt. Bij een 1d xform is de functie wel behoorlijk smooth, maar in principe is de 2d functie net zo smooth.

[curry684]

Topictitel even 'iets' duidelijker gemaakt

[voodooless]

Klein vraagje: Wat is het grote verschil tussen die "Space Filling" dingen, en gewoon regel voor regel zigzaggen?

code:

______________
_____________|
|_____________
_____________|

Ik denk juist dat het probleem is dat je echt twee dimensies hebt, horizontale frequenties (of wavelets), en vertikale frequenties (of wavelets). Met zo'n space filling algo vallen deze twee dimensies dus weg. Ik ben er echter nog niet echt uit of dat wel zo rampzalig is voor de uitkomst, maar ik denk dat je wel in die hoek zult moet gaan zoeken.

[SWfreak]

Als ik het me goed herinner, doet JPEG 2000 in principe ook alleen maar 1d transforms, nl eerst op rijen en dan op kolommen.

[voodooless]

SWfreak schreef op 12 juni 2004 @ 20:55:
Als ik het me goed herinner, doet JPEG 2000 in principe ook alleen maar 1d transforms, nl eerst op rijen en dan op kolommen.

Yah, zo werkt een 2D transform nu eenmaal. Horizontale en verikale frequenties (of wavelets) Twee maal een 1D transform idd, op iedere rij. Wat de TS nu wil doen is een maal een 1D transform doen van het gehele beeld.

[ Voor 17% gewijzigd door voodooless op 12-06-2004 21:04 ]

[Zoijar]

deepspace schreef op 12 juni 2004 @ 20:13:
Klein vraagje: Wat is het grote verschil tussen die "Space Filling" dingen, en gewoon regel voor regel zigzaggen?

code:

______________
_____________|
|_____________
_____________|

Het gemiddelde afstands verschil tussen ((a,b),(c,d)) en (P(a,b),P(c,d)) waar P de curve projectie is. Bijvoorbeeld het punt x=0,y=0 en x=0,y=1 liggen maar op afstand 1 in het origineel. Kleine afstanden in het origineel schelen waarschijnlijk weinig in waarde en compressen dus goed. Maar bij jouw curve is de geprojecteerde afstand tussen die twee punten gelijk aan twee maal de rij lengte.

De theorie over spacefilling curves is vrij uitgebreid...iha doen hilbert, z, of pi curves het wel ok, maar je kan curves met verschillende eigenschappen vinden. Paketten die op extreem grote matrices werken (inversie, decompositie, etc) slaan deze matrices in curve order op disk op. Op die manier heb je een veel betere block cache performance. Als je een element op een nieuwe rij leest hoef je waarschijnlijk niet een heel nieuwe block op te halen

SWfreak schreef op 12 juni 2004 @ 20:55:
Als ik het me goed herinner, doet JPEG 2000 in principe ook alleen maar 1d transforms, nl eerst op rijen en dan op kolommen.

Niet helemaal. Bij een image van nxn worden eerst van de rijen de average en de detail opgeslagen (beide (n/2)xn) en dan worden beiden weer getransformeerd in een average en een detail. Zo krijg je 1 average, 1 horizontal detail, 1 vertical detail en 1 diagonal detail, allemaal van (n/2)x(n/2)

[ Voor 20% gewijzigd door Zoijar op 12-06-2004 21:18 ]

[Infinitive]

deepspace schreef op 12 juni 2004 @ 20:13:
Klein vraagje: Wat is het grote verschil tussen die "Space Filling" dingen, en gewoon regel voor regel zigzaggen?

zigzaggen is een speciaal geval van "Space Filling". Met een slimme keuze voor space filling kan je correlaties tussen horizontale dan wel verticale aangrenzende pixels gebruiken voor betere compressie. Maar dat zou dus ook betekenen dat je die "Space Filling" volgorde ook op moet slaan. Tenzij je deze van te voren vast kiest, maar dan maak je in het algemene geval geen gebruik van 2D correlaties.

Bovendien heb ik het idee dat je bij "Space Filling" eigenlijk af en toe een sprongetje zou willen maken, maar dat kan niet omdat het volgende punt moet grenzen aan het vorige.

offtopic:
disclaimer: ik ben niet helemaal bekend met de theorie in dit wereldje, dus hier kan een heleboel onzin staan.

[ Voor 27% gewijzigd door Infinitive op 12-06-2004 21:25 ]

[Zoijar]

Infinitive schreef op 12 juni 2004 @ 21:21:
zigzaggen is een speciaal geval van "Space Filling". Met een slimme keuze voor space filling kan je correlaties tussen horizontale dan wel verticale aangrenzende pixels gebruiken voor betere compressie. Maar dat zou dus ook betekenen dat je die "Space Filling" volgorde ook op moet slaan. Tenzij je deze van te voren vast kiest, maar dan maak je in het algemene geval geen gebruik van 2D correlaties.

Ja je kan idd ook dynamische space filling doen, zie bv http://www.math.tau.ac.il/~matias/papers/eg2000.pdf