Compactar uma imagem para uma visualização de 4 KiB

Neste desafio, você criará um algoritmo de compactação de visualização de imagem. Seu objetivo é reduzir um arquivo de imagem arbitrário para uma imagem de visualização de 4 KiB, que pode ser usada para identificar rapidamente imagens com muito pouca largura de banda.

Você deve escrever dois programas (ou um programa combinado): um compressor e um descompressor. Ambos devem pegar um arquivo ou stdin como entrada e enviar para um arquivo ou stdout. O compressor deve aceitar uma imagem em um formato de imagem convencional sem perdas de escolha (por exemplo, PNG, BMP, PPM) e gerar um arquivo com no máximo 4096 bytes . O descompactador deve aceitar qualquer arquivo gerado pelo compressor e gerar uma imagem o mais próximo possível da entrada. Observe que não há limite de tamanho do código-fonte para o codificador / decodificador, para que você possa ser criativo em seu algoritmo.

Restrições:

• Sem 'trapaça'. Seus programas não podem usar entradas ocultas, armazenamento de dados na Internet etc. Você também está proibido de incluir recursos / dados pertencentes apenas ao conjunto de imagens de pontuação.

• Para bibliotecas / ferramentas / built-ins que você está autorizado a usar genéricos operações de processamento de imagem (scaling, borrar, cor espaço de transformação, etc), mas não imagem decodificação / codificação / compressão de operações (exceto para a entrada do compressor e descompressor de saída). A compactação / descompactação genérica também não é permitida . Pretende-se implementar sua própria compactação para esse desafio.

• As dimensões da imagem gerada pelo descompactador devem corresponder exatamente às do arquivo original fornecido ao compressor. Você pode supor que as dimensões da imagem não excedam 2 ¹⁶ em qualquer direção.

• O seu compressor deve funcionar em um PC de consumo médio em menos de 5 minutos e o descompactador deve funcionar em menos de 10 segundos para qualquer imagem no conjunto abaixo.

Pontuação

Para ajudar na verificação rápida e na comparação visual, inclua um álbum de imagem sem perdas do corpus de teste após a compactação usando sua resposta.

Seu compressor será testado usando o seguinte corpus de imagens :

Você pode baixar todas as imagens em um arquivo zip aqui .

Sua pontuação será o índice de similaridade estrutural médio para o seu compressor em todas as imagens. Usaremos o código aberto dssimpara esse desafio. É facilmente construído a partir da fonte ou, se você estiver no Ubuntu, também possui um PPA. É preferível que você avalie sua própria resposta, mas se você não sabe como criar aplicativos C e não executa o Debian / Ubuntu, pode deixar que outra pessoa faça sua avaliação. dssimespera entrada / saída em PNG, então converta sua saída em PNG primeiro, se você produzir em um formato diferente.

Para tornar a pontuação indolor, aqui está um script Python auxiliar rápido, uso 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)))

Menor pontuação ganha.

Python com PIL, pontuação 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 < 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

Descompressor:

#!/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

Ambos os scripts recebem entrada por meio de argumentos de linha de comando, como dois diretórios (entrada e saída), e convertem todas as imagens no diretório de entrada.

A idéia é encontrar um tamanho que caiba abaixo de 4 KiB e tenha a mesma proporção que o original e use um filtro Lanczos para obter o máximo de qualidade possível da imagem reduzida na amostra.

Álbum de imagens compactadas, após redimensionar para as dimensões originais

Pontuação do script de saída:

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 (baunilha, deve funcionar com java 1.5 ou superior), pontuação 0,672

Não gera pontuações dssim particularmente boas, mas, a meu ver, produz imagens mais amigáveis ​​ao ser humano ...

Álbum: http://imgur.com/a/yL31U

Pontuação do script de saída:

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

A cadeia de compressão:

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.

Para descompactar, inflar e, em seguida, ler os índices do bloco e enviar o patch correspondente ao arquivo de saída e redimensionar para as dimensões originais.

Infelizmente, o código é muito grande para o stackoverflow, portanto, pode ser encontrado em https://gist.github.com/anonymous/989ab8a1bb6ec14f6ea9

Para correr:

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.

Na primeira vez em que esse aplicativo é executado, os arquivos necessários serão gerados e salvos em um diretório relativo ao diretório de trabalho de execução. Isso pode levar alguns minutos. Para execuções subseqüentes, esta etapa não precisará ser executada.