双線形補間

数学において、双線形補間（そうぎどうひょう）とは、反復線形補間を用いて2変数（例えばxとy ）の関数を補間する手法である。通常は2次元の直線グリッド上でサンプリングされた関数に適用されるが、任意の凸四辺形（のメッシュ）の頂点上で定義された関数にも一般化できる。

双線形補間は、まず一方向に線形補間を行い、次に別の方向に線形補間を行います。各ステップはサンプリング値と位置において線形ですが、補間全体は線形ではなく、サンプリング位置において2次関数となります。

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

計算

点 ( x , y ) における未知関数fの値を求めたいとします。f の4つの点Q ₁₁ = ( x ₁ , y ₁ )、Q _{12 = ( x 1 , y 2 )、}Q ₂₁ = ( x ₂ , y ₁ )、Q 22 ₌ ( x 2 _, y 2 ₎における値は既知で_あると仮定し_ます。

繰り返し線形補間

まずx方向の線形補間を行う。これは以下の式となる。

{\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方向に補間していきます。

{\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)\\&{\begin{aligned}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}(&f(Q_{11})(x_{2}-x)(y_{2}-y)+f(Q_{12})(x_{2}-x)(y-y_{1})\\&+f(Q_{21})(x-x_{1})(y_{2}-y)+f(Q_{22})(x-x_{1})(y-y_{1}))\end{aligned}}\\&={\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]

多項式近似

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

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

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

{\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}}

結果をもたらす

{\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 )の加重平均として書くこともできます。

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となり、転置線形システムを満たす。

{\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}},

結果をもたらす

{\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}}

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

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

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

代替行列形式

上記を組み合わせると、

{\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）の座標系を選択すると、補間式は次のように簡略化されます。

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,

あるいは、行列演算では次のように表せます。

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}}.

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

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

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

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

どこ

{\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 次元に拡張したものが三線形補間と呼ばれます。

逆計算

を、によってパラメータ化された単位正方形上に双線形補間されるベクトル場とします。補間を反転するには、2 つの双線形多項式方程式の連立を解く必要があります。ここで、の2 次元外積 (グラスマン積を参照) を慎重に選んだベクトルと取ると、次の項を消去できます。これは、に展開されます。ここで、 2 次方程式は、2 次方程式の公式を使用して解くことができます。同等の行列式と解が得られます (線形関係により、符号が反対になります)。またはの場合は、別々に処理する必要があります。適切な条件が与えられれば、2 つの解のうちの 1 つは単位正方形内に存在するはずです。 ${\textstyle F}$ ${\textstyle \mu ,\lambda \in [0,1]}$ $A+B\lambda +C\mu +D\lambda \mu =0$ ${\begin{aligned}A&=F_{00}-F\\B&=F_{10}-F_{00}\\C&=F_{01}-F_{00}\\D&=F_{11}-F_{01}-F_{10}+F_{00}\end{aligned}}$ ${\begin{aligned}(A+B\lambda +C\mu )&\times D&=0\\(A+B\lambda )&\times (C+D\lambda )&=0\\(A+C\mu )&\times (B+D\mu )&=0\\\end{aligned}}$ ${\begin{aligned}c+e\lambda +f\mu &=0\\b+(c+d)\lambda +e\lambda ^{2}&=0\\a+(c-d)\mu +f\mu ^{2}&=0\\\end{aligned}}$ ${\begin{aligned}a&=A\times B\\b&=A\times C\qquad d=B\times C\\c&=A\times D\qquad e=B\times D\qquad f=C\times D\end{aligned}}$ $\mathbb {D} =(c+d)^{2}-4eb=(c-d)^{2}-4fa$ $\lambda ={\frac {-c-d\pm {\sqrt {\mathbb {D} }}}{2e}}\qquad \mu ={\frac {-c+d\mp {\sqrt {\mathbb {D} }}}{2f}}$ $e=0$ $f=0$

画像処理への応用

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

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

双線形補間は、ピクセルマッチングによる完全な画像変換が不可能な場合に使用でき、適切な輝度値を計算してピクセルに割り当てることができます。最近傍補間や双三次補間などの他の補間手法とは異なり、双線形補間では、特定のピクセルから対角方向に位置する最も近い4つのピクセルの値のみを使用して、そのピクセルの適切な色輝度値を求めます。

双線形補間では、未知のピクセルの計算位置を囲む、既知のピクセル値の最も近い2×2近傍を考慮します。そして、これら4つのピクセルの加重平均を計算し、最終的な補間値を求めます。^[5]^[6]

例

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

{\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}}

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

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.

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

用語の簡素化

この例は、ある変数に対する参照として、表形式の圧力 (列) 対温度 (行) データを示しています。

{\begin{array}{|c|ccc|}{\bcancel {{}_{T}\quad {}^{P}}}&P_{1}&P_{x}&P_{2}\\\hline T_{1}&V_{11}&V_{1x}&V_{12}\\T_{x}&&V_{xx}&\\T_{2}&V_{21}&V_{2x}&V_{22}\end{array}}

次の標準的な部分計算には 27 個の演算があります。

{\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}}

上記には、、、、、などの繰り返し演算といくつかの比が含まれています。これらの繰り返し演算には、単一の補間を計算する際に一時変数を割り当てることができます。これにより、演算回数は19回に減ります。 $(P_{2}-P_{1})$ $(P_{x}-P_{1})$ $(P_{x}-P_{1})$ $(T_{2}-T_{1})$

これを、最初の 19 個の個別操作から次のように 17 個の個別操作に簡略化できます。

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})}}.

用語の簡素化は、数学的手法を工学アプリケーションに適用するための良い方法であり、プロセスの計算およびエネルギー要件を削減することができます。^{[引用が必要]}

参照

参考文献

^ Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1992). Numerical Recipes in C: the art of scientific computing (第2版). ニューヨーク, NY, USA: Cambridge University Press. pp. 123-128. ISBN 0-521-43108-5。
^ Monasse, Pascal (2019-08-10). 「双線形画像のレベルラインの抽出」. Image Processing on Line . 9 : 205–219 . doi : 10.5201/ipol.2019.269 . ISSN 2105-1232.
^ Quilez, Inigo (2010). 「逆双線形補間」. iquilezles.org . 2010年8月13日時点のオリジナルよりアーカイブ。 2024年2月17日閲覧。
^ 双線形補間の定義 (www.pcmag.com の人気記事)。
^ Khosravi, MR (2021-03-19). 「BL-ALM：グリーンIoMT-UAVネットワークを介したスマート環境モニタリングのためのブラインドスケーラブルエッジガイド再構成フィルタ」. IEEE Transactions on Green Communications and Networking . 5 (2): 727– 736. Bibcode :2021ITGCN...5..727K. doi :10.1109/TGCN.2021.3067555. S2CID 233669511.
^ 「Web チュートリアル: デジタル画像補間」。

[1] Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1992). Numerical Recipes in C: the art of scientific computing (第2版). ニューヨーク, NY, USA: Cambridge University Press. pp. 123-128. ISBN 0-521-43108-5。

[2] Monasse, Pascal (2019-08-10). 「双線形画像のレベルラインの抽出」. Image Processing on Line . 9 : 205–219 . doi : 10.5201/ipol.2019.269 . ISSN 2105-1232.

[3] Quilez, Inigo (2010). 「逆双線形補間」. iquilezles.org . 2010年8月13日時点のオリジナルよりアーカイブ。 2024年2月17日閲覧。

[4] 双線形補間の定義 (www.pcmag.com の人気記事)。

[5] Khosravi, MR (2021-03-19). 「BL-ALM：グリーンIoMT-UAVネットワークを介したスマート環境モニタリングのためのブラインドスケーラブルエッジガイド再構成フィルタ」. IEEE Transactions on Green Communications and Networking . 5 (2): 727– 736. Bibcode :2021ITGCN...5..727K. doi :10.1109/TGCN.2021.3067555. S2CID 233669511.

[6] 「Web チュートリアル: デジタル画像補間」。