JPH07220089A

JPH07220089A - 位置検出方法

Info

Publication number: JPH07220089A
Application number: JP6009274A
Authority: JP
Inventors: Takashi Anezaki; 隆姉▲崎▼
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1994-01-31
Filing date: 1994-01-31
Publication date: 1995-08-18

Abstract

(57)【要約】【目的】任意の形状の物体に適用できて汎用性があ
り、且つ、高速に処理できて、耐ノイズ性が高い画像認
識による位置検出方法の提供。【構成】走査検出した画像輪郭点が既検出か未検出か
を、既検出画像輪郭点Ｇを記憶しているオーバレイメモ
リによって判断し、未検出の画像輪郭点Ｇを始点として
輪郭線追跡Ｈを開始し、参照点への到着方向番号別の画
像輪郭点探索方向番号表の探索方向順に基づいて２値化
画像をアクセスして次の画像輪郭点を検出し、前記オー
バレイメモリによって、輪郭線追跡終了点を検出して、
現輪郭線追跡を終了し、前記始点の次の点から走査を継
続して、外側画像輪郭線Ｉ、画像内部の輪郭線Ｄ、Ｅ、
Ｆを検出し、検出された輪郭線の特徴点を検出し、これ
らの特徴点間の距離角度の累積演算結果を用いて形状照
合し、位置を検出する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、視覚システムにおける
物体の位置検出方法に関し、特に、２値化画像上で対象
物の画像が有する輪郭線を検出しその輪郭線に基づいて
対象物の位置を検出する位置検出方法に関する。

【０００２】

【従来の技術】最近、米国や日本において、物体の識別
や位置認識等に使用する汎用の視覚システム（ビジョン
・システム）が多数開発されている。これらのシステム
で物体の識別や位置認識等に使用される従来の一般的な
方法は、主として、次の２種類である。

【０００３】第１の方法は、画像データ上の物体の画像
領域を統計的に処理する方法である。例えば、面積、長
径や短径、慣性モーメント等の統計量を基準として、物
体の形状、位置、方向を検出する方法である。

【０００４】第２の方法は、物体が有する特徴ある形状
に合わせてテンプレート（基準画像）を使用し、このテ
ンプレートで、前記物体を撮像して得られた画像を走査
し、前記画像とテンプレートとの間で相関演算を行い、
その相関係数に基づいて、前記画像の中で前記特徴ある
形状が存在する位置を識別し、その位置によって前記物
体の位置を検出する方法である。

【０００５】しかし、第１の方法では、輪郭形状を直接
使用していないので、輪郭検出の精度が不足するという
問題点がある。

【０００６】又、第２の方法では、使用するテンプレー
トの大きさや方向等の限定条件が派生し、汎用化が困難
であるという問題点がある。

【０００７】上記の問題点の対策として、図１６に示す
ように、画像窓枠Ａ内の対象物の画像Ｂの外形輪郭線を
計算機を使用してプログラムモードで追跡し、検出した
輪郭線から、物体の所定位置Ｃの位置検出を行う位置検
出方法がある。

【０００８】この位置検出方法における輪郭線追跡手順
は次の通りである。

【０００９】（１）画像窓枠Ａ内を走査して、輪郭線
検出基準を満たす最初の点を画像輪郭点として検出す
る。最初に検出された画像輪郭点は、輪郭線追跡の始
点、即ち、第１参照点になる。この場合、輪郭線検出基
準はプログラム的にできている。

【００１０】（２）輪郭点追跡基準に基づいて、第１
参照点の８近傍点をアクセスして、次の画像輪郭点を検
出する。検出した前記次の画像輪郭点が輪郭線終端条件
を満たしていない場合にはこの処理を繰り返す。この場
合、輪郭点追跡基準と輪郭線終端条件とはプログラム的
にできている。

【００１１】（３）検出された画像輪郭点が前記輪郭
線終端条件を満たしている場合には、その時点で、この
アルゴリズムは終了する。

【００１２】この手順で、輪郭線検出基準、輪郭点追跡
基準、輪郭線終端条件のプログラムを種々変更すること
により、さまざまな輪郭線追跡アルゴリズムを構成で
き、複雑な形状の物体でも輪郭線追跡が可能である。

【００１３】（４）上記で得られた輪郭線について、
特徴点を検出し、検出した特徴点と、予め登録してある
対象物の形状に関する特徴点の基準データとを、プログ
ラム的な照合法で照合して位置を検出する。

【００１４】

【発明が解決しようとする課題】しかし、従来の位置検
出方法では、輪郭線を検出する輪郭線検出基準、輪郭点
追跡基準、輪郭線終端条件等の実行と、検出した輪郭線
の特徴点の位置と予め登録してある特徴点の基準データ
との照合の実行とをプログラム的に行っているために、
これを大容量の画像データに適用した場合に、処理量が
多くなり、時間がかかり過ぎて実用性が無くなるという
問題点がある。

【００１５】特に、画像を走査して輪郭線追跡の始点を
求める段階で、走査して到達した画像輪郭点を、既検
出、未検出の区別をしないで始点にしている場合には、
この始点の検出は、対象物の画像の外郭に限定され、走
査が画像の内部に及ばないので、画像の内部にある輪郭
線の検出ができないという問題点があり、又、この既検
出、未検出の区別をプログラムで行うのでは時間が掛か
り過ぎ、実用的ではないという問題点がある。

【００１６】又、輪郭線追跡開始点を輪郭線追跡終了点
として記憶して終了処理をしている場合には、対象物の
画像Ｂの輪郭線が画像窓枠Ａの４端辺に交差する場合に
は、実用可能な時間内で処理できる範囲のプログラムで
は、この交差点で終了できず、端辺では画像輪郭点を追
跡できないので、迷走してしまうという問題点があり、
閉じた外郭の輪郭線にしか適用できないという問題点が
ある。又、この問題をプログラム的に解決するのでは時
間が掛かり過ぎ、実用的ではないという問題点がある。

【００１７】本発明は上記の問題点を解決し、単純、迅
速で、汎用性があり、開いた輪郭線や画像の内部にある
輪郭線を検出し、これらの輪郭線の特徴点に基づいて位
置を検出する位置検出方法を提供することを課題として
いる。

【００１８】

【課題を解決するための手段】本発明の位置出方法は、
上記の課題を解決するために、第１ステップにおいて、
画像記憶手段に記憶した２値化画像データを線順次に走
査し、画像輪郭点に到達した位置で走査を一旦停止し、
第２ステップにおいて、前記到達した画像輪郭点を、そ
れまでの既検出画像輪郭点を記憶しているオーバレイメ
モリによって、既検出か未検出かを判断し、既検出であ
れば走査を再開し、未検出であれば前記到達した画像輪
郭点を、始点として前記オーバレイメモリに記憶させ、
第３ステップにおいて、前記始点を第１参照点として前
記２値化画像データについて輪郭線追跡を始め、第１参
照点では到着方向番号が７の、第２参照点以降では前参
照点から現参照点へ向かう方向である到着方向番号の画
像輪郭点探索方向番号表を、その参照点への到着方向番
号別に決まるその参照点での探索方向順を８つの到着方
向番号別に決めた画像輪郭点探索方向番号表から選択
し、選択した画像輪郭点探索方向番号表の探索方向順に
基づいて前記２値化画像をアクセスして次の画像輪郭点
を検出して前記オーバレイメモリに記憶させ、第４ステ
ップにおいて、前記オーバレイメモリに記憶されている
前記始点および既検出画像輪郭点のデータを、現参照点
の周囲の８近傍点についてアクセスし、このアクセス結
果で、第３ステップで検出された画像輪郭点が未検出か
既検出かを判断し、第５ステップにおいて、未検出であ
れば、前記第３〜第４ステップを繰り返し、既検出であ
れば、第３ステップで検出された画像輪郭点は輪郭線追
跡終了点であるので、現輪郭線追跡を終了して第１ステ
ップに戻り、前記始点の次の点から走査を続け、第６ス
テップにおいて、上記線順次走査が２値化画像の下端に
達したときに総ての輪郭線追跡を終了し、第７ステップ
において、これまでに検出した各輪郭線の曲率を計算し
曲率に基づく特徴点を検出し、第８ステップにおいて、
前記特徴点間の輪郭線長と角度とを各輪郭線毎に順次累
積演算して距離角度累積演算結果を記憶し、第９ステッ
プにおいて、予め登録してある対象物の形状に関する距
離角度累積演算基準データと、前記距離角度累積演算結
果とを、特徴点毎に照合しながらシフトし最適な照合位
置を検出することを特徴とする。

【００１９】

【作用】プログラム処理で物体の画像の輪郭線を追跡
し、物体の位置を検出する位置検出方法では、所要時間
を実用的に短くすれば機能不足になり、機能を満たせば
時間がかかり過ぎて実用性が無いという従来例の問題点
を解決するために、プログラムの前記輪郭線検出基準、
輪郭点追跡基準、輪郭線終端条件、位置照合条件を単純
化して、処理時間を短縮する必要がある。

【００２０】このために、本発明は、（１）輪郭点追跡基準の処理を、プログラムで逐次実
施する代わりに、プログラムの一部を画像輪郭点探索方
向番号表を使用して、単純、迅速化している。そして、
この画像輪郭点探索方向番号表は、参照点で８近傍点を
アクセスすべき順序が、その参照点への到着方向番号別
に決まることを利用したもので、どの方向に次の画像輪
郭点があっても、表を参照することによって、同一処理
で検出することができ、単純、迅速化できる。そして、
又、閉じた画像輪郭線の追跡だけではなく、後述のよう
に端点がある輪郭線の端点を検出して追跡を終了でき
る。従って、処理が単純化して所要時間が短縮するだけ
ではなく、略同じ短い時間で機能を拡大できる。

【００２１】（２）輪郭線検出基準と輪郭線終端条件
との処理を、プログラムで逐次実施する代わりに、既検
出画像輪郭点を記憶しているオーバレイメモリによっ
て、既検出か未検出かを判断している。このオーバレイ
メモリには、既検出の画像輪郭点を総て記憶させること
ができるので、処理が単純化して所要時間が短縮するだ
けではなく、未検出の画像輪郭点が無くなるまで、繰り
返し輪郭線の追跡を続け、外側輪郭線を通過して外側輪
郭線の内部にある輪郭線も追跡することができる。

【００２２】（３）又、検出した輪郭線の特徴点を曲
率計算によって検出し、検出した特徴点間の距離角度累
積演算結果を距離角度累積演算基準データと形状照合し
て位置を検出することにより、汎用性を有すると共に、
他の部分に影やノイズがあっても正確に位置を検出でき
るので、耐ノイズ性が高い位置検出を行うことができ
る。

【００２３】

【実施例】本発明の位置検出方法の第１実施例を図１〜
図１５と表１〜表３と式（１）〜式（４）とに基づいて
説明する。

【００２４】（１）第１、第２ステップで、２値化画
像の画像窓枠Ａを、上端より横方向に線順次に走査し、
到達した画像輪郭点Ｇで、オーバレイメモリによって、
この到達した画像輪郭点Ｇが未検出か否かを判断し未検
出であれば、この到達した画像輪郭点Ｇを輪郭線追跡の
始点にすると共に、この到達した画像輪郭点Ｇを既検出
画像輪郭点としてオーバレイメモリに記憶させる。

【００２５】（２）第３ステップで、前記始点Ｇを第
１参照点として前記２値化画像データについて輪郭線追
跡Ｈを始め、第１参照点Ｇにおいては、図２に示す方向
コードの７を到着方向番号とし、第２参照点以降におい
ては、前参照点から現参照点へ向かう図２に示す方向番
号の方向を到着方向番号として、８つの到着方向番号別
に決めた表１に示すような画像輪郭点探索方向番号表を
選択し、選択した画像輪郭点探索方向番号表の探索方向
順に基づいて前記２値化画像をアクセスする。

【００２６】表１に示す画像輪郭点探索方向番号表は、
到着方向番号が５のものである。

【００２７】

【表１】

【００２８】表１を説明する。方向番号１〜８は、図２
（ａ）に示す８方向番号に対応する。Ｐ₀は現参照点で
ある。方向番号１〜８の方向に次の参照点Ｐ₁〜Ｐ₈が
あり、矢印Ｊの反時計回りにアクセスする。○印は背景
点、●印は対象物の領域点を示すビットパターンであ
る。次の方向番号は求めるべき次の参照点への方向番号
を示し、アクセスして得られた方向番号１〜８のビット
パターンで表を参照し、その方向番号と●印とが一致す
る欄の下にある次の方向番号を求めることによって、次
の参照点への方向番号が得られる。×印はエラーを示
す。表１で、次の方向番号が１になった場合には、次の
参照点が前の参照点に後戻りしていることになり、現参
照点は、端点がある輪郭線のその端点であることを示
す。即ち、表１で、端点がある輪郭線の端点を検出でき
ることになる。

【００２９】以下に述べる理由によって、一般的に、到
着方向番号がｉであれば、図２（ｂ）に示すｉ−３の方
向は必ず背景点になる。ｉ−３の方向が領域点の場合に
はエラーとして扱う。従って、表１では、５−３＝２の
方向は必ず背景点になるので、表１に示す到着方向番号
が５の場合には、図２に示す８方向番号１〜８の中の方
向番号２の方向から反時計回りに、現参照点の８近傍点
をアクセスし、最初に領域点を得た方向が、次の参照点
の方向である。

【００３０】ｉ−３の方向は必ず背景点になる説明は以
下の通りである。

【００３１】対象物の画像Ｂの輪郭形状は、図３（ａ）
の閉じた画像Ｂ₁か、図３（ｂ）の開いた画像Ｂ₂の何
れかである。

【００３２】閉じた図形Ｂ₁の参照点をＳ₁、開いた画
像Ｂ₂の参照点をＳ₂とすると、それぞれ図４（ａ）、
図４（ｂ）に示すようになる。

【００３３】図５、図６は、前参照点から現参照点への
方向番号が、５〜８の場合の背景点○と領域点●の位置
関係を示した図である。この場合、図５は閉じた図形Ｂ
₁の場合を、図６は開いた図形Ｂ₂の場合を示す。何れ
の場合も、ｉ−３の方向は背景点になっており、ｉ−３
の方向から反時計回りに探索を開始すれば、次の参照点
を検出できる。

【００３４】図７は、輪郭線上での検出を示した図で、
図７（ａ）では、前参照点Ｐ₁₀より例えば方向番号６の
方向に現参照点Ｐ₀が検出された場合、現参照点Ｐ₀か
ら見て６−３＝３の方向は必ず背景点となり且つこれよ
り時計回り方向には次の参照点は存在しない。従って、
方向番号３から反時計回りに探索すれば次の参照点が検
出できる。同様に、図７（ｂ）では、前参照点Ｐ₁₀より
例えば方向番号５の方向に現参照点Ｐ₀が検出された場
合、現参照点Ｐ₀から見て５−３＝２の方向は必ず背景
点となり且つこれより時計回り方向には次の参照点は存
在しない。従って、方向番号２から反時計回りに探索す
れば次の参照点が検出できる。

【００３５】１〜８の各方向番号について、図４〜図７
を試みれば、何れも同様の結果が得られる。以上より帰
納して作成した、ｉ−３の方向から反時計回りに探索を
開始するための画像輪郭点探索方向番号表が表１であ
る。

【００３６】又、走査して到着した始点からの探索の場
合には、到着方向番号を７とすれば良いことが容易に判
る。

【００３７】上記のようにして、表１の画像輪郭点探索
方向番号表でアクセスして次の画像輪郭点を検出し、こ
の検出した画像輪郭点を前記オーバレイメモリに記憶さ
せる。

【００３８】（３）第４ステップにおいて、前記オー
バレイメモリに記憶されている前記始点および既検出画
像輪郭点のデータを、現参照点の周囲の８近傍点につい
てアクセスし、前記の今回検出した画像輪郭点と重なる
前記始点および既検出画像輪郭点の有無を判断する。こ
の結果で、第３ステップで検出された画像輪郭点が未検
出か既検出かを判断できる。

【００３９】（４）第５ステップにおいて、未検出で
あれば、前記第３〜第４ステップを繰り返し、既検出で
あれば、第３ステップで検出された画像輪郭点は輪郭線
追跡終了点であるので、現輪郭線追跡を終了して第１ス
テップに戻り、前記始点の次の点から走査を続ける。

【００４０】（５）次の走査では、既検出の画像輪郭
点を検出しても、前記オーバレイメモリの判断で、これ
を始点にしないで通過し、未検出の画像輪郭点を検出し
てこれを始点として画像輪郭線の探索を行い、未検出の
画像輪郭点の検出がなくなるまで繰り返される。従っ
て、図１についていえば、先ず、輪郭線追跡Ｈによっ
て、対象物の画像Ｂの外側画像輪郭線Ｉを検出した後、
対象物の画像Ｂの内部の輪郭線Ｄ、Ｅ、Ｆが検出され、
所定位置Ｃの位置が認識される。この場合、対象物の画
像Ｂの外側画像輪郭線Ｉの走査と、対象物の画像Ｂの内
部の輪郭線Ｄ、Ｅ、Ｆの走査とでは、画像輪郭点の検出
位置での画像データの「０」→「１」、「１」→「０」
の変化が逆になる。

【００４１】（６）尚、画像記憶手段に記憶した２値
化画像データの画像窓枠の４端辺上の点を既検出の画像
輪郭点として扱うようにすれば、図４（ｂ）の開いた画
像の画像輪郭線を探索できる。これを簡単に行うには、
画像記憶手段に記憶した２値化画像データの画像窓枠の
４端辺上の点を既検出の画像輪郭点としてオーバレイメ
モリに記憶させれば良い。

【００４２】上記の本発明の位置検出方法を実施する第
１実施例を図８、図９に基づいて説明する。

【００４３】本実施例は、輪郭線追跡の一部をプログラ
ム制御ではなくランダムロジックによるハードウェアで
行って迅速化するもので、図８において、画像記憶部１
０２は画像メモリと、これに座標を重ね合わせたオーバ
レイメモリとで構成されており、このオーバレイメモリ
には始点と検出された画像輪郭点が順次書き込まれる。
制御部１０７は、画像記憶部１０２の画像メモリが記憶
している２値化画像に対して、ＤＭＡ（ダイレクトメモ
リアクセス）部１０３を用いて走査を行いながら、画像
記憶部１０２のオーバレイメモリを使用して、既検出点
チェックを実施して、画像輪郭点を検出する。制御部１
０７は上記の走査によって到達し検出した画像輪郭点を
画像輪郭線追跡の始点とし、始点アドレスと、到着方向
番号によって選択した画像輪郭点探索方向番号表に基づ
く探索方向順の開始方向数とをアドレス算出部１０５と
輪郭点探索部１０４とに送り、画像輪郭線追跡を開始さ
せる。ＤＭＡ部１０３より追跡終了情報が出されて画像
輪郭線追跡が終了すると、引き続いて走査を行う。そし
て、未検出の画像輪郭点が検出されると、上記の動作を
繰り返し、これを、画像データが終了するまで、即ち、
上記の線順次走査が２値化画像の下端に達するまで実行
する。

【００４４】ＤＭＡ部１０３は、始点または参照点の８
近傍点を画像記憶部１０２の画像メモリよりアクセスす
る。この場合、１度のアドレス指定アクセスで、画像メ
モリとオーバレイメモリとの両方のアクセスが可であ
る。画像メモリからアクセスしたデータを輪郭点探索部
１０４に送り、オーバレイメモリからアクセスしたオー
バレイデータを一旦記憶する。輪郭点探索部１０４は、
下記のようにして画像輪郭点を検出し、ＤＭＡ部１０３
は、輪郭点探索部１０４が検出した画像輪郭点を、オー
バレイメモリに記憶された始点および既検出画像輪郭点
と比較し、追跡終了情報を検出する。追跡終了情報を検
出した場合には、これを制御部１０７におくる。

【００４５】輪郭点探索部１０４は、ＤＭＡ部１０３か
らの８近傍点のデータを前記の画像輪郭点探索方向番号
表に基づく探索方向順の開始方向数に基づいて画像輪郭
点を検出する。輪郭点探索方向番号表はＲＯＭで構成さ
れ、入力データは、到着方向番号の３ビットと８近傍点
のデータの８ビットとの合計１１ビットがアドレスとし
て与えられ、これによって、次の方向番号のデータの３
ビットとエラー情報１ビットの合計４ビットが読み出さ
れる。エラー情報は、８近傍点が総て「１」又は総て
「０」のとき、及び方向番号ｉ−３が「対象物の領域
点」のとき「１」が出力し、エラーを示すようにする。
読み出された次の方向番号はアドレス算出部１０５へ、
エラー情報は制御部１０７へ送られる。

【００４６】アドレス算出部１０５は、輪郭点探索部１
０４で得られた次の方向番号に従ってアドレスをＸ、Ｙ
方向に夫々増減させて、次の参照点のアドレスを作り、
このアドレスをＤＭＡ部１０３へ送り、また検出されて
いる次の方向番号と共に、輪郭データ記憶部１０６に送
り、輪郭データ記憶部１０６はこれを記憶する。

【００４７】図９は、図８のＤＭＡ部１０３、輪郭点探
索部１０４及びアドレス算出部１０５の詳細の一例を示
すブロック図である。

【００４８】図８、図９において、ＤＭＡ部１０３の線
順次メモリアクセス回路１００８へ制御部１０７より線
順次走査始点アドレスが送られ、線順次メモリアクセス
回路１００８は前記始点アドレスより線順次走査を開始
する。

【００４９】線順次走査と同時に、画像記憶部１０２よ
り同一座標点の画像メモリデータとオーバレイデータと
を、線順次メモリアクセス回路１００８が読み込む。こ
の読み込んだ同一座標点の画像メモリデータとオーバレ
イデータとを、比較回路１００９で比較する。このと
き、画像メモリデータが「０」→「１」に変化する座標
で、オーバレイデータが「０」の場合には、その座標
は、輪郭線追跡始点であり、前記以外の場合は輪郭線追
跡始点ではない。

【００５０】輪郭線追跡始点が検出されると、始点情報
が制御部１０７へ送られる。制御部１０７は始点情報を
受け取ると、線順次メモリアクセス中止指令を線順次メ
モリアクセス回路１００８へ送り、始点の次のアドレス
を線順次走査始点アドレスとして記憶する。

【００５１】続いて、制御部１０７より、線順次走査始
点アドレスがバッファ１００７へ、開始方向数がバッフ
ァ１００４へ送られる。バッファ１００７が記憶する線
順次走査始点アドレスに従いメモリアクセス回路１００
１は８近傍点データとオーバレイデータとをアクセス
し、探索表１００３および比較回路１００２に送る。比
較回路１００２へ送られたオーバレイデータは一旦記憶
される。前記の表１の説明のようにして探索表１００３
より次の方向番号が得られ、この方向番号はバッファ１
００４と演算テーブル１００５と輪郭データ記憶部１０
６とに送られる。

【００５２】比較回路１００２はバッファ１００４が記
憶する方向番号を、先に記憶したオーバレイデータと比
較して追跡終了情報を得る。演算テーブル１００５に
は、各方向番号に対応するＸ、Ｙ方向の増減値ΔＸ、Δ
Ｙが書き込まれており、これが演算回路１００６に送ら
れて、次の参照点アドレスが算出される。参照点アドレ
スは輪郭データ記憶部１０６とバッファ１００７へ送ら
れる。

【００５３】特徴点検出部１０８は、検出した輪郭線を
細分して曲率計算し、その結果から特徴点位置を検出し
て記憶する。詳しく説明すると、特徴点検出部１０８
は、図１０に示すように、曲率値算出部１１１と、曲率
値比較部１１２と、特徴点記憶部１１３とで構成され
る。輪郭データ記憶部１０６に記憶されている輪郭デー
タの実形状の一例を図１１に示し、以下にこれを参照し
て説明する。

【００５４】図１１において、各輪郭点の番号は追跡番
号を示している。曲率値算出部１１１では、各輪郭点ｉ
毎に、検出された方向 code i に基づいて、例えば、次
の（１）式に示す曲率計算式に従って、曲率値を算出す
る。

【００５５】

【数１】

【００５６】但し、加減算は modulo 8 で実施曲率値比
較部１１２では、曲率値算出部１１１で算出された曲率
値を輪郭点毎に、その曲率値の絶対値と、設定した閾値
とを比較して特徴点の判定を行う。例えば、〔１〕｜曲率計算値｜≦閾値１のときは直線〔２〕閾値１＜｜曲率計算値｜＜閾値２のときはカーブ〔３〕閾値２≦｜曲率計算値｜のときはコーナと判定する。図１３の輪郭線における方向 code i と曲
率値と特徴点の判定結果を表２に示す。尚、この例で
は、ｎ＝２で演算している。

【００５７】

【表２】

【００５８】そして、直線は特徴点とせず、カーブは連
続点となるがその最初の点をカーブ特徴点とし、コーナ
は１点又は連続点となるが、連続点の場合、最大値があ
る場合はその最大値の点を、最大値が無い場合は最初の
点をコーナ特徴点と判定する。こうして得られた特徴点
情報（ｘ、ｙ座標と特徴情報）を特徴点記憶部１１３に
記憶する。図１１の結果を表３に示す。

【００５９】

【表３】

【００６０】このようにして、曲率計算を使用して輪郭
線の特徴点を求めることにより、輪郭線を特定するため
のデータ量を大幅に圧縮することができ、高速処理が可
能になる。

【００６１】距離角度累積演算部１０９は、特徴点検出
部１０８の特徴点記憶部１１３に記憶した特徴点位置間
の輪郭長と画像横方向に対する角度とを輪郭線毎に、順
次累積演算し、その結果を記憶する。即ち、特徴点記憶
部１１３に記憶した特徴点データについて、次の式
（２）、（３）を使用して、距離角度累積演算を行う。

【００６２】

【数２】

【００６３】

【数３】

【００６４】但し、追跡点番号１では、Ｓ＝０、Φ＝０
とする。

【００６５】以上の演算による距離角度累積演算結果を
図１２に示す。この距離角度演算結果を使用すると、輪
郭線に多少の凹凸や変形部分があっても、図１２のライ
ンに微小かつ局部的な振れが現れるだけであり、全体と
して、形状が同一であれば、同一のラインパターンとな
るので、耐ノイズ性が高い輪郭線形状の検出ができる。

【００６６】形状照合部１１０は、距離角度累積演算部
１０９に記憶した演算結果に対し、予め登録してあるテ
ンプレートの距離角度累積演算基準データを、特徴点毎
にシフトしながら照合し、最適な照合位置を検出する。
図１３（ａ）にテンプレートの実形状を示し、図１３
（ｂ）にその距離角度累積演算基準データを示す。そし
て、次の式（４）に示す、一致度Ｄを最小にする点を、
形状照合点とし、検出結果とする。

【００６７】

【数４】

【００６８】但し、Φは対象物、Φt はテンプレート次に、本発明方法を使用する第２実施例を図１４、図１
５に基づいて説明する。

【００６９】図１４は、第２実施例の構成を示すブロッ
ク図で、画像入力部１１０１と、画像記憶部１１０２
と、ＣＰＵ１１０３と、一時記憶部１１０４とからな
る。このＣＰＵ１１０３の動作を、図１５のフローチャ
ートで説明する。

【００７０】ステップ＃１において、記憶した画像を線
順次に走査して、境界点座標データを検出する。

【００７１】ステップ＃２において、検出された境界点
座標データより未検出の境界点を始点として検出する。
始点であれば、ステップ＃３に進み、始点でなければ、
ステップ＃１に戻る。

【００７２】ステップ＃３において、得られた始点より
輪郭線探索を開始し、その始点の次の走査点を次の始点
として記憶する。

【００７３】ステップ＃４において、探索テーブルに従
い、次の輪郭点を検出する。

【００７４】ステップ＃５において、オーバレイデータ
に基づいて、上記の検出された輪郭線が、探索終了条件
を満たすか否かを判定する。探索終了条件でない場合
は、ステップ＃４に戻り、探索終了条件であれば、ステ
ップ＃６に進む。

【００７５】ステップ＃６において、引き続いて画像輪
郭線の終端まで走査し、他の始点があるか否かを判定す
る。他の始点があれば、ステップ＃３に戻り、他の始点
がなければ、走査を終了し、ステップ＃７に進む。

【００７６】ステップ＃７において、検出した画像輪郭
線の曲率計算を行い、その結果に基づいて特徴点を検出
する。

【００７７】ステップ＃８において、検出した特徴点間
の輪郭長と角度とを、輪郭線毎に順次累積演算した結果
を距離角度累積演算結果として記憶する。

【００７８】ステップ＃９において、登録したテンプレ
ートの距離角度累積演算基準データを、特徴点毎にシフ
トしながら、前記の距離角度累積演算結果と照合し、最
適な照合位置を検出し終了する。

【００７９】

【発明の効果】本発明の位置検出方法は、輪郭線追跡の
始点の走査検出と輪郭線追跡の終了点の検出とを、プロ
グラムで順次処理する代わりに、既使用の始点や既検出
の画像輪郭点を画像データに座標を重ね合わせて記憶さ
せたオーバレイメモリを利用して処理を単純化し、単純
化するにもかかわらず、従来技術ではできなかった、開
いた画像の輪郭線の追跡と、画像の内側にある閉じた輪
郭線の検出をすることができるという効果を奏する。

【００８０】又、検出した輪郭線の特徴点を曲率計算に
よって検出し、これらの特徴点間の距離角度累積演算結
果を用いて形状照合して物体の位置を検出することによ
り、汎用性を有し、他の部分に影やノイズがあっても、
正確に位置検出ができるという、耐ノイズ性が高い位置
検出が可能になるという効果を奏する。

【図面の簡単な説明】

【図１】本発明の動作を示す図である。

【図２】本発明の探索方向順を示す図である。

【図３】閉じた画像と開いた画像とを示す図である。

【図４】閉じた画像と開いた画像の参照点を示す図であ
る。

【図５】閉じた画像の前参照点と現参照点と背景点とを
示す図である。

【図６】開いた画像の前参照点と現参照点と背景点とを
示す図である。

【図７】本発明の前参照点と現参照点と探索方向とを示
す図である。

【図８】本発明を使用する位置検出装置の第１実施例の
構成を示すブロック図である。

【図９】図８の一部詳細図である。

【図１０】第１実施例の特徴点検出部の詳細ブロック図
である。

【図１１】第１実施例の輪郭データ記憶部に記憶された
輪郭線の平面図である。

【図１２】第１実施例における距離角度累積演算結果の
平面図である。

【図１３】第１実施例において位置照合に用いるテンプ
レートとその距離角度累積演算基準データの平面図であ
る。

【図１４】本発明を使用する位置検出装置の第２実施例
の構成を示すブロック図である。

【図１５】第２実施例の動作を示すフローチャートであ
る。

【図１６】従来例の動作を示す図である。

【符号の説明】

Ａ画像窓枠Ｂ対象物の画像Ｃ所定位置Ｄ、Ｅ、Ｆ内部の輪郭線Ｇ画像輪郭点（始点）Ｈ輪郭線追跡Ｉ外側画像輪郭線１０１画像入力部１０２画像記憶部１０３ＤＭＡ部１０４輪郭点探索部１０５アドレス算出部１０６輪郭データ記憶部１０７制御部１０８特徴点検出部１０９距離角度累積演算部１１０形状照合部１１１曲率値算出部１１２曲率値比較部１１３特徴点記憶部１１０１画像入力部１１０２画像記憶部１１０３ＣＰＵ１１０４一時記憶部

フロントページの続き (51)Int.Cl.⁶ 識別記号庁内整理番号ＦＩ技術表示箇所Ｇ０６Ｔ 7/00 9/20 7459−5ＬＧ０６Ｆ 15/70 ３３５Ｚ

Claims

【特許請求の範囲】

【請求項１】第１ステップにおいて、画像記憶手段に
記憶した２値化画像データを線順次に走査し、画像輪郭
点に到達した位置で走査を一旦停止し、第２ステップに
おいて、前記到達した画像輪郭点を、それまでの既検出
画像輪郭点を記憶しているオーバレイメモリによって、
既検出か未検出かを判断し、既検出であれば走査を再開
し、未検出であれば前記到達した画像輪郭点を、始点と
して前記オーバレイメモリに記憶させ、第３ステップに
おいて、前記始点を第１参照点として前記２値化画像デ
ータについて輪郭線追跡を始め、第１参照点では到着方
向番号が７の、第２参照点以降では前参照点から現参照
点へ向かう方向である到着方向番号の画像輪郭点探索方
向番号表を、その参照点への到着方向番号別に決まるそ
の参照点での探索方向順を８つの到着方向番号別に決め
た画像輪郭点探索方向番号表から選択し、選択した画像
輪郭点探索方向番号表の探索方向順に基づいて前記２値
化画像をアクセスして次の画像輪郭点を検出して前記オ
ーバレイメモリに記憶させ、第４ステップにおいて、前
記オーバレイメモリに記憶されている前記始点および既
検出画像輪郭点のデータを、現参照点の周囲の８近傍点
についてアクセスし、このアクセス結果で、第３ステッ
プで検出された画像輪郭点が未検出か既検出かを判断
し、第５ステップにおいて、未検出であれば、前記第３
〜第４ステップを繰り返し、既検出であれば、第３ステ
ップで検出された画像輪郭点は輪郭線追跡終了点である
ので、現輪郭線追跡を終了して第１ステップに戻り、前
記始点の次の点から走査を続け、第６ステップにおい
て、上記線順次走査が２値化画像の下端に達したときに
総ての輪郭線追跡を終了し、第７ステップにおいて、こ
れまでに検出した各輪郭線の曲率を計算し曲率に基づく
特徴点を検出し、第８ステップにおいて、前記特徴点間
の輪郭線長と角度とを各輪郭線毎に順次累積演算して距
離角度累積演算結果を記憶し、第９ステップにおいて、
予め登録してある対象物の形状に関する距離角度累積演
算基準データと、前記距離角度累積演算結果とを、特徴
点毎に照合しながらシフトし最適な照合位置を検出する
ことを特徴とする位置検出方法。