TOP > 国内特許検索 > 情報処理装置及び情報処理方法 > 明細書

明細書 :情報処理装置及び情報処理方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4576524号 (P4576524)
公開番号 特開2005-310009 (P2005-310009A)
登録日 平成22年9月3日(2010.9.3)
発行日 平成22年11月10日(2010.11.10)
公開日 平成17年11月4日(2005.11.4)
発明の名称または考案の名称 情報処理装置及び情報処理方法
国際特許分類 G06T   7/00        (2006.01)
FI G06T 7/00 350A
請求項の数または発明の数 5
全頁数 29
出願番号 特願2004-129088 (P2004-129088)
出願日 平成16年4月23日(2004.4.23)
審査請求日 平成19年3月28日(2007.3.28)
特許権者または実用新案権者 【識別番号】504174135
【氏名又は名称】国立大学法人九州工業大学
発明者または考案者 【氏名】中野 鉄平
【氏名】森江 隆
個別代理人の代理人 【識別番号】100121371、【弁理士】、【氏名又は名称】石田 和人
審査官 【審査官】佐藤 実
参考文献・文献 特開平11-346369(JP,A)
特開2005-293399(JP,A)
特開昭63-231798(JP,A)
T. Nakano, T. Morie, and A. Iwata,A Face/Object Recognition SystemUsing FPGA Implementation of Coarse Region Segmentation,SICE Annual Conference 2003,SICE,2003年 8月 6日,pp. 1418-1423
調査した分野 G06T 7/00~7/60
特許請求の範囲 【請求項1】
第1画像上に複数の画素を格子点とする第1格子を設定するとともに、第2画像上に前記第1格子を同相写像した第2格子を設定し、前記第2格子の格子点を移動させて第1格子の格子点のそれぞれに対応する第2格子の格子点の最適な位置を決定することで、第1画像と第2画像との間の伸縮グラフ・マッチング処理を行う情報処理装置であって、
前記第1格子の格子点を固定した条件下において、前記第2格子の各格子点の相対位置には依存せず前記第2格子の格子点の座標に依存して決定される評価量である絶対評価量を計算する絶対評価量計算手段と、
前記第2格子のそれぞれの格子点に対して、当該格子点の周囲の範囲であって当該格子点に隣接する隣接格子点を含まない所定の範囲である注目点近傍領域内に位置する画素点における絶対評価量を保存する絶対評価量記憶手段と、
前記第1格子の格子点を固定した条件下において、前記第2格子の格子点の座標とその格子点から所定の範囲内にある各格子点の座標に依存して決定される評価量である相対評価量を計算する相対評価量計算手段と、
及び、前記第2格子の格子点のそれぞれを、順次注目格子点とし、当該注目格子点及び当該注目格子点の周囲の範囲であって前記注目点近傍領域より狭い所定の範囲である移動範囲内にある画素点について、前記絶対評価量記憶手段に記憶された前記絶対評価量と前記相対評価量計算手段により算出される前記相対評価量とから所定の評価関数により総合評価量を計算し、総合評価量が最適である画素点に当該注目格子点を移動する処理を行う第2格子最適化手段と、を備え、
前記第2格子最適化手段は、前記注目格子点を移動した結果、前記移動範囲が前記注目点近傍領域内からはみ出す場合において、前記移動範囲が含まれる位置まで前記注目点近傍領域をシフトし、このシフトにより新たに前記注目点近傍領域に属することとなる画素点の絶対評価量を前記絶対評価量計算手段により計算し、前記絶対評価量記憶手段内の当該注目点近傍領域の絶対評価量を更新することを特徴とする情報処理装置。
【請求項2】
前記絶対評価量計算手段は、前記第1画像の各画素位置において定義され少なくとも1個以上の特徴量を要素として持つ特徴ベクトルと、前記第2画像の各画素位置において定義され少なくとも1個以上の特徴量を要素として持つ特徴ベクトルとの相関値で表される絶対評価量eを計算するものであり、
前記相対評価量計算手段は、前記第1格子の格子点の座標及び前記第2格子の格子点の座標を用いて算出される格子間距離の変位の総和で表される相対評価量eを計算するものであり、
前記第2格子最適化手段は、前記第2格子の格子点のそれぞれを、順次注目格子点とし、当該注目格子点及びその周囲の所定の範囲内にある画素点について、前記絶対評価量計算手段及び前記相対評価量計算手段により算出される前記絶対評価量eと前記相対評価量eとから、絶対評価量eに対して正の傾きを有し相対評価量eに対しては負の傾きを有する関数又はその定数倍で表される評価関数により総合評価量eを計算し、前記総合評価量eが最適である画素点に当該注目格子点を移動する処理を行うものであること
を特徴とする請求項1記載の情報処理装置。
【請求項3】
前記第1格子の格子点の座標を記憶する第1格子座標記憶手段と、
前記第2格子の格子点の座標を記憶する第2格子座標記憶手段と、
を備え、
前記第2格子最適化手段は、
前記第2格子の格子点のそれぞれを、順次注目格子点とし、前記注目格子点及び前記注目格子点に隣接する格子点の座標、並びにそれらの格子点に対応する前記第1格子の格子点の座標を前記第1格子座標記憶手段及び前記第2格子座標記憶手段から読み出す座標取得手段と、
前記注目点近傍領域内に位置する画素点における絶対評価量を一時的に記憶するキャッシュ・メモリと、
前記絶対評価量記憶手段から、前記注目格子点及び前記注目近傍領域内に位置する画素点における絶対評価量を読み出して前記キャッシュ・メモリに保存する絶対評価量読出手段と、
前記注目格子点及びその周囲の一定の範囲である移動範囲内にある画素点について、前記相対評価量計算手段により相対評価量を算出するとともに、前記キャッシュ・メモリに記憶された絶対評価量を用いて総合評価量を算出する総合評価量計算手段と、
前記注目格子点及びその周囲の所定の範囲内にある画素点のうち、総合評価量が最適である画素点を検出する最適画素点検出手段と、
前記最適画素点検出手段が検出する画素点である検出画素点を注目格子点として、前記第2格子座標記憶手段に保存する格子点座標更新手段と、
前記検出画素点を中心とする前記移動範囲が、前記キャッシュ・メモリに記憶された前記注目近傍領域内からはみ出す場合、前記検出画素点を中心とする前記移動範囲が含まれる位置に前記キャッシュ・メモリに記憶された前記注目近傍領域を更新する注目近傍領域更新手段と、
前記注目近傍領域更新手段が前記注目近傍領域を更新することにより新たに前記注目近傍領域に含まれる画素点について、前記絶対評価量計算手段により絶対評価量を計算し、前記キャッシュ・メモリに保存する絶対評価量補充手段と、
前記キャッシュ・メモリに記憶された注目近傍領域の絶対評価量を前記絶対評価量記憶手段に保存する絶対評価量更新手段と、
を備えた請求項1又は2記載の情報処理装置。
【請求項4】
前記キャッシュ・メモリは、
行列状又はハニカム状に2次元配列されたレジスタと、
それぞれのレジスタに対して1つ備えられた方向選択用セレクタと、
を備え、
各方向選択用セレクタの出力線は、当該方向選択用セレクタに対応するレジスタの入力線に接続されており、
各方向選択用セレクタの複数束の入力線は、それぞれ、当該方向選択用セレクタに対応するレジスタの出力線、並びに当該方向選択用セレクタに対応するレジスタに隣接するレジスタの出力線に接続されたシフト・レジスタであること
を特徴とする請求項3記載の情報処理装置。
【請求項5】
第1画像上に複数の画素を格子点とする第1格子を設定するとともに、第2画像上に前記第1格子を同相写像した第2格子を設定し、前記第2格子の格子点を移動させて第1格子の格子点のそれぞれに対応する第2格子の格子点の最適な位置を決定することで、第1画像と第2画像との間の伸縮グラフ・マッチング処理を行う情報処理方法であって、
前記第1格子の格子点を固定した条件下において、前記第2格子の各格子点の相対位置には依存せず前記第2格子の格子点の座標に依存して決定される評価量である絶対評価量を、前記第2格子のすべての格子点及び当該格子点の周囲の範囲であって当該格子点に隣接する隣接格子点を含まない所定の範囲である注目点近傍領域内にある画素点について計算し、絶対評価量記憶手段に保存する第1のステップと、
前記第2格子の格子点のそれぞれを、順次注目格子点とし、当該注目格子点及び当該注目格子点の周囲の範囲であって前記注目点近傍領域より狭い所定の範囲である移動範囲内にある画素点について総合評価量を計算し、総合評価量が最適である画素点に当該注目格子点を移動する処理を行う第2のステップと、を含み、
前記第2のステップにおいては、
前記第2格子の格子点のそれぞれを、順次注目格子点として選択するステップ、
前記移動範囲内にある画素点について、前記第1格子の格子点を固定した条件下において、前記第2格子の格子点の座標とその格子点から所定の範囲内にある各格子点の座標とに依存して決定される評価量である相対評価量を算出するステップ、
前記移動範囲に含まれる画素点について、前記相対評価量と前記絶対評価量記憶手段から読み出される絶対評価量とから所定の評価関数により総合評価量を算出するステップ、
総合評価量が最適である画素点に当該注目格子点を移動するステップ、
及び、当該注目格子点を移動した場合、移動した結果、前記移動範囲が前記注目点近傍領域内からはみ出す場合において、前記移動範囲が含まれる位置まで前記注目点近傍領域をシフトし、このシフトにより新たに前記注目点近傍領域に属することとなる画素点の絶対評価量を計算し、前記絶対評価量記憶手段内の当該注目点近傍領域の絶対評価量を更新するステップ、を含んでいることを特徴とする情報処理方法。
発明の詳細な説明 【技術分野】
【0001】
本発明は、画像内における顔や物体の認識技術の一つである伸縮グラフ・マッチング(elastic graph matching:以下、「EGM」という。)を行うための情報処理技術に関する。
【背景技術】
【0002】
近年、画像における顔や物体の認識・認証技術が盛んに研究されている。物体認識技術としては、これまでに種々の方法が提案されており、例えば、サポート・ベクター・マシン(SVM)を用いる方法(非特許文献5参照)、高次局所自己相関特徴と判別分析を用いる方法(非特許文献6参照)、EGMを用いる方法(非特許文献1参照)などが知られている。
【0003】
SVMによる方法では、複数のサンプル画像を用いて学習させた識別器を用いて、入力画像がどのサンプル画像に対応するかを判別する。この場合、判別させたい物体1個につき1個の識別器が必要となる。この方法では、すべての識別器に対して、記憶対象画像を学習させる必要があり、計算量が膨大となる。
【0004】
高次局所自己相関特徴では、画像に含まれる特徴を抽出し、その特徴毎にヒストグラムを構成し、画像固有のパラメータとする。そして、そのパラメータ同士を入力画像と比較することにより、マッチングを行う。この方法では、画像内での特徴の位置関係を無視するため、物体の位置ずれにロバストな認識が可能である。
【0005】
EGMでは、画像上に格子点を配置した評価点を、入力画像及び記憶画像それぞれに定義し、対応する評価点での一致度と格子の歪みの少なさで定義される評価関数を最大にするように格子点を移動させる。その評価関数が画像間の一致度となる。評価点を移動させて比較するため、顔の表情や物体の傾きのような変化を吸収することができる。そのため、顔認識の分野では、その性能についての評価が高く、実用化もされている(特許文献1,非特許文献2~4参照)。
【0006】
EGMでは、図15に示すように、入力画像と記憶画像とのそれぞれに評価点(以下、「格子点」という。)を格子状に並べる(図15(a),(b)参照)。そして、後述の評価関数が最大となるように格子点を移動させることで、マッチングを行う(図15(c)参照)。
【0007】
EGMを実行する前に、物体の位置を検出する必要がある。検出方法としては、EGMのオリジナルの手法として、格子の形状を固定した状態で格子を画像内で動かし、大局的な特徴による評価関数が最大となる位置を探索する方法がある(非特許文献1参照)。また、抵抗ヒューズ・ネットワーク処理により画像を大局的な領域として分割し、物体が位置する領域を抽出する方法なども知られている(非特許文献7,8参照)。また、顔に特化した方法としては、階層型ニューラル・ネットワークにより顔の位置を検出する方法(非特許文献9~11参照)、6分割矩形フィルタにより眉間を検出することで顔の候補とし、SVMにより判別する方法(非特許文献12参照)等がある。
【0008】
評価関数は(数1)により定義される(非特許文献1参照)。
【0009】
【数1】
JP0004576524B2_000002t.gif

【0010】
ここで、Ecは、入力画像と記憶画像との特徴量の差を表す項である。Edは格子全体の歪みを表す項である。λは、EcとEdとのトレード・オフを決定する定数である。
【0011】
入力画像と記憶画像との特徴量の差を表す項Ecは、(数2)のように定義される。
【0012】
【数2】
JP0004576524B2_000003t.gif

【0013】
但し、Vは全格子点の集合である。evcは、入力画像及び記憶画像の対応する格子点vでの特徴量差を表す項であり、(数3)により表される。
【0014】
【数3】
JP0004576524B2_000004t.gif

【0015】
但し、JvI, JvMは格子点vにおいて、それぞれ、入力画像、記憶画像のガボール・ウェーブレット変換(Gabor Wavelet transform:以下、「GWT」という。)により得られる特徴ベクトルである。
【0016】
次に、格子全体の歪みを表す項Edは、(数4)により定義される。
【0017】
【数4】
JP0004576524B2_000005t.gif

【0018】
ここで、evdは、格子点vとその隣接格子点との距離の和を表し、(数5)により定義される。
【0019】
【数5】
JP0004576524B2_000006t.gif

【0020】
但し、Nvは格子点vの隣接格子点の集合である。DvwI, DvwMは、それぞれ、入力画像、記憶画像の格子点v, w間の距離である。
【0021】
(数1)により得られる評価関数Eの値は、画像間の“一致度”を表す。他の記憶画像についても同様の処理を行い、最も一致度の高い画像を、同一物体(人物)の画像とする。

【特許文献1】特表2004-509391号
【非特許文献1】Martin Lades, Jan C. Vorbrnggen, Joachim Buhmann, J. Lange, Christoph von der Malsburg, Rolf P. Whrtz, and Wolfgang Konen, "Distortion Invariant Obj ect Recognition in the Dynamic Link Architecture", IEEE Transactions on Computers, vol. 42, pp. 300-31 l, 1993.
【非特許文献2】森本勝,安達澄昭,西村純一,「顔認識技術を用いた徘徊者保護支援システム」,OMRON TECHNICS,通巻137号,2001.
【非特許文献3】大久保達也,安達澄昭,岩尾博之,「顔認識技術を用いた入退室管理システム」,OMRON TECHNICS,通巻135号,2000.
【非特許文献4】T. Nakano, T. Morie, and A. Iwata, "A Face/Object Recognition System Using FPGA Implementation of Coarse Region Segmentation," in SICE Annual 'Conference, 2003.
【非特許文献5】P. J. Phillips, "Support Vector Machines Applied to Face Recognition," In Advances in Neural Information Processing Systems 11, MIT Press, pp. 803-809, 1999.
【非特許文献6】T. Kurita, N. Otsu, and T. Sato, "A Face Recognition Method Using Higher Order Local Autocorrelation And Multivariate Analysis:' ICPR, vol. B, pp. 213-216.
【非特許文献7】中野鉄平,森江隆,安藤博士,石津任章,岩田穆,「大局的画像領域分割のためのデジタル方式抵抗ヒューズ・ネットワークの設計とFPGAへの実装」,信学技報,VLD2002-154, ICD2002-219, 2003.
【非特許文献8】T Nakano, H. Ando, H. Ishizu, T. Morie, and A. Iwata, "Coarse Image Region Segmentation Using Resistive-fuse Networks Implemented in FPGA," in The 7th World Multiconference on Systemics, Cybernetics and Informatics (SCI 2003) Proceedings, volume IV, pp. 186-191, Orlando, July 27-30 2003.
【非特許文献9】S. Lawrence, C. L. Giles, A. C. Tsor and A. D. Back, "Face Recognition: A Convolutional Neural-Network Approach:' IEEE Trans. Neural Networks, vol. 8, pp. 98-1 13, 1997.
【非特許文献10】M. Matsugu. K. Mori, M. Ishii, and Y. Mitarai, "Convolutional Spiking Neural Network Model for Robust Face Detection," in Proc. Int. Conf on Neural Information Processing (ICONIP) , pp. 660-664, 2002.
【非特許文献11】K. Korekado, T. Morie, Osamu Nomura, H. Ando, T. Nakano, M. Matsugu, and A. Iwata, "A Convolutional Neural Network VLSI for Image Recognition Using Merged/Mixed Analog-Digital Architecture," in 7th Int. Conf on Knowledge-Based Intelligent Information and Engineering Systems (KES'2003), pp. II-169-176, Oxford, Sept. 3-5 2003.
【非特許文献12】川戸慎二郎,鉄谷信二,「SSRフィルターとSVMを用いた顔の実時間検出と追跡」,信学技法,PRMU2003-148 HIP2003-54, 2003.
【発明の開示】
【発明が解決しようとする課題】
【0022】
しかしながら、上記EGMのアルゴリズムをハードウェアで実行する場合、(数3)に示されたような特徴量差の演算の演算量が大きい。一方、(数1)の評価関数が最大となるように記憶画像の各格子点の座標を決める場合、各格子点を動かしながら(数1)の評価関数を計算する必要がある。従って、長い演算時間を必要とする。
【0023】
特に、膨大な記憶画像のデータベースから、入力画像にマッチングする画像を検索する場合のように、記憶画像の候補が多い場合、できるだけ演算時間を短縮する必要がある。高速化するためには、格子点vごとにevcの演算を並列化することが考えられる。しかし、evcの演算を並列化すると、回路面積が増大し、それに伴い回路の消費電力が増大するというデメリットが生じる。
【0024】
そこで、本発明の目的は、小規模な回路で実現することが可能であり、かつEGMの演算時間を短くすることが可能な情報処理技術を提供することにある。
【0025】
また、本発明の他の目的は、上記情報処理技術に使用するのに特に適したシフト・レジスタを提供することにある。
【課題を解決するための手段】
【0026】
本発明に係る情報処理装置の第1の構成は、第1画像上に複数の画素を格子点とする第1格子を設定するとともに、第2画像上に前記第1格子を同相写像(topological mapping)した第2格子を設定し、前記第2格子の格子点を移動させて第1格子の格子点のそれぞれに対応する第2格子の格子点の最適な位置を決定することで、第1画像と第2画像との間の伸縮グラフ・マッチング(elastic graph matching)処理を行う情報処理装置において、以下の構成を含むことを特徴とする:
前記第1格子の格子点を固定した条件下において、前記第2格子の各格子点の相対位置には依存せず前記第2格子の格子点の座標に依存して決定される評価量である絶対評価量を計算する絶対評価量計算手段;
前記第1格子の格子点を固定した条件下において、前記第2格子の格子点の座標とその格子点から所定の範囲内にある各格子点の座標に依存して決定される評価量である相対評価量を計算する相対評価量計算手段;
及び、前記第2格子の格子点のそれぞれを、順次注目格子点とし、当該注目格子点及びその周囲の所定の範囲内にある画素点について、前記絶対評価量計算手段及び前記相対評価量計算手段により算出される前記絶対評価量と前記相対評価量とから所定の評価関数により総合評価量を計算し、総合評価量が最適である画素点に当該注目格子点を移動する処理を行う第2格子最適化手段。
【0027】
すなわち、第2格子の格子点全体の総合評価量を最適化するに際して、注目格子点を微少量だけ移動させた場合、注目格子点以外の格子点の総合評価量は殆ど変化しない。そこで、注目格子点を微少量だけ移動させて総合評価量を評価する際に、第2格子の格子点全体の総合評価量を演算せず、注目格子点に関する総合評価量のみを第2格子最適化手段により演算する。そして、注目格子点に関する総合評価量が最適となる方向に注目格子点を移動させる。この操作を、注目格子点を順次変更しながら第2格子の格子点全体にわたって繰り返し行うことにより、第2格子の格子点全体の総合評価量を最適化することができる。
【0028】
このように、第2格子最適化手段は、注目格子点に関する総合評価量のみを演算するため、高速な演算処理が可能となる。また、各格子点について1点ずつ順次演算処理を行うため、少ないハードウェア量で構成することが可能となる。
【0029】
本発明に係る情報処理装置の第2の構成は、前記第1の構成において、前記絶対評価量計算手段は、前記第1画像の各画素位置において定義され少なくとも1個以上の特徴量を要素として持つ特徴ベクトルと、前記第2画像の各画素位置において定義され少なくとも1個以上の特徴量を要素として持つ特徴ベクトルとの相関値で表される絶対評価量eを計算するものであり、
前記相対評価量計算手段は、前記第1格子の格子点の座標及び前記第2格子の格子点の座標を用いて算出される格子間距離の変位の総和で表される相対評価量evdを計算するものであり、
前記第2格子最適化手段は、前記第2格子の格子点のそれぞれを、順次注目格子点とし、当該注目格子点及びその周囲の所定の範囲内にある画素点について、前記絶対評価量計算手段及び前記相対評価量計算手段により算出される前記絶対評価量evcと前記相対評価量evdとから、絶対評価量eに対して正の傾きを有し相対評価量eに対しては負の傾きを有する関数又はその定数倍で表される評価関数により総合評価量evを計算し、前記総合評価量evが最適である画素点に当該注目格子点を移動する処理を行うものであることを特徴とする。
【0030】
この構成により、上記背景技術において説明したような、EGMの演算処理を高速に、かつ小規模な回路で実現することが可能となる。
【0031】
ここで、「特徴ベクトル」とは、特徴パラメータを要素とするベクトルで、特徴を表現したものをいう。「特徴パラメータ(特徴量)」とは、パターンが持っている特徴を量的に表したものをいう。特徴パラメータの抽出方法としては、例えば、画像のK-L(Karhunen-Loeve)展開や、方向と周波数で決定される基底による展開(例えば、ウェーブレット展開)などがある。
【0032】
具体的には、「特徴ベクトル」としては、例えば、画像をガボール(Gabor)・ウェーブレット、ハール(Haar)・ウェーブレット、Malverウェーブレット、Morletウェーブレット、メキシカン・ハット・ウェーブレット、Shannonウェーブレット、Daubechiesウェーブレット等のウェーブレットによりウェーブレット展開して得られる特徴ベクトル等が挙げられる。
【0033】
「格子間距離」としては、ユークリッド距離のほか、シティブロック距離、重みつきユークリッド距離、マハラノビス距離、類似度等が挙げられる。
【0034】
「絶対評価量eに対して正の傾きを有し相対評価量eに対しては負の傾きを有する関数又はその定数倍で表される評価関数」としては、例えば、関数e-eや関数e-λe(λは定数)、e/eなどが挙げられる。
【0035】
「総合評価量eが最適」とは、評価関数の形に依存して、総合評価量eが最大となるときが最適である場合や総合評価量eが最小となるときが最適である場合がある。
【0036】
本発明に係る情報処理装置の第3の構成は、前記第1又は2の構成において、前記第2格子のそれぞれの格子点に対して、その格子点の周囲の所定の範囲内に位置する画素点における絶対評価量を保存する絶対評価量記憶手段を備えていることを特徴とする。
【0037】
第2格子のそれぞれの格子点に対して、その格子点の周囲の所定の範囲内に位置する画素点における絶対評価量を、絶対評価量記憶手段に予め保存しておく。そして、第2格子最適化手段が、注目格子点及びその周囲の所定の範囲内にある画素点について総合評価量計算手段により総合評価量を計算する際には、絶対評価量は絶対評価量記憶手段に予め保存されたものを使用する。これにより、同じ画素点について何度も重複して絶対評価量を演算することがなくなり、演算処理を高速化することができる。
【0038】
本発明に係る情報処理装置の第4の構成は、前記第3の構成において、前記第1格子の格子点の座標を記憶する第1格子座標記憶手段と、前記第2格子の格子点の座標を記憶する第2格子座標記憶手段と、を備え、
前記第2格子最適化手段は、
前記第2格子の格子点のそれぞれを、順次注目格子点とし、前記注目格子点及び前記注目格子点に隣接する格子点の座標、並びにそれらの格子点に対応する前記第1格子の格子点の座標を前記第1格子座標記憶手段及び前記第2格子座標記憶手段から読み出す座標取得手段と、
前記注目格子点及び前記注目格子点の周囲の所定の範囲(以下、「注目点近傍領域」という。)内に位置する画素点における絶対評価量を一時的に記憶するキャッシュ・メモリと、
前記絶対評価量記憶手段から、前記注目格子点及び前記注目近傍領域内に位置する画素点における絶対評価量を読み出して前記キャッシュ・メモリに保存する絶対評価量読出手段と、
前記注目格子点及びその周囲の一定の範囲(以下、「移動範囲」という。)内にある画素点について、前記相対評価量計算手段により相対評価量を算出するとともに、前記キャッシュ・メモリに記憶された絶対評価量を用いて総合評価量を算出する総合評価量計算手段と、
前記注目格子点及びその周囲の所定の範囲内にある画素点のうち、総合評価量が最適である画素点を検出する最適画素点検出手段と、
前記最適画素点検出手段が検出する画素点(以下、「検出画素点」という。)を注目格子点として、前記第2格子座標記憶手段に保存する格子点座標更新手段と、
前記検出画素点を中心とする前記移動範囲が、前記キャッシュ・メモリに記憶された前記注目近傍領域内からはみ出す場合、前記検出画素点を中心とする前記移動範囲が含まれる位置に前記キャッシュ・メモリに記憶された前記注目近傍領域を更新する注目近傍領域更新手段と、
前記注目近傍領域更新手段が前記注目近傍領域を更新することにより新たに前記注目近傍領域に含まれる画素点について、前記絶対評価量計算手段により絶対評価量を計算し、前記キャッシュ・メモリに保存する絶対評価量補充手段と、
前記キャッシュ・メモリに記憶された注目近傍領域の絶対評価量を前記絶対評価量記憶手段に保存する絶対評価量更新手段と、
を備えていることを特徴とする。
【0039】
この構成によれば、注目格子点が移動して移動範囲が注目点近傍領域からはみ出した場合には、注目近傍領域更新手段が注目点近傍領域を更新するとともに、絶対評価量補充手段が新たに注目近傍領域に含まれることとなった画素点について絶対評価量を計算する。そして、絶対評価量更新手段が、更新された注目点近傍領域の絶対評価量を絶対評価量記憶手段に保存する。
【0040】
このように、注目近傍領域を必要に応じて適宜更新することにより、注目近傍領域の大きさを必要最小限に小さくし絶対評価量の演算量を減らすことができる。
【0041】
本発明に係る情報処理装置の第5の構成は、前記第4の構成において、前記キャッシュ・メモリは、行列状又はハニカム状に2次元配列されたレジスタと、それぞれのレジスタに対して1つ備えられた方向選択用セレクタと、を備え、各方向選択用セレクタの出力線は、当該方向選択用セレクタに対応するレジスタの入力線に接続されており、各方向選択用セレクタの複数束の入力線は、それぞれ、当該方向選択用セレクタに対応するレジスタの出力線、並びに当該方向選択用セレクタに対応するレジスタに隣接するレジスタの出力線に接続されたシフト・レジスタであることを特徴とする。
【0042】
この構成により、すべての方向選択用セレクタの選択方向を同方向に切り替えることにより、行列状又はハニカム状に2次元配列されたレジスタのデータを行方向又は列方向(若しくは、ハニカム状の場合には斜め方向)にシフトさせることができる。従って、簡単な回路構成によって、キャッシュ・メモリに記憶された注目近傍領域を2次元的に自由にシフトさせることができる。
【0043】
本発明に係るシフト・レジスタの構成は、行列状又はハニカム状に2次元配列されたレジスタと、それぞれのレジスタに対して1つ備えられた方向選択用セレクタと、を備え、各方向選択用セレクタの出力線は、当該方向選択用セレクタに対応するレジスタの入力線に接続されており、各方向選択用セレクタの複数束の入力線は、それぞれ、当該方向選択用セレクタに対応するレジスタの出力線、並びに当該方向選択用セレクタに対応するレジスタに隣接するレジスタの出力線に接続されていることを特徴とする。
【0044】
この構成によれば、上記の情報処理装置のキャッシュ・メモリに使用するのに適したシフト・レジスタを構成することができる。
【0045】
本発明に係る情報処理方法は、第1画像上に複数の画素を格子点とする第1格子を設定するとともに、第2画像上に前記第1格子を同相写像(topological mapping)した第2格子を設定し、前記第2格子の格子点を移動させて第1格子の格子点のそれぞれに対応する第2格子の格子点の最適な位置を決定することで、第1画像と第2画像との間の伸縮グラフ・マッチング(elastic graph matching)処理を行う情報処理方法であって、前記第1格子の格子点を固定した条件下において、前記第2格子の各格子点の相対位置には依存せず前記第2格子の格子点の座標に依存して決定される評価量である絶対評価量を、前記第2格子のすべての格子点及びそれらの周囲の所定の範囲内にある画素点について計算し、絶対評価量記憶手段に保存する第1のステップと、前記第2格子の格子点のそれぞれを、順次注目格子点とし、当該注目格子点及びその周囲の所定の範囲内にある画素点について総合評価量を計算し、総合評価量が最適である画素点に当該注目格子点を移動する処理を行う第2のステップと、を含み、前記第2のステップにおいては、前記第2格子の格子点のそれぞれを、順次注目格子点として選択するステップ、前記注目格子点及びその周囲の一定の範囲(以下、「移動範囲」という。)内にある画素点について、前記第1格子の格子点を固定した条件下において、前記第2格子の格子点の座標とその格子点から所定の範囲内にある各格子点の座標とに依存して決定される評価量である相対評価量を算出するステップ、及び、前記移動範囲に含まれる画素点について、前記相対評価量と前記絶対評価量記憶手段に保存された絶対評価量とから所定の評価関数により総合評価量を算出するステップ、を含んでいることを特徴とする。
【発明の効果】
【0046】
以上のように、本発明によれば、第2格子の格子点全体の総合評価量を最適化する場合において、順次注目格子点を移動させながら、注目格子点に関する総合評価量のみを演算し注目格子点を最適な位置に移動させていくことで、高速な演算処理が可能となる。また、少ないハードウェア量で構成することが可能となる。
【発明を実施するための最良の形態】
【0047】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例1】
【0048】
〔1〕情報処理装置の機能ブロック構成
図1は本発明の実施例1に係る情報処理装置の機能構成を表すブロック図である。本発明に係る情報処理装置1は、2つの画像(第1画像及び第2画像)をガボール・ウェーブレット変換(以下、「GWT」という。)を行うことにより得られる特徴ベクトルに基づき、EGMを行う情報処理装置である。
【0049】
本発明に係る情報処理装置1は、第1特徴ベクトル記憶手段2は、第2特徴ベクトル記憶手段3、第1格子座標記憶手段4、第2格子座標記憶手段5、絶対評価量計算手段6、絶対評価量記憶手段7、相対評価量計算手段8、及び第2格子最適化手段9を備えている。
【0050】
第1特徴ベクトル記憶手段2及び第2特徴ベクトル記憶手段3、それぞれ、マッチング処理の対象となる第1画像、第2画像をガボール・ウェーブレット変換して得られる特徴ベクトルJ={J;v∈V},J={J;v∈V}が記憶される。ここで、Vは全画素点の集合を表す。以下の説明においては、入力画像を、予め用意されたテンプレート画像である記憶画像とマッチングする場合を考える。以下、第1画像のことを「入力画像」、第2画像のことを「記憶画像」といい、それぞれ、I,Mと記す。尚、この対応関係は逆でもよい。
【0051】
第1格子座標記憶手段4には、第1画像上に設定される第1格子の各格子点の座標が記憶される。ここで、「第1格子」とは、画像のマッチングを行うときに、評価対象とする第1画像内の画素を格子点とする格子をいう。
【0052】
第2格子座標記憶手段5には、第2画像上に設定される第2格子の各格子点の座標が記憶される。ここで、「第2格子」とは、画像のマッチングを行うときに、評価対象とする第2画像内の画素を格子点とする格子をいう。第2格子は、第1格子を同相写像した格子であり、第1格子内の格子点の数と等しい数の格子点を有している。初期状態においては、第2格子の各格子点は、対応する第1格子の各格子点と等しい座標を有している。
【0053】
絶対評価量計算手段6は、第1特徴ベクトル記憶手段2及び第2特徴ベクトル記憶手段3に記憶された入力画像I及び記憶画像Mの特徴ベクトルJ,Jに基づき、記憶画像の指定された画素点について絶対評価量を計算する。「絶対評価量」とは、第1格子の格子点を固定した条件下において、第2格子の各格子点間の相対座標には依存せず、第2格子の格子点の座標(絶対座標)に依存して決定される評価量である。「評価量」とは、2つの画像の“一致度”を表すための目安となる量のことをいう。
【0054】
ここで、本発明においては、EGMにおいて使用される、2つの画像の“一致度”を表す評価関数としては、種々の評価関数を使用することが可能である。本実施例のEGMにおいては、説明の便宜上、評価関数として、上述の(数1),(数2)(数4)及び後述の(数6),(数7)で表される評価関数を使用するものとする。この場合、(数6)で表される“特徴量差evc”が絶対評価量である。
【0055】
特徴量差evcは、特徴ベクトルJと特徴ベクトルJとの間の方向余弦を表す。特徴ベクトルJと特徴ベクトルJとの方向が一致しているほど、特徴量差evcの値は大きくなり、完全に方向が一致した場合には1となる。特徴ベクトルJと特徴ベクトルJとの方向が垂直の場合には特徴量差evcの値は0となる。特徴量差evcは、特徴ベクトルJ及び特徴ベクトルJの絶対値には依存しない。従って、特徴量差evcは画像の明度(グレースケール)には依存しない。
【0056】
絶対評価量記憶手段7は、第2格子のそれぞれの格子点に対して、その格子点の周囲の所定の範囲内に位置する画素点における絶対評価量(ここでは、特徴量差evc)を記憶する。
【0057】
なお、本発明においては、「格子点の周囲の所定の範囲」としては、隣接する格子を含まない程度の任意の領域にすることができる。本実施例においては、簡単のため、「格子点の周囲の所定の範囲」は、一の格子を含むm×m画素の方形領域とする。
【0058】
相対評価量計算手段8は、入力画像I及び記憶画像Mの格子点の座標に基づき、記憶画像内の指定された画素点について相対評価量を計算する。「相対評価量」とは、第1格子の格子点を固定した条件下において、第2格子の格子点の座標とその格子点から所定の範囲内にある各格子点の座標に依存して決定される評価量である。ここで、「所定の範囲」は、自由に定めることができるが、最も簡単には、隣接する範囲とすることができる。
【0059】
本実施例においては、EGMの評価関数として(数1),(数2),(数4)で表される評価関数を使用する。但し、evc及びevdについては、(数3),(数5)の代わりに、それぞれ、以下の(数6),(数7)を使用する。
【0060】
【数6】
JP0004576524B2_000007t.gif

【0061】
【数7】
JP0004576524B2_000008t.gif
ここでは、evcは、(数3)における平方根演算を省略するために、(数3)で定義された特徴量差を表す項を自乗して(数6)として定義している。また、evdは、自乗計算の煩雑さを避けるため、(数5)の右辺の平方根をとった(数7)により定義されている。以下本実施例においては、(数6)で定義されるevcを「特徴量差」、(数7)で定義されるevdを「歪み量」と呼ぶ。
【0062】
歪み量evdは、第1格子の格子点間の距離に対する第2格子の格子点間の距離の相違の度合いを表す量である。第1格子に対して第2格子が歪んでいるほど歪み量evdは大きくなる。逆に、第1格子と第2格子とが同型である場合には歪み量evdは0となる。
【0063】
第2格子最適化手段9は、第2格子の格子点のそれぞれを、順次、「注目格子点」として、この注目格子点を、総合評価量が最適化される方向に移動する処理を行う。この際、第2格子最適化手段9は、注目格子点及びその周囲の所定の範囲内にある画素点について、絶対評価量計算手段6及び相対評価量計算手段8により算出される絶対評価量及び相対評価量から、所定の評価関数により総合評価量を算出する。そして、これらの座標点のうち、総合評価量が最適である画素点に注目格子点を移動させる。
【0064】
ここで、「総合評価量」とは、絶対評価量及び相対評価量から所定の評価関数によって算出される2つの画像の“一致度”を表す量である。ここでは、評価関数として、(数8)を使用する。
【0065】
【数8】
JP0004576524B2_000009t.gif

【0066】
ここで、λは、特徴量差evcと歪み量evdとのトレード・オフを決定する定数である。この総合評価量のことを、以下、「評価値」と呼ぶことにする。評価値evは、特徴量差evcが大きいほど大きくなり、また、歪み量evdが小さいほど大きくなる。
【0067】
第2格子最適化手段9は、キャッシュ・メモリ10、絶対評価量読出手段11、絶対評価量更新手段12、座標取得手段13、総合評価量計算手段14、最適画素点検出手段15、格子点座標更新手段16、注目近傍領域更新手段17、及び絶対評価量補充手段18を備えている。
【0068】
キャッシュ・メモリ10は、注目点及びその周囲の所定の範囲(以下、「注目点近傍領域」という。)内に位置する画素点における評価値evを一時的に記憶するシフト・レジスタである。キャッシュ・メモリ10の詳細な構成については後述する。
【0069】
絶対評価量読出手段11は、絶対評価量記憶手段7から、注目格子点が属する注目近傍領域内に位置する画素点における評価値evを読み出してキャッシュ・メモリ10に保存する。
【0070】
絶対評価量更新手段12は、キャッシュ・メモリ10に記憶されている注目近傍領域内に位置する画素点における評価値evを、絶対評価量記憶手段7に保存する。
【0071】
座標取得手段13は、第2格子の格子点のそれぞれを、順次、注目格子点とし、注目格子点及び注目格子点に隣接する格子点の座標、並びに注目格子点に対応する第1格子の格子点の座標を、第1格子座標記憶手段4及び第2格子座標記憶手段5から読み出す。
【0072】
総合評価量計算手段14は、注目格子点及びその周囲の一定の範囲(以下、「移動範囲」という。)内にある画素点について、相対評価量計算手段8により歪み量evdを算出する。また、それとともに、キャッシュ・メモリ10に記憶された特徴量差evcを用いて(数8)により評価値evを算出する。
【0073】
最適画素点検出手段15は、注目格子点及びその周囲の所定の範囲内にある画素点のうち、評価値evが最大である画素点を検出する。
【0074】
格子点座標更新手段16は、最適画素点検出手段15が検出する画素点(以下、「検出画素点」という。)を注目格子点として、その座標を第2格子座標記憶手段5に保存する。
【0075】
注目近傍領域更新手段17は、検出画素点を中心とする移動範囲が、キャッシュ・メモリ10に記憶された注目近傍領域内からはみ出す場合において、検出画素点を中心とする移動範囲が含まれる位置にキャッシュ・メモリ10に記憶された注目近傍領域をシフトする。このシフト動作の詳細についても、後述する。
【0076】
絶対評価量補充手段18は、注目近傍領域更新手段が注目近傍領域をシフトすることにより新たに注目近傍領域に含まれる画素点について、絶対評価量計算手段6により特徴量差evcを計算し、キャッシュ・メモリ10に保存する。
【0077】
〔2〕情報処理装置のハードウェア構成
次に、以上のような機能構成を有する本実施例に係る情報処理装置をハードウェアで構成した例について説明する。
【0078】
図2は、本発明の実施例1に係る情報処理装置の回路構成を表すブロック図である。情報処理装置1は、画像メモリ21、特徴量差計算ブロック22、第1格子座標レジスタ23、第2格子座標レジスタ24、アービタ25、評価値計算ユニット26、上格子点座標レジスタ27、下格子点座標レジスタ28、左格子点座標レジスタ29、右格子点座標レジスタ30、特徴量差レジスタ31、読出キャッシュ・メモリ32、書込キャッシュ・メモリ33、及びコントローラ34を備えている。
【0079】
また、評価値計算ユニット26は、注目格子点座標レジスタ35及び更新ユニット36を備えている。さらに、コントローラ34は、内部に、移動判定カウンタ37及び更新回数カウンタ38を備えている。
【0080】
ここで、図1と図2の対応関係を明らかにしておく。第1特徴ベクトル記憶手段2及び第2特徴ベクトル記憶手段3は、画像メモリ21により実現されている。第1格子座標記憶手段4は、第1格子座標レジスタ23により実現されている。第2格子座標記憶手段5は、第2格子座標レジスタ24により実現されている。絶対評価量計算手段6は、特徴量差計算ブロック22により実現されている。絶対評価量記憶手段7は、特徴量差レジスタ31により実現されている。相対評価量計算手段8及び第2格子最適化手段9は、更新ユニット36とコントローラ34とが協働することにより実現されている。
【0081】
図2において、画像メモリ21は、外部から入力される入力画像I及び記憶画像Mの特徴ベクトルJ,Jを記憶するメモリである。
【0082】
特徴量差計算ブロック22は、画像メモリ21に記憶された座標点vの特徴ベクトルJ,Jを読み出して、その座標点vの特徴量差evcを演算するブロックである。特徴量差計算ブロック22の詳しい内部構成については後述する。
【0083】
第1格子座標レジスタ23は、外部から入力される第1格子の各格子点の座標を記憶するレジスタである。第2格子座標レジスタ24は、第2格子の各格子点の座標を記憶するレジスタである。アービタ25は、第2格子座標レジスタ24のデータ入出力線に接続されており、第2格子座標レジスタ24のデータの入出力方向の調停を行う。
【0084】
特徴量差レジスタ31は、第2格子の各格子点について、その格子点を含む注目点近傍領域の座標点の特徴量差evcと、その格子点の注目点近傍領域における相対座標xvfとを記憶するレジスタである。
【0085】
評価値計算ユニット26は、第2格子の注目格子点について、その評価値eが最大となる方向に移動させる処理を行うユニットである。評価値計算ユニット26は、注目格子点座標レジスタ35及び更新ユニット36を有している。
【0086】
注目格子点座標レジスタ35には、アービタ25を介して第2格子座標レジスタ24から読み出される注目格子点の座標が格納される。また、上格子点座標レジスタ27、下格子点座標レジスタ28、左格子点座標レジスタ29、及び右格子点座標レジスタ30には、それぞれ、アービタ25を介して第2格子座標レジスタ24から読み出される注目格子点の上下左右の格子点の座標が格納される。
【0087】
更新ユニット36は、注目格子点座標レジスタ35、上格子点座標レジスタ27、下格子点座標レジスタ28、左格子点座標レジスタ29、及び右格子点座標レジスタ30に格納された座標と、第1格子座標レジスタ23から読み出される第1格子内の注目格子点及びその上下左右の格子点の座標とに基づいて、歪み量evdの演算を行う。それとともに、更新ユニット36は、特徴量差レジスタ31に保存されている注目格子点が属する注目点近傍領域の特徴量差evcを用いて、移動範囲内の座標点についての評価値evの演算を行う。そして、更新ユニット36は、この評価値evが最大となる座標点に注目格子点を移動させる処理を行う。更に、更新ユニット36は、必要に応じて注目点近傍領域の更新処理を行う。この更新処理により新たに注目点近傍領域に含まれることとなった座標点の特徴量差evcは特徴量差計算ブロック22により演算される。そして、更新ユニット36は、新たな注目点領域の特徴量差evcを、特徴量差レジスタ31に保存する。尚、更新ユニット36の詳細な内部構成については後述する。
【0088】
読出キャッシュ・メモリ32及び書込キャッシュ・メモリ33は、それぞれ、特徴量差レジスタ31から読み出す注目点近傍領域の特徴量差evc及び特徴量差レジスタ31へ書き込む注目点近傍領域の特徴量差evcを一時的に保存するキャッシュ・メモリである。これらのキャッシュ・メモリは、特徴量差レジスタ31のデータの読み出しや書き込みを高速化するために設けられているものである。
【0089】
コントローラ34は、情報処理装置1全体の動作を制御するものである。移動判定カウンタ37は、更新ユニット36を用いて、評価値evが最大となるように第2格子の各格子点の格子点の移動処理を行う場合、全格子点について1巡の移動処理を行った場合に、すべての格子点が移動しなかったか否かを判定するために設けられたカウンタである。更新回数カウンタ38は、全格子点について1巡の移動処理を行った回数(最適化サイクル数)を計数するためのカウンタである。これらの動作については後述する。
【0090】
〔3〕特徴量差計算ブロック
図3は、図2の特徴量差計算ブロックの構成を表す図である。図3に表された特徴量差計算ブロック22は(数6)の演算を行う。特徴ベクトルJ,Jのベクトル要素数をN、各要素のビット精度をN、画像メモリ21の出力ビット幅をNとする。画像メモリ21から、J,Jの順番で、N/NずつN/(N/N)回に分けて、各ベクトル要素を特徴量差計算ブロック22の入力線に入力する。ここで、G≡N/N,H≡N/(N/N)とおく。特徴量差計算ブロック22の入力線の本数はG束(1束の本数はN本)である。ここでは、説明の便宜上、G=4,H=5の場合が示されているが、G,Hはこれに限られるものではない。
【0091】
特徴量差計算ブロック22は、分子計算ブロック41、分母計算ブロック42、及び除算器43を備えている。分子計算ブロック41及び分母計算ブロック42は、それぞれ、(数6)の分子及び分母の演算を行う演算器である。除算器43は、分子計算ブロック41の出力値を、分母計算ブロック42の出力値で除算して、その結果を特徴量差evcとして出力する。
【0092】
分子計算ブロック41は、G個のシフト・レジスタ44、G個の乗算器45、並びに、累算器46及び自乗演算器47を備えている。シフト・レジスタ44は、Nビット幅のレジスタがH個直列接続されている。G束の各入力線のそれぞれは、その入力線に対応するシフト・レジスタ44の入力端子及び乗算器45の一方の入力端子に接続されている。また、乗算器45の他方の入力端子は、シフト・レジスタ44の出力端子が接続されている。乗算器45は、特徴ベクトルJ,Jの各要素の乗算を行う。
【0093】
累算器46はG個の入力端子を有しており、これらはそれぞれの乗算器45の出力端子に接続されている。累算器46は、特徴ベクトルJ,Jの各要素を掛けた結果を累算することにより、J・Jを計算する。
【0094】
累算器46の出力端子は、自乗演算器47の入力端子に接続されている。自乗演算器47は、J・Jの自乗計算を行う。この自乗演算器47の出力が分子計算ブロック41の出力となる。
【0095】
尚、本実施例においては、特徴量差evcとして(数6)を用いた例を示しているが、他の例として特徴量差evcに(数3)を使用する場合には、自乗演算器47を省略すればよい。
【0096】
分母計算ブロック42は、G個の自乗演算器48、累算器49、セレクタ50、レジスタ51、及び乗算器52を備えている。G個の自乗演算器48の入力端子には、それぞれ対応する入力線束が接続されている。自乗演算器48は、入力線から入力される特徴ベクトルJ,Jの自乗演算を行う。
【0097】
累算器49はG個の入力端子を有しており、これらはそれぞれの乗算器48の出力端子に接続されている。累算器49は、特徴ベクトルJ,Jの自乗値を累算することにより、∥J,∥Jを計算する。
【0098】
尚、本実施例においては、特徴量差evcとして(数6)を用いた例を示しているが、他の例として特徴量差evcに(数3)を使用する場合には、累算器49の出力側に、∥J,∥Jの平方根を演算する平方根演算器を設ければよい。
【0099】
セレクタ50は、2つの入力端子α,βを備えている。セレクタ50は、入力端子α,βのうち何れか一方を選択して出力端子と接続する。セレクタ50の出力端子は、レジスタ51の入力端子に接続されている。レジスタ51の出力端子は、セレクタ50の入力端子β及び乗算器52の一方の入力端子に接続されている。累算器49の出力端子は、乗算器52の他方の入力端子、及びセレクタ50の入力端子αに接続されている。乗算器52の出力が、分母計算ブロック42の出力となる。
【0100】
この特徴量差計算ブロック22の演算処理の手順は、次の通りである。
【0101】
(1)セレクタ50の選択を入力端子α側に切り替えるとともに、累算器49をクリアする。
【0102】
(2)画像メモリ21は、特徴ベクトルJを、G個の要素ずつH回に分けて入力線に入力する。分子計算ブロック41では、各シフト・レジスタ44が特徴ベクトルJの値を保持する。一方、分母計算ブロック42では、各自乗演算器48が特徴ベクトルJの各要素を自乗し、累算器49がこれらを累算する。そして、レジスタ51は、累算器49の累算値∥Jを保持する。
【0103】
(3)セレクタ50の選択を入力端子β側に切り替えるとともに、累算器46,49をクリアする。
【0104】
(4)画像メモリ21は、特徴ベクトルJを、G個の要素ずつH回に分けて入力線に入力する。分子計算ブロック41の累算器46では、入力線から入力される特徴ベクトルJの各要素とシフト・レジスタ44に保持された特徴ベクトルJの各要素とを乗算し累算する。自乗演算器47は、累算器46の累算結果を自乗して、(J・Jを出力する。一方、分母計算ブロック42の各自乗演算器48は、入力線から入力される特徴ベクトルJの各要素を自乗する。そして、累算器49は、これらを累算し∥Jを演算する。乗算器52は、レジスタ51が出力する累算値∥Jと累算器49が出力する累算値∥Jとを乗算し、∥J・∥Jを出力する。
【0105】
(5)最後に、除算器43が、分子計算ブロック41の出力(J・Jから分母計算ブロック42の出力∥J・∥Jを除算して、(数6)の演算結果を得る。
【0106】
〔4〕更新ユニット
図4は、図2の更新ユニットの構成を表す図である。更新ユニット36は、距離演算器61、歪み演算器62、評価値計算ブロック63、ウィナー・テーク・オール回路(Winner Take All circuit:以下、「WTA回路」という。)64、座標更新ブロック65、特徴量差データ・アドレス・レジスタ66、及び更新ブロック67を備えている。
【0107】
距離演算器61は、注目格子点及びその周囲の移動範囲内にある画素点(注目格子点を含めて合計9個の画素点)について、注目格子点の上下左右の格子点との間の距離Dvwを計算する。
【0108】
ここで、注目格子点と移動範囲及び注目点近傍領域との関係について説明する。例えば、画像の画素点が図5のように配列されている場合を考える。図5において「○」が画素点を表している。例えば、画素点Aが注目格子点であるとする。このとき、移動範囲は、注目格子点Aと、注目格子点Aの上下左右及び左上、右上、左下、右下の注目格子点Aに隣接する画素点B~Iとの合計9個の画素点を含む領域である。また、注目点近傍領域は、移動範囲内のすべての画素点A~Iを含む所定の大きさ(図5の例では、6×6画素)の方形領域とされる。
【0109】
歪み演算器62は、移動範囲内の9個の画素点のそれぞれについて、注目格子点の上下左右に|Dvw-Dvw|を演算し、これらを加えて(数7)の歪み量evdを演算する。従って、この距離演算器61及び歪み演算器62が、図1における相対評価量計算手段8として機能する。
【0110】
尚、本実施例においては、歪み量evdとして(数7)を用いた例を示しているが、他の例として歪み量evdに(数5)を使用する場合には、歪み演算器62は、|Dvw-Dvwを演算するように構成すればよい。
【0111】
評価値計算ブロック63は、歪み演算器62が出力する歪み量evdと、後述の更新ブロック67が出力する特徴量差evcから、(数8)の演算を行って評価値evを出力するブロックである。ここでは、評価値evの演算は、注目格子点を含む移動領域内の9個の画素点について、並列に演算される。この評価値計算ブロック63が、図1における総合評価量計算手段14として機能する。
【0112】
WTA回路64は、注目格子点を含む移動領域内の9個の画素点のうち、評価値計算ブロック63が出力する評価値evが最大であるもの(以下、「検出画素点」という。)を選択し、座標更新ブロック65に出力する。このWTA回路64が、図1における最適画素点検出手段15として機能する。
【0113】
座標更新ブロック65は、WTA回路64から検出画素点が入力されると、注目格子点座標レジスタ35の座標値を、検出画素点の座標値に更新するとともに、特徴量差データ・アドレス・レジスタ66の記憶値xvfを、注目点近傍領域内における検出画素点の相対座標値に更新する。この座標更新ブロック65が、図1における格子点座標更新手段16として機能する。
【0114】
特徴量差データ・アドレス・レジスタ66は、注目点近傍領域内における注目格子点の相対座標値xvfを記憶する。この相対座標値xvfは、更新ブロック67、書込キャッシュ・メモリ33、及びコントローラ34へ出力される。
【0115】
更新ブロック67は、注目格子点を含む注目点近傍領域内における画素点について、特徴量差の保持と更新を行う回路ブロックである。この更新ブロック67の内部構成の詳細は後述する。
【0116】
以上のような更新ユニット36の演算処理の手順は、次の通りである。
【0117】
(1)距離演算器61で、注目格子点が属する移動範囲内の9個の画素点について、隣接格子点との距離を計算する。
【0118】
(2)この9個の画素点について、歪み演算器62が歪み量evdを計算する。
【0119】
(3)評価値計算ブロック63は、(2)で歪み演算器62が出力する9個の画素点についての歪み量evdと、更新ブロック67が出力する各画素点に対応した特徴量差evcとを用いて、各画素点について(数8)の評価関数により評価値evを求める。
【0120】
(4)WTA回路64は、9個の画素点のうち、評価値evが最大となる画素点を選択しこれを検出画素点として座標更新ブロック65に出力する。
【0121】
(5)座標更新ブロック65は、注目格子点座標レジスタ35の座標値を、検出画素点の座標値に更新することによって、注目格子点を検出画素点へ移動させる。また、このとき、特徴量差データ・アドレス・レジスタ66の相対座標値xvfも更新する。
【0122】
(6)コントローラ34は、特徴量差データ・アドレス・レジスタ66が出力する相対座標値xvfから、新たな注目格子点の移動範囲が、注目点近傍領域からはみ出るか否かを判定する。ここで、はみ出る場合には、コントローラ34は、更新ブロック67により、新たな注目格子点の移動範囲が注目点近傍領域内に入るように、注目点近傍領域のシフト処理を行う。この注目点近傍領域のシフト処理については後述する。
【0123】
(7)最後に、コントローラ34は、注目格子点座標レジスタ35に保存された注目格子点の座標を、アービタ25を介して第2格子座標レジスタ24に保存する。また、更新ブロック67が保持している注目点近傍領域内の画素点の特徴量差evc及び特徴量差データ・アドレス・レジスタ66が保持する相対座標値xvfを書込キャッシュ・メモリ33に書き出す。書込キャッシュ・メモリ33に書き出された特徴量差evc及び相対座標値xvfは、特徴量差レジスタ31に保存される。
【0124】
〔5〕更新ブロック
図6は、図4の更新ブロックの構成を表す図である。更新ブロック67は、キャッシュ・メモリ71、データ更新用シフト・レジスタ72、及びセレクタ73を備えている。
【0125】
キャッシュ・メモリ71は、図1のキャッシュ・メモリ10に相当する。このキャッシュ・メモリ71は、注目点近傍領域内の各画素点の特徴量差evcを保持するためのメモリ・セル71aが行列状に2次元配列された構成からなる。1個のメモリ・セル71aは、レジスタ75と方向選択用セレクタ76との組み合わせにより構成されている。
【0126】
各メモリ・セル71aの方向選択用セレクタ76の出力線は、当該メモリ・セル71a内のレジスタ75の入力線に接続されている。また、各方向選択用セレクタ76の6束の入力線は、それぞれ、当該メモリ・セル71a内のレジスタ75の出力線、当該メモリ・セル71aの上下左右に隣接するメモリ・セル71a内のレジスタ75の出力線、及び、読出キャッシュ・メモリ32の出力線に接続されている。各方向選択用セレクタ76の選択の切り替えは、コントローラ34から入力される3ビットのシフト制御信号によって行われる。
【0127】
このような構成により、レジスタ75は、各メモリ・セル71aに保持されたデータを、上下左右に2次元的にシフトさせることが可能な2次元のシフト・レジスタとなる。すなわち、図1における注目近傍領域更新手段17が実現される。
【0128】
また、方向選択用セレクタ76により読出キャッシュ・メモリ32の出力線を選択することにより、読出キャッシュ・メモリ32に保存された注目点近傍領域内の各画素点の特徴量差evcを、全メモリ・セル71aに一度に入力することができる。
【0129】
データ更新用シフト・レジスタ72は、キャッシュ・メモリ71のデータを更新するために使用されるシフト・レジスタである。データ更新用シフト・レジスタ72は、図1における絶対評価量補充手段18を実現する。
【0130】
キャッシュ・メモリ71のメモリ・セル71aの個数をm×m個とすると、データ更新用シフト・レジスタ72は、m個のレジスタ72aが一列に接続された構成からなる。最前段のレジスタ72aの入力線は、特徴量差計算ブロック22の出力端子に接続されている。また、最前段以外のレジスタ72aの入力線は、前段のレジスタ72aの出力線に接続されている。また、各レジスタ72aの出力線は、キャッシュ・メモリ71の上下左右の辺に沿ったメモリ・セル71aの方向選択用セレクタ76の入力線の一つに接続されている。
【0131】
キャッシュ・メモリ71の上下左右の辺の何れかに沿ったメモリ・セル71aの列に対して特徴量差evcを入力する場合には、まず、特徴量差計算ブロック22で特徴量差evcを1つずつ計算し、データ更新用シフト・レジスタ72の最前段のレジスタ72aに入力する。そして、データ更新用シフト・レジスタ72をシフトさせながら、特徴量差evcを入力し、すべてのレジスタ72aに特徴量差evcを入力する。
【0132】
そして、キャッシュ・メモリ71の上下左右の辺の何れかに沿ったメモリ・セル71aの方向選択用セレクタ76を切り替えて、データ更新用シフト・レジスタ72のレジスタ72aの出力線を選択する。これにより、1辺につき一度に特徴量差evcを更新することができる。
【0133】
セレクタ73は、特徴量差データ・アドレス・レジスタ66が出力する注目格子点の注目点近傍領域内の相対座標値xvfに基づいて、キャッシュ・メモリ71の各メモリ・セル71aから、注目格子点の属する移動範囲内の9個の画素点の特徴量差evcを選択し出力する。
【0134】
また、キャッシュ・メモリ71の各メモリ・セル71aの出力線(レジスタ75の出力線)は、書込キャッシュ・メモリ33の入力端子に接続されている。これにより、キャッシュ・メモリ71の各メモリ・セル71aの内容を、書込キャッシュ・メモリ33に一度に書き込むことができる。
【0135】
〔6〕情報処理装置の動作
最後に、上記実施例1に係る情報処理装置のEGM演算処理動作について説明をする。図7は、本発明の実施例1に係る情報処理方法の処理の流れを表すフローチャートである。
【0136】
まず、最初に、外部から入力画像Iと記憶画像Mとの特徴ベクトルJ,Jが入力され、画像メモリ21に保存される(S1)。また、このとき、外部から第1格子の各格子点の座標x={x}も入力され、第1格子座標レジスタ23に保存される。この、第1格子の各格子点の座標x={x}は、アービタ25を介して第2格子座標レジスタ24にも入力され、保存される。
【0137】
次に、コントローラ34の制御により、第2格子の各格子点を中心とする注目点近傍領域内の画素点について、特徴量差計算ブロック22が特徴量差evcを計算し、特徴量差レジスタ31に保存する(S2)。これにより、特徴量差レジスタ31が初期化される。
【0138】
次に、コントローラ34の制御により、第2格子の全格子点の評価値evの和(数1)が最大となるように、第2格子の全格子点の座標の最適化処理が行われる(S3)。
【0139】
最後に、コントローラ34が(数1)の評価関数Eを計算し、評価関数Eの値と最適化された第2格子の座標値を出力し(S4)、EGM演算処理を終了する。
【0140】
図8は、図7のステップS2における特徴量差レジスタの初期化処理の動作を表すフローチャートである。
【0141】
まず、コントローラ34は、内部のカウンタiの値を1に初期化する(S11)。
【0142】
次に、コントローラ34は、第2格子座標レジスタ24からi番目の格子点の座標を読み出し、アービタ25を介して注目格子点座標レジスタ35に保存する。また、コントローラ34は、第2格子座標レジスタ24からi番目の格子点の上下左右に隣接する格子点の座標を読み出し、アービタ25を介して、それぞれ、上格子点座標レジスタ27、下格子点座標レジスタ28、左格子点座標レジスタ29、及び右格子点座標レジスタ30に保存する(S12)。
【0143】
次に、コントローラ34は、更新ユニット36を制御することにより、i番目の格子点を含む注目点近傍領域の特徴量差evcを計算する(S13)。この計算を、図9を用いて説明する。
【0144】
まず、図9(a)に示すように、コントローラ34は、特徴量差計算ブロック22により、特徴量差evcを順次計算し、データ更新用シフト・レジスタ72に格納する。データ更新用シフト・レジスタ72のすべてのレジスタ72aに特徴量差evcが格納された時点で、コントローラ34は、キャッシュ・メモリ71の各セルの方向選択用セレクタ76の選択を、下方向にシフトするように切り替える。これにより、図9(b)に示すように、データ更新用シフト・レジスタ72の特徴量差evcは、キャッシュ・メモリ71の上辺のメモリ・セル71aに保存される。
【0145】
次に、また同様に、コントローラ34は、特徴量差計算ブロック22により、特徴量差evcを順次計算し、データ更新用シフト・レジスタ72に格納する(図9(c))。そして、データ更新用シフト・レジスタ72のすべてのレジスタ72aに特徴量差evcが格納された時点で、コントローラ34は、キャッシュ・メモリ71の各セルの方向選択用セレクタ76の選択を、下方向にシフトするように切り替える。これにより、図9(d)に示すように、データ更新用シフト・レジスタ72の特徴量差evcは、キャッシュ・メモリ71の上辺のメモリ・セル71aに保存される。また、キャッシュ・メモリ71の各行のメモリ・セル71aの内容は、その下の行のメモリ・セル71aに保存される。
【0146】
以下同様に特徴量差evcの演算を実行し、最終的には図9(e)に示したように、すべての特徴量差evcが計算され、キャッシュ・メモリ71に格納される。
【0147】
図8に戻って、次に、コントローラ34は、キャッシュ・メモリ71に格納されたi番目の格子点を含む注目点近傍領域の特徴量差evc及びi番目の格子点の注目点近傍領域内にける相対座標を、書込キャッシュ・メモリ33に取り込み、特徴量差レジスタ31に保存する(S14)。
【0148】
そして、コントローラ34は、カウンタiの値を1だけインクリメントする(S15)。ここで、iが全格子点数N以下であれば(S16)、再びステップS12に戻る。iがNよりも大きければ、特徴量差レジスタ31の初期化処理を終了する。
【0149】
図10は、図7のステップS3における格子点座標の最適化処理の流れを表すフローチャートである。
【0150】
まず、コントローラ34は、移動判定カウンタ37のカウント値n及び更新回数カウンタ38のカウント値nを0に初期化する(S21)。
【0151】
次に、コントローラ34は、注目格子点の番号を表す変数iを1に初期化する(S22)。
【0152】
次に、コントローラ34は、i番目の格子点を注目格子点として、第2格子座標レジスタ24から、注目格子点の座標、及び注目格子点の上下左右に隣接する画素点の座標を、注目格子点座標レジスタ35、上格子点座標レジスタ27、下格子点座標レジスタ28、左格子点座標レジスタ29、及び右格子点座標レジスタ30に読み出す。また、コントローラ34は、特徴量差レジスタ31から、注目格子点が属する注目点近傍領域の特徴量差evcを読み出してキャッシュ・メモリ71に格納する。また、コントローラ34は、同時に特徴量差レジスタ31から注目格子点の注目点近傍領域内の相対座標を読み出して、特徴量差データ・アドレス・レジスタ66に設定する。そして、距離演算器61及び歪み演算器62は、注目格子点が属する移動範囲内の画素点について、注目格子点の上下左右に隣接する格子点との間の歪み度eを計算する(S23)。
【0153】
次に、評価値計算ブロック63は、i番目の格子点が属する移動範囲内の画素点について、評価値evを計算する(S24)。
【0154】
次に、WTA回路64は、移動範囲に属する画素点のうち、評価値evが最大のものを検出し、注目格子点をその画素点に移動させる(S25)。
【0155】
なお、ステップS23~S25の動作の詳細は、すでに説明しているため、ここでは省略する。
【0156】
次に、コントローラ34は、i番目の格子点が移動したか否かを判定する(S26)。移動していない場合には、コントローラ34は、移動判定カウンタ37のカウント値nを1だけ増加させる(S27)。一方、移動している場合には、コントローラ34は、移動判定カウンタ37のカウント値nを0にクリアする(S28)。
【0157】
次に、座標更新ブロック65は、注目格子点座標レジスタ35の座標値x、及び特徴量差データ・アドレス・レジスタ66の相対座標値xvfを更新する(S29)。
【0158】
次に、コントローラ34は、i番目の格子点の移動領域が注目点近傍領域からはみ出すか否かを判定する(S30)。
【0159】
はみ出す場合は、コントローラ34は、相対座標値xvfから注目点近傍領域の移動方向を決定し、特徴量差計算ブロック22により、注目点近傍領域の移動により新たに注目点近傍領域に属することとなる画素点の特徴量差evcを計算して、データ更新用シフト・レジスタ72に格納する(S31)。そして、コントローラ34は、キャッシュ・メモリ71内の全メモリ・セル71aの方向選択用セレクタ76の選択を切り替えて、キャッシュ・メモリ71のデータをシフトさせる(S32)。そして、コントローラ34は、注目点近傍領域の移動後の相対座標値xvfの値を計算して、特徴量差データ・アドレス・レジスタ66の相対座標値xvfを更新する(S33)。
【0160】
一方、ステップS30において、i番目の格子点の移動領域が注目点近傍領域からはみ出さない場合には、ステップS31~S33の動作は行わない。
【0161】
ここで、注目点近傍領域の移動処理について補足説明する。例えば、注目格子点が図11(a)に示す画素点Aにある場合を考える。このとき、画素点A~Iが注目格子点の属する移動領域である。このとき、キャッシュ・メモリ71には、図11(b)に示すような位置に、画素点A~Iの特徴量差evcが格納されている。
【0162】
ここで、注目格子点が画素点Aから画素点Eに移動する場合を考える。注目格子点が画素点Eに移動すると、新たな注目格子点の移動範囲は、図12(a)に示された画素点A,B,C,E,G,I,L,M,Kとなる。この場合、画素点L,M,Kは注目点近傍領域からはみ出す。そこで、この場合、注目点近傍領域を右に移動させる。
【0163】
まず、コントローラ34は、特徴量差計算ブロック22により、新たに注目点近傍領域に含まれることとなる画素点J~Oの特徴量差evcを計算して、データ更新用シフト・レジスタ72に保存する。そして、コントローラ34は、図12(b)に示すように、データ更新用シフト・レジスタ72をキャッシュ・メモリ71の最右列に接続し、キャッシュ・メモリ71を左に1つシフトさせる。これにより、図13(b)に示すように、キャッシュ・メモリ71の各メモリ・セル71aのデータは左に1つシフトされ、最右列には、画素点J~Oの特徴量差evcが格納される。すなわち、画像上では、図13(a)に示すように注目点近傍領域が右に1画素だけシフトしたこととなる。
【0164】
図10に戻って、次に、コントローラ34は、キャッシュ・メモリ71に保存された注目点近傍領域の特徴量差evcを、特徴量差レジスタ31に保存する(S34)。そして、コントローラ34は、注目格子点の番号を表す変数iを1だけ増加させ、次の格子点を注目格子点とする(S35)。
【0165】
ここで、iが全格子点数N以下の場合、ステップS23に戻る(S36)。一方、iがNより大きい場合には、コントローラ34は、更新回数カウンタ38のカウント値nを1だけ増加させる(S37)。
【0166】
ここで、n=N、すなわち、全格子点において格子点の移動がなかった場合には(S38)、格子点座標は最適化されているため、処理を終了する。一方、n<Nの場合、コントローラ34は、更新回数カウンタ38のカウント値nが所定の閾値Nrmaxを超えているか否かを判定し(S39)、超えていない場合には、ステップS22に戻る。一方、カウント値nが所定の閾値Nrmaxを超えた場合には、収束しない状態を避けるため、処理を終了する。
【0167】
以上のような処理により、EGM演算処理を行うことができる。また、本実施例の演算処理では、評価関数(数1)の代わりに(数8)を使用して行うため、高速な演算処理が可能となる。また、少ないハードウェア量で構成することが可能となる。
【0168】
尚、本実施例では、キャッシュ・メモリ71には、メモリ・セル71aが行列状に2次元配列されたシフト・レジスタを使用した例を示した。しかし、キャッシュ・メモリには、図14に示すような、メモリ・セル71a’がハニカム状に二次元配列されたシフト・レジスタを使用することもできる。
【図面の簡単な説明】
【0169】
【図1】本発明の実施例1に係る情報処理装置の機能構成を表すブロック図である。
【図2】本発明の実施例1に係る情報処理装置の回路構成を表すブロック図である。
【図3】図2の特徴量差計算ブロックの構成を表す図である。
【図4】図2の更新ユニットの構成を表す図である。
【図5】注目格子点と移動範囲、注目点近傍領域との関係を説明する図である。
【図6】図4の更新ブロックの構成を表す図である。
【図7】本発明の実施例1に係る情報処理方法の処理の流れを表すフローチャートである。
【図8】特徴量差レジスタの初期化処理の動作を表すフローチャートである。
【図9】格子点を含む注目点近傍領域の特徴量差evcを計算する処理手順を説明する図である。
【図10】格子点座標の最適化処理の流れを表すフローチャートである。
【図11】注目点近傍領域のシフト処理を説明する図である。
【図12】注目点近傍領域のシフト処理を説明する図である。
【図13】注目点近傍領域のシフト処理を説明する図である。
【図14】レジスタがハニカム状に二次元配列されたシフト・レジスタの例を表す図である。
【図15】EGMの原理を説明する図である。
【符号の説明】
【0170】
1 情報処理装置
2 第1特徴ベクトル記憶手段
3 第2特徴ベクトル記憶手段
4 第1格子座標記憶手段
5 第2格子座標記憶手段
6 絶対評価量計算手段
7 絶対評価量記憶手段
8 相対評価量計算手段
9 第2格子最適化手段
10 キャッシュ・メモリ
11 絶対評価量読出手段
12 絶対評価量更新手段
13 座標取得手段
14 総合評価量計算手段
15 最適画素点検出手段
16 格子点座標更新手段
17 注目近傍領域更新手段
18 絶対評価量補充手段
21 画像メモリ
22 特徴量差計算ブロック
23 第1格子座標レジスタ
24 第2格子座標レジスタ
25 アービタ
26 評価値計算ユニット
27 上格子点座標レジスタ
28 下格子点座標レジスタ
29 左格子点座標レジスタ
30 右格子点座標レジスタ
31 特徴量差レジスタ
32 読出キャッシュ・メモリ
33 書込キャッシュ・メモリ
34 コントローラ
35 注目格子点座標レジスタ
36 更新ユニット
37 移動判定カウンタ
38 更新回数カウンタ
41 分子計算ブロック
42 分母計算ブロック
43 除算器
44 シフト・レジスタ
45 乗算器
46 累算器
47 自乗演算器
48 自乗演算器
49 累算器
50 セレクタ
51 レジスタ
52 乗算器
61 距離演算器
62 歪み演算器
63 評価値計算ブロック
64 ウィナー・テーク・オール回路(WTA回路)
65 座標更新ブロック
66 特徴量差データ・アドレス・レジスタ
67 更新ブロック
71 キャッシュ・メモリ
71a メモリ・セル
72 データ更新用シフト・レジスタ
73 セレクタ
75 レジスタ75
76 方向選択用セレクタ
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14