CN101166272B - Data storage method for difference compensation points - Google Patents

Abstract

The invention provides a data storage method of compensation point, which uses the temporary storage area in the high-speed buffer and the concept of storing overlapping record to store the calculated data of compensation point, thereby avoiding repeated calculation, reducing the system operation amount and reducing the times of reading integer point from the external memory to calculate the compensation point. In addition, the invention provides a data storage mode of the temporary storage area, and utilizes the concept of memory address rotation to store the data of the interpolation point beyond the boundary of the temporary storage area. The invention also stores the interpolation point data in a plurality of areas according to different combinations of the decimal part of the coordinate of the interpolation point, thereby saving the storage space of the temporary storage area and being convenient for searching the interpolation point data in the temporary storage area.

Description

Data storage method for making up shortfall points

technical field

The present invention relates to an interpolation calculation in a video encoding and decoding system, and in particular to a method for storing interpolation data in a video encoding and decoding system.

Background technique

In the current video encoding and decoding system, motion estimation (motion estimation) has the accuracy of 1/2, 1/4, 1/8 point, and this non-integer point does not exist in the external memory, there is an external memory for use Integer points calculated from . Therefore, in the video encoding and decoding system, regardless of motion estimation or motion compensation, as long as the motion vector of non-integer points is involved, the compensation point operation will be used.

For example, as shown in Figure 1, in the H.264 video system specification, the value of its 1/2 point pixel (pixel) is a finite impulse response filter (finiteimpulse response) using six sets of coefficients (six-tap). , referred to as FIR) calculated. In Figure 1, the white squares (such as A, B, C, D, etc.) represent integer point positions, while the squares containing lines (such as aa, bb, h, m, etc.) represent 1/2 point positions that need to be supplemented by point calculations . The value of the pixel at point b is an integer value for the value of the formula (E-5F+20G+20H-5I+J)/32. The value of the pixel at point h is an integer value for the value of the formula (A-5C+20G+20M-5R+T)/32. It can be seen from the above formula that calculating the value of the pixel at the 1/2 point requires 4 multiplication operations. Taking the common intermediate format (CIF for short) as the most common image format at present, each frame (frame) has 352*288 pixels, and the value of all 1/2 dot pixels in the CIF format needs to be calculated (703*575 -352*288 (integer point))*4=1,211,396 multiplication operations, about 1.2 million multiplication operations; about 50 million multiplication operations are required to calculate the values of all 1/8 point position pixels. Among them, the value of the 1/4 point position pixel can use the adder and shifter, so it is not included in the evaluation. In addition, in the CIF format, all 1/2 dot positions have 703*575-352*288 (integer points)=302,846 pixels, which means that it takes about 296Kbytes of memory space to store the values of all 1/2 dot position pixels; The values of all 1/8 dot pixels require about 6Mbytes of memory space. Since the supplementary point is deduced from the integer points stored in the external memory, if the bandwidth of the external memory is 16 bits, in order to calculate the value of the 1/2, 1/4, and 1/8 point pixel, each needs to capture the entire The integer point data of the screen, that is, to capture 396*256*1.5/16=76032 times.

It can be seen from the above description that in the video encoding and decoding system, the amount of computation for calculating the supplementary points and the required memory space for storing the supplementary points are extremely costly, and the external memory for storing integer points needs to be read multiple times.

Contents of the invention

The present invention provides a method for storing supplementary point data. A temporary storage area (memory buffer) exists in a high-speed cache (cache) to store calculated supplementary point data, which can reduce the amount of computation and the number of memory accesses.

The present invention also provides a storage method for supplementary point data, which adopts a storage method that effectively utilizes memory space, so as to avoid the above-mentioned waste of space in the temporary storage area.

A preferred embodiment of the present invention is to use the size distribution ratio of the motion vector difference to analyze the image, so as to determine the space size of the temporary storage area in the cache. The supplementary point is to use the motion vector to find the macro of the reference picture Block (macroblock), in order to calculate the supplementary points, and these motion vectors correspond to the macroblocks of the reference picture, and generally there will be more overlaps in images with strong correlation with each other, so use this temporary storage area to store the previous These calculated supplementary points avoid the amount of repeated calculations and the number of times to read the integer point position pixels from the external memory.

Another preferred embodiment of the present invention is a storage method in which the temporary storage area exists in the cache. The temporary storage area is divided into a plurality of areas by using these supplementary points corresponding to the decimal point of the logical coordinates in the external memory, and these areas are used to store the supplementary point data of non-integer point positions. In this way, the supplementary point data can be quickly searched in the temporary storage area without retaining the integer point position, which has the advantages of saving cache space and improving efficiency.

The present invention also provides a method for storing supplementary point data, including: judging whether non-integer point supplementary point data is stored in the temporary storage area; if the temporary storage area has stored the supplementary point data, providing the supplementary point data; and if The supplementary point data is not stored in the temporary storage area, and the integer point data adjacent to the non-integer point is read from the memory to calculate the supplementary point data, and then the supplementary point data is stored in the temporary storage area.

The present invention also provides a method for storing supplementary point data, including: dividing the temporary storage area into a plurality of areas; and using these areas to store the supplementary point data of multiple non-integer points; The fractional part of a logical coordinate is the same as that of the corresponding logical coordinate of another non-integer point in the same area.

The present invention also provides a method for storing supplementary point data, including: dividing the temporary storage area into multiple areas; using these areas to store multiple non-integer point supplementary point data, wherein each of the above-mentioned non-integer points The decimal part of the logical coordinates is the same as that of the corresponding logical coordinates of another non-integer point in the same area; if the supplementary point data of a specific non-integer point has been stored in the temporary storage area, the supplementary point data will be provided directly; And if the temporary storage area does not store the supplementary point data of the specific non-integer point, read the integer point data adjacent to the specific non-integer point from the memory, calculate the supplementary point data, and then store the supplementary point data into the staging area.

In order to make the above and other objects, features and advantages of the present invention more comprehensible, preferred embodiments of the present invention will be described in detail below together with the accompanying drawings.

Description of drawings

FIG. 1 is a schematic diagram of a supplementary point calculation in a general video encoding and decoding system.

FIG. 2 is a schematic diagram of a temporary storage area for supplementary point data according to an embodiment of the present invention.

3 and 4 are schematic diagrams of storage address rotation according to an embodiment of the present invention.

FIG. 5 is a schematic diagram of a partitioned storage method according to an embodiment of the present invention.

[Description of main component labels]

200: Staging area for cache

201, 202: Macro block

203: The overlapping part of the macro block

310, 320: The temporary storage area of supplementary point data is at the corresponding boundary of the reference picture

315, 325: non-integer point macroblocks of the reference picture

500: Temporary storage area for make-up point data

501, 502, 503: storage areas in the temporary storage area

511, 521, 531: Non-integer point data in the temporary storage area

MV1, MV2: dynamic vector

Detailed ways

The following description of the preferred embodiments takes a video encoder or a video decoder as an example. The video encoder or video decoder of this embodiment uses an external memory to store the data of the pixels at the integer point positions of the reference frame, and uses the built-in high-speed cache as a temporary storage area to store the previously calculated non-integer point positions The value of the pixel.

If you want to reduce the amount of system computation and the access frequency of external memory, you can use a large-capacity cache to store the calculated supplementary point data, but too large a cache will cause problems in terms of circuit area and price. Therefore, this embodiment uses a relatively small temporary storage area, such as 32*32 pixels, and adds the concept of storage address rotation (details will be described later), which can effectively reduce the amount of system computation and the frequency of external memory access, and also does not require Cache too large. In this embodiment, whenever a non-integer point supplementary point data is required, it is first judged whether the non-integer point supplementary point data is stored in the temporary storage area, and if it is stored, it is directly taken out and used without repeated calculation. On the contrary, if the temporary storage area does not store the supplementary point data, read the integer point data adjacent to the non-integer point from the external memory, calculate the required supplementary point data, and then store the calculated supplementary point data into Temporary storage area, which can be reused later.

FIG. 2 illustrates an example of the above method. Please refer to FIG. 2 , 200 is a temporary storage area for storing the supplementary point data. Assume that a certain macroblock of the current picture corresponds to the non-integer point macroblock 201 of the reference picture according to the motion vector MV1, and corresponds to the non-integer point macroblock 202 of the reference picture according to the motion vector MV2. When the supplementary point data of the macroblock 201 is calculated, the supplementary point data has been stored in the temporary storage area 200 . When the supplementary point data of the macroblock 202 is needed, the supplementary point data of the overlapping part 203 of the two macroblocks can be directly provided by the temporary storage area 200 without repeated calculation. As far as the macro block 202 is concerned, 31*31*4=3844 multiplication operations are originally required, but only 31*4-16*2=368 multiplication operations are required after deducting the overlapping part 203, saving about 90.4% of calculations quantity.

The size of the temporary storage area in this embodiment is not limited to 32*32 pixels. In fact, in this embodiment, the size distribution of the motion vector difference (MVD: motion vector difference) of at least one video bitstream is counted first, and then the size of the temporary storage area is determined according to the above size distribution. The magnitude of the so-called dynamic vector difference is defined here as the maximum value of each coordinate component of the dynamic vector difference. For example, a dynamic vector difference is (a, b), if a is greater than b, then the magnitude of the dynamic vector difference is a, otherwise it is b.

In this embodiment, three video data streams are analyzed, which are named News, Silent and Football, which can respectively represent low-frequency, medium-frequency and high-frequency video images. The video data stream News is mainly for broadcasting news, and its image movement changes little; the video data stream Silent is mainly for sign language movements, and its image movement is concentrated in some areas, and the movement change is higher than that of News; the video data stream Football is an American football scene, where athletes and Ball movement varies greatly. The above three video data streams are all CIF specifications, and the analysis results are shown in Table 1 below.

MVD<8 pixels 8<MVD<16 pixels 16<MVD<32 pixels MVD > 32 pixels News 67% 32.9% 0.1% 0% Silent twenty two% 57% 19% 2% Football 11% 36% 45% 8%

Table 1 Statistical table of dynamic vector difference analysis of various video data streams

In Table 1, most of the motion vector differences are less than 32 pixels, so the size of the temporary storage area in this embodiment is set to 32*32 pixels. If the high-frequency video is processed intensively, a temporary storage area of 64*64 pixels can be used ; If low-frequency video is processed intensively, a temporary storage area of 16*16 pixels is enough. In short, the size of the temporary storage area can be adjusted according to the distribution ratio of the dynamic vector difference. For example, the minimum side length of the temporary storage area must be greater than all Among all the motion vector differences of the video data stream, a preset proportion of the motion vector differences.

The temporary storage area in this embodiment is a two-dimensional array, which corresponds to an area of the same size in the reference frame. Since the temporary storage area is limited in size, it is inevitable that there will be macroblocks with non-integer points beyond the boundary of the temporary storage area. Please refer to Figure 3. Assume that the original boundary of the temporary storage area in the reference picture is 310, the logical coordinates of the upper left corner in the reference picture are (2.5, 3.5), the logical coordinates of the lower right corner in the reference picture are (34.5, 35.5), and the upper left corner is starting point. The boundary 310 can accommodate a macroblock 315 whose upper left corner has logical coordinates (18.5, 19.5) in the reference frame and its lower right corner has logical coordinates (34.5, 35.5) in the reference frame. The non-integer logical coordinates of the macroblock 315 are calculated based on a certain macroblock and its motion vector in the current frame.

In FIG. 3 , the logical coordinates of the upper left corner of another macroblock 325 are (20.5, 21.5), and the logical coordinates of the lower right corner are (36.5, 37.5). For the current boundary 310, if the supplementary point data of the macroblock 325 is to be stored, some non-integer points will exceed the range. In this embodiment, if a non-integer point exceeds the boundary of the temporary storage area, the logical coordinates of the starting point of the temporary storage area are adjusted so that the non-integer point falls into the new boundary of the temporary storage area. In the example of FIG. 3, in order to accommodate the supplementary point data of the macroblock 325, the logical coordinates of the starting point of the temporary storage area will be moved from (2.5, 3.5) to (4.5, 5.5), that is, the boundary of the temporary storage area will be moved from 310 to 320.

The access of supplementary point data in the temporary storage area is based on its real coordinates, and the real coordinates in the temporary storage area are different from the logical coordinates of the reference picture. Whenever the starting point of the temporary storage area moves, the logical coordinates of the starting point and the real coordinates will move synchronously, so that the supplementary point data stored in the temporary storage area does not have to follow the movement of the starting point. The method of calculating the real coordinates of a non-integer point is, for each logical coordinate of the above-mentioned non-integer point, calculate the result of subtracting the corresponding logical coordinate of the starting point from the logical coordinate plus the corresponding real coordinate of the starting point, and use the above result as the non-integer point The corresponding real coordinates of this logical coordinates of . Each of the above-mentioned logical coordinates refers to a different sub-coordinate corresponding to each coordinate axis, and the correspondence between the above-mentioned different sub-coordinates refers to corresponding to the same coordinate axis. For example, in the example of FIG. 3 , the logical coordinates of the starting point of the temporary storage area boundary 310 are (2.5, 3.5), and the real coordinates of the starting point are [0][0]. The x logical coordinate of the upper left corner of the macro block 315 is 18.5, subtract the x logical coordinate 2.5 of the starting point and add the x real coordinate 0 of the starting point, and the result is 16, which is the x real coordinate of the upper left corner of the macro block 315 . In the same way, the y logical coordinate of the upper left corner of the macro block 315 is 19.5, which is subtracted from the y logical coordinate 3.5 of the starting point and added to the y real coordinate 0 of the starting point, and the result is 16, which is the y coordinate of the upper left corner of the macro block 315. y real coordinate. When the boundary of the temporary storage area moves from 310 to 320, the logical coordinates of the new starting point are (4.5, 5.5), and the real coordinates of the new starting point are [2][2]. The logical coordinates (18.5, 19.5) of the upper left corner of the macroblock 315 are subtracted from the logical coordinates (4.5, 5.5) of the starting point and the real coordinates [2][2] of the starting point are added, and the result is the same real coordinates [16][16] . From the above results, it can be known that since the logical coordinates of the starting point and the real coordinates move synchronously, the real coordinates of the same non-integer point before and after the boundary movement are the same, so the data of the supplementary point does not need to follow the movement of the starting point and move in the temporary storage area.

After moving the starting point, the real coordinates of the non-integer points may still exceed the boundary of the temporary storage area. For example, in Figure 3, the real coordinates of the lower right corner of the macro block 325 are [34][34], exceeding the maximum allowable coordinates [31] [31]. At this time, the countermeasure of this embodiment is to store address rotation, as shown in Figure 4, store the non-integer points whose real coordinates exceed the right side of the temporary storage area on the left side of the temporary storage area, and store the real coordinates beyond the temporary storage area The non-integer points at the lower end are stored at the upper end of the temporary storage area, and vice versa. More precisely, if the real coordinates of a non-integer point corresponding to a certain coordinate axis are smaller than the lower limit of the coordinates of the same coordinate axis in the temporary storage area, then the This real coordinate plus the side length of the temporary storage area corresponding to the same coordinate axis. Conversely, if the real coordinate of a non-integer point corresponding to a certain coordinate axis is greater than the upper limit of the coordinates of the temporary storage area corresponding to the same coordinate axis, the real coordinate is subtracted Remove the side length corresponding to the same coordinate axis in the temporary storage area. For example, the logical coordinates of the upper right corner of the macro block 325 are (36.5, 21.5), the real coordinates are [34][18], and its x real coordinate exceeds the x-axis of the temporary storage area The upper limit is 31, the x-axis side length of the temporary storage area must be subtracted by 32, and then access is made in the temporary storage area according to the adjusted real coordinates [2][18]. Similarly, the logical coordinates of the lower left corner of the macroblock 325 is (20.5, 37.5), the real coordinates are [18][34], and its y real coordinates exceed the upper limit of the y-axis of the temporary storage area by 31, and the side length of the y-axis of the temporary storage area must be subtracted by 32, and then according to the adjusted real The coordinates [18][2] are accessed in the temporary storage area.

Please refer to FIG. 5 below. In the temporary storage area 500 in FIG. 5 , in addition to the non-integer points (marked by x), the storage locations of integer points (marked by o) are also reserved. This is for the convenience of searching for non-integer point supplementary point data in the temporary storage area 500 , but this will waste storage space. On the contrary, if the location of the integer point is not reserved in order to save the cache, more complex addressing operations are required to determine the storage location of the non-integer point. In order to take into account both storage space and computing efficiency, this embodiment adopts the method shown in FIG. 5 to divide the temporary storage area into multiple areas, and then disperse and store the supplementary point data of non-integer points in the above areas. Area 501 stores non-integer point data whose x coordinate is 1/2 and y coordinate is an integer point, such as 511 . Area 502 stores non-integer point data, such as 521 , whose y-coordinate is 1/2 and x-coordinate is an integer point. Area 503 stores non-integer point data whose x and y coordinates are both 1/2, such as 531 . In this way, the non-integer points in each area are arranged regularly, which is not only easy to address, but also can avoid the storage waste of integer point space.

The partition storage method in FIG. 5 is an example of 1/2 points. In fact, the above partition storage method is also applicable to other types of non-integer points, such as 1/4 points or 1/8 points. The temporary storage area of 1/4 point should be divided into 4 ² -1=15 areas, the temporary storage area of 1/8 point should be divided into 8 ² -1=63 areas, and so on. The general principle is that in each region, each non-integer point corresponds to the fractional part of the logical coordinates of each coordinate axis, which is the same as the fractional part of the logical coordinates corresponding to the same coordinate axis of another non-integer point in the same region. For example, in the region 502 in FIG. 5 , the fractional part of the x logical coordinate of each non-integer point is 0, and the fractional part of the y logical coordinate of each non-integer point is 0.5. In addition, the sets formed by the fractional parts of logical coordinates of non-integer points in each area are different. For example, in the example of Figure 5, the set of fractional parts of logical coordinates of non-integer points in area 501 is {0.5, 0}, the set of three areas is {0, 0.5} in area 502, and {0.5, 0.5} in area 503 vary.

The experimental results of this example will be described below. The experimental environment of the present embodiment is the H.264 decoder, respectively testing the video data stream News, Silent and Football of the CIF format, comparing the reference code JM8.2 of the International Standards Organization (ISO: International Standards Organization) and the method of the present embodiment , evaluate the amount of multiplication calculations (number of multiplication operations) required to calculate the value of the pixel at the 1/2 dot position and the amount of memory access per frame. The experimental results are shown in Table 2, Table 3 and Table 4 below. It can be seen from the following table that compared with the known JM8.2, this embodiment can indeed reduce the amount of multiplication calculation and memory access frequency.

News JM8.2 This embodiment growth rate Amount of multiplication 357,000/picture 113,000/picture 68% memory access 148.5K bytes/picture 49.5K bytes/picture 66.7%

Table 2 Experimental results of CIF video data stream News

Silent JM8.2 This embodiment growth rate Amount of multiplication 206,000/picture 86,000/picture 58.5% memory access 148.5K bytes/picture 65.4K bytes/picture 56%

Table 3 Experimental results of CIF video data stream Silent

Football JM8.2 This embodiment growth rate Amount of multiplication 87,000/picture 67,000/picture twenty three% memory access 148.5K bytes/picture 117.4K bytes/picture twenty one%

Table 4 Experimental results of CIF video data stream Football

To sum up, this embodiment uses a relatively small temporary storage area to store the previously calculated supplementary point data, which can reduce the calculation amount of the supplementary point and reduce the frequency of reading integer point data from the external memory, and it does not need to be too large. cache. This embodiment also adopts the method of storing non-integer point data in sub-areas to maintain simple addressing operations and avoid wasting space in the temporary storage area. The application of the present invention is not limited to video encoding and decoding, and any computing system that needs to repeatedly calculate the difference point can be applied. The integer point data required for calculating the supplementary point is not limited to be obtained from the reference picture, but may also be obtained from any data array with more than two dimensions. Compared with the above-mentioned computing system, the integer point data can be stored in the built-in general memory besides the external memory.

Although the present invention has been disclosed above with preferred embodiments, it is not intended to limit the present invention. Any person skilled in the art may make some changes and modifications without departing from the spirit and scope of the present invention. Therefore, this The scope of protection of the invention should be defined by the appended claims.

Claims (10)

1. A data storage method for making up shortfalls, comprising: Judging whether the supplementary point data of non-integer points is stored in the temporary storage area; Provide the make-up point data if the temporary storage area has already stored the make-up point data; and If the supplementary point data is not stored in the temporary storage area, the integer point data adjacent to the non-integer point is read from the memory to calculate the supplementary point data, and then the supplementary point data is stored in the temporary storage area. 2. The data storage method for making up the difference according to claim 1, further comprising: If the non-integer point exceeds the boundary of the temporary storage area, the logical coordinates of the starting point of the temporary storage area are adjusted so that the non-integer point falls within the boundary of the temporary storage area. 3. The data storage method for making up the difference according to claim 2, further comprising: For each logical coordinate of the non-integer point, calculate the result of the logical coordinate minus the corresponding logical coordinate of the starting point plus the corresponding real coordinate of the starting point, and use the above result as the corresponding real value of the logical coordinate of the non-integer point coordinate; If the real coordinate of the non-integer point is smaller than the corresponding lower limit of the temporary storage area, add the real coordinate to the corresponding side length of the temporary storage area; If the real coordinate of the non-integer point is greater than the corresponding upper limit of the temporary storage area, the real coordinate is subtracted from the corresponding side length of the temporary storage area; and The temporary storage area is accessed using the above real coordinates of the non-integer point. 4. The method for storing supplementary point data according to claim 1, wherein the supplementary point data storage method is executed by a computing system, the temporary storage area is stored in the cache memory of the computing system, and the memory for storing these integer point data is The external memory of the operating system. 5. The method for storing supplementary point data according to claim 4, wherein the computing system is a video encoder or a video decoder. 6. The data storage method for making up the difference according to claim 5, further comprising: Statistically calculate the magnitude distribution of the motion vector difference of at least one video data stream; and The size of the temporary storage area is determined according to the above size distribution. 7. The data storage method of supplementary points according to claim 6, wherein the magnitude of each of the dynamic vector differences is the maximum value of each coordinate component of the dynamic vector differences. 8 . The method for storing supplementary point data according to claim 7 , furthermore, among the dynamic vector differences, a preset proportion of the dynamic vector differences is smaller than the minimum side length of the temporary storage area. 9. The method for storing complementary point data according to claim 5, wherein the integer point data comes from reference frames of macroblocks. 10. The method for storing supplementary point data according to claim 9, wherein the logical coordinates of the non-integer point are calculated according to the motion vector of the macroblock.

Images