Octree Quantization

컬러 양자화(color quantization) 방법으로는 Median-Cut 알고리즘 외에도 Octree를 이용한 알고리즘이 널리 사용된다. 예를 들어 Paint Shop Pro에서는 Median-Cut, Octree, 그리고 간단한 Web-safe 양자화 방법을 모두 제공한다.

Octree는 하나의 노드가 최대 8개의 자식 노드를 가지는 트리 자료구조이다. RGB 컬러는 R, G, B 각각이 8비트로 표현되므로, 각 비트 평면(bit plane)의 비트값 \((R_i,G_i,B_i)\)을 이용하면 한 레벨에서 가능한 경우의 수는 \(2^3=8\)가지가 된다. 따라서 각 경우를 하나의 자식 노드에 대응시키면 RGB 컬러 공간을 Octree 구조로 자연스럽게 표현할 수 있다.

24비트 RGB 컬러를 모두 표현하면 루트 노드를 포함하여 깊이가 9인 Octree가 만들어진다. 각 레벨은 R, G, B의 한 비트씩을 차례로 사용하여 하위 노드로 내려가며, 최종 leaf 노드는 하나의 RGB 컬러를 나타낸다. 이론적으로는 최대 \(8^8=2^{24}=16,777,216\) 개의 leaf 노드가 존재할 수 있다.

Octree 양자화에서는 영상을 한 번 스캔하면서 등장하는 컬러만을 이용하여 Octree를 동적으로 구성한다. 새로운 컬러가 입력될 때마다 해당 leaf 노드에는 그 컬러의 출현 횟수와 RGB값의 합이 저장된다. 트리를 구성하는 과정에서 leaf 노드의 개수가 원하는 팔레트 크기를 초과하면 reduction 과정을 수행하여 leaf의 개수를 줄인다.

Reduction에서는 가장 깊은 내부 노드(internal node)를 선택한 뒤, 그 노드의 자식 leaf 노드들을 하나의 부모 leaf 노드로 병합한다. 이때 부모 노드에는 자식 노드들의 RGB값의 합과 픽셀 수를 모두 누적하여 저장한다. 이러한 병합 과정을 반복하면 leaf 노드의 수가 점차 감소하여 원하는 팔레트 크기에 도달하게 된다.

최종적으로 각 leaf 노드에서 저장하고 있는 RGB 합을 픽셀 수로 나누어 평균 RGB값을 계산하고, 이를 대표 컬러로 사용하여 팔레트를 만든다. 원본 영상의 각 픽셀은 자신이 속한 leaf 노드의 대표 컬러로 대체되어 양자화가 완료된다.

결과적으로 Octree 양자화는 RGB 컬러의 상위 비트가 전체적인 색상을 결정한다는 점을 이용하여, 하위 비트에 해당하는 세부적인 색상 정보를 단계적으로 제거하면서 컬러 수를 줄이는 방법이다. Median-Cut이 컬러 공간을 반복적으로 분할하여 대표 컬러를 찾는 방식이라면, Octree는 컬러 공간을 계층적인 트리 구조로 표현한 뒤 하위 노드를 순차적으로 병합하여 원하는 개수의 대표 컬러를 만드는 방식이라는 차이가 있다.

       
특정 RGB 비트 평면에서 R, G, B비트 값을 이용하여서 child-노드의 인덱스를 만드는 방법은

    child-node index = (R-비트<<2)|(G-비트<<1)|(B-비트) ;

 

     (R, G, B)=(109,204,170)의 경우;

      node |
      level | 0 1 2 3 4 5 6 7
     -------------------------
           R | 0 1 1 0 1 1 0 1
           G | 1 1 0 0 1 1 0 0
           B | 1 0 1 0 1 0 1 0
     ------|------------------
      child | 3 6 5 0 7 6 1 4
     index |
  

Octree 알고리즘은 컬러 영상을 한 번만 스캔하면서 트리를 동적으로 구성할 수 있으므로, 일반적으로 Median-Cut 알고리즘보다 메모리 사용량이 적고 계산 효율이 높은 편이다. 또한 트리의 최대 깊이를 제한하면 계산량과 메모리 사용량을 더욱 줄일 수 있지만, 그만큼 색 표현의 정확도는 다소 감소할 수 있다.

최종적으로 팔레트를 구성하는 대표 컬러는 각 leaf 노드에 누적된 RGB값의 평균으로 계산된다. 따라서 대표 컬러는 leaf 노드가 나타내는 비트 패턴과 반드시 일치하지 않으며, 해당 영역에 포함된 픽셀들의 평균적인 색상을 나타낸다.

원본 영상의 각 픽셀은 자신이 속한 leaf 노드의 대표 컬러로 대체되어 양자화가 완료된다. 새로운 컬러를 팔레트에 대응시키는 과정은 루트 노드에서 시작하여 트리를 따라 내려가기만 하면 되므로 매우 빠르게 수행할 수 있다.

Octree 양자화는 트리의 생성, 노드의 병합(reduction), 그리고 팔레트 생성이 모두 트리 구조를 기반으로 이루어진다. 재귀(recursion)를 이용하면 비교적 간결하게 구현할 수 있으며, 반복(iteration)을 이용한 구현도 가능하다. 또한 널리 사용되는 알고리즘인 만큼 인터넷에서 다양한 구현 예제와 공개 소스를 쉽게 찾아볼 수 있다.

 

참고 논문: "A Simple Method for Color Quantization: Octree Quantization." by M. Gervautz and W. Purgathofer 1988.

256 컬러 이미지(트리 깊이 = 5): RGB 값이 주어지면 전체 트리에서 해당 leaf을 찾아서 팔레트 인덱스를 얻는다. 이와는 다른 방법으로는 팔레트가 주어졌으므로 주어진  RGB 값과 가장 가까운 유클리디안 거리를 주는 팔레트의 인덱스를 할당하는 방법도 있다. 이 방법을 이용하면 아래의 결과와 약간 차이가 생긴다.

양자화된 컬러 이미지

L2 error;

** 네이버 블로그에서 이전;

source code(C++): web.archive.org/web/20050306011057/www.drmay.net/octree/