Эффективное заполнение разреженной матрицы на основе 4-пиксельных или 8-пиксельных окрестностей

Question

Учитывая изображение размера [hh,ww]Я хотел бы эффективно создать разреженную матрицу размера [hh*ww, hh*ww], Для каждого 4 или 8 соседей данного пикселя разреженная матрица должна быть заполнена постоянным значением (скажем, -1) в правильной строке (которая представляет оцениваемый пиксель) и столбцах (соответствующие 4-соседям или 8-соседям пикселя).

Например, учитывая 4-пиксельную окрестность и матрицу [2,2], результирующая разреженная матрица размером [4,4] выглядит следующим образом:

 0  -1  -1   0
-1   0   0  -1
-1   0   0  -1
 0  -1  -1   0

Первый ряд был заполнен -1 в столбцах № 2 и № 3, поскольку эти пиксели находятся в 4-окрестности пикселя 1 (линейное индексирование приведено ниже):

1   3
2   4

Приведенный ниже код работает, но становится очень медленным, когда матрицы становятся слишком большими, например, для матрицы 2000x2000.

hh=2;
ww=2;
%hh=2000;
%ww=2000;
sG     = sparse(hh*ww,hh*ww);
linIdx = reshape(1:hh*ww, [hh ww]);
sG( sub2ind([hh*ww hh*ww], linIdx(:,1:end-1),linIdx(:,2:end)) ) = -1;
sG( sub2ind([hh*ww hh*ww], linIdx(1:end-1,:),linIdx(2:end,:)) ) = -1;
sG = max(sG, sG'); 

Есть идеи, как сделать код эффективным при наличии больших матриц? В идеале это должно работать для 4-neighborhoods или же 8-neighborhoods,

Answer 1

Я написал функцию, которая эффективно вычисляет матрицу разреженной смежности, как вы описали. Увидеть sparse_adj_matrix,

Использование:

[ii jj] = sparse_adj_matrix( [hh ww], 1, 1 ); % p is L1 for 4-connect 
sG = sparse( ii, jj, -1, hh*ww, hh*ww ); % construct the sparse matrix

Для 8-коннект

[ii jj] = sparse_adj_matrix( [hh ww], 1, inf ); % p is inf for 8-connect 
sG = sparse( ii, jj, -1, hh*ww, hh*ww ); % construct the sparse matrix

Эта функция может обрабатывать регулярные сетки произвольного размера (более 2) с окрестностями, отличными от 4 или 8 (радиус больше 1, метрика L1, L2 или Loo).