Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Einführung in
Blind Deconvolution
16.12.2005
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Überblick
(Non-blind) Deconvolution
Modell, Lösungsansätze, Eigenschaften
Blind Deconvolution
Modell, Anwendungsbeispiele
Eindeutigkeit
Verschiedene Randbedingungen und Dimensionen
Einige Lösungsansätze
Nullstellenidentifikation, Regularisierungsansätze (
und
)
Eigene Arbeit
Eindeutigkeit, Grad der schlecht-Gestelltheit, Regularisierung
2 / 27
Zentrum für Technomathematik
Fachbereich 03
Mathematik und Informatik
(Non-blind) Deconvolution
Modell:
Bekannt:
Kern
Daten
Unbekannt:
Rauschen
Bild
3 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Deconvolution - Eigenschaften
Auf
: Fourier-Faltungssatz
Lineares Problem
I.d.R. eindeutig lösbar
Schlecht gestellt
Grad der schlecht-Gestelltheit hängt vom Abfallverhalten des Kerns ab
Schneller Abfall
Rauschen wird stark verstärkt
4 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Deconvolution - Lösungsansätze
Regularisierung
Möglichkeiten zur Wahl des Glattheitsraumes
: lineares Problem
: Lösung mit Surrogate-Ansatz (Daubechies et. al.)
: Rudin-Osher-Fatemi-Funktional
Funktional konvex und Minimum i.d.R. eindeutig
Beispiel:
5 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Blind Deconvolution
Modell:
Bekannt:
Daten
Unbekannt:
Rauschen
Bild
Kern
Ziel: Rekonstruiere
und
aus
6 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Anwendungsbeispiele
Astronomie
Rekonstruktion von Hubble-Aufnahmen vor der optischen Korrektur
(Bertero et. al. '94)
Photographie
Unbekannte Bewegungs- oder Tiefenunschärfe (Fabian, Malah '91)
Seismologie
Rekonstruktion von 1D-seismischen Wellen (Stefan '05)
Medizinische Bildverarbeitung
Röntgentomographie (Faulkner et. al. '89)
Positronen-Emissions-Tomographie (PET) (Drossos '89)
7 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Eindeutigkeit
Ohne Rauschen:
Ist
eine Lösung, so auch
für alle
Man fordert daher oft
Eindeutigkeit hängt von Randbedingungen und Dimension ab
Diskret, D-dimensional mit periodischen Randbedingungen
Diskret, 1-dimensional mit Null-Randbedingungen
Diskret, 2-dimensional mit Null-Randbedingungen
8 / 27
Zentrum für Technomathematik
Fachbereich 03
Mathematik und Informatik
D-dim. mit periodische Randbedingungen
Modell (D=2):
Fourier-Faltungssatz:
Unendlich viele Lösungen
9 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
1-dim. mit Null-Randbedingungen
Modell:
... 0
0 ...
... 0
0 ...
... 0
0 ...
Definiere Polynome:
Dann ist
Äquivalentes Problem: Rekonstruiere Polynome
und
aus
10 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
1-dim. mit Null-Randbedingungen
zerfällt in Linearfaktoren
Diese können beliebig auf
und
verteilt werden, z.B.
oder
Endlich viele Lösungen (bis auf Skalierung)
11 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
2-dim. mit Null-Randbedingungen
Modell:
0
..
.
0
0
0
...
...
0
0
0
..
.
0
0.
.
0
0 ... 0
0 ... 0
0.
.
0
0. ... 0.
.
.
0 ... 0
Ebenfalls äquivalent zu Polynomzerlegungs-Problem
2-D Polynome i.Allg. nicht faktorisierbar
I.d.R. eindeutige Lösung! (bis auf Skalierung)
12 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Lösungsansätze - Nullmusteridentifikation
Identifikation von Nullstellenmuster in
(Cannon '76)
Typisches Modell für z.B. Tiefenunschärfe:
Nullstellen von
sind konzentrische Kreise
hat ebenfalls dieses Nullstellenmuster
Rekonstruiere
und somit
aus dem Muster
Benutze non-blind-Verfahren für
13 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Lösungsansätze – Doppel-Regularisierung
Idee:
You, Kaveh '96:
und
gewichtete Sobolev-Räume
Chan, Wong '98:
Minimum nicht eindeutig für
Burger, Scherzer '01:
Existenz von Minimierern
Stabilität bei Störungen in
Konvergenz gegen Minimum-Norm-Lösung
14 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Alternierende Minimierung (AM)
Problem:
Aber:
nicht konvex!
und
sind konvex
Alternierende Minimierung
Starte mit Schätzer
Für
(z.B.
)
berechne
und
Chan, Wong, '00: Konvergenz für
Burger, Scherzer '01: Konvergenz für allgemeinere Klasse
15 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Offene Fragen
Ist das Minimum eindeutig für
?
Wie schlecht ist das Problem konditioniert?
Konvergiert AM gegen eine Minimum-Norm-Lösung?
16 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Eigene Arbeit
Untersuchung von
-Minimum-Norm-Lösungen
a-priori Schätzer von Bild und Kern
ist eine
-Minimum-Norm-Lösung
von falls
Wegen Plancherels Formel gilt auch
Minimiere punktweise!
17 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Berechnung der Minimum-Norm-Lösung
=
Nullstelle von
Polynom 4. Grades
Projektion auf
Hyperbel
18 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Der Lösungsoperator I
Voraussetzungen and die Schätzer und die Daten
ist symmetrisch, d.h.
ist nicht-negativ, d.h.
ist normalisiert, d.h.
mit der Wiener Algebra
, wobei
19 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Der Lösungsoperator II
Dann gilt (J., Ramlau '05)
Es gibt eine eindeutige Minimum-Norm-Lösung
Bei festem
wird ein Lösungsoperator („Pseudoinverse“)
induziert.
Dieser ist Hölder-stetig mit Exponent ½
20 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Bedeutung der Stetigkeit des Operators
Daten in
(d.h.
stabil invertiert werden
) können
Unabhängig vom echten Kern
Non-blind Deconvolution:
Daten müssen mindestens so glatt wie der echte Kern sein
Funktionen in
sind „nur“ gleichmäßig stetig
Blind Deconvolution ist
weniger schlecht gestellt
(weniger schlecht konditioniert)
als non-blind Deconvolution
21 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Regularisierung
Allgemeine Daten
mit
sind nicht in
Idee: Vorglätten
Datenglättung
Inversion
Regularisierung und Inversion sind zwei getrennte Schritte
Untersuchte Glättungsoperatoren
Tikhonov-Regularisierung des Sobolev-Einbettungsoperators
Fourier Soft-Shrinkage
22 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Regularisierter Einbettungsoperator
für
J., Ramlau '05:
Unter der Parameterwahl
Ist zusätzlich
und
und
mit
für
gilt
,
so gilt mit
23 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Fourier Soft-Shrinkage
J. '06 (to appear):
Ähnliche Aussagen, aber „Glattheitsräume“ hier:
mit
Es gibt eine Einbettung
Beispiel: Funktion
(!)
, aber nicht umgekehrt
, aber
24 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Beispiele
Originalbild
Daten
Rekonstruktion
25 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Beispiele
Satellit
Lena
Barbara
Cameraman Tomograph
26 / 27
Fachbereich 03
Mathematik und Informatik
Zentrum für Technomathematik
Zusammenfassung
Blind Deconvolution und schlecht-Gestelltheit nach Hadamard
Existenz von Lösungen

Eindeutigkeit
• Hauptproblem
Stetige Abhängigkeit
• Spielt untergeordnete Rolle
• Blinde Variante nicht so schlecht-gestellt wie normale Deconvolution
Ein Zoo von Lösungsverfahren
Oft Übertragung von non-blind Verfahren auf blind Deconvolution
Existenz und Eindeutigkeit Lösungen meistens nicht geklärt
Viele Fragen offen...
27 / 27

Vortrag Lutz Justen, 2005-12-16