Matrix “Zigzag” Reordenación

Considera el código:

 M = randi(100, [3 4]); %# input matrix ind = reshape(1:numel(M), size(M)); %# indices of elements ind = fliplr( spdiags( fliplr(ind) ) ); %# get the anti-diagonals ind(:,1:2:end) = flipud( ind(:,1:2:end) ); %# reverse order of odd columns ind(ind==0) = []; %# keep non-zero indices M(ind) %# get elements in zigzag order 

Un ejemplo con una matriz 4×4:

 » M M = 17 35 26 96 12 59 51 55 50 23 70 14 96 76 90 15 » M(ind) ans = 17 35 12 50 59 26 96 51 23 96 76 70 55 14 90 15 

y un ejemplo con una matriz no cuadrada

 M = 69 9 16 100 75 23 83 8 46 92 54 45 ans = 69 9 75 46 23 16 100 83 92 54 8 45 

Aquí hay una solución sin bucle zig_zag.m . Se ve feo pero funciona !:

 function [M,index] = zig_zag(M) [r,c] = size(M); checker = rem(hankel(1:r,r-1+(1:c)),2); [rEven,cEven] = find(checker); [cOdd,rOdd] = find(~checker.'); %'# rTotal = [rEven; rOdd]; cTotal = [cEven; cOdd]; [junk,sortIndex] = sort(rTotal+cTotal); rSort = rTotal(sortIndex); cSort = cTotal(sortIndex); index = sub2ind([rc],rSort,cSort); M = M(index); end 

Y una matriz de prueba:

 >> M = [magic(4) zeros(4,1)]; M = 16 2 3 13 0 5 11 10 8 0 9 7 6 12 0 4 14 15 1 0 >> newM = zig_zag(M) %# Zig-zag sampled elements newM = 16 2 5 9 11 3 13 10 7 4 14 6 8 0 0 12 15 1 0 0 

Este enfoque es bastante rápido:

 X = randn(500,2000); %// example input matrix [r, c] = size(X); M = bsxfun(@plus, (1:r).', 0:c-1); M = M + bsxfun(@times, (1:r).'/(r+c), (-1).^M); [~, ind] = sort(M(:)); y = X(ind).'; %'// output row vector 

Benchmarking

El siguiente código compara el tiempo de ejecución con el de la excelente respuesta de Amro , usando timeit . Prueba diferentes combinaciones del tamaño de la matriz (número de entradas) y la forma de la matriz (número de filas con relación al número de columnas).

 %// Amro's approach function y = zigzag_Amro(M) ind = reshape(1:numel(M), size(M)); ind = fliplr( spdiags( fliplr(ind) ) ); ind(:,1:2:end) = flipud( ind(:,1:2:end) ); ind(ind==0) = []; y = M(ind); %// Luis' approach function y = zigzag_Luis(X) [r, c] = size(X); M = bsxfun(@plus, (1:r).', 0:c-1); M = M + bsxfun(@times, (1:r).'/(r+c), (-1).^M); [~, ind] = sort(M(:)); y = X(ind).'; %// Benchmarking code: S = [10 30 100 300 1000 3000]; %// reference to generate matrix size f = [1 1]; %// number of cols is S*f(1); number of rows is S*f(2) %// f = [0.5 2]; %// plotted with '--' %// f = [2 0.5]; %// plotted with ':' t_Amro = NaN(size(S)); t_Luis = NaN(size(S)); for n = 1:numel(S) X = rand(f(1)*S(n), f(2)*S(n)); f_Amro = @() zigzag_Amro(X); f_Luis = @() zigzag_Luis(X); t_Amro(n) = timeit(f_Amro); t_Luis(n) = timeit(f_Luis); end loglog(S.^2*prod(f), t_Amro, '.b-'); hold on loglog(S.^2*prod(f), t_Luis, '.r-'); xlabel('number of matrix entries') ylabel('time') 

La figura siguiente se ha obtenido con Matlab R2014b en Windows 7 64 bits. Los resultados en R2010b son muy similares. Se ve que el nuevo enfoque reduce el tiempo de ejecución en un factor entre 2.5 (para matrices pequeñas) y 1.4 (para matrices grandes). Los resultados se consideran casi insensibles a la forma de la matriz, dado el número total de entradas.

Aquí hay una manera de cómo hacer esto. Básicamente, su matriz es una matriz Hankel más vectores de 1: m, donde m es el número de elementos en cada diagonal. Tal vez alguien más tiene una idea clara sobre cómo crear las matrices diagonales que deben agregarse a la matriz de hankel invertida sin un bucle.

Creo que esto debería ser generalizable a una matriz no cuadrada.

 % for a 3x3 array n=3; numElementsPerDiagonal = [1:n,n-1:-1:1]; hadaRC = cumsum([0,numElementsPerDiagonal(1:end-1)]); array2add = fliplr(hankel(hadaRC(1:n),hadaRC(end-n+1:n))); % loop through the hankel array and add numbers counting either up or down % if they are even or odd for d = 1:(2*n-1) if floor(d/2)==d/2 % even, count down array2add = array2add + diag(1:numElementsPerDiagonal(d),dn); else % odd, count up array2add = array2add + diag(numElementsPerDiagonal(d):-1:1,dn); end end % now flip to get the result indexMatrix = fliplr(array2add) result = 1 2 6 3 5 7 4 8 9 

Luego, solo debes llamar a reshape(image(indexMatrix),[],1) para obtener el vector de elementos reordenados.

EDITAR

De acuerdo, a partir de tu comentario, parece que necesitas utilizar el sort como sugirió Marc.

 indexMatrixT = indexMatrix'; % ' SO formatting [dummy,sortedIdx] = sort(indexMatrixT(:)); sortedIdx = 1 2 4 7 5 3 6 8 9 

Tenga en cuenta que primero tendrá que transponer su matriz de entrada antes de indexar, porque Matlab cuenta primero, luego, a la derecha.

Suponiendo que X sea ​​la matriz 2D de entrada y que sea square o landscape-shaped , esto parece ser bastante eficiente:

 [m,n] = size(X); nlim = m*n; n = n+mod(nm,2); mask = bsxfun(@le,[1:m]',[n:-1:1]); start_vec = m:m-1:m*(m-1)+1; a = bsxfun(@plus,start_vec',[0:n-1]*m); offset_startcol = 2- mod(m+1,2); [~,idx] = min(mask,[],1); idx = idx - 1; idx(idx==0) = m; end_ind = a([0:n-1]*m + idx); offsets = a(1,offset_startcol:2:end) + end_ind(offset_startcol:2:end); a(:,offset_startcol:2:end) = bsxfun(@minus,offsets,a(:,offset_startcol:2:end)); out = a(mask); out2 = m*n+1 - out(end:-1:1+m*(n-m+1)); result = X([out2 ; out(out<=nlim)]); 

Pruebas rápidas de tiempo de ejecución contra el enfoque de Luis :

 Datasize: 500 x 2000 ------------------------------------- With Proposed Approach Elapsed time is 0.037145 seconds. ------------------------------------- With Luis Approach Elapsed time is 0.045900 seconds. Datasize: 5000 x 20000 ------------------------------------- With Proposed Approach Elapsed time is 3.947325 seconds. ------------------------------------- With Luis Approach Elapsed time is 6.370463 seconds. 

Supongamos por un momento que tienes una matriz 2D que tiene el mismo tamaño que tu imagen y especifica el índice correcto. Llamar a esta matriz idx; entonces los comandos de matlab para reordenar su imagen serían

 [~,I] = sort (idx(:)); %sort the 1D indices of the image into ascending order according to idx reorderedim = im(I); 

No veo una solución obvia para generar idx sin usar bucles o recursión, pero pensaré un poco más.