JPH0337228B2 - - Google Patents

Description

【発明の詳細な説明】 〔概 要〕 原パターンの輪郭線から屈曲点を抽出してパタ
ーン情報量を圧縮する方式において、抽出された
微小四角形の屈曲点パターン中に屈曲点抽出方式
に基づく特定屈曲点パターンが検出されたとき
に、屈曲点を微小四角形の正規の屈曲点位置に補
正する。これにより、原パターンを確実に復元す
ることが出来ると共に圧縮率を向上させ、更に拡
大や縮小等の変換処理時に形崩れのない変換パタ
ーンを生成することが出来る。

〔産業上の利用分野〕

本発明は、文字や図形等の原パターンの情報量
圧縮方式、特に、原パターンの輪郭線から屈曲点
を抽出してパターン情報量を圧縮する方式におい
て、微小四角形の直角部の近傍に抽出された屈曲
点の位置を直角点位置に正しく補正することによ
り、元の原パターンを確実に復元出来ると共に、
圧縮率の向上、拡大や縮小の際のパターンの変形
量を低下させる様に改良したパターン情報量圧縮
方式に関する。

〔従来の技術〕

情報処理装置の記憶装置に文字や図形等の原パ
ターン情報を記憶する場合、記憶量を減らす為に
原パターンの情報量を圧縮して記憶が行われる。
その際、原パターンを完全に復元することが出来
ると共に、拡大や縮小等が容易なパターン情報量
圧縮方式であることが要求される。

第５図は、この様な要求を満足させるパターン
情報量圧縮方式の一例として同一出願人によつて
提案されたパターン情報圧縮方式（特願昭60−
48895号）の構成をブロツク図で示したものであ
る。

第５図において、２１は原パターン保持部で、
原パターンのデータを保持する。２２は追跡部
で、原パターンの輪郭部分を追跡して輪郭線を構
成する座標点列を抽出する。２３は直線発生部
で、輪郭線上の２点間に直線を発生させる。２４
は輪郭線切出部で、原パターンの輪郭線から２点
間の輪郭線を切り出す処理を行う。２５は比較部
で、直線発生部２３から発生された２点間の直線
と輪郭線切出部２４から切り出された輪郭線が等
しいか否かを判別する。２６は屈曲点生成部で、
比較部２５の比較結果に基づいて屈曲点を生成す
る処理を行う。２７は圧縮データ保持部で、屈曲
点生成部２６で生成された屈曲点で構成された圧
縮パターンのデータを保持する。

次に、第５図の動作を、第６図を参照して説明
する。

追跡部２２は、パターン保持部２１の原パター
ンの輪郭部分を追跡して、第６図に示す様に、原
パターンの輪郭線を構成する座標点列P₁〜P₂₀を
抽出する。

いま、P₁点が屈曲点の１つとして検出されて
いるとすると、次の屈曲線点は、次の様にして生
成される。

直線発生部２３は、P₁と輪郭線上の他のPi
点間の直線₁を、P₂を出発点としP₁を終点
として順次発生させる。P₁と輪郭線上の他の
２点間の直線は、例えばDDA（Digital
Differential Analyzer：デイジタル微分解析
機）を用いて発生される。このDDA法による
と、例えばP₁とP₈の直線₁は、P₁，P₂，
P₂₁，P₂₂，P₂₃，P₈の座標点列で形成される。

輪郭線切出部２４は、P₁と輪郭線上の他の
Pi点間の輪郭線P₁Piを、直線発生の場合と同
様にPiを出発点としP₁を終点とし、直線₁
と同期して切り出す。輪郭線P₁Piは、例えば
輪郭線P₁P₈の場合はP₈，P₉，P₁₀，P₁₁，……
P₁₆……P₂₀の座標点列で切り出される。

比較部２５は、直線発生部２３の発生した直
線₁と輪郭線切出部２４の切り出した輪郭
線P₁Piの両座標点列を比較し、両者が一致し
ているか否かを判別する。一致しない場合は、
不一致信号を発生する。

屈曲点生成部２６は、この不一致信号を受け
ると直線発生部２３及び輪郭線切出部２４に指
定して、次の直線_{1 i+1}の発生及び輪郭線
P₁P_i+1の切出しを行わせる。比較部２５は、両
者の座標点列を比較する。

第６図の場合は、直線_{1 16}及び輪郭線P₁P₁₆
に至つて両者の座標点列が一致するので、P₁₆
点で一致信号が出力される。

屈曲線生成部２６は、この一致信号を受ける
とP₁₆をP₁の次の屈曲点として生成する。

以下同様にして、P₁₆を基準としてその次の
屈曲点P₁₁を生成し、更に次の屈曲点P₆の生成
を順次行う。生成された各屈曲点は、圧縮デー
タ保持部２７に格納される。

以上の様にして、原パターンの輪郭線P₁〜P₂₀
を、屈曲点P₁，P₁₆，P₁₁，P₆の４座標点列データ
に圧縮させることが出来る。この屈曲点P₁，P₁₆，
P₁₁，P₆から元の原パターンを正しく復元するこ
とも出来、又、拡大及び縮小処理を正しく行うこ
とが出来る。

第７図は、以上のパターン情報圧縮によつて抽
出された、文字パターン“隘”についての各屈曲
点を例示したもので、大きな黒点が抽出された各
屈曲点である。

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

従来のパターン情報圧縮方式は、前述の様に、
圧縮データから元の原パターンを復元、更に、拡
大及び縮小等の変換処理を正しく行うことが出来
るものである。

然しながら、原パターン中に微小な四角形部分
が存在すると、その屈曲点抽出方式の為に、微小
四角形の直角部分に正規の位置からずれた位置で
且つ余分な屈曲点が抽出される。

例えば、第７図の“隘”のパターンの場合、そ
の中に存在する微小四角形部分R₁，R₂及びR₃の
部分を拡大して示すと、第８図の様になる。

第８図において、小さい黒丸点は輪郭線を構成
する点列であり、大きい四角点Pa〜Pfが抽出さ
れた各屈曲点である。即ち、抽出された各屈曲点
は正しい屈曲点Qa，Qb，Qc，Qdからずれた位
置に発生し、その数も４個（Qa〜Qd）で済むべ
きものが６個（Pa〜Pf）生成される。なお、大
きい四角形の場合には、この様な不都合は生じな
い。

この様に、従来のパターン情報量圧縮方式は、
原パターン中に微小四角形部分が存在すると、そ
の屈曲点抽出方式の為に、微小四角形の直角部分
に正規の位置からずれた位置で且つ余分な屈曲点
が抽出される。この為、それだけ情報量が増加し
て圧縮効果が削減されると共に、拡大や縮小処理
等を行つた場合に形崩れが生じるという問題があ
つた。

本発明は、原パターン中に存在する微小四角形
の直角部分に正規の位置からずれて抽出された各
屈曲点を正規の位置に補正することにより、元の
原画像を確実に復元することが出来ると共に情報
の圧縮率を向上させ、拡大や縮小等によつて形崩
れが生じない様にしたパターン情報圧縮方式を提
供することを目的とする。

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

原パターンの輪郭線上の２点間における直線及
び輪郭線を比較し、両者が一致したときにその点
を屈曲点として抽出する従来の屈曲点抽出方式の
場合、微小四角形について抽出される屈曲点のパ
ターンは、第３図ａ〜ｄに示す４種類のパターン
に分類される。

従つて、この様な４種類の屈曲点パターンａ〜
ｄが検出されたときは、その３個の屈曲点P₂，
P₃及びP₄を第３図a′〜d′に示すP₂及びP₄に補正す
る様にすれば、微小四角形の正規の位置に屈曲点
が生成され、原パターンを正しく復元することが
出来ると共に、パターン情報量の圧縮率を向上さ
せることが出来る。更に、拡大や縮小等の処理を
行つた場合にも形崩れが生じない様にすることが
出来る。

本発明は、この様な知見に基づいて、従来のパ
ターン情報圧縮方式における前述の問題点を解決
したものである。以下、本発明が講じた各手段
を、第１図を参照して説明する。

第１図は、本発明の基本構成をブロツク図で示
したものである。

第１図において、１１は屈曲点抽出手段で、原
パターンから輪郭線を抽出し、この輪郭線上の２
点間における直線と輪郭線とが一致するか否かを
検出する屈曲点抽出方式により輪郭線の屈曲点情
報を抽出する。

１２は屈曲点補正手段で、屈曲点抽出手段１１
によつて抽出された屈曲点中に、微小四角形の場
合に前記屈曲点抽出方式によつて生じる特定屈曲
点パターンが検出されたときに、屈曲点を微小四
角形の正規の屈曲点位置に補正する。

〔作 用〕

屈曲点抽出手段１１は、原パターンから輪郭線
を抽出し、この輪郭線上の２点間の直線と輪郭線
とが一致するか否かを検出する屈曲点抽出方式に
より、輪郭線の屈曲点情報を抽出する。

屈曲点補正手段１２は、屈曲点抽出手段１１に
よつて抽出された屈曲点中に、微小四角形の場合
に前記屈曲点抽出方式によつて生じる特定屈曲点
パターンが存在するかを検出する。第３図ａ〜ｄ
に例示する様な特定屈曲点パターンが検出された
ときは、屈曲点の位置を、第３図a′〜d′に例示す
る様に、微小四角形の正規の屈曲点位置に補正す
る。

この様にすることにより、原パターンの微小四
角形部分においても正規の位置に屈曲点が抽出さ
れ、原パターンを正しく復元することが出来ると
共に、パターン情報量の増加を阻止して圧縮率を
向上させることが出来る。更に、拡大や縮小等の
変換処理を行つた場合にも形崩れの無い交換パタ
ーンを生成することが出来る。

〔実施例〕

本発明の実施例は、第２図〜第４図を参照して
説明する。

第２図は、本発明の一実施例の構成のブロツク
説明図であり、第３図は、前述の様に、同実施例
における微小四角形の屈曲点補正方式の説明図で
あり、第４図は、同実施例による屈曲点抽出例の
説明図である。

(A) 実施例の構成 第２図において、屈曲点抽出手段１１及び屈
曲点補正手段１２については、第１図で説明し
た通りである。

１３は原パターン保持部で、文字や図形等の
原パターンを保持する。

屈曲点抽出手段１１において、１１１は追跡
部で、原パターンの輪郭部分を追跡して輪郭線
を構成する座標点列を抽出する。１１２は直線
発生部で、輪郭線上の２点間に直線を発生させ
る。１１３は輪郭線発生部で、原パターンの輪
郭線から２点間の輪郭線を切り出す処理を行
う。１１４は比較部で、直線発生部１１２から
発生された２点間の直線と輪郭線切出部１１３
から切り出された輪郭線が等しいか否かを判別
する。１１５は屈曲点生成部で、比較部１１４
の比較結果に基づいて屈曲点を生成する処理を
行う。

これらの追跡部１１１、直線発生部１１２、
輪郭線発生部１１３、比較部１１４及び屈曲点
生成部１１５は、第５図に示した従来のパター
ン情報量圧縮方式における追跡部２２、直線発
生部２３、輪郭線発生部２４、比較部２５及び
屈曲点生成部２６にそれぞれ対応し、同様な構
成及び機能を有している。

屈曲点補正手段１２において、１２１は、補
正屈曲点検出部で、屈曲点抽出手段１１によつ
て抽出された各屈曲点中に、その屈曲点抽出方
式によつて生じる微小四角形の特定屈曲点パタ
ーンが存在するかを検出する。

１２２は屈曲点補正部で、微小四角形の特定
屈曲点パターンが検出されたときに、屈曲点を
微小四角形の正規の屈曲点位置に補正する処理
を行う。

１４は圧縮データ保持部で、屈曲点補正手段
１２によつて補正処理された屈曲点で構成され
た原パターンの圧縮パターンのデータを保持す
る。

(B) 実施例の動作 実施例の動作を、第２図〜第５図及び第７図
〜第８図を参照して説明する。

第２図の屈曲点抽出手段１１を構成する追跡
部１１１、直線発生部１１２、輪郭発生部１１
３、比較部１１４及び屈曲点生成部１１５は、
前述の様に、第５図の追跡部２２、直線発生部
２３、輪郭線発生部２４、比較部２５及び屈曲
点生成部２６に対応し、同様な構成及び機能を
有している。

従つて、屈曲点生成部１１５からは、第５図
の屈曲点生成部２６と同様に、原パターンの輪
郭線上の各屈曲点に対する座標点列からなる圧
縮パターンデータが生成される。屈曲点抽出手
段１１内の各部の動作は、対応する第５図にお
ける各部の動作と同じであるので、その詳細な
説明は省略する。

屈曲点抽出手段１１によつて抽出された原パ
ターンの輪郭線上の屈曲点は、微小四角形部分
を除き正しい屈曲点位置に生成されるが、微小
四角形の場合には、第８図に示す様に、正規の
屈曲点位置Qa〜QdからずれたPa〜Pfに生成さ
れることは、既に説明した通りである。

微小四角形部分に生成される屈曲点Pa〜Pf
について考察すると、原パターンの輪郭線上の
２点間における直線と輪郭線をそれらの座標点
列によつて比較し、両者が一致したときにその
点を屈曲点として抽出する屈曲点抽出方式の場
合、微小四角形について抽出される屈曲点のパ
ターンは、第３図ａ〜ｄに示す４種類のパター
ンに分類される。第３図ａ〜ｄにおいて、P₂
とP₃およびP₃とP₄の各２点間における直線と
輪郭線の各座標点列が一致することは、前述の
屈曲点抽出方式から明らかである。

従つて、この様な４種類の屈曲点パターンａ
〜ｄに検出されたときは、その３個の屈曲点
P₂，P₃及びP₄を第３図a′〜d′に示すP₂及びP₄に
補正する様にすれば、微小四角形の正規の位置
に屈曲点が生成されることになる。

補正屈曲点検出部１２１は、屈曲点抽出手段
１１によつて抽出された各屈曲点中に、前記第
３図ａ〜ｄに示すパターンを持つた屈曲点が存
在するか否かを検出する。

第３図ａ〜ｄの屈曲点パターン（以下、屈曲
点パターンａ〜ｄという）の判定条件は、それ
ぞれ次の通りである。なお、以下の説明におい
て、屈曲点Piの座標（Xi，Yi）、即ち、Ｘ座標
をXi、Ｙ座標をYiで表現するものとする。

(1) 屈曲点パターンａの判定条件 屈曲点パターンａの判定条件は、次の〜
の条件がすべて同時に満足されることであ
る。

X₁＝X₂、X₄＝X₅、（Y₂−Y₁）×
（Y₄−Y₅）＞０、（Y₂−Y₁）×（Y₃−Y₂）＞
０、（Y₃−Y₄）×（Y₄−Y₅）＞０、｜X₃
−X₂｜＝２、｜X₃−X₄｜＝１、｜Y₃−
Y₂｜＋｜Y₃−Y₄｜＝３、点（X₂，Y₃）が
黒点（画像点）である、点（X₄，Y₃）が
黒点である。

以上の判定条件において、、、及び
は、図から明らかである。は、点P₂及
びP₄が点P₁及びP₅から同じ側にある要件で
ある。は、P₁，P₂及びP₃が同じ方向で、
P₁→P₂→P₃の順で配列されている要件であ
る。は、P₅，P₄及びP₃が同じ方向で、P₅
→P₄→P₃の順で配列されている要件である。
〜は屈曲点P₁〜P₅が微小四角形の輪郭
線上の屈曲点であることを示す要件で、図か
ら明らかである。

以下同様にして、屈曲点パターンｂ〜ｄの
判定条件は次の様になる。

(2) 屈曲点パターンｂの判定条件 屈曲パターンｂの判定条件は、次の₁〜
の条件がすべて同時に満足されることであ
る。

X₁＝X₂、X₄＝X₅、（Y₂−Y₁）×
（Y₄−Y₅）＞０、（Y₂−Y₁）×（Y₃−Y₂）＞
０、（Y₃−Y₄）×（Y₄−Y₅）＞０、｜X₃
−X₂｜＝１、｜X₃−X₄｜＝１、｜Y₃−
Y₂｜＋｜Y₃−Y₄｜＝３、点（X₂，Y₃）が
黒点である、点（X₄，Y₃）が黒点である。

(3) 屈曲点パターンｃの判定条件 屈曲点パターンｃの判定条件は、次の〜
の条件がすべて同時に満足されることであ
る。

Y₁＝Y₂、Y₄＝Y₅、（X₂−X₁）×
（X₄−X₅）＞０、（X₂−X₁）×（X₃−X₂）＞
０、（X₃−X₄）×（X₄−X₅）＞０、｜Y₃
−Y₂｜＝２、｜Y₃−Y₄｜＝１、｜X₃−
X₂｜＋｜X₃−X₄｜＝３、点（X₃，Y₂）が
黒点である、点（X₃，Y₄）が黒点である。

(4) 屈曲点パターンｄの判定条件 屈曲点パターンｄの判定条件は、次の〜
の条件がすべて同時に満足されることであ
る。

Y₁＝Y₂、Y₄＝Y₅、（X₂−X₁）×
（X₄−X₅）＞０、（X₂−X₁）×（X₃−X₂）＞
０、（X₃−X₄）×（X₄−X₅）＞０、｜Y₃
−Y₂｜＝１、｜Y₃−Y₄｜＝１、｜X₃−
X₂｜＋｜X₃−X₄｜＝３、点（X₃，Y₂）が
黒点である、点（X₃，Y₄）が黒点である。

補正屈曲点検出部１２１によつて前述の屈曲
点パターンが検出されたとき、屈曲点補正部１
２２は、屈曲点パターンの種類に応じて次の様
に各屈曲点の位置及び数を補正する。

(1)′ 屈曲点パターンａ又はｂが検出された場
合 屈曲点パターンａ又はｂが検出された場合
は、点P₂とP₄のＹ座標をY₃に補正し、点P₃
を削除する。この補正処理により、屈曲点パ
ターンａ及びｂは第３図a′及びｂの様に補正
されて、微小四角形の正規の屈曲点位置に屈
曲点P₂及びP₄がそれぞれ生成される。

(2)′ 屈曲点パターンｃ又はｄが検出された場
合 屈曲点パターンｃ又はｄが検出された場合
は、点P₂とP₄のＸ座標をX₃に補正し、点P₃
を削除する。この補正処理により、屈曲点パ
ターンｃ及びｄは第３図c′及びd′の様補正さ
れ、微小四角形の正規の屈曲点位置に屈曲点
P₂及びP₄がそれぞれ生成される。

以上の様に補正処理された各屈曲点の座標デー
タは、圧縮データ保持部１４に送られて格納され
る。なお、屈曲点パターンａ〜ｄの何れにも該当
しない各屈曲点は、補正処理されることなく、そ
のまま圧縮データ保持部１４に格納される。

第４図は、以上の様に補正処理によつて抽出さ
れた文字パターン“隘”の各屈曲点を示したもの
で、大きな黒点が抽出された各屈曲点である。第
８図と対比すると明らかな様に、微小四角形R₁，
R₂及びR₃の各屈曲点が正規の屈曲点位置におい
て抽出されていることが分る。

〔発明の効果〕

以上説明した様に、本発明によれば、次の諸効
果が得られる。

(イ) 屈曲点補正処理により、原パターンの微小四
角形部分においても正規の屈曲点位置において
屈曲点を抽出することが出来る。

(ロ) 前記(イ)により原パターンを正しく復元するこ
とが出来る。

(ハ) 屈曲点補正処理により屈曲点の増加を阻止し
て、圧縮率を向上させることが出来る。

(ニ) 前記(イ)により拡大や縮小等の変更処理を行つ
た場合にも形崩れの無い変換パターンを生成す
ることが出来る。

【図面の簡単な説明】

第１図…本発明の基本構成の説明図、第２図…
本発明の一実施例の構成の説明図、第３図…同実
施例における微小四角形の屈曲点補正方式の説明
図、第４図…同実施例による屈曲点抽出例の説明
図、第５図…従来のパターン情報量圧縮方式の説
明図、第６図…従来のパターン情報量圧縮方式に
おける屈曲点抽出方式の説明図、第７図…従来の
屈曲点抽出方式による屈曲点抽出例の説明図、第
８図…従来の屈曲点抽出方式による微小四角形に
おける屈曲点抽出例の説明図。 第１図及び第２図において、１１…屈曲点抽出
手段、１２…屈曲点補正手段、１３…原パターン
保持部、１４…圧縮データ保持部。

Claims (1)

1. 【特許請求の範囲】 １ 原パターンの輪郭線から屈曲点を抽出してパ
   ターン情報量を圧縮するパターン情報量圧縮方式
   において、 (a) 原パターンから輪郭線を抽出し、この輪郭線
   上の２点間における直線と輪郭線とが一致する
   か含かを検出する屈曲点抽出方式より輪郭線の
   屈曲点情報を検出する屈曲点抽出手段１１と、 (b) 屈曲点抽出手段１１によつて抽出された屈曲
   点中に、微小四角形の場合に前記屈曲点抽出方
   式によつて生じる特定屈曲点パターンが検出さ
   れたときに、屈曲点を微小四角形の正規の屈曲
   点位置に補正する屈曲点補正手段１２、 を備えたことを特徴とするパターン情報量圧縮方
   式。