コルモゴロフ複雑性に 基づ く 画像圧縮と分類に 関する実験と考察
Image compression and clustering based on Kolmogorov complexity
齋藤 高央 †
Takao Saitoh

1.

湊 真一 †
Shin-ichi Minato

ま え がき近年、インターネットなど の 普及に より、多量の 画像データを扱う 機会が増え てき ている。多量の 画像データを手作業で分類するの は困難であり、自動的に 分類できる手法への ニーズが高まりつつある。
情報の 複雑さを表す指標とし て、コルモゴロフ複雑性が知られている。 [5] コルモゴロフ複雑性に 基づ く 類似度判定手法の 一つとし て、圧縮度を用いた手法が提案されている。 [3]本研究では、パラメータフリーな画像の 分類手法の 確立を目指し ている。そ こ で基本的性質を調査するために 、まず 画像に 対し てコルモゴロフ複雑性に 基づ く 圧縮度を用いた類似度判定を行い、画像を分類する実験を行っ た。

2.

コルモ ゴ ロ フ 複雑性と正規圧 縮距離

コルモゴロフ複雑性は、有限長の データ列の 複雑度を表す指標の 一つで、与え られた文字列 x の コルモゴロフ複雑性 K(x) は、K(x) を出力するプログラムの 最短長で 表される。
こ の コルモゴロフ複雑性を用いた データ間の 距離の定義とし て、Normalized Information Distance(以下NID) が提案 [1][2][6] されている。文字列 x, y 間の 距離
N ID(x, y) は、以下の よう に 定義される。

N ID(x, y) =本実験では、画像の みを扱う こ ととし た の で、圧縮形式も画像特有の 形式を用いた方がよいと判断し 、可逆圧縮で あり、扱え る色数が多い PNG 形式を用いた 。

3.

実験

本実験は、Pentium M 1.80GHz、RAM 2GB の 計算機で 、OS は WindowsXP SP3 を用いて行っ た 。実験プログラムは C#を用いて作成し 、画像の 圧縮に は ImageMagick の C#向け ライブラリで ある MagickNet を用いた 。

3.1 概要本実験の 目的は、基本的な性質を把握するこ とであるの で、比較的単純なパターンの 画像を用いて行う こ ととし た。分類結果の 判定がし やすいもの とし て、10 カ国の国旗 (図 1) を用い、以下の 手順で 実験を行っ た 。

M ax(K(x), K(y))
M ax(K(x|y), K(y|x))

こ こ で 、K(x|y) は、y を入力とし た とき に x を出力するプログラムの 最短の 長さで あり、K(x) は、入力なし で x を出力するプログラムの 最短の 長さである。し かし 、K(x) は原理的に 計算不能で あるこ とが知られており [5]、N ID(x, y) を直接求めるこ とがで き ない。
そ こ で、コルモゴロフ複雑性を近似的に 求める手法が提案 [3] されている。具体的に は、ある文字列 x をある
圧縮プログラム C を用いて復号可能な状態で 究極に 圧縮し た 時の ビット長を C(x) と表し 、こ れを文字列 x のコロモゴロフ複雑性 K(x) の 近似値と考え る。
こ の 近似を用いたデータ間の 距離を Normalized Compression Distance(以下 NCD) と呼び 、下の よう に 定義される。

N CD(x, y) =ツォイクマ ン ト ー マ ス †Thomas Zeugmann

C(xy) − M in(C(x), C(y))
M ax(C(x), C(y))

こ こ で、C(x) はある文字列 x を圧縮プログラム C を用いて圧縮し た 時の ビット長であり、C(xy) は文字列 x, yを結合し た もの を圧縮プログラム C を用いて圧縮し た
時の ビット長で ある。
† 北海道大学 大学院 情報科学研究科

図 1: 実験に 用いた 10 カ国の 国旗
まず 前処理とし て、画像を縦横比 4:3 に 揃え た 24bitの Microsoft Windows Bitmap Image 形式に 変換し た 。
こ れは、現在の 結合処理の 都合で、画像の 縦横比を揃えておく 必要があっ た からで ある。
次に 画像を結合・圧縮し て距離を計算する。こ れをす
べての 組み合わせ に 対し て繰り返し 実行し 、距離行列を作成し た 。こ の 距離行列を基に クラスタリングを行い、結果を比較し た 。
画像ファイルを扱う 場合、単純に 上下に 画像を結合すると、元の 画像で同じ位置に あっ た 部位が離れて配置されてし まう こ とに なる。例え ば、元の 画像で左上だっ た部分は、結合後の 画像では左上と中央付近に 配置される
こ とに なる。
こ れを改善するため、画像を 1px 幅でインターリーブ結合する方式での 実験を行っ た 。インターリーブ結合の場合、元画像で左上端に あっ た ピクセル同士が、結合後の 画像でも左上端で上下に 並ぶこ とに なり、より圧縮率の 改善が見込めると考え た た めで ある図 2: 本手法を用いた距離行列に よるクラスタリング結果

4.

図 3: Complearn を用いた 距離行列に よるクラスタリン
グ結果

結果

4.1 Complearn との比較
圧縮度ベースの 距離を計算するツールとし てよく 知られているもの に Complearn[3] がある。Complearn は汎用の 圧縮アルゴリズムを用いて距離を計算するツールであるの で、汎用アルゴリズムと画像向け の アルゴリズムの 結果を比較するこ とができ る。比較に 用いたの はComplearn バージョン 0.9.7 で 、圧縮形式は zlib を用いた 。
Complearn はクラスタリングを行う 機能を持っ ているが、本実験に おいてはクラスタリング手法を統一する必要があっ た の で 、こ の 機能は使用し ていない。
クラスタリングを行っ た 結果は図 2,3 の よう に なる。
両者とも星条旗、縦縞を図案に 持つ国旗、丸を図案に 持つ国旗の 3 つの クラスタができ ているこ とが分かる。縦縞の クラスタの 距離に 一部差があるが、全体とし てみると類似し た 結果となっ た 。 PNG 形式は内部的に zlib を使っ ているの で 、こ の 結果は妥当と考え られる。

図 4: 本手法を用いた インターリーブ結合で の クラスタ
リング結果

4.2 結合方式に よる 比較
単純な上下結合とインターリーブ結合での 結果 (図 4)を比較し た 。単純な画像の 場合、インターリーブ結合を行っ た こ とで結合時の 圧縮率が悪化し 、クラスタリング結果に 悪影響を与え ていると推測で き る。

を用いた 場合の 距離行列も表 2 の よう に なり、類似し た傾向に ある。

4.3 自分自身との距離距離行列の 対角線は自身との 距離であるの で、0 に なる事が望まし い。実験の 結果得られた距離行列は表 1 のよう に なっ た 。こ れは我々が利用するこ との でき る圧縮プログラムが理想的な動作をする圧縮プログラムではな
く 、理想的な圧縮結果を得るこ とはでき ないた めであると考え られる。自身との 距離は近似的に 0 とみなす事とするが、ややばらつき が大き い。
例え ば、アメリカ合衆国の 場合は 自身との 距離が0.0559 となり 0 に 近似で き るが、フランスの 場合は0.3713 となり、0 に 近似するに はやや大き い。Complearn

そ こ で、圧縮後の ファイルサイズを調べてみると、表3 の よう に なっ た 。圧縮後の ファイルサイズが小さいもの ほど 、自分自身との 距離が大き く なっ ているこ とがわかる。こ の 傾向は同じクラスタに 分類された他の 国旗の場合でも共通し ており、圧縮後の ファイルサイズは（縦縞の 図案を持つ国旗）＜（丸の 図案を持つ国旗）＜（星条旗）となっ ていた 。
こ れらの 結果から、圧縮されやすい画像の 場合、結合時の 圧縮率が改善されず 近似が成立し づ らく なっ ていると考え られる。

表 1: 実験プログラムに よる距離行列（一部抜粋）
国名 バングラデシュ フランス アメリカ
バングラデシュ
0.15370.91920.9593フランス
0.91670.37130.9740アメリカ
0.96000.97330.0559International Conference, TAMC 2006, Beijing,
China, May 2006, Proceedings, Vol.3959 of Lecture
Notes in Computer Science, Berlin Springer, pp.2145 (2006) (Complearn http://www.complearn.org/)[4] Robert Gentleman and Ross Ihaka etal. “RDocumentation http://www.r-project.org/other表 2: Complearn に よる距離行列（一部抜粋）
docs.html”
国名 バングラデシュ フランス アメリカ
バングラデシュ0.18580.93540.9806 [5] A.N. Kolmogorov “Three approaches to the quantiフランス
0.93540.4051
0.9946
tative definition of information,” Problems Inform.
アメリカ
0.9806
0.99420.0592
Transmission, 1:1(1965), 1-7.
表 3: 圧縮後の ファイルサイズ
単独時 (byte)
結合時 (byte)

5.

バングラデシュ
1177
1293

フランス
237
312

アメリカ
3077
3341

終わ り に汎用の 圧縮形式に 変え て、画像特有の 圧縮形式を用いて NCD を計算する手法に 関し て実験を行っ た 。本実験
では、内部的に 汎用の 圧縮形式に 近いアルゴリズムを使う PNG 形式を選択し た た め、汎用の 圧縮形式との 違いがあまりない結果となっ た 。画像向け の 圧縮形式を使用し た場合でも、既存の 形式と同程度の 分類結果を得られるこ とが分かっ た 。
本実験に おいては 単純な上下方向の 画像結合が有効であっ た が、風景写真を用いて行っ た 実験ではインターリーブ結合の 方が優勢な結果が得られるなど 、現段階ではすべての 種類の 画像をパラメータフリーで分類する事はでき ていない。また 、類似の 色成分を集中させ るた めに ブロックソートなど を用いる手法も考考え られる。
今後は、画像特有の 成分を活用する可逆圧縮形式などを用いての 実験を行う 予定で ある。

謝辞
本研究の 一部は、文部科学省科学研究費補助金特定領域研究「情報爆発時代に 向け た 新し い IT 基盤技術の 研究」（領域番号 456 に よる）

参考文献[1] Charles. H. Bennett, Peter Gacs, Ming Li, PaulM. B. Vitányi and W.H.Zurek: “Information Distance,” IEEE Transactions on Information Theory,44, 4, pp.1407-1423 (1998)[2] Rudi Cilibrasi and Paul M. B. Vitányi: “Clusteringby compression,” IEEE Transactions on Information Theory, 51, 4, pp.1523-1545(2005)[3] Rudi Cilibrasi and Paul M. B. Vitányi: “Similarity of objects and meaning of the words,” Theoryand Applications of Models of Computation, Third[6] Ming Li, Xin Chen, Xing Li, Bin Ma and Paul M. B.
Vitányi: “The similarity metric,” Proc. 14th ACMSIAM Symposium on Discrete Algorithms (SODA),
pp.863-872 (2003)