JPH0460780A - 境界追跡画像処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） この発明は、２値画像における対象物の境界点を追跡し
、ラベル付けを行なうと同時に対象物の特＠量を演算す
る装置に関する。

（従来の技ｊ４？） 画像内に存在する対象物の特徴量、例えば対象物の面積
や周囲長等を算出する場合には、先ず、２値画像を連結
成分毎（対象物毎）に分割する必要から対象物の境界点
を追跡し、それぞれの対象物にラベルを付ける処理がよ
く行なわれる。

このため、特徴量の算出までの過程を高速に行なうため
には、上記境界追跡を高速化し、ラベル付けを特徴量の
演算と共に行ってこのラベル付け及び特徴量の演算も高
速に行なうことが考えられる。

これを実現するために、本出願人は、境界追跡の高速化
の点について、現在注目している境界点の１つ前の境界
点から見た現在の境界点の存在方向（入力方向）と、現
在の境界点を取り囲む近傍画素の情報とから、予めこれ
らの情報と対応づけて記憶させておいた出力方向（現在
の境界点から見た次の境界点の存在方向）の情報を出力
する装置を開発し、これについて先に出願している。

また、本出願人はラベル付け及び特徴量の演算の高速化
についても研究しており、情報処理学会第３５回（昭和
６２年後期）全国大会の講演論文集（文献ＮＯ−８８−
０３８７、ＰＰ２０３１−２０３２）に収録された「境
界線追跡を用いたラベル付けアルゴリズム」に示される
境界追跡によるラベル付け処理に並行して、この境界追
跡の過程で対象物の特徴量を併せて演算する装置につい
ても開発するに至っている。

（発明が解決しようとする課題） しかしながら、上記２つの装置を作成するに当り、前者
においては、例えば入力方向と近傍画素の情報を一時点
に格納するレジスタとこれらのレジスタの内容を入力す
ることにより出力方向の情報を出力するＭＡＰ　　ＲＯ
Ｍを備える必要があり、また後者においても、入力方向
と出力方向の情報を一時点に格納するレジスタと、これ
らのレジスタの内容を入力することによりラベル付け及
び面積計算の有無を判断する情報を出力するＭＡＲＲＯ
Ｍを備える必要があり、これらを別々に構成したのでは
、高速化は実現できるものの、ハードウェアの構成要素
が多くなり、コスト高となる不都合がある。

そこで、この発明においては、上記不都合を解消し、境
界追跡とラベル付け及び面積計算の高速処理を少ないハ
ードウェアの構成要素をもって実現し、コストの低減を
図ることができる境界追跡画像処理装置を提供すること
を課題としている。

（課題を解決するための手段） しかして、この発明の要旨とするところは、第１図に示
されるように、２値画像の各画素を取り囲む近傍画素の
情報を格納する近傍情報格納手段１００と、前記２値画
像の対象物の境界点のうち注目する境界点の１つ前の境
界点から見た該注目する境界点の存在方向（以下入力方
向という）に関する情報と、前記注目する境界点からみ
た次の境界点の存在方向（以下出力方向という）に関す
る情報とを選択的に格納する第１の格納手段２００と、
前記近傍情報格納手段１００に格納された近傍画素の情
報と、前記入力方向に関する情報とを選択的に格納する
第２の格納手段３００と、第１の格納手段２００から読
出された出力方向に関する情報を入力方向に関する情報
にしてこれを該第１の格納手段２００へ出力し、第１の
格納手段２００から読出された入力方向に関する情報を
前記第２の格納手段３００へ出力する方向情報制御手段
４００と、前記第１の格納手段２００に格納された入力
方向に関する情報と前記第２の格納手段３００に格納さ
れた近傍画素の情報とを入力した場合に出力方向に関す
る情報を出力し、前記第１の格納手段２００に格納され
た出力方向に関する情報と前記第２の格納手段３００に
格納された入力方向に関する情報とを入力した場合にラ
ベル付け及び特徴量の演算の有無を判別する情報を圧力
する演算回路５００と、この演算回路５００からの出力
に基づいて境界追跡を行ない、ラベル付け及び特徴量演
算処理を行なう処理実行手段６００と、前記第１の格納
手段２００に前記方向情報制御手段４００から入力方向
に関する情報を読込み、前記第２の格納手段３００に前
記近傍情報格納手段１００から近傍画素の情報を読込む
タイミングと、前記第１の格納手段２００に前記演算回
路５００から出力される出力方向に関する情報を読込み
、前記第２の格納手段３００に前記方向情報制御手段４
００から入力方向に関する情報を読込むタイミングとを
交互に行なうタイミング制御手段７００とを具備するこ
とにある。

ここで、第１及び第２の格納手段２００，３００として
は、データをそれぞれ一時的に保持するレジスタを用い
てもよく、また演算回路５００としては、入力方向に関
する情報と近傍画素の情報を入力すれば出力方向に関す
る情報を出力し、出力方向と入力方向に関する情報を入
力すればラベル付け及び対象物の特徴量演算の有無を識
別するコードを出力するようなＲＯＭを用いてもよい。

（作用） したがって、タイミング制御手段７００によって第１の
格納手段２００に入力方向に関する情報を格納すると共
に第２の格納手段３００に近傍情報格納手段１００から
近傍画素の情報を格納し、しかる後にこの入力方向に関
する情報と近傍画素の情報とが演算回路５００に入力さ
れると、この演算回路５００からは出力方向に関する情
報が出力される。この出力方向に関する情報は、タイミ
ング制御手段７００によって次の段階で第１の格納手段
２００に格納され、また前段階で第１の格納手段２００
に格納されていた入力方向に関する情報は、方向情報制
御手段４００を介して第２の格納手段３００に格納され
る。そして、演算回路５００にこの第１の及び第２の格
納手段２００゜３００の内容が入力されると、この演算
回路５００からはラベル付け及び対象物の特徴量の有無
を判断する情報が出力される。

また、次の段階においては、第１の格納手段２００に格
納されていた出力方向に関する情報が、方向情報制御手
段４００によって入力方向に関する情報に変換されて第
１の格納手段２００に格納され、第２の格納手段３００
には近傍情報格納手段１００から次の境界点の近傍画素
の情報が読込まれ、以下同様の操作が繰り返される。

このため、上述のように、第１及び第２の格納手段２０
０，３００と演算回路５００とをタイミングをずらして
共通に利用すれば、境界追跡の処理とラベル付け及び特
徴量の演算とを別々のハードウェアで構成しなくてもよ
く、少ないハードウェアをもって従来と同様の高速処理
が実現でき、そのため、上記課題を達成することができ
るものである。

（実施例） 以下、この発明の実施例を図面に基づいて説明する。

第２図において、この発明に係る境界追跡画像処理装置
を説明するための画像処理システムの概略構成が示され
ている。

この画像処理システムは、中央演算装置（ＣＰ［Ｉ）、
入出カポ−）　（Ｉｌｏ）等を含むそれ自体公知のマイ
クロコンピュータを備えた画像処理制御装置ｌを有し、
この画像処理制御装置１には、１６ビノＩ−（Ｄ、〜Ｄ
ｏｓ）のデータバスに接続するデータ入出力端子、制御
信号を出力する制御信号出力端子Ｓ、及び１６ビソト（
ＡＤ〜Ａ８．）のアドレスバスに接続するアドレス端子
が少なくとも具備されている。また、この画像処理制御
装置１は、各画素を２値化した２５６ｘ２５６の画像マ
トリクスのデータを格納する２値画像メモリを有してお
り、この２値画像メモリへのデータの格納は、後述する
画像追跡処理や対象物のラベル付け及び特徴量の算出処
理が行なわれる前の段階で行なわれるようになっている
。

近傍情報メモリ２は、前記２値画像のデータをもとにし
て画像処理制御装置１内で形成される各画素の近傍画素
情報を格納するＲＡＭからなり、データバスの下位８ビ
フト（Ｄ、〜Ｄｏ）が接続するデータ入出力端子を有す
ると共に、Ｉ６ビノ）　（Ａ、、〜Ａ、）のアドレス入
力端子を有している。このアドレス入力端子の上位８ビ
ツト（Ａ１゜〜Ａｌ）は行カウンタ３に接続され、また
下位８ビツト　（Ａ　’ｒ〜Ａｏ）は列カウンタ４に接
続されており、このため、この近傍情報メモリ２に入力
されるアドレス情報は、上位アドレス（８ビツト）と下
位アドレス（８ビツト）に分割されて、それぞれ独立に
カウントアンプ、カウントダウンできるようになってい
る。

近傍情報メモリ２に格納されている近傍情報は、第３図
に示すように、この実施例では注目する画素Ｘ４．（第
ｉ行ｊ列の画素）の周囲を取り巻（８ケの画素の２値化
情報を収集したものであり、Ｘ　、の画素の近傍情報は
、第４図に示されるように、（ｉＸ２５６＋ｊ）番地の
アドレスに格納されている。従って、この近傍情報の読
出しに際しては、このｉとｊが行カウンタ３と列カウン
タ４で指定されることになり、前記上位アドレスは画像
マトリクスの行アドレスに、また下位アドレスは列アド
レスにそれぞれ対応している。尚、上記８ビツトからな
る近傍情報のひとまとまり（ｎｔｎ６　ｎ５　ｎ４　ｎ
、、　ｎｌ　ｎｌ　”０　）を、ここでは近傍情報ベク
トルと呼ぶことにする。

行カウンタ３及び列カウンタ４は、第１のデコーダ５か
らのクロック信号及び第２のデコーダ６からの制御信号
に基づいてカウントアツプまたはカウントダウンするア
ップ／ダウンカウンタにより構成されている。この行カ
ウンタ３にはデータバスの上位８ピツ）（Ｄｏｓ〜Ｄ、
）が、また列カウンタ４にはデータバスの下位８ピント
（Ｄ？〜Ｄ、）がそれぞれ接続されており、それぞれの
カウンタ３，４には、第１のデコーダ５からのロード入
力が加えられることにより、画像処理制御装置ｌで指定
する初期アドレスを、データバスを介してそれぞれ入力
し、初期セットできるようになっている。

ここで、第１のデコーダ５は、画像処理制御装置１から
入力される制御信号Ｓとアドレスバス（Ａ１．〜ＡＤ）
からの信号に基づき、上記近傍情報メモリ２、行カウン
タ３、列カウンタ４と、下記する第１および第２のレジ
スタ７．８、第１及至第３のバッファ９，１０．ＩＩの
各要素を制御する制御信号を所定のタイミングで出力し
ている。

更に、行カウンタ３と、列カウンタ４のアドレス出力端
子は、第１のバッファ９を介してデータバスに接続され
ており、この第１のバッファ９に第１のデコーダ５から
の制御信号が入力されると、この行アドレスと列アドレ
スとを組合わせたアドレス情報が画像処理制御装置１に
送出されるようになっている。

第１のレジスタ７は、入力方向の情報または出力方間の
情報を一時的に格納しておくもので、データバスの下位
４ビン）　（Ｄ、〜ｐｏ）が接続されており、第１のデ
コーダ５からの制御信号に応じて、入力方向データまた
は出力方向データ（４ビツト）を取込み、またこのレジ
スタ７から出力するようになっている。

また、この第１のレジスタ７は、第２のバッファ１０を
介してデータバスの下位４ビツト（Ｄ３〜Ｄｏ）に接続
されており、第１のデコーダ５がらの制御信号に基づい
て、第１のレジスタ７内に格納される入力方向の情報を
画像処理制御袋Ｗ１へ出力するようになっている。

第２のレジスタ８は、前記近傍情報メモリ２に格納され
ている近傍情報ベクトル、または入力方向の情報を一時
的に格納しておくもので、データバスの下位８ピント（
Ｄ７〜Ｄｉ））が接続されており、第１のデコーダ５か
らの制御信号に応じて近傍情報ベクトルまたは入力方向
のデータを取込み、またこのレジスタ８から出力するよ
うになっている。

ここで、出力方向の情報は、現在の注目している境界点
から見た次の境界点の存在方向を、第５図に示すように
「０」から「７」の数値で表したものであり、また入力
方向の情報は、１つ前の境界点から見た現在の境界点の
存在方向を、同じく第５図に基づいて数値化したもので
あり、このシステムにおいては、この数値を２進化して
用いている。

そして、前記第１及び第２のレジスタ７．８の出力端子
はＭＡＰ　　ＲＯＭ１２のアドレス入力端子（Ａ＋＋〜
Ａ（＋）の上位４ビツト（Ａ　＋　＋　””　Ａ　ａ　
）と下位８ピント（Ａ？〜Ａｔ）にそれぞれ接続されて
おり、第１及び第２のレジスタ７．８からのデータをア
ドレス情報としてＭＡＰ　　ＲＯＭ１２に入力し、その
データの組合わせから、４ビツト（Ｄ、〜Ｄｏ）の情報
を出力し、第２のデコーダ６に対してはそのうち下位３
ビツト（Ｄｚ〜Ｄｏ）の情報を送出する。また、ＭＡＰ
　　ＲＯＭ１２からの４ビツトの情報は、第３のパンフ
ァ１１を介して第１のレジスタ７へ出力されると共に、
同第３のパフファ１１を介して画像処理制御装置１へ出
力されるようになっている。

次に、ＭＡＰ　　ＲＯＭ１２の具体的な内容とその動作
について説明する。

ＭＡＰ　　ＲＯＭ１２は、入力方向の情報と近傍情報ベ
クトルとがアドレス情報として入力されると、出力方向
のデータを出力する機能があり、またこの機能の他に、
出力方向の情報と入力方向の情報とがアドレス情報とし
て入力されると、対象物のラベル付けと面積計算の有無
を判別するデータを出力する機能を兼ね備えている。

このＭＡＲＲＯＭ１２の出力データは、第６図に示すよ
うなもので、これを説明するに当り、境界追跡の原理、
対象物の面積計算とラベル付けの原理について触れてお
く。

先ず、境界追跡の原理について説明すると、第７図に示
すように、現在注目している境界点（ｐｘ　）の１つ前
の境界点（ＰＫ−＋　）から見た（ＰＫ）の存在方向（
入力方向）と、（ｐＫ）を中心として形成されたその周
囲に存在する８ケの近傍画素の状態（この図において斜
線部は“１”が割当てられた対象物の領域であり、それ
以外は“０”が割当てられた背景の領域である）とがわ
かると、近傍画素を１つ１つ判別しなくても、（ＰＫ　
）の出力方向を一義的に決めることができる。本システ
ムにおいては、このことを利用して出力方向の情報を得
ているもので、この出力方向のデータをもとに、第２の
デコーダ６を介して行カウンタ３と列カウンタ４とを必
要によりカウントアンプまたはカウントダウンして逐次
境界点の追跡を行なう。

ここで第２のデコーダ６のデコード内容は、第８図に示
すようなもので、例えば出力方向が”０“（０００）で
あれば行カウンタ３をそのままにして列カウンタ４を１
カウントアンプする。また、例えば出力方向が“１”　
（００１）であれば行カウンタ３を１カウントダウンす
ると共に列カウンタ４を１カウントアツプし、出力方向
が“５”（１０１）であれば、行カウンタ３を１カウン
トアンプし、列カウンタ４を１カウントダウンする。

従って、第７図の境界点においては、入力方向が“２”
　（０１０）の方向であり、また、この境界点における
近傍情報ベクトルは、ｒｏｏｌｏｌｏｌｌＪである。そ
こで、この入力方向と近傍情報ベクトルとの組合せで決
定されるアドレス（ｏｘｏ：　００１０１０１１）に、
予め′１″　（００１）という出力方向データを格納し
ておけば、この入力方向の情報と近傍情報ベクトルとを
ＭＡＲＲＯＭ１２に入力することにより、このＭＡＰ　
　ＲＯＭ１２がらは（００１）という出力方向のデータ
が自動的に続出される。

そして、この（００１）の出力方向は、第８図にも示さ
れるように、行アドレスを１カウントダウンすると共に
列アドレスを１カウントアツプしたものに相当しており
、これを実行することにより出力方向に存在する次の境
界点のアドレスを設定することができる。

このため、このＭＡＰ　　ＲＯＭ１２には、入力方向の
データと近傍情報のデータの組合わせで決まるそれぞれ
のアドレスに、予め出力方向のデータが格納されており
、この出力方向のデータは、入力方向と近傍情報ベクト
ルとを入力することにより出力されるようになっている
。

次に、対象物の面積計算の概要について説明する。

例えば、第９図の斜線部で示された対象物の面積を求め
る場合には、画像を各画素毎に縦横に仕切って形成した
単位面積を考え、この斜線部に含まれる単位面積の数を
集計する。

その手段としては、対象物の外周境界点について着目し
た場合、外周左端を形成する境界点（例えば第９図の■
の箇所）においては、（１）式に示すように、面積変数
ｒＳＪ　　（初期においては零）から境界点の列方向の
座標ｘ　（ｘ＝φ、１．・・・、２５５）より１つ手前
の列座標値（ｘ−１）を滅してＳの内容を更新する。

Ｓ　　−５−（Ｘ−１）　　　　　　　・・・（１）こ
れは、対象物の外周左端より左側の背景領域の面積を除
外する操作に対応している。

また、対象物の上下端部より巾１の突出領域を形成する
境界点（例えば■の箇所）においては、（２）式に示す
ように、Ｓに１を加えてＳの内容を更新し、突出領域の
面積を直接加算していく。

Ｓ　←　Ｓ＋１　　　　　　　　　　　・・・（２）更
に、対象物の外周右端を形成する境界点（例えば■の箇
所）においては、（３）式に示すように、Ｓに該境界点
の列座標値Ｘを加えてＳの内容を更新する。

Ｓ−３＋ｘ　　　　　　　　　　　・・・（３）これは
、対象物の外周右端より左側の面積を加算するための操
作に対応している。

尚、それ以外の外周境界点、即ち、対象物の上下端部の
うち巾１で突出する部分を除いた部分においては、Ｓの
値を更新しない。

このような手法をもって外周境界点を一周すると、変数
Ｓには、外周で囲まれた領域内の単位面積の数が収集さ
れる。

ところで、上述のＳには対象物内部に存在する背景、即
ち穴の部分（内周境界点で囲まれた領域）も含まれてい
る。このため、穴の面積を知るために以下の操作を行な
う。

即ち、内周右端を形成する境界点（例えば■の箇所）に
おいては、（４）式に示されるように、Ｓに列座標値（
ｘ−１）を加えてＳの内容を更新し、内周右端より左側
の領域の面積を加算する。

Ｓ　４−　Ｓ＋（ｘ−１）　　　　　　・・・（４）ま
た、内周の上下端部より巾１で内側に突出する領域を形
成している境界点（例えば■の箇所）においては、（５
）式に示すように、Ｓから１を減じてＳの内容を更新し
、その部分の面積を直接差引く。

Ｓ　　←　　Ｓ−１・　・　・（５） 更に、内周左端を形成する境界点（例えば■の箇所）に
おいでは、（６）式に示すように、Ｓから該境界点の列
座標値Ｘを減じてＳの内容を更新し、内周左端より左側
の領域の面積を減算する操作を行なう。

Ｓ　←　Ｓ−ｘ　　　　　　　　　　　・・・（６）尚
、それ以外の内周境界点、即ち、穴の上下端部のうち巾
１で内側に突出する部分を除いた部分において、Ｓの値
を更新しない。

以上の（４）〜（６）式の操作をもって内周境界点を一
周すると、変数Ｓには、内周境界点で囲まれた領域の単
位面積の数が収集され、前記外周境界点で囲まれた領域
の単位面積数からこの内周境界点で囲まれた領域の単位
面積数を引くことにより、目的とする斜線部の面積が得
られるものである。

次にラベル付けについて説明すると、このラベル付け処
理は、従来とほぼ同様の形式で行われ、ラベル付けは、
２値化された画像データをもとに、対象物の外周左端の
境界点にラベルｒＮＪ　　（Ｎは整数）を付ける第１の
処理、ラスター走査をしなからｒＮＪの右隣りの対象物
領域の箇所（“１”の箇所）に順次ｒＮＪを付ける第２
の処理、及び対象物に穴がある場合にその対象物の内周
右端の境界点にラベルｒＮＪを付ける第３の３種類の処
理を行なう。

外周左端にラベルを付けるためには、第１０図（ａｌの
条件をもって外周境界追跡の開始点を見つけ（第９図の
■の箇所）、この境界点から例えば時計回りに外周を追
跡しながらラベル付けを行なう。

また、内周右端にラベルを付すためには、第１Ｏ図（Ｃ
１の条件をもって内周境界追跡の開始点を見つけ（第５
図の■の箇所）、この境界点から反時計回りに内周を追
跡しなからラベルを付けていく。

前記第２及び第３の処理は第１の処理が終了した後に行
われ、第３の処理は、第２の処理の途中で行なわれる。

尚、穴がない場合には第３の処理は行われない。

このため、境界点のそれぞれにおいて、面積計算の有無
を区別すると共に、（１）式から（３）式（あるいは（
４）式から（６）式）のいずれの計算式を用いるかを判
別する必要があり、また、境界追跡の過程でラベル付け
の有無を判断する必要がある。第１１図はこれを図表化
したもので、入力方向と出力方向の情報に基づいてラベ
ル付けの有無や面積計算の有無、更には面積計算の計算
式を判別できるようになっている。

これを具体的に説明すると、第１１図のマトリクスにお
いて「◎」の部分は、現在取り扱っている境界点にラベ
ル付けを行ない、その境界点において対象物の特徴量（
この実施例では面積）の計算を（１１式あるいは（４）
式で行なうことを示しており、この「◎」には“６”を
２進化したコード（１１０）が割り当てられている。ま
た、「・」の部分は、同様に境界点にラベル付けを行な
うと共に、その境界点において面積計算を（２）式ある
いは（５）式で行なうことを示しており、この「・」に
対応するＭＡＰ　　ＲＯＭ１２の箇所には“０”を２進
化したコード（０００）が割り当てられている。「◇」
の境界点の部分は、ラベル付けを行わないが、面積計算
を（３）式あるいは（６）式で行なうことを示しており
、この「◇」の部分には“２”を２進化したコード（０
１０）が割り当てられている。「○」の部分はラベルを
付けるだけで面積計算を行なわない境界点であることを
示し、この「○」の部分には“７”を２進化したコード
（１１１）が割り当てられている。更に、「×」の部分
は、ラベルを付ける必要も、また面積計算を行なう必要
もない境界点であることを示し、「△」の部分はそのよ
うな境界点が存在しないために、ラベル付けも面積計算
も不要であることを示し、これら「×」と「△」の部分
に対しては“１″を２進化したコード（００１）が割り
当てられている。

したがって、ＭＡＰ　　ＲＯＭ１２には、予めラベル付
けと面積計算の有無等を判別する上述したデータＫが格
納されており、このＭＡＰ　　ＲＯＭ１２は、出力方向
と入力方向のデータを入力することにより、自動的にこ
のＫを出力するようになっている。

ところで、上述したように、ＭＡＰ　　ＲＯＭ１２には
、出力方向のデータとラベル付け及び面積計算の有無を
判別するデータにの両方が収納されている。このため、
第１のレジスタからの入力データが入力方向のデータで
あり、また第２のレジスタからの入力データが近傍情報
ヘクトルである場合には出力方向のデータを、そして第
１のレジスタからの入力データが出力方向のデータであ
り、また第２のレジスタからの入力データが入力方向の
データである場合にはＫを、それぞれ区別して出力する
手段が必要になる。

そこで、この実施例においては、第１のレジスタから出
力される４ビフトデータのうち、下位３ビツトを方向デ
ータとして用い、上位１ピントを“０″にするか“１”
にするかで区別している。

即ち、出力方向のデータを読出すために第１のレジスタ
に入力方向のデータが格納されるときは、最上位桁の１
ビツトを“０”にし、Ｋを読出すために第１のレジスタ
に出力方向のデータが格納される時には、最上位桁の１
ビツトを“１”にする。

また、ＭＡＰ　　ＲＯＭ１２の出力方向のデータは、後
に第１のレジスタ７に入力してラベル付け及び面積計算
の有無判断に用いることができるので、出力情報の４ビ
ツトのうち下位３ビツトに出力方向のコードが割り当て
られ、上位１ビツトにＫの出力操作を選択するための“
ｌ”がセントされている。

上記構成において、次にこの画像システムの動作を、第
１２図に示すフローチャートに基づきながら説明する。

先ず、画像処理制御装置１は、ステップ５０に示される
ように、画像の各画素の情報を２値化して２値画像を形
成しく対象物を“１゛、その背景（穴も含む）の部分を
“Ｏ”）、このデータを２値画像メモリに格納する。

そして、次のステップ５２において、画像処理制御装置
１は、各画素毎に近傍情報を収集し、その収集したデー
タを近傍情報メモリ２に格納する。

次のステップ５４においては、第１のレジスタ７の内容
を“Ｏ”に初期化して入力方向を０にすると共に、面積
変数Ｓも“０”に初期化する。しかる後に次のステップ
５６へ進み、このステップ５６において、画像の一行目
からラスクー走査を開始し、前記２値画像データに基づ
いて、第１０図ｆａｌの関係を満たす外周境界追跡の開
始点を検索する。

第１Ｏ図（ａｌの関係を満たす境界点が見つかると、ラ
スター走査を中断し、ステップ５８において、第１のデ
コーダ５から行カウンタ３及び列カウンタ４にロード入
力を加え、これら両カウンタ３４に境界の追跡開始点の
アドレスデータ、即ち行アドレスと列アドレスをセット
し、この開始点から時計回りに境界追跡を開始する。

先ず、ステップ６０において、第２のバッファ１０に第
１のデコーダ５から制御信号を送出し、第１のレジスタ
７に一時点に格納された入力方向データをデータバスを
介して画像処理制御装置１へ送出し、このデータを変数
Ｙにセットする。

次に、ステップ６２において、第１のデコーダ５から近
傍情報メモリに続出信号を与え、行カウンタ３と列カウ
ンタ４により指定されるアドレスから、現在の境界点の
近傍情報ベクトルを読出し、これを第２のレジスタ８に
格納する。

そして、次のステップ６４において、第１のレジスタ７
から入力方向の情報が、また第２のレジスタ８から近傍
情報ベクトルがＭＡＰ　　ＲＯＭ１２に入力され、これ
らがアドレス情報としてＭＡＰＲＯＭ内で処理されて出
力方向のデータが出力される。この出力方向のデータは
、方向情報を示す下位３ビツトが第２のデコーダ６に入
力されると共に、全４ビツトが第１のデコーダ５から第
３のバッファ１１に制御信号を送出した段階で第１のレ
ジスタ７にも送出され、このレジスタ７に格納される。

次のステップ６６においては、画像処理制御装置１内で
変数Ｙにセットされた入力方向データを読出し、第２の
レジスタ８に格納する。これにより第１のレジスタ７に
は、現在の境界点の出力方向の情報が、また第２のレジ
スタ８には、現在の境界点の入力方向の情報がそれぞれ
セットされた状態となる。

そして、次のステップ６８においてこの第１及び第２の
レジスタ７．８の内容をアドレス情報としてＭＡＰ　　
ＲＯＭ１２へ出力し、ラベル付けや面積計算の処理を行
なう。

具体的には、この処理を例えば第１３図に示すフローチ
ャートに基づいて行なうもので、先ず、ステップ４０に
おいて、ＭＡＰ　　ＲＯＭ１２から入力方向と出力方向
との組合わせによって予め決められたラベル付け及び面
積計算の有無を表わすデータＫを読出し、これを第３の
バッファ１１を介して画像処理制御装置１へ送る。これ
により、画像処理制御装置１は、ステップ４１，４２，
４３゜４４において、ＭＡＰ　　ＲＯＭ１２から読出し
たＫの値を判別し、Ｋの値が２であれば、ステップ４５
において前記（３）式によりＳの値を更新し、またに＝
１であれば、Ｓを更新しないで共にラベル付を行わずに
第１２図のステップ７０へ進む。また、Ｋ＝６であれば
、ステップ４６へ進んで前記（１１式により、Ｋ＝０で
あれば、ステップ４７へ進んで前記（２）式によりそれ
ぞれＳの値を更新し、Ｋ−７であれば、Ｓを更新しない
で、これらいずれの場合もステップ４８へ進み、現在注
目している境界点にラベルを付け、その後ステップ７０
へ進む。

ステップ７０においては、第２のバッファ１０に第１の
デコーダ５から制御信号を送って、第１のレジスタ７に
格納されている出力方向の情報を画像処理制御袋Ｗ１へ
送出する。この出力方向の情報は最上位ビットが“１”
にセットされており、画像処理制御装置Ｉはこの“工”
を“０”にセットし直し、入力方向の情報として再び第
１のレジスタ７に格納する。これは、境界点が次の境界
点に移行すると、前回の境界点の出力方向が次の境界点
の入力方向になることから、最上位ビットに“１″をセ
ットして表した出力方向データを、最上位ビットだけ変
更してそのまま利用するためである。

そして、次のステップ７２においては、前記出力方向の
データ（３ビツト）が入力された第２のデコーダ６によ
り、行カウンタ３及び列カウンタ４の内容が更新され、
この更新された両カウンタ３，４の内容を次の境界点の
アドレス情報として、第１のバ・７フア９を介して画像
処理制御装置１へ送出し、次の境界点の座標が境界追跡
の開始点のアドレスと同じであるか否かを判定する。こ
れにより、境界点が追跡開始点に戻るまでは、ステップ
６０へ戻って上記処理を繰り返し、追跡開始点に戻った
段階で外周境界追跡とそれに伴うラベル付け及び面積計
算の処理を終了する。

これらの処理を第１４図ｆａ）に示すような具体的な形
状でみれば、第１４図（ｂ）の■の箇所が外周追跡の開
始点になり、ここから境界点の追跡処理とラベル付け及
び面積計算の処理が逐次行われる。

その過程を第７図に示す境界点の一部を抽出してＭＡＰ
　ＲＯＭ１２のアドレス情報と出力情報との関係で説明
すると、注目している境界点がＰ８である場合には、Ｐ
Ｋの入力方向は（０１０）であり、近傍情報ベクトルは
（００１０１０１１）である。第１のレジスタ７は、こ
の情報に最上位ビット“０”を加えた（ＯＯ１０）の４
ビツトのコードとして格納されており、これと近傍情報
ベクトルとをＭＡＰ　　ＲＯＭ１２に入力すると、第６
図のＡのアドレスが指定される。これにより、ＭＡＰ　
　ＲＯＭ１２からは、（１００１）の出力方向に関する
出力情報が出力される。

そして、第１のレジスタ７に格納されていた入力方向は
、第２のレジスタ８にセットされ、また上記出力方向に
関するデータ（１００１）は第１のレジスタ７にセント
され、この入出力方向の情報がＭＡＰ　　ＲＯＭ１２に
入力されると、第６図Ｂのアドレスが指定される。

ここで、明らかなように、出力方向に関する情報を得る
ために指定されたアドレス情報の上位４ビツト（入力方
向の情報）と、その際にＭＡＰ　ＲＯＭ１２から出力さ
れる出力方向に関する情報（４ビツト）は、次のＭＡＰ
　　ＲＯＭ１２の作動時に指定されるアドレスの下位８
ビツトと上位４ビツトにそれぞれ対応している。

そして、図中Ｂのアドレスが指定されたことにより、Ｍ
ＡＰ　ＲＯＭ１２からは（０１１０）ｒ６Ｊの出力情報
が読出され、これにより、この境界点にラベルが付され
ると共に（１）式をもって変数Ｓが更新される。

次に、第１のレジスタ７に格納されている出力方向に関
する情報（１００１）は、画像処理制御装置１で上位１
ビツトが“０”に変換され、その情報（０００１）が再
び第１のレジスタ７にセットされる。それと同時に、第
７図の波線で囲まれた次の境界点（ＰＫ、Ｉ　）の近傍
情報ベクトル（００００１１１１）が、近傍情報メモリ
２がら続出されて第２のレジスタ８にセントされる。そ
して、これらの情報がＭＡＰ　　ＲＯＭ１２に入力され
ると、第６図Ｃのアドレスがセントされ、（１０００）
の出力方向に関する情報が自動的に読出される。

その後、アドレスＣの上位４ビツトのアドレス情報（０
００１）と、出力情報（１０００）とからＭＡＲＲＯＭ
１２のアドレスＤが指定され、以下同様に、次のＭＡＰ
　　ＲＯＭ１２のアドレスが、アドレス領域のうち上位
ピントに“０″を持つ領域と“Ｉ”を持つ領域とから交
互に指定される。

以上の工程を注目している境界点が開始点に戻るまで行
なうと、第１４図（ｅ）に示すように、対象物の左端に
ラベルｒＮＪが付されると共に、「ｓ」には、外周で囲
まれた部分（穴の部分も含む）の面積の値が格納される
。

外周境界追跡によるラベル付と面積計算の処理（ステッ
プ６８）が終わると、第１２図のステ・７ブ７４へ進み
、画像処理制御装置１は、ラスター走査の中断した箇所
（外周境界追跡の開始点）に戻り、この点からラスター
走査を再開し、第１０図（′ｂ）の条件を満たす“１”
の箇所にラベルｒＮＪを付けていく　（第１４図（ｄ）
参照）。そして、このラスター走査によるラベル付処理
は、第１０図（Ｃ１の条件を満たす内周境界追跡の開始
点が見つかるまで行なわれる（ステップ７６）。

内周境界追跡の開始点が見つかると、再びラスター走査
を中断してステップ７８へ進み、このステップ７８にお
いて内周境界追跡の開始点から反時計回りに対象物の内
周を追跡しなからラベル付及び面積計算の処理を行なう
。

その具体的な処理内容は、前記ステップ５８及至７２に
示される処理と同様のもので、ここで注記すべきことは
、前記（４）〜（６）式を用いて面積計算を行なう代わ
りに、外周追跡の面積計算と同様の（１）〜（３）式を
利用している点にある。これは、（４）〜（６）式によ
る面積計算においては、穴の面積がプラスの値として求
まるのに対し、（１）〜（３）式を用いて穴の面積を計
算する場合には、この面積をマイナスの値で表わすこと
ができるので、外周で囲まれた領域の面積と穴の面積と
を別々の変数をもって求めなくても、（１）〜（３）式
を用いれば、前記Ｓの値を順次更新してい（ことで同様
の処理が行なえることによる。

第１４図（ｄｌにおいては、■の箇所が内周境界追跡の
開始点となり、ここから反時計回りに内周追跡が行なわ
れ、それが終了した時点で、第１４図（ｅ）に示すよう
に、内周の右端にラベルｒＮＪが付されると共に、変数
Ｓには、外周で囲まれた領域の面積から穴の面積を差し
引いた目的とする対象物の面積の値が格納される。

そして、内周境界追跡によるラベル付と面積計算の処理
が終わると、ステップ８０へ進み、画像処理制御装置１
は、ラスター走査の中断した箇所く内周境界追跡の開始
点）に戻り、この点から再びラスター走査を開始し、第
１０図（ｂ）の条件を満たす“１”の箇所にラベルｒＮ
Ｊを付けていく。

この処理は画像の最終行に至るまで行われ（ステップ８
２）、この最終行のラスター走査が終了した時点におい
ては、第１４図（ｆ）に示すように、対象物の全類域に
ラベルが付けられる。

尚、この実施例においては、画像対象物が１つだけしか
ない場合について示したが、２つ以上存在する場合にお
いても、同様の原理で、境界追跡が行われ、それぞれ異
なるラベルが付されると共に各対象物の面積が算出され
るものである。

また、対象物の特徴量の算出として面積を算出する場合
を示したが、境界線の周囲長、重心点等の他の特徴量に
ついても、ＭＡＰ　　ＲＯＭ１２の内容を変えることに
より、境界追跡を行ないながらラベル付けと並行して算
出することができるものである。

（発明の効果） 以上述べたように、この発明によれば、入力方向に関す
る情報と近傍画素の情報とに基づいて出力方向に関する
情報を得る場合と、出力方向と入力方向に関する情報に
基づいてラベル付け及び特徴量演算の有無を判別する情
報を得る場合を、タイミングをずらすことで同しハード
ウェア構成をもって処理するようにしたので、従来と同
様の高速処理を少ないハードウェアの構成で実現でき、
もってコストダウンを図ることができるものである。

【図面の簡単な説明】

第１図はこの発明における境界追跡画像処理装置の機能
ブロック図、第２図は画像処理システムを示す概略構成
図、第３図は画素を取り囲む近傍情報ベクトルを説明す
る説明図、第４図は近傍情報メモリの格納状態を示す説
明図、第５図は人出力方向とアドレス情報との関係を説
明する説明図、第６圀はＭＡＰ　　ＲＯＭのアドレスと
出力情報との関係を示す説明図、第７図は境界追跡時に
おける入出力方向と近傍情報ベクトルとの関係を説明す
る説明図、第８図は第２のデコーダのデコード内容を示
す図表、第９図は対象物の面積計算及び境界追跡を説明
するための説明図、第１０図は境界追跡の開始点及びラ
ベル付けの条件を示す図表、第１１図はラベル付け及び
面積計算の有無判断と入出力方向との対応を示す図表、
第１２図はこの画像処理システムの制御動作例を示すフ
ローチャート、第１３図は同上におけるフローチャート
のラベル付け、面積計算の処理例を示すフローチャート
、第１４図（ａ）〜（［１は、対象物のラベル付けの過
程等を説明するために用いる説明図である。 ■・・・画像処理制御装置、２・・・近傍情報メモリ、
３・・・行カウンタ、４・・・列カウンタ、５・・・第
１のデコーダ、６・・・第２のデコーダ、７・・・第１
のレジスタ、８・・・第２のレジスタ、１２・・・ＭＡ
Ｐ　　ＲＯＭ。 第７図 第８図 第１３図 第１４図（ａ’） 第１４図（ｂ） 第１４図（Ｃ） 第１４図（ｄ） 第１４図（ｅ） 第１４図（ｆ）

Claims (1)

1. 【特許請求の範囲】 ２値画像の各画素を取り囲む近傍画素の情報を格納する
   近傍情報格納手段と、 前記２値画像の対象物の境界点のうち注目する境界点の
   １つ前の境界点から見た該注目する境界点の存在方向（
   以下入力方向という）に関する情報と、前記注目する境
   界点からみた次の境界点の存在方向（以下出力方向とい
   う）に関する情報とを選択的に格納する第１の格納手段
   と、 前記近傍情報格納手段に格納された近傍画素の情報と、
   前記入力方向に関する情報とを選択的に格納する第２の
   格納手段と、 第１の格納手段から読出された出力方向に関する情報を
   入力方向に関する情報にしてこれを該第１の格納手段へ
   出力し、第１の格納手段から読出された入力方向に関す
   る情報を前記第２の格納手段へ出力する方向情報制御手
   段と、 前記第１の格納手段に格納された入力方向に関する情報
   と前記第２の格納手段に格納された近傍画素の情報とを
   入力した場合に出力方向に関する情報を出力し、前記第
   １の格納手段に格納された出力方向に関する情報と前記
   第２の格納手段に格納された入力方向に関する情報とを
   入力した場合にラベル付け及び特徴量の演算の有無を判
   別する情報を出力する演算回路と、 この演算回路からの出力に基づいて境界追跡を行ない、
   ラベル付け及び特徴量演算処理を行なう処理実行手段と
   、 前記第１の格納手段に前記方向情報制御手段から入力方
   向に関する情報を読込み、前記第２の格納手段に前記近
   傍情報格納手段から近傍画素の情報を読込むタイミング
   と、前記第１の格納手段に前記演算回路から出力される
   出力方向に関する情報を読込み、前記第２の格納手段に
   前記方向情報制御手段から入力方向に関する情報を読込
   むタイミングとを交互に繰り返すタイミング制御手段と
   、を具備することを特徴とする境界追跡画像処理装置。