1

Given an image of size [hh,ww], I would like to create efficiently a sparse matrix of size [hh*ww, hh*ww]. For each 4- or 8-neighbor of a given pixel, the sparse matrix should be filled with a constant value (say -1) at the proper row (which represents the pixel under evaluation) and columns (the corresponding 4-neighbors or 8-neighbors of the pixel).

For instance, considering a 4-pixel neighborhood and a [2,2] matrix, the resulting sparse matrix of size [4,4] looks like:

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

The first row was filled with -1 at columns #2 and #3 since those pixels are in the 4-neighborhood of pixel 1 (linear indexing given below ):

1   3
2   4

The code below does the work, but becomes very slow whenever the matrices become too large, for instance, for a 2000x2000 matrix.

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');

Any ideas how to make the code efficient when having large matrices? Ideally, it should work for 4-neighborhoods or 8-neighborhoods.

Tin
  • 1,006
  • 1
  • 15
  • 27
  • possible duplicate of [Construct adjacency matrix in MATLAB](http://stackoverflow.com/questions/3277541/construct-adjacency-matrix-in-matlab) – Shai Mar 02 '14 at 13:40

1 Answers1

2

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).

Shai
  • 111,146
  • 38
  • 238
  • 371
  • thanks @Shai! sounds good! What if I need to fill the upper-triangular matrix with a given value `x1` and the lowe-triangular-matrix with another value say `x2`. Would it also work? – Tin Mar 02 '14 at 13:41
  • @Tin - once you have indices `ii` and `jj` into the matrix `sG` you can manipulate them: `sG = sparse( ii, jj, x1*( ii > jj ) + x2*( ii < jj ), ww*hh, ww*hh );` – Shai Mar 02 '14 at 13:43
  • One more thing @Shai, imagine that the values to be filled `x1` and `x2` come from 2 different matrices `M1` and `M2` each of size `[hh,ww]`, how could I then place the values in the sparse matrix in the correct way? The upper triangular part should come from `M1` and the lower triangular from `M2` – Tin Mar 02 '14 at 14:31