JPS6286468A - 線画像の折線近似回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （支）産業上の利用分野 この発明は、空間上に表わされた濃淡画像を線画にする
画像処理装置に関する。特に、線画像から、有効な情報
を損わずにデータを圧縮する折線近似回路に関する。

（社）従来技術とその問題点 文字や図形、物体などをＴＶカメラで撮像し、これを画
素に分け、明暗について、ある閾値と比較して二値化し
、細線化処理をすると、輪郭線を現わす線画像が得られ
る。

細線化処理というのは、連続する細い輪郭線を得るため
に、不要な黒画素を消去する処理である。

細線化処理の内容については、いくつかの方法があって
、ここでは説明しない。細線化の方法によって、残る黒
画素が異なってくる。線画像というのは連続する黒画素
の集合である。

線画像には、始点と終点とがある。始点と終点との間は
、画素によって連続的に、接続されている。

線画像のデータは、全画素のｘ％ｙ座標を指定すること
によって完全に記述される。しかし、このようにすると
、データの数が多すぎて、以後の画像処理や、データ記
憶が容易でない。

そこでデータを圧縮するという事が考えられる。

第１図に線画像の例を示す。

始点と終点の間が画素によって連続的に接続されておシ
、連続線は１本しかない。したがって、黒画素そのもの
のかわりに、変化の方向、つまシ線の傾きをデータして
採用することができる。

第２図に、ある画素を中心として、８つの変化の方向を
示す。画素から次の画素への変化は、周囲の８つのいず
れかの画素への変化である。これを０〜７の番号を付け
て、チェインコードと呼ぶ。

直上への動きが０１左上斜めへの動きが１で、以後反時
計廻りにチェインコードが対応づけられている。

チェインコードは３ビツトのデータである。ある画素を
指定するには、ＸＳｙ座標を与えなければならない。こ
れらがｍビット（例えば８ビツト又は１６ビツト）であ
るとすれば、２ｍビットのデータ量が必要である。とこ
ろが、チェインコードは３ビツトであるから、ひとつの
点を指定するためのデータ量は（２ｍ−８）ビット減少
する。

そこで、線画像を指定するため、始点の座標（ｘｏ　ｓ
３’ｏ　）と、これに続く変化の方向についてチェイン
コードの系列を用いる、という事が一般に行なわれる。

第８図は第１図の線画像をチェインコードの系列によっ
て表現したものである。

始点から第２点への変化は右上斜めであるから、チェイ
ンコードは７である。第２点から第３点への変化は真上
方向であるから、チェインコードは０である。第３点か
ら第４点への変化は真上方向であるから、チェインコー
ドはＯである。以下同様にして、チェインコードを並べ
てゆき、終点に至る。始点とチェインコード列によシ、
線画像を一意的に指定できる。

このようにしても、未だ線画像のデータが多すぎるので
、もつとデータを圧縮する事が望まれる。

このため、折線近似という事がなされる。

これは、線画像を直線とみなしうる部分毎に分割し、各
部分を線分で近似するものである。

曲線ではなく線分で近似するから、近似後の画像は折線
になる。このため、折線近似と呼んでいる。

折線近似すると、データは折線の交差点を指定するもの
だけに減少する。従って、データの数は大幅に減少する
事になる。

従来の折線近似法は、線画像を始点から追跡し、変化の
方向が変わる点（換向点と呼ぶ）を検出し、換向点の間
を線分で結ぶ方法が主流であった。

変化方向は８つのチェインコードによって表わされてい
るから、変化方向の変化は、チェインコードの変化をみ
ることによって分る。従って換向点を順次検出するのは
容易である。

この方法は、いわば微分法であるから、局所的なノイズ
に弱いという難点がある。

線画像を得るには、対象物に照明を当て、反射光をＴＶ
カメラで撮像し、縦横の画素に分け、画素の明暗を二値
化する処理が必要である。このため、照明の状態によっ
て、ノイズが生ずることもある。また、細線化処理によ
ってノイズが発生することもある。

従来法は、換向点を全て検出するから、ノイズをそのま
ま含んでしまう。局所的なノイズは落してしまう方がよ
いのである。

さらに、前記の微分法は、データの圧縮はできるが、線
画像の形状はそのまま残るので、画像的には近似とはい
えない。

近似というのは、データを圧縮する事が、大きな目的で
あるが、それだけではなく、ノイズを落す、という事も
あるのである。

（＋７）　　　　目　　　　　的 線画像のデータ量を圧縮するために、局所的なノイズに
対して強く、任意の近似度で折線近似できるような線画
像の折線近似回路を与える事が本発明の第１の目的であ
る。

比較的簡単な回路によって、折れ目となる画素の座標を
高速で見い出すことのできる折線近似回路を与える事が
本発明の第２の目的である。

比較的簡単な素子の組合わせからなる回路であって、容
易にＬＳＩ化することのできる折線近似回路を与えるこ
とが本発明の第３の目的である。

に）折線近似の原理 従来の微分的な折線近似に対し、本発明者は、いわば積
分的な折線近似法を確立した。これは、チェインコード
で記憶された線画像に対して、極めて有効に使用できる
方法である。

まず、本発明者の創意になる折線近似法を説明する。

まず、始点Ａ（Ｘｏｌｙｏ）と終点Ｂ（ｘｌ、ｙｌ）と
を結ぶ。線分ＡＢが得られる。線分ＡＢがこの線画像の
第０近似を与える。

直線ＡＢは、線分ＡＢを両側へ無限に延長した直線のこ
とである。ある点と直線の距離というのは、その点から
直線に下した垂線の長さの事である。垂線の足が線分の
外にあっても同じように距離を一義的に定義できる。

線画像を構成する任意の１番目の画素と、直線ＡＢとの
距離をｄｉとする。

第４図にこれらの関係を示す。

全ての画素について距離ｄｔ　ｆ求め、この内の最大値
をｄｊとする。最大値を与える画素をｊとする。

これを０点（Ｘｊ、Ｙｊ）とする。０点を最大距離点と
呼ぶ。

予め近似の度合を決定する距離ｌを与えておく。

これを近似長ｌと呼ぶ。

ｄｊと４とを比較する。ｄｊがｌよシ小さければ、近似
操作を打ち切る。ｄｊがｌよシ大きければ、始点Ａ１終
点Ｂと、最大距離点Ｃ（Ｘｊ、Ｙｊ）とを結ぶ。

第５図にこれを示す。線画像は２本の線分ＡＣ１０Ｈに
よって近似されている。これが第１近似である。

次に、直線ＡＣと、端点Ａ、Ｃで挾まれる全ての画素と
の距離を計算し、その最大値を求める。

最大値を与える点も求める。これがＤ点であるとする。

Ｄ点と直線ＡＣの距離と近似長ｌとを比較する。ｌの方
が長かったとする。この場合、もはや近似を進めない。

つまｆｉ、Ａ、０点とＤ点とを結ばず、線分ＡＣのまま
にしておく。

線分ＣＢについても同様のことをする。

直線ＣＢと、Ｃ，Ｂ点で挾まれる線画像１全ての画素と
の距離を求める。距離の最大値をｄｏとし、最大値を与
える点をＥとする。最大距離ｄｅと近似長ｌとを比較す
る。ｄｅＯ方が６．１大きいとする。この場合、端点Ｃ
，Ｂと最大距離点Ｅとを結ぶ。線分ＧＥ、ＥＢに関して
は第２近似である。

さらに、ＣＥ間及びＥＢ間について、最大距離をそれぞ
れ求め、これと近似長ｌとを比較する。

いずれの最大距離も近似長ｌよシ短いとする。ここで近
似を打ち切る。第６図にこれを示す。

このように、最大距離を与える点を検出し、これが４よ
シ長ければ、この点と両端点とを線分で結合する。新た
な線分はよフ高い近似を与える。

この線分を含む直線と、線分の端点て挾まれる全ての画
素との最大距離を求め、これがｌよシ長ければ、同じよ
うにして線分を引いて近似を高める。

以下、最大距離が近似長ｌより短くなるまで、このよう
な操作を繰り返す。

最大距離がｌよシ短くなれば、近似操作を終了する。

このようにして、任意の線画像を折線近似する事ができ
る。

近似長ｌが長ければ、粗い近似になるが、近似操作に要
する時間は短い。

近似長ｌが短いと、よシ細い近似になるが、近似に要す
る時間は長くなる。また、ｌがあまシに短いと、ノイズ
が落ちない、という欠点もあられれる。ノイズや必要な
時間、要求される図形などによシ、適当な近似長ｌを決
定する。

団　必要な計算式 次に、画素ｊと、距離ｄｊの算出方法について説明する
。

画素面はｘｙ座標で指定されている。

始点（Ｘ８％　ｙｏ　）と終点（Ｘｌ、ｙｌ）を通る直
線をａｘ　−１−ｂｙ　十〇　＝　Ｑによって表わす。

この直線と画素１（ｘｉ、ｙｔ）との距離ｄｉは次式で
与えられる。

パラメータａ％ｂ、ｃは、始点終点の座標を上記の直線
の式に入れて求めることができる。

パラメータの比の値は決まるが、絶対値は決まらない。

そこで、簡単・に、 ａ　＝　ｙｌ−ｙｏ　　　　　　　　　（２）ｂ”’　
　Ｘｏ　　Ｘｔ　　　　　　　　　　（８）Ｃ”　　Ｘ
１３’ＯＸＯ３’ｌ　　　　　　　　（４’とする事が
できる。もちろんこれらに定数を乗じたものであっても
よい。

ｄｌが最大となる画素ｊを求める時は、分母ｄ’ｉ　　
＝＝　ｌ　ａＸｉ　十ｂｙｉ　＋　ＣＩ　　　（５１を
定義し、これが最大となる画素ｊを求める。

線画像の任意の連結において、ある画素（ｘｉ　％　ｙ
ｉ　）と、直前の画素（ｘｉ−１、ｙｉ−１）との変化
分がｍｉ。

ｎｉで表わされるとする。ｍｌ、ｎｉは０１＋１、−１
のいずれかの値をとシ、チェインコードト一対−の対応
がある。いずれもＯであることはない。

これらの値に関して、 ｘｔ　　＝　　Ｘｌ−１＋ｍｔ　　　　　　　　（６１
ｙｉ　　＝　　ｙｉ−１−１−ｎｉ　　　　　　　　（
７）が成り立つ。ｍはＸ方向への増分、ｎはｙ方向の増
分であるから、第２図で定義されるチェインコードに対
し、次の関係がある。

これを第１表に示す。右欄のマルチプレクサ出力につい
ては後に述べる。

第１表　チェインコードとｍ、　ｎの値、マルチプレク
サ出力ａｘｉ−１−ｂｙｉ　＋ｃ　　＝　ａＸｏ＋１）
３’ｏ　＋Ｃとなる。始点（ａｏＳｙｏ）は直線ａｘ　
＋ｂｙ　−ｔ−ｃ　＝　００上にあるから、（８）式の
右辺第１項は０である。

従って、ｄｌの値は、 となる。同じ式は、次のようにも表現できる。

Δに＝　ａｍｈ　　＋　　ｂｎｓｔ　　　　　　　（１
０）Σｋ　＝　ΣΔｈ　　　　　　　　　　（１１）ｈ
＝１ ここで、Σ１−１の絶対値がｄ’ｉ−ｉである。

チェインコードによって、２つの整数ｍｋ、ｎｋが与え
られ、Δにはこれによって決まる。Δｋ　はｍ、ｎを０
１＋１として与えられるが、次の８つの値ａ、　−ｂ、
　−ａ、　　ｂ、　　ａ＋ｂ、　−ａ十す、　　ａ−ｂ
。

−ａ−ｂ′ｆｆ：とる。

結局、代数的距離Σｉは、前のΣ１−１に、ａ、−ｂ。

−ａ　、・・などを加える事によって求められる。

つまシ、チェインコード列を追跡してゆく際、前の値Σ
ｉｌを保持してゆけば、Δにの足し算のみで、Σｉを求
めることができる。

また、この際に、ｘｌｙの値を平行に計算し、ｄ’ｉが
最大になる時の値（Ｘｊ　Ｓ’ｆｊ）を保存すると（１
■ とにすれば、簡単な方法で高速にｄ’ｔを求め、その画
素の座標が分る。最大距離点の座標が分っていれば、始
点、終点と最大距離点とを結ぶ線分をすぐに確定できる
。次の段階への近似へ迅速に進むことができる。

□□□）発明の構成 本発明は以上に述べた計算を迅速に行なう回路構成に関
するので、第７図によってこれを説明する。

定数レジスタ１〜８は、始点（ｘｏ　ｓ　ｙｏ　）と、
終点（Ｘｌ、’／ｘ　）の座標の値から計算されるａ、
ｂ。

−ａ、　−ｂ、　ａ−ｂ、−ａ＋ｂ、Ｉａ十す、　−ａ
−ｂ　　（７）値を演算に先立ってあらかじめ格納して
おくレジスタ群である。

定数レジスタ１〜８の出力は、マルチプレクサ９に入力
される。これは８人力１出力のマルチプレクサであって
、チェインコードが入力され、第１表に従ってチェイン
コードの値に対応する定数レジスタのひとつの内容（ａ
ｌｂｌ−ａｌ−ｂｌ・・・・の内のひとつ）を選択して
出力する。

マルチプレクサ９の出力は、加算器１０に入力される。

マルチプレクサの出力は、前述のΔｋに当る値であシ、
これとレジスタ１１に保持されている直前の画素までの
代数和Σｋ−１とが加算されて、Σｋが求められる。

この値は、レジスタ１１に入力されてここで一時的に保
持される。

結局、加算器１０とレジスタ１１は、加算器１０に入力
されるΣΔにの値を求めるアキュームレータとなってい
る。つまシ、ｋ番目のチェインコードが入力された後、
Σｋの値が加算器の出力に現われる。

絶対値算出回路１２は加算器出力の絶対値Σｋを計算す
る回路である。これは距離ｄ’ｋに等しい。

絶対値算出回路１２の出力は、レジスタ１４と比較器１
５に与えられる。

比較器１５は５番目の距離ｄ’ｉが入力された時、レジ
スタ１４に保持された値とこれを比較し　ｄ／ｉの方が
大きいか又は等しければ、レジスタ１４にｄ’ｉをロー
ドする制御信号を出す。レジスタ１４にｄ’ｔが格納さ
れる。ｄ’ｔの方が小さい時は制御信号は出ない。レジ
スタ１４の内容は不変に保たれる。

従って、レジスタ１４が最初０にセットされていれば、
この中には、ｉ番目までの距離の最大値が常に格納され
ていることになる。つまり、レジスタ１４と比較器１５
は最大値検出回路として機能しているのである。

カウンタ１３はチェインコードの数を数えるカウンタで
あシ、チェインコードが入力されるごとに内容を＋１す
る。チェインコード計数カウンタ１３の出力が入力され
るレジスタ１６は比較器１５の制御信号によって、カウ
ンタ１３の値をロードする。つまシ、レジスタ１６には
、ｉ番目までの画素の内、最大距離を与える画素の番号
が一時的に保持されることになる。

デコーダ１７はチェインコードの値（θ〜７）に対して
、ｘ１ｙ方向の変化量ｍ、ｎを、第１表に従って、出力
する。この内ｍの値は、Ｘ方向カウンタ１８に与えられ
る。Ｘ方向カウンタ１８は、アップダウンカウンタであ
って、ｍの値を積算する。ｍはＯ１＋１、−１　　であ
るからカウンタで積算できる。

ｎの値は、Ｘ方向のカウンタ１９に与えられる。

Ｘ方向カウンタ１９はｎの値を積算する。

これらカウンタ１８．１９はプログラマプ／Ｌ／（ブリ
セラタブ／Ｌ／）カウンタであって、初期値を設定でき
る。初期値として、始点（ｘｏ　ｓ　３’ｏ　）の座標
Ｘｏ　ｓ　７ｏを与える。これ以後、Ｘ方向、Ｘ方向の
変化ｍｋ、ｎｋを順に加えてゆくから、１番目のチェイ
ンコードが入力された時、カウンタ１ｇハＸｔＯ値、カ
ウンタ１９はＹｉＯ値を保持している事になる。つまシ
、１番目の画素の座標（Ｘｉ、　Ｙｉ）がこれによって
分る。

Ｘ方向レジスタ２０、Ｘ方向レジスタ２１は、比較器１
５が制御信号を発した時に、Ｘ方向カウンタ１８、Ｘ方
向カウンタ１９の出力をそれぞれロードする。比較器１
５は、ｄ′ｉの方が、レジスタ１４に保持される値よシ
大きい時に、つまシ、ｄ’１が１番目までで最大値であ
る時に、制御信号を発するから、Ｘ方向レジスタ２０、
Ｘ方向レジスタ２１は、最大距離を与える画素のＸ座標
、Ｙ座標を保持することになる。

従って、終点まで全てのチェインコードが読み出された
時、Ｘ方向レジスタ２０、Ｘ方向レジスタ２１には、ｄ
’１の最大値ｄ／ｊを与える画素ｊのＸ１ｙ座標である
ｘｊｌＹｊが保持されている。ｊの値は、レジスタ１６
に保持されている。ｄ′ｊの値はレジスタ１４に保持さ
れている。

ｄ′ｊの値から、（１）式に従ってｄｊを求め、これと
近似長ｌとを比較する。

ｄｊＯ方がｌよシ大きければ、始点、終点と、最大距離
点（ＸＩＹｊ）とを線分で接続する。ｄｊＯ方がｌよシ
小さければ、これで近似操作を打ち切る。

始点、終点と最大距離点を線分で連結すると、一本の線
分が２本の線分になったわけで、よシ高次の近似になっ
たことになる。

次に、新しい線分の始点、終点が決まるので、これによ
って、ａ、ｂの値を決定する。ａ、ｂの値が決まれば、
定数レジスタ１〜８の値も決まるので、前回の保持値、
ａ％　５％　　’１−ｂ％・・・・のかわシに、新しく
計算された保持値を定数レジスタに入力させる。そして
、同様にチェインコードをマルチプレクサ９、デコーダ
１７に入力してユキ、新たに最大値を求める。

ただし、後半の部分については、（ｊ＋１）番目の画素
がチェインコードの１番目になる。５番目の画素が始点
になるからである。

いずれの回の演算に於ても、演算に先立って、レジスタ
１１．１４、カウンタ１６はクリヤしておき、カウンタ
１８．１９にはその回の始点の座標Ｘｏｓ’１０をロー
ドしておく。

（至）　発明の効果 （１）　　チェインコードで表現された線画像を折線で
近似するから、データ量を大幅に圧縮する事ができる。

（２）換向点を見つけるのではなく、長い線分と画素と
の距離が一定値以下になるように折線近似するので、ノ
イズに対して強い。ｌがノイズのゆらぎよシ大きければ
、ノイズは落ちてしまう。

（３）近似長ｌがパラメータになっている。これが制御
可能なパラメータであるから、任意の精度で、折線近似
する事ができる。

近似の程度を指定する事ができる。ｌが近似の程度を表
現すると考えることもできる。

（４）比較的簡単な回路で、折れ目となる画素の番号ｊ
と、座標Ｘｊ１Ｙｊとが高速で見出される。

（５）簡単な機能の素子を組合わせればこの回路を作る
ととができるので、回路の全体をＬＳＩ化する事は容易
である。

【図面の簡単な説明】

第１図は２次元線画像の一例を示す図。 第２図は画素から次の画素への変化の方向とチェインコ
ードの対応説明図。 第３図は第１図の線画像をチェインコードで表示した例
。 第４図は本発明で用いる折線近似原理の説明図であって
、第Ｏ近似を示す線図。 第５図は第１近似を示す線図。 第６図は第２近似以後の最終的な近似線図。 第７図は本発明の折線近似回路構成図。 １〜８・・定数レジスタ ９　・・・・マルチプレクサ １０・・・・加　算　器 １１・・・・レジスタ １２・・・・絶対値算出回路 １３・・・・カウンタ １４・・・・レジスタ １５・・・・比　較　器 １６・・・・レジスタ １７・・・・デコーダ １８・・・・　Ｘ方向カウンタ １９・・・・　Ｘ方向カウンタ ２０・・・・　ｎ方向レジスタ ２１・・・・　ｙ方向レジスタ 発明者　　　朝夷名　　巧 小　　城　　邦　　雄

Claims (1)

【特許請求の範囲】
1. チェインコードで表現された線画像を直線とみなしうる
   部分毎に分割し、各部分を線分で近似するため、線画像
   の始点と終点とを線分で結びこれを含む直線と画素との
   距離の最大値ｄ＿ｊと最大値を与える画素ｊと座標Ｘ＿
   ｊ、Ｙ＿ｊとを求め、ｄ＿ｊが予め定められた近似長ｌ
   より大きい場合は始点、終点と最大距離点ｊとを線分で
   結んで近似を高め、さらにこれら線分を含む直線と線分
   の端点で挾まれる画素との距離の最大値と、最大値を与
   える画素とその座標とを求め、最大距離がｌより大きけ
   れば、該線分の端点と最大距離点とを線分で結び近似を
   高める操作を繰り返して、直線と画素の最大距離がｌ以
   下になるまで線画像を折線近似することとし、始点、終
   点の座標の差ａ、ｂから計算されるところの８つの定数
   ａ、ｂ、−ａ、−ｂ、ａ＋ｂ、−ａ−ｂ、−ａ＋ｂ、ａ
   −ｂを保持する８つの定数レジスタ１〜８と、線画像を
   表現するチェインコードを入力する事により前記定数レ
   ジスタ１〜８のひとつを選択するマルチプレクサ９と、
   前記マルチプレクサ９の出力Δ＿ｋを加算累積するアキ
   ュームレータと、アキュームレータの出力Σ＿ｋの絶対
   値ｄ＿ｋ′を求める絶対値算出回路１２と、絶対値算出
   回路１２の出力の（ｋ−１）番目までの最大値を保持す
   るレジスタ１４と、絶対値算出回路１２の出力ｄ＿ｋ′
   と、レジスタ１４の保持値とを比較しｄ＿ｋ′の方が大
   きいか又は等しい時にｄ＿ｋ′の値をレジスタ１４にロ
   ードする制御信号を発する比較器１５と、チェインコー
   ドの数を計数するカウンタ１３と、比較器１５からの制
   御信号によつて前記カウンタ１３の値をロードするレジ
   スタ１６と、チェインコードから線画像のｘ方向の変化
   ｍ＿ｋとｙ方向の変化ｎ＿ｋとを求めるデコーダ１７と
   、始点の座標ｘ＿０、ｙ＿０を予め入力しておきこれら
   にｘ方向変化ｍ＿ｋ、ｙ方向変化ｎ＿ｋを加算しｋ番目
   の画素の座標Ｘ＿ｋ、Ｙ＿ｋを求めるｘ方向カウンタ１
   ８、ｙ方向カウンタ１９と、比較器１５からの制御信号
   によつてｘ方向カウンタ１８、ｙ方向カウンタ１９の値
   をロードするｘ方向レジスタ２０、ｙ方向レジスタ２１
   とよりなる事を特徴とする線画像の折線近似回路。