Finding least-energy path across an image

Question

Consider a bidimensional array containing grayscale values, represented as the image below:

I want to find best path between the red dots. If you consider bright areas to be "high" and dark areas to be "low" in an elevation sense, then I want a line running along the dark "valley" running from one marker to another.

Two categories of algorithms that I know about are:

1. Image-processing-based, "bottom up" operations (skeletonization, watershed, ultimate erosion, etc.)
2. Iterative minimization, "top down" operations (active contours).

My question is:

Is there any typical and well-defined operation or algorithm to solve this problem, or should I create one myself from some of the generic techniques mentioned above?

I would try skeletonization first, but I don't know how to perform it upon a grayscale image. And, if I were to try an active contour, I wonder what would be good internal and external energy functions for images similar to the one shown (I suspect image gradient could act as a vector field).

Original data (CSV) here.

EDIT: this is my working code after implementing seam carving algorithm (as described in Wikipedia) and Shoham suggestions to force the path through the markers:

private double[] MinimumEnergyBetweenMarkers(double[,] array, Point upper, Point lower)
{
    int rows = array.GetLength(0);
    int cols = array.GetLength(1);

    // Points might come in another format, whatever
    int iupper = upper.Y;
    int jupper = upper.X;

    int ilower = lower.Y;
    int jlower = lower.X;            


    // First, scan down from upper marker,
    // storing temp results in a second array
     double[,] new_array = new double[rows, cols];
    FillArrayWithNans(ref new_array, double.NaN);
    new_array[iupper, jupper] = array[iupper, jupper];
    int i = iupper;

    while (i++ < ilower + 1)
    {
        for (int j = 1; j < cols - 1; j++)
        {
            var valid_neighbors = new List<double>()
            {
                new_array[i-1, j-1],
                new_array[i-1, j],
                new_array[i-1, j+1]
            }.Where(v => !Double.IsNaN(v));
            if (valid_neighbors.Count() > 0)
                new_array[i,j] = array[i,j] + valid_neighbors.Min();
        }
    }

    double[] shortest_path = new double[rows];
    FillArrayWithNans(ref shortest_path, double.Nan)

    shortest_path[ilower] = jlower;
    i = ilower;
    int jj = jlower;

    // offsets might be wider to allow for "steeper" paths
    var offsets = new int[]{-1,0,1};

    while (i-- > iupper)
    {
        double minimum = double.MaxValue;
        int jtemp = jj;
        foreach (int offset in offsets)
        {
            if (jj > 0 && jj < cols - 1)
            {
                double candidate = array[i-1, jj+offset];
                if (candidate < minimum)
                {
                    minimum = candidate;
                    jtemp = jj+offset;
                }
            }
        }
        jj = jtemp;
        shortest_path[i] = jj;
    }

    return shortest_path;
}

Answer 1

Use dynamic programming. This method is used by Seam Carving on edges. You need to use it on the original data, but make sure that dark areas are given a low value and that you are calculating only the paths that are possible between the two red points.

Seam carving adjusted for your purpose:

1. Each pixel is given a number to represent the energy. In your case, darkness or brightness.

2. Start one row under the upper red dot.

3. Scan downwards. For each pixel sum his energy plus the minimum sum of energy from the three pixels above him (save this value). You also need to save who was his father (the pixel that had the minimum energy above the current pixel).

4. Another change that needs to be done to the algorithm is that you you must flag the pixels that originated in the upper first red dot (flag the upper dot also) and always give a priority to a flagged pixel.

If you follow all of this steps, the lower red dot pixel will contain the least energy route to the upper dot.

Remark: This can be performance improved.