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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Якщо необхідно інтерполювати значення функції f в точці P = (x, y). І задано значення функції в навколишніх до P точках Q11 = (x1y1), Q12 = (x1y2), Q21 = (x2y1), и Q22 = (x2y2).

Спершу лінійно інтерполюємо в напрямку осі 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 x y \,

де

 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;
        }
    }
}

Див. також[ред.ред. код]