Chapter 8 손실 압축 기법 8.1 소개 8.2 왜곡측정 8.3 빈도 왜곡 이론 8.4 양자화 8.5 변환 부호화

Presentation on theme: "Chapter 8 손실 압축 기법 8.1 소개 8.2 왜곡측정 8.3 빈도 왜곡 이론 8.4 양자화 8.5 변환 부호화"— Presentation transcript:

1 Chapter 8 손실 압축 기법 8.1 소개 8.2 왜곡측정 8.3 빈도 왜곡 이론 8.4 양자화 8.5 변환 부호화
8.6 웨이블릿 기반 부호화 8.7 웨이블릿군 8.8 웨이블릿 계수의 내장 제로트리 8.9 계층적 트리에서 부분별로 나누기(SPIHT) 멀티미디어시스템 2011-2학기

2 8.1 소 개 무손실 압축 알고리즘은 충분히 높은 압축률을 제공하지 못한다. 따라서 대부분의 멀티미디어 압축 알고리즘은 손실이다. 손실압축 이란? - 압축된 데이터는 원래 데이터와 동일하지 않지만, 매우 근사한 값을 가진다. - 무손실 압축보다 훨씬 높은 압축률을 가진다. 멀티미디어시스템 2011-2학기

3 8.2 왜곡 측정 영상 압축에서 주로 사용되는 세 가지 왜곡측정 기법은 다음과 같다: - 평균 제곱 오차(MSE) σ2,
여기서 xn과 yn, N은 입력 데이터열, 복원데이터열, 데이터열의 길이를 나타낸다. - 신호 대 잡음비(SNR), 데시벨 단위(dB)로 표현되어, 여기서 σx2은 원래데이터열의 평균 제곱값이고, σd2는 MSE이다. - 최대 신호 대 잡음비(PSNR), 멀티미디어시스템 2011-2학기

4 8.3 빈도-왜곡 이론 빈도와 왜곡간의 타협에 대한 근간이 된다. 빈도: 각 기호를 표현하는데 필요한 평균 비트 수
R(D): 왜곡함수 D: 왜곡 D=0, 즉 무손실에서 가능한 최소 빈도는 원천 데이터의 엔트로피가 된다. 그림 8.1 멀티미디어시스템 2011-2학기

5 8.4 양자화 출력 값을 훨씬 적은 수의 값들로 줄인다. 손실 압축에서 “손실”의 주요 요인이다. 세 가지 양자화의 종류
- 균일 : 미드라이즈와 미드트레드 양자화기 - 비균일 : 컴팬드 양자화 - 벡터 양자화 멀티미디어시스템 2011-2학기

6 균일 스칼라 양자화 균일 스칼라 양자화는 양단 바깥영역을 제외하고는 입력 값들을 균일하게 분할된 구간으로 할당한다.
- 각 구간에 해당하는 출력값 또는 재건값은 구간의 중심값으로 취해진다. - 각 구간의 길이는 단계크기라고 부르고 기호 ∆로 표시한다. 균일 스칼라 양자화기의 두 가지 형태 - 미드라이즈 양자화기는 출력으로 짝수개의 단계를 가짐. - 미드트레드 양자화기는 홀수개의 단계를 가지며, 0을 포함한다.(그림 8.2) 멀티미디어시스템 2011-2학기

7 특별히 ∆=1 인 경우에는 이러한 양자화기에 대한 출력값들 다음과 같이 간단히 계산할 수 있다.
M 단계 양자화기의 성능을 살펴보자. B={b0,b1,…,bM}을 결정경계로하고,Y={y1,y2,…,yM}을 출력값 또는 재건값이라고 하자. 구간 에 균일하게 분포하는 입력을 생각해보자. 양자화기의 빈도는 다음과 같다. 멀티미디어시스템 2011-2학기

8 균일 스칼라 양자화기: (a) 미드라이즈 (b) 미드트레드
그림 8.2 멀티미디어시스템 2011-2학기

9 균일 분포 특성의 원천 신호에 대한 양자화 오차 낟알무늬 왜곡 : 제한된 값을 가지는 입력에 대한 양자화기에 의한 양자화 오차
- 낟알무늬 왜곡에 대한 전반적인 특성을 파악하기 위해서, 미드라이즈 양자화기에서의 결정경계 bi는 [(i-1)∆,i∆], i =1...M/2 로서 양수의 데이터 X를 표현한다.(다른 반구간은 음수 X로 대응) - 양수 데이터에 대해 생각하면, 출력값 yi는 중간값 i∆-∆/2, i =1...M/2이 되는 것이다. 전체 왜곡은 양수 데이터 전반에서의 합에 두 배를 한 것이다. 재건값 yi은 각 구간의 중간값이므로, 양자화 오차는 분명히 [-∆/2, ∆/2] 사이의 값이다. 그림 8.3은 균일하게 분포한 원천 신호에 대한 양자화 오차의 그래프이다. 멀티미디어시스템 2011-2학기

10 균일하게 분포한 원천 신호에 대한 양자화 오차의 그래프
그림 8.3 멀티미디어시스템 2011-2학기

11 8.4.2 비균일 스칼라 양자화 만약 입력이 균일하지 않을 경우, 균일 양자화기는 효율적이지 못할 수 있다.
비균일 양자화기: 로이드-맥스 양자화, 컴팬드 양자화 로이드-맥스 양자화 신호의 분포가 균일하지 않으면 확률 분포(확률 밀도 함수) fx(x)를 고려해야 한다. 정확한 결정 경계 bi, 재건값 yi 를 총 왜곡 측정에 포함시킨다. 식 8.12 참고 컴팬드 양자화 입력이 압축기 함수 G 에 의해 사상되고, 균일 양자화를 이용하여 양자화가 이루어진다. 전송이 이루어진 후에는 양자화된 값이 확장자 함수 G-1을 이용하여 역사상이 이루어진다. 멀티미디어시스템 2011-2학기

12 위 그림과 같이 컴팬더는 압축기 함수 G, 균일 양자화기와 확장자 함수 G-1을 이용한다.
컴팬드 양자화 그림 8.4 컴팬드 양자화는 비선형이다. 위 그림과 같이 컴팬더는 압축기 함수 G, 균일 양자화기와 확장자 함수 G-1을 이용한다. 두 가지 널리 쓰이는 것은 μ-law와 A-law 컴팬드 양자화이다. 멀티미디어시스템 2011-2학기

13 8.4.3 벡터 양자화(VQ) 정보이론을 다룬 Shannon의 이론에 따르면, 압축이 개별적인 기호나 샘플이 아닌 벡터나 샘플의 집합의 단위로 수행될 때 압축 시스템이 더 좋은 성능을 보일 수 있다. 연속된 샘플을 단일 벡터로 묶음으로써 입력 샘플에 대한 벡터를 생성할 수 있다. 벡터 양자화는 스칼라 양자화와 비슷하나 다중 차원으로 확장된 것이다. 스칼라 양자화에서는 하나의 재건값을 대상으로 하지만, VQ에서는 n 성분을 가지는 코드 벡터가 사용된다. 이러한 코드 벡터의 집합이 코드북 을 형성한다. 멀티미디어시스템 2011-2학기

14 그림 8.5 - 부호화기는 입력 벡터에 가까운 코드 벡터를 찾아내고, 출력은 관련된 인덱스가 된다.
- 복호화기는 부호화된 인덱스기가 수신되면 단순히 표를 참조하여 벡터를 재건한다. 그림 8.5 멀티미디어시스템 2011-2학기

15 적당한 코드북을 찾고 부호화기 단에서 가장 가까운 코드 벡터를 검색하는 것은 계산량이 소요되고, 복호화기에서는 빠르게 수행
VQ 는 부호화기 단에는 고성능의 시스템을 가지고 있고, 복호화기 단에는 제한된 성능만을 가지고 있어서 빠른 수행을 요구하는 경우에 좋다. 멀티미디어시스템 2011-2학기

16 8.5 변환 부호화 입력 데이터가 정지 영상, 음악, 오디오, 비디오의 경우에는 인접한 샘플들 xi 간에 상당한 상호 관련성이 있다. 변환이론의 근간 이론 만약 Y가 입력 벡터 X에 대한 선형 변환 T의 결과라고 하면, 이때 Y의 요소들은 상대적으로 훨씬 적은 상호 관련성을 가지게 되고, Y는 X보다 더 효율적으로 부호화할 수 있게 된다. 대부분의 정보는 변환된 벡터의 처음 몇 개의 성분에 의해 정확히 표현될 수 있다면, 나머지 성분들은 성기게 양자화될 수 있고, 심지어 0으로 놓아도 신호의 왜곡은 아주 미미할 것이다. 우선 이산 여현 변환(DCT)에 대해 알아보고, 입력 X의 성분을 최적으로 분해하는 Karhunen-Loeve 변환(KLT)에 대해 알아본다. 멀티미디어시스템 2011-2학기

17 8.5.1 DCT (Discrete Cosine Transform): 이산 여현 변환
데이터 독립적인 방법으로 입력 신호의 역상관화를 수행하는 변환 부호화 기법 공간 주파수는 영상 블록간에 화소값의 변화가 얼마나 자주 일어나는가를 의미한다. DCT는 이러한 개념을 블록당 구형파의 주기에 해당하는 영상 정보의 변화 정도로서 표현한다. DCT는 원래 신호를 DC와 AC 성분으로 분해한다. : IDCT는 신호를 복원한다. 멀티미디어시스템 2011-2학기

18 DCT의 정의 : 두 개의 정수 값 i, j에 의해 표현된 함수 (한 정지 영상)가 주어졌을 때 2D DCT 변환은 이 함수를 i와 j와 동일한 범위를 가지는 정수 u, v로 표현되는 새로운 함수 로 변환한다. 이 변환의 일반적인 정의는 다음과 같다. 여기서 i, u = 0,1,...,M-1, j, v = 0,1,...,N-1이고, 상수 C(u)와 C(v)는 다음과 같다. 멀티미디어시스템 2011-2학기

19 2D 이산 여현 변환(2D DCT) 2D 역 이산 여현 변환(2D IDCT)
- JPEG 영상 압축 표준에서 영상 블록은 차원 M=N=8 로 정의 - 여기서 i, j, u, v = 0,1,...,7이고 상수 C(u), C(v)는 식 (8.16)과 같다. 2D 역 이산 여현 변환(2D IDCT) 역 함수는 거의 동일하며 f(i,j)와 F(u,v)가 뒤바뀐 형태인데, 단지 C(u)C(v)가 합산 내부에 포함된다. 여기서 i, j, u, v = 0,1,...,7 이다. - 2차원 변환은 디지털 영상과 같은 2차원 신호에 적용된다. 멀티미디어시스템 2011-2학기

20 1D 이산 여현 변환(1D DCT) 1D 역 이산 여현 변환(1D IDCT) 여기서 i, u = 0,1,...,7이다.
멀티미디어시스템 2011-2학기

21 1차원 DCT 1차원 신호의 DCT 는 2차원 DCT의 확장 개념이다. 상수 크기를 가지는 전기 신호는 DC (직류)
일정 주기로 크기가 변하는 전기 신호는 AC (교류) 음성 신호나 디지털 이미지에서의 회색계 밝기의 행은 1차원 신호의 예 어떠한 경우의 신호라도 다양한 크기와 주파수를 가지는 여현(코사인) 파들의 합으로 표현될 수 있다. 신호의 AC 와 DC 성분의 크기를 결정하는 과정을 여현 변환이라고 하며, 정수 계에 대한 것으로 이산 여현 변환이라고 부른다. 식 8.19 에서 u=0 이면 DC 계수를 얻고, u = 1, .., 7 까지 변화시킬 때 AC 계수를 얻는다. DCT 의 역할은 원천 신호를 DC 와 AC 로 분해하는 것이다. IDCT 역할은 신호를 복원하는 것이다. DCT와 IDCT는 동일한 여현 함수를 사용한다. 1차원 DCT 변환은 시공간의 신호 f(i)를 주파수 공간의 신호 F(u)로 변환한다. F(u)는 주파수 응답이고, f(i)의 주파수 스펙트럼 구성. 멀티미디어시스템 2011-2학기

22 그림 8.6  8개의 1차원 DCT 기저함수군 표현 멀티미디어시스템 2011-2학기

23 그림 8.6 (cont’d) 멀티미디어시스템 2011-2학기

24 그림 8.7  주파수 응답의 예 멀티미디어시스템 2011-2학기

25 그림 8.7 (cont’d) 멀티미디어시스템 2011-2학기

26 그림 8.8  역 DCT(IDCT) 예 멀티미디어시스템 2011-2학기

27 그림 8.8 (cont’d) 멀티미디어시스템 2011-2학기

28 DCT의 성질 1. DCT는 공간 신호 f(i)에 대응하는 주파수 스펙트럼 F(u)를 생성한다.
여기서 α와 β는 상수이며, p와 q는 어떠한 함수나 변수 혹은 상수이다. 식 (8.19)에서의 정의로부터, 이러한 성질은 DCT가 단순 산술 연산만을 사용하기 때문에 쉽게 증명될 수 있다. 멀티미디어시스템 2011-2학기

29 여현 기저 함수들 함수 Bp(i)와 Bq(i)는 다음을 만족할 때 직교한다. 직교할 때 중복성이 가장 작음
또한 다음과 같은 사실을 확인할 수 있다. 멀티미디어시스템 2011-2학기

30 2차원 DCT 함수에 대해 8x8 영상으로 보인 기저를 사용한다.
2차원 기저함수들 2차원 DCT 함수에 대해 8x8 영상으로 보인 기저를 사용한다. 그림 8.9에서 흰색은 양수를 의미하고 검은색은 음수를 의미한다. DCT 계수를 얻기 위해서는 원 영상에서 8x8 블록에 대하여 이 64개의 기저 영상을 각각 내적한다 64개의 곱의 계산을 통해 8x8 공간 주파수 영상 F(u, v)를 만들 수 있다. 멀티미디어시스템 2011-2학기

31 흰색은 양수, 검은색은 음수를 의미 그림 8.9 멀티미디어시스템 2011-2학기

32 2D 구분 가능한 기저 2D DCT 는 1D DCT를 두 단계로 구분하여 수행할 수 있다.
이 간단한 방법이 많은 연산 단계를 줄이는 것을 쉽게 알 수 있다. 반복 횟수는 8×8에서 8+8로 줄게 되는 것이다. 멀티미디어시스템 2011-2학기

33 DCT와 DFT 비교 이산 여현 변환[4]은 이산 푸리에 변환(DFT)와 매우 유사하다. DCT는 DFT의 실수 부분에 국한된 변환이다. 연속 신호에 대해서는 연속 푸리에 변환 ℱ 는 다음과 같이 정의된다. 디지털 컴퓨터는 입력신호를 이산화하여야 받아들일 수 있으므로, 입력신호 {f0, f1, , f7}에 대해 다음과 같이 DFT는 다음과 같이 정의 된다: 멀티미디어시스템 2011-2학기

34 사인과 코사인 부분을 분리하면 다음과 같이 표시할 수 있다.
DFT의 실수 부분만을 사용하도록 한 DCT를 고안한 배경에는 원천 입력 신호를 대칭적으로 복사함으로써 DFT의 허수부분을 제거할 수 있다는 통찰에 의한 것이다. 8개의 입력 샘플들에 대한 DCT는 그림 8.10에서와 같이 이 샘플들을 대칭적으로 복사하여 만든 16개의 샘플에 대한 DFT에 대응한다. 멀티미디어시스템 2011-2학기

35 그림 8.10 멀티미디어시스템 2011-2학기

36 DCT와 DFT의 간단한 비교 표 8.1과 그림 8.11에서 경사 함수에 대한 DCT와 DFT를 처음 3개의 성분만을 고려할 경우에 대해 비교하고 있다. 표 8.1 멀티미디어시스템 2011-2학기

37 경사함수의 근사화: (a) 세 개 성분의 DCT 근사화, (b) 세 개 성분의 DFT 근사화
그림 8.11 멀티미디어시스템 2011-2학기

38 Karhuene-Loeve 변환(KLT)
이 변환은 입력 신호를 상호연관성이 없는 성분으로 가장 최적화된 형태로 분해할 수 있다 KLT의 최적성을 이해하기 위해 다음과 같이 정의된 입력 벡터 X의 자기상관 행렬 Rx를 생각해보자. 멀티미디어시스템 2011-2학기

39 여기서 Karhenen-Loeve 변환을 다음과 같이 정의할 수 있다.
우리의 목적은 출력 Y의 성분이 상관성이 없도록 하는 변환 T를 구하는 것이다. 즉, t≠s에서 E[YtYs]=0. 이처럼 Y의 자기상환 행렬은 양의 대각행렬의 형태를 취한다. 어떤 자기 상관 행렬은 대칭이고 음이 아니면서 제한된 형태이므로, k개의 직교 고유벡터 u1,u2,…uk와 k 개의 실수이고 음이 아닌 고유값 λ1≥λ2 ≥ λk ≥ 0을 가진다. 여기서 Karhenen-Loeve 변환을 다음과 같이 정의할 수 있다. 그리고, Y의 자기상관 행렬은 다음과 같이 된다. 멀티미디어시스템 2011-2학기

40 KLT 예제 KLT의 구조를 설명하기 위해, 4개의 3D 입력 벡터 x1=(4,4,5), x2=(3,2,5), x3=(5,7,6), x4=(6,7,7) 을 생각해보자. 평균 예측 입력에 대한 자기상관 행렬 예측 멀티미디어시스템 2011-2학기

41 Rx의 고유값은 λ1=6.1963, λ2=0.2147, λ3=0.0264이다. 대응하는 고유벡터는,
KLT는 다음 행렬로 주어진다. 멀티미디어시스템 2011-2학기

42 각 입력 벡터로부터 평균 벡터를 빼고, KLT를 적용하면 다음을 얻는다.
T의 행들은 정규직교 벡터들이므로, 역 변환은 단순히 전치시키면 된다. : T-1= TT. 그리고, 일반적으로, KLT 이후에 변환 계수의 대부분의 “에너지”는 첫 번째 몇 개의 성분에 집중되게 된다. 이것이 KLT의 에너지 집중 성질이다. 멀티미디어시스템 2011-2학기

43 8.6 웨이블릿 기반 부호화 입력 신호를 그의 성분들로 분해함으로써 압축 성능을 향상시키기 위해 각 성분들에 적당한 부호화 기법 적용 웨이블릿 변환은 입력 신호를 다루기 쉬운 성분으로 분해하며, 이들은 특수한 해석이 가능하고, 압축을 위해 성분들을 양자화할 수 있다. 이러한 성분들을 사용하여 적어도 근사적으로 원래 신호를 복원하고자 한다. 웨이블릿 변환의 기저 함수들은 시간과 주파수 모두에서 분해능을 가진다. 웨이블릿 변환에는 두 가지 형태가 있다. : 연속 웨이블릿 변환(CWT)와 이산 웨이블릿 변환(DWT) 영상에 대한 이들 작용은 점점 더 작은 영상을 생성하는 것과 동일 각 단계에서 크기가 ¼로 줄어들고 평균과의 차분을 저장해가는 것이다. 멀티미디어시스템 2011-2학기

44 연속 웨이블릿 변환 일반적으로 웨이블릿은 평균이 0인 함수 Ψ∈L2(R) 이다.
이것을 달리 표현하면, Ψ(t)의 0번째 모멘트 Mo는 0이다. P번째 모멘트는 다음과 같이 정의된다. 함수 Ψ는 ∥Ψ∥=1로 정규화되고, t=0 주변에 밀집된다. 다음의 전형 웨이블릿의 크기를 조절하고 변형함으로써 웨이블릿 함수군을 얻을 수 있다. 멀티미디어시스템 2011-2학기

45 시간 u, 크기 s에 대해 f ∈L2(R)의 연속 웨이블릿 변환(CWT)은 다음과 같이 정의된다. :
연속 웨이블릿 변환의 역은 : 여기서 이고, Ψ(ω)는 Ψ(t)의 푸리에 변환이다. 멀티미디어시스템 2011-2학기

46 이산 웨이블릿 변환 이산 웨이블릿 변환들은 동일한 전형 웨이블릿에서 출발하지만, 스케일링과 이동을 달리한다.
DWT는 다해상도 분석에서 연속 시공간에서의 웨이블릿들과 이산 시공간에서의 “필터 은행”과의 연결을 수행한다. 다음과 같이 변형된 웨이블군을 표현할 수 있다. 이것은 L2(R)의 정규직교 기저를 이룬다. 멀티미디어시스템 2011-2학기

47 웨이블릿 기반의 다해상도 해석 다해상도 분석은 특별한 목적을 위해 신호 해상도를 적당한 수준으로 변경하는 도구가 될 수 있다.
근사 성분은 반복적으로 근사 성분과 상세 성분으로 분해되어가고 연속적으로 성긴 스케일을 가지게 된다. 웨이블릿 함수 Ψ(t)은 상세 정보를 구체화하는데 사용된다. 평균 정보는 전형 웨이블릿에 대한 일종의 이원으로 결정되며, 스케일링 함수 Φ(t)로 불린다. 웨이블릿들은 해상도 2-j의 근사가 더 성긴 해상도 2-(j+1)의 근사를 계산하기에 충분한 정보를 포함하도록 설정된다. 멀티미디어시스템 2011-2학기

48 스케일링 함수는 다음의 이른바 변형식을 만족하여야 한다.
스케일링 함수뿐만 아니라 더 성긴 수준의 웨이블릿 또한 다음과 같이 변경값의 합으로 표현될 수 있다. 벡터 h0[n]과 h1[n]은 각각 저역 분해 필터, 고역 분해 필터라고 한다. 원래 입력 신호를 복원하기 위해서는 역의 과정이 필요하다. 역 필터는 합성 필터라고 한다. 멀티미디어시스템 2011-2학기

49 1D dyadic 웨이블릿 변환 블록도 그림 8.18 멀티미디어시스템 2011-2학기

50 웨이블릿 변환 예제 원래 신호열을 그의 짝이 되는 평균 xn-1,i와 차분 dn-1,i 으로 교체하는 변환을 생각해보자.
다음과 같은 입력 문자열을 생각해보자. 원래 신호열을 그의 짝이 되는 평균 xn-1,i와 차분 dn-1,i 으로 교체하는 변환을 생각해보자. 평균과 차분히 첫 번째 요소가 짝수 색인을 가지는 입력열의 연속된 짝에만 적용된다는 것을 기억하자. 그러므로 각 집합 {xn-1,i} 와 {dn-1,i} 에서 성분의 수는 원래 입력열의 요소의 수의 정확히 절반이다. 멀티미디어시스템 2011-2학기

51 이 신호열은 입력 신호열 요소의 수와 정확히 동일한 수의 요소를 가진다. – 변환은 데이터량을 증가시키지 않는다.
이때 두 신호열 {xn-1,i} 와 {dn-1,i} 를 줄줄이 연결하면 원래 신호열과 동일한 길이의 새로운 신호열을 형성할 수 있다. 결과 신호열은 다음과 같다. 이 신호열은 입력 신호열 요소의 수와 정확히 동일한 수의 요소를 가진다. – 변환은 데이터량을 증가시키지 않는다. 위 신호열의 처음 절반부분은 원래 신호열로부터의 평균값을 가지기 때문에 원래 신호의 성긴 근사로 볼 수 있다. 이 신호열의 나머지 절반은 그 처음 절반의 근사오차로 볼 수 있다. 멀티미디어시스템 2011-2학기

52 다음의 관계식으로부터 변환된 신호열로부터 원래신호를 쉽게 복원할 수 있음을 보일 수 있다.
이 변환이 이산 Harr 웨이블릿 변환이다. 그림 8.12 멀티미디어시스템 2011-2학기

53 그림 8.13 멀티미디어시스템 2011-2학기

54 그림 8.14 멀티미디어시스템 2011-2학기

55 그림 8.15 멀티미디어시스템 2011-2학기

56 그림 8.16 멀티미디어시스템 2011-2학기

57 그림 8.17 멀티미디어시스템 2011-2학기

58 이중직교 웨이블릿 정규직교 웨이블릿에서 순방향 변환과 그의 역은 서로 전치이며, 분해 필터와 합성 필터는 동일하다.
직교성이 없다면 분해와 합성에 대한 웨이블릿을 “이중직교”라고 한다. 합성 필터는 더 이상 분해 필터와 동일하지 않다. 이들을 각각 다음과 같이 표시한다. 이중직교 웨이블릿 변환을 구체화하기 위해서는 h0[n]과 가 모두 필요하다. 멀티미디어시스템 2011-2학기

59 표 8.2 멀티미디어시스템 2011-2학기

60 표 8.3 멀티미디어시스템 2011-2학기

61 2D 웨이블릿 변환 N x N 입력 영상에 대해, 2차원 DWT는 다음과 같이 수행된다.
- 영상의 각 행을 h0[n]와 h1[n]로 콘볼루션한 결과에서 각 홀수번째 열을 제거하고 변환된 행을 구성하기 위해 이 열을 연속되게 묶는다.    - 모든 행이 변환된 후에는 결과의 각 열을 h0[n]와 h1[n] 로 콘볼루션한다. 다시 홀수번째 행을 제거하고 결과를 연속되게 묶는다. 위의 각 과정을 수행하고 나면, DWT의 한 단계가 완성된다. 변환된 영상은 이제 네 가지 부대역 LL, HL, LH, HH를 포함하게 된다. 멀티미디어시스템 2011-2학기

62 그림 8.19 멀티미디어시스템 2011-2학기

63 2D 웨이블릿 변환 예제 입력 영상은 영상 Lena의 서브 샘플링된 형태로 그림 8.20과 같다. 입력의 크기는 16×16이고, 예에서 사용된 필터는 표 8.3의 Antonini 9/7 필터이다. 그림 8.20 멀티미디어시스템 2011-2학기

64 우선, 분석과 합성 고역 통과 필터를 계산할 필요가 있다.
수식적인 형태로 입력 영상은 다음과 같다. 우선, 분석과 합성 고역 통과 필터를 계산할 필요가 있다. 멀티미디어시스템 2011-2학기

65 첫 번째 행을 h0[n]와 h1[n]로 콘볼루션함으로 시작해서 홀수 번째 값을 제거한다. 이 두 가지를 수행한 결과는
다음으로 결과 계수를 연속적으로 나열함으로써 변환된 결과 행을 얻게 된다. 변환된 영상의 첫 번째 행은 다음과 같다. 이제 남은 행에 동일한 동작을 수행해나간다. 멀티미디어시스템 2011-2학기

66 결과는 다음과 같다. 멀티미디어시스템 2011-2학기

67 위 결과들을 하나의 열로 묶고, 남아있는 각 열에 동일한 과정을 적용하면 다음과 같은 마지막 변환된 영상에 이르게 된다.
이제 위의 결과 영상의 열에 필터를 적용시켜나가자. 이전에서와 같이 각 열에 h0[n]와 h1[n] 모두를 적용하고 홀수 번째 결과를 제거한다. 위 결과들을 하나의 열로 묶고, 남아있는 각 열에 동일한 과정을 적용하면 다음과 같은 마지막 변환된 영상에 이르게 된다. 멀티미디어시스템 2011-2학기

68 이산 웨이블릿 변환의 한 단계가 이제 완성되었다
이산 웨이블릿 변환의 한 단계가 이제 완성되었다. 이제 동일한 변환 과정을 좌상단 8×8 DC 영상 I12(x,y) 에 적용함으로써 다른 단계를 수행할 수 있다. 결과적인 2 단계 변환 영상은 다음과 같다. 멀티미디어시스템 2011-2학기

69 그림 8.21 멀티미디어시스템 2011-2학기

70 8.7 웨이블릿군 보통의 dyadic 웨이블릿 분해에서 단지 저역 통과 필터링 된 부대역만이 반복적으로 분해 되고 대수 트리 구조에 의해 표현될 수 있다. 웨이블릿군 분해는 이 분해를 전체 트리 중 어떤 제거된 부트리에 의해 표현되는 것을 허용한다. 웨이블릿군은 비용 측정에 따른 최적의 웨이블릿 기저를 사용할 수 있기 때문에 매우 융통성이 있다. 멀티미디어시스템 2011-2학기

71 8.8 웨이블릿 계수의 내장 제로트리 영상 부호화에서 매우 효율적이고 계산 소요가 적은 방식
EZW 알고리즘은 두가지 문제점을 안고 있다. 1. 주어진 비트율에서 가장 좋은 영상의 품질을 얻는 것과 2. 내장형태에서 이러한 일을 이뤄내는 것이다. 내장 부호는 부호기가 어느 지점에서도 부호화를 종료할 수 있도록 하고, 따라서 어떠한 목표 비트율이라도 정확히 충족시킬 수 있다. 마찬가지로 복호기는 어느 지점에서도 복호를 중지할 수 있고, 모든 낮은 율의 부호화에 대응하여 복원 신호를 생성할 수 있다. 멀티미디어시스템 2011-2학기

72 제로트리 데이터 구조 EZW 알고리즘은 0이아닌 양자화된 웨이블릿 계수들의 위치를 표시하는 “중요도 사상도”를 효율적으로 부호화한다. 이것은 제로트리라고하는 새로운 데이터 구조를 사용하기 때문이다. 계층적 웨이블릿 분해를 사용하여 주어진 스케일에서의 모든 계수들을 비슷한 원류를 가지는 다음의 더 세밀한 스케일에서의 계수들과 연관시킬 수 있다. 성긴 스케일에서 계수는 부모라고 부르고, 모든 대응하는 계수들은 동일한 공간 지역과 비슷한 원류의 다음의 세밀한 스케일은 자식이라고 불린다. 멀티미디어시스템 2011-2학기

73 그림 8.22 멀티미디어시스템 2011-2학기

74 그림 8.23 멀티미디어시스템 2011-2학기

75 중요도 사상도는 4개의 기호 알파벳을 가지는 제로트리를 사용하여 부호화된다.
주어진 문턱값 T에서 만약 계수 x가 중요하지 않고 모든 그 손자들이 또한 중요하지 않다면 이것은 제로트리의 요소이다. 만약 이전에 제로트리 뿌리의 손자가 아니라면 제로트리의 요소는 제로트리 뿌리가 된다. 중요도 사상도는 4개의 기호 알파벳을 가지는 제로트리를 사용하여 부호화된다. - 제로트리 뿌리. 제로트리의 뿌리는 세밀한 스케일에서 계수의 비중요도가 완벽히 예측됨을 지시하는 특별한 기호로 부호화된다.     - 고립 제로. 계수는 중요하지 않지만, 어떤 중요한 손자를 가질 수는 있다.    - 양의 중요도. 계수는 양수 값의 중요도를 가진다.     - 음의 중요도. 계수는 음수 값의 중요도를 가진다. 멀티미디어시스템 2011-2학기

76 연속 근사 양자화 동기 : - 제로트리 데이터 구조를 사용한 중요도 사상도의 효율적인 부호화의 장점을 활용하자.
- 이블릿 변환된 영상에 대한 스케일 공간의 성긴 스케일에서부터 세밀한 스케일로의 다중 세밀도의 대수적 표현을 제공하는 내장 부호를 생성하자. SAQ 방법은 각 계수의 중요도를 결정하기 위해 일련의 문턱값 T0,…,TN-1을 연속적으로 적용한다. 주 목록과  부 목록은 부호화와 복호화 과정 내내 유지된다. 멀티미디어시스템 2011-2학기

77 주 경로 주 경로에서 자신의 좌표를 가지고 있는 주목록의 계수들은 그들이 아직 중요하지 않다는 것을 의미한다.
이 계수들은 그 중요도가 결정되기 위해 문턱값 Ti 와 비교가 수행된다. 만약 계수가 중요하다고 판명되면, 그 크기가 부 목록에 첨부되고, 웨이블릿 변환 행렬의 계수들은 더 작은 문턱값에서 미래의 주 경로에서 제로트리가 나타날 가능성을 활성화하기 위해 0으로 놓여지게 된다. 결과 중요도 사상도는 제로트리 부호화된다. 멀티미디어시스템 2011-2학기

78 부 경로 부 목록의 모든 계수들이 스캔 되고 그 크기는 복호기에서 사용가능해질 때 추가 비트로 상세화된다.
계수의 실제 크기에 대한 불확실성 구간의 길이는 절반으로 줄여진다. 부 목록의 각 크기에 대해, 상세화는 이진 알파벳을 이용하여 부호화될 수 있는데, 여기서 1은 참 값이 불확실성 구간의 상위 절반부에 들어감을 의미하고, 0은 하위 절반에 들어가게 됨을 의미한다. 부 경로를 거친 후에 부 목록의 크기는 부호기가 동일한 순서화를 수행할 수 있는 정도로 감소하는 순서로 순서화된다. 멀티미디어시스템 2011-2학기

79 그림 8.24 멀티미디어시스템 2011-2학기

80 부호화 가장 큰 계수는 57이므로, 초기 문턱값 T0를 32로 놓는다. 처음에 주목록에는 모든 계수의 좌표가 포함된다.
스캔된 계수들은 다음과 같다. 문턱값과 비교하면, 계수 57과 -37은 중요하다고 볼 수 있다. 이처럼 p, n으로 그들을 표현하는 출력값을 결정한다. 멀티미디어시스템 2011-2학기

81 계수 -29는 중요하지 않지만, LH1에 있는 중요한 손자 33을 가진다. 그러므로 z로 부호화된다.
이런 방식으로 진행해나가면 주 경로 결과 기호는 다음과 같다. 5개의 계수가 중요하다고 판명되었다. : 57, -37, 39, 33과 또 하나의 33. 어떤 계수도 2T0=64보다는 크지 않고, 첫 번째 주 경로에서 사용된 문턱값이 32임을 알기 때문에 불확실성 구간은 [32, 64)가 된다. 이제 부경로가 수행되어 이 계수들이 불확실성 구간의 첫 절반부에 존재하는지 두 번째 절반부에 존재하는지 표시함으로써 계수의 크기를 상세화한다. 멀티미디어시스템 2011-2학기

82 이제 주 목록은 중요하다고 판명된 계수들을 제외한 모든 계수의 좌표를 포함한다. 그리고 부목록은
부 경로가 완성되면, 더 큰 계수가 작은 값들 이전에 나타나도록 부 목록의 값들을 재정렬한다. 여기서 한 가지 제한점은 복호기도 동일한 재정렬을 수행할 수 있다는 가정이다. 복호기는 [32,48)과 [48,64)의 값을 구별할 수 있다. 39와 37은 복호단에서 구별되지 않으므로 이들의 순서는 변하지 않을 것이다. 멀티미디어시스템 2011-2학기

83 두 번째 주 경로에 대한 새로운 문턱값은 T1=16 이다. 위에서와 동일한 과정을 수행하면 주 경로는 다음의 기호를 출력한다.
두 번째 주 경로 및 부경로를 시작하기 전에, 웨이블릿 변환 행렬에 있는 중요한 계수의 값을 0으로 놓아 새로운 제로트리가 생성되는 것을 막는다. 두 번째 주 경로에 대한 새로운 문턱값은 T1=16 이다. 위에서와 동일한 과정을 수행하면 주 경로는 다음의 기호를 출력한다. 부 목록은 이제 다음과 같이 된다: 멀티미디어시스템 2011-2학기

84 연속된 주 경로와 부 경로의 출력들은 다음과 같다.
부 경로에서 세 개의 현재 불확실성 구간 [48, 64), [32, 48), [16, 32) 각각을 절반으로 줄인다. 부경로에 의한 결과 비트는 다음과 같다. 연속된 주 경로와 부 경로의 출력들은 다음과 같다. 멀티미디어시스템 2011-2학기

85 복호화 복호기 단에서 첫 번째 주 경로 및 부 경로로부터만 정보를 받게 된다고 가정하자. 부호화 과정을 역으로 수행함으로써 변환 계수의 손실된 형태의 값들을 복원할 수 있다. D0의 심볼들로부터 중요한 계수의 위치를 얻을 수 있다. 그러면 S0로부터 복호화된 비트들을 이용하여 불확실성 구간의 중앙의 값으로 이 계수들을 복원한다. 그림 8.25 멀티미디어시스템 2011-2학기

86 만약 복호기가 D0,S0,D1,S1,D2,S2를 받고 S2의 오직 첫 10비트만을 수신했을 때 복원된 형태는 다음과 같다.
그림 8.26 멀티미디어시스템 2011-2학기

87 8.9 SPIHT SPIHT는 EZW 알고리즘을 획기적으로 확장한 방법이다.
또, 어떠한 순서화 정보도 복호기에 완전히 전송될 필요가 없다. 대신 복호기는 부호기의 실행 경로를 재생성하여 순서화정보를 복원해낸다. 멀티미디어시스템 2011-2학기