% REGIONADJACENCY Computes adjacency matrix for image of labeled segmented regions
%
% Usage: [Am, Al] = regionadjacency(L, connectivity)
%
% Arguments: L - A region segmented image, such as might be produced by a
% graph cut or superpixel algorithm. All pixels in each
% region are labeled by an integer.
% connectivity - 8 or 4. If not specified connectivity defaults to 8.
%
% Returns: Am - An adjacency matrix indicating which labeled regions are
% adjacent to each other, that is, they share boundaries. Am
% is sparse to save memory.
% Al - A cell array representing the adjacency list corresponding
% to Am. Al{n} is an array of the region indices adjacent to
% region n.
%
% Regions with a label of 0 are not processed. They are considered to be
% 'background regions' that are not to be considered. If you want to include
% these regions you should assign a new positive label to these areas using, say
% >> L(L==0) = max(L(:)) + 1;
%
% See also: CLEANUPREGIONS, RENUMBERREGIONS, SLIC
% Copyright (c) 2013 Peter Kovesi
% www.peterkovesi.com/matlabfns/
%
% Permission is hereby granted, free of charge, to any person obtaining a copy
% of this software and associated documentation files (the "Software"), to deal
% in the Software without restriction, subject to the following conditions:
%
% The above copyright notice and this permission notice shall be included in
% all copies or substantial portions of the Software.
%
% February 2013 Original version
% July 2013 Speed improvement in sparse matrix formation (4x)
function [Am, varargout] = regionadjacency(L, connectivity)
if ~exist('connectivity', 'var'), connectivity = 8; end
[rows,cols] = size(L);
% Identify the unique labels in the image, excluding 0 as a label.
labels = setdiff(unique(L(:))',0);
if isempty(labels)
warning('There are no objects in the image')
Am = [];
Al = {};
return
end
N = max(labels); % Required size of adjacency matrix
% Strategy: Step through the labeled image. For 8-connectedness inspect
% pixels as follows and set the appropriate entries in the adjacency
% matrix.
% x - o
% / | \
% o o o
%
% For 4-connectedness we only inspect the following pixels
% x - o
% |
% o
%
% Becuase the adjacency search looks 'forwards' a final OR operation is
% performed on the adjacency matrix and its transpose to ensure
% connectivity both ways.
% Allocate vectors for forming row, col, value triplets used to construct
% sparse matrix. Forming these vectors first is faster than filling
% entries directly into the sparse matrix
i = zeros(rows*cols,1); % row value
j = zeros(rows*cols,1); % col value
s = zeros(rows*cols,1); % value
if connectivity == 8
n = 1;
for r = 1:rows-1
% Handle pixels in 1st column
i(n) = L(r,1); j(n) = L(r ,2); s(n) = 1; n=n+1;
i(n) = L(r,1); j(n) = L(r+1,1); s(n) = 1; n=n+1;
i(n) = L(r,1); j(n) = L(r+1,2); s(n) = 1; n=n+1;
% ... now the rest of the column
for c = 2:cols-1
i(n) = L(r,c); j(n) = L(r ,c+1); s(n) = 1; n=n+1;
i(n) = L(r,c); j(n) = L(r+1,c-1); s(n) = 1; n=n+1;
i(n) = L(r,c); j(n) = L(r+1,c ); s(n) = 1; n=n+1;
i(n) = L(r,c); j(n) = L(r+1,c+1); s(n) = 1; n=n+1;
end
end
elseif connectivity == 4
n = 1;
for r = 1:rows-1
for c = 1:cols-1
i(n) = L(r,c); j(n) = L(r ,c+1); s(n) = 1; n=n+1;
i(n) = L(r,c); j(n) = L(r+1,c ); s(n) = 1; n=n+1;
end
end
else
error('Connectivity must be 4 or 8');
end
% Form the logical sparse adjacency matrix
Am = logical(sparse(i, j, s, N, N));
% Zero out the diagonal
for r = 1:N
Am(r,r) = 0;
end
% Ensure connectivity both ways for all regions.
Am = Am | Am';
% If an adjacency list is requested...
if nargout == 2
Al = cell(N,1);
for r = 1:N
Al{r} = find(Am(r,:));
end
varargout{1} = Al;
end