Patent Description:
Embodiments of the present invention relate generally to computer science and, more specifically, to constant-slope bitrate allocation for distributed encoding.

Efficiently encoding source data is essential for real-time delivery of video content. To optimize encoding time, distributed encoding processes parallelize the encoding work across multiple compute instances. In one approach to distributed encoding, an encoding subsystem decomposes source data (e.g., a video) into individual source chunks and distributes per-chunk encoding across multiple compute instances. Because the compute instances encode each source chunk independently of and in parallel to the other source chunks, encoding time is optimized. However, because there is no feedback between the compute instances during the per-chunk encoding, globally optimizing encoding decisions across the chunks during the encoding process is difficult. Consequently, conventional approaches for allocating the number of bits used to encode each of the source chunks, also referred to herein as the bitrate, oftentimes result in sub-optimal tradeoffs between bitrate and visual quality.

For instance, in one approach to allocating bitrates, the encoding subsystem computes a single bitrate based on the complexity of the source data. The encoding subsystem then configures the compute instances to apply the bitrate to each of the source chunks. However, in situations where the complexity of the source data differs noticeably between source chunks, the tradeoff represented by the single bitrate can be sub-optimal. More specifically, suppose that the encoding subsystem computes a bitrate based on an average complexity of a simple cartoon, but a particular source chunk includes a detailed action sequence. This computed bitrate results in an under-allocation of bits to the source chunk that includes the detailed action sequence, which causes that chunk of the cartoon to have relatively poor visual quality compared to the other chunks making up the cartoon. Conversely, suppose that the encoding subsystem computes a bitrate based on an average complexity of a detailed action movie, but a particular source chunk includes rolling credits. Here, the computed bitrate results in an over-allocation of bits to the source chunk that includes the rolling credits, which takes away resources from the other chunks making up the detailed action movie, such as storage and bandwidth usage, without noticeably increasing overall visual quality of the movie.

To improve the allocation of bits across the different chunks making up source data, some encoding approaches compute a single constant rate factor that represents a target overall level of visual quality. For each source chunk, a compute instance estimates the complexity of each frame included in the source chunk and then allocates the number of bits used to encode each frame based on the estimated complexity and the constant rate factor. Accordingly, encoding based on this type of constant rate factor typically results in visual qualities across chunks that are more uniform compared to visual qualities across chunks that would have resulted from encoding based on a single bitrate, as described above.

However, because the different compute instances compute the bitrate for each source chunk independently from one another, the constant rate factor does not typically result in globally optimized bitrates that balance between resource allocation across different chunks with visual quality. In particular, with a constant rate factor approach, each additional bit that the compute instances allocate during encoding may still result in an over-allocation of bits to one chunk and an under-allocation of bits to a different chunk. Consequently, for the total number of bits that are used to encode the source data, the overall visual quality of the aggregate encode may not be optimized. Further, constant rate factor encoding is only available in certain encoders. For example, constant rate factor encoding is not available in the libvpx implementation of VP9.

As the foregoing illustrates, what is needed in the art are more effective approaches for allocating bitrates during distributed encoding processes. <CIT> considers methods and devices for efficient adaptive bitrate streaming. <CIT> relates to techniques for optimizing bitrates and resolutions during encoding.

The invention to which this European patent is directed is defined in the independent claims.

One advantage of the disclosed techniques is that encoding each chunk based on the chunk-specific computed bitrate results in an aggregate encode that is optimized across the chunks with respect to the single computed optimization factor. Consequently, unlike conventional bitrate allocation techniques for distributed encoding, for any given bitrate, the constant-slope bitrate allocator optimizes the overall visual quality of the aggregate encode.

So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments.

In the following description, numerous specific details are set forth to provide a more thorough understanding of the present invention. However, it will be apparent to one of skilled in the art that the present invention may be practiced without one or more of these specific details.

<FIG> is a conceptual illustration of an encoding system <NUM> configured to implement one or more aspects of the present invention. As shown, the encoding system <NUM> includes a virtual private cloud (i.e., encapsulated shared resources, software, data, etc.) <NUM> connected to a variety of devices capable of transmitting input data and/or displaying video content. Such devices include, without limitation, a game console <NUM>, a smartphone <NUM>, a smart television <NUM>, a laptop <NUM>, a tablet <NUM>, and a desktop computer <NUM>. In alternate embodiments, the encoding system <NUM> may include any number and/or type of input, output, and/or input/output devices in any combination.

The virtual private cloud <NUM> includes, without limitation, any number and type of compute instances <NUM>. The virtual private cloud <NUM> receives input user information from an input device (e.g., the laptop <NUM>), one or more computer instances <NUM> operate on the user information, and the virtual private cloud <NUM> transmits processed information to the user. The virtual private cloud <NUM> conveys output information to the user via display capabilities of any number of devices, such as a conventional cathode ray tube, liquid crystal display, light-emitting diode, or the like.

In alternate embodiments, the virtual private cloud <NUM> may be replaced with any type of cloud computing environment, such as a public or a hybrid cloud. In other embodiments, the encoding system <NUM> may include any distributed computer system instead of the virtual private cloud <NUM>. In yet other embodiments, the encoding system <NUM> does not include the virtual private cloud <NUM> and, instead, the encoding system <NUM> includes a single computing unit that implements multiple processing units (e.g., central processing units and/or graphical processing units in any combination).

For explanatory purposes, multiple instances of like objects are denoted with reference numbers identifying the object and parenthetical numbers identifying the instance where needed. As shown for the compute instance <NUM>(P), each compute instance <NUM> includes, without limitation, a processor <NUM> and a memory <NUM>. The processor <NUM> may be any instruction execution system, apparatus, or device capable of executing instructions. For example, the processor <NUM> could comprise a central processing unit (CPU), a graphics processing unit (GPU), a controller, a microcontroller, a state machine, or any combination thereof. The memory <NUM> stores content, such as software applications and data, for use by the processor <NUM> of the compute instance <NUM>.

The memory <NUM> may be one or more of a readily available memory, such as random access memory (RAM), read only memory (ROM), floppy disk, hard disk, or any other form of digital storage, local or remote. In some embodiments, a storage (not shown) may supplement or replace the memory <NUM>. The storage may include any number and type of external memories that are accessible to the processor <NUM>. For example, and without limitation, the storage may include a Secure Digital Card, an external Flash memory, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing.

In general, the compute instances <NUM> included in the virtual private cloud <NUM> are configured to implement one or more applications. More specifically, the compute instances <NUM> included in the virtual private cloud <NUM> are configured to encode source data <NUM>, such as a video file. As shown, the compute instances <NUM>(P)-<NUM>(Q) are configured as an encoding preprocessor <NUM>, the compute instances <NUM>(<NUM>)-<NUM>(N) are configured as a parallel chunk encoder <NUM>, and the compute instance <NUM>(M) is configured as a multi-chunk assembler <NUM>. In alternate embodiments, any number of the compute instances may be configured as the encoding processor <NUM>, the parallel chunk encoder <NUM>, and the multi-chunk assembler <NUM>, in any combination. For example, in some embodiments, the compute instance <NUM>(<NUM>) could be configured as both the encoding preprocessor <NUM> and the multi-chunk assembler <NUM>, and the compute instances <NUM>(<NUM>)-<NUM>(<NUM>) could be configured as the parallel chunk encoder <NUM>.

In operation, a source chunker <NUM> included in the encoding preprocessor <NUM> receives the source data <NUM> and breaks the source data <NUM> into N different source chunks (not shown in <FIG>) where N corresponds to the number of compute instances <NUM> included in the parallel chunk encoder <NUM>. For each source chunk, the encoding preprocessor <NUM> generates an encoding task <NUM> that configures a different one of the compute instances <NUM> included in the parallel chunk encoder <NUM> to perform encoding operations on the source chunk to create a corresponding chunk encode <NUM>. The multi-chunk assembler <NUM> then combines the chunk encodes <NUM>(<NUM>)-<NUM>(N) into an aggregate encode <NUM>. In alternate embodiments, the source chunker <NUM> may break the source data <NUM> into any number of source chunks, and the number of source chunks may or may not equal the number of compute instances <NUM> included in the parallel chunk encoder <NUM>.

As persons skilled in the art will recognize, each of the source chunks includes source data for a specific time interval. Consequently the bitrate at which the parallel chunk encoder <NUM> encodes a particular source chunk determines the number of bits that are included in the resulting chunk encode <NUM>. Accordingly, optimizing the bitrate for a particular source chunk may also be referred to herein as optimizing the number of bits allocated for encoding the source chunk or allocating the optimum number of bits for encoding the source chunk.

To optimize encoding time, irrespective of the number of chunks and the number of computer instances <NUM> included in the parallel chunk encoder <NUM>, the parallel chunk encoder <NUM> encodes the source chunks independently and substantially in parallel. As referred to herein, encoding source chunks "substantially in parallel," comprises performing different encoding operations involving two or more source chunks, where at least a portion of the different encoding operations overlap partially or fully in time. One limitation of the parallel chunk encoder <NUM> is that there is no feedback between the compute instances <NUM> that encode different chunks during the per-chunk distributed encoding process. Consequently, optimizing tradeoffs across the chunks during the encoding process is difficult. In particular, conventional approaches for allocating the number of bits used to encode each of the source chunks, also referred to herein as the bitrate, oftentimes result in sub-optimal tradeoffs between bitrate and visual quality.

For instance, some conventional encoding approaches compute a single constant rate factor that represents a target overall level of visual quality. For each source chunk, a compute instance independently estimates the complexity of each frame included in the source chunk and then allocates the number of bits used to encode each frame based on the estimated complexity and the constant rate factor. However, because the different compute instances compute the bitrate for each source chunk independently from one another, the constant rate factor does not typically result in globally optimized bitrates that balance between resource allocation across different chunks with visual quality. In particular, with a constant rate factor approach, each additional bit that the compute instances allocate during encoding may still result in an over-allocation of bits to one chunk and an under-allocation of bits to a different chunk. Consequently, for the total number of bits that are used to encode the source data, the overall visual quality of the aggregate encode may not be optimized. Further, constant rate factor encoding is only available in certain encoders. For example, constant rate factor encoding is not available in the libvpx implementation of VP9.

To ensure that each additional bit that the parallel chunk encoder <NUM> allocates during encoding of the source data <NUM> is allocated to the optimal chunk encode <NUM>, the encoding preprocessor <NUM> includes a constant-slope bitrate allocator <NUM>. In general, the constant-slope bitrate allocator <NUM> implements a constant slope interpretation of Lagrangian optimization to globally optimize a single bitrate-quality tradeoff while allocating bitrates to source chunks. More specifically, the constant-slope bitrate allocator <NUM> determines a Lagrange multiplier, referred to herein as lambda (λ), that reflects a desired, global bitrate-quality tradeoff for the source data <NUM>. For each source chunk, the constant-slope bitrate allocator <NUM> then individually computes an optimized chunk-specific bitrate, referred to herein as a chunk bitrate, based on a chunk-specific bitrate-quality curve and the single lambda.

For each source chunk, the encoding preprocessor <NUM> then generates the encoding task <NUM> that configures the corresponding compute instance <NUM> included in the parallel chunk encoder <NUM> to encode the source chunk at the associated chunk bitrate. As persons skilled in the art will recognize, because each of the chunk bitrates is optimized with respect to lambda, Lagrangian optimization ensures that the chunk encodes <NUM> are globally optimized with respect to the global bitrate-quality tradeoff reflected by lambda. Consequently each additional bit allocated during encoding is allocated to the optimal chunk encode <NUM> and, for the total number of bits that are included in the resulting aggregate encode <NUM>, the overall visual quality of aggregate encode <NUM> is optimized.

Note that the techniques described herein are illustrative rather than restrictive, and may be altered without departing from the broader scope of the invention. In particular, the functionality provided by the constant-slope bitrate allocator <NUM> may be implemented in any number (including <NUM>) of compute instances <NUM> and software applications in any combination. For example, in some embodiments, each of the compute instances <NUM> included in the parallel chunk encoder <NUM> may implement a portion of the functionality of the constant-slope bitrate allocator <NUM>. In such embodiments, in addition to encoding the source chunks substantially in parallel, the compute instances <NUM> included in the parallel chunk encoder <NUM> may compute optimized chunk bitrates individually and substantially in parallel.

<FIG> is a more detailed illustration of the constant-slope bitrate allocator <NUM> of <FIG>, according to various embodiments of the present invention. As shown, the constant-slope bitrate allocator <NUM> includes, without limitation, a complexity analyzer <NUM> and a bitrate optimization engine <NUM>. As also shown, the source data <NUM> is partitioned into source chunks <NUM>(<NUM>)-<NUM>(N).

The complexity analyzer <NUM> receives all the source chunks <NUM> included in the source data <NUM> and computes a lambda <NUM> based on a desired rate-quality tradeoff for the source data <NUM>. The complexity analyzer <NUM> may be configured to implement any desired rate-quality tradeoff in any technically feasible fashion. As persons skilled in the art will recognize, the complexity analyzer <NUM> may leverage techniques that are conventionally used to compute a single constant rate factor that represents a target visual quality. The lambda <NUM> is also referred to herein as a Lagrangian multiplier and/or an optimization factor.

For example, the complexity analyzer <NUM> could be configured to determine a bitrate that ensures that <NUM> percent of the chunk encodes <NUM> exceed a predetermined visual quality level. The complexity analyzer <NUM> could encode the source chunks <NUM> included in the source data <NUM> at the predetermined visual quality level and then construct a cumulative distribution function (CDF) based on the corresponding encoded bitrates. Based on the CDF, the complexity analyzer <NUM> could set a "representative" source chunk <NUM> and a "representative" bitrate to, respectively, the source chunk <NUM> and the encoded bitrate that correspond to the <NUM>th percentile of the source chunks <NUM>.

For the representative source chunk <NUM>, the complexity analyzer <NUM> could generate multiple representative pre-encodes at a variety of visual quality levels and then construct a representative bitrate-quality curve based on the representative pre-encodes. Subsequently, the complexity analyzer <NUM> could select a tangent to the representative bitrate-quality curve at the representative bitrate or quality as the global bitrate-quality tradeoff. Finally, the complexity analyzer <NUM> could set the lambda (i.e., the Lagrangian multiplier in a constant-slope interpretation of Lagrangian optimization) equal to the slope of the tangent.

In alternate embodiments, the constant-slope bitrate allocator <NUM>, the complexity analyzer <NUM>, or any other component included in the encoding system <NUM> may determine the global bitrate-quality tradeoff and/or the lambda <NUM> in any technically feasible fashion. For instance, in some embodiments, the complexity analyzer <NUM> may implement heuristics to estimate the representative chunk and representative bitrate. In other embodiments, the constant-slope bitrate allocator <NUM> may not include the complexity analyzer <NUM>, and the constant-slope bitrate allocator <NUM> may receive the lambda <NUM> from a graphical user interface.

In general, the constant-slope bitrate allocator <NUM> may determine the lambda <NUM> based on any number of heuristics and configuration inputs. Some examples of configuration inputs include a specified type of the source data <NUM> (e.g., action file, documentary, etc.), a target visual quality, and a programmable parameter that specifies a percentile for identifying a representative chunk, to name a few. In alternate embodiments, the constant-slope bitrate allocator <NUM> or the complexity analyzer <NUM> may select the lambda <NUM> in any technically feasible fashion based on resource constraints such as available bandwidth, equipment capabilities, and the like. For example, the complexity analyzer <NUM> could implement iterative techniques (e.g., bisection search) to determine a value for the lambda <NUM> that meets a total "budget" of bits available for encoding.

As shown, for each of the source chunks <NUM>, a separate instance of the bitrate optimization engine <NUM> receives the source chunk <NUM> and the lambda <NUM>, and then computes a chunk bitrate <NUM> associated with the source chunk <NUM>. The instances of the bitrate optimization engine <NUM> operate on the source chunks <NUM> individually and substantially in parallel. In alternate embodiments, the constant-slope bitrate allocator <NUM> may include any number of instances (including <NUM>) of the bitrate optimization engines <NUM>. Further the instances of the bitrate optimization engines <NUM> may operate concurrently, sequentially, or in any combination thereof.

Irrespective of how the bitrate optimization engine <NUM> is configured to operate on the source chunks <NUM>, the bitrate optimization engine <NUM> performs Lagrangian optimization operations to determine the different chunk bitrate <NUM> for each of the source chunks <NUM> based on the lambda <NUM>. Consequently, encoding each of the source chunks <NUM> at the corresponding chunk bitrate <NUM> ensures that the aggregate encode <NUM> is optimized with respect to the global bitrate-quality tradeoff reflected by the lambda <NUM>.

As shown, the bitrate optimization engine <NUM> includes, without limitation, a curve computation pass engine <NUM>, a curve fitter <NUM>, and a bitrate selector <NUM>. Upon receiving the source chunk <NUM>, the curve computation pass engine <NUM> generates four per-encodes <NUM>. More precisely, for each of four different predetermined visual quality levels, the curve computation pass engine <NUM> configures an encoder (e.g., the parallel chunk encoder <NUM>) to encode the source chunk <NUM> at the visual quality level.

In alternate embodiments, the curve computation pass engine <NUM> may generate any number of pre-encodes <NUM> at any number of visual quality levels. Further, the curve computation pass engine <NUM> may generate the pre-encodes <NUM> and determine the visual quality levels in any technically feasible fashion. For instance, in some embodiments the curve-computation pass engine <NUM> may implement heuristics to generate approximate pre-encodes <NUM> for twelve visual quality levels that the curve-computation pass engine <NUM> may receive from a graphical user interface.

Advantageously, the constant-slope bitrate allocator <NUM> and/or the complexity analyzer <NUM> may be configured based on any number and type of visual quality metrics (including distortion metrics) irrespective of the capabilities of the parallel chunk encoder <NUM>. Some examples of visual quality metrics include, without limitation, Video Multimethod Assesment Fusion (VMAF), detail loss measure (DLM), visual information fidelity (VIF), structural similarity (SSIM) index, and mean-squared-error (MSE). By contrast, conventional techniques for bit allocation rely on the visual quality metrics that are implemented in the parallel chunk encoder <NUM>.

The curve computation pass engine <NUM> analyzes each of the pre-encodes <NUM> to determine a corresponding bitrate-quality point <NUM>. More precisely, for each of the pre-encodes <NUM>, the curve-computation pass engine <NUM> generates the bitrate-quality point <NUM> that includes the bitrate of the pre-encode <NUM> and the predetermined visual quality level associated with the pre-encode <NUM>. In alternate embodiments, the curve computation pass engine <NUM> may generate the bitrate-quality points <NUM> in any technically feasible fashion. In some alternate embodiments, the curve computation pass engine <NUM> may not generate the pre-encodes <NUM> and instead implement heuristics to estimate the bitrate-quality points <NUM>.

Subsequently, the curve fitter <NUM> generates a bitrate-quality curve <NUM> that is associated with the source chunk <NUM> based on the bitrate-quality points <NUM>. The curve fitter <NUM> may generate the bitrate-quality curve <NUM> in any technically feasible fashion. For instance, in some embodiments and as described in detail below in conjunction with <FIG>, the curve fitter <NUM> may fit a logarithmic curve to the bitrate-quality curve <NUM> and then set the bitrate-quality curve <NUM> equal to the logarithmic curve. In other embodiments, the curve fitter <NUM> may fit a polynomial curve to the bitrate-quality points <NUM> and then set the bitrate-quality curve <NUM> equal to the polynomial curve.

As shown, the bitrate selector <NUM> receives the bitrate-quality curve <NUM> and the lambda <NUM>. In general, the bitrate selector <NUM> performs operations that identify a bitrate at which the slope of a tangent to the bitrate-quality curve <NUM> equals the lambda <NUM>. The bitrate selector <NUM> then sets the chunk bitrate <NUM> associated with the source chunk <NUM> equal to the identified bitrate. The bitrate selector <NUM> may perform any number and type of operations that are consistent with the characteristics of the bitrate-quality curve <NUM> and the characteristics of the lambda <NUM> to determine the chunk bitrate <NUM>. For example, as detailed below in conjunction with <FIG>, the bitrate selector <NUM> may set a derivative of the bitrate-quality curve <NUM> equal to the lambda <NUM> and then solve for the chunk bitrate <NUM>.

Note that the techniques described herein are illustrative rather than restrictive, and may be altered without departing from the broader scope of the invention. In particular, the functionality provided by the constant-slope bitrate allocator <NUM>, the bitrate optimization engine <NUM>, and/or the complexity analyzer <NUM> may be implemented in any number (including <NUM>) of software applications in any combination. Further, in various embodiments, any number of the techniques disclosed herein may be implemented while other techniques may be omitted in any technically feasible fashion.

Many modifications and variations on the functionality provided by the constant-slope bitrate allocator <NUM>, the bitrate optimization engine <NUM>, and/or the complexity analyzer <NUM> will be apparent to those of ordinary skill in the art without departing from the scope of the described embodiments. For example, in some embodiments, the constant-slope bitrate allocator <NUM> may be configured to generate and analyze bitrate-distortion curves instead of the bitrate-quality curves <NUM>.

<FIG> is an exemplary illustration of operations performed by the bitrate optimization engine <NUM>(i) of <FIG>, according to various embodiments of the present invention. As outlined previously herein, the bitrate optimization engine <NUM>(i) optimizes the chunk bitrate <NUM>(i) associated with the source chunk <NUM>(i) with respect to the lambda <NUM>. For explanatory purposes only, a sequence of operations is expressed graphically. Further, an analogous, alternate sequence of operations is expressed in equation form.

To compute the chunk bitrate <NUM>(i) graphically, the curve fitter <NUM>(i) executes the operations depicted by the circles labeled "<NUM>," "<NUM>, and "<NUM>. " First, as the circle labeled "<NUM>" depicts, the curve fitter <NUM>(i) fits a logarithmic curve to the bitrate-quality points <NUM>. The curve fitter <NUM>(i) then sets the bitrate-quality curve <NUM>(i) equal to the fitted logarithmic curve. In this fashion, the bitrate-quality curve <NUM>(i) approximates the bitrate-quality points <NUM>. Second, as the circle labeled "<NUM>" depicts, the curve fitter <NUM>(i) identifies a tangent to the bitrate-quality curve <NUM>(i) for which the slope equals the lambda <NUM>. Finally, as the circle labeled "<NUM>" depicts, the curve fitter <NUM>(i) set the chunk bitrate <NUM>(i) equal to the bitrate corresponding to the identified tangent.

To compute the chunk bitrate <NUM>(i) based on the bitrate-quality curve <NUM>(i) expressed in equation form (as an "express as logarithmic function" <NUM> depicts), the bitrate selector <NUM> first expresses the bitrate-quality curve <NUM> as a logarithmic function (L) of the bitrate (R) as follows:
<MAT>.

Second, as a "set derivative to lambda" <NUM> depicts, the bitrate selector <NUM> sets a derivative of the logarithmic function equal to the lambda <NUM> as follows:
<MAT>.

Finally, as a "solve for bitrate" <NUM> depicts, the bitrate selector <NUM> solves for the chunk bitrate <NUM>(i) as follows:
<MAT>.

In alternate embodiments, the bitrate optimization engine <NUM>(i) may implement any number and types of operations that optimize the chunk bitrate <NUM>(i) based on the lambda <NUM>. For example, to compute the chunk bitrate <NUM>(i), the bitrate optimization engine <NUM>(i) could divide the slope of a log-log graph of the bitrate-quality curve <NUM>(i) by the lambda <NUM>.

<FIG> is a flow diagram of method steps for allocating bitrates when encoding source data, according to various embodiments of the present invention. Although the method steps are described with reference to the systems of <FIG>, persons skilled in the art will understand that any system configured to implement the method steps, in any order, falls within the scope of the present invention.

As shown, a method <NUM> begins at step <NUM> where the complexity analyzer <NUM> computes the lambda <NUM> based on the source chunks <NUM> included in the source data <NUM>. The lambda <NUM> reflects a global bitrate-quality tradeoff for the source data <NUM>. The complexity analyzer <NUM> may compute the lambda <NUM> in any technically feasible fashion that is consistent with the use of the lambda <NUM> as a Lagrangian multiplier for optimizing the chunk bitrates <NUM>. For instance, in some embodiments, the complexity analyzer <NUM> may implement the method steps of <FIG> (described below) to compute the lambda <NUM>.

At step <NUM>, for each of the source chunks <NUM>, the curve computation pass engine <NUM> encodes the source chunk <NUM> at M predetermined visual quality levels to generate M pre-encodes <NUM>. At step <NUM>, for each of the source chunks <NUM>, the curve-computation pass engine <NUM> determines M bitrate-quality points <NUM> based on the M pre-encodes <NUM>. Each of the bitrate-quality points <NUM> includes a predetermined visual quality level and the encoded bitrate of the pre-encode <NUM> that is encoded at the predetermined visual quality level.

In alternate embodiments, the curve computation pass engine <NUM> may generate the pre-encodes <NUM> and/or determine the bitrate-quality points <NUM> in any technically feasible fashion. For instance, in some alternate embodiments, the curve computation pass engine <NUM> may estimate the bitrate-quality points <NUM> based on heuristics. In such embodiments, the curve computation pass engine <NUM> may not execute step <NUM>.

At step <NUM>, for each of the source chunks <NUM>, the curve fitter <NUM> fits a logarithmic curve to the M bitrate-quality points <NUM> to generate the bitrate-quality curve <NUM> associated with the source chunk <NUM>. In alternate embodiments, the curve fitter <NUM> may generate the bitrate-quality curve <NUM> in any technically feasible fashion. For instance, in alternate embodiments, the curve fitter <NUM> may fit a polynomial curve to the bitrate-quality points <NUM> and then set the bitrate-quality curve <NUM> equal to the polynomial curve.

At step <NUM>, for each of the source chunks <NUM>, the bitrate selector <NUM> identifies a tangent to the bitrate-quality curve <NUM> with a slope that is equal to the lambda <NUM>. The bitrate selector <NUM> may identify the tangent in any technically feasible fashion. At step <NUM>, for each of the source chunks <NUM>, the bitrate selector <NUM> sets the chunk bitrate <NUM> for the source chunk <NUM> based on the identified tangent for the associated bitrate-quality curve <NUM>. More specifically, the bitrate selector <NUM> sets the chunk bitrate <NUM> to the bitrate corresponding to the identified tangent.

In alternate embodiments, for each of the source chunks <NUM>(i), the bitrate selector <NUM> may compute the chunk bitrate <NUM>(i) based on the bitrate-quality curve <NUM>(i) in any technically feasible fashion. For instance, in some embodiments, the bitrate selector <NUM> may set a derivative of the bitrate-quality curve <NUM>(i) equal to the lambda <NUM> and then solve for the chunk bitrate <NUM>(i). In such embodiments, the bitrate selector <NUM> may not execute step <NUM> and/or <NUM>.

At step <NUM>, for each of the source chunks <NUM>, the encoding preprocessor <NUM> configures a separate compute instance <NUM> included in the parallel chunk encoder <NUM> to independently encode the source chunk <NUM> at the associated chunk bitrate <NUM>. In this fashion, the encoding preprocessor <NUM> ensures that the parallel chunk encoder <NUM> generates each of the chunk encodes <NUM> based on a single, global bitrate-quality tradeoff.

<FIG> is a flow diagram of method steps for computing a factor that is designed to optimize bitrate allocations and overall image quality when encoding source data, according to various embodiments of the present invention. Although the method steps are described with reference to the systems of <FIG>, persons skilled in the art will understand that any system configured to implement the method steps, in any order, falls within the scope of the present invention.

As shown, a method <NUM> begins at step <NUM>, where the complexity analyzer <NUM> encodes the source chunks <NUM> included in the source data <NUM> at a predetermined visual quality level to determine the corresponding encoded bitrates. At step <NUM>, the complexity analyzer <NUM> generates a cumulative distribution function (CDF) of the encoded bitrates. At step <NUM>, the complexity analyzer <NUM> selects a representative chunk and a representative bitrate based on the CDF and a predetermined percentile. More specifically, the complexity analyzer <NUM> analyzes the CDF and sets the representative bitrate to a bitrate that exceeds the encoded bitrates for the predetermined percentile of the source chunks <NUM>. The complexity analyzer <NUM> then sets the representative chunk to the source chunk <NUM> associated with the representative bitrate. In alternate embodiments, the complexity analyzer <NUM> may select the representative chunk and the representative bitrate in any technically feasible fashion.

At step <NUM>, for the representative chunk, the complexity analyzer <NUM> generates a representative pre-encode at each of M predetermined visual quality levels. At step <NUM>, the complexity analyzer determines M representative bitrate-quality points based on the M pre-encodes. Each of the M representative bitrate-quality point specifies a predetermined visual quality level and the encoded bitrate of the representative pre-encode that is encoded at the predetermined visual quality level.

At step <NUM>, the complexity analyzer <NUM> fits a logarithmic curve to the M representative bitrate-quality points to construct a representative bitrate-quality curve. In alternate embodiments, the complexity analyzer <NUM> may fit any type of curve to the representative bitrate-quality points in any technically feasible fashion. At step <NUM>, the complexity analyzer sets the lambda <NUM> to a slope of a tangent to the representative bitrate-quality curve corresponding to the representative bitrate. The method <NUM> then terminates.

In sum, the disclosed techniques may be used to allocate bitrates across the source chunks included in source data (e.g., movie, etc.) during a distributed encoding process. A constant-slope bitrate allocator includes a complexity analyzer and multiple instances of a bitrate optimization engine. The complexity analyzer analyzes the source chunks to compute a single lambda that represents a globally optimized tradeoff between bitrate and quality for encoding the source data. Subsequently and substantially in parallel, for each source chunk, an instance of a bitrate optimization engine leverages Lagrangian optimization techniques to compute a chunk bitrate based on the lambda. More specifically, for each source chunk, the bitrate optimization engine approximates a bitrate-quality curve associated with encoding the source chunk and identifies a point on the curve where the slope of the curve matches lambda. The bitrate optimization engine then sets the chunk bitrate equal to the bitrate of the identified point.

Advantageously, encoding each chunk based on the corresponding chunk bitrate results in an aggregate encode that is optimized across the chunks with respect to a global tradeoff between bitrate and quality. Consequently, unlike conventional bitrate allocation techniques for distributed encoding, for any given bitrate, the constant-slope bitrate allocator optimizes the overall visual quality of the aggregate encode. Further, unlike conventional bitrate allocation techniques that are based on a constant rate factor, encoders for any compression standard, including VP9, may implement the disclosed bitrate allocation techniques based on any quality metric.

Aspects of the present embodiments may be embodied as a system, method or computer program product. Accordingly, aspects of the present disclosure may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a ""module" or "system. " Furthermore, aspects of the present disclosure may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present disclosure.

Claim 1:
A computer-implemented method, comprising:
computing an optimization factor (<NUM>) for a plurality of chunks of source data by: generating a representative bitrate-quality curve that is associated with encoding a representative chunk included in the plurality of chunks, the representative chunk and a representative encoding bitrate being selected based on a cumulative distribution function of encoded bit rates of encoded versions of the plurality of chunks and a predetermined percentile;
computing a tangent to the representative curve corresponding to the representative encoding bitrate; and
setting the optimization factor equal to a slope of the tangent;
generating a logarithmic curve (<NUM>) based on a plurality of bitrate-quality points (<NUM>), wherein each point specifies a different visual quality level and a corresponding encoding bitrate for encoding a respective chunk included in the plurality of chunks (<NUM>) of source data;
computing an encoding bitrate (<NUM>) for encoding each respective chunk based on the generated logarithmic curve and the computed optimization factor; and
causing each respective chunk to be encoded at the respective encoding bitrate.