데이터 압축 알고리즘 데이터 압축 알고리즘 지도교수 : 김 재 형 교수님 지도교수 : 김 재 형 교수님 98914050 배 재 성 20011314 조 성 인

 목 차 데이터 압축의 필요성 데이터 압축이란? 데이터 압축 – 무손실 압축(Lossless)  목 차 데이터 압축의 필요성 데이터 압축이란? 데이터 압축 – 무손실 압축(Lossless) 데이터 압축 – 유손실 압축(Lossy) 데이터 압축 – 혼합방식(Hybrid) 향후과제 및 결론

1 2 3  데이터 압축의 필요성 통신 미디어의 경우 저장 미디어의 경우 방송 미디어의 경우 종래 불가능하다고 여겨졌던 영상등의 멀티미디어 통신이 가능해진다. 전화와 같이 싼 요금으로 영상 등의 멀티미디어 통신이 가능해 진다. 통신 미디어의 경우 값싼 저장 미디어로 영상 등의 멀티미디어 정보를 기록할수 있게 된다. 저장 매체에 있어서 기록에 필요한 점유량을 작게 할수 있다. 저장 미디어의 경우 방송 미디어의 경우 열화가 없고 고품질 전송이 가능해 진다. 다채널화가 가능해진다.

데이터 압축의 개념 저장 장치 용량의 한계, 통신라인의 데이타 전송율 한계 - 이미지, 오디오, 비디오의 압축이 필수적이다.

데이터 압축의 개념 용어 복원(decompression) 인코더(encoder)/디코더(decoder) 인코더와 디코더를 합쳐코덱(codec)이라 한다. 손실(lossy) 기법, 무손실(lossless) 기법

데이터 압축의 개념 주요 압축 알고리즘 JPEG, MPEG, P*64(H.261), 등이 대표적이다.

데이터 압축의 개념 압축기법의 요구사항 압축후 복원의 결과가 원래의 데이터와 큰 차이가 없어야 한다. 압축과 복원으로 인한 지연 시간이 너무 길지 않아야 한다. 다양한 데이타 압축율을 지원할 수 있어야 한다. H/W적인 구현과 S/W적인 구현이 모두 가능해야 한다.

압축을 수행한 뒤 이를 다시 해제하여도 압축 전과 같은 데이터를 유지하는 압축기법 무손실 압축 압축을 수행한 뒤 이를 다시 해제하여도 압축 전과 같은 데이터를 유지하는 압축기법 Run-Length Coding ( 예 ) 압축전의 데이터: PRSSSSSSSSTTBVVVVVVVMM(22바이트) Run-length 코딩: PQR!8STTU!7VWW(14바이트) Huffman Coding 출현 빈도가 높은 문자에 짧은 코드를 할당 출현빈도가 낮은 문자에 긴 코드를 할당 압축된 코드 길이가 다양

(예) MPEG, JPEG, MP3, OGG(오그보비스) 유손실 압축 압축을 수행한 뒤 이를 다시 해제하면 압축 전과는 어느정도의 데이터 손실을 감안하는 압축기법 주로 시각이나 청각등의 사람의 감각적 인식범위 내의 데이터는 최적으로 압축하고 사람의 감각적 인식 범위를 벗어나는 부분은 손실 압축을 통해 데이터 량을 현저히 줄이는 압축기법 (예) MPEG, JPEG, MP3, OGG(오그보비스)

무손실 압축 - Run Length Encloding RLE 동일한 바이트가 일정 개수 4이상 발생하면 ‘해당문자 플래그 바이트 개수’의 형태로 표현된다. 예) AAAAAAAABCCCC(13 byte) -> A ! 4 B C ! 0 (7 byte) 1. 압축과 복원 속도가 빠르다. 2. 프로그래밍이 쉽고 프로그램의 크기가 작다. 3. 같은 문자가 계속 반복된 파일을 압축할 경우 가장 높은 압축률로 압축된다. 적어도 4개 이상의 동일한 문자가 인접해 있을 경우에만 효과가 있다. 일반적인 파일 압축에는 압축률이 낮아서 사용되지 않는다.

무손실 압축 - Huffman Huffman Leaf 노드의 문자는 압축하여야 할 데이터를 나타낸다. 모든 노드는 출현빈도를 가지고 있다. 루트노드의 확률값은 1이다. 트리는 다음 방법에 의하여 구성한다. *가장 낮은 빈도를 가지는 두 개의 노드를 결합하며 2진 서브트리를 만든다. *이 과정을 루트를 만날 때까지 반복한다. *트리를 완성한 후에 모든 에지(edge)에 0과 1 값을 임의로 지정한다.

Huffman 이진 트리 구성의 예: 1 2 3 A=6 , B=6 , C=8 , D=9 *노드 AB로부터 A로 가는 엣지에 0 지 정, AB로부터 B로 가는 엣지에 1을 나머지 노드의 빈도는 다음과 같다 : AB = 12, C = 8, D = 9  1 *노드 AB와 노드 C의 빈도가 가장 낮으므로 결합하 여 ABC노드를 구성 *노드 ABC로부터 AB로 가는 엣지에 0을 지정하고 C로 가는 노드에 1을 지정 나머지 노드의 빈도는 다음과 같다 :  ABC =20 , D = 9 2 노드 ABC와 D를 결합하여 루트 노드 ABCD를 구성 노드 ABCD로부터 ABC로 가는 엣지에 0을 지정, D 로 가는 엣지에 1을 지정 루터 노드 ABCD의 빈도 ABCD = 29 A=000, B=001, C=01, D=1 3

ABCD=29 ABC=20 1 AB=12 1 1 A=6 B=6 C=8 D=9 Huffman 이진 트리

AABCBBCCCDDDAABADDABBCCCCDDDD 압축에 사용될 대표값 29Bytes AABCBBCCCDDDAABADDABBCCCCDDDD Length 1 D 2 01 C 3 001 B 000 A 비트수 대표값 문자 byte 8 00000000 00010100 10010101 01111000 00000100 01100000 01011111 7 6 5 4 3 2 8bytes/29bytes 압축률 1 bit

Huffman 압축 실행 결과 문자 원래 크기 압축된 크기 차이(bit) A B C D 합계 빈도수 원래 크기 압축된 크기 차이(bit) A 6 6*8=48 6*3=18 64-18=46 B 42-12=30 C 8 8*8=64 8*2=16 64-16=48 D 9 9*8=72 9*1=9 72-18=54 합계 33 232 61 232-61=171 Huffman 압축은 기존의 아스키 코드 값으로 232bits (29bytes) 크기의 데이터를 61bits (8bytes) 크기의 데이터로 줄였다.

JPEG - Joint Photographic Experts Group 개 요 CCITT와 ISO에 의해 정의된 정지영상압축 국제 표준 이진영상을 제외한 그레이 레벨 영상이나 컬러 영상등 거의 모든 2차원 정지영상을 압축하기 위해 필요한 사항 명시 두 가지 압축방법 포함 Lossy compression : predictive coding Lossless compression : transform coding

JPEG - Joint Photographic Experts Group 배 경 JPEG의 요구사항 압축에 사용되는 기술은 가능한 최신의 것 어떠한 영상 응용 분야에도 적용 소프트웨어로도 구현 가능해야 됨 네 가지 동작모드 순차적 모드(sequential DCT-based mode) 점진적 모드(progressive DCT-based mode) 계층적 모드(hierarchical mode) 무손실 모드(lossless mode)

JPEG - Joint Photographic Experts Group 순차적 부호화 모드(Sequential) 영상의 각 컴포넌트가 순차적으로 부호화 영상의 위->아래, 좌측->우측으로 순서적으로 처리

JPEG - Joint Photographic Experts Group 점진적 부호화 모드 영상이 여러 개의 스캔으로 부호화 처음 스캔으로 대략적으로 부호화하고 스캔 횟수가 증가함에 따라 영상 품질이 개선

JPEG - Joint Photographic Experts Group 계층적 부호화 모드 공간해상도에 따라 영상이 계층적으로 부호화 저해상도-> 고해상도로 부호화 통신망의 전송속도나 터미널의 해상도에 적용 가능

JPEG - Joint Photographic Experts Group 무손실 압축 모드 영상의 품질을 전혀 손상 없이 원영상을 그대로 재현 약 2:1의 압축률

JPEG - Joint Photographic Experts Group 원본이미지 8X8 크기의 격자로 이미지를 자름

JPEG - Joint Photographic Experts Group DCT 변환 Width 8 Height 8 양자화 단계 최종 압축영상 엔트로피 인코딩

JPEG - Joint Photographic Experts Group D C T DCT (Discrete Cosine Transform) 에 의한 압축 이미지 및 비디오 데이터등의 공간 및 시간 중복 데이터를 효율적으로 제거한다.  상관관계가 높은 이미지 데이타인 경우, 압축효율이 최적에 가깝다. DCT는 직교성(orthogonal)을 가지고 있어서 역함수가 간단하며 오버헤드가 비슷하다. 공간영역을 주파수(frequency)영역으로 변환하여 인간 시각시스템의 특성을 반영하여 코딩한다. 빠른 알고리즘의 구현이 가능하다.

JPEG - Joint Photographic Experts Group D C T DCT에 의한 압축 시스템의 주요 단계(1-1) DCT 변환 단계 X Y로의 함수: 앞방향 (Forward) DCT or DCT

JPEG - Joint Photographic Experts Group D C T DCT에 의한 압축 시스템의 주요 단계(1-2) DCT 변환 단계 Y X로의 함수 : IDCT (Inverse DCT)

JPEG - Joint Photographic Experts Group D C T DCT에 의한 압축 시스템의 주요 단계(2) DCT 변환 단계 DC 및 AC상수 DC(Direct Current) 상수 행렬 Y의 첫 번째 원소 수평 및 수직으로 주파수대가 0인 상수 8 X 8 블록의 64개 칼라값에 대한 평균값을 나타냄 AC(Alternate Current) 상수 DC상수를 제외한 나머지 상수

JPEG - Joint Photographic Experts Group D C T DCT에 의한 압축 시스템의 주요 단계(3) DCT 변환 단계 DCT 상수의 특징 수평(horizontal) 및 수직(vertical) 축은 주파수에 대한 강도(intensity)를 나타낸다. 수직축으로 내려 갈수록 그리고 수평축을 따라 오른쪽으로 갈수록 주파수가 높다.

JPEG - Joint Photographic Experts Group 양자화 (quantization) 양자화 실제적인 압축효과 발생 역양자화 시에 정보 유실의 원인 64개의 양자화 계수를 갖는 양자화 테이블에 의해 균일 양자화(uniform quantization) 양자화 테이블의 결정 고주파 계수가 저주파 계수보다 주관적으로 덜 중요 고주파 계수에 큰 양자화 간격(step size) Chrominance 성분이 luminance 성분보다 덜 중요 테이블 값 : 각각의 DCT계수들에 대한 양자화 간격(1~255)

JPEG - Joint Photographic Experts Group 양자화 (quantization) 양자화 과정 DCT계수를 양자화 테이블에 의한 양자화 간격으로 나눈다 가까운 정수 값으로 Rounding

JPEG - Joint Photographic Experts Group 양자화 (quantization) 역양자화 과정

JPEG - Joint Photographic Experts Group 양자화 (quantization) 양자화 과정에서 데이터 손실이 일어나는 부분 양자화의 이해 고주파 – 시각적으로 덜 중요 1 1 1 1 1 1 1 1 1 저주파 – 시각적으로 중요 1 1 1 1 1 1 1 1 1 1 1 1 1

JPEG - Joint Photographic Experts Group 139 144 149 153 155 155 155 155 144 151 153 156 159 156 156 156 150 155 160 163 158 156 156 156 159 161 162 160 160 159 159 159 161 161 161 161 160 157 157 157 162 162 161 163 162 157 157 157 162 162 161 161 163 158 158 158

JPEG - Joint Photographic Experts Group 단계 2) DCT 변환 235.6 -1.0 –12.1 –5.2 2.1 –1.7 –2.7 1.3 -22.6 –17.5 –6.2 –3.2 –2.9 –0.1 0.4 –1.2 -10.9 –9.3 –1.6 –1.5 0.2 –0.9 –0.6 –0.1 -7.1 –1.9 0.2 1.5 0.9 –0.1 0.0 0.3 -0.6 –0.8 1.5 1.6 –0.1 –0.7 0.6 1.3 1.8 –0.2 1.6 –0.3 –0.8 1.5 1.0 –1.0 -1.3 –0.4 –0.3 –1.5 –0.5 1.7 1.1 –0.8 -2.6 1.6 –3.8 –1.8 1.9 1.2 –0.6 –0.4

JPEG - Joint Photographic Experts Group 단계 3) 양자화 과정 16 11 10 16 24 40 51 61 12 12 14 19 26 58 60 55 14 13 16 24 40 57 69 56 14 17 22 29 51 87 80 62 18 22 37 56 68 109 103 77 24 35 55 64 81 104 113 92 49 64 78 87 103 121 120 101 72 92 95 98 112 100 103 99 15 0 -1 0 0 0 0 0 -2 -1 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Luminance 양자화 테이블(Q(u,v)) 양자화된 계수값(FQ(u,v))

JPEG - Joint Photographic Experts Group 단계 4) 양자화된 계수값을 지그재그 열로 변환 15 0 -1 0 0 0 0 0 -2 -1 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 –2 –1 –1 –1 0 0 –1 EOB DC 계수(이전 DC 값이 12라고 가정) Diff : 3 = 15-12 (SIZE)(AMPLITUDE) = (2)(3) AC 계수 {(RUNLENGTH, SIZE)(AMPLITUDE)}  {(1,2)(-2), (0,1)(-1), (0,1)(-1), (0,1)(-1), (2,1)(-1), (0,0)} DC 계수

JPEG - Joint Photographic Experts Group

JPEG - Joint Photographic Experts Group

JPEG - Joint Photographic Experts Group 코드 부여 예 DC 계수 AC 계수 Huffman 코드(VLC) VLI (2) : 011 (3) : 11 Huffman 코드(VLC) VLI (0,0) : 1010 (0,1) : 00 (1,2) : 11011 (2,1) : 11100 (-2) : 01 (-1) : 0 최종코드 : 011111101010000000001110000001010 (34bits  5bytes) / 64bytes(한 블럭의 이미지크기) ~ 1 / 13 (압축률)

JPEG - Joint Photographic Experts Group 25% 50% 75%

시 연 시 연 허프만 코드를 이용한 문서파일 압축 및 복원 JPEG 압축 기술을 이용한 그림파일 압축

향후 과제 및 결론 향후 과제 및 결론 향후 과제 결 론