論文

予測誤差の Golomb-Rice 符号量を最小化する線形予測分析
亀岡 弘和†

鎌本

優†

原田

登†

守谷 健弘†A Linear Predictive Coding Algorithm Minimizing the Golomb-Rice Code Lengthof the Residual Signal
Hirokazu KAMEOKA† , Yutaka KAMAMOTO† , Noboru HARADA† ,and Takehiro MORIYA†
あらまし 本論文では，予測誤差ベクトルの 2 ノルムを最小化する従来の線形予測分析に基づく可逆圧縮符号化方式は予測誤差の符号量を直接的に小さくするものではなかった点に着目し，予測誤差の符号量をできるだけ小さくする線形予測分析の効率的なアルゴリズムの導出を目的とする．予測誤差の符号化に利用する Golomb-Rice
符号における振幅値と符号量との関係をよく表すコスト関数モデルを考え，これに基づいて立てられる目的関数（予測誤差ベクトルの 1 ノルム等）の最小解を効率的に求める反復アルゴリズム（補助関数法）を提案する．評
価実験により，提案法の動作と提案法による圧縮性能を確認した．
キーワード

可逆圧縮符号化，線形予測分析，Golomb-Rice 符号，1 ノルム，補助関数法

での最適化となっていない．線形予測分析による時系

1. ま え が き
線形予測分析に基づく時系列信号の可逆圧縮符号化

列信号の可逆圧縮符号化の国際標準 MPEG-4 Audio
Lossless Coding（ALS）[2] では，ビットストリーム

方式は，時系列信号を線形予測分析し，その結果求まや復号化の手順の標準は規定されているものの，符号る線形予測係数あるいは PARCOR 係数と予測誤差化の手段には自由度が残されているため，予測係数の（残差）を符号化して伝送し，受信側で無歪に復号化

算出方法には符号量削減の余地が少なからず残されてできる仕組みとなっている．線形予測分析により生成いる．もし予測係数の算出法の改善によって標準準拠

される残差信号の振幅は通常 0 付近に集中するというの参照ソフトウェアに比べて圧縮率をたとえわずかで性質を利用し，出現頻度の高い値ほど短い符号を割りも向上できれば，標準準拠の拘束から外れずに圧縮率当てる Golomb-Rice 符号 [1] をはじめとするエントロ

向上が達成されたことになり大変価値が高い．

ピー符号化を残差の符号化に用いることで全体の符号

線形予測分析を包含する枠組である線形回帰分析に量を小さく抑えようとする点がこの方式の特徴である．

おいて，誤差ベクトルの要素の絶対値和を最小化する

Golomb-Rice 符号の場合，残差振幅に割り当てられる回帰係数の解法は，その最適化問題が線形計画の問題

符号量は，振幅の絶対値とほぼ比例関係にあるため，として定式化できる [3] ことから，シンプレックス法

残差符号量は残差振幅の絶対値和である程度よく近似に基づくもの [4] や内点法に基づくもの [5] や有効制される．したがって，残差振幅の絶対値和が小さいほ約法に基づくもの [6] などがよく知られる．このほか

ど符号量はより小さくできる可能性がある．しかしなに有効な解法として，重み付きメジアン法 [7]，反復再がら，従来の線形予測分析による可逆圧縮符号化方式

重み付き最小二乗誤差推定（Iteratively Reweighted

では，残差振幅の二乗和を最小化するように予測係数

Least Squares，IRLS）法 [8] などが提案されている．

を求めるため，残差符号量を直接的に最小化する規準

これらの手法は，線形予測分析による可逆圧縮符号化における残差符号量削減という本論文で提起する目的†

日本電信電話株式会社 NTT コミュニケーション科学基礎研究所，
厚木市
NTT Communication Science Laboratories, NTT Corporation, Atsugi-shi, 243–0198 Japan

電子情報通信学会論文誌 A Vol. J91–A

意識とは別に，最小絶対値推定量がロバスト推定量であることから線形予測分析に基づく音声分析の耐雑音性能を向上する目的として応用されている [9], [10]．

c （社）電子情報通信学会 2008
No. 11 pp. 1017–1025 

1017

電子情報通信学会論文誌 2008/11 Vol. J91–A No. 11

我々の問題設定においては，残差の絶対値はあくま

を s に関して最小化する問題であり，I ≥ J ならばで Golomb-Rice 符号における残差振幅値と符号量と

s = (AT A)−1 AT x が最適解となる．これに対し，の関係を近似した，いわば「符号量モデル」の一つと我々がここで考えるのは，z の各要素が互いに独立にいう位置付けにすぎず，残差の絶対値和より更に良い

ラプラス分布に従う場合を仮定した s の最ゆう解を求目的関数がほかに立てられる可能性がある．上記従来める問題である．すなわち，1 ノルム（絶対誤差）

法が他の目的関数に対しても必ずしも適用可能というわけではないため，このことが，より一般的な予測L(s) ≡ z1 = x − As1 =Ixi −(As)i  (2)i=1

係数算出方法を開発する本研究の動機となっている．
本論文では，残差符号量をできるだけ小さくする線を最小化する s がこの場合の最ゆう解に対応する．こ形予測分析の効率的なアルゴリズムの確立を目的との推定量のことは 1 推定量と呼び，x の外れ値に頑健

し，（ 1 ）誤差ベクトルの要素の絶対値和を最小化するなロバスト推定量の一つとして知られる．

回帰係数を効率的に求める手法の導出を出発点とし，2. 2 線形予測モデルとの対応（ 2 ）Golomb-Rice 符号量関数を絶対値和に比べてよ

線形予測モデルは式 (1) の特殊例である．線形予

りよく表現する目的関数をいくつか導入し，（ 3 ）これ

測モデルは，あるディジタル信号の時刻 i におけるらを最小化する回帰係数も同様の原理に基づいて求サンプル yi を，時刻 i − 1 から過去 J 個のサンプル
yi−1 , yi−2 , · · · , yi−J の線形結合で表現するモデル

められることを示す．そして以上の手法を線形予測分
析に基づく可逆圧縮符号化に応用し，圧縮性能評価を行う．
なお，次章より明らかにするが，導出過程は異なる

yi 

J


sj yi−j(3)

j=1

ものの提案法は IRLS 法 [8] と形式的に非常に似た手法である．IRLS 法は，重み付き最小二乗誤差推定をであり，自己回帰モデルとも呼ばれる．I 個の連続す

反復的に重みを更新しながら行う手法であるのに対し，るサンプル y1 , · · · , yI すべてを最もよく表す線形予測

提案法は，重みだけでなく観測値を仮想的にシフトすモデルの J 個の係数を推定することを線形予測分析とる補正項も更新しながら重み付き最小二乗誤差推定を反復的に行う手法である．IRLS 法は，重みの更新規呼ぶ．式 (1) に対応させると，線形予測モデルは，

⎛ ⎞ ⎛

⎞

が目的関数の単調減少性を保証するように導き出されy1
y0 y−1 . . . y1−J ⎛ ⎞
⎜ ⎟ ⎜
⎟ a1
y0 . . . y2−J ⎟⎜ . ⎟⎜ y2 ⎟ ⎜ y1
⎜ . ⎟=⎜ .
.. ⎟..
⎜.⎟ ⎜ .
⎟⎝ .. ⎠+z (4). ⎠.
⎝.⎠ ⎝ .
aJ
yI−1 yI−2 . . . yI−J
yI

るため，IRLS 法では収束が保証されない目的関数にとおいたことに相当し，z が残差ベクトルである．

範が目的関数の一次近似に基づいており，限られた目的関数に対してしか収束性は保証されない．これに対し提案法の原理的な特長は，重みと補正項の更新公式

対しても反復アルゴリズムの収束性が保証される点に

2. 3 補助関数法の原理ある．このため，提案法は IRLS 法より幅広いクラス

提案法の特徴は，式 (2) の最小化に，補助関数法との目的関数を扱うことができる．

呼ぶ原理を用いる点にある．補助関数法とは，適切に

2. 絶対誤差を最小化する線形回帰分析

設計した補助関数を反復的に減少させていくことで目

2. 1 問 題 設 定
x, s をそれぞれ I 次元及び J 次元ベクトル，A を

リズムを一般化した原理である．EM アルゴリズム同

I × J 行列とし，次のような線形回帰モデル
x = As + z

的関数を間接的に最小化する手法であり，EM アルゴ
様に補助関数法はいかなる最適化問題に適用可能というわけではないが，ある要件を満たす補助関数が設計(1)

できれば大変効率の良い最適化アルゴリズムが導ける場合がある．以下に，補助関数法の原理を示し，補助を仮定（ただし，z は雑音を表す確率ベクトル）し，x, A が与えられたもとで，s の最ゆう推定値を求める線形回帰分析の問題を考える．z にもしガウス性
白色雑音を仮定すると，これは 2 ノルム x − As22
1018

関数が満たすべき要件を明らかにする．
目的関数 L(s) に対し，

L(s) = min L+ (s, B)
B(5)

論文／予測誤差の Golomb-Rice 符号量を最小化する線形予測分析

が成り立つとき，L+ (s, B) を L(s) の補助関数，B を補助変数と定義すると，次の定理が成り立つ．
定理 1（補助関数法） 補助関数 L+ (s, B) を，B に関して最小化するステップと，s に関して最小化するス
テップを繰り返すことで，目的関数 L(s) を単調減少させていくことができる．
（ 証 明）Bt+1 = argminB L+ (st , B) と し ，st+1 =argmins L+ (s, Bt+1 ) と す る ．た だ し ，t は 反 復 計
算 の ス テップ 数 を 表 す．s = st , B = Bt か
ら s = st+1 , B = Bt+1 に 更 新 さ れ た と き に ，L(s) が 非増 加 す る こ とを 示 す．明 ら か に L(st ) =L+ (st , Bt+1 ) であり，st+1 = argmins L+ (s, Bt+1 )より，L+ (st , Bt+1 ) ≥ L+ (st+1 , Bt+1 ) である．更に補助関数の定義より，L+ (st+1 , Bt+1 ) ≥ L(st+1 ) なのだから，結局，L(st ) ≥ L(st+1 ) である．
2
以上より，補助関数法を効果的に適用するには，次

図 1 絶対値関数とそれに接する放物線 (b = 0.1, 3, 5)
Fig. 1 Quadratic functions with b = 0.1, 3, 5 tangent
to the absolute value function.

が成り立ち，等号は接点 z = b において成立する．
この不等式を式 (2) に当てはめると，

L(s) ≤の 2 点を満たす補助関数を設計する必要がある．
（要件 1） argminB L+ (s, B) が解析的に求められる．
（要件 2） argmins L+ (s, B) が解析的に求められる．
更に，要件 1,2 を満たす L+ (s, B) が複数存在する場

合，その中で L(s) に最も近いものを補助関数として採用することが望ましい．これを踏まえ，式 (2) の最小化問題を解くための補助関数を以下で設計する．

Ixi − (As)i2|bi |

i=1= x − As

T

2

|bi |
+
2


(9)



B x − As + d ≡ L+ (s, B)のような不等式が立てられる．ただし，

⎛
⎜

B=⎜
⎝

1
2|b1 |

⎞

0
..

.
1
2|bI |

0

I

⎟
|bi |
⎟, d =
(10)
⎠
2
i=1

2. 4 二次形式の補助関数の導出
式 (2) の最小化のための補助関数を設計するにあたである．以上より，L+ (s, B) は補助関数の定義を満た

り，絶対値関数より小さくなることがなく（補助関数

す．次に，L+ (s, B) が補助関数の要件を満たすかどうの定義より），かつ，絶対値関数に接する（要件 1 よかを確認する．

り）二次関数（要件 2 より）を見つけたいが，このような二次関数は無数に存在する．二次関数を絶対値関数にできるだけ近づけるためには二次の係数を小さくとればよいので，条件を満たす二次関数の中で二次の係数が最小となるものを選べばよい．絶対値関数

f0 : R → R+

⎛
⎜

B=⎜
⎝

1
2|x1 −(As)1 |

0
..

(6)

に b = 0 で接する原点に関して対称な二次関数（図 1）

|b|
z2
+
h0 (z) =
2|b|
2

(7)

が f0 (z) を下回らず，かつ，f0 (z) に接する二次関数

2

⎞
⎟
⎟
⎠

(11)

である．一方，B 固定のときに L+ (s, B) を最小化す
る s は，式 (11) より，大きい残差には小さい重みを，小さい残差には大きい重みを課す重み付き最小二乗誤差推定量に相当し，正規方程式の解

s= AT BA

−1

AT Bx

(12)

で与えられる．AT BA は正定値対称行列であるのの中で二次の係数が最小となる．すなわち，2 z  ≤ z + |b|.
1
2|xI −(As)I |0 f0 (z) = z 

2|b|

2. 5 予測係数と補助変数の更新則
まず，L(s) = L+ (s, B) となる B は明らかに，(8)

で，s は Cholesky 分解で求めるとよい．以上より，

L+ (s, B) は補助関数の要件を満たし，次の手順
1019

電子情報通信学会論文誌 2008/11 Vol. J91–A No. 11（ 1 ） s の初期値設定（ 2 ） s と B を次のように交互に更新

⎛
⎜

B←⎜
⎝

1
2|x1 −(As)1 |

0
..

.
1
2|xI −(As)I |0s ← AT BA

−1

⎞
⎟
⎟
⎠

AT Bx

により，回帰係数の絶対誤差最小解を得ることができる．式 (2) は s に関して凸なので，収束解は大域最適解に一致する．ただし，大域最適解は一意とは限らず（大域最適解の集合は解空間上で凸集合をなし），提案

Fig. 2図 2 Golomb-Rice 符号量 R(z) (r = 4)
Golomb-Rice code length R(z) with r = 4.

法はその中の 1 点を求めるものである．以上のアルゴ



リズムは，ロバスト推定の一つである Huber の M 推
定 [11] に用いられる IRLS 法 [8] と同じ手続きをとる．

f1 (z) ≡1 推定量を得るための上記手順においては IRLS 法との間に違いはないが，次章で違いを明らかにする．

3. 残差符号量を最小化する線形予測分析
3. 1 Golomb-Rice 符号量モデル
振幅 z ∈ Z に対する Golomb-Rice 符号量 R(z) は，

⎧

z
⎪
⎨ r−1 + r + 1(z ≥ 0)2
R(z) = −1⎪⎩ −zr−1+ r + 1 (z < 0)

(13)

2

と表せる．ただし， · は切捨て整数化演算子を表し，

z2
+ βγ
4βγ

(|z| ≤ 2β)|z|/γ(|z| > 2β)
f2 (z) ≡f3 (z) ≡z2 + β2
γ

⎧
⎪
⎪
⎨β/γ

(z−|β−c|)2
+ βγ
4cγ

⎪
⎪
⎩|z|/γ(|z| ≤ β − c)(β − c < |z| ≤ β + c)(|z| > β + c)を導入する．β/γ = r + 1，γ = 2r−1 であり，β, γ はGolomb-Rice パラメータに依存して一意に決まる定数である．f1 (z) は Huber 尺度，f2 (z) は 1 -2 尺度と呼ばれる．c は 0 < c ≤ β の範囲で適当に定める定数r ∈ N は Golomb-Rice パラメータである．2. で最であり，c → 0 で f3 (z) は Vapnik’s ε-insensitive [12]

小化しようとした残差振幅の絶対誤差は，r = 1 とおに漸近する．また，c = β で f1 (z) = f3 (z) となる．

いた場合の Golomb-Rice 符号量のモデルに相当する．

各々の概形を図 3 に示す．以上の符号量モデルを用い，

しかし Golomb-Rice 符号化では実際のところ r > 1

残差符号の全符号量を近似した 3 種類の目的関数と設定することが多く，式 (13) は図 2 のように階段形の関数となる．ここで特に注目すべきは，z = 0 周
辺の一定範囲内の値には等しい符号量が割り当てられLn (s) =I

fn xi − (As)i(n = 1, 2, 3) (14)i=1

る点であり，このことは，残差振幅の絶対値をできるが立てられる．いずれの目的関数においても s の最適だけ小さくすることだけに専念するよりも，0 付近の解は γ によらないので，以後簡単のため γ = 1 とす

残差振幅には適度な「遊び」をもたせ，その自由度のる．なお，これらはいずれも s に関してやはり凸であ分だけ極端な外れ値を少なくする方が全体の符号量をり，局所解と大域最適解は一致する．

より小さくできることを示している．残差振幅が通常

これらの目的関数はいずれも s に関して非線形であ0 付近に集中する点を考慮すると，残差振幅にかかる符号量に則した目的関数は，z = 0 周辺の R(z) をより，線形計画法をベースにした手法や，重み付きメジく近似したもので表された方がよいと考えられる．

いても，最適解近傍以外のあらゆる点で Hesse 行列がアン法は適用できない．また，いずれの目的関数にお以 上 の 問 題 意 識 に 基 づ き ，絶 対 値 関 数 に 代 わ る

ほぼ零行列になると考えられ，ニュートン法をはじめ

次 の よ う な 3 種 類 の Golomb-Rice 符 号 量 モ デ ルとするこう配法はうまく動作しないことが予想される．

f1 (z), f2 (z), f3 (z)これに対し，2. で提案した原理はこれらの目的関数1020

論文／予測誤差の Golomb-Rice 符号量を最小化する線形予測分析

Ln (s) ≤ x−As−wnT

Bn x−As−wn + dn

≡ L+ (s, Bn , wn )(15)

なる不等式が立てられ，補助関数 L+ (s, Bn , wn ) が設計できる．ここでは，Bn だけでなく wn も補助変数であることに注意が必要である．wn は，コストが最小となる残差振幅ベクトル値を表す．すなわち，wn
が 0 以外の値をとる場合には，残差振幅値の絶対値を0 に近づけさえすればよいというわけではなくなる．
wn を補助変数とすることは，反復計算の過程で残差振幅値がある程度小さな値になってさえいれば十分とみなし，その分，他の大きな残差振幅値を小さくする
よう促す効果をもたらすのである．
さて，2. 同様，補助関数法の定理に基づき，（ 1 ） s の初期値設定（ 2 ） s と Bn , wn を次のように交互に更新

⎛ (n)

⎜
Bn ← ⎝b1

0..

0s ← A T Bn A
図 3 Golomb-Rice 符号量モデル fn (z) (n = 1, 2, 3)
Fig. 3 Golomb-Rice code length models fn (z).

.

⎞⎛ (n) ⎞w1⎟
⎜ . ⎟⎠ , wn ← ⎝ .. ⎠

(n)

−1

(n)

wI

bI

AT Bn (x − wn )により，目的関数 Ln (s) を最小化する回帰係数を得る(n)ことができる．行列 Bn の対角要素 bi

及びベクトル(n)
wn の要素 wi の更新則は，符号量モデルの選択にの最小化に対しても同様に適用できる．

3. 2 補助関数の導出
各々の符号量モデル fn (z) (n = 1, 2, 3) に対し，2.
と同様の方針で，二次関数 hn (z)h1 (z) =max(|b|, 2β)z2+
2 max(|b|, 2β)
2
z2

応じて

1
(1)
, wi = 0
2 max(|zi |, 2β)
1
(2)
(2)
bi = 
, wi = 02 zi2 + β 2(1)bib2 + 2β 2h2 (z) = + 
2 b2 + β 2
2 b2 + β 2

(3)

bi

h3 (z) =

⎧ 2
z
+ |b|
(|b| ≥ 2β)
⎪
2|b|
2
⎪
⎪
⎪
⎨ (z−(2sign(b)β−b))2 + β (β + c < |b| < 2β)4(|b|−β)(z−sign(b)(β−c))2⎪+ β (β − c < |b| < β + c)⎪4c⎪⎪
⎩ (z−b)24(β−|b|)+β=(0 ≤ |b| < β − c)がそれぞれ導出できる（h3 (z) の導出は付録参照）．

(3)

wi

=

⎧
1
⎪
2|zi |⎪⎪⎪⎨ 1(|zi | ≥ 2β)(β + c ≤ |zi | < 2β)

⎪
⎪
⎪
⎪
⎩

4(|zi |−β)14c(β − c ≤ |zi | < β + c)14(β−|zi |)(0 ≤ |zi | < β − c)

=

⎧
0
⎪
⎪
⎪
⎪
⎨2sign(z )β − zi(|zi | ≥ 2β)i⎪sign(zi )(β − c)
⎪
⎪
⎪
⎩
zi

(β + c ≤ |zi | < 2β)(β − c ≤ |zi | < β + c)
(0 ≤ |zi | < β − c)hn (z) (n = 1, 2, 3) はいずれも fn (z) と点 b で接し，fn (z) より決して小さくなることのない二次関数の中と与えられる．ただし，zi = xi − (As)i である．

で二次の係数が最小のものである．これにより，それ証されない．この点が，補助関数法により導出されたぞれの目的関数について統一的に提案法と IRLS 法の原理的な違いと優位性を端的に示

なお，IRLS 法では目的関数 L3 (s) の単調減少は保1021

電子情報通信学会論文誌 2008/11 Vol. J91–A No. 11

している．
また，2. のアルゴリズムは，反復計算の過程で，
xi − (As)i  = 0(16)となる i が少なくとも一つ存在すると，行列 AT BA
は非正則となり，反復計算が続けられなくなるという不安定さがあったのに対し，本章で述べた Bn の更新式ではいずれも行列の対角要素が 0 より大きいため，
Bn が原因となって行列 AT Bn A が非正則になることはないという利点がある．

4. 評 価 実 験
4. 1 収束性の確認
まず，提案法の収束性を確認するための評価実験

図 4 各次数における収束の様子（横軸：初期値及び反復計算回数，縦軸：初期値で正規化された絶対値和の値，初期値は Levinson-Durbin（L-D）法の解）
Fig. 4 Transitions of the sum of the absolute value ofpredictive errors divided by the initial residue,
obtained via Levinson-Durbin algorithm.

を行った．実験データは文献 [13] に収録されている
音声認識実験用の音声データ（サンプリング周波数：

16 kHz，振幅語長：16 bit，モノラル，合計約 140 秒）を用い，線形予測分析の次数は 4，8，12 でそれぞれ固定とし，分析フレームは 1024 サンプルとして，2.
の各反復計算における絶対値和（各フレームにおける残差振幅の絶対値和の合計値）の挙動を調べた．
図 4 は，各次数（四次：四角印，八次：三角印，十二次：丸印）において補助関数法の更新によりどれだ
け絶対値和が変化していくかを表しており，初期値のLevinson-Durbin 法で求めたときの絶対値和で正規化している．いずれの次数でも 10 回程度の反復計算で収束していることが分かる．四次の場合は二乗誤差規準と比べて約 3%絶対値和が小さくなっており，十二図 5 初期値を Levinson-Durbin 法と Burg 法で求めた場合の絶対誤差収束の様子
Fig. 5 Transitions of the absolute errors whose initialpoints were given respectively by LevinsonDurbin algorithm and Burg method.

次では約 5%小さくなっている．このことから，処理時間と最小化の度合のトレードオフを考えると，5 回

既存アルゴリズムの後処理として組み込むこともでき

程度の反復計算で十分な性能が得られると考えられる．

るため実用的である．

2. の収束解が大域最適解に一致することを確かめ

4. 2 圧縮率の確認るため，異なる初期値でも同じ絶対値和に収束するか

ここでは，音響信号を対象として，提案法の圧縮性どうかを調べた．図 5 は四次の予測において，初期能の評価実験を行った．本実験の目的は，提案法の原値を Levinson-Durbin 法と Burg 法の 2 通りで求め理を実証することだけでなく，線形予測分析に基づくた場合の収束性の違いを表している．前図と同様に可逆圧縮符号化において残差の符号量削減の余地がど

Levinson-Durbin 法で求めたときの絶対値和で正規化の程度残されているのかを見極めることである．

している．いずれの初期値から反復計算を始めても，評価実験用に，RWC 研究用音楽データベース [14]絶対値和がほぼ同一の値に収束していくのが分かる．

に含まれる，サンプリング周波数 44.1 kHz，16 ビッ

八次や十二次の場合も，同様の結果であった．

トで収録されたステレオの音楽ファイル（WAV 形式）

両図において，反復計算を繰り返すごとに絶対値和10 個（RWC-MDB-P-2001 No.33〜42）を実験データ

はほぼ単調に減少している．単調な収束性をもつ提案（合計約 432 MByte）として用いた．分析フレーム長

法は，処理時間と圧縮性能のトレードオフのバランス

は 2048 サンプルとした．

を自由に調節できたり，初期値に依存しないことから
1022

Levinson-Durbin 法に基づく二乗誤差規準の線形予

論文／予測誤差の Golomb-Rice 符号量を最小化する線形予測分析

図6

二乗誤差規準の線形予測符号化（従来法）に対する，
L2 (s) 及び L3 (s) を規準とした線形予測符号化（提案法 1&2) による圧縮率の比較
Fig. 6 Comparison of the compression ratios among
the devised methods and the conventional 2 norm-based-LPC.

図 7 予測次数が十五次の場合の圧縮率と演算速度の関係
Fig. 7 Trade-oﬀ between the compression ratio andthe computational cost when setting the number of LPC coeﬃcients to 15.

リアルタイムファクタ (%)
測分析の従来の方式を従来法，従来法で得られた予測係数を初期値として，3. 1 で示した L2 (s) 及び L3 (s)を規準とした反復最適化アルゴリズムによる線形予測
分析の方式をそれぞれ提案法 1，提案法 2 と略称する．
提案法 1 及び提案法 2 の反復計算回数は 10 とした．
なお，各方式ではいずれもチャネル間相関に基づく圧縮は行っていない．また，予測次数（式 (4) におけるJ ）は固定とした．
L2 (s) は 2 ノルムに比べて Golomb-Rice 符号量に則した目的関数となっているため，従来法に比べ，提案法 1 の圧縮率は向上するものと予想される．一方，

L3 (s) は L2 (s) に比べてより Golomb-Rice 符号量に則した目的関数となっているため，提案法 1 に比べ，提案法 2 の圧縮率は若干向上するものと予想される．
従来法，提案法 1，提案法 2 それぞれについての，予測次数が 7，15，31 の場合の圧縮率を図 6 に示す．
圧縮率は，次のように算出した．

=

圧縮にかかった総時間
× 100
総演奏時間

とした．100%のときに実時間で動作し，10%であれば10 倍速く動作する．つまりこの値が小さいほど性能が良い．また実験には Windows Server 2003, AMD

Opteron プロセッサ 2.4 GHz，メモリ 2 GByte を搭載した計算機を用いた．
初期値を Levinson-Durbin 法で求めても，Burg 法
で求めても，10 回程度で収束していることが分かる．
また，10 回の反復計算を行っても，実時間よりも高速に処理を終えることができることが分かる．

5. む す び
本論文では，従来の線形予測分析による可逆圧縮符
号化は残差符号量を直接的に小さくするものではな
かった点に着目し，残差符号量をできるだけ小さくする線形予測分析法の確立を目的とし，（ 1 ）残差の符号

圧縮後のファイルサイズ
圧縮率 (%) =× 100
もとのファイルサイズ

号量との関係をモデル化し，（ 2 ）Golomb-Rice 符号

図 6 より，予想どおり，提案法 2 による圧縮率が最も量モデルに基づいて立てられる目的関数の最小解を効高く，次いで提案法 1 による圧縮率が高かった．以上

率的に求める反復アルゴリズム（補助関数法）を考案の結果から，提案法の有効性と，提案法により実現さした．

化に利用される Golomb-Rice 符号における振幅と符れた残差符号量削減の度合を確認することができた．

実験結果より，提案法は初期値から 10 回程度の反なお，L1 (s) を規準とした場合と L2 (s) を規準とした復計算で単調に収束することと，初期値には依存せず場合とで圧縮率の差はほとんど見られなかったため，に収束することが確認された．ただし，ここでの初期

L1 (s) を規準とした場合の結果については省略した．
図 7 は予測次数が十五次の場合の圧縮率と演算速度の関係を示している．圧縮にかかる時間は “timeit.exe”

値は二乗誤差最小化規準で求めたものであるという条により計測し，リアルタイムファクタはできたり，容易に既存アルゴリズムに組み込むことが件付きである．単調な収束性をもつ提案法は，処理時間と圧縮性能のトレードオフのバランスを自由に調節1023

電子情報通信学会論文誌 2008/11 Vol. J91–A No. 11

できるため実用的である．また，提案法により圧縮率の向上を確認した．
一方，原理面では，提案法は，ある条件を満たす目

York, 1998.
[13]

鹿野清宏，伊藤克亘，河原達也，武田一哉，山本幹雄（編），[14]

音声認識システム，オーム社，東京，2001.
後藤真孝，橋口博樹，西村拓一，岡 隆一，“RWC 研究

的関数を規準とする場合には IRLS 法と同一の反復ア

用音楽データベース：研究目的で利用可能な著作権処理済

ルゴリズムを与えることが明らかになった．しかしなみ楽曲・楽器音データベース，” 情処学論，vol.45, no.3,
pp.728–738, 2004.

がら，IRLS 法では収束性が保証されない目的関数に対しても，提案法の枠組みでは収束性が保証された反付録

復アルゴリズムを導けることを例示した．このことで，提案法は IRLS 法より幅広いクラスの目的関数を扱える方法論であることが示される．
謝辞

本研究は，東京大学大 学院小野 順貴講 師，

嵯峨山茂樹教授との議論を通して進展したものです．
有益な議論をして頂いた御両名に感謝致します．
文

献

[1]

S.W. Golomb, “Run-length encodings,” IEEE Trans.

[2]

T. Liebchen and Y. Reznik, “MPEG-4 ALS: An

Inf. Theory, vol.12, no.3, pp.399–401, 1966.
emerging standard for lossless audio coding,” Proc.
IEEE Data Compression Conference 2004, pp.439–

ここでは，f3 (z) に点 b で接し，f3 (z) を下回らない二次関数の中で二次の係数が最小のものを求めたい．まず，|b| ≥ 2β では式 (7) の頂点は β より下回らないため，式 (7) が上記要件を満たす．次に，β +c ≤ |b| < 2βでは，点 b で |z| に接し，かつ，頂点が β に接する二次関数が要件を満たすので，

k(b − l)2 + β = |b|, 2k(b − l) = sign(b) (A·1)となる k, l を連立して解けばよく，これを解けば

k=1, l = 2sign(b)β − b4(|b| − β)(A·2)

448, 2004.
[3]

T.E. Harris, “Regression using minimum absolute de-を得る．次に，β − c ≤ |b| < β + c においては，f3 (z)viations,” American Statistician, vol.4, no.1, pp.14–が β − c ≤ z < β + c において二次関数であるため，

15, 1950.
[4]

I. Barrodale and F.D.K. Roberts, “An improved algorithm for discrete 1 linear approximation,” SIAM
J. Numer. Anal., vol.10, no.5, pp.839–848, 1973.

[5](z − |β − c|)2
+β
4c

(A·3)

Y. Zhang, “Primal-dual interior point approach forが要件を満たす．最後に，0 ≤ |b| < β − c においてcomputing 1 -solutions, and ∞ -solutions of overde-は，頂点が (b, β) であり，かつ，sign(b)z に接する二termined linear systems,” J. Optim. Theory Appl.,

次関数が要件を満たすので，vol.77, no.2, pp.323–341, 1993.
[6]

P. Bloomﬁeld and W. Steiger, “Least absolute devia-k(z − b)2 + β = sign(b)z(A·4)

tions curve-ﬁtting,” SIAM J. Sci. Stat. Comp., vol.1,
no.2, pp.290–301, 1980.
[7]

worth’s method for minimum absolute error linear regression,” IEEE Trans. Signal Process., vol.42, no.8,
pp.2045–2054, 1994.
[8]

P. Green, “Iterative reweighted least squares for
maximum likelihood estimation and some robust
and resistant alternative (with discussions),” J. Roy.
Statist. Soc., Series B, vol.46, pp.149–162, 1984.

[9]

E. Denoël and J.-P. Solvay, “Linear prediction of
speech with a least absolute error criterion,” IEEE
Trans. Acoust. Speech Signal Process., vol.ASSP-33,
no.6, pp.1397–1403, 1985.

[10]

C.-H. Lee, “On robust linear prediction of speech,”
IEEE Trans. Acoust. Speech Signal Process., vol.36,
no.5, pp.642–650, 1988.

[11]

P.J. Huber, Robust Statistics, Wiley, New York,
1981.

[12]

が重解をもつように k を決めればよく，これを解けばR.W. Hawley and N.C. Gallagher, Jr., “On edge-

V. Vapnik, Statistical Learning Theory, Wiley, New

1024

k=

1
4(β − |b|)

(A·5)

を得る．
（平成 20 年 2 月 18 日受付，6 月 11 日再受付）

論文／予測誤差の Golomb-Rice 符号量を最小化する線形予測分析

亀岡

弘和 （正員）2002 東大・工・計数卒．2004 同大大学
院・情報理工システム情報修士課程了．2007

同博士課程了．情報理工博．同年日本電信電話（株）入社．以来，音楽，音声を対象とした音響信号処理の研究に従事．現在，
NTT コミュニケーション科学基礎研究所
勤務．第 20 回電気通信普及財団テレコムシステム技術学生

賞，Best Student Paper Award Finalist at ICASSP2005，
情報処理学会平 17 年度山下記念研究賞，日本音響学会第 2 回
独創研究奨励賞板倉記念，平 18 年度東京大学大学院情報理工学系研究科研究科長賞，第 1 回 IEEE Signal Processing
Society Japan Chapter Student Paper Award，日本音響学会第 25 回粟屋潔学術奨励賞を受賞．情報処理学会，日本音響学会，IEEE 各会員．

鎌本

優 （正員）

2003 慶大・理工・物理情報卒．2005 東大大学院・情報理工・システム情報修士課

程了．同年日本電信電話（株）入社．以来，信号処理，情報理論に関する研究に従事．
現在，NTT コミュニケーション科学基礎研究所勤務．平成 17 年度情報処理学会論文賞第 21 回電気通信普及財団テレコムシステム技術学生賞，第 22 回電気通信普及財団テレコムシステム技術賞（奨励賞）．
日本音響学会，情報処理学会，情報理論とその応用学会，IEEE
各会員．

原田

登 （正員）

1995 九工大・情報工卒．1997 同大大学
院・情報シス修士課程了．同年日本電信電話（株）入社．以来，音声・楽音の高能率符
号化，音声情報処理，VoIP の研究に従事．
現在，NTT コミュニケーション科学基礎研究所研究主任．第 22 回電気通信普及財
団テレコムシステム技術賞（奨励賞）．日本音響学会，AudioEngineering Society, IEEE 各会員．

守谷

健弘 （正員）1978 東大・工・計数卒．1980 同大大学
院・工・計数修士課程了．同年日本電信電話公社（現 NTT）入社．以来，音声音響
信号の符号化の研究開発，標準化に従事．
1989 工学博士．同年 AT&T ベル研究所客員研究員．現在，NTT コミュニケーショ
ン科学基礎研究所特別研究室長，NTT フェロー．本会より学術奨励賞，論文賞，業績賞・小林記念特別賞受賞．IEEE（フェロー），日本音響学会，情報処理学会，情報理論とその応用学会，Audio Engineering Society 各会員．

1025