Abstand (min, max, avg) in Bitmap

[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.