JPH01282684A - 線図形の近似誤差補正方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 、。　　〔技術分野〕 １　　　本発明は、点列として表された線図形を折れ線
と円弧で近似する線図形の近似方法に係り、特に円弧と
円弧、直線と円弧を滑らかにつなぐようにした線図形の
近似誤差補正方法に関する。

〔従来技術〕

従来より、画像の輪郭線抽出などで得られた線図形を、
折れ線近似の結果を用いて直線と円弧で近似することが
行われている。

第７図は、従来における折れ線近似の結果を用いて、線
図形を直線と円弧で近似する場合の処理手順をブロック
図で示したものである。以下に、第７図に示した（１）
〜（６）までの各ブロックの機能および具体的な手法を
順を追って説明する。

（１）点列データ 点列データは、（Ｘ　、　Ｙ）座標列で記述される。

（２）折れ線近似 ディジタルノイズの除去ならびに後処理を効率よく行な
うために、その前処理として折れ線近似を行なう。

この場合の近似に対する評価方法としては、■変位９而
楢等の位置ずれを評価する方法、０曲率、偏角、変位／
線長、複雑度等の形状ずれを評価する方法、■上記の■
と■の両方を評価する方法に大別される。ここでの折れ
線近似に対しては、上記■の位置ずれを評価する方法に
属する反復端点あてはめ法が用いられる。

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

まず、同図（ａ）に示すように、点列（点セグメント）
の両端の点を仮想的に直線Ｌ１で結び、この直線Ｌ１か
ら最も離れた点（図中の・印）を見つけ、該直線Ｌ１か
らの最大距離が誤差値ε０より大きければ、この点を分
割点として、同図（ｂ）に示すように点列の各端とを２
本の直線Ｌ２　、Ｌ３で結ぶ。゛ そして、直線から最も離れた点までの距離が誤差値ε。

よりも大きければ、その点を再び分割点として、同図（
Ｃ）に示すように直線Ｌ２を直線Ｌ４、Ｌ５でさらに分
割する。さらに、上記の最大距離が誤差値ε。よりも大
きい場合は、同図（ｄ）に示すように直線Ｌ４を直ｉＬ
６．Ｌ７でさらに分割し、最大距離が誤差値ε。より小
さくなった時点で、折れ線近似を終了する。

この結果、上記した点列の場合は、第８図（ｄ）に示す
ように４本の折れ線（Ｌ６．Ｌ？、Ｌ５．Ｌ３）により
近似されることになる。そして、上記の折れ線近似を行
なった後、連続した折れ線群について、円弧近似が可能
であるか否かの判定処理が行なわれる。

（３）円弧仮定 上記した折れ線近似の結果を用いて、円弧部の仮定を行
なう。すなわち、ここでは折れ線が等しい長さでかつ等
しい角度で記述された部分を円弧部と仮定する。

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

第９図は、円弧仮定を説明するための図であり、図示の
特徴点Ｐ　（１）　、　Ｐ　（２）を結ぶ折れ線Ｌ１お
よび特徴点Ｐ　（２）　、　Ｐ　（３）を結ぶ折れ線Ｌ
２に対するそれぞれの垂直二等分線Ｍｌ、Ｖ２の交点Ｃ
（１）と、特徴点Ｐ　（２）　、　Ｐ　（３）を結ぶ折
れ線Ｌ２および特徴点Ｐ（３）　、　Ｐ　（４）を結ぶ
折れ線Ｌ３に対するそれぞれの垂直二等分線Ｖ２　、Ｖ
３の交点Ｃ（２）を求める。

次に、ＸＹ座標において、上記のようにして求めた交点
Ｃ（１）　、　Ｃ（２）を対角頂点とした横がＸ方向、
縦がＹ方向に平行な矩形ボックス７を生成する。

そして、上記の矩形ボックス７の縦と横の辺の長さがし
きい値Ｌｍａｘ以下であるかどうかを調べ、該しきい値
Ｌ　＋ｓａｘ以下であれば、現時点で対象となっている
最も小さな番手の特徴点（図示の例ではＰ（１））の位
置を円弧部の始点の位置Ｃｓとする。

なお、これは交点のばらつきから、連続した３本以上の
折れ線について、隣合う折れ線の内角の連続性を判定す
るものである。

もしミ矩形ボックス７の一辺でも、長さが上記のしきい
値Ｌｒｍａｘを超えた場合は、判定すべき特徴点を一つ
進めて、上記したと同様の処理を行なう。第９図に示し
た例では、特徴点Ｐ（２）〜Ｐ（５）について上記した
処理を行なう。

順次、各特徴点間に垂直二等分線を引き、特徴点Ｐ　（
４）　、　Ｐ　（５）を結ぶ折れ゛線部４の垂直二等分
線Ｖ４と、この直前の折れ線Ｌ３の垂直二等分線Ｖ３と
の交点を求め、これらの交点群の中で、第１０図に示す
ようにＸ方向およびＹ方向のそれぞれに対して最も離れ
ている４個の交点を囲むように矩形ボックス７を拡大す
る。第１Ｏ図中のＯ印は交点群であり、この拡大された
矩形ボックス７Ａの中心の位置をＲｃとする。

そして、拡大された矩形ボックス７Ａについて、各辺の
長さがしきい値しｌｌ１ａｘ以下であるかどうかを調べ
、−辺でもしきい値Ｌ　ｗａｘを超えた場合は、現時点
で対象となっている最も大きな番手の一つ手前の特徴点
を、この円弧部の終点の位置Ｃｅとする。

ただし、上記の円弧部中に折れ線の数が少ない場合は直
線部とする。

（４）円弧検証 円弧仮定部に円弧をあてはめ、ある全以内におさまるか
どうかで検証を行なう。以下に、具体的な手法にらいて
説明する。

しきい値Ｌｍａｘを超える直前の矩形ボックスの中心Ｒ
ｃ（第１０図参照）と、円弧部と仮定された始点Ｃｓか
ら終点Ｃｅ間のすべての原データ点列との距離Ｄ　（ｉ
）を計算し、該距離Ｄ（ｉ）の最大距離Ｄｍａにと最小
距離Ｄ　ｖａ　ｉ　ｎを求める。

そして、上記の最大距離Ｄｒｍａｘと最小距離Ｄ　ｖａ
　ｉ　ｎを順次更新し、下式が成立するか否かを調べる
。

Ｄｍａｘ−ＤＩＩｉｎ＞ＴＨ。

もし、上式が成立すれば、現時点よりも円弧長を短くす
る方向で、かつ最寄りの特徴点を最終的な円弧部の終点
Ｃｅ”　（次の円弧仮定対象の始点）とする。

ただし、上記の円弧部中に折れ線の数が少ない場合は直
線部とする。

（５）補正゛ 各円弧データは、上述した始点の位置Ｃ８、終点の位置
Ｃｅ’　　（次コマンドの始点の位置）、中心の位ＷＲ
ｃで記述され、一般には計算誤差に対する補正が必要で
ある。

なお、本発明はこの円弧部の補正に係るものである。

（６）出力 折れ線と円弧のコマンド群で記述される。

しかし上記した方法においては、（４）で説明した円弧
検証の後の出力では円弧と円弧、円弧と直線のつなぎに
すき間が生じるといった問題があった。

そこで、上記の問題を解消するために、次に示す補正方
法も提案されている。

第１の補正方法は、第１１図に示すように、円弧の始点
Ｃｓと終点Ｃｅを結ぶ直線Ｌａを引き、次にこの直線Ｌ
ａの垂直二等分線Ｖａを引いて、該垂直二等分線Ｖａ上
で、かつＲｃに最も近い位置を補正後の円弧部中心の位
置Ｒｃ’　とする方法である。

また、第２の補正方法は、第１２図に示すように、円弧
の始点Ｃｓと終点Ｃｅを結ぶ直線Ｌａを引き、次にこの
直線Ｌａの垂直二等分線Ｖａを引いて、該垂直二等分線
Ｖａ上で、かつＣ５−Ｒｃ間と等しい位置を補正後の円
弧部中心の位ＭＲｃ’とする方法モある。

しかしながら、上記した補正方法によっても、視覚的に
曲率の連続性が積極的に望まれる場合には対処できない
といった問題があった。

〔目　的〕

本発明は、上記した従来における問題を解消するために
なされたもので、点列として表現された線図形を折れ線
と円弧で近似する方法において、注目円弧の一つ手前の
折れ線あるいは円弧とのつなぎ目に曲率の連続性を考慮
して該注目円弧の中心座標を補正し、円弧と円弧または
直線と円弧のつなぎを滑らかにした線図形の近似誤差補
正方法を提供することを目的とする。

〔構　成〕

本発明は上記の目的を達成させるために、線図形を折れ
線と円弧で近似するに際して、折れ線部は始点座標群で
、円弧部は始点座標群と中心座標群で記述し、注目の円
弧始点と一つ手前の折れ線あるいは円弧終点のつなぎの
曲率が連続であると判定された場合にのみ、上記の中心
座標を補正するようにしたことを特徴とするものである
。

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

第１図は、本発明を実施するためのハードウェアーの構
成例を示す図である。

図において、１は線図形の点列データ（Ｘ　、　Ｙ座標
データ）を格納した点列データメモリであり、上記の点
列データは具体的には２個画像の輪郭線抽出などで得ら
れた線図形の゛データである。２は、近似処理を実行す
る中央演算処理装置、３は近似処理のためのプログラム
を格納したプログラムメモリである。なお、上記におけ
るプログラムは、点列の折れ線近似の部分と、該折れ線
近似の結果および点列データを用いた円弧抽出の部分か
ら構成されている。４は処理の中間データ、処理結果デ
ータを格納するためのデータメモリである。

第２図は、本発明による近似処理の処理フローであり、
以下この処理フローに基づいて順を追って説明する。

まず、ステップＳＩにおいて、点列データメモＩＪ　ｌ
内の各点列（線セグメント）について、前述した反復端
点あてはめ法により折れ線近似を行なう。

そして、この折れ線近似は、近似折れ線と点列との最大
距離（歪みりが許容誤差値ε。以下になるまで行われ、
この処理による折れ線近似データはデータメモリ４に格
納される。

なお、上記の折れ線近似は、最小二乗法の特徴点の数を
順次増していく方法であってもよく、あるいは第３図に
示すように、特徴点（・印）の真中（小数点以下は切り
捨て）の点を次の特徴点（分割点）とする方法で行なっ
てもよい。

上記のようにして得られた折れ線近似データに基づいて
、以下に説明するステップＳ２以降の処理により、円弧
近似が行なわれる。

ステップＳ２において、連続した３本の折れ線の端点、
すなわち特徴点Ｐ（ｉ）、Ｐ　（ｉ　＋　１）　ｔ　Ｐ
（１＋２）　　ｔ　Ｐ　（ｉ＋　３）について、それぞ
れの折れ線の垂直二等分線の隣合うものどうしの交点Ｃ
（ｉ）、Ｃ（ｉ＋１）を計算する。ただし、上記したス
テップＳ、において、ｉ＝１に初期設定されている。

ここでは、前述した第９図に示すような特徴点Ｐ（１）
〜Ｐ（４）の場合、折れ線Ｌｌ、Ｌ２の垂直二等分線Ｖ
ｌ、Ｖ２（７）交点Ｃ（１）、折れ線Ｌ２　、Ｌ３（７
）垂直二等分線Ｖ２　、Ｖ３の交点Ｃ（２）を算出する
。

続いて、ステップＳ３において、上記した交点Ｃ（ｉ）
、Ｃ（ｉ＋１）を対角頂点とした矩形ボックス（第９図
中に示した符号７）を生成する。そして、ステップＳ４
において、矩形ボックスの横方向（Ｘ方向）および縦方
向（Ｙ方向）の各辺の長さが、あるしきい値Ｌ　ｍａｘ
以下であるかどうかを調べ、これにより交点のばらつき
から連続した３本以上の折れ線について、隣合う折れ線
の内角の連続性を判定する。

なお、上記のステップＳ４において、矩形ボックスの一
辺でもその長さがしきい値Ｌ　ｍａｘを超えた場合は、
ｉに＋１してステップＳ２に戻る。すなわち、判定すべ
き特徴点を一つ進めて上記と同様の処理を行なう。第９
図に示した例では、特徴点Ｐ（２）からＰ（５）につい
て上記の処理を行なう。そして、特徴点Ｐ（１）からＰ
（２）の範囲の点列は円弧としては抽出されず、折れ線
Ｌ１で近似される。

ステップＳ４において、矩形ボックスのＸ方向ならびに
Ｙ方向の両方の辺がしきい値Ｌ　ｍａｘ以下であると判
定された場合は、ステップＳ、において特徴点Ｐ　（ｉ
）を円弧候補の始点Ｃｓに設定する。

次に、ステップＳ６において、特徴点Ｐ　（ｉ＋３）と
Ｐ　（ｉ＋４）を結ぶ折れ線の垂直二等分線と、この直
前の折れ線に対する垂直二等イ）線との交点（第９図の
例では折れ線Ｌ３　、Ｌ４のそれぞれの垂直二等分線Ｖ
３　、Ｖ４との交点）を計算する。

ステ°ツブＳ、において、上記したステップＳ。

までの処理で計算して得た交点群の中で、Ｘ方向および
Ｙ方向に最も離れた４個の交点を囲むように矩形ボック
スを、第１０図の符号７Ａで示すように拡大する。

上記のようにして拡大した矩形ボックスについて、ステ
ップＳ８において各辺がしきい値Ｌｍａｘ以下であるか
どうかを調べる。そして、このステップＳ、において、
拡大した矩形ボックスの両辺ともその長さがしきい値Ｌ
　ｗａｘ以下であると判定された場合は、ｉを＋１し、
すなわち判定対象の特徴点を一つ進め、上記したステッ
プＳ、の処理に戻る。

上記のように、矩形ボックスを拡大することにより、判
定範囲を順次拡大しながら折れ線の方向性を調べていく
。

上記のステップＳｓにおいて、矩形ボックスの一辺でも
その長さがしきい値Ｌ　ｗａｘを超えたと判定された場
合は、ステップＳ、に移行し、現時点で対象としている
最後の特徴点Ｐ　（ｉ＋４）の一つ手前の特徴点Ｐ　（
ｉ＋３）を円弧候補の終点Ｃｅに設定する。すなわち、
Ｐ（ｉ）からＰ　（ｉ＋３）までの範囲の点列を円弧候
補として、とりあえず抽出する。

続いて、ステップＳ、。において、円弧候補に含まれる
折れ線の数（始点Ｃｓから終点Ｃｅ間における折れ線の
数）がしきい値以上であるかどうかが判定される。ここ
で、折れ線の数がしきい値以下であり、円弧として抽出
すべきセグメント長に達しないと判定された場合は、円
弧候補を取り消してステップＳ２に戻り、上記した終点
Ｃｅの特徴点より円弧抽出を再開する。

また、上記のステップＳＩ６において、円弧候補の折れ
線の数がしきい値以上であると判定された場合は、ステ
ップＳ１１に移行し、ここで矩形ボックスの中心Ｒｃ（
第１０図参照）を求め、この中心Ｒｃと始点Ｃｓから終
点Ｃｅまでのすべての原データ点列との距離Ｄ　（ｉ）
を計算し、最大路ＨＤｌＩＩａｘと最小距離Ｄｍｉｎを
求める。

そして、Ｄａ＋ａｘ−Ｄｍｉｎがしきい値以上である場
合に１よ、円弧近似を行なうには近似誤差が大きくて不
適切であるため、現時点よりも円弧長を短（する方向で
、かつ最寄りの特徴点を最終的な円弧部の終点Ｃｅ’　
　（次の円弧仮定対象の始点）とし、この最終的な終点
Ｃｅ’をステップＳＬ１において設定する。

次に、ステップ５ｒｆｆにおいて、上記した終点Ｃｅ″
から始点Ｃｓまでの間における折れ線の数がしきい値以
上であるかどうかが判定される。ここで、折れ線の数が
しきい値以下であると判定された場合は、ステップＳ２
に戻り終点Ｃｅの特徴点より円弧抽出を再開する。

また、上記のステップｓ＋３において、折れ線の数がし
きい値以上であると判定された場合は、ステップＳＩ４
に移行し、ここで中心位置を補正する。

第４図はステップＳ　１４であ中心位置を補正するため
の判定方法を説明するための図である。補正対象となる
注目円弧の一つ手前の折れ線あるいは円弧の終点Ｃｓを
通る垂直線Ｖａを引く。そして、この垂直線Ｖａと補正
前の円弧部中心の位置Ｒｃとの距離ｄ、が、しきい値Ｔ
Ｈ，以下である場合に補正する。

また、第５図は他の判定方法ならびに補正方法を説明す
るための図である。この方法では、補正対象となる注目
円弧の一つ手前の折れ線あるいは円弧の終点Ｃｓを通る
垂直線Ｖａと、ＣｓとＣｅ’を結ぶ直線Ｌａの垂直二等
分線ｖｂとの交点をＣとする。そして、この交点Ｃと補
正前の円弧部中心の位置Ｒｃとの距離ｄ２が、しきい値
Ｔ　Ｈ，以下である場合に補正する。

そして、この場合の補正は、補正対象となる注目円弧の
一つ手前の折れ線あるいは円弧の終点Ｃ８を通る垂直線
Ｖａと、ＣｓとＣｅ’を結ぶ直線Ｌａの垂直二等分線ｖ
ｂの交点Ｃを、円弧部中心の位置Ｒｃ’　として補正す
る。

なお、円弧部の前とのつながりで曲率の連続性を望まず
、後が折れ線である場合も上記したと同様の判定と補正
を行なう。また、第６図に示すような場合も上記した補
正処理が行なわれるが、円弧仮定時にＣｓでのベクトル
変化を記述することにより；このような誤った補正を避
けることができる。

上記したステップＳＩ４における中心位置補正の後、ス
テップ３１％に移行し、抽出した円弧の始点Ｃｓ、最終
的な終点Ｃｅ’および補正後の中心Ｒｃ゛を円弧データ
としてデータメモリ４に格納する。

そして、ステップＳ０において点列データの終了判定を
行ない、まだ途中であればステップＳｚに戻って終点Ｃ
ｅの特徴点より円弧抽出処理を再開し、すべての点列デ
ータに対する処理が終了した時点で、上記した一連の円
弧抽出処理を終了する。

〔効　果〕

以上説明した本発明によ糺ば、折れ線部は始点、座標群
で、円弧部は始点座標群と中心座標群で記述し、注目の
円弧始点と一つ手前の折れ線あるいは円弧終点のつなぎ
の曲率が連続であると判定された場合にのみ、上記の中
心座標を補正するようにして円弧部前後の曲率の連続性
を考慮したので、円弧と円弧または直線と円弧のつなぎ
を円滑化することができる。

【図面の簡単な説明】

第１図は本発明を説明するためのハードウェアの一構成
例を示すブロック図、 第２図は本発明の一実施例における近似処理のフローチ
ャート、 第３図は折れ線近似のための別の手法を説明するための
図、 第４図は中心位置補正のための判定方法を説明するため
の図、 第５図は中心位置補正のための判定方法ならびに補正方
法を説明するための図、 第６図は誤った補正例を説明するための図、第７図は従
来における折れ線近似処理の手順を示すブロック図、 第８図は反復端点あてはめ法による折れ線近似の説明図
、 第９図は円弧抽出のための説明図、 第１０図は矩形ボックスの拡大と中心位置を説明するた
めの図、 第１１図は従来の中心位置の補正方法を説明するための
図、 第１２図は他の中心位置の補正方法を説明するための図
である。 特許出願人　　　　　株式会社　リ　コ　一第３図 第４図 Ｃｓ 第５図 Ｃｓ 第６図 （ｂ）　　　　　　　　　　　　　　　　（ｄ）第８図 第９図 第１０図

Claims (5)

【特許請求の範囲】
1. （１）線図形の点列を折れ線と円弧により近似するよう
   にした方法において、 折れ線部は始点座標群Ｐ（ｉ）で、円弧部は始点座標群
   Ｐ（ｉ）と中心座標群Ｒｃ（ｉ）で記述し、注目の円弧
   始点Ｐ（ｊ）と一つ手前の折れ線あるいは円弧終点Ｐ（
   ｊ）のつなぎの曲率が連続であると判定された場合にの
   み、中心座標Ｒｃ（ｊ）を補正するようにしたことを特
   徴とする線図形の近似誤差補正方法。
2. （２）上記の判定を、一つ手前の折れ線あるいは円弧終
   点Ｐ（ｊ）を通る垂直線と、補正前の中心座標Ｒｃ（ｊ
   ）との距離に基づいて行なうことを特徴とする請求項（
   １）記載の線図形の近似誤差補正方法。
3. （３）上記の判定を、一つ手前の折れ線あるいは円弧終
   点Ｐ（ｊ）を通る垂直線と、注目の円弧始点Ｐ（ｊ）と
   終点Ｐ（ｊ＋１）を結ぶ直線の垂直二等分線との交点Ｃ
   を求め、該交点Ｃと補正前の中心座標Ｒｃ（ｊ）との距
   離に基づいて行なうことを特徴とする請求項（１）記載
   の線図形の近似誤差補正方法。
4. （４）つなぎの曲率が連続であると判定された場合の補
   正後の中心座標Ｒｃ’（ｊ）が、一つ手前の折れ線ある
   いは円弧終点Ｐ（ｊ）を通る垂直線上にあることを特徴
   とする請求項（１）記載の線図形の近似誤差補正方法。
5. （５）補正後の中心座標Ｒｃ’（ｊ）が、円弧終点Ｐ（
   ｊ）を通る垂直線と、注目の円弧始点Ｐ（ｊ）と終点Ｐ
   （ｊ＋１）を結ぶ直線の垂直二等分線との交点Ｃである
   ことを特徴とする請求項（４）記載の線図形の近似誤差
   補正方法。