Compress an image to a 4 KiB preview In this challenge you will be creating an image preview compression algorithm. It's goal is to
reduce an arbitrary image file to a 4 KiB preview image, that can be used to quickly identify images
with very little bandwidth.

You must write two programs (or one combined program): a compressor and a decompressor. Both must
take a file or stdin as input, and output to a file or stdout. The compressor must accept one image
in a mainstream lossless image format of choice (e.g. PNG, BMP, PPM), and output a file of at
most 4096 bytes. The decompressor must accept any file generated by the compressor, and output an image as close as possible to the input. Note that there is no source code size limit for the encoder/decoder, so you
can be creative in your algorithm.

Restrictions:


No 'cheating'. Your programs may not use hidden inputs, storing data on the internet, etc. You are
also forbidden from including features / data pertaining only to the set of scoring images. 
For libraries / tools / built-ins you are allowed to use generic image processing operations
(scaling, blurring, color space transformation, etc), but not image decoding / encoding /
compression operations (except for compressor input and decompressor output). Generic compression / decompression is also disallowed. It is intended
that you implement your own compression for this challenge.
The dimensions of the image output by the decompressor must exactly match those of the original
file given to the compressor. You may assume that the image dimensions do not exceed
216 in either direction.
Your compressor must run on an average consumer PC in under 5 minutes, and the decompressor must
run in under 10 seconds for any image in the set below.


Scoring

To help quick verification and visual comparison, please include a lossless image album of the test corpus after compression using your answer.

Your compressor will be tested using the following corpus of images:










You can download all images in a zip file here. 

Your score will be the average structural similarity index for your compressor on all the images. We will be using the open source dssim for this challenge. It is easily built from source, or if you're on Ubuntu it also has a PPA. It is preferred if you score your own answer, but if you do not know how to build C applications and you do not run Debian/Ubuntu, you can let someone else score for you. dssim expects input/output in PNG, so convert your output to PNG first if you output in a different format.

To make scoring painless, here's a quick helper Python script, usage python score.py corpus_dir compressed_dir:

import glob, sys, os, subprocess

scores = []
for img in sorted(os.listdir(sys.argv[1])):
    ref, preview = (os.path.join(sys.argv[i], img) for i in (1, 2))
    sys.stdout.write("Comparing {} to {}... ".format(ref, preview))
    out = subprocess.check_output(["dssim", ref, preview]).decode("utf-8").split()[0]
    print(out)
    scores.append(float(out))

print("Average score: {:.6f}".format(sum(scores) / len(scores)))




Lowest score wins.
Python with PIL, score 0.094218

Compressor:
#!/usr/bin/env python
from __future__ import division
import sys, traceback, os
from PIL import Image
from fractions import Fraction
import time, io

def image_bytes(img, scale):
    w,h = [int(dim*scale) for dim in img.size]
    bio = io.BytesIO()
    img.resize((w,h), Image.LANCZOS).save(bio, format='PPM')
    return len(bio.getvalue())

def compress(img):
    w,h = img.size
    w1,w2 = w // 256, w % 256
    h1,h2 = h // 256, h % 256
    n = w*h
    total_size = 4*1024 - 8 #4 KiB minus 8 bytes for
                            # original and new sizes
    #beginning guess for the optimal scaling
    scale = Fraction(total_size, image_bytes(img, 1))
    #now we do a binary search for the optimal dimensions,
    # with the restriction that we maintain the scale factor
    low,high = Fraction(0),Fraction(1)
    best = None
    start_time = time.time()
    iter_count = 0
    while iter_count &lt; 100: #scientifically chosen, not arbitrary at all
        #make sure we don't take longer than 5 minutes for the whole program
        #10 seconds is more than reasonable for the loading/saving
        if time.time() - start_time &gt;= 5*60-10:
            break
        size = image_bytes(img, scale)
        if size &gt; total_size:
            high = scale
        elif size &lt; total_size:
            low = scale
            if best is None or total_size-size &lt; best[1]:
                best = (scale, total_size-size)
        else:
            break
        scale = (low+high)/2
        iter_count += 1
    w_new, h_new = [int(dim*best[0]) for dim in (w,h)]
    wn1,wn2 = w_new // 256, w_new % 256
    hn1, hn2 = h_new // 256, h_new % 256
    i_new = img.resize((w_new, h_new), Image.LANCZOS)
    bio = io.BytesIO()
    i_new.save(bio, format='PPM')
    return ''.join(map(chr, (w1,w2,h1,h2,wn1,wn2,hn1,hn2))) + bio.getvalue()

if __name__ == '__main__':
    for f in sorted(os.listdir(sys.argv[1])):
        try:
            print(&quot;Compressing {}&quot;.format(f))
            with Image.open(os.path.join(sys.argv[1],f)) as img:
                with open(os.path.join(sys.argv[2], f), 'wb') as out:
                    out.write(compress(img.convert(mode='RGB')))
        except:
            print(&quot;Exception with {}&quot;.format(f))
            traceback.print_exc()
            continue

Decompressor:
#!/usr/bin/env python
from __future__ import division
import sys, traceback, os
from PIL import Image
from fractions import Fraction
import io

def process_rect(rect):
    return rect

def decompress(compressed):
    w1,w2,h1,h2,wn1,wn2,hn1,hn2 = map(ord, compressed[:8])
    w,h = (w1*256+w2, h1*256+h2)
    wc, hc = (wn1*256+wn2, hn1*256+hn2)
    img_bytes = compressed[8:]
    bio = io.BytesIO(img_bytes)
    img = Image.open(bio)
    return img.resize((w,h), Image.LANCZOS)
    

if __name__ == '__main__':
    for f in sorted(os.listdir(sys.argv[1])):
        try:
            print(&quot;Decompressing {}&quot;.format(f))
            with open(os.path.join(sys.argv[1],f), 'rb') as img:
                decompress(img.read()).save(os.path.join(sys.argv[2],f))
        except:
            print(&quot;Exception with {}&quot;.format(f))
            traceback.print_exc()
            continue

Both scripts take input via command line arguments, as two directories (input and output), and convert all images in the input directory.
The idea is to find a size that fits under 4 KiB and has the same aspect ratio as the original, and use a Lanczos filter to get as high of a quality out of the downsampled image as possible.
Imgur album of compressed images, after resizing to original dimensions
Scoring script output:
Comparing corpus/1 - starry.png to test/1 - starry.png... 0.159444
Comparing corpus/2 - source.png to test/2 - source.png... 0.103666
Comparing corpus/3 - room.png to test/3 - room.png... 0.065547
Comparing corpus/4 - rainbow.png to test/4 - rainbow.png... 0.001020
Comparing corpus/5 - margin.png to test/5 - margin.png... 0.282746
Comparing corpus/6 - llama.png to test/6 - llama.png... 0.057997
Comparing corpus/7 - kid.png to test/7 - kid.png... 0.061476
Comparing corpus/8 - julia.png to test/8 - julia.png... 0.021848
Average score: 0.094218