(57)【特許請求の範囲】
【請求項１】
多値画像データから画素ブロックを単位に、周波数変換、量子化処理を行ない、当該量子化処理で得られた多値の各係数を符号化する画像符号化装置であって、
前記各係数についての、最上位から最下位ビットに向かって最初に“１”となるビット位置から最下位ビットまでの有効ビット数を検出し、各有効ビット数の出現回数をカウントするカウント手段と、
有効ビット数Ｂの出現回数をＮ（Ｂ）と定義し、出現回数が１以上の最大の有効ビット数をｂmaxと定義し、変数ｂ＝０、１、２…に対する次式の合算関数：
Ｓ（ｂmax−ｂ）＝ΣＮ（ｂmax−ｉ）  （ｉ＝０、１、…、ｂ）
において、予め設定された閾値Ｔｈとの関係が、
Ｓ（ｂmax−ｂ）＞Ｔｈ
を満たす最大整数ｂを求め、当該最大整数ｂに基づいて、境界ビット位置を決定する境界ビット位置決定手段と、
前記各係数の値を、前記境界ビット位置決定手段で算出した境界ビット位置を境界にして、上位ビット部、下位ビット部とに分離する分離手段と、
該分離手段で分離した各係数の前記上位ビット部を符号化する上位ビット符号化手段と、
前記分離手段で分離した各係数の前記下位ビット部を符号化する下位ビット符号化手段と、
前記上位ビット符号化手段、前記下位ビット符号化手段それぞれで得られた符号化データから、着目画素ブロックの符号化データを生成し、出力する出力手段と
を備えることを特徴とする画像符号化装置。
【請求項２】
前記上位ビット符号化手段は、ゼロの連続数と非ゼロの値の組み合せを符号化するランレングス符号化手段であって、
前記下位ビット符号化手段は、各係数の前記下位ビット部の同一ビット位置のビット情報を連結したビットプレーンに変換し、出力する手段である
ことを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記分離手段は、前記境界ビット位置決定手段で算出した境界ビット位置より上位の第１の上位ビット部と、前記境界ビット位置−１より上位の第２の上位ビット部と、前記境界ビット位置以下の下位ビット部とに分離し、
前記上位ビット符号化手段は、前記第１の上位ビット部、前記第２の上位ビット部をそれぞれ符号化し、
前記出力手段は、
前記第１の上位ビット部の符号量をＣａ、前記第２の上位ビット部の符号量をＣｂ、前記下位ビット部の符号量をＣｃ、そして、前記下位ビット部の符号化データから、前記境界ビット位置のビットプレーンの符号化データを除いた符号化データの符号量をＣｄと定義したとき、
Ｃａ＋Ｃｃ≦Ｃｂ＋Ｃｄの場合、前記上位ビット符号化手段で得られた前記第１の上位ビット部の符号化データと前記下位ビット符号化手段で得られた符号化データを前記着目画素ブロックの符号化データとして出力し、
Ｃａ＋Ｃｃ＞Ｃｂ＋Ｃｄの場合、前記下位ビット符号化手段で得られた符号化データから前記境界ビット位置のビットプレーンの符号化データを除外した符号化データと、前記上位ビット符号化手段で得られた前記第２の上位ビット部の符号化データとを、前記着目画素ブロックの符号化データとして出力することを特徴とする請求項２に記載の画像符号化装置。
【請求項４】
更に、前記着目ブロック内の各係数に基づき、各ビット位置を境界ビット位置とした場合の各係数の上位ビット部の非ゼロランの数を計数する計数手段と、
前記境界ビット位置決定手段で算出された境界ビット位置の前記非ゼロランの数と予め設定された閾値とを比較し、当該比較結果に基づき、前記境界ビット位置決定手段で算出された境界ビット位置を調整する調整手段と
を備えることを特徴とする請求項１又は２に記載の画像符号化装置。
【請求項５】
多値画像データから画素ブロックを単位に、周波数変換、量子化処理を行ない、当該量子化処理で得られた多値の各係数を符号化する画像符号化装置の制御方法であって、
前記各係数についての、最上位から最下位ビットに向かって最初に“１”となるビット位置から最下位ビットまでの有効ビット数を検出し、各有効ビット数の出現回数をカウントするカウント工程と、
有効ビット数Ｂの出現回数をＮ（Ｂ）と定義し、出現回数が１以上の最大の有効ビット数をｂmaxと定義し、変数ｂ＝０、１、２…に対する次式の合算関数：
Ｓ（ｂmax−ｂ）＝ΣＮ（ｂmax−ｉ）  （ｉ＝０，１，…，ｂ）
において、予め設定された閾値Ｔｈとの関係が、
Ｓ（ｂmax−ｂ）＞Ｔｈ
を満たす最大整数ｂを求め、当該最大整数ｂに基づいて、境界ビット位置を決定する境界ビット位置決定工程と、
前記各係数の値を、前記境界ビット位置決定工程で算出した境界ビット位置を境界にして、上位ビット部、下位ビット部とに分離する分離工程と、
該分離工程で分離した各係数の前記上位ビット部を符号化する上位ビット符号化工程と、
前記分離工程で分離した各係数の前記下位ビット部を符号化する下位ビット符号化工程と、
前記上位ビット符号化工程、前記下位ビット符号化工程それぞれで得られた符号化データから、着目画素ブロックの符号化データを生成し、出力する出力工程と
を有することを特徴とする画像符号化装置の制御方法。
【請求項６】
コンピュータに読み込ませ実行させることで、前記コンピュータを請求項１乃至４のいずれか１項に記載の画像符号化装置として機能させることを特徴とするコンピュータプログラム。
【請求項７】
請求項６に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像符号化技術、特に、画像データを周波数空間のデータへと変換し、得られた変換係数を符号化することで符号化画像データを生成する技術に関するものである。
【背景技術】
【０００２】
従来、画像の符号化手法として、画像データを周波数空間のデータへと変換して符号化を行う変換符号化が用いられる。静止画符号化の国際標準方式として勧告されるＪＰＥＧは周波数空間への変換手法としてＤＣＴを利用した変換符号化の代表例である。以下、ＪＰＥＧの符号化処理過程を簡単に述べる。
【０００３】
符号化対象の画像データは、矩形領域のブロックに分割され、各ブロックに離散コサイン変換が適用される。変換によって得られた係数を、所望の画質レベル、符号量に応じて量子化し、量子化後の変換係数をエントロピ符号化する。ＪＰＥＧ  Ｂａｓｅｌｉｎｅでは、係数のエントロピ符号化手法としてハフマン符号化を採用している。８×８＝６４個の周波数帯域のデータは１個のＤＣ成分と、６３個のＡＣ成分に分けて符号化される。ＤＣ成分は直前のブロックとの差分値として符号化し、ＡＣ成分はゼロの連続数（ゼロラン）と非ゼロの係数値の組み合わせによりハフマン符号化を行う。
【０００４】
ＪＰＥＧ Ｂａｓｅｌｉｎｅに見られるように、ゼロの連続数を符号化する符号化手法において、符号化が効率的に行われるためには、０となる係数がある程度存在しなければならない。極端な例を挙げるならば、６３個のＡＣ係数の全てが非ゼロであるような場合には、ラン０と非ゼロ係数値を組み合わせて符号化することになり、効率的とは言えない。
【０００５】
例えば、量子化ステップ値を小さく設定して、ＪＰＥＧ符号化を行う場合、符号化を効率的に機能させるために、各係数を上位ビット部と下位ビット部に分離して、上位ビット部に対してのみランレングス符号化を適用するといった手法が提案されている。
【０００６】
このような従来技術を用いた画像処理装置、画像処理方法の一例が特許文献１に開示されている。
【特許文献１】特開２０００−１３７９７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述の上位ビット部、下位ビット部を分離する符号化においては、どのビット位置で係数を分離するかが圧縮性能を決定付ける重要な要因となる。境界ビット位置を低く設定した場合には、ゼロランの長さが短くなり、ランレングス符号化が有効に機能しない。一方で、境界ビット位置を高く設定しすぎた場合には、下位ビット部に冗長なデータが多く含まれ、下位ビット部の符号化性能が全体の性能を左右する。例えば、先に示した特許文献１では、下位ビット部を非圧縮としているが、このような場合には高い符号化性能を実現することができなくなる。
【０００８】
本願発明は、上述の問題点に鑑みてなされたものであり、画素ブロックを単位に周波数変換、量子化を行なう画像符号化処理において、量子化後の係数を、より効率良く符号化する技術を提供しようとするものである。
【課題を解決するための手段】
【０００９】
かかる課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
多値画像データから画素ブロックを単位に、周波数変換、量子化処理を行ない、当該量子化処理で得られた多値の各係数を符号化する画像符号化装置であって、
前記各係数についての、最上位から最下位ビットに向かって最初に“１”となるビット位置から最下位ビットまでの有効ビット数を検出し、各有効ビット数の出現回数をカウントするカウント手段と、
有効ビット数Ｂの出現回数をＮ（Ｂ）と定義し、出現回数が１以上の最大の有効ビット数をｂmaxと定義し、変数ｂ＝０、１、２…に対する次式の合算関数：
Ｓ（ｂmax−ｂ）＝ΣＮ（ｂmax−ｉ）  （ｉ＝０、１、…、ｂ）
において、予め設定された閾値Ｔｈとの関係が、
Ｓ（ｂmax−ｂ）＞Ｔｈ
を満たす最大整数ｂを求め、当該最大整数ｂに基づいて、境界ビット位置を決定する境界ビット位置決定手段と、
前記各係数の値を、前記境界ビット位置決定手段で算出した境界ビット位置を境界にして、上位ビット部、下位ビット部とに分離する分離手段と、
該分離手段で分離した各係数の前記上位ビット部を符号化する上位ビット符号化手段と、
前記分離手段で分離した各係数の前記下位ビット部を符号化する下位ビット符号化手段と、
前記上位ビット符号化手段、前記下位ビット符号化手段それぞれで得られた符号化データから、着目画素ブロックの符号化データを生成し、出力する出力手段とを備える。
【発明の効果】
【００１０】
本発明によれば、画素ブロックを単位に周波数変換、量子化を行なう画像符号化処理において、量子化後の係数を、より効率良く符号化する技術を提供できる。
【発明を実施するための最良の形態】
【００１１】
以下添付図面に従って本発明に係る実施形態を詳細に説明する。
【００１２】
［第１の実施形態］
図１は、実施形態における画像符号化装置のブロック構成図である。
【００１３】
本実施形態の画像符号化装置は、符号化対象となる画像データを外部から入力し、画素ブロックを単位に周波数変換（ＤＣＴ）等の系列変換、量子化を行なう。そして、着目画素ブロックから得られる、量子化後の各係数を上位ビット部と下位ビット部に分離して符号化するものである。なお、画像データの入力源は、イメージスキャナとするが、画像データをファイルとして格納している記憶媒体等であっても良く、その種類は問わない。
【００１４】
符号化の対象となる画像データは輝度成分のみのモノクロ多値画像データとし、輝度成分は８ビット（０乃至２５５の２５６階調）として説明する。但し、これは実施形態の説明を簡単なものとするためであって、１画素が複数成分（例えば、ＲＧＢやＣＭＹＫ）でも構わず、その色空間の種類は問わないし、１成分のビット数も８ビットに限らず、８ビットを超えるビット数でも構わない。また、更に、符号化対象の画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成され、説明簡易化のため、Ｗ、Ｈは８の倍数であるとして説明する。
【００１５】
以下、図１における画像符号化装置における符号化処理を説明する。
【００１６】
まず、画像入力部１０１から符号化対象となる画像データが順に入力される。画素データの入力順序はラスタースキャン順とする。１画素は８ビットで表現される０から２５５までの非負の整数値とする。画像の左上隅を座標（０，０）とし、水平右方向の画素位置ｘ、垂直下方向の画素位置ｙにある画素の値をＰ（ｘ，ｙ）と表すこととする。例えば、位置（ｘ、ｙ）＝（３，４）にある画素が、１２８という輝度値を持つ場合、Ｐ（３，４）＝１２８と表現する。また、以下の説明では、位置（ｘ、ｙ）の“画素”を表現する場合にも“Ｐ（ｘ，ｙ）”という表現を用いることとする。
【００１７】
ブロック分割部１０２は画像入力部１０１から入力される画素データを適宜不図示の内部バッファに格納し、８×８画素の大きさの矩形ブロックを単位として順番に出力する。画像の左上端のブロックを番号０とし、ラスタースキャンの順序で、昇順に識別番号を付与し、この順番で矩形ブロックデータを取り出して出力する。
【００１８】
系列変換部１０３では、ブロック分割部１０２から出力される矩形ブロックデータを周波数変換する。ここでは、系列変換処理として、ＪＰＥＧ（ＩＳＯ／ＩＥＣ  １５４４４−１）で用いられる離散コサイン変換を適用し、ＤＣＴ係数データへと変換する。本発明の別の実施形態では、ブロックの歪を軽減させるために、ブロックを重複させながら変換処理を行う、重複直交変換や重複双直交変換などを用いて周波数空間への変換を行うことができる。なお、ＪＰＥＧの離散コサイン変換処理については、以下の国際標準勧告書等に記載されているので、ここでは説明を割愛する。
ITU-T Recommendation T.81 | ISO/IEC 10918-1:1994, Information technology - Digital compression and coding of continuous-tone still images: Requirements and guidelines.
なお、ＪＰＥＧの場合と同様に、離散コサイン変換の適用に先立ち、中間値を減算するレベルシフト処理を行うものとする。本実施形態では、入力する符号化対象の画像データの各画素は、０乃至２５５の範囲の８ビットのデータとなっているので、画素値Ｐ（ｘ，ｙ）から１２８を減じる。
【００１９】
係数量子化部１０４は系列変換部１０３により得られたＤＣＴ係数データを要求される画質レベルに応じて量子化処理を実行し、量子化後の各係数値（実施形態の場合には６４個）を係数バッファ１０５へと格納する。なお、以降、特に量子化の有無を区別する必要がない場合、係数バッファ１０５に格納されている量子化された係数値を単に、係数値と記す。また、実施形態では、１個の係数値は、９ビット（うち１ビットは正負の符号）で表わされるものとして説明するが、精度を向上させるため１０ビット以上であっても構わない。
【００２０】
係数バッファ１０５は１矩形ブロック分の係数値（実施形態の場合には６４個）を格納する。
【００２１】
境界ビット位置決定部１１６は、係数バッファ１０５に格納される１矩形ブロック分の各係数値について、後述する有効ビット数の分布を調べ、後段の係数符号化部１１７で用いる境界ビット位置Ｂを決定する。
【００２２】
境界ビット位置決定部１１６は、有効ビット判定部１０６、頻度テーブル生成部１０７、頻度テーブルバッファ１０８、境界ビット選択部１０９を備える。
【００２３】
有効ビット判定部１０６は係数バッファ１０５に格納される、着目する矩形ブロック内の各係数値Ｃｎを順番に読み出し、その有効ビット数Ｂ（Ｃｎ）を求める。有効ビット数とは係数値Ｃｎの絶対値を自然２進数表記した場合に、上位から下位ビットに探索した際に最初に“１”が出現するビット位置を示す。例えば、着目する係数値Ｃｎが“−５”である場合、その絶対値“５”について自然２進表記すると、“０…０１０１”となる。最上位の“１”は下位から３桁目であるので、Ｂ(５)＝３となる。言い換えれば、絶対値が“５”の係数値の有効なビット数は、最下位ビットから３ビットであると言うことができる。なお、Ｃｎ＝０である場合、“１”のビットは存在しないので、有効ビット数Ｂ（Ｃｎ）は０となる。要するに、有効ビット数Ｂ（Ｃｎ）は、係数の絶対値｜Ｃｎ｜に対して｜Ｃｎ｜＜２Pの条件を満たす最小の正の整数値Ｐであると言える。
【００２４】
頻度テーブル生成部１０７は有効ビット数判定部１０６から出力されるＢ（Ｃｎ）について、頻度テーブルバッファ１０８に保持する発生頻度テーブルを更新する。頻度テーブルバッファ１０８は、有効ビット数０乃至８それぞれの出現頻度Ｎ（０）乃至Ｎ（８）を格納する容量を有する。頻度テーブルバッファ１０８は、１つの矩形ブロックの頻度を求める際に、“０”で初期化されるものとする。そして、有効ビット判定部１０６が着目係数値Ｃｎの有効ビット数Ｂ（Ｃｎ）を決定した場合、頻度テーブル生成部１０７は頻度テーブルバッファ１０８内のＮ（Ｂ（Ｃｎ））を“１”だけ増加させる。つまり、頻度テーブル生成部１０７は、有効ビット判定部１０６によって１つの係数値の有効ビットを判定する度に、頻度テーブルバッファ１０８を更新する。
【００２５】
図４は、上記のようにして求めた、着目ブロック内の全係数値の有効ビットの出現頻度をグラフにして示した例を示している。図４では、有効ビット数が０乃至７が存在し、有効ビット数８の出現回数は０回であった例を示している。
【００２６】
さて、着目する矩形ブロックのすべての係数値について、有効ビット数の判定、頻度テーブルの更新処理が行われると、境界ビット選択部１０９は、着目矩形ブロックにおける境界ビットＢの選択を行なう。具体的には、次の通りである。
【００２７】
境界ビット選択部１０９は、まず、頻度テーブルバッファ１０８に格納される各有効ビット数の出現回数Ｎ（ｂ）（ｂは有効ビット数を表す任意の整数値）を、有効ビット数の最大値から最小値に向けて累積加算することで、図５のような累積頻度のテーブルＳ（ｂ）へと変換を行う。着目する矩形ブロックにおいて、出現回数が１以上の有効ビット数の最大値をｂmax（図４の場合にはｂmax＝７）とするとき、境界ビット選択部１０９は、変数ｂ＝ｂmax，ｂmax−１，ｂmax−２…と更新して、次式で示される累積頻度テーブルＳ（ｂ）を求める。
Ｓ（ｂ）＝Ｎ（ｂ）                ｂ＝ｂmaxの場合
Ｓ（ｂ）＝Ｎ（ｂ）＋Ｓ（ｂ＋１）  ｂ≠ｂmaxの場合
【００２８】
上記は、逆に変数ｂ＝０、１、２、…、ｂmaxと更新する場合、合算関数Σを用いて次のように表わすこともできる。
Ｓ（ｂmax−ｂ）＝ΣＮ（ｂmax−ｉ）    （ｉ＝０，１，…，ｂ）
【００２９】
累積頻度テーブルＳ（ｂ）は、要するに、ｂ≠０の場合、絶対値が２＾ｂ以上となる係数値の個数を表すことを示している。また、Ｓ（０）は着目矩形ブロック内の全係数値の個数に等しい。
【００３０】
累積頻度テーブルＳ（ｂ）を得た後、境界ビット選択部１０９は、有効ビット数の最大値から最小値に向けて、すなわち、降順にＳ（ｂ）の値を調べ、予め設定された閾値Ｔｈを超える最大整数ｂを探索する。そして、境界ビット選択部１０９は、得られたｂを境界ビット位置Ｂとして出力する。なお、詳細は後述する説明から明らかになるが、Ｓ（１）が閾値Ｔｈを超えない場合、着目矩形ブロック内の全係数についての分離処理は行われず、全てランレングス符号化されることになる。
【００３１】
ここで閾値Ｔｈは係数値の総数（実施形態の場合、矩形ブロックは８×８画素のサイズなので、係数値の総数は６４個）に対して、所定の比率となるように設定する。この閾値Ｔｈはユーザが適宜設定もしくは選択可能にすることができるものとするが、統計的に見ると、この閾値Ｔｈは矩形ブロック内の全係数の個数の１／４乃至１／３が適当である。例えば、比率１／３を採用するなら、閾値Ｔｈは“２１”（≒６４／３）である。
【００３２】
後述するが、後段の係数符号化部１１７における着目矩形ブロック内の各係数値の符号化処理においては、係数値を境界ビットＢで上位と下位に分離し、上位ビット部に対してゼロの連続数の符号化、即ち、ランレングス符号化を適用する。従って、ここでの閾値Ｔｈの役割は、係数値の上位ビット部が非ゼロの係数とゼロの係数値の比を調整するためのものであり、ランレングス符号化を有効に機能させることを狙いとして設定されるものであると言える。図５に示した例では、“５”が閾値Ｔｈを超える最大のｂにあたり、境界ビット位置として“５”が出力される。
【００３３】
境界ビット位置決定部１１６により境界ビット位置Ｂが決定されると、係数符号化部１１７は、係数バッファ１０５に格納される各係数値を、予め設定された順番に従って、読み出して符号化処理を行う。
【００３４】
つまり、係数バッファ１０５に格納された係数値の読み出し（スキャン）は２度行われる。最初のスキャンは、既に説明した境界ビット位置決定部１１６による境界ビット位置Ｂの決定処理のためである。そして、２回目のスキャンでは、以下に説明する、係数符号化部１１７による係数値の符号化処理のためである。
【００３５】
本実施形態においては、１回目のスキャンのスキャン順は、どのような順序でも構わない。一方、２回めの係数符号化部１１７によるスキャンは、符号化効率の観点からジグザグスキャン順とするが、必ずしもこれに限らない。詳細については後述するが、後段の係数符号化部１１７において、係数の上位ビット部をゼロの連続数と非ゼロの係数値の組み合わせにより符号化する。この際にゼロの連続数が長くなるように考えたスキャン方法であれば良く、例えば、いくつかのスキャンパターンから適切な方法を選択するようにしても良い。また、過去に符号化したブロックにおける係数の分布を参照して係数のパワーの大きいものから小さいものへと並ぶように動的にスキャン順序を変えるなどしても構わない。
【００３６】
本実施形態における係数符号化部１１７は、上位／下位ビット分離部１１０、上位ビット符号化部１１１、下位ビット符号化部１１２、符号バッファ１１３から構成される。
【００３７】
上位／下位ビット分離部１１０は、係数バッファ１０５から読出した着目する係数値Ｃｎについて、その符号絶対値表現における下位Ｂビットを取り除いて得られる上位ビット部と、境界ビット位置以下の下位Ｂビット部とに分離する。但し、正負の符号ビットは処理対象外とする。より具体的には、境界ビット選択部１０９は、着目係数値Ｃｎの、上位ビット部Ｕｎ（＝Ｃｎ＞＞Ｂ）と、下位ビット部Ｌｎ（＝｜Ｃｎ｜＆（（１＜＜Ｂ）−１））を求める。ここでＹ＞＞Ｘは、値ＹをＸビットだけ下位方向にシフトすることを示し、Ｙ＜＜Ｘは値ＹをＸビットだけ上位方向にシフトすることを示している。また、｜Ｙ｜は値Ｙの絶対値を、Ｘ＆Ｙは値Ｘと値Ｙとのビット単位の論理積（ＡＮＤ）を示す。
【００３８】
上位／下位ビット分離部１１０は、着目係数値Ｃｎの上記ビット部Ｕｎを上位ビット符号化部１１１に出力し、下位ビット部Ｌｎを下位ビット符号化部１１２へと出力する。
【００３９】
なお、上位ビット部Ｕｎの値が“０”である係数Ｃｎについては、係数Ｃｎの正負を表す符号も下位ビット符号化部１１２へと引き渡されるものとする。
【００４０】
図６に、係数値Ｃｎの一例として“−４１、−７、２８、−１、…”が入力され、境界ビット位置Ｂ＝４で上位ビット部Ｕｎと下位ビット部Ｌｎに分離した例を示す。
【００４１】
図示の場合、上位／下位ビット分離部１１０は、正負符号の１ビットを含む６４個の上位ビット部Ｕｎを上位ビット符号化部１１１に出力する。
【００４２】
上位ビット符号化部１１１は、入力される上位ビット部Ｕｎの正負符号ビットを除外した４ビットで表わされる値が“０”の場合、ここではその正負符号ビットの符号化を行なわない。上位ビット部Ｕｎにおいて、正負符号ビットを除外した４ビットで表わされる値が“０”となるのは、図６の場合係数値Ｃｎ＝“−７”、“−１”である。また、上位ビット部Ｕｎの正負符号ビットを除く、４ビットで表わされる値が非“０”の場合、その正負符号ビットを含む上位ビット部Ｕｎがそのままランレングス符号化対象となる。
【００４３】
従って、図６の場合、上位ビット符号化部１１１は、１０進数表記の多値データ“−２”、“０”、“１”、“０”…の順に、ランレングス符号化を行なうことになる。この結果、上位ビット部が“０”となる確率が高くなり、符号化効率が高めることができる。
【００４４】
なお、１つの矩形ブロックからは、１個のＤＣ係数と、６３個のＡＣ係数が得られる。そして、実施形態における上位ビット符号化部１１１の符号化はＪＰＥＧのＢａｓｅｌｉｎｅでのＤＣ，ＡＣ係数の符号化と同じ方法を用いる。すなわち、着目矩形ブロックのＤＣ係数の上位ビット部Ｕｎを符号化する場合には、直前のブロック（既に符号化済みのブロックでもある）のＤＣ係数の上位ビット部Ｕｎを予測値として用いる。そして、着目ブロックの上位ビット部Ｕｎと予測値との差分を算出し、その差分に基づきハフマン符号化を行う。そして、ＡＣ係数の上位ビット部Ｕｎについては、ゼロの連続数と非ゼロの係数を組み合わせてハフマン符号化を行う。ブロックの最後がゼロの連続で終わる場合にはＥＯＢ（Ｅｎｄ Ｏｆ Ｂｌｏｃｋ）を表す特殊符号を用いる点についてもＪＰＥＧ Ｂａｓｅｌｉｎｅと同様である。
【００４５】
一方、上位／下位ビット分離部１１０は、着目矩形ブロックの６４個の下位ビット部Ｌｎを下位ビット符号化部１１２に出力する。ただし、先に説明したように、上位／下位ビット分離部１１０は、上位ビット部Ｕｎの正負符号ビットを除く４ビットの値が“０”である係数Ｃｎについては、その正負符号ビットを下位ビット部Ｌｎに付加して下位ビット符号化部１１２に出力する。
【００４６】
正負符号ビットを除く上位ビット部Ｕｎの値が“０”となるのは、図６の例では、係数値“−７”と、“−１”である。そこで、正負符号ビットの付加位置は、下位ビット部Ｌｎの上位から下位に向かって最初に“１”が出現する位置とする。図６の場合には、斜線で示される位置が正負ビットを挿入する位置になる。
【００４７】
下位ビット符号化部１１２は上位／下位ビット分離部１１０から出力された下位ビット部Ｌｎの符号化を行う。上位ビット部Ｕｎに対し、下位ビット部Ｌｎは一般に圧縮しにくいデータであるので、本実施形態の下位ビット符号化部１１２では下位ビット部を非圧縮で出力する（但し、圧縮性能を追求する場合には算術符号などを適用しても良い）。非圧縮であるので、基本的には入力データがそのまま符号化データとなるが、画質への影響度に応じてビットデータが配置されるように、言い換えれば、復号装置がプログレッシブ再生できるようにするため、ビットプレーン順に並び替えて出力する。
【００４８】
図６の場合、下位ビット符号化部１１２は、入力した下位ビット部Ｌｎを不図示の内部バッファに格納し、各下位ビット部Ｌｎの最上位のビット桁（Ｂ番目の桁）で構成されるビットプレーンを出力する。この処理を最下位のビット桁（１番目の桁）まで繰り返す。
【００４９】
図６に示した係数値列“−４１、−７、２８、−１、…”の場合（境界ビット位置Ｂ＝４）における、下位ビット符号化部１１２が出力するデータの例を、図７に示す。
【００５０】
下位ビット部Ｌｎの最初に出力されるプレーン（同一ビット位置のビット情報）はＢ桁のビットプレーン“１０１０…”となる。この中の“１”に対応するのは、係数値“−４１”、“２８”である。係数値“−４１”、“２８”の符号ビットを除く上位ビット部Ｕｎが表わす値は非０であるので、正負符号ビットは挿入されない。
【００５１】
次のＢ−１桁のビットプレーンに着目すると、係数値“−７”を表わす最初の“１”のビットが出現する（図６参照）。また、係数値“−７”の正負符号ビットを除く上位ビット部Ｕｎの値は“０”となる。それ故、図示の如く、係数値“−７”を表わす最初の“１”に後続する位置に、正負の符号ビットを挿入する。以下、Ｂ−２桁のビットプレーン、Ｂ−３桁のビットプレーンを出力していく。Ｂ−３桁のビットプレーンでは、係数値“−１”を表わす最初の“１”が出現するので、それに後続して正負符号ビットが挿入される。
【００５２】
符号化バッファ１１３には、上位ビット符号化部１１１、下位ビット符号化部１１２から出力される矩形ブロックを単位とする符号化データが格納される。
【００５３】
符号列形成部１１４は符号バッファ１１３に格納される、着目する矩形ブロックの符号化データを読み出し、符号化形成部１１４が内部に備えるバッファに格納しながら、所定の形式の符号化データを生成し、符号出力部１１５に出力する。符号出力部１１５は、符号化対象の画像データを入力する際に、出力先（例えばハードディスク装置）にファイルヘッダを生成し、それに後続して、符号列形成部１１４で生成された符号列を出力し、１個の符号化データファイルを生成することになる。
【００５４】
図８に本実施形態の画像符号化装置から出力される符号化データファイルの構造を示す。ファイルヘッダ符号列には画像の水平方向画素数、垂直方向画素数や、色成分の数（実施形態でモノクロ画像の例であるので色成分の数は１つ）、各画素のビット数など、復号に必要な各種情報がヘッダとして付与される。このヘッダには全ての矩形ブロックについての境界ビットＢの情報が含まれる。従って、復号装置はこのヘッダを解析すれば、各ブロックの境界ビット位置を得ることができる。ファイルヘッダの後に、画像の全矩形ブロックについて上位ビット部Ｕｎの符号化データが配置され、その後に、下位ビット符号化データが並ぶ。図中、Ｎはブロックの総数を表し、Ｌは全ブロックについて探索した境界ビット位置Ｂの最大値を表す。上位ビット符号化データは、矩形ブロックを単位とするラスタースキャンの順番で、各矩形ブロックの上位ビット部符号化データを連結して構成される。下位ビット符号化データは各矩形ブロックの下位ビット部符号化データをビットプレーン順に配置して構成される。ビットプレーンｉはラスタースキャンの順番で各ブロックのビットプレーンｉのデータを集めて構成されるが、境界ビットＢ＜ｉとなるブロックからのデータは含まれないため、必ずしもすべてのブロックからデータが集められるわけではない。
【００５５】
図８に示した符号の構造は、あくまでもその一例であり、境界ビット位置の情報と、少なくとも一部の上位ビット符号化データが含まれるものであれば良い。また、図８は、複数のブロックで構成されるマクロブロック、又は、そのマクロブロックを複数包含するタイルのデータ構造としても構わない。
【００５６】
本実施形態の画像符号化装置で生成した符号化データは、上位ビット部を境界ビット位置Ｂで表されるビット数分上位にシフトして、必要な画質レベルに応じて下位ビット部を復元し、符号化と逆の過程で復号することにより、再生できる。
【００５７】
以上のように、本実施形態の画像符号化装置では、複数の画素で構成される画素ブロック（実施形態では８×８画素のサイズ）で、系列変換、量子化した後の係数の有効ビット数についての頻度分布を求める。そして、上位ビット部Ｕｎが非ゼロとなる個数が矩形ブロック全体の係数の数に対して所定の比率となる、境界ビットを求めた。これを用いて係数を上位ビット部と下位ビット部とに分離し、上位ビット部に対してゼロの連続数と非ゼロの係数を組み合わせた符号化を行った。これにより、ランレングス符号化を有効に機能させることができ、符号化の効率を向上することができる。
【００５８】
［第１の実施形態の変形例］
上記第１の実施形態と同等の処理を、コンピュータプログラムによって実現する例を第１の実施形態の変形例として以下に説明する。
【００５９】
図１３は、本変形例における情報処理装置（例えばパーソナルコンピュータ）のブロック構成図である。
【００６０】
図中、１４０１はＣＰＵで、ＲＡＭ１４０２やＲＯＭ１４０３に記憶されているプログラムやデータを用いて本装置全体の制御を行うと共に、後述する画像符号化処理、復号処理を実行する。１４０２はＲＡＭで、外部記憶装置１４０７や記憶媒体ドライブ１４０８、若しくはＩ／Ｆ１４０９を介して外部装置からダウンロードされたプログラムやデータを記憶する為のエリアを備える。また、ＲＡＭ１４０２は、ＣＰＵ１４０１が各種の処理を実行する際に使用するワークエリアも備える。１４０３はＲＯＭで、ブートプログラムや本装置の設定プログラムやデータを格納する。１４０４、１４０５は夫々キーボード、マウスで、ＣＰＵ１４０１に対して各種の指示を入力することができる。
【００６１】
１４０６は表示装置で、ＣＲＴや液晶画面などにより構成されており、画像や文字などの情報を表示することができる。１４０７はハードディスクドライブ装置等の大容量の外部記憶装置である。この外部記憶装置１４０７には、ＯＳ（オペレーティングシステム）や後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象画像の符号化データなどがファイルとして保存されている。また、ＣＰＵ１４０１は、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードし、実行することになる。
【００６２】
１４０８は記憶媒体ドライブで、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記憶媒体に記録されたプログラムやデータを読み出してＲＡＭ１４０２や外部記憶装置１４０７に出力するものである。なお、この記憶媒体に後述する画像符号化、復号処理の為のプログラム、符号化対象の画像データ、復号対象の画像の符号化データなどを記録しておいても良い。この場合、記憶媒体ドライブ１４０８は、ＣＰＵ１４０１による制御によって、これらのプログラムやデータをＲＡＭ１４０２上の所定のエリアにロードする。
【００６３】
１４０９はＩ／Ｆで、このＩ／Ｆ１４０９によって外部装置を本装置に接続し、本装置と外部装置との間でデータ通信を可能にするものである。例えは符号化対象の画像データや、復号対象の画像の符号化データなどを本装置のＲＡＭ１４０２や外部記憶装置１４０７、あるいは記憶媒体ドライブ１４０８に入力することもできる。１４１０は上述の各部を繋ぐバスである。
【００６４】
上記構成において、本装置の電源がＯＮになると、ＣＰＵ１４０１はＲＯＭ１４０３のブートプログラムに従って、外部記憶装置１４０７からＯＳをＲＡＭ１４０２にロードする。この結果、キーボード１４０４、マウス１４０５の入力が可能となり、表示装置１４０６にＧＵＩを表示することが可能になる。ユーザが、キーボード１４０４やマウス１４０５を操作し、外部記憶装置１４０７に格納された画像符号化処理用アプリケーションプログラムの起動の指示を行なうと、ＣＰＵ１４０１はそのプログラムをＲＡＭ１４０２にロードし、実行する。これにより、本装置が画像符号化装置として機能することになる。
【００６５】
以下、ＣＰＵ１４０１が実行する画像処理用のアプリケーションプログラムの処理手順を図２のフローチャートに従って説明する。基本的に、このプログラムは、図１に示す各構成要素に相当する関数を備えることになる。ただし、図１における係数バッファ１０５、頻度テーブルバッファ１０８、符号バッファ１１３の各領域はＲＡＭ１４０２内に予め確保することになる。
【００６６】
まず、ステップＳ２００において、符号化を開始する前の初期化処理が行われる。ここでは、処理する画素ブロックの番号を保持する変数ｉを０に初期化する。
【００６７】
次に、ステップＳ２０１においてＩ／Ｆ１４０９によって接続される外部装置から符号化対象の画像データを順次入力し、ＲＡＭ１４０２に格納しながら、ｉ番目のブロックデータを形成する（画像入力部１０１、ブロック分割部１０１の処理に相当）。このとき、画像データのヘッダを参照することで、その画像に含まれる画素ブロックの総数を算出しておく。
【００６８】
次に、ステップＳ２０２において、着目する画素ブロックＭＢ（ｉ）について離散コサイン変換等の系列変換処理を施し、対応するＤＣＴ係数データ（ブロック係数値）をＲＡＭ１４０２内に格納する（系列変換部１０３の処理に相当）。
【００６９】
続いて、ステップＳ２０３で、ＤＣＴ係数データの量子化を行い、ＲＡＭ１４０２内に係数値として格納する（係数量子化部１０４の処理に相当）。
【００７０】
次に、ステップＳ２０４において、着目するブロックＭＢ(ｉ)の各係数値を参照し、その境界ビット位置Ｂを求める（境界ビット位置決定部１１６の処理に相当）。
【００７１】
図３にステップＳ２０４における境界ビット位置Ｂの決定について、処理フローを示す。
【００７２】
以下、図３を用いて着目するブロックＭＢ（ｉ）の係数値の境界ビット位置Ｂを決定する処理の流れについて説明する。
【００７３】
まず、ステップＳ３０１で、頻度テーブルの初期化と、着目するブロックＭＢ（ｉ）の内部の係数を識別する番号ｎの初期化を行う。具体的には、全ての有効ビット数について出現回数を０に初期設定し、係数番号ｎに０を設定する。
【００７４】
次に、ステップＳ３０２において、番号ｎで表される係数ＣｎをＲＡＭ１４０２から取得する。
【００７５】
続くステップＳ３０３では、着目する係数Ｃｎについて有効ビット数Ｂ（Ｃｎ）を求める（有効ビット数判定部１０６の処理に相当）。
【００７６】
ステップＳ３０４ではステップＳ３０３で得た有効ビット数Ｂ（Ｃｎ）について、対応する頻度テーブルＮ（Ｂ（Ｃｎ））の値をインクリメントして更新する（頻度テーブル生成部１０７の処理に相当）。
【００７７】
ステップＳ３０５では着目する係数Ｃｎがブロックの最後の係数であるか否かを判定し、最後の係数である場合（yes）にはステップＳ３０７へと処理を移し、そうでない場合（no）にはステップＳ３０６に移る。なお、画素ブロックのサイズが８×８画素のサイズとしているので、係数Ｃｎがブロックの最後の係数であるか否かは変数ｎと“６４”とを比較すれば判定できる。
【００７８】
係数Ｃｎがブロック内の最後の係数でない場合、次の係数へと処理の対象を移すために、ステップＳ３０６でｎの値をインクリメントして更新する。ステップＳ３０６の後は、ステップＳ３０２に戻り、新たに着目する係数Ｃｎについて処理を行う。
【００７９】
一方、ステップＳ３０５の判定において、Ｃｎがブロックの最後の係数であった場合、ステップＳ３０７では頻度テーブルＮ（ｂ）（ｂは有効ビット数を表す任意の整数）から累積頻度テーブルＳ（ｂ）へと変換を行う。これは境界ビット選択部１０９の処理の一部に相当する。
【００８０】
次に、ステップＳ３０８でステップＳ３０７で生成した累積頻度テーブルＳ（ｂ）のｂについて、有効ビットの最大値から最小値に向かう順に探索し、境界ビット位置Ｂとして選択する（境界ビット選択部１０９の処理の一部に相当）。
【００８１】
以上の処理により、着目するブロックＭＢ（ｉ）の境界ビット位置Ｂが決定される。
【００８２】
図２の説明に戻る。上記のようにして、着目するブロックＭＢ（ｉ）の境界ビット位置Ｂが決定されると、処理はステップＳ２０５に進み、着目するブロックＭＢ（ｉ）の係数値を上位ビット部Ｕｎと下位ビット部Ｌｎに分離し、それぞれ符号化を行う。これは係数符号化部１１７の処理に相当する。
【００８３】
ステップＳ２０６では、処理したブロックが画像の最後のブロックか否かを判定し、最後のブロックである場合にはステップＳ２０８へと処理を移し、そうでない場合にはステップＳ２０７へと処理を移す。
【００８４】
ステップＳ２０７では、処理対象のブロックを次のブロックへと移すため、変数ｉに１を加えて更新し、次のブロックについてステップＳ２０１から符号化処理を継続する。
【００８５】
一方、画像の全てのブロックについて処理が終了した場合、処理はステップＳ２０８に進み、最終的な符号化データを生成して、Ｉ／Ｆ１４０９を解して外部装置へと出力する（符号列形成部１１４、符号出力部１１５の処理に相当）。
【００８６】
以上説明したように本変形例によっても、第１の実施形態と同様の作用効果を奏することが可能となるのは明らかであろう。すなわち、複数の画素で構成されるブロックを単位に、量子化後の係数値の有効ビット数の頻度分布を求め、上位ビット部が非ゼロとなる係数が所望の比率となる適切な境界ビット位置を決定する。この結果、符号化の効率を向上することができる。
【００８７】
［第２の実施形態］
上記第１の実施形態及びその変形例では、ブロック毎に、量子化後の係数値の上位ビット部がゼロとなる係数の個数が、所定の比率に近くなるように、境界ビットを設定して符号化を行った。しかしながら、この境界ビット位置の選択はある程度の効率は期待できるが、必ずしも最小符号量となることを約束するものとは言えない。なぜなら、複数の非０の上位ビット部Ｕｎが連続して位置するのではなく、離散した位置にある場合、ランレングス符号化の効率を上げることができないからである。
【００８８】
そこで、本第２の実施形態では、境界ビット決定部から出力される境界ビット位置Ｂと、その近傍の境界ビット位置Ｂ−１で、符号化処理を行ない、符号量の少ない方を選択する例について説明する。
【００８９】
なお、本第２の実施形態でも、符号化対象の画像データは、説明を簡単にするためにモノクロ画像データとするが、ＲＧＢ画像データや、ＣＭＹＫカラー画像データに適用しても良い。また、画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成されるものとする。また、処理単位の矩形ブロックのサイズも８×８画素サイズであるものとして説明する。
本第２の実施形態に係る画像符号化装置のブロック図を図９に示す。図９と図１との違いは、図１における係数符号化部１１７が図９の係数符号化部９００で置き換わった点であり、これ以外は同じであるので同参照番号を付した。従って、図１と同じ参照番号を付した要素についてはその説明は省略する。
【００９０】
係数符号化部９００は、上位ビット／下位ビット分離部９０１と、２つの上位ビット符号化部９０２、９０３と、下位ビット符号化部９０４、符号バッファ９０７、及び、符号選択部９０６を有する。第１の実施形態で説明した係数符号化部１１７と同じく、係数符号化部９００は、境界ビット位置決定部１１６からの境界ビット位置Ｂと、係数バッファ１０５からの矩形ブロックの係数データＣｎとを入力する。
【００９１】
上位／下位ビット分離部９０１では、着目する係数データＣｎについて、その符号絶対値表現における下位Ｂビットを取り除いて得られる第１の上位ビット部と、下位Ｂ−１ビットを取り除いて得られる第２の上位ビット部と、下位Ｂビット部とに分離する。
【００９２】
以下の説明では、第１の上位ビット部をＵ１ｎ、第２の上位ビット部をＵ２ｎと表すとする。Ｕ１ｎ，Ｕ２ｎ，Ｌｎを式で示せば次の通りである。
Ｕ１ｎ＝Ｃｎ＞＞Ｂ
Ｕ２ｎ＝Ｃｎ＞＞（Ｂ−１）
Ｌｎ  ＝｜Ｃｎ｜＆（（１＜＜Ｂ）−１）
【００９３】
上位／下位ビット分離部９０１は、第１の上位ビット部Ｕ１ｎを上位ビット符号化部９０２に出力し、第２の上位ビット部Ｕ２ｎを上位ビット符号化部９０３に出力する。また、上位／下位ビット分離部９０１は、下位ビット部Ｌｎを下位ビット符号化部９０４へと出力する。なお、正負符号ビットを除く上位ビット部Ｕ１ｎで表わされる値が０である係数Ｃｎについては、係数Ｃｎの正負を表す符号を下位ビット符号化部９０４へと引き渡されるものとする。この原理は第１の実施形態と同じである。
【００９４】
上位ビット符号化部９０２は、着目矩形ブロック内の６４個の第１の上位ビット部Ｕ１ｎを入力し、符号化を行なう。また、上位ビット符号化部９０３は、着目矩形ブロック内の６４個の第２の上位ビット部Ｕ２ｎを入力し、符号化を行なう。これら２つの符号化部は、第１の実施形態における上位ビット符号化部１１１と同じく、ＪＰＥＧ ＢａｓｅｌｉｎｅにおけるＤＣ、ＡＣ係数の符号化と同じ方法を用いるものとする。
【００９５】
上位ビット符号化部９０２からは第１の上位ビット部Ｕ１ｎの符号化データが符号バッファ９０５に出力される。また、上位ビット符号化部９０３からは第２の上位ビット部Ｕ２ｎの符号化データが符号バッファ９０５に出力される。
【００９６】
一方、下位ビット符号化部９０４は第１の実施形態における下位ビット符号化部１１２と同様にして、上位／下位ビット分離部９０１の出力する係数の下位ビット部Ｌｎの符号化を行い、ビットプレーン順に並べられた下位ビット符号化データが符号バッファ９０５に出力される。
【００９７】
上記のようにして、着目している矩形ブロックの全係数値の符号化処理を終えると、符号選択部９０８は、符号バッファ９０５に格納される第１の上位ビット部Ｕ１ｎの符号化データ、第２の上位ビット部Ｕ２ｎの符号化データ、下位ビット部Ｌｎの符号化データの符号量に基づき、境界ビット位置をＢとするか、Ｂ−１とするかを決定する。そして、決定した境界ビット位置に基づき、出力すべき符号化データを取り出す。
【００９８】
今、第１の上位ビット部Ｕ１ｎの符号化データの符号量をＣａ、第２の上位ビット部Ｕ２ｎの符号化データの符号量をＣｂ、下位ビット部Ｌｎの符号化データの符号量をＣｃと定義する。また、下位ビット部Ｌｎの符号化データから、Ｂ桁のビットプレーンの符号化データを除いた符号化データの符号量をＣｄと定義する。
【００９９】
従って、“Ｃａ＋Ｃｃ”は、境界ビット位置をＢとした場合の着目している矩形ブロックの符号量を意味する。また、“Ｃｂ＋Ｃｄ”は、境界ビット位置をＢ−１とした場合の着目している矩形ブロックの符号量を意味することになるのは明らかであろう。
【０１００】
それ故、符号選択部９０８は、“Ｃａ＋Ｃｃ”と“Ｃｂ＋Ｃｄ”とを比較する。この比較結果に応じて、符号選択部９０８は次の処理を実行する。
・Ｃａ＋Ｃｃ≦Ｃｂ＋Ｃｄの場合：
符号選択部９０６は、符号バッファ９０５内に格納された第１の上位ビット部Ｕ１ｎの符号化データと、下位ビット部Ｌｎの符号化データを選択し、符号列形成部１１４に出力する。また、このとき、符号選択部９０６は、境界ビット位置がＢであることを示す信号を符号列形成部１１４に出力する。
・Ｃａ＋Ｃｃ＞Ｃｂ＋Ｃｄの場合：
符号選択部９０６は、符号バッファ９０５内に格納された第２の上位ビット部Ｕ２ｎの符号化データと、下位ビット部Ｌｎの符号化データからＢ桁のビットプレーンの符号化データを除く符号化データを選択し、符号列形成部１１４に出力する。また、このとき、符号選択部９０６は、境界ビット位置がＢ−１であることを示す信号を符号列形成部１１４に出力する。
【０１０１】
以上説明したように本第２の実施形態によれば、境界ビット位置Ｂとその近傍に当たるＢ−１を用いて上位ビット部の符号化を行い、ブロックの符号量の小さくなる方を選択する。これにより、少なくとも第１の実施形態と比較して、より高い圧縮率の符号化データを生成することが可能になる。
【０１０２】
なお、本第２の実施形態では、境界ビット位置ＢとＢ−１の２つの方法での符号化データ量を比較する例を説明したが、Ｂ＋１、Ｂ、Ｂ−１の３つの方法で符号化データを比較し、最小の符号化データを選択するようにしても構わない。この３つの方法を利用する場合では、Ｂ＋１を境界ビット位置として、下位ビット部を下位ビット符号化部で符号化すればよい。境界ビット位置Ｂ、Ｂ−１の場合の下位ビット部の符号化データは、下位ビット符号化部で得られた符号化データの中から選択できるからである。別な表現を用いるのであれば、Ｂ”＝Ｂ＋１とした場合、Ｂ”、Ｂ”−１、Ｂ”−２について符号化データ量を比較することとも等価であるから、かかる点は容易に理解できよう。
【０１０３】
＜第２の実施形態の変形例＞
上記第２の実施形態の処理についても、第１の実施形態の変形例と同様にコンピュータプログラムで実現することができる。装置構成は、第１の実施形態の変形例と同じ図１３の構成で構わない。また、処理のフローについても図２に示した第１の実施形態の変形例と基本的に同じである。相違点は、ステップＳ２０５におけるブロックＭＢ（ｉ）の符号化において、上述の係数符号化部９０９の処理に相当する符号化処理が行われることのみであるため、ここでの詳述は不要であろう。
【０１０４】
以上説明したように、本変形例によっても、第２の実施形態と同様の作用効果を奏することが可能となるのは明らかである。即ち、境界ビット位置Ｂとその近傍に当たるＢ−１を用いて上位ビット部の符号化を行い、ブロックの符号量の小さくなる方を選択する。これにより、より最適に近い境界ビット位置の選択が可能となり、符号量を削減することができる。
【０１０５】
［第３の実施形態］
上記第１、第２の実施形態の画像符号化装置では、上位ビット部の符号化に用いるランレングス符号化が有効に機能するように、係数の有効ビット数の分布から上位ビット部のゼロ係数が所定の比率となる境界ビットＢを選択した。しかしながら、先に説明したように、ゼロ係数が同数の場合でも、非ゼロ係数が固まっているか、分散しているかによっても符号化の効率は異なってくるため、第２の実施形態による符号化データが最も効率が良いことを約束するものではない。そこで、本第３の実施形態では、単に比率から導かれる閾値のみを用いるのではなく、ゼロ係数、非ゼロ係数の分布状況を考慮して境界ビット位置を決定する例を説明する。すなわち、本第３の実施形態では、非ゼロ係数が固まっているのか、分散しているのか検出し、非ゼロラン長（ラン長がゼロでない）の数を計数して境界ビットＢの決定に用いる実装形態を説明する。
【０１０６】
なお、本第３の実施形態でも、符号化対象の画像データは、説明を簡単にするためにモノクロ画像データとするが、ＲＧＢ画像データや、ＣＭＹＫカラー画像データに適用しても良い。また、画像は水平方向Ｗ画素、垂直方向Ｈ画素により構成され、いずれも８の整数倍であるものとして説明する。
【０１０７】
本第３の実施形態に係る画像符号化装置のブロック構成図を図１０に示す。図１０と図１との違いは、図１における境界ビット位置決定部１１６が、図９の境界ビット位置決定部１０００に置き換わった点である。また、境界ビット位置決定部１０００における有効ビット数判定部１０６、頻度テーブル生成部１０７、及び、頻度テーブル１０８についても、図１と同じであるので、その説明については詳述しない。
【０１０８】
以下、本第３の実施形態との差異部分である、境界ビット位置決定部１０００の処理について説明する。なお、本第３の実施形態における有効ビット数判定部１０６、及び、上位／下位ビット分離部１１０は、係数バッファ１０５から係数値Ｃｎを読取る順番（スキャン順）は同じ順であるとして説明する。
【０１０９】
図１０の境界ビット位置決定部１０００は、図１における境界ビット位置決定部１１６に、非ゼロランカウンタ更新部１００１、非ゼロランカウンタ１００２を追加した構成となっている。非ゼロランカウンタ１００２は、図１１に示すように、各ビット位置を境界ビットとした場合の非ゼロランの数を保持する。ビット位置ｂの非ゼロラン数をＮＺ（ｂ）と記す。ブロックの読み込み開始時に、全てのｂについて非ゼロラン数ＮＺ（ｂ）を０に設定する。
【０１１０】
入力される着目係数Ｃｎに対して、有効ビット数判定部１０６により、有効ビット数Ｂ（Ｃｎ）が求められると、頻度テーブル生成部１０７により頻度テーブルバッファ１０８に格納される頻度テーブルの更新処理が行われる。
【０１１１】
一方、有効ビット数Ｂ（Ｃｎ）は非ゼロランカウンタ更新部１００１にも供給される。非ゼロランカウンタ更新部１００１は、直前の係数Ｃｎに対する有効ビット数Ｂ（Ｃｎ−１）が保持している。そして、Ｂ（Ｃｎ）＞Ｂ（Ｃｎ−１）である場合、Ｂ（Ｃｎ−１）≦ｂ＜Ｂ（Ｃｎ）となるｂについて、非ゼロランカウンタ１００２に保持するＮＺ（ｂ）を“１”だけインクリメントして更新する。
【０１１２】
例えば、図１２に示す係数値Ｃｎ−１とＣｎの場合を考える。境界ビット位置Ｂを０−３に設定した場合、どちらの上位ビットも非ゼロであり、Ｃｎの上位ビット部は長さゼロのゼロランの後の非ゼロ係数として符号化される。一方、境界ビット位置Ｂを４、または、５に設定した場合、Ｃｎ−１の上位ビットはゼロとなるが、Ｃｎの上位ビットはゼロとならないため、Ｃｎは非ゼロのラン長のゼロランの後に続く非ゼロ係数として符号化される。よってビットｂ＝４、５について非ゼロラン数ＮＺ（ｂ）をインクリメントする。境界ビット位置Ｂを６以上に設定した場合にはＣｎ−１もＣｎも上位ビットはゼロとなるため、変更しない。
【０１１３】
上記処理を着目するブロックについて行うことにより、各ビットを境界ビットとした場合の非ゼロラン数のカウントを行う。
【０１１４】
境界ビット選択部１００３は、まず、第１の実施形態で説明した境界ビット選択部１０９と同様にして、頻度テーブルから累積頻度テーブルへと変換を行い、上位ビット部の非ゼロ係数の出現回数と所望の比率で表わされる閾値とを比較することで、暫定境界ビット位置Ｂ’を決定し、この段階では係数符号化部１１７に供給しない（第１の実施形態では、この段階で得られた境界ビット位置が係数符号化部１１７に供給されていた）。
【０１１５】
境界ビット選択部１００３は、暫定境界ビット位置Ｂ’を用いて、非ゼロランカウンタ１００２を参照してＮＺ（Ｂ’）を得る。そして、境界ビット選択部１００３は、得られたＮＺ（Ｂ’）と予め設定された閾値Ｔｈ２、Ｔｈ３とを比較する。ここで閾値Ｔｈ３、Ｔｈ２の関係は、Ｔｈ３＜Ｔｈ２の関係にあるものとする。
【０１１６】
もし、ＮＺ（Ｂ’）＞Ｔｈ２であったとすると、境界ビット位置Ｂ’を境界ビットとした場合に非ゼロとなる係数が分散している状態あることを示している。言い換えれば、これ以上境界ビットを下位方向に設定してしまうと、効率的なランレングス符号化ができないことを意味する。よって、ＮＺ（Ｂ’）＞Ｔｈ２である場合、境界ビット選択部１００３はＢ’＋１を、最終的な境界ビット位置Ｂとして係数符号化部１１７に供給する。
【０１１７】
また、ＮＺ（Ｂ’）＜Ｔｈ３であったとすると、暫定境界ビット位置Ｂ’を境界ビットとした場合に非ゼロとなる係数が密集（連続）している状態あることを示している。言い換えれば、更に境界ビット位置を下位ビット方向に変更したとしても、効率的なランレングス符号化が期待できることを意味する。よって、ＮＺ（Ｂ’）＜Ｔｈ３である場合、境界ビット選択部１００３はＢ’−１を、最終的な境界ビット位置Ｂとして係数符号化部１１７に供給する。
【０１１８】
また、Ｔｈ３≦ＮＺ（Ｂ’）≦Ｔｈ２の関係にあるとき、境界ビット選択部１００３は暫定境界ビット位置Ｂ’を、最終的な境界ビット位置Ｂとして係数符号化部１１７に供給する。
【０１１９】
以上説明したように本第３の実施形態によれば、境界ビットの候補位置において、上位ビット部のゼロ、非ゼロの係数の分布状況を判別し、境界ビットを選択することで、ランレングス符号化を更に効率的に機能させることができる。
【０１２０】
＜第３の実施形態の変形例＞
上記第３の実施形態の処理についても、第１、第２の実施形態の処理と同様にコンピュータプログラムで実現することができる。装置構成は、第１の実施形態の変形例と同じ図１３の構成で構わない。また、処理のフローについても図２に示した第１の実施形態の変形例と基本的に同じである。相違点は、ステップＳ２０４における境界ビット決定と、ステップＳ２０５におけるブロックＭＢ（ｉ）の符号化の内部処理のみである。すなわち、上述の通り、ステップＳ２０４においては境界ビット位置決定部１００４に相当する処理が行われ、ステップＳ２０５においては、第２の実施形態で説明した係数符号化部９０９に相当する符号化処理が行われる。
【０１２１】
従って、本変形例によっても、第３の実施形態と同様の作用効果を奏することが可能となるのは明らかであろう。即ち、暫定境界ビット位置において、上位ビット部のゼロ、非ゼロの係数の分布状況を判別し、暫定境界ビット位置を調整することで、ランレングス符号化を効率的に機能させることができる。
【０１２２】
［その他の実施形態］
上記各実施形態では、上位ビット部の符号化にＪＰＥＧ Ｂａｓｅｌｉｎｅと同様の手法を用いる例について示した。しかしながら、ゼロと非ゼロの情報の伝達にランレングス符号化を用いたものであればこれに限らず、各種の変形が可能であることは容易に理解できよう。また、上述の実施形態では８×８画素をブロックとして境界ビット位置を決定したが、ＪＰＥＧにおけるＭＣＵのように８×８ブロックのいくつかの集まりで最小符号化単位を構成し、それぞれに境界ビットを設定するようにしても良い。あるいは、画像をあらかじめタイルに分割し、各タイル毎に境界ビット位置を決定するようにしても構わない。
【０１２３】
また、実施形態では、モノクロ画像データの符号化を例に説明したが、画像の色空間は、ＲＧＢ、ＣＭＹＫ、Ｌａｂ、ＹＣｒＣｂなど様々なタイプの画像データに適用可能であるのは明らかであるので、色成分の数や色空間の種類によって本発明が限定されるものではない。
【０１２４】
また、通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されていて、それをコンピュータの読取り装置（ＣＤ−ＲＯＭドライブ）にセットし、システムにコピーもしくはインストールすることで実行可能になる。従って、このようなコンピュータ可読記憶媒体も本発明の範疇に入ることも明らかである。
【図面の簡単な説明】
【０１２５】
【図１】第１の実施形態に係る画像符号化装置のブロック構成図である。
【図２】第１の実施形態における変形例の符号化処理手順を示すフローチャートである。
【図３】第１の実施形態における変形例の境界ビット位置決定の処理手順を示すフローチャートである。
【図４】頻度テーブルの例を示す図である。
【図５】累積頻度テーブルの例を示す図である。
【図６】係数のビット分離の概略を示す図である。
【図７】下位ビット符号化データの例を示す図である。
【図８】第１の実施形態において生成する符号化データファイルのデータ構造を示す図である。
【図９】第２の実施形態に係る画像符号化装置のブロック構成図である。
【図１０】第３の実施形態に係る画像符号化装置のブロック構成図である。
【図１１】非ゼロランカウンタ１００２に保持されるカウンタの概略を示す図である。
【図１２】係数Ｃｎと直前の係数Ｃｎ−１の例を示す図である。
【図１３】第１の実施形態の変形例に係る情報処理装置のブロック構成図である。
【図１】
0004944833.tif 000002
【図２】
0004944833.tif 000003
【図３】
0004944833.tif 000004
【図４】
0004944833.tif 000005
【図５】
0004944833.tif 000006
【図６】
0004944833.tif 000007
【図７】
0004944833.tif 000008
【図８】
0004944833.tif 000009
【図９】
0004944833.tif 000010
【図１０】
0004944833.tif 000011
【図１１】
0004944833.tif 000012
【図１２】
0004944833.tif 000013
【図１３】
0004944833.tif 000014