Python Kontur für binäre 2D-Matrix

Question

Ich mag eine konvexe Hülle um eine Form in einer binären NxM-Matrix zu berechnen. Die konvexe Hülle Algorithmus erwartet eine Liste von Koordinaten, so nehme ich numpy.argwhere (im) alle Koordinaten Formpunkt zu haben. die meisten dieser Punkte sind jedoch nicht beiträgt zu der konvexen Hülle (sie liegen auf der Innenseite der Form). Da konvexe Hülle Berechnungszeit mindestens proportional zu der Anzahl der Punkte ist, dass es als Eingabe erhält, entwickelte ich eine Idee, um die Fülle von nutzlosen Punkte auf vorher zu filtern und nur diejenigen, übergeben, die den Umriss erstrecken. Die Idee ist ganz einfach, dass für jede Zeile in der binären Matrix NxM ich nur den minimalen und maximalen Indizes nehmen. So zum Beispiel:

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)

Dann Umriss sollte (in Tupeln oder als 5x2 numpy Array, ich habe nichts dagegen) lesen:

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

Jede konvexe Hülle eng um diese Form (im), muss eine Teilmenge dieser Punkte (Entwurf). Mit anderen Worten, wenn „someFunc ()“ ist effizient in Filterung der Innenseite Punkte dann spart es Zeit für die konvexe Hülle Berechnung.

Ich habe Code, der die oben genannten Trick funktioniert, aber ich bin der Hoffnung, jemand schlauer hat (lesen Sie schneller) Ansatz, da ich es viele, viele Male ausgeführt werden müssen. Der Code, den ich habe, ist:

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

Eine andere Idee, die ich hatte, war Python zu verwenden, die reduzieren (), so würde ich brauche über die Liste der coords laufen nur einmal. Aber ich habe Schwierigkeiten, eine gute Verringerung der Funktion zu finden.

Jede Hilfe wäre sehr geschätzt werden!

Bearbeiten

In der Zwischenzeit habe ich einen schnelleren Weg gefunden von im zu direkt outline. Zumindest mit großen Bildern ist dies deutlich schneller. In der scheinbaren Abwesenheit einer externen Lösung als die Lösung dieser Frage bin ich setzend.

Dennoch, wenn jemand eine noch schnellere Methode kennt, bitte sprechen:)

Answer 1

In Ermangelung einer akzeptablen Antwort, die ich meinen besten Arbeits Code als die Lösung veröffentlichen.

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

Diese Zuordnung scheint das gleiche wie Ihre letzten beiden Schritte zu erreichen:

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

Sie wissen nicht, ob es nicht schneller, aber.

Answer 3

Für weitere allgemeine Lösung, könnten Sie somekind von Kantenerkennungsverfahren verwenden nur die Randpunkte zu finden. Ich glaube (Google ..), dass NumPy verfügt über eine integrierte in Sobel-Filter, die das tun wird.