(57)【要約】  高速且つ頑健にSfMを求める技法を提供すること。  サーバの役割を果たすコンピュータ・システムが、スマート・フォンから、通信機能により、画像と加速度センサの測定結果を受け取る。コンピュータ・システムはまず、画像から垂直方向のエッジだけを抽出する。そのために、加速度センサを用いて、カメラ座標系における重力ベクトルを求める。そして次に、システムは、重力ベクトルを用いてスクリーン座標系での垂直方向の消失点(u',v')を求める。次にコンピュータ・システムは、スクリーン座標系の各ピクセル(u,v)毎に、輝度のU方向及びV方向の微分ベクトルを計算する。次にコンピュータ・システムは、垂直方向に並んだエッジの集合に対して、垂直方向のエッジ強度の総和を求め、それにより垂直方向の直線を抽出する。コンピュータ・システムは、この抽出された直線の周囲で特徴ベクトルを計算する。
2014027500.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理により、画像から特徴を抽出する方法であって、
画像取得手段と、加速度測定手段をもつモバイル・デバイスから、画像と、加速度の測定データを受け取るステップと、
前記加速度の測定データに基づき、前記画像のカメラ座標系における重力ベクトルを求めるステップと、
前記重力ベクトルを用いて、前記画像のスクリーン座標系での垂直方向の消失点を求めるステップと、
前記スクリーン座標系の各ピクセル毎に２軸方向の微分ベクトルを求めるステップと、
前記消失点から前記各ピクセルをむすぶ結線ベクトルを求めるステップと、
前記微分ベクトルと前記結線ベクトルのなす角度がある閾値の範囲にあることに基づき、垂直方向のエッジを特定するステップと、
前記垂直方向のエッジ強度の総和を求めて所定の変数配列に書き込むステップと、
前記変数配列に基づきキーポイントを抽出するステップと、
前記キーポイントから特徴量を計算するステップを有する、
特徴抽出方法。
【請求項２】
前記加速度測定手段は、加速度センサである、請求項１に記載の方法。
【請求項３】
前記垂直方向のエッジ強度の総和を求めて所定の変数配列に書き込むステップは、スクリーン座標を(u,v)とし、前記消失点を(u',v')をとしたとき、前記微分ベクトルと(u'-u,v'-v)の内積の絶対値を計算し、前記変数配列に書き込むステップを有する、請求項１に記載の方法。
【請求項４】
前記キーポイントを抽出するステップは、前記変数配列を横長の画像とみなし、DoG関数を使って極値を計算するステップを含む、請求項１に記載の方法。
【請求項５】
前記モバイル・デバイスは、スマート・フォンである、請求項１に記載の方法。
【請求項６】
前記特徴量を計算するステップが、HoGを計算するステップを有する、請求項１に記載の方法。
【請求項７】
前記モバイル・デバイスにより、前記ステップの一部または全てが実行される、請求項１に記載の方法。
【請求項８】
コンピュータの処理により、画像から特徴を抽出するプログラムであって、
前記コンピュータに、
画像取得手段と、加速度測定手段をもつモバイル・デバイスから、画像と、加速度の測定データを受け取るステップと、
前記加速度の測定データに基づき、前記画像のカメラ座標系における重力ベクトルを求めるステップと、
前記重力ベクトルを用いて、前記画像のスクリーン座標系での垂直方向の消失点を求めるステップと、
前記スクリーン座標系の各ピクセル毎に２軸方向の微分ベクトルを求めるステップと、
前記消失点から前記各ピクセルをむすぶ結線ベクトルを求めるステップと、
前記微分ベクトルと前記結線ベクトルのなす角度がある閾値の範囲にあることに基づき、垂直方向のエッジを特定するステップと、
前記垂直方向のエッジ強度の総和を求めて所定の変数配列に書き込むステップと、
前記変数配列に基づきキーポイントを抽出するステップと、
前記キーポイントから特徴量を計算するステップを実行させる、
特徴抽出プログラム。
【請求項９】
前記モバイル・デバイスは、スマート・フォンである、請求項８に記載のプログラム。
【請求項１０】
前記加速度測定手段は、加速度センサである、請求項９に記載のプログラム。
【請求項１１】
前記垂直方向のエッジ強度の総和を求めて所定の変数配列に書き込むステップは、スクリーン座標を(u,v)とし、前記消失点を(u',v')をとしたとき、前記微分ベクトルと(u'-u,v'-v)の内積の絶対値を計算し、前記変数配列に書き込むステップを有する、請求項８に記載のプログラム。
【請求項１２】
前記キーポイントを抽出するステップは、前記変数配列を横長の画像とみなし、DoG関数を使って極値を計算するステップを含む、請求項８に記載のプログラム。
【請求項１３】
前記特徴量を計算するステップが、HoGを計算するステップを有する、請求項８に記載のプログラム。
【請求項１４】
前記モバイル・デバイスにより、前記ステップの一部または全てが実行される、請求項８に記載のプログラム。
【請求項１５】
コンピュータの処理により、画像から特徴を抽出するシステムであって、
画像取得手段と、加速度測定手段をもつモバイル・デバイスから、画像と、加速度の測定データを受け取る手段と、
前記加速度の測定データに基づき、カメラ座標系における重力ベクトルを求める手段と、
前記重力ベクトルを用いて、スクリーン座標系での垂直方向の消失点を求める手段と、
スクリーン座標系の各ピクセル毎に２軸方向の微分ベクトルを求める手段と、
前記消失点から前記各ピクセルをむすぶ結線ベクトルを求める手段と、
前記微分ベクトルと前記結線ベクトルのなす角度がある閾値の範囲にあることに基づき、垂直方向のエッジを特定する手段と、
前記垂直方向のエッジ強度の総和を求めて所定の変数配列に書き込む手段と、
前記変数配列に基づきキーポイントを抽出する手段と、
前記キーポイントから特徴量を計算する手段を有する、
特徴抽出システム。
【請求項１６】
前記モバイル・デバイスは、スマート・フォンである、請求項１５に記載のシステム。
【請求項１７】
前記加速度測定手段は、加速度センサである、請求項１６に記載のシステム。
【請求項１８】
前記垂直方向のエッジ強度の総和を求めて所定の変数配列に書き込む手段は、スクリーン座標を(u,v)とし、前記消失点を(u',v')をとしたとき、前記微分ベクトルと(u'-u,v'-v)の内積の絶対値を計算し、前記変数配列に書き込む処理を行なう、請求項１５に記載のシステム。
【請求項１９】
前記キーポイントを抽出する手段は、前記変数配列を横長の画像とみなし、DoG関数を使って極値を計算する処理を行なう、請求項１５に記載のシステム。
【請求項２０】
前記特徴量を計算する手段が、HoGを計算する処理を行なう、請求項１５に記載のシステム。
【請求項２１】
コンピュータの処理により、画像から特徴を抽出するモバイル・デバイスであって、
画像取得手段と、
加速度測定手段と、
前記加速度測定手段からの測定データに基づき、前記画像取得手段により取得した画像のカメラ座標系における重力ベクトルを求める手段と、
前記重力ベクトルを用いて、前記画像のスクリーン座標系での垂直方向の消失点を求める手段と、
前記スクリーン座標系の各ピクセル毎に２軸方向の微分ベクトルを求める手段と、
前記消失点から前記各ピクセルをむすぶ結線ベクトルを求める手段と、
前記微分ベクトルと前記結線ベクトルのなす角度がある閾値の範囲にあることに基づき、垂直方向のエッジを特定する手段と、
前記垂直方向のエッジ強度の総和を求めて所定の変数配列に書き込む手段と、
前記変数配列に基づきキーポイントを抽出する手段と、
前記キーポイントから特徴量を計算する手段を有する、
モバイル・デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像から特徴量を抽出し、位置推定を行うための技法に関する。
【背景技術】
【０００２】
近年、ショッピングセンターや公共施設などにおける顧客の動線解析や在庫管理など、屋内で位置を推定する技術の要望が高まっている。【０００３】
屋内では、WiFiやRFIDなどの無線機器を用いるとノイズが大きいため、正確な位置推定が難しい。GPSは比較的正確な位置推定を与えるが、屋内ではGPSは使えない。そこで、移動体にカメラを取り付け、撮像した画像を解析することで位置を予測する技法が注目されている。【０００４】
これに関する従来技術として、ＷＯ２００８／０８７９７４は、複数のカメラの位置関係を算出する技術、および、算出した位置関係に基づいてユーザインタフェースを生成する技術に関し、ＧＰＳを用いず、撮像により、複数のカメラの位置を算出することを開示する。【０００５】
藤吉 弘亘、"Gradientベースの特徴抽出 : SIFTとHOG", 情報処理学会研究報告. CVIM, [コンピュータビジョンとイメージメディア] 2007(87), 211-224, 2007-09-03は、SIFTのアルゴリズムについて概説し、DOG画像からの極値検出や、HOGについても説明する。【０００６】
特開２０１１−５３１８１は、地磁気センサを搭載する必要がなく、利用者の向きを推定したり、その推定結果に従って表示部の表示情報を制御したりすることができる、信頼性の高い情報端末装置を提供するために、SIFT(Scale-Invariant Feature Transform)特徴量を使用して、方位を推定することを開示する。【０００７】
SIFTは、画像の特徴抽出技法の一つで、特徴点検出と、特徴点の周囲の特徴ベクトル計算方法に関するものであるが、これとは別に、画像から特異点とカメラ位置の３次元上の位置関係を復元する技術として、Structure from Motion(SfM)が知られており、SfMは例えば、特開平１０−４０３８５、特開２００９−２３７８４５、特開２００９−２３７８４７などに記載がある。【０００８】
SfMは、コーナーになっている部分を取り出すなど、画像から特徴点を検出し、特徴点の周囲の8x8ピクセルの明るさを並べて、単純に64ビットの特徴ベクトルを作るなどの方法で特徴点の周囲の画素から特徴ベクトルを計算し、複数の画素間でマッチングを行なう技術であり、これにより、特徴点の３次元上の位置と、カメラの位置を同時に復元することができる。【０００９】
しかし、SfMを安定して求めるには、ノイズに頑健、すなわち画像のブレに対して頑健且つ画像の回転・拡大縮小に頑健な特徴量の計算手法が必要であるところ、従来の方法は計算コストが大きいという問題があった。一般的にSfMを求めるためには、ピクセル数に比例した計算量が必要なので、計算コストに対する配慮は本質的である。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】ＷＯ２００８／０８７９７４
【特許文献２】特開２０１１−５３１８１
【特許文献３】特開平１０−４０３８５
【特許文献４】特開２００９−２３７８４５
【特許文献５】特開２００９−２３７８４７
【非特許文献】
【００１１】
【非特許文献１】藤吉 弘亘、"Gradientベースの特徴抽出 : SIFTとHOG", 情報処理学会研究報告. CVIM, [コンピュータビジョンとイメージメディア] 2007(87), 211-224, 2007-09-03
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、この発明の目的は、高速且つ頑健にSfMを求める技法を提供することにある。
【課題を解決するための手段】
【００１３】
この発明は、SfMで利用される特徴量は重力方向と平行な直線が多く、利用可能なモバイル・デバイスであるスマート・フォンなどに、加速度センサあるいはジャイロセンサが付属していることに着目して、上記課題を解決するものである。【００１４】
この発明によれば、サーバの役割を果たすコンピュータ・システムが、スマート・フォンから、通信機能により、画像と加速度センサの測定結果を受け取る。【００１５】
コンピュータ・システムはまず、画像から垂直方向のエッジだけを抽出する。そのために、加速度センサを用いて、カメラ座標系における重力ベクトルを求める。そして次に、システムは、重力ベクトルを用いてスクリーン座標系での垂直方向の消失点(u',v')を求める。【００１６】
次にコンピュータ・システムは、スクリーン座標系の各ピクセル(u,v)毎に、輝度のu方向及びv方向の微分ベクトルを計算する。そして、微分ベクトルと(u'-u,v'-v)のなすcos成分を求め、その２つのベクトルを長さ１で正規化した後、内積を計算する。このとき、cosの絶対値がある閾値以上の場合、その画素は垂直方向のエッジをもっていると判定する。【００１７】
次にコンピュータ・システムは、垂直方向に並んだエッジの集合に対して、垂直方向のエッジ強度の総和を求める。具体的には、スクリーン座標(u,v)をカメラ座標系に変換し、スクリーン座標(u,v)の２軸から１軸に射影する。そして、(u,v)における微分ベクトルの絶対値を計算し、テーブルsum[q]に書き込む。【００１８】
こうしてsum[q]が用意されると、コンピュータ・システムは、sum[q]をw×1の横長の画像とみなし、例えば、DoG(difference of Gaussian)関数を使って極値を計算する。この極値を用いて、特徴量を計算する。
【発明の効果】
【００１９】
この発明によれば、モバイル・デバイスから受け取った画像と加速度センサの測定結果に基づき、垂直方向に並んだエッジを検出し、それらのエッジを用いて特徴抽出を行なうので、より少ない計算量で高速に位置推定を行なうことが可能となる。
【図面の簡単な説明】
【００２０】
【図１】室内で、スマート・フォンにより加速度データと画像データを取得して、処理のためにコンピュータに送信する様子を示す図である。
【図２】本発明で使用されるコンピュータのハードウェアの例示的なブロック図である。
【図３】本発明の処理に係る、機能ブロック図である。
【図４】sumの計算のための処理のフローチャートを示す図である。
【図５】DoGの計算及び極値検出処理のフローチャートを示す図である。
【図６】特徴量計算処理のフローチャートを示す図である。
【図７】カメラ座標系、スクリーン、重力方向の関係を示す図である。
【図８】画素の２軸の座標を、重力方向と直交する１軸に射影する方法を示す図である。
【図９】各画素と消失点を結ぶ地面と垂直な直線を、スクリーンに射影した様子を示す図である。
【図１０】画像における、抽出されたキーポイントを示す図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して、本発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。また、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことに留意されたい。
【００２２】
図１は、本発明を実施するための一例の全体構成を示す概要図である。図１において、部屋１０２には、収納庫１０４などの場所的特徴物が配置されている。
【００２３】
オペレータ１０６は、加速度センサとカメラ機能をもつ、スマート・フォン１０８で、部屋１０２の内部を撮影し、その撮影したイメージ・データと、加速度センサの測定データを、無線通信により、室内に配置されているコンピュータ１１０に送信する。
【００２４】
コンピュータ１１０は、送信されたイメージ・データと、加速度センサの測定データを受信し、これらのデータを用いて特徴を抽出し、場所を推定する処理を行なう。コンピュータ１１０は、スマート・フォン１０８から加速度センサの測定データと画像データを受信可能な構成であるなら、遠隔の場所に配置していてもよい。その場合、ＷｉＦｉなどの受信ステーションを経由して、遠隔の場所に配置されたコンピュータ１１０に情報が転送されることになる。あるいは、最近のスマート・フォン１０８は、処理能力が高いので、スマート・フォン１０８の内部で、以下で説明する、特徴を抽出する処理を行なうようにしてもよい。以下の実施例では説明の便宜上、スマート・フォン１０８とは別のコンピュータ１１０で、特徴を抽出し、場所を推定する処理を行なうものとして説明を行なう。
【００２５】
図２は、コンピュータ１１０のハードウェア構成のブロック図を示す。図２において、システム・バス２０２には、ＣＰＵ２０４と、主記憶（ＲＡＭ）２０６と、ハードディスク・ドライブ（ＨＤＤ）２０８と、キーボード２１０と、マウス２１２と、ディスプレイ２１４が接続されている。ＣＰＵ２０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社の、Core(商標） i7、Core(商標） i5、AMD Athlon (商標）IIなどを使用することができる。主記憶２０６は、好適には、４ＧＢ以上の容量をもつものである。
【００２６】
システム・バス２０２にはさらに、通信インターフェース２１６が接続されている。通信インターフェース２１６は、例えばＩＥＥＥ８０２．１１ａ／ｂ／ｇの規格に従い、アンテナ２１８を介して、スマート・フォン１０８と通信可能である。なお、コンピュータ１１０がスマート・フォン１０８からデータを受け取る方式は、ＩＥＥＥ８０２．１１ａ／ｂ／ｇに限定されず、パケット通信など、任意の方式を使用することができる。
【００２７】
ハードディスク・ドライブ２０８には、オペレーティング・システムが、格納されている。オペレーティング・システムは、Linux（商標）、マイクロソフト社のWindows 7（商標）、Windows XP（商標）、アップルコンピュータのMac OSX（商標）などの、ＣＰＵ２０４に適合する任意のものを使用することができる。
【００２８】
ハードディスク・ドライブ２０８にはさらに、図３に関連して後で説明する、メイン・プログラム３０２、sum計算ルーチン３０６、DoGの計算＆極値検出ルーチン３０８、及び特徴量計算ルーチン３１０が保存されている。これらは、C、C++、Java(R)などの既存の任意のプログラミング言語で作成することができる。
【００２９】
図３は、コンピュータ１１０における、本発明に関連する機能を実行する部分のソフトウェア構成のブロック図である。
【００３０】
図３において、メイン・プログラム３０２は、キーボード２１０やマウス２１２の操作により起動され、通信モジュール３０４の働きで、WiFiなどの仕組みにより、スマート・フォン１０８から、画像データと、加速度センサの測定データを受け取り、好適にはハードディスク・ドライブ２０８に保存する。
【００３１】
メイン・プログラム３０２はさらに、sum計算ルーチン３０６とDoGの計算＆極値検出ルーチン３０８と特徴量計算ルーチン３１０を起動し、スマート・フォン１０８から送信された画像データと、加速度センサの測定データに基づき、本発明に従い、特徴抽出を開始する。
【００３２】
より具体的には、sum計算ルーチン３０６は、スマート・フォン１０８から送信された画像データと、加速度センサの測定データとから、１次元配列であるsumを計算する処理を行なう。sum計算ルーチン３０６の処理の詳細は、図４のフローチャートを参照して、後でより詳しく説明する。
【００３３】
DoGの計算＆極値検出ルーチン３０８は、sum計算ルーチン３０６によって計算されたsumの値を用いて、DoG (Difference of Gaussian)を計算し、極値を検出する処理を行なう。DoGの計算＆極値検出ルーチン３０８の処理の詳細は、図５のフローチャートを参照して、後でより詳しく説明する。
【００３４】
特徴量計算ルーチン３１０は、DoGの計算＆極値検出ルーチン３０８によって検出された極値（キーポイント）に基づき、特徴量を計算する処理を行なう。特徴量計算ルーチン３１０の処理の詳細は、図６のフローチャートを参照して、後でより詳しく説明する。
【００３５】
次に、図４のフローチャートを参照して、sum計算ルーチン３０６の処理について説明する。sum計算ルーチン３０６は、ステップ４０２に示すように、画像の輝度I(u,v)と、閾値の値thresholdを引数として、メイン・プログラム３０２により呼び出される。ここで、画像の輝度I(u,v)とは、ピクセル座標(x,y) = (u,v)における画素の輝度である。閾値の値thresholdは、１つの実施例では0.95とセットされる。
【００３６】
sum計算ルーチン３０６は、ステップ４０４で、消失点u',v'を求める。すなわち、wを画像の幅、hを画像の高さ、fを焦点距離、Vg = (xg,yg,zg)を、スマート・フォン１０８から受け取った、重力方向をあらわす加速度の値のベクトルとすると、以下のような式により、消失点u',v'を計算する。
u' = f*xg/zg + w/2
v' = -f*yg/zg + h/2
【００３７】
sum計算ルーチン３０６は、ステップ４０６で、下記の式により、全ピクセル(u,v)に対して、du(u,v), dv(u,v), dlen(u,v)を求める。ここで、du(u,v)は、(u,v)におけるu方向の微分であり、dv(u,v)は、(u,v)におけるv方向の微分である。
【数１】
2014027500.tif 000003
なおここでは、微分を、前進差分と後進差分の差の平均をとる形で計算したが、適宜、前進差分だけ、あるいは後進差分だけのような任意の微分の計算方式を採用することができる。
【００３８】
sum計算ルーチン３０６は次に、ステップ４０８で、全ピクセル(u,v)に対して、消失点に向かうベクトル(u'-u,v'-v)と、(-dv(u,v),du(u,v))のなす角のコサイン(cosine)成分c(u,v)を次の式で求める。
【数２】
2014027500.tif 000004
【００３９】
sum計算ルーチン３０６は次に、ステップ４１０で、水平面に射影した点q(u,v)を求める。より具体的にはまず、V = (x,y,1) = ((u - w/2)/f, -(v - h/2)/f, 1)で、スクリーン座標から、カメラ座標に変換した点を求める。図７は、カメラ座標系、スクリーン、重力方向の関係を模式的に示す図である。次にsum計算ルーチン３０６は、Vh = (xh,yh,1) = V - Vg*<V,Vg>/<Vg,Vg>と(xg/zg,yg/zg,1)を通り、スクリーン上(z = 1)で、Vgと直交する位置を求め、Vhのx座標xhを、例えば、小数点以下を切り捨てることにより整数化した値をq(u,v)とする。すなわち、q(u,v) = (int) xhである。ここで、<V,Vg>は、ベクトルVとベクトルVgの内積をあらわす。図８に、射影によりq(u,v)を求める様子を模式的に示す。
【００４０】
sum計算ルーチン３０６は次に、ステップ４１２で、１次元配列sumを用意する。
【００４１】
sum計算ルーチン３０６は次に、ステップ４１４からステップ４２０までで、全ピクセル(u,v)に亘る処理を行なう。すなわち、ステップ４１６で、所与のピクセル(u,v)について、|c(u,v)| > thresholdかどうか判断し、もしそうなら、ステップ４１８で、sum[q(u,v)] += dlen(u,v)により、dlen(u,v)の値を足し込む。この実施例では、threshold = 0.95と設定されている。なお、dlen(u,v)の値はステップ４０６で、すべての(u,v)について、予め計算されている。
【００４２】
このとき、sum[q(u,v)]の値は、q(u,v)を通り地面と垂直な直線をスクリーンに射影した直線に沿って、垂直方向のエッジの強さを合算した値である。また、q(u,v)とは、q(u,v)を通り地面と垂直な直線を表している。
【００４３】
このようにして、ステップ４１４からステップ４２０までで、全ピクセル(u,v)に亘って処理が完了すると、Dogの計算及び極値検出に必要なsumの値が得られる。
【００４４】
次に、図５のフローチャートを参照して、DoGの計算及び極値検出ルーチン３０８の処理について説明する。DoGの計算及び極値検出ルーチン３０８は、ステップ５０２に示すように、sum計算ルーチン３０６によって計算されたsumと、パラメータdを入力として、メイン・プログラム３０２により呼び出される。
【００４５】
DoGの計算及び極値検出ルーチン３０８は、ステップ５０４で、標準偏差σ = σ0、σ0k、σ0k2、σ0k3、・・・で、sumをガウシアン平滑化し、sum1、sum2、sum3、sum4・・・をそれぞれ得る。
【００４６】
ガウシアン平滑化とは、下記のような関数を畳み込む計算を行なうことである。
【数３】
2014027500.tif 000005
【００４７】
kはσの分割数であり、スケールスペースの分割数をsとすると、k = 21/sと設定される。ここで、例えば藤吉 弘亘、"Gradientベースの特徴抽出 : SIFTとHOG", 情報処理学会研究報告. CVIM, [コンピュータビジョンとイメージメディア] 2007(87), 211-224, 2007-09-03などの記載に基づき、σ0 = 1.6、分割数s = 3とおくものとする。
【００４８】
DoGの計算及び極値検出ルーチン３０８は、ステップ５０６で、下記のとおり差分画像を計算して、dog1、dog2、dog3、・・・を得る。
dog1 = sum2 - sum1
dog2 = sum3 - sum2
dog3 = sum4 - sum3
・・・
【００４９】
ステップ５０８からステップ５１４までは、全てのq,iはの組み合わせに亘る処理であり、ステップ５１０でDoGの計算及び極値検出ルーチン３０８は、q,iの全ての近傍のq',i'で、dogi[q] < dogi'[q'] - dが成立するかどうか、すなわち、dogi[q]が極値になっているかどうかを判断し、もしそうなら、ステップ５１２で、q,iを検出した直線として記録する。なお、q,iの近傍のq',i'とはq±δ、i±δ以内のようなq',i'であって、例えば、δ = 2などと選んでおく。また、dの値は、大きいほど、より先鋭な極値を選ぶように条件設定される。
【００５０】
DoGの計算及び極値検出ルーチン３０８は、ステップ５１０でq,iの全ての近傍のq',i'で、dogi[q] < dogi'[q'] - dが成立すると判断すると、ステップ５１２で、q,iを、検出した直線として記録する。
【００５１】
こうしてステップ５０８からステップ５１４までを全てのq,iの組み合わせに亘って処理すると、全ての極値(q,i)の組み合わせが集まることになる。極値(q,i)において、i番目のDoGの値を求めるために使われた標準偏差をσとすると、(q,σ)をキーポイントと呼ぶ。dogi = sumi+1 - sumiにおいて、標準偏差σは、例えばsumi+1またはsumiのガウシアン平滑化における標準偏差である。
【００５２】
図１０は、ある画像における抽出されたキーポイントの例を示す。
【００５３】
次に、図６のフローチャートを参照して、特徴量計算ルーチン３１０の処理について説明する。特徴量計算ルーチン３１０は、全てのキーポイントの値(q,σ)を入力として、メイン・プログラム３０２により呼び出される。特徴量計算ルーチン３１０は、藤吉 弘亘、"Gradientベースの特徴抽出 : SIFTとHOG", 情報処理学会研究報告. CVIM, [コンピュータビジョンとイメージメディア] 2007(87), 211-224, 2007-09-03に記述されているような、HoG(Histograms of Oriented Gradients)に基づく特徴抽出を行なう。
【００５４】
図６において、ステップ６０２からステップ６２０までのループは、全てのキーポイントの値における、個々のキーポイントの値(p,σ)毎の処理に対応する。ここで、σは、極値(q,i)におけるdogiの計算に使用されたsumi+1またはsumiのガウシアン平滑化における標準偏差である。
【００５５】
特徴量計算ルーチン３１０は、ステップ６０４で、下記の式により、qに対するスクリーン上の直線u = av + bを求める。
xh = (q - w/2)/f
yh = -(xg*xh + zg)/yg
uh = q
vh = -yh*f + h/2
a = (uh - u')/(vh - v')
b = uh - a*vh
【００５６】
ステップ６０６からステップ６１４までのループは、0,1,2,...,hの個々のvに対する処理である。
【００５７】
特徴量計算ルーチン３１０は、ステップ６０８で、ステップ６０４で決定されたa,bを用いて、u = av + bの計算を行なう。
【００５８】
特徴量計算ルーチン３１０は、ステップ６１０で、(u,v)が垂直方向のエッジかどうか判断し、そうでないなら次のステップ６１２をスキップし、そうなら、ステップ６１２で、def = I(u -σ,v) - I(u +σ,v)と、dot(u,v)を計算する。ここで、dot(u,v)は、(u'-u,v'-v)と、(-dv(u,v),du(u,v))の内積である。ここでσは、当該キーポイントを計算した際のガウシアン平滑化の標準偏差である。
【００５９】
こうして、v = 0,1,,...,hの各々についてステップ６０６からステップ６１４までのループを辿ると、v = 0,1,,...,hの各々についてdef = I(u -σ,v) - I(u +σ,v)と、dot(u,v)が揃う。そこで特徴量計算ルーチン３１０はステップ６１６で、各々のdefを降順にソートし、defに対応するdot(u,v)を足しこんでいく。そして、dotの累算が、dotの総和の半数を超えたところのdefの値を以って、defのmedian(中央値)とする。
【００６０】
次に特徴量計算ルーチン３１０はステップ６１８で、ステップ６１６でmedianとして選ばれたdefに対応する(u,v)におけるI(u -σ,v)とI(u +σ,v)の２つの輝度を、当該直線の特徴量とする。
【００６１】
このようにして、ステップ６０２からステップ６２０までを、全てのキーポイント(q,σ)について処理することにより、全てのキーポイント(q,σ)についての特徴量が得られる。
【００６２】
メイン・プログラム３０２は、このようにして得られたキーポイント(q,σ)についての特徴量でもって、既存の画像から抽出された直線の特徴量とマッチするものを探す。そして、クエリー画像の直線と、既存の画像の直線のマッチングができたら、バンドル調整（Bundle Adjustment）技法を使って、スマート・フォン１０８の位置を推定することができる。
【００６３】
以上のように、加速度センサとカメラ機能をもつスマート・フォンから、加速度データと画像データを取得する例について説明してきたが、この発明は、スマート・フォンに限定されず、加速度を測定する機能とカメラ機能をもつ任意のデバイスを使用することができる。また、加速度センサ−以外にも、ジャイロ・センサにより加速度を測定するようにしてもよい。
【００６４】
また、加速度データと画像データをコンピュータに送信する技術は、ＷｉＦｉ以外の任意の無線通信を使用することができ、有線通信を使用してもよい。
【００６５】
また、上記実施例では、スマート・フォンの加速度センサとカメラ機能のデータを使用し、その後の処理は別のコンピュータに送って特徴量の抽出、あるいは位置の推定を行なうようにしたが、最近のスマート・フォンの処理能力や仕様に鑑みると、別のコンピュータで行なわれる処理の一部または全部をスマート・フォン上で行なうようにすることも可能である。
【００６６】
さらに、加速度データと画像データを処理するためのコンピュータは、特定のハードウェアやオペレーティング・システムには限定されず、任意のプラットフォームのコンピュータが使用可能である。
【符号の説明】
【００６７】
１０８・・・スマート・フォン
１１０・・・コンピュータ
２０４・・・ＣＰＵ
２０６・・・ＲＡＭ
２０８・・・ハードディスク・ドライブ
２１６・・・通信インターフェース
３０４・・・通信モジュール
３０６・・・sum計算ルーチン
３０８・・・DoGの計算&極値検出ルーチン
３１０・・・特徴量計算ルーチン
【図１】
2014027500.tif 000006
【図２】
2014027500.tif 000007
【図３】
2014027500.tif 000008
【図４】
2014027500.tif 000009
【図５】
2014027500.tif 000010
【図６】
2014027500.tif 000011
【図７】
2014027500.tif 000012
【図８】
2014027500.tif 000013
【図９】
2014027500.tif 000014
【図１０】
2014027500.tif 000015
【国際調査報告】
2014027500.tif 000016
2014027500.tif 000017