Chapter 7 무손실 압축 기법 멀티미디어시스템 2010-2학기

Chapter 7 무손실 압축 기법 7.1 소개 7.2 기본적인 정보 이론 7.3 줄길이 부호화 7.4 가변 길이 부호화 7.5 사전 기반 부호화 7.6 산술 부호화 7.7 무손실 영상 압축 멀티미디어시스템 2010-2학기

7.1 소개 압축 : 특정 정보를 표현하기 위해 필요한 비트 수를 효과 적으로 줄여주는 코딩의 과정 그림 7.1 : 일반적인 데이터 압축 구조 멀티미디어시스템 2010-2학기

압축률: compression ratio = B0/B1 (7.1) B0 – 압축 전의 비트의 수 B1 – 압축 후의 비트의 수 만약 압축을 하는 과정과 푸는 과정이 정보의 손실을 일으 키지 않으면, 그 압축 구조는 무손실(lossless)이다 ; 그렇지 않으면 손실(lossy)이다. 압축률: compression ratio = B0/B1 (7.1) B0 – 압축 전의 비트의 수 B1 – 압축 후의 비트의 수 압축률이 높을수록 더 좋은 무손실 압축 방법 멀티미디어시스템 2010-2학기

7.2 기본적인 정보 이론 S={s1,s2,...,sn} 로 표현되는 원천 정보의 엔트로피 η (에타) 는 : pi – 심볼 si 가 S 안에서 일어날 확률. Log21/pi – si 에 포함된 정보의 양(Shannon은 자기정보량으 로 정의하였다.)을 의미하며 이것은 si를 부호화하는데 필 요한 비트 수 임. 멀티미디어시스템 2010-2학기

원고 내 문자 n 이 사용될 확률이 1/32 라고 하면 이것의 정보량은 5비트가 된다. pi – 심볼 si 가 S 안에서 일어날 확률. Log21/pi – si 에 포함된 정보의 양(Shannon은 자기정보량으 로 정의하였다.)을 의미하며 이것은 si를 부호화하는데 필 요한 비트 수 임. 예: 원고 내 문자 n 이 사용될 확률이 1/32 라고 하면 이것의 정보량은 5비트가 된다. 문자열 nnn 을 부호화하는데는 15비트 필요. 멀티미디어시스템 2010-2학기

엔트로피 (1) 과학분야에서의 정의는 “시스템의 무질서 정도를 측량” 엔트로피가 첨가될수록 더욱 무질서 시스템에서 질서 첨가하기를 할 때 음수의 엔트로피를 더 하게 된다. 엔트로피의 정의는 두 가지 결정이 음수 엔트로피의 두 배 만큼의 전송을 의미한다. 2비트 벡터는 22 의 상태를 가지고 로그값은 음수 엔트로 피의 2 의 값을 가진다. 멀티미디어시스템 2010-2학기

엔트로피 (2) 두 가지 결정을 위해 2비트를 보낼 때 가능한 상태의 수는 4개이고 각 결과는 ¼ 확률을 가진다. 두 가지 결정을 위해 2비트를 보낼 때 가능한 상태의 수는 4개이고 각 결과는 ¼ 확률을 가진다. 평균적으로 각 결과당 비트 수는 4 x (1/4) x log (1/(1/4)) = 2 비트가 된다. 즉, 두 가지 결정을 전송하기 위해서 2 비트를 전송 엔트로피는 압축된 데이터스트림이 적은 코드워드를 생성 하는 좋은 방법이며, 엔트로피 부호화를 위해 가변길이 부 호화를 사용한다. 자주 발생하는 기호는 빨리 전송될 수 있는 코드가 부여 되고 자주 발생하지 않는 기호는 긴 코드가 부여된다. 멀티미디어시스템 2010-2학기

회색계 강도의 분포 그림 7.2 두 개의 회색도 강도 영상의 히스토그램 그림 7.2 (a)는 평활한 분포의 획색계 강도를 가지는 영상의 히스 토그램을 보여준다, 즉, ∀i pi = 1/256. 따라서, 이 영상의 엔트로피 는: 256 η = ∑ (1/256) log2 256 = 8 (7.4) i=0 멀티미디어시스템 2010-2학기

엔트로피와 코드 길이 식 (7.3)에서 볼 수 있듯이 엔트로피 η는 log21/pi 의 가중치 곱을 합산한 것으로, 따라서 원천 정보 S에서 각 기호가 포 함하는 평균 정보량을 의미한다. 엔트로피 η는 S의 각 기호를 부호화하기 위한 평균 비트수 의 최소 한계 값이다, 즉, ḹ : 부호기에서 발생하는 코드워드의 평균 길이(단위는 비트). 멀티미디어시스템 2010-2학기

7.3 줄길이 부호화 (RLC) 메모리리스 소스: 독립적으로 분포된 원천 정보. 말하자면, 현재 심볼의 값은 이전에 나타났던 심볼의 값들에 의존하 지 않는다. 줄길이 부호화(RLC)는 메모리리스 정보 대신에 원천 정보 에 나타난 메모리를 활용한다. RLC의 이론적 설명: 만약 원천 정보가 심볼들이 연속적인 그룹을 이루는 성질을 가진다면, 그러한 심볼과 그룹의 길 이는 코딩될 수 있다. 멀티미디어시스템 2010-2학기

7.4 가변 길이 부호화(VLC) Symbol H E L O Count 1 1 2 1 Shannon-Fano 알고리즘 – top-down 접근 1. 심볼들의 발생 빈도에 따라 기호를 분류한다. 2. 모든 부분이 오직 하나의 기호를 포함할 때까지 각각이 비슷한 정도의 빈도를 가지도록 재귀적으로 두 개의 기호를 두 개의 부분으로 구분한다. 예제: “HELLO” 의 코딩 “HELLO”에서 심볼의 발생 빈도수 Symbol H E L O Count 1 1 2 1 멀티미디어시스템 2010-2학기

그림 7.3: Shannon-Fano 알고리즘에 의한 HELLO 코드 트리 멀티미디어시스템 2010-2학기

HELLO 의 각 문자를 부호화하기 위한 최소 길이는 적어 도 1.92 비트가 된다는 것을 의미한다. η = PL log2 (1/PL) + PH log2 (1/PH) + PE = log2 (1/PE) + PO log2 (1/PO) = 0.4 x 1.32 + 02 x 2.32 + 0.2 x 2.32 + 0.2 x 2.32 = 1.92 HELLO 의 각 문자를 부호화하기 위한 최소 길이는 적어 도 1.92 비트가 된다는 것을 의미한다. Shannon-Fano 알고리즘은 각 기호를 부호화하는데 평균 10/5 = 2 비트를 사용하고 있고, 하한 경계인 1.92에 매우 근접한 것이 확인됨. 멀티미디어시스템 2010-2학기

표 7.1: HELLO 에 대한 Shonnon-Fano 알고리즘 적용 결과 멀티미디어시스템 2010-2학기

그림 7.4 Shonnon-Fano 알고리즘에 의한 HELLO 의 또 다른 코드 트리 멀티미디어시스템 2010-2학기

표 7.2 : HELLO 에 대한 Shannon-Fano 알고리즘 적용의 또 다른 결과 멀티미디어시스템 2010-2학기

허프만 부호화 알고리즘 7.1 허프만 부호화 알고리즘 –bottom-up 접근 1. 초기화 : 모든 기호를 출현 빈도수에 따라 나열한다. 2. 단 한 가지 기호가 남을 때까지 아래 단계를 반복한다. (a) 목록으로부터 가장 빈도가 낮은 두 개의 기호를 고른 다. 허프만이 두 가지 기호를 부노드를 가지는 부트리를 구 성하고 주노드를 생성한다. (b) 부노드 단의 기호들의 빈도수를 더하여 주노드에 할 당하고 목록의 순서에 맞도록 목록에 삽입한다. (c) 목록에서 부노드에 포함된 기호를 제거한다. 3. 뿌리로부터의 경로에서 각 가지에 코드워드를 부여한다. 멀티미디어시스템 2010-2학기

그림 7.5: Huffman 알고리즘을 사용한 HELLO 의 코 드 트리 멀티미디어시스템 2010-2학기

위 그림에서 새로운 기호 P1, P2, P3는 허프만 부호화 트리에 서 주노드를 표시하기 위해 생성된 것이다 위 그림에서 새로운 기호 P1, P2, P3는 허프만 부호화 트리에 서 주노드를 표시하기 위해 생성된 것이다. 목록은 다음과 같이 나열된다. 초기화 후 : LHEO 반복 후 (a) : L P1 H 반복 후 (b) : L P2 반복 후 (C) : P3 멀티미디어시스템 2010-2학기

허프만 코딩의 속성 유일 전치 속성:  허프만 부호는 다른 어떠한 허프만 부 호의 전치가 되지 않는다. - 복호과정에서 어떠한 모호성 도 배제 2. 최적성: 최소공간중복 코드 - 주어진 데이터 모델(즉, 정 확한 확률분포가 주어진 상황)에 있어서 최적화되어 있 음 - 두 개의 최소 빈도 기호들은 허프만 부호화에서 같은 길이를 가지게 되며, 오직 마지막 한 비트만이 다르다. 이것은 위의 알고리즘에서 분명히 알 수 있다.      - 더 자주 발생하는 기호는 더 작은 크기의 허프만 코드 를 가진다. 즉, 기호 si와 sj에 대하여 pi≥pj이면, 코드워드 의 비트 수는 li≤lj이다.      - 원천 정보 S에 대하여 평균 부호 길이는 η+1보다 작으 며, 식 7.5와 결합하면, 다음의 결과를 얻게 된다. 멀티미디어시스템 2010-2학기

확장된 허프만 부호화 동기: 허프만 코딩에서의 모든 코드워드는 정수의 비트 길 이를 가진다. Pi가 매우 크고 따라서 log21/pi가 0에 가까워 질 때, 이것은 비경제적이다. 몇 개의 기호들은 하나의 그룹으로 묶고 그 그룹에 하나의 코드워드를 부여하면 어떨까? 확장된 알파벳: 원천정보 S={s1, s2, …., sn}에 대하여 k 개의 기호를 하나로 묶었을 때 이 확장된 기호는 다음과 같다: - 새로운 알파벳 S(k)의 크기는 nk이다. 멀티미디어시스템 2010-2학기

각 심볼에 대한 평균 비트의 수가 다음과 같음을 보일 수 있다: 각 심볼에 대한 평균 비트의 수가 다음과 같음을 보일 수 있다: 원래의 허프만 코딩에 비해 향상을 가져오지만, 월등한 향 상은 아니다. 문제점: 만약 k가 비교적 크다면, 대부분의 실제적인 상황 에서 n≫1이므로, 는 매우 큰 수가 될 것이고, 따라서 매우 큰 기호 목록이 필요하게 된다. 때문에 확장된 허프만 부호 화가 실질적으로는 사용되지 못한다. 멀티미디어시스템 2010-2학기

적응적 허프만 코딩 적응적 허프만 코딩: 통계치가 도착하는 데이터 열에 따라 유동적으로 모아지고 갱신되는 방식. 적응적 허프만 코딩: 통계치가 도착하는 데이터 열에 따라 유동적으로 모아지고 갱신되는 방식. 멀티미디어시스템 2010-2학기

부호기와 복호기는 정확히 똑같은 Initial_code와 update_tree 과정을 사용해야 한다. Initial_code 는 빈도수에 대한 사전 정보 없이 어떤 초기 코 드를 기호에 부여한다. 예를 들어, ASCII와 같은 어떤 임의 코드가 문자 기호를 부호화하기 위해 사용될 수 있다. update_tree 는 적응적 허프만 트리를 만드는 과정이다. 이것은 기본적으로 두 가지 일을 한다. (a) 심볼들의 발생 빈도수를 증가시킨다.(새로운 심볼들도 포함) (b) 트리를 업데이트시킨다. 부호기와 복호기는 정확히 똑같은 Initial_code와 update_tree 과정을 사용해야 한다. 멀티미디어시스템 2010-2학기

허프만 트리 업데이트시 주의사항 노드들은 왼쪽에서 오른쪽으로, 아래에서 위로 번호가 매 겨진다. 괄호 안의 숫자는 횟수(count)를 의미한다. 허프만 트리는 양단성질을 항상 유지하여야한다. 즉, 모든 노드들은(내부와 가지) 빈도수의 순서에 따라 나열된다. 양단성질이 위반될 때는 트리를 갱신하기 위해 노드들을 재배열함으로써 교체 과정이 수행된다. 교체가 필요하다면, 빈도수가 N인 가장 먼 노드가 이제 막 빈도수가 N+1이 된 노드와 교체된다. 멀티미디어시스템 2010-2학기

그림 7.6: 적응 허프만 트리를 갱신하기 위한 노드 교체 멀티미디어시스템 2010-2학기

기타 예제: 적용 허프만 코딩 여기서는 단순히 어떻게 트리가 갱신되는지 말하는 것 보 다, 정확히 무슨 비트들이 보내지는가를 보일 것이다. 한 가지 추가적인 규칙: 어떤 문자/기호가 한번 보내지려면, 특정한 기호 NEW가 선행되어야 한다. NEW의 초기 코드 는 0이다. NEW의 빈도수는 항상 0으로 고정된다. 즉, 그림 7.7과 같이 항상 NEW:(0)으로 표시된다. 멀티미디어시스템 2010-2학기

표 7.3: 적응 허프만 코딩을 사용한 AADCCDD열의 초기 코 드 배분 멀티미디어시스템 2010-2학기

그림 7.7 AADCCDD에 대한 적응 허프만 트리 멀티미디어시스템 2010-2학기

그림 7.7 멀티미디어시스템 2010-2학기

적응적 허프만 부호화 과정에서는 종종 특정 기호의 코드가 바뀐다는 점은 중요하다. 표 7.4 복호화기로 보내진 심볼과 코드 열 적응적 허프만 부호화 과정에서는 종종 특정 기호의 코드가 바뀐다는 점은 중요하다. 예를 들어, AADCCDD가 수신되면, 문자 D는 A보다 발생빈도가 높아지게 된다. 따라서 코드는 101에서 0으로 바뀐다. 이 책의 웹사이트상의 “Squeeze Page"는 적응적 허프만 부호화를 위한 자바 애플릿을 제공하여 이 알고리즘에 대한 이해를 돕고자 한다. 멀티미디어시스템 2010-2학기

7.5 사전 기반 부호화 LZW는 영어 문장의 단어처럼 주로 함께 발생하는 가변길 이의 기호/문자열을 표현하는데 고정길이 코드워드를 사 용한다. LZW 부호기와 복호기는 데이터를 수신하는 동안 유동적 으로 동일한 사전을 생성한다. LZW는 사전에 더욱더 긴 반복된 기재사항을 만들고, 만약 성분(element)가 이미 사전 안에 있으면, 그 성분에 대해 기 호 대신 코드를 내보낸다. 멀티미디어시스템 2010-2학기

알고리즘 7.2 LZW 압축 멀티미디어시스템 2010-2학기

예제 7.2 LZW 압축 for 문자열 “ABABBABCABABBA” 단지 세 개의 문자가 포함된 간단한 사전(일명 문자열표) 으로 시작하자. 입력열이 ABABBABCABABBA일 때 LZW 압축 알고리듬은 다음과 같이 동작한다. 멀티미디어시스템 2010-2학기

ABABBABCABABBA 출력 코드는 1 2 4 5 2 3 4 6 1이다. 14개의 문자 대신에 단 9 개의 코드가 필요할 뿐이다. (압축률=14/9=1.56) 멀티미디어시스템 2010-2학기

알고리즘 7.3 LZW 복호화(간단한 방법) 예제 7.3: ABABBABCABABBA의 LZW 복호화 복호기의 입력코드가 1 2 4 5 2 3 4 6 1 이라고 하자. 초기 문 자열 표는 부호기에서 사용한 것과 동일하다. 멀티미디어시스템 2010-2학기

LZW 복호 알고리즘은 다음과 같이 진행된다. 출력 문자열은 ABABBABCABABBA로 손실 없는 결과를 얻었 다. 멀티미디어시스템 2010-2학기

알고리즘 7.4 LZW 복호화(개선된) 멀티미디어시스템 2010-2학기

실제 구현에 있어서, 부호 길이 l은 [수식]에 제한된다. 사전 은 최초에 (수식2l0)의 크기를 가진다 실제 구현에 있어서, 부호 길이 l은 [수식]에 제한된다. 사전 은 최초에 (수식2l0)의 크기를 가진다. 이것이 꽉 차면, 부호 길이는 1만큼 증가되고, (수식l=lmax)가 될 때까지 반복될 수 있다. Lmax에 다다르고 사전이 다 채워지면, 사전은 비워질 (flushed) 필요가 있다. (Unix 압축에서처럼, 또는 LRU(최근 에 가장 적게 사용된) 목록을 제거하기 위해) 멀티미디어시스템 2010-2학기

7.6 산술 부호화 산술부호화는 일반적으로 허프만 부호화보다 우수한 성능 을 보이는 좀더 최신의 부호화 기법이다. 허프만 부호화는 각 기호에 정수의 비트 길이를 가지는 코 드워드를 부여한다. 산술부호화는 전체 메시지를 하나의 단위로 취급할 수 있다. 하나의 메시지는 0과 1사이의 실수 a, b에 의한 [a,b)의 반개 구간으로 표현되게 된다. 초기에 구간은 [0,1)이다. 메시지 가 길어지면, 구간의 길이는 짧아지게 된다. 그리고 그 구간 을 표현하기 위한 비트 수는 증가한다. 멀티미디어시스템 2010-2학기

알고리즘 7.5 산술 부호화 부호기 멀티미디어시스템 2010-2학기

(a) 심볼들의 확률 분포 그림 7.8: 산술 부호화: 부호화 심볼 CAEE$ 예제: 산술 부호화 (a) 심볼들의 확률 분포 그림 7.8: 산술 부호화: 부호화 심볼 CAEE$ 멀티미디어시스템 2010-2학기

그림 7.8(b) 축소되는 영역의 도식적 표현 멀티미디어시스템 2010-2학기

그림 7.8(c) 생성된 새로운 저, 고 영역 멀티미디어시스템 2010-2학기

수행과정7.2 부호기에서의 코드워드 생성 부화화의 마지막 단계에서는 [low,high) 구간 내의 숫자를 생성해내야 한다. 위의 알고리즘은 확실히 최단의 이진 코 드워드가 찾아지게 한다. 멀티미디어시스템 2010-2학기

알고리즘 7.6 산술 부호화 복호기 멀티미디어시스템 2010-2학기

표 7.5 산술 부호화: 복호 심볼들 CAEE$ 멀티미디어시스템 2010-2학기

7.7 무손실 영상 압축 영상의 차분 부호화 - 원본 영상 I(x,y)에 대해 간단한 차분기를 사용하여 차분 영상 d(x,y)를 다음과 같이 정의한다: 또는 다른 방법으로 이산 2D 라플라시안 연산기를 이용한 것으로 다음과 같다. I 영상에서의 공간적인 중복(redundancy) 때문에, 그림 7.9 에서 보듯이 차분 영상 D 는 I 보다 더 좁은 히스토그램을 가지고, 따라서 더 작은 엔트로피를 가진다. 멀티미디어시스템 2010-2학기

그림 7.9 원 영상의 분포와 미분 영상 비교. (a, b): 원래의 회색 도 크기 영상과 부분 미분 영상; (c, d): 원 영상과 미분 영상 에 대한 히스토그램. 이 그림은 ‘Barb’라고 불리는 보편적으 로 사용되는 영상이다. 멀티미디어시스템 2010-2학기

무손실 JPEG 무손실 JPEG: JPEG 영상 압축의 특별한 경우. 예측적 방법 1. 차분 예측기 구성: 예측기는 그림 7.10에서 X로 표시된 현재 화소의 예측값으로서 3개까지의 인접화소의 값들을 결합한다. 예측기는 표 7.6에 나와 있는 7개의 값 중 하나를 가질 수 있다. 2. 부호화: 부호기는 예측과 위치 X 에서의 실제 화소값을 비교하고, 설명하였던 Huffman 부호화와 같은 무손실 압축 기법 중 하나를 사용하여 차이를 부호화한다. 멀티미디어시스템 2010-2학기

그림 7.10: 무손실 JPEG의 예측을 위한 이웃 화소들 Note: 부호-복호 사이클 상의 복호기에서 A, B, C 중 어떤 것도 예측기에서 사용되기 전에 이미 복호화 되었다. 멀티미디어시스템 2010-2학기

표 7.6: 무손실 JPEG을 위한 예측기들 멀티미디어시스템 2010-2학기

표 7.7: 다른 무손실 압축 프로그램과 무손실 JPEG 과의 비 교 멀티미디어시스템 2010-2학기