제 4장. 멀티미디어 데이터 압축.

Presentation on theme: "제 4장. 멀티미디어 데이터 압축."— Presentation transcript:

1 제 4장. 멀티미디어 데이터 압축

2 목차 압축의 개념 압축 알고리즘 이미지 압축 표준 오디오 압축 기법 동영상 압축 표준 요약 및 참고문헌

3 압축의 개념 압축의 개념 코딩의 개념 코딩의 목적에 따른 분류
코딩(coding) = 인코딩(encoding) + 디코딩(decoding) 인코딩: 목적에 따라 데이터의 형태를 변환하는 과정 디코딩: 인코딩된 데이터를 원래의 데이터로 복원하는 과정 코딩의 목적에 따른 분류 저장공간과 전송 대역폭의 효율적 이용 → 압축 데이터의 전송 도중에 발생하는 오류의 처리 → 패리티 비트, 해밍코드 데이터의 보호 → 암호화 (encryption)

4 압축의 개념 (계속) 압축의 개념 저장공간과 전송 대역폭의 효율적 이용을 위해 데이터를 크기(전체 비트 수)를 줄이는 것
데이터 압축 시스템 구조 인코더에서 압축을 하고, 디코더에서 복원 중간 매체: 데이터 저장 공간 또는 통신/컴퓨터 네트워크 코드(code): 인코더의 출력 일반적인 데이터 압축 시스템 구조

5 압축의 개념 (계속) 압축의 필요성 대용량의 멀티미디어 데이터를 컴퓨터에 저장하거나 네트워크를 통해 다른 기기에 전송하는데 많은 자원이 소모됨 3 분 길이의 CD오디오 품질의 음악을 44.1 kHz의 주기로 16 비트 샘플링하여 디지털 데이터로 변환한 데이터의 크기 3 분 x 60 초/분 x 44,100 회/초 x 2 bytes/회 ≈ 15 Mbytes 1280 x 1024 해상도의 32 비트 색 이미지를 초당 30 프레임으로 전송하는 비디오 응용에 필요한 전송 대역폭 1280 x 1024 x 4 bytes/프레임 x 30 프레임/초 = 150 Mbytes/초 전화선(xDSL)과 모뎀을 이용할 경우: 0.2 ~ 6.3 Mbytes/초 (=1.5 ~ 52 Mbps) Ethernet을 이용할 경우: 1.2 ~ 12 Mbytes/초 (=10 ~ 100 Mbps) Video demystified p.2 하단 참조 Fundamentals of multimedia p.431 참조

6 압축의 개념 (계속) 데이터의 특성 중복성(redundancy) 시간적 중복성(temporal redundancy)
시간의 흐름에 따라 동일한 데이터가 반복하여 나타남 사운드 데이터, 동영상 데이터 공간적 중복성(spatial redundancy) 공간상의 여러 위치에 같은 데이터가 중복되어 나타남 정지 영상 데이터나 문서 데이터, 동영상 데이터 A B C A B C 시간 T5 T4 T3 T2 T1 (a) 시간적 중복성 (b) 공간적 중복성 중복성의 예

7 압축의 개념 (계속) 압축 시스템의 평가 기준 압축률(compression ratio) 복원된 데이터의 품질(quality)
압축 이전의 데이터 크기와 압축된 데이터 크기의 비율 복원된 데이터의 품질(quality) 무손실 압축(lossless compression) 문서 데이터 손실 압축(lossy compression) 소리 데이터, 이미지 데이터 압축률 = (B0: 압축 이전의 데이터 비트 수 B1: 압축 이후의 데이터 비트 수) 대화형 멀티미디어 응용과 검색형 멀티미디어 응용은 박스로 설명 예정

8 압축의 개념 (계속) 압축/복원 속도 대화형(dialogue) 멀티미디어 응용 검색형(retrieval) 멀티미디어 응용
데이터의 압축과 복원이 거의 동시에 일어남 압축/복원 속도 모두 중요 대칭형(symmetric) 멀티미디어 응용 예) 비디오 전화, 비디오 회의 등 검색형(retrieval) 멀티미디어 응용 압축된 데이터는 저장 공간에 저장되었다가 필요에 의해 복원됨 복원 속도 중요, 압축 속도는 덜 중요 비대칭형(asymmetric) 멀티미디어 응용 예) 주문형 비디오(VOD), 비디오 CD 등

9 압축 알고리즘 분류 반복길이 코딩 (run-length coding) 무손실 압축 (lossless compression)
허프만 코딩 (Huffman coding) 렘펠-지프 코딩 (Lempel-Ziv coding) 손실 압축 (lossy compression) 변환 코딩 (transform coding) FFT, DCT 예측 코딩 (predictive coding) DPCM, ADPCM DM, ADM 양자화 (quantization) 웨이블릿 코딩 (wavelet-based coding) 보간법 (interpolation) 프랙탈 압축 (fractal compression) 혼성 압축 (hybrid compression) JPEG, GIF, MPEG, H.261, H.263 … 무손실 압축 – 엔트로피 코딩 (미디어의 특성 고려하지 않음) 손실 압축 – 소스 코딩 (미디어의 특성이나 데이터의 의미를 고려함)

10 압축 알고리즘 (계속) 무손실 압축 손실 압축 압축 이전의 데이터에 포함된 모든 정보를 손실 없이 인코딩
동일한 정보의 반복적인 출현에 의해 나타나는 중복성만을 제거 문서 데이터 압축에 필수 엔트로피(entropy) 코딩 손실 압축 데이터에 포함된 정보 중 내용을 인식하는데 크게 영향을 주지 않는 정보들을 삭제함 무손실 압축에 비해 압축률을 높임 원천(source) 코딩

11 압축 알고리즘 (계속) 혼성 압축 손실 압축 기법과 무손실 압축 기법을 혼용
20:1 ~ 200:1 정도의 압축률을 얻을 수 있음 대부분의 표준 압축 기법에서 이용됨 혼성 압축의 과정

12 압축 알고리즘 (계속) 반복길이 코딩(Run-Length Coding)
예) TABBBBBBBBBBBBBBGLC → 14개

13 압축 알고리즘 (계속) 허프만 코딩(Huffman Coding)
데이터를 구성하는 단위 정보들의 빈도수를 기반으로, 각 단위 정보를 표현하는 비트 수를 효율적으로 할당하는 방법 가변 길이 코딩 (Variable-Length Coding) 방법 예) 26개의 글자 S 1 H I E T C . N THIS IS TEST SENTENCE. bottom-up 방식 가장 자주 나타나는 문자에 가장 적은 비트 수를 할당. E T S H I 5 4 2 N C . 1 각 문자의 출현 빈도 허프만 트리

14 압축 알고리즘 (계속) 높은 빈도로 나타나는 단위 정보에는 비트 수를 적게 사용하고,
E T S H I N C . 11 10 011 010 0011 0010 0001 00001 00000 [각 문자마다 할당된 코드] 높은 빈도로 나타나는 단위 정보에는 비트 수를 적게 사용하고, 낮은 빈도로 나타나는 단위 정보에는 비트 수를 많이 사용 8비트 아스키 코드 이용: 8 x 26 = 208 비트 허프만 코딩 이용: (2x5)x2 + (3x4)x2 + (4x2)x3 + (5x1)x2 = 78 비트 허프만 코딩의 특징 추가

15 압축 알고리즘 (계속) 허프만 코딩의 속성 허프만 코딩의 단점
유일한 접두사를 가지고 있음(unique prefix property) 하나의 허프만 코드는 다른 허프만 코드의 접두사가 될 수 없음 ← 이유: 모든 입력 기호들을 허프만 트리의 리프 노드에 둠 허프만 코딩으로 만들어진 코드보다 더 효율적인 방법이 없음(optimality) 인코딩된 데이터의 길이가 최소임(minimum-redundancy code) 허프만 코딩의 단점 입력 기호의 확률 분포가 변한다면, 효율성을 잃어버릴 수 있음 (가변 길이 코딩) 입력 기호의 확률을 인코딩 전에 미리 알아야 함

16 CCITT GRUOP3 1D 압축을 위한 코드 테이블 (일부)
압축 알고리즘 (계속) 미리 정의된 허프만 코드 테이블을 이용 흑백 비트맵 이미지의 압축에 이용 각 비트 패턴에 따라 해당하는 코드가 테이블에 미리 정의됨 대량의 샘플 영상을 바탕으로 허프만 코딩을 수행하여 코드를 할당 (CCITT Group 3 표준) 비트 0의 반복 횟수 코드 비트 1의 반복 횟수 코드 1 2 3 ... 20 50 000111 0111 1000 ... 1 2 3 ... 20 50 010 11 10 ... CCITT GRUOP3 1D 압축을 위한 코드 테이블 (일부)

17 압축 알고리즘 (계속) 렘펠-지프 코딩(Lempel-Ziv Coding)
동일한 어구(phrase)가 반복적으로 나타나는 데이터의 성질 이용 처음 나타난 어구는 사전(dictionary)에 어구와 그 어구의 위치 정보를 등록하고 그대로 출력 반복해서 나타난 어구는 사전에 등록된 위치 정보로 치환하여 출력 미리 확률이나 통계를 필요로 하지 않음 pkzip과 같은 파일 압축 프로그램에 이용됨.

18 압축 알고리즘 (계속) 렘펠-지프-웰치(LZW: Lempel-Ziv-Welch) 코딩 예) 어구들 사이의 상대적 위치를 이용
UNIX의 compress에 이용 GIF(Graphics Interchange Format)의 영상 압축 기법

19 압축 알고리즘 (계속) 변환 코딩(Transform Coding) 적당한 변환을 통하여 데이터의 영역(domain)을 옮김
데이터를 구성하는 단위 정보의 개수를 줄이는 기법 FFT(Fast Fourier Transform): 시간 영역 → 주파수 영역 DCT(Discrete Cosine Transform): 공간 영역 → 주파수 영역 진폭 진폭 시간 주파수 (a) 시간 영역에서 본 데이터 (b) 주파수 영역에서 본 데이터 사운드 데이터의 영역에 따른 표현

20 압축 알고리즘 (계속) 빠른 푸리에 변환(FFT: Fast Fourier Transform) CD-Audio의 인코딩에 이용
사운드 데이터를 시간 영역에서 주파수 영역으로 변환 시간 영역 내의 n개의 샘플링된 값들을 주파수 영역 내의 n개의 값들로 변환하는 경우, 변환된 데이터의 i번째 값은 ( Pk는 원래 데이터의 k번째 값)

21 압축 알고리즘 (계속) 이산 코사인 변환(DCT: Discrete Cosine Transform)
JPEG, MPEG, H.261 등의 표준 압축 기법에서 이용 정지 영상 데이터를 공간 영역에서 주파수 영역으로 변환 크기가 N x N인 단위 영상 데이터를 변환하는 경우, 변환된 데이터의 (i, j)번째 값은 ( Pxy는 원래 데이터의 (x, y)번째 값, Ci, Cj 는 Ci  Cj  if (i  j  0), 1 if (i  0 혹은 j  0) ) 8 * 8 픽셀 단위의 블록 단위로 변환을 수행

22 압축 알고리즘 (계속) DCT 변환의 예 8×8 픽셀로 이루어진 이미지 데이터 블록을 단위로 변환 DCT 변환의 예

23 압축 알고리즘 (계속) 예측 코딩(Predictive Coding)
가정 : 정보의 흐름에 있어서, 다음에 나타날 정보는 바로 직전에 나타난 정보와 크게 다르지 않다 이전 정보와 차이 정보를 가지고 다음 정보를 생성 예측 코딩 기법의 예 차이 PCM(DPCM: Differential PCM) 적응적 차이 PCM(ADPCM: Adaptive DPCM) 델타 변조 방식(DM: Delta Modulation) 적응적 DM(ADM : Adaptive DM)

24 압축 알고리즘 (계속) DPCM 직전의 예측값을 이용하여 지금 인코딩하려는 정보를 예측
실제 정보의 값과 예측값 사이의 차이 정보를 생성 및 출력 데이터의 복원은 예측을 통해 이루어지며 예측에 의한 오류는 인코딩된 정보를 이용하여 보정됨 기울기 과부화(slope overload) 문제가 발생할 수 있음 실제 정보의 값과 예측값을 비교 인코딩하려는 정보 오류 보정 정보 (실제 정보의 값 – 예측값) 다음 정보의 값을 예측 (기존 예측값 + 오류 보정 정보) 예측값 DPCM을 이용한 인코딩

25 압축 알고리즘 (계속) ADPCM 출력되는 오류 보정 정보(차이 정보)의 크기가 출력 표현 한계를 넘어 서는 경우, 출력 정보의 스케일(scale)이 적응적으로 변화함 DPCM의 기울기 과부하문제를 해결

26 ADPCM 코딩을 이용한 기울기 과부하의 해결
압축 알고리즘 (계속) DPCM과 ADPCM의 예 8비트 데이터를 5비트 오류 보정 정보로 생성하는 경우 16 40 89 75 24 32 66 19 +15 -16 -12 15 30 45 60 44 47 31 +12 +1 +2 +8 -11 39 69 73 25 33 65 21 원래 데이터 DPCM으로 인코딩하고 디코딩한 데이터 ADPCM으로 인코딩하고 디코딩한 데이터 x 2 x 2 x 4 x 4 x 4 x 4 x 4 : 스케일 변화 정보 (ADPCM) ADPCM 코딩을 이용한 기울기 과부하의 해결

27 압축 알고리즘 (계속) DM ADM 차이 정보를 표현하는데 오직 1 비트만을 이용 (+, -)
차이 정보에 따라, 미리 정해진 차이 값을 더하거나 빼서 원래 정보를 복원 압축률은 매우 높지만, 원래 데이터를 완벽하게 복원할 수 없음 ADM 차이 정보의 순서에 따라 차이 값의 규모를 변화시킴 p ⅹ q = 1, p > 1 (p, q는 실수) (+, +), (-, -) : 차이 값의 규모를 키움 L ⅹ p (+, -), (-, +) : 차이 값의 규모를 줄임 L ⅹ q DM에 비해 원래 데이터와의 오차를 더 줄임 200kHz 이상의 샘플링 주기를 갖는 PCM에 의해 생성된 데이터에 사용

28 압축 알고리즘 (계속) DM과 ADM의 예 8비트 데이터를 DM과 ADM으로 각각 인코딩하고 디코딩하는 경우 16 24 36
40 89 75 24 32 66 19 + - 48 64 76 52 원래 데이터 DM으로 인코딩하고 디코딩한 데이터 ADM으로 인코딩하고 디코딩한 데이터 LADM = 16 24 36 24 36 24 36 24 차이 값의 변화 16 16 16 16 16 16 16 16 (p = 3/2, q = 2/3) LDM = DM 코딩과 ADM 코딩의 비교

29 압축 알고리즘 (계속) 양자화(Quantization)
양자(quantum)라는 미리 정의된 정보를 이용하여 주어진 데이터를 코딩하는 방법 스칼라 양자화 (scalar quantization) 어떤 스칼라 값을 양자(quantum)로 정하고, 데이터를 구성하는 값들을 양자의 개수로 치환 데이터의 중요도에 따라 크기가 다른 양자를 이용함으로써 덜 중요한 정보를 삭제하는 효과를 얻음 1 차원 변수를 기반으로 양자화하는 것 스칼라 양자화: R,G,B (intensity와 같은 1차원 변수로) 예)

30 압축 알고리즘 (계속) 벡터 양자화 (vector quantization) 하나의 값에 대해 둘 이상의 변수를 사용하여 양자화
코드북(codebook)에 미리 정의된 벡터 정보를 이용하여 데이터 내의 정보들을 코드북에 존재하는 정보의 색인으로 치환 인코딩 과정에서는 속도가 느리나, 디코딩 과정에서는 각 단위 정보마다 코드북을 한번만 참조하므로 속도가 비교적 빠름 코드북의 품질에 의해 영향을 받음 효율적인 코드북을 구성하는 것이 중요: 데이터의 특성을 바탕으로 구성됨 벡터 양자화: 여러 차원의 벡터 상에서 작용 사전 -> 기호일람표 quantizer에 대한 codebook

31 압축 알고리즘 (계속) 스칼라 양자화와 벡터 양자화의 예 스칼라 양자화와 벡터 양자화의 비교

32 압축 알고리즘 (계속) 웨이블릿 코딩(Wavelet-Based Coding)
웨이블릿 변환(wavelet transform)을 사용하여 입력 신호 (signal)를 시간과 진동수 측면에서 양측 모두 좋은 신호로 분해하여 압축 성능을 높인 코딩 방법 이미지 압축에 주로 사용됨 이산 웨이블릿 변환(DWT: Discrete Wavelet Transform) MPEG-4와 JPEG2000에 사용됨 2 개의 상호 보완적인(complementary) function 이용 웨이블릿(wavelet): 높은 주파수의 세부 이미지를 추출 스케일링 함수(scaling function): 높은 주파수를 제거 많은 값들이 0 또는 0에 가까운 값을 지님. 나머지는 상대적으로 인지할 정도의 값으로 양자화됨. <wavelet ; 웨이블릿> 웨이블릿은 디지털 신호 처리 및 이미지 압축에 사용되는 유용한 수학 함수이다. 웨이블릿 그 자체는 새로운 것이 아니지만, 이러한 용도로 웨이블릿을 사용한 것은 최근의 일이다. 웨이블릿의 근본 원리는 푸리에(Fourier) 분석과 비슷하며, 19세기 초반에 처음 개발되었다. 신호처리를 위해 웨이블릿을 이용하면 잡음 속에 섞인 약한 신호를 복원할 수 있다. 웨이블릿은 특히 의료 분야의 X-선 및 자기공명 이미지 처리에서 그 유용성이 입증되었다. 이런 방법으로 처리된 이미지는 세부적인 내용에 흐릿함이 없이 깨끗하게 처리될 수 있다. 웨이블릿은 인터넷 통신에서도 이미지를 압축하는데 사용되었는데, 일반적으로 다른 방식으로 했을 때에 비해 훨씬 효율이 높다. 일부의 경우에서 웨이블릿으로 압축된 이미지는 잘 알려진 JPEG 이미지를 사용한 비슷한 품질의 이미지에 비해 파일 크기가 25% 정도 밖에는 되지 않는다. 그러므로, 크기가 200 KB라서 다운로드에 1분이 걸리는 JPEG 형식의 사진을 예를 들면, 웨이블릿으로 압축된 형식에서는 크기가 50 KB에 15초 밖에는 걸리지 않는다는 얘기가 된다. 웨이블릿 압축 작업은 먼저 이미지를 분석하여, 그것을 수신측에서 복원할 수 있는 일련의 수학적 표현으로 변환함으로써 이루어진다. 웨이블릿 압축 이미지 파일의 확장자는 주로 "WIF"가 붙는다. 만약 사용자의 브라우저가 이 형식의 파일을 직접 지원하지 않는다면 플러그인 프로그램이 필요하다. 웨이블릿 압축은 아직 웹상에서 광범위하게 사용되지는 않는다. 가장 보편적인 압축 형식은 아직도 도면류에는 GIF, 그리고 사진류에는 JPEG이 널리 쓰인다.

33 압축 알고리즘 (계속) 2차원의 이미지의 경우, 수평과 수직 방향 모두에 2개의 함수 적용
4개의 서브이미지(subimage) 생성: HH, HL, LH, LL 웨이블릿 변환을 이용한 이미지의 분해 과정

34 2 차원 DWT: (a)첫 번째 단계(level)의 변환 (b)세 번째 단계의 변환
압축 알고리즘 (계속) 웨이블릿 계수(wavelet coefficient) 세부 이미지의 표현의 정도와 제거된 세부 이미지를 결정 (c) 2 차원 DWT: (a)첫 번째 단계(level)의 변환 (b)세 번째 단계의 변환 (c) 레벨변환을 한 실제 이미지

35 압축 알고리즘 (계속) DCT 기반 압축과의 비교 웨이블릿 계수와 DCT 계수의 유사성 압축 시스템의 유사성
많은 값들이 0에 가까운 수로 치환됨, 나머지 값들은 정도에 따라 상대적으로 인지할만한 값으로 양자화 압축 시스템의 유사성 DCT 변환 양자화 스캔 가변길이 인코딩 [ DCT 기반 압축 ] [ 웨이블릿 기반 압축 ] 웨이블릿 변환 양자화 스캔 가변길이 인코딩 많은 값들이 0 또는 0에 가까운 값을 지님. 나머지는 상대적으로 인지할 정도의 값으로 양자화됨. DCT 기반 압축과 웨이블릿 기반 압축

36 압축 알고리즘 (계속) 차이점: 웨이블릿 코딩의 장점 차이점: 웨이블릿 코딩의 단점
디코더가 복원 과정을 수행하는 중에 어느 시점에서든지 중지할 수 있음 (원래 이미지로의 완전한 해상도를 요구하지 않을 경우) 낮은 픽셀 깊이(bitrate)에서 더 효율적임 DCT에서 나타날 수 있는 블록화 현상(block artifact) 방지 일반적으로 다른 방식으로 이미지를 압축했을 때에 비해 훨씬 효율(화일 크기 및 전송 속도)이 높음 예) 비슷한 품질의 JPEG 이미지에 비해 화일 크기가 25 % 정도 차이점: 웨이블릿 코딩의 단점 더 많은 계산 능력을 필요로 함 거의 비슷한 압축률에 있어서 DCT 기반 압축보다 효율성이 떨어짐

37 인접한 픽셀들의 값이 유사한 경우에 대한 보간법의 적용
압축 알고리즘 (계속) 보간법 (Interpolation) 연속된 비슷한 정보들 중 몇 개만을 저장 데이터의 복원 시에 보간을 통해 삭제된 정보를 복원 예) 1 2 3 4 5 6 7 원래 데이터 압축 복원(보간) 1 2 3 4 5 6 7 저장되는 데이터 인접한 픽셀들의 값이 유사한 경우에 대한 보간법의 적용

38 압축 알고리즘 (계속) 프랙탈 압축(Fractal Compression) 개념 문제점
어떤 데이터 I가 있다고 할 때 모든 종류의 데이터 A에 대하여 W*(A) = I인, 즉 수렴점이 I인 변환 W를 찾아내는 기법 W*(A)는 변환 W의 무한 반복, 즉 W(W(W(…(W(A))))) 반복작업으로 생성해낼 수 있는 시스템의 구성 정보로 치환함으로써 데이터를 인코딩 실험적으로 60:1 이상의 압축율 문제점 복원은 빠르나 인코딩 과정은 복잡하고 느림 모든 종류의 데이터에 대해 변환 W가 존재하는 지와, 구해진 변환 W의 수렴점이 원하는 데이터와 일치하는 지를 증명하기 곤란함

39 압축 알고리즘 (계속) 예) 지어핀스키(Sierpinski) 삼각형

40 이미지 압축 표준 JPEG(Joint Photographic Experts Group)
Color & Grayscale 정지 영상의 압축 코딩의 표준 ISO에서 1992년에 제정 주요 특징 압축률과 영상의 품질을 사용자가 지정할 수 있음 영상의 형태(내용,크기,해상도,화면비,색상모형)에 관계없이 적용 가능 소프트웨어적으로 구현 가능 하드웨어를 이용할 경우, 영상의 품질이 크게 향상됨

41 이미지 압축 표준 (계속) 제공되는 부호화 방법 순차적 모드(Sequential DCT-based mode)
JPEG의 기본 인코딩 방법 이미지의 각 요소가 스캔되는 순서에 따라서 인코딩 DCT 변환, 양자화, 허프만 코딩을 이용 점진적 모드(Progressive DCT-based mode) 순차적 인코딩과 동일한 코딩 기법들을 이용 이미지가 여러 개의 스캔으로 인코딩됨 디코딩된 영상은 이미지의 윤곽부터 나타나고, 서서히 선명해짐 itu-t P.21

42 이미지 압축 표준 (계속) 무손실 모드(Lossless mode) 계층적 모드(Hierarchical mode)
정보의 손실 없이 영상을 인코딩 DCT와 양자화 대신, 픽셀 단위의 예측 기법을 이용 2 : 1 정도의 압축률을 얻음 계층적 모드(Hierarchical mode) 다양한 환경에서 영상을 재생하거나 출력 가능 영상의 해상도를 높여 가면서 여러 번 인코딩 각 단계의 인코딩은 앞의 세 가지 중 어느 것이든 이용 가능 예) 높은 해상도의 영상을 낮은 화면 해상도의 모니터에 상영하거나 낮은 해상도의 프린터에 출력하고자 할 때 사용

43 이미지 압축 표준 (계속) JPEG 인코딩(순차적 모드) 허프만 코드 테이블 이미지 8 x 8 블록들로 나눔 8 x 8 블록
DC-계수 DPCM DC 허프만 코딩 DCT 양자화 Zigzag 압축된 데이터 RLC AC 허프만 코딩 8 x 8 양자화 행렬 저술시 설명 순서 변경 예정 약간 수정 (이미지, zigzag, RLC, 압축된 데이터) AC-계수 JPEG 표준의 순차적 모드

44 이미지 압축 표준 (계속) 이미지 준비 단계 RGB 또는 YUV 등의 색상 모델을 이용하여 각 색상마다 평면(plane)으로 분리 각 평면을 8ⅹ8 픽셀로 이루어진 블록(block)들로 분할 최소 코딩 단위(MCU: Minimum Coded Unit): 디코딩하는 단위 평면 3 평면 2 평면 1 A 원래 이미지 최소 코딩 단위 평면과 최소 코딩 단위

45 이미지 압축 표준 (계속) DCT 변환 DC-계수(DC-coefficient) AC-계수(AC-coefficient)
블록의 기본 색상을 결정 x, y 각 방향에 대해 모두 주파수가 0인 경우에 해당 앞/뒤 프레임의 DC-계수와 함께 DPCM으로 인코딩됨 AC-계수(AC-coefficient) DCT 변환을 수행한 결과에서 DC-계수를 제외한 나머지 블록 내에서 각 픽셀간의 색상 변화에 대한 정보를 나타냄 x, y 어느 방향으로든 주파수가 0이 아닌 경우에 해당 프레임별로 Zig-Zag 형태로 나열됨

46 이미지 압축 표준 (계속) DCT로 변환된 블록의 형태 x y 주파수 커짐 DC AC01 AC07 주파수 커짐 AC70
AC-계수의 Zig-Zag 순서

47 이미지 압축 표준 (계속) 양자화 (Quantization)
높은 주파수의 AC-계수일수록 큰 값으로 나누어지므로 대부분 0으로 바뀜 예)

48 이미지 압축 표준 (계속) JPEG2000 12 개의 파트로 이루어져 있음 (이 중 파트 7은 취소)
JPEG보다 더 나은 변형률(rate-distortion)을 제공하고 이미지 품질을 향상시킴 웨이블릿 코딩 사용 DCT 기반 코딩도 JPEG과의 호환을 위해 지원 압축된 사진 비교: JPEG과 JPEG2000

49 이미지 압축 표준 (계속) JPEG의 약점 낮은 픽셀 깊이(0.25 bpp 이하) 압축에서 변형(distortion)이 심함
하나의 비트 스트림(bitstream) 상에서 무손실 및 손실 압축 제공 못함 사이즈가 매우 크거나 높은 정밀도를 가진 이미지들을 처리할 수 없음 낮은 전송률에서 높은 전송률에 이르는 점진적(progressive) 전송 하나의 복원 구조(single decompression architecture)가 없음 전송 에러 시 복원력이 매우 약함 관심 지역 코딩(ROI: Region-of-interest coding)을 지원하지 못함 특정 부분이 이미지의 나머지 부분보다 더 나은 품질로 코딩될 수 있음 컴퓨터 합성(computer-generated) 이미지나 혼합 문서에서는 좋은 성능이 나오지 않음

50 이미지 압축 표준 (계속) JPEG2000의 인코딩 과정 JPEG2000의 인코딩 과정

51 이미지 압축 표준 (계속) 전처리(pre-processing) DWT 양자화
타일화(tiling): 이미지를 서로 겹쳐지지 않는 같은 크기의 직사각형 타일(tile)들로 분할 이미지들을 여러 개의 요소 평면(component plane)들로 나누는 과정 DWT 웨이블릿 변환을 적용하여 각각의 타일을 높은 서브밴드(high subband)와 낮은 서브밴드(low subband)로 분해(decomposition) 0부터 32 단계(level)까지 지원 양자화 웨이블릿 변환의 결과로 얻은 웨이블릿 계수를 양자화

52 타일(tile)의 분할(partition)
이미지 압축 표준 (계속) EBC(Embedded Block Coding) 서브밴드가 서로 같은 크기의 코드 블록(code-block)들로 나눠짐 엔트로피 코딩이 각각의 코드 블록에 대하여 독립적으로 수행 EBCOT(EBC with Optimized Truncation) 알고리즘 사용 4행 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 64 … 65 타일(tile)의 분할(partition) 및 서브밴드와 구역과 코드 블록 비트 평면 코딩을 위한 스캔 형태

53 이미지 압축 표준 (계속) 비트율 조정(rate control) 비트 스트림 구성(bitstream organization)
후처리 작업 대상으로 하는 비트율에 도달할 수 있도록 코드 스트림(code-stream)을 바꾸는 과정 비트 스트림 구성(bitstream organization) 비트 평면 코딩 패스로부터의 압축된 데이터를 패킷(packet)들로 분리 구역(precinct): 하나의 해상도 수준 내에서 코드 블록들의 집합 각각의 구역이 하나의 패킷 패킷은 헤더와 압축된 데이터로 구성됨 패킷들이 특정 순서로 하나의 코드 스트림을 만듦

54 이미지 압축 표준 (계속) 코드 스트림의 구성

55 이미지 압축 표준 (계속) JPEG과 JPEG2000의 이미지 비교 예) [JPEG: 37 KB]

56 이미지 압축 표준 (계속) GIF (Graphics Interchange Format) 그래픽 정지 영상 표준 포맷
Compuserve™의 표준 정지 영상 포맷 8bpp(bit-per-pixel) 정지 영상을 대상으로 함 256 색상(8 bit)을 표현할 수 있음 참색상(24 bpp) 영상을 GIF로 인코딩하는 경우 색상테이블에 정의된 256 개의 색상으로 양자화 색상 정보를 잃어버리게 됨 렘펠-지프-웰치(LZW) 코딩을 이용 렘펠-지프 코딩의 개선된 기법 색상 정보 이외의 다른 정보는 손실되지 않음 타입(flavor) GIF87a, GIF89a(애니메이션 지원)

57 이미지 압축 표준 (계속) RGB 각 값들에 대하여 8 bit씩 할당되어, 256 가지로 색인된 색상을 표현 비트(bits)
바이트(byte) # 1 2 3 4 5 6 적색 강도(intensity) 녹색 강도(intensity) 청색 강도(intensity) . 색상 색인 0에 대한 적색 값 색상 색인 0에 대한 녹색 값 색상 색인 0에 대한 청색 값 색상 색인 1에 대한 적색 값 색상 색인 1에 대한 녹색 값 색상 색인 1에 대한 청색 값 GIF 색상테이블

58 오디오 압축 기법 G.72X 표준 제한된 대역의 전화 채널상에서 음성의 효율적인 코딩을 지원
화상회의나 모뎀과 같은 다양한 원격통신(telecommunication) 응용에 적용 ADPCM 일련의 데이터의 연속된 샘플의 값들 사이의 차이만을 인코딩하고 저장함으로써 압축을 하는 방식 ITU의 음성 압축 표준인 G.721, G.723, G.726, G.727의 핵심 기법 32 kbps에서 음성이 인지되는 품질 표준 64 kbps PCM 전송시보다 약간 떨어짐 DPCM보다 좋음

59 오디오 압축 기법 (계속) G.721: 첫 번째 표준으로, 300에서 3400 Hz의 대역폭을 가진 채널 상에서 32 kbps ADPCM으로 음성을 압축 G.723: G.721 ADPCM의 24, 40 kbps로의 확장 G.726: 1990년에 G.721과 G.723을 대체함, 16, 24, 32, 40 kbps에서의 데이터 압축 지원 G.722: G.726의 개선된 버전으로, 0에서 8 kHz의 광대역(broadband) 전화 채널 상에서 64 kbps내의 7 kHz 오디오 코딩

60 오디오 압축 기법 (계속) MPEG 오디오 압축
Philips™에 의해 개발된 MUSICAM 시스템을 기반으로 한 압축 방법에 따라 표준화 청각 심리 모델(psychoacoustic model) 이용 인간의 사운드에 대한 감각적인 특성을 모델링 3가지 계층 1 계층: 디지털 오디오 테이프 2 계층: 1 계층 보다 높은 복잡도 지님, 디지털 오디오 방송 3 계층: 가장 복잡, ISDN 선상에서의 오디오 전송을 목표로 시작 MP3가 이에 해당 MPEG-1 layer 2 : 32 kHz, 44.1 kHz, 48 kHz에서 샘플링

61 오디오 압축 기법 (계속) 입력에 필터를 적용시켜 주파수 요소로 분해
데이터에 청각 심리 모델(psychoacoustic model) 을 적용시켜 블록에 비트할당을 한 후 양자화 기본적인 MPEG 오디오 인코딩 과정

62 오디오 압축 기법 (계속) MPEG-1 layer 2 MPEG-2 MP3 (MPEG-1 layer 3) MPEG-4
순방향 적응적(forward adaptive) 비트 할당 부분 비트 양자화 사용 MPEG-2 MPEG-1 오디오에 유연성(flexibility) 추가 MPEG-1 샘플링 속도의 ½에 해당하는 샘플링 속도 추가 다채널(multichannel)로 확장 DVD를 지원하는 표준 차량 등에 널리 쓰임 MP3 (MPEG-1 layer 3) 압축 효율이 큼 MPEG-4 음성 압축(speech compression), 지각 기반 코더(perceptual coder), TTS, MIDI 등 여러 가지 다른 오디오 요소들을 하나의 표준으로 통합

63 오디오 압축 기법 (계속) 서브밴드 코딩 (Subband Coding)
아날로그 신호를 주파수 대역 상에서 다수 개의 주파수 대역으로 분리하고, 그 후에 각 아날로그 신호에 대해 코딩 방법을 적용 선택적인 주파수 변환 기법 주파수 대역 등의 스펙트럼의 미리 정의된 영역에서만 신호를 다룸 대역의 개수가 중요한 품질의 척도 보통 32개의 서브밴드를 사용 장점 음성 압축에 잘 적용됨: 인간의 청각 특성을 이용한 처리가 용이 에너지가 편중된 주파수 대역에 더 많은 비트를 부여하여 양자화함으로써 청각적인 오류를 최소화함 서로 다른 주파수 대역에 대한 코딩 과정에서 일어날 수 있는 양자화 에러는 각 주파수 대역간에 서로 무관

64 * DS(DownSampling): 신호의 샘플링 개수를 줄이는 것
오디오 압축 기법 (계속) 음성 신호는 각 주파수 대역 별로 구분된 여러 개의 대역 통과 필터(BPF: Band Pass Filter)를 통과해 분리된 신호를 얻음 * DS(DownSampling): 신호의 샘플링 개수를 줄이는 것 서브밴드 코딩의 인코딩 과정

65 동영상 압축 표준 H.261 1990년에 ITU-T에 의해 제정된 동영상 압축 표준
ISDN 전화선 상에서 대화형 멀티미디어 응용을 위해 고안됨 64kbps의 배수만큼의 전송대역폭을 필요로 함(px64, p:1~30) 압축/복원 두 과정에 의한 시간 지연 < 0.15초 대상으로 삼고 있는 동영상 CIF(Common Intermediate Format) QCIF(Quarter-CIF) 동영상 포맷 밝기 정보 해상도 색채 정보 압축되지 않은 경우 전송률(Mbps) – 30프레임/초 H.261 지원 QCIF 176ⅹ144 88ⅹ72 9.1 Yes CIF 352ⅹ288 36.5 Optional 테이블 추가 블록과 매크로 블록 서브샘플링(2:1:1) 기법에 의해 하나의 밝기 정보(luminance) Y와 두 개의 색채 정보(chrominance) Cb, Cr로 나뉘어 인코딩 블록(block): 8 x 8 픽셀 매크로(macro) 블록: 네 개의 Y블록과 이에 대응하는 한 개씩의 Cb, Cr블록

66 동영상 압축 표준 (계속) 블록과 매크로 블록 서브샘플링(2:1:1) 기법에 의해 하나의 밝기 정보(luminance) Y와 두 개의 색채 정보(chrominance) Cb, Cr로 나뉘어 인코딩 블록(block): 8×8 픽셀로 이루어진 단위 매크로(macro) 블록: 네 개의 Y 블록과 이에 대응하는 한 개씩의 Cb, Cr 블록 영어 수정 H.261의 블록과 매크로 블록

67 동영상 압축 표준 (계속) 코딩 알고리즘 인트라코딩(intra-frame coding)
프레임 자체를 인코딩 JPEG의 순차적 부호화 기법과 유사 DCT, 양자화, 허프만 코딩을 이용 공간적 중복성(spatial redundancy)을 제거 인터코딩(inter-frame coding) 매크로 블록들과 그 이전의 기준 프레임의 매크로 블록들간에 존재하는 차이 정보를 이용 움직임 보상 기법을 이용 시간적 중복성(temporal redundancy)을 제거

68 동영상 압축 표준 (계속) 움직임 보상 기법(motion compensation)
매크로 블록들 사이의 움직임 벡터와 차이 정보로 화면을 인코딩하는 방법 인코딩하려는 프레임과 기준 프레임의 매크로 블록들을 대응 위치의 차이는 움직임 벡터 (motion vector)를 이용하여 표현 매크로 블록들 사이의 차이 정보가 일정 임계값(threshold)을 넘는 경우, DCT, 양자화, 허프만 코딩을 이용하여 차이 정보를 인코딩 움직임 보상 기법의 예

69 동영상 압축 표준 (계속) H.263 1995년에 ITU-T에 의해 제정된 동영상 압축 표준
대화형 멀티미디어 응용을 지원하는 향상된 비디오 코드화 표준 일반 전화망(PSTN, Public Switched Telephone Networks) 사용 64kbps이하의 낮은 전송률을 대상 예) PC, 디지털 카메라, 화상 전화, 감시 카메라, 핸드폰, 멀티미디어 플레이어 등

70 동영상 압축 표준 (계속) 대상으로 삼고 있는 동영상 sub-QCIF 4CIF 16CIF
CIF(Common Intermediate Format) QCIF(Quarter-CIF) 동영상 포맷 밝기 정보 해상도 색채 정보 압축되지 않은 경우 전송률(Mbps) – 30프레임/초 H.263 지원 Sub-QCIF 128ⅹ96 64ⅹ48 4.4 Yes QCIF 176ⅹ144 88ⅹ72 9.1 CIF 352ⅹ288 36.5 Optional 4CIF 704ⅹ576 146.0 16CIF 1408ⅹ1152 583.9 성능을 향상시키기 위해 협상가능한 4개의 코딩 옵션

71 동영상 압축 표준 (계속) 코딩 알고리즘 H.261과 유사 차이점 인트라코딩: 변환 코딩 인터코딩: 예측 코딩
GOB(Group Of Blocks) 고정 크기가 아님 이미지의 왼쪽 경계에서 시작해서 오른쪽 경계에서 끝남 사용할 수 있는(negotiable) 4개의 코딩 option Unrestricted motion vector mode Syntax-based arithmetic coding mode Advanced prediction mode PB-frames mode

72 동영상 압축 표준 (계속) 움직임 보상 기법 움직임 벡터가 수평, 수직 성분의 중간(median) 값으로부터 예측됨
MV(u, v)에 대해 에러 벡터인 (∂u, ∂v)가 코딩 (∂u = u - up, ∂v = v - vp) up = median(u1, u2, u3), vp = median(v1, v2, v3) H.263의 이동 벡터의 예측

73 동영상 압축 표준 (계속) 품질을 향상시키기 위해 반픽셀 정밀도(half-pixel precision)를 지원
쌍선형 보간법(bilinear interpolation) 이용 H.263의 반픽셀 예측

74 동영상 압축 표준 (계속) MPEG (Motion Picture Experts Group)
국제 표준화 기구(ISO: International Organization for Standardization)와 국제 전기 표준 회의(IEC: International Electrotechnical Commision) 가 구성한 공동 위원회(JTC1: Joint Technical Committee 1) 산하의 전문 부윈원회(SC29: Sub-Committee 29)를 지칭 1988년에 설립 동영상과 오디오 압축과 압축된 정보를 전송하는 방법 등에 대한 표준을 제정

75 동영상 압축 표준 (계속) MPEG-1 1991년에 ISO에 의해 승인된 표준 대화형 및 검색형 멀티미디어 응용에 모두 사용
CD-ROM 등의 일반 디지털 저장매체를 대상으로 함 1.5 Mbps의 전송률의 일반 디지털 저장 매체를 대상 JPEG과 H.261 표준에 사용된 기술 흡수 및 호환성 제공

76 동영상 압축 표준 (계속) MPEG-2 1994년에 ISO에 의해 승인된 표준
고품질 디지털 비디오, TV, HDTV의 압축과 복원 2 ~ 45 Mbps의 전송률 지원 MPEG-1과 H.261 등 기존 표준들과의 호환성 제공 여러 단계(level)를 정의: 각 단계마다 거기에 적합한 응용들의 특성에 맞게 여러 프로파일(profile)들이 정의 사운드 데이터에 있어서도 많은 확장이 이루어짐 동영상 압축 방식: DCT를 기반 MPEG-3 흡수: MPEG-2가 HDTV 응용을 지원

77 동영상 압축 표준 (계속) MPEG-4 1999년에 ISO에 의해 승인된 표준
사용자와 서비스 제공자와의 쌍방향 통신을 지원하고, 통신, 컴퓨터, 방송기기 등의 여러 매체들을 통합하려는 목적으로 개발됨 이동(mobile) 환경에서 멀티미디어 통신을 지원 5 kbps ~ 10 Mbps의 낮은 전송률로 동화상을 보내고자 개발된 압축과 복원

78 요약 멀티미디어 데이터 압축의 개념과 그 필요성 압축 알고리즘 이미지 압축 표준 오디오 압축 기법 동영상 압축 표준
저장 공간의 절약과 전송 대역폭을 효율적으로 사용하기 위해 압축 알고리즘 무손실 압축: 반복길이 코딩, 허프만 코딩, 렘펠-지프 코딩 손실 압축: 변환 코딩, 예측 코딩, 양자화, 웨이블릿 코딩, 보간법, 프랙탈 압축 이미지 압축 표준 JPEG, JPEG2000, GIF 오디오 압축 기법 G.72X, MPEG 오디오 압축, 서브밴드 코딩 동영상 압축 표준 H.261, H.263, MPEG

79 참고문헌 김명호, 이윤준 공저, 멀티미디어 개념 및 응용 (개정판), 홍릉과학출판사, 1997
Ze-Nian Li, Mark S.Drew, Fundamentals of Multimedia, Pearson Prentice Hall, 2004 Peter Symes, Video Compression Demystified, McGraw-Hill, 2001 Ralf Steinmetz, Klara Nahrstedt, Multimedia Fundamentals, volume 1: Media Coding and Content Processing, Prentice Hall PTR, 2002, Chapter 7 Al Bovik et al., Handbook of Image and Video Processing, Academic Press, 2000, Section Ⅴ, Ⅵ Vasudev Bhaskaran, Konstantinos Konstantinides, Image and Video Compression Standards, Kluwer Academic Publishers, 1997 Ralf Steinmetz, Klara Nahrstedt, Multimedia: Computing, Communications, and applications, Prentice Hall PTR, 1995 Prabhat K.Andleigh, Kiran Thakrar, Multimedia Systems Design, Prentice Hall PTR, 1996, Chapter 1, 2

80 참고문헌 (계속) John F. Koegel Buford, Multimedia Systems, Addison-Wesley, 1994, Chapter 6 신동일, 신동규 공저, 멀티미디어 데이터베이스 개론, 인터비젼, 2002, 부록 최윤철, 고 견, 임순범 공저, 멀티미디어 배움터(개정판), 생능출판사, 2003 강현배, 김대경, 서진근 저, 웨이블릿 이론과 응용, 아카넷, 2001년 오영환 저, 음성언어 정보처리, 홍릉과학출판사, 1998, 제8장 이석규 외, 멀티미디어의 세계, 한국전자통신연구소, 1993 ABRAHAM LEMPEL and JACOB ZIV, “A Universal Algorithm for Sequential Data Compression,” IEEE Transactions on Information Theory, May 1977.

81 참고문헌 (계속) Shuzo Saito and Kazuo Nakata, Fundamentals of Speech Signal Processing, Academic Press, 1985. Yuval Fisher, “Fractal Image Compression,” SIGGRAPH 92 Course Notes. Gregory K. Wallace, “The JPEG Still Picture Compression Standard,” Communications of ACM, Vol. 34, No. 4, April 1991, pp Charilaos Christopoulos, Athanassios Skodras, Touradj Ebrahimi, “The JPEG2000 Still Image Coding System: An Overview”, IEEE Transactions on Consumer Electronics, Vol.46, No.4, pp , November 2000 Michal W.Marcellin, Michal J.Gormish, Ali Bilgin, Martin P.Boliek, “An Onverview of JPEG-2000”, Proceedings of IEEE Data Compression Conference, pp , 2000. Didier Le Gall, “MPEG: A Video Compression Standard for Multimedia Applications,” Communications of ACM, Vol. 34, No. 4, April 1991, pp

82 참고문헌 (계속) Ming Liou, “An overview of the px64 kbit/s video coding standard,” Communications of ACM, Vol. 34, No. 4, April 1991, pp 웹문서 JPEG: JPEG2000: H.261: H.263: MPEG: