쌍선형 보간법

z 값이 0, 1, 1, 0.5인 단위 정사각형에 대한 쌍선형 보간의 예시. 보간된 값은 색상으로 표시된다. 수학에서 **쌍선형 보간법**(Bilinear interpolation)은 반복된 선형 보간법을 사용하여 두 변수(예: x와 y)의 함수를 보간하는 방법이다. 일반적으로 2D 직교 격자에서 샘플링된 함수에 적용되지만, 임의의 볼록 사각형의 정점(또는 폴리곤 메시의)에 정의된 함수로 일반화될 수 있다. 쌍선형 보간은 한 방향으로 선형 보간을 먼저 수행한 다음 다른 방향으로 다시 수행하여 이루어진다. 각 단계는 샘플링된 값과 위치에 대해 선형이지만, 보간 전체는 선형이 아니라 샘플 위치에 대해 이차이다. 쌍선형 보간은 컴퓨터 비전 및 영상 처리에서 기본 리샘플링 기술 중 하나이며, **쌍선형 필터링** 또는 **쌍선형 텍스처 매핑**이라고도 불린다.
# 계산
네 개의 빨간 점은 데이터 포인트를, 녹색 점은 보간하려는 점을 나타낸다. 점 (x, y)에서 미지의 함수 f의 값을 찾고자 한다고 가정해보자. f의 값은 네 점 Q11 = (x1, y1), Q12 = (x1, y2), Q21 = (x2, y1), Q22 = (x2, y2)에서 알려져 있다고 가정한다.
## 반복 선형 보간
먼저 x 방향으로 선형 보간을 수행한다. 이로부터 다음을 얻는다: :\begin{align} 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{align} 다음으로 y 방향으로 보간하여 원하는 추정치를 얻는다: :\begin{align} 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}[b] = \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{align} 보간이 y 방향으로 먼저 수행된 다음 x 방향으로 수행되더라도 동일한 결과를 얻는다는 점에 유의한다.url=https://archive.org/details/numericalrecipes0865unse/page/123
## 다항식 적합
다른 방법은 보간 문제의 해를 다중선형 다항식으로 작성하는 것이다. :f(x, y) \approx a_{00} + a_{10}x + a_{01}y + a_{11}xy, 계수는 선형 시스템을 풀어 찾는다. :\begin{align} \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{align} 결과를 산출한다. :\begin{align} \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_2y_2 & -x_2y_1 & -x_1y_2 & x_1y_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{align}
## 가중 평균
쌍선형 보간의 기하학적 시각화. 원하는 점(검정)의 값과 전체 면적의 곱은 각 모서리의 값과 모서리 대각선 반대편 부분 면적(해당 색상)의 곱의 합과 같다. 해는 또한 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_1y_1 & x_1y_2 & x_2y_1 & x_2y_2 \end{bmatrix} \begin{bmatrix} w_{11} \\\ w_{12} \\\ w_{21} \\\ w_{22} \end{bmatrix} = \begin{bmatrix} 1 \\\ x \\\ y \\\ xy \end{bmatrix}, 결과를 산출한다. :\begin{align} \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_2y_2 & -y_2 & -x_2 & 1 \\\ -x_2y_1 & y_1 & x_2 & -1 \\\ -x_1y_2 & y_2 & x_1 & -1 \\\ x_1y_1 & -y_1 & -x_1 & 1 \end{bmatrix}\begin{bmatrix} 1\\\x\\\y\\\xy \end{bmatrix}, \end{align} 이는 다음과 같이 단순화된다. :\begin{align} 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{align} 반복 선형 보간으로 얻은 결과와 일치한다. 가중치 집합은 사각형에 대한 일반화된 무게 중심 좌표 집합으로도 해석될 수 있다.
## 다른 행렬 형식
위 내용을 종합하면 다음과 같다. :\begin{align} 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_2y_2 & -y_2 & -x_2 & 1 \\\ -x_2y_1 & y_1 & x_2 & -1 \\\ -x_1y_2 & y_2 & x_1 & -1 \\\ x_1y_1 & -y_1 & -x_1 & 1 \end{bmatrix}\begin{bmatrix} 1\\\x\\\y\\\xy \end{bmatrix}. \end{align}
## 단위 정사각형에서
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{align} w_{11} &= (1 - x)(1 - y), \\\ w_{12} &= (1 - x)y, \\\ w_{21} &= x(1 - y), \\\ w_{22} &= xy. \end{align} 또는 단위 정사각형의 보간 함수는 다음과 같이 쓸 수 있다. :f(x, y) = a_{00} + a_{10}x + a_{01}y + a_{11}xy, 여기서 :\begin{align} 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{align} 두 경우 모두 상수의 개수(네 개)는 f가 주어지는 데이터 점의 개수에 해당한다.
# 속성
이름에서 알 수 있듯이 쌍선형 보간기는 선형이 아니지만, x 또는 y 방향과 평행한 선을 따라서는 선형(즉, 아핀)이다. 다시 말해 x 또는 y가 상수일 때 선형이다. 다른 어떤 직선을 따라서는 보간기가 이차적이다. 보간이 위치(x와 y)에 대해 선형이 아니더라도, 고정된 점에서는 보간 값에 대해 선형인데, 위 (행렬) 방정식에서 볼 수 있다. 쌍선형 보간의 결과는 어떤 축이 먼저 보간되고 어떤 축이 나중에 보간되는지에 관계없이 동일하다. 만약 먼저 y 방향으로 선형 보간을 수행한 다음 x 방향으로 수행했다면, 결과적인 근사치는 동일했을 것이다. 보간기는 쌍선형 다항식이며, 라플라스 방정식을 만족하는 조화 함수이기도 하다. 그래프는 쌍선형 베지에 곡면 패치이다.
# 역함수 및 일반화
일반적으로 보간 함수는 무한히 많은 점( 쌍곡선의 가지를 형성하는doi-access=free)에서(정점 값의 볼록 폐포 내에서) 임의의 값을 취하므로, 보간은 역함수가 존재하지 않는다. 그러나 쌍선형 보간이 두 함수에 동시에 적용되는 경우(예: 벡터장 보간 시), 보간은 (특정 조건 하에서) 역함수가 존재한다. 특히, 이 역함수는 임의의 볼록 사각형 내부의 점의 "단위 정사각형 좌표"를 찾는 데 사용될 수 있다(사각형의 좌표를 단위 정사각형에서 쌍선형으로 보간된 벡터장으로 간주하여). 이 절차를 사용하면 쌍선형 보간을 임의의 볼록 사각형으로 확장할 수 있지만, 평행사변형이 아닌 경우 계산이 훨씬 더 복잡하다.archive-date=2010-08-13 사각형 간의 결과적인 맵은 쌍선형 변환, 쌍선형 왜곡 또는 쌍선형 뒤틀림으로 알려져 있다. 대안적으로, 사각형과 단위 사각형 사이의 사영 매핑이 사용될 수 있지만, 결과적인 보간은 쌍선형이 아니다. 사각형이 평행사변형인 특수한 경우, 단위 정사각형으로의 선형 매핑이 존재하며 일반화는 쉽게 이어진다. 쌍선형 보간을 3차원으로 명확하게 확장한 것을 삼선형 보간법이라고 한다. 역 계산 \mu, \lambda \in [0,1]에 의해 매개변수화된 단위 사각형에 대해 쌍선형 보간된 벡터장을 F라고 하자. 보간을 역으로 하려면 두 개의 쌍선형 다항식 방정식 시스템을 풀어야 한다. A + B\lambda + C\mu + D\lambda\mu = 0 여기서 \begin{align} A &= F_{00} - F \\\ B &= F_{10} - F_{00} \\\ C &= F_{01} - F_{00} \\\ D &= F_{11} - F_{01} - F_{10} + F_{00} \end{align} 신중하게 선택된 벡터와 시스템의 2차원 외적( 그라스만 곱 참조)을 취하면 항을 제거할 수 있다. \begin{align} (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{align} 이는 다음과 같이 확장된다. \begin{align} c + e\lambda + f\mu &= 0 \\\ b + (c + d)\lambda + e\lambda^2&= 0 \\\ a + (c - d)\mu + f\mu^2&= 0 \\\ \end{align} 여기서 \begin{align} 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{align} 이차 방정식은 이차 공식을 사용하여 풀 수 있다. 우리는 다음 동등한 판별식을 가진다. \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인 경우는 별도로 처리해야 한다. 올바른 조건이 주어지면 두 해 중 하나는 단위 사각형 내에 있어야 한다. 글 숨김 끝
# 영상 처리에서의 응용
컴퓨터 비전 및 영상 처리에서 쌍선형 보간법은 이미지와 텍스처를 리샘플링하는 데 사용된다. 화면 픽셀 위치를 텍스처 맵의 해당 점에 매핑하는 알고리즘이 사용된다. 주변 네 텍셀의 속성(색상, 투명도 등)의 가중 평균을 계산하여 화면 픽셀에 적용한다. 이 과정은 텍스처링되는 객체를 구성하는 각 픽셀에 대해 반복된다.쌍선형 보간 정의 (www.pcmag.com의 인기 기사). 이미지를 확대해야 할 때, 원본 이미지의 각 픽셀은 스케일 상수에 따라 특정 방향으로 이동해야 한다. 그러나 이미지를 정수적이지 않은 스케일 인수로 확대할 때, 적절한 픽셀 값이 할당되지 않은 픽셀(즉, 구멍)이 있다. 이 경우, 출력 이미지에 값 없는 픽셀이 없도록 해당 구멍에 적절한 RGB 또는 회색조 값을 할당해야 한다. 쌍선형 보간법은 픽셀 매칭을 통한 완벽한 이미지 변환이 불가능할 때 사용될 수 있으며, 이를 통해 픽셀에 적절한 강도 값을 계산하고 할당할 수 있다. 최근접 이웃 보간법 및 바이큐빅 보간법과 같은 다른 보간 기술과 달리, 쌍선형 보간법은 주어진 픽셀의 적절한 색상 강도 값을 찾기 위해 해당 픽셀의 대각선 방향에 있는 가장 가까운 2 × 2 픽셀 값만을 사용한다. 쌍선형 보간법은 알 수 없는 픽셀의 계산된 위치를 둘러싸는 알려진 픽셀 값의 가장 가까운 2 × 2 이웃을 고려한다. 그런 다음 이 4개 픽셀의 가중 평균을 취하여 최종 보간 값을 얻는다.url-access=subscription"웹 튜토리얼: 디지털 이미지 보간". 회색조 값의 쌍선형 보간 예시
## 예시
오른쪽 예시에서 볼 수 있듯이, 20.2행, 14.5열에 계산된 픽셀의 강도 값은 먼저 각 20행과 21행에서 14열과 15열 사이의 값을 선형 보간하여 계산할 수 있으며, 이는 다음과 같다. :\begin{align} 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{align} 그리고 이 값들을 선형으로 보간하면 다음과 같다. :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{align} 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{align} 위 식에는 (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)}. 용어의 단순화는 수학적 방법론을 공학 응용 분야에 적용하는 좋은 방법이며, 공정의 계산 및 에너지 요구 사항을 줄일 수 있다.