Matrix of points to suitable Path

I have a 128 by 128 matrix of 0s and 1s, like so

From this I need to generate a single path that starts somewhere at the bottom of the matrix to the highest point of the matrix. So for example the output would be:

I have implementing like a A* path cost flood fill and try to get lowest cost with no luck. Would there be any other methods of doing this? Any recommendations or help would be greatly appreciated !

(The point of this is I need to get a robot to follow the path after converting the pixel coordinates to world coordinates)

[Jan]

Please explain "no luck" with and details. Perhaps you had a simply typo in your code?

[trent cooper]

So far I have a function like this...

    function output = path_cost(input)
    % if a point (x,y) = 1 then x+1, x-1, y+1, y-1 etc will equal 2 
    % unless its already a value
    output = input;
    V_size = size(output);
    for x=1:V_size(1)
        for y=1:V_size(2)
            if output(x,y)==1
                if output(x-1,y-1)==0
                    output(x-1,y-1)=2;
                elseif output(x,y-1)==0
                    output(x,y-1)=2;
                elseif output(x+1,y-1)==0
                    output(x+1,y-1)=2;
                elseif output(x-1,y)==0
                    output(x-1,y)=2;
                elseif output(x+1,y)==0
                    output(x+1,y)=2;
                elseif output(x-1,y+1)==0
                    output(x-1,y+1)=2;
                elseif output(x,y+1)==0
                    output(x,y+1)=2;
                elseif output(x+1,y+1)==0
                    output(x+1,y+1)=2;
                end
            end
        end
    end

end

This method seems tedious and was hoping there would be a better way of doing this. (Note the function currently doesn't take into account the matrix boundaries and would also need to be repeated over a number of times to get a cost in each cell, was thinking recursion?)

Answer 1

[Image Analyst]

A* should work. Doesn't look like your code used it though. There are other ways. Like dynamic programming, or the function shortestpath(), etc. Is there a continous path in your dots and just got lost due to subsampling for display? If so, you can use bwdistgeodesic().

[trent cooper]

So I have a camera on my robot which is getting the optical flow when a person walks in front of it and then places a 1 at the position of that person in the frame over 15secs. So I end up with a matrix with a bunch of 1s simulating a path. What I'd like is a continuous path that follows the '1s'.

I was trying to create like a cost matrix. Like shown below. And keep looping through until all the cells had a cost. And then somehow get the path with shortest cost.

I'm trying to teach myself as I go. I had a look as to how I would implement the functions you provided but still unsure. Could you provide a small example would be awesome Thank you

[Image Analyst]

I don't think A* is the way to go, given the additional information. You want standard tracking. The Computer Vision system Toolbox has lots of demos on tracking things like vehicles and people: http://www.mathworks.com/products/computer-vision/code-examples.html That is what you'd want to do instead.

Answer 2

[Walter Roberson]

bwmorph and 'thicken' just enough to join segments together. Then skeletonize.

Or perhaps you could use alpha shapes to enclose the branches, then fill, then skeletonize