JPS6079479A - 線図形符号化方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は、チェイン符号化された線図形データを基に高
能率直線近似符号化するようにした線図形符号化方法に
関するものである。

従来、線図形の代表的な符号化方法としては、チェイン
符号化方法と直線近似符号化方法とが知られている。

チェイン符号化方法は、与えられた線図形を線幅が１画
素となるように細線化処理を行なった後に、′線図形を
構成する画素が、治目している画素に対し、第１図に０
　、１　、２−−−７で示す８方向のいずれの方向に連
結しているかを、３ビット／画素の符号爪を用いて符号
化する方法である。

また、直線近似符号化方法は第２図に示すように、線図
形ｌ上に幅ｄをもった直線状のチューブ２を当てはめて
ゆき、チューブ内に含まれる画素列はそれぞれ１つのＩ
Ｕ線で近似可能とみなし、各チューブ内の画素列の両端
点の画素位置を始点。

終点とする直線で近似符号化する方法である。

上記のチェイン符号化方法は、任意の曲線全近似なしで
忠実に符号化するため、前記ｉｒｆ線近似符号化方法に
比べて符号数が多いという欠点があり、またその直線近
似符号化方法は、第２図に示すように符号化のチューブ
２０幅ｄによって近似精度が決定されるので、符号化し
た後は、その直線近似仔号データを用いて近似精度を変
えて符号化しなおすことはできなかった。そのため用途
別に近似精度を変えた直線近似符号化結果を得たい場合
には、データ量の多い原線図形データを保管しておかな
ければならず、また各画素が幅ｄのチューブ内にあるか
否かの判定は、画素の二次元座標値を用いて行なう必要
があるため、処理喰が多くなる等の欠点があった。

本発明の目的は、上述のような従来の線図形の符号化方
法における欠点を除去するため、原線図形データに比較
して少ないデータ臘で忠実な符号化が行なえるチェイン
符号化データを用いて、高能率に直線近似符号化を行な
うようにした線図形のσ号化方法を提供しようとするも
のである。

本発明の線図形符号化方法ｔよ、１画素幅の線図形を折
線により近似して符号化する方式において、線図形を形
成する画素列を、１府接する画素の連なりの方向が予し
め定めた隣り合う方向となる画素列群に分割し、この分
割した個々の画素列がなす各セグメント毎に１本または
複数本の直線からなる折線で近似して符号化することを
特徴とするものである。

以下、図面に基づいて本発明方法を詳細に説明する。

第８図は、チェイン符号化方法の１種であるセグメント
・チェイン符号化方法の説明図であり、８は線図形を形
成する個々の画素、４はチェイン、５はセグメントであ
る。第４図の表は、チェイン符号化方法におけるチェイ
ン符号とセグメント・チェイン符号化方法におけるオク
タント符号と方向符号の対応関係を示す。

セグメント・チェイン符号化方法は、線図形をなす線分
は局所的に見ると同一方向に連続する場合が多い点に着
目して、符号級を削減する方法である。（参照文献：電
子通信学会論文誌、　ｖｏｌ、　Ｊ　６５−Ｄ、應１１
　、　ｐ、ｐｌ　８９０へ１３９７．「線図形のセグメ
ントチェーン符号化」） 具体的には、第８図に示したように、第１図で説明した
隣接する２つのチェイン符号だけを用いて符号化できる
範囲の画素列をセグメント５と定義し、各セグメント５
を単位にして第４図示の表に従い、チェイン符号欄に示
す隣接関係にある２種のチェイン符号が続く画素列の範
囲を、セグメント５として上欄のそれらのチェイン符号
に対応するオクタント符号のとおりそれぞれ符号化する
方法である。また同時にそのオクタント符号に符号化し
たセグメント５内の２種のチェイン符号の区別を、同図
の表の下軸の方向符号を用いてそれぞれ符号化し、この
方向符号と前記オクタント符号とによって線図形の符号
化データを得るものである。

このようなセグメント・チェイン符号化方法ハ、従来技
術を用いて容易に実現することが−ｉＪ能である。例え
ば線図ＩＩぞを二次元的に光学走査し、光電変換して得
られた画像信号を蓄積し、間知の方法によって基準泣面
の画素に隣り合う画素を検知して、ＨＢｉ図に示したよ
うにその隣接方向に応じチェイン符号化し、第４図示の
表に従ってこのチェイン符号に対Ｉ心する０またＧま１
の方向符号と３ビツト／セグメントのオクタント符号を
発生させるように構成ずれはよい。

第５図および第６図は、線図形を形成する画素列を、隣
接する画素の連なりの方向が予しめ定めた隣り合う方向
となる画素列に分割し、この分割した画素列がなす各セ
グメントとして上記セグメント・チェイン符号化方法に
おけるセグメント５のセグメント・チェイン符号化デー
タを用いた場合の本発明方法の実施例の説明図である。

その第５図は、１個のセグメント５を１本の直線で近似
する場合の説明図で、８は画素、３−１および８−２は
セグメント５の始点および終点の各画素、６はセグメン
ト５に対応する近似直線を示す。

一方、第６図は、１個のセグメント５を、２本のｉＭＭ
Ｂ２１．６−２からなる折線で近似符号化する場合の説
明図である。なお、７は折点を示す。

本発明方法は、セグメント５を単位に符号化処理するも
のであって、第５図に示したようにセグメント５の両端
画素３−１．８−２間を結ぶ近似直線６と、これに対１
心するセグメント５をなす画素列の各画素８との距離ｌ
の最大値によって、近似直線６の近似精度が規定される
。

以下、第５図および第６図に基づいて本発明方法におけ
る符号化処理の流れを説明すると次のとおりである。

（１）第５図において、セグメント５の始点８−１、終
点８−２を両端点とする直線を第１次近似曲線６とする
。

（句　各画素８と第１次近似直線６との距離をめ、最大
距離ｌが許容範囲内にあるか否かを調べ、その最大距離
ｌが許容範囲内であれば、第１次近似直線６を最終近似
直線として、これに対応するセグメント５を１本のｉ［
Ｍで近似符号化する。

（８）　Ｏｆｆ記最大距離ｌが許容範囲外であれば、第
１次近似直線６からの距離が最大となる画素（複数個あ
る場合は、その中の１つの画素）を、第６図に示すよう
に折点１とする。

（４）　次に、第６図に示したように１つのセグメント
５を、２つの第２次近（以１亘線、すなわちセグメント
５の始点画素３−１と折点７を結ぶ近似＋ｉｆ線６−１
および折点７とセグメント５の終点画素８−２を結ぶ近
似直線６−２＆二分割する。

（５）　折点７で分割された画素列の各範囲について、
対応する第２次近似直線６−１．６−２と各ＩＩ！ｉＩ
素との距離を調べ、その距離が許容範囲内にあれば、そ
の画素列の範囲はこれに対応する第２次近似ｉｌｔ線６
−１．６−２を最終近似は線として符号化する。また、
許容範囲外の距離となる画素を含む画素列の範囲につい
ては、その画素列の範囲内に、１）１１記（８）と同様
にして、新たに折点を設定し、近似精度が許容範囲内に
なるまで前記（８）以下の処理過卑を繰り返す。

（６）以上のようにして各セグメント６−１．６−２毎
に近似精度がδ１゛容範囲内に入った１本または偵数本
の直線からなる折線で近似して符号化する。

次に、第７図によって前記近似直線６と、これに対応す
る画素列の各画素８の距離ｔの算出法を説明する。ここ
では第１次近似直線を対象に説明するが、第２次以上の
近似直線に対しても、始点画素８−１または終点画素３
−２を必要に応じて折点画素に置き換えれば以下の説明
はそのまま適用し得るものである。

第７図において、８．９は１個のセグメント５内に含ま
れる２種類のチェイン・ペクトルーフ１．　ｙｉであり
、それぞれはチェイン符号が示す方向に隣接する隣り合
う２個の画素の中−し・間の距離に相当する長さをもっ
ている。

なお、説明上、近似直線６は、始点画素８−１の位置か
ら終点画素３−２の位置への向きをもつベクトルと考え
、これをビと表現する。

この時、次式が成立する。

「−（曾□十＝−＋、　十−−−十ぜ。）　＋（７，十
２＋−−−＋ザ）　−−−（１） 上記（１１式において、ｍ、ｎはセグメント５内に含ま
れるチェイン・ベクトルＷ□ｌ　７１の個数である。そ
の結果、第７図に示すようにチェイン・ベクトルｕｉ＋
　ｙｉを、ベクトル官に直交する成分ｕ／ｉ　ｒ　ｖｌ
ｉと平行な成分と分けて考えると、 しぜ　十寸　十−一一十で　）　＋Ｌ　ｖ、、十１２　
＋−−−／ｌ　／２　．１ｍ 十ｖ’　）−０−−−（１） ／ｎ となる。すなわち、チェイン・ベクトルｕｉｌｖ、の各
１個によって生じる直線ｆからの距離の変動比率は、／
、／であって、相互ｍ　ｎ に逆方向に変動する。ｍまたはｎのいずれか一方が零で
ある場合には、セグメント５は完全に直線６と一致する
ことは明らかであるので、ここではｍ−ｎ＼０としてい
る。

以上のことから、次のようにして近似直線６からの距離
が最大となる画素を決定することができる。すなわち、
始点画素３−１から１１１０次画素列をたどって、ｋ番
目の画素に到達したとする時、それまでに経過したチェ
イン・ベクトルｖ、　、　Ｖ、の個数をそれぞれＭ、Ｎ
個１　ｌ とすれば、当該に番目の画素と近似直線６との距１１１
ｄｋは、 ｄｋ−α・ｌト旧　−（８） （Ｍ十Ｎ−に、αは比例定数） で与えられるから、このｄｋが最大となる画素がめる画
素となる。

七゛グメント・チェイン符号化法で（ま、セグメント５
内の画素数ｆ　ｍ＋ｎ　）は既知であり、かつ、チェイ
ン・ベクトルｕｉｌ　Ｖｉの識別は、第４図の表の方向
符号に対応させればよいのテ、周知の演算回路を用いる
ことによって茶”易に上記の処理によりｄｋが最大とな
る画素をめることができる。

次に、前記近似直線６の近似精度を評価するため、前記
ｄｋの最大距離の絶対値を算出する。そのための処理は
、前述の処理によってめた最大距離を与える画素につい
てのみ行なえばよいので、以下説明する算出式により短
時間に処理し得る。

すなわち、最大距離を与える画素の座標値を（Ｘｋ＋　
Ｖｋ　）　ｒセグメント５の始点画素３−１および終点
画素８−２の各位置をそれぞれ１（Ｘｓ、ｙ８）、（Ｘ
ｅ、ｙｏ）とすると請求める最大距離ｄｍａＸは、 で与えられる。

なお、セグメント・チェイン符号化された画素の座標値
は、始点画素８−１の座標値を基準にして、第４図の表
におけるオクタント符号が示すセグメントについて、同
図の表の下欄の方向符号に関連して、前記座標値のＸ値
またはＹ値％ｂ％、林※れへ両筒に、値ｌの加減算を行
なうことによりめられることＧｌ明らかであるから、前
記（４）式の演算処理も比較的容易に行ない得る。

以上、ｌｌｌｊｍのセグメントについての処理方法を説
明したが、任意のセグメントについても同様に処理し得
ることは明らかである。

このようにして演算処理により得た最大距ｒＡｉ’ｐ　
ｄｍａｘを用いて、近似精度を評価した後の符号化処理
は、さきに第５図および第６図によって説明したとおり
である。

以上、セグメント・チェイン符号化されたデータを用い
た本発明方法の実側例について説明したが、通常のチェ
イン符号化データのセグメント・チェイン符号化データ
への変換は、第４図の表を用いて容易に実行することが
できるので、この変換をｌ’ｌ＋Ｊα理として実行する
ことによりチェイン符号化データに対しても本発明方法
を容易適用し得ることは論をまたない。

以上詳細に説明したように、本発明方法は、線図形を１
１琺成する画素列を、隣接する画素の連り方向にｌＪ６
じて予め定めた隣り合う方向となる画素列群に分割し、
この分割された個々の画素列からなる各セグメント毎に
１本または複数本の直線からなる折線で近似符号化する
方法であるから、線図形をデータ圧縮して、精度高く符
号化し得る効果がある。特に画素の２次元配列として表
現された生の図面データに比較して、大幅にデータ圧縮
されたセグメント・チェイン１子号化データを基本デー
タとして蓄積しておき、これを基に本発明方法により符
号化すれば、所要近似精度に応じてさらにデータ圧縮効
果の高い直線近似符号化データを得ることができる利点
がある。このこと（ま、例えば図面データベースシステ
ムにおいて、センタに基本データとしてセグメント・チ
ェイン符号化データを蓄積しておき、これを遠隔のＸ−
Ｙプロッタに出力する時、所望の近似精度内で直線近似
データに変換して伝送し得ることとなり、伝送コストの
低減上極めて有利である等本発明方法によって得られる
効果は極めて太きい。

【図面の簡単な説明】

第１図は、チェイン符号化方法シこおけるチェインの方
向を示す図、 第２図は、従来の直線近似符号化方法の説明図、第８図
は、セグメント・チェイーン符号化方法＋１ｉＤ説明図
、 第４図は、ヂエイン符号に対重る方向Ｔ′：ｆ号および
オクタント符号の対応間１糸を示す図、第５図および第
６図は、セグメント・チェイン符号化コードを用いた場
合を例にとって本発明方法を説明するための説明図、 第７図は、近似直線と画素の間の距離の算出法σ）−例
の説明図である。 １・・・線図　２・・・チューブ ３、８−１．３−２・・・画素　４・・・チェイン５・
・・セグメント Ｑ、　６−１．　＋３−２・・・近似直線７・・・折点
８，９・・・チェイン・ベクトル。 第６図 第’／　ｌ；ｒｉ −１

Claims (1)

【特許請求の範囲】
1. １１画素１幅の線図形を折線により近似して符号化する
   方式において、線図形を形成する画素列を、隣接する画
   素の連なりの方向が予じめ定めた隣り合う方向となる画
   素列群に分割し、この分割した個々の画素列がなす各セ
   グメント毎に１本または複数本の直線からなる折線で近
   似して符号化することを特徴とする線図形符号化方法。