Новые методы

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

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

Линейная интерполяция между двумя точками (х₀,y₀) и (x₁,y₁) рассчитывается по формуле

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

…, то, используя ту же формулу, нам нужно продолжить линию с отрезка [x_{0 ,} x₁] до [(x₀*3-x₁)/2 , (x₁*3-x₀)/2] (то есть, например с [0.25,0.75] до [0,1])

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

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

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

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

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

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

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

Так как мы работаем в двух измерениях, то и точек будет 2^2=4 – (x₀,y₀), (x₀,y₁), (x₁,y₀), (x₁,y₁), а их значениями q₁, q₄, q₂ и q₃ соответственно

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

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

Тут мы уже видим, что за пределами интерполяции (экстраполяция) значения могут уходить выше предела яркости (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:

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

И уменьшим его в 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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