|
  |
 DCT und Custom-Matrix, kurze(?) Übersicht |
Videostation
Super Moderator
Dabei seit: 16.03.2002
Beiträge: 1.533
Herkunft: Dresdner Raum
 |
|
| DCT und Custom-Matrix, kurze(?) Übersicht |
     |
DCT und Custom-Matrix, kurze(?) Übersicht
(by Ethanolix & Videostation) - 30.05.2003
Einer der Vorteile von XviD ist, dass man direkt die Quantisierungsmatrix bearbeiten kann. Jedoch ist dies zu Anfang recht schwierig, wenn man nicht genau weiß, welche Bedeutung der Matrix zukommt bzw. für was die einzelnen Werte stehen.
Wir sind zwar keine Experten auf diesem Gebiet, billigen uns aber zu soviel von der Materie zu verstehen, um all denjenigen, 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-/Farbwerte => Frequenzspektrum
Um bei der Videokomprimierung (wie auch bei der reinen Bildkompression nach JPEG) eine möglichst effektive Datenreduktion zu erreichen, überführt man die Bildinformation mittels Diskreter Cosinus Transformation (DCT) in den Frequenzbereich. Die DCT ist eine Sonderform der DFT (Diskrete Fourier Transformation). Die Besonderheit und der Vorteil der DCT liegt darin, dass das Ergebnis reellwertig ist und nicht wie bei der DFT komplexe Anteile enthält. Sie dient bei der Bildverarbeitung zur Irrelevanzreduktion.
Vor der DCT wird das Quellbild in 8*8 Pixel große Blöcke zerlegt, um einerseits den Rechenaufwand für die DCT in Grenzen zu halten und andererseits ein möglichst gutes Ergebnis sowie eine hohe Kompression zu erzielen. Aus diesem Vorgehen ergeben sich aber auch die allseits bekannten Blockartefakte bei der Dekodierung, falls das Material zu stark komprimiert wurde.
Ein Farbbild wird dazu in seine Komponenten zerlegt Helligkeit (Luminance = Y) und Farbart (Chrominance = C). Das Farbartsignal besteht dabei aus zwei so genannten Farbdifferenzsignalen, Cb entspricht dem Blaudifferenz- und Cr dem Rotdifferenzsignal. Die DCT wird bei jeder der drei Komponenten, für einen 8*8-Block, durchgeführt. Dem Algorithmus ist es dabei egal, ob es sich um Helligkeits- oder Farbdifferenzwerte handelt.
Die zweidimensionale DCT ist definiert durch:
Die zweidimensionale iDCT lautet folgendermaßen:
In beiden Gleichungen gilt:
An dieser Stelle vielleicht noch ein, zwei Sätze zu den Gleichungen. Die Werte k und n sowie x und y definieren die Position des DCT-Koeffizienten bzw. des jeweiligen Pixels in der 8*8 Matrix. Die Funktionen C(k) bzw. C(n) sind Gewichtungsfaktoren.
Um einen DCT-Koeffizienten zu berechnen erfolgt die Multiplikation jedes einzelnen Helligkeits- oder Farbwertes der Bildmatrix , von (0,0) bis (7,7), mit den entsprechend gewichteten Kosinusfunktionen und deren anschließenden Summation. Hier wird auch der hohe Rechenaufwand deutlich. In der Praxis gibt es jedoch optimierte DCT-Implementierungen, die die Anzahl der durchzuführenden Rechenoperationen minimiert. Anhand der Transformationsgleichungen wird somit auch ersichtlich, dass mit Vergrößerung der Pixelanzahl eines Blocks der Aufwand stark ansteigt und deshalb eine Begrenzung auf 8*8 Pixel sinnvoll ist.
Wie man sich die Arbeitsweise dieser Transformationsgleichungen vorzustellen hat, wird im nächsten Abschnitt genauer erklärt.
Was das nun???
Jedes Pixel des entsprechenden Blockes repräsentiert dabei einen Helligkeits- bzw. Farbwert. Trägt man beispielsweise die Helligkeitswerte der ersten Zeile eines 8*8-Blockes gegen die Pixel auf, erhält man im mathematischen Sinne eine Funktion [x-Achse: Pixel 0,... ,7; y-Achse die Grauwerte z.B. auf einer 256 Stufen-Skala (8bit)]. Diese stufenartige Funktion wird bei der DCT durch eine Summe modifizierter Kosinusfunktionen ersetzt.
Bei der graphischen Darstellung eines 8*8-Blocks würde sich hierbei eine dreidimensionale Funktion für jede einzelne der drei Bildkomponenten Y, Cb und Cr ergeben [x- & y-Achse: Pixelkoordinaten; z-Achse: Helligkeits- bzw. Farbwert]. Da diese Funktion nicht kontinuierlich verläuft, sondern stufenartig (wertediskret), kann man sie auch als 8*8 Matrix darstellen. In dieser Matrix steht jeder Koeffizient für den Helligkeits- oder Farbwertwert des entsprechenden Pixels im 8*8 Block. Jeder dieser 8*8-Blöcke kann durch eine gewichtete Summe der 64 DCT-Basisbilder (Bild 1) dargestellt werden, d.h. jedes Basisbild wird mit einem bestimmten Faktor beaufschlagt. Wie man sich die DCT-Basisbilder veranschaulichen kann zeigt folgendes Bild:
Wichtig ist, dass jede dieser cos-Funktionen Daten für jedes der 64 Pixel des Blockes enthält.
Der Koeffizient. links oben (0,0), auch DC-Koeffizient genannt beschreibt, die Grundhelligkeit des Blockes an sich. Der darunter (1,0) den einfachen Helligkeitsverlauf von der ersten bis zur 8. Pixelzeile und der Koeffizient. (0,1) den Helligkeitsverlauf von der ersten bis zur 8. Pixelspalte usw. Man sieht, dass die Muster immer Detailreicher werden, je weiter man nach unten rechts gelangt.
Nach der DCT erhält man wieder eine 8*8 Matrix mit den DCT-Koeffizienten (Frequenz-Matrix, FM). Jeder Koeffizient steht jetzt für eine Funktion, die für sich alleine schon einen 8*8 Pixel-Block darstellt. Um den Ursprünglichen Block zurück zu erhalten, werden alle 64 cos-Funktionen mit dem DCT-Koeffizienten in der Matrix multipliziert und aufaddiert, d.h. überlagert. Die einzelnen Koeffizienten geben also an, wie stark die jeweilige Funktion bei der Darstellung des Blockes zu berücksichtigen ist. In Bild 2 ist die gewichtete Überlagerung der einzelnen DCT-Basismuster, zur Rekonstruktion des Originalbildblocks dargestellt.
Und was mach die Quantizer-Matrix (QM) des Codec?
Nachdem man (also eigentlich ja der Abakus digitalis) die DCT durchgeführt hat, hat man, wie oben schon erwähnt, eine Matrix mit 64 DCT-Koeffizienten und noch kein einziges Bit gespart. Im Gegenteil, waren es vor der DCT 8Bit Werte (0...255 bzw. -128...+127 mittelwertfrei), so sind nach der DCT sogar 12Bit (-2048...+2047) zur Speicherung notwendig. Und genau hier kommt die Quantizer Matrix des Codec ins Spiel.
Der Codec dividiert nun jeden Wert der DCT-Koeffizienten Matrix durch den entsprechenden Wert in der Quantizer-Matrix und rundet dann auf den nächstgelegenen Integer, d.h. ganzzahlig. 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 (Siehe XviD Encoding Mode). Durch dieses Division und die anschließende Rundung wird ein Großteil der DCT-Koeffizienten zu Null. Je größer der Quantizer gewählt wird, desto mehr Koeffizienten der Matrix erhalten den Wert Null. Denn je mehr Nullen in der Matrix enthalten sind, desto effektiver lässt sich der Bildblock komprimieren, vor allem wenn es sich um lange Nullfolgen handelt. Aus diesem Grund wird die Matrix nach einem Zick-Zack Schema ausgelesen (Bild 3), d.h. von niedrigen zu hohen Frequenzen hin. Denn mit steigender Frequenz steigt auch die Wahrscheinlichkeit das des entsprechende Element den Wert Null besitzt. Die in Bild 3 gezeigte Zick-Zack-Folge wird für progressives Bildmaterial, die alternative Zick-Zack-Folge in Bild 4 für Interlaced-Material verwendet.
Die serielle Datenfolge, die man nun erhält, wird noch einer Redundanzreduktion unterzogen. Wobei zuerst eine Lauflängenkodierung (RLC) und anschließend eine variable-Längenkodierung (VLC) zum Einsatz kommt.
Bei der RLC werden ununterbrochene Folgen von Nullen in einer Zahl gespeichert, d.h. in einem Zahlenpaar. Die erste Zahl ist die Anzahl der Nullen, die zweite die eigentliche Zahl nach der Nullfolge. Für den Fall, dass ab einem bestimmten Koeffizienten bei der Zick-Zack-Abtastung nur noch Nullen folgen, wird nicht mehr jeder einzelne Koeffizient als Bitfolge gespeichert, sondern mit einem "end of block" Codewort angegeben, dass der Rest der Koeffizienten Null ist. Am folgenden Beispiel ist eine Bitfolge vor und nach der RLC zusehen:
... 0 11 0 0 1 0 -1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 2 ...
... (1,11) (2,1) (1,-1) (4,2) (9,2)...
Die anschließende VLC übernimmt dabei ein statistisches Kodierungsverfahren wie die Huffman-Kodierung. Hier werden häufig auftretenden Werten kurze und selten auftretenden Werten lange Codewörter gegeben, vergleichbar mit dem MORSE-Alphabet.
Hieraus wird auch ersichtlich, dass die aktuelle Bitrate über den Quantizer variiert wird: Höherer Quantizer => mehr Koeffizienten =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, wird diese im Regelfall mit übertragen. Falls es sich um Standardwerte, wie bei der H.263 Matrix handelt kann auch nur eine entsprechende Kennung gesendet werden. Bei der Wiederherstellung des Bildblocks, nach der iDCT (inverse Diskrete Cosinus Transformation), machen sich nun die Rundungsfehler der Quantisierung bemerkbar. Die Frequenzen, deren Koeffizienten als Null gespeichert wurden, werden bei der iDCT, bei der aus der FM wieder der Bildblock gewonnen wird, also gar nicht erst berücksichtigt.
Wichtig! Die folgende Beispielrechnung soll nur die groben, prinzipiellen Auswirkungen der Rundung darstellen, weil die Rekonstruktion ebenfalls eine gewichtete Überlagerung aller gespeicherten DCT-Koeffizienten darstellt und die Abweichung in der Praxis nicht so berechnet werden kann.
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,4375, also gerundet 2 gespeichert. Beim Rekonstruieren der Frequenz-Matrix während des Dekodierens, ergibt sich daher für den entsprechenden Koeffizient.: 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.
Bild 5 zeigt den Ablauf der Bildkompression an einem realen Beispiel. In der Matrix links oben sind die Helligkeitswerte eines Bildblocks dargestellt. Diese werden mit Hilfe der DCT in den Frequenzbereich überführt. Die DCT-Koeffizienten die man nach dieser Transformation erhält werden jetzt durch die Werte der Quantisierungsmatrix rechts oben geteilt. In diesem Fall wurde noch ein Quantizer von 2 verwendet, d.h. vor der Divison müssen alle Werte der h.263-Matrix verdoppelt werden. Nach der Quantisierung erhält man die im Bild links unten dargestellte Matrix. Hier ist auch deutlich der Grund für die Quantisierung zu erkennen. Je größer der Quantizer, desto mehr DCT-Koeffizienten werden zu Null. Das letzte Bild rechts unten zeigt den rekonstruierten Bildblock nach der iDCT. An dieser Matrix wird die Verfälschung der Ausgangswerte durch die Quantisierung und anschließende Rundung ersichtlich. Des Weiteren ist auch nachzuvollziehen, dass das oben gezeigte Rechenbeispiel so nicht funktioniert.
In Bild 6.1 ist der Originalbildblock und in Bild 6.2 der rekonstruierte Bildblock stark vergrößert (Faktor 20) zu sehen. Bild 6.3 zeigt die beiden Blöcke in Originalgröße (8*8 Pixel), direkt nebeneinander. Hier ist rein optisch eigentlich kein Unterschied zwischen Originalbildblock und rekonstruiertem Bildblock zu erkennen.
|
|
19.05.2003 22:42 |
|
|
Videostation
Super Moderator
Dabei seit: 16.03.2002
Beiträge: 1.533
Herkunft: Dresdner Raum
Themenstarter 
|
|
Und was heißt das jetzt für meine Matrix?
Mit diesem Wissen und ein paar Tests, lassen sich folgende Leitlinien für die Entwicklung einer eigenen Matrix erstellen:
- kleine Werte => weniger Detailverlust, hoher Speicherbedarf
- beste Komprimierbarkeit, wenn Quantisierungswerte gemäß der Speicherreihenfolge ansteigen
- übertrieben hohen Werte in den ersten beiden Spalten und Zeilen führen zu verfrühter Blockartefaktbildung
Dies ist sicherlich nicht alles, was es zu beachten gilt, aber zumindest das, was sich einigermaßen leicht in Worten ausdrücken lässt. Ansonsten ist natürlich noch sagen, dass man am besten erst einmal selber testet, testet und noch mal testet. Dafür eignen sich am besten Sequenzen mit scharfen Kanten (hell/dunkel-Übergänge), dunkle Flächen (z.B. Nachtszenarien) und natürlich sehr detailreiches Bildmaterial.
Es hilft auch beim testen Matrizen zu verwenden, deren Werte bewusst übertrieben sind, einfach um den Einfluss und den Effekt abschätzen zu können, den die Quantisierungsmatrix auf das Endergebnis hat.
So das war's für's erste.
Zu guter letzt sei noch mal daran erinnert, dass dies nur eine grobe Übersicht zum Thema sein soll. Es kann gut sein, dass sich der eine oder andere Fehler eingeschlichen hat. An dieser Stelle sind wir für Korrekturen dankbar. Ebenso können und wollen wir nicht ausschließen, dass sich manch einem, der tiefere Einblicke in die Materie oder die dahinter stehende Mathematik hat, die Fußnägel rollen, wenn er diese mathematisch sicherlich nicht hasenrein formulierten Zeilen liest.
Dieser Text erhebt keinen Anspruch auf Vollständigkeit!!!
Aber wir hoffen, dass diejenigen, die sich für dieses Thema interessieren, ein wenig Einblick in die entsprechende Materie bekommen haben. Wer noch ein wenig mehr lesen möchte, dem seien die folgenden Links empfohlen:
Bei Fragen, Vorschlägen, Fehlern etc. bitte eine PM an mich schicken bzw. direkt in diesem Thread posten: http://www.flaskmpeg.info/board/thread.php?threadid=3104&boardid=9&styleid=
1
|
|
|
19.05.2003 22:45 |
|
|
|
|
|
|
|
