쌍입방 보간법

수학에서 **쌍입방 보간법**(Bicubic interpolation)은 입방 스플라인 보간 (데이터 세트에 입방 보간을 적용하는 방법)을 2차원 정규 격자의 데이터 포인트를 보간하기 위해 확장한 것이다. 보간된 표면(이미지가 아닌 커널 모양을 의미함)은 해당 쌍선형 보간법 또는 최근접 이웃 보간법으로 얻은 표면보다 더 매끄럽다. 쌍입방 보간법은 라그랑주 다항식, 입방 스플라인 또는 입방 합성곱 알고리즘을 사용하여 수행할 수 있다.

영상 처리에서 쌍입방 보간법은 속도가 문제가 되지 않을 때 이미지 리샘플링에서 쌍선형 또는 최근접 이웃 보간법보다 자주 선택된다. 4개의 화소 (2×2)만 고려하는 쌍선형 보간법과 달리 쌍입방 보간법은 16개의 화소 (4×4)를 고려한다. 쌍입방 보간법으로 리샘플링된 이미지는 선택된 b 및 c 값에 따라 다른 보간 아티팩트를 가질 수 있다.

## 계산

[섬네일|right|25개의 단위 정사각형으로 패치된 <math>[0,4] \times [0,4]</math> 정사각형에 대한 쌍입방 보간법. [Matplotlib의 구현에 따른 쌍입방 보간법. 색상은 함수 값을 나타낸다. 검은 점은 보간되는 지정된 데이터의 위치이다. 색상 샘플이 방사상으로 대칭이 아님에 유의하라.]]
[섬네일|right|위와 동일한 데이터 세트에 대한 [쌍선형 보간법. 표면의 도함수는 정사각형 경계에서 연속적이지 않다.]]
[섬네일|right|위와 동일한 데이터 세트에 대한 [최근접 이웃 보간법.]]

단위 정사각형의 네 모서리 (0,0), (1,0), (0,1), (1,1)에서 함수 값 f와 도함수 f_x, f_y, f_{xy}가 알려져 있다고 가정하자. 그러면 보간된 표면은 다음과 같이 쓸 수 있다.
p(x,y) = \sum\limits_{i=0}^3 \sum_{j=0}^3 a_{ij} x^i y^j.

보간 문제는 16개의 계수 a_{ij}를 결정하는 것으로 구성된다.
p(x,y)를 함수 값과 일치시키면 네 가지 방정식이 생성된다.
# f(0,0)      = p(0,0)   = a_{00},
# f(1,0)      = p(1,0)   = a_{00} + a_{10} + a_{20} + a_{30},
# f(0,1)      = p(0,1)   = a_{00} + a_{01} + a_{02} + a_{03},
# f(1,1)      = p(1,1)   = \textstyle \sum\limits_{i=0}^3 \sum\limits_{j=0}^3 a_{ij}.

마찬가지로 x 및 y 방향의 도함수에 대한 여덟 가지 방정식:
# f_x(0,0)    = p_x(0,0) = a_{10},
# f_x(1,0)    = p_x(1,0) =  a_{10} + 2a_{20} + 3a_{30},
# f_x(0,1)    = p_x(0,1) = a_{10} + a_{11} + a_{12} + a_{13},
# f_x(1,1)    = p_x(1,1) = \textstyle \sum\limits_{i=1}^3 \sum\limits_{j=0}^3 a_{ij} i,
# f_y(0,0)    = p_y(0,0) = a_{01},
# f_y(1,0)    = p_y(1,0) = a_{01} + a_{11} + a_{21} + a_{31},
# f_y(0,1)    = p_y(0,1) = a_{01} + 2a_{02} + 3a_{03},
# f_y(1,1)    = p_y(1,1) = \textstyle \sum\limits_{i=0}^3 \sum\limits_{j=1}^3 a_{ij} j.

그리고 xy 혼합 편미분에 대한 네 가지 방정식:
# f_{xy}(0,0) = p_{xy}(0,0) = a_{11},
# f_{xy}(1,0) = p_{xy}(1,0) = a_{11} + 2a_{21} + 3a_{31},
# f_{xy}(0,1) = p_{xy}(0,1) = a_{11} + 2a_{12} + 3a_{13},
# f_{xy}(1,1) = p_{xy}(1,1) = \textstyle \sum\limits_{i=1}^3 \sum\limits_{j=1}^3 a_{ij} i j.

위의 표현식은 다음 항등식을 사용했다.
p_x(x,y) = \textstyle \sum\limits_{i=1}^3 \sum\limits_{j=0}^3 a_{ij} i x^{i-1} y^j,
p_y(x,y) = \textstyle \sum\limits_{i=0}^3 \sum\limits_{j=1}^3 a_{ij} x^i j y^{j-1},
p_{xy}(x,y) = \textstyle \sum\limits_{i=1}^3 \sum\limits_{j=1}^3 a_{ij} i x^{i-1} j y^{j-1}.

이 절차는 단위정사각형 [0,1] \times [0,1]에서 연속적이며 연속적인 도함수를 갖는 표면 p(x,y)를 생성한다. 임의의 크기의 정규 격자에 대한 쌍입방 보간법은 이러한 쌍입방 표면을 패치하여 경계에서 도함수가 일치하도록 보장함으로써 수행할 수 있다.

알려지지 않은 매개변수 a_{ij}를 벡터로 그룹화하면
\alpha=\left[\begin{smallmatrix}a_{00}&a_{10}&a_{20}&a_{30}&a_{01}&a_{11}&a_{21}&a_{31}&a_{02}&a_{12}&a_{22}&a_{32}&a_{03}&a_{13}&a_{23}&a_{33}\end{smallmatrix}\right]^T
다음과 같이 된다.
x=\left[\begin{smallmatrix}f(0,0)&f(1,0)&f(0,1)&f(1,1)&f_x(0,0)&f_x(1,0)&f_x(0,1)&f_x(1,1)&f_y(0,0)&f_y(1,0)&f_y(0,1)&f_y(1,1)&f_{xy}(0,0)&f_{xy}(1,0)&f_{xy}(0,1)&f_{xy}(1,1)\end{smallmatrix}\right]^T,
위의 방정식 시스템은 선형 방정식 A\alpha=x에 대한 행렬로 재구성될 수 있다.

행렬을 반전시키면 더 유용한 선형 방정식 A^{-1}x=\alpha가 되는데, 여기서
A^{-1}=\left[\begin{smallmatrix}\begin{array}{rrrrrrrrrrrrrrrr}
 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 -3 & 3 & 0 & 0 & -2 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 2 & -2 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -3 & 3 & 0 & 0 & -2 & -1 & 0 & 0 \\
 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & -2 & 0 & 0 & 1 & 1 & 0 & 0 \\
 -3 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & -2 & 0 & -1 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 & -3 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & -2 & 0 & -1 & 0 \\
 9 & -9 & -9 & 9 & 6 & 3 & -6 & -3 & 6 & -6 & 3 & -3 & 4 & 2 & 2 & 1 \\
 -6 & 6 & 6 & -6 & -3 & -3 & 3 & 3 & -4 & 4 & -2 & 2 & -2 & -2 & -1 & -1 \\
 2 & 0 & -2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
 0 & 0 & 0 & 0 & 2 & 0 & -2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
 -6 & 6 & 6 & -6 & -4 & -2 & 4 & 2 & -3 & 3 & -3 & 3 & -2 & -1 & -2 & -1 \\
 4 & -4 & -4 & 4 & 2 & 2 & -2 & -2 & 2 & -2 & 2 & -2 & 1 & 1 & 1 & 1
\end{array}\end{smallmatrix}\right],
이를 통해 \alpha를 빠르고 쉽게 계산할 수 있다.

16개의 계수에 대한 또 다른 간결한 행렬 형식은 다음과 같다.
\begin{bmatrix}
f(0,0)&f(0,1)&f_y (0,0)&f_y (0,1)\\f(1,0)&f(1,1)&f_y (1,0)&f_y (1,1)\\f_x (0,0)&f_x (0,1)&f_{xy} (0,0)&f_{xy} (0,1)\\f_x (1,0)&f_x (1,1)&f_{xy} (1,0)&f_{xy} (1,1)
\end{bmatrix} =
\begin{bmatrix}
1&0&0&0\\1&1&1&1\\0&1&0&0\\0&1&2&3
\end{bmatrix}
\begin{bmatrix}
a_{00}&a_{01}&a_{02}&a_{03}\\a_{10}&a_{11}&a_{12}&a_{13}\\a_{20}&a_{21}&a_{22}&a_{23}\\a_{30}&a_{31}&a_{32}&a_{33}
\end{bmatrix}
\begin{bmatrix}
1&1&0&0\\0&1&1&1\\0&1&0&2\\0&1&0&3
\end{bmatrix},
또는

\begin{bmatrix}
a_{00}&a_{01}&a_{02}&a_{03}\\a_{10}&a_{11}&a_{12}&a_{13}\\a_{20}&a_{21}&a_{22}&a_{23}\\a_{30}&a_{31}&a_{32}&a_{33}
\end{bmatrix}
=
\begin{bmatrix}
1&0&0&0\\0&0&1&0\\-3&3&-2&-1\\2&-2&1&1
\end{bmatrix}
\begin{bmatrix}
f(0,0)&f(0,1)&f_y (0,0)&f_y (0,1)\\f(1,0)&f(1,1)&f_y (1,0)&f_y (1,1)\\f_x (0,0)&f_x (0,1)&f_{xy} (0,0)&f_{xy} (0,1)\\f_x (1,0)&f_x (1,1)&f_{xy} (1,0)&f_{xy} (1,1)
\end{bmatrix}
\begin{bmatrix}
1&0&-3&2\\0&0&3&-2\\0&1&-2&1\\0&0&-1&1
\end{bmatrix},

여기서
p(x,y)=\begin{bmatrix}1
&x&x^2&x^3\end{bmatrix}
\begin{bmatrix}
a_{00}&a_{01}&a_{02}&a_{03}\\a_{10}&a_{11}&a_{12}&a_{13}\\a_{20}&a_{21}&a_{22}&a_{23}\\a_{30}&a_{31}&a_{32}&a_{33}
\end{bmatrix}
\begin{bmatrix}1\\y\\y^2\\y^3\end{bmatrix}.

## 직교 격자로의 확장

종종 응용 프로그램은 단위 정사각형이 아닌 직교 격자의 데이터를 사용하여 쌍입방 보간법을 호출한다. 이 경우 p_x, p_y, 및 p_{xy}에 대한 항등식은 다음과 같다.
p_x(x,y) = \textstyle \sum\limits_{i=1}^3 \sum\limits_{j=0}^3 \frac{a_{ij} i x^{i-1} y^j}{\Delta x},
p_y(x,y) = \textstyle \sum\limits_{i=0}^3 \sum\limits_{j=1}^3 \frac{a_{ij} x^i j y^{j-1}}{\Delta y},
p_{xy}(x,y) = \textstyle \sum\limits_{i=1}^3 \sum\limits_{j=1}^3 \frac{a_{ij} i x^{i-1} j y^{j-1}}{\Delta x \Delta y},
여기서 \Delta x는 점 (x,y)를 포함하는 셀의 x 간격이며 \Delta y도 비슷하다.
이 경우 계수 \alpha를 계산하는 가장 실용적인 방법은 다음과 같이 하는 것이다.
x=\left[\begin{smallmatrix}f(0,0)&f(1,0)&f(0,1)&f(1,1)&\Delta x f_x(0,0)&\Delta xf_x(1,0)&\Delta x f_x(0,1)&\Delta x f_x(1,1)&\Delta y f_y(0,0)&\Delta y f_y(1,0)&\Delta y f_y(0,1)&\Delta y f_y(1,1)&\Delta x \Delta y f_{xy}(0,0)&\Delta x \Delta y f_{xy}(1,0)&\Delta x \Delta y f_{xy}(0,1)&\Delta x \Delta y f_{xy}(1,1)\end{smallmatrix}\right]^T,
그런 다음 이전과 같이 A를 사용하여 \alpha=A^{-1}x를 해결한다. 다음으로 정규화된 보간 변수는 다음과 같이 계산된다.
\begin{align}
\overline{x} &= \frac{x-x_0}{x_1-x_0}, \\
\overline{y} &= \frac{y-y_0}{y_1-y_0}
\end{align}
여기서 x_0, x_1, y_0, 및 y_1은 점 (x,y)를 둘러싸는 격자점의 x 및 y 좌표이다. 그러면 보간 표면은 다음과 같이 된다.
p(x,y) = \sum\limits_{i=0}^3 \sum_{j=0}^3 a_{ij} {\overline{x}}^i {\overline{y}}^j.

## 함수 값에서 도함수 찾기

도함수가 알려지지 않은 경우, 일반적으로 유한 차분을 사용하여 단위 정사각형 모서리 주변의 점들에서 함수 값으로부터 근사화된다.

이 방법을 사용하여 단일 도함수 f_x 또는 f_y 중 하나를 찾으려면 적절한 축에서 주변 두 점 사이의 기울기를 찾는다. 예를 들어, 한 점에 대한 f_x를 계산하려면 대상 점의 왼쪽과 오른쪽에 있는 점들에 대한 f(x,y)를 찾아 기울기를 계산하고, f_y도 마찬가지이다.

교차 도함수 f_{xy}를 찾으려면 한 번에 한 축씩 두 축 모두에서 도함수를 취한다. 예를 들어, 먼저 f_x 절차를 사용하여 대상 점 위와 아래의 점들의 x 도함수를 찾은 다음, 이 값들(평소처럼 해당 점들의 f 값이 아님)에 f_y 절차를 사용하여 대상 점에 대한 f_{xy}(x,y) 값을 얻을 수 있다. (또는 반대 방향으로, 먼저 f_y를 계산한 다음 그 값들로부터 f_x를 계산할 수도 있다. 두 가지 방법은 동일한 결과를 제공한다.)

데이터 세트의 가장자리에서 주변 점들 중 일부가 누락된 경우, 누락된 점들은 여러 가지 방법으로 근사화될 수 있다. 간단하고 일반적인 방법은 기존 점에서 대상 점까지의 기울기가 더 이상 변하지 않고 계속된다고 가정하고, 이를 사용하여 누락된 점의 가상 값을 계산하는 것이다.

## 쌍입방 합성곱 알고리즘

쌍입방 스플라인 보간법은 각 그리드 셀에 대해 위에 설명된 선형 시스템의 해를 요구한다. 다음과 같은 커널을 두 차원에서 합성곱에 적용하여 유사한 속성을 가진 보간기를 얻을 수 있다.
W(x) =
\begin{cases}
 (a+2)|x|^3-(a+3)|x|^2+1 & \text{for } |x| \leq 1, \\
 a|x|^3-5a|x|^2+8a|x|-4a & \text{for } 1 
여기서 a는 일반적으로 -0.5 또는 -0.75로 설정된다. W(0)=1이고 모든 0이 아닌 정수 n에 대해 W(n)=0이라는 점에 유의하라.

이 접근법은 Keys에 의해 제안되었으며, a=-0.5가 원래 함수의 샘플링 간격에 대해 3차 수렴을 생성함을 보여주었다.

일반적인 경우 a = -0.5에 대한 행렬 표기법을 사용하면 방정식을 더 친숙한 방식으로 표현할 수 있다.
p(t) =
\tfrac{1}{2}
\begin{bmatrix}
1 & t & t^2 & t^3
\end{bmatrix}

\begin{bmatrix}
0 & 2 & 0 & 0 \\
-1 & 0 & 1 & 0 \\
2 & -5 & 4 & -1 \\
-1 & 3 & -3 & 1
\end{bmatrix}

\begin{bmatrix}
f_{-1} \\
f_0 \\
f_1 \\
f_2
\end{bmatrix}

1차원의 경우 t는 0에서 1 사이이다. 1차원 입방 합성곱 보간에는 4개의 샘플 포인트가 필요하다. 각 조회에 대해 왼쪽에는 두 개의 샘플, 오른쪽에는 두 개의 샘플이 있다. 이 텍스트에서는 이 점들을 -1에서 2까지로 색인한다. 0으로 색인된 점과 조회 점 사이의 거리는 여기에서 t로 표시된다.

두 차원의 경우 먼저 x에 한 번, 다시 y에 한 번 적용한다.
\begin{align}
b_{-1}&= p(t_x, f_{(-1,-1)}, f_{(0,-1)}, f_{(1,-1)}, f_{(2,-1)}), \\[1ex]
b_{0} &= p(t_x, f_{(-1,0)}, f_{(0,0)}, f_{(1,0)}, f_{(2,0)}), \\[1ex]
b_{1} &= p(t_x, f_{(-1,1)}, f_{(0,1)}, f_{(1,1)}, f_{(2,1)}), \\[1ex]
b_{2} &= p(t_x, f_{(-1,2)}, f_{(0,2)}, f_{(1,2)}, f_{(2,2)}),
\end{align}
p(x,y) = p(t_y, b_{-1}, b_{0}, b_{1}, b_{2}).

## 컴퓨터 그래픽에서의 사용

[250px|섬네일|이 그림의 아래쪽 절반은 위쪽 절반을 확대한 것으로, 왼쪽 선의 명백한 선명도가 어떻게 생성되는지 보여준다. 쌍입방 보간법은 [오버슈트 (신호)|오버슈트를 유발하여 선명도를 증가시킨다.]]

쌍입방 알고리즘은 디스플레이를 위해 이미지와 비디오를 스케일링하는 데 자주 사용된다(비트맵 리샘플링 참조). 이는 일반적인 쌍선형 필터링 알고리즘보다 미세한 디테일을 더 잘 보존한다.

그러나 커널의 음의 엽(lobe) 때문에 오버슈트(할로잉)를 유발한다. 이는 클리핑을 유발할 수 있으며 아티팩트(링잉 아티팩트 참조)이지만, 선명도(명백한 선명도)를 증가시켜 바람직할 수 있다.

## 같이 보기

* 공간 안티에일리어싱
* 베지에 곡면
* 쌍선형 보간법
* 입방 에르미트 스플라인, 쌍입방 스플라인의 1차원 아날로그
* 랑초시 리샘플링
* 자연 이웃 보간법
* 싱크 필터
* 스플라인 보간법
* 삼입방 보간법
* 방향 입방 합성곱 보간

## 각주

## 외부 링크
* 고도 샘플에 대한 보간 적용
* 보간 이론
* (쌍)입방 보간의 설명 및 Java/C++ 구현
* 쌍입방 라그랑주 보간을 위한 엑셀 워크시트 함수

분류:영상 처리