5 Implementation

5 Implementation

Um eine vergleichende Bewertung der verschiedenen Optimierungsstrategien durchzuführen, wurden sie modular in ein C-Programm implementiert. Die Steuerung des Optimierungsprogrammes erfolgte über eine sogenannte PCF-Datei (Program Control File). Mit Hilfe dieser Dateien können einem Programm sämtliche relevanten Parameter, wie Art der Strategie, Strategieparameter, Filterform, etc., übergeben werden. Ein Beispiel für eine PCF-Datei findet sich in Abschnitt 8 dieser Studienarbeit.

Für die Interpolation des Bildmaterials wurde der Faktor zwei gewählt, da sich mit diesem Wert die Implementation äußerst einfach gestaltet. Zudem lassen sich höhere Vergrößerungsfaktoren, die auf einem Vielfachen von zwei basieren, durch eine wiederholte Anwendung einer Interpolation mit dem Faktor zwei erzeugen.

5.1 Implementation der Filter

Zur Bewertung der Interpolationsergebnisse ist ein objektives Bewertungskriterium für die Bildqualität erforderlich, da eine subjektive Bewertung aufgrund des Aufwandes solcher Tests für Optimierungsläufe mit mehreren tausend Bewertungen nicht realisierbar ist. Der Peak Signal to Noise Ratio (PSNR) stellt ein solches objektives Maß für die Bildqualität dar. Um die Qualität der ermittelten Filterkoeffizienten zu beurteilen, wird das zu interpolierende Bild gefiltert und mit einem Referenzbild verglichen. Der PSNR errechnet sich durch folgende Gleichung [Schmidt96]:

Formel

bin und bref enthalten die Bildpunkte der xmax · ymax großen Bilder. Die Zahl 255 entspricht dabei dem größtmöglichen Luminanzwert. Das zu interpolierende Bild (bin) besteht aus jedem vierten Bildelement des Referenzbildes (bref). Dies entspricht einem Bild mit einem Viertel der Größe des Referenzbildes. Ein Beispiel dafür wird in Abbildung 5.1 gezeigt. Die fehlenden Bildpunkte des Eingangsbildes werden durch die interpolierende Filterung ergänzt. Der PSNR gibt das Signal-Rausch-Verhältnis zwischen Referenzbild und gefiltertem Bild wieder. Bei identischen Bildern ist das Verhältnis unendlich groß, da die Differenz zwischen beiden Bildern Null ist. Im Allgemeinen kann der PSNR keine negativen Werte annehmen, aber durch die Verwendung von zufälligen Startkoeffizienten bei der linearen Filterung können Luminanzwerte, welche die maximale Helligkeit überschreiten, so häufig auftreten, dass der Nenner in Gleichung (5.1) größer als der Zähler wird und sich somit ein negativer PSNR ergibt. Die Summe der Filterkoeffizienten sollte genau eins betragen, um die Gesamthelligkeit des Bildes auf dem gleichen Niveau zu halten. Wegen der zufälligen Startwerte werden aber Luminanzwerte erreicht, die weit über der darstellbaren Helligkeit liegen. Würden diese Werte auf die maximale Größe begrenzt (Clipping), könnten diese Konfigurationen nicht korrekt verglichen werden, da diese durch das Clipping mit hoher Wahrscheinlichkeit alle den minimalen PSNR 0 dB zugeordnet bekämen.


Referenzbild   zu interpolierendes Bild
Abbildung 5.1: Referenzbild und zu interpolierendes Bild

Der häufige Aufruf der Bewertungsfunktion mit der aufwendigen Filterung des Bildes verlangt nach einem optimierten Algorithmus dieser Funktion. (Der eigentliche Optimierungsvorgang Tausender Individuen dauert nur wenige Sekunden, während die Filterung und Bewertung der Individuen zusammen einige Stunden benötigen kann.) Für lineare Filter wird die symmetrische Filtermaske nach Abbildung 5.2 benutzt. Durch die Symmetrie werden die Filterkoeffizienten xi viermal verwendet, der zentrale Koeffizient x0 nur einmal und die auf den Nebendiagonalen liegenden Punkte sogar achtmal. Zur Berechnung eines neuen Bildpunktes werden die Werte an den Positionen des Fensters mit gleichem Index aufsummiert und mit dem entsprechenden Filterkoeffizienten multipliziert. Der neue Bildpunkt erhält die Summe dieser Werte. Auf diese Weise lässt sich die Anzahl der rechenaufwendigen Fließkommamultiplikationen reduzieren. Die Gesamtgröße g der Maske errechnet sich aus der Ausdehnung des symmetrischen Teils s in x-Richtung durch

g = (2 · s - 1)2 .

Filtermaske
Abbildung 5.2: Symmetrische Filtermaske

Die Filtermaske aus Abbildung 5.2 läßt sich nicht auf Medianfilter anwenden. Weil im Eingangsbild nur jeder vierte Bildpunkt gesetzt ist, bleiben die zu interpolierenden Punkte auch nach einer Medianfilterung unbesetzt. Daher müssen die Masken entsprechend angepaßt werden. Es werden nur diejenigen Bildpunkte zur Filterung verwendet, die auch im Eingangsbild vorhanden sind. Zur Filterung werden daher Filtermasken für drei verschiedene Richtungen benötigt: horizontal, vertikal und diagonal. Mit jeder Filterung werden Bildpunkte in der entsprechenden Richtung hinzugefügt. Das Filtern in unterschiedlichen Richtungen verdeutlicht Abbildung 5.3. Die vollständige Interpolation eines Bildes erfordert für jede verwendete Filterrichtung eine eigenständige Suche nach den optimalen Filterkoeffizienten.


Filterung
Abbildung 5.3: Filterung in unterschiedlichen Richtungen

Um Medianfilter mit ungerader Koeffizientenanzahl zu erzielen, ist es notwendig, den geradzahligen Filtermasken einen zusätzlichen Wert hinzuzufügen. Dazu wird aus den Punkten x1, die dem durch die Filterung zu erzeugenden Bildpunkt am nächsten liegen, ein Mittelwert gebildet und als zusätzlicher Filterkoeffizient x0 benutzt. Hierdurch erhöht sich die Dimension des Optimierungsproblems um eins. Dieser Mittelwert erhält die Gewichtung

2 · x0 + 1.

In den Abbildungen 5.4 bis 5.6 sind die verschiedenen Filtermasken mit einer Symmetriegröße von drei dargestellt. Dabei sind die nicht im zu interpolierenden Bild enthaltenen Punkte weiß gezeichnet und der durch die Filterung neu erzeugte Bildpunkt schraffiert. Die symmetrischen Komponenten der Masken sind jeweils stärker umrandet. Um den Optimierungsaufwand zu senken, sind die dargestellten Filtermasken nur näherungsweise symmetrisch. Für eine symmetrische Maske wären im abgebildeten Fall statt sechs neun Filterkoeffizienten erforderlich.


Filtermaske
Abbildung 5.4: Horizontale Filtermaske

Filtermaske
Abbildung 5.5: Vertikale Filtermaske

Filtermaske
Abbildung 5.6: Diagonale Filtermaske

Bei Testbildern, die maximal 256 Graustufen enthalten, kann die Medianfilterung erheblich beschleunigt werden. Dann ist der Einsatz der sogenannten Histogramm-Methode möglich. Mit ihrer Hilfe kann auf die aufwendige Sortierung der Eingangssequenzen verzichtet werden. Dieses Verfahren ist etwa fünf mal schneller als die Verwendung eines Quick-Sort-Algorithmus, einem der schnellsten bekannten Sortieralgorithmen. Die Histogramm-Methode benutzt ein Feld, welches für jeden möglichen Grauwert ein Element bereitstellt. Der Feldindex entspricht dabei dem jeweiligen Luminanzwert. Um eine Filterung durchzuführen, werden die zur Medianmaske gehörenden Grauwerte zur Adressierung des Feldes verwendet. Die Gewichtung wird dem jeweiligen Element, welches sich an der der Helligkeit entsprechenden Position befindet, hinzuaddiert. Der Median lässt sich bestimmen, indem das Feld solange durchlaufen wird, bis die Summe aller schon betrachteten Elemente größer oder gleich der Hälfte der Summe aller Gewichte ist.

Die für jede Richtung unterschiedlichen Filtermasken ergeben jeweils einen eigenen Filter. Diese Einzelfilter werden auch als Phase bezeichnet, so dass ein aus einzelnen Phasen zusammengesetzter Filter als Polyphasenfilter bezeichnet wird [Bremer97]. Wie die Abbildungen 5.4 bis 5.6 zeigen, können die Einzelfilter eines Polyphasenfilters unterschiedliche Längen besitzen. Polyphasenfilter können nicht nur als Medianfilter sondern auch als linearer Filter verwendet werden. Auch hierbei muss zur Erzeugung der einzelnen Masken jeweils ein kompletter Optimierungslauf gestartet werden.

5.2 Beweis der Unimodalität der Interpolation mit linearen Filtern

Ziel der Optimierung ist das Erreichen eines möglichst großen PSNR. Für die diagonale Filterung muss der Ausdruck

Formel

maximiert werden. In bdiag sind die aus den Eingangsbildpunkten bin in diagonaler Richtung interpolierten Pixel enthalten. bref,d beschreibt die entsprechenden Bildpunkte des Referenzbildes. Dies ist in Abbildung 5.7 dargestellt. Nach Zusammenfassung der Vorfaktoren erfolgt die Optimierung durch die Maximierung des Ausdrucks

Formel

Referenzbild
Abbildung 5.7: Referenzbild und interpoliertes Bild

Das gleiche Ziel wird durch die Minimierung von

Formel

erreicht.

Werden die Bildpunkte jeweils in Matrizen pdiag und pref,d eingetragen, so ergibt sich aus Gleichung (5.4)

Formel

Ein lineares FIR-Filter der Größe N × M in Polyphasendarstellung wird durch

Formel

beschrieben. h(ξ,η) gibt dabei die Impulsantwort des Interpolationsfilters an. Die Faltung ist auch als Matrix-Vektor-Produkt darstellbar. Dazu wird h nach [AndrewsHunt77] zeilenweise in einen Spaltenvektor eingetragen:

Formel

Eine Bildzeile des gefilterten Bildes lässt sich durch

Formel

beschreiben. Die Matrix [pin] ist eine Streifenband- oder Toeplitzmatrix, d. h. sowohl die untere linke Ecke als auch die obere rechte Ecke der Matrix sind unbesetzt. Mit

Formel

wird das gesamte gefilterte Bild als Spaltenvektor beschrieben:

Formel

wobei die Matrizen [Ps] die Größe (M + xmax - 1) × M besitzen und aus der s-ten Zeile der Matrix pin nach

Formel

gebildet werden.

Das Referenzbild der Größe (ymax + N - 1) × (xmax + M - 1) wird ebenfalls in einen Spaltenvektor eingelesen:

Formel

Damit beide Matrizen die gleiche Dimension bekommen, muss ggf. der Rand mit Nullen aufgefüllt werden. Dies ist in Abbildung 5.8 gezeigt.


Randbereich
Abbildung 5.8: Randbereich

Unter Verwendung der Euklidschen Norm

Formel

ergibt sich für das gesamte Bild der Ausdruck

Formel

welcher zu minimieren ist. Dieses Gleichungssystem ist überbestimmt, da wesentlich mehr Bildpunkte als Filterkoeffizienten vorhanden sind. Das Gleichungssystem

Formel

ist nach [GolubLoan96] im Sinne der "Least Squares" durch Bestimmung von

Formel

analytisch optimal lösbar. Damit ist bewiesen, dass die Interpolation mit linearen Filtern ein unimodales Problem darstellt.

Dies kann durch folgendes Beispiel veranschaulicht werden.

Für den dreidimensionalen Fall wird aus der Linearkombination von zwei Spaltenvektoren u und v eine Ebene E aufgespannt. Dies verdeutlicht Abbildung 5.7.


Ebene
Abbildung 5.9: Aus den Spaltenvektoren aufgespannte Ebene

Betrachtet wird ein überbestimmtes Gleichungssystem mit drei Gleichungen und zwei Variablen:

Formel

Der Zielpunkt des Vektors r liegt im allgemeinen nicht in der Ebene E, so dass keine exakte Lösung des Gleichungssystems möglich ist. Daher wird durch eine Linearkombination der Vektoren u und v ein Punkt P ermittelt, der den geringstmöglichen Abstand ||e|| zu r besitzt. Der Vektor e steht dabei orthogonal auf der Fläche, die durch die Vektoren aufgespannt wird (Projektion). Daraus ergibt sich

Formel

Aus

Formel

folgt

Formel

Mit

Formel

ergibt sich Gleichung (5.16).

5.3 Implementation der Optimierungsstrategien

Die einzelnen Optimierungsstrategien sind im Programm als Module realisiert. Sie erhalten ihre Strategieparameter aus dem Hauptprogramm und geben ihrerseits die beste von ihnen ermittelte Filterkonfiguration zurück.


Direkte Suchverfahren und Gradientenstrategie

Von den in Kapitel 4.1 beschriebenen diskreten direkten Suchverfahren wurde nur die erste Strategie, welche den Parameterraum in Richtung der Koordinatenachsen abtastet, implementiert, da sie die größte Effektivität bei geringstem Programmieraufwand versprach. Dieses diskrete Suchverfahren benötigt keine Strategieparameter. Es findet sein Ziel von einer zufälligen Startposition.

Im kontinuierlichen Fall wird die Schrittweite des Differenzenquotienten δ nach Gleichung (2.3) benötigt. Weiterhin kann die Schrittweite s und der Schrittweitenreduktionsfaktor r angegeben werden. Als letzter Parameter wird die Abbruchschrittweite ends verlangt.


Simulated Annealing

Zur Bestimmung des Optimums mit Hilfe des Simulated Annealing ist die Angabe der Starttemperatur T(0) und der Startstreuweite d(0) erforderlich. Sie geben den maximal erreichbaren Rahmen vor, in welchem Zufallswerte zur Bildung neuer Parameterkonfigurationen erzeugt werden. Der Abkühlungsfaktor α und der Streuweitenreduktionsfaktor β dienen zur Adaption der Schrittweite während des Suchprozesses. Die Variable N legt fest, nach wie vielen Schritten ohne Verbesserung der Zielfunktion das Equilibrium1 erreicht ist. Schließlich ist noch die Übergabe der unteren Grenze der Temperatur ε notwendig, mit deren Erreichen die Suche beendet wird.


Evolutionsstrategien

Die verwendeten (μ + λ)- und (μ , λ)-Evolutionsstrategien sind die aufwendigsten der untersuchten Optimierungsstrategien. Notwendige Parameter sind die Werte von μ und λ. Ein weiterer Parameter ist die Konstante τ, die nach Gleichung (2.6) zur Mutation der Streuwerte verwendet wird. Durch prek wird die Wahrscheinlichkeit der diskreten bzw. intermediäreren Rekombination angegeben.


Differential Evolution

Die Strategie der Differential Evolution erfordert eine eigene Routine zur Bildung ihrer Startvektoren. Während die anderen beschriebenen Optimierungsverfahren auch ohne die Wahl von zufälligen Startpunkten ihr Ziel erreichen2, müssen bei der Differential Evolution unterschiedliche Startwerte vorgegeben werden, da die Bildung neuer Individuen über die Addition eines Differenzvektors zweier vorhandener Vektoren zu einem anderen erfolgt. Daher sollten die Startvektoren über den Parameterraum gleichverteilt sein.

Als Strategieparameter werden die Angabe der Differential-Evolution-Strategie und der Crossover-Methode nach Kapitel 2.5.1 erwartet. Da wie bei den Evolutionsstrategien eine Population von verschiedenen Individuen benutzt wird, kann deren Größe NP angegeben werden. Ein weiterer Strategieparameter ist der in den Gleichungen (2.7) bis (2.11) verwendete Gewichtungsfaktor F. Als letzter Parameter kann die Crossover-Wahrscheinlichkeit CR zur binominalen Veränderung der Vektorkomponenten angegeben werden.


1 siehe Kapitel 2.3

2 Als Startpunkt kann beispielsweise ein linearer Tiefpassfilter angegeben werden, bei dem alle Koeffizienten denselben Wert haben (Moving Average).


Kapitel4 Zurück Kapitel6