カラー画像のBTCアルゴリズム

実時間のデータ圧縮が可能なためには、各画素を２つのクラスに分類するためのアル ゴリズムは簡単で高速なものでなければならない。しかし、一般に使われている k-mean 法に基づくベクトル量子化法[107]は、データを繰り返し処理する アルゴリズムであるため計算に時間が掛かる。ここでは、ブロック内の画素の色情報 を主成分分析[22,68] することによって得られた主成分スコアを 用いてベクトル量子化器を設計する。各画素はその主成分スコアによって２つのクラ スに分類し、その分類結果に基づいて２つのクラスの代表色を決定する。

今、ブロック内の画素数を $m$ とし、そのブロックの $i$ 番目の画素の色の赤、緑、 そして青成分を $\mbox{\boldmath$x$}_i^T=(r_i,g_i,b_i)\ (i=1,\ldots,m)$ とする。以下では、 $\mbox{\boldmath$x$}_i$ を色ベクトルと呼ぶ。このとき、ブロック内の色の平均ベクトルおよび 共分散行列は、それぞれ、

$$\bar{\mbox{\boldmath$x$}} = \frac{1}{m} \sum_{i=1}^m \mbox{\boldmath$x$}_i$$ (279)

$$\Sigma = \frac{1}{m} \sum_{i=1}^m \mbox{\boldmath$x$}_i \mbox{\boldmath$x$}_i^T - \bar{\mbox{\boldmath$x$}} \bar{\mbox{\boldmath$x$}}^T$$ (280)

となる。従って、$i$番目の画素の主成分スコア $y_i$ は、

$$y_i = \mbox{\boldmath$u$}^T (\mbox{\boldmath$x$}_i - \bar{\mbox{\boldmath$x$}}) ,$$ (281)

で定義される。ここで、係数ベクトル $\mbox{\boldmath$u$}$ は、固有値問題

$$\Sigma \mbox{\boldmath$u$} = \lambda \mbox{\boldmath$u$}$$ (282)

から求められる。このとき、主成分スコアの平均値は常に $0$ となる。

また、共分散行列 $\Sigma$ は、３行３列の実対称行列であるから、 ３次の代数方程式の根を求めるための Cardano の公式を用いることによる最大固有 値 $\lambda$ を求めることができ、対応する固有ベクトルも簡単に計算できる。

主成分スコアに基づいて各画素を２つのクラス（$C_0$ と $C_1$）に分類するために は、１ビットのスカラー量子化器が利用できる。ここでは、１ビットのスカラー量子 化法として最も簡単な平均値による方法を用いるものとする。主成分スコアの平均値 は常に $0$ であるから、各画素の主成分スコアの符号を調べることによって２つの クラスに分類することができる。つまり、主成分スコアが $0$ 以下ならクラス $C_0$ に分類し、主成分スコアが $0$ 以上ならクラス $C_1$ に分類する。

ブロック内の各画素を２つのクラスに分類した後、その分類結果に基づいて各クラス の代表色を決定する。平均２乗誤差最小の意味で最適な代表色は各クラスの平均色で ある。