Java-Applet: Affine Transformationen

 
 
 
 Für einwandfreie Funktion ist mindestens Netscape mit Java-Version 1.14 erforderlich.
 



1) Einleitung

Anwendungen für geometrische Transformationen gibt es viele, z.B. in der Vermessung von realen Objekten mittels digitaler Bilder. Die verwendeten CCD-Sensoren sind sehr präzis, so daß genaue Vermessungen möglich sind.

Um die Koordinaten des Originals in solche eines Bildes oder Modells umrechnen zu können, ist eine Abbildungsvorschrift erforderlich, die das gewünschte Resultat liefert. Dazu bedarf es eines mathematischen Modells, welches den geometrischen Zusammenhang (z.B. Projektion) zwischen Urbild und Bild definiert.

Mögliche Fragestellungen


Anforderungen an geometrische Transformationen

Allgemein soll eine geometrische Transformation Die Pixelkoordinaten von Urbild und Bild in Beziehung setzen. In vielen Fällen wird es darum gehen, die reale Welt in ein Pixelbild abzubilden. Dabei spielen Position, Größe, Abstand und relative Anordnungen (z.B. Parallelität) eine Rolle. Hat man z.B. photographisches Material zur Verfügung, so kann es wünschenswert sein, radiale Verzerrungen, die durch das Linsensystem zustande kommen (Fischaugeneffekt) zu beseitigen.

Der nächste Schritt ist oft eine Vergrößerung oder Verkleinerung. Dabei ist die Frage zu beantworten, wie hinzukommende Pixel aufgefüllt werden. Auch sollen relative Maße erhalten bleiben, was im Pixelbereich auf Grenzen stößt. Was die Genauigkeit technischer Bauelemente ermöglicht, soll nicht durch ungenaue Rechnungen in Frage gestellt werden.

Nachdem das Original in geeigneter Form abgebildet ist, z.B. mit einer Stereokamera in Form von zwei zweidimensionalen Pixelbildern, könnte daraus ein dreidimensionales Bild berechnet werden.

2) Vorwärts und rückwärts abbilden

Geometrische Transformationen sind Abbildungen von einer in eine andere Punktmenge.

Ein großes Problem entsteht durch die Tatsache, daß die Rasterungen von Urbild und Bild im allgemeinen nicht übereinstimmen. Es treten zwei Teilprobleme auf:

Sei f eine Abbildung zwischen zwei Pixelmengen, P und P' Pixel mit P Urbild, P' Bild. Dann gibt es zwei Möglichkeiten zur Vorgehensweise:

a) P' = f(P)

Wir nehmen die Urbildpixel und bilden sie auf das Bildraster ab. Im allgemeinen wird das Bildpixel P' irgendwo zwischen den Rasterpositionen liegen. Jetzt könnten wir P' dem am nächsten liegenden Pixel zuordnen. Es würden einige Pixel des Bildrasters unter Umständen gar nicht, andere mehrfach getroffen werden.


Das helle Muster im skalierten Bild entsteht durch den durchscheinenden Hintergrund an Stellen, wo Pixeln des Bildrasters kein Bild eines Urbildpixels zugeordnet wurde.

Besser wäre es, P' auf mehrere Pixel zu verteilen. Dies ist möglich, wenn wir jedes Pixel als Quadrat auffassen. Ein Pixel im Bildraster würde dann aus allen ihn überdeckenden Bildpixeln gemittelt, wobei als Gewicht der Überdeckungsanteil genommen würde. Es wäre eine relativ aufwendige Rechnung nötig.

Beide Methoden lösen nicht das Problem von Löchern im Bild.


a) P' = f(P) Das Bild des Urbildrasters (schräg gezeichnet) deckt sich nicht mit dem Bildraster. Die vier Pixel könnten zur Berechnung des Wertes des Bildpixels verwendet werden.
b) P = f -1 (P') Das Urbild des Pixels (schräg gezeichnet) berührt mehrere Urbildpixel.

b) P = f -1 (P')

Eine wesentlich bessere Methode ist, vom Bildraster auszugehen und für jedes Pixel P' den Ort im Urbildraster zu suchen, der durch die Abbildung f auf P' abgebildet wird. Es wird also für jedes Bildpixel das rechnerische Urbild ermitteln. Dazu wird die Umkehrabbildung f -1verwendet. Auf diese Weise können keine Löcher im Bild entstehen. Das Interpolationsproblem befindet sich nun im Urbild. Da die errechneten Punkte P = f -1 (P') zwischen den Pixeln des Urbildrasters liegen, muß ein Algorithmus ihnen einen sinnvollen Wert zuordnen. Dieses kann der Wert des am nächsten liegenden oder ein Mittelwert der benachbarten Pixelwerte sein, bzw. sich aus der Umgebung des Urbildpixels berechnen.

Skalierung unter Verwendung der Methode der Umkehrabbildung ohne Interpolation.

Es wird jeweils der Pixelwert des dem rechnerischen Urbild am nächsten liegenden Pixels verwendet.
Daher treten im Bild keine Löcher auf.


3) Lineare und affine Abbildungen

Faßt man einen Punkt P als Vektor v auf, so zählen zu den (bezüglich Vektoraddition und Multiplikation mit einem Skalar) linearen Abbildungen Rotation, Skalierung, Dehnung und Scherung. Die Translation ist nicht linear und gehört zusammen mit den linearen zu den affinen Transformationen.

Urbild Translation Skalierung
Dehnung Scherung Rotation

Für eine lineare Abbildung f, angewandt auf die Punkte P und Q und den Skalar k gilt also:

Für eine affine Abbildung g, einen Vektor T und P, Q, k wie oben gilt:

Affine Abbildungen haben eine Reihe von nützlichen Eigenschaften, wie z.B. Parallelität zu erhalten und können durch Matrizenrechnung berechnet werden.

3.1) Bildvektoren bestimmen

Lineare Abbildungen in Vektorräumen lassen sich durch Matrizenmultiplikation berechnen, für die Translation wird ein Vektor addiert. Für Punkte (x, y) im R² erhalten wir für eine affine Abbildung:

v' = M * v + T ,

wobei v Urbild, v' Bild , M im R² eine 2x2-Matrix der linearen Abbildung, T Translationsvektor,

oder genauer:

Diese Transformationen lassen sich auch mit nur einer Matrizenmultiplikation ausdrücken, wenn man zu homogenen Koordinaten übergeht.

Ein Punkt P im R² läßt sich durch genau einen Vektor v = (x, y) mit kartesischen Koordinaten darstellen. Bei Verwendung homogener Koordinaten wird eine Koordinate hinzugefügt. Ein Punkt entspricht dann einer ganzen Scharr von Vektoren v = k*(x ,y, 1). Wir verwenden den Repräsentanten (x, y, 1). Im R³ haben die Vektoren entsprechend eine Koordinate mehr.

Eine affine Abbildung läßt sich wie folgt berechnen:

v' = A * v ,

wobei v Urbild, v' Bild , A im R² eine 3x3-Matrix der affinen Abbildung

oder genauer:

a11, a12, a21, a22 bestimmen den linearen Anteil der Transformation, tx und ty die Translation.

Auf diese Weise läßt sich also das Bild berechnen, wenn Urbild und Transformationsmatrix gegeben sind.


Wie oben zu sehen, können mit diesem Applet verschiedene im Text erwähnte Funktionen im Zweidimensionalen ausgeführt werden.

Funktionalität:




3.2) Transformationsmatrix bestimmen

Für die Berechnung der Transformationsmatrix wird eine geometrische Eigenschaft affiner Abbildungen genutzt: Sie erhält nämlich die Parallelität. Parallelogramme werden auf Parallelogramme abgebildet und niemals auf beliebige Vierecke. Daher reichen drei Punkte in beliebiger Lage (nicht auf einer Geraden!) mit ihren Bildern, um eine affine Abbildung zu definieren. Diese drei Punkte dürfen nicht linear abhängig sein, d.h. nicht auf einer Geraden liegen. Die Gleichung v' = M * v muß für diese Punkte erfüllt sein, genauer, es wird M gesucht, so daß die Gleichung erfüllt ist. Für jeden Punkt ergeben sich drei Gleichungen.

Insgesamt läßt sich folgende Vektorgleichung aufschreiben:

X' = A * X ,

oder genauer

und auflösen nach : A = X' * X -1 .

Die inverse Abbildung läßt sich mit der inversen Matrix A -1 berechnen.

Bildung einer Inversen Matrix

Es gilt:

Für 3x3-Matrizen gilt:



4) Allgemeine Projektionen

Die Koeffizienten a31 und a32 bestimmen beliebige Projektionen. Für a31 oder a32 ungleich Null sind die Abbildungen nicht mehr affin, Parallelität muß nicht erhalten bleiben.

Allgemein lassen sich aus der Gleichung X' = A * X im Zweidimensionalen folgende Formeln für die Berechnung der Bildkoordinaten gewinnen:

Für affine Transformationen fällt der Nenner weg, da a31 und a32 dann immer Null sind.

Abbildungen dieser Art sind durch vier Punkte mit ihren Bildern bestimmt. (Es gilt aber: Nicht alle Abbildungen, die durch vier Punkte mit ihren Bildern gegeben sind, sind in homogenen Koordinaten mit einer 3x3-Matrix darstellbar!)

Abbildung mit der Matrix:

Parallelen bleiben nicht erhalten, dies ist keine affine Abbildung.
(Die Löcher im Bild stammen lediglich von der Vorwärts-Abbildung.)



5) Interpolation

Interpolation wird immer dann nötig, wenn die Rasterung von Urbild und Bild nicht übereinstimmen, also das rechnerische Ziel von Bildpunkten nicht genau mit der Rasterung im Bild übereinstimmt, Pixel nicht oder mehrfach getroffen werden. Im Idealfall sollte das Urbild sich wieder aus dem Bild rückrechnen lassen. Das ist nicht möglich. wenn Informationen durch ungeeignete Interpolationsverfahren verfälscht werden oder verloren gehen. Wird die Pixelzahl verringert, so kann natürlich eine Rückvergrößerung nicht das ursprüngliche Bild ergeben. Bei Vergrößerung müssen die zusätzlichen Pixel aufgefüllt werden, was zu einem Treppeneffekt führt. Die Rückrechnung des Urbildes wird immer nur näherungsweise möglich sein. Daher muß man sich vorher überlegen, welches Interpolationsverfahren den gewünschten Anforderungen am ehesten entspricht. Ausgehend von der diskreten Pixelstruktur eines Bildes entwirft man zunächst eine geeignete kontinuierliche Funktion, die dieser Grauwertverteilung möglichst nahe kommt, z.B. ein Polynom durch die gegebenen Punkte des Bildes. Diese Konvolutionsfunktion muß also Grauwerte aufgrund der Nachbarschaftsverhältnisse berechnen.

Seien x ein Punkt und xm,n einer aus der Umgebung von x. 'm', 'n' beziehen sich dabei auf die Position innerhalb des Filterkerns, angewendet auf x. G(xm,n) ist der Grauwert von xm,n:

H ist dabei der verwendete Filterkern, Gi(x) der resultierende Grauwert an der Stelle i.

Gehen wir davon aus daß der Filterkern H separierbar ist, so läßt er sich in eindimensionale Filterkerne zerlegen.

5.1) Interpolation mit Polynomen

Polynome n-ten Grades werden durch die gegebenen Punkte gelegt. Die Polynome stellen die Annäherung dar.

Ein höherer Grad gibt eine glattere Kurve, benötigt aber auch mehr Rechenzeit. Der einfachste Fall ist n=0. Hier werden überhaupt keine mittleren Werte berechnet, sondern die Werte der Stützstellen verwendet. Die "ausgleichende" Kurve besteht aus Konstanten und weist Sprünge auf, ist also nicht stetig. Diese Sprünge sind im Bild als Grauwertstufen zu sehen.

Bei Fall n=1 werden alle Punkte mit Geraden verbunden, wobei x=0 die zu interpolierende Stelle sei.

Sei dx der Abstand zweier benachbarter Punkte, so ergibt sich für -dx/2 < x < dx/2:

Für den Filterkern ergibt sich:

Die ausgleichende Kurve hat keine Sprünge aber Ecken an den Stützstellen, ist also stetig aber nicht differenzierbar. Das Bild ist im Vergleich zum vorigen Fall wesentlich weicher.

Ab n=2 werden Parabeln verwendet.


Für n = 0 findet keine Interpolation statt, die Punkte erhalten den Wert des nächsten Nachbarn.

Für n = 1 gibt es keine Sprünge, jedoch ist die Kurve in den Stützpunkten nicht stetig ableitbar.

Für n > 1 ergibt sich dann eine gebogene Kurve, bei erhöhtem Rechenaufwand.

Der Nachteil der Interpolation mit Polynomen ist, daß nicht alle Ableitungen stetig sind.


Vergrößerung um Faktor 4 mit Verwendung der nächsten Nachbarn.

Jeweils vier Pixel in einer Zeile erhalten den gleichen Wert, wodurch ein Treppeneffekt zustande kommt.

Vergrößerung um Faktor 4. Die Pixelwerte errechnen sich aus den Urbildpixeln mit ihren vier Nachbarn. Dabei wird eine Art linearer Interpolation verwendet, das arithmetische Mittel der Intensitäten der drei Farbbestandteile. Der Treppeneffekt wird deutlich geglättet. (Die Abstände zu den Nachbarn gehen in diesem Beispiel nicht ein.)


5.2) Interpolation mit B-Splines

Mit B-Splines ist es möglich, eine Interpolation herzustellen, die in allen Ableitungen stetig ist, was unter Umständen von Vorteil ist.

Ein B-Spline ist eine ausgleichendeKurve um vorgegebene Punkte Pi und berechnet sich als parametrisierte Kurve im Prinzip durch folgende Formel:

wobei t aus [0,1] und Bi(t) eine Gewichtung ist, die sich rekursiv berechnen läßt.

Die Bi(t) gehören einer zuvor zu definierenden Ordnung an, welche die Qualität der Interpolation bestimmt. Bei Ordnung 1 werden die Werte der Nachbarpixel übernommen. Ordnung 2 ist eine lineare Interpolation, d.h. die Punkte werden miteinander verbunden. Ab Ordnung 3 resultieren ausgleichende Kurven. Bei B-Spline-interpolierten Bildern werden ausreißende Grauwerte geglättet, da die Kurve nicht durch die Stützpunkte laufen muß.



B-Spline der Ordnung 4.

Ein Applet, das B-Splines erzeugt findet sich unter:

BsplineApplet.html.


6.1) Skalierung

Bei einer Verkleinerung sollten zuvor alle sehr feinen Details, die im Bild nicht mehr sichtbar sein dürfen, geglättet werden (z.B. mit B-Splines), da sie sonst gegebenenfalls übernommen werden (falls die Umkehrabbildung sie trifft). Da die Pixel im Urbild in der Regel nicht mit enen im Bild übereinstimmen, muß interpoliert werden.

Bei Verwendung eines Interpolationsfilters mit separierbaren, d.h. in eindimensionale Kerne zerlegbaren Filterkernen können zunächst alle Zeilen skaliert werden und dann erst die Spalten, was die Effizienz erhöht. Dazu können für jede Zeile dieselben Ortskoeffizienten genommen werden, was erheblich Rechenzeit spart.

Entsprechend werden im nächsten Schritt die Spalten skaliert.

Skaliertes Bild und ein Zeilenprofil:

a) Vergrößerung mit Interpolation der Ordnung 0, d.h. mit Übernahme der Nachbarpixel

b) Vergrößerung mit Interpolation der Ordnung 1, d.h. mit linearer Interpolation. (Verbinden der Pixelwerte durch Geraden)

c) Vergrößerung mit Interpolation der Ordnung 3, d.h. mit kubischer Interpolation (Polynome der Ordnung 3)

Bei Übernahme der Nachbarpixelwerte entstehen Stufen. Die Interpolationen 1. und 3. Ordrung sind kaum zu unterscheiden.

6.2) Rotation

Auch hier kann die Verwendung separierbarer Filterkerne die Effizienz steigern. Denn sie ermöglichen, eindimensionale Operationen anzuwenden.

Eine Rotation ist zwar mit einer einzigen Matrizenmultiplikation möglich, dabei werden jedoch Zeilen und Spalten zugleich transformiert. Es ist jedoch möglich, diese Operation mit einer Reihe eindimensionaler Transformationen auszuführen, um sie mit den eindimensionalen Filteroperationen koppeln zu können. Dazu kann man sich dreier Scherungen bedienen:

Scherungen können effizient zeilenweise ausgeführt werden, da wie bei der Skalierung für jede Zeile die selben Koeffizienten verwendet werden können.



6.3) Beliebige affine Abbildungen

Jede lineare Abbildung kann mit einer 2x2-Matrix dargestellt werden und ist in Skalierung, Scherung und Rotation zerlegbar.

Die Rotation kann wie oben beschrieben zerlegt werden. Die Skalierungsparameter sx und sy, der Scherungsparameter s, sowie der Rotationswinkel können wie folgt berechnet werden:

Für eine effiziente affine Transformation sind also maximal drei Operationen für den Rotationsanteil, je eine für Skalierung und Scherung und zusätzlich eine für Translation erforderlich. Jede dieser einfachen zweidimensionalen Operationen wird mit dem Interpolationsfilter gekoppelt.

Effiziente Rotation zusammengesetzt aus drei Scherungen.