数理解析研究所講究録
第 1744 巻 2011 年 181-184

181

2010 年度冬の LA シンポジウム [S2]量子セルオートマトンに基づく
画像圧縮のための画像変換アルゴリズム
大畑 和樹 *

1

西野 哲朗 \dag er

はじめに若月 光夫 \d ag er

3

量子コンピュータ

量子コンピュータとは，量子力学の原理を用いる
本節では，量子コンピュータの数理モデル [5] につことで，量子並列計算が可能なコンピュータである． いて説明する．量子コンピュータの状態は通常，量子コンピュータは，Shor のアルゴリズムによる整 次元の複素ベクトル空間 のベクトルで表され，任$2^{n}$$V$数の因数分解など特定の用途において，現在のコン 意のベクトルはと書く．これは状態ベクトルとピュータよりも効率よく処理を行える可能性がある 呼ばれる．ここで，を上の任意の状態ベ$|x\rangle$$|x\rangle,$が，未だ実現には至っていない [1].

量子コンピュー タのモデルとして，John Watrous
は 1 次元量子セルオートマトンを提案した [2]. これ$V$$a,$$b$による線形結合は，離散的な計算モデルである 1 次元セルオートマトンを量子的に拡張したものである．

$|y\rangle$

クトルとする．このとき，任意の複素数(1)$a|x\rangle+b|y\rangle$における状態となる．これを状態の重ね合わ現在，セルオートマトンを用いたアプリケーショはそれせという．ここで，状態ベクトルの係数ンや物理現象の解析手法などが多数提案されているぞれの確率振幅という．
が [3], 量子セルオートマトンを用いることで，より量子コンピュータの計算は，ユニタリな作用素有効な結果を得られる可能性がある．
を状態ベクトルに作用させたことによる，
も $V$$a,$$|x\rangle,$$b$$|y\rangle$$U$$|x\rangle\in V$

2

研究の目的

異なる確率振幅を持っ状態(2)$|z\rangle=U|x\rangle\in V$

画像圧縮では一般的に，画像データを圧縮しやすいように変換し，圧縮アルゴリズムを用いて，変換さ への遷移として考えることができる．ここで作用素れた画像データを圧縮する処理が行われている．先行研究では，1 次元セルオートマトンを用いた画像変$U$がユニタリであるとは(3)$UU^{\dagger}=U^{\dagger}U=I$

換を施すことで色の違いを平滑化し，圧縮率の向上を目指した [4]. しかし，人物の写真など画素の色の が成り立つことである．ここではの複変化が大きい複雑な画像では，圧縮率の低下や画質 素行列， は の共役転置行列， は単位行列で$U$$U^{\uparrow}$の劣化が生じるといった問題点があった．

$U$$2^{n}\cross 2^{n}$$I$ある．

量子セルオートマトンの最大の特徴は，状態の重ね合わせを利用できるという点である．この特徴を 4
量子セルオートマトン用いることで，上記の問題点を解決できる可能性がある．そこで本研究では，量子セルオートマトンに基セルオートマトンとは，単純な遷移規則によってセづく処理手法を用いた画像圧縮アプリケーションの ルの状態が離散時間で変化する計算モデルである [3].
提案および実装を目的とする．
セルオートマトンの離散時間的な変化は発展と呼ばれる．また，本研究で用いた 3 近傍の 1 次元セルオー.

トマトンは次のような特徴を持つ．
$*$$\dagger$$\ddagger$

電気通信大学大学院情報理工学研究科
第 1 著者に同じ
第 1 著者に同じ

セルは格子状であり，大きさはみな等しく，一直線上に並んでいる．

182$\bullet$$\bullet$

各セルは有限個の状態のうち，1 っの状態をとる． 状態の重ね合わせ
次の時刻のセルの状態は，現在の状態と近傍である両隣のセルの状態に基づく局所的な遷移関数によって決定する．

画像の各画素の色は，R, G, B 成分の重ね合わせによって表現されていると考えることができる．そこで R, G, B 各成分に対して式 (4) の遷移関数を適用し，色の平滑化を行う．
また，一般に PSNR(画像信号と，混入したノイズで規則番号として表すことができる．の比率) が $30dB$ 以上であれば，実用的な画像であると言われている [6]. そこで，PSNR が 3MB 以上か
1 次元量子セルオートマトンとは，1 次元セルオー つ圧縮率が最高となるような R, G, B 成分の近傍差トマトンを量子的に拡張したセルオートマトンであ分値の組み合わせを決定する．なお，近傍差分値の組
る [2]. 1 次元量子セルオートマトンには，状態遷移み合わせの決定方法は，以下の通りである．
$\bullet$.
.

局所的な遷移関数は，1 対 1 で対応付けることに関して次のような特徴がある．

5

次の時刻でセルは，局所的な遷移関数によって確率振幅を与えられた，状態の重ね合わせを成す．

1. ある近傍差分値において，PSNR が $30dB$ 以上かつ最小となるような発展回数を探す．このとき，R, G, B 成分それぞれの近傍差分値は同じ値にする．

1 次元量子セルオートマトンの発展は，可逆である．

2. 異なる近傍差分値に対して (a) を行う．

3. (b) で求めた回数だけ発展させた画像の PSNR

平滑化処理

先行研究では，1 ピクセルを 1 セルとした 256 状
態 3 近傍の 1 次元セルオートマトンが用いられ，色の違いを平滑化させるため，式 (4) の遷移関数が提案された．なお，セルの位置座標を , 時刻を とした
$t$

$i$

とき，位置$i$のセルの時刻$t$での状態を$a\dot{i}$と表す．と圧縮率が共に最高となるような近傍差分値を探す．

4. (c) で求めた近傍差分値を参考にし，PSNR が$30dB$ 以上かつ圧縮率が最高となるような近傍差分値の R, G, B 成分の組み合わせを求める．
このとき，発展回数は固定する．

また，近傍差分値とは平滑化を行うためのしきい値であり，1 から 255 までの任意の値を設定する．
可逆性

量子セルオートマトンの発展の可逆変換性になら$a_{t+1}^{i}=\{\begin{array}{l}\frac{a^{:-1}+a^{:+1}}{2}(|a_{t}^{i-1}-a_{t}^{i+1}|< \text{近傍差分値} )a_{t}^{i}(\text{上記以外})\end{array}$(4)

い，画像を変換する際にログファイルを作成することで，圧縮された画像の復元を可能にする．作成する
ログファイルは，次の 2 種類である．
ログファイル 1 遷移関数と規則番号との対応表
ログファイル 2 各セルでの状態遷移で使用された規則番号を記した表

6

提案アルゴリズム

6.1

応用する量子セルオートマトンの性質 6.2

本研究では，量子セルオートマトンの以下の 2 つの性質を模倣して提案アルゴリズムの実装を行う．

画像圧縮アルゴリズム

本研究では画像圧縮アプリケーションを構築するため，以下に示す圧縮用アルゴリズムと復元用アルゴリズムを提案する．なお，本研究では，圧縮対象画
像ファイルは bmp 形式のファイルとする．

183
圧縮用アルゴリズム

なお，圧縮率は次の式から求める．

1. 入力として bmp 形式の画像ファイルの 1 ピク
セルを 1 セルとして読み込み，セルの初期状態と R, G, B 成分ごとに近傍とし，発展回数

圧縮率

$=$

「縮オ$\grave\grave$$|)$$\grave\sqrt{}\grave$

ナフルァフイァイサルイサズイズ(5)$\cross 100$

$T$差分値を与える．

2. 読み込んだ全部のセルに対して遷移関数を適用
し，R, G, B 成分それぞれについてファイル 1,また，lena-opti, text-opti を求める際に設定した発展回数および近傍差分値は，表 1 のとおりである．
する部門です。粛部門ではファイル 2 を作成する．

3. 2 の操作を発展回数たり、席替えしたりする特別$/|$ち抜き制』です。 ゲーム行 ,$|$

$T$$\Delta\neg$だけ繰り返す．

$|$PointJ

4. 発展させた結果として得られるセルの状態のbmp 形式の画像ファイルを，bzip2 を用いて圧$\beta g$

目 $\dagger 2_{PO}|ntJ$『六裂、もつとも $P0|nt$ の高し、$\eta=$’’$\backslash$縮して出力する．と、気$D^{v}i\Xi$(なりそうですが、ていたたいた後は、超ハイス$)$を勝ち抜いた猛者たちによそ
On $100QJ$ の称号を手にする

復元用アルゴリズム

1. 入力として，圧縮された bmp 形式の画像ファイ

ル，圧縮に使用した発展回数$T$, 圧縮時に作成し(a) lena$|$(b) text

図 1: 圧縮前の画像たログファイルを与える．
する部門です。粛部門では

2. ファイル 2 の内容を参照し，記載されている規たり、席替えしたりする特別

則番号と対応している遷移関数をファイル 1 か$|$$P0|nt4\beta g@*?P0|nt\Delta\beta$ 六

ルに色を埋め込んでいく．

裂、もつとも $oo|nt$ の高い’ と、気だけ繰り返す$)$$\eta=_{J}$

そうですが、ていただいた後は、超ハイス(a) lena-opt$|$(b) text-opti$i$

圧縮用および復元用アルゴリズムを実装し，画像する邸門でず． 邸酌で $1l$ 乞$\Phi$たり、席類えしたりする特獲増:籔き制 です．: ゲーム
point\S@ $*?poinfl\#\cross$$\mathfrak{t}5$$\mathfrak{B}^{\gamma}$’ と、気$\backslash$$\}$$\acute{i}\overline{J}$と 6point の罵$\delta^{\sigma}$

溝$\langle a$$\iota(\eta^{s_{d}}$りそうですが、ていただし、た後 S 、超ハイス$|$を総ち叛し、た鑓艦たちによ

色の変化が大きい複雑な画像のうち，使われている色の種類が多い画像である lena 図 $1(a))$ と少ない画像である text 図 $1(b))$ について提案アルゴリズムによる画像圧縮を行い，lena-opti 図 $2(a))$ ,text-opti(図$2(b))$ を生成した．また，PSNR と圧縮率の比較のた$\beta$rr

喫、圧縮率および PSNR の比較

屋 $n?00$ 鵯の称$|$$($$($め，先行研究の手法を用いて lena と text を圧縮し，lena-prev 図 $3(a))$ , text-prev 図 $3(b))$ を生成した．
$($(a) lena-prev$i$\S を夢 こする$($$($$\prime_{(}-$図 2: 提案手法を用いて圧縮した画像に圧縮および復元処理を施した後に処理前と処理後の画像データを比較した．その結果，差異は生じなかったので，アルゴリズムは機能したと言える．この結果を踏まえて，以下の 2 つの調査を行った．

7.1$\iota\int$

on2009 』の称号を手にするの画像ファイルを出力する．

実験結果(なを鵬ち抜いた猛者たちによ4. 復元した結果得られるセルの状態の bmp 形式

7$D^{r}i\Xi$$\backslash$$T$$/|$

ち抜き制』です． ゲーム行;$|$ら探し出す．この遷移関数を用いて，各ピクセ
3. 2 の操作を発展回数$\triangle\neg$(b) text-prev

図 3: 先行研究の手法を用いて圧縮した画像

$|$

184
表 1: lena-opti, text-opti を求める際に設定した発表 4: lena の画像圧縮時に生成される各ファイルの展回数および近傍差分値

サイズ (単位:[Byte])

表 2: lena における先行研究との比較 (単位: PSNR
は $[dB]$ , 圧縮率は$[$% , 他はすべて [Byte]$]$$)$

表 5: text の画像圧縮時に生成される各ファイルのサイズ (単位: [Byte])

表 3: text における先行研究との比較 (単位: PSNR
は $[dB]$ , 圧縮率は$[$% , 他はすべて [Byte]$]$$)$

案手法による画像圧縮で高い圧縮率を実現できることがわかった．また，画像圧縮時に作成したログファイルを用いることで，圧縮された画像を復元するアルゴリズムによって画像を完全に復元できることもその結果，表 2, 表 3 より，text は先行研究と同等 確認できた．今後の課題としては，アルゴリズムやプログラムの改良による PSNR の保持，発展回数や近の圧縮率を保持することができた．また lena は，適切な近傍差分値と発展回数を設定することで，先行 傍差分値の設定の自動化，ログファイルの更なる縮研究に比べ，画質を保持したまま圧縮率を上げるこ小化などが挙げられる．とができた．

参考文献

7.2

[1] 西野哲朗，“量子コンピュータの理論”, 培風館，ログファイルのサイズの調査

lena および text の画像圧縮の際に作成されたログファイルのサイズは表 4, 表 5 のとおりである．表2002.
[2] John Watrous, “On One-Dimensional Quantum
Cellular Automata”, Proceedings of the 36th

4 と表 5 を比較すると，ログファイルのサイズと圧Annual Symposium on Foundations of Com縮された画像ファイルのサイズの和は，text の方がputer
Science, 1995.
lena よりも小さくなっている．これは，使用されている色の種類が少ないために，保存しておくべき遷 [3] 加藤恭義，光成友孝，築山洋，“セルオートマト移関数の種類が大幅に削減されたためであると考えられる．したがって text の方が，lena に比べて少ないデータで画像を復元できることがわかる．

8

おわりに
本研究では先行研究の結果を受けて，色の変化が大きい複雑な画像の圧縮率が高くなるような，量子セルオートマトンに基づく画像圧縮アプリケーションを提案した．その結果，色の変化が大きな画像の中でも，使用されている色の種類が少ないものほど，提ン法複雑系の自己組織化と超並列処理-”, 森北出版，1998.

[4] 渡辺潤，“セルオートマトンによる画像圧縮の研究”, 電気通信大学情報通信工学科卒業論文，2008.
[5] 上坂吉則，“量子コンピュータの基礎数理”, コロナ社，2000.
[6] 株式会社高度圧縮技術研究所，
http: $//www$ . supercompression. com/motionpict

ure.html