曲折扫描

曲折扫描

曲折扫描（英语：Zigzag scanning）是JPEG压缩技术的核心算法之一，输入三个64DCT系数DCTY、DCTCb、DCTCr后，输出三个曲折扫描矩阵DY、DCb、DCr，目的是将出现频率低的系数组合在一起。

介绍

JPEG影像压缩技术之所以使用曲折扫描的原因是，它能合理的期待在一个区块中的像素相较于在一条直在线的像素的出现频率会比较高，而出现频率高就代表能压缩的比例高。

例如，某个区块中的颜色都是不同深浅的蓝色，只需要存储该区块内不同像素的差异性而不必将区块内所有像素的一切资讯都保存，而更进一步的，这些差异值有可能会是0，或是一个非常小而可以视为0的差异。这样的技术允许图像或是影片能有更佳的压缩率。

另外在影片压缩技术的应用上，同样的颜色区块在连续的祯上很可能只有位移而并未改变区块中的像素内容，这样只需要保存该区块位移的位置即可。

例如，在影像A中某个区块已经被存储，而在影像B中该区块位移了(5, 5)的距离，则在影像B的存储上只需要纪录该区块的编号以及新的位置即可，如此就能达到压缩的目的。

使用曲折扫描技术也有其会松散压缩的缺点，假如影片或图像没有足够的可用位元来精确的保存资讯，则在部分的图像上可能会出现类似马赛克一般的方形色块，这个在压缩技术的术语上被称为宏区块。

代码

/**
 * traverses m*n grid in zigzag order
 */
void traverseZigZag(int m, int n) {
 
    int i = 0, j = 0, up=1;
    bool turned = false;
    int d[2][2] = { { 1, -1 }, { -1, 1 } };
    int corner[2][4] = { { 1, 0, 0, 1 }, { 0, 1, 1, 0 } };
    while (i < m && j < n) {
        //here you have your (i,j), do what you want with them.
        printf("%d %d\n",i,j);
        if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
            if (!turned) {
                int k = 2 * (up * (j / (n - 1)) | (1 - up) * (i / (m - 1)));
                i += corner[up][k];
                j += corner[up][k + 1];
                turned = true;
                up = 1 - up;
                continue;
            } else
                turned = false;
        }
        i += d[up][0];
        j += d[up][1];
    }
}

引用来源