多目標追尾装置
【課題】従来の多目標追尾装置は、N次元の相関を毎サンプリング毎に求めるため演算負荷が大きく、また許容可能な時間で解導出を繰り返しても閾値条件を満たす準最適解を得ることができず、尤度の低い相関解しか得られないことがある。
【解決手段】センサの観測回数が設定値の整数倍か否か判別し、整数倍以外のときは、２次元相関算出部で観測値と既追尾航跡の相関を取り、新たな航跡を生成・出力し、整数倍のときは、コスト行列更新部で観測値からコスト行列を1サンプリング毎に更新しながら算出し、Lagrange乗数設定部でコスト行列に基づきLagrange緩和法により求められたLagrange乗数によってLagrange緩和解算出部で緩和された制約条件下で相関解を計算し、実現可能解算出部でこの緩和解を修正して全ての制約条件を満たす解を求め、新たな航跡を生成・出力する。
【解決手段】センサの観測回数が設定値の整数倍か否か判別し、整数倍以外のときは、２次元相関算出部で観測値と既追尾航跡の相関を取り、新たな航跡を生成・出力し、整数倍のときは、コスト行列更新部で観測値からコスト行列を1サンプリング毎に更新しながら算出し、Lagrange乗数設定部でコスト行列に基づきLagrange緩和法により求められたLagrange乗数によってLagrange緩和解算出部で緩和された制約条件下で相関解を計算し、実現可能解算出部でこの緩和解を修正して全ての制約条件を満たす解を求め、新たな航跡を生成・出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、レーダ等のセンサシステムにおいて、センサからの目標位置の観測値を使って目標の航跡を生成する際の相関を多次元的に解く技術において、演算時間を削減しながら許容可能な解を導出する多目標追尾装置に関する。
【背景技術】
【０００２】
センサにより目標を観測して得られた観測値を使って目標を追尾する技術についてはすでに多くの論文、特許等の文献で取り挙げられており、その装置および方法について様々な提案がなされている。
近接多目標を追尾する場合やクラッタ等の不要信号環境下で目標を追尾する場合、複数のサンプリング時刻における観測値間の相関決定方法は追尾性能を左右する重要な部分である。相関とは図１に示す様な各サンプリング時刻で複数の観測値が得られた場合、「サンプリング時刻t１からサンプリング時刻t3に至るどの観測値を同じ目標と見なすか」を示すものである。
【０００３】
この相関決定の方式としては、図２に示す様に、各サンプリング時刻毎に航跡を生成し、1サンプリング時刻前の航跡と最新サンプリング時刻の観測値の対応付けを行う方式が用いられてきた。この航跡と観測値の2次元の相関を決定する方法については様々なやり方があるが、一例としては各々の既存航跡に対して、相関の度合いが最も高い探知データを割り当てるＮＮ(Nearest Neighbor)がある。この方式については、文献１：Samuel S.Blackman著 “Design and Analysis of Modern Tracking Systems” (ARTECH HOUSE)の第1章3.2節にその記述がある。
またもう一つの例としては、各々の既存航跡に対して可能な相関全てを考慮し、相関の組み合わせで仮説を構成し、各々の相関の度合いを基に仮説の信頼度を計算するMHT (Multiple Hypothesis Tracking)がある。この方式については、文献２：Donald B.Reidによる論文 “An Algorithm for Tracking Multiple Targets”(IEEE Transactions on Automatic Control, Vol.AC-24, No6, December,1979)にその詳細が説明されている。
【０００４】
上記の技術は既存の航跡と最新の観測値の割り当てを決定する方式であるが、さらなる相関性能の向上を目指し、複数サンプリング時刻に跨る観測値の相関をまとめて計算して航跡を生成するアルゴリズムとして複数フレーム割り当て法(Multiple Frame Assignment)がある。この技術については文献３：A.B.Poore and A.J.RobertsonIII著“A New Multi-dimensional Data Association Algorithm for Multisensor-Multitarget Tracking”(Proc. Of SPIE vol.2561,1995)において詳細が記述されている。
複数フレーム割り当て法ではNサンプリング時刻に跨る観測値の相関決定をN次元の割り当て問題に変換して解く。定式化された割り当て問題を以下に示す。
N次元の割り当て問題：
【０００５】
【数１】
【０００６】
ここで、コスト行列ｃj1・・・jN は観測値ｉ1，・・・,ｉN から航跡を生成するのにかかるコストであり、通常航跡尤度比の逆数を使用する。
変数ｚj1・・・jNには以下の意味がある。
【０００７】
【数２】
【０００８】
ただし、以下に示す制約条件がある。
【０００９】
【数３】
【００１０】
上記の割り当て問題は、コスト行列の各次元から要素を一つずつ選択して、選択した要素を最小にするという問題である。簡単な例として、Ｎ＝２の場合の観測値と対応するコスト行列の例を図４に示す。このコスト行列から得られる解の例と対応する航跡の構成を図５に示す。この解によるコストは、「1」が設定された部分に対応するコスト行列の要素の和をとってｃ11＋ｃ24＋ｃ32＋ｃ43となる。また制約条件は、「1」と設定される要素の列が重複してはならないことを示す。例えば図６の様な相関決定は第2サンプリング時刻における第2要素に重複して「1」が設定されており、制約条件を満たさない。これは追尾において、1つの観測値を重複して使用していることに相当する。
【００１１】
以上に説明したＮ次元の割り当てで実現可能な(制約条件を満たす)解の数は観測値の数に応じて指数的に増加する。そのためコストを最小とする最適解を得るためには処理時間が観測値の数や処理する次元数Ｎに応じて指数的に増加するという問題がある。これを解決するために上記文献３で示されている複数フレーム割り当て方式ではLagrange緩和法を使ってＮ次元の割り当て問題を２次元に緩和しながら準最適な解を得る。
【００１２】
文献３で示されている方式を相関処理に適用した従来技術の処理手順を以下に説明する。
図７はその多目標追尾装置の構成を示すブロック図、図８はその処理手順図である。後者の図８に従い図７のシステム図を参照しながら処理手順を説明する。
まず、「観測値入力」ステップS001で、センサ01から得られた過去から最新までのNサンプリング時刻分の観測値がコスト行列計算部02に入力される。
次の「コスト行列計算」ステップS002では、コスト行列計算部02が各サンプリング時刻から一つずつ観測値を選択し、その観測値の組み合わせによって形成される航跡の尤度比を計算し、その逆数を使ってコスト行列を計算する。
【００１３】
次の「Lagrange乗数初期設定」ステップS003では、Lagrange乗数設定部03が制約条件を緩和するためのLagrange乗数の設定を行う。このLagrange乗数は第3サンプリング時刻から第Nサンプリング時刻に至る観測値全てについて設定される。観測値ｊrに関するLagrange乗数をｕjrとする。このLagrange乗数を設定することにより、N次元のコスト行列の第1次元〜第N次元の観測値に関する制約を2次元に緩和することができる。この緩和によりコスト関数は2次元のコスト行列に変形され、その要素は以下の式で表せる。
【００１４】
【数４】
【００１５】
この「Lagrange乗数初期設定」ステップS003での処理の一例として、初期のLagrange乗数を全て0に設定する。
次の「Lagrange緩和解算出」ステップS004では、Lagrange緩和解算出部04がLagrange乗数によって緩和された2次元の割り当て問題の解を算出する。この2次元解の算出方法はハンガリー法等の高速な解導出方式があり、そのうちの何れかを使用する。導出された解のコストをｑ(u)とする。この緩和された2次元の割り当ての解と解のコストｑ(u) を緩和解とコストｑ(u)記憶部07に記憶させる。
次の「実現可能解算出」ステップS005では、実現可能解算出部05が上記の緩和解を修正して、全ての制約条件を満たす実現可能解を導出する。導出された解のコストをν(z) とする。この実現可能解と解のコストν(z)を実現可能解とコストν(z)記憶部08に記憶させる。
【００１６】
次いで、実現可能解算出部05でLagrange緩和解のコストｑ(ｕ)と実現可能解のコストν(z)の差をｑ(ｕ)で割った値を算出し、それがあらかじめ設定した閾値パラメータ以下であるか否かを判定し、閾値パラメータ以下であったら、航跡表示部06が「解出力」ステップS007で実現可能解をこのN次元割り当て問題の準最適解として出力する。閾値条件を満たさない場合は、「Lagrange乗数再設定」ステップS006でLagrange乗数設定部03がLagrange乗数の再設定を行う。この再設定では最新の緩和解における制約条件の逸脱具合に応じた乗数設定を行う。
上記の「Lagrange乗数再設定ステップ」S006をLagrange乗数設定部03で実行した場合は以降Lagrange緩和解算出部04による「Lagrange緩和解算出」ステップS004と実現可能解算出部05による「実現可能解算出」ステップS005が、閾値条件を満たすまで繰り返される。
【００１７】
【非特許文献１】Samuel S.Blackman “Design and Analysis of Modern Tracking Systems” ARTECH HOUSE第1章3.2節
【非特許文献２】Donald B.Reid “An Algorithm for Tracking Multiple Targets” IEEE Transactions on Automatic Control, Vol.AC-24, No6, December,1979
【非特許文献３】A.B.Poore and A.J.RobertsonIII “A New Multi-dimensional Data Association Algorithm for Multisensor-Multitarget Tracking” Proc. Of SPIE vol.2561,1995
【発明の開示】
【発明が解決しようとする課題】
【００１８】
上記の従来複数フレーム割り当て法技術には、N次元の相関の問題を毎サンプリング時刻に解く必要があるため演算負荷が大きくなるという問題がある。また許容可能な範囲内の時間で解導出をいくら繰り返しても閾値条件を満たす準最適解を得ることができず、2次元相関方式よりも尤度の低い相関解しか得られないという可能性もあり得る。
【００１９】
この発明は、上記の課題を解決するためになされたもので、許容可能な処理時間で、少なくとも2次元相関方式に匹敵する尤度を持った解を得ることができる複数フレーム割り当て法に基づいた多目標追尾装置を実現することを目的とする。
【課題を解決するための手段】
【００２０】
この発明に係る多目標追尾装置は、
センサから観測回数が予め設定されたパラメータ値の整数倍か否かを判別する処理法選択部と、
観測回数がパラメータ値の整数倍以外のとき、センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成・出力する2次元相関算出部と、
観測回数がパラメータ値の整数倍のとき、センサからの観測値からコスト行列を1サンプリング時刻毎に更新しながら算出するコスト行列更新部と、
このコスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす解を計算し、新たな航跡を生成・出力する実現可能解算出部を備える。
【発明の効果】
【００２１】
この発明によれば、2次元相関処理と複数フレーム割り当て処理を使い分けるため、2次元相関処理を行うサンプリング時刻での処理負荷は軽いものとなる。また2次元相関処理においてコスト行列作成の計算を行うため、複数フレーム割り当て処理を行うサンプリング時刻でも従来方式に比べて処理負荷が軽減される。よって観測値数が多く相関処理の問題の規模が大きい場合でも対処可能となる。
【発明を実施するための最良の形態】
【００２２】
実施の形態１．
この発明の実施の形態１に関わる多目標追尾装置を図面を参照しながら説明する。
図９は，この発明の実施の形態１に関わる多目標追尾装置の構成を示すブロック図であり、図１０は、この発明の実施の形態1に関わる多目標追尾装置による追尾処理の処理手順図である。
以下この図１０の手順図に従い図９のブロック図を参照しながら相関決定処理の内容を説明する。
【００２３】
最初に「観測値入力」ステップS001で、センサ01からコスト行列更新部12と2次元相関算出部11に観測値が入力される。この時、サンプリング開始時刻から現サンプリング時刻までのサンプリング時間をサンプリング間隔で割った値(処理回数)が予めパラメータとして設定されていた値nの倍数であるか否かを処理法選択部17で判定し、パラメータ値nの倍数である場合には複数フレーム割り当て処理を行い、そうでない場合には2次元相関算出部11で2次元相関算出処理を行う。
【００２４】
まず、2次元相関算出処理を行う場合について説明する。最初2次元相関算出部11が「2次元相関算出」ステップS011を実行する。相関決定方式としては、NNやMHT等の航跡と観測値の相関を決定する方式の何れかを適用して、相関を決定し、新たな航跡を生成する。そしてこの生成された新たな航跡を航跡記憶部18に記憶し、かつ航跡表示部06に送り、航跡表示部06が新たな航跡として出力表示する。この航跡記憶部18は次のサンプリング時刻における観測値を2次元相関算出部11が入力したときに新たな航跡を生成するときの既航跡として使用される。
【００２５】
さらに「コスト行列更新」ステップS01２で、コスト行列更新部12が現サンプリング時刻までのコスト行列の更新を行う。このコスト行列の計算には2次元相関処理で生成した航跡の尤度比のみならず、目標とする観測値得られる可能性の高い範囲、即ちゲート内にある他の観測値を使用して作った航跡の尤度比も計算しておく。図１１に例を示す。実線で示された航跡は2次元相関処理で生成される航跡であるが、この航跡の尤度に加えて点線で示す航跡の尤度も計算する。この更新されたコスト行列は一時コスト行列記憶部19に記憶される。
なお上記の尤度計算は、観測値の組み合わせから得られる全ての航跡でなく、上位ｍの尤度を達成する航跡のみについて尤度比計算を行い、その他の航跡については形成不可とする様な処理内容でもよい。
【００２６】
処理回数による判定結果として複数フレーム割り当て法を行うと判定された場合の処理手順について説明する。まず「コスト行列更新」ステップS013において、コスト行列更新部12が前サンプリング時刻までの相関を考慮して作られたコスト行列に、前サンプリング時刻の航跡と現サンプリング時刻の観測値の相関による尤度比を計算して現サンプリング時刻のコスト行列を生成する。
「コスト行列更新」S013ステップ以降の処理は従来技術と同様である。
【００２７】
以上のように、この実施の形態１で説明した発明によれば、2次元相関処理と複数フレーム割り当て処理を使い分けるため、2次元相関処理を行うサンプリング時刻での処理負荷は軽いものとなる。また2次元相関処理においてコスト行列作成の計算を行い、一時コスト行列記憶部に記憶させて置くため、複数フレーム割り当て処理を行うサンプリング時刻でも従来方式に比べて処理負荷が軽減される。よって観測値数が多く相関処理の問題の規模が大きい場合でも対処可能となる。
【００２８】
実施の形態２．
この発明の実施の形態２に関わる多目標追尾装置を図面を参照しながら説明する。
図１２は，この発明の実施の形態２に関わる多目標追尾装置の構成を示すブロック図である。また図１３は、この発明の実施の形態２に関わる多目標追尾装置による追尾処理の処理手順図である。以下この図１３の手順図に従い図１２のブロック図を参照しながら相関決定処理の内容を説明する。
【００２９】
まず、「観測値入力」ステップS001で、センサ01からコスト行列計算部02と2次元相関算出部11に各サンプリング時刻における全ての観測値が入力される。次に複数フレーム割り当て処理と2次元相関計算が全ての観測値に対して並行して実行される。
複数フレーム割り当て処理ではまずコスト行列計算部02による「コスト行列計算」ステップS002から実行されるが、このステップS002から実現可能解算出部05による「実現可能解算出」ステップS005までのステップの処理内容は従来技術と同様である。その後Lagrange緩和解と実現可能解のコストの比較が実現可能解算出部05で行われ閾値判定で解導出が繰り返される場合、「Lagrange乗数再設定」ステップS006の前で「コスト行列縮小」ステップS014がコスト行列縮小部13によって実行される。このステップS014では、実現可能解と2次元相関算出の解を比較し、一致している部分については決定済みとしてコスト行列から該当する要素を削除する。
【００３０】
この「コスト行列縮小」ステップS014の処理内容を、例を使って説明する。説明を簡単にするために、2サンプリング時刻分の相関をとる場合（Ｎ＝２）における例を使用する。図１４は第1サンプリング時刻において4個、第2サンプリング時刻において7個の観測値が得られる例である。図１５に複数フレーム割り当て法の実現可能解と2次元相関による解を示す。この二つの解を比較すると、第1サンプリング時刻における1番目の観測値と第2サンプリング時刻における2番目の観測値の対応付け、第1サンプリング時刻における2番目の観測値と第2サンプリング時刻における4番目の観測値の対応付けが一致している。よって、第1サンプリング時刻における1番目と2番目の観測値、第2サンプリング時刻における2番目と4番目の観測値をコスト行列から外す。すると図１６の様に4行7列の規模を持つコスト行列が2行5列に縮小される。以降の複数フレーム割り当て処理ではこの縮小された行列から解を導出する。
なお上記は2次元相関算出部11における一つの解からコスト行列を縮小する方法を説明したが、2次元相関にはMHTを使用することを前提とし、コスト行列縮小部13がMHTで計算された複数仮説の上位m個に対応するm個の解全てに共通する部分のみをコスト行列から削除する様にしてもよい。
【００３１】
以上のように、この実施の形態２で説明した発明によれば、複数フレーム割り当て法と2次元相関処理の解を比較してその一致する部分をコスト行列から除きながら処理を行うため、計算負荷が軽減される。
【００３２】
実施の形態３．
この発明の実施の形態３に関わる多目標追尾装置を図面参照しながら説明する。
図１７は，この発明の実施の形態3に関わる多目標追尾装置の構成を示すブロック図である。また図１８は、この発明の実施の形態3に関わる多目標追尾装置による追尾処理の手順図である。以下、この図１８の手順図に従い図１７のブロック図を参照しながら相関決定処理の内容を説明する。
【００３３】
まず、「観測値入力」ステップS001で、センサ01からの各サンプリング時刻における全ての観測値がコスト行列計算部02と2次元相関算出部11に入力される。次に複数フレーム割り当て処理と2次元相関計算が全ての観測値に対して並行して実行される。複数フレーム割り当て法を処理する側では従来技術の「コスト行列計算」ステップS002がコスト行列計算部02で行われる。一方、2次元相関算出部11に入力された観測値に基づき2次元相関の解が「2次元相関算出」ステップS011で求められ、この解から新たな航跡が生成され、航跡記憶部18に記憶される。
「Lagrange乗数初期値計算」ステップS015がLagrange乗数初期値計算部14によって実行される。このステップS015では、2次元相関算出部11による2次元相関の解が緩和解と一致する様にLagrange乗数の初期値を計算する。このLagrange乗数の初期値の設定について説明する。緩和された2次元のコスト行列の各要素は以下の式で表せる。
【００３４】
【数５】
【００３５】
上式において、2次元相関解で選択された部分のコストが小さくなる様にLagrange乗数を設定することにより、複数フレーム割り当て法における最初の解が2次元相関解と一致することになる。
このステップ以降の処理内容は従来技術と同様である。
【００３６】
以上のように、この実施の形態3で説明した発明によれば、Lagrange緩和解の初期の解を2次元相関解と一致させるため、複数フレーム割り当て処理における解の収束が速まり、効率的な処理が可能となる。また従来の複数フレーム割り当て処理を行うと許容可能な範囲内の時間で解導出をいくら繰り返しても閾値条件を満たす準最適解を得ることができず2次元相関方式よりも尤度の低い相関解しか得られない場合でも、少なくとも2次元相関方式に匹敵する尤度を持った解を得ることができる。
【００３７】
実施の形態４．
この発明の実施の形態4に関わる多目標追尾装置を図面参照しながら説明する。
図１９は，この発明の実施の形態４に関わる多目標追尾装置の構成を示すブロック図である。また図２０は、この発明の実施の形態4に関わる多目標追尾装置による追尾処理の手順図である。以下、この図２０の手順図に従い図１９のブロック図を参照しながら相関決定処理の内容を説明する。
【００３８】
まず、「観測値入力」ステップS001で、センサ01からの各サンプリング時刻における全ての観測値がコスト行列計算部02と2次元相関算出部としてのMHT処理部11に入力される。次に複数フレーム割り当て処理と2次元の相関計算が全ての観測値に対して並行して実行される。2次元の相関計算ではMHT処理部11でMHT方式に従った「MHT処理」ステップS011が行われ2次元相関の解が求められる。この2次元相関の解から新たな航跡が生成されて航跡記憶部18に記憶される。
複数フレーム割り当て法を処理する側では従来技術の「コスト行列計算」ステップS002がコスト行列計算部02で行われた後、「複数Lagrange乗数初期値計算」ステップS016が複数Lagrange乗数初期値計算部15によって実行される。このステップでは、MHT処理部11の処理における上位m仮説の相関の解が緩和解と一致する様に、m通りのLagrange乗数の初期値を計算する。
【００３９】
このステップ以降の処理内容は、m通りのLagrange乗数について従来技術と同様の処理を行う。
「Lagrange緩和解算出」ステップS004ではm通りのLagrange乗数についてm個の緩和解を導出する。
「実現可能解算出」ステップS005では前ステップで算出されたm個の緩和解の各々について実現可能解を算出する。
その後の閾値比較では、m個ある実現可能解のコストの最小値とm個ある緩和解のコストの最大値を使って以下の様な閾値判定を行う。
【００４０】
【数６】
【００４１】
「Lagrange乗数再設定」ステップS006ではm通りのLagrange乗数の再設定を行う。
【００４２】
以上のように、この実施の形態4で説明した発明によれば、Lagrange緩和解の初期の解をMHT相関解と一致させるため、複数フレーム割り当て処理における解の収束が速まり、効率的な処理が可能となる。また従来の複数フレーム割り当て処理を行うと許容可能な範囲内の時間で解導出をいくら繰り返しても閾値条件を満たす準最適解を得ることができず2次元相関方式よりも尤度の低い相関解しか得られない場合でも、少なくとも2次元相関方式に匹敵する尤度を持った解を得ることができる。またMHT処理における複数の仮説の相関解を初期の解として複数フレーム割り当て処理を行うので、実施の形態3に比べてより適した解が得られる可能性が高くなる。
【００４３】
実施の形態５．
この発明の実施の形態５に関わる多目標追尾装置を図面参照しながら説明する。
図２１は，この発明の実施の形態５に関わる多目標追尾装置の構成を示すブロック図である。また図２２は、この発明の実施の形態５に関わる多目標追尾装置による追尾処理の手順図である。以下、この図２２の手順図に従い図２１のブロック図を参照しながら相関決定処理の内容を説明する。
【００４４】
まず、「観測値入力」ステップS001で、センサ01から各サンプリング時刻における全ての観測値がコスト行列計算部02と2次元相関算出部11に入力される。次に複数フレーム割り当て処理と2次元の相関計算が全ての観測値に対して並行して実行される。２次元の相関計算ではMHT方式に従った「MHT処理」ステップS011がMHT処理部011で行われ、２次元の相関が求められる。この2次元相関の解から新たな航跡が生成されて航跡記憶部18に記憶される。
複数フレーム割り当て法を処理する側では従来技術の「コスト行列計算」ステップS002がコスト行列計算部02で行われた後、「複数Lagrange乗数初期値計算」ステップS016が複数Lagrange乗数初期値計算部15によって実行される。このステップでは、MHT処理部011の処理における上位m仮説の相関の解が緩和解と一致する様に、m通りのLagrange乗数の初期値を計算する。複数Lagrange乗数初期値計算部15によって得られたm通りのLagrange乗数の初期値はLagrange乗数初期値記憶部20に記憶される。
【００４５】
このステップ以降の処理内容は、m個のLagrange乗数の中から一つを選び、切り替えを行いながらLagrange乗数について従来技術と同様の処理を行う。最初の選択では、MHT処理における第1位の仮説から得られるLagrange乗数を選ぶ。
「Lagrange緩和解算出」ステップS004では従来技術と同様に、Lagrange緩和解算出部04が緩和解を導出する。
「実現可能解算出」ステップS005では従来技術と同様に、前ステップS004でLagrange緩和解算出部04により算出された緩和解から実現可能解算出部05が実現可能解を算出する。
その後の閾値比較は従来技術と同様に行い、その後解の収束具合の判定を行う。この収束具合は以下の式に示すコスト差の割合、
【００４６】
【数７】
【００４７】
の前サンプリング時刻における値と現サンプリング時刻における値の差を計算し、その値が閾値を下回ったら「Lagrange乗数初期値切り換え」ステップS017において、Lagrange乗数切り換え部16がLagrange乗数初期値記憶部20に記憶されているm個あるLagrange乗数の初期値の中から別の乗数初期値に切り換える。この切り替え以降は新たに設定されたLagrange乗数初期値を使って複数フレーム割り当て処理を実行する。切り換えるLagrange乗数の選択方法については、切り換え前にMHT処理の第j位の仮説から計算されたLagrange乗数初期値を使用していた場合には、切り換え後は第j+1位の仮説から計算されたLagrange乗数初期値を使用する。閾値を下回らない場合は従来技術における「Lagrange乗数再設定」ステップS006の処理を実行する。
【００４８】
以上のように、この実施の形態５で説明した発明によれば、Lagrange緩和解の初期の解をMHT相関解と一致させるため、複数フレーム割り当て処理における解の収束が速まり、効率的な処理が可能となる。また従来の複数フレーム割り当て処理を行うと許容可能な範囲内の時間で解導出をいくら繰り返しても閾値条件を満たす準最適解を得ることができず、2次元相関方式よりも尤度の低い相関解しか得られない場合でも少なくとも2次元相関方式に匹敵する尤度を持った解を得ることができる。また、これはMHT処理における複数仮説のうちの一つの相関解を初期の解としながらも、初期値の切り換えを行いながら複数フレーム割り当て処理を行うので、実施の形態４に比べて演算負荷が軽くなる。
【産業上の利用可能性】
【００４９】
レーダシステムに適用されることでクラッタ中の多目標追尾、低Ｓ／Ｎでの目標航跡検出に効果を発する。
【図面の簡単な説明】
【００５０】
【図１】複数の観測値による相関の概念を説明する図である。
【図２】2次元相関方式における相関決定の例を説明する図である。
【図３】MFA相関方式における相関決定の例を説明する図である。
【図４】サンプリング時刻２の場合の観測値と対応コスト行列の例を示す図である。
【図５】コスト行列から得られる解と対応する航跡の構成を説明する図である。
【図６】制約条件を満たさない相関決定の例を示す図である。
【図７】従来技術による多目標追尾装置の構成を示すブロック図である。
【図８】従来技術の多目標追尾装置による処理手順図である。
【図９】この発明の実施の形態１に関わる多目標追尾装置の構成を示すブロック図である。
【図１０】この発明の実施の形態1に関わる多目標追尾装置による追尾処理の処理手順図である。
【図１１】この発明の実施の形態1によるコスト行列の計算例を示す図である。
【図１２】この発明の実施の形態２に関わる多目標追尾装置の構成を示すブロック図である。
【図１３】この発明の実施の形態２に関わる多目標追尾装置による追尾処理の処理手順図である。
【図１４】コスト行列縮小ステップの処理内容の説明図である。
【図１５】複数フレーム割り当て法の実現可能解と2次元相関による解の説明図である。
【図１６】コスト行列縮小ステップの処理結果の説明図である。
【図１７】この発明の実施の形態3に関わる多目標追尾装置の構成を示すブロック図である。
【図１８】この発明の実施の形態3に関わる多目標追尾装置による追尾処理の手順図である。
【図１９】この発明の実施の形態4に関わる多目標追尾装置の構成を示すブロック図である。
【図２０】この発明の実施の形態4に関わる多目標追尾装置による追尾処理の手順図である。
【図２１】この発明の実施の形態５に関わる多目標追尾装置の構成を示すブロック図である。
【図２２】この発明の実施の形態５に関わる多目標追尾装置による追尾処理の手順図である。
【符号の説明】
【００５１】
01；センサ、02；コスト行列計算部、03；Lagrange乗数設定部、04；Lagrange緩和解算出部、05；実現可能解算出部、06；航跡表示部、07；緩和解とコストｑ(u)記憶部、08；実現可能解とコストν(z)記憶部、11；2次元相関算出部、12；コスト行列更新部、13；コスト行列縮小部、14；Lagrange乗数初期値計算部、15；複数Lagrange乗数初期値計算部、16；Lagrange乗数切り換え部、17；処理法選択部、18；航跡記憶部、19；一時コスト行列記憶部、20；Lagrange乗数初期値記憶部。
【技術分野】
【０００１】
この発明は、レーダ等のセンサシステムにおいて、センサからの目標位置の観測値を使って目標の航跡を生成する際の相関を多次元的に解く技術において、演算時間を削減しながら許容可能な解を導出する多目標追尾装置に関する。
【背景技術】
【０００２】
センサにより目標を観測して得られた観測値を使って目標を追尾する技術についてはすでに多くの論文、特許等の文献で取り挙げられており、その装置および方法について様々な提案がなされている。
近接多目標を追尾する場合やクラッタ等の不要信号環境下で目標を追尾する場合、複数のサンプリング時刻における観測値間の相関決定方法は追尾性能を左右する重要な部分である。相関とは図１に示す様な各サンプリング時刻で複数の観測値が得られた場合、「サンプリング時刻t１からサンプリング時刻t3に至るどの観測値を同じ目標と見なすか」を示すものである。
【０００３】
この相関決定の方式としては、図２に示す様に、各サンプリング時刻毎に航跡を生成し、1サンプリング時刻前の航跡と最新サンプリング時刻の観測値の対応付けを行う方式が用いられてきた。この航跡と観測値の2次元の相関を決定する方法については様々なやり方があるが、一例としては各々の既存航跡に対して、相関の度合いが最も高い探知データを割り当てるＮＮ(Nearest Neighbor)がある。この方式については、文献１：Samuel S.Blackman著 “Design and Analysis of Modern Tracking Systems” (ARTECH HOUSE)の第1章3.2節にその記述がある。
またもう一つの例としては、各々の既存航跡に対して可能な相関全てを考慮し、相関の組み合わせで仮説を構成し、各々の相関の度合いを基に仮説の信頼度を計算するMHT (Multiple Hypothesis Tracking)がある。この方式については、文献２：Donald B.Reidによる論文 “An Algorithm for Tracking Multiple Targets”(IEEE Transactions on Automatic Control, Vol.AC-24, No6, December,1979)にその詳細が説明されている。
【０００４】
上記の技術は既存の航跡と最新の観測値の割り当てを決定する方式であるが、さらなる相関性能の向上を目指し、複数サンプリング時刻に跨る観測値の相関をまとめて計算して航跡を生成するアルゴリズムとして複数フレーム割り当て法(Multiple Frame Assignment)がある。この技術については文献３：A.B.Poore and A.J.RobertsonIII著“A New Multi-dimensional Data Association Algorithm for Multisensor-Multitarget Tracking”(Proc. Of SPIE vol.2561,1995)において詳細が記述されている。
複数フレーム割り当て法ではNサンプリング時刻に跨る観測値の相関決定をN次元の割り当て問題に変換して解く。定式化された割り当て問題を以下に示す。
N次元の割り当て問題：
【０００５】
【数１】
【０００６】
ここで、コスト行列ｃj1・・・jN は観測値ｉ1，・・・,ｉN から航跡を生成するのにかかるコストであり、通常航跡尤度比の逆数を使用する。
変数ｚj1・・・jNには以下の意味がある。
【０００７】
【数２】
【０００８】
ただし、以下に示す制約条件がある。
【０００９】
【数３】
【００１０】
上記の割り当て問題は、コスト行列の各次元から要素を一つずつ選択して、選択した要素を最小にするという問題である。簡単な例として、Ｎ＝２の場合の観測値と対応するコスト行列の例を図４に示す。このコスト行列から得られる解の例と対応する航跡の構成を図５に示す。この解によるコストは、「1」が設定された部分に対応するコスト行列の要素の和をとってｃ11＋ｃ24＋ｃ32＋ｃ43となる。また制約条件は、「1」と設定される要素の列が重複してはならないことを示す。例えば図６の様な相関決定は第2サンプリング時刻における第2要素に重複して「1」が設定されており、制約条件を満たさない。これは追尾において、1つの観測値を重複して使用していることに相当する。
【００１１】
以上に説明したＮ次元の割り当てで実現可能な(制約条件を満たす)解の数は観測値の数に応じて指数的に増加する。そのためコストを最小とする最適解を得るためには処理時間が観測値の数や処理する次元数Ｎに応じて指数的に増加するという問題がある。これを解決するために上記文献３で示されている複数フレーム割り当て方式ではLagrange緩和法を使ってＮ次元の割り当て問題を２次元に緩和しながら準最適な解を得る。
【００１２】
文献３で示されている方式を相関処理に適用した従来技術の処理手順を以下に説明する。
図７はその多目標追尾装置の構成を示すブロック図、図８はその処理手順図である。後者の図８に従い図７のシステム図を参照しながら処理手順を説明する。
まず、「観測値入力」ステップS001で、センサ01から得られた過去から最新までのNサンプリング時刻分の観測値がコスト行列計算部02に入力される。
次の「コスト行列計算」ステップS002では、コスト行列計算部02が各サンプリング時刻から一つずつ観測値を選択し、その観測値の組み合わせによって形成される航跡の尤度比を計算し、その逆数を使ってコスト行列を計算する。
【００１３】
次の「Lagrange乗数初期設定」ステップS003では、Lagrange乗数設定部03が制約条件を緩和するためのLagrange乗数の設定を行う。このLagrange乗数は第3サンプリング時刻から第Nサンプリング時刻に至る観測値全てについて設定される。観測値ｊrに関するLagrange乗数をｕjrとする。このLagrange乗数を設定することにより、N次元のコスト行列の第1次元〜第N次元の観測値に関する制約を2次元に緩和することができる。この緩和によりコスト関数は2次元のコスト行列に変形され、その要素は以下の式で表せる。
【００１４】
【数４】
【００１５】
この「Lagrange乗数初期設定」ステップS003での処理の一例として、初期のLagrange乗数を全て0に設定する。
次の「Lagrange緩和解算出」ステップS004では、Lagrange緩和解算出部04がLagrange乗数によって緩和された2次元の割り当て問題の解を算出する。この2次元解の算出方法はハンガリー法等の高速な解導出方式があり、そのうちの何れかを使用する。導出された解のコストをｑ(u)とする。この緩和された2次元の割り当ての解と解のコストｑ(u) を緩和解とコストｑ(u)記憶部07に記憶させる。
次の「実現可能解算出」ステップS005では、実現可能解算出部05が上記の緩和解を修正して、全ての制約条件を満たす実現可能解を導出する。導出された解のコストをν(z) とする。この実現可能解と解のコストν(z)を実現可能解とコストν(z)記憶部08に記憶させる。
【００１６】
次いで、実現可能解算出部05でLagrange緩和解のコストｑ(ｕ)と実現可能解のコストν(z)の差をｑ(ｕ)で割った値を算出し、それがあらかじめ設定した閾値パラメータ以下であるか否かを判定し、閾値パラメータ以下であったら、航跡表示部06が「解出力」ステップS007で実現可能解をこのN次元割り当て問題の準最適解として出力する。閾値条件を満たさない場合は、「Lagrange乗数再設定」ステップS006でLagrange乗数設定部03がLagrange乗数の再設定を行う。この再設定では最新の緩和解における制約条件の逸脱具合に応じた乗数設定を行う。
上記の「Lagrange乗数再設定ステップ」S006をLagrange乗数設定部03で実行した場合は以降Lagrange緩和解算出部04による「Lagrange緩和解算出」ステップS004と実現可能解算出部05による「実現可能解算出」ステップS005が、閾値条件を満たすまで繰り返される。
【００１７】
【非特許文献１】Samuel S.Blackman “Design and Analysis of Modern Tracking Systems” ARTECH HOUSE第1章3.2節
【非特許文献２】Donald B.Reid “An Algorithm for Tracking Multiple Targets” IEEE Transactions on Automatic Control, Vol.AC-24, No6, December,1979
【非特許文献３】A.B.Poore and A.J.RobertsonIII “A New Multi-dimensional Data Association Algorithm for Multisensor-Multitarget Tracking” Proc. Of SPIE vol.2561,1995
【発明の開示】
【発明が解決しようとする課題】
【００１８】
上記の従来複数フレーム割り当て法技術には、N次元の相関の問題を毎サンプリング時刻に解く必要があるため演算負荷が大きくなるという問題がある。また許容可能な範囲内の時間で解導出をいくら繰り返しても閾値条件を満たす準最適解を得ることができず、2次元相関方式よりも尤度の低い相関解しか得られないという可能性もあり得る。
【００１９】
この発明は、上記の課題を解決するためになされたもので、許容可能な処理時間で、少なくとも2次元相関方式に匹敵する尤度を持った解を得ることができる複数フレーム割り当て法に基づいた多目標追尾装置を実現することを目的とする。
【課題を解決するための手段】
【００２０】
この発明に係る多目標追尾装置は、
センサから観測回数が予め設定されたパラメータ値の整数倍か否かを判別する処理法選択部と、
観測回数がパラメータ値の整数倍以外のとき、センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成・出力する2次元相関算出部と、
観測回数がパラメータ値の整数倍のとき、センサからの観測値からコスト行列を1サンプリング時刻毎に更新しながら算出するコスト行列更新部と、
このコスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす解を計算し、新たな航跡を生成・出力する実現可能解算出部を備える。
【発明の効果】
【００２１】
この発明によれば、2次元相関処理と複数フレーム割り当て処理を使い分けるため、2次元相関処理を行うサンプリング時刻での処理負荷は軽いものとなる。また2次元相関処理においてコスト行列作成の計算を行うため、複数フレーム割り当て処理を行うサンプリング時刻でも従来方式に比べて処理負荷が軽減される。よって観測値数が多く相関処理の問題の規模が大きい場合でも対処可能となる。
【発明を実施するための最良の形態】
【００２２】
実施の形態１．
この発明の実施の形態１に関わる多目標追尾装置を図面を参照しながら説明する。
図９は，この発明の実施の形態１に関わる多目標追尾装置の構成を示すブロック図であり、図１０は、この発明の実施の形態1に関わる多目標追尾装置による追尾処理の処理手順図である。
以下この図１０の手順図に従い図９のブロック図を参照しながら相関決定処理の内容を説明する。
【００２３】
最初に「観測値入力」ステップS001で、センサ01からコスト行列更新部12と2次元相関算出部11に観測値が入力される。この時、サンプリング開始時刻から現サンプリング時刻までのサンプリング時間をサンプリング間隔で割った値(処理回数)が予めパラメータとして設定されていた値nの倍数であるか否かを処理法選択部17で判定し、パラメータ値nの倍数である場合には複数フレーム割り当て処理を行い、そうでない場合には2次元相関算出部11で2次元相関算出処理を行う。
【００２４】
まず、2次元相関算出処理を行う場合について説明する。最初2次元相関算出部11が「2次元相関算出」ステップS011を実行する。相関決定方式としては、NNやMHT等の航跡と観測値の相関を決定する方式の何れかを適用して、相関を決定し、新たな航跡を生成する。そしてこの生成された新たな航跡を航跡記憶部18に記憶し、かつ航跡表示部06に送り、航跡表示部06が新たな航跡として出力表示する。この航跡記憶部18は次のサンプリング時刻における観測値を2次元相関算出部11が入力したときに新たな航跡を生成するときの既航跡として使用される。
【００２５】
さらに「コスト行列更新」ステップS01２で、コスト行列更新部12が現サンプリング時刻までのコスト行列の更新を行う。このコスト行列の計算には2次元相関処理で生成した航跡の尤度比のみならず、目標とする観測値得られる可能性の高い範囲、即ちゲート内にある他の観測値を使用して作った航跡の尤度比も計算しておく。図１１に例を示す。実線で示された航跡は2次元相関処理で生成される航跡であるが、この航跡の尤度に加えて点線で示す航跡の尤度も計算する。この更新されたコスト行列は一時コスト行列記憶部19に記憶される。
なお上記の尤度計算は、観測値の組み合わせから得られる全ての航跡でなく、上位ｍの尤度を達成する航跡のみについて尤度比計算を行い、その他の航跡については形成不可とする様な処理内容でもよい。
【００２６】
処理回数による判定結果として複数フレーム割り当て法を行うと判定された場合の処理手順について説明する。まず「コスト行列更新」ステップS013において、コスト行列更新部12が前サンプリング時刻までの相関を考慮して作られたコスト行列に、前サンプリング時刻の航跡と現サンプリング時刻の観測値の相関による尤度比を計算して現サンプリング時刻のコスト行列を生成する。
「コスト行列更新」S013ステップ以降の処理は従来技術と同様である。
【００２７】
以上のように、この実施の形態１で説明した発明によれば、2次元相関処理と複数フレーム割り当て処理を使い分けるため、2次元相関処理を行うサンプリング時刻での処理負荷は軽いものとなる。また2次元相関処理においてコスト行列作成の計算を行い、一時コスト行列記憶部に記憶させて置くため、複数フレーム割り当て処理を行うサンプリング時刻でも従来方式に比べて処理負荷が軽減される。よって観測値数が多く相関処理の問題の規模が大きい場合でも対処可能となる。
【００２８】
実施の形態２．
この発明の実施の形態２に関わる多目標追尾装置を図面を参照しながら説明する。
図１２は，この発明の実施の形態２に関わる多目標追尾装置の構成を示すブロック図である。また図１３は、この発明の実施の形態２に関わる多目標追尾装置による追尾処理の処理手順図である。以下この図１３の手順図に従い図１２のブロック図を参照しながら相関決定処理の内容を説明する。
【００２９】
まず、「観測値入力」ステップS001で、センサ01からコスト行列計算部02と2次元相関算出部11に各サンプリング時刻における全ての観測値が入力される。次に複数フレーム割り当て処理と2次元相関計算が全ての観測値に対して並行して実行される。
複数フレーム割り当て処理ではまずコスト行列計算部02による「コスト行列計算」ステップS002から実行されるが、このステップS002から実現可能解算出部05による「実現可能解算出」ステップS005までのステップの処理内容は従来技術と同様である。その後Lagrange緩和解と実現可能解のコストの比較が実現可能解算出部05で行われ閾値判定で解導出が繰り返される場合、「Lagrange乗数再設定」ステップS006の前で「コスト行列縮小」ステップS014がコスト行列縮小部13によって実行される。このステップS014では、実現可能解と2次元相関算出の解を比較し、一致している部分については決定済みとしてコスト行列から該当する要素を削除する。
【００３０】
この「コスト行列縮小」ステップS014の処理内容を、例を使って説明する。説明を簡単にするために、2サンプリング時刻分の相関をとる場合（Ｎ＝２）における例を使用する。図１４は第1サンプリング時刻において4個、第2サンプリング時刻において7個の観測値が得られる例である。図１５に複数フレーム割り当て法の実現可能解と2次元相関による解を示す。この二つの解を比較すると、第1サンプリング時刻における1番目の観測値と第2サンプリング時刻における2番目の観測値の対応付け、第1サンプリング時刻における2番目の観測値と第2サンプリング時刻における4番目の観測値の対応付けが一致している。よって、第1サンプリング時刻における1番目と2番目の観測値、第2サンプリング時刻における2番目と4番目の観測値をコスト行列から外す。すると図１６の様に4行7列の規模を持つコスト行列が2行5列に縮小される。以降の複数フレーム割り当て処理ではこの縮小された行列から解を導出する。
なお上記は2次元相関算出部11における一つの解からコスト行列を縮小する方法を説明したが、2次元相関にはMHTを使用することを前提とし、コスト行列縮小部13がMHTで計算された複数仮説の上位m個に対応するm個の解全てに共通する部分のみをコスト行列から削除する様にしてもよい。
【００３１】
以上のように、この実施の形態２で説明した発明によれば、複数フレーム割り当て法と2次元相関処理の解を比較してその一致する部分をコスト行列から除きながら処理を行うため、計算負荷が軽減される。
【００３２】
実施の形態３．
この発明の実施の形態３に関わる多目標追尾装置を図面参照しながら説明する。
図１７は，この発明の実施の形態3に関わる多目標追尾装置の構成を示すブロック図である。また図１８は、この発明の実施の形態3に関わる多目標追尾装置による追尾処理の手順図である。以下、この図１８の手順図に従い図１７のブロック図を参照しながら相関決定処理の内容を説明する。
【００３３】
まず、「観測値入力」ステップS001で、センサ01からの各サンプリング時刻における全ての観測値がコスト行列計算部02と2次元相関算出部11に入力される。次に複数フレーム割り当て処理と2次元相関計算が全ての観測値に対して並行して実行される。複数フレーム割り当て法を処理する側では従来技術の「コスト行列計算」ステップS002がコスト行列計算部02で行われる。一方、2次元相関算出部11に入力された観測値に基づき2次元相関の解が「2次元相関算出」ステップS011で求められ、この解から新たな航跡が生成され、航跡記憶部18に記憶される。
「Lagrange乗数初期値計算」ステップS015がLagrange乗数初期値計算部14によって実行される。このステップS015では、2次元相関算出部11による2次元相関の解が緩和解と一致する様にLagrange乗数の初期値を計算する。このLagrange乗数の初期値の設定について説明する。緩和された2次元のコスト行列の各要素は以下の式で表せる。
【００３４】
【数５】
【００３５】
上式において、2次元相関解で選択された部分のコストが小さくなる様にLagrange乗数を設定することにより、複数フレーム割り当て法における最初の解が2次元相関解と一致することになる。
このステップ以降の処理内容は従来技術と同様である。
【００３６】
以上のように、この実施の形態3で説明した発明によれば、Lagrange緩和解の初期の解を2次元相関解と一致させるため、複数フレーム割り当て処理における解の収束が速まり、効率的な処理が可能となる。また従来の複数フレーム割り当て処理を行うと許容可能な範囲内の時間で解導出をいくら繰り返しても閾値条件を満たす準最適解を得ることができず2次元相関方式よりも尤度の低い相関解しか得られない場合でも、少なくとも2次元相関方式に匹敵する尤度を持った解を得ることができる。
【００３７】
実施の形態４．
この発明の実施の形態4に関わる多目標追尾装置を図面参照しながら説明する。
図１９は，この発明の実施の形態４に関わる多目標追尾装置の構成を示すブロック図である。また図２０は、この発明の実施の形態4に関わる多目標追尾装置による追尾処理の手順図である。以下、この図２０の手順図に従い図１９のブロック図を参照しながら相関決定処理の内容を説明する。
【００３８】
まず、「観測値入力」ステップS001で、センサ01からの各サンプリング時刻における全ての観測値がコスト行列計算部02と2次元相関算出部としてのMHT処理部11に入力される。次に複数フレーム割り当て処理と2次元の相関計算が全ての観測値に対して並行して実行される。2次元の相関計算ではMHT処理部11でMHT方式に従った「MHT処理」ステップS011が行われ2次元相関の解が求められる。この2次元相関の解から新たな航跡が生成されて航跡記憶部18に記憶される。
複数フレーム割り当て法を処理する側では従来技術の「コスト行列計算」ステップS002がコスト行列計算部02で行われた後、「複数Lagrange乗数初期値計算」ステップS016が複数Lagrange乗数初期値計算部15によって実行される。このステップでは、MHT処理部11の処理における上位m仮説の相関の解が緩和解と一致する様に、m通りのLagrange乗数の初期値を計算する。
【００３９】
このステップ以降の処理内容は、m通りのLagrange乗数について従来技術と同様の処理を行う。
「Lagrange緩和解算出」ステップS004ではm通りのLagrange乗数についてm個の緩和解を導出する。
「実現可能解算出」ステップS005では前ステップで算出されたm個の緩和解の各々について実現可能解を算出する。
その後の閾値比較では、m個ある実現可能解のコストの最小値とm個ある緩和解のコストの最大値を使って以下の様な閾値判定を行う。
【００４０】
【数６】
【００４１】
「Lagrange乗数再設定」ステップS006ではm通りのLagrange乗数の再設定を行う。
【００４２】
以上のように、この実施の形態4で説明した発明によれば、Lagrange緩和解の初期の解をMHT相関解と一致させるため、複数フレーム割り当て処理における解の収束が速まり、効率的な処理が可能となる。また従来の複数フレーム割り当て処理を行うと許容可能な範囲内の時間で解導出をいくら繰り返しても閾値条件を満たす準最適解を得ることができず2次元相関方式よりも尤度の低い相関解しか得られない場合でも、少なくとも2次元相関方式に匹敵する尤度を持った解を得ることができる。またMHT処理における複数の仮説の相関解を初期の解として複数フレーム割り当て処理を行うので、実施の形態3に比べてより適した解が得られる可能性が高くなる。
【００４３】
実施の形態５．
この発明の実施の形態５に関わる多目標追尾装置を図面参照しながら説明する。
図２１は，この発明の実施の形態５に関わる多目標追尾装置の構成を示すブロック図である。また図２２は、この発明の実施の形態５に関わる多目標追尾装置による追尾処理の手順図である。以下、この図２２の手順図に従い図２１のブロック図を参照しながら相関決定処理の内容を説明する。
【００４４】
まず、「観測値入力」ステップS001で、センサ01から各サンプリング時刻における全ての観測値がコスト行列計算部02と2次元相関算出部11に入力される。次に複数フレーム割り当て処理と2次元の相関計算が全ての観測値に対して並行して実行される。２次元の相関計算ではMHT方式に従った「MHT処理」ステップS011がMHT処理部011で行われ、２次元の相関が求められる。この2次元相関の解から新たな航跡が生成されて航跡記憶部18に記憶される。
複数フレーム割り当て法を処理する側では従来技術の「コスト行列計算」ステップS002がコスト行列計算部02で行われた後、「複数Lagrange乗数初期値計算」ステップS016が複数Lagrange乗数初期値計算部15によって実行される。このステップでは、MHT処理部011の処理における上位m仮説の相関の解が緩和解と一致する様に、m通りのLagrange乗数の初期値を計算する。複数Lagrange乗数初期値計算部15によって得られたm通りのLagrange乗数の初期値はLagrange乗数初期値記憶部20に記憶される。
【００４５】
このステップ以降の処理内容は、m個のLagrange乗数の中から一つを選び、切り替えを行いながらLagrange乗数について従来技術と同様の処理を行う。最初の選択では、MHT処理における第1位の仮説から得られるLagrange乗数を選ぶ。
「Lagrange緩和解算出」ステップS004では従来技術と同様に、Lagrange緩和解算出部04が緩和解を導出する。
「実現可能解算出」ステップS005では従来技術と同様に、前ステップS004でLagrange緩和解算出部04により算出された緩和解から実現可能解算出部05が実現可能解を算出する。
その後の閾値比較は従来技術と同様に行い、その後解の収束具合の判定を行う。この収束具合は以下の式に示すコスト差の割合、
【００４６】
【数７】
【００４７】
の前サンプリング時刻における値と現サンプリング時刻における値の差を計算し、その値が閾値を下回ったら「Lagrange乗数初期値切り換え」ステップS017において、Lagrange乗数切り換え部16がLagrange乗数初期値記憶部20に記憶されているm個あるLagrange乗数の初期値の中から別の乗数初期値に切り換える。この切り替え以降は新たに設定されたLagrange乗数初期値を使って複数フレーム割り当て処理を実行する。切り換えるLagrange乗数の選択方法については、切り換え前にMHT処理の第j位の仮説から計算されたLagrange乗数初期値を使用していた場合には、切り換え後は第j+1位の仮説から計算されたLagrange乗数初期値を使用する。閾値を下回らない場合は従来技術における「Lagrange乗数再設定」ステップS006の処理を実行する。
【００４８】
以上のように、この実施の形態５で説明した発明によれば、Lagrange緩和解の初期の解をMHT相関解と一致させるため、複数フレーム割り当て処理における解の収束が速まり、効率的な処理が可能となる。また従来の複数フレーム割り当て処理を行うと許容可能な範囲内の時間で解導出をいくら繰り返しても閾値条件を満たす準最適解を得ることができず、2次元相関方式よりも尤度の低い相関解しか得られない場合でも少なくとも2次元相関方式に匹敵する尤度を持った解を得ることができる。また、これはMHT処理における複数仮説のうちの一つの相関解を初期の解としながらも、初期値の切り換えを行いながら複数フレーム割り当て処理を行うので、実施の形態４に比べて演算負荷が軽くなる。
【産業上の利用可能性】
【００４９】
レーダシステムに適用されることでクラッタ中の多目標追尾、低Ｓ／Ｎでの目標航跡検出に効果を発する。
【図面の簡単な説明】
【００５０】
【図１】複数の観測値による相関の概念を説明する図である。
【図２】2次元相関方式における相関決定の例を説明する図である。
【図３】MFA相関方式における相関決定の例を説明する図である。
【図４】サンプリング時刻２の場合の観測値と対応コスト行列の例を示す図である。
【図５】コスト行列から得られる解と対応する航跡の構成を説明する図である。
【図６】制約条件を満たさない相関決定の例を示す図である。
【図７】従来技術による多目標追尾装置の構成を示すブロック図である。
【図８】従来技術の多目標追尾装置による処理手順図である。
【図９】この発明の実施の形態１に関わる多目標追尾装置の構成を示すブロック図である。
【図１０】この発明の実施の形態1に関わる多目標追尾装置による追尾処理の処理手順図である。
【図１１】この発明の実施の形態1によるコスト行列の計算例を示す図である。
【図１２】この発明の実施の形態２に関わる多目標追尾装置の構成を示すブロック図である。
【図１３】この発明の実施の形態２に関わる多目標追尾装置による追尾処理の処理手順図である。
【図１４】コスト行列縮小ステップの処理内容の説明図である。
【図１５】複数フレーム割り当て法の実現可能解と2次元相関による解の説明図である。
【図１６】コスト行列縮小ステップの処理結果の説明図である。
【図１７】この発明の実施の形態3に関わる多目標追尾装置の構成を示すブロック図である。
【図１８】この発明の実施の形態3に関わる多目標追尾装置による追尾処理の手順図である。
【図１９】この発明の実施の形態4に関わる多目標追尾装置の構成を示すブロック図である。
【図２０】この発明の実施の形態4に関わる多目標追尾装置による追尾処理の手順図である。
【図２１】この発明の実施の形態５に関わる多目標追尾装置の構成を示すブロック図である。
【図２２】この発明の実施の形態５に関わる多目標追尾装置による追尾処理の手順図である。
【符号の説明】
【００５１】
01；センサ、02；コスト行列計算部、03；Lagrange乗数設定部、04；Lagrange緩和解算出部、05；実現可能解算出部、06；航跡表示部、07；緩和解とコストｑ(u)記憶部、08；実現可能解とコストν(z)記憶部、11；2次元相関算出部、12；コスト行列更新部、13；コスト行列縮小部、14；Lagrange乗数初期値計算部、15；複数Lagrange乗数初期値計算部、16；Lagrange乗数切り換え部、17；処理法選択部、18；航跡記憶部、19；一時コスト行列記憶部、20；Lagrange乗数初期値記憶部。
【特許請求の範囲】
【請求項１】
センサからの観測値を入力し、その観測値を得た観測回数が予め設定されたパラメータ値の整数倍か否かを判別する処理法選択部と、
観測回数がパラメータ値の整数倍以外のとき、センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成・出力する2次元相関算出部と、
観測回数がパラメータ値の整数倍のとき、センサからの観測値からコスト行列を1サンプリング時刻毎に更新しながら算出するコスト行列更新部と、
このコスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす解を計算し、新たな航跡を生成・出力する実現可能解算出部を備えてなることを特徴とする多目標追尾装置。
【請求項２】
コスト行列更新部がコストの少ない上位m個の相関のみを計算し、他の相関の可能性を排除することを特徴とする請求項１記載の多目標追尾装置。
【請求項３】
センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成する2次元相関算出部と、
同じくセンサからの観測値からコスト行列を算出するコスト行列計算部と、
このコスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす実現可能解を計算し実現可能解が閾値以下のとき、新たな航跡を生成・出力する実現可能解算出部と、
実現可能解算出部が計算する実現可能解が閾値を超えるとき実現可能解と2次元相関算出部が算出する解を比較し、一致する部分をコスト行列から削除した縮小コスト行列をLagrange乗数再設定のためLagrange乗数設定部に入力するコスト行列縮小部を備えてなることを特徴とする多目標追尾装置。
【請求項４】
2次元相関算出部はMHT方式を使用し、コスト行列縮小部がMHT方式で計算された複数仮説の上位m個の全てに共通する部分のみをコスト行列から削除することを特徴とする請求項３に記述の多目標追尾装置。
【請求項５】
センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成する2次元相関算出部と、
同じくセンサからの観測値からコスト行列を算出するコスト行列計算部と、
コスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
2次元相関算出部が算出する解を実現可能解とするLagrange乗数の初期値を逆算するLagrange乗数初期値計算部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす実現可能解を計算する実現可能解算出部を備えてなることを特徴とする多目標追尾装置。
【請求項６】
センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成する2次元相関算出処理をMHT方式に従って行うMHT処理部と、
同じくセンサからの観測値からコスト行列を算出するコスト行列計算部と、
コスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下でm個の相関解を計算するLagrange緩和解算出部と、
m個のLagrange緩和解を修正して全ての制約条件を満たすm個の実現可能解を計算する実現可能解算出部と、
MHT処理部が算出する複数仮説のうち上位m個分について、それに相当する相関の解を実現可能解とするm通りのLagrange乗数の初期値を逆算する複数Lagrange乗数初期値計算部
を備えてなることを特徴とする多目標追尾装置。
【請求項７】
センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成する2次元相関算出処理をMHT方式に従って行うMHT処理部と、
同じくセンサからの観測値からコスト行列を算出するコスト行列計算部と、
コスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす実現可能解を計算する実現可能解算出部と、
MHT処理部が算出する複数仮説のうち上位m個分について、それに相当する相関の解を実現可能解とするm通りのLagrange乗数の初期値を逆算する複数Lagrange乗数初期値計算部と、
所定のLagrange乗数の初期値からの解の導出過程で、その収束度合いが小さい場合に複数Lagrange乗数初期値計算部が逆算した別のLagrange乗数の初期値に切り換えて解の導出を行うLagrange乗数初期値切り換え部を備えてなることを特徴とする多目標追尾装置。
【請求項１】
センサからの観測値を入力し、その観測値を得た観測回数が予め設定されたパラメータ値の整数倍か否かを判別する処理法選択部と、
観測回数がパラメータ値の整数倍以外のとき、センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成・出力する2次元相関算出部と、
観測回数がパラメータ値の整数倍のとき、センサからの観測値からコスト行列を1サンプリング時刻毎に更新しながら算出するコスト行列更新部と、
このコスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす解を計算し、新たな航跡を生成・出力する実現可能解算出部を備えてなることを特徴とする多目標追尾装置。
【請求項２】
コスト行列更新部がコストの少ない上位m個の相関のみを計算し、他の相関の可能性を排除することを特徴とする請求項１記載の多目標追尾装置。
【請求項３】
センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成する2次元相関算出部と、
同じくセンサからの観測値からコスト行列を算出するコスト行列計算部と、
このコスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす実現可能解を計算し実現可能解が閾値以下のとき、新たな航跡を生成・出力する実現可能解算出部と、
実現可能解算出部が計算する実現可能解が閾値を超えるとき実現可能解と2次元相関算出部が算出する解を比較し、一致する部分をコスト行列から削除した縮小コスト行列をLagrange乗数再設定のためLagrange乗数設定部に入力するコスト行列縮小部を備えてなることを特徴とする多目標追尾装置。
【請求項４】
2次元相関算出部はMHT方式を使用し、コスト行列縮小部がMHT方式で計算された複数仮説の上位m個の全てに共通する部分のみをコスト行列から削除することを特徴とする請求項３に記述の多目標追尾装置。
【請求項５】
センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成する2次元相関算出部と、
同じくセンサからの観測値からコスト行列を算出するコスト行列計算部と、
コスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
2次元相関算出部が算出する解を実現可能解とするLagrange乗数の初期値を逆算するLagrange乗数初期値計算部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす実現可能解を計算する実現可能解算出部を備えてなることを特徴とする多目標追尾装置。
【請求項６】
センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成する2次元相関算出処理をMHT方式に従って行うMHT処理部と、
同じくセンサからの観測値からコスト行列を算出するコスト行列計算部と、
コスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下でm個の相関解を計算するLagrange緩和解算出部と、
m個のLagrange緩和解を修正して全ての制約条件を満たすm個の実現可能解を計算する実現可能解算出部と、
MHT処理部が算出する複数仮説のうち上位m個分について、それに相当する相関の解を実現可能解とするm通りのLagrange乗数の初期値を逆算する複数Lagrange乗数初期値計算部
を備えてなることを特徴とする多目標追尾装置。
【請求項７】
センサからの観測値と既追尾航跡の相関を取り、新たな航跡を生成する2次元相関算出処理をMHT方式に従って行うMHT処理部と、
同じくセンサからの観測値からコスト行列を算出するコスト行列計算部と、
コスト行列に基づきLagrange緩和法を用いてLagrange乗数を計算するLagrange乗数設定部と、
Lagrange乗数によって緩和された制約条件下で相関解を計算するLagrange緩和解算出部と、
Lagrange緩和解を修正して全ての制約条件を満たす実現可能解を計算する実現可能解算出部と、
MHT処理部が算出する複数仮説のうち上位m個分について、それに相当する相関の解を実現可能解とするm通りのLagrange乗数の初期値を逆算する複数Lagrange乗数初期値計算部と、
所定のLagrange乗数の初期値からの解の導出過程で、その収束度合いが小さい場合に複数Lagrange乗数初期値計算部が逆算した別のLagrange乗数の初期値に切り換えて解の導出を行うLagrange乗数初期値切り換え部を備えてなることを特徴とする多目標追尾装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２００７−２１２２４４（Ｐ２００７−２１２２４４Ａ）
【公開日】平成１９年８月２３日（２００７．８．２３）
【国際特許分類】
【出願番号】特願２００６−３１４２５（Ｐ２００６−３１４２５）
【出願日】平成１８年２月８日（２００６．２．８）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成１９年８月２３日（２００７．８．２３）
【国際特許分類】
【出願日】平成１８年２月８日（２００６．２．８）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]