METHODS FOR RDO (RATE-DISTORTION OPTIMIZATION) BASED ON FIT-CURVES AND APPARATUSES USING THE SAME

Abstract

A method for RDO (Rate-Distortion Optimization) based on fit-curves contains at least the following steps: calculating a first fit-curve and a second fit-curve according to information regarding a first frame; carrying information regarding a second frame into the first and second fit-curves to calculate fit distortions and fit bit counts; calculating costs according to the fit distortions and the fit bit counts; determining the best block-division mode for the second frame according to the costs; and dividing the second frame into blocks according to the best block-division mode and encoding the second frame.

Claims

1. A method for RDO (Rate-Distortion Optimization) based on fit-curves, comprising: calculating a first fit-curve and a second fit-curve according to information regarding a first frame; carrying information regarding a second frame into the first and second fit-curves to calculate a plurality of fit distortions and a plurality of fit bit counts; calculating a plurality of costs according to the fit distortions and the fit bit counts; determining the best block-division mode for the second frame according to the costs; and dividing the second frame into blocks according to the best block-division mode and encoding the second frame.

2. The method of claim 1, wherein the first fit-curve and the second fit-curve are third-order functions.

3. The method of claim 1, wherein the step for calculating a first fit-curve and a second fit-curve according to information regarding a first frame further comprises: obtaining a plurality of first distortions between a plurality of original pixel values and a plurality of predicted pixel values of a plurality of PUs (Prediction Units) of the first frame; obtaining a plurality of second distortions between the original pixel values and a plurality of reconstructed pixel values of the PUs of the first frame; calculating the first fit-curve according to the first distortions and the second distortions; obtaining a plurality of first absolute values of syntax of residuals of the PUs of the first frame; obtaining a plurality of bit counts required to encode the first frame; and calculating the second fit-curve according to the first absolute values of syntax of residuals and the bit counts.

4. The method of claim 3, wherein the step for calculating the first fit-curve according to the first distortions and the second distortions further comprises: calculating the first fit-curve using Equations (1) and (2): $\begin{matrix} [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. 1 & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{5} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{5} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{6} \end{matrix}] .Math. [\begin{matrix} a_{1} \\ b_{1} \\ c_{1} \\ d_{1} \end{matrix}] = [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} .Math. y_{i .Math. .Math. 1} \end{matrix}] & (1) \\ y_{1} (x) = a_{1} .Math. x^{3} + b_{1} .Math. x^{2} + c_{1} .Math. x + d_{1} & (2) \end{matrix}$ wherein x.sub.i1 indicates the distortion between the original pixel value and the predicted pixel value of the i-th PU and y.sub.i1 indicates the distortion between the original pixel value and the reconstructed pixel value of the i-th PU, and a.sub.1, b.sub.1, c.sub.1 and d.sub.1 indicates coefficients of the first fit-curve; and calculating the second fit-curve using Equations (3) and (4): $\begin{matrix} [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. 1 & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{5} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{5} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{6} \end{matrix}] .Math. [\begin{matrix} a_{2} \\ b_{2} \\ c_{2} \\ d_{2} \end{matrix}] = [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} .Math. y_{i .Math. .Math. 2} \end{matrix}] & (3) \\ y_{2} (x) = a_{2} .Math. x^{3} + b_{2} .Math. x^{2} + c_{2} .Math. x + d_{2} & (4) \end{matrix}$ wherein x.sub.i2 indicates the first absolute value of syntax of residual of the i-th PU and y.sub.i2 indicates the bit count required to encode the syntax of the i-th PU, and a.sub.2, b.sub.2, c.sub.2 and d.sub.2 indicates coefficients of the second fit-curve.

5. The apparatus of claim 3, wherein the step for carrying information regarding a second frame into the first and second fit-curves to calculate a plurality of fit distortions and a plurality of fit bit counts further comprises: obtaining a plurality of third distortions between a plurality of original pixel values and a plurality of predicted pixel values of a plurality of PUs of the second frame; carrying the third distortions into the first fit-curve to calculate the fit distortions; obtaining a plurality of second absolute values of syntax of residuals of the PUs of the second frame; and carrying the second absolute values of syntax of residuals into the second fit-curve to calculate a plurality of fit bit counts.

6. The method of claim 5, wherein the step for calculating a plurality of costs according to the fit distortions and the fit bit counts further comprises: calculating the costs using Equation (5):
min{J}, J=D+λ.Math.R (5) wherein λ indicates a Lagrange constant, D′ indicates the fit distortions, R′ indicates a total amount of the fit bit counts, and J indicates the costs.

7. An apparatus for RDO (Rate-Distortion Optimization) based on fit-curves, comprising: an intra-frame/inter-frame prediction module; an RD cost calculation module; and a curve-fitting module, wherein the curve-fitting module calculates a first fit-curve and a second fit-curve according to information regarding a first frame; and carries information regarding a second frame into the first and second fit-curves to calculate a plurality of fit distortions and a plurality of fit bit counts, wherein the RD cost calculation module calculates a plurality of costs according to the fit distortions and the fit bit counts, and wherein the intra-frame/inter-frame prediction module determines the best block-division mode for the second frame according to the costs; and divides the second frame into blocks according to the best block-division mode and encodes the second frame.

8. The apparatus of claim 7, wherein the first fit-curve and the second fit-curve are third-order functions.

9. The apparatus of claim 7, further comprising: a distortion calculation module; and an entropy coding module, wherein the curve-fitting module obtains a plurality of first distortions between original pixel values and a plurality of predicted pixel values of a plurality of PUs (Prediction Units) of the first frame from the intra-frame/inter-frame prediction module; obtains a plurality of second distortions between the original pixel values and a plurality of reconstructed pixel values of the PUs of the first frame from the distortion calculation module; calculates the first fit-curve according to the first distortions and the second distortions; obtains a plurality of first absolute values of syntax of residuals of the PUs of the first frame from the intra-frame/inter-frame prediction module; obtains a plurality of bit counts required to encode the first frame from the entropy coding module; and calculates the second fit-curve according to the first absolute values of syntax of residuals and the bit counts.

10. The apparatus of claim 9, wherein the first fit-curve is calculated using Equations (1) and (2): $\begin{matrix} [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. 1 & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{5} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{5} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{6} \end{matrix}] .Math. [\begin{matrix} a_{1} \\ b_{1} \\ c_{1} \\ d_{1} \end{matrix}] = [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} .Math. y_{i .Math. .Math. 1} \end{matrix}] & (1) \\ y_{1} (x) = a_{1} .Math. x^{3} + b_{1} .Math. x^{2} + c_{1} .Math. x + d_{1} & (2) \end{matrix}$ wherein x.sub.i1 indicates the distortion between the original pixel value and the predicted pixel value of the i-th PU and y.sub.i1 indicates the distortion between the original pixel value and the reconstructed pixel value of the i-th PU, and a.sub.1, b.sub.1, c.sub.1 and d.sub.1 indicates coefficients of the first fit-curve; and wherein the second fit-curve is calculated using Equations (3) and (4): $\begin{matrix} [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. 1 & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{5} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{5} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{6} \end{matrix}] .Math. [\begin{matrix} a_{2} \\ b_{2} \\ c_{2} \\ d_{2} \end{matrix}] = [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} .Math. y_{i .Math. .Math. 2} \end{matrix}] & (3) \\ y_{2} (x) = a_{2} .Math. x^{3} + b_{2} .Math. x^{2} + c_{2} .Math. x + d_{2} & (4) \end{matrix}$ wherein x.sub.i2 indicates the first absolute value of syntax of residual of the i-th PU and y.sub.i2 indicates the bit count required to encode the syntax of the i-th PU, and a.sub.2, b.sub.2, c.sub.2 and d.sub.2 indicates coefficients of the second fit-curve.

11. The apparatus of claim 9, wherein the curve fitting module obtains a plurality of third distortions between a plurality of original pixel values and a plurality of predicted pixel values of PUs of the second frame from the intra-frame/inter-frame prediction module; carries the third distortions into the first fit-curve to calculate the fit distortions; obtains a plurality of second absolute values of syntax of residuals of the PUs of the second frame from the intra-frame/inter-frame prediction module; and carries the second absolute values of syntax of residuals into the second fit-curve to calculate fit bit counts.

12. The apparatus of claim 11, wherein the costs is calculated using Equation (5):
min{J}, J=D+λ.Math.R (5) wherein λ indicates a Lagrange constant, D′ indicates the fit distortions, R′ indicates a total amount of the fit bit counts, and J indicates the costs.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0008] The present invention can be fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein:

[0009] FIG. 1 is a flowchart illustrating a method for RDO based on fit-curves according to an embodiment of the invention;

[0010] FIG. 2 is the system block diagram for RDO based on fit-curves according to an embodiment of the invention; and

[0011] FIG. 3 is a flowchart illustrating a method of video encoding according to an embodiment of the invention.

DETAILED DESCRIPTION

[0012] The following description is of the best-contemplated mode of carrying out the invention. This description is made for the purpose of illustrating the general principles of the invention and should not be taken in a limiting sense. The scope of the invention is best determined by reference to the appended claims.

[0013] The present invention will be described with respect to particular embodiments and with reference to certain drawings, but the invention is not limited thereto and is only limited by the claims. Furthermore, it should be understood that the terms “comprises,” “comprising,” “includes” and/or “including,” when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

[0014] Use of ordinal terms such as “first”, “second”, “third”, etc., in the claims to modify a claim element does not by itself connote any priority, precedence, or order of one claim element over another or the temporal order in which acts of a method are performed, but are used merely as labels to distinguish one claim element having a certain name from another element having the same name (but for use of the ordinal term) to distinguish the claim elements.

[0015] Embodiments of the invention introduce a method for RDO (Rate-Distortion Optimization) based on fit-curves. The method needs to perform fit-curves for certain kinds of data. For an example, a curve fitting is performed on absolute values of syntax to be encoded and total amounts of encoded bits for the syntax to obtain a curve describing relationships between the absolute values of syntax and the total amounts of encoded bits for the syntax. In another example, a curve fitting is performed on distortions between the original frame and the predicted frame and distortions between the original frame and the reconstructed frame to obtain a curve describing relationships between these two kinds of distortions. The method does not need to calculate R and D values like the conventional methods in the subsequent RDO. Instead, after obtaining the curves, the method only requires to calculate the absolute values of syntax to be encoded and carry the absolute values into the corresponding fit-curve to obtain the corresponding values R′, and calculate the distortions between the original frame and the predicted frame and carry the distortions to obtain the corresponding values D′. By using the fit-curves to calculate the values R′ and D′, the calculation complexity and the time deferring for encoding may be reduced. FIG. 1 is a flowchart illustrating a method for RDO based on fit-curves according to an embodiment of the invention. The method calculates a first fit-curve and a second fit-curve according to information regarding a first frame (referred to as a reference frame) (step S110), carries information regarding a second frame (referred to as a encoding frame) into the first and second fit-curves to calculate fit distortions and fit bit counts (step S130) and calculate costs according to the fit distortions and the fit bit counts (step S150). Next, the method determines the best block-division mode for the second frame according to the costs (step S170) and divides the second frame into blocks according to the best block-division mode and encodes the second frame (step S190).

[0016] FIG. 2 is the system block diagram for RDO based on fit-curves according to an embodiment of the invention. The curve-fitting module 240 may fit a curve using an algorithm of GLS (Generalized Least Squares). GLS estimates the unknown parameters in a regression model under the minimum error sum of square. GLS can be used to perform regression when there is a certain degree of correlation between the explanatory variables (independent variables) of the regression model. The estimation function may be a third-order function as shown in the Equation (2):

y(x)=a.Math.x.sup.3+b.Math.x.sup.2+c.Math.x+d (2)

[0017] The curve-fitting module 240 may calculate values a, b, c and d using the Equation (3):

[00001] $\begin{matrix} [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. 1 & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{3} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{4} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{5} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{5} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{6} \end{matrix}] .Math. [\begin{matrix} a \\ b \\ c \\ d \end{matrix}] = [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. y_{i} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i} .Math. y_{i} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{2} .Math. y_{i} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i}^{3} .Math. y_{i} \end{matrix}] & (3) \end{matrix}$

Where N indicates a total amount of samplings, [x.sub.i, y.sub.i] indicates values of i-th pair of sampling. After values a, b, c and d are calculated according to information regarding one frame using the Equation (3), the fit-curve of the Equation (2) is generated accordingly. Subsequently, the curve fitting module 240 carries values x of the next frame into the Equation (2) to obtain values y. The curve fitting module 240 fits curves for the parts D and R of the Equation (1) using the Equations (2) and (3).

[0018] Specifically, for the curve fitting of the value D, the curve fitting module 240 may obtain distortions SAD between original pixel values and predicted pixel values of N different PUs (Prediction Units) of the frame from the intra-frame/inter-frame prediction module 210, and obtain distortions D between original pixel values and reconstructed pixel values of the PUs of the frame from the distortion calculation module 230, so as to obtain N pairs of [x.sub.i1, y.sub.i1], where x.sub.i1 indicates the distortion between the original pixel value and the predicted pixel value of the i-th PU and y.sub.i1 indicates the distortion between the original pixel value and the reconstructed pixel value of the i-th PU. Subsequently, the curve fitting module 240 may calculate values a.sub.1, b.sub.1, c.sub.1 and d.sub.1 using the Equation (4):

[00002] $\begin{matrix} [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. 1 & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{5} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{5} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{6} \end{matrix}] .Math. [\begin{matrix} a_{1} \\ b_{1} \\ c_{1} \\ d_{1} \end{matrix}] = [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1} .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{2} .Math. y_{i .Math. .Math. 1} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 1}^{3} .Math. y_{i .Math. .Math. 1} \end{matrix}] & (4) \end{matrix}$

Finally, the curve fitting module 240 obtains the fit-curve calculated according to the distortions SAD and the distortions D by carrying a.sub.1, b.sub.1, c.sub.1 and d.sub.1 into the Equation (5):

y.sub.1(x)=a.sub.1.Math.x.sup.3+b.sub.1.Math.x.sup.2+c.sub.1.Math.x+d.sub.1 (5)

[0019] Specifically, for the curve fitting of the value R, the curve fitting module 240 may obtain absolute values V of syntax of residuals of N different PUs (Prediction Units) of the frame from the intra-frame/inter-frame prediction module 210, and obtain bit counts R required to encode the syntax of the PUs of the frame from the entropy coding module 220, so as to obtain N pairs of [x.sub.i2, y.sub.i2], where x.sub.i2 indicates the absolute value of syntax of residual of the i-th PU and y.sub.i2 indicates the bit count required to encode the syntax of the i-th PU. Subsequently, the curve fitting module 240 may calculate values a.sub.2, b.sub.2, c.sub.2 and d.sub.2 using the Equation (6):

[00003] $\begin{matrix} [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. 1 & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{5} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{4} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{5} & {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{6} \end{matrix}] .Math. [\begin{matrix} a_{2} \\ b_{2} \\ c_{2} \\ d_{2} \end{matrix}] = [\begin{matrix} {.Math.}_{i = 1}^{N} .Math. .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2} .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{2} .Math. y_{i .Math. .Math. 2} \\ {.Math.}_{i = 1}^{N} .Math. .Math. x_{i .Math. .Math. 2}^{3} .Math. y_{i .Math. .Math. 2} \end{matrix}] & (6) \end{matrix}$

Finally, the curve fitting module 240 obtains the fit-curve calculated according to the syntax of residuals V and the bit counts R by carrying a.sub.2, b.sub.2, c.sub.2 and d.sub.2 into the Equation (7):

y.sub.2(x)=a.sub.2.Math.x.sup.3+b.sub.2.Math.x.sup.2+c.sub.2.Math.x+d.sub.2 (7)

[0020] FIG. 3 is a flowchart illustrating a method of video encoding according to an embodiment of the invention. The method is employed in the system as shown in FIG. 2. First, a first frame is encoded (step S310). Next, a loop is repeatedly performed to encode the next frame (step S330) until a VS (Video Sequence) is completed encoded (the “Yes” path of step S350). In step S310, RDO is not performed. When it is determined how to divide blocks, only the distortions SAD between the original frame and the predicted frame are used to perform the determinations, that is, J=SAD. Specifically, the intra-frame/inter-frame prediction module 210 directly employs the distortions SAD between the original frame and the predicted frame to perform block divisions. After the determinations, the intra-frame/inter-frame prediction module 210 may obtain the best block-division mode and record information regarding values SAD, residuals, MVs and reference frame, or others, under the best block-division mode. Subsequently, the T (Transform) 271, the Q (Quantization) 273, the IQ (Inverse Quantization) 275, the IT (Inverse Transform) 277, the entropy coding 220 and the reconstruction 279 are calculated for each block. The entropy coding module 220 records the bit counts R required in the entropy encoding and the bit counts R are output to the curve fitting module 240. In addition, the distortion calculation module 230 calculates the distortions D between the original frame F and the reconstructed frame F′ and the distortions D are output to the curve fitting module 240. After collecting the required values, the curve fitting module 240 obtains the fit-curve y.sub.1(x) for the distortions D and the fit-curve y.sub.2(x) for the required bit counts R using the Equations (4), (5), (6) and (7). In step S330, the fit-curves y(x) are used to perform RDO. Specifically, the intra-frame/inter-frame prediction module 210 calculates values SAD of PUs and outputs the values SAD of PUs to the curve fitting module 240. The curve fitting module 240 carries the values SAD of PUs into the fit-curve y.sub.1(x) of the Equation (5) to obtain the fit distortions D′. The intra-frame/inter-frame prediction module 210 further calculates absolute values of syntax of residuals V of PUs and outputs the absolute values of syntax of residuals V of PUs to the curve fitting module 240. The curve fitting module 240 carries the absolute values of syntax of residuals V of PUs into the fit-curve y.sub.2(x) of the Equation (7) to obtain the fit bit counts R′.sub.r of PUs. All fit bit counts are summed to obtain a total amount of the fit bit counts R′. The RD cost calculation module 250 calculates the fit RD cost J=D′+λ.Math.R′ and outputs the fit RD cost to the intra-frame/inter-frame prediction module 210. Subsequently, the intra-frame/inter-frame prediction module 210 employs the values J to determine the best block-division mode. In the meantime, the frame also needs to undergo the calculations of step S310 to update the fit-curves y.sub.1(x) and y.sub.2(x).

[0021] The curve-fitting module 240 and the RD cost calculation module 250 can be implemented in numerous ways, such as with dedicated hardware, or with general-purpose hardware (e.g., a single processor, multiple processors or graphics processing units capable of parallel computations, or others) that is programmed using microcode or software instructions to perform the functions recited herein. The intra-frame/inter-frame prediction module 210, the entropy coding module 220, the distortion calculation module 230, the T 271, the Q 273, the IQ 275, the IT 277 and the reconstruction 279 can be implemented in numerous ways, such as with dedicated hardware, or with general-purpose hardware that is programmed using microcode or software instructions to perform the functions recited herein.

[0022] As to the block-division determinations, the intra-frame/inter-frame prediction module 210, for example, may determine to divide one 16×16 CU (Coding Unit) into one of four 8×8 PUs, two 8×16 PUs and two 16×8 PUs. Or, the intra-frame/inter-frame prediction module 210 may determine to divide one 8×8 CU into one of four 4×4 PUs, two 4×8 PUs and two 8×4 PUs.

[0023] Although the embodiments have been described in FIG. 2 as having specific elements, it should be noted that additional elements may be included to achieve better performance without departing from the spirit of the invention. While the process flows described in FIG. 1 includes a number of operations that appear to occur in a specific order, it should be apparent that these processes can include more or fewer operations, which can be executed serially or in parallel (e.g., using parallel processors or a multi-threading environment).

[0024] While the invention has been described by way of example and in terms of the preferred embodiments, it should be understood that the invention is not limited to the disclosed embodiments. On the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.

METHODS FOR RDO (RATE-DISTORTION OPTIMIZATION) BASED ON FIT-CURVES AND APPARATUSES USING THE SAME

Inventors

Cpc classification

Classification Explorer

H04N19/147

ELECTRICITY

Classification Explorer

H04N19/176

ELECTRICITY

Classification Explorer

H04N19/567

ELECTRICITY

Classification Explorer

H04N19/172

ELECTRICITY

Classification Explorer

H04N19/119

ELECTRICITY

Classification Explorer

H04N19/593

ELECTRICITY

International classification

Classification Explorer

H04N19/567

ELECTRICITY

Classification Explorer

H04N19/176

ELECTRICITY

Classification Explorer

H04N19/593

ELECTRICITY

Abstract

Claims

Description