Find path through logical matrix (only walking right or down)

Hello,

I have given a logical matrix, e.g.

1 1 0 0 0 0

0 0 1 0 0 0

0 0 1 0 0 0

0 0 0 1 1 1

I want to check if I can walk from the top left corner to the bottom right corner. It shall only be possible to walk "forward" meaning I can only go to the right, bottom, or bottom right diagonal. Permitted fields are marked with the value 1.

I have tried it with "bwlabel" but there are only symmetric masks possible. What I would need is the mask

0 0 0

0 1 1

0 1 1

Has anyone an idea how I can implement that, mostly as computationally efficient as possible.

Thank you very much in advance.

[Stephen23]

Perhaps CONV2 might help you:

https://www.mathworks.com/help/matlab/ref/conv2.html

[Dyuman Joshi]

Adding @Stephen23's answer to @Stephen23's comment - Finding neighbours of elements in a matrix using conv2()

[DGM]

I don't see how connectivity alone can solve the problem. Using conv2() or bwlookup() will tell you whether you can make the next step from the perspective of a single pixel, but they won't tell you if you can reach any given pixel from any other pixel.

I'm inclined to think there is an obvious solution that I'm not seeing. (other than just walking through the image)

Answer 1

[Jon]

It seems natural to think of this as a graph traversal question, where the nodes in a directed graph are the locations in the matrix where there are nonzero (true) elements. Maybe a simpler way to solve this, but here's how you could do it using a directed graph

% Define matrix to be checked
M = logical([...
1 1 0 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 1 1])

M = 4×6 logical array
   1   1   0   0   0   0
   0   0   1   0   0   0
   0   0   1   0   0   0
   0   0   0   1   1   1

[m,n] = size(M);
% Augment M with additional row and column of zeros to make bookkeeping
% easier
Ma = [M zeros(m,1);zeros(1,n+1)];


% Make corresponding adjacency matrix
% 

numNodes = sum(Ma(:));
idx = find(Ma(:)); % linear indices of non-zero elements
[ma,na] = size(Ma);
A = zeros(ma*na); % preallocate adjacency matrix
for k = 1:numNodes
    % get row and column indices corresponding to this node
    [i,j] = ind2sub([ma,na],idx(k));

    % add possible connections to neighbors
    A(idx(k),sub2ind([ma,na],i,j+1)) = 1;
    A(idx(k),sub2ind([ma,na],i+1,j+1)) = 1;
    A(idx(k),sub2ind([ma,na],i+1,j)) = 1;
end
% Remove non-existent nodes from adjacency matrix
idl = logical(Ma(:));
A = A(idl,idl);

% Make directed  graph
G = digraph(A);

% Find out if first and last node are connected
connected = ~isempty(shortestpath(G,1,numNodes))

connected = logical
   1

[Jon]

You can also do this without loops

% Define matrix to be checked
M = logical([...
    1 1 0 0 0 0
    0 0 1 0 0 0
    0 0 1 0 0 0
    0 0 0 1 1 1]);

[m,n] = size(M);
% Augment M with additional row and column of zeros to make bookkeeping
% easier
Ma = [M zeros(m,1);zeros(1,n+1)];


% Make corresponding adjacency matrix
numNodes = sum(Ma(:));
idx = find(Ma(:)); % linear indices of non-zero elements
szMa = size(Ma);
szA = [szMa(1)*szMa(2),szMa(1)*szMa(2)]; % size of adjacency matrix
A = zeros(szA); % preallocate adjacency matrix
% Add possible connection to all the neighbors (below, right, below-diag)
% some of these connections may be to nodes that are not in the graph
[i,j] = ind2sub(szMa,idx);
A(sub2ind(szA,idx,sub2ind(szMa,i+1,j))) = 1; % below
A(sub2ind(szA,idx,sub2ind(szMa,i,j+1))) = 1; % right
A(sub2ind(szA,idx,sub2ind(szMa,i+1,j+1))) = 1; % diagonal

% Remove non-existent nodes from adjacency matrix
idl = logical(Ma(:));
A = A(idl,idl);

% Make directed  graph
G = digraph(A);

% Find out if first and last node are connected
connected = ~isempty(shortestpath(G,1,numNodes))

connected = logical
   1

[Jon]

Were you able to give this a try?