Создать граф окрестностей из заданной двоичной матрицы, используя 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 ];

My 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 имеет 1 при A(4,5), A(5,4), A(4,8), A(8,4), A(5,8) и A(8,5).

Как я могу создать такую ​​матрицу смежности A с учетом матрицы B эффективным способом?

Answer 1

Это не требует никакого набора инструментов и работает для квадратных или прямоугольных матриц.Он использует операции с массивами с комплексными числами.

Рассмотрим двоичную матрицу B размера M × N.

1. Создание матрицы M × N, t, который содержит комплексные координаты каждой ненулевой записи B.То есть запись t(r,c) содержит r+1j*c, если B(r,c) не равен нулю, и NaN в противном случае.
2. Вычисляет матрицу M*N × M*N, d, содержащую абсолютную разницу длякаждая пара записей B.Пары записей B, отличных от нуля и смежных, приведут к 1 или sqrt(2) в матрице d.
3. Создайте матрицу результата, 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

Получить B назад от A:

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

Answer 2

Вот решение, использующее набор инструментов для обработки изображений *, которое создает разреженное матричное представление матрицы смежности:

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 можно найти здесь .