메뉴펼치기
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
해당 자료는 3페이지 까지만 미리보기를 제공합니다.
3페이지 이후부터 다운로드 후 확인할 수 있습니다.
3페이지 이후부터 다운로드 후 확인할 수 있습니다.
목차
1. Explain the relationship between DCT and DFT. Explain FFT(Fast Fourier Transform) and block-DCT which are widely used in many signal processing applications. Describe the merits and demerits of block-DCT compared to DCT
2. Explain aliasing phenomenon, blocking artifact and ringing artifact. Explain why the ringing effect occurs when using the frequency domain filter while it does not occur when using the spatial domain filter.
3. Investigate still image compression standards (JPEG, JPEG2000) and summary their characteristics.
4. Investigate the video compression techniques and describe the difference between the still image compression and video compression.
5. Investigate the quantization process in signal processing.
2. Explain aliasing phenomenon, blocking artifact and ringing artifact. Explain why the ringing effect occurs when using the frequency domain filter while it does not occur when using the spatial domain filter.
3. Investigate still image compression standards (JPEG, JPEG2000) and summary their characteristics.
4. Investigate the video compression techniques and describe the difference between the still image compression and video compression.
5. Investigate the quantization process in signal processing.
본문내용
1. Explain the relationship between DCT and DFT. Explain FFT(Fast Fourier Transform) and block-DCT which are widely used in many signal processing applications. Describe the merits and demerits of block-DCT compared to DCT.
①DCT와 DFT의 관계
DCT는 기본적으로 DFT에서 파생되었지만, 몇 가지 차이점을 보인다. 우선, DFT가 Real값과 Imaginary를 가지는 Complex의 형태로 나타나는 것에 비해서 DCT는 cosine값으로 나타나는 Real값만을 다루기 때문에 연산량이 적고, 그래프로 표시하기가 수월하다.
DFT에서 DCT를 유도하는 방법은, 아래의 식과 같다.
2N-point DFT에서 실수영역 부분만 고려해서 DCT 얻는 것은 아래와 같이 하면 된다.
DCT는 단지 실수로만 구성되어 있기 때문에, DFT는 DCT를 mirroring 한 것과 같은 형상을 가진다. 여기서 DFT는 실수 부분과 허수 부분을 모두 가지고 있는 복소수 형태이다. 그리고 even-symmetry를 갖는 data에 적용되어, DCT를 mirroring하여 DFT를 얻는다.
②FFT (Fast Fourier Transform)
DFT를 구현하는데 있어서 N개의 sample에 대해 하나당 N번의 연산을 해야 하므로 O(N^2)의 complexity가 요구된다. 본 실험에서는 256*256 size의 image를 다루므로 많은 양의 sample에 대해서 연산을 수행해야 한다. Image의 경우 DFT가 x축, y축으로 각각 한 번씩 해야 하므로 가로세로 sample의 수가 같다면 총 O(N^4)의 complexity가 요구된다.
이런 비효율적인 문제를 해결하기 위해 제안된 알고리즘이 FFT이다. FFT는 N개의 sample을 작은 단위로 잘라서 연산을 한 후에 그것을 다시 합치는 Divide & Conquer방식에 기초하고 있다. FFT의 경우에는 1D의 연산이 N log_2N만에 연산이 가능하다. Image의 경우 N=256이면 O(N^2 log_2N)만에 연산이 가능하다. FFT는 다음과 같이 유도된다.
X(k)=∑_(n=-0)^(N-1)▒〖x[n]exp(-j 2πkn/N〗)=∑_(n=-0)^(N-1)▒〖x[n] 〖W_N〗^kn 〗 (∵W_N=exp(-j 2π/N))
=∑_(n=0)^(N/2-1)▒〖x[2n] 〖W_N〗^(k(2n)) 〗+ ∑_(n=0)^(N/2-1)▒〖x[2n+1] 〖W_N〗^k(2n+1) =∑_(n=0)^(N/2-1)▒〖f_even [n] 〖W_(N/2)〗^kn 〗+ ∑_(n=0)^(N/2-1)▒〖f_odd [n] 〖W_(N/2)〗^kn 〖W_N〗^k 〗 〗
(∵〖W_N〗^k(2n+1) =〖W_N〗^k(2n) 〖W_N〗^k=exp〖(-j 2π/N k2n) 〖W_N〗^k 〗=exp〖(-j 2π/(N/2) kn) 〖W_N〗^k 〗=〖W_(N/2)〗^kn 〖W_N〗^k)
=F_even (k)+〖W_N〗^k F_odd (k)
Even term과 Odd term으로 나뉘는데 결국 하나의 DFT가 두 개의 DFT의 합으로 이루어진다. 이것을 반복하면 결국 하나의 DFT가 N개의 DFT의 합으로 이루어지고, 다시 합치는 데에 O( log_2N)의 연산이 수행된다. 이것을 그림으로 표현하면 다음과 같다.
위와 같은 Butterfly graph를 얻는데 필요한 것이 DFT의 Periodic한 성질이다.
X(k+N/2)=F_even (k+N/2)+〖W_N〗^(k+N/2) F_odd (k+N/2)=F_even (k)+〖W_N〗^k 〖W_N〗^(N/2) F_odd (k)
=F_even (k)-〖W_N〗^k F_odd (k)
①DCT와 DFT의 관계
DCT는 기본적으로 DFT에서 파생되었지만, 몇 가지 차이점을 보인다. 우선, DFT가 Real값과 Imaginary를 가지는 Complex의 형태로 나타나는 것에 비해서 DCT는 cosine값으로 나타나는 Real값만을 다루기 때문에 연산량이 적고, 그래프로 표시하기가 수월하다.
DFT에서 DCT를 유도하는 방법은, 아래의 식과 같다.
2N-point DFT에서 실수영역 부분만 고려해서 DCT 얻는 것은 아래와 같이 하면 된다.
DCT는 단지 실수로만 구성되어 있기 때문에, DFT는 DCT를 mirroring 한 것과 같은 형상을 가진다. 여기서 DFT는 실수 부분과 허수 부분을 모두 가지고 있는 복소수 형태이다. 그리고 even-symmetry를 갖는 data에 적용되어, DCT를 mirroring하여 DFT를 얻는다.
②FFT (Fast Fourier Transform)
DFT를 구현하는데 있어서 N개의 sample에 대해 하나당 N번의 연산을 해야 하므로 O(N^2)의 complexity가 요구된다. 본 실험에서는 256*256 size의 image를 다루므로 많은 양의 sample에 대해서 연산을 수행해야 한다. Image의 경우 DFT가 x축, y축으로 각각 한 번씩 해야 하므로 가로세로 sample의 수가 같다면 총 O(N^4)의 complexity가 요구된다.
이런 비효율적인 문제를 해결하기 위해 제안된 알고리즘이 FFT이다. FFT는 N개의 sample을 작은 단위로 잘라서 연산을 한 후에 그것을 다시 합치는 Divide & Conquer방식에 기초하고 있다. FFT의 경우에는 1D의 연산이 N log_2N만에 연산이 가능하다. Image의 경우 N=256이면 O(N^2 log_2N)만에 연산이 가능하다. FFT는 다음과 같이 유도된다.
X(k)=∑_(n=-0)^(N-1)▒〖x[n]exp(-j 2πkn/N〗)=∑_(n=-0)^(N-1)▒〖x[n] 〖W_N〗^kn 〗 (∵W_N=exp(-j 2π/N))
=∑_(n=0)^(N/2-1)▒〖x[2n] 〖W_N〗^(k(2n)) 〗+ ∑_(n=0)^(N/2-1)▒〖x[2n+1] 〖W_N〗^k(2n+1) =∑_(n=0)^(N/2-1)▒〖f_even [n] 〖W_(N/2)〗^kn 〗+ ∑_(n=0)^(N/2-1)▒〖f_odd [n] 〖W_(N/2)〗^kn 〖W_N〗^k 〗 〗
(∵〖W_N〗^k(2n+1) =〖W_N〗^k(2n) 〖W_N〗^k=exp〖(-j 2π/N k2n) 〖W_N〗^k 〗=exp〖(-j 2π/(N/2) kn) 〖W_N〗^k 〗=〖W_(N/2)〗^kn 〖W_N〗^k)
=F_even (k)+〖W_N〗^k F_odd (k)
Even term과 Odd term으로 나뉘는데 결국 하나의 DFT가 두 개의 DFT의 합으로 이루어진다. 이것을 반복하면 결국 하나의 DFT가 N개의 DFT의 합으로 이루어지고, 다시 합치는 데에 O( log_2N)의 연산이 수행된다. 이것을 그림으로 표현하면 다음과 같다.
위와 같은 Butterfly graph를 얻는데 필요한 것이 DFT의 Periodic한 성질이다.
X(k+N/2)=F_even (k+N/2)+〖W_N〗^(k+N/2) F_odd (k+N/2)=F_even (k)+〖W_N〗^k 〖W_N〗^(N/2) F_odd (k)
=F_even (k)-〖W_N〗^k F_odd (k)
- 가격3,000원
- 페이지수10페이지
- 등록일2010.05.28
- 저작시기2010.4
- 파일형식기타(docx)
- 자료번호#615212
본 자료는 최근 2주간 다운받은 회원이 없습니다.
소개글