八分木
八分木による色量子化アルゴリズムは、1988年、Gervautz と Purgathofer が考案した。これは、画像の色データを最大9レベルの深さの八分木で符号化するものである。八分木がこの用途に使われるのは、 2 3 = 8 {\displaystyle 2^{3}=8} であり、かつRGBモデルでは色の成分が3つになっているためである。赤 (Red)、緑 (Green)、青 (Blue) の最上位ビットの値を数式(例えば 4r + 2g + b)に入れて、根ノードからの分岐を決定する。次の分岐は最上位から2番目のビットで同様に行う。最下位ビットの方は木構造のサイズを減らすために無視することがある。
木構造の大きさは制限可能であるため、このアルゴリズムはメモリ効率がよい。八分木の最下位レベルにある葉ノードには、木構造内では表されていない色データが対応している。また、レベルが深くなるほど、色の差異は微妙になる。パレットの色数と葉ノードの個数を常に比較しながら標本化していき、葉ノードの個数がパレットの色数を越える場合は、その部分の木構造を切り捨てて親ノードを葉ノードとして色を対応させる。その際に各葉ノードの色となっている標本数をカウントしておいて、切り捨てる部分を決定するのに使う。