(57)【特許請求の範囲】
【請求項１】
クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための方法であって、
前記クライアントデバイスにより、クエリ画像の少なくとも１つの特徴を定義する画像特徴記述子のセットをクエリ画像から抽出することと、
第１の量子化レベルで量子化された前記画像特徴記述子のセットを表す第１のクエリデータを生成するために、前記クライアントデバイスにより、前記第１の量子化レベルで前記画像特徴記述子のセットを量子化することと、
前記クライアントデバイスにより、前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信することと、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが第２の量子化レベルで量子化された前記画像特徴記述子のセットを表すように、前記クライアントデバイスにより、前記第１のクエリデータを拡張する第２のクエリデータを決定することと、前記第２の量子化レベルは、前記第１の量子化レベルで量子化された前記画像特徴記述子のセットより正確な前記画像特徴記述子のセットの表現を達成し、
前記第１のクエリデータをリファインするために、前記クライアントデバイスにより、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信することと、
を備える方法。
【請求項２】
前記第２のクエリデータを送信することは、前記視覚探索デバイスが前記第１の量子化レベルで量子化された前記画像特徴記述子を表す前記第１のクエリデータを使用して前記視覚探索を実行することと同時に、前記第２のクエリデータを送信することを備える、請求項１に記載の方法。
【請求項３】
第１の量子化レベルで前記画像特徴記述子を量子化することは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を決定することを含み、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
第２のクエリデータを決定することは、
追加の再構成点のそれぞれが前記面のそれぞれの中心に位置するように、追加の再構成点を決定することと、
前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定することと、
前記オフセットベクトルを含むように前記第２のクエリデータを生成することと、
を含む請求項１に記載の方法。
【請求項４】
第１の量子化レベルで前記画像特徴記述子を量子化することは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を決定することを含み、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
第２のクエリデータを決定することは、
前記追加の再構成点のそれぞれが前記ボロノイセルの前記交点に位置するように、追加の再構成点を決定することと、
前記前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定することと、
前記オフセットベクトルを含むように前記第２のクエリデータを生成することと、
を含む請求項１に記載の方法。
【請求項５】
前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記画像特徴記述子を第１の量子化レベルで量子化することは、
勾配のヒストグラムに対して最近のタイプを決定することと、前記タイプは、所与の共通分母を有する有理数のセットであり、前記有理数のセットの合計は１に等しい、
前記決定されたタイプを、前記所与の共通分母を有するすべての可能なタイプに対して前記決定されたタイプの辞書式配列を一意に識別するインデックスにマッピングすることと、を含み、
前記第１のクエリデータは前記タイプのインデックスを含む、
請求項１に記載の方法。
【請求項６】
前記第２のクエリデータにより拡張された後に前記第１のクエリデータが第３のクエリデータでアップデートされると、前記連続してアップデートされた第１のクエリデータが第３の量子化レベルで量子化された前記画像特徴記述子を表すように前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを送信する前に、前記視覚探索デバイスで維持されるデータベース内を探索した結果として得られた、前記視覚探索デバイスからの識別データを受信することと、
前記第３のクエリデータを送ることなく前記視覚探索を終わらせることと、
前記識別データを視覚探索アプリケーションの中で使用することと、
をさらに備える、請求項１に記載の方法。
【請求項７】
前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子のセットを表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを決定することと、前記第３の量子化レベルは、前記第２の量子化レベルで量子化するときよりも一層正確な前記画像特徴記述子のセットの表現を達成し、
前記第２のクエリデータで拡張された後の前記第１のクエリデータを連続的にリファインするために、前記第３のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信することと、
をさらに備える、請求項１に記載の方法。
【請求項８】
クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための方法であって、
前記視覚探索デバイスにより、第１のクエリデータを使用して前記視覚探索を実行することと、前記第１のクエリデータは、画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子のセットを表し、
前記視覚探索デバイスにより、第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して受信することと、
前記第２のクエリデータは、前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた前記第１のクエリデータが、第２の量子化レベルで量子化された前記画像特徴記述子のセットを表すように前記第１のデータを拡張し、
前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記第２の量子化レベルで量子化された前記画像特徴記述子を表す、アップデートされた第１のクエリデータを生成するために、前記視覚探索デバイスにより、前記第１のクエリデータを前記第２のクエリデータでアップデートすることと、
前記視覚探索デバイスにより、前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行することと、
を備える方法。
【請求項９】
前記第１のクエリデータを使用して前記視覚探索を実行することは、前記第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して前記視覚探索デバイスに送信することと同時に、前記第１のクエリデータを使用して前記視覚探索を実行することを備える、請求項８に記載の方法。
【請求項１０】
前記第１のクエリデータは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記面のそれぞれの中心に位置し、
前記アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートすることは、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加することを含む、請求項８に記載の方法。
【請求項１１】
前記第１のクエリデータは、前記再構成点がそれぞれ前記画像特徴記述子のセットに対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記ボロノイセルの交点に位置し、
前記アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートすることは、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加することを含む、請求項８に記載の方法。
【請求項１２】
前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記第１のクエリデータは、タイプインデックスを含み、前記タイプインデックスは、所与の共通分母を有するタイプの辞書式配列内の１つのタイプを一意に識別し、前記タイプのそれぞれは、前記所与の共通分母を有する有理数のセットを備え、各タイプの有理数の前記セットを合計すると１になり、
前記方法は、さらに、
前記タイプインデックスを前記タイプにマッピングすることと、
前記タイプから前記勾配のヒストグラムを再構成することと、をさらに備え、
前記第１のクエリデータを使用して前記視覚探索を実行することは、前記再構成された勾配のヒストグラムを使用して前記視覚探索を実行することを含む、請求項８に記載の方法。
【請求項１３】
前記第１のクエリデータをアップデートすることは、
アップデートされたタイプを生成するために、前記タイプを前記第２のクエリデータでアップデートすることと、
前記アップデートされたタイプに基づいて前記画像特徴記述子を前記第２の量子化レベルで再構成することと、
を備える請求項１２に記載の方法。
【請求項１４】
前記第２のクエリデータを受信する前に、前記第１のクエリデータを使用して前記視覚探索デバイスによって維持されているデータベースの中で前記視覚探索を実行することの結果として、識別データを決定することと、
前記視覚探索を効果的に終わらせるために、前記第２のクエリデータを受信する前に前記識別データを送信することと、
をさらに備える請求項８に記載の方法。
【請求項１５】
前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子のセットを表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを受信することと、前記第３の量子化レベルは、前記第２の量子化レベルで量子化するときより正確な前記画像特徴記述子データの表現を達成し、
前記第３の量子化レベルで量子化された前記画像特徴記述子のセットを表す、２回アップデートされた第１のクエリデータを生成するために、前記アップデートされた第１のクエリデータを前記第３のクエリデータでアップデートすることと、
前記視覚探索を前記２回アップデートされた第１のクエリデータを使用して実行することと、
をさらに備える請求項８に記載の方法。
【請求項１６】
視覚探索を実行するために、クエリデータをネットワークを介して視覚探索デバイスに送信するクライアントデバイスであって、
画像を定義するデータを記憶するメモリと、
画像特徴記述子のセットを前記画像から抽出する特徴抽出ユニットと、前記画像特徴記述子は前記画像の少なくとも１つの特徴を定義し、
第１の量子化レベルで量子化された前記画像特徴記述子を表す第１のクエリデータを生成するために、前記画像特徴記述子を前記第１の量子化レベルで量子化する特徴圧縮ユニットと、
前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信するインターフェースと、を備え、
前記特徴圧縮ユニットは、前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルにおいて量子化された前記画像特徴記述子を表すように、前記第１のクエリデータを拡張する第２のクエリデータを決定し、
前記第２の量子化レベルは、前記第１の量子化レベルにおいて量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記インターフェースは、前記第１のクエリデータを連続的にリファインするために、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する、クライアントデバイス。
【請求項１７】
前記視覚探索デバイスが、前記第１の量子化レベルで量子化された前記画像特徴記述子のセットを表す前記第１のクエリデータを使用して前記視覚探索を実行することと同時に、前記インターフェースが前記第２のクエリデータを送信する、請求項１６に記載のクライアントデバイス。
【請求項１８】
前記特徴圧縮ユニットは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を決定し、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記特徴圧縮ユニットは、追加の再構成点のそれぞれが前記面のそれぞれの中心に位置するように、追加の再構成点を決定し、前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定し、前記オフセットベクトルを含むように前記第２のクエリデータを生成する、
請求項１６に記載のクライアントデバイス。
【請求項１９】
前記特徴圧縮ユニットは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を決定し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記特徴圧縮ユニットは、追加の再構成点のそれぞれが前記ボロノイセルの前記交点に位置するように追加の再構成点をさらに決定し、前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定し、前記オフセットベクトルを含むように前記第２のクエリデータを生成する、
請求項１６に記載のクライアントデバイス。
【請求項２０】
前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記特徴圧縮ユニットは、さらに、前記勾配のヒストグラムに対して最近のタイプを決定し、前記タイプは所与の共通分母を有する有理数のセットであり、前記有理数のセットの合計は１に等しい、
前記特徴圧縮ユニットは、さらに、前記決定されたタイプを、前記所与の共通分母を有するすべての可能なタイプに対して前記決定されたタイプの辞書式配列を一意に識別するタイプインデックスにマッピングし、
前記第１のクエリデータは、前記タイプインデックスを含む、
請求項１６に記載のクライアントデバイス。
【請求項２１】
前記インターフェースは、前記第２のクエリデータにより拡張された後に前記第１のクエリデータが第３のクエリデータでアップデートされると、前記連続してアップデートされた第１のクエリデータが第３の量子化レベルで量子化された前記画像特徴記述子のセットを表すように前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを送信する前に、前記視覚探索デバイスで維持されるデータベース内を探索した結果として得られた、前記視覚探索デバイスからの識別データを受信し、
前記クライアントデバイスは、前記識別データを受信することに応答して前記第３のクエリデータを送ることなく前記視覚探索を終了し、
前記クライアントデバイスは、前記識別データを使用する視覚探索アプリケーションを実行するプロセッサを含む、
請求項１６に記載のクライアントデバイス。
【請求項２２】
前記第２のクエリデータで拡張された後の前記第１のクエリデータが前記第３のクエリデータでアップデートされると、前記連続的にアップデートされた第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子のセットを表すように、前記特徴圧縮ユニットが、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを決定し、前記第３の量子化レベルは、前記第２の量子化レベルで量子化するときよりも一層正確な前記画像特徴記述子のセットの表現を達成し、
前記インターフェースは、前記第２のクエリデータで拡張された後の前記第１のクエリデータを連続的にリファインするために、前記第３のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する、
請求項１６に記載のクライアントデバイス。
【請求項２３】
クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための視覚探索デバイスであって、
画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子のセットを表す第１のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信するインターフェースと、
前記第１のクエリデータを使用して前記視覚探索を実行する特徴マッチングユニットと、
を備え、
前記インターフェースは、第２のクエリデータを前記クライアントデバイスから前記ネットワークを介してさらに受信し、
前記第２のクエリデータは、前記第１のクエリデータが前記第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルにおいて量子化された画像特徴記述子を表すように前記第１のデータを拡張し、
前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記視覚探索デバイスは、さらに、
第２の量子化レベルで量子化された前記画像特徴記述子を表す、アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートする特徴再構成ユニットを備え、
前記特徴マッチングユニットは、前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行する、
視覚探索デバイス。
【請求項２４】
前記特徴マッチングユニットは、前記第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して前記視覚探索デバイスに送信することと同時に、前記第１のクエリデータを使用して前記視覚探索を実行する、請求項２３に記載の視覚探索デバイス。
【請求項２５】
前記第１のクエリデータは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれ対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記面のそれぞれの中心に位置し、
前記特徴再構成ユニットは、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加する、請求項２３に記載の視覚探索デバイス。
【請求項２６】
前記第１のクエリデータは、前記再構成点がそれぞれ前記画像特徴記述子のセットに対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記ボロノイセルの交点に位置し、
前記特徴再構成ユニットは、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加する、
請求項２３に記載の視覚探索デバイス。
【請求項２７】
前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記第１のクエリデータはタイプインデックスを含み、前記タイプインデックスは、所与の共通分母を有するタイプの辞書式配列内の１つのタイプを一意に識別し、前記タイプのそれぞれは、前記所与の共通分母を有する有理数のセットを備え、各タイプの有理数の前記セットを合計すると１になり、
前記特徴再構成ユニットは、前記タイプインデックスを前記タイプにマッピングし、前記タイプから前記勾配のヒストグラムを再構成し、
前記特徴マッチングユニットは、前記再構成された勾配のヒストグラムを使用して前記視覚探索を実行する、
請求項２３に記載の視覚探索デバイス。
【請求項２８】
前記特徴再構成ユニットは、アップデートされたタイプを生成するために、前記タイプを前記第２のクエリデータでさらにアップデートし、前記アップデートされたタイプに基づいて前記画像特徴記述子を前記第２の量子化レベルで再構成する、請求項２７に記載の視覚探索デバイス。
【請求項２９】
前記特徴マッチングユニットは、前記第２のクエリデータを受信する前に、前記第１のクエリデータを使用して前記視覚探索デバイスによって維持されているデータベースの中で前記視覚探索を実行することの結果として、識別データを決定し、
前記インターフェースは、前記視覚探索を効果的に終了するために、前記第２のクエリデータを受信する前に前記識別データを送信する、
請求項２３に記載の視覚探索デバイス。
【請求項３０】
前記インターフェースは、前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子のセットを表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを受信し、
前記第３の量子化レベルは、前記第２の量子化レベルにおいて量子化するときより正確な前記画像特徴記述子のセットの表現を達成し、
前記特徴再構成ユニットは、前記第３の量子化レベルで量子化された前記画像特徴記述子のセットを表す、２回アップデートされた第１のクエリデータを生成するために、前記アップデートされた第１のクエリデータを前記第３のクエリデータでアップデートし、
前記特徴マッチングユニットは、前記２回アップデートされた第１のクエリデータを使用して前記視覚探索を実行する、
請求項２３に記載の視覚探索デバイス。
【請求項３１】
クエリデータをネットワークを介して視覚探索デバイスに送信するデバイスであって、
クエリ画像を定義するデータを記憶する手段と、
画像特徴記述子のセットを前記クエリ画像から抽出する手段と、前記画像特徴記述子は前記クエリ画像の少なくとも１つの特徴を定義し、
第１の量子化レベルで量子化された前記画像特徴記述子のセットを表す第１のクエリデータを生成するために、第１の量子化レベルで前記画像特徴記述子のセットを量子化する手段と、
前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する手段と、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された画像特徴記述子の前記セットを表すように、前記第１のクエリデータを拡張する第２のクエリデータを決定する手段と、前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子のセットの表現を達成し、
前記第１のクエリデータをリファインするために、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する手段と、
を備えるデバイス。
【請求項３２】
前記第２のクエリデータを送信する手段は、前記視覚探索デバイスが前記第１の量子化レベルで量子化された前記画像特徴記述子を表す前記第１のクエリデータを使用して前記視覚探索を実行するのと同時に、前記第２のクエリデータを送信する手段を備える、請求項３１に記載のデバイス。
【請求項３３】
前記第１の量子化レベルで前記画像特徴記述子を量子化する手段は、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義された異なるボロノイセルのそれぞれの中心に位置するように再構成点を決定する手段を含み、前記ボロノイセルが、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータを決定する手段は、
追加の再構成点のそれぞれが前記面のそれぞれの中心に位置するように、追加の再構成点を決定する手段と、
前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定する手段と、
前記オフセットベクトルを含むように前記第２のクエリデータを生成する手段と、
を含む請求項３１に記載のデバイス。
【請求項３４】
前記第１の量子化レベルで前記画像特徴記述子を量子化する手段は、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義された異なるボロノイセルのそれぞれの中心に位置するように再構成点を決定する手段を含み、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータを決定する手段は、
前記追加の再構成点のそれぞれが前記ボロノイセルの前記交点に位置するように追加の再構成点を決定する手段と、
前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定する手段と、
前記オフセットベクトルを含むように前記第２のクエリデータを生成する手段と、
を含む請求項３１に記載のデバイス。
【請求項３５】
前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記画像特徴記述子を第１の量子化レベルで量子化する手段は、
勾配のヒストグラムに対して最近のタイプを決定する手段と、前記タイプは所与の共通分母を有する有理数のセットであり、前記有理数のセットの合計は１に等しい、
前記決定されたタイプを、前記所与の共通分母を有するすべての可能なタイプに対して前記決定されたタイプの辞書式配列を一意に識別するタイプインデックスにマッピングする手段と、を含み、
前記第１のクエリデータは前記タイプインデックスを含む、
請求項３１に記載のデバイス。
【請求項３６】
前記第２のクエリデータにより拡張された後に前記第１のクエリデータが第３のクエリデータでアップデートされると、前記連続してアップデートされた第１のクエリデータが第３の量子化レベルで量子化された前記画像特徴記述子を表すように前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを送信する前に、前記視覚探索デバイスで維持されるデータベース内を探索した結果として得られた、前記視覚探索デバイスからの識別データを受信する手段と、
前記第３のクエリデータを送ることなく前記視覚探索を終了する手段と、
視覚探索アプリケーション中に、前記識別データを使用する手段と、
をさらに備える、請求項３１に記載のデバイス。
【請求項３７】
前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、前記連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子のセットを表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを決定する手段と、前記第３の量子化レベルは、前記第２の量子化レベルで量子化するときより正確な前記画像特徴記述子のセットの表現を達成し、
前記第２のクエリデータで拡張された後の前記第１のクエリデータを連続的にリファインするために、前記第３のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する手段と、
をさらに備える請求項３１に記載のデバイス。
【請求項３８】
クライアントデバイスから送信されるクエリデータをネットワークを介して受信し、視覚探索を実行するための視覚探索デバイスであって、
画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子のセットを表す第１のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信する手段と、
前記第１のクエリデータを使用して前記視覚探索を実行する手段と、
前記第２のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信する手段と、前記第２のクエリデータは、前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた前記第１のクエリデータが、第２の量子化レベルにおいて量子化された画像特徴記述子の前記セットを表すものとなるように前記第１のデータを拡張し、前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記第２の量子化レベルで量子化された前記画像特徴記述子を表す、アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートする手段と、
前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行する手段と、
を備える視覚探索デバイス。
【請求項３９】
前記第１のクエリデータを使用して前記視覚探索を実行する手段は、前記第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して前記視覚探索デバイスに送信することと同時に、前記第１のクエリデータを使用して前記視覚探索を実行する手段を備える、請求項３８に記載の視覚探索デバイス。
【請求項４０】
前記第１のクエリデータは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義された異なるボロノイセルのそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記面のそれぞれの中心に位置し、
前記アップデートされた第１のクエリデータを生成するために前記第１のクエリデータを前記第２のクエリデータでアップデートする手段は、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加する手段を含む、
請求項３８に記載の視覚探索デバイス。
【請求項４１】
前記第１のクエリデータは、前記再構成点がそれぞれ前記画像特徴記述子のセットに対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記ボロノイセルの交点に位置し、
前記アップデートされた第１のクエリデータを生成するために前記第１のクエリデータを前記第２のクエリデータでアップデートする手段は、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加する手段を含む、
請求項３８に記載の視覚探索デバイス。
【請求項４２】
前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記第１のクエリデータはタイプインデックスを含み、前記タイプインデックスは、所与の共通分母を有するタイプの辞書式配列内の１つのタイプを一意に識別し、前記タイプのそれぞれは、前記所与の共通分母を有する有理数のセットを備え、各タイプの有理数の前記セットを合計すると１になり、
前記視覚探索デバイスは、
前記タイプインデックスを前記タイプにマッピングする手段と、
前記タイプから前記勾配のヒストグラムを再構成する手段と、
をさらに備え、
前記第１のクエリデータを使用して前記視覚探索を実行する手段は、前記再構成された勾配のヒストグラムを使用して前記視覚探索を実行する手段を含む、請求項３８に記載の視覚探索デバイス。
【請求項４３】
前記第１のクエリデータをアップデートする手段は、
アップデートされたタイプを生成するために、前記タイプを前記第２のクエリデータでアップデートする手段と、
前記アップデートされたタイプに基づいて前記画像特徴記述子を前記第２の量子化レベルで再構成する手段と、
を備える請求項４２に記載の視覚探索デバイス。
【請求項４４】
前記第２のクエリデータを受信する前に、前記第１のクエリデータを使用して前記視覚探索デバイスによって維持されているデータベースの中で前記視覚探索を実行することの結果として、識別データを決定する手段と、
前記視覚探索を効果的に終わらせるために、前記第２のクエリデータを受信する前に前記識別データを送信する手段と、
をさらに備える請求項３８に記載の視覚探索デバイス。
【請求項４５】
前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを受信する手段と、前記第３の量子化レベルは、前記第２の量子化レベルにおいて量子化するときより正確な前記画像特徴記述子データの表現を達成し、
前記第３の量子化レベルで量子化された前記画像特徴記述子を表す、２回アップデートされた第１のクエリデータを生成するために、前記アップデートされた第１のクエリデータを前記第３のクエリデータでアップデートする手段と、
前記２回アップデートされた第１のクエリデータを使用して前記視覚探索を実行する手段と、
をさらに備える、請求項３８に記載の視覚探索デバイス。
【請求項４６】
命令を備える非一時的コンピュータ可読媒体であって、実行されたとき、１つまたは複数のプロセッサに、
クエリ画像を定義するデータを記憶させ、
前記クエリ画像の特徴を定義する画像特徴記述子を前記クエリ画像から抽出させ、
第１の量子化レベルで量子化された前記画像特徴記述子を表す第１のクエリデータを生成するために、前記画像特徴記述子を第１の量子化レベルで量子化させ、
前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信させ、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１のクエリデータを拡張する前記第２のクエリデータを決定させ、ここで、前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記第１のクエリデータを連続的にリファインするために、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信させる、
命令を備える非一時的コンピュータ可読媒体。
【請求項４７】
命令を備える非一時的コンピュータ可読媒体であって、実行されたとき、１つまたは複数のプロセッサに、
画像から抽出され、第１の量子化レベルで量子化により圧縮された画像特徴記述子を表す第１のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信させ、
前記第１のクエリデータを使用して前記視覚探索を実行させ、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた前記第１のクエリデータが、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成する第２の量子化レベルで量子化された画像特徴記述子を表すように前記第１のデータを拡張する前記第２のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信させ、
第２の量子化レベルで量子化された前記画像特徴記述子を表す、アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートさせ、
前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行させる命令を備える、非一時的コンピュータ可読媒体。
【請求項４８】
視覚探索を実行するためのネットワークシステムであって、
クライアントデバイスと、
視覚探索デバイスと、
前記視覚探索を実行するために、前記クライアントデバイスと視覚探索デバイスとを互いに通信するようにインターフェースするネットワークと、を備え、
前記クライアントデバイスは、
画像を定義するデータを記憶する非一時的コンピュータ可読媒体と、
前記画像の特徴を定義する画像特徴記述子を前記画像から抽出し、第１の量子化レベルで量子化された前記画像特徴記述子を表す第１のクエリデータを生成するために、前記第１の量子化レベルで前記画像特徴記述子を量子化するクライアントプロセッサと、
前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する第１のネットワークインターフェースと、を備え、
前記視覚探索デバイスは、
前記第１のクエリデータを前記ネットワークを介して前記クライアントデバイスから受信する第２のネットワークインターフェースと、
前記第１のクエリデータを使用して前記視覚探索を実行するサーバプロセッサと、を含み、
前記クライアントプロセッサは、前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された前記画像特徴記述子を表すように前記第１のクエリデータを拡張する前記第２のクエリデータを決定し、前記第２の量子化レベルは、前記第１の量子化レベルにおいて量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記第１のネットワークインターフェースは、前記第１のクエリデータを連続的にリファインするために、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信し、
前記第２のネットワークインターフェースは、前記第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して受信し、
前記サーバプロセッサは、第２の量子化レベルで量子化された前記画像特徴記述子を表すアップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートし、前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行する、
ネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、画像処理システムに関し、より詳細には、画像処理システムを用いて視覚探索を実行することに関する
【背景技術】
【０００２】
[0002]コンピューティングデバイスまたはコンピュータのコンテキストにおける視覚探索は、コンピュータまたは他のデバイスが、対象物および／または他の対象物の間の特徴および／もしくは１つまたは複数の画像の中の特徴に対する探索を実行することを可能にする技法を指す。視覚探索における最近の関心は、コンピュータが、部分的に隠された対象物、および／または、画像スケール、雑音、照明、および局部的な幾何学的歪みにおける変化を含む多種多様に変化する画像条件における特徴、を識別することを可能にするアルゴリズムをもたらした。この同じ期間に、カメラを特徴とするモバイルデバイスが出現したが、そのカメラは、テキストを入力するため、または場合によってはモバイルデバイスとのインターフェースのために限られたユーザインターフェースしか持ち得なかった。モバイルデバイスおよびモバイルデバイスアプリケーションの開発者は、モバイルデバイスのカメラをモバイルデバイスとのユーザインターフェースを向上させるために利用しようと努めてきた。
【０００３】
[0003]１つの向上を示すと、モバイルデバイスのユーザは、店舗で買い物をする間に任意の所与の製品の画像をキャプチャするためにモバイルデバイスのカメラを使用し得る。次いで、モバイルデバイスは、画像マッチング（matching imagery）に基づいて製品を識別するために、様々な画像について記録された特徴記述子（feature descriptor）のセットの範囲内で視覚探索アルゴリズムを開始し得る。製品を識別した後、モバイルデバイスは、次いで、インターネットの探索を開始し、当該製品が近隣の店および／またはオンライン商人から入手可能な最低価格を含む、当該識別した製品についての情報を含むウェブページを提示し得る。
【０００４】
[0004]カメラと視覚探索へのアクセスとを備えるモバイルデバイスが使用し得るアプリケーションはいくつか存在するが、視覚探索アルゴリズムは、しばしば、一般にかなりの量の電力を消費する大きな処理リソースを伴う。上述のモバイル、ポータブルおよびハンドヘルドデバイスなど、電力をバッテリに依存する電力依存型デバイス（power-conscious device）を用いて視覚探索を実行することは、特に、それらのバッテリが電気切れに近い期間中は制限されることがある。その結果、これらの電力依存型デバイスに視覚探索をそっくりそのまま実装することを回避するアーキテクチャが開発された。代わりに、視覚探索を実行する視覚探索デバイスが、電力依存型デバイスとは別個に与えられる。電力依存型デバイスは、視覚探索デバイスとともにセッションを開始し、いくつかの例では、探索要求中に画像を視覚探索デバイスに与える。視覚探索デバイスは、視覚探索を実行し、視覚探索によって識別された対象物および／または特徴を記述する探索応答を返す。このようにして、電力依存型のデバイスは、視覚探索へのアクセスを有するが、かなりの量の電力を消費するプロセッサ集約的な視覚探索を実行する必要性を回避する。
【発明の概要】
【０００５】
[0005]一般に、本開示は、「クライアントデバイス」とも呼ばれるモバイル、ポータブルまたは他の電力依存型デバイスと、視覚探索サーバとを含むネットワーク環境内で視覚探索を実行するための技法を説明する。画像をそのまま視覚探索サーバに送るのではなく、クライアントデバイスは特徴抽出を局所的に実行して、クライアントデバイス上に記憶されている画像から、いわゆる「特徴記述子」の形態で特徴を抽出する。いくつかの例では、これらの特徴記述子は、ヒストグラムを備える。本開示で説明する技法によれば、クライアントデバイスは、これらのヒストグラム特徴記述子を、連続してリファイン可能な方式で量子化し得る。このようにして、クライアントデバイスは、第１の粗い量子化レベルにおいて量子化される特徴記述子に基づく視覚探索を開始し、特徴記述子の量子化をリファインする一方、視覚探索はこの特徴記述子に関して追加の情報を必要とし得る。結果として、視覚探索を実行するために、クライアントデバイスとサーバの両方が同時に動作するので、いくらかの量の並行処理が発生し得る。
【０００６】
[0006]一例では、クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための方法を説明する。方法は、クライアントデバイスでクエリ画像を定義するデータを記憶することと、クライアントデバイスで、クエリ画像から画像特徴記述子のセットを抽出することと、を備え、画像特徴記述子はクエリ画像の少なくとも１つの特徴を定義する。方法はまた、第１の量子化レベルにおいて量子化された画像特徴記述子のセットを表す第１のクエリデータを生成するために、クライアントデバイスで、第１の量子化レベルにおいて画像特徴記述子のセットを量子化すること、クライアントデバイスで、第１のクエリデータをネットワークを介して視覚探索デバイスに送信することと、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが第２の量子化レベルにおいて量子化された画像特徴記述子のセットを表すように、第１のクエリデータを拡張する第２のクエリデータを決定することと、第２の量子化レベルは、第１の量子化レベルにおいて量子化するときに得られたものより精細または正確な画像特徴記述子のセットの表現が得られ、第１のクエリデータをリファインするために、クライアントデバイスで、第２のクエリデータをネットワークを介して視覚探索デバイスに送信ことと、を備える。
【０００７】
[0007]別の例では、クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための方法を説明する。方法は、視覚探索デバイスで、第１のクエリデータをクライアントデバイスからネットワークを介して受信することと、第１のクエリデータは、画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子のセットを表し、視覚探索デバイスで、第１のクエリデータを使用して視覚探索を実行し、第２のクエリデータをクライアントデバイスからネットワークを介して受信することと、を備え、第２のクエリデータは、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルにおいて量子化された画像特徴記述子のセットを表すように第１のクエリデータを拡張し、第２の量子化レベルは、第１の量子化レベルにおいて量子化するときに得られたものより精細または正確な画像特徴記述子の表現が得られる。方法はまた、第２の量子化レベルにおいて量子化された画像特徴記述子を表すアップデートされた第１のクエリデータを生成するために、視覚探索デバイスで、第１のクエリデータを第２のクエリデータでアップデートすることと、視覚探索デバイスで、アップデートされた第１のクエリデータを使用して視覚探索を実行することと、を備える。
【０００８】
[0008]別の例では、視覚探索を実行するためにクエリデータをネットワークを介して視覚探索デバイスに送信するクライアントデバイスを説明する。クライアントデバイスは、画像を定義するデータを記憶するメモリと、画像から、画像の少なくとも１つの特徴を定義する画像特徴記述子のセットを抽出する特徴抽出ユニットと、第１の量子化レベルにおいて量子化された画像特徴記述子を表す第１のクエリデータを生成するために、画像特徴記述子を第１の量子化レベルにおいて量子化する特徴圧縮ユニットと、第１のクエリデータをネットワークを介して視覚探索デバイスに送信するインターフェースと、を備える。特徴圧縮ユニットは、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルにおいて量子化された画像特徴記述子を表すように、第１のクエリデータを拡張する第２のクエリデータを決定し、第２の量子化レベルは、第１の量子化レベルにおいて量子化するときに得られたものより精細で正確な画像特徴記述子の表現が得られる。インターフェースは、第１のクエリデータを連続してリファインするために、第２のクエリデータをネットワークを介して視覚探索デバイスに送信する。
【０００９】
[0009]別の例では、クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための視覚探索デバイスを説明する。視覚探索デバイスは、画像から抽出され、第１の量子化レベルにおける量子化により圧縮された画像特徴記述子のセットを表す第１のクエリデータを、クライアントデバイスからネットワークを介して受信するインターフェースと、第１のクエリデータを使用して視覚探索を実行する特徴マッチングユニットとを備える。インターフェースは、さらに、第２のクエリデータをクライアントデバイスからネットワークを介して受信し、第２のクエリデータは、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルにおいて量子化された画像特徴記述子を表すように第１のクエリデータを拡張し、第２の量子化レベルは、第１の量子化レベルにおいて量子化するときに得られたものより精細で正確な画像特徴記述子の表現が得られる。視覚探索デバイスはまた、第２の量子化レベルにおいて量子化された画像特徴記述子を表すアップデートされた第１のクエリデータを生成するために、第１のクエリデータを第２のクエリデータでアップデートする特徴再構成ユニットを備える。特徴マッチングユニットは、アップデートされた第１のクエリデータを使用して視覚探索を実行する。
【００１０】
[0010]別の例では、クエリデータをネットワークを介して視覚探索デバイスに送信するデバイスを説明する。デバイスは、クエリ画像を定義するデータを記憶する手段と、クエリ画像の少なくとも１つの特徴を定義する画像特徴記述子のセットをクエリ画像から抽出する手段と、第１の量子化レベルで量子化された画像特徴記述子のセットを表す第１のクエリデータを生成するために、画像特徴記述子のセットを第１の量子化レベルで量子化する手段とを備える。方法はまた、第１のクエリデータをネットワークを介して視覚探索デバイスに送信する手段と、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された画像特徴記述子のセットを表すように、第１のクエリデータを拡張する第２のクエリデータを決定する手段と、第２の量子化レベルは、第１の量子化レベルで量子化するときに得られたものより正確な画像特徴記述子のセットの表現が得られ、第１のクエリデータをリファインするために第２のクエリデータをネットワークを介して視覚探索デバイスに送信する手段と、を備える。
【００１１】
[0011]別の例では、クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するためのデバイスを説明する。デバイスは、画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子のセットを表す第１のクエリデータをクライアントデバイスからネットワークを介して受信する手段と、第１のクエリデータを使用して視覚探索を実行する手段と、第２のクエリデータをクライアントデバイスからネットワークを介して受信する手段と、を備え、第２のクエリデータは、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された画像特徴記述子のセットを表すように第１のクエリデータを拡張し、第２の量子化レベルは、第１の量子化レベルで量子化するときに得られたものより正確な画像特徴記述子の表現が得られる。デバイスはまた、第２の量子化レベルで量子化された画像特徴記述子を表すアップデートされた第１のクエリデータを生成するために、第１のクエリデータを前記第２のクエリデータでアップデートする手段と、アップデートされた第１のクエリデータを使用して視覚探索を実行する手段とを備える。
【００１２】
[0012]別の例では、非一時的コンピュータ可読媒体は、実行させると、１つまたは複数のプロセッサに、クエリ画像を定義するデータを記憶させ、クエリ画像の特徴を定義する画像特徴記述子をクエリ画像から抽出させ、第１の量子化レベルで量子化された画像特徴記述子を表す第１のクエリデータを生成するために、画像特徴記述子を第１の量子化レベルで量子化させ、第１のクエリデータをネットワークを介して視覚探索デバイスに送信させ、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された画像特徴記述子を表すように、第１のクエリデータを拡張する第２のクエリデータを決定させ、第２の量子化レベルは、第１の量子化レベルで量子化するときに得られたものより正確な画像特徴記述子の表現が得られ、第１のクエリデータを連続してリファインするために第２のクエリデータをネットワークを介して視覚探索デバイスに送信させる、命令を備える。
【００１３】
[0013]別の例では、非一時的コンピュータ可読媒体は、実行されると、１つまたは複数のプロセッサに、画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子を表す第１のクエリデータをクライアントデバイスからネットワークを介して受信させ、第１のクエリデータを使用して視覚探索を実行させ、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された画像特徴記述子を表すように第１のクエリデータを拡張する第２のクエリデータを、クライアントデバイスからネットワークを介して受信させ、第２の量子化レベルは、第１の量子化レベルで量子化するときに得られたものより正確な画像特徴記述子の表現が得られ、第２の量子化レベルで量子化された画像特徴記述子を表すアップデートされた第１のクエリデータを生成するために、第１のクエリデータを第２のクエリデータでアップデートさせ、アップデートされた第１のクエリデータを使用して視覚探索を実行させる、命令を備える。
【００１４】
[0014]別の例では、視覚探索を実行するためのネットワークシステムを説明する。ネットワークシステムは、クライアントデバイスと、視覚探索デバイスと、視覚探索を実行するために互いに通信するためにクライアントデバイスと視覚探索デバイスとをインターフェースするネットワークとを備える。クライアントデバイスは、画像を定義するデータを記憶する非一時的コンピュータ可読媒体と、画像の特徴を定義する画像特徴記述子を画像から抽出し、第１の量子化レベルで量子化された画像特徴記述子を表す第１のクエリデータを生成するために、画像特徴記述子を第１の量子化レベルで量子化するクライアントプロセッサと、第１のクエリデータをネットワークを介して視覚探索デバイスに送信する第１のネットワークインターフェースとを含む。視覚探索デバイスは、第１のクエリデータをクライアントデバイスからネットワークを介して受信する第２のネットワークインターフェースと、第１のクエリデータを使用して視覚探索を実行するサーバプロセッサとを含む。クライアントプロセッサは、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された画像特徴記述子を表すように第１のクエリデータを拡張する第２のクエリデータを決定し、第２の量子化レベルは、第１の量子化レベルで量子化するときに得られるものより正確な画像特徴記述子の表現が得られる。第１のネットワークインターフェースは、第１のクエリデータを連続してリファインするために、第２のクエリデータをネットワークを介して視覚探索デバイスに送信する。第２のネットワークインターフェースは、第２のクエリデータをクライアントデバイスからネットワークを介して受信する。サーバは、第２の量子化レベルで量子化された画像特徴記述子を表すアップデートされた第１のクエリデータを生成するために第１のクエリデータを第２のクエリデータでアップデートし、アップデートされた第１のクエリデータを使用して視覚探索を実行する。
【図面の簡単な説明】
【００１５】
【図１】本開示で説明する、連続的にリファイン可能な特徴記述子量子化技法を実装する画像処理システムを示すブロック図。
【図２】図１の特徴圧縮ユニットをより詳細に示すブロック図。
【図３】図１の特徴再構成ユニットをより詳細に示すブロック図。
【図４】本開示で説明する、連続的にリファイン可能な特徴記述子量子化技法を実装する際の、視覚探索クライアントデバイスの例示的な動作を示すフローチャート。
【図５】本開示で説明する、連続的にリファイン可能な特徴記述子量子化技法を実装する際の、視覚探索サーバの例示的な動作を示すフローチャート。
【図６】特徴抽出ユニットがキーポイント抽出の実行において使用するためにガウシアン差分（ＤｏＧ：difference of Gaussian）ピラミッドを決定するプロセスを示す図。
【図７】ガウシアン差分（ＤｏＧ）ピラミッドを決定した後のキーポイントの検出を示す図。
【図８】特徴抽出ユニットが勾配分布と方向ヒストグラムとを決定するプロセスを示す図。
【図９Ａ】本開示で説明する技法によって求められた特徴記述子と再構成点とを示すグラフ。
【図９Ｂ】本開示で説明する技法によって求められた特徴記述子と再構成点とを示すグラフ。
【図１０】本開示で説明する技法を実装するシステムに関する待ち時間を示す時間図 (time diagram)。
【発明を実施するための形態】
【００１６】
[0025]一般に、本開示は、「クライアントデバイス」とも呼ばれるモバイル、ポータブルまたは他の電力依存型デバイス、ならびに視覚探索サーバを含むネットワーク環境内で視覚探索を実行するための技法を説明する。画像をそっくりそのまま視覚探索サーバに送るのではなく、いわゆる「特徴記述子」の形式でクライアントデバイス上に記憶されている画像から特徴を抽出するために、クライアントデバイスは特徴抽出を局所的に実行する。いくつかの例では、これらの特徴記述子は、ヒストグラムを備える。本開示で説明する技法によれば、クライアントデバイスは、これらの特徴記述子（やはり、ヒストグラムの形態であることが多い）を連続的にリファイン可能な方式で量子化することができる。このようにして、クライアントデバイスは、第１の粗い量子化レベルで量子化された特徴記述子に基づく視覚探索を開始するが、視覚探索がこの特徴記述子に関して追加の情報を必要とする場合は、特徴記述子の量子化をリファインする。結果として、視覚探索を実行するために、クライアントデバイスとサーバの両方が同時に動作するので、いくらかの量の並行処理が発生し得る。
【００１７】
[0026]たとえば、クライアントデバイスは、特徴記述子を、最初に第１の粗い量子化レベルで量子化する。この粗く量子化された特徴記述子は次に第１のクエリデータとして視覚探索サーバに送られ、視覚探索サーバは、続いて、この第１のクエリデータに基づいて視覚探索を実行し得る。この視覚探索を粗く量子化された特徴記述子を用いて実行している間に、クライアントデバイスは、第１のクエリデータが第２のクエリデータでアップデートされると、アップデートされた第１のクエリデータが、第２の量子化レベルで量子化されたヒストグラム特徴記述子を表すように第１のクエリデータを拡張する追加のまたは第２のクエリデータを決定し得る。
【００１８】
[0027]このようにして、本技法は、視覚探索サーバが視覚探索を実行しているのと同時に、クエリデータがクライアントデバイスによって繰返し決定および視覚探索サーバに提供されることで、視覚探索の実行に関連する待ち時間を低減することができる。したがって、全画像を送信し、その送信でかなりの量の帯域幅を費やし、さらに視覚探索サーバが視覚探索を完了するのを待つのではなく、本技法は特徴記述子を送り、それにより帯域幅を節約する。その上、本技法は、画像特徴記述子をそっくりそのまま送ることを回避し、かつ待ち時間を低減する方式で画像特徴記述子を連続的にリファインする方法を提供することができる。本技法は、アップデートされたクエリデータが、より精細でより完全または正確な量子化レベルで量子化された画像特徴記述子をもたらすように、前に送られたクエリデータをアップデート可能にする方式で、ビットストリームまたはクエリデータを綿密に構成することによってこの待ち時間の低減を達成し得る。
【００１９】
[0028]図１は、本開示で説明する連続的にリファイン可能な量子化技法を実装する画像処理システム１０を示すブロック図である。図１の例では、画像処理システム１０は、クライアントデバイス１２と、視覚探索サーバ１４と、ネットワーク１６とを含む。クライアントデバイス１２は、この例において、ラップトップ、いわゆるネットブック、携帯情報端末（ＰＤＡ）、セルラーもしくはモバイルの電話もしくはハンドセット（いわゆる「スマートフォン」を含む）、全地球測位システム（ＧＰＳ）デバイス、デジタルカメラ、デジタルメディアプレーヤ、ゲームデバイス、または視覚探索サーバ１４と通信可能な任意の他のモバイルデバイスのようなモバイルデバイスを表す。本開示では、モバイルクライアントデバイス１２に関して説明するが、本開示で説明する技法は、この点についてモバイルクライアントデバイスに限定されるべきではない。代わりに、本技法は、ネットワーク１６または任意の他の通信媒体を介して視覚探索サーバ１４と通信可能な任意のデバイスによって実装されてよい。
【００２０】
[0029]視覚探索サーバ１４は、一般的には伝送制御プロトコル（ＴＣＰ）接続の形態で接続を受け、クエリデータを受信して識別データを供給するためのＴＣＰセッションを形成するためにそれ自体のＴＣＰ接続で応答するサーバデバイスを表す。視覚探索サーバ１４は、視覚探索サーバは、画像内の１つもしくは複数の特徴または対象物を識別するための視覚探索アルゴリズムを実行するかあるいは実装するという点で、視覚探索サーバデバイスを代表し得る。いくつかの例では、視覚探索サーバ１４は、モバイルクライアントデバイスをパケット交換ネットワークまたはデータネットワークに相互接続するセルラーアクセスネットワークの基地局の中に配置され得る。
【００２１】
[0030]ネットワーク１６は、クライアントデバイス１２と視覚探索サーバ１４とを相互接続するインターネットのような公衆ネットワークを表す。通常、ネットワーク１６は、クライアントデバイス１２と視覚探索サーバ１４との間で通信またはデータを転送することを可能にするために、ＯＳＩ（open system interconnection）モデルの様々な層を実装する。ネットワーク１６は、一般的には、クライアントデバイス１２と視覚探索サーバ１４との間のデータの転送を可能にするスイッチ、ハブ、ルータ、サーバなど、任意の数のネットワークデバイスを含む。単一のネットワークとして示しているが、ネットワーク１６は、ネットワーク１６を形成するために相互接続される、１つまたは複数のサブネットワークを備えてもよい。これらのサブネットワークは、ネットワーク１６全体を介してデータの転送を提供するために公衆ネットワーク内で共通に使用される、サービスプロバイダネットワーク、アクセスネットワーク、バックエンドネットワーク、または任意の他の種類のネットワークを備えてよい。本例では公衆ネットワークとして説明するが、ネットワーク１６は、一般に公衆がアクセスできないプライベートネットワークを備えてもよい。
【００２２】
[0031]図１の例に示すように、クライアントデバイス１２は、特徴抽出ユニット１８と、特徴圧縮ユニット２０と、インターフェース２２と、ディスプレイ２４とを含む。特徴抽出ユニット１８は、圧縮勾配ヒストグラム（ＣＨｏＧ：compressed histogram of gradients）アルゴリズム、または特徴をヒストグラムの形式で抽出し、これらのヒストグラムをタイプとして量子化する任意の他の特徴記述抽出アルゴリズムなどの特徴抽出アルゴリズムによる特徴抽出を実行するユニットを表す。一般に、特徴抽出ユニット１８は、クライアントデバイス１２の中に含まれるカメラまたは他の画像キャプチャデバイス（図１の例に示さず）を使用してローカルにキャプチャされ得る画像データ２６上で動作する。代替として、クライアントデバイス１２は、この画像データ２６をネットワーク１６からダウンロードする方法によってこの画像データ自体をキャプチャすることなく、別のコンピューティングデバイスとのワイヤード接続を介して、または任意の他のワイヤードもしくはワイヤレスの形態の通信を介して、ローカルに画像データ２６を記憶し得る。
【００２３】
[0032]以下により詳細に説明するが、要約すれば、特徴抽出ユニット１８は、２つの連続するガウスぼけ画像（Gaussian-blurred image）を生成するためにガウスぼかし画像（Gaussian blurring image）データ２６によって特徴記述子２８を抽出し得る。ガウスぼかしは、一般に、定義されたスケールで、ガウスぼかし関数（Gaussian blur function）を用いて画像データ２６を畳み込むことを伴う。特徴抽出ユニット１８は画像データ２６を増加的に畳み込み、得られた複数のガウスぼけ画像は、スケール空間内の定数によって互いに分離される。次いで、特徴抽出ユニット１８は、「ガウシアンピラミッド」または「ガウシアンピラミッドの差分」とも呼ばれるものを形成するために、これらのガウスぼけ画像を積み重ねる。次いで、特徴抽出ユニット１８は、ガウシアン差分（ＤｏＧ）画像を生成するために、２つの連続して積み重ねられたガウスぼけ画像を比較する。ＤｏＧ画像は、「ＤｏＧ空間」と呼ばれるものを形成し得る。
【００２４】
[0033]このＤｏＧ空間に基づいて、特徴抽出ユニット１８は、キーポイントを検出し得、キーポイントは、画像データ２６の中の幾何学的観点から潜在的に関心のある特定のサンプル点または画素の周りの画素の領域またはパッチのことをいう。一般に、特徴抽出ユニット１８は、キーポイントを、構成されたＤｏＧ空間内の局所的最大値および／または局所的最小値として識別する。次いで、特徴抽出ユニット１８は、キーポイントが検出されたパッチに対する局所画像の勾配の方向に基づいて、１つまたは複数の方向（orientation）または方向(direction)をこれらのキーポイントに割り当てる。これらの方向（orientation）を特徴付けるために、特徴抽出ユニット１８は、勾配方向ヒストグラムの観点から方向（orientation）を定義し得る。次いで、特徴抽出ユニット１８は、特徴記述子２８を、位置および方向として（たとえば、勾配方向ヒストグラムによって）定義する。特徴記述子２８を定義した後、特徴抽出ユニット１８は、この特徴記述子２８を特徴圧縮ユニット２０に出力する。特徴抽出ユニット１８は、このプロセスを使用して特徴記述子２８のセットを出力し得る。
【００２５】
[0034]特徴圧縮ユニット２０は、特徴記述子２８のような特徴記述子を定義するために使用されるデータの量を、これらの特徴記述子を定義するために特徴抽出ユニット１８によって使用されるデータの量に対して圧縮または低減するユニットを表す。特徴記述子を圧縮するために、特徴圧縮ユニット２０は、タイプ量子化（type quantization）と呼ばれる量子化の形態を実行して、特徴記述子２８を圧縮する。この点において、特徴記述子２８によって定義されたヒストグラムをそのまま送るのではなく、特徴圧縮ユニット２０はタイプ量子化を実行して、ヒストグラムをいわゆる「タイプ」として表す。一般に、タイプは、ヒストグラムの圧縮された表現である（たとえば、タイプは、ヒストグラム全体ではなくヒストグラムの形状を表す）。タイプは、一般に、シンボルの度数のセットを表し、ヒストグラムのコンテキストにおいて、ヒストグラムの勾配分布の度数を表し得る。言い換えれば、タイプは、対応する１つの特徴記述子２８を作り出したソースの真の分布の推定を表す。この点において、タイプは、特定のサンプルに基づいて推定されうるので、タイプの符号化および送信は、分布の形状を符号化し送信することと等価であるものと見なされ得る（すなわち、タイプは、この例では対応する１つの特徴記述子２８で定義されるヒストグラムである）。
【００２６】
[0035]特徴記述子２８および量子化レベル（本明細では「ｎ」で数学的に示され得る）が与えられれば、特徴圧縮ユニット２０は、特徴記述子２８の各々に対してパラメータｋ1、．．．、ｋm（ここでｍは次元の数を示す）を有するタイプを計算する。各タイプは、所与の共通分母を有する有理数のセットを表し得、ここで有理数の合計は１である。次いで、特徴記述子２８は、このタイプを、辞書式列挙を用いてインデックスとして符号化し得る。言い換えれば、所与の共通分母を有するすべての可能なタイプに対して、特徴圧縮ユニット２８は、これらのタイプの辞書式順序付けに基づいてこれらのタイプの各々にインデックスを有効に割り当てる。それにより、特徴圧縮ユニット２８は、特徴記述子２８を単一の辞書式に配列されたインデックスに圧縮し、これらの圧縮された特徴記述子をクエリデータ３０Ａ、３０Ｂの形態でインターフェース２２に出力する。
【００２７】
[0036]辞書式配列に関して説明するが、本技法は、そのような配列がクライアントデバイスと視覚探索サーバの両方に提供される限り、任意の他の種類の配列に対して使用されてよい。いくつかの例では、クライアントデバイスは、配列モードを視覚探索サーバに通知し得、クライアントデバイスと視覚探索サーバとは配列モードをネゴシエートし得る。他の例では、この配列モードは、視覚探索を実行することに関する通知および他のオーバーヘッドを回避するために、クライアントデバイスと視覚探索サーバの両方において静的に構成されてよい。
【００２８】
[0037]インターフェース２２は、ワイヤレスインターフェースとワイヤードインターフェースとを含むネットワーク１６を介して視覚探索サーバ１４と通信可能な任意の種類のインターフェースを表す。インターフェース２２は、ワイヤレスセルラーインターフェースを表し得、必要なハードウェア、または、アンテナ、変調器などの他の構成要素を含み、ワイヤレスセルラーネットワークを介してネットワーク１６と通信し、ネットワーク１６を介してかつ視覚探索サーバ１４と通信する。この例では、図１の例に示していないが、ネットワーク１６はワイヤレスセルラーアクセスネットワークを含み、それによって、ワイヤレスセルラーインターフェース２２は、ネットワーク１６と通信する。ディスプレイ２４は、画像データ２６または任意の他の種類のデータなどの画像を表示可能な任意の種類のディスプレイユニットを表す。ディスプレイ２４は、たとえば、発光ダイオード（ＬＥＤ）ディスプレイデバイス、有機ＬＥＤ（ＯＬＥＤ）ディスプレイデバイス、液晶ディスプレイ（ＬＣＤ）デバイス、プラズマディスプレイデバイス、または任意の他の種類のディスプレイデバイスを表し得る。
【００２９】
[0038]視覚探索サーバ１４は、インターフェース３２と、特徴再構成ユニット３４と、特徴マッチングユニット３６と、特徴記述子データベース３８とを含む。インターフェース３２は、それが、ネットワーク１６などのネットワークと通信可能な任意の種類のインターフェースを表し得るという点で、インターフェース２２に類似し得る。特徴再構成ユニット３４は、圧縮された特徴記述子から特徴記述子を再構成するために、圧縮された特徴記述子を解凍するユニットを表す。特徴再構成ユニット３４は、それが、圧縮された特徴記述子から特徴記述子を再構成するために量子化の逆（しばしば、再構成と呼ばれる）を実行することで、特徴圧縮ユニット２０によって実行される動作と逆の動作を実行し得る。特徴マッチングユニット３６は、再構成された特徴記述子に基づいて画像データ２６内の１つまたは複数の特徴または対象物を識別するために特徴マッチングを実行するユニットを表す。特徴マッチングユニット３６は、この特徴識別を実行するために特徴記述子データベース３８にアクセスし、特徴記述子データベース３８は、特徴記述子を定義し、これらの特徴記述子のうちの少なくともいくつかを画像データ２６から抽出された、対応する特徴または対象物を識別する識別データと関連付けるデータを記憶する。再構成された特徴記述子４０Ａ（本明細では「クエリデータ４０Ａ」とも呼ばれ、このデータは視覚探索またはクエリを実行するために使用される視覚探索クエリデータを表す）のような再構成された特徴記述子に基づいて画像データ２６から抽出された特徴または対象物を首尾よく識別すると、特徴マッチングユニット３６は、この識別データを識別データ４２として返す。
【００３０】
[0039]最初に、クライアントデバイス１２のユーザが、視覚探索を開始するためにクライアントデバイス１２と対話する。ユーザは、画像データ２６を選択するためにユーザインターフェースまたはディスプレイ２４によって提示される他の種類のインターフェースと対話し、次いで、視覚探索を開始して、画像データ２６として記憶された画像の焦点である１つまたは複数の特徴または対象物を識別する。たとえば、画像データ２６は、１個の有名なアートワークの画像を示す。ユーザは、この画像を、クライアントデバイス１２の画像キャプチャユニット（たとえば、カメラ）を使用してキャプチャし、または代替として、この画像を、ネットワーク１６から、または別のコンピューティングデバイスとのワイヤードもしくはワイヤレス接続を介してローカルにダウンロードしている。いずれの場合も、画像データ２６を選択したのち、ユーザは、この例では、１個の有名なアートワークを、たとえば名前、アーティスト、および完成日によって識別するために、視覚探索を開始する。
【００３１】
[0040]視覚探索を開始したことに応答して、クライアントデバイス１２は、特徴抽出ユニット１８を起動して、画像データ２６の分析を介して発見された、いわゆる「キーポイント」のうちの１つを表現する少なくとも１つの特徴記述子２８を抽出する。特徴抽出ユニット１８は、この特徴記述子２８を特徴圧縮ユニット２０に転送し、特徴圧縮ユニット２０は、続いて、特徴記述子２８を圧縮し、クエリデータ３０Ａを生成する。特徴圧縮ユニット２０は、クエリデータ３０Ａをインターフェース２２に出力し、インターフェース２２は、クエリデータ３０Ａをネットワーク１６を介して視覚探索サーバ１４に転送する。
【００３２】
[0041]視覚探索サーバ１４のインターフェース３２は、クエリデータ３０Ａを受信する。クエリデータ３０Ａを受信したことに応答して、視覚探索サーバ１４は、特徴再構成ユニット３４を起動する。特徴再構成ユニット３４は、クエリデータ３０Ａに基づいて特徴記述子２８を再構成することを試み、再構成された特徴記述子４０Ａを出力する。特徴マッチングユニット３６は、再構成された特徴記述子４０Ａを受信し、特徴記述子４０Ａに基づいて特徴マッチングを実行する。特徴マッチングユニット３６は、特徴記述子データベース３８にアクセスし、特徴記述子データベース３８によってデータとして記憶されている特徴記述子をトラバースして実質的にマッチする特徴記述子を識別することによって特徴マッチングを実行する。再構成された特徴記述子４０Ａに基づいて画像データ２６から抽出された特徴を首尾よく識別すると、特徴マッチングユニット３６は、再構成された特徴記述子４０Ａにある程度（しばしば、閾値で表される）マッチする、特徴記述子データベース３８内に記憶されている特徴記述子に関連付けられた識別データ４２を出力する。インターフェース３２は、この識別データ４２を受信し、識別データ４２をネットワーク１６を介してクライアントデバイス１２に転送する。
【００３３】
[0042]クライアントデバイス１２のインターフェース２２は、この識別データ４２を受信し、この識別データ４２をディスプレイ２４で提示する。すなわち、インターフェース２２は、識別データ４２をディスプレイ２４に転送し、次いでディスプレイ２４は、この識別データ４２を、画像データ２６に対する視覚探索を開始するために使用されるユーザインターフェースなどのユーザインターフェースを介して提示または表示する。この例では、識別データ４２は、１個のアートワークの名前と、アーティストの名前と、１個のアートワークの完成日と、この１個のアートワークに関連する任意の他の情報とを備え得る。いくつかの例では、インターフェース２２は、識別データを、クライアントデバイス１２内で実行している視覚探索アプリケーションに転送し、次いで、クライアントデバイス１２は、この識別データを（たとえば、この識別データをディスプレイ２４を介して提示することによって）使用する。
【００３４】
[0043]本開示では、開示する技法を実行するように構成されたデバイスの機能的態様を強調するために様々な構成要素、モジュール、またはユニットについて説明したが、これらのユニットを、必ずしも異なるハードウェアユニットによって実現する必要はない。むしろ、様々なユニットが、コンピュータ可読媒体に記憶されている好適なソフトウェアおよび／またはファームウェアとともに、上記で説明したように１つまたは複数のプロセッサを含んで、ハードウェアユニットにおいて組み合わせられるか、または相互動作ハードウェアユニットの集合によって与えられ得る。この点において、本開示におけるユニットを参照することは、個別のハードウェアユニットならびに／またはハードウェアおよびソフトウェアユニットとして実装されてもされなくてもよい異なる機能ユニットを示唆することが意図されている。
【００３５】
[0044]この形態のネットワーク視覚探索を実行することにおいて、クライアントデバイス１２は、電力またはエネルギーを消費するが、これらのデバイスが、携帯性と、特徴記述子２８を抽出することと、次いでこれらの特徴記述子２８を圧縮してクエリデータ３０Ａを生成することとを可能にするために、バッテリまたは他のエネルギー貯蔵デバイスを使用するという意味におけるモバイルデバイスまたはポータブルデバイスコンテキストにおいて、電力またはエネルギーは、しばしば制限される。いくつかの例では、特徴圧縮ユニット２０は、特徴記述子２８を圧縮するために起動されなくてもよい。たとえば、クライアントデバイス１２は、利用可能な電力またはエネルギーが、利用可能電力の２０％など、利用可能電力の一定の閾値より低いことを検出すると、特徴圧縮ユニット２０を起動しない。クライアントデバイス１２は、帯域幅消費と電力消費とのバランスをとるために、これらの閾値を設けることができる。
【００３６】
[0045]通常、帯域幅消費は、ワイヤレスセルラーアクセスネットワークとインターフェースするモバイルデバイスにとって重要であり、なぜなら、これらのワイヤレスセルラーアクセスネットワークは、固定料金に対して限定された量の帯域幅しか提供され得ず、またはいくつかの例では、消費される帯域幅のキロバイトごとに課金されるからである。上記の閾値を超えるときなど、圧縮が可能でない場合、クライアントデバイス１２は、最初に特徴記述子２８を圧縮することなくクエリデータ３０Ａとして特徴記述子２８を送る。圧縮を回避することで電力が節約される一方で、圧縮されていない特徴記述子２８をクエリデータ３０Ａとして送ることで、消費される帯域幅の量が増加し、その結果、視覚探索を実行することに関連するコストが増加する可能性がある。この意味で、電力消費と帯域幅消費の両方が、ネットワーク視覚探索を実行するときに重要となる。
【００３７】
[0046]ネットワーク視覚探索に関する別の重要な点は待ち時間である。通常、特徴記述子２８は、それぞれが８ビン（bin）を有する１６のヒストグラムからから導出された１２８要素のベクトルとして定義される。特徴記述子２８の圧縮は、少ないデータを通信することが、概して比較的より多くのデータを通信することよりもかかる時間は少ないという点で、待ち時間を低減し得る。圧縮は、特徴記述子２８を送る合計時間に関して待ち時間を低減する一方で、ネットワーク１６は、特徴記述子２８をクライアントデバイス１２から視覚探索サーバ１４に送信するためにネットワーク１６がかかる時間の量に関する待ち時間をもたらす。この待ち時間は、特に、画像の１つまたは複数の対象物を確実に識別するために多くの特徴記述子が必要とされるとのような多くの待ち時間がもたらされる場合に、ユーザのエクスペリエンスを低減するか、またはそれに悪影響を及ぼす可能性がある。いくつかの例では、追加の遅延を挿入する追加の特徴記述子を要求することによって視覚探索の実行を継続するのではなく、視覚探索サーバ１４は、視覚探索を停止または休止して、探索が失敗したことを示す情報データ４２を返す。
【００３８】
[0047]本開示で説明する技法によれば、クライアントデバイス１２の特徴圧縮ユニット２０は、特徴記述子２８を連続的にリファイン可能な量子化を伴う形態の特徴記述子圧縮を実行する。言い換えれば、画像データ２６をそのまま、圧縮されていない特徴記述子２８、またはさらに所与の所定の量子化レベルで量子化された特徴記述子２８を送るのではなく（通常、実験として到達する）、本技法は、第１の量子化レベルで量子化された特徴記述子２８を表すクエリデータ３０Ａを生成する。この第１の量子化レベルは、一般に、特徴記述子２８などの特徴記述子を量子化するために従来から使用されている所与の所定の量子化レベルよりも精細でなくまたは完全でない。
【００３９】
[0048]次いで、特徴圧縮ユニット２０は、クエリデータ３０Ａがクエリデータ３０Ｂでアップデートされると、アップデートされた第１のクエリデータ３０Ａが、第１の量子化レベルで量子化されるときに達成されるよりもより完全な特徴記述子２８を表現する（すなわち、より低い量子化の程度）第２の量子化レベルで量子化された特徴記述子２８を表すように、クエリデータ３０Ａを拡張する方式でクエリデータ３０Ｂを決定し得る。この意味で、特徴圧縮ユニット２０は、第１のクエリデータ３０Ａが生成され、次いで特徴記述子２８のより完全な表現となるように第２のクエリデータ３０Ｂで引き続いて更新されることで、特徴記述子２８の量子化を連続的にリファインすることができる。
【００４０】
[0049]クエリデータ３０Ａが、概して、従来特徴記述子を量子化するために使用されるレベルほど精細でない第１の量子化レベルにおいて量子化された特徴記述子２８を表すことを考慮すると、本技法によって編成されたクエリデータ３０Ａは、従来量子化された特徴記述子より小さいサイズであり得、そのことで、帯域幅消費が低減され、同時に待ち時間が改善され得る。その上、クライアントデバイス１２は、クエリデータ３０Ｂを拡張するクエリデータ３０Ｂを決定する間に、クエリデータ３０Ａを送信し得る。次いで、クライアントデバイス１２によるクエリデータ３０Ｂの決定と同時に、視覚探索サーバ１６は、クエリデータ３０Ａを受信し、視覚探索を開始し得る。このようにして、クエリデータ３０Ａを拡張するクエリデータ３０Ｂを決定する間に視覚探索を実行するという同時性の性質によって、待ち時間が大幅に低減され得る。
【００４１】
[0050]動作時、クライアントデバイス１２は、上記のようにクエリ画像を定義する画像データ２６を記憶する。特徴抽出ユニット１８は、クエリ画像の特徴を定義する画像データ２６から画像特徴記述子２８を抽出する。次いで、特徴圧縮ユニット２０は、第１の量子化レベルで特徴記述子２８を量子化して、第１の量子化レベルで量子化された特徴記述子２８を表す第１のクエリデータ３０Ａを生成するために、本開示で説明する技法を実装する。第１のクエリデータ３０Ａは、第２のクエリデータ３０Ｂでアップデートされると第１のクエリデータ３０Ａを引き続いて拡張することが可能になるように定義される。特徴圧縮ユニット２０は、このクエリデータ３０Ａをインターフェース２２に転送し、インターフェース２２は、クエリデータ３０Ａを視覚探索サーバ１４に送信する。視覚探索サーバ１４のインターフェース３２は、クエリデータ３０Ａを受信し、その後、視覚探索サーバ１４は、特徴記述子２８を再構成するために特徴再構成ユニット３４を起動する。次いで、特徴再構成ユニット３４は、再構成された特徴記述子４０Ａを出力する。次いで、特徴マッチングユニット３６が、再構成された特徴記述子４０Ａに基づいて特徴記述子データベース３８にアクセスすることによって視覚探索を実行する。
【００４２】
[0051]特徴マッチングユニット３６が、再構成された特徴記述子４０Ａを使用して視覚探索を実行するのと並行して、特徴圧縮ユニット２０は、第１のクエリデータ３０Ａが第２のクエリデータ３０Ｂでアップデートされると、アップデートされた第１のクエリデータ３０Ａが、第２の量子化レベルで量子化された特徴記述子２８を表すように第１のクエリデータ３０Ａを拡張する第２のクエリデータ３０Ｂを決定する。再び、この第２の量子化レベルは、第１の量子化レベルで量子化するときに達成されるものより精細かまたはより完全な特徴記述子２８の表現を達成する。次いで、特徴圧縮ユニット２０は、クエリデータ３０Ｂをインターフェース２２に出力し、インターフェース２２は、第１のクエリデータ３０Ａを連続的にリファインするために、第２のクエリデータ３０Ｂをネットワーク１６を介して視覚探索サーバ１４に送信する。
【００４３】
[0052]視覚探索サーバ１４のインターフェース３２は第２のクエリデータ３０Ｂを受信し、その後、視覚探索サーバ１４は特徴再構成ユニット３４を起動する。次いで、特徴再構成ユニット３４は、第１のクエリデータ３０Ａを第２のクエリデータ３０Ｂでアップデートすることによってより精細なレベルで特徴記述子２８を再構成し、再構成された特徴記述子４０Ｂを生成し得る（特徴記述子４０Ｂは、再び、「アップデートされたクエリデータ４０Ｂ」と呼ばれ、このデータは、視覚探索、または視覚探索もしくはクエリを実行するために使用される視覚探索またはクエリデータに関連する）。次いで、特徴マッチングユニット３６は、クエリデータ４０Ａではなくアップデートされたクエリデータ４０Ｂを使用して視覚探索を再開し得る。
【００４４】
[0053]図１の例に示さないが、より精細な量子化レベルを使用して特徴記述子２８を連続的にリファインし、次いで視覚探索を再開するこのプロセスは、特徴マッチングユニット３６が、画像データ２６から抽出された１つまたは複数の対象物もしくは特徴を確実に識別するか、この特徴もしくは対象物が識別できないと決定するか、または視覚探索プロセスを終了させ得る電力消費、待ち時間、または他の閾値に到達するまで、継続し得る。たとえば、クライアントデバイス１２は、例として、現在決定された電力量を電力の閾値と比較することによって、さらなる時間特徴記述子２８をリファインするための十分な電力を有すると決定することができる。
【００４５】
[0054]この決定に応答して、クライアントデバイス１２は、クエリデータ４０Ｂがこの第３のクエリデータでアップデートされると、このアップデートされた第２のクエリデータが、第２の量子化レベルより一層精細な第３の量子化レベルで量子化された再構成された特徴記述子をもたらすように、第２のクエリデータ３０Ｂを拡張する第３のクエリデータを、この再開された視覚探索と並行して決定するために、特徴圧縮ユニット２０を起動する。視覚探索サーバ１４は、この第３のクエリデータを受信し、この同じ特徴記述子ではあるが第３の量子化レベルにおいて量子化された特徴記述子に対して視覚探索を再開し得る。
【００４６】
[0055]したがって、特徴記述子の第１のセットに基づき視覚探索を実行した後、引き続いて異なる特徴記述子（それらは一般的には、第１の特徴記述子とは異なるか、または、全く異なる画像から抽出され、それゆえまったく異なる画像を表現する）に基づいて視覚探索を実行する従来のシステムとは異なり、本開示で説明する技法は、第１の量子化レベルにおいて量子化された特徴記述子に対して視覚探索を開始し、次いで、同じ特徴記述子であるが、第２の異なる、通常より精細またはより完全な量子化レベルにおいて量子化された特徴記述子に対して視覚探索を再開する。このプロセスは、上述のように反復ベースで継続され得、それにより、同じ特徴記述子の連続するバージョンが、連続的に小さくなる度合いで、すなわち粗い特徴記述子データから、より精細な特徴記述子データで、量子化される。いくつかの例では、視覚探索の再開（しかし、第１のクエリデータ４０Ａより精細にまたはより完全に量子化されたクエリデータ４０Ｂに対して）を可能にする第２のクエリデータ３０Ｂを決定しながら、同時に、視覚探索を開始するのに十分に詳細なクエリデータ３０Ａを送信することによって、本技法は、視覚探索が量子化と同時に実行されることを考えると、待ち時間を改善する。
【００４７】
[0056]いくつかの例では、本技法は、視覚探索サーバが、この粗く量子化された第１のクエリデータに基づいて特徴を何らかの許容できる程度に識別することができるものと仮定すると、粗く量子化された第１のクエリデータを視覚探索サーバに供給するだけで、その後終了することができる。この例では、クライアントデバイスは、視覚探索サーバが第２のより精細な量子化の程度で特徴記述子を再構成することを可能にするのに十分なデータを定義する第２のクエリデータを提供するために、特徴記述子を引き続き量子化する必要はない。このようにして、本技法は、従来のシステムと共通のより精細に量子化された特徴記述子を決定するよりも少ない時間で決定できる、より粗く量子化された特徴記述子を提供することで、従来の技法に対して待ち時間を改善し得る。結果として、視覚探索サーバは、従来のシステムに対してより速やかに特徴を識別し得る。
【００４８】
[0057]その上、クエリデータ３０Ｂは、その後、視覚探索を実行するための基礎として使用されるクエリデータ３０Ａからのデータを繰り返さない。言い換えれば、クエリデータ３０Ｂはクエリデータ３０Ａを拡張し、かつクエリデータ３０Ａのいかなる部分も置き換えることはない。この点において、本技法は、（本技法で使用される第２の量子化レベルが従来使用されるものとほぼ等しいものと仮定すると）従来、量子化された特徴記述子２８を送るよりもはるかに多くの帯域幅を、ネットワーク１６内で消費するものではない。帯域幅消費の増加は、クエリデータ３０Ａと３０Ｂの両方が、ネットワーク１２を横断するためのパケットヘッダと、従来、所与の特徴記述子は量子化され、一度送られるだけであるので必要ではなかった他のごく少量のメタデータとを必要とするために、発生するのみである。しかも、この帯域幅の増加は、本開示で説明する技法のアプリケーションを通して可能となる待ち時間の減少と比較すると、一般的にはささいなものである。
【００４９】
[0058]図２は、図１の特徴圧縮ユニット２０をより詳細に示すブロック図である。図２の例に示すように、特徴圧縮ユニット２０は、リファイン可能な格子量子化ユニット５０とインデックスマッピングユニット５２とを含む。リファイン可能な格子量子化ユニット５０は、特徴記述子の連続的なリファインを提供するために本開示で説明する技法を実装するユニットを表す。本開示で説明する技法を実装することに加えて、リファイン可能な格子量子化ユニット５０はまた、上記で説明したタイプを決定する形態の格子量子化を実行する。
【００５０】
[0059]格子量子化を実行するとき、リファイン可能な格子量子化ユニット５０は、最初に基底の量子化レベル５４（数学的にｎと呼ばれてよい）と特徴記述子２８とに基づいて、格子点ｋ'1、．．．、ｋ'mを計算する。次いで、リファイン可能な格子量子化ユニット５０は、これらの点を合計して、ｎ'を求め、ｎ'をｎと比較する。ｎ'がｎに等しい場合、リファイン可能な格子量子化ユニット５０は、ｋi（ここでｉ＝１、．．．、ｍ）をｋ'iにセットする。ｎ'がｎに等しくない場合、リファイン可能な格子量子化ユニット５０は、ｋ'iと、ｎと、特徴記述子２８との関数として誤差を計算し、次いでこれらの誤差をソートする。その後、リファイン可能な格子量子化ユニット５０は、ｎ'マイナスｎがゼロより大きいかどうかを判定する。ｎ'マイナスｎがゼロより大きい場合、リファイン可能な格子量子化ユニット５０は、最大の誤差を有するＫ'i値を１だけ減分する。ｎ'マイナスｎがゼロより大きい場合、リファイン可能な格子量子化ユニット５０は、最小の誤差を有するＫ'i値を１だけ増分する。この方式で増分または減分される場合、リファイン可能な格子量子化ユニット５０は、ｋiを調整されたｋ'i値にセットする。次いで、リファイン可能な格子量子化ユニット５０は、これらのｋi値をタイプ５６としてインデックスマッピングユニット５２に出力する。
【００５１】
[0060]インデックスマッピングユニット５２は、タイプ５６をインデックスに一意にマッピングするユニットを表す。タイプ５６が決定された次元と同じ次元の特徴記述子（やはり、ヒストグラムの形態の確率分布として表現される）に対して計算されたすべての可能なタイプの辞書式配列においてタイプ５６を識別するインデックスとして、インデックスマッピングユニット５２は、このインデックスを数学的に計算し得る。インデックスマッピングユニット５２は、タイプ５６に対してこのインデックスを計算し、クエリデータ３０Ａとしてこのインデックスを出力し得る。
【００５２】
[0061]動作時、リファイン可能な格子量子化ユニット５０は、特徴記述子２８を受信し、ｋ1、．．．、ｋmのパラメータを有するタイプ５６を計算する。次いで、リファイン可能な格子量子化ユニット５０は、タイプ５６をインデックスマッピングユニット５２に出力する。インデックスマッピングユニット５２は、次元数ｍを有する特徴記述子に対して可能なすべてのタイプのセットの中でタイプ５６を一意に識別するインデックスに、タイプ５６をマッピングする。次いで、インデックスマッピングユニット５２は、このインデックスをクエリデータ３０Ａとして出力する。このインデックスは、図９Ａおよび図９Ｂに関連してより詳細に図示され、説明されるように、確率分布上に一様に定義されたボロノイセル（Voronoi cells）の中心に位置する再構成点の格子を表すものと見なされ得る。上記のように、視覚探索サーバ１４は、クエリデータ３０Ａを受信し、再構成された特徴記述子４０Ａを求め、再構成された特徴記述子４０Ａに基づいて視覚探索を実行する。ボロノイセルに対して説明したが、本技法は、類似の種類のインデックスマッピングを可能にするために空間のセグメント化を容易にすることができる、任意の他の種類の一様なまたは一様でないセルに対して実装されうる。
【００５３】
[0062]一般的に、クエリデータ３０Ａがクライアントとサーバ１４との間で伝送途中にある間、および／または、視覚探索サーバ１４が再構成された特徴記述子４０Ａを決定し、および／または再構成された特徴記述子４０Ａに基づいて視覚探索を実行している間、リファイン可能な格子量子化ユニット５０は、クエリデータ３０Ａがクエリデータ３０Ｂで拡張されると、拡張またはアップデートされたクエリデータ３０Ａが、基底または第１の量子化レベルよりも精細な量子化レベルで量子化された特徴記述子２８を表すような方式で、クエリデータ３０Ｂを決定するために、本開示で説明する技法を実装する。リファイン可能な格子量子化ユニット５０は、タイプパラメータ再構成点ｋ1、．．．、ｋmの関数
【数１】
0005639277.tif 000002
【００５４】
である再構成点ｑ1、．．．、ｑmからオフセットを識別する１つまたは複数のオフセットベクトルとしてクエリデータ３０Ｂを求める。
【００５５】
[0063]リファイン可能な格子量子化ユニット５０は、２つの方法のうちの一方でクエリデータ３０Ｂを決定する。第１の方法では、リファイン可能な格子量子化ユニット５０は、クエリデータ３０Ａで特徴記述子２８を表すために使用される再構成点の数を２倍にすることによってクエリデータ３０Ｂを決定する。この点において、第２の量子化レベルは、第１のまたは基底の量子化レベル５４の２倍のレベルであるものと見なされ得る。図９Ａの例に示す例示的な格子に関して、これらのオフセットベクトルは、追加の再構成点を、ボロノイセルの各々の面の中心として識別し得る。以下でより詳細に説明するように、再構成点の数を２倍にし、それによってより粒度の高い特徴記述子２８を定義するが、連続的に量子化される特徴記述子２８のこの第１の方法は、２番目に高い量子化レベルにおける再構成点の格子を単に送ることと比較して、これらのベクトルを送るために必要なビットの数に関してあまりに多くのオーバーヘッド（およびそれによる帯域幅消費）をもたらすことを回避するために、基底の量子化レベル５４は、それが、この例のヒストグラムとして表される確率分布の次元数より十分に大きい（すなわち、ｎがｍより大きく定義される）ように定義されることが必要である。
【００５６】
[0064]たいていのまたは少なくともいくつかの例では、基底の量子化レベル５４は確率分布（またはこの例ではヒストグラム）の次元数より大きく定義され得るが、いくつかの例では、基底の量子化レベル５４は、確率分布の次元性より十分に大きく定義され得ない。これらの例では、リファイン可能な格子量子化ユニット５０は、代替として、二重格子（dual lattice）を使用して第２の方法によってオフセットベクトルを計算することができる。すなわち、クエリデータ３０Ａで定義された再構成点の数を２倍にするのではなく、リファイン可能な格子量子化ユニット５０は、インデックスマッピングユニット５２でマッピングされたインデックスによって、クエリデータ３０Ａとして表される再構成点の格子の中の穴を埋めるようにオフセットベクトルを求める。ここでも、この拡張を、図９Ｂの例に関してより詳細に図示し説明する。これらのオフセットベクトルがボロノイセルの交差部または交点に入る再構成点の追加の格子を定義することを考慮すると、クエリデータ３０Ｂとして表されるこれらのオフセットベクトルは、クエリデータ３０Ａで表される再構成点の格子に加えて、再構成点のさらに別の格子を定義するものと見なされ、したがってこのことは、この第２の方法が二重格子を使用するという特性に導く。
【００５７】
[0065]特徴記述子２８の量子化レベルを連続的にリファインするこの第２の方法は、基底の量子化レベル５４が、基礎をなす（underlying）確率分布の次元数より実質的に大きく定義される必要がない一方で、この第２の方法は、オフセットベクトルを計算するために必要な動作の数に関してより複雑になる可能性がある。いくつかの例では、追加の動作を実行することで、電力消費が増加する可能性があることを考慮すると、特徴記述子２８の量子化を連続的にリファインするこの第２の方法は、十分な電力が利用できるときにだけ使用され得る。電力の充足度（power sufficiency）が、ユーザ定義、アプリケーション定義、または静的に定義された電力閾値に対して決定されてよく、それにより、リファイン可能な格子量子化ユニット５０は、現在の電力がこの閾値を超えるときだけ、この第２の方法を使用する。他の例では、リファイン可能な格子量子化ユニット５０は、基底レベルの量子化は、確率分布の次元数と比較して十分に大きく定義され得ないこれらの例において、オーバーヘッドがもたらされるのを回避するために、この第２の方法を常に使用し得る。代替的に、リファイン可能な格子量子化ユニット５０は、実装形態の複雑性と、その結果としての第２の方法に関連する電力消費とを回避するために、常に第１の方法を使用し得る。
【００５８】
[0066]図３は、図１の特徴再構成ユニット３４をより詳細に示すブロック図である。図３の例に示すように、特徴再構成ユニット３４は、タイプマッピングユニット６０と、特徴復元ユニット６２と、特徴拡張ユニット６４とを含む。タイプマッピングユニット６０は、クエリデータ３０Ａのインデックスをタイプ５６に戻すマッピングをするために、インデックスマッピングユニット５２の逆を実行するユニットを表す。特徴復元ユニット６２は、再構成された特徴記述子４０Ａを出力するために、タイプ５６に基づいて特徴記述子２８を復元するユニットを表す。特徴復元ユニット６２は、特徴記述子２８をタイプ５６に縮小する（reduce）するときにリファイン可能な格子量子化ユニット５０に対して上記で説明した動作と逆の動作を実行する。特徴拡張ユニット６４は、クエリデータ３０Ｂのオフセットベクトルを受信し、オフセットベクトルに基づいてタイプ５６で定義された再構成点の格子に対する再構成の追加によりタイプ５６を拡張する。特徴拡張ユニット６４は、追加の再構成点を決定するために、クエリデータ３０Ｂのオフセットベクトルを、タイプ５６で定義された再構成点の格子に適用する。次いで、特徴拡張ユニット６４は、タイプ５６をこれらの決定された追加の再構成点でアップデートし、アップデートされたタイプ５８を特徴復元ユニット６２に出力する。次いで、特徴復元ユニット６２は、再構成された特徴記述子４０Ｂを出力するために、アップデートされたタイプ５８から特徴記述子２８を復元する。
【００５９】
[0067]図４は、本開示で説明する連続的にリファイン可能な量子化技法の実装において、図１の例に示すクライアントデバイス１２などの視覚探索クライアントデバイスの例示的な動作を示すフローチャートである。特定のデバイス、すなわちクライアントデバイス１２に関して説明したが、本技法は、視覚探索を実行するためなど、この確率分布のさらなる使用において待ち時間を低減するために、確率分布に対する数学演算を実行することができる任意のデバイスによって実装され得る。加えて、視覚探索のコンテキストにおいて説明するが、本技法は、確率分布の連続的なリファインを可能にする他のコンテキストにおいて実装されてもよい。
【００６０】
[0068]最初に、クライアントデバイス１２は、画像データ２６を記憶し得る。クライアントデバイス１２は、画像データ２６をキャプチャするために画像またはビデオカメラなど、キャプチャデバイスを含み得る。代替として、クライアントデバイス１２は、画像データ２６を、ダウンロードまたは場合によっては受信し得る。クライアントデバイス１２のユーザまたは他のオペータは、画像データ２６に対する視覚探索を開始するために、クライアントデバイス１２（図示を容易にするために図１の例に示さず）によって提供されるユーザインターフェースと対話し得る。このユーザインターフェースは、グラフィカルユーザインターフェース（ＧＵＩ）、コマンドラインインターフェース（ＣＬＩ）、またはデバイスのユーザもしくはオペレータとインターフェースするために使用される任意の他の種類のユーザインターフェースを備えることができる。
【００６１】
[0069]視覚探索の開始に応答して、クライアントデバイス１２は特徴抽出ユニット１８を起動する。起動すると、特徴抽出ユニット１８は、本開示で説明する方式で画像データ２６から特徴記述子２８を抽出する（７０）。特徴抽出ユニット１８は、特徴記述子２８を特徴圧縮ユニット２０に転送する。図２Ａの例により詳細に示す特徴圧縮ユニット２０は、リファイン可能な格子量子化ユニット５０を起動する。リファイン可能な格子量子化ユニット５０は、基底の量子化レベル５４における特徴記述子２８の量子化を介して特徴記述子２８をタイプ５６に縮小する。上記のように、この特徴記述子２８は、より一般的な確率分布の具体例である勾配のヒストグラムを表す。特徴記述子２８は、変数ｐとして数学的に表され得る。
【００６２】
[0070]特徴圧縮ユニット２０は、抽出された特徴記述子２８に対するタイプを求めるために、タイプ格子（type lattice）量子化の形態を実行する（７２）。このタイプは、変数Qで数学的に表される再生可能（reproducible）分布のセットの中の再構成点または中心のセットを表し得、ここでQは、別個の事象（Ａ）のセットに対する確率分布（Ωm）のセットのサブセットと見なされ得る。ここでも、変数ｍは、確率分布の次元数を指す。Ｑは、再構成点の格子と見なされてよい。変数Ｑは、Ｑnに到達するために変数ｎで修正され、Ｑnは、格子内の点の密度（ある程度まで量子化のレベルと見なされ得る）を定義するパラメータｎを有する格子を表す。Ｑnは、次式（１）で数学的に表され得る。
【数２】
0005639277.tif 000003
【００６３】
式（１）において、Ｑnの要素はｑ1、．．．、ｑmとして示される。変数Ｚ+は、すべての正の整数を表す。
【００６４】
[0071]所与のｍとｎとを有する格子に対して、格子Ｑnは、次式（２）で数学的に表される点の数を含み得る。
【数３】
0005639277.tif 000004
【００６５】
また、Ｌノルムベースの最大距離に関して表される、このタイプの格子のカバレージ半径は、次式（３）〜（５）で表される半径である。
【数４】
0005639277.tif 000005
【００６６】
上式（３）〜（５）では、変数ａは、次式（６）で数学的に表され得る。
【数５】
0005639277.tif 000006
【００６７】
加えて、タイプインデックスのダイレクト（非スケーラブルまたはリファイン不可能な）伝送（transmission）は、次式（７）〜（９）で数学的に表されるように、量子化器の以下の半径／レート（radius/rate）特性をもたらす。
【数６】
0005639277.tif 000007
【００６８】
[0072]所与の基底の量子化レベル５４（上述の変数ｎを表し得る）において再構成点またはいわゆる「タイプ」のこのセットを生成するために、リファイン可能な格子量子化ユニット５０は、最初に、下式（１０）によって値ｋ'iを計算する。
【数７】
0005639277.tif 000008
【００６９】
式（１０）の変数ｉは、値１、．．．、ｍのセットを表す。ｎ'がｎに等しい場合、最近のタイプは、ｋi＝ｋ'iで与えられる。そうではなく、ｎ'がｎに等しくない場合、リファイン可能な格子量子化ユニット５０は、次式（１１）によって誤差δiを計算し、
【数８】
0005639277.tif 000009
【００７０】
次式（１２）が満たされるようにこれらの誤差を分類する。
【数９】
0005639277.tif 000010
【００７１】
次いで、リファイン可能な格子量子化ユニット５０は、ｎ'とｎとの間の差分を求め、そのような差分は変数Δで示され得、下式（１３）で表される。
【数１０】
0005639277.tif 000011
【００７２】
[0073]Δがゼロより大きい場合、リファイン可能な格子量子化ユニット５０は、それらの最大の誤差を有するｋ'iの値を減分し、それらの値は、次式（１４）で数学的に表され得る。
【数１１】
0005639277.tif 000012
【００７３】
しかしながら、Δがゼロより小さいと判断される場合、リファイン可能な格子量子化ユニット５０は、最小の誤差を有するｋ'iの値を増分し、それらの値は、次式（１５）で数学的に表され得る。
【数１２】
0005639277.tif 000013
【００７４】
基底の量子化レベルすなわちｎが既知であると仮定すれば、タイプをｑ1、．．．、ｑmに関して表すのではなく、リファイン可能な格子量子化ユニット５０は、上述の３つの方法のうちの１つによって計算されるｋ1、．．．、ｋmの関数としてタイプ５６を表す。リファイン可能な格子量子化ユニット５０は、このタイプ５６をインデックスマッピングユニット５２に出力する。
【００７５】
[0074]インデックスマッピングユニット５２は、このタイプ５６を、クエリデータ３０Ａに含まれるインデックスにマッピングする（７４）。このタイプ５６をインデックスにマッピングするために、インデックスマッピングユニット５２は、次元数ｍを有する確率分布に対するすべてのタイプのセットの中でのタイプ５６の辞書式配列を示すタイプ５６に割り当てられたインデックスζ（ｋ1、．．．、ｋm）を計算する次式（１６）を実装し得る。
【数１３】
0005639277.tif 000014
【００７６】
インデックスマッピングユニット５６は、予め計算された二項係数の配列を使用してこの式を実装し得る。次いで、インデックスマッピングユニット５２は、決定されたインデックスを含むクエリデータ３０Ａを生成する（７６）。次いで、クライアントデバイス１２は、このクエリデータ３０Ａをネットワーク１６を介して視覚探索サーバ１４に送信する（７８）。
【００７７】
[0075]インデックスマッピングユニット５２がインデックスを決定すること、および／またはクライアントデバイス１２がクエリデータ３０Ａを送信すること、および／または視覚探索サーバ１４がクエリデータ３０Ａに基づいて視覚探索を実行することと同時に、リファイン可能な格子量子化ユニット５０は、タイプ５６がオフセットベクトル３０Ｂでアップデートされると、このアップデートまたは拡張されたタイプ５６が、クエリデータ３０Ａ内に含まれていたときのタイプ５６の量子化に使用された量子化レベルよりも精細な量子化レベルでの特徴記述子２８を表し得るように、前に決定されたタイプ５６を拡張するオフセットベクトル３０Ｂを決定する（８０）。上述のように、リファイン可能な格子量子化ユニット５０は、最初にタイプ５６の形態で格子Ｑnを受信する。リファイン可能な格子量子化ユニット５０は、オフセットベクトル３０Ｂを計算する２つの方法の一方または両方を実装し得る。
【００７８】
[0076]第１の方法では、リファイン可能な格子量子化ユニット５０は、基底の量子化レベル５４すなわちｎを２倍にして、数学的に２ｎで表され得る第２のより精細な量子化レベルを得る。この第２のより精細な量子化レベルを使用して生成された格子は、Ｑ2nで示され、ここで格子Ｑ2nの点は、次式（１７）で定義されるように格子Ｑnの点に関連する。
【数１４】
0005639277.tif 000015
【００７９】
ここでδ1＋．．．＋δm＝０であるように、δ1、．．．、δm∈｛−１、０、１｝。オフセットベクトル３０Ｂを計算するこの方法の評価は、元の格子Ｑnの中の点の周りに挿入され得る点の数を検討することによって始まる。点の数は、次式（１８）によって計算され得、ここでｋ-1、ｋ0、ｋ1は、変位ベクトル［δ1、．．．、δm］の要素の中で値−１、０、１が発生する回数を示す。δ1＋．．．＋δm＝０がｋ-1＝ｋ1を意味するという条件を与えると、点の数は、下式（１８）で計算され得る。
【数１５】
0005639277.tif 000016
【００８０】
式（１８）から、漸近的に（大きなｍに対して）この点の数はη（ｍ）〜αｍ！になると判断できる。ここで
【数１６】
0005639277.tif 000017
【００８１】
である。
【００８２】
[0077]格子Ｑnに関して格子Ｑ2n内のタイプの位置を指定するために必要なベクトル［δ1、．．．、δm］を符号化するために、せいぜい必要なビットの数は、次式（１９）を使用して導出され得る。
【数１７】
0005639277.tif 000018
【００８３】
オフセットベクトルを送るために必要なビット数のこの測定値（measure）を、Ｑ2n内の点の直接符号化を送るために必要なビット数と比較すると、次式（２０）となる。
【数１８】
0005639277.tif 000019
【００８４】
式(２０)を概括的に考察すると、タイプインデックスの漸増的送信に対して小さなオーバーヘッドを確保するために、この第１の方法は、ｎがｍよりはるかに大きい（≫）格子Ｑnからインデックスを直接送信することで開始すべきであることに気づく。第１の方法を実装することにおけるこの条件は、常に実用的であるとは限らない。
【００８５】
[0078]代替として、リファイン可能な格子量子化ユニット５０は、この条件に縛られない第２の方法を実装し得る。この第２の方法は、ボロノイセルの穴または交点に設置される点によってＱnを拡張することを伴い、ここで得られた格子は
【数１９】
0005639277.tif 000020
【００８６】
で示され、これは次式（２１）によって定義される。
【数２０】
0005639277.tif 000021
【００８７】
この格子
【数２１】
0005639277.tif 000022
【００８８】
は、本開示では「二重タイプ格子（dual type lattice）」と呼ばれ得る。変数νiは、ボロノイセルの交点に対するオフセットを示すベクトルを表し、変数νiは次式（２２）によって数学的に表され得る。
【数２２】
0005639277.tif 000023
【００８９】
各ベクトルνiは、その値の
【数２３】
0005639277.tif 000024
【００９０】
を可能にする。この転置の数が与えられれば、Ｑnを二重タイプ格子
【数２４】
0005639277.tif 000025
【００９１】
に変換することによってＱn内の点の周りに挿入される点の総数は、次式（２３）で示す式を満たす。
【数２５】
0005639277.tif 000026
【００９２】
式（２３）が与えられれば、格子Ｑn内の点の既知の位置に対する、二重タイプ格子
【数２６】
0005639277.tif 000027
【００９３】
内の点の符号化は、せいぜい次式（２４）で表されるビットの数を送信することによって達成され得る。
【数２７】
0005639277.tif 000028
【００９４】
[0079]オフセットベクトル３０Ｂを決定するこの第２の方法を評価することにおいて、格子Ｑnから
【数２８】
0005639277.tif 000029
【００９５】
に切り替えるときに、カバー半径（covering radius）における縮小の推定値が必要になる。タイプ格子Ｑnに対して、次式（２５）は半径カバレージ（radius coverage）
【数２９】
0005639277.tif 000030
【００９６】
を表す。
【数３０】
0005639277.tif 000031
【００９７】
一方、二重タイプ格子
【数３１】
0005639277.tif 000032
【００９８】
に対して、次式（２６）が半径カバレージを表す。
【数３２】
0005639277.tif 000033
【００９９】
これら２つの異なる半径カバレージの値を比較すると、格子Ｑnから
【数３３】
0005639277.tif 000034
【０１００】
への遷移でカバー半径がファクタ
【数３４】
0005639277.tif 000035
【０１０１】
だけ縮小し、一方、約ｍビットレートのオーバーヘッドを生じると決定され得る。リファイン不可能なＱn格子ベースの符号化と比較したこの第２の符号化の方法の効率は、次式（２７）によって推定できる。
【数３５】
0005639277.tif 000036
【０１０２】
式（２７）から、符号化のこの第２の方法は、開始の格子（すなわち、この例におけるパラメータｎで定義される）の基底の量子化レベルに対して減少していることがみてとれるが、このパラメータｎは、次元数ｍに対して比較的大きくなくてもよい。リファイン可能な格子量子化ユニット５０は、前に決定されたタイプ５６に対してオフセットベクトル３０Ｂを決定するこれら２つの方法の一方または両方を利用することができる。
【０１０３】
[0080]次いで、リファイン可能な格子量子化ユニット５０は、これらのオフセットベクトルを含む追加のクエリデータ３０Ｂを生成する（８２）。クライアントデバイス１２は、上記で説明した方式でクエリデータ３０Ｂを視覚探索サーバ１２に送信する（８４）。次いで、クライアントデバイス１２は、識別データ４２を受信したかどうかを決定し得る（８６）。クライアントデバイス１２は、識別データ４２を未だに受信していないと決定する場合（８６の「ＮＯ」）、クライアントデバイス１２は、いくつかの例では、上記で説明した２つの方法のうちのいずれかを使用してすでに拡張されているタイプ５６を拡張する追加のオフセットベクトルを決定することによって、拡張されたタイプ５６をさらにリファインし、これらの追加のオフセットベクトルを含む第３のクエリデータを生成し、この第３のクエリデータを視覚探索サーバ１４に送信することを継続し得る（８０〜８４）。このプロセスは、いくつかの例では、クライアントデバイス１２が識別データ４２を受信するまで継続し得る。いくつかの例では、クライアントデバイス１２は、第１のリファインの後、タイプ５６をリファインすることを、クライアントデバイス１２が、上述のように、この追加のリファインを実行するために十分な電力を有しているときだけ継続する。いずれにしても、クライアントデバイス１２が識別データ４２を受信する場合、クライアントデバイス１２は、この識別データ４２をディスプレイ２４を介してユーザに提示する（８８）。
【０１０４】
[0081]図５は、本開示で説明する連続的にリファイン可能な量子化技法を実装することにおいて、図１の例に示す視覚探索サーバ１４ようのよう視覚探索サーバの例示的な動作を示すフローチャートである。特定のデバイス、すなわち視覚探索サーバ１４に関して説明したが、本技法は、視覚探索を実行するためなど、この確率分布のさらなる使用において待ち時間を低減するために、確率分布に対する数学演算を実行することができる任意のデバイスによって実装され得る。加えて、視覚探索のコンテキストを説明するが、本技法は、確率分布の連続的なリファインを可能にする他のコンテキストで実装されてもよい。
【０１０５】
[0082]最初に、視覚探索サーバ１４は、上記で説明したように、インデックスを含むクエリデータ３０Ａを受信する（１００）。クエリデータ３０Ａの受信に応答して、視覚探索サーバ１４は、特徴再構成ユニット３４を起動する。図３を参照すると、特徴再構成ユニット３４は、上記で説明した方式で、クエリデータ３０Ａのインデックスをタイプ５６にマッピングするために、タイプマッピングユニット６０を起動する（１０２）。タイプマッピングユニット６０は、決定されたタイプ５６を特徴復元ユニット６２に出力する。次いで、特徴復元ユニット６２は、上記で説明したように、タイプ５６に基づいて特徴記述子２８を再構成し、再構成された特徴記述子４０Ａを出力する（１０４）。次いで、視覚探索サーバ１４は、特徴マッチングユニット３６を起動し、特徴マッチングユニット３６は、上記で説明した方式で、再構成された特徴記述子４０Ａを使用して視覚探索を実行する（１０６）。
【０１０６】
[0083]特徴マッチングユニット３６で実行される視覚探索が特徴の確実な識別をもたらさない場合（１０８の「ＮＯ」）、特徴マッチングユニット６２は、識別データを生成せず、次いでそのデータをクライアントデバイス１２に送ることはない。この識別データを受信しなかった結果として、クライアントデバイス１２は、クエリデータ３０Ｂの形態のオフセットベクトルを生成して送る。視覚探索サーバ１４は、これらのオフセットベクトルを含むこの追加のクエリデータ３０Ｂを受信する（１１０）。視覚探索サーバ１４は、受信したクエリデータ３０Ｂを処理するために特徴再構成ユニット３４を起動する。特徴再構成ユニット３４は、起動されると次に、特徴拡張ユニット６４を起動する。特徴拡張ユニット６４は、特徴記述子２８を粒度のより精細なレベルで再構成するために、そのオフセットベクトルに基づいてタイプ５４を拡張する（１１２）。
【０１０７】
[0084]特徴拡張ユニット６４は、拡張またはアップデートされたタイプ５８を特徴復元ユニット６２に出力する。次いで、特徴復元ユニット６２は、アップデートされたタイプ５８に基づいて特徴記述子２８を復元して再構成された特徴記述子４０Ｂを出力し、ここで再構成された特徴記述子４０Ｂは、特徴記述子４０Ａで表されるレベルより精細なレベルにおいて量子化された特徴記述子２８を表す（１１３）。次いで、特徴復元ユニット６２は、再構成された特徴記述子４０Ｂを特徴マッチングユニット３６に出力する。次いで、特徴マッチングユニット３６は、特徴記述子４０Ｂを使用して視覚探索を再開する（１０６）。このプロセスは、特徴が識別されるまで（１０６〜１１３）またはクライアントデバイス１２がもはや追加のオフセットベクトルを供給しなくなるまで継続し得る。識別されれば（１０８の「ＹＥＳ」）、特徴マッチングユニット３６は、識別データ４２を生成し、それを視覚探索クライアント、すなわちこの例ではクライアントデバイス１２に送信する（１１４）。
【０１０８】
[0085]図６は、特徴記述子抽出における使用のために求められたガウシアン差分（DｏＧ）ピラミッド２０４を示す図である。図１の特徴抽出ユニット１８は、ガウシアンピラミッド２０２内の任意の２つの連続するガウスぼけ画像の差分を計算することによってＤｏＧピラミッド２０４を構築し得る。図１の例では画像データ２６として示される入力画像Ｉ（ｘ、ｙ）が、ガウシアンピラミッド２０２を構築するために、徐々にガウスぼかしされる（Gaussian blurred）。ガウスぼかしは、一般に、ガウスぼけ関数（Gaussian blurred function）Ｌ（ｘ、ｙ、ｃσ）が
【数３６】
0005639277.tif 000037
【０１０９】
と定義されるように、元の画像Ｉ（ｘ、ｙ）をスケールｃσでガウスぼけ関数（Gaussian blur function）Ｇ（ｘ、ｙ、ｃσ）で畳み込むことを伴う。ここで、Ｇはガウスカーネルであり、ｃσは画像Ｉ（ｘ、ｙ）をぼかすために使用されるガウス関数の標準偏差を示す。ｃは変えられる（ｃ0＜ｃ1＜ｃ2＜ｃ3＜ｃ4）ので、標準偏差ｃσは変化し、漸進的なぼかしが得られる。シグマσは、ベーススケール変数（本質的にはガウスカーネルの幅）である。ぼけ画像Ｌを生成するために初期画像Ｉ（ｘ、ｙ）がガウシアンＧで増分的に畳み込まれるとき、ぼけ画像Ｌは、スケール空間において一定ファクタｃだけ分離される。
【０１１０】
[0086]ＤｏＧ空間またはＤｏＧピラミッド２０４において、Ｄ（ｘ、ｙ、ａ）＝Ｌ（ｘ、ｙ、ｃnσ）−Ｌ（ｘ、ｙ、ｃn-1σ）。ＤｏＧ画像Ｄ（ｘ、ｙ、σ）は、スケールがｃnσおよびｃn-1σにおける２つの隣接するガウスぼけ画像Ｌの間の差分である。Ｄ（ｘ、ｙ、σ）のスケールは、ｃnσとｃn-1σとの間のどこかに存在する。ガウスぼけ画像Ｌの数が増加し、ガウシアンピラミッド２０２のために与えられる近似が連続的空間に近づくにつれて、２つのスケールもまた１つのスケールに近づく。畳み込まれた画像Ｌはオクターブによってグループ化され得、ここでオクターブは、標準偏差σの値の２倍に対応する。さらに、乗数ｋ（たとえば、ｃ0＜ｃ1＜ｃ2＜ｃ3＜ｃ4）の値は、固定数の畳み込まれた画像Ｌが、オクターブごとに取得されるように選択される。次いで、ＤｏＧ画像Ｄが、オクターブごとに隣接するガウスぼけ画像Ｌから取得され得る。各オクターブの後、ガウス画像が２分の１にダウンサンプリングされ、次いでプロセスが繰り返される。
【０１１１】
[0087]次いで、特徴抽出ユニット１８は、画像Ｉ（ｘ、ｙ）に対するキーポイントを識別するためにＤｏＧピラミッド２０４を使用し得る。キーポイント検出を実行することにおいて、特徴抽出ユニット１９は、画像内の特定のサンプル点または画素の周りの局所領域またはパッチが、（幾何学的に言って）潜在的に関心のあるパッチであるかどうかを決定する。一般に、特徴抽出ユニット１８は、ＤｏＧ空間２０４内に局所的最大値および／または局所的最小値を識別し、これらの極大値および極小値の位置をＤｏＧ空間２０４内のキーポイントの位置として使用する。図６に示す例では、特徴抽出ユニット１８は、パッチ２０６内にキーポイント２０８を識別する。局所的最大値および最小値を発見すること（局所的極値検出としても知られる）が、ＤｏＧ空間２０４内の各画素（たとえば、キーポイント２０８に対する画素）を、同じスケールでそれに隣接する８つの画素と、および、両側に隣接するスケールの各々で（隣接するパッチ２１０および２１２内の）隣接する９つの画素と、の合計２６画素（９×２＋８＝２６）に対して比較することによって達成され得る。キーポイント２０６に対する画素値が、パッチ２０６、２１０および２０８内の２６個の比較された画素のすべての中の極大値または極小値であれば、特徴抽出ユニット１８は、この画素をキーポイントとして選択する。特徴抽出ユニット１８は、キーポイントを、それらの位置がより正確に識別されるように、さらに処理し得る。いくつかの例では、特徴抽出ユニット１８は、低コントラストのキーポイントおよびエッジキーポイントなど、キーポイントのうちのいくつかを破棄することがある。
【０１１２】
[0088]図７は、キーポイントの検出をより詳細に示す図である。図７の例では、パッチ２０６、２１０および２１２の各々は３×３の画素領域を含む。特徴抽出ユニット１８は、最初に、関心のある画素（たとえば、キーポイント２０８）を、同じスケール（たとえば、パッチ２０６）においてそれに隣接する８つの画素３０２と比較し、および、キーポイント２０８の両側の隣接するスケールの各々内の隣接するパッチ２１０および２１２内の隣接する９つの画素３０４および３０６と比較する。
【０１１３】
[0089]特徴抽出ユニット１８は、局所画像勾配の方向(directions)に基づいて、各キーポイントに１つまたは複数の方向（orientations）、または方向(directions)を割り当て得る。局所画像属性に基づいて各キーポイントに一定の方向を割り当てることによって、特徴抽出ユニット１８は、この方向に対するキーポイント記述子を表し得、したがって画像回転に対する不変性を達成する。次いで、特徴抽出ユニット１８は、ガウスぼけ画像Ｌ内でおよび／またはキーポイントスケール内のキーポイント２０８の周りの隣接する領域内の各画素に対して大きさと方向とを計算する。（ｘ、ｙ）に位置するキーポイント２０８に対する勾配の大きさは、ｍ（ｘ、ｙ）として表され、（ｘ、ｙ）におけるキーポイントに対する勾配の方向(orientation)または方向(direction)は、Γ（ｘ、ｙ）として表され得る。
【０１１４】
[0090]次いで、特徴抽出ユニット１８は、すべての計算がスケール不変方式で実行されるように、キーポイント２０８のスケールに最も近いスケールで、ガウス平滑画像Ｌを選択するために、キーポイントのスケールを使用する。各画像サンプルＬ（ｘ、ｙ）に対して、このスケールで、特徴抽出ユニット１８は、勾配の大きさｍ（ｘ、ｙ）と方向Γ（ｘ、ｙ）とを、画素差分を使用して計算する。たとえば、大きさｍ（ｘ、ｙ）は、次式（２８）によって計算され得る。
【数３７】
0005639277.tif 000038
【０１１５】
[0091]特徴抽出ユニット１８は、方向(direction)または方向(orientation)Γ（ｘ、ｙ）を、次式（２９）によって計算し得る。
【数３８】
0005639277.tif 000039
【０１１６】
式(２９)において、Ｌ（ｘ、ｙ）は、キーポイントのスケールでもあるスケールにおける、ガウスぼけ画像Ｌ（ｘ、ｙ、  ）のサンプルを表す。
【０１１７】
[0092]特徴抽出ユニット１８は、ＤｏＧ空間内のキーポイントの平面より上に、より高いスケールで存在するガウシアンピラミッド内の平面、またはキーポイントより下に、より低いスケールで存在するガウシアンピラミッドの平面内のいずれかに対して、キーポイントに対する勾配を常に計算し得る。どちらにしても、各キーポイントに対して、特徴抽出ユニット１８は、同じスケールにおいて、キーポイントを取り囲む矩形領域（たとえば、パッチ）内で勾配を計算する。さらに、画像信号の周波数が、ガウスぼけ画像のスケールにおいて反映される。しかも、圧縮勾配ヒストグラム（ＣＨｏＧ）アルゴリズムのようなＳＩＦＴおよび他のアルゴリズムは、単に、パッチ（たとえば、矩形領域）内のすべての画素における勾配値を使用する。パッチがキーポイントの周りで定義され、サブブロックがブロック内で定義され、サンプルがサブブロック内で定義され、この構成は、キーポイントのスケールが異なるときでさえ、すべてのキーポイントに対して同じままである。したがって、画像信号の周波数が、同じオクターブ内の次に続くガウス平滑化フィルタのアプリケーションによって変化するが、異なるスケールにおいて識別されたキーポイントは、スケールで表される画像信号の周波数の変化にかかわらず、同じサンプル数でサンプリングされ得る。
【０１１８】
[0093]キーポイントの方向を特徴付けるために、特徴抽出ユニット１８は、たとえば圧縮勾配ヒストグラム（ＣＨｏＧ）を使用することによって勾配方向ヒストグラム（gradient orientation histogram）（図４参照）を生成し得る。隣接する各画素の寄与は、勾配の大きさおよびガウス窓によって重み付けされ得る。ヒストグラムのピークは支配的な方向に対応する。特徴抽出ユニット１８は、キーポイントの方向に対するキーポイントのすべての属性を測定し、このことが、回転に対する不変性をもたらす。
【０１１９】
[0094]一例では、特徴抽出ユニット１８は、各ブロックに対するガウス重み付け勾配（Gaussian-weighted gradient）の分布を計算し、ここで各ブロックは、２サブブロック×２サブブロックで合計４サブブロックである。ガウス重み付け勾配の分布を計算するために特徴抽出ユニット１８は、それぞれがキーポイントの周りの領域の一部をカバーするいくつかのビンで方向ヒストグラムを形成する。たとえば、方向ヒストグラムは３６のビンを有し、各ビンは３６０度の方向領域のうちの１０度をカバーする。代替として、ヒストグラムは８つのビンを有し、それぞれが３６０度の領域のうちの４５度をカバーする。本明細書で説明するヒストグラム符号化技法は、任意の数のビンのヒストグラムにも適用可能であることは明らかである。
【０１２０】
[0095]図８は、特徴抽出ユニット１８のような特徴抽出ユニットが勾配分布と方向ヒストグラムとを求めるプロセスを示す図である。ここで、２次元勾配分布（ｄｘ、ｄｙ）（たとえば、ブロック４０６）が１次元分布（たとえば、ヒストグラム４１４）に変換される。キーポイント２０８は、キーポイント２０８を取り囲むパッチ４０６（セルまたは領域とも呼ばれる）の中心に位置する。各レベルのピラミッドに対して予め計算された勾配が、各サンプル位置４０８において小さい矢として示される。図示のように、サンプル４０８の領域が、ビン４１０とも呼ばれるサブブロック４１０を形成する。特徴抽出ユニット１８は、サブブロックすなわちビン４１０内の各サンプル４０８に重みを割り当てるために、ガウス重み付け関数を使用し得る。ガウス重み付け関数によってサンプル４０８の各々に割り当てられた重みは、ビン４１０の図心（centroid）２０９Ａ、２０９Ｂおよびキーポイント２０８（図心でもある）から滑らかに離れ落ちる。ガウス重み付け関数の目的は、窓の位置の小さな変化によって記述子が突然変化することを回避し、記述子の中心から遠い勾配にあまり重要視しないことである。特徴抽出ユニット１８は、ヒストグラムの各ビン内に８つの方向を有する方向ヒストグラム４１２の配列を決定し、次元特徴記述子を得る。たとえば、方向ヒストグラム４１３は、サブブロック４１０に対する勾配分布に対応する。
【０１２１】
[0096]いくつかの例では、特徴抽出ユニット１８は、勾配分布を得るために、他の種類の量子化ビンコンステレーション（たとえば、異なるボロノイセル構成を有する）を使用する。これらの他の種類のビンコンステレーションは、同様に、ソフトビニング（soft binning）の形態を使用し得、ソフトビニングは、いわゆるデイジー（DAISY）構成が使用されるときに定義されるものなどの重複ビン（overlapping bin）を指す。図８の例では、３つのソフトビンが定義されるが、９つまたはそれ以上が、一般にキーポイント２０８の周りに円形構成で配置された図心(centroid)とともに使用されてもよい。すなわち、ビンの中心または図心２０８、２０９Ａ、２０９Ｂ。
【０１２２】
[0097]本明細書で使用するヒストグラムは、ビンとして知られている様々な独立したカテゴリーに分類される観測、サンプルまたは発生（たとえば、勾配）の数をカウントするマッピングｋｉである。ヒストグラムのグラフは、ヒストグラムを表すための単なる一方法である。したがって、ｋが観測、サンプルまたは発生の総数であり、ｍがビンの総数である場合、ヒストグラムｋｉにおける度数は、式（３０）で表される下記の条件を満足する。ここでΣは加算演算である。
【数３９】
0005639277.tif 000040
【０１２３】
[0098]特徴抽出ユニット１８は、ヒストグラム４１２に追加された各サンプルを、キーポイントのスケールの１．５倍である標準偏差を有するガウス重み付け関数で定義されるその勾配の大きさによって重み付けすることができる。得られた方向ヒストグラム４１４内のピークは、局所勾配の支配的な方向に対応する。次いで、特徴抽出ユニット１８は、ヒストグラム内の最高のピークを検出し、次いで、最高のピークの８０％など、あるパーセンテージ内にある任意の他の局所ピーク（それはまた、その方向を有するキーポイントを生成するために使用され得る）を検出する。したがって、類似の大きさの複数のピークを有する場所に対して、特徴抽出ユニット１８は、同じ場所およびスケールであるが異なる方向において生成される複数のキーポイントを抽出する。
【０１２４】
[0099]次いで、特徴抽出ユニット１８は、ヒストグラムをタイプとして表すタイプ量子化と呼ばれる量子化の形態を使用して、ヒストグラムを量子化する。このようにして、特徴抽出ユニット１８は、各キーポイントに対する記述子を抽出することができ、そのような記述子は、場所（ｘ、ｙ）と、方向（orientation）と、タイプの形態でガウス重み付け勾配の分布の記述子とによって特徴付けられ得る。このようにして、画像は、１つまたは複数のキーポイント記述子（画像記述子とも呼ばれる）によって特徴付けられ得る。
【０１２５】
[0100]図９Ａおよび図９Ｂは、本開示で説明する技法によって決定された特徴記述子５０２Ａ、５０２Ｂの各々と再構成点５０４〜５０８とを示すグラフ５００Ａ、５００Ｂである。図９Ａおよび図９Ｂ内の軸（「ｐ１」、「ｐ２」および「ｐ３」で示す）は、特徴記述子空間のパラメータを指し、その空間は、上述のヒストグラムのセルの確率を定義する。最初に図９Ａの例を参照すると、特徴記述子５０２Ａがボロノイセル５１２Ａ〜５１２Ｆに分割されている。各ボロノイセルの中心において、特徴圧縮ユニット２０が、基底の量子化レベル５４（図２の例に示す）が２に等しいときの再構成点５０４を決定する。次いで、再構成点５０４が追加の再構成点５０６でアップデートされると、その結果得られる特徴記述子５００Ａがより高い量子化レベル（すなわち、この例ではｎ＝４）で再構成されるように、これらの追加の再構成点を求める上述の第１の方法によって再構成点５０４を拡張する追加の再構成点５０６（図９Ａの例では白／黒の点で示す）を、本開示で説明する技法によって特徴圧縮ユニット２０が決定する。この第１の方法では、追加の再構成点５０６は、ボロノイセル５１２の各面の中心に存在するように決定される。
【０１２６】
[0101]次に図９Ｂの例を参照すると、特徴記述子５０２Ｂがボロノイセル５１２Ａ〜５１２Ｆに分割されている。各ボロノイセルの中心に、特徴圧縮ユニット２０は、基底の量子化レベル５４（図２の例に示す）が２に等しいときの再構成点５０４を決定する。次いで、再構成点５０４が追加の再構成点５０８でアップデートされると、その結果得られる特徴記述子５００Ａがより高い量子化レベル（すなわち、この例ではｎ＝４）において再構成されるように、これらの追加の再構成点を決定する上述の第２の方法によって再構成点５０４を拡張する追加の再構成点５０８（図９Ｂの例では白／黒の点で示す）を、本開示で説明する技法によって特徴圧縮ユニット２０が決定する。この第２の方法では、追加の再構成点５０８は、ボロノイセル５１２の各々の交点に存在するように決定される。
【０１２７】
[0102]図１０は、本開示で説明する技法を実装する図１の例に示すシステム１０などのシステムに関する待ち時間を示す時間図６００である。底の線は、ユーザによる探査の開始（ゼロで示す）から特徴記述子の確実な識別（この例では６番目の時間ユニットまでに発生する）までの経過時間を示す。クライアントデバイス１２は、最初に、特徴記述子を抽出し、特徴記述子を基底レベルで量子化し、特徴記述子を送ることに、１ユニットの待ち時間をもたらす。しかしながら、クライアントデバイス１２は、ネットワーク１６がクエリデータ３０Ａを中継し、視覚探索サーバ１４がクエリデータ３０Ａに対して視覚探索を実行している間に、本開示の技法によって特徴記述子をさらにリファインするために次に続くオフセットベクトルを計算するので、この例では、さらなる待ち時間をもたらさない。その後、ネットワーク１６と視覚探索サーバ１４だけが待ち時間に寄与するが、そのような寄与は、ネットワーク１６がオフセットベクトルを配信している間にサーバ１４はクエリデータ３０Ａに対する視覚探索を実行していることで、オーバーラップする。その後、各アップデートはネットワーク１６とサーバ１４との同時実行をもたらし、それにより、特にクライアントデバイス１２とサーバ１４との同時実行を考慮すれば、待ち時間は、従来のシステムと比較すると大幅に低減され得る。
【０１２８】
[0103]１つまたは複数の例では、説明した機能は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せで実装され得る。ソフトウェアで実装する場合、機能は、１つまたは複数の命令またはコードとしてコンピュータ可読媒体上に記憶するか、あるいはコンピュータ可読媒体を介して送信することができ得る。コンピュータ可読媒体は、ある場所から別の場所へのコンピュータプログラムの転送を可能にする任意の媒体を含む、コンピュータデータ記憶媒体または通信媒体を含み得る。データ記憶媒体は、本開示で説明した技法の実装のための命令、コードおよび／またはデータ構造を取り出すために１つまたは複数のコンピュータあるいは１つまたは複数のプロセッサによってアクセスされ得る任意の利用可能な媒体であり得る。限定ではなく、例として、そのようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたは他の光ディスクストレージ、磁気ディスクストレージまたは他の磁気ストレージデバイス、フラッシュメモリ、あるいは命令またはデータ構造の形態の所望のプログラムコードを搬送または記憶するために使用され得、コンピュータによってアクセスされ得る、任意の他の媒体を備えることができる。同様に、いかなる接続も適切にコンピュータ可読媒体と称される。たとえば、ソフトウェアが、同軸ケーブル、光ファイバケーブル、ツイストペア、デジタル加入者回線（ＤＳＬ）、または赤外線、無線、およびマイクロ波などのワイヤレス技術を使用して、ウェブサイト、サーバ、または他のリモートソースから送信される場合、同軸ケーブル、光ファイバケーブル、ツイストペア、ＤＳＬ、または赤外線、無線、およびマイクロ波などのワイヤレス技術は、媒体の定義に含まれる。本明細書で使用するディスク（disk）およびディスク（disc）は、コンパクトディスク（disc）（ＣＤ）、レーザディスク（disc）、光ディスク（disc）、デジタル多用途ディスク（disc）（ＤＶＤ）、フロッピー（登録商標）ディスク（disk）およびブルーレイ（登録商標）ディスク（disc）を含み、ディスク（disk）は、通常、データを磁気的に再生し、ディスク（disc）は、データをレーザで光学的に再生する。上記の組合せもコンピュータ可読媒体の範囲内に含めるべきである。
【０１２９】
[0104]コードは、１つまたは複数のデジタル信号プロセッサ（ＤＳＰ）などの１つまたは複数のプロセッサ、汎用マイクロプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブル論理アレイ（ＦＰＧＡ）、あるいは他の等価な集積回路またはディスクリート論理回路によって実行され得る。したがって、本明細書で使用する「プロセッサ」という用語は、前述の構造、または本明細書で説明する技法の実装に好適な他の構造のいずれかを指す。さらに、いくつかの態様では、本明細書で説明した機能は、符号化および復号のために構成された専用のハードウェアおよび／またはソフトウェアモジュール内に提供され得、あるいは複合コーデックに組み込まれ得る。また、本技法は、１つまたは複数の回路または論理要素中に十分に実装され得る。
【０１３０】
[0105]本開示の技法は、ワイヤレスハンドセット、集積回路（ＩＣ）またはＩＣのセット（たとえば、チップセット）を含む、多種多様なデバイスまたは装置において実施され得る。本開示では、開示する技法を実行するように構成されたデバイスの機能的態様を強調するために様々な構成要素、モジュール、またはユニットについて説明したが、それらの構成要素、モジュール、またはユニットを、必ずしも異なるハードウェアユニットによって実現する必要はない。むしろ、上記で説明したように、様々なユニットが、一時的または非一時的のいずれかのコンピュータ可読媒体に記憶されている好適なソフトウェアおよび／またはファームウェアとともに、上記で説明したように１つまたは複数のプロセッサを含んで、コーデックハードウェアユニットにおいて組み合わせられるか、または相互動作ハードウェアユニットの集合によって与えられ得る。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［１］  クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための方法であって、
前記クライアントデバイスにより、クエリ画像の少なくとも１つの特徴を定義する画像特徴記述子のセットをクエリ画像から抽出することと、
第１の量子化レベルで量子化された前記画像特徴記述子のセットを表す第１のクエリデータを生成するために、前記クライアントデバイスにより、前記第１の量子化レベルで前記画像特徴記述子のセットを量子化することと、
前記クライアントデバイスにより、前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信することと、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが第２の量子化レベルで量子化された前記画像特徴記述子のセットを表すように、前記クライアントデバイスにより、前記第１のクエリデータを拡張することと、前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子のセットの表現を達成し、
前記第１のクエリデータを精製するために、前記クライアントデバイスにより、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信することと、
を備える方法。
［２］  前記第２のクエリデータを送信することは、前記視覚探索デバイスが前記第１の量子化レベルで量子化された前記画像特徴記述子を表す前記第１のクエリデータを使用して前記視覚探索を実行することと同時に、前記第２のクエリデータを送信することを備える、［１］に記載の方法。
［３］  第１の量子化レベルで前記画像特徴記述子を量子化することは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を決定することを含み、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
第２のクエリデータを求めることは、
追加の再構成点のそれぞれが前記面のそれぞれの中心に位置するように、追加の再構成点を決定することと、
前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定することと、
前記オフセットベクトルを含むように前記第２のクエリデータを生成することと、
を含む請求項１に記載の方法。
［４］  第１の量子化レベルで前記画像特徴記述子を量子化することは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を決定することを含み、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
第２のクエリデータを求めることは、
前記追加の再構成点のそれぞれが前記ボロノイセルの前記交点に位置するように、追加の再構成点を決定することと、
前記前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定することと、
前記オフセットベクトルを含むように前記第２のクエリデータを生成することと、
を含む［１］に記載の方法。
［５］  前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記画像特徴記述子を第１の量子化レベルで量子化することは、
勾配のヒストグラムに対して最近のタイプを決定することと、前記タイプは、所与の共通分母を有する有理数のセットであり、前記有理数のセットの合計は１に等しい、
前記決定されたタイプを、前記所与の共通分母を有するすべての可能なタイプに対して前記決定されたタイプの辞書式配列を一意に識別するインデックスにマッピングすることと、を含み、
前記第１のクエリデータは前記タイプのインデックスを含む、
［１］に記載の方法。
［６］  前記第２のクエリデータを送信する前に、前記視覚探索デバイスで維持されるデータベース内を探索した結果として得られた、前記視覚探索デバイスからの識別データを受信することと、
前記第２のクエリデータを送ることなく前記視覚探索を終わらせることと、
前記識別データを視覚探索アプリケーションの中で使用することと、
をさらに備える、［１］に記載の方法。
［７］  前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを決定することと、前記第３のレベルは、前記第２の量子化レベルで量子化するときよりも一層正確な前記画像特徴記述子データの表現を達成し、
前記第２のクエリデータで拡張された後の前記第１のクエリデータを連続的に精製するために、前記第３のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信することと、
をさらに備える、［１］に記載の方法。
［８］  クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための方法であって、
前記視覚探索デバイスにより、第１のクエリデータを使用して前記視覚探索を実行することと、前記第１のクエリデータは、画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子のセットを表し、
前記視覚探索デバイスにより、第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して受信することと、
前記第２のクエリデータは、前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた前記第１のクエリデータが、第２の量子化レベルで量子化された前記画像特徴記述子のセットを表すように前記第１のデータを拡張し、
前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記第２の量子化レベルで量子化された前記画像特徴記述子を表す、アップデートされた第１のクエリデータを生成するために、前記視覚探索デバイスにより、前記第１のクエリデータを前記第２のクエリデータでアップデートすることと、
前記視覚探索デバイスにより、前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行することと、
を備える方法。
［９］  前記第１のクエリデータを使用して前記視覚探索を実行することは、前記第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して前記視覚探索デバイスに送信することと同時に、前記第１のクエリデータを使用して前記視覚探索を実行することを備える、［８］に記載の方法。
［１０］  前記第１のクエリデータは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記面のそれぞれの中心に位置し、
前記アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートすることは、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加することを含む、［８］に記載の方法。
［１１］  前記第１のクエリデータは、前記再構成点がそれぞれ前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記ボロノイセルの交点に位置し、
前記アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートすることは、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加することを含む、［８］に記載の方法。
［１２］  前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記第１のクエリデータは、タイプインデックスを含み、前記タイプインデックスは、所与の共通分母を有するタイプの辞書式配列内の１つのタイプを一意に識別し、前記タイプのそれぞれは、前記所与の共通分母を有する有理数のセットを備え、各タイプの有理数の前記セットを合計すると１になり、
前記方法は、さらに、
前記タイプインデックスを前記タイプにマッピングすることと、
前記タイプから前記勾配のヒストグラムを再構成することと、をさらに備え、
前記第１のクエリデータを使用して前記視覚探索を実行することは、前記再構成された勾配のヒストグラムを使用して前記視覚探索を実行することを含む、［８］に記載の方法。
［１３］  前記第１のクエリデータをアップデートすることは、
アップデートされたタイプを生成するために、前記タイプを前記第２のクエリデータでアップデートすることと、
前記アップデートされたタイプに基づいて前記画像特徴記述子を前記第２の量子化レベルで再構成することと、
を備える［１２］に記載の方法。
［１４］  前記第２のクエリデータを受信する前に、前記第１のクエリデータを使用して前記視覚探索デバイスによって維持されているデータベースの中で前記視覚探索を実行することの結果として、識別データを決定することと、
前記視覚探索を効果的に終わらせるために、前記第２のクエリデータを受信する前に前記識別データを送信することと、
をさらに備える［８］に記載の方法。
［１５］  前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを受信することと、前記第３の量子化レベルは、前記第２の量子化レベルで量子化するときより正確な前記画像特徴記述子データの表現を達成し、
前記第３の量子化レベルで量子化された前記画像特徴記述子を表す、２回アップデートされた第１のクエリデータを生成するために、前記アップデートされた第１のクエリデータを前記第３のクエリデータでアップデートすることと、
前記視覚探索を前記２回アップデートされた第１のクエリデータを使用して実行することと、
をさらに備える［８］に記載の方法。
［１６］  視覚探索を実行するために、クエリデータをネットワークを介して視覚探索デバイスに送信するクライアントデバイスであって、
画像を定義するデータを記憶するメモリと、
画像特徴記述子のセットを前記画像から抽出する特徴抽出ユニットと、前記画像特徴記述子は前記画像の少なくとも１つの特徴を定義し、
第１の量子化レベルで量子化された前記画像特徴記述子を表す第１のクエリデータを生成するために、前記画像特徴記述子を前記第１の量子化レベルで量子化する特徴圧縮ユニットと、
前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信するインターフェースと、を備え、
前記特徴圧縮ユニットは、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルにおいて量子化された前記画像特徴記述子を表すように、前記第１のクエリデータを拡張し、
前記第２の量子化レベルは、前記第１の量子化レベルにおいて量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記インターフェースは、前記第１のクエリデータを連続的に精製するために、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する、クライアントデバイス。
［１７］  前記視覚探索デバイスが、前記第１の量子化レベルで量子化された前記画像特徴記述子を表す前記第１のクエリデータを使用して前記視覚探索を実行することと同時に、前記インターフェースが前記第２のクエリデータを送信する、［１６］に記載のクライアントデバイス。
［１８］  前記特徴圧縮ユニットは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を決定し、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記特徴圧縮ユニットは、追加の再構成点のそれぞれが前記面のそれぞれの中心に位置するように、追加の再構成点を決定し、前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定し、前記オフセットベクトルを含むように前記第２のクエリデータを生成する、
［１６］に記載のクライアントデバイス。
［１９］  前記特徴圧縮ユニットは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を決定し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記特徴圧縮ユニットは、追加の再構成点のそれぞれが前記ボロノイセルの前記交点に位置するように追加の再構成点をさらに決定し、前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定し、前記オフセットベクトルを含むように前記第２のクエリデータを生成する、
［１６］に記載のクライアントデバイス。
［２０］  前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記特徴圧縮ユニットは、前記勾配のヒストグラムに対して最近のタイプを決定し、前記タイプは所与の共通分母を有する有理数のセットであり、前記有理数のセットの合計は１に等しい、
前記特徴圧縮ユニットは、さらに、前記決定されたタイプを、前記所与の共通分母を有するすべての可能なタイプに対して前記決定されたタイプの辞書式配列を一意に識別するタイプインデックスにマッピングし、
前記第１のクエリデータは、前記タイプインデックスを含む、
［１６］に記載のクライアントデバイス。
［２１］  前記インターフェースは、前記第２のクエリデータを送信する前に、前記視覚探索デバイスで維持されるデータベース内を探索した結果として得られた、前記視覚探索デバイスからの識別データを受信し、
前記クライアントデバイスは、前記識別データを受信することに応答して前記第２のクエリデータを送ることなく前記視覚探索を終了し、
前記クライアントデバイスは、前記識別データを使用する視覚探索アプリケーションを実行するプロセッサを含む、
［１６］に記載のクライアントデバイス。
［２２］  前記第２のクエリデータで拡張された後の前記第１のクエリデータが前記第３のクエリデータでアップデートされると、前記連続的にアップデートされた第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを決定し、前記第３のレベルは、前記第２の量子化レベルで量子化するときよりも一層正確な前記画像特徴記述子データの表現を達成し、
前記インターフェースは、前記第２のクエリデータで拡張された後の前記第１のクエリデータを連続的に精製するために、前記第３のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する、
［１６］に記載のクライアントデバイス。
［２３］  クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するための視覚探索デバイスであって、
画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子のセットを表す第１のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信するインターフェースと、
前記第１のクエリデータを使用して前記視覚探索を実行する特徴マッチングユニットと、
を備え、
前記インターフェースは、第２のクエリデータを前記クライアントデバイスから前記ネットワークを介してさらに受信し、
前記第２のクエリデータは、前記第１のクエリデータが前記第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルにおいて量子化された画像特徴記述子を表すように前記第１のデータを拡張し、
前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記視覚探索デバイスは、さらに、
第２の量子化レベルで量子化された前記画像特徴記述子を表す、アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートする特徴再構成ユニットを備え、
前記特徴マッチングユニットは、前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行する、視覚探索デバイス。
［２４］  前記特徴マッチングユニットは、前記第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して前記視覚探索デバイスに送信することと同時に、前記第１のクエリデータを使用して前記視覚探索を実行する、［２３］に記載の視覚探索デバイス。
［２５］  前記第１のクエリデータは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれ対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記面のそれぞれの中心に位置し、
前記特徴再構成ユニットは、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加する、請求項２３に記載の視覚探索デバイス。
［２６］  前記第１のクエリデータは、前記再構成点がそれぞれ前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記ボロノイセルの交点に位置し、
前記特徴再構成ユニットは、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加する、
［２３］に記載の視覚探索デバイス。
［２７］  前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記第１のクエリデータはタイプインデックスを含み、前記タイプインデックスは、所与の共通分母を有するタイプの辞書式配列内の１つのタイプを一意に識別し、前記タイプのそれぞれは、前記所与の共通分母を有する有理数のセットを備え、各タイプの有理数の前記セットを合計すると１になり、
前記特徴再構成ユニットは、前記タイプインデックスを前記タイプにマッピングし、前記タイプから前記勾配のヒストグラムを再構成し、
前記特徴マッチングユニットは、前記再構成された勾配のヒストグラムを使用して前記視覚探索を実行する、
［２３］に記載の視覚探索デバイス。
［２８］  前記特徴再構成ユニットは、アップデートされたタイプを生成するために、前記タイプを前記第２のクエリデータでさらにアップデートし、前記アップデートされたタイプに基づいて前記画像特徴記述子を前記第２の量子化レベルで再構成する、［２７］に記載の視覚探索デバイス。
［２９］  前記特徴マッチングユニットは、前記第２のクエリデータを受信する前に、前記第１のクエリデータを使用して前記視覚探索デバイスによって維持されているデータベースの中で前記視覚探索を実行することの結果として、識別データを決定し、
前記インターフェースは、前記視覚探索を効果的に終了するために、前記第２のクエリデータを受信する前に前記識別データを送信する、
［２３］に記載の視覚探索デバイス。
［３０］  前記インターフェースは、前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを受信し、
前記第３の量子化レベルは、前記第２の量子化レベルにおいて量子化するときより正確な前記画像特徴記述子データの表現を達成し、
前記特徴再構成ユニットは、前記第３の量子化レベルで量子化された前記画像特徴記述子を表す、２回アップデートされた第１のクエリデータを生成するために、前記アップデートされた第１のクエリデータを前記第３のクエリデータでアップデートし、
前記特徴マッチングユニットは、前記２回アップデートされた第１のクエリデータを使用して前記視覚探索を実行する、
［２３］に記載の視覚探索デバイス。
［３１］  クエリデータをネットワークを介して視覚探索デバイスに送信するデバイスであって、
クエリ画像を定義するデータを記憶する手段と、
画像特徴記述子のセットを前記クエリ画像から抽出する手段と、前記画像特徴記述子は前記クエリ画像の少なくとも１つの特徴を定義し、
第１の量子化レベルで量子化された前記画像特徴記述子のセットを表す第１のクエリデータを生成するために、第１の量子化レベルで前記画像特徴記述子のセットを量子化する手段と、
前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する手段と、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された画像特徴記述子の前記セットを表すように、前記第１のクエリデータを拡張する第２のクエリデータを決定する手段と、前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子のセットの表現を達成し、
前記第１のクエリデータを精製するために、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する手段と、
を備えるデバイス。
［３２］  前記第２のクエリデータを送信する手段は、前記視覚探索デバイスが前記第１の量子化レベルで量子化された前記画像特徴記述子を表す前記第１のクエリデータを使用して前記視覚探索を実行するのと同時に、前記第２のクエリデータを送信する手段を備える、［３１］に記載のデバイス。
［３３］  前記第１の量子化レベルで前記画像特徴記述子を量子化する手段は、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義された異なるボロノイセルのそれぞれの中心に位置するように再構成点を決定する手段を含み、前記ボロノイセルが、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータを決定する手段は、
追加の再構成点のそれぞれが前記面のそれぞれの中心に位置するように、追加の再構成点を決定する手段と、
前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定する手段と、
前記オフセットベクトルを含むように前記第２のクエリデータを生成する手段と、
を含む［３１］に記載のデバイス。
［３４］  前記第１の量子化レベルで前記画像特徴記述子を量子化する手段は、前記再構成点にそれぞれが、前記画像特徴記述子に対して定義された異なるボロノイセルのそれぞれの中心に位置するように再構成点を決定する手段を含み、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータを決定する手段は、
前記追加の再構成点のそれぞれが前記ボロノイセルの前記交点に位置するように追加の再構成点を決定する手段と、
前に決定された再構成点のそれぞれからのオフセットベクトルとして前記追加の再構成点を指定する手段と、
前記オフセットベクトルを含むように前記第２のクエリデータを生成する手段と、
を含む［３１］に記載のデバイス。
［３５］  前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記画像特徴記述子を第１の量子化レベルで量子化する手段は、
勾配のヒストグラムに対して最近のタイプを決定する手段と、前記タイプは所与の共通分母を有する有理数のセットであり、前記有理数のセットの合計は１に等しい、
前記決定されたタイプを、前記所与の共通分母を有するすべての可能なタイプに対して前記決定されたタイプの辞書式配列を一意に識別するタイプインデックスにマッピングする手段と、を含み、
前記第１のクエリデータは前記タイプインデックスを含む、
［３１］に記載のデバイス。
［３６］  前記第２のクエリデータを送信する前に、前記視覚探索デバイスで維持されるデータベース内を探索した結果として得られた、前記視覚探索デバイスからの識別データを受信する手段と、
前記第２のクエリデータを送ることなく前記視覚探索を終了する手段と、
視覚探索アプリケーション中に、前記識別データを使用する手段と、
をさらに備える、［３１］に記載のデバイス。
［３７］  前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、前記連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを決定する手段と、前記第３の量子化レベルは、前記第２の量子化レベルで量子化するときより正確な前記画像特徴記述子データの表現を達成し、
前記第２のクエリデータで拡張された後の前記第１のクエリデータを連続的に精製するために、前記第３のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する手段と、
をさらに備える［３１］に記載のデバイス。
［３８］  クライアントデバイスがクエリデータをネットワークを介して視覚探索デバイスに送信するネットワークシステムにおいて視覚探索を実行するためのデバイスであって、
画像から抽出され、第１の量子化レベルでの量子化により圧縮された画像特徴記述子のセットを表す第１のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信する手段と、
前記第１のクエリデータを使用して前記視覚探索を実行する手段と、
前記第２のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信する手段と、前記第２のクエリデータは、前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた前記第１のクエリデータが、第２の量子化レベルにおいて量子化された画像特徴記述子の前記セットを表すものとなるように前記第１のデータを拡張し、前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記第２の量子化レベルで量子化された前記画像特徴記述子を表す、アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートする手段と、
前記視覚探索を、前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行する手段と、
を備えるデバイス。
［３９］  前記第１のクエリデータを使用して前記視覚探索を実行する手段は、前記第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して前記視覚探索デバイスに送信することと同時に、前記第１のクエリデータを使用して前記視覚探索を実行する手段を備える、［３８］に記載のデバイス。
［４０］  前記第１のクエリデータは、前記再構成点のそれぞれが、前記画像特徴記述子に対して定義された異なるボロノイセルのそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記面のそれぞれの中心に位置し、
前記アップデートされた第１のクエリデータを生成するために前記第１のクエリデータを前記第２のクエリデータでアップデートする手段は、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加する手段を含む、［３８］に記載のデバイス。
［４１］  前記第１のクエリデータは、前記再構成点がそれぞれ前記画像特徴記述子に対して定義されたボロノイセルの異なるそれぞれの中心に位置するように再構成点を定義し、前記ボロノイセルは、前記ボロノイセル間に前記境界を画定する面と、２つ以上の前記面が交差する交点とを含み、
前記第２のクエリデータは、前に定義された再構成点のそれぞれに対する追加の再構成点の位置を指定するオフセットベクトルを含み、前記追加の再構成点はそれぞれ前記ボロノイセルの交点に位置し、
前記アップデートされた第１のクエリデータを生成するために前記第１のクエリデータを前記第２のクエリデータでアップデートする手段は、前記オフセットベクトルに基づいて前記追加の再構成点を前記前に定義された再構成点に追加する手段を含む、
［３８］に記載のデバイス。
［４２］  前記画像特徴記述子のそれぞれは、前記画像内の特徴位置の周辺でサンプリングされた勾配のヒストグラムを備え、
前記第１のクエリデータはタイプインデックスを含み、前記タイプインデックスは、所与の共通分母を有するタイプの辞書式配列内の１つのタイプを一意に識別し、前記タイプのそれぞれは、前記所与の共通分母を有する有理数のセットを備え、各タイプの有理数の前記セットを合計すると１になり、
前記デバイスは、
前記タイプインデックスを前記タイプにマッピングする手段と、
前記タイプから前記勾配のヒストグラムを再構成する手段と、
をさらに備え、
前記第１のクエリデータを使用して前記視覚探索を実行するための手段は、前記再構成された勾配のヒストグラムを使用して前記視覚探索を実行する手段を含む、［３８］に記載のデバイス。
［４３］  前記第１のクエリデータをアップデートする手段は、
アップデートされたタイプを生成するために、前記タイプを前記第２のクエリデータでアップデートする手段と、
前記アップデートされたタイプに基づいて前記画像特徴記述子を前記第２の量子化レベルで再構成する手段と、
を備える［４２］に記載のデバイス。
［４４］  前記第２のクエリデータを受信する前に、前記第１のクエリデータを使用して前記視覚探索デバイスによって維持されているデータベースの中で前記視覚探索を実行することの結果として、識別データを決定する手段と、
前記視覚探索を効果的に終わらせるために、前記第２のクエリデータを受信する前に前記識別データを送信する手段と、
をさらに備える［３８］に記載のデバイス。
［４５］  前記第２のクエリデータで拡張された後の前記第１のクエリデータが第３のクエリデータでアップデートされると、連続してアップデートされた前記第１のクエリデータが、第３の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１および第２のクエリデータをさらに拡張する第３のクエリデータを受信する手段と、前記第３の量子化レベルは、前記第２の量子化レベルにおいて量子化するときより正確な前記画像特徴記述子データの表現を達成し、
前記第３の量子化レベルで量子化された前記画像特徴記述子を表す、２回アップデートされた第１のクエリデータを生成するために、前記アップデートされた第１のクエリデータを前記第３のクエリデータでアップデートする手段と、
前記２回アップデートされた第１のクエリデータを使用して前記視覚探索を実行する手段と、
をさらに備える、［３８］に記載のデバイス。
［４６］  命令を備える非一時的コンピュータ可読媒体であって、実行されたとき、１つまたは複数のプロセッサに、
クエリ画像を定義するデータを記憶させ、
前記クエリ画像の特徴を定義する画像特徴記述子を前記クエリ画像から抽出させ、
第１の量子化レベルで量子化された前記画像特徴記述子を表す第１のクエリデータを生成するために、前記画像特徴記述子を第１の量子化レベルで量子化させ、
前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信させ、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された前記画像特徴記述子を表すように、前記第１のクエリデータを拡張する前記第２のクエリデータを求めさせ、ここで、前記第２の量子化レベルは、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記第１のクエリデータを連続的に精製するために、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信させる、
命令を備える非一時的コンピュータ可読媒体。
［４７］  命令を備える非一時的コンピュータ可読媒体であって、実行されたとき、１つまたは複数のプロセッサに、
画像から抽出され、第１の量子化レベルで量子化により圧縮された画像特徴記述子を表す第１のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信させ、
前記第１のクエリデータを使用して前記視覚探索を実行させ、
前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた前記第１のクエリデータが、前記第１の量子化レベルで量子化するときより正確な前記画像特徴記述子の表現を達成する第２の量子化レベルで量子化された画像特徴記述子を表すように前記第１のデータを拡張する前記第２のクエリデータを、前記クライアントデバイスから前記ネットワークを介して受信させ、
第２の量子化レベルで量子化された前記画像特徴記述子を表す、アップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートさせ、
前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行させる命令を備える、非一時的コンピュータ可読媒体。
［４８］  視覚探索を実行するためのネットワークシステムであって、
クライアントデバイスと、
視覚探索デバイスと、
前記視覚探索を実行するために、前記クライアントデバイスと視覚探索デバイスとを互いに通信するようにインターフェースするネットワークと、を備え、
前記クライアントデバイスは、
画像を定義するデータを記憶する非一時的コンピュータ可読媒体と、
前記画像の特徴を定義する画像特徴記述子を前記画像から抽出し、第１の量子化レベルで量子化された前記画像特徴記述子を表す第１のクエリデータを生成するために、前記第１の量子化レベルで前記画像特徴記述子を量子化するクライアントプロセッサと、
前記第１のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信する第１のネットワークインターフェースと、を備え、
前記視覚探索デバイスは、
前記第１のクエリデータを前記ネットワークを介して前記クライアントデバイスから受信する第２のネットワークインターフェースと、
前記第１のクエリデータを使用して前記視覚探索を実行するサーバプロセッサと、を含み、
前記クライアントプロセッサは、前記第１のクエリデータが第２のクエリデータでアップデートされると、前記アップデートされた第１のクエリデータが、第２の量子化レベルで量子化された前記画像特徴記述子を表すように前記第１のクエリデータを拡張する前記第２のクエリデータを決定し、前記第２の量子化レベルは、前記第１の量子化レベルにおいて量子化するときより正確な前記画像特徴記述子の表現を達成し、
前記第１のネットワークインターフェースは、前記第１のクエリデータを連続的に精製するために、前記第２のクエリデータを前記ネットワークを介して前記視覚探索デバイスに送信し、
前記第２のネットワークインターフェースは、前記第２のクエリデータを前記クライアントデバイスから前記ネットワークを介して受信し、
前記サーバプロセッサは、第２の量子化レベルで量子化された前記画像特徴記述子を表すアップデートされた第１のクエリデータを生成するために、前記第１のクエリデータを前記第２のクエリデータでアップデートし、前記アップデートされた第１のクエリデータを使用して前記視覚探索を実行する、
ネットワークシステム。
【図１】
0005639277.tif 000041
【図２】
0005639277.tif 000042
【図３】
0005639277.tif 000043
【図４】
0005639277.tif 000044
【図５】
0005639277.tif 000045
【図６】
0005639277.tif 000046
【図７】
0005639277.tif 000047
【図８】
0005639277.tif 000048
【図９Ａ】
0005639277.tif 000049
【図９Ｂ】
0005639277.tif 000050
【図１０】
0005639277.tif 000051