Ähnlichkeit zweier Polygone bestimmen

  • VB.NET
  • .NET (FX) 4.5–4.8

Es gibt 50 Antworten in diesem Thema. Der letzte Beitrag () ist von Mokki.

    Ähnlichkeit zweier Polygone bestimmen

    Hallo Leute,
    also meine Frage ist, wie sie bereits im Titel steht, wie kann ich die Ähnlichkeit zweier Polygone bestimmen ? (prozentual)

    Ansätze:
    1. Flächeninhalt der beine Polygone vergleichen -> sehr ungenau, abhängig von Größenveränderung (de.mathworks.com/matlabcentral…ilarities-in-two-polygons)
    2. Hausdorff- oder Hamming- Distanz -> abhängig von Rotation (www8.cs.umu.se/kurser/TDBAfl/V…ms/BOOK/BOOK5/NODE196.HTM)
    3. Hue-Momente berechnen und vergleichen -> verstehe ich nach längerem Lesen immer noch nicht (docs.opencv.org/2.4.8/modules/…criptors.html#matchshapes)
    4. In Vektor-Kette mit komplexen Zahlen umwandeln und vergleichen -> würde funktionieren(versucht), aber hat Copyright (codeproject.com/Articles/19616…or-Image-Recognition-in-C)
    5. Nach diesem Video youtube.com/watch?v=AFEDUm4bPHk -> nicht prozentual
    6. Turning Functions -> Versteh' ich auch nicht (sites.google.com/site/turningfunctions/)

    Hat jemand noch bessere oder einfacher Ansätze oder Ideen zu diesem Thema oder würde mir 3. besser erklären ?
    Ich hoffe, ihr könnt mir helfen :)

    mfG Frank

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „xd-franky-5“ ()

    @xd-franky-5 Da musst Du zunächst definieren, was Du unter ähnlich verstehen willst.
    Für mich sind 2 Körper ähnlich, wenn sie durch Translation, Rotation und +-Vergrößerung ineinander übergehen.
    Die Vektorkette ist für mich ein Vergleich von Längen und Winkeln, ich kann nicht erkennen, dass es für einen solch elementaren Algorithmus ein Copyright geben soll.
    Die in diesem Artikel beschriebene Konturanalyse geht doch wohl weit über Dein Problem hinaus.
    Oder hast Du eine Winzigkeit in Deiner Problembeschreibung vergessen?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @RodFromGermany ich verstehe unter ähnlich, wenn die zwei Polygone unabhängig von Rotation, Skalierung und Position gleich "aussehen" (mir fällt kein besseres Wort ein. Vielleicht gleiche Winkel und Seitenlänge?). Ich weiß nicht, wie elementar das ist, weil das der einzige Beitrag mit dieser Vorgehensweise ist, den ich finden konnte und der Entwickler wahrscheinlich Wochen lang daran gearbeitet hat. Außerdem "This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)". Mein vorhaben ist ein Polygon mit einer Liste von anderen Polygonen zu vergleichen und das Ähnlichste (wie oben beschrieben) auszuwerten.
    Ich hoffe, ich habe nun alles richtig beschrieben :-/

    mfG Frank

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „xd-franky-5“ ()

    @xd-franky-5 Dann sehen wir beide das "gleich ähnlich". :thumbsup:
    Allerdings sehe ich bei dieser Aufgabenstellung, die gewiss älter ist als die elektronische Rechentechnik, immer noch keine Befürchtung wegen Copyright.
    Fang an bei einer Ecke und schreibe auf den Winkel zum anderen Schenkel und die Länge, die packst Du in eine geeignete Klasse mit einer List(Of Tuple(Double, Double)) und machst da eine "Endloskette" draus.
    Dranhängen eines Faktors
    oder
    kürzestes Element = 1 oder oder oder...
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @RodFromGermany klingt ja fast schon zu einfach, warum wurde das nirgendwo erwähnt? Ich habe dann ja zwei Listen, wie vergleiche ich die nun so, dass ich eine Zahl zwischen 0 und 1 rauskommt? Außerdem, wie mach ich das unabhängig von Skalierung?

    EDIT: Außerdem, wegen der Rotation, ich müsste dann ja von jedem Startpunkt aus anfangen zu vergleichen. Also wenn ich 30 Ecken in meinem Polygon habe, muss ich 30 Listen machen. Für das andere Polygon reicht eine Liste, die ich dann mit allen 30 vergleiche.

    Mit freundlichen Grüßen Frank

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „xd-franky-5“ ()

    xd-franky-5 schrieb:

    wie mach ich das unabhängig von Skalierung?

    RodFromGermany schrieb:

    kürzestes Element = 1
    Dann musst Du sie nur noch so umordnen (von vorn nach hinten dran hängen), dass das erste Element das kürzeste ist (bei einem Rechteck gibt es da zwei Möglichkeiten).
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    xd-franky-5 schrieb:

    Außerdem, wie mach ich das unabhängig von Skalierung?

    RodFromGermany schrieb:

    Dranhängen eines Faktors
    oder
    kürzestes Element = 1 oder oder oder...


    Rods Vorschlag kommt aber imo sehr schnell an seine Grenzen, wenn beispielsweise nicht mehr die gleiche Anzahl an Eckpunkten gegeben ist, sondern z.B. ein weiterer, von der bisherigen Geraden nur geringfügig abweichender Eckpunkt eingefügt wurde.
    Insgesamt entspricht das ziemlich genau dem, was in dem von dir verlinkten Video gemacht wird und kann einfach verwendet werden, um identische Polygone unabhängig von Rotation und Skalierung zu bestimmen. Wenn du nach der Methode aber die Ähnlichkeit bestimmen willst, dann resultiert das mMn letzten Endes wieder in dem Codeproject-Artikel, siehe (hinsichtlich der unterschiedlichen Längen der Konturen) z.B. dort auch der Absatz "Equalization of Contours"

    EDIT: Part 1 wurde ja schon beantwortet.
    Die Herangehensweise, das kürzeste Element als Teil 1 zu verwenden, funktioniert ebenfalls bei identischen Polygonen wunderbar, stößt aber ebenfalls an seine Grenzen, wenn z.B. beim ähnlichen, aber nicht identischen Referenzpolygon eine andere Seite kürzer ist. Ggf. müsste man da halt mehrere, ähnlich kurze Seiten ausprobieren.

    @RodFromGermany Mit dem ersten bin ich einverstanden, aber mit dem umordnen nicht. Denn jedes Polygon ist gleich lang, diese werden auch nicht immer genau vermessen, bei einem Polygon das einem H ähnelt, kann das kürzeste Element auch mal wo anders sein wenn man es etwas neigt etc. Am beste wäre es glaube ich doch, das Polygon in 30 verschiedene Listen mit je einer Rotation mehr aufzuteilen oder was meinst du ?

    EDIT: @BjöNi habe deinen Beitrag noch nicht bekommen, ups. Ja also meine Polygone sind bereits alle gleich lang. Und zu deinem Edit hab' ich ja hier etwas dazu gesagt.

    xd-franky-5 schrieb:

    aber mit dem umordnen nicht.
    Warum nicht?
    Es ist doch egal, welche Ecke "1" heißt.
    =================
    @BjöNi Wenn die Anzahl der Eckpunkte nicht gleich ist, verstößt dieser Sachverhalt gegen das 1. Ähnlichkeitspostulat.
    Wenn hier ähnliche Konturen unter der Nebenbedingung unterschiedlicher Anzahl an Eckpunkten behandelt werden soll, ist das eine völlig neue Aufgabenstellung, zu der ich mich nicht positioniert habe.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @RodFromGermany wie jetzt, die Ecke heißt 1 oder ist 1 lang oder an 1. Stelle ? :D Ich komm' nicht mehr mit, ich habe das jetzt so aufgefasst, dass das kürzeste Element 1 lang ist und somit an die erste Stelle rotiert wird um die Sache rotationsinvariant zu machen, aber das ja nicht wirklich geht, da auch manchmal ein anderes Element das kürzeste sein kann :-S

    xd-franky-5 schrieb:

    da auch manchmal ein anderes Element das kürzeste sein kann
    Nein.
    Per Definition ist das kürzeste an der Position 1.
    Sind mehrere gleich kurz, müssen wir einen anderen Ansatz definieren, weil

    RodFromGermany schrieb:

    bei einem Rechteck gibt es da zwei Möglichkeiten
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Hi
    bestimme einfach die Linien, entlang derer sich die Polygone aufspannen. Das H setzt sich bspw. durch drei Strecken zusammen: Die beiden vertikalen Linien und die horizontale, die mit den beiden vertikalen optimalerweise in der Mitte verbunden ist. Damit tust du dir wesentlich leichter, bzw. derjenige, der dir den Algorithmus dann letztendlich mit einer dir passenden Lizenz implementiert.

    Viele Grüße
    ~blaze~

    @RodFromGermany welche Definition? Ja dann definieren wir mal einen anderen Ansatz, denn es wird auf jeden Fall so sein, dass das Referenzpolygon ein anderes kürzestes Element haben kann wie das ermittelte Polygon.

    @~blaze~ das "H" war nicht "eindimensional" gedacht, tut mir leid, war mein Fehler. Es sieht eher wie in dem Beitrag aus, ich kann ja mal ein Bild davon anhängen. Die haben immer die gleiche Länge, in meinem Fall habe ich sie mit 30 bestimmt.

    EDIT: Das Sample ist das derzeitig-ermittelte Polygon. Das Template ist hier ein vorher ermitteltes Polygon, welches gespeichert wurde in eine Datenbank o.ä. und als am ähnlichsten berechnet wurde.
    Bilder

    • Screenshot_1.png

      32,96 kB, 154×357, 133 mal angesehen

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „xd-franky-5“ ()

    xd-franky-5 schrieb:

    welche Definition?

    RodFromGermany schrieb:

    Da musst Du zunächst definieren, was Du unter ähnlich verstehen willst.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @~blaze~ mhm okay. Also Vektorrechnung hatten wir in der Schule noch nicht, aber ich habe den Beitrag mit den Vektorketten, den ich verlinkt habe versucht zu verstehen (auch mit meinem Mathe-Lehrer). Ist dein Plan ungefähr so wie dort? Du kannst ihn ja mal genauer beschreiben, Schrittweise wäre am Besten :)

    <p>

    RodFromGermany schrieb:

    Wenn hier &auml;hnliche Konturen unter der Nebenbedingung unterschiedlicher Anzahl an Eckpunkten behandelt werden soll, ist das eine v&ouml;llig neue Aufgabenstellung, zu der ich mich nicht positioniert habe.
    </p>

    <p>

    RodFromGermany schrieb:

    xd-franky-5 schrieb:

    welche Definition?

    RodFromGermany schrieb:

    Da musst Du zun&auml;chst definieren, was Du unter &auml;hnlich verstehen willst.
    </p>

    <p>Ganz genau das ist das Problem, weshalb hier alle aneinander vorbeigeredet hatten. Ich hatte es eben so aufgefasst, dass zwei Polygone auch (nach seiner Definition) &quot;&auml;hnlich&quot; aussehen k&ouml;nnen, wenn die Anzahl der Eckpunkte nicht identisch ist. Scheint aber ja nicht der Fall zu sein.</p>

    ~blaze~ schrieb:

    Es lassen sich dennoch Linien durch das Polygon ziehen, die den "Grundbau" des Hs beschreiben. Und die verlaufen, abgesehen von Rotation, Translation usw. immer gleich. D.h. elementare Vektorrechnung mit Toleranz genügt zum Bestimmen, sobald du auf die "Knochen" kommst.
    Das ist zwar sicher bei OCR ein guter und richtiger Ansatz (ist ja auch in dem Artikel von der schwedischen Uni erwähnt)
    Comparing Skeletons
    A more powerful approach to shape similarity uses thinning to extract a tree-like skeleton for each object. This skeleton captures many aspects of the original shape. The problem now reduces to comparing the shape of two such skeletons, using such features as the topology of the tree and the lengths/slopes of the edges. This comparison can be modeled as a form of subgraph isomorphism, with edges allowed to match whenever their lengths and slopes are sufficiently similar.
    erscheint mir hier aber viel zu kompliziert, da die Anzahl der Ecken und scheinbar auch die grundsätzliche Positionierung der Ecken identisch ist (d.h. es fehlt nicht beim Polygon P' auf der einen Seite eine Ecke, dafür hat es auf der anderen Seite eine mehr).

    xd-franky-5 schrieb:

    Am beste wäre es glaube ich doch, das Polygon in 30 verschiedene Listen mit je einer Rotation mehr aufzuteilen oder was meinst du ?
    30 verschiedene Listen bauchst du dafür nicht, beim Vergleich der zwei (!) Listen musst du halt eine Rotation implementieren. Sinnvollerweise (zwecks Effizienz) würde ich die Referenzpolygonliste so sortieren, dass sie mit dem kürzesten Element anfängt, und die anderen Rotationen nach aufsteigender Anfangselementlänge durchprobieren:
    Referenzpolygon R
    (kürzeste Seite A an Position 1)
    		Vergleich #1 mit R => kein Match
    (beginnend mit kürzester Seite C)
    		Vergleich #2 mit R => Match
    (beginnend mit 2.kürzester Seite A)
    A 1,1
    B 5,2
    C 1,2
    D 9,0
    		C' 1,0
    D' 9,1
    A' 1,1
    B' 5,3
    		A' 1,1
    B' 5,3
    C' 1,0
    D' 9,1

    So musst du nicht alle 30 Rotationen durchprobieren, sondern normalerweise nur 1-3, bzw. du kannst auch z.B. einschränken, dass du nur die ersten 5 Rotationen durchprobierst und danach davon ausgehst, dass es nicht passt - respektive davon ausgehen, dass du z.B. nach einem Match über einem bestimmten Wert keinen weiteren, besseren mehr finden wirst. Würde natürlich auch identisch nach Winkelgrößen statt nach Längen sortiert funktionieren (ist aber eigentlich erstmal irrelevant, da es wie gesagt nur die Effizienz betrifft).

    xd-franky-5 schrieb:

    Hm was mach ich nun?
    Erneut davon ausgehend, dass Anzahl und Positionierung der Ecken identisch ist, würde ich erstmal einfach nur die Differenzen der Winkel sowie die der Längen zusammenrechnen und mir anschauen. Abhängig von deinen Anforderungen kannst du dann die Differenzen von Winkeln bei längeren Seiten höher gewichten als die bei kürzeren Seiten etc. Letzten Endes kannst du aber keine lineare Skala von 0-100% bilden (100% ist klar, absolut identisch, aber 0% gibt es so nicht. Es gibt ja immer ein noch weiter abweichendes Polygon). Da du aber wohl nur eine Gewichtung brauchst würde ich die Skala wie oben geschrieben umdrehen und nach oben offen gestalten, d.h. je geringer die Differenz, desto größer der Match.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „BjöNi“ ()

    @BjöNi
    "Anzahl und Positionierung der Ecken identisch", die Anzahl der ECKEN ist identisch, ja. Aber die Positionierung nicht, außer ich definiere Positionierung anders. Ich versuche es nochmal zu formulieren:
    Wir haben ein gespeichertes Vergleichspolygon und ein live-ermitteltes Polygon.
    Beide haben IMMER die selbe Anzahl an Ecken.
    Beide können unterschiedlich skaliert sein.
    Beide können unterschiedlich rotiert sein.
    Beide können unterschiedlich positioniert sein.
    Es kann vorkommen, dass es mehrere "kleinste Seiten" gibt.

    Dennoch sind zb. diese beiden Polygone zu 95% identisch:

    Obwohl eventuell bei dem einen eine andere Seite die kleinste ist, ein paar Ecken einen leicht anderen Winkel aufweisen, oder das gesamte Muster um ca. 45° rotiert ist und etwas kleiner/größer ist.

    Die 30 Listen waren auch nur theoretisch, ich meinte natürlich 30 mal rotieren. Trifft dein Lösungsvorschlag nun noch immer auf mein Problem zu? Wenn ja, bin ich immer ein großer Freund von Pseudo-Code oder der ähnlichen :)

    mfG Frank

    EDIT: habe mich im ersten Satz verschrieben, natürlich ist die Anzahl der ECKEN identisch

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „xd-franky-5“ ()