再標本化装置
【課題】メモリのランダムアクセスを避けつつ、並列的なスイッチング操作によって高速な再標本化を実現し、特に粒子数が少ない場合に有利な再標本化装置を提供する。
【解決手段】再標本化装置１は、尤度値が入力された時点における累積尤度値を算出する累積尤度値算出手段と、最大の累積尤度値未満の一様乱数を生成する一様乱数発生手段１３と、複数の累積尤度値と一様乱数とを一様乱数が生成される度に比較する複数の比較手段１４と、比較手段１４によって一様乱数以下であると判定された累積尤度値の中から最大の累積尤度値を選択し、当該最大の累積尤度値が算出される際に累積尤度値算出手段に入力された尤度値に対応する仮説を示すコードを生成するプライオリティエンコーダ１５と、複数のコードが示す複数の仮説に対応する接点を制御することで、再標本化された複数の仮説を出力するマトリックススイッチ１８と、を備えている。
【解決手段】再標本化装置１は、尤度値が入力された時点における累積尤度値を算出する累積尤度値算出手段と、最大の累積尤度値未満の一様乱数を生成する一様乱数発生手段１３と、複数の累積尤度値と一様乱数とを一様乱数が生成される度に比較する複数の比較手段１４と、比較手段１４によって一様乱数以下であると判定された累積尤度値の中から最大の累積尤度値を選択し、当該最大の累積尤度値が算出される際に累積尤度値算出手段に入力された尤度値に対応する仮説を示すコードを生成するプライオリティエンコーダ１５と、複数のコードが示す複数の仮説に対応する接点を制御することで、再標本化された複数の仮説を出力するマトリックススイッチ１８と、を備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、逐次モンテカルロ法によるパラメータ推定に関し、重み付けに応じた仮説の再標本化を行う再標本化装置に関する。
【背景技術】
【０００２】
観測情報と、観測量と状態量との間の関係を確率・統計的に表現したモデルと、に基づいて状態量（パラメータ）を推定する方法として、逐次モンテカルロ法（パーティクルフィルタ、粒子フィルタまたはCONDENSATION等とも呼ばれる）がある。逐次モンテカルロ法では、状態量の確率密度分布を空間方向に離散化（標本化）して表現することで、多次元の状態空間における確率的な挙動を能率的に模擬することができる。また、逐次モンテカルロ法では、この離散化された状態空間内の数量を仮説（粒子）と呼び、複数かつ有限の粒子によって確率密度分布を近似表現する。
【０００３】
逐次モンテカルロ法では、各粒子に重み付けを行うことが広く行われている。これにより、確率密度は状態空間内における粒子の密度と重みとの積によって表現されることになる。このように、逐次モンテカルロ法では、各粒子に重み付けを行うことで表現の自由度が増えるため、確率密度関数をより精度高く近似表現することができる。
【０００４】
その一方で、逐次モンテカルロ法では、重み付けの小さい粒子が増加すると、寄与の少ない粒子が数多く存在することになり無駄が生じる。そのため、重み付けに応じた出現頻度となるように、新たな粒子に再編成（重み付けはより均質なものとする）することで、寄与の少ない粒子を省く操作が行われる。この操作のことを再標本化（あるいはリサンプリング）と呼ぶ（例えば特許文献１の段落０００２、非特許文献１参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−１１７８６５号公報
【非特許文献】
【０００６】
【非特許文献１】A Doucet, N de Freitas and N Gordon: "Sequential Monte Carlo Methods in Practice," Springer, 2001. ISBN 978-0387951461.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、再標本化処理には、重み付けに応じた頻度で生起する特殊な乱数発生器が必要である。なお、「重み付けに応じた頻度で生起する」とは、重み付けの重い粒子ほど乱数が生起される確率が高いということを意味している。このような重み付けに応じた頻度で生起する特殊な乱数は、例えば重み付けを積算したものを累積確率密度分布とみなし、その逆関数に対して一様乱数を代入することで生成することができるが、従来はソフトウェア処理によって当該演算が行われており、論理回路や順序回路を用いたハードウェア処理によって前記した機能を高速に実現することは考えられてこなかった。
【０００８】
また、従来の逐次モンテカルロ法では、非常に多くの（例えば千個ないし十万個程度の）粒子を用いて演算を行うことが通例であり、粒子をメモリ上に記憶した上で、前記した特殊な乱数によるアドレッシングによってランダムアクセスを行って再標本化を実現していた。そのため、従来の逐次モンテカルロ法では、次元数と粒子数との積の回数だけメモリのランダムアクセスが発生することが、特に状態量の次元（すなわち粒子の次元）が高い場合における演算のボトルネックとなっていた。
【０００９】
一方、画像処理等の用途によっては、粒子数は比較的少ない数で良いものの、状態空間が極めて高次である場合や、非常に多数の逐次モンテカルロ法による処理を並列して実行しなければならない場合がある。このような用途においては、メモリのランダムアクセスが次元数や並列処理数に比例して増大することが問題点となるため、粒子数が少ない場合の利点（例えば再標本化による高速化等の利点）を生かすことができなかった。
【００１０】
本発明はかかる点に鑑みてなされたものであって、メモリのランダムアクセスを避けつつ、並列的なスイッチング操作によって高速な再標本化を実現することを課題とし、特に粒子数が少ない場合に有利な再標本化装置を提供することを課題とする。
【課題を解決するための手段】
【００１１】
前記課題を解決するために請求項１に係る再標本化装置は、逐次モンテカルロ法によりモデルのパラメータを推定する際に用いられる当該パラメータの解の候補である複数の仮説を、当該仮説の尤もらしさを示す尤度値に従って再標本化する再標本化装置であって、累積尤度値算出手段と、一様乱数発生手段と、複数の比較手段と、プライオリティエンコーダと、マトリックススイッチと、を備える構成とした。
【００１２】
これにより、再標本化装置は、累積尤度値算出手段に複数の仮説に対応した尤度値が順次入力され、当該累積尤度値算出手段によって、当該尤度値が入力された時点における累積尤度値を、当該尤度値が入力される度に算出する。また、再標本化装置は、一様乱数発生手段によって、累積値尤度値算出手段において算出された最大の累積尤度値未満の一様乱数を、所定の時間間隔で所定の回数だけ生成する。なお、一様乱数とは、指定区間内で一様と見なすことができる乱数、すなわち予め定められた区間内で全ての数が同じ確率で現れるような乱数のことを意味している。
【００１３】
また、再標本化装置は、複数の比較手段によって、累積尤度値算出手段において算出された複数の累積尤度値のそれぞれと、一様乱数発生手段によって生成された一様乱数とを、当該一様乱数が生成される度に比較する。また、再標本化装置は、プライオリティエンコーダによって、複数の比較手段において一様乱数以下であると判定された累積尤度値の中から最大の累積尤度値を選択し、当該最大の累積尤度値が算出される際に累積尤度値算出手段に入力された尤度値に対応する仮説を示すコードを、複数の比較手段から比較結果が入力される度に生成する。そして、再標本化装置は、複数の接点を備えるマトリックススイッチに複数の仮説が入力され、当該マトリックススイッチによって、プライオリティエンコーダにおいて生成された複数のコードが示す複数の仮説に対応する接点を制御することで、再標本化された複数の仮説を出力する。
【００１４】
このように、再標本化装置は、累積尤度値算出手段、一様乱数発生手段、複数の比較手段およびプライオリティエンコーダにおける一連の処理によって、再標本化の対象となる複数の仮説を決定する。そして、マトリックススイッチに複数の仮説が入力されると、当該マトリックススイッチから、前記した一連の処理によって決定された再標本化後の複数の仮説が一度に出力されることになる。従って、再標本化装置によれば、複数の仮説（粒子）をメモリに記憶する必要がないため、メモリのランダムアクセスが発生することがない。また、再標本化装置によれば、マトリックススイッチに標本化前の複数の仮説を入力すると、再標本化後の複数の仮説が一度に出力されるという並列的なスイッチング操作を実現することができる。
【００１５】
また、請求項２に係る再標本化装置は、請求項１に係る再標本化装置において、累積尤度値算出手段が、加算手段と、シフトレジスタと、を備える構成とした。
【００１６】
これにより、再標本化装置は、加算手段に複数の仮説に対応した複数の尤度値が順次入力され、当該加算手段によって、複数の尤度値を順次加算することで、入力された尤度値の数に対応する複数の累積尤度値を算出する。また、シフトレジスタに加算手段から累積尤度値が順次入力され、当該シフトレジスタによって、複数の比較手段に対して、複数の累積尤度値を同時に出力する。
【００１７】
このように、再標本化装置は、加算手段とシフトレジスタによって、入力された尤度値列を累積尤度値列に変換し、当該累積尤度値列を構成する複数の累積尤度列を複数の比較手段に対して同時に出力することができる。
【発明の効果】
【００１８】
請求項１および請求項２に係る発明によれば、論理回路や順序回路を用いてハードウェア処理を行うことで、仮説（粒子）をメモリに記憶する必要がなく、かつ、複数の仮説（粒子）を一度に再標本化することができるため、メモリのランダムアクセスを避けつつ、並列的なスイッチング操作によって高速な再標本化を実現することができる。また、請求項１および請求項２に係る発明によれば、状態空間が高次である場合であっても、並列的に処理を行うことができるため、粒子数が少ない場合において、次元数に関わらず高速に再標本化を行うことができる。
【図面の簡単な説明】
【００１９】
【図１】本発明に係る再標本化装置の構成例を示すブロック図である。
【図２】本発明に係る再標本化装置が備えるシフトレジスタの構成例を示すブロック図である。
【図３】本発明に係る再標本化装置が備える加算手段の構成例を示すブロック図である。
【図４】本発明に係る再標本化装置の入出力のタイミングを示すタイミングチャートである。
【図５】本発明に係る再標本化装置が備える一様乱数発生手段の構成例を示すブロック図である。
【図６】本発明に係る再標本化装置が備える一様乱数発生手段の入力のタイミングを示すタイミングチャートである。
【発明を実施するための形態】
【００２０】
本発明の実施形態に係る再標本化装置について、図面を参照しながら説明する。なお、以下の説明において、同一の構成については同一の名称及び符号を付し、詳細説明を省略する。
【００２１】
再標本化装置１は、逐次モンテカルロ法によるモデルのパラメータを推定する際に用いられる複数の仮説を、それらの仮説に対応した尤度値に従って再標本化するものである。ここで、仮説とは、前記したモデルのパラメータの解の候補のことを意味している。また、尤度値とは、それぞれの仮説の尤もらしさを示す値のことを意味している。
【００２２】
再標本化装置１は、例えば映像中における人間の顔の姿勢（位置、向き）をトラッキング（追跡）する場合において、当該映像中における人間の顔の位置（２次元）、大きさ（１次元）、向き（３次元）からなる顔姿勢パラメータ等を推定するためのパラメータ推定装置の内部に組み込まれて用いられる。このパラメータ推定装置は、まず前記した顔姿勢パラメータの複数の仮説を作成し、各仮説について、現在のフレームの画像に対して当該仮説がどの程度尤もらしいかの評価（尤度評価）を行う。そして、パラメータ推定装置は、各仮説の尤度を用いて最終的な姿勢パラメータ推定を行う。再標本化装置１は、このようなパラメータ推定装置において、前記した尤度に従って仮説の再標本化を行い、寄与の少ない仮説を省く処理を行う。
【００２３】
再標本化装置１は、ここでは図１に示すように、シフトレジスタ１０と、加算手段１２と、一様乱数発生手段１３と、比較手段１４と、プライオリティエンコーダ１５と、計数手段１６と、マトリックス制御手段１７と、マトリックススイッチ１８と、を備えている。そして、再標本化装置１は、図１に示すように、図示しない外部の仮説（粒子）生成手段からマトリックススイッチ１８に入力される複数の仮説（粒子）１〜Ｈを、図示しない外部の尤度評価手段から加算手段１２に入力される複数の尤度値と、一様乱数発生手段１３によって生成される一様乱数と、に基づいて複数の仮説（粒子）１〜Ｋに再標本化する。なお、再標本化装置１が備えるシフトレジスタ１０および加算手段１２は、後記するように、外部から入力される尤度値から累積尤度値を算出するための累積尤度値算出手段として機能する。また、前記した「Ｈ」および「Ｋ」は、２以上の整数を意味しており、同数であっても同数でなくてもどちらでも構わない。
【００２４】
シフトレジスタ１０は、予め定められたクロックに同期して、データを内部でシフトさせながら保持するものである。シフトレジスタ１０は、具体的には図１に示すように、加算手段１２から順次入力される複数の累積尤度値のそれぞれを保持し、後記する複数の比較手段１４に対して、それぞれの累積尤度値を同時に出力する。シフトレジスタ１０は、図１に示すように、複数の遅延手段１１−１，１１−２，１１−３，・・・，１１−Ｈから構成される。すなわち、シフトレジスタ１０は、図１に示すように、遅延手段がＨ段分カスケード接続されて構成される。
【００２５】
シフトレジスタ１０には、図１に示すように、クロックφ１のタイミングで、加算手段１２から累積尤度値が順次入力される。この累積尤度値は、図示しない外部の尤度評価手段から順次入力される尤度値が順次加算されたものであり、後に入力されるものほど値が大きくなる。そして、シフトレジスタ１０は、図１に示すように、順次入力される累積尤度値を遅延手段１１−Ｈ、・・・、遅延手段１１−３、遅延手段１１−２、遅延手段１１−１、の順序で上方向に順次シフトさせ、遅延手段１１−１，１１−２，１１−３，・・・，１１−Ｈのそれぞれに累積尤度値を保持させる。なお、以下の説明では、複数の遅延手段１１−１，１１−２，１１−３，・・・，１１−Ｈを包括して、「遅延手段１１−ｈ（ｈは１以上Ｈ以下の整数）」と表記する場合がある。
【００２６】
遅延手段１１−ｈは、入力された数値をクロック入力のタイミングで保持するとともに、当該数値をリセット入力のタイミングで破棄するものである。なお、遅延手段１１−ｈが保持または破棄する数値は、整数、固定小数点、または浮動小数点のいずれであっても構わない。遅延手段１１−ｈは、具体的には図１に示すように、後記する加算手段１２から入力される累積尤度値を、図示しない外部のクロック発生手段から入力されるクロックφ１のタイミングで保持するとともに、図示しない外部のリセット発生手段から入力されるリセット入力Ｒのタイミングで破棄して値ゼロを出力する。
【００２７】
ここで、累積尤度値とは、前記したように、図示しない外部の尤度評価手段から入力される複数の尤度値を加算したものである。例えば、再標本化装置１の加算手段１２に対して、尤度値Ｌ１、尤度値Ｌ２、尤度値Ｌ３および尤度値Ｌ４がこの順番で入力される場合、これらの尤度値が入力される度に、後記する加算手段１２によって累積尤度値Ａ１（＝Ｌ１）、累積尤度値Ａ２（＝Ｌ１＋Ｌ２）、累積尤度値Ａ３（＝Ｌ１＋Ｌ２＋Ｌ３）および累積尤度値Ａ４（＝Ｌ１＋Ｌ２＋Ｌ３＋Ｌ４））が順次算出され、遅延手段１１−ｈ（ここではｈ＝４）に順次入力される。このように、累積尤度値は、加算手段によって、図示しない外部の尤度評価手段から入力される尤度値の数と同じ数だけ算出され、遅延手段１１−ｈに順次入力される。
【００２８】
遅延手段１１−ｈは、具体的には図２に示すように、リセット入力付きのＤ（Ｄｅｌａｙ）フリップフロップによって実現することができる。ここで、遅延手段１１−ｈの上下方向の段数は、図１に示すように、再標本化装置１に入力される尤度値（または粒子）の数Ｈに対応している。すなわち、遅延手段１１−ｈは、例えば再標本化装置１に入力される尤度値の個数Ｈが４つである場合、上下方向に少なくとも４段配置される。
【００２９】
また、遅延手段１１−ｈの左右方向の段数は、再標本化装置１に入力される尤度値の個数Ｈと尤度値の範囲（例えば尤度値を２進数で表わした場合のビット数）とに対応している。すなわち、遅延手段１１−ｈは、例えば２進数の数値が入力される場合において、再標本化装置１に入力される尤度値の個数Ｈが４つであり、それぞれの尤度値の範囲が０以上２５５以下（つまり２進数で８ビット以下）である場合、左右方向に少なくとも１０段配置される。これは、例えば再標本化装置１の加算手段１２に対して、４回とも尤度値「２５５」が入力され、当該加算手段１２から遅延手段１１−ｈに対して、累積尤度値「１０２０（つまり２進数で１０ビット）」が入力された場合であっても、桁があふれないようにするためである。
【００３０】
遅延手段１１−ｈには、図１に示すように、後記する加算手段１２から、クロックφ１に同期して累積尤度値Ａ１，Ａ２，Ａ３，・・・，ＡＨが順次入力される。そして、遅延手段１１−ｈは、当該クロックφ１の立ち上がりエッジのタイミングで、最下段の遅延手段１１−Ｈから最上段の遅延手段１１−１に向かって、累積尤度値Ａ１，Ａ２，Ａ３，・・・，ＡＨを一段ずつ順次シフトさせて保持させる。そして、遅延手段１１−ｈは、比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）に対して、累積尤度値Ａ１，Ａ２，Ａ３，・・・を同時に出力し、一様乱数発生手段１３に対して、最大の累積尤度値ＡＨを出力する。なお、以下の説明では、複数の累積尤度値Ａ１，Ａ２，Ａ３，・・・，ＡＨを包括して、「累積尤度値Ａｈ（ｈは１以上Ｈ以下の整数）」と表記する場合がある。
【００３１】
加算手段１２は、入力された数値を加算するものである。なお、加算手段１２が加算する２つの数値は、整数、固定小数点、または浮動小数点のいずれであっても構わない。加算手段１２には、図１に示すように、図示しない外部の尤度評価手段から、クロックφ１に同期して尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨが順次入力されるとともに、シフトレジスタ１０の最下段に配置された遅延手段１１−Ｈから、クロックφ１に同期して累積尤度値が順次入力される。ここで、尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨは、後記するマトリックススイッチ１８に入力される、再標本化をしようとする複数の仮説（粒子）１〜Ｈに対応したものである。
【００３２】
そして、加算手段１２は、両者を加算することでさらに累積尤度値を算出し、これを遅延手段１１−Ｈに出力する。すなわち、加算手段１２は、尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨが入力される度に、当該尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨが入力された時点における累積尤度値を算出し、当該累積尤度値を遅延手段１１−Ｈに出力する。なお、以下の説明では、複数の尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨを包括して、「尤度値Ｌｈ（ｈは１以上Ｈ以下の整数）」と表記する場合がある。
【００３３】
加算手段１２は、入力された２つの数値が整数または固定小数点による２進数で表現されている場合には、例えば半加算器１個以上および全加算器０個以上によって実現することができる。但し、加算手段１２の具体的構成は、図示しない外部の尤度評価手段から入力される尤度値Ｌｈの値の範囲によって異なる。例えば、加算手段１２に入力される一方の値、すなわち図示しない外部の尤度評価手段から入力される尤度値Ｌｈの範囲が０以上Ｍ以下の整数値である場合、加算手段１２に入力される他方の値、すなわち遅延手段１１−Ｈから入力される累積尤度値は、０以上Ｍ×（Ｈ−１）以下の整数値となる。従って、この場合、以下の式（１）によって加算手段１２を構成する最小限の半加算器の数を算出することができるとともに、以下の式（２）によって加算手段１２を構成する最小限の全加算器の数を算出することができる。
【００３４】
【数１】
【００３５】
【数２】
【００３６】
加算手段１２は、例えば図示しない外部の尤度評価手段から入力される尤度値Ｌｈの範囲が０以上２５５以下であり、シフトレジスタ１０の段数Ｈ、すなわち再標本化装置１に入力される尤度値の個数Ｈが８個である場合、図３に示すように、少なくとも半加算器５個と全加算器７個とで構成することができる。ここで、図３において、Ａ，Ｂ，ＳおよびＣの端子を有するブロックは、半加算器を表わしており、Ａ，Ｂ，Ｘ，ＳおよびＣの端子を有するブロックは、全加算器を示している。そして、図３における半加算器および全加算器の端子の記号は、ＡおよびＢが被加算器入力、Ｘがキャリー入力、Ｓが加算結果出力、Ｃがキャリー出力を表わしている。
【００３７】
再標本化装置１では、シフトレジスタ１０および加算手段１２、すなわち累積尤度値算出手段を前記したように構成することで、最上段の遅延手段１１−１から最下段の遅延手段１１−Ｈに向かって、それぞれ累積尤度値Ａｈが現れる。すなわち、再標本化装置１では、外部の図示しない尤度評価手段から加算手段１２に対して尤度列（尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨ）が入力されると、遅延手段１１−ｈから累積尤度列（累積尤度値Ａ１，Ａ２，Ａ３，・・・，ＡＨ）が出力される。
【００３８】
以下、遅延手段１１−ｈおよび加算手段１２の動作について、図４を参照しながら簡単に説明する。なお、以下では、再標本化装置１に入力される尤度値Ｌｈの個数Ｈを４個（つまり遅延手段１１−ｈの段数Ｈを４段）とした場合について説明する。また、図４のタイミングチャートにおいて途切れている箇所は、途中の動作を省略していることを示している。
【００３９】
まず、加算手段１２は、１回目のクロックφ１の立ち上がりエッジのタイミングで外部から尤度値Ｌ１が入力されると、これを累積尤度値Ａ１として遅延手段１１−ｈの最下段（説明の便宜上、「遅延手段１１−４」とする）に出力する。すると、遅延手段１１−４は、加算手段１２から入力された累積尤度値Ａ１（＝尤度値Ｌ１）を保持する。
【００４０】
次に、加算手段１２は、２回目のクロックφ１の立ち上がりエッジのタイミングで外部から尤度値Ｌ２が入力されるとともに、遅延手段１１−４から累積尤度値Ａ１（＝尤度値Ｌ１）が入力されると、両者を加算して累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を算出し、これを遅延手段１１−４に出力する。すると、遅延手段１１−４は、前記した累積尤度値Ａ１（＝尤度値Ｌ１）を上段の遅延手段１１−３へとシフトさせ、加算手段１２から入力された累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を保持する。
【００４１】
次に、加算手段１２は、３回目のクロックφ１の立ち上がりエッジのタイミングで外部から尤度値Ｌ３が入力されるとともに、遅延手段１１−４から累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）が入力されると、両者を加算して累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）を算出し、これを遅延手段１１−４に出力する。すると、遅延手段１１−４は、前記した累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を上段の遅延手段１１−３へとシフトさせ、加算手段１２から入力された累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）を保持する。また、遅延手段１１−３は、前記した累積尤度値Ａ１（＝尤度値Ｌ１）を上段の遅延手段１１−２へとシフトさせ、遅延手段１１−４から入力された累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を保持する。
【００４２】
次に、加算手段１２は、４回目のクロックφ１の立ち上がりエッジのタイミングで外部から尤度値Ｌ４が入力されるとともに、遅延手段１１−４から累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）が入力されると、両者を加算して累積尤度値Ａ４（＝尤度値Ｌ１＋Ｌ２＋Ｌ３＋Ｌ４）を算出し、これを遅延手段１１−４に出力する。すると、遅延手段１１−４は、前記した累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）を上段の遅延手段１１−３へとシフトさせ、加算手段１２から入力された累積尤度値Ａ４（＝尤度値Ｌ１＋Ｌ２＋Ｌ３＋Ｌ４）を保持する。また、遅延手段１１−３は、前記した累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を上段の遅延手段１１−２へとシフトさせ、遅延手段１１−４から入力された累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）を保持する。また、遅延手段１１−２は、前記した累積尤度値Ａ１（＝尤度値Ｌ１）を上段の遅延手段１１−１へとシフトさせ、遅延手段１１−３から入力された累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を保持する。
【００４３】
以上のような動作により、累積尤度算手段は、クロックφ１に同期して、加算手段１２によって尤度値Ｌ１，Ｌ２，Ｌ３，Ｌ４の数に対応する累積尤度値Ａ１，Ａ２，Ａ３，Ａ４を算出し、遅延手段１１−１，１１−２，１１−３，１１−４によって累積尤度値Ａ１，Ａ２，Ａ３，Ａ４をそれぞれ保持する。そして、クロックφ２に同期して、遅延手段１１−４は、一様乱数発生手段１３に対して累積尤度値Ａ４を出力するとともに、遅延手段１１−１，１１−２，１１−３は、複数の比較手段１４に対して累積尤度値Ａ１，Ａ２，Ａ３を出力する。以下、再標本化装置１の残りの構成について説明する。
【００４４】
一様乱数発生手段１３は、一様乱数を発生させるものである。この一様乱数とは、前記したように、指定区間内で一様と見なすことができる乱数のことを意味している。一様乱数発生手段１３は、図１に示すように、一様乱数を所定の時間間隔ごと、すなわちクロックφ２ごとに発生させるとともに、所定の回数、すなわち出力する粒子の数と同じＫ回発生させる。一様乱数発生手段１３には、図１に示すように、シフトレジスタ１０の最下段に配置された遅延手段１１−Ｈから累積尤度値ＡＨが入力される。そして、一様乱数発生手段１３は、当該累積尤度値ＡＨに基づいて、０以上ＡＨ未満の範囲の一様乱数を発生させる。すなわち、一様乱数発生手段１３は、加算手段１２によって算出された最大の累積尤度値ＡＨ未満の一様乱数を生成する。
【００４５】
一様乱数発生手段１３は、例えばＭ系列やＰＮ系列等の擬似乱数発生回路によって発生させた乱数値ｓ（ｓがとり得る値の最小値は０、最大値はＡＨ以上とする）に対して、遅延手段１１−Ｈから入力された累積尤度値ＡＨによる剰余演算を施すことによって実現することができる。従って、一様乱数発生手段１３は、具体的には図５に示すように、擬似乱数発生回路２０と、シフトレジスタ２１と、切替回路２２と、ラッチ回路２３と、減算回路２４と、シフトレジスタ２５と、ラッチ回路２６と、から構成することができる。
【００４６】
擬似乱数発生回路２０は、擬似的な乱数を発生させるものである。擬似乱数発生回路２０は、前記したように、例えばＭ系列やＰＮ系列の乱数発生回路によって構成することができ、ここでは図５に示すように、シフトレジスタ２１に排他的論理和ゲートを３個接続した周期６５５３５のＭ系列発生回路で構成されている。
【００４７】
一様乱数発生手段１３の残りの構成であるシフトレジスタ２１、切替回路２２、ラッチ回路２３、減算回路２４およびシフトレジスタ２５は、前記した累積尤度値ＡＨによる剰余演算を施すための剰余演算回路を構成するものである。これらの構成はそれぞれ一般的なものであるため、詳細な説明は省略する。
【００４８】
以下、一様乱数発生手段１３の動作について、図６を参照（適宜図５も参照）しながら簡単に説明する。また、図６のタイミングチャートにおいて途切れている箇所は、途中の動作を省略していることを示している。
【００４９】
まず、一様乱数発生手段１３は、図６に示すように、クロックφ３によって擬似乱数発生回路２０の擬似乱数の乱数値ｓを更新する。次に、一様乱数発生手段１３は、図６に示すように、制御信号ｃ１をローレベルにすることで、切替回路２２のスイッチ群を擬似乱数発生回路２０側に倒しつつ、シフトレジスタ２５をクリアする。次に、一様乱数発生手段１３は、図６に示すように、クロックφ４に１番目の正のパルスを与え、ラッチ回路２３に擬似乱数発生回路２０が発生させた擬似乱数の乱数値ｓをラッチする。次に、一様乱数発生手段１３は、図６に示すように、制御信号ｃ２をローレベルとした状態で、クロックφ５に１番目の正のパルスを与え、Ｈ番目の累積尤度値出力の値（シフトレジスタ１０の最下段の遅延手段１１−Ｈから出力される累積尤度値ＡＨ）をシフトレジスタ２５にセットし、その後、制御信号ｃ２をハイレベルにする。
【００５０】
次に、一様乱数発生手段１３は、図６に示すように、クロックφ４とクロックφ５について、２番目ないし（ビット幅−１）番目（図５の例では１５番目）まで、交互に正のパルスを与える（但し、クロックφ４をクロックφ５に先行させる）。これにより、擬似乱数の乱数値ｓから引き得る最大の「ＡＨの整数倍」を引いた結果（すなわち、ｓをＡＨで除した際の剰余（Ｒ＝ｓ％ＡＨ））が減算回路２４の出力に現れる。そして、一様乱数発生手段１３は、図６に示すように、最後にクロックφ２に正のパルスを与えることで、０以上ＡＨ未満の整数の一様乱数Ｒ（以下、単に乱数Ｒという）をラッチ回路２６にラッチし、乱数出力を得る。このように、一様乱数発生手段１３はクロックφ２ごとに乱数Ｒを発生させ、図１に示すように、その都度当該乱数Ｒを複数の比較手段１４に対して出力する。
【００５１】
なお、図６のタイミングチャートにおける「ＡＨ−１が乱数Ｒの最大値となる」とは、後記する比較手段１４において、累積尤度値と比較される乱数Ｒの最大値が実質的にＡＨ−１であることを示している。すなわち、一様乱数発生手段１３は、前記したように０以上ＡＨ未満の乱数Ｒを発生させることができるが、図１に示すように、比較手段１４にはシフトレジスタ１０の最下段に配置された遅延手段１１−Ｈから累積尤度値ＡＨが入力されない。そのため、仮に一様乱数発生手段１３によってＡＨ−１超えＡＨ以下の乱数Ｒが生成され、当該乱数Ｒが比較手段１４に入力されると、後記する比較結果Ｄｈの値が必ず０となる。従って、図６のタイミングチャートにおける「ＡＨ−１が乱数Ｒの最大値となる」とは、乱数Ｒの実質的な最大値がＡＨ−１であることを示している。
【００５２】
比較手段１４は、入力された２つの数値の大小を比較するものである。比較手段１４は、図１に示すように、複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）から構成される。すなわち、比較手段１４は、図１に示すように、比較手段が、シフトレジスタ１０を構成する遅延手段の段数Ｈよりも１個少ないがＨ−１段分カスケード接続されて構成される。
【００５３】
複数の比較手段１４には、図１に示すように、遅延手段１１−Ｈを除く遅延手段１１−ｈから、累積尤度値Ａｈがそれぞれ同時に入力されるとともに、一様乱数発生手段１３から乱数Ｒがそれぞれ同時に入力される。そして、比較手段１４は、前記した一様乱数発生手段１３によって一様乱数Ｒが生成されて入力される度に、以下の式（３）に示すように、累積尤度値Ａｈと乱数Ｒとの大小を比較し、その比較結果Ｄｈをプライオリティエンコーダ１５に出力する。すなわち、比較手段１４は、以下の式（３）に示すように、累積尤度値Ａｈが乱数Ｒより大きい場合は「比較結果Ｄｈ＝０」を出力し、累積尤度値Ａｈが乱数Ｒ以下である場合は「比較結果Ｄｈ＝１」を出力する。
【００５４】
【数３】
【００５５】
ここで、「比較結果Ｄｈを出力する」とは、例えば再標本化装置１の加算手段１２にＨ個の尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨが入力された場合に、比較手段１４が、入力された尤度値Ｌｈよりも１個少ないＨ−１個の比較結果Ｄ１，Ｄ２，Ｄ３，・・・，ＤＨ−１をプライオリティエンコーダ１５に対して出力することを示している。なお、前記した式（３）において、Ｄｈの値「０」はローレベルと読み替え、Ｄｈの値「１」はハイレベルと読み替えても構わない。
【００５６】
例えば、再標本化装置１の加算手段１２に入力される尤度値Ｌｈの個数Ｈが４つ（つまり遅延手段１１−ｈの段数Ｈが４段）である場合、比較手段１４−１には、遅延手段１１−１から累積尤度値Ａ１が入力され、比較手段１４−２には、遅延手段１１−２から累積尤度値Ａ２が入力される。そして、比較手段１４の最下段（説明の便宜上、「比較手段１４−３」とする）には、最下段の遅延手段１１−３から累積尤度値Ａ３が入力される。また同時に、比較手段１４−１，１４−２，１４−３には、クロックφ２に同期して乱数Ｒがそれぞれ入力される。
【００５７】
そして、比較手段１４−１は、累積尤度値Ａ１と乱数Ｒとの比較結果Ｄ１をプライオリティエンコーダ１５に出力し、比較手段１４−２は、累積尤度値Ａ２と乱数Ｒとの比較結果Ｄ２をプライオリティエンコーダ１５に出力し、比較手段１４−３は、累積尤度値Ａ３と乱数Ｒとの比較結果Ｄ３をプライオリティエンコーダ１５に出力する。このように、再標本化装置１の加算手段１２に４つの尤度値Ｌ１，Ｌ２，Ｌ３，Ｌ４が入力されると、プライオリティエンコーダ１５には、３つの比較結果Ｄ１，Ｄ２，Ｄ３が同時に入力されることになる。
【００５８】
比較手段１４は、例えば累積尤度値Ａｈと乱数Ｒとの差分を演算する減算回路として実装し、Ｒ−Ａｈを演算した結果として現れる最上位ビットのボローフラグを比較結果Ｄｈとすることができる。
【００５９】
プライオリティエンコーダ１５は、優先順位の最も高い入力に対応するコードを出力するものである。プライオリティエンコーダ１５には、具体的には図１に示すように、複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）のそれぞれから比較結果Ｄｈが入力される。この比較結果Ｄｈは、前記した式（３）に示すように、０または１の数値（フラグ）から構成されるものである。そして、プライオリティエンコーダ１５は、複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）から入力される複数の比較結果Ｄｈのうち、Ｄｈ＝１（乱数Ｒ以下であると判定された比較結果）となるものを選出し、値が１である比較結果Ｄｈのうちの最大の「ｈ」を選択する。なお、全てのｈについてＤｈ＝０の場合には、最大の「ｈ」は０であったものとみなす。
【００６０】
ここで、前記した「複数の比較結果Ｄｈのうち、Ｄｈ＝１（乱数Ｒ以下であると判定された比較結果）となるものを選出し、値が１である比較結果Ｄｈのうちの最大の「ｈ」を選択する」とは、言い換えれば、複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）によって乱数Ｒ以下であると判定された累積尤度値Ａｈとなるものを選出し、これらの累積尤度値Ａｈの中から、最大の累積尤度値Ａｈを選択するとともに、当該累積尤度値Ａｈのインデックス（下付き数字）である「ｈ」を選択するという処理のことを意味している。
【００６１】
そして、プライオリティエンコーダ１５は、選択したｈに１を加えた（ｈ＋１）を標本点Ｐとしてマトリックス制御手段１７に出力する。ここで、標本点Ｐとは、言い換えれば、前記した最大の累積尤度値Ａｈが算出される際に加算手段１２（累積尤度値算出手段）に入力された尤度値Ｌｈに対応する仮説を示すコードのことを意味している。なお、プライオリティエンコーダ１５は、前記した複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）から比較結果Ｄｈが入力される度に、コード（標本点Ｐ）を生成し、これをマトリックス制御手段１７に出力する。
【００６２】
例えば、再標本化装置１に入力される尤度値Ｌｈの個数Ｈが４つ（つまり遅延手段１１−ｈの段数Ｈが４段）である場合、プライオリティエンコーダ１５には、比較手段１４−１から比較結果Ｄ１が、比較手段１４−１から比較結果Ｄ２が、比較手段１４の最下段（説明の便宜上、「比較手段１４−３」とする）から比較結果Ｄ３が入力される。そして、例えばこれらの比較結果Ｄ１，Ｄ２，Ｄ３の値がそれぞれ「Ｄ１＝１，Ｄ２＝１，Ｄ３＝０」である場合、プライオリティエンコーダ１５は、値が１である比較結果Ｄ１，Ｄ２のうちの最大の「ｈ」（インデックス、下付き数字）である「２」を選出し、当該「２」に１を加えた「３」のコード（標本点Ｐ）をマトリックス制御手段１７に出力する。
【００６３】
ここで、プライオリティエンコーダ１５が生成する標本点Ｐは、再標本化の対象となる仮説を示している。従って、前記した例において、プライオリティエンコーダ１５によって値が１である比較結果Ｄ１，Ｄ２のうちの最大の「ｈ」に１を加えた「３」を選出するという処理は、比較手段１４−３によって乱数Ｒ以下であると判定された累積尤度値Ａ１，Ａ２の中で最も大きい累積尤度値Ａ２を選択した後に、当該累積尤度値Ａ２よりも一段階大きい累積尤度値Ａ３を選択し、当該累積尤度値Ａ３が算出される際に加算手段１２に入力された尤度値Ｌ３に対応する仮説を選出するという処理に相当することになる。
【００６４】
以上の処理により、比較手段１４の比較結果Ｄｈのうち、１（ハイレベル）のビットが立つ「ｈ」である標本点Ｐは、近似的に一様な乱数Ｒを累積尤度関数の逆関数に代入した結果に近似することになる。すなわち、標本点Ｐは、累積尤度関数に近似的に比例する確率で生起することになる。
【００６５】
計数手段１６は、クロックφ２のタイミングで１〜Ｋまで計数するカウンタである。このＫは、図１に示すように、再標本化後の粒子の数（自然数）であり、予め任意の数で設定される。計数手段１６は、例えばバイナリカウンタを用いることができ、図１に示すように、クロックφ２に同期して、そのカウント値ｋをマトリックス制御手段１７に出力する。
【００６６】
マトリックス制御手段１７は、プライオリティエンコーダ１５から入力される標本点Ｐ（コード）と、計数手段１６から入力されるカウント値ｋと、に基づいてマトリックススイッチ１８の接点の継断を制御するものである。マトリックス制御手段１７は、具体的には図１に示すように、プライオリティエンコーダ１５から標本点Ｐが、計数手段１６からカウント値ｋが、それぞれ入力されると、Ｐ番目の入力（図１では行）とｋ番目の出力（図１では列）との接点を閉じ、Ｐ番目以外の入力（図１では行）とｋ番目の出力（図１では列）との接点を開放するような接点制御信号を生成し、これをマトリックススイッチ１８に出力する。これにより、マトリックス制御手段１７は、図１に示すように、１番目〜Ｋ番目の各粒子（仮説）の出力を、１番目〜Ｈ番目の粒子の入力の中の１つの入力に接続することができ、その結果として、マトリックススイッチ１８に入力されたＨ個の粒子を再標本化後のＫ個の粒子に写像して出力することができる。
【００６７】
マトリックススイッチ１８は、スイッチング操作によって、外部から入力される複数の仮説（粒子）を複数の仮説（粒子）に再標本化するものである。マトリックススイッチ１８は、図１に示すように、碁盤状に接点が配置されており、マトリックス制御手段１７から入力される接点制御信号に従って、これらの接点を閉鎖または開放するように構成されている。また、マトリックススイッチ１８が備える接点は、図１に示すように、外部から入力される再標本化前の複数の仮説（粒子）１〜Ｈと、外部に出力する再標本化後の複数の仮説（粒子）１〜Ｋと、に対応している。このマトリックススイッチ１８は、例えばＣＭＯＳ（Complementary Metal Oxide Semiconductor）によるスイッチで実現することができる。
【００６８】
マトリックススイッチ１８には、図１に示すように、図示しない外部の仮説（粒子）生成手段から、再標本化前の複数の仮説（粒子）１〜Ｈが入力され、マトリックス制御手段１７から、接点制御信号が入力される。この接点制御信号には、プライオリティエンコーダ１５によって生成された標本点Ｐ（コード）と、計数手段１６によって計数されたカウント値ｋに関する情報が含まれている。そして、マトリックススイッチ１８は、当該接点制御信号に基づいて図１に示す接点を制御することで、再標本化後の複数の仮説（粒子）１〜Ｋを出力する。このような処理によって、マトリックススイッチ１８における粒子入力と粒子出力の関係が、再標本化前の粒子と再標本化後の粒子の関係となる。すなわち、マトリックススイッチ１８に複数の粒子の状態量（複数の仮説１〜Ｈ）を入力すると、即座に再標本化が実行され、再標本化後の複数の粒子の状態量（複数の仮説１〜Ｋ）が出力されることになる。
【００６９】
以上のような構成を備える再標本化装置１は、累積尤度値算出手段（加算手段１２およびシフトレジスタ１０）、一様乱数発生手段１３、複数の比較手段１４およびプライオリティエンコーダ１５における一連の処理によって、再標本化の対象となる複数の仮説を決定する。そして、マトリックススイッチ１８に複数の仮説が入力されると、当該マトリックススイッチ１８から、前記した一連の処理によって決定された再標本化後の複数の仮説が一度に出力されることになる。従って、再標本化装置１によれば、複数の仮説（粒子）をメモリに記憶する必要がないため、メモリのランダムアクセスが発生することがない。また、再標本化装置１によれば、マトリックススイッチ１８に標本化前の複数の仮説を入力すると、再標本化後の複数の仮説が一度に出力されるという並列的なスイッチング操作を実現することができる。
【００７０】
従って、再標本化装置１によれば、論理回路や順序回路を用いてハードウェア処理を行うことで、仮説（粒子）をメモリに記憶する必要がなく、かつ、複数の仮説（粒子）を一度に再標本化することができるため、メモリのランダムアクセスを避けつつ、並列的なスイッチング操作によって高速な再標本化を実現することができる。また、再標本化装置１によれば、状態空間が高次である場合であっても、並列的に処理を行うことができるため、粒子数が少ない場合において、次元数に関わらず高速に再標本化を行うことができる。
【００７１】
以上、本発明に係る再標本化装置について、発明を実施するための形態により具体的に説明したが、本発明の趣旨はこれらの記載に限定されるものではなく、特許請求の範囲の記載に基づいて広く解釈されなければならない。また、これらの記載に基づいて種々変更、改変等したものも本発明の趣旨に含まれることはいうまでもない。
【符号の説明】
【００７２】
１ 再標本化装置
１０ シフトレジスタ
１１−１，１１−２，１１−３，１１−Ｈ，１１−ｈ 遅延手段
１２ 加算手段
１３ 一様乱数発生手段
１４，１４−１，１４−２，１４−（Ｈ−１） 比較手段
１５ プライオリティエンコーダ
１６ 計数手段
１７ マトリックス制御手段
１８ マトリックススイッチ
２０ 擬似乱数発生回路
２１ シフトレジスタ
２２ 切替回路
２３ ラッチ回路
２４ 減算回路
２５ シフトレジスタ
２６ ラッチ回路
【技術分野】
【０００１】
本発明は、逐次モンテカルロ法によるパラメータ推定に関し、重み付けに応じた仮説の再標本化を行う再標本化装置に関する。
【背景技術】
【０００２】
観測情報と、観測量と状態量との間の関係を確率・統計的に表現したモデルと、に基づいて状態量（パラメータ）を推定する方法として、逐次モンテカルロ法（パーティクルフィルタ、粒子フィルタまたはCONDENSATION等とも呼ばれる）がある。逐次モンテカルロ法では、状態量の確率密度分布を空間方向に離散化（標本化）して表現することで、多次元の状態空間における確率的な挙動を能率的に模擬することができる。また、逐次モンテカルロ法では、この離散化された状態空間内の数量を仮説（粒子）と呼び、複数かつ有限の粒子によって確率密度分布を近似表現する。
【０００３】
逐次モンテカルロ法では、各粒子に重み付けを行うことが広く行われている。これにより、確率密度は状態空間内における粒子の密度と重みとの積によって表現されることになる。このように、逐次モンテカルロ法では、各粒子に重み付けを行うことで表現の自由度が増えるため、確率密度関数をより精度高く近似表現することができる。
【０００４】
その一方で、逐次モンテカルロ法では、重み付けの小さい粒子が増加すると、寄与の少ない粒子が数多く存在することになり無駄が生じる。そのため、重み付けに応じた出現頻度となるように、新たな粒子に再編成（重み付けはより均質なものとする）することで、寄与の少ない粒子を省く操作が行われる。この操作のことを再標本化（あるいはリサンプリング）と呼ぶ（例えば特許文献１の段落０００２、非特許文献１参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−１１７８６５号公報
【非特許文献】
【０００６】
【非特許文献１】A Doucet, N de Freitas and N Gordon: "Sequential Monte Carlo Methods in Practice," Springer, 2001. ISBN 978-0387951461.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、再標本化処理には、重み付けに応じた頻度で生起する特殊な乱数発生器が必要である。なお、「重み付けに応じた頻度で生起する」とは、重み付けの重い粒子ほど乱数が生起される確率が高いということを意味している。このような重み付けに応じた頻度で生起する特殊な乱数は、例えば重み付けを積算したものを累積確率密度分布とみなし、その逆関数に対して一様乱数を代入することで生成することができるが、従来はソフトウェア処理によって当該演算が行われており、論理回路や順序回路を用いたハードウェア処理によって前記した機能を高速に実現することは考えられてこなかった。
【０００８】
また、従来の逐次モンテカルロ法では、非常に多くの（例えば千個ないし十万個程度の）粒子を用いて演算を行うことが通例であり、粒子をメモリ上に記憶した上で、前記した特殊な乱数によるアドレッシングによってランダムアクセスを行って再標本化を実現していた。そのため、従来の逐次モンテカルロ法では、次元数と粒子数との積の回数だけメモリのランダムアクセスが発生することが、特に状態量の次元（すなわち粒子の次元）が高い場合における演算のボトルネックとなっていた。
【０００９】
一方、画像処理等の用途によっては、粒子数は比較的少ない数で良いものの、状態空間が極めて高次である場合や、非常に多数の逐次モンテカルロ法による処理を並列して実行しなければならない場合がある。このような用途においては、メモリのランダムアクセスが次元数や並列処理数に比例して増大することが問題点となるため、粒子数が少ない場合の利点（例えば再標本化による高速化等の利点）を生かすことができなかった。
【００１０】
本発明はかかる点に鑑みてなされたものであって、メモリのランダムアクセスを避けつつ、並列的なスイッチング操作によって高速な再標本化を実現することを課題とし、特に粒子数が少ない場合に有利な再標本化装置を提供することを課題とする。
【課題を解決するための手段】
【００１１】
前記課題を解決するために請求項１に係る再標本化装置は、逐次モンテカルロ法によりモデルのパラメータを推定する際に用いられる当該パラメータの解の候補である複数の仮説を、当該仮説の尤もらしさを示す尤度値に従って再標本化する再標本化装置であって、累積尤度値算出手段と、一様乱数発生手段と、複数の比較手段と、プライオリティエンコーダと、マトリックススイッチと、を備える構成とした。
【００１２】
これにより、再標本化装置は、累積尤度値算出手段に複数の仮説に対応した尤度値が順次入力され、当該累積尤度値算出手段によって、当該尤度値が入力された時点における累積尤度値を、当該尤度値が入力される度に算出する。また、再標本化装置は、一様乱数発生手段によって、累積値尤度値算出手段において算出された最大の累積尤度値未満の一様乱数を、所定の時間間隔で所定の回数だけ生成する。なお、一様乱数とは、指定区間内で一様と見なすことができる乱数、すなわち予め定められた区間内で全ての数が同じ確率で現れるような乱数のことを意味している。
【００１３】
また、再標本化装置は、複数の比較手段によって、累積尤度値算出手段において算出された複数の累積尤度値のそれぞれと、一様乱数発生手段によって生成された一様乱数とを、当該一様乱数が生成される度に比較する。また、再標本化装置は、プライオリティエンコーダによって、複数の比較手段において一様乱数以下であると判定された累積尤度値の中から最大の累積尤度値を選択し、当該最大の累積尤度値が算出される際に累積尤度値算出手段に入力された尤度値に対応する仮説を示すコードを、複数の比較手段から比較結果が入力される度に生成する。そして、再標本化装置は、複数の接点を備えるマトリックススイッチに複数の仮説が入力され、当該マトリックススイッチによって、プライオリティエンコーダにおいて生成された複数のコードが示す複数の仮説に対応する接点を制御することで、再標本化された複数の仮説を出力する。
【００１４】
このように、再標本化装置は、累積尤度値算出手段、一様乱数発生手段、複数の比較手段およびプライオリティエンコーダにおける一連の処理によって、再標本化の対象となる複数の仮説を決定する。そして、マトリックススイッチに複数の仮説が入力されると、当該マトリックススイッチから、前記した一連の処理によって決定された再標本化後の複数の仮説が一度に出力されることになる。従って、再標本化装置によれば、複数の仮説（粒子）をメモリに記憶する必要がないため、メモリのランダムアクセスが発生することがない。また、再標本化装置によれば、マトリックススイッチに標本化前の複数の仮説を入力すると、再標本化後の複数の仮説が一度に出力されるという並列的なスイッチング操作を実現することができる。
【００１５】
また、請求項２に係る再標本化装置は、請求項１に係る再標本化装置において、累積尤度値算出手段が、加算手段と、シフトレジスタと、を備える構成とした。
【００１６】
これにより、再標本化装置は、加算手段に複数の仮説に対応した複数の尤度値が順次入力され、当該加算手段によって、複数の尤度値を順次加算することで、入力された尤度値の数に対応する複数の累積尤度値を算出する。また、シフトレジスタに加算手段から累積尤度値が順次入力され、当該シフトレジスタによって、複数の比較手段に対して、複数の累積尤度値を同時に出力する。
【００１７】
このように、再標本化装置は、加算手段とシフトレジスタによって、入力された尤度値列を累積尤度値列に変換し、当該累積尤度値列を構成する複数の累積尤度列を複数の比較手段に対して同時に出力することができる。
【発明の効果】
【００１８】
請求項１および請求項２に係る発明によれば、論理回路や順序回路を用いてハードウェア処理を行うことで、仮説（粒子）をメモリに記憶する必要がなく、かつ、複数の仮説（粒子）を一度に再標本化することができるため、メモリのランダムアクセスを避けつつ、並列的なスイッチング操作によって高速な再標本化を実現することができる。また、請求項１および請求項２に係る発明によれば、状態空間が高次である場合であっても、並列的に処理を行うことができるため、粒子数が少ない場合において、次元数に関わらず高速に再標本化を行うことができる。
【図面の簡単な説明】
【００１９】
【図１】本発明に係る再標本化装置の構成例を示すブロック図である。
【図２】本発明に係る再標本化装置が備えるシフトレジスタの構成例を示すブロック図である。
【図３】本発明に係る再標本化装置が備える加算手段の構成例を示すブロック図である。
【図４】本発明に係る再標本化装置の入出力のタイミングを示すタイミングチャートである。
【図５】本発明に係る再標本化装置が備える一様乱数発生手段の構成例を示すブロック図である。
【図６】本発明に係る再標本化装置が備える一様乱数発生手段の入力のタイミングを示すタイミングチャートである。
【発明を実施するための形態】
【００２０】
本発明の実施形態に係る再標本化装置について、図面を参照しながら説明する。なお、以下の説明において、同一の構成については同一の名称及び符号を付し、詳細説明を省略する。
【００２１】
再標本化装置１は、逐次モンテカルロ法によるモデルのパラメータを推定する際に用いられる複数の仮説を、それらの仮説に対応した尤度値に従って再標本化するものである。ここで、仮説とは、前記したモデルのパラメータの解の候補のことを意味している。また、尤度値とは、それぞれの仮説の尤もらしさを示す値のことを意味している。
【００２２】
再標本化装置１は、例えば映像中における人間の顔の姿勢（位置、向き）をトラッキング（追跡）する場合において、当該映像中における人間の顔の位置（２次元）、大きさ（１次元）、向き（３次元）からなる顔姿勢パラメータ等を推定するためのパラメータ推定装置の内部に組み込まれて用いられる。このパラメータ推定装置は、まず前記した顔姿勢パラメータの複数の仮説を作成し、各仮説について、現在のフレームの画像に対して当該仮説がどの程度尤もらしいかの評価（尤度評価）を行う。そして、パラメータ推定装置は、各仮説の尤度を用いて最終的な姿勢パラメータ推定を行う。再標本化装置１は、このようなパラメータ推定装置において、前記した尤度に従って仮説の再標本化を行い、寄与の少ない仮説を省く処理を行う。
【００２３】
再標本化装置１は、ここでは図１に示すように、シフトレジスタ１０と、加算手段１２と、一様乱数発生手段１３と、比較手段１４と、プライオリティエンコーダ１５と、計数手段１６と、マトリックス制御手段１７と、マトリックススイッチ１８と、を備えている。そして、再標本化装置１は、図１に示すように、図示しない外部の仮説（粒子）生成手段からマトリックススイッチ１８に入力される複数の仮説（粒子）１〜Ｈを、図示しない外部の尤度評価手段から加算手段１２に入力される複数の尤度値と、一様乱数発生手段１３によって生成される一様乱数と、に基づいて複数の仮説（粒子）１〜Ｋに再標本化する。なお、再標本化装置１が備えるシフトレジスタ１０および加算手段１２は、後記するように、外部から入力される尤度値から累積尤度値を算出するための累積尤度値算出手段として機能する。また、前記した「Ｈ」および「Ｋ」は、２以上の整数を意味しており、同数であっても同数でなくてもどちらでも構わない。
【００２４】
シフトレジスタ１０は、予め定められたクロックに同期して、データを内部でシフトさせながら保持するものである。シフトレジスタ１０は、具体的には図１に示すように、加算手段１２から順次入力される複数の累積尤度値のそれぞれを保持し、後記する複数の比較手段１４に対して、それぞれの累積尤度値を同時に出力する。シフトレジスタ１０は、図１に示すように、複数の遅延手段１１−１，１１−２，１１−３，・・・，１１−Ｈから構成される。すなわち、シフトレジスタ１０は、図１に示すように、遅延手段がＨ段分カスケード接続されて構成される。
【００２５】
シフトレジスタ１０には、図１に示すように、クロックφ１のタイミングで、加算手段１２から累積尤度値が順次入力される。この累積尤度値は、図示しない外部の尤度評価手段から順次入力される尤度値が順次加算されたものであり、後に入力されるものほど値が大きくなる。そして、シフトレジスタ１０は、図１に示すように、順次入力される累積尤度値を遅延手段１１−Ｈ、・・・、遅延手段１１−３、遅延手段１１−２、遅延手段１１−１、の順序で上方向に順次シフトさせ、遅延手段１１−１，１１−２，１１−３，・・・，１１−Ｈのそれぞれに累積尤度値を保持させる。なお、以下の説明では、複数の遅延手段１１−１，１１−２，１１−３，・・・，１１−Ｈを包括して、「遅延手段１１−ｈ（ｈは１以上Ｈ以下の整数）」と表記する場合がある。
【００２６】
遅延手段１１−ｈは、入力された数値をクロック入力のタイミングで保持するとともに、当該数値をリセット入力のタイミングで破棄するものである。なお、遅延手段１１−ｈが保持または破棄する数値は、整数、固定小数点、または浮動小数点のいずれであっても構わない。遅延手段１１−ｈは、具体的には図１に示すように、後記する加算手段１２から入力される累積尤度値を、図示しない外部のクロック発生手段から入力されるクロックφ１のタイミングで保持するとともに、図示しない外部のリセット発生手段から入力されるリセット入力Ｒのタイミングで破棄して値ゼロを出力する。
【００２７】
ここで、累積尤度値とは、前記したように、図示しない外部の尤度評価手段から入力される複数の尤度値を加算したものである。例えば、再標本化装置１の加算手段１２に対して、尤度値Ｌ１、尤度値Ｌ２、尤度値Ｌ３および尤度値Ｌ４がこの順番で入力される場合、これらの尤度値が入力される度に、後記する加算手段１２によって累積尤度値Ａ１（＝Ｌ１）、累積尤度値Ａ２（＝Ｌ１＋Ｌ２）、累積尤度値Ａ３（＝Ｌ１＋Ｌ２＋Ｌ３）および累積尤度値Ａ４（＝Ｌ１＋Ｌ２＋Ｌ３＋Ｌ４））が順次算出され、遅延手段１１−ｈ（ここではｈ＝４）に順次入力される。このように、累積尤度値は、加算手段によって、図示しない外部の尤度評価手段から入力される尤度値の数と同じ数だけ算出され、遅延手段１１−ｈに順次入力される。
【００２８】
遅延手段１１−ｈは、具体的には図２に示すように、リセット入力付きのＤ（Ｄｅｌａｙ）フリップフロップによって実現することができる。ここで、遅延手段１１−ｈの上下方向の段数は、図１に示すように、再標本化装置１に入力される尤度値（または粒子）の数Ｈに対応している。すなわち、遅延手段１１−ｈは、例えば再標本化装置１に入力される尤度値の個数Ｈが４つである場合、上下方向に少なくとも４段配置される。
【００２９】
また、遅延手段１１−ｈの左右方向の段数は、再標本化装置１に入力される尤度値の個数Ｈと尤度値の範囲（例えば尤度値を２進数で表わした場合のビット数）とに対応している。すなわち、遅延手段１１−ｈは、例えば２進数の数値が入力される場合において、再標本化装置１に入力される尤度値の個数Ｈが４つであり、それぞれの尤度値の範囲が０以上２５５以下（つまり２進数で８ビット以下）である場合、左右方向に少なくとも１０段配置される。これは、例えば再標本化装置１の加算手段１２に対して、４回とも尤度値「２５５」が入力され、当該加算手段１２から遅延手段１１−ｈに対して、累積尤度値「１０２０（つまり２進数で１０ビット）」が入力された場合であっても、桁があふれないようにするためである。
【００３０】
遅延手段１１−ｈには、図１に示すように、後記する加算手段１２から、クロックφ１に同期して累積尤度値Ａ１，Ａ２，Ａ３，・・・，ＡＨが順次入力される。そして、遅延手段１１−ｈは、当該クロックφ１の立ち上がりエッジのタイミングで、最下段の遅延手段１１−Ｈから最上段の遅延手段１１−１に向かって、累積尤度値Ａ１，Ａ２，Ａ３，・・・，ＡＨを一段ずつ順次シフトさせて保持させる。そして、遅延手段１１−ｈは、比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）に対して、累積尤度値Ａ１，Ａ２，Ａ３，・・・を同時に出力し、一様乱数発生手段１３に対して、最大の累積尤度値ＡＨを出力する。なお、以下の説明では、複数の累積尤度値Ａ１，Ａ２，Ａ３，・・・，ＡＨを包括して、「累積尤度値Ａｈ（ｈは１以上Ｈ以下の整数）」と表記する場合がある。
【００３１】
加算手段１２は、入力された数値を加算するものである。なお、加算手段１２が加算する２つの数値は、整数、固定小数点、または浮動小数点のいずれであっても構わない。加算手段１２には、図１に示すように、図示しない外部の尤度評価手段から、クロックφ１に同期して尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨが順次入力されるとともに、シフトレジスタ１０の最下段に配置された遅延手段１１−Ｈから、クロックφ１に同期して累積尤度値が順次入力される。ここで、尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨは、後記するマトリックススイッチ１８に入力される、再標本化をしようとする複数の仮説（粒子）１〜Ｈに対応したものである。
【００３２】
そして、加算手段１２は、両者を加算することでさらに累積尤度値を算出し、これを遅延手段１１−Ｈに出力する。すなわち、加算手段１２は、尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨが入力される度に、当該尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨが入力された時点における累積尤度値を算出し、当該累積尤度値を遅延手段１１−Ｈに出力する。なお、以下の説明では、複数の尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨを包括して、「尤度値Ｌｈ（ｈは１以上Ｈ以下の整数）」と表記する場合がある。
【００３３】
加算手段１２は、入力された２つの数値が整数または固定小数点による２進数で表現されている場合には、例えば半加算器１個以上および全加算器０個以上によって実現することができる。但し、加算手段１２の具体的構成は、図示しない外部の尤度評価手段から入力される尤度値Ｌｈの値の範囲によって異なる。例えば、加算手段１２に入力される一方の値、すなわち図示しない外部の尤度評価手段から入力される尤度値Ｌｈの範囲が０以上Ｍ以下の整数値である場合、加算手段１２に入力される他方の値、すなわち遅延手段１１−Ｈから入力される累積尤度値は、０以上Ｍ×（Ｈ−１）以下の整数値となる。従って、この場合、以下の式（１）によって加算手段１２を構成する最小限の半加算器の数を算出することができるとともに、以下の式（２）によって加算手段１２を構成する最小限の全加算器の数を算出することができる。
【００３４】
【数１】
【００３５】
【数２】
【００３６】
加算手段１２は、例えば図示しない外部の尤度評価手段から入力される尤度値Ｌｈの範囲が０以上２５５以下であり、シフトレジスタ１０の段数Ｈ、すなわち再標本化装置１に入力される尤度値の個数Ｈが８個である場合、図３に示すように、少なくとも半加算器５個と全加算器７個とで構成することができる。ここで、図３において、Ａ，Ｂ，ＳおよびＣの端子を有するブロックは、半加算器を表わしており、Ａ，Ｂ，Ｘ，ＳおよびＣの端子を有するブロックは、全加算器を示している。そして、図３における半加算器および全加算器の端子の記号は、ＡおよびＢが被加算器入力、Ｘがキャリー入力、Ｓが加算結果出力、Ｃがキャリー出力を表わしている。
【００３７】
再標本化装置１では、シフトレジスタ１０および加算手段１２、すなわち累積尤度値算出手段を前記したように構成することで、最上段の遅延手段１１−１から最下段の遅延手段１１−Ｈに向かって、それぞれ累積尤度値Ａｈが現れる。すなわち、再標本化装置１では、外部の図示しない尤度評価手段から加算手段１２に対して尤度列（尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨ）が入力されると、遅延手段１１−ｈから累積尤度列（累積尤度値Ａ１，Ａ２，Ａ３，・・・，ＡＨ）が出力される。
【００３８】
以下、遅延手段１１−ｈおよび加算手段１２の動作について、図４を参照しながら簡単に説明する。なお、以下では、再標本化装置１に入力される尤度値Ｌｈの個数Ｈを４個（つまり遅延手段１１−ｈの段数Ｈを４段）とした場合について説明する。また、図４のタイミングチャートにおいて途切れている箇所は、途中の動作を省略していることを示している。
【００３９】
まず、加算手段１２は、１回目のクロックφ１の立ち上がりエッジのタイミングで外部から尤度値Ｌ１が入力されると、これを累積尤度値Ａ１として遅延手段１１−ｈの最下段（説明の便宜上、「遅延手段１１−４」とする）に出力する。すると、遅延手段１１−４は、加算手段１２から入力された累積尤度値Ａ１（＝尤度値Ｌ１）を保持する。
【００４０】
次に、加算手段１２は、２回目のクロックφ１の立ち上がりエッジのタイミングで外部から尤度値Ｌ２が入力されるとともに、遅延手段１１−４から累積尤度値Ａ１（＝尤度値Ｌ１）が入力されると、両者を加算して累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を算出し、これを遅延手段１１−４に出力する。すると、遅延手段１１−４は、前記した累積尤度値Ａ１（＝尤度値Ｌ１）を上段の遅延手段１１−３へとシフトさせ、加算手段１２から入力された累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を保持する。
【００４１】
次に、加算手段１２は、３回目のクロックφ１の立ち上がりエッジのタイミングで外部から尤度値Ｌ３が入力されるとともに、遅延手段１１−４から累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）が入力されると、両者を加算して累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）を算出し、これを遅延手段１１−４に出力する。すると、遅延手段１１−４は、前記した累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を上段の遅延手段１１−３へとシフトさせ、加算手段１２から入力された累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）を保持する。また、遅延手段１１−３は、前記した累積尤度値Ａ１（＝尤度値Ｌ１）を上段の遅延手段１１−２へとシフトさせ、遅延手段１１−４から入力された累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を保持する。
【００４２】
次に、加算手段１２は、４回目のクロックφ１の立ち上がりエッジのタイミングで外部から尤度値Ｌ４が入力されるとともに、遅延手段１１−４から累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）が入力されると、両者を加算して累積尤度値Ａ４（＝尤度値Ｌ１＋Ｌ２＋Ｌ３＋Ｌ４）を算出し、これを遅延手段１１−４に出力する。すると、遅延手段１１−４は、前記した累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）を上段の遅延手段１１−３へとシフトさせ、加算手段１２から入力された累積尤度値Ａ４（＝尤度値Ｌ１＋Ｌ２＋Ｌ３＋Ｌ４）を保持する。また、遅延手段１１−３は、前記した累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を上段の遅延手段１１−２へとシフトさせ、遅延手段１１−４から入力された累積尤度値Ａ３（＝尤度値Ｌ１＋Ｌ２＋Ｌ３）を保持する。また、遅延手段１１−２は、前記した累積尤度値Ａ１（＝尤度値Ｌ１）を上段の遅延手段１１−１へとシフトさせ、遅延手段１１−３から入力された累積尤度値Ａ２（＝尤度値Ｌ１＋Ｌ２）を保持する。
【００４３】
以上のような動作により、累積尤度算手段は、クロックφ１に同期して、加算手段１２によって尤度値Ｌ１，Ｌ２，Ｌ３，Ｌ４の数に対応する累積尤度値Ａ１，Ａ２，Ａ３，Ａ４を算出し、遅延手段１１−１，１１−２，１１−３，１１−４によって累積尤度値Ａ１，Ａ２，Ａ３，Ａ４をそれぞれ保持する。そして、クロックφ２に同期して、遅延手段１１−４は、一様乱数発生手段１３に対して累積尤度値Ａ４を出力するとともに、遅延手段１１−１，１１−２，１１−３は、複数の比較手段１４に対して累積尤度値Ａ１，Ａ２，Ａ３を出力する。以下、再標本化装置１の残りの構成について説明する。
【００４４】
一様乱数発生手段１３は、一様乱数を発生させるものである。この一様乱数とは、前記したように、指定区間内で一様と見なすことができる乱数のことを意味している。一様乱数発生手段１３は、図１に示すように、一様乱数を所定の時間間隔ごと、すなわちクロックφ２ごとに発生させるとともに、所定の回数、すなわち出力する粒子の数と同じＫ回発生させる。一様乱数発生手段１３には、図１に示すように、シフトレジスタ１０の最下段に配置された遅延手段１１−Ｈから累積尤度値ＡＨが入力される。そして、一様乱数発生手段１３は、当該累積尤度値ＡＨに基づいて、０以上ＡＨ未満の範囲の一様乱数を発生させる。すなわち、一様乱数発生手段１３は、加算手段１２によって算出された最大の累積尤度値ＡＨ未満の一様乱数を生成する。
【００４５】
一様乱数発生手段１３は、例えばＭ系列やＰＮ系列等の擬似乱数発生回路によって発生させた乱数値ｓ（ｓがとり得る値の最小値は０、最大値はＡＨ以上とする）に対して、遅延手段１１−Ｈから入力された累積尤度値ＡＨによる剰余演算を施すことによって実現することができる。従って、一様乱数発生手段１３は、具体的には図５に示すように、擬似乱数発生回路２０と、シフトレジスタ２１と、切替回路２２と、ラッチ回路２３と、減算回路２４と、シフトレジスタ２５と、ラッチ回路２６と、から構成することができる。
【００４６】
擬似乱数発生回路２０は、擬似的な乱数を発生させるものである。擬似乱数発生回路２０は、前記したように、例えばＭ系列やＰＮ系列の乱数発生回路によって構成することができ、ここでは図５に示すように、シフトレジスタ２１に排他的論理和ゲートを３個接続した周期６５５３５のＭ系列発生回路で構成されている。
【００４７】
一様乱数発生手段１３の残りの構成であるシフトレジスタ２１、切替回路２２、ラッチ回路２３、減算回路２４およびシフトレジスタ２５は、前記した累積尤度値ＡＨによる剰余演算を施すための剰余演算回路を構成するものである。これらの構成はそれぞれ一般的なものであるため、詳細な説明は省略する。
【００４８】
以下、一様乱数発生手段１３の動作について、図６を参照（適宜図５も参照）しながら簡単に説明する。また、図６のタイミングチャートにおいて途切れている箇所は、途中の動作を省略していることを示している。
【００４９】
まず、一様乱数発生手段１３は、図６に示すように、クロックφ３によって擬似乱数発生回路２０の擬似乱数の乱数値ｓを更新する。次に、一様乱数発生手段１３は、図６に示すように、制御信号ｃ１をローレベルにすることで、切替回路２２のスイッチ群を擬似乱数発生回路２０側に倒しつつ、シフトレジスタ２５をクリアする。次に、一様乱数発生手段１３は、図６に示すように、クロックφ４に１番目の正のパルスを与え、ラッチ回路２３に擬似乱数発生回路２０が発生させた擬似乱数の乱数値ｓをラッチする。次に、一様乱数発生手段１３は、図６に示すように、制御信号ｃ２をローレベルとした状態で、クロックφ５に１番目の正のパルスを与え、Ｈ番目の累積尤度値出力の値（シフトレジスタ１０の最下段の遅延手段１１−Ｈから出力される累積尤度値ＡＨ）をシフトレジスタ２５にセットし、その後、制御信号ｃ２をハイレベルにする。
【００５０】
次に、一様乱数発生手段１３は、図６に示すように、クロックφ４とクロックφ５について、２番目ないし（ビット幅−１）番目（図５の例では１５番目）まで、交互に正のパルスを与える（但し、クロックφ４をクロックφ５に先行させる）。これにより、擬似乱数の乱数値ｓから引き得る最大の「ＡＨの整数倍」を引いた結果（すなわち、ｓをＡＨで除した際の剰余（Ｒ＝ｓ％ＡＨ））が減算回路２４の出力に現れる。そして、一様乱数発生手段１３は、図６に示すように、最後にクロックφ２に正のパルスを与えることで、０以上ＡＨ未満の整数の一様乱数Ｒ（以下、単に乱数Ｒという）をラッチ回路２６にラッチし、乱数出力を得る。このように、一様乱数発生手段１３はクロックφ２ごとに乱数Ｒを発生させ、図１に示すように、その都度当該乱数Ｒを複数の比較手段１４に対して出力する。
【００５１】
なお、図６のタイミングチャートにおける「ＡＨ−１が乱数Ｒの最大値となる」とは、後記する比較手段１４において、累積尤度値と比較される乱数Ｒの最大値が実質的にＡＨ−１であることを示している。すなわち、一様乱数発生手段１３は、前記したように０以上ＡＨ未満の乱数Ｒを発生させることができるが、図１に示すように、比較手段１４にはシフトレジスタ１０の最下段に配置された遅延手段１１−Ｈから累積尤度値ＡＨが入力されない。そのため、仮に一様乱数発生手段１３によってＡＨ−１超えＡＨ以下の乱数Ｒが生成され、当該乱数Ｒが比較手段１４に入力されると、後記する比較結果Ｄｈの値が必ず０となる。従って、図６のタイミングチャートにおける「ＡＨ−１が乱数Ｒの最大値となる」とは、乱数Ｒの実質的な最大値がＡＨ−１であることを示している。
【００５２】
比較手段１４は、入力された２つの数値の大小を比較するものである。比較手段１４は、図１に示すように、複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）から構成される。すなわち、比較手段１４は、図１に示すように、比較手段が、シフトレジスタ１０を構成する遅延手段の段数Ｈよりも１個少ないがＨ−１段分カスケード接続されて構成される。
【００５３】
複数の比較手段１４には、図１に示すように、遅延手段１１−Ｈを除く遅延手段１１−ｈから、累積尤度値Ａｈがそれぞれ同時に入力されるとともに、一様乱数発生手段１３から乱数Ｒがそれぞれ同時に入力される。そして、比較手段１４は、前記した一様乱数発生手段１３によって一様乱数Ｒが生成されて入力される度に、以下の式（３）に示すように、累積尤度値Ａｈと乱数Ｒとの大小を比較し、その比較結果Ｄｈをプライオリティエンコーダ１５に出力する。すなわち、比較手段１４は、以下の式（３）に示すように、累積尤度値Ａｈが乱数Ｒより大きい場合は「比較結果Ｄｈ＝０」を出力し、累積尤度値Ａｈが乱数Ｒ以下である場合は「比較結果Ｄｈ＝１」を出力する。
【００５４】
【数３】
【００５５】
ここで、「比較結果Ｄｈを出力する」とは、例えば再標本化装置１の加算手段１２にＨ個の尤度値Ｌ１，Ｌ２，Ｌ３，・・・，ＬＨが入力された場合に、比較手段１４が、入力された尤度値Ｌｈよりも１個少ないＨ−１個の比較結果Ｄ１，Ｄ２，Ｄ３，・・・，ＤＨ−１をプライオリティエンコーダ１５に対して出力することを示している。なお、前記した式（３）において、Ｄｈの値「０」はローレベルと読み替え、Ｄｈの値「１」はハイレベルと読み替えても構わない。
【００５６】
例えば、再標本化装置１の加算手段１２に入力される尤度値Ｌｈの個数Ｈが４つ（つまり遅延手段１１−ｈの段数Ｈが４段）である場合、比較手段１４−１には、遅延手段１１−１から累積尤度値Ａ１が入力され、比較手段１４−２には、遅延手段１１−２から累積尤度値Ａ２が入力される。そして、比較手段１４の最下段（説明の便宜上、「比較手段１４−３」とする）には、最下段の遅延手段１１−３から累積尤度値Ａ３が入力される。また同時に、比較手段１４−１，１４−２，１４−３には、クロックφ２に同期して乱数Ｒがそれぞれ入力される。
【００５７】
そして、比較手段１４−１は、累積尤度値Ａ１と乱数Ｒとの比較結果Ｄ１をプライオリティエンコーダ１５に出力し、比較手段１４−２は、累積尤度値Ａ２と乱数Ｒとの比較結果Ｄ２をプライオリティエンコーダ１５に出力し、比較手段１４−３は、累積尤度値Ａ３と乱数Ｒとの比較結果Ｄ３をプライオリティエンコーダ１５に出力する。このように、再標本化装置１の加算手段１２に４つの尤度値Ｌ１，Ｌ２，Ｌ３，Ｌ４が入力されると、プライオリティエンコーダ１５には、３つの比較結果Ｄ１，Ｄ２，Ｄ３が同時に入力されることになる。
【００５８】
比較手段１４は、例えば累積尤度値Ａｈと乱数Ｒとの差分を演算する減算回路として実装し、Ｒ−Ａｈを演算した結果として現れる最上位ビットのボローフラグを比較結果Ｄｈとすることができる。
【００５９】
プライオリティエンコーダ１５は、優先順位の最も高い入力に対応するコードを出力するものである。プライオリティエンコーダ１５には、具体的には図１に示すように、複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）のそれぞれから比較結果Ｄｈが入力される。この比較結果Ｄｈは、前記した式（３）に示すように、０または１の数値（フラグ）から構成されるものである。そして、プライオリティエンコーダ１５は、複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）から入力される複数の比較結果Ｄｈのうち、Ｄｈ＝１（乱数Ｒ以下であると判定された比較結果）となるものを選出し、値が１である比較結果Ｄｈのうちの最大の「ｈ」を選択する。なお、全てのｈについてＤｈ＝０の場合には、最大の「ｈ」は０であったものとみなす。
【００６０】
ここで、前記した「複数の比較結果Ｄｈのうち、Ｄｈ＝１（乱数Ｒ以下であると判定された比較結果）となるものを選出し、値が１である比較結果Ｄｈのうちの最大の「ｈ」を選択する」とは、言い換えれば、複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）によって乱数Ｒ以下であると判定された累積尤度値Ａｈとなるものを選出し、これらの累積尤度値Ａｈの中から、最大の累積尤度値Ａｈを選択するとともに、当該累積尤度値Ａｈのインデックス（下付き数字）である「ｈ」を選択するという処理のことを意味している。
【００６１】
そして、プライオリティエンコーダ１５は、選択したｈに１を加えた（ｈ＋１）を標本点Ｐとしてマトリックス制御手段１７に出力する。ここで、標本点Ｐとは、言い換えれば、前記した最大の累積尤度値Ａｈが算出される際に加算手段１２（累積尤度値算出手段）に入力された尤度値Ｌｈに対応する仮説を示すコードのことを意味している。なお、プライオリティエンコーダ１５は、前記した複数の比較手段１４−１，１４−２，・・・，１４−（Ｈ−１）から比較結果Ｄｈが入力される度に、コード（標本点Ｐ）を生成し、これをマトリックス制御手段１７に出力する。
【００６２】
例えば、再標本化装置１に入力される尤度値Ｌｈの個数Ｈが４つ（つまり遅延手段１１−ｈの段数Ｈが４段）である場合、プライオリティエンコーダ１５には、比較手段１４−１から比較結果Ｄ１が、比較手段１４−１から比較結果Ｄ２が、比較手段１４の最下段（説明の便宜上、「比較手段１４−３」とする）から比較結果Ｄ３が入力される。そして、例えばこれらの比較結果Ｄ１，Ｄ２，Ｄ３の値がそれぞれ「Ｄ１＝１，Ｄ２＝１，Ｄ３＝０」である場合、プライオリティエンコーダ１５は、値が１である比較結果Ｄ１，Ｄ２のうちの最大の「ｈ」（インデックス、下付き数字）である「２」を選出し、当該「２」に１を加えた「３」のコード（標本点Ｐ）をマトリックス制御手段１７に出力する。
【００６３】
ここで、プライオリティエンコーダ１５が生成する標本点Ｐは、再標本化の対象となる仮説を示している。従って、前記した例において、プライオリティエンコーダ１５によって値が１である比較結果Ｄ１，Ｄ２のうちの最大の「ｈ」に１を加えた「３」を選出するという処理は、比較手段１４−３によって乱数Ｒ以下であると判定された累積尤度値Ａ１，Ａ２の中で最も大きい累積尤度値Ａ２を選択した後に、当該累積尤度値Ａ２よりも一段階大きい累積尤度値Ａ３を選択し、当該累積尤度値Ａ３が算出される際に加算手段１２に入力された尤度値Ｌ３に対応する仮説を選出するという処理に相当することになる。
【００６４】
以上の処理により、比較手段１４の比較結果Ｄｈのうち、１（ハイレベル）のビットが立つ「ｈ」である標本点Ｐは、近似的に一様な乱数Ｒを累積尤度関数の逆関数に代入した結果に近似することになる。すなわち、標本点Ｐは、累積尤度関数に近似的に比例する確率で生起することになる。
【００６５】
計数手段１６は、クロックφ２のタイミングで１〜Ｋまで計数するカウンタである。このＫは、図１に示すように、再標本化後の粒子の数（自然数）であり、予め任意の数で設定される。計数手段１６は、例えばバイナリカウンタを用いることができ、図１に示すように、クロックφ２に同期して、そのカウント値ｋをマトリックス制御手段１７に出力する。
【００６６】
マトリックス制御手段１７は、プライオリティエンコーダ１５から入力される標本点Ｐ（コード）と、計数手段１６から入力されるカウント値ｋと、に基づいてマトリックススイッチ１８の接点の継断を制御するものである。マトリックス制御手段１７は、具体的には図１に示すように、プライオリティエンコーダ１５から標本点Ｐが、計数手段１６からカウント値ｋが、それぞれ入力されると、Ｐ番目の入力（図１では行）とｋ番目の出力（図１では列）との接点を閉じ、Ｐ番目以外の入力（図１では行）とｋ番目の出力（図１では列）との接点を開放するような接点制御信号を生成し、これをマトリックススイッチ１８に出力する。これにより、マトリックス制御手段１７は、図１に示すように、１番目〜Ｋ番目の各粒子（仮説）の出力を、１番目〜Ｈ番目の粒子の入力の中の１つの入力に接続することができ、その結果として、マトリックススイッチ１８に入力されたＨ個の粒子を再標本化後のＫ個の粒子に写像して出力することができる。
【００６７】
マトリックススイッチ１８は、スイッチング操作によって、外部から入力される複数の仮説（粒子）を複数の仮説（粒子）に再標本化するものである。マトリックススイッチ１８は、図１に示すように、碁盤状に接点が配置されており、マトリックス制御手段１７から入力される接点制御信号に従って、これらの接点を閉鎖または開放するように構成されている。また、マトリックススイッチ１８が備える接点は、図１に示すように、外部から入力される再標本化前の複数の仮説（粒子）１〜Ｈと、外部に出力する再標本化後の複数の仮説（粒子）１〜Ｋと、に対応している。このマトリックススイッチ１８は、例えばＣＭＯＳ（Complementary Metal Oxide Semiconductor）によるスイッチで実現することができる。
【００６８】
マトリックススイッチ１８には、図１に示すように、図示しない外部の仮説（粒子）生成手段から、再標本化前の複数の仮説（粒子）１〜Ｈが入力され、マトリックス制御手段１７から、接点制御信号が入力される。この接点制御信号には、プライオリティエンコーダ１５によって生成された標本点Ｐ（コード）と、計数手段１６によって計数されたカウント値ｋに関する情報が含まれている。そして、マトリックススイッチ１８は、当該接点制御信号に基づいて図１に示す接点を制御することで、再標本化後の複数の仮説（粒子）１〜Ｋを出力する。このような処理によって、マトリックススイッチ１８における粒子入力と粒子出力の関係が、再標本化前の粒子と再標本化後の粒子の関係となる。すなわち、マトリックススイッチ１８に複数の粒子の状態量（複数の仮説１〜Ｈ）を入力すると、即座に再標本化が実行され、再標本化後の複数の粒子の状態量（複数の仮説１〜Ｋ）が出力されることになる。
【００６９】
以上のような構成を備える再標本化装置１は、累積尤度値算出手段（加算手段１２およびシフトレジスタ１０）、一様乱数発生手段１３、複数の比較手段１４およびプライオリティエンコーダ１５における一連の処理によって、再標本化の対象となる複数の仮説を決定する。そして、マトリックススイッチ１８に複数の仮説が入力されると、当該マトリックススイッチ１８から、前記した一連の処理によって決定された再標本化後の複数の仮説が一度に出力されることになる。従って、再標本化装置１によれば、複数の仮説（粒子）をメモリに記憶する必要がないため、メモリのランダムアクセスが発生することがない。また、再標本化装置１によれば、マトリックススイッチ１８に標本化前の複数の仮説を入力すると、再標本化後の複数の仮説が一度に出力されるという並列的なスイッチング操作を実現することができる。
【００７０】
従って、再標本化装置１によれば、論理回路や順序回路を用いてハードウェア処理を行うことで、仮説（粒子）をメモリに記憶する必要がなく、かつ、複数の仮説（粒子）を一度に再標本化することができるため、メモリのランダムアクセスを避けつつ、並列的なスイッチング操作によって高速な再標本化を実現することができる。また、再標本化装置１によれば、状態空間が高次である場合であっても、並列的に処理を行うことができるため、粒子数が少ない場合において、次元数に関わらず高速に再標本化を行うことができる。
【００７１】
以上、本発明に係る再標本化装置について、発明を実施するための形態により具体的に説明したが、本発明の趣旨はこれらの記載に限定されるものではなく、特許請求の範囲の記載に基づいて広く解釈されなければならない。また、これらの記載に基づいて種々変更、改変等したものも本発明の趣旨に含まれることはいうまでもない。
【符号の説明】
【００７２】
１ 再標本化装置
１０ シフトレジスタ
１１−１，１１−２，１１−３，１１−Ｈ，１１−ｈ 遅延手段
１２ 加算手段
１３ 一様乱数発生手段
１４，１４−１，１４−２，１４−（Ｈ−１） 比較手段
１５ プライオリティエンコーダ
１６ 計数手段
１７ マトリックス制御手段
１８ マトリックススイッチ
２０ 擬似乱数発生回路
２１ シフトレジスタ
２２ 切替回路
２３ ラッチ回路
２４ 減算回路
２５ シフトレジスタ
２６ ラッチ回路
【特許請求の範囲】
【請求項１】
逐次モンテカルロ法によりモデルのパラメータを推定する際に用いられる当該パラメータの解の候補である複数の仮説を、当該仮説の尤もらしさを示す尤度値に従って再標本化する再標本化装置であって、
前記複数の仮説に対応した前記尤度値が順次入力され、当該尤度値が入力された時点における累積尤度値を、当該尤度値が入力される度に算出する累積尤度値算出手段と、
前記累積値尤度値算出手段によって算出された最大の累積尤度値未満の一様乱数を、所定の時間間隔で所定の回数だけ生成する一様乱数発生手段と、
前記累積尤度値算出手段によって算出された複数の前記累積尤度値のそれぞれと、前記一様乱数発生手段によって生成された前記一様乱数とを、当該一様乱数が生成される度に比較する複数の比較手段と、
前記複数の比較手段によって前記一様乱数以下であると判定された前記累積尤度値の中から最大の累積尤度値を選択し、当該最大の累積尤度値が算出される際に前記累積尤度値算出手段に入力された前記尤度値に対応する仮説を示すコードを、前記複数の比較手段から比較結果が入力される度に生成するプライオリティエンコーダと、
前記複数の仮説が入力されるとともに、当該複数の仮説に対応した複数の接点を備え、前記プライオリティエンコーダによって生成された複数の前記コードが示す複数の仮説に対応する前記接点を制御することで、再標本化された複数の仮説を出力するマトリックススイッチと、
を備えることを特徴とする再標本化装置。
【請求項２】
前記累積尤度算出手段は、
前記複数の仮説に対応した前記複数の尤度値が順次入力され、当該複数の尤度値を順次加算することで、入力された前記尤度値の数に対応する複数の前記累積尤度値を算出する加算手段と、
前記加算手段から前記累積尤度値が順次入力され、前記複数の比較手段に対して、複数の前記累積尤度値を同時に出力するシフトレジスタと、
を備えることを特徴とする請求項１に記載の再標本化装置。
【請求項１】
逐次モンテカルロ法によりモデルのパラメータを推定する際に用いられる当該パラメータの解の候補である複数の仮説を、当該仮説の尤もらしさを示す尤度値に従って再標本化する再標本化装置であって、
前記複数の仮説に対応した前記尤度値が順次入力され、当該尤度値が入力された時点における累積尤度値を、当該尤度値が入力される度に算出する累積尤度値算出手段と、
前記累積値尤度値算出手段によって算出された最大の累積尤度値未満の一様乱数を、所定の時間間隔で所定の回数だけ生成する一様乱数発生手段と、
前記累積尤度値算出手段によって算出された複数の前記累積尤度値のそれぞれと、前記一様乱数発生手段によって生成された前記一様乱数とを、当該一様乱数が生成される度に比較する複数の比較手段と、
前記複数の比較手段によって前記一様乱数以下であると判定された前記累積尤度値の中から最大の累積尤度値を選択し、当該最大の累積尤度値が算出される際に前記累積尤度値算出手段に入力された前記尤度値に対応する仮説を示すコードを、前記複数の比較手段から比較結果が入力される度に生成するプライオリティエンコーダと、
前記複数の仮説が入力されるとともに、当該複数の仮説に対応した複数の接点を備え、前記プライオリティエンコーダによって生成された複数の前記コードが示す複数の仮説に対応する前記接点を制御することで、再標本化された複数の仮説を出力するマトリックススイッチと、
を備えることを特徴とする再標本化装置。
【請求項２】
前記累積尤度算出手段は、
前記複数の仮説に対応した前記複数の尤度値が順次入力され、当該複数の尤度値を順次加算することで、入力された前記尤度値の数に対応する複数の前記累積尤度値を算出する加算手段と、
前記加算手段から前記累積尤度値が順次入力され、前記複数の比較手段に対して、複数の前記累積尤度値を同時に出力するシフトレジスタと、
を備えることを特徴とする請求項１に記載の再標本化装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１３−９２８９５（Ｐ２０１３−９２８９５Ａ）
【公開日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願番号】特願２０１１−２３４３１４（Ｐ２０１１−２３４３１４）
【出願日】平成２３年１０月２５日（２０１１．１０．２５）
【出願人】（０００００４３５２）日本放送協会 (2,206)
【公開日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願日】平成２３年１０月２５日（２０１１．１０．２５）
【出願人】（０００００４３５２）日本放送協会 (2,206)
[ Back to top ]