信号処理装置及び方法、並びにプログラム
【課題】 ＤＰマッチングにおける経路構築を効率よく高速に行うことが可能な信号処理装置及びその方法、並びにプログラムを提供する。
【解決手段】 評価値計算部１０は、各対応点における評価値を計算し、経路選択部１１は、各対応点における経路を選択する。選択された経路は、経路列生成部１２に順次格納され、経路列毎に纏められる。経路列生成部１２は、経路列を経路列記憶部１４に格納し、経路構築部１６は、格納された経路列に基づいて、２系列の要素の対応関係を表す経路を探索する。ここで、経路列記憶部１４では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、経路構築部１６は、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定する。
【解決手段】 評価値計算部１０は、各対応点における評価値を計算し、経路選択部１１は、各対応点における経路を選択する。選択された経路は、経路列生成部１２に順次格納され、経路列毎に纏められる。経路列生成部１２は、経路列を経路列記憶部１４に格納し、経路構築部１６は、格納された経路列に基づいて、２系列の要素の対応関係を表す経路を探索する。ここで、経路列記憶部１４では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、経路構築部１６は、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＤＰ（Dynamic Programming）マッチング（動的計画法）を用いた演算を行う信号処理装置及びその方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来より、２枚の画像からの仮想視点画像や距離画像の作成、或いは音声認識等の分野において、ＤＰ（Dynamic Programming）マッチング（動的計画法）が広く用いられており、ソフトウェアでは実装されているものもある（特許文献１等を参照）。
【０００３】
一例として、第１の画像と第２の画像との画素パターンを対応付ける場合について、図１４を参照しながら説明する。
【０００４】
先ず、第１の画像のあるスキャンライン（水平ライン）上の各要素を水平軸、第２の画像の対応するスキャンライン上の各要素を垂直軸として並べ、要素同士の全ての対応点における評価値を求める。ここで用いるスキャンラインは、エピポーラ拘束等を用いて予め算出しておいたものである。例えば要素ｎ１と要素ｎ２との対応点（図中四角で示す）における評価値を求める場合、それらの要素の画素値に加えて、要素ｎ１と要素(ｎ−１)２との対応点、要素(ｎ−１)１と要素ｎ２との対応点、及び要素(ｎ−１)１と要素(ｎ−１)２との対応点（何れも、図中丸で示す）における評価値のそれぞれを用いて３種類の評価値を計算し、これらの３種類の評価値のうちの最小値を当該対応点における評価値として記憶する。この際、その最小の評価値をもたらした経路（左，下，左下の何れか）を併せて記憶する。この計算を左下隅の対応点から始めて右上隅の対応点へと至るまでの全ての対応点について行い、且つ、全ての経路を記憶する。
【０００５】
なお、評価値の計算方法は解決しようとする問題によって種々存在するが、例えばステレオ法を用いて距離画像を作成する場合の評価値の計算方法は、非特許文献１等に記載されている。
【０００６】
その後、右上隅の対応点から始めて、記憶された経路を逆に辿って左下隅の対応点へと至る経路を構築すると、その経路上に存在する対応点がスキャンライン上の要素同士の対応関係を表すことになる。
【０００７】
このように、ＤＰマッチングでは、各要素の組合せという小さい単位の計算を繰り返して解くことによって、それと同じタイプの大きな単位の問題を解決する。
【０００８】
【特許文献１】特開平２−５３１８７号公報
【非特許文献１】J. Cox, et al.,“A Maximum Likelihood Stereo Algorithm”, COMPUTER VISION AND IMAGE UNDERSTANDING, Vol.63, No.3, May, pp.542-567, 1996
【特許文献２】特開昭５０−２３５３３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ところで、図１４から分かるように、ある対応点における評価値を計算するためには、当該対応点の左，下，左下の対応点における評価値が事前に計算されている必要があり、また、その計算を行う時点までそれらの評価値を記憶しておかなければならない。このため、単純に逐次処理を行うと、要素数がＮ倍になればその計算量及び計算に要する時間はＮ２倍となり、また、その計算を行う時点まで記憶しておかなければならない評価値の数も飛躍的に増大していく。したがって、実時間処理を行うためにハードウェア化を試みたとしても、リソース量やメモリ量、或いは動作速度の観点からその実現は困難であった。
【００１０】
そこで、従来、左下隅の対応点と右上隅の対応点とを結ぶ対角線の軌跡に沿って複数の対応点における評価値を並列に計算するようにハードウェアを構成することにより、評価値の計算に要する時間を削減する技術が提案されている（特許文献２を参照）。この特許文献２記載の技術によれば、ＤＰマッチングにおける評価値の計算を高速に行うことができると共に、並列計算した各対応点において最小の評価値を与える経路を記憶することができる。
【００１１】
しかしながら、特許文献２記載の技術を含む従来の技術では、各対応点における経路を単純に記憶するのみであったため、右上隅の対応点から始めて、記憶された経路を逆に辿って左下隅の対応点へと至る経路を構築する際に、各対応点における経路を効率的に読み出すことができず、経路構築に比較的長い時間を要してしまうという問題があった。
【００１２】
本発明は、このような従来の実情に鑑みて提案されたものであり、ＤＰマッチングにおける経路構築を効率よく高速に行うことが可能な信号処理装置及びその方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上述した目的を達成するために、本発明に係る信号処理装置は、第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める信号処理装置であって、上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算手段と、上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択手段と、上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列が格納される経路列記憶手段と、上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築手段とを備え、上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、上記経路構築手段は、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定することを特徴とする。
【００１４】
また、上述した目的を達成するために、本発明に係る信号処理方法は、第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める信号処理方法であって、上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算工程と、上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択工程と、上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列を経路列記憶手段に格納する経路列記憶工程と、上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築工程とを有し、上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、上記経路構築工程では、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定することを特徴とする。
【００１５】
また、本発明に係るプログラムは、上述した信号処理をコンピュータに実行させるものである。
【発明の効果】
【００１６】
本発明に係る信号処理装置及びその方法、並びにプログラムによれば、ＤＰマッチングにおける経路構築を効率よく高速に行うことが可能とされる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００１８】
先ず、本実施の形態における信号処理装置の概略構成を図１に示す。図１に示すように、本実施の形態における信号処理装置１は、入力された各対応点における要素値に基づいて、各対応点について３種類の評価値を計算する評価値計算部１０と、各対応点について３種類の評価値のうち最小の評価値を与える経路（左，下，左下の何れか）を選択する経路選択部１１と、それぞれ１つの経路を格納する記憶子が複数並んだ構造を有し、各対応点について選択された経路を各記憶子に順次格納して後述する経路列を生成する経路列生成部１２と、経路列生成部１２に対して１列分の経路列の格納が終了したか否かを判定する経路列格納終了判定部１３と、経路列生成部１２で生成された経路列が格納される経路列記憶部１４と、全ての対応点について評価値が計算され、経路列が経路列記憶部１４に格納されたか否かを判定する計算終了判定部１５と、経路列記憶部１４に格納された経路列に基づいて、２系列の要素の対応関係を表す経路を構築する経路構築部１６とから構成されている。
【００１９】
ここで、上述した経路列とは、図２の楕円で示すように、左上隅の対応点と右下隅の対応点とを結ぶ対角線に平行な直線（以下、「列」という。）上の対応点における経路を表したものである。なお、評価値計算部１０においては、各列上の対応点の評価値を並列に計算するようにしてもよい。
【００２０】
この信号処理装置１の処理手順について、図３のフローチャートを用いて説明する。先ずステップＳ１において、評価値計算部１０は、各対応点における要素値を入力して３種類の評価値を計算し、ステップＳ２において、経路選択部１１は、各対応点について３種類の評価値のうち最小の評価値を与える経路（左，下，左下の何れか）を選択する。選択された経路は、経路列生成部１２内の各記憶子に順次格納され、経路列毎に並べて纏められる。なお、経路列記憶部１２内の記憶子は、２系列の要素のうち、多い方の要素数分用意すればよい。
【００２１】
次にステップＳ３において、経路列格納終了判定部１３は、経路列生成部１２に対する１列分の経路列の格納が終了したか否かを判定し、終了していなければステップＳ１に戻って計算を繰り返す。一方、１列分の経路列の格納が終了していれば、ステップＳ４に進む。
【００２２】
続いてステップＳ４において、経路列生成部１２は、生成された経路列を経路列記憶部１４に格納する。ここで、経路列は、図４の模式図に示すようにして経路列記憶部１４に格納される。すなわち、経路列は左下隅の対応点と右上隅の対応点とを結ぶ対角線で２つの部分経路列に分割され、右下の部分経路列はそのまま第１の部分経路列記憶部２０に格納され、左上の部分経路列はその並び順を反転して第２の部分経路列記憶部２１に格納される。この際、各部分経路列は、第１，第２の部分経路列記憶部２０，２１内の１つのアドレスに格納される。
【００２３】
続いてステップＳ５において、計算終了判定部１５は、全ての経路列の経路列記憶部１４への格納が終了したか否かを判定し、終了していなければステップＳ１に戻って計算を繰り返し、終了していればステップＳ６に進む。
【００２４】
続いてステップＳ６において、経路構築部１６は、経路列記憶部１４に格納された経路列に基づいて、２系列の要素の対応関係を表す経路を構築する。
【００２５】
ここで、経路列の経路列記憶部１４への格納と、経路列記憶部１４に格納された経路列に基づく経路構築について、さらに詳細に説明する。
【００２６】
上述したように、各部分経路列は、第１，第２の部分経路列記憶部２０，２１内の１つのアドレスに格納されるが、この際、部分経路列上での位置に応じて、例えば図５に示すようにインデクスが付与される。すなわち、左下隅の対応点と右上隅の対応点とを結ぶ対角線上の対応点についてはインデクス０が付与され、対角線よりも右の対応点についてはそれぞれの経路列に沿って対角線に近い対応点からインデクス１，２，３・・・が付与され、対角線よりも左の対応点についてはそれぞれの経路列に沿って対角線に近い対応点からインデクス−１，−２，−３・・・が付与される。そして、右上隅の対応点における経路を含む経路列は第１，第２の部分経路列記憶部２０，２１内のアドレス０に格納され、以下、左下隅の対応点における経路を含む経路列に至るまで、アドレス１，２，３・・・に格納される。なお、各部分経路列は、例えば図６のような配列で第１，第２の部分経路列記憶部２０，２１内の各アドレスに格納される。
【００２７】
上述した経路構築部１６は、アドレス及びインデクスを増減させながら、経路列記憶部１４から経路を読み出し、２系列の要素の対応関係を表す経路を構築する。この経路列記憶部１４からの経路の読み出しは、図７のフローチャートのようにして行われる。先ずステップＳ１０において、現在の対応点における経路を判別し、経路が「左」であれば、ステップＳ１１において現在のアドレスが奇数であるか偶数であるかを判別する。そして、現在のアドレスが奇数であればステップＳ１３においてアドレスを＋１、インデクスを±０してステップＳ１８に進み、偶数であればステップＳ１４においてアドレスを＋１、インデクスを−１してステップＳ１８に進む。また、ステップＳ１０において、経路が「下」であれば、ステップＳ１２において現在のアドレスが奇数であるか偶数であるかを判別する。そして、現在のアドレスが偶数であればステップＳ１５においてアドレスを＋１、インデクスを±０してステップＳ１８に進み、奇数であればステップＳ１６においてアドレスを＋１、インデクスを＋１してステップＳ１８に進む。また、ステップＳ１０において、経路が「左下」であれば、ステップＳ１７においてアドレスを＋２、インデクスを±０してステップＳ１８に進む。
【００２８】
次にステップＳ１８において、増減後のアドレスから経路列を読み出し、ステップＳ１９において、その経路列のうち、増減後のインデクスで示される経路を選択する。そしてステップＳ２０において経路を構築し、ステップＳ１０に戻る。
【００２９】
ここで、例えば図８の太線で示すような経路が構築される場合のアドレス及びインデクスの増減方法について説明する。経路の構築は右上隅の対応点から始められる。この対応点における経路は、第１の部分経路列記憶部２０のアドレス０のインデクス０に格納されている。これが「左下」を示しているので、左下へと進む。この場合、次の経路は、アドレスを＋２、インデクスを±０した場所、つまりアドレス２のインデクス０に格納されている。これが「下」を示しているので下へと進む。この場合、次の経路は、アドレスを＋１、インデクスを±０した場所、つまりアドレス３のインデクス０に格納されている。このような処理を繰り返すことにより、図中太線で示すような経路が構築される。
【００３０】
以上のように、本実施の形態における信号処理装置１によれば、部分経路列上での位置に応じてインデクスを付与することにより、例えば図７のフローチャートのような簡単な論理の処理で経路を構築することができ、また、各経路列を１つのアドレスに格納することにより、１回の読み出し処理で１つの対応点における経路が構築できるため、ＤＰマッチングにおける経路構築を効率よく行うことが可能となる。
【００３１】
したがって、この信号処理装置１を用いることにより、例えばＤＰマッチングを用いた仮想視点画像や距離画像の生成、ビュー・インターポレーション（View Interpolation）等の画像処理や、或いは音声認識処理等が実時間で行えるようなシステムを構築することができる。
【００３２】
例えばステレオ法を用いた距離画像生成にこの信号処理装置１を用いた場合、奇数アドレスのインデクスを＋０．５すれば、このインデクスをそのまま距離情報のインデクスとすることができる。なお、＋０．５を実現するには、インデクスを１ビット拡張し、アドレスの最下位ビットを付加すればよい。
【００３３】
また、同じくステレオ法を用いた距離画像生成にこの信号処理装置１を用いた場合、２台のカメラの光軸が交差しない範囲という拘束条件を設ければ、左下隅の対応点と右上隅の対応点とを結ぶ対角線よりも右の対応点についてのみ部分経路列を求めればよく、第２の部分経路列記憶部２１を省略することができる。
【００３４】
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【００３５】
例えば、上述した実施の形態では、図５に示したように、左下隅の対応点と右上隅の対応点とを結ぶ対角線上の対応点についてはインデクス０を付与し、対角線よりも右の対応点についてはそれぞれの経路列に沿って対角線に近い対応点からインデクス１，２，３・・・を付与し、対角線よりも左の対応点についてはそれぞれの経路列に沿って対角線に近い対応点からインデクス−１，−２，−３・・・を付与するものとして説明したが、本発明はこの例に限定されるものではなく、以下の第１〜第３の変形例に示すように、種々の変更が可能である。
【００３６】
先ず、第１の変形例は、図８に示すように、左下隅の対応点と右上隅の対応点とを結ぶ対角線上の対応点についてはインデクス０を付与し、対角線よりも右の対応点については垂直軸に沿って対角線に近い対応点からインデクス１，２，３・・・を付与し、対角線よりも左の対応点については垂直軸に沿って対角線に近い対応点からインデクス−１，−２，−３・・・を付与するものである。この場合、部分経路列が２列分ずつ第１，第２の部分経路列記憶部２０，２１に格納される。なお、負のインデクスが付与された対応点における経路を格納する際に、インデクス０が付与された対応点における経路を含めるようにしても構わない。
【００３７】
第１の変形例における経路列記憶部１４からの経路の読み出しは、図９のフローチャートのようにして行われる。先ずステップＳ３０において、現在の対応点における経路を判別し、経路が「左」であれば、ステップＳ３１においてアドレスを±０、インデクスを−１してステップＳ３４に進む。また、ステップＳ３０において、経路が「左下」であれば、ステップＳ３２においてアドレスを＋１、インデクスを±０してステップＳ３４に進む。また、ステップＳ３０において、経路が「下」であれば、ステップＳ３３においてアドレスを±０、インデクスを＋１してステップＳ３４に進む。
【００３８】
次にステップＳ３４において、増減後のアドレスから経路列を読み出し、ステップＳ３５において、その経路列のうち、増減後のインデクスで示される経路を選択する。そしてステップＳ３６において経路を構築し、ステップＳ３０に戻る。
【００３９】
なお、この第１の変形例の場合においても、ステレオ法を用いた距離画像生成に用いた場合に、２台のカメラの光軸が交差しない範囲という拘束条件を設ければ、第２の部分経路列記憶部２１を省略することができる。
【００４０】
次に、第２の変形例は、図１０に示すように、右上隅の対応点を含む水平軸上の対応点についてはインデクス０を付与し、以下、左下隅の対応点を含む水平軸に至るまで、インデクス１，２，３・・・を付与するものである。この場合、部分経路列には分割されず、各経路列が経路列記憶部１４の１つのアドレスに記憶される。
【００４１】
第２の変形例における経路列記憶部１４からの経路の読み出しは、図１１のフローチャートのようにして行われる。先ずステップＳ４０において、現在の対応点における経路を判別し、経路が「左」であれば、ステップＳ４１においてアドレスを＋１、インデクスを±０してステップＳ４４に進む。また、ステップＳ４０において、経路が「左下」であれば、ステップＳ４２においてアドレスを＋２、インデクスを＋１してステップＳ４４に進む。また、ステップＳ４０において、経路が「下」であれば、ステップＳ４３においてアドレスを＋１、インデクスを＋１してステップＳ４４に進む。
【００４２】
次にステップＳ４４において、増減後のアドレスから経路列を読み出し、ステップＳ４５において、その経路列のうち、増減後のインデクスで示される経路を選択する。そしてステップＳ４６において経路を構築し、ステップＳ４０に戻る。
【００４３】
続いて第３の変形例は、図１２に示すように、右上隅の対応点を含む垂直軸上の対応点についてはインデクス０を付与し、以下、左下隅の対応点を含む垂直軸に至るまで、インデクス１，２，３・・・を付与するものである。この場合、部分経路列には分割されず、各経路列が経路列記憶部１４の１つのアドレスに記憶される。
【００４４】
第３の変形例における経路列記憶部１４からの経路の読み出しは、図１３のフローチャートのようにして行われる。先ずステップＳ５０において、現在の対応点における経路を判別し、経路が「左」であれば、ステップＳ５１においてアドレスを＋１、インデクスを＋１してステップＳ５４に進む。また、ステップＳ５０において、経路が「左下」であれば、ステップＳ５２においてアドレスを＋２、インデクスを＋１してステップＳ５４に進む。また、ステップＳ５０において、経路が「下」であれば、ステップＳ５３においてアドレスを＋１、インデクスを±０してステップＳ５４に進む。
【００４５】
次にステップＳ５４において、増減後のアドレスから経路列を読み出し、ステップＳ５５において、その経路列のうち、増減後のインデクスで示される経路を選択する。そしてステップＳ５６において経路を構築し、ステップＳ５０に戻る。
【図面の簡単な説明】
【００４６】
【図１】本実施の形態における信号処理装置の概略構成を示す図である。
【図２】本実施の形態における経路列を示す図である。
【図３】同信号処理装置の処理手順を説明するフローチャートである。
【図４】経路列の経路列記憶部への格納を模式的に示す図である。
【図５】各対応点に付加されるインデクスと部分経路列が格納されるアドレスとを示す図である。
【図６】第１，第２の経路列記憶部に格納される際の部分経路列の配列を示す図である。
【図７】図５の場合における経路列記憶部からの経路の読み出しを説明するフローチャートである。
【図８】各対応点に付加されるインデクスと経路列が格納されるアドレスとを示す図である。
【図９】図８の場合における経路列記憶部からの経路の読み出しを説明するフローチャートである。
【図１０】各対応点に付加されるインデクスと経路列が格納されるアドレスとを示す図である。
【図１１】図１０の場合における経路列記憶部からの経路の読み出しを説明するフローチャートである。
【図１２】各対応点に付加されるインデクスと経路列が格納されるアドレスとを示す図である。
【図１３】図１２の場合における経路列記憶部からの経路の読み出しを説明するフローチャートである。
【図１４】ＤＰマッチングを用いて第１の画像と第２の画像との画素パターンを対応付ける場合について説明する図である。
【符号の説明】
【００４７】
１ 信号処理装置、１０ 評価値計算部、１１ 経路選択部、１２ 経路列生成部、１３ 経路列格納終了判定部、１４ 経路列記憶部、１５ 計算終了判定部、１６ 経路構築部、２０ 第１の部分経路列記憶部、２１ 第２の部分経路列記憶部
【技術分野】
【０００１】
本発明は、ＤＰ（Dynamic Programming）マッチング（動的計画法）を用いた演算を行う信号処理装置及びその方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来より、２枚の画像からの仮想視点画像や距離画像の作成、或いは音声認識等の分野において、ＤＰ（Dynamic Programming）マッチング（動的計画法）が広く用いられており、ソフトウェアでは実装されているものもある（特許文献１等を参照）。
【０００３】
一例として、第１の画像と第２の画像との画素パターンを対応付ける場合について、図１４を参照しながら説明する。
【０００４】
先ず、第１の画像のあるスキャンライン（水平ライン）上の各要素を水平軸、第２の画像の対応するスキャンライン上の各要素を垂直軸として並べ、要素同士の全ての対応点における評価値を求める。ここで用いるスキャンラインは、エピポーラ拘束等を用いて予め算出しておいたものである。例えば要素ｎ１と要素ｎ２との対応点（図中四角で示す）における評価値を求める場合、それらの要素の画素値に加えて、要素ｎ１と要素(ｎ−１)２との対応点、要素(ｎ−１)１と要素ｎ２との対応点、及び要素(ｎ−１)１と要素(ｎ−１)２との対応点（何れも、図中丸で示す）における評価値のそれぞれを用いて３種類の評価値を計算し、これらの３種類の評価値のうちの最小値を当該対応点における評価値として記憶する。この際、その最小の評価値をもたらした経路（左，下，左下の何れか）を併せて記憶する。この計算を左下隅の対応点から始めて右上隅の対応点へと至るまでの全ての対応点について行い、且つ、全ての経路を記憶する。
【０００５】
なお、評価値の計算方法は解決しようとする問題によって種々存在するが、例えばステレオ法を用いて距離画像を作成する場合の評価値の計算方法は、非特許文献１等に記載されている。
【０００６】
その後、右上隅の対応点から始めて、記憶された経路を逆に辿って左下隅の対応点へと至る経路を構築すると、その経路上に存在する対応点がスキャンライン上の要素同士の対応関係を表すことになる。
【０００７】
このように、ＤＰマッチングでは、各要素の組合せという小さい単位の計算を繰り返して解くことによって、それと同じタイプの大きな単位の問題を解決する。
【０００８】
【特許文献１】特開平２−５３１８７号公報
【非特許文献１】J. Cox, et al.,“A Maximum Likelihood Stereo Algorithm”, COMPUTER VISION AND IMAGE UNDERSTANDING, Vol.63, No.3, May, pp.542-567, 1996
【特許文献２】特開昭５０−２３５３３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ところで、図１４から分かるように、ある対応点における評価値を計算するためには、当該対応点の左，下，左下の対応点における評価値が事前に計算されている必要があり、また、その計算を行う時点までそれらの評価値を記憶しておかなければならない。このため、単純に逐次処理を行うと、要素数がＮ倍になればその計算量及び計算に要する時間はＮ２倍となり、また、その計算を行う時点まで記憶しておかなければならない評価値の数も飛躍的に増大していく。したがって、実時間処理を行うためにハードウェア化を試みたとしても、リソース量やメモリ量、或いは動作速度の観点からその実現は困難であった。
【００１０】
そこで、従来、左下隅の対応点と右上隅の対応点とを結ぶ対角線の軌跡に沿って複数の対応点における評価値を並列に計算するようにハードウェアを構成することにより、評価値の計算に要する時間を削減する技術が提案されている（特許文献２を参照）。この特許文献２記載の技術によれば、ＤＰマッチングにおける評価値の計算を高速に行うことができると共に、並列計算した各対応点において最小の評価値を与える経路を記憶することができる。
【００１１】
しかしながら、特許文献２記載の技術を含む従来の技術では、各対応点における経路を単純に記憶するのみであったため、右上隅の対応点から始めて、記憶された経路を逆に辿って左下隅の対応点へと至る経路を構築する際に、各対応点における経路を効率的に読み出すことができず、経路構築に比較的長い時間を要してしまうという問題があった。
【００１２】
本発明は、このような従来の実情に鑑みて提案されたものであり、ＤＰマッチングにおける経路構築を効率よく高速に行うことが可能な信号処理装置及びその方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上述した目的を達成するために、本発明に係る信号処理装置は、第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める信号処理装置であって、上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算手段と、上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択手段と、上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列が格納される経路列記憶手段と、上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築手段とを備え、上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、上記経路構築手段は、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定することを特徴とする。
【００１４】
また、上述した目的を達成するために、本発明に係る信号処理方法は、第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める信号処理方法であって、上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算工程と、上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択工程と、上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列を経路列記憶手段に格納する経路列記憶工程と、上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築工程とを有し、上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、上記経路構築工程では、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定することを特徴とする。
【００１５】
また、本発明に係るプログラムは、上述した信号処理をコンピュータに実行させるものである。
【発明の効果】
【００１６】
本発明に係る信号処理装置及びその方法、並びにプログラムによれば、ＤＰマッチングにおける経路構築を効率よく高速に行うことが可能とされる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００１８】
先ず、本実施の形態における信号処理装置の概略構成を図１に示す。図１に示すように、本実施の形態における信号処理装置１は、入力された各対応点における要素値に基づいて、各対応点について３種類の評価値を計算する評価値計算部１０と、各対応点について３種類の評価値のうち最小の評価値を与える経路（左，下，左下の何れか）を選択する経路選択部１１と、それぞれ１つの経路を格納する記憶子が複数並んだ構造を有し、各対応点について選択された経路を各記憶子に順次格納して後述する経路列を生成する経路列生成部１２と、経路列生成部１２に対して１列分の経路列の格納が終了したか否かを判定する経路列格納終了判定部１３と、経路列生成部１２で生成された経路列が格納される経路列記憶部１４と、全ての対応点について評価値が計算され、経路列が経路列記憶部１４に格納されたか否かを判定する計算終了判定部１５と、経路列記憶部１４に格納された経路列に基づいて、２系列の要素の対応関係を表す経路を構築する経路構築部１６とから構成されている。
【００１９】
ここで、上述した経路列とは、図２の楕円で示すように、左上隅の対応点と右下隅の対応点とを結ぶ対角線に平行な直線（以下、「列」という。）上の対応点における経路を表したものである。なお、評価値計算部１０においては、各列上の対応点の評価値を並列に計算するようにしてもよい。
【００２０】
この信号処理装置１の処理手順について、図３のフローチャートを用いて説明する。先ずステップＳ１において、評価値計算部１０は、各対応点における要素値を入力して３種類の評価値を計算し、ステップＳ２において、経路選択部１１は、各対応点について３種類の評価値のうち最小の評価値を与える経路（左，下，左下の何れか）を選択する。選択された経路は、経路列生成部１２内の各記憶子に順次格納され、経路列毎に並べて纏められる。なお、経路列記憶部１２内の記憶子は、２系列の要素のうち、多い方の要素数分用意すればよい。
【００２１】
次にステップＳ３において、経路列格納終了判定部１３は、経路列生成部１２に対する１列分の経路列の格納が終了したか否かを判定し、終了していなければステップＳ１に戻って計算を繰り返す。一方、１列分の経路列の格納が終了していれば、ステップＳ４に進む。
【００２２】
続いてステップＳ４において、経路列生成部１２は、生成された経路列を経路列記憶部１４に格納する。ここで、経路列は、図４の模式図に示すようにして経路列記憶部１４に格納される。すなわち、経路列は左下隅の対応点と右上隅の対応点とを結ぶ対角線で２つの部分経路列に分割され、右下の部分経路列はそのまま第１の部分経路列記憶部２０に格納され、左上の部分経路列はその並び順を反転して第２の部分経路列記憶部２１に格納される。この際、各部分経路列は、第１，第２の部分経路列記憶部２０，２１内の１つのアドレスに格納される。
【００２３】
続いてステップＳ５において、計算終了判定部１５は、全ての経路列の経路列記憶部１４への格納が終了したか否かを判定し、終了していなければステップＳ１に戻って計算を繰り返し、終了していればステップＳ６に進む。
【００２４】
続いてステップＳ６において、経路構築部１６は、経路列記憶部１４に格納された経路列に基づいて、２系列の要素の対応関係を表す経路を構築する。
【００２５】
ここで、経路列の経路列記憶部１４への格納と、経路列記憶部１４に格納された経路列に基づく経路構築について、さらに詳細に説明する。
【００２６】
上述したように、各部分経路列は、第１，第２の部分経路列記憶部２０，２１内の１つのアドレスに格納されるが、この際、部分経路列上での位置に応じて、例えば図５に示すようにインデクスが付与される。すなわち、左下隅の対応点と右上隅の対応点とを結ぶ対角線上の対応点についてはインデクス０が付与され、対角線よりも右の対応点についてはそれぞれの経路列に沿って対角線に近い対応点からインデクス１，２，３・・・が付与され、対角線よりも左の対応点についてはそれぞれの経路列に沿って対角線に近い対応点からインデクス−１，−２，−３・・・が付与される。そして、右上隅の対応点における経路を含む経路列は第１，第２の部分経路列記憶部２０，２１内のアドレス０に格納され、以下、左下隅の対応点における経路を含む経路列に至るまで、アドレス１，２，３・・・に格納される。なお、各部分経路列は、例えば図６のような配列で第１，第２の部分経路列記憶部２０，２１内の各アドレスに格納される。
【００２７】
上述した経路構築部１６は、アドレス及びインデクスを増減させながら、経路列記憶部１４から経路を読み出し、２系列の要素の対応関係を表す経路を構築する。この経路列記憶部１４からの経路の読み出しは、図７のフローチャートのようにして行われる。先ずステップＳ１０において、現在の対応点における経路を判別し、経路が「左」であれば、ステップＳ１１において現在のアドレスが奇数であるか偶数であるかを判別する。そして、現在のアドレスが奇数であればステップＳ１３においてアドレスを＋１、インデクスを±０してステップＳ１８に進み、偶数であればステップＳ１４においてアドレスを＋１、インデクスを−１してステップＳ１８に進む。また、ステップＳ１０において、経路が「下」であれば、ステップＳ１２において現在のアドレスが奇数であるか偶数であるかを判別する。そして、現在のアドレスが偶数であればステップＳ１５においてアドレスを＋１、インデクスを±０してステップＳ１８に進み、奇数であればステップＳ１６においてアドレスを＋１、インデクスを＋１してステップＳ１８に進む。また、ステップＳ１０において、経路が「左下」であれば、ステップＳ１７においてアドレスを＋２、インデクスを±０してステップＳ１８に進む。
【００２８】
次にステップＳ１８において、増減後のアドレスから経路列を読み出し、ステップＳ１９において、その経路列のうち、増減後のインデクスで示される経路を選択する。そしてステップＳ２０において経路を構築し、ステップＳ１０に戻る。
【００２９】
ここで、例えば図８の太線で示すような経路が構築される場合のアドレス及びインデクスの増減方法について説明する。経路の構築は右上隅の対応点から始められる。この対応点における経路は、第１の部分経路列記憶部２０のアドレス０のインデクス０に格納されている。これが「左下」を示しているので、左下へと進む。この場合、次の経路は、アドレスを＋２、インデクスを±０した場所、つまりアドレス２のインデクス０に格納されている。これが「下」を示しているので下へと進む。この場合、次の経路は、アドレスを＋１、インデクスを±０した場所、つまりアドレス３のインデクス０に格納されている。このような処理を繰り返すことにより、図中太線で示すような経路が構築される。
【００３０】
以上のように、本実施の形態における信号処理装置１によれば、部分経路列上での位置に応じてインデクスを付与することにより、例えば図７のフローチャートのような簡単な論理の処理で経路を構築することができ、また、各経路列を１つのアドレスに格納することにより、１回の読み出し処理で１つの対応点における経路が構築できるため、ＤＰマッチングにおける経路構築を効率よく行うことが可能となる。
【００３１】
したがって、この信号処理装置１を用いることにより、例えばＤＰマッチングを用いた仮想視点画像や距離画像の生成、ビュー・インターポレーション（View Interpolation）等の画像処理や、或いは音声認識処理等が実時間で行えるようなシステムを構築することができる。
【００３２】
例えばステレオ法を用いた距離画像生成にこの信号処理装置１を用いた場合、奇数アドレスのインデクスを＋０．５すれば、このインデクスをそのまま距離情報のインデクスとすることができる。なお、＋０．５を実現するには、インデクスを１ビット拡張し、アドレスの最下位ビットを付加すればよい。
【００３３】
また、同じくステレオ法を用いた距離画像生成にこの信号処理装置１を用いた場合、２台のカメラの光軸が交差しない範囲という拘束条件を設ければ、左下隅の対応点と右上隅の対応点とを結ぶ対角線よりも右の対応点についてのみ部分経路列を求めればよく、第２の部分経路列記憶部２１を省略することができる。
【００３４】
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【００３５】
例えば、上述した実施の形態では、図５に示したように、左下隅の対応点と右上隅の対応点とを結ぶ対角線上の対応点についてはインデクス０を付与し、対角線よりも右の対応点についてはそれぞれの経路列に沿って対角線に近い対応点からインデクス１，２，３・・・を付与し、対角線よりも左の対応点についてはそれぞれの経路列に沿って対角線に近い対応点からインデクス−１，−２，−３・・・を付与するものとして説明したが、本発明はこの例に限定されるものではなく、以下の第１〜第３の変形例に示すように、種々の変更が可能である。
【００３６】
先ず、第１の変形例は、図８に示すように、左下隅の対応点と右上隅の対応点とを結ぶ対角線上の対応点についてはインデクス０を付与し、対角線よりも右の対応点については垂直軸に沿って対角線に近い対応点からインデクス１，２，３・・・を付与し、対角線よりも左の対応点については垂直軸に沿って対角線に近い対応点からインデクス−１，−２，−３・・・を付与するものである。この場合、部分経路列が２列分ずつ第１，第２の部分経路列記憶部２０，２１に格納される。なお、負のインデクスが付与された対応点における経路を格納する際に、インデクス０が付与された対応点における経路を含めるようにしても構わない。
【００３７】
第１の変形例における経路列記憶部１４からの経路の読み出しは、図９のフローチャートのようにして行われる。先ずステップＳ３０において、現在の対応点における経路を判別し、経路が「左」であれば、ステップＳ３１においてアドレスを±０、インデクスを−１してステップＳ３４に進む。また、ステップＳ３０において、経路が「左下」であれば、ステップＳ３２においてアドレスを＋１、インデクスを±０してステップＳ３４に進む。また、ステップＳ３０において、経路が「下」であれば、ステップＳ３３においてアドレスを±０、インデクスを＋１してステップＳ３４に進む。
【００３８】
次にステップＳ３４において、増減後のアドレスから経路列を読み出し、ステップＳ３５において、その経路列のうち、増減後のインデクスで示される経路を選択する。そしてステップＳ３６において経路を構築し、ステップＳ３０に戻る。
【００３９】
なお、この第１の変形例の場合においても、ステレオ法を用いた距離画像生成に用いた場合に、２台のカメラの光軸が交差しない範囲という拘束条件を設ければ、第２の部分経路列記憶部２１を省略することができる。
【００４０】
次に、第２の変形例は、図１０に示すように、右上隅の対応点を含む水平軸上の対応点についてはインデクス０を付与し、以下、左下隅の対応点を含む水平軸に至るまで、インデクス１，２，３・・・を付与するものである。この場合、部分経路列には分割されず、各経路列が経路列記憶部１４の１つのアドレスに記憶される。
【００４１】
第２の変形例における経路列記憶部１４からの経路の読み出しは、図１１のフローチャートのようにして行われる。先ずステップＳ４０において、現在の対応点における経路を判別し、経路が「左」であれば、ステップＳ４１においてアドレスを＋１、インデクスを±０してステップＳ４４に進む。また、ステップＳ４０において、経路が「左下」であれば、ステップＳ４２においてアドレスを＋２、インデクスを＋１してステップＳ４４に進む。また、ステップＳ４０において、経路が「下」であれば、ステップＳ４３においてアドレスを＋１、インデクスを＋１してステップＳ４４に進む。
【００４２】
次にステップＳ４４において、増減後のアドレスから経路列を読み出し、ステップＳ４５において、その経路列のうち、増減後のインデクスで示される経路を選択する。そしてステップＳ４６において経路を構築し、ステップＳ４０に戻る。
【００４３】
続いて第３の変形例は、図１２に示すように、右上隅の対応点を含む垂直軸上の対応点についてはインデクス０を付与し、以下、左下隅の対応点を含む垂直軸に至るまで、インデクス１，２，３・・・を付与するものである。この場合、部分経路列には分割されず、各経路列が経路列記憶部１４の１つのアドレスに記憶される。
【００４４】
第３の変形例における経路列記憶部１４からの経路の読み出しは、図１３のフローチャートのようにして行われる。先ずステップＳ５０において、現在の対応点における経路を判別し、経路が「左」であれば、ステップＳ５１においてアドレスを＋１、インデクスを＋１してステップＳ５４に進む。また、ステップＳ５０において、経路が「左下」であれば、ステップＳ５２においてアドレスを＋２、インデクスを＋１してステップＳ５４に進む。また、ステップＳ５０において、経路が「下」であれば、ステップＳ５３においてアドレスを＋１、インデクスを±０してステップＳ５４に進む。
【００４５】
次にステップＳ５４において、増減後のアドレスから経路列を読み出し、ステップＳ５５において、その経路列のうち、増減後のインデクスで示される経路を選択する。そしてステップＳ５６において経路を構築し、ステップＳ５０に戻る。
【図面の簡単な説明】
【００４６】
【図１】本実施の形態における信号処理装置の概略構成を示す図である。
【図２】本実施の形態における経路列を示す図である。
【図３】同信号処理装置の処理手順を説明するフローチャートである。
【図４】経路列の経路列記憶部への格納を模式的に示す図である。
【図５】各対応点に付加されるインデクスと部分経路列が格納されるアドレスとを示す図である。
【図６】第１，第２の経路列記憶部に格納される際の部分経路列の配列を示す図である。
【図７】図５の場合における経路列記憶部からの経路の読み出しを説明するフローチャートである。
【図８】各対応点に付加されるインデクスと経路列が格納されるアドレスとを示す図である。
【図９】図８の場合における経路列記憶部からの経路の読み出しを説明するフローチャートである。
【図１０】各対応点に付加されるインデクスと経路列が格納されるアドレスとを示す図である。
【図１１】図１０の場合における経路列記憶部からの経路の読み出しを説明するフローチャートである。
【図１２】各対応点に付加されるインデクスと経路列が格納されるアドレスとを示す図である。
【図１３】図１２の場合における経路列記憶部からの経路の読み出しを説明するフローチャートである。
【図１４】ＤＰマッチングを用いて第１の画像と第２の画像との画素パターンを対応付ける場合について説明する図である。
【符号の説明】
【００４７】
１ 信号処理装置、１０ 評価値計算部、１１ 経路選択部、１２ 経路列生成部、１３ 経路列格納終了判定部、１４ 経路列記憶部、１５ 計算終了判定部、１６ 経路構築部、２０ 第１の部分経路列記憶部、２１ 第２の部分経路列記憶部
【特許請求の範囲】
【請求項１】
第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める信号処理装置であって、
上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算手段と、
上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択手段と、
上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列が格納される経路列記憶手段と、
上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築手段とを備え、
上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、
上記経路構築手段は、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定する
ことを特徴とする信号処理装置。
【請求項２】
上記経路列記憶手段は、上記第１，第２の要素列の最後の要素同士の対応点と、上記第１，第２の要素列の最初の要素同士の対応点とを結ぶ対角線で各経路列を分割して２つの部分経路列としたときの一方の部分経路列が格納される第１の部分経路列記憶手段と、他方の部分経路列が格納される第２の部分経路列記憶手段とを有することを特徴とする請求項１記載の信号処理装置。
【請求項３】
第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める信号処理方法であって、
上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算工程と、
上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択工程と、
上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列を経路列記憶手段に格納する経路列記憶工程と、
上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築工程とを有し、
上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、
上記経路構築工程では、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定する
ことを特徴とする信号処理方法。
【請求項４】
第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める処理をコンピュータに実行させるプログラムであって、
上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算工程と、
上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択工程と、
上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列を経路列記憶手段に格納する経路列記憶工程と、
上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築工程とを有し、
上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、
上記経路構築工程では、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定する
ことを特徴とするプログラム。
【請求項１】
第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める信号処理装置であって、
上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算手段と、
上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択手段と、
上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列が格納される経路列記憶手段と、
上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築手段とを備え、
上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、
上記経路構築手段は、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定する
ことを特徴とする信号処理装置。
【請求項２】
上記経路列記憶手段は、上記第１，第２の要素列の最後の要素同士の対応点と、上記第１，第２の要素列の最初の要素同士の対応点とを結ぶ対角線で各経路列を分割して２つの部分経路列としたときの一方の部分経路列が格納される第１の部分経路列記憶手段と、他方の部分経路列が格納される第２の部分経路列記憶手段とを有することを特徴とする請求項１記載の信号処理装置。
【請求項３】
第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める信号処理方法であって、
上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算工程と、
上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択工程と、
上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列を経路列記憶手段に格納する経路列記憶工程と、
上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築工程とを有し、
上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、
上記経路構築工程では、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定する
ことを特徴とする信号処理方法。
【請求項４】
第１の要素列と第２の要素列との要素同士の対応関係を動的計画法を用いて求める処理をコンピュータに実行させるプログラムであって、
上記第１の要素列を第１の軸、上記第２の要素列を上記第１の軸と垂直な第２の軸として、要素同士が対応する各対応点における評価値を計算する評価値計算工程と、
上記各対応点における評価値に基づいて各対応点における経路を選択する経路選択工程と、
上記第１，第２の要素列の最後の要素同士を結ぶ対角線に平行な各列上の対応点における経路である経路列を経路列記憶手段に格納する経路列記憶工程と、
上記第１の要素列と上記第２の要素列とのうち、対応する要素同士の対応点における経路を上記経路列記憶手段から順次読み出し、上記第１の要素列と上記第２の要素列との要素同士の対応関係を表す経路を構築する経路構築工程とを有し、
上記経路列記憶手段では、各経路列の位置に応じて当該経路列が格納されるアドレスが決定されていると共に、各経路列上での位置に応じて当該経路列に含まれる各経路のインデクスが決定されており、
上記経路構築工程では、各対応点における経路に基づいて、次に読み出すべき経路が格納されたアドレス及びインデクスを特定する
ことを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００６−２７７５７５（Ｐ２００６−２７７５７５Ａ）
【公開日】平成１８年１０月１２日（２００６．１０．１２）
【国際特許分類】
【出願番号】特願２００５−９８７８１（Ｐ２００５−９８７８１）
【出願日】平成１７年３月３０日（２００５．３．３０）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成１８年１０月１２日（２００６．１０．１２）
【国際特許分類】
【出願日】平成１７年３月３０日（２００５．３．３０）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]