(57)【特許請求の範囲】
【請求項１】
画像の高次元特徴の類似性を比較するための方法において、
局所性鋭敏型ハッシュ（ＬＳＨ）アルゴリズムによって前記画像の抽出された固有ベクトルの次元を低減して、低次元固有ベクトルを取得するステップと、
前記低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立するステップと、
クエリされた画像の前記セグメント化された低次元固有ベクトルを前記セグメント索引テーブルから検索して、候補サンプル集合を取得するステップと、
（Ａ）前記クエリされた画像の前記低次元固有ベクトルと（Ｂ）前記候補サンプル集合における各サンプルとの間の類似性メトリックを実施するステップであり、各サンプルは対応する低次元固有ベクトルである、ステップと、
を含み、
クエリされた画像の前記セグメント化された低次元固有ベクトルを前記セグメント索引テーブルから検索して、候補サンプル集合を取得する前記ステップが、
前記クエリされた画像の前記セグメント化された低次元固有ベクトルのエントリアドレスにアクセスして、競合集合を取得するステップと、
前記クエリされた画像の前記セグメント化された低次元固有ベクトルのフィンガープリントと同じフィンガープリントを有する、前記競合集合のノードに対応する前記低次元固有ベクトルを候補集合として抽出するステップと、
それぞれのセグメント検索によって取得した前記候補集合を組み合わせ、重複した低次元固有ベクトルをそれから除去して、候補サンプル集合を取得するステップと、
を含むことを特徴とする、方法。
【請求項２】
前記画像の固有ベクトルが、深層学習技法を使用して構築されたニューラルネットワークを用いて抽出されることを特徴とする、請求項１に記載の方法。
【請求項３】
前記ニューラルネットワークが、畳み込みニューラルネットワークであることを特徴とする、請求項２に記載の方法。
【請求項４】
前記低次元固有ベクトルを平均的にセグメント化するステップの前に、
より小さい検証集合により最適セグメント長を実験的に決定するステップをさらに含むことを特徴とする、請求項１に記載の方法。
【請求項５】
前記低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立する前記ステップが、
前記低次元固有ベクトルを平均的にセグメント化し、前記セグメント化された固有ベクトルを索引項目として使用し、前記索引項目のそれぞれのフィンガープリントを計算するステップと、
前記セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いて前記フィンガープリントに対する剰余演算を実施して、前記索引項目に対するエントリアドレスを取得するステップと、
前記取得したエントリアドレスに応じて前記低次元固有ベクトルを前記セグメント索引テーブルに挿入して、前記セグメント索引テーブルを確立するステップと、
を含むことを特徴とする、請求項１に記載の方法。
【請求項６】
（Ａ）前記クエリされた画像の前記低次元固有ベクトルと（Ｂ）前記候補サンプル集合における各サンプルとの間の類似性メトリックを実施する前記ステップが、
前記クエリされた画像の前記低次元固有ベクトルと前記候補サンプル集合における各サンプルとの間のマンハッタン距離のスコアを計算するステップと、
前記スコアを昇順によりソートし、前記クエリされた画像の類似画像として所定の数の最上位スコアを有する前記サンプルに対応する画像を選ぶステップと、
を含むことを特徴とする、請求項１に記載の方法。
【請求項７】
画像の高次元特徴の類似性を比較するためのデバイスにおいて、
ＬＳＨアルゴリズムによって前記画像の抽出された固有ベクトルの次元を低減して、低次元固有ベクトルを取得するための特徴次元低減モジュールと、
前記低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立するためのセグメント索引作成モジュールと、
クエリされた画像の前記セグメント化された低次元固有ベクトルを前記セグメント索引テーブルから検索して、候補サンプル集合を取得するための類似性クエリモジュールと、
（Ａ）前記クエリされた画像の前記低次元固有ベクトルと（Ｂ）前記候補サンプル集合における各サンプルとの間の類似性メトリックを実施するための比較メトリックモジュールであり、各サンプルは対応する低次元固有ベクトルである、比較メトリックモジュールとを含み、
前記類似性クエリモジュールが、さらに、
前記クエリされた画像の前記セグメント化された低次元固有ベクトルのエントリアドレスにアクセスして、競合集合を取得することと、
前記クエリされた画像の前記セグメント化された低次元固有ベクトルのフィンガープリントと同じフィンガープリントを有する、前記競合集合のノードに対応する前記低次元固有ベクトルを候補集合として抽出することと、
それぞれのセグメント検索によって取得した前記候補集合を組み合わせ、重複した低次元固有ベクトルをそれから除去して、候補サンプル集合を取得することと、
を行うことを特徴する、デバイス。
【請求項８】
前記画像の固有ベクトルが、深層学習技法を使用して構築されたニューラルネットワークを用いて抽出されることを特徴とする、請求項７に記載のデバイス。
【請求項９】
前記ニューラルネットワークが、畳み込みニューラルネットワークであることを特徴とする、請求項８に記載のデバイス。
【請求項１０】
前記低次元固有ベクトルを平均的にセグメント化するステップの前に、前記セグメント索引作成モジュールが、さらに、
より小さい検証集合により最適セグメント長を実験的に決定することを特徴とする、請求項７に記載のデバイス。
【請求項１１】
前記セグメント索引作成モジュールが、さらに、
前記低次元固有ベクトルを平均的にセグメント化し、前記セグメント化された固有ベクトルを索引項目として使用し、前記索引項目のそれぞれのフィンガープリントを計算することと、
前記セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いて前記フィンガープリントに対する剰余演算を実施して、前記索引項目に対するエントリアドレスを取得することと、
前記取得したエントリアドレスに応じて前記低次元固有ベクトルを前記セグメント索引テーブルに挿入して、前記セグメント索引テーブルを確立することと、
を行うことを特徴とする、請求項７に記載のデバイス。
【請求項１２】
前記比較メトリックモジュールが、さらに、
前記クエリされた画像の前記低次元固有ベクトルと前記候補サンプル集合における各サンプルとの間のマンハッタン距離のスコアを計算することと、
前記スコアを昇順によりソートし、前記クエリされた画像の類似画像として所定の数の最上位スコアを有する前記サンプルに対応する画像を選ぶことと、
を行うことを特徴とする、請求項７に記載のデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、コンピュータの技術分野に関し、詳細には、画像の高次元特徴の類似性を比較するための方法及びデバイスに関する。
【背景技術】
【０００２】
今日のインターネット環境において、インターネットユーザは、テキスト検索の必要性に加えて、音声、画像及び動画などのマルチメディアコンテンツも検索したいと思っている。画像検索に関しては、ユーザは、自分自身がクエリするために提供した画像に類似した候補画像の集合をインターネットサービスプロバイダが見つけ出すことを期待している。該当するシナリオの例には、ユーザによって提供された商品画像に基づく同じ又は類似のスタイルの商品を推奨する電子商取引企業、ユーザによって提供された風景画像により類似画像を表示する検索サイトなどが含まれる。
【０００３】
従来の画像検索は、手動で指定された画像特徴に基づく類似性メトリックを実施することによって一般に行われる。画像データの意味的に非構造化された特性により、代表的特徴を手動で発見することは困難である。Ｈｉｎｔｏｎらによって提案されたニューラルネットワークのための深層学習の技法により、特徴抽出、すなわち、自己学習による、原画像の高次元固有ベクトル空間から低次元固有ベクトル空間への効率的なマッピングが可能となり、それにより、画像フィールドにおける特徴表現の効率が大幅に改善される。
【０００４】
インターネット産業において、サービス会社は、しばしば、大量の画像を保管している。検索結果を第２レベルの応答時間内で取得する必要がある場合、ユーザからの検索の必要性に関しては、大規模な並列計算技術を使用することに加えて、次元縮小、索引作成、及び照合アルゴリズムの速度を増加させることも必要である。局所性鋭敏型ハッシュ（ＬＳＨ：Ｌｏｃａｌｉｔｙ  Ｓｅｎｓｉｔｉｖｅ  Ｈａｓｈ）アルゴリズムは、一種の次元縮小コーディング技法であり、それは生成されたハッシュコードにおいて相対位置を元の固有ベクトル空間に保持することを特徴とし、したがって、画像の迅速検索に使用することができる。
【０００５】
従来技術において、画像検索のためのＬＳＨアルゴリズムは、以下のステップを主に含む。
【０００６】
１．画像のＬＳＨコーディング
画像のＬＳＨコーディングのプロセスを図１に示す。原画像は、ＲＧＢチャンネルのｎ次元ベクトルとして表され、次いで、畳み込みニューラルネットワーク（ＣＮＮ）によってｎ次元ベクトルをコード化することにより取得した隠れ層の出力（通常、最後から２番目の層から、最下部から１４番目の層までの）は、画像のｍ次元固有ベクトルと解釈される（次元の典型的な長さは４０９６である）。次いで、固有ベクトルは、ｍ次元固有ベクトルにＬＳＨベクトル演算の集合を適用した後、ｋ次元（ｋはｍよりもずっと小さい）ＬＳＨコードに変換される。この方法によれば、サービス企業は、画像のすべてをそのようなコードに変換し、次いで、その後の画像の類似性検索がそのような画像表現に基づいて行われる。
【０００７】
２．画像の類似性検索
画像の類似性検索のプロセスを図２に示す。まず、クエリするためにユーザによってアップロードされた画像のＬＳＨコード（ベクトルＡ）が前述のステップ１を通して取得され、次いで、ＬＳＨベクトルテーブルにおける各ベクトル（ベクトルＢ）に対して、ベクトルＡとＢとの間のハミング距離が計算される。続いて、ベクトルは、計算された距離により昇順でソートされ、最後に、いくつかの最上位ベクトルに対応する原画像が類似性検索の結果としてユーザに返される。
【０００８】
しかし、既存のＬＳＨアルゴリズムを画像検索方法に適用することは、使用の際に以下の不利点を有する。
１．ＬＳＨコーディングに基づく類似性検索の速度が、画像の集合が相対的に大きい（例えば、数百万、数千万以上の画像を含む）場合に依然として相対的に遅い。
２．計算速度の適切な観点から、ハミング距離メトリックは、ユークリッド距離メトリック及びマンハッタン距離メトリックなどよりも速いが、その精度はかなり低下し、検索結果は不満足である。
【発明の概要】
【０００９】
この点から見て、本発明は、画像の高次元特徴の類似性を比較するための方法及びデバイスを提供する。画像のセグメント索引作成及びセグメント検索ＬＳＨコードの方法によって、並びにマンハッタン距離を類似性メトリックに適用することによって、検索速度及び検索精度は、ＬＳＨコーディングに基づく大量画像からの類似性検索において改善される。
【００１０】
上記の目的を達成するために、本発明の一態様により、画像の高次元特徴の類似性を比較するための方法が提供される。
【００１１】
本発明による画像の高次元特徴の類似性を比較するための方法は、局所性鋭敏型ハッシュ（ＬＳＨ）アルゴリズムによって画像の抽出された固有ベクトルの次元を低減して、低次元固有ベクトルを取得するステップと、低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立するステップと、クエリされた画像のセグメント化された低次元固有ベクトルをセグメント索引テーブルから検索して、候補サンプル集合を取得するステップと、クエリされた画像の低次元固有ベクトルと候補サンプル集合における各サンプルとの間の類似性メトリックを実施するステップと、を含む。
【００１２】
任意選択で、画像の固有ベクトルは、深層学習技法を使用して構築されたニューラルネットワークを用いて抽出される。
【００１３】
任意選択で、ニューラルネットワークは、畳み込みニューラルネットワークである。
【００１４】
任意選択で、低次元固有ベクトルを平均的にセグメント化するステップの前に、方法は、より小さい検証集合による最適セグメント長を実験的に決定するステップをさらに含む。
【００１５】
任意選択で、低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立するステップは、低次元固有ベクトルを平均的にセグメント化し、セグメント化された固有ベクトルを索引項目として使用し、索引項目のそれぞれのフィンガープリントを計算するステップと、セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いてフィンガープリントに対する剰余演算を実施して、索引項目に対するエントリアドレスを取得するステップと、取得したエントリアドレスに応じて低次元固有ベクトルをセグメント索引テーブルに挿入して、セグメント索引テーブルを確立するステップとを含む。
【００１６】
任意選択で、クエリされた画像のセグメント化された低次元固有ベクトルをセグメント索引テーブルから検索して、候補サンプルの集合を取得するステップは、クエリされた画像のセグメント化された低次元固有ベクトルのエントリアドレスにアクセスして、競合集合を取得するステップと、クエリされた画像のセグメント化された低次元固有ベクトルのフィンガープリントと同じフィンガープリントを有する、競合集合のノードに対応する低次元固有ベクトルを候補集合として抽出するステップと、それぞれのセグメント検索によって取得した候補集合を組み合わせ、重複した低次元固有ベクトルをそれから除去して、候補サンプル集合を取得するステップとを含む。
【００１７】
任意選択で、クエリされた画像の低次元固有ベクトルと候補サンプル集合における各サンプルとの間の類似性メトリックを実施するステップは、クエリされた画像の低次元固有ベクトルと候補サンプル集合における各サンプルとの間のマンハッタン距離のスコアを計算するステップと、スコアを昇順によりソートし、クエリされた画像の類似画像として所定の数の最上位スコアを有するサンプルに対応する画像を選ぶステップとを含む。
【００１８】
本発明の別の態様によれば、画像の高次元特徴の類似性を比較するためのデバイスが提供される。
【００１９】
本発明による、画像の高次元特徴の類似性を比較するためのデバイスが、ＬＳＨアルゴリズムによって画像の抽出された固有ベクトルの次元を低減して、低次元固有ベクトルを取得するための特徴次元低減モジュールと、低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立するためのセグメント索引作成モジュールと、クエリされた画像のセグメント化された低次元固有ベクトルをセグメント索引テーブルから検索して、候補サンプル集合を取得するための類似性クエリモジュールと、クエリされた画像の低次元固有ベクトルと候補サンプル集合における各サンプルとの間の類似性メトリックを実施するための比較メトリックモジュールとを備える。
【００２０】
任意選択で、画像の固有ベクトルは、深層学習技法を使用して構築されたニューラルネットワークを用いて抽出される。
【００２１】
任意選択で、ニューラルネットワークは、畳み込みニューラルネットワークである。
【００２２】
任意選択で、低次元固有ベクトルを平均的にセグメント化するステップの前に、セグメント索引作成モジュールは、さらに、より小さい検証集合により最適セグメント長を実験的に決定する。
【００２３】
任意選択で、セグメント索引作成モジュールは、さらに、低次元固有ベクトルを平均的にセグメント化し、セグメント化された固有ベクトルを索引項目として使用し、索引項目のそれぞれのフィンガープリントを計算することと、セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いてフィンガープリントに対する剰余演算を実施して、索引項目に対するエントリアドレスを取得することと、取得したエントリアドレスに応じて低次元固有ベクトルをセグメント索引テーブルに挿入して、セグメント索引テーブルを確立することとを行う。
【００２４】
任意選択で、類似性クエリモジュールは、さらに、クエリされた画像のセグメント化された低次元固有ベクトルのエントリアドレスにアクセスして、競合集合を取得することと、クエリされた画像のセグメント化された低次元固有ベクトルのフィンガープリントと同じフィンガープリントを有する、競合集合のノードに対応する低次元固有ベクトルを候補集合として抽出することと、それぞれのセグメント検索によって取得した候補集合を組み合わせ、重複した低次元固有ベクトルをそれから除去して、候補サンプル集合を取得することとを行う。
【００２５】
任意選択で、比較メトリックモジュールは、さらに、クエリされた画像の低次元固有ベクトルと候補サンプル集合における各サンプルとの間のマンハッタン距離のスコアを計算することと、スコアを昇順によりソートし、クエリされた画像の類似画像として所定の数の最上位スコアを有するサンプルに対応する画像を選ぶこととを行う。
【００２６】
本発明の技術的解決策によれば、画像のＬＳＨコードの次元低減された固有ベクトルに対するセグメント索引を確立することによって、検索速度を速めて、検索効率を改善することができる。画像の類似性検索において、従来のハミング距離メトリックの代わりにマンハッタン距離メトリックを使用することによって、ＬＳＨコードに含まれる定量化可能な距離情報を十分に利用して、セグメント検索における検索精度を改善することができる。
【図面の簡単な説明】
【００２７】
図面は、本発明をよりよく理解するためであり、本発明の不適切な限定を構成しない。
【図１】従来技術における画像のＬＳＨコードを生成するプロセスの概略図である。
【図２】従来技術における画像類似性検索プロセスの概略図である。
【図３】本発明の実施形態による、画像の高次元特徴の類似性を比較するための方法の主要ステップの概略図である。
【図４】本発明の実装形態による、画像のＬＳＨコードを生成し、セグメント索引を確立するプロセスの概略図である。
【図５】本発明の実装形態による、セグメントハッシュ索引テーブルの構造図である。
【図６】本発明の実装形態による、セグメント索引に基づく画像類似性検索プロセスの概略図である。
【図７】本発明の実施形態による、画像の高次元特徴の類似性を比較するためのデバイスの主要モジュールの概略図である。
【好ましい実施形態】
【００２８】
本発明の例示的な実施形態を添付の図面を参照して以下に説明するが、添付の図面には、本発明の実施形態の様々な詳細が理解を容易にするために含まれており、単に例示的であると考えるべきである。したがって、当業者は、本発明の範囲及び精神から逸脱することなく様々な変更及び修正を本明細書に説明する実施形態に加えることができることを理解する。また、明確及び簡潔にするために、周知の機能及び構成の説明は以下の説明から省略される。
【００２９】
本発明の実装形態を図３〜図６を参照して以下に説明する。図３は、本発明の実施形態による、画像の高次元特徴の類似性を比較するための方法の主要ステップの概略図である。図３に示すように、本発明による、画像の高次元特徴の類似性を比較するための方法は、以下のステップＳ３１〜Ｓ３４を含む。
【００３０】
ステップＳ３１：ＬＳＨアルゴリズムによって画像の抽出された固有ベクトルの次元を低減して、低次元固有ベクトルを取得するステップ。このステップにおける画像の固有ベクトルは、深層学習技法を使用して構築されたニューラルネットワークを用いて抽出してもよい。一般に、使用されるニューラルネットワークは、畳み込みニューラルネットワークＣＮＮである。図４に示すように、本発明の実装形態による、画像のＬＳＨコードを生成し、セグメント索引を確立するプロセスの概略図を次に参照すると、原画像が畳み込みニューラルネットワークＣＮＮを通して抽出する特徴を受けて、ＣＮＮのｍ次元固有ベクトルを取得する。続いて、ｍ次元固有ベクトルは、ＬＳＨを通して次元低減を受けて、より低い（例えば、ｍよりもずっと小さいｋ）次元の固有ベクトルのＬＳＨコードを取得する。
【００３１】
ステップＳ３２：低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立するステップ。ＬＳＨコードを平均的にセグメント化し、セグメント索引を確立するステップの前に、最適セグメント長をより小さい検証集合により実験的に決定してもよい、したがって、本発明の技術的解決策は、検索速度と検索精度との相対的に満足すべき妥協点を取得する。続いて、ＬＳＨコードの低次元ベクトルが、決定された最適セグメント長ｄにより、平均的にセグメント化される。例として、１００１と番号付けされたサンプルのＬＳＨコードは、
［０，１，１，０，０，３，１，０，１，０，２，１，０，１，２，１，１，０，１，−１，２，１，０，１，１，１，０，０］
である。
【００３２】
最適セグメント長ｄが７である場合、それは４つのセグメントに分割する必要があり、取得したセグメント索引項目は、
１［０，１，１，０，０，３，１］，２［０，１，０，２，１，０，１］，３［２，１，１，０，１，−１，２］，４［１，０，１，１，１，０，０］
である。各セグメントの前の数は、最初のセグメントが１であり、２番目のセグメントが２であるなどの位置決め番号を表す。
【００３３】
ＬＳＨコードの低次元固有ベクトルが平均的にセグメント化された後、セグメントハッシュ索引テーブルが低次元固有ベクトルのためにメモリ内に確立される。主要ステップは以下のようにまとめることができる。
ステップＳ３２１：低次元固有ベクトルを平均的にセグメント化し、セグメント化された固有ベクトルを索引項目として使用し、索引項目のそれぞれのフィンガープリントを計算するステップ、
ステップＳ３２２：セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いてフィンガープリントに対する剰余演算を実施して、索引項目に対するエントリアドレスを取得するステップ、及び
ステップＳ３２３：取得したエントリアドレスに応じて低次元固有ベクトルをセグメント索引テーブルに挿入して、セグメント索引テーブルを確立するステップ。
【００３４】
図５に示す、本発明の実装形態による、セグメント化されたハッシュ索引テーブルの構造図を参照すると、前述の１００１と番号付けされたサンプルが、説明のための例として挙げられる。サンプルが４つのセグメントに分割された後、セグメント化された固有ベクトルは、索引項目として使用され、各セグメント索引項目のフィンガープリントが計算される。例えば、各索引項目のフィンガープリントは、メッセージダイジェストアルゴリズムの第５世代（すなわち、ＭＤ５関数）を用いて計算することによって取得することができる。次いで、セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いてこれらのフィンガープリントに対する剰余演算を実施して、索引項目のそれぞれに対するエントリアドレスを取得する。セグメント索引テーブルのエントリＮの数は、必要に応じて、例えば、マシンのメモリのサイズ又は機能を実現するための要件などにより設定してもよい。実際には、セグメント索引項目の数が大きいので、索引項目のエントリアドレスは、重複することがあり、これは一般に「主要競合」と呼ばれる。主要競合を有する索引項目は、競合集合の連結リストの形で保存される。最後に、ＬＳＨコードの低次元固有ベクトルは、取得したエントリアドレスに応じてセグメント索引テーブルに挿入されて、セグメント索引テーブルを確立する。
【００３５】
上記のステップＳ３１及びＳ３２を通して、本発明の実装形態による、画像のＬＳＨコードを生成し、セグメント索引を確立するプロセスを実施することができる。セグメント索引に基づく画像類似性検索プロセスを添付の図面を参照して以下に説明する。
【００３６】
ステップＳ３３：クエリされた画像のセグメント化された低次元固有ベクトルをセグメント索引テーブルから検索して、候補サンプル集合を取得するステップ。類似画像検索プロセスは、以下のステップに基づいて実装してもよい。
ステップＳ３３１：クエリされた画像のセグメント化された低次元固有ベクトルのエントリアドレスにアクセスして、競合集合を取得するステップ、
ステップＳ３３２：クエリされた画像のセグメント化された低次元固有ベクトルのフィンガープリントと同じフィンガープリントを有する、競合集合のノードに対応する低次元固有ベクトルを候補集合として抽出するステップ、及び
ステップＳ３３３：セグメント検索でそれぞれ検索することによって取得した候補集合を組み合わせ、重複した低次元固有ベクトルをそれから除去して、候補サンプル集合を取得するステップ。
【００３７】
図５に示すセグメントハッシュ索引テーブルの構造を参照すると、候補サンプル集合に対する検索するプロセスが、前述の１００１と番号付けされたサンプルを例として挙げることによって紹介される。例えば、ステップＳ３３１では、まず、各セグメント索引項目のフィンガープリントを計算して、索引テーブル内で各セグメント索引項目のエントリアドレスＳを見つけ、競合集合の対応する連結リストをエントリアドレスＳにアクセスすることによって取得する。競合集合の連結リスト内の各ノードの右向きのポインタは、競合集合の連結リストを示すのに使用され、下向きのポインタは、候補集合の連結リストを示すのに使用される。いわゆる候補集合は、ノードのセグメント索引項目に対応する候補サンプル集合用であり、それは特定の距離比較を受け、ノードの「セグメントＬＳＨコード」（セグメント索引項目）のフィンガープリントは、あるクエリされた画像のセグメント索引項目のフィンガープリントと同じである。本明細書における候補サンプルは、対応する低次元固有ベクトルである。ステップＳ３３２で述べたように、候補集合が抽出される。最後に、ステップＳ３３３で述べたように、すべてのセグメント検索が完了した後、すべての取得した候補集合は組み合わされ、重複した低次元固有ベクトルは、距離比較のための候補サンプル集合を最終的に取得するために除去される。
【００３８】
ステップＳ３４：クエリされた画像の低次元固有ベクトルと候補サンプル集合における各サンプルとの間の類似性メトリックを実施するステップ。類似性メトリックにおいて、まず、クエリされた画像の低次元固有ベクトルと候補サンプル集合内の各サンプルとの間のマンハッタン距離のスコアが計算され、スコアは昇順によりソートされ、所定の数の最上位スコアを有するサンプルに対応する画像が、クエリされた画像の類似画像として選ばれる。
【００３９】
マンハッタン距離原理によれば、スコアが小さければ小さいほど、類似性が高くなる。したがって、計算されたマンハッタン距離スコアに基づいて、類似性を比較し、ソートすることができる。実際には、表示される類似画像の数は、適用例の必要性に応じてあらかじめ設定してもよいし、又はユーザ自身によって選択してもよい。
【００４０】
図６に示す、本発明の実装形態による、セグメント索引に基づく画像類似性検索のプロセスは、上記のステップＳ３３及びステップＳ３４を通して実装することができる。すなわち、クエリされた画像の低次元固有ベクトルと、セグメントＬＳＨコードのベクトル集合の各１つとの類似性は、それぞれセグメント索引及びマンハッタン距離に基づいて判別される。最後に、類似のＬＳＨコードを有するレコードの集合が、対応する類似画像を得るために取得される。
【００４１】
本発明の技術的解決策は、上記のステップＳ３１〜Ｓ３４を通して実装することができる。実験を通して、１００万の画像の集合に関しては、５１２ビットのＬＳＨコードが、畳み込みニューラルネットワークの最下部から３番目の層の固有ベクトルから取得される。画像類似性検索に関して２４ビットのセグメント長ｄが選ばれ、索引が確立された場合、検索速度は、セグメントなしの直接一対比較よりも約１０００倍速い。すなわち、セグメント索引を用いた検索速度は、元のＬＳＨコードに直接基づく比較に対して大幅に改善されている。さらに、ＬＳＨコードが定量化可能な距離情報を含むので、マンハッタン距離が類似性メトリックに使用されるとき、距離情報を十分に利用することができるが、その一方で、ハミング距離は、桁の均等性を比較するのより適切である。したがって、マンハッタン距離に基づく類似性メトリックの検索精度は、ハミング距離に基づく類似性メトリックの検索精度よりも高い。数多くの実験データがその検索精度が約５％高いことを示している。
【００４２】
図７は、本発明の実施形態による、画像の高次元特徴の類似性を比較するためのデバイスの主要モジュールの概略図である。図７に示すように、本発明の実施形態における画像の高次元特徴の類似性を比較するためのデバイス７０は、特徴次元低減モジュール７１と、セグメント索引作成モジュール７２と、類似性クエリモジュール７３と、比較メトリックモジュール７４とを主に備える。
【００４３】
特徴次元低減モジュール７１は、ＬＳＨアルゴリズムによって画像の抽出された固有ベクトルの次元を低減して、低次元固有ベクトルを取得する。
【００４４】
セグメント索引作成モジュール７２は、低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立する。低次元固有ベクトルを平均的にセグメント化するステップの前に、セグメント索引作成モジュール７２は、さらに、より小さい検証集合による最適セグメント長を実験的に決定する。
【００４５】
セグメント索引作成モジュール７２は、さらに、低次元固有ベクトルを平均的にセグメント化し、セグメント化された固有ベクトルを索引項目として使用し、索引項目のそれぞれのフィンガープリントを計算することと、セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いてフィンガープリントに対する剰余演算を実施して、索引項目に対するエントリアドレスを取得することと、取得したエントリアドレスに応じて低次元固有ベクトルをセグメント索引テーブルに挿入して、セグメント索引テーブルを確立することとを行う。
【００４６】
類似性クエリモジュール７３は、クエリされた画像のセグメント化された低次元固有ベクトルをセグメント索引テーブルから検索して、候補サンプル集合を取得する。
【００４７】
類似性クエリモジュール７３は、さらに、クエリされた画像のセグメント化された低次元固有ベクトルのエントリアドレスにアクセスして、競合集合を取得することと、クエリされた画像のセグメント化された低次元固有ベクトルのフィンガープリントと同じフィンガープリントを候補集合として有する競合集合のノードに対応する低次元固有ベクトルを抽出することと、それぞれのセグメント検索によって取得した候補集合を組み合わせ、重複した低次元固有ベクトルをそれから除去して、候補サンプル集合を取得することとを行う。
【００４８】
比較メトリックモジュール７４は、クエリされた画像の低次元固有ベクトルと候補サンプル集合における各サンプルとの間の類似性メトリックを実施する。
【００４９】
比較メトリックモジュール７４は、さらに、クエリされた画像の低次元固有ベクトルと候補サンプル集合における各サンプルとの間のマンハッタン距離のスコアを計算することと、スコアを昇順によりソートし、クエリされた画像の類似画像として所定の数の最上位スコアを有するサンプルに対応する画像を選ぶこととを行う。
【００５０】
本発明の実施形態の技術的解決策によれば、画像のＬＳＨコードの次元低減された固有ベクトルのセグメント索引を確立することによって、検索速度を速めて、検索効率を改善することができる。画像の類似性検索において、従来のハミング距離メトリックの代わりにマンハッタン距離メトリックを使用することによって、ＬＳＨコードに含まれる定量化可能な距離情報を十分に利用して、セグメント検索における検索精度を改善することができる。
【００５１】
さらに、本発明の技術的解決策におけるセグメント索引を確立するプロセスは、１つのマシンで実施されることに限定しなくてもよく、分散スケジューリングシステムにおいて並列に実行してもよい。このように、より大きな規模におけるデータを処理することができる。
【００５２】
上記の具体的な実装形態は、本発明の保護範囲に対するいかなる限定も構成しない。当業者は、様々な変更、組合せ、部分的組合せ、及び改変を設計要件及び他の要因に応じて行ってよいことを理解するはずである。本発明の精神及び原理内で行われる任意の変更、同等の交換、改善などは、本発明の保護範囲に含めるべきである。
［発明の項目］
［項目１］
画像の高次元特徴の類似性を比較するための方法において、
局所性鋭敏型ハッシュ（ＬＳＨ）アルゴリズムによって前記画像の抽出された固有ベクトルの次元を低減して、低次元固有ベクトルを取得するステップと、
前記低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立するステップと、
クエリされた画像の前記セグメント化された低次元固有ベクトルを前記セグメント索引テーブルから検索して、候補サンプル集合を取得するステップと、
前記クエリされた画像の前記低次元固有ベクトルと前記候補サンプル集合における各サンプルとの間の類似性メトリックを実施するステップと、
を含むことを特徴とする、方法。
［項目２］
前記画像の固有ベクトルが、深層学習技法を使用して構築されたニューラルネットワークを用いて抽出されることを特徴とする、項目１に記載の方法。
［項目３］
前記ニューラルネットワークが、畳み込みニューラルネットワークであることを特徴とする、項目２に記載の方法。
［項目４］
前記低次元固有ベクトルを平均的にセグメント化するステップの前に、
より小さい検証集合により最適セグメント長を実験的に決定するステップをさらに含むことを特徴とする、項目１に記載の方法。
［項目５］
前記低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立する前記ステップが、
前記低次元固有ベクトルを平均的にセグメント化し、前記セグメント化された固有ベクトルを索引項目として使用し、前記索引項目のそれぞれのフィンガープリントを計算するステップと、
前記セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いて前記フィンガープリントに対する剰余演算を実施して、前記索引項目に対するエントリアドレスを取得するステップと、
前記取得したエントリアドレスに応じて前記低次元固有ベクトルを前記セグメント索引テーブルに挿入して、前記セグメント索引テーブルを確立するステップと、
を含むことを特徴とする、項目１に記載の方法。
［項目６］
クエリされた画像の前記セグメント化された低次元固有ベクトルを前記セグメント索引テーブルから検索して、候補サンプル集合を取得する前記ステップが、
前記クエリされた画像の前記セグメント化された低次元固有ベクトルのエントリアドレスにアクセスして、競合集合を取得するステップと、
前記クエリされた画像の前記セグメント化された低次元固有ベクトルのフィンガープリントと同じフィンガープリントを有する、前記競合集合のノードに対応する前記低次元固有ベクトルを候補集合として抽出するステップと、
それぞれのセグメント検索によって取得した前記候補集合を組み合わせ、重複した低次元固有ベクトルをそれから除去して、候補サンプル集合を取得するステップと、
を含むことを特徴とする、項目１に記載の方法。
［項目７］
前記クエリされた画像の前記低次元固有ベクトルと前記候補サンプル集合における各サンプルとの間の類似性メトリックを実施する前記ステップが、
前記クエリされた画像の前記低次元固有ベクトルと前記候補サンプル集合における各サンプルとの間のマンハッタン距離のスコアを計算するステップと、
前記スコアを昇順によりソートし、前記クエリされた画像の類似画像として所定の数の最上位スコアを有する前記サンプルに対応する画像を選ぶステップと、
を含むことを特徴とする、項目１に記載の方法。
［項目８］
画像の高次元特徴の類似性を比較するためのデバイスにおいて、
ＬＳＨアルゴリズムによって前記画像の抽出された固有ベクトルの次元を低減して、低次元固有ベクトルを取得するための特徴次元低減モジュールと、
前記低次元固有ベクトルを平均的にセグメント化し、セグメント索引テーブルを確立するためのセグメント索引作成モジュールと、
クエリされた画像の前記セグメント化された低次元固有ベクトルを前記セグメント索引テーブルから検索して、候補サンプル集合を取得するための類似性クエリモジュールと、
前記クエリされた画像の前記低次元固有ベクトルと前記候補サンプル集合における各サンプルとの間の類似性メトリックを実施するための比較メトリックモジュールとを含むことを特徴する、デバイス。
［項目９］
前記画像の固有ベクトルが、深層学習技法を使用して構築されたニューラルネットワークを用いて抽出されることを特徴とする、項目８に記載のデバイス。
［項目１０］
前記ニューラルネットワークが、畳み込みニューラルネットワークであることを特徴とする、項目９に記載のデバイス。
［項目１１］
前記低次元固有ベクトルを平均的にセグメント化するステップの前に、前記セグメント索引作成モジュールが、さらに、
より小さい検証集合により最適セグメント長を実験的に決定することを特徴とする、項目８に記載のデバイス。
［項目１２］
前記セグメント索引作成モジュールが、さらに、
前記低次元固有ベクトルを平均的にセグメント化し、前記セグメント化された固有ベクトルを索引項目として使用し、前記索引項目のそれぞれのフィンガープリントを計算することと、
前記セグメント索引テーブルに含まれる所定の数のエントリに最も近い素数を用いて前記フィンガープリントに対する剰余演算を実施して、前記索引項目に対するエントリアドレスを取得することと、
前記取得したエントリアドレスに応じて前記低次元固有ベクトルを前記セグメント索引テーブルに挿入して、前記セグメント索引テーブルを確立することと、
を行うことを特徴とする、項目８に記載のデバイス。
［項目１３］
前記類似性クエリモジュールが、さらに、
前記クエリされた画像の前記セグメント化された低次元固有ベクトルのエントリアドレスにアクセスして、競合集合を取得することと、
前記クエリされた画像の前記セグメント化された低次元固有ベクトルのフィンガープリントと同じフィンガープリントを有する、前記競合集合のノードに対応する前記低次元固有ベクトルを候補集合として抽出することと、
それぞれのセグメント検索によって取得した前記候補集合を組み合わせ、重複した低次元固有ベクトルをそれから除去して、候補サンプル集合を取得することと、
を行うことを特徴とする、項目８に記載のデバイス。
［項目１４］
前記比較メトリックモジュールが、さらに、
前記クエリされた画像の前記低次元固有ベクトルと前記候補サンプル集合における各サンプルとの間のマンハッタン距離のスコアを計算することと、
前記スコアを昇順によりソートし、前記クエリされた画像の類似画像として所定の数の最上位スコアを有する前記サンプルに対応する画像を選ぶことと、
を行うことを特徴とする、項目８に記載のデバイス。
【図１】
0006544756.tif 000002
【図２】
0006544756.tif 000003
【図３】
0006544756.tif 000004
【図４】
0006544756.tif 000005
【図５】
0006544756.tif 000006
【図６】
0006544756.tif 000007
【図７】
0006544756.tif 000008