Suche nach Kurven in Datenmenge

[-gb- (Gast)]

Aus einer Bildverarbeitung kommen 2D-XY-Daten in einen Bildspeicher, der 
von einem Videoprozessor ausgelesen wird. Im Bild (hell-dunkel), das 
stark verrauscht ist, sollen Kreise identifiziert werden. Der 
Mittelpunkt kann dabei ausserhalb des Bildes liegen.

Es gibt einen dark spot und einen light spot, deren Grösse und Lage 
bestimmt werden sollen. Infolge diverser Effekte sind die Kreise leicht 
deformiert. (Real sind es Kugelprojekttionen, die schwimmen und 
verwackeln).

Angedeutet ist der Bilduschnitt im Videospeicher.

Das Bild kann mehrfach ausgelesen, zwischengespeichert und analysiert 
werden.

Was ich schon hinbekommen habe, ist das Bild so zubearbeiten, dass ich 
das Rauschen weg habe und Kreise ausweisen kann. Wie gelange ich nun zu 
den Parametern R und Xm,Ym?

[John (Gast)]

Räumlicher Hochpass (Sobel) -> Hough-Transformation?

[-gb- (Gast)]

Die Hough-Trans habe ich schon probiert. Das ist aufwändig und nicht so 
ergenisbringend. Weitere Ideen?

[Otto (Gast)]

1) Filtern
2) Kantendetektion
3) Morphologische Filter (optional)
4) Klassifizierungs-Algo (bspw. k-Means)

Georg B. schrieb:
> Die Hough-Trans habe ich schon probiert. Das ist aufwändig und nicht so
> ergenisbringend.

Wir bewegen uns hier im Bereich des Maschinellen Sehens -- hier ist 
nichts einfach und mal eben schnell ohne großen Aufwand gemacht.

[zwonk (Gast)]

Langsam verstehe ich, wieso hier der Ton häufig rauer als erwartet ist.

Wenn du ein Problem schilderst mit der Frage "Wie gelange ich nun zu
den Parametern R und Xm,Ym?" ohne deine bereits versuchten Verfahren zu 
schildern, bekommst du garantiert die am meisten Erfolg versprechenden 
Methoden, i.e. Kantenfilter + Hough.

Besser, du legst die Karten auf den Tisch und erzählst uns ein 
bisschen mehr.

1) Sieht aus wie Fluoreszenzmikroskopie. Stimmt das? Wenn nicht, was ist 
es?
2) Du sagst, die Objekte sind nicht statisch. Also her mit den Daten! 
Mindestens eine Bildfolge von mehreren zeitlich kohärenten Aufnahmen 
einer typischen Situation.
3) Was hast du bereits versucht, mit welchen Parametern?
4) Bist du bereit, Code zu veröffentlichen oder willst du nur eine 
Diskussion, bei der wir dir alles aus der Nase ziehen müssen?
5) Du sagst, du hast das Rauschen beseitigt. Warum zeigst du uns dann 
ein verrauschtes Bild?
6) Du kannst Kreise ausweisen. Bitte erläutern. Meinst du, du guckst das 
Bild an und sagst "KREIS!" oder hast du was handfestes?

Okay, hab mich beruhigt. Was brauchst du? Radius und Kreismittelpunkt. 
Wie bekommst du das? Indem du einen Kreis an die Objekte fittest. Durch 
was ist ein Kreis definiert? Durch die Punkte, die die Kreisformel 
erfüllen. Diese Punkte liegen auf der Kontur der Objekte deines Bildes. 
Du musst also die Konturpunkte finden.

Ansatz 1: Segmentierung der gesamten Objekte und Kontursuche.
A) Dynamische Schwellwerte
B) Texturanalyse (Stichwort Morphologie, FFT, Kookkurenzmatrix, Laws 
Texture Energy Measures)
C) Maschinelles Lernen: SVM, Neuronale Netze

Ansatz 2: Direkte Klassifizierung der Konturpunkte.
A) Kantendetektion (Hochpass, Canny, Morphologische Filter)
B) Maschinelles Lernen
C) Feature-Extraktion mit nachfolgender Filterung nach Kriterien

Ansatz 3: Statistische Kurvenbestimmung
Hough ist nicht nur für Kreise da! Lies dich ein.

Ansatz 4: Zeitliche Kohärenz ausnutzen
WENN du zeitlich kohärente Bilder hast, dann nutz das aus! Bilde den 
optical flow zwischen aufeinanderfolgenden Bildern. Entsprechende 
Vektoren in aufeinanderfolgenden Bildern deuten auf Objekte hin, 
zufällige Vektoren auf Hintergrund, FALLS dein Hintergrund einem 
statistischem Prozess folgt.
Stichworte: Features, Dense Optical Flow

So, jetzt bist du dran!

[-gb- (Gast)]

zwonk schrieb:
> 1) Sieht aus wie Fluoreszenzmikroskopie. Stimmt das? Wenn nicht, was ist
> es?
Es ist ein Forschungsprojekt aus dem Bereich der elektromagnetischen 
3D-Lokalisation von metallischen Objekten. Sie entstehen nach einer 
Flächenabtastung eines elektrosensitiven Sensors.

> 2) Du sagst, die Objekte sind nicht statisch. Also her mit den Daten!
Habe ich noch keine.

> 3) Was hast du bereits versucht, mit welchen Parametern?
Ich habe die Bilder ofline mit MATLAB prozessiert und mir überlegt, wie 
es möglich sein könnte, das Rauschen wegzubekommen. Angelangt bin ich 
bei einem glatten Bild

> 4) Bist du bereit, Code zu veröffentlichen
Habe noch keinen. Es geht jetzt darum, festzustellen, was man braucht 
und welche Plattform sowas leisten kann.

> 5) Du sagst, du hast das Rauschen beseitigt. Warum zeigst du uns dann
> ein verrauschtes Bild?

Siehe oben das entrauschte Bild


> 6) Du kannst Kreise ausweisen. Bitte erläutern. Meinst du, du guckst das
> Bild an und sagst "KREIS!" oder hast du was handfestes?

Es müssen Kreise sein, weil die Emmission kubisch ist und die Projektion 
auf einer Fläche immer ein Kreis ist.

> Okay, hab mich beruhigt.
Was hat Dich denn so erregt?

[Stefan (Gast)]

Es gibt doch in OpenCV eine eingebaute Kreiserkennung? Meine ich neulich 
in einem Tutorialgelesen zu haben...

[zwonk (Gast)]

Okay, kapiert. Ich halte mich raus. Aus deinen Antworten sehe ich genau 
das, was ich schon hundertmal in real life und hier im Board gesehen 
habe. Wenig Input, schwammige Formulierung, ausweichende Antworten, aber 
Erwartungshaltung.

Viel Spaß mit dem Projekt!

[-gb- (Gast)]

Stefan schrieb:
> Es gibt doch in OpenCV eine eingebaute Kreiserkennung? Meine ich neulich
> in einem Tutorialgelesen zu haben...

Das ist ein guter Hinweis. Vielen Dank. Das werde ich mir raussuchen.

Danke denen, die konstruktives beigetragen haben.

Den anderen wünsche ich noch ein schönes Wochenende.

[knowz (Gast)]

> Besser, du legst die Karten auf den Tisch und erzählst uns ein
> bisschen mehr.

Die Frage war klar und verständlich formuliert. Es ging um 
Bildverarbeitung.

Die Schuhgröße des Großvaters väterlicherseits, ob das Bild durch 
Kirlianfotografie oder ektoplasmische Niederschläge entstanden ist und 
ob der Code letztlich Open Source wird, tut da nichts zur Sache.

Ich verstehe auch, warum der Ton oft so indiskutabel wird: Das passiert 
dann, wenn Leute, die offenbar keine Antwort beisteuern können, ihre 
niedrigen Instinkte durch Herumnörgeln an der Fragestelltung ausleben.

[Klaus (Gast)]

Das kann man klar und eindeutig beantworten.

Entweder man ist ein Enthusiast der ein Thema oder Problem diskutieren 
will.

Dann erklärt man das Problem und seine Umgebung klar und offen.
1. Wer das verneint, hat noch nie komplexe Probleme bearbeitet, bei 
denen oft gar nicht klar ist ob gewisse Tatsachen nun zur befriedigenden 
Lösung beitragen oder nicht.
2. Wer das verneint, will auch nicht, dass die Gemeinschaft von der 
Diskussion profitiert und das kann sie überhaupt erst und um so besser, 
wenn viel von dem Gesamtzusammenhang offengelegt wird.

Oder man ist, wie sich aus dem oben Gesagten ergibt, ein "Kunde", der 
die Information, die er preisgibt minimieren und die, die er erhält 
maximieren will.
Dann soll er hier Projektanfragen stellen oder Stellenanzeigen aufgeben.

[-gb- (Gast)]

Ich sehe schon, Wochenende ist kein guter Tag zum Fragen.

[Dogbert (Gast)]

Wie klein wird der kleinste Kreis?

Das Bild kann man doch ohne weiteres auf 10% also 1% der Pixel 
runtersamplen ohne relevante Information zu verlieren.

Vielleicht kann man dann noch die ganzen Kreise erfassen ohne sie 
abzuschneiden und ohne diesen hässlichen Rand?

Dann wäre es einfach eine Diskriminierung nach Amplitude über 
Schwellenwerte und danach ein center of gravity für den Mittelpunkt und 
eine Flächenberechnung für den Radius.

[Disco (Gast)]

Diese Kreiserkennung interessiert mich dienstlich auch, aber ich werde 
hier nicht nach Lösungen fragen.  Der Zahn wurde mir wieder mal 
gezogenen.

Wenn ich mir dieses Segment ansehe, wird mir immer wieder klar, das der 
Mensch den Kreis gut erkennen kann, die fehlenden Ränder simple 
mathematische Verfahren jedoch ausschließen.

Andererseits braucht man nur 3 Punkte auf der Peripherie um einen 
Idealen Kreis erkennen.  Leider ist kein Kreis ideal.

[-gb- (Gast)]

Was wäre der Vorteil des runterskalierens? Ich verliere Information. Wo 
ist der Wert?

Der Bildschauschnitt ist nicht willkürlich. Der Aufnahmebereich ist 
begrenzt, wie bei einer Fotokamera. Ich kann diesen maximieren und dabei 
Bildrate verlieren, aber nicht über alle Grenzen gehen. Es wird immer so 
sein, dass Projektionen unvollständig bleiben. Ich möchte dann natürlich 
den Ausschnittsbreich anpassen, sobald ich die Kreisgrössen habe.

Es reicht aber, die Kreise zu fitten und die XY-Koordinaten zu haben. 
Die XZ und YZ-Raumpositionen bestimmen orthogonale Messsysteme.

Damit kann dann letztlich der 3D-Mittelpunkt ermittelt werden. 
Hoffentlich :-)

[Dogbert (Gast)]

Da fällt mir gerade ein was der schlüssel zur lösung ist:

Transformation nach log-polar:

googeln z.B. nach log polar circle

[Sigi (Gast)]

Wenn du das Bild auf 10% verkleinerst, dann erkennt man noch
immer sehr genau die Kreise, auch innerhalb des Quadrats.
D.h., für eine Erkennung dürfte es noch ausreichend sein.

Und Hough-Transformation ist nicht gleich Hough-Transformation.
Du kannst die Transformation so formulieren, dass du einen
Punkt nicht auf Rand-, sondern auf Flächen-Zugehörigkeit testest.
Dabei kannst du das Transformationsraster nochmal gröber machen.
Dazu noch eine Transformation für verschiedene Kreisdurchmesser
oder gleich eine mehrdim. Hough-Transformation.

Dann die Transformierte ausreichend glätten und nach Max/Min
suchen...

Selbst wenn du nur einen Teilkreis, Rest abgeschnitten, hast,
liefert dir die Transformation noch immer Treffer. Ich habe
selbst schon bei verschiedenen Formen gemacht, meist immer
erfolgreich.

Der Algorithmus lässt sich übrigends gut auf einer GPU ausführen.

[Dogbert (Gast)]

Georg B. schrieb:
> Was wäre der Vorteil des runterskalierens? Ich verliere
> Information. Wo
> ist der Wert?

So wie das Bild aussieht denke ich nicht dass Information verloren geht 
bei runtersamplen auf 10%.

Denn schaut man sich das Bild im Frequenzbereich an, wird man 
feststellen dass ab 1/10 Nyquistfrequenz wohl das Rauschen bei weitem 
das Nutzsignal aus den Kreisen übersteigt.

Man erhöht also lediglich das Messrauschen für einen Algorithmus der 
nicht das ganze Bild auswertet sondern nach "Features" sucht, also nur 
wenige Pixel verrechnet von einem Kreis der aus Tausenden besteht.

Ich habe die fft transformation des Beispielbildes angehängt.

Sie umfasst 10^4 von schwarz zu weiss und ist fnull auf mitte zentriert.

Die Information der Kreise ist sehr nahe am hellen Mittelpunkt, da sehr 
niederfrequent. Die höherfrequenten Teile der Kreise sind zu schwach um 
über das Rauschen zu kommen.

Die Linien sind der sinc des Rechtecks im Bild.

[Dogbert (Gast)]

Das richtige Bild.

[Dogbert (Gast)]

Mist, das wirklich richtige.

[-gb- (Gast)]

Das muss ich mir erst näher ansehen. Kann es sein, dass das alles 
dieselben Bilder sind? Ich sehe den Unterschied nicht.

[Dogbert (Gast)]

Feine Unterschiede im letzten. Da sieht man den "sinc" des rechtecks als 
das in der helligkeit modulierte kreuz.

[Sigi (Gast)]

Ich habe mal von von der 10%-Skalierung eine
Hough-Transformation gemacht: Wie man im Bild
sieht, kann man den gefüllten Kreis gut erkennen
bzw. die Koordinaten bestimmen.

Dass der (weisse) Kreis an den Rändern abgeschnitten
ist ändert nichts an der guten Erkennbarkeit.

[-gb- (Gast)]

Auf welchen Ausschnitt bezieht sich das? Müssten da nun nicht zwei Peaks 
sein, da ja auch zwei Kreisausschnitte im Bild sind?

[Detlef _. (detlef_a)]

Ich habe mal von dem 'preprocessed' Bild ne Hough Transformation 
gemacht, da findet man die Kreise wunderbar und ohne jede Schwierigkeit.

Und es entstehen wieder diese schönen, zarten, feengleichen Bilder der 
Houghräume ;-) .

Hough ist für die Aufgabe geschaffen, es gibt auch Houghvarianten für 
Ellipsen.

Matlab Code anbei, der läuft bei mir paar Sekunden, eine Schleife kann 
man auch noch rausschmeissen, ist mir aber wg. Müdigkeit nicht mehr 
gelungen.

War großer Spaß.
Gute Nacht
Cheers
Detlef

clear

M=imread('c:\\matlab\\myfiles\\powersolutioncloudpostprocessed.jpg ','jpg');  
M=double(M);
kkr=350/2; % kleiner Kreis Radius
gkr=750/2; % grosser Kreis Radius, beide geschaetzt
M=M/max(max(M));
M1=M>0.9;
ind=find(M1==1);
n=size(M1);
nzei=n(1);nsp=n(2);
M2=zeros(size(M1));
%for(k=1:length(ind))
% M2(rem((ind(k)-1),nzei)+1,fix((ind(k)-1)/nzei)+1)=1;   
%end;
ind=[(rem((ind-1),nzei)+1) fix((ind-1)/nzei)+1];
%for(k=1:length(ind))
% M2(ind(k,1),ind(k,2))=1;   
%end;
M2((ind(:,2)-1)*nzei+ind(:,1))=1;
M3=zeros(size(repmat(M,3,3)));

zoff=nzei;
soff=nsp;
kk=kkr*exp(j*linspace(0,2*pi,fix(kkr*2*pi*1.1)));
gk=gkr*exp(j*linspace(0,2*pi,fix(gkr*2*pi*1.1)));
kk=kk(:);
gk=gk(:);
for(k=1:length(kk))
  length(kk)-k  
  ko=ind+repmat([real(kk(k)) imag(kk(k))],length(ind),1);
  ko=ko+repmat([zoff soff],length(ind),1);
  for(nn=1:length(ko))
  M3(fix(ko(nn,1)),fix(ko(nn,2)))=M3(fix(ko(nn,1)),fix(ko(nn,2)))+1;
  end;
end;
for(k=1:length(gk))
  length(gk)-k  
  ko=ind+repmat([real(gk(k)) imag(gk(k))],length(ind),1);
  ko=ko+repmat([zoff soff],length(ind),1);
  for(nn=1:length(ko))
  M3(fix(ko(nn,1)),fix(ko(nn,2)))=M3(fix(ko(nn,1)),fix(ko(nn,2)))+1;
  end;
end;
return

[-gb- (Gast)]

Das sieht gut aus, allerdings kam ich bei mir nicht dahin. Gfs mache ich 
auch was Falsch. Aber: Mir stellt sich die Frage, wie Du die Kreisgröße 
bestimmst. Schätzen ist ganz gut, das kann ich aber bei mir nicht 
machen. Denkbar wären verschiedene Annahmen. Muss jetzt erstmal Deinen 
Code inspizieren.

[J. S. (engineer)]

Nach der Hough-T braucht es aber auch nochmals einen Schritt, um die 
Schwerpunkte zu finden und die korrekten Radien zu bestimmen. Wenn die 
Bilder erst einmal so vorprozessiert sind, kann man die Punkte auch mit 
einer allgemeinen Ellipse fitten. Lage, Orientierung und Durchmesser 
kommen dann automatisch bei raus. Es müssen eben zuvor nur 
zusammenhängende Punkte selektiert und Gewichtungen für die lineare 
Optimierung bestimmt werden.

Wenn man die Lage und die Form einmal ungefähr hat, kann man das von 
Bild zu Bild machen unter Ausnutzung der Parameter und Fenster aus dem 
Vorbild. Die neue (leicht veränderte) Lage und die Position bekommt man 
dann am Ende des Frames. Geht in einem FPGA komplett in Echtzeit in 
einem einzigen Durchlauf. Mit etwas Intelligenz lassen sich beliebig 
viele matcher aufsetzen, die mehrere Objekte on the fly finden und 
verfolgen. Das Problem ist dann nur, die matcher profiles randseitig 
passend virtuell zu maskieren, damit sie auch für Objekte mit 
teilerhobenen Abbildungen passen.

Detlef _a schrieb:
> Und es entstehen wieder diese schönen, zarten, feengleichen Bilder der
> Houghräume ;-) .
Ich sag's doch immer: So schön kann Mathe sein.

[pathc (Gast)]

Und noch mein Senf:

1. Glätten
2. Sobel-Filter
3. Fast Radial Symmetrie Transformation (wurde hier noch nicht genannt)
4. Morphologische Operationen
5. Schwerpunkte von den Elementen im Ergebnisbild bestimmen.

[Detlef _. (detlef_a)]

>> Aber: Mir stellt sich die Frage, wie Du die Kreisgröße bestimmst.

Guter Punkt. Ich hatte sie per Hand aus den Bildern geschätzt, bei dem 
großen Kreis hatte ich mich auch verschätzt wie man an dem Houghraum 
sieht. Je 'schärfer' die peaks werden umso besser triffst Du den Radius. 
Ich hatte mal sowas für einen Pupillentracker programmiert, da habe ich 
einen kleineren und einen größeren Kreisradius mitberechnet und gekuckt, 
wer besser paßt und ggf. nachgezogen, ging ganz gut. Gibts tonnenweise 
Veröffentlichungen zu.

Cheers
Detlef

[Sigi (Gast)]

Georg B. schrieb:
> Mir stellt sich die Frage, wie Du die Kreisgröße
> bestimmst.

Ganz einfach: Die HT dient ja zur Abschätzung von
Parameter, d.h. je Parameter hast du eine HT-Dimension.
Bei dir sind es also X,Y und Radius, d.h. 3 Dimensionen.
Als Resultat bekommst du damit ein Volumen (und nicht
wie hier in den Bildern eine 2D-HT).
Für den Anfang ist es aber besser, zu einem geg.
Bild den Radius zu schätzen und sich die 2D-HT zu
betrachten.

Unterschied mein Bild/Detlef's Bild: Bei meinem Bild
habe ich keine Kreislinien-Transformation gemacht,
Detlef's HT dagegen ist die HT der Kreislinien,
gut zu erkennen an den feinen Liniengespinnsten
(das hängt aber auch vom Algorithmus ab, ist wie
bei GPU-Texture-Mapping, wo ich von Def-Raum in
Bild-Raum oder aber auch treibend vom Bild-Raum
aus dem Def-Raum Farb-Infos berechne/ziehe. Der
2. Ansatz auf die HT angewendet eliminiert diese
Gespinnste und du bekommst eine glatte Fläche).

Parameter schätzen: Ist auch wieder eine schwierige
Aufgabe, aber wenn das (oft sehr glatte!) HT-Bild
patchweise polynom. approximiert wird, dann lässt
sich leicht an den Maxima der Parameter abschätzen,
oder aber auch an der Qualität der Maxima (Stichwort
Steigung) abschätzen, ob das Objekt gut oder schlecht
geschätzt werden kann.

[-gb- (Gast)]

Gäbe es eine Möglichkeit, die Grösse direkt zu ermitteln oder brauche 
ich zwei Ergebnisse mit zwei Annahmen um dann je nach Güte des 
Ergebnisses die Mitte zu finden?

[Michael S. (schiko)]

Nicht Bruteforce HT sondern
ein Ransac-HT-Mixmax:

1. Kantenpunkte suchen
2. Kreis aus jeweils 4 zufällige Kantenpunkten bestimmen
3. Mit den Kreisparametern den Houghraum füllen
4. Wiederholen ab 2., wenn noch keine 2 Häufungen erkennbar sind
5. 2 x Kreis fitten

alternativ, mehr Ransac:
1. Kantenpunkte suchen
2. Kreis aus jeweils 4 zufällige Kantenpunkten bestimmen
3. Mit den Kreisparametern den Houghraum füllen
4. Wiederholen ab 2., wenn noch keine Häufungen erkennbar ist
5. Kreis fitten
6. Alle Ktenpunkte wegschmeißen, die nicht zum Kreis gehören
7. Wiederholen ab 2. für 2.Kreis.

So würde ichs machen:
1. Kantenpunkte suchen
2. Kreis aus jeweils 4 zufällige Kantenpunkten bestimmen
3. Nur Kreismittelpunkt 2D Array füllen
4. Wiederholen ab 2., wenn noch keine N Mittelpunkte in max delta r 
entfernung.
5. Häufung der Abstände der Kantenpunkte zum Mittelpunkt bestimmen = r
6. Kreis fitten
7. Alle Ktenpunkte wegschmeißen, die nicht zum Kreis gehören
8. Wiederholen ab 2. für 2.Kreis.


Grüße
Schiko

[Detlef _. (detlef_a)]

Hallo Schiko,

nein, so geht das nicht.
3 Punkte (nicht 4) bestimmen einen Kreis. Wenn Du jetzt aus dem 
schwarz/weiss Bild zufällig 3 Punkte auswählst und die Verteilungsdichte 
der Radien der entstehenden Kreise darstellst, kommst Du für 100k 
Punktetriplets auf die angehängte Kurve. Der Radius bei 175 ist nicht 
vorhanden, der bei ca 375 ist verschoben. Das ist auch anschaulich: Es 
ist relativ unwahrscheinlich, 3 'gute' punkte zu treffen, das Rauschen 
des Binärbildes 'verwischt' vorhandene peaks. Ausserdem ist das kein 
Verfahren, das linear mit der Anzahl der Punkte wächst sondern in der 
dritten Potenz, sowas taugt in der Regel nichts.

Gute Nacht
Detlef

clear

M=imread('c:\\matlab\\myfiles\\powersolutioncloudpostprocessed.jpg 
','jpg');
M=double(M);
kkr=350/2; % kleiner Kreis Radius
gkr=750/2; % grosser Kreis Radius, beide geschaetzt
M=M/max(max(M));
M1=M>0.9;
ind=find(M1==1);
n=size(M1);
nzei=n(1);nsp=n(2);
M2=zeros(size(M1));
%for(k=1:length(ind))
% M2(rem((ind(k)-1),nzei)+1,fix((ind(k)-1)/nzei)+1)=1;
%end;
ind=[(rem((ind-1),nzei)+1) fix((ind-1)/nzei)+1];
n=length(ind)-1;
rrr=zeros(1,2000);

nnn=100000;
for(nn=1:nnn)
  nnn-nn
x1=ind(fix(n*rand(1)+1),:);
x2=ind(fix(n*rand(1)+1),:);
x3=ind(fix(n*rand(1)+1),:);
n1=x1-x2;
n1=n1/norm(n1);
n2=x1-x3;
n2=n2/norm(n2);
xx=inv([n1 ; n2])*[n1*(x1+x2)'/2;n2*(x1+x3)'/2];
rr=norm(xx'-x1);
rr=fix(rr);
if(rr>0) if (rr<2000)
 rrr(rr)=rrr(rr)+1;
 end;end;
end;


return

[Michael S. (schiko)]

Detlef _a schrieb:
> nein, so geht das nicht.
> 3 Punkte (nicht 4) bestimmen einen Kreis.

Solange Du nur die 4 Punkte meinst, hast Du Recht,
der verdammte Auslug ins Flächenland.. ;-)
ansonsten nicht.

> Wenn Du jetzt aus dem
> schwarz/weiss Bild zufällig 3 Punkte auswählst und die Verteilungsdichte
> der Radien der entstehenden Kreise darstellst, kommst Du für 100k
> Punktetriplets auf die angehängte Kurve. Der Radius bei 175 ist nicht
> vorhanden, der bei ca 375 ist verschoben. Das ist auch anschaulich: Es
> ist relativ unwahrscheinlich, 3 'gute' punkte zu treffen, das Rauschen
> des Binärbildes 'verwischt' vorhandene peaks. Ausserdem ist das kein
> Verfahren, das linear mit der Anzahl der Punkte wächst sondern in der
> dritten Potenz, sowas taugt in der Regel nichts.

Das habe ich auch nicht beschrieben.

1. Kantenpunkte ermitteln(!), die "weißen" Punkte aus 
powersolutioncloudpostprocessed.jpg o.ä.
Gradientenermittlung wie auch immer gefiltert.

Aus ein paar(!) Durchläufen, nicht hunderten oder tausenden,
mit 3 zufälligen Punkten aus dieser Menge
hast Du ratzfatz die "ungefähren" gesuchten Mittelpunkte oder Radien.


Dito
Gutu Nacht

Schiko

[J. S. (engineer)]

Michael Schikora schrieb:
> Aus ein paar(!) Durchläufen, nicht hunderten oder tausenden,
> mit 3 zufälligen Punkten aus dieser Menge
> hast Du ratzfatz die "ungefähren" gesuchten Mittelpunkte oder Radien.

Worin siehst Du den Vorteil dieser iterativen Methode? Das ergibt doch 
auch nur eine Reihe von statistischen Werten, die man dann wieder 
mitteln/filtern müsste. Das geht doch mit einer linearen Optimierung 
direkt, zumal, wenn man es mit einem DSP oder Microcontroller machen 
kann.

Anbei ein Bild mit einem fit von 32 Punkten, die "weiss genug" und 
"genügend gut zusammenhängend" und "ausreichend gut verteilt" sind. Das 
kann man problemlos auf 64 Punkte ausdehnen, um es weiter zu 
stabilisieren. Mit einem modifizierten Gauss-Verfahren in 
Determinanten-Struktur ist das ein Leichtes, das zu fitten. Um es 
konkret zu machen, brauchte vor ziemlich geau 20 Jahren ein MS-DOS 16 
Bit-Programm (MS-DOS 6.0) mit dem sogenannten "huge memory model" (was 
waren das Zeiten) auf einem 486DX33 aus der Erinnerung heraus rund 3 
Sekunden :-)

Ich meine, das packt heute sogar ein AVR schneller, oder?

Nachtrag:

Als Idee, ließe sich die Optimierung im vorliegenden Fall sogar direkt 
auf den 3-dimensionalen Raum ausdehnen.

[-gb- (Gast)]

Leider ist es mir komplett entgangen, daß es hier noch weitergegangen 
ist. Muss mal die Benachrichtigung einschalten, denke ich.

Mich würde es interessieren, wie man das fitting optimieren kann.

Die Diskussion war wohl die, ob man drei oder 4 Kreise nimmt. Nach 
meinem Verttändnis wäre mehr beser. Als fit braucht man keine exakte 
Kreisgleichung, sondern eine linear Optimierung.

Wie wirft man unsinnige Werte aus der Gleichung?

[J. S. (engineer)]

Indem Du mit einer geeigneten Strategie prüfst, ob das, was 3 Punkte an 
"Kreis" vortäuschen, einigermaßen zum 4. passt. Man darf auch gerne 5 
Punkte nehmen und schauen, ob der 6. passt.

Die frage ist, wie man die Aspekte: "das, was einige vorgeben",  "Kreis" 
und vor allem "Passen" im Detail weich und zugleich hart genug 
formuliert. Mit etwas Geschick kann man das so formulieren, das man 
keine Iteration benötigt, sondern nur eine Mischung aus 
Mehrheitsentscheid und Statistik (Minimedian). Gerade dieses: "das, was 
einige vorgeben", spannt nämlich nehr, als eine Lösung auf, was ein 
zweidimensionales Optionsfeld für die diskrete Entscheidung "passt" und 
"in DIESEN Kreis" zur Folge hat.

Sowas kann man interativ in C formulieren, validieren, vereinfachen und 
sogar in eine Pipeline ausrollen, um sie in einen FPGA zu stopfen, der 
alle Entscheidungen in einem Takt je Datenpunkt fällt und Punkte zulässt 
oder nicht. Geht dann mit dem Horizontaltakt eines Video :-)

Die Geschichte geht auch in solche Fragestellungen nach noch deutlich 
komplexeren Strukturen rein, insbesondere, wenn die Vorgabemenge etwas 
komplizierter (mehr Rauschen, Fehlbelichtung etc) ist, als in diesem 
Beispiel:
Beitrag "Re: Bildverarbeitung; Skeleton-Berechnung"

[Hi-Tech-Progger S. (Gast)]

Jürgen S. schrieb:
> Indem Du mit einer geeigneten Strategie prüfst, ob das, was 3 Punkte an
> "Kreis" vortäuschen, einigermaßen zum 4. passt. Man darf auch gerne 5
> Punkte nehmen und schauen, ob der 6. passt.

Wie unterscheidest Du, wenn zwei Kreise existieren? Ich meine, man kann 
eigentlich immer einen Kreis durch 3 Punkte legen. Also könnte man A.B.C 
nehmen und dann D verwerfen. Oder man nimmt B.C.D. und verwirft A.

?

[J. S. (engineer)]

Du würdest prüfen, welcher der 3er-Kombinationen zu ähnlichen Kreisen 
führen. Das wäre ja das Kriterium für die richtigen Punkte, bzw für die, 
die man verwerfen müsste.

[-gb- (Gast)]

Nach längerer Zeit ein kleines update:

Es wurden am Ende bis zu 16 Punkte verwendet, um Kreisgleichungen zu 
definieren und zu lösen, weil die Rechenpower vorhanden war und die 
Aufgabe es auch nötig machte, besonders bei weitgehend verrauschten 
Bildern.

[Carlo (Gast)]

Wie werden die Punkte zuvor unterschieden, um sie überhaupt den Kreisen 
zuzuordnen? Es dürfen ja nur solche Punkte mit in die 
Ausgleichsrechnung, welche zu einem Kreis gehören und nicht etwa zu dem 
anderen.

Was passiert mit Punkten, die zu beiden Kreisen gehören (können)?