livewire with the Dijkstra’s algorithm apply to 2D image

Hello guys.

I am doing my assingment that using livewire with the Dijkstra's algorithm to find shortest path to 2D image

I tried to solve but i can't understand somepoint

The things i can't understand i marked on bold and italics

Can you help me please?

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

I = imread('pout.tif');

I2d = im2double(I);

%%

% a: gradient approximation

% approximate the gradient magnitude G by Sobel filter

Sobel_width = fspecial('sobel');

Sobel_vertical = Sobel_width';

% apply Sobel filter to image

Gx = imfilter(I2d,Sobel_width);

Gy = imfilter(I2d,Sobel_vertical);

% Calculate gradient magnitude

G_magnitude = sqrt(Gx.*Gx + Gy.*Gy);

%%

% b: livewire

% take two pixel locations as inputs, one as the start point and one as the end point

p = [50,80]; % Point P

q = [200,240]; % Point Q

% calculate the local edge weight between neighbor pixels (p; q)

[MaxG,MinG,Dist,local_weight] = localedgewidth(G_magnitude,p,q);

% search the path on the 8-connected neighborhood per pixel

G = imageTograph(I,8);

Node1 = p(1)*q(1);

Node2 = p(2)*q(2);

% find the path between the selected two pixel locations with the minimum sum of

edge weights using the Dijkstra’s algorithm

[path, path_cost] = Dijkstra(G,Node1,Node2);

[y_path, x_path] = ind2sub([q(1) q(2)], path);

%%

% c: display

figure(1)

subplot(2,2,1)

imshow(I);

subplot(2,2,2)

imshow(G_magnitude)

subplot(2,2,3)

imshow(G_magnitude)

hold on

plot(p(1),p(2),'r*','LineWidth',1,'MarkerSize',12)

plot(q(1),q(2),'r*','LineWidth',1,'MarkerSize',12)

hold off

subplot(2,2,4)

% image showing the result path

imshow(G_magnitude(x_path,y_path))

figure(2)

display 4 subplots in the second figure, including the image showing the result

path, the distance map corresponding to the start point, the binary image with the

visited pixels as 1, and the image showing the index map of previous visited pixels

function [MaxG,MinG,Dist,local_weight] = localedgewidth(G_magnitude,p,q)

MaxG=max(G_magnitude(:));

MinG=min(G_magnitude(:));

Dist=sqrt(sum((p-q).^2));

local_weight=(MaxG-G_magnitude(q(1),q(2)))/(MaxG-MinG)*(Dist/sqrt(2));

end

function [path,path_cost] = Dijkstra(image,start,target)

% start with a image of distances among N node

N = size(image,1);

% Note all nodes as unvisited

visited(1:N) = 0;

% initialize the distance to all points as infinity

distances(1:N) = Inf;

% Previous node, informs about the best previous node known to reach each network node

prev(1:N) = N+1;

% initialize the distsnce to the first point as zero

distances(start) = 0;

while sum(visited)~=N

candidates = inf(1,N);

candidates(~visited) = distances(~visited);

[candidate_cost,u]= min(candidates);

if ( isinf(candidate_cost) )

error('There are inaccessible vertices from source or zero weighted edges');

end

visited(u) = 1;

cols = find(image(u,:));

cost_i = full(image(u,cols));

new_travel_cost = distances(u) + cost_i;

prev_travel_cost = distances(cols);

betterway = new_travel_cost < prev_travel_cost;

distances(cols(betterway)) = new_travel_cost(betterway);

prev(cols(betterway)) = u;

end

path = target;

while path(1) ~= start

if prev(path(1)) <= N

path=[prev(path(1)) path];

else

error;

end

end

% final cost

path_cost = distances(target);

end

function graph = imageTograph(im, varargin)

if ( nargin == 2 )

conn = varargin{1};

elseif ( nargin == 1 )

conn = 4;

end

if ( conn ~= 4 && conn ~= 8 )

error('2nd argument is the type of neighborhood connection. Must be either 4 or 8');

end

% Image Size

[M, N] = size(im);

MxN = M*N;

% Calculate distance matrix

CostVec = reshape(im, MxN, 1);%stack columns

%Create sparse matrix to represent the graph

if ( conn == 4 )

graph = spdiags(repmat(CostVec,1,4), [-M -1 1 M], MxN, MxN);

elseif( conn == 8 )

graph = spdiags(repmat(CostVec,1,8), [-M-1, -M, -M+1, -1, 1, M-1, M, M+1], MxN, MxN);

%set to inf to disconect top from bottom rows

graph(sub2ind([MxN, MxN], (2:N-1)*M+1,(2:N-1)*M - M)) = inf;%top->bottom westwards(-M-1)

graph(sub2ind([MxN, MxN], (1:N)*M, (1:N)*M - M + 1)) = inf;%bottom->top westwards(-M+1)

graph(sub2ind([MxN, MxN], (0:N-1)*M+1,(0:N-1)*M + M)) = inf;%top->bottom eastwards(M-1)

graph(sub2ind([MxN, MxN], (1:N-2)*M, (1:N-2)*M + M + 1)) = inf;%bottom->top eastwards(M+1)

end

%set to inf to disconect top from bottom rows

graph(sub2ind([MxN, MxN], (1:N-1)*M+1, (1:N-1)*M)) = inf;%top->bottom

graph(sub2ind([MxN, MxN], (1:N-1)*M, (1:N-1)*M + 1)) = inf;%bottom->top

end

[KSSV]

Did you run the code? Is code working? It shows error.

Error using myfile>Dijkstra (line 70)
There are inaccessible vertices from source or zero weighted edges

Error in myfile (line 26)
[path, path_cost] = Dijkstra(G,Node1,Node2);
 

[Walter Roberson]

Node1 = p(1)*q(1);
Node2 = p(2)*q(2);

I would be surprised if those two lines are correct. I think you should instead be doing something like

Node1 = sub2ind(size(image), p);
Node2 = sub2ind(size(image), q);

[YUN JOONG KIM]

yes it run well in my version , i am 2021

[Walter Roberson]

The code runs for me in R2021b, provided that I comment out the explanatory text lines.

However, I am morally certain that the lines

Node1 = p(1)*q(1);
Node2 = p(2)*q(2);

are wrong. How could that calculation tell the difference between starting at (2,5), (3, 10) compared to (1,1), (6, 50) ?

Answer 1

[Iulen Cabeza Gil]

What's the use of 'localedgewidth'?

I do not think the code is well