(57)【要約】  【課題】  計算コストを抑えつつビットコード化エラーを最小にする変換行列Ｗを求める特徴変換装置を提供する。  【解決手段】  デジタル情報の特徴ベクトルをビットコードに変換する特徴変換装置１０は、複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の変換ベクトルからなる変換行列を生成する変換行列生成部１３と、変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換部１２とを備えている。変換行列生成部１３は、複数の学習用特徴ベクトルのビットコードへの変換によるエラー発生率を計算し、そのエラー発生率をコスト関数として変換行列を生成する。【選択図】  図１
2014149808.tif 000002
【特許請求の範囲】
【請求項１】
デジタル情報の特徴ベクトルをビットコードに変換する特徴変換装置であって、
複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の変換ベクトルからなる変換行列を生成する変換行列生成部と、
前記変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換部と、
を備え、
前記変換行列生成部は、前記複数の学習用特徴ベクトルのビットコードへの変換によるエラー発生率を計算し、前記エラー発生率をコスト関数として前記変換行列を生成する
ことを特徴とする特徴変換装置。
【請求項２】
前記変換行列生成部は、前記変換ベクトルによってビットコードに変換されたときに異なるビットが割り当てられてしまう前記学習用特徴ベクトルの存在確率を前記エラー発生率として計算することを特徴とする請求項１に記載の特徴変換装置。
【請求項３】
前記変換行列生成部は、前記変換ベクトルによって変換された前記学習用特徴ベクトルの、ビットコード境界を中心とする所定範囲の確率密度関数を前記エラー発生率として計算することを特徴とする請求項２に記載の特徴変換装置。
【請求項４】
前記複数の学習用特徴ベクトルの２次モーメントを生成するモーメント生成部をさらに備え、
前記変換行列生成部は、前記複数の学習用特徴ベクトルの分布が前記２次モーメントを共分散行列とする多次元ガウス分布に従うと仮定して、前記エラー発生率を計算する
ことを特徴とする請求項３に記載の特徴変換装置。
【請求項５】
前記変換行列生成部は、前記多次元ガウス分布の頂点の値を用いて、近似的に前記エラー発生率を計算することを特徴とする請求項４に記載の特徴変換装置。
【請求項６】
前記変換行列生成部は、正規直交ベクトルである前記複数の変換ベクトルを求めて前記変換行列を生成することを特徴とする請求項１ないし５のいずれか一項に記載の特徴変換装置。
【請求項７】
前記変換行列生成部は、前記コスト関数が最小になるように前記変換行列を生成することを特徴とする請求項１ないし６のいずれか一項に記載の特徴変換装置。
【請求項８】
前記変換行列生成部は、前記変換ベクトルの各々に対する前記２次モーメントの分散が等しくなるように、前記複数の変換ベクトルを求めることで、前記変換行列を生成することを特徴とする請求項１ないし６のいずれか一項に記載の特徴変換装置。
【請求項９】
デジタル情報の特徴ベクトルをビットコードに変換する特徴変換装置であって、
複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の直交する変換ベクトルからなる変換行列を生成する変換行列生成部と、
前記変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換部と、
を備え、
前記変換行列生成部は、写像される空間または部分空間においてベクトルの共分散行列の対角成分を均等化する条件、及び、その他の拘束条件を課すことで、前記変換行列を一意に生成することを特徴とする特徴変換装置。
【請求項１０】
前記その他の拘束条件は、前記変換行列の疎行列化する条件であることを特徴とする請求項９に記載の特徴変換装置。
【請求項１１】
前記変換行列生成部は、写像される空間または部分空間においてベクトルの共分散行列の対角成分を均等化する条件と、前記変換行列を疎行列化する条件とを表したコスト関数を最小化することで、前記変換行列を生成することを特徴とする請求項１０に記載の特徴変換装置。
【請求項１２】
前記変換行列生成部は、前記コスト関数を、次元圧縮を行わずに、元の次元において定義することを特徴とする請求項１１に記載の特徴変換装置。
【請求項１３】
前記変換行列生成部は、回転群ＳＯ（Ｎ）から選ぶことで、前記変換行列を生成することを特徴とする請求項１０に記載の特徴変換装置。
【請求項１４】
前記変換行列生成部は、前記回転群ＳＯ（Ｎ）のオイラー角を探索することを特徴とする請求項１３に記載の特徴変換装置。
【請求項１５】
前記その他の拘束条件は、前記複数の学習用特徴ベクトルのビットコードへの変換によるエラー発生率を最小化する条件であることを特徴とする請求項９に記載の特徴変換装置。
【請求項１６】
デジタル情報の特徴ベクトルをビットコードに変換する特徴変換方法であって、
複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の変換ベクトルからなる変換行列を生成する変換行列生成ステップと、
前記変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換ステップと、
を含み、
前記変換行列生成ステップは、前記複数の学習用特徴ベクトルのビットコードへの変換によるエラー発生率を計算し、前記エラー発生率をコスト関数として前記変換行列を生成する
ことを特徴とする特徴変換方法。
【請求項１７】
デジタル情報の特徴ベクトルをビットコードに変換する特徴変換方法であって、
複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の直交する変換ベクトルからなる変換行列を生成する変換行列生成ステップと、
前記変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換ステップと、
を含み、
前記変換行列生成ステップは、写像される空間または部分空間においてベクトルの共分散行列の対角成分を均等化する条件、及び、その他の拘束条件を課すことで、前記変換行列を一意に生成することを特徴とする特徴変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像や文章などのデジタル情報の特徴を識別や検索などの演算に有利な特徴に変換する特徴変換装置及び特徴変換方法に関するものである。
【背景技術】
【０００２】
画像検索や文章検索など、多くの分野で特徴ベクトルが用いられている。特徴ベクトルは、画像や文章などのデジタル情報を何らかの演算により変換して得られる多次元のベクトルである。デジタル情報の特徴は、識別に有効な特徴ベクトルに変換される。例えば、画像Ａの特徴ベクトルと、画像Ｂの特徴ベクトルの距離を計測することで、それらの画像が同一であるか否かを識別することが可能である。この原理を使い、大量の特徴ベクトルを保持したデータセットの中から、ある特定の特徴を持つ画像や文章を探索することが可能となる。
【０００３】
特徴ベクトル間の距離の尺度としては、Ｌ１ノルム、Ｌ２ノルム、ベクトル間角度などが用いられる。Ｌ１ノルム、Ｌ２ノルム、及びベクトル間角度は、特徴ベクトルｘ，ｙ∈ＲNについて、それぞれ以下の（１）式、（２）式、及び（３）式のように計算できる。
下式において、ｘとｙの下付きの数字は要素番号を表し、（・）Tはベクトルの転置を表
す。
【数１】
2014149808.tif 000003
【数２】
2014149808.tif 000004
【数３】
2014149808.tif 000005
【０００４】
入力となる特徴ベクトルに対して、大量の特徴ベクトルの中から最も似ているｋ個の特徴ベクトルを高速に検索する技術が研究されている。これはｋ−近傍探索、もしくは近似ｋ−近傍探索と呼ばれる。ｋ−近傍探索は、大量の特徴ベクトルの中から、最も距離が近いｋ個の特徴ベクトルを高速に検索する技術であり、代表的な手法としてｋｄ−ｔｒｅｅが挙げられる（非特許文献１参照）。
【０００５】
近似ｋ−近傍探索も、大量の特徴ベクトルの中から、最も距離が近いｋ個の特徴ベクトルを高速に検索する技術であるが、近似ｋ−近傍探索は、誤りを許すことで、ｋ−近傍探索よりもはるかに高速な処理を実現できる。近似ｋ−近傍探索の代表的な手法として、ＬＳＨ（Locality Sensitive Hashing）（非特許文献２参照）が挙げられる。
【０００６】
近年では、計算機が扱う情報の大規模化が進んでおり、大量かつ高次元の特徴ベクトルを扱うことが多くなった。そこで、次の二点が深刻な問題となっている。第一の問題点は、距離計算の計算負荷が高く、２つの特徴ベクトルｘ，ｙ∈ＲNの距離の計算が非常に遅
いことである。例えばＬ２ノルムの二乗を距離の尺度として用いる場合、それは（４）式
のようになり、従って、距離の計算には、Ｎ回の引き算、Ｎ回の乗算、Ｎ−１回の加算が必要である。
【数４】
2014149808.tif 000006
【０００７】
多くの場合、特徴ベクトルは浮動小数で表現されるため、この計算負荷は非常に高くなる。特徴ベクトルが高次元になれば、この計算負荷はさらに高くなる。また、大量の特徴ベクトルを扱う場合、この距離計算を大量に行わなければならないため、計算負荷はさらに高くなる。そのため、ｋ−近傍探索アルゴリズムや近似ｋ−近傍探索アルゴリズムを適用しても、十分な処理速度が得られないことが多い。
【０００８】
第二の問題点は、大量のメモリを消費することである。特徴ベクトルを４バイトの単精度実数で表現する場合、Ｎ次元の特徴ベクトルは４Ｎバイトのメモリを消費する。特徴ベクトルが高次元になるほど、このメモリ消費量は高くなる。大量の特徴ベクトルを扱う場合、扱う特徴ベクトルの数だけメモリを消費することになる。特徴ベクトルがメインメモリに入りきらない場合、ハードディスクなどの二次領域に特徴ベクトルを格納しなければならなくなるが、二次領域を用いた場合、計算機の処理速度は著しく低下してしまう。
【０００９】
そこで近年、特徴ベクトルをビットコード（バイナリコード）化することにより、これら２つの問題を解決する手法が提案されている。代表的な手法として、ランダムプロジェクション（random projection、非特許文献３参照）、超疎ランダムプロジェクション（very sparse random projection、非特許文献４参照）、及びスペクトラルハッシング（Spectral Hashing、非特許文献５参照）がある。
【００１０】
これらの手法は、Ｎ次元特徴ベクトルを、Ｂビットのビットコードに変換する。この変換は、もともとの空間における距離が、変換後の空間におけるハミング距離と強く相関するように行われる。ハミング距離とは、二つのビットコードのうち、異なるビットの数を数えたものである。
【００１１】
この計算は、２つのコードの各要素の排他的論理和（ＸＯＲ）をとった後に１が立っているビット数を数えるだけなので、非常に高速に行える。多くの場合、特徴ベクトルのＬ２ノルムの計算と比較して、数十〜数百倍程度の高速化が可能である。また、もともと４Ｎバイト必要であったメモリを、Ｂ／８バイトまで削減できる。これにより、数十〜数百分の一にメモリを節約できる。
【００１２】
多くのビットコード化アルゴリズムは（５）式のように一般的な形で記述できる。
【数５】
2014149808.tif 000007
ここで、ｘは特徴ベクトル（Ｎ次元）、Ｗは変換行列（Ｎ行Ｂ列）、ｍはバイアス（Ｂ次元）、ｂはビットコード（Ｂ次元）、ｆ（ｙ）は非線形関数、ｓｇｎ（ｙ）は符号関数（値が負なら−１、正なら１を返す関数）である。よって、ｂの要素は＋１か−１のどちらかになる。そこで、＋１を「１」、−１を「０」として並べたものをビットコードとする。
【００１３】
ここで、変換行列Ｗをいかに決定するかが問題となる。ランダムプロジェクションでは、変換行列Ｗの要素として、平均がゼロ、分散が１の正規分布からサンプリングしたものを用いる。バイアスｍはゼロベクトル、又は事前に集めておいた特徴ベクトルの平均値、
もしくは中央値を用いる。また、非線形関数をｆ（ｙ）＝ｙと定義する。なお、ｆ（ｙ）＝ｙの場合のビットコード化は、特別に「線形変換型ビットコード化」と呼ばれる。
【００１４】
スペクトラルハッシングでは、事前に集めておいた特徴ベクトル（訓練集合）に主成分分析を適用し、求めた主成分軸を変換行列Ｗの行ベクトルとする。また、訓練集合の平均をバイアスｍとする。非線形関数ｆ（ｙ）には、三角関数を用いる。この場合には、変換行列Ｗやバイアスｍが学習に基づいているため、より短いビットコードが生成可能である。ただし、ｓｇｎ（・）の評価が不十分であり、効果は不十分である。
【００１５】
反復量子化（Iterative Quantization）の場合は、特徴ベクトル（訓練集合）に主成分分析を適用し、主成分軸を回転させることで最適な変換行列Ｗを求める。回転は、各特徴ベクトルにつき、原点からの距離に応じた重みを乗じて求める。
【００１６】
等方ハッシング（Isotropic Hashing）では、主反復量子化と同様に、成分分析を適応
することで、目的とするビット長と同じ次元の部分空間へ特徴ベクトルを写像する。但し、等方ハッシングでは、主反復量子化と異なり、写像されたベクトルの共分散行列の対角成分が全て等しくなるように、部分空間において反復的に直交変換を行う。等方ハッシングでは、このようにして求めた変換行列Ｗを使い、特徴ベクトルから平均ベクトルを引いたベクトルｘを、（６）式によってビットコードに変換する。
【数６】
2014149808.tif 000008
等方ハッシングにおいて対角成分を均等化することは、信号のパワーあたりの情報量を一定にすることを意味している。このため、各軸を等価的に扱えることから、ハミング距離による類似度の精度の損失が少ないことが期待できる。実際に、非特許文献６（Isotropic Hashingの論文）では、他手法と比較して類似度の精度の損失が少ないことが示され
ている。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】J. L. Bentley. Multidimensional binary search trees used forassociative searching. Communications of the ACM, 18(9):509-517, 1975.
【非特許文献２】Indyk, Piotr.; Motwani, Rajeev. (1998). , "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.". Proceedings of 30th Symposium on Theory of Computing.
【非特許文献３】Michel X. Goemans, avid P. Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM Volume 42 , Issue 6 (November 1995) Pages: 1115-1145（１１２１ページのＬｅｍｍａ３．２に、もとの空間における距離と変換後の空間におけるハミング距離とが強く相関する根拠について記載されている。）
【非特許文献４】Ping Li, Trevor J. Hastie, Kenneth W. Church, "very sparse random projections", KDD '06 Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (2006)
【非特許文献５】Y. Weiss, A. Torralba, R. Fergus., "Spectral Hashing", Advances in Neural Information Processing Systems, 2008.
【非特許文献６】Weihao Kong, Wu-Jun Li, "Isotropic Hashing", Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS), 2012.
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかしながら、上記従来のビットコード化においては、以下の問題がある。まず、上述のランダムプロジェクションやスペクトラルハッシングでは、ビットコードが長くなってしまう。特に、乱数に基づいて変換行列Ｗを構成する場合には、特徴ベクトルの分布について考慮していないため、十分な性能を得るためには十分に長いビットコードが必要になる。それによって、ビットコードの変換に要する計算時間とハミング距離の計算量が多くなる問題と、メモリ消費量が多くなる問題がある。
【００１９】
また、上述の反復量子化の場合には、データそのものを利用するため、データ数に比例した計算量が必要であり、変換行列Ｗの計算コストが大きくなるという問題がある。
【００２０】
本発明は、上記の問題に鑑みてなされたものであり、計算コストを抑えつつビットコード化エラーを最小にする変換行列Ｗを求める特徴変換装置及び特徴変換方法を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明の特徴変換装置は、デジタル情報の特徴ベクトルをビットコードに変換する特徴変換装置であって、複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の変換ベクトルからなる変換行列を生成する変換行列生成部と、前記変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換部とを備え、前記変換行列生成部は、前記複数の学習用特徴ベクトルのビットコードへの変換によるエラー発生率を計算し、前記エラー発生率をコスト関数として前記変換行列を生成する構成を有している。
【００２２】
この構成によれば、エラー発生率に基づいて変換行列を生成できるので、計算コストを抑えつつビットコード化（符号化）エラーを最小にする変換行列を生成できる。
【００２３】
上記の特徴変換装置において、前記変換行列生成部は、前記変換ベクトルによってビットコードに変換されたときに異なるビットが割り当てられてしまう前記学習用特徴ベクトルの存在確率を前記エラー発生率として計算してよい。
【００２４】
この構成によれば、変換ベクトルによってビットコードに変換されたときに異なるビットが割り当てられてしまう特徴ベクトルの存在確率が低くなるように変換行列を生成できるので、ビットコード化エラーを最小にする変換行列を生成できる。
【００２５】
上記の特徴変換装置において、前記変換行列生成部は、前記変換ベクトルによって変換された前記学習用特徴ベクトルの、ビットコード境界を中心とする所定範囲の確率密度関数を前記エラー発生率として計算してよい。
【００２６】
この構成によれば、確率密度関数を用いることで、計算コストを抑えつつ、変換ベクトルによってビットコードに変換されたときに異なるビットが割り当てられてしまう前記特徴ベクトルの存在確率を求めることができる。ビットコード境界は、０であっても他の任意の値であってもよい。
【００２７】
上記の特徴変換装置は、前記複数の学習用特徴ベクトルの２次モーメントを生成するモーメント生成部をさらに備えていてよく、前記変換行列生成部は、前記複数の学習用特徴ベクトルの分布が前記２次モーメントを共分散行列とする多次元ガウス分布に従うと仮定して、前記エラー発生率を計算してよい。
【００２８】
この構成によれば、複数の学習用特徴ベクトルの分布がその２次モーメントを共分散行
列とする多次元ガウス分布に従うと仮定してエラー発生率を計算するので、簡易な計算でエラー発生率を求めることができる。
【００２９】
上記の特徴変換装置において、前記変換行列生成部は、前記多次元ガウス分布の頂点の値を用いて、近似的に前記エラー発生率を計算してよい。
【００３０】
この構成によれば、多次元ガウス分布の頂点の値と上記の所定範囲との積を上記の確率密度とすることができ、エラー発生率の計算をより簡易に行うことができる。
【００３１】
上記の特徴変換装置において、前記変換行列生成部は、正規直交ベクトルである前記複数の変換ベクトルを求めて前記変換行列を生成してよい。
【００３２】
この構成によれば、変換行列を構成する変換ベクトルが正規直交系であるであるという条件が付加されるので、エラー発生率の計算をより簡易に行うことができる。
【００３３】
上記の特徴変換装置において、前記変換行列生成部は、前記コスト関数が最小になるように前記変換行列を生成してよい。
【００３４】
この構成によれば、コスト関数が最小になるように変換行列が生成されるので、エラー発生率が最小である変換行列を得ることができる。
【００３５】
上記の特徴変換装置において、前記変換行列生成部は、前記変換ベクトルの各々に対する前記２次モーメントの分散が等しくなるように、前記複数の変換ベクトルを求めることで、前記変換行列を生成してよい。
【００３６】
この構成によれば、変換ベクトルの各々に対する前記２次モーメントの分散が等しくなるので、エラー発生率が最小である変換行列を得ることができる。
【００３７】
本発明の別の態様の特徴変換装置は、デジタル情報の特徴ベクトルをビットコードに変換する特徴変換装置であって、複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の直交する変換ベクトルからなる変換行列を生成する変換行列生成部と、前記変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換部とを備え、前記変換行列生成部は、写像される空間または部分空間においてベクトルの共分散行列の対角成分を均等化する条件、及び、その他の拘束条件を課すことで、前記変換行列を一意に生成する構成を有している。
【００３８】
この構成によれば、特徴ベクトルをビットコードに変換する際の情報の損失を低く抑えることができ、かつ変換行列と特徴ベクトルの積和演算の計算量を低減する等の付加的な効果を得ることができる。なお、ここで、「一意に」とは、解が無限にある状態（under-constrained）ではない状態（over-constrained）をいう。
【００３９】
上記の特徴変換装置において、前記その他の拘束条件は、前記変換行列の疎行列化する条件であってよい。
【００４０】
この構成によれば、変換行列と特徴ベクトルの積和演算の計算量が低減され、ビットコード化を高速化できる。
【００４１】
上記の特徴変換装置において、前記変換行列生成部は、写像される空間または部分空間においてベクトルの共分散行列の対角成分を均等化する条件と、前記変換行列を疎行列化する条件とを表したコスト関数を最小化することで、前記変換行列を生成してよい。
【００４２】
この構成によれば、コスト関数が両条件を同時に表すので、このコスト関数を最小化することで、特徴ベクトルをビットコードに変換する際の情報の損失を低く抑えることができ、かつ特徴ベクトルの積和演算の計算量を低減することが可能な変換行列を生成することができる。
【００４３】
上記の特徴変換装置において、前記変換行列生成部は、前記コスト関数を、次元圧縮を行わずに、元の次元において定義してよい。
【００４４】
この構成によれば、解の探索の範囲を広げるとともに、補空間への信号のパワーの流出を許す自由度があるため、変換行列を容易に疎行列化できる。
【００４５】
上記の特徴変換装置において、前記変換行列生成部は、回転群ＳＯ（Ｎ）から選ぶことで、前記変換行列を生成してよい。
【００４６】
この構成によれば、変換行列生成部は、変換行列を回転群ＳＯ（Ｎ）から求めるので、特徴ベクトルのユークリッド距離の関係を変えることなく変換を行うことができる。
【００４７】
上記の特徴変換装置において、前記変換行列生成部は、前記回転群ＳＯ（Ｎ）のオイラー角を探索してよい。
【００４８】
この構成によれば、変換行列そのものの探索に比べて探索空間が狭いため、計算が効率的であり、また得られる行列がＳＯ（Ｎ）に厳密に属することが自動的に保障される。
【００４９】
上記の特徴変換装置において、前記その他の拘束条件は、前記複数の学習用特徴ベクトルのビットコードへの変換によるエラー発生率を最小化する条件であってよい。
【００５０】
この構成によれば、類似度の計算精度の損失を抑えて変換ベクトルのビット長を短くできるので、変換行列と特徴ベクトルとの積和演算の計算量を低減できる。
【００５１】
本発明の特徴変換方法は、デジタル情報の特徴ベクトルをビットコードに変換する特徴変換方法であって、複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の変換ベクトルからなる変換行列を生成する変換行列生成ステップと、前記変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換ステップとを含み、前記変換行列生成ステップは、前記複数の学習用特徴ベクトルのビットコードへの変換によるエラー発生率を計算し、前記エラー発生率をコスト関数として前記変換行列を生成する。
【００５２】
この構成によっても、エラー発生率に基づいて変換行列を生成できるので、計算コストを抑えつつビットコード化（符号化）エラーを最小にする変換行列を生成できる。
【００５３】
本発明の別の態様の特徴変換方法は、デジタル情報の特徴ベクトルをビットコードに変換する特徴変換方法であって、複数の学習用特徴ベクトルを用いて、特徴ベクトルをビットコードに変換するための、複数の直交する変換ベクトルからなる変換行列を生成する変換行列生成ステップと、前記変換行列を用いて、特徴ベクトルをビットコードに変換するビットコード変換ステップとを含み、前記変換行列生成ステップは、写像される空間または部分空間においてベクトルの共分散行列の対角成分を均等化する条件、及び、その他の拘束条件を課すことで、前記変換行列を一意に生成する。
【００５４】
この構成によっても、特徴ベクトルをビットコードに変換する際の情報の損失を低く抑
えることができるとともに、変換行列と特徴ベクトルの積和演算の計算量を低減する等の付加的な効果を得ることができる。
【発明の効果】
【００５５】
本発明によれば、ビット割り当てのエラー発生率を小さく抑えることができる変換行列を得ることができ、特徴ベクトルをこの変換行列でビットコードに変換することで、少ないビット数で類似した特徴を正確に判断できるビットコードを得ることができる。また、対角成分が等しいだけでなく、さらなる付加的な拘束条件が課された変換行列を得ることができ、特徴ベクトルをビットコードに変換する際の情報の損失を低く抑えることができるとともに、変換行列と特徴ベクトルの積和演算の計算量を低減する等の付加的な効果を得ることができる。
【図面の簡単な説明】
【００５６】
【図１】本発明の第１の実施の形態における特徴変換装置を含む特徴演算装置の構成を示すブロック図
【図２】本発明の第１の実施の形態におけるエラー発生率を説明するためのベクトル空間を示す図
【図３】本発明の第１の実施の形態における変換行列の生成フロー図
【図４】本発明の第２の実施の形態における変換行列の生成フロー図
【図５】本発明の第２の実施の形態における特徴変換装置によって得られる線形変換後の共分散行列（ＲTＣＲ）の例を示す図
【図６】本発明の第２の実施の形態の特徴変換装置によって得られる回転行列（Ｒ）の例を示す図
【発明を実施するための形態】
【００５７】
以下、本発明の実施の形態の特徴変換装置について、図面を参照しながら説明する。なお、以下に説明する実施の形態は、本発明を実施する場合の一例を示すものであって、本発明を以下に説明する具体的構成に限定するものではない。本発明の実施にあたっては、実施の形態に応じた具体的構成が適宜採用されてよい。
【００５８】
（第１の実施の形態）
図１は、本発明の第１の実施の形態の特徴変換装置を含む特徴演算装置の構成を示すブロック図である。図１に示すように、特徴演算装置１００は、エンコーダ部（特徴変換装置）１０と特徴ベクトル検索部２０とからなる。本実施の形態の特徴演算装置は、特徴ベクトルを用いて、大量の画像や文章のデジタル情報の中から、入力されたデジタル情報に類似するものを検索するために特徴ベクトルの演算を行う装置である。
【００５９】
エンコーダ部１０は、モーメント生成部１１と、変換行列生成部１３と、ビットコード変換部１２とを備えている。エンコーダ部１０のこれらの構成は、演算処理部、一時記憶部等を備えたコンピュータが所定のプログラムを実行することにより実現されてよく、あるいはハードウェアによって実現されてもよい。
【００６０】
画像検索や文章検索に必要な条件とは、入力された特徴ベクトルと同じ特徴を有する特徴ベクトルをデータセットの中から探索できることである。一般に特徴ベクトルはノイズなどの影響を受ける。従って、例えば同じ対象を撮像した２枚の画像であっても、多くの場合はそれらの特徴ベクトル間の距離が０とはならず、それらの特徴ベクトルのビットコードの間の距離（ハミング距離）も０となることは稀である。有効なビットコード化とは、もとの空間で近傍にあるベクトルとのハミング距離（ビット割り当てエラー）を十分に小さくするものでなくてはならない。ただし、本実施の形態では、線形型ビットコード化を対象とする。
【００６１】
モーメント生成部１１には、複数の学習用の特徴ベクトルが入力される。これらの特徴ベクトルを（７）式のように定義する。
【数７】
2014149808.tif 000009
ｘの下付き数字はデータの番号を示している。すなわち、モーメント生成部１１には、Ｍ個の学習用特徴ベクトルが入力される。また、モーメント生成部１１に入力されたすべての特徴ベクトルをまとめたものを、（８）式のように行列Ｘとして定義する。
【数８】
2014149808.tif 000010
【００６２】
モーメント生成部１１は、入力されたＭ個の学習用特徴ベクトルから、１次モーメントを生成してビットコード変換部１３に出力し、２次モーメントを生成して変換行列生成部１２に出力する。
【００６３】
１次モーメントは、全特徴ベクトルの平均ベクトル（ａｖｅ（ｘ））である。２次モーメントは、分散共分散行列ＣXであって、（９）式のように定義される。
【数９】
2014149808.tif 000011
【００６４】
変換行列生成部１３は、この分散共分散行列のみを用いて変換行列Ｗを求める。この分散共分散行列のみを用いるということは、特徴ベクトルから平均値（ａｖｅ（ｘ））を引いた量が平均０であり、ＣXを分散共分散行列とする多次元ガウス分布に従うと仮定する
のと同義である。分散共分散行列ＣXのみを用いて変換行列Ｗを求めるので、学習用特徴
ベクトルの数Ｍではなく、ベクトルサイズＮに依存した処理量で変換行列Ｗを求めることができる。すなわち、一般にＭ＞＞Ｎであるので、変換行列Ｗを求めるための処理負担を軽減できる。
【００６５】
変換行列生成部１３は、ビット割り当てエラーを最小にする変換行列Ｗを生成する。まず、ビット割り当てエラーを最小にするためのコスト関数（ビット割り当てエラー発生率）について説明する。上述のように、本実施の形態の変換行列生成部１３は、２次モーメント（分散共分散行列）のみを用いて変換行列Ｗを求める。
【００６６】
以下では、変換行列Ｗを（１０）式のように表現する。
【数１０】
2014149808.tif 000012
この各列ベクトルｗを変換ベクトルと呼ぶ。変換ベクトルｗに望まれることは、（１）データ集合Ｘを二分すること、（２）データｘの近傍の点は同じ符号に割り当てること、（３）異なる列ベクトル間の相関が小さいこと、の３点である。
【００６７】
（１）の要望は、データの分布を平均０の多次元ガウス分布であると近似すると、原点を通る超平面で分割することと等しい。本実施の形態では、変換ベクトルｗは、原点を通る超平面であるのでこの要望を満足する。（３）の要望については、本実施の形態では緩和させた要望として、変換行列Ｗが正規直交系であるという条件を適用する。つまり（１１）式が成り立つものとする。
【数１１】
2014149808.tif 000013
【００６８】
以下、（２）の要望をいかに満足するかについて説明する。ここでは、特徴ベクトルｘを（１２）式を用いてビットコード化する場合を考える。
【数１２】
2014149808.tif 000014
また、ｘの近傍点ｘεを、‖ｘε−ｘ‖ ＜ε／２を満たす点とする。ただし，ε＞０
であり、‖・‖ はｌ2ノルムを表すものとする。
【００６９】
このような前提の下、変換行列生成部１３は、ｘを中心とする半径ε／２の超球内の範囲で、変換ベクトルｗによってビットコード化されたときに異なるビットが割り当てられてしまう特徴ベクトルｘの存在確率をもって、変換ベクトルｗに対するビット割り当てエラー発生率ＰＷを定義する。本実施の形態では、ｙ＝ｗTｘとおくと、生成されるビット
コード（０，１）を分ける境界（ビットコード境界）はｙ＝０であるので、ビット割り当てエラーが発生するのは、ｙ＝ｗTｘが０を中心とする−ε／２≦ｙ≦ε／２の範囲とな
り、従ってエラー発生率ＰＷは（１３）式として算出できる。
【数１３】
2014149808.tif 000015
ここで、σW＝ｗTＣXｗとした。（１３）式に示すように、エラー発生率ＰＷは、変換
ベクトルｗによって変換された学習用特徴ベクトルの、ビットコード境界を中心とする所定範囲（−ε／２〜ε／２）の確率密度関数として定義される。
【００７０】
図２は、エラー発生率を説明するためのベクトル空間を示す図である。ただし、図２では、説明を簡潔にするために、ベクトル空間を二次元空間で示している。変換ベクトルｗ1による変換によってビット割り当てエラーが発生し得る領域は、−ε／２≦ｙ1（＝ｗ1Tｘ）≦ε／２の領域ｒ1であり、変換ベクトルｗ2による変換によってビット割り当てエラーが発生し得る領域は、−ε／２≦ｙ2（＝ｗ2Tｘ）≦ε／２の領域ｒ2である。
【００７１】
変換行列Ｗ全体でのビット割り当てエラー率は、重複する範囲を考慮すると（１４）式となる。
【数１４】
2014149808.tif 000016
ここで、Ｗi,j＝［ｗi，ｗj］、ｗi，ｗj∈Ｗ、Σi,j＝Ｗi,jTＣXＷi,jと
した。また、｜・｜は、ｌ1ノルムである。
【００７２】
計算の簡略化のため、ε＜＜１とし、各ガウス分布の頂点の値を用いて（１４）式を近似する。Ｐi,j,...をＮ（０，Σi,j...）のモード値とおくと、（１４）式は（１５）式
と近似できる。
【数１５】
2014149808.tif 000017
【００７３】
変換行列生成部１３は、このＰＷをコスト関数として変換行列Ｗを求める。変換行列生成部１３は、コスト関数ＰＷが最小になる条件を求める。（１５）式において、Ｐiは（
１６）式のようになる。
【数１６】
2014149808.tif 000018
また、ＣXの固有値をλiとし、ｉ＝１，．．．，Ｂ、λ1≧・・・≧λBとおくと、変換行列Ｗは正規直交系であるので、
【数１７】
2014149808.tif 000019
の上限は、
【数１８】
2014149808.tif 000020
となる。
【００７４】
ラグランジュ未定乗数λLを導入し、コスト関数ＰＷの最小値を求めると、（１７）式
を得る。
【数１９】
2014149808.tif 000021
（１７）式をｗi、λLで偏微分することにより、ＰＷが最小値となる条件は（１８）式となる。
【数２０】
2014149808.tif 000022
ここから、２次モーメントが与えられた場合、各ベクトルに対する分散が等しくなるように変換ベクトルｗを設定するのが最適であることがわかる。よって、変換行列生成部１３は、モーメント生成部１１から学習用特徴ベクトルの２次モーメントＣXを取得すると
、変換ベクトルｗを、それらの分散が互いに等しくなるように（複数の変換ベクトルｗが等パワーとなるように）求める。
【００７５】
変換行列生成部１３における具体的なアルゴリズムは、次の通りである。変換行列生成部１３は、変換行列Ｗが正規直行系となるように変換ベクトルｗを一本ずつ求めていく。つまり、２次モーメントを表す共分散行列をＣXとすると、分散ｗTＣXｗがある一定値と
なるような大きさ１のベクトルを一本選び、変換ベクトルの直交補空間に共分散行列を射影し、共分散行列を更新するというサイクルを繰り返すことにより変換行列Ｗを求める。
【００７６】
変換行列生成部１３は、まず、モーメント生成部１１より与えられた２次モーメントＣXを（１９）式のように展開して、大きいほうからＢ個の固有値及び対応する固有ベクト
ルからなるＣを生成する。
【数２１】
2014149808.tif 000023
【００７７】
各変換ベクトルｗに等しい分散となるように分解していき、その分散値を
【数２２】
2014149808.tif 000024
とおく。ｗ＝ＵBｃ、‖ｃ‖＝１となる係数ベクトルｃを求め、Ｃからｗ成分を引いてい
くことにより、正規直交ベクトルから構成される変換行列Ｗを求める。
【００７８】
具体的には、変換行列生成部１３は、図３に示すフロー図に従って変換行列Ｗを生成する。ｗ＝ＵBｃbとしてｂ番目（初期値はｂ＝１）の変換ベクトルｗを求める（ステップＳ３１）。すなわち、変換行列生成部１３は、（２０）式を満たすｃbを求める。
【数２３】
2014149808.tif 000025
本実施の形態では、
【数２４】
2014149808.tif 000026
を自明解として使用する。以上から、ｗ1＝ＵBＣ1として最初の変換ベクトルが求められ
る。
【００７９】
その後、ｂ＝Ｂか否かを確認し（ステップＳ３２）、ｂ＝Ｂでなければ（ステップＳ３２にてＮＯ）、Ｃを、（２１）式によって、変換ベクトルｗと直交補空間となるように更新して（ステップＳ３３）、ｂをインクリメントして（ステップＳ３４）、ステップＳ３１に戻って処理を繰り返す。
【数２５】
2014149808.tif 000027
このようにして、ｂ＝Ｂになると（ステップＳ３２にてＹＥＳ）、それまでに得られた変換ベクトルｗ1，…，ｗBによって変換行列Ｗを生成して出力する（ステップＳ３５）。
【００８０】
以上のようにして、変換行列生成部１３にて複数の学習用特徴ベクトルから変換行列Ｗが生成されると、それがビットコード変換部１２に出力される。ビットコード変換部１２は、取得した変換行列Ｗを記憶する。ビットコード変換部１２には、ビットコード変換すべき特徴ベクトルｘが入力される。ビットコード変換部１２は、記憶している変換行列Ｗを用いて、入力された特徴ベクトルｘに対してビットコード変換を行い、出力する。
【００８１】
ビットコード変換部１２は、（２２）式によって入力された特徴ベクトルｘをビットコード変換する。
【数２６】
2014149808.tif 000028
この平均ベクトルａｖｅ（ｘ）は、モーメント生成部１１にて生成されてビットコード変換部１２に入力され、ビットコード変換部１２に記憶されているものである。ビットコード変換部１２は、ビットコードに変換された特徴ベクトルを特徴ベクトル検索部２０に出力する。
【００８２】
特徴ベクトル検索部２０は、入力された特徴ベクトル（ビットコードに変換済み）に対応する特徴ベクトル（ビットコードに変換済み）を検索する。特徴ベクトル検索部２０は、ビットコード保管部２１と、ｋ−近傍探索部２２と、距離計算部２３とを備えている。
【００８３】
ビットコード保管部２１は、検索の対象となる大量のビットコードを保管している。このビットコードは、入力された特徴ベクトルと同種のデジタル情報の特徴から生成されたものである。ビットコード保管部２１にビットコードとして保管されるデジタル情報の特徴ベクトルは、変換行列生成部１３にて生成された変換行列Ｗでビットコード化されたものである。
【００８４】
ｋ−近傍探索部２２には、エンコーダ部１０のビットコード変換部１２から、ビットコードに変換された特徴ベクトルが入力される。ｋ−近傍探索部２２は、入力された特徴ベ
クトル（ビットコード変換部１２にてビットコードに変換済み）に最も近いｋ個のビットコードを、ビットコード保管部２１に記憶された大量のビットコードの中から探索する。
【００８５】
距離計算部２３は、ｋ−近傍探索部２２におけるｋ−近傍探索に必要な距離（類似度）の計算を行う。本実施の形態では、探索の目標となる特徴ベクトル及び探索の対象となるデータのいずれもビットコードであるので、それらの間の距離は、（２３）式によって互いの正規化ハミング距離によって計算できる。
【数２７】
2014149808.tif 000029
【００８６】
（２３）式に示す正規化ハミング距離Ｄhamming（ｂu，ｂv）は、０から１の範囲の値
を取るように正規化されている。２つのビットコードｂu、ｂvの距離の値が小さいほど両ベクトルは互いに類似しており、距離が大きいほど両ベクトルは類似していないことを表す。ｋ−近傍探索部２２は、入力された特徴ベクトルに最も近いｋ個の類似ベクトルを出力する。
【００８７】
以上のように、本実施の形態の特徴量演算装置において、エンコーダ部１０の変換行列生成部１３は、入力された特徴ベクトルをビットコードに変換するための変換行列として、ビット割り当てのエラー発生率（具体的には、変換行列によってビットコード化されたときに異なるビットが割り当てられてしまう特徴ベクトルの存在確率）を最小にする変換行列を生成するので、ビットコード化エラーが発生する可能性が小さい変換行列を得ることができ、よって、特徴ベクトル検索部２０では、類似する特徴ベクトル同士のビットコード間の距離（ハミング距離）を小さく保つことができる。これによって、特徴ベクトル検索部２０は、類似する特徴ベクトルを正確に検索できる。
【００８８】
また、上記のように、類似する特徴ベクトルを正確に検索できることから、同程度のマッチング性能を達成するのに必要なビット数が他の手法により変換行列を生成する場合と比較して少なくて済み、よって、ビットコード変換の計算量やハミング距離の計算量を低く抑えることができる。
【００８９】
さらに、エンコーダ部１０は、変換行列を算出する際に、複数の学習用特徴ベクトルの２次モーメントを用い、学習用特徴ベクトルのデータそのものを用いないので、変換行列を高速に算出できる。また、さらに、生成する変換行列を正規直交系とすることで、変換行列を構成する変換ベクトル間の相関を小さくでき、類似する特徴ベクトルの検索に有利なビットコード変換を行うことができる。
【００９０】
（第２の実施の形態）
第２の実施の形態では、特徴変換装置は、等方ハッシングを改良した方法によって変換行列を求める。上述のように、等方ハッシングでは、写像されたベクトルの共分散行列の対角成分が全て等しくなるように、部分空間において反復的に直交変換を行うことで、信号のパワーあたりの情報量を一定にして、ハミング距離による類似度の精度の損失を小さくしている。
【００９１】
写像される空間においてベクトルの共分散行列の対角成分が全て等しくなるような変換行列は、３次元以上の空間であれば、無限個存在する。理由は次のとおりである。いま、Ｂ次元のベクトルの回転を考えると、回転行列の自由度は、Ｂ次元に拡張されたオイラー角の個数と同じであり、Ｂ（Ｂ−１）／２である。一方、共分散行列の対角成分が全て等しくなる条件はＢ−１個の拘束を与える（１番目の分散とｉ＝２、３、…、Ｂ番目の分散
が等しいため）。Ｂ≧３においてＢ（Ｂ−１）／２＞Ｂ−１であることから、求めたいパラメタの個数が拘束条件の個数を上回ることが分かる。つまり条件を満たす回転行列は無限個存在する。
【００９２】
非特許文献６に記載された等方ハッシングでは、Ｂ−１個の拘束以外の拘束を与えることをしておらず、従って、無限個ある変換行列のうちの１つを無作為に選択しているに過ぎず、写像される空間においてベクトルの共分散行列の対角成分が全て等しくなること以上の効果は持たない。
【００９３】
本実施の形態の特徴変換装置は、このＢ−１個の拘束に加え、付加的な拘束条件を課すことで解を一意（over-constrained）に定める。これにより、写像される空間においてベクトルの共分散行列の対角成分が全て等しいだけでなく、さらに写像の際の変換行列と特徴ベクトルの積和演算の計算量を低減可能である変換行列が得られる。
【００９４】
変換行列と特徴ベクトルの積和演算の計算量を低減するには２種類の方法がある。１つは類似度の計算精度をそれほど損なうことなくビット長を短くすること、もう１つは変換行列を疎行列にすることである。前者は、特徴ベクトルにノイズが重畳されたときに異なるビットが割り当てられてしまう事象の発生確率（エラー率）を最小化することにより達成できる。後者は変換行列のＬ１ノルムを最小化すること（変換行列を疎にすること）により達成できる。すなわち、付加的な拘束条件としては、ノイズに対する頑健性の向上（エラー率最小化）や、変換行列の疎行列化（Ｌ１ノルム最小化）がある。
【００９５】
エラー率を最小化する方法としては、第１の実施の形態で説明した方法を採用できる。本実施の形態では、写像される空間においてベクトルの共分散行列の対角成分を全て等しくさせることに加えて、疎であるという付加的拘束を課して変換行列を生成する方法について説明する。
【００９６】
本実施の形態の特徴演算装置の構成は、図１に示した第１の実施の形態の特徴演算装置１００と同じである。本実施の形態の特徴演算装置は、変換行列生成部１３における処理が、第１の実施の形態のそれと異なる。本実施の形態の変換行列生成部１３は、以下の戦略で変換行列を生成する。
【００９７】
最終的に求めたいＮ×Ｂの変換行列Ｗを直接求める代わりに、Ｎ×Ｎの回転行列Ｒを導入し、回転行列Ｒの最初のＢ列が変換行列Ｗを形成する問題を考える。つまり、回転行列Ｒの最初のＢ列を疎にする必要がある。
【００９８】
Ｎ次元の回転行列ＲはＳＯ（Ｎ）と呼ばれるリー群を形成し、（２４）式で書き下せることが知られている。
【数２８】
2014149808.tif 000030
ここで、ＭijはＮ×Ｎの行列であり、（２５）式で定義される。
【数２９】
2014149808.tif 000031
【００９９】
ここで、δijは、クロネッカーのデルタである。αij（ｊ＞ｉ）は、回転行列Ｒのパラメタ（Ｎ次元の回転行列Ｒが持つＮ（Ｎ−１）／２個のパラメタ）である。上記の条件を
満たす回転行列Ｒを生成するために、適切なαijを探索することを考える。
【０１００】
疎であり、かつ写像される空間においてベクトルの共分散行列の対角成分を全て等しくさせるような変換行列Ｗを生成するために、（２６）式、（２７）式、及び（２８）式で定義されるコスト関数Ｒ*を考える。
【数３０】
2014149808.tif 000032
【数３１】
2014149808.tif 000033
【数３２】
2014149808.tif 000034
ここで、Ｌ0は、特徴ベクトルの共分散行列の最初のＢ個の分散がそれぞれ
【数３３】
2014149808.tif 000035
に等しいときに最小となる。Ｌ1の値を下げることで回転行列Ｒを疎行列化することがで
きる。（２６）式は、Ｌ0とηＬ1の和の最小化を意味する。ここで、ηは、コスト関数のチューニングパラメータである。なお、このコスト関数Ｒ*で、η＝０と置くと、等方ハ
ッシングと同一となり、このときの解はＬ0＝０を厳密に満たすことが示されている。
【０１０１】
ｉ＝Ｂ＋１，…，Ｎ、ｊ＝Ｂ＋１，…，Ｎであるαijは、コスト関数Ｒ*には現れない
。従って、これらのパラメタは任意であるため、ここでは全て０とおく。
【０１０２】
変換行列生成部１３は、コスト関数Ｒ*を最小化することで、変換行列Ｗを探索する。
コスト関数Ｒ*はαの非線形関数であるため、変換行列生成部１３は、勾配法により解を
探索する。コストの勾配は、以下の（２９）〜（３３）式によって与えられる。
【数３４】
2014149808.tif 000036
【数３５】
2014149808.tif 000037
【数３６】
2014149808.tif 000038
【数３７】
2014149808.tif 000039
【数３８】
2014149808.tif 000040
【０１０３】
図４は、変換行列生成部１３による変換行列生成の処理のフロー図である。変換行列生成部１３は、まず、回転行列ＲをＮ×Ｎの単位行列とおき（ステップＳ４１）、ＣR＝Ｃ
とおく（ステップＳ４２）。次に、変換行列生成部１３は、αに関する一次微分を（２９）〜（３２）式を使って計算する（ステップＳ４３）。そして、変換行列生成部１３は、
【数３９】
2014149808.tif 000041
として、（２４）式により回転行列Ｒを計算する。即ち、勾配法によって回転行列Ｒを計算する（ステップＳ４４）。
【０１０４】
次に、変換行列生成部１３は、ＣRを（３３）式により計算する（ステップＳ４５）。
そして、変換行列生成部１３は、αが収束したかを判断し（ステップＳ４６）、αが収束していない場合には（ステップＳ４６にてＮＯ）、ステップＳ４３に戻り、αが収束するまでステップＳ４３〜ステップＳ４５を繰り返す。αが収束すると（ステップＳ４６にてＹＥＳ）、変換行列生成部１３は、
【数４０】
2014149808.tif 000042
として、変換行列Ｗijを求める（ステップＳ４７）。ここで、ｒは固定の実数である（例：ｒ＝０．０１）。すなわち、変換行列生成部１３は、Ｒijの絶対値がｒより小さければそれを０に丸める処理を行う。
【０１０５】
ビットコードへ変換部１２は、（１２）式を用いて特徴ベクトルをビットコードに変換する。このとき、ｘは特徴ベクトルからその平均ベクトルを引いたベクトルとする。
【０１０６】
図５は、本発明の第２の実施の形態の特徴変換装置によって得られる線形変換後の共分散行列（ＲTＣＲ）の例を示す図である。この例において、Ｎ＝１３６次元であり、Ｂ＝
９６次元である。この行列の左上のＢ×Ｂの部分は、対角成分の分散がそろっている。なお、このＢ×Ｂの部分以外の部分は補空間であり、その成分については関知する必要がない。
【０１０７】
図６は、本発明の第２の実施の形態の特徴変換装置によって得られる回転行列（Ｒ）の例を示す図である。図６の左側のＮ行Ｂ列の行列が変換行列Ｗとなる。この変換行列Ｗにおいて、ほとんどの要素が０であり、十分に疎行列化されていることが分かる。
【０１０８】
以上説明したように、本実施の形態の変換行列生成部１３は、変換行列Ｗを直接求めずに、Ｎ次元の回転行列Ｒについて問題を解き、得られた回転行列Ｒの最初のＢ列を変換行
列Ｗとすることで変換行列Ｗを得る。一方、非特許文献６に記載された等方ハッシングは、直接Ｗを求めている。通常の等方ハッシングのように、主成分分析により次元削減されたＢ次元の空間で、直交行列を探索したのでは、変換行列を充分に疎にすることはできない。なぜなら探索の次元が小さいため、疎でありかつ分散が等しい解が存在する可能性が少ないためである。本実施の形態の変換行列生成部１３は、元の大きな次元で回転を考えることで、解の探索の範囲を広げるばかりでなく、補空間への信号のパワーの流出を許す自由度があることになるため、容易に疎行列化を実現できる。
【０１０９】
また、本実施の形態の変換行列生成部１３は、回転行列Ｒを求めるにあたり、回転行列Ｒそのものを探索するのではなく、回転群ＳＯ（Ｎ）のパラメタ（オイラー角）を探索する。これに対して、既存の手法は全て行列そのものを探索している。本実施の形態の変換行列生成部１３は、回転群のパラメタを探索するので、行列の要素を全て探索することに比べ、その探索空間の小ささなり、計算が効率的になる。また、得られる行列がＳＯ（Ｎ）に厳密に属することを自動的に保障される。
【０１１０】
さらに、ハミング距離の類似度を考えたとき、ビットの符号の向きは任意でよいため、Ｏ（Ｎ）は冗長であり、ＳＯ（Ｎ）を考えるだけで十分である。そこで、本実施の形態の変換行列生成部１３は、変換行列Ｗを回転群ＳＯ（Ｎ）の中から探索する。これにより、変換行列を探索する処理負荷を軽減できる。
【０１１１】
以上のように、本発明の第２の実施の形態の特徴演算装置によれば、多数の特徴量の間の類似度の計算を大幅に高速化できることから、これまで計算速度の観点から不可能とされていた大規模画像検索などが実現可能となる。また、元の信号が持つパワーあたりに一定のビットを割り当てることで、類似度の精度を担保するばかりでなく、付加的拘束によりビットコードへの変換速度を上げることが可能である。そして、ビットコードへの変換にかかる計算量が低く済むことから、携帯電話などの非力なプロセッサでの利用も可能である。
【産業上の利用可能性】
【０１１２】
本発明は、ビット割り当てのエラー発生率を小さく抑えることができる変換行列を得ることができ、特徴ベクトルをこの変換行列でビットコードに変換することで、少ないビット数で類似した特徴を正確に判断できるビットコードをえることができるという効果を有し、画像や文章などのデジタル情報の特徴を識別や検索などの演算に有利な特徴に変換する特徴変換装置等として有用である。
【０１１３】
また、本発明は、多数の特徴量の間の類似度の計算を大幅に高速化できることから、これまで計算速度の観点から不可能であるとされていた大規模画像検索などが実現可能となり、元の信号が持つパワーあたりに一定のビットを割り当てることで、類似度の精度を担保するとともに、付加的拘束によりビットコードへの変換速度を上げることができるという効果を有し、画像や文章などのデジタル情報の特徴を識別や検索などの演算に有利な特徴に変換する特徴変換装置等として有用である。特にビットコードの変換に係る計算量が低く済むことから、携帯電話などの計算能力の低いプロセッサへの応用が有効である。
【符号の説明】
【０１１４】
１００  特徴演算装置
１０  エンコーダ部（特徴変換装置）
１１  モーメント生成部
１２  ビットコード変換部
１３  変換行列生成部
２０  特徴ベクトル検索部
２１  ビットコード保管部
２２  ｋ−近傍探索部
２３  距離計算部
【図１】
2014149808.tif 000043
【図２】
2014149808.tif 000044
【図３】
2014149808.tif 000045
【図４】
2014149808.tif 000046
【図５】
2014149808.tif 000047
【図６】
2014149808.tif 000048