(57)【要約】  方向付けおよび位置に従って解析される目標画像の離散位置で方向付け場が画素を記述する、目標画像の少なくとも複数の画素の方向付け場を判定するコンピュータを使用することによって、目標オブジェクトを目標画像において見付ける。データベース内のモデル画像における方向付け場に対して方向付け場をマッピングして、目標画像の方向付け場とデータベース内のモデル画像の方向付け場との間の整合値を計算する。整合値を閾値化し、閾値を超えるそれらの整合値を数えて、目標とモデルとの間の整合を判定する。【特許請求の範囲】
【請求項１】
目標画像において目標オブジェクトを認識する方法において、
前記目標画像の少なくとも複数の画素の方向付け場を判定するコンピュータを使用するステップであって、前記方向付け場は、方向付けおよび位置に従って解析される前記目標画像の離散位置で画素を記述するステップと、
データベース内のモデル画像における方向付け場に対して前記方向付け場をマッピングして、前記方向付け場または前記目標画像と前記データベース内のモデル画像の方向付け場との間の整合値を計算するステップと、
閾値に対して前記整合値を閾値化するステップと、
前記閾値を超えるそれらの整合値を数えて、前記目標と前記モデルとの間の整合を判定するステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、
前記モデルと前記目標の両方に対する共通スケールを判定し、全画像を変更して前記共通スケールを表現するステップをさらに含むことを特徴とする方法。
【請求項３】
請求項２に記載の方法において、
前記共通スケールを２．５画素に設定することを特徴とする方法。
【請求項４】
請求項２に記載の方法において、
前記閾値は最小重みの３％を超えることを特徴とする方法。
【請求項５】
請求項１に記載の方法において、
前記方向付け場は、オブジェクトの内側にある場合に前記オブジェクトと平行に向き、前記オブジェクトの外側に位置する場合に前記オブジェクトと垂直に向く方向付け場であることを特徴とする方法。
【請求項６】
請求項１に記載の方法において、
前記マッピングは、ベクトルの方向付け間の位置合わせを測定するステップを含むことを特徴とする方法。
【請求項７】
請求項１に記載の方法において、
前記方向付け場は、点を中心に回転する場合に１８０度の周期性を有することを特徴とする方法。
【請求項８】
請求項１に記載の方法において、
前記方向付け場は、
2015515661.tif 000020
において、
2015515661.tif 000021
によって画像Ｉの積分場Ｓを生成し、
2015515661.tif 000022
および
2015515661.tif 000023
のように組を判定することによって生成される組｛ｗ、θ｝であり、ここで、ｗは実数値スカラであり、θは区間［０、π）における角度であり、
Ｋ（μ、λ）は、特性Ｋ（μ、λ）＝Ｋ（λ、μ）およびＫ（λ、λ）＝１を有する実数値関数であることを特徴とする方法。
【請求項９】
請求項１に記載の方法において、
整合値を計算する前記ステップは、前記方向付け場の自己相関を計算することを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、
前記自己相関は、
2015515661.tif 000024
によって画素（ｉ、ｊ）で整合を規定するステップを含み、式中、Ｃ（ｉ、ｊ）は、
2015515661.tif 000025
のように計算される整合マップであり、Ａは、
2015515661.tif 000026
のように計算される前記モデルに対する自己相関であり、Ｂ（ｉ、ｊ）は、Ｃ（ｉ、ｊ）の近傍を中心に抽出された部分行列であり、ａは、自己相関の量に対して最終的な尺度に位置合わせＣ（ｉ、ｊ）を与えるべき重みの量を判定するパラメータであり、ａ＝０の場合、位置合わせの尺度のみを使用し、ａ＝１の場合、自己相関の尺度のみを使用し、ａ＝０．５の場合、位置合わせおよび自己相関を均等に重み付けすることを特徴とする方法。
【請求項１１】
色、コントラストおよび照明の変化と各種画像アーチファクトとに対して安定している、オブジェクト認識用の安定画像記述子を生成する方法において、
線積分に基づいて複数の画素位置の各々において０度〜１８０度の間の方向付け角度を生成するコンピュータを使用するステップと、
線積分を用いて前記計算方向付け角度の信頼性を示す、方向付け重みを生成する前記コンピュータを使用するステップと、
ある特定の閾値重みを超える重みを有する全方向付けを有効であると割り当て、ある特定の閾値未満の重みを有する全方向付けを無効であると割り当てるステップと、
を含むことを特徴とする方法。
【請求項１２】
方向付け場のスケール不変表現を生成する方法において、
多数のスケールの場合、画像の少なくとも一部の全画素に対して平均方向付け重みを計算するステップと、
前記平均方向付け重みを最大にするスケールを選択するステップと、
最適スケールと所定の参照スケールとの間の関係に基づいて前記方向付け場をサイズ変更するステップと、
を含むことを特徴とする方法。
【請求項１３】
２つの方向付け場１および２の相関を測定する方法において、
方向付け場１と方向付け場２における方向付けとの間の位置合わせを計算して、−１と１との間の値を前記位置合わせに割り当てるステップであって、−１は、方向付け場１の方向付け角度１が方向付け場２の方向付け角度２と垂直であることを意味し、１は、方向付け角度１および２が平行であることを意味し、０は、前記方向付けが４５度だけ異なる、または前記２つの方向付けのうち少なくとも１つが０の重みを有することを意味するステップと、
方向付け場１の全方向付けと方向付け場２における対応する方向付けとの平均位置合わせを計算するステップと、
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２０１１年２月２４日出願の仮特許出願第６１６０３０８７号明細書から優先権を主張し、この明細書の全内容を参照として取り込む。
【背景技術】
【０００２】
電子フィルタを用いて、画像における特徴を検出してそれらの特徴を見付けることができる。フィルタでは、カーネルを用いて、カーネルを整合させる部分を有する画像を見付ける、または画像を自動的に特徴付けることが多い。
【０００３】
スケール不変特徴変換、即ちＳＩＦＴなどの特徴記述アルゴリズムを用いて、画像においてオブジェクトを検出することができる。ＳＩＦＴは、例えば、米国特許第６，７１１，２９３号明細書に記載されている。一般に、ＳＩＦＴでは、デジタル画像において興味深い部分を見つけ、キーポイントとも呼ばれるＳＩＦＴ特徴記述子に従ってその部分を定義する。記述子は、データベースに記憶されている。新しい画像からデータベースに特徴を比較することによって、それらの同一画像を新しい画像において認識することができる。ＳＩＦＴアルゴリズムでは、スケール不変である異なる整合方法、方向付け、歪み、および照明の変化を教示する。
【発明の概要】
【０００４】
本出願は、画像において画像部分、例えばロゴを見付ける技法を説明する。
【０００５】
実施形態は、オブジェクト検出用の整合方向付け場フィルタ（ＭＯＦＦ）アルゴリズムの使用を説明する。
【図面の簡単な説明】
【０００６】
【図１Ａ】図１Ａは、画像におけるロゴを示す。
【図１Ｂ】図１Ｂは、画像におけるロゴを示す。
【図１Ｃ】図１Ｃは、画像におけるロゴを示す。
【図２】図２は、上部の例示的なロゴ、および下部の例示的なロゴの方向付け場を示す。
【図３Ａ】図３Ａは、ロゴ、およびそのロゴの方向付け場を示す。
【図３Ｂ】図３Ｂは、ロゴ、およびそのロゴの方向付け場を示す。
【図３Ｃ】図３Ｃは、ロゴ、およびそのロゴの方向付け場を示す。
【図４】図４は、上部のロゴ、中央部のロゴの方向付け場、および下部のロゴの閾値化方向付け場を示す。
【図５】図５は、実際の画像において見付けられたロゴに対する方向付け場を示す。
【図６】図６は、本出願による整合技法の動作のフローチャートを示す。
【発明を実施するための形態】
【０００７】
ＳＩＦＴなどのキーポイントを当てにする画像処理技法は、ある種のオブジェクト検出タスクに対して非常にうまくいっている。このようなタスクは、画像を一緒に「貼り付ける」目的で、数個の重複画像においてオブジェクトを整合させることを含む。また、ある種のロゴの検出に対して非常にうまくいっている。
【０００８】
ＳＩＦＴアルゴリズムは、大量の詳細およびテクスチャを有するオブジェクトの検出に非常に有効であり、画像貼り付けなどの多くのオブジェクト認識問題に間に合う。しかし、本発明者は、詳細またはテクスチャがほとんどない単純なオブジェクトを検出するのにＳＩＦＴアルゴリズムはあまり適していないことが分かっている。本発明者が行った実験において、ＳＩＦＴでは、例えば画像の大部分である大きいロゴを認識すると分かったが、詳細が少量のより小さいロゴを見付けられない。
【０００９】
図１Ａおよび図１Ｂは、異なる種類の画像の詳細を示し、図１Ａは、大量の詳細を有し、ＳＩＦＴを使用可能であり、図１Ｂは、低い詳細の非テクスチャのロゴであり、ＳＩＦＴはこのオブジェクトにあまり有効でないと本発明者は分かった。ロゴが全画面の非常に小さい部分である別の例を図１Ｃに示す。
【００１０】
ＳＩＦＴは画像において局所キーポイントの検出を当てにするので、ＳＩＦＴは非テクスチャのオブジェクトにあまり有効でないと、本発明者は考えている。キーポイントはできるだけ多くの一意の情報を含むように、キーポイントを選択する。しかし、図１Ｂ中のナイキ（Ｎｉｋｅ）のロゴなどのオブジェクトの場合、この画像に一意の詳細はほとんどない。ＳＩＦＴアルゴリズムが見付けるキーポイントは、目標画像において多種多様な他のオブジェクトに存在することもある。即ち、図１Ｂのロゴのような単純なロゴの特徴において十分な一意性がない。
【００１１】
本発明者は、ＳＩＦＴと異なる技法を使用し、図１Ｂ中のナイキのロゴなどの非テクスチャのオブジェクトを検出するのに特に有用である技法を開発している。ここに記載の技法では、オブジェクトの形状属性のほとんどを取り込もうとする。これは、ＳＩＦＴが使用する高度に局所的なキーポイントとは対照的に、モデルにおいて大域情報を使用する。色および光の変化、陰影、圧縮のアーチファクト、および他の画像歪みに反応しない記述子を用いて、オブジェクトの大域属性を記述する。
【００１２】
ＳＩＦＴのような技法は通常、「コーナーのような」特徴に近いキーポイントを検出することに、本発明者は留意する。本発明者は、次のセクションで例示する、この方法に関する多くの問題を認識している。
【００１３】
問題１：キーポイントがない、またはキーポイントがあまりにも少ないオブジェクト
ロゴの中には、オブジェクトを確実に検出するのにＳＩＦＴのような方法が使用できる十分多くのキーポイントを生成する「コーナーのような」特徴をあまり含まないロゴもある。これらのオブジェクトは、低品質画像においてＳＩＦＴのような方法によって確実に使用される、信頼できないまたは非常に信頼性の低いキーポイントを生成することが多い。
【００１４】
問題２：解像度の悪いオブジェクト
大量に画素化された、または圧縮のアーチファクトを含む解像度の悪いオブジェクトにＳＩＦＴのような方法を適用した場合、別の問題が生じる。このような場合、画素化は、「偽りの」コーナーを効果的に採用し、その結果、偽りのキーポイントを採用することがある。これにより、ＳＩＦＴのような方法の信頼性が大幅に制限されることがある。
【００１５】
問題３：総称オブジェクト形状の検出
ＳＩＦＴとその関係物などのキーポイントベースの方法は、「総称オブジェクト特徴」、例えば銃の形状を検出するように設計されていなかった。
【００１６】
従って、キーポイントベースの方法は、より総称的な検出問題、例えば銃の検出に使用できない。
【００１７】
ＳＩＦＴのような方法は、大量の詳細を含む良質のオブジェクトに対してうまく機能する。次のセクションで分かるように、ＭＯＦＦは、これらの全種類のオブジェクトに有効であるが、「困難な」オブジェクト、例えば、詳細がほとんどないオブジェクト、および例えば低い解像度または圧縮に起因するアーチファクトによって乱されたオブジェクトに特に適している。
【００１８】
実施形態では、方向付け場を用いた画像における特徴検出を説明する。ある特定の企業のロゴなどの、テクスチャがほとんどないまたはテクスチャがないオブジェクトを参照して、「非テクスチャ」のオブジェクトを検出する特殊な用途を説明する。
【００１９】
実施形態では、ここでは「モデル画像」と記述されている項目を１つ以上の画像において見付けることを説明する。いわゆる目標画像は、目標画像においてモデル画像の存在を検出するのに解析中である。
【００２０】
実施形態では、「信頼性重み」を各検出オブジェクトに割り当てることを説明する。信頼性重みは、整合が妥当である計算確率を示す。
【００２１】
ロゴ検出の目的で、この実施形態におけるモデル画像は、ロゴの画像であることができ、目標画像は、（大きい）画像または映画フレームである。
【００２２】
キーポイントベースのアルゴリズムの概要
キーポイントベースのアルゴリズムは通常、次の主なステップを含む。
−キーポイントの特定
−各キーポイントの周りの近傍への方向付けの割り当て
−キーポイントにおける画像記述子の生成
−データベースに対する画像記述子の整合
−一貫性のない整合およびクラスタ化の除去
【００２３】
ＭＯＦＦアルゴリズムは、画像における全画素で方向付け場を生成する。次に、技法では、モデルのデータベースに対して方向付け場の自己相関および位置合わせの尺度の機能を果たす。
【００２４】
キーポイントベースのアルゴリズムおよびＭＯＦＦアルゴリズムは両方とも、方向付けを計算する。さらに、両方とも、何らかの方法で方向付けを含む整合ステップを使用する。しかし、２つの状況で全く違って、方向付けは、定義され、計算され、使用される。ＭＯＦＦが使用する位置合わせおよび自己相関の尺度は、ＳＩＦＴの場合において対応する同等物を有しないことも分かる。
【００２５】
これらの違いのために、２つのアルゴリズムは、異なるオブジェクト検出タスクに有用である。キーポイントベースのアルゴリズムは、大量の詳細な高解像度のオブジェクトを整合させ、画像において詳細なオブジェクトを識別するのによく適している。ＭＯＦＦは、低解像度で詳細がほとんどない少量の総称オブジェクトを整合させるのによく適している。
【００２６】
異なる色および陰影を含むロゴは多種多様であることが多いので、モデルのデータベースにおいて考えられるすべての種類のロゴを使用する必要なしに、ありとあらゆる種類のロゴを検出できることは重要である。
【００２７】
ロゴに一意である他の態様も説明する。例えば、金属ロゴは、目標画像において周囲からの反射を含んでもよく、その結果、ロゴ検出技法は、このような反射を探して考慮に入れるべきである。
【００２８】
特徴検出を行う方向付け場をここで説明する。方向付け場は、解析される画像の離散位置で推定される方向付けを記述してもよい。画像における各要素を、例えば、その方向付けおよび位置に従って特徴付けることができる。実施形態では、ここに記載のような方向付け場を用いて非テクスチャのオブジェクトを記述する方法を説明する。各ロゴを表現するスケール不変方向付け場を生成する。この方向付け場が生成された後、目標画像において整合方向付け場を探索する。
【００２９】
画像Ｉの位置ｘにおける強度をＩ（ｘ）と表す。画像位置ｘにおける方向付けＦ（ｘ）を対Ｆ（ｘ）＝｛ｗ（ｘ）；θ（ｘ）｝と定義する。ここで、ｗは、角度θに対する重みを表すスカラである。角度θは、０度と１８０度（区間［０、π）との間の角度であり、重みｗは、ｗの大きさが方向付けの重要性または信頼性を測定するような実数である。
【００３０】
この方向付けを組｛ｗ、θ｝と定義する。ここで、ｗは実数値スカラであり、θは区間［０、π）における角度である。
【００３１】
ＳＩＦＴのような方法が通常使用する方向付けはベクトルであるが、ここで定義される方向付けはベクトルである必要はないことに留意されたい。これを理解する１つの方法は、ＳＩＦＴのようなアルゴリズムが通常使用する勾配ベクトルは、点を中心に回転する場合に３６０度の周期性を有することである。ＭＯＦＦが使用する方向付けは、「正方向および逆方向」の概念がなく、点を中心に回転する場合に１８０度の周期性を有する。次式によって定義される曲線族を考える。
2015515661.tif 000002
式中、θ∈［０、π）およびｓ∈［−Ｌ／２、Ｌ／２］。この曲線は、角度θで傾斜している長さＬの直線を記述する。
【００３２】
ここで、次式によって画像Ｉの積分場Ｓを生成する。
2015515661.tif 000003
【００３３】
これらの積分を所与として、次に、次式によって方向付けを生成する。
2015515661.tif 000004
式中、Ｋ（μ、λ）は、特性Ｋ（μ、λ）＝Ｋ（λ、μ）およびＫ（λ、λ）＝１を有する実数値関数である。
【００３４】
ＭＯＦＦによく適しているカーネルの有用な例は、次式のように定義される余弦カーネルである。
2015515661.tif 000005
【００３５】
この文書全体にわたって、ＭＯＦＦ方向付けとして上記のように計算された方向付けを参照する。
【００３６】
これらの方向付けは、従来の勾配ベースのベクトルの場合に３６０度の周期性を有するのに対して、点を中心に回転する場合に１８０度の周期性を有する。
【００３７】
ＭＯＦＦ方向付けに対する重みは、強度差を当てにしないだけでなく、方向付けの信頼性尺度としても考えられるはずである。一方、勾配ベースの方向付けは、隣接する画素間の強度差を当てにする。
【００３８】
上記のように計算された方向付けは、オブジェクトの外側に位置する場合にエッジの方へ向き、オブジェクトの内側に位置する場合にエッジに沿って向く独特な性質を有する。これは、エッジに対して垂直に常に向く勾配ベースの方向付けと比較して大きな違いである。
【００３９】
上記のように計算された方向付けは、ノイズおよびアーチファクトにあまり反応しない。種々のぶれ機構と組み合わせた場合でも、勾配ベースの方向付けは、特に「細い」オブジェクト（例えば、太さが１画素の曲線）の場合、ノイズおよびアーチファクトに強く影響を受けやすい。
【００４０】
ＭＯＦＦ方向付けは、細い線状の特徴を記述するのに特によく適している。勾配ベースの方向付けは、より大きい領域間のエッジを定義するのによく適している。
【００４１】
まず、勾配を用いて計算された方向付けは、「正方向および逆方向」の概念がある。これは、方向付けを表現する線に矢印の先を追加することによって例示されることが多い。しかし、ＭＯＦＦ方向付けは、「正方向および逆方向」の概念がなく、従って、矢印の先がない線分で描かれることがより適している。
【００４２】
この文書に記載の方向付けの第２の重要な特性は、方向付けの重みを評価する場合、ＭＯＦＦ方向付けは強度差ではなく形状を強調することである。その結果、ＭＯＦＦ方向付けが異なる強度を有する場合でも、ＭＯＦＦ方向付けは、同じ方向付けの２つのオブジェクトに対する同様の（強い）重みを生成する。ＭＯＦＦ方向付けの有用な特徴は、ＭＯＦＦ方向付けは、オブジェクトの内側に位置する場合にオブジェクトと平行に向き、オブジェクトの外側に位置する場合にエッジと垂直に向くことである。オブジェクトの太さにかかわらず、これは生じ、勾配ベースの方向付けが問題を有する非常に細い曲線状のオブジェクトの場合でも、この特性は安定した状態を保つ。
【００４３】
図２は、上部に原型のモデルおよび下部に方向付け場を示す例を示す。方向付けの向きは、方向付けがオブジェクトの内側または外側にあるかに左右されることに留意されたい。
【００４４】
図３ＡにおけるＭＯＦＦ方向付けおよび勾配ベースの方向付けを用いてマクドナルド（ＭｃＤｏｎａｌｄｓ）のロゴの周りの方向付け場を比較することによって、別の実施形態を理解できる。これは、図３Ｂに示すロゴの解像度の悪い部分および歪んだ映像（図３Ｃ参照）においてより一層顕著になる。
【００４５】
ぶれおよび平均化技法を採用することによって、勾配ベースの方向付けの欠点の一部を克服することができるが、このような方法は、独自の問題を有する。このような技法に関する欠点の１つは、ぶれが本物の構造の強度差を減らして、勾配の計算がより強固でなくなることである。
【００４６】
ＭＯＦＦ方向付けの重みは、方向付けの角度の信頼性に関する情報を提供するが、これらの信頼性重みを直接使用しない。あまり信頼できないと考えられる方向付けを除去するのに、それらの重みを使用するだけである。通常、信頼性が３％未満の方向付けをこのように除去する。次に、残りのすべての方向付けに同じ重み（１に設定）を与える。これは、検出したいオブジェクトの強度へのすべての参照を除去することである。強度は画像によって大きく変わることがあるが、方向付け角度で記述される基本的な形状は、アーチファクトに対して非常に安定している。
【００４７】
オブジェクトは多種多様な大きさで現れるので、オブジェクトを「正規化」の方法で表現することは重要である。上記の技法を用いて、幅Ｌの線状構造の方向付け場を生成する場合、約４ＬのスケールＬを用いて、このようなオブジェクトを中心とする方向付けの信頼性重みｗを最大にすることを示すことができる。同様な関係は、エッジの近傍で当てはまる。従って、全画素に対する平均方向付け重みを最大にする場合、画像においてオブジェクトの最も顕著な構造の近似幅を伝える最適のスケールパラメータを求めることができる。
【００４８】
これを例示するために、一方の画像が他方の画像よりも大きい、同じオブジェクトの２つの画像を考える。オブジェクトは、小さい画像の太さが２画素および大きい画像の太さが５画素を有するように見えるものとする。次に、小さい画像にスケール８および大きい画像にスケール２０を使用することによって、方向付け場の信頼性を最大にする。最適化スケールを４で割ることによって、画像における構造の真の太さを手動で推定する必要なしにその真の太さを推定することができる。
【００４９】
次に、「共通」スケールを決定する。この共通スケールを、「参照」構造の太さに選択する。その太さは、精度の理由で細すぎる（例えば、１画素）ことは望ましくないが、効率の理由で太すぎることも望ましくない。実験から、約２．５画素の参照太さがよい妥協点であることが分かっている。
【００５０】
上記の例に戻って、オブジェクトの太さを約２．５画素に等しくするために、２．５／２倍に小さい画像から方向付け場をサイズ変更する。方向付け場を参照スケールに縮小するために、約２．５／８倍に大きい画像をサイズ変更する。この手順の後、小さい画像および大きい画像のサイズ変更された方向付け場は基本的に一致する。上部がモデルのクローズアップを示し、中央部がモデルの方向付け場を示し、下部がモデルの閾値化方向付け場を示す例示については図４を参照せよ。
【００５１】
スケール不変をキーポイントベースの方法に使用するという意味ではこの「正規化」手順はオブジェクトのスケール不変表現を生成しないことに留意されたい。上記の正規化手順は、構造の幅を正規化するだけであり、ＳＩＦＴのような方法が行う、オブジェクトの全体のサイズを正規化しない。
【００５２】
モデルと目標の両方に対する方向付け場を上述のように計算して正規化した後、画像における最大重みのほぼゼロ（約３％の重み）である重みをゼロに設定するように方向付け場を閾値化する。すべての他の方向付け重みを１に設定する。
【００５３】
目標に対してモデルの整合マップを計算するために、閾値化モデル方向付け場を、畳み込み型アルゴリズムにおいて閾値化目標方向付け場にここで整合させる。しかし、従来の畳み込みは２つの入力ベクトルのスカラ積を含むのに対して、この場合、２つの入力ベクトルにおける方向付け間の位置合わせを測定する。数学的に、この整合を画素（ｉ、ｊ）で次式のように表すことができる。
2015515661.tif 000006
式中、Ｃは整合マップを表し、Ｍ×Ｎはモデル方向付け場の寸法である。
【００５４】
この式を例示するために、画像においてナイキのロゴの検出を考察する。ナイキのロゴは、詳細の不足のために、キーポイントベースの方法が失敗する周知の例である。図５は、データベースで事前計算された方向付け場と比較された目標画像から計算されたロゴの方向付け場を示している。次に、２つの方向付け場を重ね合わせて、すべての点で位置合わせを測定する。緑色で高度な位置合わせを例示する。
【００５５】
整合マップを計算する上記の総和式は、画像において各画素を中心にこの重ね合わせを効果的に計算する。次に、すべての個々の位置合わせを合計して、目標画像において画素で正味の位置合わせを与える。
【００５６】
異なる種類の方向付けをＳＩＦＴのような方法における整合に使用するが、このような方法における整合は著しく異なるやり方で行われるということを述べる価値がある。ＳＩＦＴのような方法では、キーポイントの近傍に方向付けのヒストグラム（統計値）を生成して、キーポイントで記述子を形成する短い配列の数で得られた数を収集することが多い。
【００５７】
ＭＯＦＦでは、キーポイントも局所画像記述子も使用しない。また、方向付けの特定の局所統計値を単に記録するヒストグラムも当てにしない。この場合、ＳＩＦＴが使用しない位置合わせの尺度を用いて、大域的に方向付けを比較する。後にこのセクションで、方向付け場間の自己相関を測定する追加可能な尺度も考察する。自己相関は、ＳＩＦＴのようなアルゴリズムにおいて同等物を有しない。
【００５８】
画素（ｉ、ｊ）で整合を計算するアルゴリズムを、次のようにここで記述することができる。スケール変更されたモデル方向付け場のサイズをｍｏｄｅｌＳｉｚｅＹおよびｍｏｄｅｌＳｉｚｅＸによって与えるものとする。次に、スケール変更された目標画像における画素ｉ、ｊに対する整合を、次のアルゴリズムによって計算する。
2015515661.tif 000007
【００５９】
ここで、ｍｏｄｅｌＡｒｅａは、モデル方向付け場において非ゼロ重みの数に設定される正規化定数である。
【００６０】
方向付け場の自己相関も測定することによって、ある種のオブジェクトに対する誤検出の数をかなり減らすことができる。画素（ｉ、ｊ）における方向付け場の自己相関Ａを、次式によって計算することができる。
2015515661.tif 000008
式中、ｋ、ｌ＝−ｒ、−ｒ＋１、…、ｒの場合、ｒは、どの程度の範囲にわたって方向付け場を自己相関すべきかを判定するパラメータである。次に、自己相関行列を、各モデルに対して事前計算方向付け場と一緒に記憶することができる。
【００６１】
ここで、自己相関を次のように使用することができる。まず、整合マップＣを生成する。大きい整合値を有する各画素（ｉ、ｊ）に対して、ここで、要素Ｃ（ｋ、ｌ）（式中、ｋ＝ｉ−ｒ、ｉ−ｒ＋１、…、ｉ＋ｒおよびｌ＝ｊ−ｒ、ｊ−ｒ＋１、…、ｊ＋ｒ）を抽出することによって部分行列Ｃを抽出し、その要素を行列Ｂ（ｉ、ｊ）として記憶する。
【００６２】
目標画像がモデルの正確なコピーを含んでいる場合、この部分行列は自己相関行列Ａと全く同じであることに留意されたい。従って、ＡとＢとの間の差は、目標画像における画素（ｉ、ｊ）の周りの検出オブジェクトとモデルとの間の類似性に関する追加の尺度を与える。この尺度は、長方形および銃の形状などの特定の「単純な」オブジェクトに対して特に有効である。従って、ある適切な基準によって測定されたＡとＢとの間の差に閾値化を適用することができる。
【００６３】
画素（ｉ、ｊ）で整合を有する場合、規定するのに使用する最終的な尺度を、次式によってここで与える。
2015515661.tif 000009
式中、Ｃ（ｉ、ｊ）は、上記の方程式から計算され、Ａは、上記の方程式から計算されたモデルに対する自己相関であり、Ｂ（ｉ、ｊ）は、上記のようにＣ（ｉ、ｊ）の近傍を中心に抽出された部分行列である。ここで、高い自己相関を「与える」ことを望む量に対して、最終的な尺度に位置合わせＣ（ｉ、ｊ）を「与える」ことを望む重みの量を判定するパラメータａも採用している。例えば、ａ＝０の場合、位置合わせの尺度のみを使用し、ａ＝１の場合、自己相関の尺度のみを使用する。ａ＝０．５の場合、位置合わせおよび自己相関を均等に重み付けする。
【００６４】
従って、全処理は、次の通りであり、図６のフローチャートに示されている。
【００６５】
６００では、上記の方程式を用いて、目標画像に対して方向付け場を計算する。
2015515661.tif 000010
【００６６】
Ｔ６１０、データベースにおける各モデルに対して、どこでもゼロである原画像と同じサイズを有する行列Ｍとして最終的な整合マップを初期化する。
【００６７】
各３Ｄの姿勢の場合
各サイズの場合
６２０では、方程式を用いて、各画素で整合値を計算する。
2015515661.tif 000011
これにより、Ｍｔｍｐと呼ばれる一時的整合マップが得られる。
【００６８】
６３０では、Ｍｔｍｐにおいて最大整合値のある一定の割合に基づいて整合値を閾値化する。
【００６９】
６４０では、閾値化Ｍｔｍｐにおいて極大の数を数える。極大の数が閾値よりも小さい場合、これは、整合オブジェクトを検出している可能性が高いことを意味する「まれな」事象を有することを意味する。
【００７０】
前のステップで検出されたすべての極大座標（ｉ、ｊ）の場合
整合値Ｍｔｍｐ（ｉ、ｊ）が閾値よりも大きい場合
Ｍｔｍｐにおける指標位置（ｉ、ｊ）から、原画像サイズに対して対応する位置を計算し、新しい座標を（ｉ’、ｊ’）として表す。
【００７１】
整合を最終的な整合マップに追加する。Ｍ（ｉ’、ｊ’）＝Ｍ（ｉ’、ｊ’）＋Ｍ（ｉ、ｊ）
それ以外
継続する
それ以外
継続する
【００７２】
最終的な整合マップＭを閾値化する。上記のどの点についても、閾値を現在のモデルの整合として記録する。
【００７３】
アルゴリズムをより効率的にするために、計算コストをかなり減らす全アルゴリズムに多くの改良を行う。
【００７４】
通常、多くの異なるスケールＬに対して方向付け場を計算することが有用である。このセクションでは、スケールＬｍａｘのみに対して方向付け場を計算するのとほぼ同じコストで、すべての中間スケールＬ＝２、３、…、Ｌｍａｘに対して方向付け場を生成するアルゴリズムを示す。
【００７５】
この目的のために、方向付け場を計算するのに使用された積分Ｓにスケール添字Ｌを採用する。
2015515661.tif 000012
【００７６】
次のような積分を計算する。
2015515661.tif 000013
各画素は、方程式（１）において方向付け場を計算する計算コストが最も高い部分である場合。しかし、積分ＯＬおよびＳＬの組合せを、次のような二重積分として書くことができることに留意されたい。
2015515661.tif 000014
または、同様な意味合いで、次のように書くことができる。
2015515661.tif 000015
【００７７】
ここで、この積分は「ネスト」の特性を有することに留意されたい。
2015515661.tif 000016
【００７８】
これは、より大きいスケールに対して積分Ｏを計算するために、より小さいスケールから結果を使用して、細いリングにわたって積分された積分から寄与を丁度追加することができることを意味する。この手順では、スケールＬｍａｘのみに対して方向付け場を計算するのとほぼ同じコストで、すべてのスケールＬ＝２、３、…、Ｌｍａｘに対して方向付け場を計算する。
【００７９】
別の単純化は、処理粗スケールファースト（Ｐｒｏｃｅｓｓｉｎｇ  Ｃｏａｒｓｅｒ  Ｓｃａｌｅｓ  Ｆｉｒｓｔ）である。
【００８０】
上述の正規化方法のために、より大きいスケールに対して計算された方向付け場は、より粗い格子に効果的に下方へサンプリングされる。より粗い格子上の整合を探すことによって、どこに潜在的な整合が位置するか、そしてその整合が画像内に位置するかどうか大まかに分かる。また、より粗いスケールを最初に考察することによって、確実性が高いどのオブジェクトが画像内にないかを判定して、更なる考察からこれらのオブジェクトを除去できることが多い。
【００８１】
これは、原画像の低い解像度でより粗いスケール上の整合の高速探索を行ってから、潜在的な整合がより粗いスケールに記録された領域でより精細なスケール上の整合を単に探すことができることを意味する。より精細なスケール上で、通常、データベースにおいて全モデルのごく一部を探索しさえすればよい。なぜなら、通常、より粗いスケールにおける整合結果を考察することによって探索から多くのモデルを除去できるからである。
【００８２】
ネスト化された部分集合による整合。
上述の方程式（２）内の総和において全画素（ｋ、ｌ）に対して位置合わせを即時計算する代わりに、ネスト化された部分集合の概念を採用する。方程式（２）によって総和された全画素からなる集合を定義することによって開始し、次式のように定義する。
2015515661.tif 000017
式中、ＭおよびＮは、モデルの縦横のサイズを表す。
【００８３】
次に、各部分集合が互いに真部分集合であるようにネスト化された一連の部分集合の表記法を採用する。
2015515661.tif 000018
【００８４】
集合を選択する方法を正確に指定しない。重要なのは、これが、各集合において増加している画素座標を有する一連の順序付けられた集合を生成することである。ここで、次式のように画素（ｉ、ｊ）で部分集合ｍに対して整合を定義する。
2015515661.tif 000019
【００８５】
セクション５．１．３においてアルゴリズムで整合Ｍｔｍｐを計算する場合、次のようなアルゴリズムによってそのステップをここで置換することができる。
部分集合の添字ｍ＝１、２、…、ｎ−１の場合：
方程式（５）を用いてＣｍ（ｉ、ｊ）を計算する。
Ｃｍ（ｉ、ｊ）が閾値よりも大きい場合
ループを継続する。
それ以外
ループから出て、メインループの次のサイズに続く。
【００８６】
これは、大部分の画素の場合、モデルにおける全画素のごく一部のみを用いて整合を計算するだけであることを意味する。次に、画素のより小さい部分集合に基づいて整合を有するように見える場合、整合に対する一層の寄与を計算するだけである。
【００８７】
また、Ｃｍ（ｉ、ｊ）の計算を「ネスト化」できることに留意されたい。２つの連続部分集合ｍおよびｍ−１の差によって与えられた添字にわたって方程式（５）において合計を単に計算することによって、Ｃｍ−１（ｉ、ｊ）からＣｍ（ｉ、ｊ）を計算することができる。
【００８８】
有意な画素に対して整合値Ｃを単に計算する。
【００８９】
信頼できる方向付けの近傍でオブジェクトを検出する可能性があるだけであることに留意されたい。従って、まず、目標画像の方向付け重みを閾値化し、ある特定の閾値を超える重みを含む画素の近傍で整合を単に探すことができる。通常、これは、計算を大幅に節減する場合、画像において全画素の数パーセントに対して整合Ｃ（ｉ、ｊ）を計算しさえすればよいことを意味する。
【００９０】
ごく少数の実施形態を詳細に上述したが、他の実施形態も実現可能であり、本発明者は、これらの実施形態をこの明細書内に含むようにするつもりである。明細書には、別の方法で達成可能なより一般的な目標を達成する具体例が記載されている。この開示は、例示的であることを目的としており、特許請求の範囲は、当業者に予測可能な任意の修正または代替手段を含むことを目的としている。例えば、上記は、この技法を用いたある種の検出のみを記載しているが、さらに多くの種類の用途があることを理解すべきである。これを使用して、例えば、種々の映像にロゴおよび広告を見付けることができる。スポーツでは、これを使用して、チームのジャージ上のロゴまたはチームのジャージ上の番号を見付けることができる。
【００９１】
ここに開示の実施形態に関連して記載されている種々の例示的な論理ブロック、モジュール、回路およびアルゴリズムステップを、電子ハードウェア、コンピュータソフトウェアまたは両方の組合せとして実現できることを、当業者はさらに理解するであろう。ハードウェアおよびソフトウェアのこの互換性をはっきりと例示するために、種々の例示的な構成要素、ブロック、モジュール、回路およびステップを、それらの機能性によって一般的に上述している。このような機能性をハードウェアまたはソフトウェアとして実現するかどうかは、システム全体に課せられた設計制約および特定の用途に左右される。当業者は、特定の用途の各々に対して種々の方法で記載の機能性を実現できるが、このような実現の判断は、例示的な実施形態の範囲から離れると解釈すべきでない。
【００９２】
ここに記載の機能を実行するように設計されている、汎用プロセッサまたはコンピュータ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、グラフィック処理ユニット（ＧＰＵ）または他のプログラマブル論理装置、離散ゲートまたはトランジスタ論理、離散ハードウェア構成要素、またはそれらの任意の組合せを用いて、ここに開示の実施形態に関連して記載されている種々の例示的な論理ブロック、モジュールおよび回路を実現または実行してもよい。汎用プロセッサは、マイクロプロセッサであってもよいが、代替手段では、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械であってもよい。プロセッサは、ユーザインターフェースと通信し、ユーザが入力するコマンドを受信するユーザインターフェースポートも有し、ユーザインターフェースポートを介して通信してプロセッサの制御下で動作するプログラムを含む電子情報を記憶する少なくとも１つのメモリ（例えば、ハードドライブまたは他の同等な記憶装置、およびランダムアクセスメモリ）と、例えば、ＶＧＡ、ＤＶＩ、ＨＤＭＩ、表示ポートまたは任意の他の形式などのあらゆる種類のビデオ出力形式を介して出力を生成するビデオ出力とを有するコンピュータシステムの一部であることができる。このコンピュータシステムは、ラップトップまたはデスクトップのコンピュータを含んでもよく、携帯電話、ＩＰＡＤ（商標）などのタブレットを含むポータブルコンピュータ、およびすべての他の種類のコンピュータおよび計算プラットフォームを含んでもよい。
【００９３】
計算装置の組合せ、例えば、ＤＳＰおよびマイクロプロセッサ、複数のマイクロプロセッサ、ＤＳＰコアと併用した１つ以上のマイクロプロセッサの組合せ、または任意の他のこのような構成として、プロセッサを実現してもよい。ここに記載のような装置に値を選択するのにこれらの装置を使用してもよい。
【００９４】
クラウドコンピューティングを用いてプロセッサによって実行されるソフトウェアモジュール、ハードウェア、または組合せで、ここに開示の実施形態に関連して記載されている方法またはアルゴリズムのステップを直接具体化してもよい。ソフトウェアモジュールは、ランダムアクセスメモリ（ＲＡＭ）、フラッシュメモリ、読み取り専用メモリ（ＲＯＭ）、電気的プログラマブルＲＯＭ（ＥＲＲＯＭ）、電気的消去可能プログラマブルＲＯＭ（ＥＥＲＲＯＭ）、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、または具体的な持続性コンピュータベースの命令を記憶する任意の他の形式の具体的な記憶媒体に存在してもよい。例示的な記憶媒体を、記憶媒体に情報を読み書きできるようなプロセッサに結合する。代替手段では、記憶媒体は、プロセッサと一体型であってもよい。プロセッサおよび記憶媒体は、あらゆる種類の再構成可能な論理回路に存在してもよい。
【００９５】
１つ以上の例示的な実施形態では、上述の機能を、ハードウェア、ソフトウェア、ファームウェア、それらの任意の組合せで実現してもよい。ソフトウェアで実現する場合、機能を、コンピュータ可読媒体上に記憶したり、またはコンピュータ可読媒体上に１つ以上の命令またはコードとして伝送したりしてもよい。コンピュータ可読媒体は、コンピュータプログラムをある場所から別の場所へ容易に転送できる任意の媒体を含む通信媒体およびコンピュータ記憶媒体の両方を含む。記憶媒体は、コンピュータによってアクセスできる任意の利用可能な媒体であってもよい。一例として、限定ではなく、このようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＲＲＯＭ、ＣＤ−ＲＯＭまたは他の光ディスク記憶装置、磁気ディスク記憶装置または他の磁気記憶装置、または命令またはデータ構造の形で所望のプログラムコードを搬送または記憶するのに使用でき、コンピュータによってアクセスできる任意の他の媒体を含むことができる。
【００９６】
メモリ記憶装置は、回転磁気ハードディスクドライブ、光ディスクドライブ、またはフラッシュメモリベースの記憶ドライブまたは他のこのような固体、磁気または光記憶装置であってもよい。また、任意の接続部をコンピュータ可読媒体と適切に呼ぶ。例えば、同軸ケーブル、光ファイバーケーブル、ツイストペア、デジタル加入者線（ＤＳＬ）、または赤外線、無線およびマイクロ波などのワイヤレス技術を用いて、ウェブサイト、サーバまたは他のリモートソースからソフトウェアを伝送する場合、同軸ケーブル、光ファイバーケーブル、ツイストペア、ＤＳＬ、または赤外線、無線およびマイクロ波などのワイヤレス技術は、媒体の定義に含まれる。ここで使用されるようなディスク（ｄｉｓｋ）およびディスク（ｄｉｓｃ）は、コンパクトディスク（ＣＤ）、レーザーディスク、光ディスク、デジタル多用途ディスク（ＤＶＤ）、フロッピーディスクおよびブルーレイディスクを含み、ディスク（ｄｉｓｋ）は通常、磁気的にデータを再生するが、ディスク（ｄｉｓｃ）は、レーザーを用いて光学的にデータを再生する。上記の組合せも、コンピュータ可読媒体の範囲内に含むべきである。コンピュータ可読媒体は、１つ以上の機械によって実行する場合、この明細書全体にわたって記載されているアクションを含むコンピュータ実施動作となる命令を示す情報を具体化する機械可読持続性の具体的な媒体を含む物であってもよい。
【００９７】
ここに記載のような動作を、ウェブサイト上でまたはウェブサイトを通じて実行することができる。ウェブサイトを、サーバコンピュータ上で動作させる、または、例えばクライアントコンピュータにダウンロードされることによって局所的に動作させる、または、サーバファームを介して動作させることができる。携帯電話またはＰＤＡを通じて、または任意の他のクライアント上で、ウェブサイトにアクセスすることができる。ウェブサイトでは、例えばＭＨＴＭＬまたはＸＭＬなどの任意の形式で、およびカスケーディングスタイルシート（「ＣＳＳ」）またはその他などの任意の形式によって、ＨＴＭＬコードを使用することができる。
【００９８】
また、本発明者は、「ための手段」という用語を使用する特許請求の範囲のみが３５ＵＳＣ１１２の第６段落の下で解釈されるつもりであると意図している。さらに、明細書からの限定は、それらの限定が特許請求の範囲に明示的に含まれていない限り、あらゆる特許請求の範囲に解釈されるつもりはない。ここに記載のコンピュータは、あらゆる種類のコンピュータ、例えばワークステーションなどの汎用またはある特定目的のコンピュータであってもよい。Ｃ、またはＪａｖａ、Ｂｒｅｗまたは任意の他のプログラミング言語で、プログラムを書いてもよい。プログラムは、例えば、磁気または光、コンピュータハードドライブ、リムーバブルディスクまたはメモリスティックまたはＳＤ媒体などの媒体、または他のリムーバブル媒体などの記憶媒体上に常駐してもよい。例えば、ローカルマシンがここに記載の動作を実行できる、ローカルマシンに信号を送信するサーバまたは他のマシンを用いて、ネットワークを通じてプログラムを実行してもよい。
【００９９】
特定の数値をここで述べる場合、異なる範囲を特に述べない限り、本出願の教示の範囲内に依然としてとどまるが、値を２０％だけ増減できると考えるべきである。指定の論理的意味を使用する場合、反対の論理的意味も含まれるものとする。
【０１００】
開示された例示的な実施形態の上記の説明を与えて、当業者は本発明を実行または使用することができる。例示的な実施形態の種々の修正は、当業者にとって容易に明らかであり、ここに定義される一般原理を、本発明の精神と範囲から逸脱することなく他の実施形態に適用することができる。従って、本発明は、ここに示す実施形態に限定されることはなく、ここに開示の新規な特徴および原理と一致する最大範囲を与えられる。
【図１Ａ】
2015515661.tif 000027
【図１Ｂ】
2015515661.tif 000028
【図１Ｃ】
2015515661.tif 000029
【図２】
2015515661.tif 000030
【図３Ａ】
2015515661.tif 000031
【図３Ｂ】
2015515661.tif 000032
【図３Ｃ】
2015515661.tif 000033
【図４】
2015515661.tif 000034
【図５】
2015515661.tif 000035
【図６】
2015515661.tif 000036
【国際調査報告】
2015515661.tif 000037
2015515661.tif 000038