# US 11,310,504 B2 · Complexity reduction for 32-p and 64-p LGT > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,310,504 B2 - Document ID: US11310504B2 - Status: Granted - Kind: B2 - Application number: 16/943,544 - Filed: 2020-07-30 - Published: 2022-02-03 - Granted: 2022-04-19 - Earliest claimed: 2020-07-30 - Assignees: Tencent America LLC - Applicants: Tencent America LLC - Inventors: Madhu Peringassery Krishnan; Xin Zhao; Shan Liu - Web page: https://patentgrep.com/patent/US11310504B2 ## CPC - H04N 19/625: using discrete cosine transform [DCT] - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - H04L 65/70: Media network packetisation - H04L 65/756: adapting media to device capabilities - H04N 19/12: Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264 - H04N 19/129: Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO] - H04N 19/132: Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking - H04N 19/134: characterised by the element, parameter or criterion affecting or controlling the adaptive coding - H04N 19/176: the region being a block, e.g. a macroblock - H04N 19/18: the unit being a set of transform coefficients - H04N 19/184: the unit being bits, e.g. of the compressed video stream - H04N 19/48: using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data (motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513) - H04N 19/60: using transform coding - H04N 19/423: characterised by memory arrangements (H04N19/433 takes precedence) - H04N 19/61: in combination with predictive coding - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method of coding image data performed by at least one processor, may include: receiving information regarding a data block of an image; determining whether at least one of a height or a width of a residual coding block corresponding to the data block of the image is greater than or equal to a pre-defined threshold; and based on determining that the at least one of the height or the width of the residual coding block is greater than or equal to the pre-defined threshold: identifying or generating a reduced-complexity residual coding block by reducing the number of non-zero coefficients in the residual coding block; and performing transform coding of the reduced-complexity residual coding block using a line graph transform (LGT) core to perform direct matrix multiplications for each of the horizontal and vertical dimensions of the reduced-complexity coding block. ## Claims ### Claim 1 A method of decoding a coded bitstream composed of compressed video/image data performed by at least one processor, the method comprising: receiving the coded bitstream composed of the compressed video/image data; generating a dequantized block by a process including entropy decoding the coded bitstream and dequantizing a block; determining whether at least one of a height or a width of the dequantized block is greater than or equal to a pre-defined threshold; and based on determining that the at least one of the height or the width of the dequantized block is greater than or equal to the pre-defined threshold: obtaining a reduced-complexity dequantized block based on the dequantized block and performing transform coding of the reduced-complexity dequantized block using a line graph transform (LGT) core to perform direct matrix multiplications for each of the horizontal and vertical dimensions of the reduced-complexity dequantized block, wherein the performing the transform coding includes determining an order of performing horizontal and vertical transforms to the reduced-complexity dequantized block when zero-out is enabled on LGT, depending on a ratio of width to height (M/N) of the dequantized block. ### Claim 2 (depends on 1) The method of claim 1, wherein the pre-defined threshold has a value corresponding to one of: 32 or 64. ### Claim 3 (depends on 1) The method of claim 1, wherein the pre-defined threshold has a value corresponding to one of: 32, 64, 128, or 256. ### Claim 4 (depends on 1) The method of claim 1, wherein the generating of the reduced-complexity dequantized block includes zeroing-out all coefficients except coefficients in an m×n subblock of the dequantized block, and the performing of the transform coding of the reduced-complexity dequantized block includes processing the m×n subblock of the dequantized block instead of processing the entire dequantized block. ### Claim 5 (depends on 4) The method of claim 4, wherein the m×n subblock includes a part of the dequantized block that has a frequency that is lower than a frequency of another part of the dequantized block. ### Claim 6 (depends on 4) The method of claim 4, wherein the m×n subblock has a smaller size than a remaining part of the dequantized block, wherein the dequantized block has dimensions M×N and m≤M and n≤N. ### Claim 7 (depends on 1) The method of claim 1, wherein the performing of the transform coding of the reduced-complexity dequantized block using the LGT core includes applying an N-point LGT core to the dequantized block, which has dimensions M×N, where zero-out has been performed to all coefficients of the M×N dequantized block except those in an m×n subblock of the M×N dequantized block, wherein m≤M and n≤N. ### Claim 8 (depends on 1) The method of claim 1, wherein the determining the order of the performing the horizontal and vertical transforms includes, for the reduced-complexity dequantized block with dimensions M×N and zero-out enabled for all coefficients except in an m×n subblock: based on M being greater than N, performing an M-point horizontal transform first, and then performing an N-point vertical transform second, or based on N being greater than M, performing an N-point vertical transform first, and then performing an M-point horizontal transform second, wherein m≤M and n≤N. ### Claim 9 A method of decoding a coded bitstream composed of compressed video/image data performed by at least one processor, the method comprising: receiving the coded bitstream composed of the compressed video/image data; generating a dequantized block by a process including entropy decoding the coded bitstream, and dequantizing a block; determining whether at least one of a height (N) or a width (M) of the dequantized block is greater than or equal to a pre-defined threshold; obtaining a reduced-complexity dequantized block based on the dequantized block; and based on determining that the at least one of the height or the width of the dequantized block is greater than or equal to the pre-defined threshold: performing transform coding of the reduced-complexity dequantized block using a line graph transform (LGT) core to perform direct matrix multiplications for each of the horizontal and vertical dimensions of the reduced-complexity dequantized block, wherein the obtaining the reduced-complexity dequantized block includes: based on a secondary transform being enabled for the M×N dequantized block with zero-out also enabled and an input to the secondary transform being first K coefficients along a scanning order, zeroing-out all coefficients of the dequantized block outside of an m×n subblock of the dequantized block. ### Claim 10 A method of decoding a coded bitstream composed of compressed video/image data performed by at least one processor, the method comprising: receiving the coded bitstream composed of the compressed video/image data; generating a dequantized block by a process including entropy decoding the coded bitstream and dequantizing a block; determining whether at least one of a height or a width of the dequantized block is greater than or equal to a pre-defined threshold; obtaining a reduced-complexity dequantized block based on the dequantized block; and based on determining that the at least one of the height or the width of the dequantized block is greater than or equal to the pre-defined threshold: performing transform coding of the reduced-complexity dequantized block using a line graph transform (LGT) core to perform direct matrix multiplications for each of the horizontal and vertical dimensions of the reduced-complexity dequantized block; and storing, in a memory, in advance, a pre-defined table that associates dequantized blocks of different block width and block height sizes (M×N) with subblocks of different subblock width and subblock height sizes (m×n), where all coefficients outside of the m×n region are zeroed-out. ### Claim 11 (depends on 1) The method of claim 1, wherein at least one of a block height or width of the dequantized block is greater than or equal to 32, and a block height and a width of the reduced-complexity dequantized block is 16×16. ### Claim 12 (depends on 1) The method of claim 1, wherein at least one of a block height or width of the dequantized block is greater than or equal to 64, and a block height and a width of the reduced-complexity dequantized block is 16×16. ### Claim 13 (depends on 1) A non-transitory computer-readable storage medium storing instructions that, when executed, cause a system or device comprising one or more processors to perform the method of claim 1. ### Claim 14 An apparatus comprising: at least one memory configured to store computer program code; and at least one processor configured to access the at least one memory and operate according to the computer program code, the computer program code comprising: receiving code configured to cause the at least one processor to receive a coded bitstream composed of compressed video/image data; generating code configured to cause the at least one processor to generate a dequantized block by a process including entropy decoding the coded bitstream and dequantizing a block; determining code configured to cause the at least one processor to determine whether at least one of a height or a width of the dequantized block is greater than or equal to a pre-defined threshold; and reduced-complexity code configured to cause the at least one processor to: based on determining that the at least one of the height or the width of the dequantized block is greater than or equal to the pre-defined threshold: obtain a reduced-complexity dequantized block based on the dequantized block and perform transform coding of the reduced-complexity dequantized block using a line graph transform (LGT) core to perform direct matrix multiplications for each of the horizontal and vertical dimensions of the reduced-complexity dequantized block, wherein the at least one memory stores, in advance, a pre-defined table that associates dequantized blocks of different block width and block height (M×N) sizes with subblocks of different width and subblock height (m×n) sizes. ### Claim 15 (depends on 14) The apparatus of claim 14, wherein the reduced-complexity dequantized block is obtained by reducing the number of non-zero coefficients in the dequantized block by zeroing out all coefficients outside of an m×n region of the dequantized block based on the pre-defined table. ### Claim 16 (depends on 14) The apparatus of claim 14, further comprising: a display, wherein the computer program code further comprises: display code configured to cause the at least one processor to: generate a displayable image based at least in part on the transformed reduced-complexity dequantized block; and perform control so that the displayable image is displayed by the display. ### Claim 17 A method of coding image data performed by at least one processor, the method comprising: receiving information regarding a data block of an image; determining whether at least one of a height or a width of a residual coding block corresponding to the data block of the image is greater than or equal to a pre-defined threshold; and based on determining that the at least one of the height or the width of the residual coding block is greater than or equal to the pre-defined threshold: identifying or generating a reduced-complexity residual coding block by reducing the number of non-zero coefficients in the residual coding block; and performing transform coding of the reduced-complexity residual coding block using a line graph transform (LGT) core to perform direct matrix multiplications for each of the horizontal and vertical dimensions of the reduced-complexity residual coding block, wherein the performing the transform coding includes determining an order of performing horizontal and vertical transforms to the reduced-complexity residual coding block when zero-out is enabled on LGT, depending on a ratio of width to height (M/N) of the residual coding block. ### Claim 18 (depends on 17) The method of claim 17, wherein the pre-defined threshold has a value corresponding to one of: 32, 64, 128, or 256. ### Claim 19 (depends on 17) The method of claim 17, wherein the generating of the reduced-complexity residual coding block includes zeroing-out all coefficients except coefficients in an m×n subblock of the residual coding block, and the performing of the transform coding of the reduced-complexity residual coding block includes processing the m×n subblock of the residual coding block instead of processing the entire residual coding block.