SAI 15 04 horie 20121107 Recent site activity jsaisigsai

(1)

画像による地図の複雑さによるマルチエージェントシミュレー

ションの評価に関する一考察

堀江幸生

^1∗

尾橋大

1

幸塚義之

1

伊藤暢浩

1

岩田員典

2

Horie Sachio

¹

Obasi Dai

¹

Kozuka Yosiyuki

¹

Ito Nobuhiro

¹

Iwata Kazunori

²

1

愛知工業大学大学院経営情報科学研究科

1

Graduate School of Business, Administration and Computer Science, Aichi Institute of

Technology

2

愛知大学経営学部経営学科

2

Faculty of Business Administration, Aichi University

概要: 様々な環境で動作するエージェントを評価するためには，問題となる環境とエージェントの振舞いの間にある関係を明らかにする必要がある．これまでに我々は，地図上の道路ネットワークの構造と建物配置に注目し，問題となる環境（地図）を定量化する方法を提案し，この手法を用いて異なる環境で振舞うエージェントの行動を評価する可能性について検討した．本研究では，これまでの研究成果をもとに，地図上の道路ネットワークの構造と建物配置の情報をより表現できる手法を提案するために地図を画像として捉え，構造的な特徴を抽出する方法を考察する．考察にあたり様々な地図及びエージェントを用いて，その関係性を分析した結果は，従来よりもはっきりと地図とエージェントの振る舞いの間における関係性を示した．

1 _はじめに

近年世界各地で大規模な自然災害による被害が頻繁に発生している．これに対して様々な取り組みが為されている中にRoboCupRescue^{シミュレー} ション（以下_RCRS）がある．このシミュレーションは，被災した都市における様々な種類の災害や災害救助部隊，市民の振る舞いを総合的にマルチエージェントシミュレーションする．この災害シミュレーションの開発を通して，対象となる地域に有効な防災戦略の検討や，また市民に対する防災意識の啓発だけでなく，人工知能，情報処理，ロボティクスなど多くの分野の研究促進が期待されている．

マルチエージェントシステムにおけるエージェントの評価は，エージェントの動作する環境に依存しており，環境を考慮せずにエージェントを評価することはできない．例えば，災害救助エージェントでは，ある地域に有効な防災戦略が他の地域でも有効であるとは限らない．

∗連絡先：愛知工業大学大学院経営情報科学研究科

〒_464-0807名古屋市千種区東山通_1-38-1 E-mail: [email protected]

エージェント間の関係，環境との相互作用を明らかにするためのアプローチとして，以下の ₂つがある．

1. エージェントを固定し環境を変える． 2. 環境を固定しエージェントを変える．

本研究は，前者（環境すなわち地図）について考察する．我々は，このシミュレーションを用いて，予め与えられた都市の地図情報を解析することによって，様々な実験を行った結果，エージェントにとって地図上を移動する能力は，最も根本的で重要な能力であり，この能力と密接に関係している地図情報の構成要素が道路網と建造物であると考えた解析をおこなっている[8][21][24][26]^．

2 過去の研究について

これまで地図構造について考察した研究は，地図の中でも道路に関する情報に着目した瀬戸口らの研究がある．彼らは，道路網の特徴のことを「道路ネットワークの複雑さ」と呼び定義を行った．そ

(2)

のうえで，道路ネットワークの複雑さと移動型エージェントシミュレーションとの依存関係について考察した．また，道路だけでなく建物の情報にも着目した纐纈らの建物および道路とエージェントの評価に関する考察もある．

地図構造について上記とは別の観点からなる研究として，_{M. Rosvall}らの地図上の移動において，どれだけの情報が必要であるかを定量化した，「平均探索情報量」_[40][41]についての研究がある．これらは，道路網（建物情報も含む）をグラフとしてとらえて，道路網のネットワーク構造に着目した研究である．

また，纐纈らの研究結果から，鈴木らの地図情報による災害救助エージェントの活動予測の検討についての研究_[32]や，福田らの十分に予測をおこなえている地図とあまり十分に予測をおこなえていない地図を分類し，活動予測が改良できるか否かについての研究_[33]もおこなわれている．

3 画像処理によるデータ抽出方法

我々は，地図構造を考察するにあたり，主に道路網（建物情報も含む）をグラフとしてとらえて，道路網のネットワーク構造に着目した研究を行ってきたが，当初推測していたエージェントと地図

（環境）との相関が必ずしも有意ではなかった．そこで本研究では，地図を画像として捉え，構造的な特徴を抽出する方法を提案する．

地図を画像として扱うには，画像の特徴量を求める必要がある．

特徴量とは，画像の特徴を数値として表現したものである．特徴量を複数用いることも可能であるが，画像の特徴量には大きく分けて，「色特徴」，

「テクスチャ（画像がもつパターンの規則性，方向性などを表す数値）」，「（物体の）形状」といった₃ 種類があるが，_RCRSの地図は，多様な色彩を用いない，建物などでも物体という意味での形状情報が多くないので特徴量として，「テクスチャ」を考える．

物体表面の物理的様子，規則的な濃淡変化が表す模様のことをテクスチャと呼ぶ．テクスチャにもとづいて対象物を認識したり，遠近感などを得たりする．その際、テクスチャを特徴づける何らかの数量化が必要となる．これを，テクスチャ特徴とよぶ．テクスチャ特徴は，（濃淡ヒストグラム，フーリエパワースペクトル，ランレングス行列、同時生起行列などを計測して得られる）統計的特徴と，構造的特徴（形状的特徴量）に分けられる．

本研究では当初，与えられた領域がすべて均一なテクスチャ（地図を構成する要素として常識的な要素）で構成されていると仮定して，地図画像のテクスチャ特徴としてはじめに構造的特徴に焦点をあてた．

構造的特徴とは，画像の中から直線や点などの，テクスチャを構成する基本的な構成要素を抽出し，それらの配列規則を特徴として求める方法である．抽出できる要素の種類は，手法によって異なるが非常に少ない．したがって，航空写真やリモートセンシング画像における道路や建物物など，ターゲットとして抽出する構成要素が明確な人工のテクスチャに有効であるとされている．

しかしながら，次章で説明するように，本研究では，画素の濃度に着目して，その一様性，方向性，コントラスト変化などの画像の性質を表す統計量的特徴を採用することとしてテクスチャーの特徴量に，より一般的な濃度ヒストグラムによる特徴量を採用した．すなわち，平均（濃淡レベルの平均を表す），分散（平均値から離れた画素が多く存在すれば大きな値をとる），歪度

1

（濃度ヒストグラムの対称性形状特長），尖度

2

（濃度ヒストグラムの分布形状特徴）を計算する．

3.1 地図を扱うこと：解析例と考え方

本研究では当初，地図画像のテクスチャ分析をウェーブレット変換による特徴量で研究を進めたが，分析過程で不具合が生じ，濃度ヒストグラムによる特徴量により分析を行うこととした．

ウェーブレット変換で，不具合が生じた理由を考察したので以下で説明する．

テクスチャとは，前節で説明したように画像処理の分野では，一般に「模様」のことで，エッジは「輪郭」のことであるが，「模様」を構成する要素をここでは「輪郭」と言う．

ウェーブレット変換では画像分解するにあたり，低周波成分（模様）を除去する（任意のレベルで低周波でもレベルの深さで高周波とみなせる）ことで，高周波成分（輪郭）が得られる（自然画像は近隣の画素間に大きな変化があった場合，その変化は高周波成分に強く表れるため，多重解像度解析によりエッジ検出がされる）が，この高周波成分は，レベルごとの分析画像で相関が非常に強

1

歪度は濃度ヒストグラムの形状が対称な形からどれだけずれているかを表す．

2

尖度は濃度ヒストグラムの分布がどれだけ平均値の回りに集中しているかを表す．

(3)

いので，類似する輪郭を持つような画像を分類するには，ウェーブレット解析は優れており_[28]，地図画像の分類には有効でも回帰分析には不向きであった．

そこで，地図の構造物分布を分類に関わる分析も含め，さらに回帰的に調査することも可能にするには，輪郭を説明変数にするよりも，濃度ヒストグラムの特徴量を説明変数にすることとした．

4 ロボカップレスキューシミュレー

ション（ RCRS ）

マルチエージェントシミュレーションとは，能動的に行動するエージェントを含むシステムの挙動を調べるため，エージェントの行動規範およびエージェント間や環境との相互作用を規定してシミュレーションを行い，解析する手法のことである．ロボカップレスキューシミュレーションシステムは，地震による火災，市民の埋没，道路閉塞や渋滞などが発生する災害空間を分散計算機上に実現し，その仮想的な災害空間の中で，エージェントが防災・救命救助活動を行う．その試行は，より現実に近い物理現象の計算方法やエージェントがどのように意志決定をして行動すべきなのかを研究・評価することができる．

本研究の目標は，マルチエージェントシステムの評価を可能にする手法の提案であるが，昨今の状況から災害救助の観点も重要だと考え，マルチエージェントシステムとして_RCRSを採用した．

4.1 RCRS における評価

RCRSにおける評価とは，災害救助エージェントによる災害救助活動により，震災時における都市の被害をどの程度抑えることができたかを評価することである．_RCRSの競技会では，最終都市価値と呼ぶ評価値により評価する．

災害救助エージェントの能力を評価するときに基準となるものは，以下のような項目が考えられる．

• 救助することができた市民の数

• 延焼を防いだ建築物や家屋

この中でも，救助することができた市民の数は，災害による被害を抑えるにあたり，重要な要因である．

ここで，RoboCupRescue^{シミュレーションの競} 技会では，以下に示す計算式より求められる値V を用いて災害救助エージェントによる災害救助活動を評価する．

V ₌ (

P₊ ^S S_int

) √ _B

B_int ⁽¹⁾

P _: 生存している市民，災害救助エージェントの数

S _: 全ての市民，災害救助エージェントの残りの体力の合計

Sint _: 初期状態の全ての市民，災害救助エージェントの体力の合計

B _: 燃え残った建物の面積

B_int _: 初期状態における全ての建物の面積

式（₁）からわかるように，V の値は前述した救助することができた市民の数，延焼を防いだ建築物や家屋と，密接な関係がある．このV の値を都市価値と呼ぶ．

シミュレーションの進行にともない，各エージェントの体力は減り，消火が間に合わない場合建物は延焼する．そのため，シミュレーションが進むにつれて都市価値は減点されていく．そしてシミュレーションが終了したときの最終都市価値Vendが，最終的な災害救助活動の評価となり，この値が大きいほど災害救助活動が優れていることになる．しかし最終都市価値は，地図データ上に存在するエージェント数により，値が大きく異なる．そのため，最終都市価値により，異なる地図データにおけるエージェントの評価を比較することはできない．そこで我々は，シミュレーション開始時の都市価値に対するシミュレーション終了後の都市価値の割合を，都市価値維持率として定義する．シミュレーション開始時の都市価値をV_ini，シミュレーション終了後の都市価値をV_end とするとき，都市価値維持率Vrateは次式で数値化される．

Vrate ₌

V_end Vini

(2)

なお，都市価値維持率と，地図上の各部分に統計値を割り当てる作業において，使用する集計単位地区が変わることで，データの見え方や分析の結果が変わってしまうことがある可変単位地区問題については，_RCRSの地図が，シミュレーションに必要となる地図を切り出していることより考慮しない．

(4)

5 分析

本研究でははじめに，特徴量としての濃度ヒストグラムの有効性を検証するために，主成分分析，クラスタ分析を行い，その結果をうけて回帰分析を行った．

5.1 主成分分析

主成分分析を用いて，算出した特徴量の有効性を検討した．主成分分析による，第₁∼₂主成分の累積寄与率は，地図画像に濃度ヒストグラムによる分析を用いた場合，_95%を越えた．

主成分分析を行う際に，解析対象とする主成分を見極める考え方として，以下がある．

1. ^固定値が1 以上の成分を解析対象にする． 2. 寄与率から上下で差のあるところまでを解

析対象とする．

3. ^{累積寄与率}80％を超えたところを解析対象とする．

これより，本解析の主成分でデータが分類可能であると考える．横軸，縦軸をそれぞれ第₁主成分得点，第₂主成分得点として地図をプロットしたものが，図₁である．

図_1: 地図画像の主成分分析

図₁を見るとデータはよく散らばっているが，地図をテクスチャとして考えた場合，テクスチャとして密な地図と粗な地図はきれいに分かれている．また，₁₎ 第 ₂ 主成分得点が小さいほど，テクスチャとして密な地図が多く分布する．逆に第₂ 主成分得点が大きいほど，疎な地図が多く分布する．このことから，特徴量による第₂ 主成分得点は，テクスチャの密度を区別する性能があることが観

察できる．また，₂₎ 第 ₁ 主成分得点が大きいほど，テクスチャに格子のような規則性がある．

なお，主成分を求める際，単位が違う変数が混ざっていて，かつ，各変数が含む誤差の分散が同じであるような場合に適する相関係数行列から主成分を求める方法と，単位が違う変数が混ざっていない場合に適する分散共分散行列から主成分を求める方法とがある．今回は，一般的な場合と考え，前者の手法とした．

5.2 クラスタ分析

主成分分析により特徴量の有効性が確認できたので，ここでは特徴量により地図がどのようにクラスタリングされるかを見るためにユークリッド距離によるウォード法を用いたクラスタ分析を行った．

上記特徴量によるクラスタ分析の結果を図₂に示す．

図 _2: 地図画像のクラスタ分析

これより，次の₄つに分類されると考えられる．

• ^{全体的に疎}

• ^{全体的にやや疎}

• ^{全体的にやや密}

• ^{全体的に密}

以上より特徴量は，構造的

3/^統計的⁴^{テクスチャ} を併せて分類できると考えられる．したがって，これまでの結果に基づき，都市価値維持率と濃度ヒストグラムの間の相関関係について回帰分析を行い，その優位性を検証する．

3

規則的な構造を持っている．

4

規則的な構造を持たない．

(5)

5.3 回帰分析：地図画像における構造物の分

布を分析すること

5.3.1 RCRS の地図画像

上記の結果を踏まえて，地図における画像の特徴を説明変数とし，目的変数を都市価値維持率として回帰分析をおこなった．結果を図??に示す．結果は，多重共線性，系列相関も考慮している．

図_3: 地図画像の回帰分析

各説明変数それぞれの_P-値より，分散と歪度が 1%水準で有意であり，平均は_5%水準で有意ではない．これより，平均は都市価値維持率を変化させる要因とは言えないことを示し，また，分散と歪度の偏回帰係数は負なので，両者が小さければ小さいほど都市価値維持率が高いということになる

5

．

以上の結果より都市価値維持率は濃度ヒストグラムの分散と歪度から予測可能だと考える．すなわち地図画像では，際立った濃度変化のない場合にに都市価値維持率は高いと考えられる．

5.3.2 航空写真

RCRSによる結果を踏まえて，航空写真_[31]による分析も試行することとしたが，画像解像度の領域内における変化，雲や霧の影響などで，信頼できる航空写真は₆ 都市となった

6

．

なおここで，地図画像（図．₄）と航空写真（図． 5^{）の一例を示す．}

航空写真の分析も，_RCRSとまったく同様な工程で，₁₎主成分分析，₂₎クラスタ分析，₃₎回帰分析をおこなった．₁₎では，第₁∼₂主成分の累積寄与率は，_86.1%であった．なお各成分は「模様の

5

ここではテクスチャ解析で得られた解析値である説明変数には内生性がないとしている．

6RCRSの地図画像とマッチングするにあたり，航空写真の縮尺，大きさには若干の違いが生じている．

図_4: 名古屋市西区

図_5: 名古屋市西区

(6)

規則性（縦軸）」と「航空写真全体の濃さ（横軸）」を表していた．

図_6: 航空写真の主成分分析 2)では，分散の大小と言う分類ができた．

図_7: 航空写真のクラスタ分析 3)^{は，以下で示す．}

図_8: 航空写真の回帰分析

結果は，都市価値維持率は，航空写真における濃度ヒストグラムの分散が大きければ大きいほど高いと言える．地図画像と異なり航空写真では，濃度に大きく変化がある場合に都市価値維持率が高いと考えられる．

6 結果

これまでの分析による結果は，濃度ヒストグラムと都市価値維持率の相関の有意性について示すことができた．

地図画像においては濃度変化が穏やかであるある場合に都市価値維持率が高かった．これは，_RCRS の地図画像が，建物，道路，土地など，同種の存在が同色で表示されるので，都市構造が複雑または，単純であればあるほど都市価値維持率が高いことを表している．

また，航空写真においては濃度変化が激しいほど都市価値維持率が高かった．これは，都市構造が複雑であればあるほど都市価値維持率が高いことを表しているが，航空写真では写真データの不足で，大都市の写真が多いことより更なる検証が必要である．

これまでの結果を考えると，都市構造が複雑（地図画像だけでは単純も含む）である場合に，都市価値維持率が高いと説明できる．現在の日本における都市は，城下町をはじめとした近世以前に発達したが，それは時代により大きく変化してきた．例えば戦国時代には，軍事的な理由により道路を意図的に折り曲げ，容易に直進ができないような複雑な道路網が形成されるということが見られる．また近代化が進むにつれて，都市は，効率的・合理的に形成された．このような過程を経て，ここでは人工的な都市は災害が起こった場合に，災害を回避しやすいと考える．

7 _{結論と課題}

本研究では，マルチエージェントシステムの評価手法を提案するために，地図画像と航空写真を濃度ヒストグラムという特徴量より解析した．

これまでも地図の複雑さがエージェントに及ぼす影響は，概ね示されてきたが，本研究でも，それを裏付けるように地図の複雑さとエージェントの活動との関係性は明確であることがわかった．そこでは，例えば本研究におけるエージェントの活動は，都市構造が複雑である場合に有効であるというようなマルチエージェントシステムの評価を可能にした．

さらに，本研究のエージェントの活動は，_RCRS がシミュレーションであり現実ではないが，本研究で試用されたシステム仕様の範囲内で，例えば災害時における都市の変容の仕方を予測できたように，限られた現実データ，例えば，航空写真などから，現実における都市の変容を予測できる可能性も示した．

今後の課題は，より多くの画像データを分析し，本研究を応用したネットワークの形状分析を試行することだと考える．

(7)

8 謝辞

本稿の一部は愛知大学研究助成（_C−₁₆₈）「災害救助エージェントシミュレーションにおける地図の定量化・分類と救助戦略の関連性」（₂₀₁₂年度）の成果である．

参考文献

[1] 道路地図複雑さ数値化法における可変単位地区問題，倉本亮介_,修士論文，_2011-03-25 [2] 空間統計モデルにおける可変単位地区問題，塚

井誠人・茅原周平・奥村誠，₂₀₀₉年第₂₃回応用地域学会山形大会発表原稿（2009.12.11) [3] GIS^{の新たな可能性，}SJRM^{リスクレビュー，}

小林優介，損保ジャパンリスクマネジメント， 2009

[4] 道路網のフラクタル次元に関する基礎研究，和栗健・前田義信・牧野秀夫，平成 ₁₇ 年度電子情報通信学会信越支部大会講演論文集 [5] 2008年度「フラクタル解析と重回帰分析を用いた道路ネットワークのイメージ研究」，前田研究室

[6] 複雑ネットワークの統計的性質，矢久保考介，大学院共通授業科目「トポロジー理工学特別講義Ｉ」

[7] パターン情報処理，前川，埼玉大学講義 [8] 建物および道路の散らばりを考慮した地図構

造の複雑さについて，園田純，愛知工業大学大学院経営情報科学研究科修士論文，₂₀₁₂ [9] 施設分布密度の計量方法に関する研究，磯谷

直昭，伊藤恭行，久野紀光，学術講演梗概集_{. F-1,} 都市計画_,建築経済・住宅問題_2009, 567-568, 2009-07-20

[10] 画像類似度に関する研究，浅山研究室，松若光一，榎本拓郎，鴉裕孝，岡山理科大学 [11] テクスチャ解析，計測自動制御学会，

http://www.sice.jp/handbook/

[12] 輪郭線情報とテクスチャ情報の統合による画像識別に関する研究，矢野啓司，九州大学博士論文，₁₉₉₈

[13] ウェーブレット変換を用いたテクスチャ特徴量，中田雄一郎，小早川倫広，星守，大森匡，電気通信大学大学院情報システム学研究学科，電子情報通信学会技術研究報告_{. PRMU,} パターン認識・メディア理解96(563), 45-52, 1997-03-06

[14] テクスチャ解析を用いた_QuickBird画像の土地被覆分類の可能性，大久保悟，東京大学大学院農学生命科学研究科_,2009

[15] ^非分離型2次元ロスレスウェーブレット変換 (高精細画像の処理・表示_,及び一般₎，小松邦紀，瀬崎薫，電子情報通信学会技術研究報告_. IE,^画像工学103(450), 29-34, 2003-11-13 [16] 液状化のハザードマップにおける作成方法の

現状と問題点，安田進，石田栄介，細川直行，東京電機大学理工学部，第₃₀ 回土木学会地震工学研究発表会論文集

[17] 画像処理とパターン認識入門 _- 基礎から

VCS/VC++ .NETによるプロジェクト作成

まで，酒井幸市，森北出版

[18] ^画 ^像 ^圧 ^縮 ^ア ^ル ^ゴ ^リ ^ズ ^ム ^，

http://fussy.web.fc2.com/algo/algo8-9.htm [19] エッジ検出とは，木村聡，神奈川工科大学，

http://www.f-kmr.com/dsp edge.htm^， [20] ウェーブレット変換による文学作品解析に関

する研究，井波真弓，法政大学，斉藤研究室 [21] 平均探索情報量とマルチエージェントシミュレーションとの関連性についての考察，堀江幸生，伊藤暢浩，幸塚義之，園田純，人工知能学会「社会における _AI研究会」第₁₁回研究会

[22] 公開地図データにおける建物領域の自動生成とその評価，高橋寛典，高橋友一，_{The 19th} Annual Conference of the Japanese Society for Artificial Intelligence, 2005

[23] ^パ ^タ ^ー ^ン ^情 ^報 ^処 ^理 (^前 ^川)^， http://www.cda.ics.saitama-

u.ac.jp/ maekawa/lect/pat/y10-5.pdf [24] 道路ネットワークの複雑さとマルチエージェ

ントシステムに関する研究，名古屋工業大学大学院情報工学専攻金田洋平，平成₁₇年度修士論文

(8)

[25] 画像処理工学，村上伸一，電機大出版局 [26] 道路ネットワークの複雑さと移動型エージェ

ントシミュレーションとの依存関係について，名古屋工業大学大学院情報工学専攻瀬戸口陽一，平成₁₉年度修士論文

[27] ブロックの分散・平均値を用いた画像電子透かし，桃井秀人，中村栄治，沢田克敏，愛知工業大学研究報告第₄₀ 号_B平成₁₇ 年 [28] ^{久ウェーブレットと}SOM^{を用いたエッジ特徴}

による類似画像検索システムの開発_,保正明，ザヘルアグバリ，牧之内顕文_,第₁₃回データ工学ワークショップ (DEWS 2002) B1-3, 2002.3

[29] http://blog.livedoor.jp/yoh smallwoods/archives/2007- 03.html

[30] 重み付けられた複雑ネットワークにおける一般化された強度，古谷修平，矢久保考介，日本物理学会講演概要集，日本物理学会講演概要集 62(1-2), 297, 2007-02-28

[31] Yahoo^地図

[32] 地図情報による災害救助エージェントの活動予測の検討，鈴木俊人，名古屋工業大学平成 19^{年度卒業論文}

[33] 地図の特徴とエージェントの評価との関係における地図の分類について，福田佑地，名古屋工業大学大学院情報工学専攻，平成₂₁年度修士論文．

[34] 隠れたトレンドを探る：多変量解析，

http://www5.ocn.ne.jp/˜shinya91/csm/331csm multi.html [35] EasyPCA^，http://hoxom-

hist.appspot.com/pca.html

[36] RoboCupRescueシミュレーションにおける道路ネットワークの複雑さについて，瀬戸口陽一，名古屋工業大学平成₁₇年度卒業論文 [37] Image Data base^{の指針，久保正明}

[38] 日本都市道路ネットワークの複雑さの変化に関する研究―経路探索に必要な情報量を用いて―，高翰元，九州大学，₂₀₁₀

[39] 輪郭線情報とテクスチャ情報の統合による画像識別に関する研究，矢野啓司，九州大学， 1998^{年度博士論文}

[40] M. Rosvall, A. Trusina, P. Minnhagen, and K. Sneppen, Phys.Rev. Lett. 94, 028701 (2005)

[41] 神川豪，豊木博泰，都市道路ネットワークの複雑さの定量化，山梨大学平成₁₈年度卒業論文，₂₀₀₆