JPS61121176A - 階層的図形処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、階層的図形処理方式に関する。

一般に、建物や道路等が存在する市街地を地図上に明確
に表現するには、「１」かｒＯＪかの二値入力を方向性
を持ったベクトル量として図形処理を行う。この場合、
市街地をいくつかの矩形領域に分割して１つの矩形内の
図形が直線として把握されるまで、該矩形をその中の図
形の線密度に対応して該矩形の状態で処理を終了するか
該矩形を階層的に再分割するかを判断する方式が、図形
処理の効率上は望ましい。

〔従来の技術および発明が解決しようとする間第点〕

従来の図形処理方式は、第６図（Ａ）に示すように、図
形を一定間隔の矩形領域に分割して処理していた。

例えば矩形αに関しては端点Ａ　（ｘ＋　　、ｙ＋）と
Ｂ（ｘｚ　　、ｙｚ）、ｃ（ｘｚ、ｙｚ）とＤ（ＸＪ、
７１）が（第６図（Ｂ））、矩形βに関しては端点Ｅ（
ＸＳＩｙ５）とＦ（Ｘｂ、’Ｊｈ）が（第６図（Ｃ））
図形処理の基準となり、更に矩形γに関してはその中に
図形は現れていない（第６図（Ｄ））。

しかし、矩形βに関しては（第６図（Ｃ））端点ＥとＦ
を結べば直線図形として地図上に表現することができる
が、矩形αに関しては（第６図（Ｂ））車に端点ＡとＢ
、ＣとＤを把握しただけでは、各変曲点ａ、ｂが存在す
るため図形は正確に把握できない。

従って、矩形βについては図形処理は終了しているが、
矩形αについては図形処理は厳密に終了しているとはい
えない。

更に、矩形γに関しては、何ら図形は現れていないので
、図形処理の対象外になる。

従来方式では、上述のように、同じ大きさの矩形領域に
図形を分割することにより処理していたため、図形の線
密度に応じた処理が不可能であり、処理効率が低いとい
う問題点があった。

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

本発明によれば、入力図形を格納する画像メモリ、該画
像メモリに格納された上記入力図形を所定の数の矩形領
域に分割して読み出す画像メモリアドレスコントローラ
、上記分割領域ごとの図形を格納する矩形領域バッファ
、上記画像メモリアドレスコントローラの指令を受けて
上記メモリから上記バッファに図形を書き込む矩形領域
バッファアドレスコントローラから成る矩形領域分割部
と、上記矩形領域バッファアドレスコントローラにより
読み出された上記バッファの図形の特徴を抽出する特徴
抽出部と、上記特徴が直線部又は空白部である既知カテ
ゴリかそれ以外の未知カテゴリかを判定する判定回路、
上記既知カテゴリであれば図形を出力バッファへ送出し
未知カテゴリであれば上記矩形領域分割部の画像メモリ
アドレスコントローラに再分割命令を送信する階層制御
回路から成る判定部を設け、上記入力図形を上記矩形領
域分割部により上記所定の数の領域に分割し該分割領域
図形の特徴を上記特徴抽出部により抽出した結果、上記
判定部によって既知カテゴリと判定された場合は上記入
力図形を出力バッファに送出して該図形の処理を終了さ
せ、未知カテゴリと判定された場合は上記入力図形を上
記矩形領域分割部によって上記所定の数と同じ矩形領域
に再分割することにより以後同じ操作をすべての分割領
域図形が上記既知カテゴリに属するまで階層的に行うこ
とを特徴とする階層的図形処理方式が提供される。

〔作　用〕

本発明方式は、図形を矩形で分割していく過程で該矩形
内が直線部か空白部か又はそれ以外の複雄部かの各分割
矩形領域ごとにその特徴を抽出し、直線部か空白部かの
既知カテゴリであれば該分割矩形領域をコード化して分
割を終了し、複雑部から成る未知カテゴリであれば図形
処理は終了していないと判断して該図形を更に細分割す
ることができるので、同一処理を図形の線密度状態に応
じて階層的に反復繰り返し行うことができ図形処理効率
の向上が期待できる。

〔実施例〕

以下、本発明を実施例により添付図面を参照して説明す
る。

第１図は本発明の特徴を示す図である。即ち、本発明は
「１」か「０」かの二値で表現された図形を入力しく■
）、それを一定の大きさの矩形領域で４分割すると共に
（■）該領域の特徴を３つに分類して把握しく■）、空
白部、直線部以外の複雑部であれば（■）該領域を更に
４分割して同一の処理を行い（■、■）、空白部、直線
部であれば処理を終了する。

第１図において、分割工程（■）は先ず入力図形を４分
割することから開始される（第２図（Ａ））。

そして、この４分割された領域ｄについてその特徴抽出
が行われる（■）。

この特徴は、３種類のカテゴリからなり、第３図（Ａ）
の空白部、第３図（Ｂ）の直線部、第３図（Ｃ）の複雑
部であり、この複雑部は上記空白部、直線部以外の場合
である。このように、どのような図形も直線の組合わせ
と考えて処理するのを折線近似処理方式といい、以下述
べる例はこの折線近似処理に適用した場合である。

上記３つのカテゴリのうちで空白部又は直線部と判定さ
れた領域ｄ１□、ｄｌ：ｌ（第２図（Ａ））については
処理は終了するが、複雑部と判定された領域ｄｌｌ＋ｄ
１４については更にこの領域を矩形により４分割する（
第２図（Ｂ））。

次にｄｌｌ＋ｄ１４について３つのいずれか（第３図）
の特徴を抽出する（第１図■）。

判定の結果、複雑部（第３図（Ｃ））と判断された領域
ｄＩＩＩ　　＋　ｄ１４１　について更に４分割を行う
（第２図（Ｃ））。

そして、このｄｌ。＋ｄ１４１について特徴抽出を行っ
て（■）、判定の結果、複雑部と判断された領域ｄ　１
１１１　＋　ｄ１４□につき再び特徴抽出を行う（第１
図■）。

このようにして、空白部か直線部かの既知カテゴリであ
れば処理を終了し、複雑部である未知カテゴリであれば
更に領域を４分割して特徴を抽出するという同一操作を
繰り返す。尚、第１図の２■、２■、２■及び３■、３
■、３■はそれぞれ第２図（Ａ）　、　（Ｂ）　、　（
Ｃ）及び第３図（Ａ）、（Ｂ）、（Ｃ）　’に対応して
いる。

第４図は、本発明方式の一実施例を示すフローチャート
である。また第５図は第４図の方式に従って図形が処理
されている過程を模式的に表した図である。

第４図において、入力図形はファクシミリやドラムスキ
ャナ等から入力された二値画像であり、画像メモリ１は
この入力図形を以後の処理のために格納するメモリ、画
像メモリアドレスコントローラ２は上記画像メモリ１に
格納された図形データを４分割した矩形領域ごとに読み
出す装置、矩形領域バッファ３は上記コントローラ２に
より読み出された領域の図形を格納するバッファ、矩形
領域バッファアドレスコントローラ４は上記メモリから
上記バッファへ指定された矩形領域の図形を書き込む装
置、特徴抽出回路５はバッファ３に書き込まれた図形の
特徴を抽出する回路、判定回路６は上記回路５により抽
出された特徴を空白部、直線部、複雑部の３つのカテゴ
リに分類する回路、階層制御回路７は上記判定回路６の
分類結果に基づいて空白部又は直線部の場合は該領域の
図形を次段の出力バッファ８へ送出し、複雑部の場合は
再分割するための指示をメモリアドレスコントローラ２
へ与えて画像メモリ１に格納された図形を階層的に分割
する回路、出力バッファ８は処理が終了した図形を格納
するバッファである。

また第４図と第１図との関係は、画像メモリ１とメモリ
アドレスコントローラ２と矩形領域バッファ３とバッフ
ァアドレスコントローラ４によって第１図の特徴図に示
す矩形領域分割（■）が行われ、判定回路６と階層制御
回路７によって空白部又は直線部の既知カテゴリがそれ
以外の複雑部である未知カテゴリかの判断がされる（■
）。

上記■に相・当する部分を矩形領域分割部、■に相当す
る部分を特徴抽出部、■に相当する部分を判定部と称す
る。

以下、上記第４図の動作を第５図に基づいて説明する。

先ず入力図形ｋ（第５図（Ａ））を画像メモリーにすべ
て格納する。この格納された図形にはまだ矩形領域に分
割する前のものであって、第５図（Ａ）の斜線部分が図
形に相当する。

次にメモリアドレスコントローラ２が、画像メモリー内
のアドレスを制御することにより図形にの４つの領域に
＋　　、ｋｔ　　、に３　、ｋａを読み出す（第５図（
Ａ））。これにより図形には４つの矩形領域に分割され
たが、このときバッファアドレスコントローラ４は前記
コントローラ２の指令を受けて（破線矢印）各に、、ｋ
ｔ　、に、、に４を矩形領域バッファ３の所定アドレス
空間に書き込む。

ここまでの関係を図示すれば、第５図（Ｂ）のようにな
り、ｋは分割前の図形、ｋ、、ｋｚ　、に、。

ｋ４は上記の分割後の各図形である。

その後バッファアドレスコントローラ４がバッファ３か
ら上記各に、、に２　、に、、に４を読み出して次段の
抽出回路５により各特徴を抽出すると共に判定回路６に
より３つのカテゴリに分類する（第３図（Ａ）　（Ｂ）
　（Ｃ）　）。

その結果は、第５図（＾）から明らかなように、ｋＩは
直線部（第３図（Ｂ））、ｋ２とに、とに４はいずれも
複雑部である（第３図（Ｃ））。

第５図（Ｂ）において、◎印は直線部を、Ｏ印は複雑部
を、それぞれ示している。

従って、階層制御回路７はに１については端点（ｘ＋、
ｙ＋）と（ｘｚ、ｙｚ）により表される直線図形を直ち
に出力バッファ８に格納することによりに、の処理は終
了する（第５図（Ｂ））。しかし、制御回路７は、残り
のに２からに４までについては更に階層的に分割すべく
コントローラ２に支持する（第４図）。

階層的分割支持を受けたコントローラ２は、ｋ２ないし
に４を更に分割するためにｋＺｌ、ｋＺ□。

ｋ　２３＋　ｋ　１４とｋｆｆ＋、ｋｆｆ□＋　ｋ　３
３１　ｋ　３４とに４１゜ｋ４□＋　　ｋ　４３　＋　
ｋ　４４をメモリ１から読み出すと共にコントローラ４
に書き込み信号を送出して該コントローラ４の制御によ
って上記再分割されたｋＺｌからに４４までをバッファ
３に書き込ませる。

以下、特徴抽出回路５、判定回路６、階層制御回路７に
よって上記に、からに４に関してと同様の処理を行った
結果が第５図（Ｂ）に示されている。

即ちｋＺｌ、ｋｔｔ、ｋ　４１　＋　ｋ　４Ｚについて
は複雑部と判断され更にコントローラ２により再分割領
域が読み出されるが、ｋｚ２　＊　ｋｔａ　＊　ｋＺｌ
　ｒ　ｋｘｔ　＋に３４については直線部またはｋ　３
３　＋　ｋ　４３　＋　ｋ　４４については空白部（・
印）と判断されて該領域図形が出力バッファ８に格納さ
れて図形処理は終了する。

〔発明の効果〕

上記のとおり、本発明によれば、図形を矩形で分割して
いく過程で該矩形内が直線部か空白部か又はそれ以外の
複雑部かの各分割矩形領域ごとにその特徴を抽出し、直
線部か空白部かの既知カテゴリであれば該分割矩形領域
をコード化して分割を終了し、？ｊ！錐部から成る未知
カテゴリであれば図形処理は終了していないと判断して
該図形を更に細分割することができるので、同一処理を
図形の線密度状態に応じて階層的に反復繰り返し行うこ
とができ図形処理効率の向上が期待できる。

【図面の簡単な説明】

第１図は本発明の特徴を示す図、 第２図は第１図における分割工程を示す図、第３図は第
１図における特徴を示す図、第４図は本発明方式のフロ
ーチャート、第５図は第４図の動作説明図、 第６図（Ａ）〜（Ｄ）従来方式の説明図である。 ■・・・画像メモリ、 ２・・・画像メモリアドレスコントローラ、３・・・矩
形領域バッファ、 ４・・・矩形ｊＩ　域バッファアドレスコントローラ、
５・・・特徴抽出１ｌｉ２回路、　６・・・判定回路、
７・・・階層制御回路、　８・・・出力バッファ、■・
・・入力図形、　　　■・・・矩形領域分割部、■・・
・特徴抽出部、　　■・・・判定部。

Claims (1)

【特許請求の範囲】
1. 入力図形を格納する画像メモリ、該画像メモリに格納さ
   れた上記入力図形を所定の数の矩形領域に分割して読み
   出す画像メモリアドレスコントローラ、上記分割領域ご
   との図形を格納する矩形領域バッファ、上記画像メモリ
   アドレスコントローラの指令を受けて上記メモリから上
   記バッファに図形を書き込む矩形領域バッファアドレス
   コントローラから成る矩形領域分割部と、上記矩形領域
   バッファアドレスコントローラにより読み出された上記
   バッファの図形の特徴を抽出する特徴抽出部と、上記特
   徴が直線部又は空白部である既知カテゴリかそれ以外の
   未知カテゴリかを判定する判定回路、上記既知カテゴリ
   であれば図形を出力バッファへ送出し未知カテゴリであ
   れば上記矩形領域分割部の画像メモリアドレスコントロ
   ーラに再分割命令を送信する階層制御回路から成る判定
   部を設け、上記入力図形を上記矩形領域分割部により上
   記所定の数の領域に分割し該分割領域図形の特徴を上記
   特徴抽出部により抽出した結果、上記判定部によって既
   知カテゴリと判定された場合は上記入力図形を出力バッ
   ファに送出して該図形の処理を終了させ、未知カテゴリ
   と判定された場合は上記入力図形を上記矩形領域分割部
   によって上記所定の数と同じ矩形領域に再分割すること
   により以後同じ操作をすべての分割領域図形が上記既知
   カテゴリに属するまで階層的に行うことを特徴とする階
   層的図形処理方式。