JPH04298162A - 近隣ブロック予測ビット圧縮法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データフィールドのビ
ットマップ記述を圧縮して記憶装置に効率良く格納する
アルゴリズムに関し、更に詳細には、これらアルゴリズ
ムを、日本語、中国語、ヘブライ語、アラビア語、タミ
ル語、及びペルシア語のような表意文字言語に使用され
る文字記号を効率良く記述するアルゴリズムに関する。

【０００２】

【従来の技術及びその課題】本文、図式、及び他の情報
表現に適用可能なデータ圧縮方法は、音声、ビデオ、テ
レメータ通信、及び大容量データの格納及び検索のよう
な、通信の多くの分野で使用されている。開発された方
法の中で、適応圧縮は、データの冗長性を減らすことに
よりデータに対する帯域幅利用効率を増すことができる
能力があるため、最も魅力的なものの一つである。シー
・エイ・アンドリュース（Ｃ．Ａ．　Ａｎｄｒｅｗｓ）
、他は「Ａｄａｐｔｉｖｅ　Ｄａｔａ　Ｃｏｍｐｒｅｓ
ｓｉｏｎ（適応データ圧縮）」、Ｐｒｏｃ．ＩＥＥＥ，
　ｖｏｌ．５５　（１９６７），　ｐｐ２６７〜２７７
　においてデータ圧縮方法を４つの部類に分類できるこ
とを記している。「（１）　直接データ圧縮法であって
、補間法、多項式予測法及びビットプラン符号化のよう
な可変速圧縮法、及び最適予測、差動符号化、確率符号
化、及び適応サンプリングのような固定速圧縮法がある
。（２）　予備処理フィルタ、対数増幅器、フィルタ、
リミッタ／クリッパ、コンパンダ、フーリエフィルタ、
カルーネン／レーヴェ（Ｋａｒｈｕｎｅｎ−Ｌｏｅｖｅ
）最適個別圧縮フィルタを使用する線形及び非線形の変
換圧縮法。（３）　パラメータ抽出圧縮法であって、信
号に関連する、又は信号から得られた、１つ以上のパラ
メータを使用して信号を表す。及び（４）　データを監
視し、その一部を選択して伝達又は格納する選択監視圧
縮法。　　中国語、日本語、及びヘブライ語のような言
語からの表意文字又は記号の集まりを効率良く表現し且
つ格納することは、どんな適度の言語集合でも多数の文
字を必要とするので、ここでは特に興味がある。例えば
、中国語の文字パターンの方式では、その言語の通常の
教科書に現れる文字の少なくとも９９．５％を適格に表
すために２５００〜４０００文字を備えるべきである。 中国文字は日本でも使用されているが、文字の総数は、
不定である。例えば、日本の文部省は、小学校及び中学
校で８８１文字を学習するよう区別しており、別に通常
の日常使用に知っているべき９６９文字を区別している
。日本の日刊紙は、約４０００文字を使用しており、こ
のような文字に対する一つの標準符号体系は、６３４９
文字を備えている。他の標準の日本語の文字セットには
６８０２文字が現れる。日本における中国文字（漢字）
の最も精巧な辞書は、約５００００文字を備えている。 文字の使用に関して蓄積した統計によれば、所定組み合
わせの約３０００文字が、日本の新聞及び雑誌に現れる
すべての文字の約９９．９％を網羅している。 この少ない方の数まで退いたとしても、各々がＭドット
×Ｎドットの方形パターンにより記述される、このよう
な大きなセットを表現するという任務は、威圧を感ずる
。代わりに、多数の専門職業文字及び学術的文字を含む
６３４９文字又は６８０２文字から成るもっと大きな、
もっと適格なセットに注力すれば、任務は更に威圧を受
けることになる。

【０００３】クレーン（Ｃｒａｎｅ）他は、米国特許第
４，７１８，１０２号で、漢字のような複雑な文字の構
成を、画素の所定の観察パターンに適合する可能なすべ
ての文字から成る第１のセットを区別するのに役立つア
ルゴリズム法に、及び目標文字に関連する別の特徴又は
パラメータを使用することにより第１のセットのすべて
の文字の中のあいまいさ又は可能な混乱を取り除くこと
に役立つ脱不明瞭法に、分離することを開示している。 本発明人は、統計的に、２０を超える画数又は５より少
ない画数を有する漢字、約１０画の漢字と比較して、区
別するのがはるかに容易であることに気付いた。画数の
特性は、ここでのパターン認識のアルゴリズム部分につ
いて、統計の種々な部類に関する統計が蓄積され、分析
されれば、頼りになる。

【０００４】光学的文字認識の目的で画素を取り巻く又
は画素に隣接する画素隣接を使用することは、ケイセイ
（Ｃａｓｅｙ）他が米国特許第４，８３１，６５７号で
開示している。新しいフォントで表されている文字を認
識するため、既知フォントで表された文字に関連する確
率に基づいて、確率表が作られている。判断ツリーが作
られ、新しいフォントを分析するのに使用されている。 この方法には、新しいフォントで表された文字を認識す
るのに、基準フォント又は同様なものが必要である。　
　米国特許第４，８５０，０２６号で、ジェング（Ｊｅ
ｎｇ）他は、所定フォントで表された一組の文字の有用
なすべての特徴を、文字特徴データベースとして抽出す
ることを開示している。ここで説明されている特定のデ
ータベースの特徴は、画面上のすべての画素を累積的に
網羅する画素の各一系列の長方形群の中の垂直、水平、
及び対角線方向の文字の字画である。

【０００５】中国又は日本の文字パターンのデータ圧縮
について幾つかの手法が提案されている。エム・ナガオ
（Ｍ．　Ｎａｇａｏ）は、「Ｄａｔａ　Ｃｏｍｐｒｅｓ
ｓｉｏｎ　ｏｆ　Ｃｈｉｎｅｓｅ　Ｃｈａｒａｃｔｅｒ
　Ｐａｔｔｅｒｎｓ（漢字パターンのデータ圧縮）」、
Ｐｒｏｃ．　ＩＥＥＥ．　ｖｏｌ．６８（１９８０），
　ｐｐ．８１８〜８２９　で、このような圧縮について
提案された幾つかの手法を、パターンの統計及び他の方
法を使用して検討している。二次元予測符号化法が提案
されているが、この方法では、文字パターンを一連の長
方形画素に分割し、特定の画素の黒対白の値を最も近い
４個の近隣画素のパターンを使用して予測する。ｍ×ｎ
個の部分ブロックによるパターン符号化も使用されてい
るが、これは漢字が主として直線であるという事実に頼
っている。他の手法には、字画が網目格子上の垂直、水
平、及び±４５°の字画で表された直線部分である字画
表現法がある。輪郭符号化法は、漢字の或る部分が直線
部分ではなく、むしろ曲線状であるという事実を考慮に
入れるのに使用されてきた。隣接する４個の周囲点の重
味付け総和は、画素予測に同様に使用されている。

【０００６】「Ｍａｃｈｉｎｅ　Ｒｅｃｏｇｎｉｔｉｏ
ｎ　ｏｆ　Ｐｒｉｎｔｅｄ　Ｃｈｉｎｅｓｅ　Ｃｈａｒ
ａｃｔｅｒｓ　Ｖｉａ　Ｔｒａｎｓｆｏｒｍａｔｉｏｎ
Ａｌｇｏｒｉｔｈｍ（印刷漢字の変換アルゴリズムによ
る機械認識）」、Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉ
ｏｎ，　ｖｏｌ．５（１９７３），　ｐｐ．３０３〜３
２１　で、ウォン（Ｗａｎｇ）とシャウ（Ｓｈｉａｕ）
は、漢字の左側（偏）に６３個の、その右側（旁）に不
特定数の、合体して文字全体を構成する、部分パターン
を区別している。彼らの汎用パターン認識装置は、（１
）　画素の長方形マトリックスとして受け取った各漢字
を表すレセプタモジュール、（２）　フーリエ、ハダマ
ール、ラピッド、又は他の二次元変換法を使用して文字
を一層認識しやすく且つ処理しやすい形に変換するプリ
プロセッサモジュール、（３）　各画素パターンを検査
してこれを基準文字又は特徴の中間までの最小距離（ｍ
ｉｎｉｍｕｍ−ｄｉｓｔａｎｃｅ−ｔｏ−ｍｅａｎ）の
ような判断規則に基づいて多数の部類の一つに割り当て
る分類器モジュール、及び（４）　分類した各文字を後
の検索のため格納する記憶モジュールを備えている。分
類段階で幾らかの情報が失われるように思われ、また文
字が基準文字の部類の一つに強制的にはめ込まれて文字
が正しく認識されず、正しく分類されないことがある。

【０００７】ヤマモト（Ｙａｍａｍｏｔｏ）とモリ（Ｍ
ｏｒｉ）は、「Ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆ　Ｈａｎ
ｄ−ｐｒｉｎｔｅｄ　Ｃｈａｒａｃｔｅｒｓ　Ｂｙ　Ａ
ｎ　Ｏｕｔｅｒｍｏｓｔ　Ｐｏｉｎｔ　Ｍｅｔｈｏｄ（
最外側点法による手書き文字の認識）」、Ｐａｔｔｅｒ
ｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，　ｖｏｌ．１２（１９８
０），　ｐｐ．２２９　〜２３６　で、各画素が１６レ
ベルの暗さのどれかを有する、６４×６４画素パターン
を使用し、検査した各文字の凸状外皮を構成した。一つ
以上の明るい画素を完全に取り囲む複数の暗い画素から
生ずる穴を別々に処理する。各文字の凸状外皮をマスク
として表し、マスクの集まりが文字認識用辞書を形成す
る。

【０００８】エフ・エイチ・チェン（Ｆ−Ｈ．　Ｃｈｅ
ｎｇ）他は、「Ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆ　Ｈａｎ
ｄ　ＷｒｉｔｔｅｎＣｈｉｎｅｓｅ　Ｃｈａｒａｃｔｅ
ｒｓ　ｂｙ　Ｍｏｄｉｆｉｅｄ　Ｈｏｕｇｈ　Ｔｒａｎ
ｓｆｏｒｍＴｅｃｈｎｉｑｕｅｓ　（修正ホック変換法
による手書き漢字の認識）」、ＩＥＥＥ．　Ｔｒａｎｓ
．　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ
Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，　ｖｏｌ
．１１（１９８９），　ｐｐ．４２９　〜４３９　で、
修正ホック変換法に加えて動的プログラミングを使用し
、手書き漢字の特徴を求め、認識している。ホック変換
法では、直線部分に載っているすべての点をホック変換
空間内の一つの点に写像する新しい二次元座標空間を発
生する。ホック変換法はまた、エム・クシニール（Ｍ．
Ｋｕｓｈｎｉｒ）他により、「Ａｎ　Ａｐｐｌｉｃａｔ
ｉｏｎ　ｏｆ　ｔｈｅＨｏｕｇｈ　ｔｒａｎｓｆｏｒｍ
　ｔｏｔｈｅ　Ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆ　Ｐｒｉ
ｎｔｅｄ　Ｈｅｂｒｅｗ　Ｃｈａｒａｃｔｅｒｓ　（ホ
ック変換の印刷ヘブライ文字の認識への応用）」、Ｐａ
ｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，　ｖｏｌ．１６
（１９８３），　ｐｐ．１８３　〜１９１で、及び「Ｒ
ｅｃｏｇｎｉｔｉｏｎ　ｏｆ　Ｈａｎｄ　Ｐｒｉｎｔｅ
ｄ　Ｈｅｂｒｅｗ　Ｃｈａｒａｃｔｅｒｓ　Ｕｓｉｎｇ
　Ｆｅａｔｕｒｅｓ　Ｓｅｌｅｃｔｅｄ　ｉｎ　ｔｈｅ
　Ｈｏｕｇｈ　Ｔｒａｎｓｆｏｒｍ　Ｓｐａｃｅ（ホッ
ク変換空間で選択された特徴を使用する手書きヘブライ
文字の認識）」、ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏ
ｎ，　ｖｏｌ．１８（１９８５），　ｐｐ．１０３　〜
１１４　で、印刷及び手書きヘブライ文字に応用された
。

【０００９】シロモニー（Ｓｉｒｏｍｏｎｅｙ）他は、
「Ｃｏｍｐｕｔｅｒ　Ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆ　
Ｐｒｉｎｔｅｄ　Ｔａｍｉｌ　Ｃｈａｒａｃｔｅｒｓ（
印刷タミル文字のコンピュータ認識）」、Ｐａｔｔｅｒ
ｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，　ｖｏｌ．１０（１９７
９），　ｐｐ．２４３　〜２４７　で、ランレングス符
号化法をディジタル化した文字の各線に適用してタミル
文字を認識し、区別している。

【００１０】チヌスワミー（Ｃｈｉｎｎｕｓｗａｍｙ）
他は、「Ｒｅｃｏｇｎｉｔｉｏｎ　ｏｆ　Ｈａｎｄ−ｐ
ｒｉｎｔｅｄ　Ｔａｍｉｌ　Ｃｈａｒａｃｔｅｒｓ（手
書きタミル文字の認識）」、Ｐａｔｔｅｒｎ　Ｒｅｃｏ
ｇｎｉｔｉｏｎ，　ｖｏｌ．１２（１９８０），　ｐｐ
．１４１　〜１５２　で、タミル文字を構成している直
線部分及び曲線部分に字画特性化法を適用し、文字認識
に相関係数の計算値を使用している。

【００１１】「Ａｕｔｏｍａｔｉｃ　Ｒｅｃｏｇｎｉｔ
ｉｏｎ　ｏｆ　Ｆａｒｓｉ　Ｔｅｘｔｓ（ペルシア文の
自動認識）」、Ｐａｔｔｅｍ　Ｒｅｃｏｇｎｉｔｉｏｎ
，　ｖｏｌ．１４（１９８２），　ｐｐ．３９５〜４０
３　で、パルハミ（Ｐａｒｈａｍｉ）他は、ペルシア文
の認識の五つの困難を説明し、ペルシア文字と文の認識
に、ディジタル化、線分離、部分語及び文字分離、及び
幾何学的特徴づけを組み合わせた方法を開示している。

【００１２】「Ｃｏｍｐｕｔｅｒ　Ｒｅｃｏｇｎｉｔｉ
ｏｎ　ｏｆ　Ａｒａｂｉｃ　Ｃｕｒｓｉｖｅ　Ｓｃｒｉ
ｐｔｓ（アラビア草書体のコンピュータ認識）」、Ｐａ
ｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，　ｖｏｌ．２１
（１９８８），　ｐｐ．２９３　〜３０２　で、エル・
シェイク（Ｅｌ−Ｓｈｅｉｋｈ）他は、個々の文字を得
るのに語の分割を行い、各アラビア文字の記述子を得る
のに短縮フーリエ解析を使用している。

【００１３】ヤープ（Ｙｈａｐ）他は、漢字の認識につ
いて７２個の構成形状又は字画組み合わせの使用を、「
Ａｎ　Ｏｎ−ｌｉｎｅ　Ｃｈｉｎｅｓｅ　Ｃｈａｒａｃ
ｔｅｒ　Ｒｅｃｏｇｎｉｔｉｏｎ　Ｓｙｓｔｅｍ（オン
ライン漢字認識装置）」、ＩＢＭ　Ｊｏｕｒ．　Ｒｅｓ
．　Ｄｅｖｅｌｏｐ，　ｖｏｌ．２５（１９８１），　
ｐｐ．１８７〜１９５　で開示している。この方法で約
２２００文字を認識することができるが、必ずしもすべ
ての文字をこの構成形状単独で記述することはできない
。

【００１４】スピヴェイ（Ｓｐｉｖｅｙ）は「Ｄａｔａ
　Ｃｏｍｐｒｅｓｓｉｏｎ　Ｔｅｃｈｎｉｑｕｅ　ｆｏ
ｒ　ＡＰＡ　Ｐｒｉｎｔｅｒ（Ｃｈａｎｇ　Ｂｌｏｃｋ
　Ｓｋｉｐｐｉｎｇ）（ＡＰＡプリンタ用データ圧縮法
（変化ブロック飛越し）」、ＩＢＭ　Ｔｅｃｈ．　Ｄｉ
ｓｃｌｏｓ．　Ｂｕｌｌ．　ｖｏｌ．２（１９８１），
　ｐｐ．５４６４　〜５４６７で、映像を表す画素の各
走査線を先行走査線と比較し、４個又は８個の連続画素
の各対応するグループ内の変化（もしあれば）だけに注
目している。スピヴェイ（Ｓｐｉｖｅｙ）により示され
た例で達成し得る正味の圧縮は、漢字のような複雑な形
状に適用するときは、恐らく消えてなくなるであろう。 前掲のスピヴェイ（Ｓｐｉｖｅｙ）の論文のｐｐ．５４
６８〜５４７０でも変化ブロック飛越し法の応用を論じ
ている。

【００１５】ケー・トライチ（Ｋ．Ｔｏｒａｉｃｈｉ）
他は、手書きのコンピュータ認識及び人間の作品で発表
され、１９８８年ワールド・サイエンティフィック・パ
ブリッシング・コーポレーション（Ｗｏｒｌｄ　Ｓｃｉ
ｅｎｔｉｆｉｃ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏ．）のア
ール・プラモンドン（Ｒ．　Ｐｌａｍｏｎｄｏｎ）他に
より編集されたｐｐ．１３１〜１４８　の「Ｈａｎｄｐ
ｒｉｎｔｅｄ　ＣｈｉｎｅｓｅＣｈａｒａｃｔｅｒ　Ｄ
ａｔａｂａｓｅ（手書き漢字データベース）」で、手書
き漢字の約４８０００字を分析し、４０００字ずつの１
２の組に分け、各部類の統計的輪郭（接続構成要素、「
穴」、外郭などの数）を決定した。彼らはまた各部分の
、そこで定義されている、「水平方向の複雑度」、及び
「垂直方向の複雑度」、及び外郭の勾配を求めた。多数
のデータが提示されたが、統計パラメータの幾つかの意
味は明らかにされていない。

【００１６】文字認識及び符号化の走査志向的方法は、
元の文字を、例えば１線１線、水平又は垂直の方向に、
文字とは無関係の所定の径路で走査する。これらの方法
は実行が最も容易で且つ費用が最も少ないが、しばしば
適度なデータ圧縮しか生じない。フィッチ（Ｆｉｔｃｈ
）とスピヴェイ（Ｓｐｉｖｅｙ）とは、「Ｆｏｎｔ　Ｄ
ａｔａ　Ｒｅｄｕｃｔｉｏｎ　ｂｙ　Ｓｃａｎ　Ｃｏｍ
ｐｒｅｓｓｉｏｎ　ｆｏｒ　Ｉｎｋ　Ｊｅｔ　Ｐｒｉｎ
ｔｅｒｓ（インクジェットプリンタのための走査圧縮に
よるフォントデータの縮小）」、ＩＢＭ　Ｔｅｃｈｎｉ
ｃａｌ　Ｄｉｓｃｌｏｓｕｒｅ　Ｂｕｌｌｅｔｉｎ，　
ｖｏｌ．２３（１９８１），　ｐｐ．５４７１〜５４７
２で、ランレングス符号化機構、変化ブロック飛越し法
の使用を開示しており、この方法では画素値の変化する
（暗から明へ、又は明から暗へ）位置だけが符号化され
る。「Ｃｏｍｐｒｅｓｓｉｏｎ／Ｄｅｃｏｍｐｒｅｓｓ
ｉｏｎ　ｏｆ　Ｆｏｎｔ　Ｐａｔｔｅｒｎｓ（フォント
パターンの圧縮／回復）」、ＩＢＭ　Ｔｅｃｈｎｉｃａ
ｌ　Ｄｉｓｃｌｏｓｕｒｅ　Ｂｕｌｌｅｔｉｎ，　ｖｏ
ｌ．２８（１９８６），　ｐｐ．３５６３〜３５６４（
著者不明）では、すべての明画素の連続走査線を一つの
数で表し、中に一つ以上の暗画素を有する走査線だけを
完全に詳細なビットパターンで表している。これらの各
方法は、文字を表すのに必要なビットマップ情報の量の
適度の縮小を達成している。 しかし、上に記したように、純粋の走査志向の方法は、
漢字又はヘブライ文字で書かれたもののような複雑な文
字に適用するときは縮小が行われないことがある。

【００１７】水平、垂直、及び斜めの字画は、スギタ（
Ｓｕｇｉｔａ）他が漢字の認識及び符号化について「Ｍ
ｕｌｔｉ−ｆｏｎｔ　Ｋａｎｊｉ　Ｇｅｎｅｒａｔｏｒ
（マルチフォント漢字発生器）」、Ｔｒａｎｓ．　Ｉ．
Ｅ．Ｃ．Ｅ．，　ｖｏｌ．Ｅ６６（１９８３），　ｐｐ
．３７７〜３８２　で使用している。線分の二つの画素
端点を指定し、中間（暗）画素を補間により求める。こ
れは、どんな方向の及びすべての方向の走査線を使用す
る一次元走査志法の変形である。例えば、使用するフォ
ントの周知の明朝フォントから他の型への変更は、補間
規則を変更することにより実施される。

【００１８】メーダー（Ｍａｅｄｅｒ）は「Ｌｏｃａｌ
　Ｂｌｏｃｋ　Ｐａｔｔｅｒｎ　Ｍｅｔｈｏｄｓ　ｆｏ
ｒ　Ｂｉｎａｒｙ　Ｉｍａｇｅ　Ｅｎｃｏｄｉｎｇ（二
進映像符号化のローカルブロックパターン法）」、Ｐｒ
ｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ１９８８　Ａｕｇｓ
ｇｒａｐｈ　Ｃｏｎｆｅｒｅｎｃｅで、近隣拡張法の使
用を開示しているが、この方法では、この論文では部分
的にしか挙げられていない類似行又は類似列の拡張規則
の集まりを使用して、明及び暗の画素近隣の集まりの各
々を一度に１行又は１線拡張する。複雑な漢字に適用す
ると、この方法は、互いに類似性が少ないか又は全く無
い多数の小さな近隣画素を作り出すようである。しかし
、この方法は、文字認識及び符号化において二次元類似
性を開拓しようとしている。

【００１９】これら多数の手法は、文字セット中の各文
字を表すのに、複雑で、余分な線分を含み、美学的に楽
しくないか、又は記憶装置に格納するのに必要な情報の
縮小を比較的わずかしか行わない。必要なのは、文字セ
ット中の各文字を正確に表すのに必要な情報を３０〜７
０パーセント縮小し、圧縮を復元したとき、元の映像の
各文字を表すのに使用されていると同じ量の分解能を生
ずる方法である。

【００２０】

【課題を解決するための手段】これらの必要性は、画素
のブロックで表される文字又は記号を記述するデータ圧
縮の方法であって、ブロックを各々、所定の大きさＪ画
素×Ｋ画素の複数の相互に排他的な長方形の部分ブロッ
クに分解し、部分ブロックに、ブロックの一隅から始め
、連続的に１行１行又は１列１行進んで連続的にｓ＝１
、２、・・・、Ｓと番号を付ける方法により満たされる
。各部分ブロックもまた、独特の二次元行列座標（Ｊ、
Ｋ）（ｊ＝１、２、・・・、Ｊ；ｋ＝１、２、・・・、
Ｋ）で表す。但し、所定の隅を含む行（座標ｍ）は、座
標（１、１）、（２、１）、・・・、（Ｊ、１）を有す
る部分ブロックを備えており、所定の隅を含む列（座標
ｎ）は、座標（１、１）、（１、２）、・・・、（１、
Ｋ）を有する部分ブロックを備えている。正確な画素構
成を、（ｍ、ｎ）＝（１、１）、（２、１）、・・・、
（Ｊ、１）、（１、２）、（１、３）、・・・、（１、
Ｋ）と番号の付いた各部分ブロックについて最初に決定
し、この情報を使用して所定の文字を表すブロックを作
っている他の各部分ブロックに対する画素構成を予測す
る。

【００２１】ｊ≧２、ｋ≧１又はｊ≧１、ｋ≧２として
（ｊ、ｋ）と番号の付いた各画素部分ブロックについて
、画素ブロック内のすべての部分ブロックについて隣接
画素の各別々のパターンの「統計的輪郭」を使用して、
（ｊ−１、ｋ−１）、（ｊ、ｋ−１）及び（ｊ−１、ｋ
）の番号を有する部分ブロック内の一定の「隣接画素」
の画素値を決定する。部分ブロックにも連続的にｓ＝１
、２、・・・、Ｓの番号を付ける。隣接画素の統計的輪
郭を使用して、そのブロック内の画素のｒ番目の最も確
からしいパターンをｒ＝１、２、・・・、Ｒ−１に対し
て求める。ここでＲは２以上の所定の整数である。ｓと
番号の付いた部分ブロックに対するｒ番目に最も確から
しいパターンの選択に対応する指標ａｒｓをその部分ブ
ロックに割り当てる。ｓ＝１、２、・・・、Ｓの番号の
付いた各部分ブロックに対して、指標ａｒｓ（ｒ＝１、
２、・・・、Ｒ−１）に対応するＲ−１個の画素パター
ンの一つが正しい画素パターンであれば、部分ブロック
ｓに対する正しいパターンに対応する指標ａｒｓをその
部分ブロックに関連づける。その他の場合には、部分ブ
ロックｓの正確なパターンに対応する、又は「指す」フ
ラグ又は指標ａＲＳを設ける。最後に、ｓ＝１、２、・
・・、Ｓの番号を有する各部分ブロックを数（ｓ，ａｒ
ｓ）　の順序対として、割り当てられた指標ａｒｓ（ｒ
＝１、２、・・・、Ｒ−１又はＲ）に関連づける。これ
ら数字対の集まりは、圧縮により元の表現で利用可能な
ものと同じ分解能で文字を正確に再現するような仕方で
データを圧縮する方法を提供する。圧縮復元のプロセス
は、指標ａｒｓに対応する画素パターンを画素ブロック
内の各部分ブロックに対する番号ｓの部分ブロックに割
り当て、画素パターンの部分ブロックを適切な順序で組
み立てることから成る。

【００２２】元のデータフィールドを記述するのに必要
な情報（ビットの数）の百分率圧縮又は縮小は、３０〜
７０パーセントである。すなわち、漢字パターンを表す
のに必要な情報は、平均して、その文字を直接ビットマ
ップ法で表すのに必要なビットマップ情報の３０〜７０
パーセントである。

【００２３】

【実施例】図１（Ａ）を参照すると、参照に便利のため
１１と記してある、４ビット×２ビットの部分ブロック
による画素パターン又は構成を、部分ブロック１１の左
上隅の近く及びこの部分ブロックの外側にある１、２、
・・・、８と番号の付いた８個の画素で示した画素パタ
ーンを使用して予測しようとする一つの好適な近隣予測
法の構成が示されている。代わりに、番号１の画素を図
１（Ａ）の番号１’の画素で置き換えることができる。 図１で１、２、３、・・・、８（又は１’、２、３、・
・・、８）の番号の付いた画素をここでは「隣接画素」
と言い、これは部分ブロック１１の正しい画素パターン
又は構成を予測するのに使用される。隣接画素は、当該
部分ブロック１１の近隣画素を形成し、関連する近隣値
は、

【００２４】

【数１】

【００２５】で与えられる。ここで各数値係数Ｃｈは、
番号ｈの隣接画素が暗い、すなわち「オン」であれば、
１に等しく、その隣接画素が明るい、すなわち「オフ」
であれば、０に等しい。近隣値数ＮＶには２８　＝２５
６個の数値、すなわち数０、１、２、３、・・・、２５
５があり、このような各和ＮＶは、使用する隣接画素構
成に対して明画素及び暗画素から成る画素パターンを一
義的に指定する。図１（Ａ）で１と記した隣接画素を１
’と記した隣接画素で置き換えれば、近隣値ＮＶは類似
して規定される。

【００２６】これは、図２に示す日本語の漢字のような
文字又は他の表意記号が図示したような画素の長方形ア
レイに分解され、画素のアレイが更に図示のように幅４
画素×高さ２画素の大きさの長方形部分ブロックに分割
されると仮定している。文字の画素表現中の各画素には
、当業者には周知の仕方で、それぞれ暗い影又は明るい
影を有するその画素に対応する二つの値、０又は１、の
内の一つを持っている。

【００２７】図１（Ａ）に示す４画素×２画素長方形部
分ブロックは、一層一般的に図１（Ｂ）に示すＪ画素×
Ｋ画素長方形部分ブロック１１Ａで置き換えることがで
き、この場合、隣接画素は、図１（Ｂ）に示すように、
この部分ブロックの上縁又は左縁に隣接して存在するＬ
個の画素から成るアレイである。数Ｌは、部分ブロック
１１Ａの大きさ（Ｊ×Ｋ）とは何の関係を持つ必要がな
いが、図１（Ｂ）に示す特定の構成に対しては、Ｌ＝Ｊ
＋Ｋ＋２であることが容易に確認される。この例では、
部分ブロック１１Ａの近隣画素の近隣値は、

【００２８
】

【数２】

【００２９】で規定される。

【００３０】日本工業規格の文字（ＪＩＳコード）のす
べてを含む、典型的な日本語の文字セットは、６８０２
文字を備えている。各文字を２４ビット×２４ビットの
長方形アレイで表せば、これは、文字セット全体につい
て、文字あたり７２バイト又はフォントデータの約５０
０Ｋバイトに相当する。各文字を長方形アレイ４０ビッ
ト×４０ビットで表せば、１文字に２００バイトが必要
であり、文字セット全体ではその表現に約１．４Ｍバイ
トのフォントデータが必要である。フォント圧縮アルゴ
リズムはすべて、文字を損失なく符号化し且つ復号すべ
きである。これは漢字についてはその複雑さのため困難
である。冗長除去法は、文字の他の線と同一の文字デー
タの水平線又は垂直線を識別し、その関係を符号化し、
復号しようとする。残念ながら、漢字は典型的に、この
ような規則性を示さない。しかし、部分ブロック画素パ
ターンで見ると漢字セットに一定の規則性を見ることが
でき、本発明は、これを活用している。

【００３１】本発明は、文字を同じ大きさの部分ブロッ
クの集まりとして表すことにより、文字の内部に一定の
水平及び垂直の規則性を識別し、これを活用する上で計
算した近隣値ＮＶに関連する、近隣予測コーダ（「ＮＰ
Ｃ：Ｎｅｉｇｈｂｏｒｈｏｏｄ　ＰｒｅｄｉｃｔｏｒＣ
ｏｄｅｒ」）を使用する。文字をこれら部分ブロックの
画素走査線の一つのシーケンスとして記憶させる。「次
の」又は目標の部分ブロック、特定の三つの先行部分ブ
ロックの画素パターンについての所定の情報、を予測す
る能力により所定の文字を表すのに必要な情報を平均し
てかなり（３０〜７０パーセント）圧縮することができ
る。文字表現の各部分ブロック値には、先行画素パター
ンを指標として使用して予測画素パターンの参照用テー
ブルを指すポインタとして役立つ、関連指標がある。先
行部分ブロックの画素パターンが目標部分ブロックに必
要な正確な画素パターンの予測を発生しない場合には特
別なポインタ値すなわちインジケータ又はフラグを使用
する。この場合には、しばしば発生することではないが
、実際の部分ブロック画素パターンを格納し、特別な指
標をこれと関連させる。目標部分ブロックに関連する指
標は、図１に示す実施例では、各部分ブロックに関連す
る単一ビット（二つの値、０及び１、を有する）を備え
ることができ、又はその２ｐ個の異なる可能な値を持つ
ｐビットの指標を備えることができる。各々の場合にお
いて、一つの指標値は、置き換えようとする実際の部分
ブロック画素パターンを示すフラグに対応するように選
定され、残りの指標値（単一ビット指標に対しては１、
ｐビット指標に対しては２ｐ　−１）は、隣接画素パタ
ーンから予測可能な他のもっともらしい画素パターン（
恐らく、実際の画素パターンを含む）に対応するように
選定することができる。

【００３２】この方法の第１の実施例では、部分ブロッ
クの大きさを図１に示すように幅４画素×高さ２画素（
Ｊ＝４、Ｋ＝２）になるように選定してあるので、各部
分ブロックは、１ビットがその８画素の各々に関連して
いるとすれば、正確に１バイトを備えている。ｐビット
のフラグ又は指標は、ここでの例示にｐ＝２を選定した
とき、各部分ブロックに関連している。８ビットすなわ
ち１バイトは、符号化を速くして予測情報を効率良く使
用するため、目標部分ブロックの画素パターンを予測す
るのに使用される隣接画素の集まりに対して選定される
。隣接画素構成を作っている画素の数は、類似の方法を
使用して、８より大きく又は小さくすることができる。 ２ビット指標を使用すると、各部分ブロックについて三
つの可能な画素パターンの予測が得られる他に、これら
三つの予測がいずれも正しくない場合に正確な画素パタ
ーンの位置を指す又は示すフラグを生ずる。目標部分ブ
ロック内の予測画素パターンは、目標部分ブロックの上
及び左にある、図１に示す、近くの８個の隣接画素を組
み合わせ、これら８個の画素値を、近隣値と呼ばれる８
ビット値として使用することにより作られる。２ビット
指標はこの近隣値と関連しており、ｒ＝１、２、・・・
、２ｐ−１＝３と番号付けられているｒ番目に最も確か
らしい画素パターンが、文字セット内の文字の集まりに
対して発生されている可能な部分ブロック画素パターン
の統計的輪郭（下に説明する）から選定される。各部分
ブロックには内部に８画素があるから、ｒ番目に最も確
からしい各画素パターン（ｒ＝１、２、３）について２
８＝２５６の可能な画素パターンを利用することができ
、それぞれ１バイトのエントリ２５６個を有する三つの
テーブルがここでは必要になる。更に一般的には、それ
ぞれ２５６個のエントリを有する２ｐ−１個のテーブル
がここで必要になる。画素部分ブロックのどれかを参照
して、その部分ブロック内の画素パターンを予測するの
に使用される隣接予測コード（「ＮＰＣ」）を作ってい
る画素群を、上に説明したように、その部分ブロックに
対する隣接画素群と言う。

【００３３】その文字を表すのに使用される画素アレイ
の縁から離れて又は超えて終わる所定の部分ブロックに
対する隣接画素には、画素値０が割り当てられる。従っ
て、部分ブロックの最上行又は最左列にある部分ブロッ
クは、その隣接画素の幾つか又は全部がブランクすなわ
ち「明」になる。この部分ブロックに対してこのように
決められた隣接画素の集合体は、次に、他のすべての部
分ブロックが処理されると同じ仕方で、以下に説明する
統計的輪郭の情報を使用して、部分ブロックの画素パタ
ーンを予測するのに使用される。代わりに、部分ブロッ
クの最上行又は最左列にある部分ブロックにその部分ブ
ロックに対する正確な画素パターンの位置を指すインジ
ケータ又はフラグを与えることができる。これらの方法
のいずれかを使用して、画素ブロック（部分ブロックの
アレイ）の最上行又は最左列にある各部分ブロックは、
その正確な画素パターンを決定して備えている。そして
アレイ内の他のすべての部分ブロックの画素パターンの
決定は、ＮＰＣを使用して、率直な仕方で進行する。こ
れら二つの方法をここでは当該部分ブロックの「正確な
画素パターンの決定」と言う。

【００３４】４×２部分ブロックは、ビット値の割当を
次のように表して、語Ｗに変換される。

【００３５】 　　　　　　　　　　　　　　８　　　　　　　　　　
７　　　　６　　　　５　　　　４　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　３　　　　　　　　　　Ｂ８　　Ｂ７　　Ｂ６　　
Ｂ５　　　　　　　　　　１　　２　　　　　　　　　
　Ｂ４　　Ｂ３　　Ｂ２　　Ｂ１　　　　　　　　　　
　　　　Ｗ＝（Ｂ８，Ｂ７，Ｂ６，Ｂ５，Ｂ４，Ｂ３，
Ｂ２，Ｂ１）更に一般的には、Ｊ×Ｋ部分ブロックの語
Ｗは、類推により、順に並んだＪ・Ｋ個のエントリを備
えることになる。

【００３６】文字セットの各文字に、次の構成要素が関
係している。（１）　２５６個の隣接画素パターンの各
々（常に同じ大きさ）に関連する２ｐ−１個の予測画素
パターン（及び２ｐ−１個の関連指標値）及び（２）　
その画素パターンを統計的輪郭から利用できる２ｐ−１
個の画素パターンからは予測できない（その中にない）
各部分ブロックに対する指標値及び関連の正確な又は実
際の画素パターン（これら指標の総数は、文字の大きさ
及び性質と共に変わる）。

【００３７】統計的輪郭は、各目標部分ブロックの画素
パターンを調べ、これを隣接画素の画素パターンに、又
は同等に、この目標部分ブロックの隣接画素の近隣値Ｎ
Ｖに、関連づけることにより発生される。これら各対、
すなわち目標部分ブロック画素パターンと関連近隣値Ｎ
Ｖの集まりは、セット内の各文字のすべての部分ブロッ
クについて発生される。８個の隣接画素の画素近隣の２
５６個の異なる画素パターンの各々について、近隣画素
パターンに関連するすべての部分ブロック画素パターン
の集まりが分析され、同一部分ブロック画素パターンの
数を可能な２５６個の画素近隣値ＮＶの各々について数
える。これによってヒストグラムが作られ、ｒ番目に最
も確からしい部分ブロック画素パターンを、隣接画素の
各固定近隣画素パターンについて、ｒ＝１、２、・・・
、２ｐ−１に対して区別することができる。これら最も
確からしい部分ブロック画素パターンは、このような各
固定近隣画素パターンについての統計的輪郭を示す。

【００３８】文字セット内の各文字を正確に表すのに必
要な情報を圧縮するには、文字のセットを通じて二つの
段階が必要である。第１に、上に説明したように、文字
の集まり及び部分ブロックの大きさの所定の選定（４×
２、又は更に一般的に、Ｊ×Ｋ）に対して存在する隣接
画素の各隣接画素パターンについてｒ番目に最も確から
しい部分ブロック画素パターン（ｒ＝１、２、・・・、
２ｐ−１）を決定するために、圧縮を行う前に、セット
内のすべての文字を走査することにより、統計的輪郭を
発生する。文字セット内の各文字を通じての第２の段階
は、各文字について２ｐ−１個又は２ｐ個の部分ブロッ
ク画素パターンの順序よく並んだ組み合わせを決定する
ように行われる。図１に示す構成を使用すれば、各部分
ブロックについて８個の隣接画素が使用される。ただし
、可能な例外として、文字セットの各文字を表すのに使
用される画素の長方形アレイの左上隅を含む、部分ブロ
ックの最上行及び部分ブロックの最左列にある部分ブロ
ックは除く。最上行又は最左列にある部分ブロックの画
素パターンは、これら特定の部分ブロックには一つ以上
の隣接画素が欠けているので、プロセスを始めるために
、正確に（予測ではなく）規定することができる。

【００３９】ここでの画素パターン予測に使用されるア
ルゴリズムは、複数の文字セットを使用して更に一般的
な統計的輪郭を発生することにより実施することもでき
る。これらセットは、相互に排他的であることがあり、
又はこのような各セットに入っている文字内に幾らかの
重なりを備えていることもある。この一般化した統計的
輪郭を使用して、この文字の画素表現の各目標部分ブロ
ックに対して隣接画素パターン又は等価近隣値ＮＶを発
生する一つの段階だけですべての他の文字を符号化する
ことができる。しかし、一般化統計的輪郭にはこの（新
しい）文字の効果が含まれていないことがあるので、こ
のアルゴリズムの性能は幾分劣っており、その文字を表
すには更に百分率の高い「フラグ付き」の正確なパター
ンを必要とするであろう。

【００４０】時により必要に応じて正確な画素パターン
を使用するので、各文字を表すのに必要なデータの大き
さを利用することができるが、ここで導入される総オー
バヘッドは、図１（Ｂ）の一般的状況に対して各々が２
ＪＫ個のエントリを有する２ｐ−１個のテーブルである
。 図１に示す特定の選択ｐ＝２、Ｊ＝４、及びＫ＝２に対
して、このオーバヘッドは、６８０２文字のすべての間
に分配されるので、重大ではない。（２ｐ−１）・２Ｊ
Ｋのオーバヘッドも、同じ理由で、ｐ、Ｊ、及びＫを合
理的に選定する一般的場合には重大ではない。

【００４１】この形式論の使用法を例示するために、図
１に示すように、選択ｐ＝２、Ｊ＝４、Ｋ＝２に対して
一例を提示する。統計的輪郭から、上に説明した隣接画
素に対するフォーマットを使用して、次の「最も確から
しい」部分ブロック画素パターンが生ずると仮定する。 便宜のため、統計的輪郭で生ずる２８＝２５６個の可能
な近隣値ＮＶ又は隣接画素構成の内、四つの隣接値ＮＶ
＝０（００００００００）、１（０００００００１）、
２（００００００１０）、及び３（００００００１１）
だけを考える。選択ｐ＝２に対して、２２−１＝３個の
「最も確からしい」部分ブロック画素パターンを各近隣
値ＮＶに対して選定する。これは予測値ＰＶ＝０、１、
及び２に対応する。予測値ＰＶ＝３は正確な画素パター
ンに対応する。

【００４２】次の部分ブロック画素パターンの（短縮）

【００４３】

【表１】

【００４４】系列を仮定する。３（ＮＶ＝０）、１４（
ＮＶ＝３）、１２（ＮＶ＝１）、６（ＮＶ＝０）、１３
（ＮＶ＝１）、１７（ＮＶ＝２）。これらはそれぞれｓ
＝１、２、３、４、５、及び６の番号の部分ブロックに
対応する。番号ｓ＝３及びｓ＝６の部分ブロックに対す
る画素パターンは、統計的輪郭から得られる予測画素パ
ターンを参照するのではなく、正確に規定しなければな
らない（ＰＶ＝３に対応する）。部分ブロック番号に関
連予測値ＰＶｓを加えたものは、これら部分ブロックｓ
＝１、２、・・・、６の各々に対する画素パターンを正
確に示す数（ｓ，ＰＶｓ）の順序対として表すことがで
きる。これら順序対の系列は、故に、（１，０）、（２
，２）、（３，３）、（４，２）、（５，０）、（６，
３）となる。この例では、６個の部分ブロック画素パタ
ーンの内の四つが、上の表１に示した統計的輪郭の情報
を使用して、各種部分ブロックに関連する隣接画素近隣
値ＮＶから予測される。残りの二つの画素パターンは、
隣接画素予測値ＰＶ＝３を参照して正確に指定しなけれ
ばならない。このＰＶ＝３の値は、これら二つの部分ブ
ロックに対する、補足リストに保持されている、正確な
画素パターンの位置を合図し、又は指し示す。図３は、
表１のエントリに存在する８個の部分ブロック画素パタ
ーンを示す。

【００４５】予測値ＰＶの系列（表１に示す２進化１０
進符号で表される）に必要なビットの総数は、６×８＝
４８ビットを必要とする従来のビットマップと比較して
、６×２＋８（部分ブロックｓ＝３）＋８（部分ブロッ
クｓ＝６）＝２８ビットである。実際には、文字セット
の圧縮表現に必要なビットの総数の百分率縮小は３０〜
７０パーセントであり、圧縮比７：５から１０：３まで
に相当する。

【００４６】文字を部分ブロック画素パターンの集まり
として表す目的の圧縮回復は、次のように進行する。

【００４７】部分ブロック ｓ＝１　　　　ＮＶ＝０；画素パターン＝３ｓ＝２　　
　　ＮＶ＝３；画素パターン＝１４ｓ＝３　　　　ＮＶ
＝１；画素パターン＝１２（補足リストによる） ｓ＝４　　　　ＮＶ＝０；画素パターン＝６ｓ＝５　　
　　ＮＶ＝１；画素パターン＝１３ｓ＝６　　　　ＮＶ
＝２；画素パターン＝１７（補足リストによる） 所定の文字について、各部分ブロックがアレイに追加さ
れるにつれて、先行部分ブロックからの隣接画素パター
ンにより作られた近隣値ＮＶを予測値ＰＶと共に使用し
て、この新しい部分ブロックの画素パターンを決定する
。

【００４８】単一レベルの２ｐ−１＝１、３、又は７個
の「最も確からしい」画素パターンを含む、第１の実施
例のシミュレーション試験を、漢字セットからの各２５
５文字から成る二つのサブセットについて行った。予測
テーブルを各文字サブセットについて独立に計算した。 各サブセット内の各文字を表す２４画素×２４画素のア
レイについて、表２は、これら二つのサブセットに対し
て達成された平均ビット節減又は圧縮百分率（縮小）を
示している。

【００４９】

【表２】

【００５０】これらの結果から１レベル予測に対する最
良の選択は、ｐ＝２（予測が正しくない場合、三つの予
測と正確な値）であると思われる。この最良の選択は、
選定した文字サブセットの大きさと性格とによって変わ
ることがあるが、二つの選択ｐ＝２及びｐ＝３の一方が
一般に最良の選択になる。

【００５１】図４は、図２に示す文字の試験及び分析の
結果の幾つかを示すもので、そこでは黒い画素値をそれ
だけで（正確な構成を使用）正しく予測することができ
ず、統計的輪郭の情報を使用して灰色又は斜線を施した
画素が黒であると予測された。黒の画素値はこのように
して、その画素パターンが、２ビット指標（ｐ＝２）に
対する指標ｒ＝４（ＰＶ＝３）を使用して、補足リスト
から正確に規定される部分ブロックの一部であった。白
い画素は、図を混乱させないように常にそれだけで表示
される。

【００５２】本発明の第２の実施例は、図１に示すよう
に４×２（又は、更に一般的には、Ｊ×Ｋ）の長方形画
素ブロックを使用しているが、図１に示すように１（又
は１’）、２、３、５、６、７、及び８と記した隣接画
素を使用して、目標部分ブロック画素パターンの２レベ
ルの予測を行うことを含んでいる。この第２の実施の第
１の実施例では、各文字は、（１）　その第１レベルの
予測に対する部分ブロックあたり１ビットの表、及び（
２）　Ｑ−１個の第２レベルの予測（Ｑ≧２）に目標部
分ブロックの正確な構成を加えたものから成るリスト、
に対応している。予測の第１のすなわち最低のレベルで
、目標部分ブロックの唯一の予測構成は、隣接画素の近
隣値ＮＶに対応する最も確からしい構成（ＰＶ＝０又は
ｒ＝１）である。これは、値０を有するビットＮｏ．１
に対応する。 この予測が正しくなければ、ビットＮｏ．１の値を１に
等しく設定し、予測の第２レベルを使用する。予測のこ
の第２レベルで、ｒ番目に最も確からしい構成が提示さ
れ（ｒ＝２、３、・・・、Ｑ）、目標部分ブロック構成
を予測する。便宜と能率とのため、Ｑ＝２ｑを選定する
ことができる。ただし、ｑは正の整数、たとえば、ｑ＝
４である。Ｑ＝２ｑのとき、ビット２、３、・・・、ｑ
＋１は、この第２のレベルで利用できるＱ−１個の予測
を表している。一例として、（ｑ＋１）個の（ａ１、ａ
２、・・・、ａｑ＋１）を、第１及び第２のレベルの予
測、及び必要ならば、正確な画素パターンを表すビット
としよう。第１のレベルの予測は、ａ１＝０に対応し、
ａ２、・・・、ａｑ＋１に対するビット値は重要ではな
い。第２のレベルの予測子、ａ１＝１に対して、及び残
りのｑビットａ２、・・・、ａｑ＋１の中で、これらビ
ットの中の少なくとも一つが値０を持っている。第１の
レベルでＱ−１＝２ｑ−１個の予測がどれも正しくなけ
れば、すべてのビット値ａ１、ａ２、・・・、ａｑ＋１
を１に等しく設定し、正確な部分ブロック構成をここで
使用する。たとえば、ここでｑ＝４を選定すれば、第１
レベルの予測には一つの予測構成があり、第２レベルの
予測には１５個の予測値の他に、必要ならば、目標部分
ブロックに対する正確な画素パターンがある。第２の実
行のこの実施例でｑ＝４に対して必要なビットの数は、
１（第１レベルの）予測＋４（第２レベルの）予測＝５
ビット又は５＋８（デフォルトとして、正確な画素構成
）＝１３ビットである。

【００５３】この第２の実行は、第１のレベルで、第１
のレベルの２ｔ−１個の予測に対応するｔビットに、上
に説明したように第２レベルの予測のｑビットを加えた
ものを設けることにより一般化することができる。ここ
でｔは、整数ｑとは無関係に選択することができる正の
整数である。実際には、ここではｔ＝１又はｔ＝２及び
ｑ＝４を選択するのが十分である。表３及び表４は、ｑ
＝４及びｔ＝１、２、又は３の選択に対し、それぞれ２
４×２４のフォント区画及び４０×４０のフォント区画
について２レベル近隣予測コードを使用した場合のビッ
ト節減又は百分率圧縮を示してある。選択Ｔ＝１が、上
に説明した６８０２文字セットに対してここでは最良の
選択であると思われる。最大のフォントの大きさに対し
て、

【００５４】

【表３】

【００５５】

【表４】

【００５６】平均ビット節減は６８パーセントを超える
可能性があることに注目すること。

【００５７】この第２の実行は、画素の部分ブロックに
対して異なる隣接パターンの各々について画素パターン
の、レベル数ｈによって決まる、ｔｈ個の異なる予測を
有する予測レベル数ｈ（＝１、２、３、・・・、Ｈ）を
備えたＨ個の予測レベルを使用することにより更に一般
化することができる。予測プロセスは、予測レベルｈか
ら予測レベルｈ＋１（ｈ＝１、２、・・・、Ｈ−１）ま
で、正しい画素パターンが予測によって決まるまで、又
は正確な画素パターンがデフォルトにより合図されるま
で、進行する。

【００５８】図５は、２レベルの予測を有する２４×２
４の文字表現について、図２に示す漢字に適用した２レ
ベル予測の結果を示す。図５で、黒く塗った画素位置は
、どのレベルでも予測することができないので、その部
分ブロックに対しては正確な値を使用しなければならな
い画素を表す。暗い灰色の画素は、第２レベルの予測で
予測することができるが、第１のレベルでは予測するこ
とができず、明るい灰色の画素は、第１レベルの予測で
予測することができる。白い画素は、図４に関連して上
に説明したように、常にそれだけで表示される。

【００５９】図６、図７、及び図８は、本発明による近
隣予測コードを使用する、４ビット×２ビットの部分ブ
ロックを有する、三つの他の近隣予測構成（１又は１’
、２、３、４、５、６、７、及び８と記した隣接画素）
を示す。図６、図７、及び図８に示す各近隣予測構成は
、上に説明したように、１レベル予測計画で、又は２レ
ベル予測計画で使用することができる。先に説明したよ
うに、図１、図６、図７、及び図８のいずれかに示した
４ビット×２ビットの部分ブロックは、本発明を適用す
る目的で更に一般的なＪビット×Ｋビットの長方形部分
ブロックで置き換えることができる。

【００６０】他の近隣予測構成を図９に示すが、これで
は、幅Ｊ画素×高さＫ画素の部分ブロック２１がｃ１、
ｃ２、ｃ３、・・・、ｃ（２Ｊ＋２Ｋ＋３）、ｃ（２Ｊ
＋２Ｋ＋４）と番号を付けたセットＢ　　２Ｊ＋２Ｋ＋
４個の隣接画素で囲まれている。２Ｊ＋２Ｋ＋４個の境
界画素から成るセットＢからのＬ画素（「隣接画素」）
から成るサブセットＢ１を選択し、部分ブロック１１の
統計的輪郭を境界画素のセットＢのＬ個の画素を使用し
て作り出す。各部分ブロック１１について、Ｌ個の隣接
画素から成るセットＢ１の統計的輪郭を使用して、上述
のように、部分ブロック１１に対するｒ番目に最も確か
らしい画素パターンを作る（ｒ＝１、２、・・・、２ｐ
−１）。これら２ｐ−１個の画素パターンの一つが正確
に合えば、フラグ又は他の印を使用して正確な画素パタ
ーンを示すか指摘するかし、この正確な画素パターンを
上述のように使用する。

【００６１】たとえば、Ｊ＝４及びＫ＝２を選択すると
、境界画素の最大数は、８画素部分ブロックに対して２
Ｊ＋２Ｋ＋４＝１６である。境界画素のセットＢ１は、
１６個の隣接画素全部から、又はそれらの内のＬ個から
成る適切なサブセットから構成することができる。 ここでＬは、Ｌ＝３又はＬ＝８のような、より小さい正
の整数ならどんな数でもよい。Ｌ＝２、４、又は８を選
択することは、ここでは魅力的である。

【００６２】本発明の他の実施例では、部分ブロック１
１（図１（Ａ）（Ｂ）、図６、図７、図８）又は２１（
図９）の画素パターンを近隣予測子により正確に予測す
るという所要条件は、部分ブロック内のＪ・Ｋ個の画素
の中で、或る小さい数Ｖを正しく予測すれば十分である
というように緩和される。ただしＶ＜Ｊ・Ｋである。 魅力的な二つの選択は、Ｖ＝Ｊ・Ｋ−１、及びＶ＝Ｊ・
Ｋ−２である。前のように、隣接画素（又は境界画素）
の各セットに対応する部分ブロック画素パターンの統計
的輪郭を作り、各部分ブロックに対する隣接画素（又は
境界画素）の特定のセットを分析し、ｒ番目に最も確か
らしい部分ブロック画素パターン（ｒ＝１、２、・・・
、２ｐ　−１）を実際の又は正確な画素パターンと比較
する。Ｖ＝Ｊ・Ｋ−ｗ（ｗ＝１又は２又は・・・）であ
れば、部分ブロック１１又は２１の正確な画素パターン
からｗ画素だけ異なっている予測画素パターンを（十分
厳密に）合っているものとして受け入れる。この実施例
は、部分ブロック１１又は２１の予測画素パターンに０
、１、２、・・・、又は最大ｗ個の画素までのミスマッ
チがあってよいが、レベルｗ（ｗ≧１）の増大画素マッ
チと言われる。

【００６３】ここに開示した方法は、２レベル（たとえ
ば、暗と明）の画素のアレイとして表し得る映像の予測
及び符号化にも適用することができる。従って、この方
法は、表意記号の集まりに制約なく使用される。

【００６４】増大画素マッチ機構を利用する実施例を示
したが、統計的輪郭をわずかに異なる方法で計算するの
が望ましいことがある。この方法では、特定の部分ブロ
ックの確率を、ＮＰＣを与えられた正確な部分ブロック
画素パターンの発生の頻度から、及びその部分ブロック
に厳密に合った頻度から計算する。正確な合致の頻度は
、重み付け和を使用して増加画素マッチのものと組み合
わせることができる。これにより、最も確からしい部分
ブロック値を選定するとき、増加画素マッチの影響を制
御することができる。

【００６５】画素パターンを、一度に１部分ブロックず
つ作ることは、図１（Ａ）（Ｂ）、図６、図７及び図８
に示したような所定の隅から始めることに限定されない
。図１０に示したように、任意の列ｎ＝ｎ１及び任意の
行ｍ＝ｍ１を選択し、Ｍ×Ｎ部分ブロックからなるブロ
ック内に固定することができ、ｍ＝ｍ１又はｎ＝ｎ１又
はその両者としたとき座標（ｍ、ｎ）を有する部分ブロ
ックの各々についての正確な画素パターンを決定するこ
とができる。図１０に示したように、ｍ＝ｍ１及びｎ＝
ｎ１（１＜ｍ１＜Ｍ及び１＜ｎ１＜Ｎに対して）を選択
すると画素の元のブロックが下記座標（ｍ、ｎ）を有す
る部分ブロックの四つの群に分けられる。

【００６６】 群Ｉ　　：１≦ｍ≦ｍ１−１； 群ＩＩ　　：ｍ１＋１≦ｎ≦Ｍ；　　１≦ｎ≦ｎ１−１
；群ＩＩＩ　：１≦ｍ≦ｍ１−１；　　ｎ１＋１≦ｎ≦
Ｎ；群ＩＶ　　：ｍ１＋１≦ｎ≦Ｍ；　　ｎ１＋１≦ｎ
≦Ｎ群Ｉ、ＩＩ、ＩＩＩ　、及びＩＶの各々の各部分ブ
ロックの画素パターンは未知であり、第５群、すなわち
群Ｖ　　：ｍ＝ｍ１；　　１≦ｎ≦Ｎ；及び１≦ｍ≦Ｍ
；　　ｎ＝ｎ１ の各部分ブロックの正確な画素パターンを知って構成し
なければならない。群ＩＶのすべての部分ブロックの統
計的輪郭は、図１に示すような各部分ブロックの左及び
上にある隣接画素パターン（既知と仮定）を使用して得
られる。群ＩＩＩのすべての部分ブロックの統計的輪郭
は、図６に示すような各部分ブロックの右及び上にある
隣接画素パターン（既知と仮定）を使用して得られる。 群Ｉのすべての部分ブロックの統計的輪郭は、図７に示
すような各部分ブロックの右及び下にある隣接画素パタ
ーン（既知と仮定）を使用して得られる。最後に、群Ｉ
Ｉのすべての部分ブロックの統計的輪郭は、図８に示す
ような各部分ブロックの左及び下にある隣接画素パター
ン（既知と仮定）を使用して得られる。

【００６７】群Ｉ、ＩＩ、ＩＩＩ、及びＩＶの各々に対
する統計的輪郭は、その群内の各部分ブロックの画素パ
ターンを予測するのに使用した隣接画素の位置とは異な
る位置を使用して決定されることに注目のこと。部分ブ
ロックの群Ｉ〜ＩＶの各々について、群Ｖの部分ブロッ
クの各々にある既知の画素パターンを用いて予測を開始
し、画素のブロックの境界に向かって外側に進む。

【００６８】ｍ１＝１を選択すれば、群Ｉ及びＩＩＩが
消失し、群ＩＩ及びＩＶだけが残るので、図８及び図１
にそれぞれ示した隣接画素パターンに対し、二つの統計
的輪郭だけが必要である。同様に、ｍ１＝Ｍを選択する
と、群ＩＩ及びＩＶが消失し、群Ｉ及びＩＩＩだけが残
る。同様に、ｎ１＝１を選択すれば、群Ｉ及びＩＩが消
失し、群ＩＩＩ及びＩＶだけが残る。同様に、ｎ１＝Ｎ
を選択すれば、群ＩＩＩ及びＩＶが消失し、群Ｉ及びＩ
Ｉだけが残る。ｍ１を１又はＭに選定し、ｎ１を１又は
Ｎに選定すれば、四群の内三つが消失し、一群だけが残
り、上述のように、図１（Ａ）（Ｂ）、図６、図７、及
び図８に示したように、所定の四隅の一つからの開始に
対応する。

【００６９】本発明を６８０２個の漢字のセットを参照
して例示した。本発明は、漢字のどんな大きさの異なる
組み合わせ、中国語、ヘブライ語、アラビア語、タミル
語、又は　ペルシア語の文字のセットにも同等に適用す
ることができる。本発明は、音、語、又は句を表すのに
使用される表意記号の適度の大きさのどんな組み合わせ
にも、又は画素の２レベル又は陰により表すことができ
るどんな映像を表すのにも適用することができる。

【００７０】

【発明の効果】以上のよう、本発明によれば、元のデー
タフィールドを記述するのに必要な情報（ビットの数）
の百分率圧縮又は縮小は、３０〜７０パーセントであり
、各種表意記号に関するデータを効率的に圧縮可能であ
り、さらに、圧縮を復元したとき、元の映像の各文字を
表すのに使用されていると同じ量の分解能を生ずること
が可能である。

【図面の簡単な説明】

【図１】４ビット×２ビット及びＪビット×Ｋビットの
寸法の長方形部分ブロックに適応した、近隣予測計算を
示している。

【図２】日本語で用いられる典型的な漢字を示している
。

【図３】明細書中に示した事例における画素パターンの
グループを示してる。

【図４】図２に示した文字に適応された、本発明の第１
の実施例（１レベル）を示している。

【図５】図２に示した文字に適応された、本発明の第２
の実施例（２レベル）を示してる。

【図６】本発明に基づく４ビット×２ビットの部分ブロ
ックで用いられる別の近隣予測構成を示している。

【図７】本発明に基づく４ビット×２ビットの部分ブロ
ックで用いられる別の近隣予測構成を示している。

【図８】本発明に基づく４ビット×２ビットの部分ブロ
ックで用いられる別の近隣予測構成を示している。

【図９】本発明に基づいて使用可能なより一般的な画素
近隣を示している。

【図１０】本発明に基づいて使用可能な部分ブロックの
初期の行及び列の一般的な選択を示している。

Claims (1)

【特許請求の範囲】
1. 【請求項１】画素のブロック上に画素パターンとして表
   現されるような、表意文字の集合を表現するために用い
   られるデータ圧縮法であって：各表意記号の画素のブロ
   ックをＭ×Ｎの相互に排他的な長方形の画素の部分ブロ
   ックに分解し、各ブロックの寸法はＪ画素×Ｋ画素であ
   り、ただし、Ｍ、Ｎ、Ｊ及びＫは正の整数であり、該部
   分ブロックには、ブロックの一隅から始め、連続的に１
   行１行又は１列１列進んで連続的にｓ＝１、２、・・・
   、Ｓなる番号が付与され、該各部分ブロックは固有の二
   次元座標（ｍ、ｎ）（ｍ＝１、２、・・・、Ｍ；ｎ＝１
   、２、・・・、Ｎ）であるステップと；１≦ｍ１≦Ｍの
   範囲にある所定の整数ｍ１及び１≦ｎ１≦Ｎの範囲にあ
   る所定の整数ｎ１に関して、ｍ＝ｍ１又はｎ＝ｎ１、又
   はｍ＝ｍ１かつｎ＝ｎ１と番号が付与された各部分ブロ
   ックの正確な画素パターンを決定するステップと；座標
   （ｍ、ｎ）の各画素部分ブロック（ただし、１≦ｍ≦ｍ
   １−１かつ１≦ｎ≦ｎ１−１である）に関して、座標（
   ｍ＋１、ｎ）、（ｍ＋１、ｎ＋１）及び（ｍ、ｎ＋１）
   を備えた部分ブロック内の隣接画素の画素値を決定し、
   さらに各部分ブロックに関する表意記号及び関連する隣
   接画素の集合の統計的輪郭を決定するステップと；座標
   （ｍ、ｎ）の各画素部分ブロック（ただし、１≦ｍ≦ｍ
   １−１かつｎ１＋１≦ｎ≦Ｎである）に関して、座標（
   ｍ＋１、ｎ）、（ｍ＋１、ｎ−１）及び（ｍ、ｎ−１）
   を備えた部分ブロック内の隣接画素の画素値を決定し、
   さらに各部分ブロックに関する表意記号及び関連する隣
   接画素の集合の統計的輪郭を決定するステップと；座標
   （ｍ、ｎ）の各画素部分ブロック（ただし、ｍ１＋１≦
   ｍ≦Ｍかつ１≦ｎ≦ｎ１−１である）に関して、座標（
   ｍ−１、ｎ）、（ｍ−１、ｎ＋１）及び（ｍ、ｎ＋１）
   を備えた部分ブロック内の隣接画素の画素値を決定し、
   さらに各部分ブロックに関する表意記号及び関連する隣
   接画素の集合の統計的輪郭を決定するステップと；座標
   （ｍ、ｎ）の各画素部分ブロック（ただし、ｍ１＋１≦
   ｍ≦Ｍかつｎ１＋１≦ｎ≦Ｎである）に関して、座標（
   ｍ−１、ｎ）、（ｍ−１、ｎ−１）及び（ｍ、ｎ−１）
   を備えた部分ブロック内の隣接画素の画素値を決定し、
   さらに各部分ブロックに関する表意記号及び関連する隣
   接画素の集合の統計的輪郭を決定するステップと；統計
   的輪郭が存在するｓ＝１、２、・・・、Ｓと番号が付与
   された各部分ブロックに関して、隣接画素の統計的輪郭
   から、その部分ブロック内の画素のｒ番目の最も確から
   しいパターンをｒ＝１、２、・・・、Ｒ−１に対して決
   定し、ここでＲは２以上の所定の整数の中から選択され
   、ｓ番号が付与された部分ブロックに対するｒ番目の最
   も確からしいパターンの選択に対応する指標ａｒｓを割
   当てるステップと；指標ａｒｓを割当てるｓ＝１、２、
   ・・・、Ｓの番号が付与された各部分ブロックに関して
   、指標ａｒｓに対応する予測画素パターンが正しいパタ
   ーンであれば、部分指標ａｒｓを割当て、指標ａｒｓに
   対応するＲ−１の予測画素パターン（ｒ＝１、２、・・
   ・、Ｒ−１）がいずれも正しいパターンでなければ、あ
   るいは、部分ブロックの座標（ｍ、ｎ）がｍ＝ｍ１又は
   ｎ＝ｎ１、又はｍ＝ｍ１かつｎ＝ｎ１を満足させる場合
   には、部分ブロックｓに対して正確な画素パターンの使
   用を要求する指標ａＲｓが割当てられるステップと；さ
   らに、ｓ＝１、２、・・・、Ｓの番号が付与された各部
   分ブロックが、割当てられた指標ａｒｓ又は指標ａＲｓ
   と、ケースに応じて、数（ｓ、ａｒｓ）又は（ｓ、ａＲ
   ｓ）の順序対として、関連づけられるステップと；から
   成ることを特徴とする、データ圧縮法。