(57)【要約】  本発明は、行列の行列要素と比較行列の比較行列要素との間の割当てを決定する方法であって、対応テーブル（３００）のテーブルフィールド（３０１）に行列（１０１）の行列要素（１０３）の位置を書き込むための書込みプロセスを行列（１０１）の所定数の行列要素に対して実施するステップ、所定のオフセット後に、テーブルフィールド（３０１）を読み出す読出しプロセスを実施し、同じ所定数の行列要素（１０３，・・・１０６）に対して読出しプロセスが実施されるまで、テーブルフィールド（３０１）に格納された行列（１０１）の行列要素（１０３，・・・１０６）の位置を決定するステップ、読み出されたテーブルフィールド（３０１）の位置および比較行列（２０１）の比較行列要素（２０３，２０４）の現在位置から割当てを行うステップを含む方法に関する。書込みプロセスは、行列の行列要素の特性を読み出すステップと、行列要素からアクセス特性（１１０）を決定するステップと、アクセス特性（１１０）から対応テーブル（３００）のテーブルフィールド（３０１）を決定するステップと、行列（１０１）の行列要素（１０３，・・・１０６）の位置を、決定されたテーブルフィールド（３０１）に書き込むステップとを含む。読出しプロセスは、比較行列（２０１）の比較行列要素（２０３，２０４）の特性を読み出すステップと、比較行列要素（２０３，２０４）からアクセス特性を決定するステップと、比較行列要素（２０３，２０４）のアクセス特性（１１０）から対応テーブル（３００）のテーブルフィールド（３０１）を決定するステップと、決定されたテーブルフィールドから、格納されている行列要素の位置を読み出すステップとを含む。
2019537181.tif 000002
【特許請求の範囲】
【請求項１】
行列の行列要素と比較行列の比較行列要素との間の割当てを決定する方法であって、
対応テーブル（３００）のテーブルフィールド（３０１）に行列（１０１）の行列要素（１０３）の位置を書き込むための書き込みプロセスを行列（１０１）の多数の行列要素（１０３）に対して実施するステップと、
所定のオフセット後に、テーブルフィールド（３０１）を読み出す読出しプロセスを実施し、テーブルフィールド（３０１）に格納された行列（１０１）の行列要素（１０３，・・・１０６）の位置を決定するステップと、
読み出されたテーブルフィールド（３０１）の位置および比較行列（２０１）の比較行列要素（２０３，２０４）の現在位置から割当てを行うステップと、
を含み、
書込みプロセスは、
行列の行列要素の特性を決定するステップと、
行列要素からアクセス特性（１１０）を決定するステップと、
アクセス特性（１１０）から対応テーブル（３００）のテーブルフィールド（３０１）を決定するステップと、
行列（１０１）の行列要素（１０３，・・・１０６）の位置を、決定されたテーブルフィールド（３０１）に書き込むステップと、
を含み、
読出しプロセスが、
比較行列（２０１）の比較行列要素（２０３，２０４）の特性を読み出すステップと、
比較行列要素（２０３，２０４）からアクセス特性を決定するステップと、
比較行列要素（２０３，２０４）のアクセス特性（１１０）から対応テーブル（３００）のテーブルフィールド（３０１）を決定するステップと、
決定されたテーブルフィールドから格納されている行列要素の位置を読み出すステップと、
を含む、行列の行列要素と比較行列の比較行列要素との間の割当てを決定する方法。
【請求項２】
請求項１に記載の方法において、
前記行列要素（１０３，・・・１０６）と前記比較行列要素（２０３，２０４）との間で行われた割当て（４０１）から結果行列（４００）を形成するステップを、
含む方法。
【請求項３】
請求項１または２に記載の方法において、
前記行列要素（１０３，・・・１０６）および前記比較行列要素（２０３，２０４）の位置を座標によって指定する方法。
【請求項４】
請求項１〜３のいずれか一項に記載の方法において、
第１の行列（１０１）が第１の画像（１０２）であり、比較行列（２０１）が第２の画像（２０２）であり、前記行列要素（１０３，・・・１０６）が、第１の画像（１０２）内の画素であり、前記比較行列要素（２０３，２０４）が、第２の画像（２０２）内の画素である、
方法。
【請求項５】
請求項４に記載の方法において、
オプティカルフローを割当てに用いる方法。
【請求項６】
請求項１〜５のいずれか一項に記載の方法において、
特性が、行列要素（１０３，・・・１０６）または比較行列要素（２０３，２０４）の周りの環境を記述する方法。
【請求項７】
請求項１〜６のいずれか一項に記載の方法において、
前記行列要素（１０３，・・・１０６）または前記比較行列要素（２０３，２０４）の特性からアクセス特性（１１０）を形成し、アクセス特性（１１０）を決定するために、対応テーブル（３００）の大きさと比較して特性がどのような大きさであるかに依存して、特性全体、特性の一部。またはいくつかの行列要素（１０３，・・・１０６）もしくは比較行列要素（２０３，２０４）の特性を使用する方法。
【請求項８】
請求項１〜７のいずれか一項に記載の方法において、
前記対応テーブル（３００）の前記テーブルフィールド（３０１）がさらなる属性を含む方法。
【請求項９】
請求項１〜８のいずれか一項に記載の方法において、
前記行列（１０１）および前記比較行列（２０１）の順次の処理を行う方法。
【請求項１０】
請求項１〜９のいずれか一項に記載の方法において、
オフセットが固定されているか、または可変である方法。
【請求項１１】
請求項１〜１０のいずれか一項に記載の方法において、
読出しプロセスが書込みプロセスに続き、好ましくは書込みプロセスが、読出しプロセスが見つけるべき前記行列要素（１０３，・・・１０６）を既に処理しているようにオフセットを選択する方法。
【請求項１２】
請求項１〜１１のいずれか一項に記載の方法において、
前記行列（１０１）内に、既に処理された多数の前記行列要素（１０３，１０５，１０６）を含む検索フィールド（１２０）を設け、行列要素（１０３，・・・１０６）と前記比較行列要素（２０３，２０４）との割当てを、検索フィールド（１２０）内の行列要素（１０３，・・・１０６）に対してのみ行う方法。
【請求項１３】
請求項１〜１２のいずれか一項に記載の方法において、
好ましくは前記テーブルフィールド（３０１）から読み出された位置および現在の比較行列要素（２０４）の位置から計算されるベクトル（４０１）を割当てとして用いる方法。
【請求項１４】
請求項１〜１３のいずれか一項に記載の方法において、
前記対応テーブル（３００）のリセットを実施し、対応テーブル（３００）全体の１回のリセットを行うか、または対応テーブルの連続的なリセットを行う方法。
【請求項１５】
行列（１０１）の行列要素（１０３，・・・１０６）と比較行列（２０１）の比較行列要素（２０３，２０４）との間の割当てを決定するための装置であって、請求項１〜１４のいずれか一項に記載の方法を実施するように構成されている装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列の行列要素と比較行列の比較行列要素との間の割当てを決定する方法および対応する装置に関する。
【背景技術】
【０００２】
特に、カメラベースのシステムでは、２つの行列の要素の比較が行われ、要素間で割当てが行われる。例えば、行列および比較行列は、それぞれ、第１および第２の画像を表すことができる。割当てまたは対応の形成は、コンピュータビジョンの分野、特にオプティカルフローまたはステレオ視差において使用される。オプティカルフローでは時間軸方向の対応が形成され、３Ｄシーン内の点の投影が古い座標から新しい座標へ２Ｄ画像にどのように移動したかを決定する。画像内の動きは、シーン点の移動によって、またはカメラの移動によって、またはその両方によって同時に引き起こすことができる。
【０００３】
立体視では、異なる複数の画像および個々の画素間の対応を利用して、異なる位置に配置された２つのカメラによって同時的な画像を記録する。カメラの相対的な配置は一般に知られており、固定されている。したがって、対応形成によって３Ｄシーン内の点との距離を決定することができる。
【０００４】
独国特許第１１２００９００１７２７号明細書、独国特許出願公開第１０２０１４００９５２２号明細書、および独国特許出願公開第１０２０１３２２４５０２明細書により、画像を処理し、対応を計算する方法が公知であり、この場合には、異なる画像における画素の対応が形成される。最初の２つの参考文献はオプティカルフローに関するものであるが、最後に挙げた参考文献はステレオカメラの画像に関するものである。
【発明の概要】
【０００５】
行列の行列要素と比較行列の比較行列要素との間の割当てを決定するための本発明による方法は、対応テーブルのテーブルフィールドに行列の行列要素の位置を書き込むための書き込みプロセスを実施する第１のステップを含む。書込みプロセスは行列の多数の行列要素に対して実施される。さらなるステップでは、所定のオフセット後に、対応テーブルのテーブルフィールドを読み出し、テーブルフィールドに格納された行列の行列要素の位置を決定する読出しプロセスが実施される。さらなるステップでは、読み出されたテーブルフィールドの位置および比較行列の比較行列要素の現在位置から割当てを行う。書込みプロセスは、行列の行列要素の特性を決定するステップと、行列要素からアクセス特性を決定するステップと、アクセス特性から対応テーブルのテーブルフィールドを決定するステップと、行列の現在の行列要素の位置を決定されたテーブルフィールドに書き込むステップとを含む。テーブルフィールドを読み出すための読出しプロセスは、比較行列の比較行列要素の特性を読み出すステップと、比較行列要素からアクセス特性を決定するステップとを含む。さらに、読出しプロセスは、比較行列要素のアクセス特性から対応テーブルのテーブルフィールドを決定するステップと、決定されたテーブルフィールドから格納されている行列要素の位置を読み出すステップとを含む。したがって、比較行列の比較行列要素の特性の読出し、すなわち読出しプロセスは、好ましくは行列の多数の行列要素が処理された場合、すなわち例えば位置がテーブルに書き込まれた場合にはじめて開始することができる。
【０００６】
このようにして、極めて簡単で極めて効率的な対応形成が行われる。
【０００７】
行列の行列要素の特性の決定は、読出しによって、または処理もしくは方法が実施される場合に、いわゆる「オンザフライ」方法として時間制御式に行うことができることは当業者には明らかである。時間に依存した決定は、好ましくは画像処理時に行われる。特性は、特性が必要とされる場合、または必要とされる直前にはじめて形成することができ、例えば特性がピクセルの周辺から決定された場合またはピクセルもしくは画素の周りの局所的な環境を記述する場合に形成することができる。行列は完全に占有されている必要はなく、ブランクを有してもよいし、または部分的にのみ存在してもよい。例えば、行列要素が画素またはピクセルを表す場合には、部分的に占有された行列が提供されていてもよい。
【０００８】
本発明は、行列の形式の画像データや画像の処理に適用することができるだけでなく、多様な種類の対応を効率的に決定することができる汎用的なツールである。例えば、文字列をテキストで認識することができ、適切な対応を決定することができる。使用される行列は、デカルト座標による行列に制限されておらず、他の行列形状、例えば六角格子も含む。
【０００９】
従属請求項は、本発明の好ましい実施形態を示す。
【００１０】
さらなるステップにおいて、行列要素と比較行列要素との間で行われた割当てから結果行列が形成される場合、有利である。このようにして、割当てまたは対応を容易に処理することができる。
【００１１】
同様に、行列要素および比較行列要素の位置がそれぞれ座標によって指定される場合には、有利である。このようにして、それぞれの要素の一義的な位置を定めることができる。座標は、個別に、またはベクトルの形で格納することができ、２次元行列および画像の場合には、Ｘ座標およびＹ座標における位置が指定されていてもよい。六角格子も可能である。
【００１２】
第１の行列が第１の画像であり、比較行列が第２の画像であることも有利である。行列要素は、有利には、第１の画像内の画素またはピクセルであり、比較行列要素は、第２の画像内の画素またはピクセルである。この場合、第１の画像は第２の画像に対して時間的にずらされてもよく、または第１の画像は第１のカメラの画像を表してもよく、第２の画像は同じ時点の第２のカメラの画像を表してもよい。このようにして、画素の動きを検出するか、または立体評価によって３Ｄシーンにおける画素との距離を計算することができる。
【００１３】
画像を処理する場合に、オプティカルフローとして割当てを用いることは有利である。この場合に画像間の移動が決定される。
【００１４】
特性が、行列要素または比較行列要素の周りの環境を記述する場合にも有利である。したがって、特性は、画像座標または画像のピクセルの局所的な環境を表すか、または行列の要素の周りの局所的な環境を表す。一般には、画像座標の周りの円盤状または長方形の周辺範囲が使用され、特性は、例えば、グレースケール値またはカラースケール値から形成されていてもよい。理想的には、特性は、全ての行列における同じ外観の環境が同一の特性をもたらすように構成されている。すなわち、画像処理の場合には画像座標の周りの同じ環境は同一の特性をもたらす。特性を形成する方法は当業者に周知である。
【００１５】
行列要素の特性または比較行列要素の特性からアクセス特性を形成することも同様に有利である。最も単純な場合、特性とアクセス特性とは同じである。アクセス特性を決定するために、行列要素（画素）の特性全体、この特性の一部、またはいくつかの行列要素もしくは比較行列要素の特性を使用することができる。特性の値範囲がテーブルのサイズに対応する場合、有利であり得る。この場合、特性は、アクセス特性として直接に使用することができ、対応テーブルの適切なテーブルフィールドのアドレスを指定することができる。したがって、特性の１６ビットのワード幅では、０から２１６−１までの値範囲は、長さ６５，５３６の対応テーブルと直接に比較可能である。
【００１６】
アクセス特性は、対応テーブルのテーブルフィールドのアドレスを記述することができる。特性の値範囲がテーブルの大きさもしくは長さ、すなわちテーブルフィールドの数よりも大きい場合には、いくつかの可能性が提供される。例えば、特性の一部のみをテーブルアドレスとして使用することができる。残りの部分は廃棄されるか、または、例えば属性の形で対応テーブルに格納されていてもよい追加情報として使用される。大きすぎる特性を関数によってより長さの短い特性にマッピングすることも可能であり、マッピングは損失を伴っていてもよい。
【００１７】
特性の値範囲が小さすぎる場合には特性は一義的ではなく、このことは一義的ではない対応形成をもたらす場合がある。したがって、「短い」語長を有するいくつかの特性を隣接する行列要素、または画像の場合には隣接する画素、または遠く離れた行列要素によって、より長い語長を有する特性として連結すること（結びつけること）が好ましい。
【００１８】
テーブルフィールドの数、すなわち、対応テーブルの長さは、割当てまたは対応を決定することが望ましい行列内の特性の数よりも十分に少なくてもよいし、または明らかに少なくてもよい。この場合、同じ画像内のアクセス特性は一般に繰り返し発生するので、アクセス特性は一義的ではない。
【００１９】
有利には、少なくとも１つの無効なアクセス特性、すなわち、割当てまたは対応を形成するために使用されることが望ましくないアクセス特性が設けられている。このようにして、有利には、割当てが望ましくない、または割当てが成功しないことが予見できる、行列または画像内の箇所をマークすることが可能である。画像の場合には、例えば、画像センサが飽和状態に達した完全に白い平面であってもよい。他の例は、センサのノイズとは異なる重要なテクスチャが存在しない平面、または重要ではないとマークされた平面、例えば、フロントガラスの後方に取り付けられたカメラによって検出された（重要でない）ボンネットの範囲である。
【００２０】
対応テーブルのテーブルフィールドが、行列要素の位置に加えてさらなる属性を含む場合、有利である。例えば、これらの追加情報は、割当てを形成する場合の多義性を決定し、好ましい割当てまたは好ましい対応を確定するために役立つ。特徴の値範囲が大きすぎる場合にはこれらの追加情報を利用することも可能であり、または形成された割当てに基づいて、特定の属性を１つの行列から別の行列へ、または１つの画像から別の画像へさらに移動することも可能である。例えば、画像の場合、これは、測定されたサイズ、物体距離、または行列要素もしくは画素の特定の分類であってもよい。
【００２１】
有利には、行列および比較行列の処理は順次に行われる。したがって、個々の行列要素は次々に処理される。例えば、行列要素の行毎の処理を行ってもよく、すなわち、書込みプロセスまたは読出しプロセスが、最初に第１行の第１の行列要素に適用され、次に隣接する要素に適用される。（順次）処理は、好ましくは、所定数の行列要素にわたって、好ましくは、行列の全ての行列要素にわたって行われる。好ましくは、書込みプロセスの回数と読出しプロセスの回数は同じである。
【００２２】
書込みプロセスと読出しプロセスとの間のオフセットが固定されているか、または可変である場合、有利である。有利には、オフセットは、読出しプロセスが書込みプロセスに続くように選択されているが、この原則を反転することも可能である。固定されたオフセットは、対応もしくは割当てとして見つけるべき最大の差を確定できるという利点を有する。可変のオフセットは、オフセットによって決定される検索範囲が同様に可変であり、例えば、画像処理の特異性を考慮に入れることができるという利点を有する。例えば、カメラシステムでは、画像内の点がより下方に位置すればするほど、割当てとして使用されるオプティカルフローベクトル、すなわち割当てベクトルはそれだけ長くなる。可変のオフセットによってこのような特異性を簡単に考慮することができるが、書込みプロセスおよび読出しプロセスを必要に応じて適合させる必要がある。例えば、オフセットが可変である場合には所定の時間にわたっていずれか１つのプロセスを中断することが有利なこともある。
【００２３】
行列内に検索フィールドを設けることも有利である。検索フィールドは、書込みプロセスによって既に処理された、例えばテーブルに入力された多数の行列要素を含む。検索フィールドは、有利には書込みプロセスの現在の行列要素、すなわち最後に書き込まれた行列要素を含むこともできる。行列要素と比較行列要素との割当ては、検索フィールド内に配置された行列要素に対してのみ行われる。このようにして行列と比較行列との間の割当てのための検索範囲を、例えば多義性を回避するために制限することができる。検索フィールドは、長方形または正方形ののみならず、円、楕円、多角形などの他の形状を有することもできる。
【００２４】
割当てがベクトルである場合も有利である。好ましくは、割当てベクトルは、テーブルフィールドから読み出された位置および現在の比較行列要素の位置から計算される。特に好ましくは、計算は差に基づいて行われる。割当てベクトルは、画像処理方法における移動ベクトルまたはオプティカルフローベクトルと理解することができる。割当てベクトルは簡単に処理することができる。
【００２５】
さらに、対応テーブルのリセットを実施し、既存の値を削除または上書きすることが有利である。リセットは、１回のリセット（初期化）として、例えば対応テーブル全体に対して行うことができる。リセットは、好ましくは書込みプロセスの前に行われる。代替的に、好ましくは、リセットは書込みプロセスまたは読出しプロセスと並行して実施することができる連続プロセスとして実行することもできる。すなわち、記憶されたそれぞれの位置は、好ましくは画像処理毎に数回処理され、必要に応じて削除される。したがって、リセット機能の「処理量」が得られる。対応テーブルの連続的なリセットは、好ましくは、画像処理毎に少なくとも２回行われる。なぜならば、一般に、まだ削除されてはならない、対応するかもしれないテーブルエントリが存在するからである。これらの「残り」は、好ましくは、時間遅延された後の処理時に削除される。このようにして、対応形成にもはや適していないテーブルフィールド内の古い値が廃棄または削除される。
【００２６】
時間をずらした処理のためのオフセットは、画像高さもしくは行列高さのせいぜい半分に対応ように選択されることが有利である。連続的なリセットの場合、例えばテーブルに記憶された全ての位置は定められた順序（例えば、昇順アドレス）で処理される（必要であれば削除される）。全てのアドレスが処理されると、再び同じ順序で始めから開始される。少なくとも２つのこのようなリセット処理は、画像処理（またはサブ行列処理）毎に行われ、リセットは、画像変化にかかわらず行うことができる。
【００２７】
検索フィールドが存在している場合には、検索範囲外に位置しており、したがって、読出しプロセスが適切な行列要素を既に処理してしまったために、割当て形成もしくは対応形成に使用されなくなったテーブル内の既に古くなった値が上書きされる。画像ペア毎もしくは行列ペア毎に適切に時間遅延された２つのリセット処理を行うことも有利であり、これにより連続リセットモードで正しい完全な処理が保証され、次の行列ペアを処理する場合に誤った対応形成または割当て形成が起こり得る前に、対応テーブル内の古いエントリが早期に削除されることが確保される。
【００２８】
行列の行列要素と比較行列の比較行列要素との間の割当てを決定するための装置は、本発明による方法を実施するように構成されており、有利であり、本発明による方法のすべての利点を有する。
【００２９】
次に添付の図面を参照して本発明の実施の形態を詳細に説明する。
【図面の簡単な説明】
【００３０】
【図１】第１の画像および第２の画像との対応形成を示す概略図である。
【発明を実施するための形態】
【００３１】
図１は、第１の画像１０２である行列行列１０１を示す。さらに、第２の画像２０２である比較行列行列２０１が示されている。第１の画像１０２および第２０１の画像２０２は、異なる時点の撮影に対応している。第１の行列１０１は、複数の行列要素１０３を含む。比較行列２０１は、複数の比較行列要素２０３を有する。
【００３２】
図１は、第１の画像１０２、第２の画像２０２、および対応テーブル３００が示されている現在の画像、ならびに割当てを格納および記憶することができる結果行列４００を示している。行列要素１０３、２０３は、それぞれ、ここに示される簡略化された形態のアクセス特性１１０に対応する特性を含む。アクセス特性は、好ましくは、数として符号化され、テーブルフィールド３０１のアドレスを指定する。テーブルフィールド３０１は、テーブル３００内の行に対応する。ここに示すテーブル３００は、４つの列３０２〜３０５を有し、列３０２はテーブルフィールドのアドレスを指定する。この列３０２は、通常は暗示的であり、明示的ではない。列３０２は、一般にメモリスペースを必要とせず、明確化のためだけにここ挙げられている。列３０３および３０４は位置を記述し、列３０３は、行列要素または画素の座標または位置のＸ値を反映し、列３０４は、Ｙ値を反映している。列３０５は、対応テーブル３００内の他の属性を記憶することを可能にする。
【００３３】
図１では、本発明による方法にしたがった書込みプロセスは、図１０２において既に進んでいる。書込みプロセスは、行列要素１０３の一部を処理し、現在行列要素１０４に到達している。処理された行列要素１０３は、図１では斜線で示されている。行列要素１０４は、アクセス特性１１０、この場合はアドレス１７である数１７を有する。したがって、書込みプロセスは、行列要素１０４の座標または位置を対応テーブルの１７番目のテーブル行３０１に書き込み、列３０３および３０４のそれぞれの箇所にＸ座標およびＹ座標、この場合にはＸ位置２３４およびＹ位置１１３が入力される。
【００３４】
画像１０２と画像２０２との比較は、画像２０２で実施される読取り処理が、画像１０２で実施される書込みプロセスに続くことを示している。画像１０２における書込みプロセスと画像２０２における読出しプロセスとの間のオフセットは、１行およびいくつかの列であるが、これは例示のためにのみ選択されている。フルＨＤ画像を処理する場合、オフセットは、例えば３２行および６４画像列と、はるかに大きくて選択されていてもよい。書込みプロセスは、このオフセットの分だけ読出しプロセスに先行する。
【００３５】
行列１０１および比較行列２０１内の同一のアクセス特性１１０が互いに結び付けられる、対応形成または割当て形成の処理は、左上の行列要素１０３から始まって、好ましくは順次に、例えば行毎に行われる。処理は、列毎に、または他の順序で行うこともできる。好ましくは、順序は、画像１０２および画像２０２の両方において同じように選択されるが、同時に開始されるのではなく、時間的オフセットまたは局所的オフセットとみなすことができるオフセットを有するように選択される。
【００３６】
書込みプロセスに対して読出しプロセスが時間的にずらして実施されることにより、読出しプロセスはまだ開始されていないうちに、書き込まれるだけのフェーズが最初に行われる。この後に両方のプロセスが行われるフェーズが続く。行列１０１内の最後の行列要素１０３に到達した後に書込みプロセスは停止し、比較行列２０１内の読出しプロセスはまだ継続される。
【００３７】
図１から分かるように、現在の位置での書込みプロセスは、行列要素１０４を対応テーブルに書き込む。同様に値「１７」を有するアクセス特性１１０を備える別の行列要素１０５が、１７番目の行に既にあらかじめ書き込まれている。位置、または必要に応じて追加情報などの既存のエントリが、現在の書込みプロセスで上書きされる。同様に、書込みプロセスの過程で、例示的な行列要素１０６について、値「２１」を有するアクセス特性１１０が、アドレス「２１」を有する対応テーブル３００の行３０１に既に書き込まれている。
【００３８】
現在の比較行列要素２０４を読み出す時間的にずらされた読出しプロセスは、この要素２０４に対して値「２１」を有するアクセス特性１１０を決定する。本発明による方法では、対応テーブル３００の２１番目の行で、列３０３、３０４から座標値が読み出される。テーブルフィールドは、値「２１」を有する同じアクセス特性を備える行列要素１０６を参照する。ここで、比較行列要素２０４と行列要素１０６との間の割当てが形成され、２つの要素１０６，２０４の座標が互いに比較される。有利には、差の形成が行われる。読出しプロセスは、対応テーブル３００のアドレス２１から、書込みプロセスが行列要素１０６で行われているときに書込みプロセスによってあらかじめそこに入力された、ｘｔａｂ２２８、ｙｔａｂ＝１１１を有する行列特性１０６の位置を読み出す。本発明による方法では、有利には現在の比較行列要素２０４の位置と読み出された行列要素１０６の位置との間の差が形成され、割当ては、値：
ｕ＝ｘｒ−Ｘｔａｂ＝２３０−２２８＝２
ｖ＝ｙｒ−ｙｔａｂ＝１１２−１１１−１
を獲得し、ｘｒ、ｙｒは、比較行列要素２０４の現在の位置を示す。次に本方法のさらなるステップにおいて、読出しプロセスの結果、すなわち行列要素１０６の位置が検索フィールド１２０内にあるかどうかがチェックされる。この場合、そうであれば、割当てベクトルとして提供されている決定された割当てｕ、ｖが結果行列４００に入力される。検索フィールド１２０は、常に、書込みプロセスの画像１０２または行列１０１に関係している。明確化のために、比較行列２０１または第２の画像２０２にもう一度示されている。
【００３９】
検索フィールド１２０は、好ましくは、書込みプロセスによって既に処理されており、位置がテーブルに書き込まれ、読出しプロセスによって読み出すことができる行列要素１０３のみを含むように選択されている。したがって、検索フィールドは、行列１０１の斜線で示した領域に位置していなければならない。図１は、上記の基準を満たすのにちょうど十分な大きい先行である場合を示す。書込みプロセスにおいて現在処理されている行列要素１０４の位置は、ちょうど検索フィールド１２０内にある。したがって、左から右へ順次に行毎に処理する場合、書込みプロセスによって現在処理されるべき行列要素１０４は検索フィールド１２０の右下隅に位置する。現在処理されている行列要素１０４が、例えば検索フィールド１２０の右側に位置するか、または次の行に位置するように先行はより大きくてもよい。
【００４０】
検索フィールド１２０は、比較行列要素２０４に関して非対称であることも可能であり、この場合についても該当する。現在の基準位置、すなわち、現在処理されている比較行列要素２０４が、検索フィールドの外部に位置することも可能である。しかしながら、検索フィールド１２０に位置する行列要素１０３の位置が対応テーブル３００に既に記入されており、読取りプロセスが対応テーブルにアクセスする前に書き込まれるところまで書込みプロセスが進行していることが重要である。したがって、検索フィールド１２０は、既に処理された行列要素１０３が配置されている、斜線により示した行列１０１の範囲内に常に完全に位置している必要がある。
【図１】
2019537181.tif 000003
【国際調査報告】
2019537181.tif 000004
2019537181.tif 000005
2019537181.tif 000006
2019537181.tif 000007
2019537181.tif 000008
2019537181.tif 000009