(57)【要約】  モバイルプラットフォームにおけるビジョンベーストラッキングシステムは、検出された線の群を使用して対象物をトラッキングする。トラッキングシステムは、トラッキングすべき対象物の、キャプチャされた画像内の線を検出する。線の群は、検出された線から形成される。線の群は、検出された線の交差点を計算し、交差点を使用して、接続された線を識別することによって形成され得、接続された線を使用して線の群が形成され得る。検出された線のグラフが構築され、交差点が識別され得る。興味のあるサブグラフが、接続を使用して生成され、線の群が、興味のあるサブグラフを用いて形成される。線の群が形成されると、線の群は、たとえば対象物の現在の画像内の線の群と対象物の前の画像内の線の群とを比較することによって、対象物をトラッキングするために使用される。
2014529823.tif 000002
【特許請求の範囲】
【請求項１】
トラッキングすべき対象物の画像をキャプチャするステップと、
前記対象物の前記画像内の複数の線を検出するステップと、
前記複数の線から線の群を形成するステップと、
前記線の群を使用して前記対象物をトラッキングするステップと
を含む、方法。
【請求項２】
前記線の群が、接続された線を含む、請求項1に記載の方法。
【請求項３】
前記接続された線が、閉じた形を形成する、請求項2に記載の方法。
【請求項４】
前記複数の線から前記線の群を形成するステップが、
前記複数の線のすべての交差点を計算するステップと、
前記交差点を使用して、接続された線を識別するステップと、
前記接続された線を用いて前記線の群を形成するステップと
を含む、請求項1に記載の方法。
【請求項５】
前記複数の線から前記線の群を形成するステップが、
前記複数の線からグラフを構築するステップと、
前記複数の線のすべての交差点を計算するステップと、
交差点の各ペア間の接続を使用して、興味のあるサブグラフを生成するステップと、
前記興味のあるサブグラフから前記線の群を形成するステップと
を含む、請求項1に記載の方法。
【請求項６】
前記対象物の参照モデルを前記興味のあるサブグラフとマッチングすることによって、前記トラッキングすべき対象物を検出するステップをさらに含む、請求項5に記載の方法。
【請求項７】
前記線の群を使用して前記対象物をトラッキングするステップが、前記対象物の参照モデルを前記興味のあるサブグラフとマッチングするステップを含む、請求項5に記載の方法。
【請求項８】
前記興味のあるサブグラフを生成するステップが、
前記グラフおよび得られた各サブグラフを、得られた各サブグラフが1つのサイクルを含むまで、繰返し2つに分割するステップと、
1つのサイクルを含む、得られたサブグラフを興味のあるサブグラフとして報告するステップと
を含む、請求項5に記載の方法。
【請求項９】
前記線の群を使用して前記対象物をトラッキングするステップが、前記線の群を使用して前記対象物の現在の画像と前記対象物の前の画像とを比較するステップを含む、請求項1に記載の方法。
【請求項１０】
カメラと、
前記カメラに接続されたプロセッサとを備え、前記プロセッサが、トラッキングすべき対象物の、前記カメラによってキャプチャされた画像内の複数の線を検出し、前記複数の線から線の群を形成し、前記線の群を使用して前記対象物をトラッキングするように構成される、
装置。
【請求項１１】
前記線の群が、接続された線を含む、請求項10に記載の装置。
【請求項１２】
前記接続された線が、閉じた形を形成する、請求項11に記載の装置。
【請求項１３】
前記プロセッサが、前記複数の線のすべての交差点を計算するように構成されることによって前記複数の線から前記線の群を形成し、前記交差点を使用して、接続された線を識別し、前記接続された線を用いて前記線の群を形成するように構成される、請求項10に記載の装置。
【請求項１４】
前記プロセッサが、前記複数の線からグラフを構築するように構成されることによって前記複数の線から前記線の群を形成し、前記複数の線のすべての交差点を計算し、交差点の各ペア間の接続を使用して興味のあるサブグラフを生成し、前記興味のあるサブグラフから前記線の群を形成するように構成される、請求項10に記載の装置。
【請求項１５】
前記プロセッサが、前記対象物の参照モデルを前記興味のあるサブグラフとマッチングするように構成されることによって、前記トラッキングすべき対象物を検出するようにさらに構成される、請求項14に記載の装置。
【請求項１６】
前記プロセッサが、前記対象物の参照モデルを前記興味のあるサブグラフとマッチングするように構成されることによって、前記線の群を使用して前記対象物をトラッキングするように構成される、請求項14に記載の装置。
【請求項１７】
前記プロセッサが、前記グラフおよび得られた各サブグラフを、得られた各サブグラフが1つのサイクルを含むまで、繰返し2つに分割するように構成されることによって前記興味のあるサブグラフを生成し、1つのサイクルを含む得られたサブグラフを興味のあるサブグラフとして報告するように構成される、請求項14に記載の装置。
【請求項１８】
前記プロセッサが、前記カメラによってキャプチャされた前記対象物の現在の画像と前記カメラによってキャプチャされた前記対象物の前の画像とを比較するように構成されることによって、前記線の群を使用して前記対象物をトラッキングするように構成される、請求項10に記載の装置。
【請求項１９】
トラッキングすべき対象物の画像をキャプチャするための手段と、
前記対象物の前記画像内の複数の線を検出するための手段と、
前記複数の線から線の群を形成するための手段と、
前記線の群を使用して前記対象物をトラッキングするための手段と
を含む、装置。
【請求項２０】
前記線の群が、閉じた形を形成する接続された線を含む、請求項19に記載の装置。
【請求項２１】
前記複数の線から前記線の群を形成するための前記手段が、
前記複数の線のすべての交差点を計算するための手段と、
前記交差点を使用して、接続された線を識別するための手段と、
前記接続された線を用いて前記線の群を形成するための手段と
を含む、請求項19に記載の装置。
【請求項２２】
前記複数の線から前記線の群を形成するための前記手段が、
前記複数の線からグラフを構築するための手段と、
前記複数の線のすべての交差点を計算するための手段と、
交差点の各ペア間の接続を使用して、興味のあるサブグラフを生成するための手段と、
前記興味のあるサブグラフから前記線の群を形成するための手段と
を含む、請求項19に記載の装置。
【請求項２３】
前記線の群を使用して前記対象物をトラッキングするための前記手段が、前記線の群を使用して前記対象物の現在の画像と前記対象物の前の画像とを比較するための手段を含む、請求項19に記載の装置。
【請求項２４】
プログラムコードを記憶した非一時的コンピュータ可読記録媒体であって、
トラッキングすべき対象物の画像をキャプチャするためのプログラムコードと、
前記対象物の前記画像内の複数の線を検出するためのプログラムコードと、
前記複数の線から線の群を形成するためのプログラムコードと、
前記線の群を使用して前記対象物をトラッキングするためのプログラムコードと
を含む、非一時的コンピュータ可読記録媒体。
【請求項２５】
前記線の群が、閉じた形を形成する接続された線を含む、請求項24に記載の非一時的コンピュータ可読記録媒体。
【請求項２６】
前記複数の線から前記線の群を形成するための前記プログラムコードが、
前記複数の線のすべての交差点を計算するためのプログラムコードと、
前記交差点を使用して、接続された線を識別するためのプログラムコードと、
前記接続された線を用いて前記線の群を形成するためのプログラムコードと
を含む、請求項24に記載の非一時的コンピュータ可読記録媒体。
【請求項２７】
前記複数の線から前記線の群を形成するステップが、
前記複数の線からグラフを構築するためのプログラムコードと、
前記複数の線のすべての交差点を計算するためのプログラムコードと、
交差点の各ペア間の接続を使用して、興味のあるサブグラフを生成するためのプログラムコードと、
前記興味のあるサブグラフから前記線の群を形成するためのプログラムコードと
を含む、請求項24に記載の非一時的コンピュータ可読記録媒体。
【請求項２８】
前記線の群を使用して前記対象物をトラッキングするための前記プログラムコードが、前記線の群を使用して前記対象物の現在の画像と前記対象物の前の画像とを比較するためのプログラムコードを含む、請求項24に記載の非一時的コンピュータ可読記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、2012年3月9日に出願した「Line Tracking With Automatic Model Initialization by Graph Matching and Cycle Detection」と題する米国特許出願第13/416,721号の優先権を主張するものであり、その特許出願は、ひいては、米国特許法第119条の下で、2011年9月2日に出願した「Line Tracking With Automatic Model Initialization by Graph Matching and Cycle Detection」と題する米国仮出願第61/530,907号の優先権を主張するものであり、両出願は、本明細書の譲受人に譲渡され、参照により本明細書に組み込まれる。
【０００２】
本明細書で説明する主題の実施形態は、一般に、位置およびトラッキングに関し、より詳細には、ビジョンベーストラッキングに関する。
【背景技術】
【０００３】
ビジョンベーストラッキングシステムは、参照画像に対するカメラの位置および方位(姿勢)を推定するために使用される。参照画像は、通常、そのカメラまたは他のカメラでキャプチャされた現実世界環境の一部分の複数の画像(フレームと呼ばれることがある)に基づく。決定されたカメラの姿勢によって、限定はしないが、拡張現実などのアプリケーションが、実行され得る。正確でロバストなトラッキングは、仮想拡張と現実世界環境との間の緊密なレジストレーションを可能にするので、拡張現実などのアプリケーションにとって特に重要である。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ビジョンベーストラッキングの1つのタイプは、画像内の線を検出してトラッキングすることに基づく。線トラッキングアルゴリズムは、たとえば、トラッキングされている対象物が非常に少ないテクスチャを有する場合に助けになる。しかしながら、従来の線トラッキングは、多くの拡張現実アプリケーションとって望ましいロバストネスを欠いている。したがって、線トラッキングにおける改善が望ましい。
【課題を解決するための手段】
【０００５】
モバイルプラットフォームにおけるビジョンベーストラッキングシステムは、検出された線の群を使用して対象物をトラッキングする。トラッキングシステムは、トラッキングすべき対象物の、キャプチャされた画像内の線を検出する。線の群は、検出された線から形成される。線の群は、検出された線の交差点を計算し、交差点を使用して、接続された線を識別することによって形成され、接続された線を使用して線の群が形成され得る。検出された線のグラフが構築され、交差点が識別され得る。興味のあるサブグラフが接続を使用して生成され、線の群が興味のあるサブグラフを用いて形成される。線の群が形成されると、線の群は、たとえば対象物の現在の画像内の線の群と対象物の前の画像内の線の群とを比較することによって、対象物をトラッキングするために使用される。
【０００６】
一実施形態では、方法は、トラッキングすべき対象物の画像をキャプチャするステップと、対象物の画像内の複数の線を検出するステップと、複数の線から線の群を形成するステップと、線の群を使用して対象物をトラッキングするステップとを含む。
【０００７】
一実施形態では、装置は、カメラと、カメラに接続されたプロセッサとを含み、プロセッサは、トラッキングすべき対象物の、カメラによってキャプチャされた画像内の複数の線を検出し、複数の線から線の群を形成し、線の群を使用して対象物をトラッキングするように構成される。
【０００８】
一実施形態では、装置は、トラッキングすべき対象物の画像をキャプチャするための手段と、対象物の画像内の複数の線を検出するための手段と、複数の線から線の群を形成するための手段と、線の群を使用して対象物をトラッキングするための手段とを含む。
【０００９】
一実施形態では、プログラムコードを記憶した非一時的コンピュータ可読記録媒体は、トラッキングすべき対象物の画像をキャプチャするためのプログラムコードと、対象物の画像内の複数の線を検出するためのプログラムコードと、複数の線から線の群を形成するためのプログラムコードと、線の群を使用して対象物をトラッキングするためのプログラムコードとを含む。
【図面の簡単な説明】
【００１０】
【図１Ａ】本明細書で説明するロバストな方式で、ビジョンベース線トラッキングを実行可能なモバイルプラットフォームの前面部を示す図である。
【図１Ｂ】本明細書で説明するロバストな方式で、ビジョンベース線トラッキングを実行可能なモバイルプラットフォームの背面部を示す図である。
【図２】ビジョンベーストラッキングユニットの2つの主要構成要素を示す図である。
【図３】ビジョンベーストラッキングユニット内の線検出の構成要素を示す図である。
【図４】エッジ連結アルゴリズムを示す図である。
【図５】線フィッティングにおいて使用される線近似を示す図である。
【図６】ビジョンベーストラッキングユニット内の線トラッキングを示す図である。
【図７Ａ】線フィッティングのために処理されるいくつかのエッジを含む画像を示す図である。
【図７Ｂ】線フィッティングのために処理されるいくつかのエッジを含む画像を示す図である。
【図７Ｃ】線フィッティングのために処理されるいくつかのエッジを含む画像を示す図である。
【図８】線の群を使用して対象物をトラッキングする方法を示すフローの図である。
【図９】3点間の線を示す図である。
【図１０】頂点(vertices)A、B、CおよびD間の線を示す図である。
【図１１】サイクルの検出および分離を示す図である。
【図１２Ａ】エッジを示す元のグラフを示す図である。
【図１２Ｂ】抽出されたサイクルを示すグラフを示す図である。
【図１３】図10に類似するがエッジe1〜e4を標示する、頂点A、B、CおよびD間の線を示す図である。
【図１４】行列表現に基づくサイクル検出の一例として、4つの頂点間の5本の線を示す図である。
【図１５】図14に示すグラフを分離するステップを示す図である。
【図１６】線の群を使用して対象物をトラッキングすることができるモバイルプラットフォームのブロック図である。
【発明を実施するための形態】
【００１１】
図1Aおよび図1Bはそれぞれ、本明細書で説明するロバストな方式で、ビジョンベース線トラッキングを実行可能なモバイルプラットフォーム100の前面部および背面部を示す。筐体101、タッチスクリーンディスプレイであり得るディスプレイ102、ならびにスピーカ104およびマイクロフォン106を含むモバイルプラットフォーム100が示される。さらに、モバイルプラットフォーム100は、ビジョンベーストラッキングユニット112のために環境を撮像するカメラ110を含む。ビジョンベーストラッキングユニット112は線の群をトラッキングする。大半の従来の線トラッキングシステムの欠点の1つは、線が個別にトラッキングされ、そのことで、プロセスのロバストネスが制限されることである。線の群をトラッキングすることで、トラッキングプロセスのロバストネスが改善される。加えて、ビジョンベーストラッキングユニット112は、自動モデル初期化を使用して、トラッキングされる線の群を得ることができる。自動モデル初期化は、たとえば、グラフマッチングおよびサイクル検出であってよい。ビジョンベーストラッキングユニット112は、参照フリートラッキングおよび参照ベーストラッキングとともに使用され得る。
【００１２】
本明細書で使用される場合、モバイルプラットフォームは、セルラーもしくは他のワイヤレス通信デバイス、パーソナル通信システム(PCS)デバイス、パーソナルナビゲーションデバイス(PND)、個人情報マネージャ(PIM)、携帯情報端末(PDA)、または他の適したモバイルデバイスなどの任意のポータブル電子デバイスを指す。モバイルプラットフォームは、ナビゲーション測位信号など、ワイヤレス通信および/またはナビゲーション信号を受信することが可能であり得る。「モバイルプラットフォーム」という用語はまた、短距離ワイヤレス、赤外線、有線接続、または他の接続などによって、パーソナルナビゲーションデバイス(PND)と通信するデバイスを含むことを意図し、衛星信号受信、支援データ受信、および/または位置関連処理が、そのデバイスで生じるか、またはPNDで生じるかにかかわらない。また、「モバイルプラットフォーム」は、ビジョンベーストラッキングが可能であるワイヤレス通信デバイス、コンピュータ、ラップトップ、タブレットコンピュータなどを含む、すべての電子デバイスを含むことを意図する。
【００１３】
図2に示すように、ビジョンベーストラッキングユニット112は、線検出200およびトラッキング220の2つの主要構成要素を含む。図2および図3に示すように、線検出200は、初期化202と、エッジ検出204と、エッジ連結206と、線セグメントフィッティング208とを含む。図2および図6に示すトラッキング220は、図2に示すように、局所探索を実行すること、エッジセットの分布を計算すること、およびフレーム間トラッキングを行うことを含む。線検出200における初期化202は、トラッキングすべき対象物の入力画像を提供することを含む。エッジ検出204は、たとえば、当業界でよく知られているCannyエッジ検出器、Sobelエッジ検出器、Prewittエッジ検出器、または他の適正なエッジ検出器によって実行され得る。次いで、エッジマップの形でエッジ点のセットを作成するために、非最大値抑制によるエッジシニングが実行される。次いで、エッジ連結206が実行され、エッジセグメントを得ることができる。例として、図4は、使用され得るエッジ連結アルゴリズムを示す。エッジ連結アルゴリズムは、エッジマップ内の各エッジ点を調査し、局所近傍のエッジマップを調査してこの領域内の他のエッジ点を識別することによってエッジセグメントIDを有する点を標示する。例として、局所近傍は、エッジ点周りの8×8ピクセル領域であってよい。次いで、複数の線セグメントによってエッジを表示するために、線セグメントフィッティング208が実行される。例として、図5は、点AとBとの間の曲線α上の線フィッティングを示す。点AとBとの間の曲線α上の各点Cに対して、アルゴリズムは、最初に、線CDが線ABに垂直になるように、または言い換えれば<AB，CD>=0であるように、線AB上の点Dを識別する。距離CDが留意され、最大距離CDをもたらす点Cが認識され、図5の点C*で表示される。最大距離、すなわち点C*と、対応する点D*との間の最大距離が、適切に事前選択されたしきい値Tより小さい場合、線ABは、曲線αの良い近似とみなされる。一方、最大距離がしきい値Tより大きい場合、個々の線AC*およびC*Bの各々に対して、アルゴリズムが繰り返される。
【００１４】
図6は、ビジョンベーストラッキングユニット内の線トラッキング220を示す。前のフレームに対する線検出200の段階で識別された各線セグメントに対して、局所探索領域が、現在のフレーム内で識別される(222)。図7Aは、局所探索領域250に伴っていくつかのエッジを含む画像を示しており、その領域は、エッジ領域L周りの8×8ピクセル領域であってよい。次に、局所探索領域内の各ピクセルに対して、勾配の大きさおよび方位が、現在の画像に基づいて計算される(224)。一実施形態では、画像勾配を計算するために、Canny演算子(Canny operator)が使用され得る。代替として、SobelカーネルもしくはPrewittカーネル、または等価な勾配計算カーネルが、画像勾配を計算するために使用され得る。非最大値抑制が、勾配マップ上で付加的に実行され得る。勾配の方位および勾配の大きさの分布が計算され、線セグメントLに類似する分布を有する、サーチ領域内のエッジ点のサブセットを識別するために使用される(224)。図7Bに示すように、選択されたエッジ点のサブセットの支配的方向を計算して最も近いエッジ候補を選択するために、線形回帰技法が使用され得る(226)。一実施形態では、エッジ点のサブセットの支配的方向を識別するために、主成分分析(PCA)が使用され得る。図7Cに示すように、線セグメントが、現在のフレーム内のエッジ点のサブセット上でフィッティングされ(228)、フィッティングエラーを最小にするために、線セグメントのそのパラメータがさらに洗練される(230)。
【００１５】
線トラッキングシステムのロバストネスを高めるために、線が群に組み合わされて、次にトラッキングされ得るより良い記述を形成する。図8は、線の群を使用して対象物をトラッキングする方法を示すフローである。図8に示すように、トラッキングすべき対象物の画像が、たとえば、モバイルプラットフォーム100でキャプチャされたビデオまたは画像の複数のフレームのうちの1つとしてキャプチャされる(302)。たとえば図3で上述するように、または任意の他の所望の方式で、対象物の画像内の複数の線が検出される(304)。たとえば図6で上述するように、または任意の他の所望の方式で、線の群が複数の線から形成され(306)、1つのフレームから次のフレームにかけて対象物をトラッキングするために線の群が使用される(308)。線の群は、たとえば、正方形、長方形、またはサイクル(cycle)など、閉じた形で接続された線であってよい。
【００１６】
線の群は、複数の線のすべての交差点を計算し、交差点を使用して接続された線を識別することによって形成され得る(306)。たとえば、線の群は、複数の線からグラフを構築し、複数の線のすべての交差点を計算し、交差点の各ペア間の接続を使用して興味のあるサブグラフを生成することによって形成され得る。交差点が識別されると、線のセットに対するグラフGが、
【００１７】
【数１】
2014529823.tif 000003
【００１８】
として構築され得る。
【００１９】
ここで、Tは適切に選択されたしきい値である。例として、図9は、点A、BおよびCを、線(A，B)および線(A，C)とともに示す。このグラフに対する行列Gは、
【００２０】
【数２】
2014529823.tif 000004
【００２１】
として記述され得る。
【００２２】
例として、図10は、頂点A、B、CおよびDを有する別の可能なサブグラフを示しており、そのサブグラフは、
【００２３】
【数３】
2014529823.tif 000005
【００２４】
で記述される。
【００２５】
次いで、興味のあるサブグラフが、興味のある線の群を使用して形成され得る。トラッキングの観点から興味のあるサブグラフは、三角形、正方形、長方形、一般的な多角形、またはサイクルであってよい。
【００２６】
線の群が、たとえば興味のあるサブグラフとして形成されると、フレームごとに線の群をトラッキングするために、マッチング技法が使用され得る(308)。マッチングは、参照によって実行されることも、参照なしに実行されることもある。
【００２７】
トラッキングすべき対象物の事前知識が利用可能である場合、この情報を使用することができ、正確なサブグラフおよび対象物トラッキングが、現在の入力フレームを知られている興味のある対象物とマッチングすることによって実行され得る。例として、対象物トラッキングを助けることができる事前知識のタイプは、2Dトラッキングの場合のトラッキングすべき対象物の参照画像、3Dトラッキングの場合の対象物の参照3Dモデル、3D対象物の異なるビューからの一連のフレーム、またはさらには2Dモデルもしくは3Dモデルのエッジマップであってよい。
【００２８】
事前知識がない場合に、トラッキングは、後続のフレームを比較することによって、すなわち現在のフレームを前のフレームと比較することによって実行され、前のフレームは、直前のフレームかまたは複数のフレームだけ現在のフレームより前のフレームのいずれかであってよい。事前知識がない場合、サイクル検出が実行されてよく、以下で説明するように、グラフ内の閉じた経路が、興味のある領域の境界であるとみなされる。
【００２９】
マッチングの段階では、現在の画像内で検出された線のセットが与えられると、すべての交差点が計算される。交差点の各ペア間の接続を考慮することによって、グラフが構築される。次いで、興味のあるサブグラフを検出するためにモデルの初期化が行われ、検出されたサブグラフを、モデルフレームのサブグラフ(参照ベーストラッキングの場合)、および前のフレームのサブグラフ(参照フリートラッキングの場合)と、比較するために、正確なサブグラフのグラフマッチングが使用される。
【００３０】
加えて、線の群は、サイクルを検出するために、共に組み合わされ得る。サイクル検出は、1つのグラフおよび得られた各サブグラフを、得られた各サブグラフが1つのサイクルを含むまで、繰返し2つに分割することを含む。1つのサイクルを含む、得られたサブグラフが、興味のあるサブグラフとして報告される。サイクル検出を図11に示しており、図は4サイクルを含むグラフを示しており、そのグラフは2つに分割され、それにより1サイクルと3サイクルとを含むサブグラフを作成する。3サイクルを有するサブグラフは、再び分轄されて追加のサブグラフを作成し、追加のサブグラフは、各サブグラフがただ1つのサイクルを有するまで、さらに分割される。次いで、1サイクルを含むサブグラフのすべてが、結果として戻される。このプロセスの2つの主要構成要素が、以下で示すサイクル検出およびグラフ分割である。例として、図12Aおよび図12Bは、それぞれ、エッジを示す元のグラフと、点線および鎖線で特定された、抽出されたサイクルを示すグラフとを示す。
【００３１】
サイクル検出は、様々な方法で実行され得る。議論を円滑にするために、H0で頂点の空間を表すこととする。たとえば、図10に示すサブグラフを参照すると、H0は、
【００３２】
【数４】
2014529823.tif 000006
【００３３】
のように、頂点のセット{A，B，C，D}のべき集合である。
【００３４】
さらに、図10に類似するが、
【００３５】
【数５】
2014529823.tif 000007
【００３６】
のようにエッジe1〜e4を標示する図13に示すように、H1でエッジのセット{e1，e2，e3，e4}のべき集合を表すこととする。
【００３７】
サイクル検出はまた、
∂:H1→H0
∂(e1)=A+D
∂(e1+e2)=∂(e1)+∂(e2)=A+D+D+C=A+C      eq.6
として定義される境界演算子(boundary operator)∂を使用して実行され得る。
【００３８】
したがって、境界演算子の下で、サイクルc∈H1は、
cycle space={c∈H1|∂(c)=0}      eq.7
として定義され得る。
【００３９】
サイクルCの空間はベクトル空間であり、かつ∂の零空間であり、サイクルの数は、零に等しい∂の固有値の数に等しいことに留意されたい。
【００４０】
例として、図13に示すグラフに対して、境界演算子∂は、∂(e)=Deとして数学的に表現され得、ここで、行列Dは、
【００４１】
【数６】
2014529823.tif 000008
【００４２】
で与えられる。
【００４３】
たとえば、
【００４４】
【数７】
2014529823.tif 000009
【００４５】
この記述に基づいて、エッジe1、e2、e3およびe4は、2を法とする加算の下で、
【００４６】
【数８】
2014529823.tif 000010
【００４７】
であるので、サイクルを形成する。
【００４８】
例として、図14は、4つの頂点の間の5本の線を示す。サイクルの数は、零に等しいラプラシアン行列の固有値の数を調べることによって発見され得る。この例では、ラプラシアン行列L=DTDは、
【００４９】
【数９】
2014529823.tif 000011
【００５０】
によって与えられる。
【００５１】
式11に示すように、図14に示すサイクルのグラフに対して2つの零固有値が存在し、したがって、2つのサイクルが存在する。したがって、図14に示すグラフは、図15に示すように分割されるべきであり、分割は、境界点において発生する。グラフ分割に対する適切な実装形態は、参照により本明細書に組み込まれる、Harish Chintakunta、Hamid Krim、DivideおよびConquer、「Localizing Coverage holes in Sensor Networks」、IEEE SECON、2010年6月、に記載されている。グラフ分割が実行された後、各サブグラフ内の閉じた経路が発見され、興味のある領域の境界であるとみなされる。次いで、これらの得られたサイクルは、トラッキングプロセスにおいて使用され得る。
【００５２】
図16は、線の群を使用して対象物をトラッキングすることができるモバイルプラットフォーム100のブロック図である。モバイルプラットフォーム100は、カメラ110、ならびにカメラ110によってキャプチャされた画像を表示することができるディスプレイ102を含むユーザインターフェース150を含む。また、ユーザインターフェース150は、キーパッド152、または、ユーザが情報をモバイルプラットフォーム100に入力することができる他の入力デバイスを含み得る。必要に応じて、キーパッド152は、タッチセンサを有するディスプレイ102に仮想キーパッドを組み込むことによって省かれてもよい。また、ユーザインターフェース150は、たとえばモバイルプラットフォームが携帯電話である場合には、マイクロフォン106とスピーカ104を含み得る。マイクロフォン106は、音声注釈を入力するために使用され得る。当然ながら、モバイルプラットフォーム100は、本開示に関係しない他の要素を含み得る。
【００５３】
モバイルプラットフォーム100はまた、カメラ110およびユーザインターフェース150に接続され、それらと通信する制御ユニット160、ならびに存在可能な他のシステムを含む。たとえば、加速度計、ジャイロスコープ、磁力計などのモーションセンサおよび/または位置センサが存在して、トラッキングにおいて使用される追加の情報を提供するために使用され得る。制御ユニット160は、上述のように、カメラ110からデータを受けて処理する。制御ユニット160は、バス160b、プロセッサ161および関連するメモリ164、ハードウェア162、ソフトウェア165、ならびにファームウェア163によって提供され得る。モバイルプラットフォーム100は、図1に示すビジョンベーストラッキングユニット112を構成し、上述のように動作する線検出ユニット172、線群化ニット174、およびトラッキングユニット176を含む。線検出ユニット172、線群化ユニット174、およびトラッキングユニット176は、説明を簡単にするためにプロセッサ161とは別に示され、別個のものであるが、単一のユニットであってもよく、かつ/またはプロセッサ161の中で実行されるソフトウェア165内の命令に基づいてプロセッサ161の中で実施されてもよい。本明細書で使用される場合、プロセッサ161ならびに線検出ユニット172、線群化ユニット174、およびトラッキングユニット176のうちの1つまたは複数は、1つまたは複数のマイクロプロセッサ、組込みプロセッサ、制御器、特定用途向け集積回路(ASIC)、デジタルシグナルプロセッサ(DPS)などを、必ずしも必要ではないが、含むことができる。プロセッサという用語は、特定のハードウェアではなく、システムによって実施される機能を説明するように考えられている。さらに、本明細書で使用する「メモリ」という用語は、長期メモリ、短期メモリ、またはモバイルプラットフォームに関連する他のメモリを含む任意の種類のコンピュータ記憶媒体を指し、いかなる特定の種類のメモリ、もしくはメモリの数、またはメモリが記憶される媒体の種類に限定されない。
【００５４】
本明細書で説明する方法は、用途に応じて様々な手段によって実現され得る。たとえば、これらの方法は、ハードウェア162、ファームウェア163、ソフトウェア165、またはそれらの任意の組合せで実施されてもよい。ハードウェアの実装形態の場合、処理ユニットは、本明細書で説明された機能を実行するように設計された、1つもしくは複数の特定用途向け集積回路(ASIC)、デジタル信号プロセッサ(DSP)、デジタル信号プロセッシングデバイス(DSPD)、プログラマブル論理デバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子デバイス、他の電子ユニット、またはそれらの組合せ内で実装されてもよい。
【００５５】
ファームウェアおよび/またはソフトウェア実装形態に関して、これらの方法は、本明細書で説明する機能を実行するモジュール(たとえば、プロシージャ、関数など)によって実装され得る。本明細書で説明する方法を実装する際に、命令を有形に具現化する任意の機械可読媒体が使用され得る。たとえば、ソフトウェアコードがメモリ164に記憶され、プロセッサ161によって実行されてもよい。メモリは、プロセッサ161の内部に実装されてもよく、または、プロセッサ161の外部に実装されてもよい。
【００５６】
ファームウェアおよび/またはソフトウェアに実装する場合、機能は、コンピュータ可読記録媒体に1つまたは複数の命令またはコードとして記憶され得る。例には、データ構造で符号化された非一時的コンピュータ可読記録媒体、およびコンピュータプログラムで符号化されたコンピュータ可読記録媒体を含める。コンピュータ可読記録媒体には、物理的コンピュータ記憶媒体が含まれる。記憶媒体は、コンピュータによってアクセスされ得る任意の入手可能な媒体であり得る。限定ではなく、例として、そのようなコンピュータ可読記録媒体は、RAM、ROM、フラッシュメモリ、EEPROM、CD-ROMもしくは他の光ディスクストレージ、磁気ディスクストレージもしくは他の磁気記憶デバイス、または所望のプログラムコードを命令またはデータ構造の形で記憶するのに使用することができ、かつコンピュータによってアクセスすることのできる任意の他の媒体を備えてよく、本明細書で使用するディスク(diskおよびdisc)には、コンパクトディスク(disc)(CD)、レーザディスク(disc)、光ディスク(disc)、デジタル多用途ディスク(disc)(DVD)、フロッピー（登録商標）ディスク(disk)、およびブルーレイディスク(disc)が含まれ、ディスク(disk)は通常、データを磁気的に再生するが、ディスク(disc)はデータをレーザによって光学的に再生する。上記の組合せもコンピュータ可読記録媒体の範囲内に含めるべきである。
【００５７】
説明のために本発明を特定の実施形態に関連して示したが、本発明はそれらの実施形態に限定されない。本発明の範囲から逸脱することなく様々な適合および改変がなされてもよい。したがって、添付の特許請求の範囲における趣旨および範囲は、上記の説明に限定されるべきではない。
【符号の説明】
【００５８】
100  モバイルプラットフォーム
101  筐体
102  ディスプレイ
104  スピーカ
106  マイクロフォン
110  カメラ
112  ビジョンベーストラッキングユニット
150  ユーザインターフェース
152  キーパッド
160  制御ユニット
160b  バス
161  プロセッサ
162  ハードウェア
163  ファームウェア
164  メモリ
165  ソフトウェア
172  線検出ユニット
174  線群化ユニット
176  トラッキングユニット
200  線検出
202  初期化
204  エッジ検出
206  エッジ連結
208  線セグメントフィッティング
220  トラッキング
250  局所探索領域
【図１Ａ】
2014529823.tif 000012
【図１Ｂ】
2014529823.tif 000013
【図２】
2014529823.tif 000014
【図３】
2014529823.tif 000015
【図４】
2014529823.tif 000016
【図５】
2014529823.tif 000017
【図６】
2014529823.tif 000018
【図７Ａ】
2014529823.tif 000019
【図７Ｂ】
2014529823.tif 000020
【図７Ｃ】
2014529823.tif 000021
【図８】
2014529823.tif 000022
【図９】
2014529823.tif 000023
【図１０】
2014529823.tif 000024
【図１１】
2014529823.tif 000025
【図１２Ａ】
2014529823.tif 000026
【図１２Ｂ】
2014529823.tif 000027
【図１３】
2014529823.tif 000028
【図１４】
2014529823.tif 000029
【図１５】
2014529823.tif 000030
【図１６】
2014529823.tif 000031
【手続補正書】
【提出日】平成25年6月25日(2013.6.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
トラッキングすべき対象物の画像をキャプチャするステップと、
前記対象物の前記画像内の複数の線を検出するステップと、
前記複数の線のすべての交差点を計算するステップと、
前記交差点を使用して、接続された線を識別するステップと、
前記複数の線の中の前記接続された線から線の群を形成するステップと、
前記線の群を使用して前記対象物をトラッキングするステップと
を含む、方法。
【請求項２】
前記線の群が、接続された線を含む、請求項1に記載の方法。
【請求項３】
前記接続された線が、閉じた形を形成する、請求項2に記載の方法。
【請求項４】
前記複数の線から前記線の群を形成するステップが、
前記複数の線からグラフを構築するステップと、
交差点の各ペア間の接続を使用してサブグラフを生成するステップと、
前記サブグラフから前記線の群を形成するステップと
を含む、請求項1に記載の方法。
【請求項５】
前記対象物の参照モデルを前記サブグラフとマッチングすることによって、前記トラッキングすべき対象物を検出するステップをさらに含む、請求項4に記載の方法。
【請求項６】
前記線の群を使用して前記対象物をトラッキングするステップが、前記対象物の参照モデルを前記サブグラフとマッチングするステップを含む、請求項4に記載の方法。
【請求項７】
前記サブグラフを生成するステップが、
前記グラフおよび得られた各サブグラフを、得られた各サブグラフが1つのサイクルを含むまで、繰返し2つに分割するステップと、
1つのサイクルを含む、得られたサブグラフをサブグラフとして報告するステップと
を含む、請求項4に記載の方法。
【請求項８】
前記線の群を使用して前記対象物をトラッキングするステップが、前記線の群を使用して前記対象物の現在の画像と前記対象物の前の画像とを比較するステップを含む、請求項1に記載の方法。
【請求項９】
カメラと、
前記カメラに接続されたプロセッサとを備え、前記プロセッサが、トラッキングすべき対象物の、前記カメラによってキャプチャされた画像内の複数の線を検出し、前記複数の線のすべての交差点を計算し、前記交差点を使用して、接続された線を識別し、前記複数の線の中の前記接続された線から線の群を形成し、前記線の群を使用して前記対象物をトラッキングするように構成される、装置。
【請求項１０】
前記線の群が、接続された線を含む、請求項9に記載の装置。
【請求項１１】
前記接続された線が、閉じた形を形成する、請求項10に記載の装置。
【請求項１２】
前記プロセッサが、前記複数の線からグラフを構築するように構成されることによって前記複数の線から前記線の群を形成し、交差点の各ペア間の接続を使用してサブグラフを生成し、前記サブグラフから前記線の群を形成するように構成される、請求項9に記載の装置。
【請求項１３】
前記プロセッサが、前記対象物の参照モデルを前記サブグラフとマッチングするように構成されることによって、前記トラッキングすべき対象物を検出するようにさらに構成される、請求項12に記載の装置。
【請求項１４】
前記プロセッサが、前記対象物の参照モデルを前記サブグラフとマッチングするように構成されることによって、前記線の群を使用して前記対象物をトラッキングするように構成される、請求項12に記載の装置。
【請求項１５】
前記プロセッサが、前記グラフおよび得られた各サブグラフを、得られた各サブグラフが1つのサイクルを含むまで、繰返し2つに分割するように構成されることによって前記サブグラフを生成し、1つのサイクルを含む得られたサブグラフをサブグラフとして報告するように構成される、請求項12に記載の装置。
【請求項１６】
前記プロセッサが、前記カメラによってキャプチャされた前記対象物の現在の画像と前記カメラによってキャプチャされた前記対象物の前の画像とを比較するように構成されることによって、前記線の群を使用して前記対象物をトラッキングするように構成される、請求項9に記載の装置。
【請求項１７】
トラッキングすべき対象物の画像をキャプチャするための手段と、
前記対象物の前記画像内の複数の線を検出するための手段と、
前記複数の線のすべての交差点を計算するための手段と、
前記交差点を使用して、接続された線を識別するための手段と、
前記複数の線の中の前記接続された線から線の群を形成するための手段と、
前記線の群を使用して前記対象物をトラッキングするための手段と
を含む、装置。
【請求項１８】
前記線の群が、閉じた形を形成する接続された線を含む、請求項17に記載の装置。
【請求項１９】
前記複数の線から前記線の群を形成するための前記手段が、
前記複数の線からグラフを構築するための手段と、
交差点の各ペア間の接続を使用してサブグラフを生成するための手段と、
前記サブグラフから前記線の群を形成するための手段と
を含む、請求項17に記載の装置。
【請求項２０】
前記線の群を使用して前記対象物をトラッキングするための前記手段が、前記線の群を使用して前記対象物の現在の画像と前記対象物の前の画像とを比較するための手段を含む、請求項17に記載の装置。
【請求項２１】
プログラムコードを記憶した非一時的コンピュータ可読記録媒体であって、
トラッキングすべき対象物の画像をキャプチャするためのプログラムコードと、
前記対象物の前記画像内の複数の線を検出するためのプログラムコードと、
前記複数の線のすべての交差点を計算するためのプログラムコードと、
前記交差点を使用して、接続された線を識別するためのプログラムコードと、
前記複数の線から線の群を形成するためのプログラムコードと、
前記線の群を使用して前記対象物をトラッキングするためのプログラムコードと
を含む、非一時的コンピュータ可読記録媒体。
【請求項２２】
前記線の群が、閉じた形を形成する接続された線を含む、請求項21に記載の非一時的コンピュータ可読記録媒体。
【請求項２３】
前記複数の線から前記線の群を形成するステップが、
前記複数の線からグラフを構築するためのプログラムコードと、
交差点の各ペア間の接続を使用してサブグラフを生成するためのプログラムコードと、
前記サブグラフから前記線の群を形成するためのプログラムコードと
を含む、請求項21に記載の非一時的コンピュータ可読記録媒体。
【請求項２４】
前記線の群を使用して前記対象物をトラッキングするための前記プログラムコードが、前記線の群を使用して前記対象物の現在の画像と前記対象物の前の画像とを比較するためのプログラムコードを含む、請求項21に記載の非一時的コンピュータ可読記録媒体。
【国際調査報告】
2014529823.tif 000032
2014529823.tif 000033
2014529823.tif 000034