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

6 次查看（过去 30 天）
YUN JOONG KIM
YUN JOONG KIM 2021-12-22
回答： Iulen Cabeza Gil 2022-7-7
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
  4 个评论
显示 2更早的评论
Walter Roberson
Walter Roberson 2021-12-23
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) ?

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Iulen Cabeza Gil
Iulen Cabeza Gil 2022-7-7
What's the use of 'localedgewidth'?
I do not think the code is well

类别

在 Help Center 和 File Exchange 中查找有关 Dijkstra algorithm 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by