How can i find cycles in a skeleton image with python libraries?

Question

I have many skeletonized images like this:

How can i detect a cycle, a loop in the skeleton? Are there "special" functions that do this or should I implement it as a graph?

In case there is only the graph option, can the python graph library NetworkX can help me?

Dainedainty

Implementing a simple graph is easy with python dictionaries. Here is an example from the python docs. NetworkX seems like overkill although I've never used it. Regarding converting the image to a graph, I don't know a simple way to do it although it seems like an interesting problem. I use opencv which provides a lot of functionality for manipulating images. You might find some useful parts in it. – Gintz

Answer 1

You can exploit the topology of the skeleton. A cycle will have no holes, so we can use scipy.ndimage to find any holes and compare. This isn't the fastest method, but it's extremely easy to code.

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()

I've used your "B" picture as an example. The first two images are the original and the filled version which detects a cycle. In the second version, I've broken the cycle and nothing gets filled, thus the two images are the same.

Ulyssesumayyad

Answer 2

First, let's build an image of the letter B with PIL:

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)

you may find a better way to do that, particularly with path to the fonts. Ii would be better to load an image instead of generating it. Anyway, we have now something to work on:

Now, the real part:

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)

And we have in the console (ipython): B has 2 holes

Iranian

Answer 3

Converting your skeleton image to a graph representation is not trivial, and I don't know of any tools to do that for you.

One way to do it in the bitmap would be to use a flood fill, like the paint bucket in photoshop. If you start a flood fill of the image, the entire background will get filled if there are no cycles. If the fill doesn't get the entire image then you've found a cycle. Robustly finding all the cycles could require filling multiple times.

This is likely to be very slow to execute, but probably much faster to code than a technique where you trace the skeleton into graph data structure.

Seriatim

I think it's a good solution. I count pixels' number of skeleton and the total number of pixels of the image and calculate difference, if floodfill returns me same number of pixels there are no cycles, if returns less there are cycles. – Dainedainty

Yes basically you need to label the complement of the skeletons. This will return the connected components cut out by the skeletons loops. If the number of components is greater than 1 say N you have N-1 loops. This can also be seen as a form for thinning the skeleton. – Barchan