(57)【要約】【課題】  画像符号化装置において、符号量対歪の傾きを計算する除算処理を効率化することにより、高速符号化処理を可能とする。【解決手段】  歪計算手段２０１で係数モデリング手段１０３で分割された符号化パス毎に歪を計算し、符号量計算手段２０２で、符号化パス毎に符号量をカウントし、傾き計算手段３０１で、符号化パス毎の符号量Ｒと歪Ｄに基づいて符号化パス毎の符号量対歪の傾きＳを計算し、その際、同一符号化パスに対して前に１度行った傾き計算については以降の同じ計算から除き、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行う。【選択図】        図２
2005109917.tif 000002
【特許請求の範囲】
【請求項１】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化装置において、
符号化パス毎の符号量対歪の傾きを計算するのに用いる傾き計算手段が、同一符号化パスに対して前に１度行った傾き計算については以降の同じ計算から除き、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行うことを特徴とする画像符号化装置。
【請求項２】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化装置において、
符号化パス毎の符号量対歪の傾きを計算するのに用いる傾き計算手段が、ある符号化パスについて計算した傾きが直前のパスの傾きよりも大なるときはこれらのパスの替りに前後の切捨てポイントの候補を結ぶパスの傾きを計算し、かつ切捨てポイントの降順に単調増加となるように不適切な切捨てポイントを取り除き、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行うことを特徴とする画像符号化装置。
【請求項３】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化装置において、
符号化パス毎の符号量対歪の傾きを計算するのに用いる傾き計算手段が、計算したある符号化パスの傾きが直前に有効となった符号化パスの傾きより大きければ無効な傾きとし、一方小さければ有効な傾きとすることにより、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行うことを特徴とする画像符号化装置。
【請求項４】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化装置において、
符号化パス毎の符号量対歪の傾きを計算するのに用いる傾き計算手段が、当該符号量対歪の傾きに対して切捨てポイントの候補の降順に処理することにより、結果的に上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行うことを特徴とする画像符号化装置。
【請求項５】
切捨てポイントの候補を、符号化パスの替りにビットプレーンとしたことを特徴とする請求項１から請求項４のうちいずれか１項記載の画像符号化装置。
【請求項６】
切り捨てポイントの候補の集合を予め複数設定し、符号化レートによって当該集合を切り替える切捨てポイント設定手段を備え、
分割された符号化パスに対する替りに、前記切捨てポイント設定手段で設定された切り捨てポイントの候補に対して歪と符号量を算出し、得られた符号量と歪に基づいて符号量対歪の傾きを計算し、その際上位ビットから下位ビットに向かってその傾きが単調減少になるように補正することを特徴とする請求項１から請求項４のうちいずれか１項記載の画像符号化装置。
【請求項７】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、その際、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行い、各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化装置において、
切り捨てポイントの候補の集合を予め複数設定し、符号化レートによって当該集合を切り替える切捨てポイント設定手段を備え、
分割された符号化パスに対する替りに、前記切捨てポイント設定手段で設定された切り捨てポイントの候補に対して歪と符号量を算出し、得られた符号量と歪に基づいて符号量対歪の傾きを計算し、その際上位ビットから下位ビットに向かってその傾きが単調減少になるように補正することを特徴とする請求項１から請求項４のうちいずれか１項記載の画像符号化装置。
【請求項８】
切り捨てポイント設定手段は、符号化レートと分解レベルによって切捨てポイントの候補の集合を切り替えることを特徴とする請求項６または請求項７記載の画像符号化装置。
【請求項９】
切り捨てポイント設定手段は、符号化レートと分解レベル、およびサブバンド情報によって切捨てポイントの候補の集合を切り替えることを特徴とする請求項６または請求項７記載の画像符号化装置。
【請求項１０】
切り捨てポイント設定手段は、符号化レートと分解レベル、サブバンド情報、色成分によって切捨てポイントの候補の集合を切り替えることを特徴とする請求項６または請求項７記載の画像符号化装置。
【請求項１１】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、
このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、
量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、
それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、
分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、
得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、
この傾き計算の際に、同一符号化パスに対して前に１度行った傾き計算については以降の同じ計算から除き、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行い、
各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、
各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化方法。
【請求項１２】
傾き計算の際の補正処理は、以下の処理手順により行われることを特徴とする請求項１１記載の画像符号化方法。
(1)Set Ni={n} (i.e. the set of all truncation point)
(2)Set p=0, m=1
(3)For k=m, m+1, m+2, m+3,・・・,kmax
If k belongs to Ni
Set ΔR(i,k)=R(i,k) - R(i,p), and ΔD(i,k)= D(i,p) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠0 and S(i,k) > S(i,p),
then remove p from Ni, and set p=p-1, m=k, go to step (3)
Otherwise, set p=k
ここで、Ｎｉは符号ブロックｉの符号化パスの集合、ｋは切捨てポイントの候補、ｐはｋの直前のパス、Ｒは符号量、Ｄは歪、Ｓは傾きとする。
【請求項１３】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、
このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、
量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、
それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、
分割された符号化パス毎にエントロピー符号化を行い、
分割された符号化パス毎に歪と符号量を算出し、
得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、
この傾き計算の際に、ある符号化パスについて計算した傾きが直前のパスの傾きよりも大なるときはこれらのパスの替りに前後の切捨てポイントの候補を結ぶパスの傾きを計算し、かつ切捨てポイントの降順に単調増加となるように不適切な切捨てポイントを取り除いて上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行い、
各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、
各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化装方法。
【請求項１４】
傾き計算の際の補正処理は、以下の処理手順により行われることを特徴とする請求項１３記載の画像符号化方法。
(1)Set Ni={n} (i.e. the set of all truncation point)
(2)Set p=0
(3)For k=1, 2, 3,・・・,kmax
If k belongs to Ni
Set ΔR(i,k)=R(i,k) - R(i,k-1), and ΔD(i,k)= D(i,k-1) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠0 and S(i,k) > S(i,k-1),
then remove (k-1) from Ni
Set ΔR(i,k)=R(i,k) - R(i,p-1), and ΔD(i,k)= D(i,p-1) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
Otherwise, set p=k
(4)Set p=kmax
(5)For k=kmax-1, kmax-2, ・・・, 2, 1
If k belongs to Ni, and S(i,k) < S(i,p),
then remove k from Ni
Otherwise, Set p=k
ここで、Ｎｉは符号ブロックｉの符号化パスの集合、ｋは切捨てポイントの候補、ｐはｋの直前のパス、Ｒは符号量、Ｄは歪、Ｓは傾きとする。
【請求項１５】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、
このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、
量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、
それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、
分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、
得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、
この傾き計算の際に、ある符号化パスの傾きが直前に有効となった符号化パスの傾きより大きければ無効な傾きとし、一方小さければ有効な傾きとすることにより、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行い、
各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、
各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化方法。
【請求項１６】
傾き計算の際の補正処理は、以下の処理手順により行われることを特徴とする請求項１５記載の画像符号化方法。
(1)Set Ni={n} (i.e. the set of all truncation point)
(2)Set p=0
(3)For k=1, 2, 3,・・・,kmax
Set ΔR(i,k)=R(i,k) - R(i,p), and ΔD(i,k)= D(i,p) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠0 and S(i,k) > S(i,p),
then remove k from Ni
Otherwise, set p=k
ここで、Ｎｉは符号ブロックｉの符号化パスの集合、ｋは切捨てポイントの候補、ｐはｋの直前のパス、Ｒは符号量、Ｄは歪、Ｓは傾きとする。
【請求項１７】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、
このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、
量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、
それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、
分割された符号化パス毎にエントロピー符号化を行い、
分割された符号化パス毎に歪と符号量を算出し、
得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、
この傾き計算の際に、当該符号量対歪の傾きに対して降順に処理することにより、結果的に上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行い、
各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、
各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化方法。
【請求項１８】
傾き計算の際の補正処理は、以下の処理手順により行われることを特徴とする請求項１５記載の画像符号化方法。
(1)Set Ni={n} (i.e. the set of all truncation point)
(2)Set p=kmax
(3)For k=kmax-1, kmax-2, ・・・, 1, 0
Set ΔR(i,k)=R(i,k) - R(i,p), and ΔD(i,k)= D(i,p) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠kmax and S(i,k) < S(i,p),
then remove k from Ni
Otherwise, set p=k
ここで、Ｎｉは符号ブロックｉの符号化パスの集合、ｋは切捨てポイントの候補、ｐはｋの直前のパス、Ｒは符号量、Ｄは歪、Ｓは傾きとする。
【請求項１９】
切捨てポイントの候補を、符号化パスの替りにビットプレーンとしたことを特徴とする請求項１１から請求項１８のうちいずれか１項記載の画像符号化装置。
【請求項２０】
切り捨てポイントの候補の集合を予め複数設定しておいて符号化レートによって当該集合を切り替えるようにし、分割された符号化パスに対する替りに、前記設定された切り捨てポイントの候補に対して歪と符号量を算出し、得られた符号量と歪に基づいて符号量対歪の傾きを計算し、その際上位ビットから下位ビットに向かってその傾きが単調減少になるように補正することを特徴とする請求項１１から請求項１８のうちいずれか１項記載の画像符号化方法。
【請求項２１】
入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、
このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、
量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、
それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、
分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、
予め複数設定された切り捨てポイントの候補の集合を、符号化レートによって切り替えるようにし、前記設定された切り捨てポイントの候補に対して歪と符号量を算出し、
得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、
この傾き計算の際に、同一符号化パスに対して前に１度行った傾き計算については以降の同じ計算から除き、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行い、
各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、
各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データ作成する画像符号化方法。
【請求項２２】
切捨てポイントの候補の集合を、符号化レートと分解レベルによって切り替えることを特徴とする請求項２０または請求項２１記載の画像符号化方法。
【請求項２３】
切捨てポイントの候補の集合を、符号化レートと分解レベル、およびサブバンド情報によって切り替えることを特徴とする請求項２０または請求項２１記載の画像符号化方法。
【請求項２４】
切捨てポイントの候補の集合を、符号化レートと分解レベル、サブバンド情報、色成分によって切り替えることを特徴とする請求項２０または請求項２１記載の画像符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、特にＪＰＥＧ２０００の画像符号化のレート制御処理において、符号量対歪の傾きを符号量に対して単調減少に補正処理を行う画像符号化装置および画像符号化方法に関するものである。
【背景技術】
【０００２】
現在インターネットを中心に静止画像符号化アルゴリズムＪＰＥＧが広く普及しているが、一方で次世代の符号化方式としてさらなる性能改善、機能付加の要求を背景として、１９９７年より新たにＪＰＥＧ２０００プロジェクトがＩＳＯとＩＴＵの合同機関によりスタートした。２０００年１２月には、同ＪＰＥＧ２０００アルゴリズムの基本方式を定めるパート１についてその主要な技術内容が確定した（例えば、非特許文献１参照。）。以下に、非特許文献１に従ってＪＰＥＧ２０００符号化アルゴリズムの基本方式の概略を説明する。なお、画像符号化装置としての機能構成はこの発明の図１および図２と概略同じものである。
【０００３】
入力される画像信号は、まず、２次元のウェーブレット（Wavelet ）変換が施され、複数のサブバンドに帯域分割される。ここで、２次元のウェーブレット変換は１次元のウェーブレット変換の組み合わせとして実現される。つまり、水平方向の一次元ウェーブレット変換をライン毎に順次行う処理と、垂直方向の一次元ウェーブレット変換を列毎に順次行う処理である。また、１次元のウェーブレット変換は、図２０（ａ）に示すように、所定の特性を持つローパスフィルタとハイパスフィルタおよびダウンサンプラから構成されるものである。こうして生成された２次元のウェーブレット変換係数は、低域成分をＬ、高域成分をＨとし、水平方向の変換を１文字目、垂直副走査方向の変換を２文字目で表現することで、図２０（ｂ）に示すようにＬＬ、ＨＬ、ＬＨ、ＨＨと表現される。また、これらの帯域分割された成分はサブバンドと呼ばれている。ここで、水平、垂直方向の低域成分（ＬＬ成分）は再帰的にウェーブレット変換が施される。再帰的に施される各ウェーブレット変換によって生成される各サブバンドを分解レベルと称し、図中ＬＬ、ＨＬ、ＬＨ、ＨＨの前に記載された数字がこれにあたる。すなわち、ウェーブレット変換の分解回数２の場合には、最低解像度成分の分解レベルは２となり、反対に最高解像度成分のＨＬ，ＬＨ，ＨＨの分解レベルは１になる。
【０００４】
次に、各サブバンドのウェーブレット変換係数は、サブバンド毎に設定された量子化ステップサイズにより量子化される。各サブバンドの量子化後のウェーブレット変換係数は、符号ブロックと呼ばれる固定サイズの領域に分割された後、それぞれの符号ブロックの多値データを２値のビットプレーン表現に変換し、各ビットプレーンは３通りの符号化パス（Significant Propagation Decoding Pass、Magnitude Refinement PassおよびCleanup Pass）に分割される。この３つの符号化パスから出力される２値信号は、それぞれの符号化パス毎にコンテクストモデリングが行われ、エントロピー符号化が行われる。また、エントロピー符号化処理と並行して、各符号ブロックにおいて符号化パス毎の符号量と歪情報が計算される。最後に、ラグランジェの未定乗数法を用いて、画質劣化（歪）を最小にしながら目標とする符号サイズ以下に符号量を調整するレート制御が行われる。非特許文献１に従ったレート制御部のメカニズムについての概略を以下に説明する。
【０００５】
各符号ブロックｉにおける切り捨てポイントをｎｉとした時、各切捨てポイントまでの符号量をＲ（ｉ，ｎｉ）、歪をＤ（ｉ，ｎｉ）とした時、Σ（Ｒ（ｉ，ｎｉ）＋λＤ（ｉ，ｎｉ））で表される値を最小にする切捨てポイントによって生ずる符号量Ｒが目標符号量Ｒｍａｘの範囲内であることを満足するまで変数λを調整する。これを符号ブロック毎に見た場合、（Ｒ（ｉ，ｎｉ）＋λＤ（ｉ，ｎｉ））を最小化する切捨てポイントｎｉを次のように見つける必要がある。ここで、ｋは切捨てポイントの候補とする。
Set ni=0
For k=1,2,3,・・・
Set  ΔR(i,k)= R(i,k) - R(i,ni) and ΔD(i,k)= D(i,k) - D(i,ni)
If(ΔD(i,k)/ΔR(i,k))>λ-1 ,
then set ni=k
【０００６】
ところが、このアルゴリズムでは、多数の変数λに対して上記処理を実行しなければ切捨てポイントｎｉを求めることができない。そこで、切捨てポイントの候補ｋに対して、傾きＳ（ｉ，ｋ）＝ΔＤ（ｉ，ｋ）／ΔＲ（ｉ，ｋ）が単調減少になるように補正しておくとよい。具体的には次のようなプログラム処理を行う。ここで、ｐは切捨てポイントｎｉの集合要素の一つとする。
(1)set Ni={n} (i.e. the set of all truncation point)
(2)Set p=0
(3)For k=1,2,3,4,・・・,kmax
If k belongs to Ni
Set ΔR(i,k)=R(i,k) - R(i,p), and ΔD(i,k)= D(i,p) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠0 and S(i,k) > S(i,p),
then remove p from Ni, and go to step (2)
Otherwise, set p=k
この処理により、与えられた変数λに対する切捨てポイントの最適化は、Ｓ（ｉ，ｋ）＞λ-１を満たすＮｉ（符号ブロックの中の符号パスの集合）における最大のｋとすればよい。なお、単調減少の具体的な例については、この発明と対比して図を用いて後述する。
【０００７】
この単調減少補正処理に関するフローチャートを図２１に示す。なお、同図において符号ブロックを示すｉは割愛している。また、‘remove p from Ni’つまり、切捨てポイントの候補Ｎｉの中からｐを取り除く作業は、図中では有効、無効を表すフラグ（flag）を用いて同意の処理を実現している。
【０００８】
全ての符号ブロックでこれらの情報の導出が完了したら、目標符号量Ｒｍａｘとなるような符号データを作成する。具体的には、ある変数λに対する総符号量Ｒｓｕｍに対してＲｓｕｍ≦Ｒｍａｘとなり、歪が最小となるような変数λを見つけることになる。変数λを求めたら、その値から各符号ブロックにおいて切捨てポイントを一意に求め、その切捨てポイントまでの符号データを全ての符号ブロックから集めて最終的な符号データを構成する。こうして、歪を最小にしながら目標符号量Ｒｍａｘに符号量を制御することができる。
【０００９】
【非特許文献１】勧告書ＩＳＯ/ＩＴＵ １５４４４-１:２０００のＪ．１４．３（ｐ２２０〜ｐ２２１）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述した従来の技術において、切捨てポイントの候補ｋに対する傾きＳを単調減少に補正する処理には除算処理（Ｓ（ｉ，ｋ）=ΔＤ（ｉ，ｋ）/ΔＲ（ｉ，ｋ））が含まれているが、切捨てポイントの候補ｋの最大値をｋｍａｘとした時、一つの符号ブロック内での除算回数の最大値は（ｋｍａｘ（ｋｍａｘ+１）／２）回となる。通常除算処理は、ハードウェアで実装する場合、多くの処理クロック数を必要とするため、この除算回数が多くなることにより、処理速度が遅くなってしまうという問題がある。また、ソフトウェアで実装する場合でも、パーソナルコンピュータやワークステーション等のように高速なＣＰＵにより実装する場合は多くの影響は及ぼさないが、例えばディジタルスチルカメラや携帯電話のように、十分な処理能力を持たないＣＰＵで実行する場合、除算処理が多くなることは全体の処理時間に影響を及ぼすことになる。このように、実装がハードウェアにしてもソフトウェアにしても、除算回数が多いことにより処理速度が遅くなるという問題がある。
【００１１】
この発明は、上記のような問題点を解決するためになされたもので、符号量対歪の傾きを計算する除算処理を効率化することにより、高速符号化処理を可能とする画像符号化装置および画像符号化方法を得ることを目的とする。
【課題を解決するための手段】
【００１２】
この発明に係る画像符号化装置は、入力画像信号を２次元的にウェーブレット変換してサブバンド毎のウェーブレット変換係数を生成し、このウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化し、量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、それぞれの符号ブロックの多値データを２値のビットプレーンに分解した後、符号化パスに分割し、分割された符号化パス毎にエントロピー符号化を行い、分割された符号化パス毎に歪と符号量を算出し、得られた符号化パス毎の符号量と歪に基づいて符号量対歪の傾きを計算し、各符号ブロックに対して符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出し、各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データから前記目標符号量内で最小の歪を持つ符号データを作成する画像符号化装置において、符号化パス毎の符号量対歪の傾きを計算するのに用いる傾き計算手段が、同一符号化パスに対して前に１度行った傾き計算については以降の同じ計算から除き、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行うものである。
【発明の効果】
【００１３】
この発明によれば、符号量対歪の傾きを計算する除算処理量を有効に減らすことにより高速な符号化処理を可能とする効果がある。
【発明を実施するための最良の形態】
【００１４】
実施の形態１．
図１は各実施の形態による画像符号化装置の機能構成を示すブロック図である。
図において、ウェーブレット変換手段１０１は、入力画像信号を低域通過フィルタと高域通過フィルタを用いて水平、垂直方向に２次元的にウェーブレット変換を再帰的に行い、サブバンド毎のウェーブレット変換係数を生成する手段である。量子化手段１０２は、ウェーブレット変換手段１０１によって生成されたウェーブレット変換係数をサブバンド毎に設定された量子化ステップサイズで量子化する手段である。係数モデリング手段１０３は、量子化された各サブバンドのウェーブレット変換係数を符号ブロックに分割し、それぞれの符号ブロックの多値データを２値のビットプレーンに分解し、２値算術符号化するため各ビットプレーンを３種類の符号化パスに分割する手段である。エントロピー符号化手段１０４は、分割された符号化パス毎にコンテクストモデリングを行った後、エントロピー符号化を行う手段である。符号メモリ１０５は、エントロピー符号化された符号データを一時的に格納する手段である。レート制御情報抽出手段１０６は、分割された符号化パスから、レート制御に必要な歪データと符号量データを計算し、また他で計算した符号量対歪の傾きデータを保持し、それらをレート制御情報として出力する手段である。レート制御手段１０７は、レート制御情報抽出手段１０６から出力されるレート制御情報から、目標符号量内に収まるような最適な符号データを生成する手段である。
【００１５】
図２は図１のレート制御情報抽出手段１０６およびレート制御手段１０７の詳細な構成を示すブロック図である。
図において、レート制御情報抽出手段１０６は、歪計算手段２０１、符号量計算手段２０２およびレート歪メモリ２０３から構成されている。歪計算手段２０１は、係数モデリング手段１０３で分割された符号化パス毎にウェーブレット変換係数から歪を計算する手段である。符号量計算手段２０２は、符号化パス毎に符号量をカウントする手段である。レート歪メモリ２０３は、符号化パス毎に得られた歪データと符号量データおよびレート制御手段１０７の傾き計算手段３０１で計算された符号化パス毎の符号量対歪の傾きを一時的に記憶する手段である。
【００１６】
レート制御手段１０７は、傾き計算手段３０１、切捨てポイント導出手段３０２および符号抽出手段３０３から構成されている。傾き計算手段３０１は、レート歪メモリ２０３に格納されている符号化パス毎の符号量Ｒと歪Ｄに基づいて符号化パス毎の符号量対歪の傾きＳを計算し、その際上位ビットから下位ビットに向かって当該符号量対歪の傾きＳが単調減少になるように補正処理を行う手段である。なお、この例では、計算された傾きＳはレート制御情報抽出手段１０６のレート歪メモリ２０３に格納される。切捨てポイント導出手段３０２は、各符号ブロックに対して前記レート歪メモリに記憶された符号量、歪および符号量対歪の傾きを用いて目標符号量内で歪が最小となる切り捨てポイントを導出する手段である。符号抽出手段３０３は、各符号ブロックにおいて導出された切捨てポイントより上位の符号化パスの符号データを符号メモリ１０５から集め、目標符号量内で最小の歪を持つ符号データを作成し、画像圧縮装置の最終的なデータとして出力する手段である。
【００１７】
次に動作について説明する。
例えば、イメージスキャナやデジタルカメラ、もしくはネットワークや記憶媒体等の画像入力装置（図示せず）から画像信号が入力される。ウェーブレット変換手段１０１において、入力された画像信号に対して１次元のウェーブレット変換が水平方向と垂直方向に２次元的に施され、４つのサブバンドに帯域に分割される。ここで、１次元のウェーブレット変換は、低域通過フィルタと高域通過フィルタのフィルタバンクによって構成される。２次元のウェーブレット変換を２回再帰的に施したサブバンドの例を図３に示す。図中、先頭の数字は分解レベルを表しており、続くＬまたはＨの２つの英字は、水平方向、垂直方向のフィルタの種類を表している。Ｌは低域通過フィルタを、Ｈは高域通過フィルタを施した結果を表している。また、「再帰的に」ウェーブレット変換を２回施すと言うことは、まず第１回目のウェーブレット変換により、１ＬＬ，１ＨＬ，１ＬＨ，１ＨＨが生成されると、その１ＬＬに対して２回目のウェーブレット変換を施し、２ＬＬ，２ＨＬ，２ＬＨ，２ＨＨを生成することを意味する。ウェーブレット変換手段１０１は、このようなサブバンドに対するウェーブレット変換係数を得ることになる。
【００１８】
量子化手段１０２では、サブバンド毎に設定された量子化ステップサイズにより、ウェーブレット変換手段１０１で得られたウェーブレット変換係数を量子化する。次に、係数モデリング手段１０３では、各サブバンドのウェーブレット変換係数に対して符号ブロック（code block）と呼ばれる固定サイズの領域に分割した後、それぞれの符号ブロックの多値データを２値のビットプレーン（bit plane）に変換する。通常この符号ブロックの大きさは６４×６４、３２×３２と言ったサイズが利用される。
【００１９】
ここで、図４を用いてビットプレーンの分解について詳しく説明する。
図４（ａ）は４×４の符号ブロックの一例を表している。これらのデータに対して、正負を表す１ビットの信号と絶対値の表現に変換し、それらのデータを縦方向に２進表現した結果を各行単位に並べると図４（ｂ）のようになる。次に、図４（ｂ）に対して同一のビット番号のビットを集めたものが図４（ｃ）となる。ここで、ＬＳＢ（Least Significant Bit：最下位ビット）を第０ビット、ＭＳＢ（Most Significant Bit：最上位ビット）を第３ビットとした時、第０ビットで集めたものを第０ビットプレーン、第１ビットで集めたものを第１ビットプレーン、第２ビットで集めたものを第２ビットプレーン、第３ビットで集めたものを第３ビットプレーンとしている。これ以外にも正負を表すビットの集まりとして符号ビットプレーンを作成する。
【００２０】
係数モデリング手段１０３では、さらに、各ビットプレーンを、シグニフィカントプロパゲーションデコーディングパス（Significant Propagation Decoding Pass：有意な係数が周囲にある有意でない係数の符号化）、マグニチュードリファインメントパス（Magnitude Refinement Pass：有意な係数の符号化）、クリーナップパス（Cleanup Pass：残りの係数情報の符号化）の３通りの符号化パスに分割する。
【００２１】
次に、エントロピー符号化手段１０４では、まず、それぞれの符号化パス毎に算術符号化するためのコンテクストモデリングを行う。但し、ＭＳＢプレーンから数えて全て０となるビットプレーンは、コンテクストモデリングおよび符号化を行わず、全て０のビットプレーンの数をヘッダに書くだけとする。そして、最初に１が出現したビットプレーンについてはクリーナップパスだけでコンテクストモデリングを行う。その他のビットプレーンについては前述したように３種類の符号化パスに対してコンテクストモデリングを行う。図５は符号ブロックのビットプレーン数が６で、有効なビットプレーン数が４の場合の例を示している。コンテストモデリングが終了すると、算術符号化によりエントロピー符号化が行われる。エントロピー符号化手段１０４で生成された符号化データは一旦符号メモリ１０５に格納される。
【００２２】
エントロピー符号化処理と並行して、レート制御情報抽出手段１０６で次の処理が行われる。歪計算手段２０１において、各符号ブロックの符号化パス単位に、歪Ｄを計算する。ここで、歪Ｄとは、あるビットプレーンを送った時に再生画像に対する平均二乗誤差がどれだけ減少したかを示すもので、厳密に言えば歪の減少量ということになる。したがって、ビットプレーンを１つも送っていない時の歪の減少量は０で、最終ビットプレーンを送った時の歪の減少量は、その平均二乗誤差に等しくなる。同時に、符号量計算手段２０２では、符号化パス単位にエントロピー符号化手段１０４の出力バイト数をカウントし、符号パスまで符号量を計算する。これらの歪データ、符号量データは、タイル番号、分解レベル、サブバンド、符号ブロック、符号化パス等々のインデックスが付与された後、レート歪メモリ２０３に格納される。
【００２３】
次に、レート制御手段１０７内の傾き計算手段３０１では、レート歪メモリ２０３に格納されている符号量データＲ、歪データＤに対してその符号化パス毎の傾きＳ、すなわち符号量対歪を計算する。算出された傾きＳは同一の符号化パスの歪データ、符号量データと対応するレート歪メモリ２０３の位置に格納される。この時のレート歪メモリ２０３のデータ構成例は図６のようになる。なお、フラグについては後述する。また、図２では傾き計算手段３０１がレート制御手段１０７に含まれるように記載されているが、レート制御情報抽出手段１０６に属するようにしてもよい。
【００２４】
全ての符号ブロックに対してエントロピー符号化とレート制御情報抽出が完了すると、レート制御手段１０７では、所望の符号量となるように符号量制御が行われる。符号メモリ１０５には既に全ての符号化パスに対する符号化データが格納されているので、レート制御手段１０７では、所望符号量となるように、各符号ブロックにおいてどの符号化パスまでを最終的な符号化データに含めるか、言い換えれば、どの符号化パス以降を切り捨てるかを決定する。各符号ブロックにおいて、最終的な符号データに採用する符号化パスと切り捨てる符号化パスの境界を切捨てポイントと称することとする。
【００２５】
全てのパスに対して傾きが計算できたら、切捨てポイント導出手段３０２において、目標符号量Ｒｍａｘ以下で歪が最小（歪の減少量が最大）となる切捨てポイントを全ての符号ブロックに対して見つける処理を開始する。この最適化問題は、ラグランジェの未定乗数法を用いることで実現できる。具体的には、ある符号ブロックｉにおける切捨てポイントｎｉまでの符号量をＲ（ｉ，ｎｉ）、歪をＤ（ｉ，ｎｉ）とした時、Σ（Ｒ（ｉ，ｎｉ）＋λＤ（ｉ，ｎｉ））が最小となる切捨てポイントを見つけ、その時の総符号量Ｒｓｕｍが目標符号量Ｒｍａｘとなるような変数λを求めることになる。これは、図７に示すように、符号量Ｒと歪Ｄをグラフに表した時（以下，ＲＤ曲線と称する）、変数λが接線となるような切り捨てポイントを見つけ、その切捨てポイントの符号量の総和ＲｓｕｍがＲｍａｘとなるまで変数λを調整することと同じである。図７では、２つの符号ブロックｃ１、ｃ２において、接線の傾きがλとなる切り捨てポイントがｎｃ１、ｎｃ２で、その切捨てポイントまでの符号量がＲ（ｃ１，ｎｃ１）、Ｒ（ｃ２，ｎｃ２）となることを表している。このような符号量Ｒを全ての符号ブロックに対して加算しＲｍａｘと比較する処理を行うことになる。
【００２６】
次に、λ調整方法の具体的な例を図８のフローチャートを用いて説明する。まず、傾きの下限値λｍｉｎ、上限値λｍａｘを定義し、λ＝（λｍｉｎ＋λｍａｘ）／２となる変数λを計算する。符号ブロックｉにおいて、切捨てポイントｎｉ対する傾きＳ（ｉ，ｎｉ）とλとの関係で、Ｓ（ｉ，ｎｉ）≧λとなる最大の切り捨てポイントｎｉを求め、その符号量をＲ（ｉ，ｎｉ）とする。全ての符号ブロック対してΣＲ（ｉ，ｎｉ）＝Ｒｓｕｍを計算する。ここで、
Ｒｓｕｍ≧Ｒｍａｘであればλｍｉｎ＝λとし、
Ｒｓｕｍ＜Ｒｍａｘであればλｍａｘ＝λとする。
新しいλｍｉｎ、λｍａｘが求められたら、先と同じようにλ＝（λmin＋λmax）／２の計算を行い、以下同様に繰り返す。以上の処理をλ≧λｍａｘとなるまで繰り返す。こうして、最終的に求められたλに対する切捨てポイントｎｉが求めるべき切捨てポイントとなる。
符号抽出手段３０３では、各符号ブロックにおいて切り捨てポイントｎｉより上位の符号化パスの符号データを符号メモリ１０５から集めることにより所望の符号量Ｒｍａｘ以下で最小の歪を持つ符号データを作成する。
【００２７】
ところで、図７ではＲＤ曲線の傾きＳは符号量Ｒに対して単調減少になっているが、実際には図９に示すように単調減少にならず、ある変数（傾き）λに対してこれが接線となるポイントは複数存在する場合がある。このような場合には、それぞれのポイントに対して、Ｒ（ｉ，ｎｉ）＋λＤ（ｉ，ｎｉ）を計算し、これを最小にするポイントを見つけなければならない。しかしながら、この場合は計算回数の増大を招くこととなり、実装上好ましくない。そこで、傾き計算手段３０１では、傾きを計算するだけでなく、一つの符号ブロックにおいて符号量Ｒに対して単調減少になるように傾きＳを補正し、計算回数を調整している。このことについては、従来の技術の方法で述べてきたが、この発明では、以下に述べるような処理により更に改善を図ることができる。
【００２８】
この実施の形態１における傾き計算手段３０１では、単調減少補正処理を次のようなプログラムステップにて行う。
(1)Set Ni={n} (i.e. the set of all truncation point)
(2)Set p=0, m=1
(3)For k=m, m+1, m+2, m+3,・・・,kmax
If k belongs to Ni
Set ΔR(i,k)=R(i,k) - R(i,p), and ΔD(i,k)= D(i,p) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠0 and S(i,k) > S(i,p),
then remove p from Ni, and set p=p-1, m=k, go to step (3)
Otherwise, set p=k
これをフローチャートで示すと図１０のようになる。ここで、切捨てポイントの候補の集合Ｎｉの中からｐを取り除く作業（remove p from Ni）は、図１０では有効、無効を表すフラグを用いて同意の処理を実現している。このフラグは先に図６で説明したレート歪メモリ２０３の「フラグ」欄に格納される信号である。
【００２９】
次に、図１１に示す単調減少補正処理の具体的な例を説明する。
今、ある１符号ブロックにおける補正前の符号量と歪の関係（ＲＤ曲線）が図１１（ａ）に示すような場合について考える。ここで、切捨てポイントの候補ｋは１から４の範囲（ｋｍａｘ＝４）とする。図１１（ｂ）は非特許文献１に記載の方式の場合であり、図中折れ線グラフ上に記載している数字は傾きＳを計算する順番を表している。この図からもわかるように、合計７回の除算を行っており、そのうち、５回目と６回目の除算は、１回目と２回目の計算と同一値になっており冗長であることがわかる。この実施の形態１における単調減少補正は図１１（ｃ）のようになり、除算回数は５回となり、従来技術より少なく実装することができる。また、別の符号ブロックにおける補正前のＲＤ曲線が図１１（ｄ）のような場合について考える。これは、除算回数が最大回数となる例を表しており、除算回数は、従来の方式だと図１１（ｅ）のように１０回、この実施の形態１の方式だと図１１（ｆ）のように７回となる。このことから分るように、実施の形態１では、傾き計算手段３０１が同一符号化パスに対して前に１度行った傾き計算については以降の同じ計算から除き、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行っている。
【００３０】
したがって、この実施の形態１では、除算回数は最大（２ｋｍａｘ−１）回となるため、従来技術の例からの差分を考えると、
ｋｍａｘ（ｋｍａｘ＋１）／２−（２ｋｍａｘ−１）
＝（ｋｍａｘ２ −３ｋｍａｘ＋２）／２
＝（ｋｍａｘ−１）（ｋｍａｘ−２）／２
となり、上記差分はｋｍａｘ＞２で正となり、除算回数が減ることがわかる。また、ｋｍａｘについては、例えばビットプレーン数７の場合には、符号化パス数が６×３＋１＝１９であることから、ｋｍａｘも１９となる。この時除算回数は、従来の方式では１９０回、この実施の形態１では３７回となり、最大回数で比較すると、およそ８０％の除算処理を削減することが可能となる。
【００３１】
以上のように、この実施の形態１によれば、符号化パス毎の符号量対歪の傾きを計算する際に、同一符号化パスに対して前に１度行った傾き計算を以降の同じ計算では除き、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行うので、従来の方式に比べ、符号量対歪の傾きを計算する除算回数を大幅に削減することができるため、高速な符号化処理を可能とする効果が得られる。したがって、例えばディジタルスチルカメラや携帯電話のような十分な処理能力を持たないＣＰＵで実行する場合においても、機能を十分満足させる処理時間が得られる効果がある。また、ハードウェアで実現する場合も処理クロック数を少なくできるため処理の高速化を図ることができるという効果がある。
【００３２】
実施の形態２．
この実施の形態２による画像符号化装置のブロック上の構成は実施の形態１と同様、図１および図２と同じであるが、傾き計算手段３０１の処理機能が異なる。この実施の形態２傾き計算手段３０１は、具体的には以下のようなプログラムステップで単調減少補正処理を行いながら傾きを計算する。
(1)Set Ni={n} (i.e. the set of all truncation point)
(2)Set p=0
(3)For k=1, 2, 3,・・・,kmax
If k belongs to Ni
Set ΔR(i,k)=R(i,k) - R(i,k-1), and ΔD(i,k)= D(i,k-1) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠0 and S(i,k) > S(i,k-1),
then remove (k-1) from Ni
Set ΔR(i,k)=R(i,k) - R(i,p-1), and ΔD(i,k)= D(i,p-1) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
Otherwise, set p=k
(4)Set p=kmax
(5)For k=kmax-1, kmax-2, ・・・, 2, 1
If k belongs to Ni, and S(i,k) < S(i,p),
then remove k from Ni
Otherwise, Set p=k
【００３３】
この処理をフローチャートで示すと図１２のようになる。上記ステップ（１）〜（３）が、図１２（ａ）単調減少補正Ａ、ステップ（４）〜（５）が図１２（ｂ）単調減少補正Ｂとなる。この実施の形態２の特徴は、切捨てポイントの候補ｋに対して２つのスキャンを行っているものの、実施の形態１に比べフィードバックループ（go to step (3)）がなくなっている点である。このようにフィードバックループがないことにより、制御の複雑さを緩和することができる。
【００３４】
また、除算回数について、図１３に示す具体的な例を用いて実施の形態１の場合と比較してみる。ある符号ブロックにおける補正前のＲＤ曲線において、図１３（ａ）のような最大除算回数のケースを考えてみた場合、実施の形態１の方式は図１３（ｂ）のように、また実施の形態２の方式も図１３（ｃ）のようになり、ともに７回となる。次に、例えば図１３（ｄ）のような補正前のＲＤ曲線を考えてみる。実施の形態１の場合には図１３（ｅ）のように除算回数は６回となるのに対し、実施の形態２の場合には図１３（ｆ）のように５回の除算で済むことになる。この図１３（ｆ）は図１２（ａ）の単調減少補正Ａの処理結果であり、これでは完全に単調減少に補正できていないことがわかる。そこで、図１２（ｂ）の単調減少補正Ｂに示す再補正処理を行うと、図１３（ｇ）に示すように完全に単調減少化させることができる。この図１３（ｇ）では、１番目の傾きが４番目の傾きより小さくなっているため、１番目の傾きが無効とされることにより、４番目と５番目の傾きのみが有効となることを表しており、除算処理は１回も行われない。なお、図１３（ｇ）では２つの曲線が記載されており、上側が単調現象補正Ｂにより補正された結果を表している。これを見ると、歪が増加したように見えるが、単調減少補正処理は傾きのみが意味を持つものであり、曲線が上下することはここでは意味を持たない。ここでは、1番目の傾きが除去され、０を始点に曲線を再描画した結果であり、便宜的に表現したものである。
このように、除算回数は実施の形態１では６回であるのに対し、この実施の形態２では５回で済むことがわかる。実施の形態２では、傾き計算手段３０１が符号化パス毎の符号量対歪の傾きを計算する際に、ある符号化パスについて計算した傾きが直前のパスの傾きよりも大なるときはこれらのパスの替りに前後の切捨てポイントの候補を結ぶパスの傾きを計算し、さらに切捨てポイントの降順に単調増加となるように不適切な切捨てポイントを取り除くことにより、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行っている。
【００３５】
以上のように、この実施の形態２によれば、ある符号化パスについて計算した傾きが直前のパスの傾きよりも大なるときはこれらのパスの替りに前後の切捨てポイントの候補を結ぶパスの傾きを計算し、さらに切捨てポイントの降順に単調増加となるように不適切な切捨てポイントを取り除くことにより、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行うようにしたので、実施の形態１の場合よりもさらに除算回数を削減でき、高速な符号化処理を可能とする効果が得られる。
【００３６】
実施の形態３．
この実施の形態３による画像符号化装置のブロック構成は実施の形態１と同様、図１および図２と同じであるが、傾き計算手段３０１の処理機能が異なる。この実施の形態３の傾き計算手段３０１は、具体的には以下のようなプログラムステップで単調減少補正処理を行いながら傾きを計算する。
(1)Set Ni={n} (i.e. the set of all truncation point)
(2)Set p=0
(3)For k=1, 2, 3,・・・,kmax
Set ΔR(i,k)=R(i,k) - R(i,p), and ΔD(i,k)= D(i,p) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠0 and S(i,k) > S(i,p),
then remove k from Ni
Otherwise, set p=k
【００３７】
この処理をフローチャートで示したものが図１４である。まず当該符号化パスにおいて傾きＳ（ｋ）を計算した後、直前に有効となった符号化パスの傾きＳ（ｐ）と比較し、現在の傾きの方が小さければ有効な傾きとする。反対に現在の傾きが大きければ無効な傾きとする。この実施の形態３の場合、フィードバックループがなくなっており、切捨てポイントの候補ｋに対して１回のスキャンで済むことから、制御の複雑さを大幅に緩和することができる。また、除算回数についても、図１４から常にｋｍａｘ回であることがわかる。実施の形態１の最大回数（２ｋｍａｘ−１）回と比較すると５０％近く除算回数を削減することが可能になる。
【００３８】
次に図１５に示す単調減少補正処理の具体的な例を用いて説明する。図１５（ａ）に示すある符号ブロックにおける補正前のＲＤ曲線に対して考える。図１５（ｂ）は傾きの計算順序を表しており、計算回数は４回であることがわかる。しかしながら、３番目の傾きが２番目の傾きよりも大きくなっているため、３番目の傾きは無効にしなければならない。そこで、図１５（ｃ）に示すように、この実施の形態３の処理で単調減少補正を施した結果、１，２，４番目の傾きが有効となる。
以上のように、この実施の形態３によれば、計算したある符号化パスの傾きが、直前に有効となった符号化パスの傾きより大きければ無効な傾きとし、一方小さければ有効な傾きとすることにより、上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行うようにしたので、除算回数を実施の形態１の場合よりも大幅に削減することができ、高速な符号化処理を可能とする効果が得られる。
【００３９】
実施の形態４．
この実施の形態４による画像符号化装置のブロック構成は実施の形態１と同様、図１および図２と同じであるが、傾き計算手段３０１の処理機能が異なる。この実施の形態４の傾き計算手段３０１は、具体的には以下のようなプログラムステップで単調減少補正処理を行いながら傾きを計算する。
(1)Set Ni={n} (i.e. the set of all truncation point)
(2)Set p=kmax
(3)For k=kmax-1, kmax-2, ・・・, 1, 0
Set ΔR(i,k)=R(i,k) - R(i,p), and ΔD(i,k)= D(i,p) - D(i,k)
Set S(i,k)=ΔD(i,k)/ΔR(i,k)
If p≠kmax and S(i,k) < S(i,p),
then remove k from Ni
Otherwise, set p=k
【００４０】
この処理をフローチャートで示したものが図１６である。この実施の形態４の単調減少補正処理は実施の形態３の処理方法と類似しているが、実施の形態３では切捨てポイントの候補ｋの昇順に単調減少補正を行っているのに対し、この実施の形態４では切捨てポイントの候補ｋの降順に処理することにより、結果的に上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正処理を行う点が異なる。したがって、除算回数も常にｋｍａｘ回となる。
【００４１】
次に、この実施の形態４で降順に処理している理由について述べる。
図１７（ａ）に示すある符号ブロックにおける補正前のＲＤ曲線に対して考える。図１７（ｂ）は上記実施の形態３の方式で補正処理した例を表している。昇順に処理していくと1番目の傾きより小さい傾きが存在しないため1番目のみの傾きが有効となる。レート制御において、図１７（ａ）に記載したように、1番目の傾きよりもやや大きい変数λが導出された場合、この符号ブロックに関しては、全ての符号化パスのデータが切り捨てられてしまう。その結果、画質劣化が生じやすくなる。これに対して、この実施の形態４で補正した場合、図１７（ｃ）に示すように切捨てポイントの候補ｋの降順に処理していくと、1番目の傾きのみが無効となることがわかる。ここで図１７（ｂ）で仮定したように、レート制御において１番目の傾きよりもやや大きい傾きのλが導出された場合には、全ての符号化パスが最終的な符号化データに含まれることになるため、画質劣化を招かないことがわかる。
【００４２】
以上のように、この実施の形態４によれば、切捨てポイントの候補ｋの降順に従って処理することにより、結果として上位ビットから下位ビットに向かって当該符号量対歪の傾きが単調減少となるように補正を行うので、実施の形態３と同様に制御が簡易になると同時に、除算回数を大幅に削減でき、高速な符号化処理を可能とする効果が得られる。また、加えて、実施の形態３に比べ画質劣化を抑制できる効果が得られる。
【００４３】
実施の形態５．
これまで述べた実施の形態１から実施の形態４においては切捨てポイントの候補ｋは全ての符号化パスが対象となっていたが、この実施の形態５では、切捨てポイントの候補をビットプレーンとするものである。これまでの実施の形態では符号化パス毎にその累積歪、符号量を計算していたが、この実施の形態５では、これらの計算をビットプレーン毎に行うことになる。すなわち、歪計算手段２０１は、ビットプレーン毎に歪データを計算し、符号量計算手段２０２は、ビットプレーン毎に符号量データを計算する。また、傾き計算手段３０１は、ビットプレーンの符号量と歪に基づいて符号量対歪の傾きを計算し、レート歪メモリ２０３は、ビットプレーン毎に歪データ、符号量データおよびその傾きを格納する。
ここで、ビットプレーン数をＢ、符号化パス数をＣＰとした時、ＣＰ＝ｋｍａｘ＝１＋３（Ｂ−１）となる。このことにより、パス毎に計算する方式に比べ除算回数を１／３近くに減らすことができる。そのため、レート歪メモリ２０３の容量も、ビットプレーン単位に歪や符号量などの情報を記憶することになるので、約１／３にすることができる。
【００４４】
以上のように、この実施の形態５によれば、実施の形態１から実施の形態４において、切捨てポイントの候補を符号化パスの替りにビットプレーンとしたので、パス毎に計算する方式に比べ除算回数を大幅に減らすことができ、高速な符号化処理を可能とする効果が得られる。また、レート歪メモリのメモリ規模を削減できる効果も得られる。
【００４５】
実施の形態６．
上記実施の形態５の方法によれば、大幅な高速化、メモリ規模削減が可能になるというものの、３通りの符号化パスのデータを１つにまとめるので、制御できる刻みが大きくなり、符号量制御精度が落ちるという懸念がある。それに伴って、若干の画質劣化を招く場合が考えられる。そこで、この実施の形態６では、制御精度の悪化を招かないような切捨てポイントの候補ｋを選ぶことを特徴としている。
【００４６】
図１８は実施の形態６に係るレート制御情報抽出手段１０６の機能構成を示すブロック図である。これは図２のレート制御情報抽出手段１０６の構成に対して、切捨てポイント設定手段１９０１を新たに追加したものである。この切り捨てポイント設定手段１９０１では、切捨てポイントの候補の集合を複数種類用意しておき、その中から現在の符号化に最適な切捨てポイントの候補の集合を選択する。したがって、歪計算手段２０１では、選択された切捨てポイントの候補に従って歪を計算する。同様に、符号量計算手段２０２でも切捨てポイント設定手段１９０１から選択された切捨てポイントの候補に従って符号量を計算することになる。
【００４７】
次に具体的に図１９を用いて、切捨てポイントの候補について、他の実施の形態の場合と比較して説明する。
図において、数字はビットプレーン番号、それに続くＳはSignificant Propagation Decoding Pass、ＭはMagnitude Refinement Pass、ＣはCleanup Passを表す。また、横矢印は切捨てポイントの候補である。図１９（ａ）は切り捨てポイントの候補を符号化パスに設定した場合で、実施の形態１から実施の形態４がこれに相当する。図１９（ｂ）は切捨てポイントの候補をビットプレーンにした場合で、実施の形態５がこれに相当する。図１９（ｃ）は、この実施の形態６における一例を示したもので、下位ビットでは細かく、上位ビットでは粗く切捨てポイントの候補を設定している。また、図１９（ｄ）はこの実施の形態６における別の例を示すもので、下位ビットでは粗く、上位ビットでは細かく切捨てポイントの候補を設定している。
【００４８】
例えばユーザが符号化レートを高く設定した場合、換言すれば圧縮率を低く設定した場合には、通常切捨てポイントは下位ビット側になるので、このような場合には下位ビットの刻みが細かい図１９（ｃ）のような切捨てポイントの候補を設定する。反対に、符号化レートを低く設定した場合、換言すれば圧縮率を高く設定した場合には、通常切捨てポイントは上位ビット側になるので、このような場合には上位ビットの刻みが細かい図１９（ｄ）のような切捨てポイントの候補を設定しておく。このように、切り替えポイントの候補の集合を複数用意しておき、符号化レートに応じて最適なものに切り替えることにより、本来の切捨てポイントの周辺に対して切捨てポイントの刻みを細かくとることができるようになる。そのため、制御精度の劣化を防止することができ、画質劣化も抑制できる効果が得られる。また、上記の説明では、符号化レートに応じて、切捨てポイントの候補の集合を切り替えるようにしているが、これに加えて、分解レベル、サブバンド、色成分等に応じた切り替えを行うことで、さらに制御精度の劣化を抑制でき、画質劣化も抑制することができるようになる。
【００４９】
なお、この実施の形態６は、実施の形態５と同様に、実施の形態１から実施の形態４の場合と比較して、切捨てポイントの候補数を減らすことができるため、除算回数を減らすことができ、処理の高速化を図る効果があることは言うまでもない。また、実施の形態５と同様にレート歪メモリ２０３に記憶する歪データや符号量データの計算も少なくすることができるため、メモリ規模を削減できる効果も得られる。
また実施の形態１から４に示す方法と組み合わせることにより、さらに除算回数を減らすことができ、高速化を図る効果があることは言うまでもない。
【図面の簡単な説明】
【００５０】
【図１】この発明の各実施の形態における画像符号化装置の構成を示すブロック図である。
【図２】同実施の形態１に係るレート制御情報抽出手段とレート制御手段の詳細な構成を示すブロック図である。
【図３】同実施の形態１に係るウェーブレット変換手段で分解レベル２までウェーブレット変換をした時のサブバンドを示す説明図である。
【図４】同実施の形態１に係る係数モデリング手段で変換されたビットプレーンに関する説明図である。
【図５】同実施の形態１に係るエントロピー符号化手段でビットプレーンを符号化パスへ分解する様子を示す説明図である。
【図６】同実施の形態１に係るレート歪メモリのデータ構成を示す説明図である。
【図７】同実施の形態１に係る切捨てポイントを導出する方法を説明するための符号量対歪の関係（ＲＤ曲線）を示す説明図である。
【図８】同実施の形態１に係る切捨てポイントを導出するための最適な符号量対歪の傾き（λ）を計算するフローチャートである。
【図９】符号量対歪の関係が単調減少になっていないＲＤ曲線を示す説明図である。
【図１０】同実施の形態１に係る符号量対歪の傾きを単調減少に補正する手順を示すフローチャートである。
【図１１】同実施の形態１に係る単調減少補正処理の具体的な例を示す説明図である。
【図１２】同実施の形態２に係る符号量対歪の傾きを単調減少に補正する手順を示すローチャートである。
【図１３】この発明の実施の形態２に係る単調減少補正処理の具体的な例を示す説明図である。
【図１４】この発明の実施の形態３に係る符号量対歪の傾きを単調減少に補正する手順を示すフローチャートである。
【図１５】この発明の実施の形態３に係る単調減少補正処理の具体的な例を示す説明図である。
【図１６】この発明の実施の形態４に係る符号量対歪の傾きを単調減少に補正する手順を示すフローチャートである。
【図１７】この発明の実施の形態４に係る単調減少補正処理の具体的な例を示す説明図である。
【図１８】この発明の実施の形態６に係るレート制御情報抽出手段の構成を示すブロック図である。
【図１９】この発明の実施の形態６に係る切捨てポイントの候補について示す説明図である。
【図２０】ウェーブレット変換について示す説明図である。
【図２１】従来の単調減少補正処理の手順を示すフローチャートである。
【符号の説明】
【００５１】
１０１  ウェーブレット変換手段、１０２  量子化手段、１０３  係数モデリング手段、１０４  エントロピー符号化手段、１０５  符号メモリ、１０６  レート制御情報抽出手段、１０７  レート制御手段、２０１  歪計算手段、２０２  符号量計算手段、２０３  レート歪メモリ、３０１  傾き計算手段、３０２  切捨てポイント導出手段、３０３  符号抽出手段、１９０１  切り捨てポイント設定手段。
【図１】
2005109917.tif 000003
【図２】
2005109917.tif 000004
【図３】
2005109917.tif 000005
【図４】
2005109917.tif 000006
【図５】
2005109917.tif 000007
【図６】
2005109917.tif 000008
【図７】
2005109917.tif 000009
【図８】
2005109917.tif 000010
【図９】
2005109917.tif 000011
【図１０】
2005109917.tif 000012
【図１１】
2005109917.tif 000013
【図１２】
2005109917.tif 000014
【図１３】
2005109917.tif 000015
【図１４】
2005109917.tif 000016
【図１５】
2005109917.tif 000017
【図１６】
2005109917.tif 000018
【図１７】
2005109917.tif 000019
【図１８】
2005109917.tif 000020
【図１９】
2005109917.tif 000021
【図２０】
2005109917.tif 000022
【図２１】
2005109917.tif 000023