CN1750659A - Method for forming interpolation image memory organization and fractional pixel and predicating error index calculation - Google Patents

Abstract

The present invention relates to ^fractional pixel precision motion prediction technology in video compression coding, in order to solve the problem of inconvenient reading, low efficiency, etc. Problem, the present invention proposes a memory organization method for efficiently storing images according to the characteristics of pixels. When performing 1/2 ⁿ pixel precision motion prediction, according to the 2 ⁿ times interpolation image to be generated, the pixels in it are divided into integer positions Subsets, 1/2 ^1- position subsets, 1/2 ^2- position subsets, ..., and 1/2 ⁿ -position subsets, the final classification divides 2 ²ⁿ sub-images with the same size as the original image; then each sub-image Images form a contiguous memory area and are stored in memory. Based on this method of memory organization, the present invention also provides a method for filtering and interpolating to generate the interpolated image and a cost function ( SAD) method.

Description

Interpolation Image Memory Organization, Fractional Pixel Generation and Calculation Method of Prediction Error Index

technical field

The present invention relates to a fractional pixel precision motion prediction algorithm in video compression coding, more specifically, to a method for organizing interpolation image memory for fractional pixel precision motion prediction in video compression coding, and based on the interpolation image memory organization method to generate 4 A method for doubling each fractional pixel of an interpolated image, and a method for quickly calculating the prediction error index SAD based on these two methods.

Background technique

At present, it is the mainstream video compression coding standard in the industry, whether it is the international H.263, H.263+, H.264, and MPEG-4, or the domestic AVS (Advanced Audio-Video System, my country's advanced Audio and video coding systems) are based on a common framework, namely: image block + motion prediction + residual image DCT transform (also called integer transform, Hadarmard transform) + quantization + entropy coding. Among them, the correlation between the front and back frames of the moving image is used to predict the corresponding area in the moving frame through the area in the previous frame, so as to obtain the residual image and perform quantization and entropy coding, making full use of the moving image frame The statistical correlation between them is used to eliminate redundancy and achieve the purpose of data compression. Therefore, motion prediction is the core part of this kind of common frame-based video compression coding standard, and it is the most important factor affecting the overall compression efficiency.

The general process of motion prediction is as follows: for a given region (such as MB) in the current video frame, search in the reference frame (the previous frame, or the first k frames in the case of multiple reference frames) based on some error criterion best matching area. The change of the geometric position of the predicted area relative to the reference area can be represented by a two-dimensional vector, which is called a motion vector or a displacement vector. This process of searching for the optimal motion vector based on a certain error criterion is called motion estimation and is part of the overall motion prediction. The efficiency of motion prediction depends on the residual image between the predicted area and the predicted area, the smaller the residual, the higher the efficiency. Further, the efficiency of motion prediction actually depends on the accuracy of motion estimation, and the prediction accuracy directly depends on the motion vector.

The images in digital video are the results of discrete sampling and digitization of analog video in time and space, sampling in time to form discrete frames, and sampling in space to form individual pixels in the frame. In a frame, pixels are obtained by sampling a spatially continuous analog image at a certain sampling interval. So the distance between two adjacent pixels is the sampling interval. In order to represent the motion vector more accurately, the concept of fractional sample position (Fractional Sample Position) motion prediction needs to be introduced. Using fractional sampling positions, it can be imagined that there are fractional position pixels between two adjacent integer pixels, such as 1/2 pixel (distance from integer pixel is 1/2 sampling interval), 1/4 pixel (distance from integer pixel distance is 1/4 sampling interval), 1/8 pixel (1/8 sampling interval from integer pixel distance), etc. Facts have proved that after using fractional sampling position motion prediction, the efficiency of video compression coding can be improved a lot. For example, after using 1/4 pixel precision motion prediction, the PSNR (Peak Signal to Noise Ratio) of general compressed video can be improved. 2dB. Currently, H.263 and H.263+ use 1/2 pixel precision motion prediction, H.264 uses 1/4 pixel precision motion prediction, and domestic AVS uses 1/4 pixel precision motion prediction.

The general process of fractional sampling position motion prediction is as follows: first, use a certain integer pixel motion estimation algorithm, such as full search, 3-step method, new 3-step method, 4-step method, etc., to obtain the optimal integer pixel motion vector; Perform 1/2 pixel motion estimation around this integer pixel motion vector position to find the optimal 1/2 pixel motion vector position; if 1/4 pixel motion estimation is required, then center on this optimal 1/2 pixel position, 1/4 pixel motion estimation is performed around; also, after obtaining the optimal 1/4 pixel motion vector position, 1/8 pixel motion estimation can be performed.

Take the 1/4 pixel precision motion prediction standard implementation method specified in H.264/AVC as an example, as shown in Figure 1, the shaded circle in the figure is the current macroblock position, the unshaded circle is the integer pixel position, and the triangle is the 1/2 pixel position, and the small black dot is the 1/4 pixel position. The arrow in the figure indicates the direction of the search path when performing motion search. The motion vector is a vector composed of the difference between the current macroblock and its reference macroblock in the x and y directions, such as [2, -3], etc.; in the H.264/AVC standard, 1/4 pixel precision The search process for motion prediction can be divided into three steps:

1) Use a certain motion estimation method to find out the best matching position of integer pixels;

2) Find the best matching position of 1/2 pixel from the best matching position of integer pixel and its surrounding 8 1/2 pixel positions;

3) Find the 1/4 pixel best matching position from the 1/2 pixel best matching position and the 8 1/4 pixel positions around it.

In the above process, the matching search of the integer pixel position takes the locally decoded and reconstructed image of a previous frame as the reference image. The matching search of the 1/2 pixel position and the 1/4 pixel position needs to use the interpolated image of the locally decoded reconstructed image as a reference image, and the width and height of this reference image are 4 times that of the original image.

The structure of the 4x reference image is shown in Figure 2. The pixels in it are divided into the following categories:

1) Integer pixels: those pixels whose row and column coordinates are integer multiples of the sampling interval, such as the shaded circle pixels A, B, C, D, E, F, G, H, I, J, K in Figure 2 , L and so on.

2) 1/2 pixel: that is, at least one of the row and column coordinates has the form of (k+1/2)d or (k-1/2)d, but neither row nor column coordinates have (k+1/4 )d or those pixels of the form (k-1/4)d, where k is an integer and d is the sampling interval. As shown in Figure 2, each 1/2 pixel is divided into two subclasses:

A. Full 1/2 pixel: that is, the row and column coordinates all have the form of (k+1/2)d or (k-1/2)d, such as pixels j, gg, hh and so on.

B. Half 1/2 pixel: that is, only one of the row and column coordinates has the form of (k+1/2)d or (k-1/2)d, such as pixels b, h, m, s, aa, bb, cc, dd, ee, ff, etc.

3) 1/4 pixel: that is, those pixels in which at least one of the row and column coordinates has the form of (k+1/4)d or (k-1/4)d, where k is an integer, and d is the sampling interval. Unshaded circle pixels a, c, d, e, f, g, i, k, etc. in Figure 2.

Generation of the 4x reference image is done using a multi-stage interpolation process. Divided into the following steps:

1) 1/2 pixels are generated by interpolation from integer pixels, wherein the interpolation filter used is a 6-order FIR (Finite Impulse Response finite impulse response) filter, and its weight vector is w=[1,-5,20, 20, -5, 1] ^T . The process is as follows:

A. Half 1/2 pixels are generated by interpolation from integer pixels, taking pixels b and h as examples:

b ₁ =(E-5*F+20*G+20*H-5*I+J), generating an intermediate value b ₁ ,

b=Clip((b ₁ +16)>>5), Offset, Normalize, Clip.

Among them, the offset is to add a number (offset, which can be positive or negative); normalization refers to dividing a variable by a positive number so that the absolute value of the quotient is always no greater than 1 within the value range of the variable ;Cut means that for a variable that exceeds a certain range, force its value to be within this range. For example, the range of the variable x is [0, 18]. When x=20, if it exceeds this range, then x will be clipped to x=18.

Because the sum of the absolute values of the weights of the filter is 32, the normalization is divided by 32 and implemented by shifting right by 5 bits. The clipping function Clip adjusts the values that are not in the range of [0, 255] to the range of [0, 255] by clipping. In the same way, h can be obtained:

h ₁ ＝(A-5*C+20*G+20*M-5*R+T)

h=Clip((h ₁ +16)>>5)

B. Generate full 1/2 pixels from half 1/2 pixels through interpolation. The filter used for interpolation is still the above 6th-order FIR filter. Take pixel j as an example:

j ₁ =(bb-5gg+20*h ₁ +20*m ₁ -5*kk+cc), generating the intermediate value j ₁

j=Clip((j ₁ +512)>>10)

After the above two sub-steps, all 1/2 pixels are generated.

2) Generate 1/4 pixels by interpolation from integer pixels and 1/2 pixels. 1/4 pixels are located between two integer pixels or 1/2 pixels (horizontal direction, vertical direction, diagonal direction), so the arithmetic mean of two adjacent integer pixels or 1/2 pixels can be used method to obtain. The specific calculation formula is as follows:

a=(D+b+1)>>1

c=(E+b+1)>>1

d=(D+h+1)>>1

n=(H+h+1)>>1

The above is the average value in the horizontal direction. For the case of averaging in the diagonal direction, the calculation method is as follows:

e=(b+h+1)>>1

g=(b+m+1)>>1

In the prior art, the 4x interpolation images are stored in the memory in a continuous manner in a natural order, that is, in the mode shown in FIG. 2 . However, storing 4x interpolated images in their natural order is not the most reasonable mode. In the process of interpolating to generate a 4x image, the integer pixels (which already exist) are first generated, then 1/2 pixels are generated, and finally 1/4 pixels are generated. In the process of generating 1/2 pixels, if the DSP (Digital Signal Processor, digital signal processing chip) acceleration processing technology based on SIMD (Single Instruction Multiple Data, single instruction multiple data) is used, the SIMD instruction needs to read the integer pixels as a whole; Also in the process of generating 1/4 pixels, it is necessary to read 1/2 pixels and integer pixels as a whole. The image memory is organized in such a natural order, and it is impossible to read all kinds of pixels in one block, because the current storage method is in accordance with the natural order and does not classify the pixels. For example, starting from the pixel in the upper left corner of the 4-fold interpolated image, it is stored sequentially. This sequence is: integer, 1/4, 1/2, 1/4, integer, 1/4, 1/2, 1/4, ..., after the end of the first line, enter the second line, repeat this sequentially until the last line. In this case, in any memory area, the pixels are not arranged consecutively according to the class. For example, any two integer pixels appear discontinuously, and any two 1/2 pixels appear discontinuously. Not to mention a whole block of pixels of the same kind. Therefore, if all integer pixels are to be read, they must be read at certain intervals (every 3 numbers) in the memory, which is very inefficient.

In addition, in the process of motion estimation after the 4 times interpolation image is generated, in the integer pixel precision motion prediction, it is only necessary to compare the predicted macroblock with the integer position subset in the 4 times image, and find the SAD (Summed Absolute Difference , and the absolute difference). Similarly, when performing 1/2-pixel precision motion prediction, it only needs to be compared with the part of the 1/2 position subset in the 4-fold interpolated image; 1/4-pixel precision motion prediction needs to compare only the 1/4 position subset part. Therefore, if SIMD-like DSP acceleration technology is used, each comparison and calculation of SAD only needs to read a certain type of pixels with common attributes in one block. However, in the natural sequential memory organization of images, these pixels with common attributes are not stored consecutively, which is not convenient for whole block reading.

Contents of the invention

Aiming at the above-mentioned defects of the prior art, the present invention aims to solve the problem in the existing video compression coding technology that the interpolation images are stored in the memory according to the natural order and cannot read all kinds of pixels as a whole, and provides a new The image memory organization method enables 1/2 pixel and 1/4 pixel precision motion prediction to make full use of SIMD-like DSP acceleration algorithms to improve computing efficiency.

In order to solve the above-mentioned technical problems, the present invention provides a kind of interpolation image memory organization method that is used for fractional pixel precision motion prediction, when carrying out 1/2 ⁿ pixel precision motion prediction (wherein n is a natural number), organize the interpolation image according to the following steps Memory:

(1) According to the 2 ⁿ times interpolation image to be generated, divide the pixels into integer position subsets, 1/2 ¹ position subsets, 1/2 ² position subsets, ..., and 1/2 ⁿ position subsets, The respective subsets include all integer pixels, all 1/2 pixels, all 1/4 pixels, ..., and all 1/2 ⁿ pixels;

(2) forming an integer pixel sub-image identical in size to the original image with all the integer pixels in the integer position subset;

According to the vertical, horizontal, and diagonal positional relationship between each 1/2 pixel and adjacent integer pixels, all the 1/2 pixels in the 1/2 position subset are further divided into 3 smaller subsets , forming three 1/2 pixel sub-images with the same size as the original image in one-to-one correspondence;

According to the vertical, horizontal, and diagonal positional relationship and distance relationship between each 1/4 pixel and adjacent integer pixels and 1/2 pixels, all 1/4 pixels in the 1/4 position subset Further divided into 12 smaller subsets to form 12 1/4 pixel sub-images with the same size as the original image in one-to-one correspondence;

And so on, according to the vertical, horizontal, and diagonal positions between each 1/2 ⁿ pixel and adjacent integer pixels, 1/2 pixels, 1/4 pixels, ..., 1/2 ^(n-1) pixels Classify the relationship and distance relationship, and further divide all 1/2 ⁿ pixels in the 1/2 ⁿ subset into (2 ²ⁿ -2 ^2(n-1) ) smaller subsets to form ( 2 ²ⁿ -2 ^2(n-1) ) 1/2 ⁿ -pixel sub-images of the same size as the original image;

(3) forming a continuous memory area of each sub-image and storing it in the memory;

(4) Perform zero initialization processing on the stored sub-images except the integer-pixel sub-images.

In the step (3) of the interpolation image memory organization method of the present invention, each sub-image can be formed into a continuous memory area and stored in the memory according to any one of the following three splicing methods:

A. 2 ²ⁿ ×1 splicing, that is, vertical splicing;

B. 2 ⁿ × 2 ⁿ splicing, that is, square splicing;

C. 1×2 ²ⁿ splicing, that is, horizontal strip splicing.

For 1/4 pixel precision motion prediction, the present invention also provides a method for generating each fractional pixel of a 4-fold interpolation image according to the above-mentioned interpolation image memory organization method and using the SIMD acceleration technology provided by DSP, which includes the following steps:

(1) Using the integer-pixel sub-image SP ₀ , generate 1/2-pixel sub-images SP ₄ , SP ₈ through filtering and interpolation.

(2) Using the 1/2-pixel sub-image SP ₅ , generate a 1/2-pixel sub-image SP ₁₂ through filtering and interpolation.

(3) Using the integer-pixel sub-image SP ₀ and the 1/2-pixel sub-images SP ₄ , SP ₈ , SP ₁₂ , generate 1/4-pixel sub-images SP ₁ , SP ₅ , SP ₉ , SP ₁₃ through horizontal filtering and interpolation.

(4) Using the whole-pixel sub-image SP ₀ and the 1/2-pixel sub-images SP ₄ , SP ₈ , SP ₁₂ to generate 1/4-pixel sub-images SP ₂ SP ₆ , SP ₁₀ , SP ₁₄ through vertical filtering and interpolation.

(5) Utilize the whole-pixel sub-image SP ₀ and 1/2-pixel sub-image SP ₄ , SP ₈ , SP ₁₂ to generate 1/4-pixel sub-image SP 3 , SP 3 , SP ₁₂ through +45° and -45° diagonal direction filter interpolation SP ₇ , SP ₁₁ , SP ₁₅ .

For 1/4 pixel precision motion prediction, the present invention also provides a method for generating each fractional pixel of a 4-fold interpolation image according to the above method, and a method for quickly calculating the prediction error index SAD by using the SIMD acceleration technology provided by DSP, wherein the following steps Calculate the prediction error index SAD between the current macroblock MB ₀ and the reference macroblock MB _r at a certain position in the reference frame during the motion estimation process:

(1) When performing motion prediction with integer pixel precision, according to the position of MB _r , the data of MB _r is read from the sub-image SP ₀ as a whole, and then the SAD is calculated.

(2) When performing 1/2 pixel precision motion prediction, according to the position of MB _r , read the data of MB _r from one of the sub-images SP ₄ , SP ₈ , SP ₁₂ as a whole, and then calculate the SAD.

(3) When performing 1/4 pixel precision motion prediction, according to the position of MB _r , from sub-images SP ₁ , SP ₂ , SP ₃ , SP ₅ , SP ₇ , SP ₇ , SP ₉ , SP ₁₀ , SP ₁₁ , One of SP ₁₃ , SP ₁₄ , and SP ₁₅ reads the data of MB _r as a whole, and then calculates SAD.

The method of the invention overcomes the problem of inconvenient reading caused by storing the existing 4-fold interpolation images in the memory according to the natural order. The 1/2 pixel and 1/4 pixel precision motion prediction can make full use of SIMD DSP acceleration algorithm to improve efficiency. Among them, each pixel in the 4-fold interpolation image is divided into subsets according to attributes, and each subset is further divided into several sub-images, so that each sub-image can be read as a whole block of data in SIMD-like instruction operations. By adopting the method of the present invention, in international standards such as H.263/H.263+, H.264, MPEG-4 and AVS 1.0 national standard, for 1/2 pixel and 1/4 pixel precision motion prediction process Interpolation generates 4 times interpolation image operation and motion estimation operation, which can effectively accelerate. Especially when using the SIMD-like DSP acceleration mechanism. Therefore, under the premise that other conditions remain unchanged, the frame rate of video encoding and decoding can be increased. Improve the performance of video communication equipment such as video conferencing or videophone, or reduce the cost of products by using DSP with lower processing power to achieve the same performance.

Description of drawings

The present invention will be further described below in conjunction with accompanying drawing and embodiment, in the accompanying drawing:

Fig. 1 is the search process of 1/4 pixel precision motion prediction in the existing H.264/AVC standard;

Figure 2 is the relative geometric positional relationship of integer pixels, 1/2 pixels and 1/4 pixels in the 4 times interpolation image;

Fig. 3 is that in the present invention, various pixels in the 4 times interpolation image are classified and numbered according to attributes;

Fig. 4a, Fig. 4b, Fig. 4c are original image, 4 times interpolation image under traditional storage method and 4 times interpolation image under storage method of the present invention respectively;

Fig. 5a, Fig. 5b and Fig. 5c are respectively the splicing and storing methods of 16 sub-images in the 4 times interpolation image P _4×4 obtained in the present invention.

Detailed ways

The present invention will be described below by taking 1/4 pixel precision motion prediction as an example.

For 1/4 pixel precision motion prediction, the key of the method of the present invention is a kind of reorganization and stitching method for 4 times (that is, the interpolation image whose width and height are 4 times of the original image) interpolation reference image content, thereby ensuring its stored contiguously in memory. After using the method of the present invention, when forming a 4-fold interpolation reference image by interpolation and performing 1/2 pixel and 1/4 pixel motion estimation, the proximity of successively accessed pixel data in the storage space can be fully utilized to significantly improve Computational efficiency. When using the SIMD acceleration function provided by DSP, such as Intel CPU's MMX, SSE, etc. for accelerated processing, the performance improvement is particularly obvious, because this data space proximity is very suitable for SIMD. This method is mainly aimed at the efficient realization of 1/4 pixel precision motion prediction required in H.264/AVC, but its principle can be used for 1/2 pixel precision motion prediction in H.263/H.263+, MPEG- 1/4 pixel precision motion prediction in 4, and 1/4 pixel precision motion prediction in AVS standard.

Among them, according to the 4 times interpolation image to be generated, the pixels in it are divided into three subsets, as follows:

Integer position subset _SIP ={all integer pixels}, in Fig. 3, the pixels of this subset are represented by solid large circles;

1/2 position subset S _HP ={all 1/2 pixels}, the pixels of this subset are represented by solid squares in Fig. 3;

The 1/4 position subset S _QP ={all 1/4 pixels}, and the pixels of this subset are represented by hollow squares in FIG. 3 .

It can be seen from the dotted line box in Figure 3 that for the integer pixel A (numbered 0) in the upper right corner, there will be three 1/2 pixels (numbered 4, 8, 12) and 12 1/2 pixels 4 pixels (numbered 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15). Therefore, in the present invention, all the pixels in the integer position subset _SIP are used to form an integer-pixel sub-image SP ₀ , and the size of the sub-image is the same as that of the original image.

Then classify according to the vertical, horizontal, and diagonal positional relationship between each 1/2 pixel and adjacent integer pixels, and further divide all 1/2 pixels in the 1/2 position subset S _HP into 3 subsets, each A subset constitutes a 1/2 pixel sub-image with the same size as the original image, and constitutes three 1/2 pixel sub-images SP ₄ , SP ₈ , SP ₁₂ in total;

Then classify according to the vertical, horizontal, and diagonal positional relationship and distance relationship between each 1/4 pixel and adjacent integer pixels and 1/2 pixels (for 1/4 pixel classification, distance should be considered), and 1/4 All 1/4 pixels in the position subset S _HP are further divided into 12 subsets, and each subset constitutes a 1/4 pixel sub-image with the same size as the original image, and a total of 12 1/4-pixel sub-images SP ₁ , SP ₂ , SP ₃ , SP ₅ , SP ₆ , SP ₇ , SP ₉ , SP ₁₀ , SP ₁₁ , SP ₁₃ , SP ₁₄ , SP ₁₅ ;

Therefore, the 4 times interpolated image can finally be expressed as:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}\mathrm{<span\; class="notranslate">\; x</span>}\mathrm{<span\; class="notranslate">\; 4</span>}}<span\; class="notranslate">\; =</span>\left[\begin{array}{c}{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="0"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="4"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 4</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="5"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 5</span>}}\\ {\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="3"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="6"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 6</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="7"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 7</span>}}\\ {\mathrm{<span\; class="notranslate">\; <figure-callout\; id="8"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 8</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="9"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 9</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="12"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 12</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="13"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 13</span>}}\\ {\mathrm{<span\; class="notranslate">\; <figure-callout\; id="10"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 10</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="11"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 11</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="14"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 14</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="15"\; label="SP"\; filenames="A200410076759.400221.png"\; state="\{\{state\}\}">SP</figure-callout></span>}}_{\mathrm{<span\; class="notranslate">\; 15</span>}}\end{array}\right]$

After the per-pixel reorganization above for P _4×4 , 16 sub-images of the same size as the original image are generated. There are many ways to store these sub-images in the memory. The easiest way is to store the 16 images separately. However, this storage method will lead to skip reading data when calculating the corresponding SAD value of each position, such as calculating the best integer pixel during the 1/2 pixel search process. When calculating the SAD value corresponding to the 1/2 pixel position directly above the position, the data needs to be read from the 8th image, but when calculating the SAD value corresponding to the upper left and upper right 1/2 pixel positions, it is necessary to read the data from the 12th image Reading data in the image, if the 16 images are stored independently, the storage locations of the 8th image and the 12th image in the memory will be far apart, and reciprocating access to these two locations will inevitably affect the access speed. Therefore, a more scientific method is splicing storage, that is, splicing 16 images into one large image and storing it in memory. For this reason, the present invention proposes three splicing methods,

The so-called memory splicing is mainly used to improve the reading and writing efficiency of those DSPs that have the requirements for reading and writing data in the memory according to the integer multiple of 2 byte boundaries. If a data block to be read or written is not aligned according to the boundary of a certain number of bytes (such as 32, 64 bytes), it is necessary to read or write some more data (usually padding with zeros) to make up the boundary alignment, which will naturally affect efficiency.

For 1/2 pixel and 1/4 pixel precision motion prediction, the present invention can provide three splicing methods satisfying boundary alignment. Fig. 5a, Fig. 5b and Fig. 5c show three memory splicing methods applicable to the case of 1/4 pixel precision motion prediction. Each block in this figure represents a sub-image. They are:

A. 16×1 splicing, that is, 16 sub-images are spliced into a vertical bar;

B, 4 × 4 splicing, (that is, 16 sub-images are spliced into a square);

C. 1×16 splicing, that is, 16 sub-images are spliced into one (horizontal bar).

For 1/2 pixel precision motion prediction, there are also three splicing strategies:

A. 4×1 splicing (vertical bars);

B. 2×2 splicing (square);

C, 1×4 splicing (horizontal bars).

For 1/8 pixel and even larger n, these three stitching strategies are applicable, but there may be more strategies. So for a general n, the three splicing strategies are:

A. 2 ²ⁿ ×1 splicing, that is (vertical strip splicing);

B. 2 ⁿ × 2 ⁿ splicing, that is, square splicing;

C. 1×2 ²ⁿ splicing, that is, horizontal strip splicing.

Finally, zero initialization processing is performed on the stored sub-images except for the integer-pixel sub-images.

The process of generating a 4-fold interpolation image P4×4 from the original image can be completed by using SIMD DSP acceleration instructions because of the convenience of the P4×4 structure. The convolution operation and shift operation of the filter design can be integrated in units of sub-images block complete. The reason for adopting the numbering method shown in Figure 3 is to be consistent with existing H.264 and other standards)

In motion estimation, the SAD operation can be accelerated by taking out a sub-matrix with the same size as the predicted macroblock from a certain sub-image with the help of SIMD instructions.

According to the above interpolation image memory organization method, the SIMD acceleration technology provided by DSP can be used to generate each fractional pixel of the 4 times interpolation image according to the following steps:

(1) Using the integer-pixel sub-image SP ₀ , generate 1/2-pixel sub-images SP ₄ , SP ₈ through filtering and interpolation.

(2) Using the 1/2 pixel sub-image SP ₄ , generate a 1/2 pixel sub-image SP ₁₂ through filtering and interpolation.

(3) Using the integer-pixel sub-image SP ₀ and the 1/2-pixel sub-images SP ₄ , SP ₈ , SP ₁₂ , generate 1/4-pixel sub-images SP ₁ , SP ₅ , SP ₉ , SP ₁₃ through horizontal filtering and interpolation.

(4) Using the whole-pixel sub-image SP ₀ and the 1/2-pixel sub-images SP ₄ , SP ₈ , SP ₁₂ to generate 1/4-pixel sub-images SP ₂ SP ₆ , SP ₁₀ , SP ₁₄ through vertical filtering and interpolation.

(5) Utilize the whole-pixel sub-image SP ₀ and 1/2-pixel sub-image SP ₄ , SP ₈ , SP ₁₂ to generate 1/4-pixel sub-image SP 3 , SP 3 , SP ₁₂ through +45° and -45° diagonal direction filter interpolation SP ₇ , SP ₁₁ , SP ₁₅ .

According to the above-mentioned interpolation image memory organization method and the method of generating each fractional pixel of the 4-times interpolation image, the SIMD acceleration technology provided by DSP can be used to calculate the current macroblock MB ₀ and a certain value in the reference frame during the motion estimation process according to the following steps: Prediction error index SAD between reference macroblocks MB _r of position:

(1) When performing motion prediction with integer pixel precision, according to the position of MB _r , the data of MB _r is read from the sub-image SP ₀ as a whole, and then the SAD is calculated.

(2) When performing 1/2 pixel precision motion prediction, according to the position of MB _r , read the data of MB _r from one of the sub-images SP ₄ , SP ₈ , SP ₁₂ as a whole, and then calculate the SAD.

(3) When performing 1/4 pixel precision motion prediction, according to the position of MB _r , from sub-images SP ₁ , SP ₂ , SP ₃ , SP ₅ , SP ₇ , SP ₇ , SP ₉ , SP ₁₀ , SP ₁₁ , One of SP ₁₃ , SP ₁₄ , and SP ₁₅ reads the data of MB _r as a whole, and then calculates SAD.

By adopting the present invention, in international standards such as H.263/H.263+, H.264, MPEG-4 and AVS 1.0 national standard, the interpolation generation in the motion prediction process of 1/2 pixel and 1/4 pixel precision can be 4 times interpolation image operation and motion estimation operation are effectively accelerated. Especially when using the SIMD-like DSP acceleration mechanism. Therefore, under the premise that other conditions remain unchanged, the frame rate of video encoding and decoding can be increased. Improve the performance of video communication equipment such as video conferencing or videophone, or reduce the cost of products by using DSP with lower processing power to achieve the same performance. Both of these methods can improve the market competitiveness of products. Effect of the present invention is remarkable, and following experimental data can illustrate effect of the present invention:

Experiment 1: Using the method of the present invention combined with MMX, SSE2 optimizes and accelerates the 1/4 pixel interpolation process. For the classic test image sequences Clair, News and Foreman, the results are shown in Table 1 below:

Table I Image sequence (6000 frames) no optimization MMX optimization SSE2 optimization Claire 33.88 seconds 7.81 seconds 7.55 seconds News 33.51 seconds 7.64 seconds 7.38 seconds Foreman 33.42 seconds 7.43 seconds 7.27 seconds

Experiment 2: Using the method of the present invention, the acceleration optimization of the entire 1/4 pixel precision motion prediction process is carried out for the classic test image sequences Clair, News and Foreman. The results are shown in Table 2 below, and the data in Table 2 can be completed per second Number of encoded frames:

Table II

The method of the present invention is directly applicable to video encoders and decoders following H.263/H.263+, H.264, MPEG-4 international standards and AVS domestic standards, and can realize 1/2 pixel and 1/4 pixel Precision Motion Prediction. It is also suitable for other video encoders and decoders that adopt 1/2 pixel and 1/4 pixel precision motion prediction to realize 1/2 pixel and 1/4 pixel precision motion prediction.

The method of the present invention is also suitable for realizing motion prediction with 1/8 pixel precision, and any motion prediction with 1/8 pixel precision must first perform motion prediction with 1/2 pixel precision and 1/4 pixel precision. Therefore, 1/2 pixel and 1/4 pixel precision motion prediction is a necessary component and premise of 1/8 pixel precision motion prediction. It is also applicable to the implementation of 1/8 pixel precision motion prediction in any other (not necessarily following a certain standard) video encoder and decoder implementation using 1/8 pixel precision motion prediction.

Attachment: Abbreviations and key terms used in this patent

Abbreviation English Chinese

AVC Audio-Video Coding Audio-Video Coding

AVS Advanced Audio-Video System (National) Advanced Audio-Video Coding System

dB deci-Bell deci-Bell

DSP Digital Signal Processor Digital Signal Processor

DV Displacement Vector Displacement Vector

MB Macroblock Macroblock

MV Motion Vector Motion Vector

MPEG Moving Picture Experts Group Moving Picture Experts Group (International Standards Organization)

PSNR Peak Signal-to Noise Ratio Peak Signal-to-Noise Ratio

SIMD Single Instruction Multiple Data Single Instruction Multiple Data

MMX MultiMedia Extension Multimedia Extension Instruction Set

SAD Sum of Absolute Differences Absolute difference

SSEStream SIMD Extension Single Instruction Multiple Data Extension Instruction Set

Claims (8)

1. An interpolation image memory organization method for fractional pixel precision motion prediction, characterized in that, when carrying out 1/2 ⁿ pixel precision motion prediction, wherein, n is a natural number, organize the memory of the interpolation image according to the following steps: (1) According to the 2 ⁿ times interpolation image to be generated, divide the pixels into integer position subsets, 1/2 ¹ position subsets, 1/2 ² position subsets, ..., and 1/2 ⁿ position subsets, The respective subsets include all integer pixels, all 1/2 pixels, all 1/4 pixels, ..., and all 1/2 ⁿ pixels; (2) forming an integer pixel sub-image identical in size to the original image with all the integer pixels in the integer position subset; According to the vertical, horizontal, and diagonal positional relationship between each 1/2 pixel and adjacent integer pixels, all the 1/2 pixels in the 1/2 position subset are further divided into 3 smaller subsets , forming three 1/2 pixel sub-images with the same size as the original image in one-to-one correspondence; According to the vertical, horizontal, and diagonal positional relationship and distance relationship between each 1/4 pixel and adjacent integer pixels and 1/2 pixels, all 1/4 pixels in the 1/4 position subset Further divided into 12 smaller subsets to form 12 1/4 pixel sub-images with the same size as the original image in one-to-one correspondence; And so on, according to the vertical, horizontal, and diagonal positions between each 1/2 ⁿ pixel and adjacent integer pixels, 1/2 pixels, 1/4 pixels, ..., 1/2 ^(n-1) pixels Classify the relationship and distance relationship, and further divide all 1/2 ⁿ pixels in the 1/2 ⁿ subset into (2 ²ⁿ -2 ^2(n-1) ) smaller subsets to form ( 2 ²ⁿ -2 ^2(n-1) ) 1/2 ⁿ -pixel sub-images of the same size as the original image; (3) forming a continuous memory area of each sub-image and storing it in the memory; (4) Perform zero initialization processing on the stored sub-images except the integer-pixel sub-images. 2. The interpolation image memory organization method according to claim 1, wherein the n is equal to 1, and the interpolation image memory is organized according to the following steps when performing motion prediction with 1/2 pixel precision: (1) According to the 2 times interpolation image to be generated, divide the pixels in it into an integer position subset and a 1/2 position subset, the integer position subset contains all integer pixels, and the 1/2 position subset contains all 1/2 pixel; (2) forming an integer pixel sub-image identical in size to the original image with all the integer pixels in the integer position subset; According to the vertical, horizontal, and diagonal positional relationship between each 1/2 pixel and adjacent integer pixels, all the 1/2 pixels in the 1/2 position subset are further divided into 3 smaller subsets , forming three 1/2 pixel sub-images with the same size as the original image in one-to-one correspondence; (3) forming a continuous memory area of each sub-image and storing it in the memory; (4) Perform zero-initialization processing on the three stored 1/2-pixel sub-images except the integer-pixel sub-image. 3. The interpolation image memory organization method according to claim 1, wherein the n is equal to 2, and the interpolation image memory is organized according to the following steps when performing motion prediction with 1/4 pixel precision: (1) According to the 4 times interpolation image to be generated, the pixels in it are divided into integer position subsets (S _HP ), 1/2 position subsets (S _HP ), and 1/4 position subsets (S _QP ), so The integer position subset (S _IP ) contains all integer pixels, the 1/2 position subset (S _HP ) contains all 1/2 pixels, and the 1/4 position subset (S _QP ) contains all 1/4 pixel; (2) form an integer pixel sub-image (SP ₀ ) with the same size as the original image with all the integer pixels in the integer position subset (S _IP ); According to the vertical, horizontal, and diagonal positional relationship between each 1/2 pixel and adjacent integer pixels, all 1/2 pixels in the 1/2 position subset (S _HP ) are further divided into 3 The smaller subsets form three sub-images (SP ₄ , SP ₈ , SP ₁₂ ) with the same size as the original image in one-to-one correspondence; According to the vertical, horizontal, and diagonal positional relationship and distance relationship between each 1/4 pixel and adjacent integer pixels and 1/2 pixels, all of the 1/4 position subsets (S _QP ) The 1/4 pixel is further divided into 12 smaller subsets to form 12 sub-images with the same size as the original image (SP ₁ , SP ₂ , SP ₃ , SP ₅ , SP ₆ , SP ₇ , SP ₉ , SP ₁₀ , SP ₁₁ , SP ₁₃ , SP ₁₄ , SP ₁₅ ); (3) forming a continuous memory area of each sub-image and storing it in the memory; (4) In addition to the integer-pixel sub-images, zero-initialize the stored 3 1/2-pixel sub-images and 12 1/4-pixel sub-images. 4. The interpolation image memory organization method according to claim 1, wherein the n is equal to 3, and the interpolation image memory is organized according to the following steps when performing motion prediction with 1/8 pixel precision: (1) According to the 8-fold interpolation image to be generated, the pixels in it are divided into integer position subsets, 1/2 position subsets, 1/4 position subsets, and 1/8 position subsets, and each subset is respectively Including all integer pixels, all 1/2 pixels, all 1/4 pixels, and all 1/8 pixels; (2) forming a sub-image with the same size as the original image with all the integer pixels in the subset of integer positions; According to the vertical, horizontal, and diagonal positional relationship between each 1/2 pixel and adjacent integer pixels, all the 1/2 pixels in the 1/2 position subset are further divided into 3 smaller subsets , forming three 1/2 pixel sub-images with the same size as the original image in one-to-one correspondence; According to the vertical, horizontal, and diagonal positional relationship and distance relationship between each 1/4 pixel and adjacent integer pixels and 1/2 pixels, all 1/4 pixels in the 1/4 position subset Further divided into 12 smaller subsets to form 12 1/4 pixel sub-images with the same size as the original image in one-to-one correspondence; According to the vertical, horizontal, and diagonal positional relationship and distance relationship between each 1/8 pixel and adjacent integer pixels, 1/2 pixels, and 1/4 pixels, all of the 1/8 subsets The 1/8 pixel is further divided into 48 subsets, forming 48 1/8 pixel sub-images with the same size as the original image in one-to-one correspondence; (3) forming a continuous memory area of each sub-image and storing it in the memory; (4) In addition to the integer-pixel sub-images, zero-initialize the stored 3 1/2-pixel sub-images, 12 1/4-pixel sub-images, and 48 1/8-pixel sub-images. 5. The interpolation image memory organization method according to claims 1-4, characterized in that in the step (3), the sub-images can be formed according to any one of the following three splicing methods A contiguous memory region is stored into memory: A. 2 ²ⁿ ×1 splicing, that is, vertical splicing; B. 2 ⁿ × 2 ⁿ splicing, that is, square splicing; C. 1×2 ²ⁿ splicing, that is, horizontal strip splicing. 6. The interpolation image memory organization method according to claim 5, characterized in that said n=2, and in said step (3), said The individual subimages form a contiguous memory region stored in memory: A. 16×1 splicing, that is, vertical splicing; B. 4×4 splicing, that is, square splicing; C. 1×16 splicing, that is, horizontal strip splicing. 7. According to the interpolation image memory organization method according to claim 6, the method for generating each fractional pixel of the 4-times interpolation image using the SIMD acceleration technology provided by the DSP, is characterized in that, comprising the following steps: (1) Using the integer-pixel sub-image SP ₀ , generate 1/2-pixel sub-images SP ₄ , SP ₈ through filtering and interpolation. (2) Using the 1/2 pixel sub-image SP ₄ , generate a 1/2 pixel sub-image SP ₁₂ through filtering and interpolation. (3) Using the integer-pixel sub-image SP ₀ and the 1/2-pixel sub-images SP ₄ , SP ₈ , SP ₁₂ , generate 1/4-pixel sub-images SP ₁ , SP ₅ , SP ₉ , SP ₁₃ through horizontal filtering and interpolation. (4) Using the whole-pixel sub-image SP ₀ and the 1/2-pixel sub-images SP ₄ , SP ₈ , SP ₁₂ to generate 1/4-pixel sub-images SP ₂ SP ₆ , SP ₁₀ , SP ₁₄ through vertical filtering and interpolation. (5) Utilize the whole-pixel sub-image SP ₀ and 1/2-pixel sub-image SP ₄ , SP ₈ , SP ₁₂ to generate 1/4-pixel sub-image SP 3 , SP 3 , SP ₁₂ through +45° and -45° diagonal direction filter interpolation SP ₇ , SP ₁₁ , SP ₁₅ . 8. According to the method for generating each fractional pixel of a 4-fold interpolation image according to claim 7, the method for quickly calculating the prediction error index SAD by using the SIMD acceleration technology provided by the DSP is characterized in that the current macroblock MB is calculated according to the following steps ₀ and the prediction error index SAD between the reference macroblock MB _r at a certain position in the reference frame during the motion estimation process: (1) When performing motion prediction with integer pixel precision, according to the position of MB _r , the data of MB _r is read from the sub-image SP ₀ as a whole, and then the SAD is calculated. (2) When performing 1/2 pixel precision motion prediction, according to the position of MB _r , read the data of MB _r from one of the sub-images SP ₄ , SP ₈ , SP ₁₂ as a whole, and then calculate the SAD. (3) When performing 1/4 pixel precision motion prediction, according to the position of MBr, from sub-images SP ₁ , SP ₂ , SP ₃ , SP ₅ , SP ₇ , SP ₇ , SP ₉ , SP ₁₀ , SP ₁₁ , SP _13. One of SP ₁₄ and SP ₁₅ reads the data of MB _r as a whole, and then calculates SAD.

Images