contorno in pitone per matrice binaria 2D

Question

Voglio calcolare uno scafo convesso attorno ad una forma in una matrice binaria NxM. L'algoritmo dello scafo convesso prevede un elenco di coordinate, quindi prendo numpy.argwhere (im) per avere tutte le coordinate del punto di forma. Tuttavia, la maggior parte di questi punti non contribuisce allo scafo convesso (si trovano all'interno della forma). Poiché il tempo di calcolo dello scafo convesso è almeno proporzionale al numero di punti che riceve come input, ho escogitato un'idea per filtrare in anticipo la pletora di punti inutili e passare solo quelli che coprono il contorno. L'idea è abbastanza semplice, che per ogni riga nella matrice binaria NxM prendo solo gli indici minimi e massimi. Quindi ad esempio:

im = np.array([[1,1,1,0],
              [1,0,1,1],
              [1,1,0,1],
              [0,0,0,0],
              [0,1,1,1]], dtype=np.bool)
outline = somefunc(im)

Quindi lo schema dovrebbe leggere (in tuple o come un array numpy 5x2, non mi dispiace):

[(0,0),(0,2),(1,0),(1,3),(2,0),(2,3),(4,1),(4,3)]

Qualsiasi scafo convesso stretto attorno a questa forma (im), deve essere un sottoinsieme di questi punti (contorno). In altre parole, se " somefunc () " è efficace nel filtrare i punti interni, quindi consente di risparmiare tempo per il calcolo dello scafo convesso.

Ho un codice che fa il trucco di cui sopra, ma spero che qualcuno abbia un approccio più intelligente (leggi più veloce) poiché devo eseguirlo molte volte. Il codice che ho è:

# I have a 2D binary field. random for the purpose of demonstration.
import numpy as np
im = np.random.random((320,360)) > 0.9

# This is my algorithm so far. Notice that coords is sorted.
coords = np.argwhere(im)
left = np.roll(coords[:,0], 1, axis=0) != coords[:,0]
outline = np.vstack([coords[left], coords[left[1:]], coords[-1]])

Un'altra idea che ho avuto è stata quella di utilizzare il riduttore () di Python, quindi avrei bisogno di scorrere l'elenco dei coords solo una volta. Ma ho difficoltà a trovare una buona funzione di riduzione.

Qualsiasi aiuto sarebbe molto apprezzato!

modifica

Nel frattempo ho trovato un modo più veloce per passare da im direttamente a outline . Almeno con immagini di grandi dimensioni questo è significativamente più veloce. In apparente assenza di una soluzione esterna, la sto proponendo come soluzione a questa domanda.

Tuttavia, se qualcuno conosce un metodo ancora più veloce, ti preghiamo di parlare :)

Answer 1

In assenza di una risposta accettabile, inserisco il mio miglior codice funzionante come soluzione.

def outline(im):
    ''' Input binary 2D (NxM) image. Ouput array (2xK) of K (y,x) coordinates
        where 0 <= K <= 2*M.
    '''
    topbottom = np.empty((1,2*im.shape[1]), dtype=np.uint16)
    topbottom[0,0:im.shape[1]] = np.argmax(im, axis=0)
    topbottom[0,im.shape[1]:] = (im.shape[0]-1)-np.argmax(np.flipud(im), axis=0)
    mask      = np.tile(np.any(im, axis=0), (2,))
    xvalues   = np.tile(np.arange(im.shape[1]), (1,2))
    return np.vstack([topbottom,xvalues])[:,mask].T

Answer 2

Questo incarico sembra compiere la stessa cosa dei tuoi ultimi due passaggi:

outline = np.array(dict(reversed(coords)).items() + dict(coords).items())

Non so se è più veloce, comunque.

Answer 3

Per una soluzione più generale, è possibile utilizzare un qualche metodo di rilevamento dei bordi per trovare solo i punti dei bordi. Credo (Google ..) che NumPy abbia un filtro sobel integrato, che lo farà.