JPS6219976A - パタ−ン情報量圧縮方式 - Google Patents

Abstract

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

Description

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

〔産業上の利用分野〕

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

〔従来の技術〕

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

第１０図＜ａ）において、原パターンの輪郭情報である
パターンＰｒ　　（＋＝１〜１２）を求めた後９例えば
パターンｐ＋ｚをスタート点とし終点をパターンＰ１　
と定めると共に、パターンＰ１□（スタート点）を屈曲
点として抽出する。そして、終点のパターンＰ、とスタ
ート点のパターンＰ１□とを結ぶ直線点列Ｌ　（Ｐ、、
Ｐ、□）を求める。次に。

終点のパターンＰ、から左廻り方向に、つまりスタート
点方向にこの輪郭情報であるパターンＰ１を順次追跡し
た追跡輪郭座標列Ｔ　（Ｐ、、Ｐ、　　・・・・Ｐ＋ｚ
）を得る。この場合、直線点列Ｌ（ＰＬ、Ｐ＋２）と、
追跡輪郭座標列Ｔ　（Ｐ、　、　　Ｐｌ　　・・・・Ｐ
、２）とが一致しないので、パターンＰ１の次のパター
ンＰ２と、スタート点のパターンＰ１□との直線点列Ｌ
　（Ｐｚ　、　　Ｐ＋　、　　Ｐ＋ｚ）を求めると共に
、パターンＰ２から左廻り方向に輪郭情報であるＰｌを
順次追跡して追跡輪郭座標列Ｔ（Ｐｌ、Ｐｓ　・・・・
Ｐ、□）を得る。この場合も両者が一致しないので、以
下同様な処理を行う。そして、パターンＰ、では、直線
点列しくＰ、ないしＰ１□）と、追跡輪郭座標列Ｔ　（
Ｐ、ないしＰ、２）とが一致するので、このパターンＰ
、が屈曲点として検出される（第１０図（ｂ）図中斜線
を施したＰ、ｌ）。

次に、第１０図（Ｃ）に示すように、屈曲点として検出
されたパターンＰ９をスタート点として同様の処理を行
うと、今度はパターンＰ６が屈曲点として検出される。

そして、パターンＰ、をスタート点として同様な処理を
行えばパターンＰ３が屈曲点として検出される。ここで
、直線点列しくＰｓ、Ｐ＋ｚ）と右廻りの追跡輪郭座標
列Ｔ（Ｐ３＋　　Ｐｚ＋　　Ｐｌ、Ｐ＋ｚ）とが一致す
るので抽出処理を終了する。以上のようにして算出した
屈曲点（Ｐ、ｚ、　　Ｐｑ　、　　Ｐｂ　、　　Ｐｓ　
）を用いて原パターンの輪郭を圧縮した態様で表現する
ことができる。

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

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

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

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

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

第１図において、直線発生部３は、原パターン保持部１
に格納されている原パターンを読み出し。

この原パターンの輪郭線に対応するドツト情報のうち、
任意の２点を結ぶ直線を発生させるものである。

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

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

〔作用〕

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

第２図＋ａ＋図中Ｐ＋ないしＰ４は位置補正前の屈曲点
、第２図（ｂ）図中Ｐ＋　、Ｐｌｔ、Ｐａは位置補正後
の屈曲点を表す。

第２図（ａｌにおいて１図中原パターンの輪郭線に対応
する“丸印”を用いて示すパターンのうち。

屈曲点は“黒丸”によって表されている。この“黒丸”
は２輪郭線切出部４によって抽出されたものである。

そして、以下の処理が屈曲点位置補正部７によって行わ
れる。即ち、連続する屈曲点Ｐ、、Ｐ２゜Ｐ３およびＰ
４に対し、屈曲点Ｐ２を１ドツト分屈曲点Ｐ１から屈曲
点Ｐ２の方向に移動させた点Ｎと、屈曲点Ｐ、を１ド、
ト分屈曲点Ｐ４から屈曲点Ｐ３の方向に移動させた点と
が一致し、かつその点に“丸印”で示される輪郭点が存
在する場合、屈曲点Ｐ２の座標を点Ｎの座標に置き換え
（第２図（ｂ）図中屈曲点Ｐ１□）、屈曲点Ｐ３を削除
する。これにより、４個の屈曲点（Ｐ、、ｐｚ　。

Ｐ３．Ｐ４）を用いて表現していたパターンが。

３個の屈曲点（Ｐ７．Ｐｌｔ、Ｐ４　）を用いて表現す
ることが可能になる。

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

かつパターンの拡大、縮小、圧縮を容易に行うことがで
きる。

〔実施例〕

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

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

第３図において１図中、１は原パターン保持部。

２は追跡部、３は直線発生部、４は輪郭線切出部。

５は比較部、６は屈曲点生成部、７は屈曲点位置補正部
、８は圧縮データ保持部を表す。

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

追跡部２は、原パターンの輪郭部分を追跡して輪郭線上
の座標列点を得るものである。このため。

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

直線発生部３は、与えられた２点間に直線を発生する手
段であって１周知のものが使用できる。

−例としてＯＤ　Ａ　（Ｄｉｇｉｔａｌ　Ｄｉｆｆｅｒ
ｅｎｔｉａｌ　Ａｎａｌｙｚｅｒ　　：ディジタル微分
解析機）を使用する例について、第４図および第５図を
用いて説明する。第４図に示す如＜、Ｐ＋　　（Ｘ＋　
、　Ｙｌ　）とＰｚ　　（Ｘｚ、Ｙｚ）との間に直線を
引くとき、第１ステツプ（第５図図示）として、始点を
＜ｘ＋　、Ｙｌ　）にプロットし、この直線の角度をφ
とするとき１係数Ｇ１ｗｃｏｓφ、係数Ｇ２＝ｓｉｎφ
を求め。

スタート点（Ｘ、　Ｙ）　（７）座標をＸ＝Ｘ、、Ｙ＝
Ｙ３．にセットする。そして、初期値としてＸ座標レジ
スタＲ＋、Ｙ座標レジスタＲ２に次のデータを記入する
。

ＲＩ　＝Ｘ、　　＋０．　５　　・　・　・　・　・　
・　・　・　・　・　・（１）Ｒ２＝Ｙｌ　　＋０．　
５　　・　・　・　・　・　・　・　・　・　・　・（
２）第２ステンプ（第５図図示）として、Ｘ座標レジス
タＲ１の値に前記ｃｏｓφを加え、Ｙ座標レジスタＲ２
の値に前記ｓｉｎφを加える。これは。

第４図において５スタ一ト点Ｐ＋　より２２の方に単位
長１だけ直線を引いたときのＸ座標およびＹ座標の値を
示す。ところで、メモリにセットされるデータは１通常
整数単位であるので、前記加算後の値の整数部分１１．
Ｉ！だけを取り出す。なお第５図の第２ステツプで１ｎ
ｔ（Ｐ＋）は、レジスタＲ１より整数部分のみを取り出
すことを示し、１ｎｔ（Ｒ２）はレジスタＲ２より整数
部分のみを取り出すことを示す。ここでｉｎｔは、少数
点以下を切り捨てる関数を示す。

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

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

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

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

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

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

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

イ、このうち■については、前記＋ａｌの直線発生部３
について第４図および第５図にもとづき説明したので省
略し、■および■について順次説明し。

その後に全体の動作について説明する。

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

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

第１ステツプでは３例えば第６図（ａｌに示す如く。

パターンの輪郭線上の一点を捉え、そこから輪郭線を８
連結で追跡し、白丸印で示す如き輪郭上の点の座標列を
得る。輪郭線の始点をＳ、終点をＥとする。

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

第３ステツプでは２点Ｐを終点Ｅから始点Ｓに向かって
輪郭線上を移動させながら点Ｐと点Ｓとの間に■の方法
で直線発生部３により直線を発生し、その区間の輪郭線
を輪郭線切出部４で求め。

比較部５によりこの直線と輪郭線との差を求める。

例えば１点Ｐが第６図（ｂｌに示す星印の位置にあると
き、この星印と始点Ｓ　（Ｘ印）との間の直線を求める
と、　（星印、◎、◎、◎、Ｘ印）の如き直線が得られ
、また輪郭線として星印から左廻り方向にＸ印までの輪
郭線が得られるが、この両者は一敗せず、その差は零で
はない。そのため２次に。

点Ｐは星印位置より一個Ｓ側寄りに移動したＰｌの位置
で同様に直線を発生し、また輪郭線を切り出して一致状
態をチェックする。このようなことを順次ｐ＋、ｐｇと
始点Ｓ方向に移動させて行う。

そして、第６図（ｂｌのＰ、で行うとき、そのＰｖから
始点Ｓに向かう直線とその区間の輪郭線とが一致してそ
の差が零になるので、この点Ｐｖを屈曲点Ｖとして抽出
する。

第４ステツプでは、屈曲点を全部抽出したか否かをチェ
ックするものである。このために、前記第３ステツプで
得た屈曲点■と終点Ｅとを経由して始点Ｓまでの区間の
輪郭線（この例では屈曲点Ｖから右廻り方向の輪郭線）
と、屈曲点Ｖと始点Ｓの直線との差が零か否かをチ、ｒ
−ツクする。このチェ、りは、第３図の屈曲点生成部６
からの指示により、直線発生部３が直線を発生させ１輪
郭線切出部４が輪郭線を切り出し、比較部５がその一致
、不一致をチェックすることにより行われる。

この差が後述するように零ならば、屈曲点抽出処理は終
了することになるが、第６図（ｂｌにおいて。

屈曲点Ｐ、における前記チェックでは不一致であるので
１次の屈曲点を検出するために第５ステツプに続く。

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

第７図は、前記屈曲点検出のための一般的な動作を説明
するフローチャートである。ここでは。

追跡した輪郭線の座標点列を（Ｐ＋　、Ｐｚ　　・・・
Ｐ、、）とし９輪郭線上のｉ番目の点Ｐ、と、ｊ番目の
点Ｐ、との間に前記■の手法（（ａ）の直線発生部３に
おける説明）で発生した点列（Ｎ＋　、Ｎｔ・・・Ｎ、
）と、　（Ｐｌ　・・・Ｐ、）とを比較して９両者が等
しい時はＹＥＳ、等しくないときはＮＯを返す処理ＳＡ
ＭＥ　（ｉ、ｊ）が定義されているものとする。

尚、■屈曲点の位置補正については、既に第２図を用い
て説明した如く、第２図（ａ）図中パターンＰ、ないし
Ｐ、中のパターンＰ２を１ドツト分Ｐ１からＰ２の方向
に移動させた点Ｎと、パターンＰ、を１ド、部分Ｐ、か
らＰ、の方向に移動させた点とが一致し、かつその位置
に輪郭上の点が存在する場合、パターンＰ２の座標値を
点Ｎの座標値に置き換えると共に、パターンＰ、を削除
し９第２図（ｂｌの如きパターンおよび屈曲点ｐ、　、
　　ＰＩＥ。

Ｐ４を得る。これにより、屈曲点の位置補正前の４個の
屈曲点Ｐ１．Ｐｚ　、Ｐｓ　、Ｐａが、３個の屈曲点Ｐ
　＋　、　　Ｐ　１２．　　Ｐ　ａに削減されたことと
なり。

圧縮が実行されたこととなる。

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

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

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

■終点Ｅと始点Ｓとの間の直線を直線発生部３により発
生させ、その直線の座標を比較部９に送出する。また２
輪郭線切出部４は終点Ｅから左廻りで始点Ｓまでの輪郭
線の座標（Ｅ、Ｐ＋　、ＰＫ・・・Ｓ）を比較部５に送
出する。比較部５はこの直線と輪郭線座標とを比較して
不一致のとき。

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

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

第６図（ｄｉに黒丸として示す各屈曲点が屈曲点位置補
正部７に通知される。

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

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

〔発明の効果〕

以上説明したように１本発明によれば、原パターン情報
を屈曲点情報を用いて表現すると共に。

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

【図面の簡単な説明】

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

Claims (1)

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