Lecture #6 멀티미디어 데이터 압축 & 복원

강의 개요 데이터 압축 개요 데이터 압축 기법 종류 엔트로피 코딩 기법 소스 코딩 기법 하이브리드 코딩 기법 RLE(Run-Length Encoding) Huffmann Coding Arithmetic Coding 소스 코딩 기법 변환 코딩 : DCT Coding 차분 코딩 : DPCM Coding 하이브리드 코딩 기법

압축과 복원 개요(1) 멀티미디어 데이터 압축의 필요성 멀티미디어 데이터의 대용량성  대용량의 기억 장치를 요구 멀티미디어 데이터의 실시간성  기존의 네트워크의 대역폭이나 저장장치의 입출력 대역폭이 멀티미디어 데이터의 실시간 재생에 부적합 결론 : 저장 및 전송되는 데이터 양을 줄이기 위해 데이터 압축 기술이 필요

압축과 복원 개요(2) 640*480 해상도, 24-bit 칼라의 비디오 데이터의 요구대역폭: 데이터 전송 대역폭 : 1) 한 프레임에 필요한 데이터: 640 * 480 * 24 bits = 7.03 Mbps 2) 초당 필요한 대역폭: 30 fps 전제 640 * 480 * 24 bits * 30 frames = 210.9 Mbps 3) 90분 상영 데이터의 저장공간: 210.9 Mbps * 90 분 * 60 초 = 1112.2 Gbits 데이터 전송 대역폭 : 4) 저속의 인터넷 대역폭: 10Mbps or 100Mbps 5) 24 배속 CD-ROM의 입출력 대역폭: 153.6KB * 24 배속 * 8 bits = 28.8 Mbps

압축과 복원 개요(3) 압축 및 복원의 원리 멀티미디어 데이터는 데이터 중복성(Data Redundancy)을 갖는다 중복 데이터를 제거하면 멀티미디어 정보를 표현하는 데이터를 줄일 수 있다 데이터 중복성 공간적(spatial) 중복 시간적(temporal) 중복 심리시각(psyco-visual) 중복 낮은 주파수에 민감하고 높은 주파수에 둔감 인간의 인지 능력을 고려한 중복 데이터 제거 데이터 코딩(Data Coding) 중복 데이터를 제거하여 새롭게 줄여 데이터를 표현한다는 의미 데이터 압축(data compression) 보다는 일반적인 개념

압축과 복원 개요(4) 압축의 측도 압축률(Compression Rate) bpp(bits per pixel) 압축률 = 원래 데이터의 크기 / 압축된 데이터의 크기 압축 시스템의 효율을 측정하기 위해 사용 압축률과 화질 사이에는 반비례 관계 bpp(bits per pixel) bpp = 압축된 데이터의 비트 수 / 픽셀 수 화질(picture quality)의 측도 bpp와 화질 사이의 관계 : 표 4.1 참조

압축 기법 종류 (1) 정보 이론에서의 코딩(Coding) Shannon의 통신 시스템 모델 : 그림 4.1 2가지 형태의 정보 코딩이 필요 데이터 압축 : 엔트로피 코딩(Entropy Coding) / 소스 코딩(Source Coding) 에러 제어(Error Control) : 채널 코딩(Channel Coding) 인코더 채널 디코더 Source (송신측) Destination (수신측) 압축 에러제어

압축 기법 종류 (2) 압축 기법의 특성 : 표 4.2 무손실(Lossless) 압축 / 손실(Lossy) 압축 프레임내(Intraframe) 압축 / 프레임간(Interframe) 압축 대칭(Symmetrical) 압축 / 비대칭(Asymmetrical) 압축 실시간(Real-time) 압축 스케일러블(Scalable) 압축

압축 기법 종류 (3) 멀티미디어 시스템의 압축 기법 : 표 4.3 엔트로피 코딩(Entropy Coding) 손실없는(lossless) 압축기법 데이터의 semantic을 고려하지 않는다 멀티미디어 데이터의 매체별 특성을 고려하지 않고 단순히 비트나 바이트 스트림으로 간주하여 압축 소스 코딩(Source Coding) 손실있는(lossy) 압축기법 데이터의 semantic을 고려 원래 데이터를 표현하는데 적합한 데이터와 부적합 데이터로 분리하고 부적합한 데이터를 제거하여 압축 예측코딩(Predictive Coding) / 변환코딩(Transformation) 등

압축 기법 종류 (4) 멀티미디어 시스템의 압축 기법 (계속) 하이브리드 코딩(Hybrid Coding) 엔트로피 코딩 기법과 소스 코딩 기법을 결합하여 사용 그림 4.2 참조 소스 코딩의 결과를 엔트로피 코딩의 입력 데이터로 사용 예 : JPEG 압축 기법에서 DCT 코딩과 RLE 코딩 기법의 결합

엔트로피 코딩 엔트로피(Entropy) 코딩 엔트로피 코딩 종류 엔트로피(entropy) 엔트로피 코딩 불확실성에 대한 양(the amount of uncertainty) 주어진 심볼들에 의해 얻을 수 있는 평균 정보 양을 비트 수로 표현 엔트로피 코딩 원래의 자료를 좀더 효율적으로 표현하기 위해 통계적 중복성을 사용하는 인코딩 방법 엔트로피 코딩 종류 Run-Length Encoding Huffmann Coding Arithmetic Coding

RLE(Run-Length Encoding) Run-Length Encoding(RLE) 연속적으로 반복되는 데이터를 반복 정보와 데이터로 표현함으로써 데이터 양을 줄이는 코딩 기법 가장 기본적인 코딩 기법 GIF 형식 등에서 적용 예: 압축전의 데이터: 22 바이트 PRSSSSSSSSTTBVVVVVVVMM Run-Length Encoding: 13 바이트 PR!8STTB!7VMM

Huffman Coding (1) 허프만 코딩(Huffman Coding) 원래 데이터를 구성하는 요소에 대해 출현 빈도를 나타내는 확률이 주어지면 다음과 같은 코딩으로 최적의 압축을 구하는 코딩 기법 출현 빈도가 높은 문자에는 짧은 코드를 할당 출현 빈도가 높은 문자에는 긴 코드를 할당 가변 길이 코딩(VLC:Variable Length Coding) 방식 압축된 코드 길이가 다양하게 코딩

Huffman Coding (2) 허프만 인코딩(Huffman Encoding) 허프만 인코딩 예: 허프만 코드 생성 알고리즘 : 알고리즘 4.1 허프만 코딩에서는 2진 트리를 이용하여 허프만 코드 테이블을 생성하고 이를 이용하여 코딩한다 다양한 데이터에 대해 허프만 테이블을 생성하는 경우에 코딩 비용이 커진다 허프만 코드를 이용하여 입력 데이터를 인코딩 허프만 인코딩 예: 그림 4.3 문자 A, B, C, D 에 대한 출현 빈도 확률이 P(A) = 1/16, P(B) = 1/16, P(C) = 1/8, P(D) = 3/4 일 때에 허프만 2진 트리는?

Huffman Coding (3) 허프만 2진 트리 생성 과정: P(AB)=1/8 1 1 1 P(A)=1/16 P(ABCD)=1 P(ABC)=1/4 P(AB)=1/8 1 1 1 P(A)=1/16 P(B)=1/16 P(C)=1/8 P(D)=3/4

Huffman Coding (4) 허프만 인코딩 예: 앞의 예에 대한 허프만 코드 테이블: 입력 문자 스트림에 대한 인코딩 : BDDCCDA  001 1 1 01 01 1 000 A 000 B 001 C 01 D 1

Huffman Coding (5) 허프만 디코딩 (Huffman Decoding): 디코딩 트리를 생성하여 허프만 코드 스트림을 디코딩 디코딩 예: 0011101011000 P(A)=1/16 P(B)=1/16 P(C)=1/8 P(D)=3/4 P(ABC)=1/4 P(ABCD)=1 P(AB)=1/8 1 B D D C C D A

Huffman Coding (6) 허프만 인코딩 & 디코딩 예 : 멀티미디어 데이터의 허프만 코딩 http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/huffman.html 멀티미디어 데이터의 허프만 코딩 표준화된 허프만 테이블 사용으로 테이블 구성에 따른 오버헤드를 줄여 압축시간을 단축 화질이 떨어질 가능성이 있다 고화질의 데이터에 대해서는 허프만 테이블을 원래의 데이터에 맞도록 재계산

Arithmetic Coding (1) 산술 코딩(Arithmetic Coding) 허프만 코딩 기법의 단점 데이터의 출현 빈도 확률이 변경되면 허프만 테이블을 재계산하여야 한다 코딩과 모델링이 하나의 프로세스 내에 통합되어 융통성 있는 코딩이 어렵다 산술코딩(Arithmetic Coding) 확률 집합 개념을 이용하여 코딩 [0,1) 사이의 열린 부분 구간을 이용 발생 확률이 높은 데이터는 긴 부분구간을, 발생 확률이 낮은 데이터는 짧은 부분구간을 할당하는 방법으로 압축할 데이터를 새로운 하나의 부동소숫점 값으로 압축

Arithmetic Coding (2) Arithmetic Coding의 부분구간 할당 알고리즘 데이터의 구성 요소의 발생 확률에 따라 비례하여 부분구간을 할당 예 : pp. 150 표 4.4 문 자 확 률 부분 구간 a 0.2 [0, 0.2) e 0.3 [0.2, 0.5) i 0.1 [0.5, 0.6) o [0.6, 0.8) u [0.8, 0.9) ! [0.9, 1.0)

Arithmetic Coding (3) Arithmetic Coding 알고리즘 pp. 151, 알고리즘 4.3 입력 데이터 : “eaii!” 초기 구간 : [0.0, 1.0) Processing ‘e’ : [0.2, 0.5) Processing ‘a’ : [0.2, 0.26) <- ‘e’ 구간을 10등분한 것의 1,2 구간 Processing ‘i’ : [0.23, 0.236) <- ‘a’ 구간을 10등분한 것의 5 구간 Processing ‘i’ : [0.233, 0.2336) <- ‘i’ 구간을 10등분한 것의 5 구간 Processing ‘!’ : [0.23354, 0.2336) <- ‘i’ 구간을 10등분한 것의 9 구간 Coding value = 0.233582 허프만 코딩에서는 문자를 개별적으로 취급하나, Arithmetic Coding은 압축할 데이터를 새로운 하나의 부동소숫점 값으로 압축함으로써 효율이 좋다

Arithmetic Coding (4) Arithmetic Decoding 알고리즘 pp 152, 알고리즘 4.4 표 4.5와 같이 누적 확률 값으로 나타내는 디코딩 표를 이용 Arithmetic decoding 예: 입력 : 압축값= 0.233582 Step #1 초기값: Phigh=1, Plow=0, Range=1 Step #2 디코딩 문자 선택 : Cprobi <= (input – Plow) < Cprobi-1 을 만족하는 i을 결정하고 디코딩 표에서 문자를 선택 Step #3 변수 Update: Phigh = Plow + Range * Cprobi-1 Plow = Plow + Range * Cprobi Range = Phigh - Plow Step #4 마지막 문자가 아니면 goto Step #2

Arithmetic Coding (5) Arithmetic Coding 의 특징 허프만 코딩 기법보다는 효율적이다 허프만 코딩은 문자를 개별적으로 코딩 산술 코딩은 압축할 데이터 전체를 처리하여 하나의 압축 값을 생성 부동소숫점 계산에 따른 오버헤드와 구현과정의 복잡성으로 인해 허프만 코딩이 주로 이용된다 최근 하드웨어의 처리 속도가 빨라짐에 따라 멀티미디어 압축 기법에서 엔트로피 코딩 기법으로 산술 코딩을 선택한다

소스 코딩(Source Coding) 소스 코딩(Source Coding) 인간의 감각 기관의 특성을 이용한 압축 기법 원래의 데이터를 인간이 인식할 수 있는 부분과 인식할 수 없는 부분으로 나눈다 인간이 인식할 수 없는 부분을 축소 또는 제거하여 압축 손실 압축 기법(Lossy Compression) 인간이 인식할 수 없는 부분을 제거하고 인식할 수 있는 부분만으로 복원하더라도 인간은 차이를 알지 못한다 종 류: 예측 코딩(Predictive Coding) : DPCM, ADPCM 등 변환 코딩(Transformation Coding) : DCT, DWT 등

변환 코딩: DCT Coding (1) DCT(Discrete Cosine Transform) Coding 이미지 및 비디오 데이터 압축의 기반 기술 특 징 공간 영역을 주파수 영역으로 변환하여 인간의 시각 시스템의 특성을 반영하여 코딩한다 이미지 및 비디오 데이터의 공간 및 시간 중복 데이터를 효율적으로 제거 상관 관계가 높은 데이터의 경우에 압축 효율이 최적 직교성(orthogonal)을 가지고 있어 역함수가 간단 빠른 알고리즘 구현이 가능

변환 코딩: DCT Coding (2) DCT에 의한 압축 알고리즘: pp. 156, 그림 4.4 4 개의 주요 단계로 구성 Hybrid Coding DCT에 의한 압축 알고리즘: pp. 156, 그림 4.4 4 개의 주요 단계로 구성 단계 1: 전처리 단계로서 원래의 디지털 이미지를 8 X 8 블록 으로 분할 단계 2: DCT 변환단계로서 공간 영역을 주파수 영역으로 변환 단계 3: 양자화(Quantization) 단계로 중요하지 않은 정보를 축소 및 제거 단계 4: 엔트로피 코딩 단계로 양자화 된 DCT 상수를 압축

변환 코딩: DCT Coding (3) DCT 압축 시스템의 전처리 단계: pp. 156, 그림 4.5 압축할 데이터를 아날로그 형태에서 디지털 형태로 변환 소스 디지털 데이터를 2차원 행렬로 표현 흑백 데이터 : 하나의 2차원 행렬 칼라 데이터 : 여러 개의 2차원 행렬 압축할 데이터를 N x N 픽셀로 구성된 블록으로 분할 일반적으로 N = 8 을 적용 메모리을 적게 차지하며 계산이 단순 큰 블록을 적용하더라도 압축 효율이 개선되지 않는다 예제: 256 칼라의 8 비트 샘플링 데이터, 그림 4.6

변환 코딩: DCT Coding (4) DCT 압축 시스템의 DCT 변환 단계 공간 영역의 데이터를 주파수 영역의 데이터로 변환 1 차원 변환 : 오디오 데이터 코딩 2 차원 변환 : 이미지 데이터 코딩 순방향(Forward) DCT / 역방향(Backward) DCT DCT/IDCT(Inverse DCT) 함수 이용: pp158 DCT 변환 예제: pp 158, 그림 4.7

변환 코딩: DCT Coding (5) DCT 상수 DCT 변환으로 생성된 8 x 8 블록의 픽셀 값 DC(Direct Current) 상수 8 x 8 블록의 첫번째 원소 값 수평 및 수직으로 주파수대가 0인 값 8 x 8 블록의 64개 칼라 값에 대한 평균값 AC(Alternate Current) 상수 DC 상수를 제외한 나머지 상수 DCT 상수의 주파수 분포: pp 160, 그림 4.8 인간의 시각시스템은 저 주파수대에는 매우 민감하게 반응 고 주파수대에는 둔감하게 반응한다 이미지를 압축할 때에 높은 주파수대의 상수는 이미지 인식에 크게 영향을 주지 않으므로 축소 또는 제거 DC 상수만을 이용하여 압축, 복원하더라도 이미지 질에는 큰 영향을 미치지 않는다

변환 코딩: DCT Coding (6) DCT 압축 시스템의 양자화 단계 양자화를 통해 불필요한 정보를 제거 데이터 손실이 발생 DCT 상수를 양자화 행렬로 나누고 가까운 정수로 반올림한다 : 식 4.3, 그림 4.9, 그림 4.10 대부분의 값이 0으로 변환 DC 상수는 64개의 값의 평균으로 가장 크다 0이 아닌 낮은 주파수의 값은 대각선 위에 있다 높은 주파수에 속하는 AC 상수는 대부분 0이다 양자화 상수 / 양자화 행렬 인간의 시각심리적인 요소와 압축률을 고려하여 결정 대부분의 압축 표준에서는 기본값(Default)을 제공

변환 코딩: DCT Coding (7) DCT 압축 시스템의 엔트로피 코딩 단계 양자화된 데이터에 대하여 엔트로피 코딩을 통해 압축률을 높인다  Hybrid Coding 단계 DC 상수의 인코딩 DC 상수는 해당 블록의 기본 칼라를 결정 인접한 블록들 사이의 색상 변화는 크지 않다 DCi와 DCi-1값의 차이는 크지 않다 DC 상수에 대하여 차분 코딩을 적용 : 그림 4.11 AC 상수의 인코딩 지그재그 시퀀스(Zigzag Sequence)을 적용하여 Run-length Encoding 기법을 사용 : pp 163, 그림 4.12

차분 코딩: DPCM Coding (1) DPCM(Differential Pulse Coded Modulation) Coding 차분(Difference) 기반의 예측 코딩 기법 시간적인 중복성을 이용한 압축 기법 시간흐름에 따라 데이터 사이의 변화가 크지 않은 데이터에 적용 압축할 때에 실제 값과 예측 값의 차이를 코딩 오디오 데이터 압축에 주로 이용 기준 데이터 값은 그대로 코딩하고, 이후의 값은 기준 데이터 값에 대한 차분값을 코딩한다 엔트로피 코딩과 결합하는 경우 더욱 효율적으로 이용 DPCM 압축 기법: pp. 164~165

차분 코딩: DPCM Coding (2) PCM vs DPCM

차분 코딩: DPCM Coding (3) DPCM 확장 Delta Modulation ADPCM(Adaptive DPCM) 차분값에 대해 1 비트를 사용하여 증감 여부만을 코딩 차분값의 변화가 심한 경우에는 부정확 ADPCM(Adaptive DPCM) 차분값을 코딩하는 비트 수를 다양하게 사용 변화가 심한 경우에는 많은 비트 수를 사용 변화가 적은 경우에는 적은 비트 수를 사용 DPCM 코딩 기법보다 효율적 Audio coding에 많이 적용

하이브리드 코딩 하이브리드 코딩(Hybrid Coding) 엔트로피 코딩 기법과 소스 코딩 기법을 결합 소스 코딩의 결과를 엔트로피 코딩의 입력을 사용 종 류: JPEG H.261 / H.263 MPEG Wavelet image compression : JPEG2000 Fractal image compression 등

Report #4 Huffmann Coding Programming Report #1에서 작성한 문자 빈도수 계산 루틴을 이용하여 영문 텍스트 파일(*.txt)을 허프만 코딩하는 프로그램을 작성하여라 출력 파일의 확장자 이름을 *.huf로 지정한다 압축률을 산출하여 RLE coding 기법과 비교하여라 참고 사이트 : http://dogma.net/DataCompression/Huffman.shtml