寻求图像路径优化算法帮助

Question

嗨！ 我目前正在应对涉及图像路径优化的挑战，并且可以使用一些帮助来完善我的算法。将图像表示为一维整数数组，每个像素保存一个“能级”值。图像的左上角像素索引为 (0,0)。

我的目标是计算从图像顶部到底部的最短路径（以能量测量）。该路径可以从任何 x 坐标开始。我正在探索一种更具算法性的方法，而不是诉诸蛮力。我设想路径向下前进（增加 y 坐标），并且可以选择在每一步中向左、直行或右下移动。

这是我的算法的概要：

从左上角 (0,0) 开始。

通过考虑由“lookForward”表示的前瞻距离来确定下一个最佳步骤。

对于向左、直行或向右方向返回 -1、0 或 1。

通过迭代地向下移动图像来逐步找到最佳路径。

我已经实现了大部分算法，但目前我仍在完善“lookForward”组件。我正在寻求有关“PathFinder.getBestStep(x, y, LookForward);”的帮助方法。我知道使用方法进行递归对于完成每一步并找到最佳路径是必要的，但尽管我付出了努力，我仍无法使其发挥作用。

这是我当前代码的片段：

for (int x = 0; x < imageWidth; x++) {
    int xOffset = 0;
    for (int y = 0; y < imageHeight; y++) {
        final int bestStep = PathFinder.getBestStep(x + xOffset, y, 5); // "lookForward" distance is set to 5.

        if (bestStep == -1) {
            // Move one step left and one step down
            xOffset -= 1;
        }
        if (bestStep == 0) {
            // Move one step down
        }
        if (bestStep == 1) {
            // Move one step right and one step down
            xOffset += 1;
        }
    }
}

到目前为止我有点有这个 PathFinder 类：

public class PathFinder {

    public final int[] energyMap; // energyMap is the image.
    public final int width; // Width of image (energyMap).
    public final int height; // Height of image (energyMap).
    public final int lookForward; // Amount of steps, it will lookForward.

    public PathFinder(int[] energyMap, int width, int height, int lookForward) {
        this.energyMap = energyMap;
        this.width = width;
        this.height = height;
        this.lookForward = lookForward;
    }

    // Return the -1, 0 or 1, for left, middle or right, step movement.
    public int getBestStep(final int x, final int y) {
        final List<Integer> bestPath = getBestPath(x + y * width, new ArrayList<>());
        return bestPath.getFirst();
    }

    // Get the shortest path, (based on shortest energy level)
    public List<Integer> getBestPath(final int index, List<Integer> currentPath) {
        // Don't really know what to do here.
        return null;
    }
}

我想要的可视化： ” 让我们考虑一个 10x10 的图像，为简单起见，其中每个像素代表 1 或 0：

1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1

我们可以观察到图像中“能量”较低的清晰路径。我的目标是确定并遵循这条道路。然而，我要处理的图像即使不是更大，也可能达到 4000x4000。尝试暴力破解绝对最佳路径会消耗大量时间。因此，我的目标是实现一种仅向前计算几步的方法。

虽然处理单个 4000x4000 图像并不耗时，但我可能需要多次重复此过程，可能最多 1000 次。需要注意的是，绝对精度是不必要的；我主要感兴趣的是大致确定最佳路径。我可以调整“lookForward”变量来提高路径确定的质量。 ”

任何帮助或指导将不胜感激！

在上面的帖子！我已经描述了很多我尝试过的事情以及我正在做什么😊

Answer 1

这里有一些 C++ 代码，使用 https://github.com/JamesBremner/PathFinder 中的 Dijkstra 实现解决了这个问题

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include "GraphTheory.h"
#include "cGrid2D.h"

static std::vector<std::string>
tokenize(
    const std::string &line)
{
    std::vector<std::string> ret;
    std::stringstream sst(line);
    std::string a;
    while (getline(sst, a, ' '))
        ret.push_back(a);
    return ret;
}

void findpath(std::istream &ifs)
{
    // A directed graph
    raven::graph::sGraphData graphData;
    graphData.g.clear();
    graphData.g.directed();

    // A 2D grid
    cGrid2D grid;
    std::vector<double> vHeight;

    std::string line;
    int colcount = -1;
    int rowCount = 0;
    int startRow, startCol, endRow, endCol;

    // setup grid
    while (getline(ifs, line))
    {
        auto vt = tokenize(line);

        bool firstcol = true;
        for (auto &e : vt)
        {
            if (firstcol)
                firstcol = false;
            else
                vHeight.push_back(atof(e.c_str()));
        }
        if (colcount == -1)
            colcount = vt.size() - 1;
        else if (colcount != vt.size() - 1)
            throw std::runtime_error(
                "variable column count");
        rowCount++;
    }
    grid.setDim(colcount, rowCount);

    // Path can move only downwards
    grid.addDownEdges();

    // convert grid to graph with weighted edges
    graphData.edgeWeight.clear();
    for (auto &p : grid.getEdgesVertexIndex())
    {
        // add edges to graph with weight of the destination vertex
        graphData.g.add(p.first, p.second);
        graphData.edgeWeight.push_back(vHeight[p.second]);
    }
    // start from any vertex in top row
    int startIndex = graphData.g.vertexCount();
    for (int iv = 0; iv < colcount; iv++)
    {
        graphData.g.add(startIndex, iv);
        graphData.edgeWeight.push_back(vHeight[iv]);
    }
    // end from any vertex in bottom row
    int endIndex = graphData.g.vertexCount();
    for (int iv = endIndex - 1 - colcount; iv < endIndex - 1; iv++)
    {
        graphData.g.add(iv, endIndex);
        graphData.edgeWeight.push_back(0);
    }

    // Apply Dijsktra
    graphData.startName = graphData.g.userName(startIndex);
    graphData.endName = graphData.g.userName(endIndex);
    auto res = raven::graph::path(graphData);

    // Display path found ( col, row )
    int r, c;
    for (int i = 1; i < res.first.size() - 1; i++)
    {
        grid.coords(c, r, res.first[i]);
        std::cout << c << "," << r << " -> ";
    }
    std::cout << " total energy " << res.second << "\n";
}


main()
{
    std::string sin =
        "o 1 2 3\n"
        "o 2 3 1\n"
        "o 3 2 1\n";
    std::istringstream ifs(sin);
    findpath(ifs);

    return 0;
}

输出

1,0 -> 2,1 -> 2,2 ->  total energy 4

AFAIK，Java 只是 C++ 的一个特殊版本，因此您应该能够轻松移植此代码。