# US 12,008,791 B2 · Image data compression > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,008,791 B2 - Document ID: US12008791B2 - Status: Granted - Kind: B2 - Application number: 17/213,628 - Filed: 2021-03-26 - Published: 2021-09-30 - Granted: 2024-06-11 - Earliest claimed: 2020-03-26 - Assignees: Imagination Technologies Limited - Applicants: Imagination Technologies Limited - Inventors: Xile Yang - Web page: https://patentgrep.com/patent/US12008791B2 ## CPC - G06T 9/00: Image coding (bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00) - G06T 9/005: {Statistical coding, e.g. Huffman, run length coding} - G06T 9/004: {Predictors, e.g. intraframe, interframe coding} - H04N 19/124: Quantisation - H04N 19/146: Data rate or code amount at the encoder output - H04N 19/176: the region being a block, e.g. a macroblock - H04N 19/182: the unit being a pixel - H04N 19/423: characterised by memory arrangements (H04N19/433 takes precedence) - H04N 19/50: using predictive coding (H04N19/61 takes precedence) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract A computer-implemented method and a compression unit for performing lossy compression on a block of image data in accordance with a multi-level difference table. The block of image data comprises a plurality of image element values, wherein each level of the multi-level difference table comprises a plurality of entries. An origin value for the block of image data is determined. A level within the multi-level difference table for the block of image data is determined. For each image element value in the block of image data, one of the entries at the determined level within the multi-level difference table is selected. A compressed block of data for the block of image data is formed, wherein the compressed block of data comprises: (i) data representing the determined origin value, (ii) an indication of the determined level, and (iii) for each image element value in the block of image data, an indication of the selected entry for that image element value. ## Claims ### Claim 1 A computer-implemented method of performing lossy compression on a plurality of blocks of image data in accordance with a multi-level difference table, wherein the blocks of image data relate to respective channels of multi-channel image data, wherein each block of image data comprises a plurality of image element values, and wherein each level of the multi-level difference table comprises a plurality of entries, the method comprising compressing the block of image data for each of the different channels of the multi-channel image data independently by: determining an origin value for the block of image data; determining a level within the multi-level difference table for the block of image data; for each image element value in the block of image data, selecting one of the entries at the determined level within the multi-level difference table; and forming a compressed block of data for the block of image data, the compressed block of data comprising: (i) data representing the determined origin value, (ii) an indication of the determined level, and (iii) for each image element value in the block of image data, an indication of the selected entry for that image element value; wherein said determining a level within the multi-level difference table for the block of image data comprises: determining a maximum difference between the determined origin value and any one of the image element values in the block of image data, and selecting, from the multi-difference table, the level whose largest entry most closely represents the determined maximum difference. ### Claim 2 (depends on 1) The method of claim 1, wherein a size of a range of values represented by the entries in a level is different for different levels of the multi-level difference table. ### Claim 3 (depends on 1) The method of claim 1, wherein said determining an origin value for the block of image data comprises identifying a minimum image element value in the block of image data. ### Claim 4 (depends on 1) The method of claim 1, wherein the data representing the determined origin value has fewer bits than any one of the image element values in the block of image data. ### Claim 5 (depends on 1) The method of claim 1, wherein said selecting one of the entries at the determined level within the multi-level difference table, for each of the image element values in the block of image data, comprises: determining a difference value for the image element value by determining a difference between the determined origin value and the image element value; and selecting, from the determined level of the multi-level difference table, the entry which most closely represents the determined difference value. ### Claim 6 (depends on 1) The method of claim 1, wherein the first entry in each level of the multi-level difference table represents a value of zero. ### Claim 7 (depends on 1) The method of claim 1, wherein the number of bits used to represent the compressed block of data does not depend upon the values of the image element values in the block of image data, such that a compression ratio of the lossy compression is guaranteed. ### Claim 8 (depends on 1) The method of claim 1, wherein the image element values are in an integer format, and wherein the block of image data is compressed by performing operations including one or more of addition operations, subtraction operations and compare operations on the image element values in the integer format, but the method of compressing the block of image data does not involve performing any multiplication operations or division operations. ### Claim 9 (depends on 1) The method of claim 1, wherein the block of multi-channel image data is colour data for a block of colour values, comprising: (i) a first block of image data relating to a red channel of the block of colour values, (ii) a second block of image data relating to a green channel of the block of colour values, and (iii) a third block of image data relating to a blue channel of the block of colour values, and wherein before the three blocks of image data are compressed independently, colour decorrelation is performed on the colour values. ### Claim 10 (depends on 1) The method of claim 1, wherein the multi-channel image data is colour data in an RGB format such that each colour value comprises a red value (R), a green value (G) and a blue value (B), and the method comprises converting the colour data to a luma-chroma format which comprises: (i) a first block of image data relating to a luma channel (Y) for a block of colour values, (ii) a second block of image data relating to a first chroma channel (Cb) for the block of colour values, and (iii) a third block of image data relating to a second chroma channel (Cr) for the block of colour values, wherein after the colour data has been converted to the luma-chroma format, the three blocks of image data are compressed independently. ### Claim 11 (depends on 1) A method of compressing a block of image data, comprising: determining whether a lossless compression of the block of image data will satisfy a target compression ratio for the block of image data; and in response to determining that the lossless compression of the block of image data will not satisfy the target compression ratio, performing the lossy compression method of claim 1 on the block of image data, wherein a compression ratio of the lossy compression is guaranteed to satisfy the target compression ratio for the block of image data. ### Claim 12 (depends on 11) The method of claim 11, wherein said determining whether a lossless compression of the block of image data will satisfy a target compression ratio for the block of image data comprises: predicting an amount of compressed data that would result from performing said lossless compression on the block of image data; and determining whether said predicted amount of compressed data would satisfy the target compression ratio. ### Claim 13 (depends on 11) The method of claim 11, wherein said determining whether a lossless compression of the block of image data will satisfy a target compression ratio for the block of image data comprises: performing the lossless compression on the block of image data; and determining whether the amount of compressed data resulting from performing said lossless compression on the block of image data satisfies the target compression ratio. ### Claim 14 (depends on 11) The method of claim 11, wherein the block of image data is one of a plurality of blocks of image data representing an image, wherein there is a total image target compression ratio which relates to the whole image, and wherein the method comprises modifying the target compression ratio for the block of image data in dependence on the amount of compressed data that has been formed for other blocks of image data relating to the same image, such that the total image target compression ratio is satisfied. ### Claim 15 A compression unit configured to perform lossy compression on a plurality of blocks of image data in accordance with a multi-level difference table, wherein the blocks of image data relate to respective channels of multi-channel image data, wherein each block of image data comprises a plurality of image element values, and wherein each level of the multi-level difference table comprises a plurality of entries, the compression unit being configured to compress the block of image data for each of the different channels of the multi-channel image data independently by: origin value determination logic determining an origin value for the block of image data; level determination logic determining a level within the multi-level difference table for the block of image data; entry selection logic selecting, for each image element value in the block of image data, one of the entries at the determined level within the multi-level difference table; and compressed block formation logic forming a compressed block of data for the block of image data, the compressed block of data comprising: (i) data representing the determined origin value, (ii) an indication of the determined level, and (iii) for each image element value in the block of image data, an indication of the selected entry for that image element value; wherein said determining a level within the multi-level difference table for the block of image data comprises: determining a maximum difference between the determined origin value and any one of the image element values in the block of image data; and selecting, from the multi-level difference table, the level whose largest entry most closely represents the determined maximum difference. ### Claim 16 (depends on 15) A compression unit configured to compress a block of image data, the compression unit comprising: a first compression unit configured to perform lossless compression on a block of image data; a second compression unit according to claim 15 configured to perform lossy compression on a block of image data; and compression technique determination logic configured to determine whether a lossless compression of the block of image data performed by the first compression unit will satisfy a target compression ratio for the block of image data, wherein the compression technique determination logic is configured to, if it determines that the lossless compression of the block of image data will not satisfy the target compression ratio, cause the second compression unit to perform lossy compression on the block of image data, wherein a compression ratio of the lossy compression is guaranteed to satisfy the target compression ratio for the block of image data. ### Claim 17 A non-transitory computer readable storage medium having stored thereon a computer readable dataset description of a compression unit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture an integrated circuit embodying the compression unit, wherein the compression unit is configured to perform lossy compression on a plurality of blocks of image data in accordance with a multi-level difference table, wherein the blocks of image data relate to respective channels of multi-channel image data, wherein each block of image data comprises a plurality of image element values, and wherein each level of the multi-level difference table comprises a plurality of entries, the compression unit being configured to compress the block of image data for each of the different channels of the multi-channel image data independently by: origin value determination logic determining an origin value for the block of image data; level determination logic determining a level within the multi-level difference table for the block of image data; entry selection logic selecting, for each image element value in the block of image data, one of the entries at the determined level within the multi-level difference table; and compressed block formation logic forming a compressed block of data for the block of image data, the compressed block of data comprising: (i) data representing the determined origin value, (ii) an indication of the determined level, and (iii) for each image element value in the block of image data, an indication of the selected entry for that image element value; wherein said determining a level within the multi-level difference table for the block of image data comprises: determining a maximum difference between the determined origin value and any one of the image element values in the block of image data, and selecting, from the multi-level difference table, the level whose largest entry most closely represents the determined maximum difference. ### Claim 18 (depends on 1) The method of claim 1 wherein the multi-level difference table is predetermined.