Квантування зображень

Квантування — зменшення кольорів зображення (wiki). Звичайно, зараз мало кому це необхідно, але завдання сама по собі цікава.


Квантизированная Лена привертає увагу

Наприклад, старий добрий формат GIF використовує палітру, максимум 256 кольорів. Якщо ви захочете зберегти серію своїх селфи як gif-анімацію (кому б це треба було), то перше, що вам, а точніше програмі, яку ви будете для цього використовувати, треба буде зробити – створити палітру. Можна використовувати статичну палітру, наприклад web-safe colors, алгоритм квантування вийти дуже простим і швидким, але результат буде «не дуже». Можна створити оптимальну палітру кольорів зображення, що дасть результат найбільш візуально схожий на оригінал.

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

Далі вас чекає нудне і незрозуміле розповідь про метод медіанного перетину, алгоритмом розсіювання помилок (шуму квантування) за Флойдом-Стейнбергом (і не тільки), особливості колірного сприйняття людського ока, а так само трохи гівнокоду.

ІсторіяДавним-давно, коли Nokia була теплою і лампової переважала на ринку смартфонів, а власники смартфонів гордо називали себе «смартфонщики», в ті стародавні часи писав я простенькі програмки на python для series60. На одну з них недавно натрапив копирсаючись у архівах. GifTool – програмка для створення gif-анімації з набору картинок. У ній я реалізував квантизацию методом медіанного перетину, алгоритм стиснення LZW, вся структура файлу створювалася самостійно, для незмінних на наступному слайді пікселів використовувалася прозорість, щоб зменшити підсумковий розмір файлу. Захотілося мені освіжити свою пам'ять, подивитися – як же вона працювала. Відкрив код і… Це відчуття, коли ти не можеш розібратися в своєму говнокоде десятирічної давності. Про PEP8 я тоді не знав, тому читаність коду була трохи менше ніж ніякої (тоді мені подобався мінімалізм, як і багатьом починаючим програмістам). Розплакався, поплевался, отрефакторил в PyCharm, розібрався як реалізував метод медіанного перетину, нашвидкуруч накидав «брудний» скрипт. Працює! Палітра складається, зображення на виході виходить стерпне. І тут мене закусило – чи зможу я досягти кращих результатів, щоб картинка візуально була якомога ближче до оригіналу.

Отже – метод медіанного перетину. Він простий до неподобства. Першим ділом треба з усіх унікальних кольорів зображення скласти RGB куб. Далі розсікти його по найдовшій стороні. Наприклад, діапазон червоного у нас від 7 до 231 (довжина 231-7=224), зеленого від 32 до 170 (довжина 170-32=138), синього від 12 до 250 (довжина 250-12=238), значить, будемо «різати» куб по синій стороні. Отримані сегменти так само розсікає по довгій стороні і т. д. поки не одержимо 256 сегментів. Для кожного сегмента вирахувати середній колір – так ми і отримаємо палітру.
Пара картинок майже в тему, для наочності

Що тут можна покращити? Перше, що приходить в голову – обчислювати середній колір не тупо склавши всі кольори і розділивши на їх кількість [ sum(color) / count(color) ], а з урахуванням того, скільки разів кожен колір зустрічається в зображенні. Тобто кожен колір множимо на кількість його примірників у зображенні, отримані значення складаємо, результат ділимо на кількість входжень в зображенні всіх кольорів даного сегмента [ sum(color * total) / sum(total) ]. В результаті, найбільш часто зустрічаються кольору мають пріоритет при обчисленні, але й рідкісні кольори вносять свої корективи, тому палітра виходить краще, візуальне відхилення квітів менше. Для кращих результатів бажано ще враховувати гаму, але я залишив це на потім. Друге не так явно – медіанне переріз зовсім не враховує особливості сприйняття кольору людським оком. Відтінки зеленого ми сприймаємо набагато краще відтінків синього. Я вирішив виправити це непорозуміння і «сплющил» куб – довжини сторін помножил на коефіцієнти з цієї статті. В результаті по зеленій і червоній стороні перерізів стало більше, по синій менше. Такого рішення я більше ніде не зустрічав (може погано шукав), але результат на обличчя.

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

Є ще один спосіб поліпшити якість одержуваного зображення – розсіювання помилок. Тут теж все досить просто – з індексованого кольору віднімаємо відповідний колір палітри, отримуємо помилку, розсіюємо її по сусідніх пікселях у відповідності з певною формулою (шаблоном), найбільш відома формула Флойда-Стейнберга, її я і використав. При розсіюванні помилок розмиваються різкі переходи між кольорами, і візуально здається, що зображення містить більше відтінків (квітів). Якщо цікаво – про розсіювання помилок докладно і цікаво можна почитати тут. Цей алгоритм я так вирішив допилити, помножившпи помилку на все ті ж коефіцієнти, як виявилося, це була дуже хороша ідея – так як перерізів по синьому діапазону стало менше, в ньому виходила значна помилка, і без коригування помилки коефіцієнтами розсіювання вносило багато «шуму».

Ось тепер можна знову повернутися до індексування. Розсіюванням помилок ми змінюємо кольору пікселів і отримуємо такі, яких немає в нашому RGB-кубі (нагадаю, він складений виключно з кольорів зображення). Тепер не можна просто подивитися в якому сегменті знаходиться колір, щоб призначити індекс. Рішення знайшлося відразу – пошук найближчого кольору в палітрі. В дану формулу я підставив все ті ж коефіцієнти. Порівнюючи результати підбору кольору палітри за індексом сегменту в який входить початковий колір і результати пошуку найближчого кольору, наочно побачив, що найближчий колір часто виявляється в сусідньому сегменті. Якщо вихідний колір знаходиться ближче до центру сегмента – то індекс сегмента відповідає індексу кольору в палітрі, але чим ближче вихідний колір до країв сегмента, тим більше ймовірність, що найближчий колір опиниться в сусідньому сегменті. Загалом, єдиний правильний шлях індексування – пошук найближчого кольору в палітрі. Але у пошуку є мінус – він повільний, дуже повільний. Писати числодробилку на python погана ідея.

Ну ось, хотів пояснити в двох словах, а вийшла ціла купа незрозумілою писанини. Сподіваюся, код я пишу краще, ніж пояснюю, тому ось ссилочка на github. Код кілька разів переписувався, спочатку удосконалювався алгоритм, поки результат мене не влаштував, потім виявилося, що він жере забагато оперативы при обробці фотографій (спочатку тестував на невеликих картинках), довелося перенести RGB-куб, медіанне переріз і карту пікселів в базу даних sqlite). Скрипт працює дуже повільно, але результат виходить краще, ніж квантування засобами PIL/Pillow і GIMP'ом (в ньому ця операція називається індексування).

Наочна демонстрація:Оригінал


Результат квантування в GIMP, оптимальна палітра на 256 кольорів + розмивання кольору за Флойдом-Стенбергу (нормальне)


Результат квантування PIL/Pillow
image.convert(mode='P', dither=PIL.Image.FLOYDSTEINBERG, palette=PIL.Image.ADAPTIVE, colors=256)



Результат квантування моїм кодом


На що звернути увагу: розсіювання помилки у GIMP сильно «шумить», PIL/Pillow створює не дуже оптимальну палітру і практично не розсіює помилки (різкі переходи між кольорами).
Якщо не бачите різницю — подивіться інші приклади на github.

P. S.: є чудова програма Color Quantizer, яка справляється з цим завданням краще і швидше, тому практичного сенсу мій скрипт не має, зроблений виключно з «спортивного» інтересу.
Джерело: Хабрахабр

0 коментарів

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