Adventures in Dithering: Making some gray in a sea of black and white

Yesterday I implemented support for printing images in my DropPrint Android app. One issue with the printer is the range of values it prints: mainly it has none. As they say: you can have any color you want, as long as it's black. So a typical photo, which is filled with all sorts of grays, gets turned in a photo filled only with black and white. Like this one:

In some cases this effect may be desirable, but I was curious if I could leverage the halftone effect to simulate shades of gray. With a halftone you trick the eye into seeing gray by by varying the mixture of white and black dots. One Google search told me that while halftoning may get the job done, there's another important option to consider:

If you are doing this because you like the effect, that's cool. But if you just want to dither down to a black and white image consider using a "Floyd-Steinberg" dither. It provides high quality results and distributes the error across the image. http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering

The Floyd–Steinberg dithering looked exactly like what I wanted, and the Wikipedia page even gave me an algorithm I could translate to scheme code:

(for-each-coord src-w src-h
                (lambda (x y)
                  (let* ((old-pixel (rgb->gray (pixels (idx x y))))
                         (new-pixel (if (> old-pixel 128) 255 0))
                         (quant-error (- old-pixel new-pixel)))
                    (store! x y new-pixel)
                    (update! (inc x) y       (* quant-error (/ 7 16)))
                    (update! (dec x) (inc y) (* quant-error (/ 3 16)))
                    (update! x       (inc y) (* quant-error (/ 5 16)))
                    (update! (inc x) (inc y) (* quant-error (/ 1 16))))))

After fixing update! so it wouldn't try to update pixels outside of the image (I'm looking at you (-1, 1)), I was surprised at the quality of the image generated. Here's the same image as above, but with dithering in place:

Look at that, there's now some "gray" in the image!

I'm not sure what to make of the white vertical bars. They are almost certainly a defect in code as I've printed other images that don't have them.

The main issue I have with this algorithm is that it's terribly slow. Dithering a 384x447 pixel image takes almost 30 seconds, with the vast majority of that time spent looping over every pixel in the image. I'm sure I'm doing something inefficient, though it's possible that I'm running into a performance issue with Kawa Scheme. At some point, I'll probably debug it further and see why it's so slow.

Next up: I've got to see if I can get rid of those annoying white bars and then I need to make the Bluetooth connectivity far more bullet proof. When that's done,I should have a pretty dang functional app.

As usual, the DropPrint source code can be found here.