Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Rauschunterdrückungin der Theorie & Praxis
Florian KramerUrs Pricking
Seminar „Simulation und Bildanalyse in Java“Universität Ulm, Abteilungen SAI & Stochastik
02.02.2004
Florian Kramer, Urs Pricking 2
Übersicht
1. Motivation2. Arten von Rauschen3. Eigenschaften von Glättungsfiltern4. Lineare Filter5. Nichtlineare Filter 6. Bilateraler Filter7. Literatur
Florian Kramer, Urs Pricking 3
1. Motivation
Rauschunterdrückung:Entfernen von Störungen (Noise), bei Erhalt möglichstaller ursprünglichen, signifikanten Bildeigenschaften.
Originalbild Originalbild, beschädigt
Florian Kramer, Urs Pricking 4
1. Motivation
Beschädigtes Bild gefiltertOriginalbild
Florian Kramer, Urs Pricking 5
2. Arten von Rauschen
Gaußsches Rauschen:Rauschen als additive Abweichung mit Erwartungswert 0:
Weißes Rauschen:Neuer Grauwert des Pixels ist nicht mit dem ursprünglichen Wert des Pixel korreliert.
Spezialfall: Salt and Pepper Rauschen (binäres Rauschen)
2,0~mit ,
σΝ+=′ NNGG
Florian Kramer, Urs Pricking 6
2. Arten von Rauschen
Gaußsches Rauschen Salt and Pepper Rauschen
Florian Kramer, Urs Pricking 7
3. Eigenschaften von Glättungsfiltern
Was ist ein Filter?Ein Filter ist definiert über eine Nachbarschaftsoperation N:
Beispiel:
{ } ( )( )
(Maske)t Bezugspunkmit Gebiet kompaktes :oraftsoperatNachbarsch beliebiger :
Position xan Pixels des Wert :)(,)()(
MN
xgMxxxgNxg ∈′−∀′=′
[ ]...321... [ ]
)(xg
[ ]......6......
321)( ++=′ xg
N
Florian Kramer, Urs Pricking 8
3. Eigenschaften von Glättungsfiltern
a) VerschiebungsinvarianzObjekte behalten Position.
b) Erhaltung des Mittelwertes Erhaltung des Bildmittelwertes.
c) MonotonieKleine Strukturen dürfen nicht verbleiben, wenn größere verschwinden.
d) IsotropieGlättung richtungsunabhängig.
Florian Kramer, Urs Pricking 9
- DEMO 1 -Vorführung:
• Verschiebungsinvarianz verletzt: Objekt verschiebt sich• Mittelwert wird nicht erhalten: Bild wird heller
Florian Kramer, Urs Pricking 10
4.1 Lineare Filter - Rechteckfilter
Rechteckfilter:
• Mittelung der Pixel-Werte in einem kleinen Bereich.• Addition der Pixel-Werte und Division durch die
Anzahl der Pixel der Maske.• Durch Skalierung Erhalt des Mittelwertes.
• Beispiel: 1x3 Rechtecksfilter (1-dimensional)
[ ]11131
=R
Florian Kramer, Urs Pricking 11
4.1.1 Lineare Filter – Rechteckfilter – 1 dimensional
Filteroperation angewandt auf ein Bild:
83
1237
35)( =++=′ xg7)( =xg
[ ]
=∗
........
........
........
........
....8...
........
........
11131
........
........
..153739400.
..404042415.
..912755.
........
........
[ ]
Florian Kramer, Urs Pricking 12
4.1.1 Lineare Filter – Rechteckfilter – 1 dimensional
Schneller Algorithmus:
Nur 3 Rechenoperationen pro Bildpunkt, unabhängig von der Filtergröße:
( )
pmgp
mg
ggp
gg
pm
m
pmpmmm
++
′
−+
+=
+
−−+−
Position an Pixels des Alter Wert :eFiltermaskder Größe :12
Position an Pixels des Neuer Wert :
121
1'
1'
Florian Kramer, Urs Pricking 13
4.1.2 Lineare Filter – Rechteckfilter – 2 dimensional
2-D Rechteckfilter:Beispiel: 3x3 Filter
Schneller Algorithmus:Maske separierbar (Symmetrie)
=
111111111
91R
[ ] yx RRR ∗=
∗=
=
111
31111
31
111111111
91
Florian Kramer, Urs Pricking 14
4.1.2 Lineare Filter – Rechteckfilter – Laufzeitanalyse
Laufzeitanalyse (d-dimensionale Maske mit Länge (2p+1))
• Nicht separiert:
• Separiert (d. h. entlang der Achsen in eindimensionale Masken zerlegt):
Additionen - )1)12((tionenMultiplika - )12(
−+
+d
d
pp
Additionen - )1)12((tionenMultiplika - )12(
−+⋅+⋅
pdpd
Florian Kramer, Urs Pricking 15
4.1.3 Lineare Filter – Rechteckfilter – Zusammenfassung
Vorteile:
• Gute Rauschunterdrückung bei Gaußschem Rauschen• Schnelle Berechnung im 1-dimensionalen Fall• Schnelle Berechnung im mehrdimensionalen Fall, da
Maske symmetrisch (Separierbarkeit)
Nachteile:
• Rauschunterdrückung auf Kosten der Detailauflösung • Kanten werden geglättet• Monotonieeigenschaft nicht erfüllt
Florian Kramer, Urs Pricking 16
4.1.3 Lineare Filter – Rechteckfilter – Zusammenfassung
Fehlende Monotonieeigenschaft
[ ]
=∗
−−−−−−
........
........
.000000.
.000000.
.000000.
........
........
11131
........
........
.121121.
.121121.
.121121.
........
........
[ ]
−−
−−
−−
=∗
−−−−−−
........
........
..31
31
31
31..
..31
31
31
31..
..31
31
31
31..
........
........
11131
........
........
..1111..
..1111..
..1111..
........
........
Florian Kramer, Urs Pricking 17
4.1.3 Lineare Filter – Rechteckfilter – Zusammenfassung
Florian Kramer, Urs Pricking 18
4.2 Lineare Filter - Binomialfilter
Binomialfilter:
• Stärkere Gewichtung der Pixelwerte zur Maskenmitte hin gemäß der Binomialverteilung
• Einfachste Glättungsmaske:
• p-mal hintereinander:
• Betrachtung gerader Masken
[ ]1121
=B
[ ] [ ] [ ]4444 34444 21
321
mal pmal p
11...111121... ∗∗∗== p
p BBBB
Florian Kramer, Urs Pricking 19
4.2.1 Lineare Filter - Binomialfilter – 1 dimensional
Beispiele (1-dimensional):
Berechnung der Masken nach dem Pascalschen Dreieck:
[ ][ ]18285670562881256
1
14641161
8
4
=
=
B
B
Florian Kramer, Urs Pricking 20
4.2.2 Lineare Filter – Binomialfilter – 2-dimensional
2D-Binomialfilter (analog zu 2D-Rechtecksfilter):
[ ]
∗=
=∗=
121
21121
21
121242121
41222
yx BBB
Florian Kramer, Urs Pricking 21
4.2.2 Lineare Filter – Rechteckfilter – Laufzeitanalyse
Laufzeitanalyse (d-dimensionale Maske mit Länge (2p+1))
• Nicht separiert:
• Separiert (d. h. Zerlegung in Elementarmasken B):
Additionen - )1)12((tionenMultiplika - )12(
−+
+d
d
pp
Additionen - )1)12((nOperatione-Shift alstionen Multiplika
−+⋅ pd
Florian Kramer, Urs Pricking 22
4.2.3 Lineare Filter – Binomialfilter – Zusammenfassung
Vorteile:
• Erfüllung der Monotonieeigenschaft.• Gute Unterdrückung von Gaußschem Rauschen.• Schneller Algorithmus
Nachteile:
• Schlechte Detailauflösung.• Kantenglättung.• Schlechte Unterdrückung von Salt-and-Pepper
Rauschen.
Florian Kramer, Urs Pricking 23
4.2.3 Lineare Filter – Binomialfilter – Zusammenfassung
Florian Kramer, Urs Pricking 24
4.3 Lineare Filter - Mehrschrittmittelung
Mehrschrittmittelung:
• Mittelung weiter voneinander entfernter Pixel.(Geschwindigkeitsvorteil)
• Am effizientesten sind Mehrschrittmasken entlang der Achsen (Separierbarkeit)
• Beispiel (2-dimensional):
[ ]
=
∗=
1020100000204020000010201
161
10201
4110201
4122
22 yxBB
Florian Kramer, Urs Pricking 25
4.3 Lineare Filter - Mehrschrittmittelung
Problem:
• Verlust der Filtereigenschaft für größere Strukturen (Monotonie)
=> Kaskadierte Mehrschritt-Binomialfilterung, z.B. Verdoppelung der Schrittweite:
444 3444 21L
mals
px
px
px
px
px BBBBB s
−
− 2482 1
Florian Kramer, Urs Pricking 26
5.1 Nichtlineare Filter - Medianfilter
Medianfilter:
• Medianfilter:Sortierung der Grauwerte innerhalb der Maske nach Ihrer Größe und Selektion des „mittleren“ Pixels bzgl. Ihrer Ordnung (Median)
• Medianfilter ist Rangordnungsfilter• Rangordnungsfilter (rank value filter):
Operationen zur Kombination benachbarter Pixel: Vergleichen und Selektieren
Florian Kramer, Urs Pricking 27
5.1 Nichtlineare Filter - Medianfilter
• Beispiel (1x3 Medianfilter):
[ ] [ ]
[ ] [ ]
[ ] [ ]...999000......999000...
...655421......65410221...
...987321......987321...
=
=
=
M
M
M
[ ]
0)( =xg 0)9,0,0()( ==′ Medianxg
[ ]
[ ]
3)( =xg
102)( =xg 4)4,102,2()( ==′ Medianxg
3)7,3,2()( ==′ Medianxg
Florian Kramer, Urs Pricking 28
5.1 Nichtlineare Filter - Medianfilter - Zusammenfassung
Vorteile:
• Monoton ansteigende Rampen werden erhalten• Ausreißer (binäres Rauschen) werden eliminiert• Konstante Nachbarschaften und Kanten sind Fixpunkte• Bei einzelnen gestörten Pixel reicht bereits ein 3x3
Medianfilter• Konzept erweiterbar: Minimum- und Maximumfilter
Florian Kramer, Urs Pricking 29
5.1 Nichtlineare Filter - Medianfilter - Zusammenfassung
Nachteile:
• Schlechte Rauschunterdrückung von Gaußschem Rauschen
• Bei wiederholter Anwendung bleiben nur konstante Bereiche und Kanten zurück
Florian Kramer, Urs Pricking 30
5.2 Nichtlineare Filter - Gewichtete Mittelung
Gewichtete Mittelung:
• Jeder Bildpunkt geht mit einem gewissen Wichtungsfaktor in die Berechnung ein
• Definition:
H - beliebige FaltungsmaskeG - das zu bearbeitende BildW - das Bild, das die Wichtungsfaktoren enthält
( )WH
GWHG∗
⋅∗='
Florian Kramer, Urs Pricking 31
5.2 Nichtlineare Filter - Gewichtete Mittelung
Beispiel:Gewichtete Mittelung Rechteckfilter
Florian Kramer, Urs Pricking 32
5.2 Nichtlineare Filter - Gewichtete Mittelung - Zusammenfassung
Vorteile:
• Berücksichtigung von variierenden statistischen Fehlern der Pixel
• Flexibilität, da die Gewichtung beliebig gewählt werden kann
Nachteile:
• Rechenaufwand• Wahl eines passenden Wichtungsbildes
Florian Kramer, Urs Pricking 33
5.3 Nichtlineare Filter - Steuerbare Mittelung
Steuerbare Mittelung:
• Die Maske wird abhängig von der lokalen Bildstruktur gemacht
• Einstellbare Filter besitzen frei justierbare Parameter wie Glättungsgrad oder Glättungsrichtung, über die sich die Filterung steuern lässt
• Ineffizient (Rechenaufwand)• Alternative:
- Berechnung eines Satzes gefilterter Bilder aus einer Basis von Filtern und dem ursprünglichen Bild - Interpolation dieser Bilder unter Verwendung von justierbaren Parametern
Florian Kramer, Urs Pricking 34
5.3 Nichtlineare Filter - Steuerbare Mittelung
• In Operatornotation:
• Probleme:- Existenz einer Filterbasis- Beziehung zwischen
∑=
=P
ppp HfH
1)()( αα
α
α
metersSteuerpara
deson ionsfunktiInterpolat skalare - )(f
Filter te-p -
p
pH
. und pfαpH
Florian Kramer, Urs Pricking 35
- DEMO 2 -Wirkung von linearen und nicht-linearen Filtern bzgl.
• beschädigten Bildern (Lineare vs. Medianfilter)(Min, Maxfilter „Erosion“, „Dilatation“)
• Gauß‘schem Rauschen (Lineare vs. Medianfilter)• Salt and Pepper (Lineare vs. Medianfilter)• Kantenerhaltung (Lineare vs. Medianfilter)
Zugabe (siehe Vortrag letztes Semester)• Kantenextraktion (horizontal, vertikal, beide Richtungen)
Florian Kramer, Urs Pricking 36
6. Bilateraler Filter
Bilateraler Filter:
• Glättung von Bildern bei Erhalt der Kanten (Objekterkennung)
• Bevorzugung naher und ähnlicher Pixel bei der Gewichtung (domain and range filtering)
• Gute Anwendbarkeit auf Graustufen- und Farbbilder
Florian Kramer, Urs Pricking 37
6.1 Bilateraler Filter – Domain Filter – 2 dimensional
Klassischer Bildbereich-Filter (domain filter, allgemeiner und stetiger Fall):
ξξξξ
ξξ
ξξξ
und für t nktionswerAbstandsfu :),(Position an Pixels des Alter Wert :)(
xPixelfür sfaktor Normierung :)(Position xan Pixels des Neuer Wert :)(
),()(mit
),()()()( 1
xxcf
xkxh
dxcxk
dxcfxkxh
d
d
d
∫ ∫
∫ ∫∞
∞−
∞
∞−
∞
∞−
∞
∞−
−
=
=
Florian Kramer, Urs Pricking 38
6.1 Bilateraler Filter – Range Filter – 2 dimensional
Bildwerte-Filter (range filter, allgemeiner und stetiger Fall):
)( und )(für t nktionswerAbstandsfu :))(),((Position an Pixels des Alter Wert :)(
xPixelfür sfaktor Normierung :)(Position xan Pixels des Neuer Wert :)(
))(),(()(mit
))(),(()()()( 1
ξξξξ
ξξ
ξξξ
fxfxffsf
xkxh
dxffsxk
dxffsfxkxh
r
r
r
∫ ∫
∫ ∫∞
∞−
∞
∞−
∞
∞−
∞
∞−
−
=
=
Florian Kramer, Urs Pricking 39
6.1 Bilateraler Filter – 2 dimensional
Bilateraler Filter(domain and range filtering, allgemeiner und stetiger Fall):
ξξξξ
ξξ
ξξξ
ξξξξ
und für t nktionswerAbstandsfu :),()( und )(für t nktionswerAbstandsfu :))(),((
Position an Pixels des Alter Wert :)( xPixelfür sfaktor Normierung :)(
Position xan Pixels des Neuer Wert :)(
))(),((),()(mit
))(),((),()()()( 1
xxcfxfxffs
fxkxh
dxffsxcxk
dxffsxcfxkxh
∫ ∫
∫ ∫∞
∞−
∞
∞−
∞
∞−
∞
∞−
−
=
=
Florian Kramer, Urs Pricking 40
6.1 Bilateraler Filter - Konzept
Beispiel:
Maske 23x23 einefür ))(),((),( xffsxc ξξ
Pixel 10mit Rauschen Gausschemmit gestört
Kante-Graustufen 100mit bildGraustufen
=σ
FiltersnBilaterale des Ergebnis
Florian Kramer, Urs Pricking 41
6.2 Bilateraler Filter - Gewichtungsfunktionen
Gewichtungsfunktionen:
• Prinzipiell frei wählbar• Beispiel: Gaußscher Fall
Abstander euklidisch )(),(, ),(
Abstand.er euklidisch ),(,),(
2
2
))(),((21
),(21
fffexs
xxexc
r
d
xff
xd
−Φ=−Φ=Φ
=
−=
=
−
−
δδξ
ξξξ
σξδ
σξ
Florian Kramer, Urs Pricking 42
6.2 Bilateraler Filter - Gewichtungsfunktionen
Eigenschaften:
• und können „passend“ (frei) gewählt werden• Domain-Filter ist verschiebungsinvariant• Range-Filter ist verschiebungsinvariant
dσrσ
Florian Kramer, Urs Pricking 43
6.3 Bilateraler Filter - Experimente mit Graustufenbildern
Glättung feiner Strukturen:
=> Datenreduktion bei Erhalt essentiellerEigenschaften
Bilateraler Filter
Originalbild , gefiltertOriginalbild
Florian Kramer, Urs Pricking 44
6.3 Bilateraler Filter - Experimente mit Graustufenbildern
Florian Kramer, Urs Pricking 45
6.3 Bilateraler Filter - Experimente mit Graustufenbildern
• Bilateraler Filter, 50,3 == rd σσ
Bilateraler Filter
Bilateraler Filter
Florian Kramer, Urs Pricking 46
6.3 Bilateraler Filter - Experimente mit Graustufenbildern
Laufzeitanalyse:
• Rechenoperationen:Doppelter Berechnungsaufwand (Domain und Range) wie bei nicht separierbaren klassischen Domain-Filtern (z.B. Rechtecksfilter) der gleichen Größe
• Verbesserung Gauß‘scher Fall:Berechnung aller Werte der Rangefunktion im voraus (2n+1 Differenzwerte bei n-Graustufenbild)
Florian Kramer, Urs Pricking 47
6.4 Bilateraler Filter - Experimente mit Farbbildern
Problem mit Farbbildern:Entstehung unerwünschter Farben bei der Glättung vonKanten bei traditionellen Filtern.
a) Linearer Filterb) Bilateraler Filter
(Separierung der Bänder)
c) Bilateraler Filter (Abstandsfunktion im CIE Bereich)
a)
c)b)
Florian Kramer, Urs Pricking 48
6.4 Bilateraler Filter - Experimente mit Farbbildern
Iterative Bilaterale Filterung:
1x
5x
Florian Kramer, Urs Pricking 49
6.5 Bilateraler Filter - Zusammenfassung
Vorteile:
• Vereinigt positive Eigenschaften von linearen und nicht-linearen Filtern
• Gewichtungsfunktionen frei wählbar und deren Parameter auf das gegebene Bild justierbar.
Nachteile:
• Gleicher Komplexitätsgrad wie nicht separierbare Standard Filter.
Florian Kramer, Urs Pricking 50
- DEMO 3 -Vorführung:
Glättung bei Erhaltung der Kanten am Beispiel vonGraustufen und Farbbildern:
Lineare, Nicht-Lineare vs. Bilaterale Filter
Florian Kramer, Urs Pricking 51
7. Literatur
1. B. Jähne, „Digital Image Processing “, 2002, Springer Verlag.
2. C. Tomasi and R. Manduchi, „Bilateral Filtering forGray and Color Images“, Proceedings of the 1998 IEEE International Conference on Computer Vision, Bombay, India, 1998.
Florian Kramer, Urs Pricking 52
ENDE
Vielen Dank für Ihre Aufmerksamkeit!