(57)【要約】【課題】予測精度の良い予測誤差生成装置を提供することを目的としている。【解決手段】２値イメージデータを複数の画素からなる画素ブロック毎にシフトし入力するブロックシフトレジスタ手段と、該ブロックシフトレジスタ手段の各々の画素ブロックと注目画素ブロックとの排他的論理和を行うブロック排他的論理和手段と、該ブロック排他的論理和手段の出力を用い画素ブロック毎のカウントを行うブロック予測カウント手段と、該ブロック予測カウント手段の出力を用いて参照画素ブロックのブロック位置更新を行う参照画素ブロック位置更新手段と、該参照画素ブロック位置更新手段出力の参照画素ブロックと注目画素ブロックとの排他的論理和を予測誤差として出力を行う予測誤差出力手段とを備えた。【選択図】  図１
2004159246.tif 000002
【特許請求の範囲】
【請求項１】
周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測誤差生成装置において、２値イメージデータを複数の画素からなる画素ブロック毎にシフトし入力するブロックシフトレジスタ手段と、該ブロックシフトレジスタ手段の各々の画素ブロックと注目画素ブロックとの排他的論理和を行うブロック排他的論理和手段と、該ブロック排他的論理和手段の出力を用い画素ブロック毎のカウントを行うブロック予測カウント手段と、該ブロック予測カウント手段の出力を用いて参照画素ブロックのブロック位置更新を行うを参照画素ブロック位置更新手段と、該参照画素ブロック位置更新手段出力の参照画素ブロックと注目画素ブロックとの排他的論理和を予測誤差として出力を行う予測誤差出力手段とを備えたことを特徴とする予測誤差生成装置。
【請求項２】
前記ブロック予測カウント手段において注目画素ブロックの画素値が全て０の場合にはカウントを行わないことを特徴とする請求項１記載の予測誤差生成装置。
【請求項３】
前記参照画素ブロック位置更新手段においてある画素ブロックに対するブロック予測カウント値が第１の閾値に達しても、現在の参照画素ブロックに対するブロック予測カウント値が第２の閾値を越えている場合には参照画素ブロック位置の更新を行わないことを特徴とする請求項１記載の予測誤差生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像データを高能率に圧縮伸長する画像符号化に用いられる予測誤差生成装置、予測誤差生成方法、及びその記憶媒体に関するものである。
【０００２】
【従来の技術】
プリンタ、スキャナ、複写機、ファクシミリ等の高解像度化、カラー化に伴って、プリンタ、スキャナ等のデータ入出力装置、データ蓄積装置、ネットワーク通信装置などの記憶容量、伝送時間削減のためのデータ圧縮技術が重要となってきている。
【０００３】
プリンタ、複写機等のデータ出力装置で用いる一般的な画像データは２値画像である。従ってこのような２値画像に対して効率的に圧縮を行うことが重要である。２値画像としては、ディザ画像等があり、自然画像等の中間調画像に対してこのような方式で階調変換した２値画像は、ドットの白／黒の変化が頻繁に発生する。そのためロスレス圧縮する場合そのままのデータを符号化するのでなく、スクリーンによる２値画像データやディザ画像は周期的に相関の強い画素が出現することを用い、相関の強い画素を用いて現画素の白／黒の予測を行い（以下、予測符号化と呼ぶ）、予測の当り外れを表す予測誤差データ系列に対してランレングス符号などによる符号化を行って圧縮率の向上を図っている（例えば特許文献１参照）。
【０００４】
以下にスクリーンによる２値画像やディザ画像に対する従来の予測誤差生成手法を説明する。図１０は従来の予測誤差生成装置の構成図である。従来の予測誤差生成装置においては予め発生される可能性のあるスクリーンに対してそのスクリーン間隔およびスクリーン角度に対応する画素ａ，ｂ，ｃ，ｄを観測画素として設定し、ｘを注目画素として注目画素ｘと観測画素のそれぞれとの排他的論理和を行いその結果を観測画素毎にカウントし、判断回路においてスクリーン間隔およびスクリーン角度を求めそれを用いて予測部において予測誤差データを生成している。ここで注目画素ｘおよび観測画素ａ，ｂ，ｃ，ｄはイメージデータの入力に従いシフト方向へと画素データをシフトしていく。図１１は観測画素に合った画像データ例を示す図である。すなわち、図１１は画像スクリーンを用いて生成された入力であり注目ラインを見ると注目画素ｘと観測画素ｃとの相関が見られる。このデータの場合に判断回路は観測画素ｃの位置を相関の最大点としてスクリーン間隔およびスクリーン角度を出力し、予測部はそれを元に予測誤差生成を行う。図１１の例で観測画素ｃをもとに予測誤差を求めた場合は全て一致して予測誤差データとしては全て一致したデータ例えば全て“０”のデータ出力が行われる。
【０００５】
【特許文献１】
特許第２７９７９５０号公報（図１）
【０００６】
【発明が解決しようとする課題】
しかしながら、上記従来の方法では、予め相関の強い画素の数画素を観測画素として固定しており、画像スクリーンの相関に対しては予測精度が良いが、ビジネス文書等に良く見られる画像スクリーンと異なる相関間隔を持つパターンによる描画、例えば斜線等の背景など、に対しては例えば図１２の観測画素の合わない画像データ例を示す図に示すように、画像データが入力された場合に観測画素ａ，ｂ，ｃ，ｄとは相関が取れずに予測精度が悪化するという問題点を有していた。この場合には図１２において更にｅの位置を観測画素として予め用意しておけばいいが、このような観測画素がパターン描画画像においては様々な観測位置が必要とされて観測画素が多数必要となり判断回路の判断も複雑化してしまうという問題点がある。
【０００７】
本発明は上記従来の問題点を解決するもので、画像スクリーンおよび画像スクリーンと異なる相関間隔を持つパターン描画部の双方に対して予測精度の良い予測誤差生成装置を提供することを目的としている。
【０００８】
【課題を解決するための手段】
上記課題を解決するために、本発明は画素ブロック毎に注目画素ブロックとの排他的論理和を行い、その結果により画素ブロック毎にブロック予測カウントを行うことにより１画素毎に予測カウントを行う場合に比べ注目画素より遠くの画素に対する相関をより少ないカウンタで検出でき、また処理が画素ブロック毎に行われる為により高速な予測誤差生成が行え、参照画素ブロック位置を任意に決定できるため、画像スクリーンだけでなくスクリーン間隔とは異なるパターン描画部でも予測精度の良い予測誤差生成装置が得られる。
【０００９】
【発明の実施の形態】
本発明の請求項１に記載の発明は、周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測誤差生成装置において、２値イメージデータを複数の画素からなる画素ブロック毎にシフトし入力するブロックシフトレジスタ手段と、該ブロックシフトレジスタ手段の各々の画素ブロックと注目画素ブロックとの排他的論理和を行うブロック排他的論理和手段と、該ブロック排他的論理和手段の出力を用い画素ブロック毎のカウントを行うブロック予測カウント手段と、該ブロック予測カウント手段の出力を用いて参照画素ブロックのブロック位置更新を行うを参照画素ブロック位置更新手段と、該参照画素ブロック位置更新手段出力の参照画素ブロックと注目画素ブロックとの排他的論理和を予測誤差として出力を行う予測誤差出力手段とを備えたことにより、画像スクリーンおよびパターン描画部の双方に対して予測精度の良い予測誤差生成を行うことができるという作用を有する。
【００１０】
請求項２に記載の発明は、ブロック予測カウント手段において注目画素ブロックの画素値が全て０の場合にはカウントを行わないことにより白背景部等での参照画素変更が行われずに予測精度の良い予測誤差生成を行うことができるという作用を有する。
【００１１】
請求項３に記載の発明は、参照画素ブロック位置更新手段においてある画素ブロックに対するブロック予測カウント値が第１の閾値に達しても、現在の参照画素ブロックに対するブロック予測カウント値が第２の閾値を越えている場合には参照画素ブロック位置の更新を行わないことにより頻繁な参照画素ブロック位置変更が行われない予測誤差生成を行うことができるという作用を有する。
【００１２】
（実施の形態１）
以下、本発明の実施の形態１について説明する。図１は本発明の実施の形態１における予測誤差生成装置を用いた画像符合化装置のブロック図を表している。
【００１３】
図１において１は本発明の予測誤差生成装置全体を示す。１の予測誤差生成装置は２のブロックシフトレジスタ手段、３のブロック排他的論理和手段、４のブロック予測カウント手段、５の参照画素ブロック位置更新手段、および６の予測誤差出力手段から構成される。
【００１４】
図２に本発明の実施の形態１におけるブロックシフトレジスタ手段構成図を示す。図２において８は画素ブロックを示す。図３は本発明の実施の形態１における画素ブロック図であり、画素１０の１画素を８画素分をまとめたもので構成される。またブロックシフトレジスタ手段２は観測画素ブロックとなる３２個の画素ブロック８のおよび注目画素ブロック９から構成され、図２のように画素ブロック毎にシフト方向へとシフトする。
【００１５】
図４は本発明の実施の形態１におけるブロック排他的論理和手段構成図を表している。ブロックシフトレジスタ手段２における観測画素ブロックと注目画素ブロック９とをビット毎に排他的論理和をとり、８ビットから構成される画素ブロック排他的論理和出力１１を生成する。これを観測画素ブロックの３２ブロックに対して行い、ブロック排他的論理和手段の出力とする。
【００１６】
図５は本発明の実施の形態１におけるブロック予測カウント手段フローチャートである。ブロック予測カウント手段においてはＳ１００において観測画素ブロックにおける図４のブロック排他的論理和手段により得られた画素ブロック排他的論理和１１の出力値が０であればＳ１０１へ進み、０でなければカウントを行わずに終了する。またＳ１０１で９の注目画素ブロックの８画素が全て０であるかを判断し、０であればカウントを行わずに終了し、０でなければＳ１０２においてその観測画素ブロックにおけるブロック予測カウント値を１だけインクリメントして終了する。
【００１７】
図６は本発明の実施の形態１における参照画素ブロック位置更新手段フローチャート、図７は予測誤差データ生成例を示す図である。まずＳ１０３においてブロック予測カウント手段４から出力された各々のブロック予測カウント値の中でいずれかのブロック予測カウント値が第１の閾値に達しているかどうかを判定し、達していなければ参照ブロック位置の更新を行わずに終了し、達していればＳ１０４へと進む。Ｓ１０４においては現在の参照ブロック位置に対応するブロック予測カウント値が第２の閾値以上であるかどうかを判定し、閾値以上であればＳ１０６へ進み全ての観測画素ブロックに対応するブロック予測カウント値を０にして終了し、そうでなければＳ１０５へと進む。Ｓ１０５においては予測誤差出力手段６による予測誤差出力を行った後に参照ブロック位置をＳ１０３で検出したブロック予測カウント値が第１の閾値に達した画素ブロックの１つへと更新を行い、Ｓ１０６において全ての観測画素ブロックに対応するブロック予測カウント値を０にして終了する。
【００１８】
図１の予測誤差出力手段６は図２の注目画素ブロック９と現在の参照画素ブロックとの排他的論理和をとり、８ビットのデータを予測誤差データとして出力を行う。例としては図７のような参照画素ブロックデータと注目画素ブロックデータの場合には予測誤差データとしては１ビットのみが１となる予測誤差データが得られる。
【００１９】
本発明の実施の形態１の画像符号化装置では、本発明の図１の予測誤差生成装置１の予測誤差データ出力を用いて、図１のランレングス符号化器７を用いることにより、符号化を行っている。ランレングス符号化器７は組織的な符号であるＷｙｌｅ符号を用いて符合化を行う。図８は本発明の実施の形態１におけるランレングス符号化器のラン長カウント例を示す図である。図９は本発明の実施の形態１におけるランレングス符号化器のＷｙｌｅ符号テーブルを示す図である。図８は予測誤差生成装置出力３画素ブロック分のデータ２４ビットで、ラン長としてはビット値“１”から次のビット値“１”までのビット値“０”の個数を計数してラン長とする。図８の例では｛６，０，６，８｝となる。そのラン長に対して図９のＷｙｌｅ符号の割り当てを行い符号化を行う。図９でＷｙｌｅ符号の＊の部分には０〜３のラン長以外ではラン長から図９の当てはまるラン長範囲の最小値を引いたものをビット表現で置き換え、ラン長０〜３の場合にはラン長そのものをビット表現で置き換える。図８の例ではラン長６に対しては“１０”と６−４＝２をビット表現した“１０”、ラン長０に対しては“０”と０をビット表現した“００”、ラン長８に対しては“１１０”と８−８＝０をビット表現した“０００”が符号として割り当てられ、“１０１００００１１００００”１３ビットの符号がランレングス符号化器の符号出力として出力される。
【００２０】
以上のようにして本発明の予測誤差生成装置を用いた画像符号化装置の画像符号化が行われる。
【００２１】
以上のように、前述した実施の形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、本発明の目的が達成されることは言うまでもない。
【００２２】
この場合、記憶媒体から読み出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００２３】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピー（Ｒ）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＥＥＰＲＯＭ等を用いることができる。
【００２４】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）等が実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実施される場合も含まれることは言うまでもない。
【００２５】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【００２６】
【発明の効果】
以上のように本発明によれば、周辺画素を用いて画素値の予測を行い、予測値の当り外れを表す予測誤差データ系列を作成する予測誤差生成装置において、２値イメージデータを複数の画素からなる画素ブロック毎にシフトし入力するブロックシフトレジスタ手段と、該ブロックシフトレジスタ手段の各々の画素ブロックと注目画素ブロックとの排他的論理和を行うブロック排他的論理和手段と、該ブロック排他的論理和手段の出力を用い画素ブロック毎のカウントを行うブロック予測カウント手段と、該ブロック予測カウント手段の出力を用いて参照画素ブロックのブロック位置更新を行うを参照画素ブロック位置更新手段と、該参照画素ブロック位置更新手段出力の参照画素ブロックと注目画素ブロックとの排他的論理和を予測誤差として出力を行う予測誤差出力手段とを備えたことを特徴とする予測誤差生成装置であって、観測画素ブロックと注目画素ブロックとの排他的論理和出力を用いたカウンタを備え参照画素ブロックを逐次更新することにより、様々な画像スクリーンおよびパターン描画画像において良好な予測誤差を生成できる予測誤差生成装置を実現することができる。
【００２７】
また、前記ブロック予測カウント手段において注目画素ブロックの画素値が全て０の場合にはカウントを行わないことにより白背景部等でのカウントを行わないので、予測精度の良い予測誤差生成を行う予測誤差生成装置を実現することができる。
【００２８】
また、前記参照画素ブロック位置更新手段においてある画素ブロックに対するブロック予測カウント値が第１の閾値に達しても、現在の参照画素ブロックに対するブロック予測カウント値が第２の閾値を越えている場合には参照画素ブロック位置の更新を行わないことにより頻繁な参照画素ブロック位置の更新を行わない予測誤差生成装置を実現することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態１における予測誤差生成装置を用いた画像符号化装置のブロック図
【図２】本発明の実施の形態１におけるブロックシフトレジスタ手段構成図
【図３】本発明の実施の形態１における画素ブロック図
【図４】本発明の実施の形態１におけるブロック排他的論理和手段構成図
【図５】本発明の実施の形態１におけるブロック予測カウント手段フローチャート
【図６】本発明の実施の形態１における参照画素ブロック位置更新手段フローチャート
【図７】予測誤差データ生成例を示す図
【図８】本発明の実施の形態１におけるランレングス符号化器のラン長カウント例を示す図
【図９】本発明の実施の形態１におけるランレングス符号化器のＷｙｌｅ符号テーブルを示す図
【図１０】従来の予測誤差生成装置の構成図
【図１１】観測画素に合った画像データ例を示す図
【図１２】観測画素の合わない画像データ例を示す図
【符号の説明】
１  予測誤差生成装置
２  ブロックシフトレジスタ手段
３  ブロック排他的論理和手段
４  ブロック予測カウント手段
５  参照画素ブロック位置更新手段
６  予測誤差出力手段
７  ランレングス符号化器
８  画素ブロック
９  注目画素ブロック
１０  画素
１１  画素ブロック排他的論理和出力
【図１】
2004159246.tif 000003
【図２】
2004159246.tif 000004
【図３】
2004159246.tif 000005
【図４】
2004159246.tif 000006
【図５】
2004159246.tif 000007
【図６】
2004159246.tif 000008
【図７】
2004159246.tif 000009
【図８】
2004159246.tif 000010
【図９】
2004159246.tif 000011
【図１０】
2004159246.tif 000012
【図１１】
2004159246.tif 000013
【図１２】
2004159246.tif 000014