# Encode Images into Tweets (Extreme Image Compression Edition) [closed]

Based on the very successful Twitter image encoding challenge at Stack Overflow.

If an image is worth 1000 words, how much of an image can you fit in 114.97 bytes?

I challenge you to come up with a general-purpose method to compress images into a standard Twitter comment that contains only printable ASCII text.

## Rules:

1. You must write a program that can take an image and output the encoded text.
2. The text created by the program must be at most 140 characters long and must only contain characters whose code points are in the range of 32-126, inclusive.
3. You must write a program (possibly the same program) that can take the encoded text and output a decoded version of the photograph.
4. Your program can use external libraries and files, but cannot require an internet connection or a connection to other computers.
5. The decoding process cannot access or contain the original images in any way.
6. Your program must accept images in at least one of these formats (not necessarily more): Bitmap, JPEG, GIF, TIFF, PNG. If some or all of the sample images are not in the correct format, you can convert them yourself prior to compression by your program.

## Judging:

This is a somewhat subjective challenge, so the winner will (eventually) be judged by me. I will focus my judgment on a couple of important factors, listed below in decreasing importance:

1. Ability to do a reasonable job of compressing a wide variety of images, including those not listed as a sample image
2. Ability to preserve the outlines of the major elements in an image
3. Ability to compress the colors of the major elements in an image
4. Ability to preserve outlines and colors of the minor details in an image
5. Compression time. Although not as important as how well an image is compressed, faster programs are better than slower programs that do the same thing.

Your submission should include the resulting images after decompression, along with the Twitter comment generated. If possible, you could also give a link to the source code.

## Sample images:

• U+007F (127) and U+0080 (128) are control characters. I would suggest banning those as well. – PleaseStand Apr 8 '13 at 0:57
• Good observation. I will fix that. – PhiNotPi Apr 8 '13 at 2:52
• Doesn't Twitter allow Unicode to some extent? – marinus Apr 8 '13 at 15:08
• I feel like I would want to patent a solution to this. – Shmiddty Apr 9 '13 at 22:51
• "Mountainous Landscapes" 1024x768 - Get it before it's gone! --> i.imgur.com/VaCzpRL.jpg <-- – jdstankosky Apr 16 '13 at 14:35

I've improved my method by adding actual compression. It now operates by iteratively doing the following:

1. Convert the image to YUV
2. Downsize the image preserving the aspect ratio (if the image is color, the chroma is sampled at 1/3 the width & height of the luminance)

3. Reduce the bit depth to 4 bits per sample

4. Apply median prediction to the image, making the sample distribution more uniform

5. Apply adaptive range compression to the image.

6. See if the size of the compressed image is <= 112

The largest image that fits in the 112 bytes is then used as the final image, with the remaining two bytes used to store the width & height of the compressed image, plus a flag indicating if the image is in color. For decoding, the process is reversed, and the image scaled up so the smaller dimension is 128.

There is some room for improvement, namely not all the available bytes are used typically, but I feel I'm at the point of significantly diminishing returns for downsampling + lossless compression.

Quick & dirty C++ source

Windows exe

Mona Lisa (13x20 luminance, 4x6 chroma)

&Jhmi8(,x6})Y"f!JC1jTzRh}$A7ca%/B~jZ?[_I17+91j;0q';|58yvX}YN426@"97W8qob?VB'_Psx%VR=H&3h8K=],4Bp=$K=#"v{thTV8^~lm vMVnTYT3rw N%I

Hindenburg (21x13 luminance)

GmL<B&ep^m40dPs%V[4&"~F[Yt-sNceB6L>Cs#/bv\4{TB_P Rr7Pjdk7}<*<{2=gssBkR$>!['ROG6Xs{AEtnP=OWDP6&h{^l+LbLr4%R{15Zc<D?J6<'#E.(W*?"d9wdJ' Mountains (19x14 luminance, 6x4 chroma) Y\Twg]~KC((s_P>,*cePOTM_X7ZNMHhI,WeN(m>"dVT{+cXc?8n,&m$TUT&g9%fXjy"A-fvc 3Y#Yl-P![lk~;.uX?a,pcU(7j?=HW2%i6fo@Po DtT't'(a@b;sC7"/J

2D Shapes (21x15 luminance, 7x5 chroma)

n@|~c[#w<Fv8mD}2LL!g_(~CO&MG+u><-jT#{KXJy/#S@m26CQ=[zejo,gFk0}A%i4kE]N ?R~^8!Ki*KM52u,M(his+BxqDCgU>ul*N9tNb\lfg}}n@HhX77S@TZf{k<CO69!

• This makes me feel like I'm developing cataracts or something. Haha, great job! – jdstankosky Apr 16 '13 at 14:39
• Nice improvements! – jdstankosky Apr 19 '13 at 13:56

## Go

Works by dividing the image into regions recursively. I try to divide regions with high information content, and pick the dividing line to maximize the difference in color between the two regions.

Each division is encoded using a few bits to encode the dividing line. Each leaf region is encoded as a single color.

4vN!IF$+fP0~\}:0d4a's%-~@[Q(qSd<<BDb}_s|qb&8Ys$U]t0mc]|! -FZO=PU=ln}TYLgh;{/"A6BIER|{lH1?ZW1VNwNL 6bOBFOm~P_pvhV)]&[p%GjJ ,+&!p"H4Yae@:P

<uc}+jrsxi!_:GXM!'w5J)6]N)y5jy'9xBm8.A9LD/^]+t5#L-6?9 a=/f+-S*SZ^Ch07~s)P("(DAc+$[m-:^B{rQTa:/35Jy}AvH2p!4gYR>^sz*'U9(p.%Id9wf2Lc+u\&\5M> lO6>v7z87n;XsmOW^3I-0'.M@J@CLL[4z-Xr:! VBjAT,##6[iSE.7+as8C.,7uleb=|y<t7sm$2z)k&dADF#uHXaZCLnhvLb.%+b(OyO$-2GuG~,y4NTWa=/LI3Q4w7%+Bm:!kpe& ZoIMHa;v!]&j}wr@MGlX~F=(I[cs[N^M=G=Avr*Z&Aq4V!c6>!m@~lJU:;cr"Xw!$OlzXD$Xi>_|*3t@qV?VR*It4gB;%>,e9W\1MeXy"wsA-V|rs$G4hY!G:%v?$uh-y~'Ltd.,( The Hindenburg picture looks pretty crappy, but the others I like. package main import ( "os" "image" "image/color" "image/png" _ "image/jpeg" "math" "math/big" ) // we have 919 bits to play with: floor(log_2(95^140)) // encode_region(r): // 0 // color of region (12 bits, 4 bits each color) // or // 1 // dividing line through region // 2 bits - one of 4 anchor points // 4 bits - one of 16 angles // encode_region(r1) // encode_region(r2) // // start with single region // pick leaf region with most contrast, split it type Region struct { points []image.Point anchor int // 0-3 angle int // 0-15 children [2]*Region } // mean color of region func (region *Region) meanColor(img image.Image) (float64, float64, float64) { red := 0.0 green := 0.0 blue := 0.0 num := 0 for _, p := range region.points { r, g, b, _ := img.At(p.X, p.Y).RGBA() red += float64(r) green += float64(g) blue += float64(b) num++ } return red/float64(num), green/float64(num), blue/float64(num) } // total non-uniformity in region's color func (region *Region) deviation(img image.Image) float64 { mr, mg, mb := region.meanColor(img) d := 0.0 for _, p := range region.points { r, g, b, _ := img.At(p.X, p.Y).RGBA() fr, fg, fb := float64(r), float64(g), float64(b) d += (fr - mr) * (fr - mr) + (fg - mg) * (fg - mg) + (fb - mb) * (fb - mb) } return d } // centroid of region func (region *Region) centroid() (float64, float64) { cx := 0 cy := 0 num := 0 for _, p := range region.points { cx += p.X cy += p.Y num++ } return float64(cx)/float64(num), float64(cy)/float64(num) } // a few points in (or near) the region. func (region *Region) anchors() [4][2]float64 { cx, cy := region.centroid() xweight := [4]int{1,1,3,3} yweight := [4]int{1,3,1,3} var result [4][2]float64 for i := 0; i < 4; i++ { dx := 0 dy := 0 numx := 0 numy := 0 for _, p := range region.points { if float64(p.X) > cx { dx += xweight[i] * p.X numx += xweight[i] } else { dx += (4 - xweight[i]) * p.X numx += 4 - xweight[i] } if float64(p.Y) > cy { dy += yweight[i] * p.Y numy += yweight[i] } else { dy += (4 - yweight[i]) * p.Y numy += 4 - yweight[i] } } result[i][0] = float64(dx) / float64(numx) result[i][1] = float64(dy) / float64(numy) } return result } func (region *Region) split(img image.Image) (*Region, *Region) { anchors := region.anchors() // maximize the difference between the average color on the two sides maxdiff := 0.0 var maxa *Region = nil var maxb *Region = nil maxanchor := 0 maxangle := 0 for anchor := 0; anchor < 4; anchor++ { for angle := 0; angle < 16; angle++ { sin, cos := math.Sincos(float64(angle) * math.Pi / 16.0) a := new(Region) b := new(Region) for _, p := range region.points { dx := float64(p.X) - anchors[anchor][0] dy := float64(p.Y) - anchors[anchor][1] if dx * sin + dy * cos >= 0 { a.points = append(a.points, p) } else { b.points = append(b.points, p) } } if len(a.points) == 0 || len(b.points) == 0 { continue } a_red, a_green, a_blue := a.meanColor(img) b_red, b_green, b_blue := b.meanColor(img) diff := math.Abs(a_red - b_red) + math.Abs(a_green - b_green) + math.Abs(a_blue - b_blue) if diff >= maxdiff { maxdiff = diff maxa = a maxb = b maxanchor = anchor maxangle = angle } } } region.anchor = maxanchor region.angle = maxangle region.children[0] = maxa region.children[1] = maxb return maxa, maxb } // split regions take 7 bits plus their descendents // unsplit regions take 13 bits // so each split saves 13-7=6 bits on the parent region // and costs 2*13 = 26 bits on the children, for a net of 20 bits/split func (region *Region) encode(img image.Image) []int { bits := make([]int, 0) if region.children[0] != nil { bits = append(bits, 1) d := region.anchor a := region.angle bits = append(bits, d&1, d>>1&1) bits = append(bits, a&1, a>>1&1, a>>2&1, a>>3&1) bits = append(bits, region.children[0].encode(img)...) bits = append(bits, region.children[1].encode(img)...) } else { bits = append(bits, 0) r, g, b := region.meanColor(img) kr := int(r/256./16.) kg := int(g/256./16.) kb := int(b/256./16.) bits = append(bits, kr&1, kr>>1&1, kr>>2&1, kr>>3) bits = append(bits, kg&1, kg>>1&1, kg>>2&1, kg>>3) bits = append(bits, kb&1, kb>>1&1, kb>>2&1, kb>>3) } return bits } func encode(name string) []byte { file, _ := os.Open(name) img, _, _ := image.Decode(file) // encoding bit stream bits := make([]int, 0) // start by encoding the bounds bounds := img.Bounds() w := bounds.Max.X - bounds.Min.X for ; w > 3; w >>= 1 { bits = append(bits, 1, w & 1) } bits = append(bits, 0, w & 1) h := bounds.Max.Y - bounds.Min.Y for ; h > 3; h >>= 1 { bits = append(bits, 1, h & 1) } bits = append(bits, 0, h & 1) // make new region containing whole image region := new(Region) region.children[0] = nil region.children[1] = nil for y := bounds.Min.Y; y < bounds.Max.Y; y++ { for x := bounds.Min.X; x < bounds.Max.X; x++ { region.points = append(region.points, image.Point{x, y}) } } // split the region with the most contrast until we're out of bits. regions := make([]*Region, 1) regions[0] = region for bitcnt := len(bits) + 13; bitcnt <= 919-20; bitcnt += 20 { var best_reg *Region best_dev := -1.0 for _, reg := range regions { if reg.children[0] != nil { continue } dev := reg.deviation(img) if dev > best_dev { best_reg = reg best_dev = dev } } a, b := best_reg.split(img) regions = append(regions, a, b) } // encode regions bits = append(bits, region.encode(img)...) // convert to tweet n := big.NewInt(0) for i := 0; i < len(bits); i++ { n.SetBit(n, i, uint(bits[i])) } s := make([]byte,0) r := new(big.Int) for i := 0; i < 140; i++ { n.DivMod(n, big.NewInt(95), r) s = append(s, byte(r.Int64() + 32)) } return s } // decodes and fills in region. returns number of bits used. func (region *Region) decode(bits []int, img *image.RGBA) int { if bits[0] == 1 { anchors := region.anchors() anchor := bits[1] + bits[2]*2 angle := bits[3] + bits[4]*2 + bits[5]*4 + bits[6]*8 sin, cos := math.Sincos(float64(angle) * math.Pi / 16.) a := new(Region) b := new(Region) for _, p := range region.points { dx := float64(p.X) - anchors[anchor][0] dy := float64(p.Y) - anchors[anchor][1] if dx * sin + dy * cos >= 0 { a.points = append(a.points, p) } else { b.points = append(b.points, p) } } x := a.decode(bits[7:], img) y := b.decode(bits[7+x:], img) return 7 + x + y } r := bits[1] + bits[2]*2 + bits[3]*4 + bits[4]*8 g := bits[5] + bits[6]*2 + bits[7]*4 + bits[8]*8 b := bits[9] + bits[10]*2 + bits[11]*4 + bits[12]*8 c := color.RGBA{uint8(r*16+8), uint8(g*16+8), uint8(b*16+8), 255} for _, p := range region.points { img.Set(p.X, p.Y, c) } return 13 } func decode(name string) image.Image { file, _ := os.Open(name) length, _ := file.Seek(0, 2) file.Seek(0, 0) tweet := make([]byte, length) file.Read(tweet) // convert to bit string n := big.NewInt(0) m := big.NewInt(1) for _, c := range tweet { v := big.NewInt(int64(c - 32)) v.Mul(v, m) n.Add(n, v) m.Mul(m, big.NewInt(95)) } bits := make([]int, 0) for ; n.Sign() != 0; { bits = append(bits, int(n.Int64() & 1)) n.Rsh(n, 1) } for ; len(bits) < 919; { bits = append(bits, 0) } // extract width and height w := 0 k := 1 for ; bits[0] == 1; { w += k * bits[1] k <<= 1 bits = bits[2:] } w += k * (2 + bits[1]) bits = bits[2:] h := 0 k = 1 for ; bits[0] == 1; { h += k * bits[1] k <<= 1 bits = bits[2:] } h += k * (2 + bits[1]) bits = bits[2:] // make new region containing whole image region := new(Region) region.children[0] = nil region.children[1] = nil for y := 0; y < h; y++ { for x := 0; x < w; x++ { region.points = append(region.points, image.Point{x, y}) } } // new image img := image.NewRGBA(image.Rectangle{image.Point{0, 0}, image.Point{w, h}}) // decode regions region.decode(bits, img) return img } func main() { if os.Args[1] == "encode" { s := encode(os.Args[2]) file, _ := os.Create(os.Args[3]) file.Write(s) file.Close() } if os.Args[1] == "decode" { img := decode(os.Args[2]) file, _ := os.Create(os.Args[3]) png.Encode(file, img) file.Close() } } • Dude, those look cool. – MrZander Apr 15 '13 at 22:24 • Oh Gosh that is AWESOME. – jdstankosky Apr 16 '13 at 1:19 • Wait, where's your strings? – jdstankosky Apr 16 '13 at 1:22 • This is my favorite so far. – primo Apr 16 '13 at 3:24 • +1 for the Cubist look. – Ilmari Karonen Dec 30 '13 at 17:12 ## Python Encoding requires numpy, SciPy and scikit-image. Decoding requires only PIL. This is a method based on superpixel interpolation. To begin, each image is divided into 70 similar sized regions of similar color. For example, the landscape picture is divided in the following manner: The centroid of each region is located (to the nearest raster point on a grid containing no more than 402 points), as well as it's average color (from a 216 color palette), and each of these regions is encoded as a number from 0 to 86832, capable of being stored in 2.5 printable ascii characters (actually 2.497, leaving just enough room to encode for a greyscale bit). If you're attentive, you may have noticed that 140 / 2.5 = 56 regions, and not 70 as I stated earlier. Notice, however, that each of these regions is a unique, comparable object, which may be listed in any order. Because of this, we can use the permutation of the first 56 regions to encode for the other 14, as well as having a few bits left over to store the aspect ratio. More specifically, each of the additional 14 regions is converted to a number, and then each of these numbers concatenated together (multiplying the current value by 86832, and adding the next). This (gigantic) number is then converted to a permutation on 56 objects. For example: from my_geom import * # this can be any value from 0 to 56!, and it will map unambiguously to a permutation num = 595132299344106583056657556772129922314933943196204990085065194829854239 perm = num2perm(num, 56) print perm print perm2num(perm) will output: [0, 3, 33, 13, 26, 22, 54, 12, 53, 47, 8, 39, 19, 51, 18, 27, 1, 41, 50, 20, 5, 29, 46, 9, 42, 23, 4, 37, 21, 49, 2, 6, 55, 52, 36, 7, 43, 11, 30, 10, 34, 44, 24, 45, 32, 28, 17, 35, 15, 25, 48, 40, 38, 31, 16, 14] 595132299344106583056657556772129922314933943196204990085065194829854239 The resulting permutation is then applied to the original 56 regions. The original number (and thus the additional 14 regions) can likewise be extracted by converting the permutation of the 56 encoded regions into its numerical representation. When the --greyscale option is used with the encoder, 94 regions are used instead (separated 70, 24), with 558 raster points, and 16 shades of grey. When decoding, each of these regions is treated as a 3D cone extended into infinity, with its vertex at the centroid of the region, as viewed from above (a.k.a. a Voronoi Diagram). The borders are then blended together to create the final product. ### Future Improvements 1. The dimensions of the Mona Lisa are a bit off, due to the way I'm storing the aspect ratio. I'll need to use a different system. Fixed, by assuming that the original aspect ratio is somewhere between 1:21 and 21:1, which I think is a reasonable assumption. 2. The Hindenburg could be improved a lot. The color palette I'm using only has 6 shades of grey. If I introduced a greyscale-only mode, I could use the extra information to increase the color depth, number of regions, number of raster points, or any combination of the three. I've added a --greyscale option to the encoder, which does all three. 3. 2d Shapes would probably look better with blending turned off. I'll likely add a flag for that. Added an encoder option to control the segmentation ratio, and a decoder option to turn off blending. 4. More fun with combinatorics. 56! is actually large enough to store 15 additional regions, and 15! is large enough to store 2 more for a grand total of 73. But wait, there's more! The partitioning of these 73 object could also be used to store more information. For example, there are 73 choose 56 ways to select the initial 56 regions, and then 17 choose 15 ways to select the next 15. A grand total of 2403922132944423072 partitionings, big enough to store 3 more regions for a total of 76. I'd need to come up with a clever way to uniquely number all partitions of 73 into groups of 56, 15, 2 ... and back. Perhaps not practical, but an interesting problem to think about. 0VW*Gnyq;c1JBY}tj#rOcKm)v_Ac\S.r[>,Xd_(qT6 >]!xOfU9~0jmIMG{hcg-'*a.s<X]6*%U5>/FOze?cPv@hI)PjpK9\iA7P ]a-7eC&ttS[]K>NwN-^$T1E.1OH^c0^"J 4V9X

0Jc?NsbD#1WDuqT]AJFELu<!iE3d!BB>jOA'L|<j!lCWXkr:gCXuD=D\BL{gA\ 8#*RKQ*tv\\3V0j;_4|o7>{Xage-N85):Q/Hl4.t&'0pp)d|Ry+?|xrA6u&2E!Ls]i]T<~)58%RiA

and

4PV 9G7X|}>pC[Czd!5&rA5 Eo1Q\+m5t:r#;H65NIggfkw'h4*gs.:~<bt'VuVL7V8Ed5{ft7e>HMHrVVUXc.{#7A|#PBm,i>1B781.K8>s(yUV?a<*!mC@9p+Rgd<twZ.wuFnN dp

The second one encoded with the --greyscale option.

3dVY3TY?9g+b7!5n)l"Fg H$8n?[Q-4HE3.c:[pBBaH5'MotAj%a4rIodYO.lp$h a94$n!M+Y?(eAR,@Y*LiKnz%s0rFpgnWy%!zV)?SuATmc~-ZQardp=?D5FWx;v=VA+]EJ(:% Encoded with the --greyscale option. .9l% Ge<'_)3(DTsH^eLn|l3.D_na,,sfcpnp{"|lSv<>}3b})%m2M)Ld{YUmf<Uill,*:QNGk,'f2; !2i88T:Yjqa8\Ktz4i@h2kHeC|9,P v7Xzd Yp&z:'iLra&X&-b(g6vMq Encoded with --ratio 60, and decoded with --no-blending options. encoder.py from __future__ import division import argparse, numpy from skimage.io import imread from skimage.transform import resize from skimage.segmentation import slic from skimage.measure import regionprops from my_geom import * def encode(filename, seg_ratio, greyscale): img = imread(filename) height = len(img) width = len(img[0]) ratio = width/height if greyscale: raster_size = 558 raster_ratio = 11 num_segs = 94 set1_len = 70 max_num = 8928 # 558 * 16 else: raster_size = 402 raster_ratio = 13 num_segs = 70 set1_len = 56 max_num = 86832 # 402 * 216 raster_width = (raster_size*ratio)**0.5 raster_height = int(raster_width/ratio) raster_width = int(raster_width) resize_height = raster_height * raster_ratio resize_width = raster_width * raster_ratio img = resize(img, (resize_height, resize_width)) segs = slic(img, n_segments=num_segs-4, ratio=seg_ratio).astype('int16') max_label = segs.max() numpy.place(segs, segs==0, [max_label+1]) regions = [None]*(max_label+2) for props in regionprops(segs): label = props['Label'] props['Greyscale'] = greyscale regions[label] = Region(props) for i, a in enumerate(regions): for j, b in enumerate(regions): if a==None or b==None or a==b: continue if a.centroid == b.centroid: numpy.place(segs, segs==j, [i]) regions[j] = None for y in range(resize_height): for x in range(resize_width): label = segs[y][x] regions[label].add_point(img[y][x]) regions = [r for r in regions if r != None] if len(regions)>num_segs: regions = sorted(regions, key=lambda r: r.area)[-num_segs:] regions = sorted(regions, key=lambda r: r.to_num(raster_width)) set1, set2 = regions[-set1_len:], regions[:-set1_len] set2_num = 0 for s in set2: set2_num *= max_num set2_num += s.to_num(raster_width) set2_num = ((set2_num*85 + raster_width)*85 + raster_height)*25 + len(set2) perm = num2perm(set2_num, set1_len) set1 = permute(set1, perm) outnum = 0 for r in set1: outnum *= max_num outnum += r.to_num(raster_width) outnum *= 2 outnum += greyscale outstr = '' for i in range(140): outstr = chr(32 + outnum%95) + outstr outnum //= 95 print outstr parser = argparse.ArgumentParser(description='Encodes an image into a tweetable format.') parser.add_argument('filename', type=str, help='The filename of the image to encode.') parser.add_argument('--ratio', dest='seg_ratio', type=float, default=30, help='The segmentation ratio. Higher values (50+) will result in more regular shapes, lower values in more regular region color.') parser.add_argument('--greyscale', dest='greyscale', action='store_true', help='Encode the image as greyscale.') args = parser.parse_args() encode(args.filename, args.seg_ratio, args.greyscale) decoder.py from __future__ import division import argparse from PIL import Image, ImageDraw, ImageChops, ImageFilter from my_geom import * def decode(instr, no_blending=False): innum = 0 for c in instr: innum *= 95 innum += ord(c) - 32 greyscale = innum%2 innum //= 2 if greyscale: max_num = 8928 set1_len = 70 image_mode = 'L' default_color = 0 raster_ratio = 11 else: max_num = 86832 set1_len = 56 image_mode = 'RGB' default_color = (0, 0, 0) raster_ratio = 13 nums = [] for i in range(set1_len): nums = [innum%max_num] + nums innum //= max_num set2_num = perm2num(nums) set2_len = set2_num%25 set2_num //= 25 raster_height = set2_num%85 set2_num //= 85 raster_width = set2_num%85 set2_num //= 85 resize_width = raster_width*raster_ratio resize_height = raster_height*raster_ratio for i in range(set2_len): nums += set2_num%max_num, set2_num //= max_num regions = [] for num in nums: r = Region() r.from_num(num, raster_width, greyscale) regions += r, masks = [] outimage = Image.new(image_mode, (resize_width, resize_height), default_color) for a in regions: mask = Image.new('L', (resize_width, resize_height), 255) for b in regions: if a==b: continue submask = Image.new('L', (resize_width, resize_height), 0) poly = a.centroid.bisected_poly(b.centroid, resize_width, resize_height) ImageDraw.Draw(submask).polygon(poly, fill=255, outline=255) mask = ImageChops.multiply(mask, submask) outimage.paste(a.avg_color, mask=mask) if not no_blending: outimage = outimage.resize((raster_width, raster_height), Image.ANTIALIAS) outimage = outimage.resize((resize_width, resize_height), Image.BICUBIC) smooth = ImageFilter.Kernel((3,3),(1,2,1,2,4,2,1,2,1)) for i in range(20):outimage = outimage.filter(smooth) outimage.show() parser = argparse.ArgumentParser(description='Decodes a tweet into and image.') parser.add_argument('--no-blending', dest='no_blending', action='store_true', help="Do not blend the borders in the final image.") args = parser.parse_args() instr = raw_input() decode(instr, args.no_blending) my_geom.py from __future__ import division class Point: def __init__(self, x, y): self.x = x self.y = y self.xy = (x, y) def __eq__(self, other): return self.x == other.x and self.y == other.y def __lt__(self, other): return self.y < other.y or (self.y == other.y and self.x < other.x) def inv_slope(self, other): return (other.x - self.x)/(self.y - other.y) def midpoint(self, other): return Point((self.x + other.x)/2, (self.y + other.y)/2) def dist2(self, other): dx = self.x - other.x dy = self.y - other.y return dx*dx + dy*dy def bisected_poly(self, other, resize_width, resize_height): midpoint = self.midpoint(other) points = [] if self.y == other.y: points += (midpoint.x, 0), (midpoint.x, resize_height) if self.x < midpoint.x: points += (0, resize_height), (0, 0) else: points += (resize_width, resize_height), (resize_width, 0) return points elif self.x == other.x: points += (0, midpoint.y), (resize_width, midpoint.y) if self.y < midpoint.y: points += (resize_width, 0), (0, 0) else: points += (resize_width, resize_height), (0, resize_height) return points slope = self.inv_slope(other) y_intercept = midpoint.y - slope*midpoint.x if self.y > midpoint.y: points += ((resize_height - y_intercept)/slope, resize_height), if slope < 0: points += (resize_width, slope*resize_width + y_intercept), (resize_width, resize_height) else: points += (0, y_intercept), (0, resize_height) else: points += (-y_intercept/slope, 0), if slope < 0: points += (0, y_intercept), (0, 0) else: points += (resize_width, slope*resize_width + y_intercept), (resize_width, 0) return points class Region: def __init__(self, props={}): if props: self.greyscale = props['Greyscale'] self.area = props['Area'] cy, cx = props['Centroid'] if self.greyscale: self.centroid = Point(int(cx/11)*11+5, int(cy/11)*11+5) else: self.centroid = Point(int(cx/13)*13+6, int(cy/13)*13+6) self.num_pixels = 0 self.r_total = 0 self.g_total = 0 self.b_total = 0 def __lt__(self, other): return self.centroid < other.centroid def add_point(self, rgb): r, g, b = rgb self.r_total += r self.g_total += g self.b_total += b self.num_pixels += 1 if self.greyscale: self.avg_color = int((3.2*self.r_total + 10.7*self.g_total + 1.1*self.b_total)/self.num_pixels + 0.5)*17 else: self.avg_color = ( int(5*self.r_total/self.num_pixels + 0.5)*51, int(5*self.g_total/self.num_pixels + 0.5)*51, int(5*self.b_total/self.num_pixels + 0.5)*51) def to_num(self, raster_width): if self.greyscale: raster_x = int((self.centroid.x - 5)/11) raster_y = int((self.centroid.y - 5)/11) return (raster_y*raster_width + raster_x)*16 + self.avg_color//17 else: r, g, b = self.avg_color r //= 51 g //= 51 b //= 51 raster_x = int((self.centroid.x - 6)/13) raster_y = int((self.centroid.y - 6)/13) return (raster_y*raster_width + raster_x)*216 + r*36 + g*6 + b def from_num(self, num, raster_width, greyscale): self.greyscale = greyscale if greyscale: self.avg_color = num%16*17 num //= 16 raster_x, raster_y = num%raster_width, num//raster_width self.centroid = Point(raster_x*11 + 5, raster_y*11+5) else: rgb = num%216 r, g, b = rgb//36, rgb//6%6, rgb%6 self.avg_color = (r*51, g*51, b*51) num //= 216 raster_x, raster_y = num%raster_width, num//raster_width self.centroid = Point(raster_x*13 + 6, raster_y*13 + 6) def perm2num(perm): num = 0 size = len(perm) for i in range(size): num *= size-i for j in range(i, size): num += perm[j]<perm[i] return num def num2perm(num, size): perm = [0]*size for i in range(size-1, -1, -1): perm[i] = int(num%(size-i)) num //= size-i for j in range(i+1, size): perm[j] += perm[j] >= perm[i] return perm def permute(arr, perm): size = len(arr) out = [0] * size for i in range(size): val = perm[i] out[i] = arr[val] return out • That's nothing short of amazing – lochok Apr 19 '13 at 4:59 • The color version of the Mona Lisa looks like one of her boobs popped. Jesting aside, this is incredible. – jdstankosky Apr 19 '13 at 13:47 • Using the permutations to encode additional data is rather clever. – Sir_Lagsalot Apr 23 '13 at 13:34 • Really really awesome. Can you make a gist with this 3 files? gist.github.com – rubik Apr 26 '13 at 10:17 • @rubik it is incredibly lossy, as are all of the solutions to this challenge ;) – primo Apr 26 '13 at 10:35 # PHP OK, took me a while, but here it is. All images in greyscale. Colors took too many bits to encode for my method :P Mona Lisa 47 Colors Monochrome 101 byte string. dt99vvv9t8G22+2eZbbf55v3+fAH9X+AD/0BAF6gIOX5QRy7xX8em9/UBAEVXKiiqKqqqiqqqqNqqqivtXqqMAFVUBVVVVVVVVVVU 2D Shapes 36 Colors Monochrome 105 byte string. oAAAAAAABMIDUAAEBAyoAAAAAgAwAAAAADYBtsAAAJIDbYAAAAA22AGwAAAAAGwAAAAAAAAAAKgAAAAAqgAAAACoAAAAAAAAAAAAAAAAA Hindenburg 62 Colors Monochrome 112 characters. t///tCSuvv/99tmwBI3/21U5gCW/+2bdDMxLf+r6VsaHb/tt7TAodv+NhtbFVX/bGD1IVq/4MAHbKq/4AABbVX/AQAFN1f8BCBFntb/6ttYdWnfg Mountains 63 Colors Monochrome 122 characters. qAE3VTkaIAKgqSFigAKoABgQEqAABuAgUQAGenRIBoUh2eqhABCee/2qSSAQntt/s2kJCQbf/bbaJgbWebzqsPZ7bZttwABTc3VAUFDbKqqpzY5uqpudnp5vZg My Method I encode my bitstream with a type of base64 encoding. Before it's encoded into readable text, here's what happens. I load the source image and resize it to a maximum height or width (depending on orientation, portrait/landscape) of 20 pixels. Next I recolor each pixel of the new image to it's closest match on a 6 color greyscale palette. After that's done, I create a string with each pixel color represented by the letters [A-F]. I then calculate the distribution of the 6 different letters within the string and select the most optimized binary tree for encoding based on the letter frequencies. There are 15 possible binary trees. I start my bit stream with a single bit, [1|0] depending on whether the image is tall or wide. I then use the next 4 bits in the stream to inform the decoder which binary tree should be used to decode the image. What follows is the stream of bits representing the image. Each pixel and it's color is represented by either 2 or 3 bits. This allows me to store at least 2 and up to 3 pixels worth of information for every printed ascii character. Here's a sample of binary tree 1110, which is used by the Mona Lisa: TREE / \ # # / \ / \ E # F # / \ / \ A B C D The letters E 00 and F 10 are the most common colors in the Mona Lisa. A 010, B 011, C 110, and D 111 are the least frequent. Binary trees work like this: Going from bit to bit, 0 means go left, 1 means go right. Keep going until you hit a leaf on the tree, or a dead end. The leaf you end up on is the character you want. Anyways, I encode the binary sting into base64 characters. When decoding the string, the process is done in reverse, assigning all the pixels to the appropriate color, and then the image is scaled twice the encoded size (maximum 40 pixels either X or Y, whichever is larger) and then a convolution matrix is applied to the whole thing to smooth out the colors. Anyways, here's the current code: "pastebin link" It's ugly, but if you see any room for improvements, let me know. I hacked it together as I want along. I LEARNED A LOT FROM THIS CHALLENGE. Thank you OP for posting it! • These look incredibly good considering how much unutilized storage space you have (Mona Lisa uses only 606 bits from 920 available!). – primo Apr 25 '13 at 3:49 • Thank you, primo, I truly appreciate that. I always admire your work, so hearing you say that is quite flattering! – jdstankosky Apr 26 '13 at 13:20 My first attempt. This has room for improvement. I think that the format itself actually works, the issue is in the encoder. That, and I'm missing individual bits from my output... my (slightly higher quality then here) file ended up at 144 characters, when there should have been some left. (and I really wish there was - the differences between these and those are noticeable). I learnt though, never overestimate how big 140 characters is... I bring it down to a modified version of the RISC-OS palette - basically, because I needed a 32 colour palette, and that seemed like a good enough place to start. This could do with some changing too I think. I break it down into the following shapes: and split the image into palette blocks (in this case, 2x2 pixels) of a front and back color. ## Results: Following are the tweets, the originals and how the tweet is decoded *=If$aX:=|"&brQ(EPZwxu4H";|-^;lhJCfQ(W!TqWTai),Qbd7CCtmoc(-hXt]/l87HQyaYTEZp{eI/CtkHjkFh,HJWw%5[d}VhHAWR(@;M's$VDz]17E@6 "&7tpnqK%D5kr^u9B]^3?%;@siWp-L@1g3p^*kQ=5a0tBsA':C0"*QHVDc=Z='Gc[gOpVcOj;_%>.aeg+JL4j-u[a$WWD^)\tEQUhR]HVD5_-eTobI@T0dv_el\H1<1xw[|D

)eyymlgre[rzzfi"K>#^=z_Wi|@FWbo#V5|@F)uiH?plkRS#-5:Yi-9)S3:#3 Pa4*lf TBd@zxa0g;li<O1XJ)YTT77T1Dg1?[w;X"U}YnQE(NAMQa2QhTMYh..>90DpnYd]?

## Mona Lisa

=lyZ(i>P/z8]Wmfu>] T55vZB:/>xMz#Jqs6U3z,)n|VJw<{Mu2D{!uyl)b7B6x&I"G0Y<wdD/K4hfrd62_8C\W7ArNi6R\Xz%f U[);YTZFliUEu{m%[gw10rNY_ICNN?_IB/C&=T

## Mountains

+L5#~i%X1aE?ugVCulSf*%-sgIg8hQ3j/df=xZv2v?'XoNdq=sb7e '=LWm\E$y?=:"#l7/P,H__W/v]@pwH#jI?sx|n@h\L %y(|Ry.+CvlN$Kf5W(01l2j/sdEjc)J;Peopo)HJ

## Shapes

3A"3yD4gpFtPeIImZ$g&2rsdQmj]}gEQM;e.ckbVtKE(U$r?{,S>tW5JzQZDzoTy^mc+bUV vTUG8GXs{HX'wYR[Af{1gKwY|BD]V1Z'J+76^H<K3Db>Ni/D}][n#uwll[s'c:bR56:

Here's the program. python compress.py -c img.png compresses img.png and prints the tweet.

python compress.py -d img.png takes the tweet from stdin and saves the image to img.png.

from PIL import Image
import sys
quanta  = 3
width   = 24
height  = 24

def compress(img):
psums = [0]*(256*3)
for x in range(width):
for y in range(height):
r,g,b,a = pix[x,y]
psums[r+g+b] += 1
s = 0
for i in range(256*3):
s = psums[i] = psums[i]+s

i = 0
for x in range(width):
for y in range(height):
r,g,b,a = pix[x,y]
t = psums[r+g+b]*quanta / (width*height)
if t == quanta:
t -= 1
i *= quanta
i += t
s = []
while i:
s += chr(i%95 + 32)
i /= 95
return ''.join(s)

def decompress(s):
i = 0
for c in s[::-1]:
i *= 95
i += ord(c) - 32
img = Image.new('RGB',(width,height))
for x in range(width)[::-1]:
for y in range(height)[::-1]:
t = i % quanta
i /= quanta
t *= 255/(quanta-1)
pix[x,y] = (t,t,t)
return img

if sys.argv[1] == '-c':
img = Image.open(sys.argv[2]).resize((width,height))
print compress(img)
elif sys.argv[1] == '-d':
img = decompress(raw_input())
img.resize((256,256)).save(sys.argv[2],'PNG')
• Lol, +1 for non-constrained aspect ratios. – jdstankosky Apr 16 '13 at 14:41

My modest contribution in R:

encoder<-function(img_file){
d0 <- dim(img0)
r <- d0[1]/d0[2]
f <- floor(sqrt(140/r))
d1 <- c(floor(f*r),f)
dx <- floor(d0[2]/d1[2])
dy <- floor(d0[1]/d1[1])
img1 <- matrix("",ncol=d1[2],nrow=d1[1])
x<-seq(1,d0[1],by=dy)
y<-seq(1,d0[2],by=dx)
for(i in seq_len(d1[1])){
for (j in seq_len(d1[2])){
img1[i,j]<-names(which.max(table(img0[x[i]:(x[i]+dy-1),y[j]:(y[j]+dx-1)])))
}
}
img2 <- as.vector(img1)
table1 <- array(sapply(seq(0,255,length=4),function(x)sapply(seq(0,255,length=4),function(y)sapply(seq(0,255,length=4),function(z)rgb(x/255,y/255,z/255)))),dim=c(4,4,4))
table2 <- array(strsplit(rawToChar(as.raw(48:(48+63))),"")[[1]],dim=c(4,4,4))
table3 <- cbind(1:95,sapply(32:126,function(x)rawToChar(as.raw(x))))
a <- as.array(cut(colorspace::hex2RGB(img2)@coords,breaks=seq(0,1,length=5),include.lowest=TRUE))
dim(a) <- c(length(img2),3)
img3 <- apply(a,1,function(x)paste("#",c("00","55","AA","FF")[x[1]],c("00","55","AA","FF")[x[2]],c("00","55","AA","FF")[x[3]],sep=""))
res<-paste(sapply(img3,function(x)table2[table1==x]),sep="",collapse="")
paste(table3[table3[,1]==d1[1],2],table3[table3[,1]==d1[2],2],res,collapse="",sep="")
}

decoder<-function(string){
s <- unlist(strsplit(string,""))
table1 <- array(sapply(seq(0,255,length=4),function(x)sapply(seq(0,255,length=4),function(y)sapply(seq(0,255,length=4),function(z)rgb(x/255,y/255,z/255)))),dim=c(4,4,4))
table2 <- array(strsplit(rawToChar(as.raw(48:(48+63))),"")[[1]],dim=c(4,4,4))
table3 <- cbind(1:95,sapply(32:126,function(x)rawToChar(as.raw(x))))
nr<-as.integer(table3[table3[,2]==s[1],1])
nc<-as.integer(table3[table3[,2]==s[2],1])
img <- sapply(s[3:length(s)],function(x){table1[table2==x]})
png(w=nc,h=nr,u="in",res=100)
par(mar=rep(0,4))
plot(c(1,nr),c(1,nc),type="n",axes=F,xaxs="i",yaxs="i")
rasterImage(as.raster(matrix(img,nr,nc)),1,1,nr,nc)
dev.off()
}

The idea is simply to reduce the raster (file has to be in png) to a matrix whose number of cell is lower than 140, the tweets is then a serie of colors (in 64 colors) preceded by two characters indicated the number of rows and columns of the raster.

encoder("Mona_Lisa.png")
[1] ",(XXX000@000000XYi@000000000TXi0000000000TX0000m000h00T0hT@hm000000T000000000000XX00000000000XXi0000000000TXX0000000000"

encoder("630x418.png") # Not a huge success for this one :)
[1] "(-00000000000000000000EEZZooo00E0ZZooo00Z00Zooo00Zo0oooooEZ0EEZoooooooEZo0oooooo000ooZ0Eo0000oooE0EE00oooEEEE0000000E00000000000"

encoder("2d shapes.png")
[1] "(,oooooooooooooooooooooooooo0ooooooooooo33ooooooo33oo0ooooooooooo>>oooo0oooooooo0ooooooooooooolloooo9oolooooooooooo"

encoder("mountains.png")
[1] "(,_K_K0005:_KKK0005:__OJJ006:_oKKK00O:;;_K[[4OD;;Kooo4_DOKK_o^D_4KKKJ_o5o4KK__oo4_0;K___o5JDo____o5Y0____440444040400D4"

Not a complete solution, just putting the method out there. (Matlab)

I used a 16 color palette and 40 position to create a weighted voronoi diagram. Used genetic algorithm and simple hill-climbing algorithm to fit the image.

Album with original image and I also have a 16 byte version with 4 colors and fixed positions there. :)

(Can I resize image here?)

• Can you post the other images? I wanna see what they look like with this compression! – jdstankosky Apr 17 '13 at 12:41
• @jdstankosky Sorry, I can't do it now. Maybe some time later... – randomra Apr 17 '13 at 22:24

# Update - Version 2

I made another attempt at this, now using MagickImage.NET(https://magick.codeplex.com/) to encode the JPEG data, I also wrote some basic code to better process JPEG header data(as primo suggested), I also used GuassianBlur on the output which help soften some of the JPEG compression. As the new version preforms better, I've updated my post to reflect the new method.

# Method

I've tried something unique(hopefully), rather than trying to manipulate the color depth, or edge identification, or trying to use different ways to reduce the images size myself I've used the JPEG algorithm at maximum compression on scaled down versions of the images, then by eliminating everything but the "StartOfScan"(http://en.wikipedia.org/wiki/JPEG#Syntax_and_structure) and a few key header elements I'm able to get the size down to a acceptable amount. The results are actually pretty impressive for 140 characters, gives me a new found respect for JPEG's:

## Hindenburg

,$"(b$!   _ &4j6k3Qg2ns2"::4]*;12T|4z*4n*4<T~a4- ZT_%-.13YZT;??e#=*!Q033*5>z?1Ur;?2i2^j&r4TTuZe2444b*:>z7.:2m-*.z?|*-Pq|*,^Qs<m&?:e--

## Mountains

,$(a,! (1 Q$ /P!U%%%,0b*2nr4 %)3t4 +3#UsZf3S2 7-+m1Yqis k2U'm/#"h q2T4#$s.]/)%1T &*,4Ze w$Q2Xqm&: %Q28qiqm Q,48Xq12 _

## Mona Lisa

23  (a,!  (1 Q$/P q1Q2Tc$q0,$9--/!p Ze&:6#*,Tj6l0qT%(:!m!%(84|TVk0(*2k24P)!e(U,q2x84|Tj*8a1a-%**$r4_--Xr&)12Tj8a2Tj* %r444 %%%% !

(ep 1# ,!  (1 Q$/P"2#=WTp$X[4 &[Vp p<T +0 cP* 0W=["jY5cZ9(4 (<]t  ]Z %ZT -P!18=V+UZ4" #% i6%r}#"l p QP>*r $!Yq(!]2 jo* zp!0 4 % !0 4 % '! # Code ## Version 2 - http://pastebin.com/Tgr8XZUQ I'm really starting to miss ReSharper + I have allot of things to improve, still allot of hard coding going on here, interesting to mess with though(remember you need MagickImage dll's to get this to run in VS) ## Original(Deprecated) - http://pastebin.com/BDPT0BKT Still bit of a mess. • "This is really a mess right now," I'll agree with that - surely there must be a better way to generate that header? But I suppose results are what matter most. +1 – primo Sep 29 '14 at 10:42 ## Python 3 # Method What the program does first is scaling down the image, greatly decreasing its size. Second, it converts the rgb values into binary, and snips off the last few digits. Then it converts the base 2 data into base 10, where it adds the dimensions of the picture. Then it converts the data in base 10 to base 95, using all the ascii I could find. However, I could not use /x01 and the like because of its ability to negate the function that wrote out the text file. And (for added ambiguity), the decode function does it in reverse. # compress.py from PIL import Image def FromBase(digits, b): #converts to base 10 from base b numerals='''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_-+={[}]|:;"',<.>/?~\\ '''
D=[]
for d in range(0,len(digits)):
D.append(numerals.index(digits[d]))
s=0
D=D[::-1]
for x in range(0,len(D)):
s+=D[x]*(b**x)
return(str(s))
def ToBase(digits,b): #converts from base 10 to base b
numerals='''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_-+={[}]|:;"',<.>/?~\\ ''' d=int(digits) D='' B=b while(B<=d): B*=b B//=b while(B>=1): D+=numerals[d//B] d-=((d//B)*B) B//=b return(D) im=Image.open('1.png') size=im.size scale_factor=40 im=im.resize((int(size[0]/scale_factor),int(size[1]/scale_factor)), Image.ANTIALIAS) a=list(im.getdata()) K='' for x in a: for y in range(0,3): Y=bin(x[y])[2:] while(len(Y))<9: Y='0'+Y K+=str(Y)[:-5] K='1'+K print(len(K)) K=FromBase(K,2) K+=str(size[0]) K+=str(size[1]) K=ToBase(K,95) with open('1.txt', 'w') as outfile: outfile.write(K) # decode.py from random import randint, uniform from PIL import Image, ImageFilter import math import json def FromBase(digits, b): #str converts to base 10 from base b numerals='''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_-+={[}]|:;"',<.>/?~\\ \x01\x02\x03\x04\x05\x06\x07'''
D=[]
for d in range(0,len(digits)):
D.append(numerals.index(digits[d]))
s=0
D=D[::-1]
for x in range(0,len(D)):
s+=D[x]*(b**x)
return(str(s))
def ToBase(digits,b): #str converts from base 10 to base b

# Mona Lisa

f4*_!/J7L?,Nd\#q$[f}Z;'NB[vW%H<%#rL_v4l_K_ >gyLMKf; q9]T8r51it$/e~J{ul+9<*nX0!8-eJVB86gh|:4lsCumY4^y,c%e(e3>sv(.y>S8Ve.tu<v}Ww=AOLrWuQ)

# Spheres

})|VF/h2i\(D?Vgl4LF^0+zt$d}<M7E5pTA+=Hr}{VxNs m7Y~\NLc3Q"-<|;sSPyvB[?-B6~/ZHaveyH%|%xGi[Vd*SPJ>9)MKDOsz#zNS4$v?qM'XVe6z\