Forum: Mikrocontroller und Digitale Elektronik Datenvolumen reduzieren - Kreisparameter bestimmen


von Dieter B. (Gast)


Lesenswert?

Hallo:
Die Aufgabe, die mein Mikrocontroller erledigen muss ist folgende:

Die Lage und den Radius eines Kreises, der aus n Punkten (x,y) besteht 
zu übermitteln. (Eindeutig weniger Daten, die transferiert werden 
müssen)

Allerdings handelt es sich, da von Hand gezeichnete Kreise verwendet 
werden  leider nicht um einen idealen Kreis :-(

Ich hatte eine Idee dafür, allerdings passt es bei schlampig 
gezeichneten Kreisen nicht immer so, wie ich es mir ideal vorstellen 
würde....

Könnt ihr mir helfen, wie man es lösen kann?

Meine Idee:
1. Schwerpunkt aller Punkte berechnen

        x_ = 1/n sum_i=1..n(x_i)
        y_ =1/n sum_i=1..n(y_i)

M = (x_, y_) ist jetzt mein Kreismittelpunkt

2. Punkte im Koordinatensystem verschieben, dass Ursprung in der Mitte 
liegt

        für alle i:
           x_i_neu = x_i - x_
           y_i_neu = y_i - y_


3. Durchschnitt aller Radien berechnen
Allgemein gilt für den Radius eines Kreises: r = sqrt(x^2 + y^2)
Ich möchte nun den durschnittlichen Radius berechnen:

          für alle i:
               r_i = sqrt( x_i_neu * x_i_neu + y_i_neu * y_i_neu )

         r = 1/n sum_i= 1..n( r_i)


Die Daten, die ich dann übermitteln würde wäre:
Mittelpunkt M = (x_,y_)
Radius r


Vielen Dank für Eure Hilfe, falls ihr es genauer lösen könnt!!!!

Gruß Diddi

von Detlef _. (detlef_a)


Lesenswert?

Hm. Würde ich so probieren: Punktpaare heranziehen, Verbindungsgerade 
berechnen, darauf die Mittelsenkrechte. Der Mittelpunkt eines Kreises, 
der beide Punkte enthält, liegt auf dieser Geraden. Das für alle oder 
viele Punktpaare tun. Mittelpunkt des Kreises ist der Punkt, wo sich die 
meisten Mittelsenkrechten schneiden. Mit dem Mittelpunkt und den 
Kreispunkten den Radius berechnen. Sollte robust gehen.

Cheers
Detlef

von Dieter B. (Gast)


Lesenswert?

Danke, das werde ich mal implementieren...

Das Resulatat werde ich mit meinem vergleichen. Bei Interesse kann ich 
ja beide Resultate posten.

Gruß Diddi

von Jens P. (jmoney)


Lesenswert?

Ich glaube, Detlefs Vorschlag läuft auch wieder nur auf eine Mittelung 
der Schnittpunkte hinaus. Da kann man auch gleich den Schwerpunktder 
Punkte berechnen und muss nicht vorher zig Geraden aufstellen und 
schneiden.
Vielleicht hilft ja eine andere Gewichtung bei der Mittelwertbildung. 
Hast du mal ein geometrisches oder quadratisches Mittel statt dem 
arithmetischen probiert? Das ergibt dann halt einen etwas kleineren bzw. 
größeren Kreis.
Was genau passt dir denn nicht an den gemittelten Kreisen?
Gib mal ein Beispiel, wo dir das Ergebnis nicht gefällt.

von Spiralenzeichner (Gast)


Lesenswert?

>Mittelpunkt des Kreises ist der Punkt, wo sich die
>meisten Mittelsenkrechten schneiden.

es wird viele Punkte geben, in denen sich genau zwei Mittelsenkrechten 
schneiden und mit an Sicherheit grenzender Wahrscheinlichkeit keinen, in 
dem sich drei Mittelsenkrechten schneiden.

Dieter B., dein Weg ist schon der beste, wenn du sicherstellst, dass du 
nur Punkte aus einem Umlauf um den ermittelten Mittelpunkt 
berücksichtigst. Also im zweiten Durchlauf alle Punkte auf den 
berechneten Kreis projizieren, auf eine konstante Punktedichte pro 
Kreissegment interpolieren, und dann den Mittelpunkt und Radius nach 
deiner Methode neu berechnen. Evtl. 1-2 mal iterieren.

von Dieter B. (Gast)


Lesenswert?

Mein Problem hier z.B: Wenn der Kreis nicht komplett gezeichnet wurde, 
dann wird eben der Schwerpunkt bestimmt und der Radius gemittelt.
Im Beispiel ( kommt mit ascciee nicht so gut raus)

die Sterne sind meine Eingabe, ich hätte gerne den Kreis so geschätzt, 
wie die Minusse es angeben , allerdings sieht es ( auf Grund von 
Mittelpunkt = Schwerpunkt der Punktwolke leider eher so aus, wie bei 
real angegben, wobei die - Striche natürlich schon einen exakten Kreis 
darstellen.

Ich hoffe, das Problem ist klar geworden:
Mein Verfahren detektiert eben den Schwerpunkt und den mittleren Radius,
ich wünsche mir ein Verfahren, welches aus einer bestimmten Punktmenge 
den Radius erkennt und den Mittelpunkt bestimmt....

Klar, irgendwie ist es immer Ansichtssache...

Ideal:

  -  *-
 -     *
 -  x   *-
 -     *
  * - *-
x= Mittelpunkt


real:


   *
  -  * -
 -  x * -
  -   *_
  *  *-

von Spiralenzeichner (Gast)


Lesenswert?

>Ich hoffe, das Problem ist klar geworden:

Ich hoffe du liest noch die Beiträge, die nicht von dir selbst stammen.

von Dieter B. (Gast)


Lesenswert?

Kommt mir  gerade noch eine idee, wo ich meine Kreise so anschaue:
Perfekt wäre es doch, wenn man einen Kreis wandern lassen würde...

1. Punkte wieder auf den Ursprung verschieben...

2. Für alle Punkte das Rechteck bestimmen, in dem alle Punkte drin sind

(also
x_max, x_min
y_max, y_min
bestimmen )

dann

3. Kreis mit allen möglichen Radien an allen möglichen x, y Orten 
erstellen und für alle Punkte den minimalen Abstand zu diesem Kreis 
bestimmen... Der jenige Kreis, bei dem die Gesamtheit aller Punkte den 
minimalen Abstand hat, ist es

for (x =  x_min... x_max){  <- (könnte man noch verkleinern)
 for(y  =y_min...y_max){    <- (könnte man noch verkleinern)
    for( r = 0... max( (x_max-xmin)/2, (y_max-ymin)/2)){
      sum = 0
       for (i = 1 ...n) (alle Punkte){
            minimaler Abstand dpk zum Kreis bestimmen
              sum += dpk;


nun merkt man sich das jenige (x, y, r) bei dem sum minimal ist...

Laufzeit : O (X*Y *max(X,Y) *N) ?????? oder so ähnlich -> vergiss es

von Matthias (Gast)


Lesenswert?

Wo kommen denn deine Punkte, die du selbst eingibst, her?
Also wieviele Punkte sinds denn immer, die zur Abschätzung da sind?

Weil, wenns drei Punkte sind, kann man ganz exakt den Radius und den 
Mittelpunkt errechnen...

Vielleicht alle gegebenen Punkte in Gruppen zu je drei Punkten ordnen
zB, bei 4Punkten:
P1,P2,P3
P2,P3,P4
P1,P3,P4
und die drei ermittelten Radien/Mittelpunkte nach irgendeinem 
"Mittelwertverfahren" auf einen gemeinsamen Wert/Punkt zusammenführen..

von Spiralenzeichner (Gast)


Lesenswert?

Lies mal hier http://de.wikipedia.org/wiki/Hough-Transformation
den Absatz "Hough-Transformation für Kreise und generalisierte 
Hough-Transformation" durch und verstehe ihn. Das geht in die Richtung 
von deinem 16:59h-Posting.
Und dann lies noch, fast dort zur Fast Hough Transformation steht.

von Dieter B. (Gast)


Lesenswert?

Hallo Spiralenzeichner, ja, ich lese natürlich deine Beiträge.

Das Posting um 16:44 war die Antwort auf  Jens Peter.

Während ich das Bild gezeichnet habe, ist mir mein 16:59 Posting 
eingefallen.
Dann habe ich lange geschrieben und dann musste ich mal wieder 
weiterarbeiten, Antwort auf deine Postings kommen bestimmt!

Auch deinen Wikipedia Abschnitt werde ich mir natürlich anschauen!

von Dieter (Gast)


Lesenswert?

>Das Posting um 16:44 war die Antwort auf  Jens Peter.

Du solltest auch noch Matthias antworten. Der hat auch nichts neues 
beigetragen.

von Detlef _. (detlef_a)


Lesenswert?

Hallo,

Kreisfinden geht sehr gut mit der Hough-Transformation. Wenn man den 
Radius nicht kennt, muß man allerdings mehrere Radien auprobieren, das 
kann dauern.

Idee beim Kreisfinden mit Hough geht so: Du hast einige Randpunkte des 
Kreises, dessen Mittelpunkt Du suchst. Dann malst Du um jeden dieser 
Randpunkte genau den Kreis mit dem bekannten Radius. Die schneiden sich 
alle in dem Mittelpunkt, den Du suchst.

In diesem thread hatte ich das mal anhand eines Bildes vorgeführt, in 
dem ein sehr 'ausgefranster' Kreis zu finden war:
Beitrag "Re: Bilderkennung mit DSP"

Hough findet Kreise, die man als menschlicher Beobachter kaum als Kreise 
in sehr gestörten Bildern erkennen könnte.

Bei geeigneter Parametrisierung kannst Du auch Deine Ellipsen mit der 
Hough Transformation suchen lassen.

Kurz: Hough is supergut.

Dieter, poste mal nen Bild von Deinen Kreisen, dann mal ich Dir ne Hough 
Transformation rein.

Cheers
Detlef

von Dieter (Gast)


Lesenswert?

Die Houghtrafo kann ich schon rechnen. Die Frage ist, wie das ein uC bei 
Videofrequenzen in Echtzeit machen soll. Aber danke für die Wiederholung 
und die Zusammenfassung des Wikipediaartikels.

von Detlef _. (detlef_a)


Lesenswert?

>>Die Frage ist, wie das ein uC bei Videofrequenzen in Echtzeit machen soll.<<

Auf die Frage gibts ne einfache Antwort: 'Garnicht.'

Die Anwort auf die Frage 'Was kann ein uC bei Videofrequenzen in 
Echtzeit machen?' lautet übrigens 'Fast nichts.'

Von Video und Echtzeit war bisher nicht die Rede, da ist nen uC die 
falsche Spielklasse, besser mal nach ARM/DSP kucken.

Gute Nacht
Detlef

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.