(57)【要約】  ＤＣＴよりさらに効率的な圧縮を提供しつつも、最小のオーバーヘッド情報を有するイメージ信号の圧縮方式を提供する。ＤＣＴ変換マトリックスの行間と列間との部分的な交換の程度を示すアングル・パラメータに対して、さまざまな値を適用してＤＣＴ変換マトリックスの行間と列間との部分的な交換を行う。かようなＤＣＴ変換マトリックスの修正を介して、さらに効率的な圧縮係数マトリックスを生成する。パラメータとして使われたアングル・パラメータをそのまま保存したり伝送するならば、オーバーヘッドがあまりにも大きくなる。アングル・パラメータのランダム・シーケンスを生成し、シーケンス上のそれぞれのアングル・パラメータに対して、圧縮係数マトリックスを生成して圧縮率を求める過程を反復し、最も高い圧縮率を有するアングル・パラメータを求める。ここで、最も高い圧縮率を有するアングル・パラメータ自体を保存したり伝送せずに、当該アングル・パラメータのランダム・シーケンス上での番号を求め、これを保存したり伝送する。これにより、平均６％ほどの圧縮率上昇をもたらすことができる。
2011502390.tif 000002
【特許請求の範囲】
【請求項１】
イメージ信号を圧縮する方法において、
変換マトリックスの行間と列間との部分的な交換を行う段階と、
前記行間と列間との部分的な交換が行われた変換マトリックスを使用し、圧縮しようとするイメージ信号をＤＣＴ変換する段階と、
前記ＤＣＴ変換されたイメージ信号を圧縮する段階と、
前記変換マトリックスの行間と列間との部分的な交換の程度を示すアングル・パラメータに対してさまざまな値を適用し、前記変換マトリックスの行間と列間との部分的な交換を行うことと、前記圧縮しようとするイメージ信号をＤＣＴ変換することと、前記ＤＣＴ変換されたイメージ信号を圧縮することとを反復遂行し、最も高い圧縮率に対応するアングル・パラメータを選択する段階とを含むことを特徴とするイメージ信号の圧縮方法。
【請求項２】
前記アングル・パラメータは、オイラー・アングルであることを特徴とする請求項１に記載のイメージ信号の圧縮方法。
【請求項３】
前記変換マトリックスの行間と列間との部分的な交換を行う段階は、
前記変換マトリックス左側の前記行間の部分的な交換に該当するマトリックスを乗じ、前記変換マトリックス右側の前記列間の部分的な交換に該当するマトリックスを乗じる段階を含むことを特徴とする請求項１に記載のイメージ信号の圧縮方法。
【請求項４】
前記行間の部分的な交換に該当するマトリックスは、
【数１８】
2011502390.tif 000020
であり、
前記マトリックスで、
【数１９】
2011502390.tif 000021
前記α，β，γは、オイラー・アングルであることを特徴とする請求項３に記載のイメージ信号の圧縮方法。
【請求項５】
前記最も高い圧縮率に対応するアングル・パラメータを選択する段階は、
前記アングル・パラメータに対して、ランダム・シーケンスを生成する段階と、
前記ランダム・シーケンスの値それぞれに対し、前記変換マトリックスの行間と列間との部分的な交換を行うことと、前記圧縮しようとするイメージ信号をＤＣＴ変換することと、前記ＤＣＴ変換されたイメージ信号を圧縮することとを含み、前記イメージ信号に対する圧縮率を求める段階と、
前記ランダム・シーケンスの値それぞれに対して求めた圧縮率のうち、最も高い圧縮率を求める段階と、
前記最も高い圧縮率に対応するアングル・パラメータの値を選択する段階とを含むことを特徴とする請求項１に記載のイメージ信号の圧縮方法。
【請求項６】
前記最も高い圧縮率に対応するアングル・パラメータの値の前記ランダム・シーケンス上の番号を求める段階と、
前記最も高い圧縮率で圧縮されたイメージ信号、及び前記対応するランダム・シーケンス上の番号を保存したり、デコーダ側に伝送する段階をさらに含むことを特徴とする請求項５に記載のイメージ信号の圧縮方法。
【請求項７】
前記アングル・パラメータに対して生成するランダム・シーケンスは、レーマーの擬似乱数であることを特徴とする請求項５に記載のイメージ信号の圧縮方法。
【請求項８】
前記アングル・パラメータに対してさまざまな値を適用し、前記変換マトリックスの行間と列間との部分的な交換を行うことと、前記圧縮しようとするイメージ信号をＤＣＴ変換することと、前記ＤＣＴ変換されたイメージ信号を圧縮することとを反復遂行し、最も高い圧縮率に対応するアングル・パラメータを選択する段階は、
モンテカルロ法を使用し、前記変換マトリックスの行間と列間との部分的な交換を行うことと、前記圧縮しようとするイメージ信号をＤＣＴ変換することと、前記ＤＣＴ変換されたイメージ信号を圧縮することとを反復遂行する段階を含むことを特徴とする請求項１に記載のイメージ信号の圧縮方法。
【請求項９】
前記オイラー・アングルは、０°近くまたは１８０°近くの値を有することを特徴とする請求項２に記載のイメージ信号の圧縮方法。
【請求項１０】
イメージ信号を圧縮する装置において、
変換マトリックスの行間と列間との部分的な交換を行う行間と列間との交換部と、
前記行間と列間との部分的な交換が行われた変換マトリックスを使用し、圧縮しようとするイメージ信号をＤＣＴ変換するＤＣＴ変換部と、
前記ＤＣＴ変換されたイメージ信号を圧縮するイメージ圧縮部と、
前記変換マトリックスの行間と列間との部分的な交換の程度を示すアングル・パラメータに対してさまざまな値を適用し、前記行間と列間との交換部、ＤＣＴ変換部及びイメージ圧縮部を反復動作させ、最も高い圧縮率に対応するアングル・パラメータを選択する制御部とを含むことを特徴とするイメージ信号の圧縮装置。
【請求項１１】
前記アングル・パラメータは、オイラー・アングルであることを特徴とする請求項１０に記載のイメージ信号の圧縮装置。
【請求項１２】
前記行間と列間との交換部は、
前記変換マトリックス左側の前記行間の部分的な交換に該当するマトリックスを乗じ、前記変換マトリックス右側の前記列間の部分的な交換に該当するマトリックスを乗じることを特徴とする請求項１０に記載のイメージ信号の圧縮装置。
【請求項１３】
前記行間の部分的な交換に該当するマトリックスは、
【数２０】
2011502390.tif 000022
であり、前記マトリックスで、
【数２１】
2011502390.tif 000023
前記α，β，γは、オイラー・アングルである特徴とする請求項１２に記載のイメージ信号の圧縮装置。
【請求項１４】
前記制御部は、
前記アングル・パラメータに対して、ランダム・シーケンスを生成し、前記ランダム・シーケンスの値それぞれに対し、前記行間と列間との交換部、ＤＣＴ変換部及びイメージ圧縮部を動作させ、前記イメージ信号に対する圧縮率を求め、前記ランダム・シーケンスの値それぞれに対して求めた圧縮率のうち、最も高い圧縮率を求め、前記最も高い圧縮率に対応するアングル・パラメータの値を選択することを特徴とする請求項１０に記載のイメージ信号の圧縮装置。
【請求項１５】
前記制御部は、
前記最も高い圧縮率に対応するアングル・パラメータの値の前記ランダム・シーケンス上の番号を求め、前記最も高い圧縮率で圧縮されたイメージ信号、及び前記対応するランダム・シーケンス上の番号を保存したり、デコーダ側に伝送することを特徴とする請求項１４に記載のイメージ信号の圧縮装置。
【請求項１６】
前記アングル・パラメータに対して生成するランダム・シーケンスは、レーマーの擬似乱数であることを特徴とする請求項１４に記載のイメージ信号の圧縮装置。
【請求項１７】
前記制御部は、
モンテカルロ法を使用し、前記行間と列間との交換部、ＤＣＴ変換部及びイメージ圧縮部を反復動作させて最も高い圧縮率に対応するアングル・パラメータを選択することを特徴とする請求項１０に記載のイメージ信号の圧縮装置。
【請求項１８】
前記オイラー・アングルは、０°近くまたは１８０°近くの値を有することを特徴とする請求項１１に記載のイメージ信号の圧縮装置。
【請求項１９】
イメージ信号を圧縮する方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体において、
前記イメージ信号圧縮方法は、
変換マトリックスの行間と列間との部分的な交換を行う段階と、
前記行間と列間との部分的な交換が行われた変換マトリックスを使用し、圧縮しようとするイメージ信号をＤＣＴ変換する段階と、
前記ＤＣＴ変換されたイメージ信号を圧縮する段階と、
前記変換マトリックスの行間と列間との部分的な交換の程度を示すアングル・パラメータに対してさまざまな値を適用し、前記変換マトリックスの行間と列間との部分的な交換を行うことと、前記圧縮しようとするイメージ信号をＤＣＴ変換することと、前記ＤＣＴ変換されたイメージ信号を圧縮することとを反復遂行し、最も高い圧縮率に対応するアングル・パラメータを選択する段階とを含むことを特徴とするコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、イメージ信号の圧縮に係り、特に、トランスフォーム・マトリックスの修正（modification  of  transform  matrix）によって圧縮率を向上させるイメージ信号の圧縮方法及び装置に関する。
【背景技術】
【０００２】
ＤＣＴ（discrete  cosine  transform）は、ビデオ、イメージまたはオーディオの圧縮に使われる周知の技術である。最近何年間、さらに効率的なコーディング方式を見出すための多くの試みがあった。オーディオ・コーディングでは、パラメトリック・コーディングがＤＣＴよりさらに良好な結果を示している。二次元（２Ｄ）データについては、ＫＬＴ（Karhunen  Loevetransform）係数が最小ビットインターバルを有するが、オーバーヘッド情報のサイズが非常に大きくなるという問題点がある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明では、ＤＣＴよりさらに効率的な圧縮を提供しつつも、最小のオーバーヘッド情報を有するイメージ信号の圧縮方式を提供するものである。
【課題を解決するための手段】
【０００４】
本発明では、ＤＣＴ変換マトリックスの行間と列間との部分的な交換の程度を示すパラメータに対してさまざまな値を使用し、ＤＣＴ変換マトリックスの行間と列間との部分的な交換を行う。本発明では、かようなパラメータをアングル・パラメータと呼ぶ。かようなＤＣＴ変換マトリックスの修正を介して、さらに効率的な圧縮係数マトリックスを生成する。
【０００５】
使われたアングル・パラメータの値をそのまま保存したり伝送するならば、オーバーヘッドがあまりにも大きくなる。本発明では、アングル・パラメータのランダム・シーケンスを生成し、シーケンス上のそれぞれのアングル・パラメータに対して、圧縮係数マトリックスを生成して圧縮率を求める過程を反復し、最も高い圧縮率を有するアングル・パラメータを求める。ここで、最も高い圧縮率を有するアングル・パラメータ自体を保存したり伝送せずに、当該アングル・パラメータのランダム・シーケンス上での番号を求め、これを保存したり伝送する。
【０００６】
本発明によるイメージ信号圧縮方法は、ＤＣＴ変換マトリックスの行間と列間との部分的な交換を行う段階と、前記行間と列間との部分的な交換が行われたＤＣＴ変換マトリックスを使用し、圧縮しようとするイメージ信号をＤＣＴ変換する段階と、前記ＤＣＴ変換されたイメージ信号を圧縮する段階と、前記ＤＣＴ変換マトリックスの行間と列間との部分的な交換の程度を示すアングル・パラメータに対してさまざまな値を適用し、前記ＤＣＴ変換マトリックスの行間と列間との部分的な交換を行うことと、前記圧縮しようとするイメージ信号をＤＣＴ変換することと、前記ＤＣＴ変換されたイメージ信号を圧縮することとを反復遂行し、最も高い圧縮率に対応するアングル・パラメータを選択する段階とを含むことを特徴とする。
【０００７】
前記アングル・パラメータは、オイラー・アングルであることが望ましい。
【０００８】
前記ＤＣＴ変換マトリックスの行間と列間との部分的な交換を行う段階は、前記ＤＣＴ変換マトリックス左側の前記行間の部分的な交換に該当するマトリックスを乗じ、前記ＤＣＴ変換マトリックス右側の前記列間の部分的な交換に該当するマトリックスを乗じる段階を含むことが望ましい。
【０００９】
前記行間の部分的な交換に該当するマトリックスは、
【００１０】
【数１】
2011502390.tif 000003
であり、前記マトリックスで、
【００１１】
【数２】
2011502390.tif 000004
であり、前記α，β，γは、オイラー・アングルであることが望ましい。
【００１２】
前記最も高い圧縮率に対応するアングル・パラメータを選択する段階は、前記アングル・パラメータに対して、ランダム・シーケンスを生成する段階と、前記ランダム・シーケンスの値それぞれに対し、前記ＤＣＴ変換マトリックスの行間と列間との部分的な交換を行うことと、前記圧縮しようとするイメージ信号をＤＣＴ変換することと、前記ＤＣＴ変換されたイメージ信号を圧縮することとを含み、前記イメージ信号に対する圧縮率を求める段階と、前記ランダム・シーケンスの値それぞれに対して求めた圧縮率のうち、最も高い圧縮率を求める段階と、前記最も高い圧縮率に対応するアングル・パラメータの値を選択する段階とを含むことが望ましい。
【００１３】
前記イメージ信号の圧縮方法は、前記最も高い圧縮率に対応するアングル・パラメータの値の前記ランダム・シーケンス上の番号を求める段階と、前記最も高い圧縮率で圧縮されたイメージ信号、及び前記対応するランダム・シーケンス上の番号を保存したり、デコーダ側に伝送する段階とをさらに含むことが望ましい。
【００１４】
前記アングル・パラメータに対して生成するランダム・シーケンスは、レーマーの擬似乱数（pseudo-random  number）であることが望ましい。
【００１５】
前記アングル・パラメータに対してさまざまな値を適用し、前記ＤＣＴ変換マトリックスの行間と列間との部分的な交換を行う段階と、前記圧縮しようとするイメージ信号をＤＣＴ変換する段階と、前記ＤＣＴ変換されたイメージ信号を圧縮する段階とを反復遂行し、最も高い圧縮率に対応するアングル・パラメータを選択する段階は、モンテカルロ法（Monte  Carlo  method）を使用し、前記ＤＣＴ変換マトリックスの行間と列間との部分的な交換を行う段階と、前記圧縮しようとするイメージ信号をＤＣＴ変換する段階と、前記ＤＣＴ変換されたイメージ信号を圧縮する段階とを反復遂行する段階と含むことが望ましい。
【００１６】
また、前記オイラー・アングルは、０°近くまたは１８０°近くの値を有することが望ましい。
【００１７】
本発明によるイメージ信号圧縮装置は、ＤＣＴ変換マトリックスの行間と列間との部分的な交換を行う行間と列間との交換部と、前記行間と列間との部分的な交換が行われたＤＣＴ変換マトリックスを使用し、圧縮しようとするイメージ信号をＤＣＴ変換するＤＣＴ変換部と、前記ＤＣＴ変換されたイメージ信号を圧縮するイメージ圧縮部と、前記ＤＣＴ変換マトリックスの行間と列間との部分的な交換の程度を示すアングル・パラメータに対してさまざまな値を適用し、前記行間と列間との交換部、ＤＣＴ変換部及びイメージ圧縮部を反復動作させ、最も高い圧縮率に対応するアングル・パラメータを選択する制御部とを含むことを特徴とする。
【００１８】
前記アングル・パラメータは、オイラー・アングルであることが望ましい。
【００１９】
前記行間と列間との交換部は、前記ＤＣＴ変換マトリックス左側の前記行間の部分的な交換に該当するマトリックスを乗じ、前記ＤＣＴ変換マトリックス右側の前記列間の部分的な交換に該当するマトリックスを乗じることが望ましい。
【００２０】
前記制御部は、前記アングル・パラメータに対して、ランダム・シーケンスを生成し、前記ランダム・シーケンスの値それぞれに対し、前記行間と列間との交換部、ＤＣＴ変換部及びイメージ圧縮部を動作させ、前記イメージ信号に対する圧縮率を求め、前記ランダム・シーケンスの値それぞれに対して求めた圧縮率のうち、最も高い圧縮率を求め、前記最も高い圧縮率に対応するアングル・パラメータの値を選択することが望ましい。
【００２１】
また、前記制御部は、前記最も高い圧縮率に対応するアングル・パラメータの値の前記ランダム・シーケンス上の番号を求め、前記最も高い圧縮率で圧縮されたイメージ信号及び対応する前記ランダム・シーケンス上の番号を保存したり、デコーダ側に伝送することが望ましい。
【００２２】
また、前記制御部は、モンテカルロ法を使用し、前記行間と列間との交換部、ＤＣＴ変換部及びイメージ圧縮部を反復動作させて最も高い圧縮率に対応するアングル・パラメータを選択することが望ましい。
【発明の効果】
【００２３】
本発明によるイメージ信号圧縮方法及び装置によれば、イメージ信号自体の圧縮率を向上させると同時に、変換マトリックスを修正するためのパラメータ自体を圧縮するための方式を提供し、オーバーヘッドを減少させる。従って、全体的に保存したり、デコーダ側に伝送せねばならないデータの量が減少する。
【図面の簡単な説明】
【００２４】
【図１】ＤＣＴ変換マトリックスの行間と列間との交換について説明するための図である。
【図２】ＤＣＴ変換マトリックスの行間と列間との交換について説明するための図である。
【図３】オイラー・アングルについて示した図である。
【図４】モンテカルロ法での均一グリッドポイントと擬似ランダムポイントとの比較のための図である。
【図５】本発明の一実施形態によるイメージ信号圧縮装置のブロック図である。
【図６】本発明の一実施形態によるイメージ信号圧縮方法のフローチャートである。
【図７】本発明による圧縮率の上昇を表したグラフである。
【図８】本発明による圧縮率の上昇を表したグラフである。
【発明を実施するための形態】
【００２５】
以下、添付された図面を参照しつつ、本発明によるイメージ信号の圧縮方法及び装置について詳細に説明する。
【００２６】
＜マトリックスの行間と列間との交換＞
本発明では、ＤＣＴ（discrete  cosine  transform）マトリックスの行間と列間との部分的な交換を行う。かようなＤＣＴマトリックスの修正を介して、さらに効率的な圧縮係数マトリックスを生成する。
【００２７】
図１と図２とを参照しつつ、ＤＣＴマトリックスの行間と列間との交換について説明する。
【００２８】
本発明で行間の部分的な交換というのは、行間を全部交換するのではなく、パラメータの値によって部分的に交換することを意味する。
【００２９】
２行の行であるＡとＢとの交換は、パラメータａの値によって、次の式（１）のように定義されうる。
行Ａ（ｎｅｗ）＝ｃｏｓ（ａ）＊行Ａ（ｏｌｄ）＋ｓｉｎ（ａ）＊行Ｂ（ｏｌｄ）
行Ｂ（ｎｅｗ）＝ｓｉｎ（ａ）＊行Ａ（ｏｌｄ）＋ｃｏｓ（ａ）＊行Ｂ（ｏｌｄ）  （１）
式（１）を参照するに、パラメータａ（angle）は、角の役割を行うということが分かる。従って、本発明では、このように、ＤＣＴマトリックスの行間と列間との部分的な交換の程度を示すパラメータをアングル・パラメータと呼ぶ。
【００３０】
パラメータａの値が０°である場合、交換が起こらない場合を意味する。また、パラメータａの値が９０°である場合、行間の全部交換が起こる場合を意味する。
【００３１】
また、パラメータａの値が９０°より大きく、１８０°より小さい値を有する場合、行間の交換と共に、エレメント値の符号（ｓｉｇｎ）が変更される場合を示す。パラメータａの値が１８０°である場合、行間の交換が起こらないが、それぞれの行に含まれたエレメントの符号がいずれも変更される。
【００３２】
本発明で、列間の部分的な交換は、前記行間の部分的な交換のような方式で定義される。
【００３３】
図１は、４ｘ４  ＤＣＴトランスフォーム・マトリックスの場合を示している。図１を参照するに、行間の交換に３つのパラメータα１，α２，α３が使われ、列間の交換に３つのパラメータα４，α５，α６が使われる。
【００３４】
また、図２は、８ｘ８トランスフォーム・マトリックスの場合を示している。図２の場合には、α１，α２，α３，α４，α５，α６が行間の交換に使われておち、α７，α８，α９，α１０，α１１，α１２が列間の交換に使われている。
【００３５】
図１で、パラメータα１，α２，α３の適用順序によって、互いに異なる結果が導き出される。すなわち、３つのパラメータは、互いに独立的ではない。パラメータα１をまず適用し、パラメータα２を適用した場合のマトリックス値と、パラメータα２をまず適用し、パラメータα１を適用する場合のマトリックス値は異なる。
【００３６】
本発明で、マトリックスの行間または列間の交換について詳細に注意深くみれば、三次元上の座標軸の回転と類似していることが分かる。すなわち、３列がそれぞれ三次元座標上のＸ，Ｙ，Ｚ軸に対応する。
【００３７】
三次元上の座標軸の回転においても、どの軸をまず回転させるかによって、結果が変わる。従って、三次元上の座標軸の回転を示す方式について多くの試みがあり、そのうち代表的なものがオイラー・アングル（Euler  angles）である。
【００３８】
＜オイラー・アングル＞
図３は、オイラー・アングルについて示した図である。図３を参照するに、α，β，γの３つの角（angle）がオイラー・アングルを示している。図３で、Ｘ，Ｙ，Ｚ軸は、回転前の座標軸を示し、Ｘ’，Ｙ’，Ｚ’軸は、回転後の座標軸を示す。Ｎ軸は、ＸＹ平面とＸ‘Ｙ’平面との交線（intersection）である。Ｎ軸をline  of  nodesと呼ぶ。
【００３９】
角αは、Ｚ軸を回転軸とするＸ軸とＮ軸との間の角度である。角βは、Ｎ軸を回転軸とするＺ軸とＺ’軸との間の角度である。角γは、Ｚ’軸を回転軸とするＮ軸とＸ’軸との間の角度である。
【００４０】
オイラー・アングルを適用した座標軸の回転をマトリックス形態で示せば、次の式（２）の通りである。
【００４１】
【数３】
2011502390.tif 000005
第１のマトリックスは、Ｚ’軸を回転軸とする回転（rotation  around  Ｚ’）を示す。第２のマトリックスは、Ｎ軸を回転軸とする回転（rotation  around  Ｎ）を示す。第３のマトリックスは、Ｚ軸を回転軸とする回転（rotation  around  Ｚ）を示す。
【００４２】
本発明では、マトリックスの行間と列間との交換を、オイラー・アングルを使用する座標軸の回転で示すことが望ましい。
【００４３】
＜本発明の概要＞
圧縮を効率的に行うための最適のトランスフォーム・マトリックスを見出すことは、パラメータに対する強いノンスムース依存性（strongly  non-smooth  dependence  on  parameter）を有する古典的なマルチパラメータ問題（multi  parameter  problem）である。このような問題を解決するために、モンテカルロ法（Monte  Carlo  method）が使われる。モンテカルロ法におけるランダムポイントの生成には、レーマーの数列（Lemer’s  sequence  number）が使われうる。レーマーの数列を使用することによって、パラメータとして使われるアングル・パラメータ自体を保存したり伝送する代わりに、１つの（整数だけを保存したり伝送できるようになる。従って、使われたパラメータ値をデコーダ側に知らせるために必要なオーバーヘッドが減少する。
【００４４】
すなわち、最適の実施形態で使われるアイテムは、次の通りである。
【００４５】
１．ＤＣＴマトリックスの可逆変換
２．さらに効率的なコーディングのためのエネルギーの再配置
３．レーマーの数を使用した付加される情報の最小化
図１と図２とを再び参照するに、ＤＣＴマトリックスで、回転によって修正される部分は黒色であり、修正されない部分は、白色で示している。図１の４ｘ４トランスフォームブロックでは、６個のアングル・パラメータが行間と列間とのエネルギー再配置による１５個のエレメントの修正を示している。図２の８ｘ８ブロックでは、１２個のアングル・パラメータが６０個のエレメントの修正に関係する。
【００４６】
図１を参照するに、行間の交換において、３個のアングル・パラメータが必要であり、列間の交換においてまた、３個のアングル・パラメータが必要であることが分かる。従って、４ｘ４ブロックにおいては、６個のアングル・パラメータが必要である。
【００４７】
図２を参照するに、行間の交換に、６個のアングル・パラメータが必要であり、列間の交換に、６個のアングル・パラメータが必要である。従って、８ｘ８ブロックにおいては、全１２個のアングル・パラメータが必要である。
【００４８】
＜発明の構造＞
本発明の構造は、次の通りである。
【００４９】
１段階−直交トランスフォーム・ファミリーパラメータ化（orthogonal  transform  family  parameterization）
２段階−モンテカルロ法
３段階−レーマーの擬似乱数（Lemer’s  pseudo-random  numbers）
４段階−最適化されたアングル・パラメータのための変域のローカリゼーション（localization  of  diapason  for  optimal  angle  parameters）
５段階−準最適化されたベーシス（quasi-optimal  basis）
＜発明の動作＞
ビデオ自体の圧縮率を向上させるために追加されるパラメータの数があまりにも多くなるならば、圧縮を使用せずに、ビデオ信号自体を伝送するのがかえって望ましいという状況になる。例えば、４ｘ４ブロックで、イメージ信号を圧縮し、ほぼ０に近いサイズにしたとしても、１６個の追加的なパラメータを必要とするならば、ビデオデータの圧縮のために、何も行う必要がなくなる。なぜならば、これは、１６個のピクセル値をパラメータ自体としてデコーダに伝送するのと同一であるためである。
【００５０】
このように、イメージ信号自体を圧縮すると同時に、追加されるオーバーヘッドを最小化することが望ましいということが分かる。
【００５１】
本発明での目標は、最小限の付加される情報を使用し、ビデオシーケンスを圧縮するためのトランスフォームを最適化することである。
【００５２】
＜１段階−直交トランスフォーム・ファミリーパラメータ化＞
現在のデータトランスフォームを最適化するために、ベーシスを固有に記述するパラメータの集合を決定する必要がある。ベーシスは、トランスフォーム・マトリックスによって表現される。従って、ベーシスの修正は、トランスフォーム・マトリックスの修正によって表現される。
【００５３】
ベーシス修正の主な方法として、ベーシス回転を選択する。本発明で、ベーシスの回転は、アングル・パラメータを使用して行われる。アングル・パラメータを使用したベーシスの回転を、イメージ・トランスフォームの最適化に適用することは、新規アイディアである。本発明で、前記アングル・パラメータは、オイラー・アングルであることが望ましい。しかし、マトリックスの行間と列間との部分的な交換の程度を示すものであるならば、いかなるものでも本発明によるアングル・パラメータになり、従って、本発明によるアングル・パラメータは、オイラー・アングルに限定されるものではない。以下では、オイラー・アングルを使用した実施形態について説明する。
【００５４】
トランスフォーム最適化の観点から、オイラー・アングル回転は、ＤＣＴマトリックスＤの左側積
【００５５】
【数４】
2011502390.tif 000006
及び右側積
【００５６】
【数５】
2011502390.tif 000007
を使用し、次の式（３）のように定義される。
【００５７】
【数６】
2011502390.tif 000008
ここで、Ｄ’は、回転によって修正されたＤＣＴマトリックスである。
【００５８】
マトリックス
【００５９】
【数７】
2011502390.tif 000009
は、ＤＣＴマトリックスＤの行間の交換を行う。マトリックス
【００６０】
【数８】
2011502390.tif 000010
は、ＤＣＴ係数マトリックスＤの列間の交換を行う。
【００６１】
４ｘ４ブロックにおけるマトリックス
【００６２】
【数９】
2011502390.tif 000011
の一例は、次の式（４）のようである。
【００６３】
【数１０】
2011502390.tif 000012
ここで、式（４）で、α，β，γはオイラー・アングルである。
【００６４】
従って、４ｘ４ブロックの場合、オイラー・アングルは、６個のパラメータα１，α２，α３，α４，α５，α６の集合によって、１５個のＤＣＴ係数の修正を記述する。８ｘ８トランスフォームについては、１２個のオイラー・アングルα１，α２，α３，α４，α５，α６，α７，α８，α９，α１０，α１１，α１２が６０個のＤＣＴ係数の修正を記述する。このように、トランスフォーム修正を技術するためのパラメータの縮小を十分に行うことが、提案された発明の第１のアイテムである。
【００６５】
＜２段階−モンテカルロ法＞
自由度が６個のアングル・パラメータ（８ｘ８トランスフォームの場合、１２個のアングル・パラメータ）に減少した後、最適化の問題を、ビット節約の観点から調べる必要がある。すなわち、アングルの集合を選択する方法を最適化せねばならない。
【００６６】
このような最適化問題には、パラメータの高次元ドメイン（６または１２個のアングル・パラメータ）が使われるという点と、イメージの圧縮が使われたパラメータに、ノンスムース（non-smooth）に依存するという点とに困難さがある。このような問題は、伝統的にモンテカルロ法によって解決されたた。
【００６７】
モンテカルロ法の核心を要約すれば、多数の試みを行うことである。すなわち、さまざまなポイントでの関数値（本発明では、圧縮率）を測定し、最も良好なポイントを選択することである。モンテカルロ法では、多次元ドメインでのランダムポイントの品質（quality）が非常に重要である（特に、次元が増加することによって、さらに重要である）。このようなアプリケーションでは、均一グリッド（uniform  grid）ポイントよりも、擬似ランダム（pseudo-random）ポイントがさらに好まれるということが知られている。簡単に２Ｄケースについて述べれば、図４の通りである。
【００６８】
図４の左側には、均一グリッドポイントが図示されており、右側には、擬似ランダム・シーケンスによる最初の１６個のポイントが図示されている。
【００６９】
均一グリッドポイントを使用する場合、モンテカルロ法の１６回の試みにもかかわらず、第１のパラメータ（及び第２のパラメータ）に対し、４個の異なる値しか検査されていない。一方、擬似ランダム・シーケンスを使用する場合、１６回の試みによって、第１のパラメータ（及び第２のパラメータ）に対し、１６個の互いに異なる値を検査している。すなわち、擬似ランダムポイントを使用する場合、１６個の値に対し、第１のパラメータと第２のパラメータとの互いに異なる値について十分に調べることが可能である。特に、パラメータの数が増加することによって、モンテカルロ方式において、均一グリッドポイントよりは、擬似ランダム・シーケンスを使用することが有利であることが容易に分かるのである。
【００７０】
モンテカルロ法は、最適化問題を解決するための効率性を提供するために、非常に重要である。
【００７１】
＜３段階−レーマーの擬似乱数＞
擬似乱数列（pseudo-random  sequence）を生成する方式には、さまざまがある。最も効率的な方式の１つのレーマーの数を使用するのである。これは、人工的に生成される数列であり、均一に分布された実際の乱数に最も近い性質である。レーマーの数列を生成するアルゴリズムは周知であるので、本明細書では、詳細な説明を省略する。本発明で目的とするところを満足するためには、少なくとも１０１３個の反復されないポイントを提供せねばならない。レーマーの数列は、生成アルゴリズムが知られている人工的な数列であるから、デコーダ側で容易に再計算できる。
【００７２】
レーマーの数列を使用することによって、パラメータの集合、すなわちアングル・パラメータを１つの情報（すなわち、ランダム・シーケンス上の番号）を使用してコーディングできる。
【００７３】
六次元または１２次元パラメータドメインで、一つずつランダムポイントを生成し、これを利用して圧縮を行って圧縮率を測定した後、最適のポイントを選択する。最適のパラメータの集合自体を保存したり伝送する代わりに、前記最適のパラメータ・ポイントがシーケンス上で発生した位置に対応する数を保存したり伝送すればよい。
【００７４】
もしモンテカルロ法で、２ｐ個のポイントに対する検査を行ったならば、ｐビットの情報のみをオーバーヘッドとして有することになる。
【００７５】
＜４段階−最適化されたアングル・パラメータのための変域のローカリゼーション＞
本発明の発明者らは、実験を介して、最適化された回転アングルは、０°近くまたは１８０°（πラジアン）近くの値を有するということを発見した。これは、ＤＣＴベーシスが、すでにほぼ最適化された状態であることを示す。
【００７６】
従って、本発明によるアングル・パラメータは、部分的な列間と行間の部分的な交換（オイラー・アングルの場合、０°近くのアングル）を行ったり、部分的な交換及びベーシスエレメントのサインの変更（オイラー・アングルの場合、１８０°近くのアングル）を行う必要があるだけである。
【００７７】
すなわち、本発明で使われるパラメータの変域（diapason）は、ドメインの特定部分に限定されるのであるが、これをローカリゼーション（localization）という。
【００７８】
パラメータの変域に対するローカリゼーションを行うことによって、オーバーヘッドに対するビット数が減少する。図４で、検査せねばならないポイントが特定部分に限定される場合を仮定すれば、検査せねばならない面積が減るということが分かる。単位面積当たり検査するポイントの数が増加することによって圧縮率が向上するが、同じ圧縮率向上のために、ローカリゼーション前後を比較してみれば、ローカリゼーションが適用される場合に検査せねばならないポイントの数が減少することが分かる。
【００７９】
また、検査するポイントの数が固定されているならば（すなわち、オーバーヘッドとして使用するビット数が固定されている場合）、ローカリゼーションが適用される場合、単位面積当たりさらに多くのポイントを検査できるようになるので、圧縮率がより上昇することになる。
【００８０】
＜５段階−準最適化されたベーシス＞
前記１段階ないし４段階の具現によって、あらゆるブロック（４ｘ４または８ｘ８）に対する最適化されたベーシスを選択することが可能になる。高いビットレートでは、ブロック当たり８または１０バイトのオーバーヘッドが追加されうる。ビットレートが低くなる場合、準最適化されたベーシスを選択することが望ましい。
【００８１】
準最適化されたベーシスとは、１つのマクロブロックまたはフレームに含まれたあらゆるブロック、または一部ブロックの集合に対して、同じ回転を適用することを意味する。
【００８２】
それぞれのブロックに対して最適化された回転を適用するならば、イメージ自体に対する圧縮率は上昇するが、オーバーヘッドが増加することになる。
【００８３】
１ブロック、ブロックの集合、１つのマクロブロック、１つのフレームのうち、いずれのブロックグループに対しても同じ回転を適用するについては、多様な実験によって決定されうる。
【００８４】
低いビットレートでは、回転後にブロックの多くの部分で量子化係数値が０になる。従って、かようなブロックに対しては、回転アングル値についての付加情報を伝送する必要がない。
【００８５】
＜実施形態＞
図５は、本発明の一実施形態によるイメージ信号圧縮装置のブロック図である。図５を参照するに、本発明によるイメージ信号圧縮装置１００は、行間と列間との交換部１１０、ＤＣＴ変換部１２０、イメージ圧縮部１３０及び制御部１４０を含むことが望ましい。
【００８６】
行間と列間との交換部１１０は、ＤＣＴマトリックスの行間と列間との部分的な交換を行う。式（３）で見た通り、行間と列間との交換部１１０は、ＤＣＴマトリックスの左側の行間の部分的な交換に該当するマトリックス
【００８７】
【数１１】
2011502390.tif 000013
を乗じ、ＤＣＴマトリックスの右側の列間の部分的な交換に該当するマトリックス
【００８８】
【数１２】
2011502390.tif 000014
を乗じることが望ましいが、これに限定されるものではなく、他の方式でＤＣＴマトリックスの行間と列間との部分的な交換を行うこともできる。
【００８９】
ＤＣＴ変換部１２０は、前記行間と列間との部分的な交換が行われたＤＣＴマトリックスを使用し、圧縮しようとするイメージ信号をＤＣＴ変換する。これを数式で示せば、次の式（５）の通りである。
【００９０】
【数１３】
2011502390.tif 000015
前記式（５）で、Ｄ’は、修正されたＤＣＴマトリックスであり、Ｓは、圧縮しようとするイメージ信号マトリックスである。
【００９１】
イメージ圧縮部１３０は、ＤＣＴ変換されたイメージ信号（前記Ｙ）を圧縮する。
【００９２】
制御部１４０は、アングル・パラメータに対してさまざまな値を適用し、前記行間と列間との交換部１１０、ＤＣＴ変換部１２０及びイメージ圧縮部１３０を反復動作させ（以下、「反復動作」とする）、最も高い圧縮率に対応するアングル・パラメータを選択する。
【００９３】
制御部１４０は、モンテカルロ法を使用し、多数のアングル・パラメータに対して、前記反復動作を遂行し、最も高い圧縮率に対応するアングル・パラメータを選択する。
【００９４】
このために、制御部１４０は、アングル・パラメータに対してランダム・シーケンスを生成し、ランダム・シーケンスの値それぞれに対して前記反復動作を行い、イメージ信号に対する圧縮率を求め、最も高い圧縮率を有するアングル・パラメータの値を選択する。
【００９５】
また、制御部１４０は、オーバーヘッドを減らすために、アングル・パラメータの値を直接保存したり伝送せずに、最も高い圧縮率に対応するアングル・パラメータ値のランダム・シーケンス上の番号（すなわち、位置）を求め、対応する圧縮されたイメージ信号及びランダム・シーケンス上の番号を保存したり、デコーダ側に伝送する。
【００９６】
前述の通り、前記ランダム・シーケンスは、レーマーの擬似乱数であることが望ましい。
【００９７】
図６は、本発明の一実施形態によるイメージ信号圧縮方法のフローチャートである。
【００９８】
まず、レーマーの擬似乱数を生成する（Ｓ２００）。検査するポイントの数を、ｎ個と仮定する。
【００９９】
変数ｉに１からｎまでを代入し、次の動作を反復遂行する。
【０１００】
まず、ｉに１を代入する（Ｓ２０５）。
【０１０１】
レーマーの擬似乱数列で、ｉ番目のアングル・パラメータを選択する（Ｓ２１０）。選択されたアングル・パラメータを使用し、ＤＣＴマトリックスの行間と列間との部分的な交換を行う（Ｓ２２０）。これは式（３）で述べた通りである。
【０１０２】
前記修正されたＤＣＴマトリックスＤ’を使用し、イメージ信号ＳをＤＣＴ変換する（Ｓ２３０）。これは、式（５）で述べた通りである。
【０１０３】
ＤＣＴ変換されたイメージＹを圧縮し、圧縮されたイメージ（compressed  image）
【０１０４】
【数１４】
2011502390.tif 000016
を生成し（Ｓ２４０）、圧縮率
【０１０５】
【数１５】
2011502390.tif 000017
を求める（Ｓ２５０）。
【０１０６】
ｎ番目のポイントであるか否かを確認し（Ｓ２６０）、ｎ個のポイントをいずれも検査していないのであるならば、ｉを１増加し、レーマーの乱数列の次の位置を指定し（Ｓ２７０）、Ｓ２１０ないしＳ２６０を反復遂行する。
【０１０７】
ｎ個のポイントに対して圧縮率をいずれも求めたならば、最も高い圧縮率
【０１０８】
【数１６】
2011502390.tif 000018
を有するｐを求め（Ｓ２８０）、
【０１０９】
【数１７】
2011502390.tif 000019
とｐとを保存したり、デコーダ側に伝送する（Ｓ２９０）。
【０１１０】
＜本発明のメリット＞
１．本発明は、強力な数的基礎に基づく。
２．本発明によるイメージ信号圧縮方式によれば、ビデオ圧縮で、平均して６％レベルの利得をもたらす。低いビットレートでは、最大１６％の利得も可能である。図７及び図８を参照するに、多様なＱＰ及びテストビデオシーケンスについて、８ｘ８ブロックの場合に平均６％、４ｘ４ブロックの場合に平均５．２５％の圧縮率増加をもたらす。
３．実験によれば、本発明を適用する場合、ＰＳＮＲ（peak  signal-to-noise  ratio）が約１００ほどと非常に高い値を得ることができる。従って、ほぼ無損失ビデオコーディングが可能である。
４．量子化エラーをかなり減少させられる。
【０１１１】
＜代替例＞
本発明の一実施形態では、直交トランスフォームに対して、オイラー・アングルをパラメータとして使用した。しかし、前記言及のように、異なるパラメータ化方法がまた、均等例として適用可能である。
【０１１２】
また、パラメータの集合に対して、１つの整数で表現するというアイディアは、ベーシスの回転だけではなく、付加情報の転換を要する他の方法にも適用可能である。
【０１１３】
オーバーヘッドを除外すれば、ベーシス回転によって得ることができる最も高い圧出率上昇は、２０％ほどである。しかし、オーバーヘッドの付加によって圧縮率上昇は、６％ほどとなる。オーバーヘッドをより減らすことによって、圧縮率のゲインは、前記の２０％に接近するであろう。
【０１１４】
本発明は、コンピュータで読み取り可能な記録媒体に、コンピュータ（情報処理機能を有する装置をいずれも含む）が読み取り可能なコードとして具現することが可能である。コンピュータで読み取り可能な記録媒体は、コンピュータシステムによって読み取り可能なデータが保存されるあらゆる種類の記録装置を含む。コンピュータで読み取り可能な記録装置の例としては、ＲＯＭ（read-only  memory）、ＲＡＭ（random-access  memory）、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ保存装置などがある。
【０１１５】
たとえ前記説明が多様な実施形態に適用される本発明の新規特徴に焦点を当てて説明したとしても、本技術分野に熟達した技術を有した当業者ならば、本発明の範囲を外れずに、前記説明された装置及び方法の形態及び細部事項で、多様な削除、代替、及び変更が可能であるということを理解するであろう。従って、本発明の範囲は、前記説明でよりも、特許請求の範囲によって定義されるのである。特許請求の範囲の均等範囲のうちのあらゆる変形は、本発明の範囲に含まれるのである。
【図１】
2011502390.tif 000024
【図２】
2011502390.tif 000025
【図３】
2011502390.tif 000026
【図４】
2011502390.tif 000027
【図５】
2011502390.tif 000028
【図６】
2011502390.tif 000029
【図７】
2011502390.tif 000030
【図８】
2011502390.tif 000031
【国際調査報告】
2011502390.tif 000032
2011502390.tif 000033