Patent Description:
This disclosure relates to video encoding and video decoding.

<NUM>, ITU-T H. <NUM>, High Efficiency Video Coding (HEVC), and extensions of such standards.

For block-based video coding, a video slice (e.g., a video frame or a portion of a video frame) may be partitioned into video blocks, which may also be referred to as treeblocks, coding units (CUs) and/or coding nodes.

Spatial or temporal prediction results in a predictive block for a block to be coded. Residual data represents pixel differences between the original block to be coded and the predictive block. For further compression, the residual data may be transformed from the pixel domain to a transform domain, resulting in residual transform coefficients, which then may be quantized. Entropy coding may be applied to achieve even more compression. In patent document <CIT> there are provided methods and apparatus for transform selection in video coding. An apparatus includes a video encoder for encoding at least a block in a picture by selecting a transform to apply to a residue of the block from a set of two or more available transforms. The transform is selected based on at least one of an inter prediction mode used to predict at least one reference for the block, one or more values corresponding to a motion vector, a value of a residue of one or more previously encoded blocks, a value of prediction data for the block, one or more transform selections of one or more neighboring reconstructed blocks, and a quantization step applied to transform coefficients for the residue of the block. Patent document <CIT> is also referenced.

The invention is defined by the method of encoding video data of claim <NUM>, the video encoding device of claim <NUM>, the method of decoding video data of claim <NUM>, the video decoding device of claim <NUM> and the computer-readable storage medium having stored thereon of claim <NUM>. Advantageous aspects are defined in the dependent claims.

This disclosure describes techniques that may address problems with transform coding, which is a fundamental part of video compression standards. The techniques of this disclosure may reduce memory and computational complexity for large numbers of non-separable transforms, potentially enabling large coding gains with reasonable costs.

The techniques described herein may significantly reduce the computational complexity of the transforms that work best for video coding, both in terms of number of arithmetic operations, and the memory used to store the transform parameters, with little to no penalty in compression performance. The techniques of this disclosure may exploit those memory savings per transform, since the memory savings enable using a significantly larger number of transforms to improve coding gains. This disclosure describes how these techniques are to be used in practical video coding systems.

In accordance with the techniques described herein, rather than using one or more complex transformation processes, a video coder may add pre- or post-adjustment operations to a less complex transformation process to create a sequence of transforms that approximate the results of the one or more complex transformation processes. Although more processes may be applied in these techniques, by using fewer complex processes, the video blocks and the residual data may be processed more efficiently, especially when the blocks are larger than 8x8 in size. This is because the less complex processes may be applied much faster, exponentially in some instances. Further, the resulting video data may still be approximately equal in visual quality to what the resulting video data would be if the one or more complex transformation processes had been applied, resulting in more efficient processing without a loss in video quality.

Some example video coding standards use only one type of transform (Discrete Cosine Transform), but other standards, like HEVC, employ more than one type of transform to improve compression (see <NPL>, and<NPL>, the entire contents of each which are incorporated herein by reference). In the Alliance for Open Media Video <NUM> (AV1) standard, and the latest International Telecommunication Union/Moving Pictures Expert Group (ITU/MPEG) standardization, this approach is further extended by allowing several types of Discrete Sine and Cosine Transforms (DSTs and DCTs). Employing multiple transforms may result in significant compression improvements (coding gains above <NUM>%), but also creates several practical problems related to computational complexity, including (i) the amount of memory required to store the information about all the transforms, (ii) the unequal computation requirements for each transform, and (iii) resulting need for multiple implementation optimizations.

The techniques of this disclosure address some or all of the problems above by replacing the multiple transforms with pre-defined sets of low-complexity transforms, which may be combined with new computation structures (e.g., represented by sparse matrices and similar techniques) that allow efficient and sufficiently accurate approximation of the originally proposed transforms. Experimental simulations show that this approach can replace the five additional trigonometric transforms on the Joint Exploration Model (JEM) software with negligible coding losses, using only the well-known and highly optimized DCT type II, plus the new proposed approximation stages.

<FIG> is a block diagram illustrating an example video encoding and decoding system <NUM> configured to implement techniques of the disclosure. As shown in <FIG>, system <NUM> includes a source device <NUM> that provides encoded video data to be decoded at a later time by a destination device <NUM>. In particular, source device <NUM> provides the video data to destination device <NUM> via a computer-readable medium <NUM>. Source device <NUM> and destination device <NUM> may comprise any of a wide range of devices, including desktop computers, notebook (i.e., laptop) computers, tablet computers, set-top boxes, telephone handsets such as so-called "smart" phones, tablet computers, televisions, cameras, display devices, digital media players, video gaming consoles, video streaming device, or the like. In some cases, source device <NUM> and destination device <NUM> may be equipped for wireless communication. Thus, source device <NUM> and destination device <NUM> may be wireless communication devices. Source device <NUM> is an example video encoding device (i.e., a device for encoding video data). Destination device <NUM> is an example video decoding device (i.e., a device for decoding video data).

In the example of <FIG>, source device <NUM> includes a video source <NUM>, storage media <NUM> configured to store video data, a video encoder <NUM>, and an output interface <NUM>. Destination device <NUM> includes an input interface <NUM>, a storage media <NUM> configured to store encoded video data, a video decoder <NUM>, and display device <NUM>. In other examples, source device <NUM> and destination device <NUM> include other components or arrangements. For example, source device <NUM> may receive video data from an external video source, such as an external camera. Likewise, destination device <NUM> may interface with an external display device, rather than including an integrated display device.

The illustrated system <NUM> of <FIG> is merely one example. Techniques for processing video data may be performed by any digital video encoding and/or decoding device. Although generally the techniques of this disclosure are performed by a video encoding device, the techniques may also be performed by a video encoder/decoder, typically referred to as a "CODEC. " Source device <NUM> and destination device <NUM> are merely examples of such coding devices in which source device <NUM> generates coded video data for transmission to destination device <NUM>. In some examples, source device <NUM> and destination device <NUM> may operate in a substantially symmetrical manner such that each of source device <NUM> and destination device <NUM> include video encoding and decoding components. Hence, system <NUM> may support one-way or two-way video transmission between source device <NUM> and destination device <NUM>, e.g., for video streaming, video playback, video broadcasting, or video telephony.

Video source <NUM> of source device <NUM> may include a video capture device, such as a video camera, a video archive containing previously captured video, and/or a video feed interface to receive video data from a video content provider. As a further alternative, video source <NUM> may generate computer graphics-based data as the source video, or a combination of live video, archived video, and computer-generated video. Source device <NUM> may comprise one or more data storage media (e.g., storage media <NUM>) configured to store the video data. The techniques described in this disclosure may be applicable to video coding in general, and may be applied to wireless and/or wired applications. In each case, the captured, pre-captured, or computer-generated video may be encoded by video encoder <NUM>. Output interface <NUM> may output the encoded video information to a computer-readable medium <NUM>.

Destination device <NUM> may receive the encoded video data to be decoded via computer-readable medium <NUM>. Computer-readable medium <NUM> may comprise any type of medium or device capable of moving the encoded video data from source device <NUM> to destination device <NUM>. In some examples, computer-readable medium <NUM> comprises a communication medium to enable source device <NUM> to transmit encoded video data directly to destination device <NUM> in real-time. The encoded video data may be modulated according to a communication standard, such as a wireless communication protocol, and transmitted to destination device <NUM>. The communication medium may comprise any wireless or wired communication medium, such as a radio frequency (RF) spectrum or one or more physical transmission lines. The communication medium may form part of a packet-based network, such as a local area network, a wide-area network, or a global network such as the Internet. The communication medium may include routers, switches, base stations, or any other equipment that may be useful to facilitate communication from source device <NUM> to destination device <NUM>. Destination device <NUM> may comprise one or more data storage media configured to store encoded video data and decoded video data.

In some examples, encoded data may be output from output interface <NUM> to a storage device. Similarly, encoded data may be accessed from the storage device by input interface. The storage device may include any of a variety of distributed or locally accessed data storage media such as a hard drive, Blu-ray discs, DVDs, CD-ROMs, flash memory, volatile or non-volatile memory, or any other suitable digital storage media for storing encoded video data. In a further example, the storage device may correspond to a file server or another intermediate storage device that may store the encoded video generated by source device <NUM>. Destination device <NUM> may access stored video data from the storage device via streaming or download. The file server may be any type of server capable of storing encoded video data and transmitting that encoded video data to the destination device <NUM>. Example file servers include a web server (e.g., for a website), an FTP server, network attached storage (NAS) devices, or a local disk drive. Destination device <NUM> may access the encoded video data through any standard data connection, including an Internet connection. This may include a wireless channel (e.g., a Wi-Fi connection), a wired connection (e.g., DSL, cable modem, etc.), or a combination of both that is suitable for accessing encoded video data stored on a file server. The transmission of encoded video data from the storage device may be a streaming transmission, a download transmission, or a combination thereof.

In some examples, system <NUM> may be configured to support one-way or two-way video transmission to support applications such as video streaming, video playback, video broadcasting, and/or video telephony.

Computer-readable medium <NUM> may include transient media, such as a wireless broadcast or wired network transmission, or storage media (that is, non-transitory storage media), such as a hard disk, flash drive, compact disc, digital video disc, Blu-ray disc, or other computer-readable media. In some examples, a network server (not shown) may receive encoded video data from source device <NUM> and provide the encoded video data to destination device <NUM>, e.g., via network transmission. Similarly, a computing device of a medium production facility, such as a disc stamping facility, may receive encoded video data from source device <NUM> and produce a disc containing the encoded video data. Therefore, computer-readable medium <NUM> may be understood to include one or more computer-readable media of various forms, in various examples.

Input interface <NUM> of destination device <NUM> receives information from computer-readable medium <NUM>. The information of computer-readable medium <NUM> may include syntax information defined by video encoder <NUM> of video encoder <NUM>, which is also used by video decoder <NUM>, that includes syntax elements that describe characteristics and/or processing of blocks and other coded units, e.g., groups of pictures (GOPs). Storage media <NUM> may store encoded video data received by input interface <NUM>. Display device <NUM> displays the decoded video data to a user, and may comprise any of a variety of display devices such as a cathode ray tube (CRT), a liquid crystal display (LCD), a plasma display, an organic light emitting diode (OLED) display, or another type of display device.

Video encoder <NUM> and video decoder <NUM> each may be implemented as any of a variety of suitable fixed-function and/or programmable circuitry, such as one or more microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), discrete logic, software, hardware, firmware or any combinations thereof.

In some examples, video encoder <NUM> and video decoder <NUM> may operate according to a video coding standard such as an existing or future standard. Example video coding standards include, but are not limited to, ITU-T H. <NUM>, ISO/IEC MPEG-<NUM> Visual, ITU-T H. <NUM> or ISO/IEC MPEG-<NUM> Visual, ITU-T H. <NUM>, ISO/IEC MPEG-<NUM> Visual and ITU-T H. <NUM> (also known as ISO/IEC MPEG-<NUM> AVC), including its Scalable Video Coding (SVC) and Multi-View Video Coding (MVC) extensions. In addition, a new video coding standard, namely High Efficiency Video Coding (HEVC) or ITU-T H. <NUM>, including its range and screen content coding extensions, 3D video coding (3D-HEVC) and multiview extensions (MV-HEVC) and scalable extension (SHVC), has recently been developed by the Joint Collaboration Team on Video Coding (JCT-VC) of ITU-T Video Coding Experts Group (VCEG) and ISO/IEC Motion Picture Experts Group (MPEG). Alternatively, video encoder <NUM> and video decoder <NUM> may operate according to other proprietary or industry standards, such as the Joint Exploration Test Model (JEM) or ITU-T H. <NUM>, also referred to as Versatile Video Coding (VVC). The techniques of this disclosure, however, are not limited to any particular coding standard.

In HEVC and other video coding specifications, a video sequence typically includes a series of pictures. Pictures may also be referred to as "frames. " A picture may include three sample arrays, denoted SL, SCb, and SCr. SL is a two-dimensional array (i.e., a block) of luma samples. SCb is a two-dimensional array of Cb chrominance samples. Scr is a two-dimensional array of Cr chrominance samples. Chrominance samples may also be referred to herein as "chroma" samples. In other instances, a picture may be monochrome and may only include an array of luma samples.

To generate an encoded representation of a picture, video encoder <NUM> may generate a set of coding tree units (CTUs). Each of the CTUs may comprise a coding tree block of luma samples, two corresponding coding tree blocks of chroma samples, and syntax structures used to code the samples of the coding tree blocks. In monochrome pictures or pictures having three separate color planes, a CTU may comprise a single coding tree block and syntax structures used to code the samples of the coding tree block. A coding tree block may be an NxN block of samples. A CTU may also be referred to as a "tree block" or a "largest coding unit" (LCU). The CTUs of HEVC may be broadly analogous to the macroblocks of other standards, such as H. However, a CTU is not necessarily limited to a particular size and may include one or more coding units (CUs). A slice may include an integer number of CTUs ordered consecutively in a raster scan order.

This disclosure may use the term "video unit" or "video block" or "block" to refer to one or more sample blocks and syntax structures used to code samples of the one or more blocks of samples. Example types of video units may include CTUs, CUs, PUs, transform units (TUs), macroblocks, macroblock partitions, and so on. In some contexts, discussion of PUs may be interchanged with discussion of macroblocks or macroblock partitions. Example types of video blocks may include coding tree blocks, coding blocks, and other types of blocks of video data.

To generate a coded CTU, video encoder <NUM> may recursively perform quad-tree partitioning on the coding tree blocks of a CTU to divide the coding tree blocks into coding blocks, hence the name "coding tree units. " A coding block is an NxN block of samples. A CU may comprise a coding block of luma samples and two corresponding coding blocks of chroma samples of a picture that has a luma sample array, a Cb sample array, and a Cr sample array, and syntax structures used to code the samples of the coding blocks. In monochrome pictures or pictures having three separate color planes, a CU may comprise a single coding block and syntax structures used to code the samples of the coding block.

Video encoder <NUM> may partition a coding block of a CU into one or more prediction blocks. A prediction block is a rectangular (i.e., square or non-square) block of samples on which the same prediction is applied. A prediction unit (PU) of a CU may comprise a prediction block of luma samples, two corresponding prediction blocks of chroma samples, and syntax structures used to predict the prediction blocks. In monochrome pictures or pictures having three separate color planes, a PU may comprise a single prediction block and syntax structures used to predict the prediction block. Video encoder <NUM> may generate predictive blocks (e.g., luma, Cb, and Cr predictive blocks) for prediction blocks (e.g., luma, Cb, and Cr prediction blocks) of each PU of the CU.

Video encoder <NUM> may use intra prediction or inter prediction to generate the predictive blocks for a PU. If video encoder <NUM> uses intra prediction to generate the predictive blocks of a PU, video encoder <NUM> may generate the predictive blocks of the PU based on decoded samples of the picture that includes the PU.

After video encoder <NUM> generates predictive blocks (e.g., luma, Cb, and Cr predictive blocks) for one or more PUs of a CU, video encoder <NUM> may generate one or more residual blocks for the CU. For instance, video encoder <NUM> may generate a luma residual block for the CU. Each sample in the CU's luma residual block indicates a difference between a luma sample in one of the CU's predictive luma blocks and a corresponding sample in the CU's original luma coding block. In addition, video encoder <NUM> may generate a Cb residual block for the CU. Each sample in the Cb residual block of a CU may indicate a difference between a Cb sample in one of the CU's predictive Cb blocks and a corresponding sample in the CU's original Cb coding block. Video encoder <NUM> may also generate a Cr residual block for the CU. Each sample in the CU's Cr residual block may indicate a difference between a Cr sample in one of the CU's predictive Cr blocks and a corresponding sample in the CU's original Cr coding block.

Furthermore, video encoder <NUM> may decompose the residual blocks into one or more transform blocks. For instance, video encoder <NUM> may use quad-tree partitioning to decompose the residual blocks (e.g., the luma, Cb, and Cr residual blocks) of a CU into one or more transform blocks (e.g., luma, Cb, and Cr transform blocks). A transform block is a rectangular (e.g., square or non-square) block of samples on which the same transform is applied. A transform unit (TU) of a CU may comprise a transform block of luma samples, two corresponding transform blocks of chroma samples, and syntax structures used to transform the transform block samples. Thus, each TU of a CU may have a luma transform block, a Cb transform block, and a Cr transform block. The luma transform block of the TU may be a sub-block of the CU's luma residual block. The Cb transform block may be a sub-block of the CU's Cb residual block. The Cr transform block may be a sub-block of the CU's Cr residual block. In monochrome pictures or pictures having three separate color planes, a TU may comprise a single transform block and syntax structures used to transform the samples of the transform block.

As another example, video encoder <NUM> and video decoder <NUM> may be configured to operate according to JEM or VVC. According to JEM or VVC, a video coder (such as video encoder <NUM>) partitions a picture into a plurality of coding tree units (CTUs). Video encoder <NUM> may partition a CTU according to a tree structure, such as a quadtree-binary tree (QTBT) structure or Multi-Type Tree (MTT) structure. The QTBT structure removes the concepts of multiple partition types, such as the separation between CUs, PUs, and TUs of HEVC. A QTBT structure includes two levels: a first level partitioned according to quadtree partitioning, and a second level partitioned according to binary tree partitioning. A root node of the QTBT structure corresponds to a CTU. Leaf nodes of the binary trees correspond to coding units (CUs).

In some examples, video encoder <NUM> and video decoder <NUM> may use a single QTBT structure to represent each of the luminance and chrominance components, while in other examples, video encoder <NUM> and video decoder <NUM> may use two or more QTBT structures, such as one QTBT structure for the luminance component and another QTBT structure for both chrominance components (or two QTBT structures for respective chrominance components).

In some examples, video encoder <NUM> may predict the current CU using unidirectional prediction or bi-directional prediction.

JEM and VVC also provide an affine motion compensation mode, which may be considered an inter-prediction mode. In affine motion compensation mode, video encoder <NUM> may determine two or more motion vectors that represent non-translational motion, such as zoom in or out, rotation, perspective motion, or other irregular motion types.

To perform intra-prediction, video encoder <NUM> may select an intra-prediction mode to generate the prediction block. JEM and VVC provide sixty-seven intra-prediction modes, including various directional modes, as well as planar mode and DC mode. In general, video encoder <NUM> selects an intra-prediction mode that describes neighboring samples to a current block (e.g., a block of a CU) from which to predict samples of the current block. Such samples may generally be above, above and to the left, or to the left of the current block in the same picture as the current block, assuming video encoder <NUM> codes CTUs and CUs in raster scan order (left to right, top to bottom).

Video encoder <NUM> may apply one or more transforms to a transform block of a TU to generate a coefficient block for the TU. For instance, video encoder <NUM> may apply one or more transforms to a luma transform block of a TU to generate a luma coefficient block for the TU. A coefficient block may be a two-dimensional array of transform coefficients. A transform coefficient may be a scalar quantity. Video encoder <NUM> may apply one or more transforms to a Cb transform block of a TU to generate a Cb coefficient block for the TU. Video encoder <NUM> may apply one or more transforms to a Cr transform block of a TU to generate a Cr coefficient block for the TU.

After generating a coefficient block (e.g., a luma coefficient block, a Cb coefficient block or a Cr coefficient block), video encoder <NUM> may quantize the coefficient block. Quantization generally refers to a process in which transform coefficients are quantized to possibly reduce the amount of data used to represent the transform coefficients, providing further compression. After video encoder <NUM> quantizes a coefficient block, video encoder <NUM> may entropy encode syntax elements indicating the quantized transform coefficients. For example, video encoder <NUM> may perform Context-Adaptive Binary Arithmetic Coding (CABAC) on the syntax elements indicating the quantized transform coefficients.

Video encoder <NUM> may output a bitstream that includes a sequence of bits that forms a representation of coded pictures and associated data. Thus, the bitstream comprises an encoded representation of video data. The bitstream may comprise a sequence of network abstraction layer (NAL) units. A NAL unit is a syntax structure containing an indication of the type of data in the NAL unit and bytes containing that data in the form of a raw byte sequence payload (RBSP) interspersed as necessary with emulation prevention bits. Each of the NAL units may include a NAL unit header and encapsulates a RBSP. The NAL unit header may include a syntax element indicating a NAL unit type code. The NAL unit type code specified by the NAL unit header of a NAL unit indicates the type of the NAL unit. A RBSP may be a syntax structure containing an integer number of bytes that is encapsulated within a NAL unit. In some instances, an RBSP includes zero bits.

Video decoder <NUM> may receive a bitstream generated by video encoder <NUM>. In addition, video decoder <NUM> may parse the bitstream to obtain syntax elements from the bitstream. Video decoder <NUM> may reconstruct the pictures of the video data based at least in part on the syntax elements obtained from the bitstream. The process to reconstruct the video data may be generally reciprocal to the process performed by video encoder <NUM>. For instance, video decoder <NUM> may use motion vectors of PUs to determine predictive blocks for the PUs of a current CU. In addition, video decoder <NUM> may inverse quantize coefficient blocks of TUs of the current CU. Video decoder <NUM> may perform inverse transforms on the coefficient blocks to reconstruct transform blocks of the TUs of the current CU. Video decoder <NUM> may reconstruct the coding blocks of the current CU by adding the samples of the predictive blocks for PUs of the current CU to corresponding samples of the transform blocks of the TUs of the current CU. By reconstructing the coding blocks for each CU of a picture, video decoder <NUM> may reconstruct the picture.

Transform coding is a fundamental part of all modern video coding standards, like High-Efficiency Video Coding (HEVC). It is known that optimal transform coding should employ the matrix-based Karhunen-Loève Transforms (KLTs) (or similarly adaptive transforms), because such transforms can be optimized to particular signal statistics. However, the matrix implementation tends to require a relatively high number computations and a relatively high amount of memory. In practice, fixed separable transforms like the Discrete Cosine Transform (DCT) use fewer computations and less memory to implement the transform, and therefore, have been widely adopted.

In accordance with the techniques described herein, video encoder <NUM> may perform a first prediction process on a first block of video data and a second prediction process on a second block of video data to produce a first residual and a second residual, respectively. Video encoder <NUM> may, for the first residual, determine that a first transform process of a plurality of transform processes is to be applied to the first residual. Video encoder <NUM> may then apply the first transform process to the first residual to generate first transform coefficients for the first block of video data. For the second residual, video encoder <NUM> may determine that a second transform process is to be applied to the second residual, where the second transform process includes the first transform process and at least one of a pre-adjustment operation or a post-adjustment operation to apply to the second residual. Video encoder <NUM> may apply the first transform process and at least one of the pre-adjustment operation or the post-adjustment operation to the second residual to generate second transform coefficients for the second block of video data. If the pre-adjustment operation is applied, transform processing unit <NUM> applies the pre-adjustment operation prior to applying the first transform process. If the post-adjustment operation is applied, transform processing unit <NUM> applies the post-adjustment operation after applying the first transform process. By combining the first transform process and the pre- and/or post-adjustment operations, the second transform process can be an approximation of and a substitution for a more complex trigonometric transform without needing to perform the computationally heavy operations of the complex trigonometric transform and without having to store the full matrices in memory. Video encoder <NUM> may then proceed to entropy encode the first transform coefficients and the second transform coefficients.

Further in accordance with the techniques described herein, video decoder <NUM> may, for a first block of a plurality of blocks of video data, determine that a first inverse transform process of a plurality of inverse transform processes is to be applied to the first block. Video decoder <NUM> may then apply the first inverse transform process to first transform coefficients of the first block to generate a first residual. Video decoder <NUM> may decode the first residual to produce a first decoded block. For the second block, video decoder <NUM> may determine that a second inverse transform process is to be applied to the second block, where the first inverse transform process and at least one of a pre-adjustment operation or a post-adjustment operation. Video decoder <NUM> may apply the first inverse transform process and the at least one of the pre-adjustment operation or the post-adjustment operation to second transform coefficients of the second block to generate a second residual. If the pre-adjustment operation is applied, video decoder <NUM> applies the pre-adjustment operation prior to applying the first inverse transform process. If the post-adjustment operation is applied, video decoder <NUM> applies the post-adjustment operation after applying the first inverse transform process. Video decoder <NUM> may decode the second residual to produce a second decoded block. By combining the first transform process and the pre- and/or post-adjustment operations, this combination of operations can be an approximation of and a substitution for a more complex trigonometric transform without needing to perform the computationally heavy operations of the complex trigonometric transform and without having to store the full matrices in memory. Video decoder <NUM> may then proceed to decode the video data based at least in part on the first decoded block and the second decoded block.

<FIG> is a block diagram illustrating an example system <NUM> for hybrid video encoding with transform selection. The techniques of this disclosure are applicable to the framework of adaptive transform coding shown in <FIG>, where, for each block of prediction residuals, different transforms can be chosen by the encoder, and the choice of transform is encoded as side information.

<FIG> shows a diagram of a video encoding system <NUM> (i.e., an example video encoder, such as video encoder <NUM>), where video frames are first divided into pixel blocks (block separation <NUM>). Example types of pixel blocks may include coding blocks of CUs. Furthermore, in <FIG>, for each block, video encoding system <NUM> subtracts each pixel value from its predicted value (<NUM>). The video encoder numerically transforms the blocks of differences (i.e., residuals) using a linear operation (block transform <NUM>). In the example of <FIG>, r denotes residual data, Ttr denotes transformed residual data, and t denotes an indication of which transform was applied to the residual to generate Ttr.

A linear transformation can be implemented by matrix-vector multiplications, but video coding applications have been using some special fast transforms that have fixed coefficients derived from trigonometric functions that can be computed much more efficiently than the equivalent matrix-vector products. However, in the context of this disclosure, it is important to note that the concept of computational efficiency has been changing with the advent of new hardware technologies. For instance, in some applications, decreasing the computation latency may be more important than reducing the number of arithmetic operations, which is the conventional measure of computational complexity.

In <FIG>, the video encoder may quantize the transformed residual data (quantization <NUM>) and inverse quantize (inverse quantization <NUM>) the quantized transformed residual data. The video encoder may apply an inverse transform to the inverse quantized transformed residual data (inverse transform <NUM>) to recover the residual data. A frame buffer <NUM>, also called decoded picture buffer (DPB), of the video encoder stores reconstructed pixel blocks determined based on the residual data. The video encoder may use reconstructed pixel blocks stored in frame buffer <NUM> for prediction of other pixel blocks (block prediction <NUM>). In the example of <FIG>, the inverse transform applied to the transformed residual data by the video encoder may be determined based on the transform previously applied to generate the transformed residual data. The indication of which transform was applied to generate the transformed residual data may be provided to an entropy encoding unit <NUM> of the video encoder. The entropy encoding unit <NUM> may entropy encode a syntax element indicating the transform along with syntax elements indicating the quantized transformed residual data.

Older video coding standards used only one type of block transform. To improve compression, newer standards increasingly use multiple transforms. This is indicated in the diagram of <FIG> by the dashed line connecting block transform <NUM> with entropy coding <NUM> and transform bank <NUM>, which represents the side information that the encoder uses to convey to the decoder which inverse transform is to be applied during decoding.

To reduce computational complexity, the block transforms are commonly computed in a separable manner, i.e., the horizontal and vertical lines of samples (e.g., luma and chroma samples) are transformed independently, as shown in <FIG>. In an adaptive transform scheme, two possible choices for selecting different transforms, during a transform directional pass, may include a set of transforms done in the horizontal and vertical directions (horizontal and vertical transform passes, respectively).

<FIG> show example options for applying transforms to a two-dimensional block of video residuals. <FIG> is a conceptual diagram illustrating an example option for computing separable transforms in a two-dimensional block of pixel residuals. <FIG> is a conceptual diagram illustrating an example option for computing non-separable transforms in a two-dimensional block of pixel residuals.

In the first option (e.g., <FIG>), called separable transforms, the residuals are transformed separately, first in rows and then in columns (or vice-versa), as indicated by the arrows in <FIG>. More specifically, for each respective row of an WxH input block <NUM>, a video encoder/decoder (generically referred to as video coder) produces a row of an intermediate block <NUM> by multiplying a vector consisting of elements of the respective row by an WxH transform matrix. For each respective column of intermediate block <NUM>, the video coder produces a column of an output block by multiplying a vector consisting of elements of the respective column by an WxH transform matrix. To reduce computational complexity the block transforms are commonly computed in a separable manner, i.e., the horizontal and vertical lines are transformed independently, as shown in <FIG>.

In the second type of block transformation (e.g., <FIG>), called non-separable transforms, all residuals are put together into a single vector, as shown in <FIG>, and are transformed together. This option does not exploit the two-dimensional structure of the pixel blocks, but this option is more general and powerful, and can exploit directional features different from horizontal and vertical. For instance, for an input block <NUM> consisting of WxH values, the transform matrix is W<NUM>×H<NUM>. To determine an output block or vector <NUM>, the video coder multiplies input block <NUM> by the transform matrix.

In some example video coding standards, separable fixed passes are used. In addition, the same transform is used for both the horizontal and the vertical transform passes. Separable fixed passes with different transforms in each pass were adopted in JEM in Joint Video Experts Team (JVET) of ITU-T SG <NUM> WP <NUM> and ISO/IEC JTC <NUM>/SC <NUM>/WG <NUM>, JEM Software. Testing has shown that better compression can be obtained with separable variable passes. However, with separable variable passes, the coding process may have larger computational complexity.

To minimize the computational complexity, some example video coding standards use only one block size and one type of separable transform (the DCT). With the recent adoption of HEVC, separable transforms are defined for several block sizes, and the Discrete Sine Transform (DST) has been adopted.

Denoting the input and output vectors of the transform by N-dimensional vectors x and y, respectively, any linear transform of dimension N can be represented as <MAT> where T is an N × N transform matrix. Unless stated otherwise, in this disclosure, symbol N is used to denote the transform's dimension. To simplify the quantization process, transform matrices are normally derived from orthogonal matrices, i.e., those that satisfy <MAT> In practice, the computations are done with a version of an orthogonal transform that has been scaled and has its elements converted to integers.

There are many sets of orthogonal transforms that can be defined by trigonometric functions, but one group became more widely known after it was demonstrated that the trigonometric functions were useful for media compression. Those Discrete Trigonometric Transforms (DTTs) are different types of Discrete Cosine Transform (DCT) and Discrete Sine Transform (DST), and both types are by convention numbered between <NUM> and <NUM>. Two scaling functions may be used to construct the transforms: <MAT> <MAT>.

Using those scaling functions, the matrices defining the Discrete Cosine Transforms are:.

Using the same scaling function bN (n) as used for DCT definitions, the matrices of the Discrete Sine Transforms are defined as:.

There are many mathematical properties connecting the sixteen Discrete Trigonometric Transforms listed above. Given a transform matrix T, some of the most important relationships are defined by matrix transposition, which correspond to the inverse transform. This is due to all Discrete Trigonometric Transforms being defined to be orthogonal. The "reflection" operations FTS and STF, show the orthogonal nature of the DTT matrices, where F and S are orthogonal involutory matrices defined by: <MAT> <MAT>.

Table I contains a list of those relationships.

The transposition and reflection transformations (or transform conversions) are useful in practice because the transformations represent operations that can be implemented with nearly negligible additional computational complexity and memory, and thus all transforms obtained by those transformations have practically the same computational complexity.

For instance, there are several methods for efficiently computing the DCT-<NUM>. Since the transforms DCT-<NUM>, DST-<NUM>, and DST-<NUM> are all convertible to the DCT-<NUM> by those transposition and reflection transformations (cf. Table I), each of these transforms can be computed efficiently using the same equally efficient methods. The techniques described herein exploit this fact.

In some instances, such as the general case 68A example of <FIG>, a single transformation matrix, such as any of the DTT transformations, may be applied to the video data (e.g., either the transform coefficients in the decoding process or the residuals of the encoding process).

Since linear transforms can be represented as a matrix-vector product, the maximum computational complexity of a Discrete Trigonometric Transform (number of operations per computation, and memory for its representation) is proportional to N<NUM>.

Due to their similarity to the Discrete Fourier Transform (DFT), those transforms may be computed efficiently using Fast-Fourier-Transform (FFT) algorithms with complexity proportional to N×F, where F depends on the prime factorization of N or N - <NUM>. For example, if N = <NUM>K then F = K, and the complexity is proportional to N log<NUM> N, which is commonly much lower than N<NUM>. Since the complexity can vary significantly for different values of N, the cases N = <NUM>K are commonly chosen in compression applications.

Several alternative fast methods have been proposed for DTTs that use their specific properties, but these alternatives also have large variations in complexity because, as shown in Table II, the factor that defines complexity is not equal to N for all DTTs.

Several efficient transform computation algorithms are based on the factorization of the transform matrices into sparse factors. The focus of the techniques described herein is based on an exploitation of the fact that, when N is even, the matrices of DCT-<NUM>, DCT-<NUM>, DST-<NUM>, and DCT-<NUM> have even-numbered rows with elements that have even symmetry, and the odd-numbered rows have elements with odd symmetry.

Those symmetries allow the transform to be computed with about half the complexity using the scheme 68B shown on <FIG>, where A and B are pre/post processing low complexity transforms, while R and S are N/<NUM> × N/<NUM> matrices.

One feature of some DTTs is that this factorization enables further complexity reductions. For instance, for the DCT-<NUM>, Matrix R corresponds to the DCT-<NUM> of dimension N/<NUM>. Thus, the subdivision process can be continued in a recursive manner, further reducing computational complexity. Further, Matrix S corresponds to the DCT-<NUM> of dimension N/<NUM>, which can also be computed efficiently. The DST-<NUM> can be computed from the DCT-<NUM> by simply changing matrices A and B. The DCT-<NUM> and DST-<NUM> can be computed from the DCT-<NUM> using a similar process, replacing matrix R with its transpose, and also changing matrices A and B.

To simplify this presentation, those features may not be explicitly mentioned, but those features should be implicitly considered in <FIG>, and other similar diagrams referring to "fast trigonometric transforms.

Adaptive Multiple Transforms (AMT), which is used in one example of the JEM (Joint Experimental Model) of the ITU/MPEG JVET standardization, employs trigonometric transforms. The AMT coding method employs the following trigonometric transforms DCT-<NUM> (encoder only), DCT-<NUM> (decoder only, is the inverse of DCT-<NUM>), DCT-<NUM>, DCT-<NUM>, DST-<NUM>, DST-<NUM> (decoder only, is the inverse of DST-<NUM>), and DST-<NUM> (encoder only).

Current computational resources may be able to process multiple transforms when N ≤ <NUM>, but increasingly larger blocks are being used for video coding. It is possible that the new standard may require transforms for block dimensions equal to <NUM>, or maybe even as large as <NUM>.

For a custom hardware implementation, transformations with different forms of complexity reduction techniques may require separate hardware designs for each case. Hardware and development costs are also heavily dependent on the most complex case (i.e., the worst-case scenario), and not the average complexity. It is advantageous to have a unified approach for transformation computations by enabling a single optimized implementation.

Some proposed AMT methods for JEM violates all of the above requirements, since some example AMT methods have different transforms with quite different minimum computational requirements. The methods for minimizing computational complexity are different among transforms, and even for the same transform, for different transform dimensions For some transforms and dimensions, no efficient computation method (better than direct matrix-vector computation) is known. This last problem is particularly significant for the larger transform dimensions, making the use of those transforms in large blocks prohibitively expensive.

One difficulty with the family of AMT methods is that AMT methods should address two conflicting objectives. A variety of transforms is desired to improve compression efficiency. For instance, higher diversity and better results can be obtained using the Karhunen-Loève Transform (KLT), but there are no approaches for drastically reducing the computational complexity of general transforms. The DTTs that can be computed with minimal computational complexity do not provide the variety needed to achieve maximum coding gains. Additional DTTs are employed under the consideration that at least some of them can be computed with complexity smaller than N<NUM>.

The techniques of this disclosure may provide the same or nearly the same level of diversity provided by multiple DTTs, but with computational complexity comparable to the most efficient DTTs (for all transform types and dimensions). These techniques are based on the identification that the properties needed for providing more diversity, and minimizing the computational complexity, are not mutually exclusive. This happens because the coding gains are defined mostly by the first rows of the transform matrix, which should be similar to the first rows for the KLT matrix, while the other rows are less important. Mathematically this means that, if there is already a transform that can be computed with low complexity, some form of low-complexity "adjustments" may be made in a subspace of low dimensionality to obtain the variety of transforms needed to improve compression.

<FIG> are conceptual diagrams illustrating example low-complexity transform adjustment stages in accordance with one or more techniques described herein. <FIG> shows the general approach 70A where the optional pre-processing and post-processing stages, denoted by P and Q, "adjust" a transform that is defined by a matrix T, which can be computed with low complexity. This approach requires to define pre and post processing stages P and Q, which are called Low-Complexity Transform Adjustment Stages (LCTAS), also be computed with low complexity. The following sections define families of matrices that satisfy those requirements. A fast trigonometric transform example 70B is shown in <FIG>.

One observation is that the adjustment stages may be related to approximating other transforms, but the adjustment stages may not fit what is usually known as approximation. For example, to determine the adjustment stages that enable approximating the compression performance of the DST-<NUM> using the DST-<NUM>, a transform is created that "adjusts" the DST-<NUM> to be more similar to the DST-<NUM>. However, not all rows in the transform matrix need to be equally similar.

<FIG> show actual results for this example, for transforms of dimension N = <NUM>. <FIG> shows plots 72A-72P with the rows of the matrices corresponding to each transform (DST-<NUM>, adjusted, and DST-<NUM>). For easier identification of the approximation errors, <FIG> shows the plots of matrix differences 74A-74P, where it can be observed that the first rows, corresponding to the most important transform components, are much better approximated than the last rows.

<FIG> are conceptual diagrams 76A and 76B illustrating example band diagonal and block diagonal sparse orthogonal matrices in accordance with one or more techniques described herein. Matrix-vector products can be computed with relatively low-complexity if the matrix is known to be sparse (i.e., when most entries of the matrices are zeros). In general, any technique dealing with sparse matrices can be used. However, for video coding applications, in which the transforms matrices are not very large and computational costs are high, it is preferable to use matrices with pre-defined patterns of sparsity. This avoids additional memory used to represent the sparsity patterns, and requires simpler custom hardware designs.

Two useful types of sparse transforms are band matrices, which have nonzero elements only around the main diagonal, as shown in the examples of <FIG>. For those cases, the computational complexity of the matrix-vector product is N × B, where B is the matrix band width, i.e., the upper bound on the number of non-zero elements in each row. The examples in <FIG> were obtained with a matrix with band width equal to <NUM>. The band structure of transform matrices is easy to explain, but in terms of computational complexity, any matrix that has a number of nonzero elements significantly smaller than N<NUM>, in a fixed and easy to implement pattern that can be used for pre/post processing.

<FIG> is a conceptual "Butterfly" diagram representing a Givens orthogonal transformation in accordance with one or more techniques described herein. Transform computations can also be minimized using matrices that have been factorized into sets of parallel Givens rotations. Those pairwise transformation have the structure shown in <FIG>, and for that reason a commonly called computation "butterflies.

Thus, in the example of <FIG>, the butterfly receives rn and rm as inputs and also receives a parameter θ as input. The outputs of the butterfly are tn and tm. tm is calculated as cos(θ)rm - sin(θ)rn. tn is calculated as cos(θ)rn + sin(θ)rm. When applying an inverse transform, video decoder <NUM> may calculate rm as tmcos(θ) + tnsin(θ) and rn as - tmsin(θ) + tacos(θ). Although <FIG>, and other examples of this disclosure, are described with respect to Givens rotations, other transforms may be used instead of the Givens rotation, such as the Householder transformation, Euler rotations with <NUM> or more angles, and other transformations.

<FIG> is a conceptual diagram representing an example structure composed of parallel Givens rotations for transform adjustment in accordance with one or more techniques described herein. In a transform of dimension N, up to N/<NUM> rotations that can be computed in parallel, forming a parallel Givens pass. <FIG> shows an example of a transform of dimension N = <NUM>, implemented using four such passes. The configuration on <FIG> corresponds to band matrices, where the band width is equal to twice the number of passes. Similarly to the case of sparse matrices, any implementation that uses a number of rotations (butterflies) significantly smaller than N<NUM>, can be used for adjustment.

<FIG> are conceptual diagrams 78A and 78B representing an example replacement of multiple discrete trigonometric transforms with only the family of DCT-<NUM> transforms and a low complexity adaptation state, in accordance with one or more techniques described herein. A more specific example of its application is its use for eliminating higher-complexity transforms in the AMT video coding method. For that purpose, it is advantageous to use the DCT-<NUM>, DCT-<NUM>, DST-<NUM>, and DST-<NUM>, since these specific DTT functions correspond to the same type of transform (cf. Table I), which has been the most extensively studied and have low-complexity implementations. Furthermore, as can be seen in Table II, their complexity factor is well-matched to the dimensions used for video coding.

Experimental results show that using only a pre-processing adjustment stage (e.g., post-adjustment matrix Q in <FIG> not needed), all the remaining DTTs can be replaced with one of those transforms. Table III below shows which transform should be used (i.e., the "base" transform to be adjusted). <FIG> shows how the techniques described herein can be used to replace the multiple DTTs in the AMT coding method, using only the family of DCT-<NUM> transforms, plus an adjustment stage, which is an orthogonal band matrix. Experimental results show the techniques described herein to have very small loss when the number of non-zero elements in each row of the adjustment matrix P to be upper bounded by four.

A system for implementing separable transforms is shown in <FIG>, which a video encoder, such as video encoder <NUM>, could operate. Video encoder <NUM> may use the various components shown in <FIG> during an encoding process, the components block prediction unit <NUM>, residual buffer <NUM>, horizontal transform unit <NUM>, transform memory <NUM>, transform selection <NUM>, vertical transform unit <NUM>, and quantization and coding unit <NUM>. For comparing different transformation schemes, the computational complexity of each transform may be taken take into account the computational complexity of each transform. The computational complexity of a transform may depend on: (<NUM>) the amount of memory containing transform parameters, that may be accessed and copied, whenever a transform is computed (as indicated by lines <NUM> and <NUM> in <FIG>); and/or (<NUM>) the number of operations needed to compute each transform, commonly normalized in operations per pixel.

These complexity measures depend on the type of transform employed, and the type of directional pass. Table IV shows a comparison of different cases. The first two rows correspond to a set of four Discrete Cosine and Sine Transforms (DCT, DST), containing the DCT-<NUM> and DCT-<NUM>, and the DST-<NUM> and DST-<NUM>. This set may be referred to as the DCT-<NUM> "family" (since each transform can all be computed with basically the same algorithms for complexity reduction) and represent it as DCT-2F.

The next two rows represent transforms computed directly using matrix-vector products. Due to the limitations of the DCT-2F transforms, this approach has been used in the adaptive transform methods, both for fixed directional passes, and for adaptive directional passes As shown in Table IV, there were previously only two conflicting options:.

As shown in the next section, the techniques of this disclosure may greatly reduce this trade-off, allowing for a much more flexible set of transforms, with complexity slightly larger than that of DCT-2F.

The techniques described above for Low-Complexity Transform Adjustment Stages (LCTAS) enable video coding system <NUM> to employ adaptive transform coding, where one of the transforms of the DCT-<NUM> family is employed for most of the transform computation, while the diversity that enables better compression is provided by low complexity computations, which may be referred to as transform adjustment stages.

In the following discussion, note that the complexity of the adjustment stages is low both in terms of arithmetic operations, and the memory used to store the parameters of the adjustment stages. One property of LCTAS that is particularly useful in the separable transform use case is that the adjustment stages can use the same DCT-<NUM> family of transforms. The adjustment stages may use the same set of parameters, and therefore, only need some modifications that have very low complexity (e.g., few arithmetic operations, and no additional parameters).

The techniques of this disclosure are based on the identification that the properties needed for providing more diversity, and for minimizing the computational complexity, are not mutually exclusive. This happens because the coding gains are defined mostly by the first rows of the transform matrix, which should be similar to the first rows for the KLT matrix. The other rows of the transform matrix are less important in providing coding gains.

Mathematically, this means that, if a transform can be computed with low complexity, video encoder <NUM> and video decoder <NUM> may be configured with some form of low-complexity "adjustments" in a subspace of low dimensionality, to obtain a variety of transforms, which may then improve compression. As shown in Table IV above, assuming the bandwidth value B is relatively small compared to N (which generally holds because the matrices are sparse), the complexity of the LCTAS techniques of this disclosure is nearly the same as DCT-2F, while providing for greater flexibility. These techniques may therefore improve the functioning of computing devices, such as video encoders and decoders.

<FIG> shows a diagram with an implementation of the invention. In one example, video encoder <NUM> and video decoder <NUM> may be configured to perform the main computations using one of the transforms of the DCT-<NUM> family. For instance, video encoder <NUM> may use the various components shown in <FIG> during an encoding process, the components including block prediction unit <NUM>, residual buffer <NUM>, horizontal transform adjustment unit <NUM>, horizontal DCT-2F transform unit <NUM>, vertical transform adjustment unit <NUM>, transform memory <NUM>, transform selection <NUM>, vertical DCT-2F transform unit <NUM>, and quantization and coding unit <NUM>. As indicated by the dashed lines <NUM> and <NUM> in <FIG>, a single signal (e.g., using <NUM> bits) may be used to select which of the forms of the DCT-2F is to be used, while only parameters of adjustment stages need to be copied from transform memory, as indicated by lines <NUM> and <NUM>.

The complexity of this scheme is shown in the last two rows of Table IV above, where the LCTAS techniques of this disclosure provide diversity with significant reduction in memory access, compared to the full matrix schemes.

The techniques of this disclosure can be implemented in several ways. <FIG> show examples of a horizontal pass of a separable transform, in a <NUM>×<NUM> block, showing variations on how different transform adjustment stages can be assigned to the block lines. For instance, <FIG> shows an example of different adjustments being used for each of the lines transformed in a block. <FIG> shows pairs of lines using the same adjustments, and thus reducing memory access by half. More general schemes can be employed, where the number of adjustments is defined for different situations.

For instance, a coding tree unit may include eight rows of coding units and eight columns of coding units (sixty-four coding units in total). In some examples, every coding unit in the coding tree unit undergoes the same transform process. In other examples, each row of coding units may undergo the same transform process but with different pre- and/or post-adjustment operations applied to each row and to each column (i.e., up to sixteen different combinations of transform process and adjustment) to produce higher quality video data after decoding at the expense of more data stored in memory. In still other examples, each pair of columns and pair of rows may undergo a different pre- and/or post-adjustment operation to provide a medium level of quality/memory compromise.

<FIG> is a block diagram illustrating an example video encoder <NUM> that may implement the techniques of this disclosure. <FIG> is provided for purposes of explanation and should not be considered limiting of the techniques as broadly exemplified and described in this disclosure. The techniques of this disclosure may be applicable to various coding standards or methods.

Processing circuitry includes video encoder <NUM>, and video encoder <NUM> is configured to perform one or more of the example techniques described in this disclosure. For instance, video encoder <NUM> includes integrated circuitry, and the various units illustrated in <FIG> may be formed as hardware circuit blocks that are interconnected with a circuit bus. These hardware circuit blocks may be separate circuit blocks or two or more of the units may be combined into a common hardware circuit block. The hardware circuit blocks may be formed as combination of electric components that form operation blocks such as arithmetic logic units (ALUs), elementary function units (EFUs), as well as logic blocks such as AND, OR, NAND, NOR, XOR, XNOR, and other similar logic blocks.

In some examples, one or more of the units illustrated in <FIG> may be software units executing on the processing circuitry. In such examples, the object code for these software units is stored in memory. An operating system may cause video encoder <NUM> to retrieve the object code and execute the object code, which causes video encoder <NUM> to perform operations to implement the example techniques. In some examples, the software units may be firmware that video encoder <NUM> executes at startup. Accordingly, video encoder <NUM> is a structural component having hardware that performs the example techniques or has software/firmware executing on the hardware to specialize the hardware to perform the example techniques.

In the example of <FIG>, video encoder <NUM> includes a mode select unit <NUM>, a residual generation unit <NUM>, a transform processing unit <NUM>, a quantization unit <NUM>, an inverse quantization unit <NUM>, an inverse transform processing unit <NUM>, a reconstruction unit <NUM>, a filter unit <NUM>, a reference picture memory <NUM>, and an entropy encoding unit <NUM>. Mode select unit <NUM> includes a motion estimation unit <NUM>, motion compensation unit <NUM>, partition unit <NUM>, and an intra-prediction unit <NUM>.

Video data memory <NUM> may be configured to store video data to be encoded by the components of video encoder <NUM>. The video data stored in video data memory <NUM> may be obtained, for example, from video source <NUM>. Reference picture memory <NUM> may be also be referred to as a decoded picture buffer. Reference picture memory <NUM> stores reference video data for use in encoding video data by video encoder <NUM>, e.g., in intra- or inter-coding modes. Video data memory <NUM> and reference picture memory <NUM> may be formed by any of a variety of memory devices, such as dynamic random access memory (DRAM), including synchronous DRAM (SDRAM), magnetoresistive RAM (MRAM), resistive RAM (RRAM), or other types of memory devices. Video data memory <NUM> and reference picture memory <NUM> may be provided by the same memory device or separate memory devices. In various examples, video data memory <NUM> may be on-chip with other components of video encoder <NUM>, or off-chip relative to those components. Video data memory <NUM> may be the same as or part of storage media <NUM> of <FIG>.

Video encoder <NUM> receives video data. Video encoder <NUM> may encode each CTU in a slice of a picture of the video data. Each of the CTUs may be associated with equally-sized luma coding tree blocks (CTBs) and corresponding CTBs of the picture. As part of encoding a CTU, mode select unit <NUM> may perform partitioning to divide the CTBs of the CTU into progressively-smaller blocks. The smaller blocks may be coding blocks of CUs. For example, mode select unit <NUM> may partition a CTB associated with a CTU according to a tree structure.

Video encoder <NUM> may encode CUs of a CTU to generate encoded representations of the CUs (i.e., coded CUs). As part of encoding a CU, partition unit <NUM> may partition the coding blocks associated with the CU among one or more PUs of the CU. Thus, each PU may be associated with a luma prediction block and corresponding chroma prediction blocks. As indicated above, the size of a CU may refer to the size of the luma coding block of the CU and the size of a PU may refer to the size of a luma prediction block of the PU. Assuming that the size of a particular CU is 2N×2N, video encoder <NUM> and video decoder <NUM> may support PU sizes of 2Nx2N or NxN for intra prediction, and symmetric PU sizes of 2Nx2N, 2NxN, Nx2N, NxN, or similar for inter prediction.

Motion estimation unit <NUM> and motion compensation unit <NUM> may generate predictive data for a PU by performing inter prediction on each PU of a CU. The predictive data for the PU may include predictive blocks of the PU and motion information for the PU. Intra-prediction unit <NUM> may generate predictive data for a PU by performing intra prediction on the PU. The predictive data for the PU may include predictive blocks of the PU and various syntax elements. Intra-prediction unit <NUM> may perform intra prediction on PUs in I slices, P slices, and B slices.

To perform intra prediction on a PU, intra-prediction unit <NUM> may use multiple intra prediction modes to generate multiple sets of predictive data for the PU. Intra-prediction unit <NUM> may use samples from sample blocks of neighboring PUs to generate a predictive block for a PU. The neighboring PUs may be above, above and to the right, above and to the left, or to the left of the PU, assuming a left-to-right, top-to-bottom encoding order for PUs, CUs, and CTUs. Intra-prediction unit <NUM> may use various numbers of intra prediction modes, e.g., <NUM> directional intra prediction modes. In some examples, the number of intra prediction modes may depend on the size of the region associated with the PU.

Mode select unit <NUM> may select the predictive data for PUs of a CU from among the predictive data generated by motion estimation unit <NUM> and motion compensation unit <NUM> for the PUs or the predictive data generated by intra-prediction unit <NUM> for the PUs. In some examples, mode select unit <NUM> selects the predictive data for the PUs of the CU based on rate/distortion metrics of the sets of predictive data. The predictive blocks of the selected predictive data may be referred to herein as the selected predictive blocks.

Residual generation unit <NUM> may generate, based on the coding blocks (e.g., luma, Cb and Cr coding blocks) for a CU and the selected predictive blocks (e.g., predictive luma, Cb and Cr blocks) for the PUs of the CU, residual blocks (e.g., luma, Cb and Cr residual blocks) for the CU. For instance, residual generation unit <NUM> may generate the residual blocks of the CU such that each sample in the residual blocks has a value equal to a difference between a sample in a coding block of the CU and a corresponding sample in a corresponding selected predictive block of a PU of the CU.

Transform processing unit <NUM> may perform quad-tree partitioning to partition the residual blocks associated with a CU into transform blocks associated with TUs of the CU. Thus, a TU may be associated with a luma transform block and two chroma transform blocks. The sizes and positions of the luma and chroma transform blocks of TUs of a CU may or may not be based on the sizes and positions of prediction blocks of the PUs of the CU. A quad-tree structure known as a "residual quad-tree" (RQT) may include nodes associated with each of the regions. The TUs of a CU may correspond to leaf nodes of the RQT.

Transform processing unit <NUM> may generate transform coefficient blocks for each TU of a CU by applying one or more transforms to the transform blocks of the TU. Transform processing unit <NUM> may apply various transforms to a transform block associated with a TU. For example, transform processing unit <NUM> may apply a discrete cosine transform (DCT), a directional transform, or a conceptually similar transform to a transform block. In some examples, transform processing unit <NUM> does not apply transforms to a transform block. In such examples, the transform block may be treated as a transform coefficient block.

In accordance with the techniques of this disclosure, transform processing unit <NUM> may implement the techniques described elsewhere in this disclosure. For example, after residual generation unit <NUM> performs a first prediction process on a first block of video data to produce a first residual, transform processing unit <NUM> may, for the first residual, determine that a first transform process of a plurality of transform processes is to be applied to the first residual. Transform processing unit <NUM> may then apply the first transform process to the first residual to generate first transform coefficients for the first block of video data. For instance, during the testing process, transform processing unit may determine that the DCT-<NUM> transform is the optimal transform process to apply to the first residual, and, as such, may apply the DCT-<NUM> transform to the first residual. In some instances, the first transform process is a discrete trigonometrical transform matrix. In some such instances, each transform process of the plurality of transform processes is a discrete trigonometrical transform matrix. In some instances, the first transform process is one of a DCT-<NUM> matrix, a DCT-<NUM> matrix, a DST-<NUM> matrix, or a DST-<NUM> matrix. Entropy encoding unit <NUM> may entropy encode the first transform coefficients.

After residual generation unit <NUM> performs a second prediction process on a second block of video data to produce a second residual, transform processing unit <NUM> may determine that a second transform process is to be applied to the second residual, where the second transform process is the first transform process and at least one of a first pre-adjustment operation or a first post-adjustment operation to apply to the second residual in addition to the first transform process. For instance, if every DTT were tested for the second residual, transform processing unit <NUM> may determine that the optimal transform process is the DCT-<NUM> transform process. However, using the techniques described herein, the DCT-<NUM> transform process may be closely approximated by applying the DCT-<NUM> transform process with at least one of a pre-adjustment operation or a post-adjustment operation. As such, rather than store the DCT-<NUM> matrix in memory and perform the complex DCT-<NUM> transform in the testing phase, transform processing unit may instead test the combination of the DCT-<NUM> transform process and the pre- and/or post-adjustment operation as a substitution. If this approximation of the DCT-<NUM> is the optimal transform process for the second residual, transform processing unit <NUM> may select this combination as the second transform process. In essence, the second transform coefficients resulting from the application of the DCT-<NUM> transform process and the pre- and/or post-adjustment operation would be approximately equal to transform coefficients resulting from applying the DCT-<NUM> transform process to the second residual.

In some instances, the first transform process and the at least one of the pre-adjustment operation or the post-adjustment operation each are a respective sparse matrix, as defined above. In some examples, the sparse matrix of the first transform process is a band diagonal matrix. In other examples, the sparse matrix of the first transform process is a block diagonal matrix. In some other examples, the at least one of the pre-adjustment operation or the post-adjustment operation are a respective set of one or more Givens rotations.

Transform processing unit <NUM> may apply the first transform process and at least one of the first pre-adjustment operation or the first post-adjustment operation to the second residual to generate second transform coefficients for the second block of video data. If the first pre-adjustment operation is applied, transform processing unit <NUM> applies the first pre-adjustment operation prior to applying the first transform process. If the first post-adjustment operation is applied, transform processing unit <NUM> applies the first post-adjustment operation after applying the first transform process. Video encoder <NUM> may then proceed to encode the second transform coefficients, such as by entropy encoding the first transform coefficients and the second transform coefficients.

To describe an example of the testing process described above, a generic block is used in the below description. When determining that the first or second transform processes described above are to be applied, transform processing unit <NUM> may follow a similar process. After residual generation unit <NUM> predicts a residual for the block of video data. Transform processing unit <NUM> may determine a subset of transform processes from the plurality of transform processes that includes less transform processes than the plurality of transform processes. The subset of transform processes also includes the first transform process.

Transform processing unit <NUM> may also determine a set of adjustment operations, with each adjustment operation including at least one of a pre-adjustment operation or a post-adjustment operation to be applied to the residual being evaluated. When each adjustment operation is applied in conjunction with a transform process of the subset of transform processes, the resulting transform coefficients are approximately equal to transform coefficients that would have resulted from the application of a transform process in the plurality of transform processes that is not included in the subset of transform processes to the residual being evaluated. Each adjustment operation of the set of adjustment operations is associated with a particular transform process of the subset of transform processes. Some transform processes from the subset of transform processes can be associated with multiple adjustment operations.

Transform processing unit <NUM> may determine rate-distortion characteristics for each transform process of the subset of transform processes, as well as rate-distortion characteristics each adjustment operation and the adjustment operation's associated transform process. Based on these determined rate-distortion characteristics, transform processing unit <NUM> may select either the transform process from the subset of transform processes or the adjustment operation from the set of adjustment operations and the transform process from the subset of transform processes associated with the selected adjustment operation as a complete transform process to apply to the residual being evaluated. Transform processing unit <NUM> may apply the complete transform process to the residual being evaluated to generate transform coefficients for that block of video data and encode said transform coefficients.

In some examples, the transform processes may be implemented as separable fixed passes, meaning that the same transform is applied during all of the one-dimensional transformations, although the transforms may change between the vertical and horizontal passes. In such examples, the first block may be a first coding tree unit, and the second block may be a second, different coding tree unit.

In other examples, the transform processes may be implemented as separable variable passes, where each row (for horizontal passes) or column (for vertical passes) of coding units, or pairs of rows or columns, within a single coding tree unit may use different transforms. In such examples, the first block may be a first coding unit in a first row or column of a coding tree unit, and the second block may be a second coding unit in a different row or column of the same coding tree unit. In the example where pairs of rows/columns use the same transform process, residual generation unit <NUM> may perform a third prediction process for a third coding unit of the coding tree unit to produce a third residual, where the third coding unit is in a third row of the coding tree unit, and where the second row and the third row are contiguous rows. As such, transform processing unit <NUM> may determine that the second transform process is to be applied to the third residual and apply the second transform process to the third residual to generate third transform coefficients for the third coding unit. Transform processing unit <NUM> may then encode the third transform coefficients.

Quantization unit <NUM> may quantize the transform coefficients in a coefficient block. The quantization process may reduce the bit depth associated with some or all of the transform coefficients. For example, an n-bit transform coefficient may be rounded down to an m-bit transform coefficient during quantization, where n is greater than m. Quantization unit <NUM> may quantize a coefficient block associated with a TU of a CU based on a quantization parameter (QP) value associated with the CU. Video encoder <NUM> may adjust the degree of quantization applied to the coefficient blocks associated with a CU by adjusting the QP value associated with the CU. Quantization may introduce loss of information. Thus, quantized transform coefficients may have lower precision than the original ones.

Inverse quantization unit <NUM> and inverse transform processing unit <NUM> may apply inverse quantization and inverse transforms to a coefficient block, respectively, to reconstruct a residual block from the coefficient block. Inverse quantization may restore the bit depths of transform coefficients. Reconstruction unit <NUM> may add the reconstructed residual block to corresponding samples from one or more predictive blocks generated by mode select unit <NUM> to produce a reconstructed transform block associated with a TU. By reconstructing transform blocks for each TU of a CU in this way, video encoder <NUM> may reconstruct the coding blocks of the CU.

Filter unit <NUM> may perform one or more deblocking operations to reduce blocking artifacts in the coding blocks associated with a CU. Reference picture memory <NUM> may store the reconstructed coding blocks after filter unit <NUM> performs the one or more deblocking operations on the reconstructed coding blocks. Motion estimation unit <NUM> and motion compensation unit <NUM> may use a reference picture that contains the reconstructed coding blocks to perform inter prediction on PUs of other pictures. In addition, intra-prediction unit <NUM> may use reconstructed coding blocks in reference picture memory <NUM> to perform intra prediction on other PUs in the same picture as the CU.

Entropy encoding unit <NUM> may receive data from other functional components of video encoder <NUM>. For example, entropy encoding unit <NUM> may receive coefficient blocks from quantization unit <NUM> and may receive syntax elements from mode select unit <NUM>. Entropy encoding unit <NUM> may perform one or more entropy encoding operations on the data to generate entropy-encoded data. For example, entropy encoding unit <NUM> may perform a CABAC operation, a context-adaptive variable length coding (CAVLC) operation, a variable-to-variable (V2V) length coding operation, a syntax-based context-adaptive binary arithmetic coding (SBAC) operation, a Probability Interval Partitioning Entropy (PIPE) coding operation, an Exponential-Golomb encoding operation, or another type of entropy encoding operation on the data. Video encoder <NUM> may output a bitstream that includes entropy-encoded data generated by entropy encoding unit <NUM>. For instance, the bitstream may include data that represents a RQT for a CU.

<FIG> is a block diagram illustrating an example video decoder <NUM> that is configured to implement the techniques of this disclosure. <FIG> is provided for purposes of explanation and is not limiting on the techniques as broadly exemplified and described in this disclosure. For purposes of explanation, this disclosure describes video decoder <NUM> in the context of HEVC coding. However, the techniques of this disclosure may be applicable to other coding standards or methods.

Processing circuitry includes video decoder <NUM>, and video decoder <NUM> is configured to perform one or more of the example techniques described in this disclosure. For instance, video decoder <NUM> includes integrated circuitry, and the various units illustrated in <FIG> may be formed as hardware circuit blocks that are interconnected with a circuit bus. These hardware circuit blocks may be separate circuit blocks or two or more of the units may be combined into a common hardware circuit block. The hardware circuit blocks may be formed as combination of electric components that form operation blocks such as arithmetic logic units (ALUs), elementary function units (EFUs), as well as logic blocks such as AND, OR, NAND, NOR, XOR, XNOR, and other similar logic blocks.

In some examples, one or more of the units illustrated in <FIG> may be software units executing on the processing circuitry. In such examples, the object code for these software units is stored in memory. An operating system may cause video decoder <NUM> to retrieve the object code and execute the object code, which causes video decoder <NUM> to perform operations to implement the example techniques. In some examples, the software units may be firmware that video decoder <NUM> executes at startup. Accordingly, video decoder <NUM> is a structural component having hardware that performs the example techniques or has software/firmware executing on the hardware to specialize the hardware to perform the example techniques.

In the example of <FIG>, video decoder <NUM> includes an entropy decoding unit <NUM>, video data memory <NUM>, a prediction processing unit <NUM>, an inverse quantization unit <NUM>, an inverse transform unit <NUM>, a reconstruction unit <NUM>, a filter unit <NUM>, and a reference picture memory <NUM>. Prediction processing unit <NUM> includes a motion compensation unit <NUM> and an intra-prediction processing unit <NUM>. In other examples, video decoder <NUM> may include more, fewer, or different functional components.

Video data memory <NUM> may store encoded video data, such as an encoded video bitstream, to be decoded by the components of video decoder <NUM>. The video data stored in video data memory <NUM> may be obtained, for example, from computer-readable medium <NUM>, e.g., from a local video source, such as a camera, via wired or wireless network communication of video data, or by accessing physical data storage media. Video data memory <NUM> may form a coded picture buffer (CPB) that stores encoded video data from an encoded video bitstream. Reference picture memory <NUM> may also be referred to as a reference picture memory. Reference picture memory <NUM> stores reference video data for use in decoding video data by video decoder <NUM>, e.g., in intra- or inter-coding modes, or for output. Video data memory <NUM> and reference picture memory <NUM> may be formed by any of a variety of memory devices, such as dynamic random access memory (DRAM), including synchronous DRAM (SDRAM), magnetoresistive RAM (MRAM), resistive RAM (RRAM), or other types of memory devices. Video data memory <NUM> and reference picture memory <NUM> may be provided by the same memory device or separate memory devices. In various examples, video data memory <NUM> may be on-chip with other components of video decoder <NUM>, or off-chip relative to those components. Video data memory <NUM> may be the same as or part of storage media <NUM> of <FIG>.

Video data memory <NUM> receives and stores encoded video data (e.g., NAL units) of a bitstream. Entropy decoding unit <NUM> may receive encoded video data (e.g., NAL units) from video data memory <NUM> and may parse the NAL units to obtain syntax elements. Entropy decoding unit <NUM> may entropy decode entropy-encoded syntax elements in the NAL units. Prediction processing unit <NUM>, inverse quantization unit <NUM>, inverse transform unit <NUM>, reconstruction unit <NUM>, and filter unit <NUM> may generate decoded video data based on the syntax elements extracted from the bitstream. Entropy decoding unit <NUM> may perform a process generally reciprocal to that of entropy encoding unit <NUM>.

In addition to obtaining syntax elements from the bitstream, video decoder <NUM> may perform a reconstruction operation on a non-partitioned CU. To perform the reconstruction operation on a CU, video decoder <NUM> may perform a reconstruction operation on each TU of the CU. By performing the reconstruction operation for each TU of the CU, video decoder <NUM> may reconstruct residual blocks of the CU.

As part of performing a reconstruction operation on a TU of a CU, inverse quantization unit <NUM> may inverse quantize, i.e., de-quantize, coefficient blocks associated with the TU. After inverse quantization unit <NUM> inverse quantizes a coefficient block, inverse transform unit <NUM> may apply one or more inverse transforms to the coefficient block in order to generate a residual block associated with the TU. For example, inverse transform unit <NUM> may apply an inverse DCT, an inverse integer transform, an inverse Karhunen-Loeve transform (KLT), an inverse rotational transform, an inverse directional transform, or another inverse transform to the coefficient block.

In accordance with the techniques of this disclosure, inverse transform unit <NUM> may implement the techniques described elsewhere in this disclosure. For example, inverse transform unit <NUM> may, for a first block of video data, determine that a first inverse transform process of a plurality of inverse transform processes is to be applied to the first block. Inverse transform unit <NUM> may then apply the first inverse transform process to first transform coefficients of the first block to generate a first residual and decode the first residual to produce a first decoded block. In some instances, the first inverse transform process is a discrete trigonometrical transform matrix. In some such instances, each inverse transform process of the plurality of inverse transform processes is a discrete trigonometrical inverse transform matrix. In some instances, the first inverse transform process is one of a DCT-<NUM> matrix, a DCT-<NUM> matrix, a DST-<NUM> matrix, or a DST-<NUM> matrix. For example, the first inverse transform process may be the DST-<NUM> matrix as the inverse transform process.

For a second block of video data, inverse transform unit <NUM> may determine that a second inverse transform process is to be applied to the second block, where the second inverse transform process includes the first inverse transform process and at least one of a pre-adjustment operation or a post-adjustment operation. Inverse transform unit <NUM> may apply the first inverse transform process and the at least one of the pre-adjustment operation or the post-adjustment operation to second transform coefficients of the second block to generate a second residual. If the pre-adjustment operation is applied, inverse transformation processing unit <NUM> applies the pre-adjustment operation prior to applying the first inverse transform process. If the post-adjustment operation is applied, inverse transformation processing unit <NUM> applies the post-adjustment operation after applying the first inverse transform process. Video decoder <NUM> may decode the second residual to produce a second decoded block. Video decoder <NUM> may then proceed to decode the video data based at least in part on the first decoded block and the second decoded block.

In essence, the second residual is approximately equal to a residual resulting from applying a more complex transform process to the second transform coefficients of the second block. In this example, the DST-<NUM> inverse transform process, in combination with at least one of a pre- or post-adjustment process, may result in a residual that is approximately equal to a residual that would have resulted from applying the DST-<NUM> inverse transform process.

In some instances, the first inverse transform process and the at least one of the pre-adjustment operation or the post-adjustment operation each are a respective sparse matrix, as defined above. In some examples, the sparse matrix of the first inverse transform process is a band diagonal matrix. In other examples, the sparse matrix of the first inverse transform process is a block diagonal matrix. In some examples, the at least one of the pre-adjustment operation or the post-adjustment operation are a respective set of one or more Givens rotations.

In determining which inverse transform process to apply to the second transform coefficients, inverse transform unit <NUM> may analyze index values. For instance, inverse transform unit <NUM> may read a first index value that indicates which transform process to apply to the second transform coefficients and determine that a value of the first index indicates that the first inverse transform is to be applied to the second coding block. Further, inverse transform processing unit <NUM> may read a second index value that indicates whether pre- and/or post-adjustment operations are to be applied to the second coding block in addition to the inverse transform process and determine that a value of the second index indicates that the at least one of the pre-adjustment operation and the post-adjustment operation is to be applied to the second block in addition to the first inverse transform.

In other examples, the transform processes may be implemented as separable variable passes, where each row (for horizontal passes) or column (for vertical passes) of coding units, or pairs of rows or columns, within a single coding tree unit may use different transforms. In such examples, the first block may be a first coding unit in a first row or column of a coding tree unit, and the second block may be a second coding unit in a different row or column of the same coding tree unit. In the example where pairs of rows/columns use the same transform process, inverse transform unit <NUM> may determine that the first inverse transform process and the at least one of the pre-adjustment operation or the post-adjustment operation is to be applied to a third coding unit, where the third coding unit is in a third row of the coding tree unit that is contiguous with the second row. Inverse transform unit <NUM> may then apply the first inverse transform process and the at least one of the pre-adjustment operation or the post-adjustment operation to third transform coefficients of the third coding unit to generate a third residual, decode the third residual to produce a third decoded coding unit, and decode the video data based at least in part on the third decoded block.

If a PU is encoded using intra prediction, intra-prediction processing unit <NUM> may perform intra prediction to generate predictive blocks of the PU. Intra-prediction processing unit <NUM> may use an intra prediction mode to generate the predictive blocks of the PU based on samples spatially-neighboring blocks. Intra-prediction processing unit <NUM> may determine the intra prediction mode for the PU based on one or more syntax elements obtained from the bitstream.

If a PU is encoded using inter prediction, entropy decoding unit <NUM> may determine motion information for the PU. Motion compensation unit <NUM> may determine, based on the motion information of the PU, one or more reference blocks. Motion compensation unit <NUM> may generate, based on the one or more reference blocks, predictive blocks (e.g., predictive luma, Cb and Cr blocks) for the PU.

Reconstruction unit <NUM> may use transform blocks (e.g., luma, Cb and Cr transform blocks) for TUs of a CU and the predictive blocks (e.g., luma, Cb and Cr blocks) of the PUs of the CU, i.e., either intra-prediction data or inter-prediction data, as applicable, to reconstruct the coding blocks (e.g., luma, Cb and Cr coding blocks) for the CU. For example, reconstruction unit <NUM> may add samples of the transform blocks (e.g., luma, Cb and Cr transform blocks) to corresponding samples of the predictive blocks (e.g., luma, Cb and Cr predictive blocks) to reconstruct the coding blocks (e.g., luma, Cb and Cr coding blocks) of the CU.

Filter unit <NUM> may perform a deblocking operation to reduce blocking artifacts associated with the coding blocks of the CU. Video decoder <NUM> may store the coding blocks of the CU in reference picture memory <NUM>. Reference picture memory <NUM> may provide reference pictures for subsequent motion compensation, intra prediction, and presentation on a display device, such as display device <NUM> of <FIG>. For instance, video decoder <NUM> may perform, based on the blocks in reference picture memory <NUM>, intra prediction or inter prediction operations for PUs of other CUs.

Certain aspects of this disclosure have been described with respect to extensions of the HEVC standard for purposes of illustration. However, the techniques described in this disclosure may be useful for other video coding processes, including other standard or proprietary video coding processes not yet developed.

A video coder, as described in this disclosure, may refer to a video encoder or a video decoder. Similarly, a video coding unit may refer to a video encoder or a video decoder. Likewise, video coding may refer to video encoding or video decoding, as applicable.

<FIG> is a flow diagram illustrating a first example decoding of video data that may implement techniques described in this disclosure. The example techniques of <FIG> may be performed by video decoder <NUM>. In the example of <FIG>, a decoder (e.g., video decoder <NUM>) may determine that a first inverse transform process of a plurality of inverse transform processes is to be applied to a first block of a plurality of blocks of video data (<NUM>). Video decoder <NUM> may then apply the first inverse transform process to first transform coefficients of the first block to generate a first residual (<NUM>). Video decoder <NUM> may decode the first residual to produce a first decoded block (<NUM>). For a second block of the plurality of blocks of video data, video decoder <NUM> may determine that a second inverse transform process is to be applied to a second block of the plurality of blocks of video data, where the second inverse transform process includes the first inverse transform process and at least one of a pre-adjustment operation or a post-adjustment operation (<NUM>). Video decoder <NUM> may apply the first inverse transform process and the at least one of the pre-adjustment operation or the post-adjustment operation to second transform coefficients of the second block to generate a second residual (<NUM>). If the pre-adjustment operation is applied, video decoder <NUM> applies the pre-adjustment operation prior to applying the first inverse transform process. If the post-adjustment operation is applied, video decoder <NUM> applies the post-adjustment operation after applying the first inverse transform process. Video decoder <NUM> may decode the second residual to produce a second decoded block (<NUM>). Video decoder <NUM> may then proceed to decode the video data based at least in part on the first decoded block and the second decoded block (<NUM>).

In some examples, the transform processes may be implemented as separable fixed passes, meaning that the same transform is applied during all of the one-dimensional transformations, although the transforms may change between the vertical and horizontal passes. In such examples, the first block may be a first coding tree unit, and the second block may be a second, different coding tree unit. In other examples, the transform processes may be implemented as separable variable passes, where each row (for horizontal passes) or column (for vertical passes) of coding units, or pairs of rows or columns, within a single coding tree unit may use different transforms. In such examples, the first block may be a first coding unit in a first row or column of a coding tree unit, and the second block may be a second coding unit in a different row or column of the same coding tree unit.

<FIG> is a flow diagram illustrating a first example encoding of video data that may implement techniques described in this disclosure. The example techniques of <FIG> may be performed by video encoder <NUM>. In the example of <FIG>, an encoder (e.g., video encoder <NUM>) may perform a first prediction process for a first block of video data to produce a first residual (<NUM>). Video encoder <NUM> may determine that a first transform process of a plurality of transform processes is to be applied to the first block (<NUM>). Video encoder <NUM> may then apply the first transform process to the first residual to generate first transform coefficients for the first block of video data (<NUM>). Video encoder <NUM> may then entropy encode the first transform coefficients (<NUM>). Video encoder <NUM> may perform a second prediction process for a second block of video data to produce a second residual (<NUM>). Video encoder <NUM> may determine that a second transform process is to be applied to the second block (<NUM>). The second transform process may include the first transform process and at least one of a first pre-adjustment operation or a first post-adjustment operation to apply to the second residual in addition to the first transform process. Video encoder <NUM> may apply the first transform process and at least one of the first pre-adjustment operation or the first post-adjustment operation to the second residual to generate second transform coefficients for the second block of video data (<NUM>). If the first pre-adjustment operation is applied, video encoder <NUM> applies the first pre-adjustment operation prior to applying the first transform process. If the first post-adjustment operation is applied, video encoder <NUM> applies the first post-adjustment operation after applying the first transform process. Video encoder <NUM> may then proceed to entropy encode the second transform coefficients (<NUM>).

Claim 1:
A method of encoding video data comprising:
performing a first prediction process for a first block of video data to produce a first residual;
determining that a first transform process of a plurality of transform processes is to be applied to the first residual;
applying the first transform process to the first residual to generate first transform coefficients for the first block of video data;
encoding the first transform coefficients;
performing a second prediction process for a second block of video data to produce a second residual;
determining that a second transform process is to be applied to the second residual, wherein the second transform process comprises the first transform process and at least one of a first pre-adjustment operation or a first post-adjustment operation to apply to the second residual in addition to the first transform process, wherein the at least one of the first pre-adjustment operation or the first post-adjustment operation comprises a set of one or more Givens rotations;
applying the first transform process and at least one of the first pre-adjustment operation or the first post-adjustment operation to the second residual to generate second transform coefficients for the second block of video data, wherein the first pre-adjustment operation, if applied, is applied prior to applying the first transform process, and wherein the first post-adjustment operation, if applied, is applied after applying the first transform process; and
encoding the second transform coefficients.