JPS6373381A - ベクトル生成方法 - Google Patents
ベクトル生成方法Info
- Publication number
- JPS6373381A JPS6373381A JP21771686A JP21771686A JPS6373381A JP S6373381 A JPS6373381 A JP S6373381A JP 21771686 A JP21771686 A JP 21771686A JP 21771686 A JP21771686 A JP 21771686A JP S6373381 A JPS6373381 A JP S6373381A
- Authority
- JP
- Japan
- Prior art keywords
- point
- distance
- maximum
- points
- chain code
- 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.)
- Granted
Links
Landscapes
- Image Processing (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔概要〕
細線化した２（＋！両画像端点１分岐点間で折線近似法
によりベクトル化する処理において、該画像データの全
点で、両端を結ぶ線分との距離計算を実行すると、処理
時間が増大すると云う問題を解決する為に、該距離計算
を行う前に、その点において、距離が直前の値より増加
するか、減少するかを求め、増加から減少、或いは減少
から増加に変化する点においてだけ、上記距離計算をす
るようにしたものである。
によりベクトル化する処理において、該画像データの全
点で、両端を結ぶ線分との距離計算を実行すると、処理
時間が増大すると云う問題を解決する為に、該距離計算
を行う前に、その点において、距離が直前の値より増加
するか、減少するかを求め、増加から減少、或いは減少
から増加に変化する点においてだけ、上記距離計算をす
るようにしたものである。
本発明は、画像データのベクトル化方法、特に、細線化
した画像データから折線近似によってベクトルを生成す
る方式に関する。
した画像データから折線近似によってベクトルを生成す
る方式に関する。
最近の計算機によるデータ処理の多様化に伴って、計算
機支援設軒（ＣＡＤ）等の分野においては、図面をスキ
ャナで読み取り、ベクトル化して計算機に入力すること
が行われており、そのときの処理量の増大化に伴って高
速に入力できることが求められるようになっている。
機支援設軒（ＣＡＤ）等の分野においては、図面をスキ
ャナで読み取り、ベクトル化して計算機に入力すること
が行われており、そのときの処理量の増大化に伴って高
速に入力できることが求められるようになっている。
特に、前述の計算機支援設計（ＣＡＤ）等の場合のよう
に、大量の図面を入力することが必要な分野では、一枚
当たりの入力時間を極力小さく抑えなければならない。
に、大量の図面を入力することが必要な分野では、一枚
当たりの入力時間を極力小さく抑えなければならない。
こうした事情からベクトル生成処理の処理時間の短縮が
急務となっている。
急務となっている。
〔従来の技術と発明が解決しようとする問題点〕第５図
は従来のベクトル生成方式を説明する図であって、（イ
）は構成例を示し、（ロ）は細線化パターンの一例を示
し、 （ハ）は折線生成処理を示している。
は従来のベクトル生成方式を説明する図であって、（イ
）は構成例を示し、（ロ）は細線化パターンの一例を示
し、 （ハ）は折線生成処理を示している。
先ず、（イ）図の細線化部１０では、（ロ）図の（ａ）
、 （ｂ）に示すように、例えば、３×３の大きさの
マスクに特定のパターンが出現したとき、その中心の黒
画素を°白゛に変更すると云う処理を繰り返し、線幅を
持つ入力画像データから線幅１の細線化画像を作成する
。
、 （ｂ）に示すように、例えば、３×３の大きさの
マスクに特定のパターンが出現したとき、その中心の黒
画素を°白゛に変更すると云う処理を繰り返し、線幅を
持つ入力画像データから線幅１の細線化画像を作成する
。
次の点列抽出部１４では、上記マスク処理によって、
（ロ）図の（ｃ） 、 （ｄ）に示すような分岐点パタ
ーンや８同図の（ｅ） 、 （ｆ）に示すような端点パ
ターンを探し出す。
（ロ）図の（ｃ） 、 （ｄ）に示すような分岐点パタ
ーンや８同図の（ｅ） 、 （ｆ）に示すような端点パ
ターンを探し出す。
続いて、ある端点、或いは分岐点から始めて、連続する
黒画素を、次の端点、或いは分岐点が出現する迄追跡し
て点列を取り出す。
黒画素を、次の端点、或いは分岐点が出現する迄追跡し
て点列を取り出す。
折線生成部１３では、（ハ）図に示すように、点列の両
端°を結ぶ線分と、上記点列を形成している各画素との
距離゛Ｈ゛を求め、該距離゛Ｈ゛が最大になる点におけ
る距離の値’Ｈｍａｘ’が予め設定しておいた闇値（１
１ｔｈ）以上であれば、その点を屈曲点とし、該“Ｈｍ
ａｘ’が闇値以下であれば、該２点間を結ぶ線分をベク
トルとする。
端°を結ぶ線分と、上記点列を形成している各画素との
距離゛Ｈ゛を求め、該距離゛Ｈ゛が最大になる点におけ
る距離の値’Ｈｍａｘ’が予め設定しておいた闇値（１
１ｔｈ）以上であれば、その点を屈曲点とし、該“Ｈｍ
ａｘ’が闇値以下であれば、該２点間を結ぶ線分をベク
トルとする。
このような、従来のベクトル生成方式では、点列の抽出
で、端点、或いは分岐点に挟まれた点列の全てを抽出し
、全点において距離計算を行っているので、前述の距離
が最大になる点を求める為の処理時間が大きくなると云
う問題があった。
で、端点、或いは分岐点に挟まれた点列の全てを抽出し
、全点において距離計算を行っているので、前述の距離
が最大になる点を求める為の処理時間が大きくなると云
う問題があった。
本発明は上記従来の欠点に鑑み、上記距離計算を行う際
の処理時間を短縮させるベクトル生成方式を提供するこ
とを目的とするものである。
の処理時間を短縮させるベクトル生成方式を提供するこ
とを目的とするものである。
第１図は本発明のベクトル生成方式の原理ブロック図で
ある。
ある。
本発明においては、
画像を細線化し、分岐点、端点に挟まれた点列を抽出し
て、両端を結ぶ線分との距離が最大になる点列内の点を
求めて、画像を折線近似するベクトル生成方式であって
、 線幅１の画像データを作成する細線化部１０と、分岐点
、端点間の点列に傾斜角コード（チェインコード）を与
え、該チェインコードが変化する点を抽出するチェイン
コード変化点抽出部１１と、チェインコード変化点の中
から、更に、両端を結ぶ線分との距離が極大、或いは極
小になる点だけを選択する距離極大・極小点抽出部１２
と、距離極大・極小点に対して距離が最大になる点を求
めて、その点で屈曲するベクトルを生成する折線生成部
１３と、 を備えてベクトルを生成するように構成する。
て、両端を結ぶ線分との距離が最大になる点列内の点を
求めて、画像を折線近似するベクトル生成方式であって
、 線幅１の画像データを作成する細線化部１０と、分岐点
、端点間の点列に傾斜角コード（チェインコード）を与
え、該チェインコードが変化する点を抽出するチェイン
コード変化点抽出部１１と、チェインコード変化点の中
から、更に、両端を結ぶ線分との距離が極大、或いは極
小になる点だけを選択する距離極大・極小点抽出部１２
と、距離極大・極小点に対して距離が最大になる点を求
めて、その点で屈曲するベクトルを生成する折線生成部
１３と、 を備えてベクトルを生成するように構成する。
即ち、本発明によれば、細線化した２値画像を端点１分
岐点間で折線近似法によりベクトル化する処理において
、該画像データの全点で、両端を結ぶ線分との距離計算
を実行すると、処理時間が増大すると云う問題を解決す
る為に、該距離計算を行う前に、その点において、距離
が直前の値より増加するか、減少するかを求め、増加か
ら減少。
岐点間で折線近似法によりベクトル化する処理において
、該画像データの全点で、両端を結ぶ線分との距離計算
を実行すると、処理時間が増大すると云う問題を解決す
る為に、該距離計算を行う前に、その点において、距離
が直前の値より増加するか、減少するかを求め、増加か
ら減少。
或いは減少から増加に変化する点においてだけ、上記距
離計算をするようにしたものであるので、該距離計算を
行う際の点列の数が少なくなり、折線生成部での距離計
算の為の処理時間の短縮化が図れる効果がある。
離計算をするようにしたものであるので、該距離計算を
行う際の点列の数が少なくなり、折線生成部での距離計
算の為の処理時間の短縮化が図れる効果がある。
以下本発明の実施例を図面によって詳述する。
前述の第１図が本発明のベクトル生成方式の原理ブロッ
ク図であり、第２図は本発明のチェインコード変化点抽
出部の処理を説明する図であり、第３図は本発明の距離
極大・極小点抽出部の処理を説明する図であり、第４図
は折線生成部で距離最大の点を求める処理を説明する図
であって、第１図におけるチェインコード変化点抽出部
１１．距離極大・極小点抽出部１２が本発明を実施する
のに必要な手段である。尚、全図を通して同じ符号は同
じ対象物を示している。
ク図であり、第２図は本発明のチェインコード変化点抽
出部の処理を説明する図であり、第３図は本発明の距離
極大・極小点抽出部の処理を説明する図であり、第４図
は折線生成部で距離最大の点を求める処理を説明する図
であって、第１図におけるチェインコード変化点抽出部
１１．距離極大・極小点抽出部１２が本発明を実施する
のに必要な手段である。尚、全図を通して同じ符号は同
じ対象物を示している。
以下、第１図〜第４図によって、本発明のベクトル生成
方式を説明する。
方式を説明する。
先ず、第２図は本発明のチェインコード変化点抽出部１
１での処理を説明する為の図である。
１での処理を説明する為の図である。
即ち、第２図の（ａ）は、細線化部１０において細線化
された画像データの一例であり、（ｂ）図は該細線化さ
れた画像データの点列において、ある点から、それに隣
接する点へ移動するときの方向を０゛〜°７′ で表現
することを示すもので、これを傾斜角コード（チェイン
コード）と呼ぶ。第２図の（ｃ）図は、上記（ａ）図で
示した点列に対するチェインコード列であり、Ｏ印で囲
んでいるチェインコードが変化点を示している。そして
、（ｄ）図は（ｃ）図のチェインコード列から該チェイ
ンコードが変化する点（上記○印で囲んだチェインコー
ドを持った点）だけの座標（Ｘ、Ｙ）と、その点のチェ
インコードとをテーブルにしたものである。
された画像データの一例であり、（ｂ）図は該細線化さ
れた画像データの点列において、ある点から、それに隣
接する点へ移動するときの方向を０゛〜°７′ で表現
することを示すもので、これを傾斜角コード（チェイン
コード）と呼ぶ。第２図の（ｃ）図は、上記（ａ）図で
示した点列に対するチェインコード列であり、Ｏ印で囲
んでいるチェインコードが変化点を示している。そして
、（ｄ）図は（ｃ）図のチェインコード列から該チェイ
ンコードが変化する点（上記○印で囲んだチェインコー
ドを持った点）だけの座標（Ｘ、Ｙ）と、その点のチェ
インコードとをテーブルにしたものである。
このように、チェインコード変化点抽出部１１において
は、点列のチェインコードを調べ、直前のチェインコー
ドと異なる点だけを求める処理を行っている。
は、点列のチェインコードを調べ、直前のチェインコー
ドと異なる点だけを求める処理を行っている。
次に、第３図によって、距離極大・極小点抽出部１２で
の処理を説明する。
の処理を説明する。
先ず、上記チェインコード変化点抽出部１１で求めた点
列の両端点を結ぶ線分の傾きθによって、８個のケース
に場合分けする。（（ａ）回診照）第２図（ａ）の例は
、ケース■に該当する。第３図（ａ）に示した各ケース
での、上記チェインコードに対応させた符号は、傾きθ
に対応して、前述の距離が単調に増加するか、或いは減
少するかを’＋’、’−’で表したものである。
列の両端点を結ぶ線分の傾きθによって、８個のケース
に場合分けする。（（ａ）回診照）第２図（ａ）の例は
、ケース■に該当する。第３図（ａ）に示した各ケース
での、上記チェインコードに対応させた符号は、傾きθ
に対応して、前述の距離が単調に増加するか、或いは減
少するかを’＋’、’−’で表したものである。
距離極大・極小点抽出部１２においては、第３図（ａ）
で示したチェインコードと符号との対応関係を、上で求
めた点列内の各点について求める。
で示したチェインコードと符号との対応関係を、上で求
めた点列内の各点について求める。
例えば、第２図（ｄ）で求めた例では、本図（ｂ）の表
のように対応付けられる。
のように対応付けられる。
この表から、両端点と、符号が直前のものと異なる点（
○印で示す）だけを取り出すと、本図（ｃ）に示す表が
作成できる。
○印で示す）だけを取り出すと、本図（ｃ）に示す表が
作成できる。
この表で、一番上と、一番下の座標は両端点であるので
、残りの５個の点で、前述の距離を求め、最大になる点
を決めれば良いことになる。
、残りの５個の点で、前述の距離を求め、最大になる点
を決めれば良いことになる。
第４図によって、折線生成部１３における点列の両端点
を結ぶ線分と、第３図（ｃ）で示した各点との距離の求
め方を説明する。
を結ぶ線分と、第３図（ｃ）で示した各点との距離の求
め方を説明する。
本図の（ａ）において、各点における上記線分との距離
゛Ｈ”は、図中に示した計算式で求めることができるが
、この計算式の分母は、各点の座標に依存しない。そこ
で、各点における分子だけを計算し、最大となる点を求
めると、第３図（ｃ）に示した各点については、第４図
（ｂ）のようになり、座標（６，１，３）の点で距離が
最大（Ｈｍａｘ）となることが分かる。
゛Ｈ”は、図中に示した計算式で求めることができるが
、この計算式の分母は、各点の座標に依存しない。そこ
で、各点における分子だけを計算し、最大となる点を求
めると、第３図（ｃ）に示した各点については、第４図
（ｂ）のようになり、座標（６，１，３）の点で距離が
最大（Ｈｍａｘ）となることが分かる。
この点の距離は、第４図（ａ）で示した計算式から、
Ｈ＝６９ ／ （（１２−５）”＋（１０−２）２１
””＝６．４９１となる。
””＝６．４９１となる。
この値が、予め設定されている距離の闇値より −
大きいかどうかを判定し、大きいときは、この点を屈曲
点として、この点と１両端点を結ぶ線分に対して距離極
大・極小点抽出部１２以降での処理を繰り返すことによ
り、第２図（ａ）で示した画像データのベクトル化が行
われる。
大きいかどうかを判定し、大きいときは、この点を屈曲
点として、この点と１両端点を結ぶ線分に対して距離極
大・極小点抽出部１２以降での処理を繰り返すことによ
り、第２図（ａ）で示した画像データのベクトル化が行
われる。
このように、本発明は、細線化した点列内の全点と、該
点列の両端を結ぶ線分との距離を計算することなく、各
点列において、各点を結ぶ線分の傾斜角（θ）が変化す
る点を抽出し、更に、その変化した点列の中から該傾斜
角が単調に増加するか、或いは減少するかの変曲点を求
め、その点についてのみ、距離計算をするようにした所
に特徴がある。
点列の両端を結ぶ線分との距離を計算することなく、各
点列において、各点を結ぶ線分の傾斜角（θ）が変化す
る点を抽出し、更に、その変化した点列の中から該傾斜
角が単調に増加するか、或いは減少するかの変曲点を求
め、その点についてのみ、距離計算をするようにした所
に特徴がある。
以上、詳細に説明したように、本発明のベクトル生成方
式は、細線化した２値画像を端点１分岐点間で折線近似
法によりベクトル化する処理において、該画像データの
全点で、両端を結ぶ線分との距離計算を実行すると、処
理時間が増大すると云う問題を解決する為に、該距離計
算を行う前に、その点において、距離が直前の値より増
加するか。
式は、細線化した２値画像を端点１分岐点間で折線近似
法によりベクトル化する処理において、該画像データの
全点で、両端を結ぶ線分との距離計算を実行すると、処
理時間が増大すると云う問題を解決する為に、該距離計
算を行う前に、その点において、距離が直前の値より増
加するか。
減少するかを求め、増加から減少、或いは減少から増加
に変化する点においてだけ、上記距離計算をするように
したものであるので、該距離計算を行う際の点列の数が
少なくなり、折線生成部での距離計算の為の処理時間の
短縮化が図れる効果がある。
に変化する点においてだけ、上記距離計算をするように
したものであるので、該距離計算を行う際の点列の数が
少なくなり、折線生成部での距離計算の為の処理時間の
短縮化が図れる効果がある。
第１図は本発明のベクトル生成方式の原理ブロック図。
第２図は本発明のチェインコード変化点抽出部の処理を
説明する図。 第３図は本発明の距離極大・極小点抽出部の処理を説明
する図。 第４図は折線生成部での距離最大の点を求める処理を説
明する図。 第５図は従来のベクトル生成方式を説明する図。 である。 図面において、 １０は細線化部。 １１はチェインコード変化点抽出部。 １２は距離極大・極小点抽出部。 １３は折線生成部、１４は点列抽出部。 各表中の数字は、抽出した点列の座標、又はチェインコ
ード。 °÷゛、゛−′ はチェインコードに対応させた符号。 °■′ は各点列と９画像データの両端とを結ぶ線分と
の距離で、’Ｈｍａｘ”はその最大値。 をそれぞれ示す。 ＝１３＝ 頓 り九 回 ｐへ ぃ、 − ンく （工 ８ 沿
説明する図。 第３図は本発明の距離極大・極小点抽出部の処理を説明
する図。 第４図は折線生成部での距離最大の点を求める処理を説
明する図。 第５図は従来のベクトル生成方式を説明する図。 である。 図面において、 １０は細線化部。 １１はチェインコード変化点抽出部。 １２は距離極大・極小点抽出部。 １３は折線生成部、１４は点列抽出部。 各表中の数字は、抽出した点列の座標、又はチェインコ
ード。 °÷゛、゛−′ はチェインコードに対応させた符号。 °■′ は各点列と９画像データの両端とを結ぶ線分と
の距離で、’Ｈｍａｘ”はその最大値。 をそれぞれ示す。 ＝１３＝ 頓 り九 回 ｐへ ぃ、 − ンく （工 ８ 沿
Claims (1)
- 【特許請求の範囲】 画像を細線化し、分岐点、端点に挟まれた点列を抽出し
て、両端を結ぶ線分との距離が最大になる点列内の点を
求めて、画像を折線近似するベクトル生成方式であって
、 線幅１の画像データを作成する細線化部（１０）と、分
岐点、端点間の点列に傾斜角コード（チェインコード）
を与え、該チェインコードが変化する点を抽出するチェ
インコード変化点抽出部（１１）と、チェインコード変
化点の中から、更に、両端を結ぶ線分との距離が極大、
或いは極小になる点だけを選択する距離極大・極小点抽
出部（１２）と、距離極大・極小点に対して距離が最大
になる点を求めて、その点で屈曲するベクトルを生成す
る折線生成部（１３）と、 を備えてベクトルを生成することを特徴とするベクトル
生成方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP21771686A JPS6373381A (ja) | 1986-09-16 | 1986-09-16 | ベクトル生成方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP21771686A JPS6373381A (ja) | 1986-09-16 | 1986-09-16 | ベクトル生成方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6373381A true JPS6373381A (ja) | 1988-04-02 |
| JPH0535911B2 JPH0535911B2 (ja) | 1993-05-27 |
Family
ID=16708618
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP21771686A Granted JPS6373381A (ja) | 1986-09-16 | 1986-09-16 | ベクトル生成方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6373381A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02148184A (ja) * | 1988-11-29 | 1990-06-07 | Nec Corp | 連続線の高速図形表示方式 |
-
1986
- 1986-09-16 JP JP21771686A patent/JPS6373381A/ja active Granted
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02148184A (ja) * | 1988-11-29 | 1990-06-07 | Nec Corp | 連続線の高速図形表示方式 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0535911B2 (ja) | 1993-05-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Smith | Computer processing of line images: A survey | |
| JP4300098B2 (ja) | オブジェクト識別方法とその装置、プログラム及び記録媒体 | |
| US8340433B2 (en) | Image processing apparatus, electronic medium, and image processing method | |
| US4853885A (en) | Method of compressing character or pictorial image data using curve approximation | |
| JPS6373381A (ja) | ベクトル生成方法 | |
| US5398293A (en) | System for editing image data | |
| JP3172498B2 (ja) | イメージ認識用特徴値抽出方法、およびその装置、イメージ解析プログラムを格納する記憶媒体 | |
| JP5375577B2 (ja) | 字形要素判定装置及び字形要素判定方法 | |
| Chang et al. | Skeletonization of binary digital patterns using a fast Euclidean distance transformation | |
| JP3113769B2 (ja) | 文字認識装置 | |
| JP2910344B2 (ja) | 画像処理方法 | |
| Mikheev et al. | High-quality polygonal contour approximation based on relaxation | |
| Shi | Two image-template operations for binary image processing | |
| JPH0754548B2 (ja) | 画像のベクトル化方法 | |
| JP3446794B2 (ja) | 文字認識における多角形近似法および文字認識装置 | |
| JPH0695644A (ja) | 文字パターンの直線認識方式 | |
| JP4394692B2 (ja) | 図形読み取り装置及び方法並びにそのプログラム | |
| JPS63241677A (ja) | 光学式文字読取装置 | |
| JPH01263883A (ja) | 線図形ベクトル化装置 | |
| JP2853167B2 (ja) | パターン認識用辞書作成装置 | |
| Lau et al. | EDT based tracing maximum thinning algorithm on grey scale images | |
| JP4413904B2 (ja) | パターン認識装置、パターン認識方法およびパターン認識プログラム | |
| JP2981011B2 (ja) | パターン認識装置 | |
| JP2001060250A (ja) | 文字認識方法および装置 | |
| JPH02176982A (ja) | 図形特徴抽出方法 |