使用 matlab 从给定的二进制矩阵创建邻域图

Question

我正在尝试从给定的二进制矩阵 B 创建邻域图。邻域图 (A) 被定义为邻接矩阵，使得

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

如果原始矩阵B(i) = B(j) = 1和i和j彼此相邻（左，右，上，下或对角线）。这里我使用了线性下标来访问原始矩阵B。例如，考虑下面的矩阵

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

我的 A 将是一个 9 * 9 的图表，如下所示

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 ];

由于在原始B矩阵中，B(4)、B(5)和B(8)与相应的条目1相邻，所以邻接矩阵A 在 A(4,5)、A(5,4)、A(4,8)、A(8,4)、A(5,8) 和 A(8,5).

处有 1

如何在给定矩阵 B 的情况下以有效的方式创建这样的邻接矩阵 A？

Answer 1

这是一个使用图像处理工具箱*的解决方案，它创建了邻接矩阵的稀疏矩阵表示：

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;

*可以找到 im2col 的更有效实现 here。

Answer 2

这不需要任何工具箱，适用于方形或矩形矩阵。它使用复数数组运算。

考虑大小为 M×N 的二进制矩阵 B。

创建一个 M×N 矩阵 t，其中包含 B 的每个非零条目的复数坐标。也就是说，如果 B(r,c) 非零，条目 t(r,c) 包含 r+1j*c，否则 NaN。
计算一个 M*N×M*N 矩阵，d，包含 B 的每对条目的绝对差值。 B 的非零且相邻的条目对将在矩阵 d.

1

sqrt(2)

构建结果矩阵 A，使其包含 1 当且仅当 d 中的相应条目等于 1 或 sqrt(2)。等效地，并且对数值错误更稳健，当且仅当 d 中的相应条目在 0 和 1.5 之间。

代码：

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

要从 A 取回 B：

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

使用 matlab 从给定的二进制矩阵创建邻域图

Create a neighbourhood graph from a given binary matrix using matlab

matlab

matrix

adjacency-matrix