パスベースのツリーマッチングのためのシステムおよび方法
【課題】従来技術の欠点を回避するパスベースのツリーマッチングのための方法およびシステムを提供すること。
【解決手段】物理的オブジェクトまたはモデルを表すツリー状構造を収集し；第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し、パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；類似測定に基づいてこれらのパスが一致しているか否かを定める、ツリーマッチングのための方法。
【解決手段】物理的オブジェクトまたはモデルを表すツリー状構造を収集し；第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し、パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；類似測定に基づいてこれらのパスが一致しているか否かを定める、ツリーマッチングのための方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本発明は、本願明細書に、その写しが参照として取り入れられた２００５年６月２２日出願のアメリカ合衆国仮出願６０／６９２，９５４号の便益を主張するものである。
【０００２】
技術分野
本発明は、ツリーマッチングアルゴリズムに関し、より詳細には、医療用画像処理アプリケーションとともに使用される、パスベースのツリーマッチングのためのシステムおよび方法に関する。
【背景技術】
【０００３】
ツリーマッチングアルゴリズムは、医療結像において多数の用途を有している。これは殊に、レジストレーション（重ね合わせ）、解剖学的ラベリング、セグメント化、血管および気道ツリー等の器官の案内を含む。
【０００４】
殊に、ツリーマッチングアルゴリズムは肺結像において以下の目的のために使用される。すなわち：異なる時間に撮影された同じ患者の画像内の気道−気道／動脈−動脈ツリーマッチング；異なる患者からの気道−気道／動脈−動脈ツリーマッチング；解剖学的なラベリングを行うための、アトラスに対する患者からの気道−気道／動脈−動脈ツリーマッチング；２つのツリー構造間での対応関係を定めるため、または付加的な気道または動脈の検出を補助するため、または気管支鏡案内のための画像内での気道−動脈マッチング；アトラス、または異なった時間に撮影された同じ患者の画像との静脈のマッチング、である。
【０００５】
異なった時間での同じ患者内の気道−気道および動脈−動脈マッチングは、イメージレジストレーションおよび自動化された量的分析に対する重要な基礎を提供する。例えばこのようなマッチングによって、病気の進行または治療に対する反応を監視するための、時間にわたった気管支壁厚さの自動的な変化測定が可能になる。アトラスとのマッチングは、レントゲン技師に対して幾つかのタスクを容易にする。この例は、Ｋ. Mori, J.-I. Hasegawa著「Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System (IEEE Trans, on Medical Imaging, pp. 103-114, Vol. 19, Feb 2000）」およびH. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt著 「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images（Proceedings of the ５th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002）」に記載されている。
【０００６】
アトラスマッチングは、レントゲン技師の報告において識別された問題領域と関連して解剖学的名称を定めるために使用される。異なった患者とのマッチングによって、患者データの大きなスケールでの比較が可能になる。同じ患者内での気道−動脈マッチングは気管支鏡案内のために使用される。これに対する例は、B. Geiger, A.P. Kiraly, D.P. Naidich, C.L. Novak著「Virtual Bronchoscopy of Peripheral Nodules using Arteries as Surrogate Pathways (SPIE Physiology, Function, and Structure From Medical Images, Vol. 5746,2005)」およびB. Geiger, A.P. Kiraly, D.P. Naidich, C.L. Novak, 「System and Method for Endoscopic Path Planning（米国特許出願公開第２００５０１０７６７９号明細書）」 に記載されている。同じ患者内の気道−動脈マッチングは、改善された動脈または気道セグメント化に対する基礎としても用いられる。この例は、T. Buelow, R. Wiemker, T. Blaffert, C. Lorenz, S. Renisch著 「Automatic Extraction of the Pulmonary Artery Tree from Multi-Slice CT Data( SPIE Physiology, Function, and Structure Froｍ Medical Images, pp. 730-740, Vol. 5746,2005）」に記載されている。
【０００７】
ツリーマッチングアルゴリズムは、入力としてツリー構造を必要とする。この構造は、分岐点を通じて相互に接続された一連の分枝としてツリーをあらわしている。幾つかの既知のアルゴリズムが、このツリー構造を得るために使用される。これは殊に追跡、セグメント化およびスケルトン化を含む。この例は、 A.P. Kiraly, J.P. Helferty, E.A. Hoffman, G. McLennanおよび W.E. Higgins著 「3D Path Planning for Virtual Bronchoscopy（IEEE Trans. on Medical Imaging, pp. 1365-1379, Vol. 23, Nov 2004）」に記載されている。ツリー構造が得られると、マッチングアルゴリズムは構造およびそこに含まれているあらゆるデータに直接的に作用する。気道、動脈および静脈等の非環ツリー構造体は親分枝および子分枝の固有ヒエラルキーを含む。このようなツリーは、有向性、かつ分岐グラフとして見られる。
【０００８】
同じ患者からの気道−気道ツリーをマッチングさせる幾つかのアプローチがある。アプローチの例はC. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni著「Tracking 3-D Pulmonary Tree Structures （Mathematical Methods in Biomedical Image Analysis, pp. 160-169,1996）」およびJ. Tschirren, K. Palagyi, J.M. Reinhardt, E.A. Hoffmanおよび M. Sonka著「Segmentation, Skeletonization, and Branchpoint Matching - A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees（ SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031,2003)」に記載されている。
【０００９】
さらに、気管支ツリーの自動化された解剖学的ラベリングに対する幾つかのアプローチがある。このアプローチの例は、K. Mori, J.-I. Hasegawa著「Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System （IEEE Trans. on Medical Imaging, pp. 103-114, Vol. 19, Feb 2000）」 およびH. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt著「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images（Proceedings of the 5th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002）」に記載されている。
【００１０】
近年のアルゴリズムは一般的に、分岐部点内のフィーチャのセットを結びつける。このアルゴリズムの例は、C. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni著「Tracking 3-D Pulmonary Tree Structures（ Mathematical Methods in Biomedical Image Analysis, pp. 160-169,1996）」および J. Tschirren, K. Palagyi, J.M. Reinhardt, E.A. Hoffmanおよび M. Sonka著「Segmentation, Skeletonization, and Branchpoint Matching - A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees（ SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031,2003）」および A.C.M. Dumay, R. v.d. Geest, JJ. Gerbrands, E. Jansen, Johan H.C. Reiber著「 Consistent Inexact Graph Matching Applied to Labelling Coronary Segments in Arteriograms（ Proc. l1th IAPR, pp. 439-446, Vol. III, 1992）」 および K. Haris, S.N. Efstratiadis, N. Maglaveras, C. Pappas, J. Gourassas, G. Louridas著「Model-based Morphological Segmentation and Labeling of Coronary Angiograms（ IEEE Trans, on Medical Imaging, pp.1003-1015, Vol 18, Oct 1999)」に記載されている。
【００１１】
これらのアルゴリズムは、関連したグラフ内で最大クリークを見つけるような一般的なグラフマッチング方法を使用する。この例は、M. Pelillo, K. Siddiqi, S.W. Zucker著 「Matching Hierarchical Structures Using Association Graphs（IEEE Trans. on Pattern Analysis and Machine Intelligence, pp. 1105-1120, Vol. 21, Nov 1999）」およびH. Kitaoka, Y. Park, J. Tschirren, J. Reinbardt著 「Automated Nomenclature
Labeling of the Bronchial Tree in 3D-CT Lung Images （Proceedings of the 5 th
International Conference on Medical Image Computing and Computer Assisted
Intervention-Part II, pp. 1-11, Sep 2002）」に記載されている。 これらのアルゴリズムが、ファジィ割り当を緩和することによってグラフマッチングを行ってよい。この例は、S. Medasani, R. Krishnapuram, Y.S. Choi著 「Graph Matching by Relaxation of Fuzzy Assignments （ IEEE Trans. on Fuzzy Systems, pp. 173-182, Vol. 9, Feb 2001)」に記載されている。
【００１２】
上述したツリーマッチングアルゴリズムはグラフマッチング技術に頼っており、単独のアプリケーションに焦点を合わせている。グラフマッチング技術は、確固たる理論的背景を有しているが、現実世界の医療アプリケーションにとって最適な選択ではないだろう。ここでは誤ったまたは欠落した分枝および相違、および解剖分析における変化が生じ得る。さらに、上述したマッチング方法はツリーのヒエラルキー構造を使用して、分枝−分枝レベルでのマッチングを行う。これらの方法はツリー構造を、分枝データから計算されたフィーチャを有するノードの連続としてみなすので、誤った枝はこの方法の効力を低減させてしまう。さらに、これらの方法のうちの幾つかは、各ツリー構造に対して一致された開始点を必要とし、これによってこの情報が得られない時にはこれらの方法は使用できなくなってしてしまう。この要求によって、より正確な結果のためにツリーの予備的なレジストレーションを行うことも必要になる。さらに、多くの上述した方法は、これらの制限を回避するために手動で作成されるまたは編集されることを必要とする、ツリー構造を必要とする。
【特許文献１】米国特許出願公開第２００５０１０７６７９号明細書
【非特許文献１】Ｋ. Mori, J.-I. Hasegawa著「Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System」 IEEE Trans. on Medical Imaging, pp. 103-114, Vol. 19, Feb 2000
【非特許文献２】H. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt著 「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images」Proceedings of the ５th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002
【非特許文献３】B. Geiger, A.P. Kiraly, D.P. Naidich, C.L. Novak著「Virtual Bronchoscopy of Peripheral Nodules using Arteries as Surrogate Pathways 」SPIE Physiology, Function, and Structure From Medical Images, Vol. 5746,2005
【非特許文献４】T. Buelow, R. Wiemker, T. Blaffert, C. Lorenz, S. Renisch著 「Automatic Extraction of the Pulmonary Artery Tree from Multi-Slice CT Data」 SPIE Physiology, Function, and Structure Froｍ Medical Images, pp. 730-740, Vol. 5746,2005
【非特許文献５】A.P. Kiraly, J.P. Helferty, E.A. Hoffman, G. McLennanおよび W.E. Higgins著 「3D Path Planning for Virtual Bronchoscopy」IEEE Trans. on Medical Imaging, pp. 1365-1379, Vol. 23, Nov 2004
【非特許文献６】C. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni著「Tracking 3-D Pulmonary Tree Structures 」Mathematical Methods in Biomedical Image Analysis, pp. 160-169,1996
【非特許文献７】J. Tschirren, K. Palagyi, J.M. Reinhardt, E.A. Hoffmanおよび M. Sonka著「Segmentation, Skeletonization, and Branchpoint Matching - A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees」 SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031,2003
【非特許文献８】K. Mori, J.-I. Hasegawa著「Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System （IEEE Trans. on Medical Imaging, pp. 103-114, Vol. 19, Feb 2000）」
【非特許文献９】H. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt著「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images（Proceedings of the 5th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002）」
【非特許文献１０】C. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni著「Tracking 3-D Pulmonary Tree Structures（ Mathematical Methods in Biomedical Image Analysis, pp. 160-169,1996）」
【非特許文献１１】J. Tschirren, K. Palagyi, J.M. Reinhardt, E.A. Hoffmanおよび M. Sonka著「Segmentation, Skeletonization, and Branchpoint Matching - A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees（ SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031,2003）」
【非特許文献１２】A.C.M. Dumay, R. v.d. Geest, JJ. Gerbrands, E. Jansen, Johan H.C. Reiber著「 Consistent Inexact Graph Matching Applied to Labelling Coronary Segments in Arteriograms」 Proc. l1th IAPR, pp. 439-446, Vol. III, 1992
【非特許文献１３】K. Haris, S.N. Efstratiadis, N. Maglaveras, C. Pappas, J. Gourassas, G. Louridas著「Model-based Morphological Segmentation and Labeling of Coronary Angiograms」 IEEE Trans. on Medical Imaging, pp.1003-1015, Vol 18, Oct 1999
【非特許文献１４】M. Pelillo, K. Siddiqi, S.W. Zucker著 「Matching Hierarchical Structures Using Association Graphs」 IEEE Trans. on Pattern Analysis and Machine Intelligence, pp. 1105-1120, Vol. 21, Nov 1999
【非特許文献１５】H. Kitaoka, Y. Park, J. Tschirren, J. Reinbardt著 「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images 」 Proceedings of the 5 th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002
【非特許文献１６】S. Medasani, R. Krishnapuram, Y.S. Choi著 「Graph Matching by Relaxation of Fuzzy Assignments 」 IEEE Trans. on Fuzzy Systems, pp. 173-182, Vol. 9, Feb 2001
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明の課題は、従来技術の欠点を回避するパスベースのツリーマッチングのための方法およびシステムを提供することである。
【課題を解決するための手段】
【００１４】
上述の課題は、物理的オブジェクトまたはモデルを表すツリー状構造を収集し；第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し、前記パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；当該類似測定に基づいて前記パスが一致しているか否かを定める、ことを特徴とする、ツリーマッチングのための方法によって解決される。さらに上述の課題は、第１のツリー状構造および第２のツリー状構造からパスを収集し；第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較し；第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最も一致しているのかを、当該類似測定に基づいて定める、ことを特徴とする、ツリー状構造のパスを別のツリー状構造にマッチングさせるための方法によって解決される。さらに上述の課題は、プログラムを格納するためのメモリデバイスと；当該メモリデバイスと通信するプロセッサとを含み、ここでこのプロセッサプログラムで動作し：物理的オブジェクトまたはモデルを表すツリー状構造を収集し；第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し：前記パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；当該類似測定に基づいて前記パスが一致しているか否かを定める、ツリーマッチングのためのシステムによって解決される。さらに、上述の課題は、ツリー状構造のパスを別のツリー状構造にマッチングさせるためのシステムであって：プログラムを格納するためのメモリデバイスと；当該メモリデバイスと通信するプロセッサとを含み、ここでこのプロセッサはプログラムで動作し：第１のツリー状構造および第２のツリー状構造からパスを収集し；第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較し；第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最も一致しているのかを、当該類似測定に基づいて定める、ことを特徴とする、ツリー状構造のパスを別のツリー状構造にマッチングさせるためのシステムによって解決される。
【発明を実施するための最良の形態】
【００１５】
発明の概要
本発明の１つの実施形態では、ツリーマッチング方法は以下のステップを含む、すなわち：物理的オブジェクトまたはモデルをあらわすツリー状構造を収集する；第１のツリー状構造からのパスおよび第２のツリー状構造からのパスを抽出する；これらパスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較する；この類似測定に基づいてこれらのパスが一致しているか否かを定める。
【００１６】
この方法はさらに、ツリー状構造の各パスがマッチングするまたは除外されるまで、抽出ステップ、比較ステップおよび確定ステップを繰り返すことを含む。
【００１７】
パスは、１つまたは２つのツリー状構造のヒエラルキーに従って比較される。この方法はさらに以下のステップを含む。すなわち：他のパスの類似測定に基づいてパスが一致しているか否かを定める；マッチされたパスを記録するためのマッチングマトリクスを作成する；最も一致しているパスが既に別のパスと一致している場合には、次の最適一致パスにパスをマッチングさせるための確率マトリクス（Probability matrix）を作成する。
【００１８】
この方法はさらにパスを比較する前にツリー状構造をアライメントすることを含む。
【００１９】
ツリー状構造は気道、動脈または静脈である。ツリー状構造は、追跡、セグメント化、またはスケルトン化（細線化）によって得られる。パスはセグメント化、中心線抽出、または直接的にツリー状構造から抽出される。
【００２０】
パスの抽出は、複数のパスのうちの１つのパスを、複数のパス間の比較に対する基礎として選択することを含む。長いパスのサブセクションにマッチする短いパスが、複数のパス間の比較に対する基礎として選択される。類似測定はパスの距離フィーチャ、角度フィーチャ、距離分散（distance variance）フィーチャ、またはこれらのフィーチャの数値的な組み合わせである。
【００２１】
本発明の他の実施形態では、ツリー状構造のパスを別のツリー状構造とマッチングさせるための方法は次のことを含む。すなわち：第１のツリー状構造および第２のツリー状構造からパスを収集する；第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較する；第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最も一致しているのかを、この類似測定に基づいて定める。
【００２２】
この方法はさらに、第１および第２のツリー状構造をマッチさせるために、収集ステップ、比較ステップおよび確定ステップを繰り返すことを含む。
【００２３】
第１および第２のツリー状構造のパスは、１つまたは２つのツリー状構造のヒエラルキーに従って比較される。
この方法はさらに以下のステップを有する。すなわち：マッチされたパスを記録するためのマッチングマトリクスを作成する；最も一致パスが既に別のパスに一致している場合には、次の最適一致パスを可能にするために、パスをマッチングさせるための確率マトリクスを作成する。
【００２４】
本発明のさらに別の実施形態では、ツリーマッチングのためのシステムは以下のものを含む。すなわち：プログラムを格納するためのメモリデバイスと；このメモリデバイスと通信するプロセッサを含み、このプロセッサは以下のプログラムで動作する、すなわち：物理的オブジェクトまたはモデルをあらわすツリー状構造を収集する；第１のツリー状構造からのパスおよび第２のツリー状構造からのパスを抽出する；これらのパスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較する；この類似測定に基づいてこれらのパスが一致しているか否かを定める。
【００２５】
このプロセッサはさらに、ツリー状構造の各パスがマッチするまたは除外されるまで抽出ステップ、比較ステップおよび確定ステップを繰り返すプログラムコードで動作する。
【００２６】
パスは１つまたは２つのツリー状構造のヒエラルキーに従って比較される。
このプロセッサはさらに、以下のプログラムコードで動作する。すなわち：他のパスの類似測定に基づいてこれらのパスが一致しているか否かを定める；マッチされたパスを記録するためのマッチングマトリクスを作成する；最も一致しているパスが既に別のパスに一致している場合にパスを次の最適一致パスにマッチングさせるための確率マトリクスを作成する。
【００２７】
本発明のさらに別の実施形態では、ツリー状構造のパスを別のツリー状構造とマッチングさせるためのシステムは以下のものを含む。すなわち：プログラムを格納するためのメモリデバイスと；このメモリデバイスと通信するプロセッサとを含み、ここでこのプロセッサは以下のプログラムで動作する。すなわち：第１のツリー状構造および第２のツリー状構造からパスを収集する；第１のツリー状構造および第２のツリー状構造からのパスに対する類似測定を計算することによって、第１のツリー状構造のパスを第２のツリー状構造のパスと比較する；この類似測定に基づいて、第２のツリー状構造のどのパスが、第１のツリー状構造のパスと最も一致するかを定める。
【００２８】
このプロセッサはさらにプログラムコードで作動し、第１および第２のツリー状構造がマッチするまで、収集ステップ、比較ステップおよび確定ステップを繰り返す。
【００２９】
第１および第２のツリー状構造のパスは、１つまたは２つのツリー状構造のヒエラルキーに従って比較される。
【００３０】
このプロセッサはさらにプログラムコードで作動し：マッチされたパスを記録するためのマッチングマトリクスを作成する；最も一致しているパスが既に別のパスにマッチングしている場合に次の最適一致パスを可能にするために、パスをマッチングさせるための確率マトリクスを作成する。
【００３１】
上述の特徴は代表的な実施形態のものであり、本発明の理解を補助するために提示されている。これらは特許請求の範囲によって規定される本発明を限定するもの、また特許請求の範囲に相当するものを限定するものと考えられるべきではない。従って、この特徴の概要は相当事項を確定するための方向性を定めるものと考えられるべきではない。本発明のさらなる特徴は以下の説明、図および特許請求の範囲から明らになるであろう。
【実施例】
【００３２】
実施例の詳細な説明
本発明の実施形態に従ったパスベースツリーマッチングに対する一般的な枠組みは、ツリー構造から導かれたパスを他のツリー構造からのパスと比較することを伴う。これはパスの逐点（point-by-point）比較を行うことによって実行される。ここではこのパス間の類似性をあらわすフィーチャが使用され、これらのフィーチャに基づいて数値的な値が得られる。その後この数値的値は、これらのパスが一致したのか否かを定めるために使用される。
【００３３】
パスベースのツリーマッチング方法はグラフマッチングから独立している。これは完全なパスの逐点比較に基づいているので分岐点から独立しており、従って誤った分枝および欠落した分枝に対して非常に強い。このパスベースのツリーマッチング方法は不規則なツリー構造を支持する。これは例えば複数の親を有する分枝または不完全なセグメント化および中心線抽出によって生じる平らなループである。
【００３４】
これらのフィーチャはヒエラルキーを回避することによって得られるが、階層的な拘束を伴うツリー全体のマッチングは粗い方法で起こり得る。これは例えば、本発明の実施形態に相応する分枝拘束を用いることによって起こり得る。付加的に、パスベースツリーマッチング方法は多対一パスマッピングを可能にするが、一対一パスマッピングがマッチングマトリクスによって強化される。さらにパスベースツリーマッチング方法は、一般的なグラフマッチングアルゴリズムよりも多くの処理時間を必要とするが、実行時間を低減させるために使用される種々の最適化が考察される。
【００３５】
本発明の実施形態に相応する、パスベースツリーマッチングのためのシステムおよび方法を以下で詳細に説明する。
【００３６】
図１は、本発明の実施形態に相応した、パスベースツリーマッチングのためのシステム１００をあらわすブロックダイヤグラムである。図１に示されているようにシステム１００は収集デバイス１０５、ＰＣ１１０およびオペレータコンソール１１５を含む。ここでこのオペレータコンソールはワイヤ接続された、またはワイヤレスのネットワーク１２０を介して接続されている。
【００３７】
収集デバイス１０５は、磁気共鳴（ＭＲ）結像デバイス、コンピュータトモグラフィ（ＣＴ）結像デバイス、ヘリカルＣＴデバイス、陽電子放射型コンピュータ断層撮影（ＰＥＴ）デバイス、シングルフォトンエミッションコンピューテッドトモグラフィ（ＳＰＥＣＴ）デバイス、ハイブリッドＰＥＴ−ＣＴデバイス、ハイブリッドＳＰＥＣＴ−ＣＴデバイス、二次元または三次元蛍光透視デバイス、二次元、三次元または四次元超音波（ＵＳ）結像デバイス、またはｘ線デバイスであってよい。さらに、収集デバイスはマルチモデルまたはハイブリッド収集デバイスであってよい。これは例えばＰＥＴモード、ＳＰＥＣＴモードまたはＭＲモードで画像を収集することができる。
【００３８】
ＰＣ１１０は、ポータブルまたはラップトップコンピュータ、医療診断結像システムまたはPicture archiving communication system（ＰＡＣＳ）データ管理ステーションであってよく、ＣＰＵ１２５およびメモリ１３０を含む。これは入力デバイス１５０および出力デバイス１５５と接続されている。ＣＰＵ１２５は、パスベースツリーマッチングモジュール１４５を含む。これは、以降で図２〜６を参照して考察するパスベースツリーマッチングを実施するための１つまたは複数の方法を含んでいる。ＣＰＵ１２５内に示されているが、パスベースツリーマッチングモジュール１４５はＣＰＵ１２５の外側に配置されていてもよい。
【００３９】
メモリ１３０は、ランダムアクセスメモリ（ＲＡＭ）１３５およびリードオンリーメモリ（ＲＯＭ）１４０を含む。メモリ１３０は、データベース、ディスクドライブ、テープドライブ等、またはその組み合わせを含み得る。ＲＡＭ１３５はデータメモリとして機能する。これはＣＰＵ１２５内のプログラムの実行の間に使用されるデータを格納し、ワーク領域として使用される。ＲＯＭ１４０は、ＣＰＵ１２５内で実行されるプログラムを格納するためのプログラムメモリとして機能する。入力部１５０は、キーボード、マウス等によって構成されており、出力部１５０は液晶ディスプレイＬＣＤ、ＣＲＴディスプレイまたはプリンタによって構成される。
【００４０】
システム１００の動作はオペレータコンソール１１５からコントロールされる。このオペレータコンソールは例えばキーボードであるコントローラ１６５およびディスプレイ１６０を含む。オペレータコンソール１１５はＰＣ１１５および収集デバイス１０５と通信し、収集デバイス１０５によって集められた画像データがＰＣ１１０によってレンダリングされ、ディスプレイ１６０上で見られる。ＰＣ１１０は、オペレータコンソール１１５がなくても、収集デバイス１０５によって供給された情報を処理し、表示することができるものと理解されたい。これは例えばコントローラ１６５およびディスプレイ１６０によって実行される特定のタスクを行う、入力１５０および出力１５５デバイスを用いることで行われる。
【００４１】
オペレータコンソール１１５はさらに、あらゆる適切な画像レンダリングシステム／ツール／アプリケーションを含んでよい。これは、収集されたイメージデータセットのデジタルイメージデータ（またはその一部）を処理し、イメージを作成し、ディスプレイ１６０上に表示する。より詳細には、画像レンダリングシステムは、医療画像データをレンダリングし、視覚化するアプリケーションであり、汎用コンピュータワークステーションまたは専用コンピュータワークステーションで実行される。ＰＣ１１０も上述した画像レンダリングシステム／ツール／アプリケーション含み得ることを理解されたい。
【００４２】
図２は、本発明の実施形態に従った、パスベースツリーマッチング方法の動作を表すフローチャートである。
【００４３】
図２に示されているように、物理的オブジェクトまたはモデルをあらわすツリー状構造が収集される（２１０）。
【００４４】
パスベースのツリーマッチング方法ではツリーＴは、二重リンク有向性分枝Ｂ＝（ＳＢ、ＰＢ、ＣＢ）の集合である。これは等距離の部位（Site）のセットＳＢを含み、自身の親ＰＢ（例えば気道または動脈内の１つ）にリンクし、その子ＣＢ（例えば気道または動脈に２つまたはそれより多い）にリンクする。親を有していない分枝ＰＢ＝φはルート分枝と定められ、またいかなる子も有していない分枝ＣＢ＝φは終端分枝と定められる。部位のセットＳＢは、順序付けされた等距離の三次元座標のベクトルである。これは開始部位として定められた第１の部位と、ＳＢの終端部位と定められた最後の部位を伴う。さらに、分枝は常に親または子であると見なされているので、ツリーは固有のヒエラルキーを含む。ループがないと想定すると、各分枝は特定の世代番号に属する。ルート分枝は世代０で、このルートの子は世代１である、等である。
【００４５】
ツリー状構造は、気道、動脈、静脈および管路系等のあらゆる分岐管状構造である。この分岐管状構造は例えば収集デバイス１０５を使用することによって得られる。これは例えばＣＴスキャナーであり、患者の胸部をスキャンして、肺に関する、一連の二次元画像切片を作成する。その後、この肺の二次元画像切片が組み合わされ、三次元画像が作成される。
【００４６】
肺に加えて、分岐管状構造は体のあらゆる部分から収集されることを理解された。これは例えば肝臓、脚または脳である。さらに、ＭＲＩデバイスまたは他のあらゆる結像デバイスから得られた他のタイプのデータが、本発明の実施形態に相応して使用されてよい。これらの結像デバイスは収集デバイス１０５の種々の変更に関連する。
【００４７】
ツリー状構造が得られると、各構造からパスが抽出される（２２０）。
【００４８】
パスは、１つまたは複数の直接的にリンクされた分枝の組み合わせである。これは、第１の分枝内のあらゆる部位で始まり、関連する最後の分枝のあらゆる部位で終了する。完全なパスは、ルート分枝のルート部位で始まり、あらゆる終端分枝の終端部位で終わるパスとして定められる。このヒエラルキーの故に、あらゆる完全なパスは常にルート分枝を含む。このパスはあらゆるセグメント化、中心線抽出またはキャプチャー方法によって抽出される。
【００４９】
各ツリー状構造からパスを抽出した後、これらのパスは、パス間の類似測定を計算することによって相互に比較される（２３０）。この測定は関数を使って定められる。この関数は、１つのパスからの点を他のパス内の点と比較する。ここでパスのうちの１つが、比較のための基礎として選択される。
【００５０】
パス比較のための２つのパスのうちのより短いほうを選択することはより効果的であることを理解されたい。なぜなら、短いほうのパスは長いほうパスのサブセクションにマッチすると想定されるからである。これは等しい対応部分を有していない部位毎の（site-by-site）比較における点を使用することを回避する。しかし、長いほうのパスを使用することも可能であり、このパスベースツリーマッチング方法の使用を制限するものではない。例えば、完全な気道パスがより隣接して始まるルート部位を有し、動脈パスがおそらくさらに周囲へ向かって延在するであろう場合にも、周辺の気管支に対して動脈をマッチングさせることが可能である。
【００５１】
基礎またはオリジナルツリー内の開始および終了部位を選択した後に、全ての部位を、中間的に１つの構造体に結合させることによってオリジナルパスが作成される。ここでこの構造体はヒエラルキー情報を有していない。すなわち、親および子分枝の全ての概念が除去され、一連の部位が残される。
【００５２】
幾つかの異なった類似性フィーチャがパスを比較するのに使用される。３つの例が含まれる。すなわち：距離、角度および分散である。距離フィーチャはパス間のオフセットをあらわし、角度フィーチャはパス方向における差を示し、分散フィーチャはパス間のオフセットの変化を計算する。他のフィーチャも、パスを比較するために使用可能である。最適なフィーチャの選択はアプリケーションに依存するが、上述したフィーチャは、一般的なケースにおいて良好に機能する。他の数値的なフィーチャを容易にパスベースツリーマッチング方法に組み入れることができる。
【００５３】
距離フィーチャは比較されるパス間の平均二乗された距離をあらわす。これは、オリジナルパスの各部位と、比較パス内のその最も近い部位の間の、二乗された距離を要約することによって計算される。その後、オリジナルパスの部位の数によって、この合計が除算される。核分枝の全ての部位が等しい距離に位置しているので、部位の数はパスの長さに等しい。
【００５４】
【数１】
【００５５】
ここでＰｉ＝オリジナルパスの部位ｉであり、Ｃ（Ｐｉ| q）＝Ｐｉに対する比較構造のパスｑ内の最も近い部位である。
【００５６】
角度フィーチャは、比較される２つのパスの方向の平均差異を見積もる。分枝の直線再現は使用されないので、各部位でのパスの方向は僅かに異なり得る。正確な差異を計算するために、オリジナルパスのどの部位が、比較分枝のどの部位に相応するのかを知る必要がある。この関係は事前には知られていないので、オリジナルパスの各部位での正接の方向と、比較パスの最も近い部位での方向の間の差異が使用される。その後、合計がオリジナルパスの点の数によって除算される。
【００５７】
【数２】
【００５８】
ここで
＝オリジナルパスの部位ｉでの方向であり、
＝Ｐｉに対する比較構造のパスｑ内の最も近い部位での方向である。
【００５９】
分散フィーチャは、上述した距離フィーチャにわたる分散である。
【００６０】
【数３】
【００６１】
ここでＰｉ＝オリジナルパスの部位ｉであり、Ｃ（Ｐｉ| q）＝Ｐｉに対するパスｑ内の最も近い部位であり、ｄは平均二乗された距離である。
【００６２】
これらのフィーチャが計算されると、パスが一致しているか否かが定められる（２４０）。
【００６３】
これは例えば、これらのフィーチャを比較ツリーの完全なパスに加えることによって、実行される。これによってオリジナルパスに関する距離ベクトルが得られる。このベクトルを単独値に変換するために、ノルム化されたコンビネーション（Normed combination）と称される、シンプルなコンビネーション方法が使用される。ノルム化されたコンビネーションは、各成分の変化性を考慮する。ここで高い変化性を伴う成分は、低い変化性を伴う成分よりも低い重みを受け取る。これは各成分をその分散で再スケーリングすることによって得られる。距離ベクトル
のノルムは
【数４】
に等しい。
【００６４】
ここで、
は分散のマトリクスであり、ここでメインダイアゴナルおよびゼロ値およびあらゆるほかのところでの分散を有する。結果として、比較ツリーの各完全なパスは単独値を有する。これはオリジナルパスへのその類似性をあらわす。ここで、もっとも小さい値を有するパスが最適一致になる。等しい小さい値を複数のパスが有する場合には、そのうちの１つが無作為に選択される、またはより進歩した分析が、現在のマッチとの調和に基づいて実施される。
【００６５】
このパスベースツリーマッチング方法を使用して完全なツリーがマッチする場合には、多対一マッチングが生じる。なぜならマッチングはパス毎に行われ、現在のマッチ割当を考慮しないからである。換言すれば、オリジナルツリー内の各パスが、比較ツリー内のパスに対して１つの一致しか有していなくても、比較ツリー内の所与のパスは、オリジナルパス内の１つより多いパスと一致される。一対一マッチングは、最初に完全な距離マトリクスを計算すること、および次にこのマトリクスに基づいてベストマッチを選択することによって得られる。
【００６６】
２つのパスが一致しているので、種々のラインベースフィーチャが使用されて、類似測定値が定められる。この類似測定値は、２つの三次元曲線間の変換に基づいてよい。曲率および一連の点の関数のあらゆる他の尺度等のフィーチャも使用可能である。例えば高い次数の多項式がパスにフィットし、その方程式が比較に使用される。さらに、これらのフィーチャの組み合わせが使用され、パスベースツリーマッチング方法の強さが高められる。
【００６７】
全体的なツリー構造をマッチングさせるためのパスベースツリーマッチング方法の使用の記述が続く。例えば、一致が所望されているオリジナルツリー内でパスを手動で示す代わりに、各完全なパスが自動的に選択され、他のツリー内の他の完全なパスに一致される。これは、ツリー内の全てのパスが一致されるまで各可能な完全なパスに対して、繰り返される（２５０）。
【００６８】
しかし、計算されるフィーチャ、特に距離フィーチャを収納するために、ツリー構造全体がマッチングされる前に、ツリー構造の幾つかの種類のアライメントが実施される必要があることを理解されたい。このアライメントは、多くのアプリケーションにおいて、ツリー構造の主要分枝点を用いることで実行される。このアライメントは自動的に行われ得る。気道−動脈マッチングでは、ルート部位における違い（例えば、気道に対する気管および動脈に対する心臓）のために、このアライメントプロセスが可能でないことがある。
【００６９】
角度および距離変動等の他のフィーチャはパス位置からより独立しているので、ツリー構造はアライメントされる必要がない。なぜなら、これらはアフィン変換に対してそれほど敏感ではない、または不変だからである。これらのフィーチャはおそらく、適切なマッチングのために付加的な拘束を必要とするであろう。なぜならこれらは多くの可能な一致を可能にするからである。例えば、これらのフィーチャは、左肺および右肺内の気道パスを、第２のツリーの右肺内のパスに一致させることを可能にする。従って、このようなことを起こるのを阻止するために付加的な拘束が必要とされる。
【００７０】
一対一マッチング拘束がマッチングマトリクスを使用することによって付加される。パス対パスマッチングが多対一マッピングを生じさせるので、一対一に対する一致を拘束する目的のために、一致のマトリクスが作成される。このマトリクスは、列内に挙げられた第１のツリーの全ての可能なパスを含む。また、第２のツリーの全ての可能なパスが行内に挙げられている。マトリクス内の各エントリは、２つのパス間の一致の尺度を含む。全ての距離値の絶対的な最小距離の反復した選択し、上述したようにタイを処理し、一致したとして関連するパスにラベリングし、これらをさらなるマッチングに対して無視することによって、一対一一致拘束が強制的に実施される。
【００７１】
オリジナルパスは比較ツリー内に同等なものを有していないので、一対一マッチング拘束は適切な結果を得ずに、早期の一致が不正確に行われた場合には、誤ったラベリングの連鎖に終わってしまう。従って、確率マトリクスが導入される。この確率マトリクスは一対一一致を作成することを試みるが、単独のケースでは多対一マッチングを可能にもする。従って一致されたパスは、さらなるマッチに対して完全には無視されない。
【００７２】
例えば、最も一致しているパスが既に一致されている場合には、その相違測定値が僅かにのみ高い、次のベストの、一致されていないパスがベストマッチよりも高い可能性になる。このような要求を満たすさらなるパスが見つけられない場合には、既に一致しているパスがベストマッチとしてラベリングされ、この一致の確率およびこのパスの既に存在している一致の確率が割り当てられた一致の数によって低減される。このマッチングマトリクスを用いることによって、一対一マッチングが改善される。これは先行の一致のスコアが特定の一致に与えられることが阻止されることによって行われる。このマトリクスは、この枠内で拘束が形成される１つの方法でしかない。
【００７３】
一致されたパスが与えられると、これらのパス内のどの分枝が対応しているのかが定められる。従って分枝対分枝マッチングはこの結果から導き出される。これは、一致されたパスを介して一致されている、各分枝または一連の点に対して一致票数を作成することによって実行される。より頻繁に一致される分枝が、最初に一致される。例えば、n個の一致されたパスが暗に同じ２つの分枝に一致する場合、この分枝一致はｎ票数を得る。この投票スキーマは、どの分枝がともに一致しているのかを定めるのに使用されるだけでなく、所与の分枝一致が得た票の数、および第２の競争相手が得た票の数に基づいて信頼度を定めるのにも使用される。この信頼度ファクターは、さらなる処理ステップに影響を与えるために使用される。
【００７４】
例えば、レジストレーション方法において、より大きな信頼度を有する一致はレジストレーションモデルに対してより大きい影響力を有する。低い信頼性領域もユーザに提供可能であり、これによって迅速な半自動インタフェースが可能になる。付加的に、一連の一が一致されるので、オリジナルツリー内の１つの分枝が他のツリー内の２つの分枝に一致される。誤った分枝が正しい分枝を２つの部分に分ける場合にこれが起こり得る。
【００７５】
分枝マッチングの使用は、ヒエラルキー拘束も可能にする。高い信頼度でマッチングされた２つの分枝は、次のことを課す。すなわち、これらの分枝を有する全ての他の可能なパスがこれらの分枝の部位で一致しなければならないことを課す。付加的に、１つの分枝が一致すると、反復プロセスが行われ、一致された分枝の終端がルート部位として機能し、プロシージャが繰り返される。この反復方法はヒエラルキー拘束の使用を可能にする。また同時にグラフマッチングを基本とした方法の欠点を同じく回避することができる。
【００７６】
パスベースツリーマッチング方法は、一般的なグラフマッチングアルゴリズムより長い処理時間を必要とするので、以下で説明する幾つかの最適化がこの方法の速度を高めるために使用される。
【００７７】
第１に、比較動作はそれぞれ独立しているので、パスベースツリーマッチング方法は多重インプリメンテーションに対して開放されている。これによってデュアル・プロセッサ上で潜在的に速度が２倍になり、より多くのプロセッサを有するプロセッサ上でさらに速くなる。第２に、遠いまたは非常に不所望なパス一致が容易に識別され、よりコストのかかる比較ステップが回避される。第３に、最適なフィーチャ組み合わせの識別の後、各比較ペアに対する個々のフィーチャの計算が最適化され、各フィーチャセットに対する計算時間が単独フィーチャの目下の計算時間よりも長くなることがない。フィーチャはポイントベースなので、計算時間は、パスを定める部位の数に依存する。幾つかのケースでは、最適な結果に達するための部位の間の必要な距離が増加する。これは、各フィーチャ計算に対する計算時間を直接的に低減させる。
【００７８】
他の最適化では、現在の一致に基づくマッチングマトリクスおよびヒエラルキー拘束が、どのパスが比較されるべきでないのかを予測するのに使用される。従って、従来のグラフマッチングのほうが本来は速いが、これらの最適化の使用はパスベースツリーマッチング方法に必要とされる時間を格段に低減させる。しかし、単独パスのマッチのみを必要とする気管支鏡プランニング等のアプリケーションにおいては、パスベースのツリーマッチング方法はグラフマッチングアプローチより性能が優れている。なぜなら全体的なマッチングプロセスが行われる必要がないからである。
【００７９】
全ての分岐を可能な一致であると考慮しない場合の速度差の例を次に挙げる。１つのフィーチャを使用して、４４のパスを有するツリーを、６６のパスを有するツリーにマッチングさせるための時間は４分２８秒である。各オリジナルパスが全ての比較パスと比較されるので、このフィーチャは約２９００回計算され、これは９２．２ｍｓの平均処理時間で行われる。これは各パス内の部位の数に依存する。例えば右／左の上葉支と右／左の体幹中間との間の分岐点の事前識別は、オリジナルツリーを４つの部分に分ける。これは約４倍の速度上昇になる。一般的な距離等の他の比較フィーチャも、どのパスが比較される必要がないかを定めるために使用される。
【００８０】
このパスベースのツリーマッチング方法は、気道−気道マッチングおよび気道−動脈マッチングで、優秀な結果を伴ってテストされている。最初の妥当性確認のために、気道ツリーの一部は合成して作成された比較ツリーに一致されている。人工的なツリーは、基礎としてオリジナルのデータを使用し、その後このデータを修正することによって作成される。はじめに、パラメータ特有の領域内のランダムオフセットが各部位に加えられ、これらのツリーの間のポジショニング偏差がシミュレートされる。次にパラメータ化された変化を伴うガウシアン分布ノイズが部位に加えられ、呼吸のような他の可能な差の源がシミュレートされる。この技術を使用して、マッチングに対するフィーチャの頑強性に対するノイズとオフセットの影響が試験される。５０００より多くのパス一致の妥当性確認結果が、図３に示されている。図３に示された結果を生じさせる実験は、３つのフィーチャD（距離）、Ａ（角度）、Ｖ（分散）、Ｅｕｃ（ユークリッド）およびＮｏｒｍ（ノルム）の妥当性確認を、オフセットおよびノイズに対する７５個の異なったパラメータセッティングを有する組み合わせで含む。ここでこれらのマッチング結果は、グラウンドトルースと比較され、正しい分類の割合が定められる。
【００８１】
それぞれが単独で加えられる場合、図３に示されているように、角度および分散フィーチャは、９５％を超える正しいマッチング結果に達する。単独で加えられた場合に、距離フィーチャだけが、他のフィーチャによって得られるような良好な結果を得ない。しかし約８５％の正しい分類を有し、単独で加えられた場合に距離フィーチャは完全には使用不可能ではない（図１におけるｙ軸が０で始まるのではないことに注意されたい）。ユークリッドコンビネーションの領域が分散フィーチャの領域より高いので、これは距離フィーチャの結果によって影響される。結果として、角度と分散のユークリッドコンビネーションは、傑出した結果に達する。対照的に、ノルム組み合わせは、低いフィーチャパフォーマンスによってそれほど影響されない。他方でユークリッドコンビネーションは従って多くの組み合わせが、９５％を超える正しいマッチング結果に達する。距離フィーチャと分散フィーチャの組み合わせはそれ程正確ではないが、それでも距離フィーチャ単独よりも信頼性がある。
【００８２】
図４は、患者の抽出した気道ツリーと数ヶ月後の同じ患者の追跡収集との間のマッチング結果を示している。ここでは全てのバリエーションにおけるＤ（距離）、Ａ（角度）、Ｖ（分散）Ｅｕｃ（ユークリッド）およびＮｏｒｍ（ノルム）組み合わせがテストされている。最初の気道セグメンテーションは追跡ツリーではセグメンテーションされていかった分枝を含んでいるので、完全に正確なマッチングは行われない。これらの付加的な分枝に対応するパスは、「Ｎ／Ａ」としてラベリングされる。このマッチング結果は、グラウンドトルースと比較され、「真実（例えば正しい）」および「誤り（例えば正しくない）」分類が定められる。
【００８３】
総体的に、４４のパスが含まれたマッチングは、平均で７．７５個の分枝をパス毎に有している、８３の分枝から成る。マッチングマトリクスを使用しない場合、６．８％（例えば４４のうち３つ）の誤りマッチングレートが、分散を除くあらゆるフィーチャを用いて得られる。マッチングマトリクスを導入した場合、例えば、２つの付加的な正しいマッチによって、Ｄ（距離）、Ｖ（分散）およびＮｏｒｍ（ノルム）組み合わせが改善される。これは結果としてパスの２．３％の誤りマッチングレートになる。付加的に、誤ったマッチの多くは終端分枝において誤りを含む。従って、誤ったマッチとラベリングされたパスさえも、多くの分枝にわたって正しいことがある。図５に示されているように、２つのツリー（例えば濃い点線で示されているオリジナルツリーと薄い点線で示されている比較ツリー）は分枝の数および長さにおいて相違を有する。それにもかかわらずパスベースのツリーマッチング方法は首尾良く多くの分枝とパスを一致させる。分枝レベルでのパスベースツリーマッチング方法の評価も可能である。なぜなら、パスマッチが与えられていると、分枝対分枝マッピングを構成することが可能だからである。
【００８４】
図６には気道と動脈パスとの間のマッチングが示されている。ここで気管支ツリー内に大きい円で示された開始部位が手動で選択される。次に、開始部位の周辺のサブボリューム内の血管が自動的にセグメント化され、開始部位に近い血管セグメンテーション内でルート部位を無作為に選択することによってツリー構造体にキャプチャーされる。次に開始部位で始まる全てのパスおよび全ての子孫終端分枝で終わる全てのパスが血管ツリー内の全ての完全なパスにマッチされる。あらゆるマッチングマトリクスを使用せずに選択された一致されたパスには２つのツリー内で同じ色が与えられ、濃い線でレンダリングされたオリジナルツリーと、薄い線でレンダリングされた比較ツリーを伴う。２つの異なる一致からの部位が重畳される場合、最後に一致されたパスの色が重畳領域内の全ての部位に与えられる。このカラーリングプロシージャの結果は、分枝対分枝カラーリングに類似してあらわれる。
【００８５】
本発明の実施形態に相応するパスベースツリーマッチング方法は、種々のツリーマッチングアプリケーションに使用可能である。現在の方法はグラフマッチング技術に頼っている。これはより厳格な要求を有し、誤った分枝によってより妨害されやすい。しかしパスベースツリーマッチング方法は、ツリーの異なった部分でルート分枝を有することの柔軟性を可能にし、また成功した一致が得られる。付加的に、パスベースツリーマッチング方法によって、１つのツリー内の２つの分枝が比較ツリー内の分枝と一致され、誤った中央分枝が収容される。これは標準のノードベースマッチング方法で実現するのは困難である。
【００８６】
さらに、本発明を種々の形態のハードウェア、ソフトウェア、ファームウェア、特定の目的のプロセッサまたはこれらの組み合わせに実装可能であることを理解されたい。１つの実施形態では、本発明はアプリケーションプログラムとしてソフトウェア内に実装される。これは実体的にプログラム記憶装置上で実行される（例えば磁気フロッピィディスク、ＲＡＭ、ＣＤ−ＲＯＭ、ＤＶＤ、ＲＯＭおよびフラッシュメモリ）。このアプリケーションプログラムはあらゆる適切なアーキテクチャを含む機械によってアップロードされ、実行される。
【００８７】
さらに、添付図面内に示された幾つかの構成素子的なシステムコンポーネントおよび方法ステップがソフトウェアで実装され、システムコンポーネント（またはプロセスステップ）間の実際のコネクションが、本発明がプログラムされる方法に依存して異なってよいことを理解されたい。この明細書に示された本発明の教示があれば、当業者はこれらおよび本発明の実装または構成に類似したものを企図することができる。
【００８８】
また上記の説明は、具体的な実施形態を示すためのものにすぎないことも理解されたい。理解しやすいように、上記の説明では可能な実施形態の代表的な例に的を絞っていたが、これらは本発明の基本的な思想を詳解するためのものであって、すべての可能な変形形態を排他的に列挙したわけではない。本発明の特定部分において代替的な実施形態が示されなかったこと、またはさらなる未記載の選択肢が部分に対して使用可能であることは、これらの実施形態の放棄と見なされるべきではない。別の適用形態や実施形態も、本発明の趣旨および範囲から逸脱することなく直接実現することができる。
【００８９】
したがって本発明は、特記された実施形態に制限されることない。なぜなら、上述のものに対する非新規的な代用に関連する上述したものおよび実装の多くの置き換えおよび組み合わせを作成することが可能だからである。本発明は、後続の請求の範囲で特定される。請求の範囲における文言上の範囲には未記載の実施形態が多く含まれ、これらも本発明と同等のものであることを理解されたい。
【図面の簡単な説明】
【００９０】
【図１】本発明の実施例に従ったパスベースツリーマッチングのためのシステムをあらわしたブロックダイヤグラム
【図２】本発明の実施例に従ったパスベースツリーマッチングのための方法をあらわしたフローチャート
【図３】図２の方法による、合成ツリーに一致された気道サブツリーの精度結果を示す棒グラフ
【図４】図２の方法によって一致された、異なる時間に抽出された同じ患者の気道ツリーの精度結果を示す棒グラフ
【図５】図２の方法によって一致された２つのツリーの例
【図６】図２の方法によって一致された、気道および動脈パスの例
【符号の説明】
【００９１】
１００ システム、 １０５ 収集デバイス、 １１５ オペレータコンソール、 １２５ ＣＰＵ、 １３０ メモリ、 １３５ ＲＡＭ、 １４０ ＲＯＭ、 １４５ パスベースツリーマッチングモジュール、 １５０ 入力部、 １５５ 出力部、 １６０ ディスプレイ、 １６５ コントローラ
【技術分野】
【０００１】
関連出願の相互参照
本発明は、本願明細書に、その写しが参照として取り入れられた２００５年６月２２日出願のアメリカ合衆国仮出願６０／６９２，９５４号の便益を主張するものである。
【０００２】
技術分野
本発明は、ツリーマッチングアルゴリズムに関し、より詳細には、医療用画像処理アプリケーションとともに使用される、パスベースのツリーマッチングのためのシステムおよび方法に関する。
【背景技術】
【０００３】
ツリーマッチングアルゴリズムは、医療結像において多数の用途を有している。これは殊に、レジストレーション（重ね合わせ）、解剖学的ラベリング、セグメント化、血管および気道ツリー等の器官の案内を含む。
【０００４】
殊に、ツリーマッチングアルゴリズムは肺結像において以下の目的のために使用される。すなわち：異なる時間に撮影された同じ患者の画像内の気道−気道／動脈−動脈ツリーマッチング；異なる患者からの気道−気道／動脈−動脈ツリーマッチング；解剖学的なラベリングを行うための、アトラスに対する患者からの気道−気道／動脈−動脈ツリーマッチング；２つのツリー構造間での対応関係を定めるため、または付加的な気道または動脈の検出を補助するため、または気管支鏡案内のための画像内での気道−動脈マッチング；アトラス、または異なった時間に撮影された同じ患者の画像との静脈のマッチング、である。
【０００５】
異なった時間での同じ患者内の気道−気道および動脈−動脈マッチングは、イメージレジストレーションおよび自動化された量的分析に対する重要な基礎を提供する。例えばこのようなマッチングによって、病気の進行または治療に対する反応を監視するための、時間にわたった気管支壁厚さの自動的な変化測定が可能になる。アトラスとのマッチングは、レントゲン技師に対して幾つかのタスクを容易にする。この例は、Ｋ. Mori, J.-I. Hasegawa著「Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System (IEEE Trans, on Medical Imaging, pp. 103-114, Vol. 19, Feb 2000）」およびH. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt著 「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images（Proceedings of the ５th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002）」に記載されている。
【０００６】
アトラスマッチングは、レントゲン技師の報告において識別された問題領域と関連して解剖学的名称を定めるために使用される。異なった患者とのマッチングによって、患者データの大きなスケールでの比較が可能になる。同じ患者内での気道−動脈マッチングは気管支鏡案内のために使用される。これに対する例は、B. Geiger, A.P. Kiraly, D.P. Naidich, C.L. Novak著「Virtual Bronchoscopy of Peripheral Nodules using Arteries as Surrogate Pathways (SPIE Physiology, Function, and Structure From Medical Images, Vol. 5746,2005)」およびB. Geiger, A.P. Kiraly, D.P. Naidich, C.L. Novak, 「System and Method for Endoscopic Path Planning（米国特許出願公開第２００５０１０７６７９号明細書）」 に記載されている。同じ患者内の気道−動脈マッチングは、改善された動脈または気道セグメント化に対する基礎としても用いられる。この例は、T. Buelow, R. Wiemker, T. Blaffert, C. Lorenz, S. Renisch著 「Automatic Extraction of the Pulmonary Artery Tree from Multi-Slice CT Data( SPIE Physiology, Function, and Structure Froｍ Medical Images, pp. 730-740, Vol. 5746,2005）」に記載されている。
【０００７】
ツリーマッチングアルゴリズムは、入力としてツリー構造を必要とする。この構造は、分岐点を通じて相互に接続された一連の分枝としてツリーをあらわしている。幾つかの既知のアルゴリズムが、このツリー構造を得るために使用される。これは殊に追跡、セグメント化およびスケルトン化を含む。この例は、 A.P. Kiraly, J.P. Helferty, E.A. Hoffman, G. McLennanおよび W.E. Higgins著 「3D Path Planning for Virtual Bronchoscopy（IEEE Trans. on Medical Imaging, pp. 1365-1379, Vol. 23, Nov 2004）」に記載されている。ツリー構造が得られると、マッチングアルゴリズムは構造およびそこに含まれているあらゆるデータに直接的に作用する。気道、動脈および静脈等の非環ツリー構造体は親分枝および子分枝の固有ヒエラルキーを含む。このようなツリーは、有向性、かつ分岐グラフとして見られる。
【０００８】
同じ患者からの気道−気道ツリーをマッチングさせる幾つかのアプローチがある。アプローチの例はC. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni著「Tracking 3-D Pulmonary Tree Structures （Mathematical Methods in Biomedical Image Analysis, pp. 160-169,1996）」およびJ. Tschirren, K. Palagyi, J.M. Reinhardt, E.A. Hoffmanおよび M. Sonka著「Segmentation, Skeletonization, and Branchpoint Matching - A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees（ SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031,2003)」に記載されている。
【０００９】
さらに、気管支ツリーの自動化された解剖学的ラベリングに対する幾つかのアプローチがある。このアプローチの例は、K. Mori, J.-I. Hasegawa著「Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System （IEEE Trans. on Medical Imaging, pp. 103-114, Vol. 19, Feb 2000）」 およびH. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt著「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images（Proceedings of the 5th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002）」に記載されている。
【００１０】
近年のアルゴリズムは一般的に、分岐部点内のフィーチャのセットを結びつける。このアルゴリズムの例は、C. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni著「Tracking 3-D Pulmonary Tree Structures（ Mathematical Methods in Biomedical Image Analysis, pp. 160-169,1996）」および J. Tschirren, K. Palagyi, J.M. Reinhardt, E.A. Hoffmanおよび M. Sonka著「Segmentation, Skeletonization, and Branchpoint Matching - A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees（ SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031,2003）」および A.C.M. Dumay, R. v.d. Geest, JJ. Gerbrands, E. Jansen, Johan H.C. Reiber著「 Consistent Inexact Graph Matching Applied to Labelling Coronary Segments in Arteriograms（ Proc. l1th IAPR, pp. 439-446, Vol. III, 1992）」 および K. Haris, S.N. Efstratiadis, N. Maglaveras, C. Pappas, J. Gourassas, G. Louridas著「Model-based Morphological Segmentation and Labeling of Coronary Angiograms（ IEEE Trans, on Medical Imaging, pp.1003-1015, Vol 18, Oct 1999)」に記載されている。
【００１１】
これらのアルゴリズムは、関連したグラフ内で最大クリークを見つけるような一般的なグラフマッチング方法を使用する。この例は、M. Pelillo, K. Siddiqi, S.W. Zucker著 「Matching Hierarchical Structures Using Association Graphs（IEEE Trans. on Pattern Analysis and Machine Intelligence, pp. 1105-1120, Vol. 21, Nov 1999）」およびH. Kitaoka, Y. Park, J. Tschirren, J. Reinbardt著 「Automated Nomenclature
Labeling of the Bronchial Tree in 3D-CT Lung Images （Proceedings of the 5 th
International Conference on Medical Image Computing and Computer Assisted
Intervention-Part II, pp. 1-11, Sep 2002）」に記載されている。 これらのアルゴリズムが、ファジィ割り当を緩和することによってグラフマッチングを行ってよい。この例は、S. Medasani, R. Krishnapuram, Y.S. Choi著 「Graph Matching by Relaxation of Fuzzy Assignments （ IEEE Trans. on Fuzzy Systems, pp. 173-182, Vol. 9, Feb 2001)」に記載されている。
【００１２】
上述したツリーマッチングアルゴリズムはグラフマッチング技術に頼っており、単独のアプリケーションに焦点を合わせている。グラフマッチング技術は、確固たる理論的背景を有しているが、現実世界の医療アプリケーションにとって最適な選択ではないだろう。ここでは誤ったまたは欠落した分枝および相違、および解剖分析における変化が生じ得る。さらに、上述したマッチング方法はツリーのヒエラルキー構造を使用して、分枝−分枝レベルでのマッチングを行う。これらの方法はツリー構造を、分枝データから計算されたフィーチャを有するノードの連続としてみなすので、誤った枝はこの方法の効力を低減させてしまう。さらに、これらの方法のうちの幾つかは、各ツリー構造に対して一致された開始点を必要とし、これによってこの情報が得られない時にはこれらの方法は使用できなくなってしてしまう。この要求によって、より正確な結果のためにツリーの予備的なレジストレーションを行うことも必要になる。さらに、多くの上述した方法は、これらの制限を回避するために手動で作成されるまたは編集されることを必要とする、ツリー構造を必要とする。
【特許文献１】米国特許出願公開第２００５０１０７６７９号明細書
【非特許文献１】Ｋ. Mori, J.-I. Hasegawa著「Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System」 IEEE Trans. on Medical Imaging, pp. 103-114, Vol. 19, Feb 2000
【非特許文献２】H. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt著 「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images」Proceedings of the ５th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002
【非特許文献３】B. Geiger, A.P. Kiraly, D.P. Naidich, C.L. Novak著「Virtual Bronchoscopy of Peripheral Nodules using Arteries as Surrogate Pathways 」SPIE Physiology, Function, and Structure From Medical Images, Vol. 5746,2005
【非特許文献４】T. Buelow, R. Wiemker, T. Blaffert, C. Lorenz, S. Renisch著 「Automatic Extraction of the Pulmonary Artery Tree from Multi-Slice CT Data」 SPIE Physiology, Function, and Structure Froｍ Medical Images, pp. 730-740, Vol. 5746,2005
【非特許文献５】A.P. Kiraly, J.P. Helferty, E.A. Hoffman, G. McLennanおよび W.E. Higgins著 「3D Path Planning for Virtual Bronchoscopy」IEEE Trans. on Medical Imaging, pp. 1365-1379, Vol. 23, Nov 2004
【非特許文献６】C. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni著「Tracking 3-D Pulmonary Tree Structures 」Mathematical Methods in Biomedical Image Analysis, pp. 160-169,1996
【非特許文献７】J. Tschirren, K. Palagyi, J.M. Reinhardt, E.A. Hoffmanおよび M. Sonka著「Segmentation, Skeletonization, and Branchpoint Matching - A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees」 SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031,2003
【非特許文献８】K. Mori, J.-I. Hasegawa著「Automated Anatomical Labeling of the Bronchial Branch and Its Application to the Virtual Bronchoscopy System （IEEE Trans. on Medical Imaging, pp. 103-114, Vol. 19, Feb 2000）」
【非特許文献９】H. Kitaoka, Y. Park, J. Tschirren, J. Reinhardt著「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images（Proceedings of the 5th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002）」
【非特許文献１０】C. Pisupati, L. Wolff, W. Mitzner, E. Zerhouni著「Tracking 3-D Pulmonary Tree Structures（ Mathematical Methods in Biomedical Image Analysis, pp. 160-169,1996）」
【非特許文献１１】J. Tschirren, K. Palagyi, J.M. Reinhardt, E.A. Hoffmanおよび M. Sonka著「Segmentation, Skeletonization, and Branchpoint Matching - A Fully Automated Quantitative Evaluation of Human Intrathoracic Airway Trees（ SPIE Medical Imaging 2003: Physiology and Function: Methods, Systems, and Applications, pp. 187-194, Vol. 5031,2003）」
【非特許文献１２】A.C.M. Dumay, R. v.d. Geest, JJ. Gerbrands, E. Jansen, Johan H.C. Reiber著「 Consistent Inexact Graph Matching Applied to Labelling Coronary Segments in Arteriograms」 Proc. l1th IAPR, pp. 439-446, Vol. III, 1992
【非特許文献１３】K. Haris, S.N. Efstratiadis, N. Maglaveras, C. Pappas, J. Gourassas, G. Louridas著「Model-based Morphological Segmentation and Labeling of Coronary Angiograms」 IEEE Trans. on Medical Imaging, pp.1003-1015, Vol 18, Oct 1999
【非特許文献１４】M. Pelillo, K. Siddiqi, S.W. Zucker著 「Matching Hierarchical Structures Using Association Graphs」 IEEE Trans. on Pattern Analysis and Machine Intelligence, pp. 1105-1120, Vol. 21, Nov 1999
【非特許文献１５】H. Kitaoka, Y. Park, J. Tschirren, J. Reinbardt著 「Automated Nomenclature Labeling of the Bronchial Tree in 3D-CT Lung Images 」 Proceedings of the 5 th International Conference on Medical Image Computing and Computer Assisted Intervention-Part II, pp. 1-11, Sep 2002
【非特許文献１６】S. Medasani, R. Krishnapuram, Y.S. Choi著 「Graph Matching by Relaxation of Fuzzy Assignments 」 IEEE Trans. on Fuzzy Systems, pp. 173-182, Vol. 9, Feb 2001
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明の課題は、従来技術の欠点を回避するパスベースのツリーマッチングのための方法およびシステムを提供することである。
【課題を解決するための手段】
【００１４】
上述の課題は、物理的オブジェクトまたはモデルを表すツリー状構造を収集し；第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し、前記パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；当該類似測定に基づいて前記パスが一致しているか否かを定める、ことを特徴とする、ツリーマッチングのための方法によって解決される。さらに上述の課題は、第１のツリー状構造および第２のツリー状構造からパスを収集し；第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較し；第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最も一致しているのかを、当該類似測定に基づいて定める、ことを特徴とする、ツリー状構造のパスを別のツリー状構造にマッチングさせるための方法によって解決される。さらに上述の課題は、プログラムを格納するためのメモリデバイスと；当該メモリデバイスと通信するプロセッサとを含み、ここでこのプロセッサプログラムで動作し：物理的オブジェクトまたはモデルを表すツリー状構造を収集し；第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し：前記パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；当該類似測定に基づいて前記パスが一致しているか否かを定める、ツリーマッチングのためのシステムによって解決される。さらに、上述の課題は、ツリー状構造のパスを別のツリー状構造にマッチングさせるためのシステムであって：プログラムを格納するためのメモリデバイスと；当該メモリデバイスと通信するプロセッサとを含み、ここでこのプロセッサはプログラムで動作し：第１のツリー状構造および第２のツリー状構造からパスを収集し；第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較し；第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最も一致しているのかを、当該類似測定に基づいて定める、ことを特徴とする、ツリー状構造のパスを別のツリー状構造にマッチングさせるためのシステムによって解決される。
【発明を実施するための最良の形態】
【００１５】
発明の概要
本発明の１つの実施形態では、ツリーマッチング方法は以下のステップを含む、すなわち：物理的オブジェクトまたはモデルをあらわすツリー状構造を収集する；第１のツリー状構造からのパスおよび第２のツリー状構造からのパスを抽出する；これらパスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較する；この類似測定に基づいてこれらのパスが一致しているか否かを定める。
【００１６】
この方法はさらに、ツリー状構造の各パスがマッチングするまたは除外されるまで、抽出ステップ、比較ステップおよび確定ステップを繰り返すことを含む。
【００１７】
パスは、１つまたは２つのツリー状構造のヒエラルキーに従って比較される。この方法はさらに以下のステップを含む。すなわち：他のパスの類似測定に基づいてパスが一致しているか否かを定める；マッチされたパスを記録するためのマッチングマトリクスを作成する；最も一致しているパスが既に別のパスと一致している場合には、次の最適一致パスにパスをマッチングさせるための確率マトリクス（Probability matrix）を作成する。
【００１８】
この方法はさらにパスを比較する前にツリー状構造をアライメントすることを含む。
【００１９】
ツリー状構造は気道、動脈または静脈である。ツリー状構造は、追跡、セグメント化、またはスケルトン化（細線化）によって得られる。パスはセグメント化、中心線抽出、または直接的にツリー状構造から抽出される。
【００２０】
パスの抽出は、複数のパスのうちの１つのパスを、複数のパス間の比較に対する基礎として選択することを含む。長いパスのサブセクションにマッチする短いパスが、複数のパス間の比較に対する基礎として選択される。類似測定はパスの距離フィーチャ、角度フィーチャ、距離分散（distance variance）フィーチャ、またはこれらのフィーチャの数値的な組み合わせである。
【００２１】
本発明の他の実施形態では、ツリー状構造のパスを別のツリー状構造とマッチングさせるための方法は次のことを含む。すなわち：第１のツリー状構造および第２のツリー状構造からパスを収集する；第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較する；第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最も一致しているのかを、この類似測定に基づいて定める。
【００２２】
この方法はさらに、第１および第２のツリー状構造をマッチさせるために、収集ステップ、比較ステップおよび確定ステップを繰り返すことを含む。
【００２３】
第１および第２のツリー状構造のパスは、１つまたは２つのツリー状構造のヒエラルキーに従って比較される。
この方法はさらに以下のステップを有する。すなわち：マッチされたパスを記録するためのマッチングマトリクスを作成する；最も一致パスが既に別のパスに一致している場合には、次の最適一致パスを可能にするために、パスをマッチングさせるための確率マトリクスを作成する。
【００２４】
本発明のさらに別の実施形態では、ツリーマッチングのためのシステムは以下のものを含む。すなわち：プログラムを格納するためのメモリデバイスと；このメモリデバイスと通信するプロセッサを含み、このプロセッサは以下のプログラムで動作する、すなわち：物理的オブジェクトまたはモデルをあらわすツリー状構造を収集する；第１のツリー状構造からのパスおよび第２のツリー状構造からのパスを抽出する；これらのパスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較する；この類似測定に基づいてこれらのパスが一致しているか否かを定める。
【００２５】
このプロセッサはさらに、ツリー状構造の各パスがマッチするまたは除外されるまで抽出ステップ、比較ステップおよび確定ステップを繰り返すプログラムコードで動作する。
【００２６】
パスは１つまたは２つのツリー状構造のヒエラルキーに従って比較される。
このプロセッサはさらに、以下のプログラムコードで動作する。すなわち：他のパスの類似測定に基づいてこれらのパスが一致しているか否かを定める；マッチされたパスを記録するためのマッチングマトリクスを作成する；最も一致しているパスが既に別のパスに一致している場合にパスを次の最適一致パスにマッチングさせるための確率マトリクスを作成する。
【００２７】
本発明のさらに別の実施形態では、ツリー状構造のパスを別のツリー状構造とマッチングさせるためのシステムは以下のものを含む。すなわち：プログラムを格納するためのメモリデバイスと；このメモリデバイスと通信するプロセッサとを含み、ここでこのプロセッサは以下のプログラムで動作する。すなわち：第１のツリー状構造および第２のツリー状構造からパスを収集する；第１のツリー状構造および第２のツリー状構造からのパスに対する類似測定を計算することによって、第１のツリー状構造のパスを第２のツリー状構造のパスと比較する；この類似測定に基づいて、第２のツリー状構造のどのパスが、第１のツリー状構造のパスと最も一致するかを定める。
【００２８】
このプロセッサはさらにプログラムコードで作動し、第１および第２のツリー状構造がマッチするまで、収集ステップ、比較ステップおよび確定ステップを繰り返す。
【００２９】
第１および第２のツリー状構造のパスは、１つまたは２つのツリー状構造のヒエラルキーに従って比較される。
【００３０】
このプロセッサはさらにプログラムコードで作動し：マッチされたパスを記録するためのマッチングマトリクスを作成する；最も一致しているパスが既に別のパスにマッチングしている場合に次の最適一致パスを可能にするために、パスをマッチングさせるための確率マトリクスを作成する。
【００３１】
上述の特徴は代表的な実施形態のものであり、本発明の理解を補助するために提示されている。これらは特許請求の範囲によって規定される本発明を限定するもの、また特許請求の範囲に相当するものを限定するものと考えられるべきではない。従って、この特徴の概要は相当事項を確定するための方向性を定めるものと考えられるべきではない。本発明のさらなる特徴は以下の説明、図および特許請求の範囲から明らになるであろう。
【実施例】
【００３２】
実施例の詳細な説明
本発明の実施形態に従ったパスベースツリーマッチングに対する一般的な枠組みは、ツリー構造から導かれたパスを他のツリー構造からのパスと比較することを伴う。これはパスの逐点（point-by-point）比較を行うことによって実行される。ここではこのパス間の類似性をあらわすフィーチャが使用され、これらのフィーチャに基づいて数値的な値が得られる。その後この数値的値は、これらのパスが一致したのか否かを定めるために使用される。
【００３３】
パスベースのツリーマッチング方法はグラフマッチングから独立している。これは完全なパスの逐点比較に基づいているので分岐点から独立しており、従って誤った分枝および欠落した分枝に対して非常に強い。このパスベースのツリーマッチング方法は不規則なツリー構造を支持する。これは例えば複数の親を有する分枝または不完全なセグメント化および中心線抽出によって生じる平らなループである。
【００３４】
これらのフィーチャはヒエラルキーを回避することによって得られるが、階層的な拘束を伴うツリー全体のマッチングは粗い方法で起こり得る。これは例えば、本発明の実施形態に相応する分枝拘束を用いることによって起こり得る。付加的に、パスベースツリーマッチング方法は多対一パスマッピングを可能にするが、一対一パスマッピングがマッチングマトリクスによって強化される。さらにパスベースツリーマッチング方法は、一般的なグラフマッチングアルゴリズムよりも多くの処理時間を必要とするが、実行時間を低減させるために使用される種々の最適化が考察される。
【００３５】
本発明の実施形態に相応する、パスベースツリーマッチングのためのシステムおよび方法を以下で詳細に説明する。
【００３６】
図１は、本発明の実施形態に相応した、パスベースツリーマッチングのためのシステム１００をあらわすブロックダイヤグラムである。図１に示されているようにシステム１００は収集デバイス１０５、ＰＣ１１０およびオペレータコンソール１１５を含む。ここでこのオペレータコンソールはワイヤ接続された、またはワイヤレスのネットワーク１２０を介して接続されている。
【００３７】
収集デバイス１０５は、磁気共鳴（ＭＲ）結像デバイス、コンピュータトモグラフィ（ＣＴ）結像デバイス、ヘリカルＣＴデバイス、陽電子放射型コンピュータ断層撮影（ＰＥＴ）デバイス、シングルフォトンエミッションコンピューテッドトモグラフィ（ＳＰＥＣＴ）デバイス、ハイブリッドＰＥＴ−ＣＴデバイス、ハイブリッドＳＰＥＣＴ−ＣＴデバイス、二次元または三次元蛍光透視デバイス、二次元、三次元または四次元超音波（ＵＳ）結像デバイス、またはｘ線デバイスであってよい。さらに、収集デバイスはマルチモデルまたはハイブリッド収集デバイスであってよい。これは例えばＰＥＴモード、ＳＰＥＣＴモードまたはＭＲモードで画像を収集することができる。
【００３８】
ＰＣ１１０は、ポータブルまたはラップトップコンピュータ、医療診断結像システムまたはPicture archiving communication system（ＰＡＣＳ）データ管理ステーションであってよく、ＣＰＵ１２５およびメモリ１３０を含む。これは入力デバイス１５０および出力デバイス１５５と接続されている。ＣＰＵ１２５は、パスベースツリーマッチングモジュール１４５を含む。これは、以降で図２〜６を参照して考察するパスベースツリーマッチングを実施するための１つまたは複数の方法を含んでいる。ＣＰＵ１２５内に示されているが、パスベースツリーマッチングモジュール１４５はＣＰＵ１２５の外側に配置されていてもよい。
【００３９】
メモリ１３０は、ランダムアクセスメモリ（ＲＡＭ）１３５およびリードオンリーメモリ（ＲＯＭ）１４０を含む。メモリ１３０は、データベース、ディスクドライブ、テープドライブ等、またはその組み合わせを含み得る。ＲＡＭ１３５はデータメモリとして機能する。これはＣＰＵ１２５内のプログラムの実行の間に使用されるデータを格納し、ワーク領域として使用される。ＲＯＭ１４０は、ＣＰＵ１２５内で実行されるプログラムを格納するためのプログラムメモリとして機能する。入力部１５０は、キーボード、マウス等によって構成されており、出力部１５０は液晶ディスプレイＬＣＤ、ＣＲＴディスプレイまたはプリンタによって構成される。
【００４０】
システム１００の動作はオペレータコンソール１１５からコントロールされる。このオペレータコンソールは例えばキーボードであるコントローラ１６５およびディスプレイ１６０を含む。オペレータコンソール１１５はＰＣ１１５および収集デバイス１０５と通信し、収集デバイス１０５によって集められた画像データがＰＣ１１０によってレンダリングされ、ディスプレイ１６０上で見られる。ＰＣ１１０は、オペレータコンソール１１５がなくても、収集デバイス１０５によって供給された情報を処理し、表示することができるものと理解されたい。これは例えばコントローラ１６５およびディスプレイ１６０によって実行される特定のタスクを行う、入力１５０および出力１５５デバイスを用いることで行われる。
【００４１】
オペレータコンソール１１５はさらに、あらゆる適切な画像レンダリングシステム／ツール／アプリケーションを含んでよい。これは、収集されたイメージデータセットのデジタルイメージデータ（またはその一部）を処理し、イメージを作成し、ディスプレイ１６０上に表示する。より詳細には、画像レンダリングシステムは、医療画像データをレンダリングし、視覚化するアプリケーションであり、汎用コンピュータワークステーションまたは専用コンピュータワークステーションで実行される。ＰＣ１１０も上述した画像レンダリングシステム／ツール／アプリケーション含み得ることを理解されたい。
【００４２】
図２は、本発明の実施形態に従った、パスベースツリーマッチング方法の動作を表すフローチャートである。
【００４３】
図２に示されているように、物理的オブジェクトまたはモデルをあらわすツリー状構造が収集される（２１０）。
【００４４】
パスベースのツリーマッチング方法ではツリーＴは、二重リンク有向性分枝Ｂ＝（ＳＢ、ＰＢ、ＣＢ）の集合である。これは等距離の部位（Site）のセットＳＢを含み、自身の親ＰＢ（例えば気道または動脈内の１つ）にリンクし、その子ＣＢ（例えば気道または動脈に２つまたはそれより多い）にリンクする。親を有していない分枝ＰＢ＝φはルート分枝と定められ、またいかなる子も有していない分枝ＣＢ＝φは終端分枝と定められる。部位のセットＳＢは、順序付けされた等距離の三次元座標のベクトルである。これは開始部位として定められた第１の部位と、ＳＢの終端部位と定められた最後の部位を伴う。さらに、分枝は常に親または子であると見なされているので、ツリーは固有のヒエラルキーを含む。ループがないと想定すると、各分枝は特定の世代番号に属する。ルート分枝は世代０で、このルートの子は世代１である、等である。
【００４５】
ツリー状構造は、気道、動脈、静脈および管路系等のあらゆる分岐管状構造である。この分岐管状構造は例えば収集デバイス１０５を使用することによって得られる。これは例えばＣＴスキャナーであり、患者の胸部をスキャンして、肺に関する、一連の二次元画像切片を作成する。その後、この肺の二次元画像切片が組み合わされ、三次元画像が作成される。
【００４６】
肺に加えて、分岐管状構造は体のあらゆる部分から収集されることを理解された。これは例えば肝臓、脚または脳である。さらに、ＭＲＩデバイスまたは他のあらゆる結像デバイスから得られた他のタイプのデータが、本発明の実施形態に相応して使用されてよい。これらの結像デバイスは収集デバイス１０５の種々の変更に関連する。
【００４７】
ツリー状構造が得られると、各構造からパスが抽出される（２２０）。
【００４８】
パスは、１つまたは複数の直接的にリンクされた分枝の組み合わせである。これは、第１の分枝内のあらゆる部位で始まり、関連する最後の分枝のあらゆる部位で終了する。完全なパスは、ルート分枝のルート部位で始まり、あらゆる終端分枝の終端部位で終わるパスとして定められる。このヒエラルキーの故に、あらゆる完全なパスは常にルート分枝を含む。このパスはあらゆるセグメント化、中心線抽出またはキャプチャー方法によって抽出される。
【００４９】
各ツリー状構造からパスを抽出した後、これらのパスは、パス間の類似測定を計算することによって相互に比較される（２３０）。この測定は関数を使って定められる。この関数は、１つのパスからの点を他のパス内の点と比較する。ここでパスのうちの１つが、比較のための基礎として選択される。
【００５０】
パス比較のための２つのパスのうちのより短いほうを選択することはより効果的であることを理解されたい。なぜなら、短いほうのパスは長いほうパスのサブセクションにマッチすると想定されるからである。これは等しい対応部分を有していない部位毎の（site-by-site）比較における点を使用することを回避する。しかし、長いほうのパスを使用することも可能であり、このパスベースツリーマッチング方法の使用を制限するものではない。例えば、完全な気道パスがより隣接して始まるルート部位を有し、動脈パスがおそらくさらに周囲へ向かって延在するであろう場合にも、周辺の気管支に対して動脈をマッチングさせることが可能である。
【００５１】
基礎またはオリジナルツリー内の開始および終了部位を選択した後に、全ての部位を、中間的に１つの構造体に結合させることによってオリジナルパスが作成される。ここでこの構造体はヒエラルキー情報を有していない。すなわち、親および子分枝の全ての概念が除去され、一連の部位が残される。
【００５２】
幾つかの異なった類似性フィーチャがパスを比較するのに使用される。３つの例が含まれる。すなわち：距離、角度および分散である。距離フィーチャはパス間のオフセットをあらわし、角度フィーチャはパス方向における差を示し、分散フィーチャはパス間のオフセットの変化を計算する。他のフィーチャも、パスを比較するために使用可能である。最適なフィーチャの選択はアプリケーションに依存するが、上述したフィーチャは、一般的なケースにおいて良好に機能する。他の数値的なフィーチャを容易にパスベースツリーマッチング方法に組み入れることができる。
【００５３】
距離フィーチャは比較されるパス間の平均二乗された距離をあらわす。これは、オリジナルパスの各部位と、比較パス内のその最も近い部位の間の、二乗された距離を要約することによって計算される。その後、オリジナルパスの部位の数によって、この合計が除算される。核分枝の全ての部位が等しい距離に位置しているので、部位の数はパスの長さに等しい。
【００５４】
【数１】
【００５５】
ここでＰｉ＝オリジナルパスの部位ｉであり、Ｃ（Ｐｉ| q）＝Ｐｉに対する比較構造のパスｑ内の最も近い部位である。
【００５６】
角度フィーチャは、比較される２つのパスの方向の平均差異を見積もる。分枝の直線再現は使用されないので、各部位でのパスの方向は僅かに異なり得る。正確な差異を計算するために、オリジナルパスのどの部位が、比較分枝のどの部位に相応するのかを知る必要がある。この関係は事前には知られていないので、オリジナルパスの各部位での正接の方向と、比較パスの最も近い部位での方向の間の差異が使用される。その後、合計がオリジナルパスの点の数によって除算される。
【００５７】
【数２】
【００５８】
ここで
＝オリジナルパスの部位ｉでの方向であり、
＝Ｐｉに対する比較構造のパスｑ内の最も近い部位での方向である。
【００５９】
分散フィーチャは、上述した距離フィーチャにわたる分散である。
【００６０】
【数３】
【００６１】
ここでＰｉ＝オリジナルパスの部位ｉであり、Ｃ（Ｐｉ| q）＝Ｐｉに対するパスｑ内の最も近い部位であり、ｄは平均二乗された距離である。
【００６２】
これらのフィーチャが計算されると、パスが一致しているか否かが定められる（２４０）。
【００６３】
これは例えば、これらのフィーチャを比較ツリーの完全なパスに加えることによって、実行される。これによってオリジナルパスに関する距離ベクトルが得られる。このベクトルを単独値に変換するために、ノルム化されたコンビネーション（Normed combination）と称される、シンプルなコンビネーション方法が使用される。ノルム化されたコンビネーションは、各成分の変化性を考慮する。ここで高い変化性を伴う成分は、低い変化性を伴う成分よりも低い重みを受け取る。これは各成分をその分散で再スケーリングすることによって得られる。距離ベクトル
のノルムは
【数４】
に等しい。
【００６４】
ここで、
は分散のマトリクスであり、ここでメインダイアゴナルおよびゼロ値およびあらゆるほかのところでの分散を有する。結果として、比較ツリーの各完全なパスは単独値を有する。これはオリジナルパスへのその類似性をあらわす。ここで、もっとも小さい値を有するパスが最適一致になる。等しい小さい値を複数のパスが有する場合には、そのうちの１つが無作為に選択される、またはより進歩した分析が、現在のマッチとの調和に基づいて実施される。
【００６５】
このパスベースツリーマッチング方法を使用して完全なツリーがマッチする場合には、多対一マッチングが生じる。なぜならマッチングはパス毎に行われ、現在のマッチ割当を考慮しないからである。換言すれば、オリジナルツリー内の各パスが、比較ツリー内のパスに対して１つの一致しか有していなくても、比較ツリー内の所与のパスは、オリジナルパス内の１つより多いパスと一致される。一対一マッチングは、最初に完全な距離マトリクスを計算すること、および次にこのマトリクスに基づいてベストマッチを選択することによって得られる。
【００６６】
２つのパスが一致しているので、種々のラインベースフィーチャが使用されて、類似測定値が定められる。この類似測定値は、２つの三次元曲線間の変換に基づいてよい。曲率および一連の点の関数のあらゆる他の尺度等のフィーチャも使用可能である。例えば高い次数の多項式がパスにフィットし、その方程式が比較に使用される。さらに、これらのフィーチャの組み合わせが使用され、パスベースツリーマッチング方法の強さが高められる。
【００６７】
全体的なツリー構造をマッチングさせるためのパスベースツリーマッチング方法の使用の記述が続く。例えば、一致が所望されているオリジナルツリー内でパスを手動で示す代わりに、各完全なパスが自動的に選択され、他のツリー内の他の完全なパスに一致される。これは、ツリー内の全てのパスが一致されるまで各可能な完全なパスに対して、繰り返される（２５０）。
【００６８】
しかし、計算されるフィーチャ、特に距離フィーチャを収納するために、ツリー構造全体がマッチングされる前に、ツリー構造の幾つかの種類のアライメントが実施される必要があることを理解されたい。このアライメントは、多くのアプリケーションにおいて、ツリー構造の主要分枝点を用いることで実行される。このアライメントは自動的に行われ得る。気道−動脈マッチングでは、ルート部位における違い（例えば、気道に対する気管および動脈に対する心臓）のために、このアライメントプロセスが可能でないことがある。
【００６９】
角度および距離変動等の他のフィーチャはパス位置からより独立しているので、ツリー構造はアライメントされる必要がない。なぜなら、これらはアフィン変換に対してそれほど敏感ではない、または不変だからである。これらのフィーチャはおそらく、適切なマッチングのために付加的な拘束を必要とするであろう。なぜならこれらは多くの可能な一致を可能にするからである。例えば、これらのフィーチャは、左肺および右肺内の気道パスを、第２のツリーの右肺内のパスに一致させることを可能にする。従って、このようなことを起こるのを阻止するために付加的な拘束が必要とされる。
【００７０】
一対一マッチング拘束がマッチングマトリクスを使用することによって付加される。パス対パスマッチングが多対一マッピングを生じさせるので、一対一に対する一致を拘束する目的のために、一致のマトリクスが作成される。このマトリクスは、列内に挙げられた第１のツリーの全ての可能なパスを含む。また、第２のツリーの全ての可能なパスが行内に挙げられている。マトリクス内の各エントリは、２つのパス間の一致の尺度を含む。全ての距離値の絶対的な最小距離の反復した選択し、上述したようにタイを処理し、一致したとして関連するパスにラベリングし、これらをさらなるマッチングに対して無視することによって、一対一一致拘束が強制的に実施される。
【００７１】
オリジナルパスは比較ツリー内に同等なものを有していないので、一対一マッチング拘束は適切な結果を得ずに、早期の一致が不正確に行われた場合には、誤ったラベリングの連鎖に終わってしまう。従って、確率マトリクスが導入される。この確率マトリクスは一対一一致を作成することを試みるが、単独のケースでは多対一マッチングを可能にもする。従って一致されたパスは、さらなるマッチに対して完全には無視されない。
【００７２】
例えば、最も一致しているパスが既に一致されている場合には、その相違測定値が僅かにのみ高い、次のベストの、一致されていないパスがベストマッチよりも高い可能性になる。このような要求を満たすさらなるパスが見つけられない場合には、既に一致しているパスがベストマッチとしてラベリングされ、この一致の確率およびこのパスの既に存在している一致の確率が割り当てられた一致の数によって低減される。このマッチングマトリクスを用いることによって、一対一マッチングが改善される。これは先行の一致のスコアが特定の一致に与えられることが阻止されることによって行われる。このマトリクスは、この枠内で拘束が形成される１つの方法でしかない。
【００７３】
一致されたパスが与えられると、これらのパス内のどの分枝が対応しているのかが定められる。従って分枝対分枝マッチングはこの結果から導き出される。これは、一致されたパスを介して一致されている、各分枝または一連の点に対して一致票数を作成することによって実行される。より頻繁に一致される分枝が、最初に一致される。例えば、n個の一致されたパスが暗に同じ２つの分枝に一致する場合、この分枝一致はｎ票数を得る。この投票スキーマは、どの分枝がともに一致しているのかを定めるのに使用されるだけでなく、所与の分枝一致が得た票の数、および第２の競争相手が得た票の数に基づいて信頼度を定めるのにも使用される。この信頼度ファクターは、さらなる処理ステップに影響を与えるために使用される。
【００７４】
例えば、レジストレーション方法において、より大きな信頼度を有する一致はレジストレーションモデルに対してより大きい影響力を有する。低い信頼性領域もユーザに提供可能であり、これによって迅速な半自動インタフェースが可能になる。付加的に、一連の一が一致されるので、オリジナルツリー内の１つの分枝が他のツリー内の２つの分枝に一致される。誤った分枝が正しい分枝を２つの部分に分ける場合にこれが起こり得る。
【００７５】
分枝マッチングの使用は、ヒエラルキー拘束も可能にする。高い信頼度でマッチングされた２つの分枝は、次のことを課す。すなわち、これらの分枝を有する全ての他の可能なパスがこれらの分枝の部位で一致しなければならないことを課す。付加的に、１つの分枝が一致すると、反復プロセスが行われ、一致された分枝の終端がルート部位として機能し、プロシージャが繰り返される。この反復方法はヒエラルキー拘束の使用を可能にする。また同時にグラフマッチングを基本とした方法の欠点を同じく回避することができる。
【００７６】
パスベースツリーマッチング方法は、一般的なグラフマッチングアルゴリズムより長い処理時間を必要とするので、以下で説明する幾つかの最適化がこの方法の速度を高めるために使用される。
【００７７】
第１に、比較動作はそれぞれ独立しているので、パスベースツリーマッチング方法は多重インプリメンテーションに対して開放されている。これによってデュアル・プロセッサ上で潜在的に速度が２倍になり、より多くのプロセッサを有するプロセッサ上でさらに速くなる。第２に、遠いまたは非常に不所望なパス一致が容易に識別され、よりコストのかかる比較ステップが回避される。第３に、最適なフィーチャ組み合わせの識別の後、各比較ペアに対する個々のフィーチャの計算が最適化され、各フィーチャセットに対する計算時間が単独フィーチャの目下の計算時間よりも長くなることがない。フィーチャはポイントベースなので、計算時間は、パスを定める部位の数に依存する。幾つかのケースでは、最適な結果に達するための部位の間の必要な距離が増加する。これは、各フィーチャ計算に対する計算時間を直接的に低減させる。
【００７８】
他の最適化では、現在の一致に基づくマッチングマトリクスおよびヒエラルキー拘束が、どのパスが比較されるべきでないのかを予測するのに使用される。従って、従来のグラフマッチングのほうが本来は速いが、これらの最適化の使用はパスベースツリーマッチング方法に必要とされる時間を格段に低減させる。しかし、単独パスのマッチのみを必要とする気管支鏡プランニング等のアプリケーションにおいては、パスベースのツリーマッチング方法はグラフマッチングアプローチより性能が優れている。なぜなら全体的なマッチングプロセスが行われる必要がないからである。
【００７９】
全ての分岐を可能な一致であると考慮しない場合の速度差の例を次に挙げる。１つのフィーチャを使用して、４４のパスを有するツリーを、６６のパスを有するツリーにマッチングさせるための時間は４分２８秒である。各オリジナルパスが全ての比較パスと比較されるので、このフィーチャは約２９００回計算され、これは９２．２ｍｓの平均処理時間で行われる。これは各パス内の部位の数に依存する。例えば右／左の上葉支と右／左の体幹中間との間の分岐点の事前識別は、オリジナルツリーを４つの部分に分ける。これは約４倍の速度上昇になる。一般的な距離等の他の比較フィーチャも、どのパスが比較される必要がないかを定めるために使用される。
【００８０】
このパスベースのツリーマッチング方法は、気道−気道マッチングおよび気道−動脈マッチングで、優秀な結果を伴ってテストされている。最初の妥当性確認のために、気道ツリーの一部は合成して作成された比較ツリーに一致されている。人工的なツリーは、基礎としてオリジナルのデータを使用し、その後このデータを修正することによって作成される。はじめに、パラメータ特有の領域内のランダムオフセットが各部位に加えられ、これらのツリーの間のポジショニング偏差がシミュレートされる。次にパラメータ化された変化を伴うガウシアン分布ノイズが部位に加えられ、呼吸のような他の可能な差の源がシミュレートされる。この技術を使用して、マッチングに対するフィーチャの頑強性に対するノイズとオフセットの影響が試験される。５０００より多くのパス一致の妥当性確認結果が、図３に示されている。図３に示された結果を生じさせる実験は、３つのフィーチャD（距離）、Ａ（角度）、Ｖ（分散）、Ｅｕｃ（ユークリッド）およびＮｏｒｍ（ノルム）の妥当性確認を、オフセットおよびノイズに対する７５個の異なったパラメータセッティングを有する組み合わせで含む。ここでこれらのマッチング結果は、グラウンドトルースと比較され、正しい分類の割合が定められる。
【００８１】
それぞれが単独で加えられる場合、図３に示されているように、角度および分散フィーチャは、９５％を超える正しいマッチング結果に達する。単独で加えられた場合に、距離フィーチャだけが、他のフィーチャによって得られるような良好な結果を得ない。しかし約８５％の正しい分類を有し、単独で加えられた場合に距離フィーチャは完全には使用不可能ではない（図１におけるｙ軸が０で始まるのではないことに注意されたい）。ユークリッドコンビネーションの領域が分散フィーチャの領域より高いので、これは距離フィーチャの結果によって影響される。結果として、角度と分散のユークリッドコンビネーションは、傑出した結果に達する。対照的に、ノルム組み合わせは、低いフィーチャパフォーマンスによってそれほど影響されない。他方でユークリッドコンビネーションは従って多くの組み合わせが、９５％を超える正しいマッチング結果に達する。距離フィーチャと分散フィーチャの組み合わせはそれ程正確ではないが、それでも距離フィーチャ単独よりも信頼性がある。
【００８２】
図４は、患者の抽出した気道ツリーと数ヶ月後の同じ患者の追跡収集との間のマッチング結果を示している。ここでは全てのバリエーションにおけるＤ（距離）、Ａ（角度）、Ｖ（分散）Ｅｕｃ（ユークリッド）およびＮｏｒｍ（ノルム）組み合わせがテストされている。最初の気道セグメンテーションは追跡ツリーではセグメンテーションされていかった分枝を含んでいるので、完全に正確なマッチングは行われない。これらの付加的な分枝に対応するパスは、「Ｎ／Ａ」としてラベリングされる。このマッチング結果は、グラウンドトルースと比較され、「真実（例えば正しい）」および「誤り（例えば正しくない）」分類が定められる。
【００８３】
総体的に、４４のパスが含まれたマッチングは、平均で７．７５個の分枝をパス毎に有している、８３の分枝から成る。マッチングマトリクスを使用しない場合、６．８％（例えば４４のうち３つ）の誤りマッチングレートが、分散を除くあらゆるフィーチャを用いて得られる。マッチングマトリクスを導入した場合、例えば、２つの付加的な正しいマッチによって、Ｄ（距離）、Ｖ（分散）およびＮｏｒｍ（ノルム）組み合わせが改善される。これは結果としてパスの２．３％の誤りマッチングレートになる。付加的に、誤ったマッチの多くは終端分枝において誤りを含む。従って、誤ったマッチとラベリングされたパスさえも、多くの分枝にわたって正しいことがある。図５に示されているように、２つのツリー（例えば濃い点線で示されているオリジナルツリーと薄い点線で示されている比較ツリー）は分枝の数および長さにおいて相違を有する。それにもかかわらずパスベースのツリーマッチング方法は首尾良く多くの分枝とパスを一致させる。分枝レベルでのパスベースツリーマッチング方法の評価も可能である。なぜなら、パスマッチが与えられていると、分枝対分枝マッピングを構成することが可能だからである。
【００８４】
図６には気道と動脈パスとの間のマッチングが示されている。ここで気管支ツリー内に大きい円で示された開始部位が手動で選択される。次に、開始部位の周辺のサブボリューム内の血管が自動的にセグメント化され、開始部位に近い血管セグメンテーション内でルート部位を無作為に選択することによってツリー構造体にキャプチャーされる。次に開始部位で始まる全てのパスおよび全ての子孫終端分枝で終わる全てのパスが血管ツリー内の全ての完全なパスにマッチされる。あらゆるマッチングマトリクスを使用せずに選択された一致されたパスには２つのツリー内で同じ色が与えられ、濃い線でレンダリングされたオリジナルツリーと、薄い線でレンダリングされた比較ツリーを伴う。２つの異なる一致からの部位が重畳される場合、最後に一致されたパスの色が重畳領域内の全ての部位に与えられる。このカラーリングプロシージャの結果は、分枝対分枝カラーリングに類似してあらわれる。
【００８５】
本発明の実施形態に相応するパスベースツリーマッチング方法は、種々のツリーマッチングアプリケーションに使用可能である。現在の方法はグラフマッチング技術に頼っている。これはより厳格な要求を有し、誤った分枝によってより妨害されやすい。しかしパスベースツリーマッチング方法は、ツリーの異なった部分でルート分枝を有することの柔軟性を可能にし、また成功した一致が得られる。付加的に、パスベースツリーマッチング方法によって、１つのツリー内の２つの分枝が比較ツリー内の分枝と一致され、誤った中央分枝が収容される。これは標準のノードベースマッチング方法で実現するのは困難である。
【００８６】
さらに、本発明を種々の形態のハードウェア、ソフトウェア、ファームウェア、特定の目的のプロセッサまたはこれらの組み合わせに実装可能であることを理解されたい。１つの実施形態では、本発明はアプリケーションプログラムとしてソフトウェア内に実装される。これは実体的にプログラム記憶装置上で実行される（例えば磁気フロッピィディスク、ＲＡＭ、ＣＤ−ＲＯＭ、ＤＶＤ、ＲＯＭおよびフラッシュメモリ）。このアプリケーションプログラムはあらゆる適切なアーキテクチャを含む機械によってアップロードされ、実行される。
【００８７】
さらに、添付図面内に示された幾つかの構成素子的なシステムコンポーネントおよび方法ステップがソフトウェアで実装され、システムコンポーネント（またはプロセスステップ）間の実際のコネクションが、本発明がプログラムされる方法に依存して異なってよいことを理解されたい。この明細書に示された本発明の教示があれば、当業者はこれらおよび本発明の実装または構成に類似したものを企図することができる。
【００８８】
また上記の説明は、具体的な実施形態を示すためのものにすぎないことも理解されたい。理解しやすいように、上記の説明では可能な実施形態の代表的な例に的を絞っていたが、これらは本発明の基本的な思想を詳解するためのものであって、すべての可能な変形形態を排他的に列挙したわけではない。本発明の特定部分において代替的な実施形態が示されなかったこと、またはさらなる未記載の選択肢が部分に対して使用可能であることは、これらの実施形態の放棄と見なされるべきではない。別の適用形態や実施形態も、本発明の趣旨および範囲から逸脱することなく直接実現することができる。
【００８９】
したがって本発明は、特記された実施形態に制限されることない。なぜなら、上述のものに対する非新規的な代用に関連する上述したものおよび実装の多くの置き換えおよび組み合わせを作成することが可能だからである。本発明は、後続の請求の範囲で特定される。請求の範囲における文言上の範囲には未記載の実施形態が多く含まれ、これらも本発明と同等のものであることを理解されたい。
【図面の簡単な説明】
【００９０】
【図１】本発明の実施例に従ったパスベースツリーマッチングのためのシステムをあらわしたブロックダイヤグラム
【図２】本発明の実施例に従ったパスベースツリーマッチングのための方法をあらわしたフローチャート
【図３】図２の方法による、合成ツリーに一致された気道サブツリーの精度結果を示す棒グラフ
【図４】図２の方法によって一致された、異なる時間に抽出された同じ患者の気道ツリーの精度結果を示す棒グラフ
【図５】図２の方法によって一致された２つのツリーの例
【図６】図２の方法によって一致された、気道および動脈パスの例
【符号の説明】
【００９１】
１００ システム、 １０５ 収集デバイス、 １１５ オペレータコンソール、 １２５ ＣＰＵ、 １３０ メモリ、 １３５ ＲＡＭ、 １４０ ＲＯＭ、 １４５ パスベースツリーマッチングモジュール、 １５０ 入力部、 １５５ 出力部、 １６０ ディスプレイ、 １６５ コントローラ
【特許請求の範囲】
【請求項１】
ツリーマッチングのための方法であって、
物理的オブジェクトまたはモデルを表すツリー状構造を収集し；
第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し、
前記パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；
当該類似測定に基づいて前記パスが一致しているか否かを定める、
ことを含む、
ことを特徴とする、ツリーマッチングのための方法。
【請求項２】
前記ツリー状構造の各パスが一致される、または除外されるまで、前記抽出ステップ、比較ステップ、確定ステップを繰り返す、請求項１記載の方法。
【請求項３】
前記パスを、１つまたは２つのツリー状構造のヒエラルキーに従って比較する、請求項２記載の方法。
【請求項４】
パスが一致しているかを、他のパスの類似測定に基づいて定める、請求項３記載の方法。
【請求項５】
一致されたパスを記録するためにマッチングマトリクスを作成する、請求項４記載の方法。
【請求項６】
最も一致しているパスが既に別のパスと一致している場合、次の最適一致パスとパスを一致させるために確率マトリクスを作成する、請求項４記載の方法。
【請求項７】
パスを比較する前に、ツリー状構造をアライメントする、請求項２記載の方法。
【請求項８】
前記ツリー状構造は気道、動脈または静脈である、請求項１記載の方法。
【請求項９】
前記ツリー状構造を追跡、セグメント化またはスケルトン化によって収集する、請求項１記載の方法。
【請求項１０】
前記パスを、セグメント化、中心線抽出によって抽出する、または直接的にツリー状構造から抽出する、請求項１記載の方法。
【請求項１１】
前記パスの抽出は、前記パス間の比較のための基礎として、前記パスのうちの１つを選択することを含む、請求項１０記載の方法。
【請求項１２】
長いパスのサブセクションに一致する短いパスを、前記パス間の比較のための基礎として選択する、請求項１１記載の方法。
【請求項１３】
前記類似測定は、前記パスの距離フィーチャ、角度フィーチャ、距離分散フィーチャまたは当該フィーチャの数値的な組み合わせである、請求項１記載の方法。
【請求項１４】
ツリー状構造のパスを別のツリー状構造にマッチングさせるための方法であって、
第１のツリー状構造および第２のツリー状構造からパスを収集し；
第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較し；
第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最適に一致するのかを、当該類似測定に基づいて定める、
ことを含む、
ことを特徴とする、ツリー状構造のパスを別のツリー状構造にマッチングさせるための方法。
【請求項１５】
第１および第２のツリー状構造を一致させるために、前記収集ステップ、比較ステップおよび確定ステップを繰り返す、請求項１４記載の方法。
【請求項１６】
第１および第２のツリー状構造のパスを、１つまたは２つのツリー状構造のヒエラルキーに従って比較する、請求項１５記載の方法。
【請求項１７】
一致されたパスを記録するためのマッチングマトリクスを作成する、請求項１６記載の方法。
【請求項１８】
最も一致しているパスが既に別のパスと一致している場合、次の最適一致パスを可能にするためにパスをマッチングさせる確率マトリクスを作成する、請求項１６記載の方法。
【請求項１９】
ツリーマッチングのためのシステムであって：
プログラムを格納するためのメモリデバイスと；
当該メモリデバイスと通信するプロセッサとを含み、ここで当該プロセッサはプログラムで動作し：
物理的オブジェクトまたはモデルを表すツリー状構造を収集し；
第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し：
前記パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；
当該類似測定に基づいてこれらのパスが一致しているか否かを定める、
ことを特徴とする、ツリーマッチングのためのシステム。
【請求項２０】
前記プロセッサはさらにプログラムコードで動作し；ツリー状構造の各パスが一致するまたは除外されるまで抽出ステップ、比較ステップおよび確定ステップを繰り返す、請求項１９記載のシステム。
【請求項２１】
前記パスを、１つまたは２つのツリー状構造のヒエラルキーに従って比較する、請求項２０記載のシステム。
【請求項２２】
前記プロセッサはさらにプログラムコードで動作し：他のパスの類似測定に基づいてパスが一致しているかを定める、請求項２１記載のシステム。
【請求項２３】
前記プロセッサはさらにプログラムコードで動作し：一致されたパスを記録するためのマッチングマトリクスを作成する、請求項２２記載のシステム。
【請求項２４】
前記プロセッサはさらにプログラムコードで動作し：最も一致しているパスが既に別のパスと一致している場合、次の最適一致パスとパスを一致させるために確率マトリクスを作成する、請求項２２記載のシステム。
【請求項２５】
ツリー状構造のパスを別のツリー状構造にマッチングさせるためのシステムであって：
プログラムを格納するためのメモリデバイスと；
当該メモリデバイスと通信するプロセッサとを含み、ここで当該プロセッサはプログラムで動作し：
第１のツリー状構造および第２のツリー状構造からパスを収集し；
第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較し；
第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最も一致するかを、当該類似測定に基づいて定める、
ことを含む、
ことを特徴とする、ツリー状構造のパスを別のツリー状構造にマッチングさせるためのシステム。
【請求項２６】
前記プロセッサはさらにプログラムコードで動作し：第１および第２のツリー状構造を一致させるために、前記収集ステップ、比較ステップおよび確定ステップを繰り返す、請求項２５記載の方法。
【請求項２７】
第１および第２のツリー状構造のパスを、１つまたは２つのツリー状構造のヒエラルキーに従って比較する、請求項２５記載の方法。
【請求項２８】
前記プロセッサはさらにプログラムコードで動作し：一致されたパスを記録するためにマッチングマトリクスを作成する、請求項２７記載の方法。
【請求項２９】
前記プロセッサはさらにプログラムコードで動作し：最も一致しているパスが既に別のパスと一致している場合、次の最適一致パスを可能にするために、パスをマッチングさせる確率マトリクスを作成する、請求項２７記載の方法。
【請求項１】
ツリーマッチングのための方法であって、
物理的オブジェクトまたはモデルを表すツリー状構造を収集し；
第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し、
前記パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；
当該類似測定に基づいて前記パスが一致しているか否かを定める、
ことを含む、
ことを特徴とする、ツリーマッチングのための方法。
【請求項２】
前記ツリー状構造の各パスが一致される、または除外されるまで、前記抽出ステップ、比較ステップ、確定ステップを繰り返す、請求項１記載の方法。
【請求項３】
前記パスを、１つまたは２つのツリー状構造のヒエラルキーに従って比較する、請求項２記載の方法。
【請求項４】
パスが一致しているかを、他のパスの類似測定に基づいて定める、請求項３記載の方法。
【請求項５】
一致されたパスを記録するためにマッチングマトリクスを作成する、請求項４記載の方法。
【請求項６】
最も一致しているパスが既に別のパスと一致している場合、次の最適一致パスとパスを一致させるために確率マトリクスを作成する、請求項４記載の方法。
【請求項７】
パスを比較する前に、ツリー状構造をアライメントする、請求項２記載の方法。
【請求項８】
前記ツリー状構造は気道、動脈または静脈である、請求項１記載の方法。
【請求項９】
前記ツリー状構造を追跡、セグメント化またはスケルトン化によって収集する、請求項１記載の方法。
【請求項１０】
前記パスを、セグメント化、中心線抽出によって抽出する、または直接的にツリー状構造から抽出する、請求項１記載の方法。
【請求項１１】
前記パスの抽出は、前記パス間の比較のための基礎として、前記パスのうちの１つを選択することを含む、請求項１０記載の方法。
【請求項１２】
長いパスのサブセクションに一致する短いパスを、前記パス間の比較のための基礎として選択する、請求項１１記載の方法。
【請求項１３】
前記類似測定は、前記パスの距離フィーチャ、角度フィーチャ、距離分散フィーチャまたは当該フィーチャの数値的な組み合わせである、請求項１記載の方法。
【請求項１４】
ツリー状構造のパスを別のツリー状構造にマッチングさせるための方法であって、
第１のツリー状構造および第２のツリー状構造からパスを収集し；
第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較し；
第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最適に一致するのかを、当該類似測定に基づいて定める、
ことを含む、
ことを特徴とする、ツリー状構造のパスを別のツリー状構造にマッチングさせるための方法。
【請求項１５】
第１および第２のツリー状構造を一致させるために、前記収集ステップ、比較ステップおよび確定ステップを繰り返す、請求項１４記載の方法。
【請求項１６】
第１および第２のツリー状構造のパスを、１つまたは２つのツリー状構造のヒエラルキーに従って比較する、請求項１５記載の方法。
【請求項１７】
一致されたパスを記録するためのマッチングマトリクスを作成する、請求項１６記載の方法。
【請求項１８】
最も一致しているパスが既に別のパスと一致している場合、次の最適一致パスを可能にするためにパスをマッチングさせる確率マトリクスを作成する、請求項１６記載の方法。
【請求項１９】
ツリーマッチングのためのシステムであって：
プログラムを格納するためのメモリデバイスと；
当該メモリデバイスと通信するプロセッサとを含み、ここで当該プロセッサはプログラムで動作し：
物理的オブジェクトまたはモデルを表すツリー状構造を収集し；
第１のツリー状構造からパスを抽出し、第２のツリー状構造からパスを抽出し：
前記パスに対する類似測定を計算することによって、第１および第２のツリー状構造のパスを比較し；
当該類似測定に基づいてこれらのパスが一致しているか否かを定める、
ことを特徴とする、ツリーマッチングのためのシステム。
【請求項２０】
前記プロセッサはさらにプログラムコードで動作し；ツリー状構造の各パスが一致するまたは除外されるまで抽出ステップ、比較ステップおよび確定ステップを繰り返す、請求項１９記載のシステム。
【請求項２１】
前記パスを、１つまたは２つのツリー状構造のヒエラルキーに従って比較する、請求項２０記載のシステム。
【請求項２２】
前記プロセッサはさらにプログラムコードで動作し：他のパスの類似測定に基づいてパスが一致しているかを定める、請求項２１記載のシステム。
【請求項２３】
前記プロセッサはさらにプログラムコードで動作し：一致されたパスを記録するためのマッチングマトリクスを作成する、請求項２２記載のシステム。
【請求項２４】
前記プロセッサはさらにプログラムコードで動作し：最も一致しているパスが既に別のパスと一致している場合、次の最適一致パスとパスを一致させるために確率マトリクスを作成する、請求項２２記載のシステム。
【請求項２５】
ツリー状構造のパスを別のツリー状構造にマッチングさせるためのシステムであって：
プログラムを格納するためのメモリデバイスと；
当該メモリデバイスと通信するプロセッサとを含み、ここで当該プロセッサはプログラムで動作し：
第１のツリー状構造および第２のツリー状構造からパスを収集し；
第１のツリー状構造のパスおよび第２のツリー状構造のパスに対する類似測定を計算することによって、第１のツリー状構造のパスと、第２のツリー状構造のパスを比較し；
第２のツリー状構造のパスのどのパスが、第１のツリー状構造のパスと最も一致するかを、当該類似測定に基づいて定める、
ことを含む、
ことを特徴とする、ツリー状構造のパスを別のツリー状構造にマッチングさせるためのシステム。
【請求項２６】
前記プロセッサはさらにプログラムコードで動作し：第１および第２のツリー状構造を一致させるために、前記収集ステップ、比較ステップおよび確定ステップを繰り返す、請求項２５記載の方法。
【請求項２７】
第１および第２のツリー状構造のパスを、１つまたは２つのツリー状構造のヒエラルキーに従って比較する、請求項２５記載の方法。
【請求項２８】
前記プロセッサはさらにプログラムコードで動作し：一致されたパスを記録するためにマッチングマトリクスを作成する、請求項２７記載の方法。
【請求項２９】
前記プロセッサはさらにプログラムコードで動作し：最も一致しているパスが既に別のパスと一致している場合、次の最適一致パスを可能にするために、パスをマッチングさせる確率マトリクスを作成する、請求項２７記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００７−４４４８８（Ｐ２００７−４４４８８Ａ）
【公開日】平成１９年２月２２日（２００７．２．２２）
【国際特許分類】
【外国語出願】
【出願番号】特願２００６−１７２６９６（Ｐ２００６−１７２６９６）
【出願日】平成１８年６月２２日（２００６．６．２２）
【出願人】（５９３０７８００６）シーメンス コーポレイト リサーチ インコーポレイテツド (47)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｃｏｒｐｏｒａｔｅ Ｒｅｓｅａｒｃｈ，Ｉｎｃ．
【住所又は居所原語表記】７５５ Ｃｏｌｌｅｇｅ Ｒｏａｄ Ｅａｓｔ，Ｐｒｉｎｃｅｔｏｎ， ＮＪ ０８５４０，Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ
【Ｆターム（参考）】
【公開日】平成１９年２月２２日（２００７．２．２２）
【国際特許分類】
【出願番号】特願２００６−１７２６９６（Ｐ２００６−１７２６９６）
【出願日】平成１８年６月２２日（２００６．６．２２）
【出願人】（５９３０７８００６）シーメンス コーポレイト リサーチ インコーポレイテツド (47)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｃｏｒｐｏｒａｔｅ Ｒｅｓｅａｒｃｈ，Ｉｎｃ．
【住所又は居所原語表記】７５５ Ｃｏｌｌｅｇｅ Ｒｏａｄ Ｅａｓｔ，Ｐｒｉｎｃｅｔｏｎ， ＮＪ ０８５４０，Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ
【Ｆターム（参考）】
[ Back to top ]