Abstand (min, max, avg) in Bitmap

[cltom]

Hallo,

folgende, nicht ganz leicht zu erklärende, Problemstellung:

Ich habe eine (monochrome) Bitmap mit verschiedenen Elementen, im einfachsten Fall ein paar verteilte Punkte (schwarz). Was ich nun brauche ist der mittlere (maximale und minimale) Abstand jedes (weissen) Pixels zum nächstgelegenen (schwarzen) Punkt.

In erster Näherung könnte ich für jeden (weissen) Punkt der Bitmap alle anderen Punkte der Bitmap durchgehen und prüfen, ob der Punkt a) schwarz ist, wenn ja b) den Abstand ermitteln. Wenn der untersuchte Punkt selbst schwarz ist, dann gilt Abstand=0

Der Aufwand dafür beträgt aber (bitmap.height * bitmap.width)² Durchläufe. Bei 1 MP sind das also 10^12 Durchläufe. Bei hohem Anteil (schwarzer) Punkte sinkt der Aufwand natürlich, aber dennoch ,der Aufwand erscheint groß. Bevor ich aber diese Brute-Force-Methode mache, frage ich mal:

Hat jemand eine klügere Idee?

Ein Ansatz wäre, nur ein Gitter von jedem x. Pixel zu verwerten, den Fehler könnte man versuchen, mit variierendem x abzuschätzen. Aber letztlich ist das nur "less brute".

Würde die Kenntnis der Koordinaten der `(schwarzen) Punkte etwas bringen?

danke für Tipps
grüße
tom

[KarstenK]

Hallo,

Erosion und Dilatation wäre hier eine Variante.

Die Operation iterative solange durchführen, bis keine weissen Punkte mehr da sind. und in jeden Stufe die Pixel welche wegfallen mit der Schrittweite kodieren. Damit erhälts du dannn eine Landkarte mit den (minimalen) Abständen.

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

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