contorno de pitón para matriz binaria 2D

Question

Quiero calcular un casco convexo alrededor de una forma en una matriz NxM binaria. El algoritmo de casco convexo espera una lista de coordenadas, por lo que tomo numpy.argwhere (im) para tener todas las coordenadas del punto de forma. Sin embargo, la mayoría de esos puntos no contribuyen al casco convexo (se encuentran en el interior de la forma). Debido a que el tiempo de cálculo del casco convexo es al menos proporcional al número de puntos que obtiene como entrada, ideé una idea para filtrar la gran cantidad de puntos inútiles de antemano y solo pasar los que abarcan el contorno. La idea es bastante simple, que para cada fila en la matriz NxM binaria tomo solo los índices mínimo y máximo. Así por ejemplo:

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)

Entonces el esquema debería leer (en tuplas o como una matriz numpy 5x2, no me importa):

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

Cualquier casco convexo ajustado alrededor de esta forma (im), debe ser un subconjunto de estos puntos (contorno). En otras palabras, si " somefunc () " es eficiente en el filtrado de los puntos internos y, a continuación, ahorra tiempo para el cálculo del casco convexo.

Tengo un código que hace el truco anterior, pero espero que alguien tenga un enfoque más inteligente (leer más rápido) ya que necesito ejecutarlo muchas veces. El código que tengo es:

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

Otra idea que tuve fue usar el reductor de Python (), por lo que necesitaría revisar la lista de coordenadas solo una vez. Pero tengo dificultades para encontrar una buena función reductora.

¡Cualquier ayuda sería apreciada grandemente!

edit

Mientras tanto, he encontrado una forma más rápida de pasar de im directamente a outline . Al menos con imágenes grandes, esto es significativamente más rápido. Ante la aparente ausencia de una solución externa, la poseo como la solución a esta pregunta.

Aún así, si alguien conoce un método aún más rápido, por favor, hable :)

Answer 1

En ausencia de una respuesta aceptable, publico mi mejor código de trabajo como la solución.

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 tarea parece lograr lo mismo que los dos últimos pasos:

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

Sin embargo, no sé si es más rápido.

Answer 3

Para una solución más general, podría usar algún tipo de método de detección de bordes para encontrar solo los puntos de borde. Creo (Google ...) que NumPy tiene un filtro de sobel incorporado, que hará eso.