(12) United States Patent
`Miller et al.
`
`USOO6327304B1
`(10) Patent No.:
`US 6,327,304 B1
`(45) Date of Patent:
`Dec. 4, 2001
`
`(54) APPARATUS AND METHOD TO DIGITALLY
`COMPRESS VIDEO SIGNALS
`
`(75) Inventors: Daniel B. Miller; Victor Yurkovsky,
`both of New York, NY (US)
`(73) Assignee: The Duck Corporation, New York, NY
`(US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(22) Filed:
`
`(21) Appl. No.: 09/353,864
`y
`- - -
`9
`Jul. 15, 1999
`Related U.S. Application Data
`O
`(62) Division of application No. 08/060.613, filed on May 12,
`1993.
`(51) Int. Cl." ................................................... H04N 7/12
`(52) U.S. Cl. ......................................................... 375/240.12
`(58) Field of Search ............................ 348/409; 358/403;
`375/240, 240.23, 240.12
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`5,136,376 * 8/1992 Yagasaki et al. ............... 375/240.23
`
`* cited b
`cited by examiner
`
`Examiner-Chris Kell
`Pri
`rimary Examiner
`rIS Kelley
`Assistant Examiner Allen Wong
`(74) Attorney, Agent, or Firm-Levisohn, Lerner, Berger &
`LangSam
`(57)
`
`ABSTRACT
`
`A method and apparatus is disclosed for digitally compress
`ing video signals. The method and apparatus provides a
`System which generates values related to the differences
`between respective pixel locations in an X, y pixel display.
`The differences generated between proximate pixel loca
`tions are used to generate various delta Values which are
`encoded in an asymmetric fashion. The asymmetric coding
`eliminates artifacts in the displayed image, and the delta
`encoding is performed in both a horizontal and vertical
`direction. Errors due to the compression process are distrib
`uted randomly in both horizontal and vertical directions,
`approximating the effect of analog media Such as Video and
`especially film.
`
`5,083,214 * 1/1992 Knowles .............................. 358/403
`
`2 Claims, 7 Drawing Sheets
`
`ENCODE PROCESS DAGRAM
`
`ANALOG INPUT
`
`
`
`20
`
`A/D CONVERTER
`
`OPTIONAL CORRECTION
`
`18
`DIGITAL INPUT
`
`
`
`DEFFERENCE CENERATOR
`
`AVo
`SYMBOL GENERATOR
`
`S
`LOSSESS STATISTICAL
`ENCODER
`
`
`
`46
`E
`STORAGE/TRANSMISSION
`DEVICE
`
`ASYMMETRIC
`QUANTIZER
`
`
`
`D/A CONVERTER
`DISPLAY DEVICE
`
`48
`
`IPR2018-01413
`Sony EX1009 Page 1
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 1 of 7
`
`US 6,327,304 B1
`
`PRE-ENCODE PROCESS DAGRAM
`
`10
`
`12
`
`14
`
`
`
`DETERMINE
`RANDOM
`DEVIATIONS OF
`SYSTEM
`
`SELECT CODNC
`PARAMETERS TO
`MATCH
`DECODING
`RANGE
`
`ENCODE
`DATA
`
`FIG. 1
`
`IPR2018-01413
`Sony EX1009 Page 2
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 2 of 7
`
`US 6,327,304 B1
`
`ENCODE PROCESS DAGRAM
`ANALOG INPUTh20
`
`A/D CONVERTER-22
`
`18
`DIGITAL INPUT
`
`OPTIONAL CORRECTION -24
`
`DIFFERENCE GENERATOR
`
`26
`T
`
`ASYMMETRIC
`QUANTIZER
`
`AVo
`SYMBOL CENERATOR - 42 isities."
`S
`T
`LOSSLESS STATISTICAL
`ENCODER
`
`
`
`ONE LINE T DELAY
`FOR VERTICAL
`40
`
`
`
`54
`
`E
`
`46
`
`SORCE/IESMSON optional correction
`D/A CONVERTERL48
`DISPLAY DEVICE
`
`FIG. 2
`
`IPR2018-01413
`Sony EX1009 Page 3
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 3 of 7
`
`US 6,327,304 B1
`
`DECODE PROCESS DAGRAM
`
`STORAGE/TRANSMISSION
`DEVICE
`
`60
`
`E.
`LOSSLESS
`DECODER
`
`62
`
`S
`
`SYMBOL TO DELTA
`CONVERSION
`
`64
`
`AVd
`
`66
`Vp
`
`7
`
`68
`
`ONE CYCLE V DELAY
`
`th- (HORIZONTAL)
`vo /
`one LINE t DELAY-72
`ADDER
`(VERTICAL)
`
`O
`OPTIONAL GAMMA/7
`CORRECTION
`
`D/A CONVERTER
`
`76
`
`ANALOG DISPLAY
`TRANSMISSION DEVICE
`
`78
`
`FIG. 3
`
`IPR2018-01413
`Sony EX1009 Page 4
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 4 of 7
`
`US 6,327,304 B1
`
`INPUT PIXEL (CORRECTED)
`|
`TOP PIXEL (DECODED)
`T
`OUTPUT PIXEL (DECODED)
`O
`PREVIOUS VERTICAL DIFFERENCE
`Vp
`NEW VERTICAL DIFFERENCE(INPUT)
`Vi
`VERTICAL DIFFERENCE
`Vo
`AVo DELTA BETWEEN Vp AND Vi
`AVd QUANTIZED DELTA
`S
`CODED SYMBOL
`E
`LOSSLESS-ENCODED BITSTREAM
`
`FIG. 3A
`
`IPR2018-01413
`Sony EX1009 Page 5
`
`

`

`U.S. Patent
`US. Patent
`
`Dec. 4, 2001
`
`Sheet 5 0f 7
`
`US 6,327,304 B1
`US 6,327,304 B1
`
`
`
`an;
`
`$1
`
`8+“;
`
`wn+na>
`
`:-u><
`
`Sub
`
`S+us
`
`cine,
`
`in?
`
`Bmmummzoono”.39.;
`
`5:umom+uo><00:.nmwm+no><
`n_ mm3._<>
`
`nnmmunc><
`
`Nnmm+uc><
`
`|PR2018—O1413
`
`Sony EX1009 Page 6
`
`IPR2018-01413
`Sony EX1009 Page 6
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 6 of 7
`
`US 6,327,304 B1
`
`
`
`
`
`1[\d][10WITBOWITBO TWITIOV
`
`Z
`
`9Ç+ | 8+)
`z: | _ ,- (TGFERTO B
`
`b?
`
`IPR2018-01413
`Sony EX1009 Page 7
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 7 of 7
`
`US 6,327,304 B1
`
`
`
`OO
`CO
`
`&
`
`s
`
`IPR2018-01413
`Sony EX1009 Page 8
`
`

`

`1
`APPARATUS AND METHOD TO DIGITALLY
`COMPRESS VIDEO SIGNALS
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`This application is a divisional of prior pending applica
`tion Ser. No. 08/060,613 filed May 12, 1993 and claims the
`priority thereof.
`
`BACKGROUND OF THE INVENTION
`The invention relates generally to a method of and appa
`ratus for coding and compressing information. More
`Specifically, the invention relates to a method for coding and
`compressing digital signal data, Such as digitized video
`images, for Storage and transmission. While the following
`discussion refers to compression of digitized video images,
`it is to be understood that the invention is not restricted to
`Video data, and may produce benefits in other fields where
`compression is used.
`AS the digital revolution has spread to many industries
`and technologies, the need to transmit, Store and manipulate
`large amounts of data has grown. Consequently, there have
`been many attempts to code and/or compress data in order
`to reduce the necessary Storage capacity, transmission rate,
`and processing Speed to perform a given task.
`For example, one of the fields that has recently developed
`a need for intensive digital data handling is Video technol
`ogy. This field includes applications Such as the transmission
`of real time Video over telephone lines for teleconferencing
`and the use of digital video-transmission for home television
`Viewing as well as interactive television and computer
`applications. Presently, there are limitations imposed by the
`quality and available bandwidth of existing transmission
`lines as well as capacity and data throughput of Storage
`devices necessary to Store and transmit image data.
`To reduce the data capacity requirements of Such video
`Systems and/or improve performance of Systems with lim
`ited data capacity, various methods have been devised.
`So-called “lossless' compression methods rely on redun
`dancies within the data, for instance by assigning a single
`code to represent an entire block of data that may repeat
`several times. Other methods are considered “lossy,”
`because Some of the data is lost in the compression/
`decompression process resulting in images that differ from
`the originals. Both methods are useful and practical and are
`commonly used together to create an effective compression
`System.
`In the compression of Video images, known lossy tech
`niques produce undesirable effects in the final decompressed
`image, Such as pixellation and posterization. These undesir
`able effects are known as “artifacts. Pixellation occurs when
`the number of Stored pixels is reduced for the total image,
`i.e., the resolution is decreased, leading to jagged lines and
`Squared-off curves. Posterization occurs when the number of
`values representing pixel brightness and color is reduced.
`For example, typical digitized monochrome video images
`normally have 256 shades of gray. If that number is reduced
`to 16 or 32 for the same image, areas with Smooth shading
`gradations now have regions of uniform Shade, and transi
`tions from one shade to the next are obvious. Other lossy
`techniques, Such as using a low-pass filter to eliminate
`high-frequency noise, also eliminate the high-frequency
`portion of the image, making it muddy and lacking in detail.
`To better preserve the quality of the image, others have
`applied lossleSS compression methods. However, when the
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,327,304 B1
`
`2
`process necessarily includes analog components (cameras,
`tape equipment, etc.), these methods are overkill. Any
`analog component, even the analog-to-digital (A/D) con
`verters used to digitize an image, will add a certain amount
`of noise to the digital data captured, and this amount of noise
`varies from System to System. LOSSleSS compression meth
`ods compress, transmit and decompress this noise
`accurately, along with the "good' data, at great expense in
`Storage and processing requirements. Some complex and
`noisy images can even be larger in their “compressed form
`than when not compressed with Some methods.
`Unfortunately, there is no obvious way to determine what is
`noise and what is data once the digital Signal is produced; to
`the System, it is all data. It is possible, although complicated,
`to use various forms of “dithering with filtered data to add
`a Somewhat random or pseudo-random aspect to the repro
`duced image, hopefully ameliorating Some of the effects of
`filtering and posterization. Often, these methods involve the
`addition of a separate machine generated random Signal
`during compression and/or decompression. Of course, this
`requires many additional components and method steps,
`driving up the costs and Slowing down maximum processing
`Speeds.
`One relatively simple compression Scheme well known in
`the art is called "delta encoding”. Although primarily used
`in compression of digitized audio signals, Several attempts
`have been made to apply the principle to the compression of
`image data. In delta encoding, a Series of data values are
`encoded as a first value and a Series of differences, or deltas,
`between each value and the next Subsequent value. Delta
`encoding holds advantages when used in conjunction with
`lossleSS compression means Such as Huffman coding, known
`in the art, which take advantage of the Statistical frequency
`of values in a Series to achieve data compression. The
`advantage of delta encoding arises from the fact that the
`frequency distribution of the differences between Subse
`quent values in a Series is often much leSS uniform than the
`distribution of the actual values, and in many cases this
`provides Substantial gain in the compression of Such data.
`So far, what has been described with delta encoding is a
`lossleSS compression method, in that the decoded values will
`be identical to the encoded values. Limiting the allowable
`delta values which can be encoded to a subset of the possible
`delta Values comprises a lossy compression process known
`as delta quantization. The quantizing function must include
`a means of choosing one of the allowable deltas if the actual
`delta is not equal to any of them; a simple and effective rule
`is to choose the allowable delta closest to the actual delta. It
`should be noted that when using delta quantization, the error,
`or difference between the input pixel value and the corre
`sponding decoded value, must be added into the next delta
`prior to quantization; this error is therefore being incorpo
`rated into Subsequently processed pixel values, which is to
`Say the error is being distributed in the direction correspond
`ing to pixel processing. An equivalent way of achieving this
`is to produce each delta not by taking the difference between
`Subsequent pixel values in the original image, but by taking
`the difference between the present pixel value and the last
`decoded pixel value, which is often maintained anyway by
`the compression apparatus for reference display.
`Drawbacks of delta quantization particularly as applied to
`images are: reduced Spatial frequency response,
`posterization, and edge artifacts. Frequency response is
`dependent on the size of the largest allowable delta values,
`posterization results from the choice of the Smallest values,
`and edge artifacts result from both of these factors as well as
`from the fact that previous delta encoding Schemes distribute
`error in a Single Spatial dimension.
`
`IPR2018-01413
`Sony EX1009 Page 9
`
`

`

`US 6,327,304 B1
`
`15
`
`40
`
`3
`Furthermore, the existence of Substantial noise elements
`introduced by the analog components of the Video proceSS
`(including grain from film Sources) reduces the ability of
`delta encoding to produce an image of acceptable quality
`along with Substantial data compression. The reason for this
`is that noise manifests itself primarily in the high-frequency
`domain, which creates a wide distribution of Small differ
`entials between Subsequent data values. The designer of a
`digital Video compression System using delta quantization
`techniques is faced with a dilemma: either allow a large
`number of Small delta Values to be used, resulting in leSS
`compression, or accept noticeable edge and posterization
`artifacts. For this reason, delta encoding for Video compres
`Sion has been limited to use in situations where the level of
`compression needed is Small, or where image quality is not
`of paramount importance (certain computer applications).
`Typically, where high levels of compression must be
`achieved, along with Superior Video quality, more compli
`cated means have been pursued, including discrete cosine
`transform, vector quantization, wavelet, and other tech
`niques known in the art. In addition, Some compression
`Systems as described above which aim at high levels of
`compression use inter-frame and motion estimation
`techniques, which further increase complexity and cost. A
`brief Summary of the features of Such complicated means is
`25
`set forth:
`Vector Quantization (VQ). A highly asymmetrical
`algoritlun often used on PCs. Results in poor quality Video,
`although hardware to play it back can be produced cheaply.
`Vector quantization is computationally intensive on com
`pression.
`Fractal Compression The picture quality is poor, it is even
`more asymmetrical than VO, and it is not possible to
`decompress fast enough to run video.
`35
`Wavelets. This technology is capable of good quality Video
`and is fairly equal in compression and decompression com
`putation requirements, although these requirements are
`mathematically complex.
`Discrete Cosine Transform This is the core of the JPEG
`still image standard and the elusive MPEG standard.
`Although quite complicated, this algorithm provides equal
`compression/decompression requirements and results in rea
`Sonable quality Video. Block artifacts, however, are often
`obvious and annoying.
`45
`MPEG. As a potential standard, this is a version of DCT
`and bidirectional motion estimation. However, it is very
`complicated, highly computation-intensive for compression,
`and produces both Spatial and temporal artifacts.
`VQ is undesirable on the quality basis. The rest of the
`above technologies are prohibitively expensive for incorpo
`ration into mass-market consumer devices. MPEG in par
`ticular is undesirable because of the huge computational
`requirements necessary to achieve acceptable image quality.
`The problems associated with noise are not solved by
`these Systems; they merely manifest themselves in other
`ways than with delta encoding Schemes. Complex filtering
`processes and quantization of frequency components can
`increase compression levels by reducing noise, but often
`create artificial-looking results and introduce artifacts Such
`as texture baldness. Inter-frame and motion estimation tech
`niques exacerbate the problem, causing artifacts Such as
`blockineSS and frozen noise.
`
`50
`
`4
`with high levels of compression and is simple and cost
`effective to implement and manufacture. Rather than use
`complex mathematical techniques which require equally
`complex apparatus to implement, and which, in the opinion
`of many in the business of producing and distributing
`recorded and transmitted Video material, produce unaccept
`able results at prohibitive cost, the inventors have combined
`a novel form of delta encoding with a method of image
`analysis to create a process that closely approximates the
`characteristic appearance of analog image processes, espe
`cially film. In this way, the visual effect of the compression
`process is Similar, and perhaps Superior to, the effects of the
`analog process being replaced, whether it be video tape
`recording, motion picture film, or Video transmission via
`broadcast or other means. Further, the compression and
`decompression processes can be performed relatively
`quickly So as to yield real time “on the fly' digital com
`pression and decompression. While Some prior Systems are
`capable of quarter Screen eight frame a Second operation,
`Such Systems produce poor Video quality. The System of the
`present invention is presently capable of full screen 60 fields
`per Second operation that produces excellent Video quality.
`Among the important features of the invention is that the
`Simplicity of the compression/decompression System allows
`for the system to be implemented on a customized ASIC
`(Application Specific Integrated Circuit). The benefits are
`easily visualized.
`An average American family has one or more television
`Sets, a cable converter, a VCR, and possibly a camcorder.
`There may also be a PC, and in the near future a CD-ROM
`device connected to the television Set. That is, at least three
`analog devices per household are ripe for a digital
`replacement, and two more will be expected to provide
`high-quality digital Video.
`The typical thinking today is that Since compression
`technology is complicated and expensive, a decompression
`box should be at the center of the home entertainment
`system, probably in the cable TV box. Since the decom
`preSSor now has to be shared by a number of devices,
`cumberSome Standards are being advanced that propose to
`do everything for everybody. However, with the cost effec
`tive technology of the present invention, the balance is
`different. Each one of the above mentioned video devices
`could have a decompressor built in.
`To draw an analogy, today's household has a tuner in
`every television set, every cable TV box, and every VCR,
`even though typically only one is used. It is simply cheaper
`for the manufacturer to build the tuner into every device than
`to count on the compatibility between different devices and
`guide the consumer through wiring all these devices to share
`One tuner.
`Based on this approach, an advantage of the present
`invention is that it can be implemented on a low cost custom
`ASIC, which could be installed in consumer products.
`Indeed, the present System can be implemented using 100,
`000 gates or less, using low-cost integrated circuit fabrica
`tion techniques.
`In accordance with an object of the invention, a method
`of analysis of the analog components of the Video pathway
`is provided, including the analog-to-digital and digital-to
`analog circuits used, enabling the designer of the System to
`establish an effective range of possible decoded values for
`given encoded values, termed the Decoding Range, relating
`to the noise level inherent in the System.
`Also in accordance with another object of the invention,
`a method and apparatus is disclosed which incorporates a
`
`55
`
`60
`
`SUMMARY OF THE INVENTION
`It is the object of this invention to provide a digital video
`compression process that provides Superior image quality
`
`65
`
`IPR2018-01413
`Sony EX1009 Page 10
`
`

`

`25
`
`S
`novel form of delta encoding, utilizing parameters based on
`the Decoding Range to introduce a pseudo-random element
`to the decoded values while maintaining these values within
`the Decoding Range. There are two novel elements of the
`encoding process, termed ASymmetric Delta Quantization
`and Two-Dimensional Delta Encoding. While they may be
`used Separately with benefit, they work Synergistically to
`satisfy the objects of the invention. To elucidate the descrip
`tion of the invention, there follows a general overview of
`these two novel elements.
`Asymmetric Delta Quantization is similar to Delta
`Quantization, except that certain of the allowable deltas have
`different magnitudes when they are negative than the cor
`responding positive values. This introduces the pseudo
`random element. Typically, the magnitude of the two Small
`est delta values allowed will differ by 1, such as -2 and +1,
`or -3 and +2, corresponding to a Decoding Range of 3 or 5
`respectively. Asymmetric Delta Quantization includes the
`added benefit that the unequal delta Values are chosen with
`non-uniform frequency, which can increase the compression
`level of Subsequent lossleSS compression Such as Hufftnan
`Coding.
`Asymmetric delta encoding may be described in more
`detail as follows. In order to reduce the data transmitted, a
`fixed value, Such as +2, is transmitted for every delta falling
`in the range of 0 to +5 (See FIG. 5). Similarly, the fixed value
`+8 will be transmitted for each delta falling in the range of
`greater than +5 and less than or equal to +14. In the
`traditional delta encoding process, identical fixed negative
`and positive values would be transmitted when the deltas fall
`in the respective negative and positive ranges. With the
`present invention, the lowest positive and negative output
`codes representing the lowest corresponding positive and
`negative ranges are unequal and preferably are different by
`a value of one.
`Two-Dimensional Delta Encoding expands the concept of
`delta encoding to include both horizontal and vertical axes.
`(Alternatively, one dimension could be temporal.) To per
`form delta encoding in both axes simultaneously, we gen
`erate a quantity called the Vertical Differential. The Vertical
`Differential shall be the difference between a given input
`pixel value, and the decoded pixel value directly above it.
`40
`We then perform delta encoding, preferably using ASym
`metric Delta Quantization, on Subsequent Vertical Differen
`tials from left to right for each row of pixels. To begin the
`process, we must record without compression the value of
`the first row of pixels and the first pixel value of each
`Subsequent row. (Alternatively, we can initialize the first row
`and column to a fixed value, as described for the preferred
`embodiment.) By maintaining the value of the decoded
`pixels for each previous row, we effectively distribute error
`downwards as well as to the right (as explained earlier in
`regard to delta quantization, deriving deltas using decoded
`values for previous pixels is equivalent to incorporating an
`error term). In fact, it can be shown that the pseudo-random
`aspect of ASymmetric Delta Quantization, when used in
`conjunction with Two-Dimensional Delta Encoding, causes
`error to be distributed in both vertical and horizontal dimen
`Sions on a random basis with each pixel, creating a film-like
`granular look which is much preferable to the unnatural
`effect of delta encoding in one Spatial dimension. It can also
`be shown that Two-Dimensional Delta Encoding is equiva
`lent in both dimensions; the same result is obtained whether
`We process from left to right in each Subsequent row, or
`choose to proceSS each column from top to bottom-neither
`axis is preferred or emphasized in any way.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The foregoing and other objects, features and advantages
`of the present invention will become apparent to those
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,327,304 B1
`
`15
`
`6
`skilled in the art upon reading the following detailed
`description in conjunction with the appended drawings, in
`which:
`FIG. 1 is a schematic flow chart of a method according to
`the present invention;
`FIG. 2 is a block diagram of a compression System
`according to the present invention, and Table 2A identifies
`certain values which are produced in the system of FIG. 2;
`FIG. 3 is a block diagram of a decompression System
`according to the present invention, and Table 3A identifies
`certain values which are produced in the system of FIG. 3.
`FIG. 4 is a table of input, intermediate, and compressed
`output values for a Subset of pixels from a representative
`image.
`FIG. 5 is a table of representative delta quantization
`parameters with a random deviation of -3 to +2 (decoding
`range of 6), determined at block 14, FIG. 1.
`FIG. 6 is a block diagram of a digital computer run by
`Software which can implement the present invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`For explanatory purposes, and for the purpose of Stan
`dardizing the overall detailed description of the preferred
`embodiment, the analog input Signal will be considered a
`monochrome Video signal, converted into a Stream of digital
`values from a set of 256 possible values, i.e., there are 256
`shades of gray for each pixel or Sample in the Video image.
`It will be further understood that the signal preferably does
`not contain the Video information necessary for the main
`tenance of the Video signal, Such as timing and Synchroni
`Zation signals. These signals would be removed before
`compression, and generated locally during decompression.
`The present invention is concerned with the data portion of
`the Signal or the portion that determines the shades of gray
`at each pixel or Sample. It should also be understood that the
`present invention is not limited to Video signals, but can be
`applied to any analog or digital Signal, although certain
`aspects of the present invention find great advantage for
`Video signals.
`Referring now to the drawings, FIG. 1 shows some of the
`general processes that are used in the practice of the pre
`ferred embodiment of the invention. Initially, it is necessary
`to determine the noise level, or random deviation, inherent
`to the particular analog system in use (block 10). There are
`known methods to determine this deviation, Such as by
`imaging a flat card of one continuous shade. In a perfect
`System, the digitized values would all be the same for the
`entire Video frame; by analyzing the actual Sampled values,
`the random deviation can be determined. For example, if the
`average Sampled value were 100, the individual Samples
`might represent a range of 98 to 102, resulting in a random
`deviation of +/-2. This random deviation indicates the
`acceptable range within which a Sample value must be
`decoded to avoid a noticeable increase in the noise level of
`the image. This decoding range is Supplied to a System (12)
`which is used to Select coding method parameters to match
`the random deviation of the system. The output of system 12
`is Supplied to data encoding block 14, So that these param
`eters are then used to compress the data in block 14.
`The decoding range is not static, however. It can vary
`depending on the level of the Signal and/or the difference
`between values, Such as at an edge between contrasting
`areas. In the preferred System, the range or allowable error
`is also related, in part, to the level of the Signal. Thus, it is
`
`IPR2018-01413
`Sony EX1009 Page 11
`
`

`

`US 6,327,304 B1
`
`15
`
`45
`
`50
`
`25
`
`7
`preferred that the digitized values are processed first through
`a logarithmnic or Similar function So that the decoding range
`will be substantially constant over the entire set of possible
`values, except for edges. (Discussed below, block 24 of FIG.
`2).
`FIG. 2 shows a Schematic functional block diagram of a
`compression System for performing the method of a pre
`ferred embodiment of the present invention and Table 2A
`lists the values to be generated by the system of FIG. 2. The
`image is processed Starting with the top left pixel of the
`image, moving left to right for each row (or line) of pixels,
`and down each row until all pixels have been processed.
`There are two delay blocks; a one-cycle delay that holds the
`previous vertical differential (block38), and a one-line delay
`for the previous row of output pixels (block 40). The
`one-line delay is pre-initialized to a value of 128 (a neutral
`grey on the scale of 0 to 255); the onecycle delay is
`pre-initialized to Zero.
`Initially, a Video Signal containing data is input in Some
`form (block 20), such as a camera, but it could be from any
`known Source, Such as a film Scanner or from Videotape. The
`Signal is then digitized by an analog-to-digital converter
`(block 22). The input signal could also originate at this point
`from a digital Source Such as computer-generated animation
`Sequences. At block 24, a logarithmic or other correction can
`be performed so that the random deviation will be constant
`over the entire range of possible pixel values. A represen
`tative correction function is: c=sqr(u256), where u is the
`uncorrected input pixel value, and c is the corrected value.
`The result of this correction we call I, the Input pixel value.
`At difference generator block 26, a difference is generated
`by subtracting T (the Top pixel value, which is output by the
`one-line delay at block 40) from I. This quantity is called Vi
`(Vertical input differential). At difference generator block
`28, Vp (Vertical previous differential, output by the one
`35
`cycle delay at block38) is subtracted from Vito generate AV
`(delta-Vertical differential).
`At block 30, AV is quantized using Asymmetric Delta
`Quantization, utilizing the parameters generated at block 12,
`of FIG.1. This is accomplished by providing the actual AV
`40
`to coding parameter block 12 which produces an output
`determined by the AV in accordance with the table of values
`shown in FIG. 5. The result, AVd (delta-Vertical, quantized)
`is supplied to both adder block 32 and symbol generator
`block 42. Block 32 Sums Vp and AVd, generating Vo
`(Vertical output differential). At adder block 34, Vo is
`Summed with T to produce O (Output pixel). Vo is also
`Supplied to block 38, the one-cycle delay, for Storage until
`the next horizontal pixel is processed. At block 40 (the
`one-line delay), O is stored for processing the next row of
`pixels. If a correction took place at block 24, an inverse
`correction is performed on O at optional correction block 36.
`A representative inverse correction function would be:
`c=u256/256, where again u is the uncorrected output pixel
`value and c is the corrected value. The output is then Sent to
`a Digital-to-Analog converter (block 48) for display on a
`Video monitor.
`Symbol generator block 42 processes AVd, converting the
`chosen delta value into a symbol S (see FIG. 5), Suitable for
`lossleSS compression at lossleSS Statistical encoder block 44.
`60
`Each delta value has an associated Symbol, and these Sym
`bols may be chosen in Such a way that more frequently used
`Symbols have lower values, for Statistical encoding using a
`modified Huffinan code (run-length encoding and/or other
`means known in the art could be used in conjunction or
`instead). The statistical encoder 44 Supplies an encoded bit
`Stream, E. At Storage/transmission device 46, the encoded
`
`55
`
`65
`
`8
`bit Stream is Saved to a storage device. Alternatively, the bit
`Stream E. could be transmitted for real-time Video applica
`tions Such as television transmission or teleconferencing.
`FIG. 3 shows a schematic functional block diagram of a
`decompression System utilizing the method of a preferred
`embodiment of the present invention, and Table 3A lists a
`table of coded values which are generated at different
`locations on the block diagram of FIG. 3. AS in compression,
`the image is processed Starting with the top left pixel,
`moving left to right and down each row until all pixels have
`been decompressed. The two delay blocks at 68 and 72 are
`pre-initialized to the same value used in compression
`(value=128).
`At Storage/transmission device 60, the encoded bit Stream
`E is retrieved from a Storage device and Supplied to lossleSS
`decoder 62. Alternatively, the bitstream could come from a
`data reception device in a real-time Video transmission
`System. In either case, at lossleSS decoder block 62 the
`bitstream is decoded using lossleSS Statistical decoding
`methods corresponding to the Statistical encoding methods
`used in block 44 (FIG. 2). The lossless decoder Supplies as
`an output the symbol S. At block 64, this symbol is trans
`lated or converted into the corresponding quantized delta
`value, AVd.
`At adder block 66, AVC is summed with Vp from the
`one-pixel delay at block 68, generating Vo. Vo is Stored in
`the one-pixel delay at block 68. At adder block 70, Vo is
`Summed with T (Top pixel), the output from the one-line
`delay at block 72. The output, O, of adder 70 is stored in the
`one-line delay for the next row. If a correction was made at
`block 24 (FIG. 2), an inverse correction is performed at
`optional gamma connection block 74.
`The output is then converted into an analog video signal
`at digital to analog converter block 76 and Sent to