JPH09223229A - パターンマッチング方法 - Google Patents

Abstract

(57)【要約】 【課題】伸縮する信号パターンに対し高速にマッチング
処理を行い、探索しているパターンのより正確な位置抽
出を可能とするパターンマッチング方法および装置を提
供する。 【解決手段】パターンマッチング装置は、参照信号の波
形の特徴を表現している特徴点を抽出する特徴抽出部１
００と、その参照信号における特徴点と入力信号とのマ
ッチングをＤＰ法によって行う一次元パターンマッチン
グ部３５０から構成される。また、ＤＰ法によってマッ
チングをとった際の最適パスの結果を記憶する手段と記
憶された最適パスを調べることによって高精度な位置抽
出を行う手段４００とを備えている。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、参照信号が入力信
号中のどの位置に存在するかを調べる探索処理に係り、
特に、画像を用いたパターンマッチング方法および装置
に関する。

【０００２】

【従来の技術】パターンマッチングの方法として、音声
のように個々のパターンに時間的な伸縮が存在する場合
に、参照するパターンの時間軸もしくはサンプリング間
隔を動的に変化させながら最適なマッチングをとる動的
計画法（以後、ＤＰ法と記述する）に基づく方法があっ
た（中川聖一：確率モデルによる音声認識；電子情報通
信学会）。このＤＰ法における計算時間の短縮を目的と
して、最適パスの探索範囲を限定するために最適パスと
なる可能性が低いパスの探索を中断するビームサーチに
よる探索を行い高速化する方法（迫江博昭 ほか：“フ
レーム同期化，ビームサーチ，ベクトル量子化の統合に
よるＤＰマッチングの高速化”，信学論(Ｄ)，Ｊ７１−
Ｄ，９，pp.６７８−６８４）や単純にデータを間引き
して高速化を図る方法(山田飽博三 ほか：“ＤＰ整合
法による超音波心臓動画像の認識"，信学論 (Ｄ)，Ｊ
７１−Ｄ，４，pp.６７８−６８４）があった。

【０００３】

【発明が解決しようとする課題】従来技術のＤＰ法に基
づく方法では、パターンの伸縮に対処することが可能で
あるが、マッチングにかかる計算量が大きいことが問題
となっていた。計算量に関して、ビームサーチによる方
法では個々のパターンに適したパラメータの設定が必要
であり、データの単純間引きによる方法ではデータの間
引き過程で細かいパターンにおけるパターンの特徴を消
失する危険性があり共に汎用性に問題があった。

【０００４】また、従来、ＤＰ法が伸縮するパターンを
前提としたマッチング方法であるため、ＤＰ法は認識等
には頻繁に使用されていたが、高精度の位置決め手法と
しては用いられていなかった。

【０００５】本発明の目的は、伸縮する信号パターンに
対し高速にマッチング処理を行い、探索しているパター
ンのより正確な位置抽出を可能とするパターンマッチン
グ方法および装置を提供することにある。

【０００６】

【課題を解決するための手段】本発明のパターンマッチ
ング方法および装置は、参照信号の波形の特徴を表現し
ている特徴点を抽出する特徴抽出部と、その参照信号に
おける特徴点と入力信号とのマッチングをＤＰ法によっ
て行う一次元パターンマッチング部から構成されてい
る。

【０００７】本発明のパターンマッチング方法および装
置は、ＤＰ法によってマッチングをとった際の最適パス
の結果を記憶する手段と記憶された最適パスを調べるこ
とによって高精度な位置抽出を行う手段とを備えてい
る。

【０００８】本発明によれば、参照信号を特徴点に限定
して入力信号とのマッチングをとることにより、マッチ
ングに使用する信号データ数が減少し、処理を高速化す
ることが可能となる。

【０００９】また、ＤＰ法によって行われたマッチング
処理の結果を調べる機能により、高精度な位置抽出を行
うことが可能となる。

【００１０】

【発明の実施の形態】本発明は信号処理に関するもので
あるが、本実施例では、参照画像に見られるパターンが
入力画像中のどこに存在するかを高精度に抽出する手法
と装置を一実施例として説明する。

【００１１】以下、本発明の一実施例を図面を用いて説
明する。図１は本発明の一実施例を示すパターンマッチ
ング装置のブロック図である。本実施例では、参照画像
取得部１０によって取得された画像を参照信号生成部５
０で一次元信号に変換し、変換された参照信号における
特徴点を特徴抽出部１００によって設定し、得られた一
次元信号と特徴点は参照信号としてパターンマッチング
に使用される。参照画像取得部１０で取得される参照画
像は、探索するパターンの特徴が良く表現されている箇
所を人が示唆して得られる。

【００１２】また、入力画像取得部１５０で取得された
画像を入力画像分割部２００で必要に応じて分割し、分
割された入力画像を入力信号生成部２５０で一次元信号
に変換し、得られた一次元信号を入力信号としてパター
ンマッチングに使用する。一次元パターンマッチング部
３５０で入力信号のどの位置に参照信号が存在するかを
探索し、パターン位置抽出部４００でマッチングの結果
から詳細なパターン位置抽出を行う。入力画像が入力画
像分割部２００によって分割されている場合は、複数の
マッチング結果をマッチング結果統合部４５０で総合的
に評価し、位置決めを行う。位置決めされた結果は表示
部５００でモニタに表示される。

【００１３】なお、実施例では参照信号が特徴抽出部１
００から一次元パターンマッチング部３５０に直接入力
されているが、途中にデータベースを介して参照信号を
複数保持しておき入力信号の変化に合わせて予め登録さ
れた参照信号を適用できるようにしてもよい。また、入
力画像は入力画像分割部２００で分割されているが、パ
ターンが明確である場合は参照画像と入力画像のサイズ
を調節することによって分割する必要がない。この場
合、マッチング結果統合部４５０も必要がない。図１の
参照信号生成部５０では、画像データを一次元の信号に
変換している。その変換方法を図２を用いて以下に説明
する。本実施例では、取得する段階で設定されているＸ
方向サイズ５６，Ｙ方向サイズ５７の参照画像５５に対
し、濃度投影をとることによって画像を一次元信号に変
換している。Ｘ，Ｙ軸にそれぞれ投影された結果、参照
画像５５はデータ数５６のＸ投影分布６０とデータ数５
７のＹ投影分布６５の二つの一次元信号に変換され、
Ｘ，Ｙ方向のマッチングの参照信号として使用される。
さらに、照明条件の変化と行った平均値が変化するよう
な環境変化に柔軟に対処するため、投影分布はその平均
値が０となるように変換される。

【００１４】本実施例では、参照信号生成部５０で得ら
れた参照信号に対し、マッチング処理の高速化を図るた
めに参照信号の特徴点のみを処理に使用するが、その特
徴点の抽出方法を図３および図４を用いて説明する。図
３で、参照信号は、安定した特徴点の抽出のために雑音
を除去することを目的として、平滑化手段１１０によっ
て平滑される。極値選定手段１２０では、平滑化された
参照信号に対し、極値となる点を第一の特徴点として定
義する（図４にみられる特徴点１４０）。次に、第一の
特徴点のみでは、信号の波形を十分に表現することがで
きないと考え、特徴点補間手段１３０で、第一の特徴点
間のサンプリング間隔１４５が一定値より大きくなった
場合は第二の特徴点として特徴点間を補間する特徴点を
定義した（図４にみられる特徴点１４１）。この第二の
特徴点は、すべての特徴点間隔がある値以下になるまで
抽出を続ける。

【００１５】次に、マッチングに使用する入力信号の取
得方法について図５を用いて説明する。入力画像取得部
１５０で予め設定された大きさの入力画像を取得する。
必要に応じて入力画像をＹ軸方向分割部２１０とＸ軸方
向分割部２２０において分割し、分割された入力信号に
対し入力信号生成部２５０で一次元信号に参照信号と同
様に変換する。ここで本実施例の特徴として、微弱なパ
ターンに対する安定した認識を行うために入力画像を多
分割する方法を適用した点が挙げられる。図６を用いて
Ｙ軸方向に入力画像を多分割する方法を説明する。図６
で、入力画像２０１を予め設定した間隔２１１で複数の
画像２０２，２０３，２０４に分割する。この時、分割
された画像の幅２１２は、図２における参照画像のＹ方
向の大きさ５７に等しい。入力画像の分割はＸ軸方向に
対しても必要に応じて行われる。分割された入力画像か
ら一次元の入力信号を生成する方法は参照信号と同様の
方法で行う。その概略図を図７に示し、図７のＸ投影分
布２６０は入力信号としてパターンマッチングに使用さ
れる。

【００１６】図８，図９，図１０を用いて本実施例で行
ったＤＰ法によるパターンマッチングの方法を説明す
る。図８において、参照信号６０と入力信号２６０との
マッチングは、マッチングを調べる範囲３６５を設定
し、範囲３６５をずらしながら行われる。本実施例では
環境の変化に柔軟に対処することを目的として、参照信
号６０は平均値が０になるように変換されているため、
それに合わせて範囲３６５で入力信号３６６も平均が０
になるように変換される。この処理によって、より波形
の形状に依存したマッチングをとることができる。範囲
３６５の幅３６０は、信号の伸縮を仮定して、参照信号
の信号長よりも大きく設定される。入力信号３６６と参
照信号６０とのマッチングは、図９に見られるように参
照信号６０における特徴点１４０を整合窓３６７の範囲
で入力信号３６６における最適な対応点を探索する。こ
の探索方法は一般にＤＰ法と呼ばれ、本実施例で用いら
れるＤＰ法を以下に説明する。図１０で、入力パターン
のデータをＩ＝(ａ₀，…，ａ_m，…，ａ_M)，テンプレー
トパターンのデータをＴ＝(ｂ₀，…，ｂ_n，…，ｂ_N)と
し、対応点３７１におけるマッチングの評価値ｄ(ｍ,
ｎ）を

【００１７】

【数１】 ｄ(ｍ,ｎ)＝｜ａ_m−ｂ_n｜ …（数１） と定義する。参照信号中の特徴点がそれぞれ一つの対応
点を持つものとして、それらの対応点を通るパスを考え
たときに、パスの評価値の総和が最小になるパスを最適
パスとする。本実施例のＤＰ法では、最適パスは帰納法
によって以下の漸化式から求められる。対応点３７１ま
での対応点を結ぶ最適パスの評価値の総和を距離値Ｇ
(ｍ,ｎ）とすると、第ｎフレーム目の直前の特徴フレー
ムをｎ′とし、ｎ−ｒ−１＜ｍ＜ｎ＋ｒの範囲で、

【００１８】

【数２】

【００１９】この最適パスの探索において、参照信号と
入力信号とはともに順番通りに対応していることが条件
であり、データが前後に入れ替わる様なパスの存在は認
めない。

【００２０】パターン位置抽出部４００で行われる位置
抽出の方法を図１１を用い説明する。中心線３７５は、
信号に伸縮がなかった場合の最適パスを表わしていて、
その場合は、最もマッチングのとれた位置がパターンの
詳細な位置となる。しかし、伸縮があった場合は、中心
線から最適パスがずれるため、最もマッチングがとれた
位置から少しずれた位置がパターンの詳細な位置とな
る。この詳細な位置決めは中心線３７５と対応点３７６
のずれ３７７を最適パス３８０上の全ての対応点で調べ
ることにより行われる。本実施例では、すべてのずれの
平均をとって詳細な位置を求めている。

【００２１】入力画像が分割された場合のパターン位置
の抽出方法を図１２，図１３，図１４を用いて説明す
る。図１２で、入力画像２０１は、複数の画像２０２，
203,２０４に分割されている。ここで、入力画像２０１
の地点４０５におけるマッチングの結果は、分割された
画像２０２では、地点４０６におけるマッチングの結果
に対応する。地点４０６におけるマッチングの結果は、
地点４０６を中心とした範囲４０７でのマッチング処理
で得られた結果である。ここでの範囲４０７は図８の範
囲３６５に対応する。マッチングの結果は、マッチング
結果４１０に結果４１１として保存される。マッチング
の結果は、パターン位置抽出部４００で抽出されたパタ
ーンの位置とＤＰ法によって求められた最適パスの距離
値を保持している。図１３で、パターン位置抽出部４０
０で得られた結果を結果累積手段４６０で結果を統合す
る。本実施例では、図１４に見られるように、結果４１
０，４２０，４３０における同一地点の結果を単純加算
して結果４６２とし、それらの結果から最終結果４６１
を構成する。最終位置抽出手段４７０では最適パスの距
離値の総和が最も小さい箇所でマッチングしているとみ
なし、その箇所での位置の平均値をとって詳細位置とし
た。ここで、位置決めされた結果は、表示部５００によ
って何らかの出力手段を通して出力される。

【００２２】実施例では、Ｘ方向のマッチング処理しか
説明していないが、Ｙ方向のマッチング処理も同様に行
われる。

【００２３】また、本実施例で入力画像を複数に分割す
ることにより、小さい参照画像と大きい入力画像とを使
用してパターンマッチングを行うことができる。ここで
は、小さい参照画像を用いることによって、濃度投影を
とる距離が小さくなり、参照画像のパターンが忠実に参
照信号に反映され易くなる。また、大きな入力画像を用
いることによって、微弱なパターンに対しても、より多
くの地点でマッチングを調べることによって、より安定
なパターン位置の抽出が可能となった。

【００２４】なお、実施例では、多分割した入力画像の
結果を統合して位置決め処理を行っているが、結果４１
０，４２０，４３０のすべての結果のうち最もマッチン
グ結果が良かった地点の位置だけを抽出してもよい。

【００２５】

【発明の効果】本発明のパターンマッチング方法は、Ｄ
Ｐ法によるマッチング処理の際に、参照信号における特
徴点のみを処理に使用するため、データ数の減少によっ
て処理の高速化が行える。このとき、データ数を減少さ
せる段階で信号の特徴点を使用しているため、微弱なパ
ターンや細かいパターンに対しても全てのデータを用い
たときと同等以上のマッチング結果が得られる。

【００２６】また、ＤＰ法による最適パスの探層結果を
調べることにより、パターンに伸縮がある場合でも高精
度にパターン位置を提出することが可能である。

【図面の簡単な説明】

【図１】本発明の一実施例を示すパターンマッチング装
置のブロック図。

【図２】参照画像から一次元信号を生成する方法の説明
図。

【図３】本発明の一実施例における特徴抽出部を示すブ
ロック図。

【図４】参照信号における特徴点設定の説明図。

【図５】本発明の一実施例における入力画像分割部を示
すブロック図。

【図６】入力画像を分割する方法の説明図。

【図７】入力画像から一次元信号を生成する方法の説明
図。

【図８】ＤＰ法によるマッチング処理を行う際の入力信
号と参照信号の関係の説明図。

【図９】特徴点を用いたＤＰ法によるマッチング処理の
説明図。

【図１０】特徴点を用いたＤＰ法の最適パス探索方法の
説明図。

【図１１】ＤＰ法によるパターンの位置抽出方法の説明
図。

【図１２】多分割された入力画像に対するマッチング処
理の適用方法の説明図。

【図１３】本発明の一実施例におけるマッチング結果統
合部のブロック図。

【図１４】マッチング結果を統合する方法の説明図。

【符号の説明】

１０…参照画像取得部、５０…参照信号生成部、１００
…特徴抽出部、１５０…入力画像取得部、２００…入力
画像分割部、２５０…入力信号生成部、３５０…一次元
パターンマッチング部、４００…パターン位置抽出部、
４５０…マッチング結果統合部、５００…表示部。

Claims (3)

【特許請求の範囲】
1. 【請求項１】入力信号生成部によって生成された入力信
   号と生成部によって生成された参照信号とのマッチング
   を調べるパターンマッチング方法において、前記参照信
   号の特徴を抽出し、抽出された特徴を代表する特徴点を
   設定し、前記特徴点のみをマッチング処理に使用するこ
   とを特徴とするパターンマッチング方法。
2. 【請求項２】入力信号生成部によって生成された入力信
   号と生成部によって生成された参照信号とのマッチング
   を調べるパターンマッチング方法において、前記入力信
   号もしくは前記参照信号のサンプリング間隔を伸縮させ
   て二つの信号のマッチングをとり、その結果から詳細な
   パターンの位置抽出を行うことを特徴とするパターンマ
   ッチング方法。
3. 【請求項３】入力画像を複数に分割することにより入力
   信号を複数生成し、複数の入力信号に対し参照信号との
   マッチングをとり、得られた複数の結果を統合してパタ
   ーンの位置抽出を行うことを特徴とするパターンマッチ
   ング方法。