我有一个类似于下图的栅格值（白色是高值，黑色背景值为零）。
我正在尝试编写某种路径跟踪代码，从其中一行的末尾开始并跟踪到另一端，通过可能的最高值（即，选择在行中的像素越白更好）但仍然到达另一端。
我已经为此苦苦挣扎了一段时间，似乎无法得到任何我尝试工作的东西。所以我想知道，是否已经针对此类问题开发了通用算法？我做了很多搜索，但大多数路径算法似乎都设计用于矢量/网络，而不是像这样的栅格网格。
有任何想法吗？
问问题
2185 次
4 回答
2
一种方法：
- 过滤图像以使其更接近仅黑白像素。
- 通过白色像素画一条线。为此，请从一个白色像素开始。从该像素到其他白色像素之间画一条线，距离为 2（或 3 左右），但忽略前一条线附近的像素。继续前进，直到您覆盖了与一条线不相近的每个像素（2 或 3 个像素）。您必须在此处进行一些小的调整才能使其正常工作。
- 连接您绘制的线条的端点。如果有两个端点彼此靠近（1 或 2 像素？），将它们连接起来。您最终应该得到由许多短段组成的几行，可能带有一些循环和分叉。
- 去掉线路中的任何小循环，并在分叉处分开线路，这样你就有了由许多短段组成的几条线路。
- 减少积分。对于每条线，检查它是否几乎是直的。如果是这样，请删除所有内部点。如果不是，请递归检查线的两半，直到达到最小段长度。
- 您可以选择在此点通过线条拟合样条曲线。
- 利润。
需要进行一些调整才能使其正常工作，但可以这样做。另一种变体是勾勒白色部分，如果它们比 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 回答