Video encoding apparatus and video encoding method

1. A video encoding apparatus comprising:

a processor configured to:

divide a plurality of orthogonal transform coefficients included in each of a plurality of blocks into a plurality of coefficient groups each of which includes a predetermined number of the orthogonal transform coefficients, the plurality of blocks being obtained by dividing a picture included in a video, the plurality of orthogonal transform coefficients being obtained by orthogonally transforming, for each block, a prediction error signal obtained on the basis of difference between a value of each pixel of the picture and a prediction signal of the pixel;

determine, for each of the predetermined number of orthogonal transform coefficients included in a target coefficient group from among the plurality of coefficient groups, a candidate possible to minimize a cost obtained on the basis of a coding error and an amount of coding among a plurality of quantized-coefficient candidates to be used for quantizing the orthogonal transform coefficient, to be a quantized coefficient of the orthogonal transform coefficient, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to lowest frequencies;

determine, for a target coefficient group, whether to substitute all the predetermined number of quantized coefficients included in the target coefficient group by zero, on the assumption that a quantized coefficient that is not zero is included in the coefficient group corresponding to higher frequencies than those of the target coefficient group, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to the lowest frequencies;

determine, for a target coefficient group, a first candidate for the quantized coefficient corresponding to a highest frequency among the quantized coefficients that are included in the target coefficient group and are not zero, on the assumption that all the quantized coefficients included in the coefficient groups corresponding to higher frequencies than those of the target coefficient group are zero, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to the lowest frequencies;

calculate the coding error of the coefficient groups from the coefficient group adjacent to the coefficient group including a second candidate for the quantized coefficient on a higher frequency side to the coefficient group including the first candidate, the second candidate being the quantized coefficient with the highest frequency among the quantized coefficients not being zero, obtained from the coefficient group corresponding to lower frequencies than those of the coefficient group including the first candidate;

update the second candidate to the first candidate when a comparison cost obtained by subtracting the coding error of the coefficient group corresponding to higher frequencies than those of the coefficient group including the first candidate from the cost obtained for the first candidate is lower than a value obtained by adding the coding error to the comparison cost calculated for the second candidate, and determine the second candidate at time when the second candidate for the coefficient group corresponding to highest frequencies among the plurality of coefficient groups is updated, to be the quantized coefficient that is not zero and corresponds to a highest frequency; and

calculate the coding error of the coefficient groups from the coefficient group adjacent to the coefficient group including the second candidate on a higher frequency side to the coefficient group including the first candidate,

wherein

the second candidate includes a third candidate and a fourth candidate, the third candidate being updated to the first candidate also when all the predetermined number of quantized coefficients included in the coefficient group including the first candidate are substituted by zero, the fourth candidate being not updated to the first candidate when all the predetermined number of quantized coefficients included in the coefficient group including the first candidate are substituted by zero, and

the determining a quantized coefficient that is not zero and corresponds to a highest frequency determines the third candidate as the quantized coefficient that is not zero and corresponds to the highest frequency when all the quantized coefficients included in the coefficient groups corresponding to higher frequencies than those of the coefficient group including the third candidate are zero, and

determines the fourth candidate as the quantized coefficient that is not zero and corresponds to the highest frequency when the quantized coefficient that is not zero is included in any one of the coefficient groups corresponding to higher frequencies than those of the coefficient group including the third candidate.

2. The video encoding apparatus according to claim 1 , wherein, the calculating the coding error calculates the coding error on the assumption that all the quantized coefficients included in the coefficient groups from the coefficient group adjacent to the coefficient group including the second candidate on a higher frequency side to the coefficient group including the first candidate are zero.

3. A video encoding method comprising:

dividing, by a processor, a plurality of orthogonal transform coefficients included in each of a plurality of blocks into a plurality of coefficient groups each of which includes a predetermined number of the orthogonal transform coefficients, the plurality of blocks being obtained by dividing a picture included in a video, the plurality of orthogonal transform coefficients being obtained by orthogonally transforming, for each block, a prediction error signal obtained on the basis of difference between a value of each pixel of the picture and a prediction signal of the pixel;

determining, by the processor, for each of the predetermined number of orthogonal transform coefficients included in a target coefficient group from among the plurality of coefficient groups, a candidate possible to minimize a cost obtained on the basis of a coding error and an amount of coding among a plurality of quantized-coefficient candidates to be used for quantizing the orthogonal transform coefficient, to be a quantized coefficient of the orthogonal transform coefficient, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to lowest frequencies;

determining, by the processor, for a target coefficient group, whether to substitute all the predetermined number of quantized coefficients included in the target coefficient group by zero, on the assumption that a quantized coefficient that is not zero is included in the coefficient group corresponding to higher frequencies than those of the target coefficient group, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to the lowest frequencies;

determining, by the processor, for a target coefficient group, a first candidate for the quantized coefficient corresponding to a highest frequency among the quantized coefficients that are included in the target coefficient group and are not zero, on the assumption that all the quantized coefficients included in the coefficient groups corresponding to higher frequencies than those of the target coefficient group are zero, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to the lowest frequencies;

calculating, by the processor, the coding error of the coefficient groups from the coefficient group adjacent to the coefficient group including a second candidate for the quantized coefficient on a higher frequency side to the coefficient group including the first candidate, the second candidate being the quantized coefficient with the highest frequency among the quantized coefficients not being zero, obtained from the coefficient group corresponding to lower frequencies than those of the coefficient group including the first candidate;

updating, by the processor, the second candidate to the first candidate when a comparison cost obtained by subtracting the coding error of the coefficient group corresponding to higher frequencies than those of the coefficient group including the first candidate from the cost obtained for the first candidate is lower than a value obtained by adding the coding error to the comparison cost calculated for the second candidate, and determining the second candidate at time when the second candidate for the coefficient group corresponding to highest frequencies among the plurality of coefficient groups is updated, to be the quantized coefficient that is not zero and corresponds to a highest frequency; and

calculating, by the processor, the coding error of the coefficient groups from the coefficient group adjacent to the coefficient group including the second candidate on a higher frequency side to the coefficient group including the first candidate, wherein

the second candidate includes a third candidate and a fourth candidate, the third candidate being updated to the first candidate also when all the predetermined number of quantized coefficients included in the coefficient group including the first candidate are substituted by zero, the fourth candidate being not updated to the first candidate when all the predetermined number of quantized coefficients included in the coefficient group including the first candidate are substituted by zero, and

the determining a quantized coefficient that is not zero and corresponds to a highest frequency determines the third candidate as the quantized coefficient that is not zero and corresponds to the highest frequency when all the quantized coefficients included in the coefficient groups corresponding to higher frequencies than those of the coefficient group including the third candidate are zero, and

determines the fourth candidate as the quantized coefficient that is not zero and corresponds to the highest frequency when the quantized coefficient that is not zero is included in any one of the coefficient groups corresponding to higher frequencies than those of the coefficient group including the third candidate.

4. The video encoding method according to claim 3 , wherein, the calculating the coding error calculates the coding error on the assumption that all the quantized coefficients included in the coefficient groups from the coefficient group adjacent to the coefficient group including the second candidate on a higher frequency side to the coefficient group including the first candidate are zero.

5. A non-transitory computer-readable recording medium having recorded thereon a video encoding computer program that causes a computer to execute a process comprising:

dividing a plurality of orthogonal transform coefficients included in each of a plurality of blocks into a plurality of coefficient groups each of which includes a predetermined number of the orthogonal transform coefficients, the plurality of blocks being obtained by dividing a picture included in a video, the plurality of orthogonal transform coefficients being obtained by orthogonally transforming, for each block, a prediction error signal obtained on the basis of difference between a value of each pixel of the picture and a prediction signal of the pixel;

determining, for each of the predetermined number of orthogonal transform coefficients included in a target coefficient group from among the plurality of coefficient groups, a candidate possible to minimize a cost obtained on the basis of a coding error and an amount of coding among a plurality of quantized-coefficient candidates to be used for quantizing the orthogonal transform coefficient, to be a quantized coefficient of the orthogonal transform coefficient, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to lowest frequencies;

determining, for a target coefficient group, whether to substitute all the predetermined number of quantized coefficients included in the target coefficient group by zero, on the assumption that a quantized coefficient that is not zero is included in the coefficient group corresponding to higher frequencies than those of the target coefficient group, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to the lowest frequencies;

determining, for a target coefficient group, a first candidate for the quantized coefficient corresponding to a highest frequency among the quantized coefficients that are included in the target coefficient group and are not zero, on the assumption that all the quantized coefficients included in the coefficient groups corresponding to higher frequencies than those of the target coefficient group are zero, the target coefficient group being selected from among the plurality of coefficient groups sequentially from the coefficient group including the orthogonal transform coefficients corresponding to the lowest frequencies;

calculating the coding error of the coefficient groups from the coefficient group adjacent to the coefficient group including a second candidate for the quantized coefficient on a higher frequency side to the coefficient group including the first candidate, the second candidate being the quantized coefficient with the highest frequency among the quantized coefficients not being zero, obtained from the coefficient group corresponding to lower frequencies than those of the coefficient group including the first candidate;

updating the second candidate to the first candidate when a comparison cost obtained by subtracting the coding error of the coefficient group corresponding to higher frequencies than those of the coefficient group including the first candidate from the cost obtained for the first candidate is lower than a value obtained by adding the coding error to the comparison cost calculated for the second candidate, and determining the second candidate at time when the second candidate for the coefficient group corresponding to highest frequencies among the plurality of coefficient groups is updated, to be the quantized coefficient that is not zero and corresponds to a highest frequency; and

calculating the coding error of the coefficient groups from the coefficient group adjacent to the coefficient group including the second candidate on a higher frequency side to the coefficient group including the first candidate, wherein

the second candidate includes a third candidate and a fourth candidate, the third candidate being updated to the first candidate also when all the predetermined number of quantized coefficients included in the coefficient group including the first candidate are substituted by zero, the fourth candidate being not updated to the first candidate when all the predetermined number of quantized coefficients included in the coefficient group including the first candidate are substituted by zero, and

the determining a quantized coefficient that is not zero and corresponds to a highest frequency determines the third candidate as the quantized coefficient that is not zero and corresponds to the highest frequency when all the quantized coefficients included in the coefficient groups corresponding to higher frequencies than those of the coefficient group including the third candidate are zero, and

determines the fourth candidate as the quantized coefficient that is not zero and corresponds to the highest frequency when the quantized coefficient that is not zero is included in any one of the coefficient groups corresponding to higher frequencies than those of the coefficient group including the third candidate.