This white paper is based on a paper delivered to the Information Based Indicia Program Technology Symposium, sponsored by the United States Postal Service, Nov. 25-26, 1996. (For actual presentation, which summarizes this discussion, download this Word document with slides and annotations. Those interested in the paradigm of hyperlinking the physical world might start at slide 30).

A Flexibly Configurable 2D Bar Code

Thomas Antognini, Ph.D.,

Cobblestone Software, Inc.

Walter Antognini, J.D.,

Cobblestone Software, Inc. and Pace University

Paper should make the ideal digital medium. It is cheap, portable, comfortable, and pervasive. It is by far the most common medium for human readable information, and attaching digital information would be natural and convenient. It is readily printed in large numbers. The channels of distribution, and the means of organization and storage, are well and long established.

In this article we describe a technology that attempts to achieve fully the potential of paper as a digital medium.

The article splits essentially into two largely separate parts. The first part is devoted to technical approach. The second part, which begins at the title Application of Paper Based Digital Information, discusses the application of the technology, particularly as related to the Information Based Indicia Program (IBIP) and other postal related functions. Those interested in the applications may safely skip to that segment.

Technical Method of New Symbology

Two approaches to 2D bar codes

2D bar codes attempt to turn paper into a digital medium of some capability. Yet traditional 2D bar codes suffer from limitations that stand in the way of paper becoming a serious player in the digital world. Most notably, the amount of information they carry, usually only 1-2 kilobytes, can perform few of the functions of magnetic diskettes, which have held central place in the domain of the personal computer.

There is an explanation for this. 2D bar codes are conventionally regarded as extensions of ordinary linear bar codes, and indeed were largely developed by the same companies that have made their living by selling scanners for linear bar codes. The applications envisioned for the 2D bar codes were those out of reach for a linear bar code, because it lacked the carrying capacity. Such uses might include encoding packing lists, laboratory test results, and detailed ID data. These applications typically demanded fast response. Typically, too, they needed to be able to be scanned by a small handheld device.

The effect of this orientation was to focus on 2D bar code symbologies that could be made very fast in a hardware implementation. The emphasis was therefore on a simple decoding algorithm. And the size of the symbol must be small both to bound the time it takes to decode, and to permit a handheld device to scan it.

The consequence of permitting a fast hardware implementation was that the symbologies were far more rigid than they need be. The consequence of the relatively small symbol size was of course a further severe limit in the total amount of information it could hold.

Approaching paper more directly as a digital medium for the standard PC and off-the-shelf printers and scanners yields a remarkably different result. In that case, the emphasis is on the flexibility of the format of the data, and the density that can be achieved.

It might be thought that there would be a serious price to be paid in computational speed. Yet it has not proved so, and the future, as captured by Moore's Law, is on the side of this approach. Powerful general purpose chips - the PowerPC chip for example - can readily be embedded in a variety of devices. These chips are often available at commodity prices. Memory prices too are plummeting. Everything favors the eventual broad adoption of a more powerful type of 2D bar code.

Fundamental goals of new symbology

The new approach attempts to build a symbology from basic principles.

The approach is grounded in an understanding of a basic fact: the density of information that can be encoded on paper, and reliably decoded, depends both on the printer and the scanner. The best possible result is to have a symbology that allows the maximum density of information for each such pair to be expressed and achieved.

The new symbology is explicitly defined in terms of the most basic atoms of printers themselves, namely dots, or printed pixels. All features of the symbology are constructed from these elements.

Most 2D symbologies tend to express features in terms of physical size of the features -- e.g., the size in mils of a feature in the X dimension or Y dimension in PDF 417. Printers do not directly implement the notion of these dimensions, and the fit to such dimensions may not be good for many printers, if aggregations of their dots do not neatly fit into stipulated dimensions. This lack of fit often engenders a loss in density. The most compact representation possible for a printer, given a target scanner, may not have a defined embodiment in the symbology.

The new symbology attempts to identify all the features that contribute to density of information on the printed page, and enable independent variation over all the dimensions distinguished. The set of dimensions may be regarded as defining an n-dimensional space. In this space, each pair of printer and scanner will have a point of maximum density given a desired reliability.

Data mechanism and Clocking mechanism

All 2D bar codes must, of course, have a mechanism to represent data. They must also, however, possess a mechanism to "clock", or determine the location of, the features that represent data.

The function of the data representation mechanism and the clocking mechanism are distinct, and the new symbology keeps their properties separated. In particular, the size, separation, and frequency of the data features on the one hand, and of the clocking features on the other, are kept decoupled. They are allowed to vary independently.

In many 2D bar codes the properties of the two mechanisms are conflated. Often, for example, the clocking function is fulfilled by a sequence of features on the periphery of a symbol. This sequence alternates between dark and white, and contains features of exactly the same height and width as the data features internal to the symbol. This approach may be simpler to implement in hardware, since the alternation between off and on at the periphery can trigger the retrieval of the next row of internal data bits. Yet it is not optimally suited to serve the special purpose of clocking.

The fundamental fact about clocking is that the features employed must be, feature for feature, far more reliable in location than individual data features. Many data bits may be lost if a single clocking feature provides misleading location information. While some "redundancy" can be built into the clocking features, the decoding process is inescapably sensitive to the conjunction of even a few errors in clocking features.

The constraints on clocking features are the following. They should rarely be missing due to printing errors. They must have dependable and determinable physical location in the pattern. They must also be close enough to the data features for which they are responsible that they can provide accurate location information about them.

These constraints imply that the features must be large enough that they will reliably be printed, and so that their centers of mass can be accurately fixed. The constraints also entail that the features should be separated by enough distance from other features that they can be found, and so that their material can be distinguished from that of other features. They should also be interspersed throughout the symbol, occurring frequently enough to fix the location of data features.

The constraints on the data features are the following. They must be large enough that the toner or ink is laid down reliably when the data bit is "on". They must also be large enough that the scanner can detect them. And it is important that the toner or ink not flow significantly into the area designated for a contiguous data feature.

Unlike the case of clocking features, it is not so important that the toner or ink for the data feature precisely occupy its designated area. As long as the area occupied by a data feature is, from the standpoint of the scanner, clearly dark when toner is laid down, and light when it is not, considerable looseness in the detail of how these areas get filled out can be tolerated. This looseness generally allows them to be smaller and closer together than the clocking features.

The height and width of data features should be allowed to vary independently if maximum density is to be achieved. It often happens that a perfectly square data feature in a perfectly square cell is just beyond the reach of a particular printer/scanner combination. By relaxing the size in one dimension but not both, it is frequently possible to get very reliable decoding. This may achieve significantly higher densities than relaxing both dimensions to the next largest square sizes.

Moreover, certain scanners and printers tend to introduce distortions or defects more in one dimension than another. Fax machines also tend to introduce telephone line noise horizontally. By configuring both the data features and clocking features so that they are of greater size in one dimension than the other, such difficulties can be readily compensated for while minimizing loss in density.

The notion of separation between data features is also key. Dot gain is a notorious problem for laser printers, inkjet printers, and standard printing processes. An individual dot may indeed be many times its defined size when printed. The bitmap that the printer employs must be configured so that the data features are suitably separated from each other. Otherwise, the data features will crowd into each others space when they are printed. The precise separation demanded may depend on the nature of the printer and even the state of its cartridge. Likewise, the mechanical inaccuracies typical of inkjet printing must be allowed for by introducing appropriate separation.

Scanners too can affect the amount of separation required. Typically scanners exhibit interpixel "leakage" so that a dark (or a light) feature might creep into adjoining pixels. Accommodation to this may have to be performed in the printed output.

PaperDisk format parameters and terminology

The new symbology, PaperDiskTM, represents data by means of what is termed a "spot" in a "cell." A spot is a (typically) rectangular array of dots, or printed pixels, laid down by a printer to represent a bit being on. It is separated from adjoining spots (or places they might occupy) by designated vertical and horizontal distances. These distances are measured in terms of (typically) integral numbers of dots.

A cell may be regarded as the region allocated to a given potential spot. That is, it includes the spot itself (where the bit value calls for a spot) and extends halfway to the edges of neighboring potential spots. Strictly speaking, it does not occur in the primitives of the symbology itself, but it is a convenient logical construct. It suggests the area of the printed page that is rightfully occupied only by material from a given spot.

The clocking features are called "markers" in PaperDisk. Like spots, these too are rectangular arrays of dots. They are, in the current embodiment, arranged in vertical strips throughout a pattern.

Parameters affecting data density

A number of parameters affect the density of data on the printed page. These include the height of the spots, the length of the spots, the length of the markers, the horizontal separation between markers and spots, the horizontal separation between spots, and the vertical separation between spots. All of these parameters are fully configurable -- that is, can assume essentially any numeric value -- in a PaperDisk symbol, which we term a DataTile(TM).

Figure 1 below illustrates the basic features and parameters of PaperDisk.

Figure 1. Basic PaperDisk features and parameters

Spot Height defines the height in printed pixels of each spot (where a spot is called for) representing a bit of information.

Spot Length defines, in printed pixels, the length of each spot representing a bit of information. The length is the distance across the page.

Spot Distance defines the distance in printed pixels between the right edge of one spot (when present) and the left edge of the next spot (if present) along a data segment. The most compact representation will set this to 0, so that spot positions abut one another. To create softer visual effects, however, it can be good to set this to some positive non zero value. Doing so tends to diminish the appearance of clumps in the DataTile.

Segments Per Marker defines the number of rows of data cells down between one marker and the next. Typically, there should be 3 or 4 rows of data positions down for each marker.

Data Segments. The data cells placed horizontally between two markers collectively make up one data segment. A datasector -- a rectangular subportion of the DataTile explained in the next section -- may have a number of data segments across. This parameter sets the number of data segments across per datasector, defining its width.

Marker Height defines the height in printed pixels of each marker, which serves as a guidepost to nearby rows of spots.

Marker Length defines, in printed pixels, the length of each marker. The length is the distance across the page.

Row Distance defines the distance down the page, in printed pixels, between rows of spot positions. Measured from the top of one row of cells to the top of the next row of cells.

Marker to Spot defines the distance in printed pixels between the edge of a marker and the edge of the closest spot position (filled or unfilled) along a data segment. This parameter should be high enough so that markers can be distinguished from spots.

Spots Per Segment defines the number of cells in a data segment. More precise scanning processes -- flatbed scanners as opposed to hand scanners for example -- can safely have this set higher. When significant distortions are likely to enter a scan, markers must be relatively close together so that PaperDisk can make accurate estimates of the cell positions.

Skip Marker determines which markers, if any, will be omitted in the vertical strips of markers. When PaperDisk decodes a DataTile, it needs to match markers it finds in the scanned image with the markers it expects to have been printed. When the scanned image is distorted or the printed DataTile is damaged, such matching can become quite difficult. Skipping markers can improve the accuracy of this process.

Further basic parameters of PaperDisk symbology

Several other parameters are employed to define fully the data format for a DataTile. They use the notion of a datasector. The data portion of a DataTile is composed of a number of rectangular subdivisions, called datasectors. Each has a "complete" message. PaperDisk distributes codeword bits physically throughout a datasector to allow for correction of errors due to printing defects, damage to the DataTile, and scanning distortions. All bits in any codeword by convention must be contained in the same datasector. This allows error correction and detection to be performed and completed datasector by datasector.

Among other things, this structure facilitates breaking down the image into smaller more manageable pieces in the decoding process. In particular, the memory demands on the computer are much less if only a small portion of the image need be dealt with at any given time. This is quite significant for the typical PC: a standard 8 1/2 by 11" piece of paper, scanned in by a 600 dpi gray scale scanner, would generate an image of about 32 megabytes.

Figure 2 illustrates a full DataTile.

Figure 2. Example DataTile.

Sectors Down determines the number of datasectors down the DataTile. This should not be less than 10 down the entire printed page. Otherwise, too large a portion of the scanned image of the DataTile may have to be loaded into the PaperDisk software at once. If available memory is low, the software may be unable to decode the image.

Sectors Across determines the number of datasectors across the DataTile.

The width of a DataTile is fixed by the combined effects of sectors across, data segments, spots per segment, marker length, marker to spot, spot length, and spot distance. By manipulating these parameters, virtually any width for a DataTile can be achieved. The current PaperDisk software allows the user to select a desired width. It then automatically sets these parameters so that the DataTile matches the width as closely as possible.

Decoding technique

It is reasonably straightforward simply to define a symbology that is flexibly configurable. Yet the greater the flexibility, the more difficult it may seem to decode symbols with unknown and arbitrary data format. PaperDisk introduces a method to accomplish this.

The decoding techniques import a number of notions from image understanding to do their work. The difficult thing in image understanding is to go from an image about which very little may be known apriori, and to construct, step by step, a full account of the entities in the image. Usually, the process will involve establishing certain basic facts first, then leveraging those basic facts to determine more about the content of the image. The new facts iteratively are employed to ascertain still further facts.

A DataTile is constructed precisely to facilitate this sort of reasoning. A pyramid of knowledge is enabled, so that in the end an arbitrary data format can be decoded.

In its current implementation, a DataTile has three distinct elements: the landmarks, the metasector, and the data portion of the DataTile.

The landmarks are two sets of three simple vertical strokes of known aspect ratio. They can be quickly found, and because the decoding process will look only for relative proportions, locating them is resolution independent. Of course, other items in the scan may resemble these landmarks, but if a landmark candidate is not just to left or right of the metasector, it will be rejected. Two landmarks are included for redundancy; if one landmark is damaged or poorly scanned, the other does all needed work.

The metasector is in precise scale to the landmarks, and possesses a known and rigid format. It encodes the data format values for the data portion of the DataTile below it. It is displaced at a known distance from the data portion. In its implemented form, it is itself a particular, stipulated instance of PaperDisk's general data and clocking representation scheme. It is composed of markers, and spots in cells, just as is the data portion of the DataTile, but the precise values of the parameters are known in advance. This allows the same fundamental image understanding algorithms to be employed in its case as in the remainder of the DataTile. This technique also can underpin the most compact representation of the information the metasector carries.

The data portion of the DataTile carries the information that the symbol is intended to encode.

Decoding proceeds by first finding a landmark. From a landmark, it can make a preliminary estimate of the scale and orientation of the features in the image. This estimate suffices to examine for a metasector immediately to its right or left. If the process finds it, then the landmark candidate has done its job. If not, then the process looks for another landmark candidate.

When the metasector is found, it is decoded employing the standard image understanding and error correction algorithms, to produce the data format parameter values for the data portion below. Because it is many times the size of a landmark, it also provides far more precise information about the scale and orientation of the DataTile.

The metasector also contains information about its size in printed dots. This is necessary, because the size of the metasector (and the landmarks) in printed pixels must vary among different printers. A 1200 dpi printer and a 300 dpi printer should print landmarks and metasectors of roughly the same size in inches, so that the same 300 dpi scanner can most readily locate them. Yet a landmark produced by the 1200 dpi printer, in comparison to that of the 300 dpi printer, will be larger in each dimension by about 4 times as many dots. The format parameters of the data portion of the DataTile are, as we have seen, expressed in terms of printed dots. Hence, the size of the metasector in printed dots must be communicated to the decoding process before it can make out the data portion.

Achieving maximum density

The most basic aim of the PaperDisk technology is to attain the greatest density for each combination of printer and scanner. How is this done in practice?

First, one chooses, for a given printer and scanner, safe sizes for spots and cells. That is, the sizes should be large enough that DataTiles produced can be reliably decoded. At the same time, one must also select safe settings for marker size, separation from spots, and number of spots per segment.

The general rule of thumb is that the printed spot should never flow into any part of an adjoining cell. It is, however, often quite acceptable for the size of the printed spot to be noticeably less than the size of its cell.

Bearing in mind that spots should be smaller than cells, one should, step by step, reduce the sizes of the cells and spots until the DataTiles exhibit difficulty in decoding. At that time, the sizes should be relaxed to the previous reliable sizes. This, presumably, will relax the sizes in one, but not both dimensions - for example, the horizontal size may increase but not the vertical size.

It may also prove important to experiment carefully with the spot size in a cell in order to get the maximum density. The effect of this may depend on the printer, the toner or ink cartridge, and the scanner. The amount of dot gain in particular can vary widely across printers and cartridges.

Having settled on the optimum spot size and cell size, one now proceeds to reduce the overhead due to the clocking mechanism. Gradually, one reduces the horizontal length of the markers, and the separation between marker and spot. Likewise, one increases the number of spots per segment. At some point, the decoding will fall below the acceptable reliability. At that juncture, one returns to the previous reliable setting. It should be remarked, however, that it is risky to push the reduction of overhead very far. What may seem safe on a few DataTiles can turn catastrophically bad with minor perturbations in the printing process or scanning process. Our experience is that the clocking overhead can be often reduced to about 10%, and be quite reliable. Certainly there are diminishing returns if it is reduced below that, and potential for trouble is introduced if it goes much further.

Finally, one may manipulate the redundancy to diminish overhead. In the world of standard computer printers and scanners, we have found that 15% redundancy works very well with the typical abrasions and abuse most paper documents encounter.

Error correction and detection

Several techniques are employed in PaperDisk to eliminate errors in decoding.

The most basic and effective method to eliminate certain important classes of errors is not to introduce them in the first place. The very flexibility that makes it possible to maximize density using PaperDisk also underpins the best method to reduce such errors. It has been our experience that finessing the size of the spots and cells can most effectively minimize the effects of printing defects, some forms of damage to the printed symbol, and scanner distortions. Indeed, by increasing the size of the data features and the clocking features, virtually any anticipated problem in these domains can be compensated for, so that information can be perfectly communicated.

In the literature on 2D bar codes, much attention has been paid to the selection of a scheme for error correction, as derived from communication theory. Yet it is our opinion that this focus is largely misplaced, particularly when it comes to defects introduced in the process of printing or of scanning. It is better by far to solve the problem in the image domain, by utilizing effective techniques in that domain, than to wait until after the errors have already been insinuated, and the damage done.

In PaperDisk, error correction serves to perform the final cleanup of errors that intrude into the decoding process. If the sizes of the spots and cells have been well configured, errors should not occur in large numbers, unless the pattern is badly abused. A relatively small amount of redundancy -- again, about 15% -- usually well suffices to eliminate the typical set of errors. In cases where it it is anticipated that the pattern may suffer considerable damage, more redundancy can be dialed in.

The bits in the codewords are organized in a DataTile to reduce the impact of the typical problems that affect decoding. Most such problems create burst errors in a localized region of a printed symbol. Thus, a stray mark on the page, a crinkle or fold in the paper, a dropped line in a fax transmission, a mechanical slip in a document feeder or in a scan by a handheld device, all engender such localized effects.

The error correction scheme is based on a standard Reed-Solomon technique. All of the symbols of a codeword are contained within a single datasector in a DataTile. The size of the datasector can be configured as desired -- a single datasector may indeed comprehend the whole of the data portion of a DataTile. The symbols of all the codewords in a datasector are organized so that all of the first symbols are spatially grouped together, all of the second symbols are so grouped, etc. In this way, and others, the symbols are arranged so that it will rarely be the case that two symbols from the same codeword are spatially close by. A printing defect therefore will usually affect just one symbol from each codeword. Since the codewords are able to correct errors in a number of symbols, this provides some safety from an irrecoverable corruption of the data in the scan.

Error detection plays a role as well. It may happen that a codeword has had more errors introduced into it than it can correct. A Cyclic Redundancy Check (CRC) calculated over all the information in a datasector is used to detect this circumstance. If it does not square with the data generated by error correction, then the data must be rejected.

This leads to one of the more powerful mechanisms PaperDisk employs to retrieve data perfectly and robustly. If the CRC indicates a residual error, PaperDisk does not give up. Borrowing methods again from image understanding, it employs a variety of hypotheses to attempt to get the information perfectly. Whenever a datasector is processed, assumptions are made about thresholds for on and off, kernels for setting such thresholds, locations of markers and adjustments to those locations, etc. Often these assumptions are off the mark, and the inaccuracies may engender errors that cannot be corrected. By reprocessing the datasector under a different set of hypotheses, these errors may very often be removed, and the datasector correctly decoded. PaperDisk may reprocess a datasector 10 times before it declares the decoding process a failure.

Benchmarks

PaperDisk incorporates fundamental, new techniques that prove their effectiveness in the benchmarks the technology posts. The table below states some of them.

Table 1. Density benchmarks

Printer       Scanner     Symbol      Data in symbol (KB     Density          
type, dpi     dpi         area        after compression)     (bytes/sq.in.)   

Linotronic,   600         8.0X10.5    1,027                  12,200           
1270                                                                          

laser, 600    600         8.0X10.5    667                    8,100            

laser, 600    300         8.0X10.5    285                    3,400            

fax, 200      300         8.0X10.5    213                    2,500            

fax, 200      200         8.0X10.5    51                     600              

In contrast, a PDF 417 symbol carries at most about 2KB, and the density is at most about 300 bytes per square inch, with a realistic degree of redundancy.

The flexibility of PaperDisk is also suggested in the range of symbol sizes PaperDisk has demonstrated. The smallest symbol it has produced is a fraction of a square inch in size. The largest symbol has filled a full legal size page. Even this is limited only by the printers we have used, not the symbology itself, which can produce symbols of essentially arbitrary size.

Other benchmarks are also worthy of note.

First there is the speed of the processing. On a 100MHz Pentium, the encoding achieves 35Kbps, and the decoding attains 20Kbps. If one assumes that the minimal capacity for IBIP indicia is 500 bytes, then a comparably powered system might encode about 8 indicia per second, and decode about 5 per second.

The decoding is also quite tolerant to skew. Typically, a DataTile can be successfully decoded so long as its skew is less than 20 degrees.

Range of printers and scanners

The PaperDisk software has been thoroughly tested across the range of off-the-shelf printers and scanners that occupy the consumer PC domain. The resolution independence that underlies the basic concept of the symbology has been amply demonstrated in practice.

One can produce one DataTile by a 1270 dpi printer (a Linotronic), and another DataTile by a 200 dpi printer (a fax machine), and successfully decode them with a 200 dpi scan. Likewise, one can generate a DataTile by the 1270 dpi printer, and another by a 200 dpi printer, and succeed in decoding them with a 600 dpi scan. Each of these DataTiles can be configured to reach the maximum density that the particular combination can sustain.

The software is resolution independent also in the sense that a scan of fixed resolution can recover information from a very wide range of symbol densities. Thus, at a fixed 600 dpi scan setting, the decoding process has recovered, from a full letter size page, as little as 8KB (100 bytes/sq. in.), and as much as 1,027KB (12,200 bytes/sq. in.).

The software directly supports a number of different printers and scanners, automatically choosing default settings for data format given the target printer and set of scanners. These defaults have been chosen by extensive experimentation with the many classes of printers and scanners.

Among the printers it so supports are Linotronic 1270 dpi; laser 1200, 600, and 300 dpi; inkjet 360 and 300 dpi; fax machines 200 dpi, whether thermal, laser, inkjet, ribbon, or even fax modem. The Linotronic is of course used as an intermediary step to standard high quality printing presses, so that by extension these printing processes are themselves supported. Fax modems are supported in the sense that a DataTile image can be sent directly to a fax modem, and the image immediately decoded, bypassing the steps of first printing it out and then scanning it.

Software implementation

The PaperDisk software is written in C, and runs under either Windows 3.1 or Windows 95.

The software has been extensively tested and improved. It was our experience that while the core concept of the symbology is intuitive and straightforward, truly accomplishing the goals of the symbology demanded extraordinary work. The very flexibility that is the central virtue of the technology required protracted experimentation to make fully effective. In particular, achieving robust performance across all relevant printers and scanners, at all supported resolutions, comprised an effort of a number of years.

The software has been internally tested on 20 scanners, and 26 printers. The scanners include hand helds, flatbeds, sheetfeds, and fax machines. The internal testing and refining of the software has included over 30,000 images. The software has also experienced an extended beta test, having been in the hands of beta-testers for well over a year.

The software can handle images of 8-bit, 4-bit, or 1-bit, including G3 and G4 images. 8-bit images are the "base" type that PaperDisk understands; 4- and 1-bit images are translated into an 8-bit image. In general PaperDisk fully exploits the richer data of 4- and 8-bit images, and, other things being equal, can attain significantly higher densities with such imagery than with 1-bit data.

To reduce memory requirements, the implementation can process images in bands. Using this technique, it has decoded 600 dpi 8-bit images of a full legal size page, which are roughly 40MB in size.

The software can also encode and decode files of unlimited size, by distributing the contents of a file across a number of DataTiles if necessary.

PaperDisk currently supports 10 levels of error correction, from 3% up to 50%.

To compress data, the software employs standard Zip compression. The encryption technique standard for Zip files is also supported.

The virtue of flexibility

The flexibility PaperDisk symbology enjoys has myriad consequences.

The most basic implication is what we regard as the inevitability of the symbology as a standard. The full flexibility of the technology is, apart from inessential details, uniquely solvable. That is, if a symbology is to enable maximum density for all printer/scanner combinations, it cannot deviate in any important way from the technique employed by PaperDisk. In particular, it must have the ability to configure spots in both dimensions, cells in both dimensions, and to alter the dimensions of spots and cells independently of each other. It must also be able to manipulate freely the size, separation, and frequency of the clocking mechanism, in order to achieve the required clocking accuracy on the one hand and reduce overhead on the other. Any symbology that fails to exhibit these degrees of freedom will be inferior to the PaperDisk symbology, and can be shown to be so by concrete demonstration. This demonstration would consist in producing a pair of printer and scanner for which the alternative symbology cannot attain the same reliability and density as PaperDisk.

It is our belief that, given the geometry of printed output, which is expressed in terms of rectangular arrays of dots turned on or off, PaperDisk represents the best possible solution to the problem. Variants that may achieve the same effect are fundamentally equivalent to the PaperDisk approach.

Fundamental Test of a 2D Bar Code symbology

This leads to what we regard as the Fundamental Test of a 2D Bar Code symbology. The challenge is this:

Can the symbology, for any pair of printer and scanner, support reliable encoding and decoding at the highest sustainable densities?

If a symbology cannot meet this challenge, it will not in the long run remain competitive with a symbology that does.

The argument for this assertion is compelling. It is clear that density is crucial. Space on the printed page is money: paper, ink or toner, and the distribution of paper have a price. When large numbers of documents are involved, this price may be considerable. Moreover, the amount of area it takes to capture a fixed amount of data will determine how much trouble it is to retrieve that data. A smaller region will generally enable a quicker scan. And if a less dense pattern must spread the information over several pages, it will require more user manipulation.

Very often too, the size allotted may for various reasons be fixed -- indeed indicia are just so constrained. Plainly, the amount of information a pattern can carry will determine what it can do.

It is also key for a symbology to attain the highest densities across all printer/scanner pairs. Different parties may have different sets of printers and scanners. In the near future, it might be reasonable to expect that a law office, for example, would have a high quality 600 dpi scanner, and a 600 dpi laser printer. A consumer might be expected to have a 300 dpi scanner, and a 300 or 360 dpi inkjet. Under these circumstances, digital communication by paper between law offices would naturally be more powerful than such communication between a law office and a consumer. And communication between consumers would be less powerful than either of the other forms. Yet it is highly desirable that the same underlying technology be capable of handling them all.

Moreover, the symbology must provide for a growth path. Over time, the printers and scanners standard for each class of user will of their own accord become more powerful. It will greatly encumber the process of growth in digital communication by paper if this shift is poorly supported by an underlying symbology.

In a forthcoming section, we will show why, in IBIP itself, it is crucial that the selected symbology handle well a variety of printer/scanner combinations.

2D bar codes, and standards in the consumer PC domain

It would seem inevitable that a single standard symbology be settled upon in the consumer PC domain. The same pressures that have largely forced a single standard in operating systems would seem operative here.

There is a learning curve attached to the use of any symbology. On the printing end, the manner in which information is formatted, and the uses to which it can be put, will be peculiar to the symbology and the software in which it is embedded. On the scanning end, the standard interface a consumer might expect will likewise depend on the symbology and the software developed around it. To reduce the demands placed on mastering the relevant technologies, organizations will choose the one in most common use.

Quite critically, the penetration of the symbology will determine its effectiveness. An advertiser, for example, wishes to reach the maximum number of consumers. She will wish to employ only one symbology in the space available to her. She will choose the technology most pervasive. Thus, ineluctably, consumer software will converge upon the symbology with the greatest penetration, with other symbologies at most occupying niches.

We will soon argue that paper-based digital information will come to serve as the core, glue technology that will integrate and enable a vast array of other technologies. The form this integration will assume will depend very much on the software application that supports the symbology. Users will standardize on this application in order to take advantage of the many features it will facilitate.

Application of Paper Based Digital Information

Paper as User Interface

In this section we describe a concept that represents a revolutionary new paradigm of User Interface, based on paper.

It is today universally acknowledged that the graphical user interface (GUI) was a fundamental improvement over the command line interface of the first computers. Yet the paradigm of the GUI has by now largely exhausted its potential to make interaction with a computer easier and more effective for most people. Evidence of this is that first time PC buyers have become a small and diminishing fraction of the PC market. The market for the GUI appears to have reached a ceiling.

It is our conviction that the concept we are proposing will be as basic an improvement over the GUI as the GUI was over command line interaction. Unlike many other such grand pronouncements, this assertion is testable in the best sense. We predict that the concept we are proposing will extend the use of computer technology to the majority of the population, who, to this day, have shown little inclination to utilize the standard GUI.

2D bar codes can help solve the most fundamental problem facing the acceptance of personal computers in general, and electronic commerce in particular: the daunting host of application interfaces a consumer must grasp, and feel comfortable with, to use these technologies effectively. Even those who succeed in mastering a few such interfaces rarely achieve fluency in them all: the sheer number of them is too overwhelming.

The ease-of-use of ordinary bar codes serves as a model for the potential of 2D bar codes.

It is in large measure the context sensitivity of typical bar codes that explains their remarkable pervasiveness. A bar code derives its power from its attachment to the very object about which information is sought. 2D bar codes possess this capability, but surpass linear bar codes by incorporating large amounts of data, and by making it possible to connect a document or object to any entity in the digital world.

As a technology, bar codes also boast extraordinary ease of use. Once a user has learned to scan with the bar code reader, she needs to know nothing else. The content of the bar code itself will direct the further actions of the device to which the bar code reader is attached. It is this basic, intuitive notion that we are proposing to ground a new paradigm of user interface.

The basic concept is this: paper can itself function as user interface. On a sheet of paper, one can encode patterns that automatically invoke certain functions when scanned. The paper would include a description of the actions that would ensue if the patterns were scanned. The patterns become in effect paper-based "icons." Just as the notion of icons has proved remarkably fruitful in standard GUIs, so will they also if embedded in documents.

One class of GUI icon may serve as a familiar model for what paper-based icons can do. These icons support the automatic registration of software. When clicked upon, they initialize the modem, call up an 800 number, and transmit registration information.

Encoded patterns on paper can indeed be more powerful than such GUI icons -- and herein lies much of the force of the new paradigm. GUI icons are virtually always generic in that they apply uniformly to any user who would invoke them. Information peculiar to the individual, and required for an action, must be obtained by other means. For example, when registering software, one is obliged first to enter by hand a fair amount of personal data: name, address, phone number, company name, title, etc.

In contrast, patterns on a paper bill, for example, could contain individualized information - name, address, account number, keys, current outstanding amount, minimum payment, etc. It might also contain information peculiar to the transaction implicit in the bill - an on-line dial up number, the kind of transaction expected, the type of account. Banking software might independently store on the consumer's PC relevant bank account information. Thus, a simple scan of the bill - an act so intuitive any consumer could understand it - could, in principle, pay the bill. It would invoke the banking software, combine the information for the bank account and the payment transaction, call up the on-line number, and transmit account number, payment amount, bank account, digital authentication, etc. (Alternatively, the software might call up the bank, and the conduct the transaction via that route.) If it is felt that the transaction is too easy, so that an inadvertent scan would pay a bill when not really intended, then remedies are straightforward. A standard screen, detailing the effect of the transaction, could create a pause before the transaction is consummated. Some quite deliberate action - shift-X for example - might be required before consent is assumed.

In the future, the actions that may ensue might include anything a PC can do: dial up a number, invoke a fax-back, update a file, retrieve information over the Internet, reboot Windows, print a document, pull out a video from the hard disk or a CD, or any combination of the above. Indeed paper based icons might be regarded as extending windows to paper documents and the real world: a dialog box, or menu, or World Wide Web page could be printed on paper with a pattern next to it, and when the pattern is scanned in, precisely the same "window" appears on the PC, fully enabled.

What is crucial to note about such a scenario is that it depicts a transaction inherently easier, and more comfortable, than any purely electronic alternative. The user has been spared all possible keystrokes and point-clicks. There is no navigation, and no data entry to indicate the particular thing one wishes to have done. All such detail is implicit in, for example, the bill in one's hand, and the encoded pattern makes it explicit to the computer. An exclusively electronic transaction, in contrast, would demand that the particular intention be communicated manually to the computer. It is for this reason that the standard GUI requires an array of interfaces, one each for each application. This additional complexity deters most people from making use of purely electronic transactions altogether.

Similarly, statements, forms, and other standard consumer correspondence could be encoded to capture desired and relevant actions. The locus of the decision to proceed is entirely situated in the comfortable realm of paper, rather than on the computer monitor. The computer becomes a mere prosthesis for actions contemplated and decided in the ordinary physical world.

Because of the intrinsic advantages such paper-based transactions would enjoy, they promise to become the most common means whereby people conduct electronic commerce, and other computer based transactions.

Indeed the technology we have described will likely extend the benefits of computer technology to new segments of the population. It is widely acknowledged that the most crucial obstacle to computer use among the population at large is its still formidable difficulty. A PC is complex in ways no previous consumer technology had ever been allowed to be. Paper-based icons can render the interface to computers so simple that it can draw in even the most ardent technophobe. It can do much to bridge the gulf between the technological haves and have nots.

It is the USPS that most stands to profit by the adoption of this approach: it would be the primary delivery mechanism for the encoded paper document. We elaborate on this point in a section to come.

Scanner penetration into the consumer market

An obvious issue arises here. For an audience to read the digital information, they must have scanners to do so. Why should we believe they will ever have them in numbers?

To begin with, scanners are in their own right achieving great popularity. Giga Information Group reports that in 1995, 1.3M standalone scanners were sold, and in the year 2000, estimates the number sold will exceed 4M. And Giga estimates that 7.2M multi-function peripherals (MFPs), which will include the capability to scan, as well as print, fax, and copy, will be sold in 1999.

Of course, the Holy Grail here is for each PC to arrive bundled with a scanner. There are hopeful signs of this. HP, Compaq, Packard-Bell, and Canon now sell PC models which include scanners.

This trend will only grow. Scanners are subject to the same forces of technological progress as PCs themselves. It is a certainty that, over time, the prices for consumer scanners will come down dramatically, even from their currently reasonable and generally affordable levels. It is a certainty also that their power, in terms both of resolution and speed, will increase.

It will soon be the case, if it is not already, that the consumer scanner lacks only the killer app to make it ubiquitous. Consumers nowadays buy scanners chiefly to perform faxing from their PC, convenience copying, and storage of documents on the PC in the form of images. These needs are not perhaps of universal importance, or at least are not so regarded yet.

Digital communication and storage, however, are of understood utility to all users. Already, this fact has made the floppy disk, the CD, and the fax/modem virtually universal in PCs. If paper offers unique and important digital communication and storage capabilities -- and it should be readily apparent that it does -- it too will take on, and will inexorably assume its destined role in the digital world. Scanners -- bundled with the right, standard software -- will become the enabling technology all must possess.

Why this new paradigm matters to the USPS

Forces at work in technology and the marketplace would seem to compel the USPS to embrace the new paradigm offered by paper based digital information.

Perhaps more than any other major organization, the USPS has a great deal at risk in the electronic revolution. It is true that people have shown a steadfast appreciation of paper as a medium for human readable information. Publisher of newspapers and magazines at one time greatly feared that the digital juggernaut of the World Wide Web would put them out of business. Yet they have found instead something remarkable. Sales of their printed editions have not been in any discernible way altered by the Web, even when they post for free the contents of their very publications.

Yet the case of the USPS is importantly different. The revenue base of the USPS is paper mail. And mail is not largely a one way transmission of information, like newspapers and magazines. A piece of mail is more typically a call to action. A bill must be paid, a statement must be reconciled, an inquiry must be responded to, a letter must be answered, a needed product must be purchased. People may feel most comfortable receiving information on paper, but if a response is necessary, other features may assume greater importance: convenience, timeliness, and ease in effecting the response. The risk for the USPS is that all such actions might be transported to a purely electronic realm, where all information is received electronically, and responded to electronically. Such transactions hold forth the promise of greater effectiveness than proceeding as before by utilizing ordinary paper mail.

The paradigm we are espousing would address this risk directly, and present to both consumers and the USPS what they would seem to want and need. Digitally empowered paper would offer consumers the best of two worlds. They would have on the one hand the comfort of receiving their information on paper, so that it could be read, stored, organized just as before. They would have on the other hand a direct link to the digital world: paper mail would function as a ticket to perform, with absolutely minimal fuss, the very transaction they would wish to bring about. The USPS would on its part retain a long-term and vital role in commerce, by delivering the encoded paper documents to the designated individuals in a trusted manner. USPS need not, therefore, resign itself to a long, certain decline in the use of paper mail. The attraction of digitally empowered paper mail to businesses, advertisers, and consumers would effect instead growth in the underlying business of the USPS.

Of course, the utility of digitally empowered paper mail hangs on consumers widely adopting scanners and suitable software. This is the challenge for the USPS. It must promote the paradigm to reap the rewards. Personal scanners are as crucial to the future of the USPS as modems are to the future of telecommunications companies.

Postal Applications of Paper Based Digital Information

In the remaining sections we go into more descriptive detail about how the USPS might put to use the technology and paradigm we have outlined.

Importance of 2D bar code to USPS

2D bar code presents opportunities for the USPS that go far beyond indicia of postage paid. Indeed, 2D bar code could reshape the USPS.

The USPS's greatest resource is its army of postal carriers and the resources that service that army. This army of postal carriers represents a tremendous resource because it allows for point-to-point delivery of mail from any two points in the country at a cost that is far less than any other organization can provide. This same resource can prove to be a concern if there is not enough mail for these carriers to deliver.

Absent a technology that connects the paper and digital worlds, each of us would eventually be forced to shift from paper to digital communication because the advantages of digital communication would grow too great. To date, paper communication has been almost entirely for human readable information, and digital communication has been almost entirely disconnected from paper. While paper communication continues to enjoy great advantages, such as ease of use, digital communication enjoys its own significant advantages, and the digital advantages will continue to grow. Evidence of a forced shift exists today, including, for example, the I.R.S. requirement that depositors of taxes switch to electronic deposits. This shift represents a potentially significant conflict. Almost all of us have grown accustomed to the ease of producing, distributing and absorbing information on paper. The processes developed to handle the paper flow of information represents untold hundreds of billions of dollars in investments and a switch from these processes to entirely electronic processes would entail investments of further billions. More importantly, a switch from paper to an entirely electronic information flow would require a drastic change in our way of thinking and our way doing things.

What is needed, then, is a process that simultaneously offers the advantages of both paper and digital. That is the long-term importance of 2D bar code - the link between the paper and digital worlds. The magnitude of that link can be enormous to society in general and the USPS in particular. Paper based information flow annually generates hundreds of billions of dollars in revenues in the U.S. Digital information flow likewise generates hundreds of billions in revenues in the U.S. 2D bar code serves as the most direct link between those information flows which annually generate revenues of perhaps half of a trillion dollars.

2D bar code's link between the paper and digital worlds is particularly important to the USPS. The USPS today predominantly serves the paper world. Absent a significant change in focus, the USPS will continue to depend on the flow of information on paper. But society will increasingly switch to a digital flow. 2D bar code will therefore provide both a carrot and a stick to the USPS. If the USPS does not avail itself of the opportunities presented by placing digital information on paper, it will suffer an ever increasing erosion of its core business. If, alternatively, the USPS seizes the opportunity of providing what society sorely needs and will need even more in time - a way of simultaneously providing digital data and paper based human readable information - the USPS can strengthen its core business well into the future.

The USPS's core resources and competencies make it uniquely qualified to take advantage of the opportunities presented by the link between the paper and digital worlds. There is no other organization that can approach the efficiency of the USPS in delivering paper based information to each of the over 100 million postal addresses in this country. While the information superhighway of today is based on electronic transmission, the information superhighway of tomorrow may be primarily based on paper with the USPS acting as the primary carrier. Indeed, the number of items of digital information delivered by the USPS in one day could exceed the number delivered by the Internet via e-mail in a month.

The purpose of the remainder of this paper, then, is to outline some of the opportunities that 2D bar code presents to the USPS, opportunities that will serve as a catalyst to society's adoption of 2D bar code as the necessary link between the digital and paper worlds and, therefore, the extension of the USPS's core business and competencies into the digital future. The opportunities are grouped into two categories: postal indicia enhancements and advanced applications.

Postal indicia enhancements

The PaperDisk 2D bar code technology allows density of data that can be many times greater than other 2D bar codes. The amount of data that can be stored in 2-4 square inches (the anticipated size of IBIP indicia) far exceeds the amount needed to encrypt a message containing the meter number, postage used, destination zip code, time, and date, as well as the digital signature and certificate. This excess capacity creates opportunities for storing other data. Just as items of digital information for consumers will soon be piggybacked on television signals, so also can useful information be carried in the pre-existing "signal" of indicia.

A number of possibilities follow:

• Provide in digital format the essential information contained within the envelope. Because the postal indicia will be printed anyway, a prime opportunity exists to use the indicia to provide targeted digital information with minimal additional changes to the otherwise existing processes.

There are numerous circumstances where digital data would be useful. Recipients of bills (e.g., utility bills, credit card bills) may wish to store digitized versions of those bills on their computers, including all the details that make up the charges (e.g., for a credit card bill, the payor, amount, item purchased, and date of each individual charge). Monthly banking statements could contain itemized details of each transaction. If a memo, letter or notice is sent, a digitized version of the text could be provided, obviating the need to scan the document, perform OCR, and correct the mistakes produced by the OCR process.

Because the information carried in the indicia is on the outside of the envelope, some form of security may be needed in some circumstances. Certainly the security is already greater than for information on postcards, because the contents cannot be read by casual inspection: the pattern must be scanned. The level of security required should surely be satisfied by existing standards over the telephone. For utility bills, using password protection where the account number is the password might be appropriate. For checking account and charge card statements, the account number and social security number could both be required passwords. For mail with no associated account number, a password could be written in the letter itself.

• Allow customer based advertising and other customer information. The types of information possible are limited only by the data carrying capacity of the indicia:
  1. customer advertising repurposed from other media
  2. detailed product information
  3. software that allows recipients to navigate the postal customer's voice mail and fax-on-demand system. Software can cause a computer to emit tones through a fax/modem to the postal customer's voice mail and fax-on-demand system. The software could also graphically present a logic tree of all choices. The advantage to the recipient is being able to navigate through the maze of choices far faster than present telephone based voice mail and fax-on-demand systems. Instead of taking several minutes to listen to multiple levels of choices to get to the desired information, the recipient could quickly glance down a menu of choices, click for further menus, and reach the ultimate destination in seconds rather than minutes.
  4. an abbreviated version of the postal customer's web site. While the amount of graphics would likely be minimal, the site could provide significant amounts of text: information about the company, its products, a list of employees and their telephone numbers and e-mail addresses. The site could also provide large number of hyperlinks within the site as well as links to on-line URLs. The recipient could be just one click from anywhere on the Internet.

• Provide public service announcements and software. For example, during Black History Month, the indicia could include brief biographies of accomplished African Americans. During January, the indicia could include tax preparation information, software, or links to free preparation software on-line. Health announcements could be made year round. The USPS could offer collectors' stamps during the holidays.

In addition to the 2D bar code, the indicia could include text describing the digital content. Providing public service digital content along with descriptive text would be comparable in spirit to many stamps sold today, but would provide much more information.

• Capture an image of some portion of the envelope or mailing label, place that image in a compressed file and store that file in the postal indicia. This technique can provide further safeguards against counterfeiting.

• Provide digital information describing the contents of the mail piece. This information is especially important for the blind and others with visual impairments.

Ordinary mail can prove an extraordinary burden for the blind. Technology exists allowing the conversion of text into digital data followed by conversion of the digital data into synthesized speech. This technology works best, however, with single pages of typewritten text in a single column. The task of going through several pieces of paper each of which can contain graphics and text of various fonts scattered in various locations and formats can prove difficult and time consuming at best and impossible at worst.

Providing digital information would also assist those millions who are sighted but have imperfect vision. For example, providing a digital version of the text enclosed in the envelope would allow the recipient to print, or view on the screen, substantially enlarged characters

Placing descriptive information in the postal indicia can, at a minimum, assist the blind and visually impaired in sorting through their mail. Envelopes have two sides, a front and a back. These two sides typically feel different to the touch. The back of an envelope typically has a flap that can be felt with one's hands. The front often has a plastic window, also discernible by touch. The top and bottoms of envelopes can also be determined through these tactile differences - the envelope flap is at the top. Thus, through touch, the upper right corner of the envelope front can be determined swiftly. If postal indicia is always in this location, the blind and visually impaired can easily locate the postal indicia, place that indicia on a computer scanner, and decode the digital data contained in the indicia.

As a service to those with visual impairment, the USPS could require all users of postal indicia to provide some description of the contents, or at a minimum, an indication of the sender of the mail and an indication that no further description is provided. This information can greatly aid the recipient in sorting through the mail. Indeed, given the ease of providing this information, the ease of use, the insignificant extra cost and the USPS's commitment to using 2D bar code in postal indicia, providing digital data to the visually impaired would be a reasonable accommodation to this group of disabled citizens.

The description provided could be quite extensive. One possibility is to digitize the entire contents of the mailing. Another possibility is to provide an audio file that describes the essence of the mailing. In some instances, issues of privacy could limit what is placed on the outside of the envelope. Many of these issues can be solved through encryption. For example, utilities may wish to place the entirety of bills in the postal indicia, removing any need to open the envelope. Privacy issues would exist, but are probably not critical. Using password protection, with the account number as the password, would probably suffice.

• Treating the postal indicia as a channel that carries digital data, sell some portion of that data carrying capacity for purposes such as advertising. In one variation, the postal indicia could include human readable text describing the underlying digital data. In another variation, the advertising would be in digital format without descriptive text - this would probably work best if something else entices the recipient to scan and decode the 2D bar code. In either instance, the advertising revenues could be used to partially offset the cost of postage. In one instance, the postal customer could choose to include in the indicia the advertising of another (with or without descriptive text) in exchange for a lower postal rate.

Advanced postal enhancements from 2D bar code

The U.S. Mail could enjoy further benefits from 2D bar code by extending the use of the technology beyond the postal indicia. Placing greater amounts of 2D bar code on paper inside the envelope could significantly increase the data storage capability of the total mail piece while largely eliminating any security or privacy concerns. Some of these benefits could also be achieved by placing 2D bar code on the envelope itself in areas other than the area reserved for postage indicia.

While substantial benefits could be derived from further uses of 2D bar code even without USPS involvement, greater benefits would result if the Service takes an active role. Private concerns and individuals would be able to license our technology for use on paper to be placed inside envelopes. The benefits of increased data capacity and increased security would be available to everyone licensing the technology. But, there are courses of action available to the USPS that would facilitate and thereby increase usage of the technology.

It is clearly in the best interests of the USPS to encourage and facilitate usage of the technology. The future of the mail system in the digital age is at stake. To the extent the USPS can encourage and facilitate technologies that digitize mail, the USPS will retain and increase relevance into the digital age. Otherwise, mail will increasingly lose relevance.

There are several actions the USPS can take to facilitate digital mail. Postal meters designed primarily to generate indicia of postage paid could also be used to print digital data in 2D bar code. The digital data could be used as an integral part of a new mail system, a system where information is distributed electronically before being printed, and the printed information (including 2D bar code) is then delivered by local post offices through the existing postal carrier processes. Digital data printed using 2D bar code could be used as an integral part of electronic commerce, with part of the process electronic and part using 2D bar code.

The printing process used to print postal indicia in 2D bar code could also be used to print 2D bar code symbols that encode information other than indicia. This information could be used in any number of contexts, some perhaps not directly postal related. Presumably, the printing could be done with little or no postal charge, and would lack the normal message associated with postal indicia. Obviously, if done from a meter rather than directly from a computer, the meter would require some method of generating or importing digital data from the customer. While printing the digital data with the postal meter may not afford the flexibility of personal computers and normal printing processes, the postal meter would have the advantage of being a process in place capable of producing a large number of pieces, and would add value to the postal meter.

The USPS might pursue a system where mail is distributed, printed and delivered, with 2D bar code as an integral part of this new paradigm, rather than just the current print, distribute and deliver. The current paradigm of paper based information transmission by mail includes printing the mail piece, delivery of the mail piece to the USPS, USPS sorting of the mail by intended location, moving the mail piece from the drop off point to the recipient's nearest post office, sorting at that post office by address, and delivery by postal carrier. All of these physical steps have been eliminated with e-mail. A number of these steps have been eliminated even when paper continues as the media. Xerox has been very successful in implementing a "distribute and print" paradigm where the contents of a message (e.g., the contents of a pamphlet) are first transmitted electronically to the recipient and then printed. This process has a number of advantages over the previously existing process: elimination of the cost and effort to physically deliver the printed message, speed of the overall process, and elimination of overprinting. The USPS could gain many of these same advantages by adopting a similar paradigm of mail transmission.

In light of the speed and relatively low cost of e-mail, the USPS will find itself under increasing pressure to deliver at a cost more competitive with purely electronic transmission. There are advantages that the USPS will bring into this competition. Digital communication on paper affords the best of both the paper and digital worlds. Human readable information on paper is significantly easier and faster than human readable information on a computer. Human readable information on paper requires no further equipment or training by the vast majority of recipients. This human readable information can then be supplemented, collaterally or substantially, by digital information on paper. Because of these advantages, transmission of information on paper need not be as inexpensive as purely electronic transmission. But, as availability of computer equipment and on-line access becomes more commonplace, and as the resistance to learning new techniques erodes, the advantages of digital communication together with the low cost will bring increasing price pressure on the delivery of information on paper.

A distribute, print and deliver paradigm of information dissemination can eliminate some of the physical steps of the present mail system and thus afford the opportunity of lowering postal costs as well as the overall costs of preparing and mailing information on paper. While this new paradigm would in time lessen the need for some current Post Office functions and resources (e.g., sorting and shipping at the pick up point) the most important resource, the network of postal carriers, would remain an integral part of information dissemination.

The distribute, print and deliver paradigm contemplates electronic transmission up to the general location of the ultimate recipient. The postal customer would electronically transmit the mail message to the post office (or a post office contractor) responsible for delivering mail to the ultimate recipient. This transmission could be through a private USPS network, the Internet, by direct modem to modem contact, fax transmission, or some other means. Mass mailings could be accomplished through satellite transmission - all post offices could receive the basic message together with either the addresses of the recipients or with a message to look for a list of local recipients sent by a second transmission. Varying levels of encryption protection may be appropriate depending on the sensitivity level of the mailing. The cost of the electronic transmission would presumably be comparable to current e-mail transmissions and, unless accomplished through a USPS network, borne by the postal customer. The act of sorting mail messages by intended location could be performed entirely by software.

Once received in the general location of the ultimate recipient, the mail message would be printed, handed off to the postal carrier and delivered. Each post office should accumulate each day's electronic transmissions from all sources, sort those messages by individual postal carrier and, for each postal carrier, sort by order of ultimate delivery. The day's mail would then printed in that order and given to the postal carrier. The reception of electronic messages, electronic sorting and printing could be performed inside the post office or contracted out to local printers and then delivered to the post office.

The printing of mail messages would presumably entail certain standard printing processes and paper stocks. The process would ideally include laser printing on at least 3 types of paper stock. First, postal customers should be able have mail printed on a standard stock. This stock should have a low cost and, ideally, would fold into a sealed mail piece. Second, a secure paper stock should be provided. This stock would be available for printing checks, tickets, coupons, secure messages, etc. Third, a paper stock that includes a return envelope should be made available. This paper stock would be most appropriate for bills and other mailings that anticipate a reply by mail. Larger post offices and post offices that contract out to commercial printers would presumably be able to offer a greater variety of paper stocks and printing processes.

In a variation of the distribute, print and deliver paradigm, mail recipients should be allowed to receive their mail electronically by connecting to the server at the local post office and downloading their day's mail. This would reduce the paradigm to distribute and deliver where the delivery is electronic rather than physical. This variation is comparable to e-mail in many respects. This system offers, however, many advantages over traditional e-mail. The sender does not have to know the recipient's e-mail address or know whether the recipient can receive e-mail. All that is needed is the recipient's street address. The recipient has the choice of whether to receive its mail physically or electronically, thus accommodating the individual preferences and processes of each recipient. If, for example, the recipient is a business receiving catalog orders, the recipient can choose that method of delivery which fits best into its existing methods for processing orders. If the mailing contains our 2D bar code, the recipient could derive the underlying digital data whether the mailing is on paper or entirely electronic. If the transmission is entirely electronic, the recipient would derive the digital data from our 2D bar code without the need to first scan paper. While the transmission is entirely electronic, routing the transmission through the USPS can provide an official authentication of the date and time of mailing and delivery. Finally, an entirely electronic transmission would cost considerably less to produce and deliver than printed and delivered physical mail. This cost savings could result in either greater profits for the USPS or greater cost competitiveness with e-mail.

2D bar code should be an integral part of this distribute, print and deliver paradigm. 2D bar code could easily be included in the process because digital transmission is an integral step, and the 2D bar code would simply be another part of the digital transmission and printing. Providing digital data on these paper mail pieces would present all the opportunities discussed above, linking the digital world with paper based communication, as well as the concepts of electronic commerce discussed below.

2D bar code could serve as a new paradigm of electronic commerce. This new paradigm has two main components, a hybrid system of check writing and processing, and expedited bill presentment and payment.

2D bar code could serve as integral part of a new hybrid system of check writing and processing. The current checking system typically involves the payor writing a check, recording that check, sending the check to the payee, the payee opening the envelope, endorsing the check, depositing the check in a bank account followed by the bank recording the check, settling with the payor's bank, sending the check to the payor's bank through the federal reserve system, with the payor's bank then sorting the checks by payor and sending those checks back to the payor with a checking statement. This system involves considerable effort by all parties - the payor, the payee, and the banks. Some or all of this process can be automated. Unlike other payment systems suggested as replacements of the current system, the hybrid system outlined allows the payor and payee to choose the degree of automation and the degree of change from current payment processes.

At the core of the hybrid system of checking is the inclusion of 2D bar code on each check. The 2D bar code would identify information about the check: the payor, the payor's checking account, the recipient, the check number, the date the check is written, and the amount of the check. The hybrid system contemplates that a personal computer would generate the check. The system also contemplates that the payor would be able to choose for each payment or selected group of payments one of a number of methods of issuing a check or checks.

The payor could choose to have the computer print out individual checks. This individual check would contain 2D bar code containing the basic information about the payment. Unlike current checking methods (even those producing computer generated checks) the digital data could include information that assists the payee to process the check, such as the payor's account number with the payee, the amount due and the date due. Thus, the check would not require attachment of a bill stub because all of the essential information on the bill stub would be on the check, eliminating one of the major issues in electronic payment systems. In addition to or in lieu of a physical signature by the payor, the 2D bar code could include the payor's digital signature.

The payor could also choose to issue a number of checks as part of a single document. That single document could contain both textual information describing each payment and 2D bar code containing the essential information about the payment, including bill stub information. The payor would then send that single document to an intermediary responsible for routing each of the payments to the appropriate payees. Banks and credit card companies are likely candidates for this intermediary role. For those payees not willing to accept electronic funds transfers, the intermediary could send out a check. As discussed above, these checks would contain 2D bar code containing the essential information about the payment, including bill stub information. If the payor is uncertain whether the payee can accept bill stub information in digital form, the payor could scan the bill stub and include that scanned image in the 2D bar code sent to the intermediary. The intermediary could then send both a check and a printout of the bill stub derived from the 2D bar code. For payees typically receiving numerous checks (e.g., utilities, and mail order companies), the intermediary could aggregate a number of payments from a number of payors into one check. The 2D bar code on that one check (or attached statement) could contain the payment and bill stub information for each of the payors.

The check's 2D bar code could contain a picture of the payee so as to prevent unauthorized check cashing. The person accepting the check would be able to determine whether the picture matches the person cashing the check. Fake identifications would not work because the payee's picture would be digitally printed on the check itself. Including pictures in the 2D bar code would probably be most appropriate for governmental checks such as those issued for Social Security benefits. The 2D bar code could likewise include digitized fingerprints or other unique identifiers. For further security, the digitized picture could be encrypted with the payor's private key and decrypted with the payor's public key.

Because the checks' essential information is in digital form (i.e., the 2D bar code), the payor can print and send the checks physically, generate and send the checks electronically, or print the checks and then send them electronically. Electronic transmission could be on-line or by facsimile. The payor is thus afforded discretion not only in how checks are produced but also in the how they are sent.

Digital checks contained in 2D bar code offer advantages in the presentment process as well. Because the check's essential information is contained in the 2D bar code, only the 2D bar code need be routed through the check clearing process, not the entire check. And, because that 2D bar code represents digital information, only the digital information need be transmitted. This transmission could be entirely electronic. Paper (if any) could end with the person accepting the check for deposit or cashing. The digital information from the check itself could be supplemented with processing information. For example, a signature on a physical check could be scanned or a signature could be captured electronically and, in either instance, the signature file could be included in the 2D bar code. Likewise, a picture of the person cashing the check could be included in the supplemental 2D bar code. The person accepting the check for deposit or cashing could attach digital information concerning the time, date, account and amount of deposit as well a digital signature acknowledging acceptance of the check. This supplemental information concerning acceptance could serve as a substitute for the paper trail existing today.

Use of 2D bar code could change the way checks are accumulated and returned to the person writing the checks. Instead of physically aggregating the checks, bundling those checks with a checking statement and sending the bundle to the check writer, the bank could send just a statement with images of the checks and 2D bar code that includes all the digital information accumulated with that check along the way. That accumulation of digital data, including digital signatures, could serve as proof that the payee did indeed receive payment, much as a photocopy of a check typically serves as proof of payment today. Once again, because the essential information contained in the statement is digital or could be made digital, this statement could be transmitted physically or electronically.

The USPS can provide several critical functions in this hybrid method of check writing and processing. Any physical movement of paper would typically require use of the mails. The USPS's digital signature, time and date stamp could serve as official authentication of many aspects of the transaction, especially the time and content of transmissions.

The distribute, print and deliver paradigm of mailing described above could be used for the writing of checks. Instead of physically printing and recording a check, attaching that check to the bill stub, inserting the check and bill stub into an envelope, addressing and sealing the envelope, applying postage and mailing the envelope, the payor's computer would send a message to the USPS's computer to print and deliver the check, together with relevant digital data printed in 2D bar code. The overall costs to the payor could be substantially reduced. The hybrid system of check writing would integrate well with the expedited system of bill presentment and payment described below, providing a compounding of advantages.

The USPS could itself serve as the financial institution backing the checks written through the distribute, print and deliver paradigm. These checks could take the form of postal money orders instead of bank checks. The payor would presumably need an account with the USPS to take advantage of this new service. This account could be the same account as a postal meter account, using the available balance to issue postal money orders in addition to postage. There are several advantages of using postal money orders in this way. The volume of postal money orders and the revenue therefrom could increase significantly. The dual purpose of postal meter accounts could encourage others to use postal meters reducing the need for postage stamps. Integrating the ability to issue money orders with the distribute, print and deliver paradigm could prove a considerable incentive for banks to participate in this new paradigm - the savings in the overall costs of issuing and processing checks could prove so great that banks may feel compelled to adopt the new system.

With the inclusion of 2D bar code, a bill could contain digital instructions directing a computer to pay that bill. There are many possibilities on how that bill could be paid using a computer and in one embodiment, software would allow the recipient to choose from these many methods. The recipient would receive the bill in the mail and then scan and decode the 2D bar code. The 2D bar code would contain the essential information of the bill - e.g., the creditor, amount, due date, account number and acceptable methods of bill payment. The recipient could preprogram the method of payment of bills from this creditor or could choose among options each time this creditor's bill comes. Ideally, any such software would allow the recipient to process a number of bills simultaneously - e.g., the recipient would scan a number of bills at the same sitting and then direct the computer to execute payment of all the bills, either all through the same method or through a method chosen for each bill. The methods of bill payment can range from entirely electronic to old-fashioned paper checks.

In one instance, the creditor would have prearranged for the possibility of receiving electronic funds transfers. In this instance, the recipient's computer would connect with the recipient's bank and electronically direct the bank to transfer the funds to the creditor according to the information provided in the 2D bar code.

In another instance, the digital data contained in the 2D bar code could be ported to the recipient's favorite personal financial management software (e.g., Intuit's Quicken). The personal financial management software could then print a check to be mailed with the bill or the recipient could handwrite a check and the personal financial management software would use the ported digital data as a record of checks written and expenses incurred.

The recipient may choose to pay with borrowed funds instead of available funds. If the creditor allows payment by credit card, the recipient could direct his or her computer to return a notice to the creditor, e.g., by printout and mailing or by fax, indicating a credit card number to charge for the bill.

As a further possibility, the 2D bar code could be used for both bill presentment and payment. A recipient could scan and decode a bill or, preferably, a number of bills, and direct the computer to issue a check or checks. This issuance could be pursuant to the hybrid method of checking described above. Combining the expedited bill payment and presentment system with the hybrid method of checking would afford all parties full flexibility in integrating the digital world with the more familiar paper world and could provide the greatest convenience in bill payment. For example, the recipient could stack a number of bills in the scanner, press a button, and the scanner would start scanning the bills, the computer would automatically decode the 2D bar code, generate another 2D bar code for payment of the bills, and fax that 2D bar code off to the bank.

IBIP and PaperDisk symbology

The symbology of PaperDisk addresses in many ways the core concerns of IBIP.

There is most obviously the demonstrated ability of PaperDisk patterns to encode large amounts of information compactly.

By way of comparison, a PDF-417 pattern with a modicum of redundancy may be expected to achieve at most 300 bytes/sq. in. in density. If the pattern is confined to 4 square inches, as the IBIP specification suggests for the indicia, then at maximum this would be 1,200 bytes. Since perhaps 500 bytes of this would be reserved for the minimal data requirements of the indicia, little room remains to support further features.

To begin with, the information capacity of the indicia bounds the potential for expanding security features, should such expansion become necessary. For example, as mentioned in an earlier section, it might become key to encode a low resolution, highly compressed image of a mail piece itself in its indicia, to forestall large scale copying of indicia and reuse on similar mail. Such an image might demand 1-4 KB, depending on the chosen technique. We have found, for example, that a quite satisfactory 75 dpi image of a letter can be compressed, via JBIG, to a bit more than 2KB. The virtue of encoding an image of the very mail piece is that one could know immediately and locally that the indicia was fraudulent. One need not check it against complicated and perhaps imperfect audit information, which may in any case become available only at some later time.

Moreover, when IBIP reaches the stage in which value added services are to be incorporated, the amount of information the indicia can carry will determine how much added value can be achieved. The amount of value that can be added will in turn affect the size of the market that IBIP may expect to develop.

An obvious value added feature for the indicia would be to enable mailers to communicate information to the recipients of the mail pieces. The exploding market for personal scanners can drive this form of communication. Mailers could include for example electronic forms, e-mail addresses and associated public keys, lists of telephone numbers, fax numbers, URLs, product offerings, regulatory information related to the particular mail piece, etc. This information could automatically pop up on a consumer's computer screen after a simple scan of the mail piece, as well as being stored permanently on the PC for future reference. Clicking on the appropriate item on the screen - telephone numbers, fax numbers, URLs, etc. -- might then invoke related functionalities.

It is, of course, difficult to predict in the abstract precisely what data carrying capacities indicia based on PaperDisk symbology could support. This hangs of course on the precision of the printing process and of the scanning process. The effect of printing any material on envelopes will depend on such things as the thickness of the envelope, whether a label is used, the nature of the substrate on the envelope, the speed of the printing process, and the precise printing technique (inkjet, laser, thermal). Likewise, on the scanning side the speed and quality of the feeding mechanism will be crucial. Different types of envelopes may encounter very different treatment as they pass through these feeders.

Here again, however, the flexibility of PaperDisk suits the demands of the situation exactly. A PaperDisk symbol can be configured to attain the greatest density the particular printing process and scanning process can support. In some scenarios, it might be that this density is only enough to sustain the minimal requirements of IBIP indicia. Alternative symbologies, however, because they lack the full flexibility of PaperDisk, may be unable to satisfy those requirements. PaperDisk is therefore the symbology least likely to fail the most basic goals of IBIP.

Not all cases would be the worst case, however, and PaperDisk symbology is designed to exploit this. In particular, IBIP plans that indicia will be generated in two ways: by meters, and by printers connected to computers. The second alternative, which is expected in time to become the dominant one, is almost certain to enjoy greater control and precision in printing than the first. The computer based alternative should not be bound by the limitations of meters. From conception, PaperDisk symbology has been designed to capitalize on the considerable precision of off-the-shelf computer printers. Where there is added precision, PaperDisk can provide added density. Users, and therefore vendors, will have incentives to advance to the more precise printing methods.

Likewise, as scanners and feeders improve to permit more accurate scans, the densities can rise simply by reconfiguring the PaperDisk symbol. Thus, the symbology provides a natural and painless growth path, both on the printing end and the scanning end.

Unlike other symbologies, PaperDisk has, in a sense, already "solved the future." That is, it has come to grips with the knotty issues that arise when attempting to exploit very precise printers and scanners. These are the printers and scanners that will, in time, come on line in the mailing process. PaperDisk has performed the experiments, written and refined the software, and generated numbers to talk about.

What might be the capabilities of PaperDisk based indicia?

The capacity of indicia generated by computer printers in the near future may be projected under certain assumptions. We first assume that the printer is as precise as a 600 dpi laser printer. Today such printers are common and relatively inexpensive even in the consumer market. Since the typical user of IBIP would be a business, it seems safe to assume that this level of printing technology at minimum would be available. Next, we assume that the scanner is a 300 dpi 4-bit scanner. Since at its outset IBIP will not involve scanning all mail pieces, this too seems consistent with the technologies that would be available.

Under these circumstances, we have found that we have been able to sustain, quite safely, a density of 2,550 bytes/sq. inch, even when a document has been scanned via a document feeder. At 4 sq. in., this would comprise about 10KB. If the scanner were upgraded to a 600 dpi 4-bit scanner, we would project closer to 20KB.

By way of comparison, PDF-417 might be only 1,200 bytes.

Clearly PaperDisk indicia would make space for a profusion of security features and value added features.

What is certain is that this capacity would not go unused if available. What is also certain is that it would be regretted if it might have been available, but a less able technology had been chosen instead.

PaperDisk, IBIP, and the USPS digital signature program

Because of its power, the PaperDisk symbology can work as a synergistic link between a number of USPS initiatives. In particular, it can play an important role in the USPS digital signature program. Even in the context of IBIP, PaperDisk can enable functionalities that will grow the broader digital signature program.

The digital signature program can be supported by including within the IBIP indicia digitally authenticated information. This might include for example e-mail addresses and associated public keys from the sender of the mail. It might include regulatory information from the sender. It might also include information useful for promotional purposes to the sender, such as authenticated product offerings, special coupon or certificate authentication, legally binding contest information. These certificates might be variously used either in person, by paper mail, or by e-mail and electronic commerce.

The PaperDisk symbology is powerful enough to store entire legal documents on paper side by side with the human readable document itself. The digital information, along with its digital authentication, can be stored, organized, and filed just as the human readable document itself has been traditionally. On any future occasion when it may be important to authenticate the document, or to send it via e-mail to others, there is a seamless transition back to the electronic world.

It is key that a digital signature and authentication system allow frictionless movement from the domain of paper to the digital world, and back again. The system that best supports this stands the best chance to win in becoming standard.

(It is useful to note that the software that implements IBIP on the PC should have great penetration. The USPS can leverage this to very good effect. By folding into the IBIP software additional functionalities from related programs -- the digital signature program prominently -- the USPS can powerfully promote those programs.)

This brings us back to a natural extension of IBIP that could importantly enhance both IBIP and the digital signature program. The same meter or computer that produces indicia can generate PaperDisk symbols for digital information other than indicia. These symbols may be significantly larger than indicia, depending on the printing mechanism, and might encode and digitally authenticate documents of substantial size. When the symbol is printed by a standard computer printer, such symbols can, as we have seen, fill a letter sized page, and might express hundreds of pages of information. These documents would be authenticated via the PSD, and enjoy the same authentication as indicia, including a form of time-stamping. These symbols can then be attached to the human readable version of the document, and distributed, mailed, or stored. Immediately or in the future, the document may need to be sent via e-mail, or verified to have been produced on a certain date, by a certain company or even individual. In such cases, the symbol can be scanned in, and the document, its authentication, and its time entry recovered and sent to the appropriate party.

Prospects for consumer domain

Paper mail is at base consumer driven, and must remain appealing to consumers to prosper. Conventional 2D bar codes were not, however, designed to suit the concerns of the consumer PC domain, but rather to satisfy the needs of certain vertical markets. Not surprisingly such codes are in consequence ill-suited to consumer demands.

The capacity of a PDF-417 symbol is generally too limited to be of value outside of the restricted domain for which it was originally designed. An individual PDF-417 symbol effectively reaches a maximum carrying capacity of perhaps 2KB. For packing lists, for example, a prototypical target for the technology, this may suffice. For the larger world of consumer computer technology, however, it means very little indeed. The realm of consumer PC technology is populated by word processing documents, spreadsheets, and personal finance files. Such items of information far exceed in size the capacity of a PDF-417 symbol, or that of other conventional 2D bar codes.

The conclusion must be that PDF-417 and other such codes show little prospect of an important role in the consumer PC domain.

In contrast, a single PaperDisk symbol can hold 1MB of data. It is useful to compare this with the capacity of a floppy. The 1.44MB floppy disk has exhibited remarkable longevity - it was first introduced 12 years ago, and remains as a standard on nearly all PCs. Because PaperDisk automatically compresses its information, and the floppy drive does not, the effective capacity of a PaperDisk symbol can be, with high quality printers and scanners, quite comparable to that of a floppy. It is reasonable to believe therefore that PaperDisk is fully adequate to the typical demands of the consumer PC realm for digital storage.

Certainly PaperDisk symbology can come to occupy a large, vital place among the options available to consumers for digital storage and communication.

Conclusion

IBIP presents a genuinely unique opportunity to the USPS. By taking advantage of the pre-existing market for personal scanners, and at the same time fostering the growth of that market, the USPS can powerfully bolster its own core business, paper mail.

The indicia that IBIP will generate on mail pieces will be seen by almost every consumer in America, almost every day. This represents a promotional possibility for a new technology nearly without precedent. In number of items of digital information delivered, IBIP indicia will dwarf Internet e-mail.

Depending on what is built into the indicia, the consumer, when she looks at it, might have two very different reactions. She might say, this means something to me, I can use this. Or she might say, this is none of my affair - it's just Post Office stuff.

It would be long regretted if the consumer might have had the first reaction, but was instead closed into the second.

The USPS is in a struggle to maintain the relevance of paper mail. It can do little to affect directly what goes on inside the envelope. It can do a good deal to affect what happens on the outside of the envelope, and IBIP indicia represents the most powerful example and opportunity. By promoting the concept of digitally empowered paper through IBIP indicia, the USPS can foster the adoption of that concept in the contents of paper mail.

The interests of the USPS would be well served to explore this broad potential payoff for IBIP. The USPS is in a position to be master of its own destiny. It can be -- indeed must be -- proactive in, rather than reactive to, the electronic revolution.

We fully appreciate that IBIP may have been conceived with more limited goals in mind. This is understandable, for these goals were conceived with no awareness of the PaperDisk technology, and the greater potential it enables. Yet the highest levels of management at the USPS acknowledge that the survival of the USPS as we know it may depend on a modification in internal culture, and that the USPS, to continue and flourish, must become quickly responsive to new developments in technology and the marketplace. In this context, PaperDisk technology may represent an opportunity for the USPS to demonstrate its ability to adapt rapidly to new knowledge, and change direction to grow market share.

Biographies

Thomas Antognini holds a Ph.D. from the Massachusetts Institute of Technology, and is co-founder of Cobblestone Software, Inc.

Walter Antognini, J.D., LL.M., C.P.A., is an Associate Professor at Pace University's Lubin School of Business in New York, and is co-founder of Cobblestone Software, Inc.