BACKGROUND

Video compression can be considered the process of representing digital video data in a form that uses fewer bits when stored or transmitted. Video encoding can achieve compression by exploiting redundancies in the video data, whether spatial, temporal, or color-space. Video compression processes typically segment the video data into portions, such as groups of frames and groups of pels, to identify areas of redundancy within the video that can be represented with fewer bits than required by the original video data. When these redundancies in the data are exploited, greater compression can be achieved. An encoder can be used to transform the video data into an encoded format, while a decoder can be used to transform encoded video back into a form comparable to the original video data. The implementation of the encoder/decoder is referred to as a codec.

Most modern standardized video encoders (referred to herein as “standard encoders”) divide a given video frame into non-overlapping coding units or macroblocks (rectangular regions of contiguous pels, herein referred to more generally as “input blocks” or “data blocks”) for encoding. Compression can be achieved when data blocks are predicted and encoded using previously-coded data. The process of encoding data blocks using spatially neighboring samples of previously-coded blocks within the same frame is referred to as intra-prediction. Intra-prediction attempts to exploit spatial redundancies in the data. The encoding of data blocks using similar regions from previously-coded frames, found using a motion estimation process, is referred to as inter-prediction. Inter-prediction attempts to exploit temporal redundancies in the data. The motion estimation process can generate a motion vector that specifies, for example, the location of a matching region in a reference frame relative to a data block that is being encoded.

The encoder may measure the difference between the data to be encoded and the prediction to generate a residual. The residual can provide the difference between a predicted block and the original data block. The predictions, motion vectors (for inter-prediction), residuals, and related data can be combined with other processes such as a spatial transform, a quantizer, an entropy encoder, and a loop filter to create an efficient encoding of the video data. The residual that has been quantized and transformed can be processed and added back to the prediction, assembled into a decoded frame, and stored in a framestore. Details of such encoding techniques for video will be familiar to a person skilled in the art.

H.264 (MPEG-4 Part 10, Advanced Video Coding [AVC]) and H.265 (MPEG-H Part 2, High Efficiency Video Coding [HEVC], hereafter referred to as H.264 and H.265, respectively, are two codec standards for video compression that achieve high quality video representation at relatively low bitrates. The basic coding unit for H.264 is 16×16 macroblocks, while the equivalent coding tree units for H.265 can take sizes from 16×16 up to 64×64 blocks.

Standard encoders typically define three types of frames (or pictures), based on how the data blocks in the frame are encoded. An I-frame (intra-coded picture) is encoded using only data present in the frame itself and thus consists of only intra-predicted blocks. A P-frame (predicted picture) is encoded via forward prediction, using data from previously-decoded I-frames or P-frames, also known as reference frames. P-frames can contain either intra blocks or (forward-)predicted blocks. A B-frame (bi-predicted picture) is encoded via bi-directional prediction, using data from both previous and subsequent frames. B-frames can contain intra, (forward-)predicted, or bi-predicted blocks.

A particular set of frames is termed a Group of Pictures (GOP). The GOP contains only the decoded pels within each reference frame and does not include information as to how the data blocks or frames themselves were originally encoded (I-frame, B-frame, or P-frame). Older video compression standards such as MPEG-2 use one reference frame (in the past) to predict P-frames and two reference frames (one past, one future) to predict B-frames. By contrast, more recent compression standards such as H.264 and H.265 allow the use of multiple reference frames for P-frame and B-frame prediction.

In standard encoders, inter-prediction is based on block-based motion estimation and compensation (BBMEC). The BBMEC process searches for the best match between the target block (the current data block being encoded) and same-sized regions within previously-decoded reference frames. When such a match is found, the encoder may transmit a motion vector, which serves as a pointer to the best match's position in the reference frame. For computational reasons, the BBMEC search process is limited, both temporally in terms of reference frames searched and spatially in terms of neighboring regions searched.

The simplest form of the BBMEC process initializes the motion estimation using a (0, 0) motion vector, meaning that the initial estimate of a target block is the co-located block in the reference frame. More recent motion estimation algorithms such as enhanced predictive zonal search (EPZS) [Tourapis, A.; “Enhanced predictive zonal search for single and multiple frame motion estimation,”Proc. SPIE4671,Visual Communications and Image Processing, pp. 1069-1078, 2002] consider a set of motion vector candidates for the initial estimate of a target block, based on the motion vectors of neighboring blocks that have already been encoded, as well as the motion vectors of the co-located block (and neighbors) in the previous reference frame. Once the set of initial motion vector candidates have been gathered, fine motion estimation is then performed by searching in a local neighborhood of the initial motion vectors for the region that best matches (i.e., has lowest error in relation to) the target block. The local search may be performed by exhaustive query of the local neighborhood or by any one of several “fast search” methods, such as a diamond or hexagonal search.

For any given target block, the encoder may generate multiple inter-predictions to choose from. The predictions may result from multiple prediction processes. The predictions may also differ based on the subpartitioning of the target block, where different motion vectors are associated with different subpartitions of the target block and the respective motion vectors each point to a subpartition-sized region in a reference frame. The predictions may also differ based on the reference frames to which the motion vectors point. Selection of the best prediction for a given target block is usually accomplished through rate-distortion optimization, where the best prediction is the one that minimizes the rate-distortion metric D+λR, where the distortion D measures the error between the target block and the prediction, while the rate R quantifies the cost (in bits) to encode the prediction and λ is a scalar weighting factor.

Standard encoders modulate the amount of compression that occurs within a GOP, an individual frame, a row of data blocks within a frame, or an individual data block, by means of a quantization parameter (QP). If the QP value is high, more quantization occurs and fewer bits are used to represent the data, but the visual quality of the encoded output is worse. If the QP value is low, less quantization occurs and more bits are used, but the visual quality of the encoded output is better. This tradeoff between bitrate (number of bits in the output bitstream per second of the input video) and quality is well known to persons skilled in the art.

The rate control algorithm of the encoder sets the QP values for a frame (as the frame QP), a row of data blocks within a frame (as the row QP), or an individual data block (as the block QP). The rate control algorithm allocates a bit budget to each GOP, frame, and row to achieve a target bitrate for the video encoding. Based on how many bits have been used in the encoding relative to the target bitrate and how full a virtual decoder buffer is in a hypothetical reference decoder (HRD), the rate control algorithm may increase or decrease the QP value for a given data block, row, or frame. The type of rate control determines how much the bitrate may vary from frame to frame. Constant bitrate (CBR) rate control allows little or no variation in the target bitrate from frame to frame. Variable bitrate (VBR) rate control still attempts to achieve the target bitrate on average across the entire video but allows the local bitrate for individual frames to exceed the target bitrate by some factor (e.g., 1.5 or 2 times the target bitrate). Constant rate factor (CRF) rate control attempts to maintain the quality of the output bitstream from frame to frame with less concern for the bitrate of the bitstream. However, CRF rate control may be applied with a “max-rate” parameter that governs the maximum bitrate for any given frame, thus achieving rate control similar to VBR for complex videos.

Often, the input parameters of an encoder are specified by some default configurations that generally vary according to capability, complexity, and encoding speed. For example, the open-source x264 encoder for H.264 encoding has a set of ten predefined presets ranging from “ultrafast” (fastest speed, lowest capability) to “placebo” (slowest speed, highest capability) that set the encoding parameters for the encoding. Encoding parameters that can be modified include the GOP length, the number of reference frames for inter-prediction, the maximum number of consecutive B-frames, the usage of B-frames as reference frames, the placement of adaptive B-frames, the motion estimation algorithm, the maximum range for motion estimation, the subpixel motion estimation algorithm (for fine motion estimation), and the allowable partitions for subpartitioning. In addition to the encoding parameters, the target bitrate, which can be thought of as another input parameter, is also specified in many applications as a function of frame size, available network bandwidth, and other considerations.

Using default configurations to set the input parameters for encoding can lead to encoding inefficiencies when the input parameters are not well-matched to the characteristics of the video data. Consider a method where target bitrate is specified based on the frame resolution, for example. In this case, the same target bitrate is applied independently of the content in the video. If the video content has low spatial complexity and low motion, the target bitrate will likely be “too high” and bits will be wasted because acceptable quality could be achieved with fewer bits; if the video content is spatially complex with high motion, the target bitrate will likely be “too low” and the encoding quality will be poor. The solution to this type of “settings mismatch” is to characterize the video data and then perform “smart” encoding with content-adaptive input parameters.

In general, the process of characterizing video data to derive data-adaptive input parameters involves a few essential steps. First, the data needs to be characterized by computing one or more metrics. Second, the metric values need to be converted to decisions about the input parameters. Third, to determine the effectiveness of the process, the modified encodings with data-adaptive input parameters should be compared against “original” encodings with default input parameters.

Different methods and systems have been proposed to adapt input parameters for video encoding based on the video characteristics. In [Carmel, S. et al., “Quality driven video re-encoding,” U.S. patent application Ser. No. 14/912,291, filed Aug. 11, 2014], a metric called block-based coding quality is computed for a given video to be encoded (referred to herein as a source video) and then a decision is made as to how much the target bitrate can be lowered while maintaining an acceptable value of the quality metric. In this case, there is a single metric to compute and a single input parameter to be modified (the target bitrate), and the video to be encoded must be re-encoded in a closed-loop system to obtain the “improved” (lower-bandwidth) encoding. In [Koren, N. et al., “Encoding/transcoding based on subjective video quality preferences,” U.S. Patent Application Ser. No. 15/049,051, filed Feb. 20, 2016], video quality (VQ) is measured by an “objective VQ compare module” to determine how closely an encoded video matches a user's “VQ profile” (representing the user's aesthetic video preferences), with the results fed back to allow re-encoding of the video at a lower bandwidth or higher quality. Koren et al. gives no details as to what constitutes the metrics in the “objective VQ compare module” or what input parameters are modified in the re-encoding. It is clear, however, that both of the methods described above are closed-loop systems that require multiple encodings of the same source video to obtain the final encoding with improved settings.

SUMMARY

Embodiments of the present invention take a different improved approach toward characterizing videos for smart encoding, involving considerations of human perception and perceptual quality optimization (PQO) at every step. In the first step, encoded videos are characterized using metrics designed to capture some aspect of perceptual quality by comparing the encoded videos with the original source videos. These metrics may include a perceptual quality metric based on a perceptual unified importance map combining spatial and temporal importance as proposed in [Lee, N. et al., “Perceptual optimization for model-based video encoding,” U.S. patent application Ser. No. 14/845,067, filed Sep. 3, 2015]; the gradient magnitude similarity deviation (GMSD) metric [Xue, W. et al., “Gradient magnitude similarity deviation: A highly efficient perceptual image quality index,”IEEE Trans. on Image Processing,23(2):684-695, 2013]; the just noticeable difference (JND) metric [Yang, X. et al., “Motion-compensated residue processing in video coding based on just-noticeable-distortion profile,”IEEE Trans. on Circuits, Systems, and Video Technology,15(6):742-752, 2005]; and the structural similarity (SSIM) metric [Wang, Z. et al., “Image quality assessment: From error visibility to structural similarity,”IEEE. Trans. on Image Processing,13(4):600-612, 2004].

Second, the metrics are combined into a prediction of perceptual quality based on training data from multiple subjective viewing tests (herein referred to as “subjective tests”) conducted on a set of video encodings for a range of videos. The scores from the subjective tests are averaged to obtain mean opinion scores (MOS), a widely-accepted measure of human perceptual quality. The MOS values from the subjective tests, together with the metric measurements, form the training data. The goal then is to form a model, based on the training data, that predicts MOS as a function of metric values. In one embodiment, a linear model is assumed (i.e., the predicted mean opinion score is a linear combination of metric values) and the coefficients of the linear model are derived from a least-squared error fit of the metric values to the MOS training data. In another embodiment, support vector regression for multiple outputs is used to fit the metric data to the MOS training data to derive the model [Xu, S. et al., “Multi-output least-squares support vector regression machines,”Pattern Recognition Letters,34(9):1078-1084, 2013]. The combination of metrics to create a model to predict MOS as a measure of human perceptual quality provides an important distinction between embodiments of the present invention and the prior art in content-adaptive encoding cited above, all of which base their adaptations on objective metrics that attempt to approximate MOS, rather than adapting based on predictions of the subjective MOS metric, as in embodiments of the present invention.

Third, the model predicting mean opinion scores is extended to a model relating metric values to encoding decisions. In one embodiment, metric values measured from multiple encodings of a source video are fed into the model to predict MOS values, resulting in predicted rate-quality curves that are then interpolated to find the relationship between bitrate and predicted mean opinion score for the given source video, and this relationship is used to determine the lowest target bitrate that can achieve a desired mean opinion score, thus estimating target bitrate. In another embodiment, metric values for segments of video data are used to estimate the best target bitrate for each segment.

This three-step process allows for the simultaneous optimization of both encoding quality and encoding bandwidth, either lowering bandwidth for low-complexity, low-motion videos or raising bandwidth for high-complexity, high-motion videos, all while seeking to attain a desired MOS. This is in contrast to embodiments of the present invention in [Carmel, S. et al., 2014], for example, which only seeks to determine how much bandwidth can be lowered while maintaining a minimum quality level and provides no recourse for raising bandwidth when needed for complex videos.

The metrics noted above may also be combined to discern certain video characteristics that indicate better encoding performance is likely if certain encoding parameters are changed. In one embodiment, when metrics from the unified importance map indicate that the video data has low motion and low complexity, the number of B-frames in the encoding is increased.

Perceptual importance maps as mentioned above model the response of the human visual system (HVS) to video content, indicating which parts of each video frame are most noticeable to human perception. Importance maps take on values for each data block in a video frame, and the importance map values for any given data block may change from frame to frame throughout the video. Generally, importance maps are defined such that higher values indicate more important data blocks. A perceptual importance map designed to improve encoding may be adapted into a perceptual quality measure by focusing on only those parts of the importance map calculation that are independent of the encoder's rate control.

Example embodiments are directed to computer systems, methods, and program products for iteratively predicting a target bitrate for producing a desired mean opinion score (MOS). The computer systems comprise at least one processor and memory with computer code instructions stored thereon. The memory is operatively coupled to the processor such that, when executed by the processor, the computer code instructions cause the computer system to execute the methods.

Some of the computer methods, systems, and program products iterate through the following (1)-(4) until a predicted MOS value is close to the desired MOS value. (1) The computer methods, systems, and program products generate an initial encoding of a source video and a decoding of the initial encoding. (2) The computer methods, systems, and program products next compute a first metric and a second metric on the initial encoding, the first metric being based on a video-average gradient magnitude similarity deviation (GMSD) and the second metric being based on a log-normalized mean GMSD. (3) The computer methods, systems, and program products apply a previously-derived model that predicts a mean opinion score (MOS) value for the initial encoding as a function of measurements of the computed first metric and second metric. (4) The computer methods, systems, and program products determine a target bitrate to encode and decode the source video based on a relationship between the predicted MOS value and a desired MOS value.

In example embodiments, the computer methods, systems, and program products derive the previously-derived model as follows. The computer methods, systems, and program products conduct subjective tests on a set of video encodings for a range of videos to generate training data. The computer methods, systems, and program products further obtain, from the subjective tests, mean opinion score (MOS) values by averaging scores provided by human subjects for the set of video encodings. The computer methods, systems, and program products compute the measurements of the first metric and second metric on the video encodings of the training data. The computer methods, systems, and program products calculate, based on the obtained MOS values and the computed metric measurements, a linear model that predicts MOS values as a function of metric values, using a pseudoinverse method. The calculated linear model outputs a model coefficient vector having length equal to the number of the computed metric measurements plus one.

In example embodiments, the computer methods, systems, and program products smooth the training data by fitting a line through the mean score values for the initial encoding and using the smoothed mean opinion score values instead of the mean score values for the initial encodings. In some example embodiments, the computer methods, systems, and program products determine the model that predicts MOS values as a function of metric values from a multi-output least-squares support vector regression (MLS-SVR) method instead of as a linear model. In some example embodiments, the model that predicts MOS values as a function of metric values de-emphasizes certain types of training data by first assigning the training data of certain types weights less than 1, and assigning the remaining training data weights of 1. In these example embodiments, the computer methods, systems, and program products then compute a resulting model coefficient vector using a weighted least squares method.

In some example embodiments, where multiple encodings and decodings of the source video are performed at once initially, the computer methods, systems, and program products perform the following. The computer methods, systems, and program products first compute the first and second metrics on multiple decoded data streams. The computer methods, systems, and program products next predict MOS values for the multiple decoded data streams by applying the previously-derived model to measurements of the computed first and second metrics. The computer methods, systems, and program products then collect the predicted MOS values together with output bitrates of the multiple encodings of the source video to form a predicted rate quality curve. The computer methods, systems, and program products perform interpolation or extrapolation on the predicted rate-quality curve to determine the target bitrate that achieves the desired MOS value.

In some example embodiments, the computer methods, systems, and program products apply a performance margin to the determined target bitrate by adding the performance margin to the determined target bitrate, resulting in a more conservative target bitrate. In some of these example embodiments, the computer methods, systems, and program products instead determine the performance margin by reducing the predicted MOS values by an amount, resulting in a more conservative target bitrate. In some example embodiments, the computer methods, systems, and program products apply steps (1)-(4) to segments of the source video rather than the entire source video, resulting in a set of recommended encoding bitrates, one for each video segment.

In some example embodiments, the computer methods, systems, and program products employ temporal subsampling to reduce the computation time to predict target bitrates for long source videos. For each video segment, the computer methods, systems, and program products choose a representative sub-segment on which to perform the target bitrate prediction by first finding the representative sub-segment by determining an appropriately complex portion of the video segment with a relatively high encoding cost. The computer methods, systems, and program products next estimate an encoding cost of a video frame as an average block variance of a difference signal between a current video frame and a previous video frame. The computer methods, systems, and program products further determine an encoding cost of a sub-segment of video frames equal to an average encoding cost of the video frames in the sub-segment. The computer methods, systems, and program products compute an encoding cost threshold by sorting encoding costs of each video frame in the video segment, and using a 50th percentile of the sorted encoding costs. The computer methods, systems, and program products then select the representative sub-segment having an encoding cost closest to the encoding cost threshold.

In some of these example embodiments, the computer methods, systems, and program products modify the temporal subsampling to account for scene changes by the following. When a scene change is detected, the computer methods, systems, and program products compute a modified encoding cost threshold using a 90thpercentile of the sorted encoding costs of each video frame in the video segment. The computer methods, systems, and program products then select the representative sub-segment having an encoding cost closest to the modified encoding cost threshold.

In some example embodiments, the computer methods, systems, and program products extend target bitrate predictions for the source video at a given frame size to compute bitrate predictions for the source video at different frame sizes. The encoded target bitrate predictions are used in adaptive bitrate (ABR) applications that require multiple encodings of the source video at different frame sizes and bitrates. The computer methods, systems, and program products then derive the encoded bitrate predictions at different frame sizes by scaling up or down the encoded bitrate prediction at the given frame size by a constant scaling factor, the constant scaling factor being derived from empirical subjective test data. In some of these example embodiments, the computer methods, systems, and program products derive the scaling factors to be content-dependent, based on temporal complexity of the source video, by the following. The computer methods, systems, and program products define the temporal complexity of the source video as an average motion vector magnitude of the video encoding. The defining includes adjusting constant scaling factors to be more conservative for more complex content, resulting in higher scaled bitrates, and more aggressive for less complex content, resulting in lower scaled bitrates. In other example embodiments, the computer methods, systems, and program products derive the scaling factors to be content-dependent, based on the quality of the respective video bitstreams at the smaller frame sizes, with quality measured using average P-frame QP value. In such embodiments, a dynamic scaling factor may be computed using encoding at a first frame size and an initial encoding at a second frame size in a dynamic scaling process. According to an embodiment, the dynamic scaling process adjusts the dynamic scaling factor iteratively, until average P-frame QP values of the encoding at the first frame size and the adjusted encoding at the second frame size converge, to determine a final scaling factor. This final scaling factor can, in turn, be used to compute a final bitrate at the second frame size and a final encoding at the second frame size.

In some example embodiments, for source videos consisting of a main part of a video frame and a banded part of the video frame having horizontal bands at the top and bottom of the video frame, the computer methods, systems, and program products perform the following. The computer methods, systems, and program products predict the target bitrates for the main part separately from the banded part using separate models. The computer methods, systems, and program products then compute the target bitrate for the entire source video as a linear combination of the target bitrates for the main part and the banded part.

In some example embodiments, the computer methods, systems, and program products instead compute the first metric and the second metric for the initial encodings of the source video based on a normalized perceptually-weighted PSNR (NPW-PSNR) metric as follows. The computer methods, systems, and program products calculate a perceptual unified importance map that includes both spatial and temporal offsets that represent spatial and temporal importance of each data block of the source video encodings. The computer methods, systems, and program products next combine the source video encodings into a total offset map. To combine the source video encodings, the computer methods, systems, and program products determine (i) the spatial offset determined from a spatial complexity map based on block variance and edge strength and (ii) the temporal offset from a temporal importance map that estimates how important each data block is to the encoding of future data blocks in the source video. The computer methods, systems, and program products further use the total offset map as a weighting to compute perceptually-weighted PW-PSNR for each video frame in the source video to obtain a frame-average PW-PSNR. The computer methods, systems, and program products then average the frame-average PW-PSNR values across video frames to obtain a video-average PW-PSNR. The computer methods, systems, and program products normalize the video average PW-PSNR by a measure of video complexity to obtain a normalized PW-PSNR measurement. The video complexity being computed as a combination of the spatial and temporal complexity of the source video.

Some of the computer methods, systems, and program products are for selecting videos for a training set that models video quality. The computer methods, systems, and program products provide a set of perceptual quality metrics, a desired mean opinion score (MOS), and a bitrate cap defining a maximum encoding bitrate. The computer methods, systems, and program products collect test data for video encodings for a range of videos. The test data is derived from an original set of training videos and comprises MOS values assigned by human subjects to the encodings and output bitrates from the encodings. The computer methods, systems, and program products generate, for each video in the training set, measurements of the perceptual quality metrics of the test data and a resulting estimate of a target encoding bitrate achieving the desired MOS value. The computer methods, systems, and program products then apply a baseline model that relates the generated perceptual quality metric measurements to the MOS values of the test data. The computer methods, systems, and program products next modify the training set by omitting videos having an estimated target encoding bitrate exceeding the bitrate cap. The computer methods, systems, and program products recalculate the baseline model using the modified training set.

Some of the computer methods, systems, and program products are for determining an optimal subset of perceptual quality metrics for constrained bitrate encoding applications as follows. The computer methods, systems, and program products provide a set of perceptual quality metrics and a desired MOS value. The computer methods, systems, and program products also collect subjective test data for encodings derived from a training set of videos. The subjective test data includes MOS values assigned by human subjects to the encodings and output bitrates from the encodings. The computer methods, systems, and program products further analyze the subjective test data to determine, for each video in the training set, a true bitrate that would achieve the desired MOS value. The computer methods, systems, and program products derive, for each subset of perceptual quality metrics and each video in the training set, a model that predicts MOS as a function of a measured subset of perceptual quality metrics. The computer methods, systems, and program products use the derived model for each subset of the perceptual quality metrics and each video in the training set. The derived model estimates a model bitrate for achieving the desired MOS value.

The computer methods, systems, and program products next calculate, for each subset of the perceptual quality metrics and each video in the training set, a bitrate error representing the difference between the model bitrate and the true bitrate. The computer methods, systems, and program products further select an optimal set of the perceptual quality metrics that produces a largest average bitrate savings, while incurring no underestimates where the model bitrate is more than a given percentage lower than the true bitrate for any video in the training set. The selected optimal set produces video quality at the desired MOS and maximizing the average bitrate savings subject to a constraint on the target bitrate error. In example embodiments, the fixed percentage is ten percent. In example embodiments, the bitrate encoding application is an adaptive bitrate application that uses a fixed bitrate encoding ladder, wherein the application encodes all videos at a given frame size at one or two fixed bitrates.

Some of the computer methods, systems, and program products are for determining an optimal number of B-frames for encoding a video. The computer methods, systems, and program products compute a temporal complexity metric for a video. The computer methods, systems, and program products then determine whether the video is temporally simple. If determined, the computer methods, systems, and program products increase the number of B-frames for encoding of the video.

