contorno python para a matriz 2D binário

Question

Eu quero calcular um casco convexo em torno de uma forma em uma matriz NxM binário. O algoritmo convexo casco espera uma lista de coordenadas, então eu tomo numpy.argwhere (im) para ter todas as coordenadas forma de ponto. No entanto, a maioria desses pontos não estão contribuindo para o casco convexo (jazem no interior da forma). Porque convexo tempo casco computação é, pelo menos, proporcional ao número de pontos que ele recebe como entrada, eu criei uma idéia para filtrar a multiplicidade de pontos inúteis sobre antemão e só passar aquelas que abrangem o contorno. A ideia é bastante simples, que para cada linha na NxM binário matriz eu tomo apenas os índices mínimos e máximos. Assim, por exemplo:

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)

Então esboço deve ler (em tuplas ou como uma matriz 5x2 numpy, eu não me importo):

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

Qualquer casco apertado convexo em torno desta forma (im), deve um subconjunto desses pontos (esboço). Em outras palavras, se "somefunc ()" é eficiente na filtragem dos pontos dentro, em seguida, ele economiza tempo para o cálculo casco convexo.

Eu tenho o código que faz o truque acima, mas eu estou esperando que alguém tem uma abordagem mais inteligente (leia mais rápido) desde que eu preciso para executá-lo muitas vezes. O código que eu tenho é:

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

Outra idéia que eu tinha era de usar Python de reduzir () assim que eu preciso para executar sobre a lista de coords apenas uma vez. Mas eu tenho dificuldade em encontrar um bom reduzindo função.

Qualquer ajuda seria muito apreciada!

Editar

No entretanto, eu encontrei uma maneira mais rápida de ir de im diretamente para outline. Pelo menos com imagens grandes este é significativamente mais rápido. Na aparente ausência de uma solução externa estou postulando-la como a solução para esta questão.

Ainda assim, se alguém conhece um método mais rápido, por favor, fale-se:)

Answer 1

Na ausência de uma resposta aceitável eu postar meu melhor código de trabalho como a solução.

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

Esta tarefa parece realizar a mesma coisa que suas duas últimas etapas:

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

Não sei se é mais rápido, no entanto.

Answer 3

Para a solução mais geral, você poderia usar somekind do método de detecção de borda de apenas encontrar os pontos de borda. Eu acredito (Google ..) que NumPy foi construído com filtro de Sobel, que vai fazer isso.