243
90
Note: Anders Kaseorg has been awarded the accept for now, to draw attention to his great answer, but the challenge is by no means over! I will award a 1000 point bounty to anyone who takes the top score without using built-in compression.
Below is a 386x320 png representation of van Gogh's Starry Night.
Your goal is to reproduce this image as closely as possible, in no more than 1024 bytes of code. For the purposes of this challenge, the closeness of images is measured by the squared differences in RGB pixel values, as explained below.
This is code-challenge. Scores are calculated using the validation script below. The lowest score wins.
Your code must obey the following restrictions:
- It must be a complete program
- It must output an image in a format that can be read by the validation script below, running on my machine. The script uses Python's PIL library, which can load a wide variety of file formats, including png, jpg and bmp.
- It must be completely self-contained, taking no input and loading no files (other than importing libraries, which is allowed)
- If your language or library includes a function that outputs Starry Night, you are not allowed to use that function.
- It should run deterministically, producing the same output every time.
- The dimensions of the output image must be
386x320 - For the avoidance of doubt: valid answers must use programming languages as per the usual PPCG rules. It must be a program that outputs an image, not just an image file.
It is likely that some submissions will themselves be generated by code. If this is the case, please include in your answer the code that was used to produce your submission, and explain how it works. The above restrictions only apply to the 1kB image-generating program that you submit; they don't apply to any code used to generate it.
Scoring
To calculate your score, take your output image and the original above and convert the RGB pixel values to floating point numbers ranging from 0 to 1. The score of a pixel is (orig_r-img_r)^2 +(orig_g-img_g)^2 + (orig_b-img_b)^2, i.e. the squared distance in RGB space between the two images. The score of an image is the sum of the scores of its pixels.
Below is a Python script that performs this calculation - in the case of any inconsistency or ambiguity, the definitive score is the one calculated by that script running on my machine.
Note that the score is calculated based on the output image, so if you use a lossy format that will affect the score.
The lower the score the better. The original Starry Night image would have a score of 0. In the astronomically unlikely event of a tie, the answer with the most votes will determine the winner.
Bonus objectives
Because the answers were dominated by solutions using built-in compression, I awarded a series of bounties to answers that use other techniques. The next one will be a bounty of 1000 points, to be awarded if and when an answer that does not use built-in compression takes the top place overall.
The previously awarded bonus bounties were as follows:
A 100 point bounty was awarded to nneonneo's answer, for being the highest-scoring answer that did not use built-in compression at the time. It had 4852.87 points at the time it was awarded. Honourable mentions go to 2012rcampion, who made a valiant attempt to beat nneonneo using an approach based on Voronoi tesselation, scoring 5076 points, and to Sleafar, whose answer was in the lead until near the end, with 5052 points, using a similar method to nneonneo.
A 200 point bounty was awarded to Strawdog's entry. This was awarded for being an optimization-based strategy that took the lead among non-built-in-compression answers and held it for a week. It scored 4749.88 points using an impressively clever method.
Scoring/validation script
The following Python script should be placed in the same folder as the image above (which should be named ORIGINAL.png) and run using a command of the form python validate.py myImage.png.
from PIL import Image
import sys
orig = Image.open("ORIGINAL.png")
img = Image.open(sys.argv[1])
if img.size != orig.size:
print("NOT VALID: image dimensions do not match the original")
exit()
w, h = img.size
orig = orig.convert("RGB")
img = img.convert("RGB")
orig_pix = orig.load()
img_pix = img.load()
score = 0
for x in range(w):
for y in range(h):
orig_r, orig_g, orig_b = orig_pix[x,y]
img_r, img_g, img_b = img_pix[x,y]
score += (img_r-orig_r)**2
score += (img_g-orig_g)**2
score += (img_b-orig_b)**2
print(score/255.**2)
Technical note: Objective measures of image similarity are a tricky thing. In this case I've opted for one that's easy for anyone to implement, in full knowledge that much better measures exist.
Leaderboard
var QUESTION_ID=69930,OVERRIDE_USER=21034;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+))(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;body{text-align:left!important}#answer-list,#language-list{padding:10px;width:400px;float:left}table thead{font-weight:700}table td{padding:5px}<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Score</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
Nathaniel
Posted 2016-01-23T15:16:57.587
Reputation: 6 641
5On Windows I had trouble installing the python requirements. A safer option is to use pillow (
pip unistall PIL, thenpip install pillow) and change the first line tofrom PIL import Image. – mınxomaτ – 2016-01-23T16:17:56.017@mınxomaτ I've changed that line of code. (I have never consciously installed pillow but ways of importing Image work on my machine and appear to give the same answer.) – Nathaniel – 2016-01-23T16:20:25.217
1Can the program read a file if the combined file size + 1 byte is less than 1kB? Alternatively, can the program read its own source code? – orlp – 2016-01-23T19:14:11.003
@orlp no, no loading of files is permitted regardless of their size. But reading your own source is fine. – Nathaniel – 2016-01-24T01:20:42.783
1This is essentially the same similarity metric as PSNR, correct? – Damian Yerrick – 2016-01-24T04:50:17.437
2@tepples other than going in the opposite direction and not being logarithmic, yes :) – hobbs – 2016-01-24T16:11:14.417
I don't think that you'll "feel like" awarding the bounty until my answer becomes outvoted, will you? :p – LegionMammal978 – 2016-01-26T12:20:06.690
@LegionMammal978 by "highest-scoring" I meant best score according to the rules of this challenge, not votes. (Amended.) I voted for your answer! – Nathaniel – 2016-01-26T12:33:14.793
Would an SVG or HTML file be considered a 'program' ? – dronus – 2016-01-26T12:53:14.623
@dronus no, not unless (a) those formats are programming languages according to the PPCG rules, and (b) you can run them to produce an image in a raster format that can be read by PIL.
– Nathaniel – 2016-01-26T13:01:03.180Given that the top four answers to this question seem to demonstrate an inverse relationship between their calculated score and their actual resemblance to the original painting, I think your scoring system may be broken.
– Ajedi32 – 2016-01-26T19:55:23.7501
@Ajedi32 oh, I expected that to happen! I tried to post a version where the scoring system was based on human judgement (via voting) but it was deemed to be an "art contest" and closed. Doing it by least-squares is a fun challenge, but if we wanted the results to actually look like the image, there isn't really any other way than to rely on human judgement.
– Nathaniel – 2016-01-27T00:05:28.0336I'm surprised that not a single answer has tried working with greyscale output yet. Averaging the channels in each pixel gives a score of something like 2800, and having only to compress a third of the data would introduce less error on top of that. – Martin Ender – 2016-01-28T10:16:05.417
3@MartinBüttner you could probably do even better by weighting a greyscale image by the average bluish colour of the image. I hadn't thought of this. – Nathaniel – 2016-01-28T10:29:29.510
3@Nathaniel hasn't been said enough, but this question is so awesome! ;-) – Pierre Arlaud – 2016-01-28T10:33:25.417
@Nathaniel Possibly, but I'm not sure it's worth it because then you probably also need more code to output a 3-channel image. – Martin Ender – 2016-01-28T10:36:26.220
@Nathaniel following your comment here, if you post a future challenge that rules out built in compression, it would interesting to see a score calculation that measures contrast in addition to colour similarity.
– trichoplax – 2016-01-28T13:48:16.810@trichoplax yeah, I've been thinking about how best to do that. It's actually kind of hard to come up with a good measure that's both easy for people to understand and not too expensive to compute. – Nathaniel – 2016-01-28T14:22:52.430
@Nathaniel I commented here because I couldn't find you in [chat] but there are lots of helpful people there. If you can, pop in for a longer discussion :) – trichoplax – 2016-01-28T15:49:27.817
2
A metric that measures similarity in complexity might be more interesting. e.g. x264's psychovisual optimizations and adaptive quantization try to preserve energy in the source, because "detail" looks better than blurring, even if it's the wrong detail. SSIM is a widely-used visual quality metric. It's much more complex to compute than sum-of-squared-errors (PSNR). x264's tuning for max-SSIM (rather than the default max human visual quality) is
– Peter Cordes – 2016-01-29T03:57:23.873--aq-mode 2 --no-psy, so SSIM still doesn't measure what psy optimizes for.x265's docs are good, and summarize what psy is doing there (similar to x264): psy = preserve the energy of the source image in the encoded image at the expense of compression efficiency. psy-rdoq = favoring higher energy in the reconstructed image (regardless of source energy). With these options at 0, the encoder mostly just blurs parts of frames that are hard to encode. (It's a video codec, so when they say "difficult motion", they mean big residuals that have lots of energy after motion compensation.)
– Peter Cordes – 2016-01-29T04:00:37.967Is the term "objectively" defined anywhere here? It seems like an important part of the question. – bmm6o – 2016-01-29T16:38:58.487
@trichoplax I understand how the scoring is "objective", but I read this in the title as describing the program's implementation, not the scoring methodology. Also c.f. the comment to ndenarodev's answer: "for actually drawing objects, thus filling 'objectively' term in challenge", with 6 upvotes. It seems there's some agreement that his program is "objective", but it don't see an interpretation of the word that applies. – bmm6o – 2016-01-30T00:20:43.010
@bmm6o trichoplax has it right, it refers to the scoring method. I had recently posted a similar challenge (unfortunately closed) that used human judgement for the scoring, and I was afraid this would be seen as a duplicate if I didn't make the difference clear in the title. I guess I could remove the word "objectively" the next time I have a reason to edit the question. – Nathaniel – 2016-01-30T06:33:36.683
@bmm6o Ah I see - the comment on that answer does make it sound like objectively means "object based". I think the upvoters on that comment may simply be showing that they like the approach, rather than agreeing with the interpretation of the word. We'll never know though... :) – trichoplax – 2016-01-30T21:33:07.230
This TED-Ed lesson is highly relevant. – Digital Trauma – 2016-01-30T23:59:36.087
1Just to check, nneonneo's answer (score 5080) is currently the one to beat for the bounty, right? – 2012rcampion – 2016-02-01T03:10:16.690
@2012rcampion I believe so, yes. (That answer is definitely eligible for the bounty but it's been a busy weekend, so I didn't get a chance to check if any of the other new answers are. I think they aren't, though.) – Nathaniel – 2016-02-01T04:17:25.800
You won't be able to offer either 50 or 100 points on the next bounty. Bounty amounts have to (at least) double each time, so you won't be able to offer a bounty less than 200 rep. – Martin Ender – 2016-02-03T14:05:20.983
@MartinBüttner I didn't know that. Oh well, in for a penny, in for a pound - I've upped the amount. – Nathaniel – 2016-02-04T01:27:04.080
@Nathaniel: it seems it will be very hard to get any solution without built-in compression to beat BPG... – nneonneo – 2016-02-06T05:32:01.947
@nneonneo I agree, it will be very hard. – Nathaniel – 2016-02-06T10:04:31.337
1@Nathaniel you should update the current winner part (under the bounty part) with Strawdog's answer. – Rɪᴋᴇʀ – 2016-03-20T15:54:41.157
@Nathaniel: Necropost! I've added an optimization-based approach that blows the socks off my previous no-built-in-compression attempt, and also handily beats Strawdog's submission (which hadn't even seen, because I'd stopped looking at this thread ages ago). Anyway, although I'm pretty unlikely to be able to beat my own ZSH+BPG submission, I thought you might be interested: it beats a lot of other built-in compression schemes. – nneonneo – 2016-06-03T18:55:12.510
@nneonneo where's the new post? (If you can post a link it would help, this thread has got a little unweildy) – Nathaniel – 2016-06-03T23:53:15.383
http://codegolf.stackexchange.com/a/81202. – nneonneo – 2016-06-04T00:33:12.997