I wrote a function that computes efficiently the sparse adjacency matrix, as you described. See sparse_adj_matrix
.
Usage:
[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
For 8-connect
[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
This function can handle arbitrary dimension (more than 2) regular grids with neighborhoods different than 4 or 8 (radius larger than 1, metric L1, L2 or Loo).