8

我有一个类似于下图的栅格值(白色是高值,黑色背景值为零)。

栅格网格示例

我正在尝试编写某种路径跟踪代码,从其中一行的末尾开始并跟踪到另一端,通过可能的最高值(即,选择在行中的像素越白更好)但仍然到达另一端。

我已经为此苦苦挣扎了一段时间,似乎无法得到任何我尝试工作的东西。所以我想知道,是否已经针对此类问题开发了通用算法?我做了很多搜索,但大多数路径算法似乎都设计用于矢量/网络,而不是像这样的栅格网格。

有任何想法吗?

4

4 回答 4

8

最简单的想法可能是使用A* 算法,其中每个像素是一个节点,节点的成本是像素暗度。

更新:找到了一个不错的教程

于 2010-12-03T21:24:03.417 回答
2

一种方法:

  1. 过滤图像以使其更接近仅黑白像素。
  2. 通过白色像素画一条线。为此,请从一个白色像素开始。从该像素到其他白色像素之间画一条线,距离为 2(或 3 左右),但忽略前一条线附近的像素。继续前进,直到您覆盖了与一条线不相近的每个像素(2 或 3 个像素)。您必须在此处进行一些小的调整才能使其正常工作。
  3. 连接您绘制的线条的端点。如果有两个端点彼此靠近(1 或 2 像素?),将它们连接起来。您最终应该得到由许多短段组成的几行,可能带有一些循环和分叉。
  4. 去掉线路中的任何小循环,并在分叉处分开线路,这样你就有了由许多短段组成的几条线路。
  5. 减少积分。对于每条线,检查它是否几乎是直的。如果是这样,请删除所有内部点。如果不是,请递归检查线的两半,直到达到最小段长度。
  6. 您可以选择在此点通过线条拟合样条曲线。
  7. 利润。

需要进行一些调整才能使其正常工作,但可以这样做。另一种变体是勾勒白色部分,如果它们比 1 或 2 或 3 个像素宽,然后合并双线。

于 2010-12-03T21:24:26.820 回答
1

我认为您不需要遗传算法或任何可笑的东西;好的老式递归和动态编程就足够了。我最初的想法是,您应该能够通过进行广度优先搜索来实现您的目标。从您的起点开始,您访问所有得分高于路径值的邻居——所有单元格从无穷大开始,黑色单元格的成本将是无穷大,这些是您可以修剪的路径)。一旦到达目的地,如果可以到达,您应该能够回溯以找到路径。这是贪婪的,但如果你的路径表现得像这样,那应该没问题。

对于具有更多灰色和曲折的路径,将光栅图像转换为图形可能是个好主意,边缘权重是邻居的灰度值(或灰度值的差异,取决于这个数据实际上意味着)。因此,您应该能够使用任何基于该解释的最短路径算法。

于 2010-12-03T21:09:26.180 回答
1

如果您正在大规模这样做或进行研究,您可能会尝试使用http://en.wikipedia.org/wiki/Ant_colony_optimization,但如果您这样做是为了赚钱,只需选择类似洪水填充http://en 的东西。 wikipedia.org/wiki/Flood_fill

于 2010-12-03T21:24:54.043 回答