Compressez une image en un aperçu de 4 Ko

Dans ce défi, vous allez créer un algorithme de compression de prévisualisation d'image. Son objectif est de réduire un fichier image arbitraire en une image d'aperçu de 4 Ko, qui peut être utilisée pour identifier rapidement des images avec très peu de bande passante.

Vous devez écrire deux programmes (ou un programme combiné): un compresseur et un décompresseur. Les deux doivent prendre un fichier ou stdin en entrée et sortir dans un fichier ou stdout. Le compresseur doit accepter une image dans un format d'image sans perte de choix (par exemple PNG, BMP, PPM) et produire un fichier d'au plus 4096 octets . Le décompresseur doit accepter tout fichier généré par le compresseur et produire une image aussi proche que possible de l'entrée. Notez qu'il n'y a pas de limite de taille de code source pour l'encodeur / décodeur, vous pouvez donc être créatif dans votre algorithme.

Restrictions:

• Pas de tricherie'. Vos programmes ne peuvent pas utiliser d'entrées cachées, stocker des données sur Internet, etc. Il vous est également interdit d'inclure des fonctionnalités / données se rapportant uniquement à l'ensemble d'images de notation.

• Pour les bibliothèques / outils / intégrés, vous êtes autorisé à utiliser des opérations de traitement d'image génériques (mise à l'échelle, flou, transformation de l'espace colorimétrique, etc.), mais pas les opérations de décodage / codage / compression d'image (sauf pour l'entrée du compresseur et la sortie du décompresseur). La compression / décompression générique est également interdite . Il est prévu que vous implémentiez votre propre compression pour ce défi.

• Les dimensions de l'image produite par le décompresseur doivent correspondre exactement à celles du fichier d'origine remis au compresseur. Vous pouvez supposer que les dimensions de l'image ne dépassent pas 2 ¹⁶ dans les deux sens.

• Votre compresseur doit fonctionner sur un PC grand public en moins de 5 minutes, et le décompresseur doit fonctionner en moins de 10 secondes pour toute image de l'ensemble ci-dessous.

Notation

Pour faciliter la vérification rapide et la comparaison visuelle, veuillez inclure un album d'images sans perte du corpus de test après compression en utilisant votre réponse.

Votre compresseur sera testé à l'aide du corpus d'images suivant :

Vous pouvez télécharger toutes les images dans un fichier zip ici .

Votre score sera l' indice de similitude structurelle moyen de votre compresseur sur toutes les images. Nous utiliserons l'open source dssimpour ce défi. Il est facilement construit à partir des sources, ou si vous êtes sur Ubuntu, il a également un PPA. Il est préférable de noter votre propre réponse, mais si vous ne savez pas comment créer des applications C et que vous n'exécutez pas Debian / Ubuntu, vous pouvez laisser quelqu'un d'autre marquer pour vous. dssimattend l'entrée / sortie en PNG, donc convertissez d'abord votre sortie en PNG si vous sortez dans un format différent.

Pour rendre la notation indolore, voici un script Python d'aide rapide, utilisation 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)))

Le score le plus bas l'emporte.

Python avec PIL, score 0,094218

Compresseur:

#!/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 < 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 >= 5*60-10:
            break
        size = image_bytes(img, scale)
        if size > total_size:
            high = scale
        elif size < total_size:
            low = scale
            if best is None or total_size-size < 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("Compressing {}".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("Exception with {}".format(f))
            traceback.print_exc()
            continue

Décompresseur:

#!/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("Decompressing {}".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("Exception with {}".format(f))
            traceback.print_exc()
            continue

Les deux scripts prennent l'entrée via des arguments de ligne de commande, comme deux répertoires (entrée et sortie), et convertissent toutes les images dans le répertoire d'entrée.

L'idée est de trouver une taille qui correspond à moins de 4 Ko et a le même rapport d'aspect que l'original, et d'utiliser un filtre Lanczos pour obtenir une qualité aussi élevée que possible de l'image sous-échantillonnée.

Album Imgur d'images compressées, après redimensionnement aux dimensions d'origine

Sortie du script de notation:

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

Java (vanille, devrait fonctionner avec java 1.5+), note 0,672

Il ne génère pas de bons scores dssim mais, à mon avis, il produit des images plus conviviales pour l'homme ...

Album: http://imgur.com/a/yL31U

Sortie du script de notation:

Comparing corpus/1 - starry.png to test/1 - starry.png... 2.3521
Comparing corpus/2 - source.png to test/2 - source.png... 1.738
Comparing corpus/3 - room.png to test/3 - room.png... 0.1829
Comparing corpus/4 - rainbow.png to test/4 - rainbow.png... 0.0633
Comparing corpus/5 - margin.png to test/5 - margin.png... 0.4224
Comparing corpus/6 - llama.png to test/6 - llama.png... 0.204
Comparing corpus/7 - kid.png to test/7 - kid.png... 0.36335
Comparing corpus/8 - julia.png to test/8 - julia.png... 0.05
Average score: 0.672

La chaîne de compression:

1. if filter data has already been generated goto step 6
2. create sample images from random shapes and colours
3. take sample patches from these sample images
4. perform k-clustering of patches based on similarity of luminosity and chomanosity.
5. generate similarity ordered lists for each patch as compared to the other patches.
6. read in image
7. reduce image size to current multiplier * blocksize
8. iterate over image comparing each blocksize block against the list of clustered luminosity patches and chromanosity patches, selecting the closest match
9. output the index of the closet match from the similarity ordered list (of the previous block) (repeat 8 for chromanosity)
10. perform entropy encoding using deflate.
11. if output size is < 4096 bytes then increment current multiplier and repeat step 7
12. write previous output to disk.

Pour décompresser, gonfler puis lire les index des blocs et sortir le patch correspondant dans le fichier de sortie, puis redimensionner aux dimensions d'origine.

Malheureusement, le code est trop volumineux pour stackoverflow et peut donc être trouvé à https://gist.github.com/anonymous/989ab8a1bb6ec14f6ea9

Courir:

Usage: 
       For single image compression: java CompressAnImageToA4kibPreview -c <INPUT IMAGE> [<COMPRESSED IMAGE>]
       For multiple image compression: java CompressAnImageToA4kibPreview -c <INPUT IMAGES DIR> [<COMPRESSED IMAGE DIR>]
       For single image decompression: java CompressAnImageToA4kibPreview -d <COMPRESSED IMAGE> [<DECOMPRESSED IMAGE>
       For multiple image decompression: java CompressAnImageToA4kibPreview -d <COMPRESSED IMAGE DIR> [<DECOMPRESSED IMAGES DIR>]

If optional parameters are not set then defaults will be used:
       For single image compression, compressed image will be created in same directory are input image and have '.compressed' file extension.
       For multiple image compression, compressed images will be created in a new 'out' sub directory of <INPUT IMAGES DIR> and have '.compressed' file extensions.
       For single image decompression, decompressed image will be created in same directory are input image and have '.out.png' file extension.
       For multiple image decompression, decompressed images will be created a new 'out' sub directory of <COMPRESSED IMAGE DIR> and have '.png' file extensions.

La première fois que cette application est exécutée, les fichiers requis seront générés et enregistrés dans un répertoire relatif au répertoire de travail d'exécution. Cela peut prendre quelques minutes. Pour les exécutions ultérieures, cette étape n'aura pas besoin d'être effectuée.