Zig_Zag排列算法？？

Question

图象压缩用到的排列算法，或叫之字排列如下的矩阵：1         2       3       4   .......m
m+1       m+2     m+3     m+4 .......2m
.......................................
.......................................
(n-1)*m+1............................m*n 排列成：1   3    4    10   11   21..........
2   5    9    12   20...............
6   8    13   19....................
7   14   18.........................
15  17..............................
16   ...............................
...................................m*n算法，或者提供网上下载的地址

Answer 1

我看jpeg源码里面好像是定义一个相同大小的数组Z，数组里面依次存放zig-zag的次序
当你想按照次序读取的时候只要检查对应数组里的zig-zag的次序就可以了
比方说一个8*8矩阵(2维数组)，你想读取第三个zig-zag次序的元素，你检查Z数组第三个
值是(1,0)(从零开始），就读取原数组的(1,0）元素就可以，其他的依次类推就是了。
应该可以解决你的问题

Answer 2

这样的话，这个存放zig_zag次序的数组会不会也太大了一点。
因为处理的图象大小不一定，数组就需要设的非常大另外，这个zig-zag的次序数组的初值该如何去设呢？

Answer 3

jpeg里面是将图象分成一块块8*8的单位所以你也可以这样处理，不满8*8的就补齐，
zig-zag数组由于大小已经固定了(8*8)，所以它的值也是固定的，对应8*8象素矩阵的zig-zag次序是什么样的，它的值就是什么

Answer 4

那这么说，zig_zag只能是用于分块后的dct中咯？不知道你的jpeg源码可不可以发给我一份,多谢！[email protected]

Answer 5

对了，zig_zag的确只是用于分块后的dct,我手头上是jpeglib库，你在研究jpeg压缩算法？
已经给你发了，你自己看吧

Answer 6

如果你一定要算任意m*n的zig-zag，我有一些想法，但没有实现，希望对你有些帮助。假定矩阵A的下标是从[0][0]开始的，那么里边的任意一个元素A[i][j]在zig-zag序列中的位置应该
可以算出来的：
A[i][j] 是在矩阵中的第i+j+1斜行的，而从第一斜行到第i+j斜行的总元素个数是sum=
1＋2＋...+(i+j),
还知道奇数斜行是从右上到左下的，偶数行是从左下到右上的，所以如果是奇数行就
把sum加上j，系偶数行就加上i

呵呵，以上只是当i+j+1小于min(m,n)时的情况，
再往下你自己在仔细考虑吧，不好意思。

Answer 7

问题很简单，就是一维矩阵、一般二维矩阵、之字二维矩阵三者之间的转换算法。
现记含 n*m 个元素的一维矩阵为I ，你给出的第一个矩阵为T,第二个为Z,其中I(k)表示 I 中第 k+1 (k=0...n*m-1)个元素，T(n0,m0)、Z(n0,m0)分别表示 T、Z 中第n+1行第m+1列的元素(n0=0...n-1;m0=0...m-1)。
有了以上的定义就容易回答你的问题了，先给出几个简单的：
     一、I 与 T 之间的相互转换
               T(k/m,k%m)   = I(k) 
                I(m*n0+n0)  = T(n0,m0) 
     二、已知 Z ，求 T .
         (1)、当 n = m 时
              则
              ① 若 T(k)=Z(i,j)  则 T(n^2 - k - 1) = Z(n-i-1,n-j-1)
              ② 若 i+j < n 则：
                 当 i+j 是偶数时：
                   T((i+j)*(i+j+1)/2+1+j) = Z(i,j);
                 当 i+j 是奇数时：
                   T((i+j)*(i+j+1)/2+1+i) = Z(i,j);
              ③ 结合① 、② 则可以把 i+j >= n 的情形补齐。
            综上所述，我们可以得到由 Z 到 T 的转换算法
其余情形稍微复杂一点，今天太晚了，有空再讲。

Answer 8

睡不着觉，起来再做一题：
我前一贴中 二、（1）的逆，即当 n=m 时，已知T ，求Z         对于 T(k) , 令 a=int((1+sqrt(1+8*(k+1)))/2)-1;
             则：Z(2*a-k,k-a) = T(k)(a 是奇数时）
                 Z(k-a,2*a-k) = T(k)(a 是奇数时）
另外订正：上贴中 i+j 为奇数、偶数时的函数对调。

Answer 9

综合上面两贴，则能做出三种方阵间的任意转换，对于 T 跟 Z 间的转换可以通过 I 过度一下，很容易就能得到了。
至于非正方行的矩阵则需要讨论斜角去掉后的平行四边形区域，另外还要分 n<m 和 n>m 两种情形来讨论，比较复杂，先给出n<m 和 n>m 两种情形的转化关系吧，具体其中之一的算法今天恐怕给不出了。
已知 Z 求 T 的定理：
        当 n<m 且 i+j<n 时，若存在函数 k=f(i,j) 使得： 
 
                T(k)=T(f(i,j))=Z(i,j)         则,当n>m 且 i+j<m 时，有：
              
                T(k)=T(f(j,i))=Z(i,j)有了这个我们就可以只讨论 n<m 时的情形,而的情形则套用定理做个转置就行了

Answer 10

myheart8541_cn(i++) :收到了，回信了，提了个问题，弹出来的输入可执行文件名是什么
                      意思？bighead_lz(大头)： 谢谢算法，这种从斜行算的确能解决问题。
                   其实我是想在DCT后提取其中中频部分，所以排完左上角的就差不多了crazy_lazy_pig(疯狂懒猪)：呵呵，半夜写算法，可见你非常有激情的一个人啊。非常欣赏你
                          提出的模型。我给出的第一个矩阵是I，第二个是Z。所以我的问
                          题应该是I->T->Z  你的算法看得我头晕目眩啊，不过最终我还
                          是懂了，也是从斜边考虑的思想。感谢大家！

Answer 11

哦，对，你给出的第一个矩阵实际上是按一维阵来标号的，应该称之为I。今天说两个内容：1、n<m 时的准备定理。2、由I到Z的纯计算机算法。1、参见我第一贴的（二、），给出其第一句话的补充定理：假定 n<m ，对于 i+j<n
  当 m-n 为偶数时：
       若 T(k)=Z(i,j)  则 T(n^2 - k - 1) = Z(n-i-1,n-j-1) 
  当 m-n 为奇数时：
       若 T(k)=Z(i,j)  则 T(n^2 - k - 1) = Z(n-j-1,n-i-1)2、其实我给出的算法是数学上的一一对应的关系（也就是函数关系），做一个元素的变换是快的，但是如果把整个矩阵转换过去，恐怕就不是什么好办法了。不妨做个程序一点一点转换过去。算法如下：（1）、i=0; j=0; di=1; dj=-1;  //附初始值，其中i,j表示矩阵元素的行、列指标，di、dj
                               //表示i、j的增量。
       I(0)=Z(0,0);//当由Z到T时用此语句。
       [Z(0,0)=I(0);//当由T到Z时用此语句。]
（2）、k=1;
（3）、当 k < n*m-1 时循环执行（4）到（6）。
（4）、i+=di;j+=dj;
       if (i>n) //下面是之字形行列指标变化规则。
          {i-=di;j-=2*dj;di=-di;dj=-dj;}
          else if (j>m) 
                  {j-=dj;i-=2*di;di=-di;dj=-dj;}
                else if(i<0) 
                         {i-=di;di=-di;dj=-dj;}
                        else if(j<0) 
                             {j-=dj;di=-di;dj=-dj;}
（5）、I(k)=Z(i,j);//当由Z到T时用此语句。
       [Z(i,j)=I(k);//当由T到Z时用此语句。]
（6）、k++;
（7）、结束。这个算法即是按照之字规则遍历整个矩阵，同时也就遍历了I这个一维阵。既然能同时遍历两个矩阵，那么两矩阵间的转化就很容易了，只是等号左右边的问题了。另注：算法未经调试，有疏漏之处还请多多谅解。