在MATLAB中实现Zig-zag排序的最有效方法是什么？

Question

我问这个问题主要是因为它困扰了我一段时间,我还没有想出实现这个问题最有效的方法.这主要是出于我自己的好奇心,所以肯定不会急于回答这个问题,但如果我看到一个非常有效且非常有效的解决方案,我可能会奖励一个奖励,所以有一些激励!

---

主要问题

您能想到的MATLAB中最有效的方法是采用图像块/矩阵并将其转换为符合Z字形排序的向量？您可以假设块是方形的,其中行数等于列数.

一些背景

Zigzag排序最初来自JPEG压缩标准.JPEG压缩算法背后的基本步骤如下图所示:

^{资料来源:维基百科}

总而言之,对于图像,将其分成8×8个不同的图像块,对每个块进行2D 离散余弦变换(DCT),然后对每个块执行量化以允许进行最小化总熵的编码.比特序列.对此最重要的阶段是熵编码阶段,并且是算法的最后部分.

熵编码阶段的一部分涉及Z字形排序 - 该块被重新排序为64元素向量,其中来自DCT的最重要的频率分量首先出现,然后是那些对于重建块.

以下是8 x 8块上锯齿形排序的图形表示:

^{资料来源:维基百科}

蓝色箭头从图像的左上角或原点开始.接下来,箭头移动的方向指示64元素向量如何用元素填充.

以下是参考上图的zigzag的基本算法:

1. 从块的左上角开始.
2. 我们向右移动一个空格,然后沿对角线向下移动,直到我们到达图像边界.
3. 一旦我们在步骤#2中击中图像边框,我们向下移动一个空格,然后沿对角线直立移动,直到我们到达图像边界.
4. 在步骤#2和#3之间交替,直到我们到达块的右下角.

您需要注意几个极端情况:

• 极端情况#1 -如果我们在第2步,我们打的图像边界,我们在块的最后一列,也没有动一个格的权利.改为向下移动一个空格.
• 极端情况#2 -如果我们在第3步,我们打的图像边界,我们在块的最后一行,也没有移动一个格下来.改为向右移动一个空格.

一旦出现Z字形排序,就会对此重新排序的数据执行任何无损压缩算法,例如Huffman ......以及甚至熵编码(如此阶段命名的那样).这64个元素向量将流式传输到压缩算法,因此您可以获得压缩图像.

---

回到问题描述

你现在可能正在看到我的困境.由于角落的情况,我没有找到一种有效的方法来做到这一点,而不试图用循环来做这件事.在互联网上进行了一些初步搜索之后,我在Rosetta Code上发现了一个非常类似的帖子,讨论了如何创建一个Z字形矩阵.这里的目标是产生一个大小的矩阵,M x M其中给定一个整数M > 0,矩阵中的每个位置都被枚举0,M^2 - 1其中数字按照执行之字形排序的顺序描绘,而不是作为单个向量.通过一些非常简单的修改,您可以解决上述问题,但我想知道是否有任何方法可以比循环更有效.如果你检查代码,它是非常不直观的,除非你开始在命令窗口中显示步骤,否则没有多大意义.即使在这种情况下,它仍然很难理解,我敢说是混淆了.

对于自包含,这是使用循环实现zig-zag排序的"引用"代码.这是从Rosetta代码中删除的,但我对其进行了修改,使其符合提出的问题.这将采用2D方形矩阵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的矢量化和索引构造.

感谢您抽出时间阅读,期待您的回答!