JP6737699B2 - Linear prediction coefficient output method, linear prediction coefficient output device, and linear prediction coefficient output program - Google Patents

Description

The present invention relates to a linear prediction coefficient output method, a linear prediction coefficient output device, and a linear prediction coefficient output program.

In order to realize highly efficient video coding, reducing the prediction error of intra prediction is an important issue. In the following, a video is a moving image, that is, a set of a series of images. The image is one frame or a still image forming a moving image. H.264, which is one of the video compression standard. In H.263, a pixel value prediction process using peripheral pixel values is introduced for the purpose of removing the correlation between adjacent pixel values in the same frame. H. At 263, only the prediction for the DC (Direct Current) component is performed. H.264, which is one of the video compression standard. In H.264/AVC, Plane prediction and nine directional predictions are added.

H.264, which is one of the video compression standard. In 265/HEVC (High Efficiency Video Coding), Planar prediction that improves Plane prediction is introduced, and the number of directions of directional prediction is increased to 33 ways. However, H. With the H.265/HEVC, there is room for reducing the prediction error.

The HEVC intra prediction assumes that the direction of the pixel value change is linear. In addition, H. In H.265/HEVC, the number and types of predictors are fixed regardless of the image. Therefore, when the direction of the pixel value change is not linear, the prediction error increases. Moreover, when a specific predictor is not used, the code amount required to express the prediction information increases. Therefore, in order to reduce the prediction error, it is necessary to construct an appropriate predictor for each video.

As a method of determining a predictor for each video, there is a method of determining a plurality of linear predictors for each image (see Non-Patent Document 1). In Non-Patent Document 1, one image is divided into rectangular blocks, and prediction is executed for each rectangular block. Also, in Non-Patent Document 1, each rectangular block is classified into a plurality of types of classes, and an adaptive predictor is determined for each class. Hereinafter, a rectangular block that is a unit of prediction processing is referred to as a “prediction block”.

FIG. 19 is a diagram illustrating an example of a relationship between a reference pixel used for prediction and a predicted pixel in an encoding target frame divided into a plurality of prediction blocks. In FIG. 19, as an example, the image that is the encoding target frame is divided into (5×3), and 16 predicted pixels are predicted from 13 reference pixels. The number and shape of reference pixels and the number of predicted pixels can be freely changed.

FIG. 20 is a diagram showing an example of a method of classifying prediction blocks into a plurality of classes. In FIG. 20, as an example, 15 prediction blocks are classified into 3 classes, and the coefficients required for prediction are prepared for each class. The number of classes may be set in any way as long as it is an integer of 1 or more. The method of deriving the prediction coefficient will be described later.

In Non-Patent Document 1, a single pixel prediction block (prediction target) that is the minimum unit is defined. It is desirable that the prediction error, which is the error between the pixel value in the prediction block and the pixel value in the original image, be kept low. On the other hand, the prediction blocks in the same image have different signal characteristics. Therefore, prediction blocks having similar signal characteristics are grouped into one class, and a predictor with a small prediction error in the grouped classes is designed. Non-Patent Document 1 discloses, as a class classification method, a classification method that uses the variance of neighboring pixel values around a prediction block without using additional information. In Non-Patent Document 1, linear prediction shown in Expression (1) is used for prediction of pixel values in a prediction block.

Here, i is an index indicating the number of the prediction block. c is a class number and can be 1 to C. ^x ⁱ =(^x ⁱ ₁ ,..., ^x ⁱ _l ,..., ^x ⁱ _Mi ) ^T (^ is attached to the character that follows, the same applies below) is the element Is a Mi-dimensional column vector. Mi is the number of reference pixels used for prediction. ^ Y ⁱ _c is a prediction pixel value in a prediction block. In Non-Patent Document 1, since the size of the prediction block is (1×1), ^y ⁱ _c is a one-dimensional real number. _bc is a prediction coefficient in class c and is a Mi-dimensional row vector.

In the method of determining the coefficient that minimizes the prediction error to the prediction coefficient b _c of each class, it is known to solve the linear equations called Wiener-Hopt equation. The matters described above are detailed in Non-Patent Document 1. The linear prediction of Non-Patent Document 1 is expanded, and linear prediction for a normalized pixel value in a prediction block that is not a pixel unit can be described as Expression (2).

Here, i is an index indicating the number of the prediction block. c is a class number and can be 1 to C. ^x ⁱ =(^x ⁱ ₁ ,..., ^x ⁱ _l ,..., ^x ⁱ _Mi ) ^T is a Mi-dimensional column vector whose elements are reference pixels subjected to the normalization process. Mi is the number of reference pixels used for prediction. ^x ⁱ is normalized as in Expression (3).

Here, ￣ x ⁱ = (￣ x ⁱ ₁ ;,..., ￣ x ⁱ _l ,..., ￣ x ⁱ _Mi ) ^T (￣ is attached to the following character. The same applies below) is This is a Mi-dimensional column vector whose elements are reference pixels that have not been normalized. S _c is a set of prediction block numbers that selects the class number c. μ ^x _l is the average value of the l-th reference pixel value −x ⁱ _l belonging to the class c. σ ^x _l is the standard deviation of the l-th reference pixel value belonging to the class c.

^ Y ⁱ _c =(^ y ⁱ _c [1],..., ^ y ⁱ _c [j],..., ^ y ⁱ _c [Mi]) ^T is in the prediction block subjected to the normalization process. Is a Mo-dimensional column vector whose elements are pixel values of. ^ Y ⁱ _c is normalized as in Expression (4).

^{_{Here, ¯y i c = (¯y i}} c [1], ···, ¯y i c [l], ···, ¯y i c [Mo]) T is not subjected to a normalization process This is a Mi-dimensional column vector whose elements are the pixel values in a non-predicted block. μ ⁱ _c [j] is the average value of the l-th predicted pixel value −x ⁱ _l belonging to the class c. Mo is the number of pixels of the prediction block. j is an index indicating the pixel position in the prediction block. A _c is a prediction coefficient in class c, and is a real-valued matrix having Mi in the number of columns and Mo in the number of rows. The pixel value in the j-th prediction block is predicted by the prediction coefficient in the j-th row.

The actual prediction pixel value ~y i ^c unnormalized _^(~ is attached. Similarly above the letter followed) is expressed using equation (5).

In the following, the normalization process is performed on the reference pixel and the prediction block. In the coefficient method used for the linear prediction for each image, the prediction coefficient becomes the additional information. Therefore, in the coefficient method used for the linear prediction for each image, it is a problem to suppress the generated code amount of the prediction coefficient. As a method of suppressing the generated code amount of the prediction coefficient, there is a method of determining the prediction coefficient that can reduce the prediction error under the constraint condition that most of the prediction coefficients are in a sparse state where the value is zero.

When many of the prediction coefficients have a zero value, the code amount required to express the prediction coefficient can be reduced, so that the code amount of the prediction coefficient transmitted as additional information can be reduced. On the other hand, if there are too many zero-valued prediction coefficients, the prediction error will increase, so it is expected that the code amount required to express the prediction error will increase and the image quality of the decoded image will deteriorate.

There is a problem of minimizing the square error of the L0 norm as one of the methods for minimizing the prediction error under the constraint condition that imposes sparsity that most of the prediction coefficients are zero values. The L0 norm squared error minimization problem is expressed using equation (6).

Here, S _c is a set of prediction block numbers for selecting the class number c. In the following text, the twin columns in the formula are represented by "||". ||A _c || ₀ is the number of nonzero-valued coefficients in the matrix A _c . The code amount of the prediction coefficient depends on the number of prediction coefficients that are non-zero values. Therefore, the constraint condition regarding the number of nonzero-valued coefficients has a role of adjusting the code amount required for the prediction coefficient. θ0 represents the upper limit value of the sum of L0 norms in the prediction coefficient. Hereinafter, θ0 is referred to as “L0 norm sum upper limit”.

However, it is difficult to find the optimum solution in Expression (6). Therefore, a method of solving the constraint condition by solving the condition shown in Expression (7) can be considered.

Here, ||Ac||1 is the total sum of the absolute values of the coefficients that are non-zero values in the matrix Ac. θ1 is the upper limit of the sum of absolute value sums of the prediction coefficients Ac in all classes used for linear prediction. Hereinafter, θ1 is referred to as “L1 norm summation upper limit”. By imposing a constraint condition that defines the upper limit of the L1 norm summation, a prediction coefficient having sparsity can be obtained. The L1 norm summation bounds adjust the proportion of zero-valued coefficients in the matrix across all classes.

The prediction coefficient shown in Formula (2) is predicted as each pixel in a prediction block being independent. The j-th pixel value in the prediction block is predicted using the coefficient on the j-th row of the prediction coefficient A _c . That is, when A _c =(a _c [1] ^T ,..., a _c [j] ^T ,..., a _c [Mo] ^T ) ^T is written, a _c [j] becomes a class c. It is a coefficient for predicting the j-th pixel value of the prediction block to which it belongs, and is a Mi-dimensional row vector. Hereinafter, a _c [j] is referred to as a “single pixel prediction coefficient”.

J-th pixel value of the i-th prediction block belonging to the class c, using a single-pixel prediction coefficients _a c [j] and the reference pixel ^{x _i,} is expected to a c [j] ^{x i.} When the number of classes C is one and the number of pixels Mo in the prediction block is one in the optimization problem under the constraint condition by the L1 norm, the optimization problem that determines the prediction coefficient executes linear regression. It is defined as the same problem as LASSO, which is a regularization method of, and various solution methods of optimization problems are known.

Ichiro Matsuda, Hiroshi Mori, Joji Maeda, Shin Ito, Design and evaluation of predictor with minimum rate for lossless coding, IEICE Transactions D-II, Vol. J85, No. 3, pp. 448-456, 2002.

However, the LASSO solution algorithm requires a formulation and constraint conditions in which the number of classes C and the number of pixels Mo are limited to 1. When the number of classes C and the number of pixels Mo are larger than 1, there is a problem that it is not possible to efficiently solve the optimization problem in which the constraint condition is relaxed in the condition shown in Expression (7). .. Since it is not possible to efficiently solve the optimization problem in which the constraint condition is relaxed to the condition shown in Expression (7), the optimization problem of Expression (5) cannot be solved efficiently. Therefore, there is room for improvement in reducing the prediction error (solving the optimum solution) in equation (5).

In view of the above circumstances, the present invention can efficiently solve an optimization problem even under the constraint that the number of classes and the number of pixels in a prediction block are values greater than 1 in intra prediction. It is an object to provide a linear prediction coefficient output method, a linear prediction coefficient output device, and a linear prediction coefficient output program.

One aspect of the present invention is a constraint that a sum of absolute value sums of prediction coefficients, which are coefficients used for linear prediction, satisfies an upper limit value with respect to a prediction error that is a difference between a prediction target digital signal and a predicted digital signal. A linear prediction coefficient output method executed by a linear prediction coefficient output device that outputs a prediction coefficient for linearly predicting the digital signal to be predicted using a linear predictor that minimizes the sum of squares of the prediction error under a condition The single-signal prediction satisfying the constraint condition in a set of single-signal prediction coefficients that are part of the prediction coefficients for linearly predicting the prediction target digital signal and are prediction coefficients of a one-dimensional digital signal Determining a set of coefficients as prediction coefficients for linearly predicting the prediction target digital signal, and the number of non-zero-valued coefficients that can be set as prediction coefficients for linearly predicting the prediction target digital signal Is a linear prediction coefficient output method including a step of determining the upper limit value based on the sum of the above, and a step of outputting the prediction coefficient for linearly predicting the digital signal to be predicted and the upper limit value.

One aspect of the present invention is the above linear prediction coefficient output method, wherein the prediction target digital signal is a prediction coefficient for linearly predicting the prediction target digital signal, and a digital referred to at the time of encoding. It is the matrix product with the signal.

One aspect of the present invention is the above linear prediction coefficient output method, wherein the increase amount of the upper limit value of the absolute value sum of the single signal prediction coefficients and the prediction error in the set of the single signal prediction coefficients satisfying the constraint condition. Change in the L0 norm, which is the number of non-zero-valued coefficients that can be set as the prediction coefficient for linearly predicting the digital signal to be predicted, of the prediction error reduction rate that is the ratio to the reduction amount of the sum of squares of Outputting a list in which each set of the prediction error reduction rate whose amount is 1 and the variation of the L0 norm is listed for each single signal prediction coefficient, and all the listed prediction error reduction rates and the above Outputting an integrated list, which is a list in which a set with a variation of the L0 norm is integrated, and selecting the set from the integrated list in descending order of the prediction error reduction rate, and changing the variation of the L0 norm for each set. Calculating a cumulative sum of minutes to calculate the L0 norm of the entire prediction coefficients for linearly predicting the prediction target digital signal; and a prediction coefficient for linearly predicting the prediction target digital signal. If the L0 norm of the whole is less than or equal to the sum of the number of non-zero-valued coefficients that can be set as prediction coefficients for linearly predicting the digital signal to be predicted, then the prediction error reduction rate of one of the pairs Is defined as the prediction error reduction rate of all prediction coefficients for linearly predicting the prediction target digital signal.

One aspect of the present invention is a sum of absolute value sums of prediction coefficients, which are coefficients used for linear prediction using spatial correlation, with respect to a prediction error that is a difference between a prediction target digital signal and a predicted digital signal. In a linear prediction coefficient output device that outputs a prediction coefficient for linearly predicting the digital signal to be predicted using a linear predictor that minimizes the sum of squares of the prediction errors under the constraint that The single-signal prediction coefficient satisfying the constraint condition in a set of single-signal prediction coefficients that is a part of the prediction coefficients for linearly predicting the digital signal to be predicted and is a prediction coefficient of a one-dimensional digital signal. , A prediction coefficient determination unit that defines a prediction coefficient for linearly predicting the prediction target digital signal, and a non-zero-value coefficient that can be set as a prediction coefficient for linearly predicting the prediction target digital signal Linear prediction coefficient output including an upper limit determination unit that determines the upper limit value based on the sum of the number of, and a prediction coefficient output unit that outputs the prediction coefficient for linearly predicting the digital signal to be predicted and the upper limit value. It is a device.

One aspect of the present invention is a linear prediction coefficient output program for causing a computer to execute the above linear prediction coefficient output method.

According to the present invention, it is possible to efficiently solve an optimization problem even under the constraint that the number of classes and the number of pixels in a prediction block are larger than 1 in intra prediction.

FIG. 6 is a diagram showing input/output of encoding processing and input/output of decoding processing in the embodiment. It is a figure which shows the example of the input-output relationship of the optimization problem of all the prediction coefficients in embodiment. FIG. 6 is a diagram showing a correspondence relationship between a single upper limit and a prediction error reduction rate for two LASSOs in the embodiment. It is a figure which shows the example of the input/output in a LASSO solution calculation part in embodiment. FIG. 6 is a diagram showing an example of outputting a prediction error reduction rate in which the L0 norm of prediction coefficients changes and a variation of the L0 norm for one LASSO solution in the embodiment. It is a figure which shows the example which integrates the prediction error reduction rate and L0 norm change amount which each LASSO solution calculation part calculated in embodiment. FIG. 6 is a diagram showing an example of calculating a minimum prediction error reduction rate that satisfies a constraint condition regarding an L0 norm sum total upper limit in the embodiment. FIG. 6 is a diagram showing an example of calculating a single pixel prediction coefficient for each LASSO solution calculation unit such as LARS in the embodiment. FIG. 3 is a block diagram showing an example of a configuration of a moving image encoding device that executes lossless encoding in the embodiment. FIG. 3 is a block diagram showing an example of a configuration of a moving image decoding device in the embodiment. FIG. 10 is a block diagram showing an example of a detailed configuration of the intra prediction unit shown in FIG. 9 in the embodiment. 12 is a flowchart illustrating an example of a detailed operation of the intra prediction unit illustrated in FIG. 11 in the embodiment. FIG. 11 is a block diagram showing an example of a detailed configuration of the intra prediction unit shown in FIG. 10 in the embodiment. 14 is a flowchart showing an example of detailed operation of the intra prediction unit shown in FIG. 13 in the embodiment. FIG. 12 is a block diagram showing an example of a detailed configuration of an intra prediction coefficient generation unit shown in FIG. 11 in the embodiment. 16 is a flowchart showing an example of detailed operation of the intra prediction coefficient generation unit shown in FIG. 15 in the embodiment. It is a block diagram which shows the example of a detailed structure of the intra prediction part in a prior art. 18 is a flowchart showing an example of detailed operation of the intra prediction unit shown in FIG. 17 in the related art. It is a figure which shows the example of the relationship of the reference pixel and prediction pixel used for prediction in the encoding object frame divided into the some prediction block. It is a figure which shows the example of the method of classifying a prediction block into a some class.

Embodiments of the present invention will be described in detail with reference to the drawings.
First, the principle of outputting a linear prediction coefficient will be described. In order to solve the optimization problem shown in Expression (7), Expression (7) can be rewritten as the design problem of the single pixel prediction coefficient (single signal prediction coefficient) shown in Expression (8).

Here, θ _c [j] is the upper limit value of the sum of absolute values of the coefficients determined for each single pixel prediction coefficient. Hereinafter, θ _c [j] is referred to as “single upper limit”. The optimization problem shown in Expression (8) includes a plurality of LASSOs. In the optimization problem shown in Expression (8), a constraint condition is imposed that the sum of the single upper limits for all classes and pixel values in the prediction block becomes the total upper limit.

FIG. 1 is a diagram showing input/output of an encoding process and input/output of a decoding process in the embodiment. The input/output shown in FIG. 1 is assumed as an example of the input/output in the encoding process and the decoding process using the prediction method using the embodiment of the present invention.

The moving image encoding device (encoder) acquires an original image to be encoded and an L0 norm sum total upper limit for controlling sparsity. The moving image encoding apparatus selects a prediction image output by the prediction method assumed in the embodiment of the present invention from among prediction coefficients that satisfy the constraint condition that the L0 norm of all prediction coefficients is equal to or less than the L0 norm sum upper limit. All prediction coefficients that minimize the sum of squares of the difference from the original image and the L1 norm sum total upper limit θ1 set for equation (7) are output to the moving image decoding device (decoder). Since the moving picture coding apparatus does not share the prediction coefficient between the moving picture coding apparatus and the moving picture decoding apparatus, all the prediction coefficients are compressed and all the compressed prediction coefficients are transferred to the moving picture decoding apparatus. Need to be transmitted. In the decoding process, the moving image decoding apparatus acquires the determined prediction coefficient and the coding parameter other than the prediction coefficient, and outputs the compressed decoded image.

One of the features of the embodiment of the present invention is, as shown in FIG. 1, a parameter that determines the upper limit of the sum of the L0 norms of all prediction coefficients, which means sparseness, instead of the upper limit of the L1 norm sum shown in Expression (7). Is acquired by the moving image decoding apparatus (decoder) as a constraint condition. In video encoding, from the viewpoint of code amount suppression, it may be desirable to derive a solution under the constraint condition of the L0 norm. For example, when most of the prediction coefficients are 0, it is expected that the code amount representing the prediction coefficient can be significantly reduced by introducing a flag indicating whether or not the prediction coefficient is 0. It is considered that the code amount of the prediction coefficient is dominated by the code amount of the non-zero value coefficient. From this, a method of restricting the sum of the L0 norms is conceivable as a method of controlling the code amount of the prediction coefficient.

Therefore, in solving the optimization problem shown in Expression (7), the moving picture coding device (encoder) represents the total sum of the number of nonzero-valued coefficients of all prediction coefficients, that is, the upper limit of the total sum of the L0 norm. Get θ0. It is necessary to consider a method for solving the L1 norm sum total upper limit and the prediction coefficient in the optimization problem shown in Expression (7).

In order to solve the above optimization problem, it is necessary to determine a single upper bound θ _c [j] for all classes and pixel values in the prediction block. When setting c[j] in a plurality of LASSOs, LARS (Least Angle Regression) (see Reference 1) is expanded for the purpose of reducing the amount of calculation.

Reference 1: Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. Least Angle Regression. The Annals of Statistics, Vol. 32, No. 2, pp.407-499, 2004.

LARS can output a single pixel prediction coefficient corresponding to any single upper limit in LASSO by one optimization process. As a result of the above optimization, the single pixel prediction coefficient a _c [j]εR ^Mo corresponding to each θ _c [j] is given as a set of a plurality of connected line segments in the space of R ^Mo. Hereinafter, the above set of line segments is referred to as a "path". Each point on the path is associated with the LASSO solution when θ _c [j]=||a _c [j]|| ₁ is set.

Further, only at the connecting points between the line segments in the path, (1) one coefficient changes from non-zero value to zero value, and (2) one coefficient changes from zero value to non-zero value. Either happens. If been determined path when setting the θ _{c [j],} the computation time for obtaining the theta _c single pixel prediction coefficient when changing a _[j] a _{c [j]} is reduced.

Therefore, the optimization problem shown in Expression (8) is solved by expanding LARS. As a preparation for expanding LARS, the prediction error reduction efficiency e _c [j] is defined for each single pixel prediction coefficient as in Expression (9).

Here, f _c [j] is a function that returns the sum of prediction errors when the acquired single-pixel prediction coefficient a _c [j] is used. a _c [j] is the current single pixel prediction coefficient. d _c [j] is a vector representing the difference when updating the current single pixel prediction coefficient. The prediction error reduction efficiency equation (9) represents the reduction amount of the prediction error with respect to the increase amount of the sum of absolute values of the single pixel prediction coefficients.

In LARS, the coefficient is set so that the prediction error reduction efficiency is always maximized by tracing the path. In the following, the prediction error reduction efficiency is expressed using equation (9) (see Reference 1).

FIG. 2 is a diagram illustrating an example of the input/output relationship of the optimization problem of all prediction coefficients. The overall optimization problem P of prediction coefficients when the L1 norm sum total upper limit shown in Expression (7) is given has an input/output relationship using LARS as shown in FIG. First, as a whole, when the solver of the optimization problem P acquires the L1 norm sum total upper limit, the solver of the optimization problem P determines the total prediction coefficient so that the sum of the L1 norm total of the prediction coefficients is equal to or less than the L1 norm sum upper limit.

Next, the solver (intra prediction unit) of the optimization problem P decomposes the entire prediction coefficient into single pixel prediction coefficients in order to determine each single pixel prediction coefficient, and uses the LASSO solution calculation unit 502 typified by LARS. Determine each single pixel prediction coefficient. The LASSO solution calculation unit 502 acquires a single upper limit representing the upper limit of the L1 norm for the single pixel prediction coefficient. The LASSO solution calculation unit 502 outputs a single pixel prediction coefficient that satisfies the constraint condition regarding the L1 norm and that minimizes the sum of squares of prediction errors. In this case, since the constraint condition regarding the sum of the L1 norms of all the prediction coefficients is satisfied, the sum of the single upper limits is set to be the L1 norm sum total upper limit. At this time, it is not known in the existing optimization method how to determine the single upper limit to minimize the sum of squares of the prediction error of the entire image.

In the following, a method of setting a single upper limit that minimizes the sum of squares of prediction errors will be described. As shown in FIG. 3, the method of setting the single upper limit that minimizes the sum of squares of the prediction error is that the prediction error reduction rate determined for each LASSO is the number of (class number×predicted pixel). This is a single upper limit setting method in the case of equality in LASSO.

FIG. 3 is a diagram showing a correspondence relationship between a single upper limit and a prediction error reduction rate for two LASSOs. Hereinafter, a single upper limit that minimizes the sum of squares of prediction errors is referred to as an “optimal single upper limit”. First, each LASSO solution calculation unit 502 calculates the correspondence between the single upper limit and the prediction error reduction rate in order to determine the optimum single upper limit. The correspondence between the single upper limit and the prediction error reduction rate can be derived using LARS, which is a conventional LASSO solution algorithm.

All the LASSO solution calculation units 502 calculate the correspondence between the single upper limit and the prediction error reduction rate, and then determine each single upper limit so that the prediction error reduction rates are all equal. In this case, the area of the region 1000 shown in FIG. 3 represents the sum of squares of the pixel values of the predicted image. The optimization problem shown in Expression (7) is equivalent to the problem of maximizing the sum total of the areas of the region 1000 for all LASSO solution calculation units 502.

In order to maximize the total area of the regions 1000, the LASSO solution calculation unit 502 needs to reduce the prediction error reduction rate as much as possible so as to comply with the constraint condition regarding the L0 norm total sum upper limit. Further, when determining the single upper limit (area of the region 1100 in FIG. 3) as shown in FIG. 3, each LASSO solution calculation unit 502 determines how the prediction error reduction rate is set so that the constraint upper limit on the L0 norm summation upper limit is set. You need to know if you are satisfied. Hereinafter, a method of deriving the correspondence relationship between the L0 norm sum total upper limit and the prediction error reduction rate in the entire prediction coefficient while satisfying the constraint condition regarding the L0 norm will be described.

FIG. 4 is a diagram showing an example of input/output in the LASSO solution calculation unit 502. First, as shown in FIG. 4, the LASSO solution calculation unit 502 divides the entire prediction coefficient into single-pixel prediction coefficients in order to derive the correspondence between the prediction error reduction rate and the L0 norm sum total upper limit. The LASSO solution calculation unit 502 derives all combinations of the prediction error reduction rate, the single upper limit, and the single-pixel prediction coefficient using a LASSO solution solver such as LARS. Thereby, the LASSO solution calculation unit 502 can output the prediction error reduction rate, the single upper limit, or the single pixel prediction coefficient when the single upper limit or the prediction error reduction rate is acquired.

In the embodiment of the present invention, it is noted that equalizing the prediction error reduction rate is to set an optimum single upper limit. The LASSO solution calculation unit 502 regards the problem of deriving the correspondence relationship between the L0 norm and the L1 norm of all prediction coefficients as the problem of deriving the correspondence relationship between the L0 norm of all prediction coefficients and the prediction error reduction rate. The LASSO solution calculation unit 502 further divides the L0 norm for each single pixel prediction coefficient into subproblems for deriving a correspondence relationship between the prediction error reduction rate. The correspondence relationship between the L0 norm in the single pixel prediction coefficient and the prediction error reduction rate can be searched using an existing algorithm such as LARS. The LASSO solution calculation unit 502 can easily calculate the correspondence relationship between the prediction error reduction rate and the L0 norm of the entire prediction coefficient by introducing an index called the prediction error reduction rate and integrating the partial problems.

FIG. 5 is a diagram showing an example of outputting the prediction error reduction rate in which the L0 norm of the prediction coefficient changes and the variation of the L0 norm for one LASSO solution. As shown in FIG. 5, the solver of the optimization problem P enumerates the prediction error reduction rate and the changing point where the L0 norm in the single pixel prediction coefficient changes for each single pixel prediction coefficient. The solver of the optimization problem P outputs all of the change amount of the L0 norm and the prediction error reduction rate at which the L0 norm changes in a list.

The horizontal axis of the correspondence shown on the left side in FIG. 5 is the prediction error reduction rate. The vertical axis is the L0 norm. The solver of the optimization problem P can efficiently enumerate the change points of the L0 norm of the single pixel prediction coefficient using LARS. The solver of the optimization problem P enumerates and outputs all the change points as a set of the change point of the L0 norm and the prediction error reduction rate when changing. In this case, the solver of the optimization problem P outputs the change point of the L0 norm even if the L0 norm does not change when the prediction error reduction rate becomes 0. The amount of change may increase or may decrease.

FIG. 6 is a diagram showing an example of integrating the prediction error reduction rate and the L0 norm change amount calculated by each LASSO solution calculation unit. As shown in FIG. 6, the solver of the optimization problem P obtains a list in which the change amount of the L0 norm and the prediction error reduction rate at which the L0 norm changes are listed for all single pixel prediction coefficients. The solver of the optimization problem P integrates all the lists in which the amount of change in the L0 norm and the prediction error reduction rate at which the L0 norm changes are listed into one, and rearranges them in descending order of the prediction error reduction rate. The purpose of the operation in FIG. 6 is for the LASSO solution calculation unit 502 to know the correspondence between the L0 norm of the entire prediction coefficient and the prediction error reduction rate.

The solver of the optimization problem P sets the single pixel prediction coefficient so that the overall prediction error reduction rate becomes a constant value E. At this time, among all the combinations of the change amount of the L0 norm and the prediction error reduction rate at which the L0 norm changes, a value obtained by adding all the change amounts of the L0 norm in a set having a prediction error reduction rate of a constant value E or more It is the L0 norm of the entire prediction coefficient. Therefore, the LASSO solution calculation unit 502 can obtain the correspondence relationship between the prediction error reduction rate and the L0 norm of all the prediction coefficients based on the list after integration and sorting (sorting).

Next, a method of setting the minimum prediction error reduction rate under the constraint condition of the L0 norm using the list after integration and rearrangement will be shown.
FIG. 7 is a diagram illustrating an example of calculating the minimum prediction error reduction rate that satisfies the constraint condition regarding the L0 norm sum total upper limit. That is, FIG. 7 shows the correspondence relationship between the L0 norm of all prediction coefficients and the prediction error reduction rate. The horizontal axis shows the prediction error reduction rate. The vertical axis represents the sum of L0 norms of all prediction coefficients.

The solver of the optimization problem P monitors the transition of the sum of the L0 norms when the prediction error reduction rate is changed by reflecting the change amount of the L0 norm in descending order of the prediction error reduction rate. The solver of the optimization problem P selects the prediction error reduction rate that minimizes the prediction error reduction rate under the condition that the L0 norm of all the prediction coefficients is less than or equal to the L0 norm sum total upper limit.

In this case, since the amount of change in the L0 norm may be negative, even if the upper limit of the L0 norm summation is once exceeded, there may be a case where it becomes equal to or lower than the L0 norm summation upper limit again. Therefore, it is necessary to reflect all of the change amount of the L0 norm and the prediction error reduction rate at which the L0 norm changes in the selection of the prediction error reduction rate. The solver of the optimization problem P calculates the selected minimum prediction error reduction rate as the final prediction error reduction rate E _opt set for each single pixel prediction coefficient, as shown in FIG.

FIG. 8 is a diagram illustrating an example of calculating a single pixel prediction coefficient for each LASSO solution calculation unit 502 such as LARS. As shown in FIG. 7, the solver of the optimization problem P sets the calculated prediction error reduction rate E _opt to each single pixel prediction coefficient. Each LASSO solution calculation unit 502 acquires the prediction error reduction rate E _opt as shown in FIG. 8 and outputs the single pixel prediction coefficient with which the prediction error reduction rate is E _opt .

Based on the above basic idea, a moving image coding device and a moving image decoding device to which the linear prediction coefficient output device of the embodiment of the present invention is applied will be described.

First, a moving picture coding device to which the linear prediction coefficient output device of the embodiment is applied will be described.
FIG. 9 is a block diagram showing an example of the configuration of the moving picture coding apparatus 100 that executes lossless coding (reversible coding) in the embodiment. The linear prediction coefficient output device may perform lossy coding (lossy coding).

The moving picture coding apparatus 100 acquires a video signal to be coded and outputs the coded video as a coded stream. Hereinafter, the video signal to be encoded is simply referred to as "video signal".

The moving image coding apparatus 100 includes a frame memory 101, an intra prediction unit 102, an inter prediction unit 103, a prediction residual signal generation unit 104, and an entropy coding processing unit 105. The moving image coding apparatus 100 may further include a storage device having a non-volatile recording medium (non-transitory recording medium) such as a magnetic hard disk device or a semiconductor storage device.

Some or all of the frame memory 101, the intra prediction unit 102, the inter prediction unit 103, the prediction residual signal generation unit 104, and the entropy coding processing unit 105 are, for example, a processor such as a CPU (Central Processing Unit), It may be realized by executing the program stored in the storage unit, or may be realized using hardware such as an LSI (Large Scale Integration) or an ASIC (Application Specific Integrated Circuit).

The frame memory 101 acquires a video signal. The frame memory 101 outputs the video signal to the inter prediction unit 103 as a reference image when the inter prediction unit 103 executes the inter prediction.

The intra prediction unit 102 (prediction coefficient determination unit) (upper limit determination unit) (prediction coefficient output unit) acquires a video signal as a solver of the optimization problem P and optimizes the prediction coefficient for each video signal. The intra prediction unit 102 executes intra prediction using the optimized prediction coefficient, and outputs the predicted video signal to the prediction residual signal generation unit 104.

The intra prediction unit 102 calculates, as a signal of the pixel set of the prediction target, a matrix product of a signal of the pixel set referred to at the time of encoding and a prediction coefficient for linearly predicting the signal of the pixel set of the prediction target. .. The intra prediction unit 102 is a single pixel prediction coefficient (single signal prediction coefficient) that is a part of prediction coefficients for linearly predicting a signal of a pixel set to be predicted and is a prediction coefficient of a single pixel signal (one-dimensional signal). ), a set of single pixel prediction coefficients that satisfy the constraint condition is output as a prediction coefficient for linearly predicting the signal of the pixel set to be predicted. The intra prediction unit 102 outputs to the entropy coding processing unit 105 all the prediction coefficients that need to be compressed and transmitted and the intra prediction information such as the class number defined for each prediction block. The intra prediction unit 102 is a characteristic processing unit in the embodiment of the present invention. Details of the intra prediction unit 102 will be described with reference to FIG. 8 and subsequent figures.

The inter prediction unit 103 acquires the video signal from the frame memory 101 and outputs the predicted video signal derived by the inter prediction to the prediction residual signal generation unit 104. The inter prediction unit 103 outputs to the entropy coding processing unit 105 the inter prediction information that is necessary for inter prediction such as a motion vector and that needs compression and transmission. The prediction residual signal generation unit 104 acquires the video signal and the predicted video signal output by the intra prediction unit 102 or the inter prediction unit 103, and outputs the difference between the video signal and the predicted video signal to the entropy coding processing unit 105. To do. The entropy coding processing unit 105 acquires the inter prediction information and the intra prediction coefficient from the inter prediction unit 103 and the intra prediction unit 102, respectively, and codes based on the prediction residual, the inter prediction information, the intra prediction information, and the intra prediction coefficient. Generates a stream and outputs the generated encoded stream.

Next, a moving image decoding device to which the linear prediction coefficient output device of the embodiment is applied will be described.
FIG. 10 is a block diagram showing an example of the configuration of the moving image decoding apparatus 200 in the embodiment. The moving image decoding apparatus 200 acquires the coded stream output by the entropy coding processing unit 105 illustrated in FIG. 9, and obtains a total of four pieces of information including prediction residual, inter prediction information, intra prediction information, and intra prediction coefficient. Is decoded from the encoded stream and a decoded video signal based on a total of four pieces of information is output. When the moving picture coding apparatus 100 is performing lossless coding (reversible coding), the video signal before coding and the decoded video signal are the same.

The video decoding device 200 includes an entropy decoding processing unit 201, an intra prediction unit 202, an inter prediction unit 203, a decoded signal generation unit 204, and a frame memory 205. The moving image decoding apparatus 200 may further include a storage device having a non-volatile recording medium (non-transitory recording medium) such as a magnetic hard disk device or a semiconductor storage device.

A part of or all of the entropy decoding processing unit 201, the intra prediction unit 202, the inter prediction unit 203, and the decoded signal generation unit 204 is, for example, a processor such as a CPU executing a program stored in a storage unit. It may be realized, or may be realized by using hardware such as LSI and ASIC.

The entropy decoding processing unit 201 acquires the encoded stream output by the entropy encoding processing unit 105 illustrated in FIG. 9, and encodes a total of four pieces of information of prediction residual, inter prediction information, intra prediction information, and intra prediction coefficient. It is decoded from the encoded stream and a total of 4 pieces of information are output. The intra prediction unit 202 acquires the decoded video signal from the frame memory 205, acquires the intra prediction information and the intra prediction coefficient from the entropy decoding processing unit 201, and outputs the prediction image generated by the intra prediction process.

The inter prediction unit 203 acquires the decoded video signal from the frame memory 205, acquires the inter prediction information from the entropy decoding processing unit 201, and outputs the predicted image generated by the inter prediction process. The decoded signal generation unit 204 acquires the prediction image output by the inter prediction unit 203 or the intra prediction unit 202 and the prediction residual output by the entropy decoding processing unit 201, and adds the prediction image and the prediction residual. The generated decoded video signal is output.

The frame memory 205 acquires the decoded video signal output by the decoded signal generation unit 204, and stores the decoded video signal in the storage area of the frame memory 205. The decoded video signal is used as a reference pixel by the inter prediction unit 203 and the intra prediction unit 202.

Next, with reference to FIG. 11, the configuration of the intra prediction unit 102 illustrated in FIG. 9 in the moving picture coding device 100 will be described.
FIG. 11 is a block diagram showing an example of a detailed configuration of the intra prediction unit 102 shown in FIG. The intra prediction unit 102 includes an intra prediction coefficient initialization unit 301, an intra prediction coefficient generation unit 302, an intra prediction coefficient storage unit 303, an intra prediction processing unit 304, and an intra prediction information storage unit 305.

The intra prediction coefficient initialization unit 301 acquires the intra prediction coefficient recorded in the moving image coding apparatus 100, and outputs the intra prediction coefficient storage unit 303. In FIG. 11, the operation of the intra prediction coefficient generation unit 302 is different from the conventional operation. That is, the intra prediction coefficient generation unit 302 includes the video signal to be encoded, the L1 norm sum total upper limit that is a threshold value indicating the upper limit of the L1 norm of the entire prediction coefficient, and the intra prediction information indicating the class information to which each prediction target block belongs. And the prediction coefficient that minimizes the sum of squares of prediction errors is output to the intra prediction coefficient storage unit 303 under the constraint that the sum of the L1 norms of all the prediction coefficients is less than or equal to the L1 norm sum total upper limit.

The intra prediction coefficient storage unit 303 acquires the intra prediction coefficient from the intra prediction coefficient initialization unit 301 and the intra prediction coefficient generation unit 302, and outputs the intra prediction coefficient to the intra prediction processing unit 304 that generates a predicted video signal. The intra prediction coefficient storage unit 303 outputs the intra prediction coefficient to the entropy coding processing unit 105.

The intra prediction processing unit 304 acquires the video signal to be encoded and the prediction coefficient from the intra prediction coefficient storage unit 303, and outputs the generated intra prediction signal to the prediction residual signal generation unit 104. The intra prediction processing unit 304 outputs the class number to which the predicted block belongs to the intra prediction information storage unit 305 as intra prediction information.

The intra prediction information storage unit 305 acquires the intra prediction information selected by the intra prediction processing unit 304, and outputs the intra prediction coefficient to the intra prediction coefficient generation unit 302 to determine the prediction coefficient. The intra prediction information storage unit 305 outputs the intra prediction information to the entropy coding processing unit 105 because it needs to compress and transmit the intra prediction information.

Next, with reference to FIG. 12, the operation of the intra prediction unit 102 shown in FIG. 11 with respect to the moving picture coding device 100 will be described.
FIG. 12 is a flowchart illustrating an example of detailed operation of the intra prediction unit 102 shown in FIG. The intra prediction coefficient initialization unit 301 acquires the intra prediction coefficient recorded in the encoder and records it in the intra prediction coefficient storage unit 303 (step S101).

The intra prediction processing unit 304 executes the processing from step S103 to step S105 for all blocks divided into a rectangular shape. The intra-prediction processing unit 304 determines whether or not the intra-prediction processing has been completed for all the prediction blocks (step S102). When the intra prediction process regarding any of the prediction blocks has not been completed (step S102: NO), the intra prediction processing unit 304 determines which class each prediction target block belongs to and which code amount is minimized. , Determined sequentially. That is, the intra prediction processing unit 304 determines intra prediction information for each prediction block (step S103).

The intra prediction processing unit 304 outputs the predicted video signal using the intra prediction coefficient belonging to the class determined in step S103 (step S104). The intra prediction processing unit 304 records the class number determined in step S103 in the intra prediction information storage unit 305 (step S105). When the intra prediction process regarding all the prediction blocks is completed (step S102: YES), the intra prediction processing unit 304 optimizes the intra prediction coefficient based on the video signal, the intra prediction information, and the single upper limit (step S106). ). The intra prediction processing unit 304 records the intra prediction coefficient in the intra prediction coefficient storage unit 303 (step S107).

Next, with reference to FIG. 13, the configuration of the intra prediction unit 202 illustrated in FIG. 10 regarding the moving image decoding device 200 will be described.
FIG. 13 is a block diagram showing a detailed configuration of the intra prediction unit 202 shown in FIG. The intra prediction unit 202 includes an intra prediction coefficient storage unit 401, an intra prediction information storage unit 402, and an intra prediction processing unit 403. The intra prediction coefficient storage unit 401 acquires the intra prediction coefficient from the entropy decoding processing unit 201, and stores the intra prediction coefficient in the storage area of the intra prediction coefficient storage unit 401.

The intra prediction information storage unit 402 acquires the intra prediction information from the entropy decoding processing unit 201, and stores the intra prediction information in the storage area of the intra prediction information storage unit 402. The intra prediction processing unit 403 acquires the video signal to be encoded, the intra prediction coefficient from the intra prediction coefficient storage unit 401, and the intra prediction information from the intra prediction information storage unit 402, and as a result of executing the intra prediction. Output the predicted video signal.

Next, the operation of the intra prediction unit 202 shown in FIG. 13 will be described with reference to FIG.
FIG. 14 is a flowchart showing an example of detailed operation of the intra prediction unit 202 shown in FIG. The intra prediction coefficient storage unit 401 acquires the intra prediction coefficient from the entropy decoding processing unit 201, and stores the intra prediction coefficient in the storage area of the intra prediction coefficient storage unit 401 (step S201).

The intra-prediction processing unit 403 executes the processing from step S203 to step S204 for all blocks divided into a rectangular shape. The intra-prediction processing unit 403 determines whether or not the intra-prediction processing has been completed for all prediction blocks (step S202). When the intra prediction process regarding any of the prediction blocks is not completed (step S202: NO), the intra prediction processing unit 403 acquires the class number to which each prediction target block belongs from the intra prediction coefficient storage unit 401, Determine the prediction coefficient to use. That is, the intra prediction processing unit 403 acquires intra prediction information for each prediction block (step S203).

The intra prediction processing unit 403 executes the intra prediction process on the prediction block determined in step S203, and outputs a predicted video signal (step S204). When the intra prediction process regarding all the prediction blocks has been completed (step S202: YES), the intra prediction processing unit 403 ends the process.

Next, with reference to FIG. 15, the configuration of the intra prediction coefficient generation unit 302 illustrated in FIG. 11 will be described with respect to the intra prediction unit 102 of the moving image encoding device 100.
FIG. 15 is a block diagram showing an example of a detailed configuration of the intra prediction coefficient generation unit 302 shown in FIG. The intra prediction coefficient generation unit 302 includes an intra prediction information division unit 501, a LASSO solution calculation unit 502, an L0 norm change point extraction unit 503, an L0 norm change point integration unit 504, an end determination unit 505, and an L0 norm update. A unit 506, an L0 norm storage unit 507, a compliance determination unit 508, a prediction error reduction rate update unit 509, a prediction error reduction rate storage unit 510, and an L0 norm change point list update unit 511 are provided.

The intra prediction information division unit 501 acquires the input video signal to be encoded and the intra prediction information that is the class number to which each prediction block belongs, and uses the input video signal as the information necessary for optimizing each single pixel prediction coefficient. And the intra prediction information is divided. The intra prediction information division unit 501 outputs information necessary for optimizing each single pixel prediction coefficient to the LASSO solution calculation unit 502.

The LASSO solution calculation unit 502 acquires the divided input video signal and intra prediction information from the intra prediction information division unit 501, and uses a LASSO solution solver such as LARS to predict the prediction error reduction rate, the single upper limit, and the single pixel prediction. Derive all coefficient sets. The LASSO solution calculation unit 502 outputs all the combinations of the prediction error reduction rate, the single upper limit, and the single pixel prediction coefficient to the L0 norm change point extraction unit 503. The LASSO solution calculation unit 502 acquires the prediction error reduction rate to be aligned as shown in FIG. 3, from the prediction error reduction rate storage unit 510. The LASSO solution calculation unit 502 calculates a single-pixel prediction coefficient for which the prediction error reduction rate is constant in each LASSO solution calculation unit 502, and records it as an intra prediction coefficient in the intra prediction coefficient storage unit 303.

The L0 norm change point extraction unit 503 acquires all the combinations of the prediction error reduction rate, the single upper limit, and the single pixel prediction coefficient from the LASSO solution calculation unit 502. The L0 norm change point extraction unit 503 calculates a set of the value of the prediction error reduction rate at which the L0 norm changes in each single pixel prediction coefficient and the change amount (±1), and collects all the sets as one list. The L0 norm change point extraction unit 503 outputs the list to the L0 norm change point integration unit 504.

The L0 norm change point integration unit 504 acquires as many lists of prediction error reduction rates and L0 norm change amounts as the number of single pixel prediction coefficients to be optimized. The L0 norm change point integration unit 504 integrates all the lists as one list, and outputs the integrated list to the end determination unit 505 (prediction error reduction rate search end determination unit). Hereinafter, the integrated list is referred to as an “integrated list”.

The end determination unit 505 acquires the integrated list from the L0 norm change point integration unit 504 or the L0 norm change point list update unit 511. The end determination unit 505 determines whether or not the integrated list is empty. When the integrated list is not empty and includes an element, the end determination unit 505 outputs the integrated list including the element to the L0 norm updating unit 506. When the integrated list is empty, the end determination unit 505 outputs the iteration end flag to the prediction error reduction rate storage unit 510. The end determination unit 505 outputs the integrated list to the L0 norm change point list update unit 511.

The L0 norm updating unit 506 acquires the integrated list from the end determining unit 505. The L0 norm updating unit 506 selects the set T having the maximum prediction error reduction rate from the acquired integrated list. The L0 norm updating unit 506 acquires the L0 norm of all prediction coefficients from the L0 norm storage unit 507. The L0 norm updating unit 506 adds the amount of change of the L0 norm in the set T having the maximum prediction error reduction rate to the L0 norm of all prediction coefficients. The L0 norm updating unit 506 records the sum of the L0 norm after addition and the integrated list in the L0 norm storage unit 507.

The L0 norm storage unit 507 acquires, from the L0 norm updating unit 506, the result of adding the amount of change in the L0 norm in the set T having the maximum prediction error reduction rate to the L0 norm of all prediction coefficients. The L0 norm storage unit 507 stores the result of adding the change amount of the L0 norm in the set T having the maximum prediction error reduction rate to the L0 norm of all prediction coefficients in the storage area of the L0 norm storage unit 507. The L0 norm storage unit 507 outputs the cumulative sum of the stored L0 norm to the L0 norm updating unit 506 in order to add the variation amount to the stored sum of the L0 norm of all prediction coefficients.

The compliance determination unit 508 (L0 norm constraint compliance determination unit) acquires the integrated list and the cumulative sum of the L0 norm from the L0 norm updating unit 506. The compliance determination unit 508 determines whether the sum of the L0 norms is less than or equal to the L0 norm sum total upper limit. The compliance determination unit 508 outputs the integrated list to the prediction error reduction rate update unit 509 when the sum is less than or equal to the L0 norm sum total upper limit. The compliance determination unit 508 outputs the integrated list to the L0 norm change point list update unit 511 when the value exceeds the L0 norm sum total upper limit or less.

The prediction error reduction rate updating unit 509 extracts the prediction error reduction rate in the set T having the largest prediction error reduction rate in the integrated list from the acquired integrated list. The prediction error reduction rate updating unit 509 records the prediction error reduction rate in the set T having the largest prediction error reduction rate in the integrated list in the prediction error reduction rate storage unit 510. The prediction error reduction rate update unit 509 outputs the integrated list update flag to the L0 norm change point list update unit 511.

The prediction error reduction rate storage unit 510 acquires the updated prediction error reduction rate from the prediction error reduction rate updating unit 509. The prediction error reduction rate storage unit 510 stores the prediction error reduction rate storage unit 510 in the storage area. The prediction error reduction rate storage unit 510 acquires the iteration end flag from the end determination unit 505. The prediction error reduction rate storage unit 510 stores, in the LASSO solution calculation unit 502, the smallest prediction error reduction rate among the prediction error reduction rates that satisfy the constraint condition of the L0 norm sum total upper limit stored in the prediction error reduction rate storage unit 510. Output.

The L0 norm change point list update unit 511 acquires the integrated list from the compliance determination unit 508. The L0 norm change point list update unit 511 deletes the set T having the maximum prediction error reduction rate in the integrated list from the integrated list. The L0 norm change point list updating unit 511 outputs the integrated list in which the set T having the largest prediction error reduction rate in the integrated list is deleted to the end determination unit 505.

Next, the operation of the intra prediction coefficient generation unit 302 during encoding will be described with reference to FIG.
FIG. 16 is a flowchart showing an example of detailed operation of the intra prediction coefficient generation unit 302 shown in FIG. The flowchart shown in FIG. 16 shows details of step S106 shown in FIG.

The intra prediction information division unit 501 divides the input video signal to be encoded and the intra prediction information which is the class number to which each prediction block belongs into information necessary for optimizing each single pixel prediction coefficient (step S301). ). The LASSO solution calculation unit 502 solves the optimization problem for each of the divided single-pixel prediction coefficients using a LASSO solver such as LARS. The LASSO solution calculation unit 502 outputs all the combinations of the prediction error reduction rate, the single upper limit, and the single pixel prediction coefficient to the L0 norm change point extraction unit 503 (step S302).

The L0 norm change point extraction unit 503 calculates all the prediction error reduction rates and the change amounts of the L0 norm using all of the obtained combinations of the prediction error reduction rate, the single upper limit, and the single pixel prediction coefficient, and the list Summarize as. The L0 norm change point extraction unit 503 outputs the calculated list to the L0 norm change point integration unit 504 for each LASSO solver (step S303).

The L0 norm change point integration unit 504 integrates all the lists calculated for each LASSO solver to create an integrated list (step S304). The L0 norm change point integration unit 504 rearranges the integrated list of pairs of the prediction error reduction rate and the variation of the L0 norm in descending order of the prediction error reduction rate (step S305). The prediction error reduction rate updating unit 509 satisfies the constraint condition of the L0 norm sum total upper limit and initializes the prediction error reduction rate storage unit 510 for recording the minimum prediction error reduction rate. The L0 norm updating unit 506 initializes the L0 norm storage unit 507 for recording the sum of all prediction coefficient L0 norms (step S306).

The end determination unit 505 repeats steps S308 to S312 until the integrated list becomes empty. That is, the end determination unit 505 determines whether or not the integrated list is empty (step S307). When the integrated list is empty (step S307: YES), the end determination unit 505 advances the process to step S313. When the integrated list is not empty and includes an element (step S307: NO), the L0 norm updating unit 506 selects the set T having the maximum prediction error reduction rate from the acquired integrated list (step S307). S308).

The L0 norm updating unit 506 acquires the L0 norm of all prediction coefficients from the L0 norm storage unit 507. The L0 norm updating unit 506 adds the change amount (variation) of the L0 norm in the set T having the maximum prediction error reduction rate to the L0 norm of all prediction coefficients (step S309). The compliance determination unit 508 determines whether or not the sum of the L0 norms stored in the L0 norm storage unit 507 is less than or equal to the L0 norm sum total upper limit (step S310).

If the sum of the L0 norms exceeds the L0 norm sum upper limit (step S310: NO), the compliance determination unit 508 advances the process to step S312. When the sum of the L0 norms is less than or equal to the L0 norm sum upper limit (step S310: YES), the prediction error reduction rate updating unit 509 sets the prediction error reduction rate in the set T having the maximum prediction error reduction rate in the integrated list as It records in the prediction error reduction rate storage unit 510 (step S311). The prediction error reduction rate updating unit 509 deletes the set T having the largest prediction error reduction rate in the integrated list from the integrated list (step S312). LASSO solution calculating section 502 obtains the prediction error reduction rate _{E opt,} to derive a single pixel prediction coefficient prediction error reduction rate is _{E opt} (step S313).

In the embodiment of the present invention, the intra-prediction unit 102 has the intra-prediction coefficient generation unit 302, which is a characteristic that the prior art does not have. For comparison between the intra prediction unit 102 and the intra prediction unit 102a, a detailed configuration and operation of the intra prediction unit 102a in the related art will be shown.

Next, for comparison, FIG. 17 shows a detailed configuration of the intra prediction unit 102a of the moving image encoding device in the related art.
FIG. 17 is a block diagram showing an example of a detailed configuration of the intra prediction unit 102a in the conventional technique. The intra prediction unit 102a includes an intra prediction processing unit 601, an intra prediction information storage unit 602, an intra prediction information selection unit 603, and an intra prediction coefficient storage unit 604.

The intra prediction processing unit 601 acquires the prediction coefficient from the intra prediction coefficient storage unit 604, acquires the video signal to be encoded, and outputs the predicted video signal by executing intra prediction. Further, the intra prediction processing unit 601 selects the class number to which each prediction block belongs, and outputs it to the intra prediction information storage unit 602.

The intra prediction information storage unit 602 acquires the intra prediction information output from the intra prediction processing unit 601. The intra prediction information storage unit 602 outputs the intra prediction information that needs to be compressed and transmitted to the entropy coding processing unit 105. The intra prediction information selection unit 603 selects intra prediction information from the intra prediction information stored in the intra prediction information storage unit 602. The intra prediction coefficient storage unit 604 outputs the intra prediction coefficient stored in the storage area of the intra prediction coefficient storage unit 604 to the intra prediction processing unit 601.

Next, FIG. 18 illustrates a processing operation of the intra prediction unit 102a illustrated in FIG. 17 regarding the moving image encoding device according to the related art.
FIG. 18 is a flowchart showing an example of detailed operation of the intra prediction unit 102a shown in FIG. 17 in the conventional technique. The intra prediction processing unit 601 acquires the intra prediction coefficient stored in the storage area of the intra prediction coefficient storage unit 604 (step S401). The intra prediction processing unit 601 repeats the processing from step S403 to step S405 until the processing for all the prediction blocks is completed. The intra-prediction processing unit 601 determines whether or not the intra-prediction processing has been completed for all prediction blocks (step S402).

When the intra prediction process regarding any prediction block is not completed (step S402: NO), the intra prediction processing unit 601 sets the intra prediction information, which is the class number to which each prediction block belongs, so that the code amount becomes the minimum. It is determined (step S403). The intra-prediction processing unit 601 executes intra-prediction using the intra-prediction coefficient belonging to the determined class number, and outputs a predicted video signal. That is, the intra prediction processing unit 601 executes intra prediction processing for each prediction block (step S404).

The intra prediction processing unit 601 records the intra prediction information in the intra prediction information storage unit 602 in order to compress and transmit the intra prediction information determined in step S403 (step S405). When the intra prediction process regarding all the prediction blocks is not completed (step S402: YES), the intra prediction processing unit 601 ends the process.

As described above, the linear prediction coefficient output device according to the embodiment is a coefficient used for linear prediction that utilizes spatial correlation for a prediction error that is a difference between a prediction target digital signal and a predicted digital signal. Output the prediction coefficient for linearly predicting the digital signal to be predicted using a linear predictor that minimizes the sum of squared prediction errors under the constraint that the sum of the absolute sums of prediction coefficients satisfies the upper limit .. The intra prediction unit 102 serves as a prediction coefficient determination unit, which is a part of the prediction coefficients for linearly predicting the digital signal to be predicted and is a constraint condition in the set of single-signal prediction coefficients that is a prediction coefficient of a one-dimensional digital signal. A set of single signal prediction coefficients that satisfy the above is defined as prediction coefficients for linearly predicting a digital signal to be predicted. The intra prediction unit 102 determines, as an upper limit determination unit, an upper limit value based on the sum of the number of non-zero-valued coefficients that can be set as prediction coefficients for linearly predicting a digital signal to be predicted. The intra prediction unit 102 outputs, as a prediction coefficient output unit, a prediction coefficient for linearly predicting a digital signal to be predicted and an upper limit value.

As a result, the linear prediction coefficient output device according to the embodiment is constrained to the condition shown in Expression (5) even under the constraint condition that the number of classes and the number of pixels in a prediction block are values greater than 1 in intra prediction. It is possible to efficiently solve an optimization problem with relaxed conditions. The linear prediction coefficient output device of the embodiment can efficiently perform an intra-prediction suitable for a signal characteristic by efficiently solving an optimization problem in which the constraint condition is relaxed in the condition shown in Expression (5). ..

Further, in the conventional solution of the optimization problem, since intuitive sparseness control is given, there is a problem that it is difficult to set the constraint upper limit of the L0 norm of all prediction coefficients. While the constraint by the L1 norm sum total upper limit is a parameter required to give sparseness, it is difficult to give an intuitively correct L1 norm sum total upper limit from the viewpoint of controlling the code amount. To solve this problem, the linear prediction coefficient output device of the embodiment allows the user to directly specify the upper limit of the L0 norm for the sparsity control of the optimization problem in which the constraint condition is relaxed in the condition shown in Expression (5). The sparsity can be controlled more easily.

Further, the linear prediction coefficient output device according to the embodiment can efficiently output a prediction coefficient having sparseness (non-zero-valued coefficients exist sparsely) for performing linear prediction on a digital signal. It is possible. In the embodiment, the digital signal is a signal of a pixel set in the case of video coding. A single signal (one-dimensional signal) is a single pixel signal in the case of video coding. In the case of video coding, dividing a digital signal means dividing into blocks.

The L0 norm change point extraction unit 503 of the embodiment uses the ratio between the increase amount of the upper limit value of the absolute value sum of the single signal prediction coefficients and the decrease amount of the sum of squares of the prediction errors in the set of single signal prediction coefficients that satisfy the constraint condition. Of the certain prediction error reduction rates, the prediction error reduction rate and L0 having a change amount of 1 of the L0 norm, which is the number of non-zero-valued coefficients that can be set as the prediction coefficient for linearly predicting the digital signal to be predicted, and L0 A list listing the norm variation and the set is output for each single signal prediction coefficient. The L0 norm change point integration unit 504 of the embodiment outputs an integrated list that is a list in which all the sets of the prediction error reduction rates listed and the variation of the L0 norm are integrated. The prediction error reduction rate updating unit 509 of the embodiment selects a group from the integrated list in the descending order of the prediction error reduction rate and calculates the cumulative sum of the variation of the L0 norm for each group to determine the prediction target digital signal. The entire L0 norm of prediction coefficients for linear prediction is calculated. In the prediction error reduction rate update unit 509 of the embodiment, the entire L0 norm of the prediction coefficients for linearly predicting the digital signal to be predicted can be set as the prediction coefficient for linearly predicting the digital signal to be predicted. If it is less than or equal to the total number of zero-valued coefficients, one prediction error reduction rate of the set is defined as the overall prediction error reduction rate of the prediction coefficients for linearly predicting the digital signal to be predicted.

It should be noted that reducing the non-zero coefficient in the embodiment of the present invention is only one of the means, and is not limited to such a predictor. The linear prediction coefficient output device according to the embodiment of the present invention can be applied to various fields such as encoding of other media such as voice, management system of man-hours and operation. At this time, the condition that the number of non-zero coefficients is reduced may be set according to the field to which it is applied.

You may make it implement|achieve at least one part of the linear prediction coefficient output device in the above-mentioned embodiment with a computer. In that case, the program for realizing this function may be recorded in a computer-readable recording medium, and the program recorded in this recording medium may be read by a computer system and executed. The “computer system” mentioned here includes an OS and hardware such as peripheral devices. The "computer-readable recording medium" refers to a portable medium such as a flexible disk, a magneto-optical disk, a ROM, a CD-ROM, or a storage device such as a hard disk built in a computer system. Further, the "computer-readable recording medium" means to hold a program dynamically for a short time like a communication line when transmitting the program through a network such as the Internet or a communication line such as a telephone line. In this case, a volatile memory inside a computer system that serves as a server or a client in that case may hold a program for a certain period of time. Further, the program may be for realizing some of the functions described above, or may be one that can realize the functions described above in combination with a program already recorded in a computer system, It may be realized using a programmable logic device such as FPGA (Field Programmable Gate Array).

Although the embodiment of the present invention has been described in detail above with reference to the drawings, the specific configuration is not limited to this embodiment, and includes a design and the like within a range not departing from the gist of the present invention.

The present invention efficiently solves an optimization problem even under the constraint that the number of classes and the number of pixels in a prediction block are larger than 1 in intra prediction, and thus intra prediction adapted to signal characteristics is performed. It can be applied to applications in which it is essential.

100... Moving picture coding device, 101... Frame memory, 102... Intra prediction unit, 102a... Intra prediction unit, 103... Inter prediction unit, 104... Prediction residual signal generation unit, 105... Entropy coding processing unit, 200... Moving picture decoding device, 201... Entropy decoding processing unit, 202... Intra prediction unit, 203... Inter prediction unit, 204... Decoded signal generation unit, 205... Frame memory, 301... Intra prediction coefficient initialization unit, 302... Intra prediction coefficient Generation unit, 303... Intra prediction coefficient storage unit, 304... Intra prediction processing unit, 305... Intra prediction information storage unit, 401... Intra prediction coefficient storage unit, 402... Intra prediction information storage unit, 403... Intra prediction processing unit, 501 Intra prediction information division unit, 502... LASSO solution calculation unit, 503... L0 norm change point extraction unit, 504... L0 norm change point integration unit, 505... End determination unit, 506... L0 norm update unit, 507... L0 norm storage 508... Compliance determination unit, 509... Prediction error reduction rate update unit, 510... Prediction error reduction rate storage unit, 511... L0 norm change point list update unit, 601,... Intra prediction processing unit, 602... Intra prediction information storage unit , 603... Intra prediction information selection unit, 604... Intra prediction coefficient storage unit, 1000... Region, 1100... Region

Claims (4)

Regarding the prediction error that is the difference between the prediction target digital signal and the predicted digital signal, the prediction error is under the constraint that the sum of the absolute value sums of the prediction coefficients that are coefficients used for linear prediction satisfies the upper limit value. A linear prediction coefficient output method executed by a linear prediction coefficient output device that outputs a prediction coefficient for linearly predicting the digital signal to be predicted using a linear predictor that minimizes the sum of squares of
A set of single-signal prediction coefficients satisfying the constraint condition among a set of single-signal prediction coefficients that are a part of prediction coefficients for linearly predicting the digital signal to be predicted and are prediction coefficients of a one-dimensional digital signal. Determining a prediction coefficient for linearly predicting the digital signal to be predicted,
Determining the upper limit value based on the total number of non-zero-valued coefficients that can be set as prediction coefficients for linearly predicting the digital signal to be predicted,
Outputting a prediction coefficient and the upper limit value for linearly predicting the digital signal to be predicted ,
Of the prediction error reduction rate that is the ratio of the increase amount of the upper limit value of the absolute value sum of the single signal prediction coefficients in the set of the single signal prediction coefficients satisfying the constraint conditions and the decrease amount of the square sum of the prediction error, The prediction error reduction rate and the variation of the L0 norm in which the amount of change in the L0 norm, which is the number of non-zero-valued coefficients that can be set as the prediction coefficient for linearly predicting the digital signal to be predicted, is 1 Outputting a list in which each set of
Outputting an integrated list that is an integrated list of all the sets of the prediction error reduction rates and the variation of the L0 norm listed;
Prediction for linearly predicting the prediction target digital signal by selecting the group from the integrated list in the descending order of the prediction error reduction rate and calculating the cumulative sum of the variation of the L0 norm for each group. Calculating the L0 norm of all of the coefficients,
The total L0 norm of the prediction coefficients for linearly predicting the prediction target digital signal is equal to or less than the total number of non-zero-valued coefficients that can be set as prediction coefficients for linearly predicting the prediction target digital signal. In the above case, the prediction error reduction rate of one of the sets is determined as the prediction error reduction rate of all prediction coefficients for linearly predicting the digital signal to be predicted . The predicted digital signal, the digital signal of the prediction target is a matrix product of a digital signal which is referred in the prediction coefficients and coding for linear prediction, linear prediction coefficients output according to claim 1 Method. Regarding the prediction error, which is the difference between the digital signal to be predicted and the predicted digital signal, the constraint that the sum of the absolute value sums of the prediction coefficients, which are the coefficients used for linear prediction using spatial correlation, satisfies the upper limit value. A linear prediction coefficient output device that outputs a prediction coefficient for linearly predicting the digital signal of the prediction target using a linear predictor that minimizes the sum of squares of the prediction error under a condition,
A set of single-signal prediction coefficients satisfying the constraint condition among a set of single-signal prediction coefficients that are a part of prediction coefficients for linearly predicting the digital signal to be predicted and are prediction coefficients of a one-dimensional digital signal. A prediction coefficient determination unit that defines a prediction coefficient for linearly predicting the digital signal to be predicted,
An upper limit determination unit that determines the upper limit value based on the total number of non-zero-valued coefficients that can be set as prediction coefficients for linearly predicting the digital signal to be predicted,
A prediction coefficient output unit that outputs a prediction coefficient for linearly predicting the digital signal to be predicted and the upper limit value ,
Of the prediction error reduction rate that is the ratio of the increase amount of the upper limit value of the absolute value sum of the single signal prediction coefficients in the set of the single signal prediction coefficients satisfying the constraint conditions and the decrease amount of the square sum of the prediction error, The prediction error reduction rate and the variation of the L0 norm in which the amount of change in the L0 norm, which is the number of non-zero-valued coefficients that can be set as the prediction coefficient for linearly predicting the digital signal to be predicted, is 1 An L0 norm change point extraction unit that outputs a list in which each set is listed for each single signal prediction coefficient,
An L0 norm change point consolidator that outputs an integrated list that is a list in which all combinations of the listed prediction error reduction rates and the variations of the L0 norm are integrated;
Prediction for linearly predicting the prediction target digital signal by selecting the group from the integrated list in the descending order of the prediction error reduction rate and calculating the cumulative sum of the variation of the L0 norm for each group. A prediction error reduction rate updating unit that calculates the L0 norm of all coefficients,
The total L0 norm of the prediction coefficients for linearly predicting the prediction target digital signal is equal to or less than the total number of non-zero-valued coefficients that can be set as prediction coefficients for linearly predicting the prediction target digital signal. And a prediction error reduction rate updating unit that defines the prediction error reduction rate of one of the sets as the prediction error reduction rate of the entire prediction coefficient for linearly predicting the digital signal to be predicted. Prediction coefficient output device. A linear prediction coefficient output program for causing a computer to execute the linear prediction coefficient output method according to claim 1 or 2 .

Images