Updated 2011-12-13 11:07:22 by dkf ▲

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:

times12i.gif - 1947 bytes:

castle.gif - 11598 bytes

ouster.gif - 2775 bytes

The following image appears to need different compression techniques from the ones that contributors have examined so far:

cat.gif - 11502 bytes

Another text image variant: oldeng16.gif - 4068 bytes

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
LH 1450 1522 27053 3999 11105 2639
MS1+gzip 660 683 10234 1617 7740 1241
KBK2+gzip 699 709 9273 1571 7491 1273
RHS+gzip 725 983 9663 2207 7230 1541

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 <w><h><clr0><clr1><binimgdata> 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 programmingCategory Compression