(57)【要約】【課題】  簡単な処理或いは回路規模で、階調画像をはじめ、従来苦手としていた縦縞部分あるいは文字部分に対して高い圧縮率の符号化データを生成すると共に、復号する側での簡単な処理或いは回路規模で復号することを可能とする。【解決手段】  画像データを入力端子１０９より入力する。参照画素値記憶部１０１はディザマトリクスの１周期分の画像データを記憶する。第１予測部１０２は参照画素値記憶部１０１に記憶されている１周期未満の閾値を参照して注目画素の予測値を求める。第２予測部１０４は注目画素の１周期前の画素値と予測値として決定する。連続性判定部１０５は、注目画素の直前から３つ前までの各画素値と、ディザマトリクスの１周期分だけ前の３つの画素値とをそれぞれ比較し、一致数が不一致数より多いか否かを判定し、その結果を予測値選択部１０６に出力する。予測値選択部はこの判定結果に従って一方の予測値を選択し、符号化部１０７は選択された予測値と注目画素の差分を符号化する。【選択図】  図１
2005323326.tif 000002
【特許請求の範囲】
【請求項１】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データを符号化する画像符号化装置であって、
前記所定周期未満の距離にある近傍画素を参照して、注目画素の予測値を求める第１の予測手段と、
注目画素から前記所定周期の整数倍だけ隔てた画素の値を、注目画素の予測値として求める第２の予測手段と、
注目画素の前記所定周期未満の距離にある所定数の近傍画素群と、前記近傍画素群に対して前記所定周期だけ隔てた同位相の画素群との相関度を求める相関度演算手段と、
該相関度演算手段により求めた相関度が所定閾値以上の場合には、前記第２の予測手段による予測値を選択し、前記相関度が前記所定閾値未満である場合には前記第１の予測手段による予測値を選択する選択手段と、
選択した予測値と前記注目画素の値とに基づいて、該注目画素の値を符号化する符号化手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
前記第１の予測手段は、注目画素の直前の画素値、及び、注目画素を量子化する際に用いた閾値、直前の画素を量子化する際に用いた閾値に基づいて予測値を求めることを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記第１の予測手段は、前記注目画素位置の直前からｎ個前までの近傍画素群の量子化値が同じである場合にはその値を注目画素の予測値とし、前記注目画素位置の直前からｎ個前までの近傍画素群の量子化値に不一致なものがある場合には、注目画素の量子化閾値と、注目画素の直前画素の量子化閾値の大小判定に基づいて予測値を決定することを特徴とする請求項１に記載の画像符号化装置。
【請求項４】
前記第１の予測手段は、前記注目画素の近傍の画素群の画素値と各画素の濃度クラスに基づいて、該注目画素の予測値を決定することを特徴とする請求項１に記載の画像符号化装置。
【請求項５】
前記量子化は、各入力画素に対応した属性情報に応じて量子化閾値を切り替えることを特徴とする請求項１に記載の画像符号化装置。
【請求項６】
前記相関度演算手段は、
注目画素をＤ0、注目画素の前記所定周期未満の距離にある所定数をｎと定義した際の近傍画素群をＤ-1,Ｄ-2,…Ｄ-n、前記所定周期をｐと定義した際の前記同位相の画素群をＤ-p-1,Ｄ-p-2,…、Ｄ-p-nと表わした場合、
Ｄ-1とＤ-p-1、
Ｄ-2とＤ-p-2、
：
Ｄ-nとＤ-p-n
の各組の一致数を、相関度として算出することを特徴とする請求項１乃至５のいずれか１つ記載の画像符号化装置。
【請求項７】
前記符号化手段は、前記予測値と前記注目画素の値との差分に基づいて、該注目画素の値を符号化することを特徴とする請求項１乃至６のいずれか１項に記載の画像符号化装置。
【請求項８】
前記符号化手段は、前記予測値と前記注目画素の値とが一致したか不一致であるかを示す符号と、不一致の場合には後続して注目画素の値を示す符号を生成することを特徴とする請求項１乃至６のいずれか１項に記載の画像符号化装置。
【請求項９】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データの符号データを復号する画像復号装置であって、
前記所定周期未満の距離にある既復号の近傍画素を参照して、注目画素の予測値を求める第１の予測手段と、
注目画素から前記所定周期の整数倍だけ隔てた既復号の画素の値を、注目画素の予測値として求める第２の予測手段と、
注目画素の前記所定周期未満の距離にある所定数の既復号の近傍画素群と、前記近傍画素群に対して前記所定周期だけ隔てた同位相の既復号の画素群との相関度を求める相関度演算手段と、
該相関度演算手段により求めた相関度が所定閾値以上の場合には、前記第２の予測手段による予測値を選択し、前記相関度が前記所定閾値未満である場合には前記第１の予測手段による予測値を選択する選択手段と、
選択した予測値と符号に基づいて、前記注目画素を表わす復号値を出力する復号手段と  を備えることを特徴とする画像復号装置。
【請求項１０】
前記復号手段は、前記予測値と前記符号で示される差分値とを加算することで、前記注目画素を表わす復号値を出力することを特徴とする請求項９に記載の画像復号装置。
【請求項１１】
前記復号手段は、前記符号が、画素値と予測値が一致することを示す符号であった場合には予測値を注目画素を表わす復号値として出力し、不一致を示す符号があった場合には後続する符号に対応する値を注目画素を表わす復号値として出力することを特徴とする請求項９に記載の画像復号装置。
【請求項１２】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データを符号化する画像符号化装置の制御方法であって、
前記所定周期未満の距離にある近傍画素を参照して、注目画素の予測値を求める第１の予測工程と、
注目画素から前記所定周期の整数倍だけ隔てた画素の値を、注目画素の予測値として求める第２の予測工程と、
注目画素の前記所定周期未満の距離にある所定数の近傍画素群と、前記近傍画素群に対して前記所定周期だけ隔てた同位相の画素群との相関度を求める相関度演算工程と、
該相関度演算工程により求めた相関度が所定閾値以上の場合には、前記第２の予測工程による予測値を選択し、前記相関度が前記所定閾値未満である場合には前記第１の予測工程による予測値を選択する選択工程と、
選択した予測値と前記注目画素の値とに基づいて、該注目画素の値を符号化する符号化工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項１３】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データの符号データを復号する画像復号装置の制御方法であって、
前記所定周期未満の距離にある既復号の近傍画素を参照して、注目画素の予測値を求める第１の予測工程と、
注目画素から前記所定周期の整数倍だけ隔てた既復号の画素の値を、注目画素の予測値として求める第２の予測工程と、
注目画素の前記所定周期未満の距離にある所定数の既復号の近傍画素群と、前記近傍画素群に対して前記所定周期だけ隔てた同位相の既復号の画素群との相関度を求める相関度演算工程と、
該相関度演算工程により求めた相関度が所定閾値以上の場合には、前記第２の予測工程による予測値を選択し、前記相関度が前記所定閾値未満である場合には前記第１の予測工程による予測値を選択する選択工程と、
選択した予測値と符号に基づいて、前記注目画素を表わす復号値を出力する復号工程と  を備えることを特徴とする画像復号装置の制御方法。
【請求項１４】
請求項１２又は１３の制御方法の各工程の処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項１５】
請求項１４に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項１６】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データを、各画素毎の文字線画領域／非文字線画領域のいずれであるかを示す属性データを用いて符号化する画像符号化装置であって、
前記所定周期未満の距離にある近傍画素を参照して、注目画素の予測値を求める第１の予測手段と、
注目画素から前記所定周期の整数倍だけ隔てた画素の値を、注目画素の予測値として求める第２の予測手段と、
注目画素の属性データが文字線画領域を示す場合には前記第１の予測手段による予測値を選択し、注目画素の属性データが非文字線画領域を示す場合には前記第２の予測手段による予測値を選択する選択手段と、
選択した予測値と注目画素の値とに基づいて、該注目画素の値を符号化する符号化手段と
を備えることを特徴とする画像符号化装置。
【請求項１７】
前記第１の予測手段は、
注目画素から前記所定周期未満の距離にある近傍画素群中の、前記注目画素に最も近い位置にある文字線画領域の属性データを持った画素値を探索する探索手段と、
該探索手段で探索に成功した場合には、当該探索した画素値を予測値として決定し、探索に失敗した場合には所定値を予測値として決定する手段と
を含むことを特徴とする請求項１６に記載の画像符号化装置。
【請求項１８】
前記第１の予測手段は、注目画素から前記所定周期未満の距離にある近傍画素群の中央値を予測値として求めることを特徴とする請求項１６又は１７に記載の画像符号化装置。 
【請求項１９】
前記符号化手段は、前記予測値と前記注目画素の値との差分に基づいて符号を生成することを特徴とする請求項１６乃至１８のいずれか１項に記載の画像符号化装置。
【請求項２０】
前記符号化手段は、前記予測値と前記注目画素の値とが一致したか不一致であるかを示す符号と、不一致の場合には後続して注目画素値を示す符号を生成することを特徴とする請求項１６乃至１８のいずれか１項に記載の画像符号化装置。
【請求項２１】
更に、前記属性データを符号化する属性データ符号化手段と、
該属性データ符号化手段による符号化データと前記画像符号化手段による符号化データを合成する合成手段と
を備えることを特徴とする請求項１６乃至２０のいずれか１項に記載の画像符号化装置。
【請求項２２】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データが、各画素毎の文字線画領域／非文字線画領域のいずれであるかを示す属性データを用いて符号化された符号データを復号する画像復号装置であって、
前記所定周期未満の距離にある既復号の近傍画素を参照して、注目画素の予測値を求める第１の予測手段と、
注目画素から前記所定周期の整数倍だけ隔てた既復号の画素の値を、注目画素の予測値として求める第２の予測手段と、
注目画素の属性データが文字線画領域を示す場合には前記第１の予測手段による予測値を選択し、注目画素の属性データが非文字線画領域を示す場合には前記第２の予測手段による予測値を選択する選択手段と、
選択した予測値と符号に基づいて、前記注目画素を表わす復号値を出力する復号手段と  を備えることを特徴とする画像復号装置。
【請求項２３】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データを、各画素毎の文字線画領域／非文字線画領域のいずれであるかを示す属性データを用いて符号化する画像符号化装置の制御方法であって、
前記所定周期未満の距離にある近傍画素を参照して、注目画素の予測値を求める第１の予測工程と、
注目画素から前記所定周期の整数倍だけ隔てた画素の値を、注目画素の予測値として求める第２の予測工程と、
注目画素の属性データが文字線画領域を示す場合には前記第１の予測工程による予測値を選択し、注目画素の属性データが非文字線画領域を示す場合には前記第２の予測工程による予測値を選択する選択工程と、
選択した予測値と注目画素の値とに基づいて、該注目画素の値を符号化する符号化工程と
を備えることを特徴とする画像符号化装置の制御方法。
【請求項２４】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データが、各画素毎の文字線画領域／非文字線画領域のいずれであるかを示す属性データを用いて符号化された符号データを復号する画像復号装置の制御方法であって、
前記所定周期未満の距離にある既復号の近傍画素を参照して、注目画素の予測値を求める第１の予測工程と、
注目画素から前記所定周期の整数倍だけ隔てた既復号の画素の値を、注目画素の予測値として求める第２の予測工程と、
注目画素の属性データが文字線画領域を示す場合には前記第１の予測工程による予測値を選択し、注目画素の属性データが非文字線画領域を示す場合には前記第２の予測工程による予測値を選択する選択工程と、
選択した予測値と符号に基づいて、前記注目画素を表わす復号値を求める復号工程と
を備えることを特徴とする画像復号装置の制御方法。
【請求項２５】
請求項２３又は２４の制御方法の各工程の処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２６】
請求項２５に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項２７】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データを符号化する画像符号化装置であって、
前記所定周期未満の距離にある１個以上の近傍画素の量子化値と、前記近傍画素の量子化閾値と、注目画素の量子化閾値を参照して、当該注目画素の予測値を求める予測値演算手段と、
当該予測値と前記注目画素の値とに基づいて、該注目画素の値を符号化する符号化手段と
を備えることを特徴とする画像符号化装置。
【請求項２８】
前記予測値演算手段は、
注目画素位置の直前からｎ個前までの近傍画素群の量子化値が同じである場合、その値を注目画素の予測値とし、
注目画素位置の直前からｎ個前までの近傍画素群の量子化値に不一致がある場合、注目画素の量子化閾値と、注目画素の直前画素の量子化閾値の大小判定に基づいて予測値を決定する
ことを特徴とする請求項２７に記載の画像符号化装置。
【請求項２９】
前記量子化処理は、ディザ閾値を有するディザマトリクスを利用した２値化手段であることを特徴とする請求項２７または２８に記載の画像符号化装置。
【請求項３０】
前記量子化処理は、各入力画素に対応した属性情報に応じて量子化閾値を切り替えることを特徴とする請求項２７乃至２９のいずれか１つに記載の画像符号化装置。
【請求項３１】
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データを符号化する画像符号化装置の制御方法であって、
注目多値画素値と当該注目画素用の量子化閾値と比較することで注目画素の量子化値を求める量子化処理工程と、
注目画素位置の直前からｎ個前までの量子化値、及び、注目画素の量子化処理で使用する量子化閾値と、注目画素の直前画素の量子化閾値に基づいて、注目画素の量子化値の予測値を演算する予測値演算工程と、
前記量子化処理工程で処理された注目画素の量子化値が、前記予測演算工程で求めた注目画素位置の予測値に一致するか否かを示す予測誤差データを生成する予測誤差生成工程とを備え、
該予測誤差生成工程で生成された予測誤差データを符号化対象データとすることを特徴とする画像符号化装置の制御方法。
【請求項３２】
多値画像データを量子化処理し、当該量子化処理した結果を圧縮符号化する画像処理装置として機能するコンピュータプログラムであって
注目多値画素値と当該注目画素用の量子化閾値と比較することで注目画素の量子化値を求める量子化処理手段と、
注目画素位置の直前からｎ個前までの量子化値、及び、注目画素の量子化処理で使用する量子化閾値と、注目画素の直前画素の量子化閾値に基づいて、注目画素の量子化値の予測値を演算する予測値演算手段と、
前記量子化処理手段で処理された注目画素の量子化値が、前記予測演算手段で求めた注目画素位置の予測値に一致するか否かを示す予測誤差データを生成する予測誤差生成手段として機能し、
該予測誤差生成手段で生成された予測誤差データを符号化対象データとする
ことを特徴とするコンピュータプログラム。
【請求項３３】
請求項３２に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項３４】
請求項２７の装置で圧縮符号化された画像データを復号する画像処理装置であって、
量子化処理後のデータが予測値に一致するか否かを示す予測誤差データにまで復号する復号手段と、
注目画素位置の直前からｎ個前までの量子化値、及び、注目画素の量子化処理で使用する量子化閾値と、注目画素の直前画素の量子化閾値に基づいて、注目画素の量子化値の予測値を演算する予測値演算手段と、
前記復号手段で得られた注目画素の予測誤差データと、前器予測演算手段で得られた注目画素の予測値とが一致するか否かを判断する判断手段と、
該判断手段の判断結果に基づいて、注目画素の量子化値を生成する生成手段と
を備えることを特徴とする画像処理装置。
【請求項３５】
請求項２７の装置で圧縮符号化された画像データを復号する画像処理装置の制御方法であって、
量子化値が予測値に一致するか否かを示す予測誤差データにまで復号する復号工程と、
注目画素位置の直前からｎ個前までの量子化値、及び、注目画素の量子化処理で使用する量子化閾値と、注目画素の直前画素の量子化閾値に基づいて、注目画素の量子化値を演算する予測値演算工程と、
前記復号工程で得られた注目画素の予測誤差データと、前器予測演算工程で得られた注目画素の予測値とが一致するか否かを判断する判断工程と、
該判断工程の判断結果に基づいて、注目画素の量子化値を生成する生成工程と
を備えることを特徴とする画像処理装置の制御方法。
【請求項３６】
請求項２７の装置で圧縮符号化された画像データを復号する画像処理装置として機能するコンピュータプログラムであって、
量子化値が予測値に一致するか否かを示す予測誤差データにまで復号する復号手段と、
注目画素位置の直前からｎ個前までの量子化値、及び、注目画素の量子化処理で使用する量子化閾値と、注目画素の直前画素の量子化閾値に基づいて、注目画素の量子化値の予測値を演算する予測値演算手段と、
前記復号手段で得られた注目画素の予測誤差データと、前器予測演算手段で得られた注目画素の予測値とが一致するか否かを判断する判断手段と、
該判断手段の判断結果に基づいて、注目画素の量子化値を生成する生成手段
として機能することを特徴とするコンピュータプログラム。
【請求項３７】
請求項３６に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【請求項３８】
既知の階調変換処理を施された入力画像データを符号化処理する画像処理装置であって、
各入力画素に対応した濃度クラスを与える濃度クラス付与手段と、
符号化対象の画素に対する予測値を、当該画素の近傍の画素群の画素値と各画素の濃度クラスを用いて求める予測値計算手段と、
当該画素の画素値と当該画素の予測値との差分に応じた符号を出力する符号化手段とを備え、
前記符号化手段により前記画像の符号化データを生成することを特徴とする画像処理装置。
【請求項３９】
前記閾値および前記予測値は、各入力画素に対応した属性情報に応じて決定されることを特徴とする請求項３８に記載の画像処理装置。
【請求項４０】
既知の階調変換処理を施された入力画像データを符号化処理する画像処理装置の制御方法であって、
各入力画素に対応した濃度クラスを与える濃度クラス付与工程と、
符号化対象の画素に対する予測値を、当該画素の近傍の画素群の画素値と各画素の濃度クラスを用いて求める予測値計算工程と、
当該画素の画素値と当該画素の予測値との差分に応じた符号を出力する符号化工程とを備え、
前記符号化工程により前記画像の符号化データを生成する
ことを特徴とする画像処理装置の制御方法。
【請求項４１】
既知の階調変換処理を施された入力画像データを符号化処理する画像処理装置として機能するコンピュータプログラムであって、
各入力画素に対応した濃度クラスを与える濃度クラス付与手段と、
符号化対象の画素に対する予測値を、当該画素の近傍の画素群の画素値と各画素の濃度クラスを用いて求める予測値計算手段と、
当該画素の画素値と当該画素の予測値との差分に応じた符号を出力する符号化手段として機能し、
前記符号化手段により前記画像の符号化データを生成する
ことを特徴とするコンピュータプログラム。
【請求項４２】
請求項４１に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像データの符号化及び復号に関するものである。
【背景技術】
【０００２】
画像データを圧縮符号化する場合、隣接する画素データが同一の値をもつ傾向が高いことを利用して圧縮するのが一般的である。
【０００３】
このような圧縮方法の一つとして、ランレングス符号化技術が知られている。ランレングス符号は、同一データが繰り返す場合に繰り返しの長さ（回数）とデータを符号化するものである。また別の圧縮方法としてデルタロウ符号を用いる方法がある。デルタロウ符号は直前のラインと同じデータが続いている場合に、続いている長さを符号化するものである。また、別の圧縮方法として予測符号がある。この予測符号は、近隣の数画素、例えば直左と直上の画素から注目画素の予測値を計算し、注目画素値と予測値の差分、すなわち予測誤差を符号化するものである。この他にも隣接画素を参照する様々な圧縮方式が提案されている。
【０００４】
ところで、例えば１画素が８ビット（２５６階調）のグレイスケール原画像を４ビット（１６階調）のグレイスケール画像に減色する場合、ディザマトリクスを用いて各マトリクス内の画素ごとに異なった閾値による演算処理を行って減色するのが一般的である。このようなディザマトリクスを利用して減色する場合には、例え原画像中の隣接画素値が同じであっても、隣接する画素の減色に使用される閾値が異なるので、減色後の隣接画素値は異なった値になることが多く、上述の方法では高い圧縮率は望めなない。
【０００５】
ディザマトリクスは周期的に適用されるため、隣接画素ではなく、むしろ少し離れた画素、通常はディザマトリクスの周期（サイズ）だけ離れた画素との相関が高くなる。したがってこの問題を解決するためには、隣接画素の代わりに、ディザマトリクスのサイズに応じた距離だけ隔てた画素を参照すればよい。
【０００６】
このような周期性を持つ減色処理には、ディザ処理のほか、ハーフトーン処理が知られている。ハーフトーン処理もまた、周期的に繰り返す閾値と入力画素値の比較によって出力画素値を決定する画像処理方法である。
【０００７】
そこで、この問題を軽減するために、ディザマトリックスの周期に応じて、スキャンラインを並べ替える、いわゆるインタレース処理を行うことが知られている。例えば、４画素×４画素のディザマトリクスを使用する場合、４ラインごとに飛び飛びにスキャンラインを並べることにより、垂直方向には相関の高い画素が並ぶ。しかし、水平方向は改善されないとともに、並べ替えという余分な処理が加わるため、符号化の処理時間が長くなるという欠点がある。
【０００８】
また、ディザマトリクスの周期に応じて、水平方向に画素を並び替える技術も知られている（特許文献１）。しかしながらこの方法によれば、水平方向には相関の高い画素が並ぶが、垂直方向は改善されないとともに、並べ替えという余分な処理が加わるだけでなく、画素単位での並べ替えであるため、画素が８ビット未満の場合、８ビットを最低処理単位とする通常のコンピュータで処理を行う場合にオーバーヘッドが大きいという欠点がある。
【０００９】
また、隣接するブロックを参照することにより、データの並べ替えを行うことなしに、相関の高い画素を参照する技術もある（特許文献２）。しかしながらこの方法によれば、垂直方向の相関を利用できない。よって、水平方向の相関が低く、垂直方向の相関が高い画像、たとえばブロックの幅と等しい縦縞の画像において圧縮率を高くすることが出来ないという欠点がある。
【００１０】
更に、近傍画素群の画素値を用いた予測技術もある（特許文献３）。しかしながら、上記縦縞の画像に対して効果的な圧縮を施すためには上方の画素を参照する必要があり、ある程度の大きさのメモリが必要となる。
【００１１】
そのほかにもＬＺ７７符号、ＬＺ７８符号、ＪＢＩＧ符号、ＪＰＥＧ符号など様々な符号が考案されているが、いずれも符号化における計算量が多く、ソフトウェアで符号化した場合に符号化にかなりの時間を要し、またハードウェアで復号した場合に復号器の規模も大きくなるという欠点がある。
【特許文献１】特許第２６９４８２６号公報
【特許文献２】特開平８−２２３４２８号公報
【特許文献３】特開２００３−１７４５６１公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は上記課題に鑑みなされたものであり、特にディザ処理等の周期的に変化する閾値で少ない階調数に量子化された画像データを、簡単な処理で、しかも劣化の少ない圧縮符号化を行う技術を提供しようとするものである。
【００１３】
また、本発明は、上記のようにして符号化データを復号する際の計算量を小さくすると共に、復号をハードウェアで行う場合には復号に要する回路規模を縮小させる技術を提供しようとするものである。
【課題を解決するための手段】
【００１４】
この課題を解決する本発明の画像符号化装置は以下の構成を備える。すなわち、
所定周期で変化する閾値を用い、多値画像データの１画素当たりの階調数をより少ない階調数に量子化した画像データを符号化する画像符号化装置であって、
前記所定周期未満の距離にある近傍画素を参照して、注目画素の予測値を求める第１の予測手段と、
注目画素から前記所定周期の整数倍だけ隔てた画素の値を、注目画素の予測値として求める第２の予測手段と、
注目画素の前記所定周期未満の距離にある所定数の近傍画素群と、前記近傍画素群に対して前記所定周期だけ隔てた同位相の画素群との相関度を求める相関度演算手段と、
該相関度演算手段により求めた相関度が所定閾値以上の場合には、前記第２の予測手段による予測値を選択し、前記相関度が前記所定閾値未満である場合には前記第１の予測手段による予測値を選択する選択手段と、
選択した予測値と前記注目画素の値とに基づいて、該注目画素の値を符号化する符号化手段とを備える。
【発明の効果】
【００１５】
本発明によれば、簡単な処理或いは回路規模で、階調画像をはじめ、従来苦手としていた縦縞部分あるいは文字部分に対して高い圧縮率の符号化データを生成すると共に、復号する側での簡単な処理或いは回路規模で復号することが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１７】
＜第１の実施形態＞
図１４は本実施形態における画像圧縮符号化装置の概略ブロック図である。本実施形態では注目画素近傍の画素値からの１種類の予測値を生成する例を説明する。
【００１８】
図示において、量子化部１４０１は、閾値行列（ディザマトリクスの閾値係数）を格納するための閾値行列記憶部１４０４と、画像データと閾値の比較によって２値化を行う閾値比較部１４０５で構成される。この量子化部１４０１の出力は予測値計算手段である予測値計算部１４０２と、符号化部１４０３に伝達される。
【００１９】
予測値計算部１４０２はこれまでの出力画素値と量子化に用いる閾値から予測値を計算する。ここで得られた予測値は符号化部１４０３に伝達される。
【００２０】
符号化部１４０３は予測値と出力画素値（２値化結果）とが一致したか否かを判定する判定部１４０６と、判定部１４０６からの出力を圧縮して最終出力である符号化データを可逆圧縮符号化し、その結果を出力する圧縮符号化部１４０７とで構成されている。
【００２１】
以下、上記図１４の構成の処理内容を具体的に説明する。実施形態における量子化部１４０１では、８ビット（２５６階調）のモノクロ多値画像の入力に対して、２値画素（１ビット）の出力となる組織的ディザ処理を行う。また、ある特定の閾値行列を使用することが符号化装置と復号化装置との間であらかじめ暗黙の了解として決められているものとする。また、画像データはラスタ順に量子化部１４０１に入力されるものとする。
【００２２】
本実施形態の閾値行列記憶部１４０４には図１５に示す閾値行列が格納されているものとする。また、原画像（１画素８ビット）は図１６の符号１４５０に示すように、濃度が“１００”近傍のモノクロ画像であるものとする（カラーの場合には、各色成分毎に実施形態の構成を備えればよい）。通常、写真などの自然画をデジタル画像データとしたとき、局所的に見れば、隣接する画素の濃度（或るいは輝度）は、概ね同じ値を持っているものであるので、特別な状態ではない。
【００２３】
閾値比較部１４０５は、上記入力された画像１４５０（１画素８ビット＝２５６階調）と、閾値行列記憶部１４０４から読み出した１つの閾値とを比較する。その閾値は入力画素の原画像中の位置に応じて行と列とを選択することで閾値行列から得られるものである。
【００２４】
閾値比較部１４０５は上記の比較の結果、すなわち、入力画素値が閾値以上あれば“１”を、そうでなければ“０”の１ビットの出力画素値と、その際に用いた閾値を予測値計算部１４０２及び符号化部１４０３に出力する。なお、符号化部１４０３へは実際の２値化結果のみで構わない。
【００２５】
予測値計算部１４０２は、このデータを入力して、注目画素位置における２値化予測値を生成し、出力する。そして、符号化部１４０３における判定部では、２値化予測値と、閾値変換部１４０１からの実際の２値化結果とが一致する／しないを１画素単位に判定し、その結果を１画素につき１ビットのデータとして圧縮符号化部１４０７に出力する。圧縮符号化部１４０７では、入力した２値情報をランレングス符号化等の可逆圧縮符号化を行い、その結果を出力する。なお、可逆圧縮符号化は如何なるものを採用しても構わない。
【００２６】
以下、画像データとして図１６の符号１４５０のデータが与えられた場合の例で説明する。
【００２７】
先ず、１行目（先頭のラスタライン）の処理に先立ち、比較判定部１４０５は閾値行列記憶部１４０４から第１行の処理に使用する閾値、すなわち閾値行列の１行目（８，２３２，２４，２４８）を読み出しておく。
【００２８】
次に、１行目の入力画素値と、閾値を順に比較し、出力画素値を決定する。このとき、閾値は巡回して使用する。たとえば、５画素目では１画素目と同じ閾値を使用することになる。
【００２９】
１画素目の画素値「９５」は、対応する閾値「８」と比較し、「９５≧８」なので出力画素値は“１”として２値化される。２画素目は、「１０２＜２３２」であるので“０”、３画素目は「１０５≧２４」であるので“１”に２値化される。以下、同様に比較することで、１ライン目の２値化処理が終了する。
【００３０】
１ライン目の最終画素の２値化が完了すると、２ライン目の処理を行うため、比較判定部１４０５は閾値行列記憶部１４０４から第２行の処理に使用する閾値、すなわち閾値行列の２行目の閾値（１６８，７２，１８４，８８）を読み出し、同様に繰り返す。以下、３ライン目、４ライン目と、２値化処理を行っていく。
【００３１】
閾値行列は行についても巡回して使用する。すなわち、５ライン目では、１ライン目と同じ閾値（８，２３２，２４，２４８）を用いて２値化することになる。
【００３２】
要するに、ラスタ（主走査）方向の位置をｉ（ｉ≧０）、副走査方向の位置をｊ（ｊ≧０）とし、量子化対象の画素値をＤ（ｉ，ｊ）として定義し、更に、閾値行列記憶部１４０４に格納されている閾値を同様にＴ（０、０）乃至Ｔ（３，３）で表現すると、画素値Ｄ（ｉ，ｊ）と比較する閾値はＴ（ｉ  ｍｏｄ  ４，ｊ  ｍｏｄ  ４）で定義できることになる。ここで「ａ  ｍｏｄ  ｂ」はａをｂで除算した際の余りを返す関数である。ハードウェアで実現する場合には、閾値を記憶したメモリに行方向、列方向のアドレスそれぞれ２ビット（計４ビット）を与えるようにすれば良い。
【００３３】
以上のようにして、比較判定部１４０５の出力２値化画像ータは図１７のように求めることができる。よって、２値化結果の画素値（１ビット）と閾値の組を「（２値化データ、閾値）」で表現したとき、予測値計算部１４０２へ伝達されるデータは図１８のようになる。
【００３４】
本実施形態の予測値計算手段である予測値計算部１４０２は、注目画素位置を（ｉ，ｊ）で表現したとき、その画素位置の左方の２つの２値化結果の画素Ｂ（ｉ−１，ｊ）、Ｂ（ｉ−２，ｊ）と、注目画素位置の濃度クラス値である閾値Ｔ（ｉ  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）と左隣の画素の濃度クラス値である閾値Ｔ（（ｉ−１）  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）に対して、図１９に示すような条件で、注目画素位置の２値化予測値Ｙを決定する。ただし注目画素位置がラインの先頭の場合には、それより２つ前の画素が存在しないので、画像の範囲外の領域での２値化結果は“０”とみなす。
【００３５】
図１９における第１の条件は、注目画素位置の左２画素の既２値化結果が共に同じ値であった場合には、注目画素位置での２値化結果も同じ値となり易い傾向にあることになるから、左隣の２値化結果を注目画素位置における２値化予測値Ｙとして決定することを示している。
【００３６】
そして、第２の条件として、注目画素の２つ前の画素位置の２値化結果と１つ前の２値化結果とが互いに異なっている場合、注目画素位置を２値化する際の閾値Ｔと１つ前の２値化する際の閾値に基づいて、注目画素位置の２値化予測値Ｙを決定する。
【００３７】
いずれの場合にも、予測値Ｙは、注目画素の存在するライン内で、注目画素の近傍の２値化結果と閾値でもって求めることになる。
【００３８】
ここで、第２の条件の理由を以下に説明する。
【００３９】
注目画素位置における２値化閾値Ｔ（ｉ  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）が、注目画素位置の直前（１つ左）の２値化閾値Ｔ（（ｉ−１）  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）よりも大きくなったということは、注目画素が“１”と２値化されにくくなる方向に作用する、換言すれば、“０”に２値化され易い方向に作用することを意味する。それ故、
T((i-1) mod 4、j mod 4)＜T(i mod 4、j mod 4)
という関係が成り立つとき、注目画素位置の２値化予測値Ｙは“０”にする。
【００４０】
一方、注目画素位置における２値化閾値Ｔが、注目画素位置の直前（１つ左）の２値化閾値閾値Ｔ以下の場合、注目画素位置の量子化後の画素値は“１”となり易いことを示すことになる。従って、
Ｔ（（ｉ−１）  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）≧Ｔ（ｉ  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）
という関係が成り立つ場合、注目画素位置の２値化予測値Ｙは“１”にする。
【００４１】
以下、実施形態における予測値計算部１４０２に対して、図１８に示す（２値化結果、閾値）をセットにしたデータが入力された場合について説明する。
【００４２】
先ず、１ライン目の先頭（１番目）の画素を注目画素とし、その２値化予測値Ｙ（０，０）を求める。注目画素位置の１つ前と２つ前の画素は共に存在しない。先に説明したように、存在しない２画素の２値化結果は共に“０”と見なしているわけであるから、図１９におけるＢ（ｉ−１，ｊ）＝Ｂ（ｉ−２，ｊ）＝０の場合に相当することになり、注目画素（ラインの先頭画素）の２値化予測値Ｙ（０、０）＝“０”して決定する。
【００４３】
２番目の画素位置を注目画素とした場合、その２値化予測値Ｙ（１，０）は次のようにして求める。
【００４４】
その１つ前の２値化結果Ｂ（０、０）＝“１”、２つ前の画素の２値化結果Ｂ（−１，０）（存在しない画素の２値化結果）＝“０”であり、互いに等しくない。従って、注目画素位置の２値化予測値Ｙ（１，０）は、注目画素位置の２値化閾値Ｔ（１，０）と、１つ左の画素の２値化閾値Ｔ（０，０）に基づいて決定する。注目画素位置における２値化閾値Ｔ（１，０）＝２３２であり、１つ前の２値化閾値Ｔ（０、０）＝８であるので、図１９における、
Ｔ（（ｉ−１）  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）＜Ｔ（ｉ  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）
の場合に該当する。従って、注目画素位置の２値化予測値Ｙ（１，０）＝“０”と決定する。
【００４５】
３番目の画素位置を注目画素とした場合、その２値化予測値Ｙ（２，０）は、２つ前の２値化結果Ｂ（０，０）＝“１）、１つ前の２値化結果（１，０）＝“０”であり、互いに等しくない。従って、閾値によって、注目画素位置の２値化予測値Ｙ（２，０）は閾値により求めることになる。このとき、Ｔ（２、０）＝“２４”、Ｔ（１、０）＝“２３２”であるから、図１９における、
Ｔ（（ｉ−１）  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）≧Ｔ（ｉ  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）
に該当することになるから、Ｙ（２、０）＝“１”とする。
【００４６】
以下、同様に繰り返し、１ラインの処理によって、その２値化予測値Ｙ＝｛０、０、１…｝を得ることができる。そして、１ライン目の処理が終わると、２ライン目の先頭画素から同様に処理し、最終ラインの最終画素位置まで同様に処理することになる。
【００４７】
図２０は上記の処理によって得られた各画素位置における２値化予測値を示している。
【００４８】
実施形態における符号化部１４０３における判定部１４０６は、予測値計算部１４０２からの２値化予測値データ（図２０参照）と、階調変換部１４０１での２値化結果（図１７参照）を入力し、２値化予測値と実際の２値化結果とが一致した場合、すなわち、予測値通りの２値化結果が得られた場合に“０”、予測通りにならなかった場合に“１”とする判定結果を１画素単位に圧縮符号化部１４０７に出力する。なお、判定部１４０６を最も単純化するのであれば、２入力、１出力を行う排他的論理和回路で実現できよう。
【００４９】
図２１は、図２０の予測値データ、図１７の２値化結果データを受けた場合の、判定部１４０６の出力を示している。
【００５０】
図示に示すように、各ラインの先頭画素、もしくは２画素目の判定結果が“１”になっている（２値化予測値に一致していない）のは、画像領域を越える２値化結果を“０”として見なしている影響によるものであるが、多くの“０”を生成し、２値データの“１”と“０”の出現頻度に偏りを持たせることに成功している。
【００５１】
圧縮符号化部１４０７は、ランレングス符号化等の可逆圧縮技術を利用したものであれば如何なるものでも良いので、その詳細については省略するが、図１７の２値化結果を符号化する場合と比較して、遥かに高い圧縮効率が期待できることになるのは明らかである。なお、符号化データの出力先は、如何なるものでも良い。例えば、ストレージ装置に保存する場合には、画像サイズや１ラインの画素数等を示す情報と共に符号化データを含めたファイルにして保存することになる。
【００５２】
なお、以上の説明から明らかなように、２値化予測値が実際に２値化した結果と同じなる割合が高いほど、圧縮符号化効率が向上する。しかも、予測値を求めるアルゴリズムは、注目画素が存在するラインで、且つ、注目画素に近い位置のデータのみを利用して求めることができるようになり、ハードウェアで実現する場合に回路規模がごく簡単なものとすることができる。
【００５３】
なお、ディザマトリクスの閾値の並びも、予測値を求める重要なファクタとなる。以下にその理由を説明する。
【００５４】
今、４×４サイズのディザマトリクスの或る行の４つ閾値が｛２３２、８、２４、２４８｝であり、この中の３番目の閾値「２４」を用いて注目多値画素Ｄを２値化する場合を考察する。ここで、注目多値画素の２つ前の２値化結果と、１つ前の２値化結果が等しくないと仮定すると、上記実施形態に従えば、注目画素の２値化予測値Ｙ＝０になる。なぜなら、注目画素の閾値「２４」は、１つまえの閾値「８」よりも大きいからである。
【００５５】
確かに、直前の画素の２値化閾値より、注目画素位置の２値化閾値が大きくなるので、注目画素は“０”に２値化され易い方向には作用する。しかしながら、数値「８」と「２４」とでは、もともとその差が入力画像データ８ビットのダイナミックレンジと比較して小さいから、その信頼性が余り高いとは言えない。すなわち、上記実施形態では注目画素位置の閾値と直前の画素位置の閾値との差（絶対値）が大きければ大きいほど、正しい予測値が期待できることになる。従って、ディザマトリクスを構成する行（２値化処理する方向）において、隣接する閾値の差は大きくすることが望ましいことは理解できよう。
【００５６】
従って、ディザマトリクスの閾値を大きさ順に並べ、それをＴ１，Ｔ２，…ＴＮで表わしたとき、閾値Ｔ１、Ｔ２…の順に、それら閾値が離散的に配置されたディザマトリクスを採用すると都合が良い。良く知られているディザマトリクスには幾つかのタイプがあるが、中でも、ｂａｙｅｒ型、或いはそれに類する配置のディザマトリクスが、予測値を求めるのに適したものと言える。
【００５７】
次に、上記実施形態で生成された圧縮符号化データを入力し、復号する装置の動作を説明する。図２２は、その装置のブロック構成図である。
【００５８】
先に説明したように、図１４の圧縮符号化部１４０７は可逆圧縮符号化処理を行うものであるので、図２２における復号化部２２０１はそれとは逆の処理を行い、図２１に示す差分符号データに変換すればよいので、その説明は省略する。
【００５９】
閾値行列記憶部２２０５は符号化装置における閾値行列記憶部１４０４と同じ内容（図１５参照）に設定されている。また、予測値計算部２２０３はこれまでに得られた出力画像データの一部と、注目画素位置およびその直前の画素位置に対応した閾値とにより予測値を計算するためのものである。差分加算部２２０４は復号化部２２０１からの差分符号と、予測値計算部２２０３からの予測値とから出力画像データを再構成し、２値画像データを生成するものである。
【００６０】
以下、符号化データから復号化部２２０１により図２１の差分符号データが得られたとし、説明する。
【００６１】
閾値行列記憶部２２０５には、第１実施形態の画像処理装置での処理時に使用したのと同じ図１５に示す閾値行列の要素データ（閾値データ）が格納されている。予測値計算部２２０３は第１実施形態の予測値計算部と同じ処理、すなわち、図１９の条件に従って予測値を計算する。なお、復号処理でも、各ラスタの先頭画素を越える左２画素の復号２値化結果は“０”であると見なす点に注意されたい。また、図２１に示す各データを、その座標位置でＥ（ｉ，ｊ）として表現することとする。
【００６２】
先ず、第１ラインの先頭の２値データＢ（０、０）は次のようにして求める。
【００６３】
予測値計算部２２０３は、参照するべき画素がないので第１実施形態と同様に、２つ前及び１つ前の復号結果である復号２値化データが共に“０”であるので、注目画素の予測値Ｙ（０，０）＝“０”とする。一方、注目画素位置における差分データＥ（０，０）＝“１”であったわけであるから、予測が外れたことを意味する。予測値Ｙ（０，０）＝“０”が正しくないわけであるから、注目画素の復号２値化結果Ｂ（０、０）＝“１”として決定する。
【００６４】
第１ラインの２番目の注目画素の２値データＢ（１、０）は次のようにして求める。
【００６５】
注目画素の２つ前の復号２値化結果Ｂ（−１，０）（存在しない画素位置）＝“０”、１つ前の実際の復号２値化結果Ｂ（０、０）＝“１”であり、両者は異なっている。また、注目画素位置の差分値Ｅ（１，０）＝“０”であるから、符号化する際の注目画素位置の２値化予測値は正しかったことを意味する。図１５によれば、注目画素位置の閾値Ｔ（１、０）＝“２３２”、直前の閾値Ｔ（０、０）＝“８”であり、Ｔ（０、０）＜Ｔ（１，０）の関係になっていることになる。すなわち、図１９における、
Ｔ（（ｉ−１）  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）＜Ｔ（ｉ  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）
と判定して得られた２値化予測値“０”が正しかったことを意味していることに他ならない。従って、注目２値画素データＢ（１，０）＝“０”として決定する。
【００６６】
第１ラインの３番目の画素を注目画素とし、その２値データＢ（２、０）は次のようにして求める。
【００６７】
注目画素の２つ前の復号２値化結果Ｂ（０，０）＝“１”、１つ前の復号２値化結果Ｂ（１、０）＝“０”であり、両者は違っている。また、注目画素位置の差分値Ｅ（２，０）＝“０”であるから、符号化する際の注目画素位置の２値化予測値は正しかったことを意味する。図３によれば、注目画素位置の閾値Ｔ（２、０）＝“２４”、直前の閾値Ｔ（１、０）＝“２３２”であり、Ｔ（１、０）≧Ｔ（２，０）の関係になっていることになる。すなわち、図１９における、
Ｔ（（ｉ−１）  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）≧Ｔ（ｉ  ｍｏｄ  ４、ｊ  ｍｏｄ  ４）
と判定して得られた２値化予測値“１”が正しかったことを意味する。従って、注目２値画素データＢ（１，０）＝“１”として決定する。
【００６８】
以下、上記処理を第１ラインの最終画素まで行い、それが完了すると、第２ラインの先頭画素から同様に処理することになる。そして、最終ライン、最終画素まで上記処理を繰り返し行うと、結局のところ、図１７に示すような圧縮符号化する以前の２値画像データにまで完全に復元できることになる。
【００６９】
なお、上記実施形態では復号化装置と復号化装置の双方で、同じディザマトリクスを用意する必要がある。厳密には、復号側では、ディザマトリクスの個々の係数は必要ではなく、左右に隣接する閾値間の大小関係を示す情報があればよい。同じ閾値が存在しないと仮定して良いので、大小関係は１ビットで表現できる。従って、４×４の大小関係を保持するためには１６ビットの情報が存在すれば十分である。よって、符号化データを送信する場合のヘッダ等にこの情報を格納したとしても、全体のデータ量に対する復号する際に必要なマトリクス情報のデータ量は小さい。
【００７０】
また、実施形態では、ディザマトリクスのサイズを４×４としたが、これによって本発明が限定されるものではなく、一般にＮ×Ｍのサイズで表現できる。また、注目画素の１つ前と２つ前の２値化結果の状態を参照するで注目画素の２値化結果の予測値とすることを１つの条件にしたが、注目画素のｎ個前までのｎ個の２値化結果が同じであるどうかを条件にしてもよい。
【００７１】
更に、実施形態では、１つ前と２つ前の２値化結果が等しくない場合、注目画素の閾値と１つ前の画素位置の閾値との大小関係で注目画素の２値化予測値を求めたが、これによっても本発明が限定されるものではない。
【００７２】
例えば、ライン内に着目すれば良いので、注目画素位置の閾値をＴｉと表現したとする。そして、２つ前の画素の２値化結果と、１つ前の画素の２値化結果が互いに等しくないというのは、注目画素位置での入力画素値はＴｉ−１、Ｔｉ−２の中央にある確率が高いことを意味する。仮に、その中央値をＴｍ（＝（Ｔｉ−１＋Ｔｉ−２）／２）としたとき、Ｔｍ＜Ｔｉなる関係にある場合、注目画素位置における２値化予測値Ｙは“０”、Ｔｍ≧Ｔｉの場合にはＹ＝“１”としても良い。
【００７３】
さらにまた、上記実施形態での機能実現手段は、コンピュータプログラムによっても実現できる。ここで、そのコンピュータプログラムがパーソナルコンピュータ等の汎用情報処理装置で実現する場合には、例えば、図２３に示す手順で行えば良いであろう。なお、汎用情報処理装置のブロック図は周知のもとするので省略する。また、図２３は１ラインの差分データ（図２１のデータ）を生成する処理についてのみ示している。
【００７４】
更に、２値化対象画像の１ラインはＭ画素、変数Ｂ（）は２値化結果を格納する変数、Ｄ（）は２値化対象多値画素を入力する変数、Ｔ（）はディザマトリクスの１ライン分の閾値（実施形態では４つ）を格納する変数、Ｙ（）は予測値を格納する変数、Ｅ（）は差分データを記憶する変数である。なお、変数Ｂ（０）には１ラインの先頭画素の２つ前の画素位置における２値化結果、Ｂ（１）は同１画素前の２値化結果を格納し、１ラインの画素の２値化結果はＢ（２）以降に格納されるものとする。これは、変数のインデックスに負の値が使用できないとしても正常な結果を得られるようにするためである。
【００７５】
先ず、ステップＳ１では、変数Ｂ（０）、Ｂ（１）をゼロで初期化し、変数Ｔ（）に該当するディザマトリクスの閾値を格納する。
【００７６】
次いで、ステップＳ２において、画素位置を示す変数ｉを初期値として“２”をセットする。ステップＳ３では、２値化対象画素データを変数Ｄに読み込む。そして、ステップＳ４で注目画素位置ｉに対応する閾値Ｔを求めるため、変数ｉを４で割った余りを変数ｊにセットする。また、注目画素位置の直前の閾値Ｔを求めるため、変数ｉに３を加算した値を４で割った余りを変数ｋにセットする。
【００７７】
処理がステップＳ５に進むと、注目画素値が閾値Ｔ（ｊ）より大きいか否かを判断する。閾値Ｔ（ｊ）より大きい場合、注目画素の２値化結果Ｂ（ｉ）を“１”にする（ステップＳ６）。また、閾値Ｔ（ｊ）以下であると判断した場合には、注目画素の２値化結果Ｂ（ｉ）を“０”とする（ステップＳ７）。
【００７８】
いずれの場合にも処理はステップＳ８に進み、２つ前の２値化結果Ｂ（ｉ−２）と１つ前の２値化結果Ｂ（ｉ−１）が互いに等しいか否かを判断する。
【００７９】
Ｂ（ｉ−２）＝Ｂ（ｉ−１）と判断した場合には、ステップＳ９にて注目画素位置における２値化予測値Ｙ（ｉ）に、直前の画素位置における２値化結果Ｂ（ｉ−１）を格納する。
【００８０】
また、ステップＳ８において、Ｂ（ｉ−２）≠Ｂ（ｉ−１）と判断した場合には、ステップＳ１０に進み、注目画素位置における閾値Ｔ（ｊ）と直前の画素位置における閾値Ｔ（ｋ）とを比較する。Ｔ（ｊ）＞Ｔ（ｋ）であると判断した場合には、注目画素位置の２値化予測値Ｙ（ｉ）を“０”にし（ステップＳ１１）、Ｔ（ｊ）≦Ｔ（ｋ）であると判断した場合にはＹ（ｉ）を“１”にする（ステップＳ１２）。
【００８１】
このようにして、注目画素の２値化予測値Ｙ（ｉ）を決定すると、処理はステップＳ１３に進む。ステップＳ１３では、注目画素の実際の２値化結果Ｂ（ｉ）と２値化予測値Ｙ（ｉ）とを比較する。一致している、すなわち、予測値通りに２値化した場合には、差分変数Ｅ（ｉ−２）に“０”を格納し（ステップＳ１４）、不一致の場合（予測がはずれた場合）には、変数Ｅ（ｉ−２）に“１”を格納する（ステップＳ１５）。なお、変数Ｅに格納する際に変数ｉから２を引いているのは、Ｅ（０）から差分値を格納するためである。
【００８２】
この後、ステップＳ１６にて、変数ｉを“１”だけ増加し、ステップＳ１７にて１ラインの最終画素位置までの差分算出処理が終了したか否かを判断し、終了した判断した場合には本処理を終え、例えば１ライン分の差分データＥ（）の圧縮符号化処理を行い、次のラインの処理を行うことになる。また、ステップＳ１６にて、１ラインの最終画素の処理が未完であると判断した場合にはステップＳ３以降の処理を繰り返すことになる。
【００８３】
なお、上記において、２値化結果を参照するのは、注目画素、１つ前の画素、２つ前の画素それぞれの２値化結果のみで良いので、変数Ｂ（）は３つ分のデータを格納する容量を有し、逐次、シフトしていけば良いであろう。
【００８４】
また、復号処理をホストコンピュータで実行する場合には、これまでの説明で十分に理解できるであろうから、その説明については省略する。
【００８５】
また、上記処理をホストコンピュータで実行するプログラムとしては、プリンタドライバが考えられる。すなわち、アプリケーションより渡されたデジタルカメラ等で撮像した画像をプリンタに出力する際に行うものである。当然、プリンタ側では先に説明した復号処理を行えば良い。
【００８６】
更に、上記実施形態では、２値化を例にして説明したが、３値化、４値化、…等に適用させても良い。４値化後のデータは、０、１、２、３の値のいずれかを持つことになる。この場合、３つのディザマトリクス（閾値行列）を定義すればよい。３つのディザマトリクスをＡ，Ｂ，Ｃとし、各マトリクス内の閾値をＡi,j、Ｂi,j、Ｃi,jとしたとき、
Ａi,j＜Ｂi,j＜Ｃi,j
なる関係を持たせる。
【００８７】
そして、ディザマトリクスＡ、Ｂ、Ｃそれぞれを用いて２値データを生成するようにすする。このようにすると、それぞれの２値データプレーンが上記実施形態での２値化結果と見なせるわけであるから、４値化等にも適用できるのは明らかである。
【００８８】
実施形態では図２４（ａ）のように１ライン単位で処理を行い同一ライン上の画素を参照している。しかしながら、たとえば図２４（ｂ）、（ｃ）に示したように複数ライン単位で処理を行い、注目画素とひとつ前の画素が同一ライン上にはない場合でも適用可能である。この場合、参照画素は処理の順番のほか、注目画素に対する位置関係によって決めておくこともできる。
【００８９】
＜第２の実施形態＞
次に、第２の実施形態について説明する。本第２の実施形態では、閾値の周期が必ずしも整数とならない周期関数により閾値を算出する画像処理装置に適用した例である。また、本実施例では閾値そのものではなく、出力値の出現頻度によって閾値を分類した濃度クラスを予測に用いている。
【００９０】
図２５は本実施形態の概略を示すブロック図である。
【００９１】
階調変換部２５０１は閾値算出部２５０４と閾値比較部２５０５とで構成されている。閾値算出部２５０４は画素ごとの属性情報（不図示の像域判別処理で得られるものとする）の入力から、閾値を算出するためのものである。閾値比較部２５０５は入力画素値と閾値の入力から、出力画素値を算出するためのものである。閾値算出部２５０４は画素ごとの属性情報（たとえば、背景、文字・線画、中間調画像）に応じてパラメータθ，ω，ｄを決め、入力画像データの階調数ｎ、画素位置（ｘ，ｙ）から以下の式（式１−１，式１−２，式２，式３）により閾値ｔを算出する。閾値ｔは最終的に小数部を切り捨て整数として算出するものとする。すると、閾値ｔはｄ＋１以上ｎ−ｄ−２以下の整数となる。
x' = x cosθ - y sinθ ...(式1-1)
y' = x sinθ + y cosθ ...(式1-2)
a = sin(2πωx') + sin(2πωy') ...(式2)
t = (a+2) ×(n - 2d - 3)/4 + d + 3/2 ...(式3)
閾値算出部２５０４はまた、後に予測値計算部２５０２で使用するための濃度クラスを属性の種類と、閾値に応じて決定する。本実施形態では、２種類の属性（文字・画像）について注目し、各画素にどちらかの属性が排他的に必ず付与されているものとする。カラーの場合、例えばＹ，Ｍ，Ｃ，Ｋが存在するが、上記パラメータθ，ω，ｄは各色独立に設定されていているとする。以下は、モノクロ、もしくは、１つの色成分に対するものである。
【００９２】
以下、８ビットの入力画像（ｎ＝２５６）において、文字属性に対してパラメータｄ＝４，階調画像属性に対してｄ＝１６とした場合の例について説明する。このように設定することで、以下の手順によって中間調（出力画素値１）の出現頻度は文字領域では低く、画像領域では高くなり、好ましい出力を得ることができる。
【００９３】
濃度クラスは図２６に示すように属性と閾値に応じて分類し、各クラスに分類されるべき閾値の中央値をクラス代表値と定める。
【００９４】
閾値比較部２５０５は、入力画素値ｐと閾値ｔを比較して、出力画素値ｒを求める。このとき、ｐ＜ｔ−ｄ  ならば  ｒ＝０、ｐ＞ｔ＋ｄ  ならばｒ＝２、どちらにも該当しなければｒ＝１とする。
【００９５】
次に、予測値計算部２５０２での予測方法について説明する。
【００９６】
まず、図２７で参照画素を選択する方法について説明する。予測対象画素２７０１の近傍で、同じ属性情報を持つ参照画素を図にあるように画素２７０２，画素２７０３，画素２７０４，画素２７０５の優先順位で選択する。このとき、たとえば画素２７０６は未処理なので利用することはできない。
【００９７】
同じ属性情報を持つかどうかは濃度クラスから判別可能である。すなわち、予測対象画素２７０１の濃度クラスが０または１の場合は、参照画素の濃度クラスが０または１のものを、予測対象画素２７０１の濃度クラスが２ないし４の場合は、参照画素の濃度クラスが２ないし４のものを選択すれば良い。
【００９８】
画素２７０２ないし２７０５のすべてが予測対象画素２７０１と異なる属性情報の場合は以下のように扱う。予測対象画素２７０１の濃度クラスが０または１の場合は、参照画素の濃度クラス０、出力画素値２とみなす。さもなくば、参照画素の濃度クラス２、出力画素値０とみなす。
【００９９】
画像端部において、参照画素の一部または全部が画像の範囲外となる場合はそれらの参照画素の属性情報は予測対象画素と異なるものとみなす。
【０１００】
以上のようにして参照画素と予測対象画素の属性情報が同じになるようにする。次に予測値の算出について説明する。
【０１０１】
まず、予測対象画素の属性情報が文字線画属性の場合について説明する。
【０１０２】
文字属性に対応した濃度クラス（０と１）において入力画素値とクラス代表閾値との比較で出力画素値を求めると図２８のような関係になる。
【０１０３】
入力画素値（８ビットとする）３０，６０，１９０，２１０における出力画素値は図２９のようになる。この関係を利用して、図３０のように予測を行う。
【０１０４】
すなわち、濃度クラスが同じ場合は参照画素の出力画素値を予測値とする。また、濃度クラス０の参照画素から濃度クラス１の予測値を求める場合は、参照画素の出力画素値が０または１の場合は予測値０とし、そうでない場合は予測値を２とする。濃度クラス１の参照画素から濃度クラス０の予測値を求める場合は、参照画素の出力画素値が０の場合は予測値０とし、そうでない場合は予測値を２とする。
【０１０５】
このように予測すれば、参照画素と予測対象画素の入力画素値が同じ場合は、ほとんど予測が的中することになる。
【０１０６】
次に予測対象画素の属性情報が画像（中間調画像）属性の場合について説明する。
【０１０７】
画像属性に対応した濃度クラス（２，３，４）において入力画素値とクラス代表閾値との比較で出力画素値を求めると図３１のような関係になる。
【０１０８】
この関係を利用して、図３２のように予測を行う。以上のように予測値を算出することで、ディザ処理の閾値を考慮した出力画素値の予測を行うことが可能になる。
【０１０９】
符号化部２５０３は、予測値と出力画素値との差分を計算するための差分計算部２５０６と復号化処理に必要な属性情報と差分情報を符号化するための圧縮符号化部２５０７とで構成されている。
【０１１０】
本実施形態では出力画素値は０から２までなので、予測値０の場合の差分は０，＋１，＋２、予測値１の場合の差分は−１，０，＋１、予測値２の場合の差分は−２，−１，０のいずれかとなる。
【０１１１】
そこで、差分計算部２５０６は図３３のように予測値と差分に応じた３種類の中間符号ＡもしくはＢもしくはＣを生成し、圧縮符号化部２５０７に伝達する。
【０１１２】
圧縮符号化部２５０７は１ライン単位で属性情報と中間符号符号化する。まず１ライン分の属性情報をファクシミリの伝送で標準化されているモディファイドハフマン（ＭＨ）符号に準じて符号化し、次いで差分値を表現するための中間符号を符号化するものとする。なお、ＭＨ符号の詳細についてはＣＣＩＴＴ勧告Ｔ．４で説明されているのでここでは省略する。  
差分値の符号は図３４の符号表を用いるものとする。中間符号Ａ，Ｂ，Ｃそれぞれに対応した符号が定められているほか、８個以上の連続するＡを短縮して表現する形式が定義されている。これには、圧縮率向上の目的のほか、中間符号Ａが続いた結果、ＭＨ符号で特殊な意味を持つＥＯＬ符号“０００００００００００１”と同じ並びが出現するのを防止する意味がある。
【０１１３】
９個、１６個などの連続するＡの並びについては特別な符号は定めないが、たとえば、９個を８個＋１個、１６個を８個＋８個のように分離して、図３５の例にあるように符号化すれば良い。
【０１１４】
＜第３の実施形態＞
次に、第３の実施形態について説明する。本実施形態以降は特開平８−２２３４２８号公報による従来方法が苦手としていた、閾値の変化周期と等しい縦縞画像データに対しても良好な圧縮を実現するために、閾値の周期を利用した予測と注目画素の近傍画素値による予測との２種類の予測を適応的に選択するものである。
【０１１５】
本実施形態はライン単位で符号化を行う。説明を簡単なものとするため、１画素８ビット（２５６階調）の画像データを１画素２ビット（４階調＝４値化）にディザ処理が施され、このディザ処理の画像を符号化対象とする例を説明する。
【０１１６】
このディザ処理では、ｎ×ｍ画素サイズの３つのディザマトリクス、例えば、図３（ａ）乃至（ｃ）に示す８×８サイズのディザマトリクスを用いて行われる。
【０１１７】
今、入力した原画像の画素値（８ビット）を、その水平画素位置ｉ、垂直（ライン数）をｊとしてＤ（ｉ，ｊ）と表現した場合、その画素を４値化するために使用するディザマトリクス３０１の閾値Ｔ１、ディザマトリクス３０２の閾値Ｔ２、ディザマトリクス３０３の閾値Ｔ３は、それぞれＴ１（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）、Ｔ２（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）、Ｔ３（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）として表現できる（ここで「ｘ  ｍｏｄ  ｙ」とは、ｘをｙで除算した際の余りを返す関数である）。つまり、閾値Ｔ１〜Ｔ３は、水平方向に対してディザマトリクスの水平方向のサイズである８画素周期に変化し、垂直方向についても８画素周期に変化することになる。
【０１１８】
そして、注目画素Ｄ（ｉ，ｊ）を４値化する場合には、閾値Ｔ１（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）、Ｔ２（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）、Ｔ３（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）のそれぞれと比較し、注目画素値Ｄ（ｉ，ｊ）が、これら閾値より大きくなった個数を算出する。閾値の個数は３つであるので、算出した結果は０乃至３の値、すなわち、２ビットで表現できるから、８ビットの画素値が２ビットに量子化、すなわち、４値化できることになる。
【０１１９】
なお、実施形態では、ディザマトリクス３０１，３０２，３０３の閾値閾値Ｔ１（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）、Ｔ２（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）、Ｔ３（ｉ  ｍｏｄ  ８，ｊ  ｍｏｄ  ８）の平均値をディザ平均閾値と定義する。実施形態では、ディザ平均閾値はディザマトリクス３０２に等しい。
【０１２０】
図３８は上記の２５６階調（８ビット）を４階調（２ビット）に変換するディザ回路構成の一例を示している。
【０１２１】
図示において、３８０１乃至３８０３はそれぞれ図３（ａ）乃至図３（ｃ）に対応するディザマトリクスの閾値を格納するう閾値ルックアップテーブル（ＬＵＴ）である。３８０４乃至３８０６はコンパレータであり、［＋］端子に入力された値が［−］端子に入力された値以上の場合に１ビット信号“１”を出力し、それ以外の場合には“０”の信号を出力する。３８０７は各コンパレータ３８０４乃至３８０６からの“１”をカウントし、そのカウント結果を２ビットの信号として出力するカウンタである。
【０１２２】
図示において、注目多値画素データＤ（ｉ，ｊ）を入力したとき、ｉ  ｍｏｄ  ８、ｊ  ｍｏｄ  ８（画素アドレスの下位３ビットと等価）の値を、各ルックアップテーブルテーブル３８０１乃至３８０３のアドレス信号として供給する。この結果、各閾値ルックアップテーブル３８０１乃至３８０３からは、該当する閾値Ｔ１、Ｔ２、Ｔ３が出力される。各コンパレータ３８０４乃至３８０６は、入力した多値画素データＤと閾値とを比較し、そのカウンタ３８０７に供給することになる。コンパレータ３８０４乃至３８０６から出力される“１”の個数は最大で３、最低で０であるから、その個数に応じた２ビットの信号、すなわち、ディザ処理後の画像データを出力することになる。
【０１２３】
次に、上記のディザ処理後の画像データを圧縮符号化する例を、図１に示す画像処理装置の構成を参照して説明する。
【０１２４】
図中、１０１は入力端子１０９より入力したディザ処理後の画素データを水平方向８画素分だけ記憶する参照画素値記憶部（シフトレジスタで構成する）である。この記憶する画素の個数は、ディザマトリクスの水平方向のサイズに同じである。従って、入力端子１０９より入力した画素値を注目画素値としたとき、参照画素値記憶部１０１には、それより時間的に１乃至８画素前の画素データを記憶保持することになる。
【０１２５】
１０３は図３（ａ）乃至（ｃ）に示すディザマトリクス３０１乃至３０２の平均値を記憶する記憶する閾値記憶部である。実施形態の場合、各ディザマトリクスの閾値の平均値はディザマトリクス３０２に等しいので、ディザマトリクス３０２のみを記憶すればよくなり、その分だけ記憶容量を少なくしている。勿論、複数のディザマトリクスを記憶保持し、その平均値を算出する演算部を設けるようにしてもよい。
【０１２６】
１０２は第１予測部であって、注目画素値の直前の画素値を参照画素値記憶部１０１から取り出すと共に、閾値記憶部１０３より閾値を取り出し、これらに基づいて注目画素の予測値（以下、第１予測値という）を決定する。この第１予測部１０２は従来苦手としていた縦縞画像における予測精度の向上のためのものである（詳細後述）。
【０１２７】
１０４は第２予測部であって、注目画素の８画素前の画素値、すなわち、ディザマトリクス内の同位相の入力画素値を予測値（第２予測値という）として決定する。
【０１２８】
１０５は連続性判定部であって、第１、第２予測値のいずれか一方を選択させるための判定を行う（詳細後述）。
【０１２９】
１０６は、連続性判定部１０５の判定結果に基づいて、第１、第２予測値のいずれか一方を選択し、出力する予測値選択部である。
【０１３０】
そして、１０７は予測値選択部１０７からの予測値と注目画素値に基づき、符号化する符号化部である。
【０１３１】
次に、上記構成における実施形態における符号化装置の動作を以下に説明する。
【０１３２】
入力端子１０９からは１ライン単位に画素データが入力するが、新な１ラインを入力する際には、以下の初期化処理を行う。なお、初期化処理での初期値は、復号処理と同じであれば良いので、以下の設定に限定されない。
・参照画素値記憶部１０１の内容は所定値（実施形態では０とする）を示す画素値で初期化する。
・閾値記憶部１０３には、ディザマトリクス３０２中の該当する１ラインの８つの閾値を格納する。ディザマトリクス３０２は、図３（ｂ）に示すように８ラインで構成されるので、符号化対象の４値化画像のラインをｉ番目と定義したとき、閾値記憶部１０３には「ｉ  ｍｏｄ  ８」ライン（便宜的にディザマトリクスの最上位ラインを０ラインとする）の閾値を格納すればよい。もしくは、「ｉ  ｍｏｄ  ８」で示されるラインを選択するセレクタを設ける構成でも構わない。
・符号化部１０７の一致カウンタを０に初期化する。
・連続性判定部１０５に保持されるデータを所定値でクリアする。
【０１３３】
入力される画素値は２次元画像中の１画素であるので、先に説明したように本来は２次元座標で表現されるが、実施形態では１ライン単位に符号化する例を示しているので、注目画素値は１次元の座標値で表わすこととする。すなわち、注目画素（４値化後の画素データ）をＤiとする。
【０１３４】
上記の如く、注目ラインの符号化を開始する際、参照画素値記憶部１０１はゼロクリアされることになるので、注目ラインの先頭画素Ｄ0から８画素目のＤ7までを入力している最中には、第２予測部１０４から出力される第２予測値は「０」である。そして、１ラインの９画素目以降のデータＤiを入力した場合に、第２予測部１０４はそれより８画素前のＤi-8を第２予測値として出力することになる。
【０１３５】
一方、第１予測部１０２は、注目画素の直前の画素値Ｄi-1を参照画素値記憶部１０１から読み出すと共に、注目画素値Ｄiを４値化した際に用いた閾値Ｔｈiと、注目画素の直前の画素値Ｄi-1を４値化した際に用いた閾値Ｔｈi-1の２つの閾値を閾値記憶部１０３から読出し、注目画素値の第１予測値を演算する。
【０１３６】
なお、上記において、閾値Ｔｈi、Ｔｈi-1は、本来は、Ｔｈ(i mod 8)，Ｔｈ((i-1) mod 8)とすべきである。実施形態では説明を簡単にするため、注目画素の閾値と、その直前画素の閾値の関係を示すため、便宜的に上記のように示している。ただし、注目画素がラインの先頭画素Ｄ0である場合には、Ｔｈ-1は存在しないので、Ｔｈ-1＝０、もしくは、Ｔｈ-1＝Ｔｈ7とすればよいであろう。
【０１３７】
さて、第１予測部での第１予測値であるが、実施形態では、図４に示す関係に従って決定した。すなわち、
条件Ａ：参照画素値（注目画素の直前の画素値）Ｄi-1＝０の場合、第１予測値を無条件に“０”に設定する。
条件Ｂ．Ｄi-1＝１または２の場合
Ｔｈi＞Ｔｈi-1の関係を満足すれば、第１予測値を“０”を設定する。Ｔｈi≦Ｔｈi-1の関係を満足すれば、第１予測値を“３”に設定する。
条件Ｃ：Ｄi-1＝３の場合には、第１予測値は無条件に“３”に設定する。
【０１３８】
上記のようにする理由について説明する。注目画素位置における閾値Ｔｈiが直前の画素位置における閾値Ｔｈi-1より大きい場合、すなわち、Ｔｈi＞Ｔｈi-1の関係にある場合、注目画素値Ｄiは直前の画素値Ｄi-1よりも小さな値になる確率が高いことを意味する。逆に、Ｔｈi≦Ｔｈi-1の関係にある場合、注目画素Ｄiは大きな値になる確率が高いことを意味する。上記条件Ｂは、この理由によるものである。
【０１３９】
また、図３（ａ）〜（ｃ）に示される各ディザマトリクスを用いると、中間調画像データ等、ほぼ濃度（もしくは輝度）が一定の画像を入力した場合、その殆どが“０”、“３”の値になり、“１”、“２”となる画素数は限られたものとなる。つまり、図３（ａ）乃至（ｃ）のディザマトリクスを用いると、“０”、“３”の出現確率が高く、“１”、“２”の出現確率は低いと言える。上記条件Ａ，Ｃは、このような状況に対処するものである。
【０１４０】
なお、第１予測部の予測値の求め方として、たとえば、以下のように複数の近傍画素を参照して求める方法を適用しても良い。
条件Ａ：ｎ個の近傍画素群の画素値（Ｄi-1，Ｄi-2，…，Ｄi-n）がすべて一致した場合にはその値を第１予測値する。
条件Ｂ：近傍画素群中に画素値が異なるものがあり、Ｔｈi＞Ｔｈi-1の場合に第１予測値を“０”にする。
条件Ｃ：近傍画素群中に画素値が異なるものがあり、Ｔｈi≦Ｔｈi-1の場合に第１予測値を“３”にする。
【０１４１】
これは、たとえば、文書の余白部分など、連続する複数画素が同じ値の場合、次も同じ値になる可能性が高いことを前提としたものである。
【０１４２】
この方法には、条件Ａが成立する場合が多く、またその判定は以下のようにソフトウェアでも簡単に実現できるという利点がある。
【０１４３】
ｎ＝４とした場合、４個の画素値（Ｄi-4，Ｄi-3，Ｄi-2，Ｄi-1）を連結して（左側を上位ビットとする）ひとつのレジスタＸに格納する。また、注目画素を含む４画素値（Ｄi-3，Ｄi-2，Ｄi-1，Ｄi）を連結してレジスタＹに格納する。レジスタＹの値は次の画素を処理する際にレジスタＸの値として利用可能である。
【０１４４】
レジスタＸとレジスタＹのＸＯＲ（排他的論理和）演算結果をＺとした場合、Ｚの上位３画素分が０となれば、Ｄi-4＝Ｄi-3，Ｄi-3＝Ｄi-2，Ｄi-2＝Ｄi-1すべてが成立したこととなり、条件Ａが成立したことを意味する。さらに，Ｚ全体が０となれば、Ｄi-1＝Ｄiも成立するため、予測値と注目画素値が一致したことになる。
【０１４５】
隣接する画素間での閾値の差が大きい場合には、閾値を大、中、小などのクラスに分類して、閾値そのものの比較に代えてクラス間の大小関係によって予測値を算出してもほぼ同じ結果を得ることが可能である。具体的には、閾値のうち上位２ビットを用いて４分類する方法がある。
【０１４６】
本実施形態では、第１予測部は隣接する画素間での閾値の大小関係だけを用いているため、閾値記憶部１０３には、閾値そのものに代えて１画素前の閾値との比較結果をあらかじめ算出した上で、その結果を格納しておいても良い。
【０１４７】
さて、上記のようにして、第１予測部１０２からは第１予測値、第２予測部１０４からは第２予測値が出力されるが、予測値選択部１０６は連続性判定部１０５による判定結果に従って第１、第２予測値のいずれか一方を選択し、符号化部１０７に最終的な予測値として出力することになる。そこで、次に、実施形態における連続性判定部１０５を説明する。
【０１４８】
実施形態における連続性判定部１０５は、注目画素を含まない直近の３画素分のデータ、すなわち、図３６に示す近傍画素群３６０１と、ディザマトリクスのサイズに依存した１周期前の３画素のデータ３６０１（近傍画素群と同位相の画素群）をそれぞれ比較する。ただし、ここでは注目画素の直近の３画素と、それに対応する１周期前の３画素とを比較するものとしているのが、これらの数に限定されるものではない。また、１周期前に限らず１周期の整数倍前でも構わない。ただし、距離が長くなるほど、それら画素の相関度は低くなっていくので、１周期前が望ましい。
【０１４９】
実施形態では、比較した一致数が不一致数以上の場合（実施形態では２組の３画素を比較しているので一致数が２以上の場合）、入力した画像はディザマトリクスによる周期性が顕著に反映されているものとし、第２予測値が選択されるものとして判定する。また、一致数が不一致数未満である場合には、第１予測値が選択されるものとして判定する。
【０１５０】
図８は実施形態における連続性判定部１０５の具体的な構成の一例を示す図である。
【０１５１】
シフトレジスタ７０１には、入力端子１０９より入力した注目画素Ｄiの１乃至３つ前のデータＤi-1，Ｄi-2，Ｄi-3を記憶する。また、シフトレジスタ７０２はそれぞれの８画素前のデータＤi-9，Ｄi-10，Ｄi-11を記憶する。
【０１５２】
アンド回路７０３は、画素データＤi-1とＤi-9が一致する場合に“１”、不一致の場合には“０”を出力する。アンド回路７０４、７０５も同様である。
【０１５３】
カウンタ７０６は各アンド回路７０３乃至７０５からの一致することを示す“１”の数をカウントする。比較部７０７はカウントした値が予め設定された閾値“２”以上である場合には、第２予測値を選択するための指示情報を予測値選択部１０６に出力し、それ以外では第１予測値を選択するための指示情報を予測値選択部１０６に出力する。なお、カウンタ７０６はルックアップテーブルでも構成できる。
【０１５４】
符号化部１０７はライン終端に至るまで以下の処理を繰り返す。
・ディザ処理後の注目画素値Ｄiと、予測値選択部１０６から出力された予測値が一致した場合は一致カウンタをカウントアップする。
・注目画素値Ｄiとディザ画像データと予測値が一致しない場合は、それまでの一致カウンタの値に従って一致数を示す符号を出力し、一致カウンタをクリアする。次に差分値を示す符号を出力する。
・ライン終端においてはライン終端を示す符号（ライン終端までの差分がすべて０であることを示す）を出力する。
【０１５５】
出力符号は既知の圧縮符号化方法（たとえばハフマン符号、算術符号、ＬＺ符号など）によって圧縮し、その結果を圧縮画像データとする。どちらの予測値を選択したのか、また、選択された予測値によって異なる符号表を用いるようにすることもできる。
【０１５６】
次に実施形態における復号装置（図１の画像処理（符号化）装置と対を成す画像処理（復号装置）の構成を図２に示し、以下に説明する。
【０１５７】
なお、復号化装置においても、図３（ａ）乃至（ｃ）のディザマトリクス情報を予め記憶しているものとする。ただし、ディザマトリクスの閾値データも、符号化データに含まれている場合には、それを復号してディザマトリクスを生成しても構わない。また、１ラインを構成する画素数は予め固定、もしくは、符号化データ中に１ラインの画素数を示すデータがヘッダ等に記憶されているものとして説明する。
【０１５８】
入力端子２０９から各ラインの符号化データを入力する際、そのラインの先頭において図１の画像処理（符号化）装置と同様に以下に示す初期化処理を行う。
・参照画素値記憶部２０１の内容は、符号化装置側での参照画素値記憶部１０１の初期値と同じ値（実施形態では０）で初期化する。
・閾値記憶部２０３にディザ閾値のうち処理対象ラインに相当する行の値を格納しておく。
・符号化部２０７の一致カウンタを０に設定する。
・連続性判定部２０５に保持されるデータを所定値でクリアする（符号化装置の連続性判定部と同様）。
【０１５９】
これらの初期値は以上のようにあらかじめ決められた値を使用するほか、圧縮画像データの一部として記録しておいてその内容に従って初期化を行うように構成することもできる。
【０１６０】
また、差分値復号部２０８は連続するディザ画像データと予測値が連続して一致した数を数える一致カウンタを備える。この差分値復号部２０８はライン終端の符号を検出するまで以下の処理を繰り返す。
・一致カウンタが０でない場合、一致カウンタをカウントダウンして差分値０を出力する。
・一致カウンタが０の場合、差分復号部は次の入力符号を読み取る。
このとき、入力符号が一致数を示す場合には差分値０を出力し、符号が示す一致数から１減算した値を一致カウンタにセットする。また、入力符号が差分値を示す場合にはその差分値を出力する。更に、ライン終端の符号を検出した後は次のラインの処理に移るまで繰り返し差分値０を出力する。
【０１６１】
以上の手順によって図１における符号化部１０７の生成した圧縮画像データから差分値を得ることが可能である。
【０１６２】
ディザ画像データ復元部２０７は予測値選択部２０６が選択した予測値と差分復号部２０８によって得られた差分値とを加算することでディザ画像データを復元することになる。
【０１６３】
ディザ画像データ復元部２０７が最初の出力を得るまでの手順を説明すると次の通りである。
【０１６４】
参照画素記憶部２０１は初期化処理によって図１における参照画素記憶部１０１と同じ初期値に設定されている。
【０１６５】
第２予測部２０４は、図１における第２予測部１０４と同じ方法で第２予測値を算出する。初期化処理によって参照画素値記憶部２０１の内容はすべて“０”を示す画素値となるので、最初の第２予測値は“０”の画素値となる。
【０１６６】
連続性判定部２０５は、図１における連続性判定部１０５と同様の判定を行う。初期化処理によって比較結果の記憶内容は３画素とも一致したものと設定されるため、最初の判定では第２予測値を選択することになる。
【０１６７】
予測値選択部２０６は図１における予測値選択部１０６と同様である。連続性判定部２０５の最初の判定は第２予測値であり、第２予測部２０４による最初の第２予測値は空白の画素値であるため、予測値選択部２０６が最初に選択する予測値は“０”の画素値となる。
【０１６８】
これは予測値選択部１０６の最初の予測値に等しいため、差分復号部２０８によって得られた差分値からディザ画像データ画素値を復元することができる。
【０１６９】
ディザ画像データ復元部２０７によって得られた最初のディザ画像データ画素値は参照画素記憶部２０１に記憶さる。また、連続性判定部２０５では第２予測値との比較が行われて比較結果が記憶される。このように構成することで、参照画素記憶部２０１の記憶内容は図１における参照画素記憶部１０１と同じ内容になり、また、連続性判定部２０５が記憶する比較結果も図１における連続性判定部１０５と同じ内容に更新することが可能である。
【０１７０】
よって、後続する画素に対する予測値も符号化処理時と同じ値を求めることが可能で、差分値からディザ画像データを復元することができる。
【０１７１】
以上説明したように実施形態によれば、ディザマトリクスで量子化された画素が、ディザマトリクスの周期性に依存して量子化されている確率が高い場合には、注目画素に対してディザマトリクスのサイズ分だけ過去のデータを予測値として決定し、ザマトリクスの周期性に依存しないで量子化されている確率が高い場合に、直近の画素値と、閾値変化に基づいて予測値を得るようにしたので、符号化単位である１ラインに対して直交する方向の縦線や縦縞模様を有する画像、並びに、中間調画像のような画像のいずれに対しても高い圧縮率で符号化することが可能となる。
【０１７２】
なお、上記実施形態では予測値と注目画素値との差分を符号化する例を説明したが、これによって限定されない。
【０１７３】
例えば、符号化装置では、予測値と注目画素値が一致しているか否かを示す一致／不一致判定用の符号を先ず生成し、不一致の場合にのみ注目画素値の符号を、その一致／不一致判定用符号に後続するように生成する。これを受けた復号装置では、符号が一致することを示している場合には予測値を注目画素値として出力し、不一致を示す符号があった場合には後続する符号で示される値を注目画素値として出力すればよい。
【０１７４】
＜第４の実施形態＞
第４の実施形態では、上記第３の実施形態に相当する処理をコンピュータプログラムによって実現する例を説明する。
【０１７５】
装置構成は、通常のパーソナルコンピュータの構成で構わない。図９はその一例である。
【０１７６】
図中、９００は装置全体の制御を司るＣＰＵであり、９０１はＢＩＯＳやブートプログラムを格納しているＲＯＭ、９０２はＣＰＵ９００のワークエリアとして利用されるＲＡＭ、９０４はキーボード、ポインティングデバイスで構成される指示入力部である。９０５はハードディスク装置等の外部記憶装置であって、ＯＳ、実施形態にかかるプログラムが記憶されている。また、外部記憶装置９０５には、処理結果の画像データを記憶するためにも用いられる。９０６はイメージスキャナ等の画像入力部であって、符号化しようとする画像データを入力するものである。９０７は表示制御部であって、内部には表示用メモリ、この表示メモリへの描画コントローラ、表示メモリからのデータを表示装置９０８へビデオ信号として出力する回路で構成される。９０９はネットワークインタフェースである。なお、上記において、画像入力部９０６は、画像データを入力するものであれば如何なるものでも構わない。例えば、デジタルカメラもしくはそれを接続するインタフェースでも構わないし、ネットワーク上に存在する画像データを符号化する場合には、画像入力部９０６は不要にもなる。
【０１７７】
上記構成において装置の電源をＯＮにすると、ＣＰＵ９００はＲＯＭ９０２のブートプログラムに従って外部記憶装置９０５からＯＳをＲＡＭ９０３にロードし、第４の実施形態における画像符号化プログラム、或いは、復号プログラムを指示入力部９０４で指定することで実行することになる。
【０１７８】
本第４の実施形態では、８画素×４画素のブロック単位で圧縮符号化を行う例を説明する。つまり、１ページを４ラインごとのバンドに区切り、さらに各バンドを左端から８画素づつ区切ったものがブロックとなる。
【０１７９】
ブロック内での処理順序は、位置が近い画素を続けて処理するよう考慮して図７に示す順番と定める。垂直方向の相関も第１予測値や予測値の選択に反映させるためである。
【０１８０】
図５は１つのブロックの符号化処理プログラムの処理内容を示すフローチャートである。
【０１８１】
先ず、ステップＳ５０１における初期化処理では、一致数カウンタのクリア、第２予測的中数カウンタのクリア、連続性判定結果初期値（連続性大）の設定を行う。
【０１８２】
ステップＳ５０２の２予測値算出処理では、後に使用する第２予測値を算出するためのものである。第２予測値は、直前のブロック（以下参照ブロック）で処理対象画素と同じ位置の画素値とする。各バンドで左端のブロックにおいては参照ブロックはすべて“０”の画素値を持つものとして扱う。
【０１８３】
ステップＳ５０３では、４画素処理する毎に連続性の判定を行う。４画素中に第２予測値と処理対象のディザ画素値との差分が０となる個数が２個以上であれば、連続性大と判定し、そうでなければ連続性小と判定する。判定結果によって続く４画素で使用する予測方法が決定される。
【０１８４】
４画素単位の区切りでは、第２予測的中数カウンタを参照して連続性の判定を行い、その後クリアする。４画素の区切りでない場合は、以前の判定結果をそのまま利用する。
【０１８５】
ステップＳ５０４の第１予測値設定処理は、連続性小の場合にのみ必要となる。第１予測値の算出を行い、第１予測値を処理対象画素の予測値と設定する。第１予測値は処理対象画素を含まない過去の直近３画素の中央値とする。ブロックの初めでは参照ブロックの終わりの画素を使用することになる。
【０１８６】
最近の高解像度の画像データでは、通常の文字の字画でも数画素ないし十数画素の幅を持っている。本実施形態の第１予測値はこのような文字部分での簡易的な予測を狙ったものである。
【０１８７】
ステップＳ５０５の第２予測値設定処理では、第２予測値算出ステップＳ５０２で算出した第２予測値を処理対象画素の予測値と設定する。
【０１８８】
ステップＳ５０６の第２予測的中カウント処理では、第２予測値算出ステップＳ５０２で算出した第２予測値が処理対象ディザ画素値と一致しているか否かを判定し、一致した場合に第２予測的中数のカウントアップを行う。
【０１８９】
ステップＳ５０７の差分値判定処理では、図７に示す順に従って処理対象ディザ画素値を読み出す。また、連続性の大小に応じて第１予測値設定処理（ステップＳ５０４）または第２予測値設定処理（ステップＳ５０５）で設定された予測値と、処理対象ディザ画素値との差分を算出し、差分が０であるか否かを判定する。
【０１９０】
ステップＳ５０８の一致数カウントアップは、差分値判定処理（ステップＳ５０７）における差分が０の場合の処理で、連続する差分値０を数える一致数カウンタのカウントアップを行う。
【０１９１】
ステップＳ５０９の一致数カウンタ判定処理は、差分値判定処理（ステップＳ５０７）において、差分が０とならなかった場合の処理であり、一致数カウンタを調べる。一致数カウンタが０でない場合は、直前の画素およびそれ以前の連続する差分値０の一致数は出力されていない。従って、これを出力符号に反映せるため、ステップＳ５１０にて一致数符号出力処理を必要となる。
【０１９２】
ステップＳ５１０の一致数符号出力処理は、１画素以上が差分０となった後に、処理対象画素の差分が０とならなかった場合の処理で、差分０の連続数を示す符号を出力する。ステップＳ５１１の差分値符号出力処理は、処理対象画素のディザ画素値と予測値との差分を示す符号を出力するためのものである。
【０１９３】
ステップＳ５１２のブロック終端判定処理は、ブロック内のすべての画素の処理が終わったか否かを判定するためのもので、処理を続ける必要がある間は第２予測値算出処理（ステップＳ５０２）以降の処理を繰り返す。
【０１９４】
ステップＳ５１３のブロック終端符号出力処理は、ブロックの終端を示す符号を出力するためのものである。ブロック終端符号は、ブロックのある時点から以後、差分値０がブロック終端まで続いていることを示すためのものである。
【０１９５】
次に、第４の実施形態における復号化処理を図６のフローチャートに従って説明する。この処理は、上記の符号化処理で得られた符号化データを何らかの手段（例えばＣＤ−ＲＯＭ等の記憶媒体、あるいは、ネットワークを介しての受信等）で取得した符号化データを復号するものと言えば分かりやすい。
【０１９６】
先ず、ステップＳ６０１の初期化処理では一致数カウンタのクリア、第２予測的中数カウンタのクリア、連続性判定結果初期値（連続性大）の設定を行う。
【０１９７】
ステップＳ６０２における第２予測値算出処理、ステップＳ６０３の連続性判定処理、ステップＳ６０４の第１予測値設定処理、ステップＳ６０５における第２予測値設定処理は、それぞれ図５に示した、ステップＳ５０２の第２予測値算出処理、ステップＳ５０３の連続性判定処理、ステップＳ５０４の第１予測値設定処理、ステップＳ５０５の第２予測値設定と等価な処理である。
【０１９８】
ステップＳ６０６における一致数カウンタ判定処理では、一致数カウンタの値が０か否かによって分岐を行う。一致カウンタの値が０でない場合は、処理対象画素がそれ以前の画素から連続する差分値０の区間に含まれていることを意味する。従って、ステップＳ６０７に進んで、一致数カウンタのカウントダウンを行う。連続する差分値０のうちひとつが処理対象画素の差分値として使われたことを意味する。
【０１９９】
また、一致カウンタの値が０であった場合、ステップＳ６０８にて、１語の符号を読み取り、その内容によって後続するステップＳ６０９乃至６１１のいずれかに切り替える。  
差分値設定処理（ステップＳ６０９）は、符号読み取りステップＳ６０８で差分値符号を読み取った場合の処理であり、読み取った符号に従った値を処理対象画素の差分値として使用するように設定する。
【０２００】
一致数設定処理（ステップＳ６１０）は、ステップＳ６０８で一致数符号を読み取った場合の処理であり、符号の示す連続する差分０の数から１を減じた値を一致数カウンタに設定する。１を減じるのは符号が示す数に処理対象画素も含まれているためである。
【０２０１】
終端符号設定処理（ステップＳ６１１）は、ステップＳ６０８でブロックの終端符号を読み取った場合の処理であり、ブロック内の総画素数の値を一致数カウンタに設定する。こうすることで、以後はブロック内の各画素の処理で符号読み取り処理（ステップＳ６０８）には到達せず、また、差分値０を使用するようになる。
【０２０２】
差分０設定処理（ステップＳ６１２）は、差分符号を読み取った場合を除くすべての場合において、処理対象画素の差分値を０に設定するためのものである。
【０２０３】
画素復元処理（ステップＳ６１３）は、第１予測値設定処理（ステップＳ６０４）、あるいは、第２予測値設定処理（ステップＳ６０５）で設定された予測値と、差分値設定処理（ステップＳ６０９）、あるいは、差分０設定処理（ステップＳ６１２）で設定された差分値との加算を行い、ディザ画素値を復元するためのものである。
【０２０４】
第２予測的中カウント処理（ステップＳ６１４）は、画素復元処理（ステップＳ６１３）で復元されたディザ画素値と、第２予測値算出処理（ステップＳ６０２）で算出された第２予測値との比較を行い、一致した場合に第２予測的中数カウンタのカウントアップを行うものである。第２予測的中数カウンタの値は連続性判定処理（ステップＳ６０３）で参照される。
【０２０５】
ブロック処理終了判定処理（ステップＳ６１５）は、ブロック内の画素すべての処理が終了したかどうかを判定するためのものである。処理を続ける必要がある間は第２予測値算出処理（ステップＳ６０２）以降の処理を繰り返す。
【０２０６】
以上説明したように、第４の実施形態においても、第３の実施形態と同様の作用効果を奏することができる。とくに、第４の実施形態によれば、パーソナルコンピュータ等の汎用情報処理装置で実行されるアプリケーション（の一部）に実装することが可能となる。  
なお、上記第４の実施形態でも予測値と注目画素値との差分を符号化する例を説明したが、これによって限定されない。
【０２０７】
先の第３の実施形態で説明したように、符号化装置では、予測値と注目画素値が一致しているか否かを示す一致／不一致判定用の符号を先ず生成し、不一致の場合にのみ注目画素値の符号を、その一致／不一致判定用符号に後続するように生成する。これを受けた復号装置では、符号が一致することを示している場合には予測値を注目画素値として出力し、不一致を示す符号があった場合には後続する符号で示される値を注目画素値として出力すればよいからである。
【０２０８】
これを実現するには、図５のフローチャート（符号化処理）において、ステップＳ５１１にて、注目画素値を符号として出力すればよい。なお、ステップＳ５０８では差分値０をカウントしているので、これは一致数をカウントしていると等価であり、変更は必要ない。また、図６のフローチャートでは、ステップＳ６１２にて予測値を結果の画素値として出力し、ステップＳ６０９では符号から直接結果の画素値を得ることとし、ステップＳ６１３は不要となる。
【０２０９】
＜第５の実施形態＞
本第５の実施形態における特徴とする点は、各画素毎にその画素が文字線画領域の画素であるか、非文字線画領域（中間調領域）の画素であるかを示す属性情報を入力し、この属性を予測値の決定に用いる点である。以下では、文字線画領域／非文字線画領域を単に文字／非文字として表現することとする。また、この文字／非文字は１ビットで表現できる。
【０２１０】
なお、文字／非文字等の属性情報を付与する技術は、例えば、特開平５−５６２８７号のように画像データの輪郭、濃度、色等によって判定するものとするが、一般に、文字線画の場合には隣接する画素の濃度（もしくは輝度）の変化が、所定閾値よりも急峻であることを利用することが多く、実施形態でもこれにしたがうものする。
【０２１１】
図１０は本第５の実施形態における画像符号化装置のブロック構成図である。入力端子１１０９、参照画素値記憶部１１０１、閾値記憶部１１０３、第２予測部１１０４は、図１における入力端子１０９、参照画素値記憶部１０１、閾値記憶部１０３、第２予測部１０４と同じであるので、その説明は省略する。
【０２１２】
１１１１は、文字／非文字の属性情報の入力端子であって、画像入力端子１１０９で入力される画素データと同期して属性情報を入力する。参照属性値記憶部１１０５は、ディザマトリクスのサイズに依存した数の属性情報を一時的に記憶する。本第５の実施形態でも符号化対象の画像は図３（ａ）乃至（ｃ）のディザマトリクスを用いて４値化されるものとしているので、参照属性値記憶部１１０５は８画素分の属性情報を記憶する。
【０２１３】
本第５の実施形態でも、ライン単位に符号化処理を行う。まず、各ラインの先頭において初期化処理を行う。初期値は復号処理で同じ設定をする限りは以下に示す値に限定されないが、本第５の実施形態でも以下のように定める。
・参照画素値記憶部１１０１の内容はすべて所定値（実施形態では０とする）を示す画素値を格納しておく。
・閾値記憶部１１０３には、ディザ閾値のうち処理対象ラインに相当する行の値を格納しておく。
・参照属性値記憶部１１０５の内容はすべて非文字に設定する。
・符号化部１１０７の一致カウンタを０に設定する。
【０２１４】
その後、各部は以下に説明する処理を行って圧縮符号化画像データを生成する。
【０２１５】
入力であるディザ画像データは、処理対象画素のほか過去８画素分（ディザマトリクスの列数に相当する画素数）を記憶する参照画素値記憶部１１０１に一時保存される。同様に、過去８画素分の属性値は参照属性値記憶分１１０５に一時保存される。
【０２１６】
第２予測部１１０４は、現処理対象である注目画素Ｄiからディザマトリクスの列数だけ（実施形態では８画素）離れた参照画素Ｄi-8を参照画素値記憶部１１０１より取り出し、その値を第２予測値とする。初期化処理によって参照画素値記憶部１１０１の内容はすべて所定値（実施形態では０）を示す画素値となるので、ラインの先頭から８画素分については“０”が予測値として出力されることになる。
【０２１７】
一方、第１予測部１１０２は従来苦手としていた縦縞画像における予測精度の向上のためのものである。第１予測部１１０２は、まず、注目画素の直前の画素から順にさかのぼって、参照属性値記憶分１１０５に「文字」を示す属性を探索する。文字属性の画素がある場合は、最初に見つかった文字属性を有する画素値を第１予測参照値として参照画素値記憶部１１０１より取り出す。
【０２１８】
そして、その参照画素値と、閾値Ｔｈi、Ｔｈi-1に基づいて、注目画素の第１予測値を求める。この第１予測値を求める条件は、第３の実施形態で説明した図４にしたがうものとする。注意したい点は、第３の実施形態では図４における「参照画素値」は注目画素の直前の画素値Ｄiであったのに対し、本第５の実施形態での「参照画素値」は、注目画素の直前画素から遡って最初に「文字」属性を有する画素値とする点である。
【０２１９】
なお、文字属性の探索に失敗した場合、すなわち、参照属性記憶部１１０５に記憶された８つの属性がすべて「非文字」を示す情報であった場合には、既定値（例えば黒色を示す値）を第１予測値として決定する。ここで「黒色」とは、実施形態における画像データが濃度成分で表現されている場合には最大値の“３”となるし、輝度成分で表現されている場合には最小値の“０”となる。
【０２２０】
属性符号化部１１０９は、入力された属性値を符号化し、属性符号を生成するためのものである。属性値は１ビット（２値）で表わされるので、従来知られている技術、たとえば、ファクシミリなどで使用されているＭＭＲ（Ｍｏｄｉｆｉｅｄ  Ｍｏｄｉｆｉｅｄ  ＲＥＡＤ）符号での符号化を行うものとする。
【０２２１】
予測値選択部１１０６は、注目画素の属性値に従って、第１予測値と第２予測値のいずれか一方を選択し、最終的な予測値として画像符号化部１１０７に出力する。本第５の実施形態は、注目画素が文字属性を有する場合には第１予測値、非文字属性の場合に第２予測値を選択する。
【０２２２】
画像符号化部１１０７はディザ画像データである注目画素値と予測値選択部１１０６によって選択された予測値との差分を符号化し、画像符号を生成するためのものである。差分値０（ディザ画像データと予測値が一致した場合）についてランレングス圧縮を行うために、本第５の実施形態でも、画像符号化部１１０７はディザ画像データと予測値が連続して一致した数を数える一致カウンタを備える。
【０２２３】
画像符号化部１１０７は、第３の実施形態と同様である。すなわち、ライン終端に至るまで以下の処理を繰り返すことになる。
・ディザ画像データと予測値が一致した場合は一致カウンタをカウントアップする。
・ディザ画像データと予測値が一致しない場合は、まず一致カウンタの値に従って一致数を示す符号を出力し、一致カウンタをクリアする。次に差分値を示す符号を出力する。
・ライン終端においては、ライン終端を示す符号（ライン終端までの差分がすべて０であることを示す）を出力する。
【０２２４】
出力符号は既知の圧縮符号化方法（たとえばハフマン符号、算術符号、ＬＺ符号など）によって圧縮し、その結果を圧縮画像データとする。どちらの予測値を選択したのか、また、選択された予測値によって異なる符号表を用いるようにすることもできる。
【０２２５】
符号連結部１１０８は、保存や伝送における利便性を向上させるために、属性符号化部１１０９が生成した属性符号と画像符号化部１１０７が生成した画像符号とを連結し、画像・属性符号とするためのものである。
【０２２６】
本第５の実施形態では属性データを圧縮し、圧縮画像データに転結して最終符号化データを生成したが、属性符号は画像データと比較して情報量が少ないので圧縮しない方法もある。また、画像符号と属性符号とを別々に出力することも可能である。
【０２２７】
図１１は図１０の画像符号化装置と対を成す画像復号装置の構成を示す図である。本第５の実施形態では、１ラインを構成する画素数やディザマトリクスの大きさはあらかじめ決められているものとするが、圧縮画像データ中に記録しておくように構成こともできる。
【０２２８】
各ラインの先頭において図１０の画像処理（符号化）装置と同様に以下に示す初期化処理を行う。
・参照画素値記憶部１２０１の内容はすべて所定値（実施形態では０とする）を示す画素値を格納する。
・閾値記憶部１２０３には、ディザ閾値のうち処理対象ラインに相当する行の値を格納しておく。
・符号化部１２０７の一致カウンタを０に設定する。
・参照属性値記憶部１２１１の内容ははすべて非文字に設定する。
【０２２９】
これらの初期値は以上のようにあらかじめ決められた値を使用するほか、圧縮画像データの一部として記録しておいてその内容に従って初期化を行うように構成することもできる。
【０２３０】
入力端子１２０９より入力された符号データは符号分離部１２０８によって、差分符号と属性符号に分離される。
【０２３１】
差分値復号部１２０９は以下の手順で差分値を得る。この差分値復号部１２０９は連続するディザ画像データと予測値が連続して一致した数を数える一致カウンタを備える。差分値復号部１２０９はライン終端の符号を検出するまで以下の処理を繰り返す。
・一致カウンタが０でない場合、一致カウンタをカウントダウンして差分値０を出力する。
・一致カウンタが０の場合、差分復号部は入力符号を読み取る。
ここで、入力符号が一致数を示す場合には差分値０を出力し符号が示す一致数から１減算した値を一致カウンタにセットする。また、入力符号が差分値を示す場合にはその差分値を出力する。
【０２３２】
ライン終端の符号を検出した後は次のラインの処理に移るまで繰り返し差分値０を出力する。
【０２３３】
以上の手順によって図１０における符号化部１１０７の生成した圧縮画像データから差分値を得ることが可能となる。
【０２３４】
属性値復号部１２１０は、属性符号から属性値を得るためのものである。属性値復号部１２１０によって選られた属性値は参照属性値記憶部１２１１に一時保存される。
【０２３５】
ディザ画像データ復元部１２０７は予測値選択部１２０６が選択した予測値と差分復号部１２０９によって得られた差分値とを加算することでディザ画像データを復元する。ディザ画像データ復元部１２０７が最初の出力を得るまでの手順を以下に説明する。
【０２３６】
参照画素値記憶部１２０１および参照属性値記憶部１２１１は初期化処理によって図１０における参照画素値記憶部１１０１および参照属性値記憶部１１０５と同じ初期値に設定されている。
【０２３７】
第２予測部１２０４は、図１０における第２予測部１１０４と同じ方法で第２予測値を算出する。初期化処理によって参照画素値記憶部１２０１の内容はすべて所定値（実施形態では０）となるので、最初の第２予測値は“０”の画素値となる。
【０２３８】
一方、第１予測部１２０２は、参照属性値記憶部１２１１の内容がすべて非文字属性のため第１予測値として既定値を出力する。
【０２３９】
予測値選択部１２０６は図１０における予測値選択部１１０６と同様である。文字属性の場合に第１予測値、非文字属性の場合に第２予測値を選択する。
【０２４０】
これは予測値選択部１１０６の最初の予測値に等しいため、差分復号部１２０９によって得られた差分値からディザ画像データ画素値を復元することができる。
【０２４１】
ディザ画像データ復元部１２０７によって得られた最初のディザ画像データ画素値は参照画素記憶部１２０１に記憶される。このように構成することで、参照画素記憶部１２０１の記憶内容は図１０における参照画素記憶部１１０１と同じ内容になる。
【０２４２】
また、参照属性値記憶部１２１１の内容をディザ画像データ画素値の出力と同期して更新することで、図１０における参照属性値記憶部１１０５と同じ内容にすることが可能である。
【０２４３】
よって、後続する画素に対する予測値も符号化処理時と同じ値を求めることが可能で、差分値からディザ画像データを復元することができる。
【０２４４】
以上の結果、文字線画か非文字線画（中間調画像）かを示す属性を元に、それぞれの属性に応じて予測値を決めることで、写真画像等の階調画像、文字原稿画像のいずれか、或いは、混在した画像を入力した場合においても、それぞれの像域に応じた符号化を行うことが可能となり、先に説明した第３の実施形態と同様の作用効果を奏することが可能となる。特に、第５の実施形態の場合、復号装置側では、属性情報を含めて復号することができるので、例えばプリンタ等の画像形成装置に適用した場合、文字属性の画素、中間調の画素ぞれぞれに適した記録が行えることになり、優れた画質の印刷を行うことも可能になる。
【０２４５】
なお、上記第５の実施形態でも予測値と注目画素値との差分を符号化する例を説明したが、第３、第４の実施形態で説明したように、符号化装置では、予測値と注目画素値が一致しているか否かを示す一致／不一致判定用の符号を先ず生成し、不一致の場合にのみ注目画素値の符号を、その一致／不一致判定用符号に後続するように生成する。これを受けた復号装置では、符号が一致することを示している場合には予測値を注目画素値として出力し、不一致を示す符号があった場合には後続する符号で示される値を注目画素値として出力しても構わない。これは、以下に説明する第６の実施形態でも同様である。
【０２４６】
＜第６の実施形態＞
次に第６の実施形態を説明する。本第６の実施形態はコンピュータプログラムによって実現する例である。装置構成は、第４の実施形態で示した図９と同様であるものとし、その説明は省略する。
【０２４７】
また、比較を容易にするため、本第６の実施形態では、第４の実施形態と同様、８×４画素ブロック単位で圧縮を行うこととする。従って、１ページを４ラインごとのバンドに区切り、さらに各バンドを左端から８画素づつ区切ったものがブロックとなる。また、ブロック内での処理順序は、位置が近い画素を続けて処理するよう考慮して図７に示す順番とする。垂直方向の相関も第１予測値に反映させるためである。そして、１ページの符号化は上から下へとバンドの順に行い、各バンド内では左から右へとブロックの順に行う。  
以下、本第６の実施形態の符号化処理手順を図１２のフローチャートに従って説明する。
【０２４８】
ステップＳ１５０１の初期化処理では、一致数カウンタのクリアを行う。次のステップＳ１５０２では、処理対象画素の属性を判定する。これは、第１予測値を用いるか、第２予測値を用いるか判定するためである。
【０２４９】
ステップＳ１５０３に処理が進んだ場合には、第１予測値を算出する。この第１予測値は処理対象画素を含まない過去の直近３画素の中央値とする。ブロックの初めでは直前のブロック（以下参照ブロック）の終わりの画素を使用することになる。各バンドで左端のブロックにおいては参照ブロックは存在しないので、すべて所定値（実施形態では０）の画素値を持つものとして扱う。
【０２５０】
最近の高解像度の画像データでは、通常の文字の字画でも数画素ないし十数画素の幅を持っている。本第６の実施形態の第１予測値はこのような文字部分での簡易的な予測を狙ったものである。
【０２５１】
一方、ステップＳ１５０４に進んだ場合には、第２予測値を算出する。この第２予測値は、参照ブロック内の、処理対象画素と同じ相対位置の画素値とする。
【０２５２】
ステップＳ１５０５では、図７の順番に処理対象ディザ画素値（注目画素値）を読出し、その処理対象画素の属性応じて第１予測値値、第２予測値のいずれかとの差分を算出し、差分が０であるか否かを判定する。
【０２５３】
差分が０、すなわち、注目画素値が予測値と一致した場合には、ステップＳ１５０６に進み、連続する差分値０を計数するための一致数カウンタのカウントアップする（“１”だけ増加させる）。
【０２５４】
また、ステップＳ１５０５にて、差分が０以外であると判断した場合には、ステップＳ１５０７に進み、一致数カウンタを調べる。
【０２５５】
ここで、一致数カウンタが０でない場合は、直前の画素およびそれ以前に連続する差分値０の画素は一致数カウントアップ（ステップＳ１５０６）で数えられているだけで出力符号に反映されていないことを意味する。従って、ステップＳ１５０８にて、差分０の連続数を示す符号を出力する。
【０２５６】
ステップＳ１５０９では、処理対象画素（注目画素）と予測値との差分を示す符号を出力する。
【０２５７】
そして、ステップＳ１５１０にて、ブロック終端判定、すなわち、ブロック内のすべての画素の処理が終わったか否かを判定する。否の場合には、ステップＳ１５０２以降の処理を繰り返す。
【０２５８】
また、１つのブロックの処理が完了したと判断した場合には、ステップＳ１５１１に進み、ブロックの終端を示す符号を出力する。このブロック終端符号は、ブロックのある時点から以後、差分値０がブロック終端まで続いていることを示すためのものである。
【０２５９】
なお、上記では、属性情報の符号化について説明しなかったが、先に説明したように公知のＭＭＲ等の符号化技術を用いて符号化が行われるものとしている。
【０２６０】
次に、復号処理を図１３のフローチャートに従って説明する。属性情報については公知の復号技術を使って復号するものとし、ここでは画像データの復号処理について説明することとする。
【０２６１】
ステップＳ１６０１では、一致カウンタのクリア等の初期化処理を行う。次いで、ステップＳ１６０２にて、注目画素の属性を判定し、文字属性である場合にはステップＳ１６０３にて第１予測値を算出し、非文字属性である場合にはステップＳ１６０４にて第２予測値を算出する。このステップＳ１６０２〜１６０４の処理は、図１２におけるステップＳ１５０２〜Ｓ１５０４と等価な処理である。
【０２６２】
ステップＳ１６０５では、一致数カウンタの値が０か否かによって分岐を行う。一致カウンタの値が０でないということは、復号対象の画素（注目画素）が、それ以前の画素から差分値０の連続区間に含まれていることを意味する。従って、ステップＳ１６０６にて、一致数カウンタのカウントダウンを行い、連続する差分値０のうちひとつが処理対象画素の差分値として使われたことにする。
【０２６３】
また、一致カウンタが０である場合には、ステップＳ１６０７に進む。ここでは、１語の符号を読み取り、その内容によって後続する処理を切り替える。
【０２６４】
ステップＳ１６０８の差分値設定処理は、ステップＳ１６０７で差分値符号を読み取った場合の処理であり、読み取った符号に従った値を処理対象画素の差分値として使用するように設定する。
【０２６５】
ステップＳ１６０９の処理は、読取った符号が一致数符号の場合の処理であり、符号の示す連続する差分０の数から１を減じた値を一致数カウンタに設定する。１を減じるのは符号が示す数に処理対象画素も含まれているためである。
【０２６６】
また、ステップＳ１６１０の終端符号設定処理は、読取った符号がブロックの終端符号であった場合の処理であり、ブロック内の総画素数の値を一致数カウンタに設定する。こうすることで、以後はブロック内の各画素の処理で符号読み取り（ステップＳ１６０７）には到達せず、また、ブロック内の残る画素の処理で差分値０を使用するようになる。
【０２６７】
ステップＳ１６１１では、差分符号を読み取った場合を除くすべての場合において、処理対象画素の差分値を０に設定するためのものである。
【０２６８】
ステップＳ１６１２は、第１予測値算出処理（ステップＳ１６０３）、あるいは、第２予測値算出処理（ステップＳ１６０４）で設定された予測値と、差分値設定処理（ステップＳ１６０８）、あるいは、差分０設定処理（ステップＳ１６１１）で設定された差分値との加算を行い、ディザ画素値を復元するためのものである。
【０２６９】
そして、ステップＳ１６１３では、ブロック内の画素すべての処理が終了したかどうかを判定する。否の場合には、ステップＳ１６０２以降の処理を繰り返すことになる。
【０２７０】
以上説明した通り、本第５、第６の実施形態においても、比較的簡単な方法で、ディザ画像データに対する圧縮・伸長が可能となる。特に、従来苦手としていた縦縞部分あるいは文字部分に対して高い効果が期待できる。
【０２７１】
なお、上記第３乃至第６の実施形態では、モノクロ２５６階調の画像データを、周期的に変化する閾値を用いて４値化した画像を符号化するものとしたが、モノクロに限らずカラー画像に適用してもよい。カラーに適用する場合には、各色成分について同様の処理を行えば良いからである。また、符号化対象は４値化画像のみに限定されるものではなく、一般に利用可能性の高い２値化画像をはじめ、如何なる階調数の画像でも構わない。
【０２７２】
更に、実施形態で説明したように、本発明は、コンピュータプログラムをもその範疇とする。そして、一般にコンピュータプログラムがＣＤＲＯＭ等のコンピュータ可読記憶媒体をコンピュータにセットして、システムにコピーもしくはインストールすることで実行可能となるわけであるから、当然、そのようなコンピュータ可読記憶媒体も本発明の範疇に含まれるのは明らかである。
【０２７３】
＜第７の実施形態＞
本第７の実施形態は、上述した第３の実施形態（即ち、閾値の変化周期と等しい縦縞画像データに対しても良好な圧縮を実現するために、閾値の周期を利用した予測と注目画素の近傍画素値による予測との２種類の予測を適応的に選択する場合）における第１予測部１０２による第１予測に、第２の実施形態に相当する技術を利用するものである。よって必要に応じて、第２、第３の実施形態を参照されたい。
【０２７４】
この場合、第２の実施形態で説明した場合と同様、ディザ閾値はパラメータθ，ω，ｄを決め、入力画像データの階調数ｎ・画素位置（ｘ，ｙ）から以下の式（式１−１，式１−２，式２，式３）により閾値ｔを算出する。これは、図３７のように周期１／ωの格子を角度θだけ回転させたものに相当する。
x' = x cosθ - y sinθ  ...(式1-1)
y' = x sinθ + y cosθ  ...(式1-2)
a = sin(2πωx') + sin(2πωy')      ...(式2)
t =  (a+2)×(n - 2d - 3) / 4 + d + 3/2    ...(式3)
実際には、ｓｉｎθ、ｃｏｓθは有限ビット長で表現し、また、閾値ｔは最終的に小数部を切り捨て整数として算出するものとする。すると、閾値ｔはｄ＋１以上ｎ−ｄ−２以下の整数となる。
【０２７５】
閾値比較部は、入力画素値ｐと閾値ｔを比較して、出力画素値ｒを求める。このとき、ｐ＜ｔ−ｄならばｒ＝０とし、ｐ＞ｔ＋ｄならばｒ＝２とし、どちらにも該当しなければｒ＝１とする。
【０２７６】
第１予測手段（第１予測部１０２に相当）は第２の実施形態における予測値計算部２５０２と同様の構成になる。
【０２７７】
第２予測手段（第２予測部１０４に相当）については、閾値の周期が一般には整数とはならない。有限ビット長の演算なのでいずれ循環するが、その周期が非常に長くなり実用的でない場合もある。このため、必要ならば以下のように近似する。
【０２７８】
上記閾値は、水平方向にｃｏｓθ／ωかつ垂直方向にｓｉｎθ／ω、もしくは、水平方向に−ｓｉｎθ／ωかつ垂直方向にｃｏｓθ／ωだけ離れた画素と同一となる。
【０２７９】
そこで、ｍ，ｎを整数としたときに、以下のΔｘ、Δｙが整数に近くなるような既処理画素を選び、当該画素値を第２予測値とする。
Δx = (m・cosθ - n・sinθ)/ω
Δy = (m・sinθ + n・cosθ)/ω
既処理画素は図２４（ａ）の画素順で処理を行うとすれば、以下の条件となる。
Δy ＜ 0 もしくは
Δy ＝０  且つ、Δx＜０
以上のように第２予測値を求めることで第３乃至第６の各実施形態と同様に本発明を適用することが可能となる。
【０２８０】
以上本発明に係る実施形態を説明したが、本発明はパーソナルコンピュータ等の汎用情報処理装置でも実行できるものであるから、当然、本発明はコンピュータプログラムをもその範疇とすることができる。また、通常、コンピュータでプログラムを実行可能とするためには、該当するコンピュータプログラムを格納したＣＤ−ＲＯＭのコンピュータ可読記憶媒体をコンピュータにセットし、システムにコピーもしくはインストールすることで行われるから、このようなコンピュータ可読記憶媒体も本発明の範疇に含まれるのは明らかである。
【図面の簡単な説明】
【０２８１】
【図１】第３の実施形態における画像符号化装置のブロック構成図である。
【図２】第３の実施形態における画像復号装置のブロック構成図である。
【図３】実施形態におけるディザマトリクスの例を示す図である。
【図４】実施形態における第１予測値の算出条件を示す図である。
【図５】第４の実施形態における画像符号化装置の処理手順を示すフローチャートである。
【図６】第４の実施形態における画像復号装置の処理手順を示すフローチャートである。
【図７】第４の実施形態におけるブロック内の画素処理順序を示す図である。
【図８】第３の実施形態における連続性判定部１０５のブロック構成図である。
【図９】第４の実施形態における装置のブロック構成図である。
【図１０】第５の実施形態における画像符号化装置のブロック構成図である。
【図１１】第５の実施形態における画像符号化装置のブロック構成図である。
【図１２】第６の実施形態における画像符号化装置の処理手順を示すフローチャートである。
【図１３】第６の実施形態における画像復号装置の処理手順を示すフローチャートである。
【図１４】第１実施形態の画像符号化装置のブロック構成図である。
【図１５】第１の実施形態におけるディザマトリクスの閾値を示す図である。
【図１６】入力多値画像の画像データの例を示す図である。
【図１７】２値化処理後の２値画像データを示す図である。
【図１８】図１４における閾値比較部が出力する出力画素値と閾値の対を示す図である。
【図１９】第１の実施形態における予測値を求める条件テーブルを示す図である。
【図２０】図１における予測値計算部が出力する予測値を示すデータである。
【図２１】図１７と図２０の差分データを示す図である。
【図２２】第１の実施形態における画像復号装置のブロック構成図である。
【図２３】第１の実施形態での符号化処理をコンピュータプログラムで行う場合の差分データ生成処理手順を示すフローチャートである。
【図２４】スキャンする方向の例を示す図である。
【図２５】第２実施形態の画像符号化装置のブロック構成図である。
【図２６】第２の実施形態における属性および閾値と濃度クラスの関係を示す図である。
【図２７】第２の実施形態における参照画素選択における優先順位を示す図である。
【図２８】第２の実施形態における文字属性の入力画素値と出力画素値の関係を示す図である。
【図２９】第２の実施形態における文字属性の入力値と出力値の例を示す図である。
【図３０】第２の実施形態における文字属性の画素についての予測値を示す図である。
【図３１】第２の実施形態における画像属性の入力画素値と出力画素値の関係を示す図である。
【図３２】第２の実施形態における画像属性の画素についての予測値を示す図である。
【図３３】第２の実施形態における予測値および差分値と中間符号の関係を示す図である。
【図３４】第２の実施形態における中間符号と出力符号の関係を示す図である。
【図３５】第２の実施形態における二つの出力符号を組み合わせた符号の例を示す図である。
【図３６】相関度演算手段の参照する画素の位置を説明する図である。
【図３７】第７の実施形態における閾値の周期性を説明する図である。
【図３８】第３の実施形態における４値化するディザ変換回路の構成を示す図である。
【図１】
2005323326.tif 000003
【図２】
2005323326.tif 000004
【図３】
2005323326.tif 000005
【図４】
2005323326.tif 000006
【図５】
2005323326.tif 000007
【図６】
2005323326.tif 000008
【図７】
2005323326.tif 000009
【図８】
2005323326.tif 000010
【図９】
2005323326.tif 000011
【図１０】
2005323326.tif 000012
【図１１】
2005323326.tif 000013
【図１２】
2005323326.tif 000014
【図１３】
2005323326.tif 000015
【図１４】
2005323326.tif 000016
【図１５】
2005323326.tif 000017
【図１６】
2005323326.tif 000018
【図１７】
2005323326.tif 000019
【図１８】
2005323326.tif 000020
【図１９】
2005323326.tif 000021
【図２０】
2005323326.tif 000022
【図２１】
2005323326.tif 000023
【図２２】
2005323326.tif 000024
【図２３】
2005323326.tif 000025
【図２４】
2005323326.tif 000026
【図２５】
2005323326.tif 000027
【図２６】
2005323326.tif 000028
【図２７】
2005323326.tif 000029
【図２８】
2005323326.tif 000030
【図２９】
2005323326.tif 000031
【図３０】
2005323326.tif 000032
【図３１】
2005323326.tif 000033
【図３２】
2005323326.tif 000034
【図３３】
2005323326.tif 000035
【図３４】
2005323326.tif 000036
【図３５】
2005323326.tif 000037
【図３６】
2005323326.tif 000038
【図３７】
2005323326.tif 000039
【図３８】
2005323326.tif 000040