(57)【特許請求の範囲】
【請求項１】
多次元ベクトルデータを取得するベクトルデータ取得部と、
近傍にある多次元ベクトルデータどうしをクラスター化したベクトル空間における領域を複数保持するためのクラスター保持部と、
取得した多次元ベクトルデータがいずれかの領域に含まれるか判断する包含判断部と、
包含判断部での判断結果が包含されないとの判断結果である場合には取得した多次元ベクトルデータに基づいて新たな領域をクラスター保持部に登録するクラスター登録部と、
包含判断部での判断結果が包含されるとの判断結果である場合にはその履歴である包含判断結果履歴を記録する包含判断結果履歴記録部と、
包含判断結果記録部での包含判断結果履歴における包含判断率が領域の新規登録を中止する所定の条件を満たすか判断する中止判断部と、
中止判断部での判断結果が所定の条件を満たすとの判断結果である場合にはクラスター登録部での新規の登録を中止するようにクラスター登録部を制御する中止制御部と、
を有する量子化装置。
【請求項２】
前記所定の条件は、包含判断部での所定回数中の判断結果としてのいずれにも包含されないとの結果を得た回数、いずれかに包含されるとの結果を得た回数、の関係で定められる請求項１に記載の量子化装置。
【請求項３】
近傍にある多次元ベクトルデータどうしをクラスター化したベクトル空間における領域を複数保持するためのクラスター保持部を有する量子化装置の動作方法であって、
多次元ベクトルデータを取得するベクトルデータ取得ステップと、
取得した多次元ベクトルデータがいずれかの領域に含まれるか判断する包含判断ステップと、
包含判断ステップでの判断結果が包含されないとの判断結果である場合には取得した多次元ベクトルデータに基づいて新たな領域をクラスター保持部に登録するクラスター登録ステップと、
包含判断ステップでの判断結果が包含されるとの判断結果である場合にはその履歴である包含判断結果履歴を記録する包含判断結果履歴記録ステップと、
包含判断結果記録ステップでの包含判断結果履歴における包含判断率が領域の新規登録を中止するための所定の条件を満たすか判断する中止判断ステップと、
中止判断ステップでの判断結果が所定の条件を満たすとの判断結果である場合にはクラスター登録ステップでの新規の登録を中止するように制御する中止制御ステップと、
を有する量子化装置の動作方法。
【請求項４】
近傍にある多次元ベクトルデータどうしをクラスター化したベクトル空間における領域を複数保持するためのクラスター保持部を有する量子化装置を動作させるプログラムであって、
多次元ベクトルデータを取得するベクトルデータ取得ステップと、
取得した多次元ベクトルデータがいずれかの領域に含まれるか判断する包含判断ステップと、
包含判断ステップでの判断結果が包含されないとの判断結果である場合には取得した多次元ベクトルデータに基づいて新たな領域をクラスター保持部に登録するクラスター登録ステップと、
包含判断ステップでの判断結果が包含されるとの判断結果である場合にはその履歴である包含判断結果履歴を記録する包含判断結果履歴記録ステップと、
包含判断結果記録ステップでの包含判断結果履歴における包含判断率が領域の新規登録を中止するための所定の条件を満たすか判断する中止判断ステップと、
中止判断ステップでの判断結果が所定の条件を満たすとの判断結果である場合にはクラスター登録ステップでの新規の登録を中止するように制御する中止制御ステップと、
を計算機に実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多次元のベクトルデータをベクトル空間内でクラスタリングして保持する技術に関する。
【背景技術】
【０００２】
例えば、類似画像検索などの画像認識（あるいは画像照合）技術において、近年ＢｏＶＷ（Bag of Visual Words）という手法が用いられるようになっている。この手法は、母集団となる複数の画像（学習画像という）から抽出される多次元のベクトルデータである局所特徴量をクラスタリング（個々のクラスターをビジュアルワード、Visual Words＝ VWと称する。）し所定のベクトル空間領域を割り当てて保持しておくとともに、認識すべき画像が有する局所特徴量がいずれのクラスターに属しているか、ないしは属していないか、さらには属しているとした場合にそのクラスターに属する局所特徴量の出現数（出現頻度）はいくつか、などに基づき認識画像と類似する画像を母集団中にて特定する手法である。このように多次元データである局所特徴量を量子化することで画像認識などを高速で処理することができる。
【０００３】
ここで画像認識の精度は、各クラスターに割り当てられるベクトル空間領域の広狭に依存する傾向がある。広すぎる場合には非類似と認識すべき画像を類似画像として抽出するおそれがあり、狭すぎる場合には類似と認識すべき画像を非類似画像と判断してしまうおそれがある。そのため、クラスタリングによる各領域を適正な所定範囲に収めるため、新たにビジュアルワードを登録する際には、既登録の各ビジュアルワードを検索し局所特徴量において同一ないし所定範囲内に近接する局所特徴量については新たなビジュアルワードとして登録しない処理を行う（特許文献１）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１５−２２４６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
前述のようなビジュアルワードの新規登録処理を進めていくことで各クラスターが所定の領域を有しつつベクトル空間領域がそれら各クラスターにより埋められていく。それに伴い、学習画像から抽出された局所特徴量が新たなビジュアルワードとして登録される頻度が低下していく。ビジュアルワードの登録数が充足してもなお新たにビジュアルワードとして登録するための処理を継続することは無駄である。
【０００６】
例示したように、画像や音声などの対象から抽出した多次元のベクトルデータにより対象の解析や認識などを行うにあたり、ベクトル空間における各クラスターの登録を所定条件の下、停止するように構成し、新たにクラスターを登録するための処理が無用に継続することを抑制することが望ましい。
【課題を解決するための手段】
【０００７】
そこで、上記課題を解決するために本発明において、以下の量子化装置などを提供する。すなわち、多次元ベクトルデータを取得するベクトルデータ取得部と、近傍にある多次元ベクトルデータどうしをクラスター化したベクトル空間における領域を複数保持するためのクラスター保持部と、取得した多次元ベクトルデータがいずれかの領域に含まれるか判断する包含判断部と、包含判断部での判断結果が包含されないとの判断結果である場合には取得した多次元ベクトルデータに基づいて新たな領域をクラスター保持部に登録するクラスター登録部と、包含判断部での判断結果が包含されるとの判断結果である場合にはその履歴である包含判断結果履歴を記録する包含判断結果履歴記録部と、包含判断結果記録部での包含判断結果履歴が領域の新規登録を中止する所定の条件を満たすか判断する中止判断部と、中止判断部での判断結果が所定の条件を満たすとの判断結果である場合にはクラスター登録部での新規の登録を中止するようにクラスター登録部を制御する中止制御部と、を有する量子化装置などを提供する。
【発明の効果】
【０００８】
本発明によれば、登録のために抽出した多次元ベクトルデータが既存のベクトル空間における領域に含まれるか否かの判断結果の履歴に基づき、新規にベクトル空間内の領域を登録する処理を中止することでき、新規登録のための処理を無用に行い続けることを抑制することができる。
【図面の簡単な説明】
【０００９】
【図１】本量子化装置の機能的構成の一例を示すブロック図
【図２】認識対象画像から抽出される局所特徴量の一例を示す概念図
【図３】ベクトル空間における領域を登録する処理の一例を示す概念図
【図４】包含判断結果履歴の一例を示す図
【図５】包含判断結果履歴の一例を示す図
【図６】本量子化装置のハードウェア構成の一例を表す概略図
【図７】本量子化装置における処理の流れの一例を表すフロー図
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について、添付図面を用いて説明する。なお、本発明は、これら実施形態に何ら限定されるべきものではなく、その要旨を逸脱しない範囲において、種々なる態様で実施し得る。
＜実施形態＞
＜概要＞
【００１１】
本実施形態の量子化装置は、登録のために抽出した多次元ベクトルデータがベクトル空間においてすでにクラスタリングされた領域に含まれるか否かの判断結果の履歴に基づき、新規にクラスターを登録する処理を中止することを特徴とする。かかる構成によりクラスターの新規登録のための処理を無用に行い続けることを抑制することができる。
＜構成＞
【００１２】
図１は、本実施形態の量子化装置の機能ブロックの一例を示すブロック図である。なお、以下に記載する本装置の機能ブロックは、ハードウェア及びソフトウェアの組み合わせとして実現され得る。具体的には、コンピュータを利用するものであれば、ＣＰＵ（中央演算装置）や主メモリ、システムバス、あるいは二次記憶装置（ハードディスクドライブや不揮発性メモリ、ＣＤやＤＶＤなどの記憶メディアとそれらメディアの読取ドライブなど）、情報入力に利用される入力デバイス、表示装置、その他の外部周辺装置などのハードウェア構成部、またその外部周辺装置用のインターフェース、通信用インターフェース、それらハードウェアを制御するためのドライバプログラムやその他アプリケーションプログラム、ユーザ・インターフェース用アプリケーションなどが挙げられる。
【００１３】
そして主メモリ上に展開したプログラムに従ったＣＰＵの演算処理によって、入力デバイスやその他インターフェースなどから入力され、メモリやハードディスク上に保持されているデータなどが加工、蓄積されたり、上記各ハードウェアやソフトウェアを制御するための命令が生成されたりする。あるいは本装置の機能ブロックは専用ハードウェアによって実現されてもよい。また、本装置は一つのハードウェアやソフトウェアにより構成される場合に限られず、複数のハードウェアやソフトウェアの組み合わせによって構成されてもよく、ネットワークを介在したサーバ装置を含んで構成されてもよい。
【００１４】
また、この発明は装置として実現できるのみでなく、方法としても実現可能である。また、このような発明の一部をソフトウェアとして構成することができる。さらに、そのようなソフトウェアをコンピュータに実行させるために用いるプログラム、及びプログラムを固定した記録媒体も、当然にこの発明の技術的な範囲に含まれる（本明細書の全体を通じて同様である）。
【００１５】
図１に示すように、本実施形態の量子化装置０１００は、ベクトルデータ取得部０１０１と、クラスター保持部０１０２と、包含判断部０１０３と、クラスター登録部０１０４と、包含判断結果履歴記録部０１０５、中止判断部０１０６と、中止制御部０１０７とを有する。
【００１６】
ベクトルデータ取得部０１０１は、多次元ベクトルデータを取得する機能を有する。多次元データを取得する対象としては、例えば、画像や音声の特徴量、水位や潮位、地震動（地面の動き）、大気中のＣＯ２やＰＭ２．５の濃度分布など数値で表現されるものすべてである。また、多次元データの例としては、画像を対象として取得することができる局所特徴量などがある。
【００１７】
画像における局所特徴量は、対象に応じて種々に定義され、あるいは対象の解析や認識をする者により任意に定義され得る特徴領域から取得される特徴量である。例えば、画像においては輪郭やコーナーなどの領域が該当する。
【００１８】
また、対象からベクトルデータを取得するための技術は、対象に応じてすでに種々存在し、いずれかを用いるかは限定しない。例えば、画像を対象としてベクトルデータを取得する場合には、ＳＩＦＴやＨｏＧなどの手法を用いることができる。これらの手法により取得されるベクトルデータは、数百にも及ぶ高次元のベクトルデータとなる。
【００１９】
以下、ベクトルデータを取得する対象の一例としての画像を挙げ、各構成について説明する。
【００２０】
図２は、ベクトルデータを取得する対象を画像とした場合に、取得されるベクトルデータを例示する概念図である。図２（ａ）に示すように、「トラック」の画像を対象としており、図中の丸で指し示す箇所が特徴領域であり、である当該領域における特徴量をベクトルデータとして取得する。
【００２１】
クラスター保持部０１０２は、近傍にある多次元ベクトルデータどうしをクラスター化したベクトル空間における領域を複数保持する機能を有する。このようなベクトル空間においてクラスタリングされる領域のことを、画像認識などの技術分野においてはビジュアルワードという。そして、ベクトル空間を多次元ベクトルデータ間の距離（ユークリッド距離など）に基づきクラスタリングする。例えば、図２（ｂ）は、１０のビジュアルワードで分画されたベクトル空間を示す概念図である。
【００２２】
クラスターの保持は、例えば、クラスターを代表する多次元ベクトルデータをそのクラスターのＩＤと紐付けて保持する。また、当該クラスターに含まれると判断するために規定される距離（当該クラスターを代表する多次元ベクトルデータとの距離）を併せて保持してもよい。
【００２３】
また、クラスターＩＤと紐付けられる多次元ベクトルデータは、対象から取得したベクトルデータそのものであってもよいし、後述するクラスターの登録処理による総クラスター数の増加に伴い改めてもよい。
【００２４】
包含判断部０１０３は、取得した多次元ベクトルデータがいずれかの領域に含まれるか判断する機能を有する。前述の通り、保持されるクラスターはそのクラスターを代表する多次元ベクトルデータと規定された距離に基づく所定の範囲を有する。例えば、その多次元ベクトルデータを中心とし規定された距離を半径とする円領域である。
【００２５】
図３は、クラスターの登録について概略を示す概念図である。図３（ａ）は、保持される５つのクラスターの領域をベクトル空間０３００に配置した概念図である。ＩＤ１のクラスター０３０１は、所定範囲の領域（点線円内）を有している。ＩＤ２からＩＤ５のクラスターについても同様である。
【００２６】
包含判断部は、取得した多次元ベクトルデータ０３０２と、保持されている各クラスターと紐付けられている多次元ベクトルデータとの距離（ユークリッド距離など）を計算する。その結果、取得した多次元ベクトルデータがいずれのクラスターの領域に含まれるか否かを判断する。本図の例においては、取得した多次元ベクトルデータ０３０２がいずれかのクラスターの領域に含まれないとの判断結果が得られる。このように取得した多次元ベクトルデータを包含するクラスターの存否や包含するクラスターを特定する処理を、クラスターの検索という場合がある。また、このような検索により取得したベクトルデータを包含するクラスターが存在したことを、ヒットしたという。
【００２７】
クラスター登録部０１０４は、包含判断部での判断結果が包含されないとの判断結果である場合には取得した多次元ベクトルデータに基づいて新たな領域をクラスター保持部に登録する機能を有する。前述の通り、取得した多次元ベクトルデータ０３０２は、いずれかのクラスターに包含されないとの判断結果が得られている。したがって、クラスター登録部は、図３（ｂ）に示すように、この多次元ベクトルデータに基づき新たな領域（ＩＤ６）としてクラスター保持部に登録する。
【００２８】
また、図３（ｃ）に示すように、取得した多次元ベクトルデータ０３０４が保持されるクラスター（ＩＤ１）の領域に包含されると判断された場合には、その取得した多次元ベクトルデータに基づいて新たなクラスターとして登録されない。
【００２９】
包含判断結果履歴記録部０１０５は、包含判断部での判断結果が包含されるとの判断結果である場合にはその履歴である包含判断結果履歴を記録する機能を有する。図４は、包含判断結果履歴の一例を示す図である。図示するように、累積判断回数、累積包含判断回数及び遡及包含判断回数を包含判断結果履歴として保持している。累積判断回数は、包含判断部により直近の判断時点までになされた判断の累積数である。また、累積包含判断回数は、直近の判断時点までになされたすべての判断において、包含するとの判断結果となった回数である。また、遡及包含判断回数は、直近の判断時点から遡って規定回数（Ｎ）の判断において包含するとの判断結果となった回数である。図では、規定回数を１００としている。また、包含判断回数は、ヒット回数と読み替えてもよい。
【００３０】
なお、累積包含判断回数と遡及包含判断回数との双方を必ず保持しなければならないものではなく、いずれか一方を保持するものとしてもよい。また、包含判断結果履歴として、いずれの領域にも包含されないとの結果を得た回数を保持してもよい。例えば、累積包含判断回数に換えて累積非包含判断回数を保持してもよいし、遡及包含判断回数に換えて遡及非包含判断回数を保持してもよい。
【００３１】
中止判断部０１０６は、包含判断結果記録部での包含判断結果履歴がクラスターの新規登録を中止するための所定の条件を満たすか判断する機能を有する。
【００３２】
図５は、図４で例示した包含判断結果履歴として記録したいずれかの回数の関係を所定の条件に用いた例を示している。例えば、累積包含判断率は、累積判断回数に対する累積包含判断回数の割合である。図４に示したように、累積判断回数（Ａ）が「２６９８５」で累積包含判断回数（Ｂ）が「８０９６」であるので、図５に示すように、累積包含判断率（Ｂ／Ａ）は３０．０％となる。ここで、累積包含判断率が３０％を超えたことを所定の条件とした場合には、この時点で所定の条件を満たすことになる。
【００３３】
また、前述の規定回数に対する遡及包含回数の割合である遡及包含判断率を所定の条件として用いてもよい。図４に示したように、規定回数（Ｎ）が「１００」で遡及包含判断回数（Ｂ'）が「９０」であるので、図５に示すように、遡及包含判断率（Ｂ'／Ｎ）は９０．０％となる。ここで、遡及包含判断率が９０％を超えたことを所定の条件とした場合には、この時点で所定の条件を満たすことになる。
【００３４】
なお、所定の条件は、前述のように一つ設けるものであってもよいが、複数の条件を重畳して規定してもよい。例えば、前述の累積包含判断率による条件と遡及包含判断率による条件とで、いずれか一方がその条件を満たすことを条件としてもよいし、双方の条件が満たされることを条件としてもよい。
【００３５】
また、累積判断回数が閾値Ｘを超え、かつ累積包含判断率又は遡及包含判断率がそれぞれの閾値Ｙ又はＹ'を超えたことを条件としてもよい。また、累積判断回数が閾値Ｘを超え、かつ包含するとの判断結果が連続してＺ回得られたことを所定の条件としてもよい。また、包含判断率とクラスター数を組み合わせた条件としてもよい。例えば包含判断率が閾値Ｘを超えて、かつ、クラスター数が閾値Ｃを超えた場合にのみ中止とする、条件としてもよい。
【００３６】
なお、包含判断結果履歴として、累積包含判断回数に換えて累積非包含判断回数を保持し、遡及包含判断回数に換えて遡及非包含判断回数を保持する場合にも、前述に準じ例えば遡及非包含判断率が規定の割合を下回ったことを所定の条件とするなどして、中止の条件を定めてもよい。
【００３７】
中止制御部は、中止判断部での判断結果が所定の条件を満たすとの判断結果である場合にはクラスター登録部での新規の登録を中止するようにクラスター登録部を制御する機能を有する。前述のような所定条件を満たす場合にクラスターの新規登録を中止することで、新規登録のための処理を無用に行い続けることを抑制することができる。なお、中止の制御は、中止のための条件が満たされて直ちに行ってもよいし、満たされた後に所定回数の検索（包含判断の処理）を行った後に行うようにしてもよい。
＜ハードウェア構成＞
【００３８】
図６は、上記機能的な各構成要件をハードウェアとして実現した際の、本量子化装置の構成の一例を表す概略図である。この図を利用して本量子化装置に係るそれぞれのハードウェア構成の働きについて説明する。
【００３９】
この図にあるように、量子化装置は、各種演算処理を実行するためのＣＰＵ０６０１と、主メモリ０６０２と、二次記憶装置０６０３と、通信インターフェース０６０４などを備える。二次記憶装置には画像や音声などの対象、対象から取得した多次元ベクトルデータ、クラスターデータベース、包含判断結果履歴、新規登録を中止するための条件、ベクトルデータ取得プログラムなどの各種プログラムなどが格納されている。なお、多次元ベクトルデータを取得する対象は、通信インターフェース０６０４を介して外部から取得してもよい。
【００４０】
ＣＰＵはこれら各種プログラムを主メモリに展開したうえで実行する。前記の各ハードウェア構成は、システムバス０６０５などのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【００４１】
まず、ＣＰＵは、ベクトルデータ取得プログラムを実行し、画像などの対象の多次元ベクトルデータを取得し所定の記憶領域に格納する。そして、包含判断プログラムを実行し取得した多次元ベクトルデータが保持するいずれかのクラスターの領域に含まれるか判断する。包含されないとの判断結果の場合にはクラスター登録プログラムを実行しその多次元ベクトルデータに基づいて新たな領域を登録する。包含するとの判断結果の場合には包含判断結果履歴を記録する。そして、中止判断プログラムを実行し包含判断履歴が所定の条件を満たすか判断する。満たすとの判断結果の場合には中止制御プログラムを実行しクラスターの新規登録を中止する制御を行う。
＜処理の流れ＞
【００４２】
図７は、本量子化装置における処理の流れの一例を表すフロー図である。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００４３】
図示するように、まず、多次元ベクトルデータを取得する（ベクトルデータ取得ステップ：Ｓ０７０１）。そして、取得した多次元ベクトルデータがいずれかのクラスターの領域に含まれるか判断する（包含判断ステップ：Ｓ０７０２）。包含されないとの判断結果である場合には取得した多次元ベクトルデータに基づいて新たな領域をクラスター保持部に登録する（クラスター登録ステップ：Ｓ０７０３）。包含判断ステップでの判断結果が包含されるとの判断結果である場合にはその履歴である包含判断結果履歴を記録する（包含判断結果履歴記録ステップ：Ｓ０７０４）。
【００４４】
続いて、包含判断結果履歴がクラスターの新規登録を中止するための所定の条件を満たすか判断する（中止判断ステップ：Ｓ０７０５）。中止判断ステップでの判断結果が満たさないとの結果である場合には、取得したすべての多次元ベクトルデータについていずれかのクラスターの領域に含まれるかの判断が完了したか判断する（完了判断ステップ：Ｓ０７０６）。完了判断ステップでの判断結果が完了していないとの結果である場合には未了の多次元ベクトルデータについて包含判断ステップでの処理を行う。完了判断ステップでの判断結果が完了しているとの結果である場合には処理を終了する。中止判断ステップでの判断結果が満たすとの結果である場合にはクラスター登録ステップでの新規登録を中止する制御を行う（中止制御ステップ：Ｓ０７０７）。そして、処理を終了する。
＜効果＞
【００４５】
本量子化装置によれば、登録のために取得した多次元ベクトルデータが既存のベクトル空間における領域に含まれるか否かの判断結果の履歴に基づき、新規に領域の登録をする処理を中止することでき、新規登録のための処理を無用に行い続けることを抑制することができる。
【符号の説明】
【００４６】
０１００  量子化装置
０１０１  多次元データ取得部
０１０２  クラスター保持部
０１０３  包含判断部
０１０４  クラスター登録部
０１０５  包含判断結果履歴記録部
０１０６  中止判断部
０１０７  中止制御部
【図１】
0006678445.tif 000002
【図２】
0006678445.tif 000003
【図３】
0006678445.tif 000004
【図４】
0006678445.tif 000005
【図５】
0006678445.tif 000006
【図６】
0006678445.tif 000007
【図７】
0006678445.tif 000008