Матричное “зигзагообразное” переупорядочение
У меня есть матрица NxM в MATLAB, который я хотел бы переупорядочить точно так же к способу, которым JPEG переупорядочивает свои пиксели подблока:
Я хотел бы, чтобы алгоритм был универсален таким образом, что я могу передать в 2D матрице с любыми размерами. Я - программист на C++ торговлей и очень испытываю желание записать старый школьный цикл для выполнения этого, но я подозреваю, что существует лучший способ сделать это в MATLAB.
Я был бы, скорее хотят алгоритм, который продолжил работать NxN матрица и идет оттуда.
Пример:
1 2 3
4 5 6 --> 1 2 4 7 5 3 6 8 9
7 8 9
4 ответа
Рассмотрим код:
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
Пример с матрицей 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
и пример с неквадратной матрицей:
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
Вот непетлевое решение zig_zag.m. Выглядит уродливо, но работает!:
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
И тестовая матрица:
>> 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
Вот способ, как это сделать. По сути, ваш массив - это матрица Ханкеля плюс векторы 1:m, где m - количество элементов в каждой диагонали. Может быть, у кого-то есть идея, как создать диагональные массивы, которые должны быть добавлены к перевернутому массиву Ханкеля без цикла.
Я думаю, что это можно обобщить на неквадратный массив.
% 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
После этого вы просто вызываете reshape(image(indexMatrix),[],1), чтобы получить вектор переупорядоченных элементов.
EDIT
Ок, из вашего комментария следует, что вам нужно использовать sort, как предложил Марк.
indexMatrixT = indexMatrix'; % ' SO formatting
[dummy,sortedIdx] = sort(indexMatrixT(:));
sortedIdx =
1 2 4 7 5 3 6 8 9
Обратите внимание, что вам нужно сначала транспонировать вашу входную матрицу перед индексированием, потому что Matlab считает сначала вниз, потом вправо.
Предположим на минуту, что у вас есть двумерная матрица того же размера, что и ваше изображение, с указанием правильного индекса. Назовем этот массив idx; тогда команды matlab для переупорядочивания изображения будут
[~,I] = sort (idx(:)); %sort the 1D indices of the image into ascending order according to idx
reorderedim = im(I);
Я не вижу очевидного решения для создания idx без использования циклов for или рекурсии, но я подумаю еще немного.