Algorithmus für die optimale Platzierung von beschnittenen Regionen, um Merkmale (Blobs) in einem Bild zu erfassen

Question

Ich habe ein großes Bild, das "Blobs" von Interesse vor einem Hintergrund enthält. Ich habe die Position (Zentroid, Bounding Box, Area) aller Blobs. Ich möchte eine begrenzte Anzahl von Regionen einer festen Größe im Bild zuschneiden, die es mir ermöglichen, die meisten Blobs zu erfassen. Beispiel unten für 1, 2 oder 3 beschnittene Regionen im selben Bild.

Dieses Beispiel zeigt, dass 1-Region Beschneiden (in rot) relativ einfach: nur die Region auszuwählen, mit so vielen wie möglich Blobs. Dies kann gelöst werden, indem einfach alles versucht wird oder möglicherweise eine Dichte von Blobs unter Verwendung eines Kerndichte-Schätzers oder ähnlichem berechnet wird.

Aber das Beschneiden von 2 Regionen (in blau gestrichelt) beschneidet nicht nur die nächstbeste Ernte nach der ersten Auswahl. Es ist ein neues Problem, bei dem ich die optimale Kombination von 2 Pflanzen finden muss. Der Versuch, alle Kombinationen von 2 Pflanzen (Brute Force) zu verwenden, wird wahrscheinlich zu rechenintensiv (ich habe viele Bilder zu verarbeiten und sie sind groß).

In ähnlicher Weise ist das Beschneiden von 3 Regionen (grün) ein neues Problem, für das Brute Force noch weniger geeignet ist. In diesem speziellen Beispiel sind 2 der 3 Regionen identisch mit der blauen und eine neue hinzugefügt, aber dies ist nicht der allgemeine Fall (Ich wollte nur ein etwas komplexes Szenario zeigen).

Ich habe keine Ahnung in Bezug auf den Algorithmus, um den Fall n-Ernten zu lösen. Ich frage mich, ob es eine theoretische/bekannte Lösung für dieses Problem gibt.

Zusätzlich:

• die Geometrie des Problems ist, dass etwa des obigen Beispiels (maximal zwei Ernten über die Höhe des Bildes, viele Kulturen über die Breite); in dem Fall, dass vereinfacht die Dinge
• Kulturen nicht
• Blobs sollten wie zentriert wie möglich in der Ernte schneiden sollen (dh https://dl.dropboxusercontent.com/u/1047321/SO_crop/cutout_one_blob.png )
• Kulturen innerhalb der ursprünglichen Bildgrenzen (vgl entweder Beispiel oben)
bleiben soll
• die Fläche des Blobs sollte berücksichtigt werden (ich interessiere mich mehr für große Blobs als kleine); aber das kann wahrscheinlich in jedem Algorithmus eingeführt werden, indem jedem Blob eine Gewichtung zugeordnet wird, um die Punktzahl jedes Zuschnittslayouts zu berechnen.
• ist es in Ordnung, einige Blobs zu verlassen. Tatsächlich werde ich wahrscheinlich einen Parameter für die Kostenkomplexität berechnen, wie etwa wie viele neue Blobs, die eine Feldfrucht hinzufügen, einen Schwellenwert erhalten und einstellen würde, unter dem ich keine Feldfrüchte mehr hinzufügen würde.

Vielen Dank im Voraus für jeden Zeiger.

PS: Die Programmiersprache spielt hier keine Rolle, da der Kern des Algorithmus (die optimale Position der Pflanzen bei der Position/Größe der Blobs) nur kleine Arrays (Position/Größe von ~ 100 Blobs pro Bild) benötigt) berechnet werden. Ich werde wahrscheinlich Python oder R verwenden.

Answer 1

Wenn die Blobs relativ klein sind, wie im Bild gezeigt, könnten Sie k-Means Clustering mit dem Blob-Zentrum x, y-Paare ausführen. Das Python scikit-learn-Paket ist ziemlich ausgereift und sollte gut funktionieren: http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html (function fit_predict des KMeans-Klassifikators)

k ist ein Eingang und bezeichnet die Anzahl der Cluster, die Sie wollen. Der Algorithmus teilt die Blobs (Samples) in k Cluster (Sets) auf. Sie könnten dann den x, y Rahmen (min-x, max-x, min-y, max-y) jedes Satzes berechnen und auch die einzelnen Größen der Blobs aufnehmen oder einfach deren Max nehmen, wenn sie ziemlich klein sind.

Sie könnten dann die Cluster nach ihrem # blobs/frame-area-Verhältnis sortieren und sie z. bis entweder genug Blobs bedeckt sind (fertig) - oder Ihre gesamte Fläche zu groß wird (in diesem Fall erneut mit größerem k).