Hough-Transformation / Watershed

Ziel:

• Erkennung von einfachen, parametrisierbaren Strukturen mit kleinem Parameterraum im Bild

  • Geraden/Linien (2 DOF)

  • Kreise (3 DOF)

Algorithmus:

1. Transformation der Bilddaten in binäre Kantendaten (z.B.: über lineares Kantenfilter + Binarisierung)

2. Transformation der Pixelkoordinaten in Parameterraum

3. Abtastung des Parameterraums

4. Identifikation von Parameterschnittpunkten

5. Rücktransformation einer entsprechenden Anzahl an Maxima

Geradengleichung: y = k*x +d

[x,y] : Pixelkoordinatenraum

[k,d] : Parameterraum

->Zwei Linien im Bild korrespondieren zu zwei Punkten im Hough-Raum und umgekehrt.

Aber:

• Parameterraum nicht linear skaliert

• Steigung und Achsenabschnitt haben unendlichen Wertebereich

• Für vertikale Linien:

  • k -> +- unendlich

  • d -> +- unendlich

Ansatz:

• Repräsentation des Parameterraums über Winkel und Abstand (Polardarstellung)

  x cos(θ) + y sin(θ) - ρ = 0

• θ : Winkel zur x-Achse

• ρ : Absatnd zum Ursprung

-> halbe Periode ausreichend

• Initialisiere “leeren” Parameteraum H(θ,ρ)

• Iteriere über Binärbild I für alle Pixelpositionen (x,y):

  • falls I(x,y) > 0 (“Linienpixel”): Für alle (θ,ρ) im Hough-Raum, die eine Gerade beschreiben, welche den Bildpunkt enthält: erhöhe (akkumuliere) H(θ,ρ) = H(θ,ρ)+1

• Maxima in der Hough-Transformierten korrespondieren zu präganten Linien im Binärbild

• Position der lokalen Maxima geben Parameter der Linien an

• Je mehr Punkte, desto robuster der Ansatz

Kreisgleichung: (x-xc)^2 + (y-yc)^2 -r^2 = 0

[x,y] : Pixelkoordinatenraum

[xc, yc, r] : Parameterraum (3 DOF!)

xc,yc -> Kreismitte

• Iteration über verschiedene Radien bei der Kreissuche

  • Häufig: Eingrenzung bzw. Startwert

• Vorteile gegenüber Features wie Circularity:

  • Kreis muss nicht vollständig sein oder kann überlappen

  • Radius-Range kann für Klassifikation benutzt werden

• Bisher:

  • Zuordnung zu einem gemeinsamen Label und gemeinsame Merkmalsableitung

  • Zusammenhängende Objekte wurden nicht getrennt

• Lösungsansatz: Wasserscheide-Methode (Watershed)

• Häufige Anwendungen: Segmentierung von Aggregatstrukturen wie Zellen, Poren, Partikel, etc.

Ansatz:

• Grauwertbild wird als “Höhenlandschaft” interpretiert und mit “steigendem Wasserstand geflutet”

• Dort, wo sich unterschiedliche “Wasserbecken” berühren, wird eine “Scheidewand” gezogen

Häufig umfangreiche Vorverarbeitung:

• Morphologische Filter

• Kantenfilter

• Hoch-/Tiefpass

• Marker bassierte Wasserscheidemethode

• Wasser tritt nur aus “definierten Quellen” (Markern) aus, welche nicht dem jeweiligen lokalen Grauwertminimum entsprechen müssen

Möglicher Algorithmus:

1. Separation des Vordergrundes über Grauwertmorphologie

2. Berechnung der lokalen Maxima in jeder morphologischen Region (~Fensterung)

3. Weitere morphologische Nachbearbeitung

4. Separation des Hintergrundes über morphologische Operatoren

5. “Thinning” des Hintergrundes

6. Watershed auf Basis des Hintergrundskellets und der Vordergrund-Regionsmaxima (3. & 5.)

Andere Möglichkeit:

1. Binarisierung des Eingangsbildes

2. Konturfindung & Distanztransformation

3. Marker lokale Maxima

4. Watershed