Matrix “Zigzag” Reordenación

Tengo una matriz NxM en MATLAB que me gustaría reordenar de manera similar a la forma en que JPEG reordena sus píxeles de subbloque:

patrón de diseño en zigzag (imagen de Wikipedia)

Me gustaría que el algoritmo sea genérico, de modo que pueda pasar una matriz 2D con cualquier dimensión. Soy un progtwigdor de C ++ de oficio y estoy muy tentado de escribir un ciclo de la vieja escuela para lograr esto, pero sospecho que hay una mejor manera de hacerlo en MATLAB.

Actualización: estaría más que contento con un algoritmo que funcionaba en una matriz NxN y vaya desde allí.

Ejemplo:

1 2 3 4 5 6 --> 1 2 4 7 5 3 6 8 9 7 8 9 

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.

enter image description here

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.