Videokompression

Die Kompressionsalgorithmen beruhen auf

• Redundanzen (Selbstähnlichkeiten) des Videosignals (Redundanzreduktion) sowie
• Unzulänglichkeiten und physiologischen Effekten des menschlichen Sehens (Irrelevanzreduktion).

Die Begriffe Redundanzreduktion und Irrelevanzreduktion stammen aus der Informationstheorie und beschreiben zwei verschiedene Ansätze zur Reduktion der Datenmenge, auch Datenkompression genannt, bei der Übertragung von Information. Dabei wird auf ein Modell zurückgegriffen, bei dem Information von einer Quelle zur Senke übertragen wird. Auf den konkreten Fall der Videokodierung übertragen entspricht die Quelle der Folge von Videobildern wie sie in der ursprünglichen Kamera entstehen, die Senke entspricht dem Auge des Betrachters.

Die Redundanzreduktion nutzt die Eigenschaften der Quelldaten zur Reduktion der zu übertragenden Datenmenge. Im Fall der Videokodierung werden statistische Eigenschaften des Bildsignals sowie Ähnlichkeiten (Korrelationen) zwischen zeitlich und räumlich benachbarten Bildpunkten ausgenutzt, um eine möglichst kompakte Darstellung zu erreichen. Erreichbar sind Kompressionsfaktoren von 1:2 bis 1:5. Da keine Informationen verloren gehen, spricht man von verlustloser Kodierung.

Zur Ausnutzung zeitlicher Korrelationen dienen die Verfahren der Inter-Kodierung, die aus bereits übertragenen Einzelbildern Schätzwerte extrapolieren, um nur noch die Schätzfehler übertragen zu müssen. (→Differenzkodierung) Für räumliche Korrelationen existieren die Verfahren der Intra-Kodierung, die Bildpunkte über die Differenz zu Schätzwerten aus räumlich umliegenden Punkten kodieren oder pixelüberspannende Bildmuster erkennen und kompakter beschreiben können. Zur Ausnutzung statistischer Redundanz erfolgt eine sogenannte →Entropiekodierung.

Die Irrelevanzreduktion zielt darauf ab, diejenige Information bei der Übertragung auszulassen, die für die Senke nicht relevant ist. Sie berücksichtigt physiologische Eigenheiten der menschlichen Sehwahrnehmung und verwirft gezielt Informationen, sodass die entstehenden Störungen für menschliche Betrachter möglichst wenig wahrnehmbar sind. Dadurch ist eine weitere Kompression von typischerweise 1:2 bis 1:50 möglich, abhängig von Verfahren und geforderter Qualität. Da Informationen verworfen werden, spricht man von verlustbehafteter Kodierung.

Konkret bedeutet dies im Fall der Videokodierung, dass durch Quantisierung nur ein Teil der Bilddaten übertragen wird.

Da die räumliche Auflösung der Farbwahrnehmung aufgrund der Anatomie des Auges schlechter ist als die Auflösung von Helligkeitsunterschieden, kann man die Auflösung der Farbinformationen verringern, ohne dass die Unterschiede stark wahrgenommen werden könnten. Man spricht dabei von Farbunterabtastung. Meist wird vor der Kodierung eine Konvertierung in ein entsprechendes Farbmodell vorgenommen und die Datenrate damit bereits um üblicherweise 50 % reduziert.

Eine weitere Eigenschaft des visuellen Systems, die ausgenutzt werden kann, ist die Frequenzabhängigkeit. Man kann Bilder, ähnlich wie Töne, auch als Überlagerung von zweidimensionalen Schwingungen darstellen. Niedrige Bildfrequenzen sind für grobe Bildstrukturen verantwortlich, hohe für feine Details. Störungen in den verschiedenen Frequenzbereichen werden unterschiedlich stark wahrgenommen, was an einem einfachen Testbild gut verdeutlicht werden kann^[1].

Diese Frequenzabhängigkeit wird in allen Videokompressionsverfahren der MPEG-Familie nach einer geeigneten Transformation als psychovisueller Faktor bei der Quantisierung genutzt.

Videokompressionsverfahren bestehen aus mehreren Teilverfahren, sogenannte Kompressionswerkzeuge (englisch tools), die verschiedene Arten von Redundanz ausnutzen. Auf Korrelationen räumlich benachbarter Bildpunkte stützen sich Verfahren der Intra-Frame-Vorhersage (Pixelextrapolation und Differenzkodierung) und die Transformationskodierung, zeitliche Abhängigkeiten werden bei der sogenannten Inter-Frame-Kodierung zum Beispiel Bewegungskompensation und Differenzkodierung (DPCM) genutzt und schließlich statistische Redundanz mittels Entropiekodierung reduziert.

Bei blockbasierter Transformationskodierung (zum Beispiel mit der diskreten Kosinustransformation, DCT) werden Einzelbilder (englisch frames) in quadratische Blöcke unterteilt und diese nach ihrer Komplexität beurteilt. Dieser Schritt ist notwendig, damit der Codec „weiß“, für welche (komplexen) Bildblöcke er viel Speicherplatz benötigt und für welche (einfachen) Blöcke weniger Bits genügen. Dies ist die Voraussetzung für die Irrelevanzreduktion.

Zur Nutzung von Ähnlichkeiten zwischen benachbarten Bildpunkten oder zwischen Einzelbildern wird üblicherweise die Differential Pulse Code Modulation (DPCM) eingesetzt: Es werden nur die Unterschiede zu bereits übertragenen Einzelbildern oder Bildpunkten gespeichert. Das Verfahren wird bei der Inter-Kodierung durch Bewegungskorrektur ergänzt.

Eine weitere Möglichkeit zur Verkleinerung der Datenmenge ist die Bewegungskorrektur (englisch motion compensation). Es wird nach übereinstimmenden Bildteilen gesucht, die sich gegenüber dem letzten Einzelbild weiterbewegt haben. Für diese wird ein Bewegungsvektor gespeichert, die unbewegten werden einfach vom letzten Einzelbild übernommen.

Mit einem Code mit variablen Wortlängen (englisch variable-length codes, VLC) können statistische Redundanzen in Wertereihen entfernt werden. Statt alle zu übertragenden Symbole mit konstanter Codewortlänge zu kodieren, werden häufiger auftretende beziehungsweise wahrscheinlichere Symbole mit kürzeren Codewörtern kodiert als seltenere Symbole. Hier haben Verfahren der Arithmetischen Kodierung die größte Verbreitung erreicht. Teils sind aber auch noch die ältere Huffman-Kodierung oder Varianten der weniger komplexen Lauflängenkodierung (zum Beispiel CAVLC) in Gebrauch.

Die Standardisierung begann mit dem Standard H.120, der noch keine praktische Verwendung fand. Gebräuchliche Videokodierungsformate folgen in der Regel dem mit dem Nachfolger H.261 (1988) etablierten Grundentwurf. Wichtigste Merkmale sind die blockbasierte Frequenztransformation, (bewegungskompensierte) Differential Pulse Code Modulation (DPCM) und Entropiekodierung. Die Haupttechniken dazu waren bis zum Jahr 1979 entwickelt. Dieser Grundentwurf wurde seither beständig verfeinert und Hilfstechniken entwickelt, was später auch hunderte Patente hervorbrachte. Viele ältere Techniken finden erst viele Jahre später breite Anwendung, wenn ihr Einsatz durch Fortschritte in der Leistungsfähigkeit der Mikroprozessortechnik praktikabel wird. Beispiel einer Ausnahme mit gewisser Relevanz ist der Wavelet-basierte VC-2-Standard (Dirac-Variante).

Die H.26x-Videoformatserie der ITU-T beziehungsweise die MPEG-Videoformate stellen bisher (2016) die dominierenden Videokodierungsstandards dar. Bis einschließlich H.264 markierten sie bei Veröffentlichung regelmäßig den Stand der Technik und mehrere konnten größte Verbreitung finden, darunter MPEG-1 (1991), MPEG-2 (1994) und zuletzt H.264/MPEG-4 AVC (2003). Daneben gab es außer Spezialformaten für Nischenanwendungen nacheinander verschiedene preisgünstigere und teils proprietäre Hauptkonkurrenten wie Microsofts Windows Media Video 9 beziehungsweise VC-1, mehrere Formate aus On2s VPx-Serie und zuletzt deren von Google freigekaufte Nachfolger VP8 und VP9. Seit Theora gab es Bemühungen um frei lizenzierte Formate, die zunächst noch weniger beachtet und technisch unterlegen waren. Mit Googles Freigabe von VP8 (2008) und VP9 (2012) geschahen hier bedeutende technische Fortschritte und schlossen die freien Formate in ihrer Leistungsfähigkeit weitgehend zum Stand der Technik auf. Mit der Alliance for Open Media formierte sich von Seiten der Industrie ab 2015 breite Unterstützung für lizenzkostenfreie Videoformate. Diese Alliance veröffentlichte 2018 das lizenzkostenfreie AV1, welches die Nachfolge von VP9 antritt.

Von den Bell Laboratories wurde 1950 das Patent auf DPCM angemeldet,^[2] welches schon sehr bald auf Videokodierung angewendet wurde. Die Entropiekodierung begann in den 1940ern mit Shannon-Fano-Kodierung,^[3] auf der die 1950 entwickelte, gebräuchliche Huffman-Kodierung aufbaut;^[4] die modernere kontextadaptive Arithmetische Kodierung (CABAC) wurde Anfang der 1990er veröffentlicht.^[5] Transformationskodierung (mittels Hadamard-Transformation) wurde 1969 eingeführt,^[6] die verbreitete Diskrete Kosinustransformation (DCT) tauchte 1974 in der wissenschaftlichen Literatur auf.^[7][8]

• Audiodatenkompression

• Lajos L. Hanzo, Peter J. Cherriman, Jürgen Streit (University of Southampton): Video compression and communications. from basics to H.261, H.263, H.264, MPEG2, MPEG4 for DVB and HSDPA-style adaptive turbo-transceivers. 2. Auflage. IEEE Press, 2007, ISBN 978-0-470-51849-6. 

1. ↑ Testbild zur Darstellung der Frequenzabhängigkeit der Auflösungswahrnehmung des menschlichen Auges (Memento vom 30. Oktober 2007 im Internet Archive)
2. ↑ Patent US2605361: Differential Quantization of Communication Signals. Angemeldet am 29. Juni 1950, veröffentlicht am 29. Juli 1952, Erfinder: C. Chapin Cutler.‌
3. ↑ Claude Elwood Shannon: A Mathematical Theory of Communication. In: Alcatel-Lucent (Hrsg.): Bell System Technical Journal. Band 27, Nr. 3–4, 1948 (englisch). 
4. ↑ David Albert Huffman: A method for the construction of minimum-redundancy codes. In: Proceedings of the IRE. Band 40, Nr. 9, September 1952, S. 1098–1101, doi:10.1109/JRPROC.1952.273898 (englisch, compression.ru [PDF]). 
5. ↑ CCITT Study Group VIII und die Joint Photographic Experts Group (JPEG) von ISO/IEC Joint Technical Committee 1/Subcommittee 29/Working Group 10: Recommendation T.81. Digital Compression and Coding of Continuous-tone Still images – Requirements and guidelines. Hrsg.: ITU-T. 1993, Annex D – Arithmetic coding, S. 54 ff. (englisch, w3.org [PDF; abgerufen am 7. November 2009]). 
6. ↑ William K. Pratt, Julius Kane, Harry C. Andrews: „Hadamard transform image coding“, in Proceedings of the IEEE 57.1 (1969): S. 58–68
7. ↑ Nasir Ahmed, T. Natarajan, Kamisetty Ramamohan Rao: Discrete Cosine Transform. In: IEEE Transactions on Computers. C-23, Nr. 1, Januar 1974, S. 90–93, doi:10.1109/T-C.1974.223784 (englisch, tu-berlin.de [PDF]). 
8. ↑ Cliff Reader: Patent landscape for royalty-free video coding. In: Society of Photo-Optical Instrumentation Engineers (Hrsg.): Applications of Digital Image Processing XXXIX. San Diego, California 31. August 2016 (englisch, Vortragsmitschnitt, ab 3:05:10).