Skript zur Vorlesung Digitale Bildverarbeitung

Sommersemester 2014

Teil B

(2.7.2014)

Susanne Winter Institut für Neuroinformatik

2

3

Inhalt 14. Bildvergleich ........................................................................................................................ 5 15. Registrierung ...................................................................................................................... 10 16. Punktbasierte Registrierung ............................................................................................... 13 17. Anwendungsbeispiel: Registrierung von CT- und MRT-Daten ........................................ 15 18. Anwendungsbeispiel: Kalibrierung einer Kamera ............................................................. 17 19. Morphologische Operatoren ............................................................................................... 19 

4

5

14. Bildvergleich Bildvergleich

• Bestimmung der Ähnlichkeit zwischen zwei Bildern • Einfachste Methode: Bilden der Differenz

Sind die beiden Bilder identisch, so ist die Differenz Null • Problem:

Schon kleine Änderungen z.B. des Grauwertbereichs (Helligkeit, Farbquantisierung, …), leichte Verschiebungen oder Rotationen können zu großen Abweichungen führen, obwohl das Bild für den Betrachter (fast) identisch ist.

Ein Ziel wäre z.B.

• Lokalisation eines bekannten Teilbildes • Template Matching (Template = Maske, Vorlage)

Was wird benötigt um ein Template in einem Bild zu finden?

• Maß für die Ähnlichkeit zweier Bilder / Bildausschnitte • Welche Ähnlichkeit spricht für eine Übereinstimmung? • Suchstrategie

Suchstrategie: Template (Muster) wird über das Bild geschoben Ähnlichkeitsmaße

• Abstand zwischen dem Muster und dem Bildausschnitt • Summe der Differenzbeträge • Maximaler Differenzbetrag (nicht gut geeignet) • Summe der quadratischen Abstände • Sowohl die Summe der Differenzbeträge sowie die Summe der quadratischen Abstände

weisen ein lokales Optimum auf, sind aber z.B. empfindlich gegenüber Helligkeitsänderungen • Die beste Übereinstimmung eines Bildausschnitts mit einem Muster ist an der Stelle zu finden,

an der d²E (r,s) minimal ist. • Kreuzkorrelation (abhängig von der lokalen Helligkeit) • Normalisierte Kreuzkorrelation (gutes Optimum, aber kein Maß für die absolute Ähnlichkeit) • Kovarianz (gutes Optimum, aber kein Maß für die absolute Ähnlichkeit) • Korrelationskoeffizient (liefert ein absolutes Maß für die Ähnlichkeit) • Wertebereich zwischen -1 und 1

Vergleich von Binärbildern

• Problem: kleinste Abweichungen können zu starken Änderungen im Ähnlichkeitsmaß führen – Leichte Verschiebung – Kleine Rotationen – Verzerrungen

• Interessant ist außerdem der Abstand zum gesuchten Optimum Distanztransformation

• Für einen Vergleich von Binärbildern kann die Distanztransformation genutzt werden • Für alle Hintergrundpixel wird die minimale Distanz zu einem Vordergrundpixel berechnet • Mögliche Distanzfunktionen:

– Euklidische Distanz – Manhattan-Distanz (auch city block distance)

6

Chamfer-Matching • Binäres Template: R • Vordergrundpixel des Templates: FG(R) • Binärbild: I • Distanztransformation des Bildes: D • Template wird über das Bild bewegt, die Werte der Distanzverteilung werden addiert • Der beste Match liegt im Minimum von Q

Es ergeben sich lokale Optima (das kann erwünscht oder unerwünscht sein) Form des Templates

• Form muss nicht rechteckig sein • Das Template sollte genügend Hintergrund um das eigentliche Muster herum haben, so dass

die Form des Musters heraus kommt • Die Hintergrundregion sollte nicht zu groß sein, da der Hintergrund sonst beim Matching eine

zu große Rolle spielt Umgang mit Skalierung und Drehung

• Beim Verschieben eines Templates werden Unterschiede in der Skalierung eines Objekts oder Drehungen eines Objekts nicht berücksichtigt

– Die Suche kann z.B. erweitert werden auf Templates mit unterschiedlicher Skalierung und auf rotierte Templates

– Hier sind aufgrund des hohen Rechenaufwandes aber Grenzen gesetzt Quellen / Links: Abbildungen und Formeln aus „Digitale Bildverarbeitung“ von Burger und Burge, Kapitel 17 (17.1, 17.2, 17.3, 17.7, 17.8, 17.10, 17.11, eqn. 17.1 – 17.4, eqn. 17.6, eqn. 17.14 - 17.21) Abbildungen:

7

8

9

10

15. Registrierung Was ist Registrierung?

• Matching von Bilddaten • Überlagerung von Bilddaten • Bilder der selben Szene oder desselben Objekts

– aus unterschiedlichen Blickwinkeln – mit unterschiedlichen Aufnahmebedingungen aufgenommen – zu verschiedenen Zeitpunkten (Detektion von Änderungen)

Verschiedene Blickwinkel / Aufnahmepositionen

• Überlagerung von Fotografien aus verschiedenen Blickwinkeln • Zusammensetzen einer Panoramaansicht • Zusammensetzen von Satelliten oder Radaraufnahmen zu einer großen Karte • Verschiedene Satellitenaufnahmen werden zu einer großen Aufnahme zusammengefügt

Verschiedene Aufnahmebedingungen

• Überlagern von Bilddaten, die unterschiedliche Informationen liefern • Zusammensetzen von Satellitenaufnahmen oder fotografischen Luftaufnahmen

unterschiedlicher Aufnahmen • Überlagerung von Luft- und Satellitenaufnahmen mit Landkarten • Überlagern medizinischer Bilddaten verschiedener Aufnahmemodalitäten • Überlagerung verschiedener diagnostischer Aufnahmen • Lokalisation von Veränderungen

Aufnahme zu verschiedenen Zeitpunkten

• Detektion von Veränderungen über die Zeit – Therapiekontrolle bei Tumoren – Beobachtung eines Krankheitsverlaufs

Einteilung der Registrieralgorithmen Klassifikation von Registriermethoden nach Maintz & Viergever (1998):

(A) Dimension (2D-2D, 2D-3D, 3D-3D, …) (B) Natur der Basis der Registrierung (extrinsisch, intrinsisch) (C) Art der Transformation (D) Notwendige Interaktion (E) Optimierungsstrategie (F) Bildmodalitäten

(A) Dimensionalität

• 2D-2D Registrierung: Zusammensetzen von Fotografien, Satelliten- oder Luftaufnahmen für Landkarten

• 2D-3D-Registrierung: z.B: Röntgenbilder mit dreidimensionalen CT-Daten (oder Modellen)

• 3D-3D-Registrierung: dreidimensionale Datensätze: CT- MRT-Daten, verschiedene MRT-Sequenzen, Ultraschalldaten, …

(B) Basis der Registrierung

• Extrinsische Marker – Marker, die von außen z.B. am Patienten angebracht werden – Referenzrahmen – Schraubenmarker

11

– Klebemarker • Nach Befestigung der Marker werden Bilddaten aufgenommen • Einsatz: chirurgische Navigation • Vorteil: Invasiv befestigte Marker sind sehr genau • Nachteile: Invasivität, Belastung für den Patienten, Klebemarker sind eher ungenau

• Intrinsisch

– Anatomische Landmarken / markante Punkte (meist interaktiv durch einen Benutzer markiert) Nachteil: oft können die Landmarken nicht exakt markiert werden

– Automatisch bestimmte Landmarken (z.B. Eckpunkte, Konturpunkte mit extremer Krümmung, …)

– Oberflächen (segmentierte Oberflächen z.B. Knochenoberflächen in CT-Daten oder Hautoberfläche in CT oder MRT-Daten; Umrisse / Konturen von Objekten)

– Pixel- / voxelbasiert (Grauwerte, Bildmerkmale) (C) Transformationen

• Rigide Transformation (starre Transformation, nur Verschiebung und Rotation) • Affine Transformation (parallele Linien bilden sich auf parallele Linien ab) • Projektive Transformation (Linien bilden sich auf Linien ab) • Elastische Transformation

(D) Benutzer Interaktion

• Vollautomatisch (nur die Bilddaten werden an das System gegeben) • Benutzergesteuert (der Benutzer registriert die Daten manuell und wird nur durch

Visualisierung oder Angezeigte Fehlermaße unterstützt) • Semiautomatisch = halbautomatisch

Die meisten Verfahren erfordern noch die ein oder andere Benutzerinteraktion z.B.: – Markieren korrespondierender Punkte, Regionen – Markieren relevanter Bereiche (z.B. des richtigen Wirbels) – Initialisierung der Registrierung (grobe Vorregistrierung, setzen der Startposition)

(E) Optimierungsstrategie Bestimmung der besten Parameter der Transformation

1. Alle Möglichkeiten testen (in der Regel zu aufwändig) 2. Direkt berechnen

(nur möglich z.B. bei einer geringen Zahl von Punkten) – Z.B. anhand von 2 Punkten: rigide Transformation + Skalierung – Anhand von 3 Punkten: Affine Abbildung – Anhand von 4 Punkten: Projektive Abbildung

3. Optimierungsverfahren – Gradientenbasiert (Gradientenabstiegsverfahren, Konjugierte Gradienten, BFGS,

Levenberg-Marquard, …) – Evolutionäre Verfahren

(F) Bildmodalitäten

• Modalitäten – Verschiedene medizinische Bilddaten (Ultraschall, CT, MRT, Röntgen, PET, SPECT,

…) – Fotografien – Luftaufnahmen, Radaraufnahmen, Satellitenaufnahmen

• Monomodal: Registrierung von Bildern oder Volumina derselben Modalität • Multimodal: Registrierung von Bildern oder Volumina unterschiedlicher Modalitäten (z.B. CT

mit MRT oder Ultraschall mit CT … oder Satelliten- mit Luftaufnahmen, …) • Modalität mit Modell (Registrierung z.B. mit anatomischen Modellen oder mit Landkarten)

12

• Patient-Bild-Registrierung: Nur eine Bildmodalität wird mit dem physikalischen Raum z.B. im OP registriert

Quellen / Links: Übersichtsartikel, Einteilung der Registriermethoden: Maintz, Viergever: „A survey of medical image registration“, (1998) Abbildungen:

13

16. Punktbasierte Registrierung Registrierung von Punktpaaren

• Eine exakte Abbildung kann anhand von Punktpaaren mit ein, zwei, drei oder vier Punktpaaren bestimmt werden

Registrierung anhand eines Punktpaars • Anhand eines einzelnen Punbktpaars kann nur eine Verschiebung exakt bestimmt werden.

Registrierung von zwei Punktpaaren Achtung: Die Reihenfolge der Transformationen ist entscheidend!

• 4 Freiheitsgrade – Zwei Verschiebungsparameter – Ein Rotationsparameter – Ein Skalierungsparameter

• Zur Bestimmung einer rigiden Transformation wird nur ein Punkt exakt überlagert, der zweite Punkt dient nur zur Ermittlung des Rotationswinkels.

Registrierung von drei Punktpaaren

• 6 Freiheitsgrade – Zwei Verschiebungsparameter – Ein Rotationsparameter – Zwei Skalierungsparameter – Zwei Scherungsparameter

• In beiden Bildern werden korrespondierende Punkte markiert • Anhand dieser Punkte wird die Transformation berechnet • Dreipunktregistrierung

Affine Abbildung

Registrierung von vier Punktpaaren • Bei Luftaufnahmen kann es je nach Blickwinkel zu Verzerrungen im Sinne der

perspektivischen Transformation kommen. Hier ist die Registrierung auf Basis von vier Landmarken sinnvoll.

Registrierung von Punktpaaren Zwei, drei oder vier Punktpaare können exakt registriert werden

• Vorteile: – Einfache Verfahren – Transformation kann exakt bestimmt werden

• Problem: – Güte der Registrierung hängt vom Vorhandensein geeigneter Punkte und von der Güte

der Punkte ab Registrierung von n Punktpaaren

• Um den Abbildungsfehler möglichst gering zu halten wird die Zahl der verwendeten Punkte erhöht

• Die Fehler, die durch die einzelnen Punkte entstehen sollen sich herausmitteln • n Punkte können nicht exakt registriert werden • Forderung: der Abbildungsfehler soll möglichst gering sein • Gesucht ist diejenige Transformation T, die die geringsten Abweichungen bei der Abbildung

von Punktpaaren ergibt

14

• Ziel: Minimierung der Distanzen zwischen den korrespondierenden Punkten • Eine Fehlerfunktion E wird definiert z.B. als mittlere Abweichung der korrespondierenden

Punkte nach Transformation oder als mittlere quadratische Abweichung

• Es wird diejenige Transformation T gesucht, die den Fehler E(T) minimiert • T wird bestimmt durch die Parameter der Transformation • Die Art der Transformation und damit die Parameter werden zuerst festgelegt • Entscheidend für diese Wahl ist, welche Transformation erwartet wird (rigide, Skalierung,

affin, projektiv, …) • Die Suche nach dem besten Parametersatz wird mit einer Optimierungsstrategie durchgeführt

Optimierung

• Der Fehler kann für jeden Punkt im Parameterraum berechnet werden • Der Parameterraum ist bei einer rigiden Registrierung im zweidimensionalen dreidimensional

Gradientenbasierte Optimierung

• Die Suche nach dem Optimum wird in einem Punkt gestartet (Initialisierung) • Gradientenabstieg

– Der Gradient der Optimierungsfunktion wird in diesem Punkt bestimmt (entweder berechnet oder geschätzt durch kleine Variation der Parameter)

– Abhängig von der Gradientenrichtung und dem Betrag des Gradienten erfolgt ein Schritt im Parameterraum

– Nachteile des Gradientenabstiegs: – Schrittweite ist häufig zu groß, da Gradienten sehr groß werden können es erfolgt

ein Schritt über das Optimum hinweg – Verfahren läuft in lokale Optima

• Es existieren eine ganze Reihe verschiedener Optimierungsverfahren, die auf dem Gradienten basieren

Bildbasierte Registrierung

• Es sollen keine Landmarken detektiert werden müssen • Die Registrierung arbeitet auf den Bildinhalten

15

17. Anwendungsbeispiel: Registrierung von CT- und MRT-Daten

• Ziel: Es sollen CT- und MRT-Daten eines Patienten miteinander registriert werden

• Die Bildinhalte in den Daten unterscheiden sich deutlich voneinander, daher sind Ähnlichkeitsmaße wie die Korrelation nicht geeignet

• Idee: Strukturen stellen sich zwar durch ganz unterschiedliche Grauwerte dar, aber bestimmte Gewebetypen bilden sich jeweils auf einen bestimmten Grauwertbereich ab

• Das heißt, dass bei einer exakten Überlagerung bestimmte Grauwertpaare häufig vorkommen (z.B. Knochen im CT ist weiß, im MRT schwarz, usw. …)

Entropie

• Entropie in der Physik – Maß der Unordnung

• Entropie in der Informationstheorie – Shannon Entropie

• Shannon Entropie für ein Bild / einen Bildausschnitt – Maß für die Grauwertverteilung – Kann aus dem Histogramm bestimmt werden – Absolute Grauwerte spielen keine Rolle – Nur die Anzahl verschiedener Grauwerte und deren Häufigkeit spielen eine Rolle – Bei Gleichverteilung aller auftretender Grauwerte ist die Entropie maximal

Kreuzentropie • Wenn jeder Grauwert im CT einen festen korrespondierenden Grauwert im MRT hat, dann ist

die Entropie der gemeinsamen Verteilung minimal • Das Maß hat den Nachteil, dass es sehr klein werden kann, bei geringer Überlappung der

Bilder (z.B. Überlapp nur im Hintergrund) Mutual information

• Ein besseres Maß ist daher die Mutual information (MI) (mutual engl.: beiderseits, gegenseitig)

• Ein geringer Überlapp wird dadurch bestraft, dass die Entropien der Einzelbilder sehr gering sind, wenn diese nur aus Hintergrund bestehen

• MI ist ein Maß dafür, wie viel Information ein Bild über ein anderes liefert

Vorteil der Registrierung mittels Mutual Information: • Die gesamte Bildinformation geht in die Registrierung ein, d.h. das Ergebnis ist nicht von

einer Vorverarbeitung abhängig Nachteil:

• Sehr rechenintensiv Quellen / Links: JPW Pluim, JBA Maintz, MA Viergever: „Mutual information based registration of medical images: a survey“ (2003) ; WM Wells, P Viola, H Atsumi, S Nakajima, R Kikinis: „Multi-modal volume registration by maximization of mutual information”. Medical Image Analysis 1(1), pp. 35.51, (1996)

16

Abbildungen:

17

18. Anwendungsbeispiel: Kalibrierung einer Kamera • Ziel: Es soll die Transformation gefunden werden, mit der die Aufnahme einer beliebigen

Kamera entzerrt wird

• Welche Transformation ist geeignet um diese Abbildung zu lösen? • Welches Maß ist geeignet um die Ähnlichkeit der Bilder bei Überlagerung zu beschreiben?

– Projektive Abbildung – Radiale Verzerrung – Unterschiede in der Beleuchtung

• Die Transformation soll aus einer projektiven Abbildung kombiniert mit einer radialen

Verzerrung bestehen – Die projektive Abbildung wird durch 8 Parameter bestimmt – Die radiale Verzerrung durch 5 Parameter

• Als Ähnlichkeitsmaß wird die Grauwertdifferenz verwendet, wobei ein

Beleuchtungsunterschied berücksichtigt wird – Sechs Parameter θ1, …, θ6 beschreiben die Beleuchtungskorrektur

• Bei der Registrierung einer unkalibrierten Kamera wird folgendermaßen vorgegangen: – Ein unverzerrtes Foto wird ausgedruckt und mit der unkalibrierten Kamera

aufgenommen – Dann werden die beiden Bilder miteinander registriert – Bei der Registrierung werden gleichzeitig die Parameter der Transformation und die

der Beleuchtungskorrektur optimiert. Es werden also 8 + 5 + 6 = 19 Parameter optimiert

• Das Ergebnis liefert die Transformation und die Beleuchtungskorrektur

Quellen / Links: T Tamaki, T Yamamura, N Ohnishi: „Correcting Distortion of Image by Image Registration“. In Proc. of ACCV2002, (2002)

18

Abbildungen:

19

19. Morphologische Operatoren Morphologische Operatoren

• Morphologische Filter • Morphologische Operatoren beeinflussen die Struktur von Bildern gezielt • Die Anwendung findet hauptsächlich auf Binärbilder statt • Die Idee ist: Strukturen in Bildern schrumpfen oder wachsen lassen

Nachbarschaften

• 4er-Nachbarschaft • 8er-Nachbarschaft • Verschiedene Strukturelemente

Formale Definition morphologischer Filter

• Binärbilder werden als Mengen beschrieben (Morphologie = Gestaltkunde ist Teilgebiet der mathematischen Mengenlehre)

• Elemente: zweidimensionale Koordinaten-Tupel Grundlegende Operationen auf Binärbildern

• Beschreibung in Mengennotation • Invertierung eines Binärbildes • Vereinigung zweier Punktmengen • Notation kann synonym verwendet werden (I und QI)

Dilatation

• spätlat. dilatatio = Erweiterung • Wird häufig als Wachsen bezeichnet • Summe aller möglicher Koordinatenpaare der Punktmengen QI und QH

Erosion

• lat. erosio = das Zerfressenwerden • Wird häufig als Schrumpfen bezeichnet („quasi-inverse“ Operation zum Wachsen) • Das Strukturelement H muss sich vollständig in das Bild I einbetten lassen

Typische Strukturelemente

• 4er-Nachbarschaft • 8er-Nachbarschaft • Kleine Scheibe

Eigenschaften von Dilatation und Erosion

• Dilatation und Erosion sind dual: Dilatation des Vordergrunds entspricht einer Erosion des Hintergrunds

• Dilatation ist kommutativ • Erosion ist nicht kommutativ (analog zur arithmetischen Subtraktion) • Dilatation ist assoziativ, d.h. die Reihenfolge aufeinanderfolgender Dilationen ist nicht

relevant • Dilatation mit großem Strukturelement kann durch eine Folge von Dilationen mit kleinen

Strukturelementen realisiert werden • Kombination von Erosion und Dilatation erfolgt analog zur Addition und Subtraktion

20

Zusammengesetzte Operationen • Opening: Kleine Strukturen und dünne Linien verschwinden

Erst Erosion, dann Dilatation • Closing: Löcher und kleine Zwischenräume werden gefüllt

Erst Dilatation, dann Erosion

Eigenschaften von Opening und Closing • Opening und Closing sind idempotent: d.h. jede weitere Anwendung derselben Operation

verändert das Bild nicht mehr • Opening und Closing sind zueinander dual: d.h. Opening des Vordergrunds ist äquivalent zum

Closing des Hintergrunds Quellen / Links: Abbildungen und Formeln aus „Digitale Bildverarbeitung“ von Burger und Burge, Kapitel 10

21

Abbildungen: