(57)【特許請求の範囲】
【請求項１】
照合対象の第１パターンのデータである第１パターンデータおよび第２パターンのデータである第２パターンデータを取得するパターンデータ取得部と、
前記第１パターンデータもしくは前記第２パターンデータのサイズによって定まる複数のインデックスおよび前記インデックス毎に対応付けられた値が記憶されている記憶部と、
前記第１パターンデータと前記第２パターンデータとの位相差を所定の分割数で量子化した離散値を求める量子化演算部と、
前記量子化演算部が求めた各離散値からインデックスを求めるインデックス計算部と、
前記インデックス計算部が求めた各インデックスに等しいインデックスに対応する値を前記記憶部より読み出し、読み出した値を加算することで前記第１パターンデータと前記第２パターンデータとの位相限定相関関数の値を求める相関関数演算部と、
前記相関関数演算部が求めた前記位相限定相関関数の値が極大を取る極大値の大きさおよび位置により、前記第１パターンと前記第２パターンとの照合を行う照合部と
を備えることを特徴とするパターン照合装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、空間周波数特性に基づいて、音声（１次元）、指紋（２次元）、立体（３次元）などのパターン照合を行うパターン照合装置に関するものである。
【背景技術】
【０００２】
近年、入退室管理、コンピュータ端末や銀行の金融端末へのアクセス管理などの個人認識を必要とする分野において、これまでの暗証番号やＩＤカードに代わり、音声照合装置や指紋照合装置が採用されるようになっている。
【０００３】
このような照合においては、例えば、照合対象の指紋画像と登録されている指紋画像との比較をする技術が用いられている。例えば、２つの画像データの位相限定相関関数により照合を行う技術が提案されている（特許文献１参照）。この技術では、比較する２つの画像の離散的フーリエ変換データを合成し、合成した合成フーリエ変換データに対して離散的逆フーリエ変換を実施し（位相限定相関関数を求め）、相関成分の強度が高い上位の強度に基づいて照合を行う。この位相限定相関法と呼ばれる照合技術は、指紋などの生体情報をはじめとする各種画像に対して高い識別性能を持った画像マッチング技術である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３９３００６７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した照合技術では、照合対象データ，登録データ，および合成データに対してフーリエ変換を行うので、演算コストが高くなるという問題があった。
【０００６】
本発明は、以上のような問題点を解消するためになされたものであり、フーリエ変換を用いた照合技術における演算コストが低減できるようにすることを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係るパターン照合装置は、照合対象の第１パターンのデータである第１パターンデータおよび第２パターンのデータである第２パターンデータを取得するパターンデータ取得部と、第１パターンデータもしくは第２パターンデータのサイズによって定まる複数のインデックスおよびインデックス毎に対応付けられた値が記憶されている記憶部と、第１パターンデータと第２パターンデータとの位相差を所定の分割数で量子化した離散値を求める量子化演算部と、量子化演算部が求めた各離散値からインデックスを求めるインデックス計算部と、インデックス計算部が求めた各インデックスに等しいインデックスに対応する値を記憶部より読み出し、読み出した値を加算することで第１パターンデータと第２パターンデータとの位相限定相関関数の値を求める相関関数演算部と、相関関数演算部が求めた位相限定相関関数の値が極大を取る極大値の大きさおよび位置により、第１パターンと第２パターンとの照合を行う照合部とを備える。
【発明の効果】
【０００８】
以上説明したことにより、本発明によれば、フーリエ変換を用いた照合技術における演算コストが低減できるという優れた効果が得られる。
【図面の簡単な説明】
【０００９】
【図１】図１は、本発明の実施の形態におけるパターン照合装置の構成を示す構成図である。
【図２】図２は、分割数Ｍ＝４とした量子化について説明するための説明図である。
【図３】図３は、信号長をＮ＝１２８，量子化の分割数をＭ＝２とした場合の位相限定相関関数の比較を示す特性図である。
【図４】図４は、信号長をＮ＝１２８，量子化の分割数をＭ＝４とした場合の位相限定相関関数の比較を示す特性図である。
【図５】図５は、信号長をＮ＝１２８，量子化の分割数をＭ＝８とした場合の位相限定相関関数の比較を示す特性図である。
【図６】図６は、信号長をＮ＝１２８，量子化の分割数をＭ＝１６とした場合の位相限定相関関数の比較を示す特性図である。
【図７】図７は、信号長をＮ＝１２８，量子化の分割数をＭ＝３２とした場合の位相限定相関関数の比較を示す特性図である。
【図８】図８は、信号長をＮ＝１２８，量子化の分割数をＭ＝６４とした場合の位相限定相関関数の比較を示す特性図である。
【図９】図９は、信号長をＮ＝１２８，量子化の分割数をＭ＝１２８とした場合の位相限定相関関数の比較を示す特性図である。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について図を参照して説明する。図１は、本発明の実施の形態におけるパターン照合装置の構成を示す構成図である。このパターン照合装置は、パターンデータ取得部１０１、記憶部１０２、量子化演算部１０３、インデックス計算部１０４、相関関数演算部１０５、照合部１０６を備える。
【００１１】
パターンデータ取得部１０１は、照合対象の第１パターンのデータである第１パターンデータおよび第２パターンのデータである第２パターンデータを取得する。パターンは、例えば画像であり、パターンデータ取得部１０１は、例えば、スキャナやカメラである。また、パターンデータは例えば音声であり、パターンデータ取得部１０１は録音機である。
【００１２】
記憶部１０２は、第１パターンデータもしくは第２パターンデータのサイズによって定まる複数のインデックスおよびインデックス毎に対応付けられた値を記憶している。記憶部１０２に記憶している値は、予め求められている。量子化演算部１０３は、第１パターンデータと第２パターンデータとの位相限定相関関数における位相差を所定の分割数で量子化して離散値を求める。
【００１３】
インデックス計算部１０４は、量子化演算部１０３が求めた各離散値から各々のインデックスを求める。相関関数演算部１０５は、インデックス計算部１０４が求めた各インデックスに等しいインデックスに対応する値を記憶部１０２より読み出し、読み出した値を加算することで第１パターンデータと第２パターンデータとの位相限定相関関数の値を求める。照合部１０６は、相関関数演算部１０５が求めた位相限定相関関数の値が極大を取る極大値の大きさおよび位置により、第１パターンと第２パターンとの照合を行う。また、照合部１０６は、照合結果を、図示しない表示部などに表示出力する。
【００１４】
ここで、極大値の位置を限定して上述した計算を実施することで、計算量が低減でき、照合を効率的に実施することができる。例えば、指紋などによる生体認証の場合、パターンデータである画像を正規化して２つの画像位置を合わせてから上述した処理をする場合が多い。この場合、極大値の位置は原点付近となるので、極大値の位置を限定して計算することが可能である。
【００１５】
以下、より詳細に説明する。はじめに、１次元信号の場合について説明する。
【００１６】
まず、位相限定相関関数の定義について説明する。信号長をＮとし、時間領域のインデックスをｎとし（ｎ＝０，１，２，・・・，Ｎ−１の整数値）、周波数領域のインデックスをｋとする（ｋ＝０，１，２，・・・，Ｎ−１の整数値）。また、第１パターンデータである一方の入力信号１×１（ｎ）とこの離散フーリエ変換Ｘ１（ｋ）とし、照合対象となる第２パターンデータである他方の入力信号２×２（ｎ）とこの離散フーリエ変換Ｘ２（ｋ）とすると、各々は、以下の式（１），式（２）で示されるものとなる。また、振幅と位相は、以下の式（３），式（４）となる。
【００１７】
【数１】
0006574699.tif 000002
【００１８】
なお、Ａ１（ｋ）はＸ１（ｋ）の振幅、θ１（ｋ）はＸ１（ｋ）の位相を表す。また、Ａ２（ｋ）はＸ２（ｋ）の振幅、θ２（ｋ）はＸ２（ｋ）の位相を表す。
【００１９】
従って、第１パターンデータと第２パターンデータとの位相限定相関関数は、以下の式（５）となる。
【００２０】
【数２】
0006574699.tif 000003
【００２１】
なお、「θ（ｋ）＝θ１（ｋ）−θ２（ｋ）」であり、２つのパターンデータの位相差を表している。ただし、位相の循環性（位相は０〜２πの区間で循環する）については無視した表現となっている。
【００２２】
次に、量子化演算部１０３で上述した位相限定相関関数における位相差θ（ｋ）を量子化することにより、離散フーリエ変換の式が簡単化することについて説明する。位相差を量子化することにより、式（５）のΣの中身を離散化した値に表現できる。Σの中身に着目すると以下の式（６）ように変形することができる。ここで、式（６）の右辺の一部である以下の式（７）で示される部分は、離散値となる。
【００２３】
【数３】
0006574699.tif 000004
【００２４】
従って、式（６）の右辺の「ｅjθ(k)」を量子化した離散値として表現すれば、式（６）全体が離散値として表現できるようになる。このようにすることで、式（６）は、複素数の加算、乗算、三角関数の演算などが含まれる式であったが、単純な複素数の加算のみで計算できるようになる。
【００２５】
「ｅjθ(k)」の量子化分割数は任意に決めることができるが、計算効率を考えると信号長ＮもしくはＮの約数で分割するとよい。ここで、スケーリング係数ｓと量子化の分割数Ｍとにより、Ｎ＝ｓＭとする。Ｍ状態に量子化された位相をθｑ（ｋ）とおくと、位相限定相関関数は以下のように変形できる。
【００２６】
【数４】
0006574699.tif 000005
【００２７】
ここで、ｍ（ｋ）は、１，２，・・・，Ｍ−１の値を取る。また、「ｅjθq(k)」は、以下の式（９）で示されるものとする。
【００２８】
【数５】
0006574699.tif 000006
とする。
【００２９】
ここで、以下の式（１０）は、Ｎ個の状態しか取りえないため、予め計算しておき、計算結果を記憶部１０２に記憶し、記憶している計算結果を相関関数演算部１０５で用いることで、三角関数などの計算が不要になる。
【００３０】
【数６】
0006574699.tif 000007
【００３１】
予めの計算については、以下のようなＬＵＴ（ＬｏｏｋＵｐＴａｂｌｅ）用いればよい。
【００３２】
【数７】
0006574699.tif 000008
【００３３】
記憶部１０２に、式（１１）の値を予め計算しておき、この値をインデックスｌ毎に、記憶部１０２に記憶しておけばよい。式（１１）によるＬＵＴを利用して式（８）を書きなおすと以下のようになる。なお、式（１２）において、ｍｏｄ（Ａ，Ｂ）はＡをＢで割ったときの余りを表す。
【００３４】
【数８】
0006574699.tif 000009
【００３５】
相関関数演算部１０５は、インデックス計算部１０４が求めた各インデックスに等しいインデックスに対応する、憶部１０２に記憶してある式（１１）による値を用い、式（１２）により位相限定相関関数の値を求める。このように、実施の形態によれば、位相限定相関関数の値が、加算により求めることができるようになる。
【００３６】
以上に説明したように、位相を量子化することによって離散フーリエ変換を簡単化することができる。
【００３７】
以下、量子化の分割数について説明する。まず、第１に、ＬＵＴ（ＬｏｏｋＵｐＴａｂｌｅ）を計算する。計算結果は、インデックスｌ毎に記憶部１０２に記憶しておけばよい。ここで、信号長Ｎに変更がない限り、再計算することはない。そのため、連続で同一長さ信号の演算をする場合には再利用可能である。
【００３８】
第２に、量子化を行う。例えば、量子化の分割数Ｍ＝４とした場合は、図２に示すようになる。
【００３９】
第３に、量子化の分割数を決定する。量子化の分割数は、信号長Ｎの約数として決定する。Ｎ＝ｓＭを満たすＭを量子化の分割数とする。ここでｓとＭはそれぞれ整数である。なお、Ｍを小さくすることで、位相限定相関関数の計算精度は落ちるものの、量子化された位相のデータ量は削減方向になる。図３，図４，図５，図６，図７，図８，図９に、信号長をＮ＝１２８，量子化の分割数をＭ＝２，４，８，１６，３２，６４，１２８と変化させた場合の位相限定相関関数の比較を示す。なお、いずれにおいても（ａ）が、量子化せずに計算した結果、（ｂ）が量子化して計算した結果、（ｃ）が両者の差分を示している。
【００４０】
図３〜図９より、Ｍ＝１６ぐらいではほとんど誤差がなくなっていることがわかる。従って、分割数Ｍ＝１６とすれば、量子化しない場合とほとんど変わらない照合結果が得られるものと考えられる。
【００４１】
次に、２次元信号の場合について説明する。基本的には前述した１次元信号の場合と同様である。２次元信号は、例えば画像データである。
【００４２】
まず、位相限定相関関数の定義について説明する。画像データの縦のサイズをＮ１とし、画像の横のサイズをＮ２とする。縦方向の空間領域のインデックスをｎ１（ｎ１＝０，１，２，・・・，Ｎ１−１の整数値）とし、横方向の空間領域のインデックスをｎ２（ｎ２＝０，１，２，・・・，Ｎ２−１）とする。
【００４３】
また、画像データの縦に対応する周波数領域のインデックスをｋ１（ｋ１＝０，１，２，・・・，Ｎ１−１の整数値）とし、画像データの横に対応する周波数領域のインデックスをｋ２（ｋ２＝０，１，２，・・・，Ｎ２−１の整数値）とする。
【００４４】
第１パターンデータである一方の入力画像１×１（ｎ１，ｎ２）とこの離散フーリエ変換Ｘ１（ｋ１，ｋ２）とし、照合対象となる第２パターンｄたである他方の入力画像２ｘ２（ｎ１，ｎ２）とこの離散フーリエ変換Ｘ２（ｋ１，ｋ２）とすると、各々は、以下の式（１３），式（１４）で示されるものとなる。また、振幅および位相は、以下の式（１５）および式（１６）となる。
【００４５】
【数９】
0006574699.tif 000010
【００４６】
なお、Ａ１（ｋ１，ｋ２）はＸ１（ｋ１，ｋ２）の振幅、θ１（ｋ１，ｋ２）はＸ１（ｋ１，ｋ２）の位相を表す。また、Ａ２（ｋ１，ｋ２）はＸ２（ｋ１，ｋ２）の振幅、θ２（ｋ１，ｋ２）はＸ２（ｋ１，ｋ２）の位相を表す。
【００４７】
従って、第１パターンデータと第２パターンデータとの位相限定相関関数は、以下の式（１７）となる
【００４８】
【数１０】
0006574699.tif 000011
【００４９】
なお、「θ（ｋ１，ｋ２）＝θ１（ｋ１，ｋ２）−θ２（ｋ１，ｋ２）」であり、２つのパターンデータの位相差を表す。ただし位相の循環性については無視した表現となっている。
【００５０】
次に、上述した位相限定相関関数における位相差θ（ｋ１，ｋ２）を量子化することにより、離散フーリエ変換の式が簡単化することについて説明する。位相差を量子化することにより、以下の式（１８）に示すΣの中身を離散化した値に表現できる。
【００５１】
【数１１】
0006574699.tif 000012
【００５２】
以下、位相差θ（ｋ１，ｋ２）を量子化することにより、離散フーリエ変換の式を簡単化することを以下に記載する。位相差を量子化することにより、数式（１０）のΣの中身を離散化した値に表現できる。はじめに、Ｎ１とＮ２の最小公倍数Ｎを計算する。Ｎ＝ｓ１＊Ｎ１，Ｎ＝ｓ２＊Ｎ２を満たす。ｓ１，ｓ２は整数とする。式（１８）を書きなおすと以下の式（１９）となる。
【００５３】
【数１２】
0006574699.tif 000013
【００５４】
また、Σの中身に着目すると以下のように変形することができる。
【００５５】
【数１３】
0006574699.tif 000014
【００５６】
ここで、以下の式（２１）は、離散値となる。
【００５７】
【数１４】
0006574699.tif 000015
【００５８】
従って、「ｅjθ(k1,k2)」を離散値として表現すれば、式（２０）全体が離散値として表現できるようになる。これにより、式（２０）は、複素数の加算、乗算、三角関数の演算などが含まれる式であったが、単純な複素数の加算のみで計算できるようになる。
【００５９】
「ｅjθ(k1,k2)」の量子化分割数は任意に決めることができるが、計算効率を考えるとＮもしくはＮの約数で分割するとよい。ここで、スケーリング係数ｓと量子化の分割数Ｍとにより、Ｎ＝ｓＭとする。Ｍ状態に量子化された位相をθｑ（ｋ１，ｋ２）とおくと、位相限定相関関数は以下のように変形できる。
【００６０】
【数１５】
0006574699.tif 000016
【００６１】
ここで、ｍ（ｋ１，ｋ２）は、０，１，２，・・・，Ｍ−１の値を取る。また、「ｅｊθｑ（ｋ１，ｋ２）は、以下の式（２３）で示される関係となる。
【００６２】
【数１６】
0006574699.tif 000017
【００６３】
ここで、以下の式（２４）の値は、はＮ個の状態しか取りえないため、インデックス毎に予め計算して求めておき、記憶部１０２に記憶しておくことで、三角関数などの計算が不要になる。
【００６４】
【数１７】
0006574699.tif 000018
【００６５】
予めの計算については、以下のようなＬＵＴ（ＬｏｏｋＵｐＴａｂｌｅ）を用いればよい。
【００６６】
【数１８】
0006574699.tif 000019
【００６７】
式（２５）によるＬＵＴを利用して式（２２）を書きなおすと、以下のようになる。なお、以下の式において、演算子ｍｏｄ（Ａ，Ｂ）は、ＡをＢで割ったときの余りを表す。
【００６８】
【数１９】
0006574699.tif 000020
【００６９】
相関関数演算部１０５は、インデックス計算部１０４が求めた各インデックスに等しいインデックスに対応する、憶部１０２に記憶してある式（２５）による値を用い、式（２６）により位相限定相関関数の値を求める。このように、２次元信号においても、位相限定相関関数の値が、加算により求めることができるようになる。
【００７０】
以上に説明したように、２次元信号においても、前述した１次元信号と同様に、位相を量子化することによって離散フーリエ変換を簡単化することができる。
【００７１】
以上に説明したように、本発明によれば、照合対象の第１パターンデータと第２パターンデータとの位相限定相関関数における位相差を所定の分割数で量子化して離散値とした量子化位相差を用い、第１パターンデータと第２パターンデータとの位相限定相関関数の値を、量子化位相差の加算により求めるようにしたので、フーリエ変換を用いた照合技術における演算コストが低減できるようになる。例えば、照合対象のパターンデータを、複数の照合元パターンデータと照合する場合、非常に多くの照合計算を実施することになるが、演算コストの低減効果が特に大きいものとなる。
【００７２】
なお、本発明は以上に説明した実施の形態に限定されるものではなく、本発明の技術的思想内で、当分野において通常の知識を有する者により、多くの変形および組み合わせが実施可能であることは明白である。
【符号の説明】
【００７３】
１０１…パターンデータ取得部、１０２…量子化値記憶部、１０３…相関関数演算部、１０４…照合部。
【図１】
0006574699.tif 000021
【図２】
0006574699.tif 000022
【図３】
0006574699.tif 000023
【図４】
0006574699.tif 000024
【図５】
0006574699.tif 000025
【図６】
0006574699.tif 000026
【図７】
0006574699.tif 000027
【図８】
0006574699.tif 000028
【図９】
0006574699.tif 000029