python - 区域生长算法

Question

大家好。我真的很难弄清楚这个逻辑，希望你能帮助我。在我继续之前，我只想让你知道我是业余程序员和初学者，没有接受过任何形式的正式计算机科学培训，所以请多多包涵。 :D 另外，我使用的是 Python，但我可以使用 Java 或类似的东西。

任何人，我都希望实现一个区域增长以用于基本的 Drawbot。 这是一篇关于区域增长的文章:http://en.wikipedia.org/wiki/Region_growing

按照我的设想，绘制所依据的图像将满足以下条件:

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

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

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

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

考虑的方法:

随机游走:

用随机游走解决这个问题是我的第一直觉。完成此任务的随机游走程序，我想，看起来像这样:

伪 python ...

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

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

在每个单元格中，我都会查看相邻的黑色单元格，设计一些方法来对我应该首先访问的单元格进行排序，访问所有单元格，并重复该过程，直到所有单元格都被覆盖。

我在这里看到的问题首先是处理完成此任务所必需的数据结构，也只是弄清楚其背后的逻辑。

---

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

编辑:

我还研究了迷宫生成和求解算法，但不确定如何在此处实现。我对迷宫求解算法的理解是，它们依赖于迷宫 channel 的宽度相等。我当然可能是错的。

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

虽然我不明白你提到的排名是从哪里来的。我错过了什么吗？