Качественное уменьшение изображений за константное время

в 7:53, , рубрики: Алгоритмы, высокая производительность, обработка изображений, ресайз

Хочу поделиться очень простым и эффективным методом ресайза изображении, который работает за константное время относительно размера исходного изображения и дает неожиданно качественный результат. Метод применим для любых языков и приложений.

Для начала давайте порассуждаем логически. Если вы делаете ресайз изображения, наверное вы хотите чтобы результат хотя бы отдаленно напоминал оригинал. Для этого нужно учесть как можно больше информации из исходного изображения. Вы слышали о методе «ближайшего соседа»? В этом методе для каждой точки конечного изображения просто берется какая-то одна точка из исходного изображения в неизменном виде.

Качественное уменьшение изображений за константное время - 1
Уменьшение изображения 4928×3280 до 256×170 ближайшим соседом.

Рекомендую смотреть примеры из статьи в браузере в масштабе 100% и без ретины. То есть по максимуму исключить ресайз при просмотре.

Результат не представляет ничего хорошего. Изображение дерганое, зернистое, даже трудно понять что на нем изображено. Особенно если на исходном изображении было много мелких деталей или оно само было зернистым. Почему так получается? Потому что в конечном изображении было учтено очень мало информации из исходного. Если условно отметить на исходном изображении те точки, которые попадают в конечное, получится вот такая сеточка:

Качественное уменьшение изображений за константное время - 2
Точки, которые попадут в конечное изображение размером 20×13.

Теперь визуально можно оценить, насколько мало информации об исходном изображении попадает в конечное. Согласитесь, маловероятно, что именно по этой сеточке будут располагаться пиксели, которые дадут хорошее представление об изображении на исходной картинке.

Совсем другой результат дает, например, ресайз с помощью сверток. В нем каждый пиксель исходного изображения вносит вклад в конечное, да еще и ни раз. Поэтому изображение получается плавным, а при выборе хорошего фильтра, четким.

Качественное уменьшение изображений за константное время - 3
Уменьшение с 4928×3280 до 256×170 свертками с бикубическим фильтром.

Тем не менее у метода «ближайшего соседа» есть одно неоспоримое преимущество: он работает за константное время относительно размера исходного изображения. Это значит, что не важно, какое большое или маленькое было исходное изображение, время уменьшения до определенного размера будет одинаковым. Я буду приводить примеры на Питоне с библиотекой Pillow, но вы можете получить почти такой же результат с помощью любого языка и библиотек.

>>> from PIL import Image
>>> im = Image.open('pineapple.jpeg'); im.load(); im.size
(2560, 1600)
>>> %time im.resize((256, 170), Image.NEAREST)
Wall time: 0.35 ms

>>> im = Image.open('space.jpeg'); im.load(); im.size
(4928, 3280)
>>> %time im.resize((256, 170), Image.NEAREST)
Wall time: 0.44 ms

В реальности время не совсем константное, поскольку вмешиваются разные факторы вроде кэшей процессора и локальности данных, но даже для в 4 раза большего исходного изображения мы получили замедление лишь на 23%.

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

>>> from PIL import Image
>>> im = Image.open('pineapple.jpeg'); im.load(); im.size
(2560, 1600)
>>> %time im.resize((256, 170), Image.BICUBIC)
Wall time: 33.2 ms

>>> im = Image.open('space.jpeg'); im.load(); im.size
(4928, 3280)
>>> %time im.resize((256, 170), Image.BICUBIC)
Wall time: 130 ms

Для в 4 раза большего исходного изображения время тоже возросло в 4 раза.

Фиксированное ядро

Некоторые приложения и библиотеки для работы с графикой пользуются такой хитростью: они как бы используют для ресайза те же фильтры, что и при ресайзе свертками (бывают, например, билинейный, бикубический и фильтр Ланцош), но при уменьшении изображения не увеличивают ядро фильтра адаптивно. В результате для построения любой точки конечного изображения используется только 4 пикселя исходного изображения при билинейном фильтре, при бикубическом — 16, с 3-лобным фильтром Ланцоша — 36. То есть время работы тоже получается константным относительно исходного размера.

Вот только такой подход работает для уменьшения примерно до 2 раз, а дальше результат мало чем отличается от «ближайшего соседа».

Качественное уменьшение изображений за константное время - 4
Из 4928×3280 в 256×170 с билинейным фильтром с фиксированным ядром.

И говоря «мало чем отличается от „ближайшего соседа“» я имею в виду не только то, что он такой же рваный и зернистый, я имею в виду, что он правда почти совпадает с результатом «ближайшего соседа». Откройте обе картинки в соседних вкладках браузера и попереключайте между ними, картинки почти совпадают. Может даже показаться, что где-то ошибка, что так быть не должно, потому что с фиксированным ядром интерполируется 4 пикселя, а не тупо берется первый попавшийся, и результат должен быть ближе к оригиналу. Но ошибки тут нет и вот почему:

Качественное уменьшение изображений за константное время - 5
Точки, которые будут интерполироваться при уменьшении до 20×13.

Это точки исходного изображения, по которым строится конечное. Их стало больше в 4 раза, но они расположены все в тех же местах, что и при методе ближайшего соседа. То есть скорее всего, мы не получим новой информации об изображении. Можно попытаться еще увеличить количество точек исходного изображения, участвующих в процессе, применив бикубический фильтр, но результат снова будет почти таким же и даже еще чуть-чуть более рваным, потому что в бикубическом фильтре крайние пиксели берутся с отрицательными коэффициентами.

Качественное уменьшение изображений за константное время - 6
Из 4928×3280 в 256×170 с бикубическим фильтром с фиксированным ядром.

Как не сложно догадаться, сложность и время выполнения при использовании фильтров с большим охватом значительно растет, в то время как конечное изображение почти не меняется. Все три следующие примера дают примерно одинаковую картинку, а вот время работы у них отличается до 20 раз.

>>> im = Image.open('space.jpeg'); im.load(); im.size
(4928, 3280)

# Ближайший сосед
>>> %time im.resize((256, 170), Image.NEAREST)
Wall time: 0.441 ms

# Билинейное фиксированное ядро
>>> %time im.transform((256, 170), Image.AFFINE,
                       (im.width / 256, 0, 0, 0, im.height / 170, 0), Image.BILINEAR)
Wall time: 3.62 ms

# Бикубическое фиксированное ядро
>>> %time im.transform((256, 170), Image.AFFINE,
                       (im.width / 256, 0, 0, 0, im.height / 170, 0), Image.BICUBIC)
Wall time: 9.21 ms

Тут я симулировал ресайз с фиксированным ядром с помощью аффинных преобразований. Но некоторые приложения и библиотеки правда делают это: используют для уменьшения более дорогие фильтры, результат которых почти равен методу ближайшего соседа. Так делает OpenCV, так делают браузеры, когда рисуют изображение на канве, так делают видеокарты при текстурировании без mip-уровней. Потому что хоть время и большее, но оно константное относительно разрешения исходного изображения. Ну а качество? Для качества есть свертки или суперсемплинг.

Как исправить

Вы наверное думаете, для чего я вообще вам это все рассказываю, всё же ясно: если нужна скорость — нужно брать «соседа» или фиксированное ядро, если качество — свертки. А дело в том, что, оказывается, уменьшение с фиксированным ядром можно исправить так, что его результат будет радикально лучше. Настолько лучше, что возможно, для ваших задач, этого окажется достаточно и не понадобятся свертки. Причем сложность не просто будет константой относительно размера исходного изображения, это будет та же самая константа, что и при использовании фиксированного ядра.

Качественное уменьшение изображений за константное время - 7
Результат ресайза 4928×3280 в 256×170 за константное время.

Как видите, результат этого алгоритма не идет ни в какое сравнение с разноцветной размазней, получающейся после «ближайшего соседа» или фиксированного ядра. Для примеров к этой статье я намеренно взял довольно большую картинку с мелкой сеткой, с большим количеством деталей (посмотрите на отражение в шлеме астронавта) и очень сильно её уменьшаю. Я сделал все возможное, чтобы на результате вылезло как можно больше артефактов, но алгоритм все равно справляется! Когда я первый раз узнал об этом методе от random1st, подумал, что метод скорее всего дает лишь незначительное улучшение по сравнению с фиксированным ядром, ведь количество задействованных пикселей такое же. Но результат сильно превзошел мои ожидания.

Секрет в том, чтобы брать для обработки не точки, скучковавшиеся по 4 штуки, как при фиксированном ядре, а использовать равномерную сетку в 2 раза большего разрешения, чем должно получиться в итоге. И из неё уже интерполировать конечное изображение.

Качественное уменьшение изображений за константное время - 8
Точки, которые будут использоваться при уменьшении до 20×13.

Как видите, все еще берется довольно мало точек исходного изображения. Но из-за того, что они распределены равномерно, они более репрезентативные. А из-за того, что их ровно в 4 раза больше, они все вносят одинаковый вклад в конечное изображение.

А теперь самое интересное: для использования этого метода не нужно ничего программировать! Все что нужно у вас уже есть. Первым шагом можно сделать равномерную сетку пикселей в 2 раза большего разрешения методом «ближайшего соседа», а на втором шаге сжать её в 2 раза хоть фиксированным фильтром, хоть свертками, хоть суперсемплингом (смотря что есть в вашей библиотеке). Единственное, для сверток я бы посоветовал брать фильтр Хэмминга или бикубический, но не билинейный.

>>> im = Image.open('space.jpeg'); im.load(); im.size
(4928, 3280)

# Пример с не адаптивным ядром
>>> %time im.resize((512, 340), Image.NEAREST)
            .transform((256, 170), Image.AFFINE,
                       (2, 0, 0, 0, 2, 0), Image.BILINEAR)
Wall time: 3.59 ms

# Пример со свертками и фильтром Хэмминга
>>> %time im.resize((512, 340), Image.NEAREST)
            .resize((256, 170), Image.HAMMING)
Wall time: 2.42 ms

# Пример со свертками и бикубическим фильтром
>>> %time im.resize((512, 340), Image.NEAREST)
            .resize((256, 170), Image.BICUBIC)
Wall time: 3.53 ms

# Пример с суперсемплингом
# Результат будет немного отличаться, потому что в OpenCV
# есть ошибка с точностью работы INTER_NEAREST
# см. https://github.com/opencv/opencv/issues/9096
>>> import cv2
>>> im = cv2.imread('space.jpeg')
>>> %time cv2.resize(cv2.resize(im, (512, 340), interpolation=cv2.INTER_NEAREST),
                     (256, 170), interpolation=cv2.INTER_AREA)
Wall time: 0.81 ms

Дальнейшее развитие идеи

Данное улучшение впечатляет, но можно не останавливаться на достигнутом. Кто сказал, что для построения нужно использоваться именно в 2 раза большее изображение? Почему бы не взять в 3 раза или 4 для лучшего качества. Правда невозможно будет использовать ресайз с фиксированным ядром для второго шага, потому что вылезут те же проблемы, от которых мы пытаемся избавиться. А вот свертки или суперсемплинг — пожалуйста. При этом время останется константным, просто константа будет побольше.

Качественное уменьшение изображений за константное время - 9 Качественное уменьшение изображений за константное время - 10
Ресайз из 4928×3280 в 256×170 используя 2x и 4x промежуточные изображения.

Возможно, на таком масштабе различия не сильно видны, но они достаточно сильные. Чтобы их заметить, посмотрите гифку с зумом:

Качественное уменьшение изображений за константное время - 11

Ну и время:

>>> im = Image.open('space.jpeg'); im.load(); im.size
(4928, 3280)

# Пример с 2x промежуточным изображением
>>> %time im.resize((512, 340), Image.NEAREST)
            .resize((256, 170), Image.BICUBIC)
Wall time: 3.53 ms

# Пример с 3x промежуточным изображением
>>> %time im.resize((768, 510), Image.NEAREST)
            .resize((256, 170), Image.BICUBIC)
Wall time: 6.27 ms

# Пример с 4x промежуточным изображением
>>> %time im.resize((1024, 680), Image.NEAREST)
            .resize((256, 170), Image.BICUBIC)
Wall time: 9.23 ms

Как видно, вариант с 2x промежуточным изображением работает за время, примерно равное билинейному фильтру с фиксированным ядром, а вариант с 4x промежуточным изображением за время бикубического. Ну и вообще говоря, можно использовать не целое кол-во точек.

Как сделайте правильный выбор

Возникает вопрос: если этот метод дает настолько лучшие результаты и работает со скоростью фиксированного ядра, зачем вообще использовать фиксированное ядро для уменьшения? У этого метода конечно есть область применимости — его лучше не использовать при уменьшении меньше чем в 2 раза. И это совпадает с границей применимости фиксированного ядра, которое лучше не использовать при уменьшении больше чем в 2 раза. Получается, комбинируя методы, возможно получить ресайз приемлемого качества за фиксированное время при любом масштабе.

И напоследок несколько примеров с другими изображениями. Слева направо:
1) фиксированное ядро, билинейный фильтр (то, что многие используют сейчас)
2) бикубические свертки в качестве эталона
3) этот метод с 2x увеличением
4) этот метод с 4x увеличением

Главное при просмотре помнить, что третье изображение генерируется ровно за такое же время, что и первое, а четвертое хоть и дольше в ≈3 раза, но тоже за константное время и часто до 20 раз быстрее, чем второе.

Еще раз пример из статьи. Изображение 4928×3280 уменьшенное в 19,25 раз.
Качественное уменьшение изображений за константное время - 12Качественное уменьшение изображений за константное время - 13
Качественное уменьшение изображений за константное время - 14Качественное уменьшение изображений за константное время - 15

Эта же картинка, но на этот раз уменьшенная из 600×399, то есть в 2,34 раза.
Такое небольшое уменьшение более сложный случай для данного метода.
Качественное уменьшение изображений за константное время - 16Качественное уменьшение изображений за константное время - 17
Качественное уменьшение изображений за константное время - 18Качественное уменьшение изображений за константное время - 19

Изображение 2560×1600 уменьшенное в 10 раз.
Качественное уменьшение изображений за константное время - 20Качественное уменьшение изображений за константное время - 21
Качественное уменьшение изображений за константное время - 22Качественное уменьшение изображений за константное время - 23

Изображение 4000×2667 уменьшенное в 15,625 раз.
Качественное уменьшение изображений за константное время - 24Качественное уменьшение изображений за константное время - 25
Качественное уменьшение изображений за константное время - 26Качественное уменьшение изображений за константное время - 27

Изображение 2448×3264 уменьшенное в 9,5625 раз.
Качественное уменьшение изображений за константное время - 28Качественное уменьшение изображений за константное время - 29
Качественное уменьшение изображений за константное время - 30Качественное уменьшение изображений за константное время - 31

Изображение 2000×2000 уменьшенное в 7,8125 раз.
Качественное уменьшение изображений за константное время - 32Качественное уменьшение изображений за константное время - 33
Качественное уменьшение изображений за константное время - 34Качественное уменьшение изображений за константное время - 35

Автор: homm

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js