JPH0512444A - １画面１走査型特徴量計測装置 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 １画面１走査で正確に特徴量を計測でき、回
路構成も簡略化する。 【構成】 ラスタ走査で入力されるビデオ信号をＡ／Ｄ
変換して２値化画素とする手段、ディレイを用いて走査
している画素とこの画素の左，上，左上という２×２の
４画素を取得する手段、この４画素より表１のラベル発
行規則に基づいてラベル・フラグを発行する手段、この
ラベル・フラグにより同一図形に同一ラベルを発行する
手段、同一ラベルを持つ図形の特徴量を逐次積算してい
く手段、ディレイを用いて上及び左の画素に付けられた
ラベルを保持しておく手段を備え、表１のラベル発行規
則に基づいて付与されたラベル・フラグを基にして、ラ
ベルと特徴量を管理することにより、走査中に何回、図
形の結合が起こっても、一定回数の処理で正確に特徴量
を計測できるようにしたことを特徴とする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ラスタ走査で入力され
る画像信号を逐次処理し、１画面を１回走査するだけ
で、正確に特徴量を計測できる画像処理手法を用いた装
置に関するものである。

【０００２】

【従来の技術】１枚の画像中に多数の図形が含まれてい
る時、その個々の図形の面積などの形状的な特徴量を逐
次計測していく画像処理手法は、画像認識処理の最も基
礎的かつ重要な技術である。従来の形状特徴量計測手法
であるラベル付け手法や輪郭追跡手法では、入力画像や
それに代わる中間処理画像を１画面分記憶する必要があ
り、１回の走査だけでは、形状的な特徴量を抽出するこ
とはできなかった。また、従来の１画面１走査型特徴量
計測手法では、図形が入り組んでくると、図形の数を誤
認し、誤ったラベルを付け、形状特徴量を正確に計測で
きなかった。

【０００３】図１４は従来の１画面１走査型形状特徴量
計測手法を示すアルゴリズムである。図１４において、
対象画像を１ラスタ走査している間に、入力された２値
画像信号により記号列生成のための制御信号を発生し
て、属性記号を計算し、図形の各交差部の連結状態を表
現する属性記号列を生成する。この過程より図形の変形
（分岐、連結など）を判断することによって、形状特徴
量を計算する。この１ラスタ走査を繰り返していき、或
る図形の走査終了を検知した時点で、スタックに累積さ
れた特徴量をその図形の特徴量として出力する。以上の
動作を一画面分のラスタ走査が終了するまで繰り返すこ
とにより、対象画像内の全ての図形についての形状特徴
量が得られる。しかしながら、この手法では、正確に形
状特徴量を計測することができるが、属性記号列の計算
過程が難解で回路構成も複雑であった。

【０００４】

【発明が解決しようとする課題】本発明は上記従来技術
の課題を踏まえて成されたものであり、１画面を１回走
査するだけで、正確に特徴量を計測することができると
共に、回路構成を簡略化できる１画面１走査型特徴量計
測装置を提供することを目的としたものである。

【０００５】

【課題を解決するための手段】上記課題を解決するため
の本発明の構成は、ラスタ走査で入力されるビデオ信号
をＡ／Ｄ変換して２値化画素とする手段と、画素ディレ
イやフィ−ルドディレイを用いて走査している画素とこ
の画素の左，上，左上という２×２の４画素を取得する
手段と、この４画素より表１のラベル発行規則に基づい
てラベル・フラグを発行する手段と、このラベル・フラ
グにより同一図形に同一ラベルを発行する手段と、同一
ラベルを持つ図形の特徴量を逐次積算していく手段と、
ディレイを用いて上および左の画素に付けられたラベル
を保持しておく手段とを備えた構成とし、前記表１のラ
ベル発行規則に基づいて付与されたラベル・フラグを基
にして、ラベルと特徴量を管理することにより、走査中
に何回、図形の結合が起こっても、一定回数の処理で正
確に特徴量を計測できるようにしたことを特徴とするも
のである。

【０００６】

【作用】本発明によれば、走査中に図形の結合が起き
て、ラベルの付け換えを行う場合でも、走査している画
素とその左，左上，上の４画素に着目して発行するラベ
ル・フラグを基に各ラスタのラベルを３個のメモリでポ
インタ管理する構成としている。したがって、１ラスタ
内で何回もラベルの付け換えが起きても、一定の処理で
正確にラベル付けを行うことができるため、正確に特徴
量を計測することができる。

【０００７】

【実施例】以下、本発明を図面に基づいて説明する。図
１は本発明の１画面１走査型特徴量計測装置の一実施例
を示すブロック構成図であり、図２および図３は図１装
置の回路構成図である。図１〜図３において、１はラス
タ走査で入力されるビデオ信号をＡ／Ｄ変換して、背景
が０で、図形が１となるように２値化するＡ／Ｄ変換２
値化処理部である。２はＡ／Ｄ変換２値化処理部１で得
られた２値化対象画素が入力され、１画素ディレイおよ
び１フィ−ルドディレイを用いて、対象画素と対象画素
の左，上，左上の２×２の４画素を取得する４画素取得
部である。３は４画素取得部２で取得された４画素から
ラベル・フラグを発行するラベル・フラグ発行部であ
り、ラベル・フラグ用ルック・アップ・テ−ブル（ＬＵ
Ｔ）３１は表１に示すラベル発行規則に基づいてラベル
・フラグを発行する。

【０００８】ここで、本発明に係わる表１のラベル発行
規則を説明する。なお、表１は特徴量として面積（図形
の画素数）を選んだ場合である。表１において、走査中
の対象画素とその左、上、左上の４画素の状態が、 ・ＳＯのときは、新しいラベルを発行する。そのラベル
をアドレスとして、特徴量（面積）を積算する場所を確
保し、初期値を積算する（１を与える）。 ・ｅＳのときは、新しいラベルを発行する。ｊ−１・ｊ
ラスタ内の連続領域が終了したと判断して、付け換えら
れなければならないラベルに最終的なラベルを付ける。
そのラベルをアドレスとして特徴量（面積）を積算する
場所を確保し、初期値を積算する（１を与える）。 ・ＸＳのときは、上の画素がその図形の最左部分であれ
ば、新しいラベルを発行する。そのラベルをアドレスと
して、特徴量（面積）を積算する場所を確保し、初期値
を積算する（１を与える）。また、上の画素がその図形
の最左部分でなければ、上の画素に付けられたその図形
の最左部ラベルを継承する。そのラベルをアドレスとす
る上図形の特徴量（面積）に、走査画素を含む特徴量
（面積）を積算する（１を加える）。 ・ＣＯのときは、左の画素に付けたラベルを継承する。
そのラベルをアドレスとする左図形の特徴量（面積）
に、走査画素を含む特徴量（面積）を積算する（１を加
える）。 ・ＸＣのときは、上の画素がその図形の最左部分であれ
ば、左に付けたラベルを継承する。そのラベルをアドレ
スとする左図形の特徴量（面積）に、上図形に走査画素
を含めた領域の特徴量（面積）を積算する（上図形の面
積と１を加える）。また、上の画素がその図形の最左部
分でなければ、左の画素と上の画素のラベルを比較し
て、同じラベルでなければ、上の画素に付けられたその
図形の最左部ラベルを継承する。そのラベルをアドレス
とする上図形の特徴量（面積）に、左図形の特徴量（面
積）に走査画素を含めた特徴量（面積）を積算する（左
図形の面積と１を加える）。更に、上の画素がその図形
の最左部分でなく、上の画素と左の画素のラベルが同じ
であれば、左のラベルを継承する。そのラベルをアドレ
スとする左図形の特徴量（面積）に、走査画素を含む特
徴量（面積）を積算する（１を加える）。 ・ｅｌ，ｅｕのときは、対象画素にはラベルを付けな
い。ｊ−１・ｊラスタ内の連続領域が終了したと判断
し、付け換えられなければならないラベルに最終的なラ
ベルを付ける。 ・Ｏのときは、ラベルを付けない。 というように、ラベル・フラグを発行する。

【０００９】図１〜図３に戻り、４はラベル・フラグ発
行部３で発行されたラベル・フラグにより、同一の図形
に同一ラベルを発行するラベル発行部であり、４１はラ
ベル・フラグによってラベルを選択するセレクト信号発
生器、４２はセレクト信号発生器４１により選択された
フラグZEROにより、ラベルＯを選択するバッファ、４３
は同様にフラグNEW により、新しいラベル（最新のラベ
ルに１を足した値）を選択するバッファ、４４，４５は
それぞれフラグLEFT，フラグUPPER により、左画素およ
び上画素に付けられたラベルのleft・label ，renewed
・upper ・label を選択するバッファである。５は同じ
ラベルを持つ図形の特徴量を逐次積算していく特徴量計
測部であり、図２に示す回路は特徴量として面積（図形
の画素数）を選んだ時の回路構成である。ここで、ラベ
ルｘの付いた図形の面積は、メモリarea[j] のアドレス
ｘ番地に記憶されている。走査中にラベルの付け換えが
起こると、その図形の面積は、メモリarea[j] の付け換
えられた方のラベルをアドレスとする領域に記憶される
ように、加算器への入力がlabel ・flagで選択される。
また、５１のメモリarea[j-1] も２個あり、ｊラスタの
走査が終了し、ｊ−１ラスタの走査が開始する時に、メ
モリarea[j] と入れ換えられる。６は現在のラベルから
ディレイを用いて、左画素に付けられたラベルと、上画
素に付けられたラベルを保持しておくラベル管理部であ
る。６３のメモリは、ｊ−１ラスタ走査時点で、別の図
形であったものが、ｊラスタ走査中に同じ図形であるこ
とが判った時（左部重なり型連結時）に書き換えられ
る。６４，６５のメモリは、ｊラスタ走査中に、既にラ
ベルが発行されている図形が同じ図形であると判った時
（右部重なり型連結時）に書き換えられ、ｊ＋１ラスタ
の走査が始まる時に、６１，６２のメモリと切り換えら
れることにより、正しいラベルを発行する。ここで、メ
モリp ・right[j]６４は、ラベル・ポインタであり、ポ
インタ・アドレス・カウンタ６６が発行するアドレスを
値とする。また、メモリlabel ・right[j]６５は、ポイ
ンタ・アドレス・カウンタ６６が発行したアドレスに付
け換えられたラベルを記憶する。

【００１０】このような構成において、図４〜図６は本
発明の１画面１走査型形状特徴量計測装置の動作を示す
フロ−チャ−トである。なお、図３中の６１〜６５の５
つのメモリp ・right[j-1]，label ・right[j-1]，p ・
left[j-1] ，p ・right[j]，label ・right[j]は、図７
に示すように、アドレスと同じ値を初期値として与えて
おく。ここで、ｊ−１ラスタ走査終了時点で、３つの図
形が入り子状になっている画像を考える。ラベルとして
は、外側から順番に１，２，３が与えられているとす
る。これを模式的に表したものが図８である。ｊラスタ
の走査が開始されると、左側では連結していないので、
ラベル発行規則ＸＳにより、それぞれの図形に新しく
４，５，６のラベルが与えられる。この時、メモリ６３
のp ・left[j-1] が書き換えられて、図９のようにな
る。また、図１０にｊラスタ走査時に各画素に発行され
るラベル・フラグとラベルを示し、図１１に各フラグ発
行時点でのメモリ６１〜６５の状態を示す。図１０およ
び図１１において、 ・（ａ）の時点で、フラグＳＯが出るので、新しいラベ
ル７が付けられる。 ・（ｂ）の時点で、ＸＣ２が出て、走査している領域が
６の図形と連結していることが分かり、ラベル６を付け
ると同時に、メモリ６４のp ・right[j]のアドレス７の
内容を図３中のポインタ・アドレス・カウンタ１２が新
たにカウントした値Ａ１にする。なお、Ａ１の内容は、
まだ確定していない。 ・（ｃ）の時点で、フラグＸＳ２が出て、ラベル６の図
形であることが分かり、ラベル６を付ける。 ・（ｄ）の時点で、フラグＸＣ２が出て、５の図形と連
結していることが分かり、（ｂ）の時点と同様に、ラベ
ル５を付けると同時に、メモリ６４のp ・right[j]のア
ドレス６の内容を値Ａ１にする。 ・（ｅ）の時点で、フラグＸＣ２が出て、４の図形と連
結していることが分かり、（ｂ）の時点と同様に、ラベ
ル４を付けると同時に、メモリ６４のp ・right[j]のア
ドレス５の内容を値Ａ１にする。 ・（ｆ）の時点で、フラグｅｕが出て、この図形の走査
がひとまず終了したとして、メモリ６２のlabel ・righ
t[j-1]のＡ１に、最後に付けられたラベル４を与える。

【００１１】この時、ｊ−１ラスタで図形に発行された
ラベルが入り子になっていれば、ｊ−１・ｊラスタ内連
結領域（図１０の網掛け部）に着目してラベルを発行す
ることにより、ラベル７、６、および５は、入り子にな
った図形４の外に出てくることはない。したがって、Ｘ
の出た各時点でアドレスＡ１をポインタとして与えてお
き、ｅの出た時点で４を付けるというように、１度の付
け換えだけで済むことになる。

【００１２】従来の手法では、ｊラスタの走査時に、何
度もラベルを付け換えるためには、元のラベルと新しい
ラベルの対応を全て記憶しておき、メモリの内容を順次
書き換える必要があり、１画素走査の間では処理しきれ
なかった。しかし、本発明の手法では、フラグＸＣ３が
出た時に行う処理が一番多いが、フラグＸは、２画素連
続で出力されないことを利用すれば、処理を２画素走査
の間に振り分けることができる。

【００１３】図１２はｊラスタ走査終了時点での図３中
の５つのメモリの状態を示す図である。ｊ＋１ラスタの
走査時に参照される上ラベルは、３つのメモリ６１〜６
３のp ・right[j-1]，label ・right[j-1]，p ・left[j
-1] を介したrenewed ・upper ・label なので、完全に
入り子状になっている。このように、上ラベルをポイン
タで管理することにより、一定の処理で各ラスタごとに
入り子状のラベルを継承できる。即ち、各ラスタまでに
同一図形と判断された図形には、同一のラベルが付けら
れていることになる。

【００１４】このように、本発明の手法では、完全に各
ラスタごとに入り子状のラベルを発行する。右部重なり
型連結に対しては、図７〜図１２に示したように、ｊ番
目のアドレスポインタ用メモリp ・right[j]６４とポイ
ンタの内容を記憶するメモリlabel ・right[j]６５を使
用する。１つ前のラスタ（ｊ−１ラスタ）のラベルが完
全に入り子状になっていれば、ｊラスタを走査し終った
時点で、 nested・upper ・label ＝label ・right[j-1][p ・right[j-1][upper・labe
l]] は完全に入り子になっている。

【００１５】左部重なり型連結が起こったときには、メ
モリp ・left[j-1] ６３をその場で書き換える。この動
作は、１回で良いが、その連結領域がｊラスタ上で初め
て現れたか（そこが、その領域の最左端部か）によっ
て、ラベルの付けかたが違う。なお、最左端部かどうか
は、メモリp ・left[j-1] ６３のアドレスとデ−タが同
じ値であるかどうかでわかる。

【００１６】なお、特徴量（上記実施例では面積）は、
図２に示す特徴量計測部５を構成するマルチ・プレクサ
を図４〜図６に示すフロ−チャ−トに従って、ラベル・
フラグによって管理することにより、その領域に最後に
付けられたラベルをアドレスとするメモリに積算され
る。

【００１７】図１３は図１装置による本発明の手法をコ
ンピュ−タでシミュレ−トした結果を示す図である。こ
の例では、６ラスタ目の走査までは、３つの図形とし
て、１０，１１，１２のラベルが付いていたものが、７
ラスタ目の走査で、右部重なり型連結が起こり、一つの
図形としてラベルが付け換えられている。即ち、（ハ）
図に示す７ラスタ目では、１つの図形とされて、ラベル
１３が付けられている。このように、右部重なり型連結
が起こっても、同一図形に同一ラベルを発行しているこ
とが分かる。また、面積も正確に積算されていることが
分かる。

【００１８】このように、走査中に図形の結合が起き
て、ラベルの付け換えを行う場合でも、走査している画
素とその左，左上，上の４画素に着目して発行するラベ
ル・フラグを基に各ラスタのラベルを３個のメモリでポ
インタ管理する構成としている。したがって、１ラスタ
内で何回もラベルの付け換えが起きても、一定の処理で
正確にラベル付けを行うことができるため、正確に特徴
量を計測することができる。

【００１９】なお、上記実施例において、特徴量として
面積を示したが、ラベル・フラグによる計算手法を工夫
することにより、図形の最大・最小Ｘ軸およびＹ軸座標
や、周囲長さ、孔の数、濃度積分などの多くの特徴量の
計測が可能である。

【００２０】

【発明の効果】以上、実施例と共に具体的に説明したよ
うに、本発明によれば、走査中に図形の結合が起きて、
ラベルの付け換えを行う場合でも、走査している画素と
その左，左上，上の４画素に着目して発行するラベル・
フラグを基に各ラスタのラベルを３個のメモリでポイン
タ管理する構成としている。したがって、１ラスタ内で
何回もラベルの付け換えが起きても、一定の処理で正確
にラベル付けを行うことができるため、正確に特徴量を
計測することができる１画面１走査型特徴量計測装置を
実現できる。

【図面の簡単な説明】

【図１】本発明の１画面１走査型特徴量計測装置の一実
施例を示すブロック構成図である。

【図２】図１装置の回路構成図である。

【図３】図１装置の回路構成図である。

【図４】図１装置の動作を示すフロ−チャ−トである。

【図５】図１装置の動作を示すフロ−チャ−トである。

【図６】図１装置の動作を示すフロ−チャ−トである。

【図７】ｊラスタ走査の開始される前の図３中の５つの
メモリの状態を示す図である。

【図８】ｊ−１ラスタ走査終了時点での画像を模式的に
示す図である。

【図９】右部重なり形連結の開始する前の図３中の３つ
のメモリの状態を示す図である。

【図１０】ｊラスタ走査時に各画素に発行されるラベル
・フラグとラベルを模式的に示す図である。

【図１１】各フラグ発行時点での図３中の５つのメモリ
の状態を示す図である。

【図１２】ｊラスタ走査終了時点での図３中の５つのメ
モリの状態を示す図である。

【図１３】図１装置による本発明の手法をコンピュ−タ
でシミュレ−トした結果を示す図である。

【図１４】従来の１画面１走査型形状特徴量計測手法を
示すアルゴリズムである。

【符号の説明】

１ Ａ／Ｄ変換２値化処理部 ２ ４画素取得部 ３ ラベル・フラグ発行部 ４ ラベル発行部 ５ 特徴量計測部 ６ ラベル管理部

Claims (1)

1. 【特許請求の範囲】 【請求項１】 ラスタ走査で入力されるビデオ信号をＡ
   ／Ｄ変換して２値化画素とする手段と、 画素ディレイやフィ−ルドディレイを用いて走査してい
   る画素とこの画素の左，上，左上という２×２の４画素
   を取得する手段と、 この４画素より下記表１のラベル発行規則に基づいてラ
   ベル・フラグを発行する手段と、 このラベル・フラグにより同一図形に同一ラベルを発行
   する手段と、 同一ラベルを持つ図形の特徴量を逐次積算していく手段
   と、 ディレイを用いて上および左の画素に付けられたラベル
   を保持しておく手段とを備えた構成とし、 前記表１のラベル発行規則に基づいて付与されたラベル
   ・フラグを基にして、ラベルと特徴量を管理することに
   より、走査中に何回、図形の結合が起こっても、一定回
   数の処理で正確に特徴量を計測できるようにしたことを
   特徴とする１画面１走査型特徴量計測装置。 【表１】