Каков наиболее эффективный способ реализации zig-zag ordering в MATLAB?
Я задаю этот вопрос главным образом потому, что это беспокоило меня в течение некоторого времени, и я не понял наиболее эффективный способ его реализации. Это в основном для моего собственного любопытства, поэтому, безусловно, не нужно спешить с ответом на этот вопрос, но если я увижу решение, которое очень эффективно и очень эффективно, я могу наградить щедростью, поэтому есть стимул!
Основной вопрос
Каков наиболее эффективный способ в MATLAB, который вы можете думать об этом, принимает блок/матрицу изображения и преобразует его в вектор, который соответствует зигзагообразному упорядочению? Вы можете предположить, что блок квадрат, где число строк равно числу столбцов.
Некорректный фон
Заказ Zigzag первоначально происходит из стандарта сжатия JPEG. Основные этапы алгоритма сжатия JPEG можно показать на следующей диаграмме:
Источник: Wikipedia
Подводя итог, для изображения он разбивается на 8 x 8 отдельных блоков изображения, 2D Дискретное косинусное преобразование ( DCT) берется на каждом блоке, тогда quantization выполняется на каждом блоке, чтобы разрешить кодирование, которое сводит к минимуму полную энтропию последовательность бит. Наиболее важным этапом для этого является этап энтропийного кодирования и последняя часть алгоритма.
Часть этапа энтропийного кодирования включает в себя zigzag ordering. Блок переупорядочивается в вектор-элемент 64 таким образом, что сначала появляются наиболее важные частотные компоненты DCT, за которыми следуют те компоненты, которые на самом деле не имеет значения, чтобы восстановить блок.
Вот графическое представление зигзагообразного упорядочения на блоке 8 x 8:
Источник: Wikipedia
Синяя стрелка начинается с левого верхнего положения или начала изображения. Далее, направление движения стрелки указывает, как вектор элементов должен быть заполнен элементами.
Вот основной алгоритм зигзага со ссылкой на приведенный выше рисунок:
- Начните с левого верхнего угла блока.
- Мы перемещаем одно пространство вправо, затем вниз по диагонали, пока не нажмем рамку изображения.
- Как только мы нажмем рамку изображения на шаге 2, мы переместим одно место вниз, а затем вертикально потянемся, пока мы не достигнем границы изображения.
- Перейдите между шагами №2 и №3 до тех пор, пока мы не дойдем до нижнего правого блока.
Есть несколько угловых случаев, о которых вам нужно знать:
- Угловой случай # 1 - Если мы находимся на шаге 2, мы попадаем в рамку изображения, и мы находимся в последнем столбце блока, не перемещаем одно пространство вправо. Вместо этого переместите одно пространство вниз.
- Угловой корпуС# 2. Если мы находимся на шаге 3, мы попадаем в рамку изображения, и мы находимся в последней строке блока, < не перемещаем одно место вниз. Вместо этого переместите одно место в справа.
Как только происходит зигзагообразное упорядочение, выполняется любой алгоритм сжатия без потерь, такой как Huffman... и да, даже энтропийное кодирование (как то, что названо этим этапом) выполняется по этим переупорядоченным данным. Эти 64 вектора элементов передаются в алгоритм сжатия, и у вас есть сжатое изображение.
Вернуться к описанию проблемы
Вероятно, ты видишь мою дилемму. Из-за угловых случаев я не нашел эффективного способа сделать это, не пытаясь сделать это с помощью циклов. После некоторого начального поиска в Интернете я нашел очень похожую запись в Rosetta Code, в которой говорится о создании матрицы зигзага. Цель здесь состоит в том, чтобы создать матрицу размера M x M, где задано целое число M > 0, каждое место в матрице перечисляется от 0 до M^2 - 1, где числа обозначаются в порядке, в котором порядок zig-zag выполняется, а не как один вектор. С некоторыми очень простыми изменениями вы можете решить вышеупомянутую проблему, но мне было интересно, есть ли способ сделать это более эффективным, чем циклы. Если вы проверите код, он очень неинтуитивный и не имеет большого смысла, если вы не начнете показывать шаги в окне команд. Даже когда это так, это все еще довольно сложно понять, и я осмелюсь предположить, что он запутан.
Для самоограничения это "ссылочный" код, который реализует зигзаговое упорядочение с помощью циклов. Это было снято с Rosetta Code, но я изменил его так, чтобы он соответствовал предлагаемой проблеме. Это занимает двумерную квадратную матрицу blk, а out - вектор, который производит элементы, взятые из квадратной матрицы в зигзаговом порядке:
function out = zigzag(blk)
%This is very unintiutive. This algorithm parameterizes the
%zig-zagging movement along the matrix indicies. The easiest way to see
%what this algorithm does is to go through line-by-line and write out
%what the algorithm does on a peace of paper.
[m,n] = size(blk);
if m ~= n
error('Not square');
end
out = zeros(numel(blk), 1);
flipCol = true;
flipRow = false;
out(1) = blk(1);
counter = 2;
%This for loop does the top-diagonal of the matrix
for i = (2:n)
row = (1:i);
column = (1:i);
%Causes the zig-zagging. Without these conditionals,
%you would end up with a diagonal matrix.
%To see what happens, comment these conditionals out.
if flipCol
column = fliplr(column);
flipRow = true;
flipCol = false;
elseif flipRow
row = fliplr(row);
flipRow = false;
flipCol = true;
end
%Selects a diagonal of the zig-zag matrix and places the
%correct integer value in each index along that diagonal
for j = (1:numel(row))
out(counter) = blk(row(j),column(j));
counter = counter + 1;
end
end
%This for loop does the bottom-diagonal of the matrix
for i = (2:n)
row = (i:n);
column = (i:n);
%Causes the zig-zagging. Without these conditionals,
%you would end up with a diagonal matrix.
%To see what happens comment these conditionals out.
if flipCol
column = fliplr(column);
flipRow = true;
flipCol = false;
elseif flipRow
row = fliplr(row);
flipRow = false;
flipCol = true;
end
%Selects a diagonal of the zig-zag matrix and places the
%correct integer value in each index along that diagonal
for j = (1:numel(row))
out(counter) = blk(row(j),column(j));
counter = counter + 1;
end
end
end
Как таковой, это вызов сообществу MATLAB SO, чтобы узнать, существует ли более простая реализация, используя конструктивные и векторизованные конструкторы MATLAB.
Спасибо за ваше время за чтение и с нетерпением ждем ваших ответов!