目標追尾装置
【課題】多次元相関決定時の演算負荷の減少を実現しかつ許容可能な解を導出する目標追尾装置を得る。
【解決手段】センサ観測値を入力情報とする航跡候補コスト行列生成手段１１０Ａと、航跡分離状況判定手段１３０と、多次元相関決定手段１２０とを備えている。航跡候補コスト行列生成手段１１０Ａは、航跡候補行列と、航跡候補の各々に対応するコストからなるコスト配列とを生成する。航跡分離状況判定手段１３０は、航跡が分離していると判定された場合には、航跡候補コスト行列生成手段１１０Ａに対し、航跡候補行列と航跡候補の各々とに対応するコストからなるコスト配列を再生成するように指示する。多次元相関決定手段１２０は、航跡候補行列とコスト配列とからＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
【解決手段】センサ観測値を入力情報とする航跡候補コスト行列生成手段１１０Ａと、航跡分離状況判定手段１３０と、多次元相関決定手段１２０とを備えている。航跡候補コスト行列生成手段１１０Ａは、航跡候補行列と、航跡候補の各々に対応するコストからなるコスト配列とを生成する。航跡分離状況判定手段１３０は、航跡が分離していると判定された場合には、航跡候補コスト行列生成手段１１０Ａに対し、航跡候補行列と航跡候補の各々とに対応するコストからなるコスト配列を再生成するように指示する。多次元相関決定手段１２０は、航跡候補行列とコスト配列とからＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、レーダなどのセンサシステムにおいて、センサからの目標位置の観測値を用いて多目標の航跡を生成する際の相関を多次元的に解く技術に関し、特に演算時間を削減しながら許容可能な解を導出することのできる目標追尾装置に関するものである。
【背景技術】
【０００２】
従来から、センサからの観測値を用いて航跡を多次元的に解く技術は、種々提案されており、たとえば、複数サンプリング時刻にわたる観測値の相関をまとめて計算して航跡を生成するアルゴリズムとして、複数フレーム割当法が知られている（たとえば、特許文献１、非特許文献１、非特許文献２参照）。
【０００３】
複数フレーム割当法においては、既存航跡とＮサンプリング時刻にわたる観測値の相関決定を、Ｎ＋１次元の割当問題に変換して解く。Ｎ＋１次元の割当問題は、以下のように表される。
すなわち、以下の式（１）で表される目的関数を、最小とする２値（０か１）変数を決定する。
【０００４】
【数１】
【０００５】
ここで、２値変数は、以下のように表される。
【０００６】
【数２】
【０００７】
ただし、Ｃｊ２・・・ＣｊＮ＋１は、既存航跡および観測値ｉ１・・・ｉＮ＋１から航跡を生成するために要するコストであり、通常航跡尤度比の逆数の対数値を使用する。
上記変数Ｚｊ１・・・ｚｊＮ＋１は、以下の式（２）のように表される。
【０００８】
【数３】
【０００９】
また、上記（１）においては、以下の式（３）〜式（５）の制約条件がある。
すなわち、任意のｉ１について、以下の式（３）のとおりである。
【００１０】
【数４】
【００１１】
また、任意のｉｋ（１＜ｋ＜Ｎ＋１）については、以下の式（４）のとおりである。
【００１２】
【数５】
【００１３】
任意のｉＮ＋１については、以下の式（５）のとおりである。
【００１４】
【数６】
【００１５】
以下、この問題を高速に解く方法として、非特許文献２に記載された処理手順について説明する。
図１１は非特許文献２に記載された従来の目標追尾装置の構成を示すブロック図であり、図１２は図１１の目標追尾装置による処理手順を示すフローチャートである。
【００１６】
図１１において、目標追尾装置１００は、センサ２００からの観測値を入力情報とする航跡候補コスト行列生成手段１１０と、多次元相関決定手段１２０とを備えている。
多次元相関決定手段１２０は、航跡候補コスト行列生成手段１１０からの航跡候補コスト行列を入力情報とする多次元割当問題初期値設定部１２１と、２次元割当解算出部１２２と、多次元割当解算出部１２３とを備えている。また、多次元割当解算出部１２３には、演算結果を表示する表示装置３００が接続されている。
【００１７】
図１２において、目標追尾装置１００は、まず、観測値入力処理（ステップＳＴ１）を行い、センサ２００から得られた過去から最新までのＮサンプリング時刻分の観測値を、航跡候補コスト行列生成手段１１０に取り込む。
【００１８】
続いて、航跡候補コスト行列生成処理（ステップＳＴ２）を行い、既存航跡および各サンプリング時刻から１つずつの観測値を選択し、その観測値の組み合わせによって形成される航跡候補の尤度比を計算し、尤度比の逆数を用いてコストを計算して航跡候補コスト行列を生成する。
【００１９】
次に、多次元相関決定手段１２０において、航跡候補を既存航跡番号と各観測フレームの観測番号のＮ＋１次元の組み合わせと見なし、各航跡候補のコストを用いてＮ＋１次元の割当問題を解く（ステップＳＴ８〜ＳＴ１１）。
まず、多次元割当問題初期値設定処理（ステップＳＴ８）を行い、Ｎ＋１次元の問題をＫ次元の割当問題とし、以下の式（６）により、２次元割当問題に緩和するための各航跡候補のコストの設定を行う。
【００２０】
【数７】
【００２１】
ただし、式（６）において、ｉ１ｉ２ｊ３・・・ｊＮ＋１は、ｉ１ｉ２から構成される航跡候補の中で最小コストを有する航跡候補を示す。また、観測値ｊｒに対応するＬａｇｒａｎｇｅ乗数はＵｊｒであり、初期値はすべて「０」である。
【００２２】
続いて、２次元割当解算出処理（ステップＳＴ９）を行い、２次元割当問題を解く。
２次元割当問題は、演算負荷も少なくかつ厳密解が求められる手法が多く提案されている（たとえば、Ｍｕｎｋｒｅｓ法）。この解は、Ｋ次元割当問題を２次元に緩和した解であることから、Ｋ次元割当解の下解であることが一般的に知られている。
【００２３】
次に、２次元割当許容解判定処理（ステップＳＴ１０）を行い、得られた２次元割当解がＫ次元割当問題の許容解の一部であるか否かを判定する。
ステップＳＴ１０において、前回解が以下の式（７）を満たす場合には、許容解の一部であると判定する。
【００２４】
【数８】
【００２５】
ただし、式（７）において、ｌは、２次元割当問題の解の導出の際の繰り返し回数であり、φｌは、２次元割当解における航跡候補のコストの総和であり、ｔｈｒｅｓｈｏｌｄは、２次元割当解が十分大きい値であると判断するための収束判定閾値である。
【００２６】
ステップＳＴ１０において、前回解が以下の式（７）を満たし、許容解の一部であると判定された場合には、２次元割当解を１次元列に修正し、Ｋ次元割当問題をＫ−１次元割当問題に縮小して、多次元割当問題初期値設定処理（ステップＳＴ８）に戻る。
【００２７】
一方、ステップＳＴ１０において、前回解が式（７）を満たさない場合には、Ｌａｇｒａｎｇｅ乗数を修正して、当該Ｌａｇｒａｎｇｅ乗数に対応したコストを再計算し、多次元割当問題初期値設定処理（ステップＳＴ８）に戻る。
【００２８】
以上の処理（ステップＳＴ８〜ＳＴ１０）を繰り返し実行した後、多次元割当解出力処理（ステップＳＴ１１）」を行い、縮小した次元を元のＮ＋１次元に戻す。このとき、上記式（３）〜式（５）の制約条件を満たし、上記式（１）の許容解を構成する航跡候補組み合わせを導出する。
【００２９】
【特許文献１】特開２００７−２１２２４４号公報
【非特許文献１】Ａ．Ｂ．Ｐｏｏｒｅ ａｎｄ Ａ．Ｊ．ＲｏｂｅｒｔｓｏｎＩＩＩ「Ａ Ｎｅｗ Ｍｕｌｔｉ−ｄｉｍｅｎｓｉｏｎａｌ Ｄａｔａ Ａｓｓｏｃｉａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｍｕｌｔｉｓｅｎｓｏｒ−Ｍｕｌｔｉｔａｒｇｅｔ Ｔｒａｃｋｉｎｇ」 Ｐｒｏｃ． Ｏｆ ＳＰＩＥ ｖｏｌ．２５６１，１９９５．
【非特許文献２】Ａ．Ｂ．Ｐｏｏｒｅ ａｎｄ Ａ．Ｊ．ＲｏｂｅｒｔｓｏｎＩＩＩ「Ａ Ｎｅｗ Ｌａｇｒａｎｇｉａｎ Ｒｅｌａｘａｔｉｏｎ Ｂａｓｅｄ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ａ Ｃｌａｓｓ ｏｆ Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ Ａｓｓｉｇｎｍｅｎｔ Ｐｒｏｂｌｅｍｓ」 Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ８， １２９−１５０， １９９７．
【発明の開示】
【発明が解決しようとする課題】
【００３０】
従来の目標追尾装置では、非特許文献２に記載の複数フレーム割当法を用いた場合、多次元相関決定において許容可能な解を小さい演算負荷で導出しているものの、Ｎ次元の割当問題を２次元割当問題の繰り返しに変換し、２次元割当解の導出において解が収束するまで航跡候補の組み合わせの抽出処理が繰り返し行われるので、観測間隔が短いセンサや演算速度が遅いプラットホームで処理を行うためには、さらなる演算負荷の減少が必要になるという課題があった。
【００３１】
また、特許文献１には、上記課題の解決策として、通常は２次元相関を行い、かつ一定フレーム間隔で複数フレーム割当法による相関を行い、演算時間増大フレームを制限することにより、演算負荷の減少を実現しているが、この場合、複数フレーム割当法を行うフレームにおける観測値と既存航跡との関係にかかわらず、観測フレーム数を減少させることから、導出解精度の悪化や、当該フレームでは演算時間が減少せずに、次のフレームの演算時間が消費されるという課題あった。
【００３２】
この発明は、上記のような課題を解決するためになされたものであり、航跡候補の中から、航跡候補の航跡番号と構成される観測値と航跡候補のコストとの関係から抽出される航跡組み合わせを予想し、予想された関係から、抽出される航跡が分離しているか否かを判別し、その分離状況に応じて、多次元相関決定における初期解の設定または収束判定の緩和を行うことにより、多次元相関決定においてさらなる演算負荷の減少を実現するとともに、許容可能な解を導出することのできる目標追尾装置を得ることを目的とする。
【課題を解決するための手段】
【００３３】
この発明による目標追尾装置は、センサからの観測値を入力情報とする航跡候補コスト行列生成手段と、航跡分離状況判定手段と、多次元相関決定手段と、を備えた目標追尾装置であって、航跡候補コスト行列生成手段は、現在までの最新Ｎフレームの観測値の観測番号と現在からＮ＋１フレーム前に生成された航跡の航跡番号との組み合わせを作成して、観測番号と航跡番号との複数の組み合わせの各々を航跡候補と見なす航跡候補行列と、航跡候補の各々に対応するコストからなるコスト配列と、を生成し、航跡分離状況判定手段は、航跡候補の各々で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、を対比することにより航跡の分離状況を判定して、航跡が分離していると判定された場合には、航跡候補コスト行列生成手段に対し、最新Ｍ（≦Ｎ）フレームの観測値を用いて、航跡候補行列と航跡候補の各々とに対応するコストからなるコスト配列を再生成するように指示し、多次元相関決定手段は、航跡候補行列とコスト配列とからＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出するものである。
【発明の効果】
【００３４】
この発明によれば、多次元相関決定において演算負荷の減少を実現するとともに、許容可能な解を導出することができる。
【発明を実施するための最良の形態】
【００３５】
実施の形態１．
図１はこの発明の実施の形態１に係る目標追尾装置１００Ａの構成を示すブロック図であり、前述（図１１）と同様のものについては、前述と同一符号を付して、または符号の後に「Ａ」を付して詳述を省略する。
図１において、目標追尾装置１００Ａは、航跡候補コスト行列生成手段１１０Ａと、多次元相関決定手段１２０と、航跡分離状況判定手段１３０と、を備えている。
【００３６】
航跡候補コスト行列生成手段１１０Ａは、既存航跡とセンサ２００からの観測値の航跡候補とを生成し、各航跡候補に対応するコストを算出する。
多次元相関決定手段１２０は、航跡候補コスト行列生成手段１１０Ａにより生成された航跡候補と対応するコストとから、当該観測フレームにおける最適航跡候補群の抽出を、Ｎ＋１次元割当問題として前述と同様の処理により解く。
【００３７】
航跡分離状況判定手段１３０は、最小コスト航跡抽出部１３１と、最小コスト算出諸元設定部１３２と、航跡分離状況判定部１３３と、を備えている。
航跡分離状況判定手段１３０は、抽出される航跡が分離しているか否かを判定し、分離していると判定された場合には、航跡候補コスト行列生成手段１１０Ａに対して、最新Ｎ観測フレームの利用の元で、最新Ｍ観測フレームでの航跡候補の再生成およびコストの再算出を指示する。なお、「Ｍ（≦Ｎ）」の値は、「３（航跡が確立する最低観測フレーム数）」以上に設定される。
目標追尾装置１００Ａで確立した航跡は、表示装置３００により表示される。
【００３８】
次に、図２のフローチャートと図３および図４の説明図とを参照しながら、図１に示したこの発明の実施の形態１による動作について説明する。ここでは、特に、航跡分離状況判定手段１３０を中心とした動作について説明する。
【００３９】
図２において、前述（図１２）と同様の処理（ステップＳＴ１、ＳＴ２、ＳＴ８〜ＳＴ１１）については、前述と同一符号が付されている。
図３は、Ｎ＝４、既存航跡数＝２、各観測フレームでの観測値数＝２〜３の場合の航跡候補の組み合わせ行列の例を示している。また、図４は、各最小コスト算出諸元設定値での抽出結果の例を示している。
【００４０】
図２において、まず、航跡候補コスト行列生成手段１１０Ａは、センサ２００から得られた観測値を取り込むとともに（ステップＳＴ１）、多次元割当解算出部１２３から出力された既存航跡の組み合わせを作成して、たとえば図３のように、コスト（航跡候補コスト行列）を算出する（ステップＳＴ２）。
【００４１】
図３においては、４フレーム分のスライディングウィンドウ（２点鎖線枠）内の各時刻ｔ１〜ｔ４で選択される、既存軌跡（１）（１点鎖線矢印）および既存軌跡（２）（実線矢印）の観測値ａ１、ａ２、ａ３（黒四角点）と、観測値の組み合わせ（点線枠）で示される各航跡候補およびコスト（尤度比の逆数）とが示されている。
【００４２】
図３内の観測値ａに付された数字「１」〜「３」は、観測番号を示している。
また、航跡候補（０）〜（２）において、航跡候補（０）は、既存航跡との相関が存在しないことを示し、「０」は、相関観測値が存在しないことを示している。
【００４３】
次に、最小コスト航跡抽出部１３１は、生成された航跡組候補の組み合わせ行列から、最小コスト算出諸元設定部１３２での設定値判定処理（ステップＳＴ３）を行い、設定値が「０」の場合には、ステップＳＴ４に進み、設定値が「１」の場合には、ステップＳＴ５に進む。
【００４４】
ステップＳＴ４（設定値＝０）においては、各航跡番号の中で最小コストとなる航跡候補を選択し、さらに最新観測フレームの各観測番号において最小コストとなる航跡候補を選択し、選択された各航跡候補における航跡番号と観測番号との組み合わせを、たとえば図４の抽出結果のように生成して、次の判定処理（ステップＳＴ６）に進む。
【００４５】
一方、ステップＳＴ５（設定値＝１）においては、最新Ｍ＋１観測フレームにおける観測番号において最小コストとなる航跡候補を選択し、さらに最新観測フレームの各観測番号において最小コストとなる航跡候補を選択し、選択された各航跡候補における航跡番号と観測番号との組み合わせを、たとえば図４の抽出結果のように生成して、次の判定処理（ステップＳＴ６）に進む。
【００４６】
図４においては、過去４フレーム分の時刻ｔ１〜ｔ４での各航跡番号（０）〜（２）の航跡候補に基づく、各ステップＳＴ４、ＳＴ５による導出（抽出）結果が具体的に示されている。
ここでは、ステップＳＴ４による導出結果として、航跡番号（１）に関しては、観測番号「１」（観測値ａ１）の最小コスト「−２．４」が抽出され、航跡番号（２）に関しては、観測番号「３」（観測値ａ３）の最小コスト「−６．２」が抽出されている。
【００４７】
同様に、ステップＳＴ５による導出（抽出）結果として、航跡番号（１）に関しては、観測番号「１」（観測値ａ１）の最小コスト「−２．４」が抽出され、航跡番号（２）に関しては、観測番号「３」（観測値ａ３）の最小コスト「−６．２」が抽出されている。
この結果、各航跡番号（１）、（０）、（２）での最小コスト航跡候補として、それぞれ、観測番号「１」の最小コスト「−２．４」、観測番号「２」の最小コスト「−０．５」、観測番号「３」の最小コスト「−６．２」が抽出される。
【００４８】
次に、航跡分離状況判定部１３３は、上記の２つの観点から抽出した航跡番号と観測番号との組み合わせを比較し（ステップＳＴ６）、抽出した航跡候補組み合わせで同一航跡番号および同一観測点番号の抽出がなく、かつ、一定数以上の航跡番号と観測番号との組み合わせが一致した場合には、航跡は分離しているものと判定する。
【００４９】
ステップＳＴ６による組み合わせの一致判定において、航跡番号数と観測番号数とが異なる場合には、少ない数の組み合わせでの判定を行う。
また、一定数の設定の例として、正解航跡を誤航跡と認識する確率（一般的に、「０．１」などの値）を「１」から減算した確率を設定する方法が挙げられる。
【００５０】
ステップＳＴ６において航跡が分離していると判定された場合には、航跡分離状況判定部１３３は、最小コスト算出諸元設定部１３２であらかじめ設定されている観測フレーム数Ｍを航跡候補コスト行列生成手段１１０Ａに入力する。
一方、ステップＳＴ６において航跡が分離していないと判定された場合には、航跡分離状況判定部１３３は、観測フレーム数Ｎを航跡候補コスト行列生成手段１１０Ａに入力する。
【００５１】
航跡候補コスト行列生成手段１１０Ａは、観測フレーム数＝Ｍ（航跡が分離）を入力した場合には、指定観測フレーム数での航跡候補の組み合わせ行列を生成して、コスト（航跡候補コスト行列）を算出して出力する（ステップＳＴ７）。
一方、観測フレーム数＝Ｎ（航跡の分離なし）を入力した場合には、航跡候補コスト行列生成手段１１０Ａは、すでに生成した航跡候補の組み合わせ行列およびコストを出力する。
【００５２】
以下、多次元相関決定手段１２０内の多次元割当問題初期値設定部１２１は、Ｎ（Ｍ）＋１次元の航跡候補の組み合わせ行列およびコストを、Ｋ次元の多次元相関問題として、前述の式（６）のように、Ｋ次元の問題を２次元割当問題に緩和するための各航跡候補のコストの設定を行う（ステップＳＴ８）。
【００５３】
続いて、２次元割当解算出部１２２は、前述と同様に２次元割当問題を解く（ステップＳＴ９）。
２次元割当問題は、演算負荷も少なくかつ厳密解が求められる手法が多く提案されている（たとえば、Ｍｕｎｋｒｅｓ法）。この解は、Ｋ次元割当問題を緩和した解であることから、Ｋ次元割当解の下解であることが一般的に知られている。
【００５４】
また、２次元割当解算出部１２２は、得られた２次元割当解がＫ次元割当問題の許容解の一部であるか否かを判定する（ステップＳＴ１０）。
すなわち、前回解が前述の式（７）を満たす場合には、許容解の一部であると判定し、前回解が式（７）を満たさない場合には、Ｌａｇｒａｎｇｅ乗数を修正して、当該Ｌａｇｒａｎｇｅ乗数に対応したコストを再計算し、多次元割当問題初期値設定部１２１に出力する。
【００５５】
ステップＳＴ１０において、許容解の一部であると判定された場合には、２次元割当解を１次元列に修正し、Ｋ次元割当問題をＫ−１次元割当問題に縮小して、多次元割当問題初期値設定部１２１に出力する。このとき、Ｌａｇｒａｎｇｅ乗数はすべて「０」に初期化する。
【００５６】
以上の処理（ステップＳＴ８〜ＳＴ１０）を繰り返し実行した後、縮小した次元を元のＮ（Ｍ）＋１次元に戻し、航跡候補組み合わせを導出する（ステップＳＴ１１）。
このように、抽出される航跡の分離状況を、航跡候補の航跡番号と観測番号とコストとの関係から予測し、航跡が分離していると推測される場合には、多次元相関決定手段１２０に入力する航跡候補を構成する観測フレーム数を減少させることにより、多次元相関決定の解の精度の劣化を抑えつつ演算負荷を軽減することができる。
【００５７】
以上のように、この発明の実施の形態１（図１、図２）に係る目標追尾装置１００Ａは、センサ２００からの観測値を入力情報とする航跡候補コスト行列生成手段１１０Ａと、航跡分離状況判定手段１３０と、多次元相関決定手段１２０と、を備えており、航跡候補コスト行列生成手段１１０Ａは、現在までの最新Ｎフレームの観測値の観測番号と現在からＮ＋１フレーム前に生成された航跡の航跡番号との組み合わせを作成して、観測番号と航跡番号との複数の組み合わせの各々を航跡候補と見なす航跡候補行列と、航跡候補の各々に対応するコストからなるコスト配列と、を生成する。
【００５８】
航跡分離状況判定手段１３０は、航跡候補の各々で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、を対比することにより航跡の分離状況を判定して、航跡が分離していると判定された場合には、航跡候補コスト行列生成手段１１０Ａに対し、最新Ｍ（≦Ｎ）フレームの観測値を用いて、航跡候補行列と航跡候補の各々とに対応するコストからなるコスト配列を再生成するように指示する。
【００５９】
また、航跡分離状況判定手段１３０は、利用する観測フレームを縮小したときに航跡候補行列に残らない最新の観測フレームにおける各観測番号で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と最新の観測フレームにおける各観測番号との組み合わせと、を対比することにより各航跡の分離状況を判定する
【００６０】
さらに、多次元相関決定手段１２０は、航跡候補行列およびコスト配列からＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
これにより、航跡が分離していると推測される場合には、多次元相関決定手段１２０に入力する航跡候補を構成する観測フレーム数を減少させることができ、多次元相関決定の解の精度の劣化を抑えつつ演算負荷を軽減することができる。
【００６１】
実施の形態２．
なお、上記実施の形態１（図１、図２）では、航跡分離状況判定手段１３０において、最小コストを有する航跡候補の航跡番号と最新観測フレームにおける観測番号との組み合わせから、航跡の分離状況を判定したが、このとき、コストの小さい航跡候補が航跡として抽出される可能性がある。
【００６２】
したがって、図５のように、航跡分離状況判定手段１３０Ｂ内に航跡コスト分散算出部１３４を設けることにより、航跡候補のコストの分散から航跡のコストのばらつきを求め、コストの小さい航跡候補の集合における各航跡候補の航跡番号と観測番号との共有度から、航跡の分離状況を判定してもよい。
【００６３】
図５はこの発明の実施の形態２に係る目標追尾装置１００Ｂの構成を示すブロック図であり、前述（図１）と同様のものについては、前述と同一符号を付して、または符号の後に「Ｂ」を付して詳述を省略する。
図５において、目標追尾装置１００Ｂ内の航跡分離状況判定手段１３０Ｂは、前述（図１）の最小コスト航跡算出部１３１に代えて、航跡コスト分散算出部１３４を備えている。他の構成は、図１に示したとおりである。
【００６４】
航跡コスト分散算出部１３４は、航跡候補のコストの分散を算出し、平均値から標準偏差以下のコストを有する航跡候補を抽出する。
以下、航跡分離状況判定部１３３Ｂは、抽出された航跡候補での航跡番号の重複度が一定値以下であり、かつ、各航跡番号での同一観測フレームでの観測番号の重複度が一定値以下である場合に、航跡は分離しているものと判定する。
【００６５】
航跡が分離していると判定された場合には、航跡分離状況判定部１３３Ｂは、航跡候補コスト行列生成手段１１０Ａに対して、最新Ｎ観測フレームの利用の元で、最新Ｍ観測フレーム（Ｎ≧Ｍ、Ｍ＝３（航跡が確立する最低観測フレーム数）以上）での航跡候補の再生成およびコストの再算出を指示する。
【００６６】
次に、図６のフローチャートを参照しながら、この発明の実施の形態２による航跡分離状況判定手段１３０Ｂの動作について説明する。ここでは、前述の実施の形態１（図２）との変更点を中心に説明する。
図６において、ステップＳＴ１、ＳＴ２、ＳＴ７〜ＳＴ１１は、前述（図２）と同様の処理であり、ステップＳＴ５１、ＳＴ６１は、前述のステップＳＴ６に対応する。
【００６７】
まず、観測値入力処理（ステップＳＴ１）および航跡候補コスト行列生成処理（ステップＳＴ２）に続いて、航跡コスト分散算出部１３４は、航跡候補のコストの平均値および分散を算出し（ステップＳＴ３１）、分散の平方根である標準偏差を算出して、平均値−標準偏差×定数倍（たとえば、定数＝１）の小コストを有する航跡候補を抽出する（ステップＳＴ４１）。
【００６８】
次に、航跡分離状況判定部１３３Ｂは、航跡コスト分散算出部１３４により抽出された航跡候補に対する航跡番号の重複度（重複割合）が一定値以下であるか否かを判定する（ステップＳＴ５１）。もし、航跡番号の抽出航跡に対する重複度が一定値以下の場合には、続いて、各航跡の観測番号の重複度が一定値以下であるか否かを判定する（ステップＳＴ６１）。
【００６９】
このとき、ステップＳＴ５１、ＳＴ６１での重複度判定基準となる一定値は、平均値からの差分に合わせて設定され、今回の例では、標準偏差であることから、たとえば３３％に設定される。
ステップＳＴ６１において、観測番号の重複度が一定値（航跡番号の重複度判定の場合と同一値）以下と判定された場合には、航跡分離状況判定部１３３Ｂは、航跡が分離しているものと判定する。
【００７０】
航跡分離状況判定部１３３Ｂは、航跡が分離していると判定された場合には、最小コスト算出諸元設定部１３２であらかじめ設定されている観測フレーム数Ｍを航跡候補コスト行列生成手段１１０Ａに入力し、航跡が分離していないと判定された場合には、観測フレーム数Ｎを航跡候補コスト行列生成手段１１０Ａに入力する。
上記以外の動作については、前述の実施の形態１と同様である。
【００７１】
以上のように、この発明の実施の形態２（図５、図６）によれば、航跡分離状況判定手段１３０Ｂは、航跡候補のコストの平均値からコストの標準偏差以下となるコストを有する航跡候補において、同一航跡番号および観測番号を有する航跡数から航跡の分離状況を判定する。
【００７２】
すなわち、航跡候補のコストの分散から航跡のコストのばらつきを求め、コストの小さい航跡候補の集合における各航跡候補の航跡番号と観測番号との共有度から、航跡の分離状況を判定する。
【００７３】
このように、航跡が分離していると推測される場合に、多次元相関決定手段に入力する航跡候補を構成する観測フレーム数を減少させることにより、多次元相関決定の解の精度の劣化を抑えつつ演算負荷を軽減することができる。
すなわち、抽出される航跡の分離状況を判定する際に、コストの小さい航跡候補が航跡として抽出される可能性があるが、多次元相関決定の解の精度の劣化を抑えることができる。
【００７４】
実施の形態３．
なお、上記実施の形態２（図５、図６）では、航跡分離状況判定手段１３０Ｂ内に航跡コスト分散算出部１３４を設け、航跡が分離していると判定された場合にのみ航跡候補を構成する観測フレーム数を減少させることにより、多次元相関決定の解の精度の劣化を抑えつつ演算負荷を軽減したが、図７、図６のように、多次元相関決定手段１２０Ｃ内に多次元割当問題初期値修正部１２４を設け、航跡が分離していると判定された場合に、航跡候補を構成する観測フレーム数はそのままに保持して、多次元相関決定の初期値を修正し、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の演算負荷を減少してもよい。
【００７５】
図７はこの発明の実施の形態３に係る目標追尾装置１００Ｃの構成を示すブロック図であり、前述（図１）と同様のものについては、前述と同一符号を付して、または符号の後に「Ｃ」を付して詳述を省略する。
【００７６】
図７において、目標追尾装置１００Ｃ内の多次元相関決定手段１２０Ｃは、前述（図１）の構成に加えて、多次元割当問題初期値修正部１２４を備えている。
多次元割当問題初期値修正部１２４からの修正情報は、多次元割当問題初期値設定部１２１Ｃに入力されている。他の構成は、図１に示したとおりである。
【００７７】
航跡分離状況判定手段１３０Ｃ内の航跡分離状況判定部１３３Ｃは、航跡が分離していると判定された場合には、組み合わせ同一航跡候補を出力する。
多次元相関決定手段１２０Ｃ内の多次元割当問題初期値修正部１２４は、組み合わせ同一航跡候補に応答して、抽出された航跡候補のコスト修正量を「０」に設定し、それ以外の航跡候補のコスト修正量を「正の一定値」に設定する。
【００７８】
なお、コスト修正量の「正の一定値」は、たとえば、抽出航跡を航跡表示装置３００に表示させる判定閾値の絶対値に設定される。
多次元割当問題初期値設定部１２１Ｃにおいて、航跡候補のコストに当該コスト修正量を加え、多次元相関決定における各航跡候補の初期コストとする。
【００７９】
次に、図８のフローチャートを参照しながら、この発明の実施の形態３による多次元相関決定手段１２０Ｃの動作について説明する。ここでは、前述の実施の形態１（図２）との変更点を中心に説明する。
【００８０】
図８において、ステップＳＴ１〜ＳＴ６、ＳＴ８〜ＳＴ１１は、前述（図２）と同様の処理であり、ステップＳＴ７１は、前述のステップＳＴ７に対応する。また、ステップＳＴ７１とステップＳＴ８との間に、ステップＳＴ７２が挿入されている。
【００８１】
目標追尾装置１００Ｃは、まず、前述と同様の処理（ステップＳＴ１〜ＳＴ６）を行い、航跡分離状況判定部１３３Ｃ（ステップＳＴ６）において、航跡が分離していると判定された場合には、組み合わせ同一航跡候補を抽出して出力する（ステップＳＴ７１）。
【００８２】
続いて、多次元割当問題初期値修正１２４は、抽出航跡候補のコスト修正量を「０」と設定し、抽出航跡候補以外の航跡候補のコスト修正量を「正の一定値」に設定する（ステップＳＴ７２）。
【００８３】
以下、多次元割当問題初期値設定部１２１Ｃは、航跡候補の組み合わせ行列およびコストを、Ｋ次元の多次元相関問題として、Ｋ次元の問題を２次元割当問題に緩和するための各航跡候補のコストの設定を、以下の式（８）のように、コスト修正量を加えて行う（ステップＳＴ８）。
【００８４】
【数９】
【００８５】
ここで、ｉ１ｉ２ｊ３・・・ｊＮ＋１からなる航跡候補が抽出されている場合には、以下の式（９）が成立する。
【００８６】
【数１０】
【００８７】
また、ｉ１ｉ２ｊ３・・・ｊＮ＋１からなる航跡候補が抽出されていない場合には、以下の式（１０）が成立する。
【００８８】
【数１１】
【００８９】
ただし、式（１０）において、Ａは正数値（たとえば、航跡確立閾値の絶対値）である。
上記以外の動作については、前述の実施の形態１と同様である。
【００９０】
以上のように、この発明の実施の形態３（図７、図８）によれば、多次元相関決定手段１２０Ｃは、航跡分離状況判定部１３３Ｃにより航跡が分離していると判定された場合には、航跡候補の観測フレーム数を縮小してコストを再計算することを禁止して、２次元割当問題の解の精度判定閾値を緩和し、航跡候補行列およびコスト配列からＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
【００９１】
また、多次元相関決定手段１２０Ｃは、航跡分離状況判定部１３３Ｃにより航跡が分離していると判定された場合には、２次元割当問題の解がＫ次元割当問題の許容解の一部であるか否かの判定閾値を緩和し、航跡候補行列およびコスト配列からＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
【００９２】
このように、航跡の分離状況を判定して、航跡が分離していると判定される場合には、航跡候補を構成する観測フレーム数はそのままに保持して、多次元相関決定の初期値を修正し、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の精度劣化を抑えつつ演算負荷を軽減することができる。
【００９３】
また、多次元割当問題初期値修正部１２４を用いた多次元相関決定手段の構成は、前述の実施の形態２（図５）の航跡分離状況判定手段１３０Ｂに対しても適用することができ、同等の作用効果を奏することは言うまでもない。
【００９４】
実施の形態４．
なお、上記実施の形態３（図７、図８）では、多次元割当問題初期値修正部１２４を設け、航跡が分離していると判定される場合には、航跡候補を構成する観測フレーム数はそのままに保持して、多次元相関決定の初期値を修正し、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の演算負荷を軽減したが、図９、図１０のように、収束判定閾値修正部１２５を設け、航跡が分離していると判定される場合には、２次元割当解がＫ次元の許容解の一部であるか否かの判定における収束閾値を緩和して、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の演算負荷を軽減してもよい。
【００９５】
図９はこの発明の実施の形態４に係る目標追尾装置１００Ｄの構成を示すブロック図であり、前述（図１、図７）と同様のものについては、前述と同一符号を付して、または符号の後に「Ｄ」を付して詳述を省略する。
【００９６】
図９において、目標追尾装置１００Ｄ内の多次元相関決定手段１２０Ｄは、前述（図７）の多次元割当問題初期値修正部１２４に代えて、収束判定閾値修正部１２５を備えている。他の構成は、図７に示したとおりである。
【００９７】
航跡分離状況判定手段１３０Ｄ内の航跡分離状況判定部１３３Ｄは、航跡が分離していると判定された場合には、航跡分離情報を出力する。
【００９８】
多次元相関決定手段１２０Ｄ内の収束判定閾値修正部１２５は、航跡分離情報に応答して、航跡が分離していると判定される場合には、２次元割当解算出部１２２Ｄで用いられる閾値の緩和値Ｂを設定する。
緩和値Ｂで緩和された後の閾値ｔｈｒｅｓｈｏｌｄ’は、元の閾値ｔｈｒｅｓｈｏｌｄを用いて、以下の式（１１）で表される。
【００９９】
【数１２】
【０１００】
ただし、式（１１）において、緩和値Ｂは一定値（たとえば、「１０」）である。
緩和後の閾値ｔｈｒｅｓｈｏｌｄ’は、２次元割当解算出部１２２Ｄにおいて、２次元割当解がＫ次元割当問題の許容解の一部であるか否かを判定する際に用いられる。
【０１０１】
次に、図１０のフローチャートを参照しながら、この発明の実施の形態４による多次元相関決定手段１２０Ｄの動作について説明する。ここでは、前述の実施の形態１、３（図２、図８）との変更点を中心に説明する。
図１０において、ステップＳＴ１〜ＳＴ６、ＳＴ８〜ＳＴ１１は、前述（図２、図８）と同様の処理であり、ステップＳＴ６とステップＳＴ９との間に、ステップＳＴ７３が挿入されている。
【０１０２】
図１０内のステップＳＴ６において、航跡分離状況判定手段１３０Ｄ内の航跡分離状況判定部１３３Ｄは、航跡が分離しているか否かの判定結果（分離の有無を示す）として航跡分離情報を出力する。
【０１０３】
収束判定閾値修正部１２５は、航跡分離情報が「航跡分離あり」を示す場合には、収束閾値（収束値）として、デフォルト設定閾値の定数（緩和値Ｂ）倍した修正値を設定する（ステップＳＴ７３）。
以下、２次元割当解算出部１２２Ｄは、修正された収束閾値を用いて、２次元割当解がＫ次元割当問題の許容解の一部であるか否かの判定を行う（ステップＳＴ９）。
上記以外の動作については、前述の実施の形態１と同様である。
【０１０４】
以上のように、この発明の実施の形態４（図９、図１０）によれば、多次元相関決定手段１２０Ｄは、航跡分離状況判定手段１３０Ｄにより航跡が分離していると判定された場合には、航跡分離状況判定で抽出された航跡候補の２次元割当問題導出時コストの初期値を「０」に設定し、航跡分離状況判定で抽出されなかった航跡候補の２次元割当問題導出時コストの初期値として航跡候補コストに「正数値」を付加し、航跡候補行列およびコスト配列からＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
【０１０５】
このように、２次元割当解がＫ次元の許容解の一部であるか否かの判定における収束閾値を緩和して、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の演算負荷を軽減することができる。
【０１０６】
なお、収束判定閾値修正部１２５を用いた多次元相関決定手段の構成は、前述の実施の形態２（図５）の航跡分離状況判定手段１３０Ｂに対しても適用することができ、同等の作用効果を奏することは言うまでもない。
【図面の簡単な説明】
【０１０７】
【図１】この発明の実施の形態１に係る目標追尾装置の構成を示すブロック図である。
【図２】この発明の実施の形態１による動作を示すフローチャートである。
【図３】この発明の実施の形態１における航跡候補の組み合わせ行列の例を示す説明図である。
【図４】この発明の実施の形態１における各最小コスト算出諸元設定値での抽出結果の例を示す説明図である。
【図５】この発明の実施の形態２に係る目標追尾装置の構成を示すブロック図である。
【図６】この発明の実施の形態２による動作を示すフローチャートである。
【図７】この発明の実施の形態３に係る目標追尾装置の構成を示すブロック図である。
【図８】この発明の実施の形態３による動作を示すフローチャートである。
【図９】この発明の実施の形態４に係る目標追尾装置の構成を示すブロック図である。
【図１０】この発明の実施の形態４による動作を示すフローチャートである。
【図１１】従来の目標追尾装置の構成を示すブロック図である。
【図１２】従来の目標追尾装置による動作を示すフローチャートである。
【符号の説明】
【０１０８】
１００Ａ、１００Ｂ、１００Ｃ、１００Ｄ 目標追尾装置、１１０Ａ 航跡候補コスト行列生成手段、１２０、１２０Ｃ、１２０Ｄ 多次元相関決定手段、１２１、１２１Ｃ、１２１Ｄ 多次元割当問題初期値設定部、１２２、１２２Ｄ ２次元割当解算出部、１２３ 多次元割当解算出部、１２４ 多次元割当問題初期値修正部、１２５ 収束判定閾値修正部、１３０、１３０Ｂ 航跡分離状況判定手段、１３１ 最小コスト航跡抽出部、１３２ 最小コスト算出諸元設定部、１３３、１３３Ｃ、１３３Ｄ 航跡分離状況判定部、１３４ 航跡コスト分散算出部、２００ センサ。
【技術分野】
【０００１】
この発明は、レーダなどのセンサシステムにおいて、センサからの目標位置の観測値を用いて多目標の航跡を生成する際の相関を多次元的に解く技術に関し、特に演算時間を削減しながら許容可能な解を導出することのできる目標追尾装置に関するものである。
【背景技術】
【０００２】
従来から、センサからの観測値を用いて航跡を多次元的に解く技術は、種々提案されており、たとえば、複数サンプリング時刻にわたる観測値の相関をまとめて計算して航跡を生成するアルゴリズムとして、複数フレーム割当法が知られている（たとえば、特許文献１、非特許文献１、非特許文献２参照）。
【０００３】
複数フレーム割当法においては、既存航跡とＮサンプリング時刻にわたる観測値の相関決定を、Ｎ＋１次元の割当問題に変換して解く。Ｎ＋１次元の割当問題は、以下のように表される。
すなわち、以下の式（１）で表される目的関数を、最小とする２値（０か１）変数を決定する。
【０００４】
【数１】
【０００５】
ここで、２値変数は、以下のように表される。
【０００６】
【数２】
【０００７】
ただし、Ｃｊ２・・・ＣｊＮ＋１は、既存航跡および観測値ｉ１・・・ｉＮ＋１から航跡を生成するために要するコストであり、通常航跡尤度比の逆数の対数値を使用する。
上記変数Ｚｊ１・・・ｚｊＮ＋１は、以下の式（２）のように表される。
【０００８】
【数３】
【０００９】
また、上記（１）においては、以下の式（３）〜式（５）の制約条件がある。
すなわち、任意のｉ１について、以下の式（３）のとおりである。
【００１０】
【数４】
【００１１】
また、任意のｉｋ（１＜ｋ＜Ｎ＋１）については、以下の式（４）のとおりである。
【００１２】
【数５】
【００１３】
任意のｉＮ＋１については、以下の式（５）のとおりである。
【００１４】
【数６】
【００１５】
以下、この問題を高速に解く方法として、非特許文献２に記載された処理手順について説明する。
図１１は非特許文献２に記載された従来の目標追尾装置の構成を示すブロック図であり、図１２は図１１の目標追尾装置による処理手順を示すフローチャートである。
【００１６】
図１１において、目標追尾装置１００は、センサ２００からの観測値を入力情報とする航跡候補コスト行列生成手段１１０と、多次元相関決定手段１２０とを備えている。
多次元相関決定手段１２０は、航跡候補コスト行列生成手段１１０からの航跡候補コスト行列を入力情報とする多次元割当問題初期値設定部１２１と、２次元割当解算出部１２２と、多次元割当解算出部１２３とを備えている。また、多次元割当解算出部１２３には、演算結果を表示する表示装置３００が接続されている。
【００１７】
図１２において、目標追尾装置１００は、まず、観測値入力処理（ステップＳＴ１）を行い、センサ２００から得られた過去から最新までのＮサンプリング時刻分の観測値を、航跡候補コスト行列生成手段１１０に取り込む。
【００１８】
続いて、航跡候補コスト行列生成処理（ステップＳＴ２）を行い、既存航跡および各サンプリング時刻から１つずつの観測値を選択し、その観測値の組み合わせによって形成される航跡候補の尤度比を計算し、尤度比の逆数を用いてコストを計算して航跡候補コスト行列を生成する。
【００１９】
次に、多次元相関決定手段１２０において、航跡候補を既存航跡番号と各観測フレームの観測番号のＮ＋１次元の組み合わせと見なし、各航跡候補のコストを用いてＮ＋１次元の割当問題を解く（ステップＳＴ８〜ＳＴ１１）。
まず、多次元割当問題初期値設定処理（ステップＳＴ８）を行い、Ｎ＋１次元の問題をＫ次元の割当問題とし、以下の式（６）により、２次元割当問題に緩和するための各航跡候補のコストの設定を行う。
【００２０】
【数７】
【００２１】
ただし、式（６）において、ｉ１ｉ２ｊ３・・・ｊＮ＋１は、ｉ１ｉ２から構成される航跡候補の中で最小コストを有する航跡候補を示す。また、観測値ｊｒに対応するＬａｇｒａｎｇｅ乗数はＵｊｒであり、初期値はすべて「０」である。
【００２２】
続いて、２次元割当解算出処理（ステップＳＴ９）を行い、２次元割当問題を解く。
２次元割当問題は、演算負荷も少なくかつ厳密解が求められる手法が多く提案されている（たとえば、Ｍｕｎｋｒｅｓ法）。この解は、Ｋ次元割当問題を２次元に緩和した解であることから、Ｋ次元割当解の下解であることが一般的に知られている。
【００２３】
次に、２次元割当許容解判定処理（ステップＳＴ１０）を行い、得られた２次元割当解がＫ次元割当問題の許容解の一部であるか否かを判定する。
ステップＳＴ１０において、前回解が以下の式（７）を満たす場合には、許容解の一部であると判定する。
【００２４】
【数８】
【００２５】
ただし、式（７）において、ｌは、２次元割当問題の解の導出の際の繰り返し回数であり、φｌは、２次元割当解における航跡候補のコストの総和であり、ｔｈｒｅｓｈｏｌｄは、２次元割当解が十分大きい値であると判断するための収束判定閾値である。
【００２６】
ステップＳＴ１０において、前回解が以下の式（７）を満たし、許容解の一部であると判定された場合には、２次元割当解を１次元列に修正し、Ｋ次元割当問題をＫ−１次元割当問題に縮小して、多次元割当問題初期値設定処理（ステップＳＴ８）に戻る。
【００２７】
一方、ステップＳＴ１０において、前回解が式（７）を満たさない場合には、Ｌａｇｒａｎｇｅ乗数を修正して、当該Ｌａｇｒａｎｇｅ乗数に対応したコストを再計算し、多次元割当問題初期値設定処理（ステップＳＴ８）に戻る。
【００２８】
以上の処理（ステップＳＴ８〜ＳＴ１０）を繰り返し実行した後、多次元割当解出力処理（ステップＳＴ１１）」を行い、縮小した次元を元のＮ＋１次元に戻す。このとき、上記式（３）〜式（５）の制約条件を満たし、上記式（１）の許容解を構成する航跡候補組み合わせを導出する。
【００２９】
【特許文献１】特開２００７−２１２２４４号公報
【非特許文献１】Ａ．Ｂ．Ｐｏｏｒｅ ａｎｄ Ａ．Ｊ．ＲｏｂｅｒｔｓｏｎＩＩＩ「Ａ Ｎｅｗ Ｍｕｌｔｉ−ｄｉｍｅｎｓｉｏｎａｌ Ｄａｔａ Ａｓｓｏｃｉａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｍｕｌｔｉｓｅｎｓｏｒ−Ｍｕｌｔｉｔａｒｇｅｔ Ｔｒａｃｋｉｎｇ」 Ｐｒｏｃ． Ｏｆ ＳＰＩＥ ｖｏｌ．２５６１，１９９５．
【非特許文献２】Ａ．Ｂ．Ｐｏｏｒｅ ａｎｄ Ａ．Ｊ．ＲｏｂｅｒｔｓｏｎＩＩＩ「Ａ Ｎｅｗ Ｌａｇｒａｎｇｉａｎ Ｒｅｌａｘａｔｉｏｎ Ｂａｓｅｄ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ａ Ｃｌａｓｓ ｏｆ Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ Ａｓｓｉｇｎｍｅｎｔ Ｐｒｏｂｌｅｍｓ」 Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ８， １２９−１５０， １９９７．
【発明の開示】
【発明が解決しようとする課題】
【００３０】
従来の目標追尾装置では、非特許文献２に記載の複数フレーム割当法を用いた場合、多次元相関決定において許容可能な解を小さい演算負荷で導出しているものの、Ｎ次元の割当問題を２次元割当問題の繰り返しに変換し、２次元割当解の導出において解が収束するまで航跡候補の組み合わせの抽出処理が繰り返し行われるので、観測間隔が短いセンサや演算速度が遅いプラットホームで処理を行うためには、さらなる演算負荷の減少が必要になるという課題があった。
【００３１】
また、特許文献１には、上記課題の解決策として、通常は２次元相関を行い、かつ一定フレーム間隔で複数フレーム割当法による相関を行い、演算時間増大フレームを制限することにより、演算負荷の減少を実現しているが、この場合、複数フレーム割当法を行うフレームにおける観測値と既存航跡との関係にかかわらず、観測フレーム数を減少させることから、導出解精度の悪化や、当該フレームでは演算時間が減少せずに、次のフレームの演算時間が消費されるという課題あった。
【００３２】
この発明は、上記のような課題を解決するためになされたものであり、航跡候補の中から、航跡候補の航跡番号と構成される観測値と航跡候補のコストとの関係から抽出される航跡組み合わせを予想し、予想された関係から、抽出される航跡が分離しているか否かを判別し、その分離状況に応じて、多次元相関決定における初期解の設定または収束判定の緩和を行うことにより、多次元相関決定においてさらなる演算負荷の減少を実現するとともに、許容可能な解を導出することのできる目標追尾装置を得ることを目的とする。
【課題を解決するための手段】
【００３３】
この発明による目標追尾装置は、センサからの観測値を入力情報とする航跡候補コスト行列生成手段と、航跡分離状況判定手段と、多次元相関決定手段と、を備えた目標追尾装置であって、航跡候補コスト行列生成手段は、現在までの最新Ｎフレームの観測値の観測番号と現在からＮ＋１フレーム前に生成された航跡の航跡番号との組み合わせを作成して、観測番号と航跡番号との複数の組み合わせの各々を航跡候補と見なす航跡候補行列と、航跡候補の各々に対応するコストからなるコスト配列と、を生成し、航跡分離状況判定手段は、航跡候補の各々で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、を対比することにより航跡の分離状況を判定して、航跡が分離していると判定された場合には、航跡候補コスト行列生成手段に対し、最新Ｍ（≦Ｎ）フレームの観測値を用いて、航跡候補行列と航跡候補の各々とに対応するコストからなるコスト配列を再生成するように指示し、多次元相関決定手段は、航跡候補行列とコスト配列とからＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出するものである。
【発明の効果】
【００３４】
この発明によれば、多次元相関決定において演算負荷の減少を実現するとともに、許容可能な解を導出することができる。
【発明を実施するための最良の形態】
【００３５】
実施の形態１．
図１はこの発明の実施の形態１に係る目標追尾装置１００Ａの構成を示すブロック図であり、前述（図１１）と同様のものについては、前述と同一符号を付して、または符号の後に「Ａ」を付して詳述を省略する。
図１において、目標追尾装置１００Ａは、航跡候補コスト行列生成手段１１０Ａと、多次元相関決定手段１２０と、航跡分離状況判定手段１３０と、を備えている。
【００３６】
航跡候補コスト行列生成手段１１０Ａは、既存航跡とセンサ２００からの観測値の航跡候補とを生成し、各航跡候補に対応するコストを算出する。
多次元相関決定手段１２０は、航跡候補コスト行列生成手段１１０Ａにより生成された航跡候補と対応するコストとから、当該観測フレームにおける最適航跡候補群の抽出を、Ｎ＋１次元割当問題として前述と同様の処理により解く。
【００３７】
航跡分離状況判定手段１３０は、最小コスト航跡抽出部１３１と、最小コスト算出諸元設定部１３２と、航跡分離状況判定部１３３と、を備えている。
航跡分離状況判定手段１３０は、抽出される航跡が分離しているか否かを判定し、分離していると判定された場合には、航跡候補コスト行列生成手段１１０Ａに対して、最新Ｎ観測フレームの利用の元で、最新Ｍ観測フレームでの航跡候補の再生成およびコストの再算出を指示する。なお、「Ｍ（≦Ｎ）」の値は、「３（航跡が確立する最低観測フレーム数）」以上に設定される。
目標追尾装置１００Ａで確立した航跡は、表示装置３００により表示される。
【００３８】
次に、図２のフローチャートと図３および図４の説明図とを参照しながら、図１に示したこの発明の実施の形態１による動作について説明する。ここでは、特に、航跡分離状況判定手段１３０を中心とした動作について説明する。
【００３９】
図２において、前述（図１２）と同様の処理（ステップＳＴ１、ＳＴ２、ＳＴ８〜ＳＴ１１）については、前述と同一符号が付されている。
図３は、Ｎ＝４、既存航跡数＝２、各観測フレームでの観測値数＝２〜３の場合の航跡候補の組み合わせ行列の例を示している。また、図４は、各最小コスト算出諸元設定値での抽出結果の例を示している。
【００４０】
図２において、まず、航跡候補コスト行列生成手段１１０Ａは、センサ２００から得られた観測値を取り込むとともに（ステップＳＴ１）、多次元割当解算出部１２３から出力された既存航跡の組み合わせを作成して、たとえば図３のように、コスト（航跡候補コスト行列）を算出する（ステップＳＴ２）。
【００４１】
図３においては、４フレーム分のスライディングウィンドウ（２点鎖線枠）内の各時刻ｔ１〜ｔ４で選択される、既存軌跡（１）（１点鎖線矢印）および既存軌跡（２）（実線矢印）の観測値ａ１、ａ２、ａ３（黒四角点）と、観測値の組み合わせ（点線枠）で示される各航跡候補およびコスト（尤度比の逆数）とが示されている。
【００４２】
図３内の観測値ａに付された数字「１」〜「３」は、観測番号を示している。
また、航跡候補（０）〜（２）において、航跡候補（０）は、既存航跡との相関が存在しないことを示し、「０」は、相関観測値が存在しないことを示している。
【００４３】
次に、最小コスト航跡抽出部１３１は、生成された航跡組候補の組み合わせ行列から、最小コスト算出諸元設定部１３２での設定値判定処理（ステップＳＴ３）を行い、設定値が「０」の場合には、ステップＳＴ４に進み、設定値が「１」の場合には、ステップＳＴ５に進む。
【００４４】
ステップＳＴ４（設定値＝０）においては、各航跡番号の中で最小コストとなる航跡候補を選択し、さらに最新観測フレームの各観測番号において最小コストとなる航跡候補を選択し、選択された各航跡候補における航跡番号と観測番号との組み合わせを、たとえば図４の抽出結果のように生成して、次の判定処理（ステップＳＴ６）に進む。
【００４５】
一方、ステップＳＴ５（設定値＝１）においては、最新Ｍ＋１観測フレームにおける観測番号において最小コストとなる航跡候補を選択し、さらに最新観測フレームの各観測番号において最小コストとなる航跡候補を選択し、選択された各航跡候補における航跡番号と観測番号との組み合わせを、たとえば図４の抽出結果のように生成して、次の判定処理（ステップＳＴ６）に進む。
【００４６】
図４においては、過去４フレーム分の時刻ｔ１〜ｔ４での各航跡番号（０）〜（２）の航跡候補に基づく、各ステップＳＴ４、ＳＴ５による導出（抽出）結果が具体的に示されている。
ここでは、ステップＳＴ４による導出結果として、航跡番号（１）に関しては、観測番号「１」（観測値ａ１）の最小コスト「−２．４」が抽出され、航跡番号（２）に関しては、観測番号「３」（観測値ａ３）の最小コスト「−６．２」が抽出されている。
【００４７】
同様に、ステップＳＴ５による導出（抽出）結果として、航跡番号（１）に関しては、観測番号「１」（観測値ａ１）の最小コスト「−２．４」が抽出され、航跡番号（２）に関しては、観測番号「３」（観測値ａ３）の最小コスト「−６．２」が抽出されている。
この結果、各航跡番号（１）、（０）、（２）での最小コスト航跡候補として、それぞれ、観測番号「１」の最小コスト「−２．４」、観測番号「２」の最小コスト「−０．５」、観測番号「３」の最小コスト「−６．２」が抽出される。
【００４８】
次に、航跡分離状況判定部１３３は、上記の２つの観点から抽出した航跡番号と観測番号との組み合わせを比較し（ステップＳＴ６）、抽出した航跡候補組み合わせで同一航跡番号および同一観測点番号の抽出がなく、かつ、一定数以上の航跡番号と観測番号との組み合わせが一致した場合には、航跡は分離しているものと判定する。
【００４９】
ステップＳＴ６による組み合わせの一致判定において、航跡番号数と観測番号数とが異なる場合には、少ない数の組み合わせでの判定を行う。
また、一定数の設定の例として、正解航跡を誤航跡と認識する確率（一般的に、「０．１」などの値）を「１」から減算した確率を設定する方法が挙げられる。
【００５０】
ステップＳＴ６において航跡が分離していると判定された場合には、航跡分離状況判定部１３３は、最小コスト算出諸元設定部１３２であらかじめ設定されている観測フレーム数Ｍを航跡候補コスト行列生成手段１１０Ａに入力する。
一方、ステップＳＴ６において航跡が分離していないと判定された場合には、航跡分離状況判定部１３３は、観測フレーム数Ｎを航跡候補コスト行列生成手段１１０Ａに入力する。
【００５１】
航跡候補コスト行列生成手段１１０Ａは、観測フレーム数＝Ｍ（航跡が分離）を入力した場合には、指定観測フレーム数での航跡候補の組み合わせ行列を生成して、コスト（航跡候補コスト行列）を算出して出力する（ステップＳＴ７）。
一方、観測フレーム数＝Ｎ（航跡の分離なし）を入力した場合には、航跡候補コスト行列生成手段１１０Ａは、すでに生成した航跡候補の組み合わせ行列およびコストを出力する。
【００５２】
以下、多次元相関決定手段１２０内の多次元割当問題初期値設定部１２１は、Ｎ（Ｍ）＋１次元の航跡候補の組み合わせ行列およびコストを、Ｋ次元の多次元相関問題として、前述の式（６）のように、Ｋ次元の問題を２次元割当問題に緩和するための各航跡候補のコストの設定を行う（ステップＳＴ８）。
【００５３】
続いて、２次元割当解算出部１２２は、前述と同様に２次元割当問題を解く（ステップＳＴ９）。
２次元割当問題は、演算負荷も少なくかつ厳密解が求められる手法が多く提案されている（たとえば、Ｍｕｎｋｒｅｓ法）。この解は、Ｋ次元割当問題を緩和した解であることから、Ｋ次元割当解の下解であることが一般的に知られている。
【００５４】
また、２次元割当解算出部１２２は、得られた２次元割当解がＫ次元割当問題の許容解の一部であるか否かを判定する（ステップＳＴ１０）。
すなわち、前回解が前述の式（７）を満たす場合には、許容解の一部であると判定し、前回解が式（７）を満たさない場合には、Ｌａｇｒａｎｇｅ乗数を修正して、当該Ｌａｇｒａｎｇｅ乗数に対応したコストを再計算し、多次元割当問題初期値設定部１２１に出力する。
【００５５】
ステップＳＴ１０において、許容解の一部であると判定された場合には、２次元割当解を１次元列に修正し、Ｋ次元割当問題をＫ−１次元割当問題に縮小して、多次元割当問題初期値設定部１２１に出力する。このとき、Ｌａｇｒａｎｇｅ乗数はすべて「０」に初期化する。
【００５６】
以上の処理（ステップＳＴ８〜ＳＴ１０）を繰り返し実行した後、縮小した次元を元のＮ（Ｍ）＋１次元に戻し、航跡候補組み合わせを導出する（ステップＳＴ１１）。
このように、抽出される航跡の分離状況を、航跡候補の航跡番号と観測番号とコストとの関係から予測し、航跡が分離していると推測される場合には、多次元相関決定手段１２０に入力する航跡候補を構成する観測フレーム数を減少させることにより、多次元相関決定の解の精度の劣化を抑えつつ演算負荷を軽減することができる。
【００５７】
以上のように、この発明の実施の形態１（図１、図２）に係る目標追尾装置１００Ａは、センサ２００からの観測値を入力情報とする航跡候補コスト行列生成手段１１０Ａと、航跡分離状況判定手段１３０と、多次元相関決定手段１２０と、を備えており、航跡候補コスト行列生成手段１１０Ａは、現在までの最新Ｎフレームの観測値の観測番号と現在からＮ＋１フレーム前に生成された航跡の航跡番号との組み合わせを作成して、観測番号と航跡番号との複数の組み合わせの各々を航跡候補と見なす航跡候補行列と、航跡候補の各々に対応するコストからなるコスト配列と、を生成する。
【００５８】
航跡分離状況判定手段１３０は、航跡候補の各々で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、を対比することにより航跡の分離状況を判定して、航跡が分離していると判定された場合には、航跡候補コスト行列生成手段１１０Ａに対し、最新Ｍ（≦Ｎ）フレームの観測値を用いて、航跡候補行列と航跡候補の各々とに対応するコストからなるコスト配列を再生成するように指示する。
【００５９】
また、航跡分離状況判定手段１３０は、利用する観測フレームを縮小したときに航跡候補行列に残らない最新の観測フレームにおける各観測番号で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と最新の観測フレームにおける各観測番号との組み合わせと、を対比することにより各航跡の分離状況を判定する
【００６０】
さらに、多次元相関決定手段１２０は、航跡候補行列およびコスト配列からＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
これにより、航跡が分離していると推測される場合には、多次元相関決定手段１２０に入力する航跡候補を構成する観測フレーム数を減少させることができ、多次元相関決定の解の精度の劣化を抑えつつ演算負荷を軽減することができる。
【００６１】
実施の形態２．
なお、上記実施の形態１（図１、図２）では、航跡分離状況判定手段１３０において、最小コストを有する航跡候補の航跡番号と最新観測フレームにおける観測番号との組み合わせから、航跡の分離状況を判定したが、このとき、コストの小さい航跡候補が航跡として抽出される可能性がある。
【００６２】
したがって、図５のように、航跡分離状況判定手段１３０Ｂ内に航跡コスト分散算出部１３４を設けることにより、航跡候補のコストの分散から航跡のコストのばらつきを求め、コストの小さい航跡候補の集合における各航跡候補の航跡番号と観測番号との共有度から、航跡の分離状況を判定してもよい。
【００６３】
図５はこの発明の実施の形態２に係る目標追尾装置１００Ｂの構成を示すブロック図であり、前述（図１）と同様のものについては、前述と同一符号を付して、または符号の後に「Ｂ」を付して詳述を省略する。
図５において、目標追尾装置１００Ｂ内の航跡分離状況判定手段１３０Ｂは、前述（図１）の最小コスト航跡算出部１３１に代えて、航跡コスト分散算出部１３４を備えている。他の構成は、図１に示したとおりである。
【００６４】
航跡コスト分散算出部１３４は、航跡候補のコストの分散を算出し、平均値から標準偏差以下のコストを有する航跡候補を抽出する。
以下、航跡分離状況判定部１３３Ｂは、抽出された航跡候補での航跡番号の重複度が一定値以下であり、かつ、各航跡番号での同一観測フレームでの観測番号の重複度が一定値以下である場合に、航跡は分離しているものと判定する。
【００６５】
航跡が分離していると判定された場合には、航跡分離状況判定部１３３Ｂは、航跡候補コスト行列生成手段１１０Ａに対して、最新Ｎ観測フレームの利用の元で、最新Ｍ観測フレーム（Ｎ≧Ｍ、Ｍ＝３（航跡が確立する最低観測フレーム数）以上）での航跡候補の再生成およびコストの再算出を指示する。
【００６６】
次に、図６のフローチャートを参照しながら、この発明の実施の形態２による航跡分離状況判定手段１３０Ｂの動作について説明する。ここでは、前述の実施の形態１（図２）との変更点を中心に説明する。
図６において、ステップＳＴ１、ＳＴ２、ＳＴ７〜ＳＴ１１は、前述（図２）と同様の処理であり、ステップＳＴ５１、ＳＴ６１は、前述のステップＳＴ６に対応する。
【００６７】
まず、観測値入力処理（ステップＳＴ１）および航跡候補コスト行列生成処理（ステップＳＴ２）に続いて、航跡コスト分散算出部１３４は、航跡候補のコストの平均値および分散を算出し（ステップＳＴ３１）、分散の平方根である標準偏差を算出して、平均値−標準偏差×定数倍（たとえば、定数＝１）の小コストを有する航跡候補を抽出する（ステップＳＴ４１）。
【００６８】
次に、航跡分離状況判定部１３３Ｂは、航跡コスト分散算出部１３４により抽出された航跡候補に対する航跡番号の重複度（重複割合）が一定値以下であるか否かを判定する（ステップＳＴ５１）。もし、航跡番号の抽出航跡に対する重複度が一定値以下の場合には、続いて、各航跡の観測番号の重複度が一定値以下であるか否かを判定する（ステップＳＴ６１）。
【００６９】
このとき、ステップＳＴ５１、ＳＴ６１での重複度判定基準となる一定値は、平均値からの差分に合わせて設定され、今回の例では、標準偏差であることから、たとえば３３％に設定される。
ステップＳＴ６１において、観測番号の重複度が一定値（航跡番号の重複度判定の場合と同一値）以下と判定された場合には、航跡分離状況判定部１３３Ｂは、航跡が分離しているものと判定する。
【００７０】
航跡分離状況判定部１３３Ｂは、航跡が分離していると判定された場合には、最小コスト算出諸元設定部１３２であらかじめ設定されている観測フレーム数Ｍを航跡候補コスト行列生成手段１１０Ａに入力し、航跡が分離していないと判定された場合には、観測フレーム数Ｎを航跡候補コスト行列生成手段１１０Ａに入力する。
上記以外の動作については、前述の実施の形態１と同様である。
【００７１】
以上のように、この発明の実施の形態２（図５、図６）によれば、航跡分離状況判定手段１３０Ｂは、航跡候補のコストの平均値からコストの標準偏差以下となるコストを有する航跡候補において、同一航跡番号および観測番号を有する航跡数から航跡の分離状況を判定する。
【００７２】
すなわち、航跡候補のコストの分散から航跡のコストのばらつきを求め、コストの小さい航跡候補の集合における各航跡候補の航跡番号と観測番号との共有度から、航跡の分離状況を判定する。
【００７３】
このように、航跡が分離していると推測される場合に、多次元相関決定手段に入力する航跡候補を構成する観測フレーム数を減少させることにより、多次元相関決定の解の精度の劣化を抑えつつ演算負荷を軽減することができる。
すなわち、抽出される航跡の分離状況を判定する際に、コストの小さい航跡候補が航跡として抽出される可能性があるが、多次元相関決定の解の精度の劣化を抑えることができる。
【００７４】
実施の形態３．
なお、上記実施の形態２（図５、図６）では、航跡分離状況判定手段１３０Ｂ内に航跡コスト分散算出部１３４を設け、航跡が分離していると判定された場合にのみ航跡候補を構成する観測フレーム数を減少させることにより、多次元相関決定の解の精度の劣化を抑えつつ演算負荷を軽減したが、図７、図６のように、多次元相関決定手段１２０Ｃ内に多次元割当問題初期値修正部１２４を設け、航跡が分離していると判定された場合に、航跡候補を構成する観測フレーム数はそのままに保持して、多次元相関決定の初期値を修正し、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の演算負荷を減少してもよい。
【００７５】
図７はこの発明の実施の形態３に係る目標追尾装置１００Ｃの構成を示すブロック図であり、前述（図１）と同様のものについては、前述と同一符号を付して、または符号の後に「Ｃ」を付して詳述を省略する。
【００７６】
図７において、目標追尾装置１００Ｃ内の多次元相関決定手段１２０Ｃは、前述（図１）の構成に加えて、多次元割当問題初期値修正部１２４を備えている。
多次元割当問題初期値修正部１２４からの修正情報は、多次元割当問題初期値設定部１２１Ｃに入力されている。他の構成は、図１に示したとおりである。
【００７７】
航跡分離状況判定手段１３０Ｃ内の航跡分離状況判定部１３３Ｃは、航跡が分離していると判定された場合には、組み合わせ同一航跡候補を出力する。
多次元相関決定手段１２０Ｃ内の多次元割当問題初期値修正部１２４は、組み合わせ同一航跡候補に応答して、抽出された航跡候補のコスト修正量を「０」に設定し、それ以外の航跡候補のコスト修正量を「正の一定値」に設定する。
【００７８】
なお、コスト修正量の「正の一定値」は、たとえば、抽出航跡を航跡表示装置３００に表示させる判定閾値の絶対値に設定される。
多次元割当問題初期値設定部１２１Ｃにおいて、航跡候補のコストに当該コスト修正量を加え、多次元相関決定における各航跡候補の初期コストとする。
【００７９】
次に、図８のフローチャートを参照しながら、この発明の実施の形態３による多次元相関決定手段１２０Ｃの動作について説明する。ここでは、前述の実施の形態１（図２）との変更点を中心に説明する。
【００８０】
図８において、ステップＳＴ１〜ＳＴ６、ＳＴ８〜ＳＴ１１は、前述（図２）と同様の処理であり、ステップＳＴ７１は、前述のステップＳＴ７に対応する。また、ステップＳＴ７１とステップＳＴ８との間に、ステップＳＴ７２が挿入されている。
【００８１】
目標追尾装置１００Ｃは、まず、前述と同様の処理（ステップＳＴ１〜ＳＴ６）を行い、航跡分離状況判定部１３３Ｃ（ステップＳＴ６）において、航跡が分離していると判定された場合には、組み合わせ同一航跡候補を抽出して出力する（ステップＳＴ７１）。
【００８２】
続いて、多次元割当問題初期値修正１２４は、抽出航跡候補のコスト修正量を「０」と設定し、抽出航跡候補以外の航跡候補のコスト修正量を「正の一定値」に設定する（ステップＳＴ７２）。
【００８３】
以下、多次元割当問題初期値設定部１２１Ｃは、航跡候補の組み合わせ行列およびコストを、Ｋ次元の多次元相関問題として、Ｋ次元の問題を２次元割当問題に緩和するための各航跡候補のコストの設定を、以下の式（８）のように、コスト修正量を加えて行う（ステップＳＴ８）。
【００８４】
【数９】
【００８５】
ここで、ｉ１ｉ２ｊ３・・・ｊＮ＋１からなる航跡候補が抽出されている場合には、以下の式（９）が成立する。
【００８６】
【数１０】
【００８７】
また、ｉ１ｉ２ｊ３・・・ｊＮ＋１からなる航跡候補が抽出されていない場合には、以下の式（１０）が成立する。
【００８８】
【数１１】
【００８９】
ただし、式（１０）において、Ａは正数値（たとえば、航跡確立閾値の絶対値）である。
上記以外の動作については、前述の実施の形態１と同様である。
【００９０】
以上のように、この発明の実施の形態３（図７、図８）によれば、多次元相関決定手段１２０Ｃは、航跡分離状況判定部１３３Ｃにより航跡が分離していると判定された場合には、航跡候補の観測フレーム数を縮小してコストを再計算することを禁止して、２次元割当問題の解の精度判定閾値を緩和し、航跡候補行列およびコスト配列からＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
【００９１】
また、多次元相関決定手段１２０Ｃは、航跡分離状況判定部１３３Ｃにより航跡が分離していると判定された場合には、２次元割当問題の解がＫ次元割当問題の許容解の一部であるか否かの判定閾値を緩和し、航跡候補行列およびコスト配列からＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
【００９２】
このように、航跡の分離状況を判定して、航跡が分離していると判定される場合には、航跡候補を構成する観測フレーム数はそのままに保持して、多次元相関決定の初期値を修正し、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の精度劣化を抑えつつ演算負荷を軽減することができる。
【００９３】
また、多次元割当問題初期値修正部１２４を用いた多次元相関決定手段の構成は、前述の実施の形態２（図５）の航跡分離状況判定手段１３０Ｂに対しても適用することができ、同等の作用効果を奏することは言うまでもない。
【００９４】
実施の形態４．
なお、上記実施の形態３（図７、図８）では、多次元割当問題初期値修正部１２４を設け、航跡が分離していると判定される場合には、航跡候補を構成する観測フレーム数はそのままに保持して、多次元相関決定の初期値を修正し、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の演算負荷を軽減したが、図９、図１０のように、収束判定閾値修正部１２５を設け、航跡が分離していると判定される場合には、２次元割当解がＫ次元の許容解の一部であるか否かの判定における収束閾値を緩和して、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の演算負荷を軽減してもよい。
【００９５】
図９はこの発明の実施の形態４に係る目標追尾装置１００Ｄの構成を示すブロック図であり、前述（図１、図７）と同様のものについては、前述と同一符号を付して、または符号の後に「Ｄ」を付して詳述を省略する。
【００９６】
図９において、目標追尾装置１００Ｄ内の多次元相関決定手段１２０Ｄは、前述（図７）の多次元割当問題初期値修正部１２４に代えて、収束判定閾値修正部１２５を備えている。他の構成は、図７に示したとおりである。
【００９７】
航跡分離状況判定手段１３０Ｄ内の航跡分離状況判定部１３３Ｄは、航跡が分離していると判定された場合には、航跡分離情報を出力する。
【００９８】
多次元相関決定手段１２０Ｄ内の収束判定閾値修正部１２５は、航跡分離情報に応答して、航跡が分離していると判定される場合には、２次元割当解算出部１２２Ｄで用いられる閾値の緩和値Ｂを設定する。
緩和値Ｂで緩和された後の閾値ｔｈｒｅｓｈｏｌｄ’は、元の閾値ｔｈｒｅｓｈｏｌｄを用いて、以下の式（１１）で表される。
【００９９】
【数１２】
【０１００】
ただし、式（１１）において、緩和値Ｂは一定値（たとえば、「１０」）である。
緩和後の閾値ｔｈｒｅｓｈｏｌｄ’は、２次元割当解算出部１２２Ｄにおいて、２次元割当解がＫ次元割当問題の許容解の一部であるか否かを判定する際に用いられる。
【０１０１】
次に、図１０のフローチャートを参照しながら、この発明の実施の形態４による多次元相関決定手段１２０Ｄの動作について説明する。ここでは、前述の実施の形態１、３（図２、図８）との変更点を中心に説明する。
図１０において、ステップＳＴ１〜ＳＴ６、ＳＴ８〜ＳＴ１１は、前述（図２、図８）と同様の処理であり、ステップＳＴ６とステップＳＴ９との間に、ステップＳＴ７３が挿入されている。
【０１０２】
図１０内のステップＳＴ６において、航跡分離状況判定手段１３０Ｄ内の航跡分離状況判定部１３３Ｄは、航跡が分離しているか否かの判定結果（分離の有無を示す）として航跡分離情報を出力する。
【０１０３】
収束判定閾値修正部１２５は、航跡分離情報が「航跡分離あり」を示す場合には、収束閾値（収束値）として、デフォルト設定閾値の定数（緩和値Ｂ）倍した修正値を設定する（ステップＳＴ７３）。
以下、２次元割当解算出部１２２Ｄは、修正された収束閾値を用いて、２次元割当解がＫ次元割当問題の許容解の一部であるか否かの判定を行う（ステップＳＴ９）。
上記以外の動作については、前述の実施の形態１と同様である。
【０１０４】
以上のように、この発明の実施の形態４（図９、図１０）によれば、多次元相関決定手段１２０Ｄは、航跡分離状況判定手段１３０Ｄにより航跡が分離していると判定された場合には、航跡分離状況判定で抽出された航跡候補の２次元割当問題導出時コストの初期値を「０」に設定し、航跡分離状況判定で抽出されなかった航跡候補の２次元割当問題導出時コストの初期値として航跡候補コストに「正数値」を付加し、航跡候補行列およびコスト配列からＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出する。
【０１０５】
このように、２次元割当解がＫ次元の許容解の一部であるか否かの判定における収束閾値を緩和して、多次元相関決定の２次元割当解の収束回数を少なくすることにより、多次元相関決定の２次元割当解の演算負荷を軽減することができる。
【０１０６】
なお、収束判定閾値修正部１２５を用いた多次元相関決定手段の構成は、前述の実施の形態２（図５）の航跡分離状況判定手段１３０Ｂに対しても適用することができ、同等の作用効果を奏することは言うまでもない。
【図面の簡単な説明】
【０１０７】
【図１】この発明の実施の形態１に係る目標追尾装置の構成を示すブロック図である。
【図２】この発明の実施の形態１による動作を示すフローチャートである。
【図３】この発明の実施の形態１における航跡候補の組み合わせ行列の例を示す説明図である。
【図４】この発明の実施の形態１における各最小コスト算出諸元設定値での抽出結果の例を示す説明図である。
【図５】この発明の実施の形態２に係る目標追尾装置の構成を示すブロック図である。
【図６】この発明の実施の形態２による動作を示すフローチャートである。
【図７】この発明の実施の形態３に係る目標追尾装置の構成を示すブロック図である。
【図８】この発明の実施の形態３による動作を示すフローチャートである。
【図９】この発明の実施の形態４に係る目標追尾装置の構成を示すブロック図である。
【図１０】この発明の実施の形態４による動作を示すフローチャートである。
【図１１】従来の目標追尾装置の構成を示すブロック図である。
【図１２】従来の目標追尾装置による動作を示すフローチャートである。
【符号の説明】
【０１０８】
１００Ａ、１００Ｂ、１００Ｃ、１００Ｄ 目標追尾装置、１１０Ａ 航跡候補コスト行列生成手段、１２０、１２０Ｃ、１２０Ｄ 多次元相関決定手段、１２１、１２１Ｃ、１２１Ｄ 多次元割当問題初期値設定部、１２２、１２２Ｄ ２次元割当解算出部、１２３ 多次元割当解算出部、１２４ 多次元割当問題初期値修正部、１２５ 収束判定閾値修正部、１３０、１３０Ｂ 航跡分離状況判定手段、１３１ 最小コスト航跡抽出部、１３２ 最小コスト算出諸元設定部、１３３、１３３Ｃ、１３３Ｄ 航跡分離状況判定部、１３４ 航跡コスト分散算出部、２００ センサ。
【特許請求の範囲】
【請求項１】
センサからの観測値を入力情報とする航跡候補コスト行列生成手段と、
航跡分離状況判定手段と、
多次元相関決定手段と、
を備えた目標追尾装置であって、
前記航跡候補コスト行列生成手段は、
現在までの最新Ｎフレームの観測値の観測番号と現在からＮ＋１フレーム前に生成された航跡の航跡番号との組み合わせを作成して、前記観測番号と前記航跡番号との複数の組み合わせの各々を航跡候補と見なす航跡候補行列と、前記航跡候補の各々に対応するコストからなるコスト配列と、を生成し、
前記航跡分離状況判定手段は、
前記航跡候補の各々で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、前記最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と前記最新観測フレームの観測番号との組み合わせと、を対比することにより航跡の分離状況を判定して、前記航跡が分離していると判定された場合には、前記航跡候補コスト行列生成手段に対し、最新Ｍ（≦Ｎ）フレームの観測値を用いて、前記航跡候補行列と前記航跡候補の各々とに対応するコストからなるコスト配列を再生成するように指示し、
前記多次元相関決定手段は、
前記航跡候補行列と前記コスト配列とからＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出することを特徴とする目標追尾装置。
【請求項２】
前記航跡分離状況判定手段は、利用する観測フレームを縮小したときに前記航跡候補行列に残らない最新の観測フレームにおける各観測番号で最小コストを有する航跡候補の航跡番号と前記最新観測フレームの観測番号との組み合わせと、前記最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と最新の観測フレームにおける各観測番号との組み合わせと、を対比することにより各航跡の分離状況を判定することを特徴とする請求項１に記載の目標追尾装置。
【請求項３】
前記航跡分離状況判定手段は、前記航跡候補のコストの平均値からコストの標準偏差以下となるコストを有する航跡候補において、同一航跡番号および観測番号を有する航跡数から航跡の分離状況を判定することを特徴とする請求項１に記載の目標追尾装置。
【請求項４】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、前記航跡候補の観測フレーム数を縮小してコストを再計算することを禁止して、Ｋ次元割当問題の許容解の一部であるか否かの判定閾値を緩和し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項１に記載の目標追尾装置。
【請求項５】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、前記２次元割当問題の解がＫ次元割当問題の許容解の一部であるか否かの判定閾値を緩和し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項２に記載の目標追尾装置。
【請求項６】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、前記２次元割当問題の解がＫ次元割当問題の許容解の一部であるか否かの判定閾値を緩和し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出する多次元相関決定手段を、備えたことを特徴とする請求項３に記載の目標追尾装置。
【請求項７】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、航跡分離状況判定で抽出された航跡候補の２次元割当問題導出時コストの初期値を０に設定し、前記航跡分離状況判定で抽出されなかった航跡候補の２次元割当問題導出時コストの初期値として航跡候補コストに正数値を付加し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項１に記載の目標追尾装置。
【請求項８】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、航跡分離状況判定で抽出された航跡候補の２次元割当問題導出時コストの初期値を０に設定し、前記航跡分離状況判定で抽出されなかった航跡候補の２次元割当問題導出時コストの初期値として航跡候補コストに正数値を付加し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項２に記載の目標追尾装置。
【請求項９】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、航跡分離状況判定で抽出された航跡候補の２次元割当問題導出時コストの初期値を０に設定し、前記航跡分離状況判定で抽出されなかった航跡候補の２次元割当問題導出時コストの初期値として航跡候補コストに正数値を付加し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項３に記載の目標追尾装置。
【請求項１】
センサからの観測値を入力情報とする航跡候補コスト行列生成手段と、
航跡分離状況判定手段と、
多次元相関決定手段と、
を備えた目標追尾装置であって、
前記航跡候補コスト行列生成手段は、
現在までの最新Ｎフレームの観測値の観測番号と現在からＮ＋１フレーム前に生成された航跡の航跡番号との組み合わせを作成して、前記観測番号と前記航跡番号との複数の組み合わせの各々を航跡候補と見なす航跡候補行列と、前記航跡候補の各々に対応するコストからなるコスト配列と、を生成し、
前記航跡分離状況判定手段は、
前記航跡候補の各々で最小コストを有する航跡候補の航跡番号と最新観測フレームの観測番号との組み合わせと、前記最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と前記最新観測フレームの観測番号との組み合わせと、を対比することにより航跡の分離状況を判定して、前記航跡が分離していると判定された場合には、前記航跡候補コスト行列生成手段に対し、最新Ｍ（≦Ｎ）フレームの観測値を用いて、前記航跡候補行列と前記航跡候補の各々とに対応するコストからなるコスト配列を再生成するように指示し、
前記多次元相関決定手段は、
前記航跡候補行列と前記コスト配列とからＬａｇｒａｎｇｅ緩和法を用いて、Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、最適航跡組み合わせを抽出することを特徴とする目標追尾装置。
【請求項２】
前記航跡分離状況判定手段は、利用する観測フレームを縮小したときに前記航跡候補行列に残らない最新の観測フレームにおける各観測番号で最小コストを有する航跡候補の航跡番号と前記最新観測フレームの観測番号との組み合わせと、前記最新観測フレームの各観測番号で最小コストを有する航跡候補の航跡番号と最新の観測フレームにおける各観測番号との組み合わせと、を対比することにより各航跡の分離状況を判定することを特徴とする請求項１に記載の目標追尾装置。
【請求項３】
前記航跡分離状況判定手段は、前記航跡候補のコストの平均値からコストの標準偏差以下となるコストを有する航跡候補において、同一航跡番号および観測番号を有する航跡数から航跡の分離状況を判定することを特徴とする請求項１に記載の目標追尾装置。
【請求項４】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、前記航跡候補の観測フレーム数を縮小してコストを再計算することを禁止して、Ｋ次元割当問題の許容解の一部であるか否かの判定閾値を緩和し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項１に記載の目標追尾装置。
【請求項５】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、前記２次元割当問題の解がＫ次元割当問題の許容解の一部であるか否かの判定閾値を緩和し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項２に記載の目標追尾装置。
【請求項６】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、前記２次元割当問題の解がＫ次元割当問題の許容解の一部であるか否かの判定閾値を緩和し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出する多次元相関決定手段を、備えたことを特徴とする請求項３に記載の目標追尾装置。
【請求項７】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、航跡分離状況判定で抽出された航跡候補の２次元割当問題導出時コストの初期値を０に設定し、前記航跡分離状況判定で抽出されなかった航跡候補の２次元割当問題導出時コストの初期値として航跡候補コストに正数値を付加し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項１に記載の目標追尾装置。
【請求項８】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、航跡分離状況判定で抽出された航跡候補の２次元割当問題導出時コストの初期値を０に設定し、前記航跡分離状況判定で抽出されなかった航跡候補の２次元割当問題導出時コストの初期値として航跡候補コストに正数値を付加し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項２に記載の目標追尾装置。
【請求項９】
前記多次元相関決定手段は、前記航跡分離状況判定手段により前記航跡が分離していると判定された場合には、航跡分離状況判定で抽出された航跡候補の２次元割当問題導出時コストの初期値を０に設定し、前記航跡分離状況判定で抽出されなかった航跡候補の２次元割当問題導出時コストの初期値として航跡候補コストに正数値を付加し、前記航跡候補行列および前記コスト配列から前記Ｌａｇｒａｎｇｅ緩和法を用いて、前記Ｎ＋１次元割当問題を２次元割当問題の繰り返しとして解くことにより、前記最適航跡組み合わせを抽出することを特徴とする請求項３に記載の目標追尾装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−１５１６３７（Ｐ２０１０−１５１６３７Ａ）
【公開日】平成２２年７月８日（２０１０．７．８）
【国際特許分類】
【出願番号】特願２００８−３３０４３２（Ｐ２００８−３３０４３２）
【出願日】平成２０年１２月２５日（２００８．１２．２５）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２２年７月８日（２０１０．７．８）
【国際特許分類】
【出願日】平成２０年１２月２５日（２００８．１２．２５）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]