Skompresuj obraz do podglądu 4 KiB

W tym wyzwaniu będziesz tworzyć algorytm kompresji podglądu obrazu. Jego celem jest zredukowanie dowolnego pliku obrazu do obrazu podglądu 4 KiB, którego można użyć do szybkiej identyfikacji obrazów o bardzo małej przepustowości.

Musisz napisać dwa programy (lub jeden program łączony): kompresor i dekompresor. Oba muszą przyjmować plik lub standardowe wejście jako dane wejściowe i wyjściowe do pliku lub standardowego wejścia. Kompresor musi zaakceptować jeden obraz w wybranym głównym formacie bezstratnym (np. PNG, BMP, PPM) i wygenerować plik o maksymalnej wielkości 4096 bajtów . Dekompresor musi zaakceptować dowolny plik wygenerowany przez kompresor i wysyłać obraz jak najbliżej wejścia. Pamiętaj, że koder / dekoder nie ma limitu rozmiaru kodu źródłowego, więc możesz być kreatywny w swoim algorytmie.

Ograniczenia:

• Bez oszukiwania'. Twoje programy nie mogą używać ukrytych danych wejściowych, przechowywania danych w Internecie itp. Zabronione jest również włączanie funkcji / danych dotyczących tylko zestawu obrazów punktowanych.

• Dla bibliotek / narzędzi / Wbudowana ins wy są wolno używać rodzajowe operacje przetwarzania obrazu (skalowanie, rozmycie, kolor transformacji przestrzeni, itp), ale nie obraz dekodowanie / kodowanie / kompresja operacje (oprócz wejścia kompresor i dekompresor wyjściu). Ogólna kompresja / dekompresja jest również niedozwolona . Planowane jest wdrożenie własnej kompresji dla tego wyzwania.

• Wymiary obrazu wysyłanego przez dekompresor muszą dokładnie odpowiadać wymiarom oryginalnego pliku przekazanego kompresorowi. Możesz założyć, że wymiary obrazu nie przekraczają 2 ¹⁶ w obu kierunkach.

• Kompresor musi działać na przeciętnym komputerze osobistym w mniej niż 5 minut, a dekompresor musi działać w mniej niż 10 sekund dla dowolnego obrazu z poniższego zestawu.

Punktacja

Aby pomóc w szybkiej weryfikacji i porównaniu wizualnym, dołącz bezstratny album zdjęć korpusu testowego po kompresji, używając swojej odpowiedzi.

Twój kompresor zostanie przetestowany przy użyciu następującego zbioru obrazów :

Możesz pobrać wszystkie obrazy w pliku zip tutaj .

Twój wynik będzie średnim wskaźnikiem podobieństwa strukturalnego sprężarki na wszystkich obrazach. Do dssimtego wyzwania będziemy używać oprogramowania typu open source . Jest łatwy do zbudowania ze źródła lub jeśli jesteś na Ubuntu, ma również PPA. Preferowane jest, jeśli zdobędziesz własną odpowiedź, ale jeśli nie wiesz, jak budować aplikacje C i nie uruchamiasz Debiana / Ubuntu, możesz pozwolić komuś innemu zdobyć dla ciebie. dssimoczekuje wejścia / wyjścia w formacie PNG, więc najpierw przekonwertuj dane wyjściowe na format PNG, jeśli dane wyjściowe są w innym formacie.

Aby sprawić, by punktowanie było bezbolesne, oto szybki skrypt Pythona pomocnika, użycie 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)))

Najniższy wynik wygrywa.

Python z PIL, wynik 0,094218

Kompresor:

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

Dekompresor:

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

Oba skrypty pobierają dane wejściowe za pomocą argumentów wiersza poleceń jako dwa katalogi (wejściowy i wyjściowy) i konwertują wszystkie obrazy w katalogu wejściowym.

Chodzi o to, aby znaleźć rozmiar, który mieści się poniżej 4 KiB i ma taki sam współczynnik kształtu jak oryginał, i użyć filtra Lanczos, aby uzyskać jak najwyższą jakość obrazu o zmniejszonej próbce.

Album Imgur skompresowanych obrazów po zmianie rozmiaru do oryginalnych wymiarów

Wynik skryptu oceniania:

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 (wanilia, powinna współpracować z java 1.5+), wynik 0,672

Nie generuje szczególnie dobrych wyników dssim, ale moim zdaniem tworzy bardziej przyjazne dla ludzi obrazy ...

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

Wynik skryptu oceniania:

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ńcuch kompresji:

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.

Aby zdekompresować, napompować, a następnie odczytać indeksy bloków i wyprowadzić odpowiednią poprawkę do pliku wyjściowego, a następnie zmienić rozmiar do oryginalnych wymiarów.

Niestety kod jest zbyt duży, aby można go było przepełnić, dlatego można go znaleźć na stronie https://gist.github.com/anonymous/989ab8a1bb6ec14f6ea9

Biegać:

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.

Przy pierwszym uruchomieniu tej aplikacji wymagane pliki zostaną wygenerowane i zapisane w katalogu w odniesieniu do katalogu roboczego wykonywania. To może zająć parę minut. W przypadku kolejnych wykonań ten krok nie będzie musiał zostać wykonany.