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
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
Danke, das werde ich mal implementieren... Das Resulatat werde ich mit meinem vergleichen. Bei Interesse kann ich ja beide Resultate posten. Gruß Diddi
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.
>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.
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 * - - *_ * *-
>Ich hoffe, das Problem ist klar geworden:
Ich hoffe du liest noch die Beiträge, die nicht von dir selbst stammen.
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
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..
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.
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!
>Das Posting um 16:44 war die Antwort auf Jens Peter.
Du solltest auch noch Matthias antworten. Der hat auch nichts neues
beigetragen.
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
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.
>>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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.