JPH0139265B2 - - Google Patents

Description

【発明の詳細な説明】 本発明は、２値画像、特に電算写植用デジタル
文字母形のデータ圧縮方法に関する。

従来、電算写植用デイジタル文字母形は、通常
の漢字処理装置等における文字キヤラクタとは異
なり、１文字を表わすためのドツトマトリクス
が、非常に高密度に構成されている。

この高密度に構成された文字のビツトパターン
を、そのビツトパターン形態のままで文字母形の
データとすると、１文字の記憶に要するビツト数
が非常に多くなる。例えば、電算写植用の文字母
形としては、480×480＝230400ビツト程度の密度
が必要となる。

また、電算写植用文字母形は、通常の文字キヤ
ラクタとしての意味はもとより、その文字の書体
が重要であり、種々異なる書体が要求されるた
め、文字母形は、明朝体、ゴシツク体、その他各
書体毎の文字セツトとして用意されなければなら
ず、しかも、電算写植用文字セツトとしては、必
要とされるすべての書体の文字セツトを、常に検
索可能な状態でフアイリングされていることが望
まれる。

しかし、上述の如く、１文字のビツトパターン
をそのまま文字データとして記憶させた場合は、
文字母形フアイルに要するメモリ容量が膨大とな
る難点がある。

そこで、ビツトパターンをそのまま記憶させる
のではなく、画像伝送処理における帯域圧縮技術
により、１文字分のデータを圧縮する試みがなさ
れている。

しかし、従来公知のラン・レングス方式では、
20〜30％程度の圧縮率しか得られない。

また、ベクター方式は、数％台の高圧縮を望め
るが、従来の圧縮処理方法では、ほとんど手作業
に近い処理手段でベクターが求められているた
め、電算写植用文字母形に適用した場合、１書体
分の文字セツトを圧縮処理するだけで、多大の時
間と労力を要する。

例えば、従来のベクター方式においては、手作
業が可能な程度に拡大された文字パターンの中か
ら、文字の輪郭線を直線で近似させるベクターを
作るための各点を、デジタイザによつて、目視的
にプロツトしている。

文字パターンをベクターで表わすためには、多
数の線分を必要とし、特に曲線の多い明朝体等の
書体では、プロツトされる点の数が非常に多く、
時間と労力を要するだけではなく、点をプロツト
するのに、かなりの熟練を必要とする。

さらに、デジタイザによる点のプロツトが手作
業であるため、プロツト誤差を少なくするのに、
入力用の文字パターンをできるだけ拡大したもの
を用意しなければならず、しかも最終的には、文
字パターンの形状を整形する作業を加える必要が
ある。

本発明は、上記ベクター方式と同様な圧縮方式
に基くものであり、従来のベクター方式に比し
て、文字パターンを拡大する必要がなく、直線近
似ベクターを作成するための多数の点を目視的に
プロツトする必要もないため、プロツト誤差もな
く、非常に短時間に圧縮処理することができ、従
来のベクター方式よりさらに圧縮率の高いデータ
圧縮方法を提供するものである。

以下図面に基き、本発明の実施例を説明する。

第１図は、本発明方法に基く、２値画像のデー
タ圧縮方法の一実施例を示すためのブロツク図で
ある。

データを圧縮しようとする原画パターンは、原
画入力装置１により適宜走査されて画像信号に変
換され、その画像信号は、Ａ／Ｄ（アナログ・デ
イジタル）変換装置２を介して、デイジタル画像
信号に変換されて、２値画像メモリ装置３へ送ら
れる。

この２値画像メモリ装置３へ記憶される原画パ
ターンのデータは、第２図に示す如く、ドツトマ
トリクスのビツトパターンをもつてなり、このビ
ツトパターンをもつて表わされる原画パターン
は、被圧縮２値画像となる。

また、２値画像メモリ装置３は、マトリクス配
列された複数のメモリブロツクM₀₀〜M_ijよりな
り、その各メモリブロツクM₀₀〜M_ijは、被圧縮
２値画像（以下原画像と称する）を細分割した部
分画像のビツトパターンを記憶する。

次に、各部分画像は、各メモリブロツクM₀₀〜
M_ijから、メモリブロツクごとに順次部分画像メ
モリ装置４へ、メモリ制御装置５の制御指令によ
つて移し替えられる。

メモリ制御装置５は、両メモリ装置３，４に対
するデータの書込み、読出し、並びにアドレスを
後述するフローチヤートに従つて制御するもので
ある。

第３図は、部分画像メモリ装置４へ移し替えら
れた部分画像のビツトパターンを拡大して示すも
ので、図示のものは、第２図のメモリブロツク
M₀₃のビツトパターンに対応している。

この部分画像メモリ装置４におけるビツトパタ
ーンに基づいてスタート点・エンド点検出手段６
により、部分画像の輪郭線と、該部分画像を隣接
部分画像から区分する分割縁との交点が、輪郭線
を自動的に追跡するために必要なスタート点p^(S)
とエンド点p^(E)として検出される。

スタート点・エンド点検出手段６によつてスタ
ート点p^(S)、エンド点P^(E)が検出されると、輪郭線
追跡手段７により、そのスタート点p^(S)からエン
ド点p^(E)に至るビツトパターンの輪郭線が追跡さ
れる。

この輪郭線の追跡に伴い、特徴点検出手段８に
より、輪郭線の変化の特徴が検出され、輪郭線上
の適数の特徴点が順次抽出される。

ここで抽出された各特徴点のスタート点p^(S)か
らエンド点p^(E)に至るまでの座標値の順列を追つ
た集まりは、部分画像のビツトパターンの圧縮さ
れたデータとなる。

このようにして得られた各部分画像の圧縮デー
タは、順次に処理順に、部分画像の圧縮データを
収集する線分データメモリ装置９に書込まれる。

全メモリブロツクM₀₀〜M_ijが処理されると、
部分画像相互のデータ接続手段１０により、原画
像を分割した際に切り離された輪郭線を、対応す
るスタート点p^(S)とエンド点p^(E)を接続することに
より、単一の原画像圧縮データにまとめられ、原
画像圧縮データメモリ装置１１へ書込まれる。

原画像圧縮データメモリ装置１１に書込まれた
原画像の圧縮データは、適時に出力装置１２へ送
られ、モニタを介して圧縮データによる再生原画
パターンを表示するか、もしくは、適宜のデータ
フアイリング装置へ送られる。

上述の処理過程は、第４図にフローチヤートと
して示してある。

このフローチヤートにおいて、前記スタート
点・エンド点検出手段６における処理は、ステツ
プ（25）に相当し、この検出処理の具体例は、以
下のようになされる。

すなわち、部分画像メモリ装置４のアドレス空
間は、２値画像メモリ装置３における各メモリブ
ロツクM₀₀〜M_ijと同一に構成される。そのため、
部分画像メモリ装置４のアドレス外周縁は、部分
画像の外周縁に相当している。

そこで、第３図に示す如く、部分画像メモリ装
置４のアドレス外周縁を、原点０，０から順次反
時計廻りにアドレス指定して、ビツトパターンに
おけるアドレス外周縁の画素ビツトの変化を判別
すれば良いことになる。

なお、以下の説明において、ビツトパターンに
おける各画素ビツトは、文字領域のビツトが、１
を、他の領域のビツトが０を表わしているものと
する。

すなわち、順次反時計廻りに該ビツトパターン
におけるアドレス外周縁の画素ビツトが読み出さ
れ、その画素ビツトが、１から０へ反転するとき
の１のビツトに対応する画素をスタート点p^(S)と
し、また、０から１へ反転するときの１のビツト
に対応する画素をエンド点p^(E)とする。

また、このアドレス外周縁の画素ビツトが反転
するスタート点p^(S)及びエンド点p^(E)は、部分画像
の輪郭線と部分画像の分割縁との交点に相当す
る。

なお、ビツトパターンにおける輪郭線は、本質
的には画素の辺部に存在するものであるが、以下
の説明におけるビツトパターン上の輪郭線は、輪
郭線を少くとも一辺に含む画素もしくは画素ビツ
トの列を、輪郭線とみなすものとする。

上述の如くして検出されたスタート点p^(S)並び
にエンド点p^(E)の各座標値x_i、y_iは、適宜のレジス
タに保留され、輪郭線追跡手段７の初期値並びに
終値として、該輪郭線追跡手段７に与えられる。

輪郭線追跡手段７における処理は、第４図のフ
ローチヤートのステツプ（26）に相当している。

第５図は、輪郭線追跡手段７の追跡方法の一例
を具体的に示すもので、現在注目している画素ビ
ツトQ₁に対して、その周囲の画素ビツトを反時
計廻りに検索し、その矢印の検索ループL₁にお
いて、順次隣接する画素ビツトに書込まれた信号
が１であるか０であるかを判別し、０から１へ反
転した際の１に対応する画素ビツトを、次位の輪
郭線上の画素ビツトQ₂とする。

次に、画素ビツトQ₂を注目する画素ビツトと
して、検索ループL₂を調べ、同様に次位の画素
ビツトQ₃を得、この繰返しによつて、順次輪郭
線上の画素ビツトQ₄…を追跡する。

この輪郭線の追跡に際し、輪郭線上の画素ビツ
トQ₁，Q₂，…のうちの適数個毎の画素ビツトを
代表点として選択し、その代表点の並び方の変化
を調べることにより、輪郭線の特徴を検出し、さ
らにその代表点の中から特徴点が抽出される。

この特徴点抽出手段８による具体的抽出方法の
一例は、第８図のフローチヤートに示してある。

特徴点は、その変化の態様を分類することによ
つて、例えば４種類に分けられる。第６図は、そ
の４種類の各特徴点が得られるビツトパターンの
一例を示すものである。

第６図ａは、２値化する別の部分画像を示し、
同じくｂは、部分画像メモリ装置４に、ビツトパ
ターンで表わされた当該部分画像へ各特徴点を表
示したものである。なお同図ｂの矢印は、画素ビ
ツトの検索方向を示している。

各特徴点は、以下のように分類して定義する。

p⁽¹⁾：輪郭線の方向が急激に変化する点 p⁽²⁾：輪郭線が一方向にゆるやかに変化する点 p⁽³⁾：輪郭線が直線から曲線に変化する点 p⁽⁴⁾：輪郭線が曲線から直線に変化する点 これら特徴点の抽出は、特徴点抽出手段８によ
り、次のようにして行なわれる。

まず、輪郭線の変化を調べるに際して、輪郭線
上で接近した代表点を定める。この代表点は、輪
郭線追跡手段７によつて、スタート点p^(S)を起点
として、順次追跡される輪郭線上の画素ビツト
を、適数画素ビツトおきに摘出したもので、これ
を代表点p_iとし、その座標値p_i＝x_i、y_iを得る。

代表点摘出時の画素ビツト間隔は、所要のデー
タ圧縮率又は再現画像の忠実度等によつて適宜、
設定されるもので、例えば、その間隔を広くすれ
ばデータ圧縮率（同一原画比）は向上するが、忠
実度が低下することになり、データ圧縮率及び再
現画像の忠実度の重要性の程度に応じ、その間隔
を決定する。なお実施例においては、４ビツト間
隔をもつて、所望のデータ圧縮率と再現画像の忠
実度を得ている。

次に、スタート点p^(S)、エンド点p^(E)を除く各代
表点p_iについて、相隣接する２つの代表点p_i-1，
p_i+1で形成されるベクトル ――→ p_i-1p_iと、 ―――→ p_ip_i+1 のなす角度θ_iを求める（第７図参照）。

この角度θ_iから、次のような判別法により、各
特徴点p⁽¹⁾，p⁽²⁾，p⁽³⁾，p⁽⁴⁾を決定することができ
る。

(1) 特徴点p⁽¹⁾（輪郭線の方向が急激に変化する
点） ベクトルのなす角θ_iが、所定の角度θ⁽¹⁾を越え
たときの代表点p_i。

｜θ_i｜＞θ⁽¹⁾ θ⁽¹⁾は定数として設定される（例えば30゜） (2) 特徴点p⁽²⁾（輪郭線が一方向にゆるやかに変化
する点） 或る代表点p_nから或る代表点p_oに至るまでの
各ベクトルのなす角θ_iの総和が、角度定数
（θ⁽¹⁾）を超えるときの代表点p_o。

｜_o 〓^i=m θ_i｜＞θ⁽¹⁾ ここで、和の開始点となる代表点p_nは、ス
タート点又は直前にとられた特徴点p⁽¹⁾又はp⁽²⁾
とする。ただし、これらの点以降に変曲点（輪
郭線の曲る方向を示す符号＋，−が変化する点）
が現たれた場合、その変曲点を和の開始点p_n
とする。

(3) 特徴点p⁽³⁾（輪郭線が直線から曲線に変化する
点） 直線とみなせる複数個の代表点p_n〜p_oが例え
ば３回以上続き、次の代表点p_o+0が、特徴点
p⁽¹⁾と判定されなかつたときに、特徴点p⁽²⁾の条
件を満す代表点p_o+1。

｜_o 〓^i=m θ_i｜＜θ⁽²⁾ ｎ−ｍ≧３ θ⁽¹⁾＞｜_o+1 〓^i=m θ_i｜＞θ⁽²⁾ ここで角度定数θ⁽²⁾は、輪郭線が直線である
ことを判定するための定数で、代表点p_iが直線
から１ビツト外れたときの角度θ⁽²⁾で与えられ
る。すなわち、 θ⁽²⁾＝tan^-1（１／代表点間隔）＝tan^-11/4＝14゜ (4) 特徴点p⁽⁴⁾（輪郭線が曲線から直線に変化する
点） 或る代表点p_nから或る代表点p_oに至るまで
に、代表点の曲り方向が、同一方向へ例えば２
回以上続き、かつ、その後、直線とみなせる代
表点が、例えば２回続いたときの代表点p_o。

｜_o 〓^i=m sgn（θ_i）｜≧２かつ、 sgn（θ_o-1）・sgn（θ_o）≦０ ここで、sgn（θ_i）は、角度θ_iの符号＋，０，−
に、その符号の数を計数するための単位１を与
えて、曲り方向、例えば、反時計廻り、直進、
時計廻りの３値コードを示したものである。

sgn（θ_i）＝ １ （θ_i＞０のとき） ０ （θ_i＝０のとき） −１ （θ_i＜０のとき） 第８図は、上記判別条件に基いて特徴点p⁽¹⁾〜
p⁽⁴⁾を、抽出手段８により抽出する具体的方法の
一例を示すフローチヤートである。

なお、同図のフローチヤート中の記号の意味
は、次の通りである。

θ_i：現在注目している代表点p_iと、その前後の
代表点p_i-1，p_i+1とにより作られる２つのベクト
ル ――→ p_i-1p_i、 ―――→ p_ip_i+1 のなす角度∠p_i-1p_ip_i+1 Σ⁽¹⁾θ_i：直前に抽出された特徴点から、現在注
目している代表点に至るまでの各代表点に
おける角度θ_iの和を納めるカウンタ Σ⁽²⁾θ_i：直前に判別された変曲点から、現在注
目する代表点に至るまでの各代表点におけ
る角度θ_iの和を納めるカウンタ sgnθ_i：現在注目している代表点における曲り
方向の３値コード 反時計廻り＝１、前進＝０、時計廻り＝−
１ Σsgnθ_i：直前に抽出された特徴点から、現在注
目する代表点に至るまでの曲り方向の３値
コードの和を納めるカウンタ STRGHT：直前に抽出された特徴点から、現
在注目する代表点に至るまでが、θ_i＜θ⁽²⁾に
より判別される直線であることを示すカウ
ンタ θ⁽¹⁾：曲線を判定するための判定角度 θ⁽²⁾：直線を判定するための判定角度 このようにして、各特徴点p⁽¹⁾〜p⁽⁴⁾は、スター
ト点p^(S)から輪郭線の追跡順に抽出され、その特
徴点p⁽¹⁾〜p⁽⁴⁾の座標値x_i、y_iの組み合せが、部分
画像の圧縮データとして、線分データメモリ装置
９へ書込まれる。

なお、線分データメモリ装置における各点の座
標値は、メモリブロツクM₀₀〜M_ijのブロツク番
号（00）〜（ij）に基き、元のビツトパターンの
座標値に変換しておく。

すなわち、線分データメモリ装置９には、各メ
モリブロツクM₀₀〜M_ijごとに、各特徴点p⁽¹⁾〜p⁽⁴⁾
と、その前後のスタート点p^(S)、エンド点p^(E)の座
標値が、圧縮データとして、通常、スタート点
p^(S)、特徴点p⁽¹⁾〜p⁽⁴⁾、エンド点p^(E)の順に書込ま
れる。

全メモリブロツクM₀₀〜M_ijの各圧縮データが
集まると、その各部分画像の圧縮データは、次
に、部分画像として分離された各輪郭線の対応す
るスタート点p^(S)とエンド点p^(E)とが、部分画像相
互のデータ接続手段１０により接続される。

すなわち、各線分データメモリ装置９には、原
画のビツトパターンを分離した部分画像に対応す
る各線分データが、それぞれ、スタート点p^(S)と
エンド点p^(E)を各線分データの両端のデータとす
べく書込まれることになる。

したがつて、原画全体の輪郭線は、各線分デー
タの対応するスタート点p^(S)とエンド点p^(E)を結ぶ
ことにより、連続させることができる。

また原画パターン並びにそのビツトパターンの
輪郭線は、第２図にその一例を示す如く、それぞ
れ、閉ループをなしている。

この輪郭線の閉ループにおいて、輪郭線追跡方
向が、反時計廻りとなるときは、そのループ（輪
郭線）内は黒（文字部）、また時計廻りのときは、
ループ（輪郭線）内が白となり、かつ、ループが
多重する場合は、内のループが優先する。

しかして、原画のビツトパターンは、各輪郭線
上一方向へ並べられた特徴点の座標値の集まりと
して、データが圧縮される。

以上の如く、本発明によれば、文字パターンの
データ圧縮が、短時間にかつ、正確に、しかも精
密に、人手の必要性を大幅に減少させて行なうこ
とができる。

従つて、電算写植用文字セツト等の２値画像の
フアイリングを容易とするとともに、データ圧縮
が大幅に行なえ、フアイリングに要するメモリ容
量を、大幅に減少させることができる。

【図面の簡単な説明】

図は、本発明方法の一実施例を示すもので、第
１図は、本発明方法によるデータ圧縮装置のブロ
ツク図、第２図は、被圧縮画像の１例を示すメモ
リ装置上のビツトパターンの図、第３図は、第２
図のビツトパターンの部分画像の１つを、他のメ
モリ装置へ移し替えたビツトパターンの図、第４
図は、第１図のデータ圧縮装置のフローチヤー
ト、第５図は、第１図における輪郭線追跡手段の
制御要領を示すビツトパターンの輪郭線の拡大
図、第６図は、各種の特徴点を有する画像と、そ
のメモリ装置上のビツトパターンの図、第７図
は、第１図の特徴点抽出手段における注目する代
表点と、その前後の代表点の関係を示すビツトパ
ターンの輪郭線の拡大図、第８図は、第４図にお
けるステツプ（26）の詳細なフローチヤートを示
すものである。 １……原画入力装置、２……Ａ／Ｄ変換装置、
３……２値画像メモリ装置、４……部分画像メモ
リ装置、５……メモリ制御装置、６……スター
ト・エンド検出手段、７……輪郭線追跡手段、８
……特徴点抽出手段、９……線分データメモリ装
置、１０……データ接続手段、１１……２値画像
圧縮データメモリ装置、１２……出力装置、M₀₀
〜M_ij……メモリブロツク、p^(S)……スタート点、
p^(E)……エンド点、Q₁〜Q₂……画素ビツト、L₁〜
L₄……検索ループ、p_i……代表点、p⁽¹⁾〜p⁽⁴⁾……
特徴点。

Claims (1)

1. 【特許請求の範囲】 １ 原画像を細分割して複数個の部分画像とし、
   各部分画像のそれぞれについて、順次、部分画像
   の輪郭線と当該部分画像を区分する分割線との交
   点を検索し、それら交点を始点および終点として
   輪郭線を追跡して特徴点を検出し、それら始点、
   特徴点、終点をその部分画像の輪郭線データと
   し、隣接する各部分画像の上記始点と終点を接続
   することにより、隣接する部分画像を接続するこ
   とを特徴とする２値画像のデータ圧縮方法。 ２ 輪郭線の特徴点を検出するに際して、該輪郭
   線の始点および終点、並びに当該輪郭線上に所要
   の間隔で設定された代表点のうち、隣接する各点
   で形成される各ベクトルの方向、および各ベクト
   ルが直前のベクトルとなす角度に基づいて検出す
   ることを特徴とする特許請求の範囲第１項に記載
   の２値画像のデータ圧縮方法。