Максимально точное увеличение разрешения изображений: билинейная аппроксимация

Новые методы

Это вторая статья из этого цикла, и, как говорилось в первой — интерполяция категорически не подходит для этой задачи, так как нарушает условие среднего (соответствующие пиксели получившегося изображения в среднем должны быть пикселем исходного), но я нашёл один частный случай, когда это не так:

(Кому легче воспринимать информацию в виде короткого видео-ролика в FullHD разрешении — сюда)

Линейная интерполяция между двумя точками (х0, y0) и (x1, y1) рассчитывается по формуле

y=y_0+  \frac{(y_1- y_0)(x-x_0)}{(x_1- x_0 )}Линейная интерполяция

Линейная интерполяция

Но так как логичнее использовать отцентрированную сетку, чем краевую…

Апскейл ближайшим соседом с разными сетками (слева – отцентрированная и там каждый пиксель имеет одинаковую площадь), у краевой - справа точки могут находиться прям по краям изображения

Апскейл ближайшим соседом с разными сетками (слева — отцентрированная и там каждый пиксель имеет одинаковую площадь), у краевой — справа точки могут находиться прям по краям изображения

…, то, используя ту же формулу, нам нужно продолжить линию с отрезка [x0, x1] до [(x0×3-x1)/2, (x1×3-x0)/2] (то есть, например с [0.25,0.75] до [0,1])

Линейная аппроксимация - условие среднего соблюдено

Линейная аппроксимация — условие среднего соблюдено

Проблемы начинаются, когда число точек не равно 2.

Кусочно-линейная интерполяция, как мы помним, не сохраняет средние значения, так же как, и кусочно-линейная аппроксимация:

436e204563cd020287dbbfd00d3cd9ba.png

Поэтому есть три варианта:

1) Сохранение средних значений и непрерывности (мы начинаем с конца прошлого отрезка)

fd45d580e9ecd6bd6adf49312cad1bdf.png

2) Сохранение средних значений и первой производной (вторая и следующие производные в любом случае теряются, так как прямая линия их не имеет) (находим среднюю линию от каждой из двух соседних аппроксимаций)

ba645fad75dd9b003056e3d0ea25375a.png

3) Сохранение непрерывности и производной (среднее от нескольких вариантов №1, начиная с разных точек, и учитывая их дальность от рассчитываемой точки)

4fa2714fa935d3bd714db16bd637159e.png

В любом случае, нам понадобится формула для билинейной интерполяции.

39d4216c98e4379a6ef98b7b929416e3.png

Так как мы работаем в двух измерениях, то и точек будет 2^2=4 — (x0, y0), (x0, y1), (x1, y0), (x1, y1), а их значениями q1, q4, q2 и q3 соответственно

Функция для математиков для константных координат и значений выглядит так:

f(x,y)=xy \frac{(q_1-q_2+q_3-q_4)}{(x_1-x_0)(y_1-y_0)}+x\frac{y_0 (q_4-q_3 )+y_1 (q_2-q_1 )}{(x_1-x_0)(y_1-y_0)}+y\frac{x_0 (q_2-q_3 )+x_1 (q_4-q_1)}{(x_1-x_0)(y_1-y_0}+\frac{x_0 (y_0 q_3-y_1 q_2 )-x_1 (y_0 q_4-y_1 q_1)}{(x_1-x_0)(y_1-y_0)}

И порождает гиперболический параболоид, являющийся линейчатой поверхностью, то есть поверхностью образованный движением прямой линии:

1b8325871e712e6afef09bcaf73dfffd.png

Тут мы уже видим, что за пределами интерполяции (экстраполяция) значения могут уходить выше предела яркости (255 для 8 бит) и даже уходить в минус — это проблема для цифровых изображений (например, клип-арта) и кем-то уменьшенных фото, но, теоретически, если это оригинальное фото с камеры (даже не RAW), то в реальности могли быть объекты с яркостью ниже и выше крайних порогов камеры (а при работе с фото нужно помнить, что мы имеем дело не с объективной яркостью, а относительно чувствительности фотоэлементов камеры), а если эти объекты были вдалеке и перемешавшись они попали на один пиксель (и очень тусклые — сажа, и очень яркие — блики от солнца), то исходный пиксель на фото будет в пределах нормы, и при апскейлиге фото — это вполне «нормальное» явление. Поэтому, пока, я с этой «проблемой» ничего не делал (там нужна будет уже квадрилатеральная аппроксимация) — и, хотя у меня получаются изображения большей битности (может это кому-то надо?), просто обрезаю значения до 0–255.

Функция для программистов будет попроще (C#):

static double Bilinear(int x, int y, double x0, double y0, double x1, double y1, double q1, double q2, double q3, double q4)
{
    double r0, r1, q12, q43, dx, dy;
    dx = x1 – x0;
    r1 = (x1 - x) / dx;
    r0 = (x – x0) / dx;
    q12 = r1 * q1 + r0 * q2;
    q43 = r1 * q4 + r0 * q3;
    dy = y1 – y0;
    return (y1 - y) / dy * q12 + (y – y0) / dy * q43;
}

Итак, вариант №2 выглядит странно и даёт большую ошибку в контексте апскейлинга, так как изображения в основном непрерывны, либо их прерывистость не укладывается в сеточную структуру исходного разрешения:

Среднее от четырёх (двух по каждой оси) аппроксимаций и одна аппроксимация через точку по каждой оси

Среднее от четырёх (двух по каждой оси) аппроксимаций и одна аппроксимация через точку по каждой оси

В чистом виде варианты №1 и №3 дают немного большую ошибку, чем что-то среднее между ними, так как либо условие среднего совсем не учитывается, либо производные — в итоге всё сильно размыто и звенит. Поэтому было реализовано два метода:

а) scaleSeparate — это вариант №3 для 5 точек — центральной и 4 углов, причём значения выше средних обращаются в максимальное, а ниже — в минимальное. Это немного улучшает условие среднего, но изображения становятся почти монохромными.

б) scaleBilinearApproximation — это вариант №3 для каждого исходного пикселя, но чем ближе к нему, тем результат более похож на результат от чистого варианта №1, начинающегося с этого пикселя

Тест №2

В первой статье мы провели тест некоторых алгоритмов на одном полихромном клип-арте с множеством мелких деталей и градиентом. Возьмём топ-11 этих алгоритмов и будем уменьшать количество вакантных мест с каждым тестом (таким образом, в этой статье останется 10 лучших алгоритмов). Итак, прошлые топ-11:

scaleSmooth

waifu2х (Арт — Anime Style, Cliparts)

обратный антиалиасинг

contrastBoldScale + корректировка Ланшоцем

билинейная+ интерполяция Original + корректировка Ланшоцем

бикубическая интерполяция HQ GDI + корректировка Ланшоцем

2xSal + корректировка Ланшоцем

окно Гаусса радиусом 1,2 px + корректировка Ланшоцем

билинейная интерполяция HQ GDI + корректировка Ланшоцем

окно косинуса + корректировка Ланшоцем

superXBR 2x

Во втором тесте мы возьмём другой полихромный клип-арт с множеством мелких деталей и градиентом, например, такой:

212c994af496c80a3b21e5478bf8d77d.png

И уменьшим его в 34,8125 раз.

Новшеством является не только другое изображение, но и масштаб — теперь он не только почти в 4 раза меньше, но и не является круглым числом — посмотрим, что это изменит.

И встречайте новых участников, которые хотят забрать чемпионство у старых — во первых, это, конечно, scaleSeparate и scaleBilinearApproximation, которые мы только что разбирали и которые можно попробовать (как исходники, так и .exe с GUI) во всё том же репозитории https://github.com/no4ni/scaleSmooth/, смотреть формирование изображений этими методами. Следом идут Ланшоц (окно кардинального синуса) радиусом 2 исходных пикселя (Lanczos2) (другие радиусы были проанализированы в прошлой статье) и методы изменения разрешения Photoshop: Preserve details (enlargement) (Сохранение деталей при увеличении), Preserve Details 2.0 (Сохранить детали 2.0), Bicubic smoother (enlargement) (Бикубический глаже для увеличения), Bicubic Sharper (reduction) (Бикубический острее для уменьшения) и Bicubic (smooth gradients) (Бикубический — гладкие градиенты). Также встречайте все сети unlimited: waifu2x, а именно: swin_unet/photo, cunet/art, swin_unet/art, swin_unet/art scan. Кстати, в прошлом этапе мы забыли самый стандартный метод на Windows — билинейная GDI. И, последние на сегодня — новые представители xBR (для пиксель-арта) — xBR-Hybrid, xBRZx6 (обычные представители были проанализированы в первой статье)

Проблема №1: как применить шейдер к изображению

xBR-Hybrid пока существует только в виде шейдера для видеокарт (это ускоряет производительность, но так как нет GUI (а шейдер сделан исключительно для эмуляторов старых игр) нельзя просто так взять любую картинку и увеличить её этим алгоритмом). Так как же применить любой шейдер к любому изображению? Здесь я сделал GLSL шаблон для применения таких шейдеров к изображению. В вершинном и пиксельном фрагментах есть строчки, которые нельзя удалять и строчки самого шейдера, которые можно заменить соответствующими строчками другого шейдера (прокомментированы), далее удаляем текстуру в Objects окне и создаём новую из нужного изображения, после чего правой кнопкой на неё Bind → Main (0)

f1af475b466f7e448c14a12621ed1bbf.png

Супер-результат, жалко, что у нас не пиксель-арт

Проблема №2: как уменьшить звон на изображении

scaleBiliniearApproximation выдаёт звон на изображении, причём чем в больше раз увеличиваем, тем он заметнее (на 2х-3х почти не видно). Это происходит потому что, сама формула линейной (билинейной) аппроксимации не способна отображать производные больше первого порядка:

Обратите внимание, что красная линия (вариант №1) как бы гуляет возле истинной функции (чёрная линия – то, что мы хотим получить), образуя треугольную волну – звон

Обратите внимание, что красная линия (вариант №1) как бы гуляет возле истинной функции (чёрная линия — то, что мы хотим получить), образуя треугольную волну — звон

e9ac797c5e8e988d8f7ce0bd8175c62a.png

Результат почти идеальный, если не считать огромного звона

Так как же убрать этот звон? Заметим, что такая же проблема есть у Ланшоца (поэтому радиус больше 3 исходных пикселей обычно не используется):

c4a20d66907a1de33aed5383eec25372.png

Структура звона немного другая, но в целом очень похоже.

Также обратите внимание, что scaleBilinearApproximation выглядит намного чётче, чем Ланшоц (соответственно, звон тоже сильнее заметен)

Но у Ланшоца мы можем менять радиус (а соответсвенно и звон), не меняя масштаб увеличения. Поэтому увеличим во столько же раз, но с радиусом, к примеру 3 исходных пикселя:

Ланшоц 3 исходных пикселя

Ланшоц 3 исходных пикселя

Звон пропал, осталось небольшое гало и появился небольшой алиасинг — края стали более похожи на лесенку

у Ланшоца проявляется либо сеточная структура либо звон.

А что будет если из Ланшоца большего радиуса вычесть Ланшоц меньшего радиуса?

27b5555d6d8fad0190241087657eaa34.png

Останется только звон, причём со знаком минус. (Здесь серый = 0)

Думаю, Вы уже догадались, что осталось сделать — сложить -антизвон с изображением со звоном:

ff2fc0b7c03e37bb39e3befe70e8e983.png

Слева — результат, справа — оригинал со звоном. Звон стал меньше, хотя остались его следы — структура звона разная.

После устранения всех проблем сравним методы по средней ошибке от оригинала:
(Рекомендую смотреть сравнение в формате видео — там же различные примеры на других классах изображений)

Этап 2

Этап 1

waifu2x — Artworks (Anime Style, Cliparts)

10,21%

15,72%

unlimited: waifu2x swin_unet / art

10,99%

14,00%

contrastBoldScale+ корректировка Ланшоцем

11,56%

16,97%

unlimited: waifu2x swin_unet / photo + корректировка Ланшоцем

11,72%

19,13%

Preserve details (enlargement)+ корректировка Ланшоцем

11,99%

16,29%

superXBR2x

12,15%

17,51%

unlimited: waifu2x swin_unet / art scan + корректировка Ланшоцем

12,23%

16,81%

unlimited: waifu2x cunet / art + корректировка Ланшоцем

12,40%

15,84%

обратный антиалиасинг

12,63%

16,93%

окно Гаусса радиусом 1,2 px + корректировка Ланшоцем

12,67%

17,26%

scaleBilinearApproximation+ корректировка Ланшоцем

12,69%

18,15%

xBRZx6 + корректировка Ланшоцем

12,74%

18,64%

Ланшоц 2 px

12,82%

18,05%

Bicubic Sharper + корректировка Ланшоцем

12,89%

17,89%

Bicubic (smooth gradients) + корректировка Ланшоцем

12,89%

17,99%

Bicubic Smoother + корректировка Ланшоцем

13,08%

18,01%

окно косинуса + корректировка Ланшоцем

13,15%

17,39%

билинейная+ Original + корректировка Ланшоцем

13,16%

17,02%

scaleSmooth

13,36%

15,64%

2xSal + корректировка Ланшоцем

13,48%

17,19%

Preserve Details 2.0 + корректировка Ланшоцем

13,63%

16,72%

xBR-Hybrid + корректировка Ланшоцем

13,86%

18,86%

билинейная HQ GDI + корректировка Ланшоцем

16,87%

17,29%

бикубическая HQ GDI + корректировка Ланшоцем

16,96%

17,13%

билинейная GDI + корректировка Ланшоцем

16,98%

16,91%

scaleSeparate + корректировка Ланшоцем

19,90%

19,36%

Обратите внимание, что результаты отсортированы по ошибке, получающейся от изображения второго этапа. А результаты первого этапа выбросить? Нет, но и нельзя просто так взять среднее от двух этапов — наглядно видно, что чем большее увеличение требуется, тем будет больше ошибка (1 этап требовал почти в 4 раза большего увеличения по каждой оси), поэтому нам надо нормализовать значения ошибок (где 0% — самый лучший метод на каждом этапе, а 100% — худший) и только потом взять среднее:

Нормализованная средняя ошибка по 2 этапам

unlimited: waifu2x swin_unet / art

4,00%

waifu2x — Artworks (Anime Style, Cliparts)

16,05%

unlimited: waifu2x cunet / art + корректировка Ланшоцем

28,42%

Preserve details (enlargement) + корректировка Ланшоцем

30,53%

scaleSmooth

31,57%

contrastBoldScale + корректировка Ланшоцем

34,72%

unlimited: waifu2x swin_unet / art scan + корректировка Ланшоцем

36,68%

обратный антиалиасинг

39,84%

superXBR2x

42,79%

Preserve Details 2.0 + корректировка Ланшоцем

42,98%

окно Гаусса радиусом 1,2 px + корректировка Ланшоцем

43,09%

билинейная+ Original+ корректировка Ланшоцем

43,40%

2xSal+ корректировка Ланшоцем

46,65%

окно косинуса+ корректировка Ланшоцем

46,79%

Bicubic Sharper+ корректировка Ланшоцем

50,16%

Bicubic (smooth gradients)+ корректировка Ланшоцем

51,04%

Ланшоц 2 px

51,32%

scaleBilinearApproximation+ корректировка Ланшоцем

51,53%

Bicubic Smoother+ корректировка Ланшоцем

52,21%

unlimited: waifu2x swin_unet / photo + корректировка Ланшоцем

55,69%

xBRZx6 + корректировка Ланшоцем

56,38%

билинейная GDI + корректировка Ланшоцем

62,10%

бикубическая HQ GDI + корректировка Ланшоцем

64,07%

xBR-Hybrid + корректировка Ланшоцем

64,20%

билинейная HQ GDI + корректировка Ланшоцем

65,13%

scaleSeparate + корректировка Ланшоцем

100,00%

В следующих статьях: новые методы, эксперименты с постеризацией и гамма-коррекцией, DES2, XBRz 5x, Ultra, 2xSCL, Super 2xSCL, 2xSCL, Eagle3XB, ещё более адекватный масштаб, больше нейросетей, купирование «проблемы» среза значений, методы Qimage, PhotoZoom Pro, Genuine Fractals, интерполяция Уиттекера — Шеннона и эксперимент с использованием последовательного увеличения на небольшие масштабы вместо одномоментного увеличения. Вообщем, будет много интересного — подписывайтесь!

Поиграться с моими старыми и новыми методами можно на гитхаб. Только имейте в виду, что в отличие от обычной билинейной интерполяции, которую легко можно всю распараллелить, scaleSeparate и scaleBilinearApproximation нельзя просто так. вообщем, они являются последовательными на уровне исходных пикселей и параллельными внутри них (но у меня это пока реализовано только на уровне CPU), поэтому они могут быть чрезвычайно медленными на более-менее  большой картинке (особенно scaleBilinearApproximation  в режиме Accurate) — кто может помочь с распараллеливанием на уровне GPU, решением обозначенной выше «проблемы», с другой оптимизацией и точностью — буду благодарен за пул реквесты и просто комментарии с умными мыслями.

Если Вы не хотите так глубоко лезть, можете просто посмотреть некоторые примеры работы этих методов (больше примеров в FullHD):

без корректировки выглядит не очень

без корректировки выглядит не очень

А пока используйте нейросети waifu

© Habrahabr.ru