等周ツリーを使用する画像セグメンテーション
画像セグメンテーション方法において、ツリーは入力データから得られる（３１０）。ツリーを表現する行列のノーフィルオーダリングが生成される（３２０）。連立一次方程式が行列に関して解法され、解を取得する（３３０）。解は一群のセグメンテーションを定義するため使用される（３４０）。セグメンテーションは、セグメント特性のメトリックに基づいて一群のセグメンテーションから選択される（３５０）。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、２００４年９月２２日に出願され、発明の名称が「Ｉｓｏｐｅｒｉｍｅｔｒｉｃ Ｔｒｅｅｓ ｆｏｒ Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ」であり、その内容がそのまま参照によって本明細書に組み込まれる米国仮出願第６０／６１２，１０５号（代理人書類番号２００４Ｐ１６１７２ＵＳ）の優先権を主張する。
【０００２】
１．発明の分野
本発明は、画像セグメンテーションに係わり、特に、等周ツリーを使用する画像セグメンテーションの方法及びシステムに関する。
【０００３】
２．関連技術の説明
医療イメージングは、一般的に、治療成果を改善することを目標とした診断及び患者ケアのため重要であると認められている。近年、医療イメージングは、Ｘ線、コンピュータ断層撮影（ＣＴ）、磁気共鳴イメージング（ＭＲＩ）及び超音波のようなイメージング方式における進歩に起因して爆発的に成長している。これらの方式は、生体内の内部器官を観察するために非侵襲的な方法を提供するが、データの量は大量であり、２Ｄ画像として表現されるとき、一般的に、解釈のために解剖学者／放射線学の専門家を必要とする、残念ながら、このデータの人手による解釈の際に生じるコストは日常のデータ解析としては非常に高い。
【０００４】
２Ｄスライスは、３Ｄ体積モデルを生成するために組み合わされる。画像が長時間に亘って取得されると、４Ｄ（３Ｄ＋時間）解析が可能である。このデータの正確かつ便宜的な解釈を達成することは困難である。
【０００５】
画像セグメンテーションは、データセットからの関心のある解剖学的器官又は領域の自動又は半自動抽出を可能にすることにより、解剖学的データの診断及び解析のためのコンピュータベースの医療応用において重要な役割を果たす。たとえば、画像セグメンテーション方法は、脳マッピング研究において重要かつ困難な画像処理問題である、頭蓋ストリッピングとしても知られている、脳以外の組織からの脳組織の分離を可能にする。画像セグメンテーション方法は、心臓の形状及び運動の研究を可能にする。心臓疾患は心臓の形状と運動の局所変化と強い相関関係があると考えられるので、心臓のメカニクスの研究は重要である。
【０００６】
コンピュータビジョン文献において有名になった画像セグメンテーションにおけるグラフ分割の方法は、正規化カット（ｎｏｒｍａｌｉｚｅｄ ｃｕｔｓ）アルゴリズム、最大フロー／最小カット（ｍａｘ−ｆｌｏｗ／ｍｉｎ−ｃｕｔ）、及び、ランダムウォーク（ｒａｎｄｏｍ ｗａｌｋｅｒ）アルゴリズムを含む。Ｓｈｉ，Ｊ．ａｎｄ Ｍａｌｉｋ，Ｊ．，「Ｎｏｒｍａｌｉｚｅｄ ｃｕｔｓ ａｎｄ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ」，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２２（８）：８８８−９０５，２０００。Ｂｏｙｋｏｖ，Ｙ．ａｎｄ Ｊｏｌｌｙ，Ｍ．Ｐ．，「Ｉｎｔｅｒａｃｔｉｖｅ ｇｒａｐｈ ｃｕｔｓ ｆｏｒ ｏｐｔｉｍａｌ ｂｏｕｎｄａｒｙ ＆ ｒｅｇｉｏｎ ｓｅｇｍｅｎｔａｔｉｏｎ ｏｆ ｏｂｊｅｃｔｓ ｉｎ Ｎ−Ｄ ｉｍａｇｅｓ」，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，ｖｏｌｕｍｅ Ｉ，ｐａｇｅｓ １０５−１１２，Ｊｕｌｙ ２００１．Ｙｕは、異なる画像スケールに複数レベルグラフエンコーディングキューを構築し、全グラフレベルに亘って平均Ｎｃｕｔコストを最適化する。Ｙｕ，Ｓｔｅｌｌａ Ｘ．，「Ｓｅｇｍｅｎｔａｔｉｏｎ Ｕｓｉｎｇ Ｍｕｔｉｓｃａｌｅ Ｃｕｅｓ」，ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，１（１）：２４７−２５４，２００４。
【０００７】
Ｇｒａｄｙは、全自動画像セグメンテーションの方法として、等周グラフ分割アルゴリズムを導入した。Ｇｒａｄｙ，Ｌｅｏ，「Ｓｐａｃｅ−ｖａｒｉａｎｔ ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ：Ａ ｇｒａｐｈ−ｔｈｅｏｒｅｔｉｃ ａｐｐｒｏａｃｈ」，Ｐｈ．Ｄ．ｄｉｓｓｅｒｔａｔｉｏｎ，Ｂｏｓｔｏｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｏｓｔｏｎ，Ｍａｓｓａｃｈｕｓｅｔｔｓ，２００４。しかし、そのアルゴリズムは、周りのセグメンテーションの基礎となるフォアグラウンドポイントとして単一ノードの指定を可能にさせるので、このポイントはユーザによって選定され、半自動セグメンテーションアルゴリズムもたらす。等周アルゴリズムは、画像処理の状況では、各ノードがボクセルを表現し、エッジが６連結格子内の隣接するボクセルを接続するグラフ上で立てられる。
【発明の開示】
【０００８】
本発明の典型的な実施形態によれば、グラフ分割方法が提供される。この方法は、入力データからツリーを得るステップと、等周グラフ分割アルゴリズムを使用するためのセッティングとしてツリーを使用するステップとを含む。
【０００９】
本発明の典型的な実施形態によれば、画像セグメンテーション方法が提供される。この方法は、入力データからツリーを得るステップと、ツリーを表現する行列のノーフィルオーダリング（ｎｏ−ｆｉｌｌ ｏｒｄｅｒｉｎｇ）を生成するステップと、行列に関して連立一次方程式を解法し、解を取得するステップと、一群のセグメンテーションを定義するため解を使用するステップと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するステップとを含む。
【００１０】
本発明の典型的な実施形態によれば、医療画像セグメンテーション方法が提供される。この方法は、医療画像データセットからマスクを取得するステップと、マスク上の距離マップを計算するステップと、フォアグラウンドポイントを取得するステップと、画像の近傍構造に距離マップに応じた重みを伴う最大スパニングツリーを計算するステップと、最大スパニングツリーを表現するマスクのノーフィルオーダリングを生成するステップと、行列に関して連立一次方程式を解法するステップと、一群のセグメンテーションを定義するため解を使用するステップと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するステップとを含む。
【００１１】
本発明の典型的な実施形態によれば、画像セグメンテーションのためのコンピュータコードを含むコンピュータ読み取り可能な媒体が提供される。コンピュータ読み取り可能な媒体は、入力データからツリーを得るコンピュータコードと、ツリーを表現する行列のノーフィルオーダリングを生成するコンピュータコードと、行列に関して連立一次方程式を解法し、解を取得するコンピュータコードと、一群のセグメンテーションを定義するため解を使用するコンピュータコードと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するコンピュータコードとを備える。
【００１２】
本発明は、典型的な実施形態の説明が添付図面を参照して読まれるときに当業者により明白になる。
【発明を実施するための最良の形態】
【００１３】
以下では、本発明の典型的な実施形態が添付図面を参照して詳述される。
【００１４】
形式的に、ノードすなわち頂点ｖ∈Ｖ、かつ、エッジｅ∈Ｅ⊆Ｖ×Ｖとすると、グラフはペアＧ＝（Ｖ，Ｅ）である。２個の頂点ｖiとｖjを含むエッジｅは、ｅijによって表される。重み付きグラフは、各エッジに割り当てられた重みと呼ばれる（非負実数であると仮定された）値を有する。エッジｅijの重みは、ｗ（ｅij）又はｗijによって表され、隣接ボクセル間の強度又は親和性を表現する。
【００１５】
等周グラフ分割
グラフ分割のための等周アルゴリズムは等周比を
【数１】
として記述することによって開発され、ここで、ｒはすべて１からなるベクトルであり、ｘは集合Ｓ⊆Ｖ内のノードメンバーシップを示すベクトルを表現し、すなわち、
【数２】
である。ｎ×ｎ行列Ｌはグラフのラプラシアン行列であり、
【数３】
として定義され、ここで、ｄiは頂点ｖiの重み付き次数を表し、
【数４】
である。
Ｌｖiｖjという表記は、行列Ｌが頂点ｖi及びｖjによってインデックス付けされていることを示すため使用される。
【００１６】
これらの定義によって、式１中の比の分子は、Ｓと
【数５】
を含むエッジの重みの和を表現し、一方、分母はＳの基数（ｃａｒｄｉｎａｌｉｔｙ）を与える。ｘのバイナリ定義を緩和し、ｘに関して式１の分子を最小化することにより、基数制約｜Ｖ｜−ｘTｒ＝ｋを仮定すると、特異連立方程式が残される。特異性は、任意にあるノードｖgをＳに割り当てることにより解決され、非特異連立方程式である
Ｌ0ｘ0＝ｒ0 ［式５］
が得られ、ここで、添字はｖgに対応する行が除去されたことを示す（又は、行及び列、Ｌ0の場合。
【００１７】
式５に実数値の解が与えられるならば、最小等周定数をもつ分割を生成するスレッショルドを見つけることにより、この解をパーティションに変換することが可能であり、ｎ個のスレッショルドだけを試行することが必要とされる。この状況では、グラフの幾何学的性質（マスク）に関心があるので、式５の解において、ｗij＝１を取り扱う。
【００１８】
ツリー
本発明の典型的な実施形態において、標準的な格子エッジ集合はツリーで置き換えられる。ゼロフィルガウス消去法オーダリングは、連立一次方程式が、ｎと等しいストレージを用いて、二つのパスで解法できることを意味する。特に、オーダリングは、（重み付けされていない）１の次数をもつノード（すなわち、ツリー内のリーフノード）を消去し、ルートノードに到達するまで、続いて次数１を有するノードを再帰的に消去することにより線形時間内に見つけることができる。この場合は、都合の良いルートノードはグラウンドである。本発明の典型的な実施形態によるツリーのノーフィルオーダリングを生成する方法が下に示されている。
【００１９】
ツリーのノーフィルオーダリングを生成する方法
【数６】
【００２０】
上記のツリーのノーフィルオーダリングを生成する方法は、線形時間内にオーダリングを完成し、配列「ｔｒｅｅ」は、ノード毎に、１個の隣接ノードのインデックスを格納する（過剰表現されたエッジはない）。この表現が可能であるのは、ツリーがｎ−１本のエッジを有するからである（ルートは‘０’を格納する）。
【００２１】
図１は、本発明の典型的な実施形態による、ノード内部の番号によって与えられたオーダリングを伴う、ツリーのラプラシアン行列のガウス消去法を説明する。図１を参照すると、最上行はツリーの消去を示し、最下行は各消去ステップ後のツリーのラプラシアン行列を示す。
【００２２】
距離ツリー
前述のように、基礎的なグラフ構造として、すなわち、格子の代わりに、ツリーを使用することにより、式５の線形時間の解が取得される。
【００２３】
本発明の典型的な実施形態による、式５を解法する方法が下に示されている。
【００２４】
式５を解法する方法
【数７】
【００２５】
解が希望のカットを調べるような、ツリーの最も重要な特性は、フォアグラウンドポイントと、フォアグラウンドオブジェクト中の残りのボクセルとの間のツリー内のパスがバックグラウンド中のボクセルを通過しないこと、すなわち、フォアグラウンドがツリーと接続されていることである。この条件が満たされ、バックグラウンドもまたツリー内に接続されているならば、（ツリー中にループが存在し得ないので）フォアグラウンドとバックグラウンドは単一のエッジで接続される。
【００２６】
フォアグラウンドオブジェクトが接続され、各ノードからの距離マップ上の勾配上昇が同じ集合中のノードで安定し、異なるピークに安定するすべての近傍ノードに対する距離マップがツリーフォアグラウンド／バックグラウンド境界上で最大であるならば、上記の要件を満たすツリーを構築できる。格子中の各エッジに重み
Ｗij＝Ｄ（ｖi）＋Ｄ（ｖj） ［式６］
を割り当て、ここで、Ｄ（ｖi）はｖiにおける距離マップを示し、次に、最大スパニングツリーを計算する。以下では、式６によって重みが与えられた画像の最大スパニングツリーは、「距離ツリー」と称される。距離以外の関数が本発明を実施するため適合することが理解されるべきである。本発明を実施するため適合する関数には、グレースケール、グラジエント及び距離が含まれるが、これらに限定されない。
【００２７】
図２は、本発明の典型的な実施形態による、グラフ分割方法を明らかにするフローチャートである。図２を参照すると、ステップ２１０において、ツリーが入力データから得られる。好ましくは、ツリーは距離ツリーである。本開示の目的のため、「距離ツリー」は式６によって与えられた重みを伴う画像の最大スパニングツリーを参照する。代替的に、ツリーは関数ツリーであり、関数は、データ中で何が重要であるかを定義する所定の関数である。
【００２８】
ステップ２２０において、ツリーは、等周グラフ分割アルゴリズムを使用するためのセッティングとして使用される。本発明の一実施形態において、等周グラフ分割アルゴリズムを使用するためのセッティングとしてツリーを使用するステップは、ツリーを表現する行列のノーフィルオーダリングを生成するステップと、行列に関して連立一次方程式を解法し、解を取得するステップと、一群のセグメンテーションを定義するため解を使用するステップと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するステップとを備えている。
【００２９】
本発明の実施形態によるグラフ分割方法では、入力データは、（２Ｄ画像の場合には）ピクセル、又は、（３Ｄ画像の場合には）ボクセルの何れかを備え、セグメンテーションは、ピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される。たとえば、スレッショルド以下の解の値をもつピクセル又はボクセルはフォアグラウンドと関連付けられ、スレッショルドより大きい解の値をもつピクセル又はボクセルはバックグラウンドと関連付けられる。ｎ−１個のスレッショルドが存在し、ｎはピクセルの個数である。
【００３０】
本発明の少なくとも一実施形態によるグラフ分割方法では、ユーザ介入は必要とされない。好ましくは、セグメント特性のメトリックは、ノード集合の周囲長の、ノード集合の体積に対する比として定義された、等周比である。ノード集合の体積は、集合中のノードの重み付き次数の和と集合中のノードの個数とのうちの少なくとも一方に基づいて計算される。
【００３１】
図３は、本発明の典型的な実施形態による、画像セグメンテーション方法を明らかにするフローチャートである。図３を参照すると、ステップ３１０において、ツリーが入力データから得られる。好ましくは、ツリーは距離ツリーである。代替的に、ツリーは関数ツリーである。関数は、画像中で何が重要であるかを定義する所定の関数である。所定の関数には、グレースケール、グラジエント、及び／又は、距離が含まれるが、これらに限定されない。入力データは、（２Ｄ画像の場合には）ピクセル、又は、（３Ｄ画像の場合には）ボクセルの何れかを備える。本発明の一実施形態では、入力データは（たとえば、スレッショルド化から）予め選択されたボクセルのマスクである。本発明の一実施形態では、入力データからツリーを得るステップは、入力データからマスクを取得するステップと、マスク上で距離マップを計算するステップと、距離ツリーを計算するステップとを備える。
【００３２】
ステップ３２０において、ツリーを表現する行列のノーフィルオーダリングが生成される、ステップ３３０において、連立一次方程式が行列に関して解法され、解が取得される。
【００３３】
ステップ３４０において、解が一群のセグメンテーションを定義するため使用される。セグメンテーションは、ピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される。たとえば、スレッショルド以下の解の値をもつピクセル又はボクセルはフォアグラウンドと関連付けられ、スレッショルドより大きい解の値をもつピクセル又はボクセルはバックグラウンドと関連付けられる。一般に、ｎ−１個のスレッショルドが存在し、ｎはピクセルの個数である。
【００３４】
本発明の実施形態によれば、ステップ３５０において、セグメンテーションはセグメント特性のメトリックに基づいて一群のセグメンテーションから選択される。好ましくは、セグメント特性のメトリックは、ノード集合の周囲長の、ノード集合の体積に対する比として定義された、等周比である。ノード集合の体積は、集合中のノードの重み付き次数の和と集合中のノードの個数とのうちの少なくとも一方に基づいて計算される。
【００３５】
本発明の実施形態による画像セグメンテーション方法は、フォアグラウンドポイントを取得するステップをさらに備え、フォアグラウンドポイントを取得するステップは、フォアグラウンドポイントを自動的に取得するステップ、又は、フォアグラウンドポイントを双方向的に取得するステップの何れか一方を備える。本発明の少なくとも一実施形態による画像セグメンテーション方法において、ユーザ介入は必要とされない。
【００３６】
図４は、本発明の典型的な実施形態による、医療画像セグメンテーション方法を明らかにするフローチャートである。図４を参照すると、ステップ４０１においては、マスクが医療画像データセットから取得される。医療画像データセットは、３Ｄ医療データセット、２Ｄ医療データセット、又は、より高次元の医療データセットのうちの少なくとも一つを備える。
【００３７】
ステップ４２０において、距離マップがマスク上で計算される。ステップ４３０において、フォアグラウンドポイントが取得される。好ましくは、フォアグラウンドポイントは、問題に固有のフォアグラウンドポイントである。本発明の一実施形態では、問題に固有のフォアグラウンドポイントを取得するステップは、ユーザ指定フォアグラウンドポイントを取得するステップを備える。本発明の少なくとも一実施形態による医療画像セグメンテーション方法では、ユーザ介入は必要とされない。
【００３８】
ステップ４４０において、距離マップの関数である重みを伴う最大スパニングツリーが画像の近傍構造上で計算される。距離マップの関数は式６によって与えられる。本発明の少なくとも一実施形態において、近傍構造は格子である。画像は、（２Ｄ画像の場合には）ピクセル、又は、（３Ｄ画像の場合には）ボクセルの何れかを備える。
【００３９】
ステップ４５０において、最大スパニングツリーを表現する行列のノーフィルオーダリングが生成される。ステップ４６０において、連立一次方程式が行列に関して解法され、解を取得する。
【００４０】
ステップ４７０において、解が一群のセグメンテーションを定義するため使用される。セグメンテーションは、ピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される。たとえば、スレッショルド以下の解の値をもつピクセル又はボクセルはフォアグラウンドと関連付けられ、スレッショルドより大きい解の値をもつピクセル又はボクセルはバックグラウンドと関連付けられる。一般に、ｎ−１個のスレッショルドが存在し、ｎはピクセルの個数である。
【００４１】
ステップ４８０において、セグメンテーションはセグメント特性のメトリックに基づいて一群のセグメンテーションから選択される。好ましくは、セグメント特性のメトリックは、ノード集合の周囲長の、ノード集合の体積に対する比として定義された、等周比である。ノード集合の体積は、集合中のノードの重み付き次数の和と集合中のノードの個数とのうちの少なくとも一方に基づいて計算される。
【００４２】
本発明は、種々の形式のハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、又は、それらの組み合わせで実施可能なことが理解されるべきである。一実施形態では、本発明は、プログラム記憶装置に明白に具現化されたアプリケーションプログラムとしてソフトウェアで実施され得る。アプリケーションプログラムは、適当なアーキテクチャを備える機械へアップロードされ、機械によって実行され得る。
【００４３】
図５を参照すると、本開示の実施形態によれば、画像セグメンテーション方法を実施するコンピュータシステム１０１は、特に、中央処理ユニット（ＣＰＵ）１０９と、メモリ１０３と、入力／出力（入出力）インターフェイス１０４とを備える。コンピュータシステム１０１は、一般に、入出力インターフェイス１０４を経由して、ディスプレイ１０５と、マウス及びキーボードのような様々な入力装置１０６とに接続される。サポート回路には、キャッシュ、電源、クロック回路、及び、通信バスのような回路が含まれる。メモリ１０３は、ランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）、ディスクドライブ、テープドライブなど、又は、それらの組み合わせが含まれる。本発明は、メモリ１０３に記憶され、信号源１０８からの信号を処理するためＣＰＵ１０９によって実行されるルーチン１０７としても実施され得る。このように、コンピュータシステム１０１は、本発明のルーチン１０７を実行するときに専用コンピュータシステムになる汎用コンピュータシステムである。
【００４４】
コンピュータプラットフォーム１０１は、オペレーティングシステムとマイクロ命令コードとをさらに含む。明細書に記載されている種々のプロセス及び機能は、オペレーティングシステムを介して実行されるマイクロ命令コードの一部又はアプリケーションプログラムの一部のどちらか（又は、それらの組み合わせ）であってよい。その上、付加的なデータ記憶装置及び印刷装置のような種々のその他の周辺装置がコンピュータプラットフォームに接続されていてもよい。
【００４５】
添付図面に示された構成システムコンポーネントの一部及び方法ステップの一部はソフトウェアで実施されてもよく、システムコンポーネント（又はプロセスステップ）間の実際の接続は本発明がプログラムされた態様に応じて異なり得ることがさらに理解されるべきである。明細書に記載された本発明の教示が与えられるならば、当業者は本発明の上記の実施又は構成と類似した実施又は構成を考えることが可能であろう。
【００４６】
以下では、本発明の典型的な実施形態による、画像セグメンテーションのためのコンピュータコードを含むコンピュータ読み取り可能な媒体が説明される。コンピュータ読み取り可能な媒体は、入力データからツリーを得るコンピュータコードと、ツリーを表現する行列のノンフィルオーダリングを生成するコンピュータコードと、行列に関して連立一次方程式を解法し、解を得るコンピュータコードと、一群のセグメンテーションを定義するため解を使用するコンピュータコードと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するコンピュータコードとを備える。
【００４７】
好ましくは、ツリーは距離ツリーである。代替的に、ツリーは関数ツリーである。関数は、画像中で何が重要であるかを定義する所定の関数である。所定の関数には、グレースケール、グラジエント、及び／又は、距離が含まれるが、これらに限定されない。入力データは、（２Ｄ画像の場合には）ピクセル、又は、（３Ｄ画像の場合には）ボクセルの何れかを備える。本発明の一実施形態では、入力データは（たとえば、スレッショルド化から）予め選択されたボクセルのマスクである。本発明の一実施形態では、入力データからツリーを得るステップは、入力データからマスクを取得するステップと、マスク上で距離マップを計算するステップと、距離ツリーを計算するステップとを備える。
【００４８】
本発明の典型的な実施形態では、セグメント特性のメトリックは、ノード集合の周囲長の、ノード集合の体積に対する比として定義された、等周比である。ノード集合の体積は、集合中のノードの重み付き次数の和と集合中のノードの個数とのうちの少なくとも一方に基づいて計算される。
【００４９】
本発明の実施形態による、画像セグメンテーションのためのコンピュータコードを含むコンピュータ読み取り可能な媒体は、フォアグラウンドポイントを取得するコンピュータコードをさらに備える。たとえば、フォアグラウンドポイントを自動的に取得するコンピュータコード、又は、フォアグラウンドポイントを双方向的に取得するコンピュータコードである。
【００５０】
本発明のプロセス及び装置は実例のための添付図面を参照して詳述されているが、発明のプロセス及び装置はそれらによって制限されると解釈されるべきでないことが理解されるべきである。前述の典型的な実施形態に対する種々の変形が特許請求の範囲に記載された発明の精神及び範囲から逸脱することなく行われ得ることは当業者に容易に明らかになる。
【図面の簡単な説明】
【００５１】
【図１】本発明の典型的な実施形態による、ノード内部の番号によって与えられたオーダリングを伴うツリーのラプラシアン行列のガウス消去法を説明する図である。
【図２】本発明の典型的な実施形態による、グラフ分割方法を明らかにするフローチャートである。
【図３】本発明の典型的な実施形態による、画像セグメンテーション方法を明らかにするフローチャートである。
【図４】本発明の典型的な実施形態による、医療画像セグメンテーション方法を明らかにするフローチャートである。
【図５】本発明の典型的な実施形態による、画像セグメンテーション方法を実施するコンピュータシステムを示す図である。
【技術分野】
【０００１】
関連出願の相互参照
本出願は、２００４年９月２２日に出願され、発明の名称が「Ｉｓｏｐｅｒｉｍｅｔｒｉｃ Ｔｒｅｅｓ ｆｏｒ Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ」であり、その内容がそのまま参照によって本明細書に組み込まれる米国仮出願第６０／６１２，１０５号（代理人書類番号２００４Ｐ１６１７２ＵＳ）の優先権を主張する。
【０００２】
１．発明の分野
本発明は、画像セグメンテーションに係わり、特に、等周ツリーを使用する画像セグメンテーションの方法及びシステムに関する。
【０００３】
２．関連技術の説明
医療イメージングは、一般的に、治療成果を改善することを目標とした診断及び患者ケアのため重要であると認められている。近年、医療イメージングは、Ｘ線、コンピュータ断層撮影（ＣＴ）、磁気共鳴イメージング（ＭＲＩ）及び超音波のようなイメージング方式における進歩に起因して爆発的に成長している。これらの方式は、生体内の内部器官を観察するために非侵襲的な方法を提供するが、データの量は大量であり、２Ｄ画像として表現されるとき、一般的に、解釈のために解剖学者／放射線学の専門家を必要とする、残念ながら、このデータの人手による解釈の際に生じるコストは日常のデータ解析としては非常に高い。
【０００４】
２Ｄスライスは、３Ｄ体積モデルを生成するために組み合わされる。画像が長時間に亘って取得されると、４Ｄ（３Ｄ＋時間）解析が可能である。このデータの正確かつ便宜的な解釈を達成することは困難である。
【０００５】
画像セグメンテーションは、データセットからの関心のある解剖学的器官又は領域の自動又は半自動抽出を可能にすることにより、解剖学的データの診断及び解析のためのコンピュータベースの医療応用において重要な役割を果たす。たとえば、画像セグメンテーション方法は、脳マッピング研究において重要かつ困難な画像処理問題である、頭蓋ストリッピングとしても知られている、脳以外の組織からの脳組織の分離を可能にする。画像セグメンテーション方法は、心臓の形状及び運動の研究を可能にする。心臓疾患は心臓の形状と運動の局所変化と強い相関関係があると考えられるので、心臓のメカニクスの研究は重要である。
【０００６】
コンピュータビジョン文献において有名になった画像セグメンテーションにおけるグラフ分割の方法は、正規化カット（ｎｏｒｍａｌｉｚｅｄ ｃｕｔｓ）アルゴリズム、最大フロー／最小カット（ｍａｘ−ｆｌｏｗ／ｍｉｎ−ｃｕｔ）、及び、ランダムウォーク（ｒａｎｄｏｍ ｗａｌｋｅｒ）アルゴリズムを含む。Ｓｈｉ，Ｊ．ａｎｄ Ｍａｌｉｋ，Ｊ．，「Ｎｏｒｍａｌｉｚｅｄ ｃｕｔｓ ａｎｄ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ」，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２２（８）：８８８−９０５，２０００。Ｂｏｙｋｏｖ，Ｙ．ａｎｄ Ｊｏｌｌｙ，Ｍ．Ｐ．，「Ｉｎｔｅｒａｃｔｉｖｅ ｇｒａｐｈ ｃｕｔｓ ｆｏｒ ｏｐｔｉｍａｌ ｂｏｕｎｄａｒｙ ＆ ｒｅｇｉｏｎ ｓｅｇｍｅｎｔａｔｉｏｎ ｏｆ ｏｂｊｅｃｔｓ ｉｎ Ｎ−Ｄ ｉｍａｇｅｓ」，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，ｖｏｌｕｍｅ Ｉ，ｐａｇｅｓ １０５−１１２，Ｊｕｌｙ ２００１．Ｙｕは、異なる画像スケールに複数レベルグラフエンコーディングキューを構築し、全グラフレベルに亘って平均Ｎｃｕｔコストを最適化する。Ｙｕ，Ｓｔｅｌｌａ Ｘ．，「Ｓｅｇｍｅｎｔａｔｉｏｎ Ｕｓｉｎｇ Ｍｕｔｉｓｃａｌｅ Ｃｕｅｓ」，ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，１（１）：２４７−２５４，２００４。
【０００７】
Ｇｒａｄｙは、全自動画像セグメンテーションの方法として、等周グラフ分割アルゴリズムを導入した。Ｇｒａｄｙ，Ｌｅｏ，「Ｓｐａｃｅ−ｖａｒｉａｎｔ ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ：Ａ ｇｒａｐｈ−ｔｈｅｏｒｅｔｉｃ ａｐｐｒｏａｃｈ」，Ｐｈ．Ｄ．ｄｉｓｓｅｒｔａｔｉｏｎ，Ｂｏｓｔｏｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｏｓｔｏｎ，Ｍａｓｓａｃｈｕｓｅｔｔｓ，２００４。しかし、そのアルゴリズムは、周りのセグメンテーションの基礎となるフォアグラウンドポイントとして単一ノードの指定を可能にさせるので、このポイントはユーザによって選定され、半自動セグメンテーションアルゴリズムもたらす。等周アルゴリズムは、画像処理の状況では、各ノードがボクセルを表現し、エッジが６連結格子内の隣接するボクセルを接続するグラフ上で立てられる。
【発明の開示】
【０００８】
本発明の典型的な実施形態によれば、グラフ分割方法が提供される。この方法は、入力データからツリーを得るステップと、等周グラフ分割アルゴリズムを使用するためのセッティングとしてツリーを使用するステップとを含む。
【０００９】
本発明の典型的な実施形態によれば、画像セグメンテーション方法が提供される。この方法は、入力データからツリーを得るステップと、ツリーを表現する行列のノーフィルオーダリング（ｎｏ−ｆｉｌｌ ｏｒｄｅｒｉｎｇ）を生成するステップと、行列に関して連立一次方程式を解法し、解を取得するステップと、一群のセグメンテーションを定義するため解を使用するステップと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するステップとを含む。
【００１０】
本発明の典型的な実施形態によれば、医療画像セグメンテーション方法が提供される。この方法は、医療画像データセットからマスクを取得するステップと、マスク上の距離マップを計算するステップと、フォアグラウンドポイントを取得するステップと、画像の近傍構造に距離マップに応じた重みを伴う最大スパニングツリーを計算するステップと、最大スパニングツリーを表現するマスクのノーフィルオーダリングを生成するステップと、行列に関して連立一次方程式を解法するステップと、一群のセグメンテーションを定義するため解を使用するステップと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するステップとを含む。
【００１１】
本発明の典型的な実施形態によれば、画像セグメンテーションのためのコンピュータコードを含むコンピュータ読み取り可能な媒体が提供される。コンピュータ読み取り可能な媒体は、入力データからツリーを得るコンピュータコードと、ツリーを表現する行列のノーフィルオーダリングを生成するコンピュータコードと、行列に関して連立一次方程式を解法し、解を取得するコンピュータコードと、一群のセグメンテーションを定義するため解を使用するコンピュータコードと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するコンピュータコードとを備える。
【００１２】
本発明は、典型的な実施形態の説明が添付図面を参照して読まれるときに当業者により明白になる。
【発明を実施するための最良の形態】
【００１３】
以下では、本発明の典型的な実施形態が添付図面を参照して詳述される。
【００１４】
形式的に、ノードすなわち頂点ｖ∈Ｖ、かつ、エッジｅ∈Ｅ⊆Ｖ×Ｖとすると、グラフはペアＧ＝（Ｖ，Ｅ）である。２個の頂点ｖiとｖjを含むエッジｅは、ｅijによって表される。重み付きグラフは、各エッジに割り当てられた重みと呼ばれる（非負実数であると仮定された）値を有する。エッジｅijの重みは、ｗ（ｅij）又はｗijによって表され、隣接ボクセル間の強度又は親和性を表現する。
【００１５】
等周グラフ分割
グラフ分割のための等周アルゴリズムは等周比を
【数１】
として記述することによって開発され、ここで、ｒはすべて１からなるベクトルであり、ｘは集合Ｓ⊆Ｖ内のノードメンバーシップを示すベクトルを表現し、すなわち、
【数２】
である。ｎ×ｎ行列Ｌはグラフのラプラシアン行列であり、
【数３】
として定義され、ここで、ｄiは頂点ｖiの重み付き次数を表し、
【数４】
である。
Ｌｖiｖjという表記は、行列Ｌが頂点ｖi及びｖjによってインデックス付けされていることを示すため使用される。
【００１６】
これらの定義によって、式１中の比の分子は、Ｓと
【数５】
を含むエッジの重みの和を表現し、一方、分母はＳの基数（ｃａｒｄｉｎａｌｉｔｙ）を与える。ｘのバイナリ定義を緩和し、ｘに関して式１の分子を最小化することにより、基数制約｜Ｖ｜−ｘTｒ＝ｋを仮定すると、特異連立方程式が残される。特異性は、任意にあるノードｖgをＳに割り当てることにより解決され、非特異連立方程式である
Ｌ0ｘ0＝ｒ0 ［式５］
が得られ、ここで、添字はｖgに対応する行が除去されたことを示す（又は、行及び列、Ｌ0の場合。
【００１７】
式５に実数値の解が与えられるならば、最小等周定数をもつ分割を生成するスレッショルドを見つけることにより、この解をパーティションに変換することが可能であり、ｎ個のスレッショルドだけを試行することが必要とされる。この状況では、グラフの幾何学的性質（マスク）に関心があるので、式５の解において、ｗij＝１を取り扱う。
【００１８】
ツリー
本発明の典型的な実施形態において、標準的な格子エッジ集合はツリーで置き換えられる。ゼロフィルガウス消去法オーダリングは、連立一次方程式が、ｎと等しいストレージを用いて、二つのパスで解法できることを意味する。特に、オーダリングは、（重み付けされていない）１の次数をもつノード（すなわち、ツリー内のリーフノード）を消去し、ルートノードに到達するまで、続いて次数１を有するノードを再帰的に消去することにより線形時間内に見つけることができる。この場合は、都合の良いルートノードはグラウンドである。本発明の典型的な実施形態によるツリーのノーフィルオーダリングを生成する方法が下に示されている。
【００１９】
ツリーのノーフィルオーダリングを生成する方法
【数６】
【００２０】
上記のツリーのノーフィルオーダリングを生成する方法は、線形時間内にオーダリングを完成し、配列「ｔｒｅｅ」は、ノード毎に、１個の隣接ノードのインデックスを格納する（過剰表現されたエッジはない）。この表現が可能であるのは、ツリーがｎ−１本のエッジを有するからである（ルートは‘０’を格納する）。
【００２１】
図１は、本発明の典型的な実施形態による、ノード内部の番号によって与えられたオーダリングを伴う、ツリーのラプラシアン行列のガウス消去法を説明する。図１を参照すると、最上行はツリーの消去を示し、最下行は各消去ステップ後のツリーのラプラシアン行列を示す。
【００２２】
距離ツリー
前述のように、基礎的なグラフ構造として、すなわち、格子の代わりに、ツリーを使用することにより、式５の線形時間の解が取得される。
【００２３】
本発明の典型的な実施形態による、式５を解法する方法が下に示されている。
【００２４】
式５を解法する方法
【数７】
【００２５】
解が希望のカットを調べるような、ツリーの最も重要な特性は、フォアグラウンドポイントと、フォアグラウンドオブジェクト中の残りのボクセルとの間のツリー内のパスがバックグラウンド中のボクセルを通過しないこと、すなわち、フォアグラウンドがツリーと接続されていることである。この条件が満たされ、バックグラウンドもまたツリー内に接続されているならば、（ツリー中にループが存在し得ないので）フォアグラウンドとバックグラウンドは単一のエッジで接続される。
【００２６】
フォアグラウンドオブジェクトが接続され、各ノードからの距離マップ上の勾配上昇が同じ集合中のノードで安定し、異なるピークに安定するすべての近傍ノードに対する距離マップがツリーフォアグラウンド／バックグラウンド境界上で最大であるならば、上記の要件を満たすツリーを構築できる。格子中の各エッジに重み
Ｗij＝Ｄ（ｖi）＋Ｄ（ｖj） ［式６］
を割り当て、ここで、Ｄ（ｖi）はｖiにおける距離マップを示し、次に、最大スパニングツリーを計算する。以下では、式６によって重みが与えられた画像の最大スパニングツリーは、「距離ツリー」と称される。距離以外の関数が本発明を実施するため適合することが理解されるべきである。本発明を実施するため適合する関数には、グレースケール、グラジエント及び距離が含まれるが、これらに限定されない。
【００２７】
図２は、本発明の典型的な実施形態による、グラフ分割方法を明らかにするフローチャートである。図２を参照すると、ステップ２１０において、ツリーが入力データから得られる。好ましくは、ツリーは距離ツリーである。本開示の目的のため、「距離ツリー」は式６によって与えられた重みを伴う画像の最大スパニングツリーを参照する。代替的に、ツリーは関数ツリーであり、関数は、データ中で何が重要であるかを定義する所定の関数である。
【００２８】
ステップ２２０において、ツリーは、等周グラフ分割アルゴリズムを使用するためのセッティングとして使用される。本発明の一実施形態において、等周グラフ分割アルゴリズムを使用するためのセッティングとしてツリーを使用するステップは、ツリーを表現する行列のノーフィルオーダリングを生成するステップと、行列に関して連立一次方程式を解法し、解を取得するステップと、一群のセグメンテーションを定義するため解を使用するステップと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するステップとを備えている。
【００２９】
本発明の実施形態によるグラフ分割方法では、入力データは、（２Ｄ画像の場合には）ピクセル、又は、（３Ｄ画像の場合には）ボクセルの何れかを備え、セグメンテーションは、ピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される。たとえば、スレッショルド以下の解の値をもつピクセル又はボクセルはフォアグラウンドと関連付けられ、スレッショルドより大きい解の値をもつピクセル又はボクセルはバックグラウンドと関連付けられる。ｎ−１個のスレッショルドが存在し、ｎはピクセルの個数である。
【００３０】
本発明の少なくとも一実施形態によるグラフ分割方法では、ユーザ介入は必要とされない。好ましくは、セグメント特性のメトリックは、ノード集合の周囲長の、ノード集合の体積に対する比として定義された、等周比である。ノード集合の体積は、集合中のノードの重み付き次数の和と集合中のノードの個数とのうちの少なくとも一方に基づいて計算される。
【００３１】
図３は、本発明の典型的な実施形態による、画像セグメンテーション方法を明らかにするフローチャートである。図３を参照すると、ステップ３１０において、ツリーが入力データから得られる。好ましくは、ツリーは距離ツリーである。代替的に、ツリーは関数ツリーである。関数は、画像中で何が重要であるかを定義する所定の関数である。所定の関数には、グレースケール、グラジエント、及び／又は、距離が含まれるが、これらに限定されない。入力データは、（２Ｄ画像の場合には）ピクセル、又は、（３Ｄ画像の場合には）ボクセルの何れかを備える。本発明の一実施形態では、入力データは（たとえば、スレッショルド化から）予め選択されたボクセルのマスクである。本発明の一実施形態では、入力データからツリーを得るステップは、入力データからマスクを取得するステップと、マスク上で距離マップを計算するステップと、距離ツリーを計算するステップとを備える。
【００３２】
ステップ３２０において、ツリーを表現する行列のノーフィルオーダリングが生成される、ステップ３３０において、連立一次方程式が行列に関して解法され、解が取得される。
【００３３】
ステップ３４０において、解が一群のセグメンテーションを定義するため使用される。セグメンテーションは、ピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される。たとえば、スレッショルド以下の解の値をもつピクセル又はボクセルはフォアグラウンドと関連付けられ、スレッショルドより大きい解の値をもつピクセル又はボクセルはバックグラウンドと関連付けられる。一般に、ｎ−１個のスレッショルドが存在し、ｎはピクセルの個数である。
【００３４】
本発明の実施形態によれば、ステップ３５０において、セグメンテーションはセグメント特性のメトリックに基づいて一群のセグメンテーションから選択される。好ましくは、セグメント特性のメトリックは、ノード集合の周囲長の、ノード集合の体積に対する比として定義された、等周比である。ノード集合の体積は、集合中のノードの重み付き次数の和と集合中のノードの個数とのうちの少なくとも一方に基づいて計算される。
【００３５】
本発明の実施形態による画像セグメンテーション方法は、フォアグラウンドポイントを取得するステップをさらに備え、フォアグラウンドポイントを取得するステップは、フォアグラウンドポイントを自動的に取得するステップ、又は、フォアグラウンドポイントを双方向的に取得するステップの何れか一方を備える。本発明の少なくとも一実施形態による画像セグメンテーション方法において、ユーザ介入は必要とされない。
【００３６】
図４は、本発明の典型的な実施形態による、医療画像セグメンテーション方法を明らかにするフローチャートである。図４を参照すると、ステップ４０１においては、マスクが医療画像データセットから取得される。医療画像データセットは、３Ｄ医療データセット、２Ｄ医療データセット、又は、より高次元の医療データセットのうちの少なくとも一つを備える。
【００３７】
ステップ４２０において、距離マップがマスク上で計算される。ステップ４３０において、フォアグラウンドポイントが取得される。好ましくは、フォアグラウンドポイントは、問題に固有のフォアグラウンドポイントである。本発明の一実施形態では、問題に固有のフォアグラウンドポイントを取得するステップは、ユーザ指定フォアグラウンドポイントを取得するステップを備える。本発明の少なくとも一実施形態による医療画像セグメンテーション方法では、ユーザ介入は必要とされない。
【００３８】
ステップ４４０において、距離マップの関数である重みを伴う最大スパニングツリーが画像の近傍構造上で計算される。距離マップの関数は式６によって与えられる。本発明の少なくとも一実施形態において、近傍構造は格子である。画像は、（２Ｄ画像の場合には）ピクセル、又は、（３Ｄ画像の場合には）ボクセルの何れかを備える。
【００３９】
ステップ４５０において、最大スパニングツリーを表現する行列のノーフィルオーダリングが生成される。ステップ４６０において、連立一次方程式が行列に関して解法され、解を取得する。
【００４０】
ステップ４７０において、解が一群のセグメンテーションを定義するため使用される。セグメンテーションは、ピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される。たとえば、スレッショルド以下の解の値をもつピクセル又はボクセルはフォアグラウンドと関連付けられ、スレッショルドより大きい解の値をもつピクセル又はボクセルはバックグラウンドと関連付けられる。一般に、ｎ−１個のスレッショルドが存在し、ｎはピクセルの個数である。
【００４１】
ステップ４８０において、セグメンテーションはセグメント特性のメトリックに基づいて一群のセグメンテーションから選択される。好ましくは、セグメント特性のメトリックは、ノード集合の周囲長の、ノード集合の体積に対する比として定義された、等周比である。ノード集合の体積は、集合中のノードの重み付き次数の和と集合中のノードの個数とのうちの少なくとも一方に基づいて計算される。
【００４２】
本発明は、種々の形式のハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、又は、それらの組み合わせで実施可能なことが理解されるべきである。一実施形態では、本発明は、プログラム記憶装置に明白に具現化されたアプリケーションプログラムとしてソフトウェアで実施され得る。アプリケーションプログラムは、適当なアーキテクチャを備える機械へアップロードされ、機械によって実行され得る。
【００４３】
図５を参照すると、本開示の実施形態によれば、画像セグメンテーション方法を実施するコンピュータシステム１０１は、特に、中央処理ユニット（ＣＰＵ）１０９と、メモリ１０３と、入力／出力（入出力）インターフェイス１０４とを備える。コンピュータシステム１０１は、一般に、入出力インターフェイス１０４を経由して、ディスプレイ１０５と、マウス及びキーボードのような様々な入力装置１０６とに接続される。サポート回路には、キャッシュ、電源、クロック回路、及び、通信バスのような回路が含まれる。メモリ１０３は、ランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）、ディスクドライブ、テープドライブなど、又は、それらの組み合わせが含まれる。本発明は、メモリ１０３に記憶され、信号源１０８からの信号を処理するためＣＰＵ１０９によって実行されるルーチン１０７としても実施され得る。このように、コンピュータシステム１０１は、本発明のルーチン１０７を実行するときに専用コンピュータシステムになる汎用コンピュータシステムである。
【００４４】
コンピュータプラットフォーム１０１は、オペレーティングシステムとマイクロ命令コードとをさらに含む。明細書に記載されている種々のプロセス及び機能は、オペレーティングシステムを介して実行されるマイクロ命令コードの一部又はアプリケーションプログラムの一部のどちらか（又は、それらの組み合わせ）であってよい。その上、付加的なデータ記憶装置及び印刷装置のような種々のその他の周辺装置がコンピュータプラットフォームに接続されていてもよい。
【００４５】
添付図面に示された構成システムコンポーネントの一部及び方法ステップの一部はソフトウェアで実施されてもよく、システムコンポーネント（又はプロセスステップ）間の実際の接続は本発明がプログラムされた態様に応じて異なり得ることがさらに理解されるべきである。明細書に記載された本発明の教示が与えられるならば、当業者は本発明の上記の実施又は構成と類似した実施又は構成を考えることが可能であろう。
【００４６】
以下では、本発明の典型的な実施形態による、画像セグメンテーションのためのコンピュータコードを含むコンピュータ読み取り可能な媒体が説明される。コンピュータ読み取り可能な媒体は、入力データからツリーを得るコンピュータコードと、ツリーを表現する行列のノンフィルオーダリングを生成するコンピュータコードと、行列に関して連立一次方程式を解法し、解を得るコンピュータコードと、一群のセグメンテーションを定義するため解を使用するコンピュータコードと、セグメント特性のメトリックに基づいて一群のセグメンテーションからセグメンテーションを選択するコンピュータコードとを備える。
【００４７】
好ましくは、ツリーは距離ツリーである。代替的に、ツリーは関数ツリーである。関数は、画像中で何が重要であるかを定義する所定の関数である。所定の関数には、グレースケール、グラジエント、及び／又は、距離が含まれるが、これらに限定されない。入力データは、（２Ｄ画像の場合には）ピクセル、又は、（３Ｄ画像の場合には）ボクセルの何れかを備える。本発明の一実施形態では、入力データは（たとえば、スレッショルド化から）予め選択されたボクセルのマスクである。本発明の一実施形態では、入力データからツリーを得るステップは、入力データからマスクを取得するステップと、マスク上で距離マップを計算するステップと、距離ツリーを計算するステップとを備える。
【００４８】
本発明の典型的な実施形態では、セグメント特性のメトリックは、ノード集合の周囲長の、ノード集合の体積に対する比として定義された、等周比である。ノード集合の体積は、集合中のノードの重み付き次数の和と集合中のノードの個数とのうちの少なくとも一方に基づいて計算される。
【００４９】
本発明の実施形態による、画像セグメンテーションのためのコンピュータコードを含むコンピュータ読み取り可能な媒体は、フォアグラウンドポイントを取得するコンピュータコードをさらに備える。たとえば、フォアグラウンドポイントを自動的に取得するコンピュータコード、又は、フォアグラウンドポイントを双方向的に取得するコンピュータコードである。
【００５０】
本発明のプロセス及び装置は実例のための添付図面を参照して詳述されているが、発明のプロセス及び装置はそれらによって制限されると解釈されるべきでないことが理解されるべきである。前述の典型的な実施形態に対する種々の変形が特許請求の範囲に記載された発明の精神及び範囲から逸脱することなく行われ得ることは当業者に容易に明らかになる。
【図面の簡単な説明】
【００５１】
【図１】本発明の典型的な実施形態による、ノード内部の番号によって与えられたオーダリングを伴うツリーのラプラシアン行列のガウス消去法を説明する図である。
【図２】本発明の典型的な実施形態による、グラフ分割方法を明らかにするフローチャートである。
【図３】本発明の典型的な実施形態による、画像セグメンテーション方法を明らかにするフローチャートである。
【図４】本発明の典型的な実施形態による、医療画像セグメンテーション方法を明らかにするフローチャートである。
【図５】本発明の典型的な実施形態による、画像セグメンテーション方法を実施するコンピュータシステムを示す図である。
【特許請求の範囲】
【請求項１】
入力データからツリーを得るステップと、
等周グラフ分割アルゴリズムを使用するためのセッティングとして前記ツリーを使用するステップと、
を備える、グラフ分割方法。
【請求項２】
前記ツリーが距離ツリーである、請求項１に記載の方法。
【請求項３】
前記ツリーが関数ツリーである、請求項１に記載の方法。
【請求項４】
前記関数がデータ中で何が重要であるかを定義する所定の関数である、請求項３に記載の方法。
【請求項５】
等周グラフ分割アルゴリズムを使用するためのセッティングとして前記ツリーを使用するステップが、
前記ツリーを表現する行列のノーフィルオーダリングを生成するステップと、
前記行列に関して連立一次方程式を解法し、解を取得するステップと、
一群のセグメンテーションを定義するため前記解を使用するステップと、
セグメント特性のメトリックに基づいて前記一群のセグメンテーションからセグメンテーションを選択するステップと、
を備える、請求項１に記載の方法。
【請求項６】
入力データからツリーを得るステップと、
前記ツリーを表現する行列のノーフィルオーダリングを生成するステップと、
前記行列に関して連立一次方程式を解法し、解を取得するステップと、
一群のセグメンテーションを定義するため前記解を使用するステップと、
セグメント特性のメトリックに基づいて前記一群のセグメンテーションからセグメンテーションを選択するステップと、
を備える画像セグメンテーション方法。
【請求項７】
前記入力データがピクセル又はボクセルの何れかを備え、
セグメンテーションが前記ピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される、
請求項６に記載の方法。
【請求項８】
スレッショルド以下の解の値を伴うピクセルが前記フォアグラウンドと関連付けられ、前記スレッショルドより大きな解の値を伴うピクセルが前記バックグラウンドと関連付けられる、請求項７に記載の方法。
【請求項９】
ｎ−１個のスレッショルドが存在し、ｎがピクセルの個数である、請求項８に記載の方法。
【請求項１０】
前記セグメント特性のメトリックが、ノード集合の周囲長の、前記ノード集合の体積に対する比として定義された、等周比である、請求項６に記載の方法。
【請求項１１】
前記ノード集合の体積が前記集合中のノードの重み付き次数の和と前記集合中のノードの個数とのうちの少なくとも一方に基づいて計算される、請求項１０に記載の方法。
【請求項１２】
フォアグラウンドポイントを取得するステップをさらに備え、
前記フォアグラウンドポイントを取得するステップが、フォアグラウンドポイントを自動的に取得するステップ、又は、フォアグラウンドポイントを双方向的に取得するステップのうちの何れか一方を備える、請求項６に記載の方法。
【請求項１３】
前記ツリーが距離ツリーである、請求項６に記載の方法。
【請求項１４】
前記ツリーが関数ツリーである、請求項６に記載の方法。
【請求項１５】
前記関数が画像中で何が重要であるかを定義する所定の関数である、請求項１４に記載の方法。
【請求項１６】
前記所定の関数がグレースケール、グラジエント、又は、距離のうちの少なくとも一つである、請求項１５に記載の方法。
【請求項１７】
前記入力データが予め選択されたボクセルのマスクである、請求項６に記載の方法。
【請求項１８】
前記入力データからツリーを得るステップが、
前記入力データからマスクを取得するステップと、
前記マスク上で距離マップを計算するステップと、
距離ツリーを計算するステップと、
を備える、請求項６に記載の方法。
【請求項１９】
ユーザ介入が必要とされない、請求項６に記載の方法。
【請求項２０】
医療画像データセットからマスクを取得するステップと、
前記マスク上で距離マップを計算するステップと、
フォアグラウンドポイントを取得するステップと、
画像の近傍構造上で前記距離マップの関数である重みを伴う最大スパニングツリーを計算するステップと、
前記最大スパニングツリーを表現する行列のノーフィルオーダリングを生成するステップと、
前記行列に関して連立一次方程式を解法し、解を取得するステップと、
一群のセグメンテーションを定義するため前記解を使用するステップと、
セグメント特性のメトリックに基づいて前記一群のセグメンテーションからセグメンテーションを選択するステップと、
を備える医療画像セグメンテーション方法。
【請求項２１】
前記画像がピクセル又はボクセルを備え、セグメンテーションがピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される、請求項２０に記載の方法。
【請求項２２】
スレッショルド以下の解の値を伴うピクセル又はボクセルが前記フォアグラウンドと関連付けられ、前記スレッショルドより大きな解の値を伴うピクセル又はボクセルがバックグラウンドと関連付けられる、請求項２１に記載の方法。
【請求項２３】
ｎ−１個のスレッショルドが存在し、ｎがピクセルの個数である、請求項２２に記載の方法。
【請求項２４】
前記セグメント特性のメトリックが、ノード集合の周囲長の、前記ノード集合の体積に対する比として定義された、等周比である、請求項２０に記載の方法。
【請求項２５】
前記ノード集合の体積が前記集合中のノードの重み付き次数の和と前記集合中のノードの個数とのうちの少なくとも一方に基づいて計算される、請求項２４に記載の方法。
【請求項２６】
前記医療画像データセットが、３Ｄ医療データセット、２Ｄ医療データセット、又は、より高次元の医療データセットのうちの少なくとも一つを備える、請求項２０に記載の方法。
【請求項２７】
近傍構造が格子である、請求項２０に記載の方法。
【請求項２８】
フォアグラウンドポイントを取得するステップが問題に固有のフォアグラウンドポイントを取得するステップを備える、請求項２０に記載の方法。
【請求項２９】
前記問題に固有のフォアグラウンドポイントを取得するステップがユーザ指定フォアグラウンドポイントを取得するステップを備える、請求項２８に記載の方法。
【請求項３０】
ユーザ介入が必要とされない、請求項２０に記載の方法。
【請求項３１】
デジタル処理装置において実行されるときに請求項２０に記載の方法を実施するプログラム命令が記憶されたコンピュータ読み取り可能な媒体。
【請求項３２】
入力データからツリーを得るコンピュータコードと、
前記ツリーを表現する行列のノーフィルオーダリングを生成するコンピュータコードと、
前記行列に関して連立一次方程式を解法し、解を取得するコンピュータコードと、
一群のセグメンテーションを定義するため解を使用するコンピュータコードと、
セグメント特性のメトリックに基づいて前記一群のセグメンテーションからセグメンテーションを選択するコンピュータコードと、
を備える、画像セグメンテーションのためのコンピュータコードを含むコンピュータ読み取り可能な媒体。
【請求項１】
入力データからツリーを得るステップと、
等周グラフ分割アルゴリズムを使用するためのセッティングとして前記ツリーを使用するステップと、
を備える、グラフ分割方法。
【請求項２】
前記ツリーが距離ツリーである、請求項１に記載の方法。
【請求項３】
前記ツリーが関数ツリーである、請求項１に記載の方法。
【請求項４】
前記関数がデータ中で何が重要であるかを定義する所定の関数である、請求項３に記載の方法。
【請求項５】
等周グラフ分割アルゴリズムを使用するためのセッティングとして前記ツリーを使用するステップが、
前記ツリーを表現する行列のノーフィルオーダリングを生成するステップと、
前記行列に関して連立一次方程式を解法し、解を取得するステップと、
一群のセグメンテーションを定義するため前記解を使用するステップと、
セグメント特性のメトリックに基づいて前記一群のセグメンテーションからセグメンテーションを選択するステップと、
を備える、請求項１に記載の方法。
【請求項６】
入力データからツリーを得るステップと、
前記ツリーを表現する行列のノーフィルオーダリングを生成するステップと、
前記行列に関して連立一次方程式を解法し、解を取得するステップと、
一群のセグメンテーションを定義するため前記解を使用するステップと、
セグメント特性のメトリックに基づいて前記一群のセグメンテーションからセグメンテーションを選択するステップと、
を備える画像セグメンテーション方法。
【請求項７】
前記入力データがピクセル又はボクセルの何れかを備え、
セグメンテーションが前記ピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される、
請求項６に記載の方法。
【請求項８】
スレッショルド以下の解の値を伴うピクセルが前記フォアグラウンドと関連付けられ、前記スレッショルドより大きな解の値を伴うピクセルが前記バックグラウンドと関連付けられる、請求項７に記載の方法。
【請求項９】
ｎ−１個のスレッショルドが存在し、ｎがピクセルの個数である、請求項８に記載の方法。
【請求項１０】
前記セグメント特性のメトリックが、ノード集合の周囲長の、前記ノード集合の体積に対する比として定義された、等周比である、請求項６に記載の方法。
【請求項１１】
前記ノード集合の体積が前記集合中のノードの重み付き次数の和と前記集合中のノードの個数とのうちの少なくとも一方に基づいて計算される、請求項１０に記載の方法。
【請求項１２】
フォアグラウンドポイントを取得するステップをさらに備え、
前記フォアグラウンドポイントを取得するステップが、フォアグラウンドポイントを自動的に取得するステップ、又は、フォアグラウンドポイントを双方向的に取得するステップのうちの何れか一方を備える、請求項６に記載の方法。
【請求項１３】
前記ツリーが距離ツリーである、請求項６に記載の方法。
【請求項１４】
前記ツリーが関数ツリーである、請求項６に記載の方法。
【請求項１５】
前記関数が画像中で何が重要であるかを定義する所定の関数である、請求項１４に記載の方法。
【請求項１６】
前記所定の関数がグレースケール、グラジエント、又は、距離のうちの少なくとも一つである、請求項１５に記載の方法。
【請求項１７】
前記入力データが予め選択されたボクセルのマスクである、請求項６に記載の方法。
【請求項１８】
前記入力データからツリーを得るステップが、
前記入力データからマスクを取得するステップと、
前記マスク上で距離マップを計算するステップと、
距離ツリーを計算するステップと、
を備える、請求項６に記載の方法。
【請求項１９】
ユーザ介入が必要とされない、請求項６に記載の方法。
【請求項２０】
医療画像データセットからマスクを取得するステップと、
前記マスク上で距離マップを計算するステップと、
フォアグラウンドポイントを取得するステップと、
画像の近傍構造上で前記距離マップの関数である重みを伴う最大スパニングツリーを計算するステップと、
前記最大スパニングツリーを表現する行列のノーフィルオーダリングを生成するステップと、
前記行列に関して連立一次方程式を解法し、解を取得するステップと、
一群のセグメンテーションを定義するため前記解を使用するステップと、
セグメント特性のメトリックに基づいて前記一群のセグメンテーションからセグメンテーションを選択するステップと、
を備える医療画像セグメンテーション方法。
【請求項２１】
前記画像がピクセル又はボクセルを備え、セグメンテーションがピクセル又はボクセルをフォアグラウンド又はバックグラウンドの何れか一方と関連付けることにより指定される、請求項２０に記載の方法。
【請求項２２】
スレッショルド以下の解の値を伴うピクセル又はボクセルが前記フォアグラウンドと関連付けられ、前記スレッショルドより大きな解の値を伴うピクセル又はボクセルがバックグラウンドと関連付けられる、請求項２１に記載の方法。
【請求項２３】
ｎ−１個のスレッショルドが存在し、ｎがピクセルの個数である、請求項２２に記載の方法。
【請求項２４】
前記セグメント特性のメトリックが、ノード集合の周囲長の、前記ノード集合の体積に対する比として定義された、等周比である、請求項２０に記載の方法。
【請求項２５】
前記ノード集合の体積が前記集合中のノードの重み付き次数の和と前記集合中のノードの個数とのうちの少なくとも一方に基づいて計算される、請求項２４に記載の方法。
【請求項２６】
前記医療画像データセットが、３Ｄ医療データセット、２Ｄ医療データセット、又は、より高次元の医療データセットのうちの少なくとも一つを備える、請求項２０に記載の方法。
【請求項２７】
近傍構造が格子である、請求項２０に記載の方法。
【請求項２８】
フォアグラウンドポイントを取得するステップが問題に固有のフォアグラウンドポイントを取得するステップを備える、請求項２０に記載の方法。
【請求項２９】
前記問題に固有のフォアグラウンドポイントを取得するステップがユーザ指定フォアグラウンドポイントを取得するステップを備える、請求項２８に記載の方法。
【請求項３０】
ユーザ介入が必要とされない、請求項２０に記載の方法。
【請求項３１】
デジタル処理装置において実行されるときに請求項２０に記載の方法を実施するプログラム命令が記憶されたコンピュータ読み取り可能な媒体。
【請求項３２】
入力データからツリーを得るコンピュータコードと、
前記ツリーを表現する行列のノーフィルオーダリングを生成するコンピュータコードと、
前記行列に関して連立一次方程式を解法し、解を取得するコンピュータコードと、
一群のセグメンテーションを定義するため解を使用するコンピュータコードと、
セグメント特性のメトリックに基づいて前記一群のセグメンテーションからセグメンテーションを選択するコンピュータコードと、
を備える、画像セグメンテーションのためのコンピュータコードを含むコンピュータ読み取り可能な媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公表番号】特表２００８−５１３１６４（Ｐ２００８−５１３１６４Ａ）
【公表日】平成２０年５月１日（２００８．５．１）
【国際特許分類】
【出願番号】特願２００７−５３２６８９（Ｐ２００７−５３２６８９）
【出願日】平成１７年９月２２日（２００５．９．２２）
【国際出願番号】ＰＣＴ／ＵＳ２００５／０３４１５４
【国際公開番号】ＷＯ２００６／０３６７８９
【国際公開日】平成１８年４月６日（２００６．４．６）
【出願人】（５９３０６３１０５）シーメンス メディカル ソリューションズ ユーエスエー インコーポレイテッド (156)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｍｅｄｉｃａｌ Ｓｏｌｕｔｉｏｎｓ ＵＳＡ，Ｉｎｃ．
【住所又は居所原語表記】５１ Ｖａｌｌｅｙ Ｓｔｒｅａｍ Ｐａｒｋｗａｙ，Ｍａｌｖｅｒｎ，ＰＡ １９３５５−１４０６，Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公表日】平成２０年５月１日（２００８．５．１）
【国際特許分類】
【出願日】平成１７年９月２２日（２００５．９．２２）
【国際出願番号】ＰＣＴ／ＵＳ２００５／０３４１５４
【国際公開番号】ＷＯ２００６／０３６７８９
【国際公開日】平成１８年４月６日（２００６．４．６）
【出願人】（５９３０６３１０５）シーメンス メディカル ソリューションズ ユーエスエー インコーポレイテッド (156)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｍｅｄｉｃａｌ Ｓｏｌｕｔｉｏｎｓ ＵＳＡ，Ｉｎｃ．
【住所又は居所原語表記】５１ Ｖａｌｌｅｙ Ｓｔｒｅａｍ Ｐａｒｋｗａｙ，Ｍａｌｖｅｒｎ，ＰＡ １９３５５−１４０６，Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]