k-meansクラスタリングと画像の代表色抽出をTypeScriptで実装する【画像処理100本ノック】

概要

Q.88〜92ではk-means法を実装します。前半は画像ごとの特徴ベクトルをクラスタリングし、後半は画像内の全画素をRGB空間でクラスタリングして代表色へ減色します。

k-meansは次の2処理を、割り当てが変わらなくなるまで繰り返します。

while (changed) {
  changed = assignNearestCentroid(features, centroids, labels);
  centroids = updateCentroids(features, labels, k);
}

入力にはQ.84と同じ色ヒストグラム特徴を使います。正解ラベルを使わず、色分布の近い画像が同じグループへ集まるかを確認します。

画像1枚の各画素をRGBの3次元データとして扱います。Q.91では5個の初期代表色を選び、各画素を最も近い色へ分類します。Q.92では代表色をクラスタ内画素の平均へ更新し、収束まで繰り返します。

最後に各画素を所属クラスタの代表色で置き換えると、画像全体を5色で表現できます。Q.6の固定した4階調への減色と違い、入力画像の色分布に応じた代表色が得られます。

k-meansは初期重心によって局所解が変わります。クラスタへ画素が1つも割り当てられない場合の処理も必要です。実装を読むときは、収束条件、初期化、空クラスタの扱いを確認します。

1回の反復は、各データを最も近い重心へ割り当てるステップと、クラスタ内の平均で重心を更新するステップから成ります。データ数をN、クラスタ数をK、次元数をD、反復回数をIとすると、おおよその計算量はO(I × N × K × D)です。

重心の移動量が許容値未満になったら終了し、最大反復回数も設定します。所属ラベルが変わらなくなることを収束条件にしても構いません。浮動小数点の重心を毎回整数へ丸めると早く停滞するため、計算中は小数のまま保持し、表示時だけ丸めます。

完全な乱択より、互いに離れた初期重心を選びやすいk-means++を使うと悪い局所解を減らせます。比較実験では乱数シードを固定し、複数シードの最終誤差も記録します。

空クラスタが生じた場合は、最も誤差の大きい点を新しい重心にする、既存重心から離れた点を選ぶ、そのクラスタを維持する、などの方針があります。どの方法でも無言でNaNを作らないことが重要です。

画像減色ではRGBの距離が知覚上の色差と一致しない場合があります。結果を発展させるならLab色空間でクラスタリングし、RGBへ戻して表示する方法も比較できます。