Patternmatching

[TakaBo]

Hi Leute,

hab ein kleines Programmier-Problem, welches nicht so recht in die anderen Foren passen will. Vielleicht weiß ja jemand Rat?

Aus einem Bild habe ich ein Objekt vom Hintergrund segmentiert. Nach einigen Arbeitsschritten habe ich eine ein Pixel breite, geschlossene Kontur , die die Grenze zwischen Objekt und Hintergrund beschreibt. Danach wird das ganze vektorisiert und die Ecken im Objekt gesucht. Für jede Ecke gibt es nun ein Trippel (x,y,z), wobei x und y die Position der Ecke im uv-Raum angeben und z die normierte Entfernung zum Objektmittelpunkt (also 0.0=Objektzentrum, 1.0=Maximale Entfernung zum Zentrum).

Mein Problem ist nun: Wenn ich zwei Bilder mit ähnlichen Objekten habe, die mir die gleiche Anzahl von Ecken liefern, dann sollen die Ecken des einen Objekts zu den Ecken des anderen Objekts zugeordnet werden. Das Problem ist, daß die Liste mit den Trippeln nicht unbedingt nach irgendwas geordnet sein muß.

Mein erster Versuch war es Prädikate für die Beziehung der einzelnen Punkte untereinander zu finden, z.B. "ist linker/rechter und oberer/unterer Nachbar von". Durch Permutation und Fehlerbestimmung würde man dann zu einem optimalen Ergebnis kommen. Leider hat die Sache einen Haken, denn bei 11 Eckpunkten erhält man ein paar millionen Permutationen. Also nicht die ideale Lösung.

Für Vorschläge dankbar,
TB

[Manuel]

Hi TakaBo!

Programmierst du das mit C++? Hast du sonstige Zusätze? Beispielsweise GIMP oder OpenGL?

Dein Problem kann ich mir recht gut vorstellen. Hast du vielleicht ein paar Beispielbilder?
Wie hast du die Bilder erkannt? Hough-Transformation?

Ich würde es mal versuchen, indem ich in einer Schleife durch alle Pixel p im Bild laufe und dann den obersten linken selektiere. Dabei musst du dann natürlich eine Priorität angeben, ob oben oder links genommen wird.

Aber wie gesagt, zeig mal 2 Bilder, dann denk ich mal drüber nach

Lg,
Manuel

[TakaBo]

ReHi,

das ganze wird in C++ programmiert. OpenGL wird später zur Visalisierung benutzt. Ansonsten gibt es da noch die CxImage-Klasse, die einige Bildverarbeitungsoperatoren zur Verfügung stellt.

Wie hast du die Bilder erkannt? Hough-Transformation?

Nein. Mit der Hough-Transformation funktionierte das nicht. Gab nur Probleme, da man schon vorher Annahmen darüber machen muß, welches Objekt man hat. Bei mir wird eine sogenannte Zwei-Ebenensegmentierung verwendet (grob gesagt: Kantendetektion über Sobel, Delaunay Triangulation des Kantenbildes, Zusammenfügen der einzelnen Dreiecke unter bestimmten Kriterien wie z.B. Farbwinkel, Helligkeit usw. Löschen von Dreiecken, die nicht zum Cluster gehören, also Hintergrund sind. Übrige Dreiecke ohne Nachbarn sind Randdreiecke und bilden mit einer Seite die Außenkante). Vorteil: Das Objekt besitzt einen geschlossenen Kantenzug.

Aber wie gesagt, zeig mal 2 Bilder, dann denk ich mal drüber nach

Biddeschön



Blau=gefundenen Ecken
Grün=Objektschwerpunkt/Zentrum

Oh warte... warum beschränke ich mich da? Ich weiß doch wie die ganze Schose untereinander Verbunden ist. Das kann ich ja aus der Segmentierung entnehmen. Moment (zeichne...)



D.h. in diesem Fall habe ich 12 Punkte, wobei ich immer den nächsten Nachbarpunkt kenne. Mal angenommen ich sortiere die Tabelle entsprechend nach den Nachbarpunkten, wobei mit irgendeinen Punkt angefangen wird. Wichtig in der nachfolgenden Betrachtung ist die Entfernung der Punkte zum Schwerpunkt des Objekts. Was man erhält, könnte man als Objektsignatur bezeichnen.

Man erhält z.B. für das obrige Beispiel zwei Tabellen: A und B.
Jeder Eintrag in den Tabellen wird miteinander verglichen, also
A.1 mit B.1, A.2 mit B.2 usw. und ein Fehlerquotient berechnet.
Danach wird z.B. Tabelle B um einen Eintrag weiter rotiert, sodaß B.1=B.2, ... B.n=B.1. Danach wieder Fehlerquotient berechnen usw. , bis B einmal durchrotiert wurde. Die Rotation mit dem geringsten Fehler müßte theoretisch die gesuchte Lösung sein.

Aufwand Pi mal Auge O(n^2+c).

Muß ich mal testen Finde ich genial, wie man durch Erklären des Problems zur Lösung kommt.

Gruß TB

[Manuel]

*lach*

So gehts natürlich auch

Also mit Fehler meinst du die Entfernung der Punkte aus den Tabellen?
Nun ja, wenn du eine Liste hast, dann hast du als nächsten Punkt ja immer den daneben liegenden und es ist doch dann nur wichtig, dass du den ersten Punkt findest und dann beide dementsprechend anordnest, oder darf sich der Polygonzug auf verändern?

@Hough: Stimmt...ist schon so lang her wieder...Kantendetektion mit Sobel sagt mir auch was, müsste ich aber mal wieder nachlesen...*schäm*

Also sag einfach mal bescheid, obs so geklappt hat wie du es dir gedacht hast. Sonst schaun wir mal

Lg,
Manuel

[TakaBo]

Nabend,

Also mit Fehler meinst du die Entfernung der Punkte aus den Tabellen?

Ja genau. Jeder Punkt hat eine Entfernung zum Objektzentrum. Das ganze läßt sich dann normieren. Der Quadratische Fehler für jede Verschiebung läßt sich wie folgt berechnen (theoretisch): F=sqrt( (A.1-B.1)^2+(A.2-B.2)^2+..+(A.n-B.n)^2 )

Dazu als Beispiel ein Bild:



Die Ordinate bezeichnet den Abstand des Punktes zum Objektzentrum, die Abszisse bezeichnet die Position in der Tabelle. Die gelbe Linie ist meinet wegen die Abbildung von Tabelle A und die grüne Linie entsprechend B. Das erste Diagramm hat mit der Verschiebung von B den geringsten Fehler, wobei die Entfernungen innerhalb gewisser Tolleranzen durchaus schwanken dürfen. Das zweite Diagramm wird hingegen einen wesentlich größeren Fehler produzieren, da B nicht die richtige Ausrichtung besitzt. So zumindest meine Theorie. Die Vergleiche müßten dann nur n mal gemacht werden, für n=Anzahl der Punkte. Das klingt auf jeden Fall besser als 39Millionen Vergleiche :D

Gruß TB

[Manuel]

sqrt( (A.1-B.1)^2

Also kurz gesagt der Betrag, der ja der Entfernung entspricht.

Aber mit O(n²) kann man leben. Was besseres fällt mir leider auch nicht ein. Einzige Möglichkeit wäre es halt, das nicht zu verschachteln...soll heißen, du sortierst es erst nach einer Möglichkeit und danach nach einer anderen. Denn das n² kommt ja genau von der Schleife in der Schleife. *überleg*

Muss der Algorithmus denn möglichst optimal sein? Wofür braucht man sowas wenn ich fragen darf?! Wusste gar nicht, dass du sowas beruflich machst...find ich ja cool!

Lg,
Manuel

[TakaBo]

Hi,

Aber mit O(n²) kann man leben.

Denke ich auch. Das sind bei 11 Punkten 121 Vergleiche+10 Verschiebungen, da man weiß, welcher Punkt nach dem anderen kommt. Also brauch man keine Permutationen, wie ich anfangs angenommen hatte.

soll heißen, du sortierst es erst nach einer Möglichkeit und danach nach einer anderen.

Hmm...Anstatt in der Schleife das zu erledigen, einfach plain alles nacheinander hinschreiben, verstehe ich Dich richtig? Würde an den Vergleichen aber nicht viel ändern.
Aber Du bringst mich auf eine andere Idee: Was ist, wenn man den Kurvenverlauf als kontinuierlich fortlaufende Funktion versteht und man z.B. einen Knuth-Morris-Pratt oder Boyer-Moore Algorithmus darauf anwendet? Einzige Abwandlung der Algorithmen wäre, daß man den Werten eine gewisse Tolleranz erlaubt, welche man aus Versuchen ermitteln könnte.

Mal als Beispiel ein Bild:


Das Ergebnis liegt dann im Beispiel oben vor, wenn man das zweite Muster um 9 Einheiten nach rechts verschiebt. Problematisch ist es natürlich die Tolleranz festzulegen. Zu groß oder zu klein gewählt und das Ergebnis würde nicht korrekt sein. Aber als Optimierungsversuch sicherlich eine Überlegung wert, da Komplexität von O(n+m). Da die zu durchsuchende Menge an Elementen maximal verdoppelt werden muß, aber sonst der Länge der zu suchenden Menge entspricht, wäre das für diesen Fall im Worst Case denke ich O( 2n+n ) bzw O( 3n ). Cool.

Muss der Algorithmus denn möglichst optimal sein? Wofür braucht man sowas wenn ich fragen darf?! Wusste gar nicht, dass du sowas beruflich
machst...find ich ja cool!

Bin angehender Dipl.Informatiker und für meine Dipl. Arbeit brauch ich das. Es geht darum ein Kleidungstück zu segmentieren, zu erkennen und für einen Texturatlas brauchbar zu machen, wobei der Benutzer möglichst wenig machen muß. Gute Ergebnisse sollte das ganze deshalb schon liefern und möglichst schnell sollte es auch gehen, da man das ganze sonst auch per Hand machen kann.

Gruß TB

[Manuel]

Interessanter Lösungsansatz!

Der wäre auf jeden Fall optimal. Vor allem da O( 3n ) = O(n)
Und besser gehts in diesem Fall wohl nicht.

Die beiden Verfahren die du da angesprochen hast sagen mir ehrlich gesagt gar nichts. Aber ich schau gleich mal bei wiki

Wie genau heißt denn das Studienfach? Denn als reiner Informatiker macht man solche Dinge doch normalerweise nicht, oder? Diplomarbeit muss ich bald auch schreiben. Bis dahin sinds aber glücklicherweise noch 2 Jahre. Ging es dir nach dem Grundstudium eigentlich auch so, dass du das Gefühl hattest, dass du eigentlich gar nichts weisst? Man ist allen Scheinen hinterher gejagd, aber wirklich anwenden usw. musste man es ja nie. Also zumindest nicht auf richtige Probleme...daher fällts sehr schwer, sich das alles zu merken und dann auf solche Ideen wie du sie hier gerade vorstellst zu kommen.
Aber okay, Übung macht den Meister, hm?

Lieben Gruß und viel Erfolg bei deiner Arbeit!!!
Manuel

P.S. Kannst immer gern noch andere Dinge zeigen und erklären. Dir kommt dabei die Erleuchtung und ich finds mega interessant und lern was dazu *g*

[TakaBo]

Vor allem da O( 3n ) = O(n)

Stimmt, ist mir gar nicht aufgefallen :o

Wie genau heißt denn das Studienfach? Denn als reiner Informatiker macht man solche Dinge doch normalerweise nicht, oder?

Ähm, doch Meinst Du ein "normaler" Diplom-Informatiker schreibt nur einfache Anwendungen für Banken? Man lernt im Diplom-Informatiker Studium in die Breite. Später hat man dann die Möglichkeit sich zu spezialisieren.

Ging es dir nach dem Grundstudium eigentlich auch so, dass du das Gefühl hattest, dass du eigentlich gar nichts weisst? Man ist allen Scheinen hinterher gejagd, aber wirklich anwenden usw. musste man es ja nie. Also zumindest nicht auf richtige Probleme...daher fällts sehr schwer, sich das alles zu merken und dann auf solche Ideen wie du sie hier gerade vorstellst zu kommen.

Oh ja, das scheint aber normal zu sein Bei uns hat man zwar versucht theoretische Informatik mit der praktischen Informatik zu verknüpfen, aber die Kommunikation zwischen beiden Professoren lief wohl nicht so glatt, wie geplant Unser PI-Prof wollte sich ein Denkmal setzen und meinte 4 Semester in eins zu komprimieren (Automaten in Java fürs erste Semester, heavy) Im Endeffekt kommt es nicht so darauf an, wirklich über alles bescheid zu wissen. Wichtiger ist es schonmal davon gehört zu haben, gemäß dem Satz:"Es ist nicht wichtig alles zu wissen, man muß nur wissen wo es geschrieben steht".
Hilfreich ist es, wenn man sich selbst praktische Anwenungsmöglichkeiten zu theoretischen Konstrukten überlegt. Oft kann es auch helfen, wenn man Bücher nochmal überfliegt, um Wissen nochmal aufzufrischen, oder sich Bücher besorgt, die nicht vom Prof vorgeschlagen wurden. Es gibt nämlich gute Bücher die sowohl theo als auch Praxis miteinader in Beispielen verknüpfen. Schon wird so manches, was sich hinter Formeln und Lemmas versteckt klar und deutlich.

Kannst immer gern noch andere Dinge zeigen und erklären. Dir kommt dabei die Erleuchtung und ich finds mega interessant und lern was dazu

Klar, gerne doch. Es ist auch für mich sehr interessant, da man durch Diskussionen über ein Thema auf neue Richtungen und Ideen gestoßen wird, auf die man sonst im stillen Kämmerlein nie gekommen wäre.

Gruß TB