JPH02101588A - 画像処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は、画像情報の輪郭抽出、細線化、特徴抽出、圧
縮処理等の輪郭処理に用いられる画像処理装置に係わり
、特に輪郭追跡に先立つ輪郭検出処理を行なう画像処理
装置に関する。

（従来の技術） 画像の輪郭処理は、画像情報のベクトル化（直線、円弧
近似）、画像の認識／読取り、画像データの圧縮等でし
ばしば用いられる。例えば、線構造の特徴抽出処理を例
にとると、まず、処理の高速化を図るためにラスタ走査
によりリージョンラベリング回路、論理フィルタリング
回路を用いた前処理を行なう。次に細線又は図形の輪郭
を追跡しながら端点、分岐点、角点の検出のための角度
計算を行ない、画像中の線構造の抽出を行なう。即ち、
この処理では線構造の抽出と並行して輪郭追跡が行われ
る。

ところで、このような輪郭追跡処理では、全画像中から
全ての輪郭を重複することなく検出する判定処理をいか
に容易に行なうかが重要となる。

この輪郭検出方法としては、従来、画像メモリに対応し
た１画素ｎビット（ｎ≧　ｌｏｇ２ｍ、　ｍ　；画像中
の輪郭数）のフラグメモリを用意し、各輪郭に対応した
位置にその輪郭の輪郭番号をフラグとして付与する方法
が知られている（電子通信学会研究会資料ＩＢ−７８，
１９７４，ｒ輪郭追跡による２値図形の細線化法の一検
討」）。しかしながら、この方法は検出される輪郭数が
多くなったり、画像が大型化すると、フラグメモリとし
て膨大なメモリ容量が必要となるという欠点があった。

一方、検出された輪郭に１ビットのフラグを割当てる方
法も知られている（　Ｒｏｓｅｕｌ’ｅｌｄ、Ｋａｋ“
旧ｇｌｔａｌ　Ｐｉｃｔｕｒｅ　Ｐｒｏｃｅｓｓｉｎｇ
＋、　Ａｃａｄｅｌｃ　Ｐｒｅｓｓ。

Ｎ、Ｔ　）。しかしながら、この方法は、各輪郭に対し
てマークを付す場合、周囲の８近傍画素とフラグとを参
照しなければならないのでマークの付す処理が複雑であ
り、また検出された輪郭が外輪郭（例えばパターン“０
″の外側の輪郭）であるが、内輪郭（例えばパターン“
０゛の内側の輪郭）であるかの区別が付かないという欠
点があった。特に後者の問題は、文字の特徴パターンの
抽出のため外側輪郭のみを抽出する場合や、細線化の際
に、外側から削る或は内側から削るといった処理を行な
ううえで重要な情報が得られないという問題を発生させ
る。

（発明が解決しようとする課題） このように、従来の輪郭検出処理を行なう画像処理装置
では、膨大なフラグメモリ８瓜を必要としたり、外側輪
郭と内側輪郭との区別がつがず、後の処理に混乱をきた
すという問題があった。

本発明は、上記の問題に鑑みなされたもので、少ないメ
モリ容量で、しかも外側輪郭と内側輪郭とを明確に区別
した状態で画像情報がら重複なく全ての輪郭を検出でき
る画像処理装置を提供することを目的とする。

［発明の構成］ （課題を解決するための手段） 本発明は、画像情報を記憶する画像記憶手段化、この画
像記憶手段に記憶された画像の各画素に対応した１ビッ
トのフラグを格納し得る容量を備えたフラグ記憶手段と
、前記画像記憶手段に格納された画像情報の輪郭を、当
該輪郭を構成する黒画素を一定の側に見ながら追跡する
輪郭追跡手段と、この輪郭追跡手段による輪郭追跡に伴
って前記フラグ記憶手段の各追跡点に対応する位置に第
１のフラグ（これを外フラグと呼ぶ）をセットするとと
もに、前記各追跡点のラスタ方向上流側に前記輪郭を構
成する黒画素が存在している場合に、当該黒画素に対し
てラスタ方向下流側に隣接する白画素に対応した前記フ
ラグ記憶手段の位置に第２のフラグ（これを内フラグと
呼ぶ）をセットするフラグ設定手段と、前記画像記憶手
段°中の画像情報をラスタ走査して、各走査点及びその
近傍の画像情報と前記第１および第２のフラグとから未
検出の輪郭を外輪郭と内輪郭とに識別して検出し、前記
輪郭追跡手段を起動する輪郭検出手段とを具備している
。

（作用） 本発明によれば、輪郭検出手段で検出された輪郭を輪郭
追跡手段で輪郭追跡しながらフラグ設定手段でその追跡
点に１ビットの外フラグをセットしていくとともに１、
内フラグを次の部分にセットしていく。即ち、内フラグ
は、もし画像情報が僅かな厚みを持っていたとしたなら
、その画像情報に対し僅か右側（ラスタ方向下流側）か
ら眺めたときに厚み部分として見える側縁部にセットさ
れる。従って、内フラグは、主に外側輪郭の場合にはラ
スタ方向に対して下流側、内側輪郭の場合にはラスタ方
向に対して上流側に形成されることになる。一方、輪郭
検出部は、画像情報をラスタ走査しながら未検出の輪郭
を順次検出していく。

この時、輪郭検出手段は、検出された輪郭の一部の黒画
素と白画素の配置順序、外フラグがセットされているか
、内フラグがセットされているが等によって、その輪郭
が既に検出済であるかどうか、及び外側輪郭であるか内
側輪郭であるかを容易に知ることができる。

このため、本発明によれば全画像中から全ての輪郭を重
複なく、しかも外側輪郭と内側輪郭とを区別して検出す
ることができる。

しかも、この発明では外フラグは黒画素部分、内フラグ
は白画素部分にセットされるので、これらフラグが同じ
場所に重複してセットされることはない。このため、外
フラグと内フラグとはともに１ビットのフラグで良く、
大画像に対しても小容量のフラグ記憶手段で対処できる
。

（実施例） 以下、図面を参照しながら本発明の実施例について説明
する。

第１図は本発明の一実施例に係る画像処理システムの構
成を示す図である。汎用プロセッサ１は、システムバス
２を介して画像入力装置３、画像メモリ４及びフラグメ
モリ５と接続されている。

フラグメモリ５は、画像メモリ４と同一サイズの二次元
メモリで、画像データの１画素に対して１ビットのフラ
グを格納し得るものとなっている。

処理対象となる図面は、例えば画像入力装置３を介して
二値化入力される。入力された二値画像データは、−旦
、画像メモリ４に格納される。二値画像データが画像メ
モリ４に格納されたら、汎用プロセッサ１は、画像メモ
リ４内の画像データ中の全輪郭を第２図に示す操作に従
って検出する。

即ち、まずフラグメモリ５を全面クリアする（Ｓｌ）。

続いて画像メモリ４をラスタ走査して輪郭上の点を検出
する（Ｓ２）。この輪郭検出は、例えば第６図（ａ）に
示すように、白画素が左隣に配置された黒画素、或は第
７図（ａ）に示すように、白画素が右隣に配置された黒
画素を検出することにより行われる。次に検出された黒
画素は未だ検出されていない輪郭上の点であるがどうが
が調べられる（Ｓ３）。この検索はフラグメモリ５を参
照することにより行われる。即ち、第６図（ａ）に示す
左エツジが検出された場合には、黒画素に対応する位置
のフラグを参照し、フラグが１″であれば既に検出され
た輪郭、“０”であれば未検出の輪郭であると判定する
。また、第７図（ａ）に示す右エツジが検出された場合
には、白画素に対応する位置のフラグを参照し、“１″
であればすでに検出された輪郭、ｉｉ　Ｏｓであれば未
検出の輪郭であると判定する。もし、未検出の輪郭であ
れば汎用プロセッサ１は、その黒画素から輪郭追跡処理
を開始する（Ｓ５）。

輪郭追跡処理は、第５図に示すように、３Ｘ３画素の参
照領域を設定し、現追跡画素の周囲の８つの近傍画素と
現追跡方向（白矢印）とから次の追跡方向（黒矢印）を
決定する処理を、参照領域を追跡方向に順次移動させな
がら繰返すことにより行われる。この追跡処理は、第３
図に示すように、例えば黒画素が左手に位置する向きに
進められる。画像データ中の連結図形がいくつかの穴を
持つとき、その図形の輪郭は画像の背景との境界である
場合と、画像と穴との境界である場合°の２通りがある
。ここでは、前者を外側輪郭、後者を内側輪郭と呼ぶこ
とにすると、第３図に示すように、外側輪郭の追跡方向
は反時計回り、内側輪郭の追跡方向は時計回りとなる。

さて、いまラスタ走査によって第３図の外側輪郭が検出
され、その輪郭追跡が開始されたとする。

この時、汎用プロセッサ１は、追跡処理に附随してフラ
グメモリ５に次の２つのフラグ、即ち外フラグと内フラ
グとをセットしてい＜　　（Ｓ４）。

■　外フラグ フラグメモリ５の追跡点に対応した位置にセットされる
。

■　内フラグ 追跡点の画素の右隣が白画素である場合で、かつ追跡方
向が第８図（ａ）〜（ｇ）のいずれかに示す黒矢印の向
きから入って破線矢印の向きに出ていく場合、白画素に
対応た位置にセットされる。即ち、この内フラグは、ラ
スタ方向の上流側に黒画素を見ながら追跡が行われてい
る場合に、ラスタ方向の下流側の白画素位置にセットさ
れる。

第３図の外側輪郭の追跡に伴ってセットされる外フラグ
を第４図の“１″に、また外側輪郭の追跡に伴ってセッ
トされた内フラグを第４図“２”に示す。同様に、第３
図の内側輪郭の追跡に伴ってセットされる外フラグを第
４図の“３″に、また内側輪郭の追跡に伴ってセットさ
れた内フラグを第４図“４”に示す。なお、これらフラ
グの数値は、説明の便宜上付加したもので、これらフラ
グはすべて１ビット（例えば値“１”）であることはい
うまでもない。このようなフラグのセットを伴う追跡に
よって処理が追跡開始点まで戻ったら、汎用プロセッサ
１は、画像メモリ４を再度ラスタ走査して未検出の輪郭
を検出してい＜（Ｓ５゜Ｓ２）。このとき、既に検出さ
れた輪郭に関して上記のようなフラグがセットされてい
ると、第３図中有手から左手に向かうラスタ走査に伴っ
て、外側輪郭については“０１“　（第６図（ａ）のパ
ターン）、内側輪郭については“１０′　（第７図（ａ
）のパターン）が検出された際、未検出の外側輪郭は、
第６図（ｂ）のように外フラグが立っていない点、未検
出の内側輪郭は、第７図（ｂ）のように内フラグが立っ
ていない点を検出することで、それぞれ区別して検出可
能となる。なお、外フラグは黒画素の部分、内フラグは
白画素の部分にそれぞれセットされるので、両フラグが
同一の部分にセットされることはない。よって、フラグ
メモリ５は、各画素に対して１ビットで十分であること
が分る。

ところで、第８図（ａ）〜（ｇ）の各条件は、第９図に
示すように各追跡方向に０〜７の番号を付けると、 ｄ　ｐｒｅ≧ｄ　ｎｅｘｔ （ｄｐｒｅ：前方向、ｄ　ｎｅｘｔ　：次方向）で表現
できる。これら各方向は３ビットで表現可能であるので
、上記の条件は２Ｇ−６４のエントリを持つテーブルの
形で記述することも可能である。また、ｄ　ｎｅｘｔは
、現画素の８近傍の値と、ｄ　ｐｒｅにより決まるので
、「第７図（ａ）のパターンで、かつ第８図の方向のと
き」という条件は、ｄ　ｐｒｅ　＝　３ビット、近傍値
−８ビットのエントリを持つテーブルで記述し、そのテ
ーブルを各追跡ステップ毎に参照することによりフラグ
をセットするかどうかの判定結果を得ることができる。

第１０図は、上記のようなテーブルも含め、追跡処理の
部分をハードウェア化した場合のシステム構成を示す図
である。汎用プロセッサ１１は、システムバス１２を介
して画像入力１３、画像メモリ１４、細線／輪郭追跡回
路１５、フラグメモリ及びフラグ判定テーブル１７と接
続されている。

また、これら画像人力１３、画像メモリ１４、細線／輪
郭追跡回路１５、フラグメモリ及びフラグ判定テーブル
１７は、画像バス１８を介して画像データのやりとりを
行なう。汎用プロセッサ１１は、画像メモリ１４をラス
タスキャンして、第６図（ａ）のパターン或は第７図（
ａ）のパターンを検出すると、フラグメモリ１６内の対
応する外フラグ又は内フラグがセットされているかどう
かを判定し、もしフラグが立っていない場合には、検出
点のアドレスを細線／輪郭追跡回路１５に送出してこの
回路１５を起動する。細線／輪郭追跡回路１５は、例え
ば内部に設けた３×３のキャッシュメモリに順次追跡点
の画素とその近傍８画素とを格納し、そのパターンと前
の追跡方向とから次の追跡方向を決定していく。このと
き、同時に細線／輪郭追跡回路１５は、画像バス１８を
介してフラグメモリ１６の追跡点に対応した位置に外フ
ラグをセットしていく。また、細・線／輪郭追跡回路１
５は、決定した次の追跡方向と前の追跡方向のデータと
をフラグ判定テーブル１７のエントリとして送出する。

フラグ判定テーブル１７は、エントリ情報が前述した判
定条件に合致していれば、フラグメモリ１６の対応する
追跡点の右隣に内フラグをセットする。細線／輪郭追跡
回路１５が１つの輪郭について追跡処理を終了すると、
汎用プロセッサ１１に追跡終了信号を送出する。汎用プ
ロセッサ１１は、これを受けて再度画像メモリ１４をラ
スタスキャンし、他の未検出の輪郭を検出していく。こ
のような処理を続け、全ての輪郭が検出されたら輪郭の
抽出処理は終了する。この時、得られた各輪郭は、その
最初の検出パターンが第６図のパターンであったか、第
７図のバタ−ンであったかによって外側輪郭であるか内
側輪郭であるかが区別されたものとなっている。

このように、外側輪郭と縁側輪郭とが区別されていると
、例えば内側と外側のいずれか一方の側からの細線化処
理が可能になる等、後の画像処理の適用範囲を大幅に拡
大することができる。

なお、ラスタ走査において、例えば第１１図（ａ）、（
ｂ）に示すようなパターンとのマツチング処理を行ない
、パターンがマツチしたなら、その画素についてなんら
かのマークを付しておくことにより、第１２図（ａ）、
（ｂ）に自矢印で示す方向と次の追跡方向とが一致する
かどうかの簡単な判定だけで内フラグをセットすべきか
どうかの判定を行なうことが可能になる。

また、上記実施例では輪郭の追跡方向が８方向である場
合について説明したが、追跡方向が上下左右の４方向だ
けの場合においても、本発明は適用可能である。また、
輪郭の追跡方向も上記した実施例に限定されないのはい
うまでもない。

［発明の効果コ 以上述べたように、本発明によれば、輪郭追跡に伴って
各輪郭点位置に第１のフラグをセットするとともに、画
像データのラスタ方向下流側の輪郭線の外側に第２のフ
ラグをセットするので、これら２柾類のフラグによって
未検出の輪郭を重複なく、しかも外側輪郭と内側輪郭と
を区別して検出することができる。しかも、これら第１
及び第２のフラグは１ビットで表現可能であり、かつ同
一場所にはセットされないので、フラグ記憶手段も画像
記憶手段と同一サイズで足りるという効果を奏する。

【図面の簡単な説明】

第１図は本発明の一実施例に係る画像処理装置のブロッ
ク図、第２図は同装置における輪郭検出・輪郭追跡処理
の流れ図、第３図は同装置におけるラスタ走査方向と輪
郭検出方向とを示す図、第４図は第３図の画像に対応し
たフラグメモリの内容を示す図、第５図は同装置におけ
る輪郭追跡処理を説明するための図、第６図は同装置に
おける外側輪郭の検出パターンを示す図、第７図は同装
置における内側輪郭の検出パターンを示す図、第８図は
同装置における内フラグのセット条件を示す図、第９図
は本発明の他の実施例における輪郭追跡方向を示す図、
第１０図は同実施例に係る画像処理装置のブロック図、
第１１図および第１２図は本発明の更に他の実施例に係
る画像処理装置を説明するための図である。 １．１１・・・汎用プロセッサ、２．１２・・・システ
ムバス、３．１３・・・画像入力装置、４．１４・・・
画像メモリ、５．１６・・・フラグメモリ、１５・・・
細線／輪郭追跡回路、１７・・・フラグ判定テーブル、
１８・・・画像バス。 第１図 出願人代理人　弁理士　鈴江武彦 第３図 第４図 第 図 第５ 図 （ａ） （ｂ） （ａ） （ｂ） 第６図 第７ 図 （ａ） （ｂ） （ｃ） （９ン 第 図

Claims (1)

1. 【特許請求の範囲】 画像情報を記憶する画像記憶手段と、 この画像記憶手段に記憶された画像の各画素に対応した
   １ビットのフラグを格納し得る容量を備えたフラグ記憶
   手段と、 前記画像記憶手段に格納された画像情報の輪郭を、当該
   輪郭を構成する黒画素を一定の側に見ながら追跡する輪
   郭追跡手段と、 この輪郭追跡手段による輪郭追跡に伴って前記フラグ記
   憶手段の各追跡点に対応する位置に第１のフラグをセッ
   トするとともに、前記各追跡点のラスタ方向上流側に前
   記輪郭を構成する黒画素が存在している場合に、当該黒
   画素に対してラスタ方向下流側に隣接する白画素に対応
   した前記フラグ記憶手段の位置に第２のフラグをセット
   するフラグ設定手段と、 前記画像記憶手段中の画像情報をラスタ走査して、各走
   査点及びその近傍の画像情報と前記第１及び第２のフラ
   グとから未検出の輪郭を外輪郭と内輪郭とに識別して検
   出し、前記輪郭追跡手段を起動する輪郭検出手段とを具
   備したことを特徴とする画像処理装置。