(57)【要約】【課題】各種画像において平均的に符号化効率が高く、高速で画像を符号化することが可能な画像符号化技術を提供する。【解決手段】走査径路を記憶する走査径路メモリ１３、画像を走査し一次元化画像を生成する走査手段１４、一次元化画像の各画素に対し当該画素から所定の距離以内にあり当該画素より前に走査されている参照画素から当該画素の予測画素値を算出し、予測誤差を算出する線形予測手段１６を備えた走査予測演算ユニット６を複数個備え、各走査径路メモリ１３には、それぞれ異なる走査径路が記憶されており、線形予測手段１６が出力する予測誤差の符号化効率が最も高くなる走査予測演算ユニット６を選択する最適走査選択手段７、最適走査選択手段７が選択した走査予測演算ユニット６の前記線形予測手段１６が出力する予測誤差を符号化する画像符号化手段８を備えた。【選択図】        図１
2005039723.tif 000002
【特許請求の範囲】
【請求項１】
画像の走査順序である走査径路を記憶する走査径路メモリと、
前記走査径路に従って入力された画像を走査して一次元化画像を生成する走査手段と、
前記一次元化画像の各画素に対して、当該画素から所定の距離以内にある画素であって当該画素よりも前に走査されている参照画素から、当該画素の画素値の予測値である予測画素値を算出し、当該画素の画素値と前記予測画素値との差である予測誤差を算出する線形予測手段と、
を備えた走査予測演算ユニットを複数個備え、
各走査予測演算ユニットの走査径路メモリには、それぞれ異なる走査径路が記憶されており、
前記各走査予測演算ユニットのうち、前記線形予測手段が出力する予測誤差の符号化効率が最も高くなる走査予測演算ユニットを選択する最適走査選択手段と、
前記最適走査選択手段が選択した走査予測演算ユニットの前記線形予測手段が出力する予測誤差を符号化する画像符号化手段と、
を備えていることを特徴とする画像符号化装置。
【請求項２】
前記各走査予測演算ユニットは、前記走査径路の各画素に対して、当該画素の画素値を予測するための参照画素の座標情報をルックアップテーブルとして記憶する参照画素メモリを備え、
前記線形予測手段は、前記ルックアップテーブルに記憶された参照画素の画素値から、前記走査径路の各画素に対して、当該画素の画素値の予測値である予測画素値を算出し、当該画素の画素値と前記予測画素値との差である予測誤差を算出することを特徴とする請求項１記載の画像符号化装置。
【請求項３】
入力された画像を複数の小領域に分割する小領域分割手段を備え、
前記各走査予測演算ユニットは、前記画像の小領域のそれぞれについて、各小領域ごとに予測誤差を算出すること
を特徴とする請求項１又は２に記載の画像符号化装置。
【請求項４】
前記各走査予測演算ユニットは、
前記線形予測手段が出力する各画素に対する前記予測誤差の値の分布から予測誤差のエントロピを算出するエントロピ算出手段を備え、
前記最適走査選択手段は、前記エントロピ算出手段が出力するエントロピのうちで最小のものに対応する前記走査予測演算ユニットを選択することを特徴とする請求項１乃至３の何れか一記載の画像符号化装置。
【請求項５】
画像の走査順序である走査径路を記憶する走査径路メモリに記憶されている前記走査径路に従って、入力された画像を走査して一次元化画像を生成するステップ、
及び、前記一次元化画像の各画素に対して、当該画素から所定の距離以内にある画素であって当該画素よりも前に走査されている参照画素から、当該画素の画素値の予測値である予測画素値を算出し、当該画素の画素値と前記予測画素値との差である予測誤差を算出するステップを有する走査予測演算を、異なる複数の走査径路について実行し、
前記各走査径路のうち、前記予測誤差の符号化効率が最も高くなる走査径路を選択し、
前記走査径路により走査したときの前記予測誤差を符号化することを特徴とする画像符号化方法。
【請求項６】
前記各走査予測演算においては、前記走査径路の各画素に対して参照画素メモリにルックアップテーブルとして記憶されている当該画素の画素値を予測するための参照画素の画素値から、前記走査径路の各画素に対して、当該画素の画素値の予測値である予測画素値を算出し、当該画素の画素値と前記予測画素値との差である予測誤差を算出することを特徴とする請求項５記載の画像符号化方法。
【請求項７】
入力された画像を複数の小領域に分割し、
前記各走査予測演算においては、前記画像の小領域のそれぞれについて、各小領域ごとに予測誤差を算出すること
を特徴とする請求項５又は６に記載の画像符号化方法。
【請求項８】
前記各走査予測演算においては、各画素に対する前記予測誤差の値の分布から予測誤差のエントロピを算出し、
前記各走査予測演算において算出されたエントロピのうちで最小のものに対応する前記走査径路を、前記予測誤差の符号化効率が最も高くなる走査径路として選択することを特徴とする請求項５乃至７の何れか一記載の画像符号化方法。
【請求項９】
コンピュータに読み込み実行することにより、前記コンピュータを請求項１乃至４の何れか一に記載の画像符号化装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を符号化する画像符号化技術に関し、特に、高速で符号化効率の高い画像符号化技術に関する。
【背景技術】
【０００２】
画像通信や画像蓄積においては、扱う情報量がテキストや音声などに比べて膨大であるため、画像符号化技術を用いてデータの圧縮が行われる。画像符号化技術には、画像情報を保存しつつ画像データを圧縮する可逆圧縮と、画像の持つ統計的性質や視覚的性質を利用して画像の情報量を削減し原画像情報の総ては保存されない非可逆圧縮とに分類される。医療分野や歴史的文化財等のデジタル・アーカイビング分野等で使用される自然画像は、データの精度が重要であるため、可逆圧縮が用いられる。また、パーソナル・コンピュータやＷｅｂ上で使用される文字やグラフィックス等の人工画像も、出力媒体をハードコピーと考えると、画像圧縮においては可逆圧縮が要求される。
【０００３】
従来、可逆圧縮による画像符号化技術としては、ＪＰＥＧ−ＬＳが知られている（例えば、非特許文献１参照）。非特許文献１記載の方法においては、画像をラスタ走査により走査し一次元化する。また、それとともに、各画素についての予測符号化が行われる。予測符号化は、符号化画素の周辺画素を参照して符号化画素の画素値（以下、「符号化画素値」という。）を予測するステップと、予測値と実際の符号化画素値との差分値である予測誤差を符号化するステップからなる。ＪＰＥＧ−ＬＳにおいては、符号化画素値を予測するステップにおいては、ＭＥＤ予測器（Median Edge Detection predictor）が使用される。すなわち、各符号化画素値ｘの予測値は、当該符号化画素よりも前に走査された周辺画素の画素値ａ，ｂ，ｃを使用して、（数１）により行われる。
【０００４】
【数１】
2005039723.tif 000003
【０００５】
ここで、ラスタ走査は上から下の行に、左から右の画素に順次操作される。ａは符号化画素の左隣の画素、ｂは符号化画素の上隣の画素、ｃは符号化画素の左上隣の画素の画素値を表している。
【０００６】
一方、これとは別に、特許文献１では、画像を複数の画素からなるブロックに分割し、ブロックごとに選択された走査パターンによりブロックを走査して１次元データ系列を生成し、生成された１次元データ系列をランレングス符号化する画像符号化方法が記載されている。この方法においては、走査パターンの選択では、あらかじめ複数の走査パターンを保持しておき、それらの走査パターンの中からブロック内の画素値の符号化に最も適した走査パターンを選択する。走査パターンの選択方法としては、ブロック内のランの数が最小となるものを選択する方法、ブロック内の符号長が最小となるものを選択する方法などが採られる。
【特許文献１】特開２００２−３５４２６７号公報
【非特許文献１】N.Memon, X.Wu,"Recent Developments in Context-Based Predictive Techniques for Lossless Image Compression", The Computer Journal, U.K., British Computer Society, 1997, Vol.40, N0.23, pp.127-136
【発明の開示】
【発明が解決しようとする課題】
【０００７】
以上のようなＪＰＥＧ−ＬＳによる画像符号化技術は、高い符号化効率で高速に画像の符号化を行うことを可能とする点で優れている。しかしながら、予測符号化は、画像のエッジ部分において、予測誤差が大きくなるため、符号化効率が低下するという欠点がある。ＪＰＥＧ−ＬＳでは、画像の走査方法がラスタ走査に限定されているために、画像の性質によっては高い符号化効率が得られない場合もある。特に、縦縞の多い画像では、ラスタ走査では走査線が画像内のエッジを多く横切ることとなる。そのため、予測符号化における予測誤差のダイナミックレンジが平均的に大きくなり、符号化効率は低下する。従って、種々の画像において符号化効率を向上させるには限界がある。
【０００８】
一方、上記特許文献１の画像符号化技術によれば、画像内のブロックごとに、各ブロック内の画像の性質に応じて操作方法を変更する。そのため、混成画像においても、画像のブロック領域ごとに操作方法の最適化がなされ、平均的な符号化効率を向上させる可能性はある。しかしながら、可逆圧縮においては、一般にランレングス符号化は予測符号化に比べて符号化効率が劣る場合が多い。特に、自然画像においてはランが短いため符号化効率の向上は望めない。そのため、種々の画像において平均的に符号化効率を向上させるにはやはり限界があるといえる。
【０００９】
そこで、本発明の目的は、種々の画像において平均的に符号化効率が高く、かつ高速に画像を符号化することが可能な画像符号化技術を提供することにある。
【課題を解決するための手段】
【００１０】
本発明に係る画像符号化装置の第１の構成は、画像の走査順序である走査径路を記憶する走査径路メモリと、前記走査径路に従って入力された画像を走査して一次元化画像を生成する走査手段と、前記一次元化画像の各画素に対して、当該画素から所定の距離以内にある画素であって当該画素よりも前に走査されている参照画素から、当該画素の画素値の予測値である予測画素値を算出し、当該画素の画素値と前記予測画素値との差である予測誤差を算出する線形予測手段と、を備えた走査予測演算ユニットを複数個備え、各走査予測演算ユニットの走査径路メモリには、それぞれ異なる走査径路が記憶されており、前記各走査予測演算ユニットのうち、前記線形予測手段が出力する予測誤差の符号化効率が最も高くなる走査予測演算ユニットを選択する最適走査選択手段と、前記最適走査選択手段が選択した走査予測演算ユニットの前記線形予測手段が出力する予測誤差を符号化する画像符号化手段と、を備えていることを特徴とする。
【００１１】
この構成によれば、最適走査選択手段により、画像の符号化効率が最も高くなるように、その画像に適した走査方法が選択される。すなわち、画像内のエッジを横切る回数が最も少ない走査径路が選択される。これにより、画像のエッジにおいて予測誤差が大きくなるという予測符号化の欠点が補われる。
【００１２】
また、各走査予測演算ユニットは、符号化対象となる画素（以下、「符号化画素」という。）の周辺の参照画素の画素値に基づき予測符号化を行うため、画素間の相関に基づく冗長性が除去され、エネルギーが集中化される。そのため、自然画像に対しても高効率で符号化することができる。
【００１３】
従って、画像の平坦部分ではエネルギー集中度が高い予測符号化の優位性を活かしつつ、走査径路の最適化により画像のエッジにおいて予測誤差が大きくなるという予測符号化の欠点が補償されるため、各種画像において平均的に符号化効率を高めることができる。また、予測符号化については、従来のように積和演算のみにより行うことが可能であり、符号化処理を高速に行うことが可能となる。
【００１４】
ここで、参照画素の位置を、符号化画素から所定の距離以内にある画素としたのは、参照画素を符号化画素との画素値の相関が大きい画素に限定するためである。従って、「所定の距離」は特に限定するものではないが、符号化画素との画素間相関が大きい距離とされる。また、ここでいう「距離」とは、ハミング距離やユークリッド距離等をいう。
【００１５】
また、参照画素として、「当該符号化画素よりも前に走査されているもの」に限定したのは、予測誤差系列を瞬時符号として構成するためである。これにより、予測誤差系列から画素値を復号する際に余分なバッファが必要なく、高速に復号が可能となる。
【００１６】
本発明に係る画像符号化装置の第２の構成は、上記第１の構成において、前記各走査予測演算ユニットは、前記走査径路の各画素に対して、当該画素の画素値を予測するための参照画素の座標情報をルックアップテーブルとして記憶する参照画素メモリを備え、前記線形予測手段は、前記ルックアップテーブルに記憶された参照画素の画素値から、前記走査径路の各画素に対して、当該画素の画素値の予測値である予測画素値を算出し、当該画素の画素値と前記予測画素値との差である予測誤差を算出することを特徴とする。
【００１７】
この構成によれば、各走査径路に対して参照画素の座標をルックアップテーブルに記憶させておくことで、任意の走査径路を使用する場合でも、複雑な演算を行うことなく参照画素座標を高速に取得することができる。
【００１８】
本発明に係る画像符号化装置の第３の構成は、上記第１又は２の構成において、入力された画像を複数の小領域に分割する小領域分割手段を備え、前記各走査予測演算ユニットは、前記画像の小領域のそれぞれについて、各小領域ごとに予測誤差を算出することを特徴とする。
【００１９】
この構成によれば、画像を小領域に分割して小領域ごとに最適な走査径路を選択して予測符号化を行うことができる。従って、各小領域において走査径路を画像の局所的性質に適合させ、予測誤差のエネルギー集中度を高めることができる。
【００２０】
本発明に係る画像符号化装置の第４の構成は、上記第１乃至３の何れか一の構成において、前記各走査予測演算ユニットは、前記線形予測手段が出力する各画素に対する前記予測誤差の値の分布から予測誤差のエントロピを算出するエントロピ算出手段を備え、前記最適走査選択手段は、前記エントロピ算出手段が出力するエントロピのうちで最小のものに対応する前記走査予測演算ユニットを選択することを特徴とする。
【００２１】
予測誤差のエントロピは、当該予測誤差を符号化した時の符号量と強い相関がある。従って、予測誤差のエントロピが最小となる走査径路を選択することで、予測誤差を符号化した際の符号量が最小となる走査径路を選択することができる。また、予測誤差のエントロピの演算は、予測誤差の符号化の演算に比べ高速に行うことが可能である。従って、最適な走査径路の選択を高速に行うことができる。
【００２２】
また、本発明においては、前記各走査予測演算ユニットは、各予測誤差の発生数に対するエントロピの値をルックアップテーブルとして格納するエントロピ・メモリを備え、前記エントロピ算出手段は、前記線形予測手段が出力する各画素に対する前記予測誤差の値の発生数から、前記エントロピ・メモリに格納されたルックアップテーブルを参照することにより前記予測誤差のエントロピを求める構成とすることができる。これにより、エントロピの演算を高速に行うことが可能となり、符号化処理速度が向上する。
【００２３】
本発明に係る画像符号化方法の第１の構成は、画像の走査順序である走査径路を記憶する走査径路メモリに記憶されている前記走査径路に従って、入力された画像を走査して一次元化画像を生成するステップ、及び、前記一次元化画像の各画素に対して、当該画素から所定の距離以内にある画素であって当該画素よりも前に走査されている参照画素から、当該画素の画素値の予測値である予測画素値を算出し、当該画素の画素値と前記予測画素値との差である予測誤差を算出するステップを有する走査予測演算を、異なる複数の走査径路について実行し、前記各走査径路のうち、前記予測誤差の符号化効率が最も高くなる走査径路を選択し、前記走査径路により走査したときの前記予測誤差を符号化することを特徴とする。
【００２４】
本発明に係る画像符号化方法の第２の構成は、上記第１の構成において、前記各走査予測演算においては、前記走査径路の各画素に対して参照画素メモリにルックアップテーブルとして記憶されている当該画素の画素値を予測するための参照画素の画素値から、前記走査径路の各画素に対して、当該画素の画素値の予測値である予測画素値を算出し、当該画素の画素値と前記予測画素値との差である予測誤差を算出することを特徴とする。
【００２５】
本発明に係る画像符号化方法の第３の構成は、上記第１又は２の構成において、入力された画像を複数の小領域に分割し、前記各走査予測演算においては、前記画像の小領域のそれぞれについて、各小領域ごとに予測誤差を算出することを特徴とする。
【００２６】
本発明に係る画像符号化装置の第４の構成は、上記第１乃至３の何れか一の構成において、前記各走査予測演算においては、各画素に対する前記予測誤差の値の分布から予測誤差のエントロピを算出し、前記各走査予測演算において算出されたエントロピのうちで最小のものに対応する前記走査径路を、前記予測誤差の符号化効率が最も高くなる走査径路として選択することを特徴とする。
【００２７】
本発明に係るプログラムは、コンピュータに読み込み実行することにより、前記コンピュータを前記第１乃至４の何れか一に記載の画像符号化装置として機能させることを特徴とする。
【発明の効果】
【００２８】
本発明によれば、画像の平坦部分ではエネルギー集中度が高い予測符号化の優位性を活かしつつ、走査径路の最適化により画像のエッジにおいて予測誤差が大きくなるという予測符号化の欠点が補償される。そのため、各種画像において平均的に符号化効率を高めることができる。また、予測符号化については、従来のように積和演算のみにより行うことが可能であり、符号化処理を高速に行うことが可能となる。
【００２９】
また、各走査径路に対して参照画素の座標をルックアップテーブルに記憶させておくことにより、任意の走査径路を使用する場合でも参照画素座標を高速に取得することができる。従って、容易に任意の走査径路を使用することができるとともに、符号化画素の画素値の予測演算も高速化することができる。
【００３０】
また、画像を小領域に分割して小領域ごとに最適な走査径路を選択して予測符号化を行うことで、各小領域において走査径路を画像の局所的性質に適合させ、予測誤差のエネルギー集中度を高めることができる。従って、小領域分割を行わない場合に比べて、符号化効率を向上させることが可能となる。
【００３１】
また、予測誤差のエントロピが最小となる走査径路を選択することで、予測誤差の符号化の演算までをも行わなくても、予測誤差の符号化効率が最も高くなる走査径路を選択することができる。従って、最適な走査径路の選択を高速に行うことができるので、画像の符号化演算速度を向上させることができる。
【発明を実施するための最良の形態】
【００３２】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【００３３】
（実施形態１）
図１は本発明の実施形態１に係る画像符号化装置のブロック図である。本実施形態に係る画像符号化装置１は、画像入力手段２から入力される画像データを符号化して、画像送信手段１２に出力するものである。画像入力手段２は、デジタル・カメラ、ビデオ、スキャナ等の画像入力機器により構成されている。また、画像送信手段１２は、通信回線等を通じて、符号化された画像を送信する装置である。
【００３４】
画像符号化装置１は、フレームメモリ３、小領域分割手段４、小領域メモリ５、走査予測演算ユニット６−０〜６−７、最適走査選択手段７、画像符号化手段８、符号メモリ９、走査情報符号化手段１０、及び走査情報メモリ１１を備えている。
【００３５】
フレームメモリ３は、画像入力手段２から入力される画像データを一時的に記憶する。小領域分割手段４は、フレームメモリ３に記憶された画像データを複数の小領域に分割し、小領域メモリ５に格納する。
【００３６】
走査予測演算手段６−０〜６−７は、小領域メモリ５に格納された各小領域の画像データについて、所定の走査径路に従って走査するとともに、走査径路上の各符号化画素の画素値を他の画素値から予測して予測誤差を算出し出力する。最適走査選択手段７は、走査予測演算ユニット６−０〜６−７のうち、それぞれが出力する予測誤差の符号化効率が最も高くなるものを選択する。尚、本実施形態においては、一例として、走査予測演算ユニットの数は８個とした。しかし、本発明においては走査予測演算ユニットの数はこれに限られるものではない。
【００３７】
画像符号化手段８は、最適走査選択手段７が選択した走査予測演算ユニット６−ｉ（ｉ∈｛０，…，７｝）が出力する予測誤差をエントロピ符号化により符号化し、符号メモリ９に格納する。また、走査情報符号化手段１０は、最適走査選択手段７が選択した走査予測演算ユニット６−ｉにおいて使用された走査径路を特定する識別番号を符号化し、走査情報メモリ１１に格納する。
【００３８】
画像送信手段１２は、符号メモリ９に格納された符号化された予測誤差（以下、「符号化画像」という。）と、走査情報メモリ１１に格納された符号化された走査径路の識別番号（以下、「符号化走査情報」という。）を送信する。
【００３９】
各走査予測演算ユニット６−０〜６−７は、走査径路メモリ１３、走査手段１４、参照画素メモリ１５、線形予測手段１６、予測誤差メモリ１７、ヒストグラム生成手段１８、及びエントロピ演算手段１９を備えている。
【００４０】
走査手段１４は、小領域メモリ５に格納された小領域内の画像データを、走査径路メモリ１３に格納された走査径路に沿って走査する。ここで、各走査予測演算ユニット６−０〜６−７の走査径路メモリ１３には、それぞれ異なる走査径路が格納されている。従って、各走査予測演算ユニット６−０〜６−７の走査手段１４は、それぞれが異なる走査経路に沿った小領域内の走査を行う。
【００４１】
尚、走査径路の形状としては、縦方向又は横方向のラスタ走査、斜め走査、渦巻き走査、Ｚ走査、ヒルベルト走査等の各種走査パターンが用いられる。
【００４２】
線形予測手段１６は、走査径路上の各走査点において、参照画素メモリ１５に格納された参照画素座標に対応する画素の画素値を小領域メモリ５から取得し、これらの参照画素値を用いて符号化画素値の予測値を求め、符号化画素値とその予測値との差である予測誤差を算出して、これを予測誤差メモリ１７に格納する。
【００４３】
ここで、参照画素メモリ１５には、各走査点に対応して、参照画素の座標がルックアップテーブルとして格納されている。参照画素は、符号化画素から所定の距離以内にある画素であって当該符号化画素よりも前に走査されている画素とされる。従って、参照画素の座標や数は、一般に、走査径路の形状や走査径路上の符号化座標の位置により異なる。
【００４４】
ヒストグラム生成手段１８は、予測誤差の分布表を保持しており、線形予測手段１６が出力する予測誤差によって、予測誤差の分布表を更新する。
【００４５】
エントロピ演算手段１９は、ヒストグラム生成手段１８が生成した小領域内の全画素についての予測誤差の分布表から、当該小領域の予測誤差のエントロピを算出する。
【００４６】
以上のように構成された本実施形態に係る画像符号化装置において、以下その動作を説明する。
図２は本発明の実施形態１に係る画像符号化方法の流れを表すフローチャートである。まず、画像入力手段２から、画像データが入力され、フレームメモリ３に格納される（Ｓ１）。画像データとしては、静止画像のような２次元画像のみならず、立体画像や動画像のように複数のフレームからなる３次元画像であってもよい。また、入力される画像は、白黒画像、カラー画像等を問わない。
【００４７】
次に、小領域分割手段４は、フレームメモリ３に格納された画像をＢｘ×Ｂｙ個の小領域に分割し、小領域メモリに格納する。ここで、小領域とは、画像データの走査を行う単位領域であり、小領域のサイズは自由に設定してもよい。小領域のサイズを小さくするほど、画像の局所的性質に応じた走査の最適化が図られるため符号化効率は向上する反面、小領域内の画素数Ｎの減少による符号への変換効率の減少により符号化効率が減少する。従って、小領域のサイズは、各種の画像において両者のバランスがほぼ最適化するように決められる。通常は、Ｎ＝１６×１６画素又は３２×３２画素程度とされる。尚、小領域の形状は、正方形に限られるものではなく、長方形や三角形等の形状としてもよい。
【００４８】
次に、分割された各小領域について、順次画像の符号化を行う。まず、ｋ＝０として（Ｓ３）、ｋ番目の小領域の符号化を行う。各走査予測演算ユニット６−０〜６−７の走査手段１４は、ｉ＝０として（Ｓ４−０，…，Ｓ４−７）、走査径路メモリ１３からｉ番目の走査点の座標を取得する。走査径路メモリ１３には、０番目からＮ−１番目までの走査径路座標が、ルックアップテーブルとして記憶されている。従って、走査手段１４は、このルックアップテーブルを参照することにより、走査点の座標を取得する。そして、走査手段１４は、取得した走査点の座標に対応するｋ番目の小領域内の画素の画素値を取得する（Ｓ５−０，…，Ｓ５−７）。
【００４９】
次に、線形予測手段１６は、参照画素メモリ１５から、ｉ番目の走査点の画素（符号化画素）の画素値の予測に使用するｓ個の参照画素の座標及び重み係数を取得する。続いて、取得した参照画素の座標に対応する画素の画素値を、小領域メモリ５から取得し、これらの参照画素値から符号化画素値の予測値を計算する。そして、符号化画素値とその予測値との差である予測誤差を算出し、予測誤差メモリ１７に格納する（Ｓ６−０，…，Ｓ６−７）。
【００５０】
ここで、符号化画素値の予測値の演算は、（数２）のような線型式によって算出される。
【００５１】
【数２】
2005039723.tif 000004
（数２）において、ｘｒｊはｊ番目の参照画素の画素値を表し、ｗｊはｊ番目の参照画素に対する重み係数を表し、重み係数の総和は１とされる。
【００５２】
【数３】
2005039723.tif 000005
【００５３】
尚、ここで各重み係数については、参照画素メモリ１５に記憶された重み係数をそのまま使用してもよい。また、他の方法として、ＡＬＣＭ（Activity Level Classification Model）予測器のように、予測値の演算時において随時更新するようにしてもよい。ＡＬＣＭにおける重み係数の更新規則は（数４）の通りである。
【００５４】
【数４】
2005039723.tif 000006
【００５５】
ＡＬＣＭ予測器は、ラスタ走査に対して用いられるものであるが、本実施形態においては走査径路はラスタ走査には限られない。しかしながら、上記（数４）は一般的な走査径路に対してもそのまま拡張することができる。
【００５６】
このように、符号化画素周辺の画素を用いて予測式の重み係数を適応的に変化させることで、予測誤差のエネルギー集中度を更に高めて符号化効率を上げることができる。
【００５７】
更に、予測誤差のエネルギー集中度を高めるために、上記（数４）の予測更新規則を修正して、（数５）の更新規則を用いて行いてもよい。（数５）の更新規則は、予測値と符号化画素値との差分に比例して、重み係数の制御幅を変化させる構成としたものである。
【００５８】
【数５】
2005039723.tif 000007
【００５９】
次に、ヒストグラム生成手段１８は、算出された予測誤差の値から予測誤差の分布表を更新する（Ｓ７−０，…，Ｓ７−７）。予測誤差の分布表は、各予測誤差の値に対してどの程度の頻度でその値が出現したかを表す表である。（表１）に予測誤差の分布表の例を示す。ヒストグラム生成手段１８は、算出された予測誤差の値を参照して、その値に対応する頻度値を１だけ増加させる。
【００６０】
【表１】
2005039723.tif 000008
【００６１】
以上のステップＳ５−ｐ〜Ｓ７−ｐ（ｐ∈｛０，…，７｝）の動作を、ｉの値を１ずつ増加させながら（Ｓ８−ｐ）、ｉがＮ−１となるまで繰り返し行う。ｉがＮ−１となったときに、小領域内の総ての画素についての走査と予測誤差の演算が終了する。
【００６２】
そして、次に、各走査予測演算ユニット６−０〜６−７のエントロピ演算手段１９は、予測誤差の分布表から、小領域における予測誤差のエントロピＨｐ（ｐ∈｛０，…，７｝）を（数５）により算出する（Ｓ９−０，…，Ｓ９−７）。
【００６３】
【数６】
2005039723.tif 000009
（数５）において、ｅは予測誤差値、ｎｅは予測誤差値ｅの発生頻度、Ｎは小領域内の全画素数、ｐｅは予測誤差値ｅの発生確率である。
【００６４】
ここで、各neの値に対する−pe log peの値を、予めルックアップテーブルとして用意しておく。ここで、ルックアップテーブルにおいては、ne=0に対しては０を対応させる。そして、上記各予測誤差ｅに対するエントロピ−pe log peの演算は、neの値からこのルックアップテーブルを参照して−pe log peの値を求める。これを総てのｅについて加算することで、エントロピＨｐが計算される。このように、ルックアップテーブルを用いてエントロピの演算を行うことで、ルックアップテーブルと加算器のみを使用してエントロピの演算を行うことができるため、高速演算が可能となる。
【００６５】
次に、最適走査選択手段７は、各走査予測演算ユニット６−０〜６−７が出力するエントロピＨ０〜Ｈ７のうち最小のものＨｊを求め、それに対応する走査径路Ｓｊを選択する（Ｓ１０）。
【００６６】
画像符号化手段８は、最適走査選択手段７により選択された走査径路Ｓｊによる走査で求められた予測誤差｛ei｝をエントロピ符号化により符号化し、符号メモリ９に格納する（Ｓ１１）。
【００６７】
そして、ｋの値をインクリメントして（Ｓ１２）、上記ステップＳ４〜Ｓ１１までの動作をｋがＢｘ×Ｂｙ−１となるまで繰り返す。これにより、総ての小領域について予測誤差の符号化が行われる。
【００６８】
最後に、走査情報符号化手段１０は、各小領域における走査径路の識別番号を符号化し、走査情報メモリ１１に格納する。そして、画像送信手段１２は、符号メモリに格納された符号化予測誤差と、走査情報メモリに格納された符号化走査識別番号とを送信する（Ｓ１４）。以上の動作により、入力画像が符号化され、送信が行われる。
【００６９】
尚、本実施形態においては、最適走査選択手段７は、各小領域ごとに、各走査径路に対してエントロピを計算し、エントロピが最小となる走査径路を選択する構成とした。しかし、これ以外に、最適走査選択手段７は、各小領域ごとに、各走査径路に対して予測誤差の絶対値和や二乗和を計算し、これらが最小となる走査径路を選択する構成としてもよい。更に、最適走査選択手段７は、各小領域ごとに、各走査径路に対して予測誤差データを実際に符号化し、符号量が最小となる走査径路を選択する構成としてもよい。
【００７０】
（表２）に、従来のＪＰＥＧ−ＬＳ方式により各種画像の圧縮を行った結果と、本実施形態に係る画像符号化装置を用いて画像の符号化を行った結果との比較を示す。（表２）において、方法１〜方法３は、本実施形態に係る画像符号化方法により符号化した結果を表す。
【００７１】
【表２】
2005039723.tif 000010
【００７２】
方法１は、最適走査選択手段７が、各小領域ごとに、各走査径路に対して予測誤差データを実際に符号化し符号量が最小となる走査径路を選択する方法により符号化した結果である。方法２は、最適走査選択手段７が、各小領域ごとに各走査径路に対して予測誤差の絶対値和を計算し、これらが最小となる走査径路を選択する方法により符号化した結果である。また、方法３は、最適走査選択手段７が、各走査径路に対してエントロピを計算し、エントロピが最小となる走査径路を選択する方法により符号化した結果である。方法１〜方法３において、小領域のサイズは１６×１６画素とした。また、符号化前の１画素の画素値は８ビットとし、（表２）は画像を符号化した後の１画素あたりの符号量を表している。
【００７３】
また、走査予測演算ユニットは２個とし、各走査予測演算ユニットにおける走査径路は横方向走査（通常のラスタ走査）と縦方向走査（ラスタ走査を縦方向に行ったもの）とした。
【００７４】
表２より、本発明に係る方法１〜方法３の画像符号化方法によれば、何れも従来のＪＰＥＧ−ＬＳによるものに比べて、平均０．２３〜０．１７ビット程度符号化効率が向上していることが分かる。また、計算時間は何れの方法においてもＪＰＥＧ−ＬＳとほぼ同等であった。
【００７５】
（実施形態２）
本実施形態においては、実施形態１で説明した画像符号化装置をハードウェアにより構成した例について説明する。
【００７６】
図３は図１の線形予測手段のブロック図である。本実施形態に係る画像符号化装置の線形予測手段１６は、減算器２１、加算器２２、遅延回路２３−０〜２３−（ｍ−１）、参照画素選択回路２４、積算器２５−０〜２５−（ｎ−１）、加算器２６、予測係数メモリ２７、及びアドレス生成回路２８を備えている。
【００７７】
走査手段１４から出力される符号化画素値x(i,j)は、減算器２１において、当該符号化画素値の予測値
【００７８】
【数７】
2005039723.tif 000011
が減算され、減算器２１は、予測誤差e(i,j)を出力する。この予測誤差e(i,j)は、予測誤差メモリ１７に格納されるとともに、加算器２２に出力される。加算器２２には、前記予測誤差e(i,j)と符号化画素値の予測値
【００７９】
【数８】
2005039723.tif 000012
が入力される。加算器２２は、両者を加算して再び符号化画素値x(i,j)を生成し、遅延回路２３−０に出力する。ｍ個の遅延回路２３−０〜２３−（ｍ−１）は、それぞれ入力されたデータを一時的に保持し、１画素ステップ分だけ遅延させて出力する。また、遅延回路２３−ｋ（ｋ＝０，１，…，ｍ−２）の出力は、遅延回路２３−（ｋ＋１）の入力に接続されている。
【００８０】
また、参照画素選択回路２４には、遅延回路２３−０〜２３−（ｍ−１）の出力と、参照画素メモリ１５の出力とが入力される。参照画素選択回路２４は、参照画素メモリ１５の出力データにより指定される遅延回路２３−０〜２３−（ｍ−１）の出力の幾つかを選択して出力する。この参照画素選択回路２４は、例えば、クロスバ・スイッチによって構成される。
【００８１】
尚、参照画素メモリ１５には、走査順序に従って、符号化画素の位置に対応して参照画素を遅延回路２３−０〜２３−（ｍ−１）の出力から選択するための選択情報がルックアップテーブルとして格納されている。
【００８２】
参照画素選択回路２４から出力されるｎビットの出力値は、それぞれ積算器２５−０〜２５−（ｎ−１）に出力される。また、各積算器２５−０〜２５−（ｎ−１）には、予測係数メモリ２７から出力される重み係数w0〜wn-1が入力される。積算器２５−ｋ（ｋ＝０，１，…，ｎ−１）は、参照画素選択回路２４からの出力値x(p,q)と重み係数wkとを積算し、その積算値を加算器２６に出力する。加算器２６は、各積算器２５−０〜２５−（ｎ−１）から入力される積算値を加算して、符号化画素値の予測値
【００８３】
【数９】
2005039723.tif 000013
として減算器２１及び加算器２２に出力する。
【００８４】
尚、予測係数メモリ２７には、走査順序に従って、符号化画素の位置に対応して各参照画素に対応する重み係数がルックアップテーブルとして格納されている。
【００８５】
このようにして、先行画素の画素値から符号化画素値の予測値
【００８６】
【数１０】
2005039723.tif 000014
が逐次計算され、予測誤差ｅ（ｉ，ｊ）が逐次計算され出力される。尚、走査手段１４が出力する符号化画素の走査径路上の位置と、参照画素メモリ１５が出力する参照画素の選択データ出力、及び予測係数メモリ２７が出力する各参照画素に対する重み係数の出力とを同期させるため、アドレス生成回路２８は、走査手段１４が走査を実行するクロックと同期して、予測係数メモリ２７及び参照画素メモリ１５の読み出しアドレスを変更する。これにより、走査順序に従って、予め用意されたルックアップテーブルに従って、参照画素及び重み係数が逐次切り換えられる。
【００８７】
以上のように、線形予測手段１６は、参照画素メモリ１５と参照画素選択回路２４を用いて、走査径路に合わせて自由に参照画素の選択を行うことを可能としたため、任意の走査径路に対応して、走査径路上の各画素に対応して参照画素の位置を自由に変更することが可能となる。
【００８８】
図４は図１のヒストグラム生成手段及びエントロピ演算手段のブロック図である。ヒストグラム生成手段１８は、１個のデマルチプレクサ３１、及びＮｅ個のカウンタ３２−０〜３２−（Ｎｅ−１）を備えた構成からなる。
【００８９】
デマルチプレクサ３１には、選択入力信号として予測誤差ｅ（ｉ，ｊ）が入力される。この選択信号の値によって、入力されるクロックｃｌｋが、カウンタ３２−０〜３２−（Ｎｅ−１）のうちの何れかに選択的に出力される。各カウンタ３２−０〜３２−（Ｎｅ−１）は、クロックｃｌｋの立ち上がりをカウントする。尚、走査手段１４は、クロックｃｌｋが１回立ち上がるのに同期して、１画素走査するものとする。
【００９０】
これにより、画像の小領域の総ての画素について、ヒストグラム生成手段１８に予測誤差を逐次入力することにより、カウンタ３２−０〜３２−（Ｎｅ−１）に、当該小領域の予測誤差値の分布データが蓄積される。小領域内の全画素数をＮ＝Ｂｘ×Ｂｙとすると、カウンタ３２−０〜３２−（Ｎｅ−１）のカウント値は０〜Ｎの範囲内の整数値をとる。
【００９１】
エントロピ演算手段１９は、マルチプレクサ３３、エントロピ演算回路３４、演算メモリ３５、加算器３６、エントロピ・レジスタ３７、及びエントロピ演算制御部３８を有する。マルチプレクサ３３には、カウンタ３２−０〜３２−（Ｎｅ−１）の値が入力されている。マルチプレクサ３３は、エントロピ演算制御部３８からの制御信号に従って、カウンタ３２−０〜３２−（Ｎｅ−１）の値を逐次一つずつ選択して出力する。ここでは、カウンタ３２−ｅの出力値をｎｅと置くと、ｎｅは０〜Ｎの間の値をとる。
【００９２】
エントロピ演算回路３４は、マルチプレクサ３３が出力するカウント値ｎｅに対応するエントロピの値ｈｅを、（数７）により算出する。但し、ｎｅ＝０の場合は、ｈｅ＝０とする。
【００９３】
【数１１】
2005039723.tif 000015
【００９４】
この演算は、ｎｅの値が０〜Ｎの間の値に限られているため、ルックアップテーブルを用いた参照演算によって行われる。すなわち、０〜Ｎまでの各ｎｅの値に対応するｈｅの値をルックアップテーブルとして予め演算メモリ３５に格納しておく。そして、エントロピ演算回路３４は、マルチプレクサ３３から入力されるｎｅの値に対応して、演算メモリ３５からｈｅの値を読み出して出力する。
【００９５】
加算器３６には、エントロピ演算回路３４の出力値ｈｅ、及びエントロピ・レジスタ３７から出力されるエントロピの加算値ｈ0＋…＋ｈe-1が入力される。加算器３６は、両者を加算した値ｈ0＋…＋ｈe-1＋ｈｅを、エントロピ・レジスタ３７に出力する。エントロピ・レジスタ３７は、加算器３６の出力値によって、記憶値を更新する。
【００９６】
エントロピ演算制御部３８は、ヒストグラム生成手段１８が１つの小領域の全画素について予測誤差値の分布データを蓄積し終わった時点で、マルチプレクサ３３により、カウンタ３２−０〜３２−（Ｎｅ−１）の値を逐次一つずつ読み出しながらエントロピを加算し、（数６）で表される小領域の予測誤差のエントロピＨpをエントロピ・レジスタ３７に蓄積する制御を行う。
【００９７】
エントロピ・レジスタ３７に最終的に蓄積された小領域の予測誤差のエントロピＨpは、最適走査選択手段７に出力される。
【００９８】
図５は図１の最適走査選択手段の構成を表すブロック図である。最適走査選択手段７は、最小エントロピ選択回路４０、及び予測誤差選択回路４１を備えている。最小エントロピ選択回路４０は、各走査予測演算ユニット６−０〜６−７のエントロピ演算手段１９が出力する小領域の予測誤差のエントロピＨ０〜Ｈ７のうち最小のものに対応する走査予測演算ユニットの番号a = (a2, a1, a0) = argmin(H0,H1,…,H7)を出力する。図５においては、最小エントロピ選択回路４０の出力値は（表３）のようになる。
【００９９】
【表３】
2005039723.tif 000016
【０１００】
予測誤差選択回路４１は、最小エントロピ選択回路４０が出力する走査予測演算ユニットの番号aに対応する走査ユニット６−ａの予測誤差メモリ１７に格納された予測誤差のデータを読み出して、画像符号化手段８に出力する。画像符号化手段８は、入力された予測誤差のデータを符号化する。これにより、符号化後の符号化予測誤差の符号量をほぼ最小化することが可能となる。
【０１０１】
また、最小エントロピ選択回路４０が出力する走査予測演算ユニットの番号aは走査情報符号化手段１０にも送られる。走査情報符号化手段１０は、各小領域について選択された走査予測演算ユニットの番号aを符号化して出力する。
【０１０２】
尚、本実施形態においては、線形予測手段１６の予測係数は、予測誤差の値によらず固定値としたが、例えば、図６に示したように、予測誤差の値を参照して、（数４）や（数５）等により重み係数の値を修正する係数変更回路４２を備えた構成としてもよい。
【図面の簡単な説明】
【０１０３】
【図１】本発明の実施形態１に係る画像符号化装置のブロック図である。
【図２】本発明の実施形態１に係る画像符号化方法の流れを表すフローチャートである。
【図３】図１の線形予測手段のブロック図である。
【図４】図１のヒストグラム生成手段及びエントロピ演算手段のブロック図である。
【図５】図１の最適走査選択手段の構成を表すブロック図である。
【図６】図１の線形予測手段の他の例を示すブロック図である。
【符号の説明】
【０１０４】
１    画像符号化装置
２    画像入力手段
３    フレームメモリ
４    小領域分割手段
５    小領域メモリ
６−０〜６−７    走査予測演算ユニット
７    最適走査選択手段
８    画像符号化手段
９    符号メモリ
１０    走査情報符号化手段
１１    走査情報メモリ
１２    画像送信手段
１３    走査径路メモリ
１４    走査手段
１５    参照画素メモリ
１６    線形予測手段
１７    予測誤差メモリ
１８    ヒストグラム生成手段
１９    エントロピ演算手段
２１    減算器
２２    加算器
２３−０〜２３−（ｍ−１）    遅延回路
２４    参照画素選択回路
２５−０〜２５−（ｎ−１）    積算器
２６    加算器
２７    予測係数メモリ
２８    アドレス生成回路
３１    デマルチプレクサ
３２−０〜３２−（Ｎｅ−１）    カウンタ
３３    マルチプレクサ
３４    エントロピ演算回路
３５    演算メモリ
３６    加算器
３７    エントロピ・レジスタ
３８    エントロピ演算制御部
４０    最小エントロピ選択回路
４１    予測誤差選択回路
４２    係数変更回路
【図１】
2005039723.tif 000017
【図２】
2005039723.tif 000018
【図３】
2005039723.tif 000019
【図４】
2005039723.tif 000020
【図５】
2005039723.tif 000021
【図６】
2005039723.tif 000022