Определите соседние суперпиксели итеративно

Question

Позволять 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

Мне нужно идентифицировать смежные пиксели конкретного суперпикселя,

например

1-я смежность 2 является 1, 3, 4

2-я смежность 2 является 5, 6

3-я смежность 2 является...

Какой самый быстрый способ сделать это?

Answer 1

Вот еще один подход повторного использования кода из вашего предыдущего вопроса:

%// 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 теперь матрица смежности для вашей матрицы A, и это становится проблемой графа. Отсюда вы будете использовать соответствующий алгоритм, чтобы найти кратчайший путь. Длина пути 1 - это ваша "1-я смежность", длина пути 2 - "2-я смежность" и так далее.

• Дейкстра, чтобы найти кратчайший путь из одного узла
• Флойд-Варшалл, чтобы найти кратчайшие пути из всех узлов
• Поиск в ширину для одного узла, плюс вы можете создать удобное дерево

---

Обновить

Я решил поиграть с настраиваемым обходом в ширину, чтобы использовать в этом случае, и это хорошая вещь, которую я сделал. Он выявил некоторые явные ошибки в моем псевдокоде, которые были исправлены выше с помощью работающего кода Matlab.

Используя ваш пример данных, код выше генерирует следующую матрицу смежности:

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

Затем мы можем выполнить обход графика в глубину, поместив каждый уровень дерева в ширину в ряд массива ячеек так, чтобы D{1} перечисляет узлы, которые имеют расстояние 1, D{2} имеет расстояние 2 и т. д.

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

Для начального узла 2, вывод:

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

     1   3   4

  [2,1] =

     5   6

}

Answer 2

Предположим, у вас есть функция adj(value), который имеет код из вашего предыдущего вопроса.

sidenote: вам, вероятно, понравится adj() Функция не возвращает значение пикселя, который вы анализируете. Вы можете сделать это легко.

Вы могли бы сделать:

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

Сейчас size(adjacent,2) будет количество уровней смежности для этого суперпикселя.

Я предполагаю, что этот код является оптимизируемым, я приветствую любую попытку для этого!

Answer 3

Следуя предложению Дэна в комментариях, вот возможная реализация:

% Параметры 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

куда pixVal это пиксель, который вы хотите посмотреть.

Результат:

>> adj{:}

ans =

     1     3     4


ans =

     5     6


ans =

   Empty matrix: 1-by-0