(57)【要約】【課題】グラフ理論を用いて映像データ中の対象物を精度よく追跡可能にする。【解決手段】グラフ生成部２１は、映像データを構成する複数のフレームから検出された複数の対象物それぞれをノードとし、連続する２つのフレーム間で対象物を結ぶエッジを設けて追跡グラフを生成する。ベクトル計算部２２は、対象フレームから検出された対象物と、対象フレームの前のフレームから検出された対象物との対応関係に基づき、対象フレームから検出された対象物の速度ベクトルを計算する。コスト計算部２３は、速度ベクトルに基づき、追跡グラフにおける対象フレームと対象フレームの次のフレームとの間で対象物を結ぶエッジのコストを計算する。対応特定部２４は、追跡グラフ及びコストに基づき、対象フレームと次のフレームとの間の対象物の対応関係を特定する。【選択図】図１
2019095975.tif 000002
【特許請求の範囲】
【請求項１】
映像データを構成する複数のフレームから検出された複数の対象物それぞれをノードとし、連続する２つのフレーム間で対象物を結ぶエッジを設けて追跡グラフを生成するグラフ生成部と、
前記複数のフレームのうち対象フレームから検出された対象物と、前記対象フレームの前のフレームから検出された対象物との対応関係に基づき、前記対象フレームから検出された対象物の速度ベクトルを計算するベクトル計算部と、
前記ベクトル計算部によって計算された速度ベクトルに基づき、前記追跡グラフにおける前記対象フレームと前記対象フレームの次のフレームとの間で対象物を結ぶエッジのコストを計算するコスト計算部と、
前記追跡グラフと、前記コスト計算部によって計算された前記コストとに基づき、前記対象フレームと前記次のフレームとの間の対象物の対応関係を特定する対応特定部と
を備える追跡装置。
【請求項２】
前記コスト計算部は、前記速度ベクトルから特定される位置に近い前記次のフレームにおける対象物を表すノードと結ばれたエッジほど低くなるようにコストを計算し、
前記対応特定部は、前記コストが低いエッジを優先して選択することにより、前記対応関係を特定する
請求項１に記載の追跡装置。
【請求項３】
前記ベクトル計算部は、前記対象フレームと前記次のフレームとの間の対象物の対応関係が特定されると、前記次のフレームを新たな対象フレームとして、前記新たな対象フレームから検出された対象物の速度ベクトルを計算する
請求項１又は２に記載の追跡装置。
【請求項４】
前記ベクトル計算部は、前記対象フレームから検出された対象物の加速度ベクトルを計算し、
前記コスト計算部は、前記加速度ベクトルに基づき、前記エッジのコストを計算する
請求項１から３までのいずれか１項に記載の追跡装置。
【請求項５】
前記コスト計算部は、前記速度ベクトル及び前記加速度ベクトルから特定される位置に近い前記次のフレームにおける対象物と結ばれたエッジほど低くなるようにコストを計算し、
前記対応特定部は、前記コストが低いエッジを優先して選択することにより、前記対応関係を特定する
請求項４に記載の追跡装置。
【請求項６】
映像データを構成する複数のフレームから検出された複数の対象物それぞれをノードとし、連続する２つのフレーム間で対象物を結ぶエッジを設けて追跡グラフを生成するグラフ生成処理と、
前記複数のフレームのうち対象フレームから検出された対象物と、前記対象フレームの前のフレームから検出された対象物との対応関係に基づき、前記対象フレームから検出された対象物の速度ベクトルを計算するベクトル計算処理と、
前記ベクトル計算処理によって計算された速度ベクトルに基づき、前記追跡グラフにおける前記対象フレームと前記対象フレームの次のフレームとの間で対象物を結ぶエッジのコストを計算するコスト計算処理と、
前記追跡グラフと、前記コスト計算処理によって計算された前記コストとに基づき、前記対象フレームと前記次のフレームとの間の対象物の対応関係を特定する対応特定処理と
をコンピュータに実行させる追跡プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、映像データから検出された人を追跡する技術に関する。
【背景技術】
【０００２】
監視カメラといった撮影装置によって取得された映像データに映っている人等の対象物を追跡する追跡技術がある。追跡技術では、映像データを構成する複数のフレームから検出された対象物について、フレーム間での対応関係が特定され、対象物が追跡される。
【０００３】
追跡技術としてグラフ理論を用いた方式がある（非特許文献１参照）。グラフ理論を用いた方式では、検出された物体が対象物である確率と、映像データを構成するフレーム間で対象物が同一である確率といった情報をグラフのエッジのコストとして、最小費用問題を解くことにより対象物の追跡が行なわれる。最小費用問題を解く場合には、グラフを構成する全ての辺のコストが予め分かっている必要がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｐｉｒｓｉａｖａｓｈ，  Ｈａｍｅｄ，  Ｄｅｖａ  Ｒａｍａｎａｎ，  ａｎｄ  Ｃｈａｒｌｅｓｓ  Ｃ．  Ｆｏｗｌｋｅｓ．  “Ｇｌｏｂａｌｌｙ−ｏｐｔｉｍａｌ  ｇｒｅｅｄｙ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔｒａｃｋｉｎｇ  ａ  ｖａｒｉａｂｌｅ  ｎｕｍｂｅｒ  ｏｆ  ｏｂｊｅｃｔｓ．”  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ  ａｎｄ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ  （ＣＶＰＲ），  ２０１１  ＩＥＥＥ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ．  ＩＥＥＥ，  ２０１１．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来のグラフ理論を用いた追跡技術では、グラフを構成する全ての辺のコストが予め分かっている必要があったため、過去の対象物の移動を考慮したコストの計算ができなかった。そのため、コストが適切に設定されず、精度よく対象物を追跡することができなかった。
この発明は、グラフ理論を用いて精度よく対象物を追跡可能にすることを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係る追跡装置は、
映像データを構成する複数のフレームから検出された複数の対象物それぞれをノードとし、連続する２つのフレーム間で対象物を結ぶエッジを設けて追跡グラフを生成するグラフ生成部と、
前記複数のフレームのうち対象フレームから検出された対象物と、前記対象フレームの前のフレームから検出された対象物との対応関係に基づき、前記対象フレームから検出された対象物の速度ベクトルを計算するベクトル計算部と、
前記ベクトル計算部によって計算された速度ベクトルに基づき、前記追跡グラフにおける前記対象フレームと前記対象フレームの次のフレームとの間で対象物を結ぶエッジのコストを計算するコスト計算部と、
前記追跡グラフと、前記コスト計算部によって計算された前記コストとに基づき、前記対象フレームと前記次のフレームとの間の対象物の対応関係を特定する対応特定部と
を備える。
【０００７】
前記コスト計算部は、前記速度ベクトルから特定される位置に近い前記次のフレームにおける対象物を表すノードと結ばれたエッジほど低くなるようにコストを計算し、
前記対応特定部は、前記コストが低いエッジを優先して選択することにより、前記対応関係を特定する。
【０００８】
前記ベクトル計算部は、前記対象フレームと前記次のフレームとの間の対象物の対応関係が特定されると、前記次のフレームを新たな対象フレームとして、前記新たな対象フレームから検出された対象物の速度ベクトルを計算する。
【０００９】
前記ベクトル計算部は、前記対象フレームから検出された対象物の加速度ベクトルを計算し、
前記コスト計算部は、前記加速度ベクトルに基づき、前記エッジのコストを計算する。
【００１０】
前記コスト計算部は、前記速度ベクトル及び前記加速度ベクトルから特定される位置に近い前記次のフレームにおける対象物と結ばれたエッジほど低くなるようにコストを計算し、
前記対応特定部は、前記コストが低いエッジを優先して選択することにより、前記対応関係を特定する。
【００１１】
この発明に係る追跡プログラムは、
映像データを構成する複数のフレームから検出された複数の対象物それぞれをノードとし、連続する２つのフレーム間で対象物を結ぶエッジを設けて追跡グラフを生成するグラフ生成処理と、
前記複数のフレームのうち対象フレームから検出された対象物と、前記対象フレームの前のフレームから検出された対象物との対応関係に基づき、前記対象フレームから検出された対象物の速度ベクトルを計算するベクトル計算処理と、
前記ベクトル計算処理によって計算された速度ベクトルに基づき、前記追跡グラフにおける前記対象フレームと前記対象フレームの次のフレームとの間で対象物を結ぶエッジのコストを計算するコスト計算処理と、
前記追跡グラフと、前記コスト計算処理によって計算された前記コストとに基づき、前記対象フレームと前記次のフレームとの間の対象物の対応関係を特定する対応特定処理と
をコンピュータに実行させる。
【発明の効果】
【００１２】
この発明では、対象フレームと前のフレームとの対応関係に基づき、対象フレームから検出された対象物の速度ベクトルを計算し、計算された速度ベクトルに基づき、対象フレームと次のフレームとの間のエッジのコストを計算する。そして、計算されたコストに基づき、対象フレームと次のフレームとの間の対応関係を特定する。過去の対象物の移動を考慮してコストが計算されるので、精度よく対象物を追跡可能になる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態１に係る追跡装置１０の構成図。
【図２】実施の形態１に係る追跡装置１０の全体的な動作のフローチャート。
【図３】実施の形態１に係る追跡グラフ４０の説明図。
【図４】実施の形態１に係るノード４１の他の例を示す図。
【図５】実施の形態１に係る速度ベクトル３４の説明図。
【図６】実施の形態１の効果の説明図。
【図７】変形例１に係る追跡装置１０の構成図。
【図８】実施の形態２の効果の説明図。
【発明を実施するための形態】
【００１４】
実施の形態１．
＊＊＊構成の説明＊＊＊
図１を参照して、実施の形態１に係る追跡装置１０の構成を説明する。
追跡装置１０は、プロセッサ１１と、メモリ１２と、ストレージ１３と、通信インタフェース１４とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１５】
プロセッサ１１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ１１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００１６】
メモリ１２は、データを一時的に記憶する記憶装置である。メモリ１２は、具体例としては、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００１７】
ストレージ１３は、データを保管する記憶装置である。ストレージ１３は、具体例としては、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、ストレージ１３は、ＳＤ（Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ，登録商標）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）といった可搬記録媒体であってもよい。
【００１８】
通信インタフェース１４は、外部の装置と通信するためのインタフェースである。通信インタフェース１４は、具体例としては、Ｅｔｈｅｒｎｅｔ（登録商標）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＨＤＭＩ（登録商標，Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）のポートである。
追跡装置１０は、通信インタフェース１４を介して、撮影装置１４１と、表示装置１４２とに接続されている。
【００１９】
追跡装置１０は、機能構成要素として、グラフ生成部２１と、ベクトル計算部２２と、コスト計算部２３と、対応特定部２４とを備える。追跡装置１０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ１３には、追跡装置１０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ１１によりメモリ１２に読み込まれ、プロセッサ１１によって実行される。これにより、追跡装置１０の各機能構成要素の機能が実現される。
【００２０】
図１では、プロセッサ１１は、１つだけ示されていた。しかし、プロセッサ１１は、複数であってもよく、複数のプロセッサ１１が、各機能を実現するプログラムを連携して実行してもよい。
【００２１】
＊＊＊動作の説明＊＊＊
図２から図６を参照して、実施の形態１に係る追跡装置１０の動作を説明する。
実施の形態１に係る追跡装置１０の動作は、実施の形態１に係る追跡方法に相当する。また、実施の形態１に係る追跡装置１０の動作は、実施の形態１に係る追跡プログラムの処理に相当する。
【００２２】
図２を参照して、実施の形態１に係る追跡装置１０の全体的な動作を説明する。
ここでは、時間的に前のフレーム３１から順に対象物３２間の対応関係を特定するものとして説明する。したがって、以下の説明では、あるフレーム３１の次のフレーム３１とは、あるフレーム３１の時間的に１つ後のフレーム３１であり、あるフレーム３１の前のフレーム３１とは、あるフレーム３１の時間的に１つ前のフレーム３１である。
しかし、時間的に後のフレーム３１から順に対象物３２間の対応関係を特定することも可能である。この場合には、あるフレーム３１の次のフレーム３１とは、あるフレーム３１の時間的に１つ前のフレーム３１であり、あるフレーム３１の前のフレーム３１とは、あるフレーム３１の時間的に１つ後のフレーム３１である。
【００２３】
（図２のステップＳ１：グラフ生成処理）
グラフ生成部２１は、映像データ３０を構成する複数のフレーム３１から検出された複数の対象物３２それぞれをノード４１とし、連続する２つのフレーム３１間で対象物３２を結ぶエッジ４２を設けて追跡グラフ４０を生成する。
具体的には、グラフ生成部２１は、通信インタフェース１４を介して、撮影装置１４１から映像データ３０を取得する。グラフ生成部２１は、取得された映像データ３０を構成する各フレーム３１から人等の対象物３２を抽出する。対象物３２は、人に限らず、鞄といった物体であってもよい。グラフ生成部２１は、図３に示すように、抽出された対象物３２をノード４１とし、連続する２つのフレーム間で対象物３２を結ぶエッジ４２をノード４１間に設けて、追跡グラフ４０を生成する。また、グラフ生成部２１は、開始用のノードｓと、終了用のノードｔとを設け、ノードｓと各ノード４１との間と、ノードｔと各ノード４１との間とにもエッジ４２を設ける。グラフ生成部２１は、各エッジ４２を対象として、対象のエッジ４２が繋ぐ２つのノード４１が表す対象物３２の特徴の一致度等から、対象のエッジ４２のコスト４３を計算する。グラフ生成部２１は、計算されたコスト４３を対象のエッジ４２に割り当てる。グラフ生成部２１は、各エッジ４２にコスト４３が割り当てられた追跡グラフ４０をメモリ１２に書き込む。
【００２４】
グラフ生成部２１は、図４に示すように、各ノード４１を２つのノード４１１とその間を繋ぐエッジ４１２として表してもよい。そして、グラフ生成部２１は、エッジ４１２に、ノード４１が対象物３２を表す確率等から計算されたコスト４１３を割り当ててもよい。
【００２５】
（ステップＳ２：第１対応特定処理）
対応特定部２４は、時間的に最も前のフレーム３１と、時間的に前から２番目のフレーム３１との間で、対象物３２間の対応関係を特定する。
具体的には、対応特定部２４は、メモリ１２から追跡グラフ４０を読み出す。対応特定部２４は、ノードｓからノードｔまでの最短経路問題を、動的計画法を用いて時間的に前から２番目のフレーム３１まで解く。動的計画法は、時間的に一方向に最短経路が決まっていく。動的計画法は、例えば、非特許文献１に記載がある。対応特定部２４は、決定された経路で接続されている対象物３２同士が対応するものと特定する。対応特定部２４は、特定された対応関係をメモリ１２に書き込む。
【００２６】
以下のステップＳ３からステップＳ５の処理が時間的に前から２番目のフレーム３１から最後のフレーム３１まで１つのフレーム３１ずつ順に対象として実行される。
【００２７】
（ステップＳ３：ベクトル計算処理）
ベクトル計算部２２は、複数のフレーム３１のうち対象フレーム３３から検出された対象物３２と、対象フレーム３３の前のフレーム３１から検出された対象物３２との対応関係に基づき、対象フレーム３３から検出された対象物３２の速度ベクトル３４を計算する。
具体的には、ベクトル計算部２２は、対象フレーム３３から検出された対象物３２と、対象フレーム３３の前のフレーム３１から検出された対象物３２との対応関係をメモリ１２から読み出す。ベクトル計算部２２は、読み出された対応関係が示すように、前のフレーム３１における対象物３２の位置から対象フレーム３３における対象物３２の位置に対象物３２が移動したとして、対象物３２の速度ベクトル３４を計算する。つまり、ベクトル計算部２２は、図５に示すように、１つのフレーム３１当たりに、前のフレーム３１における対象物３２の位置５１から対象フレーム３３における対象物３２の位置５２までの距離だけ、位置５１から位置５２の方向に移動することを示す速度ベクトル３４を計算する。すなわち、ベクトル計算部２２は、図５のＴ＝１の時点からＴ＝２の時点における距離及び方向（１）と同じ距離及び方向（２）だけ、Ｔ＝２の時点からＴ＝３の時点にも移動することを示す速度ベクトル３４を計算する。ベクトル計算部２２は、計算された速度ベクトル３４をメモリ１２に書き込む。
【００２８】
（ステップＳ４：コスト計算処理）
コスト計算部２３は、ステップＳ３で計算された速度ベクトル３４に基づき、追跡グラフ４０における対象フレーム３３と対象フレーム３３の次のフレーム３１との間で対象物３２を結ぶエッジ４２のコスト４３を再計算する。
具体的には、コスト計算部２３は、速度ベクトル３４から特定される位置に近いノード４１であって、次のフレーム３１における対象物３２を表すノード４１と結ばれたエッジ４２ほど低くなるようにコスト４３を再計算する。コスト計算部２３は、ステップＳ１でメモリ１２に書き込まれたコスト４３のうち再計算の対象になったエッジ４２のコスト４３を、再計算されたコスト４３で更新する。
例えば、コスト計算部２３は、対象フレーム３３と対象フレーム３３の次のフレーム３１との間で対象物３２を結ぶ各エッジ４２を対象として、速度ベクトル３４から特定される位置に近いノード４１と結ばれたエッジ４２ほど低い値Ｘを対象のエッジ４２に割り当てる。そして、コスト計算部２３は、対象フレーム３３と対象フレーム３３の次のフレーム３１との間で対象物３２を結ぶ各エッジ４２を対象として、割り当てられた値Ｘと、ステップＳ１で計算されているコスト４３とに重み付けをした上で合計して、コスト４３を再計算する。つまり、コスト計算部２３は、ステップＳ１で計算されているコスト４３をＹとし、再計算されるコスト４３をＺとし、α及びβを重み（α＋β＝１）として、Ｚ＝αＸ＋βＹによってコスト４３を再計算する。
【００２９】
（ステップＳ５：第２対応特定処理）
対応特定部２４は、追跡グラフ４０と、ステップＳ４で再計算されたコスト４３とに基づき、対象フレーム３３と次のフレーム３１との間の対象物３２の対応関係を特定する。
具体的には、対応特定部２４は、メモリ１２から再計算されたコスト４３が割り当てられた追跡グラフ４０を読み出す。対応特定部２４は、ノードｓからノードｔまでの最短経路問題を、動的計画法を用いて時間的に前から対象フレーム３３の次のフレーム３１まで解く。なお、時間的に先頭のフレーム３１から対象フレーム３３までの経路は、ステップＳ２及び過去に実行されたステップＳ５の処理で計算済である。したがって、ここでは、対象フレーム３３から次のフレーム３１への経路が計算される。対応特定部２４は、決定された経路で接続されている、対象フレーム３３における対象物３２と、次のフレーム３１における対象物３２とが対応するものと特定する。対応特定部２４は、特定された対応関係をメモリ１２に書き込む。対応特定部２４は、特定された対応関係を表示装置１４２に出力して、表示させてもよい。
【００３０】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る追跡装置１０は、速度ベクトル３４を用いて追跡グラフ４０におけるエッジ４２のコスト４３を計算する。そのため、対象物３２の過去の移動を考慮した適切なコスト４３をエッジ４２に割り当てることができる。その結果、精度よく対象物３２を追跡することが可能である。
【００３１】
グラフ理論を用いた追跡技術では、最小費用問題を解くことにより対象物の追跡が行なわれる。そのため、事前に全てのエッジのコストが特定されている必要がある。
しかし、実施の形態１に係る追跡装置１０では、動的計画法を用いて、時間的に一方向に順に経路を特定する。これにより、後に計算される経路を構成するエッジ４２のコスト４３を、既に計算済の経路の情報を用いて再計算することが可能である。つまり、対象物３２の過去の移動を考慮した適切なコスト４３をエッジ４２に割り当てることができる。
【００３２】
図６に示すように、映像データ３０には、対象物として人物Ａ及び人物Ｂが映っているとする。
ここで、時刻Ｔ＝３における人物Ａの位置と、時刻Ｔ＝２における人物Ｂの位置とが近い。すると、従来のように、速度ベクトル３４を用いていない場合には、距離の近い対象物同士を対応付けする傾向があるため、時刻Ｔ＝２における人物Ｂと時刻Ｔ＝３における人物Ａとが対応付けされる可能性がある。つまり、時刻Ｔ＝２における人物Ｂの位置を基準とする距離ｄ１及び距離ｄ２のうち短い方が優先され、時刻Ｔ＝２における人物Ｂと時刻Ｔ＝３における人物Ａとが対応付けされる可能性がある。
しかし、実施の形態１に係る追跡装置１０では、速度ベクトル３４を考慮してコスト４３を計算する。そのため、速度ベクトル３４が示す時刻Ｔ＝３における人物Ｂの予測位置Ｐに近い時刻Ｔ＝３における人物Ｂが、時刻Ｔ＝２における人物Ｂと対応付けされる。つまり、時刻Ｔ＝３における人物Ｂの予測位置Ｐを基準とする距離ｄ３及び距離ｄ４のうち短い方が優先され、時刻Ｔ＝３における人物Ｂが、時刻Ｔ＝２における人物Ｂと対応付けされる。
このように、速度ベクトル３４を考慮してコスト４３を計算することにより、移動軌跡の滑らかさ、つまり同じ速度で同じ方向に移動していることを追跡基準に加えることが可能になる。
【００３３】
＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、各機能構成要素がソフトウェアで実現された。しかし、変形例１として、各機能構成要素はハードウェアで実現されてもよい。この変形例１について、実施の形態１と異なる点を説明する。
【００３４】
図７を参照して、変形例１に係る追跡装置１０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、追跡装置１０は、プロセッサ１１とメモリ１２とストレージ１３とに代えて、電子回路１５を備える。電子回路１５は、各機能構成要素と、メモリ１２と、ストレージ１３との機能とを実現する専用の回路である。
【００３５】
電子回路１５としては、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
各機能構成要素を１つの電子回路１５で実現してもよいし、各機能構成要素を複数の電子回路１５に分散させて実現してもよい。
【００３６】
＜変形例２＞
変形例２として、一部の各機能構成要素がハードウェアで実現され、他の各機能構成要素がソフトウェアで実現されてもよい。
【００３７】
プロセッサ１１とメモリ１２とストレージ１３と電子回路１５とを処理回路という。つまり、各機能構成要素の機能は、処理回路により実現される。
【００３８】
実施の形態２．
実施の形態２は、速度ベクトル３４に加えて、あるいは、速度ベクトル３４に代えて、速度ベクトル３４の変化を表す加速度ベクトル３５を考慮してコスト４３を計算する点が実施の形態１と異なる。
【００３９】
＊＊＊動作の説明＊＊＊
図２を参照して、実施の形態２に係る追跡装置１０の動作を説明する。
実施の形態２に係る追跡装置１０の動作は、実施の形態２に係る追跡方法に相当する。また、実施の形態２に係る追跡装置１０の動作は、実施の形態２に係る追跡プログラムの処理に相当する。
【００４０】
ここでは、速度ベクトル３４に加えて加速度ベクトル３５を考慮してコスト４３を計算する場合の処理を説明する。
ステップＳ１からステップＳ２の処理と、ステップＳ５の処理とは、実施の形態１と同じである。
【００４１】
（ステップＳ３：ベクトル計算処理）
時間的に前から２番目のフレーム３１を対象フレーム３３とする場合には、ベクトル計算部２２は、実施の形態１と同様に、速度ベクトル３４を計算する。時間的に前から３番目以降のフレーム３１を対象フレーム３３とする場合には、ベクトル計算部２２は、速度ベクトル３４だけでなく、加速度ベクトル３５も計算する。
速度ベクトル３４を計算する場合には、２つのフレーム３１についての対応関係が分かれば計算できた。しかし、加速度ベクトル３５を計算する場合には、３つのフレーム３１についての対応関係が必要となる。そのため、時間的に前から２番目のフレーム３１を対象フレーム３３とする場合には、加速度ベクトル３５を計算することができない。
【００４２】
（ステップＳ４：コスト計算処理）
コスト計算部２３は、速度ベクトル３４と、ステップＳ３で加速度ベクトル３５が計算された場合には加速度ベクトル３５も考慮して、コスト４３を再計算する。具体的には、コスト計算部２３は、速度ベクトル３４及び加速度ベクトル３５から特定される位置に近い次のフレーム３１における対象物３２を表すノード４１と結ばれたエッジ４２ほど低くなるようにコスト４３を再計算する。
【００４３】
以上のように、実施の形態２に係る追跡装置１０は、加速度ベクトル３５を考慮してコスト４３を計算した。そのため、より適切なコスト４３をエッジ４２に割り当てることができる。その結果、精度よく対象物３２を追跡することが可能である。
具体的には、対象物３２が加速度一定の運動をする場合には精度よく対象物３２を追跡することができる。具体例としては、対象物３２が放物線を描く運動をする場合は、加速度一定の運動をする場合である。カーブを曲る場合は、放物線に近い軌跡を描く。
例えば、図８に示すように、速度ベクトル３４のみを考慮する場合には、Ｔ＝２，３の時点における位置から計算された速度ベクトル３４が示す予測位置Ｘに基づきコスト４３が計算される。しかし、加速度ベクトル３５も考慮する場合には、Ｔ＝２，３の時点における位置から計算された速度ベクトル３４と、Ｔ＝１〜３の時点における位置から計算された加速度ベクトル３５とが示す予測位置Ｙに基づきコスト４３が計算される。そのため、加速度一定の運動をする場合には、加速度ベクトル３５を考慮した方が予測位置と現実の位置が近くなり、コスト４３が小さくなる。そのため、正しく対応付けされる可能性が高くなる。
【００４４】
＜変形例３＞
実施の形態２では、速度ベクトル３４の変化を表す加速度ベクトル３５を考慮してコスト４３を計算した。しかし、加速度ベクトル３５に限らず、加速度ベクトル３５の変化を表すベクトル等を考慮してコスト４３を計算してもよい。
【符号の説明】
【００４５】
１０  追跡装置、１１  プロセッサ、１２  メモリ、１３  ストレージ、１４  通信インタフェース、１５  電子回路、２１  グラフ生成部、２２  ベクトル計算部、２３  コスト計算部、２４  対応特定部、３０  映像データ、３１  フレーム、３２  対象物、３３  対象フレーム、３４  速度ベクトル、３５  加速度ベクトル、４０  追跡グラフ、４１  ノード、４１１  ノード、４１２  エッジ、４１３  コスト、４２  エッジ、４３  コスト。
【図１】
2019095975.tif 000003
【図２】
2019095975.tif 000004
【図３】
2019095975.tif 000005
【図４】
2019095975.tif 000006
【図５】
2019095975.tif 000007
【図６】
2019095975.tif 000008
【図７】
2019095975.tif 000009
【図８】
2019095975.tif 000010
【手続補正書】
【提出日】平成31年1月10日(2019.1.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
映像データを構成する複数のフレームから検出された複数の対象物それぞれをノードとし、連続する２つのフレーム間で対象物を結ぶエッジを設け、最前のフレームから検出された対象物を示すノードと開始用のノードｓとを結ぶエッジを設け、最後のフレームから検出された対象物を示すノードと終了用のノードｔとを結ぶエッジとを設け、各エッジを対象として、対象のエッジが結ぶ２つのノードが表す対象物の一致度から前記対象のエッジのコストを計算して追跡グラフを生成するグラフ生成部と、
前記グラフ生成部によって生成された前記追跡グラフにおける前記開始用のノードｓから前記終了用のノードｔまでの最短経路問題を解くことにより、前記最前のフレームから検出された対象物と、前記最前のフレームの次のフレームから検出された対象物と対応関係を特定する対応特定部と、
前記複数のフレームについて前記次のフレームから時間の経過順にフレームを対象として、対象フレームから検出された対象物と、前記対象フレームの前のフレームから検出された対象物との対応関係に基づき、前記対象フレームから検出された対象物の速度ベクトルを計算するベクトル計算部と、
前記ベクトル計算部によって計算された速度ベクトルに基づき、前記追跡グラフにおける前記対象フレームと前記対象フレームの次のフレームとの間で対象物を結ぶエッジのコストを計算するコスト計算部と
を備え、
前記対応特定部は、前記追跡グラフと、前記コスト計算部によって計算された前記コストとに基づき、前記対象フレームと前記次のフレームとの間の対象物の対応関係を特定する追跡装置。
【請求項２】
前記コスト計算部は、前記速度ベクトルから特定される位置に近い前記次のフレームにおける対象物を表すノードと結ばれたエッジほど低くなるようにコストを計算し、
前記対応特定部は、前記コストが低いエッジを優先して選択することにより、前記対応関係を特定する
請求項１に記載の追跡装置。
【請求項３】
前記ベクトル計算部は、前記対象フレームと前記次のフレームとの間の対象物の対応関係が特定されると、前記次のフレームを新たな対象フレームとして、前記新たな対象フレームから検出された対象物の速度ベクトルを計算する
請求項１又は２に記載の追跡装置。
【請求項４】
前記ベクトル計算部は、前記対象フレームから検出された対象物の加速度ベクトルを計算し、
前記コスト計算部は、前記加速度ベクトルに基づき、前記エッジのコストを計算する
請求項１から３までのいずれか１項に記載の追跡装置。
【請求項５】
前記コスト計算部は、前記速度ベクトル及び前記加速度ベクトルから特定される位置に近い前記次のフレームにおける対象物と結ばれたエッジほど低くなるようにコストを計算し、
前記対応特定部は、前記コストが低いエッジを優先して選択することにより、前記対応関係を特定する
請求項４に記載の追跡装置。
【請求項６】
映像データを構成する複数のフレームから検出された複数の対象物それぞれをノードとし、連続する２つのフレーム間で対象物を結ぶエッジを設け、最前のフレームから検出された対象物を示すノードと開始用のノードｓとを結ぶエッジを設け、最後のフレームから検出された対象物を示すノードと終了用のノードｔとを結ぶエッジとを設け、各エッジを対象として、対象のエッジが結ぶ２つのノードが表す対象物の一致度から前記対象のエッジのコストを計算して追跡グラフを生成するグラフ生成処理と、
前記グラフ生成処理によって生成された前記追跡グラフにおける前記開始用のノードｓから前記終了用のノードｔまでの最短経路問題を解くことにより、前記最前のフレームから検出された対象物と、前記最前のフレームの次のフレームから検出された対象物と対応関係を特定する対応特定処理と、
前記複数のフレームについて前記次のフレームから時間の経過順にフレームを対象として、対象フレームから検出された対象物と、前記対象フレームの前のフレームから検出された対象物との対応関係に基づき、前記対象フレームから検出された対象物の速度ベクトルを計算するベクトル計算処理と、
前記ベクトル計算処理によって計算された速度ベクトルに基づき、前記追跡グラフにおける前記対象フレームと前記対象フレームの次のフレームとの間で対象物を結ぶエッジのコストを計算するコスト計算処理と
をコンピュータに実行させ、
前記対応特定処理では、前記追跡グラフと、前記コスト計算処理によって計算された前記コストとに基づき、前記対象フレームと前記次のフレームとの間の対象物の対応関係を特定する追跡プログラム。