（様式第 20）成果報告書

共同利用（産業利用トライアルユース：先端研究施設共用促進事業『みんなのスパコン』TSUBAME によるペタスケールへの飛翔）
成果報告書 平成 21 年度 新規利用拡大 課題 i09ne

進化的映像符号化の高度並列シミュレーション
Highly Parallelized Simulation of Evolutive Image Coding
高村誠之
Seishi Takamura
日本電信電話株式会社 NTT サイバースペース研究所
NTT Cyber Space Laboratories, NTT Corporation
http://www.ntt.co.jp
邦文抄録
遺伝的プログラミング(GP)に基づく「進化的手法」は、計算機によるアルゴリズム自動生成を可能とし、プラント制御、ロボット制御、株価予想など幅広く応用されている。しかしながら、JPEG や H.264/AVC などの従来の映像/画像符号化方法は、すべて固定された(動的でない)アルゴリズムを用いている。筆者が検討を進めている「進化的符号化」
は、GP に基づき入力画像に特化した画像予測アルゴリズムを自動生成するもので、従来の「固定アルゴリズム」「人が考案」「人がコーディング」からの脱却を図る、新たなパラダイムに向けた試みである。本論文では、進化処理を並列化し、さらに TSUBAME を用いることで進化処理が 2-3 桁高速化し予測効率が約 2%向上した事例を紹介する。
英文抄録
Evolutive methods based on genetic programming (GP) enable dynamic algorithm generation, andhave been successfully applied to many areas such as plant control, robot control, and stock market
prediction. However, conventional image/video coding methods such as JPEG and H.264/AVC all use
fixed (non-dynamic) algorithms without exception. The evolutive coding enables an automatic
generation of pixel prediction algorithm. It is a radical departure from conventional ``fixedalgorithm'', ``man-made algorithm'' and ``hand-made programming'' toward a new paradigm. In thisreport, we introduce a GP-based image predictor that is specifically evolved for each input image,which have been evolving day by day. We demonstrate its prediction performance. We also reportabout speeding up the evolution process using parallelization by a factor of 100-1,000 as well as
improving the prediction efficiency by about 2 %.

Keywords: 遺伝的プログラミング, 画素予測器, 可逆画像符号化, 並列処理

背景と目的

そこで映像符号化の手順自体を計算機により映像毎

従来、符号化において適応的に最適化される対象とに動的最適構成させることを究極の目的と考え、我々

して、H.264/AVC に代表される映像符号化方式ではは進化的手法、具体的には遺伝的プログラミング

動 き ベ ク ト ル や 予 測 モ ー ド 等 が 、 JPEG-LS や(Genetic Programming, GP)を用いて画像毎に自動CALIC[1]等の可逆画像符号化方式では周辺画素の構成する方法を検討している[2]。

重み係数やコンテクスト分離閾値等がある。従来これら

しかしながら進化計算は、生存選択・世代交代を何動きベクトルや量子化パラメータ等の「符号化パラメー度も繰り返し行い優良個体を得る方法であるため、極タ」は動的に変更され得るものの、「符号化手順」自体めて処理量が大きいという問題があった。

はあくまで固定であった。即ち、新たな符号化手順は人

そこで本プロジェクトでは、大規模 HPC システム間が試行錯誤の末考案するほかなく、故に符号化器のTSUBAME を利用し、進化計算の並列度をより高める

構成は人間の把握しうる程度の複雑さを超えることがことで、どの程度高速化が可能であるかを実験を通しできなかった。また、入力画像に特化した符号化手順をて確認した。その結果、利用コア数にほぼ比例した高(画像カテゴリでなく)画像毎に新規に生成するようなこ速化が実現できることが確認された。とも非現実的であった。

（様式第 20）成果報告書
概要
進化計算をシングルプロセスで行う場合、高速化手段として(GP の)ツリー評価の能率化や高速プロセッサの利用などが考えられるが、期待できる高速化は高々2-3 倍のオーダに留まる。
そこで並列動作向けに進化計算のプログラムフローを変更する。すなわち、共有ファイルに全体最良個体を記録し、母集団が一世代経る毎(10 秒程度)に、そのタイムスタンプを確認し、変化があった場合(他プロセスによる記録更新があった場合。数十回に一回程度の頻度)、自己の最良個体へ取り込みあるいは共有ファイル

図 2.

8bit/pel, gray scale テスト画像 lena.の全体最良個体へ上書きする(サイズは数百バイト程度)。こうして複数プロセス間で全体最良個体が共有さ単 一 プ ロ セ ス に よ る 進 化 は 、 弊 社 の PC(Core2れる。またファイル I/O 負荷は無視できる程度である。

Extreme QX9775 3.2GHz, 4GB Memory, MS

しかる後、図 1 に示すような複数プロセスによる進化

Windows Vista Ultimate 32bit SP1)にて行い、その計算を行う。ファイル共有によるプロセス間通信のため、他(16 並列以上)は全て TSUBAME を利用した。共有ソースコードも実行環境も、OS に依存しない。またプロファイルは/iwork 内に設置した。図 3 に、異なる並列度セス間は非同期に実行できるため、プロセスの途中離における予測器進化計算の性能改善速度を示す。横脱・途中追加が随時可能であり、かつスケーラビリティ

軸は時間、縦軸は予測残差エントロピー (予測器情報が 1～∞となる。またプロセス間の同期をとらないので量も含む画素あたり情報量)である。グラフの水平線は各コアの load は常に 100%となる。

4.407 bit/pel をあらわしている。
図 3 のグラフをみると、並列度が高まるにつれ進化が早まり、より高性能な予測器が得られることがわかる。
う ち 1,568 並列 実 験 に お い ては hpc1(65 ノー ド ),hpc3(33 ノード)を同時使用した。
予測残差エントロピーについて、以前我々が得た値(予測器情報量含む)[1]および高性能可逆符号化器である CALIC[2]の値はそれぞれ 4.482, 4.539 bit/pelであったが、今回 1,568 並列において 4.395 bit/pel の

図 1. 非同期並列進化の実行イメージ(時間は上から下値が得られた。これは[1][2]に対しそれぞれ 1.98%,へ、楕円が母集団、球が個体、赤い球が最優良個体)3.28%の性能改善である。
並列度毎の速度比較を定量的に行うために、予測残結果および考察
今回の実験画像は符号化研究で標準的に用いられている画像の一つ、lena(図 2)である。

差平均情報量が 4.407 bit/pel に達するまでの時間(図3 の水平線と各グラフとの交点)を表 1 に示す。

（様式第 20）成果報告書
4.44

1 core16 cores
80 cores
320 cores
800 cores
1568 cores (hpc1,3)

ra te[ b it / p e l]

4.435
4.434.425
4.424.415
4.414.405
4.44.395
0510152025time [days]

図 3.

並列進化結果。横軸は演算時間、縦軸は総平均情報量。水平実線は 4.407bit/pel

表 1. 4.407 bpp に到達するまでの時間
並列度(コア数)

時間(days)

125.9

16

5.41802.82

3200.79800

0.33

1,5680.129

また、同表における時間の逆数を「進化速度」とみなしてコア数との関係をグラフ化したものを図 4 に示す。

図 4.

コア数と進化速度(特定ビットレートに達する時間の逆数)の関係

コア数にほぼ比例して進化速度が向上することが見て取れる。しかしながら進化計算は多次元探索の一種であり、初期値が異なれば得られる予測器や性能も試行

今後は、より高度な進化手法も併用しつつ、大規毎に異なる、という性質を元来有していることに注意す

模 HPC である TSUBAME の資源を最大限に利用る必要がある(e.g., 図 3 で 16 cores(緑)と 80 cores(青)することで、現状のさらに先に広がる超高圧縮の世のグラフが開始後互いに拮抗しているなど)。

界を垣間見ることを期待したい。

まとめ、今後の課題

参考文献

TSUBAME の利用と処理の並列化による、進化[1] 高村誠之, 松村誠明, 八島由幸: “遺伝的プログ的画像符号化の高速化・高性能化について述べた。

ラミングに基づく画素予測器の生成と評価”, 電子情報実験の結果、本プロジェクトのシステムは計算資源通信学会技術報告, vol. 108, no. 425, IE2008-210,の利用効率が高いこと、2-3 桁の高速化が図れるこ

pp. 37–40, Feb. 2009と、得られる予測器の性能も従来より約 2%高まるこ[2] X. Wu, and N. Memon: “Context-based,となどが明らかとなった。

adaptive, lossless image coding”, IEEE Trans.
Commun., vol. 45, no. 4, pp. 437–444, Apr. 1997