JPH05303588A - 相似関数の極値の位置の決定回路装置 - Google Patents

Abstract

(57)【要約】 【目的】 僅かしか計算コストがかからないようにし
た、相似関数の極値の位置の決定回路装置を提供するこ
とである。 【構成】 デジタル形において存在する２つの信号の相
似関数の極値の位置を決定する回路装置において、前記
２つの信号から比１：ｎのサブサンプリングに対応す
る、極値のおおよその位置を決定する値を求め、 前記２
つの信号から、比１：ｎ２（ｎ２≦ｎ１）におけるサブ
サンプリングに対応する、極値の位置を一層正確に決定
する値を求め、必要に応じて極値の位置の決定を連続的
に小さくなる数ｎ１およびｎ２によって繰り返す手段
（１，２，３）が設けられている。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、デジタルの形において
存在する２つの信号の相似ないし類似関数の極値の位置
の決定回路装置に関する。

【０００２】

【従来の技術】この形式の回路装置は例えば、２つの音
声信号の時間的なずれを測定するために使用することが
できる。このような場合において、その相似性ないし類
似性を求めるべきである２つの信号は、変数（時間の）
にのみ依存している。相似ないし類似関数自体も、たっ
た１つの変数、即ち２つの信号の相互の時間的なずれの
関数である。

【０００３】２つの変数に依存している信号に対する用
途の例は、画像符号化において生じる。画像符号化（例
えば、西独国特許公開第３７２６５２０号公報を参照さ
れたい）においてビットレートを低減するために、既に
伝送された画像（第１の信号）のどの部分が実時間の画
像の部分（第２の信号）と最大の相似性を有しているか
が検査される。この場合信号は、その都度２つの位置座
標の関数でありかつ相似関数は、その都度２つの座標軸
の方向における２つのずれの関数である。

【０００４】形式上簡単にするために以下、信号が１つ
の変数にのみ依存している場合についてのみについて考
察する。というのは複数の変数へ拡張することは当業者
には容易であるからである。

【０００５】デジタルの形において存在する２つの信号
ｆおよびｇの相似関数Ａとは、ここでは次の形のそれぞ
れの関数、即ち

【０００６】

【数１】

【０００７】を意味し、ただしｋは正規化定数、ｉおよ
びμは整数であり、かつｆ（ｉ）およびｇ（ｉ−μ）
は、整数ｉおよびｉ−μによって表されている時点にお
ける関数ｆおよびｇの標本値である。その場合Ａ（μ）
は相似関数の、時点μにおける標本値である。μは同時
に、関数ｇの、その出発位置に対するずれである。考慮
されるずれμの数は制限されている。即ちμは−ｐとｐ
との間のすべての整数をとることができ、その際ｐは同
様整数でありかつ用途に応じて種々異なった大きさであ
る可能性がある。ｐは、例えばＡ（μ）の極値を探索す
る所謂探索領域を固定する。Ｆはまず、２つの関数ｆお
よびｇの詳しく特徴付けられていない結合を表してい
る。ｂは、式（１）における被加数の数である。

【０００８】式（１）の評価の際、関数の独立変数に、
当該の標本値が格納されているメモリアドレスのシンボ
ルとしての意味を持たせることもできる。どんな意味を
もっているかは、関連から明らかでありかつ以下明確に
挙げないものとする。

【０００９】結合Ｆに対して関数ｆおよびｇの積が使用
されるとき、２つの関数ｆおよびｇの相関関数が生じ
る。相関関数がその最大値をとるずれに対して、２つの
関数ｆおよびｇの最大の相似性ないし類似性が生じる。

【００１０】Ｆに対して、差の絶対値または二乗を使用
するとき、Ａ（μ）が最小値をとるμに対して、関数ｆ
およびｇの最大の相似性ないし類似性が生じる。個々の
例においてどんな結合Ｆを使用して用いるかは、その例
の付随状況に依存しておりかつここではこれ以上説明し
ないものとする。

【００１１】相似関数Ａ（μ）の最大値または最小値お
よびその位置μｅのみが重要なのではないことが多く、
つまり最大値の場合には次に小さな値および最小値の場
合には次に大きな値並びにこれらの値の位置が重要であ
ることも多い。上述したように、次に続く値も含めた極
値をここでは、極値と呼ぶことにする。

【００１２】上記式（１）の直接評価の際、極値および
その位置の決定の際に、関数ｆおよびｇの種々の異なっ
た値に対して２ｐｂ＋ｂ回の結合Ｆを求めなければなら
ない。このことは、数多くの用途に対して著しい計算コ
ストを意味することになる。

【００１３】

【発明が解決しようとする課題】本発明の課題は、相似
関数の極値およびその位置を決定するための計算コスト
が著しく低減されるようにした、冒頭に述べた形式の回
路装置を提供することである。

【００１４】

【課題を解決するための手段】この課題は、請求項１の
特徴部分に記載の構成によって解決される。その他の請
求項には有利な実施態様が記載されている。

【００１５】

【実施例】次に本発明を図示の実施例につき図面を用い
て詳細に説明する。

【００１６】図１には、本発明の回路の基本構成が示さ
れている。

【００１７】図１の回路の中心モジュールは、書き込み
および読み出しアドレスの計算によって書き込みー読み
出しメモリ１の書き込みおよび読み出し過程をアドレス
線３ａを介して制御するアドレス制御部３である。本発
明の説明にとって、書き込みは副次的な役割しか有して
いないので、詳しく説明しないことにする。

【００１８】この実施例においてｂは式（１）に従って
値１６を有しかつｐは値８を有している。ｆの標本値
は、メモリ１において第１のアドレス０ないし１５に格
納されておりかつｇの標本値は、−８から２３に及ぶ第
２のアドレスに格納されている。

【００１９】図３のａには、２つの上下に並んだスケー
ル、それぞれｇに対するスケールと、ｆに対するスケー
ルとが示されている。スケール上の数字は、ｇおよびｆ
の標本値がメモリ１において格納されているアドレスを
示している。式（１）の評価は、図３のａからわかるよ
うに、上下に位置するアドレスに格納されている、ｇお
よびｆの標本値を相互に乗算し（即ちＦは例えば乗算を
表している）かつそれから個々の積を累算するようにし
て行われる。名目上同じアドレスは上下に位置している
ので、図３のａに示されている、２つのスケールの相対
位置は、式（１）におけるずれμが値０を有しているこ
とを意味している。μ＝１が選択されるとき、同じ意味
を維持することできるためには、下側のスケールは単位
スケールだけ左方向にずらされなければならない。μ＝
ｐ＝８に対してはスケール始端が上下に位置し、μ＝−
ｐ＝−８に対しては、スケール終端が上下に位置する。
そこで（アドレス制御部３によって制御されて）ｇおよ
びｆの標本値はアドレスの増加順序で（ｇ（−８）およ
びｆ（０）において始まる）同時にメモリ１から読み出
されかつ図２に示された（公知の）相関器の入力側に供
給されるとき、この読み出し過程の終了時に相関器の出
力側に、図１の相関器が１７段を有しかつｆの標本値の
読み出しが循環的に行われることを前提とすれば、相関
関数の標本値Ａ（８）ないしＡ（−８）が取り出され
る。図３のａによれば、下側のスケールが左の下縁から
右の上縁に段階的にずらされることを示している。

【００２０】この過程は、式（１）の直接評価に相当す
る。相関器２の出力データは線２ａを介してアドレス制
御部３に供給され、アドレス制御部は、比較により大き
さＡ（８）ないしＡ（−８）の極値を決定する手段を含
んでいる。例えば極端値の位置は、極値が発生した、相
関器２の出力側において一義的に検出可能である。

【００２１】ｐがこの実施例で示された値より大きい場
合には、式（１）の直接評価を維持しようとするとき、
相関器の段数が非常に大きくなることは明らかである。
従って大きなｐに対して、本発明によれば、次に説明す
るように行われる。２つの信号のサブサンプリングが比
１：４において行われる、即ちアドレス制御部３は、記
憶されている標本値のその都度４番目の標本値のみが読
み出されかつ相関器２に供給されるように考慮する。図
３のｂにおいて、この場合に読み出される値にｘが付さ
れている。ｘを付されたすべての値の読み出しおよびそ
の、相関器２への伝送が行われると、再び２つのスケー
ルにおける最も左側に位置するｘから始められる。それ
から相関器２の出力側に（最高の精度でとは言えない
が）値Ａ（８），Ａ（４），Ａ（０），Ａ（−４）およ
びＡ（−８）が現れる。Ａ（４）がこれら値の極値であ
れば（従ってその位置はμｅ１＝４である）、この結果
は図３のｃに示されているように、２つのスケールの位
置調整によって示される。

【００２２】その後一層細かなサブサンプリング、即ち
１：２が選択されかつーその前に見付けられた、極値の
位置μｅ１＝４から出発してーこの位置の周囲において
極値の探索が続けられる。そこでアドレス制御部３によ
って読み出された標本値には、図３のｃの○が付されて
いる。○を付されたすべての値の読み出しは再び左から
右へと行われる。それから相関器２は標本値Ａ（６），
Ａ（４）およびＡ（２）を送出する。この場合Ａ（６）
が極値であるとき、最後の探索においてもはやサブサン
プリングは使用されないが、Ａ（７），Ａ（６）および
Ａ（５）の呼び出しは制限される。

【００２３】一般的な例において図１の回路の動作は次
の通りである：アドレス制御部において、ｐの約数およ
びｂの約数である整数ｎ１が記憶されている。アドレス
制御部により、連続変数ｉはｎ１＊ｉ１に置き換えられ
かつずれμはｎ１＊μ１に置き換えられる。連続変数ｉ
１は順次、０からｂ１＝ｂ／ｎ１を有するｂ１−１まで
のすべての整数値をとりかつμ１は順次、ｐ１＝ｐ／ｎ
１を有する−ｐ１から＋ｐ１までのすべての整数値をと
る。そこでアドレス制御部３はｆおよびｇのこのように
して計算されたアドレスを増加する順序において発生す
る。所属の標本値は、値Ａ（−ｎ１ｐ１），Ａ（−ｎ１
（ｐ１−１）ないしＡ（ｎ１ｐ１）を計算する相関器２
に供給される。

【００２４】それからアドレス制御部３は相似関数の極
値およびこの値ｖ０＝ｎ１＊μ１ｅの所属のずれ（位
置）を決定する。

【００２５】アドレス制御部において更に、ｎ１の約数
でありかつｂの約数である整数ｎ２が記憶されている。
アドレス制御部３は式（１）における独立変数をｎ２＊
ｉ２に置き換えかつｇの独立変数をｎ２＊ｉ２−ｎ２＊
μ２＋ｖ０に置き換える。ｉ２は順次、０からｂ／ｎ２
−１のすべての整数の値をとりかつμ２は−ｎ１／ｎ２
−１からｎ１／ｎ２−１までのすべての整数の値をと
る。このようにして求められたアドレスは再び増加する
順序でメモリ１に転送されかつそれから所属の標本値が
相関器２に供給される。アドレス制御部が比較によっ
て、μ２Ａのどの値に対して極値をとっているかを判定
したとき、この極値の位置ｖとしてｖ１＝ｖ０＋ｎ２＊
μ２が生じる。

【００２６】そこで極値のこの位置が一義的なものとし
て引き続き使用されるか、或は上述のステップが、一層
小さくなる、サブサンプリング比によって繰り返され
る。

【００２７】図２の相関器において詳しく示されていな
いクロックによってｆの標本値が上側の入力線に供給さ
れかつｇの標本値が遅延素子Ｄ１，Ｄ２，Ｄ３およびＤ
４を有する線に供給される。機能ユニットＫ１ないしＫ
５は式（１）に従ってそれらの入力データ間の結合Ｆを
実施する。これら結合の値は加算器Ａ１ないしＡ５およ
び累算器Ｒ１ないしＲ５によって連続的に累算されるの
で、出力側Ｚ１ないしＺ５において相似関数の標本値が
現れる。

【００２８】

【発明の効果】以上説明したように本発明により、僅か
な計算コストですむ、相似関数の極値の位置の決定回路
装置が実現される。

【図面の簡単な説明】

【図１】本発明の回路の基本ブロック図面である。

【図２】本発明の回路において使用することができるよ
うな、公知の相関器の回路のブロック線図である。

【図３】本発明の回路の動作の説明に供される線図であ
る。

【符号の説明】

１ 書き込みー読み出しメモリ ２ 相関器 ３ アドレス制御部 Ｄ１，Ｄ２，Ｄ３，Ｄ４ 遅延素子 Ｋ１，Ｋ２，Ｋ３，Ｋ４ 機能ユニット Ａ１，Ａ２，Ａ３，Ａ４ 加算器 Ｒ１，Ｒ２，Ｒ３，Ｒ４ 累算器

Claims (3)

【特許請求の範囲】
1. 【請求項１】 デジタル形において存在する２つの信号
   の相似関数の極値の位置の決定回路装置において、 −前記２つの信号から、比１：ｎ１におけるサブサンプ
   リングに対応する値を求め、 −該値によって、極値のおおよその位置を決定し、 −前記２つの信号から、比１：２ｎ（ｎ２≦ｎ１）にお
   けるサブサンプリングに対応する値を求め、 −該値によって、前記おおよその位置から出発して、極
   値の位置をより正確に決定し、 −必要に応じて前記極値の位置の決定を、連続的に小さ
   くなる数ｎ１およびｎ２にて繰り返す手段（１，２，
   ３）が設けられていることを特徴とする相似関数の極値
   の位置の決定回路装置。
2. 【請求項２】 次の特徴、即ち ａ）アドレス指定可能なメモリ（１）が設けられてお
   り、該メモリには前以て決められた箇所における信号の
   値がメモリアドレスに基づいて格納されており、 ｂ）アドレス制御部（３）が設けられており、該アドレ
   ス制御部を用いて前記信号の値が相関器（２）に供給さ
   れ、 ｃ）前記相関器によって計算された、相似関数の値およ
   びそれらの値に所属する位置を記憶する手段並びに比較
   によって前記相関器によって計算された相似関数の極値
   を求める手段が設けられており、 ｄ） ｄ．１ 前記アドレス制御部（３）は、比１：ｎ１にお
   いてサブサンプリングされた信号を前記相関器（２）に
   送出するアドレスを発生し、 ｄ．２ 前記サブサンプリングされた信号によって決定
   された、前記極値の位置が記憶され、 ｄ．３ 前記アドレス制御部（３）は、ｎ１より小さい
   ｎ２である比１：２ｎにおいてサブサンプリングされた
   信号を前記相関器（２）に送出しかつ前記極値のその前
   に決定された位置の所定の周囲の相似関数の経過の決定
   のためにのみ必要であるアドレスを発生し、 ｄ．４ 前記所定の周囲において前記相似関数の極値の
   位置が、比１：ｎ２においてサブサンプリングされた信
   号によって新たに決定される請求項１記載の相似関数の
   極値の位置の決定回路装置。
3. 【請求項３】 アドレス制御部（３）は、請求項２に記
   載のステップを段々と小さくなるサブサンプリングによ
   って繰り返す請求項２記載の相似関数の極値の位置の決
   定回路装置。