(57)【特許請求の範囲】
【請求項１】
画像のための局所特徴記述子を生成するための方法であって、
画像のための複数のスケール空間からの第１のスケール空間内のポイントを識別することと、
前記複数のスケール空間中のスケール空間ごとに複数の配向マップを取得することと、
対応する複数の平滑化配向マップを取得するために前記複数の配向マップの各々を平滑化することと、
前記ポイントのための局所特徴記述子を生成するために、前記複数のスケール空間からの２つ以上のスケール空間に対応する複数の平滑化配向マップをばらばらにサンプリングすることと、
を含む、方法。
【請求項２】
前記複数のスケール空間を取得するために前記画像を漸進的に平滑化することを更に含み、前記複数の平滑化配向マップ内の配向マップの前記平滑化が前記配向マップのスケール空間レベルに比例する、請求項１に記載の方法。
【請求項３】
前記複数の配向マップの各々が、対応する画像微分の非負値から取得される場合に、前記複数のスケール空間の各々について複数の画像微分を取得することをさらに含む、請求項１に記載の方法。
【請求項４】
前記ポイントが、前記複数のスケール空間内の位置のサブセットからのサンプルポイントである、請求項１に記載の方法。
【請求項５】
位置の前記サブセットが、対象物についての予想パターンに基づいて選択される、請求項４に記載の方法。
【請求項６】
前記位置のサブセットが、前記画像内の識別キーポイントに基づいて選択され、キーポイントが、イメージング条件の変化に対してロバストであると識別されているポイントである、請求項４に記載の方法。
【請求項７】
前記２つ以上のスケール空間が、前記第１のスケール空間と、前記第１のスケール空間よりも低い解像度の一つ以上の追加のスケール空間とを含む、請求項１に記載の方法。
【請求項８】
前記局所特徴記述子が、前記ポイントの中心上に分散されたサンプルポイントの空間プーリングによって定義されたカーネルプーリング構成を有する、請求項１に記載の方法。
【請求項９】
複数の平滑化配向マップをばらばらにサンプリングすることは、
第１の平滑化配向マップ上の第１の複数のポイントをサンプリングすること、
第２の平滑化配向マップ上の第２の複数のポイントをサンプリングすること、を含み、
前記第１の複数のポイントが、前記ポイントの位置と同心の第１のリングに配置され、前記第２の複数のポイントが、前記ポイントの前記位置と同心の第２のリングに配置され、前記第２の平滑化配向マップが、前記第１のスケール空間よりも低い解像度の第２のスケール空間に対応する、請求項１に記載の方法。
【請求項１０】
複数の平滑化配向マップをばらばらにサンプリングすることは、
第３の平滑化配向マップ上の第３の複数のポイントをサンプリングすることを含み、前記第３の複数のポイントが、前記ポイントの前記位置と同心の第３のリングに配置され、前記第３の平滑化配向マップが、前記第１のスケール空間よりも低い解像度の第３のスケール空間に対応する、請求項９に記載の方法。
【請求項１１】
前記第２のリングが、前記第１のリングの第１の半径よりも大きい第２の半径を有し、前記第３のリングが、前記第２のリングの前記第２の半径よりも大きい第３の半径を有する、請求項１０に記載の方法。
【請求項１２】
各スケール空間のための前記複数の配向マップが、複数の異なる配向のための配向マップを含む、請求項１に記載の方法。
【請求項１３】
各配向マップが、単一の対応する平滑化配向マップに分解する、請求項１に記載の方法。
【請求項１４】
前記複数の平滑化配向マップの前記ばらばらのサンプリングから複数の配向勾配ヒストグラムを構築することを更に含み、前記局所特徴記述子が前記複数のヒストグラムを含む、請求項１に記載の方法。
【請求項１５】
前記複数の配向マップが、同じ平滑化係数を使用して平滑化され、前記第１のスケール空間が、前記２つ以上のスケール空間のうちの１つであり、第２のスケール空間が、前記第１のスケール空間に対して所望の平滑化を達成するように選択される、請求項１に記載の方法。
【請求項１６】
画像を取得するように適応された入力インターフェースと、
一つ以上の画像についての局所特徴記述子を記憶する記憶装置と、
前記入力インターフェースと前記記憶装置とに結合された処理回路と、
を具備し、
画像のための複数のスケール空間からの第１のスケール空間内のポイントを識別することと、
前記複数のスケール空間中のスケール空間ごとに複数の配向マップを取得することと、
対応する複数の平滑化配向マップを取得するために前記複数の配向マップの各々を平滑化することと、
前記ポイントのための局所特徴記述子を生成するために、前記複数のスケール空間からの２つ以上のスケール空間に対応する複数の平滑化配向マップをばらばらにサンプリングすることと、
を行うように構成された、画像処理装置。
【請求項１７】
前記２つ以上のスケール空間が、前記第１のスケール空間と、前記第１のスケール空間よりも低い解像度の一つ以上の追加のスケール空間とを含む、請求項１６に記載の画像処理装置。
【請求項１８】
前記処理装置は、
前記複数のスケール空間の各々について複数の画像微分を取得するように更に構成され、前記複数の配向マップの各々が、対応する画像微分の非負値から取得される、請求項１６に記載の画像処理装置。
【請求項１９】
前記ポイントが、前記複数のスケール空間内の位置のサブセットからのサンプルポイントである、請求項１６に記載の画像処理装置。
【請求項２０】
前記局所特徴記述子が、前記ポイントの中心上に分散されたサンプルポイントの空間プーリングによって定義されたカーネルプーリング構成を有する、請求項１６に記載の画像処理装置。
【請求項２１】
複数の平滑化配向マップをばらばらにサンプリングすることは、
第１の平滑化配向マップ上の第１の複数のポイントをサンプリングすること、た、サンプリングすることと、
第２の平滑化配向マップ上の第２の複数のポイントをサンプリングすること、
を含み、前記第１の複数のポイントが、前記ポイントの位置と同心の第１のリングに配置され、前記第２の複数のポイントが、前記ポイントの前記位置と同心の第２のリングに配置され、前記第２の平滑化配向マップが、前記第１のスケール空間よりも低い解像度の第２のスケール空間に対応する、請求項１６に記載の画像処理装置。
【請求項２２】
複数の平滑化配向マップをばらばらにサンプリングすることは、
第３の平滑化配向マップ上の第３の複数のポイントをサンプリングすることを更に含み、前記第３の複数のポイントが、前記ポイントの前記位置と同心の第３のリングに配置され、前記第３の平滑化配向マップが、前記第１のスケール空間よりも低い解像度の第３のスケール空間に対応する、請求項２１に記載の画像処理装置。
【請求項２３】
前記処理装置は、
前記複数の平滑化配向マップの前記ばらばらのサンプリングから複数の配向勾配ヒストグラムを構築するように更に構成され、前記局所特徴記述子が前記複数のヒストグラムを含む、請求項１６に記載の画像処理装置。
【請求項２４】
前記複数の配向マップが、同じ平滑化係数を使用して平滑化され、前記第１のスケール空間が、前記２つ以上のスケール空間のうちの１つであり、第２のスケール空間が、前記第１のスケール空間に対して所望の平滑化を達成するように選択される、請求項１６に記載の画像処理装置。
【請求項２５】
画像のための複数のスケール空間からの第１のスケール空間内のポイントを識別するための手段と、
前記複数のスケール空間中のスケール空間ごとに複数の配向マップを取得するための手段と、
対応する複数の平滑化配向マップを取得するために前記複数の配向マップの各々を平滑化するための手段と、
前記ポイントのための局所特徴記述子を生成するために、前記複数のスケール空間からの２つ以上のスケール空間に対応する複数の平滑化配向マップをばらばらにサンプリングするための手段と、
を具備する、画像処理装置。
【請求項２６】
前記複数のスケール空間の各々について複数の画像微分を取得するための手段を更に含み、前記複数の配向マップの各々が、対応する画像微分の非負値から取得される、請求項２５に記載の画像処理装置。
【請求項２７】
前記ポイントが、前記複数のスケール空間内の位置のサブセットからのサンプルポイントである、請求項２５に記載の画像処理装置。
【請求項２８】
前記２つ以上のスケール空間が、前記第１のスケール空間と、前記第１のスケール空間よりも低い解像度の一つ以上の追加のスケール空間とを含む、請求項２５に記載の画像処理装置。
【請求項２９】
前記局所特徴記述子が、前記ポイントの中心上に分散されたサンプルポイントの空間プーリングによって定義されたカーネルプーリング構成を有する、請求項２５に記載の画像処理装置。
【請求項３０】
複数の平滑化配向マップをばらばらにサンプリングするための手段は、
第１の平滑化配向マップ上の第１の複数のポイントをサンプリングするための手段と、
第２の平滑化配向マップ上の第２の複数のポイントをサンプリングするための手段と、を含み、
前記第１の複数のポイントが、前記ポイントの位置と同心の第１のリングに配置され、前記第２の複数のポイントが、前記ポイントの前記位置と同心の第２のリングに配置され、前記第２の平滑化配向マップが、前記第１のスケール空間よりも低い解像度の第２のスケール空間に対応する、請求項２５に記載の画像処理装置。
【請求項３１】
複数の平滑化配向マップをばらばらにサンプリングするための手段は、
第３の平滑化配向マップ上の第３の複数のポイントをサンプリングするための手段を更に含み、前記第３の複数のポイントが、前記ポイントの前記位置と同心の第３のリングに配置され、前記第３の平滑化配向マップが、前記第１のスケール空間よりも低い解像度の第３のスケール空間に対応する、請求項３０に記載の画像処理装置。
【請求項３２】
前記複数の平滑化配向マップの前記ばらばらのサンプリングから複数の配向勾配ヒストグラムを構築するための手段を更に含み、前記局所特徴記述子が前記複数のヒストグラムを含み、請求項２５に記載の画像処理装置。
【請求項３３】
装置中で動作可能な一つ以上の命令を備えるプロセッサ可読媒体であって、処理回路によって実行されたとき、
画像のための複数のスケール空間からの第１のスケール空間内のポイントを識別することと、
前記複数のスケール空間中のスケール空間ごとに複数の配向マップを取得することと、
対応する複数の平滑化配向マップを取得するために前記複数の配向マップの各々を平滑化することと、
前記ポイントのための局所特徴記述子を生成するために、前記複数のスケール空間からの２つ以上のスケール空間に対応する複数の平滑化配向マップをばらばらにサンプリングすることと、
を前記処理回路に行わせる、プロセッサ可読記憶媒体。
【請求項３４】
前記２つ以上のスケール空間が、前記第１のスケール空間と、前記第１のスケール空間よりも低い解像度の一つ以上の追加のスケール空間とを含む、請求項３３に記載のプロセッサ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
米国特許法第１１９条による優先権の主張
本特許出願は、両方とも本出願の譲受人に譲渡され、参照により本明細書に明確に組み込まれる、２０１０年４月２０日に出願された「Extracting Daisy Descriptor in Scale-Space」と題する米国仮出願第６１／３２６，０８７号と、２０１０年１１月１１日に出願された「Fast Descriptor Extraction in Scale-Space」と題する米国仮出願第６１／４１２，７５９号との優先権を主張する。
【０００２】
１つの特徴は、コンピュータビジョンに関し、より詳細には、画像の認識及び検索性能、処理、及び／又は圧縮を改善するための方法及び技法に関する。
【背景技術】
【０００３】
様々な適用例は、視覚表現（例えば、画像又はピクチャ）中の対象物を識別することが可能である機械又はプロセッサを有することから恩恵を受け得る。コンピュータビジョンの分野は、画像中の対象物又は特徴を識別することを可能にする技法及び／又はアルゴリズムを提供することを試みており、対象物又は特徴は、一つ以上のポイント（例えば、全ての画素ポイント、注目するキーポイントなど）を識別する記述子によって特徴づけられ得る。これらの技法及び／又はアルゴリズムはまた、しばしば、適用例の中でも、顔認識、対象物検出、画像マッチング、３次元構造構築、ステレオ対応、及び／又は動き追跡に適用される。概して、対象物又は特徴認識は、特徴識別、画像検索、及び／又は対象物認識の目的で画像中の注目するポイントを識別することを伴い得る。好ましくは、ポイントは、それらが画像スケール変化及び／又は回転に対して不変（invariant）であり、歪み、視点の変化、及び／又はノイズ及び照明の変化の実質的な範囲にわたってロバストなマッチングを与えるように、選択及び／又は処理され得る。さらに、画像検索及び対象物認識などのタスクのために好適であるように、特徴記述子は、好ましくは、単一の特徴が、複数のターゲット画像からの特徴の大規模データベースに対して高い確率で正しくマッチングされ得るという意味において特徴的であり得る。
【０００４】
例えば、注目するポイントの位置を特定するために、ガウスピラミッドを使用して局所画像計算が実行され得る。ＳＩＦＴ（スケール不変特徴変換（scale invariant feature transform））など、幾つかのコンピュータビジョンアルゴリズムが、そのようなポイントを計算するために使用され、次いで、シーン中の特定の対象物の検出又は特徴に基づくクエリ対象物の分類への最初のステップとして、それらのポイントの周りの局在特徴を抽出することに進む。
【０００５】
画像中の一つ以上のポイントが検出され、位置を特定された後、それらのポイントは、様々な記述子を使用することによって識別又は記述され得る。例えば、記述子は、画像特性の中でも、形状、色、テクスチャ、回転、及び／又は動きなど、画像中のコンテンツの視覚特徴を表し得る。記述子は、ポイントと、そのポイントの周りの局所近傍とを表し得る。記述子抽出の目的は、ポイントの周りの局所情報について、ロバストで、ノイズのない表現を獲得することである。
【０００６】
ポイントに対応し、記述子によって表される個々の特徴は、既知の対象物からの特徴のデータベースにマッチングされる。従って、対応探索システムは、ポイント検出器と、特徴記述子と、対応ロケータという、３つのモジュールに分離され得る。これらの３つの論理モジュールでは、記述子の構築複雑さ及び次元数（dimensionality）が特徴マッチングシステムの性能に直接著しい影響を及ぼす。
【０００７】
そのような特徴記述子は、リアルタイム対象物認識、拡張現実、３Ｄ再構成、パノラマステッチング、ロボットマッピング、ビデオ追跡、及び同様のタスクに適用例をますます見出している。適用例によっては、特徴記述子（又は等価物）の送信及び／又は記憶は、対象物検出の計算の速度及び／又は画像データベースのサイズを制限することがある。モバイルデバイス（例えば、カメラフォン、モバイルフォンなど）又は分散カメラネットワークのコンテキストでは、ノード間での記述子抽出にかなりの通信及び処理リソースが費やされ得る。記述子抽出の計算集約的プロセスは、モバイルフォンなど、リソースの限られたデバイスに対するそれの適用を妨げるか又は複雑にする傾向がある。
【０００８】
様々な記述子が提案されており、各々が異なる利点を有する。スケール不変特徴変換（ＳＩＦＴ）は、ポイントの近傍にある（画素勾配の）支配的配向と整合され、検出されたポイントのスケールレベルに比例してサイズ決定された方形パッチを開く。この領域中の勾配値はセル中にまとめられ、各セル中には複数のビン配向ヒストグラムがある。デイジー記述子（Daisy descriptor）は、高密度マッチング及びパッチ対応問題においてＳＩＦＴよりも良好で高速のマッチング性能を示している。ＳＩＦＴ記述子に勝るデイジー記述子の重要な利点は、デイジー記述子を構築する際に、配向微分の空間ビニング（spatial binning）が異なる解像度を表すということである。より詳細には、ビンがポイントからさらに離れて位置するほど、空間ビンサイズはより大きくなる（即ち、より粗くなる）。異なる解像度を使用することにより、デイジー記述子は回転及びスケール変化に対してよりロバストになる。ただし、高速空間ビニングデイジー記述子を計算するには、画像微分ごとに３つのスケールのスケール空間を構築するための追加メモリが必要になる。（ＳＩＦＴに対して）デイジー記述子アルゴリズムの別の重要な制限は、記憶のために必要とされる追加メモリである。例えば、８つの配向微分の各々について３つのスケールレベルが必要とされる。デイジー記述子を使用するとき、合計追加メモリはＭ×Ｎ画像について（即ち、平滑化画素ごとに１バイトのダイナミックレンジを仮定して）２４×Ｍ×Ｎバイトである。メモリ複雑さは、Ｓスケールレベルをもつスケール空間では、さらに２４×Ｍ×Ｎ×Ｓに増加する。これは、スケール不変デイジー記述子、即ちスケール空間中のデイジー記述子の抽出を制限する。
【０００９】
従って、スケール空間中のデイジー記述子を生成及び／又は記憶するために必要とされるメモリの量を低減するための方法が必要とされる。
【発明の概要】
【００１０】
以下で、幾つかの実施形態の基本的な理解を与えるために、一つ以上の実施形態の簡略化された概要を提示する。この概要は、全ての企図される実施形態の包括的な概観ではなく、全ての実施形態の主要又は重要な要素を識別するものでも、いずれか又は全ての実施形態の範囲を定めるものでもない。その唯一の目的は、後で提示するより詳細な説明の導入として、一つ以上の実施形態の幾つかの概念を簡略化された形式で提示することである。
【００１１】
画像のための局所特徴記述子を生成するための方法が提供される。画像は、複数のスケール空間を取得するために漸進的に平滑化され得る。画像のための複数のスケール空間からの第１のスケール空間内のポイントが識別される。次いで、複数のスケール空間の各々について複数の画像微分が取得され、複数の配向マップの各々が、対応する画像微分の非負値から取得される。次いで、複数のスケール空間中のスケール空間ごとに複数の配向マップが取得される。各スケール空間のための複数の配向マップは、複数の異なる配向のための配向マップを含み得る。各配向マップは、単一の対応する平滑化配向マップに分解し得る。対応する複数の平滑化配向マップを取得するために複数の配向マップの各々が平滑化される。複数の平滑化配向マップ内の配向マップの平滑化は配向マップのスケール空間レベルに比例し得る。次いで、複数のスケール空間からの２つ以上のスケール空間に対応する複数の平滑化配向マップをばらばらにサンプリング（スパースサンプリング）することによって、ポイントについての局所特徴記述子が生成又は取得され得る。例えば、局所特徴記述子は、ポイントの中心上に分散されたサンプルポイントの空間プーリングによって定義されたカーネルプーリング構成を有し得る。幾つかの事例では、局所特徴記述子は、複数の平滑化配向マップのばらばらのサンプリングからの配向勾配から構築された複数のヒストグラムを備え得る。
【００１２】
一例では、ポイントは、複数のスケール空間内の位置のサブセットからのサンプルポイントであり得る。例えば、位置のサブセットは、対象物についての予想パターンに基づいて選択され得る。別の例では、位置のサブセットは、画像内の識別キーポイントに基づいて選択され得、キーポイントは、イメージング条件の変化に対してロバストであると識別されているポイントである。
【００１３】
一例では、２つ以上のスケール空間は、第１のスケール空間と、第１のスケール空間よりも低い解像度の一つ以上の追加のスケール空間とを含む。例えば、複数の平滑化配向マップをばらばらにサンプリングすることは、（ａ）第１の平滑化配向マップ上の第１の複数のポイントをサンプリングすることであって、第１の複数のポイントが、ポイントの位置と同心の第１のリングに配置された、サンプリングすること、（ｂ）第２の平滑化配向マップ上の第２の複数のポイントをサンプリングすることであって、第２の複数のポイントが、ポイントの位置と同心の第２のリングに配置され、第２の平滑化配向マップが、第１のスケール空間よりも低い解像度の第２のスケール空間に対応する、サンプリングすること、及び／又は（ｃ）第３の平滑化配向マップ上の第３の複数のポイントをサンプリングすることであって、第３の複数のポイントが、ポイントの位置と同心の第３のリングに配置され、第３の平滑化配向マップが、第１のスケール空間よりも低い解像度の第３のスケール空間に対応する、サンプリングすることを含み得る。一例では、第２のリングは、第１のリングの第１の半径よりも大きい第２の半径を有し得、第３のリングは、第２のリングの第２の半径よりも大きい第３の半径を有する。
【００１４】
一態様によれば、複数の配向マップは、同じ平滑化係数を使用して平滑化され得、第１のスケール空間は、２つ以上のスケール空間のうちの１つであり、第２のスケール空間は、第１のスケール空間に対して所望の平滑化を達成するように選択される。
【００１５】
画像のための局所特徴記述子を生成するための画像処理装置が提供される。画像処理装置は、入力インターフェース／機器、記憶装置、及び／又は処理回路を含み得る。入力インターフェースは、画像を取得、撮像、及び／又は受信するように働くか若しくは適応され得る。記憶装置は、一つ以上の画像についての局所特徴記述子を記憶するように働き得る。処理回路は、入力インターフェースと記憶装置とに結合され、（ａ）複数のスケール空間を取得するために画像を漸進的に平滑化すること、（ｂ）複数のスケール空間からの第１のスケール空間内のポイントを識別すること、（ｃ）複数のスケール空間の各々について複数の画像微分を取得すること、（ｄ）複数のスケール空間中のスケール空間ごとに複数の配向マップを取得することであって、複数の配向マップの各々が、対応する画像微分の非負値から取得される、取得すること、（ｅ）対応する複数の平滑化配向マップを取得するために複数の配向マップの各々を平滑化すること、及び／又は（ｆ）ポイントについての局所特徴記述子を生成するために、複数のスケール空間からの２つ以上のスケール空間に対応する複数の平滑化配向マップをばらばらにサンプリングすることを行うための演算を実行するように適応され得、及び／又はそのための一つ以上の回路を含み得る。局所特徴記述子は、ポイントの中心上に分散されたサンプルポイントの空間プーリングによって定義されたカーネルプーリング構成を有し得る。
【００１６】
２つ以上のスケール空間は、第１のスケール空間と、第１のスケール空間よりも低い解像度の一つ以上の追加のスケール空間とを含み得る。ポイントは、複数のスケール空間内の位置のサブセットからのサンプルポイントであり得る。
【００１７】
複数の平滑化配向マップをまばらにサンプリングすることは、（ａ）第１の平滑化配向マップ上の第１の複数のポイントをサンプリングすることであって、第１の複数のポイントが、ポイントの位置と同心の第１のリングに配置された、サンプリングすること、（ｂ）第２の平滑化配向マップ上の第２の複数のポイントをサンプリングすることであって、第２の複数のポイントが、ポイントの位置と同心の第２のリングに配置され、第２の平滑化配向マップが、第１のスケール空間よりも低い解像度の第２のスケール空間に対応する、サンプリングすること、及び／又は（ｃ）第３の平滑化配向マップ上の第３の複数のポイントをサンプリングすることを含み、第３の複数のポイントが、ポイントの位置と同心の第３のリングに配置され、第３の平滑化配向マップが、第１のスケール空間よりも低い解像度の第３のスケール空間に対応する。処理装置は、複数の平滑化配向マップのばらばらのサンプリングから複数の配向勾配ヒストグラムを構築するように構成でき、局所特徴記述子が複数のヒストグラムを備える。一例では、複数の配向マップは、同じ平滑化係数を使用して平滑化され、第１のスケール空間は、２つ以上のスケール空間のうちの１つであり、第２のスケール空間は、第１のスケール空間に対して所望の平滑化を達成するように選択される。
【００１８】
様々な特徴、性質、及び利点は、全体を通じて同様の参照符号が同様のものを指す図面とともに、以下に記載する詳細な説明を読めば明らかになろう。
【図面の簡単な説明】
【００１９】
【図１】効率的に生成されたデイジー記述子を使用することによってクエリ画像上で対象物認識を実行するための機能段階を示すブロック図。
【図２】一例による、デイジー記述子を生成するために使用されるスケール空間と配向マップとの生成を示す図。
【図３】スケール空間のスケールレベルが、配向マップを定義するために複数の勾配配向を有する画素をどのように含み得るかを示す図。
【図４】配向マップがスケール空間レベルからどのように生成され得るかを示す図。
【図５】配向マップがスケール空間レベルからどのように生成され得るかを示す図。
【図６】配向マップがスケール空間レベルからどのように生成され得るかを示す図。
【図７】デイジー記述子の典型的な生成を示す図。
【図８】配向マップごとに複数の平滑化（畳み込み）配向マップを生成する必要を回避するより効率的な一例による、修正デイジー記述子を生成するために使用されるスケール空間と配向マップとの生成を示す図。
【図９】デイジー記述子が、スケール空間ピラミッドの複数のレベルを使用することによってどのように生成され得るかを示す図。
【図１０】スケール空間上の修正デイジー記述子と比較した、典型的なデイジー記述子の生成の比較を示す図。
【図１１】複数のスケール空間レベルにわたって記述子を生成する記述子生成デバイスの一例を示すブロック図。
【図１２】複数のスケール空間レベルにわたって局所特徴記述子を生成するための方法を示す流れ図。
【図１３】スケール空間の複数のレベルにわたって生成された局所記述子を使用して画像又は対象物認識のために画像処理を実行するように適応された例示的なモバイルデバイスを示すブロック図。
【発明を実施するための形態】
【００２０】
次に、図面を参照しながら様々な実施形態について説明する。図面全体にわたって、同様の要素を指すのに同様の参照番号を使用する。以下の記述では、説明のために、一つ以上の実施形態の完全な理解を与えるために多数の具体的な詳細を記載する。ただし、そのような（一つ又は複数の）実施形態は、これらの具体的な詳細なしに実施され得ることは明らかであろう。他の例では、一つ以上の実施形態の説明を円滑にするために、よく知られている構造及びデバイスをブロック図の形態で示す。
【００２１】
概観
デイジー記述子の生成を改善するための技法が提供される。平滑化（畳み込み）配向マップの数を３から１に低減し、それによって、デイジー記述子を生成するために必要とされるメモリの量を低減する、修正デイジー記述子方法が提供される。具体的には、各配向マップから複数の平滑化配向マップを生成する代わりに、各スケール空間レベルの（即ち、対応する配向画像微分の非負値を含む）配向マップごとにただ１つの平滑化配向マップが生成される。次いで、デイジー記述子の生成においてより高いスケール空間の平滑化配向マップが使用される。これを行うために、スケール空間ピラミッドのより高いスケールは、通常ならば、元のデイジー記述子を生成する際に使用された配向マップごとの複数の平滑化配向マップによって取得されたであろう解像度を近似するように特に選択され得る。
【００２２】
さらに他の実装形態では、スケール空間ピラミッドのより高いスケールは、従来のデイジー記述子プロセスによって採用されたであろう解像度を顧慮せずに選択され得る。
【００２３】
スケール空間ピラミッドの複数のレベルにわたって修正デイジー記述子を生成することにより、そのような修正デイジー記述子がノイズに対してよりロバストにもなることに留意されたい。元のデイジー記述子アルゴリズムは、より細かい（現在のスケール）及びより粗い（より高いスケール）平滑化配向マップを導出するために単一のスケール空間レベルを使用し、それによってスケール空間ピラミッドの単一のレベルを利用する。対照的に、本手法は、ピラミッドのスケール空間レベルが高いほどノイズのより少ない勾配値が生成されるので、ノイズに対してより安定している。この理由は、より大きいカーネルを用いて画像を平滑化することにより、配向マップを生成する微分演算によって増幅され得る高周波ノイズが除去されるからである。
【００２４】
例示的な対象物認識プロセス
図１は、効率的に生成されたデイジー記述子を使用することによってクエリ画像上で対象物認識を実行するための機能段階を示すブロック図である。画像キャプチャ段階１０２において、クエリ画像１０８が撮像されるか又は他の方法で取得され得る。例えば、クエリ画像１０８は、デジタルキャプチャ画像を取得するために、一つ以上の画像センサ及び／又はアナログデジタル変換器を含み得る、撮像装置によって撮像され得る。画像センサ（例えば、電荷結合装置（ＣＣＤ）、相補型金属半導体（ＣＭＯＳ））は光を電子に変換し得る。電子はアナログ信号を形成し得、次いで、そのアナログ信号は、アナログデジタル変換器によってデジタル値に変換される。このようにして、画像Ｉ（ｘ，ｙ）を、例えば、対応する色、照度、及び／又は他の特性をもつ複数の画素として定義し得るデジタルフォーマットで画像１０８は撮像され得る。
【００２５】
次いで、画像処理段階１０４において、撮像された画像１０８は、対応するスケール空間（例えば、ガウススケール空間）を生成し（１２０）、特徴／ポイント検出を実行し（１２２）、スケール空間ごとに配向画像微分を取得し（１１９）、画像微分から配向マップ生成を実行し（１２１）、及び／又はスケール空間中の局所特徴記述子（例えば、修正デイジー記述子）生成を実行する（１２８）ことによって処理される。画像比較段階１０６において、取得された記述子１２８を使用して、既知の記述子のデータベース１３１との特徴マッチング１３０を実行する。記述子データベース１３１中の記述子は、スケール空間中の局所特徴記述子を抽出することによって同様に生成され得る。即ち、複数のテスト画像について、記述子が事前に生成され、記述子データベース１３１に記憶され得る。次いで、特徴マッチングが正しいことを確認するために、ポイントマッチングに対する幾何学的検証又は整合性検査１３２が（例えば、マッチングしている記述子に基づいて）実行されて、マッチング結果１３４を与え得る。このようにして、クエリ画像（又はそのクエリ画像中の対象物）が、ターゲット画像１０９（又は対象物）のデータベースと比較され及び／又はそれから識別され得る。
【００２６】
画像中の特徴検出を実行するために、スケール不変特徴変換（ＳＩＦＴ）を含む、幾つかのアルゴリズムが開発されている。画像中の特定の対象物の検出への第１のステップは、それの局所特徴に基づいてクエリ対象物を分類することである。その目的は、例えば、照明、画像ノイズ、回転、スケーリング、及び／又は視点の小さい変化に対して不変及び／又はロバストである特徴を識別し、選択することである。即ち、クエリ画像と比較ターゲット画像との間には照明、画像ノイズ、回転、スケール、及び／又は視点の差があるにもかかわらず、これらの２つの画像間のマッチングが発見されなければならない。
【００２７】
デイジー記述子は、高密度マッチング及びパッチ対応問題においてＳＩＦＴ記述子よりも良好で高速のマッチング性能を示している。ＳＩＦＴ記述子に勝るデイジー記述子の重要な利点は、デイジー記述子が、異なる解像度において配向微分の空間ビニングを使用することである。詳細には、デイジー記述子生成の際に、ビンがポイントからさらに離れて位置するほど、空間ビンサイズはより大きくなる。これにより、デイジー記述子は回転及びスケール変化に対してよりロバストになる。
【００２８】
例示的で典型的なデイジー記述子生成
デイジー記述子は、対象物の２つの視点間の対応を発見するために定義される。マッチングには２つの画像中のあらゆる画素が対応することが望まれるので、これを達成するための効率的な方法は、次いで比較され得る画像のための一つ以上の記述子を定義することである。スケール不変特徴変換（ＳＩＦＴ）並びに勾配位置及び配向ヒストグラム（ＧＬＯＨ）など、従来の記述子は、最初に画像の配向微分をとり、次いで、配向ヒストグラムを用いて指定された空間領域における配向微分を表すことによって記述子を構築する。この手順は、対応するヒストグラムビンのあらゆる画素勾配について３線補間（即ち、空間に対して２、及び配向に対して１）を計算することを必要とするので、計算量的に厳しい。デイジー記述子は、配向微分の線形補間の代わりに平滑化（例えば、ガウス平滑化）を使用することによってこの問題を克服する。さらに、デイジー記述子を生成するために使用される空間ビニングレイアウト（即ち、複数のレベルの平滑化配向マップにわたってポイントから出るより大きいビン）は、スケール、位置、及び配向変化に対するさらなるロバストネスを与える。
【００２９】
概して、典型的なデイジー記述子を生成するために、画像は、まず処理されて、スケール空間が取得される。スケール空間は処理されて、対応する配向微分（即ち、配向マップ）が取得される。複数の異なる平滑化係数を使用して各配向微分が平滑化されて、配向微分ごとに複数の平滑化（畳み込み）配向マップが取得される。次いで、複数の平滑化配向マップが使用されてデイジー記述子が生成される。
【００３０】
図２に、一例による、デイジー記述子を生成するために使用されるスケール空間と配向マップとの生成を示す。最初に、デジタル画像Ｉ（ｘ，ｙ）２０１が漸進的に平滑化／ぼかされて、スケール空間ピラミッド２０２が構築され得る。画像スケール空間ピラミッド２０２は、スケール空間が空間とスケールの両方においてサンプリングされる離散的表現である。ぼかし（平滑化）は、概して、スケールｃσにおいてぼかし／平滑化関数Ｇ（ｘ，ｙ，ｃiσ）（平滑化関数ｇciσとしても表される）を用いて元の画像Ｉ（ｘ，ｙ）を畳み込むことに関与し、従って、スケール空間Ｌ（ｘ，ｙ，ｃiσ）は次式のように定義される。
【数１】
0005602940.tif 000002
【００３１】
一例では、スケール空間ピラミッド２０２はガウススケール空間ピラミッドであり得る。従って、平滑化／ぼかし関数Ｇはガウスカーネルであり得、ｃiσは、画像Ｉ（ｘ，ｙ）をぼかすために使用されるガウス関数Ｇのスケーリング又は平滑化係数を示す。乗数ｃiが変化するにつれて（ｃi：ｃ0＜ｃ1＜ｃ2＜ｃ3＜ｃ4）、スケーリング係数ｃiσが変化し、画像Ｉ（ｘ，ｙ）の漸進的なぼかし／平滑化が得られる。ここで、標準偏差σ（ステップサイズ）は、スケーリング／平滑化係数（例えば、ガウスカーネルの幅）を取得する際に使用され、従って、スケーリング／平滑化係数ｃiσはσiによって表される（即ち、σi＝ｃiσ）。
【００３２】
ぼけた画像スケール空間Ｌを生成するために画像Ｉ（ｘ，ｙ）２０１が平滑化関数Ｇを用いて増分的に畳み込まれるとき、ぼけた画像スケール空間Ｌは、スケール空間において一定ファクタｃだけ分離される。ぼけた（平滑化）画像スケール空間Ｌの数が増加し、スケール空間ピラミッド２０２のために与えられる近似が連続的空間に近づくにつれて、２つの隣接するスケールは１つのスケールに近づく。一例では、画像スケール空間Ｌはオクターブによってグループ化され得、オクターブは、標準偏差σの値の倍化に対応し得る。さらに、乗数ｃi（例えば、ｃ0＜ｃ1＜ｃ2＜ｃ3＜ｃ4．．．）の値は、オクターブごとに固定数の画像スケール空間Ｌが取得されるように選択される。スケール空間及びスケールの比は、インパルス応答がピラミッド２０２の全てのレベルにおいて同じになるように、一定に保持され得る。一例では、スケーリングの各オクターブは、明示的な画像サイズ変更に対応し得る。従って、画像Ｉ（ｘ，ｙ）２０１が漸進的ぼかし／平滑化関数Ｇによってぼかされる／平滑化されるにつれて、画素の数は漸進的に低減される。スケール空間について、スケールレベルは、指数関数的に構成され得、例えば整数２のべき乗として構成され得る（例えば、σi＝２i、ｉ＝０、０．２５、０．５、０．７５、１、１．２５、１．５、１．７５、２、．．．、３、．．．）。他の例では、２の平方根又はさらにより小さいスケーリングステップなど、より近接したスケール間隔が必要とされ得る。別の例では、ピラミッドのスケール空間レベルは、２s/Sとして定義され得、ただし、Ｓは各オクターブの解像度を定義し、ｓは、正の整数ｋについて、１とｋとの間のスケールレベルである。例えば、上記の例ではＳ＝４であり、従って、ｋ＝｛１，２，３，４｝について、オクターブ０スケールレベル標準偏差はσi＝｛０，０．２５，０．５，０．７５，１｝である。
【００３３】
従来のデイジー記述子アルゴリズムでは、スケール空間ピラミッド２０２は実際に生成されないことに留意されたい。代わりに、画像２０１は単にぼかされ／平滑化され、デイジー記述子は画像２０１の平滑化バージョンから生成される。例えば、スケール空間ピラミッド２０２の他のレベルを生成することなしに平滑化画像２０４のみが生成され得る。
【数２】
0005602940.tif 000003
【００３４】
この例では、複数の画像微分２０３は複数の画像微分を含み得る。スケール空間２０４ごとに、異なる配向（例えば、Ｘ、Ｙ、Ｚ、Ｗ配向）に対応する、複数の画像微分δX２２１、δY２２３、δZ２２５、及びδW２２７が生成されることに留意されたい。
【００３５】
第３に、次いで、対応する配向マップ２０６を取得するために画像微分２０３が処理される。ここに示す例では、対応する配向マップを生成するために、画像微分の各値に（・）+演算子が適用される。例えば、…（・）+演算子は、任意の負値δをとり、そのδを次式のように０に設定し得る。
【数３】
0005602940.tif 000004
【００３６】
例えば、第１の画像微分δX２２１は、対応する配向マップγX２０８を有し、第２の画像微分δY２２３は、対応する配向マップγY２１０を有し、第３の画像微分δZ２２５は、対応する配向マップγZ２１２を有し、第４の画像微分δW２２７は、対応する配向マップγW２１３を有する。図３に、複数の画像微分２０３の画像微分２２１が、複数の勾配配向を有する画素をどのように含み得るかを示す。
【数４】
0005602940.tif 000005
【００３７】
（・）+演算子又は関数は、対応する画像微分の負の画素勾配値を０に設定するクリッピング関数であり得る。
【００３８】
図４、図５、及び図６に、配向マップがスケール空間レベルからどのように生成され得るかを示す。スケール空間レベル２０４は画像２０１の平滑化バージョンであり得る。
【数５】
0005602940.tif 000006
【００３９】
この例では、ｎ画素×ｍ画素の画像空間が使用され得る（例えば、ｎ＝ｍ及び／又はｎ≠ｍ）。
【００４０】
図４に、ｘ配向に沿った配向マップの生成を示す。複数の値δxijを有する対応する画像微分２２１を生成するために、スケール空間レベル２０４の画素勾配値βijにｘ配向に沿ってｘフィルタ［−１  ０  １］が適用される。ｘフィルタは、画像スケール空間レベル２０４の各行に沿ってｘ配向にシフト様式で適用され、ｘフィルタ［−１  ０  １］の「０」値を中心とする。例えば、画素勾配値β11では、ｘ配向値δx11は０ｘβ11＋１ｘβ12＝β12に等しい。同様に、画素勾配値β12では、ｘ配向値δx12は−１ｘβ11＋０ｘβ12＋１ｘβ13に等しい。同様に、画素勾配値β13では、ｘ配向値δx13は−１ｘβ12＋０ｘβ13＋１ｘβ14に等しい。画像微分２２１を生成するために、このプロセスは、スケール空間レベル２０４の各行にわたってｘフィルタを移動することによって繰り返される。
【００４１】
次いで、複数の値γxを有する対応する配向マップ２０８を取得するために、画像微分２２１の各値δxに（・）+演算子が適用される。（・）+演算子を使用して各配向マップ値γを計算する際に、配向に沿った正の微分のみが使用されることに留意されたい。
【数６】
0005602940.tif 000007
【００４２】
例えば、δ12＝−４である場合、γ12＝０である。一般に、特定の画素勾配値δij＜０である場合、γij＝０である。従って、画素勾配値δij＞０のみが配向値の計算に寄与する。
【００４３】
図５に、ｙ配向に沿った配向マップの生成を示す。
【数７】
0005602940.tif 000008
【００４４】
ｙフィルタは、スケール空間レベル２０４の各列に沿ってｙ配向にシフト様式で適用され、ｙフィルタ［−１  ０  １］の「０」値を中心とする。例えば、画素勾配値β11では、ｙ配向値δy11は０ｘβ11＋１ｘβ21＝β21に等しい。同様に、画素勾配値β21では、ｙ配向値δy21は−１ｘβ11＋０ｘβ21＋１ｘβ31に等しい。同様に、画素勾配値β31では、ｙ配向値δy31は−１ｘβ21＋０ｘβ31＋１ｘβ41に等しい。画像微分２２３を生成するために、このプロセスは、スケール空間レベル２０４の各列にわたってｙフィルタを移動することによって繰り返される。次いで、複数の値γyを有する対応する配向マップ２１０を取得するために、画像微分２２３の各値δyに（・）+演算子が適用される。
【００４５】
一例では、ｘ配向は０度であり得、ｙ配向は９０度であり得る。異なる配向について複数の追加の画像微分が生成され得る。例えば、０度画像微分の負数をとることによって１８０度配向画像微分が取得され得る。同様に、９０度画像微分の負数をとることによって２７０度配向画像微分が取得され得る。このようにして、４つの配向マップが取得され得る（即ち、０度、９０度、１８０度、及び２７０度）。さらに他の実装形態では、４５度、１３５度、２２５度、及び４１５度など、他の配向について追加の配向マップが取得され得る。
【００４６】
図６に、ｚ配向に沿った配向マップの生成を示す。そのようなｚ配向は、例えば、ｘ配向とｙ配向との間にあり得る。幾つかの実装形態では、そのようなｚ配向マップ２１２は、フィルタ（例えば、［−１  ０  １］）を対角線方向にシフトすることによって生成され得る。しかしながら、代替的に、ｚ配向マップ２１２を取得するためにステアラブルフィルタ６０２が使用され得る。ステアラブルフィルタ６０２は、ｚ方向に沿って画像微分２２５を取得するために、２つの他の画像微分（例えば、ｘ配向画像微分２２１及びｙ配向画像微分２２３）を線形的に結合し得る。具体的には、そのような線形結合は、対応するｚ配向画像微分値δzを取得するために、対応する配向画像微分値δxとδyとを結合する。ｘ配向画像微分２２１とｙ配向画像微分２２３の特定の線形結合は、探索されている特定の画像微分配向に依存し得る。例えば、４５度画像微分配向が探索されている場合、対応する微分値δzijを取得するために、ｘ配向画像微分２２１の画像微分値δxijとｙ配向画像微分２２３の画像微分値δyijとが結合され得る。このようにして、４５度の様々な倍数が取得され得る。同様に、（１５度又は３０度の倍数などの）他の配向マップが取得され得る。概して、角度φについて、対応する画像微分値は次式ように取得され得る。
【数８】
0005602940.tif 000009
【００４７】
前述のように、次いで、複数の値γzを有する対応する配向マップ２１２を取得するために、画像微分２２５の各値δzに（・）+演算子が適用される。
【００４８】
従って、複数の配向マップが取得され得、配向マップの数は、探索される精度、利用可能な処理リソース、及び／又は利用可能なメモリリソースの関数であり得る。例えば、様々な実装形態は、４個、８個、１２個、１６個、２０個、２４個などの配向マップを使用し得る。幾つかの実装形態では、配向マップ間の角度は同じであり得る（例えば、９０度、４５度、３０度、２０度、１５度、１０度など）。
【００４９】
再び図２を参照すると、１つの手法によれば、スケール空間レベル２０４ごとに複数の配向マップ２０６が生成された後、
【数９】
0005602940.tif 000010
【数１０】
0005602940.tif 000011
【数１１】
0005602940.tif 000012
【数１２】
0005602940.tif 000013
【００５０】
平滑化（畳み込み）配向マップ２１４、２１６、及び２１８中の各画素は、ガウス重みをもつ配向微分の空間プーリングに対応する。Ｚ配向のこの例では、配向マップ２１２ごとに３つの平滑化配向マップ２１４、２１６、及び２１８が生成される。畳み込み演算は、配向マップの値をスケーリングする／ぼかす平滑化係数αiを効果的に適用する。
【数１３】
0005602940.tif 000014
【００５１】
この例では、そのような平滑化ファクタは、第１のスケーリングファクタσj（例えば、対応するスケール空間のスケーリングファクタ）と、第２のスケーリングファクタαi（例えば、平滑化配向マップのレベルごとに変化するスケーリングファクタ）との積として表され得る。同様の様式で、平滑化配向マップは、異なる配向（例えば、配向Ｘ、Ｙ、Ｚ、Ｗ、．．．）を有する対応する配向マップごとに生成され得る。
【数１４】
0005602940.tif 000015
【００５２】
図７に、デイジー記述子の典型的な生成を示す。
【数１５】
0005602940.tif 000016
【数１６】
0005602940.tif 000017
【００５３】
スケール空間２０４中の識別ポイント７０２（例えば、キーポイント、サンプルポイント、画素など）について、平滑化配向マップ２１５、２１７、及び２１９をばらばらにサンプリングすることによってデイジー記述子が取得され得る。これは、ポイント７０２の中心上に分散された空間プーリング構成（例えば、ガウスプーリング）によって達成され得る。この例では、空間プーリング構成は、異なる平滑化配向マップ２１５、２１７、及び２１９上の複数の同心リング７０４、７０６、及び７０８として定義され得る。同心リング７０４、７０６、及び７０８は、識別ポイント７０２に対応するサンプルポイント７０３に対して同心である。各同心リング７０４、７０６、及び７０８は、リングの外周に沿った複数のばらばらにサンプリングされたポイント７１０、７１２、及び７１４を含み得る。各ばらばらにサンプリングされたポイント７１０、７１２、及び７１４は、セル７１６、７１８、及び７２０（即ち、円）の中心として働き得、サンプルポイントがポイント７０２からさらに離れて移動するにつれてセルサイズ（即ち、半径）がサイズ増加する。一例では、空間プーリング構成は、３つの同心リング７０４、７０６、及び７０８に沿って２４個のポイントを含み得、４５度だけ分離されたリング７０４、７０６、及び７０８ごとに８つのサンプルポイント（例えば、従って８つのセル）がある。（ｘ）マークは、デイジー記述子を構築するためのポイント（ｏ）７０２の周りのサンプリングポイント又は位置に対応する。この演算は配向ごとに行われ、配向勾配ヒストグラム（ＨＯＧ：histogram of oriented gradients）をもたらす。次いで、デイジー記述子（例えば、配向ヒストグラム）が、サンプルポイントの各々に関する情報を含めることによって構築され得る。
【００５４】
図７において、各円は、半径が平滑化係数の標準偏差に比例する領域を表し得、「ｘ」符号は、平滑化配向マップ中の各円の中心にあるサンプリングポイント又は画素位置を表す。これらの円の領域を重複させることによって、領域間の平滑な遷移が達成され得、並進、回転及びスケール誤差に対するある程度のロバストネスが獲得され得る。
【００５５】
図２〜図７の平滑化配向マップによって示すようにポイント７０２及び対応するサンプルポイントを定義しているので、デイジー記述子が構築され得る。画像座標（ｕ0，ｖ0）に位置するポイント７０２のヒストグラムｈΣ（ｕ，ｖ）は次式のようにベクトルとして表され得る。
【数１７】
0005602940.tif 000018
【００５６】
あるポイントについてのデイジー記述子は、そのポイントの位置を中心とする同心円上にあり、平滑化の量が円の半径に比例し得る、平滑化配向マップからの値から作られたベクトルによって定義され得る。従って、位置（ｕ，ｖ）におけるポイントについてのデイジー記述子は次式として与えられ得る。
【数１８】
0005602940.tif 000019
【００５７】
但し、ｌj（ｕ，ｖ，Ｒi）は、ｊによって与えられる方向／配向（例えば、４方向、８方向など）における位置（ｕ，ｖ）におけるポイント７０２からの距離がＲjである画素位置である。ここで、下付き「Ｖ」は、単一の平滑化配向マップレベルにおけるヒストグラムの数を表す。図７における例では、これはレイヤごとに８つのヒストグラムである。式４Ａ、式４Ｂ、式４Ｃ、及び式５は、３つの平滑化（畳み込み）配向マップレベルが使用されることを仮定しているが、他の実装形態では追加の数のレベルが使用され得ることに留意されたい。
【００５８】
図７に示すように平滑化配向マップをばらばらにサンプリングすることは、ＳＩＦＴと比較して計算時間を節約させるが、デイジー記述子を記憶するために必要とされるメモリのサイズを増加させる。特に、スケール空間ピラミッド２０２上で検出されたポイントではメモリ複雑さがより不良になる。Ｍ×Ｎ画像では、ＳＩＦＴ記述子と比較して、デイジー記述子のために２４×Ｍ×Ｎの合計追加メモリが必要とされる。この理由は、デイジー記述子を計算するために、スケール空間ピラミッド２０２のスケールレベルごとに２４個の追加の平滑化（畳み込み）配向マップ（即ち、３つの平滑化配向マップスケール×平滑化配向マップ当たりの８つの配向）が必要とされるからである。メモリ複雑さは、Ｓスケールレベルをもつスケール空間では、さらに２４×Ｍ×Ｎ×Ｓに増加する。従って、デイジー記述子を生成するために必要とされるメモリのサイズを低減するための方法が有益であろう。
【００５９】
一態様によれば、スケール不変デイジー記述子抽出のメモリ複雑さは、すでに構築されているガウススケール空間を使用することによって８×Ｍ×Ｎ×Ｓに低減され得る。デイジー記述子のパラメータは、スケール空間ピラミッドの複数のスケール空間レベルからデイジー記述子を抽出するように調整される。
【００６０】
例示的な改善されたスケール空間上デイジー記述子
デイジー記述子を生成するために必要とされるメモリのサイズのそのような低減を達成するための１つの方法は、配向マップ２０８、２１０、２１２及び２１３の各々について複数（例えば、３つ）の平滑化（畳み込み）配向マップを計算することを回避することである。
【数１９】
0005602940.tif 000020
【数２０】
0005602940.tif 000021
【数２１】
0005602940.tif 000022
【００６１】
式６、式７、及び式８において、式１の平滑化フィルタｇΣ1は、全体的な又は得られた平滑化／スケーリングを表し得る。
【数２２】
0005602940.tif 000023
【００６２】
しかしながら、（スケール空間ピラミッドの）スケール空間のスケーリング係数σjを適切に選択することによって、デイジー記述子は、配向マップごとに複数の平滑化配向マップを計算する必要なしに、スケール空間ピラミッドのすでに計算されているスケール空間を使用して計算され得る。
【００６３】
図８に、配向マップごとに複数の平滑化配向マップを生成する必要を回避するより効率的な一例による、修正デイジー記述子を生成するために使用されるスケール空間と配向マップとの生成を示す。画像Ｉ（ｘ，ｙ）８０１が、（異なるカーネル幅において）平滑化カーネルを用いて畳み込まれて、スケール空間ピラミッド８０２が取得される。図２の場合のように、ピラミッド８０２の各スケール空間レベル８０４の配向微分が生成されて、複数の画像微分δx８２１、δy８２３、δz８２５、及びδw８２７が取得される。次いで、画像微分ごとに、図２の場合のように、対応する配向マップが取得される。
【００６４】
画像の微分をとり、平滑化することは、平滑化し、次いで微分をとることに等価であることがわかる。この性質を使用して、後続の平滑化配向マップが配向マップごとに３つから１つに低減され得るような方法で画像Ｉ（ｘ，ｙ）８０１の平滑化を実行することによって図２及び図７に示すデイジー記述子プロセスを簡略化する。配向マップを取得するために、画像微分は非線形（．）+関数を通過されることに留意されたい。（典型的なデイジーの場合のような）平滑化の前の配向マップは、平滑化の後の配向マップ、及び図８に示す修正デイジー記述子の場合のような別の平滑化と厳密に同じではないが、実際には、これらの手法は両方とも同様の記述子を生成することがわかっている。従って、スケール空間ピラミッド８０２のスケール空間レベルのスケーリング係数又は平滑化係数は、デイジー記述子が複数のスケール空間レベルの平滑化配向マップに基づくように特に選択される。
【００６５】
画像Ｉ（ｘ，ｙ）８０１が１次元画像である場合、スケール空間カーネルｇσを用いた画像の微分の畳み込みは次式によって与えられる。
【数２３】
0005602940.tif 000024
【００６６】
このプロセスは、配向マップごとに単一の平滑化配向マップが生成されるようにスケール空間ピラミッド８０２の全てのスケール空間レベルについて繰り返される。
【数２４】
0005602940.tif 000025
【数２５】
0005602940.tif 000026
【００６７】
ここで、「得られた平滑化」及び／又は「全体的な平滑化」という用語は、平滑化配向マップのスケーリング／ぼかしの量を指し得る。
【数２６】
0005602940.tif 000027
【００６８】
従って、図８のスケール空間上の修正デイジー記述子では、（スケール空間ピラミッドのための）１次平滑化係数σ及び／又は（平滑化配向マップを生成するために使用される）２次平滑化係数αが知られているので、第２及び第３の平滑化配向マップをそこから取得すべき（スケール空間ピラミッド８０２の）特定のより高いスケール空間が選択されて、図２の平滑化とほぼ等価な全体的な平滑化が与えられ得る。例えば、２次平滑化係数αは、スケール空間の全てのレベルについて定数（α＝α1）であり得る。従って、達成されるスケーリング／平滑化はスケーリング空間レベルに比例する。平滑化カーネル標準偏差α1σiをスケール空間レベルに比例させることは、スケール不変性を達成するのに役立つ。
【００６９】
図８から、第１のスケール空間８０４は、第１の平滑化／スケーリング係数σ1を使用して生成されることが諒解できよう。図２の場合のように、複数の画像微分８０３が生成され、各スケール空間レベル８０４は、異なる配向に関連する複数の対応する画像微分δx８２１、δy８２３、δz８２５、及びδw８２７を有し得る。次いで、画像微分の値の各々に（・）+演算子を適用することによって第１の複数の配向マップ８０６が取得され得る。
【数２７】
0005602940.tif 000028
【００７０】
第２のスケール空間８０５は、第３の平滑化／スケーリング係数σiを使用して生成され得、ただし、この例ではσi＝σ2である。第２のスケール空間８０５の配向微分をとることによって、第２の複数の画像微分δ’x、δ’y、δ’z、及びδ’w８１１が取得される。次いで、第２の複数の画像微分δ’x、δ’y、δ’z、及びδ’w８１１に（）+演算子を適用することによって第２の複数の配向マップ８１５が取得され得る。
【数２８】
0005602940.tif 000029
【００７１】
全てのスケール空間レベルにおいて同じ平滑化係数が使用されるように、第４の平滑化係数αjは第２の平滑化係数α1と同じであり得る（例えば、αj＝α1）。他の実装形態では、第４の平滑化係数αjはあらゆるスケール空間レベルについて異なり得る（例えば、αj＝α2又はαj＝α3）。
【数２９】
0005602940.tif 000030
【００７２】
同様に、スケール空間ピラミッド８０２のより高いスケール空間に関連する複数の配向マップ中の配向マップごとに、対応する平滑化配向マップが取得され得る。
【数３０】
0005602940.tif 000031
【００７３】
第５の平滑化係数αhは、第１の平滑化係数α1と同じであり得るか（例えば、αh＝α1）、或いはあらゆるスケール空間レベルについて異なり得る（例えば、αh＝α4又はαh＝α5）。
【数３１】
0005602940.tif 000032
【数３２】
0005602940.tif 000033
【００７４】
図８に示す実装形態は、デイジー記述子を生成すべき近似的畳み込みスケール空間平滑化を与えるスケール空間ピラミッド８０２のより高いレベルにあるスケール空間レベルを特に選択する。
【００７５】
スケール空間ピラミッド８０２からより高いスケール空間を適切に選択するために、平滑化配向マップは次式として表され得ることがわかる。
【数３３】
0005602940.tif 000034
【００７６】
上式で、σ1及びσ2は、スケール空間ピラミッドの異なるスケール空間のためのスケーリング／平滑化係数であり、σ2は、σ1よりも大きい平滑化／スケーリングを与える。同様に、α1及びα2は、２つの異なる平滑化配向マップを生成するために使用されるスケーリング／平滑化係数であり、α2は、α1よりも大きい平滑化／スケーリングを与える。
【００７７】
記述子を構築するために、（・）+演算子を適用して、対応する画像微分から負成分をクリッピングすることによって平滑化配向マップが取得される。
【数３４】
0005602940.tif 000035
【００７８】
実際には、微分が画像のより平滑なバージョン（即ち、より高いスケール）に適用されるほど、この近似はよりロバストな記述子を生成する。
【数３５】
0005602940.tif 000036
【００７９】
従って、式１３及び式１４は、次のように平滑化カーネルパラメータ（例えば、スケーリング係数σ及びα）を調整することによって求められ得る。
【数３６】
0005602940.tif 000037
【００８０】
ここで、λ1は、スケール空間ピラミッドの２つのスケール空間レベルの平滑化係数σ2とσ1との間の比に対応する。式１４．１及び式１８から、第１のスケール空間の第１の平滑化配向マップについて、スケール空間ピラミッド上の第１のスケール空間から第２のスケール空間にλ1レベルだけ上がることによって第２の平滑化配向マップが選択され得ることが諒解できよう。
【数３７】
0005602940.tif 000038
【００８１】
図８に示す例では、スケール空間ピラミッド８０２の全てのレベルの配向マップを平滑化するために同じスケーリング係数α1が使用され得ることに留意されたい。
【００８２】
λ2に基づいてα1とα3との間の関係を定義するために同じプロシージャが使用され得る。即ち、α1／3＝λ2である場合、
【数３８】
0005602940.tif 000039
【００８３】
図９に、デイジー記述子が、スケール空間ピラミッドの複数のレベルを使用することによってどのように生成され得るかを示す。
【数３９】
0005602940.tif 000040
【００８４】
各同心リング９０４、９０６、及び９０８は、リングの外周に沿った複数のばらばらにサンプリングされたポイント９１０、９１２、及び９１４を含み得る。各ばらばらにサンプリングされたポイント９１０、９１２、及び９１４は、セル９１６、９１８、及び９２０（即ち、円）の中心として働き得、サンプルポイントがポイント９０２からさらに離れて移動するにつれてセルサイズ（即ち、半径）がサイズ増加する。一例では、空間プーリング構成は、３つの同心リング９０４、９０６、及び９０８に沿って２４個のポイントを含み得、４５度だけ分離されたリング９０４、９０６、及び９０８ごとに８つのサンプルポイント（例えば、従って８つのセル）がある。
【数４０】
0005602940.tif 000041
【００８５】
この演算は配向ごとに行われ、配向勾配ヒストグラム（ＨＯＧ）をもたらす。次いで、デイジー記述子（例えば、配向ヒストグラム）が、サンプルポイントの各々に関する情報を含めることによって構築され得る。例えば、画像座標（ｕ0，ｖ0）に位置するポイント９０２のヒストグラムｈΣ（ｕ，ｖ）は次式のようにベクトルとして表され得る。
【数４１】
0005602940.tif 000042
【００８６】
ポイントについてのデイジー記述子は、ポイント９０２の位置を中心とする同心円上にあり、平滑化の量が円の半径に比例し得る、平滑化配向マップからの値から作られたベクトルによって定義され得る。従って、位置（ｕ，ｖ）におけるポイントについてのデイジー記述子は次式として与えられ得る。
【数４２】
0005602940.tif 000043
【００８７】
但し、ｌj（ｕ，ｖ，Ｒi）は、ｊによって与えられる方向／配向（例えば、４方向、８方向など）における位置（ｕ，ｖ）におけるポイント９０２からの距離がＲjである画素位置である。ここで、下付き「Ｖ」は、単一の平滑化配向マップレベルにおけるヒストグラムの数を表す。図９における例では、これはレイヤごとに８つのヒストグラムである。式２１Ａ、式２１Ｂ、式２１Ｃ、及び式２２は、３つの平滑化配向マップレベルが使用されることを仮定しているが、他の実装形態では追加の数のレベルが使用され得ることに留意されたい。
【００８８】
一例では、ピラミッド８０２のスケール空間レベルは２k/Sとして定義され得、ただし、Ｓは各オクターブの解像度（即ち、オクターブ当たりのスケールレベルの数）を定義し、ｓはスケール空間ピラミッド８０２内のスケール空間レベルであり、その場合、λ1は、何らかの正の整数ｋについて、２k/Sから選択され得る。例えば、図８では、オクターブ解像度Ｓはｉ＋１（即ち、スケールレベル０からｉまで）であり、ただし、「ｉ」は整数（例えば、２、３、４、５、６、７など）であるが、スケールレベルｓは、１とｒ＋１（即ち、ピラミッド８０２中で最も高いスケールレベル）との間にあり得る。ピラミッドスケール空間レベルを定義する他の方法が使用され得ることに留意されたい。
【００８９】
他のスケール空間の平滑化配向マップを再利用することによってデイジー記述子を生成する手法は、メモリ記憶空間の節約だけでなく、精度の改善をも達成する。この手法の１つの特徴は、平滑化のどのレベルが微分演算子に適用されたかを判断することである。この手法では、微分演算子は、ガウスピラミッドのより高いスケールレベルにおいて画像に適用される。従って、この手法はノイズに対してよりロバストである。この理由は、より大きいカーネルを用いて画像を平滑化することにより、微分演算によって増幅され得る高周波ノイズが除去されるからである。このことは、全てのよく知られているエッジ検出アルゴリズムによって使用されている。
【００９０】
典型的なデイジー記述子と修正デイジー記述子との間の例示的な比較
図１０に、スケール空間上の修正デイジー記述子と比較した、典型的なデイジー記述子の生成の比較を示す。画像解像度がピラミッド１００２のより低いスケールからより高いスケールに低下するように、様々なスケーリング係数に従って画像をぼかす／平滑化することによって、スケール空間ピラミッド１００２が生成される。第１のスケール空間１００６の配向微分をとることによって（第１のスケーリング係数σ1によって生成された）第１のスケール空間１００６におけるポイント１００４についての典型的なデイジー記述子が生成されて、配向マップのセット１００８が取得され得る。配向マップのセット１００８は、異なる配向についての複数の配向マップを備える。次いで、配向マップのセット１００８は、複数の異なるスケーリング／平滑化係数を用いて畳み込むことによって平滑化されて、デイジー記述子の３つのレベルが取得される。
【数４３】
0005602940.tif 000044
【数４４】
0005602940.tif 000045
【００９１】
各同心リング１０２０、１０２２、及び１０２４は、リングの外周に沿った複数のばらばらにサンプリングされたポイントを含み得る。各ばらばらにサンプリングされたポイントは、セル（即ち、円）の中心として働き得、サンプルポイントがポイント１００４からさらに離れて移動するにつれてセルサイズ（即ち、半径）がサイズ増加する。この例では、（それぞれ平滑化配向マップ１０１４、１０１６、及び１０１８のための）３つの異なる平滑化係数α1、α2、及びα3は、値α1＝２．５、α2＝５．０、及びα3＝７．５を有し得る。セル（即ち、円）の各々の半径はその平滑化配向マップの平滑化係数に比例し得る。例えば、第１の平滑化配向マップ１０１４では、各セル又は円の半径Ｒ1はＲ1＝２．５であり得、平滑化係数α1＝２．５で１対１の比例関係がある。同様に、第２の平滑化配向マップ１０１６では、各セル又は円の半径Ｒ2はＲ2＝５．０であり得、平滑化係数α2＝５．０で１対１の比例関係がある。同様に、第３の平滑化配向マップ１０１８では、各セル又は円の半径Ｒ3はＲ3＝７．５であり得、平滑化係数α3＝７．５で１対１の比例関係がある。この例では、半径の合計Ｒ1＋Ｒ2＋Ｒ3＝１５．０画素であることに留意されたい。次いで、式３、式４Ａ、式４Ｂ、式４Ｃ、及び式５に従ってデイジー記述子が生成され得る。典型的なデイジー記述子の構築により、Ｍ×Ｎ画素の画像、Ｓレベルのスケール空間ピラミッド、及び８つの配向では、８つの配向微分（例えば、配向マップ）について３つの平滑化配向マップのための情報を記憶するために２４×Ｍ×Ｎ×Ｓのメモリが必要となる。
【００９２】
デイジー記述子を生成するための典型的な方法と比較して、本手法は、スケール空間上でデイジー記述子を生成するためにスケール空間ピラミッド１００２の複数のレベルを使用する。
【数４５】
0005602940.tif 000046
【数４６】
0005602940.tif 000047
【００９３】
第１の平滑化配向マップ１０１４及び第２の平滑化配向マップ１０２６を生成するために同じ平滑化係数α1が使用されるので、比λ1＝σ2／σ1を満たす第２のスケール空間１０１０の選択は、対応する第２の平滑化配向マップ１０２６において同じ又はほぼ同じ全体的な平滑化を達成する効果を有することになる。比λ1は、修正デイジー記述子のための所望の空間サンプリングを達成するか又は典型的なデイジー記述子にほぼマッチングするようにあらかじめ決定されていることがある。従って、比λ1と平滑化係数σ1とがわかれば、第２のスケール空間１０１０は、比λ1を満たすそれの対応する平滑化係数σ2に基づいて選択され得る。スケール空間ピラミッド１０１０についてスケール空間はあらかじめ決定され得るので、この比λ1を最も厳密に満たす第２のスケール空間１０１０が選択される。細かく離間したスケール空間を用いてスケール空間ピラミッド１００２を構築することは、比λ1を満たす平滑化係数σ2を有する第２のスケール空間１０１０を選択可能になるのを助けることに留意されたい。
【数４７】
0005602940.tif 000048
【００９４】
第１の平滑化配向マップ１０１４及び第３の平滑化配向マップ１０２８を生成するために同じ平滑化係数α1が使用されるので、比λ2＝σ3／σ1を満たす第２のスケール空間１０１６の選択は、対応する第３の平滑化配向マップ１０２８において同じ又はほぼ同じ全体的な平滑化を達成する効果を有することになる。比λ2は、修正デイジー記述子のための所望の空間サンプリングを達成するか又は典型的なデイジー記述子にほぼマッチングするようにあらかじめ決定されていることがある。従って、比λ2と平滑化係数σ1とがわかれば、第３のスケール空間１０１６は、比λ2を満たすそれの対応する平滑化係数σ3に基づいて選択され得る。スケール空間ピラミッド１０１０についてスケール空間はあらかじめ決定され得るので、この比λ2を最も厳密に満たす第３のスケール空間１０１６が選択される。
【数４８】
0005602940.tif 000049
【００９５】
この例では、第１の平滑化配向マップ１０１４では、各セル又は円の半径Ｒ1はＲ1＝α1＝２．５であり得、平滑化係数α1＝２．５で１対１の比例関係がある。ここで、（第２の平滑化配向マップ１０２６及び第３の平滑化配向マップ１０２８の）半径Ｒ’２及びＲ’３は、第２のスケール空間１０１０及び第３のスケール空間１０１６の選択の結果として達成される全体的な平滑化に依存する。
【数４９】
0005602940.tif 000050
【００９６】
この例では、半径の合計Ｒ1＋Ｒ’2＋Ｒ’3＝１６．２７画素であることに留意されたい。次いで、式２０、式２１Ａ、式２１Ｂ、式２１Ｃ、及び式２２に従ってデイジー記述子が生成され得る。この修正デイジー記述子の構築により、Ｍ×Ｎ画素の画像、Ｓレベルのスケール空間ピラミッド、及び８つの配向では、８つの配向微分（例えば、配向マップ）について平滑化配向マップのための情報を記憶するために８×Ｍ×Ｎ×Ｓのメモリが必要となる。
【００９７】
例示的な記述子生成デバイス
図１１は、複数のスケール空間レベルにわたって記述子を生成する記述子生成デバイスの一例を示すブロック図である。記述子生成デバイス１１００は、処理回路１１０２、撮像装置１１０６、及び／又は記憶装置１１０８を含み得る。撮像装置１１０６は、例えば、クエリ画像をキャプチャすることができるデジタルカメラ、一つ以上のデジタル画像を記憶する記憶メディア、及び／又は一つ以上のデジタル画像を与える通信インターフェースであり得る。
【００９８】
記憶装置１１０８は、記述子データベース１１１８、特徴／ポイント検出演算のセット１１１５、画像微分演算のセット１１１９、配向マップ生成演算のセット１１１１、配向マップ平滑化演算のセット１１１８、及び／又はスケール空間演算上記述子生成のセット１１１７を一時的又は永続的に記憶するように働き得る。
【００９９】
処理回路１１０２は、画像を処理し、その画像及び／又はその画像内の特徴を識別する一つ以上の記述子を生成するように適応され得る。この目的のために、処理回路１１０２はまた、スケール空間生成回路１１１０、特徴／ポイント検出回路１１１４、画像微分生成回路１１２１、配向マップ生成回路１１１２、配向マップ平滑化回路１１１３、及び／又はスケール空間上記述子生成回路（descriptor generation over scale space circuit）１１１６を含むか又は実装し得る。処理回路１１０２は、図８〜図１０及び図１２で説明する一つ以上の特徴及び／又は方法を実装し得る。一例では、処理回路１１０２は、記憶装置中の様々なモジュールに記憶された演算を単に実装し得る。別の例では、処理回路１１０２内の回路の各々は、記憶装置１１０８内に記憶された対応するモジュール中の演算を行うように適応され得る。
【０１００】
スケール空間生成回路１１１０は、例えば、図８に示すように、複数の異なるスケール空間を生成するためにぼかし／平滑化関数を用いて画像を畳み込むように働き得る。一例では、スケール空間生成回路１１１０は、ガウススケール空間ピラミッドを生成するように働き得る。特徴／ポイント検出回路１１１４は、画像のための各スケール空間において一部又は全部のポイント又は特徴を識別するように働き得る。画像導出生成回路１１２１は、スケール空間の各々について複数の配向微分を生成するように働き得る。配向マップ生成回路１１１２は、画像微分ごとに配向マップを生成するように働き得る。次いで、配向マップ平滑化回路１１１３は、配向マップの各々を（例えば、畳み込み演算によって）平滑化し得る。スケール空間上記述子生成回路１１１６は、複数の異なるスケール空間のための複数の平滑化配向マップ上のサンプリングポイントを使用することによってポイントについての記述子を生成する。例えば、スケール空間上記述子生成回路１１１６は、図８〜図１０及び図１２に示す修正デイジー記述子を生成し得る。
【０１０１】
図１２は、複数のスケール空間レベルにわたって局所特徴記述子を生成するための方法を示す流れ図である。この方法は、ポイントについての局所特徴記述子を生成するために、図１１の記述子生成デバイス１１００を含む様々なデバイスにおいて実装され得る。複数のスケール空間Ｌ（σ1）、Ｌ（σ2）、．．．Ｌ（σn）を取得するために画像Ｉ（ｘ，ｙ）を漸進的に平滑化する（１２０２）。
【０１０２】
複数のスケール空間からの第１のスケール空間内のポイントを識別し得る（１２０４）。ポイントは、複数のスケール空間内の位置のサブセットからのサンプルポイントであり得る。位置のサブセットの選択は特定の実装形態に依存し得る。一例では、位置のサブセットは、対象物についての予想パターンに基づいて選択され得る。例えば、顔検出適用例では、これらの位置は、顔の中心などの基準位置に対する眼、口、鼻の位置に対応するであろう。別の例では、位置のサブセットは、画像内の識別キーポイントに基づいて選択され得、キーポイントは、回転及びスケール変化に対してロバストであると識別されているポイントである。例えば、画像からの形状抽出を実装するために、位置は形状の輪郭からサンプリングされたポイントに対応し得る。
【０１０３】
複数のスケール空間の各々について配向画像微分を取得する（１２０６）。
【数５０】
0005602940.tif 000051
【０１０４】
例えば、（例えば、配向マップにクリッピング関数／演算子（・）＋を適用することによって）対応する画像微分の負値を０に設定することによって複数の配向マップの各々を取得し得る。
【数５１】
0005602940.tif 000052
【０１０５】
次いで、ポイントのための局所特徴記述子を生成するために、複数のスケール空間からの２つ以上のスケール空間に対応する複数の平滑化配向マップをばらばらにサンプリングする（１２１２）。２つ以上のスケール空間は、第１のスケール空間と、第１のスケール空間よりも低い解像度の一つ以上の追加のスケール空間とを含み得る。局所特徴記述子は、ポイントの中心上に分散されたサンプルポイントの空間プーリングによって定義されたカーネルプーリング構成を有し得る。各スケール空間のための複数の配向マップは、複数の異なる配向（例えば、配向／次元Ｘ、Ｙ、Ｚ、及びＷ）のための配向マップを含み得る。
【数５２】
0005602940.tif 000053
【０１０６】
複数の配向勾配ヒストグラムは、複数の平滑化配向マップのばらばらのサンプリングから構築され得、局所特徴記述子は複数のヒストグラムを備える。
【０１０７】
一例では、複数の平滑化配向マップをばらばらにサンプリングすることは、（ａ）第１の平滑化配向マップ上の第１の複数のポイントをサンプリングすることであって、第１の複数のポイントが、ポイントの位置と同心の第１のリングに配置された、サンプリングすること、（ｂ）第２の平滑化配向マップ上の第２の複数のポイントをサンプリングすることであって、第２の複数のポイントが、ポイントの位置と同心の第２のリングに配置され、第２の平滑化配向マップが、第１のスケール空間よりも低い解像度の第２のスケール空間に対応する、サンプリングすること、及び／又は（ｃ）第３の平滑化配向マップ上の第３の複数のポイントをサンプリングすることであって、第３の複数のポイントが、ポイントの位置と同心の第３のリングに配置され、第３の平滑化配向マップが、第１のスケール空間よりも低い解像度の第３のスケール空間に対応する、サンプリングすることを含む。第２のリングは、第１のリングの第１の半径よりも大きい第２の半径を有し得、第３のリングは、第２のリングの第２の半径よりも大きい第３の半径を有し得る。
【０１０８】
１つの事例によれば、複数の配向マップは、同じ平滑化係数を使用して平滑化され得、第１のスケール空間は、２つ以上のスケール空間のうちの１つであり得、第２のスケール空間は、第１のスケール空間に対して所望の平滑化を達成するように選択され得る。
【０１０９】
例示的なモバイルデバイス
図１３は、スケール空間の複数のレベルにわたって生成された局所記述子を使用して画像又は対象物認識のために画像処理を実行するように適応された例示的なモバイルデバイスを示すブロック図である。モバイルデバイス１３００は、撮像装置１３０４に結合された処理回路１３０２と、ワイヤレス通信インターフェース１３１０と、記憶装置１３０８とを含み得る。撮像装置１３０４（例えば、デジタルカメラ）は、注目するクエリ画像１３０６をキャプチャし、撮像されたクエリ画像を処理回路１３０２に供給するように適応され得る。
【０１１０】
記憶装置１３０８（例えば、揮発性及び／又は不揮発性メモリ）は、画像のための画像スケール空間１３１６及び／又はスケール空間上で局所特徴記述子を生成するための演算１３１４を記憶し得る。これらの演算は、例えば、スケール空間生成演算１３２１（例えば、画像のスケール空間を取得するために様々な平滑化係数／関数に従って画像を漸進的にぼかす演算）、配向画像微分演算１３２７（例えば、特定のスケール空間レベルから複数の配向微分を生成する演算）、配向マップ生成演算１３２３（例えば、配向マップを取得するために画像微分の画素勾配値にクリッピング関数（．）+を適用する演算）、平滑化（畳み込み）配向マップ生成演算１３２５（例えば、配向マップに第２の平滑化係数を適用する）、及び／又はスケール空間上局所記述子生成演算（local descriptor generation over scale space operation）１３２９（例えば、複数のスケール空間からの２つ以上のスケール空間に対応する複数の平滑化配向マップをばらばらにサンプリングする）を含み得る。これらの演算は、例えば処理回路１３０２によって実行され得る。
【０１１１】
処理回路１３０２は、撮像された画像を処理して、画像／対象物認識のために後で送信又は使用され得る局所特徴記述子を生成するように適応され得る。例えば、処理回路１３０２は、スケール空間生成器１３２０、特徴／ポイント検出器１３２６、配向画像微分生成器配向マップ生成器１３２２、平滑化配向マップ生成器１３２４、及び／又はスケール空間上局所特徴記述子生成器１３２８を含むか又は実装し得る。スケール空間生成器１３２０は、例えば、図８に示すように、複数の異なるスケール空間を生成するためにぼかし関数（例えば、ガウスカーネル）を用いて画像を畳み込むように働き得る。次いで、特徴／ポイント検出器１３２６は、（例えば、極大値及び極小値を使用することによって）画像のための異なるスケール空間中の一つ以上のポイントを識別し得る。次いで、配向画像微分生成器１３３０は、スケール空間の配向微分をとって複数の画像微分を生成し得る。配向マップ生成器１３２２は、画像微分の値にクリッピング関数（・）+を適用することによって画像微分ごとに配向マップを生成し得る。次いで、平滑化配向マップ生成器１３２４は、各配向マップをさらに畳み込んで、対応する平滑化配向マップを取得する。局所特徴／ポイント記述子生成器１３２８は、複数のスケール空間のための平滑化配向マップを使用することによって（例えば、図８、図９、及び図１０に示す）注目するポイントごとに記述子（例えば、デイジー記述子）を生成する。モバイルデバイス１３００は、それらの図で説明する一つ以上の特徴及び／又は方法を実装し得る。
【０１１２】
次いで、処理回路１３０２は、一つ以上の局所特徴／ポイント記述子を記憶装置１３０８に記憶し得、及び／又はさらに局所特徴／ポイント記述子をワイヤレス通信インターフェース１３１０（例えば、トランシーバ又は回路）を介して通信ネットワーク１３１２を通して画像マッチングサーバに送信し得、その画像マッチングサーバは特徴記述子を使用して画像又はその画像中の対象物を識別する。即ち、画像マッチングサーバは、特徴記述子をサーバ自体の特徴記述子のデータベースと比較して、それのデータベース中のいずれかの画像が同じ特徴を有するかどうかを判断し得る。
【０１１３】
図に示す構成要素、ステップ、特徴及び／又は機能のうちの１つ又は複数は、単一の構成要素、ステップ、特徴又は機能に再構成され及び／又は組み合わされ得、或いは幾つかの構成要素、ステップ、又は機能で実施され得る。また、本明細書で開示する新規の特徴から逸脱することなく追加の要素、構成要素、ステップ、及び／又は機能が追加され得る。ある図に示した装置、デバイス、及び／又は構成要素は、別の図で説明する方法、特徴、又はステップのうちの１つ又は複数を実行するように構成され得る。本明細書で説明するアルゴリズムはまた、効率的にソフトウェアで実装され及び／又はハードウェアに組み込まれ得る。
【０１１４】
また、実施形態について、フローチャート、流れ図、構造図、又はブロック図として示されたプロセスとして説明することがあることに留意されたい。フローチャートは動作を逐次プロセスとして説明することがあるが、動作の多くは並行して又は同時に実行され得る。さらに、動作の順序は並び替えられ得る。プロセスは、その動作が完了すると終了する。プロセスは、メソッド、関数、プロシージャ、サブルーチン、サブプログラムなどに対応し得る。プロセスが関数に対応する場合、その終了は呼び出し関数又はメイン関数への関数の復帰に対応する。
【０１１５】
さらに、記憶媒体は、読取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、及び／又は情報を記憶するための他の機械可読媒体、プロセッサ可読媒体、及び／又はコンピュータ可読媒体を含む、データを記憶するための一つ以上のデバイスを表し得る。「機械可読媒体」、「コンピュータ可読媒体」、及び／又は「プロセッサ可読媒体」という用語は、限定はしないが、ポータブル又は固定記憶装置、光記憶装置、並びに（一つ以上の）命令及び／又はデータを記憶、含有又は担持することが可能な様々な他の媒体などの非一時的媒体を含み得る。従って、本明細書で説明する様々な方法は、「機械可読媒体」、「コンピュータ可読媒体」、及び／又は「プロセッサ可読媒体」に記憶され、一つ以上のプロセッサ、機械及び／又はデバイスによって実行され得る命令及び／又はデータによって完全に又は部分的に実装され得る。
【０１１６】
さらに、実施形態は、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、又はそれらの任意の組合せによって実装され得る。ソフトウェア、ファームウェア、ミドルウェア又はマイクロコードで実装される場合、必要なタスクを実行するためのプログラムコード又はコードセグメントは記憶媒体或いは（一つ以上の）他の記憶装置などの機械可読媒体に記憶され得る。プロセッサは必要なタスクを実行し得る。コードセグメントは、プロシージャ、関数、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェアパッケージ、クラス、又は命令、データ構造、若しくはプログラムステートメントの任意の組合せを表し得る。コードセグメントは、情報、データ、引数、パラメータ、又はメモリ内容をパス及び／又は受信することによって、別のコードセグメント又はハードウェア回路に結合され得る。情報、引数、パラメータ、データなどは、メモリ共有、メッセージパッシング、トークンパッシング、ネットワーク送信などを含む適切な手段を介してパス、フォワーディング、又は送信され得る。
【０１１７】
本明細書に開示する例に関連して説明する様々な例示的な論理ブロック、モジュール、回路、要素、及び／又は構成要素は、汎用プロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、又は他のプログラマブルロジック構成要素、個別ゲート若しくはトランジスタ論理、個別ハードウェア構成要素、又は本明細書で説明する機能を実行するように設計されたそれらの任意の組合せを用いて実装又は実行され得る。汎用プロセッサはマイクロプロセッサであり得るが、代替として、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、又は状態機械であり得る。プロセッサはまた、コンピューティング構成要素の組合せ、例えば、ＤＳＰとマイクロプロセッサの組合せ、複数のマイクロプロセッサ、ＤＳＰコアと連携する一つ以上のマイクロプロセッサ、或いは任意の他のそのような構成として実装され得る。
【０１１８】
本明細書に開示する例に関連して説明する方法又はアルゴリズムは、ハードウェア、プロセッサによって実行可能なソフトウェアモジュール、又は両方の組合せで、処理ユニット、プログラム命令、又は他の指令の形で直接実施され得、単一のデバイスに含まれるか又は複数のデバイスにわたって分散され得る。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、又は当技術分野で知られている任意の他の形態の記憶媒体中に常駐し得る。記憶媒体は、プロセッサがその記憶媒体から情報を読み取り、その記憶媒体に情報を書き込むことができるようにプロセッサに結合され得る。代替として、記憶媒体はプロセッサに一体化され得る。
【０１１９】
さらに、本明細書で開示する実施形態に関連して説明する様々な例示的な論理ブロック、モジュール、回路、及びアルゴリズムステップは、電子ハードウェア、コンピュータソフトウェア、又は両方の組合せとして実装され得ることを、当業者は諒解されよう。ハードウェアとソフトウェアのこの互換性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、及びステップを、上記では概してそれらの機能に関して説明した。そのような機能をハードウェアとして実装するか、ソフトウェアとして実装するかは、特定の適用例及び全体的なシステムに課される設計制約に依存する。
【０１２０】
本明細書で説明する本発明の様々な特徴は、本発明から逸脱することなく様々なシステムで実装され得る。上記の実施形態は例にすぎず、本発明を限定するものと解釈すべきではないことに留意されたい。実施形態についての説明は、例示的なものであり、特許請求の範囲を限定するものではない。従って、本教示は、他のタイプの装置、並びに多くの代替形態、修正形態、及び変更形態に容易に適用できることが当業者には明らかであろう。
【図１】
0005602940.tif 000054
【図２】
0005602940.tif 000055
【図３】
0005602940.tif 000056
【図４】
0005602940.tif 000057
【図５】
0005602940.tif 000058
【図６】
0005602940.tif 000059
【図７】
0005602940.tif 000060
【図８】
0005602940.tif 000061
【図９】
0005602940.tif 000062
【図１０】
0005602940.tif 000063
【図１１】
0005602940.tif 000064
【図１２】
0005602940.tif 000065
【図１３】
0005602940.tif 000066