Compression of Halftoned Digital Images

An article of manufacture including a non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations comprising:

• based on an m×n halftone matrix and a first m×n pixel block of an image, determining, by a computing device, a first m×n halftone version of the first m×n pixel block;
• performing an n-way interleave on rows of the first m×n halftone version of the first m×n pixel block to create a first mn×1 halftone segment;
• comparing the first mn×1 halftone segment to one or more halftone segments in a first-in-first-out (FIFO) buffer;
• if the first mn×1 halftone segment does not match any halftone segments in the FIFO buffer, (i) outputting a literal code word and a representation of the first mn×1 halftone segment, and (ii) writing the representation of the first mn×1 halftone segment to the FIFO buffer;
• and
• if the first mn×1 halftone segment matches a particular halftone segment in the FIFO buffer, (i) outputting a repeat code word and a repeat value, and (ii) writing at least one representation of the first mn×1 halftone segment to the FIFO buffer.

A computing device comprising:

• a processor;
• data storage;
• and
• program instructions, stored in the data storage, that upon execution by the processor cause the computing device to perform operations comprising:
• based on an m×n halftone matrix and a first m×n pixel block of an image, determining, by a computing device, a first m×n halftone version of the first m×n pixel block;
• performing an n-way interleave on rows of the first m×n halftone version of the first m×n pixel block to create a first mn×1 halftone segment;
• comparing the first mn×1 halftone segment to one or more halftone segments in a first-in-first-out (FIFO) buffer;
• if the first mn×1 halftone segment does not match any halftone segments in the FIFO buffer, (i) outputting a literal code word and a representation of the first mn×1 halftone segment, and (ii) writing the representation of the first mn×1 halftone segment to the FIFO buffer;
• and
• if the first mn×1 halftone segment matches a particular halftone segment in the FIFO buffer, (i) outputting a repeat code word and a repeat value, and (ii) writing at least one representation of the first mn×1 halftone segment to the FIFO buffer.