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

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

14.02.17 8:17 •
homm •
# 321744 •
Хабрахабр •
66 •
14800

- такий же як Forbes, тільки краще.

Здравствуйте, меня зовут Саша, я написав найшвидший ресайз зображень для сучасних х86 процесорів. Я так стверджую, оскільки всі інші бібліотеки, які я зумів знайти і протестувати, виявилися повільніше. Я зайнявся цим завданням, коли працював над оптимізацією ресайз картинок на льоту в Uploadcare. Ми вирішили відкрити код і в результаті з'явився проект Pillow-SIMD. Будь-який бажаючий з легкістю може використовувати його в додатку на мові Python.

Будь-код виконується на конкретному залозі і хорошою оптимізації можна домогтися, тільки розуміючи його архітектуру. Всього я планую випустити 4 або 5 статей, в яких розповім як застосовувати знання архітектури заліза для оптимізації реального завдання. Своїм прикладом я хочу спонукати вас оптимізувати інші прикладні завдання. Перші дві статті вийдуть протягом тижня, решта - в міру готовності.

Під «ресайз зображень» я розумію зміна розмірів зображення за допомогою Ресемплінг методом згорток. Ресемплінг проводиться над масивом 8-бітних RGB пікселів в пам'ять, без урахування декодування і кодування зображень, однак з урахуванням виділення пам'яті під кінцеве зображення і з урахуванням підготовки коефіцієнтів, необхідних для конкретної операції.

Ось так строго. Ніяких трюків (на кшталт декодування з джіпег зображення меншого розміру) і ніякого комбінування алгоритмів, тільки чесне вимір роботи конкретного алгоритму. Трюки і оптимізації окремих випадків можна застосувати пізніше, вони не предмет розгляду цієї серії статей.

... за допомогою Ресемплінг методом згорток. Що?

Щоб було зрозуміло, що конкретно потребувало оптимізації, я розповім, що таке Ресемплінг пакунками. Згортка (правильно говорити згортка дискретних значень. Тому пікселі зображення дискретні) - це дуже проста математична операція. У нас є якийсь ряд значень №1 (коефіцієнти) і ряд значень №2 (дані, в нашому випадку інтенсивність каналів пікселів). Результат згортки цих двох рядів буде сума творів всіх членів попарно. Ось так просто - сума творів. Матан закінчився, не встигнувши початися.

Функції фільтрів не нескінченні, їх значення не дорівнюють нулю лише в центральній частині: для білінійної фільтра це діапазон значень від -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 (n?) До O (2n) (насправді менше, але все одно істотно).

Чому все ж згортки

Взагалі, фраза «ресайз зображення» несе в собі мінімум інформації про те, що потрібно зробити. Вона каже, що ми повинні отримати зображення кінцевого розміру, використовуючи оригінальне, зі збереженням геометрії зображених об'єктів. Але використовувати вихідне зображення можна по-різному. Можна наприклад для кожного кінцевого пікселя поставити у відповідність один піксель з вихідного і взяти його без змін. Це називається метод найближчого сусіда. Картинка виходить грубою, рваною, неприємною:

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

А ось як виглядає Ресемплінг за допомогою згорток:

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

Pillow - це бібліотека для роботи з зображеннями на мові Python, що розвивається спільнотою на чолі з Alex Clark і Eric Soroos. У 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, переводити всі обчислення на цілі числа, агресивно розгортати цикли і групувати обчислення. Завдання було надзвичайно цікавою, в голові завжди були ще пара ідей, як поліпшити продуктивність. Я занурювався в кролячу нору все глибше і глибше, періодично перевіряючи чергову гіпотезу.

Поступово код ставав все більше, а швидкість все вище. Частина напрацювань віддавалася назад в Pillow. Але SIMD-код було важко перенести, тому що він написаний для конкретної архітектури, а Pillow - кроссплатформенная бібліотека. Тому було вирішено вдіяти не багатоплатформовий форк Pillow-SIMD. Версії Pillow-SIMD повністю відповідають версіями оригінальної Pillow і додають прискорення деяких операцій.

В останніх версіях Pillow-SIMD з AVX2 ресайз працює від 15 до 30 разів швидше, ніж в початковому PIL. Як я вже говорив на самому початку, це найшвидша реалізація якісного ресайз, яку мені вдавалося протестувати. Можна подивитися сторінку. на якій зібрані результати бенчмарків різних бібліотек.

заміри продуктивності

Другий стовпець тут цей час в секундах, а третій - пропускна здатність вихідного зображення для даної операції. Тобто, якщо операція зайняла 0,2 с, то пропускна здатність буде 2560? 1600 / 0,2 = 20,48 мегапікселів в секунду.

Якби такий ефект вдалося екстраполювати до масштабів планети і замінити весь код, який займається ресайз картинок, на більш ефективний, користь була б величезною. Десятки тисяч зекономлених серверів, сотні кіловат електрики. А це вже одна мільйонна від світового споживання. Так можна було б врятувати планету!

а з чого раптом такий пафос?
швидкий - судження оцінне, на треба бути найшвидшим, це ні до чого, потрібно бути досить швидким щоб вирішувати поставленими перед мовою завданнями, і Python з ними справляється, останнім часом все краще і успішніше, а якщо немає, то існує можливість додати йому швидкості і має велике значення, іншими словами він для своїх завдань цілком хороший, так як якщо до вас в руки потрапив молоток не всі перетворилося в цвяхи

Можливо я чогось не зрозумів, але я взяв opencv і просто викликав resize:
2560 x 1600 -> 320 x 200 bicubic = 3 ms
А у вас SIMD SSE4 - 7.7 ms, а SIMD AVX2 - 5.7 ms, тобто в 2-2.5 рази повільніше.

Справа в тому, що в opencv для ресайз не використовується метод згорток. Там використовується той же метод, що і в Pillow до версії 2.7 для bilinear і bicubic і той же метод, що використовується в елементі canvas в браузерах. Відсилаю вас почитати статтю ресайз картинок в браузері. Все дуже погано. Відмінність мінімальне - при зменшенні зображення, вікно не збільшується на коефіцієнт зменшення, як в пакунках. Але це радикально впливає на якість і швидкість. Для прикладу я візьму ту ж картинку. що в статті (7000. 2926> 512. 214).

Як бачите, він набагато ближче до nearest neighbor. Залежно від завдання ви можете розглядати такий алгоритм або вважати його неприпустимим.

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

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

Кожен піксель після горизонтальної згортки стає комбінацією декількох сусідніх пікселів по горизонталі. Наступний прохід вертикальної згортки комбінує між собою вже не пікселі вихідного зображення, а ці «комбінації по кілька пікселів». Скажімо в фільтрі 5x5 якщо нас цікавить кут (-2, 2) то на етапі горизонтальної згортки ми порахуємо піксель p_horizontal [2] = weighted_sum ([-2,2], [-1,2], [0,2], [ 1,2], [2,2]) а потім підставимо в p = weighted_sum (p_horizontal [-2], [-1], [0], [1], [2]); нескладно бачити що в цю суму увійде і [-2.2] з якимось вагою.

Це працює не для всіх можливих 2D згорток, а тільки для спеціального їх підкласу званого згортками з «сепарабельном» ядрами. На щастя для ресайз майже всі ядра сепарабельном.

Спасибі, здається зрозумів)

При вертикальній згортку ми «додамо» пікселі з вертикальною «лінійки» з потрібними коефіцієнтами, в кожному з яких вже підсумувати його горизонтальна «лінійка». І плюс «своя» лінійка вже врахована. Так, все супер.

Єдине що - якщо докопатися до коефіцієнтів, там може виявитися деякий косяк.

Наприклад, я хочу взяти фільтр 3х3 для простоти, і крайні пікселі взяти з коефіцієнтом 0.4. Тоді після горизонтальної згортки ми додамо 0.4 для крайніх елементів в нижній лінійці, а при вертикальній ми додамо вже 0.4 * 0.4 = 0.16, тобто квадрат коефіцієнта у нас буде. Тоді як логічніше, напевно, використовувати квадратний корінь (типу пропорційно відстані). Якщо фільтр не білінійну, то там звичайно віддалі зовсім не пропорційно, але я до того, що все одно коефіцієнти цієї матриці треба б перерахувати при такому методі буде :)