(57)【要約】      （修正有）【課題】変位計算を汎用グラフィックプロセッサ上で効率的に行え、且つ、主プロセッサのメモリと汎用グラフィックプロセッサのメモリとの間のデータ転送によるオーバーヘッドを減少させることができるパターン画像認識システムを提供する。【解決手段】パターン認識手段は、入力画像のコピーを複数個連結した連結入力画像を生成する連結入力画像生成手段と、標準画像のうち異なる複数個を連結した連結標準画像を生成する連結標準画像生成手段と、前記連結入力画像と前記連結標準画像との間で変形計算を行い、複数の変位関数からなる連結変位情報を求める変形計算手段と、前記連結変位情報に基づいて、前記入力画像と各標準画像との類似度を計算し、これに基づいて認識結果を出力する認識結果出力手段と、からなる。【選択図】図１
2008059418.tif 000002
【特許請求の範囲】
【請求項１】
入力画像を取り込む画像入力手段と、
複数の標準画像が記憶されている標準画像記憶手段と、
前記入力画像と前記標準画像との間で変形計算を行い、前記入力画像のパターン認識を行うパターン認識手段と、
を有するパターン画像認識システムであって、
前記パターン認識手段は、
前記入力画像を複数個連結した連結入力画像を生成する連結入力画像生成手段と、
前記標準画像のうち異なる複数個を連結した連結標準画像を生成する連結標準画像生成手段と、
前記連結入力画像と前記連結標準画像との間で変形計算を行い、複数の変位関数からなる連結変位情報を求める変形計算手段と、
前記連結変位情報に基づいて、前記入力画像と各標準画像との類似度を計算し、これに基づいて認識結果を出力する認識結果出力手段と、
からなることを特徴とするパターン画像認識システム。
【請求項２】
前記パターン画像認識システムは、汎用の主プロセッサと、多数のパイプラインを有する副プロセッサとからなり、
前記パターン認識手段のうち、少なくとも前記変形計算手段は副プロセッサにより実行されることを特徴とする請求項１記載のパターン画像認識システム。
【請求項３】
前記パターン認識手段のうち、少なくとも前記連結入力画像生成手段と連記連結標準画像生成手段とは主プロセッサにより実行され、
少なくとも前記連結入力画像及び前記連結標準画像は、主プロセッサのメモリから副プロセッサのメモリに転送されることを特徴とする請求項２記載のパターン画像認識システム。
【請求項４】
前記副プロセッサは、汎用グラフィックプロセッサであることを特徴とする請求項２又は３記載のパターン画像認識システム。
【請求項５】
前記変形計算手段は、複数の段階を有する繰り返し計算を行うものであり、計算の初期段階では前記入力画像及び前記標準画像として解像度が本来の解像度より低いものを用い、計算の段階が進むにつれて前記入力画像及び前記標準画像の解像度を上げて本来の解像度に近づけることを特徴とする請求項１乃至４いずれか記載のパターン画像認識システム。
【請求項６】
前記変形計算手段は、複数の段階を有する繰り返し計算を行うものであり、計算の段階が進むにつれて前記複数の標準画像の候補数を減らしていくことを特徴とする請求項１乃至５いずれか記載のパターン画像認識システム。
【請求項７】
前記パターン認識手段は、前記入力画像及び前記標準画像から輪郭又は輝度傾斜を用いて入力特徴画像及び標準特徴画像を生成する特徴画像生成手段を更に有し、
前記連結入力画像生成手段及び前記連結標準画像生成手段は、前記入力特徴画像及び前記標準特徴画像から連結入力画像及び連結標準画像を生成することを特徴とする請求項１乃至６いずれか記載のパターン画像認識システム。
【請求項８】
前記変形計算手段は、前記連結入力画像における各入力画像間の画像境界位置を表し前記連結入力画像と同サイズの参照画像を有し、前記変形計算において前記参照画像を演算に組み入れることで前記連結入力画像及び前記連結標準画像における各入力画像及び標準画像間の画像境界処理を行うことを特徴とする請求項１乃至７いずれか記載のパターン画像認識システム。
【請求項９】
画像入力手段により入力画像を取り込む画像入力工程と、
演算装置により、前記入力画像と標準画像記憶手段に記憶されている標準画像との間で変形計算を行い、前記入力画像のパターン認識を行うパターン認識工程と、
を有するパターン画像認識方法であって、
前記パターン認識工程は、
前記入力画像を複数個連結した連結入力画像を生成する連結入力画像生成工程と、
前記標準画像のうち異なる複数個を連結した連結標準画像を生成する連結標準画像生成工程と、
前記連結入力画像と前記連結標準画像との間で変形計算を行い、複数の変位関数からなる連結変位情報を求める変形計算工程と、
前記連結変位情報に基づいて、前記入力画像と各標準画像との類似度を計算し、これに基づいて認識結果を出力する認識結果出力工程と、
からなることを特徴とするパターン画像認識方法。
【請求項１０】
入力画像を取り込む画像入力工程と、
前記入力画像と標準画像記憶手段に記憶されている標準画像との間で変形計算を行い、前記入力画像のパターン認識を行うパターン認識工程と、
を有するパターン画像認識プログラムであって、
前記パターン認識工程は、
前記入力画像を複数個連結した連結入力画像を生成する連結入力画像生成工程と、
前記標準画像のうち異なる複数個を連結した連結標準画像を生成する連結標準画像生成工程と、
前記連結入力画像と前記連結標準画像との間で変形計算を行い、複数の変位関数からなる連結変位情報を求める変形計算工程と、
前記連結変位情報に基づいて、前記入力画像と各標準画像との類似度を計算し、これに基づいて認識結果を出力する認識結果出力工程と、
からなることを特徴とするパターン画像認識プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、顔画像認識、物体認識、手書き文字認識、指紋認識、臓器認識、車種認識といった、入力画像が変形を有することを予想される認識問題において、高速な変位計算を有するパターン画像認識システムに関するものである。
【背景技術】
【０００２】
認識処理においては、対象画像に含まれる変形成分の把握することが重要であり、変形の計算方法については複数の発明がなされている。しかし、それらの計算方法が複雑であるために、計算時間が多大であるという問題があった。また、専用装置の開発による計算時間の短縮も考えられるが、その場合には開発および生産時にコスト的な問題が残る。
【０００３】
変位を計算した後に認識を行おうとする試みは、既に幾つかの報告がある。例えば、特許文献１が挙げられる。しかし、これらの手法では、画像面積が大きくなった場合に変位計算のための所要時間が急激に増加するという問題がある。特許文献１においては、所要時間の短縮のために変位計算処理の前段階として、特徴抽出処理を行うことで画像の大きさ、つまり、入力次元数を小さくしている。ただし、処理すべき入力画像の枚数が増加した場合には、変位計算のための所要時間が膨大になる。よって、パターン画像認識問題における高速な変位計算の実現は重要な課題であり続けている。従来のパターン画像認識問題における変位計算は、計算機の中央演算装置（CPU）によって行われてきた。また、変位計算を行うための特殊ハードウェアを用いることも考えられるが、実装コストが大きくなるという問題点がある。
【特許文献１】特開平１１−９６３００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明では、近年、急激に発達しているコンピュータグラフィックスのための演算装置である汎用グラフィックプロセッサ（Graphics Processing Units: GPU, Visual Processing Units: VPU) を用いて、変位計算を高速に行うことを提案している。但し、汎用グラフィックプロセッサの性能を十二分に発揮するためには、変位計算の実装方法について新しい発想が必要である。
【０００５】
汎用グラフィックプロセッサは、多数の並列パイプライン処理、ビデオメモリへの高速なアクセス、高い動作周波数を有することが利点である。特に、前者２つの利点を最大限に活かすためには、データをなるべく大きな区分で主記憶装置からビデオメモリに転送しておいて、このデータに対して汎用グラフィックプロセッサによるパイプライン演算を適用する必要がある。もしも、データの区分を小さくすると、主記憶装置からビデオメモリへの転送回数が頻繁になってしまうためにオーバーヘッドが生じる。さらに、ビデオメモリ上のデータに対する汎用グラフィックプロセッサのパイプライン演算の効率性が低下することになる。
【０００６】
このような状況に鑑み、本発明は、パターン画像認識における変位計算を汎用グラフィックプロセッサで実行するシステムにおいて、前記変位計算を汎用グラフィックプロセッサ上で効率的に行え、且つ、主プロセッサのメモリと汎用グラフィックプロセッサのメモリとの間のデータ転送によるオーバーヘッドを減少させることができるパターン画像認識システムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
前記課題を解決するため、本発明は以下の構成を有する。
【０００８】
入力画像を取り込む画像入力手段と、複数の標準画像が記憶されている標準画像記憶手段と、前記入力画像と前記標準画像との間で変形計算を行い、前記入力画像のパターン認識を行うパターン認識手段と、を有するパターン画像認識システムであって、前記パターン認識手段は、前記入力画像を複数個連結した連結入力画像を生成する連結入力画像生成手段と、前記標準画像のうち異なる複数個を連結した連結標準画像を生成する連結標準画像生成手段と、前記連結入力画像と前記連結標準画像との間で変形計算を行い、複数の変位関数からなる連結変位情報を求める変形計算手段と、前記連結変位情報に基づいて、前記入力画像と各標準画像との類似度を計算し、これに基づいて認識結果を出力する認識結果出力手段と、からなることを特徴とするパターン画像認識システム。
【０００９】
画像入力手段により入力画像を取り込む画像入力工程と、演算装置により、前記入力画像と標準画像記憶手段に記憶されている標準画像との間で変形計算を行い、前記入力画像のパターン認識を行うパターン認識工程と、を有するパターン画像認識方法であって、前記パターン認識工程は、前記入力画像を複数個連結した連結入力画像を生成する連結入力画像生成工程と、前記標準画像のうち異なる複数個を連結した連結標準画像を生成する連結標準画像生成工程と、前記連結入力画像と前記連結標準画像との間で変形計算を行い、複数の変位関数からなる連結変位情報を求める変形計算工程と、前記連結変位情報に基づいて、前記入力画像と各標準画像との類似度を計算し、これに基づいて認識結果を出力する認識結果出力工程と、からなることを特徴とするパターン画像認識方法。
【００１０】
入力画像を取り込む画像入力工程と、前記入力画像と標準画像記憶手段に記憶されている標準画像との間で変形計算を行い、前記入力画像のパターン認識を行うパターン認識工程と、を有するパターン画像認識プログラムであって、前記パターン認識工程は、前記入力画像を複数個連結した連結入力画像を生成する連結入力画像生成工程と、前記標準画像のうち異なる複数個を連結した連結標準画像を生成する連結標準画像生成工程と、前記連結入力画像と前記連結標準画像との間で変形計算を行い、複数の変位関数からなる連結変位情報を求める変形計算工程と、前記連結変位情報に基づいて、前記入力画像と各標準画像との類似度を計算し、これに基づいて認識結果を出力する認識結果出力工程と、からなることを特徴とするパターン画像認識プログラム。
【００１１】
また、以下の実施態様を有する。
【００１２】
前記パターン画像認識システムは、汎用の主プロセッサと、多数のパイプラインを有する副プロセッサとからなり、前記パターン認識手段のうち、少なくとも前記変形計算手段は副プロセッサにより実行される。
【００１３】
前記パターン認識手段のうち、少なくとも前記連結入力画像生成手段と連記連結標準画像生成手段とは主プロセッサにより実行され、少なくとも前記連結入力画像及び前記連結標準画像は、主プロセッサのメモリから副プロセッサのメモリに転送される。
【００１４】
前記副プロセッサは、汎用グラフィックプロセッサである。
【００１５】
前記変形計算手段は、複数の段階を有する繰り返し計算を行うものであり、計算の初期段階では前記入力画像及び前記標準画像として解像度が本来の解像度より低いものを用い、計算の段階が進むにつれて前記入力画像及び前記標準画像の解像度を上げて本来の解像度に近づける。
【００１６】
前記変形計算手段は、複数の段階を有する繰り返し計算を行うものであり、計算の段階が進むにつれて前記複数の標準画像の候補数を減らしていく。
【００１７】
前記パターン認識手段は、前記入力画像及び前記標準画像から輪郭又は輝度傾斜を用いて入力特徴画像及び標準特徴画像を生成する特徴画像生成手段を更に有し、前記連結入力画像生成手段及び前記連結標準画像生成手段は、前記入力特徴画像及び前記標準特徴画像から連結入力画像及び連結標準画像を生成する。
【００１８】
前記変形計算手段は、前記連結入力画像における各入力画像間の画像境界位置を表し前記連結入力画像と同サイズの参照画像を有し、前記変形計算において前記参照画像を演算に組み入れることで前記連結入力画像及び前記連結標準画像における各入力画像及び標準画像間の画像境界処理を行う。
【発明の効果】
【００１９】
入力画像及び標準画像として複数個の画像を連結した連結入力画像及び連結標準画像を用いることで、個別の入力画像及び標準画像のデータを転送するのに比べて主プロセッサのメモリから副プロセッサ（汎用グラフィックプロセッサ）のメモリへのデータ転送回数を減らすことができ、データ転送によるオーバーヘッドを軽減し、パターン画像認識スピードを向上させることができる。これは、プロセッサ間のメモリデータ転送においては転送するごとにオーバーヘッドがあるので、同じデータ量を送るなら１度に転送するデータ量を増やして転送回数を減らした方が効率が良いことによる。さらに、連結入力画像及び連結標準画像を用いることで、個別の入力画像及び標準画像を用いるのに比べて一度に大量の演算が行えるので、汎用グラフィックプロセッサのパイプライン演算をより効率的に利用することができる。また、粗密探索法（請求項５）、漸進的候補削減法（請求項６）を併用することで、より効率的にパターン画像認識が行える。
【００２０】
メモリの効率的利用及び演算の効率化を考えた場合、前記連結入力画像及び前記連結標準画像内の各入力画像及び標準画像を密に配置する必要があるが、これらを密に配置してしまうと変形計算の際に隣接する入力画像又は標準画像にまで計算領域がはみ出してしまうことがある。これを避けるために、条件分岐処理を用いて計算領域がはみ出さないようにすることも考えられるが、通常、多数のパイプラインを有するプロセッサは条件分岐処理を行うと演算速度が減少してしまう。本発明の請求項８の構成を採用すれば、条件分岐処理ではなく演算処理により画像境界処理を行えるので、汎用グラフィックプロセッサ等の多数のパイプラインを有するプロセッサにおいて効率的に演算が行える。
【発明を実施するための最良の形態】
【００２１】
本発明の最良の実施形態について説明する。図１は、本実施形態の処理手順の概要である。スキャナ等の入力装置から画像データを読み込み（ステップS1）、読み込んだ画像から対象物体の切り出しや雑音除去を行い（ステップS2）、入力画像を複数回数連結して連結入力画像を作成し（ステップS3）、候補カテゴリを代表する複数の標準画像を連結して連結標準画像を作成し（ステップS4）、変形情報を格納するための変位関数を連結して連結変位関数画像（連結変位情報）を作成し（ステップS5）、複数のパイプラインを有した演算装置を用いて連結入力画像と連結標準画像の間で変形計算を行い、得られた結果を連結変位画像（連結変位情報）に保存し（ステップS6）、連結変位情報を考慮して入力画像と各標準画像との類似度を計算し、これに基づいて認識結果を求め（ステップS7）、出力デバイスに認識結果を表示、または、記録デバイスに記録する（ステップS8）。
【００２２】
図２に、連結入力画像、連結標準画像、連結変位関数（連結変位情報）の一例を示す。図２(a)は、同一の入力画像を連結した連結入力画像である。但し、複数の入力画像を含む連結画像の作成も本発明の自然な適用として扱うことができる。図２(b)は、入力画像と類似した形状を有する標準画像を連結した連結標準画像である。また、図２(c)の変形格子は、連結入力画像と連結標準画像の間の変位計算結果（連結変位情報）を示している。格子上の標準画像の形状が、入力画像の形状により接近しているのが分かる。
【００２３】
以下、図３及び図４を用いて、本実施形態についてより詳細に説明する。
１．主記憶装置への標準画像集合の複写
補助記憶装置等に蓄積されている標準画像の集合が主記憶装置（主プロセッサのメモリ）に複写される。後の粗密探索戦略の準備として、個々の標準画像はもともとの解像度に加えてより低解像度な画像も包含している。また、特徴画像を用いる場合には、もともとの輝度画像に加えて、画像中の物体輪郭などに着目した多解像度の方向特徴画像を作成しておく必要があり、以後、入力画像として、または、その一部として用いることになる（特開平１１−９６３００参照）。
２．入力画像の取得
スキャナ装置やカメラ装置といった入力装置、または、ネットワークを介した入力装置を用いて入力画像を取得して、主記憶装置（主プロセッサのメモリ）に複写する。
３．入力画像の低解像度処理
粗密探索に備えて、入力画像から複数の低解像度画像を作成しておく。また、特徴画像を用いる場合には、標準画像と同様に、多解像度の方向特徴画像を作成しておく必要がある。
４．大分類による標準画像の絞込み
主演算装置（主プロセッサ）上にて、適当な解像度の標準画像集合と入力画像の間で距離計測を行い、小さな距離を与える標準画像を選択する。ここで用いる距離計測法としては、ユークリッド距離や単純類似度といった計算量が比較的少ないものを用いるのが望ましい。
５．連結画像の作成
候補となる標準画像を連結した連結標準画像を、主演算装置（主プロセッサ）を用いて主記憶装置（主プロセッサのメモリ）上に作成する。同様に、入力画像を連結した連結入力画像を作成する。両画像間の対応付けを画素単位で表現した変位関数画像を初期化しておいて、これらを連結した連結変位関数画像（連結変位情報）も作成しておく。変位は水平方向と垂直方向が仮定されるので、２枚の変位関数画像を想定することになる。
６．第２記憶装置（副プロセッサのメモリ）への連結画像の転送
主記憶装置（主プロセッサのメモリ）上から第２記憶装置（副プロセッサのメモリ）に連結入力画像、連結標準画像および連結変位関数画像（連結変位情報）を転送する。最初は、低解像度な連結画像を転送することとする。
７．変位計算の実行
複数のパイプラインを有する演算装置（副プロセッサ）を用いて、連結入力画像と連結標準画像の間の変位を計算する。ここでの計算では２つの原則に従いながら最も適切な変位を得ることとする。一つ目の原則は、計算される変位関数を考慮して入力画像と標準関数の対応付けの補正、即ち、変位計算を行うことにより、両者の相違度（距離）が小さくなることである。２つ目の原則は、変位関数が表現する対応付けはなるべく自然であるということである。ここで自然とは、例えば、隣接する画素間の対応付け補正量は類似している、といったものである。特開平１１−９６３００に見られるように、ここでの処理を計算手続き的に記述することは容易である。一般に、反復演算の形式で実行することができる。但し、連結画像上の画像間の境界においては、２つ目の原則で述べた近接変位量の類似を課する必要はない。
【００２４】
一定の反復計算の実施後、または、更新毎の改善度合いがある基準を下回るようになることを目処として、与えられた解像度での変位計算を終了する。
８．主記憶（主プロセッサのメモリ）への連結変位関数画像（連結変位情報）の転送
計算により得られた連結変位関数画像（連結変位情報）を主記憶に転送する。
９．より高解像度な対応付け
もしもより解像度な画像が準備されている場合には、手順５に戻り、より高解像度な連結入力画像、連結標準画像、および、連結変位関数画像（連結変位情報）を作成する。但し、連結高解像度に関しては、既に得た変位関数に基づいてより解像度な変位関数を初期化して、これらから連結変位関数画像（連結変位情報）を作成することとする。有望でない候補標準画像を段階的に削減していくために、各解像度にて得られた変位関数を考慮して候補標準画像と入力画像の相違度を測定して、下位の標準画像を候補から外すことも可能である。
１０．認識結果の決定
手順８で得られた連結変位関数（連結変位情報）を考慮して、現解像度にて標準画像と入力画像の相違度測定を行い、最も低い相違度を与える標準画像を選出する。この標準画像が属する分類が、入力画像の分類として判断される。
【００２５】
変形例１．上記手順１０にて、最も低い相違度を与える標準画像の分類だけでなく、その他の上位標準画像の分類も加味することも可能である。さらに、特開平１１−９６３００に見られるように、輝度に関する平均、分散といった統計量、または、変位量に関する統計量を加味した統計的識別器の利用も可能である。
変形例２．上記手順１から３において、主記憶装置上に多解像度な標準画像、入力画像を準備するだけでなく、第２記憶装置（副プロセッサのメモリ）上にも配置しておくことは更なる高速化に有望である。何故ならば、連結画像の作成処理が、複数のパイプラインを有する演算装置を用いて実現できることに加えて、連結画像を主記憶装置（主プロセッサのメモリ）から第２記憶装置（副プロセッサのメモリ）に転送処理が不要になるからである。
変形例３．複数のパイプラインを有する演算装置を汎用の主演算装置として用いることにより、主演算装置と複数のパイプラインを有する演算装置を一元化すること、および、主記憶装置と第２記憶装置を一元化することができる。
【００２６】
以下、本実施形態における「１．粗密探索を用いた変位計算」、「２．漸進的候補削減法」、「３．標準画像並列変位計算」についてさらに詳細に説明する。
【００２７】
−１．粗密探索を用いた変位計算−
本実施形態における変位計算は、1988 年に提案されたステレオ対応問題のための正則化手法に基づいている[24]。ここでは、入力文字とプロタイプのそれぞれをf(x,y), g(x,y)で表現する。さらに、g上の座標(x,y)における変位量を変位関数(u(x,y),v(x,y))で表現する（図５）。すると、変位関数の最適化問題は、以下に示す汎関数Eに関する最小化問題として再定式化される。
【００２８】
【数１】
2008059418.tif 000003
ここで、汎関数P は計算された変位を考慮するユークリッド距離を表し、汎関数S は変位関数(u,v)に対する滑らかさの制約項となっている。また、λは、関数Sの重みを調節する正則化係数である。汎関数Eの最小化する変位関数(u,v)は、変分法の枠組みから以下の反復計算式で求めることができる。
【００２９】
【数２】
2008059418.tif 000004
式(4)および(5)は、右辺第2項にてf、fxおよびfyのサブピクセル値を必要としている。サブピクセル値の算出は、周囲の４点の画素値をもとに線形補間を用いて行う。ここでの計算は、変位計算の中でも負荷の大きいものとなっている。
本実施形態では、安定性の向上のために、式(4)および(5)の代わりに、以下に示す反復計算式が用いられる[20,21]。
【００３０】
【数３】
2008059418.tif 000005
反復計算の繰り返し回数の削減と局所解への落ち込み回避のために、粗密探索を用いることは非常に有望である[25,26]。ここでは、粗密探索の段階数をNとする。低周波フィルタを用いてサンプリングを行い、各段階n(1≦n≦N)において、一辺が原画像の1／(2N-n)倍の平滑化入力画像fnおよび標準画像gnを作成する。続いて、最も解像度が低い第1段階から変位計算を行い、得られた変位関数に基づいて次の段階の初期値を決定する。最終的に、原画像と同じ解像度を持つ変位関数が得られる。
【００３１】
−２．漸進的候補削減法−
本実施形態では、入力画像と複数の標準画像の間の変位を計算した後に、ユークリッド距離（汎関数Ｐ）に基づいて最近傍識別を行う。ここで注意すべき点は、粗密探索の段階が進むにつれて変位計算に要する計算負荷が急激に増加するということである。そこで、大分類の結果に基づいて第1段階では上位L1個の標準文字に対してのみ変位計算を行う。以降のn段階では、n-1段階にて得られた変位に基づいて距離計算を行い、上位Ln(Ln≦Ln-1)個の標準文字のみに対して変位計算を行うこととする。このようにして、認識精度を落とすことなく計算負荷を抑えることができる[23]。
【００３２】
−３．標準画像並列変位計算−
従来の変形アプローチの問題点の一つはその計算負荷にあるので、計算時間を劇的に短縮するための試みは大変重要である。そこで、本実施形態では、GPU の特性と我々の提案してきた認識手法の特性に基づいた、標準画像並列変位計算法を提案する。既に述べたように、GPU の特性は、高速なビデオメモリへのアクセス、高いコア周波数、複数のプログラマブルパイプラインの実装である。このようなハードウェアアーキテクチャは、式(8) および(9)に示される局所並列演算を実装するのには適している。よって、上述した認識手法をGPU 上に実装することは、大変有望と考えられる。
【００３３】
しかしながら、ここで改めてGPU の特性を考える必要がある。GPU 上のフラグメントプロセッサーは、専用ビデオメモリ上のデータに対しては、高速なアクセス性能およびパイプライン演算性能を有する。但し、GPU はメインメモリ上のデータに直接アクセスすることができないので、事前にメインメモリからビデオメモリ上にデータを転送しておく必要がある。先述した漸進的候補削減法では、1文字の認識のために、各段階において、入力画像fnの転送に加えて、Ln個の標準画像gn,l(1≦l≦Ln)および変位関数(ul,vl)の転送を行う必要がある。結果的に、一つの入力画像を識別するために、主記憶からビデオメモリへ
【００３４】
【数４】
2008059418.tif 000006
の転送を行うことになる。ここで注意すべきことは、メインメモリからビデオメモリへの頻繁な転送は、GPU計算におけるボトルネックとなる可能性がある、ということである。
【００３５】
そこで、本実施形態ではGPUを用いた標準画像並列変位計算法(PPDC-GPU)を提案する。ここでは、各段階nにおいて、入力画像fn, Ln個の標準画像gn,l、および、変位関数(ul,vl)をタイル状に並べた巨大な画像プレート（連結画像）をメインメモリ上で作成し、ビデオメモリ上に一括転送する。その後、この画像プレート上の複数の入力画像と標準画像の間で、GPUを用いて同時並列的に変位計算を行うこととする(図６)。これにより、GPUのメモリアクセス効率、および、パイプライン効率が劇的に改善できることが期待される。また同様の転送方式は、計算済みの変位関数をビデオメモリからメインメモリに戻す際にも用いられる。
【００３６】
反復演算を行う際には、ビデオメモリ上に記憶された変位関数(u[t],v[v]) に基づいて得られた変位関数(u[t+1],v[v+1])を再びビデオメモリ上に記憶して、次の計算のための参照値として用いる必要がある。このような反復計算をGPU上で実行するために、高速性および汎用性が高いFramebuffer Object
(FBO) 拡張が近年提供されており[2]、本実施形態においてもこの拡張体系を利用している。さらに、OpenGL拡張の一つであるGL ARB texture floatによって32bitの浮動小数点演算が可能であるために、計算精度の観点からCPUと比較しても遜色はない。
続いて、反復計算式の実装詳細について述べる。式(6) および(7) で示される変位関数の平均計算は、異なる標準画像に対応する領域境界を越えて適用してはならない。そこで、各座標における上下左右に近接する画素の位置、または、有無をビデオメモリ上に事前に記憶させることとする。一方、式(8)および(9)については、(x+u,y+v)によって別の標準画像領域にアクセスするのを避けるために、境界位置に基づいたクランプ処理が必要となる。この処理については、後述の「―画像境界処理―」に説明されている。
【００３７】
標準画像並列変位計算法と漸進的候補削減法を用いることは、GPUの性能を有効活用するためにも有意義である。何故ならば、画像サイズが小さい初期段階ではプレート上に配置される画像枚数は膨大であるが、画像サイズが大きい後期段階では画像枚数が少数になるので、必要になるビデオメモリと計算負荷が急激に増加することを避けられるからである。
【００３８】
−計算機シミュレーション−
本実施形態によるGPUの実装効果を明らかにするために、NIST手書き文字データベース(HSF7)を用いた認識実験を行う。データベースには60,000以上の手書数字が含まれており、各カテゴリ毎に約6000サンプルが収められている。この中から独立ランダム抽出を行い、8000文字の訓練用集合（800文字/カテゴリ）および8000文字の評価用集合（800文字/カテゴリ）を作成した。粗密探索時の段階数は3としている。前処理として、すべての文字画像は32×32画素に縮小されており、画像上の文字は28×28画素になるように大きさの正規化、および、位置の正規化が行われている。さらに、3×3画素の領域で平滑化処理を行っている。第1段階の画像サイズは8×8画素、第2段階では16×16画素、第3段階では32×32画素としている。第n段階におけるλnの値は、それぞれ0.10, 0.10および0.50とした。また、各段階における反復回数は50としている。大分類では、入力画像と標準画像から生成された最も低解像度な画像間のEuclidean距離を用いた。これらの設定は、事前に行った小規模の実験結果に基づいて経験的に決められている。本実験では、3.2GHzのCPU、1GByteのDDR2メモリ、NVIDIA製グラフィックボードGT-7800 (ビデオメモリ128MByte) を使用している。なお、開発環境としてMicrosoft Visual C++ .NET 2003 およびNVIDIA Cg
Toolkt 1.4 を用いている[1]。
【００３９】
図２は本実施形態のPPDC-GPUの最終段階での実行例を示している。図２(a)および図２(b)はそれぞれ入力画像プレート（連結入力画像）と標準画像プレート（連結標準画像）を表している。標準画像プレートは前段階の変位計算結果に基づいて選択された上位標準文字から構成されている。一方、入力画像プレートは、同じ入力文字がから構成されている。図２(c)は、本実施形態により与えられた変位と変形された標準文字を示している。標準文字領域の境界で変位が不連続になっていること、および、変形後の標準文字の形状が入力文字に接近していること、が確認される。
【００４０】
図７(a)に、全ての段階で標準文字の個数Lnを一定値とした場合の、提案するPPDC-GPUの一文字辺りの認識に要する計算時間を示す。ここではCPUを用いた従来手法[23]、GPUを用いて画像プレートを作成せずに一文字毎の変位計算を行っている標準画像直列変位計算(prototype-sequential displacement computation with GPU; PSDC-GPU)を、比較対象として採用している。CPU を用いた従来手法と比較して、PSDC-GPUでは計算時間が約20%に削減されている。一方、PPDC-GPU では計算時間が10%以下になっており、大幅な短縮効果が確認される。特に、L≧200においては、7%以下の短縮効果が得られている。参考のために、図７(b)に認識率を示す。横軸はLnを表し、縦軸は認識率を表している。Lの値に400,
500および600を用いた場合に、最高認識率99.21%が得られた。この値は、変位を計算せずに単純相関によって得られた同データセットに対する最高認識率96.5%を上回るものであった。
【００４１】
最後に、表1に示される3つの実装手法における個々の処理時間について検討を行う。PSDC-GPUと比較して、PPDC-GPUでは変位計算のための所要時間が大幅に減少していることが確認できる。この結果は、プレートを用いることがパイプライン演算を効率化できることを支持している。但し、PPDC-GPUにおける主記憶とビデオメモリ間の時間節約効果はそれほど高くなかった。さらに、PPDC-GPUではプレートを作成するために90msecを要しており、これらの合計時間173 msecは全計算時間の34% を占めている。
【００４２】
【表１】
2008059418.tif 000007
【００４３】
−画像境界処理−
反復計算式において、画像境界を越えての補外が起こらないようにする必要がある。そのために、各画素が属する画像領域における水平および垂直方向の画像境界位置を表す２枚の参照画像を準備することが考えられる。画像境界位置を表す参照画像例を図８に示す。ここでは、左上が座標（１，１）であることを想定しており、右側が水平方向の正方向、下側が垂直方向の正方向である。また、画像サイズは水平垂直方向ともに８画素とする。Ch(x,y)は水平方向の画像終端位置を表しており、左上の画像、および、その下の画像領域においては、８を代入しておく。また、両者の右側に隣接する画像では、１６を代入しておく。一方、Cv(x,y)は垂直方向の画像終端位置を表している。
【００４４】
これらの値を用いて、例えば、式（４）及び（５）における
【００４５】
【数５】
2008059418.tif 000008
の代わりに、
【００４６】
【数６】
2008059418.tif 000009
を計算することとする。ここで、clamp(a,b,c)とは、aの値をb以上c以下の範囲で制限することを表している。上記の画像を作成しなくても例えば 8*(int)(x/8)+8
といった計算によって各座標(x,y)から水平および垂直方向の画像終端位置を調べることは可能であるが、上記のような参照画像を作成しておけば、計算時間の節約が可能である。
【００４７】
また、変位関数の平均処理（式（８）及び（９））においても、画像境界を越えての適用は望ましくない。これについても、同様に図９のような参照画像を準備することができる。参照画像w1は、画素の左側隣接画素の有無を１または０で表している。同様に、参照画像w2は右側隣接画素の有無、w3は上側隣接画素の有無、w4は下側隣接画素の有無を表している。これらの値を重みとして用いることで、判定文など用いることなしに、次式を用いて変位関数の平均処理が行える。
【００４８】
【数７】
2008059418.tif 000010
【００４９】
以上、本発明の実施形態の一例を説明したが、本発明はこれに限定されるものではなく、特許請求の範囲に記載された技術的思想の範疇において各種の変更が可能であることは言うまでもない。例えば、連結入力画像生成手段及び連結標準画像生成手段を主プロセッサ（CPU）で実行せずに、事前に副プロセッサ（汎用グラフィックプロセッサ）のメモリ上に入力画像や標準画像を転送しておいて、副プロセッサにより連結入力画像及び連結標準画像を生成しても良い。また、例えばノートＰＣなどでみられるような、主プロセッサと副プロセッサ（汎用グラフィックプロセッサ）とでメモリが共有されるようなシステムにも本発明は適用できる。
【００５０】
−参考文献−
[1] R.
Fernando and M. J. Kilgard. The Cg Tutorial : the definitive guide to
programmable real-time graphics. Addison-Wesley, 2003.
[2] J. D.
Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J.
Purcell. A survey of generalpurpose computation on graphics hardware. In
Eurographics 2005, State of the Art Reports, pages 21-51, August 2005.
[3] R. Yang
and M. Pollefeys. Multi-resolution real-time stereo on commodity graphics
hardware. In Proceedings of International Conference of Computer Vision and
Patter Recognition, pages 211-217, 2003.
[4] J. Fung
and S. Mann. Using multiple graphics cards as a general purpose parallel
computer : Applications to computer vision. In Proceeding of International
Conference of Pattern Recognition, volume 01, pages 805-808, 2004.
[5] K
Moreland and E. Angel. The FFT on a GPU. In Proc. of SIGGRAPH/Eurographics
Workshop on Graphics Hardware, pages 112-119, 2003.
[6] J.
Kruger and R. Westermann. Linear algebra operators for GPU implementation of
numerical algorithms. In Proc. SIGGRAPH 2003, pages 908-916, 2003.
[7] J. Bolz,
I. Farmer, and E. G. P. Schroder. Sparse matrix solvers on the GPU: Conjugate
gradients and multigrid. In Proc. SIGGRAPH 2003, pages 917-924, 2003.
[8] B.
Widrow. The rubber mask technique - I. pattern measurement and analysis.
Pattern Recognition, 5(3):175-197, March 1973.
[9] D.J. Burr.
A dynamic model for image registration. In Proc. IEEE Comput. Soc. Conf.
Pattern Recognition and Image Processing, pages 17-24, August 1979.
[10] M.
Kass, A. Witkin, and D. Terzopoulos. Snakes: active contour models.
International Journal of Computer Vision, 1:321-331, 1988.
[11] R.
Bajcsy and S. Kovacic. Multiresolution elastic matching. Computer Vision,
Graphics, and Image Processing, 46(1):1-21, 1989.
[12] A.L.
Yuille. Deformable templates for face recognition. Journal of Cognitive
Neuroscience, 3(1):59-70, 1991.
[13] M.
Lades, J.C. Vorbruggen, J. Buhmann, J. Lange, C.v.d. Malsburg, R.P. Wurtz, and
W. Konen. Distortion invariant object recognition in the dynamic link
architecture. IEEE-C, 42(3):300-311, March 1993.
[14] A.K.
Jain, Y. Zhong, and S. Lakshmanan. Object matching using deformable template.
IEEE Trans. PAMI, 18(3):267-278, March 1996.
[15] D.J.
Burr. Elastic matching of line drawings. IEEE Trans. PAMI, 3(6):708-713,
November 1981.
[16]
T.Wakahara. Shape matching using LAT and its application to handwritten numeral
recognition. IEEE Trans. PAMI, 16(6):618-629, June 1994.
[17] A.
Daffertshofer and H. Haken. A new approach to recognition of deformed patterns.
Pattern Recognition, 27(12):1697-1705, December 1994.
[18] M.
Revow, C. K. I. Williams, and G. E. Hinton. Using generative models for
handwritten digit recognition. IEEE Trans. PAMI, 18(6):592-606, 1996.
[19] A.K.
Jain and D. Zongker. Representation and recognition of handwritten digits using
deformable templates. IEEE Trans. PAMI, 19(12):1386-1391, December 1997.
[20] Y.
Mizukami, K. Koga, and T. Torioka. A handwritten character recognition system
using hierarchical extraction of displacement. IEICE, J77-D-II(12):2390-2393,
December 1994.
[21] Y.
Mizukami and K. Koga. A handwritten character recognition system using
hierarchical displacement extraction algorithm. In Proc. 13th Int. Conf.
Pattern Recognition, volume 3, pages 160-164, 1996.
[22] Y.
Mizukami. A handwritten Chinese character recognition system using hierarchical
displacement extraction based on directional features. Pattern Recognition
Letters, 19:595-604, 1998.
[23] Y.
Mizukami, T. Sato, and K. Tanaka. Handwritten digit recognition by hierarchical
displacement extraction with gradual prototype eliminations. In Proc. 15th Int.
Conf. Pattern Recognition, volume 3, pages 339-342, 2000.
[24] R.
March. Computation of stereo disparity using regularization. Pattern
Recognition Letters, 8(3):181-188, March 1988.
[25] F.
Glazer. Multilevel relaxation in low-level computer vision. Multiresolution
Image Processing and Analysis, pages 312-330, July 1984.
[26] N.
Yokoya. Dense matching of two views with large displacement. In Proceedings of
First IEEE International Conference on Image Processing, volume I, pages 213-217.
IEEE Computer Society Press, November 1994.
【図面の簡単な説明】
【００５１】
【図１】本発明の実施形態の処理手順の概要である。
【図２】標準画像並列変位計算法における実行例を示す図である。
【図３】本発明の実施形態のシステム図である。
【図４】本発明の実施形態のデータ及び計算状態を示す図である。
【図５】入力画像ｆと標準画像ｇと変位関数ｕ，ｖとの関係を示す図である。
【図６】主プロセッサと副プロセッサとの間のデータ転送の概略図である。
【図７】本発明の実施形態によるパターン認識結果と他の手法の結果とを比較したグラフである。
【図８】反復計算における画像境界位置を表す参照画像例である。
【図９】変位関数の平均処理における参照画像例である。
【図１】
2008059418.tif 000011
【図２】
2008059418.tif 000012
【図３】
2008059418.tif 000013
【図４】
2008059418.tif 000014
【図５】
2008059418.tif 000015
【図６】
2008059418.tif 000016
【図７】
2008059418.tif 000017
【図８】
2008059418.tif 000018
【図９】
2008059418.tif 000019