Split-and-MergeKleines Seminar

vonLena-Luisa Heß

Ablaufn Einführung

u Begriffserklärungenn Split-and-Merge

u Erklärung des Algorithmusu Problemeu Erweiterungen

n Fazit

Begriffserklärungen In Pixel besteht aus Farbwert und Ortn benachbart = Zeilen- und

Spaltennummer zweier Punkteunterscheiden sich um maximal 1

n Region = zusammenhängendeMenge von Pixeln

n Segment = Region mituntereinander ähnlichen Pixeln

Begriffserklärungen IIn Segmentierung = Zerlegung eines

Bildes in visuell unterschiedlicheRegionen, die in bezug auf gewisseEigenschaften wie z.B. Grauwert,Farbe oder Textur homogen sind.

Algorithmusn Vorbereitung

u Teile das Bild in 2n gleich große,quadratische Regionen auf

n Split-Phasen Merge-Phasen Nachbearbeitung

Split In Top-Down-Vorgehensweisen wird mit jedem Teilbild neu

gestartet

Split IIH sei ein Homogenitätskriteriumn Split:

Falls für eine Region R in dieserStruktur H(R) = FALSE gilt, teiledie Region in vier Teilregionen auf

Aufbau eines Quad-Tree

1 2

31 32 33 34

3 4

W

1 2

4331 32

3433

Beispiel eines Quad-TreeQ0 Q1

Q2 Q3

Quad-Tree

0

0 1 1 1

x

0 1 0 1

x 1

x 1

0 1 0 1

x 1 0 0

x 0

x

Merge In Bottom-Up-Vorgehensweisen Verschmelzung von kleineren

Teilbildern zu größeren Teilbildern,falls sie ähnlich genug sind

Merge IIn Merge:

Falls für vier Regionen einesQuadranten Rk1,...,Rk4H(Rk1∪ Rk2∪ Rk3∪ Rk4 ) = TRUEgilt, verschmelze sie zu einerRegion

Probleme In In relativ großem Teilbild B

befinden sich nur wenige Objektevor einem sehr homogenemHintergrund

⇒ B wird als ein Segment erkannt

Probleme I

Probleme I

Probleme IIn großer Bildteil B mit allmählichem

Farbübergang

⇒ Quad-Tree-Grenze wirdSegmentgrenze bilden

⇒ Unnatürliche Grenzverläufe anvertikalen und horizontalen Achsen

Probleme II

Probleme II

Probleme II

Abwandlungenn Erste Zerlegung eines 2n x 2n-großen

Bildes in 4k Teilbilder der Größe 2n-k x 2n-k

und startet von dortn Merging nur von gleichgroßen

Segmenten, die im Quad-Tree einengemeinsamen Vorgänger haben

n Grouping: Verschmelzung anderer, auchverschieden großer, benachbarterSegmente

Ein letztes Beispiel

1 2 3

Fazitn Split-and-Merge ist ein

Segmentierungsverfahrenn unterteilt das Bild erst in Regionen (Split)n fügt dann die Regionen, die einem

bestimmten Kriterium genügen, zusammen(Merge)

n ist rekursiv aufgebautn Regionen werden in Teilregionen unterteiltn maximale Auflösung der Teilregionen wird

gewährleistetn Rechenzeit ist hoch

Danke für Ihre Aufmerksamkeit!!