|
  |
 DCT und Custom-Matrix, kurze(?) Übersicht |
EthanoliX
Kaiser
Dabei seit: 11.04.2002
Beiträge: 1.310
Herkunft: Mainz
 |
|
| DCT und Custom-Matrix, kurze(?) Übersicht |
     |
Vorwegschicken sollte ich, daß ich eigentlich 2 Bilder einbinden wollte, aber da ich jetzt leider keine Zeit mehr habe mir im Netz was zu holen, wo ich die Bilder lagern kann, gebe ich mal die Links an.
Einer der Vorteile von Xvid, der auch mich dazu gebracht hat mich stärker mit diesem Codec zu befassen, ist, daß man direkt die Quantizer Matrix bearbeiten kann. Jedoch war dies zu Anfang recht schwierig, ohne genau zu wissen, welche Bedeutung die Matrix hat.
Nachdem ich das Netz nach Discreter Cosinus durchsucht habe und ein wenig meine alten Matheunterlagen gewälzt habe, bin ich zwar kein Experte auf diesem Gebiet, billige mir aber zu soviel verstanden zu haben, als daß ich für all diejenigen, die auch gerne mit einer eigenen Matrix experimentieren wollen, eine kurze und grobe Übersicht über das Thema zu geben.
Wie kommt die Matrix zustande? DCT - Helligkeits-/Farbspektrum => Frequenzspektrum
Ein Schritt bei der Videokomprimierung (wie auch bei der reinen Bildkompression auch) ist die Zerlegung des Bildes in quadratische Blöcke. Für jedes Pixel des Blockes müssten auf einer Skala (z.B. 8bit) die Helligkeits- und Farbinformationen gespeichert werden. Da die dabei anfallende Datenmenge in dieser Form auch verlustbehaftet nicht effektiv reduziert werden kann, überführt man die Bildinformation mittels Diskreter Cosinus Transformation (DCT) in ein Frequenzspektrum.
Was das nun???
Trägt man z.B. die Helligkeitswerte der ersten Zeile eines 8*8-Blockes gegen die Pixel auf, erhält man im mathematischen Sinne eine Funktion. [x-Ache: Pixel 1, 2, 3,... ,8; y-Achse die Grauwerte z.B. auf einer 256 Stufen-Skala (8bit)]. Diese stufenartige Funktion wird bei der DCT durch eine Summe modifizierter Cosinusfunktionen ersetzt.
Um einen ganzen 8*8-Block darzustellen werden hierbei natürlich dreidimensionale Funktionen benutzt [x- & y-Achse: Pixelkoordinaten; z-Achse: Grau-/Farbwertwert]. Da diese Funktion nicht kontinuierlich verläuft, sondern stufenartig, kann man sie auch als 8*8 Matrix (Helligkeits-/Farbmatrix) darstellen. In dieser Matrix steht jeder Koeffizient noch für den Helligkeitswert eines (des entsprechenden) einzelnen Pixels. Nach der DCT erhält man nun wieder eine 8*8 Matrix (Frequenz-Matrix, FM). Jede Position der Matrix steht jetzt für eine der insges. 64 verwendeten, modifizierten cos-Funktionen.
Wichtig ist, daß jede dieser cos-Funktionen Daten für jedes der 64 Pixel des Blockes enthält.
Jeder Koeff. steht für eine Funktion, die für sich alleine schon einen 8*8 Pixel-Block darstellt. Um den Ursprünglichen Block zu erhalten, werden sozusagen alle 64 cos-Funktionen mit dem Faktor in der Matrix multipliziert und aufaddiert. Die einzelnen Koeffizienten geben also an, wie stark die jeweilige Funktion bei der Darstellung des Blockes zu berücksichtigen ist. Wie man sich diese Funktionen veranschaulichen kann zeigt folgendes Bild:
http://doom9.psydon.org/viewtopic.php?t=3137&start=30 Post v. LigH (22.12.2002, Bild am besten speichern und stark vergrößern.)
Der Koeff. links oben (1 1) beschreibt die Helligkeit des Blockes an sich, der darunter(2 1) den einfachen Helligkeitsverlauf von der ersten bis zur 8. Pixelzeile und der Koeff. (1 2) den Helligkeitsverlauf von der ersten bis zur 8. Pixelspalte usw. Man sieht, daß die Muster immer Detailreicher werden, je weiter man nach unten rechts gelangt.Und was mach die Quantizer-Matrix (QM) des Codec?Nachdem man (also eigentlich ja der abakus digitalis) die DCT durchgeführt hat, hat man wieder eine Matrix mit 64 Koeffizienten und eigentlich noch kein einziges Bit gspart. Und genau hier kommt die Quantizer Matrix des Codec ins Spiel.
Der Codec dividiert nun jeden Wert der Frequenz-Matrix durch den entsprechenden Wert in der Quantizer-Matrix und rundet dann auf den nächstgelegenen Integer. Diesen Vorgang bezeichnet man auch als Quantisierung. Allerdings wird vorher noch die Quantizer-Matrix mit dem Wert, der jedem als Quantizer an sich bekannt ist, multipliziert. Anschließend werden die Koeffizienten als Integer-Werte variabler Bitlänge (VLI, variable length integer) in einer Zickzack-Reihenfolge gespeichert. (http://user.cs.tu-berlin.de/~magus/dct/algo.html#DCT ) Die Datenreduktion kommt nun dadurch zustande, daß 1. als VLI jeden Koeff. nur so viele Bit bekommt, wie er zwingend benötigt (auf einer 8bit-Skala benötigt jede Zahl 8 Bit: 2 => 00000010, als VLI: 10, 2 Bit); 2. viele der Koeffizienten, je weiter man nach unten rechts gelangt, den Wert null annehmen. Für den Fall, daß ab einem bestimmten Koeffizienten bei der Zickzack-aneinanderreihung nur noch Nullen folgen, wird nicht mehr jeder einzelne Koeff. als VLI-Bitfolge gespeichert, sondern mit einer geeigneten Bitfolge lapidar angegeben, daß der Rest der Koeff. eben null ist. Hieraus wird auch ersichtlich, daß die aktuelle Bitrate über den Quantizer variiert wird: Höherer Quantizer => kleinere Werte bzw. mehr Koeff.=0 => weniger Speicherbedarf => niedrigere Bitrate.
Ich will mein Bild wieder haben!
Soll nun der Block beim Dekodieren wiederhergestellt werden, werden alle Schritte in umgekehrter Reihenfolge ausgeführt. Da hierzu wiederum die QM vonnöten ist, muß diese also mind. einmal mit abgespeichert werden. Und jetzt machen sich die Rundungsfehler der Quantisierung bemerkbar. Bei einem Wert von 156 vor der Quantisierung, QM-Koeff. 32 und Quantizer 2, würde dieser Wert im fertigen Bitstrom als 156/(2*32)=2,21, also gerundet 2 gespeichert. Beim Rekonstruieren der Frequenz-Matrix während des Dekodierens, ergibt sich daher für den entsprechenden Koeff.: 2*2*32=128, was einen Fehler von ca. 20% ausmacht. Bei einem Quantizer von 1 hätte man als Quantisierten Wert 4.88 also 5 erhalten. Der rekonstruierte Wert wäre somit 5*1*32=160, was schon wesentlich dichter an der Wahrheit liegt. Die Frequenzen, deren Koeff. als null gespeichert wurde, werden bei der inversen Discreten Cosinustransformation (iDCT), bei der aus der FM wieder die Bilddaten gewonnen werden, also gar nicht erst berücksichtigt.
Und was heißt das jetzt für meine Matrix?
Mit diesem Wissen und ein paar Tests, die ich gemacht habe, lassen sich folgende Leitlinien für die entwicklung einer eigenen Matrix erstellen:
1. kleine Werte => weniger Detailverlust, hoher Speicherbedarf
2. beste Komprimierbarkeit, wenn Werte gemäß der Speicherreihenfolge ansteigen
3. übertrieben hohen Werte in den ersten beiden Spalten und Zeilen führen zu verfühter Blockartefaktbildung
Dies ist sicherlich nicht alles, was es zu beachten gilt, aber zumindest das, was sich leicht in Worten ausdrücken läßt. Ansonsten läßt sich natürlich noch sagen, daß man am besten erst einmal testet, testet und noch mal testet. Und dafür eignen sich am besten Sequenzen, mit scharfen Kanten und schwarze Flächen. Geholfen hat mir beim testen auch Matrizen zu verwenden, deren Werte bewußt übertrieben waren, einfach um den Einfluß und den Effekt abschätzen zu können, damit ich weiß, auf welche Artefakte ich achten muß.
So das war's für's erste.
Zu guter letzt möchte ich noch mal daran erinnern, daß dies nur eine grobe Übersich über das Thema sein soll. Es kann gut sein, daß ich einiges (weil ich es z.B. falsch verstanden habe) falsch geschildert habe. An dieser Stelle bin ich für Korrekturen sehr dankbar. Ebenso kann und will ich nicht ausschließen, daß sich manch einem, der tiefere Einblicke in die Materie oder die dahinterstehende Mathematik hat, die Fußnägel rollen, wenn er diese mathematisch sicherlich nicht hasenrein formulierten Zeilen liest. Auch sind einige Dinge noch unklar, wie z.B. die Behandlung von Helligkeits- und Farbwerten, die mir auch nicht wirklich klar ist (weswegen ich mich darüber nicht ausgelassen habe) und die größe der Blöcke (8*8 oder 16*16). Dieser Post erhebt keinen Anspruch auf Vollständigkeit!!! Aber ich hoffe, daß diejenigen, die sich dafür interessieren, etwas damit anfangen können.Wer noch ein wenig mehr lesen möchte, dem empfehle ich diese Seite (da ist auch das eine Bild zu finden): http://user.cs.tu-berlin.de/~magus/dct/algo.html#DCT
__________________
"Der größte Trick, den der Teufel je gebracht hat, war die Menschheit glauben zu lassen, es gäbe ihn gar nicht."
Roger "Verbal" Kint, Die üblichen Verdächtigen
|
|
17.02.2003 12:57 |
|
|
Selur
spamming old Newbie
Dabei seit: 13.03.2002
Beiträge: 10.933
|
|
Respekt!
Haste gut gemacht 
)
Cu Selur
__________________
Hybrid
|
|
|
17.02.2003 13:23 |
|
|
ajf
DVDtoOgm & DVDtoMkv-Team
Dabei seit: 17.03.2002
Beiträge: 4.211
Herkunft: Erding
|
|
Echt klasse. Jetzt ist mir das gleich etwas klarer.:danke:
ajf
|
|
|
17.02.2003 16:56 |
|
|
The_Sorcerer
Routinier
Dabei seit: 28.08.2002
Beiträge: 455
Herkunft: Hessen
|
|
jaja.... ich habs ja schon immer vermutet 
...
jetzt fühl ich mich so richtig bestätigt ihr auch???
sagt bloß ihr habt keinen plan was da steht 
) 
__________________
|
|
|
17.02.2003 21:10 |
|
|
EthanoliX
Kaiser
Dabei seit: 11.04.2002
Beiträge: 1.310
Herkunft: Mainz
Themenstarter 
|
|
Was allerdings ziemlicher Humbug ist, ist die Verwendung von "i" als Index bzw. Variable, da es so allzu leicht mit i=(-1)^0.5 verwechselt werden kann.
__________________
"Der größte Trick, den der Teufel je gebracht hat, war die Menschheit glauben zu lassen, es gäbe ihn gar nicht."
Roger "Verbal" Kint, Die üblichen Verdächtigen
|
|
|
17.02.2003 21:47 |
|
|
filewalker
König
Dabei seit: 16.03.2002
Beiträge: 859
|
|
Hut ab! sehr informativ! :danke:
jetzt kann man sich drunter einwenig mehr vorstellen...scheint auf jeden Fall sehr, sehr komplex zu sein... vielleicht ein bisserl zu komplex für mich
.
Cu filewalker 
__________________
Beziehungen sind wie Songs: Manche vergisst du nie - egal ob gut oder schlecht!
|
|
|
17.02.2003 21:59 |
|
|
Selur
spamming old Newbie
Dabei seit: 13.03.2002
Beiträge: 10.933
|
|
Hab mal den Text von EthanoliX in der FAQ Sektion gepostet
Cu Selur
__________________
Hybrid
|
|
|
18.02.2003 12:27 |
|
|
elestrodix
DER Anleitungsmann ;)
Dabei seit: 17.03.2002
Beiträge: 634
Herkunft: Bonner Raum
|
|
jääaaa, gibts mir...
__________________
OGM-Overhead-Formel?guckst du hier
|
|
|
18.02.2003 14:54 |
|
|
EthanoliX
Kaiser
Dabei seit: 11.04.2002
Beiträge: 1.310
Herkunft: Mainz
Themenstarter
|
|
Wow, daß meine Variationen der deutschen Orthographie mal den Weg in die FAQs finden hätte ich ja nicht gedacht. Danke für die Lorbeeren. *schamhafterröt*
Freut mich, daß es euch geholfen hat.
Für alle die gerne 1CD-Ripps machen habe ich hier mal die Matrix aufgeschrieben, mit der ich "Gladiator" (2h 30min, 640*272, Ogg - Quality 0.200, XviD Koepi02012003, 800er - XCD (896MB)) auf eine CD gebracht habe:
8 16 19 22 25 32 48 64
16 16 20 22 25 32 64 96
19 20 22 25 28 48 80 112
22 22 25 28 32 48 96 112
25 25 28 32 48 64 96 128
32 32 48 48 64 96 112 128
48 64 80 96 96 112 128 128
64 96 112 112 128 128 128 128
Non-Intra identisch, bis auf 16 statt 8 im ersten Feld.
Bei Testsequenzen habe ich damit 10-20 % kleinere Files bekommen als mit der h 263-Matrix, ohne, daß die Kanten zu deutlich unschön werden.
Beim fertigen Film waren auch die Blockartefakte (z.B. bei Nebel o.ä.) kaum noch zu sehen (zumindest nicht, solange man nicht im Standbild direkt vor dem Bildschirm danach sucht).
__________________
"Der größte Trick, den der Teufel je gebracht hat, war die Menschheit glauben zu lassen, es gäbe ihn gar nicht."
Roger "Verbal" Kint, Die üblichen Verdächtigen
|
|
|
22.02.2003 00:22 |
|
|
|
|
|
|
|
