区域生长算法

Question

嘿大家.我真的很难弄清楚这一个的逻辑,并希望你可以帮助我.在我继续之前,我只是想让你知道我是业余程序员和初学者,没有正式的计算机科学培训,所以请耐心等待.:D另外,我正在使用Python,但我可以使用Java或类似的东西.

Anywho,我希望实现一个Region Growing用于一个基本的Drawbot.这是一篇关于地区发展的文章:http://en.wikipedia.org/wiki/Region_growing

我设想的方式,抽奖所依据的形象将符合以下标准:

• 在任意颜色深度下,图像的尺寸最多为3x3英寸

• 图像将是白色背景上的黑色连续形状

• 形状可以位于背景上的任何位置.

我已经考虑过这个问题的以下解决方案.虽然有些工作在一定程度上,但每个都在性能或可行性方面存在一些相当大的缺陷(至少对我来说似乎不可行).此外,因为这是一个Drawbot,这需要用一条连续的线来完成.然而,这并不意味着我不能回溯,它只消除了多个起点(种子)的可能性.

考虑的方法:

随机漫步:

随机散步解决这个问题是我的第一直觉.我想,实现这一目标的随机游走程序看起来像这样:

伪蟒蛇......

Cells To Visit = Number of Black Cells
Cells Visited = 0
MarkColor = red
While Cells Visited < Cells To Visit:
    if currentcell is black:
        Mark Current Cell As Visited #change pixel to red
        Cells Visited +=1
    neighbors = Get_Adjacent_Cells() #returns cells either black or red
    next cell = random.choose(neighbors)
    currentCell = next cell

虽然我认为这是可行的,但在我看来它是非常无效并且不能保证良好的结果,但为了实际完成某些事情,我可能最终会尝试这个...我的伪代码中的逻辑是否甚至模糊地正确？

清扫模式:

对我来说,这种方法似乎是最难实现的.我的想法是我可以在形状的一个极端选择一个起点(例如最左边的最低点).从那里它将向右绘制,仅在x轴上移动,直到它击中白色像素.从这里开始,它将在y轴上向上移动一个像素,然后在x轴上向左移动,直到达到白色像素.如果它正上方的像素发生白色,则在x轴上回溯,直到它在其上方找到黑色像素.

进一步检查后的这种方法有一些重大缺陷.当遇到这样的形状时:

结果将如下所示:

即使我要告诉它在一段时间后开始扫地,中间腿仍然会被忽视.

4/8连接的邻居:

http://en.wikipedia.org/wiki/8-connected_neighborhood

这种方法在我看来是最强大和最有效的,但是在这一点上我无法完全理解它,我也不能想到如何实现它而不会留下一些被忽视的区域

在每个单元格中,我会查看相邻的黑色单元格,设计一些方法来排列我应该首先访问哪一个,访问所有这些,并重复该过程直到所有单元格都被覆盖.

我在这里看到的问题首先是处理完成此任务所必需的数据结构,并且还只是弄清楚它背后的逻辑.

---

这些是我能够想到的最佳解决方案.感谢您花时间阅读本文,我意识到它很长,但我认为我应该尽可能明确.任何和所有建议将不胜感激...谢谢!

编辑:

我也研究了迷宫生成和求解算法,但不知道如何在这里实现.我对迷宫求解算法的理解是它们依赖于迷宫的通道具有相等的宽度.我当然可能错了.

Answer 1

基本区域增长,伪代码看起来像:

seed_point // starting point
visited // boolean array/matrix, same size as image
point_queue // empty queue

point_queue.enqueue( seed_point )
visited( seed_point ) = true

while( point_queue is not empty ) {
    this_point = point_queue.dequeue()
    for each neighbour of this_point {
        if not visited( neighbour ) and neighbour is black/red/whatever
            point_queue.enqueue( neighbour )
            visited( neighbour ) = true
    }
}

// we are done. the "visited" matrix tells
// us which pixels are in the region

我不明白你提到的排名在哪里.我错过了什么吗？

Answer 2

这是一个关于编写递归迷宫求解器的非常好的小截屏视频：http://thinkcode.tv/catalog/amazing-python/

我认为它可能会给你一些关于你试图解决的问题的想法。

另外，这是我在观看截屏视频http://pastie.org/1854582后编写的一个递归迷宫解决小脚本。等宽的通道不是必需的，唯一需要的是开放空间、墙壁和某种结束条件，在这种情况下，找到迷宫的尽头。

如果您不想递归，您可以做的另一件事是使用“回溯”方法。您可以在此页面上看到它在迷宫的随机生成中使用的一个小示例： http://weblog.jamisbuck.org/2011/2/7/maze- Generation-algorithm-recap（页面上的第一个示例） 。

这听起来相关吗？如果是，请告诉我您是否希望我更详细地解释任何内容。

编辑：

这似乎是关于在 python 中进行洪水填充的非常好的讨论http://www.daniweb.com/software-development/python/threads/148874