JP4410172B2 - Motion vector estimation method, motion vector estimation device, motion vector estimation program, and motion vector estimation program recording medium - Google Patents

Description

  The present invention relates to a high-efficiency image signal encoding technique, and more particularly to a technique for performing a motion vector search in decimal pixel precision motion compensation at high speed.

One important technique in video coding is motion compensation (MC) based on block matching. In this method, the encoding target frame f _t (p) (pε {(x, y) | x = 0, 1,..., X−1, y = 0, 1,. }) Is divided into several regions, and the following inter-frame prediction using motion compensation (MC) is performed for each region.

ここで，Ｂ_i は第ｉ番目の領域であり，ｖ_i は次式を満たす動きベクトルである。

Here, B _i is the i-th region, and v _i is a motion vector that satisfies the following equation.

なお，Ｒ_i はＢ_i に対応する探索領域であり，

R _i is a search area corresponding to B _i ,

は，次に続く関数を最小化するｖを返す。すなわち，探索範囲Ｒ_i において，領域Ｂ_i 内での予測誤差を最小化するｖが動きベクトルｖ_i として選ばれる。

Returns v which minimizes the next function. That is, in the search range R _i, v that minimizes the prediction error in the area B _i is selected as the motion vector v _i.

  A typical technique for speeding up motion vector search that guarantees the minimum of prediction errors is a technique called SEA (see Non-Patent Document 1). In this method, a lower limit value of MC error is estimated in advance, and search points are narrowed down based on the lower limit value. In this method, the lower limit of the following equation is used for the MC error E (v).

E (v) ≧ C−S (v) (2)
Here, C is the pixel value sum of the coding block, and S (v) is the pixel value sum of the reference block, each represented by the following equation.

式（２）の証明は，以下の通りである。

The proof of equation (2) is as follows.

予測誤差の低減を目的として，動きベクトルを小数画素精度で表現する動き補償が検討されている。１／ｍ画素精度の動き補償の場合，動きベクトルは次式を満たすベクトルとして求める。

For the purpose of reducing the prediction error, motion compensation that expresses motion vectors with decimal pixel accuracy is being studied. In the case of motion compensation with 1 / m pixel accuracy, the motion vector is obtained as a vector that satisfies the following equation.

ここで，ｆ^* _t-1 （ｐ）はｆ_t-1 （ｐ）から生成される補間画像であり，１／ｍ画素間隔で画素値をもつ。例えば，ISO/IEC 13818-2 ＭＰＥＧ−２における１／２画素精度の動き補償の場合，次のような補間画像を用いる。

Here, f ^* _t−1 (p) is an interpolated image generated from f _t−1 (p), and has pixel values at 1 / m pixel intervals. For example, in the case of motion compensation with 1/2 pixel accuracy in ISO / IEC 13818-2 MPEG-2, the following interpolated image is used.

ここで，δ_x ＝（１，０），δ_y ＝（０，１）であり，ｐは整数値を要素とするベクトルである。つまり，予測時の参照フレームの位置が２画素の中心なら（式（７ｂ）または式（７ｃ）），２つの画素値の丸め付き平均を予測値として使用し，同位置が正方形の頂点に並んだ４画素の中心なら，４つの画素値の丸め付き平均を予測値として使用することになる（式（７ｄ））。なお，式（７ｂ）〜式（７ｄ）における１／２および２／４の演算は，例えばビットシフト演算によって行われ，小数点以下は切り捨てられる。

Here, δ _x = (1, 0), δ _y = (0, 1), and p is a vector whose elements are integer values. That is, if the position of the reference frame at the time of prediction is the center of two pixels (equation (7b) or equation (7c)), the rounded average of the two pixel values is used as the prediction value, and the same position is arranged at the apex of the square. If the center is four pixels, the rounded average of the four pixel values is used as the predicted value (formula (7d)). In addition, 1/2 and 2/4 operations in the equations (7b) to (7d) are performed by, for example, a bit shift operation, and the decimal part is rounded down.

  FIG. 1 shows reference pixel positions in the interpolation processing of Expressions (7b) to (7d). For example, FIG. 1A shows a case where the interpolation pixel position is a horizontal half-pixel position, and a circle indicated by an arrow is the interpolation pixel position. A black square is a reference pixel position used for interpolation, and the number shown on the black square side represents a weighting coefficient at the time of interpolation. 1B shows a case where the interpolation pixel position is a vertical half-pixel position, and FIG. 1C shows a case where the interpolation pixel position is a diagonal half-pixel position.

Hereinafter, the motion compensation using the motion vector obtained from Equation (1) is referred to as integer pixel accuracy MC. On the other hand, motion compensation using a motion vector obtained from Equation (6) is called decimal pixel accuracy MC. In addition, since the discussion is focused on the i-th region, B _i is represented as B.

  In the case of the decimal pixel accuracy MC, the amount of calculation of the motion vector search increases compared to the integer pixel accuracy MC. This is because the number of search points included in the search area increases. When the search area includes pixels of w × h points in the horizontal direction w and the vertical direction h, the search points in the integer pixel accuracy MC are w × h points, whereas in the fractional pixel accuracy MC with 1 / m pixel accuracy. Search points are {m (w−1) +1} × {m (h−1) +1} points.

  When reducing the amount of calculation in motion vector search with decimal pixel accuracy MC, there is a method for giving up the motion vector of Equation (6), which is an optimal solution, and for obtaining a motion vector corresponding to the suboptimal solution of Equation (6). Many have been studied. In this case, the prediction error increases in exchange for a reduction in calculation amount. However, such an increase in prediction error is not desirable in the fractional pixel accuracy MC introduced to reduce the prediction error. For this reason, a motion vector search method that reduces the amount of calculation without increasing the prediction error is required.

  As a method for reducing the amount of calculation, there is SEA shown in Non-Patent Document 1 described above, but SEA is only applied to integer pixel accuracy MC, and no examination is made on decimal pixel accuracy MC.

Therefore, the present inventors have also proposed a technique for reducing the calculation amount by pruning a motion vector search by comparison with a lower limit value while guaranteeing the minimization of the prediction error even for the decimal pixel accuracy MC. Non-patent document 2 proposes. According to the method of Non-Patent Document 2, especially when obtaining the lower limit value of the decimal MC error, the increase in the calculation amount is suppressed by using the already calculated result, and the high prediction that the decimal pixel accuracy MC has with a small calculation amount. Performance can be realized.
W. Li and E. Salari: “Successive elimination algorithm for motion estimation”, IEEE Transactions on Image Processing, Volume 4, Issue 1, Jan., pp. 105-107, 1995. Yukihiro Bando, Masayuki Takamura, Yoshiyuki Yashima: “Acceleration of whole-search sub-pixel accuracy motion estimation”, Information Processing Society of Japan, 2004-AVM-44, 2004/3/4.

  As described above, according to the technique of “acceleration of all-search decimal pixel accuracy motion estimation” described in Non-Patent Document 2, when applying SEA to the decimal pixel accuracy MC, the amount of calculation accompanying an increase in the number of search points The problem of the increase is reduced, and the speed of motion vector search in decimal pixel accuracy MC is increased.

  The present invention further improves the technique of “acceleration of all-search sub-pixel accuracy motion estimation” described in Non-Patent Document 2 to calculate the lower limit of MC error in sub-pixel accuracy motion estimation. In consideration of rounding errors that occur in the calculation of value sums, by calculating a tight lower limit, it is intended to promote pruning in the search, and to further speed up the motion vector search in decimal pixel precision MC. To do.

  It is another object of the present invention to realize a motion vector estimation that suppresses an increase in the calculation amount by calculating the rounding error with a small calculation amount.

When comparing the MC errors of two motion vectors v and u, the MC error E of the motion vector u is not compared directly with the MC error E (v) of the motion vector v. A comparison is made with the lower limit L (u) of (u). At this time,
E (v) ≦ L (u)
Then, since L (u) is the lower limit value of MC error E (u),
E (v) ≦ E (u)
Therefore, it is not necessary to calculate and compare E (u). In other words, the calculation of E (u) is
L (u) <E (v)
It is sufficient to do this only when

  As will be described later, the lower limit value of the MC error can be calculated with a smaller calculation amount than the MC error. For this reason, by comparing with the lower limit value of the MC error and omitting the calculation of the MC error, it is possible to reduce the calculation amount while ensuring the minimization of the prediction error.

  The present invention calculates a lower limit value for an inter-frame prediction error in the fractional pixel accuracy MC, performs pruning of a search using the lower limit value, and calculates an already obtained addition result and shift when calculating the lower limit value. A rounding error is calculated using an operation or the like, and a lower limit value is calculated using the rounding error. By calculating the lower limit in consideration of rounding errors, tighter pruning is possible, and the amount of calculation can be greatly reduced while maintaining the same accuracy as when full search is performed.

  Further, according to the present invention, when calculating the lower limit value, a round-off error is preliminarily looked up in a lookup table according to the value of the lower n bits (n is a number determined by the number of pixels referenced in the interpolation process) of the related reference pixel group. The amount of calculation can be further reduced by determining the correction value for the rounding error with reference to the table and calculating the lower limit value.

  Further, when the rounding error is stored in the lookup table, the memory capacity required for the lookup table can be reduced by storing the rounding error in an individual lookup table according to the decimal pixel position to be interpolated. .

  In addition, when calculating the lower limit value of the prediction error, the present invention focuses only on the difference between the reference areas indicated by the two motion vectors, and calculates the difference value of the lower limit value of the prediction error of the reference area indicated by the two motion vectors. Based on the lower limit value of the prediction error of one motion vector, the lower limit value of the prediction error for the other motion vector is calculated. Thereby, the amount of calculation can be reduced by using the already calculated result.

  In the present invention, when calculating the lower limit value of the prediction error, the rounding error for the difference portion of the reference area pointed to by the two motion vectors is stored in a lookup table, and one motion vector is referred to by referring to the table. Based on the lower limit value of the prediction error for, the lower limit value of the prediction error for the other motion vector is calculated. By calculating a rounding error for a difference portion using a lookup table, the amount of calculation can be greatly reduced.

  By using the present invention, it is possible to reduce the amount of calculation in the motion vector search while completely guaranteeing the minimization of the prediction error in the decimal pixel accuracy MC. For this reason, the increase in the calculation amount which has been a problem in the decimal pixel accuracy MC can be solved, and high prediction performance by the decimal pixel accuracy MC can be enjoyed with a small calculation amount. In particular, the effect of pruning in the search is great by obtaining rounding errors that occur in the calculation of the reference pixel value at the decimal pixel position to be interpolated and calculating the corrected lower limit value.

[First Embodiment]
The lower limit value of the MC error (decimal pixel accuracy MC error) for the decimal pixel precision motion vector v ^* is derived. In the following, description will be given by taking, as an example, a ½ pixel accuracy MC using the interpolation images of Expressions (7a) to (7d). At this time, the motion vector v ^* can have the following four values.

ここで，δ_x ＝（１，０），δ_y ＝（０，１）であり，ｖは整数値を要素とするベクトルである。なお，以下では，動きベクトルｖ^* がｖ^* ＝ｖとして整数値を要素とする場合，整数動きベクトルと呼び，それ以外を小数動きベクトルと呼ぶ。以下，ｖ^* の値に応じてＥ（ｖ^* ）を４通りに場合分けし，各下限値を求める。

Here, δ _x = (1, 0), δ _y = (0, 1), and v is a vector whose elements are integer values. In the following, when the motion vector v ^* is v ^* = v is an integer value with the element as referred integer motion vector, called the others and fractional motion vectors. Hereinafter, v according to the value of ^* and case analysis E a (v ^*) in four ways, obtaining the respective lower limit values.

(I) When v ^* = v:
Since the motion vector indicates the pixel position in the reference frame, the MC error has the following lower limit as in the case of SEA with integer pixel accuracy MC.

E (v ^* ) ≧ C−S (v) (9)
Here, C and S (v) are respectively expressed by Expression (3) and Expression (4).

(Ii) When v ^* = v−δ _x / 2:
The position of the reference frame pointed to by the motion vector is the center of two pixels, and the MC error E (v ^* ) has the following lower limit value.

E (v ^* ) ≧ C−S (v) / 2−S (v−δ _x ) / 2−R _h (v) (10)
Here, R _h (v) is a correction value for rounding error, and is obtained from the following equation.

ここで，○付きの＋はビット毎の論理積を行う演算子を表す。

Here, + with ○ represents an operator that performs a logical product for each bit.

  The proof of equation (10) is as follows. In the following proof, Expression (7b) is used because the position of the reference frame pointed to by the motion vector is the center of two pixels in the expansion from Expression (12a) to Expression (12b).

(iii) ｖ^* ＝ｖ−δ_y ／２の場合：
上述の（ii）と同様に動きベクトルの指す参照フレームの位置は２画素の中心となり，ＭＣ誤差は次の下限値を持つ。

(iii) When v ^* = v−δ _y / 2:
As in (ii) above, the position of the reference frame pointed to by the motion vector is the center of two pixels, and the MC error has the following lower limit value.

E (v ^* ) ≧ C−S (v) / 2−S (v−δ _y ) / 2−R _v (v) (13)
Proof can be performed in the same manner as in (ii). R _v (v) is a correction value for rounding error, and is obtained from the following equation.

（iv）ｖ^* ＝ｖ−（δ_x ＋δ_y ）／２の場合：
動きベクトルの指す参照フレームの位置は４画素の中央となり，ＭＣ誤差は次の下限値を持つ。

(Iv) When v ^* = v− (δ _x + δ _y ) / 2:
The position of the reference frame pointed to by the motion vector is the center of the four pixels, and the MC error has the following lower limit value.

E (v ^* ) ≧ C−S (v) / 4−S (v−δ _x ) / 4−S (v−δ _y ) / 4
_{-S (v-δ x -δ y} ) / 4-R d (v) (15)
R _d (v) is a correction value for rounding error, and is obtained from the following equation.

式（１５）の証明は，以下の通りである。なお，以下の証明において，式（１７ａ）から式（１７ｂ）への展開では，動きベクトルの指す参照フレームの位置は４画素の中央となることから，式（７ｄ）を用いた。

The proof of equation (15) is as follows. In the following proof, in the expansion from Expression (17a) to Expression (17b), Expression (7d) is used because the position of the reference frame pointed to by the motion vector is the center of four pixels.

以上（ｉ）〜（iv）をまとめると，ＭＣ誤差の下限値Ｌ（ｖ^* ）は次式となる。

Summarizing the above (i) to (iv), the lower limit L (v ^* ) of the MC error is given by the following equation.

［第２の実施形態：補正値テーブルの利用］
丸め誤差の補正値は補正値テーブルと呼ぶルックアップテーブルに格納し，予測誤差の下限値の計算時には，同テーブルを参照するものとする。以下，同テーブルの作成法について詳述する。

[Second Embodiment: Use of Correction Value Table]
The correction value for the rounding error is stored in a lookup table called a correction value table, and this table is referred to when calculating the lower limit value of the prediction error. The method for creating the table will be described in detail below.

In case of (ii) above:
R _h (v) can be expanded as follows.

この式（１９）から明らかであるように，参照領域をｘ方向に１７画素，ｙ方向に１画素の幅を持つ１７×１画素の矩形領域に分割したとすると，各矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で上述の丸め誤差の補正値をルックアップテーブルに格納する。格納する値は，以下の通りである。

As is clear from this equation (19), if the reference area is divided into rectangular areas of 17 × 1 pixels having a width of 17 pixels in the x direction and 1 pixel in the y direction, the rounding error in each rectangular area is independent. Determined. Therefore, the correction value for the rounding error is stored in the lookup table in units of the same rectangular area. The values to be stored are as follows.

この補正値は，１７の画素の下位１ビットから定まり，０から１６の値を取り得る。従って，この補正値に対するルックアップテーブルのサイズは，
５×２¹⁷＝０．６５５３６［Ｍｂｉｔｓ］
となる。

This correction value is determined from the lower 1 bit of 17 pixels and can take a value from 0 to 16. Therefore, the size of the lookup table for this correction value is
5 × 2 ¹⁷ = 0.65536 [Mbits]
It becomes.

In case of (iii) above:
R _v (v) can be expanded as follows.

この式（２１）から明らかであるように，各列における丸め誤差は独立に定まる。すなわち，参照領域をｘ方向に１画素，ｙ方向に１７画素の幅を持つ１×１７画素の矩形領域に分割したとすると，各矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で上述の丸め誤差の補正値をルックアップテーブルに格納する。格納する値は，以下の通りである。

As is clear from this equation (21), the rounding error in each column is determined independently. That is, if the reference area is divided into rectangular areas of 1 × 17 pixels having a width of 1 pixel in the x direction and 17 pixels in the y direction, the rounding error in each rectangular area is determined independently. Therefore, the correction value for the rounding error is stored in the lookup table in units of the same rectangular area. The values to be stored are as follows.

この補正値は，１７個の画素の下位１ビットから定まり，０から１６の値を取り得る。従って，この補正値に対するルックアップテーブルのサイズは，
５×２¹⁷＝０．６５５３６［Ｍｂｉｔｓ］
となる。

This correction value is determined from the lower 1 bit of 17 pixels and can take a value from 0 to 16. Therefore, the size of the lookup table for this correction value is
5 × 2 ¹⁷ = 0.65536 [Mbits]
It becomes.

In case of (iv) above:
R _d (v) can be expanded as follows.

ここで，Φ（ｘ，ｙ，ｔ）は，以下の通りとする。

Here, Φ (x, y, t) is as follows.

Φ (x, y, t) = _ft (x, y) + _ft (x-1, y)
+ F _t (x, y−1) + f _t (x−1, y−1)
As is clear from this equation (23), the rounding error in a 17 × 2 pixel rectangular region having a width of 17 pixels in the x direction and 2 pixels in the y direction in the reference region is determined independently. However, when a correction value lookup table is created for this rectangular area, the size of the lookup table is 85.899 [Gbits], which cannot be said to be a realistic size in consideration of implementation. Therefore, the rectangular area is divided into two, and correction values are stored in a lookup table in units of rectangular areas of 2 × 8 pixels. The values to be stored are as follows.

ｒ_d （ｘ₀ ，ｙ₀ ，ｖ_x ，ｖ_y ）に格納する補正値は，１８個の画素の下位１ビットから定まり，０から８の値を取り得る。従って，このルックアップテーブルのサイズは，
４×２¹⁸＝１．０４８６［Ｍｂｉｔｓ］
となる。

The correction value stored in r _d (x ₀ , y ₀ , v _x , v _y ) is determined from the lower 1 bit of 18 pixels and can take a value of 0 to 8. Therefore, the size of this lookup table is
4 × 2 ¹⁸ = 1.0486 [Mbits]
It becomes.

[Third Embodiment]
When obtaining the minimum value of prediction errors for continuous motion vectors, the amount of calculation can be reduced by paying attention to the difference area in the adjacent reference area. When the lower limit value of the prediction error is given by Expression (18), L (v ^* −δ _x ) and L (v ^* ) have the following relationship.

ここで，Ｓ^* （ｖ^* ），Ｒ^* （ｖ^* ）は，以下の通りである。

Here, S ^* (v ^* ) and R ^* (v ^* ) are as follows.

図２，図３，図４に動きベクトルｖ^* −δ_x およびｖ^* の指す領域を示す。これらは，いずれも動き補償の領域が４×４［画素］の例を図示したものである。

2, FIG. 3 shows the area indicated by the vector v ^* - [delta _x and v ^* motion in FIG. Each of these is an example in which the motion compensation region is 4 × 4 [pixel].

_{^{R * (v * -δ x)}} -R * (v *) is the correction value to be calculated. Hereinafter, v ^* in accordance with the value _{^{of, S * (v * -δ x}} ) -S * (v *), will be described in detail _{^{R * (v * -δ x)}} -R * (v *) of the calculation method . Hereinafter, the motion compensation area is 16 × 16.

(I) When v ^* = v:
In this case, no correction value is required because no rounding error occurs. In _{^{addition, S * (v * -δ x}} ) -S * (v *) is given by the following equation.

（ii）ｖ^* ＝ｖ−δ_x ／２の場合：
Ｓ^* （ｖ^* −δ_x ）−Ｓ^* （ｖ^* ）は次式となる。

(Ii) When v ^* = v−δ _x / 2:
_{^{S * (v * -δ x)}} -S * (v *) becomes the following equation.

また，Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ）は次式となる。

In _{^{addition, R * (v * -δ x}} ) -R * (v *) becomes the following equation.

(iii) ｖ^* ＝ｖ−δ_y ／２の場合：
Ｓ^* （ｖ^* −δ_y ）−Ｓ^* （ｖ^* ）は次式となる。

(iii) When v ^* = v−δ _y / 2:
S ^* (v ^* −δ _y ) −S ^* (v ^* ) is as follows.

また，Ｒ^* （ｖ^* −δ_y ）−Ｒ^* （ｖ^* ）は次式となる。

R ^* (v ^* −δ _y ) −R ^* (v ^* ) is given by the following equation.

（iv）ｖ^* ＝ｖ−δ_x ／２−δ_y ／２の場合：
Ｓ^* （ｖ^* −δ_x −δ_y ）−Ｓ^* （ｖ^* ）は次式となる。

^{(Iv) v * = v-} δ if the _{x / 2-δ y / 2} :
_{^{S * (v * -δ x -δ}} y) -S * (v *) becomes the following equation.

また，Ｒ^* （ｖ^* −δ_x −δ_y ）−Ｒ^* （ｖ^* ）は次式となる。

In _{^{addition, R * (v * -δ x}} -δ y) -R * (v *) becomes the following equation.

［第４の実施形態：差分補正値テーブルの利用］
連続した動きベクトルに対する予測誤差の最小値を求める場合，隣接参照領域における差異領域に注目することで計算量を削減できる。このときに用いる丸め誤差の補正値は差分補正値テーブルと呼ぶルックアップテーブルに格納し，予測誤差の下限値の計算時には，同テーブルを参照するものとする。

[Fourth Embodiment: Use of Difference Correction Value Table]
When obtaining the minimum value of prediction errors for continuous motion vectors, the amount of calculation can be reduced by paying attention to the difference area in the adjacent reference area. The correction value of the rounding error used at this time is stored in a lookup table called a difference correction value table, and is referred to when calculating the lower limit value of the prediction error.

When the lower limit value of the prediction error is given by equation (18), L (v ^* −δ _x ) and L (v ^* ) are in the relationship of equation (25) described above. S ^* (v ^* −δ _x ) −S ^* (v ^* ) is as described in “Third embodiment: correction value of rounding error”. _{^{R * (v * -δ x)}} -R * (v *) a value is stored in the differential correction value table. Hereinafter, the method of creating the table will be described in detail according to the value of v ^* .

(I) When v ^* = v:
In this case, no correction value is required because no rounding error occurs.

(Ii) When v ^* = v−δ _x / 2:
R ^* (v ^* −δ _x ) −R ^* (v ^* ) is expressed by equation (30). According to this equation, the rounding error in a rectangular area of 2 × 16 pixels having a width of 2 pixels in the x direction and 16 pixels in the y direction is determined independently. If the size of the correction value lookup table for this rectangular area is too large for the system to be implemented, the rectangular area is divided into two, and the correction value is looked up in a rectangular area unit of 2 × 8 pixels. Store in r _h (x ₀ , y ₀ , d _x , _dy ). ^ R _h (x ₀ , y ₀ , d _x , _dy )

として定義すると，Ｒ^* （ｖ^* −δ_x ）−Ｒ^* （ｖ^* ）は次式のように表せる。

When defined _{^{as, R * (v * -δ x}} ) -R * (v *) is expressed as follows.

(iii) ｖ^* ＝ｖ−δ_y ／２の場合：
Ｒ^* （ｖ^* −δ_y ）−Ｒ^* （ｖ^* ）は式（３２）となる。同式によれば，ｘ方向に１画素，ｙ方向に１７画素の幅を持つ１×１７画素の矩形領域における丸め誤差は独立に定まる。そこで，同矩形領域単位で補正値をルックアップテーブル＾ｒ_v （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）に格納する。＾ｒ_v （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）を，

(iii) When v ^* = v−δ _y / 2:
R ^* (v ^* −δ _y ) −R ^* (v ^* ) is expressed by Expression (32). According to this equation, the rounding error in a rectangular area of 1 × 17 pixels having a width of 1 pixel in the x direction and 17 pixels in the y direction is determined independently. Therefore, to store the correction value in the same rectangular area unit look-up table _{^ r v (x 0, y} 0, d x, d y) on. ^ R _v (x ₀ , y ₀ , d _x , _dy )

として定義すると，Ｒ^* （ｖ^* −δ_y ）−Ｒ^* （ｖ^* ）は次式のように表せる。

R ^* (v ^* −δ _y ) −R ^* (v ^* ) can be expressed as the following equation.

（iv）ｖ^* ＝ｖ−δ_x ／２−δ_y ／２の場合：
Ｒ^* （ｖ^* −δ_x −δ_y ）−Ｒ^* （ｖ^* ）は式（３４）となる。同式によれば，ｘ方向に２画素，ｙ方向に１７画素の幅を持つ２×１７画素の矩形領域における丸め誤差は独立に定まる。この矩形領域に対する補正値のルックアップテーブルのサイズが実装するシステムに対して大きすぎる場合は，同矩形領域を２つに分割し，２×８画素の矩形領域単位で補正値をルックアップテーブル＾ｒ_d （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）に格納する。＾ｒ_d （ｘ₀ ，ｙ₀ ，ｄ_x ，ｄ_y ）を，

^{(Iv) v * = v-} δ if the _{x / 2-δ y / 2} :
R ^* (v ^*-[ delta] _{x- [} delta] _y ) -R ^* (v ^* ) is given by equation (34). According to this equation, the rounding error in a rectangular area of 2 × 17 pixels having a width of 2 pixels in the x direction and 17 pixels in the y direction is determined independently. If the size of the correction value lookup table for this rectangular area is too large for the system to be implemented, the rectangular area is divided into two, and the correction value is looked up in a rectangular area unit of 2 × 8 pixels. Store in r _d (x ₀ , y ₀ , d _x , _dy ). ^ R _d (x ₀ , y ₀ , d _x , _dy )

として定義すると，Ｒ^* （ｖ^* −δ_x −δ_y ）−Ｒ^* （ｖ^* ）は次式のように表せる。

When defined _{^{as, R * (v * -δ x}} -δ y) -R * (v *) is expressed as follows.

[Flow of encoding process]
The flow of the encoding process according to the embodiment of the present invention will be described with reference to FIG.

Step S1: With the predicted pixel, reference pixel, and initial motion vector as inputs, a prediction error E (v ^* ) is calculated for the motion vector v ^* designated as the initial motion vector, and is output.

  Step S2: The pixel to be predicted is input, and the sum of pixel values to be predicted is written to the register. More specifically, the predicted pixel value sum is calculated by equation (3).

Step S3: A process of calculating a lower limit L (v ^* ) of a prediction error when using a motion vector and a reference pixel as input is performed. Details will be described later.

Step S4: The lower limit L (v ^* ) obtained in step S3 and the value ε stored as the minimum value of the prediction error are input, and L (v ^* ) and ε are compared in magnitude.
L (v ^* ) <ε
If so, the process proceeds to step S5, and if not, the process proceeds to step S8.

Step S5: A process of calculating a prediction error E (v ^* ) with respect to the motion vector v ^* is performed with the predicted pixel and the reference pixel as inputs, and E (v ^* ) is output.

Step S6: Performing a process of comparing the magnitudes of both values with the prediction error E (v ^* ) for the motion vector v ^* and the value ε stored as the minimum value of the prediction error as inputs.
E (v ^* ) <ε
If so, the process proceeds to step S7, and if not, the process proceeds to step S8.

Step S7: A process of substituting the motion vector v ^* and the prediction error E (v ^* ) for the motion vector into the registers M and ε, respectively.

  Steps S8 and S9: The above process is repeated for all motion vectors, and finally, the value stored in the register M is output as a motion vector that minimizes the prediction error among all the motion vectors.

  Details of step S3 are shown below. Note that the processing of FIG. 6 or FIG. 7 is performed on the initial motion vector.

In the case of the “first embodiment”:
The flow of calculation of the lower limit value in the case of the “first embodiment” will be described with reference to FIG.

  Step S11: The predicted pixel value sum written in step S2 of FIG. 5 is read from the register.

Step S12: Using the motion vector and the reference pixel as inputs, calculate a reference pixel value sum S (v ^* ) for the motion vector and write it to the register. More specifically, the reference pixel value sum is calculated by Expression (4).

Step S13: A process of calculating correction values R _h (v ^* ), R _v (v ^* ), R _d (v ^* ) for rounding errors for each decimal pixel position and inputting them into a register by inputting a motion vector and a reference pixel. Do. More specifically, it is obtained by Expression (11), Expression (14), and Expression (16).

Step S14: Predicted pixel value sum C, reference pixel value sum S (v ^* ), correction values R _h (v ^* ), R _v (v ^* ), R _d (v ^* ) for rounding errors for each decimal pixel position As an input, a process for calculating the lower limit L (v ^* ) of the motion vector prediction error is performed and written to the register. More specifically, the lower limit value is obtained from equation (18).

In the case of the “second embodiment”:
The flow of calculation of the lower limit value in the case of the “second embodiment” will be described with reference to FIG.

  Step S21: Same as step S11.

  Step S22: Same as step S12.

  Step S23: The correction value lookup table stored in advance in the register is read.

  Step S24: The reference pixel, the correction value lookup table read in step S23 is input, the correction value lookup table is referred to based on the reference pixel value, the correction value for the rounding error for each decimal pixel position is obtained, and the correction value is obtained. Write to the register.

  Step S25: Same as step S14.

In the case of the “third embodiment”:
The flow of calculation of the lower limit value in the case of the “third embodiment” will be described with reference to FIG.

  Step S31: The lower limit value of the prediction error for the motion vector before update is read from the register.

  Step S32: Using the motion vector and the reference pixel as input, the difference value of the reference pixel value sum with respect to the motion vector is calculated and written to the register. More specifically, the reference pixel value sum is calculated by Expression (28), Expression (29), Expression (31), and Expression (33).

  Step S33: Using the motion vector and the reference pixel as input, calculate a difference value of the correction value for the rounding error at each decimal pixel position, and write it out to the register. More specifically, it is obtained by Expression (30), Expression (32), and Expression (34).

Step S34: The difference value of the reference pixel value sum, the difference value of the correction value for the rounding error for each decimal pixel position, and the lower limit value of the prediction error for the motion vector before the update are input, and the lower limit value L (v ^* ) To calculate. More specifically, the lower limit value L (v ^* ) is obtained from equation (25).

In the case of the “fourth embodiment”:
The flow of calculation of the lower limit value in the case of the “fourth embodiment” will be described with reference to FIG.

  Step S41: Same as step S31.

  Step S42: Same as step S32.

  Step S43: A difference correction value lookup table stored in advance in a register is read.

Step S44: The reference pixel, the difference correction value lookup table read in step S43 is input, the difference correction value lookup table is referenced based on the reference pixel value, and the difference value R ^* of the correction value for the rounding error for each decimal pixel position _{^{(v * -δ x) -R *}} (v *), R * (v * -δ y) -R * (v *), R * (v * -δ x -δ y) -R * (v * ) And write to the register.

  Step S45: Same as step S34.

[Encoding device]
Next, a configuration example of the encoding device will be described.

In the case of the “first embodiment”:
FIG. 10 shows an apparatus configuration diagram according to the first embodiment of the present invention.

  When the motion vector is the initial motion vector, the switch SW1 performs processing of the initial motion vector prediction error calculation unit 101 and the predicted pixel value sum determination unit 102. In other cases, the reference pixel value sum determination unit 104 is switched to perform processing.

  The initial motion vector prediction error calculation unit 101 receives a pixel of the encoding target block, a reference pixel, and a motion vector corresponding to the initial motion vector, performs a process of calculating a prediction error, and stores the prediction error as a temporary minimum prediction error And outputs the motion vector to the provisional optimal motion vector storage unit 113.

  The predicted pixel value sum determining unit 102 receives the pixels of the encoding target block, performs a process of calculating a predicted pixel value sum in the block, and calculates the predicted pixel value sum as a predicted pixel value sum storage unit. To 103. More specifically, the predicted pixel value sum is calculated by Expression (3).

The reference pixel value sum determination unit 104 receives the reference pixel and the motion vector, performs a process of calculating the reference pixel value sum, and outputs the reference pixel value sum to the reference pixel value sum storage unit 105. More specifically, the reference pixel value sum is calculated by Expression (4). At the same time, values f _t-1 (p−v) + f _t−1 (p−v + δ _x ), f _t−1 (p−v) + f _t−1 (p−v + δ _y ), f _t−1 (p−v) + f _t−1 (p−v + δ _x ) + f _t−1 (p−v + δ _y ) + f _t−1 (p−v + δ _x + δ _y ) (p∈B) Write to the value sum storage unit 116.

  The correction value calculation unit 115 reads the partial reference pixel value sum from the partial reference pixel value sum storage unit 116, performs a process of calculating a correction value for the lower limit value of the prediction error, and outputs the correction value to the correction value storage unit 107. To do. The specific calculation of the correction value is obtained by Equation (11), Equation (14), and Equation (16) for each decimal pixel position.

  The prediction error lower limit determination unit 106 receives a motion vector, and receives a predicted pixel value sum and a reference pixel value sum from the predicted pixel value sum storage unit 103, the reference pixel value sum storage unit 105, and the correction value storage unit 107, respectively. , Read the correction value, calculate the lower limit value of the prediction error, and output the lower limit value to the lower limit value storage unit 108. The specific calculation of the lower limit value is performed according to Equation (18).

  The pruning determination unit 109 reads the lower limit value of the prediction error and the minimum value of the prediction error stored so far from the lower limit value storage unit 108 and the provisional minimum prediction error storage unit 112, and compares the two values in magnitude. If the lower limit value is smaller, the process proceeds to the next process (switch SW2). Otherwise, the process for the current motion vector is terminated.

  The prediction error calculation unit 110 receives a pixel, a reference pixel, and a motion vector of an encoding target block, performs a process for calculating a prediction error, and outputs the prediction error.

  The optimal motion vector determination unit 111 receives the prediction error calculated by the prediction error calculation unit 110 as an input, reads the minimum value of the prediction error stored so far from the provisional minimum prediction error storage unit 112, and compares the two values in magnitude. When the prediction error calculated by the prediction error calculation unit 110 is smaller, the prediction error is stored in the provisional minimum prediction error storage unit 112, and the motion vector is stored in the provisional optimum motion vector storage unit 113.

  The motion vector control unit 114 repeats the above processing for all the motion vectors, and finally outputs the value stored in the provisional optimal motion vector storage unit 113 as the optimal motion vector.

In the case of the “second embodiment”:
FIG. 11 shows an apparatus configuration diagram according to the second embodiment of the present invention.

  Each of the initial motion vector prediction error calculation unit 201 to the motion vector control unit 214 performs the same processing as the initial motion vector prediction error calculation unit 101 to the motion vector control unit 114 described with reference to FIG.

The correction value calculation unit 215 receives the values read from the look-up table storage unit 216 in which correction values are stored in advance, and receives correction values R _h (v ^* ), R _v (v ^* ), R _d (v ^* ) Is calculated and written to the correction value storage unit 207. The specific calculation of the correction value follows Formula (19), Formula (21), and Formula (23).

The lookup table storage unit 216 stores correction value table values r _v (x ₀ , y ₀ , reference values) to be referred to when calculating correction values R _h (v ^* ), R _v (v ^* ), R _d (v ^* ). _{v x, v y), r} h (x 0, y 0, v x, v y), r d (x 0, y 0, v x, is stored v _y) in advance.

In the case of the “third embodiment”:
FIG. 12 shows an apparatus configuration diagram according to the third embodiment of the present invention.

The reference pixel value sum difference value determination unit 304 receives the motion vector and the reference pixel, calculates a difference value of the reference pixel value sum with respect to the current motion vector and the motion vector before update, and a reference pixel value sum difference value storage unit Write to 305. More specifically, the calculation is performed by Expression (28), Expression (29), Expression (31), and Expression (33). At the same time, the value f _t-1 (x ₀ + 16−v _x , y−v _y ) + f _t−1 (x ₀ + 17−v _x , y−v _y ) (in the case of equation (28)) ), F _t-1 (x ₀ −v _x , y−v _y ) + f _t−1 (x ₀ + 1−v _x , y−v _y ) (in the case of equation (29)), f _t−1 (x ₀ + 16−v _x , y−v _y ) + f _t−1 (x ₀ + 16−v _x , y + 1−v _y ), f _t−1 (x ₀ −v _x , y−v _y ) + f _t−1 ( x ₀ −v _x , y + 1−v _y ) (in the case of equation (31)), Φ (x ₀ + 16−v _x , y−v _y , t−1), Φ (x ₀ −v _x , y−v _y , t−1) (in the case of equation (33)) (y ₀ ≦ y ≦ y ₀ +15) is written in the partial reference pixel value sum storage unit 316.

  The prediction error lower limit determination unit 306 includes a reference pixel value sum difference value read from the reference pixel value sum difference value storage unit 305, a correction value difference value read from the correction value difference value storage unit 307, and a lower limit value storage unit 308. The lower limit value of the prediction error with respect to the motion vector before update read from is input, the lower limit value of the prediction error of the motion vector is calculated, and the calculated lower limit value is written in the lower limit value storage unit 308. The specific calculation of the lower limit value follows Formula (25).

  The correction value difference value calculation unit 315 receives the partial reference pixel value sum read from the partial reference pixel value sum storage unit 316, calculates a correction value difference value for the rounding error for each decimal pixel position, and stores the correction value difference value storage. Processing to write to the unit 307 is performed. More specifically, the difference value is obtained by Expression (30), Expression (32), and Expression (34).

  The motion vector control unit 314 to the initial motion vector prediction error calculation unit 301 and the reference pixel value sum difference value determination unit 304 respectively move from the initial motion vector prediction error calculation unit 101 and the reference pixel value sum determination unit 104 described with reference to FIG. Processing similar to that of the vector control unit 114 is performed.

In the case of the “fourth embodiment”:
FIG. 13 shows an apparatus configuration diagram according to the fourth embodiment of the present invention.

  The initial motion vector prediction error calculation unit 401 to the motion vector control unit 414 respectively perform the same processing as the initial motion vector prediction error calculation unit 301 to the motion vector control unit 314 in FIG.

  The correction value difference value calculation unit 415 receives the value read from the lookup table storage unit 416 as an input, calculates the difference value of the correction value, and writes it to the correction value difference value storage unit 407. The specific calculation of the correction value follows Formula (36), Formula (38), and Formula (40).

The lookup table storage unit 416 stores the values of difference correction value lookup tables to be referred to when calculating the difference value of correction values ^ r _v (x ₀ , y ₀ , v _x , v _y ), ^ r _h (x ₀ , y ₀ , v _x , v _y ), ^ r _d (x ₀ , y ₀ , v _x , v _y ) are stored in advance.

  Although the example of the 1/2 pixel accuracy MC has been described, it is apparent from the above description that the 1/2 pixel accuracy MC can be easily extended to the 1 / m (m> 2) pixel accuracy MC.

  The process of estimating and encoding the above motion vector can be realized by a computer and a software program. The program can be recorded on a computer-readable recording medium or provided via a network. Is possible.

It is a figure which shows the reference pixel in an interpolation process. It is a figure explaining calculation of the lower limit which paid its attention to the difference part of a reference pixel. It is a figure explaining calculation of the lower limit which paid its attention to the difference part of a reference pixel. It is a figure explaining calculation of the lower limit which paid its attention to the difference part of a reference pixel. It is a figure which shows the flow of the encoding process which concerns on the Example of this invention. It is a figure which shows the flow (the 1) of a lower limit calculation process. It is a figure which shows the flow (the 2) of a lower limit calculation process. It is a figure which shows the flow (the 3) of a lower limit calculation process. It is a figure which shows the flow (the 4) of a lower limit calculation process. It is a figure which shows the apparatus structure (the 1) which concerns on the Example of this invention. It is a figure which shows the apparatus structure (the 2) which concerns on the Example of this invention. It is a figure which shows the apparatus structure (the 3) which concerns on the Example of this invention. It is a figure which shows the apparatus structure (the 4) which concerns on the Example of this invention.

Explanation of symbols

101, 201, 301, 401 Initial motion vector prediction error calculation unit 102, 202 Predicted pixel value sum determination unit 103, 203 Predicted pixel value sum storage unit 104, 204 Reference pixel value sum determination unit 304, 404 Reference pixel value sum Difference value determination unit 105, 205 Reference pixel value sum storage unit 305, 405 Reference pixel value sum difference value storage unit 106, 206, 306, 406 Prediction error lower limit value determination unit 107, 207 Correction value storage unit 307, 407 Correction value difference Value storage unit 108, 208, 308, 408 Lower limit storage unit 109, 209, 309, 409 Pruning determination unit 110, 210, 310, 410 Prediction error calculation unit 111, 211, 311, 411 Optimal motion vector determination unit 112, 212, 312, 412 provisional minimum prediction error storage unit 113, 213, 313, 413 provisional optimum Motion vector storage unit 114, 214, 314, 414 Motion vector control unit 115, 215 Correction value calculation unit 315, 415 Correction value difference value calculation unit 116, 316 Partial reference pixel value sum storage unit 216, 416 Look-up table storage unit SW1 , SW2 switch

Claims (8)

A motion vector estimation method in an image coding system that performs inter-frame prediction using decimal pixel precision motion compensation,
Based on the motion vector and the reference pixel, a roundoff error of the reference pixel value sum accompanying interpolation processing with decimal pixel precision is calculated, and after motion compensation determined from the predicted pixel value sum, the reference pixel value sum, and the rounding error A process of calculating a lower limit for inter-frame prediction error;
It performs pruning motion vector search using the calculated lower limit, a motion vector that minimizes the prediction error between frames possess a process of searching in the sub-pixel accuracy,
When calculating the lower limit value, a rounding error is stored in advance in a lookup table in accordance with the value of the lower bits of the reference pixel group, and the lower limit value is calculated using the rounding error determined by referring to the lookup table A motion vector estimation method characterized by: The motion vector estimation method according to claim 1 ,
When the rounding error is stored in a lookup table, the motion vector estimation method is characterized in that the rounding error is stored in an individual lookup table according to a decimal pixel position to be interpolated. A motion vector estimation method in an image coding system that performs inter-frame prediction using decimal pixel precision motion compensation,
Based on the motion vector and the reference pixel, a roundoff error of the reference pixel value sum accompanying interpolation processing with decimal pixel accuracy is calculated, and after motion compensation determined from the predicted pixel value sum, the reference pixel value sum, and the rounding error A process of calculating a lower limit for inter-frame prediction error;
Pruning a motion vector search using the calculated lower limit, and searching for a motion vector that minimizes an inter-frame prediction error with decimal pixel precision,
When calculating the lower limit value,
From the difference between the reference areas indicated by the two motion vectors, the first motion vector for which the lower limit value of the prediction error has already been calculated and the second motion vector for which the lower limit value of the prediction error will be calculated will be used. Calculate the difference value of the lower limit of the prediction error of the reference area pointed to by the two motion vectors,
A motion vector estimation method, comprising: calculating a lower limit value of a prediction error for the second motion vector based on a lower limit value of a prediction error of the first motion vector. The motion vector estimation method according to claim 3 ,
When calculating the lower limit value,
The rounding error for the difference portion of the reference area pointed to by the two motion vectors is stored in advance in a lookup table according to the value of the lower bits of the reference pixel group, and the rounding error for the difference portion is referred to by referring to the lookup table. A motion vector estimation method comprising: determining and calculating a lower limit value of a prediction error for the second motion vector based on a lower limit value of a prediction error for the first motion vector. A motion vector estimation device in an image coding system that performs inter-frame prediction using decimal pixel precision motion compensation,
Based on the motion vector and the reference pixel, a roundoff error of the reference pixel value sum accompanying interpolation processing with decimal pixel accuracy is calculated, and after motion compensation determined from the predicted pixel value sum, the reference pixel value sum, and the rounding error Means for calculating a lower limit for inter-frame prediction error;
E Bei and means for searching performs pruning motion vector search using the calculated lower limit, a motion vector that minimizes the prediction error between frames in sub-pixel accuracy,
The means for calculating the lower limit value stores a rounding error in a lookup table in advance according to the value of the lower bits of the reference pixel group, and calculates the lower limit value using the rounding error determined by referring to the lookup table. A motion vector estimation apparatus characterized by that. A motion vector estimation device in an image coding system that performs inter-frame prediction using decimal pixel precision motion compensation,
Based on the motion vector and the reference pixel, a roundoff error of the reference pixel value sum accompanying interpolation processing with decimal pixel accuracy is calculated, and after motion compensation determined from the predicted pixel value sum, the reference pixel value sum, and the rounding error Means for calculating a lower limit for inter-frame prediction error;
Means for pruning motion vector search using the calculated lower limit, and for searching for a motion vector that minimizes inter-frame prediction error with decimal pixel accuracy,
The means for calculating the lower limit value is:
From the difference between the reference areas indicated by the two motion vectors, the first motion vector for which the lower limit value of the prediction error has already been calculated and the second motion vector for which the lower limit value of the prediction error will be calculated will be used. Calculate the difference value of the lower limit of the prediction error of the reference area pointed to by the two motion vectors,
Based on the lower limit value of the prediction error of the first motion vector, the lower limit value of the prediction error for the second motion vector is calculated.
A motion vector estimation apparatus characterized by that. A motion vector estimation program for causing a computer to execute the motion vector estimation method according to any one of claims 1 to 4. A computer-readable recording medium in which a motion vector estimation program for causing a computer to execute the motion vector estimation method according to any one of claims 1 to 4 is recorded.

Images