ZigZag Scan

1. 소스 코드

ZigZag Scan은 MPEG에서 DCT 후에 수행되는 매우 중요한 동작 중에 하나이다. 대학원에 있을 때, 

교수님이 과제를 내 주었던 것 같은데, 남이 해 놓은 거 배껴서 냈는데 이제 해 보려니 잘 안되네.

해보게 된 동기는 https://www.acmicpc.net/problem/1193 <분수찾기> 문제를 풀다보니 의욕이 생겼다.

다음 블로그를 보니 잘 짜 놓은 신듯 http://kama1204.tistory.com/m/112

다만 위의 블로그의 대략적인 복자도는 O(N^2) 인 것으로 보인다. 아래 내가 짠 소스는 어찌하다 보니

O(N)으로 만들어진 것 같다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <iostream>   #define N 8   int array[N][N];   void display() {     std::printf("\n");     for(int i = 0; i < N; i++)     {         for(int j = 0; j < N; j++)         {             std::printf("%2d ", array[i][j]);         }         std::printf("\n\n");     } }   void zig_zag_scan() {     int n = 1;     int x = 0;     int y = 0;       for(int idx = 0, d = 1; idx <= 2*(N-1); idx++, d *= (-1))     {         if(idx <= N-1)         {             if(d == 1)             {                 y = idx;                 x = idx - y;             }             else             {                 x = idx;                 y = idx - x;             }         }         else         {             if(d == 1)             {                 x = idx - (N-1);                 y = idx - x;             }             else             {                 y = idx - (N-1);                 x = idx - y;             }         }           //std::printf("%d, %d, %d, %d, \n", idx, x, y, d);         for(; x >= 0 && y >= 0 && x < N && y < N; x = x + d, y = y - d)         {             array[y][x] = n++;         }           } }   int main() {     zig_zag_scan();     display();       return 0; }

2. 실행결과

3X3 행렬에 대한 동작이다. 다른 값에 대해서도 잘 동작한다.

대만에서 쓴 논문을 보니 ZigZag Scan을 FPG로 속도 개선하기 위해서 쓴 논문도 있었던 것 같다.

 1  2  6 

 3  5  7 

 4  8  9 

3. 소스 코드

달팽이 Scan도 도전해 보았다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

void snail_scan() {     int x = 0;     int y = 0;        for(int i = 0, idx = 0; i < N*N; idx++)     {         for(x = idx, y = idx; x < (N - idx) ; x++)         {             array[y][x] = ++i;             //std::printf("1. %d, %d, %d \n", x, y, i);         }           for(x = x - 1, y = y + 1; y < (N - idx) ; y++)         {             //std::printf("2. %d, %d, %d \n", x, y, i);             array[y][x] = ++i;         }           for(x = x - 1, y = y - 1; x >= idx ; x--)         {             //std::printf("3. %d, %d \n", x, y);             array[y][x] = ++i;         }                   for(x = x + 1, y = y - 1; y > idx ; y--)         {             array[y][x] = ++i;         }     }   }   int main() {     //zig_zag_scan();     //vertical_scan();     snail_scan();     display();        return 0; }

4. 실행결과

 1  2  3  4  5 

16 17 18 19  6 

15 24 25 20  7 

14 23 22 21  8 

13 12 11 10  9