MATLAB identifica le regioni adiacenti nell'immagine 3D

Question

Ho un'immagine 3D, divisa in regioni contigue in cui ogni voxel ha lo stesso valore. Il valore assegnato a questa regione è unico per la regione e funge da etichetta. L'immagine esempio seguente descrive il caso 2D:

 1 1 1 1 2 2 2 
    1 1 1 2 2 2 3 
Im = 1 4 1 2 2 3 3 
    4 4 4 4 3 3 3 
    4 4 4 4 3 3 3 

voglio creare un grafico che descrive adjaciency tra queste regioni. Nel caso di cui sopra, questo sarebbe:

0 1 0 1 
A = 1 0 1 1 
    0 1 0 1 
    1 1 1 0 

Sto cercando una soluzione rapida per fare questo per le grandi immagini 3D in MATLAB. Ho trovato una soluzione che itera su tutte le regioni, che prende lo 0.05s per iterazione - sfortunatamente, questo richiederà più di mezz'ora per un'immagine con 32'000 regioni. Qualcuno ora è un modo più elegante per farlo? Sto postando l'algoritmo corrente al di sotto:

labels = unique(Im); % assuming labels go continuously from 1 to N 
A = zeros(labels); 

for ii=labels 
    % border mask to find neighbourhood 
    dil = imdilate(Im==ii, ones(3,3,3)); 
    border = dil - (Im==ii); 

    neighLabels = unique(Im(border>0)); 
    A(ii,neighLabels) = 1; 
end 

imdilate è il collo di bottiglia vorrei evitare.

Grazie per il vostro aiuto!

Answer 1

mi si avvicinò con una soluzione che è una combinazione di Divakar 's e teng' risposte s, così come i miei proprie modifiche e generalizzati al caso 2D o 3D.

Per renderlo più efficiente, dovrei probabilmente pre-allocare il r e c, ma nel frattempo, questo è il tempo di esecuzione:

• Per un'immagine di dimensione 117x159x1263D e 32000 regioni separate : 0.79s
• Per quanto sopra 2D esempio: 0.004671s con questa soluzione, 0.002136s con la soluzione di Divakar, 0.03995s con la soluzione di teng.

Non ho provato ad estendere il vincitore (Divakar) al case 3D, però!

noDims = length(size(Im)); 
validim = ones(size(Im))>0; 
labels = unique(Im); 

if noDims == 3 
    Im = padarray(Im,[1 1 1],'replicate', 'post'); 
    shifts = {[-1 0 0] [0 -1 0] [0 0 -1]}; 
elseif noDims == 2 
    Im = padarray(Im,[1 1],'replicate', 'post'); 
    shifts = {[-1 0] [0 -1]}; 
end 

% get value of the neighbors for each pixel 
% by shifting the image in each direction 
r=[]; c=[]; 
for i = 1:numel(shifts) 
    tmp = circshift(Im,shifts{i}); 
    r = [r ; Im(validim)]; 
    c = [c ; tmp(validim)]; 
end 

A = sparse(r,c,ones(size(r)), numel(labels), numel(labels)); 
% make symmetric, delete diagonal 
A = (A+A')>0; 
A(1:size(A,1)+1:end)=0; 

Grazie per l'aiuto!

Answer 2

Di seguito è riportato il mio tentativo.

Im = [1 1 1 1 2 2 2; 
    1 1 1 2 2 2 3; 
    1 4 1 2 2 3 3; 
    4 4 4 4 3 3 3; 
    4 4 4 4 3 3 3]; 

% mark the borders 
validim = zeros(size(Im)); 
validim(2:end-1,2:end-1) = 1; 

% get value of the 4-neighbors for each pixel 
% by shifting the images 4 times in each direction 
numNeighbors = 4; 
adj = zeros([prod(size(Im)),numNeighbors]); 
shifts = {[0 1] [0 -1] [1 0] [-1 0]}; 
for i = 1:numNeighbors 
    tmp = circshift(Im,shifts{i}); 
    tmp(validim == 0) = nan; 
    adj(:,i) = tmp(:); 
end 

% mark neighbors where it does not eq Im 
imDuplicates = repmat(Im(:),[1 numNeighbors]); 
nonequals = adj ~= imDuplicates; 
% neglect the border 
nonequals(isnan(adj)) = 0;  
% get these neighbor values and the corresponding Im value 
compared = [imDuplicates(nonequals == 1) adj(nonequals == 1)]; 

% construct your 'A' % possibly could be more optimized here. 
labels = unique(Im); 
A = zeros(numel(labels)); 
for i = 1:size(compared,1) 
    A(compared(i,1),compared(i,2)) = 1; 
end 

Answer 3

Prova questo -

Im = padarray(Im,[1 1],'replicate'); 

labels = unique(Im); 
box1 = [-size(Im,1)-1 -size(Im,1) -size(Im,1)+1 -1 1 size(Im,1)-1 size(Im,1) size(Im,1)+1]; 

mat1 = NaN(numel(labels),numel(labels)); 
for k2=1:numel(labels) 
    a1 = find(Im==k2); 
    for k1=1:numel(labels) 
     a2 = find(Im==k1); 
     t1 = bsxfun(@plus,a1,box1); 
     t2 = bsxfun(@eq,t1,permute(a2,[3 2 1])); 
     mat1(k2,k1) = any(t2(:)); 
    end 
end 
mat1(1:size(mat1,1)+1:end)=0; 

Se funziona per voi, condividere con noi i tempi di esecuzione, come il confronto? Mi piacerebbe vedere se il caffè fa più veloce di mezz'ora!

Answer 4

@Lisa Il ragionamento è elegante, anche se ovviamente fornisce risposte errate per le etichette sui bordi. Prova questo semplice matrice etichetta:

Im = 

1  2  2 
3  3  3 
3  4  4 

La matrice di adiacenza risultante, secondo il codice è:

A = 

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

che rivendica un adiacenze tra etichette "2" e "4": ovviamente sbagliate. Questo accade semplicemente perché stai leggendo etichette Im imbottite basate su indici "validim", che ora non corrispondono alla nuova Im e arriva fino ai bordi inferiori.