(57)【要約】  【課題】  特徴ベクトルがｄ次元の二値ベクトルｐ∈｛−１，１｝dである場合において、そのような特徴ベクトルとｄ次元の実数ベクトルｑ∈Ｒdとの間の内積（ｐTｑもしくはｑTｐ）の演算を高速に計算できる関連性判定装置を提供する。  【解決手段】  関連性判定装置としての特徴量演算装置１００は、二値化された特徴ベクトルｐ∈｛−１，１｝dを取得する特徴ベクトル二値化部１０３と、実数ベクトルｑ∈Ｒdを二値または三値の離散値のみから構成された要素を持つ複数の基底ベクトルｍi∈｛−１，１｝dの線形和に分解することで得られた複数の基底ベクトルｍi∈｛−１，１｝dを取得するデータベース１０７と、特徴ベクトルｐ∈｛−１，１｝dと複数の基底ベクトルｍi∈｛−１，１｝dの各々との内積計算を順次行うことで、実数ベクトルｑ∈Ｒdと特徴ベクトルｐ∈｛−１，１｝dとの関連性を判定するベクトル演算部１０６を備えている。【選択図】  図１
2014112358.tif 000002
【特許請求の範囲】
【請求項１】
二値化された特徴ベクトルを取得する特徴ベクトル取得部と、
実数ベクトルを二値または三値の離散値のみから構成された要素を持つ複数の基底ベクトルの線形和に分解することで得られた前記複数の基底ベクトルを取得する基底ベクトル取得部と、
前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算を順次行うことで、前記実数ベクトルと前記特徴ベクトルとの関連性を判定するベクトル演算部と
を備えたことを特徴とする関連性判定装置。
【請求項２】
前記特徴ベクトルと前記基底ベクトルとの内積計算は、−１及び１のみを要素としてもつ第１の二値ベクトルと−１及び１のみを要素としてもつ複数の第２の二値ベクトルとの内積計算を含むことを特徴とする請求項１に記載の関連性判定装置。
【請求項３】
前記第１の二値ベクトルは、前記特徴ベクトルであることを特徴とする請求項２に記載の関連性判定装置。
【請求項４】
前記第１の二値ベクトルは、前記特徴ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする請求項２に記載の関連性判定装置。
【請求項５】
前記第１の二値ベクトルは、その各要素を線形変換することで前記特徴ベクトルが得られるベクトルであることを特徴とする請求項２に記載の関連性判定装置。
【請求項６】
前記第２の二値ベクトルは、前記基底ベクトルであることを特徴とする請求項２ないし５のいずれか一項に記載の関連性判定装置。
【請求項７】
前記第２の二値ベクトルは、前記基底ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする請求項２ないし５のいずれか一項に記載の関連性判定装置。
【請求項８】
前記第２の二値ベクトルは、その各要素を線形変換することで前記基底ベクトルが得られるベクトルであることを特徴とする請求項２ないし５のいずれか一項に記載の関連性判定装置。
【請求項９】
前記特徴ベクトルと前記基底ベクトルとの内積計算は、−１及び１のみを要素としてもつ二値ベクトルと−１、０及び１のみを要素としてもつ複数の三値ベクトルとの内積計算を含むことを特徴とする請求項１に記載の関連性判定装置。
【請求項１０】
前記二値ベクトルは、前記特徴ベクトルであることを特徴とする請求項９に記載の関連性判定装置。
【請求項１１】
前記二値ベクトルは、前記特徴ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする請求項９に記載の関連性判定装置。
【請求項１２】
前記二値ベクトルは、その各要素を線形変換することで前記特徴ベクトルが得られるベクトルであることを特徴とする請求項９に記載の関連性判定装置。
【請求項１３】
前記複数の三値ベクトルは、前記複数の基底ベクトルであることを特徴とする請求項９ないし１２のいずれか一項に記載の関連性判定装置。
【請求項１４】
前記複数の三値ベクトルは、前記複数の基底ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする請求項９ないし１２のいずれか一項に記載の関連性判定装置。
【請求項１５】
前記複数の三値ベクトルは、その各要素を線形変換することで前記複数の基底ベクトルが得られるベクトルであることを特徴とする請求項９ないし１２のいずれか一項に記載の関連性判定装置。
【請求項１６】
前記ベクトル演算部は、前記第１の二値ベクトルと前記第２の二値ベクトルとの排他的論理和をとることで、前記第１の二値ベクトルと前記第２の二値ベクトルとの内積を計算することを特徴とする請求項２に記載の関連性判定装置。
【請求項１７】
前記ベクトル演算部は、前記二値ベクトルと前記三値ベクトルとの内積計算において、前記三値ベクトルの０の要素を−１又は１の任意のいずれかに置換して０置換ベクトルを生成し、前記三値ベクトルの０の要素を−１に置換し、かつ０以外の要素を１に置換してフィルタベクトルを生成し、前記二値ベクトルと前記０置換ベクトルとの排他的論理和と前記フィルタベクトルとの論理積をとることで、前記二値ベクトルと前記三値ベクトルとの間の非０で異なる要素の要素数Ｄｆｉｌｔｅｒｄ＿ｈａｍｍｉｎｇを求め、前記要素数Ｄｆｉｌｔｅｒｄ＿ｈａｍｍｉｎｇ及び非０の要素数を前記二値ベクトルの要素数から引くことで、前記二値ベクトルと前記三値ベクトルとの間の非０で同一の要素の要素数を求め、前記二値ベクトルと前記三値ベクトルとの間の非０で同一の要素の要素数から前記二値ベクトルと前記三値ベクトルとの間の非０で異なる要素の要素数を引くことで、前記二値ベクトルと前記三値ベクトルとの内積を求めることを特徴とする請求項９に記載の関連性判定装置。
【請求項１８】
前記複数の基底ベクトルは、前記実数ベクトルと、前記複数の基底ベクトルの線形和との差分を分解誤差として、前記分解誤差が最小になるように、求められることを特徴とする請求項１に記載の関連性判定装置。
【請求項１９】
前記複数の基底ベクトルは、前記実数ベクトルと前記特徴ベクトルとの内積と、前記複数の基底ベクトルの線形和と前記特徴ベクトルとの内積との差分を分解誤差として、前記分解誤差が最小になるように、求められることを特徴とする請求項１に記載の関連性判定装置。
【請求項２０】
前記複数の基底ベクトルは、前記複数の基底ベクトルの要素を固定して、前記分解誤差が最小になるように、前記複数の基底ベクトルに係る複数の係数を更新する第１の更新と、前記複数の係数を固定して、前記分解誤差が最小になるように前記基底ベクトルの要素を更新する第２の更新とを繰り返すことで、前記複数の係数とともに求められることを特徴とする請求項１８又は１９に記載の関連性判定装置。
【請求項２１】
前記複数の基底ベクトルは、前記分解誤差の減少量が所定の値以下になるまで前記第１の更新と前記第２の更新を繰り返すことで求められることを特徴とする請求項２０に記載の関連性判定装置。
【請求項２２】
前記複数の基底ベクトルは、前記複数の基底ベクトル及び前記複数の係数の初期値を変えて、複数とおりの前記複数の基底ベクトル及び前記複数の係数を求め、前記分解誤差が最小となる前記複数の基底ベクトル及び前記複数の係数を採用することで求められることを特徴とする請求項１８又は１９に記載の関連性判定装置。
【請求項２３】
前記複数の基底ベクトルに係る複数の係数は離散値であることを特徴とする請求項１８又は１９に記載の関連性判定装置。
【請求項２４】
前記複数の基底ベクトルは、前記実数ベクトルの要素の平均値を前記実数ベクトルの各要素から引いたオフセット実数ベクトルを前記基底ベクトルの線形和に分解することで求められることを特徴とする請求項１８又は１９に記載の関連性判定装置。
【請求項２５】
前記ベクトル演算部は、前記特徴ベクトルと前記基底ベクトルとの前記内積計算を実行する度に、前記内積計算の結果の合計と、前記実数ベクトルと前記特徴ベクトルとが関連している場合に前記積算値がとり得る範囲を求め、前記合計が前記とり得る範囲外である場合に、前記内積計算を打ち切って、前記特徴ベクトルと前記基底ベクトルとの内積と所定の閾値との大小関係を判定することを特徴とする請求項１に記載の関連性判定装置。
【請求項２６】
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、当該基底ベクトルまでの前記内積計算の結果の合計が、最大側早期判定用閾値より大きい場合に、前記内積計算を打ち切って、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より大きいと判定することを特徴とする請求項２５に記載の関連性判定装置。
【請求項２７】
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る最小値を学習によって求めて、前記閾値から前記内積計算を行なっていない前記基底ベクトルと前記特徴ベクトルとの内積がとり得る値の最小値の合計を引いて、前記最大側早期判定用閾値を求めることを特徴とする請求項２６に記載の関連性判定装置。
【請求項２８】
前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る最小値は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る値のうちの最小側の上位の所定の割合にある値であることを特徴とする請求項２７に記載の関連性判定装置。
【請求項２９】
前記最小側早期判定用閾値は、前記実数ベクトルと前記特徴ベクトルとが関連している場合にとり得る前記内積計算の結果の合計の最小値であることを特徴とする請求項２６ないし２８のいずれか一項に記載の関連性判定装置。
【請求項３０】
前記ベクトル演算部は、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より大きいと判定したときに、前記特徴ベクトルと前記基底ベクトルとは関連していないと判定することを特徴とする請求項２９に記載の関連性判定装置。
【請求項３１】
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、当該基底ベクトルまでの前記内積計算の結果の合計が、最小側早期判定用閾値より小さい場合に、前記内積計算を打ち切って、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より小さいと判定することを特徴とする請求項２５ないし３０のいずれか一項に記載の関連性判定装置。
【請求項３２】
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る最大値を学習によって求めて、前記閾値から前記内積計算を行なっていない前記基底ベクトルと前記特徴ベクトルとの内積がとり得る値の最大値の合計を引いて、前記最小側早期判定用閾値を求めることを特徴とする請求項３１に記載の関連性判定装置。
【請求項３３】
前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る最大値は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る値のうちの最大側の上位の所定の割合にある値であることを特徴とする請求項３２に記載の関連性判定装置。
【請求項３４】
前記最小側早期判定用閾値は、前記実数ベクトルと前記特徴ベクトルとが関連している場合にとり得る前記内積計算の結果の合計の最小値であることを特徴とする請求項３１ないし３３のいずれか一項に記載の関連性判定装置。
【請求項３５】
前記ベクトル演算部は、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より小さいと判定したときに、前記特徴ベクトルと前記基底ベクトルとは関連していないと判定することを特徴とする請求項３４に記載の関連性判定装置。
【請求項３６】
前記ベクトル演算部は、係数の絶対値が大きい前記基底ベクトルから順に前記内積計算を行うことを特徴とする請求項２５ないし３５のいずれか一項に記載の関連性判定装置。
【請求項３７】
前記ベクトル演算部は、前記特徴ベクトルと、分解された前記実数ベクトルをそれぞれ複数の部分ベクトルに分解し、前記特徴ベクトルの分解ベクトルと分解された前記実数ベクトルの部分ベクトルとの内積が、前記閾値よりも大きくなるか否か、及び／又は前記閾値よりも小さくなるか否かを判断することを特徴とする請求項１に記載の関連性判定装置。
【請求項３８】
前記特徴ベクトルは、ＨｏＧ特徴量であり、
前記実数ベクトルは、線形ＳＶＭの重みベクトルであり、
前記ベクトル演算部は、前記関連性の判定として、線形ＳＶＭによって前記特徴ベクトルの識別を行なう
ことを特徴とする請求項１ないし３７のいずれか一項に記載の関連性判定装置。
【請求項３９】
前記特徴ベクトルは、ｋ−ｍｅａｎｓクラスタリングによるクラスタリングの対象となるベクトルであり、
前記実数ベクトルは、ｋ−ｍｅａｎｓクラスタリングにおける代表ベクトルであり、
前記ベクトル演算部は、前記関連性の判定として、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なう
ことを特徴とする請求項１ないし３７のいずれか一項に記載の関連性判定装置。
【請求項４０】
前記特徴ベクトルは、ｋ−ｍｅａｎｓ  ｔｒｅｅによる近似最近傍探索の対象となるベクトルであり、
前記実数ベクトルは、ｋ−分木のノードに登録されている代表ベクトルであり、
前記ベクトル演算部は、前記関連性の判定として、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なう
ことを特徴とする請求項１ないし３７のいずれか一項に記載の関連性判定装置。
【請求項４１】
前記特徴ベクトルは、画像の特徴量を表すベクトルであることを特徴とする請求項３８ないし４０のいずれか一項に記載の関連性判定装置。
【請求項４２】
コンピュータを、請求項１ないし４１のいずれか一項に記載の関連性判定装置として機能させるための関連性判定プログラム。
【請求項４３】
二値化された特徴ベクトルを取得する特徴ベクトル取得ステップと、
実数ベクトルを二値または三値の離散値のみから構成された要素を持つ複数の基底ベクトルの線形和に分解して得られた前記複数の基底ベクトルを取得する基底ベクトル取得ステップと、
前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算を順次行うことで、前記実数ベクトルと前記特徴ベクトルとの関連性を判定するベクトル演算ステップと
を含むことを特徴とする関連性判定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像、音声、文字等のコンテンツの特徴ベクトルを用いた演算処理を行う関連性判定装置、関連性判定プログラム、及び関連性判定方法に関し、特に、実数ベクトルと二値ベクトルに変換された特徴ベクトルとの内積の計算を含むベクトル演算によって特徴ベクトルと実数ベクトルとの関連性の判定を行う関連性判定装置、関連性判定プログラム、及び関連性判定方法に関するものである。
【背景技術】
【０００２】
従来より、画像検索、音声認識、文章検索、パターン認識など、多くの分野で特徴量が用いられている。特徴量とは、画像、音声、文章などの情報を、計算機で扱いやすいように変換したものである。特徴量は、Ｄ次元のベクトル（特徴ベクトル）で表される。
【０００３】
特徴ベクトルを用いた演算を行うことで、例えば、コンテンツの類似度を判定することができる。すなわち、画像αの特徴ベクトルと、画像βの特徴ベクトルの距離が小さければ、αとβは似ているとみなすことができる。同様に、音声波形αの特徴ベクトルと、音声波形βの特徴ベクトルとの距離が小さければ、αとβは似ているとみなすことができる。このように、音声認識、文章検索、パターン認識等の情報処理では、情報を特徴ベクトルに変換して、特徴ベクトル同士を比較して、その距離を求めることにより情報の類似度を判断する。
【０００４】
特徴ベクトル間の距離の尺度としては、Ｌ１ノルム、Ｌ２ノルム、ベクトル間角度などが用いられる。これらは、特徴ベクトルｘ，ｙ∈ＲDについて、次のように計算できる。
Ｌ１ノルム
【数１】
2014112358.tif 000003
Ｌ２ノルム
【数２】
2014112358.tif 000004
ベクトル間角度
【数３】
2014112358.tif 000005
【０００５】
特徴ベクトルが実数ベクトルである場合には、以下のような問題がある。まず、２つの特徴ベクトルｘ，ｙ∈ＲDの間の距離の計算が遅くなるという問題がある。例えば、Ｌ２ノルムの二乗を距離の尺度として用いる場合、
【数４】
2014112358.tif 000006
であるから、Ｄ回の引き算、Ｄ回の乗算、Ｄ−１回の加算が必要である。特に、特徴ベクトルが浮動小数で表現される場合には、この計算負荷は非常に高くなる。特徴ベクトルが高次元になれば、この計算負荷はさらに高くなる。
【０００６】
また、大量のメモリを消費する点も問題となる。特徴ベクトルを４バイトの単精度実数で表現する場合、Ｄ次元の特徴ベクトルは４Ｄバイトのメモリを消費する。特徴ベクトルが高次元になれば、このメモリ消費量は大きくなる。大量の特徴ベクトルを扱う場合、扱う特徴ベクトルの数だけメモリを消費することになる。
【０００７】
そこで近年、特徴ベクトルを０と１の列から成るバイナリコードに変換することにより、これら２つの問題を解決する手法が提案されている。代表的な手法として、ランダムプロジェクション（random projection、非特許文献１参照）、ベリースパースランダムプロジェクション（very sparse random projection、非特許文献２参照）、およびスペクトラルハッシング（Spectral Hashing、非特許文献３参照）がある。
【０００８】
これらの手法では、Ｄ次元の特徴ベクトルがｄビットのバイナリコードに変換される。この変換は、もともとの空間における距離が、変換後の空間におけるハミング距離と強く相関するように行われる（もともとの空間における距離と、変換後の空間におけるハミング距離と強く相関する根拠については、非特許文献１の１１２１ページのＬｅｍｍａ３．２を参照）。これによって、特徴ベクトル間の距離の計算を、バイナリコード同士のハミング距離計算で代用できるようになる。
【０００９】
なお、ハミング距離とは、二つのバイナリコードのうち、異なるビットの数を数えたものである。この計算は、二つのコードのＸＯＲをとった後に１が立っているビット数を数えるだけなので、非常に高速に行うことができる。多くの場合、バイナリコード変換によって、数十〜数百倍程度の高速化が可能である。また、特徴ベクトル間の距離の計算を、バイナリコード同士のハミング距離計算で代用することにより、もともと４Ｄバイトであったメモリの必要容量を、ｄ／８バイトまで削減できる。これにより、数十〜数百分の一にメモリ容量を節約できる。
【００１０】
抽出された特徴量をバイナリコードに変換して、さまざまなアルゴリズムを適用することで、コンテンツの検索や認識などが可能となる。例えば類似コンテンツを検索する場合には、あらかじめデータベースに登録されているコンテンツの特徴量を、すべてバイナリコードに変換しておく。また、入力クエリとして与えられたコンテンツの特徴量をバイナリコードに変換する。このとき、入力クエリのバイナリコードと、データベースに登録されているすべてのバイナリコードとの間のハミング距離を計算することで、入力クエリに類似するコンテンツを検索して出力できる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
バイナリコードはｄビットの０と１の列からなる。これを、各要素が−１及び１の二値のみを取るｄ次元のベクトルと考えることもできる。以下の説明における混乱を避けるために、「バイナリコード」と「二値ベクトル」という用語について、以下のように区別をする。「バイナリコード」は、０と１の列からなるデータ表現である。例えば、Ｃ言語において１２８ビットのバイナリコードをメモリ上に格納する場合は、符号無し整数（unsigned char）型の１６要素分の配列を用意すればよい（８ｂｉｔ×１６＝１２８ｂｉｔ）。
【００１３】
一方、「二値ベクトル」は、各要素が二値のみを取るベクトルである。例えば、二値ベクトルを各要素が−１及び１のみをとるベクトルとする場合には、バイナリコード「０１１０１１１０」に対応する二値ベクトルは、（−１，１，１，−１，１，１，１，−１）Tである。もちろん、各要素が０及び１の二値のみを取るベクトルも二値ベクトルであるし、さらには、各要素が任意のα及びβ（ここでα≠βである）の二値のみを取るベクトルも二値ベクトルである。ただし、「バイナリコード」と「二値ベクトル」の違いは、情報の表現に関するものであり、両者に本質的な違いはない。
【００１４】
特徴ベクトルを、各要素が−１及び１の二値のみを取るｄ次元の二値ベクトルに変換すれば、ＳＶＭ（サポートベクトルマシン）による識別処理や、ｋ−ｍｅａｎｓクラスタリングなど、さまざまな処理をバイナリコードに対しても適用できる。しかしながら、これらのケースではハミング距離による高速距離計算の恩恵を受けることができないことがある。すなわち、アルゴリズムによっては、バイナリコード変換による高速距離計算の恩恵を受けられないことがある。
【００１５】
バイナリコード変換による高速距離計算の恩恵を受けられない例として、以下では、識別器（Classifier）による認識処理およびｋ−ｍｅａｎｓクラスタリングを説明する。まず、識別器による認識処理については、例えば、二値ベクトルｘ∈｛−１，１｝dを２クラスに識別する問題に対して、線形ＳＶＭ（線形サポートベクトルマシン）を適用することを考える。線形ＳＶＭでは以下の式を評価する。
ｆ（ｘ）＝ｗTｘ＋ｂ
ｆ（ｘ）が正ならばｘはクラスＡに属し、ｆ（ｘ）が負ならばｘはクラスＢに属するものとして識別する。 ｗは、重みパラメータであって、ｗ∈Ｒdである。ｂは、バイアスパラメータであって、ｂ∈Ｒ1である。パラメータｗ及びｂは、学習用に用意した特徴量を用いて、学習処理により自動的に決定される。
【００１６】
ここで、学習用に用意した特徴量が二値ベクトルであっても、ｗ∈Ｒdは二値にならず、実数値になってしまう。ｆ（ｘ）の計算にはｗTｘが含まれているが、ｘが二値である一方でｗが実数値のベクトルであるため、ｗTｘの計算には、浮動小数点演算が必要になってしまう。このように、ＳＶＭを適用する識別器による認識処理では、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。
【００１７】
次に、二値ベクトルに対して、ｋ−ｍｅａｎｓクラスタリングを適用する場合、すなわち、ｄ次元の二値ベクトルがＮ個与えられたとき、互いに距離が近い二値ベクトルをまとめたｋ個のクラスタを求める問題を考える。ｋ−ｍｅａｎｓとは、次の手順によりｋ個のクラスタと代表ベクトルを算出するアルゴリズムである。
【００１８】
ステップ１：Ｎ個の特徴量からｋ個をランダムに選出し、これをクラスタの代表ベクトルとする。
ステップ２：入力として与えられたＮ個の特徴量それぞれについて、最も距離が近い代表ベクトルを求める。
ステップ３：各代表ベクトルに所属する特徴量の平均を計算し、これを新しい代表ベクトルとする。
ステップ４：ステップ２、ステップ３を収束するまで繰り返す。
【００１９】
ｋ−ｍｅａｎｓクラスタリングにおいて問題となるのは、ステップ３において、新しい代表ベクトルが二値ベクトルの平均で定義される点である。入力として与えられたデータが二値ベクトルであっても、平均の演算により、代表ベクトルは実数のベクトルになる。そのため、ステップ２における距離計算では、二値ベクトルと実数ベクトルとの間の距離を求めなければならなくなる。つまり、浮動小数点演算が必要になってしまう。このように、ｋ−ｍｅａｎｓクラスタリングにおいても、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。
【００２０】
上記のように、識別器（Classifier）による認識処理やｋ−ｍｅａｎｓクラスタリングでは、特徴ベクトルを二値ベクトルとすることによる計算高速化の恩恵を受けることができない。その理由は、いずれもｄ次元の二値ベクトルｐ∈｛−１，１｝dと、ｄ次元の実数ベクトルｑ∈Ｒdとの内積演算が必要であるという点にある。なお、ｋ−ｍｅａｎｓクラスタリングで必要なのは、ｄビットの二値ベクトルｐ∈｛−１，１｝dと、ｄ次元の実数ベクトルｑ∈Ｒdとの間の「距離」であるが、これも結局のところ、ｐTｑという内積の演算に帰着される。なぜなら、ｐとｑとの間のユークリッド距離の二乗は、下式で表現されるからである。
【数５】
2014112358.tif 000007
【００２１】
よって、識別器による認識処理においてもｋ−ｍｅａｎｓクラスタリングにおいても、二値ベクトルとｄ次元の実数ベクトルとの内積の演算を高速化することこそが、問題の解決につながる。
【００２２】
そこで、本発明は、特徴ベクトルがｄ次元の二値ベクトルｐ∈｛−１，１｝dである場合において、そのような特徴ベクトルとｄ次元の実数ベクトルｑ∈Ｒdとの間の内積（ｐTｑもしくはｑTｐ）の演算を高速に行うことを目的とする。
【課題を解決するための手段】
【００２３】
本発明の第１の態様の関連性判定装置は、二値化された特徴ベクトルを取得する特徴ベクトル取得部と、実数ベクトルを二値または三値の離散値のみから構成された要素を持つ複数の基底ベクトルの線形和に分解することで得られた前記複数の基底ベクトルを取得する基底ベクトル取得部と、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算を順次行うことで、前記実数ベクトルと前記特徴ベクトルとの関連性を判定するベクトル演算部とを備えた構成を有している。
【００２４】
本発明の第２の態様の関連性判定装置は、第１の態様の関連性判定装置において、前記特徴ベクトルと前記基底ベクトルとの内積計算は、−１及び１のみを要素としてもつ第１の二値ベクトルと−１及び１のみを要素としてもつ複数の第２の二値ベクトルとの内積計算を含むことを特徴とする。
【００２５】
本発明の第３の態様の関連性判定装置は、第２の態様の関連性判定装置において、前記第１の二値ベクトルは、前記特徴ベクトルであることを特徴とする。
【００２６】
本発明の第４の態様の関連性判定装置は、第２の態様の関連性判定装置において、前記第１の二値ベクトルは、前記特徴ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする。
【００２７】
本発明の第５の態様の関連性判定装置は、第２の態様の関連性判定装置において、前記第１の二値ベクトルは、その各要素を線形変換することで前記特徴ベクトルが得られるベクトルであることを特徴とする。
【００２８】
本発明の第６の態様の関連性判定装置は、第２ないし第５のいずれか一の態様の関連性判定装置において、前記第２の二値ベクトルは、前記基底ベクトルであることを特徴とする。
【００２９】
本発明の第７の態様の関連性判定装置は、第２ないし第５のいずれか一の態様の関連性判定装置において、前記第２の二値ベクトルは、前記基底ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする。
【００３０】
本発明の第８の態様の関連性判定装置は、第２ないし第５のいずれか一の態様の関連性判定装置において、前記第２の二値ベクトルは、その各要素を線形変換することで前記基底ベクトルが得られるベクトルであることを特徴とする。
【００３１】
本発明の第９の態様の関連性判定装置は、第１の態様の関連性判定装置において、前記特徴ベクトルと前記基底ベクトルとの内積計算は、−１及び１のみを要素としてもつ二値ベクトルと−１、０及び１のみを要素としてもつ複数の三値ベクトルとの内積計算を含むことを特徴とする。
【００３２】
本発明の第１０の態様の関連性判定装置は、第９の態様の関連性判定装置において、前記二値ベクトルは、前記特徴ベクトルであることを特徴とする。
【００３３】
本発明の第１１の態様の関連性判定装置は、第９の態様の関連性判定装置において、前記二値ベクトルは、前記特徴ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする。
【００３４】
本発明の第１２の態様の関連性判定装置は、第９の態様の関連性判定装置において、前記二値ベクトルは、その各要素を線形変換することで前記特徴ベクトルが得られるベクトルであることを特徴とする。
【００３５】
本発明の第１３の態様の関連性判定装置は、第９ないし１２のいずれか一の態様の関連性判定装置において、前記複数の三値ベクトルは、前記複数の基底ベクトルであることを特徴とする。
【００３６】
本発明の第１４の態様の関連性判定装置は、第９ないし１２のいずれか一の態様の関連性判定装置において、前記複数の三値ベクトルは、前記複数の基底ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする。
【００３７】
本発明の第１５の態様の関連性判定装置は、第９ないし１２のいずれか一の態様の関連性判定装置において、前記複数の三値ベクトルは、その各要素を線形変換することで前記複数の基底ベクトルが得られるベクトルであることを特徴とする。
【００３８】
本発明の第１６の態様の関連性判定装置は、第２の態様の関連性判定装置において、前記ベクトル演算部は、前記第１の二値ベクトルと前記第２の二値ベクトルとの排他的論理和をとることで、前記第１の二値ベクトルと前記第２の二値ベクトルとの内積を計算することを特徴とする。
【００３９】
本発明の第１７の態様の関連性判定装置は、第９の態様の関連性判定装置において、前記ベクトル演算部は、前記二値ベクトルと前記三値ベクトルとの内積計算において、前記三値ベクトルの０の要素を−１又は１の任意のいずれかに置換して０置換ベクトルを生成し、前記三値ベクトルの０の要素を−１に置換し、かつ０以外の要素を１に置換してフィルタベクトルを生成し、前記二値ベクトルと前記０置換ベクトルとの排他的論理和と前記フィルタベクトルとの論理積をとることで、前記二値ベクトルと前記三値ベクトルとの間の非０で異なる要素の要素数Ｄｆｉｌｔｅｒｄ＿ｈａｍｍｉｎｇを求め、前記要素数Ｄｆｉｌｔｅｒｄ＿ｈａｍｍｉｎｇ及び非０の要素数を前記二値ベクトルの要素数から引くことで、前記二値ベクトルと前記三値ベクトルとの間の非０で同一の要素の要素数を求め、前記二値ベクトルと前記三値ベクトルとの間の非０で同一の要素の要素数から前記二値ベクトルと前記三値ベクトルとの間の非０で異なる要素の要素数を引くことで、前記二値ベクトルと前記三値ベクトルとの内積を求めることを特徴とする。
【００４０】
本発明の第１８の態様の関連性判定装置は、第１の態様の関連性判定装置において、前記複数の基底ベクトルは、前記実数ベクトルと、前記複数の基底ベクトルの線形和との差分を分解誤差として、前記分解誤差が最小になるように、求められることを特徴とする。
【００４１】
本発明の第１９の態様の関連性判定装置は、第１の態様の関連性判定装置において、前記複数の基底ベクトルは、前記実数ベクトルと前記特徴ベクトルとの内積と、前記複数の基底ベクトルの線形和と前記特徴ベクトルとの内積との差分を分解誤差として、前記分解誤差が最小になるように、求められることを特徴とする。
【００４２】
本発明の第２０の態様の関連性判定装置は、第１８又は１９の態様の関連性判定装置において、前記複数の基底ベクトルは、前記複数の基底ベクトルの要素を固定して、前記分解誤差が最小になるように、前記複数の基底ベクトルに係る複数の係数を更新する第１の更新と、前記複数の係数を固定して、前記分解誤差が最小になるように前記基底ベクトルの要素を更新する第２の更新とを繰り返すことで、前記複数の係数とともに求められることを特徴とする。
【００４３】
本発明の第２１の態様の関連性判定装置は、第２０の態様の関連性判定装置において、前記複数の基底ベクトルは、前記分解誤差の減少量が所定の値以下になるまで前記第１の更新と前記第２の更新を繰り返すことで求められることを特徴とする。
【００４４】
本発明の第２２の態様の関連性判定装置は、第１８又は１９の態様の関連性判定装置において、前記複数の基底ベクトルは、前記複数の基底ベクトル及び前記複数の係数の初期値を変えて、複数とおりの前記複数の基底ベクトル及び前記複数の係数を求め、前記分解誤差が最小となる前記複数の基底ベクトル及び前記複数の係数を採用することで求められることを特徴とする。
【００４５】
本発明の第２３の態様の関連性判定装置は、第１８又は１９の態様の関連性判定装置において、前記複数の基底ベクトルに係る複数の係数は離散値であることを特徴とする。
【００４６】
本発明の第２４の態様の関連性判定装置は、第１８又は１９の態様の関連性判定装置において、前記複数の基底ベクトルは、前記実数ベクトルの要素の平均値を前記実数ベクトルの各要素から引いたオフセット実数ベクトルを前記基底ベクトルの線形和に分解することで求められることを特徴とする。
【００４７】
本発明の第２５の態様の関連性判定装置は、第１の態様の関連性判定装置において、前記ベクトル演算部は、前記特徴ベクトルと前記基底ベクトルとの前記内積計算を実行する度に、前記内積計算の結果の合計と、前記実数ベクトルと前記特徴ベクトルとが関連している場合に前記積算値がとり得る範囲を求め、前記合計が前記とり得る範囲外である場合に、前記内積計算を打ち切って、前記特徴ベクトルと前記基底ベクトルとの内積と所定の閾値との大小関係を判定することを特徴とする。
【００４８】
本発明の第２６の態様の関連性判定装置は、第２５の態様の関連性判定装置において、前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、当該基底ベクトルまでの前記内積計算の結果の合計が、最大側早期判定用閾値より大きい場合に、前記内積計算を打ち切って、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より大きいと判定することを特徴とする。
【００４９】
本発明の第２７の態様の関連性判定装置は、第２６の態様の関連性判定装置において、前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る最小値を学習によって求めて、前記閾値から前記内積計算を行なっていない前記基底ベクトルと前記特徴ベクトルとの内積がとり得る値の最小値の合計を引いて、前記最大側早期判定用閾値を求めることを特徴とする。
【００５０】
本発明の第２８の態様の関連性判定装置は、第２７の態様の関連性判定装置において、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る最小値は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る値のうちの最小側の上位の所定の割合にある値であることを特徴とする。
【００５１】
本発明の第２９の態様の関連性判定装置は、第２６ないし２８のいずれか一の態様の関連性判定装置において、前記ベクトル演算部は、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より大きいと判定したときに、前記特徴ベクトルと前記基底ベクトルとは関連していないと判定することを特徴とする。
【００５２】
本発明の第３０の態様の関連性判定装置は、第２９の態様の関連性判定装置において、前記ベクトル演算部は、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より大きいと判定したときに、前記特徴ベクトルと前記基底ベクトルとは関連していないと判定することを特徴とする。
【００５３】
本発明の第３１の態様の関連性判定装置は、第２５ないし３０のいずれか一の態様の関連性判定装置において、前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、当該基底ベクトルまでの前記内積計算の結果の合計が、最小側早期判定用閾値より小さい場合に、前記内積計算を打ち切って、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より小さいと判定することを特徴とする。
【００５４】
本発明の第３２の態様の関連性判定装置は、第３１の態様の関連性判定装置において、前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る最大値を学習によって求めて、前記閾値から前記内積計算を行なっていない前記基底ベクトルと前記特徴ベクトルとの内積がとり得る値の最大値の合計を引いて、前記最小側早期判定用閾値を求めることを特徴とする。
【００５５】
本発明の第３３の態様の関連性判定装置は、第３２の態様の関連性判定装置において、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る最大値は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積がとり得る値のうちの最大側の上位の所定の割合にある値であることを特徴とする。
【００５６】
本発明の第３４の態様の関連性判定装置は、第３１ないし３３のいずれか一の態様の関連性判定装置において、前記最小側早期判定用閾値は、前記実数ベクトルと前記特徴ベクトルとが関連している場合にとり得る前記内積計算の結果の合計の最小値であることを特徴とする。
【００５７】
本発明の第３５の態様の関連性判定装置は、第３４の態様の関連性判定装置において、前記ベクトル演算部は、前記実数ベクトルと前記特徴ベクトルとの内積が前記閾値より小さいと判定したときに、前記特徴ベクトルと前記基底ベクトルとは関連していないと判定することを特徴とする。
【００５８】
本発明の第３６の態様の関連性判定装置は、第２５ないし３５のいずれか一の態様の関連性判定装置において、前記ベクトル演算部は、係数の絶対値が大きい前記基底ベクトルから順に前記内積計算を行うことを特徴とする。
【００５９】
本発明の第３７の態様の関連性判定装置は、第１の態様の関連性判定装置において、前記ベクトル演算部は、前記特徴ベクトルと、分解された前記実数ベクトルをそれぞれ複数の部分ベクトルに分解し、前記特徴ベクトルの分解ベクトルと分解された前記実数ベクトルの部分ベクトルとの内積が、前記閾値よりも大きくなるか否か、及び／又は前記閾値よりも小さくなるか否かを判断することを特徴とする。
【００６０】
本発明の第３８の態様の関連性判定装置は、第１ないし３７のいずれか一の態様の関連性判定装置において、前記特徴ベクトルは、ＨｏＧ特徴量であり、前記実数ベクトルは、線形ＳＶＭの重みベクトルであり、前記ベクトル演算部は、前記関連性の判定として、線形ＳＶＭによって前記特徴ベクトルの識別を行なうことを特徴とする。
【００６１】
本発明の第３９の態様の関連性判定装置は、第１ないし３７のいずれか一の態様の関連性判定装置において、前記特徴ベクトルは、ｋ−ｍｅａｎｓクラスタリングによるクラスタリングの対象となるベクトルであり、前記実数ベクトルは、ｋ−ｍｅａｎｓクラスタリングにおける代表ベクトルであり、前記ベクトル演算部は、前記関連性の判定として、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なうことを特徴とする。
【００６２】
本発明の第４０の態様の関連性判定装置は、第１ないし３７のいずれか一の態様の関連性判定装置において、前記特徴ベクトルは、ｋ−ｍｅａｎｓ  ｔｒｅｅによる近似最近傍探索の対象となるベクトルであり、前記実数ベクトルは、ｋ−分木のノードに登録されている代表ベクトルであり、前記ベクトル演算部は、前記関連性の判定として、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なうことを特徴とする。
【００６３】
本発明の第４１の態様の関連性判定装置は、第３８ないし４０のいずれか一の態様の関連性判定装置において、前記特徴ベクトルは、画像の特徴量を表すベクトルであることを特徴とする。
【００６４】
本発明の関連性判定プログラムは、コンピュータを、第１ないし４１のいずれか一の態様の関連性判定装置として機能させる構成を有している。
【００６５】
本発明の関連性判定方法は、二値化された特徴ベクトルを取得する特徴ベクトル取得ステップと、実数ベクトルを二値または三値の離散値のみから構成された要素を持つ複数の基底ベクトルの線形和に分解して得られた前記複数の基底ベクトルを取得する基底ベクトル取得ステップと、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算を順次行うことで、前記実数ベクトルと前記特徴ベクトルとの関連性を判定するベクトル演算ステップとを含む構成を有している。
【発明の効果】
【００６６】
本発明によれば、実数ベクトルは二値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【図面の簡単な説明】
【００６７】
【図１】本発明の第１の実施の形態の特徴量演算装置の構成を示すブロック図
【図２】本発明の第１の実施の形態における実数ベクトルの分解を示す図
【図３】本発明の第２の実施の形態における計算例を示す図
【図４】本発明の第３の実施の形態のベクトル演算部におけるカスケードによる閾値処理の高速化のフロー図
【図５】本発明の第４の実施の形態の物体認識装置の構成を示すブロック図
【図６】本発明の第５の実施の形態のｋ−ｍｅａｎｓクラスタリング装置の構成を示すブロック図
【発明を実施するための形態】
【００６８】
以下、本発明の実施の形態の特徴量演算装置について、図面を参照しながら説明する。
【００６９】
（第１の実施の形態）
図１は、本発明の実施の形態の特徴量演算装置１００の構成を示すブロック図である。特徴量演算装置１００は、コンテンツ取得部１０１と、特徴ベクトル生成部１０２と、特徴ベクトル二値化部１０３と、実数ベクトル取得部１０４と、実数ベクトル分解部１０５と、ベクトル演算部１０６と、データベース１０７とを備えている。
【００７０】
本実施の形態の特徴量演算装置１００は、後述するように、特徴ベクトルと辞書データとしてデータベースに保存された実数ベクトルとの内積演算を伴うベクトル演算によって、特徴ベクトルと実数ベクトルとの関連性を判定する関連性判定装置として機能する。即ち、特徴演算装置１００は、本発明の関連性判定装置に相当する。
【００７１】
関連性判定装置としての特徴量演算装置１００は、コンピュータが本発明の実施の形態の関連性判定プログラムを実行することにより実現される。関連性判定プログラムは、記録媒体に記録されて、記録媒体からコンピュータによって読み出されてもよいし、ネットワークを通じてコンピュータにダウンロードされてもよい。
【００７２】
コンテンツ取得部１０１は、画像データ、音声データ、文字データ等のコンテンツデータを取得する。これらのコンテンツデータは、外部機器から与えられるものであってもよく、コンテンツ取得部１０１で生成されるものであってもよい。例えば、コンテンツ取得部１０１がカメラであり、そこでコンテンツデータとして画像データが生成されてよい。
【００７３】
特徴ベクトル生成部１０２は、コンテンツ取得部１０１にて取得されたコンテンツデータからＤ次元の特徴ベクトルを生成する。例えばコンテンツが画像である場合には、特徴ベクトル生成部１０２は、画像の特徴量を抽出する。特徴ベクトル二値化部１０３は、特徴ベクトル生成部１０２で生成されたＤ次元の特徴ベクトルを二値化して、各要素が−１及び１の二値のみをとるｄ次元の二値ベクトルｐ∈｛−１，１｝dを生成する。
【００７４】
なお、コンテンツ取得部１０１、特徴ベクトル生成部１０２、及び特徴ベクトル二値化部１０３からなる構成は、最終的に二値化された特徴ベクトルを取得できる構成であればよく、例えば、コンテンツ取得部１０１及び特徴ベクトル１０２を備えずに、特徴ベクトル二値化部１０３が外部機器から特徴ベクトルを取得して、その取得した特徴ベクトルを二値化する構成であってよいし、また、外部機器から二値化された特徴ベクトルを直接取得する構成であってもよい。
【００７５】
実数ベクトル取得部１０４は、ｄ次元の実数ベクトルｑ∈Ｒdを取得する。実数ベクトルは、外部機器から与えられるものであってもよく、特徴量演算装置１００の図示しない記憶装置から読み出されるものであってもよく、実数ベクトル取得部１０４で生成されるものであってもよい。実数ベクトルは、その要素に浮動小数を含む実数を持つ。
【００７６】
実数ベクトル分解部１０５は、ｄ次元の実数ベクトルｑ∈Ｒdを、二値の基底ベクトルｍi∈｛−１，１｝dの線形和に分解する。具体的には、実数ベクトル分解部１０５は、ｄ次元の実数ベクトルｑ∈Ｒdを、下式（１）によって、二値の要素を持つ基底行列Ｍと実数の要素を持つ係数ベクトルｃに分解する。
【数６】
2014112358.tif 000008
ここで、Ｍ＝（ｍ1，ｍ2，…，ｍk）∈｛−１，１｝d×kであり、ｃ＝（ｃ1，ｃ2，…，ｃk）T∈Ｒkである。すなわち、基底行列Ｍは、ｋ個の基底ベクトルｍiからなり、ここで、基底ベクトルｍiは、要素が−１及び１のみをとるｄ次元の二値ベクトルであり、従って、基底行列Ｍは、要素が−１及び１のみをとるｄ行ｋ列の二値行列である。また、係数ベクトルｃは、ｋ個の基底ベクトルに係る実数の係数を要素として持つｋ次元の実数ベクトルである。もちろん、ｑとＭｃはなるべく一致するように分解することが好ましいが、誤差を含んでもよい。
【００７７】
（第１の分解手法）
実数ベクトル分解部１０５は、誤差最少化によって実数ベクトルを分解する。第１の分解手法の手順は、以下のとおりである。
（１）基底行列Ｍ及び係数ベクトルｃをランダムに初期化する。
（２）基底行列Ｍを固定して、分解の誤差
【数７】
2014112358.tif 000009
が最小になるように係数ベクトルｃを更新する。これは、最小二乗法により求めることができる。
（３）係数ベクトルｃを固定して、分解の誤差
【数８】
2014112358.tif 000010
が最小になるように基底行列Ｍを更新する。この最小化アルゴリズムについては、後に詳しく述べる。
（４）収束するまで（２）及び（３）を繰り返す。例えば、
【数９】
2014112358.tif 000011
の減少量が一定値以下になったとき、収束したと判定する。
（５）ステップ（１）〜ステップ（４）により得た解を候補として保持する。
（６）ステップ（１）〜ステップ（５）を繰り返し、最も
【数１０】
2014112358.tif 000012
を小さくできた候補基底行列Ｍ及びｃを最終結果として採用する。なお、このステップ（１）〜ステップ（５）の繰り返しはなくてもよいが、複数回繰り返すことで、初期値依存の問題を回避できる。
【００７８】
次に、ステップ（３）における基底行列Ｍの更新処理を説明する。図２は、式（１）を図式化したものである。図２の破線枠で囲ったように、基底行列Ｍのｉ行目の行ベクトルの要素は、実数ベクトルｑのｉ番目の要素のみに依存する。基底行列Ｍのｉ行目の行ベクトルは、本実施の形態のように二値分解の場合は２k通りしか存在しない（なお、後述の第２の実施の形態の三値分解の場合にも３k通りしか存在しない）。よって、実数ベクトル分解部１０５は、これらをすべて網羅的にチェックし、分解誤差
【数１１】
2014112358.tif 000013
を最小化する行ベクトルを採用する。これを基底行列Ｍのすべての行ベクトルに対して適用して、基底行列Ｍの要素を更新する。
【００７９】
（第２の分解手法）
次に、第２の分解手法を説明する。第１の分解手法では、分解誤差を
【数１２】
2014112358.tif 000014
として定義し、この分解誤差を最小化することを考えた。しかしながら、実数ベクトルを基底ベクトルの線形和に近似した後に実際に近似をしたいのは、特徴ベクトルと実数ベクトルの内積ｐTｑである。
【００８０】
そこで、第２の分解手法では、特徴ベクトルｐをあらかじめＮ個集め、これをまとめたものをＰ∈Ｒd×Nとする。そして、分解誤差を
【数１３】
2014112358.tif 000015
と定義して、これを最小化する。こうすることで、実数ベクトルは、実際のデータの分布に従って分解されることになるため、内積の近似精度が向上する。
【００８１】
この近似分解は、ｍiを逐次的に求めることで行うことができる。第２の分解手法の手順は以下のとおりである。
（１）ｒにｑを代入する（ｒ←ｑ）
（２）ｉに１を代入する（ｉ←１）
（３）第１の分解手法によって
【数１４】
2014112358.tif 000016
を最小化してｍi、ｃiを得る。
【００８２】
（４）ステップ（３）で得られたｍi、ｃiを初期値として、次の手順で
【数１５】
2014112358.tif 000017
を最小化する。
（４−１）ｍiを固定して、
【数１６】
2014112358.tif 000018
が最小になるように、ｃiを更新する。これは、最小二乗法により求めることができる。
（４−２）ｃiを固定して、
【数１７】
2014112358.tif 000019
が最小になるように、ｍiを更新する。ｍiが離散値であるため、これは組合最適化問題となり、例えば、グリーディアルゴリズム（Greedy algorithm）、タブ−サーチ（tabu search）、シミュレイテッドアニーリング（simulated annealing）等のアルゴリズムを用いて最小化を行うことができる。ステップ（３）でよい初期値が得られているので、これらのアルゴリズムでも良好に分解誤差を最小化できる。
（４−３）収束するまで（４−１）及び（４−２）を繰り返す。例えば、
【数１８】
2014112358.tif 000020
の減少量が一定値以下になったときに、収束したと判定する。
【００８３】
（５）ｒにｒ−ｍiｃiを代入し（ｒ←ｒ−ｍiｃi）、ｉにｉ＋１を代入し（ｉ←ｉ＋１）、ｉ≦ｋであればステップ（３）に戻り、ｉ＞ｋであればステップ（６）に進む。
（６）ステップ（１）〜（６）により得た解Ｍ、ｃを候補として保持する。
（７）ステップ（１）〜（６）を繰り返し、最も
【数１９】
2014112358.tif 000021
を小さくできた候補Ｍ、ｃを最終結果として採用する。なお、ステップ（７）の繰り返しはなくてもよいが、複数回繰り返すことで、初期値依存の問題を軽減できる。
【００８４】
なお、上記の第１及び第２の分解手法は、かならずしも基底行列Ｍが二値（又は第２の実施の形態の三値）でなくともよく、基底行列Ｍのとり得る要素の種類が有限の数であれば適用可能である。また、係数ベクトルｃも、基底行列Ｍと同様にあらかじめ定められた離散的な値でもよい。たとえば、２のべき乗に制約してもよく、そうすることで、処理を高速化できる。また、分解する実数ベクトルｑの要素の平均値が著しく大きい（若しくは小さい）場合、すなわち、平均値が０から著しく離れている場合には、この平均値をあらかじめ実数ベクトルｑの各要素から引いてオフセット実数ベクトルを生成し、このオフセット実数ベクトルを基底行列Ｍと係数ベクトルｃに分解すると、より少ない基底で式（１）の近似分解を行うことができる。
【００８５】
ベクトル演算部１０６は、特徴ベクトルを用いた演算を行なう。演算の具体的内容については、後述にて、本実施の形態の特徴量演算装置１００の応用例とともに具体的に説明する。この特徴ベクトルを用いた演算には、二値化された特徴ベクトルｐ∈｛−１，１｝dと実数ベクトル分解部１０５にて二値ベクトルの線形和に分解された実数ベクトルｑとの内積ｐTｑの計算が含まれる。以下では、まず、この内積ｐTｑの計算について説明する。
【００８６】
内積ｐTｑは、下式（２）のように式変形できる。
【数２０】
2014112358.tif 000022
ここで、ｐTｍiは二値ベクトル同士の内積である。この二値ベクトル同士の内積ｐTｍiは、極めて高速に計算可能である。その理由は以下のとおりである。
【００８７】
二値ベクトル同士の内積は、ハミング距離の演算に帰着できる。ハミング距離とは、２つのバイナリコードにおいて、値が異なるビットを数えたものであり、２つの二値ベクトルの間のハミング距離は、すなわち値が異なる要素数を数えたものである。ここで、ｐとｍiのハミング距離をＤhamming（ｐ，ｍi）と記述すると、内積ｐTｍiは、
Ｄhamming（ｐ，ｍi）と下式（３）の関係がある。
【数２１】
2014112358.tif 000023
ここで、前述のとおり、ｄはバイナリコードのビット数である。
【００８８】
ハミング距離の演算は、２つのバイナリコードにおいて、ＸＯＲを適用した後に、１が立っているビットを数えることで計算できるので、極めて高速である。二値ベクトルがバイナリコード（０と１のビット列）で表現されているのであれば、ハミング距離は、下式（４）で計算できる。
【数２２】
2014112358.tif 000024
ここで、ＸＯＲ関数はｐとｍiをバイナリコード表現で考えたときに排他的論理和を
取る操作であり、ＢＩＴＣＯＵＮＴ関数はバイナリコードの１が立っているビット数を数えあげる処理のことである。
【００８９】
以上をまとめると、内積ｐTｑは下式（５）のように変形できる。
【数２３】
2014112358.tif 000025
すなわち、ｄビットのハミング距離計算をｋ回行い、ｋ個のハミング距離について、係数ベクトルｃに関する重み付け和を計算し、定数項を足したものがｐTｑになる。よって、ｋが十分小さければ、ｐTｑを浮動小数点精度で計算するよりも、はるかに高速に計算できるようになる。
【００９０】
なお、上記の内積計算において、二値化された特徴ベクトルｐは、「第１の二値ベクトル」に相当し、基底ベクトルｍiは、「第２の二値ベクトル」に相当する。
【００９１】
データベース１０７には、実数ベクトル分解部１０５にて分解された複数の実数ベクトル、即ち複数の基底ベクトルの線形和が辞書データとして記憶されている。ベクトル演算部１０６は、データベース１０７から基底ベクトルの線形和を読み出して、上記の演算を行う。このデータベース１０７は、「基底ベクトル取得部」に相当する。
【００９２】
以上のように、本実施の形態の特徴量演算装置１００によれば、特徴ベクトルを用いた演算処理に特徴ベクトルと他の実数ベクトルとの内積演算が含まれている場合にも、特徴ベクトルを二値化したうえで、実数ベクトルについても二値ベクトルの線形和に分解するので、それらの内積演算を高速化できる。
【００９３】
（第１の実施の形態の拡張）
上記の第１の実施の形態では、二値ベクトルｐ、ｍiを、それぞれ、ｐ∈｛−１，１｝d、ｍi∈｛−１，１｝dと定義して、実数ベクトルを二値ベクトルの線形和に分解することで内積演算ｐTｍiが高速になることを説明した。しかしながら、ｐ、ｍiをより一般的な二値ベクトルｐ´∈｛−ａ，ａ｝d、ｍi´∈｛−ａ，ａ｝dとしても、それらの高速な内積演算が可能である。この場合、ｐ´Tｍi´＝ａ2（ｐTｍi）であることから、−１及び１により定義される二値ベクトル同士の内積にａ2を掛ければよい。なお、この場合には、特徴ベクトルｐ´を係数ａで除して得られる二値ベクトルｐが「第１の二値ベクトル」に相当し、基底ベクトルｍi´を係数ａで除して得られる二値ベクトルｍiが「第２の二値ベクトル」に相当する。
【００９４】
さらに、特徴ベクトル及び基底ベクトルを任意の二値ベクトルｐ´´∈｛α，β｝d、ｍi´´∈｛γ，δ｝dとしても、高速な内積演算が可能である。ここで、係数α、β、γ、δは実数であり、α≠β、γ≠δである。この場合、ｐ´´およびｍi´´は、−１及び１により定義される二値ベクトルｐ及びｍiの各要素に線形変換を施すことで得られ、下式（６）及び（７）のように展開される。
【数２４】
2014112358.tif 000026
【数２５】
2014112358.tif 000027
なお、式（６）及び（７）中の太字の「１」は、長さがｄですべての要素が１であるベクトルである。また、式（６）及び（７）中のＡ、Ｂ、Ｃ、Ｄは実数であり、式（６）及び（７）が成立するようにあらかじめ計算しておけばよい。
【００９５】
内積ｐ´´Tｍi´´は、下式（８）のように展開できる。
【数２６】
2014112358.tif 000028
式（８）の括弧内の計算は、−１及び１からなる二値ベクトル同士の内積である。従って、特徴ベクトルが任意の二値の要素をもつ二値ベクトルにされ、かつ、実数ベクトルを任意の二値の要素を持つ二値ベクトルの線形和に展開した場合にも、高速演算が可能である。なお、この場合には、各要素を線形変換することで特徴ベクトルｐ´´が得られる上記の二値ベクトルｐが「第１の二値ベクトル」に相当し、各要素を線形変換することで基底ベクトルｍi´´が得られる上記の二値ベクトルｍiが「第２の二値ベクトル」に相当する。
【００９６】
（第２の実施の形態）
次に、第２の実施の形態の特徴量演算装置を説明する。第２の実施の形態の特徴量演算装置の構成は、図１に示した第１の実施の形態のそれと同じである。第１の実施の形態では、実数ベクトル分解部１０５は、実数ベクトルを式（１）によって二値ベクトルの線形和に分解したが、本実施の形態の特徴量演算装置１００の実数ベクトル分解部１０５は、実数ベクトルを三値ベクトルの線形和に分解する。
【００９７】
実数ベクトル分解部１０５は、ｄ次元の実数ベクトルｑ∈Ｒdを、三値ベクトルの線形和に分解する。具体的には、実数ベクトル分解部１０５は、ｄ次元の実数ベクトルｑ∈Ｒdを、下式（９）によって、三値の要素を持つ基底行列Ｍと実数の要素を持つ係数ベクトルｃに分解する。
【数２７】
2014112358.tif 000029
ここで、Ｍ＝（ｍ1，ｍ2，…，ｍk）∈｛−１，０，１｝d×kであり、ｃ＝（ｃ1，ｃ2，…，ｃk）T∈Ｒkである。すなわち、基底行列Ｍは、ｋ個の基底ベクトルｍiからなり、ここで、基底ベクトルｍiは、要素が−１、０、及び１のみをとるｄ次元の三値ベクトルであり、従って、基底行列Ｍは、要素が−１、０、及び１のみをとるｄ行ｋ列の三値行列である。また、係数ベクトルｃは、ｋ個の基底ベクトルに係る実数の係数を要素として持つｋ次元の実数ベクトルである。もちろん、ｑとＭｃはなるべく一致するように分解することが好ましいが、誤差を含んでもよい。実数ベクトル分解部１０５は、第１の実施の形態と同様にして、誤差最小化によって実数ベクトルを分解する。
【００９８】
ベクトル演算部１０６は、内積ｐTｑを計算する。以下では、内積ｐTｑを計算するベクトル演算部１０６を特に、内積演算部１０６とも呼ぶ。内積ｐTｑは、下式（１０）のように式変形できる。
【数２８】
2014112358.tif 000030
ここで、ｐTｍiは、二値ベクトルｐと三値ベクトルｍiとの内積である。内積演算部１０６は、ここで、三値ベクトルｍiの代わりに、以下に定義する０置換ベクトルｍibin、フィルタベクトルｍifilter、及び０要素数ｚiを用いる。
【００９９】
まず、内積演算部１０６は、ｍiの０の要素を、−１又１に置き換える。ｍiの各要素について、それを−１に置き換えるか、１に置き換えるかは、いずれでもよい。この置き換えによって、０置換ベクトルｍibin∈｛−１，１｝dが生成される。この０置換ベクトルｍibin∈｛−１，１｝dは二値ベクトルである。
【０１００】
また、内積演算部１０６は、ｍiの０の要素を−１に置き換え、０以外の要素を１に置き換える。この置き換えによって、フィルタベクトルｍifilter∈｛−１，１｝dが生成される。このフィルタベクトルｍifilterも二値ベクトルである。
【０１０１】
さらに、内積演算部１０６は、ｍiの０の要素数ｚiを求める。ｚiは整数となる。内積演算部１０６は、これらの二値ベクトルｍibin、フィルタベクトルｍifilter、及び０要素数ｚiを用いて、式（１０）におけるｐTｍiを、下の式（１１）及び式（１２）によって計算する。
【数２９】
2014112358.tif 000031
【数３０】
2014112358.tif 000032
ここで、式（１１）のＡＮＤ関数は、二値ベクトルをバイナリコード表現で考えたときに、論理積を取る操作である。
【０１０２】
以下、図３を参照して、具体例を用いて、式（１１）及び（１２）の導出を説明する。図３は、本実施の形態の計算例を示す図である。図３の例では、ｐ＝｛−１，１，−１，１，−１，１｝であり、ｍi＝｛−１，０，１，０，１，１｝である。この例では、ｍibin＝｛−１，＊，１，＊，１，１｝となる。ここで、「＊」は−１又は１の任意のいずれかを示す。また、ｍifilter＝｛１，−１，１，−１，１，１｝となり、ｚi＝２となる。
【０１０３】
式（１１）におけるｐとｍibinとの排他的論理和は、ＸＯＲ（ｐ，ｍibin）＝｛−１，＊，１，＊，１，−１｝となり、すなわち、ｐとｍiの要素のうち、非０で異なっている要素すなわち−１と１又は１と−１の組となる要素が１となり、−１と−１又は１と１の組となる要素が−１となる。
【０１０４】
次に、その排他的論理和とｍifilterとの論理積は、ＡＮＤ（ＸＯＲ（ｐ，ｍibin），ｍifilter））＝｛−１，−１，１，−１，１，−１｝となり、ｐとｍiの要素のうち、非０で異なっている要素に１が立ち、それ以外は−１となる。このビットカウントを取ると、１である要素の個数、すなわち非０で異なっている要素の個数が数え上げられ、Ｄfilterd_hamming（ｐ，ｍibin，ｍifilter）＝２となる。
【０１０５】
ここで、ｐとｍiの要素のうち、１と１又は−１と−１の組となる要素の個数は、全要素数ｄ＝６から、非０で異なっている要素の個数Ｄfilterd_hamming＝２と０である要素の個数ｚi＝２を引くことで求められる。すなわち、１と１又は−１と−１の組となる要素の数＝ｄ−Ｄfilterd_hamming−ｚi＝６−２−２＝２となる。
【０１０６】
ｐとｍiは、１と１又は−１と−１の組となる要素（積が１になる要素の組）の個数から、−１と１又は１と−１との組となる要素（積が−１になる要素の組）の個数を引いた値と等しいため、ｐTｍi＝（ｄ−Ｄfilterd_hamming−ｚi）−Ｄfilterd_hamming＝ｄ−ｚi−２Ｄfilterd_hammingとなり、式（１２）が得られ、その値は、６−２−２×２＝０となる。なお、この結果は、当然ながら、ｐTｍi＝｛−１，１，−１，１，−１，１｝×｛−１，０，１，０，１，１｝＝１＋０＋（−１）＋０＋（−１）＋１＝０と一致する。
【０１０７】
式（１０）〜（１２）をまとめると、内積ｐTｑは、下式（１３）のように変形できる。
【数３１】
2014112358.tif 000033
内積演算部１０６は、この式（１３）によって、内積ｐTｑを計算する。
【０１０８】
関数Ｄfilterd_hamming（ｐ，ｍibin，ｍifilter）は、ハミング距離演算と非常に似ており、ＡＮＤ演算が加わっただけである。したがって、ｑ∈Ｒdを、三値ベクトルの線形和に分解した場合でも、ｐTｑを浮動小数点精度で計算するよりも、はるかに高速にｐTｑを計算できるようになる。
【０１０９】
以上のように、ｄ次元の実数ベクトルｑ∈Ｒdを、二値ではなく三値ベクトルの線形和に分解することの利点は、式（９）の近似が、より少ない数のベクトルの線形和でも成立するようになることにある。すなわち、ｋの値を小さく抑えられることになるため、さらなる高速化につながる。
【０１１０】
（第２の実施の形態の拡張）
上記の第２の実施の形態では、二値ベクトルｐ及び三値ベクトルｍiを、それぞれ、ｐ∈｛−１，１｝d、ｍi∈｛−１，０，１｝dと定義して、実数ベクトルを三値ベクトルの線形和に分解することで内積演算ｐTｍiが高速になることを説明した。しかしながら、ｐ、ｍiをより一般的な二値ベクトルｐ´∈｛−ａ，ａ｝d、三値ベクトルｍi∈｛−ａ，０，ａ｝dとしても、それらの高速な内積演算が可能である。この場合、ｐ´Tｍi´＝ａ2（ｐTｍi）であることから、−１及び１により定義される二値ベクトル同士の内積にａ2を掛ければよい。
【０１１１】
さらに、二値ベクトルｐ及び三値ベクトルｍiをｐ∈｛α，β｝d、ｍi∈｛γ−δ，γ，γ＋δ｝dと一般化しても、高速な内積演算が可能である。ここで、α、β、γ、δは実数であり、α≠β、δ≠０である。この場合、ｐ及びｍiの各要素に下式（１４）及び（１５）の線形変換を施すことで、それぞれｐ´´およびｍi´´が得られる。
【数３２】
2014112358.tif 000034
【数３３】
2014112358.tif 000035
なお、式（１４）及び（１５）中の太字の「１」は、長さがｄですべての要素が１であるベクトルである。また、式（１４）及び（１５）中のＡ、Ｂ、Ｃ、Ｄは実数であり、式（１４）及び（１５）が成立するようにあらかじめ計算しておく。
【０１１２】
内積ｐ´´Tｍi´´は、下式（１６）のように展開できる。
【数３４】
2014112358.tif 000036
式（１６）の括弧内の計算は、−１及び１からなる二値ベクトル同士の内積、又は−１及び１からなる二値ベクトルと−１、０、１からなる三値ベクトルとの内積である。従って、特徴ベクトルが任意の二値ベクトルにされ、かつ、実数ベクトルを上記のとおり一般化した三値ベクトルの線形和に展開した場合にも、高速演算が可能である。
【０１１３】
（第３の実施の形態）
第１及び第２の実施の形態では、ベクトル演算部１０６における演算処理において行なわれる特徴ベクトルｐと実数ベクトルｑとの内積演算について説明した。特徴ベクトルｐと実数ベクトルｑとの内積演算を伴う演算処理については、後述にて応用例として説明するが、演算処理として、内積ｐTｑがある閾値Ｔと比較されることがある。例えば、特徴ベクトルの識別を行なう場合には、内積ｐTｑがある閾値Ｔと比較される。
【０１１４】
第１の実施の形態及び第２の実施の形態において、内積ｐTｑは、式（２）（実数ベクトルｑを二値ベクトルの線形和に分解する場合）及び式（１０）（実数ベクトルｑを三値ベクトルの線形和に分解する場合）に示すように、下式（１７）で表される。
【数３５】
2014112358.tif 000037
この点に着目して、ベクトル演算部１０６は、特徴ベクトルを用いた演算に、内積ｐTｑと閾値との比較の処理（閾値処理）が含まれる場合には、閾値処理をｋ段階に分けること（カスケード）により、閾値処理を高速化できる。
【０１１５】
（第１のカスケード）
以下、第１のカスケードによる閾値処理の高速化をする。以下の例では、閾値をＴとして、ｐTｑ＞Ｔを判定する。図４は、ベクトル演算部１０６おけるカスケードによる閾値処理の高速化のフロー図である。ベクトル演算部１０６は、まずｉ＝１、ｙ＝０とする（ステップＳ１１）。次に、ｙをｙ＋ｃi（ｐTｍi）に更新する（ステップＳ１２）。次に、ｙがＴiminより大きいか否かを判断する（ステップＳ１３）。なお、Ｔiminは、ｐTｑ＜Ｔを早期に判定するための最小側早期判定閾値であり、その決定方法については、後述する。ｙがＴiminより小さい場合には（ステップＳ１３にてＹＥＳ）、ｐTｑ＜Ｔであると判定して（ステップＳ１４）、そこで特徴ベクトルｐと実数ベクトルｑとの内積演算を打ち切って、処理を終了する。
【０１１６】
ｙがＴimin以上である場合は（ステップＳ１３にてＮＯ）、次にｙがＴimaxより大きいか否かを判断する（ステップＳ１５）。なお、Ｔimaxは、ｐTｑ＞Ｔを早期に判定するための最大側早期判定閾値であり、その決定方法については、後述する。ｙがＴimaxより大きい場合には（ステップＳ１５にてＹＥＳ）、ｐTｑ＞Ｔであると判定して（ステップＳ１６）、そこで特徴ベクトルｐと実数ベクトルｑとの内積演算を打ち切って、処理を終了する。
【０１１７】
ｙがＴimax以下である場合には（ステップＳ１５にてＮＯ）、ｉ＝ｋであるか否か、すなわち、まだ計算していない基底ｍiがあるか否かを判断する（ステップＳ１７）、ｉ＝ｋでない場合には（ステップＳ１７にてＮＯ）、ｉをインクリメントして（ステップＳ１８）、ステップＳ１２に戻る。ｉ＝ｋである場合、すなわちすべての基底ｍiを計算している場合には（ステップＳ１７にてＹＥＳ）、ステップＳ１４に移行して、ｐTｑ＜Ｔであると判断して処理を終了する。
【０１１８】
以上のように、二値ベクトルｐと実数ベクトルｑとの内積を計算する際に、実数ベクトルｑを二値ベクトル又は三値ベクトルの線形和に分解することで、閾値処理をｋ段階に分けることができ、それによって、ｐTｑ＜Ｔが明らかに成立する場合、及びｐTｑ＞Ｔが明らかに成立する場合は、そのような閾値処理の結果を早期に得ることができる。これによって、二値ベクトルｐと実数ベクトルｑの内積演算をｋ回より少ない回数に抑えることができる。
【０１１９】
なお、判定結果は、カスケードを採用しない（非カスケード）場合と完全に一致はしないが、Ｔimin及びＴimaxを適切に選択することで、判定結果を非カスケードの場合と限りなく一致させることができる。
【０１２０】
なお、ｃiを大きさによって並べ替えることで、早期判定の効果を高めることができる。また、ｃiの大きさに差がつくように分解することで、早期判定の効果を高めることができる。
【０１２１】
次に、最小側早期判定用閾値Ｔimin及び最大側早期判定用閾値Ｔimaxの決定方法について説明する。カスケード一段目における最小側早期判定用閾値Ｔ1min及び最大側早期判定用閾値Ｔ1maxを決定することを考えると、ｃi（ｐTｍi）（ｉ＝２，３，…，ｋ）が未知の状態で、安全に判定できる閾値を決めなければならない。そこで、あらかじめｃi（ｐTｍi）のとり得る最大値Ｐimax及び最小値Ｐiminを求めておく。これは、事前に学習用に準備した複数のデータから抽出した二値の特徴量ｐをｃi（ｐTｍi）に代入することで得られる。
【０１２２】
最小側早期判定用閾値Ｔiminは、次のようにして決定できる。
【数３６】
2014112358.tif 000038
すなわち、
【数３７】
2014112358.tif 000039
が成立するのであれば、カスケードの二段目以降は、どのような大きな値が入ってきたとしてもｐTｑ＜Ｔが成立するので、この時点で必ずｐTｑ＜Ｔが成立するといえる。従って、下式（１８）によってＴiminを求めることができる。
【数３８】
2014112358.tif 000040
二段目以降のＴiminについても、同じ要領で決定することができる。
【０１２３】
最大側早期判定用閾値Ｔimaxは、次のようにして決定できる。
【数３９】
2014112358.tif 000041
すなわち、
【数４０】
2014112358.tif 000042
が成立するのであれば、カスケードの二段目以降は、どのような小さな値が入ってきたとしてもｐTｑ＞Ｔが成立するので、この時点で必ずｐTｑ＞Ｔが成立するといえる。従って、下式（１９）によってＴimaxを求めることができる。
【数４１】
2014112358.tif 000043
二段目以降のＴimaxについても、同じ要領で決定することができる。なお、上記説明から明らかなように、Ｔkmin及びＴkmaxはＴである。
【０１２４】
なお、式（１９）において、Ｐiminは最小でなくても、十分小さい上位数％内の値として選択してもよい。また、式（１８）においても、Ｐimaxは最大でなくても、十分に大きい上位数％の値として選択してもよい。
【０１２５】
（第２のカスケード）
第２のカスケードでは、実数ベクトルを複数のサブベクトルに分解することでより深いカスケードを実施し、これにより、閾値との比較処理をより高速化する。即ち、第１のカスケードでは、
【数４２】
2014112358.tif 000044
であることに着目して、閾値処理をｋ段階に分けた。第２のカスケードでは、これを以下のように拡張する。
【０１２６】
まず、下式（２０）のように、ｑ∈Ｒdをｍ個の部分ベクトルに分解する。
【数４３】
2014112358.tif 000045
同様に、下式（２１）のように、ｐ∈｛１，１｝dをｍ個の部分ベクトルに分解する。
【数４４】
2014112358.tif 000046
ここで、ｑiとｐiの次元数は同じであるものとする。
【０１２７】
このとき、内積ｐTｑは、下式（２２）のように書ける。
【数４５】
2014112358.tif 000047
ｍ個のそれぞれの内積ｐiTｑiは、二値ベクトルと実数ベクトルの内積であるため、これらもまた、それぞれ二値／三値分解法を適用可能である。例えば、内積ｐiTｑiをそれぞれｋ個に分解するのであれば、ｐTｑは、ｍｋ段階のカスケード処理に分解できる。これによりカスケードの段階数が増加し、早期判定の効果を向上できる。なお、第２のカスケードにおいても、カスケード処理の順序は、係数の絶対値順、又は誤識別が少なくなるような順序に選ぶことで、早期判定の効果をより向上できる。
【０１２８】
なお、上記の第３の実施の形態では、ｐTｑ＞Ｔを判断するために、基底ごとに、明らかにｐTｑ＜Ｔが成立する（すなわち明らかにｐTｑ＞Ｔが成立しない）か否か、及び明らかにｐTｑ＞Ｔが成立するか否かを判断したが、このいずれか一方のみを判断してもよい。
【０１２９】
次に、ベクトル演算部１０６における演算処理について説明する。上記の第１及び第２の実施の形態のベクトル演算部１０６は、二値化された特徴ベクトルｐと実数ベクトルｑの内積計算を伴うものであるが、そのような演算処理は種々ある。すなわち、本発明の上記の実施の形態は、特徴ベクトルを用いて演算処理を行なう種々の装置に応用できる。なお、上記の第３の実施の形態は、上述のとおり、特に特徴ベクトルを閾値と比較する処理を伴う演算処理を行なう種々の装置に応用できる。そこで、以下、本発明の応用例を第４ないし第６の実施の形態として説明する。
【０１３０】
（第４の実施の形態）
本実施の形態では、本発明がＨｏＧによる物体認識に応用される。図５は、物体認識装置の構成を示すブロック図である。物体認識装置１０は、ＨｏＧによる物体認識を行なう。物体認識装置１０は、ピラミッド画像生成部１１と、ＨｏＧ特徴量抽出部１２と、バイナリコード変換部１３と、パラメータ決定部１４と、パラメータ行列分解部１５と、線形ＳＶＭ識別部１６と、ピーク検出部１７とを備えている。
【０１３１】
ピラミッド画像生成部１１は、入力クエリとしての画像を取得して、当該画像を複数段階の倍率でそれぞれ縮小してなるピラミッド画像を生成する。これにより、サイズの異なる物体に対処できる。このピラミッド画像生成部１１は、図１に示したコンテンツ取得部１０１に対応する。ＨｏＧ特徴量抽出部１２は、ピラミッド画像の各段における画像を、８×８ピクセルのサイズのセルに分割し、各セルからＨｏＧ特徴量を抽出する。ＨｏＧ特徴量抽出部１２は、各セルからＤ次元の特徴量を抽出する。このＨｏＧ特徴量抽出部１２は、図１に示した特徴ベクトル抽出部１０２に対応する。バイナリコード変換部１３は、各セルに与えられたＤ次元の特徴量を、ｄ次元の二値ベクトルに変換する。このバイナリコード変換部１３は、図１に示した特徴ベクトル二値化部１０３に対応する。
【０１３２】
パラメータ決定部１４は、線形ＳＶＭ識別部１６における線形ＳＶＭにて用いる重みベクトルｗ及び実数のバイアスｂを決定する。パラメータ決定部１４は、学習用に用意された特徴量を用いて、学習処理によって重みベクトルｗ及びバイアスｂを決定する。パラメータ行列分解部１５は、重みベクトルｗを第１又は第２の実施の形態で説明した式（１）又は式（９）によって離散値ベクトルの線形和に分解する。
【０１３３】
線形ＳＶＭ識別部１６は、線形ＳＶＭによって特徴ベクトルの識別を行なう。線形ＳＶＭ識別部１６は、まず、Ｗ×Ｈセルをひとまとまりとして、検出ウィンドウを構成する。１つの検出ウィンドウから抽出される特徴ベクトルは、Ｗ×Ｈ×ｄ次元のベクトルとなる。線形ＳＶＭ識別部１６は、この特徴ベクトルに対して、下式（２０）の線形ＳＶＭを適用する。
【数４６】
2014112358.tif 000048
ここで、線形ＳＶＭにおける内積演算ｗTｘは、第１又は第２の実施の形態として説明した実数ベクトルと二値ベクトルの高速内積演算により実現できる。
【０１３４】
検出位置付近では、検出結果が固まることがある。そこで、ピーク検出部１７は、周辺でｆ（ｘ）の値が最大になったところを、代表的な検出位置とする。この線形ＳＶＭ識別部１６及びピーク検出部１７は、特徴ベクトルを用いた処理を行なう構成であり、図１のベクトル演算部１０６に対応する。この線形ＳＶＭ識別部１６及びピーク検出部１７の演算に、第３の実施の形態として説明したカスケードによる閾値処理の高速化技術を採用することが可能である。
【０１３５】
（第５の実施の形態）
本実施の形態では、本発明がｋ−ｍｅａｎｓクラスタリングに応用される。図６は、ｋ−ｍｅａｎｓクラスタリング装置の構成を示すブロック図である。ｋ−ｍｅａｎｓクラスタリング装置２０は、コンテンツ取得部２１と、特徴ベクトル生成部２２と、特徴ベクトル二値化部２３と、代表ベクトル更新部２４と、収束判定部２５と、代表ベクトル分解部２６と、最近接代表ベクトル探索部２７とを備えている。
【０１３６】
コンテンツ取得部２１は、クラスタリングの対象となるＮ個のコンテンツを取得する。特徴ベクトル生成部２２は、コンテンツ取得部２１にて取得した各コンテンツからそれらの特徴量を特徴ベクトルとして抽出する。特徴ベクトル二値化部２３は、特徴ベクトル抽出部２２にて抽出された各特徴ベクトルを二値化する。
【０１３７】
代表ベクトル更新部２４は、まず、特徴ベクトル二値化部２３で二値化されたＮ個の特徴ベクトルからｋ個をランダムに選出してこれを代表ベクトルとする。収束判定部２５は、代表ベクトル更新部２４が代表ベクトルを更新するごとに収束判定を行なう。収束判定部２５にて収束したと判定された場合には、ｋ−ｍｅａｎｓクラスタリング装置２０はクラスタリングの処理を終了する。代表ベクトル分解部２６は、代表ベクトル更新部２４にて更新された代表ベクトルを離散値（二値又は三値）ベクトルに分解する。
【０１３８】
最近接代表ベクトル探索部２７は、特徴ベクトル二値化部２３より入力されるＮ個の二値ベクトルをそれぞれ最も近傍の代表ベクトルに所属させる。最近接代表ベクトル２７は、この結果を代表ベクトル更新部２４に出力する。代表ベクトル更新部２４は、各代表ベクトルについて、それに所属する特徴ベクトル（二値化されている）の平均ベクトルを算出して、これを新しい代表ベクトルとする。このようにして代表ベクトル更新部２４で更新される代表ベクトルは、二値ベクトルの平均で算出されるので、実数ベクトルとなる。
【０１３９】
従って、仮に代表ベクトル分解部２６がなければ、最近接代表ベクトル探索部２７は、更新された代表ベクトル（実数ベクトル）と特徴ベクトル（二値ベクトル）との距離を求めるためにそれらの内積を計算しなければならない。そこで、本実施の形態では、上記のように、この代表ベクトル（実数ベクトル）を代表ベクトル分解部２６によって、第１又は第２の実施の形態で説明したように、離散値（二値又は三値）ベクトルに分解する。それによって、最近接代表ベクトル探索部２７における、各特徴ベクトルと各代表ベクトルとの距離の計算を高速にでき、よって各特徴ベクトルが最も近接する代表ベクトル（すなわち、所属すべき代表ベクトル）を高速に探索できる。
【０１４０】
（第６の実施の形態）
本実施の形態では、本発明がｋ−ｍｅａｎｓ  ｔｒｅｅによる近似最近傍探索に応用される。本実施の形態の近似最近傍探索装置は、ｋ−ｍｅａｎｓを用いたｋ−分木による近似最近傍探索手法として、Marius Muja and David G. Lowe, "Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration", in International Conference on Computer Vision Theory and Applications (VISAPP' 09), 2009（http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN、http://people .cs.ubc.ca/~mariusm/uploads/FLANN/flann_visapp09.pdf）に提案されている手法を採用する。
【０１４１】
具体的には、本実施の形態の近似最近傍探索装置は、Ｎ個のデータに対してｋ−ｍｅａｎｓを再帰的に適用することでｋ−分木を構築し、上記提案の木探索の原理により近似的に最近傍点を探索する。この手法は、データが実数ベクトルであり、かつノードに登録されている代表ベクトルが二値ベクトルである場合を前提として設計される。但し、データが二値ベクトルであって、ノードに登録されている代表ベクトルが実数ベクトルである場合にも、第１又は第２の実施の形態を採用することで、木探索を高速化できる。
【０１４２】
（変形例）
特徴量演算装置１００において、コンテンツ取得部１０１、特徴ベクトル生成部１０２、特徴ベクトル二値化部１０３、実数ベクトル取得部１０４、実数ベクトル分解部１０５、及びベクトル演算部１０６の一部と他の部分とが別々の装置として構成されていてもよい。特に、コンテンツ取得部１０１、特徴ベクトル生成部１０２、特徴ベクトル二値化部１０３、及びベクトル演算部１０６が特徴演算装置１００に搭載され、実数ベクトル取得部１０４、及び実数ベクトル分解部１０５が別の装置に搭載されてよい。この場合には、実数ベクトル分解部１０５にて分解された複数の実数ベクトル（複数の係数ベクトルと基底ベクトルの組）が特徴演算装置１００のデータベースに記憶され、ベクトル演算部１０６は、データベースから分解された複数の実数ベクトルを取得する。このとき、ベクトル演算部１０６は、基底ベクトル取得部（第１及び第２の実施の形態）、あるいは、二値ベクトル取得部（第１の実施の形態）、三値ベクトル取得部（第２の実施の形態）として機能する。
【０１４３】
なお、コンテンツ取得部１０１にて取得されるコンテンツデータは、車両から得られる計測データであってよい。さらに、車両から得られる計測データは、例えば、車両に設置されたカメラで撮影された画像データ、車両に設置されたセンサで計測されたセンシングデータであってよい。この場合に、関連性判定装置としての特徴演算装置１００のベクトル演算部１０６は、計測データと辞書データとの関連性を判定する。例えば、計測データとして、車両に設置されたカメラで撮影された画像データが取得される場合には、辞書データとして複数の人物画像のデータがデータベースに保存されており、関連性判定装置としての特徴演算装置１００のベクトル演算部１０６は、第４ないし第６の実施の形態のいずれかによって、画像データの画像に人物が含まれるか否かを判定してよい。
【０１４４】
（付記）
上記の第１ないし第６の実施の形態には、以下の技術（これらに限られない）が含まれている。
【０１４５】
（付記１−１）
二値化された特徴ベクトルを取得する特徴ベクトル取得部と、
実数ベクトルを取得する実数ベクトル取得部と、
前記実数ベクトルを複数の二値の基底ベクトルの線形和に分解する実数ベクトル分解部と、
前記特徴ベクトルと分解された前記実数ベクトルとの内積計算を含む演算を行なうベクトル演算部と、
を備えたことを特徴とする特徴量演算装置。
【０１４６】
この構成により、実数ベクトルは二値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１４７】
（付記１−２）
前記特徴ベクトルと分解された前記実数ベクトルとの内積計算は、−１及び１のみを要素としてもつ第１の二値ベクトルと−１及び１のみを要素としてもつ複数の第２の二値ベクトルとの内積計算を含むことを特徴とする付記１−１に記載の特徴量演算装置。
【０１４８】
この構成により、第１の二値ベクトル及び第２の二値ベクトルはいずれも−１及び１のみを要素としてもつので、それらの内積の計算は、ハミング距離の計算によって行なうことができ、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１４９】
（付記１−３）
前記第１の二値ベクトルは、前記特徴ベクトルであることを特徴とする付記１−２に記載の特徴量演算装置。
【０１５０】
この構成により、二値化された特徴ベクトルは、−１及び１のみを要素としてもつので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１５１】
（付記１−４）
前記第１の二値ベクトルは、前記特徴ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする付記１−２に記載の特徴量演算装置。
【０１５２】
この構成により、二値化された特徴ベクトルは、任意の係数ａを用いて、ｐ´∈｛−ａ，ａ｝dと表される二値ベクトルとすることができる。
【０１５３】
（付記１−５）
前記第１の二値ベクトルは、その各要素を線形変換することで前記特徴ベクトルが得られるベクトルであることを特徴とする付記１−２に記載の特徴量演算装置。
【０１５４】
この構成により、二値化された特徴ベクトルは、任意の係数α及びβを用いて、ｐ´´∈｛α，β｝d（但し、α≠β）と表される二値ベクトルとすることができる。
【０１５５】
（付記１−６）
前記第２の二値ベクトルは、前記基底ベクトルであることを特徴とする付記１−２ないし１−５のいずれか一項に記載の特徴量演算装置。
【０１５６】
この構成により、二値の基底ベクトルは、−１及び１のみを要素としてもつので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１５７】
（付記１−７）
前記第２の二値ベクトルは、前記基底ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする付記１−２ないし１−５のいずれか一項に記載の特徴量演算装置。
【０１５８】
この構成により、二値の基底ベクトルは、任意の係数ａを用いて、ｍi´∈｛−ａ，ａ｝dと表される二値ベクトルとすることができる。
【０１５９】
（付記１−８）
前記第２の二値ベクトルは、その各要素を線形変換することで前記基底ベクトルが得られるベクトルであることを特徴とする付記１−２ないし１−５のいずれか一項に記載の特徴量演算装置。
【０１６０】
この構成により、二値の基底ベクトルは、任意の係数γ及びδを用いて、ｍi´´∈｛γ，δ｝d（但し、γ≠δ）と表される二値ベクトルとすることができる。
【０１６１】
（付記１−９）
前記ベクトル演算部は、前記第１の二値ベクトルと前記第２の二値ベクトルとの排他的論理和をとることで、前記第１の二値ベクトルと前記第２の二値ベクトルとの内積を計算することを特徴とする付記１−２ないし１−８のいずれか一項に記載の特徴量演算装置。
【０１６２】
この構成により、第１の二値ベクトルと第２の二値ベクトルとの排他的論理和をとるという負荷の少ない計算で、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１６３】
（付記１−１０）
前記実数ベクトル分解部は、前記複数の基底ベクトルの要素を固定して、分解の誤差が最小になるように、前記複数の基底ベクトルに係る複数の係数を更新する第１の更新と、前記複数の係数を固定して、分解の誤差が最小になるように前記基底ベクトルの要素を更新する第２の更新とを繰り返すことで、前記複数の基底ベクトル及び前記複数の係数を求めることを特徴とする付記１−２ないし１−９のいずれか一項に記載の特徴量演算装置。
【０１６４】
この構成により、好適に実数ベクトルを二値の基底ベクトルの線形和に分解できる。特に、基底ベクトルは、二値のベクトルであるので、その要素の組み合わせの候補は有限であり、高速に第１の更新を行なうことができる。
【０１６５】
（付記１−１１）
前記実数ベクトル分解部は、前記分解誤差の減少量が所定の値以下になるまで前記第１の更新と前記第２の更新を繰り返すことを特徴とする付記１−１０に記載の特徴量演算装置。
【０１６６】
この構成により、分解の誤差を所定の範囲内に抑えることができる。
【０１６７】
（付記１−１２）
前記実数ベクトル分解部は、前記複数の基底ベクトル及び前記複数の係数の初期値を変えて、複数とおりの前記複数の基底ベクトル及び前記複数の係数を求め、前記分解誤差が最小となる前記複数の基底ベクトル及び前記複数の係数を採用することを特徴とする付記１−１０又は１−１１に記載の特徴量演算装置。
【０１６８】
この構成により、初期値によるばらつきを軽減して、分解の誤差をより小さくできる。
【０１６９】
（付記１−１３）
前記実数ベクトル分解部は、前記複数の基底ベクトルに係る複数の係数を離散値とすることを特徴とする付記１−１ないし１−１２のいずれか一項に記載の特徴量演算装置。
【０１７０】
この構成により、実数ベクトルの基底ベクトルの線形和への分解における係数が離散値に限られるので、第２の更新を高速化できる。
【０１７１】
（付記１−１４）
前記実数ベクトル分解部は、前記実数ベクトルの要素の平均値を前記実数ベクトルの各要素から引いてオフセット実数ベクトルを生成し、当該オフセット実数ベクトルを前記基底ベクトルの線形和に分解することを特徴とする付記１−１ないし１−１３のいずれか一項に記載の特徴量演算装置。
【０１７２】
この構成により、実数ベクトルの要素が０付近にシフトするので、基底ベクトルの線形和への分解を高速化できる。
【０１７３】
（付記１−１５）
前記特徴ベクトルは、ＨｏＧ特徴量であり、
前記実数ベクトルは、線形ＳＶＭの重みベクトルであり、
前記ベクトル演算部は、線形ＳＶＭによって前記特徴ベクトルの識別を行なう
ことを特徴とする付記１−１ないし１−１４のいずれか一項に記載の特徴量演算装置。
【０１７４】
この構成により、線形ＳＶＭにおける重みベクトルと特徴ベクトルとの内積計算を高速化できる。
【０１７５】
（付記１−１６）
前記特徴ベクトルは、ｋ−ｍｅａｎｓクラスタリングによるクラスタリングの対象となるベクトルであり、
前記実数ベクトルは、ｋ−ｍｅａｎｓクラスタリングにおける代表ベクトルであり、
前記ベクトル演算部は、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なう
ことを特徴とする付記１−１ないし１−１４のいずれか一項に記載の特徴量演算装置。
【０１７６】
この構成により、ｋ−ｍｅａｎｓクラスタリングにおける特徴ベクトルと代表ベクトルとの間の距離の演算を高速化できる。
【０１７７】
（付記１−１７）
前記特徴ベクトルは、ｋ−ｍｅａｎｓ  ｔｒｅｅによる近似最近傍探索の対象となるベクトルであり、
前記実数ベクトルは、ｋ−分木のノードに登録されている代表ベクトルであり、
前記ベクトル演算部は、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なう
ことを特徴とする付記１−１ないし１−１４のいずれか一項に記載の特徴量演算装置。
【０１７８】
この構成により、ｋ−ｍｅａｎｓ  ｔｒｅｅによる近似最近傍探索における特徴ベクトルとｋ−分木のノードに登録されている代表ベクトルとの間の距離の演算を高速化できる。
【０１７９】
（付記１−１８）
前記特徴ベクトルは、画像の特徴量を表すベクトルであることを特徴とする付記１−１５ないし１−１７のいずれか一項に記載の特徴量演算装置。
【０１８０】
この構成により、画像の特徴量の演算における特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１８１】
（付記１−１９）
コンピュータを、付記１−１ないし１−１８のいずれか一項に記載の特徴量演算装置として機能させるための特徴量演算プログラム。
【０１８２】
この構成によっても、実数ベクトルは二値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１８３】
（付記１−２０）
二値化された特徴ベクトルを取得する特徴ベクトル取得ステップと、
実数ベクトルを取得する実数ベクトル取得ステップと、
前記実数ベクトルを複数の二値の基底ベクトルの線形和に分解する実数ベクトル分解ステップと、
前記特徴ベクトルと分解された前記実数ベクトルとの内積計算を含む演算を行なう特徴ベクトル演算ステップと、
を含むことを特徴とする特徴量演算方法。
【０１８４】
この構成によっても、実数ベクトルは二値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１８５】
（付記２−１）
二値化された特徴ベクトルを取得する特徴ベクトル取得部と、
実数ベクトルを取得する実数ベクトル取得部と、
前記実数ベクトルを複数の三値の基底ベクトルの線形和に分解する実数ベクトル分解部と、
前記特徴ベクトルと分解された前記実数ベクトルとの内積計算を含む演算を行なうベクトル演算部と、
を備えたことを特徴とする特徴量演算装置。
【０１８６】
この構成により、実数ベクトルは三値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１８７】
（付記２−２）
前記特徴ベクトルと分解された前記実数ベクトルとの内積計算は、−１及び１のみを要素としてもつ二値ベクトルと−１、０及び１のみを要素としてもつ複数の三値ベクトルとの内積計算を含むことを特徴とする付記２−１に記載の特徴量演算装置。
【０１８８】
この構成により、二値ベクトルは−１及び１のみを要素としてもち、三値ベクトルは−１、０及び１のみを要素としてもつので、それらの内積の計算は、ハミング距離の計算を利用して行なうことができ、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１８９】
（付記２−３）
前記二値ベクトルは、前記特徴ベクトルであることを特徴とする付記２−２に記載の特徴量演算装置。
【０１９０】
この構成により、二値化された特徴ベクトルは、−１及び１のみを要素としてもつので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１９１】
（付記２−４）
前記二値ベクトルは、前記特徴ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする付記２−２に記載の特徴量演算装置。
【０１９２】
この構成により、二値化された特徴ベクトルは、任意の係数ａを用いて、ｐ´∈｛−ａ，ａ｝dと表される二値ベクトルとすることができる。
【０１９３】
（付記２−５）
前記二値ベクトルは、その各要素を線形変換することで前記特徴ベクトルが得られるベクトルであることを特徴とする付記２−２に記載の特徴量演算装置。
【０１９４】
この構成により、二値化された特徴ベクトルは、任意の係数α及びβを用いて、ｐ´´∈｛α，β｝d（但し、α≠β）と表される二値ベクトルとすることができる。
【０１９５】
（付記２−６）
前記複数の三値ベクトルは、前記複数の基底ベクトルであることを特徴とする付記２−２ないし２−５のいずれか一項に記載の特徴量演算装置。
【０１９６】
この構成により、三値の基底ベクトルは、−１、０、及び１のみを要素としてもつので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０１９７】
（付記２−７）
前記複数の三値ベクトルは、前記複数の基底ベクトルの各要素を所定の係数で除したベクトルであることを特徴とする付記２−２ないし２−５のいずれか一項に記載の特徴量演算装置。
【０１９８】
この構成により、三値の基底ベクトルは、任意の係数ａを用いて、ｍi´∈｛−ａ，０，ａ｝dと表される三値ベクトルとすることができる。
【０１９９】
（付記２−８）
前記複数の三値ベクトルは、その各要素を線形変換することで前記複数の基底ベクトルが得られるベクトルであることを特徴とする付記２−２ないし２−５のいずれか一項に記載の特徴量演算装置。
【０２００】
この構成により、三値の基底ベクトルは、任意の係数γ及びδを用いて、ｍi´´∈｛γ−δ，γ，γ＋δ｝d（但し、γ≠δ）と表される三値ベクトルとすることができる。
【０２０１】
（付記２−９）
前記ベクトル演算部は、前記二値ベクトルと前記三値ベクトルとの内積計算において、前記三値ベクトルの０の要素を−１又は１の任意のいずれかに置換して０置換ベクトルを生成し、前記三値ベクトルの０の要素を−１に置換し、かつ０以外の要素を１に置換してフィルタベクトルを生成し、前記二値ベクトルと前記０置換ベクトルとの排他的論理和と前記フィルタベクトルとの論理積をとることで、前記二値ベクトルと前記三値ベクトルとの間の非０で異なる要素の要素数Ｄｆｉｌｔｅｒｄ＿ｈａｍｍｉｎｇを求め、前記要素数Ｄｆｉｌｔｅｒｄ＿ｈａｍｍｉｎｇ及び非０の要素数を前記二値ベクトルの要素数から引くことで、前記二値ベクトルと前記三値ベクトルとの間の非０で同一の要素の要素数を求め、前記二値ベクトルと前記三値ベクトルとの間の非０で同一の要素の要素数から前記二値ベクトルと前記三値ベクトルとの間の非０で異なる要素の要素数を引くことで、前記二値ベクトルと前記三値ベクトルとの内積を求めることを特徴とする付記２−２ないし２−８のいずれか一項に記載の特徴量演算装置。
【０２０２】
この構成により、０置換ベクトル及びフィルタベクトルを利用して、二値ベクトルと三値ベクトルとの内積演算をハミング距離の計算によって行なうことができ、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０２０３】
（付記２−１０）
前記実数ベクトル分解部は、前記複数の基底ベクトルの要素を固定して、分解の誤差が最小になるように、前記複数の基底ベクトルに係る複数の係数を更新する第１の更新と、前記複数の係数を固定して、分解の誤差が最小になるように前記基底ベクトルの要素を更新する第２の更新とを繰り返すことで、前記複数の基底ベクトル及び前記複数の係数を求めることを特徴とする付記２−１ないし２−９のいずれか一項に記載の特徴量演算装置。
【０２０４】
この構成により、好適に実数ベクトルを三値の基底ベクトルの線形和に分解できる。特に、基底ベクトルは、三値のベクトルであるので、その要素の組み合わせの候補は有限であり、高速に第１の更新を行なうことができる。
【０２０５】
（付記２−１１）
前記実数ベクトル分解部は、前記分解誤差の減少量が所定の値以下になるまで前記第１の更新と前記第２の更新を繰り返すことを特徴とする付記２−１０に記載の特徴量演算装置。
【０２０６】
この構成により、分解の誤差を所定の範囲内に抑えることができる。
【０２０７】
（付記２−１２）
前記実数ベクトル分解部は、前記複数の基底ベクトル及び前記複数の係数の初期値を変えて、複数とおりの前記複数の基底ベクトル及び前記複数の係数を求め、前記分解誤差が最小となる前記複数の基底ベクトル及び前記複数の係数を採用することを特徴とする付記２−１０又は２−１１に記載の特徴量演算装置。
【０２０８】
この構成により、初期値によるばらつきを軽減して、分解の誤差をより小さくできる。
【０２０９】
（付記２−１３）
前記実数ベクトル分解部は、前記複数の基底ベクトルに係る複数の係数を離散値とすることを特徴とする付記２−１ないし２−１２のいずれか一項に記載の特徴量演算装置。
【０２１０】
この構成により、実数ベクトルの基底ベクトルの線形和への分解における係数が離散値に限られるので、第２の更新を高速化できる。
【０２１１】
（付記２−１４）
前記実数ベクトル分解部は、前記実数ベクトルの要素の平均値を前記実数ベクトルの各要素から引いてオフセット実数ベクトルを生成し、当該オフセット実数ベクトルを前記基底ベクトルの線形和に分解することを特徴とする付記２−１ないし２−１３のいずれか一項に記載の特徴量演算装置。
【０２１２】
この構成により、実数ベクトルの要素が０付近にシフトするので、基底ベクトルの線形和への分解を高速化できる。
【０２１３】
（付記２−１５）
前記特徴ベクトルは、ＨｏＧ特徴量であり、
前記実数ベクトルは、線形ＳＶＭの重みベクトルであり、
前記ベクトル演算部は、線形ＳＶＭによって前記特徴ベクトルの識別を行なう
ことを特徴とする付記２−１ないし２−１４のいずれか一項に記載の特徴量演算装置。
【０２１４】
この構成により、線形ＳＶＭにおける重みベクトルと特徴ベクトルとの内積計算を高速化できる。
【０２１５】
（付記２−１６）
前記特徴ベクトルは、ｋ−ｍｅａｎｓクラスタリングによるクラスタリングの対象となるベクトルであり、
前記実数ベクトルは、ｋ−ｍｅａｎｓクラスタリングにおける代表ベクトルであり、
前記ベクトル演算部は、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なう
ことを特徴とする付記２−１ないし２−１４のいずれか一項に記載の特徴量演算装置。
【０２１６】
この構成により、ｋ−ｍｅａｎｓクラスタリングにおける特徴ベクトルと代表ベクトルとの間の距離の演算を高速化できる。
【０２１７】
（付記２−１７）
前記特徴ベクトルは、ｋ−ｍｅａｎｓ  ｔｒｅｅによる近似最近傍探索の対象となるベクトルであり、
前記実数ベクトルは、ｋ−分木のノードに登録されている代表ベクトルであり、
前記ベクトル演算部は、前記特徴ベクトルと前記代表ベクトルとの間の距離の演算を含むクラスタリング処理を行なう
ことを特徴とする付記２−１ないし２−１４のいずれか一項に記載の特徴量演算装置。
【０２１８】
この構成により、ｋ−ｍｅａｎｓ  ｔｒｅｅによる近似最近傍探索における特徴ベクトルとｋ−分木のノードに登録されている代表ベクトルとの間の距離の演算を高速化できる。
【０２１９】
（付記２−１８）
前記特徴ベクトルは、画像の特徴量を表すベクトルであることを特徴とする付記２−１５ないし２−１７のいずれか一項に記載の特徴量演算装置。
【０２２０】
この構成により、画像の特徴量の演算における特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０２２１】
（付記２−１９）
コンピュータを、付記２−１ないし２−１８のいずれか一項に記載の特徴量演算装置として機能させるための特徴量演算プログラム。
【０２２２】
この構成によっても、実数ベクトルは三値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０２２３】
（付記２−２０）
二値化された特徴ベクトルを取得する特徴ベクトル取得ステップと、
実数ベクトルを取得する実数ベクトル取得ステップと、
前記実数ベクトルを複数の三値の基底ベクトルの線形和に分解する実数ベクトル分解ステップと、
前記特徴ベクトルと分解された前記実数ベクトルとの内積計算を含む演算を行なう特徴ベクトル演算ステップと、
を含むことを特徴とする特徴量演算方法。
【０２２４】
この構成によっても、実数ベクトルは三値の基底ベクトルの線形和に分解されたうえで二値化された特徴ベクトルとの内積計算が行なわれるので、特徴ベクトルと実数ベクトルの内積計算を高速化できる。
【０２２５】
（付記３−１）
二値化された特徴ベクトルを取得する特徴ベクトル取得部と、
実数ベクトルを取得する実数ベクトル取得部と、
前記実数ベクトルを離散値の要素を持つ複数の基底ベクトルの線形和に分解する実数ベクトル分解部と、
前記特徴ベクトルと分解された前記実数ベクトルとの内積を所定の閾値とを比較するための演算を行なうベクトル演算部と、
を備え、
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、前記特徴ベクトルと分解された前記実数ベクトルとの内積が、前記閾値よりも大きくなるか否か、及び／又は前記閾値よりも小さくなるか否かを判断する
ことを特徴とする特徴量演算装置。
【０２２６】
この構成により、実数ベクトルが離散値の要素を持つ複数の基底ベクトルの線形和に分解されるので、特徴ベクトルと分解された実数ベクトルとの内積計算を基底ベクトルの数に応じた段階に分けることができ、このために、閾値処理もそれらの段階ごとに行なうことができ、すべての段階の計算を終える前に早期に、特徴ベクトルと分解された実数ベクトルとの内積が閾値より大きい、又は小さいという判断が可能になる。
【０２２７】
（付記３−２）
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、当該基底ベクトルまでの内積の合計が、最大側早期判定用閾値より大きいか否かによって、前記特徴ベクトルと分解された前記実数ベクトルとの内積が、前記閾値よりも大きくなるか否かを判断することを特徴とする付記３−１に記載の特徴量演算装置。
【０２２８】
この構成により、特徴ベクトルと複数の基底ベクトルの各々との内積計算ごとに、それまでに計算された内積の合計と、その段階の最大側早期判定用閾値とを比較することで、特徴ベクトルと分解された実数ベクトルとの内積が閾値より大きくなるか否かを判断できる。
【０２２９】
（付記３−３）
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積が取りうる最小値を学習によって求めて、前記閾値から内積計算を行なっていない前記基底ベクトルと前記特徴ベクトルとの内積がとりうる値の最小値の合計を引いて、前記最大側早期判定用閾値を求めることを特徴とする付記３−２に記載の特徴量演算装置。
【０２３０】
この構成により、まだ内積計算を行なっていない前記基底ベクトルと前記特徴ベクトルとの内積の合計が最も小さくなったとしても、特徴ベクトルと分解された実数ベクトルとの最終的な内積が閾値を下回ることはないことを判断できるので、それによって、特徴ベクトルと分解された実数ベクトルとの内積は閾値より大きくなると判断できる。
【０２３１】
（付記３−４）
前記特徴ベクトルと前記複数の基底ベクトルの各々との内積が取りうる最小値は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積が取りうる値のうちの最小側の上位の所定の割合にある値であることを特徴とする付記３−３に記載の特徴量演算装置。
【０２３２】
この構成により、学習による特徴ベクトルと基底ベクトルとの内積が取りうる最小値の決定を高速化できる。
【０２３３】
（付記３−５）
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、当該基底ベクトルまでの内積の合計が、最小側早期判定用閾値より小さいか否かによって、前記特徴ベクトルと分解された前記実数ベクトルとの内積が、前記閾値よりも小さくなるか否かを判断することを特徴とする付記３−１ないし３−４のいずれか一項に記載の特徴量演算装置。
【０２３４】
この構成により、特徴ベクトルと複数の基底ベクトルの各々との内積計算ごとに、それまでに計算された内積の合計と、その段階の最小側早期判定用閾値とを比較することで、特徴ベクトルと分解された実数ベクトルとの内積が閾値より小さくなるか否かを判断できる。
【０２３５】
（付記３−６）
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積が取りうる最大値を学習によって求めて、前記閾値から内積計算を行なっていない前記基底ベクトルと前記特徴ベクトルとの内積がとりうる値の最大値の合計を引いて、前記最小側早期判定用閾値を求めることを特徴とする付記３−５に記載の特徴量演算装置。
【０２３６】
この構成により、まだ内積計算を行なっていない前記基底ベクトルと前記特徴ベクトルとの内積の合計が最も大きくなったとしても、特徴ベクトルと分解された実数ベクトルとの最終的な内積が閾値を上回ることはないことを判断できるので、それによって、特徴ベクトルと分解された実数ベクトルとの内積は閾値より小さくなると判断できる。
【０２３７】
（付記３−７）
前記特徴ベクトルと前記複数の基底ベクトルの各々との内積が取りうる最大値は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積が取りうる値のうちの最大側の上位の所定の割合にある値であることを特徴とする付記３−６に記載の特徴量演算装置。
【０２３８】
この構成により、学習による特徴ベクトルと基底ベクトルとの内積が取りうる最大値の決定を高速化できる。
【０２３９】
（付記３−８）
前記実数ベクトル分解部は、前記複数の基底ベクトルの各係数を絶対値の大きさの順にすることを特徴とする付記３−１ないし３−７のいずれか一項に記載の特徴量演算装置。
【０２４０】
この構成により、早い段階で特徴ベクトルと分解された実数ベクトルとの内積が閾値よりも大きくなるか否か、及び／又は閾値よりも小さくなるか否かを判断できる。
【０２４１】
（付記３−９）
前記特徴ベクトルは、ＨｏＧ特徴量であり、
前記実数ベクトルは、線形ＳＶＭの重みベクトルであり、
前記ベクトル演算部は、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、線形ＳＶＭによって前記特徴ベクトルの識別を行なうことを特徴とする付記３−１ないし３−８のいずれか一項に記載の特徴量演算装置。
【０２４２】
この構成により、線形ＳＶＭにおいて、すべての段階の計算を終える前に早期に、特徴ベクトルの識別を行なうことができる。
【０２４３】
（付記３−１０）
コンピュータを、付記３−１ないし３−９のいずれか一項に記載の特徴量演算装置として機能させるための特徴量演算プログラム。
【０２４４】
この構成によっても、実数ベクトルが離散値の要素を持つ複数の基底ベクトルの線形和に分解されるので、特徴ベクトルと分解された実数ベクトルとの内積計算を基底ベクトルの数に応じた段階に分けることができ、このために、閾値処理もそれらの段階ごとに行なうことができ、すべての段階の計算を終える前に早期に、特徴ベクトルと分解された実数ベクトルとの内積が閾値より大きい、又は小さいという判断が可能になる。
【０２４５】
（付記３−１１）
二値化された特徴ベクトルを取得する特徴ベクトル取得ステップと、
実数ベクトルを取得する実数ベクトル取得ステップと、
前記実数ベクトルを離散値の要素を持つ複数の基底ベクトルの線形和に分解する実数ベクトル分解ステップと、
前記特徴ベクトルと分解された前記実数ベクトルとの内積を所定の閾値とを比較するための演算を行なう特徴ベクトル演算ステップと、
を含み、
前記特徴ベクトル演算ステップは、前記特徴ベクトルと前記複数の基底ベクトルの各々との内積計算ごとに、前記特徴ベクトルと分解された前記実数ベクトルとの内積が、前記閾値よりも大きくなるか否か、及び／又は前記閾値よりも小さくなるか否かを判断する
ことを特徴とする特徴量演算方法。
【０２４６】
この構成によっても、実数ベクトルが離散値の要素を持つ複数の基底ベクトルの線形和に分解されるので、特徴ベクトルと分解された実数ベクトルとの内積計算を基底ベクトルの数に応じた段階に分けることができ、このために、閾値処理もそれらの段階ごとに行なうことができ、すべての段階の計算を終える前に早期に、特徴ベクトルと分解された実数ベクトルとの内積が閾値より大きい、又は小さいという判断が可能になる。
【０２４７】
（付記４−１）
二値化された特徴ベクトルを取得する特徴ベクトル取得部と、
二値の離散値のみから構成された要素を持つ複数の二値ベクトルを取得する二値ベクトル取得部と、
前記特徴ベクトルと前記複数の二値ベクトルの各々との内積計算を順次行うベクトル演算部と、
を備え、
前記ベクトル演算部は、前記特徴ベクトルと前記二値ベクトルとの排他的論理和をとることで、前記特徴ベクトルと前記二値ベクトルとの内積を計算することを特徴とする特徴量演算装置。
【０２４８】
この構成により、二値化された特徴ベクトルと二値ベクトルとの排他的論理和をとるという負荷の少ない計算で、二値化された特徴ベクトルと二値ベクトルの内積計算を高速化できる。
【０２４９】
（付記４−２）
二値化された特徴ベクトルを取得する特徴ベクトル取得部と、
−１、０、１の三値のみから構成された要素を持つ複数の三値ベクトルを取得する三値ベクトル取得部と、
前記特徴ベクトルと前記複数の三値ベクトルの各々との内積計算を順次行うベクトル演算部と、
を備え、
前記ベクトル演算部は、前記特徴ベクトルと前記三値ベクトルとの内積計算において、前記三値ベクトルの０の要素を−１又は１の任意のいずれかに置換して０置換ベクトルを生成し、前記三値ベクトルの０の要素を−１に置換し、かつ０以外の要素を１に置換してフィルタベクトルを生成し、前記特徴ベクトルと前記０置換ベクトルとの排他的論理和と前記フィルタベクトルとの論理積をとることで、前記特徴ベクトルと前記三値ベクトルとの間の非０で異なる要素の要素数Ｄｆｉｌｔｅｒｄ＿ｈａｍｍｉｎｇを求め、前記要素数Ｄｆｉｌｔｅｒｄ＿ｈａｍｍｉｎｇ及び非０の要素数を前記特徴ベクトルの要素数から引くことで、前記特徴ベクトルと前記三値ベクトルとの間の非０で同一の要素の要素数を求め、前記特徴ベクトルと前記三値ベクトルとの間の非０で同一の要素の要素数から前記特徴ベクトルと前記三値ベクトルとの間の非０で異なる要素の要素数を引くことで、前記特徴ベクトルと前記三値ベクトルとの内積を求めることを特徴とする特徴量演算装置。
【０２５０】
この構成により、０置換ベクトル及びフィルタベクトルを利用して、二値化された特徴ベクトルと三値ベクトルとの内積演算をハミング距離の計算によって行なうことができ、二値化された特徴ベクトルと三値ベクトルの内積計算を高速化できる。
【産業上の利用可能性】
【０２５１】
本発明は、特徴ベクトルと実数ベクトルの内積計算を高速化できるという効果を有し、画像、音声、文字等のコンテンツの特徴ベクトルを用いた演算処理を行う特徴量演算装置等として有用である。
【符号の説明】
【０２５２】
１００  特徴量演算装置
１０１  コンテンツ取得部
１０２  特徴ベクトル生成部
１０３  特徴ベクトル二値化部
１０４  実数ベクトル取得部
１０５  実数ベクトル分解部
１０６  ベクトル演算部（内積演算部）
１０  物体認識装置
１１  ピラミッド画像生成部
１２  ＨｏＧ特徴量抽出部
１３  バイナリコード変換部
１４  パラメータ決定部
１５  パラメータ行列分解部
１６  線形ＳＶＭ識別部
２０  ｋ−ｍｅａｎｓクラスタリング装置
２１  コンテンツ取得部
２２  特徴ベクトル生成部
２３  特徴ベクトル二値化部
２４  代表ベクトル更新部
２５  収束判定部
２６  代表ベクトル分解部
２７  最近接代表ベクトル算出部
【図１】
2014112358.tif 000049
【図２】
2014112358.tif 000050
【図３】
2014112358.tif 000051
【図４】
2014112358.tif 000052
【図５】
2014112358.tif 000053
【図６】
2014112358.tif 000054