[영상처리] 손실 압축, 비손실 압축과 허프만(Huffman) 코딩

1. 압축(Compression)의 정의

압축이란, 이를 나타내는 영어 단어에서도 알 수 있듯이 'Compression', 무엇인가를 누른다는 것입니다. 가방에 물건을 최대한 많이 담고 싶을 때 혹은 부피를 줄이고 싶을 때 우리는 압력을 가해 그 부피를 줄이게 됩니다. 이와 같은 과정을 우리는 압축(Compression)이라 일컫습니다. 압축 과정은 결과적으로 데이터의 손실이 있느냐, 없느냐에 따라 크게 손실 압축과 비손실 압축으로 구분됩니다.

1) 손실 압축(Lossy Compression)

손실 압축은 말 그대로, 압축 과정에서 데이터의 손실이 발생함을 의미합니다. 일반적으로, 주요 데이터를 양자화(Quantization) 한 후, 중요한 정보들을 최대한 보존하는 것을 목표로 합니다. 이를 위해 사람들이 잘 느끼지 못하고, 그나마 둔감한 정보를 손실시킵니다. 영상 압축에서는 사람들이 잘 파악하지 못하는 고주파 성분 혹은 색차(Color difference) 정보를 손실시키는 방식을 주로 사용합니다. 음성(audio)의 경우에는 사람에게 잘 들리지 않는 성분을 손실시키는 방법을 사용합니다.

2) 무손실 압축(Lossless Compression)

무손실 압축은 손실 압축과는 반대되는 개념으로, 원래 정보 그대로를 보존해야 하므로 정보 엔트로피의 한계가 그대로 반영됩니다. 일반적으로, 파일 데이터의 압축에 사용하는 gzip을 비롯한 알고리즘들이 이에 해당합니다. 주로, 의료 영상이나 설계 도면과 같이 그 데이터에 사소한 손실이라도 생기면 큰 문제가 생기는 경우에 사용하게 됩니다.

2. 허프만 코딩(Huffman Coding)

1) 허프만 코딩의 정의

허프만 코딩(Huffman Coding)은 대부분의 압축 프로그램에서 사용하는 방법으로, 자주 사용되는 문자는 적은 비트의 코드로 변환해서 표현하고, 빈도가 낮은 문자는 최대한 많은 비트의 코드로 변환하여 표현하는 방법입니다. 이를 통해 전체 데이터를 표현하는 데에 사용되는 총 비트 양을 줄이는 방법입니다. 허프만 코딩에서는 압축 대상이 되는 데이터마다 다른 방식으로 사용합니다. 각 데이터의 특징에 따라 최대한 효율적으로 압축될 수 있도록 코드를 생성하고, 그 체계에 따라 압축합니다.

2) 접두부(prefix code)

접두부는 허프만 코딩의 규칙 중 하나로, 각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않게 하는 것을 의미합니다. 한마디로, 다른 문자와 겹치지 않도록 이진 코드를 부여하는 것이라 할 수 있습니다. 예를 들어, a라는 문자에 101을 부여했을 때, b라는 문자에는 1, 10, 101은 부여하지 않는 것입니다. 이러한 방식으로 접두부 코딩을 해야만 디코딩(Decoding, 인코딩: 암호화, 디코딩: 복호화)했을 때 문제가 발생하지 않습니다.

3) 최적 코드

최적 코드란 인코딩 된 메시지의 길이가 가장 짧은 코드를 의미합니다. 각 문자의 출현 빈도수를 먼저 계산하고, 그 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여합니다. 이를 통해 압축된 결과물을 생성합니다.

4) 허프만 트리(Huffman tree)

허프만 트리는 아래와 같은 규칙을 가집니다.

- 각 문자가 개별적인 트리인 상태에서 시작하여, 빈도수가 작은 두 트리를 합쳐서 보다 큰 트리를 생성하는 과정을 반복합니다.

- 각 노드는 빈도수를 표시합니다.

- 좌우의 두 간선은 각각 0과 1로 써줍니다.

- 합쳐지는 두 트리는 자식 노드를 갖는 부모 노드를 생성합니다.

- 부모 노드의 빈도수는 두 자식 노드 빈도수의 합입니다.

 

만약, 'aaabrbacard'라는 문자를 예시로 든다면, 아래와 같이 먼저 빈도수 별로 노드를 만들어 배치를 해줍니다.

허프만 트리(Huffman tree)

다음으로, 각각 가장 작은 빈도수를 가지는 c와 d를 합쳐서 부모 노드를 만들고, 그 값을 합인 2로 설정합니다. 마찬가지로 b와 r을 합쳐주고, 나머지도 순서대로 합쳐줍니다. 이러한 방식으로 생성된 선들에 각각 0과 1을 표기해 줍니다. 만약, 이를 바탕으로 b를 표기하고 싶다면, 노드를 따라 내려가 100 임을 알 수 있습니다. 마찬가지로 a는 0, r은 101, c는 110, d는 111입니다.