Encode Images into Tweets (Extreme Image Compression Edition)
I've improved my method by adding actual compression. It now operates by iteratively doing the following:


Convert the image to YUV
Downsize the image preserving the aspect ratio (if the image is color, the chroma is sampled at 1/3 the width &amp; height of the luminance)
Reduce the bit depth to 4 bits per sample
Apply median prediction to the image, making the sample distribution more uniform
Apply adaptive range compression to the image.
See if the size of the compressed image is &lt;= 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 &amp; 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 &amp; dirty C++ source

Windows exe

Mona Lisa (13x20 luminance, 4x6 chroma)

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


 

Hindenburg (21x13 luminance)

GmL&lt;B&amp;ep^m40dPs%V[4&amp;"~F[Yt-sNceB6L&gt;Cs#/bv`\4{TB_P Rr7Pjdk7}&lt;*&lt;{2=gssBkR$&gt;!['ROG6Xs{AEtnP=OWDP6&amp;h{^l+LbLr4%R{15Zc&lt;D?J6&lt;'#E.(W*?"d9wdJ'       


 

Mountains (19x14 luminance, 6x4 chroma)

Y\Twg]~KC((s_P&gt;,*cePOTM_X7ZNMHhI,WeN(m&gt;"dVT{+cXc?8n,&amp;m$TUT&amp;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&lt;Fv8mD}2LL!g_(~CO&amp;MG+u&gt;&lt;-jT#{KXJy/``#S@m26CQ=[zejo,gFk0}A%i4kE]N ?R~^8!Ki*KM52u,M(his+BxqDCgU&gt;ul*N9tNb\lfg}}n@HhX77S@TZf{k&lt;CO69!