zigzag掃描

Zigzag Scan是一種掃描矩陣的方法肝劲， 類似的還有光柵掃描等。大多用到圖像和視頻編碼中起惕。

snipaste_20180822_161737.png

H264中CAVLC編碼中崎淳，編碼一個4x4子塊的時候堪夭， 首先要對4x4子塊進行掃描， 得到一個一維序列拣凹， 之后計算非零系數(shù)和拖尾系數(shù)等森爽，
然后進行編碼。

CAVLC中使用Zigzag Scan的原因在于：

4x4塊在經(jīng)過變換嚣镜、量化之后爬迟， 非零系數(shù)主要在低頻部分（左上角）， 而高頻部分（右下角）大都是0菊匿。
使用zigzag掃描可以將非零系數(shù)較為集中的排列在一維序列的左邊付呕，
這樣可以減少Total Zeros计福、RunBefore、ZerosLeft的編碼徽职， 提高編碼效率棒搜。

下面是我自己寫的Zigzag Scan掃描程序

#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 128

typedef enum {
    MOVE_DOWN,
    MOVE_RIGHT,
    MOVE_RIGHT_UP,
    MOVE_LEFT_DOWN,
} MOVE_DIRECTION;

int zigzag_scan(int matrix[MAX_NUM][MAX_NUM], int x, int y, int *res) 
{
    int i, j;
    int move_dir = MOVE_RIGHT_UP;
    int *result = res;
    if (!result) {
        return 0;
    }

    i = j = 0;

    while (i < x && j < y) {
        *result = matrix[i][j];
        result ++;

        if (i == 0 && j < y -1) {
            move_dir = move_dir == MOVE_RIGHT_UP ? MOVE_RIGHT : MOVE_LEFT_DOWN;
        } else if (i == x-1 && j < y -1) {
            move_dir = move_dir == MOVE_LEFT_DOWN ? MOVE_RIGHT : MOVE_RIGHT_UP;
        }else if (j == 0 && i < x - 1) {
                move_dir = move_dir == MOVE_LEFT_DOWN ? MOVE_DOWN : MOVE_RIGHT_UP;
        } else if (j == y-1 && i < x-1) {
            move_dir = move_dir == MOVE_RIGHT_UP ? MOVE_DOWN : MOVE_LEFT_DOWN;
        }

        switch (move_dir) {
        case MOVE_DOWN:
            i ++;
            break;
        case MOVE_RIGHT:
            j ++;
            break;
        case MOVE_RIGHT_UP:
            i --;
            j ++;
            break;
        case MOVE_LEFT_DOWN:
            j --;
            i ++;
            break;
        default:
            break;
        }
    }
    return 1;
}

int main(int argc, char **argv)
{
    int matrix[MAX_NUM][MAX_NUM] = {{0, 3, 1, 0, 1}, 
                        {0, -1, 1, 0, 2}, 
                        {1, 0, 2, 0, 3}, 
                        {0, 1, 0, 1, 4}};
    int i;
    
    int *res = (int *)malloc(100 * sizeof(int));
    zigzag_scan(matrix, 4, 4, res);

    printf("print result ... ");
    for (i = 0; i < 20; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");

    return 0;
}