JPH01295376A - 線図形の直線近似処理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔技術分野〕 本発明は、画像処理の一つである輪郭線抽出などにより
得られる線図形を曲率と変位で評価し、折れ線で近似す
るようにした線図形の直線近似処理方式に関する。

〔従来技術〕

従来、画像の輪郭線抽出などで得られる線図形の形状近
似法として、情報処理学会研究資料、グラフィックスと
ＣＡＤ、２６−５　（１９８７）に掲載の（青白、河越
：“原図形の視覚的特徴を保持する線分近似法”）が知
られている。

上記の直線近似法においては、大まかな部分は粗くまた
細かな部分は細かく近似する方法として、近似の評価の
基準に曲率の近似Ｒ（＝ｄ／ｆ）と変位Ｄ　（＝ｄ）を
基本とすることが開示されている。

しかし、上記の曲率の近似Ｒを固定のしきい値で判断す
ると、角の目立ち具合を大きさに単純に比例させたくな
いような場合、例えば第２図（ａ）中のＰｌと同図（ｂ
）中のＰ２で角の目立ち具合に差をつけたい場合には対
処できないものである。

以下に、上記した従来における図形の複雑さに応じた直
線近似、すなわち大まかな部分は粗く、細かな部分は細
かく直線近似する方法について説明する。

この場合の直線近似に対するアルゴリズムは３ステツプ
からなるが、以下に各ステップを順を追って説明する。

（１）　　ステップ１ 第３図に示す格子上の点からなる点列（Ｐ、）を順に結
んだ時の折れ点および始点、終点を求める（図中の○印
）。

なお、求まった点列（Ｑ、）を順に結んでできる線分の
方向は、図中に示す８方向のいずれかである。

（２）　　ステップ２ 上記したステップｌで得られる格子上の点列から、直線
をディジタイズした場合に現われるパターンを見つけて
直線のあてほめを行ない、点列杏圧縮する。

第４図は直線とみなせる点列パターンの例を示しており
、咳点列は次の条件を満たしている時に直線上のものと
みなされる。

Ｉｓｏ　１＜２　　　ＯＲＩｓＩ　　１＜まただし、（
ＳＯ＋Ｓｚ）または（Ｉｓ、）ｌ≧２△　ＩＳ、１≧２
）の場合は、Ｐ、、Ｐ、０２点のみ直線上のものとみな
される。

（３）ステップ３ 上記したステップ２の結果から、最終的な近似直線を求
める。この時の評価の基準としては、第５図に示す誤差
算定要素、すなわち曲率の近似Ｒ（＝ｄ／ｆ）と変位Ｄ
（＝ｄ）を基本として用いる。

なお、Ｐ、を始点とする最大近僚直線ＰｔＰｔ＝を求め
るには、その間の全点Ｐｊに対して（Ｒｊ≦Ｔ、＋）△
（Ω、≦’ｂ）（Ｔ＋、ｂ：Ｌきい値）が成り立ち、か
つ線分ＰｉＰｋ＊１に対しては成り立たないＰｋを求め
ればよい。

上記した直線近似の評価の基準に、曲率の近似Ｒと変位
りを基本として用いる方法は、原データに対する分割型
の直線近似にも応用することができる。

以下に、例として第６図を参照して反復端点あてはめ法
（区分的直線近似法）で説明する。なお、図中の○印は
点列中の各点を示している。

（１）ステップ１ まず、同図（ａ）に示すように、点列（点セグメント）
の両端の点を仮想的に直線線分で結び、該直線線分から
最も離れた点（分割点）を見つけ、その最大距離ｄ（図
示のｄｏ）が誤差値Ｔｈｄより大きければ、または上記
の仮想的な直線線分長！（図示の２０）と最大距離ｄの
比ｄ／２（図示の場合はｄ、　／１２゜）が誤差値Ｔｈ
ｄより大きければ、上記の分割点で同図（ｂ）に示すよ
うに２つの直線線分に分割する。

なお、上記したいずれでもない場合は、この処理におけ
るアルゴリズムを終了する。　　　　　′（２）ステッ
プ２ 次に、分割した各々の直線線分に対して、上記したステ
ップ１と同様の手順を用いて分割を繰り返し行なってい
き、同図（Ｃ）　、　（ｄ）に示す直線線分に分割する
。

（３）ステップ３ 上記したアルゴリズムにより分割されたいずれの直線線
分に対しても、上記した最大距離ｄがしきい値Ｔｈ、よ
りも小さくなった時点で分割操作を停止し、各々の分割
点で結ばれた直線を求める線図形としてアルゴリズムを
終了する。

なお、上記したアルゴリズムにおいて、閉ループの場合
にはｌ＝０となるため、例えば最低１回は分割するなど
の工夫が必要となる。

しかしながら、上記した直線近似方法における特徴点の
条件域は、第７図（ａ）に示す斜線部であり、この境界
を近似結果の視覚的な好みなどの都合により任意の形状
としたい場合、例えば境界点の条件域を同図（ｂ）に示
す斜線部のようにしたい場合は対処できないといった問
題があった。

〔目　的〕

本発明は、上記した従来における問題を解消するために
なされたもので、画像処理における輪郭線抽出などで得
られる線図形を、曲率と変位で評価して直線近似を行な
う場合に、自由度の大きいパラメータの設定ができるよ
うにした線図形の直線近似処理方式を提供することを目
的とする。

〔構　成〕

本発明は上記の目的を達成させるために、線図形を直線
近似するに際して、特徴点か否かの判断を近似直線に対
する原データの変位ｄとパラメータＴｈｄとの比較と、
特徴点間の距離２とパラメータＴｈｆとの比較に基づい
て行なうようにしたことを特徴とするものである。

以下、本発明の実施例に基づいて具体的に説明する。

本発明における視覚的に好ましい直線近似のための評価
パラメータは、前述の第６図中に示した直線線分長ｌに
対応して変位ｄの誤差値Ｔｈｄを変化させることにより
設定される。

このことを、式で記述すると、 ｉｆ　　１＝ｔｘ　　ｔｈｅｎ　　Ｔｈｄ＝β　　（１
）のように表わされる。そして、上記した変位ｄと誤差
値Ｔｈｄとを比較することにより、特徴点か否かが決定
される。

以下に、この場合の具体的な実施方法について説明する
。

例えば、画素数が５１２Ｘ５１２からなる入力画を対象
とし、該入力画に対する４方向の追跡処理に基づいて輪
郭線を抽出した場合は、直線線分長ｌのとりうる整数の
種類はたかだか１０２４種類である。これに基づいて、
上記の直線線分長２の入力に対し、誤差値Ｔｈｄを出力
するルックアップテーブル（ＬＵＴ）を作成する。

また、直線線分長ｌに対する誤差値Ｔｈｆｆ１と、変位
ｄに対する誤差値Ｔｈｄとの関係が簡単な関数であれば
、下式に基づく計算により上記の誤差値Ｔｈｄを算出す
る。

例えば、上記した誤差値ＴｈｆとＴｈｄに比例関係をも
たせたければ、 Ｔｈｄ＝ｋＸ／！　（ｋはある定数）（２）とする。

而して、第１図は本発明における直線近似処理方式のフ
ローチャートであり、以下に各ステップについて説明す
る。

まず、ステップＳ、において、対象とする入力画に対す
る輪郭線追跡処理に基づく、輪郭線追跡後の（Ｘ　、　
Ｙ）座標列で記述された点列データをもとにして、咳点
列データが閉ループであるか否かの判断が行なわれる。

そして、このステップＳ１で閉ループでないと判断され
た場合はステップＳ、に移行し、閉ループであると判断
された場合はステップＳ２に移行する。

そして、閉ループである場合はステップＳ２において、
上記した点列データは始点（終点）から最も離れた点で
分割される。なお、このステップＳ２における分割処理
は、閉ループである場合の直線線分長！が０となること
に基づく、最低１回の分割を行なうための処理である。

次に、ステップＳ３において、各セグメントに対して前
述したルックアップテーブル（ＬＵＴ）から誤差値Ｔｈ
ｄを求めるとともに、引き続きステップＳ４において、
各セグメントに対する最大距離ｄを求める。

続いて、ステップＳ、において、各セグメントに対して
の上記のステップＳ、およびＳ４で求めた最大距離ｄと
誤差値Ｔｈｄとの大小関係が判断される。このステップ
Ｓｓにおいて、最大距離ｄが誤差値Ｔｈｄよりも大きい
と判断された場合は、ステップＳ、において注目のセグ
メントを分割した後に、上記したステップＳ、に戻る。

また、ステップＳ、において、最大距離ｄが誤差値Ｔｈ
ｄより小さいと判断された場合は、注目のセグメントを
分割することなくステップＳ、に移行する。

そして、ステップＳ７において点列データに対する終了
判定を行ない、まだ途中であればステップＳ１に戻って
上記した各ステップにおける処理を再開する。また、す
べての点列データに対する処理が終了したと判断された
時点でステップＳ８に移行し、このステップＳ、におい
て分割点を結ぶことにより、一連の直線近似処理を終了
する。

〔効　果〕

以上説明した本発明によれば、直線線分長２に対応して
変位ｄの誤差値Ｔｈｄを変化させ、該変位と誤差値Ｔｈ
ｄとの比較に基づいて特徴点か否かを判断するようにし
たので、線図形を曲率と変位で評価して直線近似を行な
う場合において、パラメータの設定が自由にできるとと
もに、視覚的に好ましい直線近似結果を得ることができ
る。

【図面の簡単な説明】

第１図は本発明による直線近似処理方式における処理手
順を示すフローチャート、 第２図は従来の直線近似法における不都合を説明するた
めの図、 第３図は従来の直線近似法における格子上点列の折れ点
を示す図、 第４図は従来の直線近似法における直線とみなせる点列
パターンの例を示す図、 第５図は従来の直線近似法における誤差算定要素を示す
図、 第６図は従来における反復端点あてはめ法による折れ線
近似を説明するための図、 第７図は従来の直線近似法における特徴点の条件域を示
す図である。 第１図 （Ｇ）　　　　　　　　　　　　（ｂ）Ｐｌ　０α〜Ｑ
Ｊ 第３図 （ａ）　　　　　　　　　　　　　　　（Ｃ）（ｂ）　
　　　　　　　　　　　　　（ｄ）第６図 （Ｇ）　　　　　　　　　　　　　　　　（ｂ）第７図

Claims (4)

【特許請求の範囲】
1. （１）線図形を曲率と変位で評価して直線近似するよう
   にした直線近似処理において、 特徴点か否かの判断を、近似直線に対する原データの変
   位（ｄ）と該変位に対する誤差値であるパラメータ（Ｔ
   ｈｄ）との比較と、特徴点間の距離（１）と該距離に対
   する誤差値であるパラメータ（Ｔｈｌ）との比較に基づ
   いて行なうようにしたことを特徴とする線図形の直線近
   似処理方式。
2. （２）上記のパラメータ（Ｔｈｄ）とパラメータ（Ｔｈ
   ｌ）との間に特定の関係をもたせることを特徴とする請
   求項（１）記載の線図形の直線近似処理方式。
3. （３）上記のパラメータ（Ｔｈｄ）が大なる時にパラメ
   ータ（Ｔｈｌ）が大なる関係を有することを特徴とする
   請求項（２）記載の線図形の直線近似処理方式。
4. （４）上記のパラメータ（Ｔｈｄ）とパラメータ（Ｔｈ
   ｌ）が比例関係を有することを特徴とする請求項（３）
   記載の線図形の直線近似処理方式。