DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-20 are pending in this application.
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed.
Claim Rejections - 35 USC § 112
The following is a quotation of the second paragraph of 35 U.S.C. 112:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 7, 14, and 20 are rejected under 35 U.S.C. 112, second paragraph, as being indefinite for the following reasons.
The following limitations leads to indefiniteness as the term “skp”, “no skp” and “Tx” are not adequately defined or able to be ascertained from the context of the claims:
-- searching for skp data within any Tx data range in the first compressed index table, and determining the skp data as the locator in response to no skp data being found or a frequency of appearance of the skp data being the lowest;
Appropriate correction is required to ensure that the claims are being interpreted and the art is being cited in accordance with the intended scope of the claimed limitations. For purposes of examination, these features were not examined with respect to the prior art.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1, 8 and 15 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Li et al. (US PGPub US 2016/0277760A1, hereby referred to as “Li”).
Consider Claims 1, 8 and 15.
Li teaches:
1. A multi-level compression method for picture data, performed by a server and comprising: / 8. A computer device, comprising: a processor; and a memory, coupled with the processor and storing computer programs; the computer programs, when executed by the processor, are operable to: / 15. A non-transitory computer-readable storage medium, storing computer programs which, when executed by a processor, cause the processor to carry out actions, comprising: (Li abstract, Innovations in the use of base color index map (“BCIM”) mode during encoding and/or decoding simplify implementation by reducing the number of modifications made to support BCIM mode and/or improve coding efficiency of BCIM mode. For example, some of the innovations involve reuse of a syntax structure that is adapted for transform coefficients to instead signal data for elements of an index map in BCIM mode. Other innovations relate to mapping of index values in BCIM mode or prediction of elements of an index map in BCIM mode. Still other innovations relate to handling of exception values in BCIM mode. [0036]-[0038], [0037] The innovations can be described in the general context of computer-readable media. Computer-readable media are any available tangible media that can be accessed within a computing environment. By way of example, and not limitation, with the computing system (100), computer-readable media include memory (120, 125), storage (140), and combinations of any of the above. [0047]-[0049], Figure 3)
1. obtaining original data by obtaining a picture to-be-compressed and performing modulo operation on the picture to-be-compressed; / 8. obtain original data by obtaining a picture to-be-compressed and performing modulo operation on the picture to-be-compressed; / 15. obtaining original data by obtaining a picture to-be-compressed and performing modulo operation on the picture to-be-compressed; (Li: [0036] The communication connection(s) (170) enable communication over a communication medium to another computing entity. The communication medium conveys information such as computer-executable instructions, audio or video input or output, or other data in a modulated data signal. A modulated data signal is a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media can use an electrical, optical, RF, or other carrier. [0047] FIG. 3 is a block diagram of an example encoder system (300) in conjunction with which some described embodiments may be implemented. The encoder system (300) can be a general-purpose encoding tool capable of operating in any of multiple encoding modes such as a low-latency encoding mode for real-time communication, transcoding mode, and regular encoding mode for media playback from a file or stream, or it can be a special-purpose encoding tool adapted for one such encoding mode. The encoder system (300) can be implemented as an operating system module, as part of an application library or as a standalone application. Overall, the encoder system (300) receives a sequence of source video frames (311) from a video source (310) and produces encoded data as output to a channel (390). The encoded data output to the channel can include content encoded using BCIM mode. [0048] The video source (310) can be a camera, tuner card, storage media, or other digital video source. The video source (310) produces a sequence of video frames at a frame rate of, for example, 30 frames per second. As used herein, the term “frame” generally refers to source, coded or reconstructed image data.)
1. obtaining a first storage amount by storing the original data in a first container and calculating a size of data in the first container, and obtaining a second storage amount by storing the original data in a second container and calculating a size of data in the second container; / 8. obtain a first storage amount by storing the original data in a first container and calculating a size of data in the first container, and obtain a second storage amount by storing the original data in a second container and calculating a size of data in the second container; / 15. obtaining a first storage amount by storing the original data in a first container and calculating a size of data in the first container, and obtaining a second storage amount by storing the original data in a second container and calculating a size of data in the second container; (Li: [0049] An arriving source frame (311) is stored in a source frame temporary memory storage area (320) that includes multiple frame buffer storage areas (321, 322, . . . , 32 n). A frame buffer (321, 322, etc.) holds one source frame in the source frame storage area (320). After one or more of the source frames (311) have been stored in frame buffers (321, 322, etc.), a frame selector (330) periodically selects an individual source frame from the source frame storage area (320). The order in which frames are selected by the frame selector (330) for input to the encoder (340) may differ from the order in which the frames are produced by the video source (310), e.g., a frame may be ahead in order, to facilitate temporally backward prediction. Before the encoder (340), the encoder system (300) can include a pre-processor (not shown) that performs pre-processing (e.g., filtering) of the selected frame (331) before encoding. The pre-processing can also include color space conversion into primary and secondary components for encoding. Typically, before encoding, video has been converted to a color space such as YUV, in which sample values of a luma (Y) component represent brightness or intensity values, and sample values of chroma (U, V) components represent color-difference values. The chroma sample values may be sub-sampled to a lower chroma sampling rate (e.g., for YUV 4:2:0 format), or the chroma sample values may have the same resolution as the luma sample values (e.g., for YUV 4:4:4 format). Or, the video can be encoded in another format (e.g., RGB 4:4:4 format). [0050] The encoder (340) encodes the selected frame (331) to produce a coded frame (341) and also produces memory management control operation (“MMCO”) signals (342) or reference picture set (“RPS”) information. If the current frame is not the first frame that has been encoded, when performing its encoding process, the encoder (340) may use one or more previously encoded/decoded frames (369) that have been stored in a decoded frame temporary memory storage area (360). Such stored decoded frames (369) are used as reference frames for inter-frame prediction of the content of the current source frame (331). Generally, the encoder (340) includes multiple encoding modules that perform encoding tasks such as partitioning into tiles, intra prediction estimation and prediction, motion estimation and compensation, frequency transforms, quantization and entropy coding. The exact operations performed by the encoder (340) can vary depending on compression format. The format of the output encoded data can be a variation or extension of HEVC format, Windows Media Video format, VC-1 format, MPEG-x format (e.g., MPEG-1, MPEG-2, or MPEG-4), H.26x format (e.g., H.261, H.262, H.263, H.264), or another format.)
1.determining a bit length of index data according to the first storage amount and the second storage amount, and constructing a color table and an initial index table; / 8. determine a bit length of index data according to the first storage amount and the second storage amount, and construct a color table and an initial index table; / 15. determining a bit length of index data according to the first storage amount and the second storage amount, and constructing a color table and an initial index table; (Li: [0027] The detailed description presents innovations in the use of base color index map (“BCIM”) mode during encoding and/or decoding. In particular, the detailed description presents innovations for reusing a syntax structure that is adapted for transform coefficients to instead signal data for elements of an index map in BCIM mode, mapping of index values in BCIM mode, prediction of elements of an index map and handling of exception values in BCIM mode. Some of these innovations simplify implementation by reducing the number of modifications made to support BCIM mode. Other innovations improve coding efficiency of BCIM mode. [0049] An arriving source frame (311) is stored in a source frame temporary memory storage area (320) that includes multiple frame buffer storage areas (321, 322, . . . , 32 n). A frame buffer (321, 322, etc.) holds one source frame in the source frame storage area (320). After one or more of the source frames (311) have been stored in frame buffers (321, 322, etc.), a frame selector (330) periodically selects an individual source frame from the source frame storage area (320). The order in which frames are selected by the frame selector (330) for input to the encoder (340) may differ from the order in which the frames are produced by the video source (310), e.g., a frame may be ahead in order, to facilitate temporally backward prediction. [0054] Returning to FIG. 3, the encoder represents an intra-coded block of a source frame (331) in terms of prediction from other, previously reconstructed sample values in the frame (331). For intra spatial prediction for a block, the intra-picture estimator estimates extrapolation of the neighboring reconstructed sample values into the block. The intra-prediction estimator outputs prediction information (such as prediction mode (direction) for intra spatial prediction), which is entropy coded. An intra-prediction predictor applies the prediction information to determine intra prediction values. For BCIM mode, the encoder represents an intra-coded block with index values for base colors among the sample values of the block, using a base color table for the index values and using elements of an index map. The encoder can also represent exception values in the BCIM-mode block without using index values, as described below. [0139] As a third example approach, index values for different color components (e.g., luma and chroma components for video in YUV 4:4:4 format) can be mapped into a single packed index value for a pixel. For example, a luma sample is mapped to a luma index value ny, and two corresponding chroma samples are mapped to two chroma index values nu and nv. The index values ny, nu and nv are then mapped to a single packed index value. If the number of bits used to represent each of the index values ny, nu and nv is nbits, the single packed index value npacked, combined (having 3*nbits bits) can be determined as follows.
n packed,combined =n y<<(2*n bits)+n u <<n bits +n v.
where << represents a left bit shift operation. For decoding, the index values ny, nu and nv can be reconstructed using bit mask operations and bit shifting operations to identify the values of the appropriate bits of the packed index value npacked, combined, as follows.)
1.obtaining a target color table by identifying a minimum value in the color table and subtracting the minimum value from each data in the color table for compression of the color table; / 8. obtain a target color table by identifying a minimum value in the color table and subtracting the minimum value from each data in the color table for compression of the color table; / 15. obtaining a target color table by identifying a minimum value in the color table and subtracting the minimum value from each data in the color table for compression of the color table; (Li: [0049] An arriving source frame (311) is stored in a source frame temporary memory storage area (320) that includes multiple frame buffer storage areas (321, 322, . . . , 32 n). A frame buffer (321, 322, etc.) holds one source frame in the source frame storage area (320). After one or more of the source frames (311) have been stored in frame buffers (321, 322, etc.), a frame selector (330) periodically selects an individual source frame from the source frame storage area (320). The order in which frames are selected by the frame selector (330) for input to the encoder (340) may differ from the order in which the frames are produced by the video source (310), e.g., a frame may be ahead in order, to facilitate temporally backward prediction. Before the encoder (340), the encoder system (300) can include a pre-processor (not shown) that performs pre-processing (e.g., filtering) of the selected frame (331) before encoding. The pre-processing can also include color space conversion into primary and secondary components for encoding. Typically, before encoding, video has been converted to a color space such as YUV, in which sample values of a luma (Y) component represent brightness or intensity values, and sample values of chroma (U, V) components represent color-difference values. The chroma sample values may be sub-sampled to a lower chroma sampling rate (e.g., for YUV 4:2:0 format), or the chroma sample values may have the same resolution as the luma sample values (e.g., for YUV 4:4:4 format). Or, the video can be encoded in another format (e.g., RGB 4:4:4 format). values are mapped to packed index values. [0157] FIG. 17 shows a block (1710) of packed index values npacked with dimensions i, j, for 0≦i≦7 and 0≦j≦7. Alternatively, the prediction is applied to a block of another size (e.g., 4×4, 16×16 or 32×32). During encoding, the encoder predicts a given packed index value npacked(i,j) from one or more neighboring packed index values, on a packed index value-by-packed index value basis. The direction of prediction can be horizontal, vertical, diagonal in right-downward direction, or some other direction. In FIG. 17, for example, the direction of prediction is vertical, producing a block (1730) of packed index residual values npacked, resid. The packed index value npacked(i,j) is predicted using the preceding packed index value in the same column npacked(i,j−1). The packed index residual value is simply the difference between the two values. npacked, resid(i,j)=npacked(i,j)−npacked(i,j−1). Similarly, for horizontal prediction, the packed index residual value is the difference between the packed index value and its left neighboring packed index value as the predicted index value: npacked, resid(i,j)=npacked(i,j)−npacked(i−1,j). For diagonal prediction at a 45 degree downward angle, the packed index residual value can be calculated as npacked, resid(i,j)=npacked(i,j)−(npacked(i,j−1)+npacked(i−1,j))>>1, or it can be calculated as npacked, resid(i,j)=npacked(i,j)−npacked(i−1,j−1). Prediction in other diagonal directions can similarly blend neighboring packed index values depending on the angle of prediction. For prediction at the edge of a block (e.g., i<0 and/or j<0), the neighboring packed index value can have a value of zero or be given a default value. During decoding, the decoder determines the same predicted packed index value (depending on the direction of prediction) and combines the predicted packed index value with the packed index residual value. For vertical prediction, npacked(i,j)=npacked, resid(i,j)+npacked(i,j−1). For horizontal prediction, npacked(i,j)=npacked,resid(i,j)+npacked(i−1,j). For diagonal prediction at a 45 degree downward angle, npacked(i,j)=npacked,resid(i,j)+(npacked(i,j−1)+npacked(i−1,j))>>1, or npacked(i,j)=npacked,resid(i,j)+npacked(i−1,j−1). Prediction in other diagonal directions can similarly blend neighboring packed index values depending on the angle of prediction.
[0158] In the preceding examples of prediction, subtraction operations are used during encoding, and addition operations are used during decoding. Alternatively, an encoder and decoder can use bitwise exclusive OR (XOR) operations in prediction.)
1.obtaining a first compressed index table by performing compression on the initial index table according to the bit length of the index data; / 8. obtain a first compressed index table by performing compression on the initial index table according to the bit length of the index data; / 15. obtaining a first compressed index table by performing compression on the initial index table according to the bit length of the index data; (Li: [0095] In a separate path within the decoder (600), the intra-prediction predictor (645) receives the intra prediction data (642), such as information indicating whether intra prediction uses spatial prediction or BCIM mode (e.g., a flag value per intra block or per intra block of certain prediction mode directions), prediction mode direction (for intra spatial prediction). For intra spatial prediction, using values of a reconstruction (638) of the current picture, according to prediction mode data, the intra-picture predictor (645) spatially predicts sample values of a current block of the current picture from neighboring, previously reconstructed sample values of the current picture. For BCIM mode, the decoder reconstructs an intra-coded block with index values for base colors among the sample values of the block, using a base color table for the index values and using elements of an index map. [0102]-[0104] Base Color Index Map Mode – Introduction, [0103] In BCIM mode, a video encoder or image encoder encodes sample values using index values that represent base colors. Each of the index values is associated with a different value (“base color”) among the sample values. During encoding, the sample values are replaced with corresponding index values. The encoder encodes and signals a table of index values and corresponding base colors (“base color table”) as well as the arrangement of index values that represent the sample values (“index map”). A video decoder or image decoder receives and decodes the table of index values and corresponding base colors. Using that base color table, the decoder replaces index values of the index map with base colors for the original sample values. [0104] FIG. 7. [0159] When packed index values are predicted, the encoder determines a packed index residual value as a packed index value XOR its predicted packed index value. When index values are predicted, the encoder determines an index residual value as an index value XOR its predicted index value. The residual value is signaled to the decoder. The predicted value can depend on the direction of prediction (e.g., horizontal, vertical, diagonal). [0160] When packed index values are predicted, the decoder determines a packed index value as its packed index residual value XOR the predicted packed index value. When index values are predicted, the decoder determines an index value as its index residual value XOR its predicted index value. Again, the predicted value can depend on the direction of prediction (e.g., horizontal, vertical, diagonal).)
1.and obtaining a second compressed index table by identifying a locator in the first compressed index table and performing compression on the first compressed index table according to the locator./ 8. and obtain a second compressed index table by identifying a locator in the first compressed index table and performing compression on the first compressed index table according to the locator. / 15. and obtaining a second compressed index table by identifying a locator in the first compressed index table and performing compression on the first compressed index table according to the locator. (Li: [0104] FIG. 7 shows a block (710) of sample values s in a two-dimensional arrangement with dimensions i, j, for 0≦i≦7 and 0≦j≦7. In FIG. 7, the sample values s represent intensity or brightness values for screen capture content. The sample values s include sections of uniform values and strong patterns. The block (710) includes sample values 26, 85, 41, 127, 168 and 200. [0105] The encoder creates a base color table (720) that assigns index values to corresponding base colors. In the example of FIG. 7, the index value 0 is assigned to the sample value 200, the index value 1 is assigned to the sample value 168, and so on. The encoder can assign index values to base colors according to their likelihood of occurrence in the picture, such that more common sample values have lower index values and less common sample values have higher index values, which tends to result in more efficient coding if lower index values are represented with fewer bits. Alternatively, the encoder can assign index values to base colors according to order of appearance as a block is scanned, relying on later processes such as prediction to exploit redundancy among the index values of the index map. The base color table (720) can be implemented as a look-up table or other data structure. [0106] FIG. 7 shows a block (730) in which sample values s are replaced with corresponding index values n. The process of replacing sample values with index values is lossless. Alternatively, in a lossy compression variation, a sample value can be replaced with the index value representing the base color closest to the sample value, if an exact match is not available. This can reduce the size of the base color table (720) but also introduce perceptible distortion. Another approach to handling sample values not represented with index values (so-called exception values) is described below. [0107] The encoder encodes and outputs the base color table (720) as well as an index map with elements representing the block (730) of index values n. For example, the encoder uses a coefficient coding syntax structure to represent elements of the block (730), as described below. As part of the encoding, the index values n for the block (730) can be processed with further mapping operations and/or prediction. [0161] FIG. 18 illustrates prediction using XOR operations during encoding and decoding. The packed index value is 7, and the predicted packed index value (based on one or more neighboring packed index values) is 6. During encoding, the encoder determines the packed index residual is 1: 00000001=00000111 XOR 00000110. During decoding, the decoder reconstructs the packed index value 7 from the packed index residual value and predicted packed index value: 00000111=00000001 XOR 00000110. [0164] FIG. 19 shows a technique (1900) for prediction of elements of an index map during encoding. The technique (1900) can be performed by an encoder as described with reference to FIG. 3 or FIGS. 5a and 5b , or by another encoder. [0165] The encoder encodes (1910) data, in particular, encoding elements of an index map for a block using prediction. For example, when the index map includes index residual values, the encoder predicts an index value that represents a base color, then determines an index residual value based on the index value and the predicted index value. Or, when the index map includes packed index residual values, the encoder predicts a packed index value (where the packed index value is an index value that represents a base color and is packed into a coefficient coding syntax structure), then determines a packed index residual value based on the packed index value and the predicted packed index value. The encoding with prediction can include subtraction operations, XOR operations or other operations, on all bits of the values or on partial bits of the values.)
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102 of this title, if the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains. Patentability shall not be negatived by the manner in which the invention was made.
Claims 2-7, 9-14, and 16-20 are rejected under 35 U.S.C. 103 as being unpatentable over Li et al. (US PGPub US 2016/0277760A1, hereby referred to as “Li”), in view of Bhaskar et al. (US PGPub US 201/60294410A1, hereby referred to as “Bhaskar”).
Consider Claims 1-2, 8-9 and 15-16.
Li teaches the method of claim 1, the device of claim 8 and the non-transitory computer readable storage medium of claim 15.
Li does not teach: the limitations from claims 2, 9 and 16.
Bhaskar further teaches:
1. A multi-level compression method for picture data, performed by a server and comprising: / 8. A computer device, comprising: a processor; and a memory, coupled with the processor and storing computer programs; the computer programs, when executed by the processor, are operable to: / 15. A non-transitory computer-readable storage medium, storing computer programs which, when executed by a processor, cause the processor to carry out actions, comprising: (Bhaskar: abstract, Approaches for staged data compression are provided, where each stage reflects a progressive increase in granularity, resulting in a scalable approach that exhibits improved efficiency and compression performance. The first stage comprises a long-range block-level compressor that determines redundancies on a block-level basis (based on entire data blocks, as opposed to partial segments within data blocks). The second stage comprises a long-range byte-level compressor that compresses an uncompressed block based on byte segments within the block that match previously transmitted segments. The duplicate segments are replaced with pointers to matching segments within a decompressor cache. Nonmatching segments of the data block are left uncompressed and passed to a third stage short-range compressor (e.g., a grammar-based compressor). The staged progression in granularity provides advantages of maximizing the compression gain while minimizing processing and storage requirements of the compressor and decompressor.)
1. obtaining original data by obtaining data to-be-compressed and performing modulo operation on the picture to-be-compressed; / 8. obtain original data by obtaining data to-be-compressed and performing modulo operation on the picture to-be-compressed; / 15. obtaining original data by obtaining data to-be-compressed and performing modulo operation on the picture to-be-compressed; (Bhaskar: [0032] Long range compression (LRC) is a powerful lossless data compression technique for reducing the amount of data transported over a link, so that the link capacity can be utilized more efficiently. Packets entering the link are processed by an LRC compressor, resulting in “compressed” packets of smaller size. At the other end of the link, the compressed packets are processed by an LRC de-compressor to losslessly recover the original packets. Compression is generally achieved by detection of duplicate data segments within a byte cache and highly efficient encoding of such duplicate segments. A long range compressor retains a “long range” of previously received bytes in an input byte stream for compression and captures macro redundancies in the input byte stream. As such a current byte of data may be compared with all of the stored bytes for any similar bit sequences (redundancies). A main role of long-range data compression is to provide the compressor access to a large history of past transmitted data (e.g., a large memory buffer of several tens or hundreds of megabytes), while minimizing the processing complexity needed to process the large amount of stored data. Further, the performance of such compression techniques improves with the size of the byte cache, which is stored in memory. As a result, the size and the optimum use of the available memory resources in the devices that implement compression and decompression is a critical factor in determining compression efficiency. A primary advantage of such long-range data compression is that macro redundancies as seen within a long history of the input data stream can be captured with very modest processing resources. [0040]-[0041])
1. obtaining a first storage amount by storing the original data in a first container and calculating a size of data in the first container, and obtaining a second storage amount by storing the original data in a second container and calculating a size of data in the second container; / 8. obtain a first storage amount by storing the original data in a first container and calculating a size of data in the first container, and obtain a second storage amount by storing the original data in a second container and calculating a size of data in the second container; / 15. obtaining a first storage amount by storing the original data in a first container and calculating a size of data in the first container, and obtaining a second storage amount by storing the original data in a second container and calculating a size of data in the second container; (Bhaskar: [0050] Long range compressor 106 is arranged to receive a stream of data blocks, an example block of a stream is indicated as an input data block 124. Input data block 124 varies in length, ranging from a few bytes to thousands of bytes, at a time. Some non-limiting examples of input data block 124 are IP blocks or web objects or any other blocks of data, which may be communicated over communication link 126. Long range compressor 106, hash table 108 and compressor byte cache 110 communicate with each other via a signal 130. Hash table 108 receives fingerprints computed by long range compressor 106. A hash function is used to map the fingerprint to its associated hash index. The hash index serves as an index to hash table 108, where the fingerprint and the metadata associated with that fingerprint value is stored. Hash table 108 may be implemented using any known data structure. Compressor byte cache 110 stores the previously received data blocks within the stream of data blocks, which is checked against input data block 124 for redundancy. The fingerprint metadata stored by the hash table 108 corresponds to the location of the fingerprint data window in compressor byte cache 110. Hash table 108 and compressor byte cache 110 communicate with each other via signal 132. Compressor byte cache 110 is implemented as a contiguous circular byte buffer scheme, in accordance with an aspect of the invention, with wrap-around occurring only at block boundaries. The detail implementation of compressor byte cache 110 will be described later. [0051] For the purposes of discussion, presume that input data block 124 contains a segment of bytes, which had occurred in at least one previously received data block of the stream of data blocks. Long range compressor 106, hash table 108 and compressor byte cache 110 work together to look for duplication of a segment of data (not necessarily the whole block), which had occurred earlier. Long range compressor 106 extracts characteristic patterns of data, also called fingerprints, from input data block 124. A hash value is computed for each fingerprint. The computed hash value serves as an index to hash table 108, where the fingerprint and all the metadata associated with that fingerprint is stored. The metadata of a fingerprint is basically a location index to the compressor byte cache 110; it points to the location of the data (within compressor byte cache 110) from which the fingerprint had been computed. Metadata is used to map a fingerprint back to a byte sequence within compressor byte cache 110. Fingerprints are computed for each byte of incoming input data block 124. Based on a fingerprint selection process, most of the fingerprints are discarded and only few are stored. In one embodiment, fingerprints that have ‘zero’ in their last six least significant bits (LSB) are selected to be stored.)
1.obtaining a first compressed index table by performing compression on the initial index table according to the bit length of the index data; / 8. obtain a first compressed index table by performing compression on the initial index table according to the bit length of the index data; / 15. obtaining a first compressed index table by performing compression on the initial index table according to the bit length of the index data; (Bhaskar: [0060] FIG. 2 illustrates an example embodiment of a communication system 200 in accordance with an aspect of the present invention. As illustrated in FIG. 2, communication system 200 includes a compression side 202 and a decompression side 204. Compression side 202 includes a long range compression portion 206 and a short range compression portion 208. Long range compression portion 206 includes long range compressor 106 (shown by a dotted region), hash table 108, and compressor byte cache 110 similar to FIG. 1, however the communication between different elements of long range compression portion 206 and its operation is explained in detail with reference to FIG. 2. Short range compression portion 208 further includes short range compressor 112, and compressor grammar transform portion 114 similar to FIG. 1, however the communication between different elements of short range compression portion 208 and its operation is explained in detail with reference to FIG. 2. Further, long range compressor 106 includes a fingerprint generator 214, a match region detector and expander 216, a block compressor 218, a data update portion 220 and a literals history linked list 222. In this illustration, each of fingerprint generator 214, match region detector and expander 216, block compressor 218, data update portion 220, literals history linked list 222, hash table 108 and compressor byte cache 110 are illustrated as distinct devices. However, at least two of fingerprint generator 214, match region detector and expander 216, block compressor 218, data update portion 220, literals history linked list 222, hash table 108 and compressor byte cache 110 may be combined as a unitary device. Short range compressor 112 further includes a byte sequence parser 224, a grammar update portion 226 and an adaptive arithmetic coder 228. In this illustration, each of byte sequence parser 224, grammar update portion 226, adaptive arithmetic coder 228 and compressor grammar transform portion 114 are illustrated as distinct devices. However, at least one of byte sequence parser 224, grammar update portion 226, adaptive arithmetic coder 228 and compressor grammar transform portion 114 may be combined as a unitary device.)
1.and obtaining a second compressed index table by identifying a locator in the first compressed index table and performing compression on the first compressed index table according to the locator./ 8. and obtain a second compressed index table by identifying a locator in the first compressed index table and performing compression on the first compressed index table according to the locator. / 15. and obtaining a second compressed index table by identifying a locator in the first compressed index table and performing compression on the first compressed index table according to the locator. (Bhaskar: [0058] Short range compressor 112 provides compressed data blocks 138, which are transmitted over communication link 126 and received by short range de-compressor 116. It is essential that communication link 126 provides a reliable transport or link layer to ensure that compressed data blocks 138 are delivered to short range de-compressor 116 in the order of transmission and without errors or lost blocks. Short range de-compressor 116 decompresses compressed data blocks 138 received over communication link 126 and reproduces data blocks consisting of the match descriptors and literal segments. In this non-limiting example embodiment, a grammar-based de-compressor is illustrated for short range decompression but any second order short range de-compressor may be used. Short range de-compressor 116 communicates with de-compressor grammar transform portion 118 via a signal 140. Grammar on the de-compressor side needs to be updated based on the information received over communication link 126 such that it is identical to the grammar on compression side 102, in order to achieve lossless decompression. Short range de-compressor 116 communicates with long range de-compressor 120 via a signal 142. [0059], )
2. The method of claim 1, wherein obtaining the first storage amount by storing the original data in the first container and calculating the size of the data in the first container and obtaining the second storage amount by storing the original data in the second container and calculating the size of the data in the second container comprise: / 9. The computer device of claim 8, wherein the processor configured to obtain the first storage amount by storing the original data in the first container and calculating the size of the data in the first container and obtain the second storage amount by storing the original data in the second container and calculating the size of the data in the second container is configured to: / 16. The non-transitory computer-readable storage medium of claim 15, wherein the computer program executed by the processor to carry out the action of obtaining the first storage amount by storing the original data in the first container and calculating the size of the data in the first container and obtaining the second storage amount by storing the original data in the second container and calculating the size of the data in the second container is executed by the processor to carry out actions, comprising: (Bhaskar: [0052] At a later time, if a fingerprint of input data block 124 matches with a fingerprint that is stored in hash table 108, it indicates that bytes of data of a previously received data block match bytes of data of input data block 124. In one embodiment, a fingerprint is computed over window size of data of 64 bytes. There could be a match of more than 64 bytes of data so the match region may be expanded to the left (less recently received bytes) and to the right (more recently received bytes). This will be described in greater detail below. Typically there could be thousands of matching bytes between a current data block and previous data blocks, contributing to long range compression. A valid match indicates that a segment of bytes in input data block 124 match with a segment of bytes stored in compressor byte cache 110. Once a valid match is found, long range compression of that segment of input data block 124 may be performed. [0062] Focusing now on compression side 202, fingerprint generator 214 is arranged to receive a stream of data that includes sequence of contiguous blocks of data, which needs to be compressed, such as input data block 124. In one embodiment, input data block 124 is a byte stream comprising the internet traffic. The size of the block is variable and depends on the layer at which compression is applied in the network stack. For example, at the IP layer, the blocks may be IP pockets, or at the application layer, blocks may be segments of HTTP objects. As the data enters input data block 124, fingerprint generator 214 computes a fingerprint for each byte of data based on a fast sliding window. In one embodiment, a recursively computed Rabin fingerprint is used to minimize complexity but any known polynomial computation scheme for generating a fingerprint may be used. In one embodiment, fingerprint window is a 64 bytes window. Each fingerprint is a compact characterization of the byte sequence within its fingerprint window. If any two fingerprints match, the byte sequences within the corresponding windows will be identical with a high probability. Thus, duplicate byte sequences can be detected by comparison of their fingerprint values rather than a byte-wise comparison. A fingerprint is computed for each byte of input data block 124. The computed fingerprint has to be saved when the input block is added to compressor byte cache 110 after the compression of the block is completed. Since cache sizes can be large, it would be impractical to store all the fingerprints computed for each byte of the whole block. As such, a hash system is used to reduce the number of fingerprints saved in accordance with some embodiments of the present invention. [0063] Consider the example the situation where, for a 228 byte cache, there may be 228 possible fingerprints, one for each possible distinct string of bits within compressor byte cache 110. In this example, consider that in input data block 124, only 1 out of every 64 fingerprints are retained. Therefore, as opposed to providing sufficient memory to store the possible 228 fingerprints, only enough memory is required to store 222 fingerprints. This would reduce storage space required for storing fingerprints and fingerprint metadata by a factor of 64. Hence a fingerprint selection process is used to discard most of the fingerprints and select only a small subset for storage. The key requirement for the selection criterion is that it should be position independent, for example, if two fingerprint windows, at two different positions in input data block 124, have identical data, the outcome of the selection criterion should be the same for both fingerprints. In order to meet such requirements, in an example embodiment, fingerprint generator 214 uses a criterion that selects only the fingerprints that have their last γ least significant bits as zero, where γ is an integer number. If the underlying data is random, this results in the random sampling of the computed fingerprints. The number of selected fingerprints is reduced by a factor of about 2 relative to the total numbers of fingerprints computed.)
2. obtaining the first storage amount by storing the original data in a form of double bytes in the first container and calculating the size of the data in the first container through byte statistics; / 9. obtain the first storage amount by storing the original data in a form of double bytes in the first container and calculating the size of the data in the first container through byte statistics; / 16. obtaining the first storage amount by storing the original data in a form of double bytes in the first container and calculating the size of the data in the first container through byte statistics; (Bhaskar: [0094] According to example embodiments of the present invention, therefore, such design challenges are addressed by the detection of redundant blocks based on hash values corresponding to the respective input blocks. By way of example, the block-level LRC 611, of the first stage, compresses input blocks based on a block hash table 612. More specifically, for each input block received by the block-level LRC 611 compressor, the compressor computes the hash value based on a collision-resistant hash function and stores the hash value in the block hash table 612. In one embodiment, the block hash table 612 is configured as a bucketed hash table stored in a memory efficient manner in order to facilitate efficient detection of matching hash values. A hash function applied to a number of bytes of data traffic comprises application of a mathematical operation on the data to reduce the data size by a significant factor (e.g., applying a mathematical function to a block of data traffic of say 1500 bytes and generating a hash value of say 8 or 16 bytes). Depending on the hash function applied, it is possible for two different blocks of data to result in the same hash value, which is referred to as a collision. To avoid hash collisions, collision-resistant hash functions reduce the probability of a collision to a statistically insignificant level (e.g., a probability of collision on the order of 2−64) by generating larger hash values (e.g., 128 bytes or 256 bytes in length) where the likelihood of a collision is relatively impossible in the context of the size of the data blocks being handled in this compression stage. In this embodiment, for example, the compressor applies a SHA-1 hash function to each received input block. While the present example embodiment is presented as comprising a SHA-1 hash function as a basis for determining block-level matches by the block-level compressor, it will be readily apparent that any one of a number of such collision-resistant hash functions may be employed without departing from the spirit of embodiments of the present invention.)
2. and obtaining the second storage amount by storing the original data in a form of four bytes in the second container and calculating the size of the data in the second container through byte statistics. / 9. and obtain the second storage amount by storing the original data in a form of four bytes in the second container and calculating the size of the data in the second container through byte statistics. / 16. and obtaining the second storage amount by storing the original data in a form of four bytes in the second container and calculating the size of the data in the second container through byte statistics. (Bhaskar: [0095] Accordingly, when each new input block is received at the block-level LRC 611 compressor, the compressor first computes the respective hash value for the input block, and then determines if that hash value matches the hash value corresponding to a prior input block stored in the block hash table 612. If no match exists, the compressor determines that the input block is not a duplication of a prior received input block within the range of the input blocks reflected by the block hash table. In that event, the block-level compressor does not perform any compression with respect to that particular input block, which does not reflect a match. Instead, the compressor simply passes that input block on to the second stage byte-level compressor (Stage 2). If a match is detected, the compressor determines that the input block is a duplication of the prior received input block reflected by the matching hash value stored in the block hash table. In that event, compression by the first stage is possible. Regardless of whether a match is detected or not, the block level LRC does not store the input block of bytes in a cache. Only the collision-resistant hash of the block is added to the hash table. This permits the compressor to operate as if it has a large memory, without actually requiring the storage space for storing the blocks. It should be noted that the determination of whether an input block is a duplication of a prior input block represents an assumption based on matching hash values, but that such an assumption can be made with a very high probability, since the block hash is a strong collision resistant hash (e.g., SHA-1). For example, a 20 MB block hash table can store one million SHA-1 hash values, which is equivalent to storing one million respective data blocks of say 1500 packets each (a 20 MB hash cache achieves the equivalent storage of a 1.5 GB cache, which reflects a history of one million data blocks as a basis for compression matches).)
It would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to modify Li’s multi-processing system for image compression using a base color index map with the teachings of Bhaskar for block level long compression in order to more adeptly determine and handle redundances on a block-level basis. The determination of obviousness is predicated upon the following findings: One skilled in the art would have been motivated to modify Li in order to improve the overall image compression algorithm that factors a base color index map to apply Bhaskar’s “staged progression in granularity” in order to advantageously ensure “maximizing the compression gain while minimizing processing and storage requirements of the compressor and decompressor” (Bhaskar: abstract). Furthermore, the prior art collectively includes each element claimed (though not all in the same reference), and one of ordinary skill in the art could have combined the elements in the manner explained above using known engineering design, interface and programming techniques, without changing a “fundamental” operating principle of Li, while the teaching of Bhaskar continues to perform the same function as originally taught prior to being combined, in order to produce the repeatable and predictable result of staged progression in granularity on a block level basis. It is for at least the aforementioned reasons that the examiner has reached a conclusion of obviousness with respect to the claim in question.
Consider Claims 3, 10 and 17.
The combination of Li and Bhaskar teaches:
3. The method of claim 1, wherein determining the bit length of the index data according to the first storage amount and the second storage amount and constructing the color table and the initial index table comprise: determining a smallest size among the first storage amount and the second storage amount as a target value, and determining the target value as the bit length of the index data; determining a container corresponding to the target value as a target container, and determining a data type of the target container as a target type; and constructing the color table and the initial index table according to the target container and the target type. / 10. The computer device of claim 8, wherein the processor configured to determine the bit length of the index data according to the first storage amount and the second storage amount and constructing the color table and the initial index table is configured to: determine a smallest size among the first storage amount and the second storage amount as a target value, and determining the target value as the bit length of the index data; determine a container corresponding to the target value as a target container, and determining a data type of the target container as a target type; and construct the color table and the initial index table according to the target container and the target type. / 17. The non-transitory computer-readable storage medium of claim 15, wherein the computer program executed by the processor to carry out the action of determining the bit length of the index data according to the first storage amount and the second storage amount and constructing the color table and the initial index table is executed by the processor to carry out actions, comprising: determining a smallest size among the first storage amount and the second storage amount as a target value, and determining the target value as the bit length of the index data; determining a container corresponding to the target value as a target container, and determining a data type of the target container as a target type; and constructing the color table and the initial index table according to the target container and the target type. (Bhaskar: [0062] Focusing now on compression side 202, fingerprint generator 214 is arranged to receive a stream of data that includes sequence of contiguous blocks of data, which needs to be compressed, such as input data block 124. In one embodiment, input data block 124 is a byte stream comprising the internet traffic. The size of the block is variable and depends on the layer at which compression is applied in the network stack. For example, at the IP layer, the blocks may be IP pockets, or at the application layer, blocks may be segments of HTTP objects. As the data enters input data block 124, fingerprint generator 214 computes a fingerprint for each byte of data based on a fast sliding window. In one embodiment, a recursively computed Rabin fingerprint is used to minimize complexity but any known polynomial computation scheme for generating a fingerprint may be used. In one embodiment, fingerprint window is a 64 bytes window. Each fingerprint is a compact characterization of the byte sequence within its fingerprint window. If any two fingerprints match, the byte sequences within the corresponding windows will be identical with a high probability. Thus, duplicate byte sequences can be detected by comparison of their fingerprint values rather than a byte-wise comparison. A fingerprint is computed for each byte of input data block 124. The computed fingerprint has to be saved when the input block is added to compressor byte cache 110 after the compression of the block is completed. Since cache sizes can be large, it would be impractical to store all the fingerprints computed for each byte of the whole block. As such, a hash system is used to reduce the number of fingerprints saved in accordance with some embodiments of the present invention. [0063] Consider the example the situation where, for a 228 byte cache, there may be 228 possible fingerprints, one for each possible distinct string of bits within compressor byte cache 110. In this example, consider that in input data block 124, only 1 out of every 64 fingerprints are retained. Therefore, as opposed to providing sufficient memory to store the possible 228 fingerprints, only enough memory is required to store 222 fingerprints. This would reduce storage space required for storing fingerprints and fingerprint metadata by a factor of 64. Hence a fingerprint selection process is used to discard most of the fingerprints and select only a small subset for storage. The key requirement for the selection criterion is that it should be position independent, for example, if two fingerprint windows, at two different positions in input data block 124, have identical data, the outcome of the selection criterion should be the same for both fingerprints. In order to meet such requirements, in an example embodiment, fingerprint generator 214 uses a criterion that selects only the fingerprints that have their last γ least significant bits as zero, where γ is an integer number. If the underlying data is random, this results in the random sampling of the computed fingerprints. The number of selected fingerprints is reduced by a factor of about 2 relative to the total numbers of fingerprints computed. [0095] Accordingly, when each new input block is received at the block-level LRC 611 compressor, the compressor first computes the respective hash value for the input block, and then determines if that hash value matches the hash value corresponding to a prior input block stored in the block hash table 612. If no match exists, the compressor determines that the input block is not a duplication of a prior received input block within the range of the input blocks reflected by the block hash table. In that event, the block-level compressor does not perform any compression with respect to that particular input block, which does not reflect a match. Instead, the compressor simply passes that input block on to the second stage byte-level compressor (Stage 2). If a match is detected, the compressor determines that the input block is a duplication of the prior received input block reflected by the matching hash value stored in the block hash table. In that event, compression by the first stage is possible. Regardless of whether a match is detected or not, the block level LRC does not store the input block of bytes in a cache. Only the collision-resistant hash of the block is added to the hash table. This permits the compressor to operate as if it has a large memory, without actually requiring the storage space for storing the blocks. It should be noted that the determination of whether an input block is a duplication of a prior input block represents an assumption based on matching hash values, but that such an assumption can be made with a very high probability, since the block hash is a strong collision resistant hash (e.g., SHA-1). For example, a 20 MB block hash table can store one million SHA-1 hash values, which is equivalent to storing one million respective data blocks of say 1500 packets each (a 20 MB hash cache achieves the equivalent storage of a 1.5 GB cache, which reflects a history of one million data blocks as a basis for compression matches). Li: [0102]-[0104] Base Color Index Map Mode – Introduction, [0103] In BCIM mode, a video encoder or image encoder encodes sample values using index values that represent base colors. Each of the index values is associated with a different value (“base color”) among the sample values. During encoding, the sample values are replaced with corresponding index values. The encoder encodes and signals a table of index values and corresponding base colors (“base color table”) as well as the arrangement of index values that represent the sample values (“index map”). A video decoder or image decoder receives and decodes the table of index values and corresponding base colors. Using that base color table, the decoder replaces index values of the index map with base colors for the original sample values. [0104] FIG. 7 shows a block (710) of sample values s in a two-dimensional arrangement with dimensions i, j, for 0≦i≦7 and 0≦j≦7. In FIG. 7, the sample values s represent intensity or brightness values for screen capture content. The sample values s include sections of uniform values and strong patterns. The block (710) includes sample values 26, 85, 41, 127, 168 and 200. [0105] The encoder creates a base color table (720) that assigns index values to corresponding base colors. In the example of FIG. 7, the index value 0 is assigned to the sample value 200, the index value 1 is assigned to the sample value 168, and so on. The encoder can assign index values to base colors according to their likelihood of occurrence in the picture, such that more common sample values have lower index values and less common sample values have higher index values, which tends to result in more efficient coding if lower index values are represented with fewer bits. Alternatively, the encoder can assign index values to base colors according to order of appearance as a block is scanned, relying on later processes such as prediction to exploit redundancy among the index values of the index map. The base color table (720) can be implemented as a look-up table or other data structure. [0106] FIG. 7 shows a block (730) in which sample values s are replaced with corresponding index values n. The process of replacing sample values with index values is lossless. Alternatively, in a lossy compression variation, a sample value can be replaced with the index value representing the base color closest to the sample value, if an exact match is not available. This can reduce the size of the base color table (720) but also introduce perceptible distortion. Another approach to handling sample values not represented with index values (so-called exception values) is described below. [0107] The encoder encodes and outputs the base color table (720) as well as an index map with elements representing the block (730) of index values n. For example, the encoder uses a coefficient coding syntax structure to represent elements of the block (730), as described below. As part of the encoding, the index values n for the block (730) can be processed with further mapping operations and/or prediction.)
Consider Claims 4 and 11.
The combination of Li and Bhaskar teaches:
4. The method of claim 3, wherein constructing the color table and the initial index table according to the target container and the target type comprises: constructing the color table with data in the target container; obtaining converted original data by converting a data type of the original data to the target type; and constructing the initial index table by replacing data among the converted original data which is the same as data in the color table with a corresponding index in the color table./ 11. The computer device of claim 10, wherein the processor configured to construct the color table and the initial index table according to the target container and the target type is configured to: construct the color table with data in the target container; obtain converted original data by converting a data type of the original data to the target type; and construct the initial index table by replacing data among the converted original data which is the same as data in the color table with a corresponding index in the color table. (Bhaskar: [0095] Accordingly, when each new input block is received at the block-level LRC 611 compressor, the compressor first computes the respective hash value for the input block, and then determines if that hash value matches the hash value corresponding to a prior input block stored in the block hash table 612. If no match exists, the compressor determines that the input block is not a duplication of a prior received input block within the range of the input blocks reflected by the block hash table. In that event, the block-level compressor does not perform any compression with respect to that particular input block, which does not reflect a match. Instead, the compressor simply passes that input block on to the second stage byte-level compressor (Stage 2). If a match is detected, the compressor determines that the input block is a duplication of the prior received input block reflected by the matching hash value stored in the block hash table. In that event, compression by the first stage is possible. Regardless of whether a match is detected or not, the block level LRC does not store the input block of bytes in a cache. Only the collision-resistant hash of the block is added to the hash table. This permits the compressor to operate as if it has a large memory, without actually requiring the storage space for storing the blocks. It should be noted that the determination of whether an input block is a duplication of a prior input block represents an assumption based on matching hash values, but that such an assumption can be made with a very high probability, since the block hash is a strong collision resistant hash (e.g., SHA-1). For example, a 20 MB block hash table can store one million SHA-1 hash values, which is equivalent to storing one million respective data blocks of say 1500 packets each (a 20 MB hash cache achieves the equivalent storage of a 1.5 GB cache, which reflects a history of one million data blocks as a basis for compression matches). Li: [0102]-[0104] Base Color Index Map Mode – Introduction, [0103] In BCIM mode, a video encoder or image encoder encodes sample values using index values that represent base colors. Each of the index values is associated with a different value (“base color”) among the sample values. During encoding, the sample values are replaced with corresponding index values. The encoder encodes and signals a table of index values and corresponding base colors (“base color table”) as well as the arrangement of index values that represent the sample values (“index map”). A video decoder or image decoder receives and decodes the table of index values and corresponding base colors. Using that base color table, the decoder replaces index values of the index map with base colors for the original sample values. [0104] FIG. 7 shows a block (710) of sample values s in a two-dimensional arrangement with dimensions i, j, for 0≦i≦7 and 0≦j≦7. In FIG. 7, the sample values s represent intensity or brightness values for screen capture content. The sample values s include sections of uniform values and strong patterns. The block (710) includes sample values 26, 85, 41, 127, 168 and 200. [0105] The encoder creates a base color table (720) that assigns index values to corresponding base colors. In the example of FIG. 7, the index value 0 is assigned to the sample value 200, the index value 1 is assigned to the sample value 168, and so on. The encoder can assign index values to base colors according to their likelihood of occurrence in the picture, such that more common sample values have lower index values and less common sample values have higher index values, which tends to result in more efficient coding if lower index values are represented with fewer bits. Alternatively, the encoder can assign index values to base colors according to order of appearance as a block is scanned, relying on later processes such as prediction to exploit redundancy among the index values of the index map. The base color table (720) can be implemented as a look-up table or other data structure. [0106] FIG. 7 shows a block (730) in which sample values s are replaced with corresponding index values n. The process of replacing sample values with index values is lossless. Alternatively, in a lossy compression variation, a sample value can be replaced with the index value representing the base color closest to the sample value, if an exact match is not available. This can reduce the size of the base color table (720) but also introduce perceptible distortion. Another approach to handling sample values not represented with index values (so-called exception values) is described below. [0107] The encoder encodes and outputs the base color table (720) as well as an index map with elements representing the block (730) of index values n. For example, the encoder uses a coefficient coding syntax structure to represent elements of the block (730), as described below. As part of the encoding, the index values n for the block (730) can be processed with further mapping operations and/or prediction.)
Consider Claims 5, 12 and 18.
The combination of Li and Bhaskar teaches:
5. The method of claim 1, wherein obtaining the target color table by identifying the minimum value in the color table and subtracting the minimum value from each data in the color table for compression of the color table comprises: identifying the minimum value in the color table and determining the minimum value as an offset; determining whether each data in the color table satisfies a first preset condition; obtaining the target color table by subtracting the offset from each data in the color table for compression of the color table, in response to the first preset condition being satisfied; and converting a data type of the target color table to a preset data type. / 12. The computer device of claim 8, wherein the processor configured to obtain the target color table by identifying the minimum value in the color table and subtracting the minimum value from each data in the color table for compression of the color table is configured to: identify the minimum value in the color table and determine the minimum value as an offset; determine whether each data in the color table satisfies a first preset condition; obtain the target color table by subtracting the offset from each data in the color table for compression of the color table, in response to the first preset condition being satisfied; and convert a data type of the target color table to a preset data type./ 18. The non-transitory computer-readable storage medium of claim 15, wherein the computer program executed by the processor to carry out the action of obtaining the target color table by identifying the minimum value in the color table and subtracting the minimum value from each data in the color table for compression of the color table is executed by the processor to carry out actions, comprising: identifying the minimum value in the color table and determining the minimum value as an offset; determining whether each data in the color table satisfies a first preset condition; obtaining the target color table by subtracting the offset from each data in the color table for compression of the color table, in response to the first preset condition being satisfied; and converting a data type of the target color table to a preset data type. (Bhaskar: [0095] Accordingly, when each new input block is received at the block-level LRC 611 compressor, the compressor first computes the respective hash value for the input block, and then determines if that hash value matches the hash value corresponding to a prior input block stored in the block hash table 612. If no match exists, the compressor determines that the input block is not a duplication of a prior received input block within the range of the input blocks reflected by the block hash table. In that event, the block-level compressor does not perform any compression with respect to that particular input block, which does not reflect a match. Instead, the compressor simply passes that input block on to the second stage byte-level compressor (Stage 2). If a match is detected, the compressor determines that the input block is a duplication of the prior received input block reflected by the matching hash value stored in the block hash table. In that event, compression by the first stage is possible. Regardless of whether a match is detected or not, the block level LRC does not store the input block of bytes in a cache. Only the collision-resistant hash of the block is added to the hash table. This permits the compressor to operate as if it has a large memory, without actually requiring the storage space for storing the blocks. It should be noted that the determination of whether an input block is a duplication of a prior input block represents an assumption based on matching hash values, but that such an assumption can be made with a very high probability, since the block hash is a strong collision resistant hash (e.g., SHA-1). For example, a 20 MB block hash table can store one million SHA-1 hash values, which is equivalent to storing one million respective data blocks of say 1500 packets each (a 20 MB hash cache achieves the equivalent storage of a 1.5 GB cache, which reflects a history of one million data blocks as a basis for compression matches). Li: [0102]-[0104] Base Color Index Map Mode – Introduction, [0103] In BCIM mode, a video encoder or image encoder encodes sample values using index values that represent base colors. Each of the index values is associated with a different value (“base color”) among the sample values. During encoding, the sample values are replaced with corresponding index values. The encoder encodes and signals a table of index values and corresponding base colors (“base color table”) as well as the arrangement of index values that represent the sample values (“index map”). A video decoder or image decoder receives and decodes the table of index values and corresponding base colors. Using that base color table, the decoder replaces index values of the index map with base colors for the original sample values. [0104] FIG. 7 shows a block (710) of sample values s in a two-dimensional arrangement with dimensions i, j, for 0≦i≦7 and 0≦j≦7. In FIG. 7, the sample values s represent intensity or brightness values for screen capture content. The sample values s include sections of uniform values and strong patterns. The block (710) includes sample values 26, 85, 41, 127, 168 and 200. [0105] The encoder creates a base color table (720) that assigns index values to corresponding base colors. In the example of FIG. 7, the index value 0 is assigned to the sample value 200, the index value 1 is assigned to the sample value 168, and so on. The encoder can assign index values to base colors according to their likelihood of occurrence in the picture, such that more common sample values have lower index values and less common sample values have higher index values, which tends to result in more efficient coding if lower index values are represented with fewer bits. Alternatively, the encoder can assign index values to base colors according to order of appearance as a block is scanned, relying on later processes such as prediction to exploit redundancy among the index values of the index map. The base color table (720) can be implemented as a look-up table or other data structure. [0106] FIG. 7 shows a block (730) in which sample values s are replaced with corresponding index values n. The process of replacing sample values with index values is lossless. Alternatively, in a lossy compression variation, a sample value can be replaced with the index value representing the base color closest to the sample value, if an exact match is not available. This can reduce the size of the base color table (720) but also introduce perceptible distortion. Another approach to handling sample values not represented with index values (so-called exception values) is described below. [0107] The encoder encodes and outputs the base color table (720) as well as an index map with elements representing the block (730) of index values n. For example, the encoder uses a coefficient coding syntax structure to represent elements of the block (730), as described below. As part of the encoding, the index values n for the block (730) can be processed with further mapping operations and/or prediction.)
Consider Claims 6, 13 and 19.
The combination of Li and Bhaskar teaches:
6. The method of claim 1, wherein obtaining the first compressed index table by performing compression on the initial index table according to the bit length of the index data comprises: determining the number of bits according to the bit length of the index data and a second preset condition; determining valid data and unused data in the initial index table according to the number of bits; and obtaining the first compressed index table by synthesizing new data by shifting adjacent data in the unused data for compression of the initial index table./ 13. The computer device of claim 8, wherein the processor configured to obtain the first compressed index table by performing compression on the initial index table according to the bit length of the index data is configured to: determine the number of bits according to the bit length of the index data and a second preset condition; determine valid data and unused data in the initial index table according to the number of bits; and obtain the first compressed index table by synthesizing new data by shifting adjacent data in the unused data for compression of the initial index table./ 19. The non-transitory computer-readable storage medium of claim 15, wherein the computer program executed by the processor to carry out the action of obtaining the first compressed index table by performing compression on the initial index table according to the bit length of the index data is executed by the processor to carry out actions, comprising: determining the number of bits according to the bit length of the index data and a second preset condition; determining valid data and unused data in the initial index table according to the number of bits; and obtaining the first compressed index table by synthesizing new data by shifting adjacent data in the unused data for compression of the initial index table. (Bhaskar: [0071] Circular byte cache 300 is implemented as a contiguous circular byte buffer, with wrap around occurring only at block boundaries, instead of breaking up a block across cache boundaries. When a new input block is added to circular byte cache 300, it overwrites the oldest data in the cache. If an entire input block cannot fit at the end of circular byte cache 300, wrap-around occurs and the entire block is added at the start of circular byte cache 300. For example, if a new block is too big to fit between next insert position 316 and last valid byte position 328 then instead of splitting up the block across cache boundaries, it is added at the start of segment 308. Implementation of circular byte cache 300 as a contiguous circular byte buffer, considerably simplifies cache management, expansion of match regions and verification of stale fingerprints. The simplicity provided for verification of fingerprints also means that the size of the fingerprint metadata that has to be stored is much smaller, reducing storage complexity. Contiguous storage also allows expansion of match regions across (cached) block boundaries, leading to longer matches and improves compression gain. [0095] Accordingly, when each new input block is received at the block-level LRC 611 compressor, the compressor first computes the respective hash value for the input block, and then determines if that hash value matches the hash value corresponding to a prior input block stored in the block hash table 612. If no match exists, the compressor determines that the input block is not a duplication of a prior received input block within the range of the input blocks reflected by the block hash table. In that event, the block-level compressor does not perform any compression with respect to that particular input block, which does not reflect a match. Instead, the compressor simply passes that input block on to the second stage byte-level compressor (Stage 2). If a match is detected, the compressor determines that the input block is a duplication of the prior received input block reflected by the matching hash value stored in the block hash table. In that event, compression by the first stage is possible. Regardless of whether a match is detected or not, the block level LRC does not store the input block of bytes in a cache. Only the collision-resistant hash of the block is added to the hash table. This permits the compressor to operate as if it has a large memory, without actually requiring the storage space for storing the blocks. It should be noted that the determination of whether an input block is a duplication of a prior input block represents an assumption based on matching hash values, but that such an assumption can be made with a very high probability, since the block hash is a strong collision resistant hash (e.g., SHA-1). For example, a 20 MB block hash table can store one million SHA-1 hash values, which is equivalent to storing one million respective data blocks of say 1500 packets each (a 20 MB hash cache achieves the equivalent storage of a 1.5 GB cache, which reflects a history of one million data blocks as a basis for compression matches). Li: [0102]-[0104] Base Color Index Map Mode – Introduction, [0103] In BCIM mode, a video encoder or image encoder encodes sample values using index values that represent base colors. Each of the index values is associated with a different value (“base color”) among the sample values. During encoding, the sample values are replaced with corresponding index values. The encoder encodes and signals a table of index values and corresponding base colors (“base color table”) as well as the arrangement of index values that represent the sample values (“index map”). A video decoder or image decoder receives and decodes the table of index values and corresponding base colors. Using that base color table, the decoder replaces index values of the index map with base colors for the original sample values. [0104] FIG. 7 shows a block (710) of sample values s in a two-dimensional arrangement with dimensions i, j, for 0≦i≦7 and 0≦j≦7. In FIG. 7, the sample values s represent intensity or brightness values for screen capture content. The sample values s include sections of uniform values and strong patterns. The block (710) includes sample values 26, 85, 41, 127, 168 and 200. [0105] The encoder creates a base color table (720) that assigns index values to corresponding base colors. In the example of FIG. 7, the index value 0 is assigned to the sample value 200, the index value 1 is assigned to the sample value 168, and so on. The encoder can assign index values to base colors according to their likelihood of occurrence in the picture, such that more common sample values have lower index values and less common sample values have higher index values, which tends to result in more efficient coding if lower index values are represented with fewer bits. Alternatively, the encoder can assign index values to base colors according to order of appearance as a block is scanned, relying on later processes such as prediction to exploit redundancy among the index values of the index map. The base color table (720) can be implemented as a look-up table or other data structure. [0106] FIG. 7 shows a block (730) in which sample values s are replaced with corresponding index values n. The process of replacing sample values with index values is lossless. Alternatively, in a lossy compression variation, a sample value can be replaced with the index value representing the base color closest to the sample value, if an exact match is not available. This can reduce the size of the base color table (720) but also introduce perceptible distortion. Another approach to handling sample values not represented with index values (so-called exception values) is described below. [0107] The encoder encodes and outputs the base color table (720) as well as an index map with elements representing the block (730) of index values n. For example, the encoder uses a coefficient coding syntax structure to represent elements of the block (730), as described below. As part of the encoding, the index values n for the block (730) can be processed with further mapping operations and/or prediction.)
Consider Claims 7, 14 and 20.
The combination of Li and Bhaskar teaches:
7. The method of claim 1, wherein obtaining the second compressed index table by identifying the locator in the first compressed index table and performing compression on the first compressed index table according to the locator comprises: searching for skp data within any Tx data range in the first compressed index table, and determining the skp data as the locator in response to no skp data being found or a frequency of appearance of the skp data being the lowest; traversing the first compressed index table, and inserting a preset amount of data after data equal to the locator in response to the data equal to the locator existing in the first compressed index table; and obtaining the second compressed index table by replacing continuous and identical data in a preset replacement mode for compression of the first compressed index table, in response to the continuous and identical data existing in the first compressed index table./ 14. The computer device of claim 8, wherein the processor configured to obtain the second compressed index table by identifying the locator in the first compressed index table and performing compression on the first compressed index table according to the locator is configured to: search for skp data within any Tx data range in the first compressed index table, and determine the skp data as the locator in response to no skp data being found or a frequency of appearance of the skp data being the lowest; traverse the first compressed index table, and insert a preset amount of data after data equal to the locator in response to the data equal to the locator existing in the first compressed index table; and obtain the second compressed index table by replacing continuous and identical data in a preset replacement mode for compression of the first compressed index table, in response to the continuous and identical data existing in the first compressed index table./ 20. The non-transitory computer-readable storage medium of claim 15, wherein the computer program executed by the processor to carry out the action of obtaining the second compressed index table by identifying the locator in the first compressed index table and performing compression on the first compressed index table according to the locator is executed by the processor to carry out actions, comprising: searching for skp data within any Tx data range in the first compressed index table, and determining the skp data as the locator in response to no skp data being found or a frequency of appearance of the skp data being the lowest; traversing the first compressed index table, and inserting a preset amount of data after data equal to the locator in response to the data equal to the locator existing in the first compressed index table; and obtaining the second compressed index table by replacing continuous and identical data in a preset replacement mode for compression of the first compressed index table, in response to the continuous and identical data existing in the first compressed index table. (Bhaskar: [0095] Accordingly, when each new input block is received at the block-level LRC 611 compressor, the compressor first computes the respective hash value for the input block, and then determines if that hash value matches the hash value corresponding to a prior input block stored in the block hash table 612. If no match exists, the compressor determines that the input block is not a duplication of a prior received input block within the range of the input blocks reflected by the block hash table. In that event, the block-level compressor does not perform any compression with respect to that particular input block, which does not reflect a match. Instead, the compressor simply passes that input block on to the second stage byte-level compressor (Stage 2). If a match is detected, the compressor determines that the input block is a duplication of the prior received input block reflected by the matching hash value stored in the block hash table. In that event, compression by the first stage is possible. Regardless of whether a match is detected or not, the block level LRC does not store the input block of bytes in a cache. Only the collision-resistant hash of the block is added to the hash table. This permits the compressor to operate as if it has a large memory, without actually requiring the storage space for storing the blocks. It should be noted that the determination of whether an input block is a duplication of a prior input block represents an assumption based on matching hash values, but that such an assumption can be made with a very high probability, since the block hash is a strong collision resistant hash (e.g., SHA-1). For example, a 20 MB block hash table can store one million SHA-1 hash values, which is equivalent to storing one million respective data blocks of say 1500 packets each (a 20 MB hash cache achieves the equivalent storage of a 1.5 GB cache, which reflects a history of one million data blocks as a basis for compression matches). Li: [0102]-[0104] Base Color Index Map Mode – Introduction, [0103] In BCIM mode, a video encoder or image encoder encodes sample values using index values that represent base colors. Each of the index values is associated with a different value (“base color”) among the sample values. During encoding, the sample values are replaced with corresponding index values. The encoder encodes and signals a table of index values and corresponding base colors (“base color table”) as well as the arrangement of index values that represent the sample values (“index map”). A video decoder or image decoder receives and decodes the table of index values and corresponding base colors. Using that base color table, the decoder replaces index values of the index map with base colors for the original sample values. [0104] FIG. 7 shows a block (710) of sample values s in a two-dimensional arrangement with dimensions i, j, for 0≦i≦7 and 0≦j≦7. In FIG. 7, the sample values s represent intensity or brightness values for screen capture content. The sample values s include sections of uniform values and strong patterns. The block (710) includes sample values 26, 85, 41, 127, 168 and 200. [0105] The encoder creates a base color table (720) that assigns index values to corresponding base colors. In the example of FIG. 7, the index value 0 is assigned to the sample value 200, the index value 1 is assigned to the sample value 168, and so on. The encoder can assign index values to base colors according to their likelihood of occurrence in the picture, such that more common sample values have lower index values and less common sample values have higher index values, which tends to result in more efficient coding if lower index values are represented with fewer bits. Alternatively, the encoder can assign index values to base colors according to order of appearance as a block is scanned, relying on later processes such as prediction to exploit redundancy among the index values of the index map. The base color table (720) can be implemented as a look-up table or other data structure. [0106] FIG. 7 shows a block (730) in which sample values s are replaced with corresponding index values n. The process of replacing sample values with index values is lossless. Alternatively, in a lossy compression variation, a sample value can be replaced with the index value representing the base color closest to the sample value, if an exact match is not available. This can reduce the size of the base color table (720) but also introduce perceptible distortion. Another approach to handling sample values not represented with index values (so-called exception values) is described below. [0107] The encoder encodes and outputs the base color table (720) as well as an index map with elements representing the block (730) of index values n. For example, the encoder uses a coefficient coding syntax structure to represent elements of the block (730), as described below. As part of the encoding, the index values n for the block (730) can be processed with further mapping operations and/or prediction.)
Conclusion
The prior art made of record in form PTO-892 and not relied upon is considered pertinent to applicant's disclosure.
PNG
media_image1.png
222
922
media_image1.png
Greyscale
Any inquiry concerning this communication or earlier communications from the examiner should be directed to TAHMINA ANSARI whose telephone number is 571-270-3379. The examiner can normally be reached on IFP Flex - Monday through Friday 9 to 5.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, O’NEAL MISTRY can be reached on 313-446-4912. The fax phone numbers for the organization where this application or proceeding is assigned are 571-273-8300 for regular communications and 571-273-8300 for After Final communications. TC 2600’s customer service number is 571-272-2600.
Any inquiry of a general nature or relating to the status of this application or proceeding should be directed to the receptionist whose telephone number is 571-272-2600.
2674
/Tahmina Ansari/
June 18, 2026
/TAHMINA N ANSARI/Primary Examiner, Art Unit 2674
Prosecution Insights