6 Simulationsergebnisse

6.3 Simulation mit Medianfiltern

Auch für die Simulationen mit Medianfiltern wurde das Testbild "Lena" verwendet. Für ein 5 × 5-Filter kamen die Masken aus Abbildung 5.4 bis 5.6 zum Einsatz. Aufgrund des höheren Aufwands bei großen Medianmasken und den relativ schlechten Ergebnissen bei der linearen Filterung wurde als größere Filtermaske statt einer 9 × 9-Matrix eine 7 × 7-Matrix eingesetzt. Durch die zusätzlich erforderliche Mittelpunktberechnung ergaben sich sieben bzw. elf frei wählbare Filterkoeffizienten. Da die Filterung gemäß einem Polyphasenansatz für jede der drei Filterrichtungen neu durchgeführt wurde, gab es drei individuelle Bewertungsfunktionen. Nach der Interpolation wurde der gesamte PSNR des Bildes bestimmt.

6.3.1 Gradientenstrategie

Die Gradientenstrategie hat außer der Anzahl der zu verwendenden Filterkoeffizienten keine einstellbaren Parameter. Ein Durchlauf mit sieben freien Koeffizienten benötigte 11 Minuten, mit 11 Koeffizienten 32 Minuten. Die Simulation mit der kleineren Filtermaske war nach fünf Schritten in horizontaler, 47 in vertikaler und 36 in diagonaler Richtung abgeschlossen. Im Gegensatz zur linearen Filterung, die 9480 Schritte benötigte, sind die hier erforderlichen 88 Schritte sehr wenig. Die Simulationsergebnisse sind in Tabelle 6.6 aufgeführt.


freie KoeffizientenPSNR /dB
gesamt
PSNR /dB
horizontal
PSNR / dB
vertikal
PSNR /dB
diagonal
Σ Schritte
729,78128,45529,54827,77388
1128,39326,34226,66728,809156
Tabelle 6.6: Ergebnisse der Gradientenstrategie

Stellvertretend ist der Verlauf der vertikalen Medianfilterung in Abbildung 6.16 aufgezeichnet. Die Kurve verläuft nahezu linear und steigt zum Ende etwas steiler an. Auffällig ist der hohe Startwert von über 26 dB, der schon von den zufällig ausgewählten Startkoeffizienten erzielt wurde.


Verlauf
Abbildung 6.16: Verlauf der Gradientenstrategie mit 7 freien Koeffizienten in vertikaler Richtung

6.3.2 Simulated Annealing

Die Ergebnisse aller sieben getesteten Parameterkonfigurationen des Simulated Annealing lagen sehr dicht beieinander. Die beste Strategie erreichte 32,968 dB, die schlechteste 32,822 dB. Dazu wurden für alle drei Filterrichtungen zusammen zwischen 950 und 5850 Schritte benötigt. Ein Programmdurchlauf benötigte je nach erforderlicher Schrittanzahl zwischen 15 und 55 Minuten. Zwischen den interpolierten Bildern waren keine Unterschiede erkennbar. Sie unterschieden sich nur in einzelnen Bildpunkten. Die PSNR-Werte, die in den einzelnen Filterrichtungen erreicht wurden, sind in Tabelle 6.7 aufgelistet.


PSNR /dB gesamtPSNR / dB horizontalPSNR / dB vertikalPSNR / dB diagonal
32,96831,10034,03830,714
Tabelle 6.7: Ergebnisse des Simulated Annealing, 7 freie Koeffizienten, dk = 0,2, α = β = 0,95

Dabei sind die erreichten Ergebnisse von den eingestellten Strategieparametern praktisch unabhängig. So wurde der beste Wert mit 11 freien Koeffizienten und einem Startstreuwert dk = 0,2 erreicht, während der schlechteste Wert mit 7 Koeffizienten und einem dk von 0,5 erreicht wurde.

Abbildung 6.17 zeigt den Verlauf der erfolgreichsten Simulation mit dk = 0,2, α = β = 0,95 für alle drei Filterrichtungen. Auch bei dieser Optimierungsstrategie sind die hohen Startwerte auffällig.


Verlauf
Abbildung 6.17: Verlauf des Simulated Annealing, 7 freie Koeffizienten, dk = 0,2, α = β = 0,95

6.3.3 Evolutionsstrategien

Die Optimierungsläufe wurden für jede Richtung mit jeweils 5000 Individuen durchge-führt. Für die (μ , λ)- und (μ + λ)-Strategien wurden jeweils zehn Simulationen mit unterschiedlichen μ, λ und τ-Werten durchgeführt. Eine Simulation dauerte je nach Größe der Filtermaske zwischen zwei und drei Stunden. Wie beim Simulated Annealing lagen auch hier die Ergebnisse sehr dicht beieinander. Der niedrigste PSNR wurde von einer (15,100)-Strategie mit einer Mutationskonstanten τ = 0,1 und 11 Koeffizienten mit 30,804 dB erreicht. Der höchste Wert der Bewertungsfunktion von 32,968 dB wurde sowohl von der (15,100)- als auch von der (15+100)-Strategie mit einem τ = 0,3 bei 7 freien Koeffizienten erzielt. Alle anderen Strategien erreichten, von drei Ausnahmen abgesehen, Werte größer als 32 dB. Es wurden dieselben PSNR-Werte für die einzelnen Filterrichtungen erzielt wie die in Tabelle 6.6 abgebildeten des Simulated Annealing.

In Abbildung 6.18 ist der Optimierungsverlauf der (15,100)-Strategie mit τ = 0,3 für die vertikale Filterung dargestellt. Die obere Kurve gibt den Verlauf des besten Individuums, die mittlere den des Mittelwerts und die untere den des schlechtesten Individuums an. Nach etwa 20 Generationen bzw. 2000 überprüften Individuen ist der optimale Wert erreicht.


Verlauf
Abbildung 6.18: Optimierungsverlauf der (15,100)-Strategie, 7 freie Koeffizienten, τ = 0,3

6.3.4 Differential Evolution

Wie bei den Evolutionsstrategien wurden auch bei der Differential Evolution jeweils 5000 Individuen pro Filterrichtung verwendet. Es wurde jede der fünf Methoden zu Individuengenerierung2 mit den Standardwerten des Gewichtungsfaktors F = 0,95 und der Crossover-Wahrscheinlichkeit CR = 1 überprüft. Die Populationsgröße NP betrug 100 Individuen. Desweiteren wurden einige DE/best/1- und DE/rand-to-best-Strategien mit Werten für CR aus dem Intervall 0,4 bis 1,0 und für F aus dem Intervall 0,75 bis 0,95 getestet. Alle untersuchten Differential-Evolution-Strategien erzielten den selben Wert der Zielfunktion von 32,968 dB für das gesamten Filter und 31,1 dB für die horizontale Filterung, 34,038 dB für die vertikale Filterung und 30,714 dB für die diagonale Filterung. Diese Werte wurden unabhängig von der gewählten Strategie und den verwendeten Strategieparametern erzeugt. Auch eine Änderung der Populationsgröße von NP =100 auf NP = 150 Individuen und die Wahl unterschiedlicher Crossover-Strategien führte zu demselben Ergebnis, welches auch vom Simulated Annealing und den Evolutionsstrategien erreicht wurde.

Abbildung 6.19 zeigt den Verlauf der DE/best/1-Strategie. Es sind die besten und schlechtesten Individuen einer jeweiligen Generation aufgetragen. Der Zielwert wird nach etwa zehn Generationen erreicht. Die Werte des schlechtesten Individuums und des in der Abbildung nicht dargestellten Mittelwerts der Generation nähern sich dem Maximum nur langsam und erreichen es im Gegensatz zur linearen Filterung nicht.


Verlauf
Abbildung 6.19: Verlauf der DE/best/1-Strategie, 7 freie Koeffizienten, Crossover = binominal, NP =100, F = 0,75, CR = 1

6.3.5 Vergleich der Simulationsergebnisse bei Medianfilterung

Die Optimierungsverfahren erreichten mit der Medianfilterung deutlich bessere Ergebnisse als mit linearen Filtern. Durch den Polyphasenansatz erfolgt die Optimierung bei jedem Durchlauf nur in eine Filterrichtung, so daß sich die Komplexität des Problems reduziert.

Die Endwerte der Bewertungsfunktion werden bei der Medianfilterung nach erheblich weniger untersuchten Individuen gefunden. Das ist auf den diskreten und damit wesentlich kleineren Parameterraum zurückzuführen.

Tabelle 6.8 zeigt die Gewichtungen einiger 5 × 5 Medianmasken, die durch die einzelnen Optimierungsverfahren erzeugt wurden. Es sind jeweils die Koeffizienten für die horizontale (→), vertikale (↓) und diagonale Filterrichtung (→↓) angegeben. Mit Ausnahme der Gradientenstrategie erreichte jeweils mindestens eine Parameterkonfiguration des jeweiligen Optimierungsverfahrens den besten Wert von 32,968 dB. Trotz gleichen PSNR-Wertes unterscheiden sich die ermittelten Filtermasken stark. Dies erklärt sich durch die Multimodalität dieses Optimierungsproblems.


OptimierungsverfahrenPSNR / dB  x0  x1  x2  x3  x4  x5  x6 PSNR / dB
Gradientenstrategie29,78125132617111028,455
2617119222029,584
→↓138721826027,773
Simulated Annealing32,968100000031,100
150000034,038
→↓150000030,714
(15,100)-Strategie32,96828102242131,100
26173031234,038
→↓20240010030,714
DE/best/132,96830300000031,100
30300000034,038
→↓28300000030,714
Tabelle 6.7: Durch Medianfilterung ermittelte Filterkoeffizienten

Bei der Evolutionsstrategie wurden für die zentralen Medianwerte x0 und x1 sehr hohe Gewichtungen ermittelt, während den weiteren Koeffizienten nur eine niedrige Gewichtung zukommt. Dieser Effekt tritt bei der Differential Evolution noch stärker hervor. Hier erhalten beide Zentralwerte die maximale Gewichtung von 30. Auch beim Simulated Annealing ist nur die Mitte der Filtermaske mit Gewichtungen versehen. Aber hier sind die Werte niedriger, in horizontaler Filterrichtung wird sogar nur der zentrale Wert mit einfacher Gewichtung verwendet. Die durch die Gradientenstrategie ermittelten Filterkoeffizienten weisen eine geringere Ausprägung der Filtermitte auf.

Es lassen sich also nur mit Hilfe der Nachbarpunkte des durch die Interpolation zu bildenden Pixels sehr gute Ergebnisse erzielen. Der zusätzliche Zentralwert der Medianmaske x0 wird durch Mittelung aus den zwei bzw. vier ihn umgebenden Punkten x1 erzeugt.

In den Abbildungen 6.20 und 6.21 sind als Beispiel die durch das Simulated Annealing und durch eine (15,100)-Strategie ermittelten vertikalen Filtermasken dargestellt. Abbildung 6.22 zeigt abschließend das durch die DE/best/1-Strategie ermittelte interpolierte Motiv.


Filtermaske
Abbildung 6.20: Durch Simulated Annealing ermittelte vertikale Filtermaske

Filtermaske
Abbildung 6.21: Durch (15,100)-Strategie ermittelte vertikale Filtermaske

Lena Median
Abbildung 6.22: Mittels Medianfilterung interpoliertes Bild

6.4 Simulation mit linearen Polyphasenfiltern

Aufgrund der Reduktion der freien Parameter durch den Polyphasenansatz wurden die bei der Medianfilterung verwendeten Masken auch auf lineare Filter angewendet. Da bei der uniformen Filtermaske eine gleichzeitige Optimierung dreier verschachtelter Filtermasken erfolgt, sind mit unterschiedlichen Filtermasken wegen der Separierung des Problems bessere Ergebnisse zu erwarten. Der Zeitaufwand wird aber durch die dreifache Filterung erhöht. Es wurden wieder die gleichen Masken der Größe 5 × 5 und 9 × 9 aus den Abbildungen 5.4 bis 5.6 auf das Motiv "Lena" angewendet. Dabei wurde aber von einer zusätzlichen Berechnung des Mittelpunktes abgesehen, so daß wieder 6 bzw. 15 frei wählbare Filterkoeffizienten auftraten.

6.4.1 Gradientenstrategie

Die Gradientenstrategien wurden mit einer Startschrittweite s = 0,5 und einem Differenzenquotienten δ = 0,0005 durchgeführt. Die Resultate der Simulationen sind in Tabelle 6.9 aufgeführt. Der Simulationslauf mit 6 freien Koeffizienten benötigte für die horizontale Filterung 7270 Schritte, in vertikaler 7860 und in diagonaler 9330. Er dauerte etwa 4 Stunden und 30 Minuten.


freie KoeffizientenPSNR / dB
gesamt
PSNR / dB
horizontal
PSNR / dB
vertikal
PSNR / dB
diagonal
Σ Schritte
632,53230,41533,37330,76524460
1531,12329,04930,73730,08126110
Tabelle 6.9: Ergebnisse der Gradientenstrategie

Abbildung 6.23 zeigt den Verlauf der Optimierung mit 15 freien Koeffizienten für jede der drei Filterrichtungen. Die zum Ende der Optimierung kleiner werdenden Treppenstufen entstehen durch die Adaptierung der Schrittweite.


Verlauf
Abbildung 6.23: Verlauf der Gradientenstrategie mit 15 freien Koeffizienten

6.4.2 Simulated Annealing

Für das Simulated Annealing wurde eine Starttemperatur T = 10 und ein Wert zum Erreichen des Equilibriums von N = 10 gewählt. Die Abbruchtemperatur ε betrug 0,00001. Tabelle 6.10 zeigt die Ergebnisse der durchgeführten Simulationen. Die Anzahl der Schritte ergibt sich aus der Summe aller drei Filterungen. Im Gegensatz zur Gradientenstrategie sind die hier erreichten Werte niedriger als bei der Medianfilterung.


freie KoeffizientendkαβΣ SchrittePSNR / dB
60,10,850,851225023,941
0,20,850,85600026,125
0,20,950,951975029,674
0,50,950,951740018,984
150,20,950,951870022,841
0,50,950,952545015,208
Tabelle 6.10: Ergebnisse des Simulated Annealing

Die folgende Abbildung 6.24 zeigt den Optimierungsverlauf der erfolgreichsten Parameterkonfiguration. Die drei Kurven steigen zunächst extrem stark an, verharren dann aber auf einem fast konstanten Niveau.


Verlauf
Abbildung 6.24: Verlauf des Simulated Annealing mit 6 freien Koeffizienten, T = 10, dk = 0,2, α = 0,95, β = 0,95, N = 10, ε = 0,00001

6.4.3 Evolutionsstrategien

Die Evolutionsstrategien wurden mit den gleichen Strategieparametern für μ und λ getestet wie mit den einfachen linearen Filtern. Es wurden je Richtung 20000 Individuen verwendet. Ein Simulationslauf mit sechs Koeffizienten benötigte etwa 2 h 45 min. Um den Zeitaufwand zu reduzieren wurde die Auswahl der Mutationskonstante τ auf 0,01 beschränkt.

(μ , λ)-Strategie

Die Simulationsergebnisse der (μ , λ)-Strategie sind in Tabelle 6.11 aufgelistet. Wie bei der linearen Filterung erreichen die größeren Filtermasken nur deutlich niedrigere Werte des PSNR.


μλfreie
Koeffizienten
PSNR / dB μλfreie
Koeffizienten
PSNR / dB
10100631,41510200630,312
1526,5741524,294
15100631,33520100630,120
1527,8531526,172
Tabelle 6.11: Ergebnisse der (μ , λ)-Strategie

In Abbildung 6.25 ist der Verlauf der (15,100)-Strategie aufgezeichnet. Die obere Kurve gibt die Entwicklung des besten Individuums, die mittlere die des Mittelwerts und die untere die des schlechtesten Individuums einer Generation an. Nach einem sehr steilen Anstieg flacht der Verlauf des besten Individuums ab. Der Mittelwert folgt der Kurve in einigem Abstand, während der schlechteste Wert unter starken Schwankungen leicht ansteigt.


Verlauf
Abbildung 6.25: Verlauf der (15,100)-Strategie in horizontaler Richtung mit 6 freien Koeffizienten

(μ + λ)-Strategie

Tabelle 6.12 zeigt die Resultate der (μ + λ)-Strategie. Die PSNR-Werte liegen unterhalb der durch die (μ λ, )-Strategie ermittelten Werte. Ebenso wie bei der linearen Filterung aus Kapitel 6.2.3 erreichten einige Strategien nur niedrige Werte. Die höchste Güte konnte auch hier von der (10,200)-Strategie erzielt werden. Sie liegt zwar um 2 dB oberhalb des Resultats der einfachen linearen Filterung aber deutlich unterhalb des Bestwertes der (μ , λ)-Strategie.


μλfreie
Koeffizienten
PSNR / dB μλfreie
Koeffizienten
PSNR / dB
10100614,21610200628,332
1511,5651525,130
15100617,13620100627,178
1511,7241511,799
Tabelle 6.12: Ergebnisse der (μ + λ)-Strategie

6.4.4 Differential Evolution

Wie bei den Evolutionsstrategien wurden 20000 Individuen pro Filterrichtung verwendet. Aufgrund der Ergebnisse aus Kapitel 6.2.4 wurde für den Gewichtungsfaktor F der Wert 0,95 und für die Crossover-Wahrscheinlichkeit CR der Wert 1,0 gewählt. Auch hierbei wurde eine Populationsgröße NP =100 Individuen verwendet. Die Ergebnisse der Simulationen sind in Tabelle 6.13 aufgeführt. Es bestätigen sich die Resultate der einfachen linearen Filterung. Während die DE/best/2- und DE/rand/2-Strategien genauso wie die großen Filtermasken mit 15 freien Koeffizienten und den verwendeten Strategieparametern nur schlechte Ergebnisse liefern konnten, erreichten die DE/best/1- und DE/rand-to-best-Strategien annähernd gleich gute Werte. Das Ergebnis der DE/rand/1-Strategie lag um einige dB darunter. Der PSNR von 33,31 dB der DE/rand-to-best-Strategie war der höchste aller durchgeführten Simulationen.


DE-Strategiefreie
Koeffizienten
PSNR / dB
DE/best/1633,309
DE/rand/1630,591
1510,341
DE/rand-to-best633,310
1516,432
DE/best/2614,252
DE/rand/2610,698
Tabelle 6.13: Ergebnisse der Differential Evolution, F = 0,95, CR = 1

Weitere Simulationen zeigten, daß sich durch eine Kombination aus einer größeren Population und einer Erhöhung der maximal zu überprüfenden Individuen die Qualität der 9 × 9-Filtermasken wesentlich steigern läßt. So erhöhte sich der PSNR eines mit einer diagonalen Maske gefilterten Bildes bei einer Populationsgröße von NP = 200 Individuen und 50000 getesteten Individuen von 3,878 dB auf 26,278 dB. Nach 100000 überprüften Individuen pro Filterrichtung wurde ein Gesamt-PSNR von 32,073 dB erreicht, der aber dennoch unterhalb des von der Gradientenstrategie mit sechs freien Koeffizienten erzielten Wertes liegt.

Abbildung 6.26 stellt den Verlauf der DE/best/1-Strategie mit sechs freien Koeffizienten für eine Filterung in vertikaler Richtung dar. Es zeigt sich ein ähnliches Verhalten wie bei dem in Abbildung 6.9 gezeichneten Graphen für die einfache lineare Filterung.


Verlauf
Abbildung 6.26: Verlauf der DE/best/1-Strategie in vertikaler Richtung, 6 freie Koeffizienten, Crossover = binominal, NP = 100, F = 0,95, CR =1

6.4.5 Vergleich der Simulationsergebnisse bei linearer Polyphasenfilterung

Die mit linearen Polyphasenfiltern gewonnen Simulationsergebnisse sind zwischen 5 und 6 dB besser als die durch einfache Filtermasken erhaltenen Werte. Die besten PSNR-Werte der Differential Evolution lagen sogar etwas oberhalb der durch Medianfilter erzielten Werte, während die Resultate des Simulated Annealing und der Evolutionsstrategien um ein bis zwei dB darunter lagen.

Tabelle 6.14 zeigt die durch einige Optimierungsstrategien für die jeweilige Filterrichtung ermittelten Filterkoeffizienten. Es zeigt sich ein ähnliches Bild wie bei den anderen zuvor erzeugten Filtermasken. Auch hier erhielten die mittleren Koeffizienten x0 und x1 die stärkste Gewichtung. Wie erwartet wurde von den Optimierungsstrategien für jede Filterrichtung eine individuelle Matrix ermittelt. Trotz ähnlich hoher Gesamtergebnisse liefern die Optimierungsverfahren sehr unterschiedliche Masken.


OptimierungsverfahrenPSNR / dB  x0  x1  x2  x3  x4  x5 PSNR / dB
Gradientenstrategie32,5320,350,12-0,03-0,080,000,0126,738
0,440,05-0,03-0,02-0,000,0130,737
→↓0,31-0,01-0,02-0,07-0,030,0530,081
Simulated Annealing29,6740,240,040,09-0,08-0,010,0827,638
0,180,050,010,260,03-0,1227,841
→↓0,35-0,09-0,000,02-0,110,0830,368
(15,100)-Strategie31,3350,340,08-0,04-0,03-0,030,0430,046
0,180,11-0,040,050,05-0,0430,699
→↓0,230,06-0,03-0,04-0,000,0029,630
DE/best/133,3090,57-0,000,01-0,05-0,000,0131,408
0,55-0,02-0,00-0,00-0,00-0,0034,299
→↓0,34-0,060,01-0,000,000,0031,209
Tabelle 6.14: Durch Polyphasenfilter ermittelte Filterkoeffizienten

6.4.6 Vergleich der Simulationsergebnisse mit Fensterentwurfsverfahren

Zum Vergleich wurden mehrere Filterentwürfe mit Fenstersequenzen durchgeführt. Es wurden jeweils zwei separierte Filter unterschiedlicher Größe in diagonaler Richtung mit den auf die Abtastfrequenz normierten Grenzfrequenzen fgh / fs = ¼√2 und fgh / fs = ¼ erstellt. Die Ergebnisse für die Testbilder "Lena" und "Barbara" sind in Tabelle 6.15 aufgelistet.

Zur Unterdrückung des Alias ist eine niedrigere Grenzfrequenz fg vorteilhaft. Da die Flanken des Filters nicht unendlich steil sein können, wird das Signal schon bei Frequenzen unterhalb der Grenzfrequenz gedämpft. Dies läßt sich durch eine größere Anzahl von Filterkoeffizienten oder wie beim Bild "Lena", welches "weichere" Strukturen enthält, durch Wahl einer höheren Grenzfrequenz vermeiden.


Entwurfsverfahrenfg / fsfreie KoeffizientenPSNR / dB
"Lena"
PSNR /dB
"Barbara"
Rechteckfenster¼629,14823,112
¼√228,87321,016
¼1528,95722,961
¼√230,69321,631
Kaiserfenster
(β = 2.0)
¼629,06723,064
¼√230,87321,873
¼1529,16323,080
¼√230,91621,792
DE/best/1631,20923,685
Gradientens.1530,08123,780
Tabelle 6.15: Ergebnisse separierter Filter in diagonaler Richtung

In den Abbildungen 6.27 und 6.28 sind die durch eine Kaiserfenstersequenz mit fg / fs = ½√2 und eine DE/best/1-Strategie ermittelten diagonalen Filtermasken mit sechs freien Koeffizienten dargestellt. Im Gegensatz zu den Abbildungen 6.20 und 6.21 sind nur die Filterkoeffizienten ohne die Zwischenräume abgebildet.


0,0010,001-0,022-0,0220,0010,001
0,0010,001-0,018-0,0180,0010,001
-0,022-0,0180,3250,325-0,018-0,022
-0,022-0,0180,3250,325-0,018-0,022
0,0010,001-0,018-0,0180,0010,001
0,0010,001-0,022-0,0220,0010,001
Abbildung 6.27: Durch eine Kaiserfenstersequenz ermittelte diagonale Filtermaske
(PSNR 30,873 dB)

-0,0020,0020,0080,0080,002-0,002
0,0020,008-0,057-0,0570,0080,002
0,008-0,0570,3380,338-0,0570,008
0,008-0,0570,3380,338-0,0570,008
0,0020,008-0,057-0,0570,0080,002
-0,0020,0020,0080,0080,002-0,002
Abbildung 6.28: Durch eine DE/best/1-Strategie ermittelte diagonale Filtermaske
(PSNR 31,209 dB)

6.5 Zusammenfassung der Ergebnisse

Tabelle 6.16 zeigt einen zusammenfassenden Überblick der verwendeten Optimierungsstrategien. Es werden die Anzahl der Aufrufe der Bewertungsfunktion, die Höhe des erreichten PSNR, das Verhalten des Optimierungsverfahrens auf unterschiedliche Strategieparameter und der Verlauf des PSNR während der Optimierung miteinander verglichen. Betrachtet wird der Filterentwurf mit sechs freien Filterkoeffizienten

FilterOptimierungsverfahrenBewertungen*PSNR / dBParameterempfindlichkeitAnstieg des PSNR
linearGradientenstrategie5700026,815entfälltflach
Simulated Annealing1450024,068niedrigsehr steil, dann eben
Evolutionsstrategien2000026,475großsteil, dann flach
Differential Evolution2000026,834niedrig**mittel, dann flach
medianGradientenstrategie63029,781entfälltflach
Simulated Annealing585032,968keinemittel
Evolutionsstrategien1500032,968niedrigsteil
Differential Evolution15000232,968keinesteil
linear
polyphasen
Gradientenstrategie14700032,532entfälltflach
Simulated Annealing1975029,674mittelsehr steil, dann eben
Evolutionsstrategien6000031,335großsehr steil, dann flach
Differential Evolution6000033,309niedrigmittel, dann flach
* bei Medianfilterung und Polyphasenfilter: Summe aller drei Filterrichtungen
** bei Wahl von CR = 1
Tabelle 6.16: Übersicht der Optimierungsverfahren

Das sehr gute Ergebnis der Gradientenstrategie ist ein Hinweis darauf, daß es sich bei der Interpolation durch lineare Filterung um ein unimodales, wenn auch sehr komplexes, Optimierungsproblem handelt. Trotz ihrer guten Resultate empfiehlt sich der Einsatz der Gradientenstrategie nicht, da sie nur bei unimodalen Optimierungsproblemen eine optimale Lösung erzielen kann. Bei höherdimensionalen Optimierungsproblemen steigt die Laufzeit stark an, weil zur Gradientenbildung ein Tastschritt in jede Dimension des Parameterraums erforderlich ist. Da es sich bei der Medianfilterung um ein multimodales Problem handelt, kann die Gradientenstrategie konvergieren und dann in diesem Nebenminimum keine optimalen Ergebnisse ermitteln. Daher erreichte sie als einzige Strategie den von den anderen getesteten Verfahren erzielten PSNR nicht.

Das Simulated Annealing erzielte bei der linearen Filterung die niedrigsten Werte aller Verfahren. Seine Bestwerte lagen mehr als 2 dB unter den Werten der anderen Optimierungsverfahren. Die Laufzeiten hingegen waren sehr kurz. Nach einigen hundert Optimierungsschritten lag die Qualität des interpolierten Bildes nur noch wenig unterhalb der endgültig erreichten. Der Optimierungsprozeß könnte durch eine höhere Abbruchtemperatur ε und damit einem früheren Simulationsende bei kaum verminderter Güte weiter beschleunigt werden. Auch bei der Interpolation mit Medianfiltern wird der Zielwert sehr schnell erreicht. Die ermittelten Mediangewichtungen (Tabelle 6.8) sind äußerst klein, so daß sich die erzeugten Filter auch leicht in einer Hardware implementieren ließen. Die Interpolationsergebnisse sind, abgesehen von der linearen Polyphasenfilterung, nahezu unabhängig von der Wahl der Strategieparameter.

Außer bei dem Entwurf von Medianfiltern erreichten die Evolutionsstrategien nur mäßige Ergebnisse. Trotz ihres aufwendigen Algorithmus waren die Resultate bei linearen Filtern schlechter als die der Gradientenstrategie. Zudem reagierten sie nicht vorhersagbar auf Änderungen der Strategieparameter. Eine Erhöhung der Mutationskonstante τ konnte je nach Strategie sowohl eine Verbesserung als auch eine Verschlechterung des PSNR bewirken. Als erfolgreichste Strategien erwiesen sich die (10,200)- und (10+200)-Strategien. Die doppelt so große Population enthält eine höhere Vielfalt an Individuen, somit steht für die Selektion ein größerer "Genpool" zur Verfügung. Der PSNR stieg in den überprüften Fällen mit linearen Filtern bis zur letzten überprüften Generation an, wie Abbildung 6.7 zeigt, daher können durch eine höhere Generationszahl bessere Resultate erzielt werden. Die Medianfilterung hingegen erzielte schon nach 20 Generationen ihren optimalen Wert, so daß sich hier eine niedrigere Zahl von Generationen empfiehlt.

Das Differential-Evolution-Verfahren lieferte für alle drei verwendeten Filter die besten Resultate. Als geeignetste Strategien erwiesen sich die DE/best/1- und DE/best-to-rand-Strategie. Sie ermittelten bei linearer Filterung annähernd gleich gute Werte. Für die größeren Filtermasken erwies sich die Differential Evolution jedoch als weniger geeignet. Ebenso konnten die DE/best/2- und DE/rand/2-Strategien nur äußert schlechte Filter generieren. Bei einer Wahl der Crossover-Wahrscheinlichkeit von CR = 1 zeigte sich die Differential Evolution sehr robust. Ein gutes Resultat wird schon frühzeitig erreicht, aber nach mehr Filterevaluierungen als beim Simulated Annealing. Dies gilt besonders für die Medianfilterung. Hier wurde schon nach zehn Generationen der optimale Wert ermittelt. Es empfiehlt sich wie bei den Evolutionsstrategien die Zahl der zu überprüfenden Individuen herabzusetzen.

Durch die Medianfilterung wurden im Mittel die besten Resultate erzielt. Während bei der linearen Filterung die größeren Filtermasken nur mäßige Ergebnisse hervorbrachten, erreichten sie bei der Medianfilterung die gleiche Güte wie die kleineren Masken. Ein weiterer Vorteil der Medianfilterung ist, daß die Resultate bei Wahl unterschiedlicher Strategieparameter nicht so stark schwanken. Zudem liegen die Startwerte zum Teil höher als die durch einfache lineare Filter bestimmten Endwerte.

Die stichprobenartig durchgeführten Simulationen mit dem Testbild "Barbara" bestätigen die dargestellten Ergebnisse. Wegen der im Originalbild (Abbildung 6.2) enthaltenen feinen Strukturen war die Interpolation erheblich schwieriger, so daß die erreichten PSNR-Werte um etwa 5 dB unterhalb derjenigen der Vorlage "Lena" lagen. Der auch nach der Interpolation vorhandene Alias ist in Abbildung 6.29 deutlich erkennbar.


Barbara interpoliert
Abbildung 6.29: Interpoliertes Motiv "Barbara"

1 Eine Erläuterung zu den einzelnen Differential-Evolution-Strategien findet sich in Kapitel 2.5.1.

2 siehe Kapitel 2.5.1

Kapitel6 Zurück Kapitel7