Mathematik: Konturen (Punkte-Array) vergleichen

[Medium]

Zitat von Matze:

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).

[Uwe Raabe]

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.

[TigerLilly]

Zitat von Uwe Raabe:

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.

[Uwe Raabe]

Zitat von TigerLilly:

Denn wenn du nur 4 Punkte hast, weißt du über die Kontur eigentlich nichts.

Der gezeigte Algorithmus geht von einer geraden Verbindung zwischen den Punkten aus - darauf bezog sich mein Einwand. Bei andersartigen Konturabschnitten (Kreisbogen, Bezier) kommt man mit zwei Punkten pro Anschnitt eh nicht aus und der Algorithmus müsste dann ganz anders aussehen.

[bcvs]

Mir fällt da folgender Ansatz ein:

Voraussetzung: Die Kontur ist durch Geraden zwischen den Konturpunkten definiert.

- Es wird eine innere und äußere Kontur gebildet, indem die Konturgeraden um das Maß der Toleranz nach innen bzw außen parallel verschoben werden.

- An den Knickpunkten werden die Schnittpunkte der neuen inneren bzw äußeren Konturgeraden bestimmt. Das sind dann die Eckpunkte der Toleranzfläche.

- Dann wird für jeden Punkt der zu prüfenden Kontur geprüft, ob er innerhalb der Toleranzfläche liegt. Dazu bildet man eine Gerade von dem zu prüfenden Punkt nach irgendwo ganz weit außerhalb und bestimmt die Anzahl der Schnittpunkte dieser Gerade mit der inneren und äußeren Kontur der Toleranzfläche. Ist die Anzahl ungerade, liegt der Punkt innerhalb der Toleranz.

[Uwe Raabe]

Zitat von bcvs:

- Es wird eine innere und äußere Kontur gebildet, indem die Konturgeraden um das Maß der Toleranz nach innen bzw außen parallel verschoben werden.

- An den Knickpunkten werden die Schnittpunkte der neuen inneren bzw äußeren Konturgeraden bestimmt. Das sind dann die Eckpunkte der Toleranzfläche.

Das hört sich einfacher an als es tatsächlich ist und kann ganz schön tricky werden, wenn durch die Parallelverschiebung und die Schnittpunktberechnung plötzlich ganze Teilstrecken verschwinden (gerade bei kurzen Teilstrecken im Verhältnis zum Toleranzwert). Diese Beispiel zeigt dabei noch einen relativ simplen Fall.

Die Abstandsberechnung ist da schon deutlich stabiler und vermutlich auch effizienter.

[Rollo62]

Hört sich nach Polygonen an, könnte sein das Clipper was dabei hat.
So in der Art, Schnittmenge o.ä.

Rollo

[ISMIRSCHLECHT]

Hallo,

ist das Problem noch relevant ?
Falls ja : Die Konturen ausfüllen (also doch als Bild) und nach "zweidimensionaler Kreizkorrelation" suchen.
D.h. beide Konturen sind dann Arrays mit den Werten 0 oder 1.
Die KKF wirkt Wunder

ISMIRSCHLECHT (ism)

[Matze]

Hallo

Zitat von ISMIRSCHLECHT:

ist das Problem noch relevant ?
Falls ja : Die Konturen ausfüllen (also doch als Bild) und nach "zweidimensionaler Kreizkorrelation" suchen.
D.h. beide Konturen sind dann Arrays mit den Werten 0 oder 1.
Die KKF wirkt Wunder

Sorry, aufgrund von Prüfungsstress habe ich ganz vergessen, mich nochmals zu melden.
Ich nutze nun die Bildfunktionen der bestehenden Bibliothek. Ich vermute, die arbeitet intern ähnlich oder nach KKF (Binärbild ist erforderlich), da das ausreichend flott ist. Aber sehr interessant zu wissen, was intern dahinter stecken könnte.

Euch nochmals vielen Dank.

[Matze]

Hallo,

danke auch für eure Antworten.

Zitat von Medium:

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!

Zitat von Uwe Raabe:

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