栅格路径跟踪算法

Question

我有一个栅格值网格，看起来像下面的图像(白色是高值，黑色背景值是零)。

​

​

我正在尝试编写某种路径跟踪代码，从一条线的末尾开始，跟踪到另一条线，遍历可能的最高值(即选择在这条线中的像素越白越好)，但仍会到达另一端。

我已经在这个问题上挣扎了一段时间，似乎不能得到任何我试图工作的东西。所以我想知道，是否已经为这类问题开发了一种通用算法？我做了很多搜索，但大多数路径算法似乎都是为矢量/网络而设计的，而不是像这样的栅格。

有什么想法吗？

Answer 1

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

更新:找到了一个不错的tutorial。

Answer 2

一种方法是：

1. 对图像进行过滤，使其更接近黑白像素。
2. 绘制一条穿过白色像素的线。要做到这一点，从一个白色像素开始。从那个像素到另一个白色像素画一条线，距离2(或3左右)，但忽略前一条线附近的像素。坚持下去，直到你覆盖了每一条线上不接近的像素(2或3个像素)。您必须在此处进行一些细微的调整才能使其正常工作。
3. 连接您绘制的线条的端点。如果附近有两个端点(1个或2个像素？)一个接一个，连接起来。您应该最终得到由许多短片段组成的几行代码，可能会有一些循环和分支。
4. 去掉了行中的任何小循环，并在分叉处分离了行，因此您有几行由许多短segments.
5. Reduce点组成的行。对于每一条线，检查它是否接近笔直。如果是，请删除所有内部点。如果不是，请递归地检查直线的两个部分，直到达到最小线段长度。
6. 您可以选择通过此point.
7. Profit.

处的直线拟合样条曲线

需要一些调整才能让它很好地工作，但这样做是可能的。另一种变化是，如果白色部分的宽度超过1或2或3个像素，则勾勒出它们的轮廓，然后组合双线。

Answer 3

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

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