Die diskrete Kosinus-Transformation (DCT)

Die diskrete Kosinustransformation (DCT – discrete cosine transformation) ist eine  diskrete, reellwertige, lineare und orthogonale Transformation.  Sie wurde 1974 ertsmalig vorgestellt und wurde aus der Fourier-Transformation (FT) unter Ausnutzung von Signalsymmetrien abgeleitet. Da es sich um eine reellwertige Transformation handelt, im Gegensatz zur FT deren Ergebnisse einen Real- und einen Imaginärteil hat, was natürlich nicht ganz so bequem zu handhaben ist und auch die doppelte Menge an Daten erfordert.

In diesem Artikel möchte ich einerseits die theoretischen Grundlagen und Anwendungsgebiete der DCT streifen, sowie anhand von Codebeispielen in Java eine Implementierung der diskreten Kosinustransformation vorstellen.

Theoretischer Hintergrund der diskreten Cosinus-Transformation

Generell kann man mit Hilfe der DCT eine Transformation eines Signales in geeignete Basisfunktionen vornehmen. Dabei werden die Signalwerte x auf die Koeffizienten der Basisfunktion abgebildet. Dabei gilt es Basisfunktionen zu finden die das Signal in möglichst wenige Bestandteile aufteilen. Die Qualität der Basisfunktionen wird zudem dadurch bestimmt, wie gut das Signal dekorreliert wird. Dekorrelation ist in diesem Zusammenhang so zu verstehen, dass Abhängigkeiten der Signalwerte untereinander reduziert werden, da bei zeitlichen oder räumlichen Signalen Werte meist vom benachbarten Wert abhängen. Nach der Dekorrelation sollen die Abhängigkeiten möglichst beseitigt sein, ohne dabei Informationsgehalt zu verlieren. Abgesehen von der Transformationen eigenen sich zur dekorrelation von Signalen sog. Prädiktionsverfahren, wie die lineare Prädiktion, oder aber Filterbanken.

Anwendungsgebiete der DCT

Genau wie die DFT wandelt die DCT ein Signal vom Orts- bzw. Zeitbereich in den Frequenzbereich. Besonders im Audio- und Videobereich liegen oftmals im unteren Spektralbereich hohe Signalenergien vor die mit Hilfe dieser Transformation gut dekorreliert werden können.

Ein weiteres Anwendungsgebiet ist die Bildverarbeitung. Ein bekanntes Beispiel ist das JPEG Format, welches die 2-D Kosinustransformation einsetzt  um die Bildmatrix vom Ortsbereich in den Frequenzbereich zu wandeln, welcher die Helligkeitsschwankungen einen Bildes visualisiert. Bei der Frequenzanalyse der Helligkeitsschwankungen werden grobe und feine Strukturen eines Bildes voneinander getrennt. Beim JPEG-Format ist die Transformation eine Vorbereitung der Daten für die anschliessende Kompression.

Implementierung der diskreten Cosinus-Transformation

Es gibt generell drei populäre Möglichkeiten für die Implementierung.

Die direkte Implementierung

Die separierte Implementierung, welche die 2D DCT auf die eindimensionale Variante zurückführt. Dies reduziert die Komplexität um eine Größenordnung: O(n^4) -> O(n^3)

Das Schema von Arai, welches einen sehr schnellen Algorithmus für den (wichtigen) Spezialfall N=8 bezeichnet. Auf diesen Algorithmus werde ich hier jedoch nicht näher eingehen, da die Implementierung eher trivial ist. Auf Wunsch kann ich jedoch auch hier eine Erklärung sowie eine Implementierung gerne hinzufügen.

Codebeispiel – Java Implementierung der direkten Kosinus-Transformation

	/**
	 * Methode führt die direkte DCT durch
	 * *** Methode getestet ***
	 * keine Ausnahmebehandlung
	 * @param input
	 * @param output
	 */
	public static void dctDirect(double[][] input, double[][] output){
		int n=input.length;
		double ca;
		double cb;
		double tmpXab=0.0;
		double cmpnt;
		for(int a=0;a<n;a++){
			for(int b=0;b<n;b++){
				for (int x=0;x<n;x++){
					for (int y=0;y<n;y++){
						cmpnt=input[x][y] * Math.cos(((2.0*x+1.0)*a*Math.PI)/(2.0*n))*Math.cos((2.0*y+1.0)*b*Math.PI/(2*n));
						tmpXab=tmpXab+cmpnt;
						cmpnt = 0.0;
					}
				}
				if(a==0)ca=(1.0/Math.sqrt(2.0));
				else ca=1.0;
				if(b==0)cb=(1.0/Math.sqrt(2.0));
				else cb=1.0;
				output[a][b]=(2.0/n)*ca*cb*tmpXab;
				tmpXab=0.0;
			}
		}
	}

Codebeispiel - Java Implementierung der inversen Kosinus-Transformation (iDCT)

/**
	 * Methode führt die inverse DCT für eine 8x8 Matrix durch
	 * *** Methode getestet ***
	 * keine Ausnahmebehandlung
	 * @param input 
	 * @param output
	 * 
	 */
	public static double[][] iDCT(double[][]input, double[][]output){
		//Direkte Transformation - hier können N*N Blocks übergeben werden
		//Achtung: keine X*Y Blocks
		
		int n=8;
		double ci=0.0;
		double cj=0.0;
		double tmpXab=0.0;
		double cmpnt=0.0;
		for(int x=0;x<n;x++){
			for(int y=0;y<n;y++){
				for (int i=0;i<n;i++){
					for (int j=0;j<n;j++){
						//Summe über die Eingabemtx für jedes Glied der Ausgabemtx
						if(i==0)ci=(1.0/Math.sqrt(2));
						else ci=1.0;
						if(j==0)cj=(1.0/Math.sqrt(2));
						else cj=1.0;
						cmpnt=input[i][j]*Math.cos((2*x+1.0)*i*Math.PI/(2.0*n))*Math.cos((2.0*y+1.0)*j*Math.PI/(2.0*n));
						tmpXab+=(2.0/n)*ci*cj*cmpnt;
						cmpnt=0.0;
					}
					
				}
				output[x][y]=Math.round(tmpXab);
				tmpXab=0.0;
				//cmpnt=0.0;
			}	
		}
		return output;
	}