(57)【要約】【課題】  ブロック単位の符号化データを生成する際に、互いに異なるスキャンの開始位置とスキャンルートに従ってブロック内の画素データを並べ替え、符号化データを生成し、その中の最小データ量である符号データを出力する。【解決手段】  ブロック分割部６０１は、符号化対象の画像データから、８×８画素で構成されるブロックを単位に入力する。符号化処理部６１０内のスキャン変換部６１１は、スキャン開始位置情報記憶部６１４、スキャンルート情報記憶部６１５の情報に従い、入力した８×８画素の並びを変更する。予測符号化部６１２は、並び変更後の画素データから符号化データを生成する。他の符号化処理部６２０、６３０、６４０は、それぞれのスキャン開始位置、スキャンルートに従い、符号化データを生成する。セレクタ６５０は、各符号化処理部で生成された符号化データの中で最小データ量となる符号化データを選択し、出力する。【選択図】  図６
2008278041.tif 000002
【特許請求の範囲】
【請求項１】
画像ブロックを表す複数の画素データを入力する入力手段と、
前記複数の画素データをスキャンし、符号化することにより、符号化データを生成する複数の符号化処理手段と、
前記符号化処理手段のそれぞれで生成された符号化データのうち、最小のデータ量である符号化データを選択する選択手段と、
前記複数の符号化データのいずれが選択されたかを示す識別情報と、選択された符号化データとを出力する出力手段とを備え、
前記符号化処理手段のそれぞれは、互いに、スキャン開始位置とスキャンルートの少なくとも一方が異なることを特徴とする画像符号化装置。
【請求項２】
前記符号化処理手段のそれぞれは、
前記スキャン開始位置の画素データの値を基準値とし、前記スキャンルートに従って得られた着目画素データと前記基準値との差が、予め設定された許容範囲内にある場合には、前記基準値として設定された画素から着目画素までの画素数をカウントし、
前記着目画素データの値と前記基準値との差が前記許容範囲を超える場合には、それまでにカウントした値を符号化データとして出力し、着目画素データを新たな基準値として設定すると共に、前記着目画素データの符号化データを出力し、
前記着目画素データと前記基準値との差が前記許容範囲内のまま、着目画素が最終画素の位置まで到達した場合には、ＥＯＢ（End Of Block）符号語を出力する
ことを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記符号化処理手段のそれぞれは、書き換え可能な記憶手段に格納されたスキャン開始位置を示す情報、スキャンルートを示す情報に従って、前記スキャンと符号化を行なうことを特徴とする請求項１に記載の画像符号化装置。
【請求項４】
前記許容範囲を設定する設定手段を更に備えることを特徴とする請求項２に記載の画像符号化装置。
【請求項５】
画像ブロックを表す複数の画素データを入力する入力工程と、
前記複数の画素データをスキャンし、符号化することにより、符号化データを生成する複数の符号化処理工程と、
前記符号化処理工程のそれぞれで生成された符号化データのうち、最小のデータ量である符号化データを選択する選択工程と、
前記複数の符号化データのいずれが選択されたかを示す識別情報と、選択された符号化データとを出力する出力工程とを備え、
前記符号化処理工程のそれぞれは、互いに、スキャン開始位置とスキャンルートの少なくとも一方が異なることを特徴とする画像符号化装置の制御方法。
【請求項６】
コンピュータが読込み実行することで、前記コンピュータを請求項１乃至４のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項７】
画像データを符号化する画像符号化装置であって、
符号化対象の画像データから、複数の画素データで構成されるブロックを単位に画像データを入力する入力手段と、
前記入力手段で入力したブロック内の各画素を、抽出色を持つ画素と、非抽出色である背景部を構成する画素に分類する分類手段と、
前記抽出色を符号化する第１の符号化手段と、
前記ブロック中の各画素が前記抽出色の画素であるか、前記背景部の画素であるのかを識別するため位置情報を符号化する第２の符号化手段と、
前記背景部を構成する画素に基づき、前記抽出色を持つ画素に対する置換情報を生成し、生成された置換情報で、前記抽出色を持つ画素のデータを置換する置換手段と、
前記置換手段による置換後のブロック内の画素データを符号化する第３の符号化手段と、
前記第１、第２、第３の符号化手段で生成された符号化データを多重化し、出力する多重化手段とを備え、
前記第２の符号化手段は、
入力したブロックの位置情報をスキャンし、符号化データを生成する複数の符号化処理手段と、
ここで、各々の符号化処理手段は、互いに異なるスキャン開始位置、及び、互いに異なるスキャンルートに従って前記ブロック内の前記位置情報の並びを変更し、並び変更後の位置情報から符号化データを生成する；
前記符号化処理手段それぞれで生成された符号化データのデータ量を比較し、最小データ量となった符号化データを選択する選択手段と、
前記選択手段が前記複数の符号化処理手段のいずれからの符号化データを選択したのかを示す識別情報と、選択した符号化データとを出力する出力手段とを含む
ことを特徴とする画像符号化装置。
【請求項８】
前記符号化処理手段のそれぞれは、
前記スキャン開始位置から前記スキャンルートに従ってランレングス符号化を行ない、ブロック内の最終画素位置まで同一データが連続する場合には、ＥＯＢ（End Of Block）符号語を出力する
ことを特徴とする請求項７に記載の画像符号化装置。
【請求項９】
前記符号化処理手段のそれぞれは、書き換え可能な記憶手段に格納されたスキャン開始位置を示す情報、スキャンルートを示す情報に従って、スキャンと符号化を行なうことを特徴とする請求項８に記載の画像符号化装置。
【請求項１０】
画像データを符号化する画像符号化装置の制御方法であって、
符号化対象の画像データから、複数の画素データで構成されるブロックを単位に画像データを入力する入力工程と、
前記入力工程で入力したブロック内の各画素を、抽出色を持つ画素と、非抽出色である背景部を構成する画素に分類する分類工程と、
前記抽出色を符号化する第１の符号化工程と、
前記ブロック中の各画素が前記抽出色の画素であるか、前記背景部の画素であるのかを識別するため位置情報を符号化する第２の符号化工程と、
前記背景部を構成する画素に基づき、前記抽出色を持つ画素に対する置換情報を生成し、生成された置換情報で、前記抽出色を持つ画素のデータを置換する置換工程と、
前記置換工程による置換後のブロック内の画素データを符号化する第３の符号化工程と、
前記第１、第２、第３の符号化工程で生成された符号化データを多重化し、出力する多重化工程とを備え、
前記第２の符号化工程は、
入力したブロックの位置情報をスキャンし、符号化データを生成する複数の符号化処理工程と、
ここで、各々の符号化処理工程は、互いに異なるスキャン開始位置、及び、互いに異なるスキャンルートに従って前記ブロック内の前記位置情報の並びを変更し、並び変更後の位置情報から符号化データを生成する；
前記符号化処理工程それぞれで生成された符号化データのデータ量を比較し、最小データ量となった符号化データを選択する選択工程と、
前記選択工程が前記複数の符号化処理工程のいずれからの符号化データを選択したのかを示す識別情報と、選択した符号化データとを出力する出力工程とを含む
ことを特徴とする画像符号化装置の制御方法。
【請求項１１】
コンピュータが読込み実行することで、前記コンピュータを請求項７乃至９のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項１２】
請求項６又は１１に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像の符号化技術に関するものである。
【背景技術】
【０００２】
従来、画像を符号化する方法として、直交変換を用いたＪＰＥＧ符号化などの方法あった。ここで簡単にＪＰＥＧ符号化について説明する。まず画像を８×８画素のブロックに分割し、各ブロックに対してＤＣＴ（離散コサイン変換）を行う。続いてＤＣＴで得られた８×８個のＤＣＴ係数値に対して、量子化テーブルを用いて量子化を行う。量子化テーブルは通常、高周波成分ほど量子化ステップ幅を大きくするため、量子化後の値は高周波成分ほど小さな値になり、０の発生頻度が高くなる。
【０００３】
続いて量子化後の値に対して符号化を行うが、符号化のプロセスはＤＣ成分とＡＣ成分で異なる。ＤＣ成分に関しては、ブロック間の相関が強いため差分予測符号化を行った後、ハフマン符号化される。差分予測符号化は直前の値との差を符号化する方式である。ハフマン符号化は、発生頻度の高い値には短い符号を、発生頻度の低い値には長い符号を与えることで結果的に全体の符号長を短くする符号化方法である。ＡＣ成分に関しては、ランレングス符号化を行った後、ハフマン符号化を行う。ランレングス符号化は、同一の値が長く続くほど符号化率が向上する符号化方法である。なお、量子化後の値に対してジグザグスキャンを行うことにより、高周波成分の０の値を連続させることで符号化効率を向上させている。
【０００４】
ＪＰＥＧ符号化は自然画像に対しては良好な圧縮方法である。しかし、その一方で、ＪＰＥＧ符号化は、文字や線画などの含まれる画像に対しては、画像の高周波成分が失われることを原因とするモスキートノイズが発生しやすい。また、直流成分の量子化誤差や高周波成分が失われることを原因とするブロックノイズも起こりやすいという問題がある。
【０００５】
これに対し、特許文献１においては、入力した画像データのエッジ成分を強調するエッジ強調器が、入力される画像データのエッジ成分を量子化手段にて用いられる量子化テーブルの内容に応じて強調することで、ノイズを低減させることが開示されている。
【０００６】
また、特許文献２には、画像を重要領域とそれ以外という判断を設け、直交変換、量子化処理した各ブロックに対し、重要領域に属していないブロックの量子化係数を０に置き換えることで、部分的に高画質を保つことが開示されている。
【特許文献１】特開平０９−１７２６３６号公報
【特許文献２】特開平０６−１６４９４１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、これまでの符号化では、或るブロック内の左上隅の位置を始点とし、その始点位置からラスタースキャンもしくはジグザグスキャンを行ない、符号化処理を行なっていた。符号化効率を高くするには、スキャン中に同じ値が連続する確率を高めることである。しかしながら、これまでの符号化技術では、ラスタースキャン、ジグザグスキャンのいずれであっても、スキャン終了位置は、ブロックの右下隅の位置である。すなわち、その右下隅の位置にそれまでとは異なるデータがある場合には、結局のところ、全データの符号化データを生成せざるをえず、符号化効率の点でまだまだ改善の余地があった。
【０００８】
本発明はかかる点に鑑みなされたものであり、符号化効率を更に向上させる技術を提供しようとするものである。
【課題を解決するための手段】
【０００９】
かかる課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
画像ブロックを表す複数の画素データを入力する入力手段と、
前記複数の画素データをスキャンし、符号化することにより、符号化データを生成する複数の符号化処理手段と、
前記符号化処理手段のそれぞれで生成された符号化データのうち、最小のデータ量である符号化データを選択する選択手段と、
前記複数の符号化データのいずれが選択されたかを示す識別情報と、選択された符号化データとを出力する出力手段とを備え、
前記符号化処理手段のそれぞれは、互いに、スキャン開始位置とスキャンルートの少なくとも一方が異なることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、複数の符号化処理手段が、それぞれ互いに異なるスキャンの開始位置とスキャンルートに従ってブロック内の画素データを並べ替えを行ない、符号化データを生成する。そして、その中の最小データ量である符号データを出力する。この結果、符号データ量を大幅に削減することが可能となる。
【発明を実施するための最良の形態】
【００１１】
以下、添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１２】
＜第１の実施形態＞
第１の実施形態における画像符号化装置のブロック構成図を図６に示す。
【００１３】
ブロック分割部６００は、符号化対象の画像データからｍ×ｎ画素で構成される画像データ（以下、画像ブロックデータという）を入力する。画像ブロックデータの入力順は、ブロック単位のラスタースキャン順とする。説明を簡単なものとするため、実施形態では画像ブロックは８×８画素のサイズであるものとして説明する。また、符号化対象の画像データの供給源は、イメージスキャナとするが、その画像データを記憶している記憶媒体でも構わないし、印刷データに基づき画像データを生成するレンダリング部であっても構わず、その種類は問わない。
【００１４】
本装置は、画像ブロックデータを入力し符号化データを生成する複数の符号化処理部を備える。図示の符号６１０、６２０、６３０、６４０がその符号化処理部である。なお、ここでは符号化処理部が４つの例を示しているが、その数によって本発明が限定されるものではない。
【００１５】
画像符号化処理部６１０、６２０、６３０、６４０それぞれは、ブロック分割部６００から供給された画像ブロックデータを符号化し、符号化データを生成すると共に、生成した符号化データをセレクタ部６５０に出力する。
【００１６】
セレクタ部６５０は、画像符号化処理部６１０、６２０、６３０、６４０から出力された符号化データのうち、符号化データ量が最も少ない（最小ビット数）ものを１つ選択する。そして、セレクタ部６５０はいずれの符号化データを選択したのかを示す識別ビットを生成し、その識別ビットを先ず出力し、それに後続して、選択した符号化データを出力する。実施形態の場合、画像符号化処理部は４つであるので、この識別ビットは２ビット有ればよいことになる。
【００１７】
本実施形態における画像符号化装置の処理概要は上記の通りであるが、以下、画像符号化処理部６１０について更に詳細に説明する。なお、以下の説明から明らかになるが、画像符号化処理部６１０、６２０、６３０、６４０は、ハードウェア的には同じである。ただし、それぞれのスキャン開始位置情報記憶部、スキャンルート情報記憶部には、それじれ異なる情報が格納される。また、スキャン開始位置情報記憶部、スキャンルート情報記憶部は書き換え可能なメモリ（レジスタ）で構成する。このようにする理由は、４つの画像符号化処理部を別々に回路設計することが不要となり、その分だけ開発コストが下げることができるためである。なお、実施形態では、４つの画像符号化処理部内の予測誤差許容値記憶部には同じ情報を格納しているものとして説明する。
【００１８】
スキャン変換部６１１は、１つの画像ブロックデータ（８×８個の画素データ）を格納するための内部バッファを持つ。スキャン変換部６１１は、ブロック分割部６００から８×８画素の画像ブロックデータをその内部バッファに格納すると、画素配列の変換処理を開始する。スキャン変換部６１１は、先ず、スキャン開始位置情報記憶部６１４に格納されたスキャン開始位置情報（ｘ座標、ｙ座標形式のデータ）を読込み、その位置で示される内部バッファの画素データを読出し、予測符号化部６１２に出力する。この後、スキャン変換部６１１は、スキャンルート情報記憶部６１５に格納された相対位置情報を順次読込み、内部バッファをアクセスするアドレスを順次更新する。そして、そのアドレスが更新される度に、内部バッファをアクセスして画素データを読出し、予測符号化部６１２に出力する。このようにして、スキャン変換部６１１は、入力した８×８画素データを、スキャン開始位置情報記憶部６１４、スキャンルート情報記憶部６１５を参照し、画素データを並び替えた１次元配列の６４個の画素データを生成し、予測符号化部６１２に出力する。予測符号化部６１２は、並び替えの変更後の画素データを符号化することになる。なお、スキャンルート情報記憶部６１５に相対アドレスを記憶する理由は、スキャン順が必ず隣接する画素を通るようにするのであれば、Ｘ、Ｙアドレスとも−１、０、＋１のみを記憶すればよくなり、記憶容量を削減できるためである。Ｘ、Ｙアドレスとも３通りのいずれかを特定できれば良いので、Ｘ、Ｙ座標の相対アドレスはそれぞれ２ビットあれば十分と言える。
【００１９】
図７（ａ）は、画像符号化処理部６１０におけるスキャン変換部６１１がスキャンルートを示している。図示の場合、スキャン開始位置は画像ブロックの左上隅であることを示している。そして、その開始位置から右方向に向かい右端になった場合には、１つの下のラインを今度は右端から左端に向かうルートに沿ってスキャンすることを繰り返している。
【００２０】
図７（ｂ）乃至（ｄ）は、符号化処理部６２０乃至６４０内のそれぞれのスキャン変換部におけるスキャン開始位置とスキャンルートを示している。図示の如く、４つの符号化処理部内のスキャン変換部のスキャン開始位置とそのスキャンルートは、互いに異なることが理解できよう。
【００２１】
次に、予測符号化部６１２の処理を説明する。この予測符号化部６１２は、スキャン変換部６１１から入力した６４個の画素データを、その入力順に符号化データを生成し、出力する。
【００２２】
予測符号化部６１２の符号化アルゴリズムは次の通りである。
【００２３】
予測符号化部６１２は、内部にカウンタを有し、着目ブロックの画像データ（６４個の画素データ）の符号化を開始する際に、そのカウンタをゼロクリアする。そして、最初の画素データについては、その画素データを出力すると共に、その画素データの値を基準値として保持する。２つ目以降の画素データを入力した場合には、基準値との差分の絶対値（以下、単に差分値という）を算出し、その差分値が予測誤差許容値記憶部６１６に格納された予測誤差許容値以下であるか否かを判定する。そして、差分値が予測誤差許容値以下である場合には、着目画素データの出力は行なわず、カウンタを“１”だけ増加させていく。そして、着目画素データと基準値との差分値が予測誤差許容値を超えたと判定した場合、先ず、カウンタに保持された値に基づく符号化データを出力する。そして、着目画素データの符号化データを出力すると共に、着目画素データの値を新たな基準値として更新する。この際、カウンタをゼロクリアする。なお、着目画素が最終画素位置（最初の画素を０番目とすると、６３番目の画素）になっても、差分値が予測誤差許容値以下であると判定した場合には、スキップした数の代わり、予め設定されたＥＯＢ(End Of Block)符号語を出力する。
【００２４】
以下、予測符号化部６１２の処理の一例を説明する。今、符号化対象の８×８画素の画像ブロックデータが、図７（ｅ）であるとする。また、予測誤差許容値記憶部６１６に格納されている予測誤差許容値が“３”であるものとする。
【００２５】
ここで、予測符号化部６１２が生成し、出力する予測符号化データを（Ａ,Ｂ）と表わすこととする。ここで、Ａ、Ｂの意味は次の通りである。
Ａ：差分値が予測誤差許容値より大きい場合“０”、予測誤差許容値以下の場合は“１”；
Ｂ：差分値が予測誤差許容値より大きい場合は入力した画素データ、予測誤差許容値以下ならば、それまでカウントしたデータ；
但し、ブロック内の最終画素まで入力しても、差分値が予測誤差許容値より小さい場合には「ＥＯＢ」とする。
【００２６】
さて、図７（ｅ）の画像ブロックデータを、図７（ａ）のスキャンルートでスキャンした場合の符号化データは、次のようになる。
「（０,０）（１,５３）（０,２３）（１,３）（０,１２）（０,０）ＥＯＢ」
可変長符号化部６１３は、上記符号化データから更に二進の符号化データを生成し、セレクタ部６５０に出力する。可変長符号化部６１３は、如何なる符号化技術を用いても構わない。
【００２７】
また、画像符号化処理部６２０内の予測符号化部は、図７（ｂ）のスキャンルートでスキャンして符号化データを生成する。この場合に生成される符号化データは次のようになる。
「（０,２）、（１,４７）、（０,２０）、（１,１）、（０,２）、（１,１０）、（０,１２）、（０,２０）、（１,１）」、
また、画像符号化処理部６３０内の予測符号化部は、図７（ｃ）のスキャンルートでスキャンして符号化データを生成する。この場合に生成される符号化データは次のようになる。
「（０,２１）、（１,１）、（０,１２）、（０,０）、（１,１０）、（０,２３）、（１,１）、（０,２）、ＥＯＢ」、
そして、画像符号化処理部６４０内の予測符号化部は、図７（ｄ）のスキャンルートでスキャンして符号化データを生成する。この場合に生成される符号化データは次のようになる。
「（０,０）、（１,４）、（０,１２）、（０,２０）、（１,３）、（０,２）、ＥＯＢ」
【００２８】
ここで注目すべき点は、予測符号化部６１２からＥＯＢ符号語が出力された場合、そのＥＯＢの１つ以前の符号語で示される画素データで示されるデータが、最後の画素まで継続しているものと判定できる点である。換言すれば、予測符号化部６１２からＥＯＢ符号語が発生するタイミングが早いほど、可変長符号化部６１３が生成する符号化データのデータ量は少なくなると言える。また、予測誤差許容値記憶部６１６に格納する予測誤差許容値を“０”にすると、符号化処理部６１０は可逆符号化データを生成することになる。従って、予測誤差許容値記憶部６１６に格納する値は、ユーザの指示に従って設定できるようにするため、書き込み可能なメモリで構成すると好都合である。
【００２９】
以上の手順を全ブロックに対して繰り返すことで、符号化対象の画像データの全域についての符号化が完了することになる。なお、セレクタ６５０は、着目ブロックから生成された４つの符号化データのうち、符号長が最短となるものを１つ選択すると共に、その選択した符号化データがいずれの符号化処理部で生成されたかを示す識別情報（２ビット）を先頭に付加して出力する。また、符号化処理の開始時には、符号化対象の画像のサイズ（水平、垂直方向の画素数）、各画素の精度（ビット数）、色空間の種類等、復号処理に必要な情報を含むファイルヘッダを生成することになる。
【００３０】
次に、実施形態におけるスキャン変換部６１１及び予測符号化部６１２の処理手順を、図８のフローチャートに従って説明する。図８は、１つの画像ブロックに対する処理手順を示している。
【００３１】
まずステップＳ８０１にて、スキャン変換部６１１は、スキャン開始位置情報記憶部６１４及びスキャンルート情報記憶部６１５に格納されたそれぞれの情報に基づき、入力した画像ブロックデータを構成する画素の並びを変換する。この後、ステップＳ８０２に処理を進める。ステップＳ８０２以降は、予測符号化部６１２の処理となる点に注意されたい。
【００３２】
次に、ステップＳ８０２では、予測符号化部６１２は内部のカウンタＣＮＴをゼロクリアする。
【００３３】
そして、ステップＳ８０３にて、スキャン変換部６１１から入力した着目画素データと基準値との差分値を算出し、その差分値が予測誤差許容値以下であるか否かを判定する。なお、着目画素が最初の画素である場合には、差分値は予測誤差許容値を超えるものと判定し、カウンタＣＮＴの値“０”を出力するものとする。
【００３４】
さて、着目画素データと基準値との差分値が、予測誤差許容値以下であると判断した場合には、ステップＳ８０４に進み、着目画素は最終画素か否かを判定する。最終画素ではない判定した場合には、ステップＳ８０５に進み、カウンタＣＮＴを“１”だけ増加させ、次の画素データを読込み、ステップＳ８０３の処理を行なう。また、ステップＳ８０４にて、着目画素データが最終画素であると判断した場合には、ＥＯＢ符号語を出力し、本処理を終える。
【００３５】
一方、ステップＳ８０３にて、着目画素データと基準値との差分値が、予測誤差許容値よりも大きいと判断した場合には、処理はステップＳ８０７に進む。ステップＳ８０７では、カウンタＣＮＴの値が“０”であるか否かを判断する。
【００３６】
カウンタＣＮＴの値が“０”であると判定した場合には、ステップＳ８０９にて、着目画素データを出力する。
【００３７】
また、ステップＳ８０７にて、カウンタＣＮＴの値が“０”以外であると判定した場合には、ステップＳ８０８にてカウンタＣＮＴの値を出力し、その後のステップＳ８０９にて、着目画素データを出力する。
【００３８】
この処理はステップＳ８１０に進み、着目画素が最終画素か否かを判定する。着目画素が最終画素ではないと判定した場合には、カウンタＣＮＴの値を“０”に設定し、ステップＳ８０３に処理を戻す。また、着目画素が最終画素であると判定した場合には、１画像ブロック分の符号化処理を終了する。
【００３９】
以上説明したように本実施形態によれば、４つの画像符号化処理部６１０、６２０、６３０、６４０は、画像データブロック中のそれぞれ異なる開始位置から、それぞれ異なるスキャンルートに従って符号化データを生成する。且つ、これら画像符号化処理部は、着目画素データの差分値（予測誤差）が許容範囲内のまま、その着目画素が最終画素に到達した場合にはＥＯＢ符号語を生成する。そして、この４つの符号化処理部で生成された最も短い符号化データを選択することで、圧縮率の高い符号化データを生成することが可能になる。
【００４０】
なお、上記符号化データを復号する場合には、上記と逆の手順を踏めばよい。すなわち、先ず、第１の復号部にて、先頭の２ビットの識別情報に後続する符号化データを復号し、予測符号化部６１２で生成された符号化データまで復号する。そして、第２の復号部では、一次元の６４個の画素データを生成する。この後は、識別ビットで特定される開始位置とスキャンルートに従って、６４個の画素データを配置し、出力すればよい。
【００４１】
なお、実施形態では、画像ブロックのサイズを８×８画素としたが、このサイズによって本発明が限定されるものではなく、一般にｍ×ｎ画素（ｍ，ｎは２以上の整数）に適用可能である。また、符号化処理部の数も４つとし、そのスキャンルートも図７（ａ）乃至（ｄ）としたが、この符号化処理部の数、スキャンルートもこれに限定されない。特に、実施形態で説明したように、スキャン開始位置、スキャンルートは、それぞれの情報を変更することで自由に設定できることからも容易に理解できよう。
【００４２】
＜第２の実施形態＞
第２の実施形態を説明する。図１は、本第２の実施形態における画像符号化装置のブロック構成図である。
【００４３】
図示において、前処理部１０１は、画像データをブロック単位に入力し、入力したブロック内で抽出色部と背景部（非抽出色部）とに分離するまでの一連の処理が行われる。本第２の実施形態でも、ブロックのサイズは８×８画素とするが、１６×１６画素、３２×３２画素などでも構わない。
【００４４】
抽出色部と背景部の分離方法の一例を示すのであれば次の通りである。
【００４５】
先ず、ブロック内の画素データの濃度の平均値を算出する。そして、その平均値よりも大きな値を持つ画素群（以下、第１の画素群という）と、その平均値以下の画素群（以下、第２の画素群という）とに分類する。そして、第１の画素群の平均値（第１の平均値）と第２の画素群の平均値（第２の平均値）を求め、それらの差の絶対値が、予め設定された閾値を超えるか否かを判定する。超えていれば、分類できた旨の制御信号をパック部１０５に通知する、そして、第１の画素群を、抽出色部を構成する画素群と見なす。なお、上記の第２の平均値は、後述する置換情報として利用される。
【００４６】
なお、第１の平均値と第２の平均値との差の絶対値が、予め設定された閾値以下の場合、前処理部１０１は、抽出画素部と背景画素部への分離不可を示す制御信号をパック部１０５に通知する。
【００４７】
ここで、抽出色部のデータは、抽出色を持つ画素の存在位置を示す位置情報（位置データ）、及び、抽出色情報で構成される。この位置情報は、抽出色部に属する画素位置では“１”、背景画素部（非抽出色部）に属する画素位置では“０”とする２値化した１ビットデータである。すなわち、位置情報とは、ブロック中の各画素が抽出色の画素であるか、非抽出色の画素であるのかを識別するため情報とも言える。本実施形態では、１ブロックのサイズが８×８画素としているので、この位置データは８×８＝６４ビットとなる。ビットの並びはラスタースキャン順とする。この位置データは後段の第１の符号化部１０２にて符号化される。また、抽出色情報は、後段の第２の符号化部１０３にて符号化される。
【００４８】
一方、背景部は、ブロック中の抽出色部として判定された各画素の値を、先に説明した置換情報（第２の平均値）で置換した８×８画素のデータである。また、１ブロック中の非抽出部と判定された画素は、置換処理は行なわない。この結果、背景部で示されるブロックで示される画像データ（置換後の画像データ）には、高周波成分が含まれない、もしくは高周波成分の含む割合は少なくできる。この背景部は、後段の第３の符号化部１０４（例えば、ＤＣＴ変換部、量子化部、エントロピー符号化で構成する）にて非可逆符号化される。
【００４９】
第１の符号化部１０２、第２の符号化部１０３、第３の符号化部１０４の各符号化部は、それぞれ独立した符号化アルゴリズムを採用することが可能である。
【００５０】
パック部１０５は、各符号化部で符号化されたデータを多重化し、出力する。ただし、先に説明したように、前処理部１０１から、抽出画素部と背景画素部の分離不可を示す信号を受信した場合、パック部１０５は、符号化部１０４からの符号化データのみを出力する。なお、１ブロックが３種類の符号化データで構成されているか、１種類の符号化データで構成されているかを識別するため、パック部１０５は１ブロックの符号化データの先頭（ブロックヘッダ）に識別ビットを格納する。
【００５１】
さて、本第２の実施形態の特徴は、先に示した抽出画素位置データを符号化する第２の符号化部１０２にある。そこで、この第２の符号化部１０２について以下に詳細に説明する。
【００５２】
図２は、本第２の実施形態における第２の符号化部１０２のブロック構成図である。
【００５３】
図示の如く、第２の符号化部１０２の内部構成は、第１の実施形態で示した図６と略同様の構成である。すなわち、第２の符号化部１０２は、複数（実施形態では４つ）の符号化処理部２１０、２２０、２３０、２４０を有する。そして、セレクタ部２５０は、４つの符号化処理部それぞれからの符号化データのデータ量を比較し、最小データ量となる符号化データを選択する。そして、セレクタ部２５０は、いずれを選択したのかを識別する識別情報（ＩＤ情報）に続いて、選択した符号化データを出力する。
【００５４】
４つの符号化処理部はハードウェア上は同じであるので、ここでも符号化処理部２１０について説明する。
【００５５】
スキャン変換部２０１は、前処理部１０１から供給された抽出画素位置データ（８×８＝６４ビット）を入力する。そして、スキャン変換部２０１はスキャン開始位置情報部２１３に記憶されているスキャン開始位置情報と、スキャンルート情報記憶部２１４に格納されているスキャンルート情報に基づき、位置情報をスキャンし（並べ替えを行ない）、出力する。すなわち、位置情報の並び替えを行なう。その並び替え後の位置情報は可変長符号器２１２に供給される。可変長符号化部２１２は、入力した位置情報を可変長符号化し、生成した符号化データをセレクタ部２５０に出力する。
【００５６】
以上は、符号化処理部２１０についてであるが、他の符号化処理部２２０、２３０、２４０も同様である。異なるのは、各符号化処理部内のスキャン変換部によるスキャン開始位置情報部とスキャンルート情報記憶部にセットされる情報である。
【００５７】
セレクタ部２５０は、先に説明したように、各符号化処理部２１０、２２０、２３０、２４０で可変長符号化データを受信し、それぞれのデータの符号量を比較し、最も符号量の少ない符号化データを一つ選択する。そして、選択した符号化データが符号化処理部２１０、２２０、２３０、２４０のいずれからのものであるのかを識別するための識別情報を先頭にし、それに後続して選択した符号化データを出力する。
【００５８】
ここで本第２の実施形態における符号化処理部２１０内のスキャン変換部２１１は、図３（ａ）に示すように、左上隅位置をスキャン開始位置とする。そして、スキャン変換部２１１は、その開始位置から、右方向にスキャンし、右端に到達したとき、１ラインしたの右端から今度は左方向にスキャンすることを繰り返す（水平ジグザグスキャン）。スキャン変換部２１１は、そのスキャンルート（スキャンパターン）に従って位置情報を読込み、可変長符号化部２１２に出力することになる。
【００５９】
他の符号化処理部２２０、２３０、２４０内のそれぞれのスキャン変換部は、図３（ｂ）乃至（ｄ）に示すように異なるスキャン開始位置及び異なるスキャンルートに従って位置情報の並び替えを行なう。
【００６０】
先に説明したように１画素の位置情報は２値であるため、可変長符号化部２１２は、２値データを符号化するものであり、例えばランレングス符号化を用いる。可変長符号化部２１２は、例えば、「値“０”のランレングス長、値“１”のランレングス長、値“０”のランレングス長、・・・」という形式の符号化データを生成する。
【００６１】
但し、スキャン最終位置まで同一値が連続した場合には、ランレングス符号化データの代わりにＥＯＢ符号語を付加し、出力する。ここで、ＥＯＢはＥｎｄ  Ｏｆ  Ｂｌｏｃｋの略語である。
【００６２】
今、８×８ビットの位置情報が図３（ｅ）に示す通りであるとき、図３（ａ）のスキャンルートに基づいて可変長符号化部２１２が生成する符号化データは、「５４、５、ＥＯＢ」となる。また、図３（ｂ）のスキャンルートの場合の符号化データは「４８、２、１１、３」、図３（ｃ）のスキャンルートの場合の符号化データは「３，１１、２、ＥＯＢ」、図３（ｄ）のスキャンルートの場合の符号化データは「５、５、ＥＯＢ」となる。
【００６３】
但し、スキャン最終位置まで同一値が連続した場合には、ランレングス符号化データの代わりにＥＯＢ符号語を付加し、出力する。
【００６４】
以上の手順を全ブロックに対して繰り返す。
【００６５】
なお、復号する場合には、ＥＯＢ符号語を発見した直前の位置情報が仮に“１”であり、且つ、それまでに３０ビットの位置情報を復号していた場合、残りの３４（＝６４−３０）ビットは“０”の値と見なして復号すればよい。
【００６６】
次に符号化処理部２１０、２２０、２３０、２４０及びセレクタ部２５０の処理を、図４のフローチャートに従って説明する。
【００６７】
先ず、ステップＳ４０１ａにて、符号化処理部２１０のスキャン変換部２１１は、スキャン開始位置情報記憶部２１３、スキャンルート情報記憶部２１４に格納されたそれぞれの情報に基づき、抽出画素位置情報のスキャン変換（位置情報の並べ替え）を行なう。他の符号化処理部２２０、２３０、２４０それぞれののスキャン変換部も、ステップＳ４０１ｂ、４０１ｃ、４０１ｄにて、同様の処理を行なう。
【００６８】
次いで、ステップＳ４０２ａにて、符号化処理部２１０の可変長符号化部２１２が、並べ替え後の抽出画素位置情報の可変長符号化を行なう。このとき、最後の位置情報に至るまでに位置情報が変化しなかった場合、その位置情報のランレングス符号化データの代わりにＥＯＢ符号語を設定する。他の符号化処理部２２０、２３０、２４０それぞれの可変長符号化部も、ステップＳ４０２ｂ、４０２ｃ、４０２ｄにて、同様の処理を行なう。
【００６９】
符号化処理部２１０、２２０、２３０、２４０における１ブロック分の符号化処理を終えると、処理はステップＳ４０３に進む。このステップＳ４０３において、セレクタ部２５０は、各符号化処理部で生成された符号化量（符号化データ長）を比較し、もっとも符号量の少ないものを選択する。そして、ステップＳ４０４にて、いずれの符号化データを選択したのかを示す識別情報を先頭にして、選択した符号化データを出力する。なお、実施形態の場合、符号化処理部の数は４つであるので、この識別情報は２ビットあれば十分である。
【００７０】
ステップＳ４０５では、まだ符号化処理が行われていないブロックがあるか否かが判定され、未符号化のブロックが存在すればステップＳ４０１ａ、４０１ｂ、４０１ｃ、４０１ｄ以降の処理を繰り返す。また、全てのブロックで符号化処理が終了していれば処理を終了する。
【００７１】
以上説明したように本第２の実施形態によれば、画像データをブロック単位に符号化する場合の、抽出色位置を示す位置情報（２値データ）を効率良く符号化することが可能になる。
【００７２】
＜第３の実施形態＞
なお、上記第１の実施形態では、図７（ａ）乃至（ｄ）のスキャンパターン、第２の実施形態では図３（ａ）乃至（ｄ）に示すスキャンパターンを用いる例を説明したが、これによって本発明が限定されるものではない。要するに、スキャン開始位置情報記憶部、スキャンルート情報記憶部に設定する情報に依存して、如何なる開始位置、スキャンルートも設定できる。
【００７３】
例えば、例えば、図５（ａ）乃至（ｄ）に示すスキャン開始位置及びスキャンルートを採用してもかまわない。
【００７４】
図５（ａ）はスキャン開始位置を左上隅とし、下方向にジグザグスキャンする例である。同図（ｂ）は、スキャン開始位置を左下隅とし、右方向にジグザグスキャンする例を示している。また、同図（ｃ）は、スキャン開始位置を右下隅とし、左上方向にジグザグスキャンする例を示している。そして、同図（ｄ）は、スキャン開始位置を右上隅とし、左下方向にジグザグスキャンする例を示している。これらの設定は、スキャン開始位置情報記憶部２１３、スキャン開始位置からの相対座標を記憶しているスキャンルート情報記憶部２１４の情報を変更することで実現できる。
【００７５】
仮に、この図５（ａ）乃至（ｄ）のスキャンパターンを、第２の実施形態に適用する場合について考察する。ただし、各符号化処理部内の可変長符号化部は、符号化対象データから「０ランレングス長、１ランレングス長、０ランレングス長、１ランレングス長、・・・」と、０、１のラン（同一データ）の符号化データを交互に出力する。ただし、最終の位置情報まで同じデータが連続する場合には、そのラン長の符号語の代わりに、ＥＯＢ符号語を出力するものとする。
【００７６】
この場合、符号化対象のデータ（位置情報）が図５（ｅ）の場合、図５（ａ）のスキャンパターン５０１に従って符号化した場合の符号化データは、「４０、１、１３、１、１、３、ＥＯＢ」となる。また、図５（ｂ）のスキャンパターン５０２に従って符号化した場合の符号化データは「４７、３、１１、１、１、１」となる。そして、図５（ｃ）のスキャンパターン５０３を使用した場合の符号化データは「２，１、３、ＥＯＢ」、図６（ｄ）のスキャンパターン５０４を使用した場合は「１５、１、１２、２、１２、２、ＥＯＢ」となる。この結果からもわかるように、図５（ｃ）のスキャンパターン５０３を用いた場合の符号化データ量は、他の符号化データと比較して、十分に少なくできることが理解できよう。
【００７７】
以上を考察すると、４つの符号化処理部に設定するスキャン開始位置情報、スキャンルート情報の組み合わせを幾つか用意し、ユーザがそのいずれを選択したかを示す情報を、符号化ファイルのファイルヘッダに格納するようにすることが考えられる。
【００７８】
例えば、１つの符号化処理部に設定するスキャン開始位置、スキャンルートを（ＳＳ，ＳＲ）と表現する。実施形態では、４つの符号化処理部があるわけであるから、４つの符号化処理部に設定するスキャン開始位置、及び、スキャンルートの情報は｛（ＳＳ１，ＳＲ１），（ＳＳ２，ＳＲ２），（ＳＳ３，ＳＲ３），（ＳＳ４，ＳＲ４）｝と表現できる。この４つの組み合わせを、変数ｉ（ｉは０、１、２…）を用いてＰ（ｉ）と定義する。
Ｐ（ｉ）＝｛（ＳＳ１（ｉ），ＳＲ１（ｉ）），（ＳＳ２（ｉ），ＳＲ２（ｉ）），（ＳＳ３（ｉ），ＳＲ３（ｉ）），（ＳＳ４（ｉ），ＳＲ４（ｉ））｝
【００７９】
符号化を行なう場合には、変数ｉを０から順番に変更していき、その都度、符号化処理を行なう。そして、符号量が最小となる変数ｉを決定し、その変数ｉを符号化データのファイルヘッダに格納して出力する。
【００８０】
復号装置は、先ず、ファイルヘッダを解析して変数ｉを抽出することで、｛（ＳＳ１，ＳＲ１），（ＳＳ２，ＳＲ２），（ＳＳ３，ＳＲ３），（ＳＳ４，ＳＲ４）｝の４つのパターンを決定すればよいであろう。
【００８１】
以上のようにすると、４つの符号化処理部を用いながらも、それ以上の組み合わせのスキャン開始位置とスキャンルートによる符号化処理を行なうことが可能となる。
【００８２】
なお、上記は第１の実施形態にも、そのまま反映させても構わない。以上説明したように本第３の実施形態にしたがえば、第１、第２の実施形態と比較し、符号化効率を更に上げることが可能になる。
【００８３】
以上本発明に係る実施形態を説明した。本実施形態では、符号化処理部の数を４つの例を示したが、この数に限定されるものではない。要するに、複数の符号化処理部において、それぞれが異なるスキャン開始位置、異なるスキャンルートに従って符号化対象のデータを並べ替えを行なうようにすれば良い。
【００８４】
また、上記実施形態で示した機能を、パーソナルコンピュータ等の汎用情報処理装置が実行するコンピュータプログラムによって実現できることは明らかである。ＯＳ（オペレーティングシステム）がマルチタスクに対応しているのであれば、１ブロックの符号化処理を並列に行なえば良いであろう。また、符号化処理を並列処理できない場合には、ブロック単位に順番に符号化処理を行ない、その後で比較処理を行なえば良い。
【００８５】
また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されており、それを読取り装置（ＣＤ−ＲＯＭドライブ等）にセットして、システムにコピーもしくはインストールすることで実行可能になる。従って、かかるコンピュータ可読記憶媒体も本発明の範疇にあるのは明らかである。
【図面の簡単な説明】
【００８６】
【図１】第２の実施形態における画像符号化装置のブロック構成図である。
【図２】第２の実施形態における第２の符号化部の構成を示す図である。
【図３】第２の実施形態における各符号化処理部のスキャンルートと符号化対象のデータの一例を示す図である。
【図４】第２の実施形態における第２の符号化部の処理手順を示すフローチャートである。
【図５】他の実施形態におけるスキャンルートと符号化対象のデータの一例を示す図である。
【図６】第１の実施形態に係る画像符号化装置のブロック構成図である。
【図７】第１の実施形態における各符号化処理部のスキャンルートと符号化対象のデータの一例を示す図である。
【図８】第１の実施形態における各符号化処理部の符号化処理手順を示すフローチャートである。
【図１】
2008278041.tif 000003
【図２】
2008278041.tif 000004
【図３】
2008278041.tif 000005
【図４】
2008278041.tif 000006
【図５】
2008278041.tif 000007
【図６】
2008278041.tif 000008
【図７】
2008278041.tif 000009
【図８】
2008278041.tif 000010