(57)【要約】【課題】画像上に表示された計測対象物間に、対象物間を結ぶ経路の候補が陽に与えられておらず、また経路が通過できない障害物が存在する場合においても、対象物間の最短距離を高速かつ高精度に計測することが可能な経路計測方法及び装置を提供する。【解決手段】コスト場生成装置４において、距離計測の対象物と経路が通過できない非対象物との配置関係に基づいて、経路の通りやすさを規定するコスト場を生成し、動的経路生成装置５において、画像各点におけるコスト場の値を参照しながら、対象物間を結ぶ複数の経路を動的に生成し、経路探索装置６において、対象物間を結ぶ最短経路を探索する。【選択図】図１
2008107228.tif 000002
【特許請求の範囲】
【請求項１】
あらかじめ経路の候補が定まっていない対象物に対し、画像から入力された前記対象物間の経路を計測する経路計測装置において、
距離計測の対象物及び距離計測の経路から排除される非対象物の画像を入力する画像入力装置と、
前記入力画像に含まれる、前記対象物及び前記非対象物の領域の内部と外部を二値化によって分離する画像二値化装置と、
前記経路の始点である開始点、前記経路の終点である目的点、前記経路が通過できない非対象物領域、及び前記経路の伸張パラメータｒを設定するパラメータ設定装置と、
前記開始点、前記目的点、及び前記非対象物領域に基づいて、前記開始点に近いほど、また前記目的点から遠いほど大きな値を取り、かつ前記非対象物領域内部で大きな値を取ることにより、前記経路の通りやすさを規定するコストを、前記入力画像の各点において定義し、前記コストが定義された点の集合であるコスト場を生成するコスト場生成装置と、
前記開始点を始点として、前記開始点をただ一つの要素とする始点集合を生成し、前記始点集合に含まれるそれぞれの始点から伸びる長さｒの線分からなる線分集合を生成し、前記線分の終点の集合を新たな始点集合として既存の前記始点集合を更新し、前記線分集合によって表される全ての経路が前記目的点に到達するまで、前記始点集合及び前記線分集合の生成、更新を逐次繰り返して前記経路の集合を生成する動的経路生成装置と、
前記経路の集合に含まれる経路の中から、最短経路を探索する経路探索装置と、
前記最短経路と前記最短経路の長さを表示する経路表示装置と
を具備する
経路計測装置。
【請求項２】
請求項１に記載の経路計測装置において、
前記最短経路を求めた後、前記線分の長さｒが所与の条件を満たしているかどうかを調べ、前記条件が満たされない場合に、前記線分の長さを縮小し、前記最短経路の近傍を非対象物として前記二値画像に保持する経路再構成装置
を更に具備する
経路計測装置。
【請求項３】
請求項１又は２に記載の経路計測装置において、
前記動的経路生成装置は、前記経路を生成する過程で、一つの経路を構成する線分の終点と、他の経路を構成する線分の終点との距離が所与の値よりも小さくなった場合に、これらの終点を一つに統合する
経路計測装置。
【請求項４】
請求項１乃至３のいずれか一項に記載の経路計測装置において、
前記経路探索装置は、ビタビアルゴリズムによって経路を決定する
経路計測装置。
【請求項５】
請求項１乃至４のいずれか一項に記載の経路計測装置において、
前記経路探索装置は、ダイクストラアルゴリズムによって経路を決定する
経路計測装置。
【請求項６】
あらかじめ経路の候補が定まっていない対象物間の経路を計測する経路計測方法において、
距離計測の対象物及び距離計測の経路から排除される非対象物の画像を入力する第１の工程と、
前記入力画像に含まれる、前記対象物及び前記非対象物の領域の内部と外部を二値化によって分離する第２の工程と、
前記経路の始点である開始点、前記経路の終点である目的点、前記経路が通過できない非対象物領域、及び前記経路の伸張パラメータｒを設定する第３の工程と、
前記開始点、前記目的点、及び前記非対象物領域に基づいて、前記開始点に近いほど、また前記目的点から遠いほど大きな値を取り、かつ前記非対象物領域内部で大きな値を取ることにより、前記経路の通りやすさを規定するコストを、前記入力画像の各点において定義し、前記コストが定義された点の集合であるコスト場を生成する第４の工程と、
前記開始点を始点として、前記開始点をただ一つの要素とする始点集合を生成し、前記始点集合に含まれるそれぞれの始点から伸びる長さｒの線分からなる線分集合を生成し、前記線分の終点の集合を新たな始点集合として既存の前記始点集合を更新し、前記線分集合によって表される全ての経路が前記目的点に到達するまで、前記始点集合及び前記線分集合の生成、更新を逐次繰り返して前記経路の集合を生成する第５の工程と、
前記経路の集合に含まれる経路の中から、最短経路を探索する第６の工程と、
前記最短経路と前記最短経路の長さを表示する第７の工程と
を具備する
経路計測方法。
【請求項７】
請求項６に記載の経路計測方法において、
前記最短経路を求めた後、前記線分の長さｒが所与の条件を満たしているかどうかを調べ、前記条件が満たされない場合に、前記線分の長さを縮小し、前記最短経路の近傍を非対象物として前記二値画像に保持する第８の工程
を更に具備し、
前記所与の条件が満たされるまで前記第３、前記第４、前記第５、前記第６の工程を繰り返す
経路計測方法。
【請求項８】
請求項６又は７に記載の経路計測方法において、
前記第５の工程において、前記経路を生成する過程で、一つの経路を構成する線分の終点と、他の経路を構成する線分の終点との距離が所与の値よりも小さくなった場合に、これらの終点を一つに統合する
経路計測方法。
【請求項９】
請求項６乃至８のいずれか一項に記載の経路計測方法において、
前記第６の工程において、ビタビアルゴリズムによって経路を決定する
経路計測方法。
【請求項１０】
請求項６乃至９のいずれか一項に記載の経路計測方法において、
前記第６の工程において、ダイクストラアルゴリズムによって経路を決定する
経路計測方法。
【請求項１１】
請求項６乃至１０のいずれか一項に記載の経路計測方法を、コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路計測装置及び経路計測方法に関し、特に画像上に表示された対象物間の経路を計測する経路計測装置及び経路計測方法に関する。
【背景技術】
【０００２】
従来、画像上に表示された対象物間の距離を計測する方法又は装置としては、例えば特開２００５−６５８４５号公報（特許文献１）に開示される「医用画像装置」がある。
【０００３】
特許文献１においては、操作者が医用画像上で指定した２点のうちの一方の点（以下点Ａとする）を領域拡張法により拡張し、領域の増分が他方の点（以下点Ｂとする）に到達するまで拡張を繰り返す。拡張の過程において、親画素と子画素の関係を記録しておき、拡張された領域が点Ｂに到達した時点で、親画素と子画素の関係を逆にたどり、点Ａと点Ｂを結ぶ経路の長さを計測する。
【０００４】
しかしながら、上記特許文献１における方法では、距離を計測しようとする２点間に、経路が通過できない障害物が存在する場合、領域拡張法を繰り返して得られた経路が、必ずしも最短経路とはならないという問題がある。特に、障害物の境界に沿って延びるような最短経路は、特許文献１に示すような手法では得られない。
【０００５】
医用分野においては、例えば投与した薬剤の浸透速度、あるいは細胞核内の構造物間の相互作用の有無など、対象物間の最短距離が重要な情報となることが多く、必ずしも最短距離が得られない上述の従来方法を適用した場合、正確な情報が得られないという問題がある。
【０００６】
関連する技術として、特開２００３−３０３３４４号公報（特許文献２）に画像領域抽出方法及び装置が開示されている。
この従来技術においては、画像データ空間を粗視化し、粗視化経験確率分布を算出し、パラメータを初期化し、粗視化条件付き確率分布を算出し、クラス帰属確率を算出し、パラメータを更新し、評価関数を算出し、評価関数の変化が無くなるまでこれらの処理を繰り返し、評価関数の変化が無くなった時点で、クラス帰属確率に基づいて画像領域を抽出する。
【０００７】
また、特開２００６−１３３０１２号公報（特許文献３）に経路探索装置及び経路探索用データ生成方法が開示されている。
この従来技術においては、目的地までの最適経路を探索して出力する経路探索装置が、座標を有する点データ、点列を有する線データ及び境界を回る点列を有する面データの組み合わせからなる幾何図形データを含む点・線・面混在型データと、幾何図形データと合成され面データに代表点を設定して双方向にネットワークを形成する線データの組み合わせからなる経路探索用データと、経路探索用データに基づき経路探索を行う経路探索手段と、経路探索手段により探索された経路を幾何図形データに基づき点・線・面混在方式による経路を描画し出力する経路出力手段とを備えたことを特徴とする。
【０００８】
また、特開平５−４６５９０号公報（特許文献４）に複数の最適解を求めるグラフ最短経路探索方法及び装置が開示されている。
この従来技術においては、グラフの最短経路を求める手法として、まず、頂点間の辺に実数値のコストが付いた有向グラフの任意の頂点と終点ｔとの最短コストを算出し、次に、有向グラフＧの始点ｓからの部分経路を、始点ｓからのコストの累積ｇ（Ｘｉ）と、残りの経路の最短コストｈ（Ｘｉ）との和ｆ（Ｘｉ）に基づき、設定された解析条件に従って下位を枝刈りしながら、ａ，ａ＋１のごとく終点ｔに向けて逐次的に経路展開し、探索が終了した時点で保持されている上位Ｎ個の最適な経路を出力する。
【０００９】
また、特開平１１−１８４８３７号公報（特許文献５）に最短経路探索システムが開示されている。
この従来技術においては、探索の対象となる経路を削減するための指標として、評価
値ｈ（ｖ）という関数を用いている。この評価値ｈ（ｖ）とは、現在の地点ｖから終点Ｔへ至る経路長の下限値と定義されている。この下限値を求める方法として、擬似コードを用いている。この擬似コードによると、下限値を得るためには、下限値を求めたい点の集合Ｕに含まれる点に向かって、終点Ｔから逆向きに経路をたどる必要がある。つまり、特許文献５の従来技術では、始点から終点までを結ぶ複数の経路が、あらかじめ設定されていなければならない。
【００１０】
更に、特許２９４３３５８号公報（特許文献６）に配線設計装置が開示されている。
この従来技術においては、開始点から領域を膨張させ、領域の境界が終点に到達した段階で、終点から開始点までを逆にたどって経路を発見している。このとき、経路を生成する工程があるが、生成された経路は複数ではなく一つであり、従って経路探索をする必要もない。また、必ずしも空間的に最短経路になるとは限らない。
【００１１】
【特許文献１】特開２００５−６５８４５号公報
【特許文献２】特開２００３−３０３３４４号公報
【特許文献３】特開２００６−１３３０１２号公報
【特許文献４】特開平５−４６５９０号公報
【特許文献５】特開平１１−１８４８３７号公報
【特許文献６】特許２９４３３５８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明の目的は、画像上に表示された計測対象物間に障害物が存在する場合においても、対象物間の最短距離を高速かつ高精度に計測することが可能な経路計測装置及び経路計測方法を提供することにある。
【課題を解決するための手段】
【００１３】
以下に、［発明を実施するための最良の形態］で使用される番号を括弧付きで用いて、課題を解決するための手段を説明する。これらの番号は、［特許請求の範囲］の記載と［発明を実施するための最良の形態］との対応関係を明らかにするために付加されたものである。但し、それらの番号を、［特許請求の範囲］に記載されている発明の技術的範囲の解釈に用いてはならない。
【００１４】
本発明の経路計測装置は、あらかじめ経路の候補が定まっていない対象物に対し、画像から入力された対象物間の経路を計測する経路計測装置である。そして、本発明の経路計測装置は、距離計測の対象物及び距離計測の経路から排除される非対象物の画像を入力する画像入力装置（１）と、入力画像に含まれる、対象物及び非対象物の領域の内部と外部を二値化によって分離する画像二値化装置（２）と、経路の始点である開始点、経路の終点である目的点、経路が通過できない非対象物領域、及び経路の伸張パラメータｒを設定するパラメータ設定装置（３）と、開始点、目的点、及び非対象物領域に基づいて、開始点に近いほど、また目的点から遠いほど大きな値を取り、かつ非対象物領域内部で大きな値を取ることにより、経路の通りやすさを規定するコストを、入力画像の各点において定義し、コストが定義された点の集合であるコスト場を生成するコスト場生成装置（４）と、開始点を始点として、開始点をただ一つの要素とする始点集合を生成し、始点集合に含まれるそれぞれの始点から伸びる長さｒの線分からなる線分集合を生成し、線分の終点の集合を新たな始点集合として既存の始点集合を更新し、線分集合によって表される全ての経路が目的点に到達するまで、始点集合及び線分集合の生成、更新を逐次繰り返して経路の集合を生成する動的経路生成装置（５）と、経路の集合に含まれる経路の中から、最短経路を探索する経路探索装置（６）と、最短経路と最短経路の長さを表示する経路表示装置（７）とを具備する。
【００１５】
本発明の経路計測装置は、最短経路を求めた後、線分の長さｒが所与の条件を満たしているかどうかを調べ、条件が満たされない場合に、線分の長さを縮小し、最短経路の近傍を非対象物として二値画像に保持する経路再構成装置（８）を更に具備する。
【００１６】
動的経路生成装置（５）は、経路を生成する過程で、一つの経路を構成する線分の終点と、他の経路を構成する線分の終点との距離が所与の値よりも小さくなった場合に、これらの終点を一つに統合する。
【００１７】
経路探索装置（６）は、ビタビアルゴリズムによって経路を決定する。
【００１８】
経路探索装置（６）は、ダイクストラアルゴリズムによって経路を決定する。
【００１９】
本発明の経路計測方法は、あらかじめ経路の候補が定まっていない対象物間の経路を計測する経路計測方法である。そして、本発明の経路計測方法は、距離計測の対象物及び距離計測の経路から排除される非対象物の画像を入力する第１の工程と、入力画像に含まれる、対象物及び非対象物の領域の内部と外部を二値化によって分離する第２の工程と、経路の始点である開始点、経路の終点である目的点、経路が通過できない非対象物領域、及び経路の伸張パラメータｒを設定する第３の工程と、開始点、目的点、及び非対象物領域に基づいて、開始点に近いほど、また目的点から遠いほど大きな値を取り、かつ非対象物領域内部で大きな値を取ることにより、経路の通りやすさを規定するコストを、入力画像の各点において定義し、コストが定義された点の集合であるコスト場を生成する第４の工程と、開始点を始点として、開始点をただ一つの要素とする始点集合を生成し、始点集合に含まれるそれぞれの始点から伸びる長さｒの線分からなる線分集合を生成し、線分の終点の集合を新たな始点集合として既存の始点集合を更新し、線分集合によって表される全ての経路が目的点に到達するまで、始点集合及び線分集合の生成、更新を逐次繰り返して経路の集合を生成する第５の工程と、経路の集合に含まれる経路の中から、最短経路を探索する第６の工程と、最短経路と最短経路の長さを表示する第７の工程とを具備する。
【００２０】
本発明の経路計測方法は、最短経路を求めた後、線分の長さｒが所与の条件を満たしているかどうかを調べ、条件が満たされない場合に、線分の長さを縮小し、最短経路の近傍を非対象物として二値画像に保持する第８の工程を更に具備する。また、所与の条件が満たされるまで第３、第４、第５、第６の工程を繰り返す。
【００２１】
本発明の経路計測方法は、第５の工程において、経路を生成する過程で、一つの経路を構成する線分の終点と、他の経路を構成する線分の終点との距離が所与の値よりも小さくなった場合に、これらの終点を一つに統合する。
【００２２】
本発明の経路計測方法は、第６の工程において、ビタビアルゴリズムによって経路を決定する。
【００２３】
本発明の経路計測方法は、第６の工程において、ダイクストラアルゴリズムによって経路を決定する。
【００２４】
本発明のプログラムは、上記のいずれかの経路計測方法をコンピュータに実行させる。
【発明の効果】
【００２５】
経路計測の対象物と非対象物の配置に基づいて、画像各点における経路の通りやすさを規定するコスト場を生成し、各点におけるコストを参照しながら動的に最短経路候補を生成することにより、従来手法よりも高速で高精度な経路計測を行うことができる。
【発明を実施するための最良の形態】
【００２６】
以下に本発明の第１実施形態について添付図面を参照して説明する。なお、本実施形態では、染色された細胞の顕微鏡画像を入力とし、細胞の各組織（染色体、細胞核、核小体など）間の距離を計測する場合を例にとって説明する。この場合の細胞画像は、細胞核、染色体、核小体などが別々のモノクロ画像に記録されたデータでも良いし、各対象物の領域が重複しなければ、複数の対象物、非対象物が一つのモノクロ画像上に表示されていても良い。あるいは、細胞核、染色体、核小体などが別々異なるカラーチャネルで記録された１枚のカラー画像であっても良い。これ以外の場合でも、画像として記録されているデータであるならば、以下に説明する方法と同様な手順で実行できる。
【００２７】
以下、本発明の経路計測装置について、図１を用いて説明する。図１は、本発明の経路計測装置の構成を示すブロック図である。
【００２８】
図１を参照すると、本発明の経路計測装置は、画像入力装置１と、画像二値化装置２と、パラメータ設定装置３と、コスト場生成装置４と、動的経路生成装置５と、経路探索装置６と、経路表示装置７を備えている。
【００２９】
画像入力装置１は、画像データを読み込む。画像二値化装置２は、画像を二値化する。パラメータ設定装置３は、画像中の対象物及び非対象物を指定する。コスト場生成装置４は、対象物及び非対象物の配置からコスト場を生成する。動的経路生成装置５は、対象物間を結ぶ経路を動的に生成する。経路探索装置６は、生成された複数の経路の中から、経路を探索する。経路表示装置７は、最終的な経路や対象物間の最短距離を表示する。
【００３０】
図２Ａ，図２Ｂは、本発明の経路計測方法の処理手順を示すフローチャートである。
（１）ステップＳ１
入力装置１は、生物顕微鏡などで撮影された細胞の画像を入力する。入力装置１は、読み込んだデータを画像二値化装置２に送る。
（２）ステップＳ２
画像二値化装置２は、読み込んだ各対象物の画像に対し、画像上各点の輝度値に基づいて、二値化を行う。二値化を行う場合には、例えば、所与の閾値より大きな輝度値を２５５、閾値以下の輝度値を０と置くことによって可能である。このほかに、画像上の輝度値の総和を１に正規化し、画像を２次元確率場と見なして確率的に二値化を行うことも可能である。確率場を用いた二値化については、例えば、特開２００３−３０３３４４号公報（特許文献２）に詳細に記載されている。画像二値化装置２は、入力画像と二値化された画像をパラメータ選択装置３に送る。
【００３１】
染色体１１と核小体１２を対象として、二値化された画像の例を図３に示す。図３において、中心にある大きなクラスタが核小体１２を抽出して領域を白く表示したものであり、その周辺にある二つのクラスタが染色体１１である。染色体同士が相互作用をするとき、核小体１２は障害物となるので、二つの染色体間の距離を計測するには、核小体を迂回して計測する必要がある。この場合、二つの染色体１１が対象物となり、核小体１２が非対象物となる。
【００３２】
（３）ステップＳ３
パラメータ設定装置３は、経路計測を行う開始点Ｓ、目的点Ｏ、経路が通過できない非対象物の領域、及び経路の伸張パラメータｒを設定する。開始点Ｓと目的点Ｏを指定するには、例えば開始点Ｓを含む対象物のみが記録された画像と、目的点Ｏを含む対象物のみが記録された画像と、非対象物のみが記録された画像を順次読み込み、画像二値化装置２において二値化を行った後、それぞれの領域の重心位置を開始点、目的点とすることが可能である。非対象物は非対象物のみが記録された画像を二値化したものをそのまま領域として用いる。これ以外にも、例えば操作者が外部入力機器を通してその座標値を入力することによっても実行可能である。パラメータ設定装置３は、入力画像、二値化された画像、開始点Ｓ、目的点Ｏ、二値画像で表された非対象物領域、伸張パラメータｒをコスト場生成装置４に送る。
（４）ステップＳ４
コスト場生成装置４は、経路計測の対象物と非対象物の配置に基づいて、画像上の各点における経路の通り易さを数値化する。以下では、数値化された経路の通り易さをコスト、各点で定義されたコスト全体をコスト場と呼ぶ。画像上の点ｘにおけるコストを定義するには、例えば次のような関数を用いる。
【００３３】
【数１】
2008107228.tif 000003
【００３４】
ここでｘｓ、ｘｏはそれぞれ開始点Ｓ、目的点Ｏの座標である。ａ，ｂは任意の正の実定数であり、ａは経路が開始点から斥けられる強さを、ｂは経路が目的点に引きつけられる強さを制御する。また、経路が通過できない非対象物をコスト場に反映するには、例えば次のような関数を用いる
【００３５】
【数２】
2008107228.tif 000004
【００３６】
ここで、Ｉ（ｘ）は、点ｘが非対象物に含まれる時に１、それ以外の時に０を取る指示関数である。また、ｃは任意の正の実定数であるが、経路が非対象物領域内を通過できなくするためには、大きな値に取ることが望ましい。
【００３７】
コスト場を定義する関数は上述したものに限られるものではなく、開始点Ｓに近いほど、また目的点Ｏから遠いほど大きな値を取り、かつ対象物領域内部で大きな値を取るようなものであれば良い。
【００３８】
コスト場の例を図４に示す。図４において、Ｓは開始点、Ｏは目的点を表す。図４の（ａ）は、各点におけるコストの値を濃淡で表しており、濃淡が淡いほどコストが大きく、濃いほどコストが小さい。図４の（ｂ）は、同じコスト場を３次元表示したものである。このようなコスト場を用いることにより、効率的な経路生成が可能となる。
【００３９】
コスト場生成装置４は、生成されたコスト場と開始点Ｓ、目的点Ｏ、二値画像で表された非対象物領域を動的経路生成装置５に送る。動的経路生成装置５は、開始点Ｓを始点として、目的点Ｏへ通じる複数の経路を動的に生成する。
【００４０】
以下の説明において経路とは、複数の線分から構成されるものとし、各線分は、始点と終点を結ぶ長さｒの直線であるとする。経路を構成する各々の線分の始点（又は終点）が、少なくとも一つの他の線分と終点（又は始点）を共有し、従って、少なくとも一つの経路が、開始点Ｓと目的点Ｏを結ぶことは、以下に説明する経路の構成方法から保証される。
【００４１】
（５）ステップＳ５
まず、動的経路生成装置５は、経路の逐次更新のカウンタｋを０に初期化する。
（６）ステップＳ６
次に、動的経路生成装置５は、経路の集合Ｐｋを空集合で、また始点集合Ｉｋを開始点Ｓの１点のみからなる集合で初期化する。
（７）ステップＳ７
次に、動的経路生成装置５は、経路の一部分を構成する線分の集合Ｅｋを空集合で初期化する。
（８）ステップＳ８
次に、動的経路生成装置５は、始点集合Ｉｋの中から、終点の付与されていない始点を一つ選ぶ。これをｖで表す。
（９）ステップＳ９
次に、動的経路生成装置５は、ｖが目的点Ｏと距離ｒ以内にあるかどうか調べる。
（１０）ステップＳ１０
もし、ｖが目的点Ｏと距離ｒよりも離れているならば、動的経路生成装置５は、まずｖから距離ｒ離れた点をＮ個選ぶ（Ｎは所与とする）。そのような点を選ぶには、例えば、ｖを中心とする半径ｒの円周をＮ分割した各点を用いれば良い。ｖを始点として選ばれたＮ個の点それぞれを終点とする線分をＮ個生成する。
（１１）ステップＳ１１
もし、ｖが目的点Ｏからｒ以内にあるなら、動的経路生成装置５は、目的点Ｏを終点とする線分ｖ−Ｏを生成し、生成した線分を線分集合Ｅｋに追加する。
（１２）ステップＳ１２
次に、動的経路生成装置５は、ステップＳ１０で生成したＮ個の線分、又はステップＳ１１で生成した、ｖから目的点Ｏに伸びる１個の線分を線分集合Ｅｋに追加する。
（１３）ステップＳ１３
次に、動的経路生成装置５は、Ｉｋに属する点すべてに対して終点が付与され、線分が生成されているかどうかを調べる。終点が付与されていない始点があるなら、ステップＳ８以下を繰り返す。
（１４）ステップＳ１４
もし、Ｉｋに属するすべての始点に終点が付与されているなら、動的経路生成装置５は、すべての終点が目的点Ｏに一致するかどうかを調べる。もし、すべての終点が目的点Ｏに一致するならば、開始点Ｓから目的点Ｏを結ぶ一つ以上の経路が生成されているので、動的経路生成装置５は、経路集合Ｐｋ、コスト場、開始点Ｓ、目的点Ｏ、二値画像で表された非対象物領域を経路探索装置６に送る。
（１５）ステップＳ１５
もし、目的点Ｏとは異なる終点を付与された始点があるならば、動的経路生成装置５は、まず線分集合Ｅｋに属する各線分に対し、線分が通過する点のコスト値の総和を算出し、所与のコスト値Ｃ以上の値を持つすべての線分を集めて、この集合をＤｋとする。
（１６）ステップＳ１６
次に、動的経路生成装置５は、Ｅｋに属する線分のうち、Ｄｋに属さない線分の集合（これをＥｋ−Ｄｋと記す）に対し、終点を調べて、終点の集合をＴｋとする。但し、終点が目的点Ｏと一致する場合はＴｋから除外する。
（１７）ステップＳ１７
次に、動的経路生成装置５は、終点の集合Ｔｋを次の逐次更新の始点集合Ｉｋ＋１とし、現時点で得られている経路集合Ｐｋに、Ｅｋ−Ｄｋに属する線分を追加し、この経路集合をＰｋ＋１とする。
（１８）ステップＳ１８
次に、動的経路生成装置５は、カウンタｋの値を１だけ増加させ、ステップＳ７以下を繰り返す。
【００４２】
図５に、ステップＳ５からステップＳ１８までの動的経路生成の一例を示す。図５において、Ｓは一つの経路の開始点、ｖｉ（ｉ＝１、２、〜、６）は線分の終点、ｅｉ（ｉ＝１、２、〜、６）はｖｉを終端とする線分を表す。ｋは逐次更新の回数であり、各更新時点での始点集合Ｉ、線分集合Ｅ、終点集合Ｔ、削除される線分Ｄ、生成された経路集合Ｐが図とともに示されている。
【００４３】
動的経路生成装置５においては、経路を生成する過程で、一つの経路を構成する線分の終点と、他の経路を構成する線分の終点との距離が所与の値よりも小さくなった場合に、これらの終点を一つに統合することによって、余分な経路の生成を抑制することも可能である。この機構によって、更に効率的な経路生成が可能となる。
【００４４】
（１９）ステップＳ１９
経路探索装置６は、最終的に得られた経路集合Ｐｋの中から、最短経路を探索し、最短距離を算出する。最短経路の探索には、例えば、信号処理などに用いられるビタビ（Ｖｉｔｅｒｂｉ）アルゴリズムなどを用いることができる。この場合、経路を逐次更新していくカウンタｋを時間と見なし、経路を構成する各線分に付与された重みとして、線分の距離をそのまま用いれば良い。また、経路を構成する線分を辺として、また線分の始点と終点を頂点と見なせば、最適経路の探索方法として、ダイクストラ（Ｄｉｊｋｓｔｒａ）の方法を用いることができる。
（２０）ステップＳ２０
経路表示装置７は、経路探索装置６によって得られた最短経路及びその距離を受け取り、出力する。
【００４５】
以下に本発明の第２実施形態について添付図面を参照して説明する。以下に説明する実施形態では、先に説明した第１実施形態と重複する部分の説明は省略する。
【００４６】
図６は、本発明の第２実施形態における経路計測装置の構成を示すブロック図である。本発明の第２実施形態における経路計測装置は、画像入力装置１と、画像二値化装置２と、パラメータ設定装置３と、コスト場生成装置４と、動的経路生成装置５と、経路探索装置６と、経路表示装置７に加え、更に、経路再構成装置８を備えている。
【００４７】
画像入力装置１、画像二値化装置２、パラメータ設定装置３、コスト場生成装置４、動的経路生成装置５、経路探索装置６、及び経路表示装置７については、第１実施形態と同様である。経路再構成装置８は、経路探索装置６から、最短経路と経路伸張パラメータを受け取り、経路伸張パラメータの値が所与の値より小さいかどうかを調べ、経路伸張パラメータの値が所与の値以下ならば、最短経路と経路の長さを経路表示装置７に送る。また、経路伸張パラメータの値が所与の値以上ならば、経路伸張パラメータに１より小さな所与の正実数をかけた数を新たな伸張パラメータとする。そして、最短経路の近傍以外の領域を新たな非対象物領域として二値画像で表現し、更新された伸張パラメータと二値画像で表現された最短経路近傍以外の領域をパラメータ設定装置３に送る。
【００４８】
図７Ａ，図７Ｂは、本発明の第２実施形態における経路計測方法の処理手順を示すフローチャートである。なお、図７Ａ，図７ＢにおけるステップＳ１〜ステップＳ２０については、第１実施形態と同様である。以下の処理は、ステップＳ１９とステップＳ２０の間に行われる。
（２１）ステップＳ２１
経路再構成装置８は、経路探索装置６から、最短経路と経路伸張パラメータｒを受け取り、経路伸張パラメータの値が所与の値ｒ０より小さいかどうかを調べる。もし、経路伸張パラメータの値が所与の値ｒ０以下ならば、最短経路と経路の長さを経路表示装置７に送る。
（２２）ステップＳ２２
もし、経路伸張パラメータの値が所与の値ｒ０以上ならば、経路伸張パラメータに１より小さな所与の正実数εをかけた数を新たな伸張パラメータとする。
（２３）ステップＳ２３
更に、最短経路の近傍以外の領域を新たな非対象物領域として二値画像で表現し、更新された伸張パラメータと二値画像で表現された最短経路近傍以外の領域をパラメータ設定装置３に送る。最短経路近傍としては、例えば経路を構成する各点を中心とした半径ｄ（ｄは所与とする）に含まれる全領域などとする。
【００４９】
経路再構成装置８によって得られた伸張パラメータと非対象物体領域を用いて、第１の実施例に記したステップＳ５からステップＳ１９までの手順を繰り返すことにより、より滑らかな経路を得ることができる。また、最初に得られた経路の近傍以外を非対象物体領域とすることにより、経路探索の領域が絞られ、より効率的な経路生成及び経路探索が可能となる。
【００５０】
以下に、本発明の経路計測方法及び経路計測装置の特徴について詳述する。
本発明の第１実施例の経路計測方法は、以下に示す、第１の工程と、第２の工程と、第３の工程と、第４の工程と、第５の工程と、第６の工程と、第７の工程を有することを特徴とする。
第１の工程は、あらかじめ経路の候補が定まっていない対象物間の経路を計測する経路計測方法において、該距離計測の対象物及び距離計測の経路から排除される非対象物の画像を入力する。第２の工程は、入力画像に含まれる、対象物及び非対象物の領域の内部と外部を二値化によって分離する。第３の工程は、経路の始点である開始点と、該経路の終点である目的点と、該経路が通過できない非対象物領域と、該経路の伸張パラメータｒを設定する。第４の工程は、開始点、目的点、非対象物領域に基づいて、開始点に近いほど、また目的点から遠いほど大きな値を取り、かつ非対象物領域内部で大きな値を取ることにより、経路の通りやすさを規定するコストを、入力画像の各点において定義し、該コストが定義された点の集合であるコスト場を生成する。第５の工程は、開始点を始点として、開始点をただ一つの要素とする始点集合を生成し、該始点集合に含まれるそれぞれの始点から伸びる長さｒの線分からなる線分集合を生成し、該線分の終点の集合を新たな始点集合として既存の始点集合を更新し、線分集合によって表される全ての経路が目的点に到達するまで、始点集合及び線分集合の生成、更新を逐次繰り返すことによって経路の集合を生成する。第６の工程は、経路の集合に含まれる経路の中から、最短経路を探索する。第７の工程は、最短経路と最短経路の長さを表示する。
【００５１】
本発明の第２実施例の経路計測方法は、最短経路を求めた後、線分の長さｒが所与の条件を満たしているかどうかを調べ、該条件が満たされない場合に、線分の長さを縮小し、最短経路の近傍を非対象物として二値画像に保持する第８の工程を有し、所与の条件が満たされるまで第３、第４、第５、第６の工程を繰り返すことを特徴とする。
【００５２】
本発明の第３実施例の経路計測方法は、第５の工程において、経路を生成する過程で、一つの経路を構成する線分の終点と、他の経路を構成する線分の終点との距離が所与の値よりも小さくなった場合に、これらの終点を一つに統合することを特徴とする。
【００５３】
本発明の第４実施例の経路計測方法は、第６の工程において、ビタビアルゴリズムによって経路を決定することを特徴とする。
【００５４】
本発明の第５実施例の経路計測方法は、第６の工程において、ダイクストラアルゴリズムによって経路を決定することを特徴とする。
【００５５】
本発明の第６実施例の経路計測装置は、画像入力装置と、画像二値化装置と、パラメータ設定装置と、コスト場生成装置と、動的経路生成装置と、経路探索装置と、経路表示装置とを備えることを特徴とする。
画像入力装置は、距離計測の対象物及び距離計測の経路から排除される非対象物の画像を入力する。画像二値化装置は、入力画像に含まれる、対象物及び非対象物の領域の内部と外部を二値化によって分離する。パラメータ設定装置は、経路の始点である開始点と、該経路の終点である目的点と、該経路が通過できない非対象物領域と、該経路の伸張パラメータｒを設定する。コスト場生成装置は、開始点、目的点、非対象物領域に基づいて、開始点に近いほど、また目的点から遠いほど大きな値を取り、かつ非対象物領域内部で大きな値を取ることにより、経路の通りやすさを規定するコストを、入力画像の各点において定義し、該コストが定義された点の集合であるコスト場を生成する。動的経路生成装置は、開始点を始点として、開始点をただ一つの要素とする始点集合を生成し、該始点集合に含まれるそれぞれの始点から伸びる長さｒの線分からなる線分集合を生成し、該線分の終点の集合を新たな始点集合として既存の始点集合を更新し、線分集合によって表される全ての経路が目的点に到達するまで、始点集合及び線分集合の生成、更新を逐次繰り返すことによって経路の集合を生成する。経路探索装置は、経路の集合に含まれる経路の中から、最短経路を探索する。経路表示装置は、最短経路と最短経路の長さを表示する。
【００５６】
本発明の第７実施例の経路計測装置は、最短経路を求めた後、線分の長さｒが所与の条件を満たしているかどうかを調べ、該条件が満たされない場合に、線分の長さを縮小し、最短経路の近傍を非対象物として二値画像に保持する経路再構成装置を有することを特徴とする。
【００５７】
すなわち、本発明の経路計測方法においては、本発明の第１実施例の第６の工程によって、計測対象となる物体のまわりに、コスト場を定義し、各点におけるコストの値を参照しながら動的に経路を生成する。図８に、経路の新規伸張部分となる線分１３（実践で表された矢印）と、コストの値を反映して削除された線分１４（点線で表された矢印）を示す。図８において、背景が白いほどコストが大きく、暗いほどコストが小さいことを示す。また、円形の白い領域（非対象物領域１５）は、経路が通過することができない非対象物が存在する領域を示す。コスト場は、本発明の第１実施例の第４の工程によって、経路の開始点に近付くにつれて、また目的点から遠ざかるにつれて大きな値を取り、かつ非対象物領域内部で非常に大きな値を取るように生成されている。このため、経路の生成は、非対象物の存在する領域を迂回し、開始点から目的点まで効率よく伸びていくように行われる。本発明ではこの機構により、無駄な経路を生成することなく、効率的な経路生成が可能となる。
また、本発明の第４及び第５実施例の経路探索機構により、開始点と目的点をつなぐ複数の経路の中から最短距離を持つ経路を探索するが、上述のように無駄な経路がすでに排除されているため、高速な経路計測が可能となる。
更に、本発明の第２実施例に記載するように、まず経路の伸張パラメータｒを大きく取っておおまかに最短経路を求め、得られた最短経路の近傍に探索領域を絞った後、縮小した伸張パラメータを用いて経路生成することを繰り返すことにより、更に高精度で滑らかな経路の探索が可能となる。
【図面の簡単な説明】
【００５８】
【図１】図１は、本発明の第１実施形態における、距離計測装置の構成を示すブロック図である。
【図２Ａ】図２Ａは、本発明の第１実施形態における処理手順を示すフローチャートである。
【図２Ｂ】図２Ｂは、本発明の第１実施形態における処理手順を示すフローチャートである。
【図３】図３は、距離計測の対象物である染色体と非対象物である核小体を示す図である。
【図４】図４は、コスト場の一形態を示す図である。
【図５】図５は、経路の動的生成過程の一形態を示す図である。
【図６】図６は、本発明の第２実施形態における、距離計測装置の構成を示すブロック図である。
【図７Ａ】図７Ａは、本発明の第２実施形態における処理手順を示すフローチャートである。
【図７Ｂ】図７Ｂは、本発明の第２実施形態における処理手順を示すフローチャートである。
【図８】図８は、経路の伸張分となる線分、削除された線分、非対象物領域を示す図である。
【符号の説明】
【００５９】
１…  画像入力装置
２…  画像二値化装置
３…  パラメータ設定装置
４…  コスト場生成装置
５…  動的経路生成装置
６…  経路探索装置
７…  経路表示装置
８…  経路再構成装置
１１…  染色体（二値化された画像のクラスタ）
１２…  核小体（二値化された画像のクラスタ）
１３…  経路の新規伸張部分となる線分
１４…  削除された線分
１５…  非対象物領域
【図１】
2008107228.tif 000005
【図２Ａ】
2008107228.tif 000006
【図２Ｂ】
2008107228.tif 000007
【図３】
2008107228.tif 000008
【図４】
2008107228.tif 000009
【図５】
2008107228.tif 000010
【図６】
2008107228.tif 000011
【図７Ａ】
2008107228.tif 000012
【図７Ｂ】
2008107228.tif 000013
【図８】
2008107228.tif 000014