（様式第 20）成果報告書

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

進化的映像符号化の高度並列シミュレーション
Highly Parallelized Simulation of Evolutive Image Coding
高村誠之
Seishi Takamura
日本電信電話株式会社 NTT サイバースペース研究所
NTT Cyber Space Laboratories, NTT Corporation
http://www.ntt.co.jp
邦文抄録 遺伝的プログラミング(Genetic Programming, GP)に基づいた進化的手法による動的なアルゴリズム生成は、プラント制御、ロボット制御、株価予測など多くの分野に応用されている。一方、 JPEG や
MPEG-2, MPEG-4, AVC/H.264 等の従来の画像・映像符号化アルゴリズムは例外なく固定的な(動的でない)ものであった。この制約を突破することを目標とし、GP を画像ごとに個別に用い画素値予測アルゴリズムを生成する試みがなされ、一定の成功を収めている。しかしながらその課題の一つが演算量の膨大さであった。本報告では GP に基づく画像特化型符号化アルゴリズム生成システムと、並列計算との整合性の高さを述べ、TSUBAME2.0 を用いた大規模並列計算システムで実行し、実際得られた高速化効果について述べる。
英文抄録 Evolutionary methods based on genetic programming (GP) enable dynamic algorithm
generation, and have been successfully applied to many areas such as plant control, robot control,and stock market prediction. On the other hand, conventional image/video coding methods such as
JPEG, MPEG-2, MPEG-4 and AVC/H.264 all use fixed (non-dynamic) algorithms without exception.
To relax this limitation, GP has been successfully applied to dynamic generation of pixel prediction
algorithm. However, one of the challenges of this approach is its high computational complexity. In
this article, we introduce a GP-based image predictor that is specifically evolved for each input
image, its good match with parallel computing, and some of speeding-up approaches, which includes
the use of massively parallel computation such as TSUBAME2.0 and GPGPU

Keywords: Genetic programming, Evolutive image/video coding, Parallel computing

1. 背景と目的ルゴリズムを自動構成する方法を検討している[2]。

従来、符号化において適応的に最適化される対象としかしながら進化計算は、生存選択・世代交代を何して、JPEG, JPEG-LS 等の可逆画像符号化方式では度も繰り返し行い優良個体を得る方法であるため、極周辺画素の重み係数やコンテクスト分離閾値等がある。

めて処理量が大きいという問題があり、その高速化も従来これらの「符号化パラメータ」は動的に変更され得検討されている[3-5]。

るものの、「符号化手順」自体はあくまで固定であった。

本課題では、大規模 HPC システム TSUBAME2.0

即ち、新たな符号化手順は人間が試行錯誤の末考案を利用し、進化計算の並列度をより高めることで、どのするほかなく、故に符号化器の構成は人間の把握しう程度高速化が可能であるかを実験する。結果、2,400る程度の複雑さを超えることができなかった。また、入並列まで、並列度にほぼ比例した高速化が実現できる

力画像に特化した符号化手順を(画像カテゴリでなく)画ことを確認した。

像毎に新規に生成するようなことも非現実的であった。
そこで映像符号化の手順自体を計算機により映像毎2. 概要に動的構成させることを目的とし、進化的手法(遺伝的遺伝的プログラミング[3]により、予測器を自動構築すプログラミング, GP[1])を用いて画像毎に画素予測アる方法を述べる。まず内部的に、演算や条件分岐を行う

（様式第 20）成果報告書「枝ノード」および画素値や定数などの値を持つ「葉ノー行できるため、プロセスの途中離脱・途中追加が随時ド」から構成される「木」として予測器を表現する。そして可能であり、かつスケーラビリティが 1～∞となる。また

進化的手法(突然変異、木同士の交叉)により優秀な木プロセス間の同期をとらないため各コアの load は常に(優れた圧縮性能を持つ予測器)が母集団に残るよう、100%となる。

評価・取捨選択を繰り返す。

2.1

3. 結果及び考察

予測器の構成要素

図 2,3 に、異なる並列度における予測器進化計算の枝ノードとしては、三角関数、加減乗除、冪関数、最大最小、平均、指数関数、対数、双曲線関数などを、葉ノードとしては、定数値や周辺の既知の画素値などを用いる。

性能改善速度を示す。横軸は時間、縦軸は予測残差
エントロピー (予測器情報量も含む画素あたり情報量)である。図 3 は、図 2 の先頭一時間を拡大したものである。グラフをみると、並列度が高まるにつれ進化が早まり、より高性能な予測器が得られることがわかる。

2.2 予測器の評価規準

並列度毎の速度比較を定量的に行うために、予測残は、その予測器を入力画像に施した後の原画との残差

差平均情報量が 4.407 bit/pel に達するまでの時間(図情 報 量 (IR [bits]) だ け で な く 、 木 自 体 の 情 報 量 (IT3 の水平線と各グラフとの交点)を表 1 に示す。

[bits])も考慮し、IT + IRとする。

Total Information [bits/pel]

可逆符号化における木(予測器)の優劣の判断において2.3 並列計算環境での進化計算個体を生成し評価する、という進化計算のプロセス

4.46

1 core16 cores
80 cores
320 cores
800 cores
1,568 cores
2,400 cores

4.45
4.444.434.424.41は、並列化に非常に向いている。並列動作を志向した
0Total Information [bits/pel]

進化計算の動作フローは図 1 のようになる。

244.461214161 core
16 cores
80 cores
320 cores
800 cores
1,568 cores
2,400 cores

4.454.44

4.42へ、楕円が母集団、球が個体、赤い球が最優良個体)

810Time [h]図 2 並列度ごとの符号量の時間変化の比較

4.43

図 1. 非同期並列進化の実行イメージ(時間は上から下64.41
00.20.40.6Time [h]0.81

図 3 並列度ごとの符号量の時間変化の比較(図 2共有ファイルに全体最良個体を記録し、母集団が一世の先頭一時間を拡大)

代経る毎(10 秒程度)に、そのタイムスタンプを確認し、変化があった場合(他プロセスによる記録更新があった場合。数十回に一回程度の頻度)、自己の最良個体へ取り込みあるいは共有ファイルの全体最良個体へ上書きする(サイズは数百バイト程度)。こうして複数プロセス間で全体最良個体が共有される。またファイル I/O 負荷は無視できる程度である。プロセス間は非同期に実進化速度を定量化するために、総符号量が 4.407bits/pel に到達するまでの所要時間を表 1 に示す。
右の列がシングルコアに対する速度向上度である。
コア数と速度向上度の関係を図 4 に示す。両者の間には定常的に線形な関係(コア数の約 1/2 ほど)が観（様式第 20）成果報告書
GPU による高速化の試み～」, AVM 研究会 招待

察され、並列化の効果が確認された。

講演, Sep. 2010
表 1 並列度毎の、4.407bits/pel に到達するまでのPCS2010 Tutorial Talk Dec. 2010

所要計算時間と速度向上度#cores11680320800
1,5682,400Time(hours)2075.3129.767.7819.02
7.98
3.10
1.80

速度向上度
(1 コア比)
116.0
30.6
109.1
260.1
669.4
1152.9[5] 高村: 解説記事「次世代映像符号化標準・次々世代映像符号化技術の動向」, 電子情報通信学会
誌 Sep. 2011

図 4 コア数と速度向上度(1 コア比)の関係
4. まとめ、今後の課題
TSUBAME2.0 の利用と処理の並列化による、進化的画像符号化の高速化・高性能化について述べた。
実験の結果、2-3 桁(最大 1,153 倍)の高速化が図れた。今後は、より効率的な進化手法・世代交代に関する考慮、並列化以外の高速化、特に線形オーダ以上のアルゴリズムの開発を行う予定である。
文
[1]

J.

Koza:

献

“GeneticProgramming[4] S. Takamura: "Evolutive Video Coding “ ,II,Automatic Discovery of Reusable Programs”,
The MIT Press, 1998
[2] 高村誠之, 松村誠明, 八島由幸: “遺伝的プログラミングに基づく画素予測器の生成と評価”, 電子
情 報 通 信 学 会 技 術 報 告 , vol. 108, no. 425,
IE2008-210, pp. 37–40, Feb. 2009[3] 高村:「進化的画像符号化の展望 ～スパコン・