補間法
飛び飛びの値(表やサンプル)しか分かっていないときに、その間の値を推定する方法(補間)について説明します。
<注意>
このページでは、数式を表示するためにMathJaxを使用しています。ブラウザの設定でスクリプト実行をブロックしている場合、ページ内の数式が正しく表示されません。
補間とは
値が\(\ x = 0,\ 1,\ 2,\ \dots\ \)のところだけ分かっていて、その間(たとえば\(\ x = 2.3\ \))の値が必要になることがあります。
- 三角関数の表を引くとき、表の刻みより細かい角度の値が必要になる。
- 音のサンプルを、元と違う速さで再生する(サンプルとサンプルの間の値が必要になる)。
- 絵を拡大して表示する。
分かっている点から、その間の値を推定することを補間と言います。
分かっている点を\(\ p_0,\ p_1,\ \dots\ \)とし、点\(\ i\ \)と\(\ i+1\ \)の間の位置を\(\ t\ \)(\(\ 0 \le t < 1\ \))で表します。
最近傍補間
いちばん近い点の値をそのまま使います。
\[ f = \begin{cases} p_i & (t < 1/2) \\ p_{i+1} & (t \ge 1/2) \end{cases} \]計算はいりませんが、値が階段状に変わります。
表を引くときに「小数部を四捨五入して表を引く」のは、この方法です。
線形補間
両側の2点を直線で結びます。
\[ f = p_i + (p_{i+1} - p_i)\,t = (1-t)\,p_i + t\,p_{i+1} \]掛け算1回で済み、つながりに段差がなくなります。
ただし、点のところで折れ曲がります(傾きが急に変わります)。
コードでの書き方は、線形補間のレシピにあります。
誤差
定理
\[ \frac{h^2}{8}\,\max|g''| \]
間隔\(\ h\ \)で並んだ点の線形補間と、元のなめらかな関数\(\ g\ \)との差は、を超えない(\(\ g''\ \)は\(\ g\ \)を2回微分したもの、つまり曲がり具合)。
誤差は間隔の2乗に比例するので、表の大きさを2倍にすると、誤差は1/4になります。
表をそのまま引く(最近傍補間)と、誤差は間隔に比例するので、表を2倍にしても誤差は1/2にしかなりません。
1周を256に分けた正弦の表(256方位)を、そのまま引いたときの最大の誤差は約0.012ですが、線形補間すると約0.000075になります。
1周64の表でも、線形補間すれば誤差は約0.0012で、256の表をそのまま引くより10倍正確です。
表を小さくして補間するか、表を大きくしてそのまま引くかは、時間計算量と空間計算量の釣り合いで決めます。
多項式補間
\(\ n\ \)個の点をすべて通る\(\ n-1\ \)次の多項式は、ただ1つに決まります。
これを求めて間の値を計算する方法を多項式補間と言います。
定理 (ラグランジュ補間)
\[ f(x) = \sum_{j=0}^{n-1} p_j \prod_{m \neq j} \frac{x - x_m}{x_j - x_m} \]
点\(\ (x_0,\ p_0),\ \dots,\ (x_{n-1},\ p_{n-1})\ \)をすべて通る多項式は、である。
2点なら直線(線形補間)、3点なら放物線になります。
点が多いときに、全部の点を通る1つの多項式を使うと、点と点の間で大きく波打つことがあります(ルンゲの現象)。
真ん中では元の関数によく合っていますが、両端では大きく外れています。
多くの点を補間するときは、全体を1つの式にせず、近くの数点だけを使う式を、区間ごとに切り替えて使います。
3次補間
区間の両側の2点に、さらに外側の1点ずつを加えた4点を使い、3次式でつなぎます。
よく使われるのは、次のキャットムル-ロムの式です。
\(\ p_{i-1},\ p_i,\ p_{i+1},\ p_{i+2}\ \)を\(\ P_0,\ P_1,\ P_2,\ P_3\ \)と書くと、次のようになります。
この式は、各点を通り、さらに点\(\ P_1\ \)での傾きが\(\ (P_2 - P_0)/2\ \)(両隣を結ぶ直線の傾き)になるように作られています。
隣の区間とも傾きが揃うので、点のところで折れ曲がらず、なめらかにつながります。
同じ考え方で、点を通るなめらかな曲線を作る方法は、曲線で説明します。
2次元の補間
縦横に並んだ値(絵やマップの高さなど)の間を補間するには、横方向に線形補間したものを、さらに縦方向に線形補間します(双線形補間)。
\[ f = (1-t_y)\left((1-t_x)\,p_{00} + t_x\,p_{10}\right) + t_y\left((1-t_x)\,p_{01} + t_x\,p_{11}\right) \]
最近傍補間ではマス目がそのまま大きくなり、双線形補間では、マス目の間がなめらかにつながります。
SNESのモード7の拡大は、最近傍補間にあたります(拡大すると、1つのピクセルがそのまま大きな四角になります)。
音の補間
サンプルを元より速く(高い音で)再生すると、1つの出力の間にサンプルがいくつも進み、遅く(低い音で)再生すると、サンプルの間の値が必要になります。
| 方法 | 音の性質 |
|---|---|
| 最近傍補間 | 階段状の波形になり、元の音にない高い成分(ザラザラした音)が加わる |
| 線形補間 | 折れ線になり、高い成分は少し減る |
| 4点を使う補間 | なめらかになる。重みの付け方によって、高い成分の減り方が変わる |
DSPは、前後4つのサンプルに重みを掛けて足す補間(ガウス補間)を使います(BRRの「ガウス分布補間」)。
補間は、高い成分を弱めるフィルタとしても働きます(サンプリングとデジタルフィルタ)。