JPS6074093A - 輪郭形状情報抽出回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の属する技術分野〕 画像情報処理回路に関する。特に、パターン認識のため
の手段の一つの手段として適する二値画像の対象物の輪
郭形状情報を一次元情報に圧縮する回路に関する。

〔従来技術の説明〕

画像計測において重要な対象物の輪郭形状の計測には第
１図に示す輪郭追跡法が多用される。この方法は２値画
像の対象物１２の輪郭を時計回りＩ３、または反時計回
りに追跡して対象物の輪郭を一周し、第２図に示すよう
な８方向のチェイン・コードまたは上下左右の４方向の
コー！゛を用いて、追跡方向を逐次同定し、対象物の輪
郭に関する二次元情報を一次元情報に圧縮している。こ
の輪郭追跡を高速に行うためにはハードウェアに依存す
る方法もあるが、回路が複雑になりそのような従来回路
例は少い。また、ＣＰＵなどを用いて輪郭追跡法に伴う
方向判断を行うと、リアルタイム処理が難しく高速処理
に適しない欠点があった。

〔発明の目的〕

本発明は、従来の輪郭追跡法に代る方法を用いて輪郭形
状の計測を行い、前述の画像高速処理に伴う輪郭追跡法
の欠点を除去する回路を提供することを目的とする。

〔発明の要点〕

本発明は、輪郭追跡法によるチェイン・コードの直接生
成に代り、まずラスター・スキャンによりコンティメン
ト・コードを発生し、このコードを加工して２値画像の
輪郭形状に対応するチェイン・コードを生成するもので
、 水平同期および垂直同期にしたがって平面走査された２
値画像が入力する入力端子と、上記入力端子に入力する
信号が表す画面の隣接する４個の画素についてコンティ
メント・コードを発生する回路と、上記画面の各画素毎
に上記コンテイメント・コードを記憶する記憶回路と、
この記憶回路に接続されこの記憶回路の記憶内容のアド
レス並べ換えを行うとともに、上記画面の各画素に画像
領域毎の番号付けを行うプロセッサとを備え、このプロ
セッサは、上記記憶回路の記憶内容の読出し順序が上記
画像領域の輪郭を一周するチェイン・コードと同等にな
るようにアドレス並べ換えおよび画像領域毎の番号付け
を行うことを特徴とする。

〔実施例による説明〕

本発明を図面に基づいて説明する。

第３図は実施例回路の構成を示すブロック構成図である
。

まず、第３図に基づき本実施例回路の構成を説明する。

この回路は、計測対象である二値画像をラスター・スキ
ャンを行って得られるＩｌｌおよび「０」の二値信号を
入力する画像信号久方端子３０と、コンティメント・コ
ード発生回路３Ｉと、コア１−ｏ−／Ｌ／・ロジック回
路３２と、チェイン・ツー１°発生回路３４とを備え、
さらに、コンティメント・コード発生回路３Ｉはワンラ
イン・メモリ３１１および２×２マスク回路３１２とを
備え、また、チェイン・コード発生回路３４はデータ・
メモリ３４３、並べ換えプロセッサ３４４と、コンティ
メント・コード・カウンタ３４５とを備えている。

次に、第３図に基き本実施例回路の接続を説明する。端
子３０は図示されていない画像信号源に接続されていて
、この画像信号をコンティメント・コード発生回路３１
に人力するように接続される。

コンティメント・コード発生回路３１の出力はコントロ
ール・ロジック回路３２の入力に接続される。

このコントロール・ロジック回路３２ば画像の水平同期
信号源から水平同期信号を入力する同期信号端子３６に
接続される。

このコントロール・ロジック回路３２のコンティメント
・コード出力はチェイン・コード発生回路３４のデータ
・メモリ３４３の人力に接続され、また、コントロール
・ロジック回路３２のタイミング信号出力はチェイン・
コード発生回路３４のコンテイメント・コード・カウン
タ３４５の人力に接続されている。また、コンテイメン
ト・コード・カウンタの出力はアドレスとしてデータ・
メモリ３４３に与えられるように接続される。データ・
メモリ３４３の出力は並べ換えプロセッサ３４４の入力
に接続される。

次に、本発明の回路の動作につき説明に先立って、この
動作説明に用いられる第３図から第１３図までの図面お
よび第１表から第３表までの表の要点を説明する。

（以下本頁余白） 第３図は、前述のように本実施例回路の構成を示すブロ
ック構成図である。

第４図は、第３図の２×２マスク回路に入力する隣接す
る４個の画素により構成されるマスク・パターンの４つ
の枠の名称を示すもので、図の枠ａと枠すとの１組をマ
スク・パターンの上ラインと言い、枠Ｃと枠ｄとの１組
をマスク・パターンの下ラインと言う。

第５図は、画面５０上の対象物の輪郭５２と、対象物を
２個の領域に切断する線５３とにより、画面５０の領域
を３部分に分割した状態を示すもので、対象物領域の２
部分のそれぞれに「１」および「２」の領域番号を付し
、背景領域の部分に「０」の領域番号をイリしである。

第６図は、第５図に示す対象物の輪郭に沿うマスク・パ
ターンを示す図で、マスク・パターンの４個の画素の内
、斜線の施されている画素は、ラスター・スキャンにて
得られた「１」値の信号を示し、この信号は第５図にお
ける対象物領域にその画素が属することを示し、また、
空白の画素はｒＯＪ値の信号に対応して背景領域にその
画素が属することを示す。なお、本図における対象物輪
郭線上の黒点はマスク・パターンの４つの画素の共通点
を示す。

第７図は、第６図に記入した矢印付き線Ｃにて定まる線
上に発生するマスク・パターンを示す図である。ただし
、対象物の左側および右側にある背景のマスク・パター
ンは省略しである。

第８図は、第５図に示す対象物の輪郭上のコンティメン
ト・コードを左下側コードおよび右上側コードに分類し
て示したものである。

ここで、左下側コードとは、左側コードである番号１．
８．９、ＩＩおよびＩ３のコンティメント・コードと番
号３のコンティメント・コードのｍ　Ｈ３Ｆであり、右
上側コードとは、右側コードである番号２．４．６．７
および１４と番号１２のコンティメント・コードの総称
である。ただし、番号５および１０のコンティメント・
コードはそれぞれ番号ｌと４とのコンテイメント・コー
ドおよび番号２と８のコンティメント・コードとが結合
したものとして取扱うこととする。対象物の輪郭」二に
短い縦線で示した部分７０」二のコンテイメント・コー
ドは第２表の領域番号「１」の左下側コードに所属し、
輪郭線に沿って破線の付されている部分８１」二のコン
テイメント・コードば領域番号「１」の右上側コードに
所属し、輪郭」二に付した丸印で示した部分７３および
８４上のコンティメン（−・コードばｖｉＪ５゜番号「
２」の右上側コードに所属し、輪郭上のＸ印で示した部
分８２上のコンテイメント・コードは領域＠号「２」の
左下側コードに所屈し、輪郭上の黒丸印で示した９１ｉ
分８５上のコンテイメント・コードは領域番号［２′」
の左下側コードに所属し、そして輪郭線に沿って実線の
付されている部分８６上のコンティメント・コードは領
域番号「２′」の右上側コードに所属する。なお、図に
おいて符号８００および符号８５０で示される部分面は
それぞれ領域「１」および「２」を示し、符号８２５お
よび８７５のイリされた円に囲まれた部分はそれぞしシ
ェーブの彎曲箇所および「１シエーブの彎曲箇所をそれ
ぞれ示す。

第９図から第１１図は第１表から第３表に変換する過程
を示す論理流れ図であって、並べ換えプロセッサ３４４
の動作を示す。すなわち、データ・メモリ３４３の記憶
内容が画像対象の輪郭を一周するヂエイン・コードに変
換される過程を示す。

第９図は第１０および第１１図の過程の大要とその順序
を示すものであり、第１Ｏ図の過程において第１表から
第２表に示す変換が行われ、第１１図の過程において第
２表から第３表の変換が行われる。

第１２図は、マスク・パターンと、コンテイメント・コ
ートＣｃと、時計まわりのチェイン・コードＣｄとの対
応を示すもので、チェイン・コートには方向符号も添記
されている。

第１３図は、彎曲点の左端のマスク・パターンと右端の
マスク・パターンとの組合せを示すもので、彎曲点ペア
と言う。彎曲点には上に凸の場合と、下に凸の場合と、
上に凹（以下、Ｕシェープと言う。）の場合と、下に凹
（以下、ｎシェーブと言う。）の場合とがある。彎曲点
ペアの間に介在するコンティメン）・・コード番号３お
よび１２に対ノ心するマスク・パターンの数によって彎
曲点の名称は影響されない。

第１表は、第６図の対象物の輪郭に沿うて生成されたマ
スク・パターンに対応するコンティメント・コードを示
す。なお、表にて番号１Ｇのコンティメント・コードは
ライン区別用のコートを表わす。

第２表は第８図に示す領域番号および左下例コードと右
上側コードとの組合せにより作成されるテーブルに、そ
れぞれの組合わせに所属するコンティメント・コードを
第１０図の論理流れ図に示す方法に従って処理された状
態を示す。

第３表は第２表に示すように分類されたデータを、第１
Ｉ図の論理流れ図に示す処理を経て画像領域の輪郭を一
周するチェイン　コードに変換された状態を示す。コン
ティメント・コートも（ｊｌ記し、木表と第２表との関
連を明もイＣにするとともに、データ圧縮された状態も
示すものである。

次に、本発明の回路の動作につき説明する。第３図にて
、計測対象である二値画像の画素をラスター・スキャン
して得られる「１」および「０」の二値信号はコンティ
メント・コード発生回路３１のワンライン・メモリ３１
１および第４図に示す２×２マスク回路３１２の下ライ
ンに入力する。ワンライン・メモリ３１１はワン・ライ
ン分の遅延を与えられた信号を２×２マスク回路３１２
の上ラインに入力する。このようにして、二値画像上の
隣接する４個の画素についてのマスク・パターンが構成
されて、このコンティメント・コード発生回路よりコン
ティメント・コート”が出力される。このコンティメン
ト・コートの発生状態は第７図に示すように左から右に
向かって順次に生成される。

コンＩ−ロール・ロジック回路３２は、同期信号端子３
６より与えられる水平同期信号にて、各ラスクーライン
を区別するためのこのラインの始め（または、終り）に
発信するライン区別用コートを生成し、このコートをコ
ンティメント・コード発生回路３１からのコンティメン
ト・コードに付加して、データ・メモリ３４３に出力す
る。

一方、コンティメント・コード・カウンタ３４５はコン
トロール・ロジック回路３２からコンティメント・コー
ドとライン区別用コードとをデータ・メモリ３４３に書
き込むためのタイミング信号が与えられカウント・アン
プされる。この際に、番号０および１５のコンティメン
ト・コードは輪郭上の点を表わさないので、データ・メ
モリ３４３にこれらのコードが格納されないようにアド
レス信号が制御される。

データ・メモリ３４３には、このコンテイメント・コー
ド・カウンタ３４３の出力信号にアドレスされて、コン
トロール・ロジック回路３２の出力であるコンティメン
ト・コードとライン区別用コードとが記憶される。この
記１，０の状態は第６図に示す対象物の輪郭については
第１表に示すとおりである。１画面を走査した後に、デ
ータ・メモリ３４３に記憶されているコンティメント・
コート”およびライン区別用コードは並べ換えプロセッ
サ′３４４により８売み出される。

次に、並べ換えプロセッサ３４４の動作を説明する。

まず、第９図に示すように、並べ換え過程は大別すると
コンティメント・コードを領域番号ごとに左下側コード
と右」二側コードとに分類する第一の過程と、コンティ
メント・コードを時計まわりに並べかえ、チェイン・コ
ードに変換する第二の過程とになる。

ます、第一の過程を第１０図に基づき詳細に説明すると
、並べ換えプロセッサ３４４はデータ・メモリ３４３に
格納されているコンティメント・コードを読み込み、ま
ず上に凸の彎曲点ベアを検出すると、新しい領域が始ま
ったと判断し、領域番号をカウント・アップする。次に
、領域番号ごとに左下側コードと右上側コードとに分類
する。この際に、彎曲点ベア数は彎曲点を検出すること
により知ることができる。また、Ｕシェープの形状の彎
曲点ペアが現われた時は、後に統合するため、両端のマ
スク・パターンに対応する番号１４と１３のコンティメ
ント・コードを記憶し、また、ｎシェープの形状の彎曲
点ペアが現われた時は、ここでこの彎曲点ペアが１組増
えたと判断し、また、画面の同一行に現われる同−ｆａ
　＠のコンテイメント・コードの内、最初の左側コード
と最後の右側コードをペアとして、これらの間に現われ
る左右ペアは別の領域番号に続するものと判断し、ベア
となる領域番号を上記のテーブルに書き込む。−ＦＧこ
凸の彎曲点ペアが現われた時は右左ベアが１組減少した
と判断する。第１表のコンテイメント・コー１は、上記
の判断により第２表に示すチーゾル上に分類される。

第８図に示した例の場合、輪１郭」二の、１１！丸印で
示した部分８５上のコンテイメント・コートは領域番号
「２′」の左下側コードに所属し、輪廓線に１合って実
線の付されている８６上のコンティメン（・・コードは
領域番号「２′」の右上側コートｉこ所ＩＢＭするもの
と判断する。

次に、第二の過程を第１１図に基き説明すると、Ｕシェ
ープの彎曲点および「ｌシェープの彎曲点を示すコンテ
イメント・コードが出現するまでしま領域番号最小のテ
ーブルの右側コードを順Ｇこチェイン・コートに変換す
る。次に、Ｕシェープ（７）　ｗ　凹点を示すコンティ
メント・コードが出現すれば、このＵシェープの彎曲点
ベアの左側コードを逆に並べ換えてチェイン・コードに
変換し、ざらに、このＵシェープの彎曲点ペアの相手の
右側コードをチェイン・コードに変換した後、ひぎつづ
き、領域番号最小のテーブルの右側コードを順にチェイ
ン・コート“に変換し続ける。

次にｎシェープの彎曲点を示すコンテイメント・コード
が出現すれば、この自シェープの彎曲点ペアの右側コー
トを順次チェイン・コードに変換し、さらに、自シェー
ブペアをなす彎曲点ベアの相手の左側コードを逆に並べ
換えてチェイン・コードに変換した後、ひきつづき右側
コードの変換が終了するまで領域番号最小のテーブルの
右側コートを順にチェイン・コードに変換し続ける。こ
の右側コートの変換の終了後に左側コードを逆順に並べ
換えてチェイン・コードに変換してこの過程は終了する
。

第２表に示すテーブル上のコンテイメント・コートは、
この並べ換えの結果、第３表に示すテ−プル上のチェイ
ン・コードに変換される。

次に、コンテイメント・コードをデータ・メモリ３４３
に記憶する時に、左下側か右上側力・の（ｆｔ報も同時
に記憶させ、並べ換えプロセッサ３４４の負担を軽減し
て並べ換え過程を高速化することもできる。

〔利用形態〕

（１）２値画像の再生および輪郭点座標のδ］・算筆１
４図に示ずＸＹ座標データ・メモ１ノをイ寸カロ１′る
ことにより、画像再生および座標計算を１テうことがで
きる。すなわち、このＸＹ座標データ・メモリは、コン
トロール・ロジ・ツク回路より上の凸の彎曲点ペアが現
われた時に、番号８のコンテイメント・コートを示す輪
郭上の点の座（票をδ己１意する回路である。この座標
の示す点しより）象物のｅｌｋ　！Ｉｓを一周するチェ
イン・コードを作成するｌ’祭のに白点を示すもので、
この点の座標とチェイン・コードとを用いて、もとの２
値画像が再生できる。また、各輪郭点の座標の計算も行
うことカベできる。

（２）極座標方式による輪郭形状の表現第１５図および
第１６図に基き説明する。

第１５図は対象物の輪郭１３０と対象物上の定点１３１
例えば重心の座標（Ｘｃ、Ｙｃ）および始点１３２の座
標（Ｘｏ、Ｙｏ）および定点１３１を原点とし、定点１
３１と始点１３２とを結ぶ線を極座標の基準線とし対象
物の輪郭上を極座標を示ずベクトル１３５が移動してゆ
く状態を示すものである。

第１６図の横軸は輪郭点の順序番号または基準線となず
ベクトル１３５の偏移角１３４を示し、縦軸はへりトル
１３５の長さずなわぢ重心１３５から輪郭１３０上の点
までの距離を示す。図は始点１３２を原点として画かれ
ている。

この方法によっても輪郭形状情報を表現することができ
るが、このときにチェイン・コードを利用すると、定点
からの輪郭上の点との距離Ｒ１の計算を容易に行うこと
ができる。

すなわち、任意の輪郭上の点の座標を（Ｘｉ。

Ｙｉ）とし、始点と定点間の距離をＲｏとずればＲｏ２
−（Ｘｏ　−Ｘｃ）　２＋　（Ｙｏ　Ｙｃ）’でまり、
以下、隣接する輪郭上の点の座標の変化は、それぞれ下
記のようにチェイン・コードに対応する。すなわち、 Ｘ座標の「＋１」の変化は番号１．２．８のチェイン・
コードの出現に対応し、したがってＲｉ　２＝　（Ｒ１
−１）　２ ＋２　（Ｘ−ｉ　−Ｘｃ）　＋　Ｉ Ｘ座標の「−１」の変化は、番号５．４．６のチェイン
・コードの出現に対応し、したがってＲ１２−（Ｒｓ−
ｘ　）　２ ＋２　（Ｘｉ　−Ｘｃ）　＋Ｉ Ｙ座標の「＋１」の変化は、番号３．４、】２のチェイ
ン・コードの出現に対応し、したがってＲｉ　２＝　（
Ｒ１−１）　２ ＋２　（Ｙｉ　−Ｙｃ）　＋１ また、Ｙ座標の「−１」の変化は、番号７．８．６のチ
ェイン・コードの出現に対応し、したがって Ｒ４”　−（Ｒ１−ｘ　）　２ ＋　２　（−Ｙ　ｉ　−Ｙ　ｃ）’＋１により、輪郭上
の点と定点との距離をめることができる。

（３）面積および周長の計算 対象物の面積の算出は、上記（１１の方法によりまる輪
郭点の座標に基き、その輪郭点が右側コードに属するか
左側コードに属するかを判別し、右側コードに屈すると
きは加算し、左側コードに属するときは減算を行って輪
郭を一周することにより行うことができる。この場合、
座標は始点を原点とする座標であってもよい。

また、周長の算出は一行のラスター・スキャンにて得ら
れる一連のマスク・パターンにて、コンティメント・コ
ードが番号１．２．４．７．８、］１．１３．１４の場
合、ｒＪＴ／２」として計測し、コンティメント・コー
ドが番号３．６．９．１２の場合「１」として計測する
ことによって行うことができる。

〔発明の効果〕

本発明は、ラスター・スキャンにより二値画像の輪郭形
状に対応するチェイン・コードが生成できるので、従来
の輪郭追跡法による輪郭形状表現に比べて簡単なハード
ウェアにてリアルタイム処理を行うことができる。

また、２値画像を一次元データに変換しているのでデー
タ圧縮が行われ、したがって信号の伝送および記憶に便
利である。

さらに、対象物の形状情報として面積、周長のほかに、
外周の凹凸情報も得られ、パターン認識のときの外形形
状の識別に便利である。

【図面の簡単な説明】

第１図は輪郭追跡法を説明する模式図。 第２図はチェイン・コートを説明する図。 第３図は本発明の実施例回路の構成を示すブロック構成
図。 第４図は２×２−バクーンの枠名称の説明図。 第５図は画像の領域番号を示す説明図。 第６図は輪郭のコンテイメント・コート発生状態を示す
図。 第７図は特定のラスター走査によるご１ンテイメント・
コードの発生状態を示す図。 第８図は輪郭の領域番号を示す説明図。 第９図〜第１１図は並べ換えプロセツサの動作を説明す
る論理流れ図。 第１２図は信号の対照図。 第１３図は彎曲点ベアの説明図。 第１４図はｘＹ座標データ・メモリと入出力の接続を示
す図。 第１５図および第１６図は極座標方式による輪郭形状表
現の説明図。 １１・・・走査線、Ｉ２．１３０・・・対象物輪郭、３
０・・・画像信号入力端子、３１・・・コンティメント
・コード発生回路、３２・・・コントロール・ロジック
回路、３４・・・チェイン・コート発生回路、３５・・
・タイミング発生回路、３Ｇ・・・周期信号端子、５０
・・・画面、５２・・・対象物の輪郭、５３・・・対象
物領域切断線、９０・・・座標データメモリ、９１・・
・Ｘ座標信号入力端子、９２・・・Ｙ座標信号入力端子
、１３１・・・定点、１３２・・・始点、１３３・・・
領域番号上の任意点、１３４・・・偏位角、１３５・・
・極座標ベクトル、３１１・・・ワンライ二ノ・メモリ
、３１２・・・２×２マスク回路、３４３・・・データ
・メモリ、３４４・・・並べ換エフロセッサ、３４５・
・・コンティメント・コード・カウンタ。 特許出願人　横河北辰電機株式会社 代理人　弁理士　井　出　直　孝 第　２　図 冗　４　図 第　５　口 笛　７　図 ′ｆＪ　８　口 爪　９　圏 第　１０図 篤１２回 ソυ 鶏１４　図 １１フ 兇　１５図 ゾ 元　１６回 ／

Claims (1)

1. 【特許請求の範囲】 （１１水平同期および垂直同期にしたがって平面走査さ
   れた２値画像が入力する入力端子と、上記入力端子に入
   力する信号が表わす画面の隣接する４個の画素について
   コンティメント・コードを発生する回路と、 上記画面の各画素毎に上記コンティメント・コードを記
   憶する記憶回路と、 この記ｉＱ回路に接続されこの記４９回路の記憶内容の
   アトルス並べ換えを行うとともに、上記画面の各画素に
   画像領域毎の番号付けを行うプロセッサと を備え、 このプロセッサは、上記記憶回路の記憶内容の読出し順
   序が上記画像領域の輪郭を一周するチェイン・コードと
   同等になるようにアドレス並べ、換えおよび画像領域毎
   の番号イ」けを行うことを特徴とする輪郭形状情報抽出
   回路。