Krümmung einer Linie

[Medium]

Aloah!

Ich zermürbe mir gerade die Birne. Ich habe hier Listen von zusammenhängenden Punkten (Integer-Koordinaten), die jeweils eine wie-auch-immer geformte Linie bilden. (Sie sind das Ergebnis einer Kantenerkennung.)

Nun muss ich diese Linien auf "interessante" Punkte reduzieren, wobei interessant hier heisst, dass ein bedeutsamer Richtungswechel passiert. Dabei bereitet mir u.a. Probleme, dass bei den int-Koords von einem Pixel zum nächsten ja schon nur noch 45°-Schritte passieren, also muss ich die Tangenten schon mal über die Punkte um einen Probanden herum approximieren. So weit so schlecht!

Eine Richtungsänderung muss nicht zwangweise abrupt von statten gehen, sondern es können auch mehr oder weniger lang gezogene Kurven auftauchen, so dass ich nicht einfach die geschätzten Tangenten benachbarter Punkte vergleichen kann. Diese sind in solchen fällen nämlich immer sehr ähnlich, auch wenn das gesamte Gebilde gerade dabei ist eine 90° Kurve zu machen.

Wenn ich aber nun vom Punkt 0 die Tangente schätze, und dann immer mit dem Winkel der Geraden zwischen Punkt 0 und dem aktuellen vergleiche, gehen mir zum Teil kleinere Unebenheiten flöten, z.B. ein kleiner dreieckiger Ausreisser in einer längeren Kurve. Das verschlimmert sich zudem mit zunehmendem Abstand von Punkt 0.

Ich komme also mit der lokalen Krümmung nicht weiter, da diese eben klein sein kann, dafür aber über lange Strecken. Sowas muss ich auch unterteilen. Ich kann auch nicht von der Gesamtkrümmung ab Anfang arbeiten, weil mir dann lokale (aber wichtige) Details durch gehen.

Ich suche daher also nach einem Verfahren, dass mir Punkte liefert, die die gegebene Punktliste quasi ausreichend Annähert. Wären diese Listen Splines, ließe sich da mit Optimierungsverfahren was machen, aber es sind halt einfache diskrete Listen. (Und nein, diese vorher in Splines zu verwandeln ist kein weg. Zumal es durchaus eine ähnliche Problematik ergäbe.)

Help?

[Luckie]

Ich kann dir zwar nicht helfen, aber ich bnin mir sicher, dass diejengen, die helfen können und wollen, am liebesten ein paar Bilder sehen wollen. Also das Ausgangsbild, die Punkte und was du haben willst.

[Medium]

Da könntest du nicht Unrecht haben . Ich habe aber gerade eine blendende Idee, weswegen ich die Frage zunächst einmal auf Eis legen möchte. Sobald ich das probiert hab stell ich die eventuelle Lösung natürlich hier ein. Wenn ich mich jetzt nur noch dran erinnern könnte, wie man einfach 2 Geraden im R2 schneidet... es ist echt zu spät!

[alzaimar]

Hi Medium,

vor gefühlten 100 Jahren habe ich ein ähnliches Problem für das Bundesamt für Materialprüfung gelöst. Dort wurden Biegungskennlinien von künstlichen Gelenken erfasst. Dabei sollte die Punkteschar, die in etwa einer Hystherese gleicht, auf die relevanten Punkte reduziert werden. Eine Ecken/Kantenerkennung habe ich damit jedoch nicht hinbekommen, dazu bedarf es vermutlich eines anderen Verfahrens.

Meins war sehr einfach gestrickt. Ausgehend von N Punkten habe ich immer einen Punkt entfernt, und zwar den, bei dem sich das Gesamtbild der Kurve durch Wegnahme nicht wesentlich geändert hat. Das "Gesamtbild" der Kurve ist eine Ausgleichsspline. Ich gehe also alle Punkte durch (2..N-1) und erstelle für die jeweils N-1 Punkte (Also alle ohne den Kandidaten) einen Ausgleichsspline und schaue nach, ob und wie genau dieser Ausgleichsspline den weggenommenen Punkt approximiert. Von allen Kandidaten eliminiere ich nun den, der am 'unwichtigsten' ist.

Das wiederhole ich so lange, bis ich keinen Punkt mehr entfernen kann, ohne das Gesamtbild wesentlich zu verändern. Das hat bei hinreichend glatten Kurven erstaunlich gut funktioniert.

Du könntest hier ähnlich vorgehen: Nimm Dir einfach immer M aufeinanderfolgende Punkte und prüfe, ob die durch die M Punkte führende Ausgleichsgerade durch Wegnahme einzelner Punkte wesentlich verändert wird. Wenn nicht, sind diese Punkte eben 'unwichtig', tragen also nicht wesentlich zur Beschreibung der Form bei.

[Medium]

Hey! Das klingt doch sehr nach dem was ich hier vor habe! Die Kantenerkennung an und für sich ist ja bereits abgeschlossen, daher hab ich ja die Linien. (Ist ein Canny-Edge-Detector.)

Deteilfrage: Wie komme ich mathematisch an ein Maß für "nicht wesentlich verändert"?


Meine Idee gestern Nacht war genau anders herum angesetzt: Nicht schrittweise durch Löschung "vergröbern", sondern verfeinern. Ich dachte mir folgendes:
1) Eine Strecke zwischen Punkt 0 und Punkt N-1 einer Kurve
2) Finde den Punkt der Kurve, der von dieser Strecke am weitesten weg ist
(Man muss nur drauf achten, dass man wenn man zwar die Gerade, nicht aber die begrenzte Strecke trifft die Abstände mit den Endpunkten der Strecke bildet - aber machbar.)
3) Diesen Punkt p aufnehmen, und dann rekursiv ab 1) mit Punkt P(0)/p und p/P(N-1)
Das so lange, bis der weiteste Punkt eine Grenze unterschreitet.

Das wäre dann ein Divide-and-Conquer verfahren, und zumindest in Gedankenspielen könnte das auch was sein. Wie siehst du das? (Ich hab leider noch nicht die Zeit gefunden es auszuprogrammieren.)

[alzaimar]

Zitat von Medium:

Deteilfrage: Wie komme ich mathematisch an ein Maß für "nicht wesentlich verändert"?

Na, das wäre dann einstellbar. Du erleichterst Dir die Arbeit, indem Du z.B. einen Korrelationskoeffizienten verwendest und ein wenig rumexperimentierst. Meiner Erinnerung nach war das aber ziemlich unspezifisch. Das Verfahren war relativ robust ggü. der 'Empfindlichkeit'.

Zu Deiner Idee: Wenn Dur nur einzelne Bögen / Strecken hast, könnte das gut funktionieren. Sollte schnell umzusetzen sein. Man geht bei beiden Ideen aber davon aus, das die Endpunkte fix sind. Das führt zwar nicht zu optimalen Resultaten, sollte aber fürs Erste reichen.

[Medium]

Zitat von alzaimar:

Na, das wäre dann einstellbar. Du erleichterst Dir die Arbeit, indem Du z.B. einen Korrelationskoeffizienten verwendest und ein wenig rumexperimentierst. Meiner Erinnerung nach war das aber ziemlich unspezifisch. Das Verfahren war relativ robust ggü. der 'Empfindlichkeit'.

So ganz kann ich mir dadurch leider nicht vorstellen, wie sowas nun genau als Formel bzw. Algo auszusehen hätte. Ich kenne als Genauigkeitsmaß eigentlich nur das Quadratsummenverfahren, welches hier aber insbesondere durch die unterschiedliche Länge von Ausgleichsgerade und Kurve flach fällt. Auch wäre es verhältnismäßig langsam.

Aber: Ich hab nun meine Idee immerhin zu ca. 1/2 hingeschrieben, ich probier das jetzt einfach erst einmal. Ich hoff mal Von fixen Endpunkten kann ich übrigens ausgehen. Meine Kurven sind statisch sobald sie ein Mal stehen, also null Problemo.
Vom Klang her scheint mir deine Methode zwar "professioneller", aber wenn ich das richtig einschätze auch recht rechenintensiv. Ich wollte ganz gern für ein paar hundert Kurven im Bereich von 1s Laufzeit bleiben.

[alzaimar]

Hi Medium,

es ist ja schon bald 20 Jahre her, das ich das gemacht habe, und dann auch noch auf einer HP Workstation... Dein Verfahren müsste aber gut funktionieren. Ich war damals erstaunt, das ich die eine Kurve in ziemlich kurzer Zeit auf einem 4-10MHZ Motorola 68k hinbekommen habe.

Poste doch das Ergebnis hier. Würde mich interessieren.

[Medium]

Ich hab nun ein mehrstufiges gemischtes Verfahren gebastelt. Das was ich oben beschrieben hatte, liefert je nach Krümmung der Linie sehr instabile Ergebnisse auf längeren geraden Abschnitten, zum Teil auch direkt benachbarte Punkte auf schnurgerader Strecke.

Nun mach ich es so:
- Zwei mal jeden 2. Punkt aus der Liste entfernen, damit ich nachher nicht nur 0°/45°/90° zwischen zwei benachbarten Punkten habe. Die Genauigkeit der Linie ist danach eh noch viel zu hoch, daher kein zu goßer Verlust für meine Zwecke.
- Dann für jeden Punkt den Winkel den er mit dem vorausgegangenen, und dem nachfolgenden bildet bestimmen. Ist dieser kleiner als eine gesetzte Grenze, Punkt löschen. Das ganze so oft über die gesamte Liste, bis alle Fälle gekillt sind.
- ABER! Ich bräuchte schon noch auch auf geraden Teilen so ab und an einen Punkt. Das ist natürlich ein Sonderwunsch der mir auch erst beim Basteln auffiel. Daher lösche ich nur dann einen Punkt, wenn damit die Länge des resultierenden Segmentes eine weitere wählbare Grenze nicht überschreitet.

So muss ich nicht erst rechenintensiv und fehleranfällig Tangenten schätzen, und was ich bisher gesehen habe schaut recht brauchbar aus. Es ist wie so oft die gesunde Mischung - sogar bei Algorithmen Ich hoffe dass ich damit so weiter arbeiten kann. Danke dir für die Denkanstöße!