u½¬26N EF[ubg_ÆHwÖÌpv\eWi2014/11/12Åj

全文

(1)平成 26 年度数学協働プログラム・ワークショップ. ウェーブレット理論と工学への応用. OKU & ISM 2014 Workshop. Wavelet theory and its applications to engineering. 主催：大阪教育大学，統計数理研究所場所：大阪教育大学天王寺キャンパス日程：平成 26 年 11月 7日（金）13:00 ー 18:00 平成 26 年 11月 8日（土） 9:00 ー 13:00.

(2)

(3) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 開催趣旨. ワークショップ「ウェーブレット理論と工学への応用」では，広い意味でウェーブレット解析によって解決できるかもしれないと期待できるトピックスに関して，講演者の方々に理論と工学的応用の現状，さらに解決すべき問題を解説していただき，その問題提起を端緒として参加者がディスカッションする形で，ウェーブレット解析が実際にどのように応用されているかをより深く理解することによって，新しい理論と応用への道が開かれることを目指します．. 1.

(4) 2. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. .

(5) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. ウェーブレット理論と工学への応用プログラム平成 26 年 11 月 6 日 – 8 日大阪教育大学天王寺キャンパス西館第 5 講義室平成 26 年 11 月 6 日（木）13:00 – 17:00 ウェーブレット相談会ならびに個別討論. 平成 26 年 11 月 7 日（金）13:00 – 18:00. 13:00–13:10. 開催の挨拶. 座長：上原伊音（株式会社シグマ）. 13:10–14:10. 藤ノ木健介（東海大学）. リフティングウェーブレットと信号解析．．．．．．．．．．．．７リフティングは双直交性を保証する自由度の高いウェーブレットの設計手法である．得られたフィルタは完全再構成条件を満たすが，しかしフーリエ変換が有界にならない場合もあり，ウェーブレットについても必ずしも Riesz 基底になるとは限らない．本講演では，リフティング構成による様々なウェーブレット（フィルタ）の導出法を実例を用いながら解説し，その際に生じる問題等を提起するとともに，信号解析への応用の可能性について議論する．. 座長：木下保（筑波大学）. 14:25–15:25 章忠，嶋末昂祐，戸田浩，三宅哲夫（豊橋技術科学大学） Meyer ウェーブレットを用いたリフティングスキームによる複素数離散ウェーブレット変換３１複素数離散ウェーブレット変換 (CDWT) は完全シフト不変性の特性を持つ離散ウェーブレット変換（DWT) の一種である．CDWT は実数部と虚数の２つで構成されるために，計算量が通常の. DWT の２倍以上となっている．計算量を削減する方法として，計算手法を従来の多重解像度解析からリフティングスキームへと変更することは有効であると考えられる．しかしリフティングスキームはこれまでコンパクトサポートのウェーブレットにのみ対応している．本研究では，コンパクトサポートのない Meyer ウェーブレットでのリフティングスキームを設計し，CDWT に適用させて変換処理の高速化を図る．さらにこの手法の問題点と改善について議論する．. 座長：藤田景子（富山大学）. 15:40–16:40. 岡康之（釧路高専）. シュワルツの核型定理と時不変連続線形システムについて．．．．．．．４７シュワルツの核型定理と時不変連続線形システムについて，シュワルツの核型定理と超関数の話題を中心に講演する．芦野―萬代―守本は，急減少関数を入力信号，緩増加超関数を出力信号と見なし，シュワルツの核型定理をシステム同定の枠組みで記述し，その核関数のウェーブレット解析を行っている．本講演では，芦野らによる理論を群上の超関数に拡張する．今後解決すべき課題は，群上のシステムと工学との関係であり，それに関して参加者の意見を伺いたい．. 3.

(6) 4. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 座長：藤ノ木健介（東海大学）. 16:55–17:55 新井康平（佐賀大学）薬草識別のためのウェーブレット．．．．．．．．．．．．．８３画像から抽出する情報として (1) 色，濃淡等スペクトル情報，(2) テクスチャー，形状，サイズ等空間情報，(3) 意味論的概念的関係情報がある．本講演では上述の (1) を従来手法によって抽出し，加えて (2) の情報をウェーブレットに基づき，屋外においてデジタルカメラによって撮像した草花の写真を用いて薬草を検知する手法を提案する．. 懇親会参加希望者は，１０月３１日までに，幹事の富山大学・藤田景子さん. e-mail：[email protected] にお知らせ下さい．平成 26 年 11 月 8 日（土）9:00 – 13:00 座長：芦野隆一（大阪教育大学）. 9:00–10:00 佐藤創（元専修大学）コンパクトサポートをもつウェーブレットの補間・補外に関するパラメータ領域における考察９９音声・画像データなどのウェーブレット変換に用いるウェーブレットの多くは既知のものに固定されているが，あるクラスのウェーブレット全体をパラメータ表現できれば，中間的なウェーブレットを連続的に得ることが容易となる．JSIAM 2013 で発表された２つの直交ウェーブレットに関する補間法の研究（木下・福田）はこの目的に沿ったものである．本報告ではローパス・フィルターの係数列が４項であるパラメータ領域において，この補間法がどのような特徴をもつかを考察する．係数列が６項の場合への拡張，非直交ウェーブレットへの拡張も試みる．. 座長：松浦勉（群馬大学）. 10:15–11:15 川崎秀二（岩手大学），木戸元之（東北大学）地震解析のための海底変位計測のウェーブレット相関法．．．．．．．．１１５地震予測のための有用な情報として，海底面の変位 [m] の計測が行われている．基本的手法は，観測船から海底設置トランスポンダへデータを送信し，トランスポンダからの返信波と元の送信波との相関をとることで観測船での受信時刻を示す相関ピークを時間軸上で得ようとするものである．この手法だけでは，精確なピークを得ることが難しい．これに対し，送信波・受信波それぞれのウェーブレット係数の相関をとれば，ピークが先鋭化され精確な受信時刻を特定することができることを報告する．. 座長：萬代武史（大阪電気通信大学）. 11:30–12:30 岡田正已，森田正紀（首都大学東京）不規則サンプリング補間と近似誤差の数理．．．．．．．．．．．１２７全平面に不規則に散らばった点集合上で，ある関数 [信号] の値 [データ] が観測されたときに，それらの値をサンプリング補間する関数をできるだけよく再現する一般的な方法が知られている．まずそれを概説してから，次に，不規則な点集合が無限集合のときに，自然に一般化されるためのいくつかの数学的側面がわかってきたので，それらを述べたい．.

(7) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 大阪教育大学天王寺キャンパス西館第 5 講義室〒 543-0054 大阪市天王寺区南河堀町 4-88 電話番号 (06)6775-6611. JR 天王寺駅，地下鉄天王寺駅，近鉄大阪阿部野橋駅下車，徒歩約 10 分． JR 寺田町駅下車，徒歩 5 分． http://osaka-kyoiku.ac.jp/. 統計数理研究所数学協働プログラム. http://coop-math.ism.ac.jp/. 運営責任者守本晃（大阪教育大学情報科学）. e-mail: [email protected] tel: 072-978-3665 http://www.osaka-kyoiku.ac.jp/~morimoto/TENWS/ws2014HP/ 芦野隆一（大阪教育大学数理科学）. e-mail: [email protected] tel: 072-978-3685 http://www.osaka-kyoiku.ac.jp/~ashino. 5.

(8) 6. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering.

(9) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. リフティングウェーブレットと信号解析藤ノ木健介東海大学理学部概要.. リフティングは双直交性を保証する自由度の高いウェーブレットの設計手法である．得られた双直交フィルタは完全再構成条件を満たすが，しかしながら必ずしも Riesz 基底になるとは限らない．ウェーブレットについても，モーメント消滅条件は制御できるが，基底関数の正則性や安定性は保証されない．本講演では，リフティング構成による様々なウェーブレット（フィルタ）の導出法を実例を用いながら解説し，その際に生じる問題等を上記を中心に提起するとともに，信号解析への応用の可能性について議論する．. Lifting Wavelets and Signal Analysis Kensuke Fujinoki School of Science, Tokai University Abstract.. The lifting scheme allows to construct biorthogonal wavelet filters with perfect reconstruction. The resulting filter are guaranteed to be biorthogonal, but associated wavelets do not always form a Riesz basis. While the lifting construction can control the number of vanishing moments of wavelets, the regularity and stability of bases are not guaranteed. This article attempts to describe a method to construct biorthogonal wavelets by the lifting scheme, and show bottlenecks in this lifting-based construction. Application to the field of signal processing is also discussed.. 1. はじめにリフティング（lifting）[20, 21] とは完全再構成フィルタ（perfect reconstruction filter），あるいは双直交ウェーブレットとスケーリング関数を双直交性を保ったまま修正することである．任意の双直交フィルタによる離散ウェーブレット変換はリフティングの繰り返しにより実装することができるため，Mallat 変換 [16] の高速実装を与えることから. JPEG2000 の符号化方式に採用されている [1]．このリフティング構成（lifting scheme）の特徴は，フィルタやウェーブレットの設計において従来では不可欠なフーリエ変換を用いる必要がない点である．このため，第二世代ウェーブレット（例えば [6, 22]）と呼ばれる有界領域，不規則標本化領域，サーフェイス等の多様体など，フーリエ変換の定義が困難な一般領域におけるのウェーブレットの構成と多重解像度解析の形成を可能とする [25]．しかしながら，リフティングの本質を理解するためにはフーリエ領域での考察が必要となる．そこで本稿では，内容を従来の第一世代ウェーブレットに限定して，空間（時間）領域，フーリエ領域の多角的な視点からリフティングの本質に迫り，その際に関連する解決すべき課題等を提起し，信号解析への応用と展望について述べる．. 1. 7.

(10) 8. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 2. 空間領域におけるリフティング 2.1 Haar 変換まず次のような変換を考えるところからはじめる．解像度レベル j ∈ Z の離散信号. {c j [k]}k∈Z が与えられた時，信号の偶数成分 c j [2k] と奇数成分 c j [2k + 1] を使って， c j [2k] + c j [2k + 1] 2 d j−1 [k] = −c j [2k] + c j [2k + 1] c j−1 [k] =. (2.1). と分解する．c j−1 [k] は平均成分，d j−1 [k] は差分成分となっており，各成分の信号長（解像度）は半分になっている．それぞれを近似成分，詳細成分と表現することもあるが，これを Haar 変換と呼ぶこととする．ただし，通常の Haar 変換とは正規化係数が異なることに注意しよう．これはいわば線形変換として. (2.2). 1/2 1/2 c j [2k] c j−1 [k] = d j−1 [k] −1 1 ck [2k + 1]. と書くことができ，逆変換は. d j−1 [k] 2 d j−1 [k] c j [2k + 1] = c j−1 [k] + 2 c j [2k] = c j−1 [k] −. で与えられる．逆変換を導くためには (2.2) の逆行列を求める必要があるし，行列が複雑な場合はフーリエ変換を要する．. 2.2 リフティングリフティングでは，まず信号を 2 つの独立な組に分けて扱う [23]．1 次元信号 {c j [k]}k∈Z ではすなわち偶数番地と奇数番地が候補として考えられるから，それぞれを. c j,e [k] := c j [2k],. c j,o [k] := c j [2k + 1]. と置く．これをスプリット（split）と呼ぶ（Lazy ウェーブレット変換とも呼ばれる）．ここで，c j,o [k] を隣接する c j,e [k] を使って予測（predict）することを考える．最も簡単な予測作用素（predictor, predict operator）は 1 次の場合で，単純に c j,e [k] そのものを使う一定予測（constant prediction）である．予測は正確でなくてもよく，その予測誤差を d j−1 [k] として c j,o [k] と置き換える：. (2.3). c j,o [k] → d j−1 [k] = c j,o [k] − c j,e [k] 2.

(11) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. c j,o [k] を戻すには単純に c j,o [k] = d j−1 [k] + c j,e [k]. (2.4). とすればよい．もしよい予測作用素を選べば予測誤差 d j−1 [k] はスパースになるが，一定予測の場合は信号が一定であれば d j−1 [k] は 0 になるし，局所的に変動しているときは予測誤差は増大する．つまり，予測は信号の偶数番地と奇数番地における相関を見ていると解釈でき，次数が 1 次の場合は信号の 0 次相関を消滅させる．予測によって信号は. . c j,e [k], c j,o [k] → c j,e [k], d j−1 [k]. と置き換わったが，c j [k] の平均値は変化しておりスプリットの影響も受けてエイリアシングも生じている．そこで，アップデート（update）では c j,e [k] に隣接する c j,o [k]（今は予測誤差 d j−1 [k]）を使って c j,e [k] を平滑化された c j−1 [k] に置き換える：. c j,e [k] → c j−1 [k] = c j,e [k] +. (2.5). d j−1 [k] 2. これも逆変換. c j,e [k] = c j−1 [k] −. (2.6). d j−1 [k] 2. が成り立つのは明らかである．アップデートは平均を保持するように定めるのが普通である．ここでは d j−1 [k]/2 としたが，アップデートの右辺を c j,e [k] + (c j,o [k] − c j,e [k])/2 とすれば，そこから平均. (2.7). . c j [k] =. k. 1 c j−1 [k] 2 k. が求まることがわかる．こうして予測とアップデートによって信号は. . predict update c j,e [k], c j,o [k] −→ c j,e [k], d j−1 [k] −→ c j−1 [k], d j−1 [k]. と変換されたが，実は最終的に得られた結果は Haar 変換 (2.1) のそれに他ならない．しかし，リフティングの場合は変換式の構造上，逆変換 (2.4), (2.6) が容易に成り立つことが決定的に異なる．さらに，偶数成分と奇数成分を平均と詳細に置き換え（in-place）することにより計算できるため計算効率がよい．これは，計算機で実装した際に. c j,e [0]. c j,o [0]. c j,e [1]. c j,o [1]. ↓ predict c j,e [0]. c j,e [1]. dj−1 [0]. dj−1 [1]. ↓ uddate cj−1 [0]. d j−1 [0]. cj−1 [1]. 3. d j−1 [1]. 9.

(12) 10. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. のようにひとつの配列サイズを固定して演算を実現でき，メモリ消費を抑えられる実装上の利点がある．つまり，c j−1 [k], d j−1 [k] として新たな変数を用いなくても信号の偶数番地と奇数番地だけを用いて上書き演算することが可能である．たとえば，C 言語風に書くと. odd − = even; even + = odd; であり，メモリの制約などがある小型ハードウェアへの実装時などに有利である．. 2.3 線形予測次にもう少し複雑な予測，2 次の場合の線形予測（linear prediction）を考える．つまり，. c j,o [k] を近傍の c j,e [k] の平均 c j,e [k] + c j,e [k + 1] /2 として予測する．もし信号が偶数番地間で区分的に線形であれば予測は成功し，信号の 1 次相関を消滅させる．しかし必ずしもその必要はなく，予測誤差を詳細成分として保存する．. c j,o [k] → d j−1 [k] = c j,o [k] −. (2.8). 1 c j,e [k] + c j,e [k + 1] 2. c j,e [k] をアップデートしてスムースにするためには 1 次の場合と同様に c j,e [k] の近傍の c j,o [k]（今は d j−1 [k]）を使って (2.9) c j−1 [k] = c j,e [k] + A d j−1 [k − 1] + d j−1 [k] とする．ここで，A は定数であり，. . 1 1 c j−1 [k] = c j,e [k] + A c j,o [k − 1] − c j,e [k − 1] + c j,e [k] + c j,o [k] − c j,e [k] + c j,e [k + 1] 2 2 1 = 1 − A c j,e [k] + A c j,o [k − 1] + c j,o [k] − A c j,e [k − 1] + c j,e [k + 1] 2 であるから平均 (2.7) を保持するように. k. 1 c j [k] = 1 − 2A c j,e [k] + 2A c j,o [k] = c j−1 [k] 2 k k k. c j−1 [k] は結局 12 k (c j−1,e [k] + c j−1,o [k]) とわけれるから A = 1/4 となる．なおこの選択は 1 次のモーメント 1 k c j [k] = k c j−1 [k] 2 k k. を解いて定める．ここで. 1 2. k. も保持する．従って，予測 (2.8) をアップデート (2.9) に代入すれば線形予測のアップデートは実際には. c j−1 [k] =. 1 3 1 c j,e [k] + c j,o [k − 1] + c j,o [k] − c j,e [k − 1] + c j,e [k + 1] 4 4 8 4.

(13) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 11. を計算していることになるが，これは 2 次の次数を持つ CDF(2,2)，または 5/3 双直交ウェーブレットフィルタ [5]. 1 1 3 1 1 h[k] = {− , , , , − } 8 4 4 4 8 による離散ウェーブレット変換から得られる平均成分 c j−1 [k] に他ならない．Haar 変換の場合と同様に，同じ結果が異なる計算方法で得られているわけである．. 2.4 リフティング構成以上をまとめると，予測作用素を p，アップデート作用素を u として，リフティングは次の 3 ステップで記述できる．. 1. スプリット：信号を偶数番地と奇数番地にわける． c j,e [k] := c j [2k] c j,o [k] := c j [2k + 1]. (2.10). 2. 予測：予測作用素 p を c j,e に適用して，c j,o [k] を予測する．その予測誤差を詳細成分として保存する．. (2.11). c j,o [k] → d j−1 [k] = c j,o [k] − p(c j,e )[k]. 3. アップデート：アップデート作用素 u により，予測結果 d j−1 を用いて c j,e をアップデートする．. (2.12). c j,e [k] → c j−1 [k] = c j,e [k] + u(d j−1 )[k]. 4. 正規化（option）：エネルギーの正規化 c j 2 = c j−1 2 + d j−1 2 等が必要であれば， c j−1 [k] と d j−1 [k] を定数 K で正規化する． (2.13). c j−1 [k] = K c j−1 [k] d j−1 [k] = 1/K d j−1 [k]. 上記の各リフティングステップにおいて，予測とアップデートを反転させて実行すれば. c j [2k] = c j,e [k] = c j−1 [k] − u(d j−1 )[k] c j [2k + 1] = c j,o [k] = d j−1 [k] + p(c j,e )[k] となり，c j [2k], c j [2k + 1] をマージすればもとの信号を得ることができる．Haar と線形予測の例で観測したとおり，ローパスフィルタ {h[k]}k∈Z とハイパスフィルタ {g[k]}k∈Z の畳. 5.

(14) 12. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. +. c j-1. K. 1/K. Merge. Split. dj-1. 1/K. +. K. (a). -. 2. 2. LP. + -. 2. HP. 2. (b). Fig. 1. 離散ウェーブレット変換．(a) リフティング構成．(b) Mallat 変換．. み込み演算による通常の Mallat 変換. c j−1 [k] =. . h[l − 2k]c j [l]. l. (2.14). d j−1 [k] = c j [k] =. (2.15). . . g[l − 2k]c j [l]. l. ˜h[k − 2l]c j−1 [l] + g˜ [k − 2l]d j−1 [l]. l. に比べて，リフティングは計算効率がよいことがわかる．実際，Mallat の分解アルゴリズム (2.14) は畳み込み. (h ∗ c j )[k] =. . h[ − k] c j []. . にダウンサンプリングを組み合わせた形で表現できるが，. c j−1 [k] = (h ∗ c j )↓ [k] = (h ∗ c j )[2k] =. . h[ − 2k] c j []. . 計算結果の半分は捨てられてしまう．さらに，リフティングでは信号の再構成のために双. ˜ 対フィルタ {h[k], g˜ [k]}k∈Z を新たに設計する必要もないため，逆変換の柔軟性においても優れていることがわかる（Fig. 1 参照）．問題は，よい予測作用素 p とアップデート作用素 u をどのように決定するかである．リフティング構成の構造上，どのような p と u を設定しても，逆変換が成り立つことから，設計の自由度は極めて高いといえる．予測の結果を評価するには，詳細成分 d j−1 [k] のス. 6.

(15) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 13. パース性で議論するというひとつの基準があるが，たとえば，これまでに紹介した予測次数が 1 次の場合の一定予測 (2.3) は Haar 変換となり，信号が区分的に一定であれば予測は成功したといえる．2 次の線形予測（linear prediction）(2.8) は信号を 1 次多項式に見立ててそれを補間する形で予測を実行することで，CDF(2,2) フィルタとは異なる計算過程を与える．このように多項式補間を基にした方法を用いれば，3 次予測（cubic prediction）の場合は. (2.16) (2.17). −c j,e [k − 1] + 9 c j,e [k] + 9 c j,e [k + 1] − c j,e [k + 2] p c j,e [k] = 16 −d j−1 [k − 2] + 9 d j−1 [k − 1] + 9 d j−1 [k] − d j−1 [k + 1] u d j−1 [k] = 32. で与えらえる．得られる結果は N = 4 次の Deslauriers and Dubuc (DD) ウェーブレット変換のそれと等価となり，関連するスケーリング関数 φ(t) ∈ L2 (R) は N − 1 次多項式を復元する補間関数となる．任意の次数 N を求めるには，L ≥ 1, N = 2L においてラグランジュの補間法 (Lagrange. interpolation) [18] を基にして (−1) (2.18). pN [k] =. k+L−1. 2L

(16). (L + 1/2 − n). n=1. (L − k)! (L − 1 + k)! (k − 1/2). ,. −L < k ≤ L. と置き，この結果を利用して. p¯ N [k] u [k] = , 2. N. ≤N N. と定めることで得られる．ここで， p[k] ¯ = p[−k] である．このラグランジュ補間をもとにしたリフティングの予測 (2.18) を補間予測（interpolaing prediction）と呼ぶが，この方式から得られるフィルタは，既に 3 次予測の場合で見たように，N 次の Deslauriers–Dubuc フィルタ [8, 9] となる．. 3. 完全再構成フィルタリフティングを直感的に概観するには空間領域での説明が適しているといえるが，より詳しい構造に触れるためにはフーリエ領域での議論が必要となる．そのための準備として，本節ではまずは Mallat 変換のフーリエ領域での表現を考え，次にポリフェーズ表現を導入する．. 7.

(17) 14. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 3.1 Mallat アルゴリズム信号のフーリエ変換を. cˆ j (ω) =. . c j [k] e−iωk. k∈Z. として，標準的な離散ウェーブレット変換に用いられる Mallat の分解アルゴリズム. (2.14) は (3.1). 1 ∗ cˆ j−1 (2ω) cˆ j (ω) = M (ω) cˆ j (ω + π) dˆ j−1 (2ω) 2. ∗ (ω) はモジュレーション行列（modulation matrix）M(ω) と表現できる．ここで M の複素共役であり，双対行列とあわせて. ˆ h(ω) M(ω) = gˆ (ω). ˆ + π) h(ω , gˆ (ω + π). ˆ˜ ˆ˜ + π) h(ω) h(ω. M(ω) = gˆ˜ (ω) gˆ˜ (ω + π). と定義される．逆変換は. . T (2ω) c ˆ cˆ j (ω) j−1 (ω) =M cˆ j (ω + π) dˆ j−1 (2ω). で与えられるが，信号の再構成を保証するためには完全再構成条件 T (ω) M ∗ (ω) = 2I M. (3.2). ˆ˜ gˆ˜ } を完全再構成フィルタ ˆ gˆ , h, が満たされなければならない．このようなフィルタの組 {h, と呼ぶ．. 3.2 ポリフェーズ表現ポリフェーズ表現（polyphase representation）はフィルタバンクを扱う上での極めて効率的な表現のひとつである．基本的なアイディアは信号を偶数と奇数の独立な成分として扱うことであり，これは本質的にリフティングのスプリットそのものである．ローパスフィルタを. hˆ e (ω) =. . h[2k] e−iωk ,. hˆ o (ω) =. k∈Z. . h[2k + 1] e−iωk. k∈Z. ˆ と分割して，それぞれのフーリエ変換も同様に分割すれば，h(ω) のポリフェーズ表現 ˆ h(ω) = hˆ e (2ω) + e−iω hˆ o (2ω) 8.

(18) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. LP. 2. 2. + 2. HP. 2. Fig. 2. ポリフェーズ表現での離散ウェーブレット変換. ˆ が与えられる．h(ω) の周期性から (3.3). ˆ 1 h(ω) ˆh(ω + π) = 1. e−iω. . e−i(ω+π). hˆ e (2ω) hˆ e (2ω) = U(ω) ˆ hˆ o (2ω) ho (2ω). −1 を使ってこれを逆に解けばが得られるが，U(ω) (3.4). 1 1 hˆ e (2ω) = iω hˆ o (2ω) 2 e. . 1 ei(ω+π). . ˆ h(ω) ˆh(ω + π). であり，関係式. ˆ ˆ + π) h(ω) + h(ω hˆ e (2ω) = , 2. ˆ ˆ + π) h(ω) − h(ω hˆ o (2ω) = 2 e−iω. を得る．さらに (3.3) より，Mallat アルゴリズム (3.1) は. . cˆ j−1 (ω) c ˆ (ω) j,e † = P(ω) cˆ j,o (ω) dˆ j−1 (ω). † はポリフェーズ行列とポリフェーズ形式で表現できる（Fig. 2）．ここで，P(ω) (3.5). hˆ (ω) P(ω) = ˆ e ho (ω). gˆ e (ω) gˆ o (ω). のエルミート共役である．Mallat の分解アルゴリズムを利用すれば，ポリフェーズ行列とモジュレーション行列の関係式. (3.6). 1 ∗ † = M (ω) U(ω) P(2ω) 2. (3.7). † ∗ (ω) = P(2ω) U(ω)† M. が導かれる．. . も双対フィルタ {h˜ e , h˜ o , g˜ e , g˜ o } を用いて (3.5) と同様に定義双対ポリフェーズ行列 P(ω). する．双対モジュレーション行列は. (3.8). T . (ω) = U(ω) P(2ω) M. 9. 15.

(19) 16. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. から得られる．信号の再構成は. . cˆ j−1 (2ω) cˆ j,e (2ω) . = P(2ω) ˆ cˆ j,o (2ω) d j−1 (2ω). で与えられるため，従ってポリフェーズ領域での完全再構成条件 (3.2) は. †. P(ω) P(ω) =I. (3.9) . † のユニタリ行列の場合は直交（ユニタリ）フィルと表現できる．ここで，P(ω) = P(ω) T. . † (ω)−1 の場合は双直交フィルタになる．タが得られ，P(ω) =P. 4. ポリフェーズ領域でのリフティング 4.1 一定予測（Haar） √ ˆ˜ ˆ Haar ウェーブレットフィルタ h(ω) = h(ω) = (1 + e−iω )/ 2, gˆ (ω) = gˆ˜ (ω) = (−1 + √ e−iω )/ 2 のポリフェーズ行列は 1 1 1 hˆ ∗e (ω) hˆ ∗o (ω) † = √ P(ω) = ∗ gˆ e (ω) gˆ ∗o (ω) 2 −1 1 で与えられる．これは直交行列になっている．前節で見たように Mallat アルゴリズムを使って信号の分解を. . 1 1 1 cˆ e, j (ω) cˆ j−1 (ω) = √ dˆ j−1 (ω) 2 −1 1 cˆ o, j (ω). のようにフーリエ領域で定義できるが，ここでポリフェーズ行列が. (4.1). ⎛√ ⎜⎜⎜ 2 cˆ j−1 (ω) ⎜⎝ = 0 dˆ j−1 (ω). ⎞ 0 ⎟⎟⎟ 1 ⎟ √1 ⎠ 0 2. 1 0 cˆ e, j (ω) 1 −1 1 cˆ o, j (ω) 1 2. . の形に因数分解できることに注目する．つまり，右辺において左から順に対角行列と，対角成分が 1 の上三角と下三角行列とに分解できる．直交・双直交行列の行列式は 1 であるが，分解後の各行列の行列式も明らかに 1 である．これらの行列の性質から，逆行列が必ず存在することにも着目すると，逆変換は. . ⎞ ⎛ 1 0 ⎟⎟⎟ cˆ j−1 (ω) 0 1 − 12 ⎜⎜⎜ √2 ⎜ √ ⎟⎠ ˆ 1 0 1 ⎝0 2 d j−1 (ω) ⎞ ⎛ˆ ⎜⎜⎜h˜ e (ω) gˆ˜ e (ω)⎟⎟⎟ 1 1 −1. T ⎟⎟⎠ = P(ω) = ⎜⎜⎝ ˆ = √ = P(ω) 1 1 ˜ he (ω) gˆ˜ o (ω) 2. cˆ e, j (ω) 1 = cˆ o, j (ω) 1. となる．. 10.

(20) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 式 (4.1) を一部展開して時間領域に変換して考えると. ⎛√ ⎜⎜ 2 c j−1 [k] = ⎜⎜⎝ d j−1 [k] 0. . ⎞ ⎞⎛ d [k] 0 ⎟⎟⎟ ⎜⎜⎜⎜c j,e [k] + j−1 ⎟⎟⎟⎟ ⎟ ⎜⎝ 2 ⎟⎟⎠ √1 ⎠ ⎜ c j,o [k] − c j,e [k] 2. となるが，これは空間領域でのリフティングによる Haar 変換 (2.5)，(2.3) に一致する（正規化は異なることに注意）．つまり，リフティングはポリフェーズ行列を (4.1) の形に分解することに対応しており，左から順にスケーリング，アップデート，予測の各リフティングステップを表している．. 4.2 線形予測線形予測は空間領域において. 1 c j,e [k] + c j,e [k + 1] 2 1 update : c j,e [k] → c j−1 [k] = c j,e [k] + d j−1 [k − 1] + d j−1 [k] 4. predict : c j,o [k] → d j−1 [k] = c j,o [k] −. で与えられるが，ポリフェーズ形式で書くと，予測ステップは. . ⎛ ⎞ ⎛ 1 ⎜⎜⎜ cˆ e, j (ω) ⎟⎟⎟ ⎜⎜⎜ cˆ e, j (ω) ⎟⎟⎠ = ⎜⎜⎜ 1 + eiω → ⎜⎜⎝ ⎝− cˆ o, j (ω) dˆ j−1 (ω) 2. ⎞ 0⎟⎟ ⎛⎜cˆ e, j (ω)⎞⎟ ⎟⎟⎟ ⎟⎟⎟ ⎜⎜⎜ ⎠ ⎟⎝ ⎠ 1 cˆ o, j (ω). であり，cˆ o, j (ω) → dˆ j−1 (ω) に置き換わる．一方アップデート. ⎛ ⎞ ⎞ ⎛ ⎛ ⎜⎜⎜ cˆ e, j (ω) ⎟⎟⎟ ⎜⎜⎜cˆ j−1 (ω)⎟⎟⎟ ⎜⎜⎜⎜1 ⎜⎜⎝ ⎟⎟⎠ → ⎜⎜⎝ ⎟⎟⎠ = ⎜⎜⎜ ⎝ ˆ ˆ d j−1 (ω) d j−1 (ω) 0. ⎞⎛ ⎞ 1 + e−iω ⎟⎟⎟ ⎜⎜ cˆ e, j (ω) ⎟⎟ ⎟⎟⎟ ⎜ ⎟⎜ ⎟⎠ 4 ⎟⎟⎟⎠ ⎜⎜⎝ ˆ d j−1 (ω) 1. により cˆ e, j (ω) → cˆ j−1 (ω) へと置き換わる．スケーリング K =. . ⎛ ⎞ ⎛√ ⎜⎜⎜cˆ j−1 (ω)⎟⎟⎟ ⎜⎜ 2 cˆ e, j (ω) ⎟⎟⎠ = ⎜⎜⎝ → ⎜⎜⎝ cˆ o, j (ω) 0 ˆ d j−1 (ω) . ⎞ ⎛⎜ ⎟⎟⎟ ⎜⎜⎜1 ⎟ ⎜⎜ 1 √ ⎠⎜ ⎝ 2 0 0. √. 2 も入れてまとめると，. ⎞⎛ 1 1 + e−iω ⎟⎟⎟ ⎜⎜ ⎟⎟⎟ ⎜⎜⎜ 1 + eiω 4 ⎟⎠ ⎜⎝− 1 2. ⎞ 0⎟⎟ ⎛⎜cˆ e, j (ω)⎞⎟ ⎟⎟⎟ ⎟⎟⎟ ⎜⎜⎜ ⎠ ⎟⎝ 1⎠ cˆ o, j (ω). であり，関係式 (3.4) と (3.7) を用いて. ⎛√ ⎞⎛ ⎛ ⎞ −i2ω ⎞ ⎛ 1 ⎟⎟⎟ ⎜⎜⎜ ⎜⎜⎜cˆ j−1 (2ω)⎟⎟⎟ 1 ⎜⎜⎜⎜ 2 0 ⎟⎟⎟⎟ ⎜⎜⎜⎜1 1 + e ⎟ ⎜ ⎜⎝ ⎟ ⎟⎠ = ⎜⎜⎝ ⎟ ⎜ ⎜ ⎟⎜ ⎟⎠ ⎜⎝ 1 + ei2ω 4 √1 ⎠ ⎝ 2 0 − dˆ j−1 (2ω) 0 1 2 2 ⎛ ∗ ⎞ ∗ ˆ ˆ (ω) c ˆ ⎜ ⎟ 1 ⎜h (ω) h (ω + π)⎟⎟ j ⎟⎠ = ⎜⎜⎝ ∗ ∗ 2 gˆ (ω) gˆ (ω + π) cˆ j (ω + π). 11. ⎞⎛ 0⎟⎟ ⎜⎜ 1 ⎟⎟⎟ ⎜⎜⎜ ⎟⎜ 1⎠ ⎝eiω. ⎞ 1 ⎟⎟ cˆ j (ω) ⎟⎟⎟ ⎟⎠ ei(ω+π) cˆ j (ω + π). 17.

(21) 18. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. となるから，CDF(2,2) フィルタの伝達関数. (4.2). −ei2ω + 2eiω + 6 + 2e−iω − e−i2ω hˆ ∗ (ω) = , √ 4 2. gˆ ∗ (ω) =. −1 + 2eiω − ei2ω √ 2 2. ˆ˜ ˆ˜ + π) = 2 ˆ˜ を得る．双対フィルタは h(ω) + hˆ ∗ (ω + π)h(ω = −e−iω gˆ ∗ (ω + π) として hˆ ∗ (ω)h(ω) . † を満たすように設計されるが，リフティングの場合は P(ω) = P(ω). −1. として同様の手順. を踏めば完全再構成条件 (3.9) を満たす双対フィルタが容易に得られる．. 4.3 ポリフェーズ行列の分解ポリフェーズ表現での Haar と線形予測の場合における事情を整理すると，リフティングはポリフェーズ行列を以下の形式に因数分解することに対応する．. (4.3). K † P(ω) = 0. m 0

(22) 1 0 1/K i=1. uˆ i (ω) 1 0 1 pˆ i (ω) 1. ここで，K 0 は定数であり，pˆ i (ω) と uˆ i (ω) は三角多項式である（より一般性を持たせるため pˆ i (ω) に符号はつけていない）．m = 1 の場合は Haar と線形予測で見たように補間予測の場合に対応する．この形は逆行列が必ず存在することも明らかである．. (4.4). † −1 = . P(ω) P(ω) =. 1

(23) i=m. 1 − pˆ i (ω). 0 1 1 0. . −ûi (ω) 1. 1/K 0. 0 K. . ˜ g˜ ) Daubechies and Sweldens によりコンパクトサポートを持つ（双）直交フィルタ (h, g, h, によって構成されたポリフェーズ行列は，必ず pˆ i (ω) と uˆ i (ω) を要素に持つ対角成分が 1 の上・下三角行列の形 (4.3) に分解できることが知られている [7]．したがって，各リフティングステップの行列式は常に 1 であり，もともと（双）直交フィルタで構成されたの行列式も 1 であることから，リフティングは det P(ω) を変えない変換であること P(ω) がわかる．また，ポリフェーズ行列の分解過程において，上・下三角行列の対角成分を 1 とすることで，空間領域における偶数成分と奇数成分の置き換え（in-place）演算が実現できる．このような elementary 行列を用いたサブバンド変換は信号処理におけるフィルタバンクの分野では ladder 構造 [14, 19] として知られており，パラユニタリフィルタバンク方式（paraunitary filter bank implementation）とも呼ばれる．各係数 pi [k], ui [k] はスモールサポート（典型的な係数は 2 個）を持ち，ローラン多項式として表現された既存フィルタに対してユークリッドの互除法を用いることで導出される．しかし，多項式の割り算は必ずしもユニークには決まらず，複数の因数分解の形が得られることもある [10, 24]．. 12.

(24) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 5. リフティングによるウェーブレットの修正前節では既存フィルタがポリフェーズ領域においてリフティング形式でどのように表現されるかについて述べた．空間領域におけるリフティングの予測，アップデートはポリフェーズ領域で (4.3) の形で表現することができ，その結果離散ウェーブレット変換のパラユニタリフィルタバンク方式での実装方法を与える．本節では既存フィルタに対して予測とアップデートをさらに適用することで，双直交性を保ったままフィルタを修正できるリフティングのもう一つの側面を示す．なおこれ以降用いる予測とアップデートは必ずしも空間領域の概念とは異なる場合もある．このため，予測をリフティング，アップデートを双対リフティングと呼ぶ文献もあるが，本稿では混乱を防ぐためにこれまで通りの名称を採用する．. ∗ (ω) = ポリフェーズ行列 P(ω) からフィルタ係数 {h, g} を得るには (3.7) より M. † U(ω)† とすればよいが，予測によりフィルタは P(2ω) 1 0 hˆ ∗e (2ω) hˆ ∗o (2ω) 1 hˆ ∗ (ω) hˆ ∗ (ω + π) = − p(2ω) ˆ 1 gˆ ∗e (2ω) gˆ ∗o (2ω) eiω gˆ ∗ (ω) gˆ ∗ (ω + π). 1. . ei(ω+π). となるから，{h, g} → {h, g p } へと修正される．. . ˆ ˆ h(ω) h(ω) = ˆ gˆ p (ω) gˆ (ω) − h(ω) pˆ ∗ (2ω) T. . ˜ g˜ } の場合は (3.8) の M. (ω) = U(ω) P(2ω) 双対フィルタ {h, より，予測行列の逆行列を用いて. ⎛ ˆ˜ ⎜⎜⎜ h(ω) ⎜⎜⎝ ˆ˜ + π) h(ω. ⎞ ⎛ 1 e−iω ⎜⎜⎜⎜hˆ˜ e (2ω) g˜ˆ (ω) ⎟⎟⎟⎟ ⎜ ⎟⎠ = 1 e−i(ω+π) ⎝hˆ˜ o (2ω) gˆ˜ (ω + π). ⎞ g˜ˆ e (2ω)⎟⎟⎟⎟ 1 0 ⎟⎠ ˆ 1 gˆ˜ o (2ω) p(2ω). ˜ g˜ } → {h˜ p , g˜ } を得る．となるから {h, . ˆ˜ hˆ˜ p (ω) = h(ω) + gˆ˜ (ω) p(2ω) ˆ gˆ˜ (ω) gˆ˜ (ω). ˆ˜ gˆ˜ } は次のような修正を受ける． ˆ gˆ , h, 同様に，アップデートによりフィルタ {h, . ˆ hˆ u (ω) h(ω) + gˆ (ω) uˆ ∗ (2ω) = , gˆ (ω) gˆ (ω). . ⎞ ⎛ ˆ˜ ⎜⎜⎜ ⎟⎟⎟ ˆ˜ h(ω) h(ω) ⎜⎜⎝ ⎟⎟⎠ = ˆ˜ gˆ˜ u (ω) gˆ˜ (ω) − h(ω) uˆ (2ω). 以上をまとめると，. (5.1). ˜ˆ + gˆ˜ (ω) p(2ω) ˆ hˆ˜ p (ω) = h(ω) ˆ gˆ p (ω) = gˆ (ω) − h(ω) pˆ ∗ (2ω) ˆ hˆ u (ω) = h(ω) + gˆ (ω) uˆ ∗ (2ω) ˜ˆ uˆ (2ω) gˆ˜ u (ω) = gˆ˜ (ω) − h(ω) 13. 19.

(25) 20. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. であり，行列形で書くと. (5.2). ˆ ˆ 1 0 h(ω) h(ω) , = − pˆ ∗ (2ω) 1 gˆ (ω) gˆ p (ω) ˆ 1 uˆ ∗ (2ω) h(ω) hˆ u (ω) , = 0 1 gˆ (ω) gˆ (ω). . ˆ˜ ˆ hˆ˜ p (ω) = 1 p(2ω) h(ω) 0 1 gˆ˜ (ω) gˆ˜ (ω) ˆ˜ ˆ˜ 1 0 h(ω) h(ω) = −û(2ω) 1 gˆ˜ (ω) g˜ˆ u (ω). ˜ g˜ } は新しい双直交フィルタとなる．したがって，予測により双直交フィルタ {h, g, h, ˜ g˜ u } へと {h, g p , h˜ p , g˜ } へと変換され，アップデートの場合は新しい双直交フィルタ {hu , g, h, 変換される． p(ω) ˆ と uˆ (ω) は三角多項式であればどのようなものを設定しても双直交性は失われない．例えば (5.2) の予測の場合において，双直交性 1 0 ˆ˜ h(ω) hˆ ∗ (ω) gˆ ∗ (ω) = 0 1 gˆ˜ (ω) は次式より明らかである．. . 1 0. † p(2ω) ˆ 1 0 1 = 1 − pˆ ∗ (2ω) 1 0. p(2ω) ˆ 1 − p(2ω) ˆ 1 = 1 0 1 0. . 0 1. アップデートの場合も同様に証明することができる．このように既存フィルタの修正としての側面から眺めた場合でも，リフティングはフィルタの双直交性（完全再構成）を保証するものとなっている．さらに，もし三角多項式を pˆ と uˆ に設定すれば，得られるフィルタは必ず有限になる．ここで興味深いのは，リフティングにより既存フィルタがどのように修正されるかであるが，これについては以下に示す具体例を用いて述べる．. 5.1 Lazy ウェーブレット Lazy ウェーブレットフィルタは ˆ˜ ˆ h(ω) = h(ω) = 1,. gˆ (ω) = gˆ˜ (ω) = e−iω. で与えられる．または時間領域では. ˜ h[n] = h[n] = δ[n],. g[n] = g˜ [n] = δ[n − 1]. である．Lazy フィルタのポリフェーズ行列は明らかに. 1 0 = =I P(ω) 0 1 †. である．つまり，ポリフェーズ行列の定義より lazy フィルタによるウェーブレット変換はフィルタリングを本質的には何もせず，ただ信号を偶数と奇数にわけるだけである．こ. 14.

(26) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 21. れは，3 節で見たようにフィルタバンクの世界ではポリフェーズ分解として知られていたが，リフティングではスプリットと呼ぶことを思い出そう．ウェーブレットフィルタから得られるスケーリング関数とウェーブレット. φ(t) =. √ 2 h[k] φ(2t − k),. ˜ = φ(t). k∈Z. √. ˜ φ(2t − k) 2 h[k]. k∈Z. √ 2 g[k] φ(2t − k), ψ(t) =. ˜ = ψ(t). k∈Z. √. 2 g˜ [k] φ(2t − k). k∈Z. ˜ = δ(t), ψ(t) = ψ(t) ˜ = δ(t − 1/2) となるから，L2 (R) に入らない．はデルタ関数 φ(t) = φ(t) 実際，Lazy フィルタも gˆ (0) = gˆ˜ (0) 0 となっている．双直交性は満たすが，もちろん. Riesz 基底にもならない．しかし lazy フィルタをリフティングすることで L2 (R) の枠内の双直交ウェーブレットや Riesz 基底を構成できることが知られている．以下，例をいくつか示す．. 5.2 Lazy フィルタの修正 ˆ Lazy フィルタのリフティング（予測）は gˆ p (ω) = gˆ (ω) − h(ω) pˆ ∗ (2ω) より gˆ p (ω) = e−iω − pˆ ∗ (2ω) で与えられる．ここでたとえば予測作用素として線形予測. 1 + ei2ω p(2ω) ˆ = 2 を選べば，CDF(2,2) フィルタ (4.2) が得られる（正規化されていないことに注意）．. 1 1 gˆ p (ω) = − + e−iω − e−i2ω 2 2 ˆ˜ ˆ このフィルタは h(ω), は ω = π で，gˆ (ω), gˆ˜ (ω) は ω = 0 においてそれぞれに 2 個の h(ω) ˜ はそれぞれ 2 個のモーメント消滅条件零点を持ち，ψ(t), ψ(t). ∞. t ψ(t) dt = 0 を満たす． −∞ 2 ˜ {h[k − 2l], g[k − 2l]}l∈Z , {h[k − 2l], g˜ [k − 2l]}l∈Z は (Z) 上の双直交基底であり，ウェーブレットは L2 (R) の Riesz 基底となることが知られている．このように，L2 の枠をはみ出していたウェーブレットをリフティングすることによって L2 の枠内に入れることができる．ふつうはリフティングによってフィルタが持つ固有の性質を改善したり，新たな特性を. 付加したりする用途が考えられるが，逆に. p(2ω) ˆ =−. ei2ω + e−i2ω 2. のように適当な pˆ を選べば，CDF(2,2) フィルタから lazy フィルタ gˆ p (ω) = e−iω を得ることもできる．つまり Riesz 基底のリフティングが必ずしも Riesz 基底となるとは限らない．. 15.

(27) 22. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. φ(t). ψ(t). φ(t). ψ(t). Fig. 3. CDF(2,2) ウェーブレット（上）とリフティングされた 4 次の DD ウェーブレット（下）．. Lazy ウェーブレットはモーメント消滅を持たないが，CDF(2,2) ウェーブレット ψ, ψ˜ はそれぞれ 2 個のモーメント消滅を持つため，リフティングによりウェーブレットのモーメント消滅個数を増加できることが確認できる．しかし，モーメント消滅条件は制御できても，リフティングは関数の安定性（stability）や正則性（regularity）までは保証しない．実際，Fig. 3 からわかるように，φ, ψ はイレギュラーな形をしていることからもこれを裏付けている．しかし，適切なリフティングをさらに繰り返すことによって安定性や正則性も改善できることが知られている．実際，先ほどリフティングした g p (ω) に対してさらに p(2ω) ˆ =. 1 16. −ei4ω + ei2ω + 1 − e−i2ω. として再度リフティングを適用してみる．すると 4 次の DD フィルタ 2. gˆ p (ω) =. eiω − 9 + e−iω − 9e−i2ω + e−i4ω 16. が得られる．式 (2.16) を用いた場合のように，同様の結果が lazy フィルタと 3 次の補間予測 (2.18) を用いることで. gˆ (ω) = e p. −iω. . −ei2ω + 9 + 9e−i2ω − e−i4ω − 16. . のように直接得られることにも注意しよう．この DD フィルタは ψ(t) ∈ L2 (R) が 4 次のモーメント消滅条件を満たす双直交ウェー. ˆ ˆ ブレットフィルタであり，2 (Z) の Riesz 基底を生成する．h[k] は対称性 h(ω) と = h(−ω) ˆ ˆ + π) = 1 を満たすラグランジュハーフハーフバンド条件（halfband condition）h(ω) + h(ω バンドフィルタ（Lagrange Halfband filter）[2] となり，φ(t) は 3 次多項式を復元する補間. 16.

(28) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 23. スケーリング関数である．Fig. 3 に示すように φ, ψ はともにスムースな形をしており，確かにリフティングにより関数の安定性と正則性が向上したように見える．しかし，これは偶然の結果であり，あくまで制御できるのはモーメント消滅条件だけである．この点がリフティング構成によるフィルタ設計の弱点であるといえる．. 5.3 Haar ウェーブレットの修正次に Haar のウェーブレット. 1 + e−iω ˆ h(ω) = , 2. gˆ (ω) = −1 + e−iω. のリフティングによる修正を考える．この場合はモーメント消滅の個数は 1 である．たとえば，対称で 3 個のモーメント消滅を持つためには. pˆ ∗ (2ω) =. −i sin ω 1 −i2ω e − ei2ω = 2 4. として. gˆ (ω) = −1 + e p. より. gˆ p (ω) = −. −iω. . 1 + e−iω − 2. . e−i2ω − ei2ω 4. . 1 i2ω e + eiω − 8 + 8e−iω − e−i2ω − e−i3ω 8. を得る．これは CDF(1,3) の双対フィルタであり，確かに 3 次のモーメント消滅条件を満たす．同様の結果は，lazy フィルタと一定予測に加えて，アップデートを次のように設定して導出できることに注意しよう．. T 1 0 1 (ei2ω − 8 − e−i2ω )/16 . M (ω) = U(ω) 1 1 0 1. このように lazy フィルタは P(ω) = I なため，これを初期フィルタとして出発点にすることで，リフティングを繰り返し適用して任意の既存フィルタに到達することができる．もちろん初期フィルタとして Haar やさらに複雑なフィルタを設定することも可能であり，既存フィルタに限らない新たな（双）直交ウェーブレット（フィルタ）を作ることができ，いずれの場合においても双直交性は保証される．この点がリフティング構成の大きな利点のひとつであり，たとえば多次元において非分離型ウェーブレットを構成する際にも有利になる [12, 13, 15]．. 6. スケーリング関数とウェーブレットのリフティング ˜ ψ} ˜ にどのように影本節ではリフティングによって修正されたフィルタが関数族 {φ, ψ, φ, ˜ g˜ } → {h, g p , h˜ p , g˜ } を考える．h はそのままな響するのかを述べる．まずは，予測 {h, g, h, 17.

(29) 24. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. ので φ(t) =. √ 2 k h[k]φ(2t − k) は変わらない．次に ψ をフーリエ領域で考えると 1 p ω ˆ ω p ˆ ψ (ω) = √ gˆ φ 2 2 2 1 ˆ ω ˆ ω ω ˆ ω 1 ∗ − pˆ (ω) √ h = √ gˆ φ φ 2 2 2 2 2 2 ω ˆ ω 1 − pˆ ∗ (ω) φˆ (ω) = √ gˆ φ 2 2 2 p[−k] φ(t − k) = ψ(t) − k. ˆ となる．ここで gˆ p (ω) = gˆ (ω) − h(ω) pˆ ∗ (2ω) を使った．一方で，h˜ も予測されているので， φ˜ p も予測される．しかし g˜ はそのままなので √ g˜ [k]φ˜ p (2t − k) ψ˜ p (t) = 2 k. ˆ˜ を得る．最後に φ˜ p は hˆ˜ p (ω) = h(ω) + gˆ˜ (ω) p(2ω) ˆ より ˆφ˜ p (ω) = √1 hˆ˜ p ω φˆ˜ p ω 2 2 2 1 ˆ ω ˆp ω 1 ˜ˆ ω ˆ p ω ˜ + p(ω) ˆ = √ h φ φ˜ √ g˜ 2 2 2 2 2 2 ω ˆ˜ p ω 1 + p(ω) ˆ = √ hˆ˜ φ ψˆ˜ p (ω) 2 2 2 √ ˜ φ˜ p (2t − k) + p[k] ψ˜ p (t − k) = 2 h[k] k. k. と修正される．2 行目から 3 行目への展開は右項が ψˆ˜ p に等しいという事実を使った．. ˜ g} が修正されるので，双直交ウェーブレット基底まとめると，予測によって {h, ˜ ψ} ˜ は双直交性を保ったまま新たな双直交基底 {φ, ψ p , φ˜ p , ψ˜ p } へと修正される． {φ, ψ, φ, φ(t) = φ(t) ψ p (t) = ψ(t) −. . p[−k] φ(t − k). k. (6.1). √ ˜ φ˜ p (2t − k) + p[k] ψ˜ p (t − k) φ (t) = 2 h[k] ˜p. k. √ g˜ [k] φ˜ p (2t − k) ψ (t) = 2 ˜p. k. 18. k.

(30) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 25. ˜ ψ} ˜ → {φu , ψu , φ, ˜ ψ˜ u } となる．アップデートの場合は {h, g˜ } が対象なので {φ, ψ, φ, φu (t) =. √ 2 h[k] φu (2t − k) + u[−k] ψu (t − k) k. √ g[k] φu (2t − k) ψu (t) = 2 (6.2). k. k. ˜ = φ(t) ˜ φ(t) ˜ − ψ˜ u (t) = ψ(t). . ˜ − k) u[k] φ(t. k. ˜ g˜ } が有限で，さらに {p[k], u[k]} も有限であれば，得られる関数系は初期フィルタ {h, g, h, コンパクトサポートになる．. 6.1 モーメント消滅条件 ˜ g˜ } → {hu , g, h, ˜ g˜ u } となるので，g は変化せず gˆ (0) における零のアップデートは {h, g, h, 個数は変わらない．一方で (6.2) により φ → φu へとアップデートされているため，ψ も異なる関数 ψu へと修正されている．しかし，ψu の消滅するモーメントの個数は実はアップデートされる前の ψ と同じになっている．これは修正された φu の性質がウェーブレットのモーメント消滅条件には影響を及ぼさないことを意味している．実際に gˆ (0) の零の個数が変わっていない事実もこれを裏付けている．従って，アップデートによって改善（修正）される関数系は主に φ と ψ˜ であり，ψu に関してはあくまで副次的な効果しか期待できないことが示唆されている．予測に関しては，ψ˜ と ψ˜ p において同様のことが成り立つ．. 7. 信号解析への応用リフティングをフィルタバンクにおけるサブバンド分解の視点から眺めると，Mallat 変換が畳み込みとサブサンプリングを用いるのに対し，リフティングは信号のポリフェーズ成分の in-place な乗算と加算のみで変換を実装する極めて効率的な演算方式であるといえる．O(N) を上回る演算効率が期待できるため，冒頭で述べたように JPEG2000 での採用や，無線通信における MIMO システムの効率的な検出法 [17] などの演算効率が要求される場面で応用されている．また，JPEG2000 では，リフティングの構造的な逆変換の容易さを利用した，丸め誤差を打ち消す整数型ウェーブレット変換 [3] も採用されている．なお，Mallat 変換とリフティング構成を直接組み合わせた Mallat 変換の拡張も考えられるが，実際には Mallat 変換に用いるフィルタもリフティング構成で実装できることから本質的に (4.3) と同様であるため説明は省略する．詳細は Appendix A を参照されたい．リフティングのもう一つの側面は，フィルタ設計としての用途であるが，これには様々. ˜ に作用し，アップデート u は {˜g, h} をな選択の自由度があるといえる．予測 p は {g, h} アップデートする．lazy フィルタから出発して望むフィルタの性質を満たすまでリフティ. 19.

(31) 26. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. ングを繰り返し適用してもよいし，既存の双直交フィルタを用いて任意の修正を行う方法もある．問題は目的に応じた p と u をどのように設計するかである．同時に，リフティングを何回適用するかについても特に制限はない．本稿では補間予測 (2.18) に基づき，予測とアップデートを 1 度だけ適用する (4.3) における m = 1 の場合の 2 ステップの形を扱ったが，これをさらに 3 ステップに拡張することで，より柔軟で対称性に優れた双直交フィルタの設計が可能となる [11]．いずれにせよ，どのような選択をしてもフィルタの双直交性（完全再構成）は保証されるため，信号の加工や圧縮など，逆変換が必要な実用的な場面においてリフティング構成は極めて有利な手法であるといえる．実際，リフティング構成の双直交性と柔軟性を利用して，信号の特性に応じた適応的なリフティングを行う非線形変換の画像圧縮方式も提案されている [4]．しかしながら，関数解析の立場からすると，リフティングによって新たに得られた関数族の双直交性は保持されていても，それらの性質については不明瞭な点が多い．5 節でも触れたように，例えば基底関数が Riesz 基底になっているかは保証されず，そもそも. ˜ のモーメント消滅条件は制御 L2 (R) に入るかも不明である．また，ウェーブレット {ψ, ψ} ˜ ψ} ˜ に対する安定性や正則性に具体的にどのような影響を及ぼすかにはできても，{φ, ψ, φ, ついては未だ明らかになっていない．このように，フィルタ設計，信号処理，関数解析といったそれぞれの分野において多岐にわたる未解決な問題があり，これらの点について参加者からの幅広いご意見を伺いたい．. Appendix A.. Mallat 変換のリフティング構成. 式 (5.1) のフーリエ逆変換は. ˜ + h˜ p [n] = h[n]. . g˜ [n − 2k] p[k]. k. g [n] = g[n] − p. . h[n − 2k] p[−k]. k. h [n] = h[n] + u. . g[n − 2k] u[−k]. k. g˜ [n] = g˜ [n] − u. . ˜ − 2k] u[k] h[n. k. を得る．予測されたフィルタの Mallat アルゴリズムは. c j−1 [k] =. . h[n − 2k] c j [n]. n. d pj−1 [k] =. . g p [n − 2k] c j [n]. n. 20.

(32) 27. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. -. +. 2. c j-1. K. 2. 1/K. +. cj -. 2. dj-1. 1/K. K. +. cj. 2. Fig. 4. リフティングによる Mallat 変換の拡張. となる．ここで. g p [n] = g[n] −. . h[n − 2k] p[−k]. k. であるから，詳細成分 d j−1 [k] は. d pj−1 [k]. ⎞ ⎛ ⎜⎜ ⎟⎟ ⎜ ⎜⎜⎝g[n − 2k] − = h[n − 2k − 2k] p[−k]⎟⎟⎟⎠ c j [n] n k ⎞ ⎛ ⎜⎜ ⎟⎟ ⎜ = g[n − 2k] c j [n] − ⎜⎜⎝ h[n − 2k − 2k] c j [n] p[−k]⎟⎟⎟⎠ n. = d j−1 [k] −. . n. k. p[k − n] c j−1 [n]. n. となる．同様に. hu [n] = h[n] +. . g[n − 2k] u[−k]. k. を使って，アップデートされた近似成分. cuj−1 [k] =. . hu [n − 2k] c j [n]. n. = c j−1 [k] +. . u[k − n] d j−1 [n]. n. が得られる．したがって，リフティングされた Mallat 変換は以下のように計算される．まず最初に通常の Mallat アルゴリズムを信号 c j に適用し，展開係数 (c j−1 , d j−1 ) を得る．次に，得られた結果にそれぞれリフティング（予測，アップデート）を適用する．. cuj−1 [k] = c j−1 [k] + d j−1 ∗ u[k] d pj−1 [k] = d j−1 [k] − c j−1 ∗ p[k] この構成は Mallat 変換にリフティング操作を加えただけなので，逆変換. c j−1 [k] = cuj−1 [k] − d j−1 ∗ u[k] d j−1 [k] = d pj−1 [k] + c j−1 ∗ p[k] 21.

(33) 28. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. が成り立つのは明らかである．既存フィルタをそのまま利用する場面において，それをリフティングによって修正したい場合にはこのような実装方法が役に立つが，演算効率を要求するならユークリッドの互除法を用いて予め得たフィルタを (4.3) の形で実装する方式の方が適しているといえる．. 参考文献 [1] ISO/IEC 15444–1: Information technology—JPEG 2000 image coding system—Part 1: Core coding system, ISO/IEC JTC 1/SC 29/WGI, January, 2001. [2] R. Ansari, C. Guillemot, and J. F. Kaiser, Wavelet construction using Lagrange halfband filters, IEEE Trans. Circuits Syst. 38, pp.1116–1118 1991. [3] R. C. Calderbank, I. Daubechies, W. Sweldens and Boon–Lock Yeo, Wavelet transforms that map integers to integers, J. Appl. and Comput. Harmon. Anal. (ACHA), Vol. 5 No. 3, pp. 332–369, 1998. Technical Report, Princeton and lucent Technologies, 1996. [4] R. L. Claypoole, G. M. Davis, W. Sweldens, and R. G. Baraniuk, Nonlinear wavelet transforms for image coding via lifting, IEEE Trans. Image Processing, Vol. 12, No. 12, pp1449–1459, 2003. [5] A. Cohen, I. Daubechies, and J. Feauveau, Bi-orthogonal bases of compactly supported wavelets, Comm. Pure Appl. Math., Vol. 45, pp. 486–560, 1992. [6] I. Daubechies, I. Guskov, P. Schröder and W. Sweldens, Wavelets on irregular point sets, Phil. Trans R. Soc. A, Vol. 357 No. 1760, pp. 2397–2413, 1999. [7] I. Daubechies and W. Sweldens, Factoring wavelet transforms into lifting steps, J. Fourier Anal. Appl., Vol. 4, No. 3, pp. 247–269, 1998. [8] G. Deslauriers and S. Dubuc, Symmetric iterative interpolation processes, Construct. Approx., Vol. 5, pp. 49–68, 1989. [9] S. Dubuc, Interpolation through an iterative shceme, J. Math. Anal. Applicat., Vol. 114, pp. 185–204, 1986. [10] A. Jensen, A. Ia Cour-Harbo, Ripples in Mathematics, Springer, 2001. [11] R. Eslami, and H. Radha, Design of Regular Wavelets Using a Three-Step Lifting Scheme, IEEE Trans. Signal Processing, Vol. 58, No. 4, pp. 2088–2101. [12] 藤ノ木健介，非分離型 2 次元ウェーブレットの構成と画像処理への応用，京都大学数理解析研究所講究録，2014 年（submitted） [13] K. Fujinoki and O. V. Vasilyev, TriangularWavelets: An Isotropic Image Representation with Hexagonal Symmetry, EURASIP Journal on Image and Video Processing, No. 22.

(34) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. 248581, 16 pages, 2009. [14] T. A. C. M. Kalker and I. Shah, Ladder structures for multidimensional linear phase perfect reconstruction filter banks and wavelets, In Proceedings of the SPIE Conference on Visual Communications and Image Processing, pp. 12–20, 1992. [15] 遠藤智子，坂本直道，安野拓也，武川直樹，結晶構造の分析に適用可能な三次元ウェーブレットの構築，電子情報通信学会論文誌 A, Vol. J92-A, No. 8, pp. 540–550, 2009. [16] S. Mallat, A theory for multiresolution signal decomposition, The wavelet representation, IEEE Trans. Patt. Anal. and Mach. Intell., Vol. 11, No. 7, pp.674–693, 1989. [17] A. Mobasher, R. Sotirov, and A. K. Khandani, Matrix-Lifting Semi-Definite Programming for Detection in Multiple Antenna Systems, IEEE Trans. Signal Processing, Vol. 58, No. 10, pp. 5178–5185, 2010. [18] M. J. D. Powell, Approximation theory and methods, Cambridge University Press, 1981. [19] I. Shah and T. A. C. M. Kalker, On Ladder structures and linear phase conditions for bi-orthogonal filter banks, In Proceedings of ICASSP-94, Vol. 3, pp. 181–184, 1994. [20] W. Sweldens, The lifting scheme: a custom-design construction of biorthogonal wavelets, J. Appl. Comput. Harmon. Anal., Vol. 3, No. 2, pp. 186–200, 1996. [21] W. Sweldens, The lifting scheme: a construction of second generation wavelets, SIAM J. Math. Analysis, Vol. 29, No. 2, pp. 511–546, 1997. [22] P. Schröder and W. Sweldens: Spherical wavelets: Efficiently representing functions on the sphere, Computer Graphics Proceedings, SIGGRAPH95, 161–172, 1995 [23] W. Sweldens and P. Schröder, Building your own wavelets at home, ACM SIGGRAPH course notes, 1996. [24] G. Uytterhoeven, D. Roose and A. Bultheel, Wavelet transforms using the lifting scheme, Report ITA-Wavelets-WP1.1 (Revised version), Department of Computer Science, K. U. Leuven, Heverlee, Belgium, April 1997. [25] 山田道夫，第二世代ウェーブレットの構成法と応用，京都大学数理解析研究所講究録，第 1622 巻，pp. 37–46，2009 年. 藤ノ木健介 (東海大学理学部情報数理学科) 〒259-1292 神奈川県平塚市北金目 4-1-1. E-mail: [email protected]. 23. 29.

(35) 30. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering.

(36) 31. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. ウェーブレットを用いたリフティングスキームによる複素数離散ウェーブレット変換. £. 章忠 £ 嶋末昂祐 Ý 戸田浩 £ 三宅哲夫 £ 豊橋技術科学大学工学部 Ý 豊橋技術科学大学大学院. 概要º. 複素数離散ウェーブレット変換は完全シフト不変性の特性を持つ離散ウェーブレット変換の一種である．は実数部と虚数の２つで構成されているために，計算量が通常の離散ウェーブレット変換の２倍以上となっている．計算量を削減する方法として，計算手法を従来の多重解像度解析からリフティングスキームへと変更することは有効であると考えられる．．リフティングスキームはこれまでコンパクトサポートのウェーブレットにのみ対応しているとされていた．本研究では，コンパクトサポートのないウェーブレットでのリフティングスキームを設計し，に適用させ変換処理の高速化を図る．さらにこの手法の問題点と改善について議論する．.

(37)

(38)

(39)

(40) £

(41) Ý £ £ £ Ý

(42)

(43)

(44)

(45)

(46)

(47)

(48) !

(49)

(50)

(51) "#

(52)

(53)

(54)

(55)

(56)

(57)

(58)

(59)

(60)

(61) "# $

(62)

(63)

(64)

(65)

(66)

(67)

(68)

(69)

(70)

(71) %

(72)

(73) !

(74)

(75) . ½º はじめにフーリエ変換やウェーブレット変換に代表される周波数解析は近年，音声のノイズ除去，音源分離や画像圧縮，電子透かしなどに応用され，その有用性が確認されているなかでも戸田，章ら. . が提案する複素数離散ウェーブレット変換. . ．.

(76) .

(77) 32. Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. c j ,k. a p2 b p2. c j 1,k. a p2. c j 2,k. b p2. d j 2,k. n2. g. n2. c j 1,k n2. g. n2. h. h d j 1,k. d j 1,k. Decomposition. c j ,k. Reconstruction.

(78) .

(79) は，完全シフト不変性を有し，実数部と虚数部のマザーウェーブレット

(80) は無限長であるウェーブレットを基礎に構成されている．の計算には，一般的に多重解像度解析

(81)

(82) が用いられるが，フィルタ処理後にダウンサンプリングを行うため無駄な計算が多い．一方，高速処理を実現する手法として，フィルタ処理の前にダウンサンプリングを行うリフティングスキーム ! がある "．しかしはコンパクトサポートを持つ有限長の実数ウェーブレットのみに適用され，複素数やコンパクトサポートを持たない無限長のウェーブレットには適用例がない．本研究では，上記の. ウェーブレットを基礎に構成されたに，リフティン. グスキームを適用し，完全シフト不変性を有しながら変換処理が高速な離散ウェーブレット変換の実現を目的とする．. ¾º 複素数離散ウェーブレット変換とリフティングスキーム ¾º½ 複素数離散ウェーブレット変換の吟味. の高速アルゴリズムは，双直交ウェーブレットの特性をと生かし，の理論から導かれたものである．双直交ウェーブレットのその双対ウェーブレット # の間には，以下のウェーブレット方程式が成立する． $%& $ # # $ $%$ 離散ウェーブレット変換. . . ¾. . . ¾. ただし . はウェーブレット数列，は双対ウェーブレット数列，また，# はそ. ， # に対応するスケーリング関数と双対スケーリング関数で，これらの間には次のツースケール関係 '

(83) !

(84) が成立する． $%( $ # $% # $ れぞれ. . . ¾. . ¾. $. .

(85) Proceedings of the OKU & ISM 2014 Workshop on Wavelet Theory and its Applications to Engineering. ただし数列. . はツースケール数列，. . 33. は双対ツースケール数列と呼ばれている．. ところで本論文で扱うのは直交ウェーブレットを用いた. であるので，ここか. らは直交ウェーブレットに限定して話を進める．直交ウェブレットは自己双対のため，. ，，. ∼ の. ，となることが知られているので，式の式に集約される．また数例との間には. 式は，式，

u½¬26N EF[ubg_ÆHwÖÌpv\eWi2014/11/12Åj

u½¬26N EF[ubg_ÆHwÖÌpv\eWi2014/11/12Åj