画像検索装置および画像検索方法
【課題】顔/色等の多次元特徴データが高次元で大量に存在する場合でも、ユーザの望む画像を効率よく適切に検索可能な画像検索装置および画像検索方法を提供する。
【解決手段】多次元特徴データの次元を縮退して近似データとして生成する次元縮退手段１０２と、生成した近似データを次元縮退前の多次元特徴データと対応付けて蓄積する近似データ蓄積手段１０３と、検索対象人物の多次元特徴データを識別する識別子を少なくとも検索キーとして受信する検索要求受信手段１０４と、受信した検索キーに対応する近似データと近似データ蓄積手段１０３で蓄積した複数の近似データとの距離計算を行ない類似度順に並べる近似空間検索手段１０５と、類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定する実空間最終ランク付け手段１０６とを備える。
【解決手段】多次元特徴データの次元を縮退して近似データとして生成する次元縮退手段１０２と、生成した近似データを次元縮退前の多次元特徴データと対応付けて蓄積する近似データ蓄積手段１０３と、検索対象人物の多次元特徴データを識別する識別子を少なくとも検索キーとして受信する検索要求受信手段１０４と、受信した検索キーに対応する近似データと近似データ蓄積手段１０３で蓄積した複数の近似データとの距離計算を行ない類似度順に並べる近似空間検索手段１０５と、類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定する実空間最終ランク付け手段１０６とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像から抽出した多次元特徴データ(顔,色等)を用いて、大容量の画像群から所望の画像を高速に洗出すことのできる画像検索装置および画像検索方法に関するものである。
【背景技術】
【０００２】
近年、ピッキング・強盗・放火等に代表される犯罪の増加と共に、カメラ・センサ・蓄積装置等を設置し、犯罪を未然に防止する映像監視システムの普及が大幅に進んでいる。また、監視カメラのＩＰ化・蓄積装置の大容量化に伴い、数百規模の広域監視・長時間記録を行なうシステムも増加してきた。このような状況において、監視者の業務軽減を目指し、万引き犯・迷子者・落し物者等の特定人物の洗出しを効率的に行なうための技術が要望されてきている。
【０００３】
特定人物の洗出しを高速に行なう従来技術として、画像から抽出した多次元特徴データ群(色,顔等)を予め距離の近い順にクラスタリングして木構造にしておき、検索時には検索対象人物に最も近い部分木のみ検索する手法がある。また、特許文献１には、統計的手法により用意したモデル空間に射影して、高精度で次元数の少ない多次元特徴データを生成することで高速検索する方法が記載されている。
【特許文献１】特開２００２−１８３２０５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の木構造にする方法では、多次元特徴データの次元数が多くなると、隣接空間が指数関数的に増え、多次元特徴データをクラスタリング(登録)するのに膨大な時間を要する。さらに、検索時には、隣接空間も含め近傍検索を行なうため、登録同様、膨大な時間を要する。
また、特許文献１に記載の技術においては、射影による次元縮退には限度がある。また、その対策として、目/鼻/口等の重要度の高い部分のみを使用して類似度計算をする方法も記載されているが、個人の特徴がどこに現れるのかは千差万別で、精度を維持したまま次元を縮退するには限界がある。
【０００５】
本発明は、前記従来の事情に鑑みてなされたもので、顔/色等の多次元特徴データが高次元で大量に存在する場合でも、ユーザの望む画像を効率よく適切に検索可能な画像検索装置および画像検索方法を実現することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の画像検索装置は、画像から抽出した多次元特徴データの次元を縮退して近似データを生成する次元縮退手段と、前記次元縮退手段で生成した近似データを次元縮退前の多次元特徴データと対応付けて蓄積する近似データ蓄積手段と、少なくとも、検索対象人物の多次元特徴データを識別する識別子を検索キーとして受信する検索要求受信手段と、検索条件に基づいて、前記検索要求受信手段で受信した検索キーに対応する近似データと前記近似データ蓄積手段で蓄積した複数の近似データのそれぞれとの距離計算を行ない類似度順に並べる近似空間検索手段と、前記近似空間検索手段で得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定し、検索結果として出力する実空間最終ランク付け手段とを備える。
【０００７】
この構成により、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みができるため、次元数が高次元になった時でもユーザの望む画像を効率よく検索することができる。また、検索結果を類似度順で出力するため、より効率よく検索することができる。
【０００８】
また、本発明の画像検索装置は、前記次元縮退手段が、前記多次元特徴データを構成する要素を絶対値の大きい順に並替え、上位Ｎ個（Ｎ：自然数）の(要素番号,値)を前記近似データとして生成することを特徴とする。また、本発明の画像検索装置は、前記次元縮退手段が、入力する多次元特徴データのウェーブレット変換結果から、高周波成分又は低周波成分の上位Ｎ個の値を前記近似データとして生成することを特徴とする。また、本発明の画像検索装置は、前記次元縮退手段で得られた上位Ｎ個以外の多次元特徴データを(代表値,符号ビット)として生成し前記近似データとして管理することを特徴とする。
【０００９】
この構成により、人物の特徴を強く表わす部分の影響が強く出るように次元を縮退することができるため、近似空間上で検索結果を絞込む過程における検索漏れを少なくすることができる。
【００１０】
また、本発明の画像検索装置は、前記実空間最終ランク付け手段が、前記近似空間検索手段で得られた類似度の高い上位Ｍ件（Ｍ：自然数）に対して最終順位付けを行ない、検索結果として上位Ｋ件(Ｋ<Ｍ)を出力することを特徴とする。
【００１１】
この構成により、近似空間上で検索結果を絞込む過程における検索漏れを抑制することができる。
【００１２】
また、本発明の画像検索装置は、前記実空間最終ランク付け手段が、前記近似空間検索手段で得られた類似度の高い要素(すなわち近似距離の小さい要素)から順に、次元縮退前の多次元特徴データを用いて再距離計算を行ない、再距離計算して得られた類似度の高い上位Ｋ件の実距離が、再距離計算を行なっていない全データの近似距離より小さくなった時点で処理を完了し、前記上位Ｋ件を検索結果として出力することを特徴とする。
【００１３】
この構成により、全ての次元を用いて距離計算を行なう場合と同じ結果を得ることができるため、近似空間上で検索結果を絞込む過程における検索漏れを０にすることができる。
【００１４】
また、本発明の画像検索装置は、前記実空間最終ランク付け手段が、前記近似空間検索手段で得られた結果が、最終ランク付けでどの程度変更したかを示す「次元縮退による歪み率」を結果として出力することを特徴とする。
【００１５】
この構成により、ユーザは、近似空間上で検索結果を絞込む過程で検索漏れがどの程度発生したかを把握することができるため、効率的に画像を再検索することができる。
【００１６】
また、本発明の画像検索装置は、「利用する次元数」と「絞込む件数」を、前記近似空間検索手段が用いる検索条件として指定する再検索条件指定手段を備えることを特徴とする。
【００１７】
この構成により、近似空間上で検索結果を絞込む過程で検索漏れが発生した場合であっても、ユーザが再検索による絞込み操作を簡単に行なうことができる。また、再検索条件指定手段が、実空間最終ランク付け手段で出力した「次元縮退による歪み率」を参照して自動的に検索条件を再指定する構成をとれば、より効率的に画像を検索できる。
【００１８】
また、本発明の画像検索装置は、前記実空間最終ランク付け手段で出力した検索結果に対して正解または不正解を指定する正誤指定手段を備えたことを特徴とする。また、本発明の画像検索装置は、前記近似空間検索手段が、前記正誤指定手段で正解と指定した近似データの要素番号を「正解要素番号群」として、また、不正解と指定した近似データの要素番号を「誤り要素番号群」として設定し、近似データを用いた距離計算過程で、「正解要素番号群」に含まれる各要素番号の重み付けを強く、「誤り要素番号群」に含まれる各要素番号の重み付けを弱くすることを特徴とする。
【００１９】
この構成により、近似空間上で検索結果を絞込む過程で検索漏れが多く発生しても、ユーザが再検索による絞込み操作を簡単に行なうことができる。
【００２０】
さらに、本発明の画像検索方法は、画像から抽出した多次元特徴データの次元を縮退して生成した近似データを用いて、画像蓄積手段に蓄積されている画像群を検索対象画像との類似度順に並べる近似空間検索ステップと、前記近似空間検索ステップで得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再類似度計算を行ない最終順位を決定する実空間最終ランク付けステップとを有する。
【発明の効果】
【００２１】
本発明によれば、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みができるため、次元数が高次元になった時でもユーザの望む画像を効率よく検索することができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００２３】
（実施の形態１）
図１は、本発明の実施の形態１における画像検索装置の構成図である。図１において、１１は、人物を撮影するカメラ、１２は、指定された検索条件に該当する人物を含む画像を検索する検索サーバ、１３は、検索サーバ１２に対して検索条件を指定して検索を実行させるための検索端末である。１０１は、カメラ１１で撮影した画像から、顔/色/形状などの人物を識別するための多次元特徴データを抽出する多次元特徴データ生成手段、１０２は、多次元特徴データ生成手段１０１で抽出した多次元特徴データの次元を縮退して近似データを生成する次元縮退手段、１０３は、次元縮退手段１０２で生成した近似データと次元縮退前の多次元特徴データと対応付けて、それぞれ近似特徴データ群１０３ａと実特徴データ群１０３ｂとして蓄積する近似データ蓄積手段、１０４は、少なくとも、検索対象人物の多次元特徴データを識別する識別子を検索キーとして受信する検索要求受信手段、１０５は、検索端末１３で指定された検索条件に基づいて、検索要求受信手段１０４で受信した検索キーに対応する近似データと近似データ蓄積手段１０３で蓄積した複数の近似データのそれぞれとの距離計算を行ない、計算結果の距離順すなわち類似度順に並べる近似空間検索手段、１０６は、近似空間検索手段１０５で得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定する実空間最終ランク付け手段である。実空間最終ランク付け手段１０６で決定された最終順位は、検索結果として出力される。
【００２４】
多次元特徴データ生成手段１０１で抽出する人物特徴データは、画像から切出した移動体の画像データであり、或いは、形状・色・大きさ、動きなどにより移動体を特定する情報であり、或いは、顔の目・鼻・口の形状や位置などを特定する情報である。これらの特徴情報の抽出分類方法は広く知られており、例えば、特開2001-268657号公報、及び、「画像の処理と認識」(安居院猛・長尾智晴 共著、昭晃堂出版)に厳密に記されている。これらの既存技術を利用して生成した顔/服装色等の人物特徴データは、人物を特定するために複数の要素(次元と呼ぶ)から構成されている。例えば、顔特徴データは、全体の顔つきを把握するための要素群、目/鼻/口等の特定部品の形状を把握するための要素群の合計：数百〜数千次元から構成される。
【００２５】
図２は、次元縮退手段１０２の処理手順を示したもので、以下その動作について説明する。
【００２６】
＜ステップ２０１＞入力された多次元特徴データ([要素番号,値]の系列)に対して、値を全て絶対値にして、値の大きいものから順にソートする。入力される多次元特徴データは、２−ａのように、顔全体/部品単位の主成分を持つ顔特徴データや、人物の服装の色分布をRGB/HSV等の色空間ヒストグラムとして表わしたデータや、さらに、人物が写っている領域を切出して周波数に変換したデータなどで、横軸の各要素の[要素番号,値]の集合が、ステップ２０１の多次元特徴データの入力として与えられる。また、ソート後は２−ｂのように絶対値が大きいものから順に並べられ、横軸の各要素は、[ソート前の要素番号、値]として生成される。
【００２７】
＜ステップ２０２＞指定された次元(Ｒ)で、多次元特徴データを分離（次元をカット）する。分離後、指定次元Ｒ以内の要素(絶対値の大きい要素)は、Ｒ１データとして[ソート前の要素番号,値]の系列として出力され、また、指定次元Rより大きい部分は、Ｒ２データとして、[代表値Ｖ,Ｒ２内の符号ビット列]として生成される（２−ｃ）。なお、Ｒ２データの代表値Ｖは、Ｒ２データの絶対値での平均値、或いは、Ｒ２データの絶対値の最大値が用いられる。また、符号ビット列は、Ｒ２のＮ番目の要素の値が正ならビット値＝１、負ならビット値＝０として、Ｒ２の要素数分の符号が分かるビット列として生成される。
【００２８】
＜ステップ２０３＞ステップ２０２で生成したＲ１及びＲ２データを近似データ蓄積手段１０３の近似特徴データ群103aへ格納する。また、ステップ２０１で入力されたソート前ベクトルデータを実特徴データ群103bへ格納する。このようにしてインデクスを生成する。なお、近似特徴データ群103aは、次元を縮退したデータ群であるため、高速アクセス可能なメモリ上に配置するようにしてもよい。
【００２９】
図３は、近似空間検索手段１０５及び実空間最終ランク付け手段１０６の処理手順を示したもので、以下その動作について説明する。
【００３０】
＜ステップ３０１＞検索要求受信手段１０４で受信した検索キーに対応する近似データ(３−ａ)と近似データ蓄積手段１０３で蓄積した複数の近似データ（３−ｂ）との近似距離計算を行ない、近似データ蓄積手段１０３で蓄積した複数の近似データを近似距離の小さい順に並べる。近似距離計算は、３−ｃに示すように、ソート前の全ての次元に対して、
1) 各次元が、(3-a),(3-b)のR1に含まれれば、R1にある値を用いて距離計算を行なう。
2) 各次元が、(3-a),(3-b)のR2に片方含まれれば、R2に含まれるものに対しては、R2の代表値(V)と符号ビットから近似値を算出し、それを用いて距離計算を行なう。
といった処理を行なう。
【００３１】
＜ステップ３０２＞ステップ３０１で距離の小さい順に並べた上位Ｍ件に対して、検索要求受信手段１０４で受信した検索キーとの実距離計算を行ない、３−ｄのように実距離の小さい順に上位Ｋ件を抽出し結果として返す。実距離は、実特徴データ群103bに格納したソート前ベクトルデータから計算する。
【００３２】
図３の処理は、近似距離の小さい順に並べた上位Ｍ件に対して、実空間上で最終順位付けを行なうものだが、上位Ｍ件に絞込んだ時点で検索漏れを起こす可能性がある。図４は、近似空間上での絞込みによる検索漏れを０にするための実空間最終ランク付け手段１０８の処理手順を示したもので、以下その動作について説明する。
【００３３】
＜ステップ４０１＞近似空間検索手段１０５で生成した、検索キーとの近似距離のリストを取得する。リストは、近似距離の小さいものから順に格納されているものとする。
【００３４】
＜ステップ４０２＞近似距離リストから、近似距離の小さいデータを取得する。取得した時点で、近似距離リストから該当データを削除する。
【００３５】
＜ステップ４０３＞ステップ４０２で取得したデータと検索キーに対応するデータとの実距離を計算する。
【００３６】
＜ステップ４０４＞ステップ４０２で取得したデータを実距離リストへ追加する。リストは、実距離の小さいものから順に格納されるようにする。
【００３７】
＜ステップ４０５＞実距離リストの上位Ｋ件の全ての距離が、近似距離リスト内の最小距離より小さいか判定する。Ｙｅｓの場合、ステップ４０６へ、Ｎｏの場合、ステップ４０２へ移行する。
【００３８】
＜ステップ４０６＞実距離リストの上位Ｋ件を実空間最終ランク付け手段１０６の検索結果として出力する。
【００３９】
図５を用いて、図３と図４の処理手順による検索結果の違いについて述べる。５−ａは、検索キーとデータＡ〜Ｈとの「近似距離及び実距離」の例を示したものである。５−ａに対して、図３のフローで検索した場合、５−ｂに示すようにデータＧが検索漏れを起こしてしまう。これに対し、図４のフローで検索した場合は５−ｃに示すようにデータＧの検索漏れを起こすことはない。図３と図４のどちらの検索処理を採用するかは、近似距離と実距離の関係により異なる。例えば、全てのデータに対して「近似距離≒実距離」となる場合は、近似によって検索順位が大きく入替わる可能性がないため、検索漏れを防ぎつつ高速処理が可能な図４が適している。一方、「近似距離<<実距離」となる場合は、図４の処理では全データに対する検索が結局発生して処理が遅くなるため、ある程度検索漏れを抑えつつ高速に検索できる図３の処理が適している。
【００４０】
以上のように、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みを行なうことで、次元数が高次元になった時でも演算量を抑えて、ユーザの望む画像を効率よく検索することができる。また、画像毎に、人物の特徴を強く表わす成分と平均的な成分に分離して次元を縮退することで、予め目/鼻/口等の重要度が高いと想定した成分のみを使用して次元を縮退する場合と比較して、重要度が高くないと想定した成分に特徴が大きく現れる人物の画像が登録されている場合でも、該当人物画像の検索を柔軟にかつ適切に行なうことができる。さらに、図４のような検索処理を導入する事により、近似空間上で検索結果を絞込む過程における検索漏れを０にすることができる。
【００４１】
なお、次元縮退方法として、成分値の並替えによって人物の特徴を強く表わす成分と平均的な成分に分離する方法について述べたが、Haar等に代表されるウェーブレット変換を用いて、低周波に相当する「平均的な成分」からＲ２データを生成し、高周波に相当する「平均との差分成分」からＲ１データを生成するようにしてもよい。この場合、Ｒ１/Ｒ２データを構成する要素番号が入力する多次元特徴データに依存せず固定されるため、近似空間検索手段１０５での演算量を削減できるという効果が得られる。また、多次元特徴データ間の差異が平均的な成分に強く出る場合には、前述のウェーブレット変換後の低周波に相当する「平均的な成分」をＲ１データ、高周波に相当する「平均との差分成分」をＲ２データに変更することで対応可能である。
【００４２】
（実施の形態２）
実施の形態２では、近似空間上で検索結果を絞込む過程で検索漏れが多く発生しても、ユーザが再検索による絞込み操作を簡単に行なうことができる画像検索装置について述べる。
【００４３】
本発明の実施の形態２で述べる構成は実施の形態１とほぼ同じであるため、ここでは、追加となる再検索時の絞込み操作の処理手順のみ記載し、他は省略する。
【００４４】
図６は、近似空間検索手段１０５で得られた検索結果が実空間最終ランク付け手段１０６の最終ランク付けでどの程度変更が生じたかを示す「次元縮退による歪み率」を結果表示し、ユーザが「次元縮退による歪み率」を参照しながら、近似空間検索手段１０５で「利用する次元数」と「絞込む件数」を再検索条件として設定する例を示したものである。６−ａは、検索対象者の検索キーと時刻/場所の検索範囲を最初に指定する初期検索条件指定画面、６−ｂは、「次元縮退による歪み率」も併せて検索結果を表示する検索結果表示画面、６−ｃは、3通りの再検索の方法[ 1)利用次元数(利用する次元数)の調整、２)近似範囲(絞込む件数)の調整、３)上記１）２）の調整は行なわずに次のＫ件を出力する]から次の検索条件をユーザが指定する再検索条件指定画面であり、６−ｂと６−ｃの操作は繰返し行なわれる。
【００４５】
図７を用いて、「次元縮退による歪み率」の算出例について述べる。７−ａは、図１に示すような構成で検索を行なった場合に生じる検索漏れ(データＬ、Ｇ)の例を表わしている。７−ｂは、検索漏れが起きた時の、近似空間検索手段１０５と実空間最終ランク付け手段１０６で得られた検索結果の違いを表わしている。７−ｂにおいて、近似空間での絞込みの閾値である上位Ｍ件のＭ値を大きくすれば検索漏れの確率は小さくなるが、ユーザがどの程度Ｍ値を大きくすれば良いのか判断がつかない。そこで、「次元縮退の歪み率」として、a)近似空間で得られる上位Ｋ件が最終順位付け上位Ｋ件に含まれる比率、或いは、b)最終順位付け上位Ｋ件のデータに対して、「最終順位の総和(すなわちK*(K+1)/2) ／近似空間での順位の総和」の順位比率、を用いることで、ユーザに次元縮退による歪みがどの程度発生しているのかを伝えることができる。なお、上記a)b)の値が小さいほど歪みは大きくなる。
【００４６】
次に、「次元縮退の歪み率」を参照してユーザが再検索条件を指定する操作について詳細に説明する。再検索条件の指定には、６−ｃに示したように、1)利用次元数の調整、2)近似範囲の調整、3)次のＫ件を出力する、の３パターン存在する。
【００４７】
１）の利用次元数とは、近似空間検索手段１０５で使用するＲ１データの要素数であり、Ｒ１データの要素数を増やすことで「次元縮退の歪み率」を小さくすることができる。なお、利用次元数の調整が行なわれた時に、近似空間検索手段１０５でＲ１データの要素数を変更して再検索処理ができるように、図８に示すような複数のカット次元(R#a,R#b,R#c)に対応したデータ構造を予め生成しておく。データ構造は、複数のカット次元毎に生成する必要はなく、８−ｂのように、Ｒ１データの要素数が大きいカット次元(R#c)にあわせて用意しておくことで対応可能である。
【００４８】
２）の近似範囲の調整は、近似空間で絞込む範囲(上位Ｍ件のＭ値)を調整するためのもので、「次元縮退の歪み率」が大きいときでも、Ｍ値を大きくする事で検索漏れを防ぐことができる。
【００４９】
３）の次のＫ件は、「次元縮退の歪み率が小さい」或いは「次元縮退の歪み率が大きいが、１)２)による調整が難しい」とユーザが判断した時に使用される。
【００５０】
以上のように、ユーザが「次元縮退による歪み率」を参照して、近似空間検索手段で「利用する次元数」と「絞込む件数」を調整していくことで、近似空間上で検索結果を絞込む過程における検索漏れを抑制した再検索操作を実現することができる。なお、再検索条件指定手段が、実空間最終ランク付け手段で出力した「次元縮退による歪み率」を参照して自動的に検索条件を再指定する構成としてもよい。この構成により、より効率的に画像を検索できる。
【００５１】
（実施の形態３）
実施の形態３では、近似空間上で検索結果を絞込む過程で検索漏れが多く発生しても、ユーザが再検索による絞込み操作を簡単に行なうことができる、実施の形態２とは別の画像検索装置について述べる。
【００５２】
本発明の実施の形態３で述べる構成は実施の形態１とほぼ同じであるため、ここでは、追加となる再検索時の絞込み操作の処理手順のみ記載し、他は省略する。
【００５３】
図９は、検索結果に対してユーザが正解または不正解を指定すると、近似空間検索手段１０５にて、正解と指定した近似データで使用している要素番号の重み付けを強く、また、誤りと指定した近似データで使用している要素番号の重み付けを弱くして、近似空間内での距離計算を再度行なう例を示したものである。９−ｂのように、人物の特徴を強く表わす要素番号は検索結果毎に異なるため、ユーザが正解/不正解と指定した結果から、正解を導出する要素番号と不正解を除去する要素番号をそれぞれ抽出して重み付けを行なうことで、検索漏れを抑制した再検索処理を実現する事ができる。なお、重み付けとは、図３の３−ｃの各次元の距離計算において、距離計算結果に重み係数を付与することである。
【００５４】
また、図１０は、検索結果に対してユーザが不正解と指定すると、不正解と指定したデータが実空間最終ランク付け手段１０６で出力されないように、近似空間検索手段１０５で「利用する次元数」と「絞込む件数」を自動調整する例を示したものである。１０―ｂにおいて、ユーザが「データＨ／Ｅ＝不正解」と指定した場合は、最終順位付けでデータＨ／Ｅより距離の小さい要素が出てくるまで、近似空間での絞込みの閾値である上位Ｍ件のＭ値を大きく、或いは利用する次元数を増やして処理を行なう。
【００５５】
以上のように、検索結果に対して、画像毎に、ユーザが正解/不正解を指定して、再検索時の近似距離計算パラメータ(要素番号の重み、利用次元数、近似範囲)を自動調整していくことで、近似空間上で検索結果を絞込む過程における検索漏れを抑制した再検索操作を実現することができる。
【００５６】
以上のように、本発明の各実施形態にかかる画像検索装置および画像検索方法は、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みを行なうことで、次元数が高次元になった時でも演算量を抑えて、ユーザの望む画像を効率よく適切に検索することができるという効果を有し、複数カメラを対象にした万引き犯・迷子・落し物者の全行動把握を行なう監視用途に加えて、旅行・運動会等の個人で撮影したコンテンツ（静止画・動画）に対する閲覧・検索・編集の用途等にも応用することができる。
【産業上の利用可能性】
【００５７】
本発明は、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みができるため、次元数が高次元になった時でもユーザの望む画像を効率よく検索することができるという効果を有し、画像から抽出した多次元特徴データ(顔,色等)を用いて、大容量の画像群から所望の画像を高速に洗出すことのできる画像検索装置および画像検索方法等に有用である。
【図面の簡単な説明】
【００５８】
【図１】本発明の第１の実施の形態における画像検索装置のブロック図
【図２】本発明の第１の実施の形態における画像検索装置のデータ登録動作に関するフロー図
【図３】本発明の第１の実施の形態における画像検索装置の検索動作に関するフロー図
【図４】本発明の第１の実施の形態における画像検索装置の検索漏れをなくす検索動作に関するフロー図
【図５】本発明の第１の実施の形態における画像検索装置の２種類の検索処理の違いに関する説明図
【図６】本発明の第２の実施の形態における画像検索装置の再検索操作に関するフロー図
【図７】本発明の第２の実施の形態における画像検索装置の歪み率算出に関する説明図
【図８】本発明の第２の実施の形態における画像検索装置で管理するデータ構造に関する説明図
【図９】本発明の第３の実施の形態における画像検索装置の再検索操作に関するフロー図（その１）
【図１０】本発明の第３の実施の形態における画像検索装置の再検索操作１に関するフロー図（その２）
【符号の説明】
【００５９】
１１ カメラ
１２ 検索サーバ
１３ 検索端末
１０１ 多次元特徴データ生成手段
１０２ 次元縮退手段
１０３ 近似データ蓄積手段
１０３ａ 近似特徴データ群
１０３ｂ 実特徴データ群
１０４ 検索要求受信手段
１０５ 近似空間検索手段
１０６ 実空間最終ランク付け手段
【技術分野】
【０００１】
本発明は、画像から抽出した多次元特徴データ(顔,色等)を用いて、大容量の画像群から所望の画像を高速に洗出すことのできる画像検索装置および画像検索方法に関するものである。
【背景技術】
【０００２】
近年、ピッキング・強盗・放火等に代表される犯罪の増加と共に、カメラ・センサ・蓄積装置等を設置し、犯罪を未然に防止する映像監視システムの普及が大幅に進んでいる。また、監視カメラのＩＰ化・蓄積装置の大容量化に伴い、数百規模の広域監視・長時間記録を行なうシステムも増加してきた。このような状況において、監視者の業務軽減を目指し、万引き犯・迷子者・落し物者等の特定人物の洗出しを効率的に行なうための技術が要望されてきている。
【０００３】
特定人物の洗出しを高速に行なう従来技術として、画像から抽出した多次元特徴データ群(色,顔等)を予め距離の近い順にクラスタリングして木構造にしておき、検索時には検索対象人物に最も近い部分木のみ検索する手法がある。また、特許文献１には、統計的手法により用意したモデル空間に射影して、高精度で次元数の少ない多次元特徴データを生成することで高速検索する方法が記載されている。
【特許文献１】特開２００２−１８３２０５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の木構造にする方法では、多次元特徴データの次元数が多くなると、隣接空間が指数関数的に増え、多次元特徴データをクラスタリング(登録)するのに膨大な時間を要する。さらに、検索時には、隣接空間も含め近傍検索を行なうため、登録同様、膨大な時間を要する。
また、特許文献１に記載の技術においては、射影による次元縮退には限度がある。また、その対策として、目/鼻/口等の重要度の高い部分のみを使用して類似度計算をする方法も記載されているが、個人の特徴がどこに現れるのかは千差万別で、精度を維持したまま次元を縮退するには限界がある。
【０００５】
本発明は、前記従来の事情に鑑みてなされたもので、顔/色等の多次元特徴データが高次元で大量に存在する場合でも、ユーザの望む画像を効率よく適切に検索可能な画像検索装置および画像検索方法を実現することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の画像検索装置は、画像から抽出した多次元特徴データの次元を縮退して近似データを生成する次元縮退手段と、前記次元縮退手段で生成した近似データを次元縮退前の多次元特徴データと対応付けて蓄積する近似データ蓄積手段と、少なくとも、検索対象人物の多次元特徴データを識別する識別子を検索キーとして受信する検索要求受信手段と、検索条件に基づいて、前記検索要求受信手段で受信した検索キーに対応する近似データと前記近似データ蓄積手段で蓄積した複数の近似データのそれぞれとの距離計算を行ない類似度順に並べる近似空間検索手段と、前記近似空間検索手段で得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定し、検索結果として出力する実空間最終ランク付け手段とを備える。
【０００７】
この構成により、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みができるため、次元数が高次元になった時でもユーザの望む画像を効率よく検索することができる。また、検索結果を類似度順で出力するため、より効率よく検索することができる。
【０００８】
また、本発明の画像検索装置は、前記次元縮退手段が、前記多次元特徴データを構成する要素を絶対値の大きい順に並替え、上位Ｎ個（Ｎ：自然数）の(要素番号,値)を前記近似データとして生成することを特徴とする。また、本発明の画像検索装置は、前記次元縮退手段が、入力する多次元特徴データのウェーブレット変換結果から、高周波成分又は低周波成分の上位Ｎ個の値を前記近似データとして生成することを特徴とする。また、本発明の画像検索装置は、前記次元縮退手段で得られた上位Ｎ個以外の多次元特徴データを(代表値,符号ビット)として生成し前記近似データとして管理することを特徴とする。
【０００９】
この構成により、人物の特徴を強く表わす部分の影響が強く出るように次元を縮退することができるため、近似空間上で検索結果を絞込む過程における検索漏れを少なくすることができる。
【００１０】
また、本発明の画像検索装置は、前記実空間最終ランク付け手段が、前記近似空間検索手段で得られた類似度の高い上位Ｍ件（Ｍ：自然数）に対して最終順位付けを行ない、検索結果として上位Ｋ件(Ｋ<Ｍ)を出力することを特徴とする。
【００１１】
この構成により、近似空間上で検索結果を絞込む過程における検索漏れを抑制することができる。
【００１２】
また、本発明の画像検索装置は、前記実空間最終ランク付け手段が、前記近似空間検索手段で得られた類似度の高い要素(すなわち近似距離の小さい要素)から順に、次元縮退前の多次元特徴データを用いて再距離計算を行ない、再距離計算して得られた類似度の高い上位Ｋ件の実距離が、再距離計算を行なっていない全データの近似距離より小さくなった時点で処理を完了し、前記上位Ｋ件を検索結果として出力することを特徴とする。
【００１３】
この構成により、全ての次元を用いて距離計算を行なう場合と同じ結果を得ることができるため、近似空間上で検索結果を絞込む過程における検索漏れを０にすることができる。
【００１４】
また、本発明の画像検索装置は、前記実空間最終ランク付け手段が、前記近似空間検索手段で得られた結果が、最終ランク付けでどの程度変更したかを示す「次元縮退による歪み率」を結果として出力することを特徴とする。
【００１５】
この構成により、ユーザは、近似空間上で検索結果を絞込む過程で検索漏れがどの程度発生したかを把握することができるため、効率的に画像を再検索することができる。
【００１６】
また、本発明の画像検索装置は、「利用する次元数」と「絞込む件数」を、前記近似空間検索手段が用いる検索条件として指定する再検索条件指定手段を備えることを特徴とする。
【００１７】
この構成により、近似空間上で検索結果を絞込む過程で検索漏れが発生した場合であっても、ユーザが再検索による絞込み操作を簡単に行なうことができる。また、再検索条件指定手段が、実空間最終ランク付け手段で出力した「次元縮退による歪み率」を参照して自動的に検索条件を再指定する構成をとれば、より効率的に画像を検索できる。
【００１８】
また、本発明の画像検索装置は、前記実空間最終ランク付け手段で出力した検索結果に対して正解または不正解を指定する正誤指定手段を備えたことを特徴とする。また、本発明の画像検索装置は、前記近似空間検索手段が、前記正誤指定手段で正解と指定した近似データの要素番号を「正解要素番号群」として、また、不正解と指定した近似データの要素番号を「誤り要素番号群」として設定し、近似データを用いた距離計算過程で、「正解要素番号群」に含まれる各要素番号の重み付けを強く、「誤り要素番号群」に含まれる各要素番号の重み付けを弱くすることを特徴とする。
【００１９】
この構成により、近似空間上で検索結果を絞込む過程で検索漏れが多く発生しても、ユーザが再検索による絞込み操作を簡単に行なうことができる。
【００２０】
さらに、本発明の画像検索方法は、画像から抽出した多次元特徴データの次元を縮退して生成した近似データを用いて、画像蓄積手段に蓄積されている画像群を検索対象画像との類似度順に並べる近似空間検索ステップと、前記近似空間検索ステップで得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再類似度計算を行ない最終順位を決定する実空間最終ランク付けステップとを有する。
【発明の効果】
【００２１】
本発明によれば、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みができるため、次元数が高次元になった時でもユーザの望む画像を効率よく検索することができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００２３】
（実施の形態１）
図１は、本発明の実施の形態１における画像検索装置の構成図である。図１において、１１は、人物を撮影するカメラ、１２は、指定された検索条件に該当する人物を含む画像を検索する検索サーバ、１３は、検索サーバ１２に対して検索条件を指定して検索を実行させるための検索端末である。１０１は、カメラ１１で撮影した画像から、顔/色/形状などの人物を識別するための多次元特徴データを抽出する多次元特徴データ生成手段、１０２は、多次元特徴データ生成手段１０１で抽出した多次元特徴データの次元を縮退して近似データを生成する次元縮退手段、１０３は、次元縮退手段１０２で生成した近似データと次元縮退前の多次元特徴データと対応付けて、それぞれ近似特徴データ群１０３ａと実特徴データ群１０３ｂとして蓄積する近似データ蓄積手段、１０４は、少なくとも、検索対象人物の多次元特徴データを識別する識別子を検索キーとして受信する検索要求受信手段、１０５は、検索端末１３で指定された検索条件に基づいて、検索要求受信手段１０４で受信した検索キーに対応する近似データと近似データ蓄積手段１０３で蓄積した複数の近似データのそれぞれとの距離計算を行ない、計算結果の距離順すなわち類似度順に並べる近似空間検索手段、１０６は、近似空間検索手段１０５で得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定する実空間最終ランク付け手段である。実空間最終ランク付け手段１０６で決定された最終順位は、検索結果として出力される。
【００２４】
多次元特徴データ生成手段１０１で抽出する人物特徴データは、画像から切出した移動体の画像データであり、或いは、形状・色・大きさ、動きなどにより移動体を特定する情報であり、或いは、顔の目・鼻・口の形状や位置などを特定する情報である。これらの特徴情報の抽出分類方法は広く知られており、例えば、特開2001-268657号公報、及び、「画像の処理と認識」(安居院猛・長尾智晴 共著、昭晃堂出版)に厳密に記されている。これらの既存技術を利用して生成した顔/服装色等の人物特徴データは、人物を特定するために複数の要素(次元と呼ぶ)から構成されている。例えば、顔特徴データは、全体の顔つきを把握するための要素群、目/鼻/口等の特定部品の形状を把握するための要素群の合計：数百〜数千次元から構成される。
【００２５】
図２は、次元縮退手段１０２の処理手順を示したもので、以下その動作について説明する。
【００２６】
＜ステップ２０１＞入力された多次元特徴データ([要素番号,値]の系列)に対して、値を全て絶対値にして、値の大きいものから順にソートする。入力される多次元特徴データは、２−ａのように、顔全体/部品単位の主成分を持つ顔特徴データや、人物の服装の色分布をRGB/HSV等の色空間ヒストグラムとして表わしたデータや、さらに、人物が写っている領域を切出して周波数に変換したデータなどで、横軸の各要素の[要素番号,値]の集合が、ステップ２０１の多次元特徴データの入力として与えられる。また、ソート後は２−ｂのように絶対値が大きいものから順に並べられ、横軸の各要素は、[ソート前の要素番号、値]として生成される。
【００２７】
＜ステップ２０２＞指定された次元(Ｒ)で、多次元特徴データを分離（次元をカット）する。分離後、指定次元Ｒ以内の要素(絶対値の大きい要素)は、Ｒ１データとして[ソート前の要素番号,値]の系列として出力され、また、指定次元Rより大きい部分は、Ｒ２データとして、[代表値Ｖ,Ｒ２内の符号ビット列]として生成される（２−ｃ）。なお、Ｒ２データの代表値Ｖは、Ｒ２データの絶対値での平均値、或いは、Ｒ２データの絶対値の最大値が用いられる。また、符号ビット列は、Ｒ２のＮ番目の要素の値が正ならビット値＝１、負ならビット値＝０として、Ｒ２の要素数分の符号が分かるビット列として生成される。
【００２８】
＜ステップ２０３＞ステップ２０２で生成したＲ１及びＲ２データを近似データ蓄積手段１０３の近似特徴データ群103aへ格納する。また、ステップ２０１で入力されたソート前ベクトルデータを実特徴データ群103bへ格納する。このようにしてインデクスを生成する。なお、近似特徴データ群103aは、次元を縮退したデータ群であるため、高速アクセス可能なメモリ上に配置するようにしてもよい。
【００２９】
図３は、近似空間検索手段１０５及び実空間最終ランク付け手段１０６の処理手順を示したもので、以下その動作について説明する。
【００３０】
＜ステップ３０１＞検索要求受信手段１０４で受信した検索キーに対応する近似データ(３−ａ)と近似データ蓄積手段１０３で蓄積した複数の近似データ（３−ｂ）との近似距離計算を行ない、近似データ蓄積手段１０３で蓄積した複数の近似データを近似距離の小さい順に並べる。近似距離計算は、３−ｃに示すように、ソート前の全ての次元に対して、
1) 各次元が、(3-a),(3-b)のR1に含まれれば、R1にある値を用いて距離計算を行なう。
2) 各次元が、(3-a),(3-b)のR2に片方含まれれば、R2に含まれるものに対しては、R2の代表値(V)と符号ビットから近似値を算出し、それを用いて距離計算を行なう。
といった処理を行なう。
【００３１】
＜ステップ３０２＞ステップ３０１で距離の小さい順に並べた上位Ｍ件に対して、検索要求受信手段１０４で受信した検索キーとの実距離計算を行ない、３−ｄのように実距離の小さい順に上位Ｋ件を抽出し結果として返す。実距離は、実特徴データ群103bに格納したソート前ベクトルデータから計算する。
【００３２】
図３の処理は、近似距離の小さい順に並べた上位Ｍ件に対して、実空間上で最終順位付けを行なうものだが、上位Ｍ件に絞込んだ時点で検索漏れを起こす可能性がある。図４は、近似空間上での絞込みによる検索漏れを０にするための実空間最終ランク付け手段１０８の処理手順を示したもので、以下その動作について説明する。
【００３３】
＜ステップ４０１＞近似空間検索手段１０５で生成した、検索キーとの近似距離のリストを取得する。リストは、近似距離の小さいものから順に格納されているものとする。
【００３４】
＜ステップ４０２＞近似距離リストから、近似距離の小さいデータを取得する。取得した時点で、近似距離リストから該当データを削除する。
【００３５】
＜ステップ４０３＞ステップ４０２で取得したデータと検索キーに対応するデータとの実距離を計算する。
【００３６】
＜ステップ４０４＞ステップ４０２で取得したデータを実距離リストへ追加する。リストは、実距離の小さいものから順に格納されるようにする。
【００３７】
＜ステップ４０５＞実距離リストの上位Ｋ件の全ての距離が、近似距離リスト内の最小距離より小さいか判定する。Ｙｅｓの場合、ステップ４０６へ、Ｎｏの場合、ステップ４０２へ移行する。
【００３８】
＜ステップ４０６＞実距離リストの上位Ｋ件を実空間最終ランク付け手段１０６の検索結果として出力する。
【００３９】
図５を用いて、図３と図４の処理手順による検索結果の違いについて述べる。５−ａは、検索キーとデータＡ〜Ｈとの「近似距離及び実距離」の例を示したものである。５−ａに対して、図３のフローで検索した場合、５−ｂに示すようにデータＧが検索漏れを起こしてしまう。これに対し、図４のフローで検索した場合は５−ｃに示すようにデータＧの検索漏れを起こすことはない。図３と図４のどちらの検索処理を採用するかは、近似距離と実距離の関係により異なる。例えば、全てのデータに対して「近似距離≒実距離」となる場合は、近似によって検索順位が大きく入替わる可能性がないため、検索漏れを防ぎつつ高速処理が可能な図４が適している。一方、「近似距離<<実距離」となる場合は、図４の処理では全データに対する検索が結局発生して処理が遅くなるため、ある程度検索漏れを抑えつつ高速に検索できる図３の処理が適している。
【００４０】
以上のように、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みを行なうことで、次元数が高次元になった時でも演算量を抑えて、ユーザの望む画像を効率よく検索することができる。また、画像毎に、人物の特徴を強く表わす成分と平均的な成分に分離して次元を縮退することで、予め目/鼻/口等の重要度が高いと想定した成分のみを使用して次元を縮退する場合と比較して、重要度が高くないと想定した成分に特徴が大きく現れる人物の画像が登録されている場合でも、該当人物画像の検索を柔軟にかつ適切に行なうことができる。さらに、図４のような検索処理を導入する事により、近似空間上で検索結果を絞込む過程における検索漏れを０にすることができる。
【００４１】
なお、次元縮退方法として、成分値の並替えによって人物の特徴を強く表わす成分と平均的な成分に分離する方法について述べたが、Haar等に代表されるウェーブレット変換を用いて、低周波に相当する「平均的な成分」からＲ２データを生成し、高周波に相当する「平均との差分成分」からＲ１データを生成するようにしてもよい。この場合、Ｒ１/Ｒ２データを構成する要素番号が入力する多次元特徴データに依存せず固定されるため、近似空間検索手段１０５での演算量を削減できるという効果が得られる。また、多次元特徴データ間の差異が平均的な成分に強く出る場合には、前述のウェーブレット変換後の低周波に相当する「平均的な成分」をＲ１データ、高周波に相当する「平均との差分成分」をＲ２データに変更することで対応可能である。
【００４２】
（実施の形態２）
実施の形態２では、近似空間上で検索結果を絞込む過程で検索漏れが多く発生しても、ユーザが再検索による絞込み操作を簡単に行なうことができる画像検索装置について述べる。
【００４３】
本発明の実施の形態２で述べる構成は実施の形態１とほぼ同じであるため、ここでは、追加となる再検索時の絞込み操作の処理手順のみ記載し、他は省略する。
【００４４】
図６は、近似空間検索手段１０５で得られた検索結果が実空間最終ランク付け手段１０６の最終ランク付けでどの程度変更が生じたかを示す「次元縮退による歪み率」を結果表示し、ユーザが「次元縮退による歪み率」を参照しながら、近似空間検索手段１０５で「利用する次元数」と「絞込む件数」を再検索条件として設定する例を示したものである。６−ａは、検索対象者の検索キーと時刻/場所の検索範囲を最初に指定する初期検索条件指定画面、６−ｂは、「次元縮退による歪み率」も併せて検索結果を表示する検索結果表示画面、６−ｃは、3通りの再検索の方法[ 1)利用次元数(利用する次元数)の調整、２)近似範囲(絞込む件数)の調整、３)上記１）２）の調整は行なわずに次のＫ件を出力する]から次の検索条件をユーザが指定する再検索条件指定画面であり、６−ｂと６−ｃの操作は繰返し行なわれる。
【００４５】
図７を用いて、「次元縮退による歪み率」の算出例について述べる。７−ａは、図１に示すような構成で検索を行なった場合に生じる検索漏れ(データＬ、Ｇ)の例を表わしている。７−ｂは、検索漏れが起きた時の、近似空間検索手段１０５と実空間最終ランク付け手段１０６で得られた検索結果の違いを表わしている。７−ｂにおいて、近似空間での絞込みの閾値である上位Ｍ件のＭ値を大きくすれば検索漏れの確率は小さくなるが、ユーザがどの程度Ｍ値を大きくすれば良いのか判断がつかない。そこで、「次元縮退の歪み率」として、a)近似空間で得られる上位Ｋ件が最終順位付け上位Ｋ件に含まれる比率、或いは、b)最終順位付け上位Ｋ件のデータに対して、「最終順位の総和(すなわちK*(K+1)/2) ／近似空間での順位の総和」の順位比率、を用いることで、ユーザに次元縮退による歪みがどの程度発生しているのかを伝えることができる。なお、上記a)b)の値が小さいほど歪みは大きくなる。
【００４６】
次に、「次元縮退の歪み率」を参照してユーザが再検索条件を指定する操作について詳細に説明する。再検索条件の指定には、６−ｃに示したように、1)利用次元数の調整、2)近似範囲の調整、3)次のＫ件を出力する、の３パターン存在する。
【００４７】
１）の利用次元数とは、近似空間検索手段１０５で使用するＲ１データの要素数であり、Ｒ１データの要素数を増やすことで「次元縮退の歪み率」を小さくすることができる。なお、利用次元数の調整が行なわれた時に、近似空間検索手段１０５でＲ１データの要素数を変更して再検索処理ができるように、図８に示すような複数のカット次元(R#a,R#b,R#c)に対応したデータ構造を予め生成しておく。データ構造は、複数のカット次元毎に生成する必要はなく、８−ｂのように、Ｒ１データの要素数が大きいカット次元(R#c)にあわせて用意しておくことで対応可能である。
【００４８】
２）の近似範囲の調整は、近似空間で絞込む範囲(上位Ｍ件のＭ値)を調整するためのもので、「次元縮退の歪み率」が大きいときでも、Ｍ値を大きくする事で検索漏れを防ぐことができる。
【００４９】
３）の次のＫ件は、「次元縮退の歪み率が小さい」或いは「次元縮退の歪み率が大きいが、１)２)による調整が難しい」とユーザが判断した時に使用される。
【００５０】
以上のように、ユーザが「次元縮退による歪み率」を参照して、近似空間検索手段で「利用する次元数」と「絞込む件数」を調整していくことで、近似空間上で検索結果を絞込む過程における検索漏れを抑制した再検索操作を実現することができる。なお、再検索条件指定手段が、実空間最終ランク付け手段で出力した「次元縮退による歪み率」を参照して自動的に検索条件を再指定する構成としてもよい。この構成により、より効率的に画像を検索できる。
【００５１】
（実施の形態３）
実施の形態３では、近似空間上で検索結果を絞込む過程で検索漏れが多く発生しても、ユーザが再検索による絞込み操作を簡単に行なうことができる、実施の形態２とは別の画像検索装置について述べる。
【００５２】
本発明の実施の形態３で述べる構成は実施の形態１とほぼ同じであるため、ここでは、追加となる再検索時の絞込み操作の処理手順のみ記載し、他は省略する。
【００５３】
図９は、検索結果に対してユーザが正解または不正解を指定すると、近似空間検索手段１０５にて、正解と指定した近似データで使用している要素番号の重み付けを強く、また、誤りと指定した近似データで使用している要素番号の重み付けを弱くして、近似空間内での距離計算を再度行なう例を示したものである。９−ｂのように、人物の特徴を強く表わす要素番号は検索結果毎に異なるため、ユーザが正解/不正解と指定した結果から、正解を導出する要素番号と不正解を除去する要素番号をそれぞれ抽出して重み付けを行なうことで、検索漏れを抑制した再検索処理を実現する事ができる。なお、重み付けとは、図３の３−ｃの各次元の距離計算において、距離計算結果に重み係数を付与することである。
【００５４】
また、図１０は、検索結果に対してユーザが不正解と指定すると、不正解と指定したデータが実空間最終ランク付け手段１０６で出力されないように、近似空間検索手段１０５で「利用する次元数」と「絞込む件数」を自動調整する例を示したものである。１０―ｂにおいて、ユーザが「データＨ／Ｅ＝不正解」と指定した場合は、最終順位付けでデータＨ／Ｅより距離の小さい要素が出てくるまで、近似空間での絞込みの閾値である上位Ｍ件のＭ値を大きく、或いは利用する次元数を増やして処理を行なう。
【００５５】
以上のように、検索結果に対して、画像毎に、ユーザが正解/不正解を指定して、再検索時の近似距離計算パラメータ(要素番号の重み、利用次元数、近似範囲)を自動調整していくことで、近似空間上で検索結果を絞込む過程における検索漏れを抑制した再検索操作を実現することができる。
【００５６】
以上のように、本発明の各実施形態にかかる画像検索装置および画像検索方法は、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みを行なうことで、次元数が高次元になった時でも演算量を抑えて、ユーザの望む画像を効率よく適切に検索することができるという効果を有し、複数カメラを対象にした万引き犯・迷子・落し物者の全行動把握を行なう監視用途に加えて、旅行・運動会等の個人で撮影したコンテンツ（静止画・動画）に対する閲覧・検索・編集の用途等にも応用することができる。
【産業上の利用可能性】
【００５７】
本発明は、次元数を抑えた近似空間上で検索結果をある程度絞込んだ後、実空間で最終絞込みができるため、次元数が高次元になった時でもユーザの望む画像を効率よく検索することができるという効果を有し、画像から抽出した多次元特徴データ(顔,色等)を用いて、大容量の画像群から所望の画像を高速に洗出すことのできる画像検索装置および画像検索方法等に有用である。
【図面の簡単な説明】
【００５８】
【図１】本発明の第１の実施の形態における画像検索装置のブロック図
【図２】本発明の第１の実施の形態における画像検索装置のデータ登録動作に関するフロー図
【図３】本発明の第１の実施の形態における画像検索装置の検索動作に関するフロー図
【図４】本発明の第１の実施の形態における画像検索装置の検索漏れをなくす検索動作に関するフロー図
【図５】本発明の第１の実施の形態における画像検索装置の２種類の検索処理の違いに関する説明図
【図６】本発明の第２の実施の形態における画像検索装置の再検索操作に関するフロー図
【図７】本発明の第２の実施の形態における画像検索装置の歪み率算出に関する説明図
【図８】本発明の第２の実施の形態における画像検索装置で管理するデータ構造に関する説明図
【図９】本発明の第３の実施の形態における画像検索装置の再検索操作に関するフロー図（その１）
【図１０】本発明の第３の実施の形態における画像検索装置の再検索操作１に関するフロー図（その２）
【符号の説明】
【００５９】
１１ カメラ
１２ 検索サーバ
１３ 検索端末
１０１ 多次元特徴データ生成手段
１０２ 次元縮退手段
１０３ 近似データ蓄積手段
１０３ａ 近似特徴データ群
１０３ｂ 実特徴データ群
１０４ 検索要求受信手段
１０５ 近似空間検索手段
１０６ 実空間最終ランク付け手段
【特許請求の範囲】
【請求項１】
画像から抽出した多次元特徴データの次元を縮退して近似データを生成する次元縮退手段と、
前記次元縮退手段で生成した近似データを次元縮退前の多次元特徴データと対応付けて蓄積する近似データ蓄積手段と、
少なくとも、検索対象人物の多次元特徴データを識別する識別子を検索キーとして受信する検索要求受信手段と、
検索条件に基づいて、前記検索要求受信手段で受信した検索キーに対応する近似データと前記近似データ蓄積手段で蓄積した複数の近似データのそれぞれとの距離計算を行ない類似度順に並べる近似空間検索手段と、
前記近似空間検索手段で得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定し、検索結果として出力する実空間最終ランク付け手段とを備えた画像検索装置。
【請求項２】
前記次元縮退手段は、前記多次元特徴データを構成する要素を絶対値の大きい順に並替え、上位Ｎ個（Ｎ：自然数）の(要素番号,値)を前記近似データとして生成することを特徴とする請求項１記載の画像検索装置。
【請求項３】
前記次元縮退手段は、入力する多次元特徴データのウェーブレット変換結果から、高周波成分又は低周波成分の上位Ｎ個の値を前記近似データとして生成することを特徴とする請求項１記載の画像検索装置。
【請求項４】
前記次元縮退手段で得られた上位Ｎ個以外の多次元特徴データを(代表値,符号ビット)として生成し前記近似データとして管理することを特徴とする請求項２または３記載の画像検索装置。
【請求項５】
前記実空間最終ランク付け手段は、前記近似空間検索手段で得られた類似度の高い上位Ｍ件（Ｍ：自然数）に対して最終順位付けを行ない、検索結果として上位Ｋ件(Ｋ<Ｍ)を出力することを特徴とする請求項１記載の画像検索装置。
【請求項６】
前記実空間最終ランク付け手段は、前記近似空間検索手段で得られた類似度の高い要素(すなわち近似距離の小さい要素)から順に、次元縮退前の多次元特徴データを用いて再距離計算を行ない、再距離計算して得られた類似度の高い上位Ｋ件の実距離が、再距離計算を行なっていない全データの近似距離より小さくなった時点で処理を完了し、前記上位Ｋ件を検索結果として出力することを特徴とする請求項１記載の画像検索装置。
【請求項７】
前記実空間最終ランク付け手段は、前記近似空間検索手段で得られた結果が、最終ランク付けでどの程度変更したかを示す「次元縮退による歪み率」を結果として出力することを特徴とする請求項１記載の画像検索装置。
【請求項８】
「利用する次元数」と「絞込む件数」を、前記近似空間検索手段が用いる検索条件として指定する再検索条件指定手段を備えることを特徴とする請求項７記載の画像検索装置。
【請求項９】
前記実空間最終ランク付け手段で出力した検索結果に対して正解または不正解を指定する正誤指定手段を備えたことを特徴とする請求項１記載の画像検索装置。
【請求項１０】
前記近似空間検索手段は、前記正誤指定手段で正解と指定した近似データの要素番号を「正解要素番号群」として、また、不正解と指定した近似データの要素番号を「誤り要素番号群」として設定し、近似データを用いた距離計算過程で、「正解要素番号群」に含まれる各要素番号の重み付けを強く、「誤り要素番号群」に含まれる各要素番号の重み付けを弱くすることを特徴とする請求項９記載の画像検索装置。
【請求項１１】
前記近似空間検索手段は、前記正誤指定手段で不正解と指定した近似データが前記実空間最終ランク付け手段で再出力されないように、前記検索条件である「利用する次元数」と「絞込む件数」を自動調整することを特徴とする請求項９記載の画像検索装置。
【請求項１２】
画像から抽出した多次元特徴データの次元を縮退して生成した近似データを用いて、画像蓄積手段に蓄積されている画像群を検索対象画像との類似度順に並べる近似空間検索ステップと、
前記近似空間検索ステップで得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再類似度計算を行ない最終順位を決定する実空間最終ランク付けステップとを有する画像検索方法。
【請求項１３】
前記多次元特徴データを構成する要素を絶対値の大きい順に並替え、上位Ｎ個（Ｎ：自然数）の(要素番号,値)を前記近似データとして生成することを特徴とする請求項１２記載の画像検索方法。
【請求項１４】
入力する多次元特徴データのウェーブレット変換結果から、高周波成分又は低周波成分の上位Ｎ個の値を前記近似データとして生成することを特徴とする請求項１２記載の画像検索方法。
【請求項１５】
前記近似データとして生成された上位Ｎ個以外の多次元特徴データを(代表値,符号ビット)として生成し前記近似データとして管理することを特徴とする請求項１３または１４記載の画像検索方法。
【請求項１６】
前記実空間最終ランク付けステップは、前記近似空間検索ステップで得られた類似度の高い上位Ｍ件（Ｍ：自然数）に対して最終順位付けを行ない、検索結果として上位Ｋ件(Ｋ<Ｍ)を出力することを特徴とする請求項１２記載の画像検索方法。
【請求項１７】
前記実空間最終ランク付けステップは、前記近似空間検索ステップで得られた類似度の高い要素(すなわち近似距離の小さい要素)から順に、次元縮退前の多次元特徴データを用いて再類似度計算を行ない、再類似度計算して得られた類似度の高い上位Ｋ件の実距離が、再類似度計算を行なっていない全データの近似距離より小さくなった時点で処理を完了し、前記上位Ｋ件を検索結果として出力することを特徴とする請求項１２記載の画像検索方法。
【請求項１８】
前記実空間最終ランク付けステップは、前記近似空間検索ステップで得られた結果が、最終ランク付けでどの程度変更したかを示す「次元縮退による歪み率」を結果として出力することを特徴とする請求項１２記載の画像検索方法。
【請求項１９】
「利用する次元数」と「絞込む件数」を、前記近似空間検索ステップで用いる検索条件として指定する再検索条件指定ステップを有することを特徴とする請求項１８記載の画像検索方法。
【請求項２０】
前記実空間最終ランク付けステップで出力した検索結果に対して正解または不正解を指定する正誤指定ステップを有することを特徴とする請求項１２記載の画像検索方法。
【請求項２１】
前記近似空間検索ステップは、前記正誤指定ステップで正解と指定した近似データの要素番号を「正解要素番号群」として、また、不正解と指定した近似データの要素番号を「誤り要素番号群」として設定し、近似データを用いた類似度計算過程で、「正解要素番号群」に含まれる各要素番号の重み付けを強く、「誤り要素番号群」に含まれる各要素番号の重み付けを弱くすることを特徴とする請求項２０記載の画像検索方法。
【請求項２２】
前記近似空間検索ステップは、前記正誤指定ステップで不正解と選択した近似データが前記実空間最終ランク付けステップで再出力されないように、前記検索条件である「利用する次元数」と「絞込む件数」を自動調整することを特徴とする請求項２０記載の画像検索方法。
【請求項１】
画像から抽出した多次元特徴データの次元を縮退して近似データを生成する次元縮退手段と、
前記次元縮退手段で生成した近似データを次元縮退前の多次元特徴データと対応付けて蓄積する近似データ蓄積手段と、
少なくとも、検索対象人物の多次元特徴データを識別する識別子を検索キーとして受信する検索要求受信手段と、
検索条件に基づいて、前記検索要求受信手段で受信した検索キーに対応する近似データと前記近似データ蓄積手段で蓄積した複数の近似データのそれぞれとの距離計算を行ない類似度順に並べる近似空間検索手段と、
前記近似空間検索手段で得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再度距離計算を行ない最終順位を決定し、検索結果として出力する実空間最終ランク付け手段とを備えた画像検索装置。
【請求項２】
前記次元縮退手段は、前記多次元特徴データを構成する要素を絶対値の大きい順に並替え、上位Ｎ個（Ｎ：自然数）の(要素番号,値)を前記近似データとして生成することを特徴とする請求項１記載の画像検索装置。
【請求項３】
前記次元縮退手段は、入力する多次元特徴データのウェーブレット変換結果から、高周波成分又は低周波成分の上位Ｎ個の値を前記近似データとして生成することを特徴とする請求項１記載の画像検索装置。
【請求項４】
前記次元縮退手段で得られた上位Ｎ個以外の多次元特徴データを(代表値,符号ビット)として生成し前記近似データとして管理することを特徴とする請求項２または３記載の画像検索装置。
【請求項５】
前記実空間最終ランク付け手段は、前記近似空間検索手段で得られた類似度の高い上位Ｍ件（Ｍ：自然数）に対して最終順位付けを行ない、検索結果として上位Ｋ件(Ｋ<Ｍ)を出力することを特徴とする請求項１記載の画像検索装置。
【請求項６】
前記実空間最終ランク付け手段は、前記近似空間検索手段で得られた類似度の高い要素(すなわち近似距離の小さい要素)から順に、次元縮退前の多次元特徴データを用いて再距離計算を行ない、再距離計算して得られた類似度の高い上位Ｋ件の実距離が、再距離計算を行なっていない全データの近似距離より小さくなった時点で処理を完了し、前記上位Ｋ件を検索結果として出力することを特徴とする請求項１記載の画像検索装置。
【請求項７】
前記実空間最終ランク付け手段は、前記近似空間検索手段で得られた結果が、最終ランク付けでどの程度変更したかを示す「次元縮退による歪み率」を結果として出力することを特徴とする請求項１記載の画像検索装置。
【請求項８】
「利用する次元数」と「絞込む件数」を、前記近似空間検索手段が用いる検索条件として指定する再検索条件指定手段を備えることを特徴とする請求項７記載の画像検索装置。
【請求項９】
前記実空間最終ランク付け手段で出力した検索結果に対して正解または不正解を指定する正誤指定手段を備えたことを特徴とする請求項１記載の画像検索装置。
【請求項１０】
前記近似空間検索手段は、前記正誤指定手段で正解と指定した近似データの要素番号を「正解要素番号群」として、また、不正解と指定した近似データの要素番号を「誤り要素番号群」として設定し、近似データを用いた距離計算過程で、「正解要素番号群」に含まれる各要素番号の重み付けを強く、「誤り要素番号群」に含まれる各要素番号の重み付けを弱くすることを特徴とする請求項９記載の画像検索装置。
【請求項１１】
前記近似空間検索手段は、前記正誤指定手段で不正解と指定した近似データが前記実空間最終ランク付け手段で再出力されないように、前記検索条件である「利用する次元数」と「絞込む件数」を自動調整することを特徴とする請求項９記載の画像検索装置。
【請求項１２】
画像から抽出した多次元特徴データの次元を縮退して生成した近似データを用いて、画像蓄積手段に蓄積されている画像群を検索対象画像との類似度順に並べる近似空間検索ステップと、
前記近似空間検索ステップで得られた類似度の高い結果群に対して、次元縮退前の多次元特徴データを用いて再類似度計算を行ない最終順位を決定する実空間最終ランク付けステップとを有する画像検索方法。
【請求項１３】
前記多次元特徴データを構成する要素を絶対値の大きい順に並替え、上位Ｎ個（Ｎ：自然数）の(要素番号,値)を前記近似データとして生成することを特徴とする請求項１２記載の画像検索方法。
【請求項１４】
入力する多次元特徴データのウェーブレット変換結果から、高周波成分又は低周波成分の上位Ｎ個の値を前記近似データとして生成することを特徴とする請求項１２記載の画像検索方法。
【請求項１５】
前記近似データとして生成された上位Ｎ個以外の多次元特徴データを(代表値,符号ビット)として生成し前記近似データとして管理することを特徴とする請求項１３または１４記載の画像検索方法。
【請求項１６】
前記実空間最終ランク付けステップは、前記近似空間検索ステップで得られた類似度の高い上位Ｍ件（Ｍ：自然数）に対して最終順位付けを行ない、検索結果として上位Ｋ件(Ｋ<Ｍ)を出力することを特徴とする請求項１２記載の画像検索方法。
【請求項１７】
前記実空間最終ランク付けステップは、前記近似空間検索ステップで得られた類似度の高い要素(すなわち近似距離の小さい要素)から順に、次元縮退前の多次元特徴データを用いて再類似度計算を行ない、再類似度計算して得られた類似度の高い上位Ｋ件の実距離が、再類似度計算を行なっていない全データの近似距離より小さくなった時点で処理を完了し、前記上位Ｋ件を検索結果として出力することを特徴とする請求項１２記載の画像検索方法。
【請求項１８】
前記実空間最終ランク付けステップは、前記近似空間検索ステップで得られた結果が、最終ランク付けでどの程度変更したかを示す「次元縮退による歪み率」を結果として出力することを特徴とする請求項１２記載の画像検索方法。
【請求項１９】
「利用する次元数」と「絞込む件数」を、前記近似空間検索ステップで用いる検索条件として指定する再検索条件指定ステップを有することを特徴とする請求項１８記載の画像検索方法。
【請求項２０】
前記実空間最終ランク付けステップで出力した検索結果に対して正解または不正解を指定する正誤指定ステップを有することを特徴とする請求項１２記載の画像検索方法。
【請求項２１】
前記近似空間検索ステップは、前記正誤指定ステップで正解と指定した近似データの要素番号を「正解要素番号群」として、また、不正解と指定した近似データの要素番号を「誤り要素番号群」として設定し、近似データを用いた類似度計算過程で、「正解要素番号群」に含まれる各要素番号の重み付けを強く、「誤り要素番号群」に含まれる各要素番号の重み付けを弱くすることを特徴とする請求項２０記載の画像検索方法。
【請求項２２】
前記近似空間検索ステップは、前記正誤指定ステップで不正解と選択した近似データが前記実空間最終ランク付けステップで再出力されないように、前記検索条件である「利用する次元数」と「絞込む件数」を自動調整することを特徴とする請求項２０記載の画像検索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００７−１７２３８４（Ｐ２００７−１７２３８４Ａ）
【公開日】平成１９年７月５日（２００７．７．５）
【国際特許分類】
【出願番号】特願２００５−３７０６１３（Ｐ２００５−３７０６１３）
【出願日】平成１７年１２月２２日（２００５．１２．２２）
【出願人】（０００００５８２１）松下電器産業株式会社 (73,050)
【Ｆターム（参考）】
【公開日】平成１９年７月５日（２００７．７．５）
【国際特許分類】
【出願日】平成１７年１２月２２日（２００５．１２．２２）
【出願人】（０００００５８２１）松下電器産業株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]