SVDImageCompression

A variation of SVD based image compression algorithm. SSVD(Shuffled SVD)

В ході роботи над алгоритмом було розроблено спершу звичайний SVD алгоритм, а потім і розширений SSVD із простим інтерфейсом у вигляді функції, котра стискає будь яке зображення із заданим рангом та розміром блоків.

Дані, на яких проводились експерименти

У своїй роботі автори узагальнюють алгоритм до квадратних, чорно-білих зображень. В результаті роботи було реалізовано метод стискання зображень будь якого розміру та навіть кольорових зображень, хоча, як було виявлено пізніше SVD(SSVD) не надто добре підходить до кольорових зображень.

Алгоритм на вході приймає матрицю зображення, а також кілька додаткових параметрів:

1. mode - “grayscale” чи “rgb”. Режим роботи: чорно-білі або кольорові зображення
2. block_size - розмір блоків для операції перемішування(п. 1 опису алгоритму)
3. rank - ранг матриці, до котрої ми хочемо стиснути початкову

На виході ми отримаємо матрицю стисненого зображення.

Опис експерименту

Для експерименту була вибрана відома фотографія Lena, котра дуже часто наводиться у прикладах зі стисканням зображень і також присутня в оригінальній роботі, тому в результаті цього було зручно і легко порівняти власні результати та ті, котрі отримали автори статті.

Приклад виклику функції для SSVD стискання:

from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
import svd_algo.compress_image as ci
# Open the image and convert it to numpy.arrray
img = Image.open('test_image.jpg')
img = np.array(img)
# Compress the rgb image with rank=30 and size of blocks=16
compressedImage = ci.compress_image(
coloredImg, 
mode='rgb', 
block_size=16, 
rank=30
)
# Display the compressed image
plt.figure(figsize=(12,6))
plt.imshow(compressedImage);

У репозиторії є jupyter-notebooks, у котрих покроково показана реалізації та використання кожного методу(звичайного SVD, чорно-білого SSVD, кольорового SSVD) а також есперименти та порівняння, котрі проводились(папка examples).

Початкове зображення:

Порівняння стискання чорно-білих зображень за допомогою SVD, SSVD(block size=8) та SSVD(block size=16)

Порівняння стискання кольорового зображення за допомогою SVD та SSVD(block size=16)

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

Після цього я спробував записати ці матриці у файл у бінарному вигляді(можливість бібліотеки numpy). Результати(значення в кілобайтах):

Весь код цього порівняння є у файлі examples/CompareQualityAndSize.ipynb
Багато прикладів стискання різних зображень та роботи із ними є у файлах: BasicSVDImageCompression.ipynb, ColoredSVDImageCompression.ipynb, ExtendedSVDImageCompression.ipynb

Висновки

В результаті роботи над алгоритмом стискання зображень було детально вивчено базовий алгоритм SVD та його застосування у різних сферах. Я розібрався із бібліотеками numpy, matplotlib та PIL. Навчився працювати із зображеннями, їх “трансформуванням” у звичайні матриці, розбиттю кольорового зображення на різні “шари”(червоний, зелений та синій) та подальшою обробкою. Написано відповідну реалізацію алгоритму, описану у оригінальній статті, а також зроблено вдосконалення алгоритму для роботи із будь якими зображеннями.
Найбільшу складність викликало математичне усвідомлення SVD алгоритму, його подальша реалізація та те, що автори статті наводять усі приклади для чорно-білих, квадратних зображень і потрібно було самостійно робити узагальнення роботи алгоритму для будь якого зображення.
Незрозумілим залишилось bit allocation strategy та uniform quantization. Через брак інформації не зрозуміло до кінця як це працює і як реалізувати ці ідеї.