区域生长算法

Question

大家好。我在这个问题上真的很挣扎，希望你们能帮我一下。在我继续之前，我想告诉你们，我是个业余程序员，刚刚入门，没有任何正式的计算机科学培训，所以请多多包涵。:D 另外，我使用的是Python，不过我也可以用Java或类似的语言。

总之，我想实现一个区域生长算法，用于一个简单的绘图机器人。这里有一篇关于区域生长的文章：http://en.wikipedia.org/wiki/Region_growing

我设想的绘图基于的图像将满足以下条件：

• 图像的大小最多为3x3英寸，颜色深度可以随意。

• 图像是一个黑色的连续形状，背景是白色的。

• 这个形状可以位于背景的任何地方。

我考虑了以下几种解决方案。虽然有些方法在某种程度上有效，但每种方法在性能或可行性上都有一些明显的缺陷（至少在我看来是这样）。而且，因为这是一个绘图机器人，所以需要用一条连续的线来完成。这并不意味着我不能回溯，只是排除了多个起点（种子）的可能性。

考虑过的方法：

随机游走：

用随机游走来解决这个问题是我的第一反应。我想象中的随机游走程序大概是这样的：

伪代码...

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

我对这个很长的问题感到困惑。

你确定你不是在尝试做一个叫做填充算法的东西吗？

Answer 2

基本的区域生长算法，伪代码大概是这样的：

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 3

这里有一个很不错的小视频，讲的是如何写一个递归的迷宫求解器：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