(57)【要約】  ベクトルデータ間の照合処理を高速に実行する。  照合装置１００は、複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行う。照合装置１００は、一括演算部１５０、及び、個別演算部１６０を含む。一括演算部１５０は、複数次元の内の特定次元の各々に係る所定演算を、複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により行う。個別演算部１６０は、特定次元以外の次元の各々に係る所定演算を、複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて行う。
2015194132.tif 000002
【特許請求の範囲】
【請求項１】
複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行う情報処理装置であって、
前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により行う一括演算手段と、
前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて行う個別演算手段と、
を備えた情報処理装置。
【請求項２】
前記特定次元は、前記複数次元の内の、前記所定演算が行われる順番が所定値以下の次元である、
請求項１に記載の情報処理装置。
【請求項３】
さらに、前記一括演算手段、及び、前記個別演算手段の内の少なくとも一方における、前記所定演算の実行状況に応じて、前記特定次元を決定する次元決定手段を備えた、
請求項１または２に記載の情報処理装置。
【請求項４】
前記次元決定手段は、前記特定次元以外の一の次元について、前記個別演算手段において前記所定演算が行われた回数または割合が所定値以上の場合、当該一の次元を前記特定次元に含める、
請求項３に記載の情報処理装置。
【請求項５】
前記所定演算は、ベクトルデータ間の各次元の差分、及び、差分の累積値の計算を含み、
前記個別演算手段は、前記所定の条件として、前記差分の累積値が所定の打ち切り閾値未満のベクトルデータについて、前記所定演算を行う、
請求項１乃至４のいずれかに記載の情報処理装置。
【請求項６】
複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行うベクトルデータ処理方法であって、
前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により実行する一括演算処理を行い、
前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて実行する個別演算処理を行う、
ベクトルデータ処理方法。
【請求項７】
前記特定次元は、前記複数次元の内の、前記所定演算が行われる順番が所定値以下の次元である、
請求項６に記載のベクトルデータ処理方法。
【請求項８】
さらに、前記一括演算処理、及び、前記個別演算処理の内の少なくとも一方における、前記所定演算の実行状況に応じて、前記特定次元を決定する、
請求項６または７に記載のベクトルデータ処理方法。
【請求項９】
前記特定次元以外の一の次元について、前記個別演算処理において前記所定演算が行われた回数または割合が所定値以上の場合、当該一の次元を前記特定次元に含める、
請求項８に記載のベクトルデータ処理方法。
【請求項１０】
複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行うコンピュータのプログラムを格納する記録媒体であって、
前記コンピュータに、
前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により行い、
前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて行う、
処理を実行させるプログラムを格納する、コンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、ベクトルデータ処理方法、及び、記録媒体に関する。
【背景技術】
【０００２】
複数の画像の一致を判定する画像照合処理は、一般的に、各画像から抽出した特徴量を比較することにより行われる。例えば、画像検索システムでは、データベースに格納された複数の画像の特徴量と入力画像から得られた特徴量とを比較することによって、複数の画像の各々と入力画像との照合を行う。一般に、特徴量は、特徴ベクトルと呼ばれる、多次元のベクトルデータで表される。【０００３】
図１９は、一般的な照合処理における、ベクトルデータ間の距離計算の例を示す図である。【０００４】
ベクトルデータの比較は、典型的には、比較対象の二つのベクトルデータの要素ごとの差分を計算し、それらを集約した値を閾値と比較することによって行われる。ここで、集約された差分は距離と呼ばれ、二つのベクトルデータ間の距離の計算は距離計算と呼ばれる。例えば、ベクトルデータの各要素が単一の値で表される場合、各要素の値の差分の絶対値を合計した値が距離として用いられる。すなわち、二つのベクトルデータがａ、ｂの場合、ベクトルデータａ、ｂ間の距離は、図１９に示すように、Σ｜ａ［ｊ］−ｂ［ｊ］｜で計算される。ここでａ［ｊ］、ｂ［ｊ］は、それぞれ、ベクトルデータａ、ｂのｊ番目の要素を示し、Σは全要素に対する累積を示す。また、計算した距離の比較では、例えば、距離が所定の比較閾値以下の場合、二つのベクトルデータは一致すると判定される。また、所定の比較閾値よりも大きい場合、二つのベクトルデータは一致しないと判定されることもある。【０００５】
画像検索システムにおける照合処理では、データベースに含まれる各ベクトルデータと検索対象のベクトルデータとの間で距離計算が行われる。【０００６】
図２０は、一般的な照合処理のプログラムの例である。図２０の例では、データベース中のベクトルデータの数が１２、ベクトルデータの要素の数が８である。ここで、ｕ［ｉ］［ｊ］は、データベース中のｉ番目のベクトルデータのｊ番目の要素、ｖ［ｊ］は、検索対象のベクトルデータのｊ番目の要素である。Ｔは比較閾値で、距離ｄがＴより小さい場合に、データベース中のｉ番目のベクトルデータと検索対象のベクトルデータは一致すると判定される（行番号８、９）。【０００７】
データベース中に大量のベクトルデータが含まれる場合、検索時間の長さが問題になる。検索時間を短縮するためには、ベクトルデータ間の距離計算を高速に行うことが重要である。【０００８】
ベクトルデータ間の距離計算を高速に行う方法としては、例えば、打ち切り判定が用いられる。図２１は、一般的な照合処理における、打ち切り判定の適用例を示す図である。打ち切り判定では、ベクトルデータ中の一部の要素の差のみを累積した途中の距離を所定の打ち切り閾値と比較する。そして、途中の距離が打ち切り閾値以上の場合（打ち切り条件を満たす場合）、図２１に示すように、それ以上の距離計算を不要と判定し、距離計算を終了する（打ち切り処理）。【０００９】
図２２は、一般的な照合処理において打ち切り判定を適用したプログラムの例である。図２２の例では、途中の距離が打ち切り閾値Ｔ以上になった場合に、打ち切り処理が行われる（行番号７、８）。ここでは、打ち切り閾値に、比較閾値Ｔが用いられている。【００１０】
図２３は、一般的な照合処理において打ち切り判定を適用した場合に、差分計算が行われる要素の例を示す図である。図２３の例では、データベース中のベクトルデータｕ［０］…ｕ［１１］について、斜線で示された要素が、差分計算が行われなかった（差分計算が不要な）要素を、それ以外が、差分計算が行われた（差分計算が必要な）要素を表している。この場合、ベクトルデータｕ［２］については、全次元で差分計算が行われているが、他のベクトルデータについては、１番目の次元のみ差分計算が行われている。すなわち、差分計算は、１９個の要素に対して、１９回行われている。【００１１】
画像照合におけるベクトルデータの距離計算で、このような打ち切り判定を行うシステムの一例が、例えば、特許文献１に開示されている。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】国際公開第２００８／０４４３８０号
【発明の概要】
【発明が解決しようとする課題】
【００１３】
ベクトルデータ間の距離計算を高速に行う他の方法として、ＣＰＵ（Central Processing Unit）の備えるベクトル命令を用いる方法がある。図２４は、一般的な照合処理における、ベクトル命令の適用例を示す図である。ベクトル命令は、ＣＰＵにおいて、複数データに対する同一の処理を一度の命令で処理（ベクトル演算）するものであり、複数データの各々に対して同じ命令を用いる場合に比べて、短時間で処理できる。ベクトルデータ間の距離計算は、図２４に示すように、各要素に対する差分の計算を、ベクトル命令を用いて行うことで高速化できる。図２４の例では、４つの要素に対する計算を一つのベクトル命令で行っている。【００１４】
さらに、ベクトルデータ間の距離計算をより高速に行うために、上述の、打ち切り判定とベクトル命令の両方を用いることが考えられる。図２５は、一般的な照合処理における、打ち切り判定とベクトル命令との適用例を示す図である。この場合、図２５に示すように、ベクトル命令により、複数の要素に対する計算が行われ、その結果を用いて、打ち切り判定が行われる。ベクトル命令の途中で打ち切り判定は行われないため、図２５の太枠内の斜線部のように、差分計算が不要な次元に対しても、無駄な計算が行われる。【００１５】
図２６は、一般的な照合処理において打ち切り判定とベクトル命令を適用した場合に差分計算が行われる要素の例を示す図である。図２６の例では、太枠内の要素が、ベクトル命令によって差分計算が一度に行われた要素を表している。この場合、差分計算が必要な要素は１９個であるが、１３回のベクトル命令により、５２個の要素に対して差分計算が行われている。すなわち、命令の回数は１３回に削減しているが、太枠内の斜線で示された、３３個の要素に対する計算は無駄に行われている。【００１６】
このように、照合処理に打ち切り判定とベクトル命令の両方を用いた場合、一度に複数の差分計算を行うことができるものの、無駄な計算も発生する。したがって、ベクトル命令による高速化の効果が十分発揮されない。【００１７】
本発明の目的は、上述した課題を解決し、ベクトルデータ間の照合処理を高速に実行する情報処理装置、ベクトルデータ処理方法、及び、記録媒体を提供することである。
【課題を解決するための手段】
【００１８】
本発明の一態様における情報処理装置は、複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行う情報処理装置であって、前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により行う一括演算手段と、前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて行う個別演算手段と、を備える。【００１９】
本発明の一態様におけるベクトルデータ処理方法は、複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行うベクトルデータ処理方法であって、前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により実行する一括演算処理を行い、前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて実行する個別演算処理を行う。【００２０】
本発明の一態様におけるコンピュータが読み取り可能な記録媒体は、複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行うコンピュータのプログラムを格納する記録媒体であって、前記コンピュータに、前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により行い、前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて行う、処理を実行させるプログラムを格納する。
【発明の効果】
【００２１】
本発明の効果は、ベクトルデータ間の照合処理を高速に実行できることである。
【図面の簡単な説明】
【００２２】
【図１】本発明の第１の実施の形態の特徴的な構成を示すブロック図である。
【図２】本発明の第１の実施の形態における、照合装置１００の構成を示すブロック図である。
【図３】本発明の第１の実施の形態における、一括演算部１５０の構成を示す図である。
【図４】本発明の第１の実施の形態における、個別演算部１６０の構成を示す図である。
【図５】本発明の第１の実施の形態における、ベクトルデータ集合の記憶媒体上への格納形式の例を示す図である。
【図６】本発明の第１の実施の形態における、コンピュータにより実現された照合装置１００の構成を示すブロック図である。
【図７】本発明の第１の実施の形態における、照合装置１００の動作を示すフローチャートである。
【図８】本発明の第１の実施の形態における、一括演算処理を示すフローチャートである。
【図９】本発明の第１の実施の形態における、個別演算処理を示すフローチャートである。
【図１０】本発明の第１の実施の形態における、照合装置１００のプログラムの例である。
【図１１】本発明の第１の実施の形態における、演算が行われる要素の例を示す図である。
【図１２】本発明の第１の実施の形態における、一括演算部１５０、個別演算部１６０に係る他の構成を示すブロック図である。
【図１３】本発明の第２の実施の形態における、個別演算部１６０の構成を示す図である。
【図１４】本発明の第２の実施の形態における、ベクトルデータ集合の記憶媒体上への格納形式の例を示す図である。
【図１５】本発明の第２の実施の形態における、照合装置１００のプログラムの例である。
【図１６】本発明の第３の実施の形態における、照合装置１００の構成を示すブロック図である。
【図１７】本発明の第３の実施の形態における、照合装置１００のプログラムの例である。
【図１８】本発明の第３の実施の形態における、照合装置１００の他の構成を示すブロック図である。
【図１９】一般的な照合処理における、ベクトルデータ間の距離計算の例を示す図である。
【図２０】一般的な照合処理のプログラムの例である。
【図２１】一般的な照合処理における、打ち切り判定の適用例を示す図である。
【図２２】一般的な照合処理において打ち切り判定を適用したプログラムの例である。
【図２３】一般的な照合処理において打ち切り判定を適用した場合に、差分計算が行われる要素の例を示す図である。
【図２４】一般的な照合処理における、ベクトル命令の適用例を示す図である。
【図２５】一般的な照合処理における、打ち切り判定とベクトル命令の適用例を示す図である。
【図２６】一般的な照合処理において打ち切り判定とベクトル命令を適用した場合に差分計算が行われる要素の例を示す図である。
【発明を実施するための形態】
【００２３】
（第１の実施の形態）
本発明の第１の実施の形態について説明する。
【００２４】
本発明の第１の実施の形態では、ベクトルデータは、複数の次元を有する。ベクトルデータの各次元には、先頭から順番に次元番号が付与される。
【００２５】
ベクトルデータ間の照合は、ベクトル間の距離をもとに行われる。ベクトル間の距離の算出は、各次元の要素間の、所定の演算（差分、及び、差分の累積値の計算、累積値と打ち切り閾値との比較）により行われる。各次元に対する所定の演算が行われる順番は、例えば、次元番号の順番等、予め、決められていると仮定する。
【００２６】
次に、本発明の第１の実施の形態の構成を説明する。図２は、本発明の第１の実施の形態における、照合装置１００の構成を示すブロック図である。照合装置１００は、本発明の情報処理装置の一実施形態である。
【００２７】
本発明の第１の実施の形態の照合装置１００は、データ入力部１１０、対象データ格納部１２０、データ集合格納部１３０、演算方法選択部１４０、一括演算部１５０、個別演算部１６０、距離格納部１７０、結果格納部１８０、及び、結果出力部１９０を含む。
【００２８】
データ入力部１１０は、ユーザ等から、照合対象のベクトルデータ（対象ベクトルデータ）の入力を受け付ける。
【００２９】
対象データ格納部１２０は、対象ベクトルデータを格納する。
【００３０】
データ集合格納部１３０は、対象ベクトルデータとの照合を行うベクトルデータの集合（ベクトルデータ集合）を格納する。ベクトルデータ集合は、利用者等により、予め登録される。
【００３１】
演算方法選択部１４０は、ベクトルデータの複数の次元を、一括演算部１５０を用いて上述の所定の演算を行う次元（特定の次元）と、個別演算部１６０を用いて上述の所定の演算を行う次元（特定の次元以外の次元）と、に分割する。そして、演算方法選択部１４０は、分割された次元を、一括演算部１５０と個別演算部１６０とに割り当てる。
【００３２】
例えば、演算方法選択部１４０は、複数の次元の内、上述の所定の演算が行われる順番が、予めユーザ等により設定された所定値以下の次元を、一括演算部１５０に割り当て、所定値を超える次元を、個別演算部１６０に割り当てる。各次元に対する所定の演算が、次元番号の順番で行われる場合、演算方法選択部１４０は、次元番号が所定値以下の次元を、一括演算部１５０に割り当て、所定値を超える次元を、個別演算部１６０に割り当てる。
【００３３】
一括演算部１５０、及び、個別演算部１６０は、それぞれ、演算方法選択部１４０により割り当てられた次元について、ベクトルデータ集合内のベクトルデータと対象ベクトルデータとの間で、上述の所定の演算を行う。
【００３４】
距離格納部１７０は、一括演算部１５０、及び、個別演算部１６０によって、次元ごとに計算された差分の累積値を、ベクトルデータ集合中のベクトルデータごとに格納する。
【００３５】
結果格納部１８０は、一括演算部１５０、及び、個別演算部１６０による、各ベクトルデータと対象ベクトルデータとの間の距離と比較閾値との比較結果を格納する。
【００３６】
結果出力部１９０は、ユーザ等へ、照合結果を出力する。
【００３７】
図３は、本発明の第１の実施の形態における、一括演算部１５０の構成を示す図である。
【００３８】
一括演算部１５０は、次元制御部１５１、集合内データ制御部１５２、及び、複数要素演算部１５３を含む。
【００３９】
次元制御部１５１は、一括演算部１５０に割り当てられた次元の集合（次元集合）から、次元を一つずつ選択する。典型的には、次元制御部１５１は、割り当てられた次元集合の先頭から末尾に向けて、次元を一つずつ選択し、末尾に達したら処理を終了する（図３、符号１５０１）。集合内データ制御部１５２は、ベクトルデータ集合から複数のベクトルデータを選択する。典型的には、一度に選択するベクトルデータの数は、一つのベクトル命令によって同時に処理可能なデータ数と同一である。また、典型的には、集合内データ制御部１５２は、ベクトルデータ集合内の先頭のベクトルデータから最後のベクトルデータに向けて、ベクトルデータを順番に選択し、最後のベクトルデータの処理が終わったら処理を終了する（図３、符号１５０２）。複数要素演算部１５３は、選択された複数のベクトルデータについて、選択された次元に係る所定の演算を、ベクトル命令を用いて一括して行う。すなわち、複数要素演算部１５３は、選択された複数のベクトルデータの各々と対象ベクトルデータの間で、選択された次元の要素間の差分を計算し、距離格納部１７０に累積する。また、複数要素演算部１５３は、選択された複数のベクトルデータの各々について、累積値と比較閾値との比較を行い、比較結果を結果格納部１８０に保存する。
【００４０】
図４は、本発明の第１の実施の形態における、個別演算部１６０の構成を示す図である。
【００４１】
個別演算部１６０は、次元制御部１６１、集合内データ制御部１６２、打ち切り判定部１６３、及び、単要素演算部１６４を含む。
【００４２】
次元制御部１６１は、個別演算部１６０に割り当てられた次元集合から、次元を一つずつ選択する。典型的には、次元制御部１６１は、割り当てられた次元集合の先頭から末尾に向けて、次元を一つずつ選択し、末尾に達したら処理を終了する（図４、符号１６０１）。集合内データ制御部１６２は、ベクトルデータ集合から、ベクトルデータを一つずつ選択する。典型的には、集合内データ制御部１６２は、集合内の先頭のベクトルデータから最後のベクトルデータに向けて、ベクトルデータを順番に選択し、最後のベクトルデータの処理が終わったら終了する（図４、符号１６０２）。打ち切り判定部１６３は、選択された一つのベクトルデータについて、打ち切り判定を行う。ここで、打ち切り判定部１６３は、差分の累積値と打ち切り閾値とを比較し、差分が打ち切り条件を満たしているかを判定する。打ち切り条件を満たしていない場合（所定の条件を満たしている場合）、単要素演算部１６４は、選択された一つのベクトルデータについて、選択された次元に係る演算を行う。すなわち、単要素演算部１６４は、選択された一つのベクトルデータと対象ベクトルデータの間で、選択された次元の要素間の差分を計算し、距離格納部１７０に累積する。また、単要素演算部１６４は、選択された一つのベクトルデータについて、累積値と比較閾値との比較を行い、比較結果を結果格納部１８０に保存する。
【００４３】
図５は、本発明の第１の実施の形態における、ベクトルデータ集合の記憶媒体上への格納形式の例を示す図である。図５において、ｍは、ベクトルデータの数を示す。
【００４４】
本発明の第１の実施の形態では、一つのベクトル命令が、ベクトルデータ集合中の異なるベクトルデータの同じ次元の要素について演算を行う。したがって、ベクトルデータ集合の記憶媒体への格納形式として、図５のように、同じ次元に係る異なるベクトルデータの要素が、連続して格納される形式が望ましい。
【００４５】
なお、照合装置１００は、ＣＰＵとプログラムを記憶した記憶媒体を含み、プログラムに基づく制御によって動作するコンピュータであってもよい。
【００４６】
図６は、本発明の第１の実施の形態における、コンピュータにより実現された照合装置１００の構成を示すブロック図である。照合装置１００は、ＣＰＵ１０１、ハードディスクやメモリ等の記憶手段（記憶媒体）１０２、他の装置等とデータ通信を行う通信手段１０３、キーボード等の入力手段１０４、及び、ディスプレイ等の出力手段１０５を含む。
【００４７】
ＣＰＵ１０１は、データ入力部１１０、演算方法選択部１４０、一括演算部１５０、個別演算部１６０、及び、結果出力部１９０の機能を実現するためのコンピュータプログラムを実行する。記憶手段１０２は、対象データ格納部１２０、データ集合格納部１３０、距離格納部１７０、及び、結果格納部１８０のデータを記憶する。また、対象データ格納部１２０、データ集合格納部１３０、距離格納部１７０、及び、結果格納部１８０は、それぞれ個別の記憶媒体でも、１つの記憶媒体によって構成されてもよい。入力手段１０４は、対象ベクトルデータやベクトルデータ集合の入力を受け付ける。出力手段１０５は、照合結果を出力する。また、通信手段１０３が、他の装置から対象ベクトルデータの入力を受け付ける、あるいは、他の装置へ、照合結果を出力してもよい。
【００４８】
また、図２に示した照合装置１００の各構成要素は、独立した論理回路でもよい。
【００４９】
次に、本発明の第１の実施の形態の動作を説明する。
【００５０】
図７は、本発明の第１の実施の形態における、照合装置１００の動作を示すフローチャートである。
【００５１】
データ入力部１１０は、ユーザ等から、対象ベクトルデータの入力を受け付ける（ステップＳ１）。データ入力部１１０は、対象ベクトルデータを、対象データ格納部１２０に保存する。
【００５２】
演算方法選択部１４０は、ベクトルデータの次元を、一括演算部１５０を用いて所定の演算を行う次元と、個別演算部１６０を用いて所定の演算を行う次元に分割し、一括演算部１５０と個別演算部１６０に割り当てる（ステップＳ２）。
【００５３】
一括演算部１５０は、割り当てられた次元に対して、データ集合格納部１３０に格納されたベクトルデータ集合中の各ベクトルデータと対象データ格納部１２０に格納された対象ベクトルデータとの間で、一括演算処理を行う（ステップＳ３）。
【００５４】
図８は、本発明の第１の実施の形態における、一括演算処理を示すフローチャートである。
【００５５】
次元制御部１５１は、一括演算部１５０に割り当てられた次元集合から、次元を一つ選択する（ステップＳ３１）。
【００５６】
集合内データ制御部１５２は、ベクトルデータ集合から複数のベクトルデータを選択する（ステップＳ３２）。ここで、選択されるベクトルデータの数には、一つのベクトル命令で同時に処理できるデータ数（ベクトル長）、または、それ以下の数が用いられる。
【００５７】
複数要素演算部１５３は、選択された複数のベクトルデータに対して、選択された次元に係る所定の演算を、ベクトル命令により同時に行う（ステップＳ３３）。
【００５８】
ここで、複数要素演算部１５３は、選択された複数のベクトルデータの各々と対象ベクトルデータの間で、選択された次元の要素間の差分を計算し、距離格納部１７０に累積する。また、複数要素演算部１５３は、選択された複数のベクトルデータの各々について、累積値と比較閾値との比較を行い、比較結果を結果格納部１８０に格納する。なお、複数要素演算部１５３は、累積値と打ち切り閾値とを比較し、差分や比較結果を格納する必要がない場合（打ち切り条件を満たす場合）は、距離格納部１７０や結果格納部１８０への格納を省略するといった、マスク処理を実行してもよい。
【００５９】
そして、ベクトルデータ集合内の全てのベクトルデータについて、ステップＳ３２からの処理が繰り返される（ステップＳ３４）。
【００６０】
また、一括演算部１５０に割り当てられた次元集合の内の全ての次元について、ステップＳ３１からの処理が繰り返される（ステップＳ３５）。
【００６１】
このように、一括演算部１５０は、ベクトル命令を用いることで、選択された複数のベクトルデータについての所定の演算を一度に行う。演算は、打ち切り条件を満たしているかどうか（演算が不要かどうか）に係らず行われる。
【００６２】
次に、個別演算部１６０は、割り当てられた次元に対して、データ集合格納部１３０に格納されたベクトルデータ集合中の各ベクトルデータと対象データ格納部１２０に格納された対象ベクトルデータとの間で、個別演算処理を行う（ステップＳ４）。
【００６３】
図９は、本発明の第１の実施の形態における、個別演算処理を示すフローチャートである。
【００６４】
次元制御部１６１は、個別演算部１６０に割り当てられた次元集合から、次元を一つ選択する（ステップＳ４１）。
【００６５】
集合内データ制御部１６２は、ベクトルデータ集合から一つのベクトルデータを選択する（ステップＳ４２）。
【００６６】
打ち切り判定部１６３は、距離格納部１７０を参照し、選択された一つのベクトルデータが、これまでの他の次元に対する演算の結果、打ち切り条件を満たしているか判定する（ステップＳ４３）。ここで、打ち切り判定部１６３は、選択されたベクトルデータの差分の累積値が打ち切り閾値以上の場合、打ち切り条件を満たしていると判定する。
【００６７】
ステップＳ４３で打ち切り条件を満たしている場合（ステップＳ４３／Ｙ）、ステップＳ４２の処理に戻る。
【００６８】
ステップＳ４３で打ち切り条件を満たしていない場合（ステップＳ４３／Ｎ）、単要素演算部１６４は、選択された一つのベクトルデータについて、選択された次元に係る所定の演算を行う（ステップＳ４４）。
【００６９】
ここで、単要素演算部１６４は、選択された一つのベクトルデータと対象ベクトルデータの間で、選択された次元の要素間の差分を計算し、距離格納部１７０に累積する。また、単要素演算部１６４は、選択された一つのベクトルデータについて、累積値と比較閾値との比較を行い、比較結果を結果格納部１８０に格納する。
【００７０】
そして、ベクトルデータ集合内の全てのデータについて、ステップＳ４２からの処理が繰り返される（ステップＳ４５）。
【００７１】
また、個別演算部１６０に割り当てられた次元集合の内の全ての次元について、ステップＳ４１からの処理が繰り返される（ステップＳ４６）。
【００７２】
このように、個別演算部１６０は、打ち切り条件を満たさないベクトルデータの要素に対してのみ、演算を行う。
【００７３】
次に、結果出力部１９０は、結果格納部１８０に格納された比較結果を、照合結果として、ユーザ等へ出力する（ステップＳ５）。
【００７４】
以上により、本発明の第１の実施の形態の動作が完了する。
【００７５】
一般に、ベクトルデータ間の距離は、差分を累積した次元数が増加するほど大きくなる。したがって、差分の計算が完了した次元数が少ない場合は、差分の累積値が打ち切り条件を満たさないことが多い（演算が必要な割合が多い）。また、差分の計算が完了した次元数が多い場合は、差分の累積値が打ち切り条件を満たすことが多い（演算が必要な割合が少ない）。
【００７６】
演算が必要な割合が多い次元に対しては、一括演算部１５０を用いることにより、ベクトル命令による一括演算が行われるため、複数のベクトルデータに対する演算を効率化できる。一方、演算が必要な割合が少ない次元に対しては、個別演算部１６０を用いることにより、打ち切り条件を満たさない要素に対してのみ差分計算が行われるため、無駄な演算は行われない。このように、ベクトル命令を活用しながらも、無駄な演算の回数が低減される。
【００７７】
次に、本発明の第１の実施の形態の具体例を説明する。
【００７８】
図１０は、本発明の第１の実施の形態における、照合装置１００のプログラムの例である。図１０の例では、図２０のプログラムと同様に、ベクトルデータ集合のベクトルデータの数が１２、各ベクトルデータの要素の数が８である。ここで、ｕ［ｊ］［ｉ］は、ベクトルデータ集合のｉ番目のベクトルデータのｊ番目の要素、ｖ［ｊ］が対象ベクトルデータのｊ番目の要素である。
【００７９】
図１０のプログラムには、二つの二重ループがあるが、一つ目の二重ループ（行番号４〜１０）が一括演算部１５０の処理、二つ目の二重ループ（行番号１２〜２０）が個別演算部１６０の処理に対応する。それぞれの二重ループでは、「#Pragma vector」、「#Pragma novector」によって、ベクトル演算をするようにコンパイルするかどうかが指定されている。各次元に対して、一括演算部１５０と個別演算部１６０の内のどちらを選択するかは、変数Ｋにより指定されている。図１０の例では、１番目の次元以外は、所定の演算が必要な割合が十分に少ない（打ち切り判定により、演算が不要と判定される確率が高い）ことが既知であるため、Ｋに１が設定されている。
【００８０】
Ｔは比較閾値で、距離ｄがＴより小さい場合に、ベクトルデータ集合のｉ番目のベクトルデータと対象ベクトルデータは一致すると判定される。Ｔは変数でも定数でもよい。また、打ち切り閾値にも、比較閾値Ｔが用いられている。
【００８１】
なお、図１０のプログラムでは、ベクトルデータ集合が、記憶媒体上で、図５のように格納されているため、図２０のプログラムに対して、ベクトルデータ集合ｕが転置されている。また、図２０のプログラムと異なり、次元に係るループが、ベクトルデータ集合中のベクトルデータに係るループよりも外側に存在する。
【００８２】
図１１は、本発明の第１の実施の形態における、演算が行われる要素の例を示す図である。図１１の例では、斜線で示された要素が、所定の演算が不要な要素を、太枠内の要素が、一括演算部１５０により、ベクトル命令を用いて所定の演算が一度に行われた要素を、それ以外が、個別演算部１６０により所定の演算が行われた要素を表している。この場合、１番目の次元の要素については、ベクトルデータ集合内の異なるベクトルデータの方向に、ベクトル命令を用いて、所定の演算が行われている。２番目以降の次元の要素については、打ち切り判定をしながら、所定の演算が行われている。そして、所定の演算が必要な１９個の要素について、１０回の命令により、演算が行われている。これにより、無駄な演算の回数が低減し、照合処理が高速に実行される。
【００８３】
なお、図１０、図１１の例では、ベクトルデータ集合内のベクトルデータの数は１２である。一般には、ベクトルデータの数は多数であり、特に、１番目の次元以外について、演算が必要な割合が十分に少ない場合、本発明を用いない場合に比べて、高速化の度合いがより大きくなる。
【００８４】
また、本発明の第１の実施の形態では、ベクトルデータ間の距離を得るための所定の演算として、次元ごとの差分、及び、差分の累積値を計算する場合を例に説明した。しかしながら、これに限らず、次元ごとの計算結果をもとにベクトルデータ間の距離を算出できれば、所定の演算として、他の方法を用いてもよい。また、ベクトルデータ間の照合に用いることができれば、距離以外の他の値を算出してもよい。
【００８５】
図１２は、本発明の第１の実施の形態における、一括演算部１５０、個別演算部１６０に係る他の構成を示すブロック図である。
【００８６】
図３、図４では、次元制御部１５１、１６１が、それぞれ、一括演算部１５０、個別演算部１６０に含まれていた。しかしながら、これに限らず、図１２のように、共通な次元制御部１５１が、一括演算部１５０、個別演算部１６０の外に存在してもよい。
【００８７】
図１２では、次元制御部１５１の処理の後に、演算方法選択部１４０の処理が行われる。この場合、演算方法選択部１４０は、次元制御部１５１によって選択された次元に対して、一括演算部１５０を用いるか、個別演算部１６０を用いるかを選択する。一括演算部１５０、個別演算部１６０は、選択された次元に対して、差分を計算する。これにより、次元制御部１５１が共通化できる。
【００８８】
次に、本発明の第１の実施の形態の特徴的な構成を説明する。図１は、本発明の第１の実施の形態の特徴的な構成を示すブロック図である。
【００８９】
照合装置１００（情報処理装置）は、複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行う。照合装置１００は、一括演算部１５０、及び、個別演算部１６０を含む。一括演算部１５０は、複数次元の内の特定次元の各々に係る所定演算を、複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により行う。個別演算部１６０は、特定次元以外の次元の各々に係る所定演算を、複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて行う。
【００９０】
本発明の第１の実施の形態によれば、ベクトルデータ間の照合処理を高速に実行できる。その理由は、一括演算部１５０が、複数次元の内の特定次元に係る所定演算を、異なるベクトルデータに対するベクトル演算により行い、個別演算部１６０が、特定次元以外の次元に係る所定演算を、所定の条件を満たすベクトルデータについて行うためである。
【００９１】
（第２の実施の形態）
次に、本発明の第２の実施の形態について説明する。
【００９２】
図１３は、本発明の第２の実施の形態における、個別演算部１６０の構成を示す図である。
【００９３】
本発明の第２の実施の形態の個別演算部１６０は、集合内データ制御部１６５、打ち切り判定部１６６、次元制御部１６７、打ち切り判定部１６８、及び、単要素演算部１６９を含む。本発明の第２の実施の形態の個別演算部１６０では、ベクトルデータ集合内の選択されたベクトルデータについて、個別演算部１６０に割り当てられた各次元に対する演算を連続して行う点で、本発明の第１の実施の形態と異なる。
【００９４】
集合内データ制御部１６５は、ベクトルデータ集合から、ベクトルデータを一つずつ選択する。打ち切り判定部１６６は、選択された一つのベクトルデータについて、打ち切り判定を行う。次元制御部１６７は、個別演算部１６０に割り当てられた次元集合から、次元を一つずつ選択する。打ち切り判定部１６８は、選択された次元について、打ち切り判定を行う。打ち切り判定部１６８により演算が必要と判定された場合、単要素演算部１６９は、選択された一つのベクトルデータについて、選択された次元に係る演算を行う。打ち切り判定部１６６、１６８により、演算の必要なしと判定された場合は、集合内データ制御部１６５に戻る。
【００９５】
これにより、一旦、打ち切り判定部１６６、１６８により、演算の必要がないと判定されたベクトルデータについては、本発明の第１の実施の形態のような、次元制御部が次の次元を選択する処理は行われず、次元制御部に係る処理量を低減できる。したがって、照合処理に係る所定の演算の演算量が比較的少なく、次元制御部の処理量の全体に占める割合が大きい場合、照合処理がさらに高速化される。
【００９６】
図１４は、本発明の第２の実施の形態における、ベクトルデータ集合の記憶媒体上への格納形式の例を示す図である。図１４において、ｎは、次元数を示す。
【００９７】
本発明の第２の実施の形態の個別演算部１６０は、同じベクトルデータ内の異なる次元に対する演算が連続して行われる。しがたって、ベクトルデータ集合の記憶媒体への格納形式としては、図１４のように、同じベクトルデータ内の各次元の要素が連続的に格納されている形式が望ましい。一方で、一括演算部１５０は、本発明の第１の実施の形態と同様の動作を行うため、図５のように、同じ次元に係る異なるベクトルデータの要素が、連続して格納される形式が望ましい。したがって、本発明の第２の実施の形態では、データ集合格納部１３０がベクトルデータ集合を、図５及び図１４の両方の形式で格納し、一括演算部１５０と個別演算部１６０とで使い分けてもよい。
【００９８】
次に、本発明の第２の実施の形態の具体例を説明する。
【００９９】
図１５は、本発明の第２の実施の形態における、照合装置１００のプログラムの例である。図１５の例では、本発明の第１の実施の形態と比べて、個別演算部１６０の処理に対応する二つ目の二重ループ（行番号１２〜２３）の内側と外側が入れ替えられ、次元に対するループ（内側ループ）で、打ち切り判定（行番号１７、１８）が行われている。ベクトルデータの次元数が大きく、かつ、打ち切り判定により演算不要と判定される前に、十分な回数の演算が行われる場合、内側ループをベクトル命令で実行してもよい。
【０１００】
本発明の第２の実施の形態によれば、本発明の第１の実施の形態に比べて、照合処理をさらに高速化できる。その理由は、個別演算部１６０が、ベクトルデータ集合内の選択されたベクトルデータについて、個別演算部１６０に割り当てられた各次元に対する演算を連続して行うためである。
【０１０１】
（第３の実施の形態）
次に、本発明の第３の実施の形態について説明する。
【０１０２】
図１６は、本発明の第３の実施の形態における、照合装置１００の構成を示すブロック図である。
【０１０３】
本発明の第３の実施の形態の照合装置１００は、本発明の第１の実施の形態の照合装置１００の構成に加えて、演算回数測定部２１０、及び、選択方法決定部２２０（または、次元決定部）を含む。
【０１０４】
演算回数測定部２１０は、次元ごとに、個別演算部１６０において所定の演算を行った回数と、打ち切り判定によって演算が行われなかった回数を測定する。選択方法決定部２２０は、各次元について、個別演算部１６０において所定の演算を行った回数や当該回数のベクトルデータ数に対する割合をもとに、演算方法選択部１４０による選択方法（一括演算部１５０、個別演算部１６０のどちらを選択するか）を決定する。例えば、選択方法決定部２２０は、ある次元について、演算を行った回数や割合が多い場合（所定値以上の場合）は、その次元に対して一括演算部１５０を選択するように演算方法選択部１４０に指示する。
【０１０５】
ある次元に対する演算が個別演算部１６０で行われる割合が多いということは、当該次元に対する演算を一括演算部１５０で行っても無駄が少ないことを示している。したがって、この場合、当該次元に対する演算を、一括演算部１５０を用いて行うことで、照合処理をより高速化できる。
【０１０６】
次に、本発明の第３の実施の形態の具体例を説明する。
【０１０７】
図１７は、本発明の第３の実施の形態における、照合装置１００のプログラムの例である。図１７の例では、個別演算部１６０による演算回数がＣ回以上の次元に対して、一括演算部１５０を選択するように、選択方法が決定される（行番号２５〜２８）。
【０１０８】
なお、演算回数測定部２１０は、個別演算部１６０において演算を行った回数の代わりに、一括演算部１５０において無駄な演算が行われた回数を、次元ごとに測定してもよい。この場合、選択方法決定部２２０は、一括演算部１５０において無駄な演算が行われた割合が多い次元に対して、個別演算部１６０を選択するように、演算方法選択部１４０に指示する。
【０１０９】
また、一括演算部１５０や個別演算部１６０において演算を行った回数の代わりに、一括演算部１５０や個別演算部１６０における演算時間を用いて、演算方法選択部１４０による選択方法を決定してもよい。
【０１１０】
図１８は、本発明の第３の実施の形態における、照合装置１００の他の構成を示すブロック図である。
【０１１１】
図１８の照合装置１００は、演算回数測定部２１０の代わりに、時間測定部２１１を含む。時間測定部２１１は、一括演算部１５０、及び、個別演算部１６０の処理時間を、次元ごとに測定する。選択方法決定部２２０は、各次元について、一括演算部１５０、及び、個別演算部１６０の処理時間をもとに、演算方法選択部１４０による選択方法を決定する。例えば、選択方法決定部２２０は、ある次元の選択方法を個別演算部１６０から一括演算部１５０に変更したことにより処理時間が長くなった場合、当該選択方法を、再び、個別演算部１６０に戻す。
【０１１２】
本発明の第３の実施の形態によれば、本発明の第１の実施の形態に比べて、照合処理をさらに高速化できる。その理由は、選択方法決定部２２０が、各次元について、個別演算部１６０において所定の演算を行った回数や割合をもとに、演算方法選択部１４０による選択方法を決定するためである。
【０１１３】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１１４】
例えば、本発明の実施の形態では、情報処理装置が、ベクトルデータに対する処理として、ベクトルデータ間の照合を行う場合を例に説明を行った。しかしながら、複数次元ベクトルデータの各々の各次元に係る所定演算を複数のベクトルデータに対して行う処理であれば、ベクトルデータに対する処理は、照合以外の他の処理でもよい。
【０１１５】
この出願は、２０１４年６月１９日に出願された日本出願特願２０１４−１２５８６４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１１６】
本発明は、画像検索システム等、特徴ベクトルを用いたデータベースとの照合に用いることができる。
【符号の説明】
【０１１７】
１００    照合装置
１０１    ＣＰＵ
１０２    記憶手段
１０３    通信手段
１０４    入力手段
１０５    出力手段
１１０    データ入力部
１２０    対象データ格納部
１３０    データ集合格納部
１４０    演算方法選択部
１５０    一括演算部
１５１    次元制御部
１５２    集合内データ制御部
１５３    複数要素演算部
１６０    個別演算部
１６１    次元制御部
１６２    集合内データ制御部
１６３    打ち切り判定部
１６４    単要素演算部
１６５    集合内データ制御部
１６６    打ち切り判定部
１６７    次元制御部
１６８    打ち切り判定部
１６９    単要素演算部
１７０    距離格納部
１８０    結果格納部
１９０    結果出力部
２１０    演算回数測定部
２１１    時間測定部
２２０    選択方法決定部
【図１】
2015194132.tif 000003
【図２】
2015194132.tif 000004
【図３】
2015194132.tif 000005
【図４】
2015194132.tif 000006
【図５】
2015194132.tif 000007
【図６】
2015194132.tif 000008
【図７】
2015194132.tif 000009
【図８】
2015194132.tif 000010
【図９】
2015194132.tif 000011
【図１０】
2015194132.tif 000012
【図１１】
2015194132.tif 000013
【図１２】
2015194132.tif 000014
【図１３】
2015194132.tif 000015
【図１４】
2015194132.tif 000016
【図１５】
2015194132.tif 000017
【図１６】
2015194132.tif 000018
【図１７】
2015194132.tif 000019
【図１８】
2015194132.tif 000020
【図１９】
2015194132.tif 000021
【図２０】
2015194132.tif 000022
【図２１】
2015194132.tif 000023
【図２２】
2015194132.tif 000024
【図２３】
2015194132.tif 000025
【図２４】
2015194132.tif 000026
【図２５】
2015194132.tif 000027
【図２６】
2015194132.tif 000028
【手続補正書】
【提出日】平成28年11月22日(2016.11.22)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行う情報処理装置であって、
前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により行う一括演算手段と、
前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて行う個別演算手段と、
を備えた情報処理装置。
【請求項２】
前記特定次元は、前記複数次元の内の、前記所定演算が行われる順番が所定値以下の次元である、
請求項１に記載の情報処理装置。
【請求項３】
さらに、前記一括演算手段、及び、前記個別演算手段の内の少なくとも一方における、前記所定演算の実行状況に応じて、前記特定次元を決定する次元決定手段を備えた、
請求項１または２に記載の情報処理装置。
【請求項４】
前記次元決定手段は、前記特定次元以外の一の次元について、前記個別演算手段において前記所定演算が行われた回数または割合が所定値以上の場合、当該一の次元を前記特定次元に含める、
請求項３に記載の情報処理装置。
【請求項５】
前記所定演算は、ベクトルデータ間の各次元の差分、及び、差分の累積値の計算を含み、
前記個別演算手段は、前記所定の条件として、前記差分の累積値が所定の打ち切り閾値未満のベクトルデータについて、前記所定演算を行う、
請求項１乃至４のいずれかに記載の情報処理装置。
【請求項６】
複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行うベクトルデータ処理方法であって、
前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により実行する一括演算処理を行い、
前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて実行する個別演算処理を行う、
ベクトルデータ処理方法。
【請求項７】
前記特定次元は、前記複数次元の内の、前記所定演算が行われる順番が所定値以下の次元である、
請求項６に記載のベクトルデータ処理方法。
【請求項８】
さらに、前記一括演算処理、及び、前記個別演算処理の内の少なくとも一方における、前記所定演算の実行状況に応じて、前記特定次元を決定する、
請求項６または７に記載のベクトルデータ処理方法。
【請求項９】
前記特定次元以外の一の次元について、前記個別演算処理において前記所定演算が行われた回数または割合が所定値以上の場合、当該一の次元を前記特定次元に含める、
請求項８に記載のベクトルデータ処理方法。
【請求項１０】
複数次元を有するベクトルデータの各々の各次元に係る所定演算を、複数のベクトルデータに対して行うコンピュータのプログラムを格納する記録媒体であって、
前記コンピュータに、
前記複数次元の内の特定次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の異なるベクトルデータに対するベクトル演算により行い、
前記特定次元以外の次元の各々に係る前記所定演算を、前記複数のベクトルデータの内の、所定の条件を満たすベクトルデータについて行う、
処理を実行させるプログラム。
【国際調査報告】
2015194132.tif 000029
2015194132.tif 000030