Ricerca di regioni vuote nell'immagine

Question

Questa domanda è in qualche modo indipendente dal linguaggio, ma il mio strumento di scelta sembra essere una matrice numpy.

Quello che sto facendo sta prendendo la differenza di due immagini via PIL:

img = ImageChops.difference(img1, img2) 

E voglio trovare le regioni rettangolari che contengono le modifiche da un'immagine all'altra. Ovviamente c'è il metodo integrato .getbbox(), ma se ci sono due regioni con modifiche restituirà una casella da una regione all'altra, e se ci saranno solo 1 pixel in ogni angolo restituirà l'intera immagine.

Per esempio considerare i seguenti dove o è un pixel diverso da zero:

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

Vorrei ottenere 4x4-tuple contenenti i riquadri di limitazione per ciascuna regione non-zero. Per il caso bordo della struttura

oooo 
o 
o o 

, io non sono terribilmente preoccupato come sia gestita - o ottenere entrambe le sezioni separatamente o insieme, perché i limiti della forma invertita-L si sovrappongono completamente i limiti del singolo pixel.

Non ho mai fatto nulla di così avanzato con l'elaborazione delle immagini, quindi volevo ottenere qualche input prima di scrivere davvero qualcosa (e se ci sono già dei metodi preesistenti nei moduli che sto già usando, li accolgo!) .

La mia versione psuedocodarlo-ish va qualcosa come questo:

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) 

Questo mi dovrebbe dare un elenco di coordinate, ma poi devo determinare se le regioni sono contigue. Potrei farlo con una ricerca di tipo grafico? (Abbiamo fatto un sacco di DFS e BFS in Algorithms lo scorso semestre) Ovviamente immagino di poterlo fare invece/insieme ai miei precedenti cicli?

Non lo farò su immagini "grandi" - sono estratte da una webcam e la migliore che ho attualmente è 640x480. Al massimo farei 720p o 1080p, ma è abbastanza lontano nel futuro che non è una vera preoccupazione.

Quindi la mia domanda (s): Sono diretto sulla strada giusta, o sono lontano? E ancora più importante, ci sono funzioni integrate che mi impediscono di reinventare la ruota? E infine, ci sono delle buone risorse che dovrei guardare (tutorial, documenti, ecc.) Che aiuteranno qui?

Grazie!

Answer 1

Credo che scipy's ndimage module abbia tutto ciò che serve ...

Ecco un esempio veloce

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] 

Questo uscite:

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

notare che la "object_slices" sono fondamentalmente quello che originariamente chiesto, se avete bisogno di indicies attuali.

Edit: Volevo solo sottolineare che, nonostante esso appare a gestire correttamente il caso limite di

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

in realtà non (Così l'extra solitario [[1]]). Si può vedere questo se stampare la matrice "oggetti" e dare un'occhiata a oggetti 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]] 

Speranza che aiuta!

[1]

Answer 2

È possibile cercare i componenti collegati nell'immagine e quindi determinare i limiti di questi componenti.

Answer 3

Un pacchetto di clustering (ie this) dovrebbe essere in grado di eseguire gran parte del lavoro (trovare i pixel connessi). Trovare il riquadro di delimitazione per un cluster è banale allora.