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