ZigZag Scan

1. 소스 코드

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

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

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

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

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

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

#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도 도전해 보았다.

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