30
8
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.
does the compressed picture have to be viewable? – Eumel – 2016-01-28T14:51:55.460
2@Eumel You can consider the decompressor as a viewer. So no, your compressed format can be arbitrary and is entirely up to you. Only after decompression a viewable image has to come out. – orlp – 2016-01-28T15:23:26.433
7
You may assume that the image dimensions do not exceed 2^32 in either direction.
Isn't this a little excessive? This means I have to use up 16 bytes to store a pair of (x,y) coordinates. Few image files have dimensions of more than 2^16 (65536) pixels in either direction, and 2^11 is sufficient for all the images in the corpus. – Peter Olson – 2016-01-29T02:22:30.260@PeterOlson I'll change it to
2^16
. – orlp – 2016-01-29T13:28:37.860@orlp The rules state that the decompressor must take less than ten seconds to decode an image. The idea I have will potentially take a few minutes to generate reference files that will be used in subsequent calls to the decompressor. i.e. it is a once off activity similar to "installing" an application. Would this solution be disqualified? – Moogie – 2016-02-10T03:40:02.980
@Moogie That is allowed iff those reference files are unrelated to any of the image files in the corpus. – orlp – 2016-02-10T09:19:17.000
@orlp well yes, they will be related... i.e. it would create data used for the compression of the files, however they will not be derived from the files at all... (if i could generate the image files then i would do so directly :P ) – Moogie – 2016-02-10T10:54:21.490
Is the 5-minute rule for the compression for any single image, or for the entire corpus? – Mego – 2016-02-10T19:57:28.303
@Mego Single image. – orlp – 2016-02-10T20:58:16.593
To be a bit pedantic DSSIM actually measures dis-similarity : 1/SSIM - 1, but as you can see it is very related to SSIM. For a good match, SSIM values should be close to 1 and DSSIM should instead be close to 0. However dis-similarity does not have any upper bound as SSIM can get arbitrarily close to 0. – mathreadler – 2016-02-22T15:28:48.153
Am I allowed to make a 1x1 pixel preview image? – 12Me21 – 2017-01-25T12:55:37.133
@12Me21 No. "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." – orlp – 2017-01-25T13:08:49.607