Autor Beitrag
Flamefire
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Di 09.12.08 11:32 
Hallo,
ich habe folgendes Problem: Ich will aus einem gegebenen s-w-Bild (als BMP bzw. auf TImage gezeichnet) erkennen wo ein Kreis ist.
Ich male also auf die TImage ein Bild aus z.B. 2 Kreisen und einer Linie und das Programm soll mir am Ende sagen, wo die Mittelpunkte der Kreise sind.
Mein erster Ansatz: Alle weißen Pixel verfolgen und gucken, ob sie eine Linie bilden...so kann ich zumindest rauskriegen was linien sind

leider weiß ich nicht wie ich dann auf kreise schließen kann geschweige denn den mittelpunkt davon berechnen.
zusätzliches problem: überlappungen. Also kreise übereinander oder linie über kreis oder kreis nicht ganz vollständig

jemand da ne idee?
Gummibär
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18
Erhaltene Danke: 11


Delphi 7, Turbo Delphi
BeitragVerfasst: Di 09.12.08 12:58 
Eine beliebte Methode hierfür ist die Hough-Transformation.

de.wikipedia.org/wiki/Hough-Transformation

Oder sind es immer nur zwei Kreise und eine Gerade? Dann läßt sich bestimmt was leichteres finden....

Gruß
Michael
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Di 09.12.08 13:15 
nein die anzahl ist variabel...aber ebn nur linien und kreise
Gummibär
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18
Erhaltene Danke: 11


Delphi 7, Turbo Delphi
BeitragVerfasst: Di 09.12.08 16:23 
Weil's so Spaß macht....

Hab mal eben den ersten Schritt der Hough-Transformation in ein kleines Programm gehackt. Es erzeugt auf Knopfdruck ein Zufallsbild mit Kreisen (und - wenn gewünscht - mit zusätzlichen Strichen). Dann erzeugt es das Bild mit den Schnittpunkthäufigkeiten.
Um an die Kreismittelpunkte zu kommen, müsste man dann dieses Bild analysieren und bestimmen, wo die Maxima (die hellsten Punkte) liegen (Auch nicht ganz trivial. Am besten erst mal glätten, Histogramm berechnen, und dann "sinnvoll" die Spreu vom Weizen trennen).
Allerdings weiß man dann immer noch nichts über die Radien der Kreise.

Ist also nur ein Anfang...

Gruß
Michael
Einloggen, um Attachments anzusehen!
elundril
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 3747
Erhaltene Danke: 123

Windows Vista, Ubuntu
Delphi 7 PE "Codename: Aurora", Eclipse Ganymede
BeitragVerfasst: Di 09.12.08 16:27 
kann es sein das du ein CAPTCHA umgehen willst?

_________________
This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Di 09.12.08 21:22 
nein es geht nicht darum captchas zu umgehen
ist eine (mehr oder weniger selbstauferlegte) aufgabe für die uni...

@gummibär: könntest du den teil, mit den 3 punkten aus deinem programm näher erklären?
vl mit skizze?
ansonsten scheint das schon das zu sein.

hatte vorhin mal was probiert: um jeden weißen pixel einen kreis mit radius r zeichnen. oder besser: in einem entsprechendem array den jeweiligen wert um eins erhöhen
wo der wert am höchsten ist, habe ich einen potenziellen mittelpunkt.
also nur noch prüfen ob darum ein kreis mit radius r weiß ist.

so ein zwischenbild (das array grafisch) sieht so aus wie im anhang.

das ganze mache ich dann ebn für alle möglichen radien... (also z.b. 9-15 oder so)

was ist da besser?

wenn ich das richtig gesehn hab, bekomme ich mit deiner variante sehr gut die mittelpunkte raus. (da könnte meine fkt noch fehler haben...noch nicht ausreichend getestet)
ich bräuchte dann blos noch die radien...
außerdem müsste ich deine zufällige punktauswahl durch eine permutation ersetzen die alle punkte vergleicht.
dürfte aber kein höherer aufwand sein als bei meiner, oder?
Einloggen, um Attachments anzusehen!
Gummibär
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18
Erhaltene Danke: 11


Delphi 7, Turbo Delphi
BeitragVerfasst: Mi 10.12.08 08:16 
Du meinst die Stelle "CheckRandomTriple"?

Die Idee ist hier, sich einfach drei beliebige schwarze Punkte aus dem Bild zu nehmen, dann frech zu behaupten, die lägen auf einem Kreis, und dann den zugehörigen Kreismittelpunkt zu bestimmen.

(Zu der Beschreibung hier siehe auch Skizze im Anhang)
Die Zufälligen Punkte-Indizes sind im Code t1, t2 und t3. Natürlich müssen die drei verschieden sein.
Die Koordinaten der Punkte stehen in Points[t1], Points[t2] und Points[t3].
Die Routine prüft noch, ob diese Punkte nicht auch noch auf einer Linie liegen.

Nun gilt es, unter der Annahme, die Punkte lägen auf einem Kreis, dessen Mittelpunkt zu bestimmen:
Dazu verbindet man Points[t1] und Points[t2], sowie Points[t2] und Points[t3] mit je einer (gedachten) Linie (nennen wir sie mal s0 und s1). Auf diesen beiden Linien bildet man die Mittelsenkrechten. Dabei geben die Koordinaten (X0,Y0) und (X1,Y1) die Mitten der Strecken s0 und s1 an. Die jeweiligen Steigungen der Mittelsenkrechten in X und Y Richtung (dX0, dY0 und dX1 und dY1) lassen sich leicht aus den Koordinaten der drei Punkte berechnen.

Die Mittelsenkrechte auf s0 ist somit wie folgt definiert: X=X0+f*dX0, Y=Y0+f*dY0 mit f aus den reellen Zahlen. Für die Mittelsenkrechte auf s1 gibt es analoge Formeln.

Jetzt muß man nur noch den Schnittpunkt der beiden Mittelsenkrechten suchen (Gleichsetzen der oben erwähnten Geradengleichungen) und hat damit den Mittelpunkt des gedachten Kreises, auf denen Points[t1], Points[t2] und Points[t3] liegen.

An der Stelle, an der der Mittelpunkt vermutet wird, inkrementieren wir dann im FreqGrid die entsprechende Speicherstelle um 1: Inc(FreqGrid[LX, LY]).

Nun muß man die Routine gaaaanz oft aufrufen (im Beispielcode war das 20000 mal). An echten Kreismittelpunkten wird sich dann der Wert viel stärker erhöhen als in anderen Bereichen. Im übrigen Bild bleibt ein Restrauschen übrig. Die Kunst ist jetzt, die echten Peaks von den Falschmeldungen zu unterscheiden.


Nachtrag: Zur Radien-Geschichte:
So ganz habe ich Deinen Ansatz nicht verstanden.
Ich würde so vorgehen: Zusätzlich zum FreqGrid Array würde ich mir noch ein RadGrid-Array selber Größe anlegen. Wann immer ich nun in FreqGrid einen Punkt erhöhe (An der Stelle [LX,LY], siehe oben), würde ich im RadGrid dieselbe Stelle um den zugehörigen Radius erhöhen (Beispielsweise RadGrid[LX,LY] := RadGrid[LX,LY] + (Distanz (LX,LY) zu Punkt t1) ). RadGrid wäre allerdings ein Float-Array, denn da kommen auch krumme Zahlen vor.
Hat man nun am Ende beispielsweise an der Stelle (a, b) einen maximalen weißen Punkt identifiziert, erhält man den zugehörigen Radius mittels Radius := RadGrid[a,b] / FreqGrid[a,b];

Was die Verwendung einer Permutation statt des Zufalls angeht hast Du prinzipiell recht. Allerdings wird der Rechenaufwand enorm, da unter Umständen viel mehr als "nur" 20000 Vergleiche gemacht werden müßten.

Gruß
Michael
Einloggen, um Attachments anzusehen!
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Mi 10.12.08 10:06 
zu meinem ansatz:

du hast einen kreis um den punkt (mx,my) mit radius r
wenn man jetzt um jeden punkt des kreises einen weiteren kreis mit radius r zeichnet, hat man einen häufungspunkt am punkt (mx,my), da der abstand (radius) von jedem punkt auf dem (haupt-)kreis zum mittelpunkt (mx,my) gleich ist (kann man im bild erkennen, wie das dann aussieht)

jetzt muss ich nur noch verschiedene radien durchprobieren und hab am ende meine kreise mit den radien

zum rechenaufwand bei der permutatation: n punkte; jeweils 3-er kombinationen; =3*2^n aufrufe

bei mir wird jeder punkt einmal betrachtet um den kreis zu zeichen=n aufrufe
zusätzlich dann noch jeder bildpunkt geprüft-->insgesammt m+n
also linear...

ich guck mal, ob ich mit meiner methode weiter komme...scheint sich zu lohnen.
Gummibär
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18
Erhaltene Danke: 11


Delphi 7, Turbo Delphi
BeitragVerfasst: Mi 10.12.08 10:35 
Ah, nun ist der Groschen gefallen. Interessanter Ansatz.

Ich habe in der Zwischenzeit die oben beschriebene Methode mal implementiert. Allerdings ohne Anpassung des Graustufenbildes auf relative Häufigkeiten: Der Schwellwert, ab wann ein Kreismittelpunkt angenommen wird, ist momentan fix.
Liefert dennoch schon brauchbare Resultate.

Gruß
Michael
Einloggen, um Attachments anzusehen!
Flamefire Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Mi 10.12.08 12:13 
gut dann gibt es jz 2 gute lösungen
werde meine demnächst auch mit reinstellen, falls es noch jemand braucht...dauert aber da ich z.zt. nur gprs-verbindung hab >.<
meine variante klappt aber so gut, dass ich sie für mich vorerst beibehalte (zwecks rechenzeit...)
wenn es damit probleme gibt, werde ich dann doch deine nehmen.
mal gucken was die zukunft und die tests bringen