(57)【要約】【課題】  異なる天候や異なる季節においても、位置の特定を効率的に行う画像データからの位置推定方法、装置、プログラムを提供すること。【解決手段】  位置を特定するために有効な物体の画像特徴量として、正規化した色、エッジ密度、ハフ空間における投票の最大値、エッジ方向の分散の度合い、輝度の分散の度合いのいずれか１つまたは複数を組み合わせて物体を識別することを特徴とする物体認識部３、および物体識別の結果を用いて位置を特定する位置推定のための位置識別部５により、位置を同定する。さらに、位置推定を効率的に行うために、広域的位置推定部により、移動履歴の確率分布として、マルコフ過程とベイズ定理を利用し位置の存在確率を求めることにより正答となる位置を推定する。【選択図】図２
2010026713.tif 000002
【特許請求の範囲】
【請求項１】
入力された画像データから当該画像データに写されている物体の位置を特定するために、前記画像データから物体の画像特徴量を抽出する画像特徴抽出ステップと、
前記画像特徴抽出ステップにより抽出された画像特徴量を基に、予め作成されている物体の識別データからなる物体モデルデータベースを用いて物体を識別する物体識別ステップと、
前記物体識別ステップにより識別された物体を、予め作成されている物体の位置のデータからなる位置モデルデータベースと、前回の位置から現在の位置への移動履歴の確率分布とを用いて当該物体の位置を特定する位置識別ステップと
を備えたことを特徴とする画像データから位置を推定する位置推定方法。
【請求項２】
前記物体モデルデータベースを作成するために、入力された画像データから前記画像特徴抽出ステップにより物体の画像特徴量を抽出し、物体モデルデータベースに保存する物体モデル学習ステップと、
前記位置モデルデータベースを作成するために、物体と当該物体の位置のデータとを対応させて前記位置モデルデータベースに保存する位置モデル学習ステップと
を備えたことを特徴とする請求項１に記載の画像データから位置を推定する位置推定方法。
【請求項３】
前記位置を特定する物体の画像特徴量として、正規化した色、エッジ密度、ハフ空間における投票の最大値、エッジ方向の分散の度合い、輝度の分散の度合いのいずれか１つまたは複数の組み合わせを用いて物体を識別することを特徴とする請求項１又は２に記載の画像データから位置を推定する位置推定方法。
【請求項４】
前記移動履歴の確率分布として、マルコフ過程とベイズ定理を利用し位置の存在確率を求めることにより位置を推定することを特徴とする請求項１乃至３に記載の画像データから位置を推定する位置推定方法。
【請求項５】
入力された画像データから当該画像データに写されている物体の位置を特定するために、前記画像データから物体の画像特徴量を抽出する画像特徴抽出手段と、
前記画像特徴抽出手段により抽出された画像特徴量を基に、予め作成されている物体の識別データからなる物体モデルデータベースを用いて物体を識別する物体識別手段と、
前記物体識別手段により識別された物体を、予め作成されている物体の位置のデータからなる位置モデルデータベースと、前回の位置から現在の位置への移動履歴の確率分布とを用いて当該物体の位置を特定する位置識別手段と
を備えたことを特徴とする画像データから位置を推定する位置推定装置。
【請求項６】
前記物体モデルデータベースを作成するために、入力された画像データから前記画像特徴抽出手段により物体の画像特徴量を抽出し、物体モデルデータベースに保存する物体モデル学習手段と、
前記位置モデルデータベースを作成するために、物体と当該物体の位置のデータとを対応させて前記位置モデルデータベースに保存する位置モデル学習手段と
を備えたことを特徴とする請求項５に記載の画像データから位置を推定する位置推定装置。
【請求項７】
前記画像特徴量として、正規化した色、エッジ密度、ハフ空間における投票の最大値、エッジ方向の分散の度合い、輝度の分散の度合いのいずれか１つまたは複数の組み合わせを用いて物体を識別することを特徴とする請求項５又は６に記載の位置推定装置。
【請求項８】
前記移動履歴の確率分布として、マルコフ過程とベイズ定理を利用し位置の存在確率を求めることにより正答となる位置を推定することを特徴とする請求項５乃至７の何れかに記載の位置推定装置。
【請求項９】
コンピュータに
入力された画像データから当該画像データに写されている物体の位置を特定するために、前記画像データから物体の画像特徴量を抽出する画像特徴抽出ステップと、
前記画像特徴抽出ステップにより抽出された画像特徴量を基に、予め作成されている物体の識別データからなる物体モデルデータベースを用いて物体を識別する物体識別ステップと、
前記物体識別ステップにより識別された物体を、予め作成されている物体の位置のデータからなる位置モデルデータベースと、前回の位置から現在の位置への移動履歴の確率分布とを用いて当該物体の位置を特定する位置識別ステップと
を実行させることを特徴とする位置推定プログラム。
【請求項１０】
コンピュータに
前記物体モデルデータベースを作成するために、入力された画像データから前記画像特徴抽出ステップにより物体の画像特徴量を抽出し、物体モデルデータベースに保存する物体モデル学習ステップと、
前記位置モデルデータベースを作成するために、物体と当該物体の位置のデータとを対応させて前記位置モデルデータベースに保存する位置モデル学習ステップと
を実行させることを特徴とする請求項９に記載の位置推定プログラム。
【請求項１１】
前記位置を特定する物体の画像特徴量として、正規化した色、エッジ密度、ハフ空間における投票の最大値、エッジ方向の分散の度合い、輝度の分散の度合いのいずれか１つまたは複数の組み合わせを用いて物体を識別することを特徴とする請求項９又は１０に記載の位置推定プログラム。
【請求項１２】
前記移動履歴の確率分布として、マルコフ過程とベイズ定理を利用し位置の存在確率を求めることにより位置を推定することを特徴とする請求項９乃至１１の何れかに記載の位置推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データから位置を推定する位置推定方法、位置推定装置及び位置推定プログラムに関する。
【背景技術】
【０００２】
ロボットや自動車などの移動体が屋外環境を走行する際に、自分の位置を知る必要がある。従来、Ｇｌｏｂａｌ  ｐｏｓｉｔｉｏｎｉｎｇ  ｓｙｓｔｅｍ  （以下、ＧＰＳと記す）を用いた位置推定が頻繁に用いられていた。しかし、高い建物の近くなどでは衛星の隠蔽やマルチパスの現象により、信頼できる位置推定が常に得られるとは限らない。そこで、場所固有の画像を元に位置を推定する技術が必要とされている。そのような技術において、物体認識や画像比較にＳｃａｌｅ  ｉｎｖａｒｉａｎｔ  ｆｅａｔｕｒｅ  ｔｒａｎｓｆｏｒｍ  （以下、ＳＩＦＴと記す）などの局所画像特徴を用いる場合が多い。ＳＩＦＴとは画像中の特徴点を検出し、特徴点ごとに周辺のエッジ勾配を求めるものである。画像の回転・スケール変化・照明変化等に頑健であり、これを用いた画像比較による位置推定が提案されている（非特許文献１、２、および３を参照）。
【非特許文献１】Ｍ．Ｃｕｍｍｉｎｓ，Ｐ．Ｎｅｗｍａｎ，“Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ａｐｐｅａｒａｎｃｅ  Ｂａｓｅｄ  Ｎａｖｉｇａｔｉｏｎ  ａｎｄ  Ｌｏｏｐ  Ｃｌｏｓｉｎｇ”，Ｐｒｏｃ．  ＩＣＲＡ，ｐｐ．２０４２−２０４８，２００７．
【非特許文献２】Ｃｈａｎｏｐ  Ｓｉｌｐａ−Ａｎａｎ，Ｒｉｃｈａｒｄ  Ｈａｒｔｌｅｙ，“Ｖｉｓｕａｌ  ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  ｌｏｏｐ−ｂａｃｋ  ｄｅｔｅｃｔｉｏｎ  ｗｉｔｈ  ａ  ｈｉｇｈ  ｒｅｓｏｌｕｔｉｏｎ  ｏｍｎｉｄｉｒｅｃｔｉｏｎａｌ  ｃａｍｅｒａ”，Ｉｎ  Ｐｒｏｃ．  Ｏｆ  ＯｍｎｉＶｉｓ−０５，Ｗｏｒｋｓｈｏｐ  ｉｎ  ｃｏｎｊｕｎｃｔｉｏｎ  ｗｉｔｈ  ＩＣＣＶ−２００５，２００５．
【非特許文献３】Ｄ．Ｇ．  Ｌｏｗｅ，  “Ｄｉｓｔｉｎｃｔｉｖｅ  Ｉｍａｇｅ  Ｆｅａｔｕｒｅｓ  ｆｒｏｍ  Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｋｅｙｐｏｉｎｔｓ，  Ｉｎｔ．  Ｊ．  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，  Ｖｏｌ．  ６０，  Ｎｏ．  ２，  ｐｐ．  ９１−１１０，  ２００４．
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、前記非特許文献１および２に関する技術においては、画像比較に異なる天候や異なる季節で取得した画像を用いた場合、対応数は減少し、位置推定に失敗するという問題点があった。
【０００４】
本発明は上記課題を解決するためになされたものであり、場所を特定するために有効な特徴となる物体（木や電線など）を認識することにより、異なる天候や異なる季節においても場所を同定し、その際、確率的位置推定を用いることで、位置の特定を効率的に行う画像データから位置を推定する位置推定方法、位置推定装置及び位置推定プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の第一態様の画像データより位置を推定する位置推定方法では、入力された画像データから当該画像データに写されている物体の位置を特定するために、前記画像データから物体の画像特徴量を抽出する画像特徴抽出ステップと、前記画像特徴抽出ステップにより抽出された画像特徴量を基に、予め作成されている物体の識別データからなる物体モデルデータベースを用いて物体を識別する物体識別ステップと、前記物体識別ステップにより識別された物体を、予め作成されている物体の位置のデータからなる位置モデルデータベースと、前回の位置から現在の位置への移動履歴の確率分布とを用いて当該物体の位置を特定する位置識別ステップとを備えたことを特徴とする。
【０００６】
また、前記物体モデルデータベースを作成するために、入力された画像データから前記画像特徴抽出ステップにより物体の画像特徴量を抽出し、物体モデルデータベースに保存する物体モデル学習ステップと、前記位置モデルデータベースを作成するために、物体と当該物体の位置のデータとを対応させて前記位置モデルデータベースに保存する位置モデル学習ステップとを備えても良い。
【０００７】
本発明の第二態様の画像データより位置を推定する位置推定装置では、入力された画像データから当該画像データに写されている物体の位置を特定するために、前記画像データから物体の画像特徴量を抽出する画像特徴抽出手段と、前記画像特徴抽出手段により抽出された画像特徴量を基に、予め作成されている物体の識別データからなる物体モデルデータベースを用いて物体を識別する物体識別手段と、前記物体識別手段により識別された物体を、予め作成されている物体の位置のデータからなる位置モデルデータベースと、前回の位置から現在の位置への移動履歴の確率分布とを用いて当該物体の位置を特定する位置識別手段とを備えたことを特徴とする。
【０００８】
また、前記物体モデルデータベースを作成するために、入力された画像データから前記画像特徴抽出手段により物体の画像特徴量を抽出し、物体モデルデータベースに保存する物体モデル学習手段と、前記位置モデルデータベースを作成するために、物体と当該物体の位置のデータとを対応させて前記位置モデルデータベースに保存する位置モデル学習手段とを備えても良い。
【０００９】
本発明の第三態様の位置推定プログラムでは、コンピュータに入力された画像データから当該画像データに写されている物体の位置を特定するために、前記画像データから物体の画像特徴量を抽出する画像特徴抽出ステップと、前記画像特徴抽出ステップにより抽出された画像特徴量を基に、予め作成されている物体の識別データからなる物体モデルデータベースを用いて物体を識別する物体識別ステップと、前記物体識別ステップにより識別された物体を、予め作成されている物体の位置のデータからなる位置モデルデータベースと、前回の位置から現在の位置への移動履歴の確率分布とを用いて当該物体の位置を特定する位置識別ステップとを実行させることを特徴とする。
【００１０】
また、コンピュータに前記物体モデルデータベースを作成するために、入力された画像データから前記画像特徴抽出ステップにより物体の画像特徴量を抽出し、物体モデルデータベースに保存する物体モデル学習ステップと、前記位置モデルデータベースを作成するために、物体と当該物体の位置のデータとを対応させて前記位置モデルデータベースに保存する位置モデル学習ステップとを実行させるようにしても良い。
【００１１】
尚、第一乃至第三態様の何れにおいても、前記位置を特定する物体の画像特徴量として、正規化した色、エッジ密度、ハフ空間における投票の最大値、エッジ方向の分散の度合い、輝度の分散の度合いのいずれか１つまたは複数の組み合わせを用いて物体を識別するようにしても良い。また、前記移動履歴の確率分布として、マルコフ過程とベイズ定理を利用し位置の存在確率を求めることにより位置を推定するようにしても良い。
【発明の効果】
【００１２】
本発明では、場所を特定するために有効な特徴となる木や電線などの物体を認識することにより、従来技術では困難であった、異なる天候や異なる季節においても場所を同定できる。その際、確率的位置推定を用いることで、位置推定を従来技術よりも効率的に行うとともに信頼性を向上させることができる。
【発明を実施するための最良の形態】
【００１３】
本発明の一実施の形態の位置推定方法からなる位置推定プログラムを実行する位置推定装置１０としてのコンピュータ２０について説明する。まず、コンピュータ２０の電気的構成について説明する。図１は、コンピュータ２０のブロック図である。図１に示すように、コンピュータ２０には、コンピュータ２０の制御を司るコントローラとしてのＣＰＵ１１が設けられ、該ＣＰＵ１１には、各種データを一時的に記憶するＲＡＭ１２と、ＢＩＯＳ等を記憶したＲＯＭ１３と、データの受け渡しの仲介を行うＩ／Ｏインタフェイス２３とが接続されている。Ｉ／Ｏインタフェイス２３には、ハードディスク装置１２０が接続され、当該ハードディスク装置１２０には、物体モデルデータ記憶エリア１２１と、位置モデルデータベース記憶エリア１２２と、プログラム記憶エリア１２３と、移動履歴記憶エリア１２４とが少なくとも設けられている。
【００１４】
プログラム記憶エリア１２３には、位置推定プログラム等が記憶されている。また、物体モデルデータ記憶エリア１２１には、入力された画像データから後述する画像特徴抽出処理により物体の画像特徴量を抽出した複数の物体の画像特徴量からなる物体モデルデータベースが記憶されている。また、位置モデルデータベース記憶エリア１２２には、後述する位置モデル学習処理により作成され、物体と当該物体の位置のデータとを対応させて記憶させた位置モデルデータベースが記憶されている。また、移動履歴記憶エリア１２４には、移動履歴が記憶されている。なお、コンピュータ２０がハードディスク装置１２０を備えていない専用機の場合は、ＲＯＭ１３に上記プログラムやデータベース等が記憶される。
【００１５】
また、Ｉ／Ｏインタフェイス２３には、外部装置と有線、無線又は赤外線でネットワークを介して通信するための通信装置装置１９と、マウス２１と、ビデオコントローラ１６と、キーコントローラ１７と、ＣＤ−ＲＯＭドライブ１８と、ＵＳＢ（登録商標）コントローラ４１が接続されている。ビデオコントローラ１６にはディスプレイ２４が接続され、キーコントローラ１７にはキーボード２２が接続されている。なお、ＣＤ−ＲＯＭドライブ１８に挿入されるＣＤ−ＲＯＭ１１４には、位置推定プログラム等が記憶され、導入時には、この位置推定プログラムが、ＣＤ−ＲＯＭ１１４からハードディスク装置１２０にセットアップされてプログラム記憶エリア１２３に記憶される。また、ＵＳＢ（登録商標）コントローラ４１には、デジタルカメラ４２が接続可能となっている。さらに、ＵＳＢ（登録商標）コントローラ４１には、図示外のカードリーダ等も接続できる。従って、本発明に使用する画像データ（動画及び静止画）は、ＵＳＢ（登録商標）コントローラ４１を介して、取り込むことができる。
【００１６】
次に、図２を参照して、本発明の概要について説明する。図２は、位置推定装置１０の概念図である。図２に示すように、本発明の一実施の形態である位置推定装置１０は、画像特徴抽出部１、物体モデル学習部２、物体モデルデータベース６、物体認識部３、位置モデル学習部４、位置モデルデータベース７、位置推定部５から構成される。尚、これらは、上記コンピュータ２０が位置推定プログラムを実行することにより実現される。さらに、位置推定部５は、物体識別の結果と位置モデルデータベースを用いて位置を特定する位置識別部と、移動履歴の確率分布として、マルコフ過程とベイズ定理を利用し位置の存在確率より正答となる位置を求める広域的位置識別部から構成される。
【００１７】
次に、図３乃至図５を参照して、物体モデル学習処理、位置モデル学習処理、位置推定処理について説明する。図３は、物体モデル学習処理のフローチャートであり、図４は、位置モデル学習処理のフローチャートであり、図５は、位置推定処理のフローチャートである。物体モデル学習時には、まず、手動により物体の集合に対して、正例と負例の選別を行う（Ｓ１１）。ここで、正例とは、集合に適合したモデルをいう。一方、負例とは、集合に不適合なモデルをいう。屋外で撮影した多数のカラー画像について、移動物体がほとんど存在しない、画像の上半部を取り出し、さらにその場所を固定の大きさの小領域（ウィンドウと呼ぶ）に分割する。ウィンドウの中から認識の対象となる物体のみが写っているものを取り出し、その物体の正例とする。それ以外の物体のみが移っているウィンドウを負例とする。例えば、画像を見ながら、マウス２１でクリックして、葉がある木、葉のない木、空、建物強い直線、電線等を選択する（Ｓ１１）。次いで、各画像の特徴の抽出を画像特徴抽出部１を用いて行う（Ｓ１２）。そして、抽出された画像の特徴を葉がある木、葉のない木、空、建物の強い直線、電線に対応付けて物体モデルデータベース６に記憶する物体モデルの学習を行う（Ｓ１３）。
【００１８】
次に、図４を参照して位置モデルの学習処理について説明する。まず、位置モデルの学習処理では、物体モデル学習の結果を用いて、自動的に集合の選別を行いう（Ｓ２１）。次に、画像特徴抽出部１で画像特徴の抽出を行う（Ｓ２２）。次いで、物体認識部３で、画像特徴と画像モデルデータベースから物体の認識を行う（Ｓ２３）。次いで、認識された物体について、位置モデル学習部４で位置モデルを学習する（Ｓ２４）。前記学習過程では、学習処理には、物体モデルおよび位置モデルデータベースへの保存が含まれている。
【００１９】
次に、図５を参照して、位置推定処理について説明する。まず、位置推定時には、位置推定処理を行う。この位置推定処理では、まず、現在の位置の範囲が分かっている場合には、その範囲内に含まれる位置に対し、１を含まれる位置の数で割った値を初期確率として与え、それ以外の位置には確率０を与える。また、現在の位置の範囲が分からないときには、すべての位置に対し当確率となるような初期分布を与える初期位置分布の設定を行う（Ｓ３１）。次に、カメラで撮影した画像を入力し（Ｓ３２）、入力された画像に対して、画像特徴抽出部１により入力画像の特徴を抽出する（Ｓ３３）。次に、物体認識部３により画像の特徴量と物体モデルデータベースから物体を認識する（Ｓ３４）。つぎに、物体認識の結果と位置モデルデータベースから位置推定部５により位置の推定を行う（Ｓ３５）。このとき、確率的位置推定によって効率的に位置の推定を行う。次いで、位置推定処理を続けて行うときは（Ｓ３６：ＮＯ）、Ｓ３２に戻り、次の画像を入力し（Ｓ３２）、Ｓ３３〜Ｓ３５の処理を行う。そして、次の画像が無く、位置推定処理を続けて行わず終了のときは（Ｓ３６：ＹＥＳ）、処理を終了する。
【００２０】
次に物体認識および位置推定のための識別器の構成方法、確率的位置推定方法について述べる。
【００２１】
［物体認識のための識別器］
取得した画像を小ウィンドウに分割し、小ウィンドウごとに物体を決定する。たとえば、横３２０ピクセル×縦２４０ピクセルの画像の場合、上半部の３２０×１２０ピクセルの領域を取り出し、１６×１６ピクセルのウィンドウ１６０個に分割する。図６に物体認識のための識別器の構成方法を示す。この識別器はＳｕｐｐｏｒｔ  Ｖｅｃｔｏｒ  ｍａｃｈｉｎｅ（以下「ＳＶＭ」とも言う。）により各識別器を各々構成している。例えば、図６に示すように、木識別器３１、一様領域識別器３２、建物識別器３３、電線識別器（図示外）等を構成している。尚、学習時には、小領域ごとに、いくつかの画像特徴を抽出した結果をＳＶＭ学習アルゴリズム３０に入力して、学習結果を物体モデルデータベースに記憶する。ここで、さまざまな場所・季節・天候での木のサンプルを正とすると、木以外のサンプルが負とされる。尚、認識時には、例えば、小領域ごとに、いくつかの画像特徴を抽出した結果を木識別器３１に入力すると木であるか木でないかが出力される。ここで、認識する物体の種類と、それぞれの物体に見られる特徴を以下に示す。
【００２２】
（１）葉のある木：葉のエッジが多く観測され、葉の色は季節により変化する。
【００２３】
（２）葉の落ちた木：枝のみが観測され、枝のエッジは様々な方向に向いている。
【００２４】
（３）建物：直線性のあるエッジが観測される。道路上の看板や境界もこのクラスとする。
【００２５】
（４）一様領域：建物の壁や空などエッジがほとんど存在しないクラスである。
【００２６】
（５）電線：強い直線性のあるエッジが観測され、領域内の輝度がほぼ一定のものである。
【００２７】
葉のある木または葉の落ちた木については、どちらかが認識されればそこに木が存在すると考える。これら５つの物体を認識するために、次に述べる画像特徴を用いた。
【００２８】
（ｒ，ｇ，ｂ）：正規化した色を示す。ｒ＝Ｒ／（Ｒ＋Ｇ＋Ｂ）、ｇ＝Ｇ／（Ｒ＋Ｇ＋Ｂ）、ｂ＝Ｂ／（Ｒ＋Ｇ＋Ｂ）として、それぞれ求める。正規化した色は０〜１の値を持つ。
【００２９】
ｆｅｄｇｅ  ｄｅｎｓｉｔｙ：エッジ密度を表す。小ウィンドウ内のエッジ数を小ウィンドウの面積で割り求める。エッジ数は、以下の式で定義されるソーベルオペレータにより計算した画像の勾配∇Ｉの値がしきい値以上のピクセルの数として計算する。
【００３０】
【数１】
2010026713.tif 000003
【００３１】
【数２】
2010026713.tif 000004
【００３２】
【数３】
2010026713.tif 000005
【００３３】
Ｉ（ｉ，ｊ）はピクセル、（ｉ，ｊ）の濃淡値であり、ＲＧＢの値から次式で求める。
【００３４】
【数４】
2010026713.tif 000006
【００３５】
ｆｅｄｇｅ  ｄｅｎｓｉｔｙは０〜１の値を持つ。
【００３６】
ｆｈｏｕｇｈ：各小ウィンドウの濃淡値に対してハフ変換を適用したときのハフ空間における投票の最大値を表す。ハフ変換では直線を以下の式で表す。θは直線とｘ軸のなす角度、ρは直線と原点との距離である。
【００３７】
【数５】
2010026713.tif 000007
【００３８】
各エッジについて、その座標（ｉ，ｊ）を上式に代入してθとρの関係式が得られ、離散化したθとρの空間（ハフ空間）に対し、関係式を満たすθとρの組み合わせを投票する。この処理をウィンドウ内のすべてのエッジについて行い、ｆｈｏｕｇｈを計算する。ｆｈｏｕｇｈの値を３００で割ることにより正規化し、特徴量とする。強い直線のエッジを持つ物体の認識に有効である。ｆｈｏｕｇｈは０〜１の値を持つ。
【００３９】
ｆｅｄｇｅ  ｄｉｓｔｒｉｂ：エッジ方向の分散の度合いを示す。循環統計に基づき以下の式で求める。
【００４０】
【数６】
2010026713.tif 000008
【００４１】
【数７】
2010026713.tif 000009
【００４２】
【数８】
2010026713.tif 000010
【００４３】
ここで、ｎはエッジの数、φi は i 番目のエッジの方向、ai はその強さである。様々な方向のエッジを持つ物体の認識に有効である。ｆｅｄｇｅ  ｄｉｓｔｒｉｂは０〜１の値を持つ。
【００４４】
ｆｂｒｉｇｈｔｎｅｓｓ  ｄｉｓｔｒｉｂ：輝度の分散の度合いを示す。小ウィンドウの濃淡値の分散を求め、５０００という値で割り求める。
【００４５】
表１に認識物体と使用画像特徴を示す。これら画像特徴を用いて、Ｓｕｐｐｏｒｔ  ｖｅｃｔｏｒ  ｍａｃｈｉｎｅ（ＳＶＭ）により識別器をそれぞれ構成する。ＳＶＭは学習データ集合 (x1, y1), (x2, y2), ..., (xN, yN) （xi は実数ベクトル、yi は-1 か +1、-1を持つデータは負例、+1を持つデータは正例）から、正例と負例を識別する、以下のような識別面
【００４６】
【数９】
2010026713.tif 000011
【００４７】
を学習するアルゴリズムであり、ラグランジェ乗数 ai （≧ 0） を導入し、以下の目的関数を最小化することにより、パラメータ w, h を求める。この問題は
【００４８】
【数１０】
2010026713.tif 000012
【００４９】
を以下の制約の下で最大化することにより、求められる。
【００５０】
【数１１】
2010026713.tif 000013
【００５１】
識別面が非線形の場合には、上記の LD の代わりに、カーネル関数 K(xi, xj) を用いた次式を用いる
【００５２】
【数１２】
2010026713.tif 000014
【００５３】
物体認識のための識別器においては、以下のカーネル関数を用いる。
【００５４】
【数１３】
2010026713.tif 000015
【００５５】
以上の最大化処理を行うと、αi > 0 となる学習データ xi の集合が得られる。これをサポートベクトルという。図２０は一様領域の学習結果の例である。サポートベクトルの添え字の集合を S とおくと、最適パラメータは以下のように求められる。
【００５６】
【数１４】
2010026713.tif 000016
【００５７】
ある特徴ベクトル x の識別は以下の式で行う。
【００５８】
【数１５】
2010026713.tif 000017
【００５９】
出力 y が正なら、学習したクラスに属するとし、負なら属さないと判定する。
【００６０】
【表１】
2010026713.tif 000018
上記の表１では、チェックのされている欄のｏｂｊｅｃｔが使用される。尚、「ｓｋｙ」は「空」、「ｂｕｉｌｄｉｎｇ  ｓｉｄｅ  ｗａｌｌｓ」は「建物の壁」、「ｔｒｅｅｓ  ｗｉｔｈ  ｌｅａｖｅｓ」は「木（葉有り）」、「ｔｒｅｅｓ  ｗｉｔｈｏｕｔ  ｌｅａｖｅｓ」は「木（葉無し）」、「ｂｕｉｌｄｉｎｇ  ｗｉｎｄｏｗｓ  ａｎｄ  ｂｏｕｎｄａｒｉｅｓ」は「建物窓、及び、境界線（建物の強い直線）」、「ｅｌｅｃｔｒｉｃ  ｃａｂｌｅ」は「電線」である。
【００６１】
識別器（ＳＶＭ）を用いて物体認識を行う場合は、画像を小ウィンドウに分割し、識別器に並列に入力する。この際それぞれの識別器に応じて、その識別器を構成した際の特徴の組を小ウィンドウから計算し入力とする。入力した小ウィンドウの各特徴の値が、識別器の構成の際に学習した正例に近ければ、対応する識別器が反応し正の値を返すので、そのウィンドウの出力を１とし、そうでなければ０とする。
【００６２】
１枚の入力画像に対し、１６０個のウィンドウが得られ、周囲の1行、1列分のウィンドウを除いた１０８個のウィンドウそれぞれについて、５種の物体が存在するかどうか識別する。結果として、１０８次元の０−１ベクトル（ウィンドウごとに対応する物体がある場合は１、ない場合は０を決定し、それらを並べたもの）が５つ得られる。葉のない木と葉のある木の２つのベクトルについては、対応する要素の論理和をとった新たなベクトルを生成して、それを用いる。その結果、４つの１０８次元の０−１ベクトルが得られ、それらをそのまま結合した４３２次元の０−１ベクトルを認識結果ベクトルとする。
【００６３】
［位置識別器］
まず学習走行時にデジタルカメラにより取得した画像系列から、まずオプティカルフローに基づき、停車中と右左折中の画像を除く。オプティカルフローは、1フレーム前の画像の各ピクセルについて、そのピクセルを中心とするウィンドウを設定しテンプレートとし、さらに現在のフレームで対応するピクセルの周りに探索領域を設定し、その領域内でテンプレートともっとも濃度値のパターンが似ているピクセルを探索することによって求める。オプティカルフローは画像中の各点がどのように動いたかを示すので、画像全体のオプティカルフローの平均値が小さいときは停車中であり、全ての点が同じ方向に動いているときには右左折中と判断する。
【００６４】
推定を行うためのある長さの道路に沿った領域を考え、その領域内に自動車が存在すればその位置にいるとする。領域内で取得した連続したｎｐ枚の画像に対して、物体認識を行い、得られた物体認識結果ベクトルの集合を正例とする。 
【００６５】
正例の前後ｎｂ枚間は正例と似た風景であるので、緩衝領域としてこの間のデータは使用しない。正例と緩衝領域以外から、一定間隔で取得した画像から得られた認識結果ベクトルを負例とする。この正例と負例を用いてＳＶＭにより識別器３４，３５等を構成する。位置推定のためのＳＶＭでは、カーネル関数を使わないＳＶＭ（線形ＳＶＭ）を用いる。線形ＳＶＭはカーネル関数として内積を計算する関数（K(x, y)=x・y）を利用することと等価である。他の場所についても同様にして画像系列ｎ枚ごとに識別器を構成する（図７参照）。尚、図２１に、ある位置に対する学習結果の例を示す。
【００６６】
位置識別器を用いてどの位置にいるかを判断する場合は、まず取得した画像の物体認識を行う。その結果得られた認識結果ベクトルを位置推定の識別器に次々に入力し、それぞれの識別器の出力を確認する。正の反応を返した識別器があった場合、入力画像を取得した場所は、その識別器の構成に用いた正例画像を取得した場所と似ていることになる。
【００６７】
［広域的位置識別］
ロボットや車などが移動するときには、事前に学習した場所を一つずつ順番に通過していく。したがって、ある時点での場所が分かればその少し後の場所を限定することができる。これを移動履歴の考慮という。移動履歴を考慮しない場合、現在の場所で取得した画像から得た物体認識結果を、全ての位置推定のための識別器に入力しなければならない。しかし、移動履歴を考慮すると、存在する可能性のある位置識別器にのみ入力すればよく、位置推定の時間は短縮される。しかし、ある時点での場所が確定的に決められない可能性があるので、各時点で存在する可能性のある場所の確率分布Ｂｅｌ（ｌ）を保持し、それを毎回の観測で更新する。位置認識は場所の分布の予測と推定の2段階から成る。予測を行うための式（数１６）を次に示す。
【００６８】
【数１６】
2010026713.tif 000019
【００６９】
ここで、数１６のＢｅｌ（ｌ’）は前回の観測後の場所ｌ’の確率を、Ｐａ（ｌ｜ｌ’）は場所ｌ’から場所ｌへの遷移確率を示している。０より大きいＢｅｌ(ｌ’) を持つすべての場所ｌ’について数１の計算を行って得られる（数１７）が現在の場所の予想分布である。
【数１７】
2010026713.tif 000020
【００７０】
予測と最新の観測結果を統合することにより、現在の場所の分布を計算するための式を（数１８）に示す。
【数１８】
2010026713.tif 000021
【００７１】
数１８のＰ（ｓ｜ｌ）はｌでの観測値ｓから決定した尤度であり、数１９で計算する。各場所ごとに、そこに存在する確率の予想値（数１６により計算）と観測の確からしさ（尤度、Ｐ（ｓ｜ｌ）で計算）を掛けて、全体として１になるように正規化する（Ｐ（ｓ）で割る）ことにより、現在の観測後の場所の確率分布を計算する式が数１８である。なお、数１６はマルコフ過程、数１８はベイズの公式を表している。
【００７２】
遷移確率Ｐａ（ｌ｜ｌ‘）には、図８に示す自動車の速度から決定した状態遷移モデルを用いる。ある時点で場所 l にいるとき、次の時点では、同じ場所 l にいる確率が５０％、１つ先の場所にいる確率が４０％、2つ先の場所にいる確率が１０％であるというモデルを用いる。
【００７３】
また尤度は、位置識別器の出力値に数１９に示すシグモイド関数を適用した確率モデルを用いて計算する。ＳＶＭｌ（ｓ） は、場所ｌについて学習した位置推定のためのＳＶＭに観測ｓ（具体的には、観測結果ベクトル）を入力として与えたときの出力を示す。出力が大きくなるほど尤度の値が大きくなる。図９にシグモイド関数を示す。実施例ではｋ＝５として用いる。
【００７４】
【数１９】
2010026713.tif 000022
【実施例】
【００７５】
［広域的位置識別実験］
これまでに述べた方法を用いて位置推定を行った。画像取得はＣａｎｏｎ（登録商標）製デジタルカメラ、ＩＸＹ（登録商標）  ＤＩＧＩＴＡＬ  １０００（商品名）を用いた。画像サイズは３２０×２４０ピクセルで１５［ｆｒａｍｅ／ｓ］で取得した。
【００７６】
次に、図１０を参照して、広域的位置識別実験の経路図について説明する。図１０は、広域的位置識別実験の経路図である。図１０に示すように、経路は約３．２［ｋｍ］で、自動車の速度は約２５［ｋｍ／ｈ］である。
【００７７】
学習用の画像系列は２００７年６月２０日午後５時（天候晴れ）のとき取得した。画像枚数は７１５５枚である。
【００７８】
広域的位置識別を行うための入力画像系列は２００７年６月２０日午後５時１０分（天候晴れ）、２００７年６月２２日午後５時（天候雨）、２００７年７月２４日午後７時（天候晴れ）、２００７年１０月２９日午後２時（天候曇り）のとき取得した。それぞれおよそ７０００枚である。
【００７９】
［物体認識結果］
物体認識には取得した画像の上半分３２０×１２０ピクセルを使用する。画像の上半分を２０×８個の小ウィンドウで分割し、小ウィンドウごとにどの物体に最も近いかＳＶＭを用いて認識を行う。
【００８０】
図１１は異なる日照条件でのある位置の物体認識結果である。日照条件にロバストな物体認識が行えていることがわかる。処理時間は画像処理が約０．１秒、ＳＶＭ処理が約０．２２秒である（例えば、Ｉｎｔｅｌ  Ｃｏｒｅ２  Ｄｕｏ  ３ＧＨｚを使用）。
【００８１】
次にそれぞれの物体識別器の認識率を求める。識別器の構成に用いていない小ウィンドウを用いて、認識率を求めるためのデータを作成した。このデータはそれぞれ５０００〜７０００個から成り、正例と負例の割合はほぼ同じとなっている。認識率は、葉のある木は８９．２５％、葉の落ちた木は８１．２３％、一様領域は９８．４３％、建物は７６．５２％、電線は９１．７０％となった。
【００８２】
［位置識別結果］
位置推定のための識別器は、ある位置について、その位置で取得画像を中心とした連続する正例画像ｎｐ＝３０枚を使用し、その画像の前後ｎｂ＝３０枚を緩衝領域として使用せず、負例は残りの画像から３０枚間隔で取得し構成した。ｎ＝３０枚ごとに位置推定のための識別器を構成し、位置推定のための識別器は全部で１９８個となった。これは１９８個の場所を識別できることを示す。各場所間の間隔は道路上で約１６［ｍ］の距離となる。
【００８３】
画像入力は１５枚に１枚（１秒間に１枚）行い、位置を推定する。自動車が学習時の走行速度と同じであれば、約８［ｍ］に１枚の画像を入力することとなる。入力する画像の上半分の物体認識を行い、６４０次元の特徴ベクトルを作成する。さらにカメラのずれに対応するため、小ウィンドウ数２０×８から１８×６の並びを切り出して用いる。これにより、図２２に示すように９パターンの１８×６の並びの配置があり、それぞれについて４３２次元の認識結果ベクトルが作成される。これを位置推定のための識別器に入力し、得られた９つの出力のうち最大のものを位置推定に用いる。
【００８４】
図１２乃至図１４に経路上の位置（ｌｏｃａｔｉｏｎ）１、２、３の移動履歴を考慮しないときの、位置推定結果を示す。図１２乃至図１４の各図ごとに、左の画像が入力画像、真ん中のグラフは、入力画像の認識結果ベクトルをすべての場所の識別器へ与えたときの出力値を、右の画像が最も高い出力を示した識別器に対応する場所において、学習走行時に取得した画像である。移動履歴を考慮しない場合、このように全ての識別器に対する出力を計算し、もっとも高いものを選択するという処理が必要になる。また、位置１のように、複数の識別器が反応を返す、もしくは位置３のように、どの識別器も正の反応を返さないなどの問題が生じる。
【００８５】
［広域的位置識別結果］
次に移動履歴を考慮した広域的位置識別を行う。存在確率の初期状態は、全ての位置推定の識別器に等確率で存在するものとした。
【００８６】
図１５乃至図１７に、図１２乃至図１４で示した３つの場所に対する、移動履歴を考慮した広域的位置識別の結果を示す。右の画像と左の画像は図１２乃至図１４と同じであり、真ん中のグラフは推定された場所の確率分布を示す。履歴を考慮することにより、限定された範囲に可能性が絞られていることが分かる。 
【００８７】
似たような景色が続く場所では、場所の確率分布が広い範囲に広がる（多くの場所が０より大きい確率を持つ）。しかし、先に進んで特徴的な景色を持つ場所に来ると、確率分布は狭い範囲に収束する。図１８は存在確率の収束を示すグラフ及び写真である。上の３枚の画像は左から右へ時間が進む方向へ並べたものであり、対応するグラフはそれぞれその時点での場所の確率分布を示す。位置の確率分布が広がった状態から、特徴的な物体を見つけることにより収束する様子がわかる。
【００８８】
表２に従来の履歴を使わない位置推定および履歴を使った広域的位置識別の比較結果を示す。２種類の評価値を用いた。一つは正解率であり、正しく位置推定が行えた入力画像の数と全入力画像の数の比である。もう一つは最大得点率であり、正しく位置推定が行えかつ最大の出力値を得た入力画像の数と全入力画像数の比である。表２より位置推定の精度が向上していることがわかる。物体認識を含む処理時間は、通常の位置推定では１枚あたり約１２秒かかっていたものが、広域的位置識別では識別器が５つ程度に絞られることで、約０．７８秒となった（例えば、Ｉｎｔｅｌ  Ｃｏｒｅ２  Ｄｕｏ  ＣＰＵ  ３ＧＨｚを使用）。
【００８９】
【表２】
2010026713.tif 000023
【００９０】
また表２には局所画像特徴ＳＩＦＴ（非特許文献３を参照）を用いた広域的位置識別結果も示している。ＳＩＦＴは画像の空間方向およびスケール方向の変化を調べてその極値を求め、さらにその場所での主勾配方向を基準に特徴量を記述することにより、スケール変化や回転に不変な特徴量を求める方法である。物体までの距離や見る角度が変わっても安定的に特徴点が抽出できるため、物体認識によく用いられている。
【００９１】
ＳＩＦＴを位置認識に利用するため、学習時の画像からＳＩＦＴ特徴を抽出して記憶しておき、位置推定時に画像中のＳＩＦＴ特徴を抽出し、記憶したものと照合して同じ特徴があるかどうかで位置推定を行う。移動履歴を考慮した位置推定手法に適用するために、照合によって得られた対応点数に式（数２０）を適用することにより、尤度を計算する。
【００９２】
【数２０】
2010026713.tif 000024
【００９３】
数２０のｍａｔｃｈｎｕｍｌ（ｓ）は場所ｌで記憶したＳＩＦＴ特徴と現在の観測ｓから抽出したＳＩＦＴ特徴を照合した結果の対応点の数を示す。はパラメータであり、その値は、経験的に対応点数が８になると尤度が０．５となるように、８とした、この式はシグモイド関数であり、図９に示すグラフと類似の形状を持つ。
【００９４】
図１９は日照条件がＳＩＦＴ特徴点の対応数に与える影響を示したものである。左列の２枚の画像はほぼ同じ時間に撮影したもの、右列の２枚の画像は晴れた日と雨の日に撮影したものである。上下の画像を結ぶ線は対応点の組を表している。日照条件が同じであれば多くの対応点が得られるが、日照条件が大きく変わると対応点の数が急激に減少するので、ＳＩＦＴなどの局所特徴量を用いる手法は天候や季節の変化に弱い。
【００９５】
表３に初期位置が未知の場合の正しい識別器への収束の成功率と収束したときの平均必要フレーム数を示す。初期位置が未知の場合は、すべての場所が当確率になるような初期分布を与える。収束したかどうかは、推定された場所の確率分布の中に、正しい場所が含まれているかどうかで判定する。成功率はそれぞれ９０回位置推定を行い収束に成功した回数を調べることで求めた。表３からも対応点数の減少は位置推定を失敗させる大きな原因であることがわかる。しかし我々の手法は、初期位置が未知でも正しく位置推定が行える。
【００９６】
【表３】
2010026713.tif 000025
【産業上の利用可能性】
【００９７】
自律移動ロボットへの応用や人間の移動支援への応用等が考えられる。
【図面の簡単な説明】
【００９８】
【図１】コンピュータ２０のブロック図である。
【図２】位置推定装置１０の概念図である。
【図３】物体モデル学習処理のフローチャートである。
【図４】位置モデル学習処理のフローチャートである。
【図５】位置推定処理のフローチャートである。
【図６】物体認識のための識別器の構成方法を示す図である。
【図７】識別器の構成の概念図である。
【図８】自動車の速度から決定した状態遷移モデルの図である。
【図９】シグモイド関数のグラフである。
【図１０】広域的位置識別実験の経路図である。
【図１１】異なる日照条件でのある位置の物体認識結果の図である。
【図１２】経路上の位置（ｌｏｃａｔｉｏｎ）１の移動履歴を考慮しないときの、位置推定結果を示すグラフ及び写真である。
【図１３】経路上の位置（ｌｏｃａｔｉｏｎ）２の移動履歴を考慮しないときの、位置推定結果を示すグラフ及び写真である。
【図１４】経路上の位置（ｌｏｃａｔｉｏｎ）３の移動履歴を考慮しないときの、位置推定結果を示すグラフ及び写真である。
【図１５】図１２で示した場所に対する、移動履歴を考慮した広域的位置識別の結果を示すグラフ及び写真である。
【図１６】図１３で示した場所に対する、移動履歴を考慮した広域的位置識別の結果を示すグラフ及び写真である。
【図１７】図１４で示した場所に対する、移動履歴を考慮した広域的位置識別の結果を示すグラフ及び写真である。
【図１８】存在確率の収束を示すグラフ及び写真である。
【図１９】日照条件がＳＩＦＴ特徴点の対応数に与える影響を示した写真である。
【図２０】一様領域の学習結果の例である。
【図２１】ある位置に対する学習結果の例である。
【図２２】位置推定時に用いる、９つの物体認識領域の例を示す図である。
【符号の説明】
【００９９】
１  画像特徴抽出部
２  物体モデル学習部
３  物体認識部
４  位置モデル学習部
５  位置推定部
６  物体モデルデータベース
７  位置モデルデータベース
１０  位置推定装置
１１  ＣＰＵ
１２  ＲＡＭ
１３  ＲＯＭ
２０  コンピュータ
４１  ＵＳＢコントローラ
４２  デジタルカメラ
１２０  ハードディスク装置
１２１  物体モデルデータ記憶エリア
１２２  位置モデルデータベース記憶エリア
１２３  プログラム記憶エリア
１２４  移動履歴記憶エリア
【図１】
2010026713.tif 000026
【図２】
2010026713.tif 000027
【図３】
2010026713.tif 000028
【図４】
2010026713.tif 000029
【図５】
2010026713.tif 000030
【図６】
2010026713.tif 000031
【図７】
2010026713.tif 000032
【図８】
2010026713.tif 000033
【図９】
2010026713.tif 000034
【図１０】
2010026713.tif 000035
【図１１】
2010026713.tif 000036
【図１２】
2010026713.tif 000037
【図１３】
2010026713.tif 000038
【図１４】
2010026713.tif 000039
【図１５】
2010026713.tif 000040
【図１６】
2010026713.tif 000041
【図１７】
2010026713.tif 000042
【図１８】
2010026713.tif 000043
【図１９】
2010026713.tif 000044
【図２０】
2010026713.tif 000045
【図２１】
2010026713.tif 000046
【図２２】
2010026713.tif 000047