선형 보간법(linear, bilinear, trilinear interpolation)

이 글은 1D 선형보간법(linear interpolation)을 2D로 확장한 bilinear interpolation과 3D로 확장한 trilinear interpolation이 어떤 식으로 이루어지는지와 이러한 interpolation 기법이 히스토그램(histogram)을 생성할 때 어떻게 적용되는지에 대한 글입니다.

그리고 보통 interpolation하면 직사각형이나 직육면체 내에서의 보간을 생각하기 쉬운데, 알려진 데이터 점들이 직사각형, 직육면체가 아닌 임의의 사각형 또는 임의의 육면체를 이룰 때 보간 방법에 대해서도 소개합니다.

1. Interpolation과 Extrapolation

Interpolation(인터폴레이션, 보간)이란 알려진 지점의 값 사이(중간)에 위치한 값을 알려진 값으로부터 추정하는 것을 말한다.

Interpolation과 대비되는 용어로 extrapolation이 있는데, extrapolation은 알려진 값들 사이의 값이 아닌 범위를 벗어난 외부의 위치에서의 값을 추정하는 것을 말한다.

예를 들어, 어떤 사람이 20살일때 키와 40살에서의 키를 보고 30살에서의 키를 추측하는 것은 interpolation이고 과거 1살때부터 현재 나이까지의 키를 보고 앞으로 10년 후의 키를 예측하는 것은 extrapolation이다. 또한 최근 한달간의 주가 동향을 보고 내일의 주가를 예측하는 것도 extrapolation이며 extrapolation은 interpolation에 비해 훨씬 안정성이 떨어지는 (위험한) 예측 방법이다.

아래 그림에서 x1, x2에서 데이터 값을 알고 있을 때 x1<=xi<=x2에서 값을 추정하는 것은 interpolation이고 범위 밖인 xj에서 값을 추정하는 것은 extrapolation:

<그림 1>

2. 1D Linear Interpolation

두 지점을 보간하는 방법은 polynomial 보간, spline 보간 등 여러 가지가 있으나 그 중 선형 보간법(linear interpolation)은 두 지점 사이의 값을 추정할 때 그 값을 두 지점과의 직선 거리에 따라 선형적으로 결정하는 방법이다.

두 지점 x1, x2에서의 데이터 값이 각각 f(x1), f(x2)일 때, x1, x2 사이의 임의의 지점 x (x1≤x≤x2)에서의 데이터 값 f(x)는 선형보간법을 사용할 경우 다음과 같이 계산된다.

--- (1)

단, d1은 x에서 x1까지의 거리, d2는 x에서 x2까지의 거리.

<그림 2>

☞ 원래는 f(x) = f(x1) + d1/(d1+d2)*(f(x2)-f(x1)) 인데, 이를 정리하면 식 (1)이 나온다.

만일 거리의 비를 합이 1이 되도록 정규화하면 즉, α = d1/(d1+d2), β = d2/(d1+d2)라 잡으면 식 (1)은 다음과 같이 좀더 단순화될 수 있다 (α + β = 1).

 --- (2)

3. Bilinear Interpolation

Bilinear interpolation은 우리 말로 적자면 쌍선형 보간법, 또는 이중선형 보간법 정도가 되며 1차원에서의 선형 보간법을 2차원으로 확장한 것이다.

Bilinear interpolation 방법을 설명하기 위해 아래 그림과 같이 직사각형의 네 꼭지점에서의 값이 주어져 있을 때, 이 사각형의 변 및 내부의 임의의 점에서의 값을 추정하는 문제를 생각해 보자.

<그림 3>

그림과 같이 점 P에서 x축 방향으로 사각형의 변까지의 거리를 w1, w2, y축 방향으로 거리를 h1, h2라 하고, 알려진 네 점에서의 데이터 값을 A, B, C, D라 할 때, P에서의 데이터 값은 bilinear interpolation에 의해 다음과 같이 계산된다 (단, α=h1/(h1+h2), β=h2/(h1+h2), p=w1/(w1+w2), q=w2/(w1+w2)).

 --- (3)

계산 원리는 쉽게 짐작할 수 있듯이 A, B를 보간하여 M을 얻고 C, D를 보간하여 N을 얻은 후에 M, N을 보간하여 P를 얻는 방식이다. 또는 그 순서를 바꾸어 U와 V를 먼저 얻은 후에 U, V를 보간해도 동일한 결과를 얻을 수 있다.

그런데, 위의 보간 방법은 원래의 데이터의 위치가 직사각형을 이룰 경우에만 적용할 수 있는 방법이다. 만일 아래 그림처럼 임의의 형태의 사각형에서 사각형 내부를 보간하고자 할 때에는 어떻게 해야 할까?

<그림 4>

이 경우에는 아래 그림처럼 원래의 사각형을 어떤 직사각형으로 워핑(warping)시킨 후 워핑된 사각형에서 보간(interpolation)을 수행하면 된다.

워핑할 사각형은 임의의 직사각형이 가능하지만 편의상 네 꼭지점의 좌표가 (0,0), (0,1), (1,1), (1,0)인 단위 정사각형으로 워핑시킨다고 하자.

<그림 5>

이 경우 보간 방법은 원래 사각형의 네점 ABCD를 A'B'C'D'으로 변환시키는 선형변환(linear transformation) T를 구한 후, 구한 T를 이용하여 P를 변환시킨 P'를 구하고 단위 정사각형에서 bilinear interpolation을 수행하면 된다. 선형변환 T는 2D homography ([영상 Geometry #3] 2D 변환 (Transformations) 글 참조)를 이용하여 구할 수 있다.

4. Trilinear Interpolation

삼선형 보간법 정도로 번역할 수 있겠으며 1차원에서의 선형보간법을 3차원으로 확장한 것이다.

Trilinear interpolation 방법은 3차원 공간에서 8개의 꼭지점으로 이루어진 육면체의 변 및 내부의 임의의 점에서의 데이터 값을 선형적으로 보간하는 방법을 일컫는 말이다.

<그림 6>

Trilinear interpolation 방법은 위 그림과 같이 bilinear interpolation과 원리는 동일하며 P에서의 보간값을 구하기 위해 먼저 M, N에서의 값을 보간하고 이로부터 R에서의 값을 보간한다. 마찬가지로 U, V에서의 값을 보간한 후 이로부터 S에서의 값을 보간한다. 마지막으로 R, S로부터 P를 보간한다.

만일 원래의 데이터 점들이 직육면체를 이루지 않을 경우에는 bilinear interpolation에서 설명한 방법과 마찬가지로 원래의 육면체를 임의의 직육면체로 매핑(워핑)한 후 워핑된 직육면체에서 보간값을 계산하는 방법을 사용한다.

5. 히스토그램의 보간(interpolation)

Hough 변환을 위해 히스토그램을 구할 때, 또는 영상 feature를 추출하기 위해 히스토그램을 구할 때 등 다양한 히스토그램(histogram) 변환 작업에는 설정한 히스토그램의 bin 크기에 따라 필연적으로 계단현상(aliasing, 히스토그램의 bin과 bin 경계에 위치한 값이 어떤 bin에 떨어지느냐에 따라 히스토그램 결과값이 크게 달라지는 현상)이 발생하게 된다.

이러한 히스토그램 계단현상을 완화하기 위해서 앞서 설명한 보간 방법들이 주로 사용되는데, 예를 들어 HOG(Histogram of Oriented Gradient)에서는 gradient의 방향 히스토그램을 구할 때 trilinear interpolation 방법이 적용된다 (http://lear.inrialpes.fr/people/dalal/NavneetDalalThesis.pdf의 Appendix D).

먼저 1D 히스토그램을 생성할 때 선형보간법을 적용하는 방법을 설명하면, 어떤 데이터 x에 대해 가장 가까운 인접한 두 히스토그램 bin을 b1, b2라 하고 x에서 b1까지의 거리를 d1, b2까지의 거리를 d2라 하면 b1의 값은 d2/(d1+d2)만큼 증가시키고 b2의 값은 d1/(d1+d2)만큼 증가시키는 방식이다.

만일 2D 히스토그램을 생성하는 경우라면 하나의 입력 데이터에 대해서 해당 데이터와 가장 가까운 인접한 4개의 bin 값을 bilinear interpolation 방식에 의해 증가시킨다. 예를 들어, 어떤 데이터에서 추출한 feature 값이 (f, g)이고 (f, g)와 가장 가까운 서로 인접한 4개의 히스토그램 bin을 (f1, g1), (f2, g1), (f1, g2), (f2, g2), f와 f1의 거리를 d1, f와 f2의 거리를 d2, g와 g1과의 거리를 k1, g2와의 거리를 k2라 하면 각각의 bin 값들은 다음과 같이 증가된다.

(f1, g1) : d2/(d1+d2) * k2/(k1+k2) 만큼 증가

(f1, g2) : d2/(d1+d2) * k1/(k1+k2) 만큼 증가

(f2, g1) : d1/(d1+d2) * k2/(k1+k2) 만큼 증가

(f2, g2) : d1/(d1+d2) * k1/(k1+k2) 만큼 증가 --- (4)

식 (4)는 하나의 데이터에 대해 bin의 값을 1 증가시키는 경우의 증가량 식이며 만일 어떤 데이터에 대해 증가시켜야 할 bin의 값이 1이 아니라 v라면 v에 식 (4)의 값을 가중치로 하여 곱한 값만큼씩 증가시키면 된다.

만일 3D 히스토그램을 생성하는 경우라면 데이터에 가장 가까우면서도 서로 인접한 8개의 bin을 찾아서 trilinear interpolation 방식으로 bin 값을 증가시키면 된다. 참고로 HOG의 경우를 예로 들면, HOG에서는 영상 영역을 8 x 8 픽셀 크기의 셀(cell)들로 분할한 후 각 셀마다 gradient 방향 히스토그램을 구하는데 HOG 히스토그램은 셀의 x좌표, y좌표, 그리고 gradient 방향 이렇게 3개의 축에 대해 히스토그램을 구하는 3D 히스토그램으로 볼 수 있다. 이후 HOG에서는 영상의 각 픽셀에 대해 가장 가까운 인접한 4개의 셀을 선택하고 또한 해당 픽셀에서의 gradient 방향값과 가장 가까운 2개의 bin을 선택함으로써 총 8개의 bin을 선택(각 셀의 히스토그램마다 2개씩의 bin을 선택)하여 bin 값을 update시킨다.

☞ 기본적인 내용이긴 하지만 막상 trilinear interpolation이 뭐지? 하면 햇갈릴 수 있고 또한 임의의 사각형이나 육면체, 히스토그램에 보간법을 적용하는 것은 국내에는 거의 정보가 없어서 정리를 해 보았습니다.

by 다크 프로그래머