Wie kann ich Zyklen in einem Skelett mit Python-Bibliotheken finden?

Question

Ich habe viele skelettierten Bilder wie diese:

Wie kann ich einen Zyklus, eine Schleife im Skelett erkennen? Gibt es "spezielle" Funktionen, die das tun oder sollte ich es als Graph implementieren?

Falls es nur die Grafikoption gibt, kann mir die Python Graph Bibliothek NetworkX helfen?

Answer 1

Sie können die Topologie des Skeletts ausnutzen. Ein Zyklus wird keine Löcher haben, also können wir scipy.ndimage verwenden, um Löcher zu finden und zu vergleichen. Dies ist nicht die schnellste Methode, aber es ist extrem einfach zu programmieren.

import scipy.misc, scipy.ndimage 

# Read the image 
img = scipy.misc.imread("Skel.png") 

# Retain only the skeleton 
img[img!=255] = 0 
img = img.astype(bool) 

# Fill the holes 
img2 = scipy.ndimage.binary_fill_holes(img) 

# Compare the two, an image without cycles will have no holes 
print "Cycles in image: ", ~(img == img2).all() 

# As a test break the cycles 
img3 = img.copy() 
img3[0:200, 0:200] = 0 
img4 = scipy.ndimage.binary_fill_holes(img3) 

# Compare the two, an image without cycles will have no holes 
print "Cycles in image: ", ~(img3 == img4).all() 

Ich habe Ihr "B" Bild als Beispiel verwendet. Die ersten beiden Bilder sind das Original und die gefüllte Version, die einen Zyklus erkennen. In der zweiten Version habe ich den Zyklus unterbrochen und nichts wird gefüllt, daher sind die beiden Bilder gleich.

Answer 2

Die Konvertierung Ihres Skelettbildes in eine Graphendarstellung ist nicht trivial, und ich kenne keine Werkzeuge, um das für Sie zu tun.

Eine Möglichkeit, dies in der Bitmap zu tun, wäre die Verwendung eines flood fill, wie der Farbeimer in Photoshop. Wenn Sie eine Flutfüllung des Bildes starten, wird der gesamte Hintergrund gefüllt, wenn keine Zyklen vorhanden sind. Wenn die Füllung nicht das gesamte Bild erhält, haben Sie einen Zyklus gefunden. Um alle Zyklen zuverlässig zu finden, könnte es mehrere Male erforderlich sein, sie zu füllen.

Dies ist wahrscheinlich sehr langsam auszuführen, aber wahrscheinlich viel schneller zu programmieren als eine Technik, bei der das Skelett in die Graphdatenstruktur eingezeichnet wird.

Answer 3

Lassen Sie uns zunächst ein Bild des Buchstaben B mit PIL bauen:

import Image, ImageDraw, ImageFont 
image = Image.new("RGBA", (600,150), (255,255,255)) 
draw = ImageDraw.Draw(image) 
fontsize = 150 
font = ImageFont.truetype("/usr/share/fonts/truetype/liberation/LiberationMono-Regular.ttf", fontsize) 
txt = 'B' 
draw.text((30, 5), txt, (0,0,0), font=font) 
img = image.resize((188,45), Image.ANTIALIAS) 
print type(img) 
plt.imshow(img) 

Sie einen besseren Weg, dies zu tun finden können, insbesondere mit Pfad zu den Schriftarten. Ii wäre besser, ein Bild zu laden, anstatt es zu erzeugen. Wie auch immer, wir haben jetzt etwas zu arbeiten:

nun den Realteil:

import mahotas as mh 
img = np.array(img) 
im = img[:,0:50,0] 
im = im < 128 
skel = mh.thin(im) 
noholes = mh.morph.close_holes(skel) 
plt.subplot(311) 
plt.imshow(im) 
plt.subplot(312) 
plt.imshow(skel) 
plt.subplot(313) 
cskel = np.logical_not(skel) 
choles = np.logical_not(noholes) 
holes = np.logical_and(cskel,noholes) 
lab, n = mh.label(holes) 
print 'B has %s holes'% str(n) 
plt.imshow(lab) 

Und wir haben in der Konsole (ipython): B hat zwei Löcher