JP6737700B2 - 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. 17 is a diagram illustrating an example of the relationship between the reference pixel and the predicted pixel used for prediction in the encoding target frame divided into a plurality of prediction blocks. In FIG. 17, 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. 18 is a diagram showing an example of a method of classifying prediction blocks into a plurality of classes. In FIG. 18, 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), there is room for improvement in reducing the prediction error in Expression (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 A linear prediction coefficient output method including a step of outputting a set of coefficients as prediction coefficients for linearly predicting the digital signal to be predicted.

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 in the step, the linear prediction coefficient output device has a sum of absolute value sums of the single signal prediction coefficients that is equal to or less than the upper limit value, and If the difference between the sum and the upper limit value is less than a predetermined minute amount, the set of single-signal prediction coefficients satisfying the constraint condition is output as a prediction coefficient for linearly predicting the digital signal to be predicted. To do.

One aspect of the present invention is the linear prediction coefficient output method described above, wherein in the step, the linear prediction coefficient output device, when the sum exceeds the upper limit, or the sum and the upper limit. If the difference between and is a small amount or more, a prediction coefficient for linearly predicting the prediction target digital signal is calculated based on the updated reduction rate of the prediction error.

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. Is a linear prediction coefficient output device including a prediction coefficient output unit that outputs the set of as a prediction coefficient for linearly predicting the digital signal to be predicted.

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 structure and input of an optimization problem 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 input/output related to all LASSO solution calculation units having all correspondences of each LASSO calculated by LARS or the like when executing a binary search 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. 8 is a block diagram showing an example of a detailed configuration of an intra prediction unit shown in FIG. 7 in the embodiment. 10 is a flowchart illustrating an example of a detailed operation of the intra prediction unit illustrated in FIG. 9 in the embodiment. FIG. 9 is a block diagram showing an example of a detailed configuration of the intra prediction unit shown in FIG. 8 in the embodiment. 12 is a flowchart showing an example of detailed operation of the intra prediction unit shown in FIG. 11 in the embodiment. FIG. 10 is a block diagram showing an example of a detailed configuration of an intra prediction coefficient generation unit shown in FIG. 9 in the embodiment. 10 is a flowchart showing an example of detailed operation of the intra prediction coefficient generation unit shown in FIG. 9 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. 16 is a flowchart showing an example of a detailed operation of the intra prediction unit shown in FIG. 15 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 L1 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 L1 norm of all prediction coefficients is equal to or less than the L1 norm sum upper limit. All the prediction coefficients that minimize the sum of squares of the differences from the original image are output to the moving image decoding device (decoder). Since the moving picture coding apparatus does not share prediction coefficients between the moving picture coding apparatus and the moving picture decoding apparatus, it is necessary to transmit all the prediction coefficients to the moving picture decoding apparatus. 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.

FIG. 2 is a diagram showing the structure and input of the optimization problem expressed by the equation (8). The optimization problem represented by Expression (8) is represented as “P”. The solver of the optimization problem P acquires the upper limit value (single upper limit) of the sum of L1 norms over all prediction coefficients. The solver of the optimization problem P is a prediction that is a difference between a video signal and a prediction video signal from all prediction coefficients that satisfy the constraint condition that the sum of L1 norms of all prediction coefficients is equal to or less than the L1 norm sum total upper limit. All prediction coefficients that minimize the sum of squared errors are output based on equation (8).

In order to solve the optimization problem P, it is necessary to solve a plurality of LASSOs. Each LASSO solution calculation unit 502 that solves LASSO acquires a single upper limit that can be set by the single pixel prediction coefficient to be optimized by each LASSO solution calculation unit 502. Each LASSO solution calculation unit 502 is a video signal (prediction target) for which each single-pixel prediction coefficient should be predicted from among the single-pixel prediction coefficients that satisfy the constraint condition that the L1 norm of the single-pixel prediction coefficient is equal to or less than the single upper limit In, a single pixel prediction coefficient that minimizes the sum of squares of the difference between the video signal and the predicted video signal is output.

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. 3 is a diagram showing a correspondence relationship between a single upper limit and a prediction error reduction rate for two LASSOs. As shown in FIG. 3, the correspondence relationship between all the single upper limits and the prediction error reduction rate is determined for each LASSO. If the LASSO to be solved differs, the correspondence between the single upper limit and the prediction error reduction rate differs, so in FIG. 3, the correspondence between the single upper limit and the prediction error reduction rate differs for each LASSO. Further, the area of the region 1000 represents the amount of prediction error that can be reduced as compared with the state in which no prediction is performed. That is, the area of the region 1000 represents the amount of prediction error that can be reduced compared to the state where the prediction signal value is 0. As the area of the region 1000 increases, a prediction signal with a smaller prediction error can be generated. Therefore, the equation (8) solves the problem of maximizing the area of the region 1100 in FIG.

FIG. 4 is a diagram showing an example of input/output in the LASSO solution calculation unit 502. Since LARS has all correspondences regarding the three elements of the prediction error reduction rate, the single pixel prediction coefficient, and the single upper limit, the LASSO solution calculation unit 502 that calculates all the LASSO solutions represented by LARS, Since all the correspondence relations of the prediction error reduction rate, the prediction coefficient, and the single upper limit are held, any of the above three elements can be an input and an output. When knowing the correspondence between the prediction error reduction rate and the single upper limit as shown in FIG. 3, the input/output shown in FIG. 4 can be given.

Further, FIG. 3 is also a diagram showing an example of an optimal setting method of the single upper limit θc[j] that needs to be acquired in each LASSO solution. When the optimal solution is obtained in the optimization problem P, the property that the prediction error reduction rates corresponding to the single upper limits are equal holds in all LASSOs, as shown in FIG. However, the prediction error reduction rates do not have to be set equally for LASSOs in which the single upper limit value is set to 0. This means that it is not necessary to allocate the L1 norm to LASSO having a low prediction error reduction rate.

The L1 norm upper limits θ _c,j1 , θ _c,j2 may be set so that the prediction error reduction rates in the two single-pixel prediction coefficient vector problems are equal. The reason is as follows. First, the prediction error reduction rate has the following properties.

-The prediction error decreases as the upper limit of the L1 norm increases. In FIG. 3, it corresponds to that the prediction error reduction rate is non-negative.

The prediction error reduction rate decreases as the upper limit of the L1 norm increases. In FIG. 3, the prediction error reduction rate corresponds to a monotonous decrease.

_Let us consider a case where a setting of (θ _c,j1 , θ _c,j2 ) such that (e _c,j1 <e _c,j2 ) is given for a certain _c . By increasing θ _c,j2 by a small amount Δ and decreasing θ _c,j1 by a small amount Δ, a prediction of (e _c,j2 −e _c,j1 ) Δ is made compared with before the change of the L1 norm upper limit. The L1 norm upper bound is not optimal because it can reduce the sum of squared errors. Due to symmetry, the L1 norm upper bound corresponding to (e _c,j1 >e _c,j2 ) is also not optimal. Therefore, the L1 norm upper bound corresponding to (e _c,j1 =e _c,j2 ) is optimal.

However, in the method of arranging the prediction error reduction rates to be equal, there are innumerable candidates depending on which value the prediction error reduction rate is set to. Therefore, in the embodiment of the present invention, by utilizing monotonicity, the optimal prediction error reduction rate setting method is determined by the binary search method. The higher the single upper limit, the smaller the prediction error reduction rate. Further, the higher the single upper limit is, the larger the area of the region 1100 in FIG. 3 is, and thus the prediction error becomes smaller. However, the sum of the L1 norms of each single pixel prediction coefficient needs to be equal to or less than the L1 norm sum total upper limit. That is, the sum of the single upper limits needs to be less than or equal to the L1 norm sum upper limit. Therefore, the prediction error reduction rate needs to be set as low as possible so that the constraint condition that the sum of the single upper limits is less than or equal to the L1 norm sum upper limit is satisfied.

Since each LASSO solution has monotonicity, (3) when a prediction error reduction rate less than a certain fixed value is acquired, the sum of the single upper limits becomes larger than the L1 norm sum upper limit. (4) When the prediction error reduction rate of a certain value or more is acquired, the sum of the single upper limits becomes less than or equal to the L1 norm sum upper limit. Therefore, the prediction error reduction rate such that the sum of the single upper limits is slightly smaller than the L1 norm sum upper limit can be efficiently derived by the binary search.

FIG. 5 is a diagram showing an example of input/output related to all LASSO solution calculation units 502 having all correspondences of each LASSO calculated by LARS or the like when executing the binary search. The prediction error reduction rate to be set for all LASSO solutions is denoted by “E”. The LASSO solution calculation unit 502 having the correspondence relationship in each LASSO solution acquires the prediction error reduction rate E, calculates the L1 norm value from the corresponding single upper limit or single pixel prediction coefficient, and based on the sum of the L1 norm values. The sum of L1 norms of single pixel prediction coefficients can be calculated.

FIG. 6 is a diagram illustrating an example of calculating a single pixel prediction coefficient for each LASSO solution calculation unit 502 such as LARS. When the prediction error reduction rate can be derived by the binary search, each LASSO solution calculation unit 502 acquires the obtained prediction error reduction rate and outputs the corresponding single pixel prediction coefficient, as illustrated in FIG. 6. Accordingly, the linear prediction coefficient output device having the LASSO solution calculation unit 502 can obtain the optimum solution in the optimization problem P, that is, all the prediction coefficients.

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. 7 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 output unit) acquires a video signal 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 all prediction coefficients that need to be transmitted and intra prediction information such as a class number defined for each prediction block to the entropy coding processing unit 105. 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. 9 and subsequent drawings.

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 to be transmitted. 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. 8 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 encoded stream output by the entropy encoding processing unit 105 illustrated in FIG. 7, and obtains 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. 7, 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. 9, the configuration of the intra prediction unit 102 illustrated in FIG. 7 regarding the moving image encoding device 100 will be described.
FIG. 9 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. 9, 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. Since the intra prediction information storage unit 305 needs to transmit the intra prediction information, the intra prediction information storage unit 305 outputs the intra prediction information to the entropy coding processing unit 105.

Next, with reference to FIG. 10, the operation of the intra prediction unit 102 shown in FIG. 9 in the moving picture coding device 100 will be described.
FIG. 10 is a flowchart illustrating an example of detailed operation of the intra prediction unit 102 illustrated 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. 11, the configuration of the intra prediction unit 202 illustrated in FIG. 8 regarding the moving image decoding device 200 will be described.
FIG. 11 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. 11 will be described with reference to FIG.
FIG. 12 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. 13, the configuration of the intra prediction coefficient generation unit 302 illustrated in FIG. 9 will be described with respect to the intra prediction unit 102 of the moving image encoding device 100.
FIG. 13 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, a continuation determination unit 503, and a candidate calculation unit 504. The intra-prediction information division unit 501 acquires the video signal to be compressed and the intra-prediction information that is the class number to which each prediction block belongs, and divides (classifies) each piece of information required for optimization of each single-pixel prediction coefficient. Then, the prediction block and the intra prediction information are output to the LASSO solution calculation unit 502.

The LASSO solution calculation unit 502 acquires the prediction block divided for each single pixel prediction coefficient and the intra prediction information from the intra prediction information division unit 501, acquires the prediction error reduction rate to be set from the candidate calculation unit 504, An optimization problem that minimizes the prediction error is solved under the constraint that the L1 norm of the single pixel prediction coefficient is less than or equal to the single upper limit.

The optimization problem that minimizes the prediction error can be formulated as the same problem as LASSO based on the prediction block and the intra prediction information. The single pixel prediction coefficient obtained by the formulation depends on the single upper bound. Therefore, the LASSO solution calculation unit 502 outputs the combination of the single upper limit, the prediction error reduction rate, and the single pixel prediction coefficient obtained by changing the single upper limit to the continuation determination unit 503 for each single pixel predictor. To do.

The continuation determination unit 503 acquires all the single pixel prediction coefficients from the LASSO solution calculation unit 502, acquires the L1 norm sum total upper limit as an external parameter, and the sum of the L1 norm of all single pixel prediction coefficients is equal to or less than the L1 norm total upper limit. Or not. When the sum of the L1 norms of all the single pixel prediction coefficients is less than or equal to the L1 norm sum total upper limit, and the difference between the sum and the sum total upper limit is less than the minute amount ε, the continuation determination unit 503 acquires all single pixels The prediction coefficient (set of single pixel prediction coefficients) is output as the final prediction coefficient. The continuation determination unit 503 predicts each single pixel when the sum of the L1 norms of all the single pixel prediction coefficients exceeds the upper limit of the L1 norm sum, or when the difference between the sum and the upper limit of sum is a small amount ε or more. The prediction error reduction rate is reset (updated) to determine the single upper limit that should be set for the coefficient.

That is, the continuation determination unit 503 sets the prediction error reduction rate uniformly for all single-pixel prediction coefficients, and thus satisfies the constraint condition that the sum of L1 norms of all prediction coefficients is equal to or less than the sum total upper limit, Further, it is determined whether or not a prediction error reduction rate that is apart from the optimum prediction error reduction rate by a predetermined minute amount is set. In order to reset the prediction error reduction rate, the continuation determination unit 503 outputs the search continuation flag indicating the search continuation of the prediction error reduction rate to the candidate calculation unit 504.

The candidate calculation unit 504 holds the upper limit value and the lower limit value of the prediction error reduction rate to be set. When the candidate calculation unit 504 acquires from the continuation determination unit 503 a flag indicating search continuation of the prediction error reduction rate, the candidate calculation unit 504 calculates the prediction error reduction rate to be set next by the binary search method. For example, the candidate calculation unit 504 sets the reduction rate of the prediction error to the average value of the upper limit value and the lower limit value of the reduction rate of the prediction error for each single pixel prediction coefficient. The candidate calculation unit 504 updates the upper limit value of the prediction error reduction rate to the average value when the set prediction error reduction rate satisfies the constraint condition. The candidate calculation unit 504 updates the lower limit value of the prediction error reduction rate to the average value when the set prediction error reduction rate does not satisfy the constraint condition. The candidate calculation unit 504 calculates the optimum prediction error reduction rate by repeating these processes a predetermined number of times. The candidate calculation unit 504 outputs the prediction error reduction rate to the LASSO solution calculation unit 502 in order to reset the prediction error reduction rate.

Next, with reference to FIG. 14, an operation of the intra prediction coefficient generation unit 302 illustrated in FIG. 9 will be described with respect to the intra prediction unit 102 of the moving image encoding device 100.
FIG. 14 is a flowchart showing an example of detailed operation of the intra prediction coefficient generation unit 302 shown in FIG. The intra-prediction information division unit 501 acquires the intra-prediction information and the video signal, and divides the intra-prediction information into information necessary for formulating the optimization problem of each single-pixel prediction coefficient (step S301).

The intra-prediction information dividing unit 501 outputs all the relationships among the single upper limit, the prediction error reduction rate, and the single-pixel prediction coefficient for each single-pixel prediction coefficient by using the solution method for the optimization problem such as LARS (step S302). ). The intra-prediction information division unit 501 obtains which value to set the prediction error reduction rate for all the single pixel prediction coefficients by the binary search method.

The intra-prediction information division unit 501 initializes an upper limit reduction rate U representing the upper limit of the prediction error reduction rate, a lower limit reduction rate L representing the lower limit, and an intermediate reduction rate M required as a temporary variable for the binary search method. U is a sufficiently large value. L is 0 (step S303).

The intra-prediction information dividing unit 501, until the absolute value of the difference between the sum of the L1 norms of all the single-pixel prediction coefficients and the upper limit of the sum of the L1 norms when the prediction error reduction rate is U is less than a small amount ε, Steps S305 to S309 are repeated. The intra-prediction information division unit 501 determines whether or not the absolute value of the difference between the sum of the L1 norms of all the single-pixel prediction coefficients and the upper limit of the sum of the L1 norms when the prediction error reduction rate is U is less than the minute amount ε. It is determined (step S304).

When the absolute value of the difference between the sum of the L1 norms of all the single pixel prediction coefficients and the upper limit of the sum of the L1 norms when the prediction error reduction rate is U is a small amount ε or more (step S304: NO), intra prediction The information dividing unit 501 sets the intermediate reduction rate M to (U+L)=2 (step S305). The intra prediction information division unit 501 sets each single upper limit so that the prediction error reduction rate for all single pixel prediction coefficients becomes M, and outputs each single pixel prediction coefficient (step S306).

The intra prediction information division unit 501 calculates the sum of the L1 norms of all the single pixel prediction coefficients output in step S306, and determines whether the sum of the L1 norms of all the single pixel prediction coefficients is less than or equal to the L1 norm sum upper limit. It is determined whether or not (step S307). When the sum of the L1 norms of any of the single pixel prediction coefficients exceeds the L1 norm sum total upper limit (step S307: NO), the intra prediction information division unit 501 sets L=M (step S308).

If the sum of the L1 norms of all the single pixel prediction coefficients is equal to or less than the L1 norm sum total upper limit (step S307: YES), the intra prediction information division unit 501 sets U=M (step S309). When the absolute value of the difference between the sum of the L1 norms of all the single pixel prediction coefficients and the upper limit of the sum of the L1 norms in the case where the prediction error reduction rate is U is less than the minute amount ε (step S304: YES), intra prediction The information division unit 501 ends the process.

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. 15 shows a detailed configuration of the intra prediction unit 102a of the moving image encoding apparatus in the conventional technique.
FIG. 15 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, and an intra prediction coefficient storage unit 603. The intra-prediction processing unit 601 acquires the prediction coefficient from the intra-prediction coefficient storage unit 603, 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 transmitted to the entropy coding processing unit 105. The intra prediction coefficient storage unit 603 outputs the intra prediction coefficient stored in the storage area of the intra prediction coefficient storage unit 603 to the intra prediction processing unit 601.

Next, FIG. 16 shows the processing operation of the intra prediction unit 102a shown in FIG. 15 regarding the moving image encoding apparatus in the conventional technique.
FIG. 16 is a flowchart showing a detailed operation example of the intra prediction unit 102a shown in FIG. 15 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 603 (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 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 of the linear prediction coefficient output device is a part of the prediction coefficients for linearly predicting the digital signal to be predicted, and is a constraint condition among a set of single-signal prediction coefficients that are prediction coefficients of a one-dimensional digital signal. A set of single-signal prediction coefficients that satisfy the above is output as prediction coefficients for linearly predicting a digital signal to be predicted.

As a result, the linear prediction coefficient output device according to the embodiment constrains the condition shown in Expression (7) even under the constraint condition that the number of classes and the number of pixels in the 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 solve the optimization problem in which the constraint condition is relaxed in the condition shown in Expression (7), and thereby perform the intra prediction adapted to the signal characteristic. ..

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.

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 image 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... Continuation determination unit, 601... Intra prediction processing unit, 602... Intra prediction information storage unit, 603... Intra prediction coefficient storage unit, 1000... Region, 1100... Region

Claims (6)

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. , it looks including the step of outputting a digital signal of the prediction target as a prediction coefficient for linear prediction,
In the step, in the linear prediction coefficient output device, the sum of absolute value sums of the single signal prediction coefficients is equal to or less than the upper limit value, and the difference between the total sum and the upper limit value is less than a predetermined minute amount. In this case, the set of single-signal prediction coefficients satisfying the constraint is output as a prediction coefficient for linearly predicting the digital signal to be predicted,
Linear prediction coefficients output method. 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. Outputting the prediction target digital signal as a prediction coefficient for linear prediction
Including
In the step, the linear prediction coefficient output device, if the sum exceeds the upper limit, or, if the difference between the sum and the upper limit is a small amount or more, of the updated prediction error Calculate a prediction coefficient for linearly predicting the digital signal to be predicted, based on the reduction rate,
Linear prediction coefficient output method. The predicted digital signal is a digital signal of the prediction target is the matrix product of the digital signal is referred to when the prediction coefficients and coding for linear prediction, according to claim 1 or claim 2 Linear prediction coefficient output 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 output unit that outputs as a prediction coefficient for linearly predicting the digital signal to be predicted ,
The prediction coefficient output unit, if the sum of absolute value sums of the single-signal prediction coefficients is less than or equal to the upper limit value, and if the difference between the sum and the upper limit value is less than a predetermined minute amount, the constraint condition Outputting a set of the single signal prediction coefficients that satisfy the following as prediction coefficients for linearly predicting the digital signal to be predicted,
Linear prediction coefficient output device. 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 output unit for outputting as a prediction coefficient for linearly predicting the digital signal to be predicted
Equipped with
The prediction coefficient output unit, when the total sum exceeds the upper limit value, or when the difference between the total sum and the upper limit value is a small amount or more, based on the updated reduction rate of the prediction error Calculating a prediction coefficient for linearly predicting the prediction target digital signal,
Linear prediction coefficient output device. A linear prediction coefficient output program for causing a computer to execute the linear prediction coefficient output method according to any one of claims 1 to 3 .

Images