CODEWITHSUNDEEP
matlabmatrixadjacency-matrix
Shew
Shew

Reputation: 1596

Create a neighbourhood graph from a given binary matrix using matlab

I am trying to create a neighbourhood graph from a given binary matrix B. Neighbourhood graph (A) is defined as an adjacency matrix such that

(A(i,j) = A(j,i) = 1)

if the original matrix B(i) = B(j) = 1 and i and j are adjacent to each (left, right, up, down or diagonal). Here I used the linear subscript to access the original matrix B. For example, consider the below matrix

B = [ 0 1 0; 
      0 1 1; 
      0 0 0 ];

My A will be a 9 * 9 graph as given below

A = [ 0 0 0 0 0 0 0 0 0; 
      0 0 0 0 0 0 0 0 0; 
      0 0 0 0 0 0 0 0 0; 
      0 0 0 0 1 0 0 1 0; 
      0 0 0 1 0 0 0 1 0; 
      0 0 0 0 0 0 0 0 0; 
      0 0 0 0 0 0 0 0 0; 
      0 0 0 1 1 0 0 0 0; 
      0 0 0 0 0 0 0 0 0 ];

Since in the original B matrix, B(4), B(5) and B(8) are adjacent with corresponding entries 1, the adjacency matrix A has 1 at A(4,5), A(5,4), A(4,8), A(8,4), A(5,8) and A(8,5).

How can I create such an adjacency matrix A given the matrix B in an efficient way?

Upvotes: 2

Views: 277

Answers (2)

Luis Mendo
Luis Mendo

Reputation: 112679

This doesn't require any toolbox, and works for square or rectangular matrices. It uses array operations with complex numbers.

Consider a binary matrix B of size M×N.

  1. Create an M×N matrix, t, that contains the complex coordinates of each nonzero entry of B. That is, entry t(r,c) contains r+1j*c if B(r,c) is nonzero, and NaN otherwise.
  2. Compute an M*N×M*N matrix, d, containing the absolute difference for each pair of entries of B. Pairs of entries of B that are nonzero and adjacent will produce 1 or sqrt(2) in matrix d.
  3. Build the result matrix, A, such that it contains 1 iff the corresponding entry in d equals 1 or sqrt(2). Equivalently, and more robust to numerical errors, iff the corresponding entry in d is between 0 and 1.5.

Code:

B = [0 1 0; 0 1 1; 0 0 0]; % input
t = bsxfun(@times, B, (1:size(B,1)).') + bsxfun(@times, B, 1j*(1:size(B,2)));
t(t==0) = NaN; % step 1
d = abs(bsxfun(@minus, t(:), t(:).')); % step 2
A = d>0 & d<1.5; % step 3

To get B back from A:

B2 = zeros(sqrt(size(A,1)));
B2(any(A,1)) = 1;

Upvotes: 2

rahnema1
rahnema1

Reputation: 15837

Here is a solution using image processing toolbox* that creates sparse matrix representation of the adjacency matrix:

B = [ 0 1 0; 
      0 1 1; 
      0 0 0 ]

n = numel(B);
C = zeros(size(B));
f = find(B);
C(f) = f;

D = padarray(C,[1 1]);
%If you don't have image processing toolbox
%D = zeros(size(C)+2);
%D(2:end-1,2:end-1)=C;
E = bsxfun(@times, im2col(D,[3 3]) , reshape(B, 1,[]));
[~ ,y] = find(E);
result = sparse(nonzeros(E),y,1,n,n);
result(1:n+1:end) = 0;

*More efficient implementation of im2col can be found here.

Upvotes: 2

Related Questions