AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Delphi-PRAXiS - Lounge Klatsch und Tratsch Mathematik: Konturen (Punkte-Array) vergleichen

Mathematik: Konturen (Punkte-Array) vergleichen

Ein Thema von Matze · begonnen am 21. Nov 2018 · letzter Beitrag vom 17. Dez 2018
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.987 Beiträge
 
Turbo Delphi für Win32
 
#1

Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 06:44
Hallo zusammen,

ich stehe gerade vor einer kleinen Herausforderung:
  • Gegeben sind 2 Konturen als Punkte-Array, z.B. ein Array mit Elementen. Jedes Element enthält X- und Y-Koordinaten.
  • Die Konturen können beliebig sein (Kreis, Rechteck, Bezierkurven, ...)
  • Die Anzahl der Punkte beider Konturen muss nicht übereinstimmen.
    D.h. z.B. kann eine Rechteck-Kontur aus 4 Punkten bestehen, aber auch aus 100 verschiedenen.
  • Eine der beiden Konturen ist die Idealkontur bzw. Referenzkontur

Nun muss ich irgendwie überprüfen, ob die Konturen übereinstimmen mit einer gewissen Toleranz. Ich habe eine PDF angehängt, die das hoffentlich etwas veranschaulicht.

Im Internet stößt man immer wieder auf interessante Informationen, aber irgendwie kommt mir das alles zu kompliziert vor.
Beispiel: Konturen beschreiben & matchen

Habt ihr hier gute Ideen?

Grüße
Matze
Angehängte Dateien
Dateityp: pdf Kontur_Matching.pdf (205,8 KB, 27x aufgerufen)
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
459 Beiträge
 
Delphi 10.3 Rio
 
#2

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 08:00
1. Mach um jeden Punkt beider Konturen einen Kreis mit Radius=Toleranz
2. Bestimme für jede Kombination aus Kreis der Kontur 1 und Kreis der Kontur 2 die Schnittfläche.
3. Die Summe der Schnittflächen ist ein Maß für die Abdeckung.

Das ist beides einfache Mathematik + die Formeln sind leicht zu googeln.
Schritt 2 ist ein NxN Problem und laufzeitkritisch. Die Entscheidung, ob zwei Kreise sich überhaupt schneiden ist aber einfach zu treffen.

Du kannst das aber auch mit der Monte-Carlo-Methode machen. Dann nimmst du x zufällig verteilte Punkte und schaust, ob die innerhalb/außerhalb der beiden Konturen sind. Die Anzahlen geben dir wieder ein Maß für die Deckung.
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.987 Beiträge
 
Turbo Delphi für Win32
 
#3

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 08:35
Hallo TigerLilly ,

vielen Dank für deine Antwort!

Ich hatte gerade noch einen anderen Ansatz, der auch funktionieren könnte, aber mit O(n²) laufzeitkritisch ist.
Bei geschätzt max. 10000 Punkten müsste ich die Laufzeit aber mal messen.

Pseudo-Code:
Code:
foreach refPoint in refContour
{
    foreach (contPoint in contour)
    {
        if (contPointIndex > 0)
        {
            // Gerade aus den 2 Kontour-Punkten berechnen (aktueller + voriger Punkt)
            // Abstand refPoint zur Gerade berechnen
            // Wenn Abstand eines Punkts <= Toleranz: Ref-Punkt OK       }
}
Grüße
Matze

Geändert von Matze (21. Nov 2018 um 08:46 Uhr)
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
459 Beiträge
 
Delphi 10.3 Rio
 
#4

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 08:40
Naja, du hast mit Ähnlichkeiten zu tun, das heißt du brauchst kein entweder/oder sondern ein Maß.

Wenn deine Konturen bis auf 1 Punkt weitab deckungsgleich sind, würde dein Verfahren auf "ungleich" plädieren. Das möchtest du doch nicht, oder?
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.987 Beiträge
 
Turbo Delphi für Win32
 
#5

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 08:49
Wenn deine Konturen bis auf 1 Punkt weitab deckungsgleich sind, würde dein Verfahren auf "ungleich" plädieren. Das möchtest du doch nicht, oder?
Ich hatte noch einen Denkfehler drinnen und gerade oben korrigiert:
Wenn die Schleife beendet wird, sobald der Abstand zu groß ist, werden die Konturen nie übereinstimmen, da für alle Punkte der Abstand berechnet wird (und somit ein Rechteckpunkt oben links mit einem unten rechts verglichen wird, was die Toleranz überschreitet).

D.h. man muss die innere Schleife abbrechen, wenn der Abstand <= der Toleranz ist und mit der Info entsprechend weiter arbeiten.
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.452 Beiträge
 
Delphi 2007 Enterprise
 
#6

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 09:22
Pseudo-Code:
Code:
foreach refPoint in refContour
{
    foreach (contPoint in contour)
    {
        if (contPointIndex > 0)
        {
            // Gerade aus den 2 Kontour-Punkten berechnen (aktueller + voriger Punkt)
            // Abstand refPoint zur Gerade berechnen
            // Wenn Abstand eines Punkts <= Toleranz: Ref-Punkt OK       }
}
Grüße
Matze
Ich hatte für meine Abschlussarbeit mal ein Vektor-basiertes Kompressionsverfahren gebaut, welches ziemlich genau dieses Problem aufwarf: Nach der Kantenerkennung wollte ich die entstandenen Pfade zu Catmull-Rom-Splines mit möglichst wenigen Kontrollpunkten umwandeln. Dazu habe ich (rech verschwenderisch, aber darum ging es nicht) erstmal immer gesagt: Pfad = Splinepunkte, und dann einen Punkt im Spline entfernt, die Splines mit fixer Auflösung in eine temporäre Kurve überführt, und mit genau deiner Methode eine Metrik für Ähnlichkeit Kurve:Ursprungspfad gestrickt. Das ganze iterativ für alle Möglichkeiten durchgespielt (es war sicherlich NICHT schnell!), und den Punkt letztlich aus der Kurve gelöscht, durch den der geringste "Fehler" entstanden war. Das alles dann etliche Male wiederholt, bis eine empirisch ermittelte Fehlergrenze nicht mehr unterschreitbar war.

Die Ergebnisse waren wirklich gut, auch wenn der Ansatz nicht die optimale Lösung garantieren dürfte; es war aber mehr als gut genug und hat in nur wenigen Extremfällen Murks produziert. Was meiner Meinung nach aber Grundvoraussetzung für diesen Ansatz ist, ist eine bereits recht gute Ähnlichkeit der verglichenen Pfade von Anfang an. Wie sich das bei stark abweichenden Kurven verhält habe ich nie geprüft, da ich ja quasi andersherum gegangen bin und mit einem 100% Match angefagen habe.


Edit: Ouuu neee, das ganze war sogar nur eine Metrik um die Punktlöschung zu terminieren! Die Auswahl der Punkte habe ich anhand der Krümmung gemacht. Also immer den testweise gelöscht, bei dem die Krümmung im gesamten Spline die geringste war, und dann mit o.g. Methode gemessen ob ich das noch als "okay genug" bewertete und weiter versuchen will. Krümmung aus einer diskreten Punktmenge zu ermitteln war auch nicht unspannend

Edit 2: Was das ganze hier letztlich heißen sollte ist: Jup, ich halte das für einen guten Ansatz. Das Ergebnis mag nicht immer das Optimum sein, schneller geht es vermutlich auch irgendwie, aber es ist noch anschaulich und sicherlich schneller und leichter zu implementieren als andere potenzielle Verfahren (über die ich keine Kenntnis habe, und damals wie du auch keine so wirklich fand).
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)

Geändert von Medium (21. Nov 2018 um 09:32 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe
Online

Registriert seit: 20. Jan 2006
Ort: Lübbecke
6.554 Beiträge
 
Delphi 10.3 Rio
 
#7

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 09:40
Nur so als extreme Testfälle.

Fall 1: Referenzkontur 1 ist ein Rechteck aus 4 Punkten, Kontur 2 ein Kreis aus 360 Punkten, der genau durch die Eckpunkte des Rechtecks geht.

Fall 2: Das gleiche Beispiel, aber diesmal ist der Kreis die Referenzkontur.

Der Algorithmus müsste in beiden Fällen keine Übereinstimmung auswerfen.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.987 Beiträge
 
Turbo Delphi für Win32
 
#8

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 09:43
Hallo,

danke auch für eure Antworten.

Jup, ich halte das für einen guten Ansatz. Das Ergebnis mag nicht immer das Optimum sein, schneller geht es vermutlich auch irgendwie, aber es ist noch anschaulich und sicherlich schneller und leichter zu implementieren als andere potenzielle Verfahren (über die ich keine Kenntnis habe, und damals wie du auch keine so wirklich fand).
Ich habe das gerade mal getestet mit 10000 Punkten und der Vergleich dauert mehrere Sekunden. Das ist leider untragbar, aber es funktioniert!

Der Algorithmus müsste in beiden Fällen keine Übereinstimmung auswerfen.
Tatsache, klasse Einwand!
Das würde heißen, man müsste das in beide Richtungen machen. Diese Grenzfälle habe ich gar nicht bedacht.
Wobei die Konturermittlung so viele Punkte setzt, dass die Kontur sichtbar korrekt ist. Ein Kreis hat somit (je nach Auflösung) immer deutlich mehr als 4 Punkte.


Hintergedanke ist es, bei einem Bildverarbeitungssystem Konturen zu bewerten. Da gibt es Möglichkeiten mit Bildvergleichen etc. (Dauer ca. 1 Sekunde). Ich war evtl. so naiv zu glauben, die paar mathematischen Berechnungen ohne Umweg über Bilder/Fotos seien schneller.

Kreise zu berechnen und Überschneidungen zu ermitteln würde das ganze vermutlich noch aufwändiger machen.
Aber ich kann mit der Bildverarbeitungsbibliothek zeitlich gerade so leben.

Aber tolle Vorschläge und Einwände von euch!

Grüße
Matze

Geändert von Matze (21. Nov 2018 um 09:45 Uhr)
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
459 Beiträge
 
Delphi 10.3 Rio
 
#9

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 10:15
Ich hab das mit den Kreisen mal gemacht, da ging darum, Fußabdrücke auf einer Sensormatte zur Deckung zu bringen. Die Mathematik ist nicht aufwendig + das geht sehr flott. Man musste die Fußabdrücke auch noch alle auf gleich drehen, aber das ist was anderes.

Aber wenn du eh was hast, das passt, dann isses gut.
  Mit Zitat antworten Zitat
TigerLilly

Registriert seit: 24. Mai 2017
Ort: Wien, Österreich
459 Beiträge
 
Delphi 10.3 Rio
 
#10

AW: Mathematik: Konturen (Punkte-Array) vergleichen

  Alt 21. Nov 2018, 10:18
Nur so als extreme Testfälle.

Fall 1: Referenzkontur 1 ist ein Rechteck aus 4 Punkten, Kontur 2 ein Kreis aus 360 Punkten, der genau durch die Eckpunkte des Rechtecks geht.

Fall 2: Das gleiche Beispiel, aber diesmal ist der Kreis die Referenzkontur.

Der Algorithmus müsste in beiden Fällen keine Übereinstimmung auswerfen.
Naja, das muss nicht sein. Denn wenn du nur 4 Punkte hast, weißt du über die Kontur eigentlich nichts. Und dann ist die Frage, welches Maß für Ähnlichkeit man hat bzw was man als "ähnlich" definiert. Die Kreismethode würde in beiden Fällen eher "nicht ähnlich" liefern, weil es nur wenig Deckung gäbe.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 09:32 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf