matlab - for - Matrix "Zigzag" Reordenación
for matlab (6)
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),d-n);
else
% odd, count up
array2add = array2add + diag(numElementsPerDiagonal(d):-1:1,d-n);
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.
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:
Me gustaría que el algoritmo sea genérico, de modo que pueda pasar una matriz 2D con cualquier dimensión. Soy un programador 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
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([r c],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
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 4x4:
» 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
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.
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.
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(n-m,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.