ch14. Image Coding and Compression

* 멀티미디어는 매우 큰 데이터이다.

예로, 512*512 24-bit RGB color 이미지 = 6.29Mbits 이다.

채널의 전송속도가 56kbps라면. 전송 시간은 112sec로 예상된다.

 

* 멀티미디어데이터 압축 기본 개념

+ 핵심

> 질(압축률)이 좋게!

> 복잡도가 적게!

> 수행 시간이 짧게!

 

a. 보편적인 압축 시스템 구성

codec이라고도 부름.

 

b. 압축률

c = (src coder input size)/(src coder output size)

c. Lossy compression & Lossless compresion

손실 압축과 무손실 압축

d. Statical Redundancy(중복)의 제거

- Spatial redundancy <- 예로 RLC

- temporal redundancy <- 시간상 변하는 부분만 encoding.

e. Human Visual System - 사람에 맞게. 가청, 가시영역정도로

- Spatial masking : Flat vs Texture areas

- Temporal masking : Scene cuts

 

* 멀티미디어 데이터 압축에 대한 Framework 구성

 

14.1 lossless and Lossy Compression

 

14.2 Huffman Coding <- Code Book이 고정적이다. 그리하여 Encoding 시간이 가변적인 RLE 같은 것보다 상대적으로 적다. 반면 압축률이 떨어질 수 있다.

(0.2*3)+(0.4*1)+(0.3*2)+(0.1*3) = 1.9

 

H = -(0.2log(0.2) + 0.4log(0.4) + 0.3log(0.3)+0.1log(0.1)) = 1..8464

 

 - Code Book 만드는 법

 

14.3 RLE (Run-length Encoding) <- Code book이 adaptive하게 (가변적으로) encoding 한다. 시간이 걸리더라도 압축률을 올리고 싶을 때 사용한다.

 

1) 0 과 1의 시작위치와 갯수로 encoding

2) 1의 시작위치와 갯수로 Encoding

3) bit plane하여 RLE.

4) Binary 에서 Gray code로

 

MSB -> LSB로 넘어갈때, 변화가 있다면 1로, 변화가 없다면 0으로.

 

ex) 2 = 0 0 1 0 (Binary)

-> 0 0 1 1 (Gray)

 

14.5 JPEG ( Joint Photographic Experts Group ) Image coding algorithm <- Image만 가지고 압축과 복원을 하자. MPEG(Moving ~),영상을.  H.320은 통신을 하는 사람들

 

 

 

 

- DCT 는 손실이 없다. 무손실

- Quantization Matrix: 예시 [0 255] -> [0 15], 압축을 되지만 손실이 생긴다. 

- DPCM : 첫값이 기준이 되고, 다음값들은 그저 차이만 기록하는 것.

 

 

 

 

 

 

 

 

 

 

 

 

* JPEG Algorithm 과정

 1) 이미지를 8*8 block으로 나눈다. 

// DCT를 원이미지를 한번에 하면, 시간이 너무 걸리므로 (FFT에 비해) 나눠서 한다. 그리고 8*8을 넘어서면 반대로 시간이 늘어나므로 8*8으로 하였다.

 2) 주어진 block에서 128을 빼자. // 값을 음수와 양수로 나누기 위해서

 3) DCT를 수행

 4) DCT matrix를 Q matrix로 나눈다.

 5) 이 Matrix를 zig zag scan한다.

// 좌상단으로 갈수록 저주파가 몰려있고,, 우하단으로 갈수록 고주파 성분이 있다. 이중에 저주파성분이 중요하다. 한줄로 읽으면 저주파->고주파->저주파->고주파... 이리 되니 zig zag scan을 한다.

 6) DCT 한 값의 Matrix를 Q Matrix로 나누어 nomalize한다.

 

 

 

여기는 DCT -> Quntization -> IDCT 함.

마지막 결과, 차이만 코딩하여 보낸다.

 

* JPEG decoding 하는 과정.

 1) Inverse zig zag.

 2) Q matrix랑 곱한다.

 3) Inverse DCT

 4) 128을 더한다.

 

// 원이미지와 복원한 이미지는 차이가 존재한다.

 

+)  Q Matrix를 고정하여 사용하지 않는다. 통신이 좋지않을 때는 2q (이리되면 PSNR이 낮아진다.), 좋을 때는 1/2q or 1/4q 한다.

 

* DCT 와 FFT 비교

 

 

 

- FFT는 고주판 성분을 제외하고 다시 복원을 하니,원 값과 차이가 많이 생겼다.

 

- DCT는 같은 수행을 했어도 값의 차이가 그리 크지 않았다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

* Huffman Encoding

- 책의 압출률 계산법 : 총 픽셀수 * 픽셀당 bit수/(압축된 총 Bits) = (8*8)*8bits/ 60bits = (64*8)/8 = 1.xx * 8 = 8.5 (=압축률)

- 60/64 = 0.94 (픽셀당 필요한 bit수) = Bits/Pixel

 

Run : 자기 값 앞에 0이 몇 개나 있는가?

Category : 범주,, integer을 표현하는 데 필요한 bit수 <- N을 계산 log_2(N) 의 올림.

Sign: 양수는 1, 음수는 0

Position: 테이블 상 위치.

Run, Category 값

 

을 가지고 Code Book을 보고 Code를 부여

 

* Chroma Sub-sampling

 

 

사람이 차이를 가장 느끼는 것. 명도가 중요하다. 채도를 구분하는 것은 사람에게는 참으로 어렵다.

그림에서 오른쪽으로 갈 수록 상대적으로 압축하는 것이 준다. Y는 그대로 가지만, Cb, Cr 채도만 바꾼다.

16 = 128/8

16*16 DCT * 3ch

16*16 + 8*8*2ch

 

* PSNR 계산

 

PSNR 계산하는 것을 기억하자. 여기 공식은 틀렸다고 한다.

 

*1D 2D

 

*비디오

 

 

비디오 클립이란 것은 연속된 이미지의 모음.

한 장의 압축은 JPEG 같은 것으로.

그런데 비디오에서는 Frame이 변화하였을 때 큰 차이가 별로 없는 경우가 있다. Temporal redundancy

차이가 없는 부분 = 0 = Frame 1 – Frame 2

차이가 있는 부분 = n = Frame 1 – Frame 2

그러한데 차이를 줄이고 싶다?

Motion Estimation : 지금 Frame 의 sub block이 이전 Frame에 있었는지, 가장 비슷한 곳을 유추해 내는 것.

-> Motion vector 유추. 움직인 거리.

Such range, 범위를 정해서 찾는다.

이전 Frame (reference frame)

 

조금 씩 block을 옮겨 다니면서 유추한다.

찾아낸 옮기는 차이가 motion vecto이다.

보내는 것은 차이에 대한 Matric와 motion vecto이다.