                                                                                       ChristopherJ.Payson
                                                                                      ChristopherJ.Cianciolo
                                                                                            Robert N Crouse
                                                                                         Catherine E Winsor


Hardware Accelerators for
Bitonal Image Processing
                  Electronic imaging systemns transfer viezus of real-world scenes or objects into
                  digital bits for storage, manipulation, and viewing. In the area of bitonal images,
                  a large market exists in docz~rnentmanagement, which coizsists of scanning vol-
                  umes of papers for storage and retrieval. Hozuevel; high scan densities produce
                  huge volz~mesof data, requiring compression and decoml~ressiontechniques topre-
                  serve system memnory and imnprove systmz throughput. These tech~ziques,as well as
                  general image processing algorithms, are conzpute-intensive and require high
                  memory bandwidth. To address the nzemory issues, and to achieve interactive
                  image display performancq Digital has designed a series of bitonal image hard-
                  ware accelerators. The intent was to create interactive media view stations, with
                  inzaging applications alongside other applications, In addition to achieuiilg rnem-
                  ory, performance, and versatility goals, the hclrdware accelerators have signifi-
                  cantly improvedjnal image legibility


Bitonal image technology, which can be viewed as              should come of age in the 1990s. Digital imaging
the electronic version of today's microfil~nmethod,           is already in use in many areas and new applica-
is experiencing a high rate of growth. However, the           tions are being created for both commercial and
electronic image data objects generatecl and manip-           scientific markets. The emergence of digital images
ulated in this technology are very large and require          as standard data types supported by the majority
intensive processing. In a generic system, these              of systems (like text and graphics of today) seems
requirements can result in poor image processing              assured. For a greater understanding of specific
performance or reduced application performance.               imaging applications, this section presents general
To address these needs, Digital has designed a series         imaging concepts and terms used throughout the
of imaging hardware accelerators for use in the doc-          paper.
ument management market.
   This paper provides a brief tutorial on electronic         Concepts and Terms
imaging. It begins with a general description of the          In its simplest form, imaging is the digital repre-
imaging data type and compares this type to the               sentation of real-world scenes or objects. Just as a
standard text and graphics data types. It continues           camera transfers a view of the real world onto a
with a discussion of specific issues in bitonal imag-         chemical film, an electronic imaging systenl trans-
ing, such as image data size, network transport               fers the same view into digital bits for storage,
method, rendering speed, and end-user legibility.             manipulation, and viewing. In this paper, the term
The paper then focuses on Digital's DECimage 1200             image refers to the digital bits and bytes that repre-
hardware accelerator for the VT1200 X window                  sent the real-world view.
terminal developed by the Video, Image and Print                The process of digitizing the view may be done
Systems Group. It concludes with future image                 through various methods, e.g., an image scanner
accelerator demands for the processing of multi-              or image camera. A scanner is the conceptual
media applications and continuous-tone images.                inverse of a normal printer. A printer accepts an
                                                              electronic stream of bits that describe how to
Introduction t o Imaging                                      place the ink on the paper to create the desired
Just as graphics technology blossomed in the 1980s,           picture. Conversely, optical sensors in the scanner
electronic imaging and its associatecl technologies           transfor~nlight intensity values reflected from a


Digilnl ~ & c ~ ? z ~ c L z ~ J o .u? ~No.
                              Vol.             FctlI 19'11
                                        ? ~4 ~ ~                                                                  9
Image Processing, Video Terminals, and Printer Technologies


sheet of paper and create a stream of electronic bits     media density. Scaling an image may be as simple as
to describe the picture. Similar sensors in the focal     replicating and dropping pixels, or it may involve
plane of a camera produce the other common digi-          Interpolation and other algorithms that take neigh-
tization method, the electronic image camera.             boring pixels into account. Generally, the more
   The format of a digitized image has many param-        complex scaling algorithms require more process-
eters. A pixel is the common name for a group of          ing power but yield higher-quality images, where
digitized image bits that all correspond to the sane      quality refers to how well the original scene is rep-
location in the image. This pixel contains informa-       resented in the resulting image.
tion about the intensity and color of the image at           Before an image can be displayed, its pixel values
one location, in a format that can be interpreted        often require conversion to account for the charac-
and transformed into a visible dot on a display           teristics of the display device. As a simple example,
device such as a printer or screen. The amount of        a color image cannot retain its color when output
information in the pixel classifies the image into       to a black-and-white video monitor or printer. In
one of three basic types.                                general, when a device can display fewer colors
                                                         than an image contains, the image pixel values must
  A bitonal image has only one bit in each pixel;
                                                         be quantized. Simple quantizing, or thresholding,
  the bit is either a one or a zero, representing one
                                                         can be used to reduce the number of image colors
  of two possible colors (usually black and white).
                                                         to the number of display colors, but can result in
  A gray-scale image Iias multiple bits in each pixel,   loss of image quality. Dithering is a more sophisti-
  where each pixel represents an intensity value         cated method of quantizing, which produces the
  between one color (all zeros) and another color        illusion of true gray scale or color. Although dither-
  (all ones). Since the two colors are usually black     ing need use no more colors than simple quantiz-
  and white, they produce a range of gray-scale          ing, it results in displayed images of much higher
  values to represent the image.                         quality.
                                                            Image compression is a transforn~ationprocess
  A color image has multiple components per
                                                         used to reduce the amount of memory required to
  pixel, wherc each component is a group of
                                                         store the information that represents the image.
  bits representing a value within a given range.
                                                         Different compression methods are used for bitonal
  Each component of a color image corresponds
                                                         images than those used for gray-scale and color
  to a part of the color space in which it is repre-
                                                         images. These methods are stantlardized to speclfy
  sented. Color spaces may be thought of as dif-
                                                         exactly how to compress and decompress each
  ferent ways of representing the analog, visible
                                                         type of image. For bitonal images, the most corn-
  range of colors in a digitized, numeric form. The
                                                         moll standards are the ones ~ ~ s eind facsimile
  most popular color spaces are television's YUV
                                                         machines, i.e., Recommendations ~ . 4    and ~ . of6 the
  format (one gray-scale and two color compo-
                                                         Comite Consultatif Internationale cle TkICgraphique
  nents) and the bit-mapped computer display's
                                                         et Telkphonique (CCITT).l.~ommonlyknown as
  RGB format (red, green, and blue components).
                                                         the Group 3 and Group 4 standards, the desig-
   The resolution of an image is simply the density      nations are often shortened to G3-ID, G3-2D, and
of pixels per unit distance; the most common den-        ~ 4 - 2 ~ .
                                                                   referring to the particular standard group
sities are measurecl in dots per inch (dpi), where       and to the coding method, which may be either
a pixel is called a dot. For example, a facsimile        one- or two-climensional. For gray-scale and color
machine (which is nothing more than a scannel;           images, the Joint Photographic Experts Group
printer, and phone modem in the same unit) typi-         (JPEG) standard is now emerging as a joint effort of
cally scans and prints at 100 dpi, although newer        the International Standards Organization (ISO) and
models are capable of up to 400 dpi. As another          CCITT.3 Whichever format or process is used, com-
example, most workstation display monitors are           pression is a compute-intensive task that involves
capable of 75- to 100-dpi resolution, and some high-     mathematically removing redundancy from the
end monitors achieve u p to 300-clpi resolution.         pixel data.
   To display an image at a density different from          A typical compression method creates an
its scanned density, without altering the image's        encoded bit stream which cannot be displayed
original size, requires the image to be scaled, so       directly; the compressed bits must be decom-
that the new image density matches the output            pressed before anything recognizable may be



10                                                              Vol. 3 No.4   Fh11 1991 Digital TecbvzicalJournal
                                                         Hardzuare Accelerators for Bitonal Image Processing


displayed. The term compression ratio represents              The major drawback in the imaging process is
the size of the original image divided by the size of      increased data size, which results in storage mern-
the compressed form. For bitonal images using              ory and network transport problems. High scan
the CCITT standards, the ratio is commonly 20:l on         densities and color information components create
normal paper documents, but can vary widely with           large volumes of data for each image; a bitonal
the actual content of the image. The CCITT stan-           image scanned at 300 dpi from an 8.5-by-11-inch
dards are also "lossless" methods, which means that        sheet of paper requires over 1 megabyte of mem-
the decompressed image is guaranteed to be iden-           ory in its original pixel form. Therefore, compres-
tical to the original image (not one bit different).       sion and decompression are integral parts of any
In contrast, many "lossy" compression methods              imaging system. Even in compressed form, a bitonal
allow the user to vary the compression ratio such          image of a text page requires about 50 kilobytes
that a low ratio yields a nearly perfect image repro-      of storage, whereas its American standard code
duction and a high ratio yields a visible degradation      for information interchange (ASCII) text equivalent
in image quality. This trade-off between compres-          requires only 4 to 5 kilobytes. Similarly, a graphics
sion and image quality is very useful because of the       file to describe a simple block diagram is much
wide range of applications in imaging. An applica-         smaller than its scanned image equivalent.
tion need pay no more in memory space and band-               Based on these advantages and limitations, sev-
width than necessary to meet image quality                 eral applications have emerged as perfect matches
requirements.                                              for imaging technology. Bitonal images are used
                                                           in the expanding market of document manage-
A Nezu Data Type and Its Features                          ment, which consists of scanning volumes of
The image data type is fundamentally different             papers into images. These images are stored and
from text and graphics. When a user views charac-          indexed for later searching and viewing. Basically
ters or pictures on a display device, the source of        an electronic file cabinet, this system results in
that view is usually not important. A sheet of text        large savings in physical cabinet space, extremely
from a printer may have come from either a text file       fast document access, and the ability for multiple
where the printer's own fonts were used, a graph-          users to access the same document simultaneously.
ics file where the characters were drawn with line         Gray-scale imaging is often used in medical appli-
primitives, or an image file where the original text       cations. Electronic versions of x rays can be sent
document was scanned into the system. In any               instantly to any specialist in the world for diagno-
case, the same letters and words present the user          sis, and the ordering of sequential computer-aided
with approximately the same information; the dif-          testing (CAT)-scan images into a "volume" can pro-
ferences are mostly in character quality and format.       vide valuable three-dimensional views. The appli-
   In spite of their large storage space require-          cations for color imaging are relatively new and
ments, images have several advantages over graph-          still emerging, but some are already in use commer-
ics or text. First, consider the process of getting        cially, e.g.,license and conference registration pho-
the information into the computer. With the imag-          tographs. A further extension to still imaging is
ing process, documents may be scanned automati-            digital video, which can be considerecl as a stream
cally in a few seconds or less, compared to the time       of still images. In conjunction with audio, digital
required for someone to type the information cor-          video is commonly known as multimedia, applica-
rectly (absolutely no errors) into a text file. Also,      tions for which range from promotional presenta-
even though the software exists to convert elec-           tions to a manufacturing assembly process tutorial.
tronic raster images into graphic primitive files, the        In this paper, we focus on the static bitonal imag-
process loses detail from the original image and is        ing method of representing real-world data inside
relatively slow. Next, consider the variety of infor-      computers. Static imaging is a simpler method of
mation possible on a sheet of paper: a user can-           representing a broader range of information than
not easily reproduce a diagram or a signature on a         the text and graphics media types, but it carries
document. A scanned image preserves not only the           a greater requirement for processing power and
characters, but their font, size, boldness, relative       memory space. In addition, static imaging can be
position, any pictures on the page, and even               viewed as one part of true multimedia, as can text,
smudges or tears depending on the quality of the           graphics, audio, video, and any other media for-
image scan.                                                mats. Yet static imaging does not have the system


Digital Technical Journal   Vo1.3 No. 4   Fa11 1991                                                           11
Image Processing, Video Terminals, and Printer Technologies



speed requirements of a motion video and audio           mately 3 kilobytes of memory. If the same shcct of
system. which must prescnt data at rcal-time rates.      paper is digitized by scantling at various dot tlcn-
As long as the user can dcal with static images at       sities, the resulting data files art. huge, ;IS sho\vn
an interactive rate, i.e., being able to view the        by the decompressed bitonal image sizes in 'Inable1.
images in thc format of choice ;IS F~stas the user       Note that l'iible 2 includes the size of thc scanned
c;un select them, thcn static imaging is ;I powcrhl      image if scanned in way-scale and color motles,
rnctli;~presentation tool. l'hc next section presents    although using these modes woultl not makc sense
the importi~ntissues concerning bitonal imaging in       on a black-and-white sheet of paper. The image
a document management environment.                       sizcs are included for comparison and are discussed
                                                         in the section Future Image Accelerator Require-
Bitonal Imaging Issues                                   ments. The data presented in Tables 1 and 2 illus-
As previously mentioned, bitonal electronic imag-        trates that the size of the original ASCII file is much
ing as an dtcmativc to paper documents offers            smalkr than any of the scilru~edversions. The data
many benefits, such as retluccd physic11 storage         also gives evidence that scxnned Images, in gencr;~l,
space, instant and simultaneous access of scanned        require considcrablc memory.
images, and in general a more accessible media.             Since the typical use for bitonal images is for
Serious issues need to be resolved before a produc-      volume document archival, an imaging application
tive imaging operation can be implemented. The           must include a compression process to reduce mem-
chief issues are the irnage data size, transport         ory usage. This process must transform the original
method, perceived rendering speed, and final legi-       scanned image file to a much smaller file without
bility. In the following sections, we examine each       losing the content of the original scanned data.
issue and present solutions.                                Compression algorithms may takc different paths
                                                         to achieve the same result, but they share one basic
Digitized Image Data Size                                process, the removal of redundant information to
The most important issue concerns irnage data sirs.      reduce the object size. A common compression
Images are typically documents, drawings, or pic-        routine searclies the pixel data for groupings, or
tures that have been digitized into a computer-          "run lengths," of black or white pixels. Each run
readable form for storage and retrieval. Depending       length is assigned a code significantly shorter than
on the dot density of the scanner, a single image        the run length itself. The cotles are assigned by
can be 1 to 30 megabytes o r more in size. However,      statistics, where the most frequent run lengths
storing a single irnage in its scanned form is not the   are assigned the shortcst corles; statistics have been
typical usage model. Instead, a company may have         amassed on a variety of document types for differ-
tens of thousands of scanned documents. Clearly,         ent scan densities and document sizcs. A compres-
with today's storage technologies, a company can-        sion proccss parses through the original image
not afford to store such a large volume of images        file, generating another file that contains the codes
in that format.                                          representing the original image. Figure 1, a sample
   A typical ASCII file representing the text on an      bitonal imagc compression, illustrates these com-
8.5-by-11-inch sheet of paper requires approxi-          pressed codes in a serial bit stream.


Table 1 Sample Bitonal Image Sizes
                                   Scan                    I            Kilobytes of Data I
Document Type                      Density                 Pixel Form                     Typical
(Paper Size)                       (dpi)                   (Decompressed)                 Compressed

A size
(8.5 x 11 inch)

E size                               100                           1826                                       106
(44 x 34 inch)                       200                           7305                                       114
                                     300                          16436                                       127




12                                                              Vol. .3 /Vo. 4   FLI// 1991   Digital Technical Jourrrnl
                                                                  Hardware Acceleratorsfir BiLonnl Image Pro~essfn~q


Table 2    Sample Gray-scale and Color                              Network Transport Constraints
           l mage Sizes                                             The network transport performance for an image
                                         Kilobytes of Data          is important, because i1n;lgc.s arc rnost often stored
Document Type                            in Pixel Form              on a remote system and vicwctl on a widespread
and Size                                 (Decompressed)             group of display stations. For example, onc group in
                                                                    an insurance company receives and scans claim
128 x 128 pixel, 12 bits per pixel                  24
gray-scale image
                                                                    papers to create a centralized image database,
                                                                    while users in another group acccss the tlocuments
512 x 512 pixel, 8 bits per pixel
color image                                                         simultaneously to proccss claims. For thc imaging
512 x 512 pixel, 24 bits per pixel                                  system to be productive, this image d;~taneeds
color image                                                         to be transported quickly from one group to the
8.5 x 11 inch, 100 dpi, 24 bits                  2740               other: telephone attendants answering calls must
per pixel, color image                                              have immediate access to the data.
                                                                       Scanned image documents take a long time to
                                                                    transport between systems, simply because they are
   Several algorithms for bitomal compression are                   so large. When compression techniques arc used, a
widely used totl;ty. As mentioned in the previous                   typical uncompressed image stored in 1 megabyte
section, the most common for bitonal images are                     can be reduced to approximately 50 kilobytes.
the CCII?' standards G3-1l3, <;3-2D, and ( ; 4 - 2 D , which        Since transport time is proportional to the number
all use the approach just described. For the one-                   of packets that must be sent across the network,
dimensional method, the algorithm creates run                       reducing the data size to 5 percent of its original
lengths from all pixels on the same scan line. In the               size also reduces the transport time to 5 percent
two-dimensional methods, the algorithm some-                        of the original time. Tliercfore, you can now send
times creates run lengths the same way, but the                     twenty compressed images in the same time previ-
previous scan line is also examined. Some codes                     ously spent sending one uncompressed image.
represent run lengths and even whole scan lines                         Even with compression techniques, the image
as "the same as the one in the previous scan line,                  files are still larger than their text file equivalents.
csccpt offset by .V pixels," where N is a small inte-               Moreover, most network protocols limit their
ger. Tlic two-climensional method takcs advan-                      packet size to a maximum number of bytes, i.e., an
tage of most of the recluntlancy in an image and                    image file larger than the maximum packet size
returns the smallc5t compressed file. In addition to                gets divided over multiple packets. If the protocol
prcscrving system memory, these compression                         requires an acknowledgment between packets, then
methods significantly Improve network transport                     the transport of a large file over a busy network
performance.                                                        becomes a lengthy operation.

                            IMAGE PIXELS
                       m
                                                               ONE SCAN LINE OF PIXELS

                                                                                 ' I




                                                   600 WHITE         250 WHITE         845 WHITE
                                                    /        30 BLACK   /    30BLACK       \




                                   COMPRESSED CODES IN A CONTINUOUS BIT STREAM



                                          Figure I        Bitonal Image Compression


Digitul Technical Journal     Wtl, .? No. 4   Fa11 1991                                                                  13
Image Processing,Video Terminals, and Printer Technologies


   The platform for our most recent accelerator is          them. The disk access time data from the DECimage
the VT1200 X window terminal, which uses the                project analysis shown in Table 3 demonstrates that
local area transport (LAT) network protocol. We             the disk file read time is a significant portion of the
soon realized that the X server packet size was             overall response time. Thus, the display station
limited to 16 kilobytes and the typical A-size              render time is the only area of the display response
compressed document was approximately 50 kilo-              time which can be clearly intluencetl and is, there-
bytes. With this arrangement, each image transport          fore, the main focus of our image accclcrators. The
would have required four large data packets and             local processing that must occur a t the display sta-
four acknowledgment packets. Working with the               tion is not a trivial task; an image must be tlecom-
X Window Terminal Base System Software Group,               pressed, scaled, ant1 clipped to fit the user's current
we were able to raise the packet size limit to              window size, and optionally rotated.
64 kilobytes. The base system group also imple-                The decompression procedure inverts the com-
mented a delayed acknowledgment scheme, which               pression process; both are computationally com-
eliminates the need for the client to wait for an           plex. Input to the procedure is compressed data,
acknowledgment packet before sending the next               and output is the original scan line pixel data,
data packet. Table 3 shows compressed image data            which can be written to a display device. Scaling
taken during the DECimage 1200 dmiopment                    the data to fit the current window or fill a region
cycle. Notice that the network transport times              of interest is not trivial either: a huge input data
for Digital document interchange format (DDIF)              stream must be processed (the decompressed, orig-
decrease sharply aftcr the pacltct changes.                 inal file), and a moderate output data stream must
                                                            be created (the viewable image to be displayed).
Perceived Rendering Speed                                   While simple pixel replicate and drop algorithms
Because the image scanning and compression                  may be used to scale the data, a more sophisticated
operations occur only once, they are not as                 scaling algorithm has been shown to greatly
performance-critical as the decompression and               enhance the output image quality.
rendering for display operations, which are done               In addition to scaling and clipping, the orthogo-
many times. Decompression and rendering are part            nal rotation of images (in 90-degree increments)
of the system's display response time, which is a           is a usefill function on a display station. Some docu-
critical factor in a system designed for high-volume        ments may have words running in one direction
applications that access thousands of images daily          while pictures are oriented another way, or the user
This time is measured from the instant the user             may wish to view a portrait-mode image in land-
presses the key to select an image to view, to the          scape mode. In either case, orthogonal rotation
moment the image is displayed completely on the             can help the user understand the information; i.e.,
screen. The display response time is a function of          the increased time to rotate the view is warrantecl.
the disk read t h e , network transport time, and dis-         When an image is scanned, particularly with a
play station render time.                                   hand-held scanner, the paper is never perfectly
   Although network transport time and disk file            aligned. Thus, the image often requires a rotation of
read time have a direct effect on the response time,        1 to 10 degrees to make the view appear straight
accelerator developers rarely have any control over         in the image file. However, multiple users want the


Table 3    DDlF lmage File Read Time and File Transport Performance
                                                                        Network Transport Time
                                                                            (milliseconds)
                      7Disk Read Time                          7 After                  Before
lmage Size                                 (milliseconds)               Packet         Packet
(kilobytes)           MicroVAX II             VAX 8800         VAX 6440 Change         Change




                                                                   Vol. 3 No.4 Fa11 1991 Digital Tecl~tticalJozrr~rrrl
                                                         Hardware Acceleratorsfor Bitonal Image Processing


information from the document as quickly as pos-           General Design Strategy
sible, and should not have to rotate the image by          The number of applications using bitonal image
a few degrees to make it perfectly straight on the         data continues to increase. In general, these appli-
screen. Therefore, this minimal rotation should            cations attempt to offer low cost while achieving
be done after the initial scanning process; i.e.,          an interactive level of performance, defined as
only once, prior to indexing the material into             no more than 1 second from point of request to
the database, and not by every user in a distributed       complete image display. Ultimately, software may
environment. Because any form of rotation is               provide this fi~nctionalitywithout hardware accel-
compute-intensive, allowing the user to perform            eration, but today's software cannot. Moreover, the
minimal rotations at a high-volume view station            parameters of image systems are not static; scan
would reduce the application's perceived ren-              densities, overall image size, and the number of
dering speed and add little value to the station's         images per database will all increase. These
function.                                                  increases will provide the most incentive for hard-
                                                           ware assist at the low end of the X window ter-
Final Legibility                                           minals market, because software alone cannot
While the primary issue facing imaging applica-            perform the amount of processing that users will
tions is data size, image viewing issues must also be      expect for their investment.
addressed. In short, an effective bitonal imaging
                                                           The User Model Although a single model cannot
display system must be responsive to overall image
                                                           suit every application, imaging is centered on cer-
display performance and the resulting quality of
                                                           tain functions. Therefore, a user model built on
the image displayed. To enhance our products, we
                                                           these functions would be very useful in mapping
optimized the display performance parameters as
                                                           individual steps to the hardware: hardware versus
best we could, given that some parameters are not
                                                           software performance, the function's frequency of
under our control. Improvements to monitor reso-
                                                           use, and the cost of implementation.
lution and scanner densities continue to increase
                                                              The general user model for bitonal imaging sys-
the legibility of images. An affordable image system
                                                           tems is relatively simple. A small market exists for
should increase the image legibility by rendering
                                                           image entry stations, in which documents are
a bitonal image into a gray-scale image using stan-
                                                           scanned, edited, and indexed into a database. Wllile
dard image processing techniques. We discuss the
                                                           a high throughput rate is important at these sta-
method used in our accelerators, i.e., an intelligent
scale operation in the hardware pipeline, in the           tions, a general-purpose image accelerator is not
                                                           the solution-dedicated       entry stations already
next section.
                                                           exist in the market. Instead, we designed a general-
                                                           purpose platform, or versatile media view station,
Hardware Accelerator Design                                to be used for imaging applications alongside other
As explained in the previous section, transforming         applications. The user model for this larger market
documents into a stream of electronic bits is not          is a set of operations for viewing and manipulating
the demanding part of a bitonal imaging process            images already entered into a database. The most
for document management. Also, scanners and                common operations in this model are decompres-
dedicated image data-entry stations abound in the          sion, scaling, clipping, orthogonal rotation, and
marketplace already. Instead, the challenge lies in:       region-of-interest zooming.
(1) managing the image clata size to control
memory costs and reduce network slowdown;                  Display Performance and Quality Optimiz~~tion
(2) increasing the image rendering speed, i.e.,            The main thrust of the DECimage accelerator is to
decompress the image, scale it, and clip it to fit         achieve interactive performance for the operations
the window size with optional rotation; and                defined in the user model. A secondary goal is to
(3) increasing the quality of the displayed images.        bring added value to the system by increasing the
This section describes the way our strategy                quality of the displayed image compared to tlie
influenced the design of DECimage products. We             quality of the scanned image. A side effect of maxi-
also discuss the chips used for decompression and          mizing performance in hardware is that the main
scaling, and how Digital's existing client-server pro-     system processor has work off-loaded from it, free-
tocols support these imaging hardware accelerators.        ing it for other tasks.



Digital TechnicalJozrmal   1'01.3 No. 4   Full 1991                                                         15
Image Processing, Video Terminals,and Printer Technologies


   The general design of the accelerator uses a            The most straightforwartl method of intcgr;ition is
pipelined approach. Since maximum performance              to relocate the hardware from the prcscnt option
Is desired and a large amount of &ita must be p r o        to the main system processor board; successive
cessed by the accelerator board, multiple passes           steps of ititcgration would consolidate mapped
through the board are not feasible. Similarly, the tar-    hardware to fewer total devices. The most cost-
geted low cost does not aIlow a whole image buffer         effective integration will be the inclusion of the
on the board. With one exception (rotation), all           mapped hardware in the processor in a way similar
board processing should be done in one pipeline,           to a floating-point unit (1:1'1'). Just as graphics accel-
with the system processor simply feeding the input         eration is now being incli~dedin system processor
end of the pipe and draining the output end.               design, images will eventually achieve the status of
Because of the large amount of data to be read from        a required data type and thus be supported in the
the board and displayed on the screen, the proees          base system processor.
sor should onIy have to move that data, not do any
further operations o n it. To this end, any logic          Product DeBnition- What Does the User
required to format the pixels for the display bitmap       Want?
should be included in the pipeline.                        The previously clescribecl strategy was used in the
                                                           design of the image accelerator board for the
Cost Reduction through Less Expensive System               DECimage 1200 systcm. Thc product requirements
Components The net cost of a bitonal imaging               called for a low-cost, high-performance document
system is influenced by the capability of the assist       image view station These reqi~irementsevolved
hardwdre. The capability of the hardware implies           from the belief that most users currently investi-
flexibility in the choice of other system hardware.        gating imaging systems are interested in applica-
In this regard, the most significant impact on cost        tions and hardware that will enable them to quickly
occurs in the memory and the display. A system that        and simultaneously view clocument images ant1 run
makes use of fast decompression and scaling hard-          their existing no~~imagingapplications.These users
ware can quickly display compressed images from            are involved with commercial and business appli-
memory. This means either more images can be               cations, rather than scientific applications. The
maintained in the same memory, or the system can           DECimage 1200 system was planned for the manage-
operate with less memory than it would without             ment of insurance claims processing, hospital
the assist hardware; less memory means lower cost.         patient medical recortls, bank records, and manu-
   A more dramatic effect on system cost is in the         facturing documents. As previously stated, the
display. Imaging systems generally need higher-            imaging functions required for these view-oriented
density displays than nonimaging systems, but the          applications are high-speed decompression, seal-
cost of a 150-dpl display is approximately twice the       ing, rotation, zooming, and clipping.
cost of a 100-dpi display of the same dimensions.
However, we found that we could increase legibil-          General Product Design
ity, i.e., expand a bitonal image to a gray-scale repre-   In defining the image capable system, the key
sentation, by using an intelligent scale operation         points in the product requirements list were
In the hardware pipeline. For example, a bitonal
image rendered to a 100-dpi display using the intel-         High-performance image display
ligent scale process gives the perceived legibility          Low cost
of the same image rendered to a 150-dpi clisplay
with a simple scaling method. That is, by adding the         Bitonal images only (not gray-scale or color)
intelligent scale, a 100-dpi clisplay can be used            View-only functions
where previously only a 150-dpi display would be
adequate.                                                    The need for high-performance display influ-
                                                           encecl the project team to design the hardware
Cost Reduction through Integration Presently, as           accelerator board to handle imagc decompression,
in the L>E(:itnage 1200, hardware-assisted imagc           scaling, and rotation. Previous performance test-
manipulation exists as a board-lcvel option. Higher        ing on a 3-WJP (VAX-11/780 units of performance)
levels of integration with the base platlorm will          CYU had yieldccl irn;tge software display times from
provide lower overall cost for an imaging system.          5 to 19 seconds. These images were compressetl



16                                                                Vr,I.3 No. 4   Fall 1991 Digital TechnicalJournc~l
Image Processing, Video Terminals, and Printer Technologies




                                                  INTERFACE          MEMORY                  HARDWARE




                                                      SYSTEM ADDRESSIDATA BUS

                                  t                         t           t
                            MEMORY                                   MEMORY




                                           Figure 3     VT1200 3j)sternArcbilect~~re


   The rotillion circuit handles 90- and 270-degree                to be decompressed before it can begin scaling;
rotation, whereas 180-dcgree rotation is hanclled                  instead, scaling begins as soon as the first byte of
in the data packing shift registers by changing the                data is output from the decompressor Thus tlif-
shift direction. 'I'he circuit rotates an 8-by-8-bit               ferent pieces of the image file are b e ~ n gdecom-
block of data at a time. The first byte of cight con-              pressed, scaled, and rotatecl siniultaneousl~~. The
secutive scan lines is written into eight intlividual              hardware pipeline also eliminates the need to
byte-wicle registers. The most significant bit (MSB)               store the fully uncompressed image (approximately
of each of these registers is connected to the byte-               1 megabyte of clata for A-size 300-dpi images) in
wide rotation output port latch. A procchsor reatl                 memoly. The compressed image is wrltten from
of this port triggers a simultaneous shift in all of the           system memory to the accelerator board and a
rotation data registers so that the next bit of each               tleconipressetl, scaled, and clipped image is read
register is now latched at the rotation output port                from the board. Because of the speed of the hard-
for the next read. Figure 5 diagrams the rotation                  ware, the software can redisplay an image with dif-
circuitry just described.                                          ferent scaling, clipping, or rotation parameters; it
  To achieve the best performance, we pipelinecl                   merely changes the harclware setup for the differ-
the h~nctionalblocks in the hardware. 'l'hc scaling                ent parameters and sends the compressetl image
engine docs not need to wait for the entire image                  file back through the accelerator board pipeline.



                          BUFFER                RAM BUFFER




                             J-                                                                   4
                                                  SYSTEM ADDRESSIDATA BUS

                                                  t                                      t
                                      I   COMMAND
                                          AND STATUS
                                          REGISTER      I                     ROTATION
                                                                              MATRIX




                     Figure 4         Block Diagram of DECint~~ge
                                                               1200 Accelerator Hardtoare



18                                                                          Ihl. .I IVO. 4   Fall I991   Digital TechnicalJournal
                                                               Hardware Acceleratorsfor Bitonal Image Processing


               8 SCAN LINES OF IMAGE DATA
 8-BYTE 8-BYTE 8-BYTE
                                                           .     the word contain the number of consecutive white
                                                                 or black pixels (called the run length). The upper
 BLOCK BLOCK BLOCK
 #1     #2     #3                                                bit of the word contains the run-length color code
    I                                                            (0for a white run and 1 for a black run). An FLC is
                                                                 read from the FIFO buffer and decoded into one of
                                                                 elght routine types. Each routine is made up of sev-
                  8x8                       ROTATION
                  ROTATION                  OUTPUT               eral states that control the color code toggling, run-
                  MATRIX                    REGISTER             length adder, and accumulator circuits. At tlie end
                                                                 of each routine, a new word containing the run-
SCAN LlNE 0                                                      length and color information is written into a FIFO
SCAN LlNE 1
SCAN LlNE 2
                                                                 buffer for the h a 1 stage.
SCAN LlNE 3                                                         The final stage of the decompressor chip con-
SCAN LlNE 4                                                      verts the run-length and color information to black
SCAN LlNE 5                                                      or white pixels. This stage outputs these pixels in
SCAN LlNE 6
                                                                  16-bit chunks when the scaling chip sends a signal
SCAN LlNE 7
                                                                 indicating a readiness to accept more data.



                                     n
                                      0 1 2 3 4 5 6 7
                                                                 Scaling Chip The primary purpose of the scaling
                                            DISPLAY BYTE         chip is to input high-resolution document images
                                                                 (300 dpi) and scale them for display on a medium-
                                                                 density monitor (100 dpi). The chip offers inde-
                                                                 pendent scaling in the horizontal and vertical
              Figure 5   Rotation Matrix
                                                                 directions. The scaling design implemented in the
                                                                 chip is a patented algorithm that maps the input
ASIC Design Description                                          image space to the output image space. General
The ASIC design consists of a decompressor chip,                 1v1-to-Npixel scaling is provided where M and N are
which decodes the compressed image data to pixel                 integers between 1 and 127, with the delta between
image data, and a scaling chip, which converts the               them less than 65. IM represents the number of pix-
image from the input size to the desired display size.           els in and N represents the number of pixels out (in
                                                                 the approximated scale factor).
Deco7npressor Chip The decompressor chip acts                       Given an image input size and a desired display
as a CCI?T binary image decoder. The chip contains               size, we must find the M and N scale Fdctors that
three distinct stages, which are pipelined for the               best approximate the desired scale factor, within
most efficient data processing. Double buffering                 the range limits of M and N as previously stated.
of compressed input data is implemented to enable                Thus an input width of 3300 and a desired out-
simultaneous input data loading and image decod-                 put width of 550 are represented by an PI of 6 and
ing to occur. Compressed data is loaded into the                 an N of 1. The approximatecl 1l.I and N values are
input buffer by the processor through a 16-or 32-bit             loaded into the chip scale registers for downscaling
port. Handshaking controls the transfer of decom-                or upscaling.
pressed data from the decompressor's 8-bit-wide                     The chip scaling logic uses the scale register val-
output bus to the scaling chip.                                  ues to increment the input pointer position and
   The first stage of the decompressor chip con-                 generate output pixels. A latched increment deci-
verts CC17T-standard Huffman codes, which are of                 sion term is updated every clock cycle, based on
variable-length, to 8-bit, fixed-length codes (FLCS).~           the previous term and the scale register values.
A sequential tree follower circuit is implemented                When scaling down (where fewer pixels are output
to handle this conversion. Every Huffman code cor-               than are input), tlie logic increments the input
responds to a unique path through the tree, which                pointer position every clock cycle, but only out-
ends at a leaf indicating the FLC. The 8-bit FLC is              puts a pixel when the increment decision term is
sent to a first-in, first-out (FIFO) buffer, which holds         greater than or equal to zero. Figure 6a illustrates
the data for the second stage.                                   how this algorithm maps input pixels to o u t p ~ i tpix-
   The second stage of the chip generates a 16-bit,              els for a sample reduction. When scaling up (where
run-length value from the FLC. The lower 15 bits of              every input pixel represents at least one outpiit



Digital Technical Journal    Vol. 3 No. 4    Fa11 1991                                                                 19
Image Processing,Video Terminals, and Printer Technologies


                   SCALE DOWN FROM 10 INPUT PIXELS TO 5 OUTPUT PIXELS
                   (M=ZANDN=l)




                   INPUT

                   INCREMENT
                   DECISION  D=l     D=-l   D = 1 D=-1    D = l D=-1    D = l D=-1      D = l D=-1
                   REGISTER

                   OUTPUT
                                 1




                                               (a) Downscaling



                   SCALE UP FROM 3 INPUT PIXELS TO 9 OUTPUT PIXELS
                   (M=lANDN=3)




                   INPUT

                   INCREMENT
                   DECISION  D=-1     D = l D=-3   D=-1   D = l D=-3     D=-1     D=l D = 3
                   REGISTER

                   OUTPUT              •
                                 1     2




                                                (6)   Upscaling

                                      Figure 6 Chip Scaling Examples

pixel), thc logic outputs a pixel every clock cycle,        tion ancl display at the server using the hardware
but only increments the input pointer position              accelerator board. Like the X I 1 protocol, the XIE
when the increment decision tern1 is greater than           protocol consists of a client-side library called
or equal to zero. Figure 6b illustrates how this algo-      XIElib, which provides client applications access
rithm maps input pixels to output pixels for a sam-         to image routines, and a server-side piece, which
ple magnification. For both cases, the value of the         executes the client requests. The xrE server imple-
pixel (black or white) being output is the value of         ments support at two levels: device-independent
the input pixel pointed at during that clock cycle.         and device-dependent. The device-dependent level
In this dcscription, simply substitute rows for pix-        supports the functions that benefit from optimi-
els to reprcscnt the vertical scaling process.              zation for a particular platform, or functions that
                                                            are implemented in hardware accelerators. The
Software Sz,lpportfor the Hardware                          device-independent level enables quick porting of
Software support is needed to enhance the func-             functionality from platforrn to platform. Figure 7
tions of the hardware accelerator in our imagc view         illustrates the S/XIE client-server architecture.
station. As mentioned in the section General                   The client-side XlElib offers the minimum
Product Design, thc XIE protocol extends the X l l          functions necessary for image rendition and dis-
core protocol to enable the transfer of compressetl         play The toolkit level offers higher-level routines
images across the wire ant1 to cnable image rendi-          that assist with windows application development.



20                                                                   Ihl. .? IVO. 4   R111 1991   Digital Technical Journrrl
                                                          Hardware Acceleratorsfor Bitonal Image Processing


                                                            which is essentially as fast as the user can ask for
                                                            the displays. This speed is possible because the
                                                            image already resides in compressed form in the
                                                            server memory. Thus, the image does not have to
                                                            be read from the disk or transported across the
          DECWINDOWS                 IMAGE
          TOOLKIT                    TOOLKIT                network.

                                                            Future Image Accelerator
                                                            Requirements
                                                            Hardware accelerators will continue to be required
                                                            for bitonal imaging until software can provide the
                                                            same fiinctionality at the same performance level.
                                                            This section discusses the more complex image
                                                            schemes that are used for gray-scale imaging and
                                                            multimedia applications. In contrast to bitonal
                                                            imaging, these applications will require the use of
                                                            hardware accelerators well into the future.
                                                              Other applications will require richer user inter-
                                                            faces utilizing continuous-tone images, video, and

         uDISPLAY
                                                            audio. All of these new data types are generally
                                                            data-intensive, and compression or decompression
                                                            of any one of them is a significant processing bur-
                                                            den. Handling them in combination indicates that
           Figure 7 W X I EArchitecttire                    the need for specialized hardware assistance will
                                                            persist for the foreseeable future.

An example of a routine at this level might be              Continuous-toneImages
ImageDisplay, which displays an image in a previ-           Bitonal images are either black or white at each
ously created window. ImageDisplay parameters               point, but some applications require smoothly
might include x and y scaling values, the rotation          shaded or colored images. These images are typi-
angle, and region-of-interest coordinates. Whether          cally referred to as continuous-tone images, a term
programming with the XIE protocol at the library            that denotes either color or gray-scale, e.g., photo-
or toolkit level, applications developers benefit           graphs, X rays, and still video. The representation
from the platform interoperability of the standard          and required processing of this image format is
interface. Image accelerator hardware and opti-             significantly different from that of bitonal images.
mized device-dependent XIE code changes the                    Continuous-tone images are represented by mul-
application's image display performance, but an             tiple bits per pixel. This format allows a greater
application developed using the X E protocol can            range of values for each pixel, which yields greater
run on any XlE-capable server.                              accuracy in the representation of the original
                                                            object. Additionally, each pixel can consist of mul-
Accelerator Performance Results                             tiple components, as in the case of color. The num-
With the DECimage 1200 X terminal, we have                  ber of bits used to represent a continuous-tone
achieved interactive performance rates, reduced             image is chosen according to the nature of the
memory usage, and increased final image legibility.         image.
We achieved these rates by transporting com-                   For example, medical X rays require a high
pressed files instead of huge pixel files and by imple-     degree of accuracy. Consequently, 12 bits are gener-
menting specialized image processing hardware.              ally regarded as the minimum acceptable for the
The DECimage 1200 can read, transport, decom-               rendering of this class of image. Color images typi-
press, scale, and display an 8.5-by-11-inch bitonal         cally require 8 bits per pixel for each component
document in 1 to 2 seconds. Successive displays,            (YUV or RGB format) for a total of 24 bits per pixel.
i.e., rotating, region-of-interest zooming, panning         Table 2 shows the relative size of samples of each
around the image, all occur in less than 1 second,          image. The need to express these images in a


Digital Technical Journal   Vol. .? No. 4   Full 1991                                                         21
Image Processing, Video Terminals, and Printer Techn


compressed format is obvious from the storage             because any change to either the evolvilig standard
space rrequirements and the current storage media         or a standard extension coulcl be easily introduced
limits.                                                   to the firmware. The fastest implementations arc
   Tlie comprcssion of continuoi~s-toneirnagcs can        achieved by special-purpose hardware accelerators.
be accomplisliecl in sever;il ways. Hornrevel; most          The JPEG implementation tlocs not require harcl-
imaging applications are not closed systems;              ware, i.e., the algorithm can be pcrformed corn-
inevitably, each system needs to rnanipul;lte images      plctely in software. Tlie case for hardware assist
that are not of its own making. For this reason wc        is made in performance. Table 5 clescribes tlie
aclopted the JPEG standard, wlhicl~specifics an ;~lgo-    reduced instruction set compilter (IUSC) processor
rithm for the comprcssion of gray-scale and color         performance, in millions of operations per second
images. Specifically, the JPEG compression methotl        (mops), needed to provide the specified operation
is based 011 the two-dimensional (2D) discretc            at a motion video rate of 30 frames per second.:
cosine transform (DCT). The D<:T decomposes an            However, generic NSC processors of those speeds
8-by-8 rectangle of pixels into its 64 2D spatial-        are not available today. Therefore, dedicated, cus-
frequency components. Tllc sum of these 64 2 D            tom very large-scale integration (VLSI) devices
sinusoids exactly reconstructs the 8-by-8rectangle.       (such ;I> the (:L550-10 from C-Cube Microsystems)
However, tlie rect;~ngleis approximated-and com-          must be used to perform the operation^.^ Even
pression is achieved-by tliscarding most of the           if the motion vidco rate is not required, the ASIC
64 components. 7'>,pically adjacent pixel values          devices offer the simplest hartlware solution.
vary slowly, thus there is little energy in most of the
discarded high-frequency components.                      Live Video and Video Compression
   The eclges of objects generally contribute to the
                                                          Video captures the natural progression of events in
high-frequency components of an image, whereas
                                                          an environment, and is therefore a natural and
the low-frequency components are made up of
                                                          efficient way to communicate. Consider, for exam-
intensities that vary more gradual ly. Tlie more
                                                          ple, the assembly of a set of components. One way
frequency components included in the approxi-
                                                          to express the assembly process is to show a series
mation, the more accurate the approximation
                                                          of photographs of the assembly at successive steps
becomes. Table 4 shows some sample JPEG image
                                                          of completion. As an alternative, vicleo can show
compression ratio^.^
                                                          the actual assembly process from start to finish.
   The most popul;tr part of the JPEG stantlard,
                                                          Subtle details of the process such as part rotations
the "baseline" method, was defined to be easily
                                                          and movements can be clearly conveyed, with tlie
mapped into software, firmware, or hardware.
                                                          added dimension of time.
Straightforward D(X' algorithms can be efficiently
                                                             Obviously, information expressed in video form
implemented in firmware for programmable DSP
                                                          can be valuable; howevel; significant problems arise
chips, due to their pipclined architecture. The first
                                                          in adapting video for use in computer systems.
systc1ns to embody the standarcl clitl so using DSPs,
                                                          First, the huge data size of vitleo applications can
                                                          strain the system's storage capability. Video can
Table 4      Typical Compression Parameters               be characterized as a stream of continuous-tone
             for JPEG                                     images. Each of these images consists of pixel val-
                                                          ues with individual components making up each
Compression      Compression Rendered Image               pixel. For video to have full effectiveness, the still
Ratio            Method      Integrity                    images must be presented at video rates. In manjf
       2:l       Lossless       Highest quality-          cases the rate to f a i t l ~ ~ l l y
                                                                                            reproduce motion is
                                no data loss              30 frames per secontl, which means that one
      12:l       Lossy          Excellent quality-        minute of uncompressed video (512-by-480pixels
                                indistinguishable         at 24 bits per pixel) would consume over 1 gigabyte
                                from the original         of storage. In addition to storage demands, large
                 Lossy          Good quality-             volumes of data cause banclwiclth problems.
                                satisfactory for          Presenting 30 frames per second to tlie video out-
                                most applications
                                                          put with the above parameters would require a
     1OO:l       Lossy          Low quality-
                                recognizable              transfer rate of more than 22 megabytes per sec-
                                                          ond from the storage device to tlie video output.


22                                                               1/01 .j No. 4   Fu/l I991   Digital Techlcical Jourrinl
                                                                        Hardware Acceleratorsfor Bitonal Image Processing


Table 5      Processing Requirements for lmaging Functions
                                                                                                              Processor
Imaging                      7Processor Operations per Pixel* 7Operations
Functions                     Read              Write             ALUt          Multiply         Total        at 30 fps (mops)
Pixel move                          .25            .25              0               0                  .5             15
Point operation                 2                1                  1               0              4                 120
3 x 3 convolve                  9                1                  8               9             27                 810
8 x 8DCT                       24                1                 14              16             65                1950
8 x 8 block                  128                 1                191               0           320                 9600
matching
'RISC processor, 1M pixels, 30 frames per second (fps), 8 bits.
tALU = arithmetic logic unit




Thus, reducing the amount of data used to repre-                          Audio and Audio Compression
sent the video stream would alleviate both storage                        Video is usually accompanied by audio. The audio
and bandwidth concerns.                                                   can be reproduced as it was recorded (with the
   The starting point for the compression of video                        video), or it can be mixed with the video from
is with still images and, as previously mentioned,                        a separate source (such as a compact disc (CD)
the JPEG algorithm can be used to compress still                          player). The audio data is defined by application
continuous-tone images. Because video can be rep-                         requirements. If the application allows lower
resented as a sequence of still images, the algorithm                     quality, the audio can be sampled at lower rates
could be applied to each still. This procedure                            with fewer bits per sample, such as telephony rates,
would produce a sequence of compressed video                              which are sampled at 8 kilohertz and 8 bits per
frames, each frame independent of the other                               sample. For applications requiring high-quality
frames in the sequence.                                                   (CD) audio, samples are usually taken at 44 kilo-
   The evolving Motion Picture Experts Group                              hertz and 16 bits per sample.
(MPEG) standard takes advantage of frame-to-frame                            Integrating audio data into an application creates
similarities in a video sequence, thereby enabling                        special problems. The major characteristic that
more efficient compression than the application                           differentiates audio from the other data formats
of the JPEG algorithm alone.Vn most situations,                           presented here is its continuous nature. Audio
video sequences contain high degrees of similar-                          must flow uninterrupted for it to convey any mean-
ity between adjacent frames. The compression of                           ing. In video systems, the flow of frames may slow
video can be increased by encoding a frane using                          down under heavy system loading. The user may
only the differences from the previous frame. The                         never notice it, or may not be annoyed by it. Audio,
majority of scenes can be greatly compressed; how-                        however, cannot slow or stop. For this reason, large
ever, scene transitions, lighting changes, or condi-                      buffers are used to allow for load variations that
tions of extreme motion need to be compressed as                          may affect audio reproduction.
independent frames.                                                          A more subtle problem in creating applications
   The need for hardware assist in this area is com-                      using audio is in synchronization. Audio data is
pelling. Table 5 shows that to sustain a SPEC; decorn-                    usually included to add another dimension of infor-
pression at 30 frames per second would require a                          mation to the application (such as speech).
1950-mops processor. The same result can be                               Without a method of synchronizing the video and
obtained using the CL550-10 JPEG Image Compres-                           audio, one data stream will drift out of phase with
sion P r o c e ~ s o r . ~
                       Although this device does not                      the other. One way to include synchronization is to
make use of interframe similarities to increase com-                      use time stamps on the audio and video. This is par-
pression efficiency, a device implementing the                            ticularly useful because standard time codes are
MPEC standard would exploit these similarities.                           used in most production machines.
Table 5 shows that motion compensation, to be                                The compression of audio data is not as efficient
supported ;it 30 frames per seconcl, requires a                           as that of the other data formats. Since a statistical
9600-mops processor.                                                      approach to coding audio is highly dependent on


Digital Technical Journal        Vol -3 No 4    F a l l 1991                                                                 23
Image Processing, Video Terminals, and Printer Technologies
                                                                                                                      -




the t).pe of input (i.e.,voice, musical instrument),         referenced. As the data is incorporated, it is com-
another method is requireel for gcncr;ilizetl inputs.        pressed and storecl. Authors require the c;ip;ibility
Differential pulse code modu1;ition (t)I-'(:kl) is oftcn     to edit anti mix vitleo and audio passages to get the
usecl to encocle ;iudio dat;~.DPCM cotles only the clz-      desired result. Moreover, the video and auclio m;ijr
ference betm~eenadjacent sample values. Since the            originate from different devices and may even be in
difference in value between samples is usually less          different formats.
than the magnitude of the sample, modest compres-                As clefined above, " t ~ s e rsystems" do not require
sion can be achieved ( 4 : l ) .The limitation using this    all of the functions that authoring systems neecl:
technique is in the coding of high-frequency clat;~.         only decompression is required in a typical user
   II:ird\v;ire assist for the audio data format will        system. Most existing user systems require at1 ana-
probahly come in the form of hardware to perform             log video source (vitleodisk), which is purchased
functions other than compression. For instance,              as part of the application. The device control is pel=
DSI-' algorithms can perform equalization, noise             formed by the application, i.e., when a user selects
reduction, ;lnd special effects.                             a passage to be replayed, the application sends
                                                             commands to the videodisk. Figure 8 depicts an
Mu1tinzedin                                                  authoring system and a user system, along with
As the term implies, multimctlia may integrate all           suggested 1/0 capability.
of the previously mentioned image formats. The                   Ncxt-generation multimedia platforms will make
word "may" is important in this co~itext.'l'his area         fill1 use of digital vitleo and audio. This implies that
has been mainly technology-driven, due to such               systems will be able to receive ancl transmit multi-
factors as lack of st;lnclards, clcveloping I/() clevices,   media applications ant1 data over networks. This
insufficient system bandwidth, differing clat;~for-          interactive capability miill improve the efficiency of
mats, and a vast amount of software integration.             many munclane applications and devices. For exam-
   It is currently a topic of debate nrhcther typical        ple, electronic mail can be extended with video and
users will require the ability to cre;itc, as opposed        audio annotations, or meetings can be transformecl
to only access. multimeclia source material. How-            into vicleo teleconferencing. The adoption of com-
ever, for discussion purposes, multimedi;~plat-              pletely digital data for multimedia also implies that
forms can be classified into two c;~tcgories:                the platform I/O will change. Some user systems
authoring and user. Authoring refers to creation             will not require analog device interfaces or control:
of multirneclia source material i111d requires differ-       the user will load the ;ipplication over the network
ent c;~pabilitiesthan user platforms. In the creation        or from at1 optic;~ldisk.
of a multirncdia application, data from many differ-            Each of the image formats described in this
ent devices may need to be digitized and cross-              section has different characteristics, and each will




                                                                                                   VIDEOCASSETTE
                                                                     VIDEODISK
                                                                                                   RECORDER


                     I10 AND DEVICE                                                110 AND DEVICE
                     CONTROL
                                                                                   CONTROL
                     COMPRESSION1
                                                                                   DECOMPRESSION
                     DECOMPRESSION


                                       COMPACT
         VIDEODISK
                                       DISK



                        NETWORK                                                       NETWORK




24                                                                  Vol .J No. 4   E:~~ll
                                                                                       I991   Digital Techiricnl Jonrnal
                                                         Hctrdware Acceleratorsfor Bitonal Image Processing


be presented in the embodiment of multimedia.              References and Note
Given the size, processing requirements (compres
sion and decompression), and real-time demands of          1. Standardization of Group 3 Facsimile Appa-
applications, hardware assist will be a necessity.            ratus for Doc~lnzent Transmission, CCITT
                                                              Recommendations, Volume vl-Fascicle VI1.3,
Summary                                                       Recommendation ~ . 4
                                                                                 (1980).
Imaging is a unique data type with special sys-            2. Facsimile Coding Schemes and Coding Control
tem requirements. To achieve interactive rates of             Functions for Group 4 Facsimile Apparatus,
bitonal image display performance today, hardware             CCITT Recommendations, Volume Wl-Fascicle
accelerators are needed; that has been the primary            WJ.3, Recommendation T.6 (1984).
focus of this paper, In the future, a general-purpose
                                                           3. Digital Compression and Coding of Continuous-
processor should be able to handle the imaging pro-
                                                              Tone Still Images, Part I, Requirements and
cess at the necessary speed, ancl beyond that, the
                                                              Guidelines, ISO/IEC JTCl Draft International
processor should be affordable in a low-cost bitonal
                                                              Standard 10918-1(November 1991).
imaging system. However, the bitonal document
processing market will not wait; it is in a high state     4. J. Mauro, X Image Extension Concepts, Version
of growth and requires that products like accelera-           2.4 (Cambridge: MIT X Consortium, June 1988).
tors be developed for at least a few years.
                                                           5. D. A. Huffinan, "A Method for the Construction
   Continuous-tone documents and multimedia
                                                              of Minimum Redundancy Codes," Proceedings
applications will place an even heavier processing
                                                              IRE, V O ~ .40 (1962): 1098-1101.
load on an imaging system. These areas will require
accelerators for several years. As imaging applica-        6. G. K. Wallace, "The JPEG Still Picture Compres-
tions, including bitonal, expand to cover more mar-           sion Algorithm," Communications of the ACM,
kets, the quality enhancements and performance                vol. 34, no. 4 (April 1991): 30-44.
benchmarks met by accelerators today will set
                                                           7 Table 5 is adapted from Y. Kim, "Image Com-
customer expectations. Consequently, our fiiture
                                                             puting Requirements for the 1990's: From Multi-
imaging products must be designed to meet these
                                                             media to Medicine," Proceedings of Electronic
expectations.
                                                             Imaging West (April 1991).
Acknowledgments                                            8. CL550JPEG Image Compression Processoq Pre-
The authors wish to express thanks to the                     liminary Data Book (San Jose, CA: C-Cube
X Window Terminal Hardware and Software Design                Microsystems Inc., November 1990).
Groups for their support in developing the                 9. Coding of fMoving Pictures ancl Associated
DECimage 1200 option. The two major ASICs used                Audio, Committee Draft of Standard I S 0 11172:
in the design were developed for previous pro-                ISO/MPEG 90/176 (December 1990).
jects, and those two design teams are also offered
our thanks. Special thanks to Frank Glazer and
Tim Hellman for their insightful research on the
image rendering process.




Digital TechnicalJournal   Vo1.3 iVo. 4   Full 1991                                                       25
