JPH0810395B2 - パタ−ン圧縮表現方式 - Google Patents

Description

【発明の詳細な説明】 〔目次〕 概要 産業上の利用分野 従来の技術（第３図） 発明が解決しようとする問題点 問題点を解決するための手段（第１図） 作用 実施例 全体構成の説明（第２図、第４図） 対検出／分割ラベル付与回路（第５図） 分割輪郭線抽出回路（第６図、第７図） ベクトル化回路（第８図） 輪郭ベクトル補正回路 微小直角部補正（第９図、第11図、第13図） 直角部補正（第10図、第12図） 鈍角／鋭角部補正（第13図、第14図） 輪郭ベクトル対抽出回路（第15図） 発明の効果 〔概要〕 パターンを左右の輪郭ベクトル対で表現した後、生成
パターンの品質劣化を引き起すと推測される輪郭ベクト
ル列を補正することにより、高速復元はもとより、高品
質なパターンを生成できるようにした。

〔産業上の利用分野〕

本発明は、文字、図形などの、白黒画素からなる２値
パターンを、データ圧縮して表現するパターン圧縮表現
方式に関する。

近年、文字のディジタル処理技術の導入が進み、今や
OA機器や電算写植システム等では文字の品質そのものが
問われる時代になっている。このようなシステムでは、
膨大な数の文字パターンが要求されるため、それらを格
納しておくための膨大な記憶容量が必要となる。この記
憶容量の問題を解決するため、文字パターンをフルドッ
ト形式で格納するのではなく、何らかの形で圧縮し、そ
の圧縮データから必要に応じて原文字パターンを復元し
たり、或いは、該圧縮データに拡大／縮小等の幾何学的
変換を施して原文字の幾何学的変換パターンを生成する
技術が必要とされる。また、コンピュータグラフィクス
等の分野においても、ベクトルデータで与えられた図形
データを復元したり、その幾何学的変換パターンを生成
する技術が必要とされる。特に、パターンの復元／生成
技術に関してはリアルタイム性が要求され、高速処理で
きることが肝要である。本発明は、このような分野に有
効な２値パターンの高速、高品質復元を実現できる方式
を提供しようとするものである。

〔従来の技術〕

高速復元を実現できるパターン圧縮技術としては、本
発明者らが創作した「高速復元処理向きパターン圧縮方
式」（特願昭61− ）がある。これは、パターンを
輪郭ベクトル対で圧縮表現する技術である。第３図は漢
字の「富」をドットで表現したものであり、ディジタル
処理では連続パターンもこのようなドットの集まりにな
るが、この文字パターンの輪郭を直線近似すると大ドッ
ト間を結ぶ直線群が得られ、そしてこれらの直線（ベク
トル）群は、輪郭の両縁に当るもの２つが対をなしてお
り、上記圧縮方式では輪郭ベクトル群をこの対のベクト
ル群として扱う。大ドットは、基本的にはこゝで直線が
曲るので屈曲点と呼ぶ。第３図のａは原パターンに屈曲
点を重ねて表示した図、ｂは圧縮データから復元した原
パターンに屈曲点を重ねて表示した図、ｃは圧縮データ
から拡大復元したパターンに屈曲点を重ねて表示した図
である。

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

上記圧縮方式では、矢印を付して示す角など、本来直
交状態であるべき所が角がとれて鈍るという問題があ
る。これは輪郭追跡に当って８方向連結をとるからで、
４方向連結なら上下左右のものしか連結がないとするか
ら交わる角は90°又は180°になるが、８方向連結では
上下左右の他方に斜め上下左右も連結ありとするから、
135°の角も生じてしまう。圧縮データから原パターン
を復元する場合これは格別問題でないが、圧縮データに
幾何学的変換を施し、種々の幾何学的変換パターンを生
成する場合、特に第３図ｃのように拡大表示すると輪郭
線形状劣化が目立ち、生成パターンの品質を著しく損な
う。

本発明は、この問題点を解決するために、生成パター
ンの品質劣化を引き起こす部分の圧縮データ（或る角度
を成す輪郭線形状部分であると予想される輪郭ベクトル
列）を検出し、その部分の輪郭ベクトル列を補正してお
くことによって、幾何学的変換によるパターンの生成に
おいても、品質劣化のないパターン圧縮方式を提供する
ことを目的とする。

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

第１図は本発明の原理ブロック図である。この図にお
いて、１はフルドット文字パターンである。２はこのフ
ルドット文字パターンの水平輪郭線以外の輪郭線を左輪
郭線、右輪郭線に分類し、それらを対として抽出するパ
ターンの輪郭線対抽出手段である。３はパターンの輪郭
線対抽出手段２で捉えた輪郭線対を、輪郭線単位でベク
トル化する輪郭線のベクトル化手段であり、４は輪郭線
のベクトル化手段３で得られた輪郭ベクトルデータを参
照し、或る角度を成す輪郭線形状部分の輪郭ベクトル列
を検出し、その部分の輪郭ベクトルデータを補正する輪
郭ベクトル補正手段である。５は輪郭ベクトル補正手段
４の出力である輪郭線のベクトルデータを、輪郭線対の
情報と共に表現する輪郭線対ベクトルの表現手段であ
る。

〔作用〕

本発明は、輪郭ベクトル補正手段４を備え、或る角度
を成す輪郭線形状部分の輪郭ベクトル列を検出し、幾何
学的変換を施しても原パターンとその形状が著しく変化
しないように、その部分の輪郭ベクトル列を補正するの
で、高品質なパターンを高速に復元・生成できる。

〔実施例〕

全体構成の説明 第２図は本発明の一実施例を示す。この図において6,
8はパターンメモリ、11,13は座標点テーブル、７は対検
出ラベル付与回路、９は分割ラベル付与回路、10は分割
輪郭線抽出回路、12はベクトル化回路、14は輪郭ベクト
ル補正回路、15は輪郭ベクトル対抽出回路である。与え
られた文字のフルドットパターンはパターンメモリ６に
保持される。

対検出／分割ラベル付与回路 まず、対検出ラベル付与回路７は、パターンメモリI6
からフルドット文字パターンを読み出し、Ｘ方向（水平
方向）に走査して検出した黒ランに同一の対検出ラベル
を付与し、パターンメモリII8に書き込む。第４図
（ｂ）は、第４図（ａ）に対する対検出ラベルの付与結
果を示したものであり、11,222,……が該ラベルであ
る。なおこの図では対検出ラベルは下一桁のみを表して
おり、従って０以降のもの0,1,2,……は10,11,12,……
である。

続いて、分割ラベル付与回路９は、パターンメモリII
8内の対検出ラベルパターンを参照しながら、以下の処
理によって、パターンを分割するための分割ラベルを付
与し、その結果得られる分割ラベルパターンをパターン
メモリII8の別プレーンに格納する。

ステップI:対検出ラベルパターンをＸ方向に走査（副
走査方向はＹ方向）し、同一の対検出ラベルが付与され
ている黒ランを検出する。その始点，終点のＸ座標をそ
れぞれX₁，X₂とし、Ｙ座標をY₀とする。対検出ラベルパ
ターンをすべて走査したら終了とする。

ステップII:ステップＩで検出した黒ランの上下の行
（Y₀−１），（Y₀＋１）を点（X₁−１）から点（X₂＋
１）まで走査し、その点間の白領域および対検出ラベル
の出現状態を調べ、その状態を以下に示す３つの状態に
分類する。

・状態A:白領域のみが存在する。

・状態B:対検出ラベルが１種類（白領域を含んで良い）
存在する。

・状態C:対検出ラベルが２種類以上（色領域を含んで良
い）存在する。

ステップIII:ステップIIで分類した状態の組み合わせ
によって、以下の処理を実行し、分割ラベルパターンを
を作成する（第５図参照）。なお以下の（ａ）〜（ｋ）
は第５図の（ａ）〜（ｋ）に対応する。

（Y₀−１）（Y₀＋１） ステップIV:上記ステップを繰り返す。第４図（ｃ）
は、第４図（ｂ）に対する処理結果を示す。

分割輪郭線抽出回路 次に、分割輪郭線抽出回路10は、パターンメモリII8
に格納された分割ラベルパターン（第４図（ｃ）がその
一例）を参照しながら、以下の処理によって、分割され
たパターン輪郭線の座標点列を抽出する。

ステップI:分割ラベルパターンをＸ方向に走査し、上
下方向（Ｙ方向）に隣接する▲と▼、▲と●、或いは●
と▼の分割ラベルの対を検出し（第６図（ａ）のケース
Ｉ〜III）、検出する度毎に、新しい対検出ラベル（対
検出ラベルパターンで使用したラベル数を１インクリメ
ントしたラベル、図示の例では20,21,……）と、上下方
向に隣接する部分の両端の輪郭線上の点列の座標値を座
標点テーブルI11に書き込む。但し、座標点テーブルI11
に書き込む座標点列は、その両端の分割ラベルの状態に
よって異なる。即ち、第６図（ｂ）に示すように、左端
の座標点列がｉ−左）上側の分割ラベル列が２つ以上長
い場合は、下側の左端と上側のそれより１つだけ左方
の、さらにその左方のとし、ｉ−右）上側の分割ラ
ベル列が１つだけ長い場合は、下側の左端と上側のそ
れより１つだけ左方ののみとし、ii−左）下側の分割
ラベル列が２つ以上長い場合は、上側の左端と下側の
それより１つだけ左方の、さらにその左方のとし、
ii−右）下側の分割ラベル列が１つだけ長い場合は、上
側の左端と下側のそれより１つ左方のだけとする。
右側の座標点列もこれに準ずる。なおは座標点列
を座標点テーブルI11に格納する順番でもある。また、
こゝでは▲と▼の組み合せを示したが、▲と●、●と▼
についても同様である。また、書き込む順序は、左側の
座標点列、右側の座標点列の順とし、一つの分割輪郭線
の座標点列を区別するために、各データの最後にはデリ
ミタを付ける。

ステップII:分割ラベルパターンをＸの正方向に走査
し、左隣が白領域の▲，▼、或いは、●を検出する。●
の場合はその点のみを輪郭線の点列とし、その点の対検
出ラベルと座標値を座標点テーブルI11に書き込む。▲
の場合（例えば第７図のａ）は右廻りに、▼の場合（同
ｂ）は左廻りに分割ラベル（即ち、輪郭線）を、△，
▽，∧，∨，▲，▼，●、或いは、＊（既に追跡され、
追跡の終点としてマークされた点に付与するラベル）ま
で追跡し、その間の点列を追跡の始点の対検出ラベルと
共に座標点テーブルI11に格納する（最後に、デリミタ
を付ける）。この座標点テーブルの，，は第４図
（ｄ）のそれに対応しており、最初のはベクトル対
の左側、後のは同右側に対応する（この対応関係は
走査順により決まるが、こゝでは最初のものは左側、後
のものが右側である。なおベクトル対は全てＹ成分を持
っており、水平なベクトル対はない。かゝるベクトル対
の左，右のベクトル間を塗り潰すとフルドットパターン
になる）。

始点とＸ方向に連なる同一分割ラベル部分は無条件に
追跡し、追跡済みの分割ラベル■を追跡済みを意味する
ラベル＋にする。また、追跡の始点の分割ラベルが▲の
時、追跡の終了条件として、分割ラベル△に到達した場
合には、それとＸ方向に連なる△の端点まで追跡を行
う。同様に、追跡の始点の分割ラベルが▼の時、追跡の
終了条件として、分割ラベル▲、或いは、▽に到達した
場合には、それぞれ、それとＸ方向に連なる▲、或い
は、▽の端点まで追跡を行う。さらに、追跡の始点の分
割ラベルが▲の時、追跡の終点の分割ラベルが、△，
▽，∧∨ ，▼であれば、終点をラベル＊に変更する。
また、追跡の始点の分割ラベルが▼の時、追跡の終点の
分割ラベルが、△，▽，∧，∨，▲であれば、終点をラ
ベル＊に変更する。

ステップIII:分割ラベルパターンをＸの負方向に走査
し、右隣が白領域の▲，▼、或いは、●を検出する。●
の場合はその点のみを輪郭線の点列とし、その点の対検
出ラベルと座標値を座標点テーブルI11に書き込む。▲
の場合（例えば第７図のｃ）は左廻りに、▼の場合（同
ｄ）は右廻りに分割ラベルを、△，▽，∧，∨，▲，
▼，●、或いは、＊まで追跡し、その間の点列を追跡の
始点の対検出ラベルと共に座標点テーブルI11に格納す
る（最後に、デリミタを付ける）。

但し、始点とＸ方向に連なる同一分割ラベル部分は無
条件に追跡し、追跡済みの分割ラベル■をラベル＋にす
る。また、追跡の始点の分割ラベルが▲の時、追跡の終
了条件として、分割ラベル△に到達した場合には、それ
とＸ方向に連なる△の端点まで追跡を行う。同様に、追
跡の始点の分割ラベルが▼の時、追跡の終了条件とし
て、分割ラベル▲、或いは、▽に到達した場合には、そ
れぞれ、それとＸ方向に連なる▲、或いは、△の端点ま
で追跡を行う。さらに、追跡の始点の分割ラベルが▲の
時、追跡の終点の分割ラベルが△，▽，∧，∨，▼であ
れば、終点をラベル＊に変更する。また、追跡の始点の
分割ラベルが▼の時、追跡の終点の分割ラベルが△，
▽，∧，∨，▲であれば、終点をラベル＊に変更する。

ステップIV:ステップII,ステップIIIと同様の手順
で、分割ラベルパターンをＸの正方向（負方向）に走査
し、左隣（右隣）が白領域の△，▽，∧，或いは、∨を
検出する。正方向走査時は、△，∧は左廻り、▽，∨は
右廻りに、負方向走査時は、△，∧は右廻り、▽，∨は
左廻りに分割ラベルを追跡し、その間の点列を追跡の始
点の対検出ラベルと共に座標点テーブルI11に格納する
（最後にデリミタを付ける）。

但し、始点とＸ方向に連なる同一分割ラベル部分は無
条件に追跡し、追跡済みの分割ラベル■をラベル＋にす
る。また、追跡の始点の分割ラベルが△，∧の時、追跡
の終了条件として、分割ラベル▽に到達した場合には、
それとＸ方向に連なる▽の端点まで追跡を行う。さら
に、追跡の始点の分割ラベルが△，∧の時、追跡の終点
の分割ラベルが△，▽，∧，∨，▲であれば、終点をラ
ベル＊に変更する。また、追跡の始点の分割ラベルが
▽，∨の時、追跡の終点のラベルが△，▽，∧，∨，▼
であれば、終点をラベル＊に変更する。

ステップV:ステップII,ステップIIIと同様の手順で、
分割ラベルパターンをＸの正方向（負方向）に走査し、
左隣（右隣）が白領域の■を検出する。まず、正方向走
査時は、右廻り、負方向走査時は、左廻りに、▲，▼，
●、或いは、＊に出会うまで分割ラベルを追跡し、その
点を追跡の始点とする。次に、その追跡の始点から逆
に、正方向走査時は、左廻り、負方向走査時は、右廻り
に、分割ラベルを、▲，▼，●、或いは、＊まで追跡し
て、その間の点列を最初に検出された分割ラベル■の点
の対検出ラベルと共に、座標点テーブルI11に格納する
（最後に、デリミタを付ける）。

但し、最初に検出された分割ラベル■は、追跡済みの
ラベル＋に変更しないが、他の追跡途中の■は＋に変更
する。

上述の処理によって、分割された輪郭線毎の輪郭点座
標がすべて座標点テーブルI11に格納されることになる
（第７図参照）。尚、テーブル上ではデリミタとして
“−1"を使用している。

ベクトル化回路 このようにして座標点テーブルI11に格納された輪郭
座標点データを基にベクトル化回路12は、以下のステッ
プで分割輪郭線単位でのベクトル化を行い、屈曲点を抽
出すると共に、パターンメモリI6内のフルドットパター
ン上の屈曲点座標位置に、その点が屈曲点であることを
示すラベル、例えば、黒画素“1"、白画素“0"と区別す
るためのラベルとして“2"を書き込む。

ステップI:座標点テーブルI11から１つの分割輪郭線
の座標点列｛P1,P2,……Pn｝、例えば第７図の（10,3）
（11,2）（12,1）、を読み出す。未処理の分割輪郭線が
なければ、終了する。

ステップII:分割輪郭線の点列｛P1,P2,……Pn｝からP
1を屈曲点V1として抽出すると共に、パターンメモリI6
内のフルドットパターン上の点P1の座標位置にラベル
“2"を書き込む。

ステップIII:点Pi（ｉ＝n,n−1,……１）と点P1との
間にDDAで発生した直線と、点Piと点P1との間の輪郭線
とが一致するまで、ｉを減少させる。一致した時の点Pi
を屈曲点として抽出し、これを点V2とすると共に、パタ
ーンメモリI6内のフルドットパターン上の点Piの座標位
置にラベル“2"を書き込む。

ステップIV:点Pi（ｉ＝n,n−1,……１）と点Vj（ｊ＝
2,3,……,m）との間にDDAで発生した直線と、点Piと点V
jとの間の輪郭線とが一致するまで、ｉを減少させる。
一致した時の点Piを屈曲点として抽出し、これをVj＋１
とする。さらに、パターンメモリI6内のフルドットパタ
ーン上の点Piの座標位置にラベル“2"を書き込む。点Pn
が屈曲点として抽出されれば、１つの分割輪郭線に対す
る処理を終え、ステップＩに戻る。

ステップV:ステップIVを繰り返す。

上述の処理によって、分割された輪郭線毎の対検出ラ
ベルと屈曲点座標点列、例えば第８図（ｂ）の（110,
3）（12,1）、（6,7）（5,8），……が座標点テーブ
ルII13に格納されると共に、パターンメモリI6内のフル
ドットパターン上に抽出された屈曲点がラベル“2"とし
て表現される。

輪郭ベクトル補正回路 さらに、輪郭ベクトル補正回路14は、座標点テーブル
II13に格納された屈曲点座標点列、即ち、輪郭ベクトル
列、パターンメモリI6内の屈曲点位置が表現されたフル
ドットパターン（以下、屈曲点付フルドットパターンと
呼ぶ）、パターンメモリII8内の分割ラベルパターンを
参照しながら、或る角度を形成する輪郭線形状部分、例
えば、直角部の状態にある輪郭線形状から抽出された輪
郭ベクトル列を推定し、その輪郭ベクトル列を、幾何学
的変換を施しても形状が著しく変化しないように補正し
て、その補正結果を座標点テーブルII13に格納する。前
述のように、直交すべき部分が再生文字では第３図ｄの
如く角がとれまた同ｅの如く直線部がなくなったりする
が、本処理でこれを補正して直交状態が得られるように
する。補正処理は、大きく分けて、少なくともいずれか
一方の長さが短い直角部を補正する微小直角部補正処
理、直角部を補正する直角部補正処理、或る角度までの
輪郭線形状部を補正する鋭角／鈍角部補正処理から成
る。以下、各々の補正処理の詳細を述べる。

微小直角部補正 座標点テーブルII13に格納された屈曲点座標点列、パ
ターンメモリI6内の屈曲点付フルドットパターン、パタ
ーンメモリII8内の分割ラベルパターンを参照しなが
ら、以下のステップによって、屈曲点（輪郭ベクトル）
を補正し、その結果を再び座標点テーブルII13に格納す
る。

ステップI:座標点テーブルII13の屈曲点座標点列を、
１つの分割輪郭線単位で参照し、以下の処理を実行す
る。未処理の分割輪郭線がなければ、終了する。今、参
照しているｓ番目の分割輪郭線の屈曲点座標点列をCs＝
｛P1,P2,……Pns｝とする。但し、屈曲点の個数nsが２
以下であれば、ｓをインクリメントし、次の分割輪郭線
の屈曲点座標点列の処理に移る。

ステップII:分割輪郭線の屈曲点座標点列Cs＝｛P1,P
2,……Pns｝から、順次、５点Ph,Pi,Pj,Pk,Pl｛ｉ＝1,
2,……,ns−２）ずつを取り出し、以下の処理を実行す
る。各点の座標値をそれぞれ、（Xh,Yh），（Xi,Yi），
（Xj,Yj），（Xk,Yk），（Xl,Yl）とする。但し、 ｉ）・ｉ＞ns−２ならば、ｓをインクリメントし、ステ
ップＩへ（次の分割輪郭線の処理へ）。

・ｉ≦ns−２であっても、点Pm（ｉ＜ｍ≦ns）のう
ち、その値として消去フラグ“−2"（消去フラグに関し
ては、後述する）以外のものを持つ点の個数が１以下で
あれば、ｓをインクリメントし、ステップＩへ（次の分
割輪郭線の処理へ）。

ii）取り出した点Piの値が消去フラグ“−2"であれば、
ｉをインクリメントし、ステップIIへ。

iii）点Phは、点Pi−１から点Plに向かって屈曲点座標
点列Csをサーチし、最初に、消去フラグ“−2"以外の値
を持つ点とし、点Pj,Pk,Plは、それぞれ、点Pi＋１から
点Pnsに向かって屈曲点座標点列Csをサーチし、消去フ
ラグ“−2"以外の値を持つ１番目、２番目、３番目の点
とする。但し、 ａ）点Phが未定義の場合、次のステップで定義する。

ｂ）点Plが未定義の場合、次のステップで定義する。

ステップIII:点Pi,Pj,Pkが、次の条件をすべて充たす
か否かを調べる（第11図参照）。

ｉ）|Xi−Xj|＝１で、かつ、 |Yi−Yj|＝1or2 ii）|Xj−Xk|＝１で、かつ、 |Yj−Yk|＝1or2 □上記条件をすべて充たす場合、以下の処理を実行す
る。但し、 ａ）ｉ＝１のとき、点Pi,Pj,Pkの位置関係を調べた
後、分割ラベルパターンを参照し、 ・点Pi（P1）が分割ラベル●，▲，▼であれば、点Pi
（P1）からＸの正方向（点Pi,Pj,Pkの位置関係が第11図
（ｃ），（ｄ）の関係にある場合）、或いは、負方向
（点Pi,Pj,Pkの位置関係が第11図（ａ），（ｂ）の関係
にある場合）に分割ラベルパターンを走査し、第13図に
示すような、上下方向（Ｙ方向）に白画素が隣接する点
Pi（P1）と同一の分割ラベルを追跡し、その連続状態の
端点を点Phとする。

連続状態がない場合、 ・ns＝３のときは、ｓをインクリメントし、ステップ
Ｉへ（次の分割輪郭線の処理へ）。

・ns＞３のときは、点Ph＝点Pi（P1）とする。

・点Pi（P1）が分割ラベル●，▲，▼でなければ、 ・ns＝３のときは、ｓをインクリメントし、ステップ
Ｉへ（次の分割輪郭線の処理へ）。

・ns＞３のときは、ｉをインクリメントし、再び、ス
テップIIへ。

ｂ）ｉ＝ns−２のとき、或いは、ｉ＜ns−２であって
も、点Pkが屈曲点座標点列Csの最後の点Pnsであると
き、点Pi,Pj,Pkの位置関係を調べた後、分割ラベルパタ
ーンを参照し、 ・点Pk（Pns）が分割ラベル●，▲，▼であれば、点P
k（Pns）からＸの正方向（点Pi,Pj,Pkの位置関係が第11
図（ｃ），（ｄ）の関係にある場合）、或いは、負方向
（点Pi,Pj,Pkの位置関係が第11図（ａ），（ｂ）の関係
にある場合）に屈曲点付フルドットパターンを参照しな
がら、分割ラベルパターンを走査し、第９図、第13図に
示すような、上下方向（Ｙ方向）に白画素が隣接する点
Pk（Pns）と同一の分割ラベルを、屈曲点が出現するま
で追跡し、その屈曲点を点P1とする。

連続状態がなければ、ｓをインクリメントし、ステッ
プＩへ（次の分割輪郭線の処理へ）。

・点Pk（Pns）が分割ラベル●，▲，▼でなければ、
ｓをインクリメントし、ステップＩへ（次の分割輪郭線
の処理へ）。

ステップIV:点Piから点Phに向かうベクトルをV1、点P
jから点Piに向かうベクトルをV2、点Pjから点Pkに向か
うベクトルをV3、点Pkから点P1に向かうベクトルをV4と
して、これらの点およびベクトルが以下の条件をすべて
充たすか否かを調べる（第11図参照）。

ｉ）V1とV4がＸ軸に平行で、かつ、その向きが同じ。

ii）V1の長さ＞Th、或いは、V4の長さ＞Th（但し、Thは
閾値）。

iii）屈曲点付フルドットパターン上で点（Xj,Yi）が黒
画素。

iv）屈曲点付フルドットパターン上で点（Xj,Yk）が黒
画素。

□上記条件を充たす場合、座標点テーブルII13内の点Pi
の座標格納場所に（Xj,Yi）を、また、点Pkの座標格納
場所に（Xj,Yk）を書き込み、点Pjの座標格納場所に
は、その点が消去されたことを示す消去フラグ、例え
ば、“−2"を書き込む。

□上記条件を充たさない場合、ｉをインクリメントし、
再び、ステップIIへ。

この補正で、第11図（ａ）〜（ｄ）は同（ｅ）〜
（ｈ）の如くになる。

直角部補正 座標点テーブルII13の屈曲点座標点列、パターンメモ
リI6内の屈曲点付フルドットパターン、パターンメモリ
II8内の分割ラベルパターンを参照しながら、以下のス
テップによって、屈曲点（輪郭ベクトル）を補正し、そ
の結果を再び座標点テーブルII13に格納する。

ステップI:座標点テーブルII13の屈曲点座標点列を、
１つの分割輪郭線単位で参照し、以下の処理を実行す
る。未処理の分割輪郭線がなければ、終了する。今、参
照しているｓ番目の分割輪郭線の屈曲点座標点列をCs＝
｛P1,P2,……Pns｝とする。但し、屈曲点の個数nsが１
以下であれば、ｓをインクリメントし、次の分割輪郭線
の屈曲点座標点列の処理に移る。

ステップII:分割輪郭線の屈曲点座標点列Cs＝｛P1,P
2,……Pns｝の最初の点P1を取り出し、その座標値を（X
1,Y1）とする。点P1が分割ラベルパターン上で分割ラベ
ル●，▲，▼であれば、ステップIIIへ、そうでなけれ
ば、ｓをインクリメントし、ステップＩへ（次の分割輪
郭線の処理へ）。

ステップIII:分割輪郭線の屈曲点座標点列Cs＝｛P1,P
2,……Pns｝から、最初から２番目の点P2（即ち、最初
の２点P1,P2）を取り出す。その値が消去フラグ“−2"
であれば、ｓをインクリメントし、ステップＩへ（次の
分割輪郭線の処理へ）。そうでなければ、その座標値を
（X2,Y2）とし、点P1,P2が次のいずれかの条件を充たす
か否かを調べる（第12図参照）。

ｉ）|X1−X2|＝１で、かつ、 |Y1−Y2|＝１ ii）|X1−X2|＝１で、かつ、 |Y1−Y2|＝２ iii）|X1−X2|＝２で、かつ、 |Y1−Y2|＝１ □上記条件のいずれかを充たす場合、点P1,P2の位置関
係を調べ、ステップIVへ。

□上記条件のいずれも充たさない場合、ｓをインクリメ
ントし、ステップＩへ（次の分割輪郭線の処理へ）。

ステップIV:分割輪郭線の屈曲点座標点列Cs＝｛P1,P
2,……Pns｝から、最初から３番目の点P3を取り出し、
ステップＶを実行する。但し、 ｉ）ns＝２のとき、点P2（Pns）からＸの正方向（点P
1,P2の位置関係が第12図（ｂ），（ｄ）の関係にある場
合）、或いは、負方向（点P1,P2の位置関係が第12図
（ａ），（ｃ）の関係にある場合）に屈曲点付フルドッ
トパターンを走査し、第10図に示すような、上下方向
（Ｙ方向）に白画素が隣接する黒画素（白画素以外、即
ち、屈曲点のラベルも含む）の連続状態を検出し、その
連続状態の端点を点P3とする。

連続状態がなければ、点P3＝点P2（Pns）とする。

ステップV:点P1からＹの負方向（点P1,P2の位置関係
が第12図（ａ），（ｂ）の関係にある場合）、或いは正
方向（点P1,P2の位置関係が第12図（ｃ），（ｄ）の関
係にある場合）に屈曲点付フルドットパターンを走査
し、第10図に示すような、左右方向（Ｘ方向）に白画素
が隣接する黒画素（白画素以外、即ち、屈曲点のラベル
も含む）の連続状態を検出し、その連続状態の端点を点
P0、その座標を（X0,Y0）とする。連続状態がなけれ
ば、点P0＝点P1とし、以下の処理を実行する。

ステップVI:点P1から点P0に向かうベクトルをV0、点P
2から点P1に向かうベクトルをV1、点P2から点P3に向か
うベクトルをV2とし、これらの点およびベクトルが以下
の条件をすべて充たすか否かを調べる。

ｉ）V2がＸ軸に平行で、かつ、V0,V1,V2の向きが第12図
の状態にある。

ii）V0の長さ＞Th、或いは、V2の長さ＞Th（但し、Thは
閾値）。

iii）屈曲点付フルドットパターン上で点（X1,Y2）が黒
画素。

□上記条件を充たす場合、座標点テーブルII13内の点P2
の座標格納場所に（X1,Y2）を書き込む。

□上記条件を充たさない場合、ｓをインクリメントし、
ステップＩへ（次の分割輪郭線の処理へ）。

この補正で第12図（ａ）〜（ｄ）は同（ｅ）〜（ｈ）
の如くになる。

鋭角／鈍角部補正 座標点テーブルII13の屈曲点座標点列、パターンメモ
リI6内の屈曲点付フルドットパターン、パターンメモリ
II8内の分割ラベルパターンを参照しながら、以下のス
テップによって、屈曲点（輪郭ベクトル）を補正し、そ
の結果を再び座標点テーブルII13に格納する。

ステップI:座標点テーブルII13の屈曲点座標点列を、
１つの分割輪郭線単位で参照し、以下の処理を実行す
る。未処理の分離輪郭線がなければ、終了する。今、参
照しているｓ番目の分割輪郭線の屈曲点座標点列をCs＝
｛P1,P2,……Pns｝とする。但し、屈曲点の個数nsが２
以下であれば、ｓをインクリメントし、次の分割輪郭線
の屈曲点座標点列の処理に移る。

ステップII:分割輪郭線の屈曲点座標点列Cs＝｛P1,P
2,……,Pns｝から、順次、４点Ph,Pi,Pj,Pk（ｉ＝1,2,
……,ns−１）ずつを取り出し、以下の処理を実行す
る。各点の座標値をそれぞれ（Xh,Yh），（Xi,Yi），
（Xj,Yj），（Xk,Yk）とする。但し、 ｉ）・ｉ＞ns−１ならば、ｓをインクリメントし、ステ
ップＩへ（次の分割輪郭線の処理へ）。

・ｉ≦ns−１であっても、点Pm（ｉ＜ｍ≦ns）のう
ち、その値として消去フラグ“−2"以外のものを持つ点
が存在しなければ、ｓをインクリメントし、ステップＩ
へ（次の分割輪郭線の処理へ）。

ii）取り出した点Piの値が消去フラグ“−2"であれば、
ｉをインクリメントし、ステップIIへ。

iii）点Phは、点Pi−１から点P1に向かって屈曲点座標
点列Csをサーチし、最初に、消去フラグ“−2"以外の値
を持つ点とし、点Pj,Pkは、それぞれ、点Pi＋１から点P
nsに向かって屈曲点座標点列Csをサーチし、消去フラグ
“−2"以外の値を持つ１番目、２番目の点とする。但
し、 ａ）ｉ＝１のとき、分割ラベルパターンを参照し、 □点Pi（P1）が分割ラベル●，▲，▼であれば、点Pi
（P1）からＸの正方向および負方向に分割ラベルパター
ンを走査し、第13図に示すような、上下方向（Ｙ方向）
に白画素が隣接する点Pi（P1）と同一の分割ラベルを追
跡し、その連続状態の長い走査方向の端点を点Phとす
る。

連続状態がなければ、 ・ns＝３のときは、ｓをインクリメントし、ステップ
Ｉへ（次の分割輪郭線の処理へ）。

・ns＞３のときは、点Ph＝点Pi（P1）とする。

□点Pi（P1）が分割ラベル●，▲，▼でなれば、 ・ns＝３のときは、ｓをインクリメントし、ステップ
Ｉへ（次の分割輪郭線の処理へ）。

・ns＞３のときは、ｉをインクリメントし、再び、ス
テップIIへ。

ｂ）ｉ＝ns−１のとき、或いは、ｉ＜ns−１であって
も、点Pjが屈曲点座標点列Cs内の最後の点Pnsであると
き、分割ラベルパターンを参照し、 □点Pj（Pns）が分割ラベル●，▲，▼であれば、点Pj
（Pns）からＸの正方向および負方向に分割ラベルパタ
ーンを走査し、第13図に示すような、上下方向（Ｙ方
向）に白画素が隣接する点Pj（Pns）と同一の分割ラベ
ルを追跡し、その連続状態の長い走査方向の端点を点Pk
とする。

連続状態がなければ、ｓをインクリメントし、ステッ
プＩへ（次の分割輪郭線の処理へ）。

□点Pj（Pns）が分割ラベル●，▲，▼でなければ、ｓ
をインクリメントし、ステップＩへ（次の分割輪郭線の
処理へ）。

ステップIII:点Piから点Phに向かうベクトルをV1、点
Pjから点Piに向かうベクトルをV2、点Pjから点Pkに向か
うベクトルをV3として、これらの点およびベクトルが以
下の条件をすべて充たすか否かを調べる（第14図参
照）。

ｉ）（V1とV3の内積）＞Th1（但し、Th1は閾値）。

ii）V1,V3のいずれか一方がＸ軸に平行、或いは、V1,V3
のいずれか一方がＸ軸に垂直（以下、Ｘ軸に平行、或い
は、垂直なベクトルを主ベクトルと呼ぶ）。

iii）V1,V2,V3が第14図（ａ）〜（ｈ）の状態にある。

iv）点Piと点Pjとの位置関係が次のいずれかを充たす。

・|Xi−Xj|＝１で、かつ、 |Yi−Yi|＝１ ・|Xi−Xj|＝１で、かつ、 |Yi−Yj|＝２ ・|Xi−Xj|＝２で、かつ、 |Yi−Yj|＝１ ｖ）V1の長さ＞Th、或いは、V3の長さ＞Th（但し、Thは
閾値）。

vi）主ベクトルの始点から、ベクトルV1とベクトルV3の
交点に向かって１点延長した点（Xe,Ye）が、屈曲点付
フルドットパターン上で、黒画素。

□上記条件を充たす場合、以下の処理を実行する。

□上記条件を充たさない場合、ｉをインクリメントし、
再び、ステップIIへ。

ステップIV:ベクトルV1とベクトルV3との交点を求
め、点Ｍ（Xm,Ym）とする。

但し、屈曲点付フルドットパターンを参照し、主ベク
トルの始点から点Ｍに向かう延長線上の点Ｍとの間に、
屈曲点（Xb,Yb）が存在する場合は、点Ｍをその屈曲点
の座標、すなわち、（Xm,Ym）＝（Xb,Yb）とする。さら
に、点Ｍと主ベクトルの始点との距離が２以上の時、点
Ｍとして、主ベクトルの始点から点Ｍに向かって１点延
長した点の座標（Xe,Ye）を設定する。すなわち、（Xm,
Ym）＝（Xe,Ye）とする。

ステップV:座標点テーブルII13内の主ベクトルの始点
の座標格納場所に座標（Xm,Ym）を書き込む。但し、主
ベクトルが２本の場合、一方の主ベクトルの始点の座標
格納場所に座標（Xm,Ym）を書き込み、他方の主ベクト
ルの始点の座標格納場所には、消去フラグ、例えば、
“−2"を書き込む。ｓをインクリメントし、ステップＩ
へ（次の分割輪郭線の処理へ）。

以上の処理によって、座標テーブルII13に格納された
屈曲点座標点列の補正が行われ、第14図（ａ）〜（ｈ）
は同（ｉ）〜（ｐ）の如くになる。第４図（ｅ）は、第
４図（ｄ）の処理結果を示す。

輪郭ベクトル対抽出回路 最後に、輪郭ベクトル対抽出回路15は、座標点テーブ
ルII13に格納されている対検出ラベルと屈曲点座標点列
を読み出し、第15図に示すように、対検出ラベルに基づ
いて、それに続く屈曲点座標点列（分割輪郭線の輪郭ベ
クトルデータ）が、パターンの左輪郭線のものである
か、右輪郭線のものであるかに分類し、消去フラグ、例
えば、“−2"を読み跳ばしながら、座標点テーブルI11
内の左輪郭ベクトルテーブル、右輪郭ベクトルテーブル
に格納する。なお、左輪郭線、右輪郭線の分類は、一対
の対検出ラベルに着目し、最初に出現する対検出ラベル
に続く屈曲点座標点列は左輪郭線、２番目に出現する対
検出ラベルに続く屈曲点座標点列は右輪郭線のものであ
るとする（分割輪郭線の抽出処理に関連する）。

以上、詳細に説明したように、本発明は、パターンの
輪郭線を左輪郭線、右輪郭線に分類し、それらを対とし
てベクトルで表現するとともに、幾何学的変換を施して
も、原パターンとその形状が著しく変化しないように輪
郭ベクトル列を補正するので、高品質なパターンを高速
に復元／生成できる。第16図は、本発明による処理例を
示す。

〔発明の効果〕

以上詳細に説明したように本発明は、パターンの輪郭
線を左輪郭線、右輪郭線に分類し、それらを対としてベ
クトル表現するという輪郭表現形式を採り、しかも或る
角度を成す輪郭形状部分の輪郭ベクトル列を検出し、幾
何学的変換を施しても原パターンとその形状が著しく変
化しないようにその部分の輪郭ベクトル列を補正するの
で、復元／生成の際には対となる輪郭ベクトルデータを
用いて容易にラスター単位の塗り潰しのための情報を発
生できるため、イメージバッファを必要としない高速な
パターン復元／生成処理が実現できるとともに、高品質
なパターンの生成が可能である。

【図面の簡単な説明】

第１図は本発明の原理を示すブロック図、 第２図は本発明の実施例を示すブロック図、 第３図は従来方式の問題点を示す図、 第４図は本発明方式の概要を説明する図、 第５図は分割ラベルの説明図、 第６図は分割輪郭線の抽出要領を説明する図、 第７図は座標点テーブルＩの説明図、 第８図は座標点テーブルIIの説明図、 第９図は微小直角部補正における屈曲点フルドットパタ
ーンの追跡処理の説明図、 第10図は直角部補正における屈曲点フルドットパターン
の追跡処理の説明図、 第11図は微小直角部補正要領の説明図、 第12図は直角部補正要領の説明図、 第13図は微小直角部、鋭角／鈍角部補正における分割ラ
ベルパターンの追跡処理の説明図、 第14図は鋭角／鈍角部補正要領の説明図、 第15図は輪郭ベクトル対の抽出要領の説明図、 第16図は本発明による処理例を示す図である。

Claims (1)

【特許請求の範囲】
1. 【請求項１】２値ドットパターンを、対をなす複数の輪
   郭ベクトルとして表現するパターン圧縮表現方式におい
   て、 主走査方向（Ｘ）以外のパターンの輪郭線を分割して、
   走査線に対してｉ番目に出現する画像開始輪郭線と、
   （ｉ＋１）番目に出現する画像終了輪郭線の対（と
   ，……）として捉えるパターン輪郭線対抽出手段
   （２）と、 前記分割され、対として捉えられた各輪郭線をベクトル
   化するベクトル化手段（３）と、 前記ベクトルのベクトルデータから、或る角度をなす輪
   郭線部分のベクトル列を検出し、そのベクトルデータを
   補正する輪郭ベクトル補正手段（４）と、 前記輪郭線対の情報に基づき、前記輪郭線のベクトルデ
   ータを対として表現する輪郭線対ベクトル表現手段
   （５）とを備えることを特徴とするパターン圧縮表現方
   式。