JPS62173572A - デ−タ記憶方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、データ記憶方式に関し、詳しくは矩形領域の
画像データを複数ビットでアクセス単位とし、このアク
セス単位で行または列方向にアクセスできるデータ記憶
方式に関するものである。

〔従来の技術〕

画像処理の分野では、一般に処理対象となるデータが矩
形領域であり、その領域内は濃淡を表す画素と呼ばれる
単位データで構成されている０画素は、１１１９７．′
０″で表現されるディジタルデータであり、そのデータ
構造は２次元矩形領域となる。

画像処理においては、このような矩形領域データを対象
として１輪郭追跡または行／列方向への画素ヒストグラ
ムを求める処理が実行される。その場合、２次元的な広
がりを保存したままで記憶装置に格納することが、処理
効率を高めるために望ましい。従って、従来より、行方
向または列方向のいずれの方向にも一定ビット長のアク
セス単位でアクセスできる２次元記憶空間を有する記憶
装置の開発が行われている。

第２図は、従来の２次元物理記憶空間への矩形領域の割
付は方法を示す図である。従来、このような記憶装置の
物理的空間への矩形領域データの割付けは、第２図（２
）（３）に示すような２つの方式により行われている。

その基本概念を説明すると、先ず第２図（１）において
は、格納すべき３種類の矩形領域データＡ、Ｂ、Ｃを表
し、それぞれの区分単位は記憶装置へのアクセス単位に
等しいものとする。この記憶装置の物理記憶空間は、第
２図（２Ｈ３）に示すようなＸ方向およびＹ方向への広
がりを持つ２次元空間で、一定ビット長のアクセス単位
で行または列方向にアクセスできるものとする。第２図
（２）の割付は方式では、矩形領域データＡ、Ｂ、Ｃを
物理記憶空間に２次元状配列のままで格納し、図より明
らかなように、原矩形領域イメージの２次元的連続性が
物理記憶空間上でも保存され、矩形領域内の行方向また
は列方向のいずれの方向でも、アクセス単位となる一定
ビット長を１記憶サイクルでアクセスすることができる
。また、第２図（３）に示す割付は方式では、矩形領域
データＡ、Ｂ、Ｃを物理記憶空間における行方向のアク
セス単位に等しい一定ビット長でラスク走査順に分割し
、この分割単位を物理記憶空間の任意の行の任意のアク
セス単位で区切られたアドレスらよりラスク走査順に連
続的に格納するので、物理記憶空間を密に利用すること
ができる。

〔発明が解決しようとする問題点〕

しかし、第２図（２）の直接割付は方式では、矩形領域
の形やサイズの違いにより、物理記憶空間を密に利用す
ることが困難であるという問題がある。また、第２図（
３）の一定ビット長単位の連続割付は方式では、原矩形
領域の列方向の連続性が完全に失われて、原矩形領域に
おける列方向の一定ビット長データをアクセスする場合
には、物理記憶空間上で行方向にラスク走査順に格納さ
れたビットデータを含む全ての一定ビット長データをア
クセスする必要があり、そのためアクセス単位のビット
数に等しい記憶サイクル数を要するので、処理時間が多
くかかるという問題がある。

本発明の目的は、これらの従来の問題を改善し、行方向
または列方向のいずれの方向にも一定ビット長のアクセ
ス単位でアクセスできる記憶装置において、任意の矩形
領域で表されるビット配列データを上記記憶装置の物理
記憶空間に格納する際に、物理記憶空間の高い利用率を
確保しながら、矩形領域内の行方向または列方向のいず
れの方向でもアクセス単位である一定ビット長を常に１
記憶サイクルでアクセスできるデータ記憶方式を提供す
ることにある。

〔問題点を解決するための手段〕

上記目的を達成するため、本発明のデータ記憶方式は、
記憶装置の物理記憶空間を、該記憶装置への行方向また
は列方向に対するアクセス単位であるビット長にそれぞ
れ等しい２次元矩形ブロック単位に分割し、次に分割さ
れた各ブロックに一連番号を付与した後、２次元状に配
列された領域データを記憶装置に格納する際には、該２
次元配列領域データを上記ブロック単位に分割し、かつ
ブロック内でのデータの２次元配列関係を維持したまま
、上記記憶空間内の任意のブロック領域から連続的に格
納することに特徴がある。

〔作　　用〕

本発明は、矩形領域で表される画像データを複数ビット
の並びからなる一定ビット長をアクセス単位とし、この
アクセス単位で行または列方向のいずれの方向にもアク
セスできる記憶装置において、この記憶装置の物理記憶
空間を、この記憶装置への行方向または列方向に対する
アクセス単位となる一定ビット長にそれぞれ等しい２次
元矩形ブロック単位に分割し、さらに分割されたブロッ
クに一連の番号を付与する機能構造を有する。その場合
、２次元状に配列された領域データの格納は、その２次
元配列領域データを上記ブロック単位に分割し、この分
割されたブロック単位のデータ群を、ブロック内でのデ
ータの２次元配列関係を保存したまま、上記物理記憶空
間内の任意のブロック領域から連続的に格納する。これ
により、格納すべき２次元状配列領域データの形、大き
さの違いにかかわらず、物理記憶空間の高い利用率を確
保しながら、行方向あるいは列方向のいずれの方向でも
アクセス単位である一定ビット長のアクセスを、常に１
記憶サイクルで実現できる。

２次元物理記憶空間への割付けと配置が、原２次元配列
領域全体をそのまま割付は単位として２次元物理空間に
配置するか（第２図（２）参照）、あるいはアクセス単
位である一定ビット長を割付は単位として原２次元配列
領域をその割付は単位でラスク走査順に分割して、２次
元物理空間を構成する一連の番号付けられたアクセス単
位群の任意のアクセス単位からラスク走査順に配置して
いる（第２図（３）参照）従来の方法に比べて、本発明
では、記憶装置における行方向および列方向のアクセス
単位である一定ビット長を両辺長とするブロック群を、
１次元物理ブロック空間を構成する一連の番号付けられ
たブロック群の任意のブロック領域から連続的に配置す
る。なお、Ｘ／Ｙ両方向へのアクセス可能な記憶装置の
構成については。

例えば特開昭６０−１０３３９０号公報等に記載されい
るが、単に技術的実現の可能性の存在が示されているだ
けである。

〔実施例〕

以下、本発明の実施例を、図面により詳細に説明する。

第３図は、本発明の一実施例を示すＸ／Ｙ方向にアクセ
ス可能な記憶装置の基本構成とブロック概念の関連説明
図である。第３図（１）は、Ｘ／Ｙ方向の一定ビット長
アクセスを疫ＡＭチップを用いて実現する例を示すもの
である。第３図において、１はＲＡＭチップであり、記
憶装置はｎ５ｍ列からなるチップアレイで構成される。

各ＲＡＭチップ１には共通のセルアドレスを割当て、必
要なＲＡＭチップ行あるいはチップ列の選択を同時に行
い、かつその選択されるＲＡＭチップ１への書き込み／
読み出し信号を供給することにより、任意の行方向のｍ
ビット長あるいは列方向のｎビット長がアクセスできる
ことは、第３図より原理的に明らかである。なお、ｍ　
＝　ｎであっても、勿論差し支えはない。

第３図（１）のような基本構成の記憶装置を利用するこ
とにより、任意のチップ内セルアドレスに対するＲＡＭ
チップの行または列選択により、（ｍ行）×（ｎ列）の
データのアクセスが可能であり。

同じようにして、他のチップ内セルアドレスに対しても
（ｍ行）Ｘ（ｎ列）のデータアクセスが可能である。（
ｍ行）×（ｎ列）のデータ空間をブロックと定義すると
、このブロック内では任意の行あるいは列方向の一定ビ
ット長を選択してアクセスできる。このブロックは、同
じようにして、チップ内セルアドレスを変更することに
より、ＲＡＭチップ１のビット容量分だけ生成される。

すなわち、１行Ｘ１列、２行Ｘ１列、３行Ｘ１列・・・
・。

１行Ｘ２列、２行Ｘ２列、３行Ｘ２列、・・・・という
ように、全部でｍＸｎ個のブロック数が生成される。こ
れらのブロックに、例えばＲＡＭチップ１のセルアドレ
ス順に一連の番号を付与するならば、この記憶装置の物
理記憶空間は、第３図（２）に示すような１次元配列の
ＲＡＭチップ内の総ビツト容量の等しいブロック数から
なる。すなわち、１行Ｘ１列がブロック番号ＢＯとする
と。

２行Ｘ１列がＢｌ、３行Ｘ１列が８２・・・・ｎ行×ｍ
列がＢｚとなる。

このブロック空間を前提として、本発明による２次元矩
形領域の記憶装置の物理記憶空間へのデータ記憶方式に
ついて、次に説明する。

第１図は、本発明の一実施例を示すデータ記憶方式によ
る２値画像矩形領域のブロック分割法と物理ブロック空
間への割付は概念の図である。第１図（１）は、格納す
べき２値画像矩形領域を示しており、Ｘ方向にＸＳ画素
、Ｙ方向にＹｓ画素だけ存在するものとする。いま、■
ブロック空間が第３図（１）に示したように、ｍＸｎビ
ットからなるものとすると、ｍ　Ｘ　ｎビットのブロッ
クで２値画像矩形領域をラスク走査順に分割する。その
分割された順にブロック番号を付与する。そのブロック
分割法により分割された状態を、第１図（２）ニ示ス。

この時、矩形領域のサイズによっては、図のように１ブ
ロツクに満たない場合が生じる可能性もある。このよう
な場合でも、■ブロックを割付け、端数の領域はＩＩ　
Ｏ１１を満たしておく。分割ブロックの物理ブロック空
間への割付けは、次の手順により行う。

（ａ）物理ブロック空間上の割付けるべき任意の起点ブ
ロックを決める。（ｂ）分割した矩形領域の先頭ブロッ
クを、上記起点ブロックに割付ける。

（ｃ）矩形領域の残りの分割ブロックを順次物理空間の
起点ブロック以降のブロックに、シーケンシャルに割付
ける。

第３図（２）および第１図（２）の例を用いて述べると
、物理ブロック空間上の起点ブロックをＢ。

とすることにより、格納すべき矩形領域の分割ブロック
ｂｏ、ｂｌ、　　・・・・・・ｂ７を、ｂｏ→Ｂ工、ｂ
ｌ→Ｂ工＋１．・・・・ｂ７→Ｂ□＋７のようにマツピ
ングする。このマツピングされた状態を、第１図（３）
に示す。第１図（３）では、上述の領域を第１の矩形領
域とすると、物理ブロックの任意の起点ブロックＢ□か
らＢ、＋７までに割付けられ、第２の矩形領域はその後
のブロックからＢ、＋ｊまで割付けられ、第３の矩形領
域はその後のブロックから順に割付けられる。このよう
にして、連続的に物理ブロック空間に割付けられる。ブ
ロック内のデータに関しては、分割ブロックイメージ（
矩形小領域）のままで、物理ブロックに割付けられる。

ブロック対応のデータの書き込みは、物理ブロックの先
頭よりｍビット長づつ順に書き込まれる。ブロックの読
み出しは、Ｘ方向アクセスの場合、物理ブロックの任意
の行アドレスを指定して読み出し、Ｙ方向アクセスの場
合、物理ブロックの先頭行内の任意のビットアドレスを
指定してブロックのＹ方向にｎビット長を読み出す。

次に、データアクセスにおけるアドレスの計算法につい
て、第１図（４）により説明する。第１図（４）におい
て、ブロック分割された矩形領域の任意のブロック番号
を（ｘ、ｙ）で表し、同じように、任意のビット番号を
（Ｘｂ、Ｙｂ）で表す。また、Ｘ方向のブロック数をＢ
ｘ、Ｙ方向のブロック数をＢｙとすると、これらは次の
計算式で求められる。

Ｂｘ＝ｌ　　　ｌ　　・・・・・・・・・・（１）Ｂ Ｂｙ＝ｌ　　　Ｉ・・・・・・・・・・・　（２）ただ
し、１１は、小数点以下の数値を切上げて、整数化する
ことを意味するものとする。

さらに、変換の定義を次のように行う。

ｐｂは、物理ブロック空間上で分割ブロックを割付ける
先頭ブロック番号であり（ｐｂ＝ｏ、Ｌ。

・・・・・・）、Ａは、物理ブロック空間上でのアクセ
ス対象となるブロック番号であり（Ａ＝０．１．・・・
・・）、Ａｂは、物理ブロック空間上でのアクセス対象
となる一定ビット長データの先頭ビットアドレスで、ブ
ロック内ではラスタ走糞順に連続し、かつ物理ブロック
間でも連続するようにアドレス付けされているものとす
る。

この時、Ａ、Ａｈは、次式により求められる。

Ａ；Ｐｂ＋ＢｘＹ＋Ｘ　・・・・・・・　（３）Ａｂ＝
ｍｎ　（Ａ−１）＋Ｘｓ’Ｙｂ＋Ｘｂ・・・・・・・　
（４） 次に、矩形領域内の連続データアクセス時におけるアド
レス計算の方法を、説明する。例えば、矩形領域内の任
意の分割ブロック番号（ｘ、ｙ）のブロックをアクセス
し、引き続き右方向の隣接分割ブロックをアクセスした
い場合には、Ｐｂ、Ｂｘ、Ｘ、Ｙを予め記憶装置内のレ
ジスタ等に記憶しておき、Ｘ（−Ｘ＋１として式（３）
により次にアクセスすべき物理ブロック空間上でのブロ
ック番号を計算して、その番号により目的ブロックをア
クセスすることができる。次に、矩形領域内の任意の分
割ブロックのＹ方向の任意のビット番号（Ｘｂ、Ｙｂ）
の一定ビツト長データをアクセスし、引き続きＹ方向の
下位ブロックデータをアクセスしたい場合は、ｍ　ｐ　
ｎ　ｇ　Ｘ　ｓｙ　Ａを予め上記と同じように記憶装置
内のレジスタ等に記憶しておき、Ｙｔｌ−Ｙｂ＋ｎとし
て、式（３）により次にアクセスすべき物理空間上での
ビットアドレスを計算して、そのビットアドレスにより
目的ビット列をアクセスすることができる。同じように
して、Ｘ方向の一定ビット長データのアクセスについて
は。

Ｘｂ４−Ｘｂ＋ｍとして、次アドレスを計算し、目的デ
ータをアクセスすることができる。

同じような考え方で、現在アクセス中のアドレスを基準
にして、ＸまたはＹ方向の上下左右に自由にアクセスで
きることは明らかであるので、説明は省略する。

この結果より明らかなように、従来における２次元矩形
領域イメージのままで割付ける技術（第２図（２）参照
）、あるいは一定ビット長を格納の基本単位とする技術
（第２図（３）参照）に比較すると、本実施例では、２
次元のＸ／Ｙ方向にアクセス可能な記憶装置に対して、
ブロックを割付けの基本単位とするデータ記憶方式を適
用することにより、格納すべき２値画像矩形領域の形・
サイズの違いにもかかわらず、記憶装置の物理記憶空間
へ密に割付けることができ、かつブロック内でのＸ方向
、あるいはＹ方向のいずれの方向でもアクセス単位であ
る一定ビッ１−長のアクセスを１記憶サイクルで実行す
ることが可能である。

なお、実施例では、２値画像へ適用した場合について説
明したが、記憶装置として、Ｘ／”１方向にアクセスす
る時のアクセス単位である一定ビット長の各ビットに対
応して、多値を記憶できるように、ビットプレーンを多
重に設けた、いわゆる３次元記憶空間のアクセスが可能
な装置を用いると、本発明のデータ記憶方式は多値画像
へも適用することができる。その場合に、本発明の原理
に基づいて得られる効果は、２値画像の場合と全く同じ
である。

なお１本実施例においては、矩形領域のサイズによって
は、領域の右周辺部と下周辺部に分割ブロックで割り切
れない場合に、無駄な部分が生じることもあるが、ブロ
ックサイズを１６２とすると、通常、矩形領域のサイズ
は１２８２〜１０２４２のような場合が多いので、一般
的である。この場合で、Ｉ＆悪の例として、１２９２を
考えると、周辺に（１５Ｘ１６）Ｘ１６＋１６２−１＝
４０９５〔ビット〕の無効領域が生じる。このときの物
理記憶空間の利用率は、（９２Ｘ１６２−４０９５）／
（９２Ｘ１６２）＃０．８となる。しかし、２のべき乗
サイズの矩形領域では、常に１００％の記憶空間利用率
を実現できるので、実用上は問題がない、また、本実施
例では、２値画像矩形領域データのアクセス時に、Ｘ方
向およびＹ方向の一定ビット長のアクセスを、いずれも
１記憶サイクルで実行できるので１画像処理における記
憶装置のアクセス時間の短縮に大きく寄与できる。

例えば、ブロックサイズをｍＸｍとし、（一定ビット長
）＝ｍビットすると、Ｙ方向の一定ビット長のアクセス
時には、第２図（３）に示す従来技術の場合に必要とな
るｍ回の一定ビット長アクセスを、本実施例では、１／
品つまり１回に短縮することができる。

〔発明の効果〕

以上説明したように、本発明によれば１行方向あるいは
列方向のいずれの方向にも一定ビット長のアクセス単位
でアクセスできる記憶装置に対して、矩形領域をブロッ
ク単位で分割して物理ブロックの一次元空間に連続的に
割付けるため、矩形領域の形・サイズに関係なく、密に
割付けることができ、物理記憶空間利用率を高めること
が可能である。また、行方向および列方向の一定ビット
長のアクセスを、いずれもｌ記憶サイクルで実行できる
ので、画像処理の場合の記憶装置アクセス時間の短縮が
可能である。

【図面の簡単な説明】

第１図は本発明の一実施例を示すデータ記憶方式による
２値画像矩形領域のブロック分割方法と、物理ブロック
空間への割付は概念の図、第２図は従来の行／列方向ア
クセス可能な記憶装置の物理空間に対する２値元矩形領
域データの割付は方法を示す図、第３図は本発明におけ
る行／列方向アクセス可能な記憶装置の基本構成と、ブ
ロック概念を示す図である。 Ｌ　：　ＲＡＭチップ、ｘＢ：ｘ方向画素数、Ｙｓ：Ｙ
方向画素数、（Ｘｂ、Ｙｂ）ニブロック分割された矩形
領域の任意のビット番号、（ｘ、ｙ）：同じく矩形領域
の任意のブロック番号、ＢＯ〜Ｂ−Ｌ：物理ブロック番
号、ｂＯ−ｂｊ：矩形領域の分割ブロック。 特許出願人日本電信電話株式会社、− 第１図 ＝Ｘｓ画素二 山　二値画像矩形領域　　　　　　　（２）ブロック分
別法物理ブロック番号 （３）物理プロ７りへの割ｆ＝ｆけ方式（４）分割ブロ
ンク空間と番号付与法 第２図 Ｙ二次元物理記憶空間　　Ｙ二次元物理記憶空間筒　　
　３　　　図 ｍ列　　　　−＃Ｘ方向 （１）１ブロック空間 ■　全物理ブロンク空間

Claims (1)

【特許請求の範囲】
1. １、行方向または列方向のいずれの方向にも予め定めら
   れたビット長をアクセス単位としてアクセスすることが
   可能な記憶装置において、該記憶装置の物理記憶空間を
   、該記憶装置への行方向または列方向に対するアクセス
   単位であるビット長にそれぞれ等しい２次元矩形ブロッ
   ク単位に分割し、次に分割された各ブロックに一連番号
   を付与して、２次元状に配列された領域データを記憶装
   置に格納する際には、該２次元配列領域データを上記ブ
   ロック単位に分割し、かつブロック内でのデータの２次
   元配列関係を維持したまま、上記記憶空間内の任意ブロ
   ック領域から連続的に格納することを特徴とするデータ
   記憶方式。