Identify adjacent superpixels iteratively

Question

Let A be:

 1 1 1 1 1 1
 1 2 2 3 3 3
 4 4 2 2 3 4
 4 4 4 4 4 4
 4 4 5 5 6 6
 5 5 5 5 5 6

I need to identify a particular superpixel's adjacent pixels,

e.g.

The 1st adjacency of 2 is 1, 3, 4

The 2nd adjacency of 2 is 5, 6

The 3rd adjacency of 2 is ...

What is the FASTEST way to do it?

Do you have access to the image processing toolbox? I suspect this is easy to solve using [`imdilate`](http://www.mathworks.com/help/images/ref/imdilate.html), unique and logical index. Also are all unique number guaranteed to be connected or could there be two "islands" of say `2`s that are not connected to each other? — Dan, Jul 21 '15 at 10:12

score 1 · Answer 1 · edited Jun 20 '20 at 09:12

Assume you have a function adj(value), that has the code from your previous question.

sidenote: you probably would like that adj() function not to return the value of the pixel you are analyzing. you can make that easily.

you could do:

img=[your stuff];
imgaux=img;
ii=1;
val=2; %whatever value you want
while numel(unique(imgaux))>1 % Stop if the whole image is a single superpixel
   adjacent{ii}=adj(val);
   % expand the superpixel to the ii order of adjacency
   for jj=1:size(adjacent{ii},1)
       imgaux(imgaux==adjacent{ii}(jj))==val; 

   end
   ii=ii+1;
end

Now size(adjacent,2) will be the amount of adjacency levels for that superpixel.

I am guessing this code is optimizable, I welcome any try for it!

I also thought the same way. But not sure this is the fastest/efficient way. — user570593, Jul 21 '15 at 12:29

score 1 · Answer 2 · answered Jul 21 '15 at 12:11

Following Dan's suggestion on the comments, here is a possible implementation:

% Parameters pixVal = 2;

adj = {};
prevMask = A == pixVal;
for ii = 1:length(A)
    currMask = imdilate(prevMask, ones(2 * ii + 1));
    adj{ii} = setdiff(unique(A(currMask & ~prevMask))', [adj{:}]);
    if isempty(adj{ii})
        break
    end
    prevMask = currMask;
end

Where pixVal is the pixel you want to look at.

Result:

>> adj{:}

ans =

     1     3     4


ans =

     5     6


ans =

   Empty matrix: 1-by-0

beaker · Answer 3 · 2015-07-23T03:09:21.580

Here's another approach reusing the code from your previous question:

%// create adjacency matrix
%// Includes code from @LuisMendo's answer
% // Data:
A = [ 1 1 1 1 1 1
      1 2 2 3 3 3
      4 4 2 2 3 4
      4 4 4 4 4 4
      4 4 5 5 6 6
      5 5 5 5 5 6 ];

adj = [0 1 0; 1 0 1; 0 1 0]; %// define adjacency. [1 1 1;1 0 1;1 1 1] to include diagonals

nodes=unique(A);
J=zeros(numel(nodes));
for value=nodes.'
   mask = conv2(double(A==value), adj, 'same')>0; %// from Luis' code
   result = unique(A(mask));                      %// from Luis' code
   J(value,result)=1;
   J(value,value)=0;
end

J is now the adjacency matrix for your matrix A and this becomes a graph problem. From here you would use the appropriate algorithm to find the shortest path. Path length of 1 is your "1st adjacency", path length of 2 is "2nd adjacency" and so on.

Dijkstra to find shortest path from a single node
Floyd-Warshall to find shortest paths from all the nodes
Breadth-first search for a single node, plus you can generate a handy tree

Update

I decided to play around with a custom Breadth-First Traversal to use in this case, and it's a good thing I did. It exposed some glaring errors in my pseudocode, which has been corrected above with working Matlab code.

Using your sample data, the code above generates the following adjacency matrix:

J =

   0   1   1   1   0   0
   1   0   1   1   0   0
   1   1   0   1   0   0
   1   1   1   0   1   1
   0   0   0   1   0   1
   0   0   0   1   1   0

We can then perform a depth-first traversal of the graph, putting each level of the breadth-first tree in a row of a cell array so that D{1} lists the nodes that have a distance of 1, D{2} has a distance of 2, etc.

function D = BFD(A, s)
%// BFD - Breadth-First Depth
%// Find the depth of all nodes connected to node s
%// in graph A (represented by an adjacency matrix)
   A=logical(A);   %// all distances are 1
   r=A(s,:);       %// newly visited nodes at the current depth
   v=r;            %// previously visited nodes
   v(s)=1;         %// we've visited the start node
   D={};           %// returned Depth list
   while any(r)
      D(end+1,:)=find(r);
      r=any(A(r,:))&~v;
      v=r|v;
   end
 end

For a start node of 2, the output is:

>> D=BFD(J,2)
D =
{
  [1,1] =

     1   3   4

  [2,1] =

     5   6

}

Identify adjacent superpixels iteratively

3 Answers3