Матрица "Зигзаг" Изменение порядка

Question

У меня есть матрица 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

Answer 1

Рассмотрим код:

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

Answer 2

Этот подход довольно быстрый:

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

Бенчмаркинг

Следующий код сравнивает время выполнения с Отличный ответ Amro , используя timeit.Он проверяет различные комбинации размера матрицы (количество записей) и формы матрицы (отношение количества строк к количеству столбцов).

%// 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')

Рисунок ниже получен с Matlab R2014b в Windows 7 64 бит.Результаты в R2010b очень похожи.Видно, что новый подход сокращает время выполнения в 2,5 раза (для маленьких матриц) до 1,4 (для больших матриц).Результаты считаются почти нечувствительными к форме матрицы, учитывая общее количество записей.

Answer 3

Вот решение без петель 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

Answer 4

Вот способ, как это сделать.По сути, ваш массив представляет собой матрицу Ханкеля и векторы 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), чтобы получить вектор переупорядоченных элементов.

РЕДАКТИРОВАТЬ

Хорошо, из вашего комментария это выглядит как вынужно использовать sort, как предложил Марк.

indexMatrixT = indexMatrix';   % ' SO formatting
[dummy,sortedIdx] = sort(indexMatrixT(:));

sortedIdx =
     1     2     4     7     5     3     6     8     9

Обратите внимание, что вам нужно сначала транспонировать входную матрицу перед индексированием, потому что Matlab считает сначала вниз, затем вправо.

Answer 5

Предполагая X входной 2D матрицей, а это square или landscape-shaped, это кажется довольно эффективным -

[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)]);

Быстрые тесты времени выполнения против Подход Луиса -

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.

Answer 6

Давайте на минутку предположим, что у вас есть двумерная матрица того же размера, что и ваше изображение с указанием правильного индекса. Вызовите этот массив idx; тогда команды matlab для изменения порядка изображения будут

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

Я не вижу очевидного решения для генерации idx без использования циклов for или рекурсии, но я подумаю еще.