特許ウォッチ

公開番号2025104533
公報種別公開特許公報(A)
公開日2025-07-10
出願番号2023222409
出願日2023-12-28
発明の名称情報処理装置、情報処理方法およびプログラム
出願人オムロン株式会社
代理人個人,個人,個人
主分類G06F 16/906 20190101AFI20250703BHJP(計算;計数)
要約【課題】ハッシュ法を用いた最近傍探索において、探索の効率性が高いハッシュテーブルを構築する。
【解決手段】第1のクラスに分類される対象を表現する特徴ベクトルで表される参照データを、各ビンの幅が第1の距離に設定されたハッシュテーブルに格納するデータ格納部と、第1のクラスに分類されるか否かを判定する判定対象を表現する特徴ベクトルを算出する特徴量算出部と、判定対象を表現する特徴ベクトルを用いてハッシュ値を算出し、ハッシュ値に対応するビンをハッシュテーブルにおける探索対象のビンとして決定する探索領域決定部と、前記探索対象のビンに格納されている各々の参照データと、判定対象を表現する特徴ベクトルで表されるクエリとの距離を計算する距離計算部と、各々の参照データとクエリとの距離と、第1の距離を比較することにより、判定対象が前記第1のクラスに分類されるか否かを判定する分類部と、を備える。
【選択図】図4
特許請求の範囲【請求項１】
第１のクラスに分類される対象を表現する特徴ベクトルで表される参照データを、各ビンの幅が第１の距離に設定されたハッシュテーブルに格納するデータ格納部と、
前記第１のクラスに分類されるか否かを判定する判定対象を表現する特徴ベクトルを算出する特徴量算出部と、
前記判定対象を表現する特徴ベクトルを用いてハッシュ値を算出し、前記ハッシュ値に対応するビンを前記ハッシュテーブルにおける探索対象のビンとして決定する探索領域決定部と、
前記探索対象のビンに格納されている各々の参照データと、前記判定対象を表現する特徴ベクトルで表されるクエリとの距離を計算する距離計算部と、
各々の参照データと前記クエリとの距離と、前記第１の距離を比較することにより、前記判定対象が前記第１のクラスに分類されるか否かを判定する分類部と、を備えた情報処理装置。
続きを表示（約 1,200 文字）【請求項２】
前記データ格納部は、
各々の参照データを表す特徴ベクトルの各要素の統計量に基づいて、基底とする要素を決定する、請求項１に記載の情報処理装置。
【請求項３】
前記距離計算部は、
前記ハッシュ値に対応するビンの近傍のビンも探索対象とする、請求項１に記載の情報処理装置。
【請求項４】
前記距離計算部は、
前記クエリとの距離が前記第１の距離以下の参照データが見つかった時点で他の参照データと前記クエリとの距離の計算を終了し、
前記分類部は、
前記判定対象が前記第１のクラスに分類されると判定する、請求項１に記載の情報処理装置。
【請求項５】
前記分類部は、
前記クエリとの距離が前記第１の距離以下の参照データが見つからなかった場合には、前記判定対象が前記第１のクラスに分類されないと判定する、請求項４に記載の情報処理装置。
【請求項６】
前記距離計算部は、
各々の近傍のビンの代表点と前記クエリとの距離に基づいて、近傍のビンの探索順序を決定する、請求項３に記載の情報処理装置。
【請求項７】
１つ以上の参照データを含むビンの数が最大になるように、軸または参照データの座標が変換されたハッシュテーブルを有する、請求項１に記載の情報処理装置。
【請求項８】
前記データ格納部は、
互いの距離が前記第１の距離以下の参照データの間引きを行う、請求項１に記載の情報処理装置。
【請求項９】
前記距離計算部は、
各々の参照データと前記クエリとの距離に基づいて、参照データの中から最近傍点を決定し、
前記分類部は、
前記クエリと前記最近傍点との距離と前記第１の距離を比較することにより、前記判定対象の分類を行う、請求項１に記載の情報処理装置。
【請求項１０】
第１のクラスに分類される対象を表現する特徴ベクトルで表される参照データを、ビンの最小の幅が第１の距離に設定されたハッシュテーブルに格納するデータ格納部と、
前記第１のクラスに分類されるか否かを判定する判定対象を表現する特徴ベクトルを算出する特徴量算出部と、
前記判定対象を表現する特徴ベクトルを用いてハッシュ値を算出し、前記ハッシュ値に対応するビンを前記ハッシュテーブルにおける探索対象のビンとして決定する探索領域決定部と、
前記探索対象のビンに格納されている各々の参照データと、前記判定対象を表現する特徴ベクトルで表されるクエリとの距離を計算する距離計算部と、
各々の参照データと前記クエリとの距離と、前記第１の距離を比較することにより、前記判定対象が前記第１のクラスに分類されるか否かを判定する分類部と、を備えた情報処理装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、最近傍探索を利用して判定対象の分類を行う情報処理装置、情報処理方法およびプログラムに関する。
続きを表示（約 1,700 文字）【背景技術】
【０００２】
最近傍探索は、距離空間におけるもっとも近い点を探すための手法であり、参照データ（点）の中から、クエリで示される点と最も類似している（最も距離が近い）点、すなわち、最近傍点を探す手法である。最近傍探索の具体的な手法として、ハッシュ法を用いる手法が知られている。例えば特許文献１には、ハッシュ法を用いた最近傍点の探索において、ハッシュインデックスに対応した領域（ビン）内の代表点とクエリとの距離に基づいて探索すべき領域を絞り込むことにより、最近傍点の探索を効率的に行うことが記載されている。
【先行技術文献】
【特許文献】
【０００３】
国際公開第２０１３／１２９５８０号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ハッシュ法を用いて高速かつ精度の高い最近傍探索を行うためには、探索対象の各参照データの分布に対して、ハッシュの区切りを適切に設定することが効果的である。しかしながら、従来、ハッシュ探索においてハッシュを適切に区切る方法については検討されていなかった。
【０００５】
本発明は、ハッシュ法を用いた最近傍探索において、探索の効率性が高いハッシュテーブルを構築することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上述した課題を解決するために、以下の構成を採用する。
本発明の一側面に係る情報処理装置は、第１のクラスに分類される対象を表現する特徴ベクトルで表される参照データを、各ビンの幅が第１の距離に設定されたハッシュテーブルに格納するデータ格納部と、前記第１のクラスに分類されるか否かを判定する判定対象を表現する特徴ベクトルを算出する特徴量算出部と、前記判定対象を表現する特徴ベクトルを用いてハッシュ値を算出し、前記ハッシュ値に対応するビンを前記ハッシュテーブルにおける探索対象のビンとして決定する探索領域決定部と、前記探索対象のビンに格納されている各々の参照データと、前記判定対象を表現する特徴ベクトルで表されるクエリとの距離を計算する距離計算部と、各々の参照データと前記クエリとの距離と、前記第１の距離を比較することにより、前記判定対象が前記第１のクラスに分類されるか否かを判定する分類部と、を備えたものである。
上記構成によれば、クエリとの距離が所定の閾値（第１の距離）以内の参照データの有無を探索することによって、判定対象を分類するようなタスクにおいて、効率性が非常に高いハッシュ探索の手法を提供することができる。
【０００７】
また、前記データ格納部は、各々の参照データを表す特徴ベクトルの各要素の統計量に基づいて、基底とする要素を決定するようにしてもよい。
これにより、ハッシュテーブルの各ビンに格納される参照データの偏りが軽減され、ビン内の探索を効率化することができる。
【０００８】
また、前記距離計算部は、前記ハッシュ値に対応するビンの近傍のビンも探索対象とするようにしてもよい。
これにより、近傍のビンに存在する可能性がある最近傍点（クエリとの距離が閾値以下の点）を効率的に探索することができる。
【０００９】
また、前記距離計算部は、前記クエリとの距離が前記第１の距離以下の参照データが見つかった時点で他の参照データと前記クエリとの距離の計算を終了し、前記分類部は、前記判定対象が前記第１のクラスに分類されると判定するようにしてもよい。
これにより、効率的かつ正確に判定対象の分類を行うことができる。
【００１０】
また、前記分類部は、前記クエリとの距離が前記第１の距離以下の参照データが見つからなかった場合には、前記判定対象が前記第１のクラスに分類されないと判定するようにしてもよい。
これにより、効率的かつ正確に判定対象の分類を行うことができる。
（【００１１】以降は省略されています）

関連特許