(57)【要約】  対象画像のオブジェクトを自動的に分類するシステムを提供する。分類システムは、画像の有力なオブジェクトの分類と共に分類画像のコレクションを提供する。分類システムは、分類画像に対する対象画像の類似度に基づいて対象画像のオブジェクトを分類しようと試みる。対象画像を分類するために、分類システムは、対象画像と分類画像との角点間の類似度に基づいて、最も対象画像に類似するコレクションの分類画像を識別する。分類システムは、対象画像に最も類似する分類画像に関連付けられた分類を、対象画像のオブジェクトの分類として選択する。
2010500688.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティング装置における対象画像のオブジェクトを分類するための方法であって、
分類画像と、前記分類画像に代表されるオブジェクトの分類を示す各分類画像の関連分類とを提供するステップと、
前記対象画像に最も類似する分類画像を識別するステップと、
識別された前記分類画像の分類に基づいて前記対象画像のオブジェクトの分類を選択するステップと
を備えることを特徴とする方法。
【請求項２】
分類画像の角点を識別するステップと、
類似する角点からこれらの角点を含む前記分類画像へのマッピングを生成するステップとを含む、請求項１に記載の方法であって、
分類画像を識別する前記ステップは、生成された前記マッピングを使用して、前記対象画像の角点に類似する角点を含む分類画像を識別すること
を特徴とする、請求項１に記載の方法。
【請求項３】
各角点は、ガウス（Ｇａｕｓｓｉａｎ）関数技術の差を使用して識別され、特徴ベクトルで表されることを特徴とする、請求項２に記載の方法。
【請求項４】
前記マッピングは、クラスタリング技術を使用して生成されることを特徴とする、請求項２に記載の方法。
【請求項５】
前記クラスタリング技術は、増殖セル構造アルゴリズムに基づくことを特徴とする、請求項４に記載の方法。
【請求項６】
前記対象画像に最も類似する分類画像を識別するステップは、
類似する角点に基づいて分類画像を一致画像として識別するステップと、
前記対象画像と前記一致画像との類似する角点に基づいて、前記対象画像と前記一致画像との類似度を計算するステップと
を含むことを特徴とする、請求項１に記載の方法。
【請求項７】
前記類似度は、数式：
【数１】
2010500688.tif 000013
に従って計算されることを特徴とする、請求項６に記載の方法。
【請求項８】
一致する角点間の配置と前記対象画像の類似する対応角点の配置とが不整合である時、前記一致画像をフィルタリングして除去するステップを含むことを特徴とする、請求項６に記載の方法。
【請求項９】
前記フィルタリングして除去するステップは、ＲＡＮＳＡＣベースのアルゴリズムの適用を含むことを特徴とする、請求項６に記載の方法。
【請求項１０】
分類画像の角点を識別するステップと、
類似する角点からこれらの角点を含む分類画像までのマッピングを生成するステップとを含む、請求項１に記載の方法において、
分類画像を識別する前記ステップは、生成された前記マッピングを使用して、前記対象画像の角点に類似する角点を含む分類画像を識別すること、および
分類画像を識別する前記ステップは、類似する角点に基づいて分類画像を一致画像として識別し、前記対象画像と前記一致画像との類似する角点に基づいて前記対象画像と前記一致画像との類似度を計算すること
を特徴とする、請求項１に記載の方法。
【請求項１１】
対象画像のオブジェクトを分類するためのコンピュータシステムであって、
オブジェクトの分類画像とオブジェクトの分類とを含む分類画像ストアと、
分類画像の角点の特徴ベクトルを分類画像にマッピングするインデックスを生成するコンポーネントと、
前記対象画像の角点の特徴ベクトルを生成するコンポーネントと、
生成された前記インデックスから、前記対象画像と分類画像との角点の特徴ベクトル間の類似度に基づいて前記対象画像と一致する分類画像を識別するコンポーネントと、
前記一致分類画像の分類に基づいて前記対象画像のオブジェクトを分類するコンポーネントと
を備えることを特徴とするコンピュータシステム。
【請求項１２】
インデックスを生成する前記コンポーネントは、分類画像の角点を識別し、前記角点の特徴ベクトルを生成するコンポーネントと、類似する特徴ベクトルのクラスタを生成するコンポーネントとを含むことを特徴とする、請求項１１に記載のコンピュータシステム。
【請求項１３】
前記角点は、ガウス（Ｇａｕｓｓｉａｎ）関数技術の差を使用して識別されることを特徴とする、請求項１２に記載のコンピュータシステム。
【請求項１４】
前記クラスタは、増殖セル構造アルゴリズムを使用して識別されることを特徴とする、請求項１２に記載のコンピュータシステム。
【請求項１５】
一致する分類画像を識別する前記コンポーネントは、その類似度が閾値の類似度以内にない一致画像を破棄するコンポーネントを含むことを特徴とする、請求項１１に記載のコンピュータシステム。
【請求項１６】
一致する分類画像を識別する前記コンポーネントは、その一致する角点間の配置と前記対象画像の対応角点の配置とが不整合である時、一致画像をフィルタリングして除去するコンポーネントを含むことを特徴とする、請求項１５に記載のコンピュータシステム。
【請求項１７】
前記対象画像のオブジェクトを分類する前記コンポーネントは、類似する角点の数に基づいて一致画像の分類を選択することを特徴とする、請求項１１に記載のコンピュータシステム。
【請求項１８】
分類画像の角点の特徴ベクトルを分類画像とそれらの分類にマッピングするインデックスを提供するステップと、
対象画像の角点の特徴ベクトルを生成するステップと、
提供された前記インデックスから、前記対象画像と分類画像との角点の特徴ベクトル間の類似度に基づいて、前記対象画像と一致する分類画像を識別するステップと、
前記一致分類画像の分類に基づいて前記対象画像のオブジェクトの分類を選択するステップと
を備えることを特徴とする方法により対象画像のオブジェクトを分類するために、コンピューティング装置を制御する命令を含むコンピュータ可読媒体。
【請求項１９】
一致する分類画像を識別する前記ステップは、前記対象画像と前記一致分類画像との類似する角点に基づいて、前記対象画像と前記一致分類画像との類似度を計算するステップを含むことを特徴とする、請求項１８に記載のコンピュータ可読媒体。
【請求項２０】
分類を選択する前記ステップは、前記一致分類画像の有力な分類を選択するステップを含むことを特徴とする、請求項１９に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
画像の自動分類は、ウェブページにより提供される画像が増加するにつれて、ますます重要になってきた。画像の分類には、多くの異なるアプリケーションがある。例えば、画像検索を行う検索エンジンサービスは、より効率的でより効果的な画像検索を行うために画像を分類しようと試みることができる。検索エンジンサービスは、画像を画像分類の階層（例えば、地理の階層、北米、合衆国など）に分類することができる。画像検索エンジンサービスにより、ユーザは検索要求（またはクエリ）と対象画像の分類の両方（例えば、「サンセット」のクエリと「北米」の分類）を特定することができる。この時、画像検索エンジンサービスは、検索をそれらの特定した分類内の画像に限定することができる。画像分類が役に立つ別の例は、ウェブマーケットプレイスである。ウェブマーケットプレイスにより、多くの小売業者が自分たちの製品を宣伝し、販売することができる。小売業者は、各製品に対して価格情報、製品説明、製品の画像を含む製品のデータベースを提供することができる。様々な小売業者が様々な方法で製品を記載してもよいので、その結果、マーケットプレイスシステムが販売できる製品を厳密に分類するのが難しい。マーケットプレイスシステムが製品の画像を分析することにより分類を効率的に識別できたら、マーケットプレイスシステムは製品の分類を助けるような分類を使用することができる。
【０００２】
多くの様々な技術が画像分類に適用されてきた。画像に近いテキストに基づいて画像を分類する技術もある。例えば、ウェブページは画像のタイトルや説明文を含む場合がある。このような技術の精度は、タイトルや説明文を正確に識別できる能力だけでなく、画像を表すタイトルや説明文の正確さに左右される。多種多様なウェブページの形式のために、画像に関するテキストを識別するのが難しい。また、画像に関するテキストは、分類に役立つ情報はほとんど提供できない場合がある。さらに、このような技術は、いろいろな小売業者が不十分で、あいまいで、不正確な説明をした時には、特にマーケットプレイスシステムに有用ではない。画像自身のコンテンツに基づいて画像を分類する技術もある。このような技術は、「ＣＢＩＲ」（コンテンツベースの画像検索）システムと呼ばれる。ＣＢＩＲシステムは、色、形状、テキストなどの特性に基づいて画像を分類しようと試みる。残念ながら、ＣＢＩＲシステムの精度は、画像の低レベルの特性からの分類を識別するのは難しいために十分でない。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｌｏｗｅ，Ｄ著、「Ｄｉｓｔｉｎｃｔｉｖｅ  Ｉｍａｇｅ  Ｆｅａｔｕｒｅｓ  ｆｒｏｍ  Ｓｃａｌｅ−ｉｎｖａｒｉａｎｔ  Ｋｅｙｐｏｉｎｔｓ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ出版、ｖｏｌ．６０．Ｎｏ．２  Ｐ９１〜１１０、２００４年
【非特許文献２】Ｆｒｉｔｚｋｅ，Ｂ著、「Ｇｒｏｗｉｎｇ  Ｃｅｌｌ  Ｓｔｒｕｃｔｕｒｅｓ−Ａ  Ｓｅｌｆ−Ｏｒｇａｎｉｚｉｎｇ  Ｎｅｔｗｏｒｋ  ｆｏｒ  Ｕｎｓｕｐｅｒｖｉｓｅｄ  ａｎｄ  Ｓｕｐｅｒｖｉｓｅｄ  Ｌｅａｒｎｉｎｇ」、Ｎｅｕｒａｌ  Ｎｅｔｗｏｒｋｓ出版、７（９）、Ｐ１４４１〜１４６０、１９９４年
【発明の概要】
【０００４】
対象画像のオブジェクトを自動的に分類するシステムを提供する。分類システムは、画像のオブジェクトの有力な分類と共に、分類画像のコレクションを提供する。分類システムは、分類画像に対する対象画像の類似度に基づいて対象画像のオブジェクトを分類しようと試みる。対象画像を分類するために、分類システムは、対象画像に最も類似する分類画像を識別する。分類システムは、類似度の基礎を対象画像と分類画像との角点間の類似度に置く。分類システムは、それぞれの角点を特徴ベクトルで表し、特徴ベクトル間の類似度を判断するために距離メトリックを使用する。分類システムは、対象画像と分類画像との類似度を判断するために、特徴ベクトルの距離メトリックから導かれる類似メトリックを使用する。分類システムは、対象画像に最も類似する分類画像に関連付けられた分類を対象画像のオブジェクトの分類として選択する。
【０００５】
「発明の概要」は、さらに以下の「発明を実施するための形態」で説明される概念を簡略化した形で紹介するためのものである。「発明の概要」は、請求される事項の重要な特徴または不可欠な特徴を特定するためのものではないし、請求される事項の範囲を決定するために使用されるものでもない。
【図面の簡単な説明】
【０００６】
【図１】一実施形態における分類システムのコンポーネントを示す図である。
【図２】一実施形態における特徴ベクトル／分類画像ストアの論理的表現を示す図である。
【図３】一実施形態における分類システムの画像分類を識別するオンラインコンポーネントの全体の処理を示すフロー図である。
【図４】一実施形態における分類システムのオンラインコンポーネントの一致画像発見コンポーネントの処理を示すフロー図である。
【図５】一実施形態における分類システムのオンラインコンポーネントの候補画像発見コンポーネントの処理を示すフロー図である。
【図６】一実施形態における分類システムのオンラインコンポーネントの類似度計算コンポーネントの処理を示すフロー図である。
【図７】一実施形態における分類システムのオンラインコンポーネントの分類選択コンポーネントの処理を示すフロー図である。
【発明を実施するための形態】
【０００７】
対象画像内のオブジェクトを自動的に分類するシステムを提供する。一実施形態において、分類システムは、画像のオブジェクトの有力な分類と共に画像コレクションを提供する。「オブジェクト」とは、画像内に描写されるもの（例えば、自動車、ラップトップコンピュータ、ライオン、ユニコーンなど）で、特に物質的なオブジェクトを指す。画像（「分類画像」）コレクションは、手動で画像の分類を行う、または正確であると分かっている製品説明を有する画像から自動的に分類を導き出すなどの種々の方法で生成することができる。例えば、画像コレクションは、ギターの分類と共にエレキギターの写真を含み、自転車の分類と共にマウンテンバイクの写真を含むことができる。分類システムは、コレクションの画像に対する対象画像の類似度に基づいて対象画像のオブジェクトを分類しようと試みる。対象画像を分類するために、分類システムは、対象画像に最も類似するコレクションの画像を識別する。例えば、対象画像は、クラシックギターの画像を含む場合もある。分類システムは、クラシックギターおよびエレキギターを含むコレクションの画像を最も類似するものとして識別することができる。次に、分類システムは、識別されたコレクションの画像に関連付けられた分類を対象画像のオブジェクトの分類として選択する。例えば、ほとんどの識別画像がギターの分類を有する場合、分類システムは対象画像のオブジェクトのためにギターの分類を選択する。このように、分類システムは、画像を囲む関連テキストの抽出の正確さ、または画像を表現する際のテキスト自身の正確さに依存することなく、画像のオブジェクトを自動的に分類することができる。
【０００８】
一実施形態では、分類システムは、オフラインコンポーネントとオンラインコンポーネントとを含む。オフラインコンポーネントは、対象画像に類似する画像の識別を容易にするために、分類画像を前処理する。オフラインコンポーネントは、分類画像の角点を識別し、分類画像の類似する角点からこれらの角点を含む分類画像へのマッピングを生成する。対象画像を分類するために、オンラインコンポーネントは、対象画像の類似する角点を識別し、類似する角点を有する分類画像を識別し、識別された分類画像の分類に基づいて対象画像の分類を選択する。
【０００９】
オフラインコンポーネントは、分類画像の角点の最初の識別により、分類画像を前処理する。角点は、ある画像を別の画像と区別するのに使用できるコンテンツを含むとして自動的に検出される画像領域のことである。例えば、ギターの画像内の角点は、ネック部に沿った種々の点（例えば、フレットおよび糸巻ペグ）および本体の種々の点（例えば、ブリッジ、ピックガード）を含んでもよい。以下で説明するように、このような角点を識別するのに多くの既知の技術が利用できる。オフラインコンポーネントは、各角点の特徴を表す特徴ベクトルを生成する。したがって、特徴ベクトルは角点の多次元表現である。例えば、角点の色やコントラストに基づいた特徴（またはエントリ）を含んでもよい。分類システムは、これらの特徴ベクトルの類似度に基づいて角点間の類似度を判断する。オフラインコンポーネントは、対応角点を含む分類画像への特徴ベクトルのマッピングを生成する。また、オフラインコンポーネントは、類似する特徴ベクトルをグループ化するインデックスを生成してもよい。オフラインコンポーネントは、インデックスを生成するために、クラスタリング技術を使用してもよい。類似する特徴ベクトルのクラスタリングにより、オンラインコンポーネントは、対象画像の角点に類似する分類画像の角点を素早く識別することができる。
【００１０】
オンラインコンポーネントは、オフラインコンポーネントにより生成されたインデックスやマッピングを使用して、対象画像のオブジェクトを分類する。オンラインコンポーネントは、オブジェクトを含む対象画像を受信し、対象画像の角点を識別し、各角点の特徴ベクトルを生成する。次に、オンラインコンポーネントは、インデックスやマッピングを使用して、例えば、特徴ベクトルの類似度に基づいて対象画像の角点に類似する１つまたは複数の角点を含む分類画像の候補分類画像を識別する。例えば、オンラインコンポーネントは、２０個の候補分類画像を識別することができる。対象画像のオブジェクトがエレキギターである時、２０個の候補分類画像はエレキギター、クラシックギター、テニスラケットの画像を含むことができる。オンラインコンポーネントは、対象画像と候補分類画像との類似度を評価して、類似度が閾値以下である候補分類画像を破棄する。例えば、オンラインコンポーネントは、エレキギターの対象画像とテニスラケットの分類画像とに類似する角点がわずかしかないと考えられるため、テニスラケットの画像を破棄する。次に、オンラインコンポーネントは、類似する角点の配置が対象画像の対応角点の配置と異なる（不整合である）候補分類画像をフィルタリングして除去することができる。例えば、対象画像は一列の数個の角点（例えば、ギターのネック部のフレット上に張られた弦）を有し、一致分類画像はグリッドに配置された類似する対応角点（例えば、テニスラケットの交差するストリング）を有する場合がある。この場合、オンラインコンポーネントは、不整合な配置のために、その候補分類画像を無視することができる。残りの候補分類画像は、一致分類画像のオブジェクトが対象画像のオブジェクトに一致すると考えられることから、一致分類画像と見なされる。オンラインコンポーネントは、一致分類画像の分類を分析し、対象画像のオブジェクトの分類を選択する。例えば、一致分類画像の大半が同じ分類を有する場合、オンラインコンポーネントはその分類を対象画像のオブジェクトの分類として識別する。一方、一致分類画像の分類の各々が一致分類画像の同じ数にほぼ関連付けられる場合、オンラインコンポーネントは、対象画像のオブジェクトを１つの分類に分類できないことを報告することができる。分類が階層分類である場合、オンラインコンポーネントはさらに複数の分類を分析して、それらが関連した分類（例えば、祖先および子孫、または兄弟関係の分類）を示すか否かを判断する。例えば、一致分類画像の分類がクラシックギターとエレキギターとの兄弟分類に等しく分けられる場合、オンラインコンポーネントは対象画像のオブジェクトをギターの親分類として分類することができる。また、一致分類画像の分類がギターとエレキギターとの親子分類に等しく分けられる場合、オンラインコンポーネントは対象画像のオブジェクトをエレキギターの子分類として分類することができる。
【００１１】
図１は、一実施形態における分類システムのコンポーネントを示す図である。分類システム１００は、オフラインコンポーネント１１０およびオンラインコンポーネント１２０を含む。オフラインコンポーネントは、分類画像ストア１１１と、特徴ベクトル抽出コンポーネント１１２と、特徴ベクトルによる分類インデックスコンポーネント１１３と、特徴ベクトル／分類画像ストア１１４とを含む。分類画像ストアは、分類と共に分類画像のコレクションを含む。特徴ベクトル抽出コンポーネントは、分類画像の角点を識別し、角点の特徴ベクトルを生成する。オフラインコンポーネントは、種々のタイプの検出器を使用して、分類画像の角点を識別してもよい。これらの検出器は、ガウス関数（「ＤｏＧ」（Ｇａｕｓｓｉａｎ））の差領域検出器、ヘシアンアファイン（Ｈｅｓｓｉａｎ−ａｆｆｉｎｅ）領域検出器、ハリスアファイン（Ｈａｒｒｉｓ−ａｆｆｉｎｅ）領域検出器、「ＭＳＥＲ」（最大安定外側領域）検出器、「ＩＢＲ」（強度に基づく極値領域）検出器、または「ＥＢＲ」（エッジに基づく領域）検出器を含んでもよい。分類システムは、上記した検出器以外の他の検出器を含む任意のタイプの検出器または検出器の複数のタイプを組み合わせた検出器を使用して実施してもよい。
【００１２】
一実施形態において、オフラインコンポーネント（およびオンラインコンポーネント）は、角点を識別し、スケールが不変の特徴変換技術を使用して特徴を抽出する。「ＳＩＦＴ」（スケールが不変の特徴変換）技術は、非特許文献１に示されており、これを参照として本明細書内に組み込む。Ｌｏｗｅ氏によるＳＩＦＴ技術は、画像のサイズや画像の多くの異なる変形（例えば、異なる透視角度や距離）に関係なく、正確に識別される画像の位置として角点を識別する。ＳＩＦＴ技術は、カスケード式フィルタリング手法を使用して、候補角点を識別する。ＳＩＦＴ技術は、全ての可能なサイズにわたって安定した特徴を検索することにより、同じオブジェクトの異なる視点から繰り返し配置できる位置を識別する。次に、ＳＩＦＴ技術は、各候補角点の位置、サイズ、主曲率に対する近似のデータへの詳細な適合を行う。ＳＩＦＴ技術は、低いコントラストを示し、エッジに沿ってはっきり局在しない候補角点を拒否する。次に、ＳＩＦＴ技術は、各角点の局所画像記述子（すなわち、「特徴」）を生成する。ＳＩＦＴ技術は、角点周囲の領域における各サンプル画像の勾配の大きさおよび向きの最初の計算により、向きの不変量である特徴を生成する。次に、ＳＩＦＴ技術は、これらのサンプルを４×４領域にコンテンツを集約するオリエンテーションヒストグラムに集める。各ヒストグラムは、異なる向きを表す８個のビンを有することができ、これが１２８（４×４×８）個の特徴ベクトルにより表される特徴となる。当業者は、画像の角点や角点の特徴を識別するのに他の技術が使用できることは理解できるであろう。
【００１３】
オフラインの特徴ベクトルによる分類インデックスコンポーネントは、対応する分類画像への特徴ベクトルのマッピングと特徴ベクトルのインデックスとを生成する。オフラインコンポーネントは、ツリーベース機構（例えば、Ｒツリー、ＳＳツリー、ＳＲツリー）、ハッシュベース機構（例えば、「ＬＳＨ」（局所性鋭敏型ハッシュ））、走査ベース方法（例えば、ＶＡ−ｆｉｌｅおよびＶＡ＋−ｆｉｌｅ）などの種々のタイプのインデックス機構を使用してもよい。一実施形態では、オフラインコンポーネントは、非特許文献２で示されるようなクラスタベースのインデックス技術を使用する。非特許文献２を参照として本明細書内に組み込む。オフラインコンポーネントは、以下の数式に従って、２つの特徴ベクトル間の距離（または２つの角点間の類似度）を計算することができる。
【００１４】
【数１】
2010500688.tif 000003
【００１５】
ここで、
【００１６】
【数２】
2010500688.tif 000004
【００１７】
は特徴ベクトルを表し、
【００１８】
【数３】
2010500688.tif 000005
【００１９】
および  
【００２０】
【数４】
2010500688.tif 000006
【００２１】
はＬ２ノルムを表す。
【００２２】
オンラインコンポーネントは、対象画像を受信し、一致分類画像を識別し、一致分類画像に関連付けられた分類に基づいて対象画像のオブジェクトの分類を選択する。オンラインコンポーネントは、特徴ベクトル抽出コンポーネント１２１と、候補画像発見コンポーネント１２３、候補画像ランク付けコンポーネント１２４、候補画像フィルタリングコンポーネント１２５を含む一致画像発見コンポーネント１２２と、分類選択コンポーネント１２６とを含む。特徴ベクトル抽出コンポーネントは、オフラインコンポーネントの特徴ベクトル抽出コンポーネント１１２に関して上述したように、対象画像の角点を識別し、角点の特徴ベクトルを生成する。一致画像発見コンポーネントは、対象画像に一致する分類画像を識別するために、特徴ベクトル／分類画像ストアを使用する。候補画像発見コンポーネントは、対象画像の角点に類似する角点を有する候補分類画像を識別する。候補画像ランク付けコンポーネントは、候補分類画像の対象画像との類似度をランク付けし、その類似度が閾値以下である候補分類画像を破棄する。一実施形態では、候補画像ランク付けコンポーネントは、以下の数式に従って、候補分類画像と対象画像との類似度を示す場合がある。
【００２３】
【数５】
2010500688.tif 000007
【００２４】
ここで、
【００２５】
【数６】
2010500688.tif 000008
【００２６】
は対象画像の特徴ベクトルを表し、
【００２７】
【数７】
2010500688.tif 000009
【００２８】
は分類画像の特徴ベクトルを表し、
【００２９】
【数８】
2010500688.tif 000010
【００３０】
は特徴ベクトル間の一致を測定するメトリックを表す。例えば、この一致は、
【００３１】
【数９】
2010500688.tif 000011
【００３２】
および
【００３３】
【数１０】
2010500688.tif 000012
【００３４】
のＬ２の逆距離値として数値的に計算することができる。一実施形態では、候補画像ランク付けコンポーネントは、１または０の２進値（１は類似する、０は類似しないとする）を使用して、類似する特徴ベクトルを識別する。あるいは、候補画像ランク付けコンポーネントは、一定の数または一定のパーセンテージの候補分類画像以外を破棄する、または他のデータの分類候補画像とはとうてい類似していない候補分類画像を破棄する。候補画像フィルタリングコンポーネントは、その角点の配置が対象画像の対応角点の配置と不整合である候補分類画像をフィルタリングして除去する。一実施形態では、候補画像フィルタリングコンポーネントは、ノイズをフィルタリングするための「ＲＡＮＳＡＣ」（Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ）アルゴリズムを使用する。これは、角点の幾何学的関係を立証する効果がある。候補画像フィルタリングコンポーネントは、ＲＡＮＳＡＣ分析に基づいて候補画像を再ランク付けしてもよい。分類選択コンポーネントは、候補分類画像を入力し、最も多い候補分類画像の分類に基づいて対象画像のオブジェクトの分類を選択する。しかし、その数が特定の閾値またはパーセンテージを超えない場合、分類選択コンポーネントは、分類が判断できなかったと表示することができる。あるいは、分類選択コンポーネントは、対象画像のオブジェクトの分類を選択する際に、候補分類画像の類似度を考慮に入れる場合がある。例えば、ギターの分類を有する５０の候補分類画像とエレキギターの分類を有する５０の候補分類画像の１００の候補分類画像があり、エレキギターの分類が対象画像とずっと高い類似度を有する場合、分類選択コンポーネントは、対象画像のオブジェクトとしてエレキギターの分類を選択する。
【００３５】
図２は、一実施形態における特徴ベクトル／分類画像ストアの論理的表現を示す図である。特徴ベクトル／分類画像ストアは、クラスタインデックスおよびクラスタテーブル２２０を含む、クラスタインデックスは、分類画像の（特徴ベクトルで表される）角点の各クラスタのエントリを含む。各エントリは、クラスタの代表的な特徴ベクトルおよび対応するクラスタテーブルを指し示すポインタを含んでもよい。代表的な特徴ベクトルは、クラスタ内の平均特徴ベクトル、クラスタの中間特徴ベクトル、クラスタの重心特徴ベクトルなどとしてもよい。各クラスタテーブルは、角点の特徴ベクトルと、角点を含む分類画像の参照とを含む。候補分類画像を識別するために、オンラインコンポーネントは、対象画像の角点の特徴ベクトルをクラスタインデックス内の代表的な特徴ベクトルと比較する。オンラインコンポーネントは、角点の特徴ベクトルに最も近い代表的な特徴ベクトルを選択し、対象画像の角点に最も近い角点を有するクラスタテーブルの対応分類画像を候補分類画像として選択してもよい。
【００３６】
分類システムを実装できるコンピューティング装置は、中央処理ユニット、メモリ、入力装置（例えば、キーボードおよびポインティング装置）、出力装置（例えば、表示装置）、記憶装置（例えば、ディスクドライブ）を含むことができる。メモリおよび記憶装置は、分類システムを実施する命令を含むコンピュータ可読媒体である。さらに、命令、データ構造、メッセージ構造は、通信リンク上の信号などのデータ伝送媒体を介して記憶または伝送することができる。イントラネット、ローカルエリアネットワーク、広域ネットワーク、またはポイントツーポイントダイアルアップ接続などの種々の通信リンクを使用してもよい。
【００３７】
分類システムは、パーソナルコンピュータ、サーバーコンピュータ、ハンドヘルドまたはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータを含む種々の操作環境、上述のシステムまたは装置のいずれかを含む分散コンピューティング環境などにおいて、およびこれらの環境により使用される。
【００３８】
分類システムは、１つまたは複数のコンピュータまたは他の装置により実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的な背景で説明できる。一般に、プログラムモジュールは、特定のタスクを実行し、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。一般的に、プログラムモジュールの機能性は、種々の実施形態で望ましいように組み合わせても、または分散されてもよい。例えば、オフラインコンポーネントおよびオンラインコンポーネントは、異なるコンピューティングシステムで実装されてもよい。さらに、オンラインコンポーネントは１つのコンピューティングシステムで実装されてもよく、オンラインコンポーネントを使用するアプリケーションは別のコンピューティングシステムで実装されてもよい。アプリケーションは、検索エンジンサービス、製品識別システム、画像分類システム、ロボットシステムなどを含んでもよい。検索エンジンサービスは、オンラインコンポーネントを使用して、ウェブをクロールする時に出会う画像の自動分類を支援することができる。また、検索エンジンサービスは、オンラインコンポーネントを使用して、クエリの一部として入力された画像を分類することができる。製品識別システムは、オンラインコンポーネントを使用して、製品の画像を含む製品説明から製品を分類することを支援することができる。画像分類システムは、オンラインコンポーネントを使用して、画像コレクションの画像を分類することができる。例えば、歴史的建造物を分類する画像分類システムは、画像を中国の万里の長城やワシントンモニュメントなどの分類に分類することができる。ロボットシステムは、システムが出会うオブジェクトを識別するのを助けるために画像を分類することができる。例えば、ロボットシステムは、識別されたオブジェクトを移動させ、対象のオブジェクトを配置するなどのために、識別されたオブジェクトをナビゲートする必要がある場合がある。
【００３９】
図３は、一実施形態における分類システムの画像分類を識別するオンラインコンポーネントの全体の処理を示すフロー図である。コンポーネントは、オブジェクトの対象画像を渡され、予め分類された画像に対する対象画像の類似度に基づいて対象画像のオブジェクトの分類を識別する。ブロック３０１では、コンポーネントは、対象画像の角点を識別し、各角点の特徴ベクトルを生成する。ブロック３０２では、コンポーネントは、一致画像発見コンポーネントを呼び出して、対象画像と最も一致する分類画像を識別する。ブロック３０３では、コンポーネントは、分類選択コンポーネントを呼び出して、一致分類画像の分類に基づいて対象画像の分類を選択する。次に、コンポーネントは、対象画像のオブジェクトの分類として、選択された分類を返す。
【００４０】
図４は、一実施形態における分類システムのオンラインコンポーネントの一致画像発見コンポーネントの処理を示すフロー図である。コンポーネントは、対象画像の角点の特徴ベクトルを渡され、分類画像の角点に対する特徴ベクトルの類似度に基づいて対象画像のオブジェクトの分類を返す。ブロック４０１〜４０３では、コンポーネントは、対象画像の角点に類似する角点を有する候補分類画像の識別処理をループする。ブロック４０１では、コンポーネントは、対象画像の次の角点（その特徴ベクトルで表される）を選択する。決定ブロック４０２では、対象画像の全ての角点がすでに選択された場合、コンポーネントはブロック４０４で処理を継続し、そうでなければ、コンポーネントはブロック４０３で処理を継続する。ブロック４０３では、コンポーネントは、候補画像発見コンポーネントを呼び出して、対象画像の選択された角点に類似する角点を有する分類画像を識別する。コンポーネントは、次に、ブロック４０１にループして、対象画像の次の角点を選択する。ブロック４０４〜４０６では、コンポーネントは、候補分類画像の選択処理および候補分類画像の対象画像との類似度の計算処理をループする。ブロック４０４では、コンポーネントは、次の候補分類画像を選択する。決定ブロック４０５では、全ての候補分類画像がすでに選択された場合、コンポーネントはブロック４０７で処理を継続し、そうなければ、コンポーネントはブロック４０６で処理を継続する。ブロック４０６では、コンポーネントは、類似度計算コンポーネントを呼び出して、選択された候補分類画像と対象画像との類似度を計算する。次に、コンポーネントはブロック４０４にループして、次の候補分類画像を選択する。ブロック４０７では、コンポーネントは対象画像と低い類似度を有する候補分類画像を無視する。ブロック４０８〜４１１では、コンポーネントは、角点の配置が対象画像の対応角点の配置と（例えば、幾何学的に）不整合な候補分類画像をフィルタリングして除去する処理をループする。ブロック４０８では、コンポーネントは次の候補分類画像を選択する。決定ブロック４０９では、全ての候補分類画像がすでに選択された場合、コンポーネントは、無視されなかった候補分類画像を一致分類画像として返し、そうでなければ、コンポーネントはブロック４１０で処理を継続する。ブロック４１０では、コンポーネントは、フィルタリング（例えば、ＲＡＮＳＡＣ）を適用して、角点の配置が対象画像の対応角点の配置と不整合である候補分類画像を識別する。ブロック４１１では、コンポーネントは、識別された候補分類画像を無視し、その後、ブロック４０８にループして次の候補分類画像を選択する。
【００４１】
図５は、一実施形態における分類システムのオンラインコンポーネントの候補画像発見コンポーネントの処理を示すフロー図である。コンポーネントは、対象画像の角点を渡され、候補分類画像を識別する。コンポーネントは、対象画像の角点に類似する角点と共に候補分類画像の表示を返す。対象画像の各角点に対して、コンポーネントは、分類画像の角点の最も類似するクラスタを識別する。次に、コンポーネントは、対象画像の角点に最も近いクラスタ内の角点を識別する。コンポーネントは、最も近い角点を識別するために、種々のアルゴリズムを使用してもよい。コンポーネントは、最も近い角点を含む分類画像に関係なく、Ｎ個の最も近い角点を識別するＮ−Ｎアルゴリズムを使用してもよい。したがって、Ｎ−Ｎアルゴリズムは、１つの分類画像の複数の角点を識別することができる。あるいは、コンポーネントは、最も近い角点を識別するが、各分類画像から１つの角点を識別するのみであるＮ−１アルゴリズムを使用してもよい。また、コンポーネントは、分類画像の一角点が分類画像の別の角点に近い時、類似しているとしてその角点を拒否する「ＡＲ」（Ａｍｂｉｇｕｉｔｙ  Ｒｅｊｅｃｔｉｏｎ）アルゴリズムを使用してもよい。ＡＲアルゴリズムは、対象画像の各角点が候補分類画像内の対応角点を１つだけ有するという前提に基づいている。ブロック５０１〜５０３では、渡された角点と各クラスタとの間の距離の計算処理をループする。ブロック５０１では、コンポーネントは次のクラスタを選択する。決定ブロック５０２では、全てのクラスタがすでに選択された場合、コンポーネントはブロック５０４で処理を継続し、そうでなければ、コンポーネントはブロック５０３で処理を継続する。ブロック５０３では、コンポーネントは、渡された角点から選択されたクラスタまでの距離を計算し、その後、ブロック５０１にループして次のクラスタを選択する。ブロック５０４では、コンポーネントは、渡された角点までの最小距離を有するクラスタを選択する。ブロック５０５〜５０９では、コンポーネントは渡された角点に近い選択されたクラスタの角点の識別処理をループする。ブロック５０５では、コンポーネントはクラスタの次の角点を選択する。決定ブロック５０６では、クラスタの全ての角点がすでに選択された場合、コンポーネントはブロック５１０で処理を継続し、そうでなければ、ブロック５０７で処理を継続する。ブロック５０７では、コンポーネントは、渡された角点から選択された角点までの距離を計算する。決定ブロック５０８では、その距離が閾値より小さい場合、コンポーネントはブロック５０９で処理を継続し、そうでなければ、コンポーネントはブロック５０５にループして、選択されたクラスタの次の角点を選択する。ブロック５０９では、コンポーネントは、クラスタの選択された角点を近い角点としてマーク付けし、その後、ブロック５０５にループして選択されたクラスタの次の角点を選択する。ブロック５１０〜５１３では、コンポーネントは、Ｎ−１アルゴリズムを使用して、候補として近い角点をマーク付けする処理および分類画像をマーク付けする処理をループする。ブロック５１０では、コンポーネントは、距離順で次に近い角点を選択する���距離順に選択することで、渡された角点に最も近い各分類画像の角点が確実に選択される。決定ブロック５１１では、全ての近い角点がすでに選択された場合、コンポーネントは、候補としてマーク付けされた分類画像をそれぞれのマーク付けされた角点と共に返し、そうでなければ、コンポーネントはブロック５１２で処理を継続する。オンラインコンポーネントは、マーク付けされた角点を使用して、対象画像と候補分類画像との類似度を判断する。決定ブロック５１２では、選択された近い角点の分類画像が予め候補としてマーク付けされた分類画像に対応する場合、コンポーネントは、次に近い角点を選択するために、ブロック５１０にループし、そうでなければ、コンポーネントはブロック５１３で処理を継続する。ブロック５１３では、コンポーネントは、選択された角点およびその分類画像を候補であるとしてマーク付けする。その後、コンポーネントはブロック５１０にループして次に近い角点を選択する。
【００４２】
図６は、一実施形態における分類システムのオンラインコンポーネントの類似度計算コンポーネントの処理を示すフロー図である。コンポーネントは、対象画像と候補分類画像とを渡され、画像間の類似度を計算する。ブロック６０１では、コンポーネントは類似度を０に初期化する。ブロック６０２〜６０７では、コンポーネントは、対象画像の角点の選択処理と候補分類画像とのマーク付けされた角点に基づく類似度の計算処理をループする。Ｎ−１アルゴリズムが使用される時でも、候補分類画像は複数のマーク付けされた角点を有する場合がある。例えば、候補分類画像が対象画像と全く一致する時、対象画像の各角点に対してマーク付けされた角点を有する場合がある。ブロック６０２では、コンポーネントは対象画像の次の角点を選択する。決定ブロック６０３では、対象画像の全ての角点がすでに選択された場合、コンポーネントは集められた類似度を返し、そうでなければ、コンポーネントはブロック６０４で処理を継続する。ブロック６０４では、コンポーネントは、候補画像の次のマーク付けされた角点を選択する。決定ブロック６０５では、候補分類画像の全てのマーク付けされた角点がすでに選択された場合、コンポーネントはブロック６０２にループして、対象画像の次の角点を選択し、そうでなければ、コンポーネントはブロック６０６で処理を継続する。ブロック６０６では、コンポーネントは、対象画像の選択された角点と候補分類画像との相関度を計算する。ブロック６０７では、コンポーネントは、対応を集積して類似度スコアを生成し、その後、ブロック６０４にループして候補分類画像の次のマーク付けされた角点を選択する。
【００４３】
図７は、一実施形態における分類システムのオンラインコンポーネントの分類選択コンポーネントの処理を示すフロー図である。コンポーネントは、一致分類画像を渡され、対象画像のオブジェクトの分類（すなわち、有力な分類）を選択するか、または分類が判断できないと示す。ブロック７０１〜７０４では、コンポーネントは、各分類を有する一致候補画像の数のカウント値を集める。ブロック７０１では、コンポーネントは次の一致分類画像を選択する。決定ブロック７０２では、全ての一致分類画像がすでに選択された場合、コンポーネントはブロック７０５で処理を継続し、そうでなければ、コンポーネントはブロック７０３で処理を継続する。ブロック７０３では、コンポーネントは、選択された一致分類画像の分類のカウント値をインクリメントする。ブロック７０４では、コンポーネントは、一致分類画像の全カウント値をインクリメントし、その後、ブロック７０１にループして次の一致分類画像を選択する。ブロック７０５では、コンポーネントは、一致分類画像の全カウント値で各分類のカウント値を割ることにより、分類のカウント値をパーセンテージに変換する。決定ブロック７０６では、最も高いパーセンテージが閾値より大きい場合、そのパーセンテージの分類は対象画像の候補分類であり、コンポーネントはブロック７０７で処理を継続し、そうでなければ、コンポーネントは、対象画像のオブジェクトの分類が判断できないとの表示を返す。決定ブロック７０７では、最も高いパーセンテージの分類と２番目に高いパーセンテージの分類との間の差が閾値より大きい場合、コンポーネントは一意に分類を識別し、高いパーセンテージを有する分類を対象画像のオブジェクトとして返し、そうでなければ、コンポーネントは、対象画像の分類が判断できないとの表示を返す。
【００４４】
事項は、構造的特徴および／または方法動作に特有な言葉で説明してきたが、付属の請求項で定義された事項は上述した特有の特徴や動作に必ずしも限定されないことは理解されたい。むしろ、上述した特有の特徴や動作は請求項を実装する形の例として開示されている。分類システムは、異なるコンポーネントを使用する、コンポーネントの処理順を変更するなどして実装してもよい。例えば、候補画像ランク付けコンポーネントと候補画像フィルタリングコンポーネントとの順序を交換してもよい。あるいは、オフラインコンポーネントは、コンピューティングシステムの処理力や分類の問題の性質に応じてオンラインで実装されてもよい。例えば、特徴ベクトル／分類画像ストアは、画像の新規の分類を反映するために、オンラインで徐々に更新して増加されてもよい。また、分類システムは、学習アルゴリズムを使用して、角点に基づいて対象画像を分類するために、分類子をトレーニングしてもよい。分類は、特徴ベクトル／分類画像ストアのデータをトレーニングデータとして使用して、分類子をトレーニングしてもよい。したがって、本発明は付属の請求項による場合を除き、限定されない。
【図１】
2010500688.tif 000014
【図２】
2010500688.tif 000015
【図３】
2010500688.tif 000016
【図４】
2010500688.tif 000017
【図５】
2010500688.tif 000018
【図６】
2010500688.tif 000019
【図７】
2010500688.tif 000020
【国際調査報告】
2010500688.tif 000021
2010500688.tif 000022