持ち上げスキーム

リフティング方式は、ウェーブレットの設計と離散ウェーブレット変換(DWT) の実行の両方を行う手法です。実装では、これらの手順を統合し、ウェーブレット変換を実行しながらウェーブレットフィルターを設計する方が効果的です。これは第 2 世代ウェーブレット変換と呼ばれます。この手法はWim Sweldensによって導入されました。^[1]

リフティング方式は、有限フィルタを使用した離散ウェーブレット変換を一連の基本的な畳み込み演算子、いわゆるリフティングステップに分解し、算術演算の数をほぼ2分の1に削減します。信号境界の処理も簡素化されます。^[2]

離散ウェーブレット変換では、同じ信号に複数のフィルターを別々に適用します。これとは対照的に、リフティング方式では、信号はジッパーのように分割されます。次に、分割された信号全体に 一連の畳み込み累積演算が適用されます。

上の図は、リフティング方式で表現された順方向ウェーブレット変換の最も単純なバージョンを示しています。 は予測ステップを意味し、これは単独で検討されます。 予測ステップでは、ウェーブレット変換のウェーブレット関数を計算します。 これはハイパス フィルターです。 更新ステップでは、スケーリング関数を計算し、より滑らかなデータ バージョンを生成します。 ${\displaystyle P}$

上で述べたように、リフティング方式は双直交ウェーブレットを使用してDWTを実行するための代替手法である。リフティング方式を使用してDWTを実行するには、対応するリフティングおよびスケーリングの手順を双直交ウェーブレットから導出する必要がある。特定のウェーブレットの解析フィルタ（ ）は、まず多相行列で記述される。 ${\displaystyle g,h}$

${\displaystyle P(z)={\begin{bmatrix}h_{\text{even}}(z)&g_{\text{even}}(z)\\h_{\text{odd}}(z)&g_{\text{odd}}(z)\end{bmatrix}},}$

どこ。 ${\displaystyle \det P(z)=z^{-m}}$

多相行列は、解析ローパス フィルタとハイパス フィルタを含む 2 × 2 行列で、それぞれが偶数と奇数の多項式係数に分割され、正規化されます。ここから、行列は一連の 2 × 2 の上三角行列と下三角行列に分解され、それぞれの対角要素は 1 になります。上三角行列には予測ステップの係数が含まれ、下三角行列には更新ステップの係数が含まれます。対角値を除いてすべてゼロで構成される行列を抽出して、スケーリング ステップ係数を導出できます。多相行列は、次の形式に分解されます。

${\displaystyle P(z)={\begin{bmatrix}1&a(1+z^{-1})\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\b(1+z)&1\end{bmatrix}},}$

ここで、は予測ステップの係数であり、は更新ステップの係数です。 ${\displaystyle a}$${\displaystyle b}$

複数の予測ステップと更新ステップ、およびスケーリング ステップを含む、より複雑な抽出の例を以下に示します。は最初の予測ステップの係数、は最初の更新ステップの係数、は 2 番目の予測ステップの係数、は 2 番目の更新ステップの係数、は奇数サンプルのスケーリング係数、 は偶数サンプルのスケーリング係数です。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle d}$${\displaystyle k_{1}}$${\displaystyle k_{2}}$

${\displaystyle P(z)={\begin{bmatrix}1&a(1+z^{-1})\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\b(1+z)&1\end{bmatrix}}{\begin{bmatrix}1&c(1+z^{-1})\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\d(1+z)&1\end{bmatrix}}{\begin{bmatrix}k_{1}&0\\0&k_{2}\end{bmatrix}}.}$

行列理論によれば、多項式要素と1の行列式を持つ任意の行列は、上記のように因数分解できます。したがって、有限フィルタを持つすべてのウェーブレット変換は、一連のリフティングおよびスケーリングステップに分解できます。DaubechiesとSweldensは、リフティングステップの抽出についてさらに詳しく説明しています。^[3]

CDF 9/7変換を実行するには、2つの予測ステップと2つの更新ステップの合計4つのリフティングステップが必要です。リフティング因数分解により、次のフィルタリングステップのシーケンスが実行されます。^[3]

${\displaystyle d_{l}=d_{l}+a(s_{l}+s_{l+1}),}$

${\displaystyle s_{l}=s_{l}+b(d_{l}+d_{l-1}),}$

${\displaystyle d_{l}=d_{l}+c(s_{l}+s_{l+1}),}$

${\displaystyle s_{l}=s_{l}+d(d_{l}+d_{l-1}),}$

${\displaystyle d_{l}=k_{1}d_{l},}$

${\displaystyle s_{l}=k_{2}s_{l}.}$

リフティング方式によるすべての変換は、逆変換が可能です。すべての完全再構成フィルタ バンクは、ユークリッドのアルゴリズムによってリフティング ステップに分解できます。つまり、「リフティング分解可能フィルタ バンク」と「完全再構成フィルタ バンク」は同じものを表します。すべての 2 つの完全再構成フィルタ バンクは、一連のリフティング ステップによって互いに変換できます。理解を深めるために、と が同じ行列式を持つ多相行列である場合、からへのリフティング シーケンスは、遅延多相行列からへのリフティング シーケンスと同じです。 ${\displaystyle P}$${\displaystyle Q}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle I}$${\displaystyle P^{-1}\cdot Q}$

スピードアップは 2 倍です。これは、リフティングが完全再構成フィルタ バンクに制限されているためにのみ可能になります。つまり、リフティングは、完全再構成によって生じる冗長性を何らかの方法で排除します。

変換は、一定のメモリ オーバーヘッドのみで、入力データのメモリ内で即座に実行できます (その場で実行)。

畳み込み演算は、他の演算に置き換えることができます。完全な再構成のためには、加算演算の可逆性のみが関係します。この方法では、畳み込みの丸め誤差を許容でき、ビット正確な再構成が可能です。ただし、数値の安定性は非線形性によって低下する可能性があります。変換された信号が非可逆圧縮のように処理される場合は、この点を考慮する必要があります。再構成可能なフィルタバンクはすべてリフティングステップで表現できますが、リフティングステップの一般的な説明は、ウェーブレットファミリの説明からは明らかではありません。ただし、たとえば、Cohen–Daubechies–Feauveau ウェーブレットの単純なケースでは、リフティングステップの明示的な式があります。

リフティングは、双直交フィルターを修正して、結果として得られる双直交ウェーブレットの消失モーメントの数を増やし、できれば安定性と規則性を高めます。消失モーメントの数を増やすと、信号が規則的な領域でのウェーブレット係数の振幅が減少し、よりスパースな表現が生成されます。ただし、リフティングで消失モーメントの数を増やすと、ウェーブレットのサポートも増加します。これは、孤立した特異点によって生成される大きな係数の数を増やすという悪影響があります。各リフティング ステップでは、フィルターの双直交性は維持されますが、リース境界、つまり結果として得られるウェーブレット双直交基底の安定性は制御されません。基底が直交している場合、デュアル基底は元の基底と同じです。したがって、元の基底に類似したデュアル基底を持つことは、安定性の指標となります。結果として、デュアル ウェーブレットの消失モーメントが元のウェーブレットと同じで、サポートのサイズが類似している場合、安定性は一般に向上します。このため、リフティング手順ではデュアル ウェーブレットの消失モーメントの数も増加します。また、デュアル ウェーブレットの規則性も向上します。リフティング設計は、消失モーメントの数を調整することで計算されます。結果として得られる双直交ウェーブレットの安定性と規則性は、最善の結果が得られることを期待して事後的に測定されます。これが、このウェーブレット設計手順の主な弱点です。

一般化リフティングスキームは、ジョエル・ソレとフィリップ・サレンビエによって開発され、ソレの博士論文で発表されました。^[4]これは古典的なリフティングスキームに基づいており、スキーム構造に隠された制限を打ち破ることで一般化されています。古典的なリフティングスキームには、3種類の操作があります。

1. 遅延ウェーブレット変換は、信号を で示される奇数サンプル信号と で示される偶数サンプル信号の 2 つの新しい信号に分割します。${\displaystyle f_{j}[n]}$${\displaystyle f_{j}^{o}[n]}$${\displaystyle f_{j}^{e}[n]}$
2. 予測ステップでは、偶数サンプルに基づいて奇数サンプルの予測を計算します (またはその逆)。この予測が奇数サンプルから減算され、エラー信号が作成されます。${\displaystyle g_{j+1}[n]}$
3. 更新ステップでは、サブサンプリング中にエネルギーの一部が除去され、低周波ブランチが再調整されます。従来のリフティングの場合、これは次の予測ステップのために信号を「準備」するために使用されます。予測された奇数サンプルを使用して偶数サンプルを準備します(またはその逆)。この更新は偶数サンプルから減算され、 で表される信号が生成されます。${\displaystyle g_{j+1}[n]}$${\displaystyle f_{j}^{e}[n]}$${\displaystyle f_{j+1}[n]}$

この方式は、その構造上、可逆です。受信機では、更新ステップが最初に計算され、その結果が偶数サンプルに加算され、次にまったく同じ予測を計算して奇数サンプルに追加することができます。元の信号を復元するには、遅延ウェーブレット変換を反転する必要があります。一般化リフティング方式には、同じ 3 種類の操作があります。ただし、この方式では、従来のリフティングで使用されていた加算と減算の制限が回避されますが、これにはいくつかの影響があります。たとえば、すべてのステップの設計で、方式の可逆性を保証する必要があります (加算と減算の制限が回避された場合は保証されません)。

一般化リフティング スキームは、次の規則に従う 2 項変換です。

1. 入力を偶数サンプルのストリームと奇数サンプルの別のストリームにデインターリーブします。これは、遅延ウェーブレット変換と呼ばれることもあります。
2. 予測マッピングを計算します。このステップでは、偶数サンプルを考慮して奇数サンプルを予測します (またはその逆)。 のサンプル空間から のサンプル空間へのマッピングがあります。この場合、の参照として選択されたサンプル ( から) はコンテキストと呼ばれます。これは次のように表現できます。 ${\displaystyle f_{j}^{e}[n]}$${\displaystyle g_{j+1}[n]}$${\displaystyle f_{j}^{e}[n]}$${\displaystyle f_{j}^{o}[n]}$

   ${\displaystyle g_{j+1}[n]=P(f_{j}^{o}[n];f_{j}^{e}[n])。}$

3. 更新マッピングを計算します。このステップでは、奇数の予測サンプルを考慮して偶数サンプルを更新します。これは、次の予測ステップ（ある場合）の準備のようなものになります。次のように表現できます。

   ${\displaystyle f_{j+1}[n]=U(f_{j}^{e}[n];g_{j+1}[n]).}$

明らかに、これらのマッピングは関数にはなり得ません。スキーム自体の可逆性を保証するためには、変換に含まれるすべてのマッピングが可逆でなければなりません。マッピングが有限集合（離散的な有界値信号）上で発生して到着する場合、この条件はマッピングが単射（1対1）であると言うことと同等です。さらに、マッピングが1つの集合から同じ基数の集合に向かう場合、マッピングは全単射でなければなりません。

一般化されたリフティング スキームでは、マッピングにこのステップを含めることで加算/減算の制限を回避します。このようにして、古典的なリフティング スキームが一般化されます。

予測ステップマッピングにはいくつかの設計が開発されている。更新ステップの設計は、更新ステップが正確にどの程度役立つのかがまだ不明であるため、十分に検討されていない。この技術の主な用途は画像圧縮である。^{[5] [6] [7]}や^{[8]など、興味深い参考文献がある。}

• 整数を整数にマッピングするウェーブレット変換
• ビット精度再構成によるフーリエ変換^[9]
• 必要な数の平滑化係数と消失モーメントを持つウェーブレットの構築
• 与えられたパターンにマッチしたウェーブレットの構築^[10]
• JPEG 2000における離散ウェーブレット変換の実装
• データ駆動型変換、例えばエッジ回避ウェーブレット^[11]
• 非分離格子上のウェーブレット変換、例えば五点形格子上の赤黒ウェーブレット^[12]

• 暗号学におけるFeistel方式は、データを分割し、関数の適用と加算を交互に行うというほぼ同じ考え方を採用しています。 Feistel 方式とリフティング方式の両方で、これは対称暗号化と復号化に使用されます。

• リフティングスキーム – 因数分解アルゴリズムの簡単な説明
• リフティングスキームの紹介
• 高速リフティングウェーブレット変換