(57)【要約】  本発明は、入力データを受け取るワーキングメモリ(206)と、複数の近似ディクショナリを格納する補助メモリ(204)と、入力データの近似データを反復計算するように構成されており、この逐次反復がマッチング追跡型のものである、レジューサ(202)と、先行する反復の少なくともいくつかに基づいて選択規則に応じて上述の補助メモリから近似ディクショナリを選択するように構成されているセレクタ(200)とを備え、レジューサ(202)が、反復ごとにセレクタ(200)を呼び出し、マッチング追跡においてこうして選択されたディクショナリを使用することを特徴とするコンピュータツールに関する。
2013531829.tif 000002
【特許請求の範囲】
【請求項１】
入力データを受け取るワーキングメモリ(206)と、
いくつかの近似ディクショナリを格納する補助メモリ(204)と、
入力データにおける近似データを反復して計算するように構成されており、前記逐次反復がマッチング追跡型のものである、レジューサ(202)と、
先行する反復の少なくともいくつかに基づいて選択規則に応じて前記補助メモリの中からある近似ディクショナリを選ぶように構成されているセレクタ(200)と
を備え、
前記レジューサ(202)が、反復ごとに前記セレクタ(200)を呼び出し、前記マッチング追跡において選択された前記ディクショナリを使用する
ことを特徴とするコンピュータツール。
【請求項２】
所与の反復の場合、前記セレクタによって選択された近似ディクショナリの存在下で、前記レジューサが、
前記所与の反復の現在の入力データに対応する前記近似ディクショナリからある項目を決定し、
近似データとして、現在の入力データおよび前記項目の中から対応する項目識別子と、比例係数とを定義し、
前記入力データと前記項目との差に対応する剰余を、その比例係数を乗じて計算し、
新たな現在の入力データとして、前記セレクタの前記項目識別子および前記残余を伴って続く反復を呼び出す、請求項1に記載のコンピュータツール。
【請求項３】
前記選択規則が、現在の前記反復の数および/または先行する反復において計算された前記近似データに応じたディクショナリの選択を含む、請求項1または2に記載のコンピュータツール。
【請求項４】
前記近似ディクショナリが、ツリー構成によって相互につながり、前記選択規則が、現在の前記反復の数から取られた前記ツリーのレベルにおけるディクショナリの選択を含む、請求項3に記載のコンピュータツール。
【請求項５】
所与のレベルのそれぞれの近似ディクショナリが、前記ツリーの続くレベルにおいて、選択された数の子近似ディクショナリに関連し、前記選択規則が、先行する反復において選択された前記近似ディクショナリの前記子達の中からの近似ディクショナリの選択を含む、請求項4に記載のコンピュータツール。
【請求項６】
1つの所与のレベルのそれぞれの近似ディクショナリのそれぞれの項目が、前記ツリーの続くレベルにおける子ディクショナリに関連し、所与の反復の前記選択規則が、先行する反復において計算された前記近似データの前記項目識別子によって指定された前記項目に対応する前記子ディクショナリの選択を含む、請求項5に記載のコンピュータツール。
【請求項７】
ツリーにおける1つの所与のレベルのそれぞれのディクショナリが、より高レベルのディクショナリの項目よりも1小さい大きさの項目を含む、請求項4から6のいずれか一項に記載のコンピュータツール。
【請求項８】
前記レジューサが、反復ごとに還元データのセットを計算し、前記レジューサが、前記逐次近似データの前記計算に還元データの当該セットを使用する、請求項7に記載のコンピュータツール。
【請求項９】
前記ツリーが、レベルごとに単一のディクショナリを含み、前記補助メモリが、還元データのセットをさらに格納し、前記ツリーにおける所与のレベルのそれぞれのディクショナリ項目が、還元データのセットに関連している、請求項7に記載のコンピュータツール。
【請求項１０】
前記レジューサが、前記逐次近似データを計算するために、還元データのセットを使用する、請求項9に記載のコンピュータツール。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータによる信号のスパース表現(sparse representation)の分野に関する。
【背景技術】
【０００２】
表現は、ディクショナリと呼ばれる既知のデータのセットに基づいている。スパース表現は、圧縮すべきコンテンツに最も近い項目をディクショナリから選択することによって、およびこれらの項目に関係する情報のみを送信することによって達成される。
【０００３】
一般に、「マッチング追跡(matching pursuit)」アルゴリズム群(「MPアルゴリズム」)が、圧縮すべきコンテンツおよびディクショナリに基づいたスパース表現を決定するために実施される。
【０００４】
このタイプのスキームを実施するコンピュータツールは、得られる近似値の圧縮の程度が高く、マッチング追跡アルゴリズムが極めて有効であるので、非常にパワフルである。しかし、これには、格納および計算のコスト増加を伴う大きいディクショナリが必要であるため、これらの様々なタイプのデータにおいて実行するディクショナリを得ることは困難である。
【０００５】
この弱点を補うために、様々な方法が開発されてきた。これらの方法の1つが「K-SVD」法である。この方法によれば、ディクショナリが、意図された反復の数に基づいて最適化される。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
これにより、ある程度までは満足いくが、この方法では、通常、まだ不十分である。実際、この方法は、平均において最適化されるディクショナリをもたらすが、そのディクショナリは、必ずしもMPアルゴリズムの反復それぞれについて最適化されるとは限らない。さらに、このディクショナリは、すべての反復について固定され、したがって、反復の数を変更すると決定される場合には適していない。
【０００７】
本発明は、この問題について改善を図る。
【課題を解決するための手段】
【０００８】
この目的を達成するため、コンピュータツールは、
入力データを受信するワーキングメモリと、
複数の近似ディクショナリを格納する補助メモリと、
入力データの近似データを反復して計算するように構成されており、この逐次反復がMP型のものである、レジューサと、
先行する反復の少なくともいくつかに応じて選択規則に基づいて補助メモリの中からある近似ディクショナリを選択するように構成されているセレクタと
を備え、
レジューサは、反復ごとにセレクタを呼び出し、マッチング追跡においてこうして選択されたディクショナリを使用する。
【０００９】
本発明は、
a.  トレーニングデータのセットを選択するステップと、
b.  K平均アルゴリズム群を使用して、トレーニングデータを選択された数のトレーニンググループに分割するステップと、
c.  選択規則に従って、トレーニンググループごとに項目を含む近似ディクショナリを定義するステップと、
d.  近似ディクショナリにトレーニングデータセットを射影して(projecting)、いくつかの新規トレーニングデータセットを抽出するステップであって、それぞれの新規トレーニングデータセットは、トレーニングデータセットと、近似ディクショナリにおけるこれらのデータの射影との差に対応するデータを含む、ステップと、
e.  繰返しの数に関係する停止条件が満たされるまで、新規トレーニングデータセットのそれぞれを用いてステップb)〜e)を繰り返すステップと
を含む、近似ディクショナリを駆動する方法をさらに提案する。
【００１０】
有利には、ステップbは、射影に基づく距離測定値を使用したK平均アルゴリズム群の使用を含み、重心が、それぞれのグループの特異値への分解に基づいて選択され、ステップcは、項目としてステップbから得られた重心の選択を含む。
【００１１】
本発明の他の特徴および利点は、図面による非限定例に基づいて以下の説明を読むことにより、より良く理解される。
【図面の簡単な説明】
【００１２】
【図１】本発明によるスパース表現を得る方法を示す図である。
【図２】図1の方法を実施するコンピュータツールを示す図である。
【図３】図1の方法のディクショナリツリーを示す概略図である。
【図４】図3のディクショナリツリーに適合された図1の方法のディクショナリ選択関数の例を示す図である。
【図５】図3のディクショナリの発生関数を示す図である。
【図６】図5のオペレーションを示す流れ図である。
【図７】図5の別のオペレーションを示す流れ図である。
【図８】図5の変形形態を示す図である。
【図９】図7の変形形態を示す図である。
【図１０】図5の他の変形形態を示す図である。
【図１１】図7の他の変形形態を示す図である。
【発明を実施するための形態】
【００１３】
以下の図面および説明は、既定の性質である要素を基本的に含んでいる。したがって、それらは、本発明をより良く理解する助けとなるだけでなく、必要に応じて本発明を定めるのにも役に立つ。
【００１４】
その性質によって、本明細書には、著作権保護を受ける要素が含まれ得る。著作権者は、公的ファイルに記載される限り、本出願または本明細書の、いかなる者による同一の複製に異議を唱えない。他のすべての事項においては、著作権者は、すべての権利を有する。
【００１５】
図1は、本発明によるスパース表現の計算手順を示している。
【００１６】
この方法は、「簡潔ベクトル(parsimonious vector)」として知られている空のベクトルによって近似すべき共通要素xを受け取るオペレーション100から始まる。要素xは、符号化すべきコンピュータデータの任意のタイプであってもよい。例えば、この要素は、画像内のピクチャボックスまたは符号化すべき画像の流れであっても、あるいは音楽録音におけるサウンドトラックなどであってもよい。
【００１７】
オペレーション102において、反復カウンタiが初期化され、オペレーション104において、残余変数r(i)が要素xを受け取る。反復ごとに、残余変数r(i)は、現在の近似値の剰余を受け取り、後続の反復、MPアルゴリズムの古典的なケースで近似された要素を構成する。
【００１８】
xのスパース表現は、反復カウンタの増加オペレーション106を含むループによって計算され、現在の反復についてのディクショナリ選択オペレーション108、近似ベクトル計算オペレーション110、およびループを終わらせる条件をテストするオペレーション112がそれに続く。
【００１９】
このループが終わると、要素xを還元するオペレーションが終わり、この方法は、計算済みデータを送信し、続く要素xの還元を開始することによって、オペレーション114において終了する。
【００２０】
オペレーション108は、関数Cho()の呼出しを含み、この関数は、引数として反復カウンタiを受け取り、変数DICT(i)に格納されているこの反復についての最適化されたディクショナリを送ることによって応答する。
【００２１】
オペレーション110において、関数MP()が、先行する反復の剰余r(i-1)、ならびに現在の反復のディクショナリDICT(i)を伴って呼び出される。したがって、1反復ごとに、要素xは、MPアルゴリズムの古典式に従って近似される。
【００２２】
関数MP()は、任意のタイプのMPアルゴリズム群を実施することが可能であることに留意されたい。
【００２３】
オペレーション110の結果は、近似値y(i)および剰余r(i)である。近似値y(i)は、ディクショナリDICT(i)の項目の識別子を含み、それにより、先行する反復の剰余r(i-1)およびその増倍係数が最良に近似される。
【００２４】
オペレーション112のループ終了条件は、関数Thresh()によってテストされ得る。関数Thresh()は、
反復の最大数、すなわち、iの最大数、
残余エネルギーr(i)の測定値、すなわち、剰余r(i)の基準の計算および意図された精度閾値との比較
の中から選択された1つまたは複数の条件を考慮することが可能である。
【００２５】
関数Cho()が、現在の反復に対してディクショナリ選択を適合させることを可能にするという理由から、簡潔ベクトルを求める方法は、ここでは特に対象となる。
【００２６】
これは、従来技術の手法に関して比較できる数の反復で、より正確になり得ることを意味する。さらに、これはまた、この方法を、簡潔ベクトルの探索に行われる反復の数とは無関係にし、その理由は、ディクショナリが、それぞれの反復において特異的に選択されるために、反復の総数はそれほど重要なものではないからである。
【００２７】
図2は、図1の方法を実施するコンピュータツールの簡略化した概略図を示している。
【００２８】
本発明によって開示されるコンピュータツールは、ディクショナリセレクタ200、およびベクトルレジューサ202、ならびにディクショナリDICT(i)を格納するメモリ204を備える。
【００２９】
このツールは、要素xをデータ206の形式で受け取り、スパース表現データ208を送る。
【００３０】
ここで説明するコンピュータツールは、スパース表現を使用するコンピュータデバイス、例えば、符号化/復号化、雑音除去、予測、またはソース分割デバイス内に組み込むのに適している要素を示す。したがって、このツールは、より広いデバイスの処理において、ある「ブリック」であることに適している。
【００３１】
したがって、データ206および208をこのツールの一時メモリ、またはメモリ205内に格納することができ、これらのメモリは、コンピュータツールがその中に一体化されているデバイスのメモリであってもよいことを当業者は理解するであろう。
【００３２】
一方、セレクタ200およびレジューサ202が、別個にまたは一緒に、ソフトウェアとして、すなわち、コンピュータツールがその中に一体化されているデバイスの汎用プロセッサによって、または「物理的に」、すなわち、1つまたは複数の専用プロセッサによって実行される符号の形態で実施され得ることもまた、当業者なら理解するであろう。
【００３３】
以下で分かるように、メモリ204内部のディクショナリは、関数Cho()によってランダムに格納されることも、または自動的に生成されることもない。これらのディクショナリは、下記で分かるように、本質的にレジューサの反復に関連付けられる。
【００３４】
図3は、図1の方法を実施するディクショナリのアーキテクチャの例を示している。
【００３５】
このアーキテクチャでは、ディクショナリは、ツリー構造に従って構成されている。このツリー構造において、それぞれのレベルは、反復に利用可能なすべてのディクショナリを含むことになり、その数は、ツリー内のレベルに対応する。
【００３６】
したがって、例えば、ツリーの第1のレベルは、第1の反復に使用されることになる単一のディクショナリを含み、ツリーの第2のレベルは、第2の反復に使用されることになるディクショナリのセットを含む。
【００３７】
さらに、ここに説明する例では、ある反復について選択されたそれぞれのディクショナリは、続く反復におけるディクショナリの選択を調整する。実際に、図5〜図7の説明でよく分かるように、先行する反復によって取られる「ディクショナリパス」に基づいてディクショナリを駆動することが可能である。
【００３８】
図4は、図3のツリーアーキテクチャに関してサポートされる関数Cho()の実施形態の例を示している。
【００３９】
オペレーション400において、関数Cho()は、先行する反復において剰余を近似するように選択された項目のインデックスを回復させる。この目的を達成するため、関数Rnk()が、先行する反復において決定された近似値y(i-1)、ならびにその計算のために使用済みのディクショナリDICT(i-1)を引数として受け取る。
【００４０】
DICT(i-1)におけるベクトルy(i-1)のランクjが、決定されると、単一のディクショナリが、続くレベルにおいて指定される。次いで、選択されたディクショナリDICT(i)は、オペレーション402において、ツリーの中のディクショナリDICT(i-1)に対応するノードのj番目の子として定義される。
【００４１】
したがって、次に、図3のアーキテクチャにより、いかにディクショナリの選択が構造化されるか、すなわち、ディクショナリが、所与の反復において選択される度ごとに、ツリーの中のその子達のみが、続く反復において選択され得るということが分かる。
【００４２】
これにより、単純な選択関数Cho()を実施することが可能になる。悩まされる比較考量としては、これには、ディクショナリパスが最適化されるツリーの規定が必要であるということである。下記で分かるように、この条件は、本出願によって展開される方法を考慮すると、それほど制限的なものではない。
【００４３】
図3で分かったように、第1の実施形態は、先行する反復において取られたパスに基づいて最適化されるディクショナリツリーに基づいている。
【００４４】
この最適化ディクショナリツリーは、再帰関数ITD()によって生成され得る。
【００４５】
関数ITD()は、次第にディクショナリを最適化するために使用されるトレーニングベクトルのセットの伝播の原理に基づいている。それぞれのレベルにおいて、それぞれのトレーニングセットが、より低いレベルのディクショナリを駆動するように働く様々な剰余のセットを生成する。
【００４６】
関数ITD()はまず、オペレーション500によって初期化されなくてはならず、ここで、第1のディクショナリおよび第1の剰余のセットが計算される。
【００４７】
オペレーション500は、関数Creat()によって実行され、この関数は、P個のトレーニングベクトルyのセットを引数として受け取る。ここで説明される例では、トレーニングセットは、多数のトレーニングベクトルyを含み、ベクトルyの数Pは、ツリーのディクショナリそれぞれに与えられる大きさよりもはるかに大きい。これらのトレーニングベクトルは、最適なディクショナリ構成を提供するために、可能な限り変化するように選択される。
【００４８】
トレーニングベクトルは、可能な限り規則的に意図されたベクトル空間を回復させるために、トレーニングベクトルのデータベースから取ることも、またはそれらを合成、すなわち生成することもできる。
【００４９】
関数Creat()の実施形態の例を図6に示している。その図で分かるように、関数Creat()は、オペレーション600により開始し、ここで、トレーニングベクトルが、剰余RS(0)のセット内に格納される。オペレーション602において、ツールは、関数KM()を実施して、剰余RS(0)のセットをトレーニング剰余R(s)のセットの数Nに分割する。関数KM()は、引数として残余RS(0)のセットおよび数Nから開始して、K平均アルゴリズム群を実施する関数である。
【００５０】
明確にするため、K平均アルゴリズムでは、ベクトルのセットは、以下のやり方で反復して分割されることに留意されたい。
a)  ベクトルは、重心からのそれらの距離に基づいて分割され、その距離は、測定規則によって左右され、
b)  ベクトルが分割されると、重心は、重心選択/計算規則に従って、それぞれの分割内で再計算され、
c)  続く反復は、反復の数および/または重心の成長に関係する終了条件が満たされるまで、新規重心に基づいてa)から再開する。
【００５１】
したがって、K平均アルゴリズム群では、ベクトルと重心との間の距離を計算して、それぞれの反復について分割を実行するために使用される測定値、およびそれぞれの反復の前の重心に対する計算規則は、特定のアルゴリズムを定義するパラメータであることが分かる。
【００５２】
ここで説明する例において実施されるアルゴリズムでは、使用される測定値は、射影であり、重心選択/計算規則は、個々の値へのそれぞれの分割分解に基づいている。
【００５３】
より正確には、1つの所与の分割のベクトルは、まず、マトリックス内に並んで作られる。次いで、このマトリックスは、形式UΣVTの個々の値に分解され、個々の値は、Σの対角線における下降値によって順序付けられる。次いで、マトリックスUは、この分割の重心として、その第1の列U1に還元される。
【００５４】
測定値としての射影と重心の個々の値への分解との組合せは、下記に説明する多くの利点を、具体的には、直交性の観点から示す。
【００５５】
次いで、オペレーション604では、ディクショナリDICT(1)は、関数LSV()によって計算される。関数LSV()は、オペレーション602で計算されたNセットのトレーニング剰余R(s)をその引数として取り、それらはディクショナリに還元される。
【００５６】
この目的を達成するため、関数LSV()は、それぞれのセットのトレーニング残余R(s)の個々の値への分解に基づいて選択規則を実施する。
【００５７】
この選択規則は、関数KM()の重心計算規則に非常に近い。より正確には、所与のセットのトレーニング剰余R(s)のベクトルは、まず、マトリックス内に並んで作られる。次いで、このマトリックスは、形式UΣVTで個々の値に分解され、個々の値は、Σの対角線における下降値によって順序付けられる。
【００５８】
次いで、マトリックスUは、その第1の列U1に還元され、トレーニング剰余R(s)のセットは、このベクトルU1へと還元される。最後に、ディクショナリDICT(1)は、トレーニング剰余R(s)のセットを還元することによって得られるすべてのベクトルの連結と定義される。
【００５９】
第1のディクショナリDICT(1)が計算されると、トレーニング剰余の第1のセットRS(1)は、オペレーション606において計算される。ディクショナリツリーの作成を容易にするために、図3に示すように、ディクショナリツリーに含まれるトレーニング残余のセットについてツリーが作成される。1つの変形形態において、残余のセットは、別個のツリーに格納することができる。
【００６０】
これは、第1のノードのそれぞれの子RS(1)における関数Proj()の結果を格納することによって実行され、関数Proj()は、トレーニング剰余のセットRS(0)およびディクショナリDICT(1)を引数として受け取る。
【００６１】
関数Proj()は、トレーニングの剰余のセットRS(0)のベクトルごとに以下のオペレーションを行う。
関数Proj()は、ベクトルに最も近いディクショナリDICT(1)の項目を決定し、
関数Proj()は、エントリ時のベクトルと、セットRS(1).tにおけるその項目へのその射影との差に対応する剰余のベクトルを格納する。ただし、tは、ディクショナリDICT(1)における項目のインデックスである。
【００６２】
結果として、ゼロレベルのノードは、最初のトレーニングセットRS(0)から取られた、N個の子トレーニング残余セットS(1)を生成する。
【００６３】
第1のディクショナリDICT(1)および第1のセットの剰余RS(1)が計算されると、オペレーション502において、関数ITD()は、引数としてこれらの要素を伴って呼び出される。
【００６４】
図7は、この関数の実施形態の例を示している。関数ITD()は、オペレーション700において終了条件をテストすることによって開始する。この終了条件は、図1で説明した関数Tresh()の制限付きバージョンによって、ここで説明する例でテストされる。
【００６５】
この場合、関数Tresh()の唯一の終了条件は、反復の数である。この終了の目的は、数学的見地から、それぞれの反復が、この反復のディクショナリの項目によって形成される基底における剰余の1つの射影に対応することである。
【００６６】
したがって、ディクショナリが互いに直交し、および/または選択された関数群MPが直交している場合、ベクトルは、この基底とは無関係の新規ベクトルに関して射影される。したがって、近似を図ろうとされるベクトルにおける次元と同じく反復も存在し得ない。
【００６７】
したがって、dが最初のベクトルの次元である場合、反復の最大数は、dである。これはまた、関数ITD()の収束を確実にする利点を有する。ディクショナリが互いに直交しておらず、および/または選択された関数群MPが直交していない場合、近似値は、所望の数の反復の後、満たされていると考えられる。
【００６８】
両方の場合において、ディクショナリが多すぎて格納できないことを避けるために、値dの一部に対して反復の数を制限することは賢明である。ディクショナリが最適化されるので、これにより、近似値の品質は過度の影響を受けないことになる。
【００６９】
最大数の反復が達成されると、関数IDT()は、オペレーション702において終了する。この関数において、剰余についての閾値条件は、実施されない。有利には、ヌル剰余または閾値未満の剰余は、オペレーションの過程でそれらが属するトレーニング剰余のセットから取り除かれる。
【００７０】
オペレーション700の後、反復カウンタiは、オペレーション704において増加する。この点で、関数ITD()の実行のコンテキストを説明するだけの価値がある。第1の反復に続いて、ディクショナリツリーは、ディクショナリDICT(1)を含み、剰余ツリーは、ディクショナリDICT(1)から取られたNセットのトレーニング剰余を含む。したがって、ツリーは、容易に想像される。
【００７１】
ディクショナリツリーのいずれのレベルにおいて、問題はむしろより複雑になる。ここに説明する例のコンテキストでは、レベルiのそれぞれのディクショナリは、レベルi+1のN個のディクショナリ、すなわち、親ディクショナリの項目ごとに子ディクショナリを生じさせ、この項目に対応するレベルiの残余のセットにおいて駆動される。
【００７２】
したがって、(カウンタiが704において増加したばかりであることを考慮する)一般的な場合、関数ITD()は、まず、ディクショナリDICT(i-1).mのj番目の項目に対応するトレーニング剰余のセットRS(i-1).jを受け取る。
【００７３】
オペレーション706において、反復i-1のトレーニング剰余のセットは、オペレーション602において行われたように分割される。これが行われると、Nセットのトレーニング残余R(s)が得られる。
【００７４】
次いで、オペレーション708において、これらのNセットのトレーニング剰余から生じることになるディクショナリDICT(i).jは、ディクショナリDICT(i-1).mの子として初期化される。このディクショナリは、それが、ディクショナリDICT(i-1).mの項目jから生じるので、j番目のランクにおいて初期化される。次いで、Nセットのトレーニング剰余RS(i).tは、剰余のセットRS(i-1).jの子として、オペレーション710において初期化される。
【００７５】
次いで、オペレーション712において、ディクショナリDICT(i).jは、オペレーション604において行われたことと同様に、オペレーション706から生じるNセットのトレーニング剰余R(s)を伴って呼び出された関数LSV()で満たされる。
【００７６】
ディクショナリDICT(i).jが満たされると、オペレーション714における関数Proj()によって、剰余のセットRS(i-1).jがNセットの剰余RS(i).tに展開され、tは、1からNの間で変わる。
【００７７】
最後に、オペレーション716において、関数ITD()は、一方はディクショナリDICT(i).jを、他方はNセットRS(i).tのそれぞれを引数の対として含みながら、N回再生する。
【００７８】
前述において、与えられたインデックスが絶対的ではなく、相対的であることに留意することは重要であると思われる。したがって、前述したように、最初のディクショナリは、ディクショナリDICT(i-1).m、すなわち、レベルi-1のすべてのディクショナリの中からの任意のディクショナリである。
【００７９】
表記DICT(i-1).mは、エントリのポイントをディクショナリツリーに示し、それはポインタであり、それ自体におけるそのコンテンツは、重要ではない。このディクショナリDICT(i-1).mに、先の反復RS(i-2).jから発生するトレーニング剰余のセットが対応する。このディクショナリDICT(i-1).mにより、Nセットの剰余RS(i-1).tが作成され、t=1〜Nである。ここで説明する例では、これらのセットのうちの1つ(セットRS(i-1).j)を考慮しているに過ぎないが、オペレーション716が示すように、関数ITD()は、N回呼び出され、トレーニング剰余のそれぞれのセットRS(i).tが、関数ITD()の現在の実行の過程で作成される。
【００８０】
これらのすべての反復の結果、ディクショナリツリーが再帰的に作成され、1つのレベルのそれぞれのディクショナリが次にN個のディクショナリを作成する。さらに、これらのディクショナリは、意図的にディクショナリツリー内で互いにつながり、それらの収束は、反復につながった終了条件によって確実になる。
【００８１】
図8は図5の、図9は図7の変形形態を示しており、初期化関数Creat()は同じままである。
【００８２】
これらの図は、ディクショナリを作成するこの方法により、ディクショナリの大きさの縮小が可能になるという研究結果に基づいている。実際、上述したように、トレーニング剰余のそれぞれのセットは、ディクショナリの項目における射影の結果である。したがって、トレーニング剰余のこれらのセットに基づいて、ツリーの次のレベルで作成されたディクショナリは、射影がそれに基づいている項目と直交している。したがって、この項目に対応するコンポーネント(ライン)は、それらの寄与が皆無であるので、トレーニング剰余から取り除くことができる。
【００８３】
したがって、オペレーション800は、オペレーション500と同一であり、オペレーション802は、呼び出されるのが新規関数RITD()である点で、オペレーション502とは異なる。
【００８４】
概して、図7のオペレーションと類似しているオペレーションに再度符号付けし、100の位の数字「7」を数字「9」に置き換える。図7の関数ITD()と、図9の関数RITD()との相違に関しては、
新規オペレーション905aにより、関数GS()によってマトリックスPhi(i-1).jを確立して、先の反復の項目jに対応するコンポーネントが取り除かれ、
新規オペレーション905bにより、マトリックスPhi(i-1).jを使用して、トレーニング剰余のセットRS(i-1).jが還元され、
接頭辞「R」は、RS(i).tとして引き続き知られている最終剰余を例外として、還元を示すように還元要素に付加される。
【００８５】
関数GS()は、先の反復において選択された項目をその最初のベクトルとして取る直交化関数であり、直交ベクトル基底がそれから取られ、項目が補われる。これは、例えば、グラムシュミットのアルゴリズムによって行うことができる。これらのベクトルにより、マトリックスPhi(i-1).jの列が形成される。
【００８６】
この方法により、それぞれのディクショナリは、反復ごとに1ラインずつ大きさが縮小されるので、スペースの節約が可能になる。これによりまた、マトリックスおよびディクショナリの大きさが反復ごとに縮小されるので、計算パワーの節約も可能になる。
【００８７】
上述のディクショナリを駆動する方法は、2つの主な要素において調整される。
【００８８】
第1に、これらの方法は、「カスケード」な形でディクショナリを作成する、すなわち、1つの所与の反復のそれぞれのディクショナリが、続く反復においてN個のディクショナリを作成する。
【００８９】
これは、それぞれの実行において、最初の分割をNセットのトレーニング剰余へと実行することによって得られる。1つの変形形態において、剰余のセット数は、図3で示唆したように、反復ごとに変わることがあり得(第1の反復ではNA1、第2の反復ではNA2など)、それは、オペレーション706およびオペレーション906までパスしたパラメータNによって左右される。
【００９０】
さらに、分割方法において重心を選択/計算する方法は、説明した例では、反復ごとに、それぞれの分割における個々の値への分解の中の最強項目の選択に基づいている。この規則は、例えば、重心選択/計算によって置き換えることができる。
【００９１】
さらに、ディクショナリを形成する項目の計算方法はまた、非常に重要であり、オペレーション712およびオペレーション912において、トレーニング剰余のセットのそれぞれの分割セットの個々の値への分解の中の最強項目の選択に基づいている。別の規則、例えば、重心規則が使用されてもよい場合がある。
【００９２】
図4の関数における現在の反復のディクショナリを選ぶために関数Cho()に使用されるのはこの同じ選択規則である。実際、ここで説明する例では、現在の反復のディクショナリを指定するために使用されるのは、先の反復の関数MPE()から発生する項目であり、結果的に、個々の値への分解の中の最大の相関を有する項目を選ぶことになる。
【００９３】
1つの変形形態において、別の選択規則が、反復のディクショナリを選ぶために使用されてもよい場合がある。例えば、このような規則は、近似されることが求められる残りのベクトルを最良に近似する先の反復のディクショナリDICT(i-1)の項目によって指定されるディクショナリを選択することが可能になり得、最強のK個の個々の値に対応するベクトルが第1のベクトルだけでなく考慮される。
【００９４】
図10は図5の、図11は図7の他の変形形態を示し、関数Creat()は同一のままである。
【００９５】
これらの変形形態は、図8および図9の変形形態と同じ原理に基づいているが、反復レベルごとに格納されている1つのディクショナリのみによるより軽い実施形態を意図している。選択された各項目への適合を確実にするのは還元マトリックスPhi(i-1).tであり、レベルごとに格納されているディクショナリに基づいてN個のディクショナリが得られる。
【００９６】
各ディクショナリが、続く反復において1つのディクショナリしか作成しないということに基づくと、この実施形態はより簡単に思われ、ツリー構造が縮小され、インデックス表記が縮小され、特定のオペレーションが消去される。しかし、図8および図9の場合に反して、関数Phi(i-1).tは、もはや暗黙的であることは不可能であり、この場合、ディクショナリRDICT(i)を伴って格納されなくてはならない。
【００９７】
図10では、図8との唯一の相違は、呼び出されるのは関数ITAD()であり、関数RITD()ではもはやないことである。
【００９８】
概して、図9のオペレーションと類似しているオペレーションに再度符号付けし、100の位の数字「9」を数字「11」に置き換える。図11の関数ITAD()と図9の関数RITD()との相違に関しては、
オペレーション1105aは、マトリックスPhi(i).tが、詳細に後述する関数Align()によって構成されている点で、オペレーション905aと異なり、
トレーニング剰余のNセットおよび結果得られるN個のディクショナリを作成する分割オペレーション906は消去され、
ツリー908およびツリー910の管理に関するオペレーションは消去され、
ディクショナリ作成オペレーション912は、詳細に後述する関数KM2()によって行われるのであって、もはや関数LSV()によって行われるのではなく、
オペレーション1116により、関数ITAD()の単一の再帰のみが呼び出されるが、剰余のセットは、作成されたばかりの(オペレーション1105aによって考慮に入れられた)Nセットの剰余を含んでいる
ことに留意されたい。
【００９９】
関数Align()は、形式UΣVTで、各セットRS(i-1).tの個々の値への分解を行い、個々の値は、Σの対角線における下降値で順序付けされる。
【０１００】
次いで、マトリックスUは、Σの個々のヌルでない値に対応するその列に対して還元される。したがって、マトリックスPhi(i-1).tは、RS(i-1).tの直交基底を形成する。
【０１０１】
関数KM2()は、それが同じ計算を実行する範囲内で関数KM()に非常に近い。しかし、それは、その入力およびその出力により異なる。この場合、すべての還元されたセットRRS(i-1).tが入力を形成するように再度グループ分けされ、出力は、ディクショナリRDICT(i)である。
【０１０２】
関数KM2()は、重心選択/計算規則として、最強の個々の値に対応するベクトルの選択を使用する。オペレーション1112において、ディクショナリRDICT(i)を満たすために使用されるのは、これらの重心である。
【０１０３】
さらに、この設計は直交しているので、オペレーション1105aおよびオペレーション1105bは、還元剰余RRS(i-1).jのすべてのセットが、個々の値へのそれらの分解の中の同じマトリックスUを有することになるという意味で、剰余を「位置合わせ」する。これにより、単一のディクショナリRDICT(i)の使用が可能になり、マトリックスPhi(i-1).tは、それぞれのセットRRS(i-1).jへのこのディクショナリRDICT(i)の適合を可能にする。
【０１０４】
最後に、オペレーション1116において、それがオペレーション1114において計算されたNセットのRS(i).tの組合せであるという意味で、RS(i)が参照される。
【０１０５】
図8および図9の変形形態の利点から利益を得ながら、反復iごとに1つのディクショナリしか維持しないことを可能にするのがこの位置合わせである。これは、この位置合わせを可能にするマトリックスPhi(i).tを格納するという代償を払って行われる。
【０１０６】
上記において、反復ごとにディクショナリを変える規定がなされた。しかし、関数Cho()は、選択された数の反復のグループごとに1つのディクショナリを選ぶことが可能になり得、またはK回の反復ごとに呼び出されることしかできないことになり得る。
【０１０７】
さらに、関数MP()がすべての反復について同じであるというスキームを示した。しかし、この関数は比較的コストが低く、マッチング追跡の異なるバージョン群を組み込んだ、最良のものだけが毎回保存される、いくつかの個別の関数MP()の実行が想定可能になる。
【０１０８】
さらに、個々の値への分解によってディクショナリを選び駆動することにより直交要素を生成し、これにより、タイプOMPまたはOOMPの関数を使用する関心が抑えられる。しかし、万が一、ディクショナリの選択規則が異なる場合には、本技法は、その対象のすべてを失うことになる。
【符号の説明】
【０１０９】
200  ディクショナリセレクタ
202  ベクトルレジューサ
204  メモリ
205  メモリ
206  データ
208  スパース表現データ
【図１】
2013531829.tif 000003
【図２】
2013531829.tif 000004
【図３】
2013531829.tif 000005
【図４】
2013531829.tif 000006
【図５】
2013531829.tif 000007
【図６】
2013531829.tif 000008
【図７】
2013531829.tif 000009
【図８】
2013531829.tif 000010
【図９】
2013531829.tif 000011
【図１０】
2013531829.tif 000012
【図１１】
2013531829.tif 000013
【国際調査報告】
2013531829.tif 000014
2013531829.tif 000015
2013531829.tif 000016
2013531829.tif 000017
2013531829.tif 000018
2013531829.tif 000019