(57)【要約】  ペアワイズ距離計算が、絶対距離保存マッピングを用いて第１の信号及び第２の信号を変換して、第１のマッピングされた信号と第２のマッピングされた信号との間のｋノルム距離が、第１の信号と第２の信号との間の絶対距離を表すようにする。絶対距離保存マッピングは、第１の信号又は第２の信号の要素を、信号の有限アルファベットのカーディナリティに等しいサイズを有するベクトルにマッピングする。絶対距離保存マッピングは、有限アルファベットのシンボルの順序付けされたシーケンスにおいて要素の位置Ｎを決定し、ベクトルのＮ個の要素の各々の値を、有限アルファベットにおける正の増分の分数乗１／ｋとして決定する。ベクトルの後続の要素の値は０として決定される。
2017511537.tif 000002
【特許請求の範囲】
【請求項１】
ペアワイズ距離計算のための方法であって、
絶対距離保存マッピングを用いて第１の信号を第１のマッピングされた信号に変換するステップと、
前記第１のマッピングされた信号と第２のマッピングされた信号との間のｋノルム距離が、前記第１の信号と第２の信号との間の絶対距離を表すように、前記絶対距離保存マッピングを用いて、前記第２の信号を前記第２のマッピングされた信号に変換するステップであって、前記第１の信号及び前記第２の信号の要素は有限アルファベットから選択され、前記絶対距離保存マッピングは、前記第１の信号又は前記第２の信号の要素を、前記有限アルファベットのカーディナリティに等しいサイズを有するベクトルにマッピングする、ステップと、
を含み、該方法の各ステップはプロセッサが実行し、前記絶対距離保存マッピングは、
前記有限アルファベットのシンボルの順序付けされたシーケンスにおいて前記要素の位置Ｎを決定することと、
前記ベクトルのＮ個の要素の各々の値を、前記有限アルファベットにおける正の増分の分数乗１／ｋとして決定することであって、ｋは正数であることと、
前記ベクトルの後続の要素の値を０として決定することと、
を含む、方法。
【請求項２】
前記第１のマッピングされた信号と前記第２のマッピングされた信号との間の前記ｋノルム距離を求めて、前記第１の信号と前記第２の信号との間の前記絶対距離を得ること、
を更に含む、請求項１に記載の方法。
【請求項３】
前記ｋノルム距離は、暗号化領域においてセキュアに求められる、請求項１に記載の方法。
【請求項４】
前記ｋノルム距離は、前記第１のマッピングされた信号及び前記第２のマッピングされた信号の準同型成分の線形結合として求められた二乗ユークリッド距離である、請求項３に記載の方法。
【請求項５】
前記ベクトルの前記Ｎ個の要素は、前記ベクトルの最初のＮ個の要素又は最後のＮ個の要素である、請求項１に記載の方法。
【請求項６】
前記第１の信号及び前記第２の信号はセンサーから受信される、請求項１に記載の方法。
【請求項７】
前記センサーはカメラであり、前記第１の信号及び前記第２の信号は、前記カメラによって取得される画像内のピクセルの値を含む、請求項６に記載の方法。
【請求項８】
前記第２の信号は、信号のデータベースに記憶され、
前記方法は、
前記データベース内の前記信号を、前記絶対距離保存マッピングを用いて変換して、マッピングされた信号のデータベースを得ることと、
前記第１のマッピングされた信号とのｋノルム距離を用いて、前記マッピングされた信号のデータベースをクエリし、ｋノルム距離メトリックの場合の少なくとも１つの最近傍信号を決定することと、
を更に含む、請求項１に記載の方法。
【請求項９】
前記ｋノルム距離は、ｋノルム距離最近傍探索を含む、請求項８に記載の方法。
【請求項１０】
前記ｋノルム距離は、ｋノルム距離近似近傍探索を含む、請求項８に記載の方法。
【請求項１１】
前記信号のデータベースは、各信号に対応する情報を含み、
前記方法は、
前記データベースから、前記最近傍信号に対応する前記情報を取り出すことを更に含む、請求項８に記載の方法。
【請求項１２】
ペアワイズ距離計算のためのシステムであって、
信号を決定するためのセンサーであって、第１の信号の要素は有限アルファベットから選択される、センサーと、
信号の各要素が、マッピングされた信号においてベクトルにマッピングされるように、絶対距離保存マッピングを用いて、前記信号を前記マッピングされた信号に変換するためのプロセッサであって、前記ベクトルのサイズは前記有限アルファベットのカーディナリティに等しく、前記要素の前記絶対距離保存マッピングは、
前記有限アルファベットのシンボルの順序付けされたシーケンスにおいて前記要素の位置Ｎを決定することと、
前記ベクトルのＮ個の要素の各々の値を、前記有限アルファベットにおける正の増分の分数乗１／ｋとして決定することであって、ｋは正数であることと、
前記ベクトルの後続の要素の値を０として決定することと、
を含む、プロセッサと、
前記マッピングされた信号を記憶するためのメモリと、
を備える、システム。
【請求項１３】
前記メモリは、前記絶対距離保存マッピングを用いて前記第１の信号から変換される第１のマッピングされた信号を記憶するとともに、前記絶対距離保存マッピングを用いて第２の信号から変換された第２のマッピングされた信号を記憶し、
前記システムは、
前記メモリと連動し、前記第１のマッピングされた信号と前記第２のマッピングされた信号との間のｋノルム距離を求めて、前記第１の信号と前記第２の信号との間の絶対距離を得るためのペアワイズ距離計算ユニットを更に備える、請求項１２に記載のシステム。
【請求項１４】
ペアワイズ距離計算のための方法であって、
センサーの出力を表す第１の信号を受信することであって、前記第１の信号の要素は有限アルファベットから選択されることと、
プロセッサを用いて、前記第１の信号の各要素が第１のマッピングされた信号においてベクトルにマッピングされるように、前記第１の信号を、絶対距離保存マッピングを用いて、前記第１のマッピングされた信号に変換することであって、前記ベクトルのサイズは前記有限アルファベットのカーディナリティに等しく、
前記要素の前記絶対距離保存マッピングは、
前記有限アルファベットのシンボルの順序付けされたシーケンスにおいて前記要素の位置Ｎを決定することと、
前記ベクトルのＮ個の要素の各々の値を、前記有限アルファベットにおける正の増分の分数乗１／ｋとして決定することであって、ｋは正数であることと、
前記ベクトルの後続の要素の値を０として決定することと、
を含むことと、
前記第１のマッピングされた信号をメモリに記憶することと、
を含む、方法。
【請求項１５】
前記絶対距離保存マッピングを用いて第２の信号を第２のマッピングされた信号に変換することと、
前記第１のマッピングされた信号と前記第２のマッピングされた信号との間のｋノルム距離を求めて、前記第１の信号と前記第２の信号との間の絶対距離を得ることと、
を更に含む、請求項１４に記載の方法。
【請求項１６】
前記ｋノルム距離は、暗号化領域においてセキュアに求められる、請求項１４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、ペアワイズ距離計算に関し、より詳細には、プライバシ制約を有するか又は有しない信号間の絶対距離の計算に関する。
【背景技術】
【０００２】
一方又は双方の信号に対しプライバシ制約が存在するとき、セキュア距離計算が実行される。この問題を解決する１つの方法は、暗号文空間における計算を可能にする暗号化関数を用いることである。そのような暗号システムは、準同型暗号システム（homomorphic cryptosystem）と呼ばれる。準同型暗号システムに基づく多くのプロトコルが開発された。応用形態にはセキュアな計算が含まれ、クライアントプロセッサは、暗号化データをサーバーに送信することができる。サーバーはクライアントとインタラクトして、信用できない第三者にデータを明らかにすることなく数学問題を解く。プロトコルは、中でも、ユークリッド距離（Ｌ２ノルム）、Ｌ３ノルム、相関等の計算を可能にする多項式関数計算プリミティブを含む。しかしながら、プライバシ制約の下で、２つの信号間の絶対距離を計算するための効率的なプロトコルは存在しない。
【０００３】
したがって、そのような絶対距離のセキュアな計算に適したものとなるように２つの信号間の絶対距離を求める方法が必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
２つの信号間の「距離」は、信号間の類似度の尺度としての役割を果たすことができる。本発明の幾つかの実施形態の１つの目標は、２つの信号間の絶対距離を求める方法を提供することである。幾つかの実施形態の別の目標は、信号間の絶対距離のセキュアな計算に適したそのような方法を提供することである。
【課題を解決するための手段】
【０００５】
幾つかの実施形態は、絶対距離計算をｋノルム距離計算、例えば多項式距離計算に変換することを含む。実施形態は、元々は絶対距離を求める際に多項式距離（ユークリッド距離等）を求めるために構築された計算プリミティブを、再利用することを可能にする。
【０００６】
例えば、幾つかの実施形態は、新たにマッピングされた信号の対に対し計算される適切に選択された多項式距離関数が、基礎を成す元の２つの入力信号間の絶対距離に概ね等しくなるように、元の信号を新たな信号にマッピングする。この絶対距離保存マッピング（absolute distance preserving mapping）は、入力信号の各スカラー寸法を、スカラーアルファベットのカーディナリティ（cardinality）にちょうど等しい長さを有するベクトルとして表し、ベクトルの要素の値は、利用可能な多項式距離計算プリミティブに従って選択される。
【０００７】
例えば、信号の要素の絶対距離保存マッピングは、順に配列された有限アルファベットのシンボルのベクトル内の要素の位置Ｎを決定することと、ベクトルの最初のＮ個の要素又は最後のＮ個の要素の各々の値を、有限アルファベットにおける正の増分の分数乗（fractional power）として決定することであって、分数乗は正数の逆数であることと、ベクトルの後続の要素の値を０として決定することとを含む。
【０００８】
したがって、本発明の一実施の形態は、ペアワイズ距離計算のための方法を開示する。本方法は、絶対距離保存マッピングを用いて第１の信号を第１のマッピングされた信号に変換することと、絶対距離保存マッピングを用いて第２の信号を第２のマッピングされた信号に変換することであって、第１のマッピングされた信号と第２のマッピングされた信号との間のｋノルム距離が、第１の信号と第２の信号との間の絶対距離を表すようにすることとを含む。第１の信号及び第２の信号の要素は有限アルファベットから選択され、絶対距離保存マッピングは、第１の信号又は第２の信号の要素を、有限アルファベットのカーディナリティに等しいサイズを有するベクトルにマッピングする。本方法のステップはプロセッサによって実行される。
【０００９】
別の実施の形態は、信号を決定するためのセンサーであって、第１の信号の要素は有限アルファベットから選択される、センサーと、絶対距離保存マッピングを用いて信号をマッピングされた信号に変換するためのプロセッサであって、信号の各要素がマッピングされた信号においてベクトルにマッピングされるようにし、ベクトルのサイズは有限アルファベットのカーディナリティに等しいプロセッサと、マッピングされた信号を記憶するためのメモリとを備える、システムを開示する。
【００１０】
更に別の実施の形態は、センサーの出力を表す第１の信号を受信するステップであって、第１の信号の要素は有限アルファベットから選択されるステップと、プロセッサを用いて、第１の信号を絶対距離保存マッピングを用いて第１のマッピングされた信号に変換するステップであって、第１の信号の各要素が第１のマッピングされた信号においてベクトルにマッピングされるようにし、ベクトルのサイズは有限アルファベットのカーディナリティに等しいステップと、第１のマッピングされた信号をメモリに記憶するステップとを含む、ペアワイズ距離計算のための方法を開示する。
【００１１】
様々な実施の形態において、絶対距離保存マッピングは、有限アルファベットのシンボルの順序付けされたシーケンスにおいて要素の位置Ｎを決定することと、ベクトルのＮ個の要素の各々の値を、有限アルファベットにおける正の増分の分数乗１／ｋとして決定することであって、ｋは正数であることと、ベクトルの後続の要素の値を０として決定することとを含む。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態による絶対距離保存マッピングを用いた信号処理の概観の概略図である。
【図２】本発明の実施形態による絶対距離保存マッピングのブロック図である。
【図３Ａ】本発明の実施形態による絶対距離保存マッピングの一例の概略図である。
【図３Ｂ】本発明の実施形態による絶対距離保存マッピングの一例の概略図である。
【図３Ｃ】本発明の実施形態による絶対距離保存マッピングの一例の概略図である。
【図４】本発明の実施形態による絶対距離保存マッピングを求める方法のブロック図である。
【図５】本発明の実施形態による、ｋノルム距離メトリックに基づいて最近傍探索（nearest neighbor search）を行う方法のブロック図である。
【発明を実施するための形態】
【００１３】
図１は、信号１２０の絶対距離保存マッピングを用いた信号処理の概観を示す。信号は、センサー１１０の出力とすることができる。センサー１１０の例は、カメラ、例えば、画像又は奥行きカメラ、生体センサー、音響センサー又は光センサーを含む。信号１２０の例は、画像内のピクセルの輝度値若しくは奥行き値、又は指紋における特徴点の値を含む。様々な実施形態において、信号の要素は、有限のアルファベットから選択される。例えば、信号の要素は、０から２５５まで変動する値を有する（８ビットの）整数とすることができる。しかしながら、本方法は、他のタイプの信号に適用され得ることが理解されるべきである。
【００１４】
本発明の様々な実施形態は、信号１２０をマッピングして（１４０）マッピングされた信号１５０にし、このマッピングされた信号１５０はメモリ１６０に記憶するか又は後続の処理及び／又は距離計算に用いることができる。マッピングは、プロセッサ１３０によって実行することができる絶対距離保存マッピングである。プロセッサ１３０は、センサー１１０及び／又はメモリ１６０に連動することができる。
【００１５】
本方法は、当該技術分野において既知のバスによって、メモリ及び入出力インタフェースに接続されるプロセッサにおいて実行することができる。プロセッサは、クライアントプロセッサ、サーバープロセッサ、又はクライアントプロセッサ及びサーバープロセッサの組合せとすることができる。例えば、プライバシを保護するセキュアな応用形態では、ステップのうちの幾つかはクライアントにおいて実行され、他のステップはサーバーにおいて実行され、これは、どちらのプロセッサの信号又はデータ及び方法論も他方のプロセッサに明らかであるような方式で行われる。例えば、クライアントは、信号を生成する、複雑度の低い、リソースの限られたプロセッサである。サーバーは、無制限のリソースを有することができ、マッピングを実行する。次に、マッピング結果をメモリに記憶するか、又はクライアントに返送して、クライアントが信号間の類似度（又は非類似度）レベルを評価することを可能にすることができる。
【００１６】
本発明の幾つかの実施形態は、一対の信号間の絶対距離が、マッピングされた一対の信号に適用される代替的な距離関数の値に関係するという認識に基づく。離散した有界の信号の場合、この関係は、完全に等しい関係となる。有界であるが必ずしも離散していない信号の場合、この関係は、概ね等しい関係となる。ここで、近似は、処理される信号の連続値の離散化（量子化）の結果得られる。
【００１７】
図２は、幾つかの実施形態による絶対距離保存マッピングのブロック図を示す。信号１２０の要素２１０は、有限アルファベット２３０から選択された値を有する。各要素は、例えば、信号１２０の要素２２０は、マッピングされた信号１５０内のベクトル２２５にマッピングされる。ベクトル２２５のサイズは、有限アルファベット２３０のカーディナリティに等しい。
【００１８】
図３Ａは、マッピングされた信号１５０のベクトルへの信号１２０の要素のマッピングを示す。例えば、要素３１０は、ベクトル３２０にマッピングされる。要素３１５はベクトル３２５にマッピングされる。信号のサイズがｎであり（正：is n）、有限アルファベットのカーディナリティがｍである場合、マッピングされた信号のサイズはｍｎである。この例では、ｍは５に等しいため、ベクトル３２０及び３２５のサイズは５である。
【００１９】
本発明の幾つかの実施形態では、要素２２０の絶対距離保存マッピングは、有限アルファベットのシンボル２３０の順序付けされたシーケンス内の要素の位置Ｎを決定する（２４０）。例えば、ベクトルのＮ個の要素は、ベクトルの最初のＮ個の要素又は最後のＮ個の要素とすることができ、有限アルファベットのシンボルの順序付けされたシーケンスは、昇順又は降順で配列することができる。
【００２０】
また、要素２２０の絶対距離保存マッピングは、有限アルファベット２３０における正の増分の分数乗１／ｋとして、ベクトルのＮ個の要素の各々の値を決定し（２５０）、ベクトルの後続の要素の値を０として決定する（正：determines）（２７０）。ここで、ｋ２５５は正数である。
【００２１】
図３Ｂは、可能な値、１、２、３、４及び５を有する有限アルファベットから選択された値３を有する要素３３０ｓｉの絶対距離保存マッピングｆの例を示す。値３は、有限アルファベットにおける第３の位置を有し、すなわち、Ｎ＝３である。有限アルファベットにおける正の増分は１に等しく、すなわち、２−１＝１、３−２＝１、４−３＝１及び５−４＝１である。正の増分は全て１であるため、乗数ｋの任意の値について、マッピングされたベクトル３３５の最初の３つの要素は１であり、残りの２つの値は０である。
【００２２】
図３Ｃは、値１を有する要素３４０ｓｉの絶対距離保存マッピングｆの別の例を示す。この場合、Ｎ＝１であり、マッピングされたベクトル３４５の第１の要素のみが１であり、他の要素の値は０である。
【００２３】
マッピングの基礎を成す概念は、信号の各スカラー成分が、ベクトル形式で表現可能であることである。ここで、ベクトルの個々の成分は、信号のスカラー成分と、信号が取り得る各可能な値との間の関係（≦、＝、≧）に依拠する。ここで、信号がとり得る可能な値は、例えば最も低いものから最も高いものへと順序付けされる。
【００２４】
例えば、有限アルファベット集合
【数１】
2017511537.tif 000003
であり、ここで、
【数２】
2017511537.tif 000004
である。
【００２５】
一般性を損なうことなく、ａｉ＞０を仮定する。元のアルファベットが何らかの負値を有する場合、幾つかの実施形態は、アルファベットのシンボルの全てが非負となるように、全てのアルファベットシンボルに適切な定数を加える。
【００２６】
これらの順序付けされた要素から構築されたベクトルを、ａ＝（ａ１，．．．，ａｍ）で表す。幾つかの実施形態は、２つのベクトル、ｓ，ｔ∈Ｘｎ間の絶対距離を、異なる距離尺度、例えば、２つの異なるベクトル値信号
【数３】
2017511537.tif 000005
及び
【数４】
2017511537.tif 000006
間のＬｋノルムの観点で表し、ここで、整数ｋ＞１であり、ノルムは以下のように定義される。
【数５】
2017511537.tif 000007
【００２７】
上記の式において、ベクトル
【数６】
2017511537.tif 000008
及び
【数７】
2017511537.tif 000009
は、絶対距離保存マッピングによって、（それぞれ）ｓ及びｔに関係付けられる。
【００２８】
絶対距離保存マッピングは、ｂ１＝ａ１、かつｊ＝１，２，．．．，ｍについてｂｊ＝（ａｊ−ａｊ−１）であるような、Ｘのｍ個の順序付けされた要素を用いて長さｍのベクトルｂを構築する。構築によって、ｂの要素の値は全て正の増分であり、以下のようになる。
【数８】
2017511537.tif 000010
ここで、１≦ｕ≦ｍである。
【００２９】
アルファベット集合Ｘ内の各可能な値ａｉは、ｍ個の要素を含むベクトル値関数ｆ（ａｉ）でマッピングされる。このベクトル値関数の各個々の要素は、以下によって与えられる。
【数９】
2017511537.tif 000011
【００３０】
このため、ｆ（ａｉ）の各要素は、Ｘにおける要素の正の増分の分数乗であるか、又は０値を有する。
【００３１】
上記の候補ベクトルｓ及びｔを所与とすると、幾つかの実施形態は、新たなベクトル
【数１０】
2017511537.tif 000012
及び
【数１１】
2017511537.tif 000013
を構築する。これらのベクトルの要素は、
【数１２】
2017511537.tif 000014
及び
【数１３】
2017511537.tif 000015
によって与えられる。ここで、マッピング関数は上記のとおりである。
【００３２】
ここで、
【数１４】
2017511537.tif 000016
を検証するのは簡単である。
【００３３】
このため、ｓとｔとの間の絶対距離は、
【数１５】
2017511537.tif 000017
と    
【数１６】
2017511537.tif 000018
との間のｋノルム距離として表されている。入力
【数１７】
2017511537.tif 000019
及び
【数１８】
2017511537.tif 000020
として受け入れることができ、距離メトリック
【数１９】
2017511537.tif 000021
と連携する計算プリミティブが存在する場合、これらのプリミティブは、ベクトルｓ及びｔに対する距離ベースの計算のために用いることができる。ここで、ｋ＞１であり、ｋは有限の実数である。さらに、Ｌｋノルムメトリック空間における距離を保存する
【数２０】
2017511537.tif 000022
及び
【数２１】
2017511537.tif 000023
のマッピングが存在する場合、これらのマッピングを用いて、ベクトルｓ及びｔ間の絶対距離を保存することができる。
【００３４】
図４は、計算プリミティブが本発明の１つの実施形態によるｋノルム距離に利用可能であるときの絶対距離を求める方法のブロック図を示す。本方法は、プロセッサ１３０等のプロセッサを用いて行うことができる。付加的に又は代替的に、本方法の少なくとも一部を、ペアワイズ距離計算ユニット４０１のプロセッサによって実行することができる。これは異なるプロセッサとすることができる。ペアワイズ距離計算ユニットは、メモリ１６０に連動することができる。
【００３５】
本方法は、絶対距離保存マッピングを用いて、第１の信号４１０を第１のマッピングされた信号４５０に変換し（４３０）、絶対距離保存マッピングを用いて、第２の信号４２０を第２のマッピングされた信号４６０に変換する（４４０）。第１の信号及び第２の信号の要素は、同じ有限アルファベットから選択される。
【００３６】
次に、本方法は、第１のマッピングされた信号と第２のマッピングされた信号との間のｋノルム距離を求め（４７０）、第１の信号と第２の信号との間の絶対距離４８０を得る。例えば、距離は、ｋが２であるとき、ユークリッド距離である。
【００３７】
２つの信号間のユークリッド距離は、セキュアな方式で実行することができる方法を含めて、様々な方法を用いて求めることができる。このため、幾つかの実施形態は、２つの信号間の絶対距離を求めることができ、また、そのような絶対距離をセキュアに求めることができる。
【００３８】
本発明の実施形態は、第１のマッピングされた信号４５０と第２のマッピングされた信号４６０との間のｋノルム距離をセキュアに求める様々な方法を用いる。例えば、１つの実施形態は、信号間の二乗ユークリッド距離を求める。この実施形態は、米国特許出願公開第２０１０／０３２９４４８号明細書に記載されているように、二乗ユークリッド距離関数を準同型成分の線形結合として表し、準同型変換に基づいて二乗距離を求める。準同型成分は、信号４５０及び／又は信号４６０の代数結合であり、それによって、代数結合の暗号化結果を、準同型特性を用いて信号の暗号化バージョンから直接求めることができる。
【００３９】
図５は、本発明の１つの実施形態による、ｋノルム距離メトリックに最近傍プリミティブが利用可能であるとき、絶対距離メトリックに基づいて最近傍探索を行う方法のブロック図を示す。本方法は、プロセッサ１３０等のプロセッサを用いて実行することができる。付加的に又は代替的に、本方法の少なくとも一部は、異なるプロセッサとすることができる最近傍計算ユニット５０１のプロセッサによって実行することができる。最近傍計算ユニットは、メモリ１６０と連動することができる。
【００４０】
最近傍探索は、距離メトリックに従って、クエリ信号５１０と信号のデータベース５２０との間で行われる。最近傍探索において、クエリ信号とデータベース内の複数の信号との間の距離又は近似距離が明示的に又は暗黙的に計算される。この探索の出力は、最短距離又は近似距離を有するデータベース内の信号、そのデータベース内の信号へのポインター、又はその信号に関する情報とすることができ、これらもデータベース内に記憶される。
【００４１】
この実施形態は、絶対距離保存マッピングを用いてクエリ信号５１０をマッピングされたクエリ信号５５０に変換する際に（５３０）、及び、絶対距離保存マッピングを用いて信号のデータベース内の各信号を変換することによって信号のデータベース５２０をマッピングされた信号のデータベース５６０に変換する際に（５４０）、図４の実施形態と同様に動作する。クエリ信号の要素、及び信号のデータベース内の信号の要素は、同じ有限アルファベットから選択される。
【００４２】
次に、本方法は、ｋノルム最近傍プリミティブ５７０を用いて、マッピングされたクエリ信号及びマッピングされた信号のデータベースのｋノルム最近傍探索を実行する。これによって、マッピングされたクエリ信号と、マッピングされた信号のデータベースとの間のｋノルム距離メトリックの最近傍５８０が得られる。マッピングされた信号のデータベース内のマッピングされたクエリ信号のｋノルム距離メトリックの場合の最近傍は、信号のデータベース内のクエリ信号の絶対距離メトリック５９０の場合の最近傍に対応する。
【００４３】
代替的な実施形態では、ｋノルム最近傍プリミティブは、近似ｋノルム近傍プリミティブと置き換えることができる。近似ｋノルム近傍プリミティブは、ｋノルム距離メトリックに従うが、必ずしも最近傍には従わずに、マッピングされた信号のデータベースから、マッピングされたクエリ信号との小さな距離を有する１つ又は複数の信号を選択する。代替的な実施形態では、ｋノルム距離メトリックを用いる他の同様の探索又は比較プリミティブも用いることができる。
【図１】
2017511537.tif 000024
【図２】
2017511537.tif 000025
【図３Ａ】
2017511537.tif 000026
【図３Ｂ】
2017511537.tif 000027
【図３Ｃ】
2017511537.tif 000028
【図４】
2017511537.tif 000029
【図５】
2017511537.tif 000030
【手続補正書】
【提出日】平成28年9月15日(2016.9.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入出力インタフェースに接続されたプロセッサと、センサーに接続された前記インタフェースを介して前記プロセッサに接続されたメモリに記憶された信号データとを用いて、ペアワイズ距離を計算するための、コンピューターにより実施される方法であって、
前記メモリに記憶された絶対距離保存マッピングを用いて第１の信号データを第１のマッピングされた信号データに変換するステップと、
前記第１のマッピングされた信号データと第２のマッピングされた信号データとの間のｋノルム距離が、前記第１の信号データと第２の信号データとの間の絶対距離を表すように、前記絶対距離保存マッピングを用いて、前記第２の信号データを前記第２のマッピングされた信号データに変換するステップであって、前記第２の信号データは信号データのデータベースに記憶され、前記第１の信号データ及び前記第２の信号データの要素は有限アルファベットに対応する信号データから選択され、前記絶対距離保存マッピングは、前記第１の信号データ又は前記第２の信号データの要素を、前記有限アルファベットのカーディナリティに等しいサイズを有するベクトルにマッピングする、ステップと、
を含み、該方法の各ステップは前記プロセッサが実行し、
前記ｋノルム距離は暗号化領域においてセキュアに求められ、前記第２のマッピングされた信号データは前記信号データのデータベースに記憶されることと、
前記第１のマッピングされた信号データとの前記ｋノルム距離を用いて、前記マッピングされた信号データのデータベースをクエリし、ｋノルム距離メトリックの場合の少なくとも１つの最近傍信号データを決定することであって、前記絶対距離保存マッピングは、
前記有限アルファベットのシンボルの順序付けされたシーケンスにおいて前記要素の位置Ｎを決定することと、
前記ベクトルのＮ個の要素の各々の値を、前記有限アルファベットにおける正の増分の分数乗１／ｋとして決定することであって、ｋは正数であることと、
前記ベクトルの後続の要素の値を０として決定することと、
を含む、方法。
【請求項２】
前記第１のマッピングされた信号データと前記第２のマッピングされた信号データとの間の前記ｋノルム距離を求めて、前記第１の信号データと前記第２の信号データとの間の前記絶対距離を得ること、
を更に含む、請求項１に記載の方法。
【請求項３】
前記ｋノルム距離は、前記第１のマッピングされた信号データ及び前記第２のマッピングされた信号データの準同型成分の線形結合として求められた二乗ユークリッド距離である、請求項１に記載の方法。
【請求項４】
前記ベクトルの前記Ｎ個の要素は、前記ベクトルの最初のＮ個の要素又は最後のＮ個の要素である、請求項１に記載の方法。
【請求項５】
前記第１の信号データ及び前記第２の信号データは前記センサーから受信される、請求項１に記載の方法。
【請求項６】
前記センサーはカメラであり、前記第１の信号データ及び前記第２の信号データは、前記カメラによって取得される画像内のピクセルの値を含む、請求項５に記載の方法。
【請求項７】
前記ｋノルム距離は、ｋノルム距離最近傍探索を含む、請求項１に記載の方法。
【請求項８】
前記ｋノルム距離は、ｋノルム距離近似近傍探索を含む、請求項１に記載の方法。
【請求項９】
前記信号データのデータベースは、各信号データに対応する情報を含み、
前記方法は、
前記データベースから、前記最近傍信号データに対応する前記情報を取り出すことを更に含む、請求項１に記載の方法。
【請求項１０】
信号データを決定して出力するように構成されたセンサーであって、メモリに記憶される第１の信号データの要素は有限アルファベットに対応する信号データから選択される、センサーと、
信号データの各要素が、マッピングされた信号データにおいてベクトルにマッピングされるように、絶対距離保存マッピングを用いて、前記センサーから受信した前記信号データを前記マッピングされた信号データに変換するように構成されたプロセッサであって、前記ベクトルのサイズは前記有限アルファベットのカーディナリティに等しく、ｋノルム距離は暗号化領域においてセキュアに求められ、前記マッピングされた信号データはマッピングされた信号データのデータベースに記憶され、
第１のマッピングされた信号データとの前記ｋノルム距離を用いて、前記マッピングされた信号データのデータベースをクエリして、ｋノルム距離メトリックの場合の少なくとも１つの最近傍信号データを決定し、ｋノルム距離は暗号化領域においてセキュアに求められ、前記要素の前記絶対距離保存マッピングは、
前記有限アルファベットのシンボルの順序付けされたシーケンスにおいて前記要素の位置Ｎを決定することと、
前記ベクトルのＮ個の要素の各々の値を、前記有限アルファベットにおける正の増分の分数乗１／ｋとして決定することであって、ｋは正数であることと、
前記ベクトルの後続の要素の値を０として決定することと、
を含む、プロセッサと、
前記メモリは前記マッピングされた信号データを記憶する、システム。
【請求項１１】
前記メモリは、前記絶対距離保存マッピングを用いて前記第１の信号データから変換される前記第１のマッピングされた信号データを記憶するとともに、前記絶対距離保存マッピングを用いて第２の信号データから変換された第２のマッピングされた信号データを記憶し、
前記システムは、
前記メモリと連動し、前記第１のマッピングされた信号データと前記第２のマッピングされた信号データとの間の前記ｋノルム距離を求めて、前記第１の信号データと前記第２の信号データとの間の絶対距離を得るためのペアワイズ距離計算ユニットを更に備える、請求項１０に記載のシステム。
【請求項１２】
プロセッサと、該プロセッサに接続されたメモリに記憶された信号データとを用いてペアワイズ距離を計算するための、コンピューターにより実施される方法であって、
センサーの出力を表す第１の信号データを受信することであって、前記第１の信号データの要素は有限アルファベットに対応する信号データから選択され、前記信号データは信号データのデータベースに記憶されることと、
前記プロセッサを用いて、前記第１の信号データの各要素が第１のマッピングされた信号データにおいてベクトルにマッピングされるように、前記第１の信号データを、絶対距離保存マッピングを用いて、前記第１のマッピングされた信号データに変換することであって、前記ベクトルのサイズは前記有限アルファベットのカーディナリティに等しいことと、
前記データベース内の前記信号データを、前記絶対距離保存マッピングを用いて変換して、マッピングされた信号データのデータベースを得ることと、
前記第１のマッピングされた信号データとのｋノルム距離を用いて、前記マッピングされた信号データのデータベースをクエリし、ｋノルム距離メトリックの場合の少なくとも１つの最近傍信号データを決定することであって、前記ｋノルム距離は暗号化領域においてセキュアに求められ、
前記要素の前記絶対距離保存マッピングは、
前記有限アルファベットのシンボルの順序付けされたシーケンスにおいて前記要素の位置Ｎを決定することと、
前記ベクトルのＮ個の要素の各々の値を、前記有限アルファベットにおける正の増分の分数乗１／ｋとして決定することであって、ｋは正数であることと、
前記ベクトルの後続の要素の値を０として決定することと、
を含むことと、
前記第１のマッピングされた信号データを前記メモリに記憶することと、
を含む、方法。
【請求項１３】
前記絶対距離保存マッピングを用いて第２の信号データを第２のマッピングされた信号データに変換することと、
前記第１のマッピングされた信号データと前記第２のマッピングされた信号データとの間の前記ｋノルム距離を求めて、前記第１の信号データと前記第２の信号データとの間の絶対距離を得ることと、
を更に含む、請求項１２に記載の方法。
【国際調査報告】
2017511537.tif 000031
2017511537.tif 000032