(57)【要約】【課題】パターンの表現、探索、及び／又は圧縮を実行するための方法及び装置を提供すること。【解決手段】一実施形態では、方法は、１つ又は複数の対象パターンを画像の一部から抽出するステップと、１つ又は複数の対象パターンに基づいてパターン行列を形成するステップと、パターン行列から導出された複雑度正規化表現を使用して、パターン行列を近似するステップと、クエリ内のベクトルを探して画像のライブラリを探索するためのクエリを送信して、１つ又は複数の対象パターンに類似する画像パッチを含むライブラリ内の画像を、複雑度正規化表現を使用して検出するステップとを含む。【選択図】  図５【特許請求の範囲】
【請求項１】
１つ又は複数の対象パターンを画像の一部から抽出するステップと、
前記１つ又は複数の対象パターンに基づいてパターン行列を形成するステップと、
前記パターン行列から導出された複雑度正規化表現を使用して、前記パターン行列を近似するステップと、
クエリ内のベクトルに対応する画像のライブラリを探索するために当該クエリを送信し、前記１つ又は複数の対象パターンに類似する画像パッチを含む前記ライブラリ内の画像を、前記複雑度正規化表現を使用して検出するステップと
を含む方法。
【請求項２】
実行された場合に、１つ又は複数のプロセッサに、
１つ又は複数の対象パターンを画像の一部から抽出するステップと、
前記１つ又は複数の対象パターンに基づいてパターン行列を形成するステップと、
前記パターン行列から導出された複雑度正規化表現を使用して、前記パターン行列を近似するステップと、
クエリ内のベクトルに対応する画像のライブラリを探索するために当該クエリを送信し、前記１つ又は複数の対象パターンに類似する画像パッチを含む前記ライブラリ内の画像を、前記複雑度正規化表現を使用して検出するステップと
を含む方法を実行させる命令が保存されたコンピュータ可読記憶媒体を備える製造物品。
【請求項３】
命令を保存するためのメモリと、
前記メモリに結合されたプロセッサであって、
１つ又は複数の対象パターンを画像の一部から抽出するステップと、
前記１つ又は複数の対象パターンに基づいてパターン行列を形成するステップと、
前記パターン行列から導出された複雑度正規化表現を使用して、前記パターン行列を近似するステップと、
クエリ内のベクトルに対応する画像のライブラリを探索するために当該クエリを送信し、前記１つ又は複数の対象パターンに類似する画像パッチを含む前記ライブラリ内の画像を、前記複雑度正規化表現を使用して検出するステップと
を含む方法を実行する命令を実行するためのプロセッサと
を備える装置。
【請求項４】
画像の非オーバラップブロックを抽出するステップと、
パターンのどの部分集合を圧縮するかを決定するステップと、
前記非オーバラップブロックからパターン行列を形成するステップと、
前記パターン行列を使用して複雑度正規化表現を導出するステップと、
分類マップ及びパターン基底を復号器に送って、再構成を可能にするステップと
を含む圧縮方法。
【請求項５】
サーバにおいて、関心領域を有する画像データを受け取るステップと、
複雑度正規化表現及び探索プログラムを使用して、前記サーバによってアクセスされたデータに対する前記関心領域のマッチングを実行するステップと
を含む方法。
【発明の詳細な説明】
【優先権】
【０００１】
[0001]本特許出願は、２００８年１０月３１日に出願された「Ｃｏｍｐｌｅｘｉｔｙ  Ｒｅｇｕｌａｒｉｚｅｄ  Ｐａｔｔｅｒｎ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ，  Ｓｅａｒｃｈ，  ａｎｄ  Ｃｏｍｐｒｅｓｓｉｏｎ」と題する対応する特許仮出願第６１／１１０４１８号、及び２００９年８月３日に出願された「Ｅｘｔｅｎｓｉｏｎｓ  ｔｏ  Ｃｏｍｐｌｅｘｉｔｙ  Ｒｅｇｕｌａｒｉｚｅｄ  Ｐａｔｔｅｒｎ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ，  Ｓｅａｒｃｈ，  ａｎｄ  Ｃｏｍｐｒｅｓｓｉｏｎ」と題する対応する特許仮出願第６１／２３０９３９号の優先権を主張し、これらの特許仮出願を参照により組み込む。
【技術分野】
【０００２】
[0002]本発明は、多様なパターン信号（例えば、画像、ビデオ、オーディオ、又は画像、ビデオ、オーディオから獲得される局所的なパッチ／領域など）の表現及び圧縮の分野に関し、より詳細には、本発明は、記述計算量（ｄｅｓｃｒｉｐｔｉｖｅ  ｃｏｍｐｌｅｘｉｔｙ）及び計算複雑度（ｃｏｍｐｕｔａｔｉｏｎａｌ  ｃｏｍｐｌｅｘｉｔｙ）を最低限に抑えて、圧縮、探索、及び検索のためにパターンを効率的に表す方法に関する。
【背景技術】
【０００３】
[0003]多くの応用例において、信号又は信号パッチの効率的な表現、探索、圧縮、及び検索に関心がもたれている。例えば、例ベースの画像（ビデオ）探索及び検索では、所定の画像（ビデオ）又はその様々な変更形式が画像（ビデオシーケンス）のライブラリ内に存在するかどうかを考える。そのような作業に取り組むため、一般には、例画像又はビデオからシグネチャを導出し、それをライブラリ内の画像及びビデオシーケンスのシグネチャと比較する。これらのシグネチャは、画像及びビデオシーケンスの線形表現及び非線形表現から獲得される。圧縮では、コンパクトな記述を提供することが期待される典型的な線形表現によって、画像／ビデオを表す。その後、これらの表現に関する画像／ビデオのパラメータが、画像の忠実な復元が構成される送り先に送られる。同様に、画像／ビデオの分析、認識などの応用例では、所定の表現に関して画像パラメータを考察し、これらのパラメータに関して問題を定式化する。
【０００４】
[0004]表現問題、探索問題、及び圧縮問題に取り組む既存の技法は、画像及びビデオシーケンスのモデル集合Ψ上で合理的に機能するように構成された表現によって定式化される。したがって、これらの技法の画像毎又はビデオシーケンス毎の適応性は、非常に限られたものであり、このことは、対象とする画像又はビデオシーケンスがモデル集合Ψに準拠していない場合、重大な問題となる。例えば、圧縮では、確立された技法は、離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）、ウェーブレット変換などの、固定された線形表現を使用する。そのような線形表現のためのモデル集合は、所定の表現を使用して僅かばかりの係数で高精度な近似が可能な画像／ビデオの集合である。例えば、ウェーブレット変換の場合、この集合は、点特異性（ｐｏｉｎｔ  ｓｉｎｇｕｌａｒｉｔｙ）を有する信号の集合であることがよく知られている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
[0005]既存の表現は、対象とする画像又はビデオシーケンスがそのモデル集合内にある場合は非常に良好に機能するが、モデル集合内にない場合は非常に不十分な性能を有する。例えば、図１に示されるようなテクスチャを描画する画像及びビデオシーケンス上では、そのような表現に基づいた技法の性能は、全く不十分なものになりがちであり、非常に非効率的な記述をもたらす。同様に、画像／ビデオの探索、分析、認識の応用例では、確立された技法は、単純な歪み／変形の下において、モデル集合上でかなり良好に機能することが期待される事前定義されたフィーチャを使用する。これらの技法は、アプリケーションが異なるタイプの歪みの下での操作を必要とする場合、全く不十分なものになり、計算的に複雑で、時には良好な性能を完全に阻害する非コンパクトな記述を生成する。これらの技法は、適応的ではなく、また一般に最悪ケースの性能に対して設計されるので、所定の狭い１組の信号、及び所定の１組の歪みに対しては最適でもなく、適切でもない。
【０００６】
[0006]既存の方法はまた、角を重要と判断する、線を重要と判断するなど、人間によって行われる画像の個別的（ａｄｈｏｃ）な観察に基づいているので、他のタイプの信号に一般化可能ではない。既存の方法は、人間の観察に基づいているので、オーディオデータ、地震データ、心電図などの医療信号、時系列データ、立体を描画するより高次元の医療画像など、異なるタイプの信号のためにフィーチャ／シグネチャ／表現をどうすべきかについて明瞭なガイドラインを提供しない。
【０００７】
[0007]確立された仕事に欠けている別の重要な問題は、圧縮、探索、回復などが成功するいかなる保証もないことである。既存の技法は、所定の大きさの計算複雑度に対しても、一定のレベルの成功を保証しない。例えば、無限の複雑度が許容される場合、その時は明らかに、非常に正確な探索／検索戦略を設計することができる。しかし、複雑度が制限される場合、最適なトレードオフを行うことによって、利用可能なリソースを有効に利用する必要がある。確立された技法は、許容される複雑度が制限される場合、最適なトレードオフを決して行わない。実際には、フィーチャは良好な性能をもたらすことを期待して個別的に設計されるので、複雑性問題は、直接的には対処されない。
【課題を解決するための手段】
【０００８】
[0008]本明細書では、パターンの表現、探索、及び／又は圧縮を実行するための方法及び装置が開示される。一実施形態では、方法は、１つ又は複数の対象パターンを画像の一部から抽出するステップと、１つ又は複数の対象パターンに基づいてパターン行列（ｐａｔｔｅｒｎ  ｍａｔｒｉｘ）を形成するステップと、パターン行列から導出された複雑度正規化表現（ｃｏｍｐｌｅｘｉｔｙ−ｒｅｇｕｌａｒｉｚｅｄ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）を使用して、パターン行列を近似するステップと、クエリ内のベクトルに対応する画像のライブラリを探索するために当該クエリを送信し、１つ又は複数の対象パターンに類似する画像パッチを含むライブラリ内の画像を、複雑度正規化表現を使用して検出するステップとを含む。
【図面の簡単な説明】
【０００９】
[0009]本発明については、以下に与えられる詳細な説明と、本発明の様々な実施形態の添付の図面から、より深い理解が得られるが、本発明の様々な実施形態は、本発明を特定の実施形態に限定するものと解釈されるべきではなく、もっぱら説明及び理解のためのものと解釈されるべきである。
【図１】テクスチャ画像の例を示す図である。
【図２】パターンバッグ（ｐａｔｔｅｒｎ−ｂａｇ）の構成において使用される例画像と、その変形の例を示す図である。
【図３Ａ】関心領域（ＲＯＩ：ｒｅｇｉｏｎ  ｏｆ  ｉｎｔｅｒｅｓｔ）の例を示す図である。
【図３Ｂ】関心領域（ＲＯＩ）の例を示す図である。
【図３Ｃ】ＲＯＩとオーバラップするブロックの例を示す図である。
【図３Ｄ】ＲＯＩとオーバラップするブロックの例を示す図である。
【図４】パターンバッグを構成するためのプロセスの一実施形態のフロー図である。
【図５】計算複雑度正規化分解（ｃｏｍｐｕｔａｔｉｏｎａｌ  ｃｏｍｐｌｅｘｉｔｙ  ｒｅｇｕｌａｒｉｚｅｄ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ）を使用して画像内のパターンを探索するためのプロセスの一実施形態のフロー図である。
【図６】合併された統計を計算するためのプロセスの一実施形態のフロー図である。
【図７】パターン存在統計（ｐａｔｔｅｒｎ  ｐｒｅｓｅｎｃｅ  ｓｔａｔｉｓｔｉｃｓ）を計算するためのプロセスの一実施形態のフロー図である。
【図８】記述計算量正規化分解（ｄｅｓｃｒｉｐｔｉｖｅ  ｃｏｍｐｌｅｘｉｔｙ  ｒｅｇｕｌａｒｉｚｅｄ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ）を使用して画像を圧縮するためのプロセスの一実施形態のフロー図である。
【図９】デルタを計算するためのプロセスの一実施形態のフロー図である。
【図１０】Ｔ及びＣ反復を計算するためのプロセスの一実施形態のフロー図である。
【図１１】最適化分解を計算するためのプロセスの一実施形態のフロー図である。
【図１２】正規化分解（ｎｏｒｍａｌｉｚｅｄ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ）を計算するためのプロセスの一実施形態のフロー図である。
【図１３】複雑度正規化分解を計算するためのプロセスの一実施形態のフロー図である。
【図１４】仮説検定のためのマッチ閾値を計算するためのプロセスの一実施形態のフロー図である。
【図１５】計算複雑度正規化分解を使用して、マスクされたパターンを探索するためのプロセスの一実施形態のフロー図である。
【図１６】新しい候補基底ベクトルを計算するためのプロセスの一実施形態のフロー図である。
【図１７】システムの一実施形態のブロック図である。
【図１８】歪み対複雑度グラフの一例を示す図である。
【発明を実施するための形態】
【００１０】
[0010]探索及び圧縮のための方法及び装置が説明される。実施形態は、複雑度を利用してその操作を制御する正規化パターンマッチング技法を使用する、これらの方法及び装置について説明する。
【００１１】
[0011]本発明の実施形態は、所定の１組の画像、ビデオシーケンス（これ以降、画像パッチ／ビデオパッチ）のための、特定の応用例において興味深いパッチ及びパッチのすべてのバージョンを含む（「パターンバッグ」と呼ばれる）パターン集合体（ｐａｔｔｅｒｎ  ｍａｎｉｆｏｌｄ）を構成する方法と、パターンバッグ内のパターンのための適応的な表現を設計する方法であって、適応的な表現は、パターンバッグ内のパターンの特性に合わせて緊密に調整され、最もコンパクトな方法でパターンを記述し、所定の記述計算量にとって最適にパターンを近似し、パターンバッグ内のパターンに関係する探索アプリケーション、分析アプリケーション、及び認識アプリケーションが最小の計算複雑度で成功裏に実行されることを可能にし、パターンバッグ内のパターンに関係する近似アプリケーション及び圧縮アプリケーションが最小の記述計算量で実行されることを可能にする、方法と、画像／ビデオのライブラリを効率的に探索して、パターンバッグ内のどのパターンがライブラリ内に存在するかを見出す方法と、探索及び検索が効率的になるようにライブラリを組織する方法と、パターンバッグ内のパターンを効率的に圧縮する方法とを含む。
【００１２】
[0012]本明細書で説明される技法は、信号の任意の組において最適化された探索アプリケーション、及び圧縮アプリケーションを構成することを可能にする、数学的ガイドライン、代数的設計方法、公式、及び最適化戦略を与える。
【００１３】
[0013]さらに、以下で開示される技法は、成功を正確に定義し、保証された性能をもたらす。以下で説明される技法は、成功と言えるアプリケーション性能と記述計算量／計算複雑度の間の最適なトレードオフを含む。また、提示される技法は、高度な並列化が可能であり、マルチコアプロセッサ、ＧＰＵなどの並列ハードウェア上で実施することができる。
【００１４】
[0014]本明細書の目的に沿って、画像上での操作を例示的な事例に使用する。オーディオ信号、ビデオ信号、音響信号、医療画像及び立体画像、時系列など、他のタイプの信号のための操作も同様に決定される。
【００１５】
[0015]以下の説明では、本発明のより完全な説明を提供するために、多くの詳細が説明される。しかし、本発明がこれらの特定の詳細なしでも実施できることは、当業者には明らかであろう。他の例では、よく知られた構造及びデバイスは、本発明を曖昧にしないために、詳細にではなく、ブロック図形式で示される。
【００１６】
[0016]以下の詳細な説明のいくつかの部分は、コンピュータメモリ内のデータビットに対する操作のアルゴリズム及びシンボル表現によって提示される。これらのアルゴリズムによる説明及び表現は、自分の仕事の内容を他の当業者に最も効果的に伝えるために、データ処理分野の当業者によって使用される手段である。アルゴリズムは、ここでは、また一般に、所望の結果に到達する自己矛盾のないステップの系列であると考えられる。ステップは、物理的量の物理的操作を必要とするステップである。必ずしも必要ではないが、通常は、これらの量は、保存し、転送し、組み合わせ、比較し、及び他の方法で操作することが可能な、電気的又は磁気的な信号の形態をとる。主として一般的な慣習上の理由で、これらの信号をビット、値、要素、シンボル、文字、項、又は数などと呼ぶことが便利であると分かることがある。
【００１７】
[0017]しかし、これらの用語及び類似の用語のすべては、適切な物理的量に関連付けられ、これらの量に付された単に便利なラベルであるにすぎないことに留意されたい。別途具体的に述べられない限り、以下の説明から明らかなように、説明の全体において、「処理する」、又は「計算する」、又は「算定する」、又は「決定する」、又は「表示する」などの用語を利用した説明は、コンピュータシステムのレジスタ及びメモリ内の物理的（電子的）量として表現されるデータを操作及び変形して、コンピュータシステムのメモリ若しくはレジスタ内の、又は他のそのような情報記憶デバイス、伝送デバイス、若しくは表示デバイス内の物理的量として同様に表現される他のデータにする、コンピュータシステム又は同様の電子的なコンピューティングデバイスのアクション及びプロセスを指すことが理解される。
【００１８】
[0018]本発明は、本明細書の動作を実行するための装置にも関する。この装置は、必要とされる目的のために特別に構成することができ、又はコンピュータに保存されたコンピュータプログラムによって選択的に活動化又は再構成される汎用コンピュータを含むことができる。そのようなコンピュータプログラムは、フロッピディスク、光ディスク、ＣＤ−ＲＯＭ、及び磁気光ディスクを含む任意のタイプのディスク、リードオンリメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード若しくは光カード、又は電子的命令を保存するのに適した任意のタイプの媒体などの、しかしそれらに限定されない、コンピュータ可読記憶媒体に保存することができ、各々は、コンピュータシステムバスに結合される。
【００１９】
[0019]本明細書で提示されるアルゴリズム及び表示は、特定のコンピュータ又は他の装置のいずれにも、本質的に関係しない。本明細書の教示に従ったプログラムとともに、様々な汎用システムを使用することができ、又は必要とされる方法ステップを実行するために、より専門的な装置を構成することが便利であると分かることもある。様々なこれらのシステムに必要とされる構造は、以下の説明から明らかとなる。加えて、本発明は、特定のプログラミング言語のいずれかに関連して説明されない。本明細書で説明される本発明の教示を実施するために、様々なプログラミング言語が使用できることが理解されよう。
【００２０】
[0020]機械可読媒体は、機械（例えばコンピュータ）によって可読な形式で、情報を保存又は伝送するための任意の機構を含む。例えば、機械可読媒体は、リードオンリメモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイスなどを含む。
（概要）
【００２１】
[0021]実施形態は、圧縮（「複雑度正規化パターン圧縮（Ｃｏｍｐｌｅｘｉｔｙ  Ｒｅｇｕｌａｒｉｚｅｄ  Ｐａｔｔｅｒｎ  Ｃｏｍｐｒｅｓｓｉｏｎ）」）アプリケーション、及び探索（「複雑度正規化パターン探索（Ｃｏｍｐｌｅｘｉｔｙ  Ｒｅｇｕｌａｒｉｚｅｄ  Ｐａｔｔｅｒｎ  Ｓｅａｒｃｈ）」）アプリケーションを対象とする、２つの一般的なアルゴリズムを含む。複雑度正規化パターン圧縮及び複雑度正規化パターン探索のアルゴリズムは、同様に、本明細書で「複雑度正規化パターン表現（Ｃｏｍｐｌｅｘｉｔｙ  Ｒｅｇｕｌａｒｉｚｅｄ  Ｐａｔｔｅｒｎ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）」アルゴリズムと呼ばれる第３のアルゴリズムに依存する。
【００２２】
[0022]これらのアルゴリズムを可能にする際の第１の操作は、本明細書ではパターンと呼ばれる画像パッチ／ビデオパッチの集合の定義及び構成を含む。一実施形態では、これは、列ベクトル形式で表される画像パッチ／ビデオパッチを抽出することによって実行され、抽出には、定義された関心領域の助けを借りることもあり得る。一実施形態では、抽出されたパッチは、辞書式順序を使用して順序付けられる。（行列Ｐの列に組織される）表現のためにこのように獲得されたパターンの集合は、本明細書では「パターンバッグ」とも呼ばれる。
【００２３】
[0023]複雑度正規化パターン探索のためのパターンバッグＰの構成が説明されるが、複雑度正規化パターン探索は、ユーザが画像を提供し、関心領域を指定し、提供された関心領域に類似する領域を表現するライブラリ内の画像の探索が行われる、例により探索を行う（ｓｅａｒｃｈ−ｂｙ−ｅｘａｍｐｌｅ）アプリケーションの助けを借りる。Ｐの構成は、１組の画像パッチ／ビデオパッチの収集を含むので、プロセスは、いくつかの画像、ビデオシーケンス、及び他のシナリオのために、簡単に一般化することができる。
【００２４】
[0024]ユーザが画像を提供し、関心領域（ＲＯＩ）を指定すると仮定する。ＲＯＩで指定される画像領域が、画像のライブラリ内で検出され、すなわち、ＲＯＩ内に描画された画像パッチに類似する画像パッチを含むライブラリ内の画像が、検出される。構成は、少なくとも部分的にＲＯＩとオーバラップする長方形のＷ×Ｈパッチを抽出することによって開始する。Ｗ及びＨは、例えば、４、８、１６、１７、２４、３１、１４３などとすることができる。一実施形態では、Ｗ及びＨは、ユーザによって指定される。非長方形パッチ、連結していないパッチの和集合などを抽出することもできる。一実施形態では、少なくとも部分的にＲＯＩとオーバラップするすべてのＷ×Ｈパッチが抽出され、これは、並進不変（ｔｒａｎｓｌａｔｉｏｎ  ｉｎｖａｒｉａｎｔ）操作を可能にし、すなわち、構成が、平行移動された画像と平行移動されたＲＯＩから開始する場合、同じパッチが抽出される。一代替実施形態では、最低限のオーバラップ制約を満たすように、パッチが抽出される。例えば、少なくとも部分的にＲＯＩとオーバラップし、偶数ピクセル位置にあるパッチを抽出することができる。ＲＯＩよりも小さなパッチ及び部分的にＲＯＩとオーバラップするパッチの抽出は、部分的な閉塞（ｏｃｃｌｕｓｉｏｎ）の場合に、アルゴリズムが、ＲＯＩの可視部分を検出する能力を有することを可能にする。一般に、抽出されるパターンのサイズが大きくなるほど、アルゴリズムが閉塞に対してロバストであることは期待できなくなる。他方で、非常に小さなパッチは、フォールスアラームを生じさせることが予想される。ＲＯＩとの必要最低限のオーバラップを有する指定サイズのすべてのパッチが、抽出され、ベクトルに配列され、パターンバッグに入れられる。
【００２５】
[0025]画像変形に対するロバスト性を保証するため、望ましい場合は、照明又は幾何学的変形、及び回転など、特定の操作を施された例画像のバージョンに対して、プロセスが繰り返される。図２は、パターンバッグの構成において使用される、例画像と、その変形の例を示している。図３Ａ〜図３Ｄは、関心領域の例と、ＲＯＩとオーバラップするブロックの例を示している。より具体的には、図３Ａは、画像上にマークされたＲＯＩを示しており、図３Ｂは、幾何学的な画像変形に一致するように変形された図３ＡのＲＯＩを示しており、図３Ｃは、少なくとも部分的にＲＯＩとオーバラップするＷ×Ｈブロックの例を示しており、図３Ｄは、完全にＲＯＩとオーバラップするＷ×Ｈブロックの例を示している。例えば、回転不変操作が望まれる場合、所望の回転範囲にわたって例画像を回転して、ｋ個の画像を生成することができ、生成画像の各々は、パターン抽出プロセスを経て、さらなる要素としてパターンバッグに投入される。回転及び幾何学的変形の場合、幾何学的変形を元に戻した場合に、変形画像内のＲＯＩが元の画像内で識別された領域と一致するように、ＲＯＩも適切に変形される。
【００２６】
[0026]図４は、パターンバッグを構成するためのプロセスの一実施形態のフロー図である。プロセスは、ハードウェア（例えば、専用ロジック、回路など）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる、処理ロジックによって実行される。プロセスは以下の通りである。
１．画像を受け取る（処理ブロック４０１）。
２．関心領域（ＲＯＩ）を決定する（処理ブロック４０２）。
３．ｉ＝１〜Ｎまで繰り返す。
変形ｉを画像に適用する（フィルタリング、照明、幾何学的など）
変形画像のためのＲＯＩを獲得する
変形画像においてＲＯＩとオーバラップするパターンを抽出する
抽出パターンをパターンバッグＰに追加する
（処理ブロック４０３）
４．パターンバッグＰを出力する
【００２７】
[0027]複雑度正規化圧縮のためのパターンバッグ構成は、サイズがＷ×Ｈの非オーバラップブロックが符号化（圧縮）される画像から抽出されることを除いて、上述の手順と同様である。この抽出操作は、サイズがＷ×Ｈのすべての非オーバラップブロックが抽出されるように行うこと、また非オーバラップブロックの一部のみが抽出されるように行うことなどができる。例えば、図１の画像のような一様な画像の場合、各ピクセルが１つのブロック内に存在するように、すべての非オーバラップブロックを抽出することができる。非一様な領域（例えば、テクスチャ画像上の顔画像）を描画する画像の場合、テクスチャ領域上の非オーバラップブロックのみを抽出することなどができる。一実施形態では、抽出プロセスは、圧縮の観点から最適な方法で行われ、すなわち、従来の表現を用いて良好に表される領域は従来の圧縮によって処理され、残りの領域が複雑度正規化圧縮によって処理される。そのようなプロセスの一例が、図８に示されており、図８は、以下でより詳細に説明される。
【００２８】
[0028]パターンバッグが構成されると、次の操作は、複雑度正規化表現の導出である。Ｍ個のパッチが抽出され、抽出されたＷ×Ｈパッチのすべては、Ｎ×Ｍ行列Ｐの列に配置されるベクトルとして、すなわち、各パターンがＮ個のピクセル値に対応するＭ個のパターンとして並べられると仮定する。その後の目標は、完全再構成（ｐｅｒｆｅｃｔ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ）の場合、
Ｐ＝Ｔ・Ｃ
をもたらす、Ｐの因数分解を表す行列Ｔ（Ｎ×Ｋ）及び行列Ｃ（Ｋ×Ｍ）を見出すことである。
【００２９】
[0029]本明細書の目的に沿って、Ｔの列は、パターン基底（ｐａｔｔｅｒｎ  ｂａｓｉｓ）と呼ばれ、Ｃの第ｉ列は、Ｐの第ｉのパターン（列）の基底展開係数（ｂａｓｉｓ  ｅｘｐａｎｓｉｏｎ  ｃｏｅｆｆｉｃｉｅｎｔ）を含む。ｔｉ、ｐｉ、αｉはそれぞれ、Ｔ、Ｐ、Ｃの第ｉ列を表すとする。Ｃ（ｌ，ｉ）は、Ｃの第ｌ行、第ｉ列の要素を表すとする。Ｋ個のパターン基底が存在すること、すなわち、
【数１】
2012507793.tif 000002
によって任意のパターンを表す際に、最大でＫ個の基底関数（ｂａｓｉｓ  ｆｕｎｃｔｉｏｎ）が利用されることに留意されたい。Ｋは、以下で説明されるように、最適なＴ、Ｃを設計するアルゴリズムによって決定される。
【００３０】
[0030]一実施形態では、複雑度正規化表現Ｔ及びＣの設計は、対象とする応用例に対して最適化される。表現の最適化について説明するため、最初に、複雑度正規化パターン探索アルゴリズム及び複雑度正規化パターン圧縮アルゴリズムが説明され、続いて、表現の設計についての詳細な説明が行われる。
（複雑度正規化パターン探索アルゴリズム）
【００３１】
[0031]複雑度正規化パターン探索アルゴリズムの一実施形態は、図５を併用して、以下のように要約することができる。図５のプロセスは、ハードウェア（回路、専用ロジックなど）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる、処理ロジックによって実行される。
【００３２】
[0032]図５を参照すると、プロセスは、目標複雑度（５１１）に基づいて、表現データＰに対して複雑度正規化分解を実行することによって開始する（処理ブロック５０１）。これは、出力としてＴ及びＣを生成し、Ｔ及びＣは、処理の残りの部分で以下のように使用される。
ｉ．ライブラリに属する与えられた画像に対して、候補Ｗ×Ｈパッチｓ（５１２）を抽出する。探索プロセスは、パターンバッグ内の任意のパターン（Ｐの任意の列）が近似的にｓに等しいかどうかをチェックする。一実施形態では、パターン基底及び候補パッチは、１（ｕｎｉｔｙ）に正規化され、すなわち、ｔｉＴｔｉ＝１、ｐｉＴｐｉ＝１、ｓＴｓ＝１である。別の実施形態では、正規化は行われない。便宜的に、本説明では、正規化が行われたと仮定する。
ａ．各パターンｐｉに対して、パッチｓ（５１２）との相関係数Ｙｉ＝ｓｔｐｉを見出す。どのパターンもＴ及びＣによって表すことができるので、このステップは、「複雑度正規化統計（Ｃｏｍｐｌｅｘｉｔｙ  Ｒｅｇｕｌａｒｉｚｅｄ  Ｓｔａｔｉｓｔｉｃｓ）」行列Ｚ（１×Ｋ）を
Ｚ＝ｓＴ・Ｔ
として生成し（処理ブロック５０２）、その後、すべてのパターンについての相関結果を獲得するために、この行列をＣと
Ｙ＝Ｚ・Ｃ
のように組み合わせる（処理ブロック５０３）ことと等価である。これは図６に示されている。
ｂ．Ｙ（１×Ｍ）が生成されると、ｉ＝１，…，Ｍのｉについて、「パターン存在統計」が、
Ｂｉ＝１−Ｙｉ２
として獲得される（処理ブロック５０４）。これは図７に示されている。
ｉｉ．パターンｉについて、パターン存在統計Ｂｉが閾値（５１２）と比較され、パターンｉがパッチｓ内に存在するかどうかが決定される（処理ブロック５０５）。一実施形態では、プロセスの出力に応じて、存在インジケータが、ｎｏ又はｙｅｓに設定される。
ｉｉｉ．プロセスは、画像に属するすべての候補パッチについて、及びライブラリ内のすべての候補画像について繰り返される。
【００３３】
[0033]‖Ａ‖０が行列Ａの非ゼロ項目の数を表すとする。すべてのパターンについてのすべての統計を計算するのに必要とされる操作の総数は、計算複雑度
Ｃ＝‖Ｃ‖０＋‖Ｔ‖０
に等しいことを示すことができる。
【００３４】
[0034]したがって、一実施形態では、この探索アプリケーションにとって最適な複雑度正規化表現は、処理ブロック５０１において、
【数２】
2012507793.tif 000003
として導出され、ここで、
【数３】
2012507793.tif 000004
は、Ｐ内の与えられたパターン集合を表す際に表現が有する歪みであり、‖Ｃ‖０＋‖Ｔ‖０は、この表現を用いる探索の複雑度を表し、λ≧０は、複雑度制約
【数４】
2012507793.tif 000005
を実施する正規化パラメータであり、Ｔ＊、Ｃ＊は、最適表現をもたらす。パターンバッグに最も近く、与えられた複雑度
【数５】
2012507793.tif 000006
で探索タスクを達成する表現が、求められる表現であることを、（１）の最適化によって観察されたい。一実施形態では、
【数６】
2012507793.tif 000007
は、探索が行われるプラットフォームに関して決定され、候補パッチ当たりの乗法／加法演算の許容可能数によって定量化される。
【数７】
2012507793.tif 000008
が増加することを許されると、
【数８】
2012507793.tif 000009
は減少し、それが今度は、パターン存在の完全な決定をもたらすことに留意されたい。
【数９】
2012507793.tif 000010
が低下すると、より多くのフォールスアラーム及びミスが探索中に生じることができ、それが、単純／高速な探索を行うための障害となる。
【００３５】
[0035]複雑度正規化パターン圧縮アプリケーションの場合、Ｐ内の各パターンが圧縮される高解像度のケースを以下のように考える。
ｉ．パターン基底はＰに固有であるので、Ｔは圧縮され、復号器に送られる必要がある。
ｉｉ．各パターンｐｉ（Ｐの第ｉ列）について、パターンの基底展開係数αｉ（Ｃの第ｉ列）は圧縮され、復号器に送られる必要がある。
【００３６】
[0036]図８は、記述計算量正規化分解を使用して画像を圧縮するためのプロセスの一実施形態のフロー図である。プロセスは、ハードウェア（例えば、専用ロジック、回路など）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる、処理ロジックによって実行される。プロセスは以下の通りである。
１．画像を取得する（処理ブロック８０１）。
２．ブロックを抽出する（処理ブロック８０２）。
３．ラグランジュ最適化（Ｌａｇｒａｎｇｉａｎ  Ｏｐｔｉｍｉｚａｔｉｏｎ）
【数１０】
2012507793.tif 000011
によって初期ブロック分類を実行する（処理ブロック８０３）。
４．ＣＢＣによって符号化されるブロックの場合、古典的なブロック符号化器を使用する（処理ブロック８０４）。
５．ＣＲＤによって符号化されるブロックの場合、複雑度正規化分解を使用する（処理ブロック８０５）。
６．符号化器を使用して、ブロック符号化器インジケータマップ（８１３）、Ｃｂ（８１５）、Ｔ、Ｃｒ（８１４）を符号化する（処理ブロック８０６）。
７．圧縮された画像ビットストリームを出力する（処理ブロック８１５）。
図８において、古典的なブロック符号化器（ＣＢＣ：ｃｌａｓｓｉｃａｌ  ｂｌｏｃｋ  ｃｏｄｅｒ）は、（離散コサイン変換（ＤＣＴ）などの）固定された基底Ｔｆｉｘｅｄを使用し、したがって、基底情報を復号器に送る必要はない。ブロック分類は、複雑度正規化分解ＣＲＤを用いるほうがより良く圧縮できるブロックと、ＣＢＣを用いるほうがより良く圧縮できるブロックとを決定する。そのような分類を行う一実施形態が、本出願において後で詳述される。
【００３７】
[0037]一実施形態では、圧縮プロセスを近似するために非線形近似モデルを使用して（Ａ．Ｃｏｈｅｎ、Ｉ．Ｄａｕｂｅｃｈｉｅｓ、Ｏ．Ｇ．Ｇｕｌｅｒｙｕｚ、Ｍ．Ｔ．Ｏｒｃｈａｒｄ、「Ｏｎ  ｔｈｅ  ｉｍｐｏｒｔａｎｃｅ  ｏｆ  ｃｏｍｂｉｎｉｎｇ  ｗａｖｅｌｅｔ−ｂａｓｅｄ  ｎｏｎｌｉｎｅａｒ  ａｐｐｒｏｘｉｍａｔｉｏｎ  ｗｉｔｈ  ｃｏｄｉｎｇ  ｓｔｒａｔｅｇｉｅｓ」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｖｏｌ．４８、ｎｏ．７、１８９５〜１９２１ページ、２００２年７月）、パターンバッグを表すための記述計算量
【数１１】
2012507793.tif 000012
を、Ｃ及びＴ内の非ゼロ値の数として、やはり、
【数１２】
2012507793.tif 000013
と近似することができる。
【００３８】
[0038]複雑度が実際の符号化器のレートといつでも直接比例するわけではないが、ほとんどの場合、レートと複雑度の間には高い相関がある。
【００３９】
[0039]これは、パターン探索及びパターン圧縮のどちらにしても、解く必要がある問題は、
【数１３】
2012507793.tif 000014
を最小化するＴ及びＣを見出すことであることを示しており、これは、Ｔ及びＣ内の非ゼロサンプルをできるだけ少数にして、Ｐ内のパターンの最も忠実な表現を得ることに対応する。
【００４０】
[0040]この最適化問題を解くため、Ｃ内の係数及びＴ内のパターン基底の更新を繰り返す反復プロセスが使用される。与えられた正規化パラメータλ≧０に対して、アルゴリズムは、パターンバッグＰ並びに初期行列Ｔｉｎｉｔ及びＣｉｎｉｔを受け入れ、その後、アルゴリズムは、以下のように、（１）の最適化問題を解くことに着手する。本明細書の目的に沿って、最小化される行列は、Δと呼ばれ、その結果、
【数１４】
2012507793.tif 000015
となる。これは図９に示されている。
【００４１】
[0041]与えられた初期行列に対して、Ｃの要素を、次にＴの要素を交互に更新する反復が最初に実行され、これを本明細書では「ＴＣ＿Ｉｔｅｒａｔｉｏｎｓ」と呼ぶ。「ＴＣ＿Ｉｔｅｒａｔｉｏｎｓ」内において、「Ｏｐｔｉｍｉｚｅｄ＿Ｄｅｃｏｍｐｏｓｉｔｉｏｎ」と呼ばれる手順が、メインの最適化計算を実行する。
【００４２】
[0042]手順［Ｔ，Ｃ］＝ＴＣ＿Ｉｔｅｒａｔｉｏｎｓ（Ｐ，Ｔ，Ｃ，，λ）の一実施形態が、処理ロジックによって実行され、図１０で説明されている。プロセスは、ハードウェア（例えば、専用ロジック、回路など）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる、処理ロジックによって実行される。プロセスは以下の通りである。
１．Δ１＝Δ（Ｐ，Ｔ，Ｃ，λ）を計算する（処理ブロック１００１）。
２．ｃｎｔ＝１と設定する（処理ブロック１００２）。
３．［Ｔ，Ｃ］＝Ｏｐｔｉｍｉｚｅｄ＿Ｄｅｃｏｍｐｏｓｉｔｉｏｎ（Ｐ，Ｔ，Ｃ，λ）を実行する（処理ブロック１００３）。
４．Ｒ＝ＰＴ
Ｑ＝ＣＴ
τ＝ＴＴ
と設定する（処理ブロック１００４）。
５．［Ｑ，τ］＝Ｏｐｔｉｍｉｚｅｄ＿Ｄｅｃｏｍｐｏｓｉｔｉｏｎ（Ｒ，Ｑ，τ，λ）を計算する（処理ブロック１００５）。
６．Ｃ＝ＱＴ
Ｔ＝τＴ
と設定する（処理ブロック１００６）。
７．Δ２＝Δ（Ｐ，Ｔ，Ｃ，λ）を計算する（処理ブロック１００７）。
８．ｃｎｔを１だけ増加させる（処理ブロック１００８）。
９．相対変化（Δ１−Δ２）／Δ１が与えられた閾値Ｔｈ＿Ｄよりも小さいかどうか（処理ブロック１００９）、又は反復の与えられた最大数に達したかどうか（処理ブロック１０１１）をチェックし、いずれでもない場合、Δ１＝Δ２と設定し（処理ブロック１０１２）、２に戻る（処理ブロック１０１３）。
１０．［Ｔ，Ｃ］＝Ｎｏｒｍａｌｉｚｅ＿Ｄｅｃｏｍｐｏｓｉｔｉｏｎ（Ｔ，Ｃ）（処理ブロック１０１０）。
１１．Ｔ、Ｃを返す。
【００４３】
[0043]手順が実行された後、様々な応用例に適合させるために、積ＴＣを保存する方法で、Ｔ及びＣを適切にスケーリングすることができる。一般性を失うことなく、スケーリングは、パターン基底が１に正規化されるような、すなわち、ｔｉＴｔｉ＝１となるようなものと仮定される。
【００４４】
[0044]与えられたＰ、Ｔ、Ｃ、λに対して、［Ｔ，Ｃ］＝Ｏｐｔｉｍｉｚｅｄ＿Ｄｅｃｏｍｐｏｓｉｔｉｏｎ（Ｐ，Ｔ，Ｃ，λ）を実行するためのプロセスの一実施形態が、図１１に示されており、ハードウェア（例えば、専用ロジック、回路など）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる処理ロジックによって実行される。プロセスは以下の通りである。
１．［Ｔ，Ｃ］＝Ｎｏｒｍａｌｉｚｅ＿Ｄｅｃｏｍｐｏｓｉｔｉｏｎ（Ｔ，Ｃ）（処理ブロック１１０１）。
２．Δ１＝Δ（Ｐ，Ｔ，Ｃ，λ）を計算する（処理ブロック１１０２）。
３．ｃｎｔ＝１と設定する（処理ブロック１１０３）。
４ａ．Ｃｉ（１×Ｍ）がＣの第ｉ行を表すとする。
４ｂ．Ｔの各列ｔｉ、ｉ＝１，…，Ｋについて繰り返す。
現在の表現の誤差を計算し、ｔｉの寄与を差し引く。
Ｅ＝Ｐ−Ｔ・Ｃ
Ｅｉ＝Ｅ＋ｔｉＣｉ
ｔｉとＥｉの列とのスカラ積を計算し、スカラ積と
【数１５】
2012507793.tif 000016
の間の閾値判定を以下のように実行する。
【数１６】
2012507793.tif 000017
ここで、
【数１７】
2012507793.tif 000018
４ｃ．Ｃの第ｉ行がＣｉ’になるように、すなわち、
Ｃｉ＝Ｃｉ’
と設定する（処理ブロック１１０４）。
５．Δ２＝Δ（Ｐ，Ｔ，Ｃ，λ）を計算する（処理ブロック１１０５）。
６．ｃｎｔを１だけ増加させる（処理ブロック１１０６）。
７．相対変化（Δ１−Δ２）／Δ１が与えられた閾値Ｔｈ＿Ｄよりも小さいかどうか（処理ブロック１１０７）、又は反復の与えられた最大数に達したかどうか（処理ブロック１１０８）をチェックし、いずれでもない場合、Δ１＝Δ２と設定し（処理ブロック１１０９）、処理ブロック１１０４に戻る。
８．Ｔ、Ｃを返す。
【００４５】
[0045]［Ｔ，Ｃ］＝Ｎｏｒｍａｌｉｚｅ＿Ｄｅｃｏｍｐｏｓｉｔｉｏｎ（Ｔ，Ｃ）手順の一実施形態が、図１２に示されており、ハードウェア（例えば、専用ロジック、回路など）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる処理ロジックによって実行される。プロセスは以下の通りである。
１．Ｔの各列ｔｉとＣの対応する行Ｃｉについて繰り返す。
ａ．η＝（ｔｉＴｔｉ）１／２
ｂ．ｔｉ＝ｔｉ／η
ｃ．Ｃｉ＝ηＣｉ
（処理ブロック１２０１）
２．Ｔ、Ｃを返す。
【００４６】
[0046]上では２つの手順を与えたが、図１３には、Δを最適化するための完全なアルゴリズムの一実施形態が示されている。プロセスは、ハードウェア（例えば、専用ロジック、回路など）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる、処理ロジックによって実行される。プロセスは以下の通りである。
１．Ｐ、Ｔｉｎｉｔ、Ｃｉｎｉｔ、λを取得する。
２．Ｔ＝Ｔｉｎｉｔ、Ｃ＝Ｃｉｎｉｔと設定する（処理ブロック１３０１）。
３．Δ１＝Δ（Ｐ，Ｔ，Ｃ，λ）を計算する（処理ブロック１３０２）。
４．［Ｔ，Ｃ］＝ＴＣ＿Ｉｔｅｒａｔｉｏｎｓ（Ｐ，Ｔ，Ｃ，λ）を実行する（処理ブロック１３０３）。
５．Ｔ行列を展開するための候補を見出す（処理ブロック１３０４）。
６．Ｅ＝Ｐ−Ｔ・Ｃを計算する（処理ブロック１３０５）。
７．［ｔｎｅｗ，αｎｅｗ］＝ＴＣ＿Ｉｔｅｒａｔｉｏｎｓ（Ｅ，ｔｎｅｗ，Ｃｎｅｗ，λ）を実行する（処理ブロック１３０７）。
８．
【数１８】
2012507793.tif 000019
を計算する（処理ブロック１３０８）。
９．Δ１＞Δ２であるかどうかを判定する（処理ブロック１３０９）。
ａ．Δ１＞Δ２である場合、
【数１９】
2012507793.tif 000020
、Δ１＝Δ２と設定し（処理ブロック１３１０）、処理ブロック１３０３に戻る。
ｂ．Δ１≦Δ２である場合、Ｔ、Ｃを返す。
ステップ５を実行する様々な方法の例が、段落［００７７］〜［００７８］及び図１６に示される。
（最適化スイープ（Ｏｐｔｉｍｉｚａｔｉｏｎ  Ｓｗｅｅｐ））
【００４７】
[0047]一実施形態では、λパラメータをスイープして、各λのための最適化Ｔ、Ｃペアを生成することによって、最適化が実行される。そのような場合、λは、１００００、１５７９１３．７３、ｍａｘ＿ｖａｌｕｅ×Ｎ１／２など、非常に高い値λｍａｘから開始して、７、１．１２、０．２３、０など、低い値λｍｉｎに向かって低下することができ、ここで、ｍａｘ＿ｖａｌｕｅは、８ビット画像の場合であれば２５５などの、ピクセルのための最大可能値である。一実施形態では、λは、λｍａｘからλｍｉｎまで線形に低下し、すなわち、λｎ＝λｎ−１−ｄλであり、ここで、ｄλ＝（λｍａｘ−λｍｉｎ）／ｍａｘ＿ｉｔｅｒ、ｎ＝１，２，…，ｍａｘ＿ｉｔｅｒ、及びλ０＝λｍａｘである。変数ｍａｘ＿ｉｔｅｒは、１０、１３、２０、１００など、又はスイープポイントの所望の数を決定する任意の値とすることができる。λは、非線形に低下することもできる。λ＝λｍａｘである場合、Ｔｉｎｉｔ及びＣｉｎｉｔは、ゼロ値のみを含む２つのベクトルとして設定することができる。Ｔｉｎｉｔは、１のみからなるベクトルに、又は他の何らかの非ゼロベクトル値に設定することもできる。ステージｎに対してアルゴリズムが実行されると、λｎに対して見出されたＴ及びＣの値は、ステージｎ＋１における、すなわち、λｎ＋１に対する最適化のためのＴｉｎｉｔ及びＣｉｎｉｔの値として使用することができる。
【００４８】
[0048]一実施形態では、スイープ手順は、ステージｎにおいて計算された複雑度
【数２０】
2012507793.tif 000021
が所望の複雑度を超えた場合に止められる。
【００４９】
[0049]一実施形態では、スイープ手順は、アプリケーションにおいて参照を容易にするための、ｎ、Ｔｎ、Ｃｎ、λｎ、
【数２１】
2012507793.tif 000022
、
【数２２】
2012507793.tif 000023
の値から成るルックアップテーブル（ＬＵＴ）を構成するのに使用された結果を含む全範囲について実行される。
【数２３】
2012507793.tif 000024
及び
【数２４】
2012507793.tif 000025
の値は、画像／ビデオのためのレート−歪み曲線（ｒａｔｅ−ｄｉｓｔｏｒｔｉｏｎ  ｃｕｒｖｅ）に類似した、パターンバッグのための曲線を構成するために使用することもできる。
（圧縮）
【００５０】
[0050]一実施形態では、すべてのパターン（例えば、サイズがＷ×Ｈのすべての非オーバラップブロック）が、画像から抽出され、符号化器は、複雑度正規化圧縮アルゴリズムを使用してパターンのどの部分集合を圧縮すべきかを決定する。一実施形態では、これは、パターンのすべてにわたって平均されたレート−歪み性能を最大化する方法で行われる。
【００５１】
[0051]一実施形態では、複雑度正規化圧縮アルゴリズムを用いて圧縮すべきパターンの分類は、以下のようにして決定される。すべての抽出パターンを使用して、複雑度正規化表現（Ｔ，Ｃ）が導出される。初期ブロック分類が、どのパターンが（離散コサイン変換ＤＣＴなどの）固定された非適応的な基底Ｔｆｉｘｅｄを使用してより良く表され、どのパターンが複雑度正規化分解から導出された基底であるＴを使用してより良く表されるかを決定する。この決定は、歪み
【数２５】
2012507793.tif 000026
を複雑度
【数２６】
2012507793.tif 000027
とラグランジュパラメータλを用いて結合したメトリック
【数２７】
2012507793.tif 000028
を使用して行われる。固定された基底の場合、固定された基底Ｔｆｉｘｅｄは事前に分かっているので、複雑度は、非ゼロ展開係数の数にのみ関係する。複雑度正規化分解の場合、復号器に複雑度正規化分解基底Ｔについて通知しなければならないので、Ｔ内の非ゼロ値もカウントする必要がある。したがって、組み合わされた複雑度
【数２８】
2012507793.tif 000029
は、１つ又は複数のパターンが複雑度正規化分解を使用すると仮定した場合、すべてのブロック（Ｔｆｉｘｅｄを使用するブロック及びＴを使用するブロック）上の非ゼロ展開係数の数と、Ｔ内の非ゼロ値の数とを加えたものになる。パターンのこの初期分類が行われた後、複雑度正規化表現を使用するものとして分類されたパターンのみを使用して、複雑度正規化表現を再導出することができる。
【００５２】
[0052]複雑度正規化表現が決定されると、レート−歪みを最適化するために、例えば、２００８年８月５日に出願された「Ｉｍａｇｅ  ａｎｄ  Ｖｉｄｅｏ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｕｓｉｎｇ  Ｓｐａｒｓｅ  Ｏｒｔｈｏｎｏｒｍａｌ  Ｔｒａｎｓｆｏｒｍｓ」と題する出願第１２／１８６４３９号、及び２００６年１２月２２日に出願された「Ｇｅｏｍｅｔｒｉｃａｌ  Ｉｍａｇｅ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ａｎｄ  Ｃｏｍｐｒｅｓｓｉｏｎ」と題する出願第１１／６４３９２５号に類似する方法を使用して、最終的な分類が行われる。分類マップ及びＴ内のパターン基底が、復号器に通知される。Ｔ及びＴｆｉｘｅｄに関する展開係数が、変換符号化（ｔｒａｎｓｆｏｒｍ  ｃｏｄｉｎｇ）手順と同様に通知される。
【００５３】
[0053]一実施形態では、上述の分類及び複雑度正規化表現の導出は、与えられた分類に対して表現が再導出され、続いて、与えられた表現を使用して再分類が行われて、最終的な複雑度正規化表現が得られるように、反復的に実行される。一実施形態では、反復は、先行する反復において見出されたＴ、Ｃの値が、次の反復のためのＴｉｎｉｔ及びＣｉｎｉｔとして使用されるように行われる。
【００５４】
[0054]一実施形態では、すべてのパターンが最初はＴｆｉｘｅｄを使用して表され、Ｔｆｉｘｅｄ領域において、複雑度正規化表現が導出される。
【００５５】
[0055]一実施形態では、上述のλは、
【数２９】
2012507793.tif 000030
が目標歪み
【数３０】
2012507793.tif 000031
と一致するように決定される。別の実施形態では、λはまた、
【数３１】
2012507793.tif 000032
が目標複雑度
【数３２】
2012507793.tif 000033
と一致するように決定される。これは、上で概説されたスイープ手順を使用して、又は２分法アルゴリズムを使用して行うことができる。
（パターン存在についての仮説検定）
【００５６】
[0056]一実施形態では、図５においてパターン存在統計を与えられた閾値Ｔｈと比較することによって、仮説検定が行われる。閾値の計算は、探索アルゴリズムに許容される所望の複雑度に基づいて行うことができる。所望の複雑度を使用して、複雑度正規化表現を使用するパターンバッグの表現からもたらされる、パターン毎の歪み又はパターン毎の歪みの平均を獲得することができる。図１４は、仮説検定のためのマッチ閾値を計算するためのプロセスの一実施形態のフロー図である。プロセスは、ハードウェア（例えば、専用ロジック、回路など）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる、処理ロジックによって実行される。プロセスは以下の通りである。
１．複雑度−歪みルックアップテーブルを生成する（処理ブロック１４０１）。一実施形態では、これは、上の段落００４９において説明されたように行われる。
２．複雑度−歪みルックアップテーブル１４０１を参照することによって、複雑度（１４１１）に基づいて歪みを計算する（処理ブロック１４０２）。
３．歪み及び雑音余裕ｍ（１４１２）に基づいて閾値
【数３３】
2012507793.tif 000034
を計算する（処理ブロック１４０３）。
４．閾値Ｔｈを出力する（処理ブロック１４１３）。
【００５７】
[0057]上述のような最適化スイープを実行し、結果の複雑度対歪み曲線から、又はＬＵＴ内に保存された値から、パターン毎の歪みを獲得することもできる。この歪みに適切な雑音余裕が追加されて、仮説検定において使用できる最終的な閾値が獲得される。雑音余裕は、シーンを撮影する際に使用されたカメラの特性に基づいて、シーン内に存在すると予想される雑音に基づいて、当技術分野でよく知られた雑音推定技法を使用して、又は例えば、ｍ２＝Ｎ５．１７、ｍ２＝Ｎ１７１．０２、ｍ２＝Ｎ１５３３など、他の何らかの値を使用して、決定することができる。
【００５８】
[0058]一実施形態では、パターン存在統計の成分が、導出された閾値に関して独立にチェックされて、例えば、パターンの少なくとも１つの存在を検出するための、存在インジケータを決定する。別の実施形態では、関心領域からパターンバッグが決定される場合、少なくとも所定数
【数３４】
2012507793.tif 000035
のパターンが一致したときに関心領域の存在が決定される。これは、対象画像内のＲＯＩのかなりの部分の存在を検定することを可能にする。
【００５９】
[0059]一実施形態では、ＲＯＩとオーバラップするパターンの幾何学的関係を考慮する組み合わされた方法で、閾値に関してパターン存在統計をチェックすることによって、仮説検定が行われる。例えば、ＲＯＩの面積の少なくとも指定されたパーセンテージを占めるパターンの存在、ＲＯＩの面積の少なくとも指定されたパーセンテージを占める連結パターンの存在などである。これは、閉塞が存在するときなどにＲＯＩを検出するために行われる。
＜代替的実施形態＞
（パターンマスク）
【００６０】
[0060]一実施形態では、パターンバッグ内の各パターンに対して、バイナリマスク（ｂｉｎａｒｙ  ｍａｓｋ）が定義される。Ｐの構成と同様に、これらのマスクは、Ｎ×Ｍ行列Ｗに組織され、図１５に示される図５のプロセスの変形において使用される。（１）の歪み
【数３５】
2012507793.tif 000036
は、
【数３６】
2012507793.tif 000037
と書くことができることに留意されたい。マスクが定義された場合、この歪み表現は、
【数３７】
2012507793.tif 000038
と変形され、ここで、Ｗ（ｊ，ｉ）は、重要と思われる各パターン内のピクセルと、それに関連する表現を選択する。この形式は、パターン内で描画される実際のピクセル値よりもパターンの形状がより重要である場合に重要である。マスクに適合させるため、探索手順は、２００７年１０月３０日に出願された「Ｓｐａｔｉａｌ  Ｓｐａｒｓｉｔｙ  Ｉｎｄｕｃｅｄ  Ｔｅｍｐｏｒａｌ  Ｐｒｅｄｉｃｔｉｏｎ  ｆｏｒ  Ｖｉｄｅｏ  Ｃｏｍｐｒｅｓｓｉｏｎ」と題する出願第１１／９２９４２０号において説明されるような、局所的なマッチング手法を使用するように変更することもできる。
【００６１】
[0061]これが、ｐ、ｑ＝０及びｒ、ｓ＝２として、以下の（７）によって近似できる複雑度をもたらすことを示すことができる。最適化手順は、
【数３８】
2012507793.tif 000039
及び
【数３９】
2012507793.tif 000040
のこれらのバージョンに適合するように変更される。
（ライブラリ）
【００６２】
[0062]一実施形態では、各パターン存在探索の結果を使用して、探索される次の画像／パッチを決定するように、ライブラリが組織される。例えば、Ｐ内でｓに最も近いパターンが距離ｄにある場合、ｓの距離ε内に存在する任意のパッチｓ’は、ｓ’まで少なくとも距離ｄ−εにあると推論することができる。したがって、画像のライブラリは、ｓ内におけるパターン存在の探索の出力を利用して、探索をライブラリ内に狭めることができるように、構造化されたベクトル量子化（ＶＱ：ｖｅｃｔｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ）ディクショナリの組織と同様に組織することができる。これは、例えば、ライブラリの初期部分集合上で探索を行い、部分集合内においてパターンバッグまでの距離が最小のｋ個の距離を有する画像／パッチを見出し、それらの近傍内の画像／パッチに探索を集中することによって、ＶＱ探索技法と同様に行うことができる。
【００６３】
[0063]一実施形態では、ライブラリ画像は、ユーザの地理的な位置、要求時の天候、加速度計、ジャイロスコープ、及びユーザデバイスによって供給される他のデータに基づいて、フィルタリングされ、選択され、処理される。ユーザクエリのパターンも同様に、より正確でより高速なマッチングを可能にするために、フィルタリング及び処理を行い、例えば、コントラストの向上、主軸への幾何学的な歪曲などを行うことができる。
（変換領域／ピクセル領域表現）
【００６４】
[0064]一実施形態では、上述の表現アルゴリズム、探索アルゴリズム、及び圧縮アルゴリズムは、変換領域において実行することができる。変換領域は、ウェーブレット変換領域、複素ウェーブレット変換領域、ＤＣＴ領域、ガボール変換（Ｇａｂｏｒ  ｔｒａｎｓｆｏｒｍ）領域などとすることができる。この場合、パターンバッグＰ、パターンが探索される画像ｓは、変換領域において指定される。これは、これらの量のピクセル領域表現上での所望の変換を評価し、変換された量を使用して複雑度正規化表現を導出することによって、行うことができる。これは、例えば、より僅かな保存量で画像をライブラリに保存できるようにすることによって、最適ではないが、それでも計算／圧縮性能の助けとなる、コンパクトな記述を利用することを可能にする。複雑度正規化圧縮の場合、対象画像は最初に変換され、変換されたパッチ上でアルゴリズムが実行される。
【００６５】
[0065]画像の拡張的（ｅｘｐａｎｓｉｖｅ）又は過完備（ｏｖｅｒｃｏｍｐｌｅｔｅ）なサブバンド分解を実行し、個々のサブバンドから抽出されたパターンを使用して探索アルゴリズムを進め、最後にサブバンド探索結果を組み合わせることもできる。
（複雑度メトリック）
【００６６】
[0066]一実施形態では、メトリック
【数４０】
2012507793.tif 000041
は、複雑度メトリック
【数４１】
2012507793.tif 000042
を使用して最適化され、ここで、Ａ１、Ａ２、ｐ、ｑ、ｒ、ｓは、非負の定数であり、ｑ＞０に対して、
【数４２】
2012507793.tif 000043
であり、ｐ＞０に対して、
【数４３】
2012507793.tif 000044
である。別の実施形態では、メトリック
【数４４】
2012507793.tif 000045
は、歪みメトリック
【数４５】
2012507793.tif 000046
を使用して最適化され、ここで、Ｕ及びＶは、アプリケーション固有の重み行列である。
（パターン毎の歪み）
【００６７】
[0067]パターン毎の保証を与えるため、一実施形態では、最悪の表現歪みを有するパターンが、与えられた量
【数４６】
2012507793.tif 000047
よりも小さい歪みを有するように、複雑度正規化分解が導出される。
【数４７】
2012507793.tif 000048
よりも小さい歪みを有するすべてのパターンの展開係数も調整されて、展開係数の数を削減及び／又は最小化し、すなわち、可能な場合、パターンの歪みが
【数４８】
2012507793.tif 000049
を超えないときは展開係数が廃棄され、パターンの歪みが
【数４９】
2012507793.tif 000050
を超えるときは展開係数が追加される。
（並列ハードウェア実施）
【００６８】
[0068]一実施形態では、探索、圧縮、及び表現のためのすべての計算は、マルチコアプロセッサ、グラフィックス処理ユニットなど、並列ハードウェアにおいて実施される。パターン存在統計、ＴＣ＿ｉｔｅｒａｔｉｏｎｓの計算など、アルゴリズムの主要コンポーネントは、容易に並列化可能であることに留意されたい。
（ビデオ圧縮アプリケーション）
【００６９】
[0069]一実施形態では、複雑度正規化圧縮アルゴリズムは、アルゴリズムをＩＮＴＲＡフレーム及びＩＮＴＥＲフレームに独立に適用することによって、ハイブリッドビデオ圧縮に適用される。一実施形態では、複雑度正規化圧縮アルゴリズムは、ＩＮＴＲＡフレームに適用され、パターン基底Ｔが導出され、復号器に送られる。その後、そのＩＮＴＲＡフレームに依存するすべてのＩＮＴＥＲフレームは、別個のＴを導出することなく、導出されたＴを利用する。一実施形態では、ＩＮＴＲＡフレームに依存する各ＩＮＴＥＲフレームについて、新しいパターン基底が導出されるかどうか、又はＩＮＴＲＡフレームのために導出され、送られた基底が使用されるかどうかを指定する信号が送られる。別の実施形態では、各ＩＮＴＥＲフレームについて、パターン基底が導出され、ＩＮＴＲＡフレームのために導出され、送られたパターン基底に基づいて条件付きで符号化される。一実施形態では、各ＩＮＴＲＡ／ＩＮＴＥＲフレームパターン基底情報は、先に符号化されたパターン基底のすべて又は一部に基づいて条件付きで符号化される。一実施形態では、先のフレームのために計算されたパターン基底は、現在のフレームパターン基底の計算のためのＴｉｎｉｔとして使用される。
（Ｐ内の列のベクトル量子化）
【００７０】
[0070]一実施形態では、パターンバッグＰの列は、Ｐ内の列（パターン）の数を削減する方法で、列のベクトル量子化バージョンによって表される。これは、より少数のパターンに対して相関係数Ｙｉ＝ｓｔｐｉが計算されることを可能にすることによって、計算複雑度を低減する。これが今度は、複雑度正規化表現が単純化され、ライブラリＳを探索する場合により少数の計算しか必要としないことを可能にする。実際には、量子化プロセスは、Ｐを取り、それを、行数は同じだが列はより少ない行列Ｐｖｑで置き換える。Ｐｖｑの列は、セントロイド（ｃｅｎｔｒｏｉｄ）と呼ばれる。Ｐ内の各パターンは、その量子化バージョンと本明細書で呼ばれるセントロイドに関連付けられる。Ｐｖｑの列ｊに関連付けられる（又は列ｊを中心にクラスタ化する）Ｐのすべての列は、列ｊのクラスタを形成する。この関連付けは、Ｐの代わりにＰｖｑが探索され、Ｐｖｑの列ｊがライブラリパターンと一致することが分かった場合、Ｐｖｑの列ｊに量子化される（又は列ｊを中心にクラスタ化する）Ｐ内のすべての列が、そのライブラリパターンと一致すると見なされるといったものである。上述のベクトル量子化（ＶＱ）プロセスは、例えば、ｋ平均（ｋ−ｍｅａｎｓ）アルゴリズム、修正ｋ平均（ｍｏｄｉｆｉｅｄ  ｋ−ｍｅａｎｓ）アルゴリズム、ロイド−マックス（Ｌｌｏｙｄ−Ｍａｘ）アルゴリズム、リンデ−ブゾー−グレイ（Ｌｉｎｄｅ−Ｂｕｚｏ−Ｇｒａｙ）アルゴリズムなど、当技術分野において十分に確立された技法によって実行することができる。修正ｋ平均アルゴリズムは、２つ（以上）のセントロイド（クラスタ）を有して開始し、（以下で説明される）アルゴリズムを終了するための条件が満たされない場合、条件が最終的に満たされるまで、クラスタの数が増加する。
【００７１】
[0071]一実施形態では、クラスタセントロイドのための初期化は、パターンバッグＰからランダムに選択された２つ以上のパターンによって達成される。
【００７２】
[0072]以下のように説明される条件を有するループが存在する。
ＬＯＯＰ：ｋ平均が収束するまで、与えられたセントロイドを用いてｋ平均を実行する。
（以下で説明される）条件が満たされない場合、１つ以上のセントロイドを追加し、追加される各セントロイドは、パターンバッグから、そのクラスタのセントロイドからの平方距離に比例する確率で、ランダムに選択されたパターンとすることができる。
（以下で説明される）条件が満たされる場合、ループを脱出し、セントロイド及びクラスタメンバシップ情報を返す。
【００７３】
[0073]ループを脱出するための条件は、パターンから割り当てられたセントロイドまでの平均距離が与えられた正数εよりも小さい場合、パターンから割り当てられたセントロイドまでの最大距離がεよりも小さい場合などとして確立することができる。
（ＶＱ中のオーバラップクラスタの可能性）
【００７４】
[0074]各パターンをただ１つのクラスタに所属させる代わりに、一実施形態では、パターンバッグに属するパターンは、すなわち、Ｐの列は、（以下で説明される）クラスタメンバシップの条件が満たされる限り、より多くのクラスタに所属することができる。そのようなオーバラップクラスタリングのシナリオでは、Ｐの列ｉがＰｖｑの列ｊ及び列ｋにクラスタ化される場合、ライブラリパターンと一致するｊ又はｋが見出されれば、ｉはそのライブラリパターンと一致すると見なされる。一実施形態では、クラスタメンバシップのための条件は、クラスタセントロイドからのパターンの距離が与えられたε＞０よりも小さい場合、パターンはそのクラスタのメンバになることができるというものや、パターンに最も近いセントロイドを有するクラスタとして選択された与えられたｌ個（ｌ≧１）のクラスタのメンバであることなどとすることができる。
（探索方法の連続的近似）
【００７５】
[0075]Ｐを使用して探索を行う代わりに、Ｐを最初に、そのＶＱ表現Ｐｖｑによって近似し、それを今度は、計算複雑度正規化表現Ｐｖｑ⇒ＴｖｑＣｖｑによって表現する。最初に、マッチングセントロイド／クラスタの探索が、ＴｖｑＣｖｑを使用して実行される。マッチングクラスタが決定されると、マッチングクラスタ内でマッチを探すために、アルゴリズムが開始する。アルゴリズムは、例えば、すべてのセントロイド近似が、すなわち、ライブラリパターンまでの距離がε’≧０よりも小さいＴｖｑＣｖｑの列が、マッチを宣言されるなど、いくつかの基準に基づいて、さらなる探索のために２つ以上のクラスタを伝えることができる。各クラスタｉのクラスタメンバは、上で開示された技法を使用して、そのクラスタ内のパターンを使用して決定される、それ自体のＴｉＣｉによって表される。ＴｖｑＣｖｑを使用してマッチングクラスタが見出されると、ＴｉＣｉ及び０≦ε”≦ε’を使用して、すべてのマッチングクラスタｉ上で順々に探索を継続することによって、より細やかな探索が行われる。各クラスタ内でマッチングパターンが見出され、そのようなすべてのパターンがマッチと見なされる。
【００７６】
[0076]一実施形態では、連続的近似アルゴリズムは、近似の２つ以上のレベルを通るように、すなわち、より多くの近似レイヤを有するように行われる。そのようなシナリオでは、クラスタのメンバは、そのＶＱ表現によってさらに近似され、上で説明された連続的近似探索は、近似が粗いものから精緻なものになるような方法で繰り返される。
（新しい候補基底ベクトルを表現に追加する異なる方法）
【００７７】
[0077]図１６は、新しい候補基底ベクトルを計算するためのプロセスの一実施形態のフロー図である。プロセスは、ハードウェア（例えば、専用ロジック、回路など）、（汎用コンピュータシステム若しくは専用マシン上で実行される）ソフトウェア、又は両方の組み合わせを含むことができる、処理ロジックによって実行される。プロセスは以下の通りである。
１．Ｅ＝Ｐ−ＴＣ（処理ブロック１６０２）。
２．Ｅｄｏｔ＝ＥＥＴ（処理ブロック１６０３）。
３．固有値Ｑ及び対応する単位ノルム固有ベクトルＶを見出す。
（Ｅｄｏｔ＝ＶＱＶＴ）
［Ｖ，Ｑ］＝ｅｉｇ（Ｅｄｏｔ）
（処理ブロック１６０５）
４．最大固有値に対応する固有ベクトルｖ＊を取得する。
ｔｎｅｗ＝ｖ＊
ｃｎｅｗ＝［１  １…１］
（処理ブロック１６０４）
５．ｔｎｅｗ、ｃｎｅｗを出力する。
【００７８】
[0078]図１６のプロセスでは、固有分解を使用する代わりに、例えば、現在の表現の誤差の加重平均を使用する、最大平方ノルムを有する誤差ベクトルを選択する、誤差ベクトルをランダムに選択するなど、他の方法で、テンプレートベクトルの初期化を行うこともできる。
（異なる因数分解）
【００７９】
[0079]一実施形態では、複雑度正規化表現は、
【数５０】
2012507793.tif 000051
、ｎｃ≧１の形式の因数を使用する、より精緻な因数分解によって計算される。例えば、加法的因数分解（ａｄｄｉｔｉｖｅ  ｆａｃｔｏｒｉｚａｔｉｏｎ）が以下のように実行される。
【数５１】
2012507793.tif 000052
、Ｎｆ≧１、すべてのｉについて、ｎｉ≧１
【００８０】
[0080]この場合、次に式（３）のメトリックが以下のように計算される。
【数５２】
2012507793.tif 000053
（探索プログラムの生成）
【００８１】
[0081]入力画像及びマークされたＲＯＩに基づいて、アルゴリズムは、Ｐ内のパターンのＶＱ、結果のクラスタセントロイドのＴＣ分解に加えて、与えられた複雑度制約に基づいた個々のクラスタのＴＣ分解を計算する。アルゴリズムは、セントロイドの数を（例えば０からＭまで）徐々に増加させ、歪みを低減させる、一連のＶＱ点を計算することによって、それを行う。各ＶＱ点は、歪み及び複雑度に対応し、複雑度は、セントロイドの数にＮを乗じたものに等しい。計算された各ＶＱ点に対して、アルゴリズムは、λを増加させることによって、いくつかのＴＣ分解を計算する（図１８を参照）。アルゴリズムが採用できるすべての決定は、歪み対複雑度曲線上で見つけ出すことができ、アルゴリズムは、そのようなすべての曲線をプロットし、目標複雑度（歪み）レベルにおいて、最小の歪み（複雑度）をもたらす点を見出す。図１８は、そのような曲線の一例を示している。その点を決定するパラメータ（ＶＱパラメータ、連続的近似パラメータ、ＴＣ分解パラメータなど）は、特定の探索を行う際にアルゴリズムによって使用されるパラメータである。この操作は、アルゴリズムが、連続的近似を使用すべきかどうか、使用する連続的近似のレベルなども決定するように行われる。
【００８２】
[0082]連続的近似レベル、ＶＱ点、ＴＣ分解などの結果の１組が、探索プログラムを形成する。本明細書の目的に沿って、最小の複雑度で探索を実行する方法においてアルゴリズムが選択するパラメータ及び行列は、探索プログラムと呼ばれる。
（テクスチャのために適合されたマッチング）
【００８３】
[0083]一実施形態では、マッチングプロセスが、テクスチャを探索するために適合される。これは、開示されたままのアルゴリズムによって、又はマッチ行列を変更することによって行うことができる。マッチ行列は、例えば、以下のように変更することができる。複雑度正規化表現が計算されると、与えられたライブラリベクトルｓ上で、ｚ＝ｓＴ・Ｔが計算される。ｚ内の要素は、
【数５３】
2012507793.tif 000054
を使用して閾値判定され、閾値判定後の非ゼロ値の数がカウントされる。この結果が、任意のパターンベクトル近似
【数５４】
2012507793.tif 000055
の非ゼロ係数の数に、すなわち、Ｃ行列の第ｉ列内の非ゼロ係数の数に一致する場合、ｓは、そのパターンベクトルに一致すると宣言される。
（βの使用）
【００８４】
[0084]パッチｐｉと信号ｓｊの間の類似性の計算は、スケーリング係数βを用いて、以下のように実行することができ、
【数５５】
2012507793.tif 000056
ここで、βは、
【数５６】
2012507793.tif 000057
の所定の部分集合に、例えば、０．９から１．１の間、及び−１．１から−０．９の間に限定される。
（対象マッチングアルゴリズム）
【００８５】
[0085]距離行列
【数５７】
2012507793.tif 000058
が獲得されると、それは辞書的に順序付けられ、行列Ｂが乗じられ、対象マッチングのための判定値が生成される。乗算の結果は、閾値判定を施され、対象検出結果に到達する。一実施形態では、Ｂは以下のように生成され、すなわち、パターンの部分集合が、対象又はシーンの特定の外観に対応すると仮定する。次に、ライブラリ内で同様のパターンが見出された場合、対象又はシーンマッチを宣言することができる。そのような対象／シーンマッチ条件は、一連のマッチングペアによって指定することができ、すなわち、あるＦ＞０について、ｓｉ１が
【数５８】
2012507793.tif 000059
に一致し、ｓｉ２が
【数５９】
2012507793.tif 000060
に一致し、…、ｓｉＦが
【数６０】
2012507793.tif 000061
に一致する場合に、対象の外観がライブラリ内で見出されたと言うことができる。
【数６１】
2012507793.tif 000062
は、ｓｉが
【数６２】
2012507793.tif 000063
とどれだけ良く一致するかを定量化するので、対象の第ｋの外観のマッチングのための条件を、
【数６３】
2012507793.tif 000064
によって獲得することができる。一実施形態では、Ｂは、バイナリ行列であり、一致すべき関連するパターンペアを単純に選択する。別の実施形態では、Ｂは、実数の値を含む行列である。一実施形態では、行列Ｂは、所定の計算複雑度に合わせて対象外観マッチングを計算することもできるように、
【数６４】
2012507793.tif 000065
によっても近似される。
【数６５】
2012507793.tif 000066
は、本明細書で説明される技法を使用することによって、
【数６６】
2012507793.tif 000067
によって計算することができる。
（異なる表現及び領域における画像）
【００８６】
[0086]画像は、パターン抽出及び本発明の実施形態の他の技法の適用に先立って、事前フィルタリング（例えば、ノイズ除去、局所的ＤＣ成分除去など）を行うことができ、又は元の形式で使用することができる。
（行列乗算を含む様々な問題への複雑度正規化表現の適用）
【００８７】
[0087]多くの問題で、与えられたベクトルにＸｎ行列Ｐを乗じたいことがある。本発明の実施形態の表現及び技法は、Ｐをその複雑度正規化表現によって置き換えることによって、これらの問題において、計算を著しく加速させるために使用することができる。そのような問題の一例は、Ｐｔによる再帰的乗算が実行される、ｘｎ＋１＝Ｐｔｘｎ＋ｂといった再帰的計算である。開示された分解Ｐ〜ＴＣ（及びその様々な改良形）を使用して、計算における乗算と加算の回数を著しく低減することができる。
（クラウドコンピューティングプラットフォーム上でのアルゴリズムの実行）
【００８８】
[0088]一実施形態では、クラウドコンピューティングプラットフォーム上で、適合形態又はその部分が実行される。ライブラリパターン、すなわち、行列Ｓは、分散方法でクラウドコンピューティングプラットフォーム上に保存される。ユーザがマークされたＲＯＩを有する画像を送ると、そこからＰが抽出され、そのＰ上で複雑度正規化表現が計算され、ＳとＰの間のマッチの探索がクラウド上で実行される。Ｐの抽出及び複雑度正規化表現の生成は、クラウド上で直接に、又はユーザのデバイス（例えばモバイルデバイス）上で実行することができる。後者の場合、複雑度正規化表現がクラウドに送られる。クラウドは、マッチング結果をユーザに返し、マッチが見つかった場合、ユーザは、見つかった対象についての情報と、元の画像内におけるその位置を受け取る。
【００８９】
[0089]代替的に、Ｐをクラウドコンピューティングプラットフォーム上に保存し、ユーザがＳを、すなわち、ユーザ画像形式Ｓを送る。この実施形態は、Ｐのための複雑度正規化表現及び探索プログラムが、非常に迅速な探索結果のため、オフラインで計算され、保存されることを可能にする。ユーザがＳを送ると、Ｐのための保存された探索プログラムがＳに適用され、すなわち、Ｓのために複雑度正規化表現を計算することなく、探索結果が生成される。別の代替実施形態では、複雑度正規化表現が、Ｐ及びＳの両方のために個々に計算され、結果のペアが、ＰｔＳ計算を近似するために使用される。
（固定小数点数演算）
【００９０】
[0090]一実施形態では、ＴＣ分解及び他の因数分解が、行列内の値が固定小数点数に制約されるように計算される。これは、マッチング計算において固定小数点数演算が適用されることを可能にする。
（オフラインで計算される複雑度正規化表現）
【００９１】
[0091]一実施形態では、環境はオフラインで撮像される。環境内の関心のある対象にラベルが付けられ、各対象についてＲＯＩが導出される。その後、各対象について複雑度正規化表現及び探索プログラムが導出され、サーバ内に保存される。これらの導出及び保存のすべては、オフラインで行われる。その後、同じ環境を撮像したユーザが、獲得した画像／ビデオ上でＲＯＩをマークし、又はＲＯＩが、ユーザ画像／ビデオ上で自動的に検出される。画像データ及びＲＯＩは、サーバに送られ、サーバにおいて、保存されたデータに対してマッチングが実行される。マッチ及びマッチング対象のラベルが、ユーザに返される。この実施形態は、本発明内で開示された表現に関連する計算がオフラインで行われることを可能にする。
＜システムの例＞
【００９２】
[0092]図１７は、本明細書で説明された操作の１つ又は複数を実行できる例示的なコンピュータシステムのブロック図である。図１７を参照すると、コンピュータシステム１７００は、例示的なクライアント又はサーバコンピュータシステムを含むことができる。コンピュータシステム１７００は、情報を伝達するための通信機構又はバス１７１１と、情報を処理するための、バス１７１１と結合されたプロセッサ１７１２とを含む。プロセッサ１７１２は、マイクロプロセッサに限定されないが、例えば、ペンティアム（Ｐｅｎｔｉｕｍ）（商標）、パワーＰＣ（ＰｏｗｅｒＰＣ）（商標）、アルファ（Ａｌｐｈａ）（商標）などのマイクロプロセッサを含み、２つ以上のプロセッサ、又はマルチコア若しくはマルチスレッド機能を有するプロセッサを含むことができる。
【００９３】
[0093]システム１７００は、情報又はプロセッサ１７１２によって実行される命令を保存するための、バス１７１１に結合されたランダムアクセスメモリ（ＲＡＭ）又は他の動的記憶デバイス１７０４（メインメモリと呼ばれる）をさらに含む。メインメモリ１７０４は、プロセッサ１７１２による命令の実行中に一時変数又は他の中間情報を保存するために使用することもできる。
【００９４】
[0094]コンピュータシステム１７００は、プロセッサ１７１２のための静的情報及び命令を保存するための、バス１７１１に結合されたリードオンリメモリ（ＲＯＭ）及び／又は他の静的記憶デバイス１７０６と、磁気ディスク又は光ディスク及び対応するディスクドライブなどのデータ記憶デバイス１７０７も含む。データ記憶デバイス１７０７は、情報及び命令を保存するために、バス１７１１に結合される。
【００９５】
[0095]コンピュータシステム１７００は、情報をコンピュータユーザに表示するための、バス１７１１に結合された、ブラウン管（ＣＲＴ）又は液晶ディスプレイ（ＬＣＤ）などのディスプレイデバイス１７２１にさらに結合することができる。英数字キー及び他のキーを含む英数字入力デバイス１７２２も、情報及びコマンド選択をプロセッサ１７１２に伝達するために、バス１７１１に結合することができる。さらなるユーザ入力デバイスは、方向情報及びコマンド選択をプロセッサ１７１２に伝達するため、並びにディスプレイ１７２１上でカーソルの動きを制御するための、バス１７１１に結合された、マウス、トラックボール、トラックパッド、スタイラス、又はカーソル方向キーなどのカーソルコントロール１７２３である。
【００９６】
[0096]バス１７１１に結合できる別のデバイスは、ハードコピーデバイス１７２４であり、ハードコピーデバイス１７２４は、紙、フィルム、又は類似のタイプの媒体上に情報をマークするために使用することができる。バス１７１１に結合できる別のデバイスは、電話又はハンドヘルドパームデバイスと通信するための、有線／無線通信機能１７２５である。
【００９７】
[0097]システム１７００のコンポーネント及び関連ハードウェアのいずれか又はすべてを、本発明で使用できることに留意されたい。しかし、コンピュータシステムの他の構成が、デバイスのいくつか又はすべてを含み得ることが理解できよう。
【００９８】
[0098]上述の説明を読んだ後では、当業者には疑いもなく本発明の多くの代替形態及び変更形態が明らかとなるが、例示によって示され、説明された任意の特定の実施形態は、決して限定と見なされることを意図したものではないことを理解されたい。したがって、様々な実施形態の詳細についての言及は、本発明にとって本質的と見なされる特徴のみをその中で列挙した特許請求の範囲を限定することを意図していない。
【図１】
2012507793.tif 000068
【図２】
2012507793.tif 000069
【図３】
2012507793.tif 000070
【図４】
2012507793.tif 000071
【図５】
2012507793.tif 000072
【図６】
2012507793.tif 000073
【図７】
2012507793.tif 000074
【図８】
2012507793.tif 000075
【図９】
2012507793.tif 000076
【図１０】
2012507793.tif 000077
【図１１】
2012507793.tif 000078
【図１２】
2012507793.tif 000079
【図１３】
2012507793.tif 000080
【図１４】
2012507793.tif 000081
【図１５】
2012507793.tif 000082
【図１６】
2012507793.tif 000083
【図１７】
2012507793.tif 000084
【図１８】
2012507793.tif 000085
【手続補正書】
【提出日】平成23年6月2日(2011.6.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１つ又は複数の対象パターンを画像の一部から抽出するステップと、
前記１つ又は複数の対象パターンに基づいてパターン行列を形成するステップと、
前記パターン行列から導出された複雑度正規化表現を使用して、前記パターン行列を近似するステップと、
クエリ内のベクトルに対応する画像のライブラリを探索するために当該クエリを送信し、前記１つ又は複数の対象パターンに類似する画像パッチを含む前記ライブラリ内の画像を、前記複雑度正規化表現を使用して検出するステップと
を含む方法。
【請求項２】
前記対象パターンが、画像パッチである、請求項１に記載の方法。
【請求項３】
前記１つ又は複数の対象パターンを抽出するステップが、画像の前記一部を１組のオーバラップパッチに分解するステップを含む、請求項１に記載の方法。
【請求項４】
パターンの抽出に先立って、前記画像内の関心領域を選択するステップをさらに含み、前記関心領域が、前記画像の前記一部である、請求項１に記載の方法。
【請求項５】
前記パターン行列が、前記１つ又は複数の対象パターンと、前記１つ又は複数の対象パターンの変更バージョンとを含む、請求項１に記載の方法。
【請求項６】
生成する変更バージョンの数が、前記探索の所定の複雑度に基づいて決定される、請求項５に記載の方法。
【請求項７】
前記画像の前記一部について１組の変更バージョンを生成するステップと、
追加の対象パターンを各変更バージョンから抽出するステップと、
前記対象パターンおよび前記追加の対象パターンから行列を生成するステップと
をさらに含む、請求項５に記載の方法。
【請求項８】
前記画像の前記一部について１組の変更バージョンを生成するステップが、１つ又は複数の幾何学的な変形及び歪みを前記画像の前記一部に適用するステップを含む、請求項５に記載の方法。
【請求項９】
前記パターン行列の近似に先立って、前記パターン行列を処理して、類似のベクトルを除去するステップをさらに含む、請求項１又は５に記載の方法。
【請求項１０】
処理が、ベクトル量子化を使用して実行される、請求項９に記載の方法。
【請求項１１】
前記パターン行列内の少なくとも１つのパターンが、複数のクラスタに所属し、さらに、前記パターン行列内の列がそれを中心にクラスタ化する、前記パターン行列のベクトル量子化バージョンにおける列のいずれかが、前記ライブラリ内のパターンとマッチする場合に、前記ライブラリ内のパターンのマッチが発生する、請求項１０に記載の方法。
【請求項１２】
前記パターン行列を近似するステップが、前記パターン行列の２つの行列への因数分解を実行するステップを含む、請求項１に記載の方法。
【請求項１３】
前記複雑度正規化表現が、探索に許容される計算複雑度に依存するマッチング精度に基づいて導出される、請求項１に記載の方法。
【請求項１４】
前記複雑度正規化表現が、パターン基底と係数行列とを含む、請求項１に記載の方法。
【請求項１５】
前記パターン行列を近似するステップが、最適化ルーチンを実行して、前記探索の前記計算複雑度を示す与えられた計算複雑度インジケータに対してマッチング精度に反比例する尺度を最小化することに基づいて、前記係数行列内の係数及び前記パターン基底を更新するステップを含む、請求項１４に記載の方法。
【請求項１６】
計算複雑度インジケータが、制約に依存する、請求項１５に記載の方法。
【請求項１７】
前記制約が、ラグランジュ乗数を含む、請求項１６に記載の方法。
【請求項１８】
前記複雑度正規化表現によって表される各パターンについて、前記ライブラリから抽出されたパッチとの相関係数を見出すステップと、
相関係数からパターン存在統計を生成するステップと、
各パターンについて、前記各パターンのパターン存在統計を閾値と比較して、前記各パターンが前記パッチ内に存在するかどうかを判定するステップと
を含む操作を実行するステップをさらに含む、請求項１に記載の方法。
【請求項１９】
前記複雑度正規化表現によって表される各パターンについて、前記ライブラリから抽出された前記パッチとの前記相関係数を見出すステップが、複雑度正規化統計行列を生成することと、前記複雑度正規化統計行列を前記複雑度正規化表現の１つのディスクリプタと組み合わせて、すべてのパターンについての相関結果を獲得することとを含む、請求項１８に記載の方法。
【請求項２０】
前記画像からのすべての候補パッチ及び前記ライブラリ内のすべての候補画像に対して前記操作を繰り返すステップをさらに含む、請求項１８に記載の方法。
【請求項２１】
パターン存在統計に基づいて少なくとも１つのパターンの存在を判定するステップをさらに含む、請求項１に記載の方法。
【請求項２２】
前記近似されたパターン行列と前記ライブラリの間の所定数のマッチングに基づいて、前記一部が前記ライブラリ内に存在すると判定するステップをさらに含む、請求項１に記載の方法。
【請求項２３】
前記パターン行列の近似に先立って、前記パターン行列内の各パターンにバイナリマスクを適用するステップをさらに含む、請求項１に記載の方法。
【請求項２４】
前記ライブラリが、各パターン存在探索の結果を使用して、探索される次の画像部分を決定できるように組織される、請求項１に記載の方法。
【請求項２５】
前記１つ又は複数の対象パターンに基づいてパターン行列を形成するステップ、及び前記パターン行列から導出された前記複雑度正規化表現を使用して、前記パターン行列を近似するステップが、変換領域において実行される、請求項１に記載の方法。
【請求項２６】
探索結果に基づいて前記画像内の１つ又は複数の項目にラベル付けするステップをさらに含む、請求項１に記載の方法。
【請求項２７】
前記画像が、写真を撮影するユーザから生成される、請求項２６に記載の方法。
【請求項２８】
実行された場合に、１つ又は複数のプロセッサに、
１つ又は複数の対象パターンを画像の一部から抽出するステップと、
前記１つ又は複数の対象パターンに基づいてパターン行列を形成するステップと、
前記パターン行列から導出された複雑度正規化表現を使用して、前記パターン行列を近似するステップと、
クエリ内のベクトルに対応する画像のライブラリを探索するために当該クエリを送信し、前記１つ又は複数の対象パターンに類似する画像パッチを含む前記ライブラリ内の画像を、前記複雑度正規化表現を使用して検出するステップと
を含む方法を実行させる命令が保存されたコンピュータ可読記憶媒体を備える製造物品。
【請求項２９】
命令を保存するためのメモリと、
前記メモリに結合されたプロセッサであって、
１つ又は複数の対象パターンを画像の一部から抽出するステップと、
前記１つ又は複数の対象パターンに基づいてパターン行列を形成するステップと、
前記パターン行列から導出された複雑度正規化表現を使用して、前記パターン行列を近似するステップと、
クエリ内のベクトルに対応する画像のライブラリを探索するために当該クエリを送信し、前記１つ又は複数の対象パターンに類似する画像パッチを含む前記ライブラリ内の画像を、前記複雑度正規化表現を使用して検出するステップと
を含む方法を実行する命令を実行するためのプロセッサと
を備える装置。
【請求項３０】
画像の非オーバラップブロックを抽出するステップと、
パターンのどの部分集合を圧縮するかを決定するステップと、
前記非オーバラップブロックからパターン行列を形成するステップと、
前記パターン行列を使用して複雑度正規化表現を導出するステップと、
分類マップ及びパターン基底を復号器に送って、再構成を可能にするステップと
を含む圧縮方法。
【請求項３１】
パターンのどの部分集合を圧縮するかを決定するステップが、どのパターンが固定された非適応的な基底を使用してより良く表され、どのパターンが複雑度正規化分解から導出された基底を使用してより良く表されるかに基づく、請求項３０に記載の方法。
【請求項３２】
パターンのどの部分集合を圧縮するかを決定するステップが、歪みを複雑度と組み合わせたメトリックを使用して実行される、請求項３０に記載の方法。
【請求項３３】
歪みが、ラグランジュパラメータを使用して複雑度と組み合わされる、請求項３０に記載の方法。
【請求項３４】
サーバにおいて、関心領域を有する画像データを受け取るステップと、
複雑度正規化表現及び探索プログラムを使用して、前記サーバによってアクセスされたデータに対する前記関心領域のマッチングを実行するステップと
を含む方法。
【請求項３５】
前記複雑度正規化表現及び前記探索プログラムが、オフラインで計算される、請求項３４に記載の方法。
【国際調査報告】
2012507793.tif 000086
2012507793.tif 000087