CODEWITHSUNDEEP
matlabimage-processingsuperpixels
user570593
user570593

Reputation: 3520

Identify adjacent superpixels iteratively

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?

Upvotes: 3

Views: 717

Answers (3)

beaker
beaker

Reputation: 16811

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

}

Upvotes: 1

Rafael Monteiro
Rafael Monteiro

Reputation: 4549

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

Upvotes: 1

Ander Biguri
Ander Biguri

Reputation: 35525

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!

Upvotes: 1

Related Questions