<jupyter_start><jupyter_text>JPEG Basics<jupyter_code>import itertools
from collections import Counter

import numpy as np
import matplotlib.pyplot as plt
from skimage import data
from skimage.util import view_as_blocks
from skimage.color import rgb2gray
from skimage.metrics import peak_signal_noise_ratio as psnr, structural_similarity as ssim
from scipy.fftpack import dct, idct

import rle
import huffman
import zigzag<jupyter_output><empty_output><jupyter_text>CompressingMost of the compression is done during Huffman encoding. To be effective, it is necessary that the coefficients are distributed very unevenly. You can achieve this by applying a discrete cosine transform (DCT).  PrepareTake an image and split it to blocks with a size 8x8. These blocks will be used for the application of DCT. Why 8? Some statistics here: 4 is bad, 8 is good enough and 16 is similar to 8.<jupyter_code>block_shape = (8, 8)

chelsea = data.chelsea()
chelsea = np.rint(rgb2gray(chelsea) * 255).astype(np.uint8)

height = chelsea.shape[0] // block_shape[0] * block_shape[0]
width = chelsea.shape[1] // block_shape[1] * block_shape[1]

chelsea = chelsea[:height, :width]
plt.imshow(chelsea, cmap='gray')
plt.show()
def filesize(array):
    kb = 1024
    
    bytes_count = len(bytearray(array))
    return str(bytes_count // kb) + ' kb'
filesize(chelsea)<jupyter_output><empty_output><jupyter_text>Apply discrete cosine transform and perform quantizationA discrete cosine transform (DCT) expresses a finite sequence of data points in terms of a sum of cosine functions oscillating at different frequencies. See explanations [here](https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/).From DCT we receive some coefficients. Most important are in upper left corner.We use more bits to store important coefficients than to store unimportant ones. This is quantization.<jupyter_code>def dct2d(array):
    return dct(dct(array, norm='ortho', axis=-1), norm='ortho', axis=-2)

def idct2d(array):
    return idct(idct(array, norm='ortho', axis=-1), norm='ortho', axis=-2)<jupyter_output><empty_output><jupyter_text>Common JPEG quantization matrix. Just divide DCT coefficients to matrix values.<jupyter_code>quantization_table = np.array([
    [16,  11,  10,  16,  24,   40,   51,   61 ],
    [12,  12,  14,  19,  26,   58,   60,   55 ],
    [14,  13,  16,  24,  40,   57,   69,   56 ],
    [14,  17,  22,  29,  51,   87,   80,   62 ],
    [18,  22,  37,  56,  68,   109,  103,  77 ],
    [24,  35,  55,  64,  81,   104,  113,  92 ],
    [49,  64,  78,  87,  103,  121,  120,  101],
    [72,  92,  95,  98,  112,  100,  103,  99 ]])
def quantize_block(block):
    coefs = dct2d(block) / quantization_table
    
    return np.rint(coefs + 127).clip(0, 255).astype(np.uint8)
def quantize(image):
    view = view_as_blocks(image, block_shape)
    coefs = np.zeros_like(view, dtype=np.uint8)

    for row in range(view.shape[0]):
        for col in range(view.shape[1]):
            coefs[row][col] = quantize_block(view[row][col])
    
    return coefs<jupyter_output><empty_output><jupyter_text>Take some block of size 8x8<jupyter_code>plt.imshow(chelsea[0 : 8, 0 : 8], cmap='gray')
plt.show()
coefs = quantize(chelsea.copy())<jupyter_output><empty_output><jupyter_text>This is quantized dct coefficients.<jupyter_code>coefs[0][0].astype(np.int8) - 127<jupyter_output><empty_output><jupyter_text>Most of them are zeros. Nonzero values are in upper left corner.<jupyter_code>plt.hist(coefs.flatten().astype(np.int8) - 127, bins=255)
plt.show()<jupyter_output><empty_output><jupyter_text>Prepare to huffman coding: zigzag scan and run-length encodingWe use a zigzag scan to place all zeros in a row and then apply run-length encoding (RLE). If we don't do this, huffman coding will perform worse.<jupyter_code>coefs_zigzaged = zigzag.scan(coefs.reshape(-1, 8, 8))
coefs_zigzaged_rled = rle.code(coefs_zigzaged)
plt.hist(coefs_zigzaged_rled, bins=255)
plt.show()<jupyter_output><empty_output><jupyter_text>Apply huffman coding<jupyter_code>codes = huffman.make_codes(Counter(coefs_zigzaged_rled))
length, coded = huffman.code(coefs_zigzaged_rled, codes)<jupyter_output><empty_output><jupyter_text>We made the image seven times smaller!<jupyter_code>filesize(coded), len(bytearray(chelsea)) / len(bytearray(coded))<jupyter_output><empty_output><jupyter_text>Decompressing  Decode using huffman, rle and zigzag algroithms<jupyter_code>coefs_zigzaged_rled = huffman.decode(coded, codes, length)
coefs_zigzaged = rle.decode(coefs_zigzaged_rled)
coefs = zigzag.inverse(np.array(coefs_zigzaged)).reshape(height // block_shape[0], width // block_shape[1], *block_shape)<jupyter_output><empty_output><jupyter_text>Dequantize coefficients and apply inverse discrete cosine transform<jupyter_code>def restore_block(block):
    coefs = block.astype(np.int8) - 127

    return np.rint(idct2d(coefs * quantization_table)).clip(0, 255).astype(np.uint8)
def restore(coefs):
    image = np.zeros((height, width), dtype=np.uint8)
    view = view_as_blocks(image, block_shape)

    for row in range(view.shape[0]):
        for col in range(view.shape[1]):
            view[row][col] = restore_block(coefs[row][col])
    
    return image
decompressed = restore(coefs)
plt.imshow(decompressed, cmap='gray')
plt.show()<jupyter_output><empty_output><jupyter_text>Let's see how well we were able to save the image<jupyter_code>psnr(chelsea, decompressed), ssim(chelsea, decompressed)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11468556888404216, 'fraction_numerical': 0.040530716103235186, 'mean_word_length': 5.1692825112107625, 'pattern_counts': {'":': 0, '<': 53, '<?xml version=': 0, '>': 53, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '13', 'dir': 'jupyter-structured-clean-dedup', 'id': '432470', 'license': 'MIT', 'n_tokens_mistral': 2166, 'n_tokens_neox': 1957, 'n_words': 490, 'path': 'jpeg_basics.ipynb', 'repo_name': 'egorchistov/jpeg', 'size': '5502'}