www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Polygon ausdünnen


Autor: Miriam (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Thomas (Gast)
Datum:

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

Autor: Roland Praml (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
DouglasPeucker Algorithmus?

Autor: Miriam (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Miriam (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>überall 1mm nach innen verschoben
fürs Beispiel meinte ich 2mm...

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Miriam (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Miriam (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht 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.

Autor: Miriam (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Miriam (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Holger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Miriam (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.