Bit rot antidote

PDF 1.7 is now a Draft International Standard, soon to become ISO 32000.

In my October 30 post on Photo permanence and durability I had written about the problem of bit rot. For documents, since 1993 the best antidote for bit rot has been PDF (Portable Document Format). In fact, since then I always keep a copy of my documents in its original format and in PDF. Most of my tutorial materials are created in FrameMaker, but since Adobe abandoned it on the Mac platform, I often end up making small changes directly in the PDF file, which I can edit in Illustrator or in PitStop, depending on the edit's nature.

Now PDF 1.7 has become an even more potent antidote to bit rot, because the ISO has promoted it to a Draft International Standard. To learn more about this, read Jim King's PDF blog entry of December 4 with title ISO Ballot for PDF 1.7 Passed!.

Above I wrote explicitly about documents, not about pictures. If you put your pictures in a PDF file you will always be able to read them, but note that PDF is a structured file format, not a file format for images. Therefore, inside a PDF file, the image will be encoded for example in GIF, JPEG or JPEG-2000. These encodings are also ISO standards, so there will always be decoders for them. However, JPEG does not specify a file format, so wrapping JPEG images in a PDF file is better against bit rot. This is not an issue for JPEG-2000, which specifies also file formats.

Combatting bit rot with steganography

Over the years we had various posts on bit rot, the problem that digitally stored images become unaccessible after just a few years because the system that can decode them is no longer available. Essentially, this might be an ethical problem we cannot solve with technology.

Recently, steganography has been proposed as a possible solution for digital image archiving, so today we revisit the origins of this approach.

To avoid unnecessary excitement, lets us just reveal from the beginning that it cannot do anything about bit rot in image archives, because it requires a system to decode. Sure, you might interject we can always implement a decoder, but as we saw with PhotoCD, unless there is a commercial product in the form of an operating system feature, this statement is useless in practice. For example, we can read punched cards by simply scanning them, but I doubt that you would pursue this route if you still had a stack of cards in your basement.

In the early days of digital color printing, the Feds were the early adopters of technology, so we always had their requirements in mind. One requirement relating to copiers and telecopiers (digital facsimile machines) was to be able to subject a document to seven copy generations without degrading its readability.

At the time this lead to religious wars of colorimetric reproduction versus preferred color reproduction, with the idea that colorimetric systems stood a better chance in surviving seven generations, while preferred color reproduction (e.g., saturation boost and contrast enhancement) would make more money because most customers make just one generation and a better looking copy begets more business.

The main digital color print technologies at the time comprised liquid and dry xerography, acoustic inkjet, thermal transfer, and dye diffusion thermal transfer (D2T2). In industrial research labs we cared mostly about dry xerography, because that is where the biggest profits were.

At that time we were fighting with the triboelectric effect, so halftoning with dispersed dots like dithering, or error diffusion, did not work well and be had to use clustered dot halftoning. We were achieving the best results with Tom Holladay's rotated dots. They were ellipses at a 45º angle, which were robust for the triboelectric effect and prevented the human visual system from connecting the dots into unsightly patterns.

Research is about synergies and serendipity, so at this point I need to digress.

At that time (late 80s) PARC had a big cross-lab project called System 33. It played a big role in Xerox renaming itself the document company and had a big effect on society by introducing concepts like Mark Weiser's ubiquitous computing, document management, etc. The basic idea was to take all possible technologies currently in the research stage and connect them together in one big bet.

One of these concepts was Smart Paper (not to be confused with the SmartPaper that then became Gyricon). Every document would have a cover page that could act as a banner page for print and a cover page for fax. This page would also have a barcode universally identifying the document. On one side this provided a solution for the copy generation problem, because a copier could reprint the original document referenced in the barcode instead of the document on the platen (annotation could be lifted from the paper document and overprinted onto the original document).

On the other side, having a cover page on every document is ugly and a barcode is even uglier. Although all this is done by document delivery services, you do not want this on all your office documents.

At this point the preceding two threads can be combined. Enter Rob Tow (click here for his account), who in 1988 came up with the idea of encoding information in images on documents (all office documents tend to have at least a company logo) by using Holladay's rotated dots for a binary code, by simply rotating them at ±45º. Rob called them glyphs.

Encoding a document's universal identifier in the logo was just a simple application. A more compelling application was to encode the CIELAB values of an image's pixels in the image's halftones. A dumb copier would simply do whatever it did to copy an image, but a smart copier would decode the image's colorimetric information from the halftones by interpreting them as glyphs.

At the time we coined the phrase "scan–think–print" for digital copying, so we could safely assume each one of our copiers would always have the additional intelligence to restore an image's colors from the glyphs. The actual image was then just a backup for the dumb copiers from the competition.

We even filed an invention disclosure for an Oliver North copier, which was a DocuTech with a built-in shredder. It would scan each page, encrypt the bitmap, and print the result using glyphs. The original document would be shredded right then and there, as part of the process. The copy could be stored and distributed in plain sight. It could even be copied at least seven generations, but only when the operator inserted in the copier a token with the decryption key, the copy would be the original readable document. This would have solved North's problem because he would have had only his token to be destroyed.

Rob got US Patent 5,315,098 on the basic concept, but then it took a lot of work to turn the idea into a robust technology. For one, the glyphs had to survive the infamous seven copy generations. Meg Withgott had come up with the concept of document dry-cleaning, but it took Dan Bloomberg substantial work in mathematical morphology to achieve a robust implementation for glyphs.

Then there were the problems of optical distortions, self-clocking, and error correction, among many others. All said, until the technology was done David Hecht and Noah Flores got 51 more US patents solving all the details.

The final artifact became a Xerox product under the trademark DataGlyphs. A project called Express (Henry Sang, Jr. was one of its leaders) achieved a successful commercial deployment solving the problem of processing the field test reports for Syntex, with others following.

Bit rot refers to images meant for archival applications. In that sense the glyph technology was not invented for bit rot but for document management, i.e., with a limited time scope in mind.

I am also using the term steganography in a loose sense, because it really refers to hiding a secret payload image into a carrier image. As such, steganography has to work only over a very restricted time span, just to smuggle an image through a hostile boundary.

A related concept is that of watermarks. Here the system has to be available only for the duration of a copyright, and the owner has a pecuniary incentive to keep the system working during this time.

As far as I know, currently the most promising remedy for bit rot is encoding the images in the DNG format and encapsulating them into a PDF file. However, this archiving path is not yet available at the operating system level. And there will always be the ethical issue to enable digital image archiving.

More on combatting bit rot with steganography

Last December First, I wrote about the story behind the data glyph technology and the preservation of digital images (here is the link). As it happens, at the Electronic Imaging Symposium two weeks ago, two papers presented recent progress on this technology.

Gaurav Sharma's presentation disclosed an extension of Tom Holladay's rotated dots from grayscale to full color. The authors were particularly concerned about the æsthetic quality of the images with the added payload. They conclude in their paper:

In this paper, we present a high capacity image barcode scheme for applications that require both high capacity and pleasing visual appearance of the encoded region. The scheme combines orientation modulation based data encoding on per-channel basis and color separation. We demonstrate that significant performance improvements can be obtained in terms of embedding rates by sacrificing image fidelity in favor of embedding robustness. Our simulation and experimental results indicate that dot orientation modulation based data embedding can achieve high embedding rates and well suited for per-colorant channel based data encoding in printed documents.

Link to the paper: http://dx.doi.org/10.1117/12.872215. Citation: Orhan Bulan, Basak Oztan and Gaurav Sharma, "High capacity image barcodes using color separability", Proc. SPIE 7866, 78660N (2011); doi:10.1117/12.872215.

Robert Ulichney's presentation described a system specifically for solving the image bit rot problem. The method presented was grayscale, so the payload would not be in the image's halftoning, but in a logo or other monochrome ornamental artifact.

The novelty is that the halftoning method is not Tom Holladay's rotated dots but a new algorithm called stegatones. Compared to the rotated dots, which allow a binary code, stegatones consist of 1-bit to 3-bit carriers, thus allowing a much higher capacity payload. The authors conclude:

We have improved on the scheme reported earlier for hardcopy image backup by embedding metadata into a steganographic halftone object. The advantages of this approach are:

• a better æsthetic presentation of the photo archive
• the elimination of the need to solve the complex OCR problem
• a more compact representation of the color tiles and metadata
• a layout for which auto-alignment is easier and thus the data is more recoverable

Building on the original motivation to use an analog hardcopy means of long-term image storage, our solution transcends hardware obsolescence by requiring any means of scanning the data coupled with the recovery software. While we can predict that hardware for reading digital storage media will likely not be available decades from now, some means of hardcopy scanning will be. So our strategy shifts the need to archive recovery hardware, to archiving recovery software. Long term recovery then depends on the availability of generic source code that includes means to read the accompanying stegatone.

Unfortunately the authors do not address the requirement to preserve a system capable of running the recovery software, so we are still stuck in the PhotoCD problem.

Link to the paper: http://dx.doi.org/10.1117/12.872612. Citation: Robert Ulichney, Ingeborg Tastl and Eric Hoarau, "Analog image backup with steganographic halftones", Proc. SPIE 7866, 78661I (2011); doi:10.1117/12.872612

If you missed the conference, you can easily read the two papers after downloading them from the two links above. However, you would have missed the conversation in the hall after Ulichney's talk. Actually, Elvis had already left the building, when a conversation started with Reiner E. from Rochester and Keith K. from Kihei.

We were wondering how far back this and the related technologies go. Reiner now has the date: 1982. During his first visit to the DGaO Conference (Deutsche Gesellschaft für angewandte Optik e.V.) he was getting a 'free ride' for operating the slide projector.

The talk contained the following: since digital storage is too expensive and cumbersome :-) and since it is always better to store in human readable form, since all other forms will disappear over time: create a system that stores digital in a human readable format. Data was from some satellite images (or other high quality imaging system).

Each data pixel (M > N bit) was converted to a N bit signal, where the N bits will be used as human readable signal and directly converted into an 'explicit' halftone. Meaning each pixel will get its own halftone cell with the corresponding number of elements set to "on". Since M > N, we have a many-to-one map and thus will create an M bit lookup-table for the explicit halftones, where the M_i,j that map to N_i have the identical number of 'on' bits, but in different spatial arrangement. Such a system was known in the digital field, but Reiner is not sure about the name. It is a less than optimal system for information density.

Ethics of bit rot

I am finishing up a conference paper and was planning to add some old photographs to document a workflow. I had several computers since I took the photographs, and because I have my stuff on several external disks (we researchers in image processing keep running out of disk space), I was not able to find them right away.

I remembered the photographs had been taken on film, so I thought can just quickly retrieve them from my PhotoPD archive. In fact, there they were, on PhotoCD number 6232 3073 2355. Lucky me.

Photo permanence and durability

Experience your memory fading away.

Historically, we humans have been willing to spend any amount of money on communication. We have been willing to spend even more money on communicating with our descendants after our passing — sky is the limit.

In the past you had to be a head of state to afford having your life cast in stone for posterity, or you had to be so good and work so hard that you would leave behind a historical legacy through the history books.

Today, everyone in our society can afford to leave behind their legacy in the form of digital items, such as scanned or digital photos, HD videos, AAC files, etc. Although such an archive is compact and convenient, it is still subject to bit rot. Actually, with the acceleration of technological progress, the span of time until bits have rotted is getting shorter.

With this in mind, there is still a strong argument for printing your memories and keep them around as atoms instead of bits. There is also a remarkable convenience to hard copies, especially when they are in the form of photo books.

Atoms can also rot, and in particular the dyes and pigments in inks fade. Therefore, it is useful to know how long your prints last. More specifically, you want to know how long prints on a specific media printed with a specific ink last.

In a concrete example, imagine you took a photograph during your honeymoon trip and you would like to be able to still enjoy at at you golden anniversary. Can you use refilled cartridges on generic paper or should you shell out money for fancy HP Vivera inks and special photo paper?

My colleague Ingeborg Tastl wanted to find a good answer just to this kind of problem — how will the photo with my memory fade away during the years? Since Ingeborg is our ICC profiling specialist, she built an interactive tool that allows you to simulate the fading of your memory when printed on two different ink and paper combinations. This is how the tool looks in on my PC:

Ingeborg being a very nice person, she lets you have her tool. You can download it from here and look at your own memory fading away. Of course, the lawyers had to have their say to keep us out of Court, so the selections are somewhat restricted, but it is still an interesting tool. For now the simulator is Windows only, but you can run in on an a virtual PC in an Unix system like a Mac.

PostScript and Interpress: a comparison

Back in the Seventies and Eighties, when "Internet" was the name of the Xerox internetwork of Ethernets and what we today call the "Internet" was called "ARPAnet," news where spread through a mechanism called "distribution lists" (DL). Some popular non-technical DLs where YumYum↑.pa@xerox.com, WineLovers↑.pa@xerox.com, ChocolateLovers↑.pa@xerox.com, etc. Some where replicated on the DECnet NetNews, an informal network with datagram addressing (bang addresses).