[Computer Vision] Objectives - Huffman Coding, Run-length Encoding

🧑🏻‍💻용어 정리

Computer vision
Edge
Segmentation
huffman coding
run-length encoding

 

지난 시간까지 edge를 제대로, 나누는 방법에 대해서 알아봤습니다.

 

그 방법에는 within-class variance OR between-class variance가 존재하죠.

 

 

 

Objectives

 

아래 세 가지 알고리즘은 모두 압축을 위한 Algorithm입니다.

 

• Huffman Coding
• Run-length Coding
• JPEG Compression

 

압축이 필요한 이유는 영상 데이터가 너무 커서입니다.

 

위와 같이 pixel 하나에 8비트,

 

그리고 이것이 width x height 만큼 존재하며, 이것이 1초라면 30 프레임이라 하면 30도 곱해줘야합니다.

 

용량이 너무나 크게 되죠.

 

그래서 영상 압축을 위한 기술이 필요해진 것입니다.

 

 

영상을 위한 압축 방식이라 이것을 동영상으로 확장했을 때 방식이 약간 달라집니다.

 

우리는 영상 압축에 초점을 두고 배워보도록 하겠습니다.

 

압축에는 두 가지 방식이 존재합니다.

 

• Lossless compression 무손실 압축
  • 데이터 그대로
• Loss compression 손실 압축
  • 압축률을 극대화 시키고 데이터 손실을 감수하겠다

 

 

Huffman Coding

 

 

이 huffman coding의 concept는, 자주 발생하는 정보에 더 적은 bit를 부여하겠다는 것입니다.

 

어떠한 데이터가 얼마나 발생하는지 우리는 알 수가 있죠.

 

자주 나오는 것에 적은 bit 수를 부여한다는 것으로 봅니다.

 

그럼, 용량이라는 것은 빈도수 x 해당 비트 수이죠.

 

그렇게 해서 모든 숫자에 대해서 8비트씩 부여하는 것보다 압축률을 올릴 수 있습니다.

 

 

위와 같이 pixel 값이 0 ~ 255가 아닌 0 ~ 3 정도인 아주 간단한 예시를 먼저 살펴보겠습니다.

 

그리고 각 pixel 값에 해당하는 확률이 위와 같이 주어졌다고 해봅시다.

 

위 case에서 필요한 4가지 경우에 대해서 bit는 2개만 있으면 됩니다.

 

그리고 우측 variable code와 같이,

 

더 자주 나오는 것에 더 적은 bit 수를 부여합니다.

 

 

그리고 이 각각에 대해서 필요로하는 평균 bit 수를 계산해볼 수 있습니다.

 

 

위 계산 과정을 통해 fixed code로 하는 것보다 빈도에 대해서 계산하는 variable code로 우리는 0.1이라는 bit 수를 줄일 수 있었습니다.

 

그리고, 압축에 대해서 이야기할 때 Entropy H라는 것이 있습니다.

 

확률이 주어졌을 때, 해당 데이터를 encoding하기 위해서 필요로 하는 이론적인 최솟값입니다.

 

 

그래서 위 수식에 의해서, 각 pixel에 대해서 확률이 주어지면 위와 같이 확률값을 계산해서 대입해줄 수 있습니다.

 

그래서 이러한 이론적인 최솟값이 나오게 됩니다.

 

이 값에 가까워지는 것을 목표로 한다는 것입니다.

 

 

이제 Huffman Coding을 구현하는 방법에 대해 알아보겠습니다.

 

각 pixel 값에 대해서,

 

(빈도수) / (전체 수) 가 곧 확률이니, 빈도가 나와있다고 봐도 무방합니다.

 

1. 그렇게 확률을 쭉 나열합니다.

 

2. 가장 작은 확률 두 개를 더합니다.

 

3. 그 다음 남은 것 중 가장 작은 확률 두 개를 계속 더해나갑니다.

 

그렇다면 위 Binary Tree와 같은 결과가 도출됩니다.

 

이것이 Huffman Tree를 만드는 과정입니다.

 

각 트리에서 위에는 0, 밑에는 1을 부여했습니다.

 

여기서 bit를 부여하는 방식은 1.0부터 시작하여 각각의 지점으로 도달할 때까지의 bit를 측정하면 되는 것입니다.

 

그래서 각 pixel에 대해서 코드화 시키기 위해서는, encoding하기 위해서는 새로 나온 codeword로 바꾸는 것입니다.

 

 

아래와 같이 8가지 pixel이 있는 경우를 봅시다.

 

우리가 8가지 pixel을 위해선 3 bit가 필요하죠.

 

그런데, 위와 같이 Entropy 공식에 대입만 하였더니 위와 같이 3보다 작은 숫자가 나왔습니다.

 

그래서 위와 같이 fixed 된 값보다 작은 수의 bit 수를 얻어낼 수 있습니다.

 

 

트리도 아까 구한 것과 같이 만들 수 있습니다.

그리고 0과 1을 써놓고 끝부터 따라서 하면 아래와 같이 나옵니다.

 

그래서 이 bit를 통해 평균 bit 수를 계산해볼 수 있습니다.

 

계산하면 2.7이 나옵니다.

 

위에서 계산한 entropy 값에 근접해 갑니다.

 

그래서 아래와 같이 3 4 0 0 1 2 5 라는 숫자가 들어오면 아래와 같이 우리가 설정한 Huffman code로 바꿔주면 됩니다.

 

이렇게 encoding이 되었습니다.

 

 

그리고 위 테이블에 있는 숫자가 있으면 Huffman code에서 다시 pixel 값으로 돌아오는 Decoding이 가능해집니다.

 

 

 

 

Run-length Encoding

 

Method 1

 

encoding 시 나온 pixel의 각 횟수를 적는 방식입니다.

 

000000이 나온다면 0이 06번 나왔다고 볼 수 있겠죠.

 

그런데 우리 실생활에서 이렇게 같은 숫자의 나열이 잘 나오지는 않습니다.

 

한편,

 

그런데 edge와 같은 binary image의 경우에는 나올 수가 있습니다.

 

아니면 이전 Huffman Coding을 지나면 Binary Encoding을 할 수도 있습니다.

 

그러한 형태 또한 0이나 1이 반복이 많이 되는 경우가 있겠죠.

 

그러한 것들을 한 번 더 저장할 때 사용할 수 있는 것이 이 Run-length Encoding입니다.

위 matrix를 보시죠.

 

이 경우에는 우리가 row 단위로 이 데이터를 저장할 것입니다.

 

맨 처음 row를 보면,

 

먼저 0으로 시작한다고 가정해봅시다.

 

그럼 0이 1번 발생, 그리고 1이 2번 발생, 그리고 0이 3번 발생했습니다.

 

이것에 대한 정보를 (123)으로 encoding한다면,

 

Decoding 시 011000으로 복원할 수 있겠죠.

 

 

그리고 3번째 줄에서, 우리는 이것을 0으로 시작한다고 가정했기 때문에,

 

1로 시작하는 수에 대해서 0이 하나도 안 나왔으니 0이 0번 나옴을 표시해주고 그 다음 counting을 이어가야 합니다.

 

아무래도 0,1이 반복되면 부담이 되고, 하나가 계속해서 나오면 효과가 높은 방법입니다.

 

 

Method 2

그리고, 2번째 case의 경우도 row 단위로 하긴 하는데 방법은 조금 다릅니다.

이번에는 1이라는 숫자 기준으로 몇 번 째에 몇 번 반복했나를 보는 것입니다.

 

위 첫 row는 1이 2번째에서 2번 반복 되었습니다.

 

그것을 22로 나타냅니다.

 

3번째 row의 경우는 1이 1번째에서 3번 반복 그리고 6번째에서 1번 반복이므로, 1361로 적습니다.

 

 

결국 반복되는 횟수를 기록한 것이 run-length encoding의 핵심 아이디어입니다.

 

이러한 방법은 binary 영상에 적용해볼 수 있습니다.

 

그냥 영상은 256 중에 반복되는 횟수가 적으므로 이 방법은 오히려 손해입니다.