{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

# Image compression by singular value decomposition

## Problem

Run the Python code below or simply click [here](https://sagecell.sagemath.org/?q=fcwmdf).

# get the image
import urllib.request
URL = "https://raw.githubusercontent.com/jephianlin/LA-notebook/main/incrediville-side.jpg"
urllib.request.urlretrieve(URL, "incrediville-side.jpg")

# import original image
import numpy as np
from PIL import Image

r = 10
img = Image.open('incrediville-side.jpg')
x,y = img.size
img = img.resize((x // r, y // r)).convert("L")

# compressed image
arr = np.array(img)
u,s,vh = np.linalg.svd(arr)

# choose your k
k = 50
arr_compressed = (u[:,:k] * s[:k]).dot(vh[:k,:])
img_compressed = Image.fromarray(arr_compressed.astype('uint8'), 'L')

# show compression rate and the images
concat = Image.new("L", (2 * img.width, img.height))
concat.paste(img, (0,0))
concat.paste(img_compressed, (img.width,0))
print("k: %d"%k)
print("compression rate: %.2f"%(k * (img.width + img.height + 1.0) / img.width / img.height))
concat

The image on the left is the original image, while the one on the right is an compressed image, with the compression rate printed. Try some different `k` to see if you can notice the difference.

## Thought

Every grayscale image is stored as a matrix (or array) in computer. The singular value decomposition decompose a matrix into the sum of several matrices, ordered by their "importance". By dropping the non-imporant onces, we may reduce the file size.

*This note can be found at Course website > Learning resources.*