Білінійна інтерполяція

Білінійна інтерполяція — узагальнення лінійної інтерполяції для функції двох змінних. Ідея в тому, що проводиться лінійна інтерполяція по одній осі, а потім по іншій осі.

Відомо значення функції в чотирьох червоних точках. Значення функції в зеленій точці потрібно інтерполювати.

Приклад білінійної інтерполяції в одиничному квадраті. Інтерпольовані значення представлені кольором.

Якщо необхідно інтерполювати значення функції f в точці P = (x, y). І задано значення функції в навколишніх до P точках Q₁₁ = (x₁, y₁), Q₁₂ = (x₁, y₂), Q₂₁ = (x₂, y₁), та Q₂₂ = (x₂, y₂).

Спершу лінійно інтерполюємо в напрямку осі x:

f(R_{1})\approx {\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{11})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{21}),\quad R_{1}=(x,y_{1})

f(R_{2})\approx {\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{12})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{22}),\quad R_{2}=(x,y_{2})

Тепер проводимо лінійну інтерполяцію в напрямку осі y (між точками $R_{1}$ та $R_{2}$ ) щоб отримати кінцевий результат:

f(P)\approx {\frac {y_{2}-y}{y_{2}-y_{1}}}f(R_{1})+{\frac {y-y_{1}}{y_{2}-y_{1}}}f(R_{2}).

Коли відомі вершини є вершинами одиничного квадрата: (0, 0), (0, 1), (1, 0) та (1, 1), формула білінійної інтерполяції спрощується до

f(x,y)\approx f(0,0)\,(1-x)(1-y)+f(1,0)\,x(1-y)+f(0,1)\,(1-x)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}}

Інтерполяція є добутком двох лінійних функцій. І вона також може бути записана як:

b_{1}+b_{2}x+b_{3}y+b_{4}xy\,

де

b_{1}=f(0,0)\,

b_{2}=f(1,0)-f(0,0)\,

b_{3}=f(0,1)-f(0,0)\,

b_{4}=f(0,0)-f(1,0)-f(0,1)+f(1,1)\,

.

Результат білінійної інтерполяції не залежить від порядку виконання кроків інтерполяції.

Очевидним узагальненням білінійної інтерполяції на функцію трьох змінних є — трилінійна інтерполяція.

Білінійна інтерполяція в комп'ютерній графіці

Приклад збільшення частини зображення — простим масштабуванням і зі застосуванням білінійної інтерполяції

У комп'ютерній графіці білінійна інтерполяція набула широкого поширення у процесі ресемплінга (або, простіше кажучи, масштабування) зображень.

При збільшенні цифрових зображень спостерігається сильна пікселізація зображення. Білінійна інтерполяція використовується для розрахунку кольорів додаткових пікселів $(P)$ щодо основних, вихідних $(Q),$ що дозволяє згладжувати переходи. Значенням функції $f$ у даному випадку виступає колір пікселя (його складові). При цьому квадрат, утворений чотирма розглянутими основними точками приймається за одиничний.

Недолік методу

Головним мінусом білінійної інтерполяції при масштабуванні зображень є той факт, що при збільшенні в $N$ разів зображення розміром $W$ на $H$ пікселів в результаті буде отримано зображення розміром не $NW$ на $NH$ пікселів, а $(N(W-1)+1)$ на $(N(H-1)+1)$ пікселів.

Пов'язано це з тим, що у вихідному зображенні, наприклад, по горизонталі мається $W$ точок, тобто $(W-1)$ суміжних пар. При збільшенні зображення в $N$ раз між кожною парою основних точок вставляється по $(N-1)$ додаткових точок (тобто при збільшенні вдвічі між основними точками вставляється ще по одній, при збільшенні втричі - по дві і т. д.). Усього в результаті ширина результуючого зображення дорівнюватиме сумі кількості основних і додаткових точок:

W+(W-1)(N-1)=N(W-1)+1

.

Простіше кажучи , для останнього пікселя ( в кожному рядку і стовпці ) вихідного зображення не знаходиться пари , з якою можна було б провести інтерполювання .

Для обходу цього обмеження , по-перше , звичайно приймається , що у вихідному і отриманому зображеннях колірні значення пікселів семпліровані з їхніх центрів , а не з кутів , тобто наприклад , якщо взяти абсолютну довжину і ширину зображення рівними 1 , в зображенні розміром 2 на 2 координатами вихідних точок є ( 0.25 ; 0.25 ) , ( 0.25 ; 0.75 ) , ( 0.75 ; 0.25 ) , і ( 0.75 ; 0.75 ), а не ( 0 ; 0 ) , ( 0 ; 0.5) , ( 0.5 ; 0 ) , і ( 0.5 ; 0.5) ( поправка на дискретизацію ) . Таким чином забезпечується правильна центровка зображення при масштабуванні , але проблемними виявляються не тільки останній рядок і останній стовпець , а всі прикордонні пікселі одержуваного зображення однаково , бо їх координати випадають за межі прямокутника , що окреслює точки семплування вихідного зображення (наприклад, при масштабуванні в 4 на 4 потрібно обчислити значення в точках ( 0.125 ; 0.125 ) , ( 0.125 ; 0.875 ) і т.д.). Потім, так як значення в цих точках не можуть бути інтерпольованні, то потрібно розширити вихідне зображення одним із способів (вибір якого залежить від способу подальшого використання зображення )

Екстраполяція значень крайових пікселів;
Дзеркальне відображення вихідного зображення щодо кожного краю, і центральне по кутах. Як значення відсутніх пікселів використовуються копії значень пікселів з того ж краю; таким чином, пікселі, що випадають за вихідні координати, є інтерполянтами лише в одному вимірі, а в іншому копіями крайових значень;
Теселяція вихідного зображення; копії вихідного зображення "приклеюються" впритул з кожного краю і з кутів. Як кольори відсутніх пікселів, таким чином, використовуються значення пікселів з протилежного краю. Метод підходить, якщо інтерпольоване зображення саме використовуватиметься для теселяції (наприклад, для заповнення багатокутників при текстуруванні).

Після подібної попередньої обробки процедура білінійної інтерполяції застосовується в початковому вигляді, з отриманням зображення очікуваного розміру ( $NW$ на $NH$ ).

Приклад програми

Нижче наведено приклад програми білінійної інтерполяції зображення, написаний на С++

void resample( const unsigned* inBuf  // вхідний масив пікселів
             , unsigned* outBuf       // результат - вихідний масив пікселів
             , int oldWidth           //ширина оригіналього зображення
             , int oldHeight          //висота оригіналього зображення
             , int newWidth           //ширина результуючого зображення
             , int newHeight          //висота результуючого зображення
             )
{
    const float div_height = (float) ( (oldHeight - 1) ) / (newHeight - 1);
    const float div_width = (float) ( (oldWidth - 1) ) / (newWidth - 1);
    float i_tmp = 0.f;
    for ( int i = 0; i < newHeight; ++i, i_tmp += div_height )
    {
        float j_tmp = 0.f;
        int l = (int)(i_tmp);
        if (l > oldHeight - 2)
        {
            l = oldHeight - 2;
        }
        const float u = i_tmp - l;
        l *= oldWidth;
        for ( int j = 0; j < newWidth; ++j, j_tmp += div_width )
        {

            int c = (int) (j_tmp);
            if (c > oldWidth - 2)
            {
                c = oldWidth - 2;
            }
            const float t = j_tmp - c;

            //Коефіцієнти
            const float d1 = (1 - t) * (1 - u);
            const float d2 = t * (1 - u);
            const float d3 = t * u;
            const float d4 = (1 - t) * u;

            const int ind = l + c; // для оптимізації (щоб не рахувати далі 4 рази)
        // значення кольору в 4 пікселях, за якими інтерполюємо
            const unsigned p1 = inBuf[ ind ];
            const unsigned p2 = inBuf[ ind + 1 ];
            const unsigned p3 = inBuf[ ind + oldWidth + 1 ];
            const unsigned p4 = inBuf[ ind + oldWidth];

            // Записуємо результуючий піксель
            *outBuf++ = p1 * d1 + p2 * d2 + p3 * d3 + p4 * d4;
        }
    }
}

Див. також

Інтерполяція

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.