Benutzer:ThePacker/Datenkompression ICT

Die ICT

Die ersten Grundlagen für diese Transformation legte der französische Mathematiker Fourier. Er war es, der auf die Idee kam eine Funktion durch die Summe verschiedener perodischer Funktionen darzustellen. Die Summe der periodischen Funktionen wird Fourierserie genannt. Im Jahre 1974 entstand daraus die Diskrete Cosinus Transformation. Die Transformation eines Bildes oder einer Anderen Funktion benötigt jedoch eine Reihe von Multiplikationen und Additionen. Außerdem wird nicht mit einfachen Integerzahlen operiert, sondern mit Fließkommaarithmetik, was eine besondere Genauigkeit bei der Transformation erfordert. Diese ist als reine Hardwarelösung nur schwer zu realisieren. Wenn in kurzer Zeit jedoch Millionen solcher Transformationen durchgeführt werden müssen, spielt jede einzelne aufwändige Fließkomma-Multiplikation und Fließkomma-Addition eine Rolle, die eingespart werden kann.

Die Integer Cosinus Transformation ist eine Transformation, die eine DCT-ähnliche Berechnung durchführt, die verglichen mit der DCT jedoch eine extrem geringere Berechnungskomplexität aufweist. Die ICT ist so ausgelegt, dass sie ausschließlich mit Additions- und Shift- Operationen im Integerbereich auskommt. Eine Shiftoperation wird in Hardware, meist mit Hilfe eines Multiplexers realisiert. Für die Addition werden die üblichen Halb- und Volladdierer verwendet.

Die DCT ist die wohl am häufigsten verwendete Transformationsvorschrift, weil sie relativ betrachtet die höchste Qualität bietet. Sie wird für die Bildkompression, Videompression und die Audiokompression verwendet, denn sie kommt einer idealen energetischen Transformation am nächsten.

Die erste praktische Anwendung der ICT, erfolgte in der Galileo-Sonde, in der sie für die Bildkompression verwendet wurde. Es wurde speziell ein Mikrochip entwickelt, der für die Bildverarbeitung in der Galileo-Sonde zuständig ist.

ICT(a,b,c,d,e,f,g)

Eine Integer Cosinus Transformation (ICT) wird mit Hilfe von sieben Parametern definiert. Ein Beispiel für eine solche Parametrierung ist ICT(246,222,147,50,3,1). Sie hat nur sechs Parameter statt sieben in der Überschrift. Meist ist der letzte Parameter $g=1\,$ . Dieser wird im Allgemeinen nur dann angegeben, wenn er nicht 1 ist.

\mathbf {T} =\mathbf {K} \mathbf {J}

K - Normalisierung- und Diagonalmatrix

\mathbf {J} ={\begin{bmatrix}g&g&g&g&g&g&g&g\\a&b&c&d&-d&-c&-b&-a\\e&f&-f&-e&-e&-f&f&e\\b&-d&-a&-c&c&a&d&-b\\g&-g&-g&g&g&-g&-g&g\\c&-a&d&b&-b&-d&a&-c\\f&-e&e&-f&-f&e&-e&f\\d&-c&b&-a&a&-b&c&-d\end{bmatrix}}

Orthonalität genau dann wenn $ab=ac+bd+cd$

(10,9,6,2) $10\cdot 9=10\cdot 6+9\cdot 2+6\cdot 2$

$90=60+18+12$

Ähnlichkeit zur DCT genau dann wenn $a\geq b\geq c\geq d$ und $e\geq f$

ICT(10,9,6,2,e,f,g)

Im Standard H.264 (f.k.a H.26L, a.k.a. MPEG 4 Part 10) entschied man sich für diese Variante. Sie ist von der Seite der Berechnungskomplexität betrachtet ein wahrer Traum und sehr nahe am erreichbaren Optimum, welche mit der ICT(246,222,147,50,3,1) erzielt werden kann. Sie ist zwar immer noch etwas schlechter als die DCT, aber weitaus einfacher zu berechnen.

In der Zukunft werden wird sich die ICT in der Videokompression und Bildkompression weiter durchsetzen. Das Potential das diese Transformation bietet ist zu groß um ungenutzt zu bleiben. Damit ist es möglich mobile Geräte (bspw. Mobile Telefone, Camcorder, Digitalkameras) noch stromsparender zu betreiben. Um es etwas besser zu verdeutlichen, es können durch Ersetzen der DCT durch die ICT mehr als 85 Prozent der Chipfläche eingespart werden, die für die DCT benötigt wird. Ein weiterer Vorteil ist, dass Rundungsfehler, die während der Berechnung der DCT entstehen, schlicht und ergreifend entfallen. Der Preis hierfür ist eine vernachlässigbare und leicht verschechtere Dekorrelation des zu transformierenden Signals.

Speziell im Bereich der HDTV-Codecs (1920x1200, 1920x1080) ist eine effiziente Blocktransformation nötig. Es müssen viele Tausend Transformationsoperationen pro Sekunde durchgeführt werden. Dafür eignen sich Rechenoperationen auf ganzen Zahlen einfach besser.

Transcodierung

DCT <-> ICT

Weitere Parametrierungen

ICT(230,201,134,46,3,1) - Orthogonal
ICT(175,153,102,35,3,1) - Orthogonal
ICT(120,105,70,24,3,1) - Orthogonal
ICT(185,162,108,37,3,1) - Orthogonal
ICT(250,219,146,50,3,1) - Orthogonal

ICT(120,105,70,24,3,1) -
ICT(65,57,38,13,3,1) -
ICT(55,48,32,11,3,1) - Orthogonal
ICT(75,66,44,15,3,1) - Orthogonal
ICT(85,75,50,17,3,1) -

ICT(55,51,34,11,3,1) - Ortogonal
ICT(45,39,26,9,3,1) -
ICT(45,42,28,9,3,1) -

ICT(25,24,16,5,3,1) -
ICT(25,21,14,5,3,1) -
ICT(24,21,15,4,3,1) -
ICT(26,24,15,6,3,1) -

ICT(15,15,10,3,3,1) -
ICT(15,12,8,3,3,1) -
ICT(14,12,9,2,3,1) -
ICT(12,10,6,3,3,1) -

ICT(6,6,3,2,3,1) -
ICT(6,6,3,2,6,2) -
ICT(5,3,2,1,3,1) -
ICT(7,4,3,1,3,1) -
ICT(3,2,1,1,3,1) -

ICT(205,180,120,41,3,1) - Orthogonal
ICT(140,123,82,28,3,1) - Orthogonal
ICT(215,189,126,43,3,1) - Orthogonal
ICT(235,207,138,47,3,1) - Orthogonal
ICT(246,222,147,50,3,1) - Orthogonal - Höchste Transformationseffizienz - was bedeutet das genau ?

ICT(10,9,6,2,3,1) - Höchste Effizienz für a<7 bit jedoch etwas schlechter als DCT / aber sehr effizient (Runtime)
ICT(10,9,6,2,3,1) - Orthogonal
ICT(10,9,6,2,10,4,8) - H.264
ICT(10,9,6,2,10,5,8)
ICT(10,9,6,2,9,3,1)
ICT(10,9,6,2,9,3,2)
ICT(10,9,6,2,8,4,8)

Quellenangaben

Galileo Bildkompression (eng.)
Compression of Color Images(PDF) (eng.)
Homepage von Cham, Wai-kuen (Erfinder der ICT)
- (Der Originalartikel des Entwicklers der ICT), 1989
- IEE Proceedings, Vol 136, Part 1, No 4, August 1989, Wai-Kuen Cham: Development of integer cosine transforms by the principle of dyadic symmetry
- An Order-16 Integer Cosine Transform, 1991
A Simplified Integer Cosine Transform and Its Application in Image Compression, 1994
IEEE Ttransactions on Signal Processing, Vol 53, No 2, February 2005, Ruiz et al.: Parallel-Pipeline 8x8 Forward ICT Processor Chip for Image Coding