쌍선형 보간법

z 값이 0, 1, 1, 0.5인 단위 정사각형에 대한 쌍선형 보간의 예시. 보간된 값은 색상으로 표시된다.

수학에서 쌍선형 보간법(Bilinear interpolation)은 반복된 선형 보간법을 사용하여 두 변수(예: x와 y)의 함수를 보간하는 방법이다. 일반적으로 2D 직교 격자에서 샘플링된 함수에 적용되지만, 임의의 볼록 사각형의 정점(또는 폴리곤 메시의)에 정의된 함수로 일반화될 수 있다.

쌍선형 보간은 한 방향으로 선형 보간을 먼저 수행한 다음 다른 방향으로 다시 수행하여 이루어진다. 각 단계는 샘플링된 값과 위치에 대해 선형이지만, 보간 전체는 선형이 아니라 샘플 위치에 대해 이차이다.

쌍선형 보간은 컴퓨터 비전 및 영상 처리에서 기본 리샘플링 기술 중 하나이며, 쌍선형 필터링 또는 쌍선형 텍스처 매핑이라고도 불린다.

계산

네 개의 빨간 점은 데이터 포인트를, 녹색 점은 보간하려는 점을 나타낸다.

점 (x, y)에서 미지의 함수 f의 값을 찾고자 한다고 가정해보자. f의 값은 네 점 Q₁₁ = (x₁, y₁), Q₁₂ = (x₁, y₂), Q₂₁ = (x₂, y₁), Q₂₂ = (x₂, y₂)에서 알려져 있다고 가정한다.

반복 선형 보간

먼저 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 방향으로 수행되더라도 동일한 결과를 얻는다는 점에 유의한다.

다항식 적합

다른 방법은 보간 문제의 해를 다중선형 다항식으로 작성하는 것이다.

$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가 알려진 네 점이 (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}}$

두 경우 모두 상수의 개수(네 개)는 f가 주어지는 데이터 점의 개수에 해당한다.

속성

이름에서 알 수 있듯이 쌍선형 보간기는 선형이 아니지만, x 또는 y 방향과 평행한 선을 따라서는 선형(즉, 아핀)이다. 다시 말해 x 또는 y가 상수일 때 선형이다. 다른 어떤 직선을 따라서는 보간기가 이차적이다. 보간이 위치(x와 y)에 대해 선형이 아니더라도, 고정된 점에서는 보간 값에 대해 선형인데, 위 (행렬) 방정식에서 볼 수 있다.

쌍선형 보간의 결과는 어떤 축이 먼저 보간되고 어떤 축이 나중에 보간되는지에 관계없이 동일하다. 만약 먼저 y 방향으로 선형 보간을 수행한 다음 x 방향으로 수행했다면, 결과적인 근사치는 동일했을 것이다.

보간기는 쌍선형 다항식이며, 라플라스 방정식을 만족하는 조화 함수이기도 하다. 그래프는 쌍선형 베지에 곡면 패치이다.

역함수 및 일반화

일반적으로 보간 함수는 무한히 많은 점( 쌍곡선의 가지를 형성하는)에서(정점 값의 볼록 폐포 내에서) 임의의 값을 취하므로, 보간은 역함수가 존재하지 않는다.

그러나 쌍선형 보간이 두 함수에 동시에 적용되는 경우(예: 벡터장 보간 시), 보간은 (특정 조건 하에서) 역함수가 존재한다. 특히, 이 역함수는 임의의 볼록 사각형 내부의 점의 "단위 정사각형 좌표"를 찾는 데 사용될 수 있다(사각형의 좌표를 단위 정사각형에서 쌍선형으로 보간된 벡터장으로 간주하여). 이 절차를 사용하면 쌍선형 보간을 임의의 볼록 사각형으로 확장할 수 있지만, 평행사변형이 아닌 경우 계산이 훨씬 더 복잡하다. 사각형 간의 결과적인 맵은 쌍선형 변환, 쌍선형 왜곡 또는 쌍선형 뒤틀림으로 알려져 있다.

대안적으로, 사각형과 단위 사각형 사이의 사영 매핑이 사용될 수 있지만, 결과적인 보간은 쌍선형이 아니다.

사각형이 평행사변형인 특수한 경우, 단위 정사각형으로의 선형 매핑이 존재하며 일반화는 쉽게 이어진다.

쌍선형 보간을 3차원으로 명확하게 확장한 것을 삼선형 보간법이라고 한다.

역 계산

${\textstyle \mu ,\lambda \in [0,1]}$에 의해 매개변수화된 단위 사각형에 대해 쌍선형 보간된 벡터장을 ${\textstyle F}$라고 하자. 보간을 역으로 하려면 두 개의 쌍선형 다항식 방정식 시스템을 풀어야 한다. $$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}}$$ 신중하게 선택된 벡터와 시스템의 2차원 외적( 그라스만 곱 참조)을 취하면 항을 제거할 수 있다. $${\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$인 경우는 별도로 처리해야 한다. 올바른 조건이 주어지면 두 해 중 하나는 단위 사각형 내에 있어야 한다.

영상 처리에서의 응용

컴퓨터 비전 및 영상 처리에서 쌍선형 보간법은 이미지와 텍스처를 리샘플링하는 데 사용된다. 화면 픽셀 위치를 텍스처 맵의 해당 점에 매핑하는 알고리즘이 사용된다. 주변 네 텍셀의 속성(색상, 투명도 등)의 가중 평균을 계산하여 화면 픽셀에 적용한다. 이 과정은 텍스처링되는 객체를 구성하는 각 픽셀에 대해 반복된다.

이미지를 확대해야 할 때, 원본 이미지의 각 픽셀은 스케일 상수에 따라 특정 방향으로 이동해야 한다. 그러나 이미지를 정수적이지 않은 스케일 인수로 확대할 때, 적절한 픽셀 값이 할당되지 않은 픽셀(즉, 구멍)이 있다. 이 경우, 출력 이미지에 값 없는 픽셀이 없도록 해당 구멍에 적절한 RGB 또는 회색조 값을 할당해야 한다.

쌍선형 보간법은 픽셀 매칭을 통한 완벽한 이미지 변환이 불가능할 때 사용될 수 있으며, 이를 통해 픽셀에 적절한 강도 값을 계산하고 할당할 수 있다. 최근접 이웃 보간법 및 바이큐빅 보간법과 같은 다른 보간 기술과 달리, 쌍선형 보간법은 주어진 픽셀의 적절한 색상 강도 값을 찾기 위해 해당 픽셀의 대각선 방향에 있는 가장 가까운 2 × 2 픽셀 값만을 사용한다.

쌍선형 보간법은 알 수 없는 픽셀의 계산된 위치를 둘러싸는 알려진 픽셀 값의 가장 가까운 2 × 2 이웃을 고려한다. 그런 다음 이 4개 픽셀의 가중 평균을 취하여 최종 보간 값을 얻는다.

회색조 값의 쌍선형 보간 예시

예시

오른쪽 예시에서 볼 수 있듯이, 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}}$

위 식에는 $(P_{2}-P_{1})$, $(P_{x}-P_{1})$, $(P_{x}-P_{1})$, $(T_{2}-T_{1})$와 같은 여러 반복되는 연산과 일부 비율이 있다. 이러한 반복은 단일 보간을 계산하는 동안 임시 변수에 할당될 수 있으며, 이는 연산 횟수를 19로 줄일 수 있다.

이 모든 것은 초기 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})}}.$

용어의 단순화는 수학적 방법론을 공학 응용 분야에 적용하는 좋은 방법이며, 공정의 계산 및 에너지 요구 사항을 줄일 수 있다.

같이 보기

• 쌍입방 보간법
• 삼선형 보간법
• 스플라인 보간법
• 랑초스 리샘플링
• 계단식 보간법
• 무게 중심 좌표 - 삼각형 또는 사면체 내 보간용