Introductory Image Processing

(1)

제 9 장 영상 압축

[email protected]

Prof. Doo-Hyun Choi

Introductory Image Processing

영상 압축의 기초 (1/2)

 영상 압축

 기본 아이디어: 정보 혹은 데이터의 중복(redundancy)을 최소화하자

 중복의 종류

 부호화 중복성(coding redundancy)

 화소간 중복성(inter-pixel redundancy)

 신경 시각적 중복성(psycho-visual redundancy)

 Etc.

 부호화 중복성(Coding redundancy)

 데이터의 발생 빈도(확률)를 고려하지 않고 부호화할 때 발생

 부호화 중복성을 줄이기 위해 많이 나타나는 데이터는 짧은 코드를, 가끔 나타나는 데 이터는 긴 코드를 할당함  가변 길이 부호화 사용

 부호화 중복성 제거에 사용되는 기법

 호프만 부호화(Huffman coding)

 산술부호화(Arithmetic coding)

 런-길이 부호화(Run-length coding)

Introductory image Processing IISL, School of EECS, KNU

영상 압축의 기초 (2/2)

 화소간 중복성(Inter-pixel redundancy)

 공간적인 중복성, 기하학적 중복성, 프레임 간 중복성 등

 예: 인접한 화소간의 차이가 적은 경우, 밝기 자체를 부호화하는 것보다 차이 성분만 부호화함으로써 적은 데이터 량으로 같은 정보를 유지할 수 있다.

 신경 시각적 중복성(Psycho-visual redundancy)

 인간이 잘 구별하지 못하는 정보는 제거하거나 작은 데이터 량으로 표현한다.

 인간 시각 시스템(Human visual system: HVS)의 특성을 압축에 적극적으로 활용

 비가역 압축

 예: 양자화 과정

(3)

영상 압축의 목적과 응용 분야

 영상 압축의 목적

 원하는 수준의 화질을 최소한의 비트수로 유지하자.

 영상 압축의 응용 분야

 전송: 대역폭을 줄이자.

 디지털 텔레비전

 화상 회의

 팩시밀리

 DMB (Digital multimedia broadcasting)

 Etc.

 저장: 저장 공간을 줄이자.

 DVR (Digital Video Recorder)

 영상저장전송시스템(Picture Archiving and Communication System; PACS)

영상 압축 모델 (1/3)

 영상 부호화 단계

 원 영상  특징 추출  양자화  코드워드 할당  비트열

 양자화: 추출된 혹은 부호화하고자 하는 정보를 몇 단계로 구분하는 과정

 코드워드 할당: 양자화 레벨에 코드를 할당하는 과정

특징 추출의

변환 양자화 코드워드

할당 영상

소스 비트열

(4)

영상 압축 모델 (2/3)

 영상 부호화

 파형 부호화: 영상 자체를 부호화

 변환 계수 부호화: 영상을 변환한 후 변환 계수를 부호화

 엔트로피 부호화

 데이터의 발생 빈도(확률)에 기반해서 가변길이 코드워드를 할당하는 방법

 영상 모델 부호화: 영상 전체 혹은 일부를 모델링한 후 특징 혹은 모델 파라미터를 부 호화하고, 복호시에는 모델 파라미터로부터 합성한다.

 영상 부호화 기술들

엔트로피 부호화

파형 부호화

영상 모델 부호화 영상 부호화 기술

허프만 부호화 산술 부호화

예측 부호화 변환 부호화 부대역 부호화

벡터 양자화

분할 기반 에지 기반 3차원 모델 기반

영상 압축 모델 (3/3)

 압축율과 화질

 압축율 vs. 화질: trade-off

 부호화 알고리즘의 비교: 같은 압축율에서의 화질 비교

 압축율(compression rate)과 비트율(bit-rate)

 화질

 객관적 화질

 첨두 신호대 잡음비(PSNR; peak-to-peak signal to noise ratio)

 평균 제곱 오차(MSE; Mean Squared Error)

 8비트(양자화 레벨 256, P-P는 255)의 경우, PSNR

 주관적 화질: MOS (Mean opinion score) Test

pixel]

per bit [bpp;

,

수 픽셀

비트수 비트율 사용된

용량 영상의 부호화된

용량 영상의

압축율 = 원 =

( )

^[ ^]^where

( )

^:^peak^-^to^-^{peak value}

log

10 ₁₀ ²

dB P P

MSE P

PSNR

=

P

− −

(

^ˆ

)

^where ^ˆ ^:^원영상과^복원된^영상의^차이

1 2

2 ij ij

i j

ij

x x x

M x

MSE

=



− −

( )

²⁵⁵ _[ _]

log

10 ₁₀ ²

dB

PSNR

=

MSE

(5)

무손실 부호화

 무손실 부호화

 영상의 부호화 과정에서 손실이 전혀 생기지 않는 부호화

 원영상  부호화  복호한 영상 = 원영상

 종류

 호프만 부호화(Huffman coding)

 산술 부호화

 런-길이 부호화

 무손실 예측 부호화

호프만 부호화 (Huffman Coding)

 부호화 과정

1. 부호화를 실행할 전체 심볼(영상의 경우 명암도)의 확률을 구하고, 확률을 내림차순으 로 정렬한다.

2. 확률이 가장 작은 두 개의 심볼을 묶어 새로운 노드를 생성시킨다. 이 노드의 자식 노 드 중 하나는 1을 , 다른 하나는 0을 할당한다.

3. 새로이 생성된 노드의 확률은 두 자식 노드의 확률을 합으로 한다. 확률에 따라 내림차 순으로 재정렬한다.

4. 하나의 노드가 남으면 멈추고, 그렇지 않으면 단계 2로 간다.

 호프만 부호화의 예 (3비트로 양자화된 영상)

1 0

10

01

00

111 1101

11001

(6)

산술 부호화 (Arithmetic Coding) (1/2)

 호프만 부호화 vs. 산술 부호화

 공통점: 확률에 의해 부호화

 차이점

 호프만 부호화: 화소 하나하나에 대한 코드 열 할당

 산술 부호화: 화소 열에 대해 코드 열 할당, 발생빈도에 따라 [0,1)의 구간을 분할한다.

산술 부호화 (Arithmetic Coding) (2/2)

 산술 부호화의 예

 {a,e,i,o,u,!}로 구성된 문서라고 가정하자.

 {eaii!}를 부호화 해 보자.

 복호화: (value – low) / range

 0.233597 (e)  (0.233597-0.2)/0.3=0.11199 (a)  (0.11199-0)/0.2=0.55995 (i)

 (0.55995-0.5)/0.1=0.5995 (i)  (0.5995-0.5)/0.1=0.995 (!)

삼볼 확률 범위

a e i o u

!

0.2 0.3 0.1 0.2 0.1 0.1

[0, 0.2) [0.2, 0.5) [0.5, 0.6) [0.6, 0.8) [0.8, 0.9) [0.9, 1.0) 확률 분포

0 1

a e i o u

!

0.2 0.5

a e i o u

!

0.2 0.26

a e i o u

!

0.23 0.236

a e i o u

!

0.233 0.2336

a e i o u

!

0.23354 0.2336

a e i o u

!

e a i i !

초기

산술 부호화

0.233597

(7)

런-길이 부호화

 런-길이 부호화(Run-length coding)

 심볼의 값과 런-길이를 이용하여 영상을 부호화하는 방법

 예: “AAAABBBCCCCCCC”  “A!4BBBC!7”

압축율 = 14/9 = 1.56

런-길이 부호화 후 비트율 = 9*8/14 = 5.14 [bpp]

원래의 비트율 = 14*8/14 = 8 [bpp]

 장점: 이진 영상이나 균일한 영역이 많이 존재하는 영상의 경우 높은 압축율

 단점: 변화가 심한 부분이 많이 존재하는 경우 불리함.

 대표적인 파일 포맷: PCX 파일

무손실 예측 부호화 (1/2)

 무손실 예측 부호화

 화소에 대한 정보가 화소의 예측 값과 실제 값의 차이로 정의되는 부호화 방법

 무손실 부호화의 예

 DPCM (Differential pulse code modulation)

 화소 값 대신 이웃한 화소와의 차를 이용하는 방법

 이웃한 화소는 비슷한 명암을 가진다는 가정하에서 나온 부호화 방법

 만약 차이가 크면 code overload를 사용하여 화소 값 자체를 부호화 함

 “Suzie” 영상에 대한 DPCM 결과

예측 오차 영상 원 영상

(8)

무손실 예측 부호화 (2/2)

 “Suzie” 영상에 대한 예측 오차 신호의 히스토그램

예측 오차 영상의 히스토그램 원 영상의 히스토그램

손실 부호화 (Lossy coding)

 손실 부호화

 정보는 손실되지만 높은 압축율 (cf. 무손실 부호화: 1.5~2배)

 손실 발생 원인: 적은 계수의 사용, 양자화 과정

 손실 예측 부호화

 예: DPCM에서 code overload 발생시 최대 차이 코드 사용

 변환 부호화

 원 신호의 계수보다 상관도가 낮은 변환 계수 (일부) 사용 + 양자화

 자주 사용되는 변환

 KLT (Kauhunen-Loève transform)

 최적의 에너지 집중 성능, 영상에 의존적인 변환 행렬, 고속 알고리즘 부재

 DFT (Discrete Fourier transform)

 고속 알고리즘 존재, 복소수 계수 생성, 주기성 때문에 의사 스펙트럼 생성(블록화 현상)

 DCT (Discrete cosine transform)

 고속알고리즘 존재, 실수 계수 생성, 에너지 집중 효율도 좋고 블록화 현상도 줄어듦

(9)

압축 표준 _– JPEG (1/2)

 JPEG (Joint photographic experts group)

 기본 알고리즘

1. 원 영상을 8 x 8 블록으로 분할, 각 블록에 대해 DCT 변환한다.

2. 모든 계수를 정규화한다.

3. 각 블록의 DC 성분은 DPCM 한다.

4. AC 성분은 양자화: 정보가 많은 저주파 성분은 세밀하게 양자화한다. 양자화 된 계수는 지그 재그 스캔(zigzag scan) 한다.

5. 최종적으로 계수값들을 엔트로피 부호화(DPCM, Huffman, Run-length coding, etc.)한다.

 JPEG 블록도

 블록 단위로 압축하므로 압축율이 높아지면 블록화 현상(blocking artifact) 발생

DCT 양자화 엔트로피

부호화 양자화

테이블

부호화 테이블

데이터 테이블 헤헤

압축 표준 _– JPEG (2/2)

 압축율에 따른 JPEG 영상의 예

원 영상 7 배 11 배

22 배 32 배 59 배

(10)

압축 표준 _– MPEG

 MPEG (Moving picture experts group)

 디지털 동영상 압축의 국제 표준

 공간적인 중복성 + 시간적인 중복성 이용  고압축율 구현

 Mpeg-1

 Coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s

 1991년 제정, For Video CD (VCD)

 Mpeg-2

 Generic coding of moving pictures and associated audio information

 높은 전송속도와 음질을 요구하는 DTV, DVD 등에 사용될 Video 및 Audio 압축 표준

 Mpeg-4

 Coding of audio-visual objects

 64 kbps이하 Low bit rate에서의 영상 통신 및 최고 압축율의 고화질 구현(H.264)

 Mpeg-7

 Content representation standard for multimedia information search, filtering, management and processing

 멀티미디어 데이터의 효율적인 기술과 검색을 위한 표준

 Mpeg-21

 Standard for multimedia framework

 Multimedia 유통을 위한 Framework의 주요 요소와 상호관계를 정의

Practice

 {A,B,C,D}의 네 심볼로 구성되어 있는 문서가 있다고 가정하자. 각각의 확률은 p(A)=0.4, p(B)=0.25, p(C)=0.2, p(D)=0.15 이다.

 Huffman 부호화

 각 심볼의 코드를 결정하시오.

 {ABCDA} 문자열에 대해 Huffman 부호화의 압축율을 계산하시오.

 산술 부호화

 {ABCDA} 문자열에 대해 산술부호화 하시오.

 {ABCDA} 문자열에 대해 산술부호화의 압축율을 계산하시오.

Introductory Image Processing

제 9 장 영상 압축

[email protected]

Prof. Doo-Hyun Choi

Introductory Image Processing

Contents

 영상 압축

 영상 압축의 기초

 영상 압축의 목적과 응용 분야

 영상 압축 모델

 무손실 부호화(Lossless coding)

 손실 부호화(Lossy coding)

영상 압축의 기초 (1/2)

 영상 압축

 기본 아이디어: 정보 혹은 데이터의 중복(redundancy)을 최소화하자

 중복의 종류

 부호화 중복성(Coding redundancy)

 데이터의 발생 빈도(확률)를 고려하지 않고 부호화할 때 발생

 부호화 중복성을 줄이기 위해 많이 나타나는 데이터는 짧은 코드를, 가끔 나타나는 데 이터는 긴 코드를 할당함  가변 길이 부호화 사용

 부호화 중복성 제거에 사용되는 기법

영상 압축의 기초 (2/2)

 화소간 중복성(Inter-pixel redundancy)

 공간적인 중복성, 기하학적 중복성, 프레임 간 중복성 등

 예: 인접한 화소간의 차이가 적은 경우, 밝기 자체를 부호화하는 것보다 차이 성분만 부호화함으로써 적은 데이터 량으로 같은 정보를 유지할 수 있다.

 신경 시각적 중복성(Psycho-visual redundancy)

 인간이 잘 구별하지 못하는 정보는 제거하거나 작은 데이터 량으로 표현한다.

 인간 시각 시스템(Human visual system: HVS)의 특성을 압축에 적극적으로 활용

 비가역 압축

 예: 양자화 과정

영상 압축의 목적과 응용 분야

 영상 압축의 목적

 원하는 수준의 화질을 최소한의 비트수로 유지하자.

 영상 압축의 응용 분야

 전송: 대역폭을 줄이자.

 저장: 저장 공간을 줄이자.

영상 압축 모델 (1/3)

 영상 부호화 단계

 원 영상  특징 추출  양자화  코드워드 할당  비트열

 양자화: 추출된 혹은 부호화하고자 하는 정보를 몇 단계로 구분하는 과정

 코드워드 할당: 양자화 레벨에 코드를 할당하는 과정

특징 추출의

변환 양자화 코드워드

할당 영상

소스 비트열

영상 압축 모델 (2/3)

 영상 부호화

 파형 부호화: 영상 자체를 부호화

 엔트로피 부호화

 영상 모델 부호화: 영상 전체 혹은 일부를 모델링한 후 특징 혹은 모델 파라미터를 부 호화하고, 복호시에는 모델 파라미터로부터 합성한다.

 영상 부호화 기술들

영상 압축 모델 (3/3)

 압축율과 화질

 압축율 vs. 화질: trade-off

 부호화 알고리즘의 비교: 같은 압축율에서의 화질 비교

 압축율(compression rate)과 비트율(bit-rate)

 화질

pixel]

per bit [bpp;

,

수 픽셀

비트수 비트율 사용된

용량 영상의 부호화된

용량 영상의

압축율 = 원 =

( )

( )

dB P P

MSE P

PSNR

P

(

)

x x x

M x

MSE



( )

dB

PSNR

MSE

압축 표준 _– JPEG (1/2)

압축 표준 _– JPEG (2/2)

압축 표준 _– MPEG