JP2003099786A - ２次元データから尾根を抽出する装置、方法、プログラムおよび記憶媒体 - Google Patents

Abstract

(57)【要約】 【課題】 ２次元データから１本の尾根曲線を抽出する
簡単で正確な装置，方法を提供する。 【解決手段】 高さ最大のセルを抽出し（Ｓ１１）、そ
の近傍に近傍領域を決定し（Ｓ１２）、近傍極大セル座
標を検出する（Ｓ１５）。極大セルが１つの場合は（Ｓ
１６，ＮＯ）、スタックされたセル座標があれば（Ｓ１
７ａ，ＹＥＳ）、重みづけ／最短化に従いスタックされ
たセル座標を尾根線として登録し（１８ａ）、近傍極大
セル座標を尾根線として登録し（Ｓ１９）、Ｓ１２へ戻
る。スタックされたセル座標がなければ（Ｓ１７ａ，Ｎ
Ｏ）、近傍極大セル座標を尾根線として登録し（Ｓ１
９）Ｓ１２へ戻る。極大セルが複数の場合は（Ｓ１６，
ＹＥＳ）、セル座標をスタックし（Ｓ２０）、Ｓ１２へ
戻る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、２次元データから
尾根を抽出する装置、方法、プログラム、記憶媒体に関
するものである。

【０００２】

【従来の技術】２次元データ（２次元投影データともい
う）から主たる一つの尾根を抽出するには、図７に示し
たような等高線を肉眼で走査し、図８のように、高い領
域から低い領域に凸状に延びた部分を選びだし連続曲線
とするのが比較的正確な手法であり、これをコンピュー
タにより自動化する試みがなされている。

【０００３】第一の従来例として、特開平７−２２５８
４３号公報の従来例での説明がある（以下、従来例１と
略す）。

【０００４】尾根を構成するセルは、そのセルで高さ
（セルの値）が急激に変化する。このようなセルでは、
微分の絶対値が大きいので、微分フィルタによって２次
元投影データをフィルタリングし、その絶対値が大きい
セルを、尾根を構成するセルとする。微分フィルタとし
て、図９に示すようなラプラシアンフィルタを例示して
いる。

【０００５】尾根を構成するセルをセル列として抽出す
るために、図１０に示すような８点近傍セルのセルの高
さＺについて、以下の４条件のうち２条件以上を満たし
ていれば、尾根を構成するセルとして見なすことにす
る。Ｚ＞＝ＺｏかつＺ＞＝Ｚ４、Ｚ＞＝Ｚ１かつＺ＞＝
Ｚ５、Ｚ＞＝Ｚ２かつＺ＞＝Ｚ６、Ｚ＞＝Ｚ３かつＺ＞
＝Ｚ７。これを図７のＸ＝５７〜７２，Ｙ＝６０〜８０
の範囲に適用し尾根を構成するセルを抽出したのが図１
１である。図中の数は高さＺを小数点以下を四捨五入し
たものである。セルを抽出後、隣接するものを接続す
る。このとき枝分かれする場合もあるが、短い枝を除去
し、長い枝については曲率が最小となるようなセル列の
み残して他は接続を切断して枝分かれのないセル列とす
る。

【０００６】第２の従来例として、特開平７−２８０７
４６号公報の実施例での説明がある（以下、従来例２と
略す）。

【０００７】高さが最大のセルを検出する。検出された
セルの座標と高さは注目セルとして記憶される。

【０００８】まず、２次元投影データからの注目セルの
座標を（Ａ，Ｂ）とすると、指定方向に１セルずれた位
置に並ぶ３（ないし４）セル（Ａ−１，Ｂ−１），
（Ａ，Ｂ−１），（Ａ＋１，Ｂ−１）のセルの高さ情報
を比較し最も大きかったセルを次の注目セルとし、さら
に１セルずれた位置に並ぶ３（ないし４）セルの高さ情
報を比較し最も大きかったセルを次の注目画素とするよ
うにこれを末端まで続ける。

【０００９】これを、従来例１に用いたものと同じ２次
元投影データに適用したものが図１２である。

【００１０】

【発明が解決しようとしている課題】しかしながら、従
来例１では２次元投影データのセル要素すべてについ
て、それが尾根を構成するものであるかどうかラプラシ
アンフィルタで走査して調べる必要があり、計算機負荷
を大きくしていた。また、図１１の座標（６１，６
３），（６１，６６）に示した様に尾根を構成するセル
の座標が不連続になった地点では、隣接セル座標（６
１，６６）を探し出すための特殊なアルゴリズムを要す
る。さらに、座標（６９，７５）のような飛び地に対す
る処理もしなければならない。また、たとえば図１１中
の座標（６３，７０），（６３，７１），（６４，７
１）に見られるようなＬ字型クランクを座標（６３，７
０）と座標（６４，７１）を結ぶ斜めの線分で表すよ
う、曲率を計算し細線化処理を施さねばならない。

【００１１】一方、従来例２では、従来例１で示された
座標（６８，７８）から座標（６９，７８）までのＸ軸
方向に沿った尾根を検出できておらず、図１２からわか
る通り間違った尾根を検出している。

【００１２】本発明は、このような状況のもとでなされ
たもので、２次元データから１本の尾根曲線を抽出する
簡単で正確な装置，方法を提供することを目的とするも
のである。

【００１３】

【課題を解決するための手段】前記目的を達成するた
め、本発明では、２次元データから尾根を抽出する装置
を次の（１），（５），（６）の通りに構成し、２次元
データから尾根を抽出する方法を次の（２），（７），
（８）の通りに構成し、プログラムを（３），（９）の
通りに構成し、記憶媒体を次の（４），（１０）の通り
に構成する。

【００１４】（１）２次元データから尾根を抽出する装
置であって、前記２次元データを２次元格子状に配列さ
れたセルと見なし、それぞれのセルに少なくともセルの
値と参照有無を示す状態値を持つルックアップデータテ
ーブルを有し、前記ルックアップデータテーブルにおけ
るセルの値が最大のセルを抽出する手段１１と、前記手
段１１で抽出したセルの値が最大のセルを出発点とし逐
次近傍領域を決定する手段１２と、前記２次元データの
性質をあらかじめ８点近傍セルヘの遷移確率の重みづけ
により表現する手段と、近傍領域が測定範囲外であるこ
とを検出することで尾根を構成するセルの終点であるか
否かを判断する手段１３と、近傍領域として参照された
か否かの識別フラグを立てる手段１４と、近傍極大セル
座標を検出する手段１５と、前記手段１５で検出した極
大セルが複数であるか否かを判定する手段１６と、該極
大セルが複数であった場合にその座標をスタック記憶す
る手段２０と、前記手段１５で検出した極大セルが単数
であった場合にすでにスタック記憶されたセル座標があ
るか否かを判断する手段１７ａと、前記手段１７ａの判
断がすでにスタック記憶されたセル座標があった場合に
重みづけと最短化に従いスタックされたセル座標を尾根
線として登録する手段１８ａと、前記手段１５で検出さ
れた単数の近傍極大セル座標を尾根線として登録する手
段１９と、前記手段１３において終点と判断された場合
にすでにスタック記憶されたセル座標があるか否かを判
断する手段１７ｂと、前記手段１７ｂの判断がすでにス
タック記憶されたセル座標があった場合に重みづけと最
短化に従いスタックされたセル座標を尾根線として登録
する手段１８ｂと、セルの値最大のセル座標からの尾根
線が１本のみであるか否かを判定する手段２１と、前記
手段２１での判定がセルの値最大のセル座標からの尾根
線が１本のみであった場合、再度セルの値最大のセル座
標近傍の参照有無フラグを該１本の尾根を構成するセル
座標近傍に対してのみ立て直す手段２２と、セルの値最
大のセル座標からの尾根線が１本のみでない場合に尾根
検出を終了する手段とを備えた２次元データから尾根を
抽出する装置。

【００１５】（２）２次元データから１本の尾根曲線を
抽出する方法であって、前記２次元データを２次元格子
状に配列されたセルと見なし、それぞれのセルに少なく
ともセルの値と参照有無を示す状態値を持つルックアッ
プデータテーブルを有し、前記ルックアップデータテー
ブルにおけるセルの値が最大のセルを抽出する工程１１
と、前記手段１１で抽出したセルの値が最大のセルを出
発点とし逐次近傍領域を決定する工程１２と、前記２次
元データの性質をあらかじめ８点近傍セルヘの遷移確率
の重みづけにより表現する工程と、近傍領域が測定範囲
外であることを検出することで尾根を構成するセルの終
点であるか否かを判断する工程１３と、近傍領域として
参照されたか否かの識別フラグを立てる工程１４と、近
傍極大セル座標を検出する工程１５と、前記手段１５で
検出した極大セルが複数であるか否かを判定する工程１
６と、該極大セルが複数であった場合にその座標をスタ
ック記憶する工程２０と、前記手段１５で検出した極大
セルが単数であった場合にすでにスタック記憶されたセ
ル座標があるか否かを判断する工程１７ａと、前記手段
１７ａの判断がすでにスタック記憶されたセル座標があ
った場合に重みづけと最短化に従いスタックされたセル
座標を尾根線として登録する工程１８ａと、前記工程１
５で検出された単数の近傍極大セル座標を尾根線として
登録する工程１９と、前記工程１３において終点と判断
された場合にすでにスタック記憶されたセル座標がある
か否かを判断する工程１７ｂと、前記工程１７ｂの判断
がすでにスタック記憶されたセル座標があった場合に重
みづけと最短化に従いスタックされたセル座標を尾根線
として登録する工程１８ｂと、セルの値最大のセル座標
からの尾根線が１本のみであるか否かを判定する工程２
１と、前記工程２１での判定がセルの値最大のセル座標
からの尾根線が１本のみであった場合、再度セルの値最
大のセル座標近傍の参照有無フラグを該１本の尾根を構
成するセル座標近傍に対してのみ立て直す工程２２と、
セルの値最大のセル座標からの尾根線が１本のみでない
場合に尾根検出を終了する工程とを備えた２次元データ
から尾根を抽出する方法。

【００１６】（３）前記（２）記載の方法を実現するた
めのプログラム。

【００１７】（４）前記（３）記載のプログラムを格納
した記憶媒体。

【００１８】（５）２次元正方格子状に配列された画素
のそれぞれに画素値が対応している２次元画像データか
ら、１本の尾根曲線を抽出する装置であって、画素値が
最大の画素であるところの最大画素を与える手段５１
と、尾根画素集合を空にする手段５２と、最大画素を尾
根画素集合に登録する手段５３と、終了するかどうか判
定する手段５４と、尾根画素集合に含まれる画素に隣接
する画素の集合であるところの隣接画素集合を逐次決定
する手段５５と、隣接画素集合から、尾根曲線に含まれ
る画素を除く手段６５と、隣接画素集合から尾根曲線に
含まれる画素を抽出する手段５７と、尾根曲線に含まれ
る画素を互いに隣接している画素同士であるところの隣
接尾根画素集合に分類する手段５８と、隣接尾根画素集
合の一つを選択する手段５９と、隣接尾根画素集合に含
まれる画素の全てを尾根曲線に登録する手段６０と、尾
根画素集合を空にする手段６１と、尾根曲線に含まれる
画素の集合に含まれる画素の全てを尾根画素集合に登録
する手段６２と、を備えた２次元データから尾根を抽出
する装置。

【００１９】（６）前記（５）記載の２次元データから
尾根を抽出する装置において、手段５７は、隣接画素集
合に含まれる各画素について、該画素に隣接し隣接画素
集合に含まれる画素の数を調べ、数が２であり、該画素
に隣接し隣接画素集合に含まれる画素の画素値と該画素
の画素値を比較し、該画素の画素値が最も大きい場合
に、該画素を抽出するという手段であることを特徴とす
る２次元データから尾根を抽出する装置。

【００２０】（７）２次元正方格子状に配列された画素
のそれぞれに画素値が対応している２次元画像データか
ら、１本の尾根曲線を抽出する方法であって、画素値が
最大の画素であるところの最大画素を与える工程５１
と、尾根画素集合を空にする工程５２と、最大画素を尾
根画素集合に登録する工程５３と、終了するかどうか判
定する工程５４と、尾根画素集合に含まれる画素に隣接
する画素の集合であるところの隣接画素集合を逐次決定
する工程５５と、隣接画素集合から、尾根曲線に含まれ
る画素を除く工程６５と、隣接画素集合から尾根曲線に
含まれる画素の集合を抽出する工程５７と、尾根曲線に
含まれる画素を互いに隣接している画素同士である所の
隣接尾根画素集合に分類する工程５８と、隣接尾根画素
集合の一つを選択する工程５９と、隣接尾根画素集合に
含まれる画素の全てを尾根曲線に登録する工程６０と、
尾根画素集合を空にする工程６１と、尾根曲線に含まれ
る画素の集合に含まれる画素の全てを尾根画素集合に登
録する工程６２と、を備えた２次元データから尾根を抽
出する方法。

【００２１】（８）前記（７）記載の２次元データから
尾根を抽出する方法において、工程５７は、隣接画素集
合に含まれる各画素について、該画素に隣接し隣接画素
集合に含まれる画素の数を調べ、数が２であり、該画素
に隣接し隣接画素集合に含まれる画素の画素値と該画素
の画素値を比較し、該画素の画素値が最も大きい場合
に、該画素を抽出するという工程である２次元データか
ら尾根を抽出する方法。

【００２２】（９）前記（７）または（８）記載の方法
を実現するためのプログラム。

【００２３】（１０）前記（９）記載のプログラムを格
納した記憶媒体。

【００２４】

【発明の実施の形態】以下本発明の実施の形態を２次元
データから主たる一つの尾根を抽出する装置の実施例に
より詳しく説明する。なお、本発明は、装置の形に限ら
ず、実施例の説明に裏付けられて、方法の形で、またこ
の方法を実現するプログラムの形で、またこのプログラ
ムを格納したＣＤ−ＲＯＭなどの記憶媒体の形で実施す
ることができる。

【００２５】

【実施例】（実施例１）実施例１である“２次元データ
から主たる一つの尾根を抽出する装置”について説明す
る。

【００２６】本実施例でも、従来例同様に先ず図７のＸ
＝５７〜７２，Ｙ＝６０〜８０の範囲を処理する例によ
り説明する。以後、図１および図２を用いて本実施例を
説明する。

【００２７】まず、図７の２次元投影データを２次元格
子状に配列されたセルと見なし、それぞれのセルに少な
くとも高さ（セルの値、たとえば画素の濃度など）Ｚと
参照有無を示す状態値を持つルックアップデータテーブ
ルを用意する。

【００２８】図１のステップ１１（図ではＳ１１と表記
する、以下同様）に従い図２に示す２次元投影データか
らＺが最大となるセル座標（６３，７０）を検出し、記
憶する。次いで、ステップ１２に従い図２中の領域０で
示された８セルを近傍領域と決定する。ステップ１２で
近傍領域が見つからない場合、つまり測定領域外の場合
はステップ１３に従い終点とみなす。

【００２９】終点ではない場合、ステップ１４に従い領
域０のセルはすべて参照有無フラグが立てられる。これ
により、以降の尾根線抽出にはこれらのセルは参照され
なくする。ステップ１５に従い領域０から極大となるセ
ルを抽出すると、座標（６２，６９），（６３，７
１），（６４，７１）が検出される。本実施例では、２
次元投影データの性質をあらかじめ８近傍セルヘの遷移
確率の重みづけすることで特微づける。本実施例におい
ては図３に示すように重みづけされており、このことか
ら座標（６３、７１），（６４、７１）が最初の候補と
なる。複数（今の事例では２つ）のセルが候補に上がっ
た場合、図１のステップ２０に従い座標は一時スタック
記憶され、次の近傍領域決定のステップ１２へとループ
する。ここで、参照有無フラグを参照することで、尾根
を構成するセルの候補、つまり近傍領域は、先の領域０
のセルを除き、図２の領域１に示したような領域とな
る。ここでも、終点ではないので領域１のセルには参照
有無フラグが立てられ、以降の尾根線抽出には参照され
ないようにする。この領域１の極大は座標（６４，７
２）のセルただ１つであるから、図１のステップ１７ａ
の判定によりステップ１８ａに進み、まず、最大セル座
標（６３，７０）の次のセルとしてスタックされた２つ
の座標のうち座標（６３，７１）が重みづけによって選
ばれ、これらと（６４，７２）を結んだ線が尾根を構成
するセルとして抽出される。こうすることにより、Ｌ字
型クランクが作られるのを避け細線化が図られる。

【００３０】次いで、図２において座標（６６，７６）
より（７１，８０）に至る過程を説明する。図１のアル
ゴリズムにしたがって尾根を構成するセルの抽出を行う
と座標（６６，７６）に到達する。このセルの近傍領域
として領域６が決定される。領域６のセルの参照有無フ
ラグを立てた後、極大セルを検出すると、（６６，７
７）と（６７，７７）の２つのセルがあるので、これは
図１のステップ１６の判定とステップ２０の操作に従い
一時セル座標がスタックされる。該２セルの近傍領域か
ら参照有無フラグが立っている領域を除いて領域７が近
傍領域として決定されるが、ここでも極大となるセルが
複数あるので、セル座標（６７，７８）と（６８，７
８）がスタック記憶される。

【００３１】同様の操作により、次なる近傍領域として
領域８が決定される。この領域での極大は座標（６９，
７８）のセルのみである。ここで、スタックが開始され
る以前のセル座標（６６，７６）とＸ方向、Ｙ方向の変
位を比較することで最短化に従い、それまでにスタック
記憶された座標のうち、（６７，７７），（６８，７
８）が選択される。このように、重みづけと最短化をス
タックしたセル座標に適用することでＬ字型クランクを
作らずに細線化がなされる。

【００３２】セル座標（６９，７８）での近傍領域は領
域９と決定され、参照有無フラグを領域９のセルに立て
た後、図１のステップ１６，１７ａ，１９を経て領域１
０を次の近傍領域として決定する。ここでステップ１５
によりセル座標（７１，８０）が極大として検出され、
ステップ１６，１７ａ，１９を経て尾根線を構成するセ
ルとして登録される。

【００３３】しかし、このセルの近傍領域決定を行おう
とすると、測定領域外を走査しようとするため、ステッ
プ１３の判定で「終点」と判断される。したがって、ス
テップは１７ｂへと進み、スタックされたセル座標がな
いのでステップ２１に進む。

【００３４】以上述べた一連の処理では、まだ高さ最大
セル座標から１本の尾根線しか作っていないので、ステ
ップ２２へ進む。

【００３５】ステップ２２では、領域０中の高さが最大
となる中央のセルと尾根線を構成する座標（６３，７
１）のセルとこれに隣接する領域０内のセルに参照有無
フラグを立て、それ以外の領域０内のセルの参照有無フ
ラグを下げるという参照有無フラグの立て直しを行う。
その後、ステップ１５の近傍極大セル座標検出により、
座標（６２，６９）が検出される。以降、セル座標（６
０，６２）までは前述同様の処理により到達する。

【００３６】セル座標（６０，６２）の近傍領域は領域
１８に決定されるが、極大が２セルある。

【００３７】したがって、この２つのセル座標はスタッ
ク記憶され、次なる近傍領域、領域１９の決定と極大セ
ル座標（５９，６０）の検出により、重みづけに従い座
標（５９，６１）が尾根を構成するセルとして選択さ
れ、次なる近傍領域決定において「終点」とステップ１
３により判定され、ステップ１７ｂを経てステップ２１
において高さ最大セル座標からの尾根線が２本となり、
処理終了に至る。

【００３８】次に、図７のＸ＝４６〜６１，Ｙ＝１７０
〜１９０の範囲を処理する例により説明する。

【００３９】まず、図１のステップ１１に従い２次元投
影データからＺが最大となるセル座標（５３，１８１）
を検出し、記憶する。次いで、ステップ１２に従い図４
中の領域１００で示された８セルを近傍領域と決定す
る。ステップ１２で近傍領域が見つからない場合つま
り、測定領域外の場合はステップ１３に従い終点とみな
す。

【００４０】終点ではない場合、ステップ１３に従い領
域１００のセルはすべて参照有無フラグが立てられる。
これにより、以降の尾根線抽出にはこれらのセルは参照
されなくする。ステップ１５に従い領域１００から極大
となるセルを抽出すると、座標（５３，１８２）が検出
される。図１のアルゴリズムに従えば、容易に第一の尾
根の終点セル座標（５３，１９０）に到達する。ここ
で、このセルの近傍領域決定を行おうとすると、測定領
域外を走査しようとするため、ステップ１３で「終点」
と判断される。

【００４１】したがって、ステップ１７ｂヘと進み、ス
タックされたセル座標がないのでステップ２１に進む。
以上述べた一連の処理では、まだ高さ最大セル座標から
１本の尾根線しか作っていないので、ステップ２２へ進
む。

【００４２】ステップ２２では、領域１００中の高さが
最大となる中央のセルと尾根線を構成する座標（５３，
１８２）のセルとこれに隣接する領域１００内のセル
（５２，１８２），（５４，１８２）に参照有無フラグ
を立て、それ以外の領域１００内のせるの参照有無フラ
グを下げるという参照有無フラグの立て直しを行う。そ
の後、ステップ１５の近傍極大セル座標検出により、座
標（５３，１８０）が検出される。以降、セル座標（５
４，１７４）までは同様の処理により到達する。

【００４３】セル座標（５４、１７４）の近傍領域は領
域１１６に決定されるが、極大が座標（５３，１７
２）、（５４，１７２）の２つのセルとなり、ステップ
２０により、スタック記憶される。次の近傍領域決定の
ステップ１２では、領域１１７が検出されるが、ここで
も極大が（５３，１７１），（５４，１７１）となり、
ステップ２０によりスタック記憶される。さらに、近傍
領域を検出し極大を見つけると（５３，１７０），（５
４，１７０），（５５，１７０）の３つのセルがスタッ
ク記憶されるが、ここでステップ１２の近傍領域決定手
段から終点であることが判断され、ステップ１３により
ステップ１７ｂに進む。ここで、スタック記憶されたセ
ル座標が、４階層、計９セルあるのでステップ１８ｂに
進み、重みづけにより所定のセルが選択され、図４に示
したように尾根線を形成して終了する。

【００４４】ステップ１７ａと１７ｂ、ステップ１８ａ
と１８ｂは、全く同じ処理を行っているため、一つの関
数としてまとめることもできる。

【００４５】以上説明したように、本実施例によれば、
簡単なアルゴリズムにより２次元データから主たる１本
の尾根を検出することが可能となり、重みづけと最短化
をスタックしたセル座標に適用することでＬ字型グラン
クを作らずに細線化がなされる。Ｚが画像の濃度であれ
ば、画像のエッジを検出することができる。

【００４６】（実施例２）実施例２である“２次元デー
タから主たる一つの尾根を抽出する装置”について説明
する。

【００４７】本実施例でも、実施例１と同様に図７のＸ
＝５７〜７２，Ｙ＝６０〜８０の範囲を処理する例によ
り説明する。

【００４８】図５および図６を用いて本実施例を説明す
る。まず、ステップ５１に従い図６の２次元投影データ
から高さ（画素の値、たとえば画素の濃度など）Ｚが最
大となる画素座標（６３，７０）を検出し、記憶する。

【００４９】また、ステップ５２に従い、尾根画素集合
を空にし、更にステップ５３に従い、尾根画素集合に画
素（６３，７０）が登録する。

【００５０】次いで、ステップ５４に従い、終了判定を
する。終了判定は、たとえば、尾根画素集合が画像の端
に位置しているか、或いは、尾根曲線が所望の長さにな
ったかどうかなどに基づいて判定され、得たい尾根曲線
の性質により、終了判定は異なる。

【００５１】次に、ステップ５５に従い図６中の領域０
で示された８つの画素を隣接画素集合と決定する。隣接
画素集合は、尾根画素集合に含まれる画素に隣接する画
素の集合から、尾根画素集合に含まれる画素そのものを
除いた集合である。現在は、尾根画素集合は、極大画素
ただ一つからなるため、隣接画素集合は８つの画素から
なる領域０である。

【００５２】次に、ステップ５６に従い、隣接画素集合
から尾根曲線に含まれる画素を除く。現在は、尾根曲線
は登録されていないので、画素は除かれない。

【００５３】次に、ステップ５７に従い、隣接画素集合
から、隣接する画素より画素値が大きいか等しい画素を
尾根曲線に含まれる画素として抽出する。これにより、
座標（６２，６９）、（６３，７１）、（６４，７１）
が抽出される。

【００５４】たとえば、（６２，６９）の値は２０４で
あり、隣接画素集合に含まれる、隣接する画素である
（６３，６９），（６２，７０）の値の２０２，２０３
よりも大きい。

【００５５】次に、ステップ５８に従い、尾根曲線に含
まれる画素を互いに隣接している画素同士である所の隣
接尾根画素集合に分類する。現在は、尾根曲線に含まれ
る画素として、（６２，６９）、（６３，７１）、（６
４，７１）の３つが抽出されているので、これらを、一
つ目の隣接尾根画素集合（６２，６９）と、二つ目の隣
接尾根画素集合（６３，７１）、（６４，７１）に分類
する。一回目にステップ５８を実行すると、必ず隣接尾
根画素集合Ａは二つ以上あるので、これらの中から、ど
れかを選択しなくてはならない。

【００５６】２回目の実行の時でも、尾根曲線が枝分か
れしている場合は、隣接尾根画素集合は２つあるので、
以下の処理を継続するために、どれかを選択しなくては
ならない。

【００５７】次に、ステップ５９に従い、隣接尾根画素
集合の一つを選択する。今回は画素（６３，７１）、
（６４，７１）を含む集合を選択した。選択の基準は本
実施例をどのように適用するかによって異なる。ステッ
プ５９を一回目に実行する時と、２回目以降に実行する
時で選択基準を変えても良いし、共通の基準を用いても
良い。Ｘ座標が大きいものを常に選択するといった基準
でも良いし、或いは選択しなかった集合を、後々の処理
のために保存しておいても良い。

【００５８】次に、ステップ６０に従い、隣接尾根画素
集合の各画素を尾根曲線に登録する。次に、ステップ６
１に従い、尾根画素集合を空にし、ステップ６２に従
い、尾根曲線に含まれる画素の集合を尾根画素集合に登
録する。

【００５９】次に、ステップ５４に従い終了判定をし、
ステップ５５に従い隣接画素集合を決定する。現在は尾
根画素集合が、図６に示すように、（６３，７１）、
（６４，７１）２画素である。このため、隣接画素集合
は、図６中の領域１に示す１０画素である。

【００６０】次に、ステップ５６に従い、隣接画素集合
から尾根曲線に含まれる画素を取り除く。現在は、隣接
画素集合に含まれ、尾根曲線に含まれる画素は（６３，
７０）だけであるので、これを除く。

【００６１】次に、ステップ５７に従い、隣接画素集合
から、尾根曲線に含まれる画素を抽出する。

【００６２】これにより、座標（６４，７２）が検出さ
れる。（６４，７２）は隣接する画素より画素値が大き
いか等しい。（６４，７２）の値は２０４であり、隣接
画素集合に含まれる隣接する画素である（６３，７
２），（６５，７２）の値の２０２，２０３よりも大き
い。なお、（６２，７０），（６４，７０）の２画素
は、隣接する画素集合に含まれる、隣接する画素が、そ
れぞれ（６２，７１），（６５，７０）の一つずつであ
るので、選ばれない。

【００６３】次に、ステップ５８に従い、尾根曲線に含
まれる画素を互いに隣接している画素同士である所の隣
接尾根画素集合に分類する。現在は、抽出された画素は
一つだけであるので、隣接尾根画素集合も一つだけであ
る。

【００６４】次に、ステップ５９に従い、隣接尾根画素
集合の一つを選択する。現在は隣接尾根画素集合が一つ
であるので、これを選択する。

【００６５】次に、ステップ６０に従い、隣接尾根画素
集合の画素（６４，７２）を尾根曲線に登録する。

【００６６】次に、ステップ６１に従い、尾根画素集合
を空にし、ステップ６２に従い、尾根画素集合に尾根画
素集合に含まれる各画素を登録する。

【００６７】次に、ステップ５４，５５の処理を行い、
図６中の領域２に示す画素が隣接画素集合として選ば
れ、ステップ５６ないし６０の処理を経て、（６５，７
３）が隣接尾根曲線に登録される。

【００６８】以上の処理を逐次的に行うことにより、尾
根の検出が行われる。

【００６９】以上説明したように、本実施例によれば、
簡単なアルゴリズムにより２次元投影データから主たる
１本の尾根が検出できる。

【００７０】

【発明の効果】以上説明したように、本発明によれば、
簡単なアルゴリズムにより２次元投影データから主たる
１本の尾根が検出できる。

【図面の簡単な説明】

【図１】 実施例１の処理を示すフローチャート

【図２】 実施例１による処理結果を示す図（その１）

【図３】 実施例１における近傍セルの重みづけを示す
図

【図４】 実施例１による処理結果を示す図（その２）

【図５】 実施例２の処理を示すフローチャート

【図６】 実施例２による処理結果の１部を示す図

【図７】 等高線を表示した図

【図８】 図７を肉眼で走査し尾根線を与えた図

【図９】 ラブラシアンフィルタを示す図

【図１０】 近傍セルの説明図

【図１１】 従来例１による尾根線検出を示す図

【図１２】 従来例２による尾根線検出を示す図

【符号の説明】

１１ 高さ最大セル座標検出手段 １２ 近傍領域決定手段 １４ 参照有無フラグを立てる手段 １５ 近傍極大座標検出手段 １７ａ，１７ｂ スタック記憶されたセル座標の有無判
断手段 １８ａ，１８ｂ 重みづけ／最短化に従いスタック記憶
されたセル座標を尾根線として登録する手段 １９ 近傍極大セルを尾根線として登録する手段 ２０ セル座標をスタック記憶する手段 ２２ 高さ最大セル近傍のセルの参照有無フラグを立て
直す手段

Claims (10)

【特許請求の範囲】
1. 【請求項１】 ２次元データから尾根を抽出する装置で
   あって、 前記２次元データを２次元格子状に配列されたセルと見
   なし、それぞれのセルに少なくともセルの値と参照有無
   を示す状態値を持つルックアップデータテーブルを有
   し、 前記ルックアップデータテーブルにおけるセルの値が最
   大のセルを抽出する手段１１と、 前記手段１１で抽出したセルの値が最大のセルを出発点
   とし逐次近傍領域を決定する手段１２と、 前記２次元データの性質をあらかじめ８点近傍セルヘの
   遷移確率の重みづけにより表現する手段と、 近傍領域が測定範囲外であることを検出することで尾根
   を構成するセルの終点であるか否かを判断する手段１３
   と、 近傍領域として参照されたか否かの識別フラグを立てる
   手段１４と、 近傍極大セル座標を検出する手段１５と、 前記手段１５で検出した極大セルが複数であるか否かを
   判定する手段１６と、該極大セルが複数であった場合に
   その座標をスタック記憶する手段２０と、 前記手段１５で検出した極大セルが単数であった場合に
   すでにスタック記憶されたセル座標があるか否かを判断
   する手段１７ａと、 前記手段１７ａの判断がすでにスタック記憶されたセル
   座標があった場合に重みづけと最短化に従いスタックさ
   れたセル座標を尾根線として登録する手段１８ａと、 前記手段１５で検出された単数の近傍極大セル座標を尾
   根線として登録する手段１９と、 前記手段１３において終点と判断された場合にすでにス
   タック記憶されたセル座標があるか否かを判断する手段
   １７ｂと、 前記手段１７ｂの判断がすでにスタック記憶されたセル
   座標があった場合に重みづけと最短化に従いスタックさ
   れたセル座標を尾根線として登録する手段１８ｂと、 セルの値最大のセル座標からの尾根線が１本のみである
   か否かを判定する手段２１と、 前記手段２１での判定がセルの値最大のセル座標からの
   尾根線が１本のみであった場合、再度セルの値最大のセ
   ル座標近傍の参照有無フラグを該１本の尾根を構成する
   セル座標近傍に対してのみ立て直す手段２２と、 セルの値最大のセル座標からの尾根線が１本のみでない
   場合に尾根検出を終了する手段とを備えたことを特徴と
   する２次元データから尾根を抽出する装置。
2. 【請求項２】 ２次元データから１本の尾根曲線を抽出
   する方法であって、 前記２次元データを２次元格子状に配列されたセルと見
   なし、それぞれのセルに少なくともセルの値と参照有無
   を示す状態値を持つルックアップデータテーブルを有
   し、 前記ルックアップデータテーブルにおけるセルの値が最
   大のセルを抽出する工程１１と、 前記手段１１で抽出したセルの値が最大のセルを出発点
   とし逐次近傍領域を決定する工程１２と、 前記２次元データの性質をあらかじめ８点近傍セルヘの
   遷移確率の重みづけにより表現する工程と、 近傍領域が測定範囲外であることを検出することで尾根
   を構成するセルの終点であるか否かを判断する工程１３
   と、 近傍領域として参照されたか否かの識別フラグを立てる
   工程１４と、 近傍極大セル座標を検出する工程１５と、 前記手段１５で検出した極大セルが複数であるか否かを
   判定する工程１６と、該極大セルが複数であった場合に
   その座標をスタック記憶する工程２０と、 前記手段１５で検出した極大セルが単数であった場合に
   すでにスタック記憶されたセル座標があるか否かを判断
   する工程１７ａと、 前記手段１７ａの判断がすでにスタック記憶されたセル
   座標があった場合に重みづけと最短化に従いスタックさ
   れたセル座標を尾根線として登録する工程１８ａと、 前記工程１５で検出された単数の近傍極大セル座標を尾
   根線として登録する工程１９と、 前記工程１３において終点と判断された場合にすでにス
   タック記憶されたセル座標があるか否かを判断する工程
   １７ｂと、 前記工程１７ｂの判断がすでにスタック記憶されたセル
   座標があった場合に重みづけと最短化に従いスタックさ
   れたセル座標を尾根線として登録する工程１８ｂと、 セルの値最大のセル座標からの尾根線が１本のみである
   か否かを判定する工程２１と、 前記工程２１での判定がセルの値最大のセル座標からの
   尾根線が１本のみであった場合、再度セルの値最大のセ
   ル座標近傍の参照有無フラグを該１本の尾根を構成する
   セル座標近傍に対してのみ立て直す工程２２と、 セルの値最大のセル座標からの尾根線が１本のみでない
   場合に尾根検出を終了する工程とを備えたことを特徴と
   する２次元データから尾根を抽出する方法。
3. 【請求項３】 請求項２記載の方法を実現するためのプ
   ログラム。
4. 【請求項４】 請求項３記載のプログラムを格納したこ
   とを特徴とする記憶媒体。
5. 【請求項５】 ２次元正方格子状に配列された画素のそ
   れぞれに画素値が対応している２次元画像データから、
   １本の尾根曲線を抽出する装置であって、 画素値が最大の画素であるところの最大画素を与える手
   段５１と、 尾根画素集合を空にする手段５２と、 最大画素を尾根画素集合に登録する手段５３と、 終了するかどうか判定する手段５４と、 尾根画素集合に含まれる画素に隣接する画素の集合であ
   るところの隣接画素集合を逐次決定する手段５５と、 隣接画素集合から、尾根曲線に含まれる画素を除く手段
   ５５と、 隣接画素集合から尾根曲線に含まれる画素を抽出する手
   段５７と、 尾根曲線に含まれる画素を互いに隣接している画素同士
   であるところの隣接尾根画素集合に分類する手段５８
   と、 隣接尾根画素集合の一つを選択する手段５９と、 隣接尾根画素集合に含まれる画素の全てを尾根曲線に登
   録する手段６０と、 尾根画素集合を空にする手段６１と、 尾根曲線に含まれる画素の集合に含まれる画素の全てを
   尾根画素集合に登録する手段６２と、を備えたことを特
   徴とする２次元データから尾根を抽出する装置。
6. 【請求項６】 請求項５記載の２次元データから尾根を
   抽出する装置において、 手段５７は、隣接画素集合に含まれる各画素について、
   該画素に隣接し隣接画素集合に含まれる画素の数を調
   べ、数が２であり、該画素に隣接し隣接画素集合に含ま
   れる画素の画素値と該画素の画素値を比較し、該画素の
   画素値が最も大きい場合に、該画素を抽出するという手
   段であることを特徴とする２次元データから尾根を抽出
   する装置。
7. 【請求項７】 ２次元正方格子状に配列された画素のそ
   れぞれに画素値が対応している２次元画像データから、
   １本の尾根曲線を抽出する方法であって、 画素値が最大の画素であるところの最大画素を与える工
   程５１と、 尾根画素集合を空にする工程５２と、 最大画素を尾根画素集合に登録する工程５３と、 終了するかどうか判定する工程５４と、 尾根画素集合に含まれる画素に隣接する画素の集合であ
   るところの隣接画素集合を逐次決定する工程５５と、 隣接画素集合から、尾根曲線に含まれる画素を除く工程
   ６５と、 隣接画素集合から尾根曲線に含まれる画素の集合を抽出
   する工程５７と、 尾根曲線に含まれる画素を互いに隣接している画素同士
   であるところの隣接尾根画素集合に分類する工程５８
   と、 隣接尾根画素集合の一つを選択する工程５９と、 隣接尾根画素集合に含まれる画素の全てを尾根曲線に登
   録する工程６０と、 尾根画素集合を空にする工程６１と、 尾根曲線に含まれる画素の集合に含まれる画素の全てを
   尾根画素集合に登録する工程６２と、を備えたことを特
   徴とする２次元データから尾根を抽出する方法。
8. 【請求項８】 請求項７記載の２次元データから尾根を
   抽出する方法において、 工程５７は、隣接画素集合に含まれる各画素について、
   該画素に隣接し隣接画素集合に含まれる画素の数を調
   べ、数が２であり、該画素に隣接し隣接画素集合に含ま
   れる画素の画素値と該画素の画素値を比較し、該画素の
   画素値が最も大きい場合に、該画素を抽出するという工
   程であることを特徴とする２次元データから尾根を抽出
   する方法。
9. 【請求項９】 請求項７または８記載の方法を実現する
   ためのプログラム。
10. 【請求項１０】 請求項９記載のプログラムを格納した
    ことを特徴とする記憶媒体。