JPH096969A - 輪郭抽出方法 - Google Patents
輪郭抽出方法Info
- Publication number
- JPH096969A JPH096969A JP7154363A JP15436395A JPH096969A JP H096969 A JPH096969 A JP H096969A JP 7154363 A JP7154363 A JP 7154363A JP 15436395 A JP15436395 A JP 15436395A JP H096969 A JPH096969 A JP H096969A
- Authority
- JP
- Japan
- Prior art keywords
- energy
- value
- contour
- control point
- processing
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
- 238000000605 extraction Methods 0.000 title claims description 23
- 238000000034 method Methods 0.000 claims abstract description 85
- 238000013459 approach Methods 0.000 claims description 8
- 238000012545 processing Methods 0.000 abstract description 33
- 238000004364 calculation method Methods 0.000 abstract description 13
- 230000004069 differentiation Effects 0.000 abstract description 11
- 241000270295 Serpentes Species 0.000 abstract description 10
- 238000010586 diagram Methods 0.000 description 12
- 239000013256 coordination polymer Substances 0.000 description 9
- 238000002924 energy minimization method Methods 0.000 description 8
- 230000007423 decrease Effects 0.000 description 4
- 238000011156 evaluation Methods 0.000 description 3
- 238000002474 experimental method Methods 0.000 description 2
- 238000007781 pre-processing Methods 0.000 description 1
- 238000003672 processing method Methods 0.000 description 1
Landscapes
- Image Analysis (AREA)
Abstract
(57)【要約】
【目的】 短い時間で正確に画像から物体の輪郭を抽出
すること。 【構成】 ＳＮＡＫＥＳにより画像から物体の輪郭を抽
出する際に、最初は計算コストが小さい微分によるエネ
ルギ極小化を行い（ステップＳ２）、エネルギが収束値
に近づいたら（ステップＳ３）、正確な輪郭を抽出でき
るＤＰ法によるエネルギ極小化に切り替える（ステップ
Ｓ５）。
すること。 【構成】 ＳＮＡＫＥＳにより画像から物体の輪郭を抽
出する際に、最初は計算コストが小さい微分によるエネ
ルギ極小化を行い（ステップＳ２）、エネルギが収束値
に近づいたら（ステップＳ３）、正確な輪郭を抽出でき
るＤＰ法によるエネルギ極小化に切り替える（ステップ
Ｓ５）。
Description
【０００１】
【産業上の利用分野】本発明は、“ＳＮＡＫＥＳ”と呼
ばれるエネルギ最小化原理による動的輪郭モデル（Acti
ve Contour Model）を用いた輪郭抽出方法に関し、特
に、短い処理時間で正確に画像から輪郭を抽出するため
の改良に関する。
ばれるエネルギ最小化原理による動的輪郭モデル（Acti
ve Contour Model）を用いた輪郭抽出方法に関し、特
に、短い処理時間で正確に画像から輪郭を抽出するため
の改良に関する。
【０００２】
【従来の技術】画像処理による形状や文字の認識等に必
要な画像の構造化の前処理として、従来、物体の輪郭を
画像から抽出する種々の方法が提案されている。
要な画像の構造化の前処理として、従来、物体の輪郭を
画像から抽出する種々の方法が提案されている。
【０００３】＜エッジトレース方法＞輪郭抽出方法の一
つにエッジトレース方法があげられる。エッジトレース
方法では、画像の濃度勾配を適当なしきい値により２値
化してエッジ画像を形成し、エッジ画像中の画素を順次
追跡することにより、輪郭を抽出する。
つにエッジトレース方法があげられる。エッジトレース
方法では、画像の濃度勾配を適当なしきい値により２値
化してエッジ画像を形成し、エッジ画像中の画素を順次
追跡することにより、輪郭を抽出する。
【０００４】しかし、エッジトレース方法には、輪郭線
が閉曲線にならない場合に輪郭抽出が失敗になるという
欠点がある。また、輪郭線が分岐している場合は輪郭抽
出を行うことが難しいという欠点もある。
が閉曲線にならない場合に輪郭抽出が失敗になるという
欠点がある。また、輪郭線が分岐している場合は輪郭抽
出を行うことが難しいという欠点もある。
【０００５】＜ＳＮＡＫＥＳによる輪郭抽出方法＞これ
に対し、エネルギ最小化原理による動的輪郭モデルが
“ＳＮＡＫＥＳ”と呼ばれて提案され、輪郭抽出に利用
されている。以下、これについて説明する。
に対し、エネルギ最小化原理による動的輪郭モデルが
“ＳＮＡＫＥＳ”と呼ばれて提案され、輪郭抽出に利用
されている。以下、これについて説明する。
【０００６】ＳＮＡＫＥＳなる動的輪郭モデルは図４に
示すようにｎ個の制御点（頂点）ＣＰ1 〜ＣＰn を持つ
多角形１で定義される。つまり、各制御点ＣＰi （ｉ＝
１〜ｎ）の位置座標を（Ｘi ，Ｙi ）で表わすと、それ
らの集合Ｓ＝｛（Ｘi ，Ｙi），ｉ＝１，２，…，ｎ｝
が一つの輪郭モデルとなり、この輪郭モデルの各制御点
の間隔が或る程度密ならば、物体の輪郭としての閉曲線
を表わすことができる。
示すようにｎ個の制御点（頂点）ＣＰ1 〜ＣＰn を持つ
多角形１で定義される。つまり、各制御点ＣＰi （ｉ＝
１〜ｎ）の位置座標を（Ｘi ，Ｙi ）で表わすと、それ
らの集合Ｓ＝｛（Ｘi ，Ｙi），ｉ＝１，２，…，ｎ｝
が一つの輪郭モデルとなり、この輪郭モデルの各制御点
の間隔が或る程度密ならば、物体の輪郭としての閉曲線
を表わすことができる。
【０００７】そこで図５に示すように、まず輪郭抽出の
対象となる物体２の周囲に多角形の初期輪郭Ｃini を設
定し、次いで各制御点ＣＰi の位置座標（Ｘi ，Ｙi ）
を更新して最適化することにより物体２の輪郭に輪郭線
Ｃfin を張り付ける。この輪郭線Ｃini が抽出結果であ
る。
対象となる物体２の周囲に多角形の初期輪郭Ｃini を設
定し、次いで各制御点ＣＰi の位置座標（Ｘi ，Ｙi ）
を更新して最適化することにより物体２の輪郭に輪郭線
Ｃfin を張り付ける。この輪郭線Ｃini が抽出結果であ
る。
【０００８】＜評価関数＞制御点の位置座標の最適化に
は、一般に次式（１）の評価関数で与えられるエネルギ
Ｅ(C) を用いて、エネルギＥ(C) を最小化（厳密には極
小化）するように制御点の位置座標を更新する。
は、一般に次式（１）の評価関数で与えられるエネルギ
Ｅ(C) を用いて、エネルギＥ(C) を最小化（厳密には極
小化）するように制御点の位置座標を更新する。
【数１】 Ｅ(C) ＝α・Ｅint (C) −β・Ｅext (C) …式（１）
【０００９】式（１）中で、αとβは定数、「・」は乗
算記号、Ｅint (C) は輪郭モデルＣの幾何学的拘束条件
のエネルギ（内部エネルギ）、Ｅext (C) は輪郭モデル
Ｃの画像エネルギ（外部エネルギ）をそれぞれ表わして
いる。
算記号、Ｅint (C) は輪郭モデルＣの幾何学的拘束条件
のエネルギ（内部エネルギ）、Ｅext (C) は輪郭モデル
Ｃの画像エネルギ（外部エネルギ）をそれぞれ表わして
いる。
【００１０】幾何学的拘束条件としては隣接する制御点
間の距離と、滑らかさが用いられ、そのエネルギＥint
(C) は次式（２）で与えられる。なお、式（２）の右辺
第１項が距離に関する成分、同第２項が滑らかさに関す
る成分である。従って、制御点間で距離が短いほど、ま
た滑らかであるほど、エネルギＥ(C) が小さくなる。
間の距離と、滑らかさが用いられ、そのエネルギＥint
(C) は次式（２）で与えられる。なお、式（２）の右辺
第１項が距離に関する成分、同第２項が滑らかさに関す
る成分である。従って、制御点間で距離が短いほど、ま
た滑らかであるほど、エネルギＥ(C) が小さくなる。
【数２】 α・Ｅint (C) ＝α1 ・Σ｛（Ｘi −Ｘi-1)2 ＋（Ｙi −Ｙi-1)2 ｝＋ α2 ・Σ｛（２Ｘi −Ｘi-1 −Ｘi+1)2 ＋ （２Ｙi −Ｙi-1 ＋Ｙi+1)2 ｝ …式（２）
【００１１】画像エネルギＥext (C) としては、画像中
における輪郭モデルＣ上の平均エッジ強度が用いられ、
微分画像における各制御点ＣＰi （Ｘi ，Ｙi ）での画
素値をＧ（Ｘi ，Ｙi ）とすると、次式（３）で与えら
れる。従って、各制御点が物体２の輪郭に近いほど、エ
ネルギＥ(C) が小さくなる。
における輪郭モデルＣ上の平均エッジ強度が用いられ、
微分画像における各制御点ＣＰi （Ｘi ，Ｙi ）での画
素値をＧ（Ｘi ，Ｙi ）とすると、次式（３）で与えら
れる。従って、各制御点が物体２の輪郭に近いほど、エ
ネルギＥ(C) が小さくなる。
【数３】 Ｅext (C) ＝ΣＧ（Ｘi ，Ｙi ） …式（３）
【００１２】評価関数Ｅ(C) を用いたエネルギの極小化
には、下記２つの処理手法がある。
には、下記２つの処理手法がある。
【００１３】＜第１の処理：微分によるエネルギ極小化
手法＞通常、各制御点ＣＰi （Ｘi ，Ｙi ）でエネルギ
Ｅ(C) の微分値Δｖi ＝（ΔＸi ，ΔＹi ）を計算し、
この微分値に基づいて制御点ＣＰi の位置座標を
（Ｘ i ，Ｙi ）から（Ｘi ′，Ｙi ′）＝（Ｘi ＋ΔＸ
i ，Ｙi ＋ΔＹi ）に更新することにより、エネルギＥ
(C) が極小になる輪郭線Ｃfin を求める。この手法を第
１の処理と呼ぶ。次式（４）に制御点での微分及び位置
座標更新の式を示す。
手法＞通常、各制御点ＣＰi （Ｘi ，Ｙi ）でエネルギ
Ｅ(C) の微分値Δｖi ＝（ΔＸi ，ΔＹi ）を計算し、
この微分値に基づいて制御点ＣＰi の位置座標を
（Ｘ i ，Ｙi ）から（Ｘi ′，Ｙi ′）＝（Ｘi ＋ΔＸ
i ，Ｙi ＋ΔＹi ）に更新することにより、エネルギＥ
(C) が極小になる輪郭線Ｃfin を求める。この手法を第
１の処理と呼ぶ。次式（４）に制御点での微分及び位置
座標更新の式を示す。
【００１４】
【数４】
【００１５】＜第２の処理：ＤＰ法によるエネルギ極小
化手法＞別の手法として、ＤＰ法（Dynamic Programin
g：動的計画法）を用いてエネルギを極小化する手法が
提案されている。この手法を第２の処理と呼び、以下に
説明する。
化手法＞別の手法として、ＤＰ法（Dynamic Programin
g：動的計画法）を用いてエネルギを極小化する手法が
提案されている。この手法を第２の処理と呼び、以下に
説明する。
【００１６】式（１）と式（２）を見ると、ｉ番目の制
御点ＣＰi のエネルギは、ｉ−１番目の制御点ＣＰi-1
の位置座標（Ｘi-1 ，Ｙi-1 ）とｉ＋１番目の制御点Ｃ
Ｐi+ 1 の位置座標（Ｘi+1 ，Ｙi+1 ）との関数になって
いる。そこで、ｉ番目の制御点ＣＰi のエネルギをＥi
として次式（５）で表わす。
御点ＣＰi のエネルギは、ｉ−１番目の制御点ＣＰi-1
の位置座標（Ｘi-1 ，Ｙi-1 ）とｉ＋１番目の制御点Ｃ
Ｐi+ 1 の位置座標（Ｘi+1 ，Ｙi+1 ）との関数になって
いる。そこで、ｉ番目の制御点ＣＰi のエネルギをＥi
として次式（５）で表わす。
【数５】 Ｅi ＝α1 ・｛（Ｘi −Ｘi-1)2 ＋（Ｙi −Ｙi-1)2 ｝ ＋α2 ・｛（２Ｘi −Ｘi-1 −Ｘi+1)2 ＋ ＋（２Ｙi −Ｙi-1 −Ｙi+1)2 ｝ −β・Ｇ（Ｘi ，Ｙi ） …式（５）
【００１７】但し、Ｇ（Ｘi ，Ｙi ）は原画像を微分し
て得られた画像の、位置座標（Ｘi，Ｙi ）における画
素値である。
て得られた画像の、位置座標（Ｘi，Ｙi ）における画
素値である。
【００１８】次に、１番目からｉ−２番目の制御点の位
置座標が既に決定しているものと仮定して、ｉ−１番目
の制御点の位置座標を更新する場合の手順を説明する。
置座標が既に決定しているものと仮定して、ｉ−１番目
の制御点の位置座標を更新する場合の手順を説明する。
【００１９】まず、図６に示すように９行９列のテーブ
ル３を作成する。このテーブル３には、ｉ−１番目の制
御点のエネルギを計算する際、ｉ−１番目の制御点を図
７（Ａ）に示すように更新前の位置座標（Ｘi-1 ，Ｙ
i-1 ）の８近傍動かし、且つ、ｉ番目の制御点を図７
（Ｂ）に示すように更新前の位置座標（Ｘi ，Ｙi ）の
８近傍動かすことによってそれらの全ての組合せに対し
て計算されるｉ−１番目の制御点のエネルギの値が入っ
ている。ここで、ｉ−ｉ番目の制御点の８近傍の各位置
をｐ（１≦ｐ≦９）、ｉ番目の制御点の８近傍の各位置
をｑ（１≦ｑ≦９）で表わし、テーブル３の該当する位
置（ｐ，ｑ）の各エネルギ値をＴ［ｐ］［ｑ］とする。
ル３を作成する。このテーブル３には、ｉ−１番目の制
御点のエネルギを計算する際、ｉ−１番目の制御点を図
７（Ａ）に示すように更新前の位置座標（Ｘi-1 ，Ｙ
i-1 ）の８近傍動かし、且つ、ｉ番目の制御点を図７
（Ｂ）に示すように更新前の位置座標（Ｘi ，Ｙi ）の
８近傍動かすことによってそれらの全ての組合せに対し
て計算されるｉ−１番目の制御点のエネルギの値が入っ
ている。ここで、ｉ−ｉ番目の制御点の８近傍の各位置
をｐ（１≦ｐ≦９）、ｉ番目の制御点の８近傍の各位置
をｑ（１≦ｑ≦９）で表わし、テーブル３の該当する位
置（ｐ，ｑ）の各エネルギ値をＴ［ｐ］［ｑ］とする。
【００２０】続いて、図８に示すように、９行９列の同
様なテーブル４を作成する。但し、このテーブル４に
は、ｉ番目の制御点を図９（Ａ）に示すように更新前の
位置座標（Ｘi ，Ｙi ）の８近傍動かし、且つｉ＋１番
目の制御点を図９（Ｂ）に示すように更新前の位置座標
（Ｘi+1 ，Ｙi+1 ）の８近傍動かすことによってそれら
の全ての組合せに対して計算されるｉ番目の制御点のエ
ネルギの値が入っている。ここでは、ｉ番目の制御点の
８近傍の各位置をｑ（１≦ｑ≦９）、ｉ＋１番目の制御
点の８近傍の各位置をｒ（１≦ｒ≦９）で表わし、テー
ブル４の該当する位置（ｑ，ｒ）の各エネルギ値を便宜
上Ｔn ［ｑ］［ｒ］とする。
様なテーブル４を作成する。但し、このテーブル４に
は、ｉ番目の制御点を図９（Ａ）に示すように更新前の
位置座標（Ｘi ，Ｙi ）の８近傍動かし、且つｉ＋１番
目の制御点を図９（Ｂ）に示すように更新前の位置座標
（Ｘi+1 ，Ｙi+1 ）の８近傍動かすことによってそれら
の全ての組合せに対して計算されるｉ番目の制御点のエ
ネルギの値が入っている。ここでは、ｉ番目の制御点の
８近傍の各位置をｑ（１≦ｑ≦９）、ｉ＋１番目の制御
点の８近傍の各位置をｒ（１≦ｒ≦９）で表わし、テー
ブル４の該当する位置（ｑ，ｒ）の各エネルギ値を便宜
上Ｔn ［ｑ］［ｒ］とする。
【００２１】次に、テーブル３のエネルギ値Ｔ［ｐ］
［ｑ］とテーブル４のエネルギ値Ｔn［ｑ］［ｒ］との
和Ｔ［ｐ］［ｒ］＋Ｔn ［ｑ］［ｒ］を、全ての８近傍
位置ｐ，ｑ，ｒの組合せについて計算し、そのうち最小
となる組合せにおけるｉ−１番目の制御点の８近傍の位
置ｐを、新たなｉ−１番目の制御点の位置座標とする。
［ｑ］とテーブル４のエネルギ値Ｔn［ｑ］［ｒ］との
和Ｔ［ｐ］［ｒ］＋Ｔn ［ｑ］［ｒ］を、全ての８近傍
位置ｐ，ｑ，ｒの組合せについて計算し、そのうち最小
となる組合せにおけるｉ−１番目の制御点の８近傍の位
置ｐを、新たなｉ−１番目の制御点の位置座標とする。
【００２２】再びｉ番目の制御点に着目して、ｉ＋１番
の制御点の８近傍移動とｉ＋２番目の制御点の８近傍移
動から順次テーブルを２つ作成し、上記と同じ手順を繰
り返してｉ番目の制御点の位置座標を決定し、これを全
制御点について行う。
の制御点の８近傍移動とｉ＋２番目の制御点の８近傍移
動から順次テーブルを２つ作成し、上記と同じ手順を繰
り返してｉ番目の制御点の位置座標を決定し、これを全
制御点について行う。
【００２３】このような制御点の位置座標更新を、エネ
ルギＥ(C) が極小値に達するまで繰り返す。
ルギＥ(C) が極小値に達するまで繰り返す。
【００２４】
【発明が解決しようとする課題】第１の処理即ち、微分
によるエネルギ極小化手法では、ｉ番目の制御点のエネ
ルギはｉ−１番目の制御点の位置とｉ＋１番目の制御点
の位置に依存しているにも拘らず、これら２つの点を固
定したままエネルギの極小化を行っているので収束性が
悪く、エネルギが振動する等の欠点がある。そのため、
輪郭の抽出結果が悪い。図１０，図１１に実験結果を示
す。図１０の楕円５が抽出対象となる物体であり、図１
１の外側の閉曲線Ｃini が初期輪郭であり、内側の閉曲
線Ｃfin が抽出結果である。
によるエネルギ極小化手法では、ｉ番目の制御点のエネ
ルギはｉ−１番目の制御点の位置とｉ＋１番目の制御点
の位置に依存しているにも拘らず、これら２つの点を固
定したままエネルギの極小化を行っているので収束性が
悪く、エネルギが振動する等の欠点がある。そのため、
輪郭の抽出結果が悪い。図１０，図１１に実験結果を示
す。図１０の楕円５が抽出対象となる物体であり、図１
１の外側の閉曲線Ｃini が初期輪郭であり、内側の閉曲
線Ｃfin が抽出結果である。
【００２５】第２の処理即ち、ＤＰ法によるエネルギ極
小化手法では、第１の処理の欠点が解決して図１２に示
す閉曲線Ｃfin のように良好な抽出結果が得られる。し
かし、第２の処理では計算量が非常に多くなり、収束に
非常に時間がかかってしまう。因みに、制御点数がｎの
場合の計算コストは、第１の処理ではｎに比例するが、
第２の処理ではｎの３乗に比例する。
小化手法では、第１の処理の欠点が解決して図１２に示
す閉曲線Ｃfin のように良好な抽出結果が得られる。し
かし、第２の処理では計算量が非常に多くなり、収束に
非常に時間がかかってしまう。因みに、制御点数がｎの
場合の計算コストは、第１の処理ではｎに比例するが、
第２の処理ではｎの３乗に比例する。
【００２６】そこで本発明の課題は、第２の処理よりも
短い処理時間で且つ第１の処理よりも正確に、画像から
物体の輪郭を抽出することができる方法を提供すること
である。
短い処理時間で且つ第１の処理よりも正確に、画像から
物体の輪郭を抽出することができる方法を提供すること
である。
【００２７】
【課題を解決するための手段】上記課題を解決する本発
明の輪郭抽出方法は、複数の制御点からなる動的輪郭モ
デルを用い、制御点の位置座標の関数として与えられる
エネルギが極小となるように制御点の位置座標を更新す
ることにより画像から物体の輪郭を抽出する輪郭抽出方
法において、（１）各制御点でエネルギの微分値を計算
し、微分値に基づいて各制御点の位置座標を更新する第
１の処理を、エネルギが収束値に近づくまで行うこと、
（２）第１の処理でエネルギが収束値に近づいた後は、
動的計画法によりエネルギが極小となる制御点の位置座
標を決定する第２の処理を行うこと、を特徴とするもの
である。
明の輪郭抽出方法は、複数の制御点からなる動的輪郭モ
デルを用い、制御点の位置座標の関数として与えられる
エネルギが極小となるように制御点の位置座標を更新す
ることにより画像から物体の輪郭を抽出する輪郭抽出方
法において、（１）各制御点でエネルギの微分値を計算
し、微分値に基づいて各制御点の位置座標を更新する第
１の処理を、エネルギが収束値に近づくまで行うこと、
（２）第１の処理でエネルギが収束値に近づいた後は、
動的計画法によりエネルギが極小となる制御点の位置座
標を決定する第２の処理を行うこと、を特徴とするもの
である。
【００２８】あるいは、本発明の輪郭抽出方法は、上記
に加えて、第１の処理を繰り返して行い今回のエネルギ
が前回のエネルギよりも増大した時にエネルギが収束値
に近づいたと判定し、前記第２の処理は制御点の位置座
標をエネルギ増加直前の状態に戻してから開始すること
を特徴とし、あるいは、第１の処理を繰り返して行い今
回のエネルギが前回のエネルギに一致した時にエネルギ
が収束値に近づいたと判定し、直ちに前記第２の処理を
開始することを特徴とし、あるいは、第１の処理を繰り
返して行いエネルギの傾きが予め定めたしきい値を越え
た時にエネルギが収束値に近づいたと判定することを特
徴とし、あるいは前記しきい値はゼロ近傍の負の値であ
ることを特徴とするものである。
に加えて、第１の処理を繰り返して行い今回のエネルギ
が前回のエネルギよりも増大した時にエネルギが収束値
に近づいたと判定し、前記第２の処理は制御点の位置座
標をエネルギ増加直前の状態に戻してから開始すること
を特徴とし、あるいは、第１の処理を繰り返して行い今
回のエネルギが前回のエネルギに一致した時にエネルギ
が収束値に近づいたと判定し、直ちに前記第２の処理を
開始することを特徴とし、あるいは、第１の処理を繰り
返して行いエネルギの傾きが予め定めたしきい値を越え
た時にエネルギが収束値に近づいたと判定することを特
徴とし、あるいは前記しきい値はゼロ近傍の負の値であ
ることを特徴とするものである。
【００２９】
【作用】第１の処理は微分によるエネルギ極小化手法で
あり、前述の如く、計算コストは小さいが、エネルギが
極小値に近づくと振動して収束性が悪く輪郭抽出結果が
良くない。これに対して第２の処理はＤＰ法によるエネ
ルギ極小化手法であり、前述の如く、輪郭抽出結果は正
確であるが、計算コストが高い。
あり、前述の如く、計算コストは小さいが、エネルギが
極小値に近づくと振動して収束性が悪く輪郭抽出結果が
良くない。これに対して第２の処理はＤＰ法によるエネ
ルギ極小化手法であり、前述の如く、輪郭抽出結果は正
確であるが、計算コストが高い。
【００３０】そこで本発明では、ＳＮＡＫＥＳにより輪
郭抽出を行う際に、エネルギが収束値に近づくまでは微
分によるエネルギ極小化手法により制御点の位置座標更
新を行い、その後はＤＰ法によるエネルギ極小化に切り
替える。これにより、全体として比較的小さい計算コス
ト即ち短い処理時間で、正確に輪郭を抽出することがで
きる。
郭抽出を行う際に、エネルギが収束値に近づくまでは微
分によるエネルギ極小化手法により制御点の位置座標更
新を行い、その後はＤＰ法によるエネルギ極小化に切り
替える。これにより、全体として比較的小さい計算コス
ト即ち短い処理時間で、正確に輪郭を抽出することがで
きる。
【００３１】エネルギが収束値に近づいたか否かの判定
方法は基本的には任意で良いが、第１の処理を繰り返す
場合にその都度得られる今回のエネルギを前回のエネル
ギと比較し、今回のエネルギが前回のエネルギより増大
した時、あるいは今回のエネルギが前回のエネルギに一
致した時に、エネルギが収束値に近づいたと判定する方
法が簡単である。但し、今回のエネルギが前回よりも増
大した時は、エネルギ増加直前の状態に制御点の位置座
標を戻してから第２の処理を開始すると、計算コストが
一層短かくなる。
方法は基本的には任意で良いが、第１の処理を繰り返す
場合にその都度得られる今回のエネルギを前回のエネル
ギと比較し、今回のエネルギが前回のエネルギより増大
した時、あるいは今回のエネルギが前回のエネルギに一
致した時に、エネルギが収束値に近づいたと判定する方
法が簡単である。但し、今回のエネルギが前回よりも増
大した時は、エネルギ増加直前の状態に制御点の位置座
標を戻してから第２の処理を開始すると、計算コストが
一層短かくなる。
【００３２】あるいは、エネルギは通常減小する方向に
向っているので、その傾きの符号が負であることに着目
すると、エネルギの傾きが或るしきい値を越えた時に、
エネルギが収束値に近づいたと判定する方法も簡単で良
い。この場合、しきい値は基本的に正負、ゼロいずれで
も良いが、ゼロ近傍の負の値にすると、計算コストが一
層短かくなる。
向っているので、その傾きの符号が負であることに着目
すると、エネルギの傾きが或るしきい値を越えた時に、
エネルギが収束値に近づいたと判定する方法も簡単で良
い。この場合、しきい値は基本的に正負、ゼロいずれで
も良いが、ゼロ近傍の負の値にすると、計算コストが一
層短かくなる。
【００３３】
【実施例】以下、図面を参照して本発明をその実施例と
ともに説明する。
ともに説明する。
【００３４】＜第１実施例＞図１を参照して本発明の第
１実施例に係る輪郭抽出方法を説明する。図１におい
て、“ＳＮＡＫＥＳ”により対象物体の周囲に初期輪郭
を設定し（ステップＳ１）、まずは第１の処理として、
微分によるエネルギ極小化を行う（ステップＳ２）。
１実施例に係る輪郭抽出方法を説明する。図１におい
て、“ＳＮＡＫＥＳ”により対象物体の周囲に初期輪郭
を設定し（ステップＳ１）、まずは第１の処理として、
微分によるエネルギ極小化を行う（ステップＳ２）。
【００３５】この微分によるエネルギ極小化では、前述
の通り、式（１）で与えられる内部エネルギＥint (C)
と外部エネルギＥext (C) からなるエネルギＥ(C) を用
い、全制御点について、式（４）の如く個々の制御点で
のエネルギＥ(C) の微分値を計算し得られた微分値に基
づいて同制御点の位置座標を更新する。
の通り、式（１）で与えられる内部エネルギＥint (C)
と外部エネルギＥext (C) からなるエネルギＥ(C) を用
い、全制御点について、式（４）の如く個々の制御点で
のエネルギＥ(C) の微分値を計算し得られた微分値に基
づいて同制御点の位置座標を更新する。
【００３６】基本的には、このような全制御点の位置座
標更新を繰り返して行う。
標更新を繰り返して行う。
【００３７】但し、全制御点の位置座標更新の都度エネ
ルギＥ(C) を計算し、今回のエネルギと前回のエネルギ
との大小関係を判定する（ステップＳ３）。
ルギＥ(C) を計算し、今回のエネルギと前回のエネルギ
との大小関係を判定する（ステップＳ３）。
【００３８】ここで今回が第ｊ番目の位置座標更新であ
り更新後のエネルギの値をＥj (C)とし、前回が第ｊ−
１回目の位置座標更新であり更新後のエネルギの値をＥ
j-1(C) とすると、次のように処理を行う。 （１）Ｅj (C) ＜Ｅj-1 (C) の場合、即ち今回のエネル
ギＥj (C) が前回のエネルギＥj-1 (C) よりも小さい場
合は、エネルギが減少しているので、ステップＳ２に戻
り、微分によるエネルギ極小化を繰り返す。 （２）Ｅj (C) ＞Ｅj-1 (C) の場合、即ち今回のエネル
ギＥj (C) が前回のエネルギＥj-1 (C) よりも増大した
場合は、エネルギの減少が止って収束値に近づいたの
で、第１の処理からステップＳ５の第２の処理に移る。
但し、第２の処理を開始する前に、各制御点の位置座標
を更新前の状態、即ち第ｊ−１回目の位置座標更新の状
態に戻す（ステップＳ４）。 （３）Ｅj (C) ＝Ｅj-1 (C) の場合、即ち今回のエネル
ギＥj (C) が前回のエネルギＥj-1 (C) に一致した場合
も、エネルギの減少が止って収束値に近づいたので、第
１の処理から第２の処理に切り替える。この場合、各制
御点の位置座標を更新前の状態に戻してから第２の処理
を開始しても良いが、エネルギが変っていないので、本
実施例では処理の簡単化のために更新後の状態、即ち第
ｊ回目の位置座標更新の状態のままステップＳ５の第２
の処理に移る。
り更新後のエネルギの値をＥj (C)とし、前回が第ｊ−
１回目の位置座標更新であり更新後のエネルギの値をＥ
j-1(C) とすると、次のように処理を行う。 （１）Ｅj (C) ＜Ｅj-1 (C) の場合、即ち今回のエネル
ギＥj (C) が前回のエネルギＥj-1 (C) よりも小さい場
合は、エネルギが減少しているので、ステップＳ２に戻
り、微分によるエネルギ極小化を繰り返す。 （２）Ｅj (C) ＞Ｅj-1 (C) の場合、即ち今回のエネル
ギＥj (C) が前回のエネルギＥj-1 (C) よりも増大した
場合は、エネルギの減少が止って収束値に近づいたの
で、第１の処理からステップＳ５の第２の処理に移る。
但し、第２の処理を開始する前に、各制御点の位置座標
を更新前の状態、即ち第ｊ−１回目の位置座標更新の状
態に戻す（ステップＳ４）。 （３）Ｅj (C) ＝Ｅj-1 (C) の場合、即ち今回のエネル
ギＥj (C) が前回のエネルギＥj-1 (C) に一致した場合
も、エネルギの減少が止って収束値に近づいたので、第
１の処理から第２の処理に切り替える。この場合、各制
御点の位置座標を更新前の状態に戻してから第２の処理
を開始しても良いが、エネルギが変っていないので、本
実施例では処理の簡単化のために更新後の状態、即ち第
ｊ回目の位置座標更新の状態のままステップＳ５の第２
の処理に移る。
【００３９】ステップＳ５では第２の処理として、ＤＰ
法によるエネルギ極小化を行う。このＤＰ法によるエネ
ルギ極小化では、前述の通り、式（５）で与えられる制
御点毎のエネルギＥi を用いて、ｉ番目の制御点であれ
ば前後のうち未確定の制御点の８近傍移動と当該ｉ番目
の制御点の８近傍移動とからエネルギＥi が最小となる
ｉ番目の制御点の位置座標を決定するという処理を全制
御点について行い、全制御点の位置座標を更新する。
法によるエネルギ極小化を行う。このＤＰ法によるエネ
ルギ極小化では、前述の通り、式（５）で与えられる制
御点毎のエネルギＥi を用いて、ｉ番目の制御点であれ
ば前後のうち未確定の制御点の８近傍移動と当該ｉ番目
の制御点の８近傍移動とからエネルギＥi が最小となる
ｉ番目の制御点の位置座標を決定するという処理を全制
御点について行い、全制御点の位置座標を更新する。
【００４０】このような全制御点の位置座標更新を、式
（１）で与えられるエネルギＥ(C)が極小値に達するま
で繰り返す。
（１）で与えられるエネルギＥ(C)が極小値に達するま
で繰り返す。
【００４１】本実施例では、位置座標更新の都度エネル
ギＥ(C) を計算し、今回のエネルギと前回のエネルギと
を比較し、一致した時に極小値に達したものと判定して
いる（ステップＳ６）。
ギＥ(C) を計算し、今回のエネルギと前回のエネルギと
を比較し、一致した時に極小値に達したものと判定して
いる（ステップＳ６）。
【００４２】即ち、第１の処理における位置座標更新を
含め、今回が第ｋ番目の位置座標更新でありその更新後
のエネルギの値をＥk (C) とし、前回が第ｋ−１番目の
位置座標更新でありその更新後のエネルギの値をＥk-1
(C) とすると、Ｅk (C) ＝Ｅ k-1 (C) となったら第２の
処理を終了し、この時点での全制御点がなす形状を輪郭
の抽出結果とする。
含め、今回が第ｋ番目の位置座標更新でありその更新後
のエネルギの値をＥk (C) とし、前回が第ｋ−１番目の
位置座標更新でありその更新後のエネルギの値をＥk-1
(C) とすると、Ｅk (C) ＝Ｅ k-1 (C) となったら第２の
処理を終了し、この時点での全制御点がなす形状を輪郭
の抽出結果とする。
【００４３】図２に本実施例の実験結果を示す。図２に
おいて、５が対象物体としての楕円、Ｃini が初期輪
郭、Ｃfin が輪郭の抽出結果である。図２と図１１を比
較すると、第１の処理（微分によるエネルギ極小化手
法）のみを用いた場合に比べ、本実施例による抽出結果
は極めて良好であることが判る。
おいて、５が対象物体としての楕円、Ｃini が初期輪
郭、Ｃfin が輪郭の抽出結果である。図２と図１１を比
較すると、第１の処理（微分によるエネルギ極小化手
法）のみを用いた場合に比べ、本実施例による抽出結果
は極めて良好であることが判る。
【００４４】また、表１に本実施例の実験で要した計算
時間（計算コスト）を、第２の処理（ＤＰ法によるエネ
ルギ極小化手法）のみを用いた図１２の場合の計算時間
とともに示す。表１から判るように、本実施例の方が極
めて計算時間が短い。なお、制御点数はいずれも同じで
ある。
時間（計算コスト）を、第２の処理（ＤＰ法によるエネ
ルギ極小化手法）のみを用いた図１２の場合の計算時間
とともに示す。表１から判るように、本実施例の方が極
めて計算時間が短い。なお、制御点数はいずれも同じで
ある。
【００４５】
【表１】
【００４６】＜第２実施例＞図３を参照して本発明の第
２実施例に係る輪郭抽出方法を説明する。図３におい
て、本実施例でも“ＳＮＡＫＥＳ”により対象物体の周
囲に初期輪郭を設定し（ステップＳ１１）、まずは第１
の処理として、微分によるエネルギ極小化を行う（ステ
ップＳ１２）。
２実施例に係る輪郭抽出方法を説明する。図３におい
て、本実施例でも“ＳＮＡＫＥＳ”により対象物体の周
囲に初期輪郭を設定し（ステップＳ１１）、まずは第１
の処理として、微分によるエネルギ極小化を行う（ステ
ップＳ１２）。
【００４７】この微分によるエネルギ極小化では、第１
実施例と同様、式（１）で与えられる内部エネルギＥ
int (C) と外部エネルギＥext (C) からなるエネルギＥ
(C) を用い、全制御点について、式（４）の如く個々の
制御点でのエネルギＥ(C) の微分値を計算し得られた微
分値に基づいて同制御点の位置座標を更新する。基本的
には、このような全制御点の位置座標更新を繰り返して
行う。
実施例と同様、式（１）で与えられる内部エネルギＥ
int (C) と外部エネルギＥext (C) からなるエネルギＥ
(C) を用い、全制御点について、式（４）の如く個々の
制御点でのエネルギＥ(C) の微分値を計算し得られた微
分値に基づいて同制御点の位置座標を更新する。基本的
には、このような全制御点の位置座標更新を繰り返して
行う。
【００４８】但し、全制御点の位置座標更新の都度エネ
ルギＥ(C) から、エネルギの傾きＧ i を計算し、しきい
値Ｇthとの大小関係を判定する（ステップＳ１３，Ｓ１
４）。
ルギＥ(C) から、エネルギの傾きＧ i を計算し、しきい
値Ｇthとの大小関係を判定する（ステップＳ１３，Ｓ１
４）。
【００４９】ここで今回が第ｊ番目の位置座標更新であ
り更新後のエネルギの値をＥj (C)とし、前回が第ｊ−
１回目の位置座標更新であり更新後のエネルギの値をＥ
j-1(C) とし、今回の傾きをＧj とすると、次式（６）
の計算を行う。
り更新後のエネルギの値をＥj (C)とし、前回が第ｊ−
１回目の位置座標更新であり更新後のエネルギの値をＥ
j-1(C) とし、今回の傾きをＧj とすると、次式（６）
の計算を行う。
【数６】 Ｇj ＝Ｅj (C) −Ｅj-1 (C) …式（６）
【００５０】しきい値Ｇthにはゼロ近傍の負の値を設定
してあり、次のように処理を行う。 （１）Ｇj ≦Ｇthの場合、即ちエネルギの傾きＧi がし
きい値以下である場合は、エネルギが或る程度以上大き
く減少しているので、ステップＳ１２に戻り、ＤＰ法に
よるエネルギ極小化を繰り返す。 （２）Ｇj ＞Ｇthの場合、即ちエネルギの傾きＧj がし
きい値Ｇthを越えた場合は、エネルギが殆ど減少しなく
なって収束値に近づいたので、第１の処理からステップ
Ｓ１５の第２の処理に移る。
してあり、次のように処理を行う。 （１）Ｇj ≦Ｇthの場合、即ちエネルギの傾きＧi がし
きい値以下である場合は、エネルギが或る程度以上大き
く減少しているので、ステップＳ１２に戻り、ＤＰ法に
よるエネルギ極小化を繰り返す。 （２）Ｇj ＞Ｇthの場合、即ちエネルギの傾きＧj がし
きい値Ｇthを越えた場合は、エネルギが殆ど減少しなく
なって収束値に近づいたので、第１の処理からステップ
Ｓ１５の第２の処理に移る。
【００５１】ステップＳ１５では第２の処理として、Ｄ
Ｐ法によるエネルギ極小化を行う。このＤＰ法によるエ
ネルギ極小化では、第１実施例と同様、式（５）で与え
られる制御点毎のエネルギＥi を用いて、ｉ番目の制御
点であれば前後のうち未確定の制御点の８近傍移動と当
該ｉ番目の制御点の８近傍移動とからエネルギＥi が最
小となるｉ番目の制御点の位置座標を決定するという処
理を全制御点について行い、全制御点の位置座標を更新
する。このような全制御点の位置座標更新を、式（１）
で与えられるエネルギＥ(C) が極小値に達するまで繰り
返す。
Ｐ法によるエネルギ極小化を行う。このＤＰ法によるエ
ネルギ極小化では、第１実施例と同様、式（５）で与え
られる制御点毎のエネルギＥi を用いて、ｉ番目の制御
点であれば前後のうち未確定の制御点の８近傍移動と当
該ｉ番目の制御点の８近傍移動とからエネルギＥi が最
小となるｉ番目の制御点の位置座標を決定するという処
理を全制御点について行い、全制御点の位置座標を更新
する。このような全制御点の位置座標更新を、式（１）
で与えられるエネルギＥ(C) が極小値に達するまで繰り
返す。
【００５２】本実施例でも、第１実施例と同じく位置座
標更新の都度エネルギＥ(C) を計算し、今回のエネルギ
と前回のエネルギとを比較し、一致した時に極小値に達
したものと判定している（ステップＳ１６）。即ち、第
１の処理における位置座標更新を含め、今回が第ｋ番目
の位置座標更新でありその更新後のエネルギの値をＥ k
(C) とし、前回が第ｋ−１番目の位置座標更新でありそ
の更新後のエネルギの値をＥk-1 (C) とすると、Ｅ
k (C) ＝Ｅk-1 (C) となったら第２の処理を終了し、こ
の時点での全制御点がなす形状を輪郭の抽出結果とす
る。
標更新の都度エネルギＥ(C) を計算し、今回のエネルギ
と前回のエネルギとを比較し、一致した時に極小値に達
したものと判定している（ステップＳ１６）。即ち、第
１の処理における位置座標更新を含め、今回が第ｋ番目
の位置座標更新でありその更新後のエネルギの値をＥ k
(C) とし、前回が第ｋ−１番目の位置座標更新でありそ
の更新後のエネルギの値をＥk-1 (C) とすると、Ｅ
k (C) ＝Ｅk-1 (C) となったら第２の処理を終了し、こ
の時点での全制御点がなす形状を輪郭の抽出結果とす
る。
【００５３】
【発明の効果】以上実施例とともに説明したように、本
発明によれば“ＳＮＡＫＥＳ”により画像から物体の輪
郭を抽出する際に、最初は計算コストが小さい第１の処
理を行い、エネルギが収束値に近づいたら正確な輪郭を
抽出できる第２の処理に切り替えるので、全体として従
来よりも短時間で正確に輪郭を抽出することができる。
発明によれば“ＳＮＡＫＥＳ”により画像から物体の輪
郭を抽出する際に、最初は計算コストが小さい第１の処
理を行い、エネルギが収束値に近づいたら正確な輪郭を
抽出できる第２の処理に切り替えるので、全体として従
来よりも短時間で正確に輪郭を抽出することができる。
【図１】本発明の第１実施例に係る輪郭抽出方法の手順
を示す図。
を示す図。
【図２】第１実施例の実験結果を示す図。
【図３】本発明の第２実施例に係る輪郭抽出方法の手順
を示す図。
を示す図。
【図４】ＳＮＡＫＥＳの定義を示す図。
【図５】対象物体と初期輪郭と抽出結果との関係を示す
図。
図。
【図６】ＤＰ法におけるｉ−１番目の制御点のエネルギ
の計算に用いるテーブルの例を示す図。
の計算に用いるテーブルの例を示す図。
【図７】図６のテーブルを作成するためのｉ−１番目の
制御点の８近傍移動とｉ番目の制御点の８近傍移動を示
す図。
制御点の８近傍移動とｉ番目の制御点の８近傍移動を示
す図。
【図８】ＤＰ法におけるｉ番目の制御点のエネルギの計
算に用いるテーブルの例を示す図。
算に用いるテーブルの例を示す図。
【図９】図８のテーブルを作成するためのｉ番目の制御
点の８近傍移動とｉ＋１番目の制御点の８近傍移動を示
す図。
点の８近傍移動とｉ＋１番目の制御点の８近傍移動を示
す図。
【図１０】実験における対象物体の例を示す図。
【図１１】従来の第１の処理のみによる輪郭抽出方法の
実験結果を示す図。
実験結果を示す図。
【図１２】従来の第２の処理のみによる輪郭抽出方法の
実験結果を示す図。
実験結果を示す図。
Ｃini 初期輪郭 Ｃfin 抽出結果 １ 多角形 ２ 物体 ３，４ テーブル ５ 楕円（対象物体）
Claims (5)
- 【請求項１】 複数の制御点からなる動的輪郭モデルを
用い、制御点の位置座標の関数として与えられるエネル
ギが極小となるように制御点の位置座標を更新すること
により画像から物体の輪郭を抽出する輪郭抽出方法にお
いて、 （１）各制御点でエネルギの微分値を計算し、微分値に
基づいて各制御点の位置座標を更新する第１の処理を、
エネルギが収束値に近づくまで行うこと、 （２）第１の処理でエネルギが収束値に近づいた後は、
動的計画法によりエネルギが極小となる制御点の位置座
標を決定する第２の処理を行うこと、を特徴とする輪郭
抽出方法。 - 【請求項２】 第１の処理を繰り返して行い、今回のエ
ネルギが前回のエネルギよりも増大した時にエネルギが
収束値に近づいたと判定し、前記第２の処理は制御点の
位置座標をエネルギ増加直前の状態に戻してから開始す
ることを特徴とする請求項１記載の輪郭抽出方法。 - 【請求項３】 第１の処理を繰り返して行い、今回のエ
ネルギが前回のエネルギに一致した時にエネルギが収束
値に近づいたと判定し、直ちに前記第２の処理を開始す
ることを特徴とする請求項１記載の輪郭抽出方法。 - 【請求項４】 第１の処理を繰り返して行い、エネルギ
の傾きが予め定めたしきい値を越えた時にエネルギが収
束値に近づいたと判定することを特徴とする請求項１記
載の輪郭抽出方法。 - 【請求項５】 前記しきい値はゼロ近傍の負の値である
ことを特徴とする請求項４記載の輪郭抽出方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7154363A JPH096969A (ja) | 1995-06-21 | 1995-06-21 | 輪郭抽出方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7154363A JPH096969A (ja) | 1995-06-21 | 1995-06-21 | 輪郭抽出方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH096969A true JPH096969A (ja) | 1997-01-10 |
Family
ID=15582528
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7154363A Withdrawn JPH096969A (ja) | 1995-06-21 | 1995-06-21 | 輪郭抽出方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH096969A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1061748A2 (en) * | 1999-06-10 | 2000-12-20 | University of Washington | Video object segmentation using active contour modelling with global relaxation |
| CN102854765A (zh) * | 2011-06-27 | 2013-01-02 | 富士施乐株式会社 | 图像形成设备 |
-
1995
- 1995-06-21 JP JP7154363A patent/JPH096969A/ja not_active Withdrawn
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1061748A2 (en) * | 1999-06-10 | 2000-12-20 | University of Washington | Video object segmentation using active contour modelling with global relaxation |
| CN102854765A (zh) * | 2011-06-27 | 2013-01-02 | 富士施乐株式会社 | 图像形成设备 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111815687B (zh) | 点云匹配方法、定位方法、设备及存储介质 | |
| US10943352B2 (en) | Object shape regression using wasserstein distance | |
| Li et al. | Hopfield neural networks for affine invariant matching | |
| CN106444757B (zh) | 基于直线特征地图的ekf-slam方法 | |
| CN113608663A (zh) | 一种基于深度学习和k-曲率法的指尖跟踪方法 | |
| CN113658195B (zh) | 图像分割方法、装置及电子设备 | |
| Shah-Hosseini et al. | A TASOM-based algorithm for active contour modeling | |
| Tseng et al. | Active contour model via multi-population particle swarm optimization | |
| CN111914598B (zh) | 连续帧人脸关键点检测方法、装置、设备及存储介质 | |
| CN111681300A (zh) | 轮廓素描线组成的目标区域获取方法 | |
| CN113343987B (zh) | 文本检测处理方法、装置、电子设备及存储介质 | |
| CN115063443A (zh) | 一种实时多目标跟踪方法及系统 | |
| JP4567660B2 (ja) | 電子画像内で物体のセグメントを求める方法 | |
| JPH096969A (ja) | 輪郭抽出方法 | |
| Taralathasri et al. | Real time object detection using Yolo algorithm | |
| Kung et al. | Efficient surface detection for augmented reality on 3d point clouds | |
| CN118537404A (zh) | 基于动态目标追踪的实时视觉同步定位与建图方法 | |
| CN115958603A (zh) | 机器人在观测受限下拾取及放置物体的任务规划方法及系统 | |
| KR20090087254A (ko) | 2차원 경로를 삼각형으로 변환하기 위한 장치 및 방법 | |
| Kozek et al. | An active contour algorithm for continuous-time cellular neural networks | |
| Mosa et al. | Driving active contours to concave regions | |
| Venkatesan et al. | Advanced classification using genetic algorithm and image segmentation for Improved FD | |
| Huo et al. | Semantic region estimation of assistant robot for the elderly long-term operation in indoor environment | |
| JP2976954B2 (ja) | 文字切り出し候補生成装置 | |
| JPH10240866A (ja) | 文字認識装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 20020903 |