第 6 回計測自動制御学会制御部門大会
2006 年 5 月 31 日–6 月 2 日 ウィルあいち

サンプル値 H ∞ 最適化による因果的 B-Spline 補間永原正章 ○和田敏裕 山本裕 （京都大学）

Causal B-Spline Interpolation via Sampled-Data H ∞ Optimization
M. Nagahara, ∗T. Wada, and Y. Yamamoto (Kyoto University)
Abstract– B-spline interpolation is widely used in image processing. The interpolation system contains anoncausal filter, and hence it is difficult to use this for real-time processing, for example, audio or speech
signal processing. Our objective is to design a causal filter which approximates B-spline interpolation. Forthis purpose, we introduce H ∞ optimization. Moreover, we assume that the original analog signal is anL2 signal filtered by an LTI system. It follows that the design problem is formulated by sampled-data H ∞optimization.
Key Words: B-spline interpolation, H ∞ optimization, sampled-data control

1

はじめに 信号の補間は，与えられたデータから関数を推定したり，ディジタル信号の解像度を上げるといった様々な応用があり，特にディジタル信号処理でよく用いられる技術である．信号補間の方法は様々であるが，特にB-Spline による補間 7, 8) は画像処理においてよく用いられ，画像処理の商用ソフトウェア（例えば Photoshopなど）でも標準的に組み込まれている．

    さらに，元の信号を区分的多項式とする仮定が現実の信号で成り立つとは言いがたい．そこで，元のアナログ信号を有限次元の LTI システムでフィルタリングされた L2 信号と仮定する．この仮定は，元のアナログ信号の特性を周波数分布により指定することができ，より自然な仮定である．この仮定を用いると，設計問
題はアナログ特性を考慮したディジタルフィルタの設計問題となり，サンプル値 H ∞ 最適化問題として定式化することができる．これにより，元のアナログ特性を考慮した因果的 B-Spline 補間システムが設計できる．

  

Fig. 1: n 次 B-Spline (n = 0, 1, 2, 3)

2B-Spline 補間

連続時間信号 x(t) ∈ S n , t ∈ R を考える．ここで S nは次数 n の多項式 Spline の空間であり，(そこで本研究では，厳密にサンプル点間の値を求めるのではなく，因果的なシステムを用いてサンプル点間の値を近似する手法を提案する．この近似は，不安定なゼロ点をもつシステムの安定な逆システム（の近似）を求める問題として定式化される．本研究では，この近似に H ∞ 最適化手法を用いる．これにより，H ∞ノルムの意味で最適な近似逆システムが求まり，因果的な B-Spline 補間システムが構成できる．

 

B-Spline による補間では，元のアナログ信号を区分的多項式と仮定し，B-Spline 基底による展開係数を求めることによって，サンプル点間の値を求める．しかし，展開係数を求めるためには，入力信号の未来の値をも知る必要があり，補間システムは非因果的となる．
これは，Shannon のサンプリング定理によるサンプル点間の再構成が非因果的であるのと同じ理由による．画像処理では非因果的であっても処理が行えることから，
B-Spline はもっぱら画像処理において用いられているが，リアルタイムの計測や音声処理等において B-Splineを使用することは難しい．

 

Sn =x(t) =∞X)c(k)φ(t − k), t ∈ R, c ∈ `2k=−∞で定義される 7) ．ただし，φ(t) は n 次の 対称 B-Splineφ(t) = (β 0 ∗ β 0 ∗ · · · ∗ β 0 )(t),|{z}(1,0β (t) =0,n+10≤t≤1otherwiseを表す．空間 S n に属する信号は n 次区分的多項式であり，さらに n ≥ 2 の場合は，C n−1 (n − 1 回連続微分可能な関数の集合）に属することが知られている 7) .
0 次から 3 次までの B-Spline φ(t) を Fig. 1 に示す．
連続時間信号 x(t) ∈ S n をサンプリング周期 T = 1でサンプリングした信号 x(n), n = 0, 1, 2, . . . は次式で

x(k)

c(k)

ψ↑LcL (k)φLxL (k)

Fig. 2: B-Spline 補間与えられる．
∞Xx(n) =c(k)φ(n − k)k=−∞ (1)= (c ∗ φ)(n)

また x(t) を T = 1/L, L ∈ N でサンプリングした信号を xL (n), n = 0, 1, 2, . . . とおくと，³n´xL (n) = xL∞´³nX=−kc(k)φ
L==k=−∞
∞
X
k=−∞
∞
X

 c(k)φL (n − kL)(2)











ψ(z) = φ(z)−16=z + 4 + z −1µ¶6α1
1=−+−1 ,1 − α2 1 − αz −11 − αz√
α= 3−2{(↑ L)c} (k)φL (n − k)φL (k) = φ(k/L),

cL := {(↑ L)c}となる．ここで (↑ L) はアップサンプラであり，以下で定義される．

(↑ L) : {x(k)}∞k=0 7→ {x(0), 0, 0, . . . , 0, x(1), 0, . . .}| {z }
L−1(1) と (2) より，B-Spline を用いた信号補間は，Fig. 2のシステムで構成される．ここで ψ はψ∗φ=I(3)を満たすシステムである．

因果的 B-Spline 補間

3.1 問題設定
基底関数 φ(t) はコンパクト台を持つため，そのサンプリング φ(k) および φL (k) は FIR フィルタで表現される．例えば n = 3 の Cubic Spline の場合，
1 −1 2 −2 1 −3z + z + z636である．しかし，この逆システム ψ = φ−1 はψ(z) =のようにインパルス応答を平行移動することにより，= (cL ∗ φL ) (k),φ(z) =Fig. 3: 非因果的フィルタ ψ(z) = 6/(z + 4 + z −1 ) のインパルス応答

k=−∞36z
1 + 4z −1 + z −2となり，極の一つが単位円外に存在し不安定となる．これは一般の n 次 Spline の場合も同様である 8) ．そこで ψ(z) を安定な伝達関数と反安定な伝達関数に分解することにより，非因果的な IIR フィルタとして実現する手法がよく知られている 8) ．例えば，上の CubicSpline の場合，

2 11φ(z) = z + + z −163 6と分解でき，|α| < 1 であるので，安定な非因果的 IIRフィルタとなる．この IIR フィルタのインパルス応答を Fig. 3 に示す．画像処理への応用では因果性は必要でないので，このような非因果的なフィルタでもかまわないが，音声処理や計測などでリアルタイム処理が必要な場合，非因果的なフィルタを用いることはできない．
そこで，本研究では，因果的なフィルタを設計することを考え，(3) を近似的に満たす因果的なフィルタ ψを求める．すなわち，問題を次のように定式化する．
問題 1 伝達関数 φ(z) および遅れステップ d が与えられたとき，評価関数

J(ψ) = kz −d − ψ(z)φ(z)k∞(4)を最小化する安定な伝達関数 ψ(z) を見つけよ．
この問題は標準的な H ∞ 最適化問題であり，MATLAB 等の標準的な数値計算ソフトウェアを用いて容易に解を得ることができる（Fig. 4 参照）．
得られる最適なフィルタは一般に IIR 型であるが，次節で述べるように，FIR 型の最適フィルタも線形行列不等式 (LMI) により求めることが可能である．

3.2

LMI による FIR フィルタ設計

設計すべき FIR フィルタを

ψ(z) =NXn=0

an z −n· −dz
1−φ(z)03.3 最適フィルタの性能解析
前節では，恒等式 (3) を近似するフィルタ ψ(z) をH ∞ 最適化を用いて設計する手法を提案した．ここでは，まず恒等式 (3) の近似が実際の出力 xL (k) を近似していることを示す．次の命題が成り立つ．

¸

命題 2 (3) の等式を満たす理想フィルタを ψI とおき，x ∈ `2 (x 6= 0) に対して，xL := φL (↑ L)ψI x とおく．
また因果的かつ安定なフィルタ ψ に対して，xeL :=φL (↑ L)ψx とおく．このとき，φ と L だけに依存する
定数 C > 0 が存在して，φ(z)Fig. 4: 離散時間 H ∞ 設計

kz −dL xL − xeL k2≤ Ckz −d − ψ(z)φ(z)|∞kxk2

とおく．この ψ(z) の状態空間実現は

0
10 ... 0.
 ..
..
..
..
 .
.
.
. ..

 ..
..
..
.
. 0
ψ(z) =  .
 .
.
.. 1
 ..

 0 ... ... ... 0aN . . . . . . . . . a1·¸AψBψ=:,Cψ (α) Dψ (α)£¤α := aN . . . a1 a0

0.. . 


0 
0 

1 が成り立つ．
証明 恒等式 ψI ∗ φ = I および ψI x = c （c は x(t)の φ(t) による展開係数）より，

z −dL xL − xeL = z −dL φL (↑ L)ψI x − φL (↑ L)ψx= φL (↑ L)(z −d − ψφ)ψI xa0= φL (↑ L)(z −d − ψφ)c
ここで φ は Riesz 基底 6) であるので，φ に依存する（c および x に依存しない）定数 K が存在して，

kck2 ≤ Kkxk2と書くことができる．ここで，設計パラメータ α はψ(z) の状態空間行列の C 行列と D 行列にのみ線形に入っていることに注意する．また，φ(z) および z −d の状態空間実現をそれぞれ，·φ(z) =:

AφCφ

BφDφ

¸

·,

Ad
Cdz −d =:Bd0の状態空間表現は次式で与えられる．

00AdCd−Bψ Dφ−BφBd−Dψ (α)DφAT P B−γI + B T P B
D(α)≤ kφL (↑ L)k∞ kz −d − ψφk∞ Kkxk2= Ckz −d − ψφk∞ kxk2
ただし，C := KkφL (↑ L)k∞ である．これより，不等式 (5) が成り立つことがわかる．
□すなわち，誤差系の H ∞ ノルム kz −d − ψ(z)φ(z)k∞が十分小さければ，Fig. 2 の出力 xL (k) の相対誤差も小さくなり，理想的な B-Spline 補間の良い近似であることがわかる．また，遅れステップ d を大きくすれば，この誤差は小さくなることを示すこともできる 2) ．
命題 3 遅れステップが d のときの (4) の評価関数の最小値を Jopt (d) とおくと，

lim Jopt (d) = 0が成り立つ．

命題 1 正数 γ に対して kE(z)k∞ が成り立つ必要十分条件は，以下の LMI を満たす行列 P > 0 が存在することである．

AT P A − P
 BT P AC(α)≤ kφL (↑ L)k∞ kz −d − ψφk∞ kck2d→∞

これより，設計パラメータ α は E(z) の状態空間実現における C 行列と D 行列のみに線形に依存していることがわかる．この性質と有界実補題 1) を用いれば，設計問題は LMI で記述される 9) ．

kz −dL xL − x
eL k2 = kφL (↑ L)(z −d − ψφ)ck2,E(z) := z −d − ψ(z)φ(z)

Aψ
Bψ Cφ

0AφE(z) = 
00Cψ (α) Dψ (α)Cφ¸·B
A=:C(α) D(α)

が成り立つ．以上より，¸とおく．このとき 誤差系(5)C(α)TD(α)T  < 0−γI

証明 B-Spline φ(t) は一般にコンパクト台を持ち，そのサンプリング φ(k) の Z 変換 φ(z) は安定である．したがって，文献 2) の Theorem 4.1 の証明と同様にして示すことができる．
□4

サンプル値 H ∞ 最適化

前章までは，x(t) ∈ S n と仮定して議論を進めた．空間 S n に属する信号は区分的に n 次多項式で表される信号であるが，現実の信号でそのような仮定が成り立つとは言いがたい．したがって，本章では入力信号を有限次元のフィルタ F (s) で帯域制限された L2 信号と仮定し，サンプル値 H ∞ 最適化を用いて因果的なB-Spline 補間システムを設計する．

w

F (s)xψ

Tu−HT /LφL (↑ L)eexew−mT sFig. 5: 誤差系の H ∞ ノルムを最小化するフィルタ ψ(z) を求めよ．

4.2 サンプル値 H ∞ 最適化によるフィルタ設計
問題 2 は，アップサンプラ (↑ L) を含むマルチレート系である．これを単一レート系へ変換するために，離散時間リフティング 4) LN を導入する．この離散時間リフティングを用いれば，アップサンプラ (↑ L) は0¤T...

0と表される．これを用いると，

HT /L φL（ ↑ L) = HT /L φL L−1L

£10

¤T...

0eT φeL ,=HeT := HT /L L−1 ,HL£e1
φL := LL φL L−1L0...

φeL (z)ψ(z)Fig. 6: サンプル値 H ∞ 設計

参考文献

問題 2 サンプル値の誤差系¡¢
E = e−mT s − HT /L φL (↑ L)ψST F£1(↑ L) = L−1
LeT
HST

4.1 問題設定
Fig. 5 の誤差系を考える．この誤差系において，F (s)は有限次元の LTI システムとし，入力信号の周波数分布を表す．この信号が周期 T でサンプリングされ，BSpline 補間された信号が周期 T /L のゼロ次ホールド
HT /L でアナログ信号に変換されて出力される．このアナログ出力と，元の信号を時間 mT (m は自然数) だ
け遅らせたものとの誤差を e とおく．このとき，設計問題は以下のように定式化される．

¤T

0eL はと単一レートで表現することができる．ここで，He
周期 L で動作する一般化ホールドであり，φL は 1 入力 L 出力の LTI システムとなる．
以上より，Fig. 6 の単一レートサンプル値系が得られる．このサンプル値系に対して H ∞ 最適化を行うには，ファーストサンプルファーストホールド近似による方法 5) や等価離散時間系による方法 3) があり，数値的にも効率良く最適なフィルタを求めることができる．

5· −mT s¸eF (s) −1F (s)0u

おわりに

本研究では，因果的な B-Spline 補間システムの設計法を提案した．まず，入力信号を区分的多項式の空間S n の信号と仮定し，離散時間 H ∞ 最適化を用いて設計を行った．また，その性能の解析を行い，フィルタの遅れ（処理時間）が十分長ければ，誤差が小さくなることを示した．つぎに，入力信号をアナログフィル
タ F (s) で帯域制限された L2 信号と仮定し，サンプル値 H ∞ 最適化を用いた設計を提案した．この仮定は，区分的多項式の仮定よりもより現実的な仮定である．

1) S. Boyd, L. E. Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in Systemsand Control Theory, SIAM, 1994.
2) T. Chen and B. A. Francis, Design of multirate
filter banks by H∞ optimization, IEEE Trans.
Signal Processing, Vol. 43, No. 12, pp. 2822–2830, 1995.
3) H. Kakemizu, M. Nagahara, A. Kobayashi, andY. Yamamoto, Noise reduction of JPEG images
by sampled-data H ∞ optimal ε filters, SICE Annual Conference 2005, pp. 1080–1085, 2005.
4) P. P. Khargonekar, K. Poolla, and A. Tannenbaum, Robust control of linear time-invariant
plants using periodic compensation, IEEE Trans.
Autom. Control, Vol. 30, No. 11, pp. 1088–1096, 1985.
5) 永原, 山本, インターポレータのサンプル値 H ∞設計, システム制御情報学会論文誌, Vol. 14, No.
10, pp. 483–489, 2001.
6) G. Strang and T. Nguyen, Wavelets and FilterBanks, Wellesley-Cambridge Press, 1996.
7) M. Unser, A. Aldroubi and M. Eden, B-Spline
signal processing: Part-I — Theory, IEEE Trans.
Signal Processing, Vol. 41, No. 2, pp. 821–833,
1993.
8) M. Unser, A. Aldroubi and M. Eden, B-Spline signal processing: Part-II — Efficient design and applications, IEEE Trans. Signal Processing, Vol.
41, No. 2, pp. 834–848, 1993.
9) Y. Yamamoto, B. D. O. Anderson, M. Nagaharaand Y. Koyanagi, Optimizing FIR approximation
for discrete-time IIR filters, IEEE Signal Processing Letters, Vol. 10, No. 9, pp. 273–276, 2003.