[IP] Compression(압축)

이미지와 비디오는 크기가 크므로, 저장이나 파일 교환을 위해서는 Compression(압축)이 필수적이다.

 

Compression에는 두 가지 다른 방법이 있다.

1. 모든 정보를 남기는 Lossless 압축

2. 어느정도 정보의 손실이 생기는 Lossy 압축

 

 

 

📁 Huffman Coding

가장 빈번한 정보에 더 짧은 비트를 할당해라.

픽셀 당 비트의 평균 개수는 확률론적 의미에서 기댓값과 같다.

 

 

정보의 손실 없이 이미지를 인코드하기 위한 픽셀 당 이론적인 최소 비트 수를 Entropy H라고 한다.

 

 

절차는 다음과 같다.

1. 영상에서 각 gray value의 확률을 결정한다, 즉 히스토그램을 작성한다.
2. 가장 낮은 확률 두 개를 추가하여 binary tree를 만든다.
3. 루트에서 트리의 각 분기에 0과 1을 임의로 할당한다.
4. 코드를 위에서 아래로 읽는다.

 

위 계산은 entropy H 계산의 예시이다.

 

 

Huffman code는 고유한 방식으로 디코딩이 가능하다.

 

 

 

 

📁 Run-length Encoding

각 문자열의 반복 횟수로 0과 1로 이루어진 문자열로 인코딩한다.(이진 이미지의 경우)

 

 

각 줄이 0부터 시작하여 별도로 인코딩된다고 가정하자.

 

각 row가 숫자쌍 리스트로 인코딩된다고 가정하자.

 

첫번재 숫자는 1s 실행의 스타팅 포지션이다.????????

 

두번째 숫자는 길이를 뜻한다.

 

 

 

 

📁 JPEG 알고리즘

Lossy Compression의 한 종류.

 

 

먼저 JPEG란Joint Photographic Experts Group(JPEG)