[Richard Suchenwirth] 2004-09-02 - Discussion in the [Tcl chatroom] brought me to propose this challenge for a Tcl contest: * Given a set of moderate-sized black&white GIF images, * write a pair of encoder/decoder between photo image and a binary string * so that the decoding of the encoded image is equal to the original (lossless) * and the average length of the encoded strings is minimal I prefer GIF here because it is lossless in itself, and can be read in by plain Tk. Bitmap images cannot be processed pixel-by-pixel, so they're excluded, although they're binary. Test images (feel free to add more. The GIF file size is the initial target to beat): courier12.gif - 1923 bytes: [WikiDbImage courier12.gif] times12i.gif - 1947 bytes: [WikiDbImage times12i.gif] castle.gif - 11598 bytes [http://www.100dollarhamburger.com/castle.gif] ouster.gif - 2775 bytes [http://tcl.sf.net/tct/kennykb/ouster.gif] The following image appears to need different compression techniques from the ones that contributors have examined so far: cat.gif - 11502 bytes [http://tcl.sf.net/tct/kennykb/wiki.tcl.tk/cat.gif] Another text image variant: oldeng16.gif - 4068 bytes [WikiDbImage oldeng16.gif] ---- '''Scoreboard''' The following table summarizes the file sizes from the various solutions: %| Entry | courier12 | times12i | castle | ouster | cat | oldeng16 |% &| Uncompressed | 19034 | 14618 | 127884 | 17404 | 180108 | 28010 |& &| [GIF] | 1677 | 1649 | 11598 | 2775 | 11645 | 2487 |& &| PS1 | 720 | 834 | 13672 ||||& &| PS2 | 671 | 718 | 11442 ||||& &| kroc | 902 | 885 | 15288 | 2610 | 30769 | 1989 |& &| KBK | 685 | 682 | 9260 | 1856 | 32368 | 1274 |& &| MS1 | 2163 | 1611 | 15763 | 1957 | 22291 | 3286 |& &| MS2 | 985 | 948 | 11542 | 1775 | 11146 | 1802 |& &| RS | 585 | 586 | 9993 | 1613 | 18633 | 1348 |& &| RHS | 1199 | 1126 | 14484 | 2592 | 30287 | 1956 |& %| | | | | | | |% &| MS1+gzip | 660 | 683 | 10234 | 1617 | 7740 | 1241 |& &| KBK2+gzip | 699 | 709 | 9273 | 1571 | 7491 | 1273 |& &| RHS+gzip | 725 | 983 | 9663 | 2207 | 7230 | 1541 |& * Uncompressed image is for reference (TIF). * GIF compression is also for reference * ''PS1'' and ''PS2'' - [Binary image compression challenge - Pascal's entry] * ''kroc'' - [Binary image compression challenge - Kroc's Entry] * ''KBK'' - [Binary image compression challenge - KBK's entry] * ''KBK2'' - The ''hilbert'' procedure from KBK's entry is used to produce a bit stream that is then piped through [gzip]. * ''MS1'' - [Binary image compression challenge - mig's entry] * ''MS2'' - [Binary image compression challenge - MS's entry] * ''RS'' - [Binary image compression challenge - RS's entry] * ''RHS'' - [RHS]s claims on this page. * ''DKF'' - [Binary image compression challenge - DKF's trials] '''Note''': MS1 is essentially "no compression", ie, it contains 1 bit ber pixel. ---- Links to solutions to this challenge: [PS] My you can find my attempt on [Binary image compression challenge - Pascal's Entry]. It compresses courier12.gif to 720 bytes and times12.gif to 834 bytes. Castle.gif is actually a compressed gif file! Mine 'compressed' to 13672... [PS] Update 4sept2004: Attempt number two (second code block on my entry page): now with Huffman(?) encoding for runlengths which occur 5 or more times. This actually compresses castle.gif! My new size is 11442 bytes, which is 156 bytes less than the original file! courier12 compresses to 671 bytes, times12i compresses to 718... ---- Little helpers to compare and tally photo images: proc photo'eq {im1 im2} { #-- returns 1 if both images are exactly equal, else 0 set h [image height $im1] if {[image height $im2] != $h} {return 0} set w [image width $im1] if {[image width $im2] != $w} {return 0} for {set y 0} {$y<$h} {incr y} { for {set x 0} {$x<$w} {incr x} { if {[$im1 get $x $y] ne [$im2 get $x $y]} {return 0} } } return 1 } See [photo image equality in Critcl] for faster ways to compare images... proc photo'colors img { #-- return a list of {{r g b} n} tallies of pixel colors, #-- sorted decreasing by n (number of pixels of that color) set h [image height $img] set w [image width $img] for {set y 0} {$y<$h} {incr y} { for {set x 0} {$x<$w} {incr x} { set color [$img get $x $y] if {![info exists a($color)]} {set a($color) 0} incr a($color) } } foreach {color n} [array get a] {lappend tally [list $color $n]} lsort -decreasing -index 1 -integer $tally } ---- [JH]: Here is my solution, which doesn't compression at all (doesn't beat the GIF format, but is close, the 1923b becomes 2163b). It just represents the data in a small, raw form, but not compressed. It will hopefully provide someone with a starting point to apply compression. ''[MS]: castle.gif is 'compressed' to 15764b by this; gzip reduces that file to 10305b.'' proc binimg'encode img { set clrs [photo'colors $img] if {[llength $clrs] != 2} { return -code error "not a 2 color image" } set clr0 [lindex $clrs 0 0] set clr1 [lindex $clrs 1 0] set h [image height $img] set w [image width $img] set str "" for {set y 0} {$y<$h} {incr y} { for {set x 0} {$x<$w} {incr x} { set color [$img get $x $y] append str [string equal $color $clr1] } } foreach {r g b} $clr0 { set color0 [expr {$r<<16 | $g <<8 | $b}]; break } foreach {r g b} $clr1 { set color1 [expr {$r<<16 | $g <<8 | $b}]; break } # store image as where w and h are shorts set binstr [binary format ssiib* $w $h $color0 $color1 $str] return $binstr } proc binimg'decode data { binary scan $data ssiib* w h color0 color1 clrs set img [image create photo -width $w -height $h] set clr(0) \#[format %.6x $color0] set clr(1) \#[format %.6x $color1] set i 0 set data "" set line "" foreach c [split $clrs {}] { lappend line $clr($c) if {[incr i] eq $w} { set i 0 lappend data $line set line "" } } $img put $data -to 0 0 return $img } See [Binary image compression challenge - mig's Entry] for a slight variant of this, which ''should'' compress better in general. ---- [DKF]: The simplest cheat way is to use ''gzip'' to compress the GIF files themselves! Both images compress to somewhere in the region of 1600-1650 bytes. Can you do better? [MS]: Yes; gzip'ing Jeff's coded files reduces the thing to 640-654 bytes. ---- [kroc]: My attempt, based on RLE is here: [Binary image compression challenge - Kroc's Entry]. It doesn't compress very well but it's fast: 3.1 seconds only for cat.gif ---- [KBK]: I'm putting another attempt over at [Binary image compression challenge - KBK's entry]. It outperforms [PS]'s entry on two of the three test cases, and does only slightly worse on the third. It's smaller than the GIF in all cases. It's not much worse than JH's solution postprocessed through gzip on the text images, and a good bit better on the dithered photograph and line art. * 685 bytes for courier12.gif (vs. 671 for PS's solution) * 682 bytes for times12i.gif (vs. 718) * 9260 bytes for castle.gif (vs. 11442) * 1856 bytes for ouster.gif The way it works is that it marches through the image along the [Hilbert curve]. The advantage to the Hilbert curve as opposed to a raster pattern is that areas of a solid color are likely to result in runs that are much longer than a scan line, even though the other color is present in the same row and column. The sky in the castle picture or the jacket in Ousterhout's portrait are converted to only a few long runs of 0 and 1. Once the data are ordered in Hilbert-curve sequence, they are converted to a set of run lengths; note that since runs of 0 and 1 will alternate, the run lengths are all that's needed; the colors are not stored explicitly. The run lengths are arbitrarily limited to 127; longer runs are broken into pieces with dummy 0-length runs in between. Finally, [Huffman coding] is used to make the run lengths into a string of bits. Decoding is the same process, only in reverse; the Huffman bit sequences are expanded into run lengths and then to a bit string, and the bit string is folded along the Hilbert curve to yield the image again. Compression is, of course, lossless. ---- [MS] has an entry using [Fibonacci coding] at [Binary image compression challenge - MS's Entry]. The results are * 985 bytes for courier12.gif (not too good) * 948 bytes for times12i.gif (not too good) * 11542 bytes for castle.gif (not too shabby) * 1775 bytes for ouster.gif (looking good) * 11146 bytes for cat.gif A better variant awaiting an implementation of [Arithmetic coding]. ---- [RHS] I some fun implementing a variable length RLE scheme (ie, the bits used for the runlength encoding varied by file depending on the best size for the file). I also made it check both horizontal and vertical encodings, to see which worked best, which turned out to be vertical in almost every case. My results were: * castle.gif - 14484 (9663 gzipped) * cat.gif - 30287 (7230 gzipped) * courier12.gif - 1199 (725 gzipped) * ouster.gid - 2592 (2207 gzipped) * times12i.gif - 1126 (983 gzipped) * oldeng16.gif - 1956 (1541 gzipped) ---- [TV] Normal unix like thinking would make me want to have a simple binary version of an image like the courier12.gif example, and then do heavy duty compression on that, which should be ok enough, trying that I saved the image using [gimp] in bmp format (which still leaves a (little ?) header I think) to get the pixels in bytes and then on a row, and used the open source gzip, but ''with'' the --best option on this data, to get: * courier12.gif - 605 gzipped bmp , in about 20 milliseconds coding time I'm sure reordering bits in patterns corresponding with letters before using some general compressor will improve this. Realizing that the challenge is about tcl programming, too, I first only have to offer that I use a jpeg2000 program in a tcl and bwise frame, which at least makes for some insight in [Binary image compression challenge - Theo Verelst's entry]. ---- [Arts and crafts of Tcl-Tk programming] - [Category Compression]