량적으로 비교하여라.
(solution)
Chen 알고리즘의 DCT 결과 IDCT로 복원 영상
1D DCT
8x8 DCT의 경우, 마스크가 2D로 적용되기 때문에, 2D 영상을 순회하면서 2D 필터를 적용하는 형태즉, O(N4)의 복잡도를 지닌다. DCT의 경우 x축 방향의 연산과 y측 방향의 연산이 직교적(orthogonal)이기 때문에 2D 연산을 1D의 독립된 연산의 반복으로 수행하여도 동일한 결과를 얻을수 있다. 2D 마스크를 적용하는 것 대신 1D DCT를 이용하면 복잡도가 감소한다.
Chen algorithm
DCT는 이름에서도 알 수 있듯이, 코사인 함수를 이용하여 변환의 기저(basis)를 생성한다. 따라서 DCT에 사용되는 계수들도 모두 코사인 함수에서 비롯되는데, DCT는 대칭성을 가지고 있어 반복되는 연산의 양을 줄일 수 있다. (N x N) x (N x 1)의 행렬 연산을 (N/2 x N/2) x (N/2 x 1)의 행렬 연산으로 변환하여 계산량을 줄여준다.
위 그림은 1D DCT 및 Chen 알고리듬을 적용한 결과와 IDCT를 적용하여 복원한 영상이다
6. 8x8 DCT를 고정 소수점 방식으로 구현했을 때, 발생할 수 있는 오차에 대하여 기술하고, 오차를 최소화할 수 있는 방법을 제시하여라.
(solution)
고정 소수점 DCT를 적용한 결과 고정 소수점 IDCT를 적용한 결과
고정 소수점 방식으로 구현하면, 컴퓨터에서 표현할 수 없는 범위에서의 계산이 발생할 경우 에러가 생길 수 있는 여지가 많다. 위의 오른쪽 그림은 고정 소수점 DCT의 결과에 Inverse DCT를 한 것으로, 에러가 많이 존재하여 몇 군데는 눈에 보이기까지 한다.
이러한 문제를 해결하기 위해서는, 소수점 이하에서의 계산에러를 보완하기 위해 DCT 계산 이전에 표현 가능한 범위 내에서 계산에 적용되는 모든 숫자에 큰 수를 곱해주었다가 계산이 끝난 후 다시 같은 수로 나누어 주는 방식을 사용한다. 이렇게 하면 소수점 이하에서 이루어지는 계산이 줄어들게 되어, 결과에 에러가 생기는 문제를 어느 정도 해결할 수 있다.
또한, 애초에 에러가 발생하지 않는 새로운 변환 방법을 사용하는 경우도 있다. H.264/AVC 비디오 코덱에서는 DCT 대신 Integer Transform을 사용하는데, 이는 변환 자체가 에러가 발생하지 않는 정수 계수와 덧셈 뺄셈 Shift 연산 등으로만 이루어져 있어 에러가 발생하지 않는다.