Print data compression method and printer driver Number:7,145,696 from the United States Patent and Trademark Office (PTO) owispatent

Title: Print data compression method and printer driver

Abstract: A printer driver software product is provided for execution by a computer to produce compressed page data corresponding to a page layout. The driver includes instructions to generate continuous-tone data and bi-level text and black graphics data from print data corresponding to the page layout. Data compression instructions are also included in the printer driver. Upon execution the data compression instructions cause the computer to compress the set of continuous-tone data and the set of bi-level text and black graphics data to produce compressed page data corresponding to the page layout. The compressed data is then transmitted to a printer in communication with the computer. A printer driver software product according to the invention is particularly useful where a printer is coupled to a computer by means of a relatively limited bandwidth connection.

Patent Number: 7,145,696 Issued on 12/05/2006 to Silverbrook

---

Inventors:	Silverbrook; Kia (Balmain, AU)
Assignee:	Silverbrook Research Pty Ltd (Balmain, AU)
Appl. No.:	10/975,452
Filed:	October 29, 2004

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	10402217	Mar., 2003	6857726
	09436872	Nov., 1999

---

Foreign Application Priority Data

---

Nov 09, 1998 [AU]			PP7025

Current U.S. Class:	358/2.1 ; 358/3.24; 358/426.04; 358/426.13; 358/426.14; 382/176; 382/239
Current International Class:	H04N 1/40 (20060101); G06K 9/34 (20060101); G06K 9/46 (20060101); G06T 7/00 (20060101); G06T 9/00 (20060101); H04N 1/41 (20060101)
Field of Search:	358/1.9,2.1,3.24,462,426.04,426.01,426.02,426.13,426.14 382/173,180,176-178,232,237,239,244,248

---

References Cited [Referenced By]

---

U.S. Patent Documents

	5086305		February 1992		Terasawa
	5252993		October 1993		Tomii et al.
	5260724		November 1993		Tomii et al.
	5373936		December 1994		Kawai et al.
	5436981		July 1995		Ishikawa
	5696842		December 1997		Shirasawa et al.
	5742704		April 1998		Suzuki et al.
	5774579		June 1998		Wang et al.
	5835109		November 1998		Uchida
	5917514		June 1999		Higuma et al.
	5975676		November 1999		Saijo
	6084984		July 2000		Ishikawa
	6547368		April 2003		Silverbrook
	6549657		April 2003		Ohta et al.

Foreign Patent Documents

	610 959		Aug., 1994		EP
	0 450 287		Sep., 1996		EP
	04169238		Jun., 1992		JP
	05330041		Dec., 1993		JP
	10305583		Nov., 1998		JP
	WO 00/27640		May., 2000		WO

Primary Examiner: Rogers; Scott A.

---

Parent Case Text

---

The present application is a continuation of U.S. application Ser. No. 10/402,217 filed on Mar. 31, 2003, now issued as U.S. Pat. No. 6,857,726, which is a continuation of U.S. application Ser. No. 09/436,872 filed on Nov. 9, 1999 (now abandoned).

---

Claims

---

I claim:

1. A method for processing print data corresponding to a page layout by means of a computational device, the method comprising the steps of: processing the print data to generate a set of continuous-tone data and a set of bi-level text and black graphics data; and applying data compression to the set of continuous-tone data and the set of bi-level text and black graphics data to produce compressed page data corresponding to the page layout; and transferring data corresponding to regions of text and black graphics obscured by regions of continuous-tone of the page layout from the set of continuous-tone data to the set of bi-level text and black graphics data.

2. A method according to claim 1, wherein the step of processing the print data includes: producing a first buffer of data corresponding to continuous-tone regions of the page layout; and producing a second buffer of data corresponding to text and black graphics regions of the page layout.

3. A method according to claim 1, wherein the step of applying data compression includes the application of lossy data compression to the set of continuous-tone data.

4. A method according to claim 1, wherein the step of applying data compression includes the application of lossless data compression to the text and black graphics data.

5. A printer driver software product for execution by a computer coupled to a printer in use, the driver software product including: instructions to generate a set of continuous-tone data and a set of bi-level text and black graphics data from print data corresponding to a page layout; data compression instructions to compress the set of continuous-tone data and the set of bi-level text and black graphics data to produce compressed page data corresponding to the page layout; and instructions to transfer data corresponding to regions of text and black graphics obscured by regions of continuous-tone of the page layout from the set of continuous-tone data to the set of bi-level text and black graphics data.

6. A printer driver software product according to claim 5, including: instructions to produce a first buffer of data corresponding to continuous-tone regions of the page layout; and instructions to produce a second buffer of data corresponding to text and black graphics regions of the page layout.

7. A printer driver software product according to claim 5, wherein the data compression instructions include instructions to apply lossy data compression to the set of continuous-tone data.

8. A printer driver software product according to claim 5, wherein the data compression instructions include instructions to apply lossless data compression to the set of bi-level text and black graphics data.

---

Description

---

TECHNICAL FIELD

This invention concerns a printhead capping mechanism for preventing evaporation of ink from a printhead when it is not in use. The invention has utility, for instance, in a color printer which uses a drop-on-demand inkjet printhead.

BACKGROUND OF THE INVENTION

When not in use, a drop-on-demand printhead typically remains filled with ink, and so must be capped to prevent evaporation of ink through the nozzles. Ink evaporation can lead to gradual deposition of ink components which can impair nozzle operation.

SUMMARY OF THE INVENTION

The invention is a printhead capping mechanism for preventing evaporation of ink from a printhead. The mechanism includes a printhead cap and an actuating structure attached to said cap to selectively move said cap between an engaged position to press against the printhead, and a disengaged position spaced away from the printhead. The actuating structure includes a slip member to engage with a drive wheel in a printer in which the printhead is mounted, said engagement extending through at least part of a revolution of the drive wheel, such that rotation of said drive wheel in a first direction causes movement of said cap from said engaged position to said disengaged position, and that rotation of said drive wheel in a second direction causes movement of said cap from said disengaged position to said engaged position.

In use, the mechanism will usually be mounted in a printer adjacent the printhead. The cap may involve one or more capping moldings provided to ensure that all the nozzles of the printhead can be capped. The capping molding may consist of a capping plate which holds an elastomeric seal and sponge. The elastomeric seal, or seals, are shaped and sized to seal against the face of the printhead when the mechanism is engaged. Similarly, the sponges are sized and positioned to catch any drops of ink when the mechanism is engaged. The actuating structure will typically cooperate with the mechanism of the printer in which the printhead is mounted to ensure that it is operated at appropriate times to move the capping molding between the engaged and disengaged positions.

When the printhead is not in use, the actuating structure is operated to move the capping molding to the engaged position where it is held against the face of the printhead where the elastomeric seal conforms to the face of the printhead and creates an airtight seal around the printhead. The sponge is used to catch drops ejected from nozzles in the printhead during the printhead cleaning cycle.

When the printhead is in use, the actuating structure is operated to move the capping molding away from the printhead assembly where it is held out of the paper path of the printer.

The mechanism may conveniently operate by pivoting between the engaged and disengaged positions. To achieve this the capping moulding may be connected along the length of a rotatable rod, but spaced laterally away (or offset) from the rod. In this case rotation of the rod about its axis will cause movement between the engaged and disengaged positions.

The slip member may be mounted at the end of the rod to engage with a drive wheel in the printer. The drive wheel may be coupled to the paper transport motor of the printer so that when printing is occurring the rod is driven in the uncapping direction. Once the slip member rotates to the uncapping slip point, the slip member and the capping molding stop rotating. When printing is complete, the drive wheel is reversed and driven in the capping direction. Once the slip member rotates to the capping slip point, the slip member and the capping molding stop rotating, and holds the capping plate in place against the face of the printhead assembly.

A resilient member may be used to assist in holding the capping plate in place against the face of the printhead assembly. Resilience has been found to be conveniently included in the connection between the capping plate and the rod. This need not be a continuous connection, and a series of flexible arms have been found to serve well, both as an adequate connection and a suitably resilient member. In fact, in some embodiments where plastics materials have been employed to fabricate the capping plate and rod, a continuous connecting web has been found to be difficult to make sufficiently flexible.

In another aspect the invention is a printhead assembly including a printhead and the printhead capping mechanism.

In a further aspect the invention is a printer including the printhead capping mechanism, where a drive wheel of the paper transport system of the printer operates the actuating structure of the mechanism.

BRIEF DESCRIPTION OF THE DRAWINGS

An example of a printer embodying the invention will now be described with reference to the accompanying drawings, in which:

FIG. 1 is a table which illustrates the sustained printing rate achievable with double-buffering in the printer.

FIG. 2 is a flowchart showing the conceptual data flow from application to printed page.

FIG. 3 is a pictorial view of the iPrint printer in its closed configuration.

FIG. 4 is a pictorial view of the iPrint printer in its open configuration.

FIG. 5 is a cutaway diagram showing the paper path through the printer.

FIG. 6 is a pictorial cutaway view of a Memjet printhead cartridge and printhead capping mechanism.

FIG. 7 is a sectional view of the Memjet printhead cartridge and printhead capping mechanism of FIG. 6.

FIG. 8 is a pictorial view of the printer controller.

FIG. 9 is an example of coding a simple black and white image.

FIG. 10 is a schematic diagram of a pod of ten printing nozzles numbered in firing order.

FIG. 11 is a schematic diagram of the same pod of ten printing nozzles numbered in load order.

FIG. 12 is a schematic diagram of a chromapod.

FIG. 13 is a schematic diagram of a podgroup of five chromapods.

FIG. 14 is a schematic diagram of a phasegroup of two podgroups.

FIG. 15 is a schematic diagram showing the relationship between Segments, Firegroups, Phasegroups, Podgroups and Chromapods.

FIG. 16 is a phase diagram of the AEnable and BEnable lines during a typical Print Cycle.

FIG. 17 is a diagram of the Printer controller architecture.

FIG. 18 is a flowchart summarizing the page expansion and printing data flow.

FIG. 19 is a block diagram of the EDRL expander unit.

FIG. 20 is a block diagram of the EDRL stream decoder.

FIG. 21 is a block diagram of the Runlength Decoder.

FIG. 22 is a block diagram of the Runlength Encoder.

FIG. 23 is a block diagram of the JPEG decoder.

FIG. 24 is a block diagram of the Halftoner/Compositor unit.

FIG. 25 is a series of page lines that show the relationships between page widths and margins.

FIG. 26 is a block diagram of a Multi-threshold dither.

FIG. 27 is a block diagram of the logic of the Triple-threshold unit.

FIG. 28 is a block diagram of the internal structure of the Printhead Interface.

FIG. 29 is a diagram of the conceptual overview of double buffering during print lines N and N+1.

FIG. 30 is a block diagram of the structure of the LLFU.

FIG. 31 is a diagram of the conceptual structure of a Buffer.

FIG. 32 is a diagram of the logical structure of a Buffer.

FIG. 33 is a block diagram of the generation of AEnable and BEnable Pulse Widths.

FIG. 34 is a diagram of the Dot Count logic.

FIG. 35 is a block diagram of the speaker interface.

FIG. 36 is a diagram of a two-layer page buffer.

FIG. 37 is a series of diagrams showing the compositing of a black object onto a white image.

FIG. 38 is a series of diagrams showing the compositing of a contone object onto a white image.

FIG. 39 is a series of diagrams showing the compositing of a black object onto an image containing a contone object.

FIG. 40 is a series of diagrams showing the compositing of an opaque contone object onto an image containing a black object.

FIG. 41 is a series of diagrams showing the compositing of a transparent contone object onto an image containing a black object.

FIG. 42 is a block diagram of the Windows 9x/NT printing system with printer driver components.

DESCRIPTION OF PREFERRED AND OTHER EMBODIMENTS

1 Introduction

The invention will be described with reference to a high-performance color printer which combines photographic-quality image reproduction with magazine-quality text reproduction. The printer utilizes an 8'' page-width drop-on-demand microelectromechanical inkjet ("Memjet") printhead which produces 1600 dots per inch (dpi) bi-level CMYK (Cyan, Magenta, Yellow, blacK). It prints 30 full-color A4 or Letter pages per minute, and is intended as an entry-level desktop printer. The printer has been designated as iPrint and will be referred to by that name in the following description.

1.1 Operational Overview

iPrint reproduces black text and graphics directly using bi-level black, and continuous-tone (contone) images and graphics using dithered bi-level CMYK. For practical purposes, iPrint supports a black resolution of 800 dpi, and a contone resolution of 267 pixels per inch (ppi).

iPrint is, in use, attached to a workstation or personal computer (PC) via a relatively low-speed (1.5 MBytes/s) universal serial bus (USB) connection [14]. iPrint relies on the PC to render each page to the level of contone pixels and black dots. The PC compresses each rendered page to less than 3 MB for sub-two-second delivery to the printer. iPrint decompresses and prints the page line by line at the speed of the Memjet printhead. iPrint contains sufficient buffer memory for two compressed pages (6 MB), allowing it to print one page while receiving the next, but does not contain sufficient buffer memory for even a single uncompressed page (119 MB).

1.2 Page Width

The standard Memjet nozzle layout has a half-inch unit cell, and so can be trivially adapted to page widths which are multiples of half an inch. Arbitrary page widths can be achieved with custom nozzle layouts, in markets which justify such specialisation. The initial Memjet building block is a widely useful four-inch printhead which makes efficient use of a six-inch silicon wafer. The iPrint design therefore assumes an eight-inch Memjet printhead, made up of two four-inch printheads joined together. The use of a wider printhead to achieve full bleed on A4/Letter pages only affects a few aspects of the iPrint design--specifically the exact mechanical design, and the logic of the printhead interface.

2 Memjet-Based Printing

A Memjet printhead produces 1600 dpi bi-level CMYK. On low-diffusion paper, each ejected drop forms an almost perfectly circular 22.5 micron diameter dot. Dots are easily produced in isolation, allowing dispersed-dot dithering to be exploited to its fullest. Since the Memjet printhead is page-width and operates with a constant paper velocity, the four color planes are printed in perfect registration, allowing ideal dot-on-dot printing. Since there is consequently no spatial interaction between color planes, the same dither matrix is used for each color plane.

A page layout may contain a mixture of images, graphics and text. Continuous-tone (contone) images and graphics are reproduced using a stochastic dispersed-dot dither. Unlike a clustered-dot (or amplitude-modulated) dither, a dispersed-dot (or frequency-modulated) dither reproduces high spatial frequencies (i.e. image detail) almost to the limits of the dot resolution, while simultaneously reproducing lower spatial frequencies to their full color depth. A stochastic dither matrix is carefully designed to be free of objectionable low-frequency patterns when tiled across the image. As such its size typically exceeds the minimum size required to support a number of intensity levels (i.e. 16.times.16.times.8 bits for 257 intensity levels). iPrint uses a dither volume of size 64.times.64.times.3.times.8 bits. The volume provides an extra degree of freedom during the design of the dither by allowing a dot to change states multiple times through the intensity range (rather than just once as in a conventional dither matrix).

Human contrast sensitivity peaks at a spatial frequency of about 3 cycles per degree of visual field and then falls off logarithmically, decreasing by a factor of 100 and becoming difficult to measure beyond about 40 cycles per degree [2]. At a normal viewing distance of between 400 mm and 250 mm, this translates roughly to 150 250 cycles per inch (cpi) on the printed page, or 300 500 samples per inch according to Nyquist's theorem. Taking into account the fact that color sensitivity is less acute than grayscale sensitivity, contone resolution beyond about 400 pixels per inch (ppi) is therefore of limited utility, and in fact contributes slightly to color error through the dither.

Black text and graphics are reproduced directly using bi-level black dots, and are therefore not antialiased (i.e. low-pass filtered) before being printed. Text is therefore supersampled beyond the perceptual limits discussed above, to produce smooth edges when spatially integrated. Text resolution up to about 1200 dpi continues to contribute to perceived text sharpness (assuming low-diffusion paper, of course).

3.1 Constraints

USB (Universal Serial Bus) is the standard low-speed peripheral connection on new PCs [4]. The standard high-speed peripheral connection, IEEE 1394, is recommended but unfortunately still optional in the PC 99 specification [5], and so may not be in widespread use when iPrint is first launched. iPrint therefore connects to a personal computer (PC) or workstation via USB, and the speed of the USB connection therefore imposes the most significant constraint on the architecture of the iPrint system. At a sustained printing rate of 30 pages/minute, USB at 1.5 MByte/s imposes an average limit of 3 MB/page. Since the act of interrupting a Memjet-based printer during the printing of a page produces a visible discontinuity, it is advantageous for the printer to receive the entire page before commencing printing, to eliminate the possibility of buffer underrun. Since the printer can contain only limited buffer memory, i.e. two pages' worth or 6 MB, then the 3 MB/page limit must be considered absolute.

FIG. 1 illustrates the sustained printing rate achievable with double-buffering in the printer. The first stage 1 requires the first page to be rendered in the PC, and this takes up to two seconds. During the second stage 2 the next page is rendered and the first page is transferred to the printer, again this takes up to two seconds. In the third stage 3 the first page is printed, the second page is transferred and a third page is rendered, this takes two seconds. As a result it takes up to six seconds for the first page to be printed and thereafter a page can be printed every two seconds.

Other desktop connection options provide similar bandwidth to USB, and so impose similar constraints on the architecture. These include the parallel port at 2 MB/s, and 10 Base-T Ethernet at around 1 MB/s

3.2 Page Rendering and Compression

Page rendering (or rasterization) can be split between the PC and printer in various ways. Some printers support a full page description language (PDL) such as Postscript, and contain correspondingly sophisticated renderers. Other printers provide special support only for rendering text, to achieve high text resolution. This usually includes support for built-in or downloadable fonts. In each case the use of an embedded renderer reduces the rendering burden on the PC and reduces the amount of data transmitted from the PC to the printer. However, this comes at a price. These printers are more complex than they might be, and are often unable to provide full support for the graphics system of the PC, through which application programs construct, render and print pages. They often fail to exploit the high performance of current PCs, and are unable to leverage projected exponential growth in PC performance.

iPrint relies on the PC 4 to render pages, i.e. contone images and graphics to the pixel level, and black text and graphics to the dot level. iPrint 5 contains only a simple rendering engine which dithers the contone data and combines the results with any foreground bi-level black text and graphics. This strategy keeps the printer simple, and independent of any page description language or graphics system. It fully exploits the high performance of current PCs. The downside of this strategy is the potentially large amount of data which must be transmitted from the PC to the printer. We consequently use compression to reduce this data to the 3 MB/page required to allow a sustained printing rate of 30 pages/minute.

FIG. 2 is a flowchart illustrating the conceptual data flow from an application 6 to a printed page 7.

An 8'' by 11.7'' A4 page has a bi-level CMYK pagesize of 114.3 MBytes at 1600 dpi, and a contone CMYK pagesize of 32.1 MB at 300 ppi.

In the printer driver 8, we use JPEG compression 9 to compress the contone data. Although JPEG is inherently lossy, for compression ratios of 10:1 or less the loss is usually negligible [16]. To obtain an integral contone to bi-level ratio, and to provide some compression leeway, we choose a contone resolution of 267 ppi. This yields a contone CMYK pagesize of 25.5 MB, a corresponding compression ratio of 8.5:1 to fit within the 3 MB/page limit, and a contone to bi-level ratio of 1:6 in each dimension.

A full page of black text (and/or graphics) rasterized at printer resolution (1600 dpi) yields a bi-level image of 28.6 MB. Since rasterizing text at 1600 dpi places a heavy burden on the PC for a small gain, we choose to rasterize text at a fully acceptable 800 dpi. This yields a bi-level image of 7.1 MB, requiring a lossless compression ratio of less than 2.5:1 to fit within the 3 MB/page limit. We achieve this with a two-dimensional compression scheme adapted from Group 4 Facsimile, all indicated generally at 10.

As long as the image and text regions of a page are non-overlapping, any combination of the two fits within the 3 MB limit. If text lies on top of a background image, then the worst case is a compressed pagesize approaching 6 MB (depending on the actual text compression ratio). This fits within the printer's page buffer memory, but prevents double-buffering of pages in the printer, thereby reducing the printer's page rate by two-thirds, i.e. to 10 pages/minute.

3.3 Page Expansion and Printing

As described above, the PC renders contone images and graphics to the pixel level, and black text and graphics to the dot level. These are compressed 11 by different means and transmitted together to the printer.

The printer contains two 3 MB page buffers--one 12 for the page being received from the PC, and one 13 for the page being printed. The printer expands the compressed page as it is being printed. This expansion consists of decompressing the 267 ppi contone CMYK image data 14, halftoning the resulting contone pixels to 1600 dpi bi-level CMYK dots 15, decompressing the 800 dpi bi-level black text data 16, and compositing the resulting bi-level black text dots over the corresponding bi-level CMYK image dots 17.

The conceptual data flow from the application to the printed page is illustrated in FIG. 2.

4 Printer Hardware

Because of the simplicity of the page width Memjet printhead, iPrint is very compact. It measures just 270 mm wide.times.85 mm deep.times.77 mm high when closed. FIG. 3 is a pictorial view of the iPrint 21 when closed.

The cover 22 opens to form part of the paper tray, as shown in FIG. 4. A second part 23 is hinged within cover 22 and opens to extend the paper tray. A paper exit tray 24 is slideably extendable from the front of the printer.

The front panel 25, revealed when cover 22 is opened, contains the user interface--the power button 26 and power indicator LED 27, the paper feed button 28, and the out-of-paper 29 and ink low 30 LEDs.

4.1 Paper Path

iPrint uses a standard paper transport mechanism. The paper path 50 is illustrated in FIG. 5, in which a single stepper motor 51 drives both the sheet feed roller 52 and the paper transport. When running in the forward direction the stepper motor drives the paper drive roller 53 and the pinch wheels 54 at the start and end of the active paper path, respectively. When reversed, the stepper motor drives the sheet feed roller 52 which grabs the topmost sheet from the sheet feeder and transports it the short distance to the paper drive roller 53 where it is detected by the mechanical media sensor 55.

The paper centering sliders 56 ensure that the paper is centered. This ensures that a single centered media sensor detects the sheet, and also ensures that sheets wider than the printhead are printed with balanced margins.

4.1.1 Memjet Printhead

The replaceable Memjet printhead cartridge 60 is also shown in FIG. 5. This represents one of the four possible ways to deploy the printhead in conjunction with the ink cartridge in a product such as iPrint: permanent printhead, replaceable ink cartridge (as shown here) separate replaceable printhead and ink cartridges refillable combined printhead and ink cartridge disposable combined printhead and ink cartridge

Under the printhead cartridge 60 is a printhead assembly 61 and a printhead capping mechanism 62, illustrated in pictorial cut away view in FIG. 6 and in section in FIG. 7. When not in use, the Memjet printhead 63 remains filled with ink, and so must be capped to prevent evaporation of ink through the nozzles. Ink evaporation can lead to gradual deposition of ink components which can impair nozzle operation.

iPrint includes a mechanical page width capping mechanism 62 which consists of a pivoting capping molding 64 with an elastomeric seal 65 and sponge 66. When the printhead is not in use, the capping molding 64 is held by a spring against the face of the printhead assembly 61, and the elastomeric seal 65 conforms to the face of the printhead assembly and creates an airtight seal around the printhead 63. The sponge 66 is used to catch drops ejected during the printhead cleaning cycle. When the printhead is in use, the capping molding 64 is held away from the printhead assembly 61 and out of the paper path.

The capping molding 64 is offset by a set of flexible arms 68 from a rod 69. The capping molding 64 and arms 68 pivot with the rod 69 about its axis. A slip member 70 is mounted at the end of rod 69. This slip member 70 is affixed to the rod 69 such that if the slip member 70 is caused to pivot about axis of rod 69, then rod 69 also pivots with slip member 70. The slip member 70 makes contact with a drive wheel 71. When printing is occurring, the drive wheel 71 is coupled to the paper transport motor and is driven in the uncapping direction 72. Frictional contact between the surface of drive wheel 71 and slip member 70 causes the slip member 70 and rod 69 to rotate about the longitudinal axis of rod 69 to thereby swing the capping molding 64 away from the printhead. Once the slip member rotates to the uncapping slip point 73, the slip member and the capping molding stop rotating because the slip member 70 slips against the surface of drive wheel 71. When printing is complete, the drive wheel is reversed and driven in the capping direction 74. Once the slip member rotates to the capping slip point 75, the slip member and the capping molding stop rotating by virtue of the fact that slip commences between the slip member 70 and the drive wheel 71, and the capping spring holds the capping plate in place against the face of the printhead assembly. During pivotal movement of the slip member 70 between the capping and uncapping slip points, there is static frictional contact between the slip member 70 and drive wheel 71 sufficient to effect pivotal movement of the slip member 70 about the longitudinal axis of shaft 69 to thereby effect the described movement of the capping molding 64. The flexible arms 68 help the capping plate 67 conform to the face of the printhead assembly 61.

4.2 Printer Controller

The printer controller 80 is illustrated in FIG. 8, and consists of a small PCB 81 with only a few components--a 64 Mbit RDRAM 82, the iPrint Central Processor (ICP) chip 83, a speaker 84 for notifying the user of error conditions, a QA chip 85, an external 3V DC power connection 86, an external USB connection 87, a connection to the paper transport stepper motor 88, and the flex PCB 89 which connects to the media sensor 55, LEDs 7, 9 and 10, buttons 6 and 8, and a link 90 the printhead 63.

4.3 Ink Cartridge and Ink Path

There are two versions of the ink cartridge--one large, one small. Both fit in the same ink cartridge slot at the back of the iPrint unit.

5 Printer Control Protocol

This section describes the printer control protocol used between a host and iPrint. It includes control and status handling as well as the actual page description.

5.1 Control and Status

The USB device class definition for printers [15] provides for emulation of both unidirectional and bidirectional IEEE 1284 parallel ports [3]. At its most basic level, this allows the host to determine printer capabilities (via GET_DEVICE_ID), obtain printer status (via GET_PORT_STATUS), and reset the printer (via SOFT_RESET). Centronics/IEEE 1284 printer status fields are described in Table 1 below.

TABLE-US-00001 TABLE 1 Centronics/IEEE 1284 printer status field description Select The printer is selected and available for data transfer. Paper A paper empty condition exists in the printer. Empty Fault A fault condition exists in the printer (includes Paper Empty and not Select).

Personal computer printing subsystems typically provide some level of IEEE 1284 support. Compatibility with IEEE 1284 in a printer therefore simplifies the development of the corresponding printer driver. The USB device class definition for printers seeks to leverage this same compatibility.

iPrint supports no control protocol beyond the USB device class definition for printers. Note that, if a higher-level control protocol were defined, then conditions such as out-of-ink could also be reported to the user (rather than just via the printer's out-of-ink LED).

iPrint receives page descriptions as raw transfers, i.e. not encapsulated in any higher-level control protocol.

5.2 Page Description

iPrint reproduces black at full dot resolution (1600 dpi), but reproduces contone color at a somewhat lower resolution using halftoning. The page description is therefore divided into a black layer and a contone layer. The black layer is defined to composite over the contone layer.

The black layer consists of a bitmap containing a 1-bit opacity for each pixel. This black layer matte has a resolution which is an integer factor of the printer's dot resolution. The highest supported resolution is 1600 dpi, i.e. the printer's full dot resolution.

The contone layer consists of a bitmap containing a 32-bit CMYK color for each pixel. This contone image has a resolution which is an integer factor of the printer's dot resolution. The highest supported resolution is 267 ppi, i.e. one-sixth the printer's dot resolution.

The contone resolution is also typically an integer factor of the black resolution, to simplify 25 calculations in the printer driver. This is not a requirement, however.

The black layer and the contone layer are both in compressed form for efficient transmission over the low-speed USB connection to the printer.

5.2.1 Page Structure

iPrint has a printable page area which is determined by the width of its printhead, the characteristics of its paper path, and the size of the currently selected print medium.

The printable page area has a maximum width of 8''. If the physical page width exceeds 8'', then symmetric left and right margins are implicitly created. If the physical page width is less than 8'', then the printable page width is reduced accordingly. The printable page area has no maximum length. It is simply the physical page length, less the top and bottom margins imposed by the characteristics of the paper path.

The target page size is constrained by the printable page area, less the explicit (target) left and top margins specified in the page description.

In theory iPrint does not impose a top or bottom margin--i.e. it allows full bleed in the vertical direction. In practice, however, since iPrint is not designed as a full-bleed A4/Letter printer because it uses an 8'' printhead, an artificial top and bottom margin is imposed to avoid having to include a sponge large enough to cope with regular off-edge printing.

5.2.2 Page Description Format

TABLE-US-00002 TABLE 2 Page description format Field format description Signature 16-bit integer Page description format signature. Version 16-bit integer Page description format version number. structure size 16-bit integer Size of fixed-size part of page description. target resolution 16-bit integer Resolution of target page. (dpi) This is always 1600 for iPrint. target page width 16-bit integer Width of target page, in dots. target page height 16-bit integer Height of target page, in dots. target left margin 16-bit integer Width of target left margin, in dots. target top margin 16-bit integer Height of target top margin, in dots. black scale factor 16-bit integer Scale factor from black resolution to target resolution (must be 2 or greater). black page width 16-bit integer Width of black page, in black pixels. black page height 16-bit integer Height of black page, in black pixels. black page data size 32-bit integer Size of black page data, in bytes. contone scale factor 16-bit integer Scale factor from contone resolution to target resolution (must be 6 or greater). contone page width 16-bit integer Width of contone page, in contone pixels. contone page height 16-bit integer Height of contone page, in contone pixels. contone page data 32-bit integer Size of contone page data, size in bytes. black page data EDRL Compressed bi-level black bytestream page data. contone page data JPEG bytestream Compressed contone CMYK page data.

Apart from being implicitly defined in relation to the printable page area, each page description is complete and self-contained. There is no data transmitted to the printer separately from the page description to which the page description refers.

The page description contains a signature and version which allow the printer to identify the page description format. If the signature and/or version are missing or incompatible with the printer, then the printer can reject the page.

The page description defines the resolution and size of the target page. The black and contone layers are clipped to the target page if necessary. This happens whenever the black or contone scale factors are not factors of the target page width or height.

The target left and top margins define the positioning of the target page within the printable page area.

The black layer parameters define the pixel size of the black layer, its integer scale factor to the target resolution, and the size of its compressed page data. The variable-size black page data follows the fixed-size parts of the page description.

The contone layer parameters define the pixel size of the contone layer, its integer scale factor to the target resolution, and the size of its compressed page data. The variable-size contone page data follows the variable-size black page data.

All integers in the page description are stored in big-endian byte order.

The variable-size black page data and the variable-size contone page data are aligned to 8-byte boundaries. The size of the required padding is included in the size of the fixed-size part of the page description structure and the variable-size black data.

The entire page description has a target size of less than 3 MB, and a maximum size of 6 MB, in accordance with page buffer memory in the printer.

The following sections describe the format of the compressed black layer and the compressed contone layer.

5.2.3 Bi-level Black Layer Compression

5.2.3.1 Group 3 and 4 Facsimile Compression

The Group 3 Facsimile compression algorithm [1] losslessly compresses bi-level data for transmission over slow and noisy telephone lines. The bi-level data represents scanned black text and graphics on a white background, and the algorithm is tuned for this class of images (it is explicitly not tuned, for example, for halftoned bi-level images). The 1D Group 3 algorithm runlength-encodes each scanline and then Huffman-encodes the resulting runlengths. Runlengths in the range 0 to 63 are coded with terminating codes. Runlengths in the range 64 to 2623 are coded with make-up codes, each representing a multiple of 64, followed by a terminating code. Runlengths exceeding 2623 are coded with multiple make-up codes followed by a terminating code. The Huffman tables are fixed, but are separately tuned for black and white runs (except for make-up codes above 1728, which are common). When possible, the 2D Group 3 algorithm encodes a scanline as a set of short edge deltas (0, .+-.1, .+-.2, .+-.3) with reference to the previous scanline. The delta are entropy-encoded (so that the zero delta symbol is only one bit long etc.) Edges within a 2D-encoded line which can't be delta-encoded are runlength-encoded, and are identified by a prefix. 1D- and 2D-encoded lines are marked differently. 1D-encoded lines are generated at regular intervals, whether actually required or not, to ensure that the decoder can recover from line noise with minimal image degradation. 2D Group 3 achieves compression ratios of up to 6:1 [13].

The Group 4 Facsimile algorithm [1] losslessly compresses bi-level data for transmission over error-free communications lines (i.e. the lines are truly error-free, or error-correction is done at a lower protocol level). The Group 4 algorithm is based on the 2D Group 3 algorithm, with the essential modification that since transmission is assumed to be error-free, 1D-encoded lines are no longer generated at regular intervals as an aid to error-recovery. Group 4 achieves compression ratios ranging from 20:1 to 60:1 for the CCITT set of test images [13].

The design goals and performance of the Group 4 compression algorithm qualify it as a compression algorithm for the bi-level black layer. However, its Huffman tables are tuned to a lower scanning resolution (100 400 dpi), and it encodes runlengths exceeding 2623 awkwardly. At 800 dpi, our maximum runlength is currently 6400. Although a Group 4 decoder core might be available for use in the printer controller chip (Section 7), it might not handle runlengths exceeding those normally encountered in 400 dpi facsimile applications, and so would require modification.

Since most of the benefit of Group 4 comes from the delta-encoding, a simpler algorithm based on delta-encoding alone is likely to meet our requirements. This approach is described in detail below.

5.2.3.2 Bi-level Edge Delta and Runlength (EDRL) Compression Format

The edge delta and runlength (EDRL) compression format is based loosely on the Group 4 compression format and its precursors [1][17].

EDRL uses three kinds of symbols, appropriately entropy-coded. These are create edge, kill edge, and edge delta. Each line is coded with reference to its predecessor. The predecessor of the first line is defined to a line of white. Each line is defined to start off white. If a line actually starts of black (the less likely situation), then it must define a black edge at offset zero. Each line must define an edge at its left-hand end, i.e. at offset page width.

An edge can be coded with reference to an edge in the previous line if there is an edge within the maximum delta range with the same sense (white-to-black or black-to-white). This uses one of the edge delta codes. The shorter and likelier deltas have the shorter codes. The maximum delta range (.+-.2) is chosen to match the distribution of deltas for typical glyph edges. This distribution is mostly independent of point size. A typical example is given in Table 3.

TABLE-US-00003 TABLE 3 Edge delta distribution for 10 point Times at 800 dpi |delta| probability 0 65% 1 23% 2 7% .gtoreq.3 5%

An edge can also be coded using the length of the run from the previous edge in the same line. This uses one of the create edge codes for short (7-bit) and long (13-bit) runlengths. For simplicity, and unlike Group 4, runlengths are not entropy-coded. In order to keep edge deltas implicitly synchronised with edges in the previous line, each unused edge in the previous line is `killed` when passed in the current line. This uses the kill edge code. The end-of-page code signals the end of the page to the decoder.

Note that 7-bit and 13-bit runlengths are specifically chosen to support 800 dpi A4/Letter pages. Longer runlengths could be supported without significant impact on compression performance. For example, if supporting 1600 dpi compression, the runlengths should be at least 8-bit and 14-bit respectively. A general-purpose choice might be 8-bit and 16-bit, thus supporting up to 40'' wide 1600 dpi pages.

The full set of codes is defined in Table 4. Note that there is no end-of-line code. The decoder uses the page width to detect the end of the line. The lengths of the codes are ordered by the relative probabilities of the codes' occurrence.

TABLE-US-00004 TABLE 4 EDRL codewords code encoding suffix description .DELTA.0 1 -- don't move corresponding edge .DELTA. + 1 010 -- move corresponding edge +1 .DELTA. - 1 011 -- move corresponding edge -1 .DELTA. + 2 00010 -- move corresponding edge +2 .DELTA. - 2 00011 -- move corresponding edge -2 kill edge 0010 -- kill corresponding edge create 0011 7-bit RL create edge from short near edge runlength (RL) create 00001 13-bit RL create edge from long far edge runlength (RL) end-of-page 000001 -- end-of-page marker (EOP)

FIG. 9 shows an example of coding a simple black and white image 90. The image is arranged as lines 91 of pixels 92. The first line 91 is assumed to be white and, since it is, is coded as .DELTA.0. Note that the common situation of an all-white line following another all-white line is coded using a single bit (.DELTA.0), and an all-black line following another all-black line is coded using two bits (.DELTA.0, .DELTA.0). Where an edge occurs in a line, such as the fourth line 93, the create code is used to define the edges. In the next line 94, the .DELTA.-1 and .DELTA.+1 codes are used to move the edges. In the next line 95, it is more convenient to create a new edge and kill the old edge rather than move it.

EDRL Encoding Example

Note that the foregoing describes the compression format, not the compression algorithm per se. A variety of equivalent encodings can be produced for the same image, some more compact than others. For example, a pure runlength encoding conforms to the compression format. The goal of the compression algorithm is to discover a good, if not the best, encoding for a given image. The following is a simple algorithm for producing the EDRL encoding of a line with reference to its predecessor.

TABLE-US-00005 #define SHORT_RUN_PRECISION7 // precision of short run #define LONG_RUN_PRECISION13 // precision of long run EDRL_CompressLine ( Byte prevLine[ ], // previous (reference) bi-level line Byte currLine[ ], // current (coding) bi-level line int lineLen, // line length BITSTREAM s // output (compressed) bitstream ) int prevEdge = 0 // current edge offset in previous line int currEdge = 0 // current edge offset in current line int codedEdge = currEdge // most recent coded (output) edge int prevColor = 0 // current color in previous line (0 = white) int currColor = 0 // current color in current line int prevRun // current run in previous line int currRun // current run in current line bool bUpdatePrevEdge = true // force first edge update bool bUpdateCurrEdge = true // force first edge update while (codedEdge < lineLen) // possibly update current edge in previous line if (bUpdatePrevEdge) if (prevEdge < lineLen) prevRun = GetRun(prevLine, prevEdge, lineLen, prevColor) else prevRun = 0 prevEdge += prevRun prevColor = !prevColor bUpdatePrevEdge = false // possibly update current edge in current line if (bUpdateCurrEdge) if (currEdge < lineLen) currRun = GetRun(currLine, currEdge, lineLen, currColor) else currRun = 0 currEdge += currRun currColor = !currColor bUpdateCurrEdge = false // output delta whenever possible, i.e. when // edge senses match, and delta is small enough if (prevColor == currColor) delta = currEdge - prevEdge if (abs(delta) <= MAX_DELTA) PutCode(s, EDGE_DELTA0 + delta) codedEdge = currEdge bUpdatePrevEdge = true bUpdateCurrEdge = true continue // kill unmatched edge in previous line if (prevEdge <= currEdge) PutCode(s, KILL_EDGE) bUpdatePrevEdge = true // create unmatched edge in current line if (currEdge <= prevEdge) PutCode(s, CREATE_EDGE) if (currRun < 128) PutCode(s, CREATE_NEAR_EDGE) PutBits(currRun, SHORT_RUN_PRECISION) else PutCode(s, CREATE_FAR_EDGE) PutBits(currRun, LONG_RUN_PRECISION) codedEdge = currEdge bUpdateCurrEdge = true Note that the algorithm is blind to actual edge continuity between lines, and may in fact match the "wrong" edges between two lines. Happily the compression format has nothing to say about this, since it decodes correctly, and it is difficult for a "wrong" match to have a detrimental effect on the compression ratio.

For completeness the corresponding decompression algorithm is given below. It forms the core of the EDRL Expander unit in the printer controller chip (Section 7).

TABLE-US-00006 EDRL_DecompressLine ( BITSTREAM s, // input (compressed) bitstream Byte prevLine[ ], // previous (reference) bi-level line Byte currLine[ ], // current (coding) bi-level line int lineLen // line length ) int prevEdge = 0 // current edge offset in previous line int currEdge = 0 // current edge offset in current line int prevColor = 0 // current color in previous line (0 = white) int currColor = 0 // current color in current line while (currEdge < lineLen) code = GetCode(s) switch (code) case EDGE_DELTA_MINUS2: case EDGE_DELTA_MINUS1: case EDGE_DELTA_0: case EDGE_DELTA_PLUS1: case EDGE_DELTA_PLUS2: // create edge from delta int delta = code - EDGE_DELTA_0 int run = prevEdge + delta - currEdge FillBitRun(currLine, currEdge, currColor, run) currEdge += run currColor = !currColor prevEdge += GetRun(prevLine, prevEdge, lineLen, prevColor) prevColor = !prevColor case KILL_EDGE: // discard unused reference edge prevEdge += GetRun(prevLine, prevEdge, lineLen, prevColor) prevColor = !prevColor case CREATE_NEAR_EDGE: case CREATE_FAR_EDGE: // create edge explicitly int run if (code == CREATE_NEAR_EDGE) run = GetBits(s, SHORT_RUN_PRECISION) else run = GetBits(s, LONG_RUN_PRECISION) FillBitRun(currLine, currEdge, currColor, run) currColor = !currColor currEdge += run

5.2.3.3 EDRL Compression Performance

Table 5 shows the compression performance of Group 4 and EDRL on the CCITT test documents used to select the Group 4 algorithm. Each document represents a single page scanned at 400 dpi. Group 4's superior performance is due to its entropy-coded runlengths, tuned to 400 dpi features.

TABLE-US-00007 TABLE 5 Group 4 and EDRL compression performance on standard CCITTT documents at 400 dpi CCITT document Group 4 EDRL number compression ratio compression ratio 1 29.1 21.6 2 49.9 41.3 3 17.9 14.1 4 7.3 5.5 5 15.8 12.4 6 31.0 25.5 7 7.4 5.3 8 26.7 23.4

Magazine text is typically typeset in a typeface with serifs (such as Times) at a point size of 10. At this size an A4/Letter page holds up to 14,000 characters, though a typical magazine page holds only about 7,000 characters. Text is seldom typeset at a point size smaller than 5. At 800 dpi, text cannot be meaningfully rendered at a point size lower than 2 using a standard typeface. Table 6 illustrates the legibility of various point sizes.

TABLE-US-00008 TABLE 6 Text at different point sizes point size sample text (in Times) 8 The quick brown fox jumps over the lazy dog. 9 The quick brown fox jumps over the lazy dog. 10 The quick brown fox jumps over the lazy dog.

Table 7 shows Group 4 and EDRL compression performance on pages of text of varying point sizes, rendered at 800 dpi. Note that EDRL achieves the required compression ratio of 2.5 for an entire page of text typeset at a point size of 3. The distribution of characters on the test pages is based on English-language statistics [12].

TABLE-US-00009 TABLE 7 Group 4 and EDRL compression performance on text at 800 dpi Group 4 EDRL point characters/ compression compression size A4 page ratio ratio 2 340,000 2.3 1.7 3 170,000 3.2 2.5 4 86,000 4.7 3.8 5 59,000 5.5 4.9 6 41,000 6.5 6.1 7 28,000 7.7 7.4 8 21,000 9.1 9.0 9 17,000 10.2 10.4 10 14,000 10.9 11.3 11 12,000 11.5 12.4 12 8,900 13.5 14.8 13 8,200 13.5 15.0 14 7,000 14.6 16.6 15 5,800 16.1 18.5 20 3,400 19.8 23.9

For a point size of 9 or greater, EDRL slightly outperforms Group 4, simply because Group 4's runlength codes are tuned to 400 dpi.

These compression results bear out the observation that entropy-encoded runlengths contribute much less to compression than 2D encoding, unless the data is poorly correlated vertically, such as in the case of very small characters.

5.2.4 Contone Layer Compression

5.2.4.1 JPEG Compression

The JPEG compression algorithm [6] lossily compresses a contone image at a specified quality level. It introduces imperceptible image degradation at compression ratios below 5:1, and negligible image degradation at compression ratios below 10:1 [16].

JPEG typically first transforms the image into a color space which separates luminance and chrominance into separate color channels. This allows the chrominance channels to be subsampled without appreciable loss because of the human visual system's relatively greater sensitivity to luminance than chrominance. After this first step, each color channel is compressed separately.

The image is divided into 8.times.8 pixel blocks. Each block is then transformed into the frequency domain via discrete cosine transform (DCT). This transformation has the effect of concentrating image energy in relatively lower-frequency coefficients, which allows higher-frequency coefficients to be more crudely quantized. This quantization is the principal source of compression in JPEG. Further compression is achieved by ordering coefficients by frequency to maximise the likelihood of adjacent zero coefficients, and then runlength-encoding runs of zeroes. Finally, the runlengths and non-zero frequency coefficients are entropy coded. Decompression is the inverse process of compression.

5.2.4.2 CMYK Contone JPEG Compression Format

The CMYK contone layer is compressed to an interleaved color JPEG bytestream. The interleaving is required for space-efficient decompression in the printer, but may restrict the decoder to two sets of Huffman tables rather than four (i.e. one per color channel) [16]. If luminance and chrominance are separated, then the luminance channels can share one set of tables, and the chrominance channels the other set.

If luminance/chrominance separation is deemed necessary, either for the purposes of table sharing or for chrominance subsampling, then CMY is converted to YCrCb and Cr and Cb are duly subsampled. K is treated as a luminance channel and is not subsampled.

The JPEG bytestream is complete and self-contained. It contains all data required for decompression, including quantization and Huffman tables.

6 Memjet Printhead

An 8-inch Memjet printhead consists of two standard 4-inch Memjet printheads joined together side by side.

The two 4-inch printheads are wired up together in a specific way for use in iPrint. Since the wiring requires knowledge of the 4-inch printhead, an overview of the 4-inch printhead is presented here.

6.1 Composition of a 4-Inch Printhead

Each 4-inch printhead consists of 8 segments, each segment 1/2 an inch in length. Each of the segments prints bi-level cyan, magenta, yellow and black dots over a different part of the page to produce the final image.

Since the printhead prints dots at 1600 dpi, each dot is approximately 22.5 microns in diameter, and spaced 15.875 microns apart. Thus each half-inch segment prints 800 dots, with the 8 segments corresponding to the positions shown in Table 8.

TABLE-US-00010 TABLE 8 Final image dots addressed by each segment Printhead 1 Printhead 2 Segment First dot Last dot First dot Last dot 0 0 799 6,400 7,199 1 800 1,599 7,200 7,999 2 1,600 2,399 8,000 8,799 3 2,400 3,199 8,800 9,599 4 3,200 3,999 9,600 10,399 5 4,000 4,799 10,400 11,199 6 4,800 5,599 11,200 11,999 7 5,600 6,399 12,000 12,799

Although each segment produces 800 dots of the final image, each dot is represented by a combination of bi-level cyan, magenta, yellow and black ink. Because the printing is bi-level, the input image should be dithered or error-diffused for best results.

Each segment then contains 3,200 nozzles: 800 each of cyan, magenta, yellow and black. A four-inch printhead contains 8 such segments for a total of 25,600 nozzles.

6.1.1 Grouping of Nozzles Within a Segment

The nozzles within a single segment are grouped for reasons of physical stability as well as mininization of power consumption during printing. In terms of physical stability, a total of 10 nozzles share the same ink reservoir. In terms of power consumption, groupings are made to enable a low-speed and a high-speed printing mode.

The printhead supports two printing speeds to allow speed/power consumption trade-offs to be made in different product configurations.

In the low-speed printing mode, 128 nozzles are fired simultaneously from each 4-inch printhead. The fired nozzles should be maximally distant, so 16 nozzles are fired from each segment. To fire all 25,600 nozzles, 200 different sets of 128 nozzles must be fired.

In the high-speed printing mode, 256 nozzles are fired simultaneously from each 4-inch printhead. The fired nozzles should be maximally distant, so 32 nozzles are fired from each segment. To fire all 25,600 nozzles, 100 different sets of 256 nozzles must be fired.

The power consumption in the low-speed mode is half that of the high-speed mode. Note, however, that the energy consumed to print a page is the same in both cases.

6.1.1.1 Ten Nozzles Make a Pod

A single pod 100 consists of 10 nozzles 101 sharing a common ink reservoir. 5 nozzles are in one row, and 5 are in another. Each nozzle produces dots 22.5 microns in diameter spaced on a 15.875 micron grid. FIG. 10 shows the arrangement of a single pod 100, with the nozzles 101 numbered according to the order in which they must be fired.

Although the nozzles are fired in this order, the relationship of nozzles and physical placement of dots on the printed page is different. The nozzles from one row represent the even dots from one line on the page, and the nozzles on the other row represent the odd dots from the adjacent line on the page. FIG. 11 shows the same pod 100 with the nozzles