(57)【特許請求の範囲】
【請求項１】
視覚探索デバイスで視覚探索を実行するための方法であって、
前記視覚探索デバイスで、視覚探索クエリによって提供されたクエリ特徴記述子と、複数の参照特徴記述子のそれぞれとの間の距離を計算するステップであって、前記視覚探索クエリが前記視覚探索を開始するステップと、
前記視覚探索デバイスで、クラスタリングアルゴリズムに従って、前記計算された距離のうちの1つまたは複数の第1のグループおよび前記計算された距離の第2のグループを決定するステップであって、計算された距離の前記第2のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照特徴記述子のうちの関連する参照特徴記述子が前記クエリ特徴記述子に近いことを示す前記計算された距離のグループを前記計算された距離の前記第1のグループが含み、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記クエリ特徴記述子から離れていることを示す前記計算された距離のグループを前記計算された距離の前記第2のグループが含むステップと、
前記計算された距離の前記決定された第1のグループおよび前記計算された距離の前記第2のグループに基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの最小の距離に関連付けられる前記複数の参照特徴記述子のうちの1つと一致するかどうかを前記視覚探索デバイスで決定するステップと
を備え、
前記クエリ特徴記述子が、前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定するステップが、
第1のグループ距離平均を生成するために、前記第1のグループ内にあると決定された前記計算された距離のうちの2つまたはそれ以上の平均を計算するステップと、
第2のグループ距離平均を生成するために、前記第2のグループ内にあると決定された前記計算された距離の平均を計算するステップと、
平均距離比測定値を生成するために、前記第2のグループ距離平均で前記第1のグループ距離平均を割るステップと、
前記平均距離比測定値としきい値とを比較するステップと、
前記比較に基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの前記最小の距離に関連付けられる前記複数の参照特徴記述子のうちの前記1つと一致するかどうかを決定するステップと
を含む、方法。
【請求項２】
前記計算された距離のうちの1つまたは複数の前記第1のグループ、および前記計算された距離の前記第2のグループを決定するステップが、k平均法クラスタリングアルゴリズム、ガウシアンフィッティングアルゴリズム、およびグラフカッティングアルゴリズムのうちの1つまたは複数に従って、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ、および前記計算された距離の前記第2のグループを決定するステップを含む、請求項1に記載の方法。
【請求項３】
参照画像のセットが、重複する参照画像を含まないように、参照特徴記述子の対応するグループに対して、前記第1のグループ内にあると決定された前記計算された距離が計算される前記複数の参照特徴記述子のグループに関連付けられた参照画像を含む参照画像の一意のグループを決定するステップと、
参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てるステップと、
前記割り当てられた評価に基づいて前記参照画像を順序付けるステップと、
前記視覚探索クエリに応答して、前記順序付けられた参照画像を返すステップと
をさらに備える、請求項1に記載の方法。
【請求項４】
参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てるステップが、
それぞれの前記参照画像に一定の評価を割り当てるステップ、
前記クエリ特徴記述子と、前記複数の参照特徴記述子のうちの最も近い参照特徴記述子との間の計算された距離と比較して、前記対応する計算された距離の距離比に比例する評価を割り当てるステップ、および
前記第1のグループの前記計算された距離が最小から最大へ順序づけられる場合、前記第1のグループ内の前記対応する計算された距離のランクに比例する評価を割り当てるステップ
のうちの1つまたは複数を含む、請求項3に記載の方法。
【請求項５】
前記クエリ特徴記述子が、視覚探索アルゴリズムに従ってクエリ画像データから抽出され、前記視覚探索クエリによって提供された、複数のクエリ特徴記述子のうちの1つを備え、
前記方法が、
計算された複数の距離を生成するために、前記複数のクエリ特徴記述子のそれぞれについて、前記複数のクエリ特徴記述子のうちの現在の1つと、前記複数の参照特徴記述子のそれぞれとの間の距離を計算するステップと、
前記複数の距離のそれぞれについて、前記クラスタリングアルゴリズムに従って、前記計算された複数の距離の前記第1のグループ、および前記計算された複数の距離の前記第2のグループを決定するステップであって、前記計算された複数の距離の前記第2のグループ内にあると決定された前記計算された複数の距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記クエリ特徴記述子に近いことを示す前記計算された距離のグループを前記計算された複数の距離の前記第1のグループが含み、計算された複数の距離の前記第1のグループ内にあると決定された前記計算された複数の距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記複数のクエリ特徴記述子のうちの前記現在のクエリ特徴記述子から離れていることを示す前記計算された複数の距離のグループを前記計算された複数の距離の前記第2のグループが含むステップと、
前記計算された複数の距離の前記決定された第1のグループおよび前記計算された距離の前記第2のグループに基づいて、前記複数のクエリ特徴記述子のそれぞれが、前記計算された複数の距離のうちの最小の距離に関連付けられる前記複数の参照特徴記述子のうちの1つと一致するかどうかを前記視覚探索デバイスで決定するステップと
をさらに備える、請求項1に記載の方法。
【請求項６】
参照画像のセットが、重複する参照画像を含まないように、前記複数のクエリ特徴記述子のそれぞれについて、参照特徴記述子の対応するグループに対して、前記第1のグループ内にあると決定された前記計算された複数の距離が計算される前記複数の参照特徴記述子のグループに関連付けられた参照画像を含む参照画像の一意のグループを決定するステップと、
前記複数のクエリ特徴記述子のそれぞれに決定された、参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てるステップと、
前記複数のクエリ特徴記述子のそれぞれに関連して前記評価を割り当てるステップの後で、前記割り当てられた評価に基づいて前記参照画像を順序付けるステップと、
前記視覚探索クエリに応答して、前記順序付けられた参照画像を返すステップと
をさらに備える、請求項5に記載の方法。
【請求項７】
前記クエリ特徴記述子が、局所特徴ベースの視覚探索アルゴリズムに従ってクエリ画像から抽出される、請求項1に記載の方法。
【請求項８】
前記局所特徴ベースの視覚探索アルゴリズムがスケール不変特徴変換(SIFT)アルゴリズムを備える、請求項7に記載の方法。
【請求項９】
クライアントデバイスから前記視覚探索デバイスのインターフェースを介して、圧縮されたクエリ特徴記述子として前記クエリ特徴記述子を受信するステップと、
前記視覚探索デバイスで、前記圧縮されたクエリ特徴記述子から前記クエリ特徴記述子を再構成するステップと
をさらに備える、請求項1に記載の方法。
【請求項１０】
視覚探索クエリによって提供されたクエリ特徴記述子と、複数の参照特徴記述子のそれぞれとの間の距離を計算するための手段であって、前記視覚探索クエリが視覚探索を開始する手段と、
クラスタリングアルゴリズムに従って、前記計算された距離のうちの1つまたは複数の第1のグループおよび前記計算された距離の第2のグループを決定するための手段であって、計算された距離の前記第2のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照特徴記述子のうちの関連する参照特徴記述子が前記クエリ特徴記述子に近いことを示す前記計算された距離のグループを前記計算された距離の前記第1のグループが含み、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記クエリ特徴記述子から離れていることを示す前記計算された距離のグループを前記計算された距離の前記第2のグループが含む手段と、
前記計算された距離の前記決定された第1のグループおよび前記計算された距離の前記第2のグループに基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの最小の距離に関連付けられる前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定するための手段と
を備え、
前記クエリ特徴記述子が、前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定するための手段が、
第1のグループ距離平均を生成するために、前記第1のグループ内にあると決定された前記計算された距離のうちの2つまたはそれ以上の平均を計算するための手段と、
第2のグループ距離平均を生成するために、前記第2のグループ内にあると決定された前記計算された距離の平均を計算するための手段と、
平均距離比測定値を生成するために、前記第2のグループ距離平均で前記第1のグループ距離平均を割るための手段と、
前記平均距離比測定値としきい値とを比較するための手段と、
前記比較に基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの前記最小の距離に関連付けられる前記複数の参照特徴記述子のうちの前記1つと一致するかどうかを決定するための手段と
をさらに備える、視覚探索を実行するための装置。
【請求項１１】
k平均法クラスタリングアルゴリズム、ガウシアンフィッティングアルゴリズム、およびグラフカッティングアルゴリズムのうちの1つまたは複数に従って、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ、および前記計算された距離の前記第2のグループを決定するための手段をさらに備える、請求項10に記載の装置。
【請求項１２】
参照画像のセットが、重複する参照画像を含まないように、参照特徴記述子の対応するグループに対して、前記第1のグループ内にあると決定された前記計算された距離が計算される、前記複数の参照特徴記述子のグループに関連付けられた参照画像を含む参照画像の一意のグループを決定するための手段と、
参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てるための手段と、
前記割り当てられた評価に基づいて前記参照画像を順序付けるための手段と、
前記視覚探索クエリに応答して、前記順序付けられた参照画像を返すための手段と
をさらに備える、請求項10に記載の装置。
【請求項１３】
それぞれの前記参照画像に一定の評価を割り当てるための手段、
前記クエリ特徴記述子と、前記複数の参照特徴記述子のうちの最も近い参照特徴記述子との間の計算された距離と比較して、前記対応する計算された距離の距離比に比例する評価を割り当てるための手段、および
前記第1のグループの前記計算された距離が最小から最大へ順序づけられる場合、前記第1のグループ内の前記対応する計算された距離のランクに比例する評価を割り当てるための手段
のうちの1つまたは複数をさらに備える、請求項12に記載の装置。
【請求項１４】
前記クエリ特徴記述子が、視覚探索アルゴリズムに従ってクエリ画像データから抽出され、前記視覚探索クエリによって提供された、複数のクエリ特徴記述子のうちの1つを備え、
前記装置が、
計算された複数の距離を生成するために、前記複数のクエリ特徴記述子のそれぞれについて、前記複数のクエリ特徴記述子のうちの現在の1つと、前記複数の参照特徴記述子のそれぞれとの間の距離を計算するための手段と、
前記複数の距離のそれぞれについて、前記クラスタリングアルゴリズムに従って、前記計算された複数の距離の前記第1のグループ、および前記計算された複数の距離の前記第2のグループを決定するための手段であって、前記計算された複数の距離の前記第2のグループ内にあると決定された前記計算された複数の距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記クエリ特徴記述子に近いことを示す前記計算された距離のグループを前記計算された複数の距離の前記第1のグループが含み、計算された複数の距離の前記第1のグループ内にあると決定された前記計算された複数の距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記複数のクエリ特徴記述子のうちの前記現在のクエリ特徴記述子から離れていることを示す前記計算された複数の距離のグループを前記計算された複数の距離の前記第2のグループが含む手段と、
前記計算された複数の距離の前記決定された第1のグループおよび前記計算された距離の前記第2のグループに基づいて、前記複数のクエリ特徴記述子のそれぞれが、前記計算された複数の距離のうちの最小の距離に関連付けられる前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定するための手段と
をさらに備える、請求項10に記載の装置。
【請求項１５】
参照画像のセットが、重複する参照画像を含まないように、前記複数のクエリ特徴記述子のそれぞれについて、参照特徴記述子の対応するグループに対して、前記第1のグループ内にあると決定された前記計算された複数の距離が計算される前記複数の参照特徴記述子のグループに関連付けられた参照画像を含む参照画像の一意のグループを決定するための手段と、
前記複数のクエリ特徴記述子のそれぞれに決定された、参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てるための手段と、
前記複数のクエリ特徴記述子のそれぞれに関連して前記評価を割り当てるステップの後で、前記割り当てられた評価に基づいて前記参照画像を順序付けるための手段と、
前記視覚探索クエリに応答して、前記順序付けられた参照画像を返すための手段と
をさらに備える、請求項14に記載の装置。
【請求項１６】
前記クエリ特徴記述子が、局所特徴ベースの視覚探索アルゴリズムに従ってクエリ画像から抽出される、請求項10に記載の装置。
【請求項１７】
前記局所特徴ベースの視覚探索アルゴリズムがスケール不変特徴変換(SIFT)アルゴリズムを備える、請求項16に記載の装置。
【請求項１８】
クライアントデバイスから視覚探索デバイスのインターフェースを介して、圧縮されたクエリ特徴記述子として前記クエリ特徴記述子を受信するための手段と、
前記視覚探索デバイスで、前記圧縮されたクエリ特徴記述子から前記クエリ特徴記述子を再構成するための手段と
をさらに備える、請求項10に記載の装置。
【請求項１９】
クエリ特徴記述子を受信するように構成されたインターフェースと、
視覚探索クエリによって提供された前記クエリ特徴記述子と、複数の参照特徴記述子のそれぞれとの間の距離を計算するように構成された特徴マッチングユニットであって、前記視覚探索クエリが視覚探索を開始して、クラスタリングアルゴリズムに従って、前記計算された距離のうちの1つまたは複数の第1のグループ、および前記計算された距離の第2のグループを決定するように構成され、計算された距離の前記第2のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照特徴記述子のうちの関連する参照特徴記述子が前記クエリ特徴記述子に近いことを示す前記計算された距離のグループを前記計算された距離の前記第1のグループが含み、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記クエリ特徴記述子から離れていることを示す前記計算された距離のグループを前記計算された距離の前記第2のグループが含み、前記特徴マッチングユニットが、前記計算された距離の前記決定された第1のグループ、および前記計算された距離の前記第2のグループに基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの最小の距離に関連付けられる前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定するようにさらに構成される特徴マッチングユニットとを備え、
前記特徴マッチングユニットが、第1のグループ距離平均を生成するために、前記第1のグループ内にあると決定された前記計算された距離のうちの2つまたはそれ以上の平均を計算し、第2のグループ距離平均を生成するために、前記第2のグループ内にあると決定された前記計算された距離の平均を計算し、平均距離比測定値を生成するために、前記第2のグループ距離平均で前記第1のグループ距離平均を割り、前記平均距離比測定値としきい値とを比較し、前記比較に基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの前記最小の距離に関連付けられる前記複数の参照特徴記述子のうちの前記1つと一致するかどうかを決定するようにさらに構成される、視覚探索を実行するように構成された装置。
【請求項２０】
前記特徴マッチングユニットが、k平均法クラスタリングアルゴリズム、ガウシアンフィッティングアルゴリズム、およびグラフカッティングアルゴリズムのうちの1つまたは複数に従って、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ、および前記計算された距離の前記第2のグループを決定するように構成される、請求項19に記載の装置。
【請求項２１】
前記特徴マッチングユニットが、
参照画像のセットが、重複する参照画像を含まないように、参照特徴記述子の対応するグループに対して、前記第1のグループ内にあると決定された前記計算された距離が計算される前記複数の参照特徴記述子のグループに関連付けられた参照画像を含む参照画像の一意のグループを決定して、
参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てて、
前記割り当てられた評価に基づいて前記参照画像を順序付けて、
前記視覚探索クエリに応答して、前記順序付けられた参照画像を返す
ようにさらに構成される、請求項19に記載の装置。
【請求項２２】
前記特徴マッチングユニットが、それぞれの前記参照画像に一定の評価を割り当てること、前記クエリ特徴記述子と、前記複数の参照特徴記述子のうちの最も近い参照特徴記述子との間の計算された距離と比較して、前記対応する計算された距離の距離比に比例する評価を割り当てること、および前記第1のグループの前記計算された距離が最小から最大へ順序づけられる場合、前記第1のグループ内の前記対応する計算された距離のランクに比例する評価を割り当てることのうちの1つまたは複数によって前記評価を割り当てるように構成される、請求項21に記載の装置。
【請求項２３】
前記クエリ特徴記述子が、視覚探索アルゴリズムに従ってクエリ画像データから抽出され、前記視覚探索クエリによって提供された、複数のクエリ特徴記述子のうちの1つを備え、
前記特徴マッチングユニットが、
計算された複数の距離を生成するために、前記複数のクエリ特徴記述子のそれぞれについて、前記複数のクエリ特徴記述子のうちの現在の1つと、前記複数の参照特徴記述子のそれぞれとの間の距離を計算して、
前記複数の距離のそれぞれについて、前記クラスタリングアルゴリズムに従って、前記計算された複数の距離の前記第1のグループ、および前記計算された複数の距離の前記第2のグループを決定し、前記計算された複数の距離の前記第2のグループ内にあると決定された前記計算された複数の距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記クエリ特徴記述子に近いことを示す前記計算された距離のグループを前記計算された複数の距離の前記第1のグループが含み、計算された複数の距離の前記第1のグループ内にあると決定された前記計算された複数の距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記複数のクエリ特徴記述子のうちの前記現在のクエリ特徴記述子から離れていることを示す前記計算された複数の距離のグループを前記計算された複数の距離の前記第2のグループが含み、
前記計算された複数の距離の前記決定された第1のグループおよび前記計算された距離の前記第2のグループに基づいて、前記複数のクエリ特徴記述子のそれぞれが、前記計算された複数の距離のうちの最小の距離に関連付けられる前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定するようにさらに構成される、請求項19に記載の装置。
【請求項２４】
前記特徴マッチングユニットが、
参照画像のセットが、重複する参照画像を含まないように、前記複数のクエリ特徴記述子のそれぞれについて、参照特徴記述子の対応するグループに対して、前記第1のグループ内にあると決定された前記計算された複数の距離が計算される、前記複数の参照特徴記述子のグループに関連付けられた参照画像を含む参照画像の一意のグループを決定して、
前記複数のクエリ特徴記述子のそれぞれに決定された、参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てて、
前記複数のクエリ特徴記述子のそれぞれに関連して前記評価を割り当てるステップの後で、前記割り当てられた評価に基づいて前記参照画像を順序付けて、
前記インターフェースが、前記視覚探索クエリに応答して、前記順序付けられた参照画像を返すようにさらに構成される、請求項23に記載の装置。
【請求項２５】
前記クエリ特徴記述子が、局所特徴ベースの視覚探索アルゴリズムに従ってクエリ画像から抽出される、請求項19に記載の装置。
【請求項２６】
前記局所特徴ベースの視覚探索アルゴリズムがスケール不変特徴変換(SIFT)アルゴリズムを備える、請求項25に記載の装置。
【請求項２７】
前記インターフェースが、クライアントデバイスから、圧縮されたクエリ特徴記述子として前記クエリ特徴記述子を受信するように構成され、
前記装置が、視覚探索デバイスで、前記圧縮されたクエリ特徴記述子から前記クエリ特徴記述子を再構成するように構成された特徴再構成ユニットを含む、請求項19に記載の装置。
【請求項２８】
実行されると、1つまたは複数のプロセッサに、
視覚探索クエリによって提供されたクエリ特徴記述子と複数の参照特徴記述子のそれぞれとの間の距離を計算させて、前記視覚探索クエリが視覚探索を開始し、
クラスタリングアルゴリズムに従って、計算された距離のうちの1つまたは複数の第1のグループおよび計算された距離の第2のグループを決定させて、計算された距離の前記第2のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照特徴記述子のうちの関連する参照特徴記述子が前記クエリ特徴記述子に近いこと示す前記計算された距離のグループを前記計算された距離の前記第1のグループが含み、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記クエリ特徴記述子から離れていることを示す前記計算された距離のグループを前記計算された距離の前記第2のグループが含み、
前記計算された距離の前記決定された第1のグループおよび前記計算された距離の前記第2のグループに基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの最小の距離に関連付けられる前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定させ、
前記クエリ特徴記述子が、前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定させることは、
実行されると、前記1つまたは複数のプロセッサに、
第1のグループ距離平均を生成するために、前記第1のグループ内にあると決定された前記計算された距離のうちの2つまたはそれ以上の平均を計算させて、
第2のグループ距離平均を生成するために、前記第2のグループ内にあると決定された前記計算された距離の平均を計算させて、
平均距離比測定値を生成するために、前記第2のグループ距離平均で前記第1のグループ距離平均を割らせて、
前記平均距離比測定値としきい値とを比較させて、
前記比較に基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの前記最小の距離に関連付けられる前記複数の参照特徴記述子のうちの前記1つと一致するかどうかを決定させる
命令をさらに備える、コンピュータ可読記録媒体。
【請求項２９】
実行されると、前記1つまたは複数のプロセッサに、k平均法クラスタリングアルゴリズム、ガウシアンフィッティングアルゴリズム、およびグラフカッティングアルゴリズムのうちの1つまたは複数に従って、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ、および前記計算された距離の前記第2のグループを決定させる命令をさらに備える、請求項28に記載のコンピュータ可読記録媒体。
【請求項３０】
実行されると、前記1つまたは複数のプロセッサに、
参照画像のセットが、重複する参照画像を含まないように、参照特徴記述子の対応するグループに対して、前記第1のグループ内にあると決定された前記計算された距離が計算される前記複数の参照特徴記述子のグループに関連付けられた参照画像を含む参照画像の一意のグループを決定させて、
参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てさせて、
前記割り当てられた評価に基づいて前記参照画像を順序付けさせて、
前記視覚探索クエリに応答して、前記順序付けられた参照画像を返させる
命令をさらに備える、請求項28に記載のコンピュータ可読記録媒体。
【請求項３１】
実行されると、前記1つまたは複数のプロセッサに、
それぞれの前記参照画像に一定の評価を割り当てさせて、
前記クエリ特徴記述子と、前記複数の参照特徴記述子のうちの最も近い参照特徴記述子との間の計算された距離と比較して、前記対応する計算された距離の距離比に比例する評価を割り当てさせて、
前記第1のグループの前記計算された距離が最小から最大へ順序づけられる場合、前記第1のグループ内の前記対応する計算された距離のランクに比例する評価を割り当てさせる
命令をさらに備える、請求項30に記載のコンピュータ可読記録媒体。
【請求項３２】
前記クエリ特徴記述子が、視覚探索アルゴリズムに従ってクエリ画像データから抽出され、前記視覚探索クエリによって提供された、複数のクエリ特徴記述子のうちの1つを備え、
前記コンピュータ可読記録媒体が、実行されると、前記1つまたは複数のプロセッサに、
計算された複数の距離を生成するために、前記複数のクエリ特徴記述子のそれぞれについて、前記複数のクエリ特徴記述子のうちの現在の1つと、前記複数の参照特徴記述子のそれぞれとの間の距離を計算させて、
前記複数の距離のそれぞれについて、前記クラスタリングアルゴリズムに従って、前記計算された複数の距離の前記第1のグループ、および前記計算された複数の距離の前記第2のグループを決定させて、前記計算された複数の距離の前記第2のグループ内にあると決定された前記計算された複数の距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記クエリ特徴記述子に近いことを示す前記計算された距離のグループを前記計算された複数の距離の前記第1のグループが含み、計算された複数の距離の前記第1のグループ内にあると決定された前記計算された複数の距離のグループと比較して、前記複数の参照特徴記述子のうちの前記関連する参照特徴記述子が前記複数のクエリ特徴記述子のうちの前記現在のクエリ特徴記述子から離れていることを示す前記計算された複数の距離のグループを前記計算された複数の距離の前記第2のグループが含み、
前記計算された複数の距離の前記決定された第1のグループおよび前記計算された距離の前記第2のグループに基づいて、前記複数のクエリ特徴記述子のそれぞれが、前記計算された複数の距離のうちの最小の距離に関連付けられる前記複数の参照特徴記述子のうちの1つと一致するかどうかを決定させる
命令をさらに備える、請求項28に記載のコンピュータ可読記録媒体。
【請求項３３】
実行されると、前記1つまたは複数のプロセッサに、
参照画像のセットが、重複する参照画像を含まないように、前記複数のクエリ特徴記述子のそれぞれについて、参照特徴記述子の対応するグループに対して、前記第1のグループ内にあると決定された前記計算された複数の距離が計算される前記複数の参照特徴記述子のグループに関連付けられた参照画像を含む参照画像の一意のグループを決定させて、
前記複数のクエリ特徴記述子のそれぞれに決定された、参照画像の前記一意のグループ内にあると決定された前記参照画像のそれぞれに評価を割り当てさせて、
前記複数のクエリ特徴記述子のそれぞれに関連して前記評価を割り当てるステップの後で、前記割り当てられた評価に基づいて前記参照画像を順序付けさせて、
前記視覚探索クエリに応答して、前記順序付けられた参照画像を返させる
命令をさらに備える、請求項32に記載のコンピュータ可読記録媒体。
【請求項３４】
前記クエリ特徴記述子が、局所特徴ベースの視覚探索アルゴリズムに従ってクエリ画像から抽出される、請求項28に記載のコンピュータ可読記録媒体。
【請求項３５】
前記局所特徴ベースの視覚探索アルゴリズムがスケール不変特徴変換(SIFT)アルゴリズムを備える、請求項34に記載のコンピュータ可読記録媒体。
【請求項３６】
実行されると、前記1つまたは複数のプロセッサに、
クライアントデバイスから視覚探索デバイスのインターフェースを介して、圧縮されたクエリ特徴記述子として前記クエリ特徴記述子を受信させ、
視覚探索デバイスで、前記圧縮されたクエリ特徴記述子から前記クエリ特徴記述子を再構成させる
命令をさらに備える、請求項28に記載のコンピュータ可読記録媒体。
【請求項３７】
1つまたは複数のクライアントデバイスから受信した情報を受信するための入力装置であって、前記情報が視覚探索を開始するためのクエリ特徴記述子を備える入力装置と、
複数の参照クエリ記述子を示す情報を含むデータベースと、
前記視覚探索を実行するように構成された視覚探索サーバデバイスと
を備え、前記視覚探索サーバデバイスが、
前記クエリ特徴記述子を受信するためのインターフェースと、
前記クエリ特徴記述子と、前記複数の参照クエリ記述子のそれぞれとの間の距離を計算して、
クラスタリングアルゴリズムに従って、計算された距離のうちの1つまたは複数の第1のグループおよび計算された距離の第2のグループを決定して、計算された距離の前記第2のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照クエリ記述子のうちの関連する参照クエリ記述子が前記クエリ特徴記述子に近いこと示す前記計算された距離のグループを前記計算された距離の前記第1のグループが含み、前記計算された距離のうちの前記1つまたは複数の前記第1のグループ内にあると決定された前記計算された距離のグループと比較して、前記複数の参照クエリ記述子のうちの前記関連する参照クエリ記述子が前記クエリ特徴記述子から離れていることを示す前記計算された距離のグループを前記計算された距離の前記第2のグループが含み、
前記計算された距離の前記決定された第1のグループおよび前記計算された距離の前記第2のグループに基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの最小の距離に関連付けられる前記複数の参照クエリ記述子のうちの1つと一致するかどうかを決定するように構成された特徴マッチングユニットと
を備え
前記特徴マッチングユニットが、第1のグループ距離平均を生成するために、前記第1のグループ内にあると決定された前記計算された距離のうちの2つまたはそれ以上の平均を計算し、第2のグループ距離平均を生成するために、前記第2のグループ内にあると決定された前記計算された距離の平均を計算し、平均距離比測定値を生成するために、前記第2のグループ距離平均で前記第1のグループ距離平均を割り、前記平均距離比測定値としきい値とを比較し、前記比較に基づいて、前記クエリ特徴記述子が、前記計算された距離のうちの前記最小の距離に関連付けられる前記複数の参照特徴記述子のうちの前記1つと一致するかどうかを決定するようにさらに構成される、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は画像処理システムに関し、より詳細には、画像処理システムで視覚探索を実行することに関する。
【背景技術】
【０００２】
コンピューティングデバイスまたはコンピュータに関する視覚探索は、コンピュータまたは他のデバイスが、1つまたは複数の画像内の他のオブジェクトおよび/または特徴の中から、オブジェクトおよび/または特徴の探索を実行できるようにする技法を指す。視覚探索への最近の関心によって、コンピュータが、画像スケール、ノイズ、照明、および局所的な幾何学的歪みにおける変化を含む、様々な変化する画像状態における部分的に遮蔽されたオブジェクトおよび/または特徴を識別できるようにするアルゴリズムがもたらされた。この同じ時間の間に、カメラを特色とするモバイルデバイスが出現したが、そのようなモバイルデバイスは、テキストを入力するための、またはモバイルデバイスと接続するためのユーザインターフェースが限られている場合がある。モバイルデバイスおよびモバイルデバイスアプリケーションの開発者は、ユーザとモバイルデバイスとの対話を向上するためにモバイルデバイスのカメラを利用しようとしてきた。
【０００３】
1つの向上した点を説明すると、モバイルデバイスのユーザは、店頭で買い物中に、モバイルデバイスのカメラを利用して任意の所与の製品の画像を撮影できる。次いで、モバイルデバイスは、様々な参照画像についてアーカイブされた特徴記述子のセット内の視覚探索アルゴリズムを開始して、画像(「探索画像」と呼ばれうる)内に示された製品を、一致する参照画像に基づいて識別できる。製品を識別した後、モバイルデバイスはインターネット探索を開始して、近所の商店および/またはオンライン商店で入手できるその商品の最安値を含む、識別された製品についての情報を含むウェブページを提示できる。この方法で、ユーザはキーボード(ユーザが作用を及ぼす画像としてタッチスクリーン上に提示されるという点で、しばしば「仮想」キーボードである)または他の入力メカニズムを介してモバイルデバイスと接続しなければならないことを回避でき、単に探索画像を撮影して視覚探索および後続のウェブ探索を開始するだけでよい。
【０００４】
カメラ、および視覚探索へのアクセスを備えたモバイルデバイスが使用できる、いくつかのアプリケーションがあるが、スケール不変特徴変換(scale invariant feature transform, SIFT)アルゴリズムなどの視覚探索を実施するための視覚探索アルゴリズムは、特徴マッチングを実行する点で不十分な場合がある。特徴マッチングは、探索画像から抽出された探索特徴記述子が参照画像から抽出された参照特徴記述子と一致する、視覚探索アルゴリズムの態様を指す。
【０００５】
これらの欠陥を説明するために、SIFTアルゴリズムを考慮すると、探索特徴記述子および参照特徴記述子が、建物全体に繰り返される独特のアーチや窓などのそれぞれの探索画像および参照画像の反復特徴から抽出される場合、普通なら探索特徴記述子と一致するであろう参照特徴記述子を廃棄しうる。さらに、SIFTアルゴリズムは一般的に、任意の所与の視覚探索に応答して単一の画像だけを返し、この返された画像が、SIFTアルゴリズムによってアルゴリズム的に「ベストマッチ」と決定される。しかし、ユーザはSIFTアルゴリズムと同じ方法で「ベストマッチ」を構成するものを決定できず、単一のSIFTベストマッチ結果がユーザの期待とは一致しないことがあるので、ユーザの不満をもたらす場合がある。
【発明の概要】
【課題を解決するための手段】
【０００６】
一般的に、本開示は視覚探索を実行する際の特徴マッチングを容易にする技法を記述する。本技法は、探索結果のランク付けリストを提供できる特徴マッチングアルゴリズムを提供することによって、特徴マッチングを改善しうる。本技法は、反復特徴を含む特徴マッチングアルゴリズムを提供することによって堅牢性を改善しうる。たとえばSIFTアルゴリズムによって提供されるように、現在の探索特徴記述子と一致する2つ以上の参照特徴が相互に近くに配置されている場合(2つ以上の一致する参照特徴記述子が近すぎる場合、これらの一致する参照特徴記述子は一意である可能性が低く、したがって探索画像の分類を容易にする可能性は低いという前提の下で)、参照特徴記述子を拒否せず、本技法はクラスタリングアルゴリズムを利用して、特徴マッチングを実行する際に一意性をより正確に決定できる。さらに、本技法は、従来の視覚探索アルゴリズムにおいて一般的であるように単一の参照画像をただ返すのではなく、一致する参照画像のランク付けリストの生成およびリターンを容易にすることができる。一致する参照画像のランク付けリストは、ベストマッチを構成するもののアルゴリズムの決定を強制的に受容させるのではなく、ユーザが「ベストマッチ」と考えるものを選択する機会をユーザに提供できる。
【０００７】
一例では、視覚探索デバイスで視覚探索を実行するための方法が提供される。本方法は、視覚探索デバイスで、視覚探索クエリによって提供されたクエリ特徴記述子と、それぞれの複数の参照特徴記述子との間の距離を計算するステップであって、視覚探索クエリが視覚探索を開始するステップを備える。また、本方法は、視覚探索デバイスで、クラスタリングアルゴリズムに従って、計算された距離のうちの1つまたは複数の第1のグループおよび計算された距離の第2のグループを決定するステップであって、計算された距離の第1のグループが、計算された距離の第2のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子に近いことを示す計算された距離のグループを含み、計算された距離の第2のグループが、計算された距離の第1のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子から離れていることを示す計算された距離のグループを含むステップを備える。本方法は、計算された距離の決定された第1のグループおよび計算された距離の第2のグループに基づいて、クエリ特徴記述子が、計算された距離のうちの最小の距離に関連付けられる複数の参照特徴記述子のうちの1つと一致するかどうかを視覚探索デバイスで決定するステップをさらに備える。
【０００８】
他の例では、視覚探索を実行するための装置は、視覚探索クエリによって提供されたクエリ特徴記述子と、複数の参照特徴記述子のそれぞれとの間の距離を計算するための手段であって、視覚探索クエリが視覚探索を開始する手段を備える。また、本装置は、クラスタリングアルゴリズムに従って、計算された距離のうちの1つまたは複数の第1のグループおよび計算された距離の第2のグループを決定するための手段であって、計算された距離の第2のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子に近いことを示す計算された距離のグループを計算された距離の第1のグループが含み、計算された距離の第1のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子から離れていることを示す計算された距離のグループを計算された距離の第2のグループが含む手段を備える。本装置は、計算された距離の決定された第1のグループおよび計算された距離の第2のグループに基づいて、クエリ特徴記述子が、計算された距離のうちの最小の距離に関連付けられる複数の参照特徴記述子のうちの1つと一致するかどうかを決定するための手段をさらに備える。
【０００９】
他の例では、視覚探索を実行するための装置は、クエリ特徴記述子を受信するインターフェースおよび特徴マッチングユニットを備え、特徴マッチングユニットは視覚探索クエリによって提供されるクエリ特徴記述子と複数の参照特徴記述子のそれぞれとの間の距離を計算し、視覚探索クエリが視覚探索を開始して、クラスタリングアルゴリズムに従って、計算された距離のうちの1つまたは複数の第1のグループおよび計算された距離の第2のグループを決定し、計算された距離の第2のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子に近いこと示す計算された距離のグループを計算された距離の第1のグループが含み、計算された距離の第1のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子から離れていることを示す計算された距離のグループを計算された距離の第2のグループが含み、計算された距離の決定された第1のグループおよび計算された距離の第2のグループに基づいて、クエリ特徴記述子が、計算された距離のうちの最小の距離に関連付けられる複数の参照特徴記述子のうちの1つと一致するかどうかを決定する。
【００１０】
他の例では、実行されると、1つまたは複数のプロセッサに、視覚探索クエリによって提供されたクエリ特徴記述子と複数の参照特徴記述子のそれぞれとの間の距離を計算させて、視覚探索クエリが視覚探索を開始して、クラスタリングアルゴリズムに従って、計算された距離のうちの1つまたは複数の第1のグループおよび計算された距離の第2のグループを決定させて、計算された距離の第2のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子に近いこと示す計算された距離のグループを計算された距離の第1のグループが含み、計算された距離の第1のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子から離れていることを示す計算された距離のグループを計算された距離の第2のグループが含み、計算された距離の決定された第1のグループおよび計算された距離の第2のグループに基づいて、クエリ特徴記述子が、計算された距離のうちの最小の距離に関連付けられる複数の参照特徴記述子のうちの1つと一致するかどうかを決定させる命令を備える、コンピュータ可読記録媒体を備える。
【００１１】
他の例では、システムは、視覚探索を開始するために探索クエリによってクエリ特徴記述子を送信するクライアントデバイス、複数の参照クエリ記述子を格納するデータベース、および視覚探索を実行する視覚探索サーバデバイスを備える。視覚探索サーバデバイスは、探索クエリによってクエリ特徴記述子を受信するインターフェース、およびクエリ特徴記述子と複数の参照特徴記述子のそれぞれとの間の距離を計算する特徴マッチングユニットを備え、クラスタリングアルゴリズムに従って、計算された距離のうちの1つまたは複数の第1のグループ、および計算された距離の第2のグループを決定し、計算された距離の第2のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子に近いこと示す計算された距離のグループを計算された距離の第1のグループが含み、計算された距離の第1のグループ内にあると決定された計算された距離のグループと比較して、複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子から離れていることを示す計算された距離のグループを計算された距離の第2のグループが含み、計算された距離の決定された第1のグループおよび計算された距離の第2のグループに基づいて、クエリ特徴記述子が、計算された距離のうちの最小の距離に関連付けられる複数の参照特徴記述子のうちの1つと一致するかどうかを決定するインターフェースを備える。
【００１２】
1つまたは複数の例の詳細は、添付の図面および以下の記述において説明する。他の特徴、目的、および利点は、記述および図面、ならびに特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００１３】
【図１】本開示に記載の堅牢な特徴記述子マッチング技法を実施する画像処理システムを示すブロック図である。
【図２】図1の特徴マッチングユニットをより詳細に示すブロック図である。
【図３Ａ】本開示に記載の特徴マッチング技法を実施する際の視覚探索サーバの例示的動作を示す流れ図である。
【図３Ｂ】本開示に記載の特徴マッチング技法を実施する際の視覚探索サーバの例示的動作を示す流れ図である。
【図４】特徴抽出ユニットが、キーポイント抽出を実行する際に使用するためのガウス関数の差分(DoG)ピラミッドを決定する処理を示す図である。
【図５】ガウス関数の差分(DoG)ピラミッドを決定した後のキーポイントの検出を示す図である。
【図６】特徴抽出ユニットが、勾配分布と配向ヒストグラムを決定する処理を示す図である。
【図７】特徴抽出ユニットが、勾配分布と配向ヒストグラムを決定する処理を示す図である。
【発明を実施するための形態】
【００１４】
図1は、本開示に記載の堅牢な特徴マッチング技法を実施する画像処理システム10を示すブロック図である。図1の例では、画像処理システム10は、クライアントデバイス12、視覚探索サーバ14、およびネットワーク16を含む。この例では、クライアントデバイス12は、ラップトップ、いわゆるネットブック、携帯情報端末(PDA)、セルラー式またはモバイル電話あるいはハンドセット(いわゆる「スマートフォン」を含む)、グローバルポジショニングシステム(GPS)デバイス、デジタルカメラ、デジタルメディアプレイヤー、ゲーム機などのモバイルデバイス、もしくは、視覚探索サーバ14と通信できる他の何らかのモバイルデバイスを表す。本開示には視覚探索サーバ14に関連して記述されているが、本開示に記載の技法は視覚探索サーバに限定されない。むしろ、本技法は、局所特徴ベースの視覚探索アルゴリズムの特徴マッチングの態様を実装できる任意のデバイスによって実施されうる。
【００１５】
視覚探索サーバ14は、一般的に伝送制御プロトコル(TCP)接続の形式の接続を受け入れ、クエリデータを受信して識別データを提供するためのTCPセッションを形成するために独自のTCP接続で応答する、サーバデバイスを表す。視覚探索サーバ14は、視覚探索サーバ14が、1つまたは複数の参照画像内の1つまたは複数の特徴あるいはオブジェクトを識別するために、局所特徴ベースの視覚探索アルゴリズムを実行する、または実施するという点で視覚探索サーバデバイスを表してもよい。
【００１６】
ネットワーク16は、クライアントデバイス12と視覚探索サーバ14とを相互接続する、インターネットなどのパブリックネットワークを表すが、ネットワーク16はプライベートネットワークでもよい。一般に、ネットワーク16は、クライアントデバイス12と視覚探索サーバ14との間の通信またはデータの伝送を容易にするために、開放型システム間相互接続(OSI)モデルの様々なレイヤを実装する。ネットワーク16は、一般的に、クライアントデバイス12と視覚探索サーバ14との間のデータ伝送を可能にするために、スイッチ、ハブ、ルータ、サーバなどの、任意の数のネットワークデバイスを含む。単一のネットワークとして図示されているが、ネットワーク16は、ネットワーク16を形成するために相互接続された1つまたは複数のサブネットワークを備えうる。これらのサブネットワークは、ネットワーク16を通じてデータを転送するために提供される、サービスプロバイダネットワーク、アクセスネットワーク、バックエンドネットワーク、または一般的にパブリックネットワークで使用される他の任意のタイプのネットワークを備えうる。この例ではパブリックネットワークとして記述されているが、ネットワーク16は、一般的には公衆がアクセスできないプライベートネットワークを備えうる。
【００１７】
図1の例に示されるように、クライアントデバイス12は、特徴抽出ユニット18、特徴圧縮ユニット20、インターフェース22、およびディスプレイ24を含む。特徴抽出ユニット18は、スケール不変特徴変換アルゴリズム、または特徴の抽出を提供する他の任意の特徴記述抽出アルゴリズムなどの特徴抽出アルゴリズムに従って特徴抽出を実行するユニットを表す。一般的に、特徴抽出ユニット18は、クライアントデバイス12に含まれるカメラまたは他の画像撮影デバイス(図1の例には図示せず)を使用して局所に撮影されうる画像データ26を操作する。あるいは、クライアントデバイス12は、この画像データ26を、他のコンピューティングデバイスとの有線接続を介して局所に、あるいは他の任意の有線または無線形式の通信を介して、ネットワーク16からダウンロードすることによって、この画像データ自体を撮影せずに画像データ26を格納できる。
【００１８】
以下でより詳細に記述するが、特徴抽出ユニット18は、要約すると、ガウスぼかし(Gaussian blurring)画像データ26によって特徴記述子28を抽出して、2つの連続するガウスぼかし画像を生成する。ガウスぼかしは、一般的に、定義されたスケールでガウスぼかし関数で画像データ26を畳みこむことを含む。特徴抽出ユニット18は、画像データ26を段階的に畳み込むことができ、結果として得られたガウスぼかし画像は、スケール空間内の定数によって互いに分離される。特徴抽出ユニット18はこれらのガウスぼかし画像を積み重ねて、「ガウシアンピラミッド」または「ガウス関数の差分ピラミッド」と呼ばれうるものを形成できる。特徴抽出ユニット18は、2つの連続して積み重ねられたガウスぼかし画像を比較して、ガウス関数の差分(DoG)画像を生成する。DoG画像は「DoG空間」と呼ばれるものを形成しうる。
【００１９】
このDoG空間に基づいて、特徴抽出ユニット18はキーポイントを検出できる。キーポイントは、幾何学的な観点から潜在的に興味深い画像データ26内の特定のサンプルポイントまたは画素の周辺の画素の領域またはパッチを指す。一般に特徴抽出ユニット18は、キーポイントを、構築されたDoG空間内の局所極大および/または局所極小として識別する。次いで、特徴抽出ユニット18は、キーポイントが検出されたパッチへの局所画像勾配の方向に基づいて、これらのキーポイントに1つまたは複数の配向または方向を割り当てる。これらの配向を特徴づけるために、特徴抽出ユニット18は、勾配配向ヒストグラムの観点から配向を定義できる。次いで、特徴抽出ユニット18は、位置および配向として(たとえば、勾配配向ヒストグラムによって)特徴記述子28を定義する。特徴記述子28を定義した後、特徴抽出ユニット18は、この特徴記述子28を特徴圧縮ユニット20に出力する。一般的に、特徴抽出ユニット18は、この処理を使用して特徴記述子28のセットを特徴圧縮ユニット20に出力する。
【００２０】
特徴圧縮ユニット20は、特徴記述子28などの特徴記述子を定義するために使用されるデータの量を、これらの特徴記述子を定義するために特徴抽出ユニット18によって使用されるデータの量と比較して、圧縮するか減少させるユニットを表す。特徴記述子28を圧縮するために、特徴圧縮ユニット20は、タイプ量子化と呼ばれる量子化の形態を実行できる。この点において、特徴記述子28によって定義されたヒストグラムを全体として送信するのではなく、特徴圧縮ユニット20はいわゆる「タイプ」としてヒストグラムを表すためにタイプ量子化を実行する。一般に、タイプはヒストグラムの圧縮された表現である(たとえば、タイプはヒストグラム全体ではなくヒストグラムの形を表す)。タイプは、一般的にシンボルの周波数のセットを表し、ヒストグラムとの関連では、ヒストグラムの勾配分布の周波数を表しうる。言い換えれば、タイプは特徴記述子28のうちの対応する特徴記述子を生成したソースの真の分布の推定を表しうる。この点において、タイプの符号化および送信は、特定のサンプル(すなわち、この例では、特徴記述子28のうちの対応する特徴記述子によって定義されたヒストグラム)に基づいて推定されうる分布の形の符号化および送信と等しいと考えられうる。
【００２１】
特徴記述子28および量子化のレベル(本明細書では「n」として数学的に示すことができる)を考えると、特徴圧縮ユニット20は、特徴記述子28ごとにパラメータkl,…,km(mは次元の数を示す)を有するタイプを計算する。各タイプは、所与の公分母を有する有理数の集合を表すことができ、有理数の合計は1になる。次いで、特徴記述子28が、辞書式列挙(lexicographic enumeration)を使用して、このタイプをインデックスとして符号化できる。言い換えれば、所与の公分母を有する全ての可能なタイプに関して、特徴圧縮ユニット20は、これらのタイプの辞書式順序に基づいてこれらのそれぞれのタイプにインデックスを効果的に割り当てる。それによって、特徴圧縮ユニット20は、特徴記述子28を単一の辞書式に構成されたインデックスに圧縮して、これらの圧縮された特徴記述子をクエリデータ30の形式でインターフェース22に出力する。
【００２２】
インターフェース22は、無線インターフェースおよび有線インターフェースを含めた、ネットワーク16を介して視覚探索サーバ14と通信できる任意のタイプのインターフェースを表す。インターフェース22は無線セルラー式インターフェースを表し、無線セルラー式ネットワークを介してネットワーク16と、およびネットワーク16を介して視覚探索サーバ14と通信するために必要なハードウェア、またはアンテナ、モジュレータ、および同等物などの他のコンポーネントを含むことができる。この例では、図1の例には示されていないが、ネットワーク16は、無線セルラー式インターフェース22がネットワーク16と通信する無線セルラー式アクセスネットワークを含む。ディスプレイ24は、画像データ26、または他の任意のタイプのデータなどの画像を表示できる、任意のタイプのディスプレイユニットを表す。ディスプレイ24は、たとえば、発光ダイオード(LED)ディスプレイデバイス、有機LED(OLED)ディスプレイデバイス、液晶ディスプレイ(LCD)デバイス、プラズマディスプレイデバイス、または他の任意のタイプのディスプレイデバイスを表すことができる。
【００２３】
視覚探索サーバ14は、インターフェース32、特徴再構成ユニット34、特徴マッチングユニット36、および特徴記述子データベース38を含む。視覚探索サーバ14のインターフェース32は、インターフェース32がネットワーク16などのネットワークと通信できる任意のタイプのインターフェースを表すことができるという点で、クライアントデバイス12のインターフェース22と類似している場合がある。特徴再構成ユニット34は、圧縮された特徴記述子を解凍して、圧縮された特徴記述子から特徴記述子を再構成するユニットを表す。特徴再構成ユニット34は、特徴再構成ユニット34が量子化の逆(しばしば再構成と呼ばれる)を実行して、圧縮された特徴記述子から特徴記述子を再構成するという点で、特徴圧縮ユニット20によって実行される動作の、逆の動作を実行できる。
【００２４】
特徴マッチングユニット36は、再構成された特徴記述子に基づいて画像データ26内の1つまたは複数の特徴あるいはオブジェクトを識別するために特徴マッチングを実行するユニットを表す。特徴マッチングユニット36は、この特徴識別を実行するために特徴記述子データベース38にアクセスできる。特徴記述子データベース38は特徴記述子を定義して、これらの特徴記述子のうちの少なくともいくつかを、画像データ26から抽出された対応する特徴またはオブジェクトを含む参照画像と関連付けるデータを格納する。これらの参照画像は、参照画像の1つまたは複数のサブジェクト、特徴、またはオブジェクトを識別する識別データにも関連付けることができる。データベース38は、圧縮されたk次元木(KD tree)を使用してこのデータを格納できる。
【００２５】
再構成された特徴記述子40(このデータが、視覚探索またはクエリを実行するために使用される視覚探索クエリデータを表すという点で、本明細書では「クエリデータ40」とも呼ばれうる)などの、再構成された特徴記述子に基づいて画像データ26から抽出された特徴またはオブジェクトの識別が成功すると、特徴マッチングユニット36は1つまたは複数のマッチング参照画像および任意の関連する識別データをクエリ結果データ42として返す。
【００２６】
初めに、クライアントデバイス12のユーザがクライアントデバイス12と対話して、視覚探索を開始する。ユーザは、クエリ画像データ26を選択するために、ユーザインターフェース、またはディスプレイ24によって提示された他のタイプのインターフェースと対話して、次いでクエリ画像データ26として格納された画像の焦点である1つまたは複数の特徴あるいはオブジェクトを識別するために視覚探索を開始する。たとえば、クエリ画像データ26は、ピサの斜塔などのランドマークの画像を指定できる。ユーザは、クライアントデバイス12の画像撮影ユニット(たとえば、カメラ)を使用してこの画像を撮影してもよく、ネットワーク16から、または他のコンピューティングデバイスとの有線または無線通信を介して局所に、この画像をダウンロードしてもよい。いずれにしても、クエリ画像データ26を選択した後、この例では、ユーザがランドマークを識別するために視覚探索を開始する。
【００２７】
視覚探索の開始に応答して、クライアントデバイス12が、特徴抽出ユニット18を起動して、少なくとも1つの特徴記述子28と、一般的にクエリ画像データ26の分析を通じて見つかったいわゆる「キーポイント」のうちの1つを記述するいくつかの特徴記述子28とを抽出する。特徴抽出ユニット18がこのクエリ特徴記述子28を特徴圧縮ユニット20に転送し、特徴圧縮ユニット20がクエリ特徴記述子28の圧縮およびクエリデータ30の生成に進む。特徴圧縮ユニット20がクエリデータ30をインターフェース22に出力し、インターフェース22が、ネットワーク16を介してクエリデータ30を視覚探索サーバ14に転送する。
【００２８】
視覚探索サーバ14のインターフェース32がクエリデータ30を受信する。クエリデータ30の受信に応答して、視覚探索サーバ14が特徴再構成ユニット34を起動する。特徴再構成ユニット34がクエリデータ30に基づいてクエリ特徴記述子28を再構成して、再構成されたクエリ特徴記述子40を出力する。特徴マッチングユニット36が再構成されたクエリ特徴記述子40を受信して、クエリ特徴記述子40に基づいて特徴マッチングを実行する。特徴マッチングユニット36が、特徴記述子データベース38にアクセスして、特徴記述子データベース38によってデータとして格納された参照特徴記述子を横切る(traverse)ことによって、クエリ特徴記述子40ごとに特徴マッチングを実行して、実質的に一致する特徴記述子を識別する。再構成されたクエリ特徴記述子40に基づく、画像データ26から抽出された特徴の識別が成功すると、特徴マッチングユニット36が、一致する参照特徴記述子あるいは任意の関連する識別データに関連付けられる1つまたは複数の一致する参照画像をクエリ結果データ42として出力する。インターフェース32がこのクエリ結果データ42を受信して、ネットワーク16を介してクライアントデバイス12にクエリ結果データ42を転送する。
【００２９】
クライアントデバイス12のインターフェース22がこのクエリ結果データ42を受信して、一般的にこのクエリ結果データ42を、探索クエリを起動した何らかのアプリケーションに転送する。すなわち、クライアントデバイス12は通常、視覚探索を起動でき、かつクエリ結果データ42などの返されたクエリ結果データの提示を管理できる1つまたは複数のアプリケーションを実行する。このアプリケーションは、ディスプレイ24と接続して、クエリ結果データ42を提示できる。いくつかの例では、アプリケーションは、クエリ結果データ42を増強するために、インターネット探索または他の動作を実行して、クエリ結果データ42によって定義された識別データに基づいてさらなる情報を取り出すことができる。この例では、クエリ結果データ42の識別データはランドマークの名称、すなわちこの例ではピサの斜塔、ピサの斜塔を建築した建築者の名前、ピサの斜塔の完成データ、およびこのランドマークに関連する他の任意の情報を備えうる。
【００３０】
視覚探索は、より小さいスクリーンおよび/または限られた入力メカニズム(触覚フィードバックをほとんど提供せず、ユーザによるテキストの入力を制限するか妨げうる仮想キーボードなど)を有するユーザとクライアントデバイスとの対話を容易にして、一般的に様々なアプリケーションを容易にするという点でいくつかの利点を提供することができるが、いくつかの例では、スケール不変特徴変換(SIFT)アルゴリズムなどのいくつかの視覚探索アリゴリズムは特徴マッチングを実行するという点では不十分な場合がある。これらの欠点を説明すると、SIFTアルゴリズムは、クエリ特徴記述子および参照特徴記述子が、建物(たとえば、ピサの斜塔)全体に繰り返される独特のアーチや窓などのそれぞれの探索画像および参照画像の反復特徴から抽出される場合、普通なら探索特徴記述子またはクエリ特徴記述子と一致するであろう参照特徴記述子を廃棄しうる。さらに、SIFTアルゴリズムは、一般的に任意の所与の視覚探索に応答して単一の画像だけを返し、この返された画像が、SIFTアルゴリズムによってアルゴリズム的に「ベストマッチ」と決定される。しかし、ユーザはSIFTアルゴリズムと同じ方法で「ベストマッチ」を構成するものを決定できず、単一のSIFTベストマッチ結果がユーザの期待とは一致しないことがあるので、ユーザの不満をもたらす場合がある。
【００３１】
より具体的には、SIFTアルゴリズムを含めた視覚探索アルゴリズムは、「類似性測定」と呼ばれうるものを使用して特徴マッチングを実施する。SIFTアルゴリズムは、距離比テストを使用して、クエリ特徴記述子がそれぞれの参照特徴記述子にどのくらい類似しているかを測定する。この距離比は、クエリ特徴記述子のうちの現在のクエリ特徴記述子に最も近い参照特徴記述子が、クエリ特徴記述子のうちの現在のクエリ特徴記述子に2番目に近い(やはり、特徴記述子空間において)特徴記述子とどのくらい離れているか(特徴記述子空間において)を測定する。最も近い参照特徴記述子と2番目に近い参照特徴記述子とが非常に近い場合(しきい値によって識別される)、SIFTアルゴリズムは、クエリ特徴記述子のうちの現在のクエリ特徴記述子は一意ではなく、したがって一致の信頼性が低いと判断する。この距離比類似性測定は、以下の式(1)によって表すことができる。
【００３２】
【数１】
0005749394.tif 000002
【００３３】
式(1)において、qはクエリ記述子を表し、nn1はデータベース内の最も近い参照特徴記述子(「最も近い近隣(nearest neighbor)」すなわち「nn」とも呼ばれうる)を表し、nn2はデータベース内の2番目に近い参照特徴記述子(「2番目に近い近隣(second nearest neighbor)」と呼ばれうる)を表し、dはL2ノルム演算を表し、Tはしきい値を表す。
【００３４】
SIFT距離比類似性測定は一般的に適切な結果を提供するが、特定の例では、SIFT距離比類似性測定は一致する参照特徴記述子を正確に識別できない場合がある。たとえば、画像が反復構造(図7の例に示されるピサの斜塔の反復する窓の構造など)を含む例では、2つの最も近い参照特徴記述子(やはり、ピサの斜塔を示す画像データから抽出された)間の距離が小さい場合があることを考慮すると、SIFT距離比類似性測定は、このような反復画像特徴から抽出されたクエリ特徴記述子は一意ではないと決定しうる。この例では、SIFT距離比類似性測定は、潜在的に正確な一致を拒否しうる。
【００３５】
本開示に記載の技法によると、視覚探索サーバ14の特徴マッチングユニット36は、反復構造に適応することができ、もしくはこれらおよび他の例においてより正確なマッチングを容易にすることができる、より堅牢な距離比類似性測定を使用する。さらに、本技法は、従来のシステムでは一般的なように、単に単一の「ベストマッチ」する参照画像を返すのではなく、「ベストマッチ」のアルゴリズムの決定とユーザの知覚との違いに対応するために、参照画像の順序付けられたランク付けを提供することができる。
【００３６】
本開示に記載の技法による距離比類似性測定の実施において、特徴マッチングユニット36は、まず再構成されたクエリ特徴記述子40のうちの1つと、特徴記述子データベース38に格納されたそれぞれの複数の参照特徴記述子との間の距離を計算できる。次いで、特徴マッチングユニット36は、クラスタリングアルゴリズムを使用して、計算された距離のうちの1つまたは複数の第1のグループ、および計算された距離の第2のグループを決定できる。共通のクラスタリングアルゴリズムは、k平均法クラスタリングアルゴリズム(この例では、第1および第2のグループを生成するためにkが2に設定される)、ガウシアンフィッティングアルゴリズム、およびグラフカッティングアルゴリズムを備えうる。
【００３７】
いくつかの例では、クラスタリングアルゴリズムは、最も近い、または最も小さい距離を第1のグループに、および次に近いまたは小さい複数の距離を第2のグループにクラスタリングするアルゴリズムを備えることができる。第2のグループの、次に近いまたは小さい複数の距離の数は、たとえば、次に近い距離のうちの2つ、3つ、または4つを含みうる。本明細書では、k平均法クラスタリングアルゴリズムなどのより正式なクラスタリングアルゴリズムに関して記述しているが、本開示に記載の技法に関連して、第1のグループが1つまたは複数の距離を含み第2のグループが2つ以上の距離を含む2つ以上のグループを決定できる任意のアルゴリズムを利用できる。
【００３８】
クラスタリングアルゴリズムを使用して、特徴マッチングユニット36は、計算された距離のうちの1つまたは複数の第1のグループを決定して、この第1のグループが、計算された距離の第2のグループ内にあると決定された計算された距離と比較して、特徴記述子データベース38に格納された複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子に近いことを示す、計算された距離を含むようにすることができる。やはりこのクラスタリングアルゴリズムを使用して、特徴マッチングユニット36は、計算された距離の第2のグループを決定して、この第2のグループが、計算された距離の第1のグループ内にあると決定された計算された距離と比較して、特徴記述子データベース38に格納された複数の参照特徴記述子のうちの関連する参照特徴記述子がクエリ特徴記述子40のうちの現在のクエリ特徴記述子から離れていることを示す、計算された距離を含むようにすることができる。
【００３９】
次いで、視覚探索サーバ14の特徴マッチングユニット36が、計算された距離の決定された第1のグループおよび計算された距離の第2のグループに基づいて、クエリ特徴記述子40のうちの現在のクエリ特徴記述子が、計算された距離のうちの最小の距離に関連付けられる複数の参照特徴記述子のうちの1つと一致するかどうかを決定できる。たとえば、特徴マッチングユニット36は、第1のグループ距離平均を生成するために、第1のグループ内にあると決定された計算された距離の平均をまず計算して、同様に、第2のグループ距離平均を生成するために、第2のグループ内にあると決定された計算された距離の平均を計算できる。第1のグループ距離平均および第2のグループ距離平均を計算すると、特徴マッチングユニット36は、第2のグループ距離平均によって第1のグループ距離平均を割って、平均距離比測定値を生成できる。次に、特徴マッチングユニット36は、平均距離比測定値としきい値とを比較して、その比較に基づいて、クエリ特徴記述子40のうちの現在のクエリ特徴記述子が、計算された距離のうちの最小の距離に関連付けられる複数の参照特徴記述子のうちの1つと一致するかどうかを決定できる。
【００４０】
計算された距離をこの方法でクラスタリングまたはグループ化し、次いでそれぞれのグループの距離を平均化することによって、本技法は、従来一般的であるように、相互に近くにあり、両方ともクエリ特徴記述子に一致する、任意の参照特徴記述子を完全に拒否せずに、隣接する反復特徴から抽出された特徴記述子のマッチングに対応できる。クラスタリングアルゴリズムを使用して距離測定をグループ化することは、近い特徴記述子と遠い特徴記述子との間のより明確な区別も実現し、視覚探索サーバ14の特徴マッチングユニット36が、距離を使用して、異なるまたは一意の特徴記述子を相互に正確に識別できるようになる。距離測定を平均化することによって、特徴マッチングユニット36は、しきい値を正確に適用するために、これらの2つのグループが相互にどれだけ離れているかについての比較的近い近似値を提供でき、それによって、一致する参照特徴記述子と考えられるものを拒否することを回避できるようになる。
【００４１】
本技法の、一致する画像態様の、順序付けられた、またはランク付けされたリストを実装するために、視覚探索サーバ14の特徴マッチングユニット36は、計算された距離の第2のグループと比較して、クエリ特徴記述子40のうちの現在のクエリ特徴記述子に比較的近い、計算された距離の第1のグループを利用する。第1のグループ内にあると決定されて、上述のより堅牢な距離類似性測定を使用して一致すると決定された全ての計算された距離について、特徴マッチングユニット36は、第1のグループの計算された距離に対応する、一致する参照特徴記述子に関連付けられる異なる画像に評価(vote)を割り当てることができる。すなわち、第1のグループの計算された距離に対応する参照特徴記述子のうちの複数の参照特徴記述子が同じ参照画像から抽出されると、特徴マッチングユニット36はその参照画像に単一の評価を割り当てる。
【００４２】
たとえば、特徴マッチングユニット36は、参照画像のグループがどのような重複する参照画像も含まないような一意の参照画像のグループを決定することができる。特徴マッチングユニット36は、第1のグループ内にあると決定される計算された距離が計算される参照特徴記述子を第1に考慮することができる。これらの参照特徴記述子は「第1のグループ参照特徴記述子」と呼ばれうる。それぞれの参照特徴記述子は、特徴記述子データベース38を最初に構築する際にその参照特徴記述子が抽出された参照画像(やはり特徴記述子データベース38、あるいは図1の例には示されていない他の何らかのデータベース、メモリ、またはストレージユニットに格納されうる)に関連付けられる。次いで、特徴マッチングユニット36は、参照画像の最初のグループを、第1のグループ参照特徴記述子に関連付けられる参照画像と決定できる。次いで、特徴マッチングユニット36は、参照画像のグループがどのような重複する参照画像も含まないように、参照画像の最初のグループからあらゆる重複する参照画像を削除して、一意の参照画像のグループを生成できる。
【００４３】
次いで、特徴マッチングユニット36は、一意の参照画像のグループ内にあると決定されたそれぞれの参照画像に評価を割り当てることができる。評価は、1などの定数でよい。あるいは、評価は、クエリ特徴記述子40のうちの現在のクエリ特徴記述子と、最も近い参照特徴記述子との間の計算された距離と比較して、現在の計算された距離の距離比に比例してよい。代替として、評価は、第1のグループの計算された距離が最小から最大へ順序付けられる場合、第1のグループ内のランク付けに比例してよい(たとえば第1のグループの参照特徴記述子のうちのある参照特徴記述子が、クエリ特徴記述子40のうちの現在のクエリ特徴記述子に5番目に近い場合、評価は1/5である)。次いで、特徴マッチングユニット36は、この方法でクエリ特徴記述子40ごとに評価を割り当てる。この方法で評価が参照画像またはターゲット画像に割り当てられた後、特徴マッチングユニット36は、収集された評価に基づいて参照画像またはターゲット画像をランク付けして、クエリデータ30に応答して、クエリ結果データ42の形式でターゲット画像のランク付けまたは順序付けされたリストを提供できる。
【００４４】
本開示において、開示された技法を実行するように構成されたデバイスの機能面を強調するために、様々なコンポーネント、モジュール、またはユニットを記述したが、これらのユニットは必ずしも異なるハードウェアユニットによって実現する必要はない。むしろ、コンピュータ可読記録媒体に格納された適切なソフトウェアおよび/またはファームウェアと併せて、上述のように1つまたは複数のプロセッサを含めて、様々なユニットがハードウェアユニットに結合されてもよく、相互作用するハードウェアユニットの集合によって提供されてもよい。この点で、本開示におけるユニットへの参照は、別々のハードウェアユニット、ならびに/またはハードウェアおよびソフトウェアユニットとして実装される、あるいは実装されない、異なる機能的ユニットを提案することを意図する。本明細書で使用される「コンピュータ可読記録媒体」という語句は製品のみに適用され、一時的な伝搬信号には適用されない点に留意されたい。
【００４５】
図2は、図1の例に示される特徴マッチングユニット36をより詳細に示すブロック図である。図2の例では、特徴マッチングユニット36は、距離計算ユニット50、グループ化ユニット52、マッチングユニット54、および結果生成ユニット56を含む。距離計算ユニット50は、特徴記述子データベース38に格納された参照特徴記述子51およびクエリ特徴記述子40に基づいて距離62A〜62N(「距離62」)を計算するユニットを表す。より具体的には、距離計算ユニット50は、クエリ特徴記述子40のうちの現在のクエリ特徴記述子からそれぞれの参照特徴記述子51を減算した絶対値として、クエリ特徴記述子40ごとに距離62を計算するユニットを表しうる。距離計算ユニット50は、距離62をグループ化ユニット52に出力する。
【００４６】
グループ化ユニット52は、距離62などの距離、または2つ以上の値の他の任意の空でないセットを受信して、これらの値をクラスタリングアルゴリズム64に従って少なくとも2つのグループにグループ化するユニットを表す。クラスタリングアルゴリズム64は、1つまたは複数のk平均法クラスタリングアルゴリズム(この例では、第1および第2のグループを生成するためにkが2に設定される)、ガウシアンフィッティングアルゴリズム、およびグラフカッティングアルゴリズム、ならびに値のセットから少なくとも2つのグループを生成できる他の任意の一般的なクラスタリングアルゴリズムを表しうる。図2の例では、グループ化ユニット52が距離62を受信して、クラスタリングアルゴリズム64に従って距離62の異なる距離のグループ66A、66B(「グループ66」)を計算する。グループ化ユニット52は、計算された距離62のうちの2つ以上を含むグループ66Aを決定することができ、この第1のグループ66Aが、参照記述子データベース38に格納された参照特徴記述子51のうちの関連する参照特徴記述子が、計算された距離62のグループ66B内にあると決定された計算された距離62と比較して、クエリ特徴記述子40のうちの現在のクエリ特徴記述子に近いことを示す計算された距離62を含むようにすることができる。やはりクラスタリングアルゴリズム64に従って、グループ化ユニット52は、計算された距離62のグループ66Bを決定することができ、この第2のグループ66Bが、参照特徴記述子51のうちの関連する参照特徴記述子が、計算された距離の第1のグループ内にあると決定された計算された距離62と比較して、クエリ特徴記述子40のうちの現在のクエリ特徴記述子から離れていることを示す計算された距離62を含むようにすることができる。グループ化ユニット52は、距離62のグループ66をマッチングユニット54に出力する。
【００４７】
マッチングユニット54は、クエリ特徴記述子40のうちの現在のクエリ特徴記述子が、参照特徴記述子51のうちの1つまたは複数と一意に一致するかどうかを決定するユニットを表す。クエリ特徴記述子40のうちの現在のクエリ特徴記述子が、参照特徴記述子51のうちの1つまたは複数と一意に一致するかどうかを決定するために、マッチングユニット54は一般にそれぞれの提供されたグループの値の平均を計算する。図2の例では、マッチングユニット54が、グループ66Aの距離62とグループ66Bの距離62とをそれぞれ平均化することによって、グループ平均68A、68Bを計算する。次に、マッチングユニット54が、グループ平均68Bによってグループ平均68Aを割って、その結果をしきい値70と比較する。すなわち、マッチングユニット54は一般的に、クラスタリングアルゴリズム64を使用して形成された距離62のグループ66から計算されたグループ平均のみに関連して、SIFTアルゴリズム(および上記で式(1)として示されているもの)によって現在実行されているものに類似する比較を実行する。
【００４８】
グループ平均68Bによってグループ平均68Aを割った結果がしきい値を上回る場合(グループ66Bに関連付けられる参照特徴記述子51が、グループ66Aに関連付けられる参照特徴記述子51に近いことを意味する)、マッチングユニット54が、クエリ特徴記述子40のうちの現在のクエリ特徴記述子がどの参照特徴記述子51とも一意に一致しないことを示す一致インジケータ72を出力する。本明細書では、「一意の一致」という用語は、一致が存在しうるが、クエリ画像データの識別を容易にしない場合があり、したがって一致が一意とは考えられない視覚探索を実行する状況における、特徴マッチングの側面を指すために使用される。一致がクエリ画像データの識別を容易にする場合、一致は一意である。たとえば、ピサの斜塔のクエリ画像から、このランドマークを一意に識別しうるクエリ特徴記述子としてピサの斜塔のアーチが抽出されうる。ピサの斜塔の参照画像内のこれらのアーチから抽出された参照特徴記述子が一致しうる。これらのアーチの反復特徴および一意性の狭義を考慮する従来のSIFTアルゴリズムでは一般的であったように、これらの一致する参照画像特徴記述子を拒否するのではなく、マッチングユニット54は、マッチングユニット54が動作するデータのクラスタリング性質による反復に関わらず、これらの一意な一致を適切に決定できる。この一意の一致は、上述の類似性測定とも呼ばれうる。一意の一致は、クエリ画像データの識別を一意でない一致よりも迅速に容易にするので好まれ、これが、マッチングユニット54が一意でない一致を拒否する理由である。
【００４９】
いずれにしても、グループ平均68Bによってグループ平均68Aを割った結果がしきい値を下回る場合(グループ66Bに関連付けられる参照特徴記述子51が、グループ66Aに関連付けられる参照特徴記述子51から離れていることを意味する)、マッチングユニット54が、クエリ特徴記述子40のうちの現在のクエリ特徴記述子が、距離62のうちの最小の距離に関連付けられる参照特徴記述子51のうちの1つと一意に一致することを示す一致インジケータ72を出力する。マッチングユニット54はこの一致インジケータ72を出力して、グループ66Aを結果生成ユニット56に転送する。いくつかの例では、マッチングユニット54は、一致インジケータ72が一致を示す場合のみグループ66Aを転送するので、マッチングユニット54が一致は存在しないと決定した場合、結果生成ユニット56はグループ66Aを考慮する必要がない。
【００５０】
結果生成ユニット56は、クエリ結果データ42を生成するユニットを表す。結果生成ユニット56は、リスト形成ユニット58および評価割当てユニット60を含む。リスト形成ユニット58は、グループ66Aに基づいて一意の参照画像リスト74を形成するユニットを表す。より具体的には、リスト形成ユニット58は、一致インジケータ72が一致を信号で伝える場合、グループ66Aの距離62が計算された参照特徴記述子51を決定するためにグループ66Aを処理できる。次いで、リスト形成ユニット58は、これらのそれぞれの参照特徴記述子51が抽出された参照画像53を取り出し、最初の参照画像リスト76を形成する。次いで、リスト形成ユニット58は、最初の参照画像リスト76から任意の冗長画像を除去して、一意の参照画像リスト74を生成できる。
【００５１】
最初の参照画像リスト76を形成するものとして記述したが、リスト形成ユニット58はこのようなリスト76を必ずしも形成しなくてよいが、代わりに参照画像53のうちの一意の参照画像だけを取り出しうる。すなわち、リスト形成ユニット58は、参照特徴記述子51のうちの決定された参照特徴記述子が抽出された参照画像53を取り出す際に、画像53のうちのこの画像をすでに取り出したかどうかを最初に決定して、画像53のうちのこの画像をすでに取り出していない場合、画像53のうちのこの画像を取り出すことができる。画像53のコピーまたは複製を格納することを回避することによって、リスト形成ユニット58はメモリの消費を回避でき、実装者がメモリ要件を減らすことを可能にすることができる。この理由から、本技法は、一意の参照画像リスト74を計算するどの方法にも限定されるべきではない。このように、リスト形成ユニット58が一意の参照画像リスト74を計算する方法に関わらず、リスト形成ユニット58は、一意の参照画像リスト74を評価割当てユニット60に出力する。
【００５２】
評価割当てユニット60は、評価を参照画像53のうちの1つまたは複数に割り当てるユニットを表す。一般的に、評価割当てユニット60は、それぞれの画像53を評価集計表78内のエントリに関連付けることによって、一意の参照画像リスト74によって識別されたこれらの画像53に評価を割り当てる。評価割当てユニット60は、画像53に関連付けられるそれぞれのエントリを更新して、それぞれの評価カウントをインクリメントできる。評価割当てユニット60は、上述の方法を含む任意の数の方法で評価を決定できる。すなわち、評価は1などの定数でよい。あるいは、評価は、クエリ特徴記述子40のうちの現在のクエリ特徴記述子と、最も近い参照特徴記述子との間の計算された距離と比較して、現在の計算された距離の距離比に比例してよい。代替として、評価は、第1のグループの計算された距離が最小から最大へ順序付けられる場合、第1のグループ内のランク付けに比例してよい(たとえば第1のグループの参照特徴記述子のうちのある参照特徴記述子が、クエリ特徴記述子40のうちの現在のクエリ特徴記述子に5番目に近い場合、評価は1/5である)。
【００５３】
距離計算ユニット50、グループ化ユニット52、マッチングユニット54、および結果生成ユニット56は、全てのクエリ特徴記述子40がこの特徴マッチング処理を経るまで上述の方法で継続できる。クエリ特徴記述子40のうちの最後のクエリ特徴記述子を処理した後、結果生成ユニット56が、評価集計表78に基づいてクエリ結果データ42を構成する。たとえば、結果生成ユニット56は、何らかの限界またはしきい値まで、最も多い評価、2番目に多い評価、3番目に多い評価等を受け取った参照画像53を取り出して、これらの画像53をクエリ結果データ42として(メタデータ、または、特徴記述子データベース38内のこれらのそれぞれの画像を記述するかそれに関連付けられる他のデータとともに)出力することができる。あるいは、結果生成ユニット56は、評価を受け取った画像53としてクエリ結果データ42を形成できる(やはり、メタデータ、または、特徴記述子データベース38内のこれらのそれぞれの画像を記述するかそれに関連付けられる他のデータとともに)。
【００５４】
図3は、本開示に記載の特徴マッチング技法を実施する際の、図1の例に示される視覚探索サーバ14などの視覚探索サーバの例示的動作を示す流れ図である。初めに、視覚探索サーバ14が、インターフェース32を介して、一般的に圧縮された特徴記述子を定義するクエリデータ30を受信する(90)。視覚探索サーバ14の特徴再構成ユニット34が、クエリデータ30によって定義された、圧縮された特徴記述子からクエリ特徴記述子28を再構成して、再構成されたクエリ特徴記述子40を生成する(92)。特徴再構成ユニット34が、再構成されたクエリ特徴記述子40を特徴マッチングユニット36に出力する。
【００５５】
特徴マッチングユニット36が、距離計算ユニット50とともにこれらのクエリ特徴記述子40を受信する(図2の例に示されるように)。距離計算ユニット50が、クエリ特徴記述子40のうちの1つを選択する(94)。次いで、距離計算ユニット50が、上述の方法で、クエリ特徴記述子40のうちの選択されたクエリ特徴記述子と、特徴記述子データベース38に格納された参照特徴記述子51のうちの1つまたは複数との間の距離を計算する(96)。これらの距離は、距離62として図2の例に示されている。距離計算ユニット50が、これらの距離62をグループ化ユニット52に出力する。
【００５６】
これらの距離62を受信すると、グループ化ユニット52が、クラスタリングアルゴリズム64に従って、計算された距離62の第1のグループ66Aおよび第2のグループ66Bを決定する(98)。第1のグループ66Aは、第2のグループ66Bの距離62の非ゼロのセットとは異なる、距離62の非ゼロのセットを含む。すなわち、距離62は、距離62のうちのいずれもグループ66の両方に関連付けられないように、第1および第2のグループ66に分割される。グループ化ユニット52が、グループ66をマッチングユニット54に出力する。
【００５７】
グループ66の受信に応答して、マッチングユニット54は、第1のグループ距離66Aの平均と、第2のグループ距離66Bの平均とを計算する(100)。これらの平均はグループ平均68Aおよびグループ平均68Bとして図2の例に示されており、グループ平均68Aは、グループ66Aの距離62の計算された平均を表し、グループ平均68Bは、グループ66Bの距離62の計算された平均を表す。次いで、マッチングユニット54が、グループ平均68Bによってグループ平均68Aを割って、割った結果がしきい値70を下回るかどうかを決定するために割り算の結果としきい値70とを比較する(102〜106)。結果がしきい値70を下回る場合(「はい」106)、マッチングユニット54が、クエリ特徴記述子40のうちの選択されたクエリ特徴記述子が、参照特徴記述子51のうちの決定された最も近い参照特徴記述子と一致する(距離62の点で)ことを識別する一致インジケータ72を生成する(108)。マッチングユニット54が、一致インジケータ72と第1のグループ66Aとを結果生成ユニット56に転送する。
【００５８】
結果生成ユニット56が、一致インジケータ72とグループ66Aとを受信する。一致インジケータ72とグループ66Aとの受信に応答して、結果生成ユニット56がリスト形成ユニット58を起動する。リスト形成ユニット58が、まず距離62のグループ66Aに関連付けられる参照特徴記述子51を上述の方法で識別することによって、最初の参照画像リスト76を生成する(110)。次に、リスト形成ユニット58が、やはり上述の方法で、参照特徴記述子51の内の識別された参照特徴記述子に関連付けられる参照画像53を識別する(112)。リスト形成ユニット58は、識別された参照画像53を最初の参照画像リスト76として格納できる。やはり上述のように、次いでリスト形成ユニット58が、識別された参照特徴記述子51(または最初の参照画像リスト76)に基づいて一意の参照画像53のリストを生成する。このリストは図2の例に一意の参照画像リスト74として示されている(114)。次に、結果生成ユニット56が、評価割当てユニット60を起動して、評価割当てユニット60が、上述の方法で、一意の参照画像53のリスト(または、一意の参照画像リスト74)に評価を割り当てることができる(116)。評価割当てユニット60は、一意の参照画像リスト74によって識別された参照画像53に評価を割り当てるために、評価集計表78を維持できる。
【００５９】
次いで、特徴マッチングユニット36が、上述の方法で全てのクエリ特徴記述子40の処理を終了したかどうかを決定する(118)。あるいは、マッチングユニット54が、グループ平均68Bによってグループ平均68Aを割った結果がしきい値70を下回らないと決定した場合(再び図3Aを参照すると、「いいえ」106)、特徴マッチングユニット36は、上述の方法で全てのクエリ特徴記述子40の処理を終了したかどうかを同様に決定できる(118)。全てのクエリ特徴記述子40の処理を終了したかどうかをどの状況において決定したかに関わらず、全てのクエリ特徴記述子40の処理を終了していない場合(「いいえ」118)、ユニット50〜60は、のこりのクエリ特徴記述子40を処理するために、記載した方法で動作する(94〜118)。
【００６０】
しかし、クエリ特徴記述子40の全ての処理を終了した場合(「はい」118)、評価割当てユニット60は、上述の方法で、割り当てられた評価(評価集積表78によって定義された)に基づいて参照画像53のランク付けされたリストを生成できる(120)。次いで、結果生成ユニット56が、参照画像53のランク付けされたリストを含むクエリ結果データ42を生成できる(122)。次いで、結果生成ユニット56が、インターフェース32を介してクライアントデバイス12にクエリ結果データ42を送信できる(124)。
【００６１】
図4は、特徴記述子抽出において使用するために決定されたガウス関数の差分(DoG)ピラミッド204を示す図である。図1の特徴抽出ユニット18は、ガウシアンピラミッド202内の任意の2個の連続するガウスぼかし画像の差分を計算することによってDoGピラミッド204を構成できる。図1の例に画像データ26として示されている入力画像I(x, y)は、ガウシアンピラミッド202を構成するために段階的にガウスぼかしされる。ガウスぼかしは一般的に、元の画像I(x,y)をスケールcσでガウスぼかし関数G(x,y,cσ)で畳みこむことを含む。ガウスぼかし関数L(x,y,cσ)はL(x,y,cσ)=G(x,y,cσ)*I(x, y)として定義される。この式では、Gはガウス核であり、cσは画像I(x,y)をぼかすために使用されるガウス関数の標準偏差を表す。cが(c0<c1<c2<c3<c4)と変化するように、標準偏差cσが変化して、段階的なぼかしが得られる。シグマσはベーススケール変数(基本的にガウス核の幅)である。ぼかし画像Lを生成するために最初の画像I(x, y)がガウシアンGで段階的に畳み込まれると、ぼかし画像Lはスケール空間内の定数係数cによって分離される。
【００６２】
DoG空間またはピラミッド204において、D(x,y,σ)=L(x, y, cnσ)-L(x,y,cn-1σ)である。DoG画像D(x,y,σ)は、スケールcnσとcn-1σの、2個の隣接するガウスぼかし画像L間の差分である。D(x,y,σ)のスケールはcnσとcn-1σとの間のどこかにある。ガウスぼかし画像Lの数が増加し、ガウシアンピラミッド202に提供された近似値が連続空間に近づくにつれて、2つのスケールも1つのスケールに近づく。畳み込まれた画像Lは、オクターブによってグループ化できる。オクターブは標準偏差σの値の倍増に対応する。さらに、オクターブごとに畳み込まれた画像Lの固定数が取得されるように、乗数kの値(たとえば、c0<c1<c2<c3<c4)が選択される。次いで、オクターブごとに、隣接するガウスぼかし画像LからDoG画像Dが取得されうる。それぞれのオクターブの後、ガウス画像が2倍でダウンサンプリングされて、次いでその処理が繰り返される。
【００６３】
次いで、特徴抽出ユニット18が、DoGピラミッド204を使用して、画像I(x,y)のキーポイントを識別できる。キーポイント検出を実施する際、特徴抽出ユニット18が、画像内の特定のサンプルのポイントまたは画素の周辺の局所空間またはパッチが、潜在的に興味深いパッチであるかどうかを決定する(幾何学的に言えば)。一般的に、特徴抽出ユニット18は、DoG空間204内の局所極大および/または局所極小を識別して、これらの極大および極小の位置をDoG空間204におけるキーポイント位置として使用する。図4に示される例において、特徴抽出ユニット18が、パッチ206内のキーポイント208を識別する。局所極大および局所極小を見つけること(局所極値検出としても知られている)は、DoG空間204内のそれぞれの画素(たとえば、キーポイント208の画素)を、同一スケールにおける8つの隣接画素、および両側にあるそれぞれの隣接スケールの9つの隣接画素(隣接するパッチ210および212内の)、合計で26画素(9×2+8=26)と比較することによって達成されうる。キーポイント208の画素値が、パッチ206、210、および212内の26個全ての比較された画素の中で極大または極小である場合、特徴抽出ユニット18がこれをキーポイントとして選択する。特徴抽出ユニット18が、キーポイントの位置がより正確に識別されるように、キーポイントをさらに処理できる。場合によっては、特徴抽出ユニット18が、低コントラストキーポイントおよびエッジキーポイントなどの、キーポイントのうちのいくつかを破棄しうる。
【００６４】
図5は、キーポイントの検出をより詳細に示す図である。図5の例において、それぞれのパッチ206、210および212は3×3画素空間を含む。特徴抽出ユニット18が、まず当該の画素(たとえば、キーポイント208)を、その8つの隣接画素302と、同じスケール(たとえば、パッチ206)で、ならびに隣接するパッチ210および212内の9つの隣接画素304および306と、キーポイント208の両側にそれぞれ隣接するスケールで比較する。
【００６５】
特徴抽出ユニット18は、局所画像勾配の方向に基づいて、それぞれのキーポイントを1つまたは複数の配向、または方向に割り当てることができる。局所画像特性に基づいてそれぞれのキーポイントに一貫した配向を割り当てることによって、特徴抽出ユニット18は、キーポイント記述子をこの配向に対して相対的に表して、それによって画像回転に対する不変性を達成できる。次いで、特徴抽出ユニット18は、ガウスぼかし画像Lにおける、および/またはキーポイントスケールにおけるキーポイント208の周辺の近傍領域の全ての画素に対して、大きさおよび方向を計算する。(x,y)に位置付けられたキーポイント208についての勾配の大きさは、m(x,y)と表され、(x,y)におけるキーポイントについての勾配の配向または方向はΓ(x,y)と表されうる。
【００６６】
次いで、特徴抽出ユニット18は、キーポイントのスケールを使用してキーポイント208のスケールに最も近いスケールを有するガウス平滑化された画像Lを選択する。それによって全ての計算がスケール不変の方法で行われる。このスケールで、それぞれの画像サンプルL(x,y)について、特徴抽出ユニット18は、画素差を使用して勾配の大きさm(x,y)、および配向Γ(x,y)を計算する。たとえば、大きさm(x,y)は、以下の式(2)によって計算されうる。
【００６７】
【数２】
0005749394.tif 000003
【００６８】
特徴抽出ユニット18は、以下の式(3)によって方向または配向Γ(x,y)を計算できる。
【００６９】
【数３】
0005749394.tif 000004
【００７０】
式(3)において、L(x,y)は、キーポイントのスケールでもあるスケールσにおけるガウスぼかし画像L(x,y,σ)のサンプルを表す。
【００７１】
特徴抽出ユニット18は、キーポイントについての勾配を、DoG空間内のキーポイントの平面よりも上のより高いスケールに位置するガウシアンピラミッドの平面に対して、または、キーポイントよりも下のより低いスケールに位置するガウシアンピラミッドの平面において、一貫して計算できる。いずれの方法であっても、キーポイントごとに、特徴抽出ユニット18は、そのキーポイントを囲む長方形の空間(たとえば、パッチ)において全て同じスケールで勾配を計算する。さらに、画像信号の周波数は、ガウスぼかし画像のスケールで反映される。しかし、SIFT、および圧縮された勾配のヒストグラム(CHoG)アルゴリズムなどの他のアルゴリズムは、単にパッチ(たとえば、長方形の空間)内の全ての画素で勾配値を使用する。パッチはキーポイントの周辺で定義され、サブブロックはブロック内で定義され、サンプルはサブブロック内で定義され、この構造は、たとえキーポイントのスケールが異なる場合であっても全てのキーポイントに対して同じままである。したがって、同じオクターブにおけるガウス平滑化フィルタの連続適用で画像信号の周波数は変化するが、異なるスケールで識別されたキーポイントは、この画像信号の周波数における変化とは関係なく同じサンプル数でサンプリングされ、それはスケールで表される。
【００７２】
キーポイントの配向を特徴付けるために、特徴抽出ユニット18は、たとえばSIFTを使用することによって勾配配向ヒストグラム(図6参照)を生成できる。それぞれの隣接画素の寄与は、勾配の大きさおよびガウスウィンドウによって重み付けされうる。ヒストグラムにおけるピークは、支配的な(dominant)配向に対応する。特徴抽出ユニット18は、キーポイント配向に相対してキーポイントの全ての特性を測定でき、これは回転に対する不変性を提供する。
【００７３】
一例では、特徴抽出ユニット18は、ブロックごとにガウス加重勾配の分布を計算する。それぞれのブロックは2個のサブブロック×2個のサブブロックという全部で4個のサブブロックである。ガウス加重勾配の分布を計算するために、特徴抽出ユニット18は、それぞれがキーポイントの周辺の領域の一部をカバーするいくつかのビンを備えた配向ヒストグラムを形成する。たとえば、配向ヒストグラムは36個のビンを有し、それぞれのビンが360度のうちの10度の配向をカバーする。あるいは、ヒストグラムは8個のビンを有しており、それぞれが360度のうちの45度をカバーする。本明細書に記載のヒストグラム符号化技法は、あらゆる数のビンのヒストグラムに適用可能であることは明白であるべきである。
【００７４】
図6は、特徴抽出ユニット18などの特徴抽出ユニットが、勾配分布と配向ヒストグラムとを決定する処理を示す図である。この図では、2次元勾配分布(dx,dy)(たとえば、ブロック406)が1次元分布(たとえば、ヒストグラム414)に変換される。キーポイント208が、キーポイント208を囲むブロック406(パッチ、セル、または領域とも呼ばれる)の中央に位置付けられる。ピラミッドの各レベルに対して事前に計算された勾配が、各サンプル位置408において小さい矢印で示されている。図示されるように、サンプル408の空間は、ビン410とも呼ばれうるサブブロック410を形成する。特徴抽出ユニット18は、ガウス重み関数を使用して、重みをサブブロックまたはビン410内のそれぞれのサンプル408に割り当てることができる。ガウス重み関数によってそれぞれのサンプル408に割り当てられた重みは、ビン410の重心とキーポイント208から平滑的に低下する。ガウス重み関数の目的は、ウィンドウの位置のわずかな変化による記述子の突発的な変化を回避することと、記述子の中心から離れている勾配に対してあまり重要性を与えないことである。特徴抽出ユニット18は、ヒストグラムのそれぞれのビン内の8個の配向を有する配向ヒストグラム412の矢印を決定して、次元特徴記述子をもたらす。たとえば、配向ヒストグラム413は、サブブロック410の勾配分布に対応できる。
【００７５】
いくつかの例では、特徴抽出ユニット18は、勾配分布を得るために他のタイプの量子化ビン群(たとえば、異なるボロノイセル構造を有する)を使用できる。同様に、これらの他のタイプのビン群はソフトビニングの形式を使用でき、ソフトビニングは、いわゆるDAISY構成が使用される場合に定義されるようなオーバーラッピングビンを指す。図6の例では3個のソフトビンが定義されているが、キーポイント208の周囲の円形形状402に一般的に位置する重心では9個以上が使用されうる。
【００７６】
本明細書で使用される場合、ヒストグラムは、ビンとして知られている互いに素な様々なカテゴリに含まれる観察、サンプル、または出現(たとえば、勾配)の数をカウントするマッピングkiである。ヒストグラムのグラフは、単に、ヒストグラムを表すための1つの方法である。このように、kが観察、サンプル、または出現の合計数であり、mがビンの合計数である場合、ヒストグラムkiの周波数は、式(4)で表される次の条件を満たす:
【００７７】
【数４】
0005749394.tif 000005
【００７８】
上式で、Σは、加法演算である。
【００７９】
特徴抽出ユニット18は、キーポイントのスケールの1.5倍の標準偏差でガウス重み付け関数によって定義された勾配の大きさによって、ヒストグラム412に追加されたそれぞれのサンプルに重み付けできる。結果として得られるヒストグラム414におけるピークは、局所勾配の支配的な方向に対応する。次いで、特徴抽出ユニット18は、ヒストグラム内で最も高いピーク、次いで最も高いピークの80%など特定の割合内である他の任意の局所ピークを検出する(その配向のキーポイントを作成するためにも使用できる)。したがって、類似の大きさの複数のピークがある位置について、特徴抽出ユニット18は、同じ位置およびスケールで作成されたが配向が異なる複数のキーポイントを抽出する。
【００８０】
次いで、特徴抽出ユニット18は、タイプ量子化と呼ばれる量子化の形式を使用してヒストグラムを量子化し、タイプとしてのヒストグラムを表す。この方法で、特徴抽出ユニット18はキーポイントごとに記述子を抽出でき、このような記述子は位置(x,y)、配向、およびタイプの形式のガウス加重勾配の分散の記述子によって特徴付けることができる。このように、1つまたは複数のキーポイント記述子(画像記述子とも呼ばれる)によって画像を特徴づけることができる。
【００８１】
図4〜6に示される上記の例はSIFTアルゴリズムによって実行される特徴抽出の一例を提供するが、本技法は、圧縮された勾配のヒストグラム(CHoG)アルゴリズムなどの他の任意の視覚探索アルゴリズムに従って抽出される特徴記述子に関して実施されうる。したがって、本技法は、この点でSIFTアルゴリズムを使用して抽出される特徴記述子のみに限定されるべきではなく、任意の視覚探索アルゴリズムに従って抽出される特徴記述子に関して実施されうる。
【００８２】
図7は、本開示に記載の技法による特徴マッチングを実行する際の、図1の特徴マッチングユニット36などの特徴マッチングユニットの例示的動作を示す図である。図7の例では、クエリ画像データ500および参照画像データ502が示されており、クエリ画像データ500は参照画像データ502の左に示されている。黒線は、クエリ画像データ500から抽出されたクエリ特徴記述子(利用可能な場合は左配向矢印によって表される)と、参照画像データ502から抽出されて特徴記述子データベース38に格納される参照特徴記述子(右配向矢印によって表される)との間の関係を示している。
【００８３】
クエリ画像データ500は、クライアントデバイス12などのクライアントデバイスによって撮影または取得されたピサの斜塔の画像を示している。参照画像データ502は、特徴記述子データベース38に格納されたピサの斜塔の他の画像を示している。クエリ画像データ500および参照画像データ502は、異なるスケールとして、また異なる(類似しているが)視点から撮影されたピサの斜塔の画像を示している。この例では、視覚探索サーバ14の特徴マッチングユニット36は、左矢印によって示される特徴を表すクエリ特徴記述子40を受信する。特徴マッチングユニット36は、右矢印によって示される対応する特徴を表す一致する参照特徴記述子51(図2を参照)を決定する。
【００８４】
この例では、ピサの斜塔は、ピサの斜塔を囲む反復するアーチ状の多くの反復する構造を含む。504A〜504Cで特に示される3本の黒線は、特徴記述子空間において相互に近い可能性がある、対応するクエリと参照特徴記述子との間の潜在的な一致を示している。従来の視覚探索アルゴリズムでは一般的であるようにこれらの一致を一意ではないと拒否するのではなく、特徴マッチングユニット36は、これらの線504A〜504Cの左側の矢印によって表される対応するクエリ特徴記述子40ごとに、互いに対して第1のグループ66Aにグループ化される距離62(再び図2を参照)を決定できる。
【００８５】
たとえば、線504Aによって示される一致を考慮すると、特徴マッチングユニット36は、線504Aの左矢印によって表されるクエリ特徴記述子40が、線504A〜504Cならびに504D〜504Gごとに右矢印によって表される参照特徴記述子51と一致すると決定できる。特徴マッチングユニット36は、上述の方法で、線504A〜504Gに関連付けられる、参照特徴記述子51に関連する線504Aに関連付けられる、クエリ特徴記述子40に関連する距離62を決定できる。次に、特徴マッチングユニット36は、線504Aに関連付けられるクエリ特徴記述子、および線504A〜504Cに関連付けられる参照特徴記述子に関連して計算された距離62、ならびに全ての残りの距離を含む他のグループをグループ化できる。次いで、特徴マッチングユニット36は、第1および第2のグループ距離66を平均化して、第2のグループ平均68Bによって第1のグループ平均68Aを割って、割った結果としきい値とを比較できる。この例では、特徴マッチングユニット36は、一意の一致を決定して、それによって線504Aで示される一致を決定する。
【００８６】
SIFTなどの視覚探索アルゴリズムの従来の特徴マッチング態様は、クラスタリングアルゴリズムを使用しないことによって、線504Aによって表される一致を拒否する場合があった。この一致の拒否は、線504Aの左矢印によって表される特徴から抽出されるクエリ特徴記述子40と、線504Aの右矢印によって表される特徴から抽出される参照特徴記述子51との間の距離が最小である場合があるために発生しうる。この例では、次に最小の距離は、線504Aの左矢印によって表される特徴から抽出されるクエリ特徴記述子40と、線504Bの右矢印によって表される特徴から抽出される参照特徴記述子51との間の距離の場合がある。この、次に最小の距離は、上述の最小距離とほぼ同じだけ小さい場合がある。したがって、視覚探索アルゴリズムの従来の特徴マッチング態様に従って最小距離を次に最小の距離によって割ると1に近い数字をもたらす場合があり、一般的に0.5などの1の分数に設定されるしきい値よりも大きい場合がある。
【００８７】
したがって、本開示に記載の技法によってグループを決定するためにクラスタリングアルゴリズムを使用することによって、特徴マッチングユニット36は、反復特徴パターンを参照するこれらの全ての比較的小さい距離62を第1のグループ66Aにグループ化でき、他の全ての距離62を第2のグループであるグループ66Bにグループ化できる。次いで、特徴マッチングユニット36は、それぞれのこれらのグループの比較を容易にするためにこれらの距離を平均化して、一意の一致と考えられる可能性があるものの拒否を回避するためにこの平均を比較する。結果として、本技法は、特に反復する特徴または態様を有する画像に関して特徴マッチングを改善しうる。
【００８８】
さらに、誤った一致の受諾の制御を維持しながら潜在的な一致の拒否を回避するために、本開示の堅牢な距離比技法は、上述のより区別的な類似性測定を提供する。堅牢な距離比技法は、k次元木(KD tree)-最適ビン優先を使用して、第1の最も近い隣接を問い合わせる間に格納された中間データを使用することによって、オーバーヘッドコンピューティングコストがほとんどまたは全くなしに実行されうる。
【００８９】
1つまたは複数の例では、記載された機能はハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組合せに実装されうる。ソフトウェアに実装された場合、機能は、1つまたは複数の命令あるいは符号としてコンピュータ可読記録媒体に格納されるか、またはそれを介して送信されうる。コンピュータ可読記録媒体は、コンピュータデータストレージ媒体を含みうる。データストレージ媒体は、本開示に記載の技法を実装するための命令、符号、および/またはデータ構造を取り出すために、1つまたは複数のコンピュータ、あるいは1つまたは複数のプロセッサによってアクセスされうる任意の利用可能な媒体でよい。本明細書で使用される「データストレージ媒体」は製品を指し、一時的な伝搬信号を指すものではない。例を挙げると、これに限定されないが、このようなコンピュータ可読記録媒体は、RAM、ROM、EEPROM、CD-ROM、または他の光ディスクストレージ、磁気ディスクストレージ、あるいは他の磁気ストレージデバイス、フラッシュメモリ、または所望のプログラムコードを命令またはデータ構造の形式で格納するために使用でき、コンピュータによってアクセスされうる、他の任意の媒体を備えることができる。本明細書で使用されるディスク(disk)およびディスク(disc)は、コンパクトディスク(CD)、レーザーディスク(登録商標)、光ディスク、デジタル多用途ディスク(DVD)、フロッピーディスク(登録商標)およびブルーレイディスクを含み、通常ディスク(disk)はデータを磁気的に再生し、ディスク(disc)はデータをレーザで光学的に再生する。上記の組合せも、コンピュータ可読記録媒体の範囲内に含まれるべきである。
【００９０】
符号は、1つまたは複数のデジタル信号プロセッサ(DSP)などの1つまたは複数のプロセッサ、汎用マイクロプロセッサ、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)、または他の同等の統合されたまたは個別の論理回路などの1つまたは複数のプロセッサによって実行されうる。したがって、本明細書で使用される「プロセッサ」という用語は、前述の構造のうちのいずれか、または本明細書に記載の技法の実装に適した他の任意の構造を指すことができる。さらに、いくつかの態様では、本明細書に記載の機能は、符号化および復号化するように構成された、または結合されたコーデックに組み込まれた、専用ハードウェアおよび/またはソフトウェアモジュール内で提供されうる。また、本技法は1つまたは複数の回路あるいは論理要素に完全に実装されうる。
【００９１】
本開示の技法は、無線ハンドセット、集積回路(IC)、またはICのセット(たとえば、チップセット)を含めた様々なデバイスまたは装置に実装されうる。本開示において、開示された技法を実行するように構成されたデバイスの機能面を強調するために、様々なコンポーネント、モジュール、またはユニットを記述したが、必ずしも異なるハードウェアユニットによって実現する必要はない。むしろ、上述のように、コンピュータ可読記録媒体に格納された適切なソフトウェアおよび/またはファームウェアと併せて、上述のように1つまたは複数のプロセッサを含めて、様々なユニットがコーデックハードウェアユニットに結合されてもよく、相互作用するハードウェアユニットの集合によって提供されてもよい。
【００９２】
様々な例を記述してきた。これらおよび他の例は以下の特許請求の範囲内である。
【符号の説明】
【００９３】
10  画像処理システム
12  クライアントデバイス
14  視覚探索サーバ
16  ネットワーク
18  特徴抽出ユニット
20  特徴圧縮ユニット
22  インターフェース
24  ディスプレイ
26  画像データ
28  特徴記述子
30  クエリデータ
32  インターフェース
34  特徴再構成ユニット
36  特徴マッチングユニット
38  特徴記述子データベース
40  クエリ特徴記述子
42  クエリ結果データ
50  距離計算ユニット
51  参照特徴記述子
52  グループ化ユニット
53  参照画像
54  マッチングユニット
56  結果生成ユニット
58  リスト形成ユニット
60  評価割当てユニット
62  距離
62A  距離
62N  距離
64  クラスタリングアルゴリズム
66  グループ
66A  グループ
66B  グループ
68A  グループ平均
68B  グループ平均
70  しきい値
72  一致インジケータ
74  一意の参照画像リスト
76  最初の参照画像リスト
78  評価集計表
202  ガウシアンピラミッド
204  ガウス関数の差分(DoG)ピラミッド
206  パッチ
208  キーポイント
210  パッチ
212  パッチ
302  画素
304  画素
306  画素
402  円形形状
406  ブロック
408  サンプル
410  サブブロック
410  ビン
412  配向ヒストグラム
413  配向ヒストグラム
414  ヒストグラム
500  クエリ画像データ
502  参照画像データ
504A  線
504B  線
504C  線
504D  線
504E  線
504F  線
504G  線
【図１】
0005749394.tif 000006
【図２】
0005749394.tif 000007
【図３Ａ】
0005749394.tif 000008
【図３Ｂ】
0005749394.tif 000009
【図４】
0005749394.tif 000010
【図５】
0005749394.tif 000011
【図６】
0005749394.tif 000012
【図７】
0005749394.tif 000013