shortest path approach for a binary image

[kumar1993]

Hello everyone,

Like the topic states, I have a binary image, that i have converted into 2D array of 0 and 1 values. From there, I have to calculate the shortest path from the left margin of the image to the right margin, following only black pixels.  I have given thought to A-star and Djisktra algorithms. But what I am stuck at is that I have to give different values to different path as shown in the picture. a black pixel to black , white to black, black to white values are horizontaly =2, diagonally =3 , white pixels to white pixels, horizontaly= 4, diagonally =6. The path must only move forward. 

 

What I cannot figure out is how to determine the weight distribution in 2D array that I have and what algorithm would be suitable for this job?

What I cannot figure out is

1)how to determine the weight distribution in 2D array that I have and what algorithm would be suitable for this job?

2) how to keep track of indices of the path elements?

more details that I have for finding the path,

 1) find shortes path from the index(n(i),m(i)) (row,column) to (n(j),m(last)). so we know our intial starting point and the ending point could be anywhere on the last column.

2)path must only move forward. 

Thank you for any advice or guidance. I truly appreciate.

[ijustlovemath]

Please attach the VI, so we can see the code.

[ogk.nz]

My initial suggestion would be to build a brute force method first, then try and work back to the improved pathing methods.

Considering that all of the movement costs are the same it works down to a simple selection based on the direction and whether either of the array locations are Black(In my attempt true in the boolean array). Pathing and history is quite easily done through an array of values.

Have you made any progress since your initial post?

[kumar1993]

After doing a lot of search and reading through literatures, I wasn't able to find any specific way to implement this method in labview. I wasn't able to build this kind of complicated mathematical computational system in labview, since I haven't tried anything like this previously not have I any idea how to attempt. if there is any relevent example or literature that i can refer too, I would be very grateful for such a referal. Till then, I am gonna keep searching through literatures until i can build up a better understanding.

I again thank you for your advices.

[ijustlovemath]

This sounds like a very straightforward application of Dijkstra's algorithm. Having the "only move forward constraint actually makes it a lot easier. Check out pseudocode implementations of Dijkstras for some idea of where you could add your modifications. 

[kumar1993]

I will take a look into it. Thank you for your advice.