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

영상처리 2014.01.13 21:20

이 글은 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 다크 프로그래머


저작자 표시 비영리 변경 금지
신고
  • BlogIcon 신당기 2014.01.14 12:22 신고 ADDR 수정/삭제 답글

    다크님.....벡터를 보간한다고 하면.....
    각 요소별로 보간식을 구해서 하는것이 맞나요....
    아니면....제가 참고하고 있는 RBF Interpolation 논문처럼...벡터에 대해서 계수를 구한다음 요소별로 계산하는 것이 맞나요?
    아님....둘 다 가능한데 결과값이 다르게 나오는 건가요? 마치 메디안필터에서 메디안을 정하는것처럼요.

    • BlogIcon 다크pgmr 2014.01.14 12:47 신고 수정/삭제

      두 벡터를 보간하는 문제는 벡터의 차원과 관계없이 2개의 데이터 점을 알고 있을 때 그 사이값을 보간하는 문제로서 그냥 linear interpolation 문제입니다(bilinear나 trilinear가 아님). 2차원의 경우 두 벡터를 v1=(x1,y1), v2=(x2,y2)라면 v1, v2의 interpolation은 v = v1+a*(v2-v1) (a는 0<=a<=1의 상수)이며, 이를 좌표로 보면 (x,y) = (x1,y1)+a*(x2-x1,y2-y1) = (x1+a*(x2-x1), y1+a*(y2-y1)) 입니다. 즉, x, y에 대해 독립적으로 보간을 하지는 않습니다.
      제가 글에서는 bilinear가 2차원에서의 보간이라고 했지만 사실은 데이터의 보간 방향이 2개의 축으로 구성된 보간 문제라고 하는 것이 보다 정확한 표현이 되겠습니다. 3차원 공간에서도 동일 평면위에 있는 4개의 점에 대해 보간을 하면 bilinear interpolation이 됩니다.
      즉, 요는 벡터의 차원이 아니라 벡터의 개수, 아니 보다 정확하게는 보간하고자 하는 축(feature)의 개수가 중요합니다.

    • BlogIcon 신당기 2014.01.14 19:11 신고 수정/삭제

      잘 알겠습니다....정말????
      수학이 이렇게 부족하다니....참.........
      그런데요....다크님....벡터의 보간을 컴터로 계산할 경우에는 어떻게 해야하나요? 컴터에 벡터를 표현할 방법이 없고....음 Point변수형이 있긴하네요....
      암튼.....다크님이 바로 위에서 설명해주신 벡터의 보간식에서 보면....결국은 요소별로 해도 같은 결과를 보여주는것 같아서요....

    • BlogIcon 다크pgmr 2014.01.15 09:30 신고 수정/삭제

      말씀하신데로 요소별로 해도 결과는 같은 값이 나오겠네요 ^^;
      벡터를 위한 전용 자료구조는 따로 없으며 컴퓨터에서는 벡터는 그냥 배열(array) 또는 점(point)으로 표현됩니다. 프로그램을 짜는 사람이 그 데이터를 벡터로서 다뤄야 합니다..

  • 풍성이 2014.01.14 16:22 신고 ADDR 수정/삭제 답글

    정말 필요한 자료였는데 항상 감사드립니다.

  • 김경민_군산대학교_조선공학과 2014.01.26 14:49 신고 ADDR 수정/삭제 답글

    1년동안 비전쪽 혼자 공부하면서 힘들었는데.. 정말 이 블로그가 도움이 많이 되는것 같습니다.
    책 하나 내셔도 될것같아요.. 혼자 하는 공부 도움 주셔서 정말 감사합니다. 열심히해서 나중에 사회에서 다크님과 비전쪽에서 뵙고 싶습니다.

  • 감사 2014.10.06 21:52 신고 ADDR 수정/삭제 답글

    감사합니다.^^

  • man_oh 2014.11.25 15:06 신고 ADDR 수정/삭제 답글

    영상에 관한 여러글 보고 있습니다.
    블로그에 퍼갔고 앞으로도 퍼갈 예정인데..
    출처는 표시했구요
    이상있으면 말해주세요.

    • BlogIcon 다크pgmr 2014.11.25 18:10 신고 수정/삭제

      안녕하세요. 개인적 참고용이라면 오프라인 파일형태로 보관해 주시면 감사하겠습니다. 물론 출처를 밝히고 온라인 게시해도 큰 문제는 없습니다. 하지만 향후 내용의 수정이나 댓글, 다른 글들과의 연관성 등 측면에서 단순 복제의 경우에는 링크를 걸어주시면 감사하겠습니다.

  • 2016.01.21 18:08 ADDR 수정/삭제 답글

    비밀댓글입니다

    • BlogIcon 다크pgmr 2016.01.22 08:55 신고 수정/삭제

      보간을 해서 계단현상이 생기는 것이 아니라 원래 히스토그램에는 계단현상이 있기 때문에 이를 해결하기 위해서 보간을 합니다. 글의 내용이 잘못 전달된 것 같습니다.

  • bb 2016.10.16 17:57 신고 ADDR 수정/삭제 답글

    보간법과 안티에일리어싱과이 차이점이 무엇인지 궁금합니다!

    • BlogIcon 다크pgmr 2016.10.19 14:35 신고 수정/삭제

      보간법은 주변의 값을 이용해서 비어있는 값을 채우는 것을 말하고 안티에일리어싱은 계단현상을 없애기 위한 일련의 처리를 의미합니다. 안티에일리어싱에 사용되는 대표적인 방법 중 하나가 보간법입니다. 그리고 보간법은 관측값들을 이용해서 관측되지 않은 값들을 추정하는데 쓰이는 일반적인 방법론입니다.

  • 워리 2017.10.22 01:35 신고 ADDR 수정/삭제 답글

    안녕하세요! 요즘 보간법에 대해 공부하고 있는 학생입니다.. 다름이 아니고 정사각형은 위와 같이 정사각형의 내부점에 대한 좌표를 bilinear interpolation에 의해 위와 같이 구할수 있지만 혹시 정삼각형에 대한 것도 연구가 되어있는지 궁금합니다..ㅠㅠ 정삼각형의 내부점에 대한 좌표도 위와같이 구할 수 있을까요..?

    • BlogIcon 다크pgmr 2017.10.23 01:55 신고 수정/삭제

      딱히 삼각형의 경우를 본 것은 아니지만 이렇게 하면 되지 않을까요? 삼각형 ABC 내부에 점 P가 있을 때, AP를 연장한 선이 BC와 만나는 점이 M, BM:MC=b:c라면 M의 값은 (bC+cB)/(b+c). AP:PM=a:m라면 P의 값은 (aM+mA)/(a+m)이 될 것 같습니다.