JPH046954A - 画像予測符号化方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、画像を通信するファクシミリ装置或いは蓄積
する画像ファイル装置等における画像予測符号化方式に
関するものである。

〔従来の技術〕

従来の０３．６４フアクシミリに代表されるランレング
ス符号化方式は、画素が白または黒が続く長さ（ランレ
ングス）をカウントし、あらかじめ用意された符号表か
らそのカウント値に対応する符号を決定する方式である
。ここで用いられる符号表は、文書画像に多い長い白う
、ンに対して比較的短い符号を割りあてるような特徴づ
けがされている。このためランの長さの統計的性質が符
号表を作成する時に基準とした画像のものと異なる場合
、例えば白黒が頻繁に反転する疑似中間調画像を符号化
する場合は、符号量が原データ量を越えてしまうという
問題が生じている。

そこで、この様なランレングスに基づいて符号化した場
合に不都合を生じる画像に対しても効率良い符号化が実
行できる一つの符号化手法として、算術符号等のマルコ
フモデル符号を用いた符号化が提案されている。

従来から知られている算術符号は、入力信号列を小数２
進数で表わされる符号になるように算術演算により符号
形成がなされる方法である。この方法はＬａｎｇｄｏｎ
およびＲ１５ｓａｎｅｎらによる文献“Ｃｏ　ｍ　ｐ　
ｒ　ｅ　ｓ　ｓ　ｉ　ｏ　ｎ　ｏ　ｆ　Ｂ　ｌ　ａ　ｃ
　ｋ　／　Ｗ　ｈ　ｉ　ｔ　ｅ　Ｉ　ｍ　ａ　ｇ　ｅ　
５ｗ１ｔｈ　　Ａｒｉｔｈｍｅｔｉｃ　Ｃｏｄｉｎｇ　
、　ＩＥＥＥ　ＴｒａｎＣｏｍ、Ｃ０Ｍ−２９，６，（
１９８１，６）等に発表されている。この文献によると
すでに符号化した入力信号列を８１劣勢シンボル（ＬＰ
Ｓ）の出る確率をｑ１演算レジスタＡｕｇｅｎｄをＡ　
（Ｓ）、符号レジスタをＣ（Ｓ）とした時に、入力信号
ごとに以下の算術演算を行う。

Ａ（Ｓｌ）　＝Ａ（Ｓ）　Ｘｑ　Ａ＝　Ａ（Ｓ）　Ｘ２
−’　　・・・（１）Ａ（Ｓｏ）　　＝　　＜Ａ（Ｓ）
　　−Ａ（Ｓｌ）＞　　ｉ　　　　　・・・　（２）＜
＞１は有効桁１２　ｂｉｔで打ち切りを表すｃ　（ｓｏ
）＝ｃ　（ｓ）　　　　　　　　　　・・・（３）Ｃ（
Ｓｌ）＝Ｃ（Ｓ）＋Ａ　（ＳＯ）　　　　　・・・（４
）ここで、符号データが優勢シンボル（ＭＰＳ：上の例
ではＯ）の場合はＡ　（ＳＯ）、Ｃ（ＳＯ）を次のデー
タの符号化に使う。また劣勢シンボル（ＬＰＳ：上の例
ではｌ）の場合は、Ａ　（Ｓｌ）、Ｃ（Ｓｌ）を次のデ
ータの符号化に使う。

新しいＡの値は２５倍（Ｓは０以上の整数）され、０．
５＜Ａ＜１．０の範囲におさめられる。この処理は、ハ
ードウェアでは演算レジスタＡを８回シフトすることに
相当する。符号レジスタＣに対しても同じ回数の左シフ
トが行われ、シフトアウトされた信号が符号となる。以
上の処ζを繰り返し符号形成がなされる。

また、（１）の式で示したようにＬＰＳの出現確率ｑを
２のべき乗（２−Ｑ：　Ｑは正整数）で近似することに
より、乗算計算をシフト演算に置き換えている。この近
似をさらによくするためにｑを、例えば（５）の式の如
くの２のべき乗の多項式で近似することが提案されてい
る。この近似により効率最悪点の改善が行われている。

ｑ〜２−”　＋　２−０２　　　　　　　　　　　・・
・（５）しかしながら、前述の算術符号化では、２のべ
き乗で近似された出現確率は固定であって、出現確率が
異なる画像に対しては、効率良い符号化がなされないこ
とがある。

そこで、符号化すべき画像の特徴に応じてＬＰＳの出現
確率ｑを変え、画像に適した効率的な符号化を行うこと
が提案されている。尚、この確率推定方法には、符号化
済の画素の状態により、一義的に決定する静的な方法と
、符号化しながら確率を推定していく動的な方法が考え
られている。

〔発明が解決しようとしている課題〕

前者の符号化済の周囲画素を参照しその状態により白／
黒の発生確率を推定する方法をとった場合において、文
書画像等、非常に相関の強いものが符号化対象であれば
、符号化注目画素に近いものから順に周囲の数画素を参
照し、それによる状態分けを行っただけでもかなりエン
トロピーを低くすることが出来、高効率の符号化が可能
である。

しかしながら、誤差拡散画像の如（、ランダムドツトに
近いもので構成されている画像に対しては、参照範囲を
広げること以外に効率の良い符号化に適した参照の方法
が知られていない。

〔課題を解決するための手段（及び作用）〕本発明は以
上の点に鑑みてなされたものであり、画像予測符号化方
式において、注目画素近傍領域が疑似中間調画像である
か否かを判定し、その判定に基づいて、符号化画素予測
に用いる参照画素テンプレートを疑似中間調画像用と一
般画像用とに適応的に切りかえる画像予測符号化方式を
提供するものである。

〔実施例〕

第１図は、本発明を適用した画像伝送システムの実施例
である。入力される２値付号列は入力端２００より、４
ライン分の容量をもつラインメモリ１０に蓄えられ、３
ライン前の情報と共にラッチ１２に入力される。ラッチ
１２より、ハーフトーン検出用の１８８画素の参照信号
Ｈ３Ｏ０と、予測符号化のための１４画素分の参照信号
Ｓｅｌ　３０１と、符号化画素信号Ｄ２０３が出力され
る。

ハーフトーン検出用の信号Ｈ３Ｏ０は、ハーフトーン検
出器１５に入り、１ｂｉｔの信号Ｅｄ３０２を出力する
。即ち、ハーフトーン検出器１５が、現在の符号化部分
はハーフトーンであると判定した場合に信号Ｅｄ３０２
は１であり他は０となる。信号Ｅｄ３０２に従って、予
測状態決定回路１３は、適切な（効率の良い方の）予測
テンプレートを選択し、そのテンプレート内の画素情報
を、ステータス信号５ｔ２０６として出力する。信号５
ｔ２０６は符号化画素データＤ２０３と共に符号器１１
に入り、符号化され伝送される。

第２図はラインメモリ１０及びラッチ１２のブロック図
である。入力端２００より入る画素信号はラインメモリ
１０に含まれる４本のラインバッファ４０−１〜４０−
４により３ライン前までのデータかたくわえられる。こ
れら４本のラインバッファからパラレルに出たデータは
ラッチ列に入り、注目画素とその周囲の画素の同時参照
を可能にする。

Ａ−Ｌ（Ｃ，、Ｃ２，Ｌ、、Ｌ２を含む）ラッチは予測
符号のための参照画素候補１４画素を捉えるためのもの
でこれらは信号５ｅ１３０１として出力される。また、
Ａ、Ｂ＋　　ＣＩ　＋　　Ｂ＋　　Ｂ＋　　Ｇｙ　　Ｂ
＋　　ａ＋Ｌ　Ｊｔ　Ｋ＋　Ｃ２＋　Ｊ　Ｃ＋　Ｌｌ＋
　ｄ＋　ｅｒ　ｆのラッチは、ハーフトーン部検出のた
めに用いられ、信号Ｈ３Ｏ０として出力される。Ｘは注
目画素値を記憶するラッチで、この値は信号Ｄ２０３と
して出力される。

第３図はハーフトーン検出器１５の図である。信号Ｈ３
Ｏ０より注目画素周辺の画素情報がＲＯＭ６５に入力さ
れる。ＲＯＭ６５にはあらかじめ、周囲１８８画素全状
態２１８状態に対して、それがハーフトーン部分である
率が高いか否かの判定結果ｌ又は０（ハーフトーンらし
ければ１）が記憶させてあり、信号Ｈ３Ｏ０の入力に対
し、即座に判定結果をＥｄ３０２として出力する。

第４図は、予測状態決定回路１３のブロック図である。

ハーフトーンフラッグ信号Ｅｄ３０２と参照候補画素信
号Ｓｅｌ　３０１はマルチプレクサ６６に入力される。

マルチプレクサ６６はハーフトーン検出器１５からのハ
ーフトーンフラッグ信号Ｅｄ３０２に従い、ハーフトー
ンと判定された場合には、信号５ｅ１３０１から第５図
工に示す１２画素のデータをＲＯＭ６７に送り、それ以
外の場合には、第５図■に示す様な、−船釣に用いられ
ている１２画素のデータをＲＯＭ６７に出力する。

ＲＯＭ６７は信号Ｅｄ３０２およびマルチプレクサ６６
からの１２画素のデータに従って、ステート信号５ｔ２
０６を出力する。

第６図は、符号器１１のブロック図である。

状態決定回路１３からの状態信号５ｔ２０６は、カウン
タメモリ２３、符号化条件メモリ２４に入力される。

符号化条件メモリ２４には、状態信号５ｔ２０６で表わ
される各状態毎に、出現しやすいシンボルである優勢シ
ンボルＭＰ３１０８と、後述する算術符号のＬＰＳの出
現確率を含む符号化条件を示すインデックスｌ１０７が
記憶されている。ＭＰ５１０８は予測変換回路２７に入
力され、予測変換回路２７では画素信号Ｄ２０３がＭＰ
Ｓ１０８と一致した時に１となるＹＮ信号１０１を作る
。ＹＮ信号ｌｏｔは更新回路２５に入力され、更新回路
２５では、ＹＮ信号が１の時に、カウンタメモリ２３に
記憶されているカウント値のうち対応する状態のカウン
トをインクリメントする。そして、カウンタメモリ１３
に記憶されているカウント値Ｃ１０６がカウントテーブ
ルＲＯＭ１２からの設定値ＭＣ１０５に一致したならば
、インデックスｌ１０７が太き（なる方向（ＬＰＳの出
現確率ｑが小さくなる方向）に更新する。（ＭＰＳの反
転は行わない。） 尚、カウントテーブルＲＯＭ２２は、ＬＰＳの出現確率
ｑを表わすインデックスＩに対応して決められている第
１表で示したＭＰＳの数ＭＣ１０５を更新回路２５に供
給する。

また、更新回路２５では、ＭＰ８１０８と画素信号Ｄ２
０３が不一致の場合、即ち、予測変換回路２７からのＹ
Ｎ信号が０の時はインデックス■１０７が小さくなる方
向（ＬＰＳの出現確率ｑが太き（なる方向）に更新する
。また、インデックスが１の時に値が０のＹＮ信号が来
ると、ＭＰＳを反転（０→１または１→０）する処理を
行う。出力ｉ’　１０９、ＭＰＳ’　１１０は更新後の
インデックスの値であり、符号化条件メモリ２４に再記
憶される。

符号化パラメータ決定回路２６では、インデックスｌ１
０７の値に基づいて算術符号の符号化パラメータＱｌｌ
ｌを算術符号器２８にセットする。この算術符号器２８
では、予測変換回路２７からのＹＮ信号ｌＯ１をパラメ
ータＱｌｌｌを用いて算術符号化し符号１０２を得る。

尚、符号化条件メモリ２４に初期値を与えておき、Ｉ、
ＭＰＳを更新しないようにするこ−とにより、静的な符
号化が容易に実現できる。

第９図は予測変換回路２７のブロック図である。

２値系列信号Ｄ２０３とＭＰＳ１０８がＥＸ−ＮＯＲ回
路２９に入力され、２値付号Ｄ２０３とＭＰＳ１０８が
一致したときに１１不一致のときに０となるＹＮ信号１
０１が出力される。

第７図は、更新回路２５のブロック図である。ＹＮ信号
１０１が１の時、カウンタメモリ２３からのカウント値
Ｃ１０６が加算器３１で＋１インクリメントされ、信号
Ｃ’　１１２になる。この値は比較器３３でカウントテ
ーブルＲＯＭ２２からのＭＣ１０５と比較され、Ｃ′　
の値がＭＣの値に一致したならば、更新信号ＵＰＡ１１
３をセットする。またＹＮ信号１０１は反転器３４を通
り更新信号ＵＰＢ１１４となり、ＵＰＡ。

ＵＰＢはインデックス変更回路３５に入る。また、ＵＰ
ＡとＵＰＢはＯＲ回路３７で論理ＯＲがとられ、ＯＲ回
路３７の出力信号１１５はセレクタ３２の切り換え信号
となる。セレクタ３２では信号１１５が１の時はカウン
タの値をリセットするため０信号１１９を選び、それ以
外は加算器３１の出力信号Ｃ’　１１２を選び、カウン
タ更新信号Ｃ’　１１６として出力し、これをカウンタ
メモリ２３に記憶させる。

インデックス変更回路３５には、インデックスの更新き
ざみを制御する信号ｄｌ１７　（標準的にはｄ＝１）と
ＵＰＡ１１３．ＵＰＢ１１４および符号化条件メモリ２
４から現在のインデックス１１０７が入力されている。

第２表はインデックス変更回路３５におけるインデック
ス更新方法を示すテーブルである（第２表には更新きざ
みがｄ＝１とｄ＝２の場合を示している。）このテーブ
ルを入力１１条件ｄＳＵＰＡ、ＵＰＢで参照することに
より更新したインデックス■′　を決定する。また、Ｉ
＝１でＵＰＢ＝１の時はＥＸ信号１１８をセットする。

ＥＸ信号が１の時に反転器３６では現在のＭＰ３１０８
のシンボルを反転させ（０→ｌまたは１→０）、更新Ｍ
ＰＳ’　１１０を得る。また、ＥＸ信号がＯの時はＭＰ
Ｓ’　　は変化させない。更新されたＩ’　１０９およ
びＭＰＳ’　１１０は符号化条件メモリ２４に記憶され
、次の処理用のインデックスＩ及びＭＰＳとして用いら
れる。尚、第２表に示した更新法は、ＲＯＭなどにより
テーブルでも構成できるし、加減算器を使ってロジック
で構成することも可能である。

以上の如く、２のべき乗の多項式で近似したＬＰＳの出
現確率ｑを表わすインデックスＩの値に応じて定められ
たＭＰＳの数分のＭＰＳが発生したときには、インデッ
クス■をｄ加算し、算術符号に用いるＬＰＳの出現確率
ｑを小さくせしめ、一方、ＬＰＳが発生したときには、
インデックス■をｄ減算し、算術符号に用いるＬＰＳの
出現確率ｑを太き（せしめる。また、更にＬＰＳの出現
確率ｑが０．５を表わすインデックスＩが１の状態にお
いてＬＰＳが発生した場合は、ＭＰＳを反転する。

第８図は算術符号器２８のブロック図である。

符号パラメータ決定回路２６で決められたコントロール
信号Ｑｃｌｌｌ　（第３表）のうちシフトレジスタＡ７
０にＱｌを、シフトレジスタＢにＱ２、セレクタ７２に
Ｑ３が入力される。Ｑｌ、Ｑ２はそれぞれシフトレジス
タＡＳＢに対してＡｕｇｅｎｄ信号であるＡ　ｓ　ｌ　
２３を何ｂｉｔ右にシフトするかを指示する。

シフトされた結果が出力信号１３０．１３１となる。

信号１３１は、反転器７６により補数がとられ、セレク
タ７２はコントロール信号Ｑ３により信号１３１又は反
転器７６の出力信号を選択し、出力信号１３２を得る。

加算器７３ではシフトレジスタＡ７０からの信号１３０
とセレクタ７２からの信号１３２の加算が行われ、Ａｓ
＋信号１２４が出力される。減算器７４では、ＡＳ信号
１２３からＡｓ＋信号１２４を減算し、Ａｓ。

信号１２５を得る。セレクタ７５ではＡｓｏ信号１２５
とＡＳＩ信号１２４のいずれかをＹＮ信号１０１により
選択する。即ちＹＮ信号が１の時はＡｓｏ信号が、また
、ＹＮ信号がＯの時はＡｓ＋信号がＡ′信号１２６にな
る。シフト回路８０ではＡ′　信号のＭＳＢが１になる
まで左ヘシフトする処理が行われ、このシフトによりＡ
Ｓ　　信号１２７が得られる。このシフトの回数に相当
するシフト信号１３２は、コードレジスタ７９に入り、
コードレジスタ７９からはシフト回数に相当する数のｂ
ｉｔがＫＳＢから順番に出力され符号データ１３０にな
る。

符号データ１３０は、図示しないｂｉｔ処理方法にて、
ｂｉｔｌの連続が有限個内になるように処理され、復号
器１４側に伝送されることになる。

また、コードレジスタ７９の内容’ＣＲ１２８は加算器
７７でＡｓｏ信号１２５と加算され、セレクタ７８に入
る。また、Ａｓｏ信号１２５の加算されていない信号Ｃ
Ｒ１２８もセレクタ７８ニ入り、ＹＮ信号１０１が１の
時はｃＲ’　＝ＣＲＳＹＮ信号が０の時はＣＲ’＝ＣＲ
＋ＡｓｏとなるＣＲ’　信号１２９として出力される。

コードレジスタ７９に関して前述したシフト処理はＣＲ
’　信号に対して行う。

以下に、予測状態決定回路１３における参照画素位置の
決定について第１０図を用いて説明する。今、入力され
るハーフトーン画像が誤差拡散法によるものであるとす
る。

誤差拡散画像は一般的に相関の弱いものであると言われ
ているが、その一方で中、低濃度域においては誤差拡散
法の特徴である亀甲紋様が現れる。

従って、誤差拡散用参照画素位置を示すテンプレートは
この点に注目して作られる。

即ち、誤差拡散法に一般によく用いられる１２画素の拡
散マトリクス（第１０図Ａ）を用いて、１画素８ビツト
のグレースケールを２値化したものをトレーニングデー
タとしてまず用意した。

次に第１Ｏ図Ｂの１２画素参照テンプレートを用いてト
レーニング画像のエントロピーを求め、そのうち特にエ
ントロピーの低い状態で、かつ、この画像において発生
頻度の高いものを求め、その状態を１２次次元間にプロ
ットした。プロットされたデータは空間内に一様ではな
く、いくっがのクラスターを作って存在する。各クラス
ターは各々エントロピーが低くなるような周囲情況の似
通ったものの集合である。この中から、他のクラスター
との干渉を抑えた程度に何点かの代表点（主にクラスタ
ーの重心位置付近となり、分散を最も小さ（する点）を
選出し、さらにその中から頻度の高いもののみを抽出し
た。゛この結果得られたのが第１Ｏ図Ｃのテンプレート
である。

通常用いられる文書用のテンプレートは、相関の順位が
決っており、何画素参照するかによってその形が一意に
決まる。このテンプレートを用いて、文書画像のエント
ロピーを測ると参照画素数の増加に対してエントロピー
は下っていくが、８画素参照付近でほとんど飽和してし
まう。

そのときのテンプレートを第１Ｏ図りに示す。

本実施例において提案する１２画素参照テンプレートは
、第１Ｏ図Ｅに示すとおりで、はぼ、第１Ｏ図Ｃと第１
０図りの論理和をとって１２画素にしたものであり、文
書画像についても従来と同等の符号化効率を与える一方
で、誤差拡散画像に対してはかなりの効率の改善を可能
にするものである。今回の提案は１２画素参照用である
が、それ以外のものも全く同様に作成が可能であること
は言うまでもない。

以上の実施例では、１画素１ビツトのモノクロ２値信号
をとりあげて説明をしたが、ＲＧＢ、ＭＭＣ等の３ｂｉ
ｔ力ラー信号及びＹＭＣＫの４ｂｉｔ力ラー信号に対し
ても、それらを面順次に符号化することにより実に容易
に２値カラー画像の符号化に拡張できる。

また文書用と誤差拡散用でテンプレートを切り換えたが
、これもデイザ用を加える等の拡張が可能であることは
言うまでもない。

また、テンプレートを更に複数種設け、これらを画像に
応じて使い分けることにより、更に効率良い符号化が可
能となる。

以上説明したように、２値画像の予測符号化における、
予測に用いるテンプレートを複数もたせ、予測の前処理
として、どのテンプレートを使うがを判定させ、それに
従って予測を行い符号化をすすめることによって符号化
効率は向上するのである。

特に誤差拡散法による疑似中間調画像では、符号量が数
パーセント減少し、明らかな効果がみられる。

また、２値カラー（３ｂｉｔ　　ｏｒ　　４ｂｉｔカラ
ー）画像に対し、面順次に本発明による処理を加えれば
、符号量の減少量は単純計算で３倍になり、より大きな
効果があるといえよう。

第 表 ）はｄｏｎ’ ｃ　ａ　ｒ　ｅ。

〔発明の効果〕

以上説明した様に本発明によると、注目画素近傍領域が
疑似中間調画像であるか否かを判定し、その判定に基づ
いて、符号化画素予測に用いる参照画素テンプレートを
疑似中間調画像用と一般画像用とに適応的に切りかえ、
それに従って画像予測符号化を行うので、入力画像に適
した効率良い画像符号化が達成できる。

【図面の簡単な説明】

第１図は本発明による２値画像の伝送システムのブロッ
ク図、 第２図はラインメモリ部分のブロック図、第３図はハー
フトーン判定器のブロック図、第４図は状態決定回路の
ブロック図、 第５図は参照画素テンプレートを示す図、第６図は符号
器のブロック図、 第７図は更新回路のブロック図、 第８図は算術符号器のブロック図、 第９図は予測変換回路のブロック図、 第１０図はテンプレートの説明用の図であり、１１は符
号器、 １０はラインメモリ、 １２はラッチ 回路、 １５はハーフ トーン検出器、 １３は予測状態 決定回路、 １４は復号器である。 箋３回 鴇４図 ￥１：）図 几 ′ＬＬ査 ″Ｌｔｈ魚 Ｂ

Claims (1)

【特許請求の範囲】
1. 画像予測符号化方式において、注目画素近傍領域が疑似
   中間調画像であるか否かを判定し、その判定に基づいて
   、符号化画素予測に用いる参照画素テンプレートを疑似
   中間調画像用と一般画像用とに適応的に切りかえること
   を特徴とする画像予測符号化方式。