© D. Schulz 1 Algorithmen der Objekterkennung. © D. Schulz 2 Überblick 1.Einleitung...

1© D. Schulz

Algorithmen der Objekterkennung

2© D. Schulz

Überblick

1. Einleitung2. Geländemodell: TINs3. Geomorphologische Grundbegriffe4. Erkennungsalgorithmus von

Wassereinzugsgebieten5. Visualisierung6. Erweiterungsmöglichkeit7. Praktisches Beispiel

3© D. Schulz

1. Einleitung

Digitale GeländemodelleWelche Informationen lassen sich extrahieren?

Interessant fürkostengünstige Netzplanungen, wie

Telekommunikationsnetze, Strassennetze

Durch geeignete Algorithmen können geomorphologische Geländeformen erkannt werden

4© D. Schulz

1. Einleitung

Planung mit knappen Wasserressourcen

In hydrologischer Hinsicht interessant für

Hochwasserprognosen, Ausweisung von Überflutungsflächen

Simulation von Schneeschmelze Visualisierung von Geländeprofilen,

Längsschnittbilanzen von Flussläufen Modellierung eines Niederschlag-Abfluss-Prozesses

5© D. Schulz

Graph bestehend aus Knoten und Kanten (implizit Dreiecke)

Höhe für jeden Punkt auf Geländeoberfläche berechenbar

Höhenwerte in Dreiecksknoten gespeichert

2. Geländemodell: TINs

TINs (Triangulated Irregular Neworks)

Als bevorzugtes Geländemodell für die Erkennung geomorphologischer Geländestrukturen

6© D. Schulz

Liegt Geländepunkt auf

Dreiecksfläche

2. Geländemodell: TINs

Höhenwert gegeben

Interpolation zwischen 3 Punkten

Dreiecksknoten

lineare InterpolationDreieckskante

7© D. Schulz

2. Geländemodell: TINs

Weiterer Vorteil eines TINs:Anpassungsfähigkeit an vorgegebene GeländesituationWeiterer Vorteil eines TINs:Anpassungsfähigkeit an vorgegebene Geländesituation

Integration von Landkarten

Weiterer Vorteil eines TINs:Anpassungsfähigkeit an vorgegebene Geländesituation

Integration von Landkarten

Kanten eines digitalen Flusslaufes können zu Kanten der Constraint Triangulation werden

8© D. Schulz

Grundstrukturen komplexere Zusammenhänge ableitbar

3. Geomorphologische Grundformen

Vorraussetzung einer automatischen Erkennung geomorphologischer Geländestrukturen:

genaue Formalisierung und Definitionen

9© D. Schulz

3. Geomorphologische Grundformen

3.1 Punkförmige Grundformen

Gipfel Mulde Pass

10© D. Schulz

3. Geomorphologische Grundformen

3.2 Linienförmige Grundformen

Diffluente Kante

Transfluente Kante

Konfluente Kante

11© D. Schulz

3. Geomorphologische Grundformen

3.3 AblaufpfadRhein MainMose

l

Saar

Maas Lahn

Nordsee

WeserEms

Koblenz

Der Ablaufpfad eines Punktes p beginnt in p und folgt solange der Richtung des grössten Gefälles, bis er einen Muldenpunkt erreicht hat.

12© D. Schulz

Lösung: p auf diffluenten Kante

Lösung: p auf Knoten mit Gefälle in

mehreren Richtungen

3. Geomorphologische Grundformen

3.3 AblaufpfadProblem: Richtung des grössten Gefälles nicht immer eindeutig!

2 Ablaufpfade

absolute Maximum der Gefälle auswählen

13© D. Schulz

3. Geomorphologische Grundformen

3.4 WassereinzugsgebietDas Wassereinzugsgebiet eines Punktes p umfasst alle Punkte, deren Ablaufpfad durch p geht.Wassereinzugsgebiet einer Mulde BeckenGrenze eines Beckens Wasserscheide

14© D. Schulz

Muldenpunkte auswählenUntersuchung der TIN-Knoten auf lokale Minima

Suchen der Ablaufpfade, die in einem Muldenpunkt enden1. Tiefensuche: Alle konfluente Kanten bergauf

zurückverfolgen besuchte Kanten und Knoten

markieren inzidente Dreiecksflächen markieren2. Tiefensuche: das gleiche für transfluente Kanten

die so markierten Dreiecke werden zu einem Wassereinzugsgebiet

zusammengefasst Durch Entfernen der Inneren Kanten entsteht die Wasserscheide

4. Erkennungsalgorithmus von Wassereinzugsgebieten

15© D. Schulz

Muldenpunkte auswählenUntersuchung der TIN-Knoten auf lokale Minima

Suchen der Ablaufpfade, die in einem Muldenpunkt enden konfluente Kanten bergauf zurückverfolgen

Alle besuchten Kanten und Knoten werden markiert + inzidente Dreiecksflächen

2. Tiefensuche für transfluente Kanten die so markierten Dreiecke werden zu einem Wassereinzugsgebiet

zusammengefasst

Durch Entfernen der Inneren Kanten entsteht die Wasserscheide

4. Erkennungsalgorithmus von Wassereinzugsgebieten

16© D. Schulz

4. Erkennungsalgorithmus von Wassereinzugsgebieten Dreiecke mit 1 Eingangskante und 2

Ausgangskanten können nicht immer genau einem Wassereinzugsgebiet zugeordnet werden!

17© D. Schulz

4. Erkennungsalgorithmus von Wassereinzugsgebieten

Lösung: Generierung von Pseudokanten

18© D. Schulz

4. Erkennungsalgorithmus von Wassereinzugsgebieten

Aufwand der BerechnungAufwand der Berechnung Für jedes dieser n Dreiecke könnte es 1 Pseudokante

geben. Jede dieser n Pseudokanten könnte jedes der n

Dreiecke einmal oder sogar mehrmals passieren.

Es könnten bis zu n³ Pseudokanten eingefügt werden müssen.

Aufwand der Berechnung Für jedes dieser n Dreiecke könnte es 1 Pseudokante

geben.

Aufwand der Berechnung Für jedes dieser n Dreiecke könnte es 1 Pseudokante

geben. Jede dieser n Pseudokanten könnte jedes der n

Dreiecke einmal oder sogar mehrmals passieren.

Aufwand der Berechnung Für jedes dieser n Dreiecke könnte es 1 Pseudokante

geben. Jede dieser n Pseudokanten könnte jedes der n

Dreiecke einmal oder sogar mehrmals passieren.

Es könnten bis zu n³ Pseudokanten eingefügt werden müssen. Methode bleibt aber praktikabel, da Aufwand in der Praxis deutlich geringer ausfällt.

19© D. Schulz

konfluentdiffluenttransfluent

konfluentdiffluenttransfluentPseudoZusatz

Muldenpunkt1. Ordnung2. OrdnungStart

50 m HöhenlinienPassMuldepunktGipfel

5. Visualisierung

20© D. Schulz

5. Visualisierung

21© D. Schulz

6. ErweiterungsmöglichkeitAlgorithmus erkennt auch Becken mit einer Tiefe im Zentimeterbereich

Generalisierung in Form von Filterung der Eingangsdaten

22© D. Schulz

7. Praktisches AnwendungsbeispielHochwassersimulation für

Bonn

23© D. Schulz