JPH08305861A

JPH08305861A - 輪郭ベクトル生成方法

Info

Publication number: JPH08305861A
Application number: JP7105111A
Authority: JP
Inventors: Koji Fukutomi; 耕司福富; Hironori Nakajima; 廣則中島; Yoshihiro Tsukamoto; 好広塚本
Original assignee: Meidensha Corp; Meidensha Electric Manufacturing Co Ltd
Current assignee: Meidensha Corp; Meidensha Electric Manufacturing Co Ltd
Priority date: 1995-04-28
Filing date: 1995-04-28
Publication date: 1996-11-22

Abstract

(57)【要約】【目的】輪郭ベクトル生成処理を短時間でできるよう
にするとともに、構成の簡素化を図ることができるよう
にした。【構成】文字や図形等の対象物を、イメージスキャナ
等を用いて図面入力装置に黒と白の２値画像データとし
て入力し、この２値画像データを、ステップＳ１でラン
レングスとして取得する。次に、ステップＳ２で全ての
ランレングスの始点と終点に輪郭点を生成させる。生成
された輪郭点を次のステップＳ３でつなぎ合わせて、初
期輪郭ベクトルを生成する。その後、初期輪郭ベクトル
から同一線上の輪郭点を削除する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、図面入力装置におけ
る画像データから輪郭ベクトルを生成する方法に関す
る。

【０００２】

【従来の技術】図面入力装置により文字や図形等の対象
物パターンを処理する場合、まず、書類や図面等の対象
物を、イメージスキャナ等の入力装置で操作して黒と白
の２値画像データ（入力パターン）に変換し、この２値
画像データから対象物の輪郭画素を抽出し、情報圧縮処
理や対象物の認識処理を行っている。このうち、２値画
像データから対象物の輪郭画素を抽出するための従来方
式は、図７に示すような処理動作を行う。この処理の流
れを次に示す。

【０００３】Ａ．まず、２値画像データをすべて、専用
画像メモリＭに記憶し、Ｂ．次に、このメモリＭから検出対象となるＴの輪郭の
始点となる点、例えば、点Ｐ₁を探し、Ｃ．この点Ｐ₁ に隣接する点を順次追跡抽出して対象物
Ｔの輪郭画素を抽出する。

【０００４】このように、上記の輪郭画素抽出方式にお
いては、１画面分の２値画像データを記憶するための専
用メモリを必要とする。これは、入力する書類や図面の
サイズが大きくなればなるほど、また、高解像度にする
ほどメモリが大容量になる欠点を有する。ハードウェア
構成の点からいえば、画像メモリは入力画像の縦横サイ
ズに比例して大きくなるため、場合によってはメモリボ
ードの追加を考慮した構成が必要となる。例えば、「Ａ
０」サイズを対象とする画像メモリは、「Ａ４」サイズ
の画像メモリに比べて、１６倍もの容量を必要としてお
り、「Ａ４」サイズのメモリボードが１枚で構成される
ときでも「Ａ０」サイズは１６枚も必要である。

【０００５】次に、処理時間にも大きな影響がある上記
の方式では、画像メモリに１画面分が記憶されるまでの
待ち時間が必要であり、また、輪郭を抽出するために
は、逐次追跡をソフトウェアで行う必要があり、これら
も対象の画像のサイズや解像度に比例して、処理時間に
影響を与えることになる。

【０００６】

【発明が解決しようとする課題】上述の従来方式の問題
を解決するために、輪郭ベクトルを生成する際、輪郭コ
マンドという中間データを生成する方法が開発された。
次に、この方法の概略を述べる。

【０００７】図８は上記中間データ生成方法の構成を示
す図であり、３１は輪郭抽出部で、この輪郭抽出部３１
は、対象物をラスタスキャンして得られた黒白に対応す
る２値化画素データを取り込んで、縦横２画素×２画素
の画素データをスキャンラインに沿って順次に取り出
し、この画素データに基づいて輪郭検出用のコマンド列
を作成して次段の輪郭解析部３２に出力する。輪郭解析
部３２は前記コマンド列に基づいてテーブル格納部３３
内の輪郭要素テーブル、輪郭管理テーブル及び輪郭接続
テーブルの記載を更新する。また、輪郭解析部３２は輪
郭要素テーブルと輪郭管理テーブルを使用して１輪郭画
素系列を構成する各点のうち始点からみて極大となる点
を抽出する巨視的処理部３４と、この処理で抽出された
連続する２点の間にある最大距離となる点を設定した閾
値との関係からいくつか抽出する微視的処理部３５と、
この処理部３５により抽出された点の輪郭ベクトルを輪
郭ベクトル系列テーブル３６に記載し、この輪郭ベクト
ルのうち短い（ショート）ベクトルをショートベクトル
除去部３７で除去し、その記載を更新する。

【０００８】ここで輪郭要素とは互いに隣接した２個の
黒画素を結ぶベクトルに相当するものであり、これを結
合することによって輪郭が構成される。そして輪郭要素
テーブルとは、輪郭要素とこれら輪郭要素群よりなる輪
郭とに対して各々固有の符号を付すと共に、輪郭要素毎
に、その座標及び方向と輪郭要素が所属する輪郭の符号
と輪郭要素の前後に夫々接続されている他の輪郭要素の
符号とを記載するためのものである。また輪郭管理テー
ブルとは、輪郭毎に先端及び終端に位置する輪郭要素の
符号を記載するためのものであり、輪郭接続テーブルと
は、ラスタスキャン方向に並ぶ座標とその座標に前端ま
たは後端が存在する末接続の輪郭要素の符号とその輪郭
要素の末接続端の前後端の区別とを対応させて記載する
ためのものである。また、輪郭ベクトルテーブルとは、
輪郭ベクトル系列毎に始点座標の符号を記載するための
ものである。

【０００９】上記のように輪郭コマンドという中間デー
タを生成するためには、図８に示すような処理装置を必
要とするために、その装置とのデータ通信時間を考慮す
ると、輪郭ベクトル生成処理にはまだ時間がかかってし
まうとともに、構成においても、上記のような処理装置
を必要とするために簡素化できない問題がある。

【００１０】この発明は上記の事情に鑑みてなされたも
ので、輪郭ベクトル生成処理を短時間でできるようにす
るとともに、構成の簡素化を図ることができるようにし
た輪郭ベクトル生成方法を提供することを目的とする。

【００１１】

【課題を解決するための手段および作用】この発明は、
上記の目的を達成するために、この発明の第１発明は、
文字や図形等の対象物を、イメージスキャナ等を用いて
図面入力装置に黒と白の２値画像データとして入力した
後、この２値画像データをランレングスとして取得し、
その後、取得したランレングスから全てのランレングス
の始点と終点に輪郭点を生成させ、生成された輪郭点を
次につなぎ合わせて、初期輪郭ベクトルを生成した後、
同一線上の輪郭点を削除処理した後、それらのベクトル
を１本に統合するようにしたことを特徴とするものであ
る。

【００１２】第２発明は、初期輪郭ベクトル生成後、長
さ、方向が等しいベクトルあるいは平行なベクトルで接
続されている輪郭座標点の両方あるいはどちらか一方を
削除するようにしたことを特徴とするものである。

【００１３】

【実施例】以下この発明の一実施例を図面に基づいて説
明する。図１はこの発明の一実施例を示すフローチャー
トで、図１において、まず、文字や図形等の対象物を、
イメージスキャナ等を用いて図面入力装置に黒と白の２
値画像データとして入力し、この２値画像データを、ス
テップＳ１でランレングスとして取得する。次に、ステ
ップＳ２で全てのランレングスの始点と終点に輪郭点を
生成させる。生成された輪郭点を次のステップＳ３でつ
なぎ合わせて、初期輪郭ベクトルを生成する。ここ
で、ステップＳ３における初期輪郭ベクトルを生成する
方法について述べる。図２において、一点鎖線で示す画
像データからランレングスＬを得る。なお、図２におい
て、主走査方向をｙ方向、副走査方向をｘ方向と称す
る。まず、あるランレングスＬに注目する。そのランレ
ングスＬの始点座標を（Ｋ，ｌs）、終点座標を（Ｋ，
ｌe）とする。まず、始点座標（Ｋ，ｌs）のつなぎ合わ
せについて述べるに、副走査方向ｘ＝Ｋ−１のランレン
グス群に注目する。それらのランレングスと、Ｌとの間
の関係を以下の５通りに分類し、つなぎ合わせを行う。

【００１４】図３（ａ）はＬと重なるランレングスがな
い場合の例で、この場合には始点座標（Ｋ，ｌs）から
終点座標（Ｋ，ｌe）と云うようにランレングスＬでつ
なぎ合わせる。このときの条件式はｌe’＜（ｌs−１）
である。

【００１５】図３（ｂ）はランレングスＬと接触する場
合の例で、この場合には始点座標（Ｋ，ｌs）を（Ｋ−
１，ｌe’）とつなぎ合わせる。条件式はｌe’＝（ｌs
−１）である。

【００１６】図３（ｃ）は単純重なりの場合の例で、こ
の場合には、（Ｋ，ｌs）→（Ｋ，ｌs’）→（Ｋ−１，
ｌs’）のような過程を経て座標をつなぎ合わせる。条
件式はｌs＜ｌs’≦ｌeである。

【００１７】図３（ｄ）は単純重なりの別の場合の例
で、この場合には、（Ｋ，ｌs）→（Ｋ−１，ｌs）→
（Ｋ−１，ｌs’）のような過程を経て座標をつなぎ合
わせる。条件式はｌe’≧（ｌs＋１）とｌs’≦ｌsであ
る。

【００１８】図３（ｅ）は複雑重なりの場合の例で、こ
の場合には、（Ｋ，ｌs）→（Ｋ−１，ｌs）→（Ｋ−
１，ｌe”）→（Ｋ，ｌe”）のような過程を経て座標を
つなぎ合わせる。条件式はｌe’≧ｌsとｌs’≦（ｌe”
＋１）である。

【００１９】次に終点座標（Ｋ，ｌe）のつなぎ合わせ
るについて述べるに、ｘ＝Ｋ＋１のランレングス群に注
目する。重なり方を上記と同様５通りに分類してつなぎ
合わせる。

【００２０】以上の処理を図２に示す全てのランレング
スに対して施すことにより輪郭ベクトルはループ状にな
る。この輪郭ベクトルに対してさらに次の処理を行う。
この処理を図４により述べる。

【００２１】図４において、ある２本の連続した輪郭ベ
クトルＶ₁（ｘ₁，ｙ₁）、（ｘ₂，ｙ₂）とＶ₂（ｘ₂，
ｙ₂）、（ｘ₃，ｙ₃）に関して、Ｖ₂がＶ₁に対して左に
９０°折曲した状態で、共に垂直又は水平であるとき、
つまり次式のとき、

【００２２】

【数１】

【００２３】（ｘ₂，ｙ₂）から距離１の所に輪郭点（ｘ
₄，ｙ₄），（ｘ₅，ｙ₅）を発生させ、そのつながりを
（ｘ₁，ｙ₁）→（ｘ₄，ｙ₄）→（ｘ₅，ｙ₅）→（ｘ₃，
ｙ₃）とする。このような処理により８連結相当の初期
輪郭ベクトルループ（図２に示す実線）が生成される。

【００２４】上記のようにしてステップＳ３の初期輪郭
ベクトル生成処理が終了したならステップＳ４の処理を
行う。この処理は同一直線上の輪郭ベクトルを削除する
ステップで、前記処理で連続した輪郭ベクトルが同一直
線上に並ぶことがあるので、それらのベクトルを１本に
統合するものである。なお、上記処理はコンピュータに
よって行われる。

【００２５】次に前記実施例のステップＳ４における処
理時間の短縮を図るために、ステップＳ４を行う前に図
５および図６のような輪郭座標点の場合には輪郭座標点
の一部を削除するようにした実施例である。まず、図５
に示すような輪郭座標点で、線分│ＢＣ│＝１、かつ長
さ、方向とも等しい線分ＡＢ＝ＣＤのときには、座標点
Ｂ，Ｃはともに削除する。

【００２６】また、図６に示すような輪郭座標点で、線
分│ＢＣ│＝１、かつ線分方向ＡＢとＣＤが平行のとき
には、次式により座標点ＢとＣを別々に削除する。

【００２７】

【数２】

【００２８】すなわち、上記（１）式のときには座標点
Ｃを削除し、上記（２）式のときには座標点Ｂを削除す
る。

【００２９】上記のようにして前記実施例におけるステ
ップＳ４の処理を行う前に輪郭座標点の一部を削除すれ
ば、ステップＳ４における処理をコンピュータにより行
う場合の処理時間を短縮できる。

【００３０】

【発明の効果】以上述べたように、この発明によれば、
コンピュータによる輪郭ベクトル生成処理を短時間でか
つ専用のハードウェアを使用することなく実行すること
ができる利点がある。

【図面の簡単な説明】

【図１】この発明の実施例を示すフローチャート。

【図２】上記実施例を説明するための輪郭ベクトルとラ
ンレングスを示す説明図。

【図３】図３（ａ）〜（ｅ）は実施例の動作説明図。

【図４】実施例の動作説明図。

【図５】この発明の異なる実施例の説明図。

【図６】この発明の異なる実施例の説明図。

【図７】従来の輪郭画素抽出態様図。

【図８】従来例の構成図。

【符号の説明】

Ｓ１…ランレングス取得ステップＳ２…輪郭点生成ステップＳ３…初期輪郭ベクトル生成ステップＳ４…同一線上輪郭点削除ステップ

Claims

【特許請求の範囲】

【請求項１】文字や図形等の対象物を、イメージスキ
ャナ等を用いて図面入力装置に黒と白の２値画像データ
として入力した後、この２値画像データをランレングス
として取得し、その後、取得したランレングスから全て
のランレングスの始点と終点に輪郭点を生成させ、生成
された輪郭点を次につなぎ合わせて、初期輪郭ベクトル
を生成した後、同一線上の輪郭点を削除処理した後、そ
れらのベクトルを１本に統合するようにしたことを特徴
とする輪郭ベクトル生成方法。
【請求項２】初期輪郭ベクトル生成後、長さ、方向が
等しいベクトルあるいは平行なベクトルで接続されてい
る輪郭座標点の両方あるいはどちらか一方を削除するよ
うにしたことを特徴とする請求項１記載の輪郭ベクトル
生成方法。