TECHNICAL FIELD

The present invention relates to methods, controllers and systems for complexity control of video codec using coding units, as well as software for implementing the methods or systems.

BACKGROUND

In the field of video coding and high efficient video coding, the encoding application can be one of many processes running on the host machine. Other processes can run in parallel, including operating system processes, and even other encoders and/or decoders. When the load on the host machine becomes significant, the software processes may compete for the same resources and influence each other' s processing speed. This can be problematic, particularly for a video encoder that is expected to deliver output at regular time intervals. Although buffering may solve some of these issues, adding a buffer introduces additional delay that is in many cases undesired. Conventional solutions often comprise carefully fine tuning configuration parameters and/or overprovisioning resources (e.g., selecting one of the more high- end cloud instances) resulting in additional effort and increased financial cost. Furthermore, when over dimensioning the system for the statistical "worst case" (e.g., the maximum number of video streams the cloud service should be able to handle) , there could be many occasions where the system resources are not being fully used .

G. Correa et al . ("Complexity scalability for real-time HEVC encoders," Journal of Real-Time Image Processing, pp. 1-16, 2014) propose a complexity scalability method for HEVC in which CTUs are dynamically constrained by limiting the prediction block (PB) and setting a maximum tree depth for each CTU.

Zhao et al . ("Flexible mode selection and complexity allocation in high efficiency video coding" Selected Topics in Signal Processing, IEEE Journal of, vol. 7, no. 6, pp. 1135-1144, Dec 2013) propose a hierarchical complexity allocation scheme for HEVC based on linear programming.

While these methods provide alternative means for obtaining complexity control, they report high variation of the encoding time over multiple GOPs (Group Of Pictures) .

SUMMARY OF THE INVENTION

It is an advantage of the present invention that a fully scalable solution for complexity control is provided, for optimal use of resources and where the spread in encoding time is converging.

Any of the embodiments of the invention can be implemented in an encoder .

An aspect of the present invention is a method or system or encoder to encode video frames having coding units which can be coded with a plurality of coding modes, by, for each coding unit of the frame the method steps of:

• Determining a rate distortion cost associated with encoding the coding unit with a given coding mode, for each of a chosen or selected number of coding modes being a reduced number of zones selected from the plurality of coding modes,

• Estimating an estimated rate distortion cost error as the difference between the lowest rate distortion cost amongst the determined rate distortion costs and an estimated lowest rate distortion cost amongst the complete plurality of coding modes,

wherein, the chosen number of coding modes is selected such that the difference between the rate distortion cost error and a target rate distortion cost error is minimised.

An example of a code is for example video compression.

Another aspect of the present invention relates to a method or system or encoder for adaptive use of

image frame processing resources comprising defining

a rate distortion cost error threshold or target

associated with received image frames, determining a

difference between a complexity associated with the

rate distortion cost error threshold or target and a

threshold or target complexity, and updating the

rate distortion cost error threshold or target to

reduce this difference. Preferably, process of

reducing the difference should not involve a

significant increase in the use of resources.

In the above methods or systems or encoders the use of resources may exceed or not exceed a target value. If more resources are used than the target value then other processes can be impaired. If less resources are used, then the guality of displayed video frames can be reduced. Accordingly, continuous adaption to changing parameters and video processing factors is preferred which results in the image frame processing resources varying dynamically in time.

In one embodiment of the present invention there is provided a system, a method or an encoder for adaptive use of image frame processing resources for video compression, the image frame processing resources varying dynamically in time, wherein the video signal comprises image frames processed at a video rate, wherein an image frame is expressed in a number of coding units, a coding unit having a predefined maximum size, the method comprising the steps: recursively splitting coding units into a guad-tree structure of different coding units having levels and sub-levels, wherein in a guad-tree structure, each level or sub-level is recursively split into parts, a depth of a specific coding unit being defined by the number of recursive splits of coding units that have been used in order to reach the specific coding unit, whereby the size of the specific coding unit is the maximum size divided by the number of recursive splits, a coding unit at a certain depth being encodable with a first number of different coding modes. The rate distortion cost for a second number of coding modes is determined, the second number being less or equal to the first number of different coding modes for the specific coding unit, the determining of the second number being such as to maximise the use of dynamically for the encoder available image frame processing resources, the difference between the rate distortion cost for the first and the rate distortion cost for the second number of coding modes is the rate distortion cost error, and the difference between the rate distortion cost error and a targeted rate distortion cost error has a minimum value for a certain coding mode, said coding mode is selected to encode the coding unit .

Alternatively a difference between an estimated rate distortion cost for the first number of coding modes and a determined rate distortion for the second number of coding modes is an estimated rate distortion cost error, and the difference between the estimated rate distortion cost error and a targeted rate distortion cost error has a minimum value for a certain coding mode, wherein said coding mode is selected to encode the coding unit.

The systems, encoders and methods described above provide means for maximizing the use of an available complexity budget (which refers, for example to a budget for vide frame processing resources) when performing video compression, while controlling the rate distortion cost.

A further useful step of embodiments of the present invention is to be able to normalize by dividing any of the processing factors with the number of pixels in the level to be calculated.

For example, the system, method or encoder can comprise use of a central processing or graphics processing unit to normalize the collection of pixels of the coding unit at level m and with index m, by dividing said coding unit with the number of pixels at the level m. By normalizing the procedure, the system, encoder or method becomes independent of coding level.

An advantage of the present invention is to be able to keep inside or close to a complexity budget per frame or to approach dynamically the complexity budget per frame. For example, the system, encoder or method can comprise, for each frame, the central processing or graphics processing unit providing a controller for adapting the threshold or target of the rate distortion cost error, based on the difference between the reduced complexity and the value of the complexity target in a or the previous frame stored in a memory.

By having a complexity budget per frame, distortions can be smeared out over each frame.

An advantage of the present invention is to be able to calculate in elapsed CPU OR GPU time. For example, the system, encoder or method can comprise the central processing or graphics processing unit having the controller calculating the complexity for a frame in elapsed central processing or graphics processing unit processing time for encoding the whole frame.

Accordingly, a practical measure of complexity can be to use the elapsed CPU OR GPU processing time. If too many resources are being used then this can appear as an increased CPU OR GPU processing time. If too few resources are being used then this can appear as a decreased CPU OR GPU processing time.

An advantage of the present invention is to assume that the values of a _m are independent of each other. For example, the system, encoder or method can comprising the central or graphics processing unit treating the actual number of coding modes for per coding unit being independent of each other.

In this way the system, encoder or method can be simplified by assuming that the coefficients _m (which is the actual number of coding modes evaluated for a coding unit at level m) are independent from each other. This simplification makes the calculations easier but can result in errors. Accordingly, it is preferred if methods of adaptive correction according to embodiments of the present invention are used to dynamically adjust the video frame processing.

An advantage of the present invention is to be able to estimate I _mN (which is a rate distortion cost for all modes N) . For example, the system, encoder or method can comprise the central processing or graphics processing unit estimating the rate distortion cost comprising all coding modes by assuming said cost is proportional to a linear model of the rate distortion cost comprising less than all coding modes. By estimating using a model the calculation of rate distortion costs for all coding modes is avoided. Since the optimal rate distortion (RD) cost I _m:N (for all modes N) is not known for l _mn where n<N, (i.e. when the rate distortion cost is not calculated for all coding modes N) it can be estimated, for example to be proportional to I _mn . For example, the system, encoder or method can comprise that an estimated rate distortion cost is linearly proportional to the rate distortion cost comprising all coding modes multiplied by the coefficient 0.87, 0.92, 0.94, 0.95 for the depth 0, 1, 2 and 3 respectively .

The inventors have found that the above mentioned coefficients provide a good estimate.

An advantage of the present invention is to be able to estimate only two groups of modes instead of many modes. For example, the system, encoder or method can comprise the central processing or graphics processing unit evaluating two groups of modes, the first group comprising the 2Nx2N merge mode and the second mode comprising all other modes. Accordingly, the system, encoder or method can be simplified by assuming that there are two groups of coding modes. An advantage of the present invention is to be able to program a controller. For example, the system, encoder or method can comprise the central processing unit or graphics processing unit implementing the controller based on a root-finding method. There are two types of root finding, namely bracketed and open methods. Both bracketed and open methods can be used with embodiments of the present invention. Different methods will have different performance characteristic, for example bracketed methods will converge but may take time to do so. Open methods may be quicker but do not necessarily always have a guarantee of convergence.

Examples of root finding methods such as a bisection method, a false position method, the Brent Dekker method, Muller's method, Simple fixed point iteration method, Newton' s method,

multidimensional Newton's method, secant method or similar.

A controller can be implemented to try out various modes for each coding unit; whereby the controller can be based on a root finding method such as the root-finding bisection method or one of the other methods mentioned above.

For example, the system, encoder or method can comprise the central or graphics processing unit instructing the controller to execute a root finding method of those mentioned above such as a bisection method with the following steps:

Set initial value to the step size, assign a variable "equal_sign" to True

If A and B can each be true or false, and A is the condition that the step size is larger than or equal to zero, and B is the condition that the reduced complexity is larger than or equal to the complexity threshold, and A is different from B, then

Reduce the step size to half and change direction

Set variable "equal_sign" to false

If A is equal to B and variable "equal_sign" is true, then double the step size without changing direction, Set variable "equal_sign" to false, and let the rate distortion cost error be increased by one step size unless this is smaller than zero, then let the rate distortion cost error target be zero. This may be written as pseudocode (Figure 3 ) : σ <- σ ₀

equal_sign - True

function UPDATETHRESHOLD(C7-, C _R )

if o≥ 0) ≠ (C _R > C _T ) then

σ - σ I—2

equal_sign - False

else

if equal_sign then

σ - 2σ

end if

equal_sign - True

end if

E _T - max(0, E _T + σ)

end function

This can be understood as

1 . Assign the step size sigma to an initial value, sigma zero.

2 . Assign the variable "equal_sign" to True. (Can also be

assigned to False, it may just change the number of

iterations) .

3 . The function UPDATE.... is just a notation/name for the rest of the code.

4. A first condition A is that the step size is larger or

equal to zero. A condition B is that the reduced complexity

CR should be larger or equal to the complexity threshold CT. If A is not equal to B, e.g (A, B) is (True, False) or (False, True) then

5 . Assign the step size sigma to sigma divided by - 2 , thus

reducing the step size to half and changing direction.

6. Assign "equal_sign" to False 7. Else: if the condition in 4 is not fulfilled

8. And if "equal_sign" is True

9. Then double the step size sigma (in the same direction)

10. Endif for line 8

11. Assign "equal_sign" to False (in any case)

12. Endif of line 4

13. Assign RD cost error target ET to (the RD cost error target ET + step size sigma) or zero, in case the (the RD cost error target ET + step size sigma) is less than zero 14. End of whole function.

The controller can be implemented with the above root-finding bisection method or another root finding method like the ones described above. The bisection method involves a low complexity and allows the methods, encoders and systems according to embodiments of the present invention to adapt dynamically and continuously .

In another embodiment there is provided a system, an encoder or a controller, or a method for adaptive use of image frame processing resources comprising a central processing or graphics processing unit connected to at least one memory, the central processing or graphics processing unit being configured to receive frames of a video signal, the central processing or graphics processing unit defining a rate distortion cost error threshold or target, the difference between the corresponding first complexity achieved with the use of the rate distortion cost error threshold or target and a first complexity threshold or target is stored in the memory as a reference for the calculation of an updated rate distortion cost error threshold or target, wherein the difference between a second complexity achieved with the updated rate distortion cost error threshold or target, and the former first complexity threshold or target is smaller or equal to the difference between the former first complexity and the first complexity threshold or target. This results in the same difference compared to the complexity threshold or target or a better performance. In another embodiment there is provided a system, an encoder or a controller, or a method for adaptive use of image frame processing resources comprising a central processing or graphics processing unit connected to at least one memory, the central processing or graphics processing unit being configured to receive frames of a video signal, each frame being split into coding units comprising pixels, the central processing or graphics processing unit defining a rate distortion cost error threshold, the difference between the corresponding complexity and a complexity threshold is stored in the memory as a reference for the calculation of an updated rate distortion cost error threshold, wherein the difference between the complexity resulting from the updated rate distortion cost error threshold, and the former complexity threshold is smaller or equal to the difference between the former complexity and the complexity threshold.

The system, encoder or controller provides means or a method step for maximizing the use of an available complexity budget when performing video compression, while controlling the rate distortion cost .

For example, the system, encoder, controller or method can comprise a coding unit at level m with an index m being normalised by instructing the central processing or graphics processing unit to divide it with the number of pixels at the level m. The controller can be adapted to perform the above mentioned normalization.

The normalization has the advantage of making the system, encoder, controller or method independent of coding level.

An advantage of the present invention is that the system, encoder or controller or method keeps within the complexity budget per frame. For example, the system, encoder controller or method can comprise for each frame, the threshold or target of the rate distortion cost error being adapted by the central processing or graphics processing unit, based on the difference between a desired reduced complexity and the complexity target in the previous frame. The controller can be adapted to perform the above mentioned adaptation .

By having a complexity budget per frame, distortions can be smeared out over each frame.

An advantage of the present invention is to be able to calculate in elapsed CPU OR GPU time. For example, the system, encoder, controller or method can provide that the complexity for a frame is expressed in elapsed central processing or graphics processing unit processing time for encoding the whole frame. The controller can be adapted to perform the above mentioned expression.

A practical measure of complexity can be to use the elapsed CPU OR GPU time.

An advantage of the present invention is to be able to assume that the values of a m (see above) are independent of each other. For example, the system, encoder, or method can comprise the central processing or graphics processing unit being instructed to consider the actual number of coding modes per coding unit as being independent of each other. The controller can be adapted to implement the above mentioned independency.

The system, encoder controller or method can be simplified by assuming that the coefficients _m are independent.

An advantage of the present invention is to be able to estimating the I_(m,N) (see above) . For example, the system, encoder, controller or method can provide that the rate distortion cost (comprising all coding modes) is estimated by the central processing or graphics processing unit to be proportional to a linear model of the rate distortion cost comprising less than all coding modes. The controller can be adapted to perform the above mentioned estimation. Since the optimal RD cost I_(m,N) (for all modes N) is not known for I_(m,n) where n<N, it can be estimated, for example to be proportional to I_(m, n) . An advantage of the present invention is to be able to rely on linear dependency. For example, the system, encoder or method can provide that the central processing or graphics processing unit is instructed to consider an estimated rate distortion cost being linearly proportional to the rate distortion cost comprising all coding modes, multiplied by the coefficient 0.87, 0.92, 0.94, 0.95 for the depth 0, 1, 2 and 3 respectively.

The inventors have found that the above mentioned coefficients provide a good estimate.

An advantage of the present invention is to be able to estimate only two groups of modes instead of many modes. For example, the system, encoder, controller or method can comprise that only two groups of modes are evaluated by the central processing or graphics processing unit, the first group comprising the 2Nx2N merge mode and the second mode comprising all other modes. The controller can be adapted to perform the above mentioned evaluation.

The system, encoder, controller or method can be simplified by assuming that there are two groups of coding modes.

In another aspect the present invention provides a controller for adaptive use of image frame processing resources, the controller comprising a central processing unit connected to at least one memory, the central processing unit being configured to receive frames of a video signal, each frame being split into coding units comprising pixels, the central processing unit defining a first rate distortion cost error threshold or target, the difference between the corresponding complexity achieved with the first rate distortion cost error threshold or target and a first complexity threshold is stored in the memory as a reference for the calculation of an updated rate distortion cost error threshold or target, wherein the difference between a second complexity resulting from use of the updated rate distortion cost error threshold, and the former first complexity threshold or target is smaller or equal to the difference between the former first complexity and the first complexity threshold or target.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 shows an embodiment of the present invention comprising a scatter plot of measurements of I _{m n} and I _{m N} .

Figure 2 shows an embodiment of the present invention comprising a Reduced encoding time C _R per frame.

Figure 3 show an embodiment of the present invention comprising a pseudo code of the proposed complexity controller

Figure 4 shows an embodiment of the present invention comprising a Encoding time per frame for (a) the anchor encoder and (b) the complexity constrained encoder and (c)

the average encoding time (ET) , PSNR and bitrate.

Figure 5 shows an embodiment of the present invention comprising RD curves for different complexity thresholds (CT) : (a) Kimono (b) ParkScene, (c) Comparison of encoding time (ET) and BD-rate (BDR) for different complexity thresholds.

Figure 6 shows an embodiment of the present invention for implementing a system.

Figure 7 shows an embodiment of the present invention comprising a flow diagram.

DEFINITIONS

An "image frame" or "video frame" or just "frame" can be an individual image. A sequence of such frames e.g. images shown during certain duration of time, can provide the appearance of motion. A frame can comprise a collection of pixels.

A frame can be divided into "blocks" or "Coding Tree Units" (CTUs) . CTUs can be recursively sub-divided into smaller "Coding Units" (CUs) .

A "Prediction Unit" (PU) can be a collection of pixels for which a prediction can be generated. A "Transform Unit" (TU) can be a collection of pixels for which a transformation can be applied, e.g. cosine, sine, Fourier.

The "Lagrange multiplier" or "Lagrangian" is factor that can be used in a mathematical method to solve optimization problems.

A "Motion Vector" (MV) is a vector that can be used to signal a block or unit in an image frame based on the position of this block or unit (or a similar one) in another image frame, called the reference (image) frame.

A "SKIP" or "merge SKIP" can be used in HEVC resulting in that no residue is transmitted as codec.

"Complexity" can be used as a measure for the amount of occupied resources. A resource refers to a digital processing resource especially a video frame digital processing resource such as provided by a processing engine and memory. Examples of a processing engine are a microprocessor, an FPGA, an ASIC, a graphics card, a GPU or a CPU. For example, the time take for a processing engine such as a CPU or a GPU to execute a process can be used as an indication of the amount of resources used.

A "coding mode" can be a method used to provide the coded version of a group of pixels, e.g. a block or a unit.

"Quantization Parameter", QP, controls the trade-off between bit rate and quality.

A "target" or "target value or range" or a "threshold value" can be defined more generally as a "performance indicator". A target value is a value that ideally is to be reached. Actually achieved results may go above or below a target value. A threshold value sets a limit for a desired performance. Actually achieved results are poor when the threshold is not achieved and are generally good when the threshold value has been achieved. A target value may be defined by upper and lower threshold values i.e. the meaning of target includes a target range, whereby being inside the range, i.e. between the threshold values means that a satisfactory result has been achieved. Providing target values with upper and lower thresholds can reduce the jitter created by dynamic adaption algorithms being activated when the difference between the target value and the achieved value is small. Hence, thresholding and targets or target ranges are related performance indicators and in the description and claims threshold and target are similar, e.g. interchangeable depending on design choice.

DETAILED DESCRIPTION

The present invention will be described with respect to particular embodiments and with reference to certain drawings but the invention is not limited thereto but only by the claims. The drawings described are only schematic and are non-limiting.

Furthermore, the terms first, second, third and the like in the description and in the claims, are used for distinguishing between similar elements and not necessarily for describing a sequential or chronological order. The terms are interchangeable under appropriate circumstances and the embodiments of the invention can operate in other sequences than described or illustrated herein.

The term "comprising", used in the claims, should not be interpreted as being restricted to the means listed thereafter; it does not exclude other elements or steps. It needs to be interpreted as specifying the presence of the stated features, integers, steps or components as referred to, but does not preclude the presence or addition of one or more other features, integers, steps or components, or groups thereof. Thus, the scope of the expression "a device comprising means A and B" should not be limited to devices consisting only of components A and B. It means that with respect to the present invention, the only relevant components of the device are A and B. Similarly, it is to be noticed that the term "coupled", also used in the description or claims, should not be interpreted as being restricted to direct connections only. Thus, the scope of the expression "a device A coupled to a device B" should not be limited to devices or systems wherein an output of device A is directly connected to an input of device B. It means that there exists a path between an output of A and an input of B which may be a path including other devices or means.

Elements or parts of the described devices may comprise logic encoded in media for performing any kind of information processing. Logic may comprise software encoded in a disk or other computer- readable medium and/or instructions encoded in an application specific integrated circuit (ASIC) , field programmable gate array (FPGA) , or other processor or hardware.

In the video compression standard "High Efficiency Video Codec" (HEVC, also referred to as h.265) an image frame can be expressed in a number of "coding tree units", CTUs, where the maximum size of a CTU can be set to a number of pixels, the maximum size of a CTU can be set to 64x64 pixels. A CTU can be recursively split into a quad-tree structure of different "coding units" (CUs) . In a quad ^¬ tree structure, each sub-level can recursively be split into a number of parts such as four parts. The depth of a CU is defined by the number of recursive splits of its CTU that have to be performed in order to reach it. For example, a CU with depth zero (0) is not split and has a maximum size such as 64x64 pixels and a CU with depth three (3) is split three times and has the size such as 8x8 pixels (which is, for example, the minimum size according to the HEVC standard) . To find the optimal encoding mode for a CTU, a cost of different modes such as the Lagrangian cost of different modes can be recursively evaluated and compared.

In video compression, one way of reducing the amount of data to be handled is to use prediction. Motion vectors are used in inter- frame prediction, i.e. between frames of different points in time. A "Motion Vector" (MV) is a vector that can be used to signal (e.g. provide metadata for) a block or unit in an image frame based on the position of this block or unit (or a similar one) in another image frame, called the reference (image) frame. The methods "2Nx2N merge mode" and "Advanced Motion Vector Prediction" (AMVP) can be defined to signal motion vectors (MV) , e.g., to provide metadata on the blocks or units to the decoder

Defining a complexity budget, target or threshold

If a digital process is working on data and additional resources suddenly become available, it could be beneficial if the digital process could access these resources to e.g. to obtain improved quality. For example, in cases where the load on the host computer could change dynamically, and/or the same software is expected to run flexibly on multiple hardware platforms (e.g., cloud instances of different providers) , it could be of advantage if the digital processes have an adaptive behaviour.

In one embodiment of the present invention there can be a complexity budget or target assigned to each digital process. There can be means provided for having a or each process dynamically reconfiguring itself to respect this budget, for example by using as much of the budget as possible, without exceeding it but preferably at the same time not using considerably less of the budget which could result in poorer quality displayed video.

Consider a frame being divided into M CUs so that for each CTU there can be maximum of 1+2 ² +2 ⁴ +2 ⁸ CUs. A particular CU at index or level m, m E {l, ... , ) can be encoded using n different coding modes (or methods), n £ {1, ... , N] . N may be different at different CU depths and/or CU locations. CUs at a larger depth (the larger depth meaning further in the sub-branches) will only be evaluated if the parent of the CU evaluates a need to split further. If this is the case, the CU is added to the list of evaluated CUs, said list having a length Ω. For the n'th mode with distortion D _mn (related to loss of image quality) and rate R _m>n (related to the amount of data needed) , a rate distortion costs such as a Lagrangian "rate distortion cost" ] _mn can be defined as: where λ is the Lagrange multiplier. In general, the rate distortion cost can be defined with other means than the Lagrange multiplier. In a typical encoder, only the coding mode with the lowest rate distortion cost will actually be used for encoding. If I _mn is the optimal RD cost for a CU at index m after evaluating n modes: the computational complexity required for evaluating mode n for a given CU with index m will be denoted C _{m n} . When evaluating all CU configurations and coding modes, the total frame complexity is given by ∑"=i∑n=i ^C m,n■

Defining and simplifying the optimization problem

In one embodiment, the complexity is reduced by not evaluating all encoding modes n per level m . Let cc _m be the actual number of encoding modes evaluated for a CU at index m (c _m £ {1, ... , N}) Note that the value of cc _m can have an influence on the list of evaluated CUs and therefore can change Ω .

Clearly, when only a limited set of encoding modes is evaluated (i.e., with c _m < N ) there is a possible penalty in terms of RD cost. This penalty will be called the RD cost error E _{m cCm} :

The RD cost error can be zero if the optimal encoding mode is found within the first encoding modes, otherwise E _{m am} will be positive. The c _m s can be defined so that rate and distortion are optimized while the reduced complexity / (per frame) does not exceed a particular complexity threshold or target C _T . In other words:

CR —∑m=l∑n=l ^τη,η ( 4 ) min ∑m=i E _m ,a _m subject to: C _R ≤ C _T (5) a ₀ ,...,a _a

Solving this constrained optimization problem is complex, particularly since the RD cost (and therefore also _m,a and E _{m am} ) in general depends on decisions taken in the context of previously coded CUs. If the number of encoding modes to evaluate has been severely restricted for a particular CU, the RD performance for that CU could be relatively low, which increases the RD cost for spatially and temporally neighbouring CUs trying to exploit correlation with this CU.

In one embodiment of the present invention the optimization problem can be simplified with certain assumptions. The first assumption is that the value of _m for a CU can be decided independently from other CUs. In other words, it can be assumed that the c _m s are independent from each other as well as the resulting E _mcCm s . A second assumption is that distributing the RD cost error E _mcCm equally over the CUs results in improved human visual perception. So to cope with different CU depths, the RD cost error can be normalized per level, for example by dividing it with the number of pixels at the specific level. E _T can then denote the cost error threshold or target per pixel and E _mcCm can denote the cost error per pixel. Then Eq. (5) can be reformulated as: min ∑J* ₌₁ \E _T - E _m „ \ subject to:C _R ≤C _T ( 6 ) a ₀ ,...,a _n ^m

Note that the expression in (6) is fully parameterized and can be used for any CU in the frame.

Based on equation (6) a complexity system, encoder, controller or method can be implemented where the targeted error cost or threshold error cost E _T can be varied frame-by-frame, striving to match the complexity target C _T , i.e. to bring C _R as close as possible (or equal to) C _T but without exceeding it.

Exemplary embodiments

Now follows some exemplary embodiments of the present invention. In one embodiment, the number of encoding modes can be assumed to be simplified to two groups (instead of the complete number of N modes) for illustration purposes. However, this should not be construed as a limitation of the invention as such. The two groups used can be respectively the 2Nx2N merge mode and another group containing all other encoding modes. Deciding when to stop encoding

A system, encoder, controller, encoder or method can estimate E _mam to decide whether or not to continue evaluating other modes, where E _mcCm is a normalized version of Eq. (3) . While l _mn is available at mode n, l _mN is not available and therefore needs to be estimated. Figure 1 illustrates the relationship between I _mn and I _m:N for depth or level 0 after a 2Nx2N merge mode. Due to efficient construction of the merge candidate list, there is a high probability that 2Nx2N merge mode is the optimal encoding mode or has low RD cost difference with the optimal mode. So, high correlation is expected. Therefore, in one embodiment, a simple linear model can be used to predict l _mN . The coefficients of the linear model for depth {0, 1, 2, 3} can be respectively {0.87, 0.92, 0.94, 0.95}. A higher coefficient indicates that on average a lower E _mcCm is expected if further evaluation of encoding modes is not done.

Designing the complexity controller

Embodiments of the present invention include a complexity controller which can be implemented as a standalone device, or embedded for example in a system or encoder. The goal of the complexity controller can comprise the respect of the complexity target C _T . Figure 2 shows a relation between C _R and E _T . An anchor (or reference) encoder can be used to extract _m , _a and the encoding is re-run with multiple targets or thresholds E _T . When E _T = 0 (i.e. no RD cost error in the frame) , the complexity is reduced only on the CUs where the 2Nx2N merge mode was the optimal mode. When E _T ≥ 0 different CUs will stop encoding after mode a _m when 7 _m , _a is below the normalized threshold or target. The complexity reaches a minimum when all CUs (at depth 0) only evaluate the 2Nx2N merge mode, whereby further increasing of the threshold or target will not decrease the complexity anymore. With a prediction model, E _T can be empirically defined for a constrained complexity C _T . But, this model or relation is not available for the complexity controller in a real-time implementation. However, C _R and E _T are respectively an increasing and a decreasing monotonic function of _m (see Eq.5) . So, increasing the number of evaluated encoding modes _m will always increase C _R and decrease E _T . Therefore, the complexity controller can use E _T to control the frame complexity C _R , due do the properties of monotonic functions. This is a typical root finding problem. However, there are additional difficulties compared to conventional root finding algorithms. In the present embodiment, while E _T is a constant for a frame, it does change slightly every frame due to various video processing factors such as the changing complexity of the video or inaccurate measurements of the encoding complexity. Therefore, a complexity controller that adapts E _T continuously on a frame-by- frame basis is required.

In a conventional root-finding problem the algorithm finds a point closer to the root at each iteration. In the present embodiment, only a single iteration can be used each frame and the algorithm can fine-tune this value on the next frame.

Therefore, the basic complexity controller here presented can be based on a root finding method such as the root-finding bisection method. This proposed method is explained with pseudo-code in Figure 3. If the root is outside the current interval, a will be doubled if the previous iteration was in the same direction (i.e. a has the same sign) . Doubling allows the method to search faster for the correct interval. When the interval with the root is found, it is divided by -2 so that the direction is changed. This can allow more precise approximation of the correct value while still being able adapt to local changes in the video or noise on the complexity measurement. Alternative root finding methods can be used. There are two types of root finding, namely bracketed and open methods. Both bracketed and open methods can be used with embodiments of the present invention. Different root finding methods will have different performance characteristics, for example bracketed methods will converge but may take time to do so. Open methods may be quicker but do not necessarily always have a guarantee of convergence. Examples of root finding methods included the bisection method, a false position method, the Brent Dekker method, Muller's method, Simple fixed point iteration method, Newton' s method, multidimensional Newton' s method, secant method etc.

Finally, E _T is incremented with the current σ value. As E _T = 0 indicates maximum complexity, it is not useful to accept negative values for E _T . Note that σ and equal_sign can be initialized with any value (e.g. respectively σ ₀ and True ) , this will only have influence on the iterations needed to find the correct E _F value.

Experimental results

The proposed system, encoder or method can be evaluated using sequences from class B described in the common test conditions of HEVC (F. Bossen, "Doc. JCTVC-LllOO: Common test conditions and software reference configurations, " JCTVC, Geneva, Switzerland, Tech. Rep., January 2013), i.e. Kimono, ParkScene, Cactus,

BQTerrace, BasketballDrive . The HM 16.2 reference encoder is used as the anchor or reference. There is focus on low delay settings (i.e. main tier and P slices only), with QP values 22, 27, 32, 37 and open GOP (Group Of Pictures) structure. Figure 4 shows the encoding time per frame for QP=22, for the anchor (Figure 4(a)) and the proposed method (Figure 4 (b) ) . For the anchor, although encoding settings are identical, there is a significant

difference in encoding time (i.e., 42.8%) between Cactus (highest encoding time) and Kimono (lowest encoding time) . The frame with the highest complexity in the BasketballDrive sequence has 14.1% more encoding time compared to the frame with the lowest

complexity. For the proposed method (Figure 4(b)), a complexity target of 40 seconds per frame was defined. As can be observed in the figure, the encoder initializes during the first frames in an attempt to find the RD cost threshold or target using the bisection method or another root finding method. There are two types of root finding, namely bracketed and open methods. Both bracketed and open methods can be used with embodiments of the present invention. Different root finding methods will have different performance characteristics, for example bracketed methods will converge but may take time to do so. Open methods may be quicker but do not necessarily always have a guarantee of convergence. Examples of root finding methods include the bisection method, a false position method, the Brent Dekker method, Muller's method, Simple fixed point iteration method, Newton' s method, multidimensional Newton' s method, secant method etc .

After this initialization phase, the complexity controller adapts the threshold or target frame-by-frame, and manages to keep computational complexity close to the complexity budget, with an average deviation of 0.57 seconds (1.4%) . Reduced complexity comes at a limited cost, e.g., 0.13 dB PSNR loss and 1.6% bitrate loss for a complexity reduction of 48% for the Cactus sequence.

Figure 5 shows RD curves for different complexity targets (CT) , for Kimono (Figure 5 (a) ) and ParkScene (Figure 5 (b) ) . The CT is defined relative to the anchor encoding time at same QP point (anchor encoding time for each QP are provided in the Figure) . For a complexity target of 80%, the BD-rate (BD = Bj0ntegaard Delta Rate) increase ranges from 0:00% (for ParkScene) to 1:72% (for BqTerrace) .

The proposed system, encoder or method for complexity control is compared with a number of fixed complexity methods incorporated in the HM encoder. Using early skip detection (ESD) , an average complexity of 74:8% (relative to the anchor) is measured. When only a maximum CU depth of 2 (MD2) is allowed, an average encoding time of 41:8% of the anchor encoding is measured. At high complexity targets, low BD-rate loss is measured compared to the ESD method. The BD-rate loss at CT = 40% is lower for the BasketBallDrive, Cactus and ParkScene sequences. Embodiments of the present invention provide complexity control, and in general have better RD performance compared to the ESD and MD2 methods. Occasionally, the latter methods show better performance, indicating that there is still room for improvement. Improvements can include, for example, improving the RD cost error prediction and/or allowing more groups of encoding modes instead of only 2Nx2N merge mode. Figure 6 shows an illustration of an embodiment of the present invention. The central processing unit or graphics processing unit 10 can be connected to and communicate with a memory 11, a non ^¬ volatile memory such as a solid state memory or a hard drive 12 and a network 13, e.g. to form a system or encoder or to carry out a method for adaptive use of image frame processing resources. The system or encoder can comprise a central processing or graphics processing unit connected to at least one memory, the central processing or graphics processing unit being configured to receive frames of a video signal, each frame being split into coding units comprising pixels, the central processing or graphics unit defining a first rate distortion cost error threshold or target, the difference between the corresponding first complexity achieved with this rate distortion cost error threshold or target and a first complexity threshold or target is stored in the memory as a reference for the calculation of an updated rate distortion cost error threshold, wherein the difference between a second complexity resulting from use of the updated rate distortion cost error threshold, and the former first complexity threshold or target is smaller or equal to the difference between the former first complexity and the first complexity threshold or target.

A coding unit at level m and with index m can be normalised by instructing the central processing or graphics unit to divide it with the number of pixels at the level m.

For each frame, the threshold or target value or the rate distortion cost error can be adapted by the central processing or graphics processing unit, based on the difference between the reduced complexity and the complexity target in the previous frame. The complexity for a frame can be expressed in elapsed central processing or graphics processing unit processing time for encoding the whole frame. The central processing unit or graphics processing can be instructed to consider the actual number of coding modes for per coding unit as independent of each other.

The rate distortion cost comprising all coding modes can be estimated by the central processing or graphics processing unit to be proportional to a linear model of the rate distortion cost comprising less than all coding modes.

The central processing or graphics processing unit can be instructed to consider an estimated rate distortion cost as being linearly proportional to the rate distortion cost comprising all coding modes, multiplied by the coefficient 0.87, 0.92, 0.94, 0.95 for the depth 0, 1, 2 and 3 respectively. Only two groups of modes need be evaluated by the central processing or graphics processing unit, the first group comprising the 2Nx2N merge mode and the second mode comprising all other modes.

The central processing or graphics processing unit can implement a controller by means of a root-finding method such as the bisection method. Other root finding methods can be used. There are two types of root finding, namely bracketed and open methods. Both bracketed and open methods can be used with embodiments of the present invention. Different root finding methods will have different performance characteristics, for example bracketed methods will converge but may take time to do so. Open methods may be quicker but do not necessarily always have a guarantee of convergence. Examples of root finding methods such as a bisection method include a false position method, the Brent Dekker method, Muller's method, Simple fixed point iteration method, Newton's method, multidimensional Newton's method, secant method etc. Figure 7 shows a flow chart for an embodiment of the present invention. In step 20 the various parameters are being initialized (for example, the complexity CR can be set to 0) and the value can be stored in the memory 11 (alternatively for the memory 11 the hard drive 12 can be used for storage throughout this section) . In step 21 the CPU or GPU 10 can select a coding unit n from a list of all possible coding units stored in the memory 11. In step 21 the CPU or GPU 10 can select a coding mode n from a list of coding modes that can be stored in the memory 11. In step 23 the rate distortion cost I can be calculated. In step 24 the CPU or GPU calculates the normalized rate distortion cost error and compares the result with a targeted normalized rate distortion cost error that can be stored in memory 11. The normalization can be made by dividing the RD cost error of CU n with the number of pixels in the CU n. If the difference between the calculated RD cost error and the referenced RD cost error (for CU m and mode n) is higher than the targeted difference, the CPU or GPU returns to step 22 to select the next coding mode and perform calculations in steps 23 and 24. If the calculated difference is lower or equal to the targeted difference, the coding mode n is selected. The CPU or GPU now returns to step 21 and selects the next CU m. When a coding mode has been chosen for to all CUs, the frame has been encoded and can be transmitted. In practice, the RD cost can be provided by the encoder. A common way to measure the complexity can be to measure the total CPU or GPU time needed to encode the full frame. If this is used, the used complexity can be compared with the budgeted complexity when the whole frame has been encoded. A controller can then be implemented to adjust the targeted RD cost error between frames in order to keep within the complexity budget or to approach it with time. Encoded images can be transmitted to a network for example.

In accordance with an embodiment of the present invention, an encoding engine is provided for encoding images from at least one input source. The encoding engine can be included in the controller for example. The encoding engine can include one or more FPGA, ASIC, or microprocessors, processors, controllers, or the central processing unit (CPU) 10 and/or a Graphics Processing Unit (GPU) , and can be adapted to carry out functions by being programmed with software, i.e. one or more computer programmes.

The encoding engine may have the memory 11 (such as non-transitory computer readable medium, RAM and/or ROM) , an operating system running on a microprocessor, optionally a display such as a fixed format display, data entry devices such as a keyboard, a pointer device such as a "mouse", serial or parallel ports such as I/O ports to communicate with other devices, or network cards and connections to connect to any of the networks or to peripheral devices .

In accordance with another embodiment of the present invention software may be implemented as a computer program product which has been compiled for a processing engine in the encoding engine described above, e.g. for maximizing the use of a complexity budget, wherein expression is parameterized and valid for all coding level. The computer program product may be stored on a non- transitory signal storage medium such as an optical disk (CD-ROM or DVD-ROM) , a digital magnetic tape, a magnetic disk, a solid state memory such as a USB flash memory, a ROM, etc.

The encoding software can be embodied in a computer program product adapted to carry out the following functions when the software is loaded onto the respective device or devices and executed on one or more processing engines such as microprocessors, FPGA, ASIC etc: adaptive use of image frame processing resources for video compression, the image frame processing resources varying dynamically in time, wherein the video signal comprises image frames processed at a video rate, wherein an image frame is expressed in a number of coding units, a coding unit having a predefined maximum size and a controller receiving said image frame, and/or recursively splitting coding units into a quad-tree structure of different coding units having levels and sub-levels, wherein in a quad-tree structure, each level or sub-level is recursively split into parts, a depth of a specific coding unit being defined by the number of recursive splits of coding units that have been used in order to reach the specific coding unit, whereby the size of the specific coding unit is the maximum size divided by the number of recursive splits.

The encoding software can be embodied in a computer program product adapted to carry out the following functions when the software is loaded onto the respective device or devices and executed on one or more processing engines such as microprocessors, etc: wherein a coding unit at a certain depth is encodable with a first number of different coding modes, and determining a rate distortion cost for a second number of coding modes, the second number being less or equal than the first number of different coding modes for the specific coding unit, the determining of the second number being such as to maximise the use of dynamically for the encoder available image frame processing resources, and

the difference between the estimated rate distortion cost for the first and the determined rate distortion cost for the second number of coding modes is the rate distortion cost error, and the difference between the rate distortion cost error and a targeted rate distortion cost error has a minimum value for a certain coding mode, said coding mode is selected to encode the coding unit.

The encoding software can be embodied in a computer program product adapted to carry out the following functions when the software is loaded onto the respective device or devices and executed on one or more processing engines such as microprocessors, FPGA, ASIC etc.

normalizing the collection of pixels of the coding unit at m and with index m, by dividing said coding unit with the of pixels at the level m, and/or for each frame, the central processing or graphics processing unit having the controller adapting the threshold of the rate distortion cost error, based on the difference between the reduced complexity and the value of the complexity target in the previous frame stored in the memory.

The encoding software can be embodied in a computer program product adapted to carry out the following functions when the software is loaded onto the respective device or devices and executed on one or more processing engines such as microprocessors, FPGA, ASIC etc.

calculating the complexity for a frame in elapsed central processing or graphics processing unit processing time for encoding the whole frame.

The encoding software can be embodied in a computer program product adapted to carry out the following functions when the software is loaded onto the respective device or devices and executed on one or more processing engines such as microprocessors, FPGA, ASIC etc.

treating the actual number of coding modes for per coding unit being independent of each other and/or estimating the rate distortion cost comprising all coding modes by assuming said cost is proportional to a linear model of the rate distortion cost comprising less than all coding modes. The encoding software can be embodied in a computer program product adapted to carry out the following functions when the software is loaded onto the respective device or devices and executed on one or more processing engines such as microprocessors, FPGA, ASIC etc.

an estimated rate distortion cost is linearly proportional to the rate distortion cost comprising all coding modes multiplied by the coefficient 0.87, 0.92, 0.94, 0.95 for the depth 0, 1, 2 and 3 respectively and/or evaluating two groups of modes, the first group comprising the 2Nx2N merge mode and the second mode comprising all other modes.

The encoding software can be embodied in a computer program product adapted to carry out the following functions when the software is loaded onto the respective device or devices and executed on one or more processing engines such as microprocessors, FPGA, ASIC etc.

controlling based on a root-finding method such as a bisection method for example by executing the following steps:

σ <- σ ₀

equal_sign - True

function UPDATETHRESHOLD(C ₇ -, C _R )

if o≥ 0) ≠ (C _R > C _T ) then

σ - σ I—2

equal_sign - False

else

if equal_sign then

σ <- 2σ

end if

equal_sign - True

end if

E _T - max(0, E _T + σ)

end function

Other root finding methods can be used. There are two types of root finding methods, namely bracketed and open methods. Both bracketed and open methods can be used with embodiments of the present invention. Different root finding methods will have different performance characteristics, for example bracketed methods will converge but may take time to do so. Open methods may be quicker but do not necessarily always have a guarantee o convergence. Examples of root finding methods such as the bisection method include a false position method, the Brent

Dekker method, Muller's method, Simple fixed point iteration method, Newton' s method, multidimensional Newton' s method, secant method etc.

The encoding software can be embodied in a computer program product adapted to carry out the following functions when the software is loaded onto the respective device or devices and executed on one or more processing engines such as microprocessors FPGA, ASIC etc. encoded images can be transmitted to a network for example.

The software mentioned above can be stored on a non-transitory signal storage medium, such as an optical disk (CD-ROM or DVD- ROM) ; a magnetic tape, a magnetic disk, a ROM, or a solid state memory such as a USB flash memory or similar.