Пропорциональное уменьшение изображения

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

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

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

https://www.youtube.com/watch?v=ytpressru

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

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

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

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

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

{amp}gt;{amp}gt;{amp}gt; im = Image.open('space.jpeg'); im.load(); im.size
(4928, 3280)

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

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

# Бикубическое фиксированное ядро
{amp}gt;{amp}gt;{amp}gt; %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 раза хоть фиксированным фильтром, хоть свертками, хоть бокс-фильтром (смотря что есть в вашей библиотеке). Единственное, для сверток я бы посоветовал брать фильтр Хэмминга или бикубический, но не билинейный.

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

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

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

{amp}gt;{amp}gt;{amp}gt; im = Image.open('space.jpeg'); im.load(); im.size
(4928, 3280)

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

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

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

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

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

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

https://www.youtube.com/watch?v=https:accounts.google.comServiceLogin

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

Примеры

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

Пропорциональное уменьшение изображения

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

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

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

Изображение 2560×1600 уменьшенное в 10 раз.

Изображение 4000×2667 уменьшенное в 15,625 раз.

Изображение 2448×3264 уменьшенное в 9,5625 раз.

Пропорциональное уменьшение изображенияhttps://www.youtube.com/watch?v=ytpolicyandsafetyru

Изображение 2000×2000 уменьшенное в 7,8125 раз.