JPH04364594A - 矩形抽出方法及び矩形抽出装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、文字認識装置等の画像
データ処理に係り、特に画像上の接続したランに外接す
る矩形の抽出に関する。

【０００２】

【従来の技術】このような矩形抽出は、基本的に、画像
データをスキャンして各ライン上のランを抽出してラン
データを生成する処理と、このランデータに基づいて矩
形の登録、追加、統合をする処理によって行なわれるが
、従来は追加と統合は別々の処理とされている。このよ
うな矩形抽出技術は、例えば本出願人の特願平１−２８
４２８４号特許願に添付の明細書及び図面に示されてい
る。

【０００３】ランデータは、基本的には図１１に示すよ
うにランの始点と終点の座標であるが、始点と終点のｙ
座標は同一であり、さらに同一ライン上の全てのランで
同一値であるため、ｙ座標は各ラインに１個だけあれば
間に合う。そこで通常は、個々のランについて始点のｘ
座標Ｘｓと終点のｘ座標Ｘｅがランデータとして用いら
れる。矩形データとしては、図１２に示すように、矩形
の対角点の座標が用いられる。

【０００４】ランデータより矩形を抽出するには、まず
現在処理中のライン上の着目したランのランデータと前
ライン上のランのランデータとを比較することによって
着目ランと前ライン上のランとの接続関係を調べる。着
目ランに接続するランがない場合、着目ランを新しく矩
形として登録し、その矩形データを生成する。

【０００５】着目ラインにランが接続している場合、着
目ランが既にいずれかの矩形に所属しているかどうか調
べ、所属していなければ、着目ランを接続ランの所属矩
形に追加し、その矩形データを更新する。他方、着目ラ
ンが矩形に所属済みであるときは、この所属矩形と接続
ランの所属矩形を統合する。

【０００６】この統合のためには、ランが所属する矩形
の矩形データを参照できなければならないため、ランデ
ータに始終点のｘ座標のほかに、所属矩形データを指し
示すポインタｌｉｎｋが追加される。着目ランの所属矩
形と接続ランの所属矩形の統合は、始点座標の小さい方
、あるいは終点座標の大きい方のいずれかを選び、この
矩形に他方の矩形を統合するが、通常はポインタｌｉｎ
ｋの値の小さい方の矩形に他方の矩形を統合する。

【０００７】

【発明が解決しようとする課題】従来は、ランの接続関
係によって登録、追加、統合の３種類の別処理を行なう
ため、処理の制御が複雑になるという問題があった。よ
って、本発明の主たる目的は、矩形抽出の処理制御を簡
単にすることにある。

【０００８】

【課題を解決するための手段】請求項１の発明の矩形抽
出方法は、処理中のライン上の着目ランと、処理済みの
前ライン上のランとの接続関係を調べ、着目ランが前ラ
イン上のいずれのランとも接続しない場合に該着目ラン
を新たな矩形として登録し、着目ランが前ライン上の１
個以上のランと接続している場合、該着目ランを矩形と
みなし、該矩形と該着目ランに接続している各ランが所
属している矩形とを統合することを特徴とする。

【０００９】請求項２の発明の矩形抽出装置は、処理中
ライン上のラン及び前ライン上のランの始終点のｘ座標
、各ランの所属矩形を指し示すポインタ、矩形の対角点
のｘ座標とｙ座標メモリを保有するメモリ、このメモリ
上のデータに対し請求項１記載の矩形抽出処理を実行す
る処理部、この処理部により処理中のラインのｙ座標を
保持するカウンタ、及び、前記処理部より出力されるア
ドレスをデコードし前記メモリまたは前記カウンタを選
択するアドレスデコーダを有し、前記処理部は矩形抽出
処理時に、前記メモリ上の着目ランの始終点のｘ座標の
記憶アドレスに所定のオフセットを加算したアドレスを
出力することによって前記カウンタより該着目ランの始
終点のｙ座標を取得し、前記メモリ上の矩形のｘ座標の
記憶アドレスに前記所定オフセットを加算したアドレス
を出力することにより該矩形のｙ座標を読み取りまたは
書き込むことを特徴とする。

【００１０】

【作用】従来方法によれば、矩形抽出処理は登録、追加
、統合の３種類の処理からなっていたが、請求項１の発
明によれば、追加と統合の処理が一つの統合処理に統一
されるため、処理の制御が簡単になる。通常、矩形抽出
処理はソフトウエアに依存する割合が大きいため、この
ような制御の簡略化は処理プログラムの単純化、効率化
に大きく寄与するものである。

【００１１】請求項２の発明によれば、ランデータを矩
形データと同様に扱って追加と統合の統一処理を容易か
つ効率的に実行することができるとともに、ランのｙ座
標を記憶するためのメモリスペースが不要となるため必
要なメモリ容量を減らすことができる。

【００１２】

【実施例】図１は本発明の一実施例の装置構成を示すブ
ロック図である。１は画像データをラスタースキャンし
、主走査方向（ｘ方向）のライン上のランを抽出し、ラ
ンデータを生成するラン抽出部である。２はランデータ
と矩形データに対して矩形の登録、ランの矩形への追加
、矩形の統合の処理を行なう矩形抽出部である。なお、
後述のように追加と統合は区別されず統合処理に統一さ
れる。

【００１３】また図１において、３はランデータと矩形
データを格納するメモリである。４は矩形抽出処理部２
よりバス８に出力されたアドレスをデコードしメモリ３
またはＹ方向カウンタ５を選択的に有効にするアドレス
デコーダである。Ｙ方向カウンタ５は矩形抽出処理部２
が現在処理中のライン（現在ライン）の副走査方向座標
（ｙ座標）を保持するカウンタで、矩形抽出処理部２に
よりインクリメントされる。６はＹ方向カウンタ５の出
力ゲートであり、Ｙ方向カウンタ５がアドレスデコーダ
４により選択された時にＹ方向カウンタ５の値をバス８
に出力する。

【００１４】図２は矩形抽出処理に関連したメモリマッ
プを示す。１１，１２，１３はアドレスが連続したメモ
リであり、これらは図１のメモリ３上にある実メモリで
ある。メモリ１１とメモリ１３は矩形データのバッファ
であり、メモリ１１には矩形の対角点ｘ座標（Ｘｓ，Ｘ
ｅ）とポインタ（ｌｉｎｋ）が格納され、メモリ１３に
は矩形の対角点ｙ座標（Ｙｓ，Ｙｅ）が格納される。メ
モリ１２はランデータのバッファであって、ここにはラ
ンの始終点ｘ座標（Ｘｓ，Ｘｅ）とポインタ（ｌｉｎｋ
）が格納される。

【００１５】また図２において、メモリ１３に連続した
メモリ１４はＹカウンタ５に割り当てられたもので、こ
れはメモリ３のアドレス空間より上位のアドレス空間が
割り当てられる。すなわち、このメモリ１４には実メモ
リは存在しない。このメモリ１４のアドレスが指定され
ると、アドレスデコーダ４によってＹ方向カウンタ５が
選択され、その値が出力ゲート６を介しバス８に読み出
される。

【００１６】図３に処理全体のフロー図を示す。図４は
図３中の登録処理ステップ１０８のフロー図、図５は図
３中の統合処理ステップ１１０のフロー図である。これ
らのフロー図により、矩形抽出処理を説明する。

【００１７】現在ラインのラン抽出をラン抽出部１で実
行させる（ステップ１０２）。抽出されたランのランデ
ータは、メモリ１２に前ラインのランデータに続けて格
納される。このランデータは、ランの始終点ｘ座標Ｘｓ
，Ｘｅとポインタｌｉｎｋであるが、この段階ではｌｉ
ｎｋは当該ランを指すように、当該ランデータの記憶ア
ドレスがセットされる。

【００１８】現在ラインのラン抽出が終わると、矩形抽
出処理部２は現在ラインの先頭のランより処理を開始す
る。まず、メモリ１２をアクセスし、現在ライン上の着
目ランのランデータ（ｘ座標）と前ラインのランデータ
（ｘ座標）とを比較することにより、着目ランと前ライ
ン上のランとの接続を調べる（ステップ１０６）。着目
ランとの接続ランがない場合にはステップ１０８の処理
を実行し、接続ランがある場合にはステップ１１０の処
理を実行する。

【００１９】ステップ１０８では、着目ランを新しい矩
形として登録する処理を行なう。すなわち図４に示すよ
うに、メモリ１１の最後の矩形データの次の空き領域の
アドレスｎｅｘｔに、矩形データとして、メモリ１２上
の着目ランデータを書き込む（ステップ２００）。次に
、メモリ１１とメモリ１３のアドレスのオフセットをｎ
ｅｘｔに足し込んで、メモリ１３のｎｅｘｔに対応する
アドレスを求め、このアドレスに現在ラインのｙ座標を
終点座標Ｙｓ，Ｙｅとして書き込む（ステップ２０２）
。すなわち、着目ランの矩形データを登録する。

【００２０】なお、Ｙ方向カウンタ５は現在ラインのｙ
座標を指すようにインクリメントされており、矩形抽出
処理部２は、着目ランデータの記憶アドレスにメモリ１
２とメモリ１４のアドレスのオフセット（これはメモリ
１１とメモリ１３のアドレスのオフセットと同値である
）を加算して求めたメモリ１４のアドレスを出力するこ
とにより、Ｙ方向カウンタ５に保持されている現在ライ
ンのｙ座標を読み取ることができる。

【００２１】次に矩形抽出処理部２は、メモリ１２上の
着目ランデータのｌｉｎｋと、今登録したメモリ１１上
の矩形データのｌｉｎｋを、当該矩形データの記憶アド
レスｎｅｘｔに書き換える（ステップ２０４）。かくし
て、ランデータのポインタｌｉｎｋを調べることによっ
て、各ランの所属する矩形を容易に認識できるようにな
る。最後に、次に矩形データを登録するための空き領域
のアドレスｎｅｘｔを１だけ進める（ステップ２０６）
。

【００２２】他方、前ライン上に着目ランとの接続ラン
が存在している場合にはステップ１１０において、矩形
への追加または矩形の統合を行なうが、この処理は従来
と異なり統合処理に統一される。

【００２３】図５に示すように、まずステップ３００で
、着目ランを既にある矩形に所属しているとみなし、着
目ランデータのｌｉｎｋ（ここではＰｃとする）を読み
出し、アドレスＰｃより矩形データＸｓ，Ｘｅ（これは
メモリ１２上の着目ランデータＸｓ，Ｘｅである）を読
み出し、また、Ｐｃにメモリ１１とメモリ１３のアドレ
スのオフセット（これはメモリ１２とメモリ１４のアド
レスのオフセットと同値）を加えたアドレスをアクセス
し、矩形データＹｓ，Ｙｅ（これはＹ方向カウンタ５の
値すなわち着目ランのｙ座標である）を読み出す。

【００２４】次にステップ３０２で、メモリ１２より着
目ランに接続している前ラインのランのランデータのｌ
ｉｎｋ（ここではＰａとする）を読み出す。なお、接続
ランが複数存在するときは、記憶アドレスが最も小さい
ものから順に一つのランデータを選び、そのｌｉｎｋを
読み出す。このアドレスＰａより矩形データＸｓ，Ｘｅ
（接続ランの所属矩形のｘ座標）を読み出し、またＰｃ
にメモリ１１とメモリ１２のアドレスのオフセットを加
えて得たアドレスより矩形データＹｓ，Ｙｅ（所属矩形
のｙ座標）を読み出す。

【００２５】次に、ＰａとＰｃを比較する（ステップ３
０４）。Ｐａ＜Ｐｃの場合、アドレスＰａ及びオフセッ
トを加えたアドレスにそれぞれ記憶されている矩形デー
タを、アドレスＰｃ及びオフセットを加えたアドレスよ
りそれぞれ読み出した矩形データを用いて更新し（ステ
ップ３０６）、アドレスＰｃの矩形データのｌｉｎｋに
アドレスＰａをセットする（ステップ３０８）。逆に、
Ｐａ≧Ｐｃの場合、アドレスＰｃ及びオフセットを加え
たアドレスにそれぞれ記憶されている矩形データを、ア
ドレスＰａ及びオフセットを加えたアドレスよりそれぞ
れ読み出した矩形データを用いて更新し（ステップ３１
０）、アドレスＰａの矩形データのｌｉｎｋにアドレス
Ｐｃをセットする（ステップ３１２）。

【００２６】着目ランの接続ランが残っているか調べ（
ステップ３１４）、残っている場合はステップ３００よ
り、次の接続ランに関して同様の処理を繰り返して矩形
を統合する。

【００２７】以上のようにして一つの着目ランに関する
処理を終わると、着目ランへのポインタを１つ進め（ス
テップ１１２）、次の着目ランの処理に進む。ただし、
現在ラインの最後のランまで処理が終わった場合は、ス
テップ１０４よりステップ１００に戻る。

【００２８】ここまでの説明から明らかなように、着目
ランとの接続ランが１個のみの場合は、ステップ３００
→ステップ３０２→ステップ３０６→ステップ３０８の
処理が１回だけ実行される。すなわち、着目ランが矩形
とみなされ、換言すれば着目ランのランデータが矩形デ
ータとして扱われ、矩形統合の処理によって接続ランの
所属矩形に着目ランが追加されることになる。

【００２９】他方、着目ランに対し二つの接続ランがあ
る場合、接続ランが１個のみの場合と同様に、着目ラン
を矩形とみなした矩形統合の処理により１番目の接続ラ
ンの所属矩形に着目ランが追加される。２回目の処理で
は、ステップ３００で着目ランデータのｌｉｎｋ（Ｐｃ
）を辿って、その追加矩形データがアクセスされ、ステ
ップ３０２で２番目の接続ランデータのｌｉｎｋ（Ｐａ
）を辿って、その所属矩形データがアクセスされ、ステ
ップ３０４の比較結果に従い、ステップ３０６，３０８
またはステップ３１０，３１２で矩形データ及びランデ
ータが更新されることにより、矩形の統合がなされる。

【００３０】着目ランに３個以上の接続ランがある場合
は、その個数に等しい回数だけ同様の処理が繰り返され
ることによって、矩形統合がなされる。

【００３１】処理の具体例として、図６に示すランのパ
ターンの処理について説明する。今、ｙ＝ｙｃのライン
が現在ラインとなり、そのラン抽出が行なわれたとする
。なお、このラインの前ラインまでランが存在しなかっ
たとする。

【００３２】この現在ラインの３個のランＲ１，Ｒ２，
Ｒ３は、図３のステップ１０８によって矩形として登録
されるため、登録後のメモリ内容は図７に示す如くにな
る。各ランの所属する矩形データのｘ座標はランデータ
のｘ座標と同一であり、各矩形データのｙ座標は現在ラ
インのｙ座標と同一である。各ランデータのポインタｌ
ｉｎｋには、その所属矩形データの記憶アドレス（ｒｅ
ｃ１，ｒｅｃ２，ｒｅｃ３）がセットされる。

【００３３】次に、図６に示すｙ＝ｙ＋１のラインが現
在ラインとなり、その２個のランＲ４，Ｒ５のランデー
タがメモリ１３にランＲ３のデータに続けて格納される
。各ランデータのｌｉｎｋは、この段階では、その記憶
アドレスがセットされる。

【００３４】現在ラインの最初のランＲ４は前ラインの
ランＲ１と接続しているため図３のステップ１１０で処
理されるが、接続ランは１個のみであるため、図５のス
テップ３００→ステップ３０２→ステップ３０６→ステ
ップ３０８の統合処理が１回のみ実行されることにより
、ランＲ４はランＲ１の所属矩形（ｒｅｃ１）に追加さ
れる。その結果、メモリ内容は図８に示す如く更新され
る。当該矩形データのｘ座標及びｙ座標はＸｓ＝Ｘｓ４
、Ｘｅ＝Ｘｅ１、Ｙｓ＝ｙｃ、Ｙｅ＝ｙｃ＋１に更新さ
れる。

【００３５】次のランＲ５も接続ランが存在するための
図３のステップ１１０で処理されるが、接続ラン数が２
個であるため２回の処理となる。１回目は図５のステッ
プ３００→ステップ３０２→ステップ３０６→ステップ
３０８の処理となり、これにより着目ランＲ５はランＲ
２の所属矩形（ｒｅｃ２）に追加される。この追加後の
メモリ状態は図９に示す如く更新される。２回目はステ
ップ３００→ステップ３０２→ステップ３１０→ステッ
プ３１２の処理となり、これにより着目ランＲ５及び接
続ランＲ２の所属矩形（ｒｅｃ２）に接続ランＲ３の所
属矩形（ｒｅｃ３）が統合される。かくして、図１０に
示すメモリ内容となる。

【００３６】なお、図２に示したメモリ１１，１２，１
３，１４のアドレスの割り付けを逆向きにしてもよい。 この場合でも、メモリ１１とメモリ１３並びにメモリ１
２とメモリ１４のアドレスのオフセットが負値となるの
みで、同様の処理が可能である。

【００３７】

【発明の効果】以上詳細に説明した如く、請求項１の発
明によれば、追加と統合の処理が統合処理に統一される
ため矩形抽出処理の制御が簡単になり、処理プログラム
の単純化・効率化が可能となる等の効果を得られる。ま
た、請求項２の発明によれば、ランデータを矩形データ
と同様に扱って、請求項１の発明による追加と統合の統
一処理を容易かつ効率的に実行することができるととも
に、ランのｙ座標を記憶するためのメモリスペースが不
要となるため必要なメモリ容量を減らすことができる等
の効果を得られる。

【図面の簡単な説明】

【図１】本発明の一実施例の装置構成を示すブロック図
である。

【図２】同実施例における矩形抽出処理に関連したメモ
リマップ並びにランデータ及び矩形データの構造を示す
図である。

【図３】同実施例の処理全体の流れを示すフロー図であ
る。

【図４】図３中の矩形登録処理ステップの内容を示すフ
ロー図である。

【図５】図３中の矩形統合処理ステップの内容を示すフ
ロー図である。

【図６】矩形抽出処理の説明のためのランパターンの例
を示す図である。

【図７】図６に示す上側のラインについて処理した後の
メモリ内容を示す図である。

【図８】図６に示す下側のライン上の一つ目のランにつ
いて統合処理が行なわれた段階のメモリ内容を示す図で
ある。

【図９】図６に示す下側のライン上の二つ目のランにつ
いて１回目の統合処理が行なわれた段階のメモリ内容を
示す図である。

【図１０】図６に示す下側のライン上の二つ目のランに
ついて２回目の統合処理が行なわれた段階のメモリ内容
を示す図である。

【図１１】ランデータの説明図である。

【図１２】矩形データの説明図である。

【符号の説明】

１　　ラン抽出部 ２　　矩形抽出処理部 ３　　メモリ ４　　アドレスデコーダ ５　　Ｙ方向カウンタ １１　　矩形データ（ｘ座標）保持用メモリ１２　　ラ
ンデータ保持用メモリ

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　処理中ライン上の着目ランと、処理済
   みの前ライン上のランとの接続関係を調べ、着目ランが
   前ライン上のいずれのランとも接続しない場合に該着目
   ランを新たな矩形として登録し、着目ランが前ライン上
   の１個以上のランと接続している場合、該着目ランを矩
   形とみなし、該矩形と該着目ランに接続している各ラン
   が所属している矩形とを統合することを特徴とする矩形
   抽出方法。
2. 【請求項２】　　処理中ライン上のラン及び前ライン上
   のランの始終点のｘ座標、各ランの所属矩形を指し示す
   ポインタ、矩形の対角点のｘ座標とｙ座標メモリを保有
   するメモリ、このメモリ上のデータに対し請求項１記載
   の矩形抽出処理を実行する処理部、この処理部により処
   理中のラインのｙ座標を保持するカウンタ、及び、前記
   処理部より出力されるアドレスをデコードし前記メモリ
   または前記カウンタを選択するアドレスデコーダを有し
   、前記処理部は矩形抽出処理時に、前記メモリ上の着目
   ランの始終点のｘ座標の記憶アドレスに所定のオフセッ
   トを加算したアドレスを出力することによって前記カウ
   ンタより該着目ランの始終点のｙ座標を取得し、前記メ
   モリ上の矩形のｘ座標の記憶アドレスに前記所定オフセ
   ットを加算したアドレスを出力することにより該矩形の
   ｙ座標を読み取りまたは書き込むことを特徴とする矩形
   抽出装置。