![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
自律走行ロボットとは人間が操作するのではなく，ロボット自身が考えて走行するロボットである．ロボットに経路を与え，その経路上で自律走行を行いながら目的地を目指す．ロボットが正しく走行するためには，自分が経路上のどこにいるか把握する，自己位置推定が必要となる．
ロボットに必要な自己位置推定は，一般的にレーザーレンジファインダを使用する方法が多く用いられている． この方法では空間の3次元情報を取得することで高精度の自己位置推定を行うことができる． それに対して本研究ではカメラ画像を用いた画像処理で自己位置推定を行うことを目的としている．人間が自己位置推定を行う場合，目で周囲の風景を見て自分がどこにいるかを判断することができる．それと同じことをロボットにさせようとしている．
具体的には以下の方法で自己位置推定を行う．
ここで目印として選んだ画像を探す際にはテンプレートマッチングを使用する．テンプレートマッチングとは，探索対象画像の中から，テンプレートと呼ばれる特定の画像を探し出す方法である．
本研究で扱うロボットは基本的に屋外を走行することを想定している．屋外環境下でテンプレートマッチングを行う場合，大きく3つの問題点がある．1つ目は日時や天候の変化による照明条件の変化である．左と真ん中の画像は同じ位置から撮影された画像であるが，明るさが違っているのがわかる．テンプレートマッチングには一様な明るさの変化に対応した正規化相互相関マッチングという手法があるが，屋外環境の明るさの変化は一様ではなく局所的であることが多いため正規化相互相関マッチングで対応することは難しい．
2つ目の問題点は人や車などの障害物による遮蔽である．先ほどの画像で左の画像では写っていなかった車が真ん中の画像では写っていしまっている．これは言うまでもなく誤認識原因となる．
3つ目は撮影地点の変化という問題である．ロボットが自律走行を行う際，身印となる画像を撮影した経路と全く同じ経路を走行することは非常に難しい．右の画像は真ん中の画像を撮影した地点から少しずれた位置で撮影した画像であるが，このような少しの変化でも誤認識の原因となることがある．
この3つの問題点のうち，照明条件の変化，遮蔽に対応したAccumulated Block Matchという手法が既に提案されている．
既存手法であるAccumulated Block Matchはテンプレートマッチングを行う際，テンプレート画像を図のように複数のブロック領域に分割して照合を行う手法である．ここでは探索対象画像上の点(x,y)での照合を例に説明する．テンプレートを複数のブロック領域に分割し，分割した各ブロックをテンプレートとしてブロックの左上，図の赤い点の位置で正規化相互を相関マッチングを行う．全てのブロックでマッチングを行い，その平均を点(x,y)のスコアとする．これを探索対象画像上の全ての点で行い，最も良い点をマッチング位置とする．
画像に影等が写り，局所的な明るさの変化が起こった場合，障害物による遮蔽が起こった場合を考える．テンプレートを複数のブロック領域に分割することで影の部分は，各ブロック内では一様な濃度変化とすることができる．また遮蔽は障害物が写っている部分とそうでない部分に分けることができ，全てのブロックの平均を取ることで障害物の影響を少なくすることができる．よって既存手法は照明条件の変化，遮蔽に強いマッチングを行うことができる．
しかし既存手法は，屋外環境でテンプレートマッチングを行う際の3つ目の問題点である，撮影地点の変化には対応していない．そこで撮影地点の変化に対応したFlexible Sub-window Matchingという手法を提案する．
提案手法は既存手法を改良した手法である． ここでも探索対象画像上の点(x,y)での照合を例に説明する． まず既存手法と同様にテンプレート画像を複数のブロック領域に分割する．提案手法でもこの分割したブロックをテンプレートとしてマッチングを行う．既存手法の場合，各ブロックはブロックの左上の1点のみでマッチングを行っていたが，提案手法では各ブロックを独立に動かして近傍を探索する．ここが既存手法との最大の違いとなる．近傍とは4ブロック分で図のブロックAの場合，水色の部分が探索範囲となる．この水色の範囲内でブロックAをテンプレートとし，正規化相互相関マッチングを行う．そして最も良いスコアをブロックAのスコアとする．これを全てのブロックで行い，その平均を点(x,y)のスコアとする．これを探索対象画像上の全ての点で行い，最も良いスコアの点をマッチング位置とする．
テンプレートを複数のブロック領域に分割することは既存手法と同様のため，既存手法の照明条件の変化，遮蔽に強いという特徴は受け継いでいる．各ブロックを独立に動かして近傍を探索し，適切な照合位置を求めることで，撮影地点の変化を吸収することができる．しかし，それに伴い計算コストの増大という新たな問題が発生してしまった． 何も工夫をせず，探索対象画像からブロックの探索範囲を切り取り正規化相互マッチングを行う場合，画像1枚の照合に20分以上かかってしまう．そこで実用的な速度でマッチングが行えるよう2種類の高速化手法を考案した．
定点カメラを用いて同じ場所から撮影した画像を100枚用意する．この画像は異なる日付，時間に撮影したもので明るさの変化大きいものである．
その100枚の画像の中から1枚の画像を選び，その画像から窓枠やアンテナ，木などの5種類のテンプレートを作成する．
100枚の画像および作成したテンプレートをグレー画像，エッジ画像，2値エッジ画像の3種類の画像にする処理を施した後，グレー画像ならばグレーのテンプレート，エッジ画像ならエッジのテンプレートのように，それぞれ対応する画像とテンプレートでテンプレートマッチングを行う．
そのときの類似度の計算方法にはSSD,NCC,ZNCCの3種類を使う．それぞれ正しくマッチングした数を数え，比較する.実験に使用した画像の例を以下に示す．
#ref(): File not found: "gazo4shu.jpg" at page "自律走行ロボットのための撮影位置の変化に堅牢な画像照合手法"
撮影した画像から以下の画像の赤枠のように5つのテンプレートを作成した．
#ref(): File not found: "kak.jpg" at page "自律走行ロボットのための撮影位置の変化に堅牢な画像照合手法"
#ref(): File not found: "temps.png" at page "自律走行ロボットのための撮影位置の変化に堅牢な画像照合手法"
実験1で正しくマッチングした時の画像の類似度の平均を計算する．
100枚の固定カメラから撮影した画像とはまったく関係のない風景画像50枚を用意し，その50枚の画像に対して実験1で作成したテンプレートを使い，実験1と同様にテンプレートマッチングを行う．
その時，最大マッチングとされた点の類似度の平均を計算する．2つの類似度の平均値の差を計算し，比較する．
実験1では対象物(テンプレート)が写っている画像のみを対象に実験を行った．しかし，自律走行ロボットが実際に屋外を走行し，テンプレートマッチングを行う際，対象物が写ってない場合も当然考えられる．そのような場合，ロボットは対象物は写っていないと判断しなければならない．そのため計算した類似度に対し，対象物かどうかを判断するための閾値を決める必要がある．テンプレートマッチングでは，非対称画像とテンプレートが最も似ている場所を求めることができるため，対象物が写っていない場合でも，最も似ている点を取得できる．その値は対象物が写っていて，正しくマッチングされたものよりも低くなるはずである．対象物がある画像で正しくマッチングしたときの類似度と，対象物が写っていないときの最大マッチングとされた場所の類似度の差が，大きければ大きいほど閾値の決定が容易になり，誤検出も少なくできると考えられる．そのため，2つの差が大きいものを良いマッチング方法とする．
| グレー画像 | エッジ画像 | 2値エッジ画像 | |
| SSD | 35 | 99 | 97 |
| NCC | 58 | 94 | 86 |
| ZNCC | 86 | 96 | 89 |
テンプレート１ではエッジ画像でSSDを使った場合の正解数が99と最も多くなった．エッジ画像で他の計算方法を使った場合も成功率が９割以上である．グレー画像の場合，ZNCCを以外の計算方法だと成功率が低い．ZNCCでは正解数86と悪くはない結果となったが，窓枠が光っているときは失敗することが多かった．エッジ画像でZNCCを用いた時の失敗も窓枠が光っている画像であったが，グレー画像で失敗するときは窓枠とは全く関係のない場所を最大マッチングとしていたのに対し，エッジ画像では他の窓枠を最大マッチングとしていた．窓枠のような他に似た形の物が画像内になければ，正しくマッチングできていたのではないかと考えられる．
| グレー画像 | エッジ画像 | 2値エッジ画像 | |
| SSD | 33 | 100 | 89 |
| NCC | 44 | 100 | 100 |
| ZNCC | 72 | 100 | 100 |
テンプレート2ではエッジ画像を用いた時，どの類似度の計算方法を使用しても成功率が100％だった．画像では失敗が多くZNCCを使った場合でも7割程度の成功率であった．雲程度の背景変化ならば，エッジ画像を用いることにより，少しの背景変化には対応することができると考えられる．背景に人や車など雲よりも形のはっきりした物が写る場合の検証は今回の実験ではできていなく，どこまでの背景変化に強いかは定かではないが，雲の動きと明るさに対応できることから，天候の変化にはある程度対応できるものと考えられる．
また，2値エッジ画像を用いた場合も，どの計算方法でも非常に良い成功率だった．2値エッジ画像の性質から，エッジ画像よりも背景変化に強いと推測することもできるが今回の実験では検証できていない．
| グレー画像 | エッジ画像 | 2値エッジ画像 | |
| SSD | 10 | 97 | 97 |
| NCC | 51 | 100 | 99 |
| ZNCC | 100 | 99 | 99 |
グレー画像でZNCCを使用したときと，エッジ画像でNCCを使用したときの成功率が100％だった．太陽の動きによる日差し程度ならZNCCで対応可能ということが考えられる．グレー画像でZNCC以外の方法では悪い結果となっている．エッジ画像と2値エッジ画像はどの方法でも安定して良い結果である．
| グレー画像 | エッジ画像 | 2値エッジ画像 | |
| SSD | 39 | 79 | 44 |
| NCC | 34 | 73 | 68 |
| ZNCC | 94 | 88 | 84 |
グレー画像でZNCCを用いた時に正解数94と良い結果．エッジ画像のZNCCも悪い結果ではない．固定カメラで撮影した画像100枚はすべてを同じ日に撮影したものではなく，別の日に撮影した画像に対してエッジ画像を使用したときに失敗が多かった．撮影した時期が季節の移り変わりであったことから，葉が落ちている等の変化が関係している可能性がある．また，同じ自然物でもテンプレート5と比べ成功率が高いのは，木の幹の部分は形が変わらないためだと考えられる．
| グレー画像 | エッジ画像 | 2値エッジ画像 | |
| SSD | 10 | 18 | 18 |
| NCC | 27 | 45 | 8 |
| ZNCC | 68 | 65 | 19 |
どの方法を使ってもよい結果は得られなかった．どの方法でもテンプレートの場所と少しずれた草むらを最大マッチングとしてしまった失敗が多く，草むらでは差が出にくいと考えられる．
テンプレート1，2，3と4，5を比べると分かるように，テンプレートに自然物を用いるより人工物を用いたほうが良い結果となっている．自然物では照明条件の変化だけでなく，季節の移り変わりによる形状の変化，風の影響などが大きくなってしまうためだと考えられる．照明条件の変化に加え，テンプレートの形状も変化してしまうとマッチング精度は大きく低下する．形状変化の少ないものをテンプレートとして選ぶべきである．
人工物をテンプレートとして選んだ場合，グレー画像に比べエッジ画像を用いた時のほうが，基本的に成功率が高くなることがわかる．唯一グレー画像の成功率がグレー画像を上回ったテンプレート3の結果から，多少の照明変化ならば類似度の計算方法にZNCCを使用することで対応できる．
エッジ画像を使用したマッチングでは，テンプレート1の結果から，光るものや形が同じで色の違うもの，テンプレート3の結果から，どうしても背景が写りこんでしまう画像のマッチングに強いと考えられる．
実験1の結果から，ここではアルゴリズムにZNCCを用いたものをのせる．
| あり | 無し | 差 | |
| テンプレート1 | 0.879 | 0.468 | 0.411 |
| テンプレート2 | 0.740 | 0.585 | 0.155 |
| テンプレート3 | 0.777 | 0.497 | 0.280 |
| テンプレート4 | 0.584 | 0.354 | 0.230 |
| テンプレート5 | 0.553 | 0.390 | 0.163 |
| あり | 無し | 差 | |
| テンプレート1 | 0.785 | 0.388 | 0.397 |
| テンプレート2 | 0.713 | 0.300 | 0.413 |
| テンプレート3 | 0.654 | 0.335 | 0.319 |
| テンプレート4 | 0.408 | 0.142 | 0.266 |
| テンプレート5 | 0.202 | 0.105 | 0.097 |
| あり | 無し | 差 | |
| テンプレート1 | 0.665 | 0.317 | 0.349 |
| テンプレート2 | 0.598 | 0.252 | 0.347 |
| テンプレート3 | 0.502 | 0.309 | 0.193 |
| テンプレート4 | 0.265 | 0.111 | 0.154 |
| テンプレート5 | 0.226 | 0.079 | 0.147 |
どのテンプレートを使った場合でも対象物あり，なしともにグレー，エッジ，2値エッジの順に類似度が高い．基本的に差が大きいのはエッジ画像である．特にテンプレート2の背景が写ってしまう画像では，グレー画像に比べ大きな差となっている．２値エッジ画像は今回の実験では強みを見つけられなかった．
本論文では，照明変化に対応するためにエッジ画像を用いたテンプレートマッチングの検証を行った．マッチしたものを数える実験と類似度の比較をする実験の2つの実験を行い，エッジ画像を用いる，テンプレートに人工物を選ぶ，類似度の計算方法にZNCCを使うという3つことをすることで，照明変化に堅牢なテンプレートマッチングができるという結論に至った．
今回の実験に使用した固定カメラで撮影した画像は，1つの場所で撮影したものだけであり，枚数も100枚と少なかった．結果をより確かなものにするため，他の場所で撮影した画像での検証，より多くの枚数での検証が必要である．また，今回の実験では固定カメラの画像を使用したが，自律走行ロボットが実際に走行し，カメラで撮影するものは固定カメラのものではない．自律走行ロボットが撮影する連続的な画像に対しても検証する必要がある．連続的な画像では対象物の大きさの変化，ズレ，ゆがみ等，様々な変化が考えられる．そういった手法にどこまで対応できるのか，対応するためにはどのようにすれば良いのかが今後の課題となる．
[1]國光 智,淺間 一,川端 邦明,三島 健稔 "2値エッジ画像のテンプレートによる屋外環境下にある対象物の検出", IEEJ Tranz. EIS,Vol.124, No.2, 2004.
[2]"パターンマッチング（正規化相関など）",http://imagingsolution.blog107.fc2.com/blog-entry-186.html,(access jul 21,2014).
[3]橋本研究室（秋月秀一，櫻本泰憲）(2013),"基本的なテンプレートマッチング",http://isl.sist.chukyo-u.ac.jp/Archives/tm.html,(access jul 21,2014).
[4]田村 秀行 "コンピュータ画像処理", オーム社, 2002
[5]WillowGarage,"OpenCV",http://opencv.org/,(access Apr 7,2014).
