Zig-zag Scanning

Zig-zag Scanning은 2D Array의 Traversal 방법 중 하나로, 원소를 접근함에 있어 아래와 같이 지그재그 순으로 접근하는 기법입니다. 해당 Traversal 방법은 영상 압축 과정에서 주로 쓰입니다. 관련 내용으로 [H.264] Quantization(양자화)과 Zig-zag scanning 을 참고해보시면 도움이 될 것 같습니다.

 

source: wikipedia

위 그림을 보며 원소 접근 방식을 분석해보면 중간중간 방향을 전환하는 분기점이 존재합니다. 그리고, 분기점의 y, x 위치(행렬로 치면 행, 열)에 따라 하향 혹은 우향 방향에 존재하는 원소를 한 번 접근한다음 좌하향 대각선 방향 혹은 우상향 대각선 방향으로 원소를 쭈욱 접근 하는 규칙을 가지고 있음을 확인할 수 있습니다.

 

C++을 이용하여 이를 구현해보았습니다.

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<vector<int>> scan_order_table(n, vector<int>(n, 0));
    scan_order_table[0][0] = 1;//order 1부터 numbering

    for(int order = 2, y = 0, x = 0, dir = 1; order <= n * n;)
    {
    	//분기점에서 하향 혹은 우향 방향으로 y, x 이동
        if(x == n-1) y += 1;
        else if(y == n-1) x += 1;
        else if(y == 0) x += 1;
        else if(x == 0) y += 1;

        while(y >= 0 and x >= 0 and y <= n-1 and x <= n-1)
        {
            scan_order_table[y][x] = order++;
            
            //dir=1이면 좌하향 방향으로 순서 증가, dir=-1이면 우상향 대각선으로 순서 증가
            y += dir;
            x -= dir;
        }

        //위 반복문을 거치면 y와 x가 array size를 벗어나게 되므로 이를 역으로 보상해주어야함
        y -= dir;
        x += dir;

        //방향 반전
        dir = -dir;
    }

    for(int y = 0; y < n; y++)
    {
        for(int x = 0; x < n; x++)
        {
            cout << scan_order_table[y][x] << " ";
        }
        cout << "\n";
    }

    return 0;
}

실행 결과 예시

n == 1

1

 

n == 2

1 2

3 4

 

n == 3

1 2 6

3 5 7

4 8 9