Just a Computer Graphics Studio & My Life

[C/C++] Linear, Bilinear, Trilinear

在國中的時候就學過內插法,在我們生活中一直有用到,只是大多數都取概數,用習慣之後甚至連內插法這個關鍵字也忘了~在此我想要把內插法寫成程式,若只是一維內插法那就太簡單了,為了研究就接續寫二維內插法三維內插法,感覺超有趣~

這位作者將Linear, Bilinear, Trilinear寫成template,使得任何數字資料型態都可以使用~

Interpolation.h 程式碼


#if _MSC_VER > 1000
#pragma once
#endif

#ifndef HPP_INTERPOL
#define HPP_INTERPOL

template<class T> class Interpolator
{

public:
    /*
        Linear interpolation
        target  - the target point, 0.0 - 1.0
        v       - a pointer to an array of size 2 containg the two values

    */

    inline static T Linear(float target, T *v)
    {
        return (T)(target*(v[1])+ (T(1.0f) - target)*(v[0]));
    }
    /*
        BiLinear interpolation, linear interpolation in 2D
        target  - a 2D point (X,Y)
        v       - an array of size 4 containg values cockwise around the square starting from bottom left

        cost: performs 3 linear interpolations
    */
    inline static T Bilinear(float *target, T *v)
    {
        T v_prime[2] = {
                        Linear(target[1], &(v[0])),
                        Linear(target[1], &(v[2]))
                       };

        return Linear(target[0], v_prime);

    }

    /*
        TriLinear interpolation, linear interpolation in 2D
        target  - a 3D point (X,Y,Z)
        v       - an array of size 8 containg the values of the 8 corners
                    of a cube defined as two faces: 0-3 face one (front face)
                                                    4-7 face two (back face)

        cost: 7 linear interpolations
    */

    inline static T Trilinear(float *target, T *v)
    {
        T v_prime[2] = {
                         Bilinear(&(target[0]), &(v[0])),
                         Bilinear(&(target[1]), &(v[4]))
                       };

        return Linear(target[2], v_prime);
    }
};

#endif // HPP_INTERPOL

Interpolation.cpp 程式碼


#include "Interpolation.h"
#include <iostream>

using namespace std;

int main()
{
    // Test Linear interpolation
    float fVarsLin[2] = {1.0, 2.0};
    int iVarsLin[2] = {100, 200};

    float targetLin = 0.5;

    cout<<"Linear (f): "<<Interpolator<float>::Linear(targetLin, fVarsLin)<<endl;
    cout<<"Linear (i): "<<Interpolator<int>::Linear(targetLin, iVarsLin)<<endl;

    // Test Bilinear interpolation
    float fVarsBilin[4] = {1.0, 2.0, 3.0, 4.0};
    int iVarsBilin[4] = {100, 200, 300, 400};

    float targetBilin[2] = {0.5, 0.5};

    cout<<"Bilinear (f): "<<Interpolator<float>::Bilinear(targetBilin, fVarsBilin)<<endl;
    cout<<"Bilinear (i): "<<Interpolator<int>::Bilinear(targetBilin, iVarsBilin)<<endl;

    // Test Trilinear interpolation
    float fVarsTrilin[8] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0};
    int iVarsTrilin[8] = {100, 200, 300, 400, 500, 600, 700, 800};

    float targetTrilin[3] = {0.5, 0.5, 0.5};

    cout<<"Trilinear (f): "<<Interpolator<float>::Trilinear(targetTrilin, fVarsTrilin)<<endl;
    cout<<"Trilinear (i): "<<Interpolator<int>::Trilinear(targetTrilin, iVarsTrilin)<<endl;

	system("pause");
    return 0;
}

執行結果

Linear (f): 1.5
Linear (i): 150
Bilinear (f): 2.5
Bilinear (i): 250
Trilinear (f): 4.5
Trilinear (i): 450
請按任意鍵繼續 . . .

首先看最簡單的Linear,下圖我們先只看單一維度X或Y,這個大家一定都會,如上例周圍點陣列{1.0, 2.0},而目標點值0.5,內插結果就是1.5囉~

linear interpolation

一維內插,藍色點是目標。

接著看Bilinear,如上例周圍點陣列{1.0, 2.0, 3.0, 4.0},而目標點陣列{0.5, 0.5}。

內插過程~{1.0, 2.0}對應目標值0.5,內插結果A1.5;{3.0, 4.0}對應目標值0.5,內插結果B3.5;再以結果AB{1.5, 3.5}對應目標值0.5,最後內插結果就是2.5囉~

bilinear interpolation

二維內插,綠色點是目標。

最後來看Trilinear,如上例周圍點陣列{1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0},而目標點陣列{0.5, 0.5, 0.5}。

內插過程~

{1.0, 2.0, 3.0, 4.0}對應目標點陣列{0.50.5},內插結果A為{1.5, 3.5},接著以目標點值0.5,內插結果C為2.5;

{ 5.0, 6.0, 7.0, 8.0}對應目標點陣列{0.50.5},內插結果B為{5.5, 7.5},接著以目標點值0.5,內插結果D為6.5;

再以結果CD{2.5, 6.5}對應目標值0.5,最後內插結果就是4.5囉~

trilinear interpolation

三維內插,紅色點是目標。

試驗其它目標陣列,修改目標陣列數值:

  • float targetLin = 0.7;
  • float targetBilin[2] = {0.2, 0.7};
  • float targetTrilin[3] = {0.2, 0.5, 0.7};

Linear (f): 1.7
Linear (i): 169
Bilinear (f): 2.1
Bilinear (i): 209
Trilinear (f): 5.26
Trilinear (i): 525
請按任意鍵繼續 . . .

#首先看最簡單的Linear,下圖我們先只看單一維度X或Y,這個大家一定都會,如上例周圍點陣列{1.0, 2.0},而目標點值0.7,

內插過程~2*0.7+(1-0.7)*1=1.7,內插結果就是1.7囉~

#接著看Bilinear,如上例周圍點陣列{1.0, 2.0, 3.0, 4.0},而目標點陣列{0.2, 0.7}。

內插過程~{1.0, 2.0}對應目標值0.7,內插結果A為2*0.7+(1-0.7)*1=1.7;{3.0, 4.0}對應目標值0.7,內插結果B為4*0.7+(1-0.7)*3=3.7;再以結果AB{1.7, 3.7}對應目標值0.2,最後內插結果就是3.7*0.2+(1-0.2)*1.7=2.1囉~

#最後來看Trilinear,如上例周圍點陣列{1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0},而目標點陣列{0.5, 0.5, 0.5}。

內插過程~

{1.0, 2.0, 3.0, 4.0}對應目標點陣列{0.2, 0.5}:{1.0, 2.0}對應目標值0.5,內插結果A為2*0.5+(1-0.5)*1=1.5;{3.0, 4.0}對應目標值0.5,內插結果B為4*0.5+(1-0.5)*3=3.5;結果AB{1.5, 3.5}對應目標值0.2,最後內插結果C為3.5*0.2+(1-0.2)*1.5=1.9;

{ 5.0, 6.0, 7.0, 8.0}對應目標點陣列{0.5, 0.7},{5.0, 6.0}對應目標值0.7,內插結果D為6*0.7+(1-0.7)*5=5.7;{7.0, 8.0}對應目標值0.7,內插結果E為8*0.7+(1-0.7)*7=7.7;結果DE{5.7, 7.7}對應目標值0.5,最後內插結果F為7.7*0.5+(1-0.5)*5.7=6.7;

再以結果CF{1.9, 6.7}對應目標值0.7,最後內插結果就是6.7*0.7+(1-0.7)*1.9=5.26囉~

以上邏輯推理來自程式碼~其實只要Linear搞懂,Bilinear和Trilinear都沒啥大問題了!

參考:A Linear/Bilinear/Trilinear Interpolation Class、WiKi – Linear、WiKi – Bilinear、WiKi – Trilinear

廣告

發表留言

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s

標籤雲

%d 位部落客按了讚: