(57)【要約】      （修正有）【課題】算術符号化の時間を短縮する。【解決手段】映像圧縮方法に関するもので、圧縮対象であるフレームを多数のコードブロックに分けて、各コードブロックは連続的な多数のコーディングパスを有し、各コードブロックで前記コーディングパスを順にエンコーディングしてコーディングビット数と歪みの傾きを計算及び格納し、前記傾きが所定の基準値より小さい時まで前記コーディングパスの順序を順に増加させて少なくとも一つの前記コードブロックに含まれた全てのコーディングパスをエンコーディングしない、映像圧縮方法を提供する。【選択図】図５ａ
2007325262.tif 000002
【特許請求の範囲】
【請求項１】
圧縮対象であるフレームを多数のコードブロックに分け、各コードブロックは連続的な多数のコーディングパスを有し、
各コードブロックで前記コーディングパスを順にエンコーディングしてコーディングビット数と歪みの傾きを計算及び格納し、前記傾きが所定の基準値より小さくなるまで前記コーディングパスの順序を順に増加させ、少なくとも一つの前記コードブロックに含まれた全てのコーディングパスをエンコーディングしない、映像圧縮方法。
【請求項２】
(a)多数の連続するフレームのうちk番目のフレームを多数のコードブロックに分け、各コードブロックは連続的なコーディングパスを有し、前記kは1より大きい正の整数である段階と、
(b)各コードブロックで前記コーディングパスを順にエンコーディングしてコーディングビット数と歪みの傾きを計算及び格納し、前記傾きがk-1番目のフレームの基準値より小さくなるまで前記コーディングパスの順序を順に増加させる段階と、
(c)全てのコーディングパスの前記傾きのうち最も大きな値と最も小さな値をそれぞれ最大値及び最小値として格納する段階と、
(d)前記最大値と最小値の平均を求める段階と、
(e)各コードブロックのコーディングパスの順序を順に増加させながら各コーディングパスの前記傾きと前記平均を比較し、前記傾きが前記平均より大きいか同じになるまで前記コーディングパスの順序を増加させる段階と、
(f)前記傾きが前記平均より大きいか同じ時の前記コーディングパスの順序を基準に各コードブロックの切断点を決定する段階と、
(g)全てのコードブロックの切断点までエンコーディングし、コーディングされたビット数を格納する段階と、
(h)前記コーディングされたビット数が前記目標ビット数より小さければ、前記平均値に前記最大値をアップデートし、前記コーディングされたビット数が前記目標ビット数より大きければ、前記平均値に前記最小値をアップデートする段階と、
(i)前記段階(d)〜前記段階(h)を複数回繰り返して前記平均をアップデートし、アップデートされた平均を前記k番目のフレームの基準値として格納する段階とを備える、映像圧縮方法。
【請求項３】
前記段階(a)は、
(a1)前記k番目のフレームをウェーブレット変換して多数のサブバンドに分解する段階と、
(a2)前記サブバンドのうち一つのサブバンドを前記コードブロックに分ける段階とを備える、請求項２に記載の映像圧縮方法。
【請求項４】
前記切断点は前記傾きが前記平均より大きいか同じ時の前記コーディングパスより先の順序のコーディングパスの端部に決定される、請求項２に記載の映像圧縮方法。
【請求項５】
前記段階(a)以前に、
(p1)多数の連続するフレームのうち最初のフレームを多数のコードブロックに分け、前記各コードブロックは連続的なコーディングパスを有する段階と、
(p2)前記最初のフレームの各コードブロックの全てのコーディングパスを順にエンコーディングしてコーディングビット数と歪みの傾きを計算及び格納する段階と、
(p3)前記段階(p2)の実行後、前記段階(c)以後の段階を実行する段階をさらに備える、請求項２に記載の映像圧縮方法。
【請求項６】
前記段階(b)後、
(b1)各コードブロックで前記傾きがk-1番目のフレームの基準値より小さい時、k-1番目のフレームとk番目のフレームの互いに対応するコードブロックにおいてそれぞれエンコーディングされずに残ったコーディングパスの第1総ビット数と第2総ビット数を求める段階と、
(b2)前記第1総ビット数と前記第2総ビット数の差がパス終了許容値より小さいか同じであれば、前記コーディングパスの順序を一つ増加させ、前記段階(b)以後の段階を実行する段階とをさらに備える、請求項２〜５のいずれかに記載の映像圧縮方法。
【請求項７】
前記段階(b)後、
(b3)全てのコードブロックでエンコーディングされたパスまでの映像の総コーディングビット数と目標ビット数の差が前記目標ビット数の基準率より大きいかを判断する段階と、
(b4)前記差が前記目標ビット数の基準率より小さければ前記段階(c)を実行し、前記差が前記基準率より大きければ、前記総コーディングビット数が前記目標ビット数より大きいかを判断する段階と、
(b5)前記総コーディングビット数が前記目標ビット数より大きければ前記段階(c)を実行し、前記総コーディングビット数が前記目標ビット数より小さければ前記k-1番目のフレームの基準値を減少させ、前記段階(b)以後の段階を実行する段階とをさらに備える、請求項２〜５のいずれかに記載の映像圧縮方法。
【請求項８】
前記段階(b)後、
(b1)各コードブロックで前記傾きがk-1番目のフレームの基準値より小さい時、k-1番目のフレームとk番目のフレームの互いに対応するコードブロックでそれぞれエンコーディングされずに残ったコーディングパスの第1総ビット数と第2総ビット数を求める段階と、
(b2)前記第1総ビット数と前記第2総ビット数の差がパス終了許容値より小さいか同じであれば、前記コーディングパスの順序を一つ増加させ、前記段階(b)以後の段階を実行する段階とをさらに備える、請求項７に記載の映像圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は映像圧縮方法に関し、特にEBCOT（Embedded Block Coding with Optimized Truncation)を用いて映像を圧縮する方法に関する。
【背景技術】
【０００２】
EBCOTを用いる標準圧縮方式としてはJPEG（joint photographic expert group)2000がある。JPEG2000は静止画像はもちろん動画像と医療映像の圧縮のためにも用いられる。次世代映像圧縮標準であるJPEG2000は以前の映像圧縮標準と比較して圧縮性能は向上したが、圧縮方式が非常に複雑で相対的に大きい計算量を要求する。特に、JPEG2000で採用するEBCOTは高性能の算術符号化（encoding)方式でアルゴリズムが非常に複雑で、これを用いた算術符号化時間はエンコーディング時間全体の45％〜60%程度を占める圧縮時間を増加させる問題がある。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は圧縮性能は維持しながら算術符号化対象になるコーディングパスの数を減らして圧縮時間を減少させることができる映像圧縮方法を提供することにその目的がある。
【課題を解決するための手段】
【０００４】
前述した目的を達成するために、本発明の映像圧縮方法は、圧縮対象であるフレームを多数のコードブロックに分け、各コードブロックは連続的な多数のコーディングパスを有し、各コードブロックで前記コーディングパスを順にエンコーディングしてコーディングビット数と歪みの傾きを計算及び格納し、前記傾きが所定の基準値より小さくなるまで前記コーディングパスの順序を順に増加させ、少なくとも一つの前記コードブロックに含まれた全てのコーディングパスをエンコーディングしないことを特徴とする。
【０００５】
本発明による映像圧縮方法は、（a)多数の連続するフレームのうちk番目のフレームを多数のコードブロックに分け、各コードブロックは連続的なコーディングパスを有し、前記kは1より大きい正の整数である段階；（b)各コードブロックで前記コーディングパスを順にエンコーディングしてコーディングビット数と歪みの傾きを計算及び格納し、前記傾きがk-1番目のフレームの基準値より小さくなるまで前記コーディングパスの順序を順に増加させる段階；（c)全てのコーディングパスの前記傾きのうち最も大きい値と最も小さい値をそれぞれ最大値及び最小値として格納する段階；（d)前記最大値と最小値の平均を求める段階；（e)各コードブロックのコーディングパスの順序を順に増加させながら各コーディングパスの前記傾きと前記平均を比較し、前記傾きが前記平均より大きいか同じになるまで前記コーディングパスの順序を増加させる段階；（f)前記傾きが前記平均より大きいか同じ時の前記コーディングパスの順序を基準に各コードブロックの切断点を決定する段階；（g)全てのコードブロックの切断点までエンコーディングし、コーディングされたビット数を格納する段階；（h)前記コーディングされたビット数が前記目標ビット数より小さければ、前記平均値に前記最大値をアップデートし、前記コーディングされたビット数が前記目標ビット数より大きければ、前記平均値に前記最小値をアップデートする段階；及び（i)前記段階（d)〜前記段階（h)を複数回繰り返して前記平均をアップデートし、アップデートされた平均を前記k番目のフレームの基準値として格納する段階を含む。
【発明の効果】
【０００６】
本発明は2番目以後のフレームからは算術符号化の対象となるコーディングパスの数を減らしてより効率的にエンコーディングを進行することができる。従って、目標ビット数に関係なく一定の時間がかかる従来のPCRDとは異なり、目標ビット数が小さい場合には、エンコーディングの時間を多く減少させることができる。
【発明を実施するための最良の形態】
【０００７】
以下、本発明によるEBCOTを用いた映像圧縮方法をより具体的に説明する。
【０００８】
図１に示された通り、多数のピクセルのピクセル値で表現される原本映像（フレーム)10を互いに重ならない多数のタイル（Tile1-Tile4)に分ける（Tiling)。各タイル（Tile1-Tile4)は多数のタイルピクセル（tile pixels)を含む。離散ウェーブレット変換（discrete wavelet transformation、以下、DWTという)を実行して各タイルを多数のサブバンド（LL1、HL1、LH1、HH1、HL2、LH2、HH2)に分解する（decomposing)。サブバンドを示す記号のうち最初のアルファベットは水平方向に適用されるフィルタを意味し、2番目のアルファベットは垂直方向に適用されるフィルタを意味し、数字はレベル、即ち、変換回数を示す。DWT回数は設定によって変わることがある。
【０００９】
図２に示されたように、多数のサブバンドのうち一つのサブバンド、望ましくはLLサブバンドを多数のコードブロック（B0-Bn)に分割する（partitioning)。圧縮性能を向上させるために各コードブロック内のウェーブレット変換されたフレームのピクセル値（ウェーブレット係数)を量子化させ（quantizing)、量子化されたピクセル値x（n)を符号ビット（sign bit)z（n)とmビットデータam-1，am-2，・・・，a1，a0に分解する。符号ビットz（n)とビットデータam-1，am-2，・・・，a1，a0はそれぞれ次の式１及び式２のように定義される。
【００１０】
【数１】
2007325262.tif 000003
【００１１】
【数２】
2007325262.tif 000004
【００１２】
式２でビットデータam-1はm-1ビット平面の係数値を示す。
【００１３】
式２のように各コードブロック内のピクセル値をビットデータに分解して同一ビット次数に該当するビットデータを合せて係数ビットを得て、各コードブロックをm個のビット平面（bit plane)に分解する。ビット平面は各コードブロック（B0〜Bn)の量子化されたピクセル値の同一ビット次数に該当するデータを有するピクセルの集合である。例えば、コードブロックBnを分解して得たビット平面（BnP0〜BnPm-2)のうちビット平面BnPm-2はam-2ビットデータを有するピクセルの集合である。
【００１４】
図３は一つのコードブロックで最上位ビット（most significant bit、以下MSBという)平面から最下位ビット（Least Significant Bit、以下LSBという)平面に至るビット平面を示している。
【００１５】
図４に示されている通り、MSB平面を除いた全てのビット平面は連続する3つのコーディングパスa、b、cのうち一つにエンコーディングされる。ここで、「a」、「b」、「c」はそれぞれ重要伝搬パス（significant propagation pass)、細密化パス（refinement pass)及び整理パス（clean up pass)を示す。ni（以下、iは1からnまでの自然数)番目のコーディングパスの端部は切断点（truncation point)ziの候補になる。決定された切断点の後のコーディングパスはエンコーディング過程で無視される。
【００１６】
2007325262.tif 000005
【００１７】
【数３】
2007325262.tif 000006
【００１８】
2007325262.tif 000007
【００１９】
映像全体の歪みDは次の式４のように示される。
【００２０】
【数４】
2007325262.tif 000008
【００２１】
2007325262.tif 000009
【００２２】
【数５】
2007325262.tif 000010
【００２３】
実際にコーディングされたビット数Rを増加させずに歪みDを減らすことはできない。即ち、コーディングビット数Rを減少させれば歪みDが増加する。従って、究極的な目的は、コーディングビット数Rを目標コーディングビット数Rtargetに近づけながら歪みDを減少させることである。このような問題は式６のようなラグランジ演算を用いた方程式を最小化させることと同じである。次の式６でラグランジ乗数（Lagrange multiplier)λを見出すことによって、R=Rtargetを満たして歪みDを最小化させることができるコーディングパスの集合Ni={ni（λ)}i=1,2…を求めることができる。
【００２４】
【数６】
2007325262.tif 000011
【００２５】
2007325262.tif 000012
【００２６】
【数７】
2007325262.tif 000013
【００２７】
コードブロックBiのNiから、最適ラグランジ乗数λoptimalを基準に切断点zi（λoptimal)は次の式８のように決定される。
【００２８】
【数８】
2007325262.tif 000014
【００２９】
2007325262.tif 000015
【００３０】
以下、本発明の実施例による映像圧縮方法を詳細に説明する。
【００３１】
[第1実施例]
図５ａ及び５ｂに示された通り、連続する多数のフレームのうち現在のフレーム（k番目のフレーム)の入力を受ける（S110)。k番目のフレームをウェーブレット変換して多数のサブバンドに分け（dividing)、各サブバンドを順序が定められた多数のコードブロックに分解する（S120)。前述したように各コードブロックは各ビット平面に分解され、連続する多数のコーディングパスを有する。
【００３２】
2007325262.tif 000016
【００３３】
2007325262.tif 000017
【００３４】
2007325262.tif 000018
【００３５】
続いて、現在のフレームが最後のフレームであるかを判断する（S171)。最後のフレームであれば終了し、最後のフレームでなければk=k+1に設定し（S172)、k番目のフレームの入力を要請し（S173)、段階S110に戻る。
【００３６】
2007325262.tif 000019
【００３７】
[第2実施例]
2007325262.tif 000020
【００３８】
2007325262.tif 000021
【００３９】
[第3実施例]
前述した実施例1で目標ビット数とコーディングビット数を比較して切断点を決定することもできる。図７を参照して本発明の第3実施例を説明する。
【００４０】
段階S167でi番目のコードブロックが最後のコードブロックであれば、全てのコードブロックでエンコーディングされたコーディングパスまでの総映像のビット数Rと目標ビット数Rtargetの差の絶対値が目標ビット数のr％より小さいか同じであるかを判断する（S169)。即ち、次の式９のように目標ビット数Rtargetに対するコーディングビット数Rと目標ビット数Rtargetの差が目標ビット数Rtargetの基準率r％より大きいかを判断する。
【００４１】
【数９】
2007325262.tif 000022
【００４２】
PCRDの最適化を用いて切断点ziを決定する場合にもコーディングビット数を目標ビット数に正確に合せることができないので、目標ビット数のr％程度の誤差は無視することを意味する。本発明の実施例によってr％は3%になれない。
【００４３】
2007325262.tif 000023
【００４４】
[第4実施例]
前述した実施例3でも現在のフレームと以前のフレームの該当コードブロックのエンコーディングされないパスの総ビット数を比較して切断点の決定を制御することができる。以下図９を参照し、本発明の第4実施例を説明する。
【００４５】
2007325262.tif 000024
【００４６】
本発明の第4実施例によって目標ビット数とコーディングビット数とを比較するだけでなく、現在のフレームと以前のフレームとのコーディングパスの総ビット数を比較して切断点を決定することによって、迅速性を保障しながらも映像の画質低下をより効果的に防止することができる。
【００４７】
前述した実施例は本発明の原理を応用した多様な実施例の一部を示したものに過ぎないことを理解しなければならない。本技術分野において通常の知識を有する者は本発明の本質から逸脱することなく様々な変形が可能であることを明確に分かるはずである。
【００４８】
本発明の好適な実施の形態について説明し、例示したが、本発明の特許請求の範囲の思想及び範疇を逸脱することなく、当業者は種々の改変をなし得ることが分かるであろう。
【図面の簡単な説明】
【００４９】
【図１】ウェーブレット変換過程を示す概略図である。
【図２】多数のコードブロックに分割されるサブバンドを示す概略図である。
【図３】コードブロックとビット平面の関係を示す概略図である。
【図４】ビット平面、コーディングパス及び切断点の関係を示す概略図である。
【図５ａ】本発明の第1実施例による映像圧縮方法を示す順序図である。
【図５ｂ】本発明の第1実施例による映像圧縮方法を示す順序図である。
【図６】本発明の第2実施例による映像圧縮方法を示す順序図である。
【図７】本発明の第3実施例による映像圧縮方法を示す順序図である。
【図８】本発明の第4実施例による映像圧縮方法を示す順序図である。
【図１】
2007325262.tif 000025
【図２】
2007325262.tif 000026
【図３】
2007325262.tif 000027
【図４】
2007325262.tif 000028
【図５ａ】
2007325262.tif 000029
【図５ｂ】
2007325262.tif 000030
【図６】
2007325262.tif 000031
【図７】
2007325262.tif 000032
【図８】
2007325262.tif 000033