JPH0338624B2

JPH0338624B2 -

Info

Publication number: JPH0338624B2
Application number: JP15791885A
Authority: JP
Inventors: Katsuhiko Nishikawa; Toshio Matsura; Shigemi Osada
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1985-07-17
Filing date: 1985-07-17
Publication date: 1991-06-11
Also published as: JPS6219976A

Description

【発明の詳細な説明】〔概要〕パターンの輪郭線を折線近似することにより情
報量を圧縮する方式において、２点間に直線を発
生する直線発生部と、原パターンの輪郭から抽出
される２点間の直線とその間の輪郭線とが一致す
るか否かを検出して輪郭線の屈曲点情報を抽出す
る輪郭線切出部と、抽出された屈曲点が直角かつ
所定の位置に存在するか否かに基づいて屈曲点の
位置を補正する屈曲点位置補正部とを備え、この
補正された屈曲点情報を用いて前記輪郭線情報を
表現している。

〔産業上の利用分野〕

本発明は、例えば文字形の如きパターン情報の
輪郭線情報から屈曲点情報を抽出した後、この屈
曲点情報のうち、相互に直角かつ所定の位置に存
在するか否かに基づいて屈曲点の位置を補正して
原パターンの直角部分での屈曲点の出過ぎを防止
して原パターン情報を圧縮するよう構成したパタ
ーン情報量圧縮方式に関するものである。

〔従来の技術〕

従来、パターン情報を圧縮する方式として例え
ば昭和60年３月12日特許出願（発明の名称「パタ
ーン情報量圧縮方式」）に記載されているように、
パターンの輪郭情報の屈曲点を算出し、この屈曲
点を用いて原パターンを表現することにより、情
報量を圧縮することが行われている。以下第１０
図図示従来のパターン情報量圧縮方式の原理説明
を用いて説明する。

第１０図ａにおいて、原パターンの輪郭情報で
あるパターンP_i（ｉ＝１〜12）を求めた後、例え
ばパターンP₁₂をスタート点とし終点をパターン
P₁と定めると共に、パターンP₁₂（スタート点）を
屈曲点として抽出する。そして、終点のパターン
P₁とスタート点のパターンP₁₂とを結ぶ直線点列
Ｌ（P₁，P₁₂）を求める。次に、終点のパターン
P₁から左廻り方向に、つまりスタート点方向に
この輪郭情報であるパターンP_iを順次追跡した追
跡輪郭座標列Ｔ（P₁，P₂……P₁₂）を得る。この
場合、直線点列Ｌ（P₁，P₁₂）と、追跡輪郭座標列
Ｔ（P₁，P₂，……P₁₂）とが一致しないので、パ
ターンP₁の次のパターンP₂と、スタート点のパ
ターンP₁₂との直線点列Ｌ（P₂，P₁，P₁₂）を求め
ると共に、パターンP₂から左廻り方向に輪郭情
報であるP_iを順次追跡して追跡輪郭座標列Ｔ（P₂，
P₃……P₁₂）を得る。この場合も両者が一致しな
いので、以下同様な処理を行う。そして、パター
ンP₉では、直線点列Ｌ（P₉ないしP₁₂）と、追跡
輪郭座標列Ｔ（P₉ないしP₁₂）とが一致するので、
このパターンP₉が屈曲点として検出される（第
１０図ｂ図中斜線を施したP₉）。

次に、第１０図ｃに示すように、屈曲点として
検出されたパターンP₉をスタート点として同様
の処理を行うと、今度はパターンP₆が屈曲点と
して検出される。そして、パターンP₆をスター
ト点として同様な処理を行えばパターンP₃が屈
曲点として検出される。ここで、直線点列Ｌ
（P₃，P₁₂）と右廻りの追跡輪郭座標列Ｔ（P₃，
P₂，P₁，P₁₂）とが一致するので抽出処理を終了
する。以上のようにして算出した屈曲点（P₁₂，
P₉，P₆，P₃）を用いて原パターンの輪郭を圧縮
した態様で表現することができる。

同様に、第１１図ａに示す原パターンの輪郭線
（図中“白丸”を用いて表す線）について屈曲点
を算出すると、第１１図ｂ図中に“黒丸”を用い
て示すようになる。

〔発明が解決しようとする問題点〕

従来のパターン情報量圧縮方式では、例えば第
１１図ｂ図中“黒丸”を用いて示す屈曲点情報を
用いて原パターンを表現して圧縮していたため、
第２図ａを用いて示す屈曲点では、直角部分に複
数の屈曲点が存在してしまい、充分に圧縮し得な
いという問題点があつた。

〔問題点を解決するための手段〕

本発明は、前記問題点を解決するために、相互
に直角の態様かつ所定の位置関係で抽出された屈
曲点の位置を補正して屈曲点の数を削除する構成
を採用することにより、原パターンを表現する屈
曲点の数を少なくして圧縮を行つている。

第１図は本発明の原理的構成を示す。図中、１
は磁気デイスク装置９内に設けた原パターン保持
部、３は直線発生部、４は輪郭線切出部、７は屈
曲点位置補正部、８は磁気デイスク装置９内に設
けた圧縮データ保持部、９は磁気デイスク装置を
表す。

第１図において、直線発生部３は、原パターン
保持部１に格納されている原パターンを読み出
し、この原パターンの輪郭線に対応するドツト情
報のうち、任意の２点を結ぶ直線を発生させるも
のである。

輪郭線切出部４は、直線発生部３によつてパタ
ーンの輪郭線の所定の２点間を結ぶ態様で生成し
た直線と、この２点間の輪郭線との両者が一致し
た当該輪郭線を切り出して屈曲点を抽出するもの
である。

屈曲点位置補正部７は、輪郭線切出部４によつ
て抽出された屈曲点が直角かつ所定の位置に存在
するか否かを判別し、この判別結果に基づいて屈
曲点の位置を補正するるものである。この屈曲点
の位置が補正され、屈曲点の数が削減された屈曲
点情報は磁気デイスク装置９内に設けた圧縮デー
タ保持部８に格納される。

〔作用〕

第２図に示す本発明の原理説明を用いて第１図
に示す構成の動作および作用を説明する。

第２図ａ図中P₁ないしP₄は位置補正前の屈曲
点、第２図ｂ図中P₁，P₁₂，P₄は位置補正後の屈
曲点を表す。

第２図ａにおいて、図中原パターンの輪郭線に
対応する“丸印”を用いて示すパターンのうち、
屈曲点は“黒丸”によつて表されている。この
“黒丸”は、輪郭線切出部４によつて抽出された
ものである。

そして、以下の処理が屈曲点位置補正部７によ
つて行われる。即ち、連続する屈曲点P₁，P₂，
P₃およびP₄に対し、屈曲点P₂を１ドツト分屈曲
点P₁から屈曲点P₂の方向に移動させた点Ｎと、
屈曲点P₃を１ドツト分屈曲点P₄から屈曲点P₃の
方向に移動させた点とが一致し、かつその点に
“丸印”で示される輪郭点が存在する場合、屈曲
点P₂の座標を点Ｎの座標に置き換え（第２図ｂ
図中屈曲点P₁₂）、屈曲点P₃を削除する。これによ
り、４個の屈曲点（P₁，P₂，P₃，P₄）を用いて
表現していたパターンが、３個の屈曲点（P₁，
P₁₂，P₄）を用いて表現することが可能になる。

以上説明したように、屈曲点情報を用いてパタ
ーンの輪郭情報を表現すると共に、屈曲点が相互
に直角かつ所定の位置関係にある場合に当該屈曲
点を統合して屈曲点の数を削減する構成を採用し
ているため、圧縮を充分に行うことが可能にな
り、かつパターンの拡大、縮小、圧縮を容易に行
うことができる。

〔実施例〕

本発明の１実施例を第３図〜第９図にもとづき
説明する。

(a) 本発明の１実施例構成第３図は本発明の１実施例構成図、第４図はそ
の直線発生部の直線発生状態説明図、第５図は直
線発生部の動作フローチヤートを示す。

第３図において、図中、１は原パターン保持
部、２は追跡部、３は直線発生部、４は輪郭線切
出部、５は比較部、６は屈曲点生成部、７は屈曲
点位置補正部、８は圧縮データ保持部を表す。

原パターン保持部１は、TVカメラのCCDの如
き適宜入力手段から伝達された、例えば文字のオ
リジナル・パターン（原パターン）を記憶保持す
るものである。

追跡部２は、原パターンの輪郭部分を追跡して
輪郭線上の座標列点を得るものである。このた
め、例えばパターンを３×３のウインドウで走査
してパターンの輪郭線上の一点を捉え、そこから
輪郭線を８方向に追跡可能にしてこれを追跡し、
輪郭上の点の座標列を得る。輪郭線の始点をＳ、
終点をＥとすれば、例えば第６図ａにおいて、白
丸で示す如き輪郭線を得ることになる。なお第６
図ａにおける＊印は輪郭線内部のパターンであ
る。

直線発生部３は、与えられた２点間に直線を発
生する手段であつて、周知のものが使用できる。
一例としてDDA（Digital Differential Analy
zer：デイジタル微分解析機）を使用する例につ
いて、第４図および第５図を用いて説明する。第
４図に示す如く、P₁（X₁，Y₁）とP₂（X₂，Y₂）と
の間に直線を引くとき、第１ステツプ（第５図図
示）として、始点を（X₁，Y₁）にプロツトし、
この直線の角度をφとするとき、係数G₁＝cosφ、
係数G₂＝sinφを求め、スタート点（Ｘ，Ｙ）の
座標をＸ＝X₁，Ｙ＝Y₁にセツトする。そして、
初期値としてＸ座標レジスタR₁，Ｙ座標レジス
タR₂に次のデータを記入する。

R₁＝X₁＋0.5 ……(1) R₂＝Y₁＋0.5 ……(2) 第２ステツプ（第５図図示）として、Ｘ座標レ
ジスタR₁の値に前記cosφを加え、Ｙ座標レジス
タR₂の値に前記sinφを加える。これは、第４図
において、スタート点P₁よりP₂の方に単位長１
だけ直線を引いたときのＸ座標およびＹ座標の値
を示す。ところで、メモリにセツトされるデータ
は、通常整数単位であるので、前記加算後の値の
整数部分I₁，I₂だけを取り出す。なお第５図の第
２ステツプでint（R₁）は、レジスタR₁より整数
部分のみを取り出すことを示し、int（R₂）はレジ
スタR₂より整数部分のみを取り出すことを示す。
ここでintは、少数点以下を切り捨てる関数を示
す。

第３ステツプ（第５図図示）として、前記第２
ステツプで得た整数I₁が第１ステツプのＸと異な
るか、または整数I₂が第１ステツプのＹと異なる
ときには、Ｘ＝I₁，Ｙ＝I₂としてこれらを（Ｘ，
Ｙ）にプロツトする。このようなことをＸ＝X₂，
Ｙ＝Y₂になるまで繰り返す。このようにして、
第４図に◎印で示す如きP₁，P₂間の直線のデー
タが得られる。

輪郭線切出部４は、輪郭線を適宜切り出してそ
の間の座標を出力するものである。

比較部５は、直線発生部３により発生した直線
と、輪郭線切出部４の切り出した輪郭線とが一致
するか否かを比較するものである。

屈曲点生成部６は、後述する終了条件チエツク
信号を発生し、屈曲点生成処理をさらに続けるか
否かを判断するものである。

屈曲点位置補正部７は、第２図図示原理説明図
を用いて説明した如く、屈曲点生成部６によつて
生成された屈曲点の数を削減するものである。

圧縮データ保持部８は、補正部７によつて相互
に直角な屈曲点の削除が実施された後の輪郭線の
屈曲点を保持するものである。

(b) 本発明の動作本発明は２点間の直線の発生、輪郭線から
の屈曲点抽出、および屈曲点の位置補正という
３つの技術を主にしている。

イこのうちについては、前記(a)の直線発生部
３について第４図および第５図にもとづき説明し
たので省略し、およびについて順次説明し、
その後に全体の動作について説明する。

第７図は屈曲点検出動作フローチヤート、第８
図は屈曲点の抽出例、第９図は屈曲点の位置補正
列を示す。

の輪郭線から屈曲点抽出は次の第１ステツプ
〜第５ステツプの手順によりパターンの輪郭線か
ら屈曲点を抽出する。

第１ステツプでは、例えば第６図ａに示す如
く、パターンの輪郭線上の一点を捉え、そこから
輪郭線を８連結で追跡し、白丸印で示す如き輪郭
上の点の座標列を得る。輪郭線の始点をＳ、終点
をＥとする。

第２ステツプでは、まず始点ＳをP₁とし、こ
のP₁の無条件に屈曲点として抽出する。

第３ステツプでは、点Ｐを終点Ｅから始点Ｓに
向かつて輪郭線上を移動させながら点Ｐと点Ｓと
の間にの方法で直線発生部３により直線を発生
し、その区間の輪郭線を輪郭線切出部４で求め、
比較部５によりこの直線と輪郭線との差を求め
る。例えば、点Ｐが第６図ｂに示す星印の位置に
あるとき、この星印と始点Ｓ（Ｘ印）との間の直
線を求めると、（星印、◎，◎，◎，Ｘ印）の如
き直線が得られ、また輪郭線として星印から左廻
り方向にＸ印までの輪郭線が得られるが、この両
者は一致せず、その差は零ではない。そのため、
次に、点Ｐは星印位置より一個Ｓ側寄りに移動し
たP₁の位置で同様に直線を発生し、また輪郭線
を切り出して一致状態をチエツクする。このよう
なことを順次P₁，P₂と始点Ｓ方向に移動させて
行う。そして、第６図ｂのP_Vで行うとき、その
P_Vから始点Ｓに向かう直線とその区間の輪郭線
とが一致してその差が零になるので、この点P_V
を屈曲点Ｖとして抽出する。

第４ステツプでは、屈曲点を全部抽出したか否
かをチエツクするものである。このために、前記
第３ステツプで得た屈曲点Ｖと終点Ｅとを経由し
て始点Ｓまでの区間の輪郭線（この例では屈曲点
Ｖから右廻り方向の輪郭線）と、屈曲点Ｖと始点
Ｓの直線との差が零か否かをチエツクする。この
チエツクは、第３図の屈曲点生成部６からの指示
により、直線発生部３が直線を発生させ、輪郭線
切出部４が輪郭線を切り出し、比較部５がその一
致，不一致をチエツクすることにより行われる。
この差が後述するように零ならば、屈曲点抽出処
理は終了することになるが、第６図ｂにおいて、
屈曲点P_Vにおける前記チエツクでは不一致であ
るので、次の屈曲点を検出するために第５ステツ
プに続く。

第５ステツプでは、終点Ｅから左廻りにスター
トさせて、第３ステツプと同様に、屈曲点Ｖへの
直線と、屈曲点Ｖまでの輪郭線とが一致する点を
検出し、これにより、次の屈曲点V₁が検出でき
る。そして、前記第４ステツプの終了条件をチエ
ツクするが、V₁でも終了条件が満足されてない
ので再びＥをスタート点としてV₁に対する直線
および輪郭線をを比較する。これにより、次に屈
曲点V₂が検出できる。ここで終了条件のチエツ
クが行われ、終了条件が満たされていなければ、
Ｅよりこの屈曲点V₂までの直線および輪郭線を
順次比較する。このような処理を順次行うことに
より、第６図ｄに黒丸で示す如き各屈曲点が検出
される。

第７図は、前記屈曲点検出のための一般的な動
作を説明するフローチヤートである。ここでは、
追跡した輪郭線の座標点列を（P₁，P₂…P_o）と
し、輪郭線上のｉ番目の点Piと、ｊ番目の点Pjと
の間に前記の手法（ａの直線発生部３における
説明）で発生した点列（N₁，N₂…N_L）と、（P_i
…P_j）とを比較して、両者が等しい時はYES、
等しくないときはNOを返す処理SAME（ｉ，ｊ）
が定義されているものとする。

尚、屈曲点の位置補正については、既に第２
図を用いて説明した如く、第２図ａ図中パターン
P₁ないしP₄中のパターンP₂を１ドツト分P₁から
P₂の方向に移動させた点Ｎと、パターンP₃を１
ドツト分P₄からP₃の方向に移動させた点と一致
し、かつその位置に輪郭上の点が存在する場合、
パターンP₂の座標値を点Ｎの座標値に置き換え
ると共に、パターンP₃を削除し、第２図ｂの如
きパターンおよび屈曲点P₁，P₁₂，P₄を得る。こ
れにより、屈曲点の位置補正前の４個の屈曲点
P₁，P₂，P₃…P₄が、３個の屈曲点P₁，P₁₂，P₄に
削減されたこととなり、圧縮が実行されたことと
なる。

ロ次に第３図を用いて本発明の全体動作を説明
する。

図示省略したTVカメラの如き画像入力部よ
り入力された文字パターンが保持部１に保持さ
れる。このパターンは追跡部２により、その輪
郭部分が追跡され、第６図ａの白丸で示す如き
輪郭線上の座標列点が得られる。このとき得ら
れた輪郭線の始点をＳ、終点をＥとする。これ
らのデータは、直線発生部３および輪郭線切出
部４にて保持される。

まず屈曲点生成部６は無条件に始点Ｓを屈曲
点として抽出する。

終点Ｅと始点Ｓとの間の直線を直線発生部３
により発生させ、その直線の座標を比較部５に
送出する。また、輪郭線切出部４は終点Ｅから
左廻りで始点Ｓまでの輪郭線の座標（Ｅ，P₁，
P₂…Ｓ）を比較部５に送出する。比較部５は
この直線と輪郭線座標とを比較して不一致のと
き、不一致信号を屈曲点生成部６に出力する。
屈曲点生成部６は、これにより終点Ｅの次の輪
郭線上の点P₁（始点Ｓと反対側の点）に対して
同様の処理を行うように直線発生部３と輪郭線
切出部４とに指令する。これにより、直線発生
部３はP₁とＳとの間に直線を発生させ、また
輪郭線切出部４は（P₁，P₂…Ｓ）を送出し、
比較部５で比較で行われる。このときも不一致
なので、次に点P₂からＳに向かう直線と輪郭
線との比較を行う。このようなことが順次行わ
れ、点P_Vにおいて比較部５から一致信号が出
力される。

これにより、屈曲点生成部６は、今度は輪郭
線切出部４に対して点P_Vから右廻り終点Ｅを
経由して始点Ｓまでの輪郭線を出力させ、また
直線発生部３にはP_VとＳとの直線を出力させ、
比較する。比較部５から不一致信号が送出され
るので、屈曲点生成部６はその終了条件が満た
されていないことを認識し、今度は前記イの第
５ステツプに関する説明と同様な制御が行われ
る。このようにして、各屈曲点が順次検出され
る。そして、第６図ｄに黒丸として示す各屈曲
点が屈曲点位置補正部７に通知される。

輪郭線の屈曲点情報の通知を受けた屈曲点位
置補正部７は、隣接する屈曲点が相互に直角か
つ所定の位置関係にある場合には、第２図を用
いて説明した如く、一方の屈曲点の座標を置き
換えると共に、他の屈曲点を削除する。そし
て、この位置補正を行つた各屈曲点情報が圧縮
データ保持部８に保持される。

このようにして、例えば第８図図中“黒四角”
を用いて示す位置が屈曲点として屈曲点生成部６
によつて抽出される。そして、更にこれら抽出し
た屈曲点のうち、屈曲点位置補正部７によつて位
置補正を行つたものを第９図に示す。図中“＊”
は屈曲点位置補正部７によつて屈曲点が位置補正
され、屈曲点の数が削減された位置を示す。この
ように、第９図に示す如く、屈曲点の位置補正を
実行した後の屈曲点情報を用いて原パターンを圧
縮して表現することができる。

〔発明の効果〕

以上説明したように、本発明によれば、原パタ
ーン情報を屈曲点情報を用いて表現すると共に、
当該屈曲点情報が相互に直角かつ所定の位置関係
にある場合に位置補正を実行して屈曲点の数を削
減する構成を採用しているため、屈曲点情報を用
いてきわめて圧縮した態様で原パターン情報を表
現することができる。しかも、屈曲点を座標情報
として持つため、拡大、縮小、回転等の各種変換
を容易に行うことができる。そのため、いままで
フル・ドツトを用いてパターンを記憶していた装
置に比較し、極めて小型かつ高性能化することが
できる。

【図面の簡単な説明】

第１図は本発明の原理的構成図、第２図は本発
明の原理説明図、第３図は本発明の１実施例構成
図、第４図は直線発生状態説明図、第５図は直線
発生部の動作フローチヤート、第６図は屈曲点検
出状態説明図、第７図は屈曲点検出動作フローチ
ヤート、第８図は屈曲点の抽出例、第９図は屈曲
点の位置補正例、第１０図は従来のパターン情報
量圧縮方式の原理説明図、第１１図は屈曲点の抽
出例を示す。図中、１は原パターン保持部、３は直線発生
部、４は輪郭線切出部、７は屈曲点位置補正部、
８は圧縮データ保持部、９は磁気デイスク装置を
表す。

Claims

【特許請求の範囲】１パターンの輪郭線を折線近似することにより
情報量を圧縮するパターン情報量圧縮方式におい
て、２点間に直線を発生する直線発生部３と、原パターンの輪郭から抽出される２点間の直線
と、その間の輪郭線とが一致するか否かを検出し
て輪郭線の屈曲点情報を抽出する輪郭線切出部４
と、この輪郭線切出部４によつて抽出された屈曲点
が直角かつ所定の位置に存在するか否かを判別
し、この判別結果に基づいて屈曲点の位置を補正
する屈曲点位置補正部７とを備え、この屈曲点位置補正部７によつて補正された屈
曲点情報を用いて前記輪郭線情報を表現するよう
構成したことを特徴とするパターン情報量圧縮方
式。