如何使用python库在骨架映像中查找循环？

Question

我有很多像这样的骷髅图像：

我怎么能检测出一个循环，一个骨架中的循环？ 是否有“特殊”函数可以实现这一点，或者我应该将其作为一个图形来实现？在

如果只有graph选项，python图形库NetworkX能帮助我吗？在

Answer 1

首先，让我们用PIL构建字母B的图像：

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)

您可能会找到更好的方法来实现这一点，尤其是使用字体路径。我最好加载一个图像而不是生成它。总之，我们现在有事情要做：

现在，真正的部分是：

^{pr2}$

我们在控制台中有（ipython）： <2个洞

Answer 2

将骨架图像转换为图形表示并非易事，而且我不知道有什么工具可以为您实现这一点。在

在位图中执行此操作的一种方法是使用flood fill，如photoshop中的油漆桶。如果开始对图像进行整体填充，如果没有循环，整个背景将被填充。如果填充没有得到整个图像，那么你就找到了一个循环。可靠地找到所有的循环可能需要多次填充。在

这可能执行起来非常慢，但可能比在图形数据结构中跟踪骨架的技术快得多。在

Answer 3

可以利用骨架的拓扑结构。一个循环没有空穴，所以我们可以使用scipy.ndimage来找到任何空穴并进行比较。这不是最快的方法，但它非常容易编码。在

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

我以你的“B”图为例。前两个图像是原始图像和检测循环的填充版本。在第二个版本中，我打破了循环，没有东西被填充，因此这两个图像是相同的。在