Image bit depth reduction algorithms for laser printer microfilming

I'm thinking about what would be necessary to print out the most important, say, thousand articles from Wikipedia.

One question is what to do with the images. I'm proposing to use 6 pixels per line of text, so if you don't scale down the images, they'll be humongous compared to the text (typically 16 pixels per line). But printed images actually want to use more pixels than on the screen, not less, because printers only have one bit per pixel (per color channel, if there are multiple color channels) while video screens typically have 8 bits per pixel per color channel.

So I'm trying out different algorithms on an example image to see what preserves the most detail.

This image is from [[Gwen Stefani]].

Reduced to 61% linear scale (compromise between full size and reducing proportional to the text:

The last image above, which I think is the best so far, was produced by the following procedure:

blow up the original image: convert -geometry 360x540 220px-Gwen_Stefani,_Bloomingdales.jpg blown-up-one-step.jpg
use my "pseudo-engraving" algorithm on it: ~/devel/misc/byn.py blown-up-one-step.jpg
shrink it, converting to grayscale in the process: convert -geometry 135x203 blown-up-one-step-bn.png reduced-scaled-bn.png
convert grayscale to bilevel in the GIMP: Image→Mode→Indexed, Use black and white (1-bit) palette, Color dithering: Floyd-Steinberg (reduced color bleeding)

The image before it, which is very nearly as good, was produced more simply: the scaled-down RGB image was first run through the GIMP's "sharpen" filter, set high enough to visibly degrade the image (73 I think), and then dithered in the same way.

It's clear that there's a lot of room for improvement in this problem space over the standard algorithms included in the GIMP (the dithered images above and below), and over the algorithm I developed, too.

Full size:

Reduced to 38% linear scale (proportional to text):

Doubled in size to compensate for bit depth reduction: