曲折掃描

曲折掃描

曲折掃描（英語：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];
    }
}

引用來源