![[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種類の高速化手法を考案した．
分割した各ブロックをテンプレートとして探索対象画像全体をテンプレートマッチングした結果を結果画像に保存する．ブロックを9個に分割していれば，結果画像も9枚作成される． そして各ブロックのスコアを求める際に，この結果画像から必要な部分だけを切り取ってベストスコアを求める．このようにすることで照合を行う回数が分割したブロックの数と同じになり結果，大幅な計算コストの削減になる．
探索対象画像上の点ｘ，ｙにテンプレートを置いた時と，その隣の点ｘ＋１，ｙにテンプレートをおいた時の照合を考えると，テンプレートを右に1つ動かしただけのため，1つの同じブロックの探索範囲はテンプレートの大部分が被っていることになる． 点(x,y)のベストスコアが被っている範囲に含まれていれば点(x＋1,y)の照合では，はみ出た1×(テンプレートの縦)の範囲だけを探索すればよく，更なる計算コストの削減になる．
高速化の効果は以下の表のようになった．計測に使った画像の大きさは，探索対象画像が744×480，テンプレート画像が320×240，ABMとFSwMのブロックの分割数は5×5の25個である．
| 手法 | 1枚あたりの実行速度 |
| 正規化相互相関マッチング | 約0.075秒 |
| ABM | 約0.6秒 |
| FSwM | 20分以上 |
| FSwM | 約2.0秒 |
高速化なしでは1枚の照合に20分以上かかっていたが，高速化を図ることにより1枚あたり2秒程度で照合を行えるようになった．
テンプレート画像と照明条件が異なる画像列を探索対象画像として実験を行う． 画像列は実際にロボットを走行させ撮影した全182枚の画像列である． 提案手法と既存手法でそれぞれ照合を行い，その結果を比較する．
結果が以下のグラフである．
#ref(): File not found: "gazo4shu.jpg" at page "自律走行ロボットのための撮影位置の変化に堅牢な画像照合手法"
赤が提案手法，緑が既存手法，青いラインがテンプレート画像の撮影地点となる． このグラフから既存手法，提案手法のどちらも照明条件が変化していても，正しくマッチングしていること，また，既存手法は撮影地点からずれると急激にスコアが落ちること， 提案手法では撮影地点付近でも高いスコアが出ていることがわかる． このことから，提案手法であるFSwMは既存手法と同様に照明条件の変化に強いマッチング手法といえる．さらに，提案手法は撮影地点から少しずれた地点でも高いスコアであることから，撮影地点の変化に対応しているといえる．
また，次の画像は撮影地点から前後2ｍズレた位置の画像に提案手法でマッチングしたときの結果画像である． 各ブロックの動きを見て本当に撮影地点のズレを吸収できているかを評価する． 画像の大きな赤枠がマッチング位置，小さい枠が各ブロックのマッチング位置を表している． 各ブロックの色はスコアが低いほど青に近く，スコアが高いほど赤に近い色となる． 画像から２ｍ手前では各ブロックが内側に，２ｍ奥では外側に移動していることが確認できる．2ｍ手前では探索対象は小さく，2ｍ奥では大きく写るため，ブロックが移動し撮影地点のズレを吸収しているといえる．このことからもFSwMは撮影地点のずれに対応した画像照合手法といえる．
本論文では，自律走行ロボットがテンプレートマッチングを用いて自律走行を行う際に問題となる，照明条件の変化，障害物による遮蔽，撮影地点の変化に堅牢なマッチング手法であるFlexible Sub-window Matching(FSwM) という手法を提案した．既にテンプレートマッチングを行う際，テンプレート画像を複数のブロック領域に分割し各ブロック単位で照合することで照明条件の変化，障害物による遮蔽に対応したAccumulated Block Match(ABM) という手法が提案されていたが，FSwM はそのABM を改良したものである．FSwM ではテンプレート画像 を複数のブロック領域に分割することはABMと同様であり，ABMの照明条件の変化，遮蔽に強いという特徴を継承している．各ブロックの照合を行う際，ブロック領域をそれぞれ独立に動かして近傍を探索することにより撮影地点の変化に対応した手法である．また，ブロックを独立に動かすことで計算コストが増大してしまったため，高速化の手法を考案し，実用的な範囲でFSwM を行えるようにした．評価実験として実際にロボットを走行させて撮影した撮影地点の変化がほとんどなく照明条件のみが変化している画像列に対しABM，FSwM を用いて照合を行い結果を比較した．実験からFSwM はABMと同様に照明条件の変化に頑強であること，ABMでは対応できない撮影地点の変化に対応した手法であることを確認した．
[1] 斉藤 文彦，"ブロック照合投票処理を用いた遮へいに強い画像マッチング"， 電子情報通信学会論文誌D,Vol.J84-D-,no.10,pp.2270-2279,2001.
[2] 山城 容一朗，怡土 順一，竹村 憲太郎，松本 吉央，高松 淳，小笠原 司，"ビューシーケンスに基づく照明変化に頑健な屋内外ナビゲーション", 日 本ロボット学会誌，Vol.27,No.7, pp.768-773,2009.
[3] 松本 吉央，稲葉 雅幸，井上 博弁，"ビューベースドアプローチに基づく移動 ロボットナビゲーション，日本ロボット学会誌，Vol.20,No.5, pp.506-514,2002."
[4] "パターンマッチング（正規化相関など）",http://imagingsolution.blog107.fc2.com/blog- entry-186.html,(access Jan 27,2017).
[5] 田村秀行, "コンピュータ画像処理", オーム社, 2002
[6] WillowGarage,"OpenCV",http://opencv.org/,(access Jan 27,2017).
