Suche nach leeren Bereichen in Bild

Question

Diese Frage ist etwas sprachunabhängig, aber mein Werkzeug der Wahl passiert, ein numply Array zu sein.

Was ich tue, den Unterschied von zwei Bildern über PIL nimmt:

img = ImageChops.difference(img1, img2) 

Und ich möchte die rechteckige Bereiche finden, die sich von einem Bild zum anderen enthalten. Natürlich gibt es die eingebaute .getbbox() Methode, aber wenn es zwei Regionen mit Änderungen gibt, wird eine Box von einer Region zur anderen zurückgegeben, und wenn es nur 1 Pixel Änderungen in jeder Ecke gibt, wird das ganze Bild zurückgegeben.

Zum Beispiel ist folgendes zu beachten, wo o ein Nicht-Null-Pixel ist:

______________________ 
|o   ooo | 
|  oooo ooo | 
|  o    | 
|  o o   | 
|     | 
|  oo  o  | 
| o o  ooo | 
|  oo  ooooo | 
|    ooo | 
|    o  | 
|____________________| 

Ich mag würde 4x4-Tupeln mit den Begrenzungskästen für jeden von Null Region zu erhalten. Für den Grenzfall der

oooo 
o 
o o 

Struktur, sie ist nicht sehr besorgt, wie die gehandhabt wird - entweder immer beiden Teile einzeln oder zusammen, weil die Grenzen der invertierten L-Form vollständig über die Grenzen des einzelnes überlappen Pixel.

Ich habe noch nie etwas so fortgeschrittenes mit Bildverarbeitung gemacht, also wollte ich etwas Input bekommen, bevor ich wirklich etwas schreibe (und wenn es bereits existierende Methoden in den Modulen gibt, die ich bereits benutze, begrüße ich sie!) .

Meine psuedocode-ish Version geht so etwas:

for line in image: 
    started = False 
    for pixel in line: 
     if pixel and not started: 
     started = True 
     save start coords 
     elif started and not pixel: 
     started = False 
     save end coords (x - 1 of course) 

Das sollte mir eine Liste von Koordinaten, aber dann muss ich feststellen, ob die Bereiche angrenzen. Ich könnte das mit einer graphischen Suche machen? (Wir haben im letzten Semester viel mit DFS und BFS in Algorithmen gemacht) Natürlich könnte ich das stattdessen/in Verbindung mit meinen vorherigen Loops tun?

Ich werde das nicht auf "großen" Bildern tun - sie werden von einer Webcam gezogen und die beste, die ich derzeit habe 640x480. Ich würde höchstens 720p oder 1080p machen, aber das ist weit genug in der Zukunft, dass es keine wirkliche Sorge ist.

Also meine Frage (n): Bin ich auf dem richtigen Weg, oder bin ich weg? Und noch wichtiger: Gibt es eingebaute Funktionen, die mich daran hindern, das Rad neu zu erfinden? Und schließlich, gibt es irgendwelche guten Ressourcen, die ich betrachten sollte (Tutorials, Papiere, etc.), die hier helfen werden?

Danke!

Answer 1

Ich glaube, scipy's ndimage module hat alles, was Sie brauchen ...

Hier ist ein kurzes Beispiel

import numpy as np 
import scipy as sp 
import scipy.ndimage.morphology 

# The array you gave above 
data = np.array( 
     [ 
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
      [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
      [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
      [0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
      [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
      [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
      [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0], 
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
     ]) 


# Fill holes to make sure we get nice clusters 
filled = sp.ndimage.morphology.binary_fill_holes(data) 

# Now seperate each group of contigous ones into a distinct value 
# This will be an array of values from 1 - num_objects, with zeros 
# outside of any contigous object 
objects, num_objects = sp.ndimage.label(filled) 

# Now return a list of slices around each object 
# (This is effectively the tuple that you wanted) 
object_slices = sp.ndimage.find_objects(objects) 

# Just to illustrate using the object_slices 
for obj_slice in object_slices: 
    print data[obj_slice] 

Diese Ausgänge:

[[1]] 
[[1 1 1] 
[1 1 1]] 
[[1 1 1 1] 
[1 0 0 0] 
[1 0 0 1]] 
[[1]] 
[[0 1 1 0] 
[1 0 0 1] 
[0 1 1 0]] 
[[0 0 1 0 0] 
[0 1 1 1 0] 
[1 1 1 1 1] 
[0 1 1 1 0] 
[0 0 1 0 0]] 

Beachten Sie, dass die "object_slices" sind im Grunde, was Sie ursprünglich gefragt, ob Sie die aktuellen indicies benötigen.

Edit: Ich wollte nur darauf hinweisen, dass trotz es erscheinen, um richtig die Kante Fall von

[[1 1 1 1] 
[1 0 0 0] 
[1 0 0 1]] 

es eigentlich nicht (also die zusätzlichen lone [[1]]) handhaben. Sie können das sehen, wenn Sie die „Objekte“ Array ausdrucken und an Objekten 3 & 4.

[[1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0] 
[0 0 0 0 0 0 3 3 3 3 0 0 0 2 2 2 0 0 0 0] 
[0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0] 
[0 0 0 0 0 0 3 0 0 4 0 0 0 0 0 0 0 0 0 0] 
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] 
[0 0 0 0 0 5 5 0 0 0 0 0 0 0 6 0 0 0 0 0] 
[0 0 0 0 5 5 5 5 0 0 0 0 0 6 6 6 0 0 0 0] 
[0 0 0 0 0 5 5 0 0 0 0 0 6 6 6 6 6 0 0 0] 
[0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0] 
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0]] 

Hoffnung einen Blick darauf werfen, das hilft!

[1]

Answer 2

Sie können im Bild nach verbundenen Komponenten suchen und dann die Begrenzungsrechtecke dieser Komponenten bestimmen.

Answer 3

Ein Clustering-Paket (ie this) sollte in der Lage sein, die meisten der Arbeit (finden Sie verbundene Pixel). Das Auffinden der Begrenzungsbox für einen Cluster ist dann trivial.