(57)【要約】【課題】混成画像を視覚的な歪みが少なく、高速な符号化処理を実現することが可能な画像符号化技術を提供する。【解決手段】符号化する原画像を所定の走査順序に従って走査する走査手段７と、走査手段７が原画像を走査して生成する１次元原画像を、各区間内の画素値の累積二乗誤差又は分散が所定の閾値以下となるように複数の区間に区分し、各区間内の画素値を当該区間内における画素値の平均値により近似した１次元近似画像データを生成する区分線型近似手段９と、を有する走査ユニット３を、異なる複数の走査順序に対応して複数個備え、各走査ユニット３の区分線型近似手段９が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択する最適走査選択手段４とを備えた。【選択図】        図１
2004312693.tif 000002
【特許請求の範囲】
【請求項１】
符号化する原画像を所定の走査順序に従って走査する走査手段と、
前記走査手段が原画像を走査して生成する１次元原画像を、各区間内の画素値の累積二乗誤差又は分散が所定の閾値以下となるように複数の区間に区分し、各区間内の画素値を当該区間内における画素値の平均値により近似した１次元近似画像データを生成する区分線型近似手段と、
を有する走査ユニットを、異なる複数の走査順序に対応して複数個備え、
各走査ユニットの前記区分線型近似手段が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択する最適走査選択手段と、
を備えていることを特徴とする画像符号化装置。
【請求項２】
前記区分線型近似手段は、前記１次元原画像を区分するに際し、
１次元原画像を２区間に区分したときに、両区間における画素値の累積二乗誤差又は分散の和が最小となるような区分位置で前記１次元原画像を区分する２分割処理を行うとともに、
前記２分割処理により２分された両区間について、当該区間における画素値の累積二乗誤差又は分散が所定の閾値以上の場合には、当該区間において前記２分割処理を再帰的に行うことにより、前記１次元原画像を区分すること
を特徴とする請求項１記載の画像符号化装置。
【請求項３】
前記１次元原画像を複数の小区間に分割する小区間分割手段を備え、
前記区分線型近似手段は、前記小区間分割手段が分割した各小区間の１次元原画像に対して、前記１次元近似画像データを生成すること
を特徴とする請求項１又は２記載の画像符号化装置。
【請求項４】
前記区分線型近似手段が生成する前記各小区間の１次元近似画像データについて、隣接する２つの小区間における相対する最端部の区間の画素値の平均値の差が所定の閾値以下であり、かつ、一方の区間の長さが所定の閾値以下の場合、当該両区間の近似値を当該両区間全体の画素値の平均値で置き換える併合処理手段
を備えていることを特徴とする請求項３記載の画像符号化装置。
【請求項５】
前記最適走査選択手段は、前記各走査ユニットの前記区分線型近似手段のうちの所定の数のものが１次元近似画像データの生成処理を終了した時点で、まだ１次元近似画像データの生成処理の終了していない区分線型近似手段については当該処理を打ち切らせるとともに、当該処理の終了した前記走査ユニットの前記区分線型近似手段が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択すること
を特徴とする請求項１乃至４の何れか一に記載の画像符号化装置。
【請求項６】
前記最適走査選択手段は、
前記各走査ユニットの前記区分線型近似手段のうちの１つが１次元近似画像データの生成処理を終了した時点からクロックのカウントを開始し、所定の時間内に１次元近似画像データの生成処理の終了していない区分線型近似手段については当該処理を打ち切らせるとともに、前記所定の時間内に当該処理の終了した前記走査ユニットの前記区分線型近似手段が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択すること
を特徴とする請求項１乃至４の何れか一に記載の画像符号化装置。
【請求項７】
前記最適走査選択手段は、
前記各走査ユニットの前記区分線型近似手段のうちの１つが１次元近似画像データの生成処理を終了した場合、その１次元近似画像データの区間数を基準区間数として他の前記走査ユニットに対して送信し、
各走査ユニットの区分線型近似手段は、前記基準区間数を受信した場合、１次元原画像を区分した区間数が前記基準区間数に所定の値を加えた数を超えたときに１次元近似画像データの生成処理を打ち切るとともに、
前記最適走査選択手段は、前記１次元近似画像データの生成処理の終了した前記走査ユニットの前記区分線型近似手段が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択すること
を特徴とする請求項１乃至４の何れか一に記載の画像符号化装置。
【請求項８】
符号化する原画像に対し直交変換を行い変換画像を生成する直交変換手段と、
前記変換画像を適応ビット配分により量子化し、量子化変換画像を生成する量子化手段と、
前記量子化変換画像を所定の径路で走査するとともに、走査径路に沿って同値の画素が連続するラン長、及びそのランに対する画素値の組からなるラン・データを生成するラン・データ生成手段と、
を有する直交変換ユニットを、少なくとも１つ備え、
前記最適走査選択手段は、各走査ユニットの前記区分線型近似手段が区分した区間数、及び直交変換ユニットのランデータ生成手段が生成したランの数（以下、「ラン数」という。）を比較して、区間数又はラン数が最小の１次元近似画像データ又はラン・データを選択することを特徴とする請求項１乃至７の何れか一に記載の画像符号化装置。
【請求項９】
符号化する原画像を所定の走査順序に従って走査して生成される１次元原画像を、各区間内の画素値の累積二乗誤差又は分散が所定の閾値以下となるように複数の区間に区分し、各区間内の画素値を当該区間内における画素値の平均値により近似した１次元近似画像データを生成する区分線型近似処理を、異なる複数の走査順序に対応してそれぞれ並行して行う第１のステップ、
前記各走査順序について区分線型近似処理により得られた各１次元近似画像データの区間数を比較して、区間数が最小の１次元近似画像データを選択する第２のステップ、
及び、選択された１次元近似画像データを符号化する第３のステップ
を有することを特徴とする画像符号化方法。
【請求項１０】
前記区分線型近似処理においては、前記１次元原画像を区分するに際し、１次元原画像を２区間に区分したときに、両区間における画素値の累積二乗誤差又は分散の和が最小となるような区分位置で前記１次元原画像を区分する２分割処理を行うとともに、前記２分割処理により２分された両区間について、当該区間における画素値の累積二乗誤差又は分散が所定の閾値以上の場合には、当該区間において前記２分割処理を再帰的に行うことにより、前記１次元原画像を区分することを特徴とする請求項９記載の画像符号化方法。
【請求項１１】
前記第１のステップにおいて、符号化する原画像に対し直交変換を行い変換画像を生成し、前記変換画像を適応ビット配分により量子化して量子化変換画像を生成し、前記量子化変換画像を所定の径路で走査するとともに、走査径路に沿って同値の画素が連続するラン長、及びそのランに対する画素値の組からなるラン・データを生成する走査を並行して行い、
前記第２のステップにおいては、前記各走査順序について区分線型近似処理により得られた各１次元近似画像データの区間数、及び前記ランデータのランの数（以下、「ラン数」という。）を比較して、区間数又はラン数が最小の１次元近似画像データを選択し、
前記第３のステップにおいては、選択された１次元近似画像データ又はラン・データを符号化することを特徴とする請求項９又は１０記載の画像符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の圧縮や伝送等に使用される画像符号化技術に係り、特に、人工画像と自然画像とが混在した混成画像を最適に符号化することが可能な画像符号化技術に関する。
【背景技術】
【０００２】
写真のような自然画像と文字、図形、イラスト等の人工画像とが混在する画像を混成画像という。混成画像を、非可逆圧縮する技術としては、従来、JPEG、GIF、TIFF等の各種の符号化方式が広く用いられている。
【０００３】
一方、符号化の対象となる原画像は、自然画像であるか人工画像であるかにより、画像内のパターンの性質が異なる。自然画像では画素間の相関が大きく、画素値変化が連続的であるという性質を有する。一方、人工画像は、一般に、画素値が連続して同じ区間が多く存在すると共に、鋭いエッジも多く存在するという性質を有する。このような画像の属性に基づくパターンの性質の違いから、上記従来の画像符号化方式では、あらゆる混成画像を最適に符号化することは困難である。
【０００４】
例えば、混成画像をJPEGにより符号化した場合、人工画像部分の文字や図形の輪郭にモスキートノイズが発生し、視覚的に大きな劣化を生じる。これは、JPEGは、離散コサイン変換（discrete cosine transformation : 以下、「DCT」という。）により低域にスペクトルを集中させ、高帯域情報を削除するために生じる。一方、GIFやTIFFなどの方式は、人工画像の圧縮には適しているものの、自然画像の符号化効率がJPEGに比べて低い。
【０００５】
そこで、このような混成画像の符号化を最適に行う技術として、混成画像を、人工画像を主体とする離散階調領域と、自然画像を主体とする連続階調領域との２つの領域に分離し、各領域の特性に基づいて、それぞれ、ランレングス符号化とJPEGを用いて符号化する技術が提案されている（非特許文献１参照）。
【非特許文献１】茂木健，“領域分離に基づく自然人工混在画像の圧縮”，社団法人電気情報通信学会，電子情報通信学会論文誌Ｄ−ＩＩ，Vol.J82-D-II，No.7, p.1150-1160, 1999年7月
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、混成画像を、人工画像を主体とする離散階調領域と、自然画像を主体とする連続階調領域との２つの領域に分離する画像符号化方式では、画像の領域分割の演算における計算量が多くなる。そのため、高速画像圧縮には適していない。
【０００７】
また、ハードウェア的に並列処理を行えば、高速化も可能である。しかし、この場合、回路規模が極めて大きくなる。
【０００８】
そこで、本発明の目的は、混成画像を視覚的な歪みが少なく、高速な符号化処理を実現することが可能であり、ハードウェアで並列処理する構成とした場合であっても小規模な回路で実現可能な画像符号化技術を提供することにある。
【課題を解決するための手段】
【０００９】
本発明の画像符号化装置の第１の構成は、符号化する原画像を所定の走査順序に従って走査する走査手段と、前記走査手段が原画像を走査して生成する１次元原画像を、各区間内の画素値の累積二乗誤差又は分散が所定の閾値以下となるように複数の区間に区分し、各区間内の画素値を当該区間内における画素値の平均値により近似した１次元近似画像データを生成する区分線型近似手段と、を有する走査ユニットを、異なる複数の走査順序に対応して複数個備え、各走査ユニットの前記区分線型近似手段が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択する最適走査選択手段と、を備えていることを特徴とする。
【００１０】
この構成によれば、各走査ユニットは、１次元原画像を、各区間内の画素値の累積二乗誤差又は分散が所定の閾値以下となるように複数の区間に区分する。そして、各区間内の画素値を当該区間内における画素値の平均値により近似した（以下、この近似を「区分線型近似」という。）１次元近似画像データを生成する。最適走査選択手段は、各走査ユニットの前記区分線型近似手段が区分した区間数を比較する。そして、区間数が最小の１次元近似画像データを選択する。このように、最適走査選択手段は、画像を符号化する前段階において、符号化後に符号量が最小となる走査順序を、区分線型近似手段が区分した区間数が最小となる走査順序と推定する。そして、これを最適な走査順序として選定する。最適な走査順序により走査されて区分線型近似により得られる１次元近似画像データは、その後、ランレングス符号化等により符号化すれば、原画像の最適な符号化が行われることとなる。
【００１１】
上記区分線型近似の区間数を指標とした操作順序の選択を行えば、文書画像やグラフィック画像等の人工画像のようにエッジ以外の画素値の変化が少ない画像、自然画像のように隣接する画素値の変化が多い画像などの画像の属性に応じて符号化に最適な走査順序が選択される。そのため、画像の性質に適応した走査順序による原画像の１次元化がなされる。また、本発明では、符号化のための原画像の近似に区分線型近似を使用し、完全な符号化を行う前に、区分線型近似における区間数に基づいて最適な走査順序を選定する。これにより、高速な符号化処理が可能となる。
【００１２】
また、本発明では、操作順序の選定を、区分線型近似を行って得られる１次元近似画像データの区間数の比較を用いて行う。これにより、アルゴリズムが簡単であり、ハードウェアにより並列処理を行う構成とした場合でも、小規模な回路構成によって実現することができる。
【００１３】
本発明の画像符号化装置の第２の構成は、前記第１の構成において、前記区分線型近似手段は、前記１次元原画像を区分するに際し、１次元原画像を２区間に区分したときに、両区間における画素値の累積二乗誤差又は分散の和が最小となるような区分位置で前記１次元原画像を区分する２分割処理を行うとともに、前記２分割処理により２分された両区間について、当該区間における画素値の累積二乗誤差又は分散が所定の閾値以上の場合には、当該区間において前記２分割処理を再帰的に行うことにより、前記１次元原画像を区分することを特徴とする。
【００１４】
このように、本発明では、区分線型近似手段が上記２分割処理を再帰的に実行し、１次原画像を小区間に分割する構成とした。これにより、区間分割の際に、画像のエッジ部分が分割位置として保存される。従って、人工画像のように画像のエッジが強調される画像を符号化する際でも、符号化による画像の視覚的な歪みを最小限に抑えることができる。
【００１５】
本発明の画像符号化装置の第３の構成は、前記第１又は２の構成において、前記１次元原画像を複数の小区間に分割する小区間分割手段を備え、前記区分線型近似手段は、前記小区間分割手段が分割した各小区間の１次元原画像に対して、前記１次元近似画像データを生成することを特徴とする。
【００１６】
このように、小区間分割手段により１次元原画像を小区間に区分して、区分線型近似手段が各小区間について区分線型近似を行うことで、区分線型近似手段が行う計算量が少なくなる。従って、符号化処理を高速化することができる。特に、区分線型近似に再帰処理を用いる場合には、小区間への区分により計算量を大幅に減少させることができる。
【００１７】
本発明の画像符号化装置の第４の構成は、前記第３の構成において、前記区分線型近似手段が生成する前記各小区間の１次元近似画像データについて、隣接する２つの小区間における相対する最端部の区間の画素値の平均値の差が所定の閾値以下であり、かつ、一方の区間の長さが所定の閾値以下の場合、当該両区間の近似値を当該両区間全体の画素値の平均値で置き換える併合処理手段を備えていることを特徴とする。
【００１８】
このように、本発明では、併合手段により、隣接する２つの小区間における相対する最端部の区間を、一定の条件のもとで併合する。これにより、無駄な区間分割を減らし、１次元近似画像データ全体での区間数を減少させることができる。従って、符号化効率が向上する。
【００１９】
ここで、２つの区間を併合する条件として、両区間の画素値の平均値の差が所定の閾値以下であるとしたのは、両区間の画素値の平均値の差が大きい場合には、併合による近似誤差の増加が大きくなるからである。
【００２０】
また、２つの区間を併合する条件として、一方の区間の長さが所定の閾値以下としたのは、短い区間であれば、区間の併合によりエッジ情報が失われたとしても、視覚的に目立たず、事実上無視できる程度の歪みしか生じないからである。
【００２１】
本発明の画像符号化装置の第５の構成は、前記第１乃至４の何れか一の構成において、前記最適走査選択手段は、前記各走査ユニットの前記区分線型近似手段のうちの所定の数のものが１次元近似画像データの生成処理を終了した時点で、まだ１次元近似画像データの生成処理の終了していない区分線型近似手段については当該処理を打ち切らせるとともに、当該処理の終了した前記走査ユニットの前記区分線型近似手段が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択することを特徴とする。
【００２２】
区分線型近似手段の区分線型近似処理の時間は、一般に、区分される区間数が多いほど増加する。従って、１次元近似画像データの生成処理が早く終了した走査ユニットの区間数が最小である可能性が大きい。従って、所定の数の走査ユニットの区分線型近似処理が終了した時点で、残りの走査ユニットについては、区分線型近似処理を打ち切ってもよい。このように、残りの走査ユニットについて区分線型近似処理を打ち切ることで、最適走査選択手段の処理を早く終了させ、高速化することが可能となる。
【００２３】
本発明の画像符号化装置の第６の構成は、前記第１乃至４の何れか一の構成において、前記最適走査選択手段は、前記各走査ユニットの前記区分線型近似手段のうちの１つが１次元近似画像データの生成処理を終了した時点からクロックのカウントを開始し、所定の時間内に１次元近似画像データの生成処理の終了していない区分線型近似手段については当該処理を打ち切らせるとともに、前記所定の時間内に当該処理の終了した前記走査ユニットの前記区分線型近似手段が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択することを特徴とする。
【００２４】
各走査ユニットの前記区分線型近似手段のうちの１つが１次元近似画像データの生成処理を終了した時点から、所定の時間内に１次元近似画像データの生成処理の終了しない走査ユニットの区間数は、最先に区分線型近似処理が終了した走査ユニットにおける１次元近似画像データの区間数に比べて、大きいと考えられる。従って、このような処理時間のかかる走査ユニットについては、所定の時間で区分線型近似処理を打ち切ることで、走査順序の最適な選択ができ、かつ、符号化処理時間を短縮することができる。
【００２５】
本発明の画像符号化装置の第７の構成は、前記第１乃至４の何れか一の構成において、前記最適走査選択手段は、前記各走査ユニットの前記区分線型近似手段のうちの１つが１次元近似画像データの生成処理を終了した場合、その１次元近似画像データの区間数を基準区間数として他の前記走査ユニットに対して送信し、各走査ユニットの区分線型近似手段は、前記基準区間数を受信した場合、１次元原画像を区分した区間数が前記基準区間数に所定の値を加えた数を超えたときに１次元近似画像データの生成処理を打ち切るとともに、前記最適走査選択手段は、前記１次元近似画像データの生成処理の終了した前記走査ユニットの前記区分線型近似手段が区分した区間数を比較して、区間数が最小の１次元近似画像データを選択することを特徴とする。
【００２６】
このように、基準区間数に所定の数を加えた区間数を超えた場合には、その後併合処理等を行っても基準区間数を下回る可能性は少ない。従って、このような区間数が多くなった走査ユニットについては、区間数が所定の数まで達した時点で区分線型近似処理を打ち切ることで、走査順序の最適な選択ができ、かつ、符号化処理時間を短縮することができる。
【００２７】
本発明の画像符号化装置の第７の構成は、前記第１乃至７の何れか一の構成において、符号化する原画像に対し直交変換を行い変換画像を生成する直交変換手段と、前記変換画像を適応ビット配分により量子化し、量子化変換画像を生成する量子化手段と、前記量子化変換画像を所定の径路で走査するとともに、走査径路に沿って同値の画素が連続するラン長、及びそのランに対する画素値の組からなるラン・データを生成するラン・データ生成手段と、を有する直交変換ユニットを、少なくとも１つ備え、前記最適走査選択手段は、各走査ユニットの前記区分線型近似手段が区分した区間数、及び直交変換ユニットのラン・データ生成手段が生成したランの数（以下、「ラン数」という。）を比較して、区間数又はラン数が最小の１次元近似画像データ又はラン・データを選択することを特徴とする。
【００２８】
この構成によれば、自然画像のように直交変換による圧縮率がよい画像に対しては、直交変換ユニットが出力するラン数が、各走査ユニットが出力する区間数よりも少なくなる。従って、最適走査選択手段は、ラン数が最小のラン・データを選択する。このようにして、画像の性質により適応して１次元近似画像データ又はラン・データが選択され、より最適な符号化が図られる。その結果、符号化効率はより向上する。
【００２９】
尚、「適応ビット配分」とは、通常の画像において、画素信号の電力が集中する低周波数側の画素に対しては多くのビット数を割り当てて量子化し、画素信号の電力が小さい高周波成分に対しては少ないビット数で量子化することをいう。この適応ビット配分は、変換符号化において広く使用されている方法である。
【００３０】
本発明の画像符号化方法の第１の構成は、符号化する原画像を所定の走査順序に従って走査して生成される１次元原画像を、各区間内の画素値の累積二乗誤差又は分散が所定の閾値以下となるように複数の区間に区分し、各区間内の画素値を当該区間内における画素値の平均値により近似した１次元近似画像データを生成する区分線型近似処理を、異なる複数の走査順序に対応してそれぞれ並行して行う第１のステップ、前記各走査順序について区分線型近似処理により得られた各１次元近似画像データの区間数を比較して、区間数が最小の１次元近似画像データを選択する第２のステップ、及び選択された１次元近似画像データを符号化する第３のステップを有することを特徴とする。
【００３１】
本発明の画像符号化方法の第２の構成は、前記第１の構成において、前記区分線型近似処理においては、前記１次元原画像を区分するに際し、１次元原画像を２区間に区分したときに、両区間における画素値の累積二乗誤差又は分散の和が最小となるような区分位置で前記１次元原画像を区分する２分割処理を行うとともに、前記２分割処理により２分された両区間について、当該区間における画素値の累積二乗誤差又は分散が所定の閾値以上の場合には、当該区間において前記２分割処理を再帰的に行うことにより、前記１次元原画像を区分することを特徴とする。
【００３２】
本発明の画像符号化方法の第３の構成は、前記第１又は２の構成において、前記第１のステップにおいて、符号化する原画像に対し直交変換を行い変換画像を生成し、前記変換画像を適応ビット配分により量子化して量子化変換画像を生成し、前記量子化変換画像を所定の径路で走査するとともに、走査径路に沿って同値の画素が連続するラン長、及びそのランに対する画素値の組からなるラン・データを生成する走査を並行して行い、前記第２のステップにおいては、前記各走査順序について区分線型近似処理により得られた各１次元近似画像データの区間数、及び前記ラン・データのランの数（以下、「ラン数」という。）を比較して、区間数又はラン数が最小の１次元近似画像データを選択し、前記第３のステップにおいては、選択された１次元近似画像データ又はラン・データを符号化することを特徴とする。
【発明の効果】
【００３３】
以上のように、本発明によれば、区分線型近似の区間数を指標とした操作順序の選択を行うことにより、文書画像やグラフィック画像等の人工画像のようにエッジ以外の画素値の変化が少ない画像、自然画像のように隣接する画素値の変化が多い画像などの画像の属性に応じて符号化に最適な走査順序が選択される。そのため、画像の性質に適応した走査順序による原画像の１次元化がなされる。
【００３４】
また、符号化のための原画像の近似に区分線型近似を使用し、完全な符号化を行う前に、区分線型近似における区間数に基づいて最適な走査順序を選定することとしたことにより、高速な符号化処理が可能となる。
【発明を実施するための最良の形態】
【００３５】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００３６】
図１は本発明の実施例１に係る画像符号化装置の全体構成図である。図１において、本発明の実施例１に係る画像符号化装置は、画像入力手段１、画像領域分割手段２、ｎ個（ｎ≧２）の走査ユニット３-１〜３-ｎ、最適走査選択手段４、符号化手段５、及び画像圧縮データ出力手段６を有している。
【００３７】
画像入力手段１は、画像入力装置に原画像のデータを入力するものである。画像入力手段１としては、ＣＣＤ素子等の撮像素子や、テレビ受像器、磁気ディスク装置等の画像記憶装置等が用いられる。画像領域分割手段２は、画像入力手段１から入力される画像を、複数の小領域（画像ブロック）に分割する。各走査ユニット３−ｉ（ｉ＝１，…，ｎ）は、それぞれに決められた所定の走査順序により、画像領域分割手段２が分割した各画像ブロックを走査するとともに、区分線型近似処理を行い、１次元近似画像データを生成する。
【００３８】
最適走査選択手段４は、各走査ユニット３−ｉ（ｉ＝１，…，ｎ）の生成する１次元近似画像データの区間数を比較して、最小の区間数の１次元近似画像データを選択する。符号化手段５は、最適走査選択手段４が選択した１次元近似画像データを各種符号化方式に従って符号化し、符号化画像を出力する。画像圧縮データ出力手段６は、符号化手段５が生成した符号化画像を出力する。画像圧縮データ出力手段６としては、画像送信機や画像記憶装置等が用いられる。
【００３９】
図２は図１の各走査ユニット３−ｉ（ｉ＝１，…，ｎ）の構成を表すブロック図である。走査ユニット３−ｉ（ｉ＝１，…，ｎ）は、走査手段７、小区間分割手段８、区分線型近似手段９、及び併合処理手段１０により構成されている。
【００４０】
走査手段７は、画像領域分割手段２が分割した各画像ブロックを、それぞれに決められた走査順序に従って走査し、１次元原画像を生成する。この走査手段７は、画像領域メモリ７ａと走査アドレス生成器７ｂとからなる。画像領域メモリ７ａには、各メモリアドレスに画像ブロック内の画素値が走査順序に従って記憶される。走査アドレス生成器７ｂは、各走査ユニット３−ｉ（ｉ＝１，…，ｎ）のそれぞれに対して決められた走査順序に従って、画像ブロック内の走査座標を生成する。画像領域メモリ７ａは、画像ブロックから当該走査座標における画素値を取得することにより画像ブロックの走査を行う。
【００４１】
小区間分割手段８は、走査手段７が生成した１次元原画像を、更に複数の小区間に分割する（以下、この各小区間内の原画像データを、「小区間データ」という）。区分線型近似手段９は、小区間分割手段８が生成した小区間データを、区分線型近似により近似した小区間近似画像を生成する。併合処理手段１０は、区分線型近似手段９が生成した小区間１次元近似画像データを所定の方法で併合し、１次元近似画像データを生成する。そして、この１次元近似画像データは、最適走査選択手段４に出力される。
【００４２】
図３は図２の区分線型近似手段９の構成を表すブロック図である。区分線型近似手段９は、小区間メモリ１１、区間レジスタ１２、区間分割処理部１３、分割処理制御部１４、及び小区間近似画像メモリ１５により構成されている。
【００４３】
小区間メモリ１１は、小区間分割手段８が分割した小区間データを記憶する。区間レジスタ１２は、小区間メモリ１１に記憶された画素値のデータのうち、区分線型近似を行う対象となる区間のデータ（以下、「被処理区間データ」という。）を記憶する。区間分割処理部１３は、区間レジスタ１２に記憶された被処理区間データに対して区間分割処理を行う。ここで、「区間分割処理」とは、被処理区間データを２つの区間に分割したときに、両区間の画素値の累積二乗誤差の和が最小となる位置で、被処理区間データを分割するとともに、各分割区間のデータを当該区間における画素値の平均値で近似する処理をいう。
【００４４】
分割処理制御部１４は、区間分割処理部１３により、小区間メモリ１１に記憶された小区間データについて再帰的に区間分割処理を行う。そして、分割処理制御部１４は、分割された小区間データの各区間における画素値の累積二乗誤差が、それぞれ所定の閾値以下となるように、再帰的に区間分割処理を行い、１次元近似画像データを生成する。小区間近似画像メモリ１５は、分割処理制御部１４により生成された１次元近似画像データを記憶する。
【００４５】
図４は図３の区間分割処理部１３の構成を表すブロック図である。図４において、区間分割処理部１３は、アドレス生成部２１、自乗算器２２、自乗加算アキュミュレータ２３、加算アキュミュレータ２４、自乗算器２５、アップカウンタ２６、除算器２７、減算器２８、除算器２９、減算アキュミュレータ３０、自乗減算アキュミュレータ３１、自乗算器３２、ダウンカウンタ３３、除算器３４、減算器３５、除算器３６、加算器３７、比較判定部３８、最小累積誤差メモリ３９、区分線型近似終了判定部４０、左誤差レジスタ４１、右誤差レジスタ４２、左レベルレジスタ４３、左区間長レジスタ４４、右レベルレジスタ４５、及び右区間長レジスタ４６を備えている。各部の機能については、後述の動作説明と併せて説明する。
【００４６】
図５は図２の併合処理手段１０の構成を表すブロック図である。図５において、併合処理手段１０は、併合処理判定部５１、併合データ生成部５２、及び併合区間レジスタ５３を有している。
【００４７】
併合処理判定部５１は、小区間近似画像メモリ１５に記憶された各小区間データについて、隣接する２つの小区間における相対する最端部の区間の画素値の平均値の差が所定の閾値以下であり、かつ、一方の区間の長さが所定の閾値以下であるかどうかの判定を行う。また、併合データ生成部５２は、小区間近似画像メモリ１５に記憶された各小区間データについて、隣接する２つの小区間における相対する最端部の区間の近似値を当該両区間全体の画素値の平均値で置き換える処理を行う。併合区間レジスタ５３は、併合処理が行われた後の小区間データを一時的に記憶する。
【００４８】
併合処理判定部５１は、第１のレベル差判定部６１、第２のレベル差判定部６２、境界前区間長判定部６３、境界後区間長判定部６４、及び併合処理総合判定部６５を備えている。また、併合データ生成部５２は、２つの乗算器６６，６７、２つの加算器６８，６９、及び除算器７０を備えている。これら各部の機能については、後述の動作説明と併せて説明する。
【００４９】
図６は図１の最適走査選択手段４の構成を表すブロック図である。図６において、最適走査選択手段４は、最適走査判定部８１、及び最適走査セレクタ８２を備えている。
【００５０】
最適走査判定部８１は、各走査ユニット３−ｉ（ｉ＝１，…，ｎ）の区分線型近似手段９が区分し併合処理手段により併合処理がされた１次元近似画像データのうち、最も区間数の少ないものを判定し、その走査ユニットの番号（以下、「最適走査番号」という。）ｍを出力する。最適走査セレクタ８２は、最適走査番号ｍの走査ユニット３−ｍが出力する１次元近似画像データを選択し、符号化手段５に出力する。
【００５１】
図７は図１の符号化手段５の構成を表すブロック図である。図７において、符号化手段５は、走査情報符号化部９１、輝度情報符号化部９２、区間長情報符号化部９３、及び符号化情報合成部９４を備えている。
【００５２】
走査情報符号化部９１は、最適走査選択手段４が出力する最適走査番号ｍを、走査の頻度に基づくハフマン符号等を用いたエントロピー符号化により符号化を行う。輝度情報符号化部９２は、最適走査選択手段４が出力する１次元近似画像データのうちの各区間の輝度情報について、輝度レベルの差分値のハフマン符号等を用いたエントロピー符号化により符号化を行う。区間長情報符号化部９３は、最適走査選択手段４が出力する１次元近似画像データのうちの各区間の区間長情報について、ワイル符号等を用いたエントロピー符号化による符号化を行う。
【００５３】
以上のように構成された本実施例の画像符号化装置について、以下その画像符号化方法について説明する。図８は実施例１における画像符号化方法の処理全体の流れを表すフローチャートである。
【００５４】
本実施例における画像符号化装置が原画像の符号化を行う場合、まず、画像入力手段１に、原画像のデータが入力される（Ｓ１）。原画像が入力されると、次に、画像領域分割手段２は、原画像をＭｂ個（Ｍｂ＞１）の画像ブロックに分割する（Ｓ２）。画像の分割が終了すると、画像領域分割手段２は、符号化対象となる画像ブロックの番号を表すパラメータｉに１を設定する（Ｓ３）。
【００５５】
次に、画像領域分割手段２は、各走査ユニット３−１〜３−ｎに対して、走査開始指示を出力する（Ｓ４）。これにより、各走査ユニット３−１〜３−ｎは、画像ブロックの走査と区分線型近似処理を開始する。
【００５６】
各走査ユニット３−１〜３−ｎは、区分線型近似処理が終了すると、最適走査選択手段４に対して処理終了信号を送信する。最適走査選択手段４は、総ての走査ユニット３−１〜３−ｎより処理終了信号が送信されるまで待機する（Ｓ５）。
【００５７】
ここで、区分線型近似処理においては、走査手段７によって走査され１次元化された１次元原画像データは、区分線型近似手段９により、複数の区間に分割され、各区間の画素値が当該区間内の画素値の平均値で近似される。このとき、区間の分割の仕方は、各区間内における画素値の累積二乗誤差が所定の閾値σth2以下となるように分割される。従って、各走査ユニット３−k（k=1,…,n）により生成される１次元近似画像データは、｛（ｃｉ(k)，ｌｉ(k)）；i=１，…，Nsection(k)｝（但し、ｃｉ(k)は区間ｉ内の画素の平均値、ｌｉ(k)は区間ｉの区間長、Nsection(k)は、全区間数。）のようなデータとなる。
【００５８】
また、各走査ユニット３−１〜３−ｎは、それぞれが異なる走査順序により画像ブロックを走査する。走査順序としては、例えば、図９に示したような、ラスタ走査、ジグザグ走査、渦巻き走査、ヒルベルト走査等の各種の走査順序を用いることができる。
【００５９】
総ての走査ユニット３−１〜３−ｎより処理終了信号が送信されると、最適走査選択手段４は、各走査ユニット３−１〜３−ｎが生成した１次元近似画像データの区間数Nsection(k)（k=1,…,n）を比較し（Ｓ６）、区間数が最も少ない１次元近似画像データ｛（ｃｉ(m)，ｌｉ(m)）；i=１，…，Nsection(m)｝（m=argmink Nk）を選択する（Ｓ７）。区間数Nsection(k)が少ないほど、１次元近似画像データの符号量が少ないため、符号化効率がよいからである。
【００６０】
このように、画像を符号化する前段階において、区分線型近似処理により得られる１次元近似画像データの区間数Nsection(k)（k=1,…,n）により、符号化後の符号量を推定し、符号量が最小となると推定される１次元近似画像データを選択することで、短い処理時間で、画像の属性に最も適合した走査順序を選択することが可能となる。また、区分線型近似処理は、後述するように、画像のエッジを区間の分割点とする傾向が強いため、画像のエッジが鋭いほど、１次元近似画像データにおいて画像のエッジがよく保存される。従って、人工画像のように、鋭いエッジを有する画像においては、画像のエッジにおける視覚的な歪みを最小限に抑えることが可能となる。
【００６１】
次に、符号化手段５は、選択された１次元近似画像データ（走査順序に関する情報も含む。）をハフマン符号化方式やランレングス符号化方式等の通常の手法により符号化する（Ｓ８）。そして、符号化されたｉ番目の画像ブロックのデータは、画像圧縮データ出力手段６により出力される（Ｓ９）。
【００６２】
そして、画像符号化装置は、パラメータｉの値を１だけインクリメントして、ｉがＭｂ以下である間（Ｓ１１）、上記ステップＳ４〜Ｓ１０までの動作を繰り返し行い、総ての画像ブロックについての符号化処理を行う。
【００６３】
最後に、ステップＳ１１において、パラメータｉがＭｂより大きくなったときに、画像符号化処理を終了する。
【００６４】
以上が本実施例における画像符号化方法の全体的な処理の流れであるが、以下、画像符号化装置の各部の動作について、より詳細に説明する。
図１０は走査ユニット３−ｋ（ｋ＝１，…，ｎ）のデータ処理を表すフローチャート、図１１は画像ブロック内の走査順序の一例を示す図、図１２は画像領域メモリ７ａの内容を表す図、図１３は走査アドレス生成器７ｂ内のメモリの内容を表す図である。図１１〜図１３では、画像ブロックの大きさは、ｐ×ｑ画素としてある。尚、図９では走査の例として正方形領域の走査を示しているが、これらの正方形領域の走査を組み合わせて又は変形して長方形領域の走査に拡張することは容易である。
【００６５】
走査ユニット３−ｋは、画像領域分割手段２より走査開始指示を受信すると、まず、走査手段７が、画像ブロックの走査を行い、１次元原画像を生成する（Ｓ２１）。
【００６６】
このとき、画像領域メモリ７ａには、図１２のような順序で原画像の画素値が格納されている。また、走査アドレス生成器７ｂは、走査順序を格納するメモリを有している。走査ユニット３−ｋが、図１１のようなジグザグ走査を行う場合、走査アドレス生成器７ｂ内のメモリには、アドレスの小さい順に、図１１のようなジグザグ走査の順序に従って画像領域メモリ７ａの対応するアドレスが格納されている。そして、走査アドレス生成器７ｂは、クロックに従って、画像領域メモリのアドレスを、走査順序に沿って順次出力する。画像領域メモリ７ａは、走査アドレス生成器７ｂから入力されるアドレスに格納された画素データを出力する。これにより、所定の走査順序で走査された１次元原画像が生成される。
【００６７】
次に、小区間分割手段８は、１次元原画像を、Ｍ個（Ｍ＞１）の小区間に等分し、小区間データを生成する（Ｓ２２）。この小区間分割は、後述の再帰的な区間分割処理を少ない演算回数で行うためにされる。各小区間データは、区分線型近似手段９の内部の小区間メモリ１１に一旦格納される。
【００６８】
次に、区分線型近似手段９は、内部変数として有するカウンタｉを１に設定する（Ｓ２３）。このカウンタｉは、区分線型近似処理を行う小区間データの番号を表すものである。
【００６９】
次に、区分線型近似手段９は、ｉ番目の小区間ｌの小区間データを区間レジスタ１２に設定する（Ｓ２５）。そして、区間分割処理部１３及び分割処理制御部１４は、ｉ番目の小区間データについて区分線型近似処理を行う（Ｓ２６〜Ｓ２８）。この区分線型近似処理は、（数１）のような再帰アルゴリズムによって行われる。
【００７０】
【数１】
2004312693.tif 000003
【００７１】
ここで、区間分割処理とは、区間lを２つに分割した際に、左右の区間内における画素値の累積二乗誤差が最小となる分割位置で、区間lを２つの区間ll，lrに分割する処理をいう。この区間分割処理の詳細については後述する。
【００７２】
（数１）の２行目で、区間lについて区間分割処理を行うことによって、分割された２つの区間ll，lrと、各区間における画素値の累積二乗誤差el,min，er,min及び各区間における画素値の平均cl,crが求まる。尚、（数１）では、cl,crについては直接関係ないので省略している。
【００７３】
（数１）の３〜５行目では、分割された左側の区間llにおいて、当該区間内における画素値の累積二乗誤差el,minが所定の閾値ethよりも大きい場合には、区間llについて、再帰的に区分線型近似処理を行う。一方、累積二乗誤差el,minが所定の閾値eth以下であれば、区間llについては、区分線型近似処理は行わない。
【００７４】
（数１）の６〜８行目では、分割された右側の区間lrにおいても同様に、当該区間内における画素値の累積二乗誤差er,minが所定の閾値ethよりも大きい場合には、区間lrについて、再帰的に区分線型近似処理を行い、累積二乗誤差er,minが所定の閾値eth以下であれば、区間lrについては、区分線型近似処理は行わない。
【００７５】
以上のような区分線型近似処理により、ｉ番目の小区間データは、更にf(i)個の区間からなる小区間１次元近似画像データに分割される。そして、各区間における画素値の累積二乗誤差は、所定の閾値eth以下に抑えられる。従って、区間内に画像の鋭いエッジを含むと、当該区間内の累積二乗誤差が所定の閾値eth以下には抑えられないため、エッジ部分において分割され、区間内には画像の鋭いエッジは含まれないように分割がされる。すなわち、上記区分線型近似処理により、画像のエッジは区間の境界として保存されることになる。
【００７６】
尚、上記区間分割処理については、区間分割処理部１３が行い、上述のような再帰的な処理の制御については、分割処理制御部１４が行う。また、区分線型近似処理により近似値が確定した区間については、その区間長と画素値の平均値が、小区間近似画像メモリ１５に蓄えられる。
【００７７】
ｉ番目の小区間データについての区分線型近似処理が終わると、区分線型近似手段９は、カウンタｉの値を１だけインクリメントする（Ｓ２９）。そして、ｉの値がＭよりも大きくなければ（Ｓ３０）、再び、上記ステップＳ２５〜Ｓ２９の処理を繰り返す。
【００７８】
一方、ステップＳ３０において、i>Mであった場合、区分線型近似手段９は、最適走査選択手段４に対して処理終了信号を送信する（Ｓ３１）。そして、各小区間の最端部の区間についての併合処理を行って（Ｓ３２）、走査ユニット３−ｋはデータ処理を終了する。
【００７９】
次に、区間分割処理について補足説明をする。図１４は図３，図４の区間分割処理部１３による区間分割処理を表すフローチャート、図１５は図１４の各ノードにおける演算出力を表す図である。
【００８０】
最初に、区間レジスタ１２に区間長がＮの被処理区間データ｛ｘｉ；i=1，…，N｝が設定されると、自乗加算アキュミュレータ２３及び加算アキュミュレータ２４にクリア信号が入力され、両アキュミュレータの累算値は０にクリアされる。また、アップカウンタ２６もリセットされる。そして、アドレス生成部２１は、１クロックごとに、区間レジスタ１２に対して入力するアドレス値を、昇順に１ずつ増加させる。それに伴い、区間レジスタ１２の出力であるノード(1)には、クロック値ｉ（１≦ｉ≦Ｎ）に対して画素値ｘｉが出力される。
【００８１】
自乗算器２２は、ノード(1)から入力される画素値xiを自乗した値xi2を、ノード(2)に出力する。自乗加算アキュミュレータ２３は、１クロックごとに、ノード(2)の出力値を累算する。従って、クロック値がｉ（１≦ｉ≦Ｎ）のときには、自乗加算アキュミュレータ２３には累算値としてΣk=1i xk2が記憶される。
【００８２】
同様に、加算アキュミュレータ２４は、１クロックごとに、ノード(1)の出力値を累算する。従って、クロック値がｉ（１≦ｉ≦Ｎ）のときには、加算アキュミュレータ２４には累算値としてΣk=1i xkが記憶される。
【００８３】
アップカウンタ２６は、クロック数をカウントし、クロック値がｉ（１≦ｉ≦Ｎ）のときには、ノード(6)にはｉが出力される。
【００８４】
クロック値ｉが１からＮまで変化した時点で、加算アキュミュレータ２４には（数２）のＳr,1値が記憶され、自乗加算アキュミュレータ２３には、（数３）のＳr,2値が記憶されている。また、アップカウンタ２６のカウント値はＮとなる。
【００８５】
【数２】
2004312693.tif 000004
【００８６】
【数３】
2004312693.tif 000005
【００８７】
そして、クロック値がＮ＋１となった時点で、加算アキュミュレータ２４，自乗加算アキュミュレータ２３の値は、それぞれ、減算アキュミュレータ３０及び自乗減算アキュミュレータ３１に設定される。すなわち、クロック値Ｎ＋１において、減算アキュミュレータ３０，自乗減算アキュミュレータ３１には、（数２）、（数３）で示したＳr,1，Ｓr,2の値が設定され、これらの値がノード(10)、(9)に出力される（Ｓ４１）。
【００８８】
それと同時に、加算アキュミュレータ２４，自乗加算アキュミュレータ２３にはクリア信号が入力され、両アキュミュレータの累積値は再び０にクリアされる。また、ダウンカウンタ３３には、アップカウンタ２６のカウント値Ｎが設定され、これがノード(12)に出力される。アップカウンタ２６は再びリセットされる。また、アドレス生成部２１の発生するアドレス値もリセットされる（Ｓ４２）。このとき、初期値として、左区間長レジスタ４４の値は０、右区間長レジスタ４６の値はＮ、最小累積誤差メモリ３９には（数４）の値が設定される。
【００８９】
【数４】
2004312693.tif 000006
【００９０】
更に、クロック値がＮ＋１から１ずつ増加していくと、アドレス生成部２１は、１クロックごとに、区間レジスタ１２に対して入力するアドレス値を、昇順に１ずつ増加させる。それに伴い、区間レジスタ１２の出力であるノード(1)には、クロック値がN＋N1＋1(1≦N1≦N-1)のとき、画素値xN1が出力される。そして、ノード(2)、(3)、(4)、(6)には、それぞれ、xN12, Sl,2=Σk=1N1 xk2, Sl,1=Σk=1N1 xk ,N1が出力される。また、自乗加算器２５は、ノード(4)の出力値を自乗した値Sl,12= (Σk=1N1 xk)2をノード(5)に出力する。更に、除算器２７は、ノード(5)の出力値をノード(6)の出力値で除算した値Sl,12/N1を出力する。除算器２９は、ノード(4)の出力値をノード(6)の出力値で除算した値Sl,1/N1をノード(16)に出力する。これは、長さN1の左側区間の画素値の平均値である。減算器２８は、ノード(3)の出力値からノード(7)の出力値を減算した値（数５）をノード(8)に出力する。
【００９１】
【数５】
2004312693.tif 000007
【００９２】
また、自乗減算アキュミュレータ３１は、１クロックごとに、設定されている値からノード(2)の出力値を減算し、ノード(9)に出力する。従って、クロック値がN＋N1＋1(1≦N1≦N-1)のとき、ノード(9)には、Sr,2=Σk=N1+1N xk2が出力される。減算アキュミュレータ３０は、１クロックごとに、設定されている値からノード(1)の出力値を減算し、ノード(10)に出力する。従って、クロック値がN＋N1＋1(1≦N1≦N-1)のとき、ノード(10)には、Sr,1=Σk=N1+1N xkが出力される。自乗算器３２は、ノード(10)の出力値を自乗した値Sr,12をノード(11)に出力する。一方、クロック値がＮ＋１から１ずつ増加していくと、ダウンカウンタ３３は、設定値Ｎからクロックごとに１ずつ値を減少させていく。従って、クロック値がN＋N1＋1(1≦N1≦N-1)のとき、ノード(12)には、N-N1が出力される。除算器３４は、ノード(11)の出力値をノード(12)の出力値で除算した値Sr,12/(N-N1)をノード(13)に出力する（Ｓ４４）。減算器３５は、ノード(9)の値からノード(13)の値を減算した値（数６）をノード(14)に出力する。
【００９３】
【数６】
2004312693.tif 000008
【００９４】
また、除算器３６は、ノード(10)の出力値をノード(12)の出力値で除算した値Sr,1/(N-N1)をノード(17)に出力する。これは、長さN-N1の右側区間の画素値の平均値である。
【００９５】
加算器３７は、ノード(8)の出力値とノード(14)の出力値とを加算した値（数７）をノード(15)に出力する（Ｓ４５）。これは、左右の区間の累積二乗誤差の和となっている。
【００９６】
【数７】
2004312693.tif 000009
【００９７】
比較判定部３８は、ノード(15)の出力値eと、最小累積誤差メモリ３９に記憶された判定値eminを比較する（Ｓ４６）。そして、e<eminの場合には、比較判定部３８は最小累積誤差メモリに記憶された判定値eminの値をノード(15)の出力値eに更新する。それと同時に、比較判定部３８は、左誤差レジスタ４１、右誤差レジスタ４２、左レベルレジスタ４３、右レベルレジスタ４５、左区間長レジスタ４４、及び右区間長レジスタ４６のそれぞれを一時的に書き込み状態とする。これにより、左誤差レジスタ４１及び右誤差レジスタ４２には、それぞれ、ノード(8)、ノード(14)の出力値el,min, er,minが取り込まれて記憶される。また、左レベルレジスタ４３及び右レベルレジスタ４５には、左及び右の区間の画素値の平均値（数８）、（数９）が取り込まれて記憶される。
【００９８】
【数８】
2004312693.tif 000010
【００９９】
【数９】
2004312693.tif 000011
【０１００】
また、左区間長レジスタ４４及び右区間長レジスタ４６には、それぞれ、ノード(6)、ノード(12)の出力値ll=N1, lr=N-N1が取り込まれ、記憶される（Ｓ４７）。
【０１０１】
そして、次のクロックでアップカウンタ２６のカウンタ値N1が１だけ増加する（Ｓ４８）。区分線型近似終了判定部４０は、カウンタ値N1がN−1を超えたか否かを判定し（Ｓ４９）、このカウンタ値がN−1を超えるまで上記Ｓ４３〜Ｓ４８の動作を繰り返す。
【０１０２】
これにより、分割点を被処理区間データの左から右に移動させながら、両分割区間の累積二乗誤差の和が最小となる分割点が総当たり検索される。そして、この総当たり検索が終了した時点で、左誤差レジスタ４１、右誤差レジスタ４２、左レベルレジスタ４３、右レベルレジスタ４５、左区間長レジスタ４４、及び右区間長レジスタ４６には、両分割区間の累積二乗誤差の和が最小となる分割点における左右区間の累積二乗誤差値el,min,er,min、画素値の平均値cl,cr、及び区間の長さll,lrが保持される。
【０１０３】
従って、上記処理が終了した時点で、区間分割処理部１３は、分割処理制御部１４に対して、これらのレジスタに保持された値を出力して（Ｓ５０）、動作を終了する。
【０１０４】
最後に、併合処理手段の併合処理について補足説明をしておく。図１６は併合処理手段による併合処理の動作を表すフローチャート、図１７は小区間近似画像メモリ１５の内容を表す図である。
【０１０５】
この併合処理は、区分線型近似処理における再帰処理の際の演算量を削減するために小区間分割手段８により小区間データに分割され、区分線型近似処理により生成されたM個の小区間１次元近似画像データを、再び結合させた際に、各結合境界における区間のレベル差及び区間長によって、所定の条件で両区間を結合させる処理である。この処理を行うことで、更に符号量を削減して符号化効率の向上が図られる。
【０１０６】
まず、前提として、画像ブロックのM個の小区間データについての区分線型近似処理が終了し、小区間近似画像メモリ１５にM個の小区間１次元近似画像データが図１７のように格納されている。併合処理では、ｉ番目（ｉ＝1，…，N-1）の小区間内の最終区間（f(i)番目の区間）とｉ＋１番目の小区間内の最初の区間（１番目の区間）との併合処理を行う。
【０１０７】
併合処理においては、まず、併合処理手段１０は、ｉ＝１として（Ｓ６０）、小区間近似画像メモリ１５から、ｉ番目（ｉ＝1，…，N-1）の小区間内の最終区間（f(i)番目の区間）の画素値ci,f(i)及び区間長li,f(i)とｉ＋１番目の小区間内の最初の区間（１番目の区間）の画素値ci+1,1及び区間長li+1,1とを読み出す（Ｓ６１）。
【０１０８】
そして、併合処理判定部５１の第１のレベル差判定部６１は、画素値ci,f(i)とci+1,1が同一であるか否かを判定し（Ｓ６２）、同一であればノード(1)に１を出力し、同一でなければノード(1)に０を出力する。
【０１０９】
また、第２のレベル差判定部６２は、画素値ci,f(i)とci+1,1との差の絶対値が所定の閾値Δcth以下であるかどうかを判定し（Ｓ６３）、|ci,f(i)−ci+1,1|≦Δcthの場合には１をノード(2)に出力し、|ci,f(i)−ci+1,1|＞Δcthの場合には０をノード(2)に出力する。
【０１１０】
また、境界前区間長判定部６３は、区間長li,f(i)が所定の閾値lth1以下であるかどうかを判定し、境界後区間長判定部６４は、区間長li+1,1が所定の閾値lth2以下であるかどうかを判定する（Ｓ６４）。そして、境界前区間長判定部６３、境界後区間長判定部６４は、それぞれ、li,f(i)≦lth1、li+1,1≦lth2のときには１をノード(3)、(4)に出力し、li,f(i)＞lth1、li+1,1＞lth2のときには０をノード(3)、(4)に出力する。
【０１１１】
併合処理総合判定部６５は、上記ノード(1)〜(4)に出力される論理値について、(1)∨（(2)∧（(3)∨(4)））の論理演算を行い、その演算結果をノード(5)に出力する。すなわち、ノード(5)の値が１のときは、両区間は併合処理すると判断され、ノード(5)の値が０のときは、両区間は併合されないと判断される。
【０１１２】
ここで、上記判断方法について補足説明をしておく。まず、両区間の画素値ci,f(i)，ci+1,1が等しいときには、両区間を併合することについては特に問題はない。ci,f(i)，ci+1,1が等しくない場合であって、両区間の画素値ci,f(i)，ci+1,1の差の絶対値|ci,f(i)−ci+1,1|が大きい場合には、画像のエッジである可能性があるため、両区間は併合すべきではない。これを、閾値Δcthで判定している。
【０１１３】
一方、両区間の画素値ci,f(i)，ci+1,1の差の絶対値|ci,f(i)−ci+1,1|が小さい場合であっても、どちらの区間長も長い場合、併合により両区間の近似誤差累積二乗誤差が大きくなると、視覚的に強く認識されるようになる。そこで、絶対値|ci,f(i)−ci+1,1|が小さい場合であっても、両区間長が長い場合には区間の併合は行わない。これを閾値lth1、lth2で判断している。
【０１１４】
以上の結果、ノード(5)の出力値に１が出力された場合、併合データ生成部５２による両区間の併合処理が行われる（Ｓ６５）。併合データ生成部５２の乗算器６６は、ci,f(i)とli,f(i)との積を演算し、ノード(6)に出力する。乗算器６７は、ci+1,1とli+1,1との積を演算し、ノード(7)に出力する。加算器６８は、ノード(6)の出力値とノード(7)の出力値とを加算して、ノード(8)に出力する。加算器６９は、li,f(i)とli+1,1とを加算してノード(9)に（数１０）を出力する。
【０１１５】
【数１０】
2004312693.tif 000012
【０１１６】
更に、除算器７０は、ノード(8)の出力値をノード(9)の出力値により乗算して、ノード(10)に（数１１）を出力する。
【０１１７】
【数１１】
2004312693.tif 000013
【０１１８】
併合区間レジスタには、このようにして求められた、両区間の区間長の和l'i+1,1と両区間の画素値の平均値c'i+1,1が格納される。そして、併合処理総合判定部６５によりノード(5)に１が出力された場合には、小区間近似画像メモリ１５のｉ＋１番目の小区間データの最初の区間の値（ci+1,1，li+1,1）を、（c'i+1,1，l'i+1,1）で更新する。また、小区間近似画像メモリ１５のｉ番目の小区間データの最後の区間の値（ci,f(i)，li,f(i)）は、（0，0）で更新され、無効処理がされる。
【０１１９】
尚、本実施例では、区分線型近似処理において、区間の分割を行うか否かの評価基準として累積二乗誤差を使用したが、累積二乗誤差以外にも分散値を使用することも可能である。
【実施例２】
【０１２０】
実施例１においては、図８のステップＳ５において、最適走査選択手段４は、総ての走査ユニット３−１〜３−ｎより処理終了信号が送信されるまで待機することとしたが、このように一律に総ての走査ユニット３−１〜３−ｎの処理を待つと、処理時間が区分線型近似処理に最も時間を要する走査順序による走査で決まってしまい、処理速度が遅くなる。一方、区分線型近似処理に要する時間は、当該処理により分割される区間数が多いほど長くなる。
【０１２１】
そこで、本実施例においては、図８のステップＳ５においては、所定の数n1の走査ユニットの区分線型近似処理が終了した時点で、まだ区分線型近似処理が終了していない走査ユニットの区分線型近似処理を打ち切ることを特徴とする。
【０１２２】
図１８は実施例２に係る画像符号化装置の最適走査選択手段４’を表すブロック図、図１９は実施例２に係る画像符号化方法を表すフローチャート、図２０は実施例２に係る画像符号化装置の操作ユニットの動作を表すフローチャートである。
【０１２３】
本実施例の最適走査選択手段４’は、処理打切判定部１０１を備えていることを特徴とする。尚、他の構成については実施例１で説明したものと同様であるため、説明は割愛する。
【０１２４】
処理打切判定部１０１は、図１９に示したように、各走査ユニット３−１〜３−ｎから出力される処理終了信号の数をカウントし、出力された処理終了信号の数が、所定の閾値n1を超えた時点で（Ｓ７１）、処理打切信号を出力する（Ｓ７２）。また、最適走査判定部８１は、処理打切判定部１０１が、処理打切信号を出力した時点で、既に処理終了信号を出力している操作ユニットの中から、最小区間数の１次元近似画像データを選択する（Ｓ７３）。それ以外の動作については、実施例１の場合と同様である。
【０１２５】
一方、各走査ユニット３−１〜３−ｎの区分線型近似手段９は、図２０に示したように、処理打切信号を受信した場合であって、まだ区分線型近似処理が終了していない場合には、区分線型近似処理を強制的に終了する（Ｓ７５）。
【０１２６】
このように、総ての走査ユニット３−１〜３−ｎが区分線型近似処理を終了するまで待つことなく、先着n1個の走査ユニットの区分線型近似処理が終了した時点で、符号化処理に移行することで、符号化効率を下げることなく画像符号化処理の高速化を図ることが可能となる。
【０１２７】
尚、本実施例においては、処理打切判定部１０１は、先着n1個の走査ユニットの区分線型近似処理が終了した時点で、処理打切信号を出力することとしたが、他の方法として、最初に処理終了信号を受信してから所定の時間が経過した時点で、処理終了信号を出力するように構成することも可能である。
【０１２８】
図２１は実施例２に係る他の画像符号化方法を表すフローチャートである。処理打切判定部１０１は、何れかの走査ユニットから処理終了信号が出力されると（Ｓ８１）、内部に有するカウンタtを０にリセットし（Ｓ８２）、カウントを開始する（Ｓ８３）。そして、カウント値tが所定の閾値tmaxを超えた時点で（Ｓ８４）、処理打切信号を出力する（Ｓ７２）。後の動作は、上記説明したものと同様である。
【０１２９】
区分線型近似処理は、再帰処理により区間分割が多く行われるほど時間がかかる。従って、最初に処理終了信号が出力されてから所定の時間tmax以上が経過してもなお区分線型近似処理が終了しない走査ユニットについては、最初に区分線型近似処理を終了した走査ユニットが出力する１次元近似画像データの区間数を下回ることはないと考えてもよい。従って、カウント値ｔが所定の閾値tmaxを超えた時点で未終了の区分線型近似処理を強制的に打ち切ることで、符号化効率を低下させることなく、処理の高速化を図ることが可能となる。
【実施例３】
【０１３０】
本実施例では、何れかの走査ユニット３−ｓが区分線型近似処理を終了し、生成された１次元近似画像データの区間数l(s)が確定すると、他の各走査ユニットはその確定した区間数l(s)又は区間数l(s)に所定の値を加えた数l(s)+Δlを基準区間数lstとして、各時点での自己の区間数liが基準区間数lst以上となったときに区分線型近似処理を強制的に打ち切ることを特徴とする。
【０１３１】
図２２は実施例３に係る画像符号化装置の最適走査選択手段４”を表すブロック図、図２３は実施例３に係る画像符号化方法を表すフローチャート、図２４は実施例３に係る画像符号化装置の操作ユニットの動作を表すフローチャートである。
【０１３２】
本実施例の最適走査選択手段４”は、基準区間数通知部１１１を備えていることを特徴とする。尚、他の構成については実施例１で説明したものと同様であるため、説明は割愛する。
【０１３３】
最適走査選択手段４”は、何れかの走査ユニット３−ｓが処理終了信号を出力すると（Ｓ９１）、区分線型近似処理が終了した当該走査ユニット３−ｓの区間数l(s)を取り込む（Ｓ９２）。そして、各走査ユニット３−１〜３−ｎに対して、区間数l(s)又は区間数l(s)に所定の値を加えた数l(s)+Δlを基準区間数lstとして通知する（Ｓ９３）。尚、ここで区間数l(s)に所定の値を加えた数l(s)+Δlを基準とする場合もあり得るとしたのは、上記併合処理により、最終的な区間数はl(i)以下となることから、その分を見越して余裕を持たせることもできるようにしたものである。
【０１３４】
まだ区分線型近似処理が終了していない各走査ユニット３−ｉは、基準区間数lstが入力されると（Ｓ１０１）、区分線型近似処理において区間分割処理（Ｓ２６）を行う前に、現在の区間数lが基準区間数lst以上であるかどうかの判断をする（Ｓ１０２）。l<lstならば、実施例１と同様、区間分割処理を再帰的に繰り返す（Ｓ２６〜Ｓ２８）。一方、ステップＳ１０１でl≧lstとなった場合、最適走査選択手段４”に対して処理中断信号を出力して（Ｓ１０３）、強制的に区分線型近似処理を中断する。
【０１３５】
最適走査選択手段４”は、総ての走査ユニット３−１〜３−ｎが、処理終了信号又は処理中断信号を出力するのを待って（Ｓ９４）、処理終了信号を出力した各走査ユニットの１次元近似画像データの区間数を比較する（Ｓ９５）。そして、その中から最も区間数の少ない１次元近似画像を選択する（Ｓ７）。
尚、上記以外の処理は、実施例１と同様である。
【０１３６】
このように、各走査ユニットにおいて、区分線型近似処理の途中で、基準区間数以上となったときに区分線型近似処理を強制的に打ち切ることによっても、符号化効率を落とすことなく処理の高速化を図ることが可能である。
【実施例４】
【０１３７】
図２５は本発明の実施例４に係る画像符号化装置の全体構成図である。図２５において、画像入力手段１、画像領域分割手段２、走査ユニット３−１〜３−ｎ、最適走査選択手段４、符号化手段５、画像圧縮データ出力手段６、走査手段７、小区間分割手段８、区分線型近似手段９、及び併合処理手段１０は、実施例１の図１と同様のものである。
【０１３８】
本実施例においては、走査ユニット３−１〜３−ｎと並列にｍ個の直交変換ユニット１２０−１〜１２０−ｍを備えたことを特徴としている。この直交変換操作ユニット１２０−１〜１２０−ｍは、直交変換手段１２１、量子化手段１２２、及びラン・データ生成手段１２３を備えている。
【０１３９】
直交変換手段１２１は、画像領域分割手段２から入力される画像ブロックを、それぞれ決められた方法で直交変換し、変換画像を生成する。直交変換としては、DCT、離散サイン変換（discrete sine transformation : DST）、離散フーリエ変換、アダマール変換、カルーネン・レーベ変換（ＫＬ変換）、ハール変換、スラント変換等、種々の変換を使用することが可能である。
【０１４０】
量子化手段１２２は、直交変換手段１２１が出力する変換画像を、適応ビット配分により量子化する。この量子化された変換画像を、量子化変換画像という。これにより、スペクトルが集中する低域成分に対しては、多くのビットにより量子化が行われる。逆に、スペクトル集中度が低い高域成分に対しては、少ビット数での量子化が行われる。
【０１４１】
ラン・データ生成手段１２３は、量子化変換画像を走査する。走査は、低域側から高域側にかけて、ジグザクな径路で行われる。この操作方法に関しては、変換符号化においては広く使用されているので、ここではこれ以上は説明しない。ラン・データ生成手段１２３は、上記走査を行うと共に、走査径路に沿って、同値の画素が連続するラン長、及びそのランの画素値の組からなるラン・データを生成する。このラン・データは、最適走査選択手段４に対して出力される。
【０１４２】
以上のように構成された本実施例に係る画像符号化装置について、以下その動作を説明する。
【０１４３】
まず、画像入力手段１に画像が入力されて、画像領域分割手段２が画像ブロックを出力するまでは、実施例１と同様である。また、各画像ブロックは、走査ユニット３−１〜３−ｎに入力され、走査ユニット３−１〜３−ｎが１次元近似画像データを出力する動作も、実施例１と同様である。
【０１４４】
本実施例においては、画像領域分割手段２は、各画像ブロックを各直交変換ユニット１２０−１〜１２０−ｍに対しても出力する。直交変換ユニット１２０−１〜１２０−ｍにおいては、上述のように、直交変換手段１２１が変換画像を生成し、量子化手段が量子化変換画像を生成する。そして、ラン・データ生成手段１２３が、ラン・データを生成し、最適走査選択手段４に出力する。尚、変換画像において、低域側にスペクトルが集中している場合には、高域側のラン長は長くなる。従って、ラン数は少なくなる。逆に、スペクトルの集中度が低い場合には、高域側のランは短く、ラン数は多くなる。
【０１４５】
最適走査選択手段４は、各走査ユニット３−１〜３−ｎが出力する１次元近似画像データの区間数、及び各直交変換ユニット１２０−１〜１２０−ｍが出力するラン・データのラン数を比較する。そして、最小の区間数又はラン数の１次元近似画像データ又はラン・データを選択する。そして、符号化手段５は、選択された１次元近似画像データ又はラン・データを符号化する。以下は、実施例１と同様である。
【０１４６】
このように、本実施例では、走査ユニットにより生成される１次元近似画像データに加えて、直交変換ユニットが生成するラン・データをそれぞれ対比して、最も符号量が少なくなる変換方法を選択する。これにより、画像の性質に応じて最適な変換方法が選択され、高い符号化効率で画像の符号化を行うことが可能となる。
【図面の簡単な説明】
【０１４７】
【図１】本発明の実施例１に係る画像符号化装置の全体構成図である。
【図２】図１の各走査ユニット３−ｉ（ｉ＝１，…，ｎ）の構成を表すブロック図である。
【図３】図２の区分線型近似手段９の構成を表すブロック図である。
【図４】図３の区間分割処理部１３の構成を表すブロック図である。
【図５】図２の併合処理手段１０の構成を表すブロック図である。
【図６】図１の最適走査選択手段４の構成を表すブロック図である。
【図７】図１の符号化手段５の構成を表すブロック図である。
【図８】実施例１における画像符号化方法の処理全体の流れを表すフローチャートである。
【図９】各走査ユニットの走査順序の例を表す図である。
【図１０】走査ユニット３−ｋ（ｋ＝１，…，ｎ）のデータ処理を表すフローチャートである。
【図１１】画像ブロック内の走査順序の一例を示す図である。
【図１２】画像領域メモリ７ａの内容を表す図である。
【図１３】走査アドレス生成器７ｂ内のメモリの内容を表す図である。
【図１４】図３，図４の区間分割処理部１３による区間分割処理を表すフローチャートである。
【図１５】図１４の各ノードにおける演算出力を表す図である。
【図１６】併合処理手段による併合処理の動作を表すフローチャートである。
【図１７】小区間近似画像メモリ１５の内容を表す図である。
【図１８】実施例２に係る画像符号化装置の最適走査選択手段４’を表すブロック図である。
【図１９】実施例２に係る画像符号化方法を表すフローチャートである。
【図２０】実施例２に係る画像符号化装置の操作ユニットの動作を表すフローチャートである。
【図２１】実施例２に係る他の画像符号化方法を表すフローチャートである。
【図２２】実施例３に係る画像符号化装置の最適走査選択手段４”を表すブロック図である。
【図２３】図２３は実施例３に係る画像符号化方法を表すフローチャートである。
【図２４】実施例３に係る画像符号化装置の操作ユニットの動作を表すフローチャートである。
【図２５】本発明の実施例４に係る画像符号化装置の全体構成図である。
【符号の説明】
【０１４８】
１  画像入力手段
２  画像領域分割手段
３−１〜３−ｎ  走査ユニット
４，４’，４”  最適走査選択手段
５  符号化手段
６  画像圧縮データ出力手段
７  走査手段
７ａ  画像領域メモリ
７ｂ  走査アドレス生成器
８  小区間分割手段
９  区分線型近似手段
１０  併合処理手段
１１  小区間メモリ
１２  区間レジスタ
１３  区間分割処理部
１４  分割処理制御部
１５  小区間近似画像メモリ
２１  アドレス生成部
２２，２５，３２  自乗算器
２３  自乗加算アキュミュレータ
２４  加算アキュミュレータ
２６  アップカウンタ
２７，２９，３４，３６，７０  除算器
２８，３５  減算器
３０  減算アキュミュレータ
３１  自乗減算アキュミュレータ
３３  ダウンカウンタ
３７，６８，６９  加算器
３８  比較判定部
３９  最小累積誤差メモリ
４０  区分線型近似終了判定部
４１  左誤差レジスタ
４２  右誤差レジスタ
４３  左レベルレジスタ
４４  左区間長レジスタ
４５  右レベルレジスタ
４６  右区間長レジスタ
５１  併合処理判定部
５２  併合データ生成部
５３  併合区間レジスタ
６１  第１のレベル差判定部
６２  第２のレベル差判定部
６３  境界前区間長判定部
６４  境界後区間長判定部
６５  併合処理総合判定部
６６，６７  乗算器
８１  最適走査判定部
８２  最適走査セレクタ
９１  走査情報符号化部
９２  輝度情報符号化部
９３  区間長情報符号化部
９４  符号化情報合成部
１０１  処理打切判定部
１１１  基準区間数通知部
１２０−１〜１２０−ｍ  直交変換操作ユニット
１２１  直交変換手段
１２２  量子化手段
１２３  ラン・データ生成手段
【図１】
2004312693.tif 000014
【図２】
2004312693.tif 000015
【図３】
2004312693.tif 000016
【図４】
2004312693.tif 000017
【図５】
2004312693.tif 000018
【図６】
2004312693.tif 000019
【図７】
2004312693.tif 000020
【図８】
2004312693.tif 000021
【図９】
2004312693.tif 000022
【図１０】
2004312693.tif 000023
【図１１】
2004312693.tif 000024
【図１２】
2004312693.tif 000025
【図１３】
2004312693.tif 000026
【図１４】
2004312693.tif 000027
【図１５】
2004312693.tif 000028
【図１６】
2004312693.tif 000029
【図１７】
2004312693.tif 000030
【図１８】
2004312693.tif 000031
【図１９】
2004312693.tif 000032
【図２０】
2004312693.tif 000033
【図２１】
2004312693.tif 000034
【図２２】
2004312693.tif 000035
【図２３】
2004312693.tif 000036
【図２４】
2004312693.tif 000037
【図２５】
2004312693.tif 000038