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

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

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

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

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

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

${\displaystyle 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})}$

${\displaystyle 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 (між точками ${\displaystyle R_{1}}$ та ${\displaystyle R_{2}}$) щоб отримати кінцевий результат:

${\displaystyle 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), формула білінійної інтерполяції спрощується до

${\displaystyle 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.}$

можна записати у вигляді наступної білінійної форми:

${\displaystyle 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}}}$

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

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

де

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 ) і т.д.). Потім, так як значення в цих точках не можуть бути інтерпольованні, то потрібно розширити вихідне зображення одним із способів (вибір якого залежить від способу подальшого використання зображення )

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

Після подібної попередньої обробки процедура білінійної інтерполяції застосовується в початковому вигляді, з отриманням зображення очікуваного розміру (${\displaystyle NW}$ на ${\displaystyle 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;  }  } } 

Див. також

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