直接因数分解による変形可能な形状のレジストレーション及びモデリングのためのシステム及び方法
デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法において、該方法は次のステップを有する、すなわち、
変形可能な形状の測定値のセットを提供し、該測定値のセットは測定値行列を形成するステップと、
同時に剛体レジスタリング変換（rigid registering transformation）及び線形形状モデル（linear shape model）について解くステップとを有する、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法。
変形可能な形状の測定値のセットを提供し、該測定値のセットは測定値行列を形成するステップと、
同時に剛体レジスタリング変換（rigid registering transformation）及び線形形状モデル（linear shape model）について解くステップとを有する、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連の米国出願との相互参照
本出願は２００４年９月２日に提出されたXiaoその他の米国特許仮出願番号６０／６０６６３２"Registration and Modeling of Deformable Shapes: A Factorization Approarch"から優先権を請求するものである。この開示内容は、参照によって本願の開示内容に含まれる。
【０００２】
技術分野
本発明はデジタル化された画像における変形可能な形状のレジストレーションに関する。
【０００３】
関連技術の説明
変形可能なオブジェクトの統計的形状モデルは、２次元ＭＲＩ脳画像をセグメント化すること、３次元超音波画像から心筋壁運動をトラッキングすること及び２次元ビデオから人の顔を認識することのような多くのタスクにとって重要である。しかし、多くの測定方法は局所座標系に関連してオブジェクト形状の座標を、例えば、異なる視点から得られる人の顔の２Ｄ画像又は人の心臓の３Ｄ超音波ボリュームを発生する。形状モデルを抽出するためには、異なる局所座標系におけるこれらの測定値は共通座標系にレジスタリングされる必要がある。
【０００４】
オブジェクトが剛体的（rigid）である場合には、観測される形状の変化は局所座標系の配向とスケールとの間の差から由来する。これらの形状のレジストレーションはスケーリング、回転及び並進を含むこれらの間の相似変換の推定に帰する。
【０００５】
現実の世界では、多くの生物学的オブジェクト及び自然のシーンが人の顔及び心臓のようにその形状を変化させる。観測される形状の変化は互いに結合された２つのファクタに起因する：剛体相似変換（rigid similarity transformation）と非剛体形状変形（non-rigid shape deformation）である。レジストレーションの目的は、従ってこれら２つのファクタを分解及び復元することである。１つのよく知られたアプローチ、一般化プロクラステス分析（Generalized Procrustes Analysis ＧＰＡ）は形状変形をガウス雑音として取り扱い、各々観測される形状をセントロイド形状によりアラインする。このセントロイド形状は剛体ケースのように既にアラインされた形状の平均である。このレジストレーションプロセスはそれが安定したセントロイドに収束するまで繰り返される。
【０００６】
変形可能なオブジェクトの形状は、２Ｄ及び３Ｄの人の顔の形状及び２Ｄの心筋形状のようにしばしばある種の形状基底の線形結合である。このような形状変形はほんのわずかである場合、すなわち平均形状が変形に比べて優位である場合、又は、これらが平均形状に関して対称的である場合、すなわち、正の及び負のオフセットが互いにキャンセルしあう場合、これらの変形はガウス雑音として見なすことができ、一般化プロクラステス分析は変形可能な形状をレジスタリングすることにおいて成功裡に作用する。次いで主成分分析がアラインされた形状に対して適用され、線形形状変形モデルを計算することができる。しかし、多くの適用事例においては、形状変形が大きく、非対称的であり、例えば動かない建物及び動く乗り物から成る動的シーン又は２つの目の非同期的にまばたきする場合がそうである。このような状況では、形状変形はガウス雑音とは見なせない。一般化プロクラステス分析はレジストレーションプロセスの間の非剛体形状変形を考慮にいれないので、このような変形はレジストレーション及び結果的に得られる線形形状モデルに偏りをもたらすだろう。
【０００７】
本発明の概要
ここで記述される本発明の例示的な実施形態は一般的に剛体相似変換（rigid similarity transformation）と非剛体形状変形（non-rigid shape deformations）とをデカップリングする直接因数分解レジストレーション（direct factorization registration）のための方法及びシステムを含む。直接因数分解は、同時に任意の次元における変形可能な形状をレジスタリングすること及び線形変形モデルを再構成することに対して線形な閉じた形式解を与える。変形可能な形状の線形基底表示は成功裡に２Ｄ画像から３Ｄ形状を復元するために使用されている。直接因数分解法は剛体回転の正規直交性（orthonormality）及び変形可能な形状基底の一意性（uniqueness）にそれぞれ線形な制約を課し、同時に観測された形状のレジストレーションと変形基底の再構成とに対する線形な閉じた形式の解を与える。
【０００８】
本発明の例示的な実施形態は、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法を提供し、変形可能な形状の測定値のセットを提供し、測定値のこのセットは測定値行列を形成するステップと、同時に剛体レジスタリング変換（rigid registering transformation）及び線形形状モデル（linear shape model）について解くステップとから成る。
【０００９】
本発明の別の例示的な実施形態は、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法を提供し、この方法は、Ｄ次元の変形可能な形状のＰ個の地点のＮ個の測定値の測定値行列Ｗを提供するステップと、Ｎ個の測定値に対する基底数Ｋを決定し、ここでＫ＜Ｎであり、さらに基底セットとして測定値行列ＷのＫ個の測定値をセレクトするステップと、測定値行列Ｗを行列積Ｍｘ∃Ｂに分解し、ここでＭは提案されたスケーリングされた回転行列であり、Ｂは提案された基底行列であるステップと
【数１】
により定義された行列Ｑkを計算し、ここでΦは
を表し、これは提案されたスケーリングされた回転行列及び提案された基底行列を真のスケーリングされた回転行列及び真の基底行列に変換するアンビギュイティ行列を表すステップと、行列Ｑkをｋ＝１，．．．，ＫにおいてｇkｇkTに分解し、ここでｇkはＤ∃Ｋ％Ｄ∃Ｋ行列Ｇの列であるステップと、真のスケーリングされた回転行列をＭｘ∃Ｇから及び真の基底行列をＧ-1ｘ∃Ｂから復元するステップを有する。
【００１０】
本発明の更に別の実施形態は、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングするための方法ステップを実施するためにコンピュータにより実行可能な命令のプログラムを実体的に具現化するコンピュータによりリーダブルなプログラム記憶装置において、方法ステップは次のステップを含む、すなわち、変形可能な形状の測定値のセットを提供し、測定値のセットは測定値行列を形成するステップと、同時に剛体レジスタリング変換及び線形形状モデルについて解くステップとを含む。
【００１１】
図面の簡単な説明
図１は本発明の実施形態による直接因数分解レジストレーションプロシージャのフローチャートを示す。
【００１２】
図２は本発明の実施形態による直接因数分解レジストレーションプロシージャをインプリメントするための例示的なコンピュータシステムのブロック線図である。
【００１３】
有利な実施形態の詳細な説明
ここで記述されるような本発明の例示的な実施形態は一般的に剛体相似変換と非剛体形状変形とをデカップリングする直接因数分解レジストレーションのためのシステム及び方法を含む。
【００１４】
本発明の実施形態によれば、非剛体オブジェクトの形状はＫ個の形状基底｛Ｂk，ｋ＝１，．．．，Ｋ｝の線形結合として見なされうる。各基底はＤｘＰ行列であり、この行列は形状の上のＰ個の地点をしてＤ次元オブジェクト形状空間の中での位置を変えるように指示する。よって、時間ｉにおけるこの形状の座標は
【数２】
であり、ここでｌikは基底Ｂkの結合ウェイトである。このオブジェクト形状は異なるビューから、異なる距離において、異なるスケールで測定されうる。
【００１５】
よって、オブジェクト形状とその測定値との間の相似変換が存在し、これは
【数３】
であり、ここでｃiは非零スカラーであり、ＲiはＤｘＤ正規直交行列であり、ＴiはＤｘ１ベクトルであり、これらはそれぞれスケーリング、回転及び並進変換を表し、一緒になって相似変換を形成する。１は１ｘＰベクトルであり、その全ての要素は１である。Ｓiを式（１）を使用して置き換え、ｃiをｌikの中に吸収すると、
【数４】
が得られる。もし変形可能なオブジェクトのＮ個の観測値が測定されるならば、測定値はＤＮｘＰ行列Ｗの中にスタックされうる。Ｗの中のＮ個のＤ行の各々は観測された形状をそれぞれ含む。式（３）により、全ての観測された形状は形状基底の同一セットに関するので、次式
【数５】
が得られ、ここでＭはスケーリングされたＤＮｘＤＫ回転行列であり、ＢはＤＫｘＰ基底行列であり、ＴはＤＮｘ１並進ベクトルであり、
【数６】
のように示される。
【００１６】
よって、変形可能な形状のレジストレーション及びモデリングは同時にＭ及びＴにおける剛体相似変換を復元しＢにおける非剛体変形モデルを再構成するために測定値行列Ｗを分解することを含む。観測された形状を正確にアラインするためには、Ｗにおける測定値を式（４）のように直接因数分解するべきであり、この結果、Ｂにおける変形可能な形状基底及びＭ及びＴにおける剛体相似変換を再構成する。
【００１７】
本発明の実施形態によれば、Ｗを因数分解する第１のステップは世界座標原点を観測された形状の中心に置くことである。この場合、Ｔにおける並進は形状地点の平均座標に等しい。これらを測定値から減算することによって
【数７】
が得られる。形状変形及び剛体回転が両方とも非退化（nondegenerate）であると仮定すると、すなわちスケーリングされた回転行列Ｍ及び形状基底行列Ｂが両方とも式（５）に従ってフルの階数を持つと仮定すると、Ｍの階数はmin｛ＤＫ，ＤＮ，Ｐ｝であり、Ｂの階数はmin｛ＤＫ，Ｐ｝である。これらの積
は階数min｛ＤＫ，ＤＮ，Ｐ｝を持つ。一般的に、形状数Ｎ及び地点数Ｐは基底数Ｋよりもはるかに大きく、すなわちＤＮ＞ＤＫ及びＰ＞ＤＫ。
【００１８】
の階数は従ってＤＫであり、Ｋは
【数８】
によって決定される。
【００１９】
本発明の実施形態によれば、特異値分解（ＳＶＤ）は
をＤＮｘＤＫ行列
とＤＫｘＰ行列
との積に分解するために使用されうる。この分解は正則ＤＫｘＤＫ線形変換によってしか決定されない。真のスケーリングされた回転Ｍ及び基底Ｂは
【数９】
の形式をもち、ここでＧはＭ及びＢを決定する正則ＤＫｘＤＫアンビギュイティ変換である。変形可能な形状レジストレーション及びモデリングの決定は今や
が与えられた時にＧを計算することになる。
【００２０】
行列ＧはＫ個のＤ列を有し、ｇk，ｋ＝１，．．．，Ｋと表され、ここで各列はＤＫｘＤ行列である。これらの列は互いに独立している。というのも、Ｇは正則であるからである。式（５，６）によれば、ｇkは次式
【数１０】
を満たし、ここで
はＮ個のＤ行を有し、
と表され、ここで各行はＤｘＤＫ行列である。Ｑk＝ｇkｇkTとすると、ＤＫｘＤＫ対称行列がアンビギュイティ行列列の積によって形成された。この場合、
【数１１】
である。Ｑkを計算するためには、２つのタイプの制約が利用可能である：回転行列の正規直交性及び形状基底の一意性である。
【００２１】
回転行列への正規直交性制約は２Ｄ画像から３Ｄ構造及び動きを推論するために使用されうる。上記の式から、回転の正規直交性のために、
【数１２】
が得られ、ここでＩDxDはＤｘＤ恒等行列である。上のＤ個の対角要素は同値であり、Ｑkに対するＤ−１個の線形制約をもたらす。非対角要素は全てゼロである。Ｑkは対称であるので、（Ｄ2−Ｄ）/２個の線形制約がある。
【００２２】
本発明の実施形態によれば、（Ｎ/２）（Ｄ2＋Ｄ−２）個の線形制約がＮ個の観測される形状に対して得られる。対称行列Ｑkは（Ｄ2Ｋ2＋ＤＫ）/２個の別個の要素を有する。Ｎが十分に大きく、この結果、Ｎ≧（Ｄ2Ｋ2＋ＤＫ）/（Ｄ2＋Ｄ−２）である場合、Ｑkは式（９）における線形正規直交性制約を使用して決定される。しかし、これらの制約のほとんどは他に依存し、従って冗長である。しかし、正規直交性制約についての一般解がＱk＝Ｇ（Ω＋Λ）ＧTであることが示されうる。ただしここでΩは任意のブロック歪対称行列（block-skew-symmetric matrix）であり、Λは任意のブロックスケールド恒等行列である。これらのΛ及びΩは対称的である。Λの各ＤｘＤブロックはスケーリングされた恒等行列である。Ωの全ての対角ＤｘＤブロックは零行列であり、非対角ＤｘＤブロックは全て歪対称行列である。
【００２３】
Λ及びΩはそれぞれ（Ｋ2＋Ｋ）/２及び（Ｋ2−Ｋ）（Ｄ2−Ｄ）/４個の変数を有する。それゆえ、たとえ変形可能な形状の観測が何回測定されようとも、正規直交性制約だけを実施すると（（Ｋ2−Ｋ）（Ｄ2−Ｄ）＋２（Ｋ2＋Ｋ））/４個の自由度を有する曖昧な解空間をもたらす。さらに、この空間は無効解を含む。特に、所望されるＱk＝ｇkｇkTが半正値であるので、解Ｑk＝Ｇ（Ω＋Λ）ＧTは（Ω＋Λ）が半正値でない場合には有効ではない。このような無効解は実際この空間内に存在する。例えば、Λ＝０である場合、（Ω＋Λ）がブロック歪対称行列Ωに等しく、これは半正値でない。
【００２４】
正規直交性制約が本来的に曖昧である理由は、それが形状基底の一意的なセットを決定できないからである。これらの基底に適用されるどんな正則線形変換も結果的に適当な基底の別のセットをもたらす。アンビギュイティを排除するために、形状基底の一意性を保証する制約が実施される。
【００２５】
のＤＫｘＰ部分行列はＫ個の観測された形状から形成され、ここでＫは予め決定された基底数である。
【００２６】
の条件数は基礎となる変形可能な形状の独立性の尺度である。比較的小さい条件数は比較的強い独立性に関連する。本発明の実施形態によれば、Ｋ個の観測される形状の各可能なセットの条件数が計算され、最小条件数を有するセットがセレクトされる。このセットは最も独立したＫ個の変形可能な形状を含む。線形変形空間内のＫ個の独立した形状はどれでも基底のセットと見なされるので、これらの変形可能な形状は一意的な基底セットと規定され、すなわちセレクトされた観測はそれぞれスケーリングされ回転された形状基底である。スケーリングは形状の独立性には影響を与えないので、スカラーは基底の中に吸収され、セレクトされた観測は単に回転された基底である。
【００２７】
第１のＫ個の測定値としてセレクトされた観測を表し、すなわち、
とすると、相応する係数は
【数１３】
である。式（８、１０）によれば：
【数１４】
であり、ここでΦは
を表す。これらの４Ｎ（Ｋ−１）個の線形制約は一意的に形状基底を決定する。
【００２８】
式（９）及び式（１１）の線形方程式を解くことはＱk＝ｇkｇkT，ｋ＝１，．．．．，Ｋの閉じた形式の解をもたらす。ｇkはＱkをＳＶＤを介して分解することによって復元されうる。Ｑkの分解は任意のＤｘＤ正規直交変換Ψによる。というのも、（ｇkΨ）（ｇkΨ）TもＱkに等しいからである。このアンビギュイティはｇ1，．．．，ｇkが異なる座標系の下で独立に推定されるという事実に起因する。このアンビギュイティを解消するためには、ｇ1，．．．，ｇkが単一の基準座標系の下に変換される必要がある。
【００２９】
しかし、式（７）のために
【数１５】
である。回転行列Ｒiは正規直交なので、つまり
【数１６】
である。正負の符号は基準座標系の配向によって決定される。本発明の実施形態によれば、回転のＫ個のセットはｇ1，．．．，ｇkを使用してそれぞれ計算される。分解アンビギュイティのゆえに、各々２つのセットの間にはＤｘＤ正規直交変換がある。回転セットのうちの１つが基準として指定される。他の回転の正負の符号が相応の基準回転と矛盾しないように決定される。正規直交変換は直交プロクラステス分析によって計算され、正負の符号が付けられた回転セットを基準セットに変換する。これらの正規直交変換はｇ1，．．．，ｇkも共通座標系の下にあるように変換する。すなわち、所望のアンビギュイティ変換Ｇが達成される。この場合、係数は式（７）によって計算され、形状基底は式（６）によって復元される。これらの結合は変形可能な形状を再構成する。
【００３０】
本発明の実施形態による直接因数分解レジストレーションプロシージャのフローチャートが図１に記載されている。この図を参照すると、レジストレーションはステップ１１で並進Ｔを測定値Ｗの平均として計算することによって始まり、ついでそれを
【数１７】
によって消去する。その後、ステップ１２においてＳＶＤが
【数１８】
を因数分解するために実施され、ここでＭはＤＮ％ＤＫ行列であり、ＢはＤＫ％Ｐ行列である。エネルギを支配する
の階数はこの場合ＤＫである。基底数Ｋは
【数１９】
と定義され、ここでＤはオブジェクト形状空間の次元である。ステップ１３では、Ｋ個の観測Ｗkがセレクトされ、
が整理しなおされ（reordered）、
【数２０】
のrank-ＤＫ近似がＳＶＤにより計算される。ステップ１４では、行列Ｑk，ｋ＝１，．．．，Ｋが最小二乗アルゴリズムを介して式（９）及び（１１）の線形方程式
【数２１】
を解くことによって計算される。ステップ１５ではＧの列ｇk，ｋ＝１，．．．，ＫがＳＶＤを介して計算され、回転が
【数２２】
から復元される。回転は直交プロクラステス分析を使用して共通座標系に変換される。ステップ１６では、線形形状モデルが
【数２３】
から復元され、係数が
【数２４】
から復元される。これらの結合がレジスタリングされた形状を再構成する。計算コストをセーブするために、一度十分小さい条件数を有するＫ個の観測された形状のグループが配置されたら基底観測のサーチをストップすることができる。とういうのも、これらは独立した形状のセットを指定するが、比較的独立した形状は比較的信頼性の高いレジストレーションをもたらすからである。基底数が１と決定される場合、形状は剛体的だがノイジーなデータとして取り扱われ、ＧＰＡのレジストレーションに類似の最小二乗レジストレーションが達成される。
【００３１】
本発明の実施形態による方法のパフォーマンスは人の顔、心筋層及び動的シーンを含むシミュレートされたデータとリアルなデータの両方を使用してテストされた。
【００３２】
直接因数分解法の精度及びロバスト性は異なる測定ノイズレベル及び基底数に関連して定量的に評価された。ガウス白色雑音を仮定すると、ノイズ強度はノイズのフロベニウスノルム（Frobenius norm）と測定値との間の比率：
によって表された。アルゴリズムはそれぞれ５つの異なるノイズレベル０％、５％、１０％、１５％及び２０％においてテストされた。各レベルにおいて、２Ｄ空間内で剛体設定が１個の基底に関して、非剛体設定がそれぞれ２，．．．，及び１０個の基底に関して試験された。各設定に対して、１００回のトライアルがテストされた。各トライアルにおいて、これらの基底はランダムに発生され、ノーマライズされた（｜Ｂi｜＝１）。よって、これらは一般的に非対称的であった。６６個の形状がこれらの基底の線形結合として構成された。結合ウェイトは、異なる基底に対するウェイトが同じオーダの大きさを有するように、すなわち基底のうちの１つが優位でないようにランダムに発生された。これらの形状は次いで観測値を発生するためにランダムにスケーリングされ、回転され、並進され、ノイズを添加された。基底は等しく形状合成に寄与し、基底数が大きくなればなるほど、形状はますます「非剛体的」になり、個々の基底に対するノイズは強くなる。従って、一般的に、レジストレーションは比較的多くの基底が含まれる場合に測定ノイズに対して比較的敏感である。
【００３３】
観測された形状はそれぞれ提案された方法及びＧＰＡによってレジスタリングされた。回転の空間は多様体なので、誤差はリーマン距離
【数２５】
として度で測定された。形状基底はアラインされた形状を使用して再構成され、これらのアラインされた形状はこの場合復元された形状空間に投影され所望の変形可能な形状を得る。形状における相対的な再構成誤差は
として計算された。
【００３４】
ノイズレベルが０％であった場合、直接因数分解法はいつも正確な剛体回転及び変形可能な形状をゼロ誤差で復元した。ノイズが印加された場合、予期したように、レジストレーションはノイズにより敏感になり、誤差は基底数が大きい場合ほど大きかった。しかし、直接因数分解法は例えば１０個の基底及び２０％のノイズレベルの最悪のケースでもリーズナブルな精度を達成した。形状における平均誤差は１８％より小さく、回転における平均誤差は７．５度より小さかった。剛体設定において、両方の方法は形状を剛体的だがノイジーなデータとして取り扱い、よって同様な性能を示した。しかし、ＧＰＡは全ての非剛体トライアルにおいて劣った。ノイズのないケースでさえ、このＧＰＡは形状において注目すべき誤差２２％を、回転において１１度を生じた。ＧＰＡによる誤差は基底数が大きくなると大きくなった。しかし、ＧＰＡのパフォーマンスはノイズに対してあまり敏感でなかった。なぜなら、ＧＰＡはガウス白色雑音に対して敏感でない最小二乗解を計算するからである。
【００３５】
人の顔は高度に非剛体的なオブジェクトである。それは顔形状の２Ｄ画像がいくつかの基底構造の線形結合であることに示されている。この線形統計モデルは顔トラッキング及び認識のようなタスクにとって役立つ。１つのテストシーケンスは顔回転及び瞬き及び笑みのような顔面表情を含む１８０個の画像を含んでいた。２次元顔形状は６８個の特徴点によって表示された。形状測定値から並進を、すなわち平均座標を減算すると、並進された形状はこの場合変形及び回転から構成された。基底の数は３と推定され、この結果、並進された形状のエネルギの９９％は階数制約による分解の後に残りうる。次いで剛性回転及び３基底線形形状モデルが提案された方法を使用して再構成された。レジスタリングされた形状は線形形状空間に投影され、３基底変形可能形状を復元した。
【００３６】
別のテスト例は顔形状シーケンスであって、変形が非対称的でランダムではなかった：右まぶた及び眉が開き、左まぶた及び眉が同時に閉じた。これらの形状は固定視点から観測され、剛体性回転及び並進はない。観測された形状は、従って２つの基底の合成であった。ＧＰＡによるレジストレーション及び再構成は明らかに実際には生じなかった回転を含んでいたが、他方で直接因数分解法は正確に形状をレジスタリングし変形可能モデルを再構成した。
【００３７】
心臓及び脳のような人の器官はそれらの形状をいつも動的に又は身体に亘って変化させる。統計形状モデルは、２次元ＭＲＩ脳画像をセグメント化すること及び２Ｄ超音波画像内の心筋壁運動をトラッキングすることのような多くの適用事例においてこれらのオブジェクトの画像を解釈するために利用されてきた。本発明の実施形態による方法は２Ｄ心エコー検査画像における心筋層の形状をレジスタリングすることに及び線形形状空間を抽出することにおいてテストされた。観測データは１２０個の心筋層画像から成った。この方法は基底数を３と決定し、回転及び３基底変形可能形状を復元した。最も支配的な基底は全エネルギの約９０％を占有し、すなわち変形はランダムノイズのように取るに足らなかった。
【００３８】
動的シーンの３Ｄモデリングはロボットナビゲーション及びヴィジュアルサーベイランスのようなタスクにとって重要である。３Ｄシーンが静的な建物及び乗り物又は直線に沿って動く歩行者から成る場合、形状は線形基底から成る。すなわち、静的部分と線形運動である。１つの見本シーケンスは同時にそれぞれの方向に沿って運動する３つのおもちゃを含み、２つはテーブル上にあり、１つはスロープ上にある。シーンの他の部分は静的であった。シーン形状は２つの基底から成り、静的オブジェクトの１つの基底及び線形運動のもう１つの基底である。１８個の形状が異なる視点から観測された。２個の基底ダイナミックシーン形状が正確に直接因数分解法によって再構成された。線形３Ｄ運動は重要であり、非対称的であるので、相応の形状変形はガウス雑音としては取り扱うべきではない。
【００３９】
本発明はハードウェア、ソフトウェア、ファームウェア、特殊用途プロセスの様々な形態又はこれらのコンビネーションにおいてインプリメントされうることを理解すべきである。１つの実施形態では、本発明はソフトウェアにおいてコンピュータリーダブルプログラム記憶装置に得実体的に具現化されたアプリケーションプログラムとしてインプリメントされうる。このアプリケーションプログラムはあらゆる適当なアーキテクチャを有するマシンにアップロードされ実行されうる。
【００４０】
図２は本発明の実施形態による直接因数分解レジストレーション法をインプリメントするための例示的なコンピュータシステムのブロック線図である。図２を参照すると、本発明をインプリメントするためのコンピュータシステム２１はなかんずく中央処理ユニット（ＣＰＵ）２２、メモリ２３及び入力／出力（Ｉ／Ｏ）インターフェース２４を有する。このコンピュータシステム２１は一般的にＩ／Ｏインターフェース２４を介してディスプレイ２５及びマウス及びキーボードのような様々な入力デバイス２６に結合されている。サポート回路はキャッシュ、電力供給部、クロック回路及び通信バスを含みうる。メモリ２３はランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）、ディスクドライブ、テープドライブ等々及びこれらのコンビネーションを含みうる。本発明はメモリ２３に格納されているルーチン２７としてインプリメントされ、ＣＰＵ２２により実行されて信号源２８からの信号を処理する。このように、コンピュータシステム２１は本発明のルーチン２７を実行する場合には特殊用途コンピュータシステムとなる汎用コンピュータシステムである。
【００４１】
コンピュータシステム２１はオペレーティングシステム及びマイクロ命令コードも含む。ここで記述された様々なプロセス及び機能はマイクロ命令コードの部分又はオペレーティングシステムを介して実行されるアプリケーションプログラム（又はこれらのコンビネーション）のいずれかである。さらに、付加的なデータ記憶デバイス及び印刷デバイスのように様々な他の周辺デバイスがコンピュータプラットフォームに接続されうる。
【００４２】
幾つかの制約のために添付図面に記載されたシステムコンポーネント及び方法ステップはソフトウェアにおいてインプリメントされ、システムコンポーネント間の瞬時の接続（プロセスステップ）は本発明がプログラムされるやり方に依存して異なることを理解すべきである。本発明の教示がここで提示されれば、当業者は本発明のこれらの及び類似のインプリメンテーション又はコンフィギュレーションを考えることが可能であろう。
本発明を、有利な実施形態を参照して詳細に説明したが、当業者であれば本発明の種々の変更および置換を、特許請求の範囲に記載された思想および範囲から逸脱せずに行えることを認識できる。
【図面の簡単な説明】
【００４３】
【図１】本発明の実施形態による直接因数分解レジストレーションプロシージャのフローチャートを示す。
【図２】本発明の実施形態による直接因数分解レジストレーションプロシージャをインプリメントするための例示的なコンピュータシステムのブロック線図である。
【符号の説明】
【００４４】
２１ コンピュータシステム
２２ 中央処理ユニット
２３ メモリ
２４ Ｉ／Ｏインターフェース
２５ ディスプレイ
２６ 入力デバイス
２７ ルーチン
２８ 信号源
【技術分野】
【０００１】
関連の米国出願との相互参照
本出願は２００４年９月２日に提出されたXiaoその他の米国特許仮出願番号６０／６０６６３２"Registration and Modeling of Deformable Shapes: A Factorization Approarch"から優先権を請求するものである。この開示内容は、参照によって本願の開示内容に含まれる。
【０００２】
技術分野
本発明はデジタル化された画像における変形可能な形状のレジストレーションに関する。
【０００３】
関連技術の説明
変形可能なオブジェクトの統計的形状モデルは、２次元ＭＲＩ脳画像をセグメント化すること、３次元超音波画像から心筋壁運動をトラッキングすること及び２次元ビデオから人の顔を認識することのような多くのタスクにとって重要である。しかし、多くの測定方法は局所座標系に関連してオブジェクト形状の座標を、例えば、異なる視点から得られる人の顔の２Ｄ画像又は人の心臓の３Ｄ超音波ボリュームを発生する。形状モデルを抽出するためには、異なる局所座標系におけるこれらの測定値は共通座標系にレジスタリングされる必要がある。
【０００４】
オブジェクトが剛体的（rigid）である場合には、観測される形状の変化は局所座標系の配向とスケールとの間の差から由来する。これらの形状のレジストレーションはスケーリング、回転及び並進を含むこれらの間の相似変換の推定に帰する。
【０００５】
現実の世界では、多くの生物学的オブジェクト及び自然のシーンが人の顔及び心臓のようにその形状を変化させる。観測される形状の変化は互いに結合された２つのファクタに起因する：剛体相似変換（rigid similarity transformation）と非剛体形状変形（non-rigid shape deformation）である。レジストレーションの目的は、従ってこれら２つのファクタを分解及び復元することである。１つのよく知られたアプローチ、一般化プロクラステス分析（Generalized Procrustes Analysis ＧＰＡ）は形状変形をガウス雑音として取り扱い、各々観測される形状をセントロイド形状によりアラインする。このセントロイド形状は剛体ケースのように既にアラインされた形状の平均である。このレジストレーションプロセスはそれが安定したセントロイドに収束するまで繰り返される。
【０００６】
変形可能なオブジェクトの形状は、２Ｄ及び３Ｄの人の顔の形状及び２Ｄの心筋形状のようにしばしばある種の形状基底の線形結合である。このような形状変形はほんのわずかである場合、すなわち平均形状が変形に比べて優位である場合、又は、これらが平均形状に関して対称的である場合、すなわち、正の及び負のオフセットが互いにキャンセルしあう場合、これらの変形はガウス雑音として見なすことができ、一般化プロクラステス分析は変形可能な形状をレジスタリングすることにおいて成功裡に作用する。次いで主成分分析がアラインされた形状に対して適用され、線形形状変形モデルを計算することができる。しかし、多くの適用事例においては、形状変形が大きく、非対称的であり、例えば動かない建物及び動く乗り物から成る動的シーン又は２つの目の非同期的にまばたきする場合がそうである。このような状況では、形状変形はガウス雑音とは見なせない。一般化プロクラステス分析はレジストレーションプロセスの間の非剛体形状変形を考慮にいれないので、このような変形はレジストレーション及び結果的に得られる線形形状モデルに偏りをもたらすだろう。
【０００７】
本発明の概要
ここで記述される本発明の例示的な実施形態は一般的に剛体相似変換（rigid similarity transformation）と非剛体形状変形（non-rigid shape deformations）とをデカップリングする直接因数分解レジストレーション（direct factorization registration）のための方法及びシステムを含む。直接因数分解は、同時に任意の次元における変形可能な形状をレジスタリングすること及び線形変形モデルを再構成することに対して線形な閉じた形式解を与える。変形可能な形状の線形基底表示は成功裡に２Ｄ画像から３Ｄ形状を復元するために使用されている。直接因数分解法は剛体回転の正規直交性（orthonormality）及び変形可能な形状基底の一意性（uniqueness）にそれぞれ線形な制約を課し、同時に観測された形状のレジストレーションと変形基底の再構成とに対する線形な閉じた形式の解を与える。
【０００８】
本発明の例示的な実施形態は、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法を提供し、変形可能な形状の測定値のセットを提供し、測定値のこのセットは測定値行列を形成するステップと、同時に剛体レジスタリング変換（rigid registering transformation）及び線形形状モデル（linear shape model）について解くステップとから成る。
【０００９】
本発明の別の例示的な実施形態は、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法を提供し、この方法は、Ｄ次元の変形可能な形状のＰ個の地点のＮ個の測定値の測定値行列Ｗを提供するステップと、Ｎ個の測定値に対する基底数Ｋを決定し、ここでＫ＜Ｎであり、さらに基底セットとして測定値行列ＷのＫ個の測定値をセレクトするステップと、測定値行列Ｗを行列積Ｍｘ∃Ｂに分解し、ここでＭは提案されたスケーリングされた回転行列であり、Ｂは提案された基底行列であるステップと
【数１】
により定義された行列Ｑkを計算し、ここでΦは
を表し、これは提案されたスケーリングされた回転行列及び提案された基底行列を真のスケーリングされた回転行列及び真の基底行列に変換するアンビギュイティ行列を表すステップと、行列Ｑkをｋ＝１，．．．，ＫにおいてｇkｇkTに分解し、ここでｇkはＤ∃Ｋ％Ｄ∃Ｋ行列Ｇの列であるステップと、真のスケーリングされた回転行列をＭｘ∃Ｇから及び真の基底行列をＧ-1ｘ∃Ｂから復元するステップを有する。
【００１０】
本発明の更に別の実施形態は、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングするための方法ステップを実施するためにコンピュータにより実行可能な命令のプログラムを実体的に具現化するコンピュータによりリーダブルなプログラム記憶装置において、方法ステップは次のステップを含む、すなわち、変形可能な形状の測定値のセットを提供し、測定値のセットは測定値行列を形成するステップと、同時に剛体レジスタリング変換及び線形形状モデルについて解くステップとを含む。
【００１１】
図面の簡単な説明
図１は本発明の実施形態による直接因数分解レジストレーションプロシージャのフローチャートを示す。
【００１２】
図２は本発明の実施形態による直接因数分解レジストレーションプロシージャをインプリメントするための例示的なコンピュータシステムのブロック線図である。
【００１３】
有利な実施形態の詳細な説明
ここで記述されるような本発明の例示的な実施形態は一般的に剛体相似変換と非剛体形状変形とをデカップリングする直接因数分解レジストレーションのためのシステム及び方法を含む。
【００１４】
本発明の実施形態によれば、非剛体オブジェクトの形状はＫ個の形状基底｛Ｂk，ｋ＝１，．．．，Ｋ｝の線形結合として見なされうる。各基底はＤｘＰ行列であり、この行列は形状の上のＰ個の地点をしてＤ次元オブジェクト形状空間の中での位置を変えるように指示する。よって、時間ｉにおけるこの形状の座標は
【数２】
であり、ここでｌikは基底Ｂkの結合ウェイトである。このオブジェクト形状は異なるビューから、異なる距離において、異なるスケールで測定されうる。
【００１５】
よって、オブジェクト形状とその測定値との間の相似変換が存在し、これは
【数３】
であり、ここでｃiは非零スカラーであり、ＲiはＤｘＤ正規直交行列であり、ＴiはＤｘ１ベクトルであり、これらはそれぞれスケーリング、回転及び並進変換を表し、一緒になって相似変換を形成する。１は１ｘＰベクトルであり、その全ての要素は１である。Ｓiを式（１）を使用して置き換え、ｃiをｌikの中に吸収すると、
【数４】
が得られる。もし変形可能なオブジェクトのＮ個の観測値が測定されるならば、測定値はＤＮｘＰ行列Ｗの中にスタックされうる。Ｗの中のＮ個のＤ行の各々は観測された形状をそれぞれ含む。式（３）により、全ての観測された形状は形状基底の同一セットに関するので、次式
【数５】
が得られ、ここでＭはスケーリングされたＤＮｘＤＫ回転行列であり、ＢはＤＫｘＰ基底行列であり、ＴはＤＮｘ１並進ベクトルであり、
【数６】
のように示される。
【００１６】
よって、変形可能な形状のレジストレーション及びモデリングは同時にＭ及びＴにおける剛体相似変換を復元しＢにおける非剛体変形モデルを再構成するために測定値行列Ｗを分解することを含む。観測された形状を正確にアラインするためには、Ｗにおける測定値を式（４）のように直接因数分解するべきであり、この結果、Ｂにおける変形可能な形状基底及びＭ及びＴにおける剛体相似変換を再構成する。
【００１７】
本発明の実施形態によれば、Ｗを因数分解する第１のステップは世界座標原点を観測された形状の中心に置くことである。この場合、Ｔにおける並進は形状地点の平均座標に等しい。これらを測定値から減算することによって
【数７】
が得られる。形状変形及び剛体回転が両方とも非退化（nondegenerate）であると仮定すると、すなわちスケーリングされた回転行列Ｍ及び形状基底行列Ｂが両方とも式（５）に従ってフルの階数を持つと仮定すると、Ｍの階数はmin｛ＤＫ，ＤＮ，Ｐ｝であり、Ｂの階数はmin｛ＤＫ，Ｐ｝である。これらの積
は階数min｛ＤＫ，ＤＮ，Ｐ｝を持つ。一般的に、形状数Ｎ及び地点数Ｐは基底数Ｋよりもはるかに大きく、すなわちＤＮ＞ＤＫ及びＰ＞ＤＫ。
【００１８】
の階数は従ってＤＫであり、Ｋは
【数８】
によって決定される。
【００１９】
本発明の実施形態によれば、特異値分解（ＳＶＤ）は
をＤＮｘＤＫ行列
とＤＫｘＰ行列
との積に分解するために使用されうる。この分解は正則ＤＫｘＤＫ線形変換によってしか決定されない。真のスケーリングされた回転Ｍ及び基底Ｂは
【数９】
の形式をもち、ここでＧはＭ及びＢを決定する正則ＤＫｘＤＫアンビギュイティ変換である。変形可能な形状レジストレーション及びモデリングの決定は今や
が与えられた時にＧを計算することになる。
【００２０】
行列ＧはＫ個のＤ列を有し、ｇk，ｋ＝１，．．．，Ｋと表され、ここで各列はＤＫｘＤ行列である。これらの列は互いに独立している。というのも、Ｇは正則であるからである。式（５，６）によれば、ｇkは次式
【数１０】
を満たし、ここで
はＮ個のＤ行を有し、
と表され、ここで各行はＤｘＤＫ行列である。Ｑk＝ｇkｇkTとすると、ＤＫｘＤＫ対称行列がアンビギュイティ行列列の積によって形成された。この場合、
【数１１】
である。Ｑkを計算するためには、２つのタイプの制約が利用可能である：回転行列の正規直交性及び形状基底の一意性である。
【００２１】
回転行列への正規直交性制約は２Ｄ画像から３Ｄ構造及び動きを推論するために使用されうる。上記の式から、回転の正規直交性のために、
【数１２】
が得られ、ここでＩDxDはＤｘＤ恒等行列である。上のＤ個の対角要素は同値であり、Ｑkに対するＤ−１個の線形制約をもたらす。非対角要素は全てゼロである。Ｑkは対称であるので、（Ｄ2−Ｄ）/２個の線形制約がある。
【００２２】
本発明の実施形態によれば、（Ｎ/２）（Ｄ2＋Ｄ−２）個の線形制約がＮ個の観測される形状に対して得られる。対称行列Ｑkは（Ｄ2Ｋ2＋ＤＫ）/２個の別個の要素を有する。Ｎが十分に大きく、この結果、Ｎ≧（Ｄ2Ｋ2＋ＤＫ）/（Ｄ2＋Ｄ−２）である場合、Ｑkは式（９）における線形正規直交性制約を使用して決定される。しかし、これらの制約のほとんどは他に依存し、従って冗長である。しかし、正規直交性制約についての一般解がＱk＝Ｇ（Ω＋Λ）ＧTであることが示されうる。ただしここでΩは任意のブロック歪対称行列（block-skew-symmetric matrix）であり、Λは任意のブロックスケールド恒等行列である。これらのΛ及びΩは対称的である。Λの各ＤｘＤブロックはスケーリングされた恒等行列である。Ωの全ての対角ＤｘＤブロックは零行列であり、非対角ＤｘＤブロックは全て歪対称行列である。
【００２３】
Λ及びΩはそれぞれ（Ｋ2＋Ｋ）/２及び（Ｋ2−Ｋ）（Ｄ2−Ｄ）/４個の変数を有する。それゆえ、たとえ変形可能な形状の観測が何回測定されようとも、正規直交性制約だけを実施すると（（Ｋ2−Ｋ）（Ｄ2−Ｄ）＋２（Ｋ2＋Ｋ））/４個の自由度を有する曖昧な解空間をもたらす。さらに、この空間は無効解を含む。特に、所望されるＱk＝ｇkｇkTが半正値であるので、解Ｑk＝Ｇ（Ω＋Λ）ＧTは（Ω＋Λ）が半正値でない場合には有効ではない。このような無効解は実際この空間内に存在する。例えば、Λ＝０である場合、（Ω＋Λ）がブロック歪対称行列Ωに等しく、これは半正値でない。
【００２４】
正規直交性制約が本来的に曖昧である理由は、それが形状基底の一意的なセットを決定できないからである。これらの基底に適用されるどんな正則線形変換も結果的に適当な基底の別のセットをもたらす。アンビギュイティを排除するために、形状基底の一意性を保証する制約が実施される。
【００２５】
のＤＫｘＰ部分行列はＫ個の観測された形状から形成され、ここでＫは予め決定された基底数である。
【００２６】
の条件数は基礎となる変形可能な形状の独立性の尺度である。比較的小さい条件数は比較的強い独立性に関連する。本発明の実施形態によれば、Ｋ個の観測される形状の各可能なセットの条件数が計算され、最小条件数を有するセットがセレクトされる。このセットは最も独立したＫ個の変形可能な形状を含む。線形変形空間内のＫ個の独立した形状はどれでも基底のセットと見なされるので、これらの変形可能な形状は一意的な基底セットと規定され、すなわちセレクトされた観測はそれぞれスケーリングされ回転された形状基底である。スケーリングは形状の独立性には影響を与えないので、スカラーは基底の中に吸収され、セレクトされた観測は単に回転された基底である。
【００２７】
第１のＫ個の測定値としてセレクトされた観測を表し、すなわち、
とすると、相応する係数は
【数１３】
である。式（８、１０）によれば：
【数１４】
であり、ここでΦは
を表す。これらの４Ｎ（Ｋ−１）個の線形制約は一意的に形状基底を決定する。
【００２８】
式（９）及び式（１１）の線形方程式を解くことはＱk＝ｇkｇkT，ｋ＝１，．．．．，Ｋの閉じた形式の解をもたらす。ｇkはＱkをＳＶＤを介して分解することによって復元されうる。Ｑkの分解は任意のＤｘＤ正規直交変換Ψによる。というのも、（ｇkΨ）（ｇkΨ）TもＱkに等しいからである。このアンビギュイティはｇ1，．．．，ｇkが異なる座標系の下で独立に推定されるという事実に起因する。このアンビギュイティを解消するためには、ｇ1，．．．，ｇkが単一の基準座標系の下に変換される必要がある。
【００２９】
しかし、式（７）のために
【数１５】
である。回転行列Ｒiは正規直交なので、つまり
【数１６】
である。正負の符号は基準座標系の配向によって決定される。本発明の実施形態によれば、回転のＫ個のセットはｇ1，．．．，ｇkを使用してそれぞれ計算される。分解アンビギュイティのゆえに、各々２つのセットの間にはＤｘＤ正規直交変換がある。回転セットのうちの１つが基準として指定される。他の回転の正負の符号が相応の基準回転と矛盾しないように決定される。正規直交変換は直交プロクラステス分析によって計算され、正負の符号が付けられた回転セットを基準セットに変換する。これらの正規直交変換はｇ1，．．．，ｇkも共通座標系の下にあるように変換する。すなわち、所望のアンビギュイティ変換Ｇが達成される。この場合、係数は式（７）によって計算され、形状基底は式（６）によって復元される。これらの結合は変形可能な形状を再構成する。
【００３０】
本発明の実施形態による直接因数分解レジストレーションプロシージャのフローチャートが図１に記載されている。この図を参照すると、レジストレーションはステップ１１で並進Ｔを測定値Ｗの平均として計算することによって始まり、ついでそれを
【数１７】
によって消去する。その後、ステップ１２においてＳＶＤが
【数１８】
を因数分解するために実施され、ここでＭはＤＮ％ＤＫ行列であり、ＢはＤＫ％Ｐ行列である。エネルギを支配する
の階数はこの場合ＤＫである。基底数Ｋは
【数１９】
と定義され、ここでＤはオブジェクト形状空間の次元である。ステップ１３では、Ｋ個の観測Ｗkがセレクトされ、
が整理しなおされ（reordered）、
【数２０】
のrank-ＤＫ近似がＳＶＤにより計算される。ステップ１４では、行列Ｑk，ｋ＝１，．．．，Ｋが最小二乗アルゴリズムを介して式（９）及び（１１）の線形方程式
【数２１】
を解くことによって計算される。ステップ１５ではＧの列ｇk，ｋ＝１，．．．，ＫがＳＶＤを介して計算され、回転が
【数２２】
から復元される。回転は直交プロクラステス分析を使用して共通座標系に変換される。ステップ１６では、線形形状モデルが
【数２３】
から復元され、係数が
【数２４】
から復元される。これらの結合がレジスタリングされた形状を再構成する。計算コストをセーブするために、一度十分小さい条件数を有するＫ個の観測された形状のグループが配置されたら基底観測のサーチをストップすることができる。とういうのも、これらは独立した形状のセットを指定するが、比較的独立した形状は比較的信頼性の高いレジストレーションをもたらすからである。基底数が１と決定される場合、形状は剛体的だがノイジーなデータとして取り扱われ、ＧＰＡのレジストレーションに類似の最小二乗レジストレーションが達成される。
【００３１】
本発明の実施形態による方法のパフォーマンスは人の顔、心筋層及び動的シーンを含むシミュレートされたデータとリアルなデータの両方を使用してテストされた。
【００３２】
直接因数分解法の精度及びロバスト性は異なる測定ノイズレベル及び基底数に関連して定量的に評価された。ガウス白色雑音を仮定すると、ノイズ強度はノイズのフロベニウスノルム（Frobenius norm）と測定値との間の比率：
によって表された。アルゴリズムはそれぞれ５つの異なるノイズレベル０％、５％、１０％、１５％及び２０％においてテストされた。各レベルにおいて、２Ｄ空間内で剛体設定が１個の基底に関して、非剛体設定がそれぞれ２，．．．，及び１０個の基底に関して試験された。各設定に対して、１００回のトライアルがテストされた。各トライアルにおいて、これらの基底はランダムに発生され、ノーマライズされた（｜Ｂi｜＝１）。よって、これらは一般的に非対称的であった。６６個の形状がこれらの基底の線形結合として構成された。結合ウェイトは、異なる基底に対するウェイトが同じオーダの大きさを有するように、すなわち基底のうちの１つが優位でないようにランダムに発生された。これらの形状は次いで観測値を発生するためにランダムにスケーリングされ、回転され、並進され、ノイズを添加された。基底は等しく形状合成に寄与し、基底数が大きくなればなるほど、形状はますます「非剛体的」になり、個々の基底に対するノイズは強くなる。従って、一般的に、レジストレーションは比較的多くの基底が含まれる場合に測定ノイズに対して比較的敏感である。
【００３３】
観測された形状はそれぞれ提案された方法及びＧＰＡによってレジスタリングされた。回転の空間は多様体なので、誤差はリーマン距離
【数２５】
として度で測定された。形状基底はアラインされた形状を使用して再構成され、これらのアラインされた形状はこの場合復元された形状空間に投影され所望の変形可能な形状を得る。形状における相対的な再構成誤差は
として計算された。
【００３４】
ノイズレベルが０％であった場合、直接因数分解法はいつも正確な剛体回転及び変形可能な形状をゼロ誤差で復元した。ノイズが印加された場合、予期したように、レジストレーションはノイズにより敏感になり、誤差は基底数が大きい場合ほど大きかった。しかし、直接因数分解法は例えば１０個の基底及び２０％のノイズレベルの最悪のケースでもリーズナブルな精度を達成した。形状における平均誤差は１８％より小さく、回転における平均誤差は７．５度より小さかった。剛体設定において、両方の方法は形状を剛体的だがノイジーなデータとして取り扱い、よって同様な性能を示した。しかし、ＧＰＡは全ての非剛体トライアルにおいて劣った。ノイズのないケースでさえ、このＧＰＡは形状において注目すべき誤差２２％を、回転において１１度を生じた。ＧＰＡによる誤差は基底数が大きくなると大きくなった。しかし、ＧＰＡのパフォーマンスはノイズに対してあまり敏感でなかった。なぜなら、ＧＰＡはガウス白色雑音に対して敏感でない最小二乗解を計算するからである。
【００３５】
人の顔は高度に非剛体的なオブジェクトである。それは顔形状の２Ｄ画像がいくつかの基底構造の線形結合であることに示されている。この線形統計モデルは顔トラッキング及び認識のようなタスクにとって役立つ。１つのテストシーケンスは顔回転及び瞬き及び笑みのような顔面表情を含む１８０個の画像を含んでいた。２次元顔形状は６８個の特徴点によって表示された。形状測定値から並進を、すなわち平均座標を減算すると、並進された形状はこの場合変形及び回転から構成された。基底の数は３と推定され、この結果、並進された形状のエネルギの９９％は階数制約による分解の後に残りうる。次いで剛性回転及び３基底線形形状モデルが提案された方法を使用して再構成された。レジスタリングされた形状は線形形状空間に投影され、３基底変形可能形状を復元した。
【００３６】
別のテスト例は顔形状シーケンスであって、変形が非対称的でランダムではなかった：右まぶた及び眉が開き、左まぶた及び眉が同時に閉じた。これらの形状は固定視点から観測され、剛体性回転及び並進はない。観測された形状は、従って２つの基底の合成であった。ＧＰＡによるレジストレーション及び再構成は明らかに実際には生じなかった回転を含んでいたが、他方で直接因数分解法は正確に形状をレジスタリングし変形可能モデルを再構成した。
【００３７】
心臓及び脳のような人の器官はそれらの形状をいつも動的に又は身体に亘って変化させる。統計形状モデルは、２次元ＭＲＩ脳画像をセグメント化すること及び２Ｄ超音波画像内の心筋壁運動をトラッキングすることのような多くの適用事例においてこれらのオブジェクトの画像を解釈するために利用されてきた。本発明の実施形態による方法は２Ｄ心エコー検査画像における心筋層の形状をレジスタリングすることに及び線形形状空間を抽出することにおいてテストされた。観測データは１２０個の心筋層画像から成った。この方法は基底数を３と決定し、回転及び３基底変形可能形状を復元した。最も支配的な基底は全エネルギの約９０％を占有し、すなわち変形はランダムノイズのように取るに足らなかった。
【００３８】
動的シーンの３Ｄモデリングはロボットナビゲーション及びヴィジュアルサーベイランスのようなタスクにとって重要である。３Ｄシーンが静的な建物及び乗り物又は直線に沿って動く歩行者から成る場合、形状は線形基底から成る。すなわち、静的部分と線形運動である。１つの見本シーケンスは同時にそれぞれの方向に沿って運動する３つのおもちゃを含み、２つはテーブル上にあり、１つはスロープ上にある。シーンの他の部分は静的であった。シーン形状は２つの基底から成り、静的オブジェクトの１つの基底及び線形運動のもう１つの基底である。１８個の形状が異なる視点から観測された。２個の基底ダイナミックシーン形状が正確に直接因数分解法によって再構成された。線形３Ｄ運動は重要であり、非対称的であるので、相応の形状変形はガウス雑音としては取り扱うべきではない。
【００３９】
本発明はハードウェア、ソフトウェア、ファームウェア、特殊用途プロセスの様々な形態又はこれらのコンビネーションにおいてインプリメントされうることを理解すべきである。１つの実施形態では、本発明はソフトウェアにおいてコンピュータリーダブルプログラム記憶装置に得実体的に具現化されたアプリケーションプログラムとしてインプリメントされうる。このアプリケーションプログラムはあらゆる適当なアーキテクチャを有するマシンにアップロードされ実行されうる。
【００４０】
図２は本発明の実施形態による直接因数分解レジストレーション法をインプリメントするための例示的なコンピュータシステムのブロック線図である。図２を参照すると、本発明をインプリメントするためのコンピュータシステム２１はなかんずく中央処理ユニット（ＣＰＵ）２２、メモリ２３及び入力／出力（Ｉ／Ｏ）インターフェース２４を有する。このコンピュータシステム２１は一般的にＩ／Ｏインターフェース２４を介してディスプレイ２５及びマウス及びキーボードのような様々な入力デバイス２６に結合されている。サポート回路はキャッシュ、電力供給部、クロック回路及び通信バスを含みうる。メモリ２３はランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）、ディスクドライブ、テープドライブ等々及びこれらのコンビネーションを含みうる。本発明はメモリ２３に格納されているルーチン２７としてインプリメントされ、ＣＰＵ２２により実行されて信号源２８からの信号を処理する。このように、コンピュータシステム２１は本発明のルーチン２７を実行する場合には特殊用途コンピュータシステムとなる汎用コンピュータシステムである。
【００４１】
コンピュータシステム２１はオペレーティングシステム及びマイクロ命令コードも含む。ここで記述された様々なプロセス及び機能はマイクロ命令コードの部分又はオペレーティングシステムを介して実行されるアプリケーションプログラム（又はこれらのコンビネーション）のいずれかである。さらに、付加的なデータ記憶デバイス及び印刷デバイスのように様々な他の周辺デバイスがコンピュータプラットフォームに接続されうる。
【００４２】
幾つかの制約のために添付図面に記載されたシステムコンポーネント及び方法ステップはソフトウェアにおいてインプリメントされ、システムコンポーネント間の瞬時の接続（プロセスステップ）は本発明がプログラムされるやり方に依存して異なることを理解すべきである。本発明の教示がここで提示されれば、当業者は本発明のこれらの及び類似のインプリメンテーション又はコンフィギュレーションを考えることが可能であろう。
本発明を、有利な実施形態を参照して詳細に説明したが、当業者であれば本発明の種々の変更および置換を、特許請求の範囲に記載された思想および範囲から逸脱せずに行えることを認識できる。
【図面の簡単な説明】
【００４３】
【図１】本発明の実施形態による直接因数分解レジストレーションプロシージャのフローチャートを示す。
【図２】本発明の実施形態による直接因数分解レジストレーションプロシージャをインプリメントするための例示的なコンピュータシステムのブロック線図である。
【符号の説明】
【００４４】
２１ コンピュータシステム
２２ 中央処理ユニット
２３ メモリ
２４ Ｉ／Ｏインターフェース
２５ ディスプレイ
２６ 入力デバイス
２７ ルーチン
２８ 信号源
【特許請求の範囲】
【請求項１】
デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法において、該方法は次のステップを有する、すなわち、
変形可能な形状の測定値のセットを提供し、該測定値のセットは測定値行列を形成するステップと、
同時に剛体レジスタリング変換（rigid registering transformation）及び線形形状モデル（linear shape model）について解くステップとを有する、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法。
【請求項２】
剛体レジスタリング変換及び線形形状モデルについて同時に解くステップは次のステップを有する、すなわち、
前記測定値のセットの平均を形成し、該平均を前記測定値のセットから減算するステップと、
前記測定値行列を提案されたスケーリングされた回転行列と提案された基底行列との積へと分解するステップと、
前記提案されたスケーリングされた回転行列及び前記提案された基底行列からアンビギュイティ変換（ambiguity transformation）の積行列を計算するステップと、
前記積行列を制約及び分解してアンビギュイティ変換行列を決定するステップと、
該アンビギュイティ変換行列を使用して真のスケーリングされた回転行列及び真の基底行列を決定するステップと、
前記真のスケーリングされた回転行列及び前記真の基底行列からレジスタリングされた形状を構成するステップとを有する、請求項１記載の方法。
【請求項３】
さらに測定値行列の階数及び該階数から基底数Ｋを決定することを有する、請求項２記載の方法。
【請求項４】
測定値のセットはＮ個の測定値のセットからセレクトされたＫ個の測定値のサブセットであり、ここでＫ＜Ｎであり、さらに前記セレクトされたサブセットはＫ個の測定値の全ての可能なサブセットの最小条件数を有する、請求項３記載の方法。
【請求項５】
前記測定値行列は特異値分解を使用して分解される、請求項２記載の方法。
【請求項６】
アンビギュイティ変換行列は提案されたスケーリングされた回転行列に正規直交性制約（orthonomality constraints）を課することによって及び提案された基底行列に一意性制約（uniqueness constraints）を課することによって計算される、請求項４記載の方法。
【請求項７】
前記アンビギュイティ変換行列は特異値分解を使用して分解される、請求項２記載の方法。
【請求項８】
提案された基底行列に一意性制約を課することはさらに回転された基底セットとして最小条件数を有するＫ個の測定値をセレクトすること及び提案されたスケーリングされた回転行列に対するスケーリング係数を計算することから成る、請求項６記載の方法。
【請求項９】
直交プロクラステス分析を使用してアンビギュイティ変換行列を共通座標系に変換するステップをさらに有する、請求項７記載の方法。
【請求項１０】
デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法において、該方法は次のステップを有する、すなわち、
Ｄ次元の変形可能な形状のＰ個の地点のＮ個の測定値の測定値行列Ｗを提供するステップと、
Ｎ個の測定値に対する基底数Ｋを決定し、ここでＫ＜Ｎであり、さらに基底セットとして前記測定値行列ＷのＫ個の測定値をセレクトするステップと、
前記測定値行列Ｗを行列積Ｍｘ∃Ｂに分解し、ここでＭは提案されたスケーリングされた回転行列であり、Ｂは提案された基底行列であるステップと、
【数１】
により定義された行列Ｑkを計算し、ここでΦは
を表し、これは提案されたスケーリングされた回転行列及び提案された基底行列を真のスケーリングされた回転行列及び真の基底行列に変換するアンビギュイティ行列を表すステップと、
行列Ｑkをｋ＝１，．．．，ＫにおいてｇkｇkTに分解し、ここでｇkはＤ∃Ｋ％Ｄ∃Ｋ行列Ｇの列であるステップと、
真のスケーリングされた回転行列をＭｘ∃Ｇから及び真の基底行列をＧ-1ｘ∃Ｂから復元するステップを有する、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法。
【請求項１１】
測定値行列ＷはサイズＤ∃Ｎｘ％Ｐを持ち、さらに前記測定値行列Ｗの階数Ｄ∃Ｋを決定するために該測定値行列Ｗを分解することを含み、基底数Ｋはrank（Ｗ）/Ｄにより定義される、請求項１０記載の方法。
【請求項１２】
提案されたスケーリングされた回転行列ＭはサイズＤ∃Ｎｘ％Ｄ∃Ｋを持ち、提案された基底行列ＢはサイズＤ∃Ｋｘ％Ｐを持つ、請求項１１記載の方法。
【請求項１３】
行列Ｑkは最小二乗アルゴリズムにより計算される、請求項１０記載の方法。
【請求項１４】
スケーリングされない回転Ｒiはスケーリングされた回転行列ＭのサイズＤ％Ｎ行Ｍiに対して
【数２】
によってｇkから決定される、請求項１０記載の方法。
【請求項１５】
デジタル化された画像における変形可能な形状をレジスタリング及びモデリングするための方法ステップを実施するためにコンピュータにより実行可能な命令のプログラムを実体的に具現化するコンピュータによりリーダブルなプログラム記憶装置において、前記方法ステップは次のステップを含む、すなわち、
変形可能な形状の測定値のセットを提供し、該測定値のセットは測定値行列を形成するステップと、
同時に剛体レジスタリング変換及び線形形状モデルについて解くステップとを含む、コンピュータによりリーダブルなプログラム記憶装置。
【請求項１６】
剛体レジスタリング変換及び線形形状モデルについて同時に解くステップは次のステップを含む、すなわち、
前記測定値のセットの平均を形成し、該平均を前記測定値のセットから減算するステップと、
前記測定値行列を提案されたスケーリングされた回転行列と提案された基底行列との積へと分解するステップと、
前記提案されたスケーリングされた回転行列及び前記提案された基底行列からアンビギュイティ変換の積行列を計算するステップと、
前記積行列を制約及び分解してアンビギュイティ変換行列を決定するステップと、
前記アンビギュイティ変換行列を使用して真のスケーリングされた回転行列及び真の基底行列を決定するステップと、
前記真のスケーリングされた回転行列及び前記真の基底行列からレジスタリングされた形状を構成するステップとを含む、請求項１５記載のコンピュータリーダブルプログラム記憶装置。
【請求項１７】
さらに前記測定値行列の階数及び該階数から基底数Ｋを決定することを含む、請求項１６記載のコンピュータリーダブルプログラム記憶装置。
【請求項１８】
測定値のセットはＮ個の測定値のセットからセレクトされたＫ個の測定値のサブセットであり、ここでＫ＜Ｎであり、さらに前記セレクトされたサブセットはＫ個の測定値の全ての可能なサブセットの最小条件数を有する、請求項１７記載のコンピュータリーダブルプログラム記憶装置。
【請求項１９】
測定値行列は特異値分解を使用して分解される、請求項１６記載のコンピュータリーダブルプログラム記憶装置。
【請求項２０】
アンビギュイティ変換行列は提案されたスケーリングされた回転行列に正規直交性制約を課することによって及び提案された基底行列に一意性制約を課することによって計算される、請求項１８記載のコンピュータリーダブルプログラム記憶装置。
【請求項２１】
アンビギュイティ変換行列は特異値分解を使用して分解される、請求項１６記載のコンピュータリーダブルプログラム記憶装置。
【請求項２２】
提案された基底行列に一意性制約を課することはさらに回転された基底セットとして最小条件数を有するＫ個の測定値をセレクトすること及び提案されたスケーリングされた回転行列に対するスケーリング係数を計算することを含む、請求項２０記載のコンピュータリーダブルプログラム記憶装置。
【請求項２３】
直交プロクラステス分析を使用してアンビギュイティ変換行列を共通座標系に変換するステップをさらに含む、請求項２１記載のコンピュータリーダブルプログラム記憶装置。
【請求項１】
デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法において、該方法は次のステップを有する、すなわち、
変形可能な形状の測定値のセットを提供し、該測定値のセットは測定値行列を形成するステップと、
同時に剛体レジスタリング変換（rigid registering transformation）及び線形形状モデル（linear shape model）について解くステップとを有する、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法。
【請求項２】
剛体レジスタリング変換及び線形形状モデルについて同時に解くステップは次のステップを有する、すなわち、
前記測定値のセットの平均を形成し、該平均を前記測定値のセットから減算するステップと、
前記測定値行列を提案されたスケーリングされた回転行列と提案された基底行列との積へと分解するステップと、
前記提案されたスケーリングされた回転行列及び前記提案された基底行列からアンビギュイティ変換（ambiguity transformation）の積行列を計算するステップと、
前記積行列を制約及び分解してアンビギュイティ変換行列を決定するステップと、
該アンビギュイティ変換行列を使用して真のスケーリングされた回転行列及び真の基底行列を決定するステップと、
前記真のスケーリングされた回転行列及び前記真の基底行列からレジスタリングされた形状を構成するステップとを有する、請求項１記載の方法。
【請求項３】
さらに測定値行列の階数及び該階数から基底数Ｋを決定することを有する、請求項２記載の方法。
【請求項４】
測定値のセットはＮ個の測定値のセットからセレクトされたＫ個の測定値のサブセットであり、ここでＫ＜Ｎであり、さらに前記セレクトされたサブセットはＫ個の測定値の全ての可能なサブセットの最小条件数を有する、請求項３記載の方法。
【請求項５】
前記測定値行列は特異値分解を使用して分解される、請求項２記載の方法。
【請求項６】
アンビギュイティ変換行列は提案されたスケーリングされた回転行列に正規直交性制約（orthonomality constraints）を課することによって及び提案された基底行列に一意性制約（uniqueness constraints）を課することによって計算される、請求項４記載の方法。
【請求項７】
前記アンビギュイティ変換行列は特異値分解を使用して分解される、請求項２記載の方法。
【請求項８】
提案された基底行列に一意性制約を課することはさらに回転された基底セットとして最小条件数を有するＫ個の測定値をセレクトすること及び提案されたスケーリングされた回転行列に対するスケーリング係数を計算することから成る、請求項６記載の方法。
【請求項９】
直交プロクラステス分析を使用してアンビギュイティ変換行列を共通座標系に変換するステップをさらに有する、請求項７記載の方法。
【請求項１０】
デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法において、該方法は次のステップを有する、すなわち、
Ｄ次元の変形可能な形状のＰ個の地点のＮ個の測定値の測定値行列Ｗを提供するステップと、
Ｎ個の測定値に対する基底数Ｋを決定し、ここでＫ＜Ｎであり、さらに基底セットとして前記測定値行列ＷのＫ個の測定値をセレクトするステップと、
前記測定値行列Ｗを行列積Ｍｘ∃Ｂに分解し、ここでＭは提案されたスケーリングされた回転行列であり、Ｂは提案された基底行列であるステップと、
【数１】
により定義された行列Ｑkを計算し、ここでΦは
を表し、これは提案されたスケーリングされた回転行列及び提案された基底行列を真のスケーリングされた回転行列及び真の基底行列に変換するアンビギュイティ行列を表すステップと、
行列Ｑkをｋ＝１，．．．，ＫにおいてｇkｇkTに分解し、ここでｇkはＤ∃Ｋ％Ｄ∃Ｋ行列Ｇの列であるステップと、
真のスケーリングされた回転行列をＭｘ∃Ｇから及び真の基底行列をＧ-1ｘ∃Ｂから復元するステップを有する、デジタル化された画像における変形可能な形状をレジスタリング及びモデリングする方法。
【請求項１１】
測定値行列ＷはサイズＤ∃Ｎｘ％Ｐを持ち、さらに前記測定値行列Ｗの階数Ｄ∃Ｋを決定するために該測定値行列Ｗを分解することを含み、基底数Ｋはrank（Ｗ）/Ｄにより定義される、請求項１０記載の方法。
【請求項１２】
提案されたスケーリングされた回転行列ＭはサイズＤ∃Ｎｘ％Ｄ∃Ｋを持ち、提案された基底行列ＢはサイズＤ∃Ｋｘ％Ｐを持つ、請求項１１記載の方法。
【請求項１３】
行列Ｑkは最小二乗アルゴリズムにより計算される、請求項１０記載の方法。
【請求項１４】
スケーリングされない回転Ｒiはスケーリングされた回転行列ＭのサイズＤ％Ｎ行Ｍiに対して
【数２】
によってｇkから決定される、請求項１０記載の方法。
【請求項１５】
デジタル化された画像における変形可能な形状をレジスタリング及びモデリングするための方法ステップを実施するためにコンピュータにより実行可能な命令のプログラムを実体的に具現化するコンピュータによりリーダブルなプログラム記憶装置において、前記方法ステップは次のステップを含む、すなわち、
変形可能な形状の測定値のセットを提供し、該測定値のセットは測定値行列を形成するステップと、
同時に剛体レジスタリング変換及び線形形状モデルについて解くステップとを含む、コンピュータによりリーダブルなプログラム記憶装置。
【請求項１６】
剛体レジスタリング変換及び線形形状モデルについて同時に解くステップは次のステップを含む、すなわち、
前記測定値のセットの平均を形成し、該平均を前記測定値のセットから減算するステップと、
前記測定値行列を提案されたスケーリングされた回転行列と提案された基底行列との積へと分解するステップと、
前記提案されたスケーリングされた回転行列及び前記提案された基底行列からアンビギュイティ変換の積行列を計算するステップと、
前記積行列を制約及び分解してアンビギュイティ変換行列を決定するステップと、
前記アンビギュイティ変換行列を使用して真のスケーリングされた回転行列及び真の基底行列を決定するステップと、
前記真のスケーリングされた回転行列及び前記真の基底行列からレジスタリングされた形状を構成するステップとを含む、請求項１５記載のコンピュータリーダブルプログラム記憶装置。
【請求項１７】
さらに前記測定値行列の階数及び該階数から基底数Ｋを決定することを含む、請求項１６記載のコンピュータリーダブルプログラム記憶装置。
【請求項１８】
測定値のセットはＮ個の測定値のセットからセレクトされたＫ個の測定値のサブセットであり、ここでＫ＜Ｎであり、さらに前記セレクトされたサブセットはＫ個の測定値の全ての可能なサブセットの最小条件数を有する、請求項１７記載のコンピュータリーダブルプログラム記憶装置。
【請求項１９】
測定値行列は特異値分解を使用して分解される、請求項１６記載のコンピュータリーダブルプログラム記憶装置。
【請求項２０】
アンビギュイティ変換行列は提案されたスケーリングされた回転行列に正規直交性制約を課することによって及び提案された基底行列に一意性制約を課することによって計算される、請求項１８記載のコンピュータリーダブルプログラム記憶装置。
【請求項２１】
アンビギュイティ変換行列は特異値分解を使用して分解される、請求項１６記載のコンピュータリーダブルプログラム記憶装置。
【請求項２２】
提案された基底行列に一意性制約を課することはさらに回転された基底セットとして最小条件数を有するＫ個の測定値をセレクトすること及び提案されたスケーリングされた回転行列に対するスケーリング係数を計算することを含む、請求項２０記載のコンピュータリーダブルプログラム記憶装置。
【請求項２３】
直交プロクラステス分析を使用してアンビギュイティ変換行列を共通座標系に変換するステップをさらに含む、請求項２１記載のコンピュータリーダブルプログラム記憶装置。
【図１】
【図２】
【図２】
【公表番号】特表２００８−５１１９３２（Ｐ２００８−５１１９３２Ａ）
【公表日】平成２０年４月１７日（２００８．４．１７）
【国際特許分類】
【出願番号】特願２００７−５３０３０６（Ｐ２００７−５３０３０６）
【出願日】平成１７年８月３１日（２００５．８．３１）
【国際出願番号】ＰＣＴ／ＵＳ２００５／０３０９５２
【国際公開番号】ＷＯ２００６／０２８８４１
【国際公開日】平成１８年３月１６日（２００６．３．１６）
【出願人】（５９３０６３１０５）シーメンス メディカル ソリューションズ ユーエスエー インコーポレイテッド (156)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｍｅｄｉｃａｌ Ｓｏｌｕｔｉｏｎｓ ＵＳＡ，Ｉｎｃ．
【住所又は居所原語表記】５１ Ｖａｌｌｅｙ Ｓｔｒｅａｍ Ｐａｒｋｗａｙ，Ｍａｌｖｅｒｎ，ＰＡ １９３５５−１４０６，Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公表日】平成２０年４月１７日（２００８．４．１７）
【国際特許分類】
【出願日】平成１７年８月３１日（２００５．８．３１）
【国際出願番号】ＰＣＴ／ＵＳ２００５／０３０９５２
【国際公開番号】ＷＯ２００６／０２８８４１
【国際公開日】平成１８年３月１６日（２００６．３．１６）
【出願人】（５９３０６３１０５）シーメンス メディカル ソリューションズ ユーエスエー インコーポレイテッド (156)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｍｅｄｉｃａｌ Ｓｏｌｕｔｉｏｎｓ ＵＳＡ，Ｉｎｃ．
【住所又は居所原語表記】５１ Ｖａｌｌｅｙ Ｓｔｒｅａｍ Ｐａｒｋｗａｙ，Ｍａｌｖｅｒｎ，ＰＡ １９３５５−１４０６，Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]