Abstand (min, max, avg) in Bitmap

[Furtbichler]

Du musst ja nicht jedesmal, wenn Du einen Punkt analysierst, die ganze Bitmap durchgehen.

1. Ermitteln der Positionen aller Punkte und aufteilen in Schwarz/Weiß.
2. Ermitteln aller Abstände zwischen zwei Punkten (weiss ->schwarz)
3. Ermitteln der Zielwerte Min/Max/Avg für jeden weissen Punkt

Erster Durchlauf: O(h*b). h,b = Dimension des Bitmaps.
Zweiter und dritter Durchlauf: O(n*m). n= Anzahl der gefundenen weissen Punkte, m=schwarze Punkte

Ist n*m überschaubar, gehts eins-fix-drei, Im theoretischen Worstcase jedoch O((h*b)^2). Die Frage lautet jedoch: Was ist der realistische Worstcase?

Selbst bei einigen Tausend Punkten solltest Du in überschaubarer Zeit hinkommen.

Code:

For x := 0 to bitmap.width - 1 do
  For y:= 0 to bitmap.height - 1 do
     case Bitmap.pixel[x,y] of 
       White : WhitePoints.Add(x,y):
       Black : BlackPoints.Add(x,y):

Foreach Point W in WhitePoints do begin
  Foreach Point B in BlackPoints do
    W.Distances.Add(Distance(W,B));

  Output ('White Point ', W, 'Min=', W.Distance.Min, 'Max=', W.Distances.Max, 'Avg=',W.Distances.Avg);
end

[Medium]

Sind das nun schwarze Punkte auf weissem Hintergrund, oder schwarze und weisse Punkte mite "Leerraum" dazwischen? Heisst "Punkt" bei dir Pixel, oder sind das eher kleine Pixelgrüppchen? Was ist der minimale und maximale Abstand in deinem Fall? (Verständnis des letzteren hängt von den anderen Fragen ab vermute ich.)

Eine Skizze, oder besser noch ein Realfall als Bild wären hier verdammt hilfreich. Weil so ohne weiteres an Kenntnis über die Struktur, bleibt erstmal wirklich nur alle paarweisen Abstände einzeln durchzukauen. Man kann zwar, wenn es nur um größer/kleiner geht zunächst die Wurzelei einsparen, aber es bleibt dennoch eine Zahlenschlacht

[cltom]

Vielen Dank einmal für die Antworten.

Zu den Fragen:

Die Bitmaps enthalten Kreise und Rechtecke in regelmäßiger Verteilung/Anordnung. Typischerweise 10-40% der Fläche ist schwarz. Im Wesentlichen ein (Loch)Gitter, Beispiel anbei.

Bekannt sind die Koordinaten der Punkte sowie deren Radius. Gesucht ist eben von jedem (weissen) Punkt der kleinstmögliche Weg zum nächsten schwarzen Punkt. Wenn ich also irgendwo auf einem weissen Pixel lande, wie weit ist der Weg maximal, bis ich zum nächsten schwarzen Punkt komme. Und über diesen Weg eine Art Histogramm oder eben min. max. avg. (der kürzeste Weg ist offensichtlich gerade ein Pixel zum nächsten Punkt, interessant sind mehr der mittlere und der längste Weg).

In Anlehnung an Deinen Vorschlag, Furtbichler, könnte man also die Randpunkte der Kreise nehmen und damit schon mal eingrenzen. Die Menge aller Punkte innerhalb des Kreises fällt weg, das reduziert den Aufwand.

Alternativ: ich gehe für jeden weissen Punkt alle (bekannten) Objekte durch und schaue, wie weit sie entfernt sind.

Je mehr ich darüber nachdenke, desto eher wird klar, dass der Ansatz falsch ist, es pixelbasiert zu lösen und nicht anhand der Koordinaten der Objekte ...

[Medium]

Darauf zielte meine Fragerei auch ab Wenn du die Mittelpunkte und Radien hast, wird das Problem ja fast schon trivial. Man kann sich zwar nicht sparen alle "weissen Pixel" durchzugehen, aber dann musst du ja nur noch die Abstände zu deinen Mittelpunkten minus der Radien errechnen.

[Medium]

Mal obiges in Code gegossen, da ich leider zuhause aber kein Delphi habe in C#. Aber das geht hoffe ich als Pseudocode durch (Achtung, grausig Quick&Dirty):

Code:

      public int[] CentersX, CentersY;
      public int[] Radii;
      
      public float MinDist(int x, int y)
      {
         float min = float.MaxValue;
         for (int i=0; i<CentersX.Length; i++)
         {
            float xx = x-CentersX[i];
            float yy = y-CentersY[i];
            float tmp = (float)(Math.Sqrt(xx*xx+yy*yy)-(float)Radii[i]);
            if (tmp<min) min = tmp;
         }
         return min;
      }
      
      void Button1Click(object sender, EventArgs e)
      {
         Bitmap b = new Bitmap(pictureBox1.Width, pictureBox1.Height);
         // Zufällige Kreise erzeugen. 4-9 Stück, mit Radius von 50-100 und Mittelpunkt im Bild
         Random rng = new Random();
         int count = (int)(rng.NextDouble()*5)+5; // im Bild unten war count = 9
         CentersX = new int[count];
         CentersY = new int[count];
         Radii = new int[count];
         for (int i=0; i<count; i++)
         {
            CentersX[i] = (int)(rng.NextDouble()*pictureBox1.Width);
            CentersY[i] = (int)(rng.NextDouble()*pictureBox1.Height);
            Radii[i] = (int)(rng.NextDouble()*50)+50;
         }
         for (int y=0; y<pictureBox1.Height; y++)
         {
            for (int x=0; x<pictureBox1.Width; x++)
            {
               float f = MinDist(x, y);
               // die Verwurstung mit 127 ist nur so, damit ich nachher nett auf Grauwerte zwischen 0 und 254 skalieren kann,
               // und die Abnahme in der Farbe doppelt so schnell ist wie die eigentliche Distanz. War optisch netter.
               if ((f>0) && (f<=127)) 
               {
                  int c = (int)((127-f)*2f);
                  b.SetPixel(x, y, Color.FromArgb(255, c, c, c));
               }
               else
               {
                  b.SetPixel(x, y, Color.Black);
               }
            }
         }
         pictureBox1.Image = b;
      }

Das Bild im Anhang ist so entstanden. Zumindest bei konstanten Radien ist man da, wie ich vermutet hatte, ganz ganz nah an der Delaunay-Triangulation. Vielleicht ist über diesen Weg noch etwas für dich herauszuholen, weil auch wenn man mit o.g. Variante "nur" O(Width*Height*CircleCount) hat, ist es zumindest für Echtzeiteinsätze kaum geeignet. (Der Code von mir unter C# brauchte für 800x600 Pixel große Bilder so runde 200-300ms auf einem Core i7 950.)
Edit: Schaut ein wenig aus wie ein Kalottenmodell


Eine ganz andere Idee wäre noch Gaussfilterung des Ausgangsbildes. Bei geeignet großem Radius des Filters sollte sich nachher ein zumindest ähnliches Bild ergeben, nur ist ein so großer, akkurater Gaussfilter auch nicht gerade der Performance bester Freund, und man würde da keine echten Distanzen bekommen, sondern nur ablesen können, an welchen Stellen sich die "Ridges" in den Mitten zwischen den Kreisen befänden. Am Ende muss man schließlich egal wie jeden Pixel einzeln anfassen.
Noch eine Methode wäre eine "missbrauchte" Shepard Interpolation, die aber das gleiche Laufzeitverhalten wie die oben implementierte Version hat.

[cltom]

whow, das ist immer wieder unglaublich, wie schnell man hier hochwertiges Futter bekommt. Ich schaue mir das mal durch, vielen Dank!