멀티미디어 처리 4장 : 정보압축의 원리 및 기본이론

수업목표 및 내용 정보압축의 원리를 이해한다. 정보압축에 사용되는 기본이론 실험실습 안내 정보압축의 기본적인 원리 이해 공간적, 시간적, 통계적 중복성 제거 원리 정보압축에 사용되는 기본이론 런-길이 부호화 허프만 부호화 변환부호화 이론 양자화 및 역양자화 이론 차분 부호화 이론 실험실습 안내 실습 5: DCT-IDCT 실습 실습 6: 허프만 부호화 실습

[정보미디어의 정보량(압축하지 않았을 때)] 1. 정보압축의 개요 및 필요성 [정보미디어의 정보량(압축하지 않았을 때)] 정보미디어 대표값 정보량(대략) 편지 1000 문자 8 ~ 16 Kbit 신문 14000 문자 x 24 page 336 Kbit ~ 672 Kbit 정지영상(1장) 640x480 해상도의 칼라영상 7.4 Mbit 전화 1시간 230 Mbit 음악(CD) 5.0 Gbit 비디오(VHS 품질) 109 Gbit 현행 아날로그 TV(수신품질) 360 Gbit HDTV (스튜디오 품질) 4320 Gbit

1. 정보압축의 개요 및 필요성 부호화기 (encoder) 복호화기 (decoder) 입력신호 (영상, 음성 등) 미디어 저장 또는 네트워크 전송 복구된 신호 [그림 4-1] 전형적인 정보 압축 시스템 개념도

[그림 4-2] 정보 압축기술 발전의 효과와 필요성 정보압축기술의 발전효과 및 필요성 소형대용량화에 따른 저장공간의 축소 값싼 저장미디어로 멀티미디어 정보를 기록, 저장 정보압축기술의 발달 통신미디어의 발달 방송미디어의 발달 디지털 TV 방송(HDTV) 열화가 없는 고품질 영상전송 가능 다채널화가 가능 다양한 방송미디어의 출현(DMB, ATSC, DVB, ISDB) 저장미디어의 발달 멀티미디어통신이 가능(화상회의, 인터넷 전화등) 정보의 디지털화 [그림 4-2] 정보 압축기술 발전의 효과와 필요성

[그림 4-3] 압축기술(MPEG-2)을 이용한 디지털 방송의 다채널화 정보압축기술의 발전효과 및 필요성 30 Mbps 채널 채널1(MBC): 5 Mbps 채널2 (KBS-1): 5 Mbps 채널3(KBS-2): 5 Mbps 채널4(SBS): 5 Mbps 채널5(EBS): 5 Mbps 아날로그 1채널 정보압축 후 디지털 방송 6채널 6채널 수신가능 1채널 수신 27 MHz 전송대역 채널6(아리랑): 5 Mbps 아날로그 TV 디지탈 TV MPEG-2 시스템 인코더 [그림 4-3] 압축기술(MPEG-2)을 이용한 디지털 방송의 다채널화

[그림 4-4] 색감도 인지능력의 둔감성 예제 영상 2. 정보압축의 기본적인 원리 이해 인간의 시각/청각 특징을 고려한 압축원리 (a) 색 품질 16비트 설정 (b) 색 품질 32비트 설정 [그림 4-4] 색감도 인지능력의 둔감성 예제 영상 (컴퓨터 디스플레이 설정)

[그림 4-5]사람이 들을 수 있는 가청 주파수 대역 [그림 4-6] 마스킹 효과(masking effect) 정보압축기술의 기본적인 원리 사람의 청각 특징을 고려한 사운드 압축원리 [그림 4-5]사람이 들을 수 있는 가청 주파수 대역 [그림 4-6] 마스킹 효과(masking effect)

정보압축기술의 기본적인 원리 영상에서의 공간주파수 (a) 영상 (b) 수평 한 라인에서의 밝기값 변화 [그림 4-7] 영상에서의 공간주파수 개념

[그림 4-8] 다양한 공간 주파수에 대한 예제 영상 정보압축기술의 기본적인 원리 X Y a 밝기값 (a) 공간주파수가 낮은 영상 (b) 공간주파수가 (a) 영상에 비해서 약간 높은 영상 (c) 공간주파수가 (a) 영상에 비해서 높은 영상 [그림 4-8] 다양한 공간 주파수에 대한 예제 영상

정보압축기술의 기본적인 원리 공간적 중복성 제거원리 [그림 4-9] 영상의 공간 중복성

정보압축기술의 기본적인 원리 공간적 중복성 제거원리 (계속) [그림 4-11] 화소의 공간적 중복성 제거 예] [그림 4-12] 차영상: X-(A+C)/2]

정보압축기술의 기본적인 원리 공간적 중복성 제거원리 (계속) (a) 차영상의 히스토그램 (b) 원영상의 히스토그램 [그림 4-13] 원영상과 차영상의 히스토그램

정보압축기술의 기본적인 원리 시간적 중복성 (a) 50 번째 영상 (b) 51 번째 영상 (c) 52 번째 영상 [그림 4-14 Hall Monitor 동영상]

정보압축기술의 기본적인 원리 시간적 중복성 (계속) (a) 51번째 영상과 50번째 영상의 차 (b) 52번째 영상과 51번째 영상의 차 [그림 4-15] 연속된 영상과의 차영상

정보압축기술의 기본적인 원리 시간적 중복성 (계속) [그림 4-16] 움직임 정보의 예

압축기술의 기본적인 원리-시간적 중복성 [그림 4-17] 움직임 보상의 결과 (a) 원영상과 움직임 보상된 51번째 영상과의 차 (b) 원영상과 움직임 보상된 52번째 영상과의 차 (c) 움직임 보상된 51번째 영상 (d) 움직임 보상된 52번째 영상 [그림 4-17] 움직임 보상의 결과

[그림 4-18] 움직임 보상된 52번째 영상의 블록화 현상 압축기술의 기본적인 원리-시간적 중복성 움직임 보상된 52번째 영상         (b) 사각형 영역의 확대 영상 [그림 4-18] 움직임 보상된 52번째 영상의 블록화 현상

기본적인 정보 이론(Information Theory) Claud E. Shannon에 의하면, 로 표현되는 원본 정보의 엔트로피(entropy of source: 소스의 정보량) 비트 Average number of bits per codeword = 여기서, n: 원본 소스의 다른 심볼 번호, : S 에서 기호 가 발생할 확률 예) 네 개의 심볼 발생 확률이 1/4로 동일한 경우와 1/2, 1/4, 3/8, 3/8로 상이할 경우 entropy 상이함

기본적인 정보 이론(Information Theory) [그림 4-19] 정보량과 상관성, 정보량과 발생확률의 개략적인 관계

압축기술의 기본적인 원리 통계적 중복성 제거 엔트로피는 신호가 가지고 있는 평균 정보량이며, 신호는 이 정보를 전달하기 위해 사용된 수단이다. 엔트로피란 신호에 포함된 정보량을 의미하므로, 신호로 이 정보를 모두 표현하기 위해서는 최소한 엔트로피 만큼의 비트가 평균적으로 소요되어야 함을 의미한다. 신호는 엔트로피 이상의 비트로 표현되어야 하며, 엔트로피 이상으로 소요된 정보는 그 만큼 중복성을 가지게 된다. 이러한 중복성을 제거하여 가능한 한 엔트로피에 가깝도록 부호화하는 것을 엔트로피 부호화(entropy coding)라고 한다. 엔트로피 부호화 방식에는 허프만 부호화 (huffman coding)와 산술부호화 (arithmetic coding) 등이 있다.

정보압축에 사용되는 기본적인 원리 [표 4-2] 정보압축원리와 압축이론 압축원리|압축이론 압축이론 시각적/청각적 특징  압축원리|압축이론 압축이론 시각적/청각적 특징 영상의 디지털화 형식(4:2:0, 4:2:2 등) 음성의 마스킹 효과 공간적 중복성 제거 변환 부호화(DCT, Wavelet 변환 등) 양자화 이론 영상: 차분 부호화(DC 계수 부호화에 사용) 시간적 중복성 제거 영상에서의 움직임 예측 및 움직임 보상 이론 예측압축기법 음성: DPCM (Differential Pulse Code Modulation) 통계적 중복성 제거 엔트로피 부호화(허프만 부호화, 런-길이 부호화, 산술 부호화)

압축 알고리즘 분류 압축알고리즘 [그림 4-20] 개략적인 압축 알고리즘 분류 손실압축 무손실 압축 변환압축기법 예측압축기법 엔트로피 압축기법 길이가변부호화 통계적 부호화 허프만부호화 산술부호화 [그림 4-20] 개략적인 압축 알고리즘 분류

런-길이 부호화 (Run-Length Encoding) AAAABBBBBCCCCCCCCDEEEE  22 byte 런-길이 부호화 4A5B8C1D4E  10 byte 1 문자 = 1 byte 가정 [그림 4-21] 런-길이 부호화 알고리즘 적용 예

런-길이 부호화 (Run-Length Encoding) 000000011111111110000011… 런-길이 부호화 0 7 1 10 0 5 1 2…  7 10 5 2…  또는 처음 신호가 0 이라고 가정하면 [그림 4-22] 런-길이 부호화 알고리즘 적용 다른 예

런-길이 부호화 (Run-Length Encoding) FAX 압축, GIF 등이 run length coding을 이용 그림 파일 압축 효과가 크고, 원리가 단순 그러나, 문서 파일 압축에는 부적합 파일 종류 압축 전 압축 후 압축률 문서 파일 14,862 29,506 199% 그림 파일 96,062 38,328 40% 프로그램 파일 24,576 15,198 62%

런-길이 부호화의 단점 예) “This is a pen.” This is a pen. 압축 후 두 배로 커짐. This is a pen. T1h1i1s1 1i1s1 1a1 1p1e1n1.1

허프만 부호화 개요 David Huffman(1952)에 의해 알고리즘 제시 자료군의 분석에 의해 매우 빈번하게 발생하는 자료에 짧은 비트 스트림할당, 드물게 발생하는 자료에 긴 비트스트림을 할당하는 가변길이 압축기법 toupee t o u p e (48 bit) 111 0100 10111 10110 100 (23 bit) 압축률 : 2.08

허프만 부호화 엔트로피 : 신호의 평균 정보량 예를 통해 본 부호의 할당과 엔트로피 아래 2가지 경우에 대해 각 심볼에 ‘0’과 ‘1’의 부호를 부여하였다고 하자 (사례1) 2개의 심볼이 각각 0.5, 0.5의 확률을 가지는 경우 (사례2) 2개의 심볼이 각각 0.75, 0.25의 확률을 가지는 경우 효율적인 부호화  사례1 수신자입장에서 보면 사례1의 경우 송신자가 심볼을 전송하지 않으면 송신자가 보내려고 하는 심볼이 ‘0’인지 ‘1’인지 알아맞추기가 사례2의 경우보다 어려움(즉, 좀 더 불확실)  사례1이 정보량이 큼  사례1과 사례2에서 1비트로 각 심볼을 부호화하였을 때 사례1의 1비트 심볼이 더 많은 정보를 보유->결국 0과 1을 부여함

허프만 부호화 2개 보다 많은 심볼의 경우 1) 다수의 심볼을 2개의 부류로 분할하고 각 부류를 하나의 심볼로 간주하면 2개의 심볼로 생각할 수 있음 2) 2개의 부류를 나눌 때 각 부류에 속한 심볼의 확률의 합이 각각 0.5에 가깝도록 분류하고 각 부류에 대해 ‘0’과 ‘1’의 부호를 부여 3) 각 부류 내에 속한 심볼들을 다시 두개의 부류로 분류하고 다시 ‘0’과 ‘1’을 할당. 2)에서 ‘0’이 부여된 부류라면 2)에서 부여된 부호 ‘0’을 앞에 붙혀 ’00’ 또는 ’01’이 됨. 4) 2)의 과정을 3)처럼 계속 반복함

허프만 부호화 전체 심볼을 0.5의 확률에 가깝도록 두 부류로 분류  {s0} 와 {s1, s2, s3}  두 부류를 구별하기 위하여 ‘0’과 ‘1’의 코드를 부여함  s0 = ‘0’ 3개의 심볼을 포함하는 {s1, s2, s3} 를 다시 반반의 확률을 가지도록 분류  {s1}과 {s2, s3}  각 부류에 ‘0’과 ‘1’의 코드 부여  s1 = ’10’ 2개의 심볼을 포함하는 {s2, s3} 를 다시 반반의 확률을 가지도록 분류  {s2}과 {s3}  각 부류에 ‘0’과 ‘1’의 코드 부여  s2 = ’110’, s3 = ‘111’

허프만 부호화 허프만 부호화 알고리즘 아래는 널리 알려진 알고리즘으로서 앞 슬라이드에서 설명한 방법과 상이하나(역과정에 해당) 원리에 있어서 동일하며 각 심볼에 할당되는 비트수는 동일함 알고리즘 원래의 모든 심볼들을 각기 독립된 노드인 자유 노드들로 간주한다. 가장 낮은 빈도수를 가진 두 개의 자유 노드들을 자식 노드로 하는 하나의 부모 노드를 생성하고 두개의 자식노드는 각각 ‘0’과 ‘1’의 부호가 부여된다. 생성되는 부모 노드의 빈도수는 자식 노드들의 합으로 이루어진다. 연결한 두 개의 자식 노드들을 자유 노드 리스트에서 제거한다. 새롭게 생성된 부모 노드를 리스트에 추가한다. 2단계와 3단계를 하나의 자유 노드만 남을 때까지 반복 수행한다. 이 자유 노드는 구성되는 트리의 루트가 된다. 마지막 남은 자유 노드에서 출발하여 원래의 자유노드(원래의 심볼)까지 부여된 부호를 읽음으로써 심볼의 부호를 결정한다.

허프만 부호화 사례

[참고]데이터의 부호화 – 허프만코드 허프만(Huffman)코드 가변길이 코드방법 - 정보량에 따라 길이가 달라진다 데이터 압축 기법 무손실(lossless coding) 부호화 기법 정보에 따른 확률 트리 예 정보 나타날 확률 2진부호 허프만부호 A 0.5 00 1 B 0.25 01 C 0.125 10 001 D 11 000 평균 부호 길이 2bit 1.75bit

[참고]허프만 부호화 현재 사용되는 대부분의 압축 기법에 이용 기본 원리: 다양한 길이의 코드(부호) 예) 파일에서 각 문자가 등장하는 빈도가 다름. 예, A는 100번, &는 3번, ... 빈도가 높은 문자는 짧은 코드, 빈도가 적은 문자는 긴 코드로 부호화한다. 예) A와 &를 모두 8비트 코드로 표현 100X8 + 3X8 = 824비트 A를 2비트, &를 10비트로 표현 100X2 + 3X10 = 230비트

허프만 부호화 허프만 코드의 생성 빈도수에 따른 문자의 빈도수 배열 생성 이진 트리를 이용하여 허프만 테이블 생성 빈도수에 따른 문자의 빈도수 배열 생성 이진 트리를 이용하여 허프만 테이블 생성 1. 처음에는 모든 문자들을 각기 독립된 노드인 자유노드로 간주 2. 가장 낮은 빈도수를 가진 두개의 자유 노드들을 자식 노드로 하는 부모 노드 생성.생성되는 부모 노드는 자식 노드들의 합과 동일한 가중치를 가짐 3. 연결한 두 개의 자식 노드들을 자유 노드 리스트에서 제거하고, 새롭게 생성된 부모 노드를 리스트에 추가 4. 2단계와 3단계를 하나의 자유 노드만 남을 때까지 반복

변환 부호화 이론 한 영역에서 다른 영역으로 변환한 후 압축한다. FFT (Fast Fourier Transform) DCT (Discrete Cosine Transform) : 2D, 8 x 8 FDCT (Forward DCT) 여기서, IDCT (Inverse DCT)

[그림 4-25] 일반적인 직교변환(주파수성분의 분해)에 대한 개념도 변환 부호화 이론 = a1 x + a2 x + a3 x + a4 x + a5 x + a6 x + a7 x + a16 x + ……. 제1저주파항 제2저주파항 공간주파수 증가 고주파항 [그림 4-25] 일반적인 직교변환(주파수성분의 분해)에 대한 개념도

변환 부호화 - DCT [그림 4-26] Forward DCT 변환 원리

변환 부호화 - DCT [그림 4-27] DCT 계수값에 대한 주파수 분포 [그림 4-28] DCT 변환 예

[그림 4-29] 64 개의 DCT 기본 함수(basis function)

변환부호화 - DCT (a) 128 x 128 Lenna 영상 (b) Lenna DCT 변환계수 영상 (c) 128 x 128 Citrus 영상 (d) Citrus DCT 변환계수 영상

[그림 4-30] Lenna 영상의 압축화질 비교(압축률 70:1) 웨이블릿 변환 5장에서 자세히 설명 정지영상 압축 표준인 JPEG2000에서 사용 (a) JPEG2000 (b) JPEG [그림 4-30] Lenna 영상의 압축화질 비교(압축률 70:1)

[그림 4-31] 양자화 테이블 예: (a) Y를 위한 양자화 테이블(); 양자화(Quantization) [그림 4-31] 양자화 테이블 예: (a) Y를 위한 양자화 테이블(); (b)  Cb, Cr을 위한 양자화 테이블()

[그림 4-32] 양자화 테이블을 이용한 양자화 과정 양자화(Quantization) [그림 4-32] 양자화 테이블을 이용한 양자화 과정

양자화(Quantization) [그림 4-33] 양자화와 역양자화 과정 예

차분 부호화 (Differential encoding)  [그림 4-34] 8x8 블록들을 DCT변환 후 DC 계수들에 대한 차분부호화 개념도

차분 부호화 (Differential encoding)  [그림 4-35] PCM 블럭도

차분 부호화 (Differential encoding) [그림 4-36] 아날로그 음성신호를 PCM 하는 과정에서의 신호형태

차분 부호화 (Differential encoding) 14 13 [그림 4-37] 차등적 펄스코드 변조(DPCM) 압축이론 개념도