Rate distortion optimization in image and video encoding

An offline quantization module is used to optimize a rate-distortion task. The offline quantization module calculates a quantization kernel for a range of computable block parameters and a range of rate-distortion slope values representing the rate and complexity of a coded video. A quantization kernel is utilized by an encoder application for content-adaptive quantization of transformed coefficients. The quantization kernel includes a block data model, a quality metric model, and an entropy coding model. The quantization kernel is suitable for existing and future coding standards. A rate-distortion slope selection process is performed on a per-frame basis for improved rate-distortion performance. The slope is selected by referring to the block model parameter value within the quantization kernel.

CROSS REFERENCE TO RELATED APPLICATIONS

This application claims the right of priority based on Russian application serial no. 2011140631, filed Oct. 6, 2011, which is incorporated by reference in its entirety. This application is related to U.S. patent application Ser. No. 13/451,413, titled “Improved Visual Quality Measure for Real-Time Video Processing”, filed on Apr. 19, 2012, which is incorporated by reference herein in its entirety.

BACKGROUND

Field of Disclosure

This disclosure relates in general to the field of digital video and in particular to scalar quantization and rate control in a real time video codec.

Description of the Related Art

Raw digital video streams often consume immense digital storage space, and are prohibitively massive for transmission. To reduce storage space or transmission bandwidth requirements, a raw video stream is encoded to reduce its size. Typical video encoding involves the process of subtracting a reference frame from an original frame of video to obtain a residual frame containing less information than the original frame. Residual frames are then further processed to obtain a compressed digital video stream for transmission or storage. A typical video decoder receives the compressed digital video stream and decompresses the compressed digital video into the original video stream or a downgraded version of the digital video stream.

In the field of video coding, proper quantization parameter selection is an important consideration in encoding video frames in a video stream. Improved quantization parameter construction can improve the quality of the video and/or reduce the bandwidth used to transmit video of a given quality. A selected quantization parameter is typically maintained throughout the video coding process regardless of whether a new coding mode is considered, the signal model is changed, or a new distortion metric is introduced. This may introduce inefficiencies in rate-distortion performance.

SUMMARY

Embodiments relate to content-adaptive selection of quantization parameters for encoding which uses mapping of block model parameters to quantization parameters to obtain quantization parameters suitable for characteristics and properties of a raw video frame. A Lagrange multiplier value for the raw video frame is selected and used for determining quantization parameters for the raw video frame. The raw video frame is encoded by performing quantization based on the quantization parameters.

In one embodiment, the mapping of the block model parameters to the quantization parameters are computed offline before performing encoding to reduce the amount of computation during encoding. During encoding, the mapping is referenced to determine quantization parameters appropriate for a raw video frame.

DETAILED DESCRIPTION

The Figures (FIGS.) and the following description describe certain embodiments by way of illustration only. Reference will now be made in detail to several embodiments, examples of which are illustrated in the accompanying figures. It is noted that wherever practicable similar or like reference numbers may be used in the figures and may indicate similar or like functionality.

Embodiments relate to selection of quantization parameters depending on the content of individual video frames in a video stream to provide improved rate-distortion performance. A model or mapping of block model parameters to quantization parameters is generated offline and made available for encoding in real-time based on the content and characteristics of the video frames. Among other advantages, embodiments provide improved rate-distortion performance and enable real-time encoding by reducing required calculations.

A block described herein refers to a group of pixels within an image in a spatial pixel domain or a group of coefficients in a transform domain. In a spatial pixel domain, a block may include information about luminance or chrominance values for a set of pixels. A block may be a group of pixels of any size (e.g., 4×4 pixels or 8×8 pixels) in the spatial pixel domain. In a transform domain, blocks may be a group of transform coefficients of any size within an image.

Block model parameters described herein refer to a set of parameters which represent computable characteristics which are calculated or approximated from properties of a macroblock in a raw video frame. Block model parameters may also include aggregated characteristics of multiple macroblocks in a raw video frame. Aggregated characteristics of multiple macroblocks may include averaged characteristics or aspects of otherwise aggregated characteristics from multiple macroblocks. For example, estimators derived from a Gaussian distribution of block data may be utilized as block model parameters. The block model parameters may include, for example, Sum of Absolute Differences (SAD) values and Average Absolute Deviation (DEV) values. In one embodiment, the block model parameters are computed real time during an encoding process.

Quantization model parameters described herein refers to operating parameters associated with performing quantization during an encoding process. The quantization parameters may include quantization thresholds and quantization invariants.

The term “offline” as described herein indicates that an operation is performed in a separate process before an encoding process. In one embodiment, output of the offline quantization module is generated prior to the encoding process occurring and without knowledge of the current video frame or stream being encoded.

Overview of Process

FIG. 1is a flowchart illustrating an overall process for encoding a raw video frame, according to one embodiment. First, a coding mode is selected101based on a Lagrange multiplier and estimated block model parameters taken from previous frames. If the raw frame100is an initial video frame (not preceded by other video frame), a predetermined initial value for the Lagrange multiplier is selected during encoder initialization without reference to any previous frame (since no previous frame is available) and used during mode selection. Then, a Lagrange multiplier value representing the relationship between frame distortion and bit rate is selected102based on block model parameters from the raw image100and other previous frames received at the encoder. In addition, a histogram of Sum of Absolute Differences for previous frames may be considered in Lagrange multiplier selection.

In one embodiment, the statistics of the frames are computed in real time during the encoding. By selecting the Lagrange multiplier value based on the real time analysis of video frames, rate-distortion performance of the encoder can be improved compared to encoders using a constant Lagrange multiplier value for different video frames.

The encoder then selects104quantization parameters corresponding to the frame distortion and bit rate values at an offline quantization module, as described below in detail with reference toFIGS. 3 and 4. The quantization parameters for frame distortion and bit rate values are computed and stored offline and made available during encoding to reduce computation during real time encoding.

The encoder then applies the retrieved quantization parameters to encode106the current frame and produce a compressed frame108.

Example Operating Environment

FIG. 2is a high-level block diagram illustrating a typical environment for content adaptive selection of quantization parameters, according to one embodiment. Illustrated are at least one processor202coupled to a chipset204. Also coupled to the chipset204are a memory206, a storage device208, a keyboard210, a graphics adapter212, a pointing device214, and a network adapter216. The network adapter216is communicatively coupled to computer232and mobile device234through network230. A display218is coupled to the graphics adapter212. In one embodiment, the functionality of the chipset204is provided by a memory controller hub220and an I/O controller hub222.

In another embodiment, the memory206is coupled directly to the processor202instead of the chipset204, or is located within processor202, such as in a system-on-a-chip environment. In such embodiments, the operating environment may lack certain components, such as chipset204, storage device208, keyboard210, graphics adapter212, pointing device214, network adapter216and display218. Processor202may be a special-purpose dedicated processor, such as an Application-Specific Integrated Circuit (ASIC), or a customizable general-purpose processor, such as a Field-Programmable Gate Array (FPGA). Processor202may also be embodied as a commercially available Central Processing Unit (CPU) or (Graphics Processing Unit (GPU), with one or more processor cores.

The storage device208is a non-transitory computer-readable storage medium, such as a hard drive, compact disk read-only memory (CD-ROM), DVD, or a solid-state memory device. The memory206may contain, among other data, instructions and data used by the processor202. The pointing device214is a mouse, track ball, or other type of pointing device, and is used in combination with the keyboard210to input data into the computer system. The graphics adapter212displays images and other information on the display218. The network230enables communications between the processor202, computer232and mobile device234. In one embodiment, the network230uses standard communications technologies and/or protocols and can include the Internet as well as mobile telephone networks.

Additional modules not illustrated inFIG. 2may also be present in the operating environment. For instance, encoder modules, decoder modules, transform modules, or any other claimed module may be implemented by processor202, chipset204, memory206, storage device208, graphics adapter212, or by an additional component not displayed such as a specialized hardware module to implement the functionality described below with regards toFIGS. 3 through 6, which may or may not be external to the computer. The term “module” described herein refer hardware, firmware, software or a combination thereof embodied as various components described inFIG. 2. A module is typically stored on a computer-readable storage medium such as the storage device208, loaded into the memory206, and executed by the processor202.

Example of Encoder Architecture

FIG. 3is a block diagram illustrating modules within an encoder300in accordance with one embodiment. The encoder300receives the raw frame100, processes the raw frame100by a series of modules (e.g., spatial or temporal prediction module302, transform module304, quantization module314and entropy coding module316). As a result, the encoder300generates and output the compressed frame108. One or more of these modules may be embodied in hardware, software, firmware or a combination thereof.

In addition to the series of modules for processing the raw frame100, the encoder300also includes (i) modules for determining operating parameters for the series of modules and (ii) modules for reconstructing a decoded version of the video frame from the compressed frame108. The modules for determining operating parameters may include, among other components, coding control module308, rate-distortion slope module310, averaging module306and offline quantization module400. The modules for reconstructing the decoded version of the video frame may include, among other components, inverse quantization module318, inverse transform module322, and spatial or temporal reconstruction module324. One or more of these modules may be embodied in hardware, software, firmware or a combination thereof.

The spatial or temporal prediction module302calculates a residual block of data301from the current video frame that is to be encoded and the previously encoded frame. By indicating the change in video frames rather than the entire video frame to be encoded, the residual block of data is able to reduce the amount of data that is to be encoded to transmit the video frame. The spatial or temporal prediction module302may be capable of operating in more than one coding modes. The coding mode of the spatial or temporal prediction module302may be selected by the coding control module308. Moreover, the spatial or temporal prediction module302generates and sends block model parameter370(i.e., per-block statistics) to the coding control308.

The transform module304receives the residual block data301from the special or temporal prediction module302and outputs a transformed block of transform coefficients305for quantization and averaging.

The averaging module306receives transform coefficients305from the transform module304and determines averaged block data307. In one embodiment, the averaging module306sums the transformed coefficients305and generates the averaged or summed version307of the transformed coefficients305. The summed version307becomes part of the block model parameters and is passed to the coding control308to determine the operating parameters in the encoder300.

The coding control module308determines and outputs one or more operating parameters such as (i) quantization thresholds309for use by the quantization module314and inverse quantization module318, and (ii) selection350of coding modes for spatial or temporal prediction module302based on block model parameters computed by the averaging module306. Quantization parameters stored in the offline quantization module400are selected which best match the block model parameters. The coding control module308also sends data to the rate-distortion slope module310for selecting a Lagrange multiplier value (i.e., a rate-distortion slope). For such operation, the coding control module308receives input from the offline quantization module400, per-block statistics370from the spatial or temporal prediction module302, per-frame averaged block statistics307from the averaging module306, and the rate-distortion slope311from the rate-distortion slope module310.

The coding control module308may retrieve suitable quantization thresholds from the offline quantization module400in response to sending block model parameters to the offline quantization module describing properties or parameters of the current frame and/or previous frames. The operation of the coding control308and the offline quantization module400for determining the quantization thresholds are described below in detail with reference toFIG. 4.

The rate-distortion slope module310receives data describing video frames on a per-frame basis and selects a Lagrange multiplier value (i.e., a rate-distortion slope) used for determining a coding mode and quantization thresholds, as described above in detail with reference toFIG. 1.

The quantization module314performs quantization on the residual of the current video frame. Specifically, the quantization module314maps the residual data of the current video frame to a set of entropy coding alphabet symbols according to the transform coefficients305received from the transform module304and the quantization thresholds309received from the coding control module308. The quantization thresholds309define to what level values are quantized, and quantization invariants define which values remain the same after both quantization and de-quantization.

Scalar quantization processes use a number of quantization levels for encoding. For example, a set of quantization thresholds tkand quantization invariants IkLassociated with a codec may satisfy IkL=L·Qk, where L represents a quantization level. For a given transformed residual image coefficient {circumflex over (r)}k, where IkL−tk·Qk≦rk<IkL+1−tk·Qk, {circumflex over (r)}kis mapped to quantization level L. Typically, many higher frequency coefficients are rounded to zero, reducing the digital footprint of the compressed frame108. The quantization module314may also determine and output quantization invariants IkLand quantization thresholds tk.

Entropy coding module316codes the data315as quantized by the quantization module314and sends out the coded data, using a method as well known in the art.

The inverse quantization module318generates reconstructed transform coefficients319and transmits them to the inverse transform module322. The inverse transform module322performs an inverse transformation on the reconstructed transform coefficients319according to the coding standard to generate inverse transformed coefficients321. The spatial or temporal reconstruction module324restores the coded representation of the input video frame325according to the active coding standard using the inverse transformed coefficients321. The restored representation of the video frame is provided as reference to the spatial or temporal prediction module302. This allows residual frame information to be calculated for a subsequent video frame.

Example Operation of Offline Quantization Module

FIG. 4is a block diagram illustrating an offline quantization module400in accordance with one embodiment. The offline quantization module400may include, among other components, a block data model402, a quality metric model404, an entropy coding model406and a quantization kernel module408. The offline quantization module400generates mapping tables representing relationship of quantization parameters and corresponding rate-distortion slopes for various coding modes available to the encoder. The mapping tables are transmitted to the coding control module308for use in the encoding process. Additionally, in one embodiment, the content of the quantization kernel module408may be accessed during encoding. One or more of these modules may be implemented in hardware, software, firmware or a combination thereof.

The block data model402maps block model parameters to expected energy distribution over horizontal and vertical frequency domain sub-bands. That is, the block data model402represents a parametric model that maps block model parameters of the raw frames to quantization thresholds appropriate for encoding the raw frames.

In one embodiment, the block data model402stores, for a set of given block model parameters, quantization thresholds corresponding to minimized version of Lagrangian cost function, as represented by the following equation.

∑j=0NM-1⁢∑c∈Cj⁢Pcj⁢∑l=0∞⁢∫tlj,ctl+1j,c⁢D⁡(xj,QIj,c-1⁡(QTj,c⁡(xj)))+Λ⁢vl,c⁢⁢d⁢⁢μj,(1)
where N represents the number of columns in a block, M represents the number of rows in the block, Cjrepresents a set of possible coding contexts for the j-th coefficient, Pcjrepresents probability of coding context C for the j-th coefficient of the parametric model for a selected block model, xjrepresents coefficient in the block, Q represents a scalar quantization process, Q−1represents an inverse quantization process, Tj,crepresents a set of thresholds associated with ascending values tlj,c, Ij,crepresents applied invariants associated with ascending values ilj,c, D represents a distortion metric, |vl,c| the codeword length for a given level l coded under the entropy coding context c, and Λ represents a Lagrange multiplier. For the purpose of determining quantization thresholds using equation (1), a number of typical two-dimensional data distributions on a mesh of Lagrange multiplier values may be used.

The block data model402is referenced by the coding control module308of the encoder300through the quantization kernel408to select quantization thresholds. The use of multiple parameters allows the encoder300to account for video frames with a wide range of parameters. In one embodiment, quantization parameters may describe a subset of a video frame such as a block, and quantization thresholds may be selected for the subset. The block model parameters submitted for retrieving the quantization threshold may include, for example, block rates and distortion values. The block model parameters may be computed by the encoder in real time per each frame being encoded. Alternatively, the block characteristics may be averaged over multiple frames. The parameterized data generated by the block data model402is used by the coding control module308to estimate parameter values based on the average transformed data collected during the coding process.

The quality metric model404comprises a data structure mapping a target visual quality metric to the difference in an original block and a transformed block. The target visual quality metric is identified for each block of a video frame from the original data blocks of a video frame and the coded representation of the block. The target visual quality metric is used to quantify the visual quality that can be expected with a given original block and transformed block. For example, the Peak Signal-to Noise Ratio (PSNR) may be used to represent the target visual quality metric.

In one embodiment, obtaining the PSNR includes determining the mean square error (MSE) of the video frame. In one embodiment, the process of computing PSNR includes computing the MSE for each of the plurality of blocks of the original image and the corresponding coded representation of the blocks, and averaging the computed MSE values. Alternatively, the PSNR may be computed by computing the MSE for a subset of the plurality of blocks of the original image and the corresponding blocks of the coded representation of the image. The output of the method is the visual quality of the coded representation of the image relative to the original image. The visual quality may be a unit-less ratio of distortion between the coded representation of the image and the original image, or may comprise any suitable measurement unit.

The quality metric model404may employ various quality metrics that are computable on a per block basis including PSNR and MSE as described above as well as video quality metric (VQM), structural similarity (SSIM) index and mean structural similarity (MSSIM) index. In one embodiment, implementations of quality metrics are used which calculate metrics for non-overlapping blocks.

The entropy coding model406represents a dependency between symbols and their context, and the amount of bits that are to be used for the representation of the symbols in the coded stream for a particular video coding standard. This dependency can be provided in the form of tabular or functional mapping. The mapping table stored by the entropy coding model406may be referenced by the coding control308through the quantization kernel408to encode a video frame using quantization parameters identified using the block data model402.

The quantization kernel408retrieves mappings from the block data model402, quality metric model404and entropy coding model406, and makes the mappings available to the coding control408for determining a set of quantization thresholds utilized by a quantization module314.

Example Video Encoding Process

FIG. 5is a flowchart illustrating a method of performing video encoding, according to one embodiment. The spatial or temporal prediction module302receives a raw frame100for encoding. The spatial or temporal prediction module302generates500a residual image301of the raw frame100by selecting a prediction image with similar features to the raw image of the video frame and subtracting the prediction image from the raw image.

The transform module304then transforms502the residual image301to produce transformed coefficients305in a transform domain (e.g., frequency domain). In one embodiment, a set of coefficients is produced for each block of pixels (e.g., 4×4 pixels or 8×8 pixels).

The rate-distortion slope module310then selects504a rate-distortion slope, as described above in detail with reference toFIG. 1.

The coding control308(or the offline quantization module400) then selects506quantization parameters. For this purpose, the coding control module308transmits block model parameters to the quantization kernel408of the offline quantization module400. The quantization kernel408retrieves appropriate quantization parameters from the parametric model stored in the block data model402. When a codec uses different quantization levels, the encoder300determines the quantization level using equation IkL=L·Qk, as described above in detail with reference toFIG. 3.

The entropy coding module316then receives the quantization levels and performs510entropy coding to form a compressed frame108.

Some process ofFIG. 5may be omitted. For example, a fixed rate distortion slope may be used instead of selecting504the rate distortion slope for different raw frames.

Offline Quantization Parameters Optimization

FIG. 6is a flowchart illustrating a method of determining quantization parameters by minimizing a Lagrangian cost function in a offline process. An example of the cost function is described above as equation (1).

First, a parametric model μjis selected600which represents a probability density function for values of the coefficient xjin a block size of N×M of a video frame being encoded. For each coding context cεCjused in entropy coding, a probability Pcjis calculated602for the j-th coefficient of the parametric model. Transform coefficients of the scalar quantization process Q are represented604with a set Tj,cof ascending thresholds tlj,c. The inverse quantization process Q−1is represented606by a set Ij,cof ascending recoverable values ilj,c.

In one embodiment, the parametric model μjis a Laplace distribution with the parameter λjdepending on the position of the coefficient in the transformed block. In one embodiment, scalar quantization optimization is performed by satisfying an encoding standard with a predefined de-quantization process by minimizing the Lagrangian cost function of equation (1) with thresholds tlj,cas free optimization parameters. In one embodiment, a de-quantization process comprises minimizing the Lagrangian cost function of equation (1) with recoverable values ilj,cas free optimization parameters.

In one embodiment, performing rate-distortion optimization of quantization thresholds for one-pass real-time image and video encoders comprises first selecting a grid on a direct product of application domains for a set of de-quantization recoverable values, Lagrange multiplier and an estimate for the parameter of a parametric model μj.

The offline quantization module400minimizes the Lagrangian cost function for each point of the grid and outputs a set of quantization thresholds corresponding to each point. The Lagrange multiplier is then determined to apply in real-time on a frame by frame basis. During the encoding of each block, an estimate is calculated for the parametric model parameter λjand the set of quantization thresholds is derived using the data generated in the offline quantization module. The set of quantization thresholds is applied when performing quantization for block coefficients.

In another embodiment, performing rate-distortion optimization of quantization thresholds for a constant bit rate video encoder comprises first selecting a grid on a direct product of application domains for a set of de-quantization recoverable values, Lagrange multiplier and an estimate for the parameter of a parametric model μj. An offline quantization module400minimizes the Lagrangian cost function for each point of the grid and outputs a block distortion and a block rate corresponding to the set of quantization thresholds at each point of the grid. The Lagrange multiplier is set to a predefined initial value during the encoder initialization. Subsequently, when encoding each frame with a target bitrate T, a lower (L) and upper (U) bound for bitrate output are set. U is a value greater than T which may be selected arbitrarily by the encoder, or selected based on limiting characteristics of an output channel. In one embodiment, L is set to 0, but may be set to any value lower than T at the discretion of the encoder. The total frame distortion D*and rate R*are summed using information collected from the offline quantization module and average frame statistics for blocks having various values for the parameter λjin various coding modes. Lagrange multiplier bounds for the current frame are calculated using equations (2) and (3).
ΛL=R*−1(L)  (2)
ΛU=R*−1(U)  (3)

If D*(ΛU) is greater than the distortion Dpachieved for the previous frame, the Lagrange multiplier for the current frame is set to ΛU. If D*(ΛL) is less than Dp, the Lagrange multiplier is set to ΛL. If neither condition is satisfied, the Lagrange multiplier is set to a value of D*−1(Dp). After the encoding of a frame, the statistics on the amount of blocks within a frame having various values of the parameter λjare then updated for each coding mode.

The above description is included to illustrate the operation of certain embodiments and is not meant to limit the scope of the disclosure. The scope of the disclosure is to be limited only by the following claims. From the above discussion, many variations will be apparent to one skilled in the relevant art that would yet be encompassed by the spirit and scope of the disclosure.