JPS61129974A - 図形処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 く技術分野〉 この発明は図形処理装置に関し、さらに詳細にいえば、
変化点アドレスデータ（画素座標値）により表現された
画像データを論理演算し、その画像図形を演算処理する
図形処理装置に関する。

〈従来技術〉 ファクシミリ装置等のインテリジェント化を図る場合に
は、各走査線間の画素データの連結状態を検出して原稿
に記載された記号、図形等を認識する必要がある。

従来、読取装置で読取られ、白レベル画素を“Ｏ″、黒
レベル画素を″１′°として２値化された画像データに
ついて、その画像図形の面積、或は外接長方形等を計算
するためには、先ず、各画素毎に演算処理を施して黒レ
ベル画素の連結領域に分割し、各領域の黒レベル画素の
数を係数する手法が用いられていた。

しかし、このような画像処理では、各画素が処理単位と
なるので、処理すべき画像データ量が多くなり、処理時
間が長くなるという不都合を有しており、汎用計算機を
用いて処理する場合にはピット操作が必要となり、効率
が悪くなるという不都合を有している。

そこで、処理画像データ数を減少させるために、１走査
線Ｍ個の画素に対して、順番に○から（Ｍ−１）の番号
をつけ、画素レベルが白から黒、または黒から白へ変化
した時点の画素番号（画素アドレス）でもって画像内容
を表す（変化点アドレス表現する）ことが考えられる。

本件発明者は、上記の方法による図形処理装置について
、特開昭５８−１４２４６７号公報、および特開昭５８
−１４２４６８号公報に示す新規な図形処理装置を発明
した。

これら発明によれば、処理すべき画像データ量を少なく
して処理時間を短縮でき、しかも汎用計算機を用いて黒
領域の面積、外接長方形等を計ねする場合に、簡単なア
ルゴリズムを用いて、比較的高速に、１回の走査のみで
同時に計算することができるという利点を有している。

しかしながら、面積、外接長方形等の算出は、画像認識
処理の１段階として行なわれることが多く、画像認識処
理全体としてみれば、文字、図形としての黒領域のみな
らず、背景としての白領域についても面積、外接長方形
等の算出をも行なわなければならない。そして、上記発
明は、黒領域についてのみ、面積、外接長方形等の算出
を行なうものであるから、上記黒領域、および白領域に
ついて面積、外接長方形等の算出を行なおうとすれば、
１回の走査を行なって黒領域に対する図形処理を行なっ
た後、白領域と黒領域とを反転させる処理を行ない、次
いで反転処理されたデータに対して、１回走査すること
により白領域（反転後の黒領域）に対する図形処理を行
なう必要がある。

即ら、白領域と黒領域とについて図形処理を行なおうと
すれば、走査回数が多くなり、全体としての処理時間が
長くなるという不都合がある。

く目的〉 この発明は上記の問題点に鑑みてなされたものであり、
簡単なアルゴリズムを用いて、１回走査を行なうのみで
、黒領域、および白領域の双方についての図形処理を行
なうことができる図形処理装置を提供することを目的と
している。

〈構成〉 十記の目的を達成するための、この発明の図形処理装置
は、判定手段と、記憶テーブルと、演算手段とを具備し
ており、判定手段は、隣接する両走査線の変化点アドレ
ス値をその４順に比較するとともに、その比較結果に応
じて予め定められた複数の連結画素パターンに分離判定
し、さらに走査開始部分、および走査終了部分をも予め
定められた複数の連結画素パターンに分離判定するもの
であり、記憶テーブルは、白データ、黒データ毎に、上
記判定結果に基いてラン状態を記憶するものであり、演
算手段は、Ｌ記判定結果に応じて走査線の変化点アドレ
スデータ、および上記記憶テーブルの内容を演算処理す
るものである。

したがって、判定手段によって、１回の走査により得ら
れる、走査線の全範囲について画素連結パターンに分離
判定し、この判定結果に基いて白データ、黒データ毎に
ラン状態を記憶テーブルに記憶させ、演算手段によって
、必要な演算処理を行ない、もって図形処理を行なうこ
とができる。

促し、演算手段としては、連結画素領域の面積を算出す
るものであってもよく、或は連結画素領域に外接する外
接長方形の座標値を算出するものであってもよい。

〈実施例〉 以下、実施例を示ず添付図面によって詳細に説明する。

先ず、画像データの処理は、走査線単位に、そして、走
査線番号順に行なわれる。即ち、走査入力される画像デ
ータＡは、変化点数を■とすると、第２図のように示さ
れ、これら各変化点アドレスデータａ（Ｉｌ）［＋１＝
１．２・ＰＩは、０からＭまでの間の画素アドレス値を
とり、昇順（ａ（１））＜ａ（Ｅｌ＋１））に配列され
ている。尚、この走査線Ａの変化点アドレスデータには
内部の処理の必要性から、そのデータＷＪ　＋７）　最
１　ニ、ＨＸＩ（＞Ｈ）、＋４２２（＞ＨＸｆ）　（７
）　２データが付加されている。

また、隣接走査線にまたがる画素の連結領域を知るため
には、現在、処理を行なっている走査線Ａの１つ前の走
査線の画像データＢが必要となる。

この場合の変化点数をＪとすると、第３図に示すように
、その各変化点アドレスデータはｂ（ｑ）［ｑ＝１．２
・・・Ｑ］となり、走査線△の場合と同様に、そのデー
タ列の最後にはＨＸＩ　、　ＨＸ２が付加されている。

第１図は図形処理装置を示すブロック図であり、操作に
よりｉｑられる画１９データＡを、隣接する両走査線の
変化点アドレス値をその昇順に比較するとともに、その
比較結果に応じて予め定められた複数の連結画素パター
ンに分離判定し、さらに走査開始部分、および走査終了
部分をも予め定められた複数の連結画素パターンに分離
判定する判定手段（１）に印加し、判定手段〔１）の出
力信号を、白データ、黒データ毎に、上記判定結果に基
いてラン状態を記憶する記憶テーブル（２１に印加し、
上記判定手段（１）の出力信号に応じて、走査線の変化
点アドレスデータ、および上記記憶テーブル（２の記憶
データを演算手段（３）に印加している。

次いで、第４図乃至第７図を参照して図形処理動作を詳
細に説明する。

第４図のフローチャートは、図形処理全体の動作を説明
するものであり、ステップ■において、ｐｌｑをそれぞ
れ１に初期設定し、ステップ■において最初のランの処
理を行ない、ステップ■において黒領域か否かを判別す
る。

そして、黒領域でなければ、ステップ■においてレコー
ドエンドか否か、即ち、ｐトｑ≧トＮ−２か否かを判別
し、レコードエンドであれば、ステップ■において最後
のランの処理を行なう。もし、レコードエンドでなけれ
ば、ステップ■■においてＴＩ、Ｔ２の判別を行なう。

ここで、Ｔ１であると判別されれば、ステップ■におい
て８１の処理を行ない、ステップ■においてＷ４の処理
を行ない、ステップ［相］においてｐを２だけ増加さぼ
、再びステップ■以下の判別、処理を行なう。また、Ｔ
２であると判別されれば、ステップ■において８２の処
理を行ない、ステップ■においてＷ５の処理を行ない、
ステップ［相］においてｑを２だけ増加させ、再びステ
ップ■以下の判別、処理を行なう。また、Ｔ１でもＴ２
でもないと判別されれば、ステップ■において８３の処
理を行ない、ステップ■においてＷ６の処理を行ない、
ステップ［相］においてｐ、Ｑを１だけ増加させ、次い
でステップ＠の判別を行なう。

一方、ステップ■において黒領域であると判別された場
合には、ステップ■においてレコードエンドであるか否
かを判別し、レコードエンドであれば、ステップ■にお
いて最後のランの処理を行なう。もし、レコードエンド
でなければ、ステップ■［相］においてＴ３、Ｔ４の判
別を行なう。ここで、Ｔ３であると判別されれば、ステ
ップ■において８４の処理を行ない、ステップ０におい
てＷｌの処理を行ない、ステップ［相］においてｐを２
だけ増加させ、再びステップＯ以下の判別、処理を行な
う。また、Ｔ４であると判別されれば、ステップ■にお
いて８５の処理を行ない、ステップ［相］においてＷ２
の処理を行ない、ステップ■においてｑを２だけ増加さ
せ、再びステップ＠以下の判別、処理を行なう。また、
Ｔ３でもＴ４でもない場合には、ステップＯにおいて８
６の処理を行ない、ステップ［相］においてＷ３の処理
を行ない、ステップＯにおいてｐ、ｑを１だけ増加させ
、再びステップ■以下の判別、処理を行なう。

Ｍ５図は上記ステップ■の最初のランを処理するための
フローチャートを示し、ステップ■においてａ（１）が
“′０″であるか否かを判別する。

そして、ａ（１）が′０″であれば、ステップ■におい
てｂ（１）が１１０１１であるか否かを判別し、ＩＩ　
Ｏ１１であれば、ステップ■において８３の処理を行な
い、ステップ■においてり、Ｑを１だけ増加させる。

また、ｂ（１）が°Ｏ′でなければ、ステップ■におい
てａ（２）とｂ（１）との大小関係を判別し、ａ（２）
≧ｂ（１）であれば、ステップ■においてＷ２Ｂ５の処
理を行ない、ステップ■において８３の処理を行ない、
ステップ■においてり、Ｑを１だけ増加さゼる。もし、
ａ（２）＜　ｂ（１）であれば、ステップ■において８
１の処理を行ない、ステップ■においてＷ３Ｂ８の処理
を行ない、ステップ■においてｐを２だけ増加させる。

一方、ａ（１）が０′°でなければ、ステップ＠におい
てｂ（１）が０１１か否かを判別し、“０パでなければ
、ステップ［相］においてＷ３Ｃ８の処理を行なう。ま
た、ｂ（１）が“０″′であれば、ステップ■において
ａ（１）とｂ（２）との大小関係を判別し、ａ（１）＞
ｂ（２）であれば、ステップ■において８２の処理を行
ない、ステップ［相］においてＷ３ＡＳの処理を行ない
、ステップＯにおいてｑを２だけ増加させる。もし、ａ
（１）≦ｂ（２）であれば、ステップ［相］においてＷ
Ｉ　ＡＳの処理を行ない、ステップ［相］においてＢ３
の処理を行ない、ステップ［相］においてｐｌｑを１だ
け増加させる。

そして、以上の場合において、ステップ■■［相］の処
理を行なった後は、第４図のフローチャートのステップ
Ｏ以下の判別、処理を行ない、上記ステップ■［相］Ｏ
の処理を行なった後は、第４図のフローチャートのステ
ップ■以下の判別、処理を行なう。

尚、上記第５図のフローチャートは８連結の場合に対応
するものであるが、ステップ■における判別をａ（２）
＞　ｂ（１）か、ａ（２）≦ｂ（１）かによって行なう
とともに、ステップ■における判別をａ（１）≧ｂ（２
）か、ａ（１）＜ｂ（２）かによって行なえば、４連結
の場合に対応するものとすることができる。

第６図は第４図のステップ■の最後のランを処理するた
めのフロ・−チャートを示し、ステップ■■において、
ａ（ｐ）＝Ｍであるか否か、およびｂ（ｑ）＝Ｍである
か否かを判別する。ａ（ｐ）＝Ｍでなければステップ■
においてＷｌＡＥ、お−よびＢ６の処理を行な、う。ま
た、ａ（ｐ）−Ｍであって、しかもｂ（ｑ）＝Ｍでなけ
ればステップ■においてＷ２ＢＥ１およびＢ６の処理を
行なう。もし、ａ（ｐ）＝　Ｍであって、しかもｂ（ａ
）＝Ｍであればステップ■において８６の処理を行なう
。

そして、以上の場合において、ステップ■■■の処理を
行なった後は上記第４図のフローチャートの判別、処理
を終了する。

第７図は第４図のステップ［相］の最後のランを処理す
るためのフローチャートを示し、ステップ■において残
りデータ数が“ＯＮであるか否かを判別し、残りデータ
数が“Ｏ１１でなければ、ステップ■■においてａ（１
））＝Ｍであるか否か、およびｂ（Ｑ）＝Ｍであるか否
かを判別する。ａ（１））＝Ｍであればステップ■にお
いて８２、およびＷ６ＡＥの処理を行なう。また、ｂ（
Ｑ）＝Ｍであって、しかもａ（ｐ）−Ｍでなければステ
ップ■において８１、およびＷ６８Ｅの処理を行なう。

もし、ａ（ｐ）＝Ｍでなく、しかもｂ（Ｑ）＝　Ｍでな
ければステップ■においてＷ６０Ｅの処理を行なう。ま
た、ステップ■において残りデータ数が０″であると判
別された場合にもステップ■の処理を行なう。

そして、以上の場合において、ステップ■■■の処理を
行なった後は上記第４図のフローチャートの判別、処理
を終了する。

但し、上記連結画素状態Ｗ１〜Ｗ６．８１〜Ｂ６を元の
白、黒２値信号で表すと、第８図のとおりである。即ち
、Ｂ１はＡだけに黒ランが１つある状態を示し、Ｂ２は
Ｂだけに黒ランが１つある状態を示し、Ｂ３はＡ、Ｂで
連結した黒ランが検出された状態を示し、８４〜Ｂ６は
、それぞれ１〜Ｂ３状態を白黒反転させた状態を示し、
Ｗ１〜Ｗ３はそれぞれ８４〜Ｂ６状態と同じ状態を示し
、Ｗ４〜Ｗ６はそれぞれ８１〜Ｂ３状態と同じ状態を示
している。第８図から明らかなように、８１〜Ｂ３．Ｗ
４〜Ｗ６状態は、両走査線の前の状態としてＷｌ、Ｗ２
．８３であることが必要であり、８４〜８６．Ｗ１〜Ｗ
３状態は、前の状態としてＷ３，８１．８２であること
が必要である。

また、最初のランの連結画素状態Ｗ３Ｃ８；Ｂ１および
Ｗ３ＢＳ、Ｂ２およびＷ３△Ｓ、ＷＩＡＳおよびＢ３、
Ｗ２Ｂ５およびＢ３、Ｂ３を元の白、黒２ｆｉｉ信号で
表すと、第９図のとおりである。

即ち、Ｗ３Ｃ８はＡ、８で連結した白ランがある状態を
示し、Ｂ１およびＷ３ＢＳはＡだ【プに黒ランが１つあ
る状態を示し、Ｂ２およびＷ３ＡＳはＢだけに黒ランが
１つある状態を示し、ＷＩＡＳおよびＢ３はＡだけに白
ランが１つある状態を示し、Ｗ２Ｂ５およびＢ３はＢだ
けに白ランが１つある状態を示し、Ｂ３はＡ、Ｂで連結
した黒ランがある状態を示している。

また、最後のランの連結画素状態Ｗ６ＣＥ、Ｂ１および
Ｗ６ＢＥ、８２およびＷ６ＡＥ、ＷｌＡＥおよびＢ６、
Ｗ２ＢＥおよびＢ６、Ｂ６を元の白、黒２値信丹で表す
と、第１０図のとおりである。

即ち、Ｗ６０ＥはＡ、Ｂで連結した白ランがある状態を
示し、Ｂ１およびＷ６ＢＥはＡだけに黒ランが１つある
状態を示し、Ｂ２およびＷ６ＡＥはＢだりに思ランが１
つある状態を示し、ＷＩＡＥおよびＢ６はＡだけに白ラ
ンが１つある状態を示し、Ｗ２ＢＥおよびＢ６はＢだけ
に白ランが１つある状態を示し、Ｂ６はＡ、Ｂで連結し
た黒ランがある状態を示している。

尚、連結領域の判定との関係では、厳密には正確ではな
いが、概念的には、Ｂ１は新たな黒の連結領域が検出さ
れたことを示し、Ｂ２は黒の連結領域がなくなったこと
を示し、Ｂ３は黒の連結領域が続いていることを示し、
Ｂ４は黒の連結領域が分裂していくことを示し、Ｂ５は
２つの黒の連結領域が接続したことを示し、Ｗ１〜Ｗ６
は白の連結領域について、上記８１〜Ｂ６に対応する状
態を示している。

また、上記の分離判定のための必要十分条件は第１１図
に示すとおりである。連結条件として４連結と８連結が
あるが、それにより、必要十分条件は異なったものとな
る。そして、第４図のフローチャートのステップ■■［
相］［相］の判別条件Ｔ１〜Ｔ４は、それぞれＢ１およ
びＷ４、Ｂ２およびＷ５、Ｂ４およびＷｌ、８５および
Ｗ２の必要十分条件と等しく設定されている。

ところで、連結画素領域の面積を計算するためには、処
理を行なっている走査線までの途中結果を入れるテーブ
ルが必要であり、その構成としては第１２図に示すとお
りであり、それぞれのエリアは各連結領域に対応してい
る。そして、Ｃ０ＮＴはコン１〜ロール用であり、（ｒ
ｅｓ）＝１は、その連結領域の演算が終了し、′ｒｆＪ
積が求まったことを示しており、（ＡＣＴ）＝１は、そ
のエリアが連結領域に割当てられ、面積を計算中である
ことを示している。また、Ｓは演算出力、即ち、面積を
いれるためのものである。

また、第１３図は面積を算出するための処理を示す図で
あり、状態８１〜Ｂ６に対して図示の処理を行なうこと
により黒の連結領域の面積を算出することができ、状ｆ
ｆＷ１〜Ｗ６に対して図示の処理を行なうことにより黒
の連結領域の面積を算出することができる。

他方、第１２図のテーブルの構成、および第１３図の処
理を、それぞれ第１４図、第１５図に示すように変更す
ることにより、連結領域の外接長方形（アドレス座標点
）を算出することができる。

く効果〉 以上のようにこの発明は、１回の走査により読取られ、
２値化された画素データに基いて、最初の白ラン部分、
および最後の白ラン部分をも考慮した簡単なアルゴリズ
ムで白の連結領域、黒の連結領域の面積、外接長方形等
を算出することができるようにしているので、処理ＦＲ
間を大幅に短縮することができるという特有の効果を奏
する。

【図面の簡単な説明】

第１図は図形処理装置を示すブロック図、第２図および
第３図は変化点アドレス表現された各走査線の画像デー
タを示すデータ説明図、第４図乃至第７図は図形処理動
作を示すフローチャート、 第８図乃至第１０図は連結画素状態を示すパターン図、 第１１図は連結画素状態を判定するための必要十分条件
を示す説明図、 第１２図は面積を算出するための記憶テーブルの構成を
示す図、 第１３図は面積算出のための処理動作を示す説明図、 第１４図は外接長方形を算出するための記憶テーブルの
構成を示す図、 第１５図は外接長り形算出のための処理動作を示す説明
図。

Claims (1)

1. 【特許請求の範囲】 １、走査入力される２値化画像データを変 化点アドレス情報に変換し、その変化点 アドレス値（画素座標値）を用いて２つ の走査線の対応画素を論理演算する図形 処理装置において、上記隣接する両走査 線の変化点アドレス値をその昇順に比較 するとともに、その比較結果に応じて予 め定められた複数の連結画素パターンに 分離判定し、さらに走査開始部分、およ び走査終了部分をも予め定められた複数 の連結画素パターンに分離判定する判定 手段と、白データ、黒データ毎に、上記 判定結果に基いてラン状態を記憶する記 憶テーブルと、上記判定結果に応じて走 査線の変化点アドレスデータ、および上 記記憶テーブルの内容を演算処理する演 算手段とを具備することを特徴とする図 形処理装置。 ２、演算手段が、連結画素領域の面積を算 出するものである上記特許請求の範囲第 １項記載の図形処理装置。 ３、演算手段が、連結画素領域に外接する 外接長方形の座標値を算出するものであ る上記特許請求の範囲第１項記載の図形 処理装置。