Як я зробив найшвидший ресайз зображень. Частина 0

Привіт, мене звати Саша, я написав найшвидший ресайз зображень для сучасних процесорів х86. Я так стверджую, оскільки всі інші бібліотеки, які я зумів знайти і протестувати, виявилися повільніше. Я зайнявся цим завданням, коли працював над оптимізацією ресайза картинок на льоту Uploadcare. Ми вирішили відкрити код і в результаті з'явився проект Pillow-SIMD. Будь-хто з легкістю може використовувати його в додатку на мові Python.
Будь-код виконується на конкретному залозі і гарну оптимізацію можна домогтися, лише розуміючи його архітектуру. Всього я планую випустити 4 або 5 статей, в яких розповім як застосовувати знання архітектури заліза для оптимізації реальної задачі. Своїм прикладом я хочу спонукати вас оптимізувати інші прикладні задачі. Перші дві статті вийдуть протягом тижня, решта — по мірі готовності.
завдання
Під «ресайзом зображень» я розумію зміна розмірів зображення з допомогою ресемплинга методом згорток. Ресемплінг проводиться над масивом 8-бітних RGB пікселів в пам'ять, без урахування декодування і кодування зображень, однак з урахуванням виділення пам'яті під кінцеве зображення і з урахуванням підготовки коефіцієнтів, необхідних для конкретної операції.
Ось так суворо. Жодних трюків (зразок декодування з джипега зображення меншого розміру) і ніякого комбінування алгоритмів, що тільки чесне вимірювання роботи конкретного алгоритму. Трюки і оптимізації приватних випадків можна застосувати пізніше, вони не предмет розгляду цієї серії статей.
… з допомогою ресемплинга методом згорток. Що?
Щоб було зрозуміло, що конкретно потребувало оптимізації, я розповім, що таке ресемплінг звірками. Згортка (правильно казати згортка дискретних значень, оскільки пікселі зображення дискретні) — це дуже проста математична операція. У нас є якийсь ряд значень №1 (коефіцієнти) і ряд значень №2 (дані, в нашому випадку інтенсивність каналів пікселів). Результат згортки цих двох рядів буде сума добутків всіх членів попарно. Ось так просто — сума творів. Матан закінчився, не встигнувши початися.

Залишилося зрозуміти, як саме ця операція пов'язана з ресайзом. Ряд значень №2 — це ряд пікселів вихідного зображення. Ряд значень №1 — це коефіцієнти, що виходять з фільтра. Фільтр — це така функція, яка визначає, як саме ми будемо згортати значення. Може бути ви помічали у віконці ресайза в Фотошопі або іншому графічному редакторі випадаюче меню з фільтрами — білінійна, бікубічний, іноді Ланцош. Це і є цей фільтр. А ось що вийшло в результаті згортки значення — це інтенсивність одного каналу одного пікселя кінцевого зображення. Тобто щоб отримати зображення розміром M×N пікселів, нам потрібно зробити M×N×C операцій згортки, де З — кількість колірних каналів. Так, порахувати весь піксель однією операцією не вийде, значення різних каналів незалежні і повинні вважатися окремо.
Опції фільтрів не безмежні, їх значення не дорівнюють нулю лише у центральній частині: для билинейного фільтру це діапазон значень від -1 до 1; для бикубического від -2 до 2, для Ланцоша від -3 до + 3 (правда бувають і інші різновиди Ланцоша).

Ці числа називають вікном фільтра, т. к. фільтр застосовується тільки в цьому діапазоні, а за його межами дорівнює нулю. Відповідно ряд вихідних пікселів, необхідний для згортки, береться в радіусі розміром у вікно фільтра помноженому на коефіцієнт зменшення (або на одиницю, якщо відбувається збільшення). Думаю, це краще пояснити на прикладі. Нам потрібно зменшити зображення шириною 2560 пікселів до ширини 2048, використовуючи бікубічний фільтр. Припустимо, ми хочемо знайти значення 33-го пікселя кінцевого зображення. У бикубического фільтра розмір вікна дорівнює двом, а коефіцієнт зменшення виходить 2560/2048 = 1,25, тому нам потрібно буде взяти рядок пікселів вихідного зображення від
floor((33 - 2) × 1,25)
до
ceil((33 + 2) × 1,25)
. Тобто з 38-го по 44-й піксель. Для цих же пікселів вираховуються значення коефіцієнтів.
До цього моменту я говорив про ряд коефіцієнтів і ряді пікселів, випускаючи з уваги факт, що зображення — це взагалі-то двовимірна структура. І начебто за логікою, потрібно згортати не лінію, а якусь область початкового зображення. Але одне з властивостей згорток полягає в тому, що операцію можна провести окремо по вертикалі і по горизонталі, зробивши два проходи. Грубо кажучи, це дозволяє зменшити складність однієї згортки з O(n2) до O(2n) (насправді менше, але все одно істотно).
Чому все ж згортки
Взагалі, фраза «ресайз зображення» несе в собі мінімум інформації про те, що потрібно зробити. Вона говорить, що ми повинні отримати зображення кінцевого розміру, використовуючи оригінальне із збереженням геометрії зображених об'єктів. Але використовувати початкове зображення можна по-різному. Можна наприклад для кожного кінцевого пікселя поставити у відповідність один піксел з вихідного і взяти його без змін. Це називається метод найближчого сусіда. Картинка виходить грубою, рваною, неприємною:

Так відбувається тому, що в кінцевому зображенні була використана дуже мала частина вихідних пікселів (на наведеному вище прикладі менше одного відсотка). Інформацію з тих точках, які не потрапили в кінцеве зображення, ми втратили.
А ось як виглядає ресемплінг з допомогою згорток:

Ресемплінг з допомогою згорток правильно враховує внесок кожного вихідного пікселя в кінцеве зображення. Він універсальний, оскільки дає однаково хороший і передбачуваний результат для широкого діапазону коефіцієнтів масштабування, не містить спотворень геометрії на локальному рівні (з застереженням, що використовується фільтр, який не дає таких спотворень, оскільки деякі фільтри все ж дають). І взагалі, він весь такий правильний і хороший зі всіх сторін, крім однієї: продуктивності.
Pillow
Pillow — це бібліотека для роботи із зображеннями на мові Python. У Uploadcare Pillow використовувався ще до того, як я прийшов в команду. Тоді мені це здалося дивним — робота з зображеннями була однією з основних завдань, навіщо було брати для неї бібліотеку, зав'язану на мову. Чи Не краще взяти той же ImageMagick, у якого тонна функцій, якими користуються мільйон розробників, вже в ньому, напевно, все повинно бути добре з продуктивністю. По закінченні декількох років, можу сказати, що це була удача як для мене, так і для Pillow. Як з'ясувалося, продуктивність обох бібліотек на старті була приблизно однаковою, але я дуже сумніваюся, що у мене вистачило б сил зробити для ImageMagick щось таке, що я зробив для Pillow.
Pillow — це форк дуже старої бібліотеки PIL. Історично, для ресайза в PIL не використовувалися згортки. Перша реалізація ресайза на згортках в PIL з'явилася у версії 1.1.3 і була доступна при використанні фільтра ANTIALIAS, назва якого підкреслювало те, що інші фільтри використовували менш якісні алгоритми. У мережі дотепер можна часто зустріти вже не актуальні рекомендації використовувати при ресайзе в PIL (і в Pillow, як приймачі) тільки фільтр ANTIALIAS.
На жаль, у ANTIALIAS була досить низька продуктивність. Я поліз в вихідний код, щоб подивитися, що можна зробити, і виявилося, що реалізація ресайза для ANTIALIAS (тобто згортки), може бути використана і з іншими фільтрами. А сама константа ANTIALIAS відповідає фільтру Ланцоша, у якого велике вікно (±3), і тому він досить повільний. Найперша оптимізація, яку я хотів зробити — включити згортки для билинейного і бикубического фільтрів. Так стало б можливим у себе в додатку використовувати більш дешевий бікубічний фільтр (з вікном ±2) і не занадто втратити в якості.
Далі мені було цікаво подивитися на код самого ресайза. Я без зусиль знайшов його в цьому модулі. І хоч я і пишу в основному на пітоні, я відразу помітив кілька сумнівних місць з точки зору продуктивності. Після декількох оптимізація я отримав приріст в 2,5 рази (це буде описано в наступній статті). Потім я став експериментувати з SIMD, переводити всі обчислення на цілі числа, агресивно розгортати цикли і групувати обчислення. Завдання було надзвичайно цікавою, в голові завжди були ще пара ідей, як поліпшити продуктивність. Я занурювався в кролячу нору все глибше і глибше, періодично перевіряючи чергову гіпотезу.
Поступово код ставав все більше, а швидкість все вище. Частина напрацювань віддавалася назад в Подушку. Але SIMD-код було важко перенести, тому що він написаний для конкретної архітектури, а Pillow — платформна бібліотека. Тому було вирішено зробити не багатоплатформовий форк Pillow-SIMD. Версії Pillow-SIMD повністю відповідають версіями оригінальної Pillow і додають прискорення деяких операцій.
В останніх версіях Pillow-SIMD з AVX2 ресайз працює від 15 до 30 разів швидше, ніж в початковому PIL. Як я вже говорив на самому початку, це найшвидша реалізація якісного ресайза, яку мені вдавалося протестувати. Можна подивитися сторінку, на якій зібрані результати бенчмарків різних бібліотек.

Що мене радує в випадку з Pillow і Pillow-SIMD, це те, що це реальні бібліотеки, які реально використовувати навіть починаючому розробнику. Це не шматок коду, опублікований на Stack Overflow, який незрозуміло куди встромити. І не «примітивні блоки», з яких як з конструктора потрібно збирати кожну операцію. І навіть не складна C++ бібліотека з заплутаним інтерфейсом, яка компілюється півгодини. Це одна строчка установки, одна строчка імпорту бібліотеки, одна строчка завантаження зображення і, «гей, мам, дивись, я користуюся самим швидким ресайзом у своєму додатку».
Виміри продуктивності
У статтях я буду викладати виміри продуктивності у вигляді таблиці, в якій початкове зображення роздільною здатністю 2560×1600 пікселів ресайзится до дозволів 320x200, 2048x1280 і 5478x3424 з використанням билинейного, бикубического і фільтра Ланцоша (тобто всього 9 операцій). Початкове зображення взято досить велика, щоб не повністю поміститися в кеш процесора третього рівня. При цьому фактичний вміст зображення не має значення з точки зору продуктивності, можна ресайз хоч порожній білий аркуш, хоч чорний, хоч фоточку вашого кота. Ось приклад результатів бібліотеки Pillow версії 2.6, до будь-яких оптимізацій.
Scale 2560×1600 RGB image
to 320x200 bil 0.08927 s 45.88 Mpx/s
to 320x200 bic 0.13073 s 31.33 Mpx/s
to 320x200 lzs 0.16436 s 24.92 Mpx/s
to 2048x1280 bil 0.40833 s 10.03 Mpx/s
to 2048x1280 bic 0.45507 s 9.00 Mpx/s
to 2048x1280 lzs 0.52855 s 7.75 Mpx/s
to 5478x3424 bil 1.49024 s 2.75 Mpx/s
to 5478x3424 bic 1.84503 s 2.22 Mpx/s
to 5478x3424 lzs 2.04901 s 2.00 Mpx/s

Другий стовпець тут цей час у секундах, а третій — пропускна здатність вихідного зображення для даної операції. Тобто, якщо операція зайняла 0,2 с, то пропускна здатність 2560×1600/0,2 = 20,48 мегапікселів в секунду.
Початкове зображення ресайзится до дозволу 320×200 за 164 мілісекунди. Ну що, начебто непогано. Може бути взагалі не потрібно оптимізувати, залишити як є? Ну, якщо згадати, що дозвіл фоток з мобільних телефонів зараз в середньому має розмір 12 мегапікселів, то все виходить не так райдужно. Фотка з айфона буде зменшуватися півсекунди без урахування розпакування. Враховуючи інші операції, в хвилину ви можете обробити ≈80 картинок, а в годину — близько 5000. Поточна навантаження на наш сервіс близько 130 тисяч запитів на годину. Нам знадобилося 26 AWS c4.large серверів, що працюють на межі, щоб впоратися з таким навантаженням. У реальності ж у нас задіяно всього 4 сервера, навантаження на які гарячі годинник близько 40%.
Якщо б такий ефект вдалося екстраполювати до масштабів планети і замінити весь код, який займається ресайзом картинок, на більш ефективний, користь була б величезною. Десятки тисяч заощаджених серверів, сотні кіловат електрики. А це вже одна мільйонна від світового споживання. Так можна було б врятувати планету!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.