(57)【特許請求の範囲】
【請求項１】
データ項目メモリと、空間における座標によりアドレス指定が可能な長さメモリとを利用する、前記座標を有するデータ項目のメモリシステムへの書き込み処理及び検索対象のデータ項目の前記メモリシステムからの読み出し処理方法であって、
前記書き込み処理は、座標系列の各座標に対して、
関連付けされたデータ項目を受け取るステップと、
前記関連付けされたデータ項目から、該データ項目の前記データ項目メモリへの格納に要するデータ長さを示す前記データ項目の長さコードを決定し、前記座標によりアドレス指定された前記長さメモリに前記長さコードを書き込むステップと、
前記長さコードが長さゼロを示さない場合、前記座標系列の前記座標に先行するすべての座標の長さコードの累積に対応する前記データ項目メモリのアドレスに前記関連付けられたデータ項目を書き込むステップとを有し、
前記読み出し処理は、前記検索対象のデータ項目に関連付けられている与えられた座標に対して、
前記与えられた座標によりアドレス指定された前記長さメモリからアドレス指定された長さコードを読み出すステップと、
前記アドレス指定された長さコードにより示される長さがゼロより大きい場合には、前記座標系列の前記与えられた座標に先行する座標の長さコードを読み出し、該長さコードにより指示される長さの和を決定し、前記データ項目メモリから前記和により示される前記検索対象のデータ項目を読み出すステップと、
を有する方法において、
前記書き込み処理は、
各座標に対して、各カテゴリにおける複数の座標が前記座標系列において連続するように前記空間を複数の座標カテゴリに分割する所定の座標分類において、前記座標が属するカテゴリを決定するステップと、
各カテゴリに対して、前記データ項目メモリに格納され、前記カテゴリの座標に関連付けされているデータ項目群に対する参照値を参照メモリに格納するステップとを有し、
前記読み出し処理は、
前記与えられた座標が属するカテゴリを決定するステップと、
前記カテゴリの表示によりアドレス指定される前記参照メモリから参照値を読み出すステップと、
前記カテゴリの座標の長さコードに限定された前記和と前記参照値との合成により指示される前記データ項目メモリから前記検索対象のデータ項目を読み出すステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
前記長さメモリは、各ブロックが前記座標系列において互いに連続する複数の座標によりアドレス指定される２以上の長さコードを有する、複数のブロック単位でのアクセスが可能であり、
前記和の決定は、１つのブロックの読み出しに基づく２以上の長さの部分和の決定に関することを特徴とする方法。
【請求項３】
請求項１又は２記載の方法であって、各カテゴリのすべての座標は所定の部分に関して同一であることを特徴とする方法。
【請求項４】
請求項１乃至３何れか一項記載の方法であって、前記空間と前記座標は、少なくとも３次元であることを特徴とする方法。
【請求項５】
請求項１乃至４何れか一項記載の方法であって、前記データ項目が複数の標準値の１つを有する場合、長さゼロを示す長さコードが選択され、前記場合における前記長さコードは前記データ項目の該当する標準値を示すことを特徴とする方法。
【請求項６】
請求項１乃至５何れか一項記載のメモリシステムへのデータ項目の書き込み処理方法。
【請求項７】
請求項１乃至５何れか一項記載のメモリシステムからのデータ項目の読み出し処理方法。
【請求項８】
空間における座標を有するデータ項目を格納するよう構成されたメモリシステムと、
前記メモリシステムに結合された書き込み手段と、
前記メモリシステムに結合された読み出し手段と、
を有する装置であって、
前記書き込み手段は、
座標に関連付けされたデータ項目を受け取る入力と、
前記データ項目から、該データ項目をデータ項目メモリに格納するのに要するデータ長を示す長さコードを決定するよう構成される長さ決定手段と、
長さメモリと、
前記長さメモリの前記座標に対応するアドレスに前記長さコードを書き込む長さ書き込み手段と、
所定の座標系列の前記座標に先行するすべての座標の長さコードの累積に対応する前記データ項目メモリのアドレスに前記データ項目を書き込むデータ項目書き込み手段とを有し、
前記読み出し手段は、
検索対象のデータ項目が関連付けされている与えられた座標を受け取る入力と、
前記アドレス指定された前記長さメモリから前記検索対象の長さコードを読み出す長さ読み出し手段と、
前記データ項目メモリから前記検索対象のデータ項目を読み出すデータ項目読み出し手段とを有し、
前記データ項目読み出し手段は、
前記座標系列の前記与えられた座標に先行する座標の長さコードにより示される長さの和を決定する和決定手段と、前記データ項目メモリから前記和により指示された前記検索対象のデータ項目を読み出すよう構成される指示手段とを有する装置において、
前記メモリシステムは、
各カテゴリにおける複数の座標が前記座標系列において連続するように前記空間を複数の座標カテゴリに分割する所定の座標分類において、前記データ項目が関連付けされている前記座標を分類する分類手段と、
参照メモリと、
前記データ項目メモリに格納され、前記カテゴリの座標に関連付けされているデータ項目群に対する参照値を前記参照メモリに書き込む参照書き込み手段と、
前記与えられた座標のカテゴリの表示によりアドレス指定された前記参照メモリから参照値を読み出す参照読み出し手段とを有し、
前記指示手段は、前記和と前記参照値との合成により指示された前記データ項目を前記データ項目メモリから読み出すよう構成されることを特徴とする装置。
【請求項９】
請求項８記載の装置であって、
前記長さメモリは、各ブロックが前記座標系列において互いに連続する複数の座標によりアドレス指定される２以上の長さコードを有する、複数のブロック単位でのアクセスが可能であり、
前記和決定手段は、１つのブロックの読み出しに基づく前記和の決定のため、２以上の長さを合計するよう構成されることを特徴とする装置。
【請求項１０】
請求項８又は９記載の装置であって、各カテゴリのすべての座標は所定の部分に関して同一であることを特徴とする装置。
【請求項１１】
請求項８乃至１０何れか一項記載の装置であって、前記空間と前記座標は、少なくとも３次元であることを特徴とする装置。
【請求項１２】
請求項８乃至１１何れか一項記載の書き込み手段を有するメモリシステム。
【請求項１３】
請求項８乃至１１何れか一項記載の読み出し手段を有するメモリシステム。
【発明の詳細な説明】
本発明は、メモリシステムにおいて、関連した空間の座標の組を有する各データ項目を書き込み、読み出す方法に係る。本発明は、かかるデータ項目をメモリシステムに書き込む方法と、メモリシステムから読み出す方法にも関する。
更に、本発明は、かかるデータ項目を読み出し、書き込むために適するメモリシステムからなる装置に係る。本発明は、かかるデータ項目の読み出しに適する装置用の書き込み手段及び読み出し手段からなるメモリ装置にも関する。
例えば、画像処理技術において、座標（ｘ，ｙ）の組によって示された格納場所と関係したデータ項目を記憶することが屡々必要とされる。データ項目は、例えば、カメラ画像のディジタル化された光強度、当該座標（ｘ，ｙ）の領域で認識されたパターンを表わす色ベクトル又はベクトル、或いは、当該格納場所と関係した補足データである。
従来、関係したデータ項目の座標の組によるアドレス指定が可能なデータ項目メモリが上記目的のため使用されている。記憶の際に、データ項目が、関係したデータ項目の座標の組をそのアドレスとして有するメモリ格納場所に格納される。読み出し時に、上記格納場所は関係した座標の組によってアドレス指定される。
かかるデータ項目メモリは大きい記憶空間を必要とし、特に、各データ項目のビット数が多くなると共に、空間の寸法が大きくなる。一例として、３次元断層写真を供給するＸ線スキャナから発生する医用“画像”処理において、例えば、データ項目に必要とされるメモリ空間は、２次元画像が関係している場合よりも実質的に大きく
本発明の目的は、特に、データ項目を格納及び／又は読み出すために必要とされる平均時間を極端に増加させることなく、より小さい記憶空間しか必要としない書き込みと読み出しの方法及び装置を提供することである。
本発明は、データ項目メモリと、関連した座標の組によってアドレス指定が可能な長さメモリとを利用し、空間内の上記関連した座標の組を有する各データ項目をメモリシステムに書き込み、検索された上記データ項目を上記メモリシステムから読み出す方法であって、
関連した座標の組の各系列に対し、書き込みのための以下の段階：
−関連したデータ項目を受ける段階と、
−上記関連したデータ項目から、上記データ項目を上記データ項目メモリに格納するため必要とされるデータ長を示す夫々の長さコード決定し、上記夫々のデータ項目を、該関連した座標の組によってアドレス指定された上記長さメモリに書き込む段階と、
−上記夫々の長さコードが長さゼロを示すまで、上記系列内の該関連した座標の組に先行する全ての座標の組の長さコードの累積に対応する夫々のアドレスにある上記データ項目メモリに、上記関連したデータ項目を書き込む段階とを有し、
上記検索されたデータ項目が関連付けられた与えられた座標の組に対し、読み出しのための以下の段階：
−上記与えられた座標の組によってアドレス指定された上記長さメモリからアドレス指定された長さコードを読み出し、上記アドレス指定された長さコードによって示された上記長さがゼロよりも大きい場合に、
−上記系列内の該関連した座標の組に先行する上記関連した座標の組の上記長さコードを読み出し、これにより示された上記長さの和を決定し、
−上記和により索引が付けられた上記検索されたデータ項目を上記データ項目メモリから読み出す段階とを有する方法を提供する。
本発明は、更に、関連する空間内の座標の組を有する各データ項目を格納するため配置されたメモリシステムと、上記メモリシステムに接続された書き込み手段及び読み出し手段とからなる装置であって、
上記書き込み手段は、
−関連する座標の組と関連したデータ項目を受ける入力と、
−上記データ項目から、上記データ項目を上記データ項目メモリに格納するため必要とされるデータ長を示す長さコードを決定するため配置された長さ決定手段と、
−長さメモリと、
−上記長さコードを当該座標の組に対応するアドレスで上記長さメモリに書き込む長さ書き込み手段と、
−上記データ項目を、所定の座標の系列内の当該関連した座標の組に先行する全ての関連した座標の組の上記長さコードの累積に対応する固有のアドレスで上記データ項目メモリに書き込むデータ項目書き込み手段と、
−検索されたデータ項目が関連付けられた与えられた座標の組を受ける入力と、
−上記与えられた座標の組によってアドレス指定された上記長さメモリから、検索された長さコードを読み出す長さ読み出し手段と、
−上記系列内で上記与えられた座標の組に先行する上記関連した座標の組の長さコードによって示された長さの和を決定する和決定手段と、
上記データ項目メモリから上記和によって索引が付けられた上記検索されたデータ項目を読み出すため配置された索引手段とを有し、上記データ項目メモリから上記検索されたデータ項目を読み出すデータ項目読み出し手段とからなる装置を提供する。
本発明は、殆どの応用において、情報を含まない、又は、格納される必要のない標準的な値を有するデータ項目が、大多数の座標の組に関連付けられているとの認識に基づいている。データ項目を記憶する必要があるならば、所定の長さのデータ項目メモリ、又は、制限された数の実現可能な長さの中の一つが必要とされる。従って、長さコードは、１ビット又は少数のビットしか必要としない。その結果として、長さメモリは比較的小さくてもよい。少数のデータ項目、即ち、情報を含み、又は、標準的な値を持たないデータ項目しか記憶する必要がないので、同様に、データ項目メモリが比較的小さくても構わない。
読み出しの際に、通常、上記長さメモリだけを読み出すことが必要である。座標の組は所望の長さコードを直接アドレス指定するので、長さメモリだけの読み出しは非常に迅速に行われる。特に、これによれば、データ項目が座標を用いてアドレス指定可能であるよう格納されたメモリ内のデータ項目の検索よりも多くの時間が必要とされることはない。データ項目メモリの参照は、通常、格納されたデータの中から、与えられた座標の組と関係したデータを見つける必要があるので、より多くの時間を必要とする。しかし、データ項目メモリの参照が必要とされるのは、例外的な場合に限られるので、読み出しに要する平均時間は、僅かしか増加しない。
しかし、上記方法は、データ項目メモリ内に空間が必要とされないデータ項目が関連付けられている座標の組が、座標の組の中の低いパーセンテージ（例えば、２％）しかないとき、メモリ占有の制限に関して利点がある。
本発明による別の方法は、書き込みのための以下の段階：
−各座標の組に対し、上記空間を該系列内の夫々の連結を構成する座標の組のカテゴリーに再分する上記座標の組の所定の分類の範囲内で、上記座標の組が属する分類を決定する段階と、
−上記データ項目メモリに格納され、当該カテゴリー内の座標の組と関連した上記データ項目の夫々の部分組に対する夫々の基準を、各カテゴリー毎に基準メモリに格納する段階とを更に有し、
読み出しのための以下の段階：
−上記与えられた座標の組が属するカテゴリーであって、該和が当該カテゴリー内の上記関連した座標の組の長さコードに制限されたカテゴリーを決定する段階と、
−上記カテゴリーの指示によってアドレス指定された上記基準メモリから基準を読み出す段階と、
−上記和と上記基準の組み合わせによって索引が付けられた上記データ項目メモリから上記検索されたデータ項目を読み出す段階とを更に有する。
読み出しの際に、関連した座標の組からカウントすれば十分であるので、カウントをより迅速に行うことが可能である。基準メモリの要求は、カテゴリー毎に１個のメモリ格納場所しか含まないので、かなり少ないまま維持することが可能である。簡単に実現可能な分類方法は、各座標の組の一部分を取り出し、この一部分が同一である座標の組を全く同一のカテゴリーに割り当てる段階からなる。例えば、座標の組（ｘ，ｙ，ｚ）に対し、同一の（ｙ，ｚ）を有する全ての組を一つのカテゴリーに割り当てることができる。一実施例において、共通部分は、１個の座標を除く全ての座標に関係する。従って、カウントは最小の時間間隔しか必要としないが、基準メモリはかなり大きくなる。他の実施例の場合、共通部分は、一つの座標にしか関係しないので；基準メモリは比較的小さくなるが、カウントにはより多くの時間が必要とされる。座標の順序でデータ項目が受けられる場合、共通部分は、好ましくは、受信の際に、最も緩やかに変化する座標の部分に関係する。
本発明のデータ項目を読み出す方法の一つのバージョンによれば、長さメモリは、系列内で直接的に相互に後に続く座標の組によってアドレス指定された少なくとも２個の長さコードを含む各ブロックでアクセス可能であり、和の決定は、１ブロックの読み出しに基づく少なくとも２個の長さの部分和の決定を含む。かくして、合計の際に和データが長さメモリから読み出されるべき回数は、合計演算のため読み出されるべき長さコードの数よりも少ない。その結果として、長さコードの読み出しは、かなり少ない量の時間しか必要としないので、合計の実行が加速される。
書き込みと読み出しは、好ましくは、組み合わされた形式で行われる。上記方法は、特に、例えば、Ｘ線スキャナ、磁気共鳴画像スキャナ等の医用画像処理において、屡々発生するような３次元、又は、より高次元の空間の座標の組と関連したデータ項目を処理する際に利点が得られる。
更に、本発明は、上記方法を実行するため設けられた装置に関係する。
本発明の上記及び他の面は、以下に説明される添付図面を参照して明らかになり、かつ、解明される。
図面に関して：
図１は本発明の装置の一実施例を表わし、
図２ａはデータ項目を書き込む本発明の方法の一つのバージョンを表わすフローチャートであり、
図２ｂはデータ項目を書き込む本発明の方法の一つのバージョンを表わす別のフローチャートであり、
図３は本発明の装置の一実施例を表わし、
図４はデータ項目を読み出す本発明の一つのバージョンのフローチャートである。
図１には本発明によるデータ項目を書き込む装置の一実施例が表わされている。上記装置は、処理ユニット２２の入力に接続された画像源２０、例えば、Ｘ線スキャナからなる。処理ユニット２２は、座標出力２２ａと、データ項目出力２２ｂとからなる。データ項目出力２２ｂは、データ項目メモリＤＭ２６２のデータ入力と、検出器２４とに接続されている。検出器２４の出力は、フラグメモリＦ２６０と呼ばれる長さメモリＦ２６０と、基準（以下、本明細書における「基準」とは、「参照」または「参照値」を意味するものとする。）カウンタ２６４とに接続されている。基準カウンタ２６４は、データ項目メモリＤＭ２６２のアドレス入力と、基準メモリＰ２６６のデータ入力とに接続された標準出力を有する。処理ユニット２２の座標出力２２ｂは、フラグメモリＦ２６０のアドレス入力に接続され、かつ、分類ユニット２８を介して、基準メモリＰ２６６のアドレス入力に接続されている。
図１に示された装置の動作を説明する前に、図２ａを参照して本発明の方法のより一般的な説明を行う。
図２ａには、データ項目をメモリシステムに書き込む本発明の方法の１バージョンのフローチャートが示されている。このフローチャートは、基準格納用の基準メモリＰ２６６と、フラグ格納用のフラグメモリＦ２６０と、データ項目格納用のデータメモリＤＭ２６２とを利用する。例えば、このフローチャートは、座標の組（ｘ，ｙ）と、書き込まれたデータ項目Ｄとを利用し、データ項目は、ｘ座標が急速に増加する座標値の上昇する順序で得られる場合を想定する。座標（ｘ，ｙ）は、１からｘｍａｘ及びｙｍａｘに夫々増加する。
上記フローチャートには、座標の中の第１の座標ｙが、初期値０を有し、基準“ｐ”が初期値（例えば、１）を有する開始点９がある。開始点９からステップ１０に達する。そこで、第１の座標ｙの値がインクリメントされ、もう一方の座標ｘが０に初期化され、基準“ｐ”が、第１の座標ｙによってアドレス指定された格納場所Ｐ（ｙ）で基準メモリＰ２６６に書き込まれる。
フローチャートの次のステップはステップ１２である。そこで、第２の座標ｘがインクリメントされ、座標の組（ｘ，ｙ）と関連したデータ項目Ｄが書き込まれる。続いて、データ項目メモリ内にデータ項目Ｄを格納するため必要とされるメモリ空間の長さＬ（Ｄ）が決定される。データ項目に依存して、この長さを、例えば、ゼロ又は４０バイトとしてもよい。
パターン認識の場合に、例えば、座標の組を用いてパターンが認識されないならば、長さゼロが使用され、座標の組を用いてパターンが認識されたならば、明暗値、明暗値の微係数等のような４０バイトの情報が使用される。上記長さが取る値の数が制限されているとき、Ｌ（Ｄ）は、好ましくは、数値の直接的な２進数表現ではなく、実現可能な長さの間の選択である長さコード（長さが０又は４０バイトの上記例の場合、ビットの値０が、例えば、長さ０を表わし、ビットの値１が長さ４０を表わす１ビットの長さのコードで十分である）を構成する。
長さコードＬ（Ｄ）は、座標（ｘ，ｙ）によってアドレス指定された格納場所Ｆ（ｘ，ｙ）のフラグメモリＦ２６０に書き込まれる。
ステップ１４は、次のステップ１６の条件付き実行を提供する。長さコードＬ（Ｄ）によって、ゼロよりも大きいデータ項目Ｄの長さが得られることが示されたならば、データ項目Ｄは、基準ｐによって示された格納場所のデータメモリＤＭ２６２に書き込まれる。必要であれば、データ項目Ｄの関係した一部だけが書き込まれ、或いは、データ項目Ｄが書き込み中に補足的な情報によって補足される。
基準ｐは、次いで、上記データ項目に対し使用された長さだけインクリメントされる。書き込まれた全てのデータ項目Ｄが同じ長さを有する場合、データ項目メモリＤＭ２６２内のアドレスは、好ましくは、上記長さの単位で表現されるので；その場合、基準ｐは、１ずつインクリメントされる。
次に、ｘ座標がその最大値に達したかどうかがテストされる（ステップ１８）。最大値に達していない場合、上記方法は、座標ｘがインクリメントされ、かつ、データ項目Ｄが書き込まれるステップ１２から繰り返される。ｘ座標がその最大値に達した場合、ｙ座標がその最大値に達したかどうかがテストされる（ステップ１９）。最大値に達していない場合、上記方法は最初のステップ１０から繰り返される。
テスト１９によって、ｙ座標がその最大値に達したことが分かった場合に、上記方法の実行は終了する。フラグメモリＦ２６０は、座標の組（ｘ，ｙ）によってアドレス指定された夫々のメモリ格納場所に格納された各長さコードで充填される。当該格納場所に格納された長さコードは、当該格納場所（ｘ，ｙ）と関連したデータ項目のため使用されたメモリ空間の長さを示す。次に、データ項目メモリＤＭ２６２は、所定の座標の順序、即ち、ｙ座標が上昇する順序、及び、対応するｙ座標の場合には、ｘ座標が上昇する順序で、ゼロを上回る長さが得られるデータ項目を格納する。基準メモリＰ２６２は、たとえあるとしても、夫々のｙ座標に関連し、かつ、このｙ座標を有するデータ項目Ｄが格納されたデータ項目メモリＤＭ２６２内の第１の格納場所に関する基準を構成する格納場所に対する各基準を、データ項目メモリＤＭ２６２に格納する。
図２ｂは、データ項目をメモリシステムに書き込む本発明の方法の他の例の更なるフローチャートである。このフローチャートは、図２ａのステップ１２、１４を除いて、図２ａに示されたフローチャートと同じである。図２ｂにおいて、上記ステップはステップ１２ａ，１４ａによって置換されている。
相違点は、図２ａのフローチャートにおいて、データ項目Ｄをデータ項目メモリＤＭ２６２に書き込むかどうかがデータ項目Ｄの値によって決定される点である。データ項目Ｄが標準的な値Ｓを有するならば、データ項目Ｄは書き込まれない。
ステップ１２ａにおいて、データ項目Ｄが標準的な値Ｓを有するかどうかを示すフラグが、座標（ｘ，ｙ）によりアドレス指定された格納場所Ｆ（ｘ，ｙ）でフラグメモリＦ２６０に書き込まれる。
ステップ１４ａは、次のステップ１６の条件付き実行を提供する。データ項目Ｄが標準的な値Ｓを持たない場合、データ項目Ｄは、基準ｐによって示された格納場所のデータ項目メモリＤＭ２６２に書き込まれる。基準ｐは、次いで、インクリメントされる。
上記例は、データ項目が標準的な値Ｓを持つかどうかを排他的に示す２進数のフラグに基づいている。しかし、２進数のフラグの代わりに、３個以上の異なる値を想定し得るフラグを用いてもよい。従って、フラグは、複数の標準的な値の中からデータ項目の関係する値を示し、或いは、データ項目がデータ項目メモリＤＭ２６２に格納されたことを示す。例えば、２ビットのフラグは、例えば、値０を用いて、データ項目がデータ項目メモリＤＭ２６２に格納されたことを示し、値１、２及び３を用いて、データ項目が、第１、第２及び第３の標準的な値を夫々有することを示す。かかるフラグの使用は、フラグメモリＦ２６０に対しより大きい容量を必要とするが、データ項目メモリＤＭ２６２において利点が得られる。これは、データ項目が、通常、２個以上の制限された数の標準的な値の中の一つを有する場合に、特に有利である。
基本的に、標準的な値を持たないデータ項目だけがデータ項目メモリＤＭ２６２に書き込まれ；フラグメモリＦ２６０に書き込まれたフラグは、データ項目が標準的な値ではないことを示す。しかし、フラグは、特に、データ項目メモリＤＭ２６２内でデータ項目のため使用された長さを示すために機能する。従って、標準的な値のデータ項目がデータ項目メモリＤＭ２６２に書き込まれたときに、フラグメモリＦ２６０内の関連したフラグがその旨を示すならば、好ましく無くはない。標準的な値のデータ項目の書き込みが行われた座標の組が、標準的な値を持たないデータ項目に対する座標の組の数よりも少ない限り、装置の性能に殆ど悪影響を与えることがない。
図１に示された装置の動作中の効果は、図２のフローチャートに示された効果と一致する。データ項目Ｄ及び座標の組（ｘ，ｙ）は、アドレス指定の主要部を提供する処理ユニット２２によって形成される。データ項目に加えて、処理ユニットは、データ項目メモリＤＭ２６２内の適当な格納場所にデータ項目と共に格納されるべき種々の補足的な情報を計算可能であり；かかる情報は、例えば、明暗度値、明暗度値の空間微係数、例えば、局部的に重み付けられたモーメント、局部的に認識されたパターンの識別等のようなその他の特微量を含む。
分類ユニット２８はｙ座標だけを伝えることにより動作する。テスト１４は検出器２４によって実行され；基準ｐの条件付きインクリメントは、基準ｐをデータ項目メモリＤＭ２６２及び基準メモリＰ２６６に供給する基準カウンタ２６４により行われる。図１の種々の部品はクロック（図示しない）によって同期させられる。
図３は、本発明によりデータ項目を読み出す装置の一実施例を示している。上記装置は、フラグメモリＦ２６０と、基準メモリＰ２６６と、データ項目メモリＤＭ２６２とからなる。上記装置は、座標用の入力Ｃを更に有する。入力Ｃは、読み出しユニット４０と、分類ユニット４８と、受信ユニット４６（例えば、表示装置）とに接続される。読み出しユニット４０の出力は、フラグメモリＦ２６０のアドレス入力に接続される。フラグメモリＦ２６０のデータ出力は読み出しユニット４０に接続される。読み出しユニット４０は、置換ユニット４４の制御入力に接続された別の出力を有する。読み出しユニット４０は、加算器４２の第１の入力に接続された出力を更に有する。分類ユニット４８は、基準メモリＰ２６６のアドレス入力に接続される。基準メモリＰ２６６のデータ出力は、加算器４２の第２の入力に接続される。加算器４２の出力は、データ項目メモリＤＭ２６２のアドレス入力に接続される。データ項目メモリＤＭ２６２のデータ出力は、置換ユニット４４に接続される。置換ユニット４４の出力は、受信ユニットに接続される。
図３に示された装置の動作の説明を行う前に、図４を参照して本発明の方法をより詳細に説明する。
図４には、メモリシステムからデータ項目を読み出す本発明の方法の１バージョンが示されている。フラグメモリＦ２６０と、データ項目メモリＤＭ２６２と、基準メモリＰ２６６は、図２ａ又は２ｂを参照して説明が行われた方法を用いて得られるような値を有する場合を想定する。更に、例えば、フローチャートの開始点３０において受信された２次元の座標の組（ｘ，ｙ）が利用可能であり、フラグメモリＦ２６０のフラグは、値０及び１を取り、座標の組（ｘ，ｙ）によってアドレス指定されたアドレスに値０を有するフラグは、この座標の組に関連したデータ項目がメモリに格納されていないことを示し、値１を有するフラグは、データ項目が所定の長さの一つのメモリユニット内のメモリに格納されていることを示す場合を想定する。
フローチャートの最初のステップ３２の間に、受信された座標の組（ｘ，ｙ）によってアドレス指定された格納場所Ｆ（ｘ，ｙ）のフラグメモリＦ２６０の内容がゼロがどうかがテストされる。フラグメモリＦ２６０の内容がゼロならば、上記方法は、データ項目Ｄに標準的な値Ｓが設定されるステップ３９ｂに続き、その後、フローチャートは、終了点３０ｃに達し、データ項目Ｄの利用が可能になる。
フラグＦ（ｘ，ｙ）の値がゼロではないならば、座標の組（ｘ，ｙ）と関連したデータ項目がデータ項目メモリＤＭ２６２に格納されていることを意味するので、多数の次のステップ３４、３６、３８が実行される。上記ステップの間に、与えられた座標の組（ｚ，ｙ）として同一のｙ座標及びより小さいｘ座標ｘｘを有する座標の組（ｘｘ，ｙ）の個数がカウントされ、一方、フラグメモリＦ２６０において、かかる座標によってアドレス指定されたフラグＦ（ｘｘ，ｙ）は、関連したデータ項目がデータ項目メモリＤＭ２６２に格納されたことを示す。
カウントは以下のように行われる。最初の次のステップ３４の間に、カウントＮと、カウント座標ｘｘが初期化される。２番目の次のステップ３６の間に、カウント座標ｘｘが座標の組（ｘ，ｙ）のｘ座標の値に達したかどうかがテストされる。達していない場合、次のステップ３８の間に、カウントＮがフラグメモリＦ２６０内の座標の組（ｘｘ，ｙ）と関連したフラグの値ずつインクリメントされ、即ち、フラグＦ（ｘｘ，ｙ）によって関連したデータ項目が標準的な値を持たないことが示されるならば、Ｎは１ずつインクリメントされ；それ以外の場合、Ｎはインクリメントされない。次に、カウント座標ｘｘがインクリメントされ、上記方法は、カウント座標ｘｘが座標の組のｘ座標の値に達したかどうかがテストされるステップ３６から繰り返される。
カウント座標ｘｘが座標の組のｘ座標の値に達した場合、次のステップ３９ａが実行される。そこで、基準Ａが基準メモリＰ２６６から、即ち、与えられた座標の組のｙ座標によってアドレス指定された格納場所Ｐ（ｙ）から読み出される。次に、データ項目Ｄがデータ項目メモリＤＭ２６２、即ち、読み出された基準ＡとカウントＮの和がアドレス（Ａ＋Ｎ）である格納位置から読み出される。かくして、フローチャートは、再び終了点３９ｃに達し、データ項目Ｄの利用が可能になる。
図３に示された装置は、動作中に、図４のフローチャートに示された効果と等しい効果を有する。読み出しユニット４０は、フラグの値に関しテスト３２を実行し、必要であるならば、カウントＮを決定する。読み出しユニット４０は、カウントＮを加算器４２に供給し、カウントＮが基準メモリＰ２６６から発生したアドレスＡに加算される。標準的な値が座標（ｘ，ｙ）と関係していることがフラグメモリＦ２６０により示されることを読み出しユニット４０が通知した場合に、読み出しユニット４０は、標準的な値Ｓを受信ユニット４６に供給する置換ユニット４４を制御し；通知されない場合に、置換ユニット４４は、データ項目メモリＤＭ２６２から読み出されたデータ項目Ｄを伝達する。図３の種々の部品は、クロック（図示しない）を用いて同期させられている。
フラグメモリＦ２６０のために、好ましくは、例えば、１６ビットワードの同時的なブロックで読み出し可能なメモリが使用される。連続した座標の組と関連した多数のフラグがフラグの数をカウントするため全く同一のブロックにまとめて格納されるように、フラグは、好ましくは、系列の形でフラグメモリＦ２６０に格納される。カウントを行う間に（図４を参照のこと）、読み出しユニット４０は、連続した座標の組の多数のフラグを読み出すため、フラグメモリＦ２６０から多数のブロックを読み出す必要があり、その都度、読み出された各ブロック内のフラグの数をカウントしなければならない。読み出されるべきブロックの数は、従って、カウントされるべきフラグの数よりも実質的に少ない。かくして、フラグメモリＦ２６０からフラグを個別に読み出す必要がある場合よりも、カウントを高速に行うことが可能である。
ブロック内に読み出されたフラグの数のカウントは、ルックアップテーブル（ＬＵＴ）を用いて簡単に行うことができる。各ブロックの内容は、ＬＵＴメモリのアドレスとしての役割を行い；内容によってアドレス指定された格納場所で、ＬＵＴメモリは、上記内容の中のフラグの数を含む（例えば、アドレス０の個数０、アドレス１の個数１、アドレス２の個数１、アドレス３の個数２等）。
図１乃至４の実施例は、本発明の簡単化された例を示す役割だけを行う。実際上、多数の他の例を実現することができる。例えば、２次元の座標の組（ｘ，ｙ）の代わりに、より高次元の組、例えば、３次元の組（ｘ，ｙ，ｚ）を利用してもよい。上記組は、１個以上の座標を省くことにより分類され；例えば、同一の（ｙ，ｚ）の値（“共通因子”）を有する全ての座標の組は、同一のカテゴリーに属すると考え得るので、（ｙ，ｚ）の値は、基準メモリＰ２６６のアドレスとしての役割を行い、或いは、“ｚ”座標だけがカテゴリーの共通因子であるとみなされる。何れの場合でも、読み出しの際に（図４を参照のこと）、カウント３４、３６、３８を修正する必要があるので、与えられた座標の組（ｘ，ｙ，ｚ）と同一のカテゴリーに属する座標の組と関連したフラグによって、カウントが行われる。共通因子として（ｙ，ｚ）を利用する分類の場合に、例えば、フラグは、ｘｘがｘｘ＝１乃至ｘを表わすとき、（ｘｘ，ｙ，ｚ）に対しカウントすることができ；共通因子としてｚを利用する分類の場合、ｙｙがｙｙ＝１乃至ｙを表わすとき、ｙｙ＝ｙかつｘｘ＝１乃至ｘのとき、ｙｙ＜ｙかつｘｘが実現可能な全ての値のとき、（ｘｘ，ｙｙ，ｚ）に対しカウントが行われる。一つの分類内の同一のカテゴリー毎の座標が少なくなると共に、より多くのカウント作業と、より少ない基準メモリＰ２６６が必要とされる。
全ての座標の組が同一のカテゴリーの一部を形成すると考えられる極端な場合には、カウント作業（ｚｚ＝１乃至ｚならば、全ての座標の組（ｘｘ，ｙｙ，ｚｚ）に対するカウント、ｚｚ＜ｚならば、全ての実現可能なｘｘ及びｙｙに対するカウント、ｚｚ＝ｚならば、共通因子としてｚ座標と共にカテゴリーを利用する場合と同一の範囲に亘るカウント）の増加を犠牲にするならば、基準メモリを完全に省き、図２ａ、２ｂ及び４における上記メモリの操作を無くすことが可能である。書き込みの際に、データ項目メモリＤＭ２６２に格納された各データ項目と対応して、関連した座標の組をメモリに格納することにより、カウントを省略することが可能である。読み出しの際に、与えられた座標の組（ｘ，ｙ，．．．）のフラグＦ（ｘ，ｙ，．．．）によって、関連したデータ項目が標準的な値を持たないことが示されるならば、データ項目メモリＤＭ２６２内で正確な座標が対応するデータ項目を検索することが可能である。
更に、図１乃至４の説明は、データ項目が標準的な値Ｓを有するかどうかを排他的に示す２進数のフラグを想定している。しかし、その代わりに、３個以上の異なる値を取り得るフラグを利用することができる。従って、フラグは、多数の標準的な値の中からデータ項目の標準的な値を示し、或いは、データ項目がデータ項目メモリＤＭ２６２に格納されていることを示す。例えば、値０を用いることにより、２ビットのフラグは、データ項目メモリＤＭ２６２にデータ項目が格納されたことを示し、値１、２及び３を用いることにより、データ項目が、夫々、第１、第２又は第３の標準的な値を有することを示す。かかるフラグの使用により、フラグメモリＦ２６０に対しより大きい容量が必要とされるが、データ項目メモリＤＭ２６２に関し利点が生じる。これにより、特に、データ項目が、通常２個以上の制限された数の標準的な値の中から一つの値を取る場合に利点が得られる。
データ項目メモリＤＭ２６２に書き込まれた夫々のデータ項目の長さが、制限された数の値（例えば、０、４０又は８０バイト）しか取れないならば、データ項目メモリＤＭ２６２を数個のデータ項目メモリに分割することにより、各実現可能な長さの値に対し一つのデータ項目メモリ（例えば、４０バイトのデータ項目に対し１個、８０バイトのデータ項目に対し１個）が形成される利点が得られる。次に、同じ長さのデータ項目が同一のデータ項目メモリに書き込まれる。データ項目の読み出しのため、最初に、読み出しが行われるデータ項目メモリ（例えば、８０バイトメモリ又は４０バイトメモリ）が、長さコードに基づいて決定され、長さメモリＦ２６０を用いて、当該データ項目メモリ内の検索されたデータ項目に先行するデータ項目の数がカウントされる。長さの和はカウントを行うことにより簡単に決定されるので、長さを明示的に加算する必要がないという利点が得られる。
更に、図１乃至４の説明は、座標の一部（例えば、ｙ及びｚ座標）がカテゴリー内で常に同一である座標の組のカテゴリーに基づいている。他の分類、例えば、全ての座標の組がｘ＋ｙの同一の値を有するカテゴリーも実現可能である。一般的に言うと、分類ユニット２８，４８は、夫々のカテゴリーの数を各座標の組に加算する分類関数Ｃ（ｘ，ｙ，．．．）を実行する。しかし、カテゴリー内の座標の組と関連したデータ項目は、データ項目メモリＤＭ２６２に書き込まれる限り、継続してメモリＤＭ２６２に書き込まれるべきであり、即ち、他のカテゴリーからの座標の組と関連したデータ項目がその間に書き込まれることが無い。上記の語“継続して”は、論理的な意味で、“データ項目メモリＤＭ２６２への書き込みの継続”を意味し；それは、必ずしも物理的、空間的な継続（例えば、何時でもメモリ格納場所を飛ばすことが可能であり、飛ばされた格納場所を後のカテゴリーのため使用可能性）ではなく、再現性のある論理的な継続である。
実際上、継続とは、通常、一つの座標の繰り返し的なインクリメント又はデクリメントであり、引き続いて、最大又は最小の値に達したときにリセットされ；リセットに応答して、次の座標（例えば、ｙ座標）がインクリメント又はデクリメントされ、以下同様である。分類ユニット２８，４８は、カテゴリーの間の境界として上記の如く継続して所定の座標を指定し、１対の境界の間の座標の組が同一のカテゴリーに属するとみなすことにより座標の組を分類する。次いで、カウント（図４のステップ３４）は、次の小さい方の境界から継続して座標をカウントすることにより開始される。
図の記載を簡単にするため、別々のフラグメモリＦ２６０と、基準メモリＰ２６６と、データ項目メモリＤＭ２６２とが用いられている。上記メモリは、異なる性質（別個のメモリチップ、ディスクメモリ等）でもよく、或いは、例えば、全体的に半導体メモリ、磁気ディスクメモリ等として構成された一つの大きい物理的なメモリ内の異なるアドレス範囲に対応していても構わない。
【図１】
0003789132.tif 000002
【図３】
0003789132.tif 000003
【図２ａ】
0003789132.tif 000004
【図２ｂ】
0003789132.tif 000005
【図４】
0003789132.tif 000006