Schnelle Fourier-Transformation (1D + 2D) für ActionScript

Wie schon in einem älteren Beitrag (SoundMixer.computeSpectrum() vs. Sound.extract()) von mir beschrieben, gibt es (noch immer) ein Problem mit der computeSpectrum Methode des SoundMixers. Diese Methode zum Auslesen des Spektrums ist an sich eine schöne Funktion, gehört aber dem SoundMixer. Dieser ist eine globale Flash-Klasse, was einige Probleme mit sich bringt. Nutzt man diese Funktion innerhalb eines SWFs und hat andere SWF, welche Sound beinhaltet offen, kommt es unweigerlich zu Sicherheitsfehlern und wirklich unschönen Geräuschen.

Umgehen lässt sich dies mit Hilfe der der extract() Methode der Sound-Klasse. Hier wird das gesamte Frequenzspektum des Sounds augelesen und kann weiter verwendet werden. Aber es gibt einen gravierenden Unterschied bei beiden Mehtoden. Die computeSpectrum liefert von Haus aus eine schnelle Fourier Transformation mit. Hingegen liefert die extract()-Methode nur RAW-Daten zurück. Kurz zusammengefasst bedeutet dies, dass mit Hilfe der computeSpectrum die zurückgelieferten Frequenzen nach Bereich sortiert werden und bei der anderen Funktion eben nicht.

Klar könnte man hingehen und selbst eine einfache Sortierfunktion schreiben. Doch bei der etwas größeren Datenmenge die bewältigt werden muss, wird dies das Script auf jeden Fall verlangsamen. Eine Methode die verwendet werden kann zur Sortierung ist die Schnelle Fourier-Transformation, die auf der Diskreten Fourier-Transformation basiert. Aber leider gab es diese Funktion, wie gesagt, nur innerhalb der computeSepctrum() Methode.

Nun hat Eugene Zatepyakin sich die Mühe gemacht und eine Implementierung der schnellen Fourier-Transformation in ActionScript 3 geschrieben, die frei verfügbar bei Google-Code ist. Mit Hilfe dieser Klassen konnte ich, nach ein paar Tests, den SoundVisualizer mit der Funktionalität zur Sortierung der Sound Daten erweitern, ohne die oben kurz angerissenen Probleme wieder aufzureißen.

Die Implementierung ist, wie Eugene sie auch beschreibt, sehr einfach. Für die Verwendung mit Sound wird die FFT-Klasse verwendet. Des weiteren gibt es noch die FFT2D-Klasse, welche die Möglichkeit eine zweidimensionale Transforation durchzuführen bietet, wie sie etwa bei Bildern Verwendung findet. Bei der Initialisierung der Klasse mit deren init()-Methode sollte man auch nicht über 2048 Bytes gehen, da sonst wiederum die Performance leidet. Besonders ist darauf zu achten, dass die Anzahl der ausgelesenen Bytes über die extract-Methode mit der bei der init Methode übereinstimmt.

Der eingentliche Analyzer ist in der FFTSpectrumAnalyzer-Klasse. Hier wird in der initLogarithmicAverages-Methode zunächst die Mindestbandbreite angegeben und die Anzahl an Bändern, in die eine Oktave unterteilt werden soll.
Sehr wichtig ist auch die Einstellung „Little Endian“ für den ByteArray, welcher die resultierenden Daten hält. Innerhalb des onSampleDataEvent-Handlers werden die ausgelesenen Bytes dann der fft-Klass mittels setStereoRAWDataByteArray(bytes) mitgegeben, um dann anschließend die forwardFFT() aufzurufen, welche die eigentliche Transformation ausführt. fftHelp.analyzeSpectrum() liefert dann den analysierten ByteArray, welcher dann weiter benutzt werden kann für alle möglichen visuellen Ausgaben, zurück. Noch ist hier der Sound selbst noch nicht ausgegeben. Dafür müssen die Bytes zurück transformiert werden über fft.inverseFFT(). Nach dem Zurücksetzen der Position innerhalb des BytesArrays können nun die SoundBytes an event.data zur Ausgabe übergeben werden. Den genauen Ablauf der Funktionen kann man auch auf Google Code nachlesen. Hier hat Eugene zwei Beispielscripts eingefügt. Und als anschauliches Beispiel für die Verwendung seiner Bibliothek einfach den zeroseven SoundVisualizer anschauen. Hier ist im letzten Reiter eine weitere Checkbox, in der man angeben kann, ob die Daten sortiert (FFT) oder unsortiert (RAW) verwendet werden sollen.

Links:

Flash Matrix

Die Matrix Klasse ist eine Transformationsmatrix. Sie legt fest, wie ein Punkt innerhalb des Koordinatensystems einem anderen Koordinatenraum zugeordnet ist. Mit Hilfe dieser Matrix ist es möglich, Objekte zu verschieben, skalieren, drehen und zu scheren beziehungsweise zu neigen. Dabei handelt es sich um affine Transformationen, was bedeutet, dass gerade und somit parallele Linien erhalten bleiben.

Über die transform() Methode lassen sich somit DisplayObjects mit den oben beschriebenen Eigenschaften modifizieren. Aber auch der BitmapData.draw() Methode enthält als Parameter eine Matrix, welche dann bestimmt, wie das neue BitmapData-Objekt gezeichnet wird. Ein weiteres Anwendungsgebiet der Matrix ist die Bestimmung der Fülleigenschaften von display.Graphics (BitmapFill, GradientFill, GradientStyle). Hier lässt sich mit der Matrix die Art der Füllung mit bestimmen.

Die Flash-Matrix ist grundsätzlich gesehen eine 3×3-Matrix:

Flash 3x3 Matrix

Für die oben beschriebenen Transformationen werden jedoch nur die oberen beiden Zeilen verwendet. Die Werte u = 0, v = 0 und w = 1 verhalten sich neutral. Diese untere Zeile wird nicht verwendet, da Flash nur im 2D-Raum operiert und die oben beschiebenen Werte werden somit vorausgesetzt. Dies bedeutet die Flash-Matrix sieht eigentlich so aus:

Flash 2x3 Matrix

Für die Verschiebung werden die tx und ty Eigenschaften verändert:

Flash Matrix Verschiebung

Für die Skalierung werden die Eigenschaften a (sx) und d (sy) verändert:

Flash Matrix Neigung

Bei der Rotation werden die vier Werte a, b, c und d verändert mit der folgenden Werteberechnung:
a -> cos(alpha)
b -> -sin(alpha)
c -> sin(alpha)
d -> cos(alpha)

Flash Matrix Rotation

Das Scheren, beziehungsweisen Neigen lässt sich mit den Eigenschaften b und c definieren:
b -> tan(neigungx)
c -> tan(neigungy)

Flash Matrix Neigung

Anwendungsbeispiel:

Anwendung findet die Matrix zum Beispiel beim „kopieren“ von Bildteilen. Nimmt man ein Bitmap als Ausgangsgrafik und will einen bestimmten Bereichen davon in ein anderes BitmapData-Objekt zeichnen, ist eine Matrix unerlässlich. Zunächst wird ein leeres BitmapData-Objekt erstellt, mit der Größe der zu kopierenden Fläche. Des Weiteren wird ein Rectangle-Objekt benötigt mit ebenfalls der selben Größe. In der nun zu erstellenden Matrix werden die tx und ty Eigenschaften auf den negativen Wert der Koordinaten des Punktes gesetzt, der die linke obere Ecke des zu kopierenden Bereiches darstellt. Mit dem folgenden Script wird nun der gewünschte Bereich in das neue BitmapData-Objekt gezeichnet:

clipBitmapData.draw(originalBitmapData, transformMatrix, null, null, clipRectangle);

Dieses Objekt kann nun als eigenständiges Objekt in Flash weiter verwendet werden.

Mehr zum Thema: Matrix in den LiveDocs

Ein kleiner Nachtrag:

Gelegentlich kann es vorkommen, dass man eine Matrix hat (zum Beispiel die TransformMatrix eines Objektes) und möchte daraus wiederum den Drehungwinkel berechnen. Und wie oben zu sehen ist, geht eine Rotation in der Matrix über die 4 Parameter a, b, c und d. Also nicht ganz einfach, wenn man die Berechnung von Hand bewerkstelligen will. Aber hier hat Adobe im fl.motion-Package ein kleine Helferklasse drin, die eben solche Probleme löst. So liefert die Funktion getRotation(m:Matrix) den gesuchten Rotationswinkel in Grad zurück. Aauch die anderen Transformationen können so ausgelesen werden.

Mehr dazu unter: MatrixTransformer