双線形補間

数学において、双線形補間は、反復線形補間を使用して2 つの変数 (たとえば、xとy )の関数を補間する方法です。通常は 2D直線グリッド上でサンプリングされた関数に適用されますが、任意の凸四辺形(のメッシュ)の頂点で定義された関数に一般化することもできます。

双線形補間は、最初に一方向の線形補間を使用して実行され、次に別の方向の線形補間を使用して実行されます。各ステップは、サンプル値と位置では線形ですが、補間全体は線形ではなく、サンプル位置では 2 次です。

双線形補間は、コンピュータビジョンと画像処理における基本的な再サンプリング手法の 1 つで、双線形フィルタリングまたは双線形テクスチャ マッピングとも呼ばれます。

点 ( x , y ) における未知の関数 f の値を求めるとします。4つの点Q ₁₁ = ( x ₁ ,  y ₁ )、Q ₁₂ = ( x ₁ ,  y ₂ )、Q ₂₁ = ( x 2 , y ₁ )、Q ₂₂ = ( x ₂ ,  y _{2 ) における}fの値がわかって_いるものと します。

まずx方向の線形補間を行う。これにより、

${\displaystyle {\begin{aligned}f(x,y_{1})={\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{11})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{21}),\\f(x,y_{2})={\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{12})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{22}).\end{aligned}}}$

望ましい推定値を得るために、 y方向に補間していきます。

${\displaystyle {\begin{aligned}f(x,y)&={\frac {y_{2}-y}{y_{2}-y_{1}}}f(x,y_{1})+{\frac {y-y_{1}}{y_{2}-y_{1}}}f(x,y_{2})\\&={\frac {y_{2}-y}{y_{2}-y_{1}}}\left({\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{11})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{21})\right)+{\frac {y-y_{1}}{y_{2}-y_{1}}}\left({\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{12})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{22})\right)\\&={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}\left(f(Q_{11})(x_{2}-x)(y_{2}-y)+f(Q_{21})(x-x_{1})(y_{2}-y)+f(Q_{12})(x_{2}-x)(y-y_{1})+f(Q_{22})(x-x_{1})(y-y_{1})\right)\\&={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}-x&x-x_{1}\end{bmatrix}}{\begin{bmatrix}f(Q_{11})&f(Q_{12})\\f(Q_{21})&f(Q_{22})\end{bmatrix}}{\begin{bmatrix}y_{2}-y\\y-y_{1}\end{bmatrix}}.\end{aligned}}}$

最初にy方向に沿って補間し、次にx方向に沿って補間した場合も同じ結果が得られることに注意してください。^[1]

別の方法としては、補間問題の解を多線型多項式として記述する方法がある。

${\displaystyle f(x,y)\approx a_{00}+a_{10}x+a_{01}y+a_{11}xy,}$

ここで係数は線形方程式を解くことによって求められる。

${\displaystyle {\begin{aligned}{\begin{bmatrix}1&x_{1}&y_{1}&x_{1}y_{1}\\1&x_{1}&y_{2}&x_{1}y_{2}\\1&x_{2}&y_{1}&x_{2}y_{1}\\1&x_{2}&y_{2}&x_{2}y_{2}\end{bmatrix}}{\begin{bmatrix}a_{00}\\a_{10}\\a_{01}\\a_{11}\end{bmatrix}}={\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}},\end{aligned}}}$

結果をもたらす

${\displaystyle {\begin{aligned}{\begin{bmatrix}a_{00}\\a_{10}\\a_{01}\\a_{11}\end{bmatrix}}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}y_{2}&-x_{2}y_{1}&-x_{1}y_{2}&x_{1}y_{1}\\-y_{2}&y_{1}&y_{2}&-y_{1}\\-x_{2}&x_{2}&x_{1}&-x_{1}\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}}.\end{aligned}}}$

解はf ( Q )の加重平均として表すこともできます。

${\displaystyle f(x,y)\approx w_{11}f(Q_{11})+w_{12}f(Q_{12})+w_{21}f(Q_{21})+w_{22}f(Q_{22}),}$

ここで重みの合計は1となり、転置線形システムを満たす。

${\displaystyle {\begin{bmatrix}1&1&1&1\\x_{1}&x_{1}&x_{2}&x_{2}\\y_{1}&y_{2}&y_{1}&y_{2}\\x_{1}y_{1}&x_{1}y_{2}&x_{2}y_{1}&x_{2}y_{2}\end{bmatrix}}{\begin{bmatrix}w_{11}\\w_{12}\\w_{21}\\w_{22}\end{bmatrix}}={\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}},}$

結果をもたらす

${\displaystyle {\begin{aligned}{\begin{bmatrix}w_{11}\\w_{21}\\w_{12}\\w_{22}\end{bmatrix}}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}y_{2}&-y_{2}&-x_{2}&1\\-x_{2}y_{1}&y_{1}&x_{2}&-1\\-x_{1}y_{2}&y_{2}&x_{1}&-1\\x_{1}y_{1}&-y_{1}&-x_{1}&1\end{bmatrix}}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}},\end{aligned}}}$

これは次のように単純化される

${\displaystyle {\begin{aligned}w_{11}&=(x_{2}-x)(y_{2}-y)/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{12}&=(x_{2}-x)(y-y_{1})/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{21}&=(x-x_{1})(y_{2}-y)/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{22}&=(x-x_{1})(y-y_{1})/((x_{2}-x_{1})(y_{2}-y_{1})),\end{aligned}}}$

これは、線形補間を繰り返して得られた結果と一致します。重みのセットは、長方形の 一般化された重心座標のセットとして解釈することもできます。

上記を組み合わせると、

${\displaystyle {\begin{aligned}f(x,y)\approx {\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}f(Q_{11})&f(Q_{12})&f(Q_{21})&f(Q_{22})\end{bmatrix}}{\begin{bmatrix}x_{2}y_{2}&-y_{2}&-x_{2}&1\\-x_{2}y_{1}&y_{1}&x_{2}&-1\\-x_{1}y_{2}&y_{2}&x_{1}&-1\\x_{1}y_{1}&-y_{1}&-x_{1}&1\end{bmatrix}}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}}.\end{aligned}}}$

fが既知である4つの点が(0, 0)、(0, 1)、(1, 0)、(1, 1)である座標系を選択すると、補間式は次のように簡略化されます。

${\displaystyle f(x,y)\approx f(0,0)(1-x)(1-y)+f(0,1)(1-x)y+f(1,0)x(1-y)+f(1,1)xy,}$

または、行列演算では次のように同等になります。

${\displaystyle f(x,y)\approx {\begin{bmatrix}1-x&x\end{bmatrix}}{\begin{bmatrix}f(0,0)&f(0,1)\\f(1,0)&f(1,1)\end{bmatrix}}{\begin{bmatrix}1-y\\y\end{bmatrix}}.}$

ここでは重みも認識します。

${\displaystyle {\begin{aligned}w_{11}&=(1-x)(1-y),\\w_{12}&=(1-x)y,\\w_{21}&=x(1-y),\\w_{22}&=xy.\end{aligned}}}$

あるいは、単位正方形上の補間式は次のように書くこともできる。

${\displaystyle f(x,y)=a_{00}+a_{10}x+a_{01}y+a_{11}xy,}$

どこ

${\displaystyle {\begin{aligned}a_{00}&=f(0,0),\\a_{10}&=f(1,0)-f(0,0),\\a_{01}&=f(0,1)-f(0,0),\\a_{11}&=f(1,1)-f(1,0)-f(0,1)+f(0,0).\end{aligned}}}$

どちらの場合も、定数の数 (4) は、 fが指定されたデータ ポイントの数に対応します。

名前が示すように、双線形補間は線形ではありません。ただし、xまたはy方向に平行な線に沿って線形 (つまりアフィン) になります。これは、 xまたはy が一定に保たれている場合と同じです。その他の直線に沿っては、補間は2 次式になります。補間は位置 ( xとy )では線形ではありませんが、上記の (行列) 方程式に見られるように、固定点では補間値では線形 です。

双線形補間の結果は、どの軸が最初に補間され、どの軸が次に補間されるかには依存しません。最初にy方向で線形補間を実行し、次にx方向で線形補間を実行した場合、結果の近似値は同じになります。

補間式は双線形多項式であり、ラプラス方程式を満たす調和関数でもあります。そのグラフは双線形ベジェ曲面パッチです。

一般に、補間は（頂点値の凸包内の）無限個の点（双曲線の枝を形成^[2] ）での任意の値をとるため、補間は可逆ではありません。

しかし、ベクトル場を補間する場合など、2 つの関数に同時に双線形補間を適用すると、補間は可逆になります (特定の条件下で)。特に、この逆補間は、任意の凸四辺形 内の点の「単位正方形座標」を見つけるために使用できます(四辺形の座標を、単位正方形上で双線形補間されるベクトル場と見なすことにより)。この手順を使用すると、双線形補間を任意の凸四辺形に拡張できますが、平行四辺形でない場合は計算が大幅に複雑になります。^{[3]四辺形間の結果として得られるマップは}、双線形変換、双線形ワープ、または双線形歪みとして知られています。

あるいは、四辺形と単位正方形の間の 射影マッピングを使用することもできますが、結果の補間は双線形にはなりません。

四辺形が平行四辺形である特殊な場合には、単位正方形への線形写像が存在し、一般化は容易に従います。

双線形補間を 3 次元に拡張したものは、三線形補間と呼ばれます。

コンピュータビジョンと画像処理では、画像やテクスチャを再サンプリングするために双線形補間が使用されます。アルゴリズムを使用して、画面のピクセル位置をテクスチャマップ上の対応するポイントにマッピングします。周囲の4つのテクセルの属性（色、透明度など）の加重平均が計算され、画面のピクセルに適用されます。このプロセスは、テクスチャリングされるオブジェクトを形成する各ピクセルに対して繰り返されます。^[4]

画像を拡大する必要がある場合、元の画像の各ピクセルをスケール定数に基づいて特定の方向に移動する必要があります。ただし、非整数スケール係数で画像を拡大すると、適切なピクセル値が割り当てられていないピクセル (つまり、ホール) が存在します。この場合、出力画像に値のないピクセルが含まれないように 、それらのホールに適切なRGB値またはグレースケール値を割り当てる必要があります。

双線形補間は、ピクセルを一致させた完全な画像変換が不可能な場合に使用でき、適切な強度値を計算してピクセルに割り当てることができます。最近傍補間や双三次補間などの他の補間手法とは異なり、双線形補間では、特定のピクセルから対角方向にある最も近い 4 つのピクセルの値のみを使用して、そのピクセルの適切な色強度値を見つけます。

双線形補間では、未知のピクセルの計算された位置を囲む既知のピクセル値の最も近い2×2近傍を考慮します。次に、これら4つのピクセルの加重平均を取り、最終的な補間値に到達します。^{[5] [6]}

右の例に示すように、行20.2、列14.5にあると計算されたピクセルの強度値は、まず行20と行21の列14と列15の値を線形補間することで計算でき、次のようになります。

${\displaystyle {\begin{aligned}I_{20,14.5}&={\frac {15-14.5}{15-14}}\cdot 91+{\frac {14.5-14}{15-14}}\cdot 210=150.5,\\I_{21,14.5}&={\frac {15-14.5}{15-14}}\cdot 162+{\frac {14.5-14}{15-14}}\cdot 95=128.5,\end{aligned}}}$

そしてこれらの値の間を線形補間すると、

${\displaystyle I_{20.2,14.5}={\frac {21-20.2}{21-20}}\cdot 150.5+{\frac {20.2-20}{21-20}}\cdot 128.5=146.1.}$

このアルゴリズムは、サイズ変更された画像の一部のピクセルが他のピクセルよりも大きく表示される最近傍補間とは対照的に、画像を非整数のズーム係数にサイズ変更することによって発生する視覚的な歪みを軽減します。

この例は、圧力（列）と温度（行）のデータを表形式で表し、ある変数に対する参照として用いたものである。

次の標準的な部分計算には 18 個の演算が必要です。

${\displaystyle {\begin{aligned}I_{T_{1},P_{1}-P_{2}}&={\frac {P_{2}-P_{x}}{P_{2}-P_{1}}}\cdot V_{11}+{\frac {P_{x}-P_{1}}{P_{2}-P_{1}}}\cdot V_{12}=V_{1x},\\I_{T_{2},P_{1}-P_{2}}&={\frac {P_{2}-P_{x}}{P_{2}-P_{1}}}\cdot V_{21}+{\frac {P_{x}-P_{1}}{P_{2}-P_{1}}}\cdot V_{22}=V_{2x},\\I_{P_{x},T_{1}-T_{2}}&={\frac {T_{2}-T_{x}}{T_{2}-T_{1}}}\cdot V_{1x}+{\frac {T_{x}-T_{1}}{T_{2}-T_{1}}}\cdot V_{2x}=V_{xx}\end{aligned}}}$

これにより、最初の 18 個の個別操作が 16 個の個別操作に簡素化されます。

${\displaystyle V_{xx}={\frac {((P_{2}-P_{x})\cdot V_{11}+(P_{x}-P_{1})\cdot V_{12})\cdot (T_{2}-T_{x})+((P_{2}-P_{x})\cdot V_{21}+(P_{x}-P_{1})\cdot V_{22})\cdot (T_{x}-T_{1})}{(P_{2}-P_{1})\cdot (T_{2}-T_{1})}}.}$

上記には 2 つの繰り返し操作があります。

${\displaystyle (P_{2}-P_{x}),(P_{x}-P_{1}).}$

これら 2 回の繰り返しには、1 回の補間を計算しながら一時変数を割り当てることができます。これにより、計算回数が 14 回の演算にまで減ります。これは、目的の補間を生成するために必要な最小のステップ数です。この補間を 18 回ではなく 14 回で実行することで、効率が 22% 向上します。

用語の簡略化は、数学的手法をエンジニアリング アプリケーションに適用するための優れた方法であり、プロセスの計算要件とエネルギー要件を削減できます。

• バイキュービック補間
• 三線補間
• スプライン補間
• ランチョス再サンプリング
• 階段状補間
• 重心座標- 三角形または四面体内の補間用