DAVID KRIESEL, a doctoral student in computational geometry at Bonn University, has no academic interest in compression algorithms. When a former client asked him about a bizarre incident involving a photocopier, his first reaction was, “You guys have to be kidding me.” The client called him when they found that a Xerox machine had scanned an architectural drawing of a house in such a way that numbers from one part of the original drawing wound up replacing those in another portion. The mystery proved too hard to resist.
In the floor plan, areas corresponding to three rooms were shown as measuring 14.13, 21.11 and 17.42 square meters (see picture). After a bit of investigating, Mr Kriesel found that two different Xerox Workcentre models would replace one or two of those numbers with another, in an apparently random fashion. (Modern photocopiers act as big digital scanners with a printer attached rather than using the traditional analogue photographic process and can produce image files as well as printed duplicates.)
He first checked that optical character recognition (OCR) was not enabled. (OCR software searches image data to find characters and map them to digitally represented text that can be edited and searched.) But whether OCR was turned on or off, the problem persisted, even after Xerox’s technical support, equally mystified as he was, updated one of the devices to the latest firmware. He created a test sheet of numbers and scanned them, and found similar substitutions.
On close inspection, Mr Kriesel spotted that the substituted digits weren’t merely similar to other appearances throughout the scan; they were precisely the same, pixel for pixel. He realised that image compression could be the culprit.
There are two types of image compression: lossless and lossy. Lossless compression replaces redundant patterns of data in a file with codes that take up less space. The compressed file, when decompressed, matches the original bit for bit. Lossy compression, used for images, audio and video, approximates the original instead of representing it exactly. For instance, software can make the lossy JIF image format used as part of JPEG vary from blurry and pixelated to crisp. The less fidelity, the smaller the file.
After a week, he posted an entry on his blog which spread through technology websites. Mr Kriesel heard back from readers that for the highest compression for black-and-white (one-bit or bilevel) scans Xerox employed a standard known as JBIG2. JBIG2 can provide variable levels of compression by using coarse matches that identify broadly similar areas, or patches, in an image and replacing all of them with a single simulacrum. On decompression, all the coded areas are restored by the equivalent of a rubberstamp of one patch.
Mr Kriesel’s post prompted Xerox to look into the problem. Rick Dastin, in charge of the Xerox division which makes business printers, says this was “a bunch of unlikely probabilities coming together”. In fact, a warning concerning potential character substitution pops up in Xerox’s software when a user changes a factory-provided setting. Only documents with characters that are both small enough to fall within the threshold that the compression algorithm uses for fuzzy matching yet barely large enough to be legible are affected. (The architectural drawing and Mr Kriesel’s later seven-point type tests fit the bill.) The default setting does not carry the warning, but then it doesn’t cause the problem either. That said, Xerox’s support staff were seemingly unaware of this as a documented issue.
So why include a mode that could distort or substitute characters in the first place? Mr Dastin says it is a much-requested feature and one that Xerox markets heavily. For some industries and regions in which bandwidth is at a premium, this highly compressed mode provides Xerox with an edge over competitors. Some potential clients even bring specific documents to sales meetings to test how small Xerox’s approach can squeeze the resulting file size. Mr Dastin mentions oil rigs, which suffer from piddling bandwidth and worry about every kilobyte because it costs them a wad of money.
With sufficiently large type and with images, JBIG2 provides an advantage. Most users have no need to shave bytes, or to use black-and-white scanning as opposed to tonal (grayscale) or colour, in which this compression algorithm cannot be used anyway. Francis Tse, a principal engineer at Xerox, says the idea is to “let people who know what they are doing get a lot of capability out of the equipment”.
Both Mr Dastin and Mr Kriesel express chagrin. Mr Kriesel does not want to be remembered as the fellow who didn’t read a software label. Mr Dastin is concerned that his support staff were not better informed; some retraining will happen, he says. A patch is forthcoming that will let firms’ technical staff disable the high-compression mode entirely or easily reset devices to the factory default.
Mr Kriesel says he continues to get troubling reports from readers who checked their scanner settings and photocopies to find substitutions. He has assembled a list of potentially affected Xerox hardware, and has begun to assemble reports of this issue in equipment from other manufacturers, too. The extent of the problem, he frets, will probably remain unknown. But the errors will be felt. For his part, Mr Dastin says Xerox takes this seriously, although this is the first report they have had despite the technology’s being around for years. He and Mr Kriesel have thought about how to make the trade-offs more obvious, and the company will make changes.
Powered by Facebook Comments