258
\$\begingroup\$

Note: a 1000 point bounty is still available for this challenge, which I will create and award if anyone takes the top score without using built-in compression.

Below is a 386x320 png representation of van Gogh's Starry Night.

enter image description here

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 . 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>

\$\endgroup\$
37
  • 5
    \$\begingroup\$ On Windows I had trouble installing the python requirements. A safer option is to use pillow (pip unistall PIL, then pip install pillow) and change the first line to from PIL import Image. \$\endgroup\$
    – user42643
    Commented Jan 23, 2016 at 16:17
  • 2
    \$\begingroup\$ @tepples other than going in the opposite direction and not being logarithmic, yes :) \$\endgroup\$
    – hobbs
    Commented Jan 24, 2016 at 16:11
  • 6
    \$\begingroup\$ I'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. \$\endgroup\$ Commented Jan 28, 2016 at 10:16
  • 3
    \$\begingroup\$ @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. \$\endgroup\$
    – N. Virgo
    Commented Jan 28, 2016 at 10:29
  • 3
    \$\begingroup\$ @Nathaniel hasn't been said enough, but this question is so awesome! ;-) \$\endgroup\$ Commented Jan 28, 2016 at 10:33

38 Answers 38

1
2
7
\$\begingroup\$

zsh + FLIF, 4672.71078816

This solution is very similar to @orlp's, and it scores worse...

So why am I even bothering to type this?

Well, this solution has one less dependency: it does not require ImageMagick. Maybe that counts for something :)

Exploiting FLIF's progressive decoding, we create an interlaced FLIF file of a simplified image (to make sure that as much information is squeezed in as possible) and truncate it to fit the available file size. Since the FLIF image has the correct size already (the FLIF decoder will interpolate what was truncated), ImageMagick is not needed to scale the image up.

Here's the script that produces the 1024-byte script that produces the image:

convert ORIGINAL.png -resize x80 -resize 386x320! -depth 6 - | pngquant --speed 1 --ordered -f 25 > i.png
flif i.png o.flif -vvvvvvvvvvvvv -I -T200 -Y -R0 -P0
dd if=o.flif of=o.truncated.flif bs=992 count=1
echo 'exec flif =(tail -n+2 $0) o.png' > genstarry.sh
cat o.truncated.flif >> genstarry.sh
zsh genstarry.sh

Resulting image

\$\endgroup\$
7
\$\begingroup\$

bash + base64 + bpgdec, 4363.51784698

base64 -d>q<<<QlBH+2AAgwKCQAADkkJQRAHBkJWBFgNwAAABJgGvBdj9qQPRDPJb0JstVKPQw7JUMnA9cHZZuSvN5LfqLUYKsGDdgAcWfhxLa0YsnYwOO0fWZXO4OqHzX5ADymrgGGCv+zW21b35rhCmBtfK6uUHrMjRwckNPtYo1E4n2eU423MvrkdzUdRauwRQWO0pHxzyv3RfvYaKDDWttHEGFg55fZLwwfodyaDvcmOHYk6ekHLviqucjow6vDdg7J6NQXYoZJwfZPThO0u6jfWyWrXToUjq3XBj3NO+IQOjk0z1Zbc+NSd8kgH7a6fVRL6dAg/52jRsMgPf96U4dTbzk9gIEH54ArF/TdTweDp7d3FxOXFiQi8TTPrrTaqfO1QLKFrvOfQv2bIsCUxpGYffO8eqMZZIMGko50F0tWzk5TpZcTr2PqFSF6xbF7tzjJBDoVp3moFXU0kGNPBr7wgBQxwzuQlY+p0oXn3WMsuMfy+c7DUQGP9DvApHSmHNdRyfPNkyxfs0Hzn8KAsZ0Yiaz3ZjdwBuhDk87xYLAtzo9/G/A3Qja381JQynGiLuI9V36vVXTzQjccWbn9q43tcNBooroUD3Kjo6MITCG+69ij5j+X9z0aMs8v7Tpr2m5FS5tR21erm9Wr18BUYu9Oft49ZKgNd3fxi37keDsK1LlsowGrkRVkemvyVE7fznfyxGuWkXz+MfVIzIlQTMJxgaupqhSJgNv05hd/8LkU9PitwYP2S92d/UayjhJScIMaAP7AtyLWhhlrrPhNfdbWG0ermM2/sRGeKxC0sIEsqbiccjtwWkeEwUMZ6Fopm9oXL/a2KDLRAcTC+ef00wTB+m/dk2mql1WtXX44ewjCHAFV7Qvn8NaHB+rBVWskSfvwAwtztwwLRZ4sl9VURj8Iv81Xeg6CjW+0fmkmxEoY8PjeQY2wCB7XTj8vvCM3yPGWmIEEKE95NJmVgFXhLvJ1qOIBa+IclF0zU=;bpgdec q -o w

Evolutionary advancement of yallie's BPG answer, just to lower the score. Not competing for the bounty (in this answer).

Encoding command line userd:

bpgenc -c ycbcr -f 444 -noalpha -q 49 -m 10 -e jctvc ORIGINAL.png -o 1.bpg

I also experimented with bpgenc patched to use x265 in PSNR mode, but it didn't improve results. Also tried usual HEVC and VP9 (without scaling, the latter can't produce small enough file at all).

1.bpg.png

\$\endgroup\$
2
  • \$\begingroup\$ Can you embed the resulting image? \$\endgroup\$ Commented Feb 1, 2016 at 3:33
  • \$\begingroup\$ It is visually very similar to other BPG solutions. \$\endgroup\$
    – Vi.
    Commented Feb 1, 2016 at 8:21
4
\$\begingroup\$

C, 10299.28

draw.min.c, 250 bytes:

#define N getchar()
char m[320][386][3];main(){puts("P6 386 320 255");int c=N,i=0;while(c--){int r=N,g=N,b=N,x=N*2,v=N*2,u=N*2,w=N*2,y;for(;x<=v;x++){for(y=u;y<=w;y++){m[y][x][0]=r;m[y][x][1]=g;m[y][x][2]=b;}}}while(i<370560){putchar(*((**m)+i++));}}

image.dat, 149 bytes (hexdump):

0000000 3915 3d41 c100 a000 5043 568e 2bbb 4361
0000010 9050 974e 532b 4765 6389 2a97 5f53 7947
0000020 ba41 4e03 3d3a 439f 07c1 3970 8e5c 886d
0000030 622b 7943 4e96 006d 2563 9ead 706d 6303
0000040 5c38 5684 219b 3a53 8e5c 9256 760e 5c3a
0000050 006d 00bb 5870 a95c 7063 5307 4b3a 63a9
0000060 3ba0 385f 7c5c 9741 6307 5c58 4579 2abb
0000070 6553 8e79 5543 6200 ad25 43c5 31ac 4362
0000080 795c 8b03 530e 7f3a 337c 1b6d 6563 8470
0000090 c12b 6303 000a                         

Compile draw.min.c into a.out and pipe image.dat into it. This will result in a PPM file on stdout.

gcc -std=c99 draw.min.c
./a.out < image.dat > output.ppm

blocky blueish image

Explanation

image.dat is a list of rectangles to draw. The first byte is the number of rectangles; the remainder of the file is the actual rectangles. Each rectangle is 7 bytes: the first three are the color as RGB; then the x-coordinate to start at, the x-coordinate to end at, the y-coordinate to start at, and the y-coordinate to end at. These coordinates are multiplied by two so they cover the entire image (thus, one 'pixel' is actually 2x2).

draw.min.c simply takes this list and draws each entry into its internal pixmap, then dumps the resulting Portable PixMap file.

The data file could also be embedded into the program but it was easier for development to have it separate.

This was primarily an experiment in genetic algorithms. I've posted the code I used to generate this file on GitHub. The conclusion I reached is that they're a lot of effort to implement, and if not done right they don't give very good results at all.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ +1 for using a genetic algorithm, but to comply with the rules your program must take no input and load no files, so you would have to include the data in the source code. \$\endgroup\$
    – N. Virgo
    Commented Jan 26, 2016 at 5:28
  • \$\begingroup\$ +1 as well, I also tried some optimization approach, but based on a Voronoi Diagram (maybe I'll post the results later...) \$\endgroup\$
    – Marco13
    Commented Jan 26, 2016 at 10:47
  • \$\begingroup\$ +1 from me too, we had mostly the same idea :) I didn't look through your code too carefully, but it looks like you also let color vary? I think you'll get better results if you pick the color of each rectangle to minimize the score since you know the target image ahead of time (I just took a mean of each color channel in the original image). \$\endgroup\$
    – neocpp
    Commented Jan 26, 2016 at 14:32
4
\$\begingroup\$

Python 3 (no built in compression) 7147.31

While not a terribly competitive answer, I had the idea of using a pseudo-grid optimized to each color. It has the nice property that it looks like abstract stained glass. enter image description here

The drawing algorithm is this -- for each of the colors, define six "vertical" lines (from a point on the top edge to a point on the bottom edge) and six "horizontal" lines (from a point on the left edge to a point on the right edge). Assign each pixel a value (i,j) where i is the number of horizontal lines above it and j is the number of vertical lines to the left of it. For each of the 49 (i,j) pairs, define a value from 0 to 255 for that color channel. Each channel gets its own grid and set of 49 color values. A Gaussian blur of 3 pixels is applied afterwards. This fits into 1020 bytes.

import base64, numpy, PIL.Image, PIL.ImageFilter
j="0123456789"
q={a:b for b,a in zip(j+"()[], ",j+"abcdef")}
def z(x,y,u,d,w):
 return sum([x>(a+(b-a)*(y/w)) for a,b in zip(u,d)])
exec("s,h,w,u,d,l,r,c="+"".join(q[t] for t in base64.binascii.b2a_hex(base64.b85decode(b'rsE*vhU~(Y;}hd3<0;`W;db7`1LK}S;}YeLW!}L)Gv?>yE-l{7H-0b<Fdiw67LHNg!xiC};Zfsa<9;KJ>==#~E*CDIN8y0o?8%-WULZaWBVJAHC+I#><>EQwSKh)>;Wy)MBu*iI5Ix?^BOVo=79JoT7#<l7>?!76CE^YjZWb-<77i)mS>a{kY3GgJ%va%2=RRrSCgvVT=nf=Kli_6HQ0R^`=bjLLhUZ=rE)iZw=ROx+A)XU%5q=WrUK1Xb;#1*M;u7UvC*cR-gW@LPIpHJa9%11);v(ZdY2qGu=AG;iUJ;IP=q?ftFy;;!PGRUSP~@H`<8CtLE-2@I6HXB>L*ouM=Uxzw6F!&bK6vR4W$B&~UKlQB=`L5{8R3B8FyVIQju3tq9u{5~o)tbK=q>Dq;X~m$;YQ&C<DPKgDd9rlY2ifSN#t&0;xOSz;S}SJRpD+i;UwseBOWAvH{ufFjuJi<K2DM12jWgu;WpupGT~<9ZV`S-;VI!T;Z)&4;T7Q%=1to')).decode("utf-8")))
PIL.Image.fromarray(numpy.array([[[c[i][(s+1)*z(x,y,u[i],d[i],h)+z(y,x,l[i],r[i],w)] for i in range(3)] for x in range(w)] for y in range(h)]).astype("uint8")).filter(PIL.ImageFilter.GaussianBlur(3)).save("o.png")

I used simulated annealing to determine the best parameters, and base85 encoded them into the python program. I think there's a lot of tuning that could be done here -- for example, I encode the parameters by printing a huge tuple, stripping out the spaces, converting the characters 0-9()[], into hex digits, then encoding that in b85. Probably not the best way to do it.

\$\endgroup\$
4
\$\begingroup\$

HTML + JS, 7433.57

I put a ton of work into this. Turns out I didn't pick the best tool for the job :p

This contains a ton of unprintables:

<canvas width=386 height=320 id=c><script>t=c.getContext`2d`;i=0;`[h|\rhuAOrRx|m&f&aMh\\CYo$%6t*hh
*@?NOd\\Lu3
wj@=POD\\   /"8|

B"Ow|)U 8z@D02z%>e;VJ7Af
CDRQ=   /kH
NATU)A( 'Z=vUA0e$uW#Ke68M4#n-
k>;5cLxc\\G1d3b3fM);F4yIe3]=-#xrr(gKZ<a[.d  (SwHS6$}+4%0$j\r;fni";'I[F>wRlPN*-" wR^\\?V1V\\qi!5%\r~ XGY2vtmS2$(r~\`FYRv]32h,:#*TrTs'tJ4c*h{?(r  B Q*HCJ)M'Tz#/e+H[*[HWD93,d.    [.<iLr6$iaEfSitj9OcqwKeVr5"/hc: cIIDQxt8
z1EK%ib:"nsBvDZqWU3 Mx#BpB\\W%Jz-j6RAb@4kCRxt\\#[jx*^
T?gapt>D21F)I+xg%bG8DSPxrZG1UD62\r
k$  JZ]A0%ci,setIE+ $1x|H GCqY: Gcb!L5&$)L~@'   t:dtTfeU3$M(cZDpQSg%J%DH0jd]T'S@x5
"@|B cAa>Gx|6DR)<l0gC   \\b/\res1Dl5N)#J(nNg4qE>&\rGs!lvH`.replace(/./gs,p=>p.charCodeAt(0).toString(2).padStart(7,0)).match(/.{16}/g).map(p=>(t.fillStyle=`rgb(${(g=p.match(/.{8}/g).map(d=>parseInt(d,2)))[0]},${g[0]},${g[1]})`,t.fillRect(i%35*11,(i++/35|0)*35,11,35)))</script>

Anyway, here's the result:

Blocky looking recreation of Starry Night

It's pretty neat I guess, unfortunately the edges are white (or maybe transparent) since the block size I chose doesn't fit evenly. That probably added onto my score quite a bit.

Explanation:

The big long string of unprintables is base 128 encoding. Because I can't include null bytes, I just fudged the colors a bit to get rid of them. It encodes every block as 16 bits. It uses a combined R/G channel, because the painting is mostly blue, yellow, and gray, which don't require differentiating red and green.

Planning on dropping it to 7 bit colors, and maybe even less. This could allow me to make the blocks smaller, as right now they're 11 by 29 pixels, much too large to encode the painting with the necessary detail to get a higher score.

\$\endgroup\$
3
\$\begingroup\$

C#, 6735.73

1023 bytes

My naive C# 4.0 approach, based on a 12x10 image on base64.

The PixelOffsetMode.HighQuality makes a huge difference on the result, that's why I spent some bytes on that.

using System;using System.Drawing;
class P{ static void Main(){
var i=Image.FromStream(new System.IO.MemoryStream(Convert.FromBase64String("iVBORw0KGgoAAAANSUhEUgAAAAwAAAAKCAYAAACALL/6AAAABmJLR0QA/wD/AP+gvaeTAAAACXBIWXMAAAsTAAALEwEAmpwYAAAAB3RJTUUH4AEdFx8ea7+R2AAAAZVJREFUGNMFwctuElEAgOH/zJwB5sYMUrCNicakpdVaE62JJq6MO5+hG/e+gQ/iG7h14QNoTNy4aexCm0ZZSAu0XAYYYG7MOX6fOHn3Xk/HBVG0JmzUCUKDm3GVTQ7b7Rn9oYsf2hwcVlFZivx14UMx5/FuxOnfHTJtEviKOC5ZZC7akHQOW7w5+kZU7iIPOgb9gUWkHvH0RZNlNKDUDu0gZLXMOX4F3b5mnG2xTtfIcLuFaaQMb3rYy4SK3QZh4vkuWT7j5+8SUVV8/P4M25wj41XMenbG4N+CWzv7NFsNRuOI0fUIr25TNxwyJXh+pLjTDJDTyZrRZQ5acdwxsawVvascLTWev8GpmoQBnJ8P+PDpM/L+XYeoZ5Jcdvny9ZR7D/eoOwXpquTsxwJdJBRlhUqtwYOXJ4gnr9/qIu4yH/4B06Ti7eE2buN4AcowEWWC6woc26ZirJCkI7LFAGlZaDQ6vUIkOVpMiKIUS2rymkdcq2EKifTsa1TdIppkaFWi1ZI8k0ijZMsHIQOSjYEoEvLNlP8c3rfxrVY4fQAAAABJRU5ErkJggg==")));
var d=new Bitmap(386,320);
var g=Graphics.FromImage(d);
g.PixelOffsetMode=System.Drawing.Drawing2D.PixelOffsetMode.HighQuality;
g.DrawImage(i,0,0,386,320);
d.Save("d.png");}}

Generated image

\$\endgroup\$
3
\$\begingroup\$

Python 3, score 5052.495855440216

No builtin compression used. This program creates a 30x25 image from embedded binary data. Each byte encodes one pixel of the image. The most significant 4 bits encode the green channel, the least significant 4 bits encode the blue channel. The red channel is created by copying and scaling the values of the green channel. Finally the image is resized to 386x320 and saved to "a.png".

Partial code (see hexdump for complete code):

#coding:latin-1
from PIL.Image import *
d='''place data from hexdump here'''
i=new('RGB',(30,25))
for y in range(25):
 for x in range(30):
  t=ord(d[x+y*30])
  g=(t>>4)*165/15+26
  i.putpixel((x,y),(round(g*75/91),round(g),round((t&0xf)*162/15+21)))
i.resize((386,320),BICUBIC).save('a.png')

Hexdump:

00000000: 2363 6f64 696e 673a 6c61 7469 6e2d 310a  #coding:latin-1.
00000010: 6672 6f6d 2050 494c 2e49 6d61 6765 2069  from PIL.Image i
00000020: 6d70 6f72 7420 2a0a 643d 2727 2738 9aa9  mport *.d='''8..
00000030: 6916 5878 165b a98b 595a 7a7b 5a49 3838  i.Xx.[..YZz{ZI88
00000040: 5949 486a 5a7b 6a7b 7b6b 5939 abc7 9c29  YIHjZ{j{{kY9...)
00000050: 3747 3849 aa8a a88a 4a39 3a3a aa99 6b4a  7G8I....J9::..kJ
00000060: 5b49 6b6a aedb caca 8b39 6b7c 4b38 152a  [Ikj.....9k|K8.*
00000070: 4a4b 4b3a 5a49 4a4a 296b b9a7 7a49 386c  JKK:ZIJJ)k..zI8l
00000080: 7dbc daf9 e6ea cc38 5c5c 4c3a 2656 8749  }......8\\L:&V.I
00000090: 3a4a 4949 485a 4939 3a7b 7b49 3849 5c5c  :JIIHZI9:{{I8I\\
000000a0: 9edb ead3 f9ea dc5b 4b5b 4b36 96b4 6a4b  .......[K[K6..jK
000000b0: 5b7b 9caa adac 7b8c 6b48 5a8b 8c6d 8dec  [{....{.kHZ..m..
000000c0: e7d2 f9e9 db8b 4a4a 3a25 5a7a 5b8c 8c8b  ......JJ:%Zz[...
000000d0: aa7b 798b 8c7c ae6a 6bca bb8d 8dcc fad3  .{y..|.jk.......
000000e0: d3c4 dc9b 9b6a 4b58 588d 9dbc 9c9c 485b  .....jKXX.....H[
000000f0: 7b7b 8c8c 7b8c 6baa cd9d 7d9b cbe9 f9ea  {{..{.k...}.....
00000100: bc8b adad 9c9b 239d ac9c bc37 8b9b 8c9d  ......#....7....
00000110: 8c9d 8c6b 6c6c 6c8d 7c8c acbd bcad 9dac  ...klll.|.......
00000120: 6a8c 9b46 229d 9c8a ba6b 8c8c ad8b 8dad  j..F"....k......
00000130: ae6a 7b5a 7c8c 6b8d 7d9e 8d7b 8cbd bdbf  .j{Z|.k.}..{....
00000140: 8b34 236b 365a 6a8c 9d8c 6b8c 8cad 8c7c  .4#k6Zj...k....|
00000150: 9c9b 8c8c 8c9d 8e9e 8d8c cc8c 8c9c 7912  ..............y.
00000160: 2258 5848 6b9d ae9c 9b6b 7b6b 7b9b 9c6b  "XXHk....k{k{..k
00000170: 9d9d 7c9e 9dae ddec ddcc 7cba b811 1157  ..|.......|....W
00000180: 7b8c adbd 9d9d 9c9c 9c8c 7c7c 9c9d 9c9e  {.........||....
00000190: 7b9c edec eded dd6b 8dba b911 1135 7bcc  {......k.....5{.
000001a0: eced de6b 6a7b 7b6b 7b7b ad9d ac7c 8bdc  ...kj{{k{{...|..
000001b0: ddcd ddab 786a 6a7d 5811 1135 7bcc ebda  ....xjj}X..5{...
000001c0: bc8c 7b7c 7c7b 6a8b ac8c 8c9c dcdc cc9c  ..{||{j.........
000001d0: 6801 139a ab6c 4611 0122 599a eeef ac8b  h....lF.."Y.....
000001e0: 9cab 9bab ccbb ccbc bcbc bcac ab45 1313  .............E..
000001f0: 149b cbbd 4601 0111 4659 9cab b9ba abaa  ....F...FY......
00000200: aaab 7a8a 8a9a 9b8b 5835 1437 5959 599c  ..z.....X5.7YYY.
00000210: 9cbd 6801 1111 2322 abbc 7b8b 7a8b 8b69  ..h...#"..{.z..i
00000220: 3838 3815 1436 364a 5c5c 7d8c 7d7b 6a9b  888..66J\\}.}{j.
00000230: 8c8b 1101 1123 1133 595a 3736 5949 594a  .....#.3YZ76YIYJ
00000240: 4827 385a 5b6a 5b6a 8c9d 7b6a 365a 4936  H'8Z[j[j..{j6ZI6
00000250: 1101 0101 1111 1214 1548 4847 5937 3749  .........HHGY77I
00000260: 4835 4646 5757 8975 7766 2425 2411 1101  H5FFWW.uwf$%$...
00000270: 0101 1111 1225 2546 3536 5768 6947 3534  .....%%F56WhiG54
00000280: 4657 5758 7968 6746 2424 2512 1121 1111  FWWXyhgF$$%..!..
00000290: 0111 1112 3525 4646 5624 2547 3635 2425  ....5%FFV$%G65$%
000002a0: 3658 5757 4668 2336 3511 0111 1101 1111  6XWWFh#65.......
000002b0: 1111 1312 4423 6935 1302 3336 4534 1224  ....D#i5..36E4.$
000002c0: 3614 2423 2544 4411 1111 1111 2111 1101  6.$#%DD.....!...
000002d0: 1222 2345 3422 2302 0114 4536 7835 4546  ."#E4"#...E6x5EF
000002e0: 5647 3253 4321 1111 0111 1101 0101 1111  VG2SC!..........
000002f0: 2223 2333 4345 3423 2336 1546 4634 1133  "##3CE4##6.FF4.3
00000300: 5354 4454 3211 2211 1101 1101 1122 3433  STDT2."......"43
00000310: 3423 3434 4556 3534 2423 1323 3355 2727  4#44EV54$#.#3U''
00000320: 270a 693d 6e65 7728 2752 4742 272c 2833  '.i=new('RGB',(3
00000330: 302c 3235 2929 0a66 6f72 2079 2069 6e20  0,25)).for y in 
00000340: 7261 6e67 6528 3235 293a 0a20 666f 7220  range(25):. for 
00000350: 7820 696e 2072 616e 6765 2833 3029 3a0a  x in range(30):.
00000360: 2020 743d 6f72 6428 645b 782b 792a 3330    t=ord(d[x+y*30
00000370: 5d29 0a20 2067 3d28 743e 3e34 292a 3136  ]).  g=(t>>4)*16
00000380: 352f 3135 2b32 360a 2020 692e 7075 7470  5/15+26.  i.putp
00000390: 6978 656c 2828 782c 7929 2c28 726f 756e  ixel((x,y),(roun
000003a0: 6428 672a 3735 2f39 3129 2c72 6f75 6e64  d(g*75/91),round
000003b0: 2867 292c 726f 756e 6428 2874 2630 7866  (g),round((t&0xf
000003c0: 292a 3136 322f 3135 2b32 3129 2929 0a69  )*162/15+21))).i
000003d0: 2e72 6573 697a 6528 2833 3836 2c33 3230  .resize((386,320
000003e0: 292c 4249 4355 4249 4329 2e73 6176 6528  ),BICUBIC).save(
000003f0: 2761 2e70 6e67 2729 0a                   'a.png').

Image:

enter image description here

\$\endgroup\$
2
\$\begingroup\$

Pyth (no built-in compression), score 4349.4941

Output image from the program

This challenge has been stuck in my head, I keep coming back to it every couple years trying to beat the score of 4159 without using built-in compression. While I haven't been able to do that, my solution is good enough for second place, so I decided to package it up and post it. The basic idea is to perform a Discrete Cosine Transform over the full 386x320x3 image, then encode a compact approximation of the DCT along with the code to extract it and do an inverse DCT. A DCT is similar to a Fourier transform, and converts the image matrix into a matrix of cosine waves of varying frequency and amplitude. This transformation is useful since images like this have most of the information concentrated in the lower frequencies. The below image shows a visualization of the absolute magnitudes of the DCT for Starry Night. A visualization of the absolute magnitudes of the DCT

In fact, after the transformation of Starry Night, we can discard over 75% of the points and still have a score under 0.1, and selecting the best 1200 points would probably be sufficient to beat a score of 4159. Unfortunately, trying to store the location and value of these points is prohibitively large, so I went with a different route. First the data is quantized by dividing by a fixed value and rounding to an integer with a slight bias towards zero. Next, since most of the information is concentrated in the lower frequencies, we can encode the values in diagonal strips moving away from the origin, with each strip having a fixed number of bits for the absolute value, and one bit for the sign if it is non-zero. At the start of a strip, the number of bits to read per value is encoded based on its change from the previous value, and can increase or decrease. When the bits per symbol in a strip drops to to zero, that color channel is done. Below is a visualization of the DCT values encoded by this solution.

A visualization of the DCT encoded by this program

This encoding method allows a lot of preprocessing work to be done to find an optimal combination of scale factor, rounding bias, bits per strip, etc., for a given size. It also allows the sequence to be tweaked to avoid characters that would need to be escaped. The end result is a 220 byte Pyth program with 804 bytes of data, and a score of 4349.4941. The program and data can be optimized a bit more, but not near enough to take first place. I currently improve the score by about one point per additional byte of data, and that diminishes the smaller the score gets. My best attempt at beating a score of 4159 still requires over 1024 bytes of data alone. The resulting Pyth program must be run with the -M option to disable memoization, since functions have side effects. It is also very slow, mainly due to Pyth constantly copying large lists. Pypy3 speeds things up a bit, but it still takes almost an hour to run on my machine. When complete, it will save the output as o.png. The bulk of the development work was done in C, with the decode functionality being converted to Python and then Pyth at the end when I decided to go for second place.

The code

A hex dump of the 1024 bytes that make up the program:

4B 6D 30 2A 2A 33 4A 33 38 36 3D 54 33 32 30 3D
47 43 22 04 C9 8A 40 18 0B F2 AA 09 86 29 80 24
31 1B 00 0B 68 D9 4F 54 C0 60 A9 2C CA 89 03 1F
37 90 2A 00 01 B0 0C 88 61 80 08 40 40 50 1C 48
BD 0B 00 A0 46 40 78 7A 0C 40 C7 F3 01 99 E0 28
C9 E1 89 50 28 9A 0E 53 67 13 83 34 58 E1 FE 40
4B D0 06 C0 F8 0A 78 B1 7E AF 61 61 8C 26 00 01
B0 DA 0B 26 40 42 B2 0D B5 17 88 6C 2E B0 06 2D
C7 01 9C C1 72 A2 B0 50 00 38 0F 46 11 4D 80 26
5F C3 20 41 F0 35 70 FB 04 14 F0 80 10 86 40 12
8E 52 86 F1 01 18 C6 05 0A 08 43 3E 8A 5E 20 1B
07 A5 82 AF 3F 99 DE F0 52 69 99 20 04 A4 57 2D
71 4E C2 E8 74 69 C0 61 F0 28 43 63 9D 28 D7 C3
A2 12 79 9D 4F BF 3B 51 21 B3 2C 05 0A 84 62 24
A1 E5 FB FA B0 56 06 15 34 B8 1B 6D E3 C0 0A C1
FC 01 BE 13 AF 2C 8F 3D 1B 0A 54 B4 C1 21 60 BA
AC 52 F6 92 96 2A D6 32 F3 69 9B D9 D4 15 65 40
7B E0 4D F9 6C C4 D5 28 47 51 E5 49 79 49 0F AC
AD 43 C4 FD 55 38 9E 35 F4 12 73 79 82 B4 E2 33
D6 A0 DE 4A 76 E4 F1 A6 59 34 57 DB 2F CA 85 2F
50 FC F5 C3 77 0A 8F 07 D2 15 EA 57 F4 F3 78 D3
6F C7 7E 24 1B F4 D7 90 D4 26 5D EE F4 FB 8D B4
0A 52 15 50 8A 50 97 48 6C 80 16 84 C3 B4 AA DC
12 46 14 99 2A 28 81 44 37 66 83 44 46 04 B9 95
BA 55 71 7A 75 59 AC 92 23 68 6D A8 E6 24 27 A1
69 AF 79 84 A4 A9 EB BB 3E F7 2A 7F D8 E4 85 18
53 68 3C 71 00 46 E0 5B 89 59 C1 AE B5 04 24 B4
6A 24 C9 23 8E 63 D1 0E F9 55 42 26 2D 7B 1D 91
A7 E2 92 89 33 C7 90 52 D2 15 DF 6D 58 D1 17 36
E4 8C CC 9B 4A DB 34 3B 34 FF 1E 75 2B 08 B7 F2
CD 50 DD DE 04 1C 2C 55 D9 98 0A 21 96 F1 1D 8D
8E AA 37 FA E9 BF 6F 0A 2D 3A 07 F9 18 3A 1C 06
35 52 46 24 10 85 C8 D6 83 E2 3C 8D DD D1 57 90
16 AF 81 0A 55 A1 A5 75 04 68 E4 24 3B 0C 35 00
04 48 AA 04 02 C8 33 E1 4E 81 DA 74 11 80 16 3F
47 30 39 01 1F 81 A8 CE A1 19 2C D2 24 A0 C6 98
30 4D B5 17 E5 B0 2B B2 20 53 DB C5 50 F9 45 02
20 03 46 3D 91 E0 0F B8 80 C1 8D 9B 82 69 D4 E7
09 0B 53 12 42 A3 A3 24 92 A6 A8 00 C0 02 C2 2B
00 80 29 2C 28 54 42 00 AC 28 B0 00 56 0C 1E 60
3F 31 45 88 00 80 5F 98 15 80 93 C6 A3 CF 0D 06
68 14 24 3C 62 60 21 45 0A 68 E4 1F 2A 19 56 A0
08 21 02 29 2C E8 C3 3F 45 40 81 18 F3 DB 53 88
C5 40 41 EA F1 68 A1 9E 39 F1 7C D4 FC C7 99 AC
C8 95 28 96 C4 D1 28 40 85 15 6B 6E 24 01 BF 62
B7 3C 41 AA 9D 4C 85 32 F2 40 14 98 36 F1 2C 01
42 95 C4 87 A9 73 1B 42 AE 02 6F 2E D4 DB 10 13
86 39 C3 7C F4 DC D0 F3 96 E3 45 34 20 81 E8 CE
48 0B 48 89 1C 96 8C D1 3C 52 B7 B5 11 5A 7E 15
1D 65 04 C8 49 0D 2C 84 6A 81 93 E3 12 69 88 07
C4 2A 89 26 18 83 E7 90 73 2E 39 09 A3 11 80 CE
88 D0 DC 4B 91 2E 56 22 4C 65 41 2E 44 47 5E 32
62 56 33 3D 64 79 34 56 54 46 59 3A 48 68 2A 48
4A 74 4A 49 3D 6B 2A 79 64 32 30 37 20 58 4B 2B
2A 59 33 2D 32 4E 3F 79 31 5F 6B 6B 29 29 57 26
64 79 31 3D 2B 64 7C 79 31 5F 31 3B 44 67 47 48
3D 6B 25 48 3E 4B 47 56 59 3D 64 30 46 5A 55 59
3D 2B 64 63 2A 40 6B 5A 2E 74 2A 2A 63 2E 6E 30
59 2B 4E 2E 35 5A 31 3F 5A 31 2E 6E 32 29 20 58
4B 2B 47 2A 4E 48 2A 64 40 63 32 59 32 3B 56 3D
59 54 67 4E 2A 33 4A 3B 56 33 56 54 67 2B 2A 2A
48 3D 59 4A 33 4E 33 3B 56 2A 4A 54 67 2A 3D 59
33 4E 31 3B 2E 77 6D 6D 2E 3C 6D 2E 52 62 30 3A
4B 3D 5A 2A 2B 2A 64 4A 6B 33 2B 33 5A 32 4A 54

Code Walk Through

Km0**3J386=T320;        Initialize J to width, T to height, K to a list of width * height * 3 zeros. A list is used instead of a matrix to save code size.
=GC"..."                Setup the bit sequence. G is set to an integer encoded as a 804 byte long base 256 string, the value was modified slightly during preprocessing to avoid characters that would need to be escaped.
LeA.DG^2b               Define y(b) as a ReadBits(int) function. It will set G to G//2^b and return the remainder. Returns 0 and does not modify G when b is 0. 

V3                      Loop through each color channel using N as the variable
    =dy4                Set d to ReadBits(4) to get the starting number of bits per symbol
    VT                  Loop through 320 diagonal strips using H as the variable, only 80 or strips so actually have data
        FY:Hh*HJtJ      Loop through the strip indexes using the variable Y. Start at the strip number, step forward by width-1 each time to go one row up and one column back until the end of the strip
            I=k*yd207   Set k to ReadBits(d) times the scaling factor 207 and check if it is non-zero
                XK+*Y3-2N   Index into the list K. Y is the index within the color plane, so multiply by 3, and then (2-N) so that we start with the last channel and work backwards. Working backwards was done since it made tweaking the bit sequence easier if the sequence ran out in the long strips at the end of the first (Green) channel.
                ?y1_kk))    Assign -k if ReadBits(1), else k
        W&dy1=+d|y1_1;      Strip is done, update the number of bits to read per symbol. While d > 0 and ReadBits(1): d += 1 if ReadBits(1) else -1

DgGH                    Define the inverse one-dimensional DCT function g that takes the parameters G (offset) and H (stride), plus the global value of Y as the length
    =k%H>KG             Copy every Hth (stride) element of K starting from offset G into k. K will be progressively overwritten with results, so the original values need to be preserved beforehand. 
    VY                  Loop length times using variable N
        =d0             Initialize d to 0
        FZUY            Loop length times using variable Z. Summation loop
            =+dc*@kZ.t**c.n0Y+N.5Z1?Z1.n2)    A bunch of math. Add (k[Z] * cos(pi / length * (N + 0.5) * Z) / (1 if Z>0 else sqrt(2))) to d.
        XK+G*NH*d@c2Y2; Store the result of the summation divided by sqrt(2/length) to K[N * stride + offset]

       To undo the DCT, the one-dimensional iDCT is performed on each column for each color channel, then on each row for each color channel, then (width * height) times over every 3-element pixel
V=YT                     Loop over the columns performing iDCT. Loop using variable N. For the iDCT, we would normally want to loop over all 386 columns, and do that 3 times (once per color channel), but since most of the columns don't have any data in them we only need to do around 80 or so columns. Plus, since color channels are adjacent, we can combine the operations and only need to loop over the first 80*3 or so columns. The image height of 320 is sufficient, and Y needs to be set to it for the length parameter of the iDCT, so this lets us save some code and improve performance.
    gN*3J;               Call the iDCT function with the column offset, and a stride of 3 * Width. Y (length) has been set to height
V3                       Loop over the color channels using variable N
    VT                   Loop over the rows using variable H
        g+**H=YJ3N3;     Perform iDCT of the offset (row * Width * 3 + channel), stride of 3. Sets Y (length) to width.
V*JT                     Loop (width * height) times using N. Performs iDCT of each pixel.
    g*=Y3N1;             Perform iDCT at offset (N * 3), stride of 1. Sets Y (Length) to 3
.w                       Save the following matrix as a PNG image with the filename o.png
    mm.<m.Rb0:K=Z*+*dJk3+3Z2JT    Use a bunch of maps and slicing to transform the list into a matrix for writing to PNG. Pixels are also encoded as GBR since that allows DCT to compact the information better, so a shift is also applied to transform them back to RGB. It also rounds each entry to an int.
\$\endgroup\$
1
  • \$\begingroup\$ This is great! I've temporarily awarded you the green check to draw attention to your answer \$\endgroup\$
    – N. Virgo
    Commented Mar 1 at 16:54
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.