StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>My full solution can be found at <a href="http://caca.zoy.org/wiki/img2twit"><a href="http://caca.zoy.org/wiki/img2twit">http://caca.zoy.org/wiki/img2twit</a></a>. It has the following features:</p> <ul><li>Reasonable compression time (around 1 minute for high quality)</li> <li>Fast decompression (a fraction of a second)</li> <li>Keeps the original image size (not just the aspect ratio)</li> <li>Decent reconstruction quality (IMHO)</li> <li>Message length and character set (ASCII, CJK, Symbols) can be chosen at runtime</li> <li>Message length and character set are autodetected at decompression time</li> <li>Very efficient information packing</li> </ul> <blockquote> <p><a href="http://caca.zoy.org/raw-attachment/wiki/img2twit/so-logo.png">http://caca.zoy.org/raw-attachment/wiki/img2twit/so-logo.png</a> <a href="http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter4.png">http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter4.png</a></p> <p>蜥秓鋖筷聝诿缰偺腶漷庯祩皙靊谪獜岨幻寤厎趆脘搇梄踥桻理戂溥欇渹裏軱骿苸髙骟市簶璨粭浧鱉捕弫潮衍蚙瀹岚玧霫鏓蓕戲債鼶襋躻弯袮足庭侅旍凼飙驅據嘛掔倾诗籂阉嶹婻椿糢墤渽緛赐更儅棫武婩縑逡荨璙杯翉珸齸陁颗鳣憫擲舥攩寉鈶兓庭璱篂鰀乾丕耓庁錸努樀肝亖弜喆蝞躐葌熲谎蛪曟暙刍镶媏嘝驌慸盂氤缰殾譑 </p> </blockquote> <p>Here is a rough overview of the encoding process:</p> <ul> <li>The number of available bits is computed from desired message length and usable charset</li> <li>The source image is segmented into as many square cells as the available bits permit</li> <li>A fixed number of points (currently 2) is affected to each cell, with initial coordinates and colour values</li> <li>The following is repeated until a quality condition is met: <ul><li> A point is chosen a random </li> <li> An operation is performed at random on this point (moving it inside its cell, changing its colour)</li> <li> If the resulting image (see the decoding process below) is closer to the source image, the operation is kept </li> </ul></li> <li>The image size and list of points is encoded in UTF-8 </li> </ul> <p>And this is the decoding process:</p> <ul> <li>The image size and points are read from the UTF-8 stream</li> <li>For each pixel in the destination image: <ul><li> The list of natural neigbours is computed </li> <li> The pixel's final colour is set as a weighted average of its natural neighbours' colours </li></ul> </li> </ul> <p>What I believe is the most original part of the program is the bitstream. Instead of packing bit-aligned values (<code>stream <<= shift; stream |= value</code>), I pack arbitrary values that are not in power-of-two ranges (<code>stream *= range; stream += value</code>). This requires bignum computations and is of course a lot slower, but it gives me 2009.18 bits instead of 1960 when using the 20902 main CJK characters (that's three more points I can put in the data). And when using ASCII, it gives me 917.64 bits instead of 840.</p> <p>I decided against a method for the initial image computation that would have required heavy weaponry (corner detection, feature extraction, colour quantisation...) because I wasn't sure at first it would really help. Now I realise convergence is slow (1 minute is acceptable but it's slow nonetheless) and I may try to improve on that.</p> <p>The main fitting loop is loosely inspired from the Direct Binary Seach dithering algorithm (where pixels are randomly swapped or flipped until a better halftone is obtained). The energy computation is a simple root-mean-square distance, but I perform a 5x5 median filter on the original image first. A Gaussian blur would probably better represent the human eye behaviour, but I didn't want to lose sharp edges. I also decided against simulated annealing or other difficult to tune methods because I don't have months to calibrate the process. Thus the "quality" flag just represents the number of iterations that are performed on each point before the encoder ends.</p> <blockquote> <p><a href="http://caca.zoy.org/raw-attachment/wiki/img2twit/Mona_Lisa_scaled.jpg">http://caca.zoy.org/raw-attachment/wiki/img2twit/Mona_Lisa_scaled.jpg</a> <a href="http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter2.png">http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter2.png</a></p> <p>苉憗揣嶕繠剳腏篮濕茝霮墧蒆棌杚蓳縳樟赒肴飗噹砃燋任朓峂釰靂陴貜犟掝喗讄荛砙矺敨鷾瓔亨髎芟氲簵鸬嫤鉸俇激躙憮鄴甮槺骳佛愚猪駪惾嫥綖珏矯坼堭颽箽赭飉訥偁箝窂蹻熛漧衆橼愀航玴毡裋頢羔恺墎嬔鑹楄瑥鶼呍蕖抲鸝秓苾绒酯嵞脔婺污囉酼俵菛琪棺则辩曚鸸職銛蒝礭鱚蟺稿纡醾陴鳣尥蟀惘鋁髚忩祤脤养趯沅况</p> </blockquote> <p>Even though not all images compress well, I'm surprised by the results and I really wonder what other methods exist that can compress an image to 250 bytes.</p> <p>I also have small movies of the encoder state's evolution <a href="http://people.zoy.org/~sam/twitter-random.ogm">from a random initial state</a> and <a href="http://people.zoy.org/~sam/twitter-good.ogm">from a "good" initial state</a>.</p> <p><strong>Edit</strong>: here is how the compression method compares with JPEG. On the left, jamoes's above 536-byte picture. On the right, Mona Lisa compressed down to 534 bytes using the method described here (the bytes mentioned here refer to data bytes, therefore ignoring bits wasted by using Unicode characters):</p> <blockquote> <p><a href="http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona.jpg">http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona.jpg</a> <a href="http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona2.png">http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona2.png</a></p> </blockquote> <p><strong>Edit</strong>: just replaced CJK text with the newest versions of the images.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload