United States Patent [19]
`Iverson et al.
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US005459486A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,459,486
`Oct. 17, 1995
`
`[54] METHOD AND APPARATUS FOR
`COMBINING PALETTES OF COLOR
`QUANTIZED IMAGES
`
`[75]
`
`Inventors: VaughnS. Iverson, Beaverton, Oreg.;
`Eve A. Riskin, Seattle, Wash.
`
`[73] Assignee: University of Washington, Seattle,
`Wash.
`
`Orchard eta!.; "Color Quantization of Images" IEEE Trans(cid:173)
`actions on Signal Processing; vol. 39, No. 12; Dec. 1991.
`Balasubramanian et al.; "A New Approach to Palette Selec(cid:173)
`tion for Color Images;" Journal of Imaging Technology, vol.
`17, No. 6, Dec. 1991.
`Bottemiller, Robert L.; "Commoners on 'A New Vector
`Quantization Clustering Algorithm' ;" IEEE Transactions on
`Signal Processing, vol. 40, No. 2, Feb. 1992.
`
`[21] Appl. No.: 228,694
`
`[22]
`
`Filed:
`
`Apr. 18, 1994
`
`[51]
`[52]
`[58]
`
`[56]
`
`Int. Cl. 6
`.... ............ .............. ........ ........ ......... G09G 5/06
`U.S. Cl ............................ 345/153; 345/199; 3951131
`Field of Search ............................... 382117; 3951131;
`348/32-34, 172; 358/29, 81, 82; 345/199,
`150, 119, 153
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,794,386 1211988 Bedrij et a! ............................. 3451119
`4,862,389
`8/1989 Takagi ..................................... 345/119
`5,068,723 1111991 Dixit eta! ..
`
`OTIIER PUBLICATIONS
`
`Iverson, Vaughn S., Riskin,. Eve A.; "A Fast Method for
`Combining Palettes of Color Quantized Images"; ICASSP
`Apr. 27, 1993.
`Iverson, Vaughn S., Riskin, Eva A.; "A Fast Method for
`Combining Palettes . .. " Paper Summary; (Unpublished).
`Iverson, Vaughn; "Using Vector Quantization Algorithms
`for Choosing and Combining Palettes for Color Quantized
`RGB Images;" Jun. 9, 1992 (Unpublished).
`Iverson, VaughnS.; "A Fast Method For Combining Palettes
`of Color Quantized Images;" Jan. 27, 1993 (Unpublished).
`Gray, Robert M.; "Vector Quantization;" IEEE ASSP Maga(cid:173)
`zine, Apr. 1984.
`Equitz, William H.; "A New Vector Quantization Clustering
`Algorithm;" IEEE Transactions on Acoustics, Speech and
`Signal Processing, val. 37, No. 10; Oct. 1989.
`Gentile et a!.; "A Comparison of Techniques for Color
`Gamut Mismatch Compensation;" Journal of Imaging Tech;
`vol. 16, No. 5, Oct. 1989.
`
`(List continued on next page.)
`
`Primary Examiner-Richard Hjerpe
`Assistant Examiner-Lun-Yi Lao
`Attorney, Agent, or Firm-Steven P. Koda
`
`[57]
`
`ABSTRACT
`
`A color-mapped display sub,stem efficiently combines pal(cid:173)
`ettes of multiple images into a single shared palette. As each
`image already received a degree of distortion during con(cid:173)
`ventional palette selection, it is desirable to minimize further
`distortion during the palette combination method of this
`invention. A pairwise nearest neighbor (PNN) technique is
`used for combining colors from respective palettes to mini(cid:173)
`mize further distortion. For a final 256-color shared palette,
`up to 256 (n-1) individual vector merges are performed
`(where n is the number of image palettes being combined).
`In one embodiment, two vectors are chosen at each step that
`yield the lowest increase in distortion when merged. A mean
`squared error distortion measure of gamma-corrected values
`defined in YIQ space is used to compare distortion. Search(cid:173)
`ing time at each step is reduced from O(N2
`) to O(N), while
`also eliminating the need for extensive recalculation of color
`pair distortions between steps. Efficiency is enhanced
`because the matrix effectively caches distortion calculations
`between steps. One advantage of the invention is the ability
`to service run-time demands for the simultaneous display of
`multiple images on a personal computer or workstation
`platform having an 8-bit color-mapped display subsystem.
`Another advantage is the maintenance of image quality
`across similar multiple images using a shared palette.
`
`4 Claims, 4 Drawing Sheets
`
`/
`
`lOS
`
`HIMIMUfl
`DISmRTION
`
`~tATE COLOR
`
`c 1
`cz
`[3
`
`[ 4
`
`c 5
`
`C(n•kH
`
`C n•k
`
`[3
`
`[ 1
`
`[4
`
`Cs
`
`cn•k
`
`[50
`
`[4
`
`Q( 1,3 1
`
`012,11
`
`0(3 ,41
`
`0(4,51
`
`Q(S,n•kl
`
`o: n•k,4 I
`
`Vedanti Systems Limited - Ex. 2020
`Page 1
`
`

`
`5,459,486
`Page 2
`
`OTHER PUBLICATIONS
`
`Wu, Xiaolin; "Color Quantization by Dynamic Program(cid:173)
`ming and Principal Analysis;" ACM Transactions on Graph(cid:173)
`ics, vol. 11, No. 4; Oct. 1992.
`
`Horowitz, E., Sahni, S. "Fundamentals of Computer Algo(cid:173)
`rithms," Computer Science Press, 1978 pp. 98, 108-109.
`
`Taylor, R. et a! "Color Image Digitization For Real Time
`Video Processing".
`
`Vedanti Systems Limited - Ex. 2020
`Page 2
`
`

`
`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 1 of 4
`
`5,459,486
`
`12
`
`14
`
`CPU
`
`SYSTEM
`MEMORY
`
`!6
`
`10
`
`/
`
`32
`
`34
`
`DISPLAY
`SUBSYSTEM
`
`AUDIO
`SUBSYSTEM
`
`30
`
`LOCAL
`BUS I/F
`
`20
`
`42
`
`FIG.1
`
`HARD
`DRIVE
`
`FLOPPY
`DRIVE
`
`40
`
`36
`
`20
`
`50
`
`/
`. BUFFER
`.
`l
`VIDEO
`PROCESSOR
`
`52
`
`/
`~ VRAM
`
`.
`""
`~48
`
`COLOR-MAP
`TABLE
`/
`
`56
`
`FIG.2
`
`32
`
`54
`
`/
`I
`. DAC
`..
`
`46\
`
`DISPLAY
`DEVICE
`~
`
`22
`
`18
`
`~
`
`....
`
`~
`
`Vedanti Systems Limited - Ex. 2020
`Page 3
`
`

`
`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 2 of 4
`
`5,459,486
`
`60
`
`I
`REQUEST FOR SIMULTANEOUS
`DISPLAY OF MULTIPLE IMAGES
`
`r
`
`READ RESPECTIVE l/ 62
`PALETTES
`
`r
`COMBINE PALETTES
`
`64
`
`r
`
`LOAD COMBINED
`1 /66
`PALETTE INTO HIW v'
`LOOK-UP TABLE
`
`MAP PIXELS OF EACH
`IMAGE TO COMBINED
`PALETTE
`
`/
`
`68
`
`r
`
`OUTPUT PIXEL MAPS l/70
`TO GENERATE
`SIMULTANEOUS IMAGES
`
`END )
`
`FIG.3
`
`Vedanti Systems Limited - Ex. 2020
`Page 4
`
`

`
`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 3 of 4
`
`5,459,486
`
`102
`
`104
`
`t06
`
`110
`
`112
`
`114
`
`116
`
`DEFINE NxN MATRIX
`OF OISffiRTION V~lES
`FOR EACH COLOR PAIR
`
`FIG.4
`
`!!FINE MINIMUM
`DISTORTION PAIR (MNPl
`ARRAY OF N ELEMENTS
`
`CALCULATE LOCATION
`OF MERGE COLOR
`IN NxN MATRIX
`
`FOR EACH ELEMENT
`IN MOP ARRAY EQUAL
`TO A MERGED COLOR~
`RECALCULATE MDP
`
`CALCULATE MINIMUM
`DISTORTION MATE FOR
`THE MERGED COLOR ~
`STORE IN MOP ARRAY
`
`UPDATE MOP ARRAY TO
`DETERMINE IF MERGED
`COLOR IS THE MINIMUM
`DISTORTION MATE FOR
`ANY ffiLOR
`
`YES
`
`Vedanti Systems Limited - Ex. 2020
`Page 5
`
`

`
`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 4 of 4
`
`5,459,486
`
`/
`
`[3
`
`l03
`
`(
`
`IJ(L3)
`
`I
`
`I
`
`I
`
`t:X2,3)
`
`0(3,3)
`
`0(4,3)
`
`• • •
`
`I
`
`I
`
`I
`
`0( 3, n*k)
`
`I
`
`I
`
`I
`
`0(4,n*k)
`
`C I
`
`0(1 I I)
`
`0( 2, l )
`
`0( 3,1)
`
`0(4,1)
`
`[1
`
`[2
`
`(3
`
`(4
`
`Cs
`•
`•
`•
`C ( n*k )-1
`
`0( 5, l)
`•
`•
`•
`0( ( n*k )-l, I )
`
`0(1,2)
`
`0( 2,2)
`
`[)(3,2)
`
`0( 4,2)
`
`0<5,2)
`
`I
`
`0( ( n*k )-!, 2)
`
`I
`
`I
`
`I
`
`0( 5, n*k)
`0(5,3)
`•
`•
`•
`•
`•
`•
`0( ( n*k )-1, 3) • .. 0( ( n*k )-L n*k)
`
`FIG.5
`FIG. 6
`
`MATE COLOR
`
`c 1
`[2
`
`[3
`
`[4
`
`[5
`•
`•
`•
`C ( n*k )-!
`
`C n*k
`
`[3
`
`[ 1
`
`[4
`
`c5
`
`[ n*k
`
`I
`
`•
`
`I
`
`[50
`
`[4
`
`/
`
`105
`
`MIMIMUM
`DISTORTION
`m L3 l
`
`0( 2, 1)
`
`0( 3,4)
`
`0(4,5)
`
`0( 5, n*k)
`•
`•
`•
`0( ( n*k )-1, 50 )
`
`Vedanti Systems Limited - Ex. 2020
`Page 6
`
`

`
`5,459,486
`
`1
`METHOD AND APPARATUS FOR
`COMBINING PALETTES OF COLOR
`QUANTIZED IMAGES
`
`FEDERAL FUNDING STATEMENT
`
`This invention was made with government support under
`grant numbers MIP-9110508 and MIP-9257587 awarded by
`the U.S. National Science Foundation. The U.S. government
`has certain rights in the invention.
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent 15
`disclosure as it appears in the public Patent and Trademark
`Office file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`BACKGROUND OF THE INVENTION
`
`2
`megabytes of expensive VRAM are required.
`Color-mapped display subsystems differ from full-color
`display subsystems by trading resolution to reduce memory
`needs. Specifically, resolution and memory requirements are
`5 decreased by restricting the image on a screen to a palette of
`a fixed number of colors. The conventional 8-bit color(cid:173)
`mapped display subsystem uses a 256-color palette. For
`colors having 18-bit resolution the palette color-map table
`requires 4608 bits. For colors having 24-bit resolution the
`10 color-map table requires 6144 bits. A full color look-up
`table, however, requires space for 262,144 potential 18-bit
`colors or 16.7 million potential 24-bit colors.
`To achieve high image quality or efficient image manipu(cid:173)
`lation or substitution, a color-mapped subsystem requires
`effective palette selection and effective pixel mapping. If a
`palette is selected ineffectively or pixels are mapped inef-
`fectively, poor image quality is observed.
`Typically, palette selection is performed when an image is
`scanned into a computer system. Alternatively, a utility
`20 program converts a full-color image into an 8-bit color(cid:173)
`mapped image. The color-mapped image is stored as a
`256-color palette and an image bit-map of 8-bit indexes.
`Each index points to a color in the palette. When the image
`is to be displayed, the palette is loaded into a color-map table
`25 hardwired or integral to a video processor. The image
`bit-map then is output with each stored index value pointing
`to a color to be generated at the corresponding pixel.
`Following are background sections on palette selection
`techniques and pixel mapping techniques. Thereafter, the
`30 palette management problem is defined.
`Palette Selection Techniques
`Given a picture with potentially millions of colors in it,
`how does one select and distribute a color map of 256 colors
`that are representative of the original image so that it looks
`"right" when viewed only with those colors in the color map.
`According to one common method, histogram clustering, it
`is assumed that the most significant colors will tend to
`cluster together when their lower order bits are truncated. A
`histogram of these reduced colors shows occurrences of the
`reduced colors. The 256 colors with the highest histogram
`values are taken as a representation of the colors in the
`image.
`A more effective approach is vector quantization. Accord-
`ing to vector quantization, palette selection is a data com(cid:173)
`pression problem. The potentially millions of colors in the
`original picture are compressed to a representative set of 256
`colors. Vector quantization is described generally in "Vector
`Quantization;" by Robert M. Gray, IEEE ASSP Magazine,
`50 April 1984. Vector Quantization as applied to image com(cid:173)
`pression is described in "A New Vector Quantization Clus(cid:173)
`tering Algorithm" by William H. Equitz, IEEE Transactions
`on Acoustics, Speech and Signal Processing , Vol. 37, No. 10,
`October 1989. Vector Quantization as applied specifically to
`55 palette selection is described in (1) "A New Approach to
`Palette Selection for Color Images;" by Balasubramanian et
`al.; Journal of Imaging Technology, Vol. 17, No. 6, Decem(cid:173)
`ber 1991; and (2) "Color Quantization of Images;" by
`Orchard, et al.; IEEE Transactions on Signal Processing,
`60 Vol. 39, No. 12, December 1991. According to the vector
`quantization methods, an RGB image is analyzed as a set of
`3-dimensional vectors (each vector representing a pixel
`comprising 3 phosphors-red, green and blue). Palette
`selection then is the vector quantization problem of choosing
`65 an optimal 8-bit codebook of 256 vectors which effectively
`compresses a given image's potentially millions of colors
`down to 256 colors.
`
`35
`
`This invention relates to a method and apparatus for
`displaying color image data. More particularly this invention
`relates to a computer which executes palette management
`software for servicing run-time demands for displaying
`multiple images simultaneously. Respective palettes for the
`images are combined in real time, while minimizing image
`degradation.
`The use of color image data is a growing trend in personal
`and workstation computing. Until recent years, the hardware
`needed to achieve adequate image quality and image
`manipulation performance has been prohibitively expensive
`for the typical personal computer or workstation user. The
`introduction of less expensive color-mapped display sub(cid:173)
`systems has led to the development of many color image
`applications. Following is background information on color
`display subsystems, palette selection techniques, pixel map(cid:173)
`ping techniques and palette management techniques. The
`inventive subject matter herein is directed toward improved
`palette management techniques in a color-mapped display 40
`subsystem.
`Color Display Subsystems
`Color monitors are capable of displaying images at a
`specified resolution (e.g., 1280xl024; 1024x768). The
`1280x1024 resolution monitor, for example, displays an
`image using 1280 rows of pixel elements by 1024 columns
`of pixel elements. The illuminated pixels are perceived in
`total as a color image. In a color monitor each pixel is
`composed of three smaller elements (called phosphors): one
`red, one green and one blue. The color of the pixel is
`determined by mixing the individual intensities of the red,
`green and blue (RGB) phosphors. In a computer environ(cid:173)
`ment, a digital signal drives the display to define the RGB
`intensities of each pixel. Each pixel is driven to define one
`of some finite number of colors as determined by an internal
`representation of an image within a computer's display
`hardware. Most display subsystems represent colors inter(cid:173)
`nally as 24-bit, 18-bit or 16-bit numbers. Often the bit
`pattern comprises subsets of the R, G and B components
`comprising the pixel color. For example, a 16-bit color often
`is represented by 5 bits of the red component, 6 bits of the
`green component and 5 bits of the blue component. An
`image occupying the entire display on a 16-bit color sub(cid:173)
`system could require 1280x1024x16 bits of memory. A
`system storing an entire image in a buffer at maximum
`resolution is a full-color display subsystem. To achieve the
`high resolution of a full-color display subsystem, many
`
`45
`
`Vedanti Systems Limited - Ex. 2020
`Page 7
`
`

`
`5,459,486
`
`4
`IEEE Transactions on Signal Processing, Vol. 39, No. 12,
`December 1991; Orchard et a!. describe pixel mapping
`techniques for improving image quality. According to an
`"ordered dithering" technique, a pseudo-random noise pat(cid:173)
`tern is added to blocks of pixels before quantizing them.
`According to an "error diffusion" technique, the image is
`quantized to have an average value substantially equal ~o the
`average value of the true image. In effect, these techniques
`allow a larger total squared error so that average color of the
`displayed and original images can be closely matched.
`The Palette Management Problem
`The problem of how to deal flexibly with color-mapped
`images has limited the potential of imaging applications on
`8-bit display subsystems. (By 8-bit display subsystem, it is
`15 meant color-mapped display subsystems using an 8-bit
`index into a k-color palette (e.g., 256-color) of j-bit colors
`(e.g., 18-bit color resolution, 24-bit color resolution). For
`example, the task of simultaneously displaying two images
`with different palettes on an 8-bit display subsystem is so
`formidable that most applications and user interfaces do not
`allow such capability. Conventional applications displaying
`two images use the palette from one image to display the
`other. The image quality of the other image typically suffers
`from unacceptable levels of distortion. Accordingly, there is
`a need for a technology which effectively manages palettes
`from multiple images to enable simultaneous display of a
`plurality of minimally-distorted color quantized images.
`
`SUMMARY OF THE INVENTION
`
`3
`Equitz describes the generalized Lloyd algorithm of
`Linde, Buzo and Gray (also referred to as the LBG ~¥o­
`rithm) for defining a codebook based on a set of trrurung
`vectors (e.g., an initial set of pixel colors forming the ~~lor
`image). A starting codebook is selected, then each trrurung 5
`vector (pixel color) is assigned its best fit based on a
`distortion measure. Next, for a given subset of vectors
`assigned to a code, the code is modified to minimize the
`distortion error among the vectors assigned to it. Iterations
`occur of assigning vectors based on fit and modifying the 10
`vectors to minimize error. A weakness of Lloyd's algorithm
`is that the selection of the initial codebook impacts the final
`result. Equitz proposes a pairwise nearest neighbor (PNN)
`algorithm to select the initial codebook, or alternatively, as
`a substitute for Lloyd's algorithm.
`Equitz describes a full search version and an alternative
`fast search version of PNN clustering. Pairs of clusters are
`progressively merged based on minimizing weighted dis(cid:173)
`tance between cluster centroids. The full search PNN algo(cid:173)
`rithm begins with a separate cluster for each vector in the 20
`image and merges two clusters at a time until the desired size
`vector codebook is achieved. For the fast-search version
`Equitz uses a data structure known as a K-d tree to reduce
`the scope of searching to O(log N) choices by subdividing
`the training set into "neighborhoods" and only considering 25
`merging vector pairs having centroids in the same neigh(cid:173)
`borhood.
`Balasubramanian eta!. describe an application ofEquitz's
`clustering vector quantization technique for palette selec(cid:173)
`tion. Initial image colors form a training set of sample 30
`vectors. Pairwise nearest neighbor (PNN) clustering of the
`initial sample vectors then is performed until the number of
`vectors equals the desired number of output codewords.
`Cluster centroids are chosen to be output centroids. Clusters
`are merged to minimize means squared error between vee- 35
`tors. PNN searches are implemented using K-dirnensional
`trees. A prequantization step partitions RGB space into
`cubes. Centroids of colors in each cube are treated as the
`sample vectors. Image-dependent activity criteria determine
`the size of the cubes and weight intercluster distances to 40
`improve visual quality.
`Orchard et a!. describe a binary tree algorithm for parti(cid:173)
`tioning clusters. Total squared-error, weighted total squared(cid:173)
`error and erosion-based weighting are criteria applied for
`improving quantization. A gamma-based corrected coordi- 45
`nate system is used for computation, and L,a,b and L,u,v
`coordinate systems are proposed as alternative coordinate
`systems.
`An alternative to the recursive bipartitioning methods of
`Equitz, Balasubramanian et a!., and Orchard et a!., is pro-
`posed in "Color Quantization by Dynamic Programming and
`Principal Analysis;" Xiaolin Wu, ACM Transactions on
`Graphics, Vol. 11, No. 4, October 1992. Wu proposes
`partitioning based on halfplanes set normal to a principal
`axis along which color points have maximum variance.
`Quantization is carried out in L*u*v space.
`Pixel Mapping Techniques
`Once a palette is selected, the pixels forming an image are
`mapped to the palette. Each pixel value of the original image 60
`is compared to the palette colors. An 8-bit index to a color
`in the palette closest to the original color is assigned to each
`pixel. By using 8-bit values for each pixel rather than 24 bits
`or 18 bits, the image consumes approximately one-third the
`memory of a full-color display subsystem.
`Selection of one of the 256 colors in the palette is referred
`to as pixel mapping. In "Color Quantization of Images;"
`
`50
`
`55
`
`According to the invention, a computer system including
`a color-mapped display subsystem combines palettes of
`multiple images into a single shared palette. Requests for the
`simultaneous display of multiple images using a shared
`palette are serviced in real time. Alternatively images are
`redefined using a shared palette and stored for later recall.
`During palette selection of a given image, the image
`receives a degree of distortion as 256 colors are selected to
`represent the potentially millions of colors in the true image.
`It is an object of the invention to minimize further distortion
`when modifying the palettes to define a shared palette for
`displaying the images simultaneously.
`According to one aspect of the invention, the colors
`included in the palettes are redefined into a set of 256 colors.
`To do so, colors are merged to redefine a color which
`minimizes distortion. In a preferred embodiment colors are
`merged two at a time.
`According to one aspect of the invention, an efficient
`distortion measure is used to select which colors among the
`multiple palettes are combined when defining a shared
`palette. It is known to measure distortion using variations in
`color defined by RGB components (i.e., in an RGB cartesian
`coordinate space). However, variations in RGB color space
`do not correlate well to variations perceived by the human
`eye. Thus, an alternative reference space is used-the YIQ
`(or YUV) color space defined by the NTSC color television
`standard. YIQ space variations have a stronger correlation to
`variations perceived by the human eye. Also, YIQ space is
`a linear transform of RGB space. Thus, centroids of vectors
`in YIQ and RGB space are the same. All calculations other
`than distortion remain in RGB color-coordinate space to
`take advantage of the convenience of using the RGB
`orthonormal, cartesian-coordinate space. The distortion
`65 measure used as a decision criteria in combining colors is the
`mean-squared error distortion measure of gamma-corrected
`values defined in YIQ space.
`
`Vedanti Systems Limited - Ex. 2020
`Page 8
`
`

`
`5,459,486
`
`s
`
`5
`According to another aspect of the invention, a pairwise
`nearest neighbor (PNN) technique is used for combining
`palette colors. Palette combination is modeled as a vector
`quantization problem. Respective palettes are taken as an
`initial vector training set of256*n color vectors, (where n is
`the number of image palettes being combined and 256 is the
`number of colors forming a palette). The 256*n vectors are
`compressed into a single 256-color palette. To enable run(cid:173)
`time application, the maintenance of K-d trees as taught by
`Equitz, Orchard et al. and Balasubramanian et al. during
`palette selection are avoided. It was found that maintenance
`of K-d trees requires an undesirably high constant searching
`time factor in combining vectors. The method of this inven(cid:173)
`tion, which addresses palette management, instead defines a
`matrix of distortion values for each vector pair.
`For a final 256-color shared palette, up to 256 (n-1)
`individual vector merges are performed (where n is the
`number of image palettes being combined). At each step,
`two vectors are chosen that yield the lowest increase in
`distortion when merged. Out of O(N2
`) pairs to merge, where
`N=n*k, searching time at each step is reduced to O(N). 20
`Because distortion value are stored in the matrix, the need
`for extensive recalculation of vector pair distortions between
`merge steps is substantially reduced. Reducing the search
`time and recalculation of distortion pairs at each step results
`in an efficient combining method operable in real time. 25
`Efficiency is further enhanced because distortion calcula(cid:173)
`tions are cached between merge steps.
`According to another aspect of the invention palettes for
`respective images are combined at run-time or are pre(cid:173)
`combined to form a shared palette. When pre-combined, 30
`each image is stored as a new image using the shared palette.
`The multiple images subsequently are recalled for simulta(cid:173)
`neous display.
`The most distinct advantage of the invention is the ability
`to service run-time demands for the simultaneous display of 35
`multiple images on a personal computer or workstation
`platform having an 8-bit color-mapped display subsystem.
`Previously, multiple images simultaneously displayed have
`used the palette of one of the images. Embodiments of this
`invention produce multiple images of better quality because 40
`an optimal shared palette is defined.
`The aspects and advantages of the invention will be better
`understood by reference to the following detailed descrip(cid:173)
`tion taken in conjunction with the accompanying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`6
`memory 14, multiple communication busses 16, 18, 20 and
`several system components and peripherals. According to
`preferred embodiments, the computer system 10 is a work
`station, personal computer, or any of several other standard-
`ized and proprietary general purpose or embedded micro(cid:173)
`computers. Embodiments of the invention may be hosted on
`many alternative single or multiple microprocessor-based
`computer system architectures, including proprietary and
`open-standard work stations, IBM-compatible personal
`10 computers, PENTIUMTM machines, APPLE MACIN(cid:173)
`TOSHTM machines, and other microcomputer machines cur(cid:173)
`rently available or to come based on the Intel 80X86
`architecture, Motorola 68XXX architecture, other CISC
`processor architectures, and oncoming RISC processor and
`15 multiprocessor architectures. Operating system and environ(cid:173)
`ment platforms include DOS, Windows, OS/2, System VII,
`UNIX and other open or proprietary platforms. In alternate
`embodiments the computer system 10 may comprise a
`minicomputer or a mainframe computer system architecture.
`The number and types of communication busses, system
`components and peripherals may vary. For the system 10
`shown, there is a processor bus 16, I/0 bus 18 and local bus
`and/or expansion bus 20. The CPU 12 and system memory
`14 (e.g., external cache and system RAM) are located on the
`processor bus 16. The I/0 bus 18 is linked to the processor
`bus 16 for interfacing to I/0 ports. A printer 22, keyboard 24
`and pointing device 28 (e.g., mouse) typically are coupled to
`the I/0 bus 18 via I/0 ports (not shown).
`A local bus and/or expansion bus 20 are linked to the
`processor bus 16 via a bus interface 30. Exemplary local
`busses are the video local (VL) or VESA-standard bus, the
`peripheral component interface (PCI) bus and the NU-B US.
`The PCI bus, for example, may couple up to 10 peripheral
`devices. Illustrated are a display subsystem 32, audio sub(cid:173)
`system 34, CD-ROM 36 and controller 38, and floppy drive
`40, hard drive 42 and drive controller 44. Typically an
`expansion bus is linked to the processor bus 16 via the local
`bus 120.
`Color-Mapped Display Subsystem 32
`FIG. 2 shows a color-mapped display subsystem 32
`interfaced to the computer system 10. The display subsystem
`32 controls the output of video signals to a display device 46.
`Typical display devices include cathode ray tubes (CRTs), or
`45 LED-based, transistor-based, or plasma-based display pan(cid:173)
`els. The subsystem 32 includes a display device 46, video
`processor 48, buffer 50, VRAM 52 and video DAC (digital
`to analog converter) 54. A color-map table 56 is formed by
`storage elements integral or hard-wired to the video proces-
`50 sor 48.
`The video processor 48 receives commands from the host
`to define an operating mode or to process graphical com(cid:173)
`mands. Image data is input from the host into a buffer 50 via
`the bus 20. The data is then routed into video RAM (VRAM)
`52 by the video processor 48. Alternatively, the host maps
`the image data directly into VRAM 52.
`According to a color-mapped display subsystem, an
`image is defined by a palette and a bit-map. Typically, the
`palette is formed by a set of 256 j-bit colors. Common
`display systems are 16-bit, 18-bit or 24-bit colors systems.
`18-bit and 24-bit colors are the most common for 8-bit
`color-mapped display subsystems. The bit-map is formed as
`a set of 8-bit indexes into the palette. Each element in the
`bit-map corresponds to a pixel of the image to be displayed.
`To generate an image, each element is read from the bit-map
`and mapped to the palette color corresponding to the 8-bit
`index value. The selected color then is generated on the
`
`FIG. 1 is a block diagram of a host computer system for
`implementing an embodiment of the method and apparatus
`of this invention;
`FIG. 2 is a block diagram of a color-mapped display
`subsystem of the computer system of FIG. 1;
`FIG. 3 is a flow chart of a method for servicing a request
`to simultaneously display multiple images on the display
`subsystem of FIG. 2;
`FIG. 4 is a flow chart of a method for combining palettes 55
`of color quantized images according to an embodiment of
`this invention;
`FIG. 5 is a depiction of an NxN matrix of distortion values
`among N=n*k colors; and
`FIG. 6 is a depiction of a minimum distortion pair array 60
`of color pairs according to an embodiment of this invention.
`DESCRIPTION OF SPECIFIC EMBODIMENTS
`
`Host Computer System
`FIG. 1 shows a computer system 10 serving as a host for 65
`implementing an embodiment of this invention. The com(cid:173)
`puter system 10 includes a central processing unit 12, system
`
`Vedanti Systems Limited - Ex. 2020
`Page 9
`
`

`
`5,459,486
`
`8
`the method, each color in each palette is treated as a vector.
`For palettes including 256 colors, a set of "256xn" vectors
`is compressed into 256 vectors, where n is the number of
`palettes to be combined (and also, the number of images to
`5 be simultaneously displayed). Iterations are executed during
`which two colors of similar appearance are merged into one
`color. Eventually enough colors are merged to shrink the set
`to 256 colors. Such set is the shared palette. To select which
`two colors are merged, distortion between colors are derived
`1 o and the color pairs offering minimal distortion are combined.
`The distortion measurement is described below.
`
`DISTORTION MEASUREMENT
`
`25
`
`40
`
`7
`display for such pixel When all the pixels are "painted," an
`image is perceived.
`The subsystem 32 receives the image data bit-map and
`palette from the host. The palette is loaded into the color(cid:173)
`map table 56. The bit-map is loaded into VRAM 52. A
`stream of index data is processed by mapping the indices to
`the palette. Addressed palette colors are output to the DAC
`54 as a stream of digital color signals. The DAC 54 converts
`the digital color signals into standard analog output signals
`(e.g., RGB signals) for driving the display device 46.
`In one embodiment, palettes of multiple images are com(cid:173)
`bined by the host system lO's CPU 12. The shared palette
`then is loaded into the display subsystem 32 in place of the
`predefined palette. According to another embodiment, how(cid:173)
`ever, multiple images and respective palettes are received by 15
`the display subsystem 32 before the palettes are combined.
`The video processor 48 combines the palettes to define a
`shared palette which is stored in the color-map table 56.
`Palette combination as a feature of the video processor 48 is
`embodied as a fixed mode, a selectable operating feature/ 20
`mode, or simply a video command transmitted by the host
`CPU 12.
`Procedure for Displaying Multiple Images
`FIG. 3 shows a flow chart of the procedure for servicing
`a run-time request for simultaneously displaying multiple
`images. According to conventional practices, when an image
`is scanned it is stored in a digital format. For color-mapped
`systems, the scanning software is set to generate a palette of
`colors (e.g., 256 colors) used in displaying the image. The
`image is stored in memory as a bit-map of indexes and a
`palette. Full-color images are converted using conventional
`utility software into 8-bit images (i.e., bit-map of 8-bit
`indexes, plus 256 color palette of j-bit color resolution,
`where j is typically, 16, 18 or 24). Standard image formats
`include TGA, DIB, GIF and TIFF.
`At step 60 a request is made for the simultaneous display
`of multiple images using a combined palette. As the number
`of images to be simultaneously displayed increases, added
`distortion and processing time increases.
`At step 62, the respective palettes for each image are read.
`At step 64, the individual palettes are combined into a shared
`palette according to an embodiment of the method of this
`invention (see FIG. 4 and discussion below in the section,
`Method for Combining Palettes). At step 66, the combined
`palette is loaded into the color-map look-up table 56. At step
`68, a pixel map referenced to the combined palette is
`generated for each image according to conventional pixel
`mapping techniques. At step 70 the pixel map(s) are pro(cid:173)
`cessed to generate RGB signals for simultaneously display-
`ing the multiple images.
`In an alternative embodiment for non-real