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

Інтерполяція зображень  відбувається у всіх цифрових фотографіях  на певному етапі, будь то дематризація або масштабування. Вона відбувається всякий раз, коли  змінюється розмір зображення з однієї сітки пікселів в іншу. Зміна розміру зображення необхідно, коли потрібно збільшити або зменшити число пікселів, тоді як зміна положення може відбуватися в самих різних випадках: виправлення викривлень об'єктива, зміна перспективи або поворот зображення.

Наприклад:

Вихідне зображення                                          Результат інтерполяції

 

Навіть якщо зміні розміру  піддається одне і те ж зображення, результати можуть значно відрізнятися в залежності від алгоритму інтерполяції. Оскільки будь-яка інтерполяція є всього лише наближенням, зображення буде дещо втрачати якість всякий раз, коли піддається інтерполяції.

Суть інтерполяції полягає  у використанні наявних даних  для отримання очікуваних значень  в невідомих точках. Наприклад, якщо потрібно знати, яка була температура опівдні, але її вимірювали в 11 і в годину, можна припустити її значення, застосувавши лінійну інтерполяцію:

Якби було додаткове вимірювання  в половині дванадцятого, то можна було б помітити, що до опівдня температура зростала швидше, і використовувати це додаткове вимірювання для квадратичної інтерполяції:

 

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

 

 

Приклад зміни розміру  зображення

Інтерполяція зображень  працює в двох вимірах і намагається  досягти найкращого наближення в  кольорі і яскравості пікселя, грунтуючись  на значеннях оточуючих пікселів. Наступний приклад ілюструє роботу масштабування:

Оригінал                                до                     після              без інтерполяції

 

На відміну від коливань температури повітря і вищенаведеного ідеального градієнта, значення пікселів можуть мінятися набагато більше різко від точки до точки. Як і в прикладі з температурою, чим більше ми знаєм про оточуючі пікселі, тим краще спрацює інтерполяція. Ось чому результати швидко погіршуються в міру розтягування зображення, а крім того, інтерполяція ніколи не зможе додати зображенню детальності, якої в ньому немає.

 

Приклад обертання зображення

Інтерполяція відбувається також кожного разу, коли ми повертаєм або змінюєм перспективу зображення. Попередній приклад був оманливим, оскільки це окремий випадок, в якому інтерполянти зазвичай працюють непогано. Наступний приклад показує, як швидко може бути втрачена детальність зображення:

Оригінал                    поворот        поворот       2 поворота      6 поворотів

                                    на 45°          на 90°         на 45°                  на 15°

                                                      (без втрат)

 

 

Поворот на 90 ° не вносить  втрат, оскільки ні один піксель не потрібно помістити на кордон між  двома (і як наслідок розділити). Відмітимо, як велика частина деталей втрачається при першому ж повороті, і як якість продовжує падати при наступних. Це означає, що слід уникати обертань, наскільки можливо; якщо нерівно виставлений кадр вимагає повороту, не слід обертати його більше одного разу.

 Вищенаведені результати  використовують так званий «Бікубічний» алгоритм і показують істотне погіршення якості. Зверніть увагу, як знижується загальний контраст у зв'язку зі зниженням інтенсивності кольору, як навколо світло-синього виникають темні забарвлення. Результати можуть бути значно кращі в залежності від алгоритму інтерполяції і зображуваного предмета.

 

 

Типи алгоритмів інтерполяції

Загальноприйняті алгоритми  інтерполяції можна поділити на дві  категорії: адаптивні та неадаптивні. Адаптивні методи змінюються залежно  від предмета інтерполяції (різкі  межі, гладка текстура), тоді як неадаптивні  методи обробляють всі пікселі однаково.Неадаптивні  алгоритми включають: метод найближчого  сусіда, білінійну, бікубічну. В залежності від складності, вони використовують від 0 до 256 (або більше) суміжних пікселів для інтерполяції. Чим більше суміжних пікселів вони включають, тим більше точними можуть виявитися, але це досягається за рахунок значного приросту часу обробки. Ці алгоритми можуть використовуватися як для розгортки, так і для масштабування зображення.

 

 

Адаптивні алгоритми включають  в себе багато комерційних алгоритмів в ліцензованих програмах, таких як Qimage, PhotoZoom Pro, Genuine Fractals та інші. Багато з них застосовують різні версії своїх алгоритмів (на основі попіксельного аналізу), коли виявляють наявність кордону - з метою мінімізувати непривабливі дефекти інтерполяції в місцях, де вони найбільш помітні. Ці алгоритми в першу чергу розроблені для максимізації бездефектної детальності збільшених зображень, так що деякі з них для обертання або зміни перспективи зображення непридатні.

 

 

Метод найближчого сусіда

Це найбільш базовий зі всіх алгоритмів інтерполяції, який вимагає  найменшого часу обробки, оскільки враховує тільки один піксель - найближчий до точки  інтерполяції. В результаті кожен  піксель просто стає більше.

 

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

Білінійна інтерполяція розглядає  квадрат 2x2 відомих пікселів, оточуючих невідомий. В якості інтерпольованого значення використовується зважене усереднення цих чотирьох пікселів. В результаті зображення виглядають значно більш гладко, ніж результат роботи методу найближчого сусіда. Дана діаграма відноситься до випадку, коли всі відомі пікселі рівні, так що інтерпольоване значення просто є їх сумою, поділеною на 4.

 

Бікубічна інтерполяція

Бікубічна інтерполяція йде на один крок далі білінійної, розглядаючи масив з 4x4 оточуючих пікселів - всього 16. Оскільки вони знаходяться на різних відстанях від невідомого пікселя, найближчі пікселі отримують при розрахунку більшу вагу. Бікубічна інтерполяція виробляє значно більш різкі зображення, ніж попередні два методи, і можливо, є оптимальною по співвідношенню часу обробки і якості на виході. З цієї причини вона стала стандартною для багатьох програм редагування зображень (включаючи Adobe Photoshop), драйверів принтерів і вбудованою інтерполяції камер.

 

 

 

 

Інтерполяція вищого порядку: сплайни і sinc

Є багато інших інтерполяторів, які беруть до уваги більше оточуючих пікселів і таким чином вимагають більш інтенсивних обчислень. Ці алгоритми включають в себе сплайни і кардинальний синус (sinc), і вони зберігають більшість інформації про зображення після інтерполяції. Як наслідок, вони є виключно корисними, коли зображення вимагає декількох поворотів або змін перспективи за окремі кроки. Однак, для однократних збільшень або поворотів такі алгоритми вищого порядку дають незначне візуальне поліпшення при істотному збільшенні часу обробки. Більш того, в деяких випадках алгоритм кардинального синуса на гладкій ділянці відпрацьовує гірше, ніж бікубічна інтерполяція.

 

 

Спостережувані дефекти  інтерполяції

Всі неадаптивні інтерполятори намагаються підібрати оптимальний баланс між трьома небажаними дефектами: граничними забарвлення, розмиттям і ступінчастістю.

 

Оригінал                              ступінчасть            розмиття         забарвлення

 

Навіть найбільш розвинені  неадаптивні інтерполятори завжди змушені збільшувати або зменшувати один з вищенаведених дефектів за рахунок двох інших - внаслідок, як мінімум один з них буде помітний. Зауважимо, наскільки граничне забарвлення схоже на дефект, породжуваний підвищенням різкості за допомогою нечіткої маски, і як воно підвищує гадану різкість за допомогою посилення чіткості.

Адаптивні інтерполятори можуть створювати або не створювати вищеописані дефекти, але вони теж можуть породити невластиві вихідному зображенню текстуру або одиночні пікселі на великих масштабах:

 

Оригінал з малорозмірною                                 ділянка при збільшенні

            текстурою                                                              220%

 

З іншого боку, деякі «дефекти»  адаптивних інтерполяторів теж можуть розглядатися як переваги. Оскільки користувач очікує побачити в областях з дрібною текстурою, таких як листя, деталі аж до найдрібніших подробиць, подібні малюнки можуть обдурити його на відстані (для певних видів матеріалу).

 

Оптичний і цифровий зум

Багато компактні цифрові  камери можуть здійснювати як оптичне, так і цифрове збільшення (зум). Оптичний зум здійснюється рухом варіоб'єктива, так щоб світло посилювалось до попадання на цифровий сенсор. На контрасті, цифровий зум знижує якість, оскільки здійснює просту інтерполяцію зображення - вже після отримання його сенсором.

 

Навіть незважаючи на те, що фото з ​​використанням цифрового  зума містить те ж число пікселів, його детальність виразно менша, ніж при використанні оптичного зума. Цифровий зум слід практично повністю виключити, за врахуванням випадків, коли він допомагає відобразити віддалений об'єкт на ЖК-екрані камери. З іншого боку, якщо ми звичайно знімаємо в JPEG і хочемо згодом обрізати і збільшити знімок, цифровий зум має перевагу в тому, що його інтерполяція здійснюється до внесення дефектів компресії.

 

 

Математична модель білінійної інтерполяції

 

Припустимо, що необхідно  інтерполювати значення функції F в  точці P = (х, у). Для цього необхідно  знати значення функцій в (оточуючих P) точках Q11 = (x1, y1), Q12 = (x1, y2), Q21 = (x2, y1), і Q22 = (x2, y2).

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

Тепер проводиться лінійна  інтерполяція між допоміжними точками  R₁ і R₂.

Це і є приблизне  значення функції в точці P, тобто F (х, у).

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

Або ж за допомогою множення векторів з матрицею:

Потрібно звернути увагу, що сам інтерполянт нелінійний:

так як він створений за допомогою двох лінійних функцій. Альтернативне написання:

де

Результат білінійної інтерполяції не залежить від порядку кроків. Можливо спочатку інтерполювати між відомими точками вздовж осі ординат і потім, отримавши два допоміжних значення, інтерполювати між ними уздовж осі абсцис. Результат буде той же.

 

 

Блок-схема роботи алгоритму:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список використаних джерел

1. http://ru.wikipedia.org/wiki/Билинейная_интерполяция
2. http://www.cambridgeincolour.com/ru/tutorials/image-interpolation.htm
3. http://www.cambridgeincolour.com/ru/tutorials/digital-photo-enlargement.htm