

Method for storing interpolation data 
8395635 
Method for storing interpolation data


Patent Drawings: 
(3 images) 

Inventor: 
Kao 
Date Issued: 
March 12, 2013 
Application: 

Filed: 

Inventors: 

Assignee: 

Primary Examiner: 
Brier; Jeffery A 
Assistant Examiner: 

Attorney Or Agent: 
Jianq Chyun IP Office 
U.S. Class: 
345/557; 345/568 
Field Of Search: 
345/557; 345/568 
International Class: 
G09G 5/36; G06F 12/00 
U.S Patent Documents: 

Foreign Patent Documents: 

Other References: 
Kao, JungYang; Method for Decreasing Computation Load and Memory Access Frequency during Interpolation for Video Coding; Signal 2007 IEEEWorkshop on Processing Systems; Nov. 21, 2007; pp. 610614. cited by examiner. Asaduzzaman, A. and Mahgoub, I.; Cache Optimization for Embedded Systems Running H.264/AVC Video Decoder, Apr. 18, 2006; IEEE International Conference on Computer Systems and Applications, 2006; pp. 665672. cited by examiner. ShinHaeng Ji, JungWook Park, and ShinDug Kim; Optimization of Memory Management for H.264/AVC Decoder; The 8th International Conference Advanced Communication Technology, 2006. ICACT 2006; May 8, 2006, pp. 6568. cited by examiner. 

Abstract: 
A method for storing interpolation data is provided. The method uses a buffer in a cache memory and the concept of memory overlap record for storing previously calculated interpolation data, so as to avoid repeated interpolation, thereby decreasing the amount of system operation and the frequency of reading integer points for calculating interpolation from an external memory. Furthermore, a method of data storage for the buffer is provided. The storage method uses the concept of memory address rotation to store interpolation data beyond the boundary of the buffer. Moreover, another storage method is provided, which distributes interpolation data into a plurality of regions in the buffer according to different combinations of decimal coordinates of the interpolation points for economizing the use of memory space and simplifying the search of interpolation data in the buffer. 
Claim: 
What is claimed is:
1. A method for storing interpolated data of a plurality of noninteger points, implemented by a calculation system calculating the interpolated data of the plurality ofnoninteger points, comprising: the calculation system determining whether the interpolated data of the plurality of noninteger points are stored in a buffer of the calculation system, wherein the calculation system is a video encoder or a videodecoder, and the buffer is stored in a builtin cache memory of the calculation system; if the interpolated data of the plurality of noninteger points are stored in the buffer, the calculation system providing the interpolated data; if theinterpolated data are not stored in the buffer, the calculation system reading the data of a plurality of integer points adjacent to the noninteger points from another memory of the calculation system, calculating the interpolated data of the pluralityof noninteger points by interpolating the data of the integer points, and storing the interpolated data of the plurality of noninteger points into the buffer; when the calculation system accesses the interpolated data of the noninteger points in thebuffer, for each logical coordinate of the noninteger points, the calculation system calculating a result of the logical coordinate minus a corresponding logical coordinate of a starting point of the buffer plus a corresponding real coordinate of thestarting point, wherein the result is taken as the real coordinate corresponding to the logical coordinate; if the real coordinate is smaller than a corresponding lower limit of the buffer, the calculation system adding a corresponding side length ofthe buffer to the real coordinate; if the real coordinate is larger than a corresponding upper limit of the buffer, the calculation system subtracting the corresponding side length of the buffer from the real coordinate; and the calculation systemaccessing the buffer with the real coordinates of the noninteger points.
2. The method for storing interpolated data of the plurality of noninteger points as claimed in claim 1, further comprising: if the noninteger points exceed the boundary of the buffer, adjusting the logical coordinates of the starting pointof the buffer, so as to make the noninteger points fall within the boundary of the buffer.
3. The method for storing interpolated data of the plurality of noninteger points as claimed in claim 1, wherein the memory storing the data of the integer points is an external memory of the calculation system.
4. The method for storing interpolated data of the plurality of noninteger points as claimed in claim 1, further comprising: counting the size distribution of motion vector differences (MVDs) of at least one video bitstream; and determiningthe size of the buffer according to the size distribution.
5. The method for storing interpolated data of the plurality of noninteger points as claimed in claim 4, wherein the size of each of the MVDs is the maximum value among the coordinate components of the MVD.
6. The method for storing interpolated data of the plurality of noninteger points as claimed in claim 5, wherein the size of each of a predetermined proportion of the MVDs is smaller than the minimum side length of the buffer.
7. The method for storing interpolated data of the plurality of noninteger points as claimed in claim 1, wherein the data of the integer points are from a reference frame of a macroblock.
8. The method for storing interpolated data of the plurality of noninteger points as claimed in claim 7, wherein the logical coordinates of the noninteger points are calculated according to a motion vector of the macroblock. 
Description: 
CROSSREFERENCE TO RELATED APPLICATION
This application claims the priority benefit of Taiwan application serial no. 95134555, filed Sep. 19, 2006. All disclosure of the Taiwan application is incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to interpolation in a video encoding and decoding system. More particularly, the present invention relates to a method for storing interpolation data in a video encoding and decoding system.
2. Description of Related Art
In the current video encoding and decoding system, the motion estimation has precisions of 1/2, 1/4, 1/8 points, wherein these noninteger points do not exist in an external memory and are obtained through the calculation of integer points inthe external memory. Therefore, in the video encoding and decoding system, interpolation is adopted no matter for motion estimation or motion compensation, as long as the motion vector of noninteger points is concerned.
For example, referring to FIG. 1, in the H.264 video system specification, the pixel value at the 1/2 point is calculated by a sixtap finite impulse response (FIR). In FIG. 1, white blocks (such as A, B, C, D) represent the positions ofinteger points, and lined blocks (such as aa, bb, h, m) represent the positions of 1/2 points that need interpolation. The pixel value at b point is the integer value of the formula (E5F+20G+20H5I+J)/32. The pixel value at h point is the integervalue of the formula (A5C+20G+20M5R+T)/32. Seen from the above formulae, the pixel value at 1/2 point is calculated through four multiply operations. As for the recently most popular image format, i.e., the common intermediate format (CIF), eachframe has 352.times.288 pixels, such that (703.times.575352.times.288(integer points)).times.4=1,211,396 multiply operations, approximately 1.2 million multiply operations, are needed to calculate all pixel values at 1/2 points of the CIF, andapproximately 50 million multiply operations are needed to calculate all pixel values at 1/8 points. In addition, the pixel values at 1/4 points can be calculated by an adder and a shifter, and thus are not discussed here. Moreover, in the CIF, the 1/2points alltogether have 703.times.575352.times.288(integer points)=302,846 pixels, which represents that approximately 296 Kbytes memory space is required for storing all of the pixel values at 1/2 points, and about 6 Mbytes memory space is requiredfor storing all of the pixel values at 1/8 points. As the interpolation points are deduced from the integer points stored in the external memory, if the bandwidth of the external memory is assumed to be 16 bits, to calculate the pixel values at 1/2, 1/4and 1/8 points, the integer point data of the whole frame has to be captured in each category, i.e., to capture 396.times.256.times.1.5/16=76032 times.
In view of the above, in video encoding and decoding systems, it is desirable to reduce the amount of operation for calculating the interpolation points and the memory space required for storing the interpolation points. It is also desirable toreduce the frequency of reading integer points data from the external memory.
SUMMARY OF THE INVENTION
The present invention is directed to providing a method for storing interpolation data, which uses a buffer in a cache memory to store the previously calculated interpolation data, so as to reduce the amount of operation and the access frequencyof the memory.
The present invention is further directed to providing a method for storing interpolation data, which employs a storage manner that can effectively utilize the memory space to avoid wasting of the above buffer space.
In a preferred embodiment of the present invention, as strongly related images are overlapped in many parts, a buffer is used to store the previously calculated interpolation points, thereby avoiding repeated interpolation and decreasing theamount of calculation and the frequency of reading the pixels at integer points from an external memory.
Another preferred embodiment of the present invention provides a storage method for the buffer in the cache memory. Based on the decimal parts of the logical coordinates of interpolation points corresponding to the external memory, the bufferis divided into a plurality of regions for storing the interpolation data of noninteger points. Therefore, the search of interpolation data in the buffer may be achieved rapidly without reserving the positions of integer points, the use of memory spaceis economized, and the efficiency thereof is improved.
In order to make the aforementioned and other objectives, features and advantages of the present invention comprehensible, preferred embodiments accompanied with figures are described in detail below.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a schematic view of interpolation in a common video encoding and decoding system.
FIG. 2 is a schematic view of a buffer for interpolation data according to an embodiment of the present invention.
FIGS. 3 and 4 are schematic views of memory address rotation according to an embodiment of the present invention.
FIG. 5 is a schematic view of the storage method of distributing data into divided regions according to an embodiment of the present invention.
DESCRIPTION OF EMBODIMENTS
In the following preferred embodiment, a video encoder or video decoder is used for example. The video encoder or video decoder of this embodiment adopts an external memory to store the pixel data of integer points of the reference frame, andemploys a builtin cache memory as a buffer to store the previously calculated pixel values of the noninteger points.
To reduce the amount of system operation and the access frequency of the external memory, a cache memory of large capacity can be used to store the previously calculated interpolation data. However, an oversized cache memory may cause problemsin the circuit area and price. Therefore, a buffer of a relatively smaller size, for example, 32.times.32 pixels, is employed in this embodiment, and the concept of memory address rotation (the details thereof will be illustrated later) is also adopted,such that the amount of system operation and the access frequency of the external memory can be effectively decreased without using a cache memory of excessively large capacity. In this embodiment, every time the interpolation data of a nonintegerpoint is required, whether the required interpolation data of a noninteger point is stored in the buffer is first determined, if yes, the data is fetched directly without repeated interpolation; while if not, the data of integer points adjacent to theabove noninteger point is read from an external memory for calculating the required interpolation data, and the calculated interpolation data is stored into the buffer for repeated use.
FIG. 2 is an example of the above method. Referring to FIG. 2, a buffer for storing interpolation data is marked with 200. Assume that a certain macroblock of the current frame is corresponding to a macroblock 201 of noninteger points in thereference frame according to a motion vector MV1, and is corresponding to a macroblock 202 of noninteger points in the reference frame according to a motion vector MV2. The interpolation data of the macroblock 201 has been stored in the buffer 200 whenbeing calculated. When the interpolation data of the macroblock 202 is required, the interpolation data of the overlap section 203 of the above two macroblocks can be directly provided by the buffer 200 without repeated interpolation. As for themacroblock 202, 31.times.31.times.4=3844 multiply operations are needed initially, but only 31.times.416.times.2=368 multiply operations are required after the overlap section 203 is subtracted, thus saving about 90.4% of the amount of operation.
The size of the buffer in this embodiment is not limited to 32.times.32 pixels. Actually, in this embodiment, the size distribution of the MVD of at least one video bitstream is first counted, and the size of the buffer is determined accordingto the size distribution. The socalled size of the MVD is defined as the maximum value among the coordinate components of the MVD. For example, a certain MVD is (a, b), wherein if a is larger than b, then the size of the MVD is a, otherwise b.
In this embodiment, three video bitstreams, namely News, Silent and Football, respectively representing video images of low frequency, intermediate frequency and high frequency are analyzed. The video bitstream News is mainly news broadcast,wherein the image movement variation is small. The video bitstream Silent is mainly gesture language, wherein the image movement is concentrated in some areas and the movement variation is higher than News. The video bitstream Football is the scene ofplaying American football, wherein the movement variation of the players and the football is significant. The above three video bitstreams are all of the CIF specification, and the analysis results are shown in Table 1 as follows.
TABLEUS00001 TABLE 1 MVD Analysis Statistics of Various Video Bitstreams MVD < 8 8 < MVD < 16 16 < MVD < 32 MVD > 32 pixels pixels pixels pixels News 67% 32.9% 0.1% 0% Silent 22% 57% 19% 2% Football 11% 36% 45% 8%
In Table 1, most of the MVDs are smaller than 32 pixels, so the size of the buffer in this embodiment is set to be 32.times.32 pixels. To integrally process high frequency videos, a buffer of 64.times.64 pixels is employed; while to integrallyprocess low frequency videos, a buffer of 16.times.16 pixels is enough. To sum up, the size of the buffer can be adjusted depending on the size distribution of the MVDs. For example, the minimum side length of the buffer may be set to be larger thaneach of the sizes of a predetermined proportion of all the MVDs of the video bitstreams.
The buffer of this embodiment is a two dimensional array corresponding to a region of the same size in the reference frame. As the size of the buffer is limited, it is unavoidable that some macroblocks of noninteger points exceed the boundaryof the buffer. Referring to FIG. 3, assume that the initial corresponding boundary of the buffer in the reference frame is 310, wherein the logical coordinates of the upper left corner of the buffer in the reference frame are (2.5, 3.5), the logicalcoordinates of the lower right corner thereof in the reference frame are (34.5, 35.5), and the upper left corner is taken as the starting point. The macroblock 315 is accommodated within the boundary 310, wherein the logical coordinates of the upperleft corner of the macroblock 315 in the reference frame are (18.5, 19.5), and the logical coordinates of the lower right corner thereof in the reference frame are (34.5, 35.5). The logical coordinates of the noninteger points in the macroblock 315 arecalculated according to a certain macroblock in the current frame and the motion vector thereof.
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 thereof are (36.5, 37.5). As for the current boundary 310, to store the interpolationdata of the macroblock 325, a portion of the noninteger points may exceed the range. In this embodiment, if a noninteger point exceeds the boundary of the buffer, the logical coordinates of the starting point of the buffer are adjusted to make thenoninteger point fall within the new boundary of the buffer. In the example of FIG. 3, to accommodate the interpolation data of the macroblock 325, the logical coordinates of the starting point of the buffer are moved from (2.5, 3.5) to (4.5, 5.5),i.e., moving the boundary of the buffer from 310 to 320.
The access of the interpolation data in the buffer depends on its real coordinates which are different from the logical coordinates in the reference frame. Whenever the starting point of the buffer is moved, the logical coordinates and realcoordinates of the starting point are moved synchronously, such that the interpolation data stored in the buffer does not have to be moved along with the starting point. The method for calculating the real coordinates of a noninteger point is that, foreach logical coordinate of the noninteger point, the result of the logic coordinate minus the corresponding logical coordinate of the starting point plus the corresponding real coordinate of the starting point is calculated, and the result is taken asthe real coordinate corresponding to the logic coordinate of the noninteger point. Each of the above logical coordinates refers to various subcoordinates in different coordinate axes, and the corresponding relation between the above subcoordinates isabout the same coordinate axis. For example, in the example of FIG. 3, the logical coordinates of the starting point on the boundary 310 of the buffer are (2.5, 3.5), and the real coordinates of the starting point are [0] [0]. The x logical coordinateof the upper left corner of the macroblock 315 is 18.5, subtract the x logical coordinate 2.5 of the starting point from the above logical coordinate and then add the x real coordinate 0 of the starting point, the result is 16, which is the x realcoordinate of the upper left corner of the macroblock 315. Similarly, the y logical coordinate of the upper left corner of the macroblock 315 is 19.5, subtract the y logical coordinate 3.5 of the starting point from the above logical coordinate and thenadd the y real coordinate 0 of the starting point, the result is 16, which is the y real coordinate of the upper left corner of the macroblock 315. When the boundary of the buffer is moved from 310 to 320, the new logical coordinates of the startingpoint are (4.5, 5.5), and the new real coordinates of the starting point are [2][2]. Subtract the logical coordinates (4.5, 5.5) of the starting point from the logical coordinates (18.5, 19.5) of the upper left corner of the macroblock 315 and then addthe real coordinates [2][2] of the starting point, the result is the real coordinates [16][16] as well. Seen from the above, as the logical coordinates and real coordinates of the starting point are moved synchronously, the real coordinates of the samenoninteger point before and after the movement of the boundary are identical. Therefore, the interpolation data of the noninteger point does not have to be moved in the buffer along with the starting point.
After the position of the starting point is moved, the real coordinates of the noninteger point may still exceed the boundary of the buffer. For example, in FIG. 3, the real coordinates of the lower right corner of the macroblock 325 are[34][34], which exceeds the maximum tolerable coordinates [31][31]. At this time, this embodiment resorts to the concept of memory address rotation. Referring to FIG. 4, the noninteger points with real coordinates exceeding the right side of thebuffer are stored on the left side of the buffer, and the noninteger points with real coordinates exceeding the lower side of the buffer are stored on the upper side of the buffer, vice versa. More precisely, if a real coordinate of a noninteger pointcorresponding to a coordinate axis is smaller than the lower limit of the buffer corresponding to the same coordinate axis, the side length of the buffer corresponding to the same coordinate axis is added to the real coordinate. On the contrary, if areal coordinate of a noninteger point corresponding to a coordinate axis is larger than the upper limit of the buffer corresponding to the same coordinate axis, the side length of the buffer corresponding to the same coordinate axis is subtracted fromthe real coordinate. For example, the logical coordinates of the upper right corner of the macroblock 325 are (36.5, 21.5), and the real coordinates thereof are [34][18]. As the x real coordinate of the macroblock 325 exceeds the upper limit 31 of thebuffer in the x axis, the side length 32 of the buffer in the x axis must be subtracted, and then the access in the buffer is performed according to the adjusted real coordinates [2][18]. Similarly, the logical coordinates of the lower left corner ofthe macroblock 325 are (20.5, 37.5), and the real coordinates thereof are [18][34]. As the y real coordinate of the macroblock 325 exceeds the upper limit 31 of the buffer in the y axis, the side length 32 of the buffer in the y axis must be subtracted,and then the access in the buffer is performed according to the adjusted real coordinates [18] [2].
Referring to FIG. 5, in the buffer 500 of FIG. 5, besides the noninteger points (marked by x), the storage positions of the integer points (marked by o) are also reserved for simplifying the search of the interpolation data of the nonintegerpoints in the buffer 500. However, as such, the memory space is wasted. On the contrary, if the positions of the integer points are not reserved for economizing the cache memory, a complicated addressing operation is needed to determine the storagepositions of the noninteger points. Therefore, to save the memory space and meanwhile improve the operation efficiency, this embodiment adopts a method shown in FIG. 5, wherein the buffer is divided into a plurality of regions, and the interpolationdata of the noninteger points are distributed into the regions. The region 501 stores the data of noninteger points with an x coordinate as 1/2 and y coordinate as an integer point, for example, 511. The region 502 stores the data of nonintegerpoints with a y coordinate as 1/2 and x coordinate as an integer point, for example, 521. The region 503 stores the data of noninteger points with x, y coordinates both as 1/2, for example, 531. As such, the noninteger points in each region arearranged regularly, which not only facilitates the addressing of the noninteger points, but also avoids wasting memory space on the integer points.
In FIG. 5, the storage method of distributing data into divided regions takes 1/2 points as an example. Actually, the above method is also applicable to other noninteger points, for example, 1/4 points or 1/8 points. The buffer of 1/4 pointsshould be divided into 4.sup.21=15 regions, the buffer of 1/8 points should be divided into 8.sup.21=63 regions, and the rest may be deduced by analogy. A general principle is that, in each region, the decimal part of the logical coordinate of eachnoninteger point in each coordinate axis is identical to that of the logical coordinate of another noninteger point in the same coordinate axis in the same region. For example, in the region 502 of FIG. 5, the decimal part of the x logical coordinatefor each noninteger point is 0, and the decimal part of the y logical coordinate for each noninteger point is 0.5. Additionally, the collection formed by the decimal parts of the logical coordinates of the noninteger points in each region isdifferent. For example, in the example of FIG. 5, the collection formed by the decimal parts of the logical coordinates of the noninteger points in the region 501 is {0.5, 0}, the region 502 is {0, 0.5} and the region 503 is {0.5, 0.5}, which aredifferent from each other.
The experimental results of this embodiment are described below. The experimental environment of this embodiment is H.264 decoder, wherein the CIF video bitstreams News, Silent and Football, are tested respectively, the reference code JM8.2 ofthe International Standards Organization (ISO) is compared with the method of this embodiment, and the amount of multiply operation (the frequency of multiply operation) required for calculating the pixel values at 1/2 points and the capacity of thememory in each frame are evaluated. The experimental results are shown in Tables 2, 3 and 4. Seen from the following tables, compared with the conventional JM8.2, this embodiment can surely reduce the amount of multiply operation and the accessfrequency of the memory.
TABLEUS00002 TABLE 2 Experimental Results of CIF Video Bitstream News Improvement News JM8.2 This Embodiment Rate Amount of 357,000/frame 113,000/frame 68% Multiply Operation Capacity of 148.5 Kbytes/frame 49.5 Kbytes/frame 66.7% Memory
TABLEUS00003 TABLE 3 Experimental Results of CIF Video Bitstream Silent Improvement Silent JM8.2 This Embodiment Rate Amount of 206,000/frame 86,000/frame 58.5% Multiply Operation Capacity of 148.5 Kbytes/frame 65.4 Kbytes/frame 56% Memory
TABLEUS00004 TABLE 4 Experimental Results of CIF Video Bitstream Football Improvement Football JM8.2 This Embodiment Rate Amount of 87,000/frame 67,000/frame 23% Multiply Operation Capacity of 148.5 Kbytes/frame 117.4 Kbytes/frame 21% Memory
In view of the above, this embodiment uses a relatively small buffer to store the previously calculated interpolation data, such that the amount of operation for the interpolation points and the frequency of reading the data of integer pointsfrom an external memory are reduced, and thus a moderatelysized cache memory is enough. This embodiment also adopts a storage method of distributing the data of noninteger points into divided regions, so as to maintain a simple addressing operationand avoid wasting the buffer space. The present invention is not limited to the video encoding and decoding system, but applicable to any calculation system that has to perform interpolation repeatedly. The data of integer points required forcalculating interpolation points is not limited to be acquired from a reference frame, but can also be acquired from any two dimensional data arrays. As for the above calculation system, the data of the integer points can not only be stored in anexternal memory, but also in a common builtin memory.
Though the present invention has been disclosed above by the preferred embodiments, they are not intended to limit the present invention. Anybody skilled in the art can make some modifications and variations without departing from the spiritand scope of the present invention. Therefore, the protecting range of the present invention falls in the appended claims.
* * * * * 


