United States Patent 19
`Wittenstein et al.
`
`III USOO573.4744A
`5,734,744
`Mar. 31, 1998
`
`Patent Number:
`11
`45 Date of Patent:
`
`54 METHOD AND APPARATUS FOR
`COMPRESSION AND DECOMPRESSION OF
`COLOR DATA
`
`75) Inventors: Andreas Wittenstein. Lagunitas; Loren
`Carpenter. Novado; Leo Hourwitz, San
`Francisco, all of Calif.
`
`73) Assignee: Pixar, Richmond, Calif.
`
`(21) Appl. No.: 484,345
`22 Filed:
`Jun. 7, 1995
`(51) Int. Cl. .................... G06K9/00
`52 U.S. Cl. ........................................... 382/166; 382/236
`58) Field of Search .................................... 382/166. 236,
`382/239; 358/539, 430; 348/416, 415, 412,
`413
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,654.720 3/1987 Tozawa ................................... 358/283
`5,049,986 9/1991. Aono et al.
`358/523
`5,067,152 11/1991 Kisor et al.
`348/422
`5,263,100 11/1993 Kim et al...
`382/239
`5,467413 11/1995 Barrett .................................... 38.2/236
`5.506,624 4/1996 Moreton ................................., 348/420
`5.508,822 4/1996 Ulichney et al. ...................... 358/456
`
`Primary Examiner-Yon Couso
`Attorney, Agent, or Firm-Hecker & Harriman
`57
`ABSTRACT
`The present invention is a method and apparatus for com
`pressing and decompressing data. In particular. the present
`invention provides a method for compressing color video
`data for storage on a CD-ROM for later playback on a
`computer system. The present invention uses an asymmetri
`cal compression-decompression scheme that provides color
`compression, temporal compression, and spatial compres
`sion. In the preferred embodiment of the invention, the color
`compression is accomplished in three stages. In the first
`stage, the colors are sampled from the source data. This
`generates a histogram that contains the colors of the source
`material. Next, these colors are quantized into the target
`colors. In the third step of the color compression, the actual
`colors on the film are mapped to the quantized colors. The
`temporal compression step specifies a target display rate.
`Only those pixels that have changed significantly from
`frame to frame are updated. A bit mask is generated for each
`frame and is used to target those pixels that will be updated
`for each frame. The spatial compression step is used to
`further reduce storage requirements by dividing data into
`pixel "tiles." The CD-ROM stores an index into the table so
`that when data is required only the index need be provided.
`not the tile.
`
`19 Claims, 14 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`201
`
`
`
`COMPESS COR
`
`24-B
`DIREC-COOP
`EAS IMAGE
`
`24-B
`OIRECT-COOf
`SOURCE IMAGE
`
`200
`
`SAP
`COORS
`
`COOR
`HISOGRAM
`
`GANIZE
`COLOR
`SPACE
`
`COLOR
`QANZR
`
`(LAAFIF
`PXES
`
`
`
`
`
`8-BI
`INDEXED-COLOR
`IES
`ACE
`
`COMPRESS COLOR
`
`-
`8-BI
`NCEXED-COLOR
`44GE
`
`22
`
`IPR2018-01413
`Sony EX1038 Page 1
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 1 of 14
`
`5,734,744
`
`FIG. 1
`
`f 16
`
`f 13
`
`
`
`
`
`
`
`MASS SIORAGE
`
`110
`
`1 11
`
`f 12
`
`
`
`
`
`
`
`
`
`USE CURRENT
`CENIROIDS
`
`CALCULAIE DISIANCE MENRIC
`
`FIG. 6
`
`ASSIGN EACH SAMPLE O NEARESI CENIROID
`
`CAICULAJE AWG OF
`All SAMPLES ASSIGNED 10 CENTROID
`
`
`
`SE7 AVERAGE AS CURRENT CENTROID
`
`603
`
`604
`
`607
`
`IPR2018-01413
`Sony EX1038 Page 2
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 2 of 14
`
`5,734,744
`
`
`
`24-BIT
`DIRECT-COLOR
`SOURCE IMAGE
`
`200
`
`COMPRESS MOWIE
`
`s/ COMPRESS
`JIME
`
`f-BIT
`IILE-MASK
`
`COMPRESS
`SPACE
`
`INDEXED-TILE
`IMAGE
`
`QUANIIZER
`
`COMPRESSED
`MOWIE
`
`IPR2018-01413
`Sony EX1038 Page 3
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 3 of 14
`5,734,744
`FIG. 3
`
`201
`
`COMPRESS COLOR
`
`24-BIN
`DIRECT-COLOR
`BIAS IMAGE
`
`24-BIT
`OIRECT-COLOR
`SOURCE IMAGE
`
`200
`
`SAMPLE
`COLORS
`
`
`
`
`
`
`
`
`
`COLOR
`HISIOGRAM
`
`
`
`QUANIIZE
`COLOR
`SPACE
`
`
`
`COLOR
`QUAWIZER
`
`OUANIIZE
`PIXELS
`
`8-BIT
`INDEXED-COLOR
`IESI IMAGE
`
`
`
`EMPHASIZE: v.
`WSAISFACTOR
`
`8-BIT
`INDEXED-COLOR
`IMAGE
`
`
`
`COMPRESS COLOR
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IPR2018-01413
`Sony EX1038 Page 4
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 4 of 14
`
`5,734,744
`
`
`
`
`
`24-BIT
`DIRECT-COLOR
`SOURCE IMAGE
`
`
`
`200
`
`SAMPLE COLORS
`
`4O1
`
`402
`
`403
`
`SAMPLE
`COLOR
`
`COLOR
`SAMPLE
`
`REDUCE
`SAMPLE
`RAIE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(INFREQUENT)
`COLOR
`SAMPLE
`
`
`
`
`
`404
`
`
`
`
`
`
`
`REDUCE
`COLOR
`PRECISION
`
`405
`
`
`
`impricist) - 406
`COLOR
`SAMPLE
`
`RECORD
`COLOR
`OBSERVATION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 4
`
`COLOR
`HISTOGRAM
`
`408
`
`DECIMATE
`HISTOGRAM
`
`409
`
`SPARSE
`COLOR
`HISTOGRAM
`
`410
`
`COMPRESS
`HISIOGRAM
`
`411
`
`
`
`
`
`
`
`
`
`INDEXED
`COLOR
`HISTOGRAM
`
`SAMPLE COLORS
`
`IPR2018-01413
`Sony EX1038 Page 5
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet S of 14
`
`5,734,744
`
`INDEXED
`COLOR
`HISIOGRAM
`
`302
`
`303
`
`F,| G. 5
`
`OUANIIZE COLOR SPACE
`
`IRANSFORM
`COLORS
`
`
`
`
`
`
`
`PERCEPTUAL
`COLORS
`
`50f
`
`502
`
`INITIALIZE
`- COLOR
`CENIROIDS
`
`
`
`
`
`
`
`
`
`INTIAL
`COLOR
`CENTROIDS
`
`505
`
`
`
`QUAWIZE
`COLORS
`
`in a
`
`REQUANIIZE
`COLORS
`
`
`
`COLOR
`INDICES
`
`CENTROID
`
`DEVIATIONS
`
`COLOR
`CENIROIDS
`
`
`
`ADJUSI
`CENTROIDS
`BUILD COLOR
`QUANIIZER
`
`OUAWTIZE COLOR SPACE
`
`COLOR OUANIIZER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IPR2018-01413
`Sony EX1038 Page 6
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 6 of 14
`
`5.734,744
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`701
`
`FIG. 7
`
`SELECT CENTER
`CENTROID
`
`SELECT CANDIDATE CENTROID
`
`DEIERMINE OCIANT OF CANDIDATE
`
`702
`
`703
`
`704
`
`705
`
`YES
`
`SEI CANDIDAIE AS CURRENT
`CLOSES IN OCIAWT
`
`CAWDIDATE
`CLOSER THAN
`CURRENT CLOSESI
`IW OCANT
`2
`
`707
`
`CREATE TABLE OF NEIGHBORS
`FOR CENIER CENTROID
`
`ALL
`CANDIDAIEN YES
`NEIGHBORS
`EXAMINED
`2
`
`
`
`ALL
`CENIER CENIROIDS
`EXAMINED
`2
`
`
`
`703
`
`YES
`
`END
`
`IPR2018-01413
`Sony EX1038 Page 7
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 7 of 14
`
`5,734,744
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`304
`
`COLOR
`QUANIIZER
`
`
`
`24-BIT
`DIRECT-COLOR
`SOURCE IMAGE
`
`FIG. 3
`
`OUAWIIZE PIXELS
`
`200
`
`
`
`UPDATE
`IEMPORAL
`CACHE
`
`IEMPORAL
`DIHERED-PIXEL
`CACHE
`
`
`
`CHECK
`IEMPORAL
`CACHE
`
`MISS
`
`SPAIAL
`PIXEL
`CACHE
`
`UPDATE
`SPATIAL
`CACHE
`
`CHECK
`SPAJIAL
`CACHE
`
`MISS
`
`OUANIIZE
`COLOR
`
`
`
`
`
`8-BIN
`INDEXED-COLOR
`IMAGE
`
`DIIHERED 8-BIT
`INDEXED-COLOR
`IMAGE
`
`CREATE
`DITHER
`MASK
`
`
`
`
`
`QUANIIZE PIXELS
`
`
`
`
`
`
`
`IPR2018-01413
`Sony EX1038 Page 8
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 8 of 14
`
`5,734,744
`
`()
`
`901
`OBIAIW A PIXEL FROM THE SOURCE IMAGE
`
`FIG. 9A
`
`COMPARE COLOR OF THE OBJAINED PIXEL IO IHE COLOR
`STORED IN THE EMPORAL CACHE AIA LOCATION
`CORRESPONDING TO THE PIXE FRAME LOCATION
`
`902
`
`904
`
`90.3
`
`
`
`IEMPORAL
`CACHE HII
`2
`
`NO
`
`COMPARE THE COLOR OF THE OBJAINED PIXEL
`IO THE COLORS STORED IN THE SPA IIAL CACHE
`
`916
`
`
`
`
`
`IEMPORAL
`CACHE HII
`2
`
`ASSIGN QUAWIZED
`COLOR TO PIXE
`
`CALCULAIE x DISIANCE BETWEEN HE PIXEL AND A QUANIIZED COLOR
`
`906
`
`907
`
`
`
`DISIANCE
`LESS THAN BEST
`FII x DISIANCE
`2
`
`
`
`YES
`
`CALCULATE y DISTANCE BETWEEN THE PIXEL AND THE QUANIIZED COLOR
`
`
`
`
`
`909
`
`Xy
`DISTANCE
`LESS THAN BEST
`FIT y DISIANCE
`2
`
`
`
`YES
`
`
`
`
`
`IPR2018-01413
`Sony EX1038 Page 9
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 9 of 14
`
`5,734,744
`
`FIG. 9C G
`
`910
`
`CAICULAIE. z DISTANCE BETWEEN IHE
`PIXEL AND THE QUANIIZED COLOR
`
`911
`
`
`
`
`
`XVZ
`DISIANCE
`(ESS THAN BEST FIT
`xyz DISIANCE
`2
`
`M-G)
`
`YES
`
`912
`
`SEI CURRENI QUANIIZED COLOR AS BEST FIT
`
`
`
`
`
`All
`QUANIZED
`COLORS, CHECKED
`2
`
`914
`
`GET NEXI OUAWTIZED COLOR
`
`FIG. 9D
`
`
`
`All
`PIXELS
`CHECKED
`2
`
`
`
`IPR2018-01413
`Sony EX1038 Page 10
`
`

`

`Mar. 31, 1998
`200
`
`304
`
`
`
`COLOR
`QUANIIZER
`
`Sheet 10 of 14
`
`5,734,744
`
`8-BIT
`INDEXED-COLOR
`IMAGE
`
`202
`
`COMPRESS TIME
`
`MEASURE AGED
`INDEXED-COLOR
`JILE CHANGES
`
`IILE
`CHANGE
`SAI 1 ENCES
`
`INDEX-SORT
`IILE-CHANGE
`SAIF ENCES
`
`IHRESH AND LIMIT
`IILE CHANGES
`
`
`
`1-BIT
`JILE-MASK
`IESI IMAGE
`
`U.S. Patent
`
`24-BIT
`DIRECT-COLOR
`SOURCE IMAGE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 1 O
`
`1009
`
`
`
`7-BIT
`IILE-MASK
`IMAGE
`
`IPR2018-01413
`Sony EX1038 Page 11
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 11 of 14
`
`5,734,744
`
`
`
`
`
`
`
`
`
`
`
`
`
`IPR2018-01413
`Sony EX1038 Page 12
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 12 of 14
`
`5,734,744
`
`FIG. 12
`
`1200
`
`COMPRESSED MOWIE
`
`BACKGROUND IMAGE
`
`
`
`
`
`DECOMPRESS MOVIE
`
`
`
`
`
`
`COOR BATCH
`
`IILE BAICH
`
`COMPRESSED IMAGE
`
`
`
`
`
`SKIP UNCHANGED
`IILES
`
`DECOMPRESS MOWIE
`
`
`
`
`
`8-BIT INDEXED-COLOR
`IMAGE
`
`1220
`
`IPR2018-01413
`Sony EX1038 Page 13
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 13 of 14
`
`5,734,744
`
`1009
`
`304
`COLOR
`QUANIIZER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1-BIT
`IILE-MASK
`IMAGE
`
`8-BIT
`INDEXED-COLOR
`IMAGE
`
`FIG. 13
`
`UPDATE
`IILE-DISIANCE
`CACHE
`
`IIILE
`DISTANCE
`CACHE
`
`CHECK
`
`---
`
`E" | NERIlf
`DISIANCE
`INDICES
`CACHE
`e-S
`
`UPDATE
`
`IILE
`
`IABLE
`
`
`
`
`
`IILE t
`
`IILE
`QUANIIZER
`
`
`
`
`
`32-BIT
`INDEXED-TILE
`IMAGE
`
`IPR2018-01413
`Sony EX1038 Page 14
`
`

`

`U.S. Patent
`
`Mar. 31, 1998
`
`Sheet 14 of 14
`
`5,734,744
`
`f009
`
`1-BIT
`IILE-MASK
`IMAGE
`
`8-BIT
`INDEXED-COLOR
`IMAGE
`
`2O2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IEMPORAL
`IILE CACHE
`
`
`
`CHECK
`IEMPORAL
`IILE
`CACHE
`
`
`
`SPAIAL
`NILE
`
`UPDATE
`iiMFORAL
`IILE CACHE
`
`UPDATE
`SPATIAL
`IILE CACHE
`
`
`
`
`
`
`
`CHECK
`
`SPAJIAL
`
`t
`
`1301
`
`FIG. 14
`
`MISS
`
`
`
`1,308
`
`CHECK
`IILE-
`DISIANCE
`CACHE
`
`302
`
`f 102
`
`
`
`
`
`IABLE
`On AP
`32-BIT
`INDEXED-IILE
`IMAGE
`
`IPR2018-01413
`Sony EX1038 Page 15
`
`

`

`5,734,744
`
`10
`
`15
`
`25
`
`3.
`
`35
`
`1
`METHOD AND APPARATUS FOR
`COMPRESSION AND DECOMPRESSION OF
`COLOR DATA
`BACKGROUND OF THE INVENTON
`1. Field of the Invention
`This invention relates to the field of compression and
`decompression of data.
`2. Background Art
`Computers are often used to process, play back, and
`display video data. This video data may come from sources
`such as storage devices, on-line services, VCRs, cable
`systems, broadcast television tuners, etc. Video data is
`memory intensive. that is, video data requires large amounts
`of memory for storage and use by a computer system.
`CD-ROMs provide one solution to the problem of storing
`large amounts of data. However, even the storage capabili
`ties of a CD-ROM can be exceeded when storing motion
`picture length video data.
`To reduce the transmission bandwidth and memory
`requirements when working with video data, various com
`pression schemes have been developed so that less storage
`space is needed to store video information and a smaller
`bandwidth is needed to transmit it. Prior art video compres
`sion schemes include Motion JPEG, MPEG-1, MPEG-2,
`Indeo, Quicktime, True Motion-S, CinePak, etc.
`A disadvantage of existing prior art compression schemes
`is their inability to provide adequate quality of playback in
`terms of format (spatial resolution), frame rate (temporal
`resolution) and color fidelity. In addition, the existing prior
`art schemes do not adequately compensate for the low data
`output rate of CD-ROMs. CD-ROMs suffer from a disad
`vantage of having a low data output rate compared to that
`needed for realistic video playback.
`With respect to spatial resolution, many prior art schemes
`do not provide a "full screen" of video output. Here, full
`screen is defined as 640 by 480 color pixels. Many prior art
`compression schemes provide a small "box" that displays
`video data. Such small displays are difficult to view, and do
`not provide adequate playback of video data. Regarding
`temporal resolution, many of the prior art schemes provide
`"choppy" playback of video data, with jerky motion. and
`pauses in playback while new frame data is being generated.
`Many source images include high resolution color infor
`mation. For example, the source image may have a color
`resolution of 15. 24, or 32 bits per pixel. Many computer
`systems are only capable of providing 8 bit per pixel color
`output. This requires that the large number of colors of the
`source image be mapped to a smaller number of colors that
`can be displayed by the computer system. This step involves
`the use of a color look-up table (LUT). Prior art compression
`schemes typically rely on the host computer system to
`provide a color lookup table. These color lookup tables are
`not optimized for the particular source image, so unsatis
`factory color display results.
`Another disadvantage of prior art compression schemes is
`that they are "symmetrical". These schemes attempt to
`compress the data in the same time it takes to display the
`data. Typically, prior art compression schemes compress the
`data in a single pass, in real time or as close to it as possible.
`This limits the performance of prior art compression
`schemes.
`
`45
`
`55
`
`SUMMARY OF THE INVENTION
`The present invention is a method and apparatus for
`compressing and decompressing data. In particular, the
`
`35
`
`2
`present invention provides a method for compressing color
`video data for storage on a CD-ROM for later playback on
`a computer system. The present invention uses an asym
`metrical compression-decompression scheme where the
`compression takes longer than the decompression. The com
`pression of the color video data is optimized so that playback
`of the compressed video data on a computer system more
`closely approximates the original source image.
`The present invention converts 24-bit true color data to
`8-bit categorical color data using color compression. tem
`poral compression, and spatial compression.
`In the preferred embodiment of the invention, the color
`compression is accomplished in three stages. In the first
`stage, the colors are sampled from the source data. This
`generates a histogram that contains the colors of the source
`material. Next, these colors are quantized into the target
`colors. In the preferred embodiment of the present invention,
`the quantizing step yields two hundred and fifty-six colors.
`In the third step of the color compression, the actual colors
`on the film are mapped to the quantized colors.
`The temporal compression step is accomplished by speci
`fying a target display rate. In the preferred embodiment of
`the invention, the target display rate is fifteen frames per
`second for a 640x480, 8-bit color display. This target display
`rate is limited by the display update rate and the reading rate
`from the CD-ROM. To limit the number of pixels that need
`to be updated for each frame, only those pixels that have
`changed significantly from frame to frame are updated. The
`temporal compression step is used to determine which pixels
`change significantly from frame to frame, and therefore,
`need to be updated. A bit mask is generated for each frame
`and is used to target those pixels that will be updated for
`each frame.
`The spatial compression step is used to further reduce
`storage requirements by dividing data into 4x4 pixel "tiles."
`The CD-ROM stores an index into the table so that when
`data is required only the index need be provided, not the tile.
`This allows the tile to be stored once but displayed many
`times, further reducing storage requirements.
`Decompression is accomplished by providing the opti
`mized color table to the display system and mapping the
`colors in the color table to the best colors available on the
`display. This color mapping is done once during loading
`where delays in displaying the first frame of a sequence of
`frames are acceptable. A tile table is also loaded into the
`main memory of the display computer system, and the
`indexes to the tile look-up table are retrieved from the
`CD-ROM for display,
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a diagram of a computer system that may be used
`with the present invention.
`FIG. 2 is an information flow diagram of the operation of
`the present invention.
`FIG. 3 is an information flow diagram of the operation of
`the color compression step of FIG. 2.
`FIG. 4 is an information flow diagram of the operation of
`the color sampling step of FIG, 3.
`FIG. 5 is an information flow diagram of the operation of
`the color quantizing step of FIG. 3.
`FIG. 6 is a process flow diagram of the color quantizing
`step of the present invention,
`FIG. 7 is a process flow diagram illustrating the centroid
`neighbor calculation of the present invention.
`FIG. 8 is an information flow diagram of the operation of
`the pixel quantizing step of FIG. 3.
`
`IPR2018-01413
`Sony EX1038 Page 16
`
`

`

`3
`FIGS. 9A. 9B. 9C and 9D are a process flow diagram of
`the pixel quantizing step of the present invention.
`FIG. 10 is an information flow diagram of the temporal
`compression of the present invention,
`FIG. 11 is an information flow diagram of the spatial
`compression of the present invention.
`FIG. 12 is an information flow diagram illustrating the
`decompression of the present invention.
`FIG. 13 is an information flow diagram illustrating tile
`quantizing.
`FIG. 14 is an information flow diagram illustrating the
`exact match tile step of FIG. 13.
`DETALED DESCRIPTION OF THE
`INVENTION
`A method and apparatus for compression and decompres
`sion of data is described. In the following description
`numerous, specific details, such as number of colors, bits per
`pixel, data read rate, etc. are set forth in order to provide a
`more thorough understanding of the present invention. It
`will be apparent, however, to one skilled in the art, that the
`present invention may be practiced without these specific
`details, In other instances, well known features have not
`been described in detail so as not to unnecessarily obscure
`the present invention.
`In the preferred embodiment of the present invention,
`Source image material consists of computer animated mov
`ies. These movies may be based on three-dimensional ren
`30
`derings and, for purposes of example, consist of 24-bit color
`with 8 bits for red, green, and blue color channels respec
`tively. Although the preferred embodiment of the present
`invention utilizes computer-animated movies, live action
`movies or any other source can be used without departing
`from the spirit and scope of the present invention.
`The present invention can be used for traditional movies
`(i.e. sequential frame access) or interactive movies (random
`frame access). The output computer system of the present
`invention is assumed to be a computer system that supports
`a display format of 640x480, 8-bit indexed color pixels at a
`display rate of approximately 15 frames per second. The
`data is compressed so that a data rate that can be read off a
`double-speed CD-ROM drive in real time is accomplished.
`This system is given by way of example only and other data
`rates, storage devices, color resolutions, etc., can all be used
`with the present invention.
`The present invention implements an asynchronous, mul
`tiple pass compression scheme offering parametric control
`and manual intervention during each phase of operation.
`This permits a degree of artistic and technical control
`designed to optimize and maximize the quality of the
`compressed movie. For comparable image quality, the
`invention reduces computer-intensive, bandwidth-intensive,
`and storage-intensive aspects of prior art video decompres
`sion schemes at the expense of using more resources during
`the compression phase.
`COMPUTER SYSTEM
`The present invention may be implemented on any con
`ventional or general purpose computer system. An example
`of one embodiment of a computer system for implementing
`this invention is illustrated in FIG. 1. A keyboard 110 and
`mouse 111 are coupled to a bi-directional system bus 118.
`The keyboard and mouse are for introducing user input to
`the computer system and communicating that user input to
`CPU 113. The computer system of FIG. 1 also includes a
`
`65
`
`25
`
`35
`
`45
`
`50
`
`55
`
`5,734,744
`
`O
`
`15
`
`4
`video memory 114, main memory 115 and mass storage 112,
`all coupled to bi-directional system bus 118 along with
`keyboard 110, mouse 111 and CPU 113. The mass storage
`112 may include both fixed and removable media, such as
`magnetic, optical or magnetic optical storage systems or any
`other available mass storage technology. In the preferred
`embodiment of the present invention, for decompression, the
`mass storage is a double speed CD-ROM drive. For
`compression, the mass storage should be writable, and
`magnetic disks are used in the preferred embodiment. The
`mass storage may be shared on a network, or it may be
`dedicated mass storage. Bus 118 may contain, for example,
`32 address lines for addressing video memory 114 or main
`memory 115. The system bus 118 also includes, for example,
`a 32-bit data bus for transferring data between and among
`the components, such as CPU 113, main memory 115, video
`memory 114 and mass storage 112. Alternatively, multiplex
`data/address lines may be used instead of separate data and
`address lines.
`In the preferred embodiment of this invention, the CPU
`113 is a 32-bit microprocessor manufactured by Motorola,
`such as the 68030. 68040. or PowerPC. However, any other
`suitable microprocessor or microcomputer, such as the
`80386, 80486, or Pentium microprocessors manufactured by
`Intel Corporation of Santa Clara, Calif., may be utilized.
`Main memory 115 is comprised of dynamic random
`access memory (DRAM) and in the preferred embodiment
`of this invention, comprises 4 megabytes of memory for
`decompression and 16 megabytes of memory for color
`compression. More or less memory may be used without
`departing from the scope of this invention. Video memory
`114 is a dual-ported video random access memory, and in
`this invention consists, for example, of 300 kilobytes of
`memory for decompression and 1.2 megabytes of memory
`for compression. However, more or less video memory may
`be provided as well.
`One port of video memory 114 is coupled via video
`multiplexing shifter circuitry (not shown) to video amplifier
`116. The video amplifier 116 is used to drive the cathode ray
`tube (CRT) raster monitor 117. Video multiplexing shifter
`circuitry and video amplifier 116 are well known in the art
`and may be implemented by any suitable means. This
`circuitry converts pixel data stored in video memory 114 to
`a raster signal suitable for use by monitor 117. Monitor 117
`is a type of monitor suitable for displaying graphic images,
`and in the preferred embodiment of this invention, has a
`resolution of at least 640x480. Other resolution monitors
`may be utilized in this invention.
`The computer system described above is for purposes of
`example only. The present invention may be implemented in
`any type of computer system or programming or processing
`environment.
`
`COMPRESSION
`The compressor of the present invention compresses a
`sequence of full-color images (stored, for example, as 24-bit
`RGB PICT or TIFF files) into a stream of tile store codes.
`skip codes, background codes, and tile display codes. A skip
`code specifies where on the display the next file should
`appear if it is not in sequential scan line order. Abackground
`code specifies how many tiles to copy from the correspond
`ing position in a background image. A tile display code
`specifies which (4x4 pixel) tile of indexed colors from the
`tile table to display at the current tile position. The tile
`display code is converted to an index into a table of indexed
`color tiles. If the movie is an interactive movie, a fixed tile
`
`IPR2018-01413
`Sony EX1038 Page 17
`
`

`

`5
`table is stored at the beginning of the entire movie. For a
`sequential movie, the tile table can be changed and is stored
`dynamically, with a batch of tile store codes at the beginning
`of each frame. The tile store codes specifies which entry in
`the tile table to replace with what tile of the next color pixels.
`The color indices are indices into a color table which, like
`the tile table, is either a fixed color table for a random access
`movie, or a dynamically updated color table for a sequential
`access movie.
`FIG. 2 is a flow diagram illustrating the compression
`scheme of the present invention. The present invention
`begins, in the preferred embodiment, with a sequence of
`24-bit direct color source images 200. The present invention
`then executes a color compression step 201. a time com
`pression step 204 and a spatial compression step 206 to lead
`to a compressed movie 210.
`At step 201, the color compression step, the original
`colors of the source image are quantized using a color
`quantizer 203 to yield 8-bit indexed color images 202. In this
`step, the true colors of the source movie are mapped to some
`number (e.g. 256) of color table values and the pixels of
`each frame are mapped to a quantized color of the color table
`to create an indexed color image.
`Temporal compression 204 is applied to these indexed
`color images to generate one-bit tile mask images 205.
`Temporal compression is used to reduce the number of bits
`that need to be updated in a refresh cycle. Ideally, only those
`pixels that are changed are updated. By identifying only
`those pixels that need to be updated from frame to frame, the
`effective speed of updating is increased.
`Spatial compression 206 uses tile quantization 208 to
`generate 16-bit indexed tile images 207. This reduces the
`display data by defining files in a look-up table and storing
`only the indexes to the tiles in the data stream. In this
`manner, a single tile that may be displayed many times is
`stored only once, and a smaller index to that tile can be
`stored many times in the data stream. The indexed color
`images 202. tile mask images 205, and indexed tile images
`207 are combined at step 209 to generate a compressed
`movie 210.
`
`30
`
`35
`
`COLOR COMPRESSION
`FIG. 3 is an information flow diagram illustrating the
`color compression 201 of the present invention. The color
`compression is accomplished by sampling the colors 301.
`quantizing the color space 303 and then quantizing the
`pixels 305 (i.e. assigning quantized colors to film pixels).
`The 24-bit source images 200 are sampled at the sample
`color step 301 to create a color histogram 302. The histo
`gram is subjected to a quantization step at quantize color
`space 303 to yield a color quantizer 304. The color quantizer
`provides an optimum mapping of the source colors to a
`desired number (i.e. 256) of quantized colors. At quantize
`pixels step 305, each pixel is assigned a color from the color
`quantized table to generate an 8-bit indexed color test image
`306. This test image can be used as the indexed color images
`202 or optional step 307 may be applied. At optional step
`307 unsatisfactory regions can be reviewed and touched up
`to create 24-bit direct color bias images 308 which are
`returned to the color compression process at step 301.
`The sample color step 301, quantize color step 303, and
`quantize pixels step 305 are described in detail below with
`respect to FIGS. 4, 5, and 6 respectively.
`Sample Colors 301
`FIG. 4 is a flow diagram illustrating the method of color
`sampling in the present invention. Essentially, the color
`
`45
`
`55
`
`65
`
`5,734,744
`
`10
`
`5
`
`20
`
`25
`
`6
`sampling consists of generating a histogram of the colors of
`the film. A histogram is a graph that represents the popula
`tion of a plurality of characteristics of a sample set. In this
`case, the characteristics are different colors. A histogram is
`considered to be a series of “bins' where each bin represents
`one of the possible colors. For 24 bit color, there are 2'
`equals 16,777.216 different colors. Therefore, a histogram
`for a 24-bit color sample would have 16,777,216 bins. Each
`bin contains a number representing the number of samples
`(i.e., pixels) in the source material that have the associated
`color.
`In the present invention, the histogram can be generated
`in one of two ways, a full histogram or a reduced histogram.
`For a full histogram, every sample of the source data is
`counted and placed in its appropriate bin. A full histogram
`requires a large amount of memory for storage. If there are
`32 bits (4 bytes) count available for storage of each possible
`color. four (2) equals 64 megabytes of memory required
`for the full histogram. A 4-byte count for each possible color
`value is sufficient to represent 4,294,967,295 pixels
`(samples) of each color value. Adding another byte per bin
`would require approximately 80 megabytes of memory for
`the histogram table.
`The memory required for the histogram may be reduced
`(a reduced histogram) by reducing the sampling frequency,
`The target storage space (i.e., 16 megabytes) is compared to
`the total number of samples in the source film. This ratio is
`used to calculate a sampling frequency rate that will permit
`use of the reduced memory histogram without overflowing.
`The factor of reduction of the sampling rate from full
`sampling rate to new sampling rate is used to determine how
`many pixels will be grouped together to effectuate the lower
`sampling rate. For example, if the sampling rate is reduced
`by 4, the pixels are sampled in groups of 4, and in each
`sample one of the four pixels is pseudo randomly chosen as
`the representative sample of that group of 4 pixels. Code
`illustrating the operation of this stage of the invention is
`illustrated in Appendix 1.
`After the histogram is generated, it may be optionally
`decimated. To decimate the histogram, the histogram is
`examined to determine the number of bins of the 16 million
`plus bins that are in fact populated with observations. In a
`typical film, many of the bins will likely be populated.
`Next, a target number for a fraction of the populated bins
`is selected. For example, consider the case where there are
`one million populated bins in the histogram, and it is desired
`to reduce that number to 100,000. The algorithm of the
`present invention, which is illustrated in the code of Appen
`dix 2, first brackets the decimation fraction to between Zero
`and one, and guesses it to be the target number of colors
`divided by the number of populated bins. In this case, that
`fraction would be one tenth. It then reduces this range and
`revises its guesses by binary search until it finds the deci
`mation fraction that yields the target number of bins, as
`follows: If the decimated bin count would be less than the
`target bin count, then the lower limit is set to just above the
`guessed fraction; otherwise the upper limit is set to just
`below the guessed fraction. In either case, the next guess is
`set to the center of the new range. This test is repeated until
`the decimated bin count reaches the target bin count, at
`which point the histogram is actually decimated at the
`guessed decimation fraction. The histogram is decimated by
`multiplying the population of each populated bin by the
`decimation fraction, resolving fractional populations by
`adding a pseudorandom fraction less than one, and taking
`the integer part. This decimated histogram is then used in
`subsequent processing steps.
`
`IPR2018-01413
`Sony EX1038 Page 18
`
`

`

`5,734,744
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`7
`FIG. 4 illustrates a detailed information flow of the
`sample color step 301 of FIG. 3. At sample color step 401,
`a color of the 24-bit source images 200 is sampled to create
`a color sample 402. If desired, each color in the source
`image can be sampled to create a full histogram of the entire
`source image. Alternatively, a reduced sampling rate 403 as
`described above can be used to generate an infrequent color
`sample 404. Another time and memory saving step is a
`reduced precision step 405 which yields (imprecise) color
`sample 406. At step 407, the color observation is recorded
`i.e., the bin for that color is incremented to create a color
`histogram 408. This color histogram can be used as the
`indexed color histogram 302. Alternatively, the histogram
`may be decimated at step 409 to create a sparse color
`histogram 410. If desired, the full histogram or the sparse
`color histogram can be compressed at step 411 to yield an
`indexed color histogram 302.
`Quantizing The Color Space 303
`After the histogram has been generated and modified if
`desired, the next step is to quantize the color space. The
`purpose of this step is to determine the 256 colors that are
`most optimal for representing the hundreds of thousands or
`millions of colors in the source image file histogram. An
`information flow diagram for accomplishing the quantiza
`tion of the colors is illustrated in FIG. S.
`At step 501, the data from the indexed color histogram
`302 is su