contour python pour matrice binaire 2D

Question

Je souhaite calculer une coque convexe autour d’une forme dans une matrice binaire NxM. L’algorithme de la coque convexe attend une liste de coordonnées, je considère donc numpy.argwhere (im) comme ayant toutes les coordonnées du point de forme. Cependant, la plupart de ces points ne contribuent pas à la coque convexe (ils se trouvent à l'intérieur de la forme). Parce que le temps de calcul de la coque convexe est au moins proportionnel au nombre de points qu’il reçoit en entrée, j’ai imaginé une idée pour filtrer au préalable la pléthore de points inutiles et ne transmettre que ceux qui couvrent le contour. L'idée est assez simple, pour chaque ligne de la matrice binaire NxM, je ne prends que les indices minimal et maximal. Ainsi, par exemple:

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)

Ensuite, le contour devrait se lire (en tuples ou sous forme de tableau numpy 5x2, cela ne me dérange pas):

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

Toute coque convexe serrée autour de cette forme (im), doit constituer un sous-ensemble de ces points (contours). En d'autres termes, si "somefunc ()" est efficace pour filtrer les points intérieurs, il permet de gagner du temps pour le calcul de la coque convexe.

J'ai un code qui fait le tour ci-dessus, mais j'espère que quelqu'un adoptera une approche plus intelligente (plus rapide), car j'ai besoin de l'exécuter plusieurs fois. Le code que j'ai est:

# 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]])

Une autre idée que j'ai eue était d'utiliser la réduction () de Python afin de ne devoir parcourir la liste des coordonnées qu'une seule fois. Mais j'ai du mal à trouver une bonne fonction réductrice.

Toute aide serait grandement appréciée!

modifier

Entre temps, j'ai trouvé un moyen plus rapide de passer directement de im à plan . Au moins avec les grandes images, c'est beaucoup plus rapide. En l'absence apparente d'une solution externe, je la propose comme solution à cette question.

Néanmoins, si quelqu'un connaît une méthode encore plus rapide, veuillez parler plus haut:)

Answer 1

En l'absence d'une réponse acceptable, je poste mon meilleur code de travail en tant que solution.

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

Cette tâche semble avoir le même résultat que vos deux dernières étapes:

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

Je ne sais pas si c'est plus rapide, cependant.

Answer 3

Pour une solution plus générale, vous pouvez utiliser une méthode de détection de bord inhabituelle pour rechercher uniquement les points de bord. Je crois (Google ..) que NumPy a un filtre sobel intégré, qui le fera.