homm Oct 26 2017 at 10:53

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

8 min

28K

High performance*Algorithms*Image processing*

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

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

Уменьшение изображения 4928×3280 до 256×170 ближайшим соседом.

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

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

Точки, которые попадут в конечное изображение размером 20×13.

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

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

Уменьшение с 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 раз, а дальше результат мало чем отличается от «ближайшего соседа».

Из 4928×3280 в 256×170 с билинейным фильтром с фиксированным ядром.

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

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

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

Из 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-уровней. Потому что хоть время и большее, но оно константное относительно разрешения исходного изображения. Ну а качество? Для качества есть свертки.

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

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

Результат ресайза 4928×3280 в 256×170 за константное время.

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

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

Точки, которые будут использоваться при уменьшении до 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 для лучшего качества. Правда невозможно будет использовать ресайз с фиксированным ядром для второго шага, потому что вылезут те же проблемы, от которых мы пытаемся избавиться. А вот свертки — пожалуйста. При этом время останется константным, просто константа будет побольше.

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

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

Ну и время:

>>> 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 раза. Получается, комбинируя методы, возможно получить ресайз приемлемого качества за фиксированное время при любом масштабе.

Важное дополнение

В комментариях vintage верно указывает, что этот метод правильно называть суперсемплингом. Суперсемплинг часто используется в играх для устранения алиасинга. По сути игровая сцена — это изображение бесконечного разрешения, потому что мы могли бы отрисовать её в любом разрешении. Для суперсемплинга сцена рисуется в большем разрешении чем нужно и несколько соседних пикселей усредняются в один. То есть аналогия полная. Но это не отменяет факта, что такой метод очень редко применяется в ПО несмотря на его достоинства.

Примеры

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

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

Еще раз пример из статьи. Изображение 4928×3280 уменьшенное в 19,25 раз.