Autor Beitrag
UweK
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 51
Erhaltene Danke: 1

Win 7
Delphi Enterprise XE6
BeitragVerfasst: Mi 29.12.21 16:29 
Hallo,

Ich bin auf der Suche nach einer Fit-Prozedur, die in ein 2-dimensionales Bild der Form "Intensität = f(x,y)" einen Kreis fitten kann. Vielleicht ist jemandem von euch so etwas schon mal über den Weg gelaufen? Oder zumindest etwas ähnliches, an dem ich mir anschauen könnte, wie man das selbst macht?

Ich habe ein 2-dimensionales Bild
ausblenden Delphi-Quelltext
1:
Pixelbild: array of array of Double					

mit einer Größe von ungefähr 1000 x 1000 Punkten, wobei jeder Punkt durch seine 3 Werte (x,y,Intensität) beschrieben ist. (x,y) ist die Lage des Punktes in dem 2-dimensionalen Rechteck. Schaut man sich die Intensitäten dieser Punkte an, so bilden sie einen schmalen Kreisring von ca. 30 Punkten Breite, der sich in seiner Intensität gut vom Untergrund innerhalb und außerhalb des Kreisrings abhebt. Das ganze ist ein bisschen verrauscht mit etwas unscharfen Rändern des Kreisringes.

In diesem Bild möchte ich den Mittelpunkt des Kreisringes (x-m,y-m) bestimmen. Also eine scharfe Kreislinie mit Mittelpunkt (x-m,y-m) und Radius R so hinein fitten, dass sie dem Verlauf der Intensität des Kreisringes möglicht nahe kommt.

1-dimensionale Fits für Kurven der Form "y=f(x)" habe ich gefunden, z.B. im Mathematik-Paket "DMath". Aber nichts 2-dimensionales.

Über Tipps würde ich mich sehr freuen!



Nachtrag 1: Ich habe vergessen mit aufzuschreiben, dass der Fit intensitäts-gewichtet erfolgen soll. Das heißt, ein Punkt mit höherer Intensität soll sich stärker auf die Position des gefitteten Kreises auswirken, als ein Punkt mit kleinerer Intensität. Trotzdem wäre eine Fitprozedur ohne einen solchen Gewichtsfaktor schon eine Hilfe, sofern der Quelltext dafür zugänglich ist, so dass ich versuchen könnte, den Gewichtsfaktor nachträglich dazu zu basteln. Was leider nicht hilft, wäre eine ungewichtete Fitprozedur aus einer vorgefertigten Grafik-Bibliothek, die nur in compilierter Form als Blackbox vorliegt.

Nachtrag 2: Ich habe ein Beispielbild angehängt. Der Kreis auf den es ankommt ist hier schon am Rand teilweise aus dem Bild herausgerutscht. Manchmal ist er auch kleiner und komplett drin. Das schwarze Streifenmuster sind tote Bereiche zwischen mehreren nebeneinander aufgebauten Einzeldetektoren. Durch diese Lücken und die manchmal fehlenden Kreisteile am Rand funktionieren einfache Schwerpunktrechnungen leider nicht, wie sie unten gerade mandras vorgeschlagen hat. Ich muss es irgendwie auf die Kreisform selbst beziehen.
Einloggen, um Attachments anzusehen!


Zuletzt bearbeitet von UweK am Mo 03.01.22 15:46, insgesamt 1-mal bearbeitet
mandras
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 429
Erhaltene Danke: 107

Win 10
Delphi 6 Prof, Delphi 10.4 Prof
BeitragVerfasst: Fr 31.12.21 01:24 
Als allererstes käme mir der Schwerpunkt der Figur in den Sinn, vorausgesetzt, die Qualität des Bildes ist so wie Du sagtest (eigentlich nur der Kreisring relevant, Rauschen etc. vernachlässigbar).

Ein hingetippseltes Beispiel:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
procedure TForm1.Button1Click(Sender: TObject);
var i,j:integer;
    mx,my:double;
    anz, pw:integer;
    bb,bh:integer;
const Schwelle=50;
begin
 mx:=0; my:=0; anz:=0;
 bb:=Image1.Picture.Bitmap.Width;
 bh:=Image1.Picture.Bitmap.Height;
 for i:=0 to bb-1 do begin
  for j:=0 to bh-1 do begin
  pw:= 255-(Image1.Picture.Bitmap.Canvas.Pixels[i,j] and 255);
  if pw > Schwelle then begin
   mx := mx+i;
   my:=my+j;
   anz:=anz+1;
  end;
  end;
 end;
 mx:=mx / anz;
 my:=my / anz;
 Image1.Picture.Bitmap.Canvas.MoveTo(round(mx),round(my)-10);
 Image1.Picture.Bitmap.Canvas.LineTo(round(mx),round(my)+10);
 Image1.Picture.Bitmap.Canvas.MoveTo(round(mx)-10,round(my));
 Image1.Picture.Bitmap.Canvas.LineTo(round(mx)+10,round(my));
end;

Die dahinterstehende Idee:
Auf dem Formular ist eine Image-Komponente, in der das zu bewertende Bild ist (BMP 24Bit berücksichtigt wird nur ein Farbkanal).
Hier ist das Bild weiß, der Kreisring soll dunkel sein, Beispiel habe ich hier beigefügt.

Wenn ein Pixel dunkler als ein Schwellwert ist, werden dessen Koordinaten i/j zur Mittelpunktsvariablen mx/my hinzuaddiert.

mx/anz bzw my/anz stellen am Schluß den Mittelwert der Koordinaten der gefundenen Pixel des Kreises dar, hierum wird ein Fadenkreuz gezeichnet.

Bei komplexeren Anforderungen (geringe Bildqualität o.ä.) sind ggf. andere Verfahren von Vorteil.

Ein frohes neues!

Moderiert von user profile iconTh69: Beitragsformatierung überarbeitet.
Einloggen, um Attachments anzusehen!
UweK Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 51
Erhaltene Danke: 1

Win 7
Delphi Enterprise XE6
BeitragVerfasst: Mo 03.01.22 15:50 
Hallo mandras,

Danke für den Tipp, aber er hilft mir leider noch nicht weiter. Ich habe in meiner Frage noch ein paar zusätzliche Klarstellungen und ein Beispielbild hinzugefügt.
mandras
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 429
Erhaltene Danke: 107

Win 10
Delphi 6 Prof, Delphi 10.4 Prof
BeitragVerfasst: Mo 03.01.22 18:37 
Dann fiele mir noch eine Auto/Kreuzkorrelation ein, da ich aber zuletzt so vor 15 Jahren für Mustererkennungen damit gearbeitet habe bekomme ich das wahrscheinlich nicht so "auf die Schnelle" beisammen, werde mich aber heut abend mal daransetzen.
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: Mi 05.01.22 15:04 
Du kannst eine de.wikipedia.org/wiki/Hough-Transformation machen.

Dabei wertest du alle Pixel aus und jeder Pixel > x ist dann ein "Zeuge" für einen möglichen Kreis. Also ein Pixel an Stelle 10, 10 könnte bspw. von folgenden Kreisen stammen: 11,10,R=1 oder 12,10,R=2 oder 13,10,R=3 oder ...

in einem 3D Array kannst du diese potenziellen Kreise inkrementieren. Am Ende guckst du dann, welcher Punkt die meisten "Zeugen" hat - das sind dann deine Kreisparameter.

Für diesen Beitrag haben gedankt: Narses
FinnO
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1331
Erhaltene Danke: 123

Mac OSX, Arch
TypeScript (Webstorm), Kotlin, Clojure (IDEA), Golang (VSCode)
BeitragVerfasst: Mi 05.01.22 19:06 
Eine Alternative zur Hough-Transformation, die user profile iconjfheins angeregt hat, wäre RANSAC.

Der Vorteil von Ransac wäre, dass die Laufzeit von vornehinein klar ist, der Nachteil ist, dass man nicht garantiert den besten Fit erhält. Musst du abwägen ;-).

Für diesen Beitrag haben gedankt: Narses
UweK Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 51
Erhaltene Danke: 1

Win 7
Delphi Enterprise XE6
BeitragVerfasst: Di 18.01.22 17:27 
Hallo allerseits,

Danke für die Ideen. Am Ende habe ich nun doch noch ein anderes, aber sehr gutes Lösungsrezept gefunden, das sich leicht nachkochen ließ und auch tatsächlich so funktioniert wie angegeben:

goodcalculators.com/...-squares-calculator/

Nach dieser Methode kann man für eine Punktmenge einen Least-Square Kreis sogar direkt mit einer analytischen Formel berechnen, ganz ohne numerischen Fit und dessen immanente Unannehmlichkeiten (Startwerte probieren, Abbruchgenauigkeit usw.). Man löst einfach die Matrizengleichung bei "Finding A, B, and C with Matrices" und erhält sofort Mittelpunkt (k,m) und Radius r des gesuchten Kreises.

Für diesen Beitrag haben gedankt: icho2099