ZFX
ZFX Neu
Home
Community
Neueste Posts
Chat
FAQ
IOTW
Tutorials
Bücher
zfxCON
ZFXCE
Mathlib
ASSIMP
NES
Wir über uns
Impressum
Regeln
Suchen
Mitgliederliste
Membername:
Passwort:
Besucher:
4442160
Jetzt (Chat):
13 (0)
Mitglieder:
5239
Themen:
24223
Nachrichten:
234554
Neuestes Mitglied:
-insane-

ZFX
Coding-Foren
Algorithmen und Datenstrukturen
Re: JPEG kompression
Normal
AutorThema
firehawk Offline
ZFX'ler


Registriert seit:
30.06.2002

Deutschland
292992177
JPEG kompressionNach oben.
Hi,

ich bin gerade dabei mir ein eigenes Grafikformat zu entwickeln. Es soll intern erst mal so aufgebaut sein, wie ein JPEG-Bild.
Dabei gehe ich folgendermaßen vor:

1. Bild von RGB auf VUV umwandeln
2. Indexverschiebung von Helligkeit, Sättigung, Farbton (YUV) um -128
3. Einteiung in 8*8 große Pixelblöcke
4. Diskrete Kosinustransformation (DCT)
5. Quantensierung
6. Huffmann-Codierung

Mein Problem: Die Diskrete Kosinustransformation dauert zur Berechnug sehr lange Zeit.

Hier ist mein code:

Code:
void dct_blocks( BLOCK_YUV in, BLOCK_YUV out) {
    
    int u, v, x, y;
    float u_cs, v_cs, pi = 3.1415927f;

    for( u=0 ; u<8 ; u++ ) {
        for( v=0 ; v<8 ; v++ ) {
            for( x=0 ; x<8 ; x++ ) {
                for( y=0 ; y<8 ; y++ ) {
                    u_cs = cosf(((2.0f*FLOAT(x)+1.0f)*FLOAT(u)*pi)/16.0f);
                    if( u==0 ) u_cs = (1.0f/FLOAT(sqrt(2.0f)));
                    v_cs = cosf(((2.0f*FLOAT(y)+1.0f)*FLOAT(v)*pi)/16.0f);
                    if( v==0 ) v_cs = (1.0f/FLOAT(sqrt(2.0f)));
                    out.pixels[u][v].y += 0.25f * in.pixels[x][y].y * u_cs * v_cs;
                    out.pixels[u][v].v += 0.25f * in.pixels[x][y].v * u_cs * v_cs;
                    out.pixels[u][v].u += 0.25f * in.pixels[x][y].u * u_cs * v_cs;

                }
            }
        }
    }
}


Für ein 1024*768 Pixel großes Bild, muss ich die Funktion 128*96 Mal aufrufen. Und das dauert.

Gibt es eine andere Möglichkeit, die schneller geht? In allen Grafikprogrammen dauert das Umwandeln von BMP in JPEG nur 'ne Sekunde, wie machen die das ??

Ich freue mich über jede Antwort

firehawk
11.06.2003, 16:38:37 Uhr
Marilyn Offline
ZFX'ler


Registriert seit:
06.05.2003

Schleswig-Holstein
Re: JPEG kompressionNach oben.
Ich weiß ja nicht, wie intelligent der Compiler schon optimiert, aber vielleicht u_cs * v_cs nur einmal berechnen und zwischenspeichern, statt drei mal neu zu berechnen.
Außerdem vielleicht 2.0f*FLOAT(x) durch eine Addition ersetzen.
Wie gesagt, ich weiß nicht in wie weit, der Compiler diese Optimierungen schon vornimmt. Ansonsten, wenn du dir 100% sicher bist, dass hier der Flaschenhals liegt, das ganze in Assembler umschreiben

11.06.2003, 17:54:36 Uhr
smurfer Offline
ZFX'ler


Registriert seit:
25.02.2002

Deutschland
Re: JPEG kompressionNach oben.
Hi,

ich bin jetzt Deine Funktion nicht genau durchgegangen, benutzt Du die FFT (Fast Fourier Transform)?
Denn man nimmt ja soweit ich weiss gerade aus dem Grunde die DCT, da man so die FFT verwenden kann.

ciao, smurfer..
11.06.2003, 22:41:09 Uhr
Swordfighter Offline
Administrator


Registriert seit:
25.02.2002

England
Re: JPEG kompressionNach oben.
schon mal bei http://www.jpeg.org/ vorbeigeschaut?
12.06.2003, 15:17:41 Uhr
Swordfighter's Realm
firehawk Offline
ZFX'ler


Registriert seit:
30.06.2002

Deutschland
292992177
Re: JPEG kompressionNach oben.
@swordfighter

Danke für den Link. Da war ich aber leider schon. Irgendwie finde ich dort keine richtigen Informationen.

@smurfer

Danke dür den Hinweis mit dem FFT. Hast du vielleicht einen Link, zu einer Website, die beschreibt, wie FFT funktioniert??
13.06.2003, 21:01:38 Uhr
THE_MATRIX Offline
ZFX'ler


Registriert seit:
18.07.2002

Deutschland
Re: JPEG kompressionNach oben.
hi,

die Cosinus Werte brauchst du nicht ständig neu zu berechnen! Leg ein Array an
und berechne die Werte vor, schließlich sind es nur 64 Stück. Eine weitere Optimierung
währe es z.B. die innere Schleife auszurollen.

ciao
14.06.2003, 22:49:34 Uhr
xcvb Offline
ZFX'ler


Registriert seit:
09.06.2002

Deutschland
Re: JPEG kompressionNach oben.
me hat gerade an ner MDCT/iMDCT (modifizierte dirkrete cosinus transformation) gebastelt und die is im vergleich zu referenzimplementierung, die so in etwa wie deine aussah um das 300fache schneller geworden. zum einen durch den einsatz einer schon oben erwähnten fft, zum anderen durch den göertzel algorithmus, mit dem sequentielle sinus- und cosinuswerte nach der initialisierung mit einer addition und multiplikation berechnet werden. zum umwandeln der dct in eine fft hab ich grad keinen link, da ich eben ne mdct programmiert hab (und auch nur 1d) aber für die sinuswerte empfehle ich http://www.dattalo.com/technical/theory/sinewave.html .

btw könnte auch die mdct für dich interessant sein, weil sie ein paar nette eigenschaften wie z.b. tdac (Time Domain Aliasing Cancellation). d.h. anstatt blockig zu werden tendiert die mdct eher zu einer unschärfe, was optisch wesentlich besser aussieht. vergleiche http://www.stanford.edu/~nouk/mdct/mdct/ . wenn schon ein neues bildformat, dann nicht den gleichen blockmist wie jpeg :)
15.06.2003, 12:09:55 Uhr
Linksammlung
Normal


ZFX Community Software, Version 0.9.1
Copyright 2002-2003 by Steffen Engel