Matlab: Dijkstra methode - shortest way on gradient (small neighborhood)

The Dijkstra Methode

(German) In this post i show you with Matlab how to calculate the shortest path on a gradient images with d´the dijkstra methode i wrote. I take an image as an input and convert it to an double and calculate the gradient [G,Gdir] = imgradient(img,'sobel'); and I use my function Dijkstra(G,p,q):
THis function needs a image as double G, a start value p and the target q, where the first entry of the oints is the column and the second the row.
This methode sets all distances to infinity except the at the start value is zero obviously. All unvisited pixels have the value 1. The algortihm continous as long as the target is an unvisible pixel.
For all neighborhood pixels the weights are calculated with the function [weight] = localedgewidth(G,p,q) ,where the value of the neightbor pixel is substract by the maximum of the matrix and devided by the difference of maximal and minimal value of the matrix G and multiplied with the distance to the neighbor pixel. Is the weigth smaller than the distance it is overwritten and the previous visited pixel is safed. If the actual value is smaller than the previous one the algorithm goes to the next pixel repeating this algorithm.
To reconstruct the path the path is set to zero as long as it is equal to the start point.
Furthermore the distance, the path, the unvisited pixels and the previous visited pixels are output values of the function.
Here you see a short example how it works where you find the code below the code of the dijkstra methode.

Here one can download the following code on MathWorks:

Source Code Dijkstra:

function [path, prev, unvis, distance] = Dijkstra(Matrix, start, target)
%Matrix is the incoming image
%start is the start point in a vector [a,b] where a is the column and b the
%row
%target is the end point similare to start
%path is the matrix with ones excepted at the position of the path where it is 0
%prev are also the previous visited pixels where the algorithm took the
%wrong way
%unvis are all unvisited pixels
%distance is the distance or weight of the pixels

%calculate amount of nodes
    n = size(Matrix);

    unvis = ones(n); %set all unvisited to 1
    distance = ones(n).*inf; %set all distances to inf
    prev = zeros(n);%previous node

    u = start;
    distance(start) = 0;%start distance is 0

    while (unvis(target(1),target(2))==1)
        test = inf;
        for i=1:1:3%sum over the neighborhood pixels
            for j=1:1:3
                if(i~=2 | j ~=2)%exclude the pixel u in the middle
                    vx = u(1)-2+i;%generate the neighborhood pixels (3x3)
                    vy = u(2)-2+j;
                    v = [vx vy];
                    if (unvis(vx,vy)==1)%if actual neighbor is unvisited
                        cost = localedgewidth(Matrix,u,v);%calculate the weight
                        if (cost<distance(vx,vy))
                            distance(vx,vy)=cost;
                            prev(vx,vy)=u(1)*n(2)+u(2);%set previous node
                            if (cost<test)
                                next=[vx vy]; 
                                test=cost;
                            end
                        end
                    end
                end
            end
        end 
        unvis(u(1),u(2))=0;
        u=next;
    end
    path=ones(n);
    u = target;
    %backtrack from end to start to find best sequence
    while u ~= start
        previous=prev(u(1),u(2));
        k=floor(previous/n(2));
        l=previous-k*n(2);
        path(k,l)=0;%generate path
        u=[k,l];
    end

end

function [weight] = localedgewidth(G,p,q)
% aclculate the local edge width between neighborhood pixels
    maxG=max(G(:));
    minG=min(G(:));
    d=sqrt(sum((p-q).^2));
    weight=(maxG-G(q(1),q(2)))/(maxG-minG)*d/sqrt(2);
end

 

Source Code application:

 clear;
clc;

img = imread('pout.tif');
img = im2double(img);
%a)
[G,Gdir] = imgradient(img,'sobel');
n = size(G);
p = [120 165];
q = [274 205];

[path, prev, unvis, distance] = Dijkstra(G, p, q);
% use my function and plot everything
fig(1) = figure(1);
clf(1);
subplot(2,3,1);hold on;imshow(img);title('original');
subplot(2,3,2);hold on;imshow(G);title('gradient');
subplot(2,3,3);hold on;imshow(G);plot(165,120,'r.','markersize',12);
plot(205,274,'b.','markersize',12);title('Start, Target, Path');
for i=1:1:n(1)
    for j=1:1:n(2)
        if path(i,j) == 0
            plot(j,i,'g.','markersize',1);
        end
    end
end
subplot(2,3,4);hold on;imshow(distance);title('distance');
subplot(2,3,5);hold on;imshow(unvis);title('visited pixels');
subplot(2,3,6);hold on;imshow(mat2gray(prev));title('previous point')