`Kim et al.
`
`|||||||||I||
`11)
`5,533,138
`(45)
`Jul. 2, 1996
`
`US0055331 38A
`Patent Number:
`Date of Patent:
`
`54 IMAGE COMPRESSION ENCODING AND
`DECODING METHOD AND APPARATUS
`THEREFOR
`
`Primary Examiner-Stephen Chin
`Assistant Examiner Timothy J. May
`Attorney, Agent, or Firm-Robert E. Bushnell
`
`75) Inventors: Yong-Kyu Kim, Seoul, Rep. of Korea;
`Tianmin Liu, Lawrenceville; Steven T.
`Jaffe, Freehold, both of N.J.;
`Christopher H. Strolle, Glenside, Pa.
`73 Assignee: SamSung Electronics Co., Ltd.,
`Kyungki-do, Rep. of Korea
`
`(21) Appl. No.: 239,848
`(22 Filed:
`May 9, 1994
`Related U.S. Application Data
`
`63 Continuation of Ser. No. 851,019, Mar. 13, 1992, aban
`doned.
`Int. Cl. ................................ H04N 7/12: G06K 9/36
`(51
`52 U.S. Cl. .......................... 382/232; 348/403; 348/422;
`358/.433
`58) Field of Search ............................... 382/56; 348/403,
`348/422; 358/.430, 429, 431,432, 433,
`262.
`
`56
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,845,559 7/1989 Labit et al. ............................. 358/133
`5,047,852 9/1991 Hanyu ..................................... 358/141
`5,051,840 9/1991 Watanabe et al. ........................ 382/56
`5,121,216 6/1992 Chen et al. ............................... 382/56
`5,122,875 6/1992 Rachaudhuri et al. ................. 358/141
`OTHER PUBLICATIONS
`R. M. Gray, "Vector Quantization”, Apr. 1984, pp. 4-26
`IEEE ASSP Magazine, 1, No. 2.
`Lee et al., “A study on New DCT-Based Bit Rate Reduction
`Algorithm and Variable Speed Playback for a Home-Use
`Digital VCR'', Aug. 1992, pp. 236-242.
`Yashima et al., "HDTV/Standard TV Compatible Coding
`Based on DCT", 1990.
`
`ABSTRACT
`57
`Television images to be digitally recorded are divided into
`blocks and the discrete cosine transform DCT of each block
`is taken. The DC coefficient of each DCT block is scalar
`quantized, and its AC coefficients are classified-vector
`quantized (CVO). The square of the value that part or all the
`AC coefficients among horizontal AC coefficients including
`a first AC coefficient and vertical AC coefficients including
`a second AC coefficient, according to the zigzag scanning
`sequence of DCT block, are subtracted from a representative
`value of a preset reference class. Using a multilevel com
`pression method, lowest level codes are vector-partitioned
`by P-units at equal intervals with respect to each classified
`DCT block, and code books of representative vectors cor
`responding to the partitioned vectors are provided. Indices
`of corresponding representative vectors in respective code
`books and the classified codes are taken as encoding data
`corresponding to AC coefficients to keep a constant number
`of bits in the lowest level codes. Then, errors created in a
`preceding level are corrected. Code books of S-units of
`representative vectors corresponding to the errors are pro
`vided again, and corresponding indices and parity data in the
`respective code books are provided. Here, codes are output
`in which an image is more compactly compressed in lower
`levels, and higher levels have more elaborate picture quality.
`During tape recording, the codes descriptive of the scalar
`quantized DC term, the classification of the AC terms and
`the lowest-level vector-quantization index for each succes
`sive DCT block are grouped together for recording in a
`respective one of regularly spaced equal-length segments of
`the recording tracks. Decoding is performed in the reverse
`sequence of encoding. During a high speed search, only
`lowest level codes having a constant number of bits are
`decoded regardless of the complexity of the picture, so that
`picture quality is good enough to discern the nature of the
`images.
`
`20 Claims, 4 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`BUFFER
`
`20
`
`Solai
`
`DC COD
`
`CASSFER
`
`CLASS CODE
`
`t
`
`
`
`1st LEVELCODE
`
`
`
`INTRA
`FRAME
`VECTOR
`ALLOCATOR
`
`i
`
`Amazon / WAG Acquisition
`Exhibit 1017
`Page 1
`
`
`
`U.S. Patent
`
`Jul. 2, 1996
`
`Sheet 1 of 4
`
`5,533,138
`
`30
`
`O
`
`20
`
`41
`
`DC COD
`
`CLASS COD
`
`CODE BOOK
`
`
`
`
`
`
`
`V
`
`
`
`
`
`
`
`1st LEVEL VO
`
`1st LEVELCODE
`
`60
`CODE BOOK g- 2.
`
`2nd LEVEL VO
`
`CODEBOOK
`
`
`
`3rd LEVEL VO
`
`INTRA
`FRAME
`VECTOR
`ALLOCATOR
`
`2nd LEVELCOD
`:
`
`3rd LEVELCOD
`
`50
`PRECEDING FRAME
`IMAGE INFORMATION DETERMINER
`
`FIG. I.
`
`Amazon / WAG Acquisition
`Exhibit 1017
`Page 2
`
`
`
`U.S. Patent
`
`Jul. 2, 1996
`
`Sheet 2 of 4
`
`5,533,138
`
`
`
`DC
`
`AC
`
`Ž33 EgBSE: Pig
`41-61611s as as a
`T,111s 2.2442
`1611, also as also
`1823. 38445153
`Yalala, assos.sg
`25 as as as also sale
`Fasla, assels, see
`
`
`
`
`
`Amazon / WAG Acquisition
`Exhibit 1017
`Page 3
`
`
`
`U.S. Patent
`
`Jul. 2, 1996
`
`Sheet 3 of 4
`
`5,533,138
`
`
`
`ONÅS
`
`Amazon / WAG Acquisition
`Exhibit 1017
`Page 4
`
`
`
`U.S. Patent
`
`Jul. 2, 1996
`
`Sheet 4 of 4
`
`5,533,138
`
`DC CODE
`
`110
`
`21
`
`CLASS CODE
`
`CODE BOOK
`
`122
`
`127
`
`St CODE
`
`1st LEVEL VQ
`
`--
`to 129
`
`CODEBOOK
`
`LEVEL VQ
`
`CODE BOOK
`
`
`
`3rd LEVEL VQ
`
`2nd CODE
`
`
`
`
`
`3rd CODE
`
`
`
`NORMAL TRICK
`
`FIG. 5
`
`140
`50
`IDCT - BUFFER
`
`30
`
`MODE SELECTOR
`
`Amazon / WAG Acquisition
`Exhibit 1017
`Page 5
`
`
`
`5,533,138
`
`1.
`IMAGE COMPRESSION ENCOOING AND
`DECODING METHOD AND APPARATUS
`THEREFOR
`
`This is a continuation of application Ser. No. 07/851,019,
`filed 13 Mar. 1992 now abandoned.
`
`5
`
`2
`It is another object of the present invention to provide an
`image compression decoding method and apparatus therefor
`which records, on magnetic tape, codes produced by a
`multilevel compression method which more compactly
`compresses lower levels of image to output a result having
`a constant number of bits and outputs an encoded result
`having components leading to more elaborate picture quality
`in higher levels, and decodes only the lowest level codes in
`a special playback mode such as a high speed search
`differently from a normal playback mode where the entire
`codes are decoded, thereby enabling a special playback
`function.
`To accomplish the objects, in the image compression
`encoding and decoding method and apparatus therefor of the
`present invention, DC coefficients of a DCT block are
`scalar-quantized and AC coefficients are classified-vector
`quantized (CVO). Respective DCT blocks are classified by
`the least value of the square of the value that part or all of
`the AC coefficient among horizontal AC coefficients includ
`ing a first AC coefficient according to the zigzag scanning
`sequence of a DCT block, and vertical AC coefficients
`including a second AC coefficient are subtracted from a
`representative value of a preset reference class. Using the
`multilevel compression method, lowest level codes are
`vector-partitioned by P-units at equal intervals with respect
`to each classified DCT block, and code books of represen
`tative vectors corresponding to the partitioned vectors are
`provided. Indices of corresponding representative vectors in
`respective code books and the classified codes are provided
`as encoding data corresponding to AC coefficients to keep a
`constant number of bits. Then, errors created in a preceding
`level are obtained. Code books of S-units of representative
`vectors corresponding to the errors are provided again. The
`multilevel CVO of the method providing corresponding
`indices and parity data in the respective code books is
`performed to be encoded. Here, codes are output in which an
`image is more compactly compressed in lower levels, and
`higher levels have more elaborate picture quality.
`Decoding is performed in the reverse sequence of encod
`ing. During a high speed search, only the lowest level codes
`having a constant number of bits are restored regardless of
`the complexity of the picture so that a high speed search
`does not lead to deterioration of picture quality.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The above objects and other advantages of the present
`invention will become more apparent by describing in detail
`a preferred embodiment of the present invention with ref
`erence to the attached drawings in which:
`FIG. 1 is a block diagram of a video compression coder
`according to the present invention;
`FIG. 2 illustrates DC and AC coefficients of an 8 by 8
`DCT block;
`FIG. 3 illustrates a classification in the classifier for the
`video compression coder of FIG. 1;
`FIGS. 4A and 4B illustrate a tape format for the video
`compression coder of FIG. 1; and
`FIG. 5 is a block diagram of a video compression decoder
`according to the present invention.
`DETAILED DESCRIPTION OF THE
`INVENTION
`In FIG. 1, Y, R-Y, and B-Y video signals (4:2:2) input
`from a signal input source are subsampled with respect to a
`chrominance difference signal by a buffer 10 to be changed
`
`BACKGROUND OF THE INVENTION
`The present invention relates to an image compression
`encoding and decoding method and apparatus therefor, and
`more particularly to an image compression coding and
`decoding method and apparatus therefor which, using a
`multilevel compression method, reproduces pictures without
`degradation of picture quality during a special playback such
`as a high speed search.
`Recently, video information compressing technology has
`been used in processing a video signal as digital data in
`digital video apparatus such as digital VCR, HDTV, digital
`video camera and video phone.
`Since known image compression technology has a vari
`able number of compressed coding bits according to picture
`complexity, a problem has been raised about how to keep
`constant a compression result in digital VCRs, HDTVs and
`others which require a constant compression result. Espe
`cially, for image compression for a DVCR, since its record
`ing medium is magnetic tape which enables only sequential
`recording and playback, it has more limitations than that of
`an ordinary transmission line or disk (CD or hard disk). The
`most serious problem to be solved is a special playback
`function (also known as trick play) such as a high speed
`Search.
`For a solution, when an image compression method and
`its tape format are selected, movement of the VCR head
`(head's scan trace) during recording and playback should be
`considered. In other words, for special functions such as a
`high speed search, during compression, each image should
`be exactly the same size, and a portion of data on a tape
`should correspond to the image's original screen position
`and be reproduced regardless of other images.
`Generally however, during coding, a complicated portion
`of an image requires a relatively large amount of bits and a
`simple portion relatively few bits. Accordingly, when video
`signals corresponding to one picture or its one segment are
`to be encoded and recorded in a track having a limited length
`of magnetic tape, and if the number of encoded bits exceed
`one track, a conventional digital VCR method records the
`excess of the encoded bits in a next track or, if the encoded
`bits reach the number of set bits, stops coding the remaining
`part which is discarded.
`However, the recording method of the excess of the
`encoded bits in a next track has difficulty in a special
`playback or high speed search, and the coding stop method
`deteriorates the quality of a reproduced picture because of
`partial loss of its picture information.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`SUMMARY OF THE INVENTION
`Therefore, it is an object of the present invention to
`provide an image compression coding method and apparatus
`therefor which, using a multilevel compression method,
`more compactly compresses lower levels of an image to
`output a result having a constant number of bits and outputs
`an encoded result having components leading to more
`elaborate picture quality in higher levels, so that one picture
`has a constant bit rate.
`
`60
`
`65
`
`Amazon / WAG Acquisition
`Exhibit 1017
`Page 6
`
`
`
`5,533,138
`
`3
`into the form of 4:2:0. That is, the form of 4:2:2 represents
`Y (width: 720 pixels, length: 480 pixels), R-Y and B-Y
`(width: 360 pixels, length: 480 pixels), while the form of
`4:2:0 represents Y (width: 720 pixels, length: 480 pixels),
`R-Y and B-Y (width: 360 pixels, length: 240 pixels).
`A DCT block 20 divides the two-dimensional video signal
`output from buffer 10 into N by N blocks (e.g., 8 by 8) and
`DCT-transforms each block to generate DCT coefficients. A
`DC encoder 30 scalar-quantizes (SQ) the DC values of DCT
`block 20 by eight bits and, for decoding, records them on
`tape.
`A classifier 41 selects part or all the AC coefficient k
`among a horizontal AC coefficient including a first AC
`coefficient according to the ZigZag scanning sequence of a
`DCT block and vertical AC coefficient including a second
`AC coefficient (here, x01 and y10). As shown in FIG. 3,
`edge direction is detected according to the minimum value
`of the square of the value from which representative values
`Yi of eight reference classes preset in the horizontal, verti
`cal, diagonal and its opposing diagonal directions, are sub
`tracted. According to the detected results, each DCT block
`is classified into eight classes. In other words,
`class = C, Yo e min dis(YiX)
`(0s is 7)
`
`10
`
`15
`
`Here, K(k) is a constant, det P is a correlation determi
`nant, and N is a uniform probability in case of DC or a
`Laplacian probability in case of AC.
`In the above equations, as value o’ becomes smaller,
`value D1 (distortion) becomes smaller. Therefore, in order to
`reduce the value of geometric dispersion og, the vector is
`partitioned because, when the values of the vector consist of
`both low-frequency components and high-frequency com
`ponents of the DCT block, the value og’ becomes smaller.
`The present invention is composed of three vectors to
`improve picture quality by about 2dB.
`When a code vector having little error is selected, all 128
`vectors are usually compared, which requires a considerable
`amount of operation. Thus, here, in order to reduce the
`amount of operation, all the vectors of code books 42, 44,
`and 47 are sorted according to a mathematic statistical value
`such as an activity or dispersion value. In other words, the
`search area of the code books is reduced to one quarter of
`their original search area by the mathematic statistical value
`such as the activity of vector or dispersion value so as to also
`reduce the amount of operation to one quarter.
`A first level code, which is the output of a first level vector
`quantization block 43, is compressed to /16. During special
`playback such as a high speed search, only the first level
`code is reproduced. During normal playback, the first level
`code is reproduced along with a higher level code. Even only
`with the first level code, image can be obtained. When
`recorded on tape, as shown in FIGS. 4A and 4B, the first
`level code is recorded on an independent decodable code
`(IDC) region. The code has a total of 21 bits where each
`vector has seven bits, and decoding requires at least 32 bits
`(8 DC bits+3 class bits+21 vector bits).
`Second and third code books 44 and 47 each have seven
`components and 128 vectors. A first subtracter 45 subtracts
`an encoding result in first level vector quantization block 43,
`that is, the vectors of first code book 42 corresponding to
`selected indices, from the whole AC coefficients of DCT
`block 20 except its DC, to determine the errors produced
`during the lowest level encoding of each DCT block 20.
`A second level vector quantization block 46 vector par
`titions the errors produced during the lowest level encoding
`of each DCT block 20 into nine vectors, by equal-interval
`sampling. A second subtracter 48 subtracts an encoding
`result in the second level vector quantization block 46 from
`the AC coefficients of the errors produced during the lowest
`level encoding of each DCT block 20, as supplied from the
`subtracter 45, to determine remnant errors after the second
`level encoding, for encoding in third level vector quantiza
`tion block 49. In other words, image cannot be reproduced
`only with the second and third level vector codes but should
`be necessarily reproduced along with the lowest level code.
`Meanwhile, a parameter determiner 50 determines an
`encoding parameter of the image of a current picture, based
`upon an encoding result of the video signal of a preceding
`picture. As the encoding result of a preceding image, if the
`number of required bits are smaller than that of reference
`bits set for one frame, the value of the parameter is con
`trolled to require a larger number of bits in encoding a
`current image, and if the number of required bits is larger
`than that of the reference bits set for one frame, the value of
`the parameter is controlled to require a smaller number of
`bits in encoding a current image. Here, data transmission
`
`20
`
`k
`dis(YiX) = 2 (yi - xii)
`i
`
`X = (V,H)
`
`vertical AC coefficient. W= i lyiOl
`
`(1 s is 7)
`
`AC coefficient H = : lyOil
`1=0
`
`(yi0: AC coefficient)
`
`In other words, each DCT block is classified into a most
`approximate class by the V and H values on the coordinates
`of FIG. 3. Here, value j is more favorable as it becomes
`larger but may be selected according to the complexity of
`classifier 41. For decoding, these class codes are recorded on
`tape by three bits.
`A first code book 42 contains 21 components and 128
`vectors according to each class. A clustering algorithm
`(LBG algorithm) is used with respect to a transform coef
`ficient relating to edge characteristic, among DCT coeffi
`cients. The LBG algorithm is disclosed in "An Algorithm for
`Vector Quantizer Design,” by Y. Linde, A. Buzo and R. M.
`Gray, IEEE Trans.on Comm., vol. COM-28, pp. 84-95, Jan.
`1980.
`A first level vector quantization block 43 selects a code
`vector having the smallest error by comparing DCT input
`vectors with vectors of the code book, and outputs addresses
`that are indices of the vector as 7-bit compressed codes.
`In other words, the input DCT blocks are vector-parti
`tioned by equal interval sampling to form three vectors. That
`is, as shown in FIG. 2, an 8 by 8 DCT block is zigzag
`scanned and one-dimensionally arranged as follows.
`VECTOR 0-(0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36,
`39, 42, 45, 48,51,54, 57, 60)
`VECTOR 1=(1,4,7,10, 13, 16, 19, 22, 25, 31, 34, 37, 40,
`43, 46, 49, 52, 55, 58, 61)
`VECTOR2=(2,5, 8, 11, 14, 17, 20, 23, 26, 32,35, 38, 41,
`44, 47, 50, 53,56, 59,62)
`This is based upon "Asymptotic Performance of Block
`Quantizer with Difference Distortion Measure,” by Y.
`Yamada, S. Tazaki and R. M. Gray, IEEE Trans. inform.
`Theory, Vol. IT-26, pp. 6–14, Jan. 1980. Here, the reason the
`vectors are partitioned is to reduce the distortion of vector
`quantization. The whole distortion is as follows.
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Amazon / WAG Acquisition
`Exhibit 1017
`Page 7
`
`
`
`5,533,138
`
`5
`speed M of DVCR is 20 megabits per second (Mbps). As one
`second needs 30 frames, the number b of reference bits for
`one frame is b=M/30. In other words, if the difference
`between the required bits and reference bits is larger than a
`preset value, the parameter is determined considering the
`number of the reference bits by the vector distribution
`according to its activity.
`An intraframe vector allocator 60 adaptively allocates
`vectors by the parameter determined by parameter deter
`miner 50.
`Even if the number of vectors to be encoded in second and
`third level vector quantization blocks 46 and 49 is 18, since
`only about nine vectors are allowed to be encoded consid
`ering the number of reference bits, only vectors having an
`activity above a proper size (threshold value) are actually
`encoded. The activity of each vector is defined as follows.
`7
`activity = f lyil
`
`(yi: vector component)
`
`10
`
`15
`
`20
`
`25
`
`30
`
`6
`A first level vector inverse-quantization block 122 outputs
`a corresponding vector component by comparing a first level
`code and the code of code book 121. The decoding result of
`the first level code and the DC coefficients are supplied to a
`first adder 127. Second and third level vector inverse
`quantization blocks 124 and 126 output a corresponding
`vector component by the comparison of second and third
`level codes loaded on the DDC area and the codes of code
`books 123 and 125. The decoding results of the second and
`third level codes are supplied to a second adder 128.
`Meanwhile, according to a normal/trick playback control
`signal for indicating whether a VCR is in a normal playback
`or special playback mode, a mode selector 130 supplies the
`outputs of second and third level vector inverse-quantization
`blocks 124 and 126 to a third adder 129, during normal
`playback. During a trick playback such as high speed search,
`since only the lowest level code is reproduced according to
`the VCR characteristic and the higher level codes are not
`reproduced, mode selector 130 supplies a null signal to third
`adder 129.
`Third adder 129 adds the DC and the decoding results of
`the respective levels, and an inverse-DCT block 140 inverse
`DCT transforms the added outputs to be converted into an
`original two-dimensional video signal. A buffer 150 changes
`the inverse-DCT result into an output form, that is, changes
`the result of 4:2:0 form into 4:2:2 form.
`As described above in detail, the image compression
`encoding and decoding method and apparatus therefor of the
`present invention compresses DCT blocks by steps, using
`classified vector quantization via a multilevel compression
`method so that, during a special playback mode such as high
`speed search, only the lowest level image having a fixed
`number of bits is reproduced to cause no degradation of
`picture quality during the special playback mode.
`While the invention has been particularly shown and
`described with reference to preferred embodiments thereof,
`it will be understood by those skilled in the art that various
`changes in form and details may be made therein without
`departing from the spirit and scope of the invention as
`defined by the appended claims.
`What is claimed is:
`1. An image compression encoding method for a video
`signal that describes a sequence of television image frames,
`some of said television image flames including images of
`objects having edges that are directed in various directions,
`said image compression encoding method comprising:
`a discrete-cosine transform generation step wherein each
`said television image frame is segmented into a plu
`rality of closely packed non-overlapping image blocks
`arranged in rows and in columns, each said image block
`being of prescribed height and width dimensions, por
`tions of the video signal descriptive of each said image
`block being transformed to a respective two-dimen
`sional discrete cosine transform block, each said dis
`crete cosine transform block being composed of a
`respective plurality of coefficients each manifested as a
`respective electrical signal, one of said coefficients
`being a direct-current coefficient and the others of said
`coefficients being alternating-current coefficients in
`two-dimensional spatial frequency;
`a scalar quantization step for scalar quantizing the direct
`current coefficient of each said discrete cosine trans
`form block, thereby generating a respective direct
`current code for each said discrete cosine transform
`block, each said respective direct-current code having
`exactly n bits therein;
`a classification step for classifying the alternating-current
`coefficients of each said discrete cosine transform block
`
`Here, the threshold value (parameter:THR) is determined
`by the encoding state of a preceding image, that is to say,
`transfer vectors from second and third level vector quanti
`zation blocks 46 and 49.
`Transfer Vector=Vij, (jeActj>THR), (0sjs8)
`Though the bits of the second and third level encoding
`codes are fixed in one frame, they can be varied in units of
`a sync block. In other words, as shown in FIG. 4A, one
`frame has four tracks and one sync bloc has six DCT blocks.
`The sync block comprises a sync signal for indicating the
`beginning and end of the block, an index signal for indicat
`ing a position in a frame, a first level quantization encoding
`code contained in an IDC area, an error correction code
`(ECC) for error-correcting the code loaded on the IDC area,
`the plurality of vector quantization encoding codes con
`tained in a dependent decodable code (DDC), and an ECC
`35
`for error-correcting the code loaded on the DDC area.
`If the required number of bits exceeds the reference
`number of bits, the amount of bits in the periphery of the
`image is forced to be cut. The image on the periphery is
`reproduced only with the lowest level code. This means that
`the center and the periphery of the image are encoded using
`different weights. This is possible because normal human
`vision will concentrate mainly on the center of an image.
`Higher level codes are sequentially recorded on the DDC
`area shown in FIGS. 4A and 4B when recorded in tape. The
`second level needs parity data of 9-bit parity data and the
`third level needs parity data of the number of bits of actual
`transfer vectors of the second level. The parity data indicates
`to a decoder which vector is actually recorded on a tape.
`Here, without intraframe vector allocator 60, the reference
`bits are satisfied by only using differential encoding accord
`ing to weights and by image sections. Good picture quality
`can be obtained even if the image is divided into a plurality
`of levels from the center to the periphery, so that the lowest
`level is uniformly encoded and higher levels are encoded by
`varying their parameters for each level.
`From now on, the image compression decoding method of
`the present invention will be briefly described below. The
`decoding method is performed by the reverse order of the
`image compression coding method.
`In FIG. 5, a DC decoder 110 inverse-scalar-quantizes an
`8-bit DC code reproduced from a tape, and decodes it with
`DC coefficients. A first code book 21, which is the same as
`code book 42 of FIG. 1, has 21 components and 128 vectors.
`Second and third code books 123 and 125, which are the
`same as code books 44 and 47 of FIG. 1, each have 7
`components and 128 vectors. Each code book 121, 123 and
`125 outputs its vector according to an input class code.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Amazon / WAG Acquisition
`Exhibit 1017
`Page 8
`
`
`
`5,533,138
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`7
`as belonging to a selected one of m classes, thereby
`generating a respective class code for each said discrete
`cosine transform block;
`a first-level vector quantization step for approximating a
`vector formed from the classified alternating-current
`coefficients of each said discrete cosine transform block
`with a selected one off first-level approximation vec
`tors prescribed for each class, and identifying the
`selected one of said first-level approximation vectors
`by a respective first index having exactly g bits therein,
`said selected first-level approximation vector providing
`an approximation of said vector formed from the clas
`sified alternating-current coefficients of each said dis
`crete cosine transform block with no more error than
`any other of said first-level approximation vectors
`prescribed for said selected class, said respective first
`index having exactly g bits and being supplied as a
`first-level code for each said discrete cosine transform
`block, the direct-current code and the class code and the
`first-level code for each said discrete cosine transform
`block together forming an independently decodable
`code having a number B of encoding bits that is a
`positive integer equal to the quantity n+(log2m)+f g or
`the closest positive integer rounding upward from said
`quantity, f, g, m, and n being positive integers of
`predetermined respective values so that the number B
`is unchanging;
`a step of determining after each said first-level vector
`quantization step on one said discrete cosine transform
`block whether a first prescribed amount of permissible
`vector-quantization error is exceeded by a first-level
`error vector that is defined by all the alternating-current
`coefficients of said one discrete cosine transform block
`decremented by corresponding ones of the alternating
`current coefficients of the first-level approximation
`vector selected in said first-level vector quantization
`step on said one said discrete cosine transform block;
`a second-level vector quantization step of approximating
`each said first-level error vector that exceeds said first
`prescribed amount of permissible vector-quantization
`error with a selected one of a plurality of second-level
`approximation vectors prescribed for said selected
`class, said selected second-level approximation vector
`providing an approximation of said first-level error
`vector with no more error than any other of said
`second-level approximation vectors prescribed for said
`selected class, and identifying said selected second
`level approximation vector with a respective second
`index, thereby generating a second-level code for each
`said discrete cosine transform block the respective
`first-level error vector of which exceeds said first
`prescribed amount of permissible vector-quantization
`error, said second-level code depending for its decod
`ing on the first-level code for the same discrete cosine
`transform block and being included in a dependently
`decodable code for said same discrete cosine transform
`block;
`a step of determining after each said second-level vector
`quantization step on one said discrete cosine transform
`block whether a second prescribed amount of permis
`sible vector-quantization error is exceeded by a second
`level error vector that is defined by all the alternating
`current coefficients of said one said discrete cosine
`transform block decremented by corresponding ones of
`the alternating-current coefficients of the first-level
`approximation vector selected in said first-level vector
`quantization step on said one said discrete cosine
`
`45
`
`50
`
`60
`
`65
`
`8
`transform block and further decremented by corre
`sponding ones of the alternating-current coefficients of
`the second-level approximation vector selected in said
`second-level vector quantization step on said one said
`discrete cosine transform block;
`a third-level vector quantization step of approximating
`each said second-level error vector that exceeds said
`second prescribed amount of permissible vector-quan
`tization error, with a closest one of a plurality of
`third-level approximation vectors prescribed for said
`selected class, said selected third-level approximation
`vector providing an approximation of said second-level
`error vector with no more error than any other of said
`third-level approximation vectors prescribed for said
`selected class, and identifying said selected third-level
`approximation vector with a respective third index,
`thereby generating a third-level code for each said
`discrete cosine transform block the respective second
`level error vector of which exceeds said second pre
`scribed amount of permissible vector-quantization
`error, said third-level code depending for its decoding
`on the first-level code and the second-level code for the
`same discrete cosine transform block and being
`included in said dependently decodable code for said
`same discrete cosine transform block; and
`an intra-frame vector allocation step of determining prior
`to encoding each next television image frame the
`quantity of bits by which the result of encoding an
`immediately preceding television image frame
`departed from a number of bits prescribed for each
`television image frame, and using that quantity as an
`error signal in a degenerative feedback subroutine that
`adjusts at least one of said first and second prescribed
`amounts of permissible vector-quantization error dur
`ing encoding of said next television image frame, for
`controlling the number of bits said second-level and
`third-level vector quantization steps together contribute
`for inclusion in said dependently decodable codes
`within each successive television image frame;
`said image compression encoding method included within
`a method using a helical-scanning tape recorder for
`tape recording a digital electric signal representative of
`said discrete cosine transform blocks on a tape along
`parallel tracks crossing a surface of said tape at a
`prescribed skew angle,
`in which said method for tape recording said digital
`electric signal, successive independently decodable
`codes generated for each said discrete cosine transform
`block by said scalar quantization, classification and
`first