光栅路径跟踪算法
我有一个值的栅格网格，如下图所示（白色是高值，黑色背景值为零）。
我正在尝试编写某种路径跟踪代码，以从其中一行的末尾开始并跟踪到另一端，通过尽可能高的值（即，选择在线中的像素越白越好），但仍然到达另一端。
我已经为此苦苦挣扎了一段时间，似乎无法得到任何我想要做的事情。所以我想知道，是否已经为此类问题开发了通用算法？我已经做了很多搜索，但大多数路径算法似乎都是设计用于矢量/网络，而不是像这样的栅格网格。
有什么想法吗？
I've got a raster grid of values that looks something like the image below (white is high values, the black background value is zero).
I'm trying to write some kind of path-following code to start at the end of one of the lines and trace to the other end, going via the highest possible values (that is, the whiter the pixels chosen to be in the line the better) but still getting to the other end.
I've been struggling with this for a while, and can't seem to get anything I try to work. So I wondered, has a generic algorithm already been developed for this sort of problem? I've done a lot of searching, but most path algorithms seem to be designed to work on vectors/networks, not raster grids like this.
Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
最简单的想法可能是使用 A* 算法，其中每个像素都是一个节点，节点的成本是像素暗度。
更新：找到了一个不错的 教程。
The simplest idea probably is to use the A* algorithm, where each pixel is a node, and the cost of the node is the pixel darkness.
Update: Found a nice tutorial.
一种方法是：
需要进行一些调整才能使其正常工作，但这样做是可能的。另一种变体是勾勒白色部分（如果它们比 1、2 或 3 个像素宽），然后合并双线。
One way to do this:
It will take some tweaking to get it to work well, but it is possible to do it this way. One other variant is to outline the white sections, if they are wider than 1 or 2 or 3 pixels, and combine the double lines afterward.
我认为你不需要遗传算法或任何荒谬的东西；好的老式递归和动态编程就足够了。我最初认为，您应该能够通过广度优先搜索来实现您的目标。从起点开始，您访问分数大于路径值的所有邻居——所有单元格都从无穷大开始，黑色单元格的成本将是无穷大，这些是您可以修剪掉的路径）。到达目的地后，如果可以到达，您应该能够原路返回以找到路径。它很贪婪，但如果你的路径像这些一样表现良好，那就应该没问题。
对于灰度较多且曲折的路径，将光栅图像转换为图形可能是一个好主意，边缘权重是邻居的灰度值（或灰度值的差异，具体取决于这是什么）数据实际上意味着）。因此，您应该能够根据该解释使用任何最短路径算法。
I don't think you'll need a genetic algorithm or anything ridiculous; good old fashion recursion and dynamic programming should suffice. I am initially thinking, that you should be able to accomplish your goal by doing a breadth first search. From your starting point, you visit all the neighbors with scores greater then that paths value --all cells start out at infinity, and costs to black cells would be infinity, and these are the paths you can prune off). Once at your destination, if reachable, you should be able to backtrack to find the path. It's greedy, but if your paths are well behaved like these are, it should be fine.
For paths with more gray and twists and turns, it might be a good idea to convert the raster image to a graph, with the edge weight being the the gray scale values of the neighbors (or difference in gray scale values, depending on what this data actually means). So, you should be able to use any algorithm for shortest paths based on that interpretation.
如果您大规模这样做或进行研究，您可以尝试 http://en.wikipedia.org/ wiki/Ant_colony_optimization，但如果你这样做是为了钱，只需选择类似洪水填充的东西 http: //en.wikipedia.org/wiki/Flood_fill
If you are doing this on big scale or for research you might try whit http://en.wikipedia.org/wiki/Ant_colony_optimization, but if you are doing this for money just pick up something like flood fill http://en.wikipedia.org/wiki/Flood_fill