Forum: Digitale Signalverarbeitung / DSP / Machine Learning Polygon ausdünnen


von Miriam (Gast)


Lesenswert?

Es gibt doch in Vektorzeichenprogrammen die Funktion, Polygone nach 
aussen oder innen zu "puffern", sprich alle Punkte hinzuzfügen oder zu 
löschen, die höchstens einen Abstand x vom Rand des Polygons haben.

Ich versuche, für eine Platinenbohrmaschine, deren Positionierung nicht 
ideal ist, über optische Rückkopplung die exakte Bohrlochposition zu 
treffen. Dazu muss ich u.a. aus dem von einer Kamera erfassten Verlauf 
der Leiterbahnen, deren Ränder (=die oben angesprochenen Polygone) exakt 
detektiert werden, die "Achse" dieser Leiterbahnen rekonstruieren, was 
darauf hinausläuft, diese Polygone überall gerade soweit auszudünnen, 
dass eine Linienstärke von 0 (bzw. ein Pixel, falls das pixelbasiert 
laufen muss) übrigbleibt.

Gibt es dafür einen Algorithmus, der sich auf DSPs verwenden lässt?

Er sollte auch in Kurven, Knicks und Abzweigungen funktionieren. Was bei 
Pads und Pins passiert, ist erstmal egal.

von Thomas (Gast)


Lesenswert?

Kennst du einen Gast namens "Gast"? Der versucht gerade genau das 
gleiche. Bzw. versucht es nicht mehr fg

von Roland Praml (Gast)


Lesenswert?

DouglasPeucker Algorithmus?

von Miriam (Gast)


Lesenswert?

>DouglasPeucker Algorithmus?

Nein, da habe ich mich unklar ausgedrückt. Mit Ausdünnen meine ich, dass 
die Polygonränder z.B. überall 1mm nach innen verschoben werden. Aus 
einem Rechteck von 100mm x 5mm wird dann eines von 96mm x 1mm. Es geht 
nicht darum, den Polygonzug auf weniger Punkte zu reduzieren (das ist 
bereits erledigt, wobei vielleicht Douglas-Peucker besser als mein 
Bruteforceansatz ist).

Dieses Ausdünnen wird fortgesetzt, bis das verbleibende Polygon zu einem 
Linienzug entartet. Beim Rechteck ist das trivial. Bei anderen Polygonen 
muss je nach lokalem Abstand zu den Rändern um einen unterschiedlichen 
Betrag ausgedünnt werden, was alles andere als trivial ist.

von Miriam (Gast)


Lesenswert?

>überall 1mm nach innen verschoben
fürs Beispiel meinte ich 2mm...

von Christoph Kessler (db1uq) (Gast)


Lesenswert?

Ich habe mal von ELV ein Programm zur Vektorisierung von Pixelgrafiken 
gekauft, das hatte zur Vorbearbeitung die Funktionen "Verdicken" und 
"Ausdünnen". Besonders gut hat das nicht funktioniert, die Hoffnung dass 
am Schluß eine dünne Linie herauskommt ist vergebens.

von Miriam (Gast)


Lesenswert?

Christoph, ich will dir ja nicht auf die Füße treten. Aber ich denke 
genau solche Beiträge sind es, die dazu führen dass Threads wie der zur 
paramtrierten Punktwolke ausufern. Ich habe den nach Thomas Kommentar 
gleich überflogen und muss sagen, dass ich die Entgleisungen des 
"Gast"es dort sehr gut nachvollziehen kann.

Du scheinst ein übertriebenes Mitteilungsbedürfnis zu haben.

von Christoph Kessler (db1uq) (Gast)


Lesenswert?

Tut mir leid, Miriam,
ich hatte den Eindruck, Thomas und Jorge wurden ähnlich behandelt wie 
ich, da erwacht mein Widerspruchsbedüfnis.

Wenn meine Äußerung nicht klar ist, das hier bezog sich auf "falls das 
pixelbasiert laufen muss". Eine Kamera liefert ein Pixelbild das 
irgendwann vektorisiert wird, die Verdünnung kann davor oder danach 
passieren.

von yalu (Gast)


Lesenswert?

> Es gibt doch in Vektorzeichenprogrammen die Funktion, Polygone nach
> aussen oder innen zu "puffern", sprich alle Punkte hinzuzfügen oder
> zu löschen, die höchstens einen Abstand x vom Rand des Polygons
> haben.

Schau doch einfach nach, wie die das machen. Z.B. in Inkscape, dort
heißt die Funktion Inset/Outset.

  http://www.inkscape.org

> ... was darauf hinausläuft, diese Polygone überall gerade soweit
> auszudünnen, dass eine Linienstärke von 0 ...

In Inkscape ensteht durch fortgesetztes "Ausdünnen" keine Linie,
sondern ein ein immer kleiner werdendes Polygon, das an Einschnürungen
irgendwann auseinanderbricht, d.h. in zwei nicht mehr verbundene
Polygone aufgeteilt wird.

> ... (bzw. ein Pixel, falls das pixelbasiert laufen muss)
> übrigbleibt.

In der pixelorientierten Bildverarbeitung heißen die Funktionen
Erosion und Dilatation. Darüber gibt's viel Information und sicher
auch fertige Algorithmen im Netz. Aber auch bei diesen Algorithmen
bleibt am Schluss nicht eine Linie stehen.

Wahrscheinlich ist die Skelettierung eher das, wonach du suchst. Ein
guter Startpunkt dafür ist könnte

  http://www.graphenreiter.de/skelettierung.html

sein. Skelettierung gibt's für sowohl Pixel- als auch für
Vektorbilder.

von Miriam (Gast)


Lesenswert?

>Wenn meine Äußerung nicht klar ist, das hier bezog sich auf "falls das
>pixelbasiert laufen muss". Eine Kamera liefert ein Pixelbild das
>irgendwann vektorisiert wird, die Verdünnung kann davor oder danach
>passieren.

Deine Äußerung ist immer noch wirr. Wen interessiert, dass es in der ELV 
mal ein Programm gab, das für mein Ziel nicht geeignet ist?

von Christoph db1uq K. (christoph_kessler)


Angehängte Dateien:

Lesenswert?

Das muß am Wetter liegen, dass einige heute so aggressiv sind...
Hier die Titelzeile des Programms, mit genau den Bezeichnungen, die yalu 
genannt hat, Erode, Dilate, Skelettieren, die waren mir entfallen.

von Miriam (Gast)


Lesenswert?

Liegt es auch am Wetter, daß du lernresistent bist?

Dein Programm INTERESSIERT MICH NICHT!

Meine Frage lautete "Gibt es dafür einen Algorithmus, der sich auf DSPs 
verwenden lässt?"

Mit den allerliebsten Grüßen,
Deine Miriam

von Christoph db1uq K. (christoph_kessler)


Lesenswert?

Das Programm ist auch völlig uninteressant, mir geht es um die 
Suchbegriffe für Google, der erste Schritt für eine erfolgreiche 
Internetrecherche.
"Erode Dilate Skeleton" in Google wirft jede Menge noch ziemlich 
ungeordneter Fundstellen aus, aber daraus kann man doch weitere 
Stichworte entnehmen.

von Miriam (Gast)


Lesenswert?

>Das Programm ist auch völlig uninteressant, mir geht es um die
>Suchbegriffe für Google

Aha und diese Suchbegriffe hast du mir hiermit
>Ich habe mal von ELV ein Programm zur Vektorisierung von Pixelgrafiken
>gekauft, das hatte zur Vorbearbeitung die Funktionen "Verdicken" und
>"Ausdünnen". Besonders gut hat das nicht funktioniert, die Hoffnung dass
>am Schluß eine dünne Linie herauskommt ist vergebens.
in mein Unterbewußtsein übertragen, ja? Kannst du das bitte nochmal lang 
und breit erläutern, damit ich a) es endlich verstehe und b) morgen früh 
was zu lachen habe?

von Holger (Gast)


Lesenswert?


von Miriam (Gast)


Lesenswert?

>Lese mal da nach Johnson algo.
>http://www.einfach-cnc.de/seiten/KnowHow_Platinen_...

Wie meinen?

Wolltest du artikulieren
"Lies mal, was dort zum Johnson Algorithmus geschrieben wurde."?
Das Wort Johnson taucht dort nur in Verbindung mit einem Programm zur 
Ausgabe von G-code auf. Ich sehe da keinen Zusammenhang. Auch hier 
nicht: http://de.wikipedia.org/wiki/Johnson-Algorithmus

von yalu (Gast)


Lesenswert?

Lass mich mal für Holger antworten, der nach deiner letzten Antwort
möglicher- und verständlicherweise keinen Bock mehr hat, weiter in
diesem Thread zu posten ;-)

> Wie meinen?

Wolltest du artikulieren
"Wie hast du diesen Satz gemeint?"?

> Wolltest du artikulieren
> "Lies mal, was dort zum Johnson Algorithmus geschrieben wurde."?

Ich glaube, genau das wollte Holger.

> Das Wort Johnson taucht dort nur in Verbindung mit einem Programm
> zur Ausgabe von G-code auf. Ich sehe da keinen Zusammenhang.

Ich schon.

Möglicherweise löst er dein Problem nicht (s. mein Beitrag weiter
oben), aber er bietet die Umsetzung für deinen in deinem ersten Post
ungeschickterweise (weil nicht zum Ziel führenden) vorweggenommenen
Lösungsansatz, und das sogar in Form von C-ähnlichem Quellcode.

Was erwartest du mehr?

> Auch hier nicht: http://de.wikipedia.org/wiki/Johnson-Algorithmus

Nein, hier wirklich nicht, das hat aber auch niemand behauptet.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.