JPH0523463B2 - - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、物体を画像処理してその認識を行
なう認識装置、特に複数の物体が互いに接触また
は重なつた物体（以下、重畳物体とも云う。）を
も認識することが可能な認識装置に関する。

〔従来の技術〕

かかる認識の手法には種々のものがあるが、そ
の代表的なものゝ１つとして、米国のスタンフオ
ード大学で開発されたスターンフオードアルゴリ
ズムと呼ばれるものが知られている。以下、その
概要について説明する。

まず、対象物体を白、黒レベルで２値化し、こ
の２値化されたデータからランレングス（白ラン
または黒ランの長さ）によるコード化を行なう。
次いで、ランレングス化されたデータについて連
結性解析を行ない、種々の特徴量を計算する。ま
た、この基本的な特徴量の計算をもとにして、さ
らに多くの有用な特徴パラメータを計算する。そ
して、これらの特徴量およびパラメータを手がか
りとして認識を行なうが、これに先立つて標準サ
ンプルの学習が行なわれる。すなわち、テレビカ
メラ等の撮像装置により各物体を互いに独立に撮
像し、その画像処理を行なつて各種特徴量および
パラメータを計算し、統計処理を行なつた後に平
均値、標準偏差値等を計算して所定のメモリに辞
書として格納する操作が行なわれる。なお、この
操作は対象となる物体の全てに対して行なわれ
る。次いで、未知の物体について特徴量およびパ
ラメータを求め、これらをメモリに記憶されてい
る標準サンプルのそれらと比較し、その差が或る
許容値以下のときに未知物体の同定を行なう。こ
のとき、対象物体の形状や複雑さや対象物の種類
により、さらには識別精度（正確さ）、処理時間
等を考慮し、適切なパラメータを選択して用いる
ようにする。

〔発明が解決しようとする問題点〕

しかしながら、かゝる手法は飽く迄も個々の物
体が互いに分離された状態で識別を行なうことを
前提とするものであるため、複数個の物体が互い
に接触したり、第１６図の如くその一部が重なり
合うと認識が不能になるか、または誤判定すると
云う問題があつた。おお、第１６図は円と四角形
が重なり合つた場合の例である。

したがつて、この発明は重畳物体を含む未知物
体を正しく認識し得るようにすることを目的とす
る。

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

複数種類の認識対象物体の各々についてその輪
郭を追跡してこれを直線部、円弧部等のプリミテ
イブに分割しそれぞれの属性と各頂点の属性とを
辞書として辞書メモリに登録する処理を予め行な
い、しかる後未知物体を辞書と同じくプリミテイ
ブに分割しそのプリミテイブ、頂点の属性により
未知物体を記述して所定のメモリに記憶し、これ
らのデータから未知物体の認識を行なう場合に、
未知物体の各プリミテイブをもとにこれとマツチ
ングするプリミテイブを辞書メモリからそれぞれ
探索しマツチングのとれたものを全てマツチング
組として取り出す辞書探索手段と、このマツチン
グ組の各々について辞書上のプリミテイブ、頂点
と未知物体のそれらとがどれだけマツチングして
いるかの度合を調べてマツチング対応表を作成す
る対応表作成手段と、この対応表より未知物体中
に隠されているプリミテイブまたは頂点を推定し
てプリミテイブ長の修正を行ない辞書とのマツチ
ングの度合を調べた後最適なものを推定物体とし
て取り出す隠れ部分推定手段と、この推定物体を
未知物体から除去しその結果残された部分につい
て如何なるプリミテイブ、頂点を補充すべきかの
推定を行ないその結果にもとづき未知物体を更新
する未知物体更新手段とを設ける。

〔作用〕

第１図はこの発明の一実施例の構成を示すブロ
ツク図である。なお、同図において、１は輪郭追
跡部、２は曲率計算部、３はプリミテイブ記述
部、４は辞書作成部、５は辞書探索部、６はマツ
チング部、７は隠れ部分推定部、８は未知物体更
新部、Ｍ１は辞書データ記憶部、Ｍ２は未知物体
データ記憶部、IDは推定物体データ出力部であ
る。

まず、辞書を作成する（学習処理）。

すなわち、図示されない撮像装置を介して入
力される画像データは、輪郭追跡部１により輪
郭上の境界点座標の列に変換される。なお、輪
郭追跡は、例えば良く知られているフリーマン
コーデイングにより行なわれる。曲率計算部２
は各境界点における曲率を求め、その極大点
（頂点）で境界点列を分割し、プリミテイブと
して取り出す。プリミテイブ記述部３では、こ
うして求めたプリミテイブにつきその平均曲率
によつて分類を行ない、平均曲率が或るしきい
値よりも大きいものを円弧部、小さいものを直
線部とする。辞書作成部４では、各プリミテイ
ブ毎にその属性（種類、長さ、半径、中心座
標、始点頂点No.、終点No.）を調べる一方、頂点
についても属性（種類、座標、角度、入力プリ
ミテイブNo.、出力プリミテイブNo.）を調べ、こ
れらを辞書として記憶部Ｍ１に格納しておく。
こゝで、プリミテイブの始点頂点No.および終点
頂点No.は、プリミテイブの隣接関係を記述する
ために用いられる。また、入力プリミテイブと
はその頂点を終点とするプリミテイブ、出力プ
リミテイブとはその頂点を始点とするプリミテ
イブのことである。

次に、未知物体についても上記と同様な方法
でプリミテイブ分割を行ない、プリミテイブお
よび頂点データによつて物体の記述を行なう。
頂点に関するデータは、記憶部Ｍ２に格納され
る。

辞書探索部５は未知物体のプリミテイブのう
ち最長のものから順に、辞書中にそれとマツチ
ングするプリミテイブがあるかどうかを調べ
る。そして、得られた未知物体中のプリミテイ
ブと辞書中のプリミテイブの組をマツチング組
としてマツチング部（対応表作成部）６へ送
る。このとき、未知物体のひとつのプリミテイ
ブに対して辞書中にマツチングするプリミテイ
ブが多数ある場合は、マツチング組もその数だ
け存在することになる。

次に、マツチング部６は辞書探索部から送ら
れてきたマツチング組のひとつひとつに対し
て、辞書パターンと未知物体上のプリミテイ
ブ、頂点の対応付けを行い、その結果をマツチ
ング対応表に書き入れる。このとき、辞書パタ
ーンのデータと未知物体上で対応付けられたデ
ータとの誤差を、辞書パターンのデータで正規
化したものをマツチング度として定義しておく
ものとする。マツチング組のうち、最も高いマ
ツチング度を持つ１組のマツチング対応表を穏
れ部分推定部７に送る。

マツチング対応表中で辞書パターンのプリミ
テイブ、頂点に対して未知物体上で対応するプ
リミテイブ、頂点がないところは他の物体によ
つて隠されていると考えられるので、隠れ部分
推定部７にて隠されている部分の推定を行う。
推定は一度に１頂点、または１プリミテイブに
ついて行う。頂点が隠れている場合には、その
頂点の両端のプリミテイブを延長してその交点
を求めることにより頂点の位置および角度の推
測を行い、両方のプリミテイブ長の修正を行
う。一方、プリミテイブが隠れていて、辞書中
では１つのプリミテイブとなつているものが未
知物体中で他の物体によつて隠され２本以上に
分断されている時は、両方のプリミテイブの延
長、接続によつてプリミテイブ長の修正を行
う。こうして推定を行つた結果、辞書中のパタ
ーンと一致する物体が構成できれば、これを推
定物体として出力部IDへ出力する。推定を行
つても辞書パターンと一致しない場合はマツチ
ング部６へ戻り、次にマツチング度の高かつた
組合わせのマツチング対応表を持つて来て、再
び隠れ部分の推定を行う。

隠れ部分推定部７から辞書中の推定物体が出
力された場合 未知物体からこの推定物体を除去する働きをす
るのが未知物体更新部８である。未知物体更新部
８は未知物体から辞書との対応のついたプリミテ
イブ、頂点を除去し、その後残つた空白部分につ
いてこゝに何を補充すべきかの推定を行い、頂点
角度、プリミテイブ長および接続関係等の修正を
行う。そして、この修正または更新された物体を
新たに未知物体として入力し、辞書探索部５から
同じ処理を繰り返す。最後に、辞書と一致する未
知物体が残れば全処理終了となる。

〔実施例〕

第２図はこの発明が適用される認識装置を示す
構成図である。同図において、１０は対象物体、
１１はテレビカメラの如き撮像装置、１２は増幅
器および２値化回路等を含む前処理回路、１３は
物体の各種特徴量を抽出する特徴抽出回路、１４
は画像メモリ、１５はマイクロプロセツサ等から
なる処理装置（プロセツサ）、１６はインタエイ
ス回路、１７はキーボードやデイスプレイからな
る端末、Ｍはデータメモリで第１図の記憶部Ｍ
１，Ｍ２を包含している。すなわち、テレビカメ
ラ１１を介して得られる対象物体１０の映像信号
（ビデオ信号）は、前処理回路１２にて２値化さ
れ、さらに特徴抽出回路１３によりセグメント
（ランレングスに相当する）情報として画像メモ
リ１４に書き込まれる。このデータをプロセツサ
１５で処理し、辞書の作成や未知物体の記述を行
ない、メモリＭに格納する。しかる後、このデー
タにもとづき第１図で説明したような処理を行な
うことにより、未知の重量物体から個々の物体を
分離して認識することができるようにする。な
お、インタフエイス回路１６を介して端末１７か
らキー入力することにより、２値化しきい値等の
変更が可能であり、処理結果をデイスプレイ上で
見ることも可能である。

その動作の概要は第１図で説明したとおりであ
るが、以下に特徴となる各部の動作について詳細
に説明する。なお、第１図の輪郭追跡部１、曲率
計算部２、プリミテイブ記述部３および辞書作成
部４を介して得られる辞書パターンとそのデータ
がそれぞれ第３図（辞書１）、第４図（辞書２）
および第５図（辞書３）の如く表わされるものと
し、第６図の如き未知の重量物体を識別する場合
を具体例として説明する。なお、第６Ａ図は第６
図に示すプリミテイブのデータを説明するための
説明図、第６Ｂ図は同じくその頂点データを説明
するための説明図である。

まず、辞書探索部について説明する。

辞書探索部は未知物体の最長プリミテイブに対
しそのプリミテイブとマツチングするプリミテイ
ブを辞書中から探索する。マツチングの条件は、
以下のとおりである。

・ 直線プリミテイブの場合 辺の長さと両端の角度が一致するプリミテイブ ・ 円または円弧プリミテイブの場合 半径の一致するプリミテイブ ここでいう一致とは、その差が許容誤差範囲内
にある場合を含むものとする。未知物体中の最長
プリミテイブに対し、マツチングするプリミテイ
ブが見つからない場合は、次に長いプリミテイブ
に対して探索を行う。探索によつて得られた辞書
中のプリミテイブ全部に対して、次の如く表わさ
れるマツチング組 （辞書No.−辞書中プリミテイブNo.、未知物体プ
リミテイブNo.（PRNo.）、マツチング度） をマツチング部へ送る。

未知物体中の第ｉプリミテイブと、辞書ｊの第
ｋプリミテイブがマツチングした場合のマツチン
グ度M_i-jkを、次式にて算出する。

M_i-jk＝｛１−｜L_i−L_jk｜／L_jk｝ ×｛１−｜R_i−R_jk｜／R_jk｝ ×｛１−｜T_i ^-−T_jk ^-｜／T_jk ^-｝ ×｛１−｜T_i ⁺−T_jk ⁺｜／T_jk ⁺｝ …(1) こゝに、L_iは未知物体の第ｉプリミテイブ長、
R_iは同じくその半径、T_i ^-は同じくその始点角度、
T_i ⁺は同じくその終点角度である。また、L_jkは辞
書ｊの第ｋプリミテイブ長、R_jkは同じくその半
径、T_jk ^-は同じくその始点角度、T_jk ⁺は同じくそ
の終点角度である。なお、(1)式で直線プリミテイ
ブの場合は第２項＝１とし、また円、円弧プリミ
テイブの場合は第３項＝第４項＝１とする。

第６図の例における最長プリミテイブは長さ
140の円弧プリミテイブ７である。辞書中よりこ
れにマツチングするプリミテイブを探索すると、
第３図に示す辞書１のプリミテイブ１（PR1）が
見つかるが、このときのマツチング度M⁷ _1-1は、 M⁷ _1-1＝｛１−｜R₇−R₁₁｜／R₁₁｝ ｛１−｜L₇−L₁₁｜／L₁₁｝＝｛１−｜30−30｜／30｝ ｛１−｜140−188｜／188｝＝0.74 となる。他にこのプリミテイブにマツチングする
プリミテイブは辞書中には存在しないので、次の
如きマツチング組 （辞書１−PR1，PR7，0.74） をマツチング部へ送る。なお、第３図ロのＸ，Ｙ
は中心のＸ座標、Ｙ座標を示す。

第７Ａ図ないし第７Ｅ図は、辞書探索部におけ
る以上の如き動作を説明するためのフローチヤー
トである。

すなわち、第７Ａ図は最も長いプリミテイブを
探索するための部分フローチヤートであり、未知
物体のプリミテイブ番号を“１”最長のプリミテ
イブ長を“L₁”と仮定して処理を開始し、最長
のプリミテイブ番号I_MAXとその長さL_MAXを抽出す
る。また、第７Ｂ図は最長のプリミテイブが円の
場合の動作を説明するための部分フローチヤー
ト、第７Ｃ図は最長のプリミテイブが円弧の場合
の動作を説明するための部分フローチヤート、第
７Ｄ図は最長のプリミテイブが直線の場合の動作
を説明するための部分フローチヤート、第７Ｅ図
はマツチング組があつた場合となかつた場合の動
作を説明するための部分フローチヤートである。
なお、これらの図において、ｉは未知物体のプリ
ミテイブ番号、ｊは辞書番号、ｋは辞書ｊのプリ
ミテイブ番号、Ｎは未知物体のプリミテイブ総
数、ｍは辞書総数、N_jは辞書ｊ上のプリミテイ
ブ総数をそれぞれ表わしている。

マツチング部（対応表作成部） こゝでは、辞書探索部から送られてきたマツチ
ング組のひとつひとつについて、辞書上のプリミ
テイブ、頂点と未知物体とがどれだけマツチング
しているかを調べ、マツチング対応表を作成す
る。

いま、辞書探索部から（辞書ｊ−PRk，PRi，
Mⁱ _j-k）なるマツチング組が送られてきたとする。
これは、未知物体中の第ｉプリミテイブと辞書ｊ
の第ｋプリミテイブがマツチングがとれているこ
とを意味する。マツチング対応表は対応するプリ
ミテイブ、頂点とそのマツチング度を一覧表にし
たものである。なお、プリミテイブと頂点とで
は、マツチング度の定義が異なる。すなわち、プ
リミテイブのマツチング度MPⁱ _j-kは、 MPⁱ _j-k＝｛１−｜R_i−R_jk｜／R_jk｝ ×｛１−｜L_i−L_jk｜／L_jk｝ …(2) であり、頂点のマツチング度は、 MAⁱ _j-k＝｛１−｜T_i−T_jk｜／T_jk｝ …(3) である。こゝに、T_iは未知物体上の第ｉ頂点の角
度、T_jkは辞書ｊの第ｋ頂点の角度をそれぞれ表
わしている。

まず、マツチング組に記載されているプリミテ
イブ、頂点の対応関係を対応表へ書き写す。マツ
チング表は辞書中の全要素（プリミテイブ、頂点
を合わせたものを要素と呼ぶ。）について、 （辞書上のマツチング要素、未知物体上のマツ
チング要素、マツチング度） という値の組を並べたものである。辞書要素に対
応する未知物体上の要素がない場合はマツチング
表内の第２項，第３項には０（ゼロ）を入れるこ
とゝする。この部分は後のステツプでの推定対象
となる。つまり、第７Ａ図ないし第７Ｅ図では未
知物体のプリミテイブをもとに辞書を探索した
が、こゝでは逆に辞書から未知物体を探索する。
その動作を示すのが第８Ａ図ないし第８Ｋ図であ
る。まず、未知物体の第ｉプリミテイブと、辞書
ｊの第ｋプリミテイブとがマツチングしているか
ら、i₀＝ｉ，k₀＝ｋとして辞書ｊが円か否かを判
別する（第８Ａ図○イ，○ロ参照）。

Ａ 辞書ｊが円である場合 マツチング組の内容をそのままマツチング対応
表に書き写す。次に、未知物体上で第ｉプリミテ
イブと半径、中心が一致する円弧プリミテイブを
探し、あれば辞書ｊの第１プリミテイブ（円は物
体上にひとつのプリミテイブしかない）とそのプ
リミテイブとのマツチング度を求めて、マツチン
グ対応表に追加する。

Ｂ 辞書ｊの第ｋプリミテイブが直線である場合 Ｂ−１ この場合、第８Ａ図のから第８Ｂ図
のへと進み、まず、マツチング組を３つの
要素（始点頂点、プリミテイブ、終点頂点）
に分け、それぞれのマツチング度とともにマ
ツチング対応表に書く（第８Ｂ図○イ，○ロ，○ハ
参照）。

いま、例えばマツチング組として（辞書ｊ
−PRk，PRi，Mⁱ _j-k）が送られてきたとす
る。ここで、辞書ｊのプリミテイブｋは直線
である。したがつて、辞書ｊのプリミテイブ
ｋと未知物体上のプリミテイブｉとがマツチ
ングしたということは、その始点角度、プリ
ミテイブ長（半径）、終点角度の３つの要素
がマツチングしたということであるので、 （ｊ−Ak^-，Ai^-，MA^i- _j-k ^-）：始点角度 （ｊ−PRk，PRi，MPⁱ _j-k）：プリミテイブ （ｊ−Ak⁺，Ai⁺，MAⁱ⁺ _j-k ⁺）：終点角度 の３つをマツチング対応表に書く。こゝに、
Ak^-，Ai^-はそれぞれ第ｋプリミテイブの始
点、第ｉプリミテイブの始点、Ak⁺，Ai⁺は
それぞれ第ｋプリミテイブの終点、第ｉプリ
ミテイブの終点を示す。そして、最初にマツ
チング組で送られてきたｋ，ｉをそれぞれ
k₀，i₀として残しておく。これは、マツチン
グの終了チエツクに使用する（第８Ａ図○イ参
照）。

Ｂ−２ マツチング組によつて対応づけられた
プリミテイブから、反時計回りの方向にどれ
だけ対応付けができるかを調べる。この場
合、第８Ｂ図のから第８Ｃ図のに進む。
辞書について、第ｋプリミテイブに反時計回
り方向に隣接するプリミテイブは ｋ＝ｋ mod N_j＋１ となる。こゝに、N_jは辞書ｊ中のプリミテ
イブ総数である。なお、Ａ modBはＡをＢ
で割つたときの余りを表わす。一方、未知物
体中の第ｉプリミテイブに反時計回り方向に
隣接するプリミテイブは、未知物体上のプリ
ミテイブ総数をＮとすれば、 ｉ＝ｉ modN＋１ であり、この２つのプリミテイブの長さを比
較する（第８Ｃ図○イ参照）。

Ｂ−２− L_i＜L_jkの場合 この場合、第８Ｃ図のから第８Ｄ図の
へ分岐する。このとき、辞書ｊの第ｋプ
リミテイブに対応する未知物体上のプリミ
テイブが他の物体によつて一部隠されてい
ることになる。そこで、まずL_iとL_jkにつ
いてマツチング対応表に次の値を書き加え
る（第８Ｄ図○イ参照）。

（辞書ｊ＝PRk，PRi，MPⁱ _j-k） しかる後、未知物体上に辞書ｊの第ｋプリ
ミテイブに対応する残りのプリミテイブが
あるかどうか調べる。調べ方は、変数ii＝
ｉとし ii＝imodN＋１ の如く更新して未知物体を反時計回りの方
向に辿つてゆき、第ｉプリミテイブと同一
直線上にあるプリミテイブで、かつ始点間
距離がL_jk以下のものを探す（第８Ｄ図○ロ，
○ハ参照）。

ａ○ ii＝i₀−１までで見つからなかつた場合は、
第８Ｄ図のから第８Ｅ図のへ分岐し、こ
の方向の探索を打ち切る。そして、kfwd＝
ｋとして、次の逆方向探索Ｂ−ii−３）項
（）へ進む。

ｂ○ 見つかつた場合 Γ 第ｉプリミテイブ始点と第iiプリミテイ
ブ終点間距離＜L_jkのときは、 （辞書ｊ−PRk，PRii，MPⁱⁱ _j-k） をマツチング対応表に加え、第８Ｄ図のか
ら○ロへ戻り、さらに探索を続ける。

Γ 第ｉプリミテイブ始点と第iiプリミテイ
ブ終点間距離＝L_jkのときは、 （辞書ｊ−PRk，PRii，MPⁱⁱ _j-k） をマツチング対応表に加え、ｉ＝iiとして第
８Ｃ図のに進む。

Γ 第ｉプリミテイブ始点と第iiプリミテイ
ブ終点間距離＞L_jkのときは、第８Ｄ図の
から第８Ｅ図のへ分岐する。この場合、第
iiプリミテイブは辞書ｊの第ｋプリミテイブ
に対応するプリミテイブと他のプリミテイブ
が重なつているものと考えられる。従つて、
これを分割して、辞書ｊの第ｋプリミテイブ
に対応する分だけについてマツチングを求め
る。そのため、第ｉプリミテイブの始点から
L_jkだけ離れた第iiプリミテイブ上の点の座標
を求め、この点と第iiプリミテイブ始点との
距離をL_ii′とし、このL_ii′を使用してマツチ
ング度 MPⁱⁱ′_j-k＝｛１−｜L_ii′−L_jk｜／L_jk｝ を求め、 （辞書ｊ−PRk，PRii，MPⁱⁱ′_j-k） をマツチング対応表中に書き込む。ｉ＝iiと
した後の処理は、次のＢ−２−iii）項のｂ○と
同じである。

Ｂ−２−ii L_i＝L_jkの場合 ａ○ 辞書ｊの第ｋプリミテイブと未知物体上の
第ｉプリミテイブが対応付けられたの
で、 （辞書ｊ−PRk，PRi，MPⁱ _j-k） をマツチング対応表に加える（第８Ｃ図
○ロ，○ハ参照）。

ｂ○ 終点の頂点同志が対応しているかどうかを
調べる。その前に、未知物体と辞書ｊが
全く同一のものであつた場合、辞書ｊに
ついてひととおり対応付けが終了したか
どうかをチエツクするために、第ｋプリ
ミテイブの終点の頂点No.と第k₀プリミテ
イブの始点の頂点No.が等しいかどうかを
みる（第８Ｃ図○ニ参照）。等しければ、
マツチング対応表の作成を終了する（
参照）。等しくない場合は、未知物体の
第ｉプリミテイブの終点と辞書ｊの第ｋ
プリミテイブの終点が種類、角度ともに
等しいかを調べる（第８Ｃ図○ホ参照）。

Γ 等しい場合は頂点のマツチング度を
求め、 （辞書ｊ−k⁺，i⁺，MAⁱ⁺ _j-k ⁺） をマツチング対応表に加え、次に隣接す
るプリミテイブのチエツクへ戻る（第８
Ｃ図参照）。

Γ 等しくない場合は、辞書ｊの第ｋプ
リミテイブの終点に対してマツチングす
る頂点がないので、第８Ｃ図のを経て
第８図のへ進み、 （辞書ｊ−k⁺，０，０） をマツチング対応表に加え、kfwd＝ｋ，
ifwd＝ｉとしてこの方向のマツチング
を終了し、次のＢ−３項へ進む。

Ｂ−２− L_i＞L_jkの場合 この場合、第８Ｃ図のから第８Ｅ図のへ分
岐する。このとき、未知物体上の第ｉプリミテイ
ブは辞書ｊの第ｋプリミテイブに対応するプリミ
テイブと他のプリミテイブとが重なつているもの
と考えられる。

ａ○ 第ｉプリミテイブのうち、辞書ｊの第ｋプ
リミテイブと対応する部分についてマツ
チングをとる。MPⁱ _jk＝１とし （辞書ｊ−PRk，PRi，１） をマツチング対応表に追加する。

ｂ○ 未知物体上の第ｉプリミテイブは辞書ｊの
第ｋプリミテイブに対応する部分とそう
でない部分に分割されることを示すた
め、未知物体プリミテイブデータの分割
フラグを立てる（第８Ｅ図○イ参照）。

ｃ○ 辞書ｊの第ｋプリミテイブの終点角につい
ては角度＝180゜のため、マツチングがと
れないので、 （辞書ｊ−k⁺，０，０） をマツチング対応表に加え、kfwd＝ｋ，
ifwd＝ｉとしてこの方向のマツチング
を終了し、次のＢ−３項へ進む。

Ｂ−３ 反時計回りの方向のマツチングにより対
応付けが終らなかつた場合、時計回り方向
についても同様の方法によりマツチングを
行う。このとき、 ｋ＝（ｋ＋N_j−１）mod N_j ｉ＝（ｉ＋Ｎ−１）mod Ｎ とすれば、それぞれ辞書ｊ上および未知物
体上で時計回りの方向に隣接するプリミテ
イブが求められる。その動作は第８Ｆ図な
いし第８Ｈ図の如く行なわれるが、方向が
時計回りであることを除けば先のＢ−２項
と全く同様なので、省略する。なお、第８
Ｆ図，第８Ｇ図および第８Ｈ図はそれぞれ
第８Ｃ図，第８Ｄ図および第８Ｅ図と対応
する。また、対応付けがとれなくなつたと
ころで、kbck＝ｋ，ibck＝ｉとして次の
Ｂ−４項へ進む。

Ｂ−４ 両方向のマツチングを行つても対応付不
可能なプリミテイブがある場合 Ｂ−４− 両方向のマツチングにより、辞書上
のプリミテイブで対応付不可能なプリミテ
イブが１本だけ残つた場合（第８Ｉ図，第
８Ｊ図参照）。

辞書ｊの第kfwdプリミテイブと第kbck
プリミテイブとの間に対応付けの不可能な
プリミテイブが１本だけ残つた場合は、次
の方法によりその間のプリミテイブへの対
応付けを行う。

ａ○ 辞書ｊの第kbckプリミテイブの終点
kbck⁺に対応する未知物体上の頂点よ
り、未知物体上の第ibckプリミテイブの
方向に距離L_jkbckだけ離れた点の座標
（x₁，y₁）を求める（第８Ｉ図○イ参照）。

ｂ○ 辞書ｊの第kfwdプリミテイブの始点
kbck^-に対応する未知物体上の頂点よ
り、未知物体上の第ifwdプリミテイブ
の方向に距離L_jkfwdだけ離れた点の座標
（x₂，y₂）を求める（第８Ｉ図○ロ参照）。

ｃ○ 未知物体上でｉ＝ifwd modN＋１からｉ
＝（ibck＋Ｎ−１）mod Ｎまでのプリミ
テイブの中で（x₁，y₁）と（x₂，y₂）を
結んだ直線上にあるものを探し、あれば
マツチング対応表に （辞書ｊ−PRk，PRi，MPⁱ _j-k） を加える。なければ、 （辞書ｊ＝PRk，０，０） とする（第８Ｊ図参照）。

Ｂ−４− 両方向のマツチングにより辞書上の
プリミテイブのうち対応付けできなかつた
ものが２本以上残つた場合、ｋ＝kfwd
mod N_j＋１からｋ＝（kbck＋N_j−１）
mod N_jまでの要素（プリミテイブ頂点）
について、 （辞書ｊ−PRk，０，０）……プリミテ
イブ （辞書ｊ−Ak⁺，０，０）……頂点 をマツチング対応表に加える（第８Ｋ図参
照）。

第６図の例のマツチング組（辞書１−
PR1，PR7，0.74）に対するマツチング対
応表を作成すると、未知物体中の第８プリ
ミテイブが半径、中心座標ともに一致する
ので、第９図のようになる。

隠れ部分推定部 こゝでは、マツチング部から送られてきたマツ
チング対応表より、未知物体中の隠れたプリミテ
イブ、頂点の推定を行う。

○ プリミテイブ推定 マツチング対応表中の１つの辞書プリミテイブ
に対して、未知物体上の２本以上のプリミテイブ
が対応している場合、これらのプリミテイブは途
中が隠されていると考えられるので、その部分を
推定する。辞書中の円プリミテイブと未知物体中
の複数の円弧プリミテイブが対応している場合は
これらの円弧プリミテイブから辞書ｊの円を推定
し、マツチング対応表に加える。また、辞書中の
直線プリミテイブと未知物体中の複数の直線プリ
ミテイブが対応している場合、これらの直線プリ
ミテイブのうち最も外側の端点間の距離をプリミ
テイブ長として推定する。推定によつてできた新
しいプリミテイブと辞書ｊのプリミテイブｋとの
マツチング度を求め、マツチング対応表に加え
る。

○ 頂点推定 マツチング対応表中、辞書中の頂点に対応する
頂点が未知物体上にない場合、頂点の両端のプリ
ミテイブの交点を求め、頂点の推定を行う。そし
て、両端のプリミテイブの長さも推定した頂点を
使つて求め直し、マツチング度も推定した頂点、
プリミテイブについて新たに計算する。

○ 推定図形チエツク マツチング対応表の推定項目についてのデータ
も利用して、推定図形が果して辞書とマツチング
がとれるかどうかをチエツクする。すなわち、円
の場合は、辞書の円と推定図形の円の半径の差が
許容誤差範囲内にあれば、推定図形の円を出力す
る。直線から構成される図形の場合は、辞書中の
全てのプリミテイブ、頂点について推定により対
応付けられるものがあり、かつ全ての対応につい
てマツチング度が基準値以上であれば推定図形を
出力する。推定図形が出力できない場合は、マツ
チング部へ次のマツチング対応表を送れとの指示
を出す。

第６図の例について、第９図○イに示すようなマ
ツチング対応表がマツチング部から来る。これに
対し、隠れ部分推定部では未知物体中のPR7と
PR8より円を推定する。こゝに、推定された円の
半径は２つのプリミテイブの半径の平均とする。
ここでは、31となる。辞書１のPR1の半径は30な
ので、マツチング度は、 M¹¹ _1-1＝｛１−｜R_1-1−R₁₁｜／R_1-1｝ ×｛１−｜L_1-1−L₁₁｜／L_1-1｝ ＝｛１−｜30−31｜／30｝ ×｛１−｜180−195｜／188｝ ＝0.93 となり、マツチング度の許容範囲を0.9以上とす
ると、推定物体は辞書１に一致したとしてよいの
で、推定物体として辞書１を出力する。

第９図○ロはPR7とPR8より推定したPR11を加
えたプリミテイブ対応関係を示すものである。

未知物体更新 推定物体が隠していた部分を未知物体をもとに
推定してやり、もとの未知物体から推定物体を除
去したものを新たに未知物体として更新する。

１ 推定物体に含まれる未知物体上のプリミテイ
ブ、頂点を除去する。ただし、推定物体に含ま
れていても、未知物体のプリミテイブデータの
分割フラグが立つているプリミテイブについて
は、そのプリミテイブは一部が推定物体に含ま
れていたということなので、そのまま残してお
く。これにより、未知物体上には輪郭として切
断された部分が生じる。

２ この切断された部分について推定を行うが、
その推定方法は基本的には隠れ部分推定部と同
じである。すなわち、推定物体により抜き出さ
れた切断部が一カ所の場合にはその前後のプリ
ミテイブについて、また切断部が２カ所以上の
場合は推定物体として抜き出されたあるプリミ
テイブの終点を始点するとプリミテイブと、時
計回りの方向に見て次に抜き出されたプリミテ
イブの始点を終点とする２つのプリミテイブの
組について行う。指定方法は、次の通りであ
る。

両方のプリミテイブがともに円弧の場合 ２つの円弧を接続して１つの円または円弧と
する。

両方のプリミテイブがともに直線で同一直
線上にある場合 ２つのプリミテイブを接続して１つの直線
プリミテイブとする。

両方のプリミテイブがともに直線で同一直
線上にない場合 ２つの直線延長線上の交点を求め、これを
新しく頂点とする。

一方のプリミテイブが円弧で一方のプリミ
テイブが直線の場合 円弧と直線をそれぞれ延長した交点を求め、こ
れを新しく頂点とする。これにより、未知物体の
プリミテイブデータおよび頂点データも変更す
る。分割フラグが立つていたプリミテイブでは、
このプリミテイブと他のプリミテイブとの交点
が、プリミテイブの延長線上でなくプリミテイブ
上に表われることもある。この場合、交点から先
のプリミテイブは無視してよい。第１５Ａ図，１
５Ｂ図はこのような場合を示すもので、こゝでは
プリミテイブPR3，PR4が無視されている。

第６図の例で円と推定された未知物体上のプリ
ミテイブ７と８を除去した状態を示すのが第１０
図である。

ここで、前述のルールに従つてプリミテイブ７
の終点を始点とするプリミテイブ、つまりプリミ
テイブ１とプリミテイブ８の始点を終点とするプ
リミテイブ、すなわちプリミテイブ１０とから隠
し部分の推定を行うと、このプリミテイブは同一
直線上にない直線であるから、上記２−項より
第１０図の如き頂点Ｇを推定することができる。
同様に、プリミテイブ６とプリミテイブ７から頂
点Ｆを推定する。こうして第１１図の如き新しい
未知物体ができたので、これを再び未知物体とし
て入力する。この新たな未知物体中の最長プリミ
テイブは長さ62のプリミテイブ５なので、辞書探
索部はプリミテイブ５とマツチングするプリミテ
イブを辞書中から探し、辞書３のプリミテイブ
１，２，３を候補とする。しかし、辞書３は３回
転対称なので、どのプリミテイブが対応しても同
じである。そこで、マツチング組 （辞書３−PR1，PR5，0.97） をマツチング部へ送る。マツチング部でマツチン
グ対応関係を作成すると第１２Ａ図に示すものが
できる。これより、未知物体中のプリミテイブ７
とプリミテイブ４より穏れたプリミテイブを推定
し、これを新しくプリミテイブ９とする。このプ
リミテイブ長は頂点Ｄと頂点Ｆとの距離＝59とな
るので、プリミテイブ対応関係は第１２Ｂ図のよ
うになる。

このときの、平均マツチング度は、 １＋0.97＋１＋0.97＋１＋0.98／６＝0.99 となり、マツチング度の許容範囲0.9以上を満足
しているので、推定物体として辞書３を出力す
る。第１３図に推定物体として未知物体中のプリ
ミテイブ４，５，６，７を抜き出したところを示
す。

次に、残つた未知物体中のプリミテイブのうち
接続関係の中断しているプリミテイブ３と８より
頂点を推定し、プリミテイブ、頂点データを更新
すると第１４図のようになる。これを、再び新た
な未知物体として入力してやると、最長プリミテ
イブ３と辞書２のプリミテイブ１とのマツチング
組（辞書２−PR1，PR3，0.98）が辞書探索部か
ら出力される。これについてマツチング対応関係
を作成すると第１４Ｃ図のようになる。その平均
マツチング度は、 １／８（0.98＋0.98＋0.98＋0.95＋0.98＋0.95＋１ ＋0.95）＝0.97 となり、推定物体として辞書２が出力される。

以上により、未知物体上のプリミテイブのうち
対応のつかないものはなくなつたので、処理を終
了する。その結果、未知物体は辞書１，２，３の
重なり合つたものとして認識されることになる。

〔発明の効果〕

この発明によれば、未知物体の認識を行う場
合、未知物体上のプリミテイブとマツチングする
プリミテイブを辞書中から探索し、辞書と未知物
体のプリミテイブ、頂点の対応付けを行い、未知
物体上で隠れているプリミテイブ、頂点を推定す
るという手法をとるようにしているため、複数個
の認識対象物体が互いに重なり合つているような
重畳物体でも認識ができるようになり、その適用
範囲を広げることが可能となる利点がもたらされ
る。

【図面の簡単な説明】

第１図はこの発明の一実施例の構成を示すブロ
ツク図、第２図はこの発明が適用される認識装置
を示す構成図、第３図は円の辞書パターンとデー
タを説明するための説明図、第４図は四角形の辞
書パターンとデータを説明するための説明図、第
５図は三角形の辞書パターンとデータを説明する
ための説明図、第６図は重なり合つた未知物体パ
ターンの一例を示す説明図、第６Ａ図は第６図に
示すプリミテイブのデータを説明するための説明
図、第６Ｂ図は同じく頂点のデータを説明するた
めの説明図、第７Ａ図ないし第７Ｅ図は辞書探索
部の動作を説明するためのフローチヤート、第８
Ａ図ないし第８Ｋ図はマツチング部の動作を説明
するためのフローチヤート、第９図は第６図の例
における未知物体と辞書との対応関係を説明する
ための説明図、第１０図は円の推定物体を未知物
体から除去した場合を説明する説明図、第１１図
は更新された未知物体を示すパターン図、第１１
Ａ図は第１１図のプリミテイブデータを説明する
ための説明図、第１１Ｂ図は同じくその頂点デー
タを説明するための説明図、第１２Ａ図は第１１
図に示す未知物体と第５図に示す辞書との対応関
係を示す説明図、第１２Ｂ図は第１２Ａ図におい
て推定が行なわれた場合の対応関係を示す説明
図、第１３図は三角形の推定物体を更新された未
知物体から除去する場合を説明する説明図、第１
４図は再度更新された未知物体を示すパターン
図、第１４Ａ図は第１４図のプリミテイブデータ
を説明するための説明図、第１４Ｂ図は同じくそ
の頂点データを説明するための説明図、第１４Ｃ
図は第１４図に示す未知物体と第４図に示す辞書
との対応関係を示す説明図、第１５Ａ図は２つの
辞書の辞書のプリミテイブ同志が重なつた場合を
示すパターン図、第１５Ｂ図は第１５Ａ図より三
角形を除去した場合を示すパターン図、第１６図
は重なり合つた物体を示すパターン図である。 符号説明、１…輪郭追跡部、２…曲率計算部、
３…プリミテイブ記述部、４…辞書作成部、５…
辞書探索部、６…マツチング部（対応表作成部）、
７…隠れ部分推定部、８…未知物体更新部、１０
…認識対象物体、１１…撮像装置（テレビカメ
ラ）、１２…前処理回路、１３…特徴抽出回路、
１４…画像メモリ、１５…プロセツサ、１６…イ
ンタフエイス回路、１７…端末、Ｍ，Ｍ１，Ｍ２
…メモリ、ID…推定物体データ出力部。

Claims (1)

1. 【特許請求の範囲】 １ 複数種類の認識対象物体の各々についてその
   輪郭を追跡し直線部、円弧部を含むプリミテイブ
   に分割してそれぞれの属性と各頂点の属性とを辞
   書として辞書メモリに登録する処理を予め行な
   い、しかる後未知物体を辞書と同じくプリミテイ
   ブに分割しそのプリミテイブ、頂点の属性により
   未知物体を記述して所定のメモリに記憶し、未知
   物体と辞書の各記載データにもとづき未知物体を
   認識する認識装置であつて、 未知物体の各プリミテイブをもとにこれとマツ
   チングするプリミテイブを前記辞書メモリからそ
   れぞれ探索しマツチングのとれたものを全てマツ
   チング組として取り出す辞書探索手段と、 該マツチング組の各々について辞書上のプリミ
   テイブ、頂点と未知物体のそれらとがどれだけマ
   ツチングしているかの度合を調べてマツチング対
   応表を作成する対応表作成手段と、 該マツチング対応表より未知物体の中に隠され
   ているプリミテイブまたは頂点を推定してプリミ
   テイブ長の修正を行ない辞書とのマツチングの度
   合を調べた後最適なものを推定物体として取り出
   す隠れ部分推定手段と、 該推定物体を未知物体から除去しその結果残さ
   れた部分について如何なるプリミテイブ、頂点を
   補充すべきかの推定をし該推定結果にもとづき未
   知物体を更新する未知物体更新手段と、 前記未知物体の更新を未知物体のプリミテイブ
   の対応のつかないものがなくなるまで繰り返し行
   なうことにより、複数の物体が接触または重なつ
   て形成される未知物体の認識をも可能にする手段
   と、 から成ることを特徴とする物体認識装置。