Top > Search of Japanese Patents > IMAGE PATTERN MATCHING DEVICE, AND METHOD AND PROGRAM OF THE SAME

IMAGE PATTERN MATCHING DEVICE, AND METHOD AND PROGRAM OF THE SAME commons meetings

Patent code P10P007366
Posted date Aug 6, 2010
Application number P2009-005682
Publication number P2010-165104A
Patent number P5247481
Date of filing Jan 14, 2009
Date of publication of application Jul 29, 2010
Date of registration Apr 19, 2013
Inventor
  • (In Japanese)岡 嶐一
  • (In Japanese)矢口 勇一
  • (In Japanese)井関 健太
Applicant
  • (In Japanese)公立大学法人会津大学
Title IMAGE PATTERN MATCHING DEVICE, AND METHOD AND PROGRAM OF THE SAME commons meetings
Abstract PROBLEM TO BE SOLVED: To determine correspondence between object images (image patterns) in optional different images for each pixel as well as a moving image while securing the monotonic continuity between pixels.
SOLUTION: An image processing means 2 calculates minimum cumulative distance where the cumulative value of the inter-pixel distances between the pixel position of one image and the pixel positions of the other images becomes minimum by cumulatively integrating the inter-pixel distances in four-dimensional space coordinates. The image processing means 2, in integration, performs calculation in the order where the sum of values in m coordinate and values in n coordinate becomes small based on the diagonal direction. The image processing means 2, in calculating the minimum cumulative distance, restricts the transition state from the previous coordinate position in accumulating calculation, and then calculates the cumulative distance between the coordinates related to the corresponding pixel based on the distance between cumulative coordinates at the previous coordinate position.
Outline of related art and contending technology (In Japanese)


従来より、類似する画像パターンが示された異なる画像において、対応する画像間のピクセル(画素)の対応関係を求めたり、対応する特徴抽出点を求めたりする方法が考えられている。このような対応するピクセルの抽出処理は、画像応用処理分野における画像認識手法、特徴点トラッキング手法、対象物の平面画像に基づいて対象物を3次元的に復元する手法などのさまざまなコンピュータサイエンスに応用することが可能となっている。しかしながら、コンピュータサイエンスにおける応用範囲が広いにもかかわらず、画像パターンの認識処理技術に関する決定的な手法が未だに確立されていないという問題があった。



例えば、画像間のピクセル対応問題を扱った手法として、動的計画法を利用する方法が提案されている(例えば、非特許文献1~非特許文献3参照)。ここで、動的計画法とは、多変数の最適化を求める問題を解くための手法であって、最短経路問題などに利用される方法である。動的計画法では、「最適経路中の部分経路も、その部分経路における最適な経路により構成されている」という最適性の原理を利用する。このように最適性の原理を利用することにより、問題全体を部分問題における最適な解(決定)の積み重ねによって求めることができる。



このような動的計画法を応用した事例として、例えば、マッチングされる2つの画像の双方について領域を固定することにより、手書き文字認識を2次元非線形問題として求める研究が行われている(例えば、非特許文献4参照)。



また、今日では、入力時系列中の検索区間を事前に定めることなく、マッチング区間の抽出を行う連続動的計画法(1次元パターンでのセグメンテーションフリーの非線形マッチングを行う手法)が提案され(例えば、非特許文献5参照)、さらに1次元の連続動的計画法を2次元に拡張した2次元連続動的計画法が提案されている(例えば、非特許文献6参照)。2次元連続動的計画法を用いることにより、複数の画像から対象となる画像パターンの認識と抽出とを同時に行うことが可能となっている。



一方で、動画像において特徴点を抽出する処理や、特徴点などに基づいて対象物の3次元形状を復元する処理に関する研究が行われている。特徴点などに基づいて対象物の3次元形状を復元する処理では、動画を構成する画像間での適切な対応関係を求めることが重要となっており、この対応関係を求めることにより特徴点の追跡が可能となる。従来より数多く用いられる特徴点の追跡方法として、KLT方法が知られている(例えば、非特許文献7参照)。



また、異なる特徴点の追跡方法として、SIFT特徴量を用いた手法も提案されている(例えば、特許文献8参照)。SIFT特徴量を用いた手法は、物体のスケール変化、物体の回転、物体の平行移動に対して影響を受けない(不変となる)特徴点を抽出することを特徴としており、その特徴点の抽出は128次元のベクトルにより構成されている。

Field of industrial application (In Japanese)


本発明は、画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムに関し、より詳細には、類似するパターン画像が記録された複数の画像(例えば、一の画像を参照画像、他の画像を対象画像とする)において、類似する画像パターンの各画素をそれぞれの画像より抽出することによって、画素毎の対応関係を求めることが可能な画像パターンマッチング装置、画像パターンマッチング方法および画像パターンマッチング用プログラムに関する。

Scope of claims (In Japanese)
【請求項1】
 
互いに類似する画像パターンを含み得る一の画像と他の画像との画素毎の対応関係を求める画像パターンマッチング装置であって
前記一の画像と前記他の画像とにおける類似する画像パターンの画素毎の対応関係を求める画像処理手段とを有し、
該画像処理手段は、
前記一の画像を構成する画素の画素位置をi座標およびj座標を用いて特定するとともに、前記他の画像を構成する画素の画素位置をm座標およびn座標を用いて特定し、
前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画素間距離を積み上げ計算することにより算出し、
算出された前記最小累積距離に基づいて、類似した画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求め、
前記積み上げ計算を行う場合には、前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、
前記最小累積距離の算出処理を行う場合には、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うこと
を特徴とする画像パターンマッチング装置。

【請求項2】
 
前記画像処理手段は、
前記最小累積距離の算出処理を行う場合に、前記最小累積距離の計算を、前記m座標方向に関する最小累積距離の計算と前記n座標方向に関する最小累積距離の計算とに要素分割を行った上で、前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う
ことを特徴とする請求項1に記載の画像パターンマッチング装置。

【請求項3】
 
画素位置をi座標およびj座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をm座標およびn座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング方法であって、
画像処理手段が、前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画像間距離を積み上げ計算することにより算出する最小累積距離算出ステップと、
前記画像処理手段が、該最小累積距離算出ステップにおいて算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求める対応画素算出ステップとを有し、
前記最小累積距離算出ステップにおいて、
前記積み上げ計算を行う場合には、前記画像処理手段が、前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行し、
前記最小累積距離の算出処理を行う場合には、前記画像処理手段が、累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行うこと
を特徴とする画像パターンマッチング方法。

【請求項4】
 
前記最小累積距離算出ステップは、前記最小累積距離の算出処理を行う場合において、
前記最小累積距離の計算を、前記画像処理手段が、前記m座標方向に関する最小累積距離の計算と、前記n座標方向に関する最小累積距離の計算とに要素分割を行う分割ステップと、
前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向のそれぞれの方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行う積み上げ計算ステップと
を有することを特徴とする請求項3に記載の画像パターンマッチング方法。

【請求項5】
 
画素位置をi座標およびj座標により特定することが可能な一の画像と、該一の画像と類似する画像パターンを含み得る画像であり、かつ、画素位置をm座標およびn座標により特定することが可能な他の画像とに基づいて、類似する画像パターンの画素毎の対応関係を求める画像パターンマッチング用プログラムであって、
コンピュータに、
前記一の画像の画素位置と前記他の画像の画素位置との画素間距離の累積値が最小となる最小累積距離を、前記i座標、前記j座標、前記m座標および前記n座標からなる4次元空間座標において、累積的に前記画像間距離を積み上げ計算させることにより算出させる最小累積距離算出機能と、
該最小累積距離算出機能により算出された前記最小累積距離に基づいて、類似する画像パターンに対応する前記一の画像の画素位置と前記他の画像の画素位置との対応関係を求めさせる対応画素算出機能と
を実現させ、
前記最小累積距離算出機能には、
前記m座標および前記n座標における対角方向を基準として、m座標の値とn座標の値との和の値が小さくなる順番で前記積み上げ計算を実行させる積み上げ計算順番機能と、
累積計算における直前の座標位置からの遷移状態を所定の遷移パターンに制限した上で、当該直前の座標位置における累積座標間距離に基づいて対応する画素に関する累積座標間距離の算出を行わせる累積座標間距離算出機能とが含まれること
を特徴とする画像パターンマッチング用プログラム。

【請求項6】
 
前記積み上げ計算順番機能は、
前記最小累積距離の計算を、前記m座標方向に関する最小累積距離の計算と、前記n座標方向に関する最小累積距離の計算とに要素分割させる分割機能と、
前記m座標方向に関する最小累積距離の計算および前記n座標方向に関する最小累積距離の計算のそれぞれの計算において、前記i座標方向および前記j座標方向に対する前記遷移パターンを、等倍、等倍±45度回転、2倍、2倍±45度回転および縮小により構成される遷移パターンに制限することにより前記積み上げ計算を行わせる積み上げ計算機能と
を有することを特徴とする請求項5に記載の画像パターンマッチング用プログラム。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2009005682thum.jpg
State of application right Registered
(In Japanese)本技術について、ライセンスや共同研究等をご希望の方は、下記「問合せ先」まで直接お問い合わせください。


PAGE TOP

close
close
close
close
close
close
close