Patent Publication Number: US-8989268-B2

Title: Method and apparatus for motion estimation for video processing

Description:
This application claims the benefit of Taiwan application Serial No. 99124049, filed Jul. 21, 2010, the subject matter of which is incorporated herein by reference. 
     BACKGROUND 
     1. Technical Field 
     The disclosure relates in general to a method and an apparatus for motion estimation, and more particularly to a method using fractional motion estimation and an apparatus for motion estimation. 
     2. Description of the Related Art 
     The H.264/Advanced Video Coding (AVC) video compression standard stipulated by the International Telecommunication Union (ITU-T) and the International Organization for Standardization (ISO)/International Electrotechnical Commission (IEC) achieves high compression ratio and has been widely used in many applications such as blue-ray disc, Internet Protocol Television (IPTV), and High Definition Television (HDTV) broadcasting. The compression standard employs two prediction methods for predicting the pixels of the currently encoded macroblock. One method is intra frame prediction, which predicts the pixels of the currently encoded macroblock according to the spatial correlation between adjacent macroblocks. The other method is inter frame prediction, which predicts the pixels of the currently encoded macroblock according to the time correlation between consecutive frames. The method for motion estimation finds the best matching region from the previous frame for each of the macroblocks that need to be encoded, and generates a corresponding motion vector. In addition to performing integer motion estimation with respect to the integer pixels, the method for motion estimation could perform fractional motion estimation to increase the accuracy level up to ½ or ¼ pixel. 
     The inter frame prediction, despite having great contribution in terms of compression performance, requires a large amount of computation time. For example, the H.264/AVC standard provides motion estimation for variable-size block modes, but motion estimation occupies about 60%-90% of the encoding time. Moreover, in the H.264 reference software, to obtain the best block mode, full search is performed with respect to all block modes, wherein integer motion estimation and fractional motion estimation are respectively performed. Thus, the complexity of the encoding computation according to H.264 is much higher than the previous video standard such as MPEG-1 or MPEG-2, which adopts fix-sized macroblock for motion estimation. The application of real-time encoding, such as the application of video recording in a hand-held apparatus, will use a large amount of computation resources or require a high-performance processor for encoding, thus increasing the cost for the implementation of an encoder. 
     SUMMARY 
     Embodiments are directed to a method and an apparatus for motion estimation, which could be used in a video coding process which performs motion estimation at variable accuracy levels with respect to the blocks with different sizes. An embodiment provides a method for motion estimation, which reduces the number of the modes requiring fractional motion estimation, hence increasing the efficiency of fractional motion estimation. Another embodiment provides a method for motion estimation, which reduces the number of search positions during fractional motion estimation, so that the required computation resources or hardware resources are reduced. Under the circumstances that the number of the modes requiring fractional motion estimation is decreased according to the above embodiments, fractional motion estimation could be performed with fewer search positions. Thus, the complexity and the required computation time for coding are reduced, and the overall computation time of motion estimation is largely reduced. 
     According to a first aspect, an embodiment of a method for motion estimation is provided. The method includes the following steps. In the course of motion estimation, integer motion estimation is performed with respect to a macroblock to generate a plurality of integer motion vectors. It is determined, according to a portion of the motion vectors, which correspond to a plurality of block modes, whether the integer motion vectors of each block mode are substantially equal to those of corresponding upper-layer block mode(s) of the block mode, so as to determine whether to perform or skip fractional motion estimation of the block mode, wherein each corresponding block of the upper-layer block mode(s) of the block mode is greater than the block mode. Thus, the number of the modes requiring fractional motion estimation is decreased. 
     According to a second aspect, a method for motion estimation is provided. The method includes the following steps. In the course of motion estimation, a first fractional motion estimation is performed to determine a first fractional optimum position according to a direction of a predicted motion vector, and a second fractional motion estimation is performed to determine a second fractional optimum position according to the direction of the predicted motion vector and the first fractional optimum position, wherein accuracy of the second fractional motion estimation is higher than that of the first fractional motion estimation. Thus, in the course of the fractional motion estimation, the number of search positions is reduced. 
     According to a third aspect, an apparatus with motion estimation is provided. The apparatus includes a motion estimation unit and a control unit. In the course of motion estimation, the motion estimation unit performs integer motion estimation with respect to a macroblock to generate a plurality of integer motion vectors. The control unit determines, according to a portion of the integer motion vectors, which correspond to a plurality of block modes, whether the integer motion vectors of each block mode are substantially equal to those of corresponding upper-layer block mode(s) of the block modes, and selectively controls the motion estimation unit to perform or skip fractional motion estimation of the block mode, wherein each corresponding block of the upper-layer block mode(s) of the block mode is greater than the block mode. 
     According to a fourth aspect, an apparatus with motion estimation is provided. The apparatus includes an integer motion estimation unit and a fractional motion estimation unit. In the course of motion estimation, in response to an integer motion vector generated by integer motion estimation unit, the fractional motion estimation unit refines the integer motion vector. The fractional motion estimation unit performs a first fractional motion estimation with respect to the integer motion vector to determine a first fractional optimum position according to the direction of a predicted motion vector, and performs a second fractional motion estimation to determine a second fractional optimum position according to the direction of the predicted motion vector and the first fractional optimum position, wherein accuracy of the second fractional motion estimation is higher than that of the first fractional motion estimation. 
     The above and other aspects of the disclosure will become better understood with regard to the following detailed description of the preferred but non-limiting embodiment(s). The following description is made with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows various types of H.264 block modes. 
         FIG. 2  shows an implementation of motion estimation by hardware. 
         FIG. 3  shows an example of a portion of a circuit block diagram of a video encoder. 
         FIG. 4  shows the partition and naming of the modes 1 to 3 and mode P8×8. 
         FIG. 5  shows a flowchart of a first example of a method for motion estimation according to a first embodiment. 
         FIG. 6  shows a flowchart of a second example of a method for motion estimation according to the first embodiment. 
         FIG. 7  shows a flowchart of a method for motion estimation according to a second embodiment. 
         FIG. 8  shows the process of locating fractional optimum position according to a method for the motion estimation of the second embodiment. 
         FIGS. 9A-9D  respectively show four scenarios for selecting first fractional search positions and directions. 
         FIGS. 10A-10C  respectively show three scenarios for selecting second fractional search positions and directions. 
         FIG. 11  shows a block diagram of a fractional motion estimation unit according to the second embodiment. 
     
    
    
     DETAILED DESCRIPTION 
     A number of embodiments are exemplified below according to the H.264 standard. However, the following embodiments could also be used in other implementations of video standards based on H.264 such as scalable video coding (SVC), or used in storage media such as blue-ray discs and high definition DVD (HD-DVD), or TV broadcasting such as high definition TV or internet protocol TV (IPTV). Thus, the embodiments disclosed below could be used in various occasions of video processing or implemented in various computation apparatuses, hand-held apparatuses or video processing apparatuses. 
     First Embodiment 
     The first embodiment provides a method for motion estimation capable of decreasing the number of the modes requiring fractional motion estimation. In the course of the fractional motion estimation of the present embodiment, the modes requiring fractional motion estimation are determined according to a portion of motion vectors obtained from integer motion estimation, so that the number of the modes requiring fractional motion estimation is reduced and the efficiency of fractional motion estimation is increased. 
     The present embodiment could be used in the video coding using variable block-size motion estimation. As an example, H.264/AVC (referred to as H.264 hereinafter) allows different block modes by dividing a 16×16 macroblock into several blocks of different sizes, and totally seven block modes of different sizes are provided. As indicated in  FIG. 1 , the block modes could be categorized as macroblock type and 8×8 type (sub-macroblock type or 8×8 type). The macroblock type includes 16×16, 16×8, 8×16 and 8×8 block modes. The 8×8 type includes 8×8, 8×4, 4×8 and 4×4 block modes. 
       FIG. 2  shows an implementation of motion estimation by hardware. Integer motion estimation (IME) and fractional motion estimation (FME) are respectively implemented by two circuit stages such as an IME unit  210  and an FME unit  220 , which could be realized by two pipeline stages. However, other implementations could be used in other examples. The IME unit  210  generates 41 integer motion vectors (IMV) of the seven block modes from a macroblock according to variable-block-size motion estimation (VBSME). Then, the FME unit  220  sequentially increases the accuracy of the motion vector of each block mode. In other words, the FME unit  220  refines the motion vectors. Lastly, after the processing by the FME unit  220 , the mode with minimum cost will be selected as the optimum mode for coding. 
     When the method of the first embodiment is applied to motion estimation circuit of  FIG. 2 , which of the block modes required to be processed by the FME unit  220  are determined through comparison according to a portion of motion vectors obtained by the IME unit  210 . Thus, the FME unit  220  does not need to perform fractional motion estimation with respect to the integer motion vectors IMV of all modes. Thus, the computation time and the computation resources required for fractional motion estimation are reduced, and the circuit complexity of the circuit implementation of the FME unit  220  could be simplified. 
       FIG. 3  shows an example of a portion of a circuit block diagram of a video encoder. A motion estimation unit  200  is implemented according to the architecture of  FIG. 2  to generate the optimum motion vectors MVB. The controller  100  obtains a portion of integer motion vectors from the motion estimation unit  200 , and determines which block modes requiring fractional motion estimation according to the integer motion vectors. The controller  100  controls the motion estimation unit  200 , for example, through at least one control signal CS. 
     The method of the present embodiment determines which modes require fractional motion estimation through the comparison of a portion of motion vectors obtained from integer motion estimation. The details of the method are exemplified below. 
     According to H.264, the rate-distortion cost (RD cost) could be used as a criterion for determining the mode with minimum cost. The RD cost could be expressed as: λ*bit_len (mvd)+SATD, wherein λ is determined by a quantization parameter, bit_len (mvd) denotes the coded bits of motion vectors difference (mvd), and SATD denotes the sum of absolute transformed difference. With regard to H.264, the present embodiment sets the criteria for determining the mode according to the following viewpoints to reduce the motion estimation of redundant modes. One viewpoint is that: if the integer motion vectors of two modes are substantially identical, then the SATD of the two modes will be very close. Here, the term “substantially identical (or equal)” refers to the integer motion vectors of two modes being identical (for example, the coordinates of the two motion vectors are identical) or the difference of the integer motion vectors of two modes being within a predetermined range, for example, the coordinate difference (at least one of the x coordinate and the y coordinate) between two motion vectors being within the range of one or two pixels, and the range could be defined or set according to the need in practical application. The other viewpoint is that: it is probably that the motion vector of one mode may approach the upper-layer block of the mode. As indicated in  FIG. 1 , the partition 0 of the mode 2 (that is, the 16×8 block mode) is viewed as the upper-layer block of the partition 0 or 1 of the mode 4 (that is, the 16×16 block mode is divided into four 8×8 block modes), and the motion vectors of the latter normally approach the motion vectors of the former. Thus, the method for motion estimation according to the first embodiment is exemplified in two examples below. 
     Referring to  FIG. 5 , a flowchart of a first example of a method for motion estimation according to the first embodiment is shown. In the course of motion estimation, as indicated in step S 100 , integer motion estimation is performed with respect to a macroblock, such as seven block modes for H.264, to generate a plurality of corresponding integer motion vectors. Next, as indicated in step S 500 , a method of fractional motion estimation of the present embodiment is performed according to a portion of motion vectors obtained from integer motion estimation to determine whether the integer motion vectors of a mode are substantially equal to the integer motion vectors of the upper-layer block mode so as to determine whether to perform or skip the fractional motion estimation of the mode. The definition of the modes, taken H.264 for example, is indicated in  FIGS. 1 and 4 . The modes 1-3 respectively denote three block modes, namely, 16×16, 16×8 and 8×16. The mode P8×8 denotes the 8×8 type, wherein each 8×8 block and its partitions could be resulted in four different blocks of different sizes such as 8×8, 8×4, 4×8 and 4×4. The mode P8×8 of  FIG. 4  is a macroblock with partitions 0-8, wherein the integer motion vector of a partition n of a mode is referred to as IMVn. 
     The fractional motion estimation of  FIG. 5  includes the following steps. Firstly, as indicated in step S 510 , the fractional motion estimation of the mode 1 is performed. Next, the method proceeds to step S 520 , whether the integer motion vectors of the mode 2 are substantially equal to the integer motion vector of the mode 1 is determined. That is, whether the integer motion vectors (that is, IMV 0  and IMV 1 ) of partitions 0 and 1 of the mode 2 are all substantially equal to the integer motion vector (that is, IMV 0 ) of the mode 1 is determined. If not, then the method proceeds to step S 525 , wherein the fractional motion estimation of the mode 2 is performed. That is, fractional motion estimation is performed with respect to the integer motion vectors of the mode 2. For example, the two integer motion vectors IMV 0  and IMV 1  of the mode 2 are refined by the FME unit  220  of motion estimation unit  200 , and after step S 525  is completed, the method proceeds to step S 530 . If the determination result in step S 520  is affirmative, this implies that step S 525  could be skipped. 
     The method of the present example proceeds to step S 530  to determine whether the integer motion vectors of the mode 3 and the mode 1 are substantially equal. That is, whether the integer motion vectors IMV 0  and IMV 1  of partitions 0 and 1 of the mode 3 are all equal to the integer motion vectors IMV 0  of the mode 1 is determined. If not, then the method proceeds to step S 535 , the fractional motion estimation of the mode 3 is performed, and after step S 535  is completed, the method proceeds to step S 540 . If the determination result in step S 530  is affirmative, this implies that step S 535  could be skipped. 
     The method of the present example proceeds to step S 540  to determine whether the integer motion vectors of the mode P8×8 are substantially equal to the integer motion vectors of the mode 1, 2 or 3. If not, the method proceeds to step S 545 , the fractional motion estimation of the mode P8×8 is performed. If the determination result in step S 540  is affirmative, this implies that step S 545  could be skipped. The determination criterion of step S 540  is one of the criteria 1, 2 and 3. Criterion 1: the integer motion vectors IMV 0 -IMV 8  of the mode P8×8 are all equal to the integer motion vectors IMV 0  of the mode 1. Criterion 2: the integer motion vectors IMV 0 -MV 2  of the mode P8×8 are all equal to the integer motion vectors IMV 0  of the mode 2, and the integer motion vectors IMV 3 -MV 8  of the mode P8×8 are all equal to the integer motion vectors IMV 1  of the mode 2. Criterion 3: the integer motion vectors IMV 0 , IMV 3  and IMV 4  of the mode P8×8 are all equal to the integer motion vector IMV 0  of the mode 3, and the integer motion vectors IMV 1 , IMV 2 , and IMV 5 -IMV 8  of the mode P8×8 are all equal to the integer motion vector IMV 1  of the mode 3. In order to reduce the number of the modes requiring fractional motion estimation with respect to the integer motion vectors of the mode P8×8 in step S 540 , in an example, it is sufficient to use the integer motion vectors of the optimum mode (that is, the mode with minimum RD cost) of the 8×8 types (including the modes 8×8, 8×4, 4×8 and 4×4) of each of the four 8×8 blocks obtained from the partitions of a macroblock. Thus, in step S 540 , the comparison could be based on at least 4 to at most 16 IMVs, and at least the integer motion vectors IMV of the optimum mode are used for comparison, and the modes that are not used could be excluded from criterion 1, 2 or 3. Suppose the optimum integer motion vectors of the mode P8×8 are the integer motion vectors IMV 0  of the four 8×8 block modes. If the integer motion vectors IMV 0  of the four modes P8×8 are all equal to the integer motion vector IMV 0  of the mode 1, this implies that criterion 1 is satisfied, and there is no need to compare the integer motion vectors IMV 2 -IMV 8  which are not the IMV of the optimum mode. Suppose the integer motion vectors of the mode P8×8 are the integer motion vectors IMV 0  of two 8×8 block modes, the integer motion vectors IMV 1  and IMV 2  of one 8×4 block mode, the integer motion vectors IMV 3  and IMV 4  of one 4×8 block mode, and the integer motion vectors IMV 5 -IMV 8  of one 4×4 block mode. If the integer motion vectors IMV 0 -IMV 2  of this example are equal to the integer motion vectors IMV 0  of the mode 2, and the integer motion vectors IMV 3 -IMV 8  are all equal to the integer motion vectors IMV 1  of the mode 2, then criterion 2 is satisfied. Other scenarios could be known in the similar manner, and are not repeated here for the sake of brevity. 
     After step S 540  or S 545  is completed, the method for motion estimation could further determine suitable block modes and motion vectors according to the fractional motion vectors obtained in step S 500  and the known integer motion vectors. For example, the H.264 motion estimation determines optimum block modes and motion vectors according to the rate-distortion cost. 
     By simulations, tests for the first example of the present embodiment on a number of exemplary video files (such as akiyo, news, silent, foreman, mobile) show that the number of clock cycles required for fractional motion estimation could be reduced by decreasing the number of the modes requiring fractional motion estimation, and the reduction in the number of clock cycles is about 60% of the H.264 reference software. Besides, the quality similar to the H.264 reference software could also be achieved. 
     Referring to  FIG. 6 , a flowchart of a second example of a method for motion estimation according to the first embodiment is shown. The main difference between the example of  FIG. 6  and the example of  FIG. 5  is as follows. According to a method of fractional motion estimation as indicated in step S 600 , a determination as to whether to perform the fractional motion estimation of a mode is made according to the number of encoded bits of the motion vector difference in addition to a portion of motion vectors obtained from integer motion estimation for comparison. That is, the determination is made according to the relationship of integer motion vectors IMV and motion vector differential cost mvd_cost between the mode and its upper-layer block mode. The rate-distortion cost RD cost is expressed as: λ*bit_len (mvd)+SATD, wherein λ*bit_len (mvd) denotes the motion vector differential cost mvd_cost. 
     The fractional motion estimation of  FIG. 6  includes the following steps. As indicated in step S 610 , it is determined whether the integer motion vectors of the mode 2 and mode 1 are substantially equal, and the motion vector differential cost of the mode 2 is greater than the motion vector differential cost of the mode 1 (that is, whether mvd_cost (mode 2 )&gt;mvd_cost (mode 1)), wherein modeN denotes the mode N, N is a positive integer. If not, the method proceeds to step S 615 , the fractional motion estimation of the mode 2 is performed, and after step S 615  is completed, the method proceeds to step S 620 . If the determination result in step S 610  is affirmative, this implies that step S 615  could be skipped. 
     The method then proceeds to step S 620  to determine whether the integer motion vectors of the mode 3 and mode 1 are substantially equal, and the motion vector differential cost of the mode 3 is greater than the motion vector differential cost of the mode 1 (that is, whether mvd_cost (mode 3 )&gt;mvd_cost (mode 1)). If not, then the method proceeds to step S 625 , the fractional motion estimation of the mode 3 is performed, and after step S 625  is completed, the method proceeds to step S 630 . If the determination result in step S 620  is affirmative, this implies that step S 625  could be skipped. 
     Then, the method proceeds to step S 630 , wherein it is determined whether the integer motion vectors IMV of the mode 1 are substantially equal to those of the mode 2 and the FME of the mode 2 is performed, or the integer motion vectors IMV of the mode 1 and mode 3 are substantially equal and the FME of the mode 3 is performed. If not, then the method proceeds to step S 635 , the fractional motion estimation of the mode 1 is performed, and after step S 635  is completed, the method proceeds to step S 640 . If the determination result in step S 630  is affirmative, this implies that step S 635  could be skipped. 
     Then, the method proceeds to step S 640  to determine whether the integer motion vectors of the mode P8×8 are substantially equal to those of the mode 1, 2 or 3. If not, the method proceeds to step S 645  to perform the fractional motion estimation of the mode P8×8. If the determination result in step S 640  is affirmative, this implies that step S 645  could be skipped. Since steps S 640  and S 645  of  FIG. 6  are similar to steps S 540  and S 545  of  FIG. 5 , the similarities are not repeated here. 
     After step S 640  or S 645  is completed, the method for motion estimation could further determine suitable block modes and motion vectors according to the fractional motion vectors obtained in step S 600  and the known integer motion vectors. For example, the H.264 motion estimation determines optimum block modes and motion vectors according to the rate-distortion cost. 
     In the second example of  FIG. 6 , the motion vector differential cost is further used as a determination criterion, so that the required computation resources are reduced and the bit rate could be similar to the reference software. In hardware implementation of the two examples of the first embodiment, a determination circuit is needed, which could be realized by comparators, adders, or logic circuitry. Referring to  FIG. 3 , the determination circuit could be realized in the controller  100 . In addition, in this example, if the integer motion vectors of the optimum mode from the integer motion vectors of the mode P8×8 are adopted in the implementation of step S 540 , a reduced amount of IMVs are then required to be transmitted to the controller  100  and it is sufficient for the controller  100  to control the motion estimation unit  200  which determines whether to perform or to skip the modes. In this manner, the efficiency of fractional motion estimation could be enhanced. The controller  100  could be realized as an independent circuit, or a control circuit of a video processor (e.g., an encoder or a video transmission apparatus), such as an encoding controller. 
     Second Embodiment 
     A second embodiment provides a method for motion estimation to reduce the number of search positions in the course of fractional motion estimation. In the course of fractional motion estimation with respect to an integer motion vector, a plurality of first fractional search positions are generated according to a direction of a predicted motion vector and a first fractional optimum position is determined accordingly. For further refinement, a plurality of second fractional search positions are then generated according to the direction of the predicted motion vector and the first fractional optimum position so as to determine a second fractional optimum position. In this way, the efficiency of fractional motion estimation is increased, the required computation resources are reduced, and the fractional motion estimation could be implemented by less hardware resources. 
     Referring to  FIG. 7 , a flowchart of a method for motion estimation according to the second embodiment is shown. The method is for performing fractional motion estimation with respect to an integer motion vector to increase the accuracy of fractional motion estimation, that is, to refine the integer motion vector, for example, an integer motion vector with minimum integer motion estimation cost. In the following exemplification, the coordinates of an integer motion vector being an integer position are used as a starting point (which could be viewed as the original point), such as the starting point P 800  of  FIG. 8 , for performing fractional motion estimation. In  FIG. 7 , as in step S 710 , a predicted motion vector PMV is obtained, wherein the predicted motion vector, such as a default motion vector according to H.264, is determined according to the motion vectors of the adjacent macroblocks of the currently encoded macroblock. Next, the method proceeds to step S 720 , a plurality of first fractional search positions are generated according to the direction of the predicted motion vector, and the first fractional search positions are the first fractional positions closer to the direction, wherein the first fractional positions indicate the positions at a first fractional accuracy, for example, half-pixel accuracy. For example, an arrow A 10  of  FIG. 8  indicates the direction of the predicted motion vector is towards the top right, and the three half-pixel positions (such as the three hollowed squares) closer to the direction are used as the half-pixel search positions. 
     Then, the method proceeds to step S 730 , the FME is performed with respect to the first fractional search positions and the integer position to determine a first fractional optimum position, wherein the FME adopts parallel processing. For example, the FME unit calculates the rate-distortion cost of the three half-pixel search positions and the starting point P 800  according to H.264, and determines the position with minimum RD cost, such as the position P 810 , as the first fractional optimum position. In step S 740 , a plurality of second fractional (such as quarter-pixel) search positions are generated according to the first fractional optimum position and the direction of the predicted motion vector. The second fractional search positions are the second fractional positions (i.e., the positions at a second fractional accuracy) closer to the direction of the predicted motion vector and the integer position. For example, in the vicinity of the position P 810 , the second fractional search positions are the second fractional positions (the positions denoted by the four hollowed triangles) closer to the direction of the predicted motion vector (the top right direction) and the integer position (i.e., the position P 800 ). 
     Then, the method proceeds to step S 750 , the FME is performed with respect to the second fractional search positions to determine the second fractional optimum position such as the position P 820 , wherein the FME is implemented by parallel processing. 
     In step S 720 , the first fractional search positions generated according to the direction of the predicted motion vector are the first fractional positions closer to the direction. In an example as indicated in  FIGS. 9A-9D , the search positions could have four scenarios based on the direction of the predicted motion vector. For example, according to different combinations of the + sign and the − sign of the coordinate direction, denoted by (x-dir, y-dir), there are scenario  1  to  4 , namely, (+,+), (+,−), (−,−), (−,+), respectively. In step S 720 , a corresponding predetermined search direction, i.e., one of the search directions include bottom right, top right, top left and bottom left. As indicated by the arrows, and a number (such as three or two) of corresponding first fractional search positions could be identified from the four scenarios according to the direction of the predicted motion vector. All three positions are closer to the direction and are separated from the starting point by a first fractional coordinate, such as ½ pixel according to H.264. 
     Furthermore, in step S 740 , all the second fractional search positions generated according to the first fractional optimum position and the direction of the predicted motion vector are the second fractional positions closer to the direction of the predicted motion vector and the integer position. The method of the present example is called “adaptive and direction-based location search”. Three scenarios are illustrated in  FIGS. 10A-10C . 
     Scenario  1 : in step S 730 , if the original point P 800  is identified as the first fractional optimum position, then the second fractional search positions could be set as being in the vicinity (upper, lower, left, and right positions) of the original point P 800  and separated from the starting point by a second fractional coordinate, such as ¼ pixel according to H.264. For example, the second fractional search positions could be set as (¼,0), (0,¼), (−¼,0) and (0,−¼). 
       FIG. 10B  shows scenario  2 : if the first fractional optimum position P 730  is not the original point P 800 , then the second fractional search positions could be selected from the five ¼ pixel positions (such as the positions denoted by triangles) according to an updated prediction direction A 110 . The updated prediction direction A 110  is obtained according to the position P 730  and the above mentioned direction of the predicted motion vector A 100 . As indicated in  FIG. 10B , the updated prediction direction A 110  indicates that the more accurate search positions should appear in the second fractional positions (such as the positions denoted in hollowed triangles) that are closer to the direction of the predicted motion vector A 100  and the integer position P 800 . The coordinates of the second fractional positions are (¼,−½), (¼,−¼), (0,−¼) and (−¼,−¼), i.e., as indicated by the positions denoted by hollowed triangles. Similarly, if the updated prediction direction A 110  is inclined to the bottom left, then the leftward four positions, namely, (−¼,−½), (−¼,−¼), (0,−¼) and (¼,−¼), are selected. Likewise, when the other optimum position P 730  falls in the x-axis or the y-axis passing through the original point, the second fractional positions fall in the possible positions, for example, denoted by bold lines P 10 B of  FIG. 10B . 
       FIG. 10C  shows scenario  3 : if the first fractional optimum positions P 730  are the squares of  FIG. 10C , then the selection of the second fractional search position is similar to scenario  2  of  FIG. 10B , and the similarities are not repeated here for the sake of brevity. For example, the second fractional positions fall in the possible positions, for example, denoted by bold lines P 10 C of  FIG. 10C . 
     In the example of the second embodiment, fractional motion estimation finds an optimum position from four first or second fractional search positions. However, the present embodiment is not limited thereto. In other examples of the second embodiment, a number of search positions, such as three, four or five, could be generated in step S 720  (or step S 740 ) according to the direction of the predicted motion vector of fractional motion estimation. Further, in the present embodiment, the first fractional accuracy and the second fractional accuracy are not subjected to being ½ pixel and ¼ pixel respectively, and other fractional accuracy such as ⅓, ⅙ or ⅛ pixel could also be used. Besides, in other examples, the steps S 740  and S 750  of  FIG. 7  could be repeated to make refinement. Also, the selection of the first or the second fractional search positions could be achieved in other way. That is, all first fractional search positions are first fractional positions closer to the direction of the predicted motion vector, and all second fractional search positions are second fractional positions closer to the direction of the predicted motion vector and the integer position. 
     An apparatus for fractional motion estimation could be implemented according to the present embodiment. Referring to  FIG. 11 , a block diagram of a fractional motion estimation unit  1000  according to the present embodiment is shown. The fractional motion estimation unit  1000  includes a fractional motion estimation device  1100  and a mode determination circuit  1170 , and a memory  1180  such as a buffer. The fractional motion estimation apparatus  1100  is implemented by hardware according to, for example, the fractional motion estimation method of  FIG. 7 . The predicted motion vector generation device  910  receives the motion vectors (MV) of the macroblocks adjacent to the current macroblock CB to generate a predicted motion vector PMV to implement step S 710 . The search position generation device  1120  generates suitable search positions with the interpolation device  1110  according to the predicted motion vector PMV so as to implement step S 720 . The search position generation device  1120  could determine the selection of scenarios, corresponding direction and search positions according to the coordinates of the predicted motion vector and could be implemented according to the approaches as indicated in  FIGS. 9A-9D  by using such as a digital circuit, a logic circuit, a look-up table or a firmware. When fractional motion estimation is performed according to the search positions, the fractional motion estimation apparatus  1100  needs to read a pixel RB of the reference frame and a pixel CB of the current macroblock. On the part of the fractional motion estimation apparatus  1100 , the residue calculation circuit  1130 , the Hadamard transform (HT) device  1140  (for implementing 4×4 Hadamard transform), and the accumulator (ACC)  1150 , perform fractional motion estimation according to, for example, H.264 standard, and calculate the corresponding cost (such as the RD cost) of each search position. The residue calculation circuit  1130  reads the pixel CB of the current macroblock and further compares the pixel CB of the current macroblock with the search position generated by the search position generation device  1120  to generate and provide a residue to the HT device  1140 , and could additionally outputs the residue data. There are four HT devices  1140  in total, which correspond to four search positions, adopt parallel processing, corporate with the ACC  1150  to obtain the SATD of each search position, and further corporate with the motion vector cost calculation circuit  920  to output the mvd_cost, so as to complete the calculation of the RD cost for each search position. Then, the search position with minimum cost is determined by the comparison circuit  1160 , and step S 730  is thus implemented. Besides, the search position generation device  1120  receives the first fractional optimum search position outputted from the comparison circuit  1160 , and further generates the second fractional search positions according to the predicted motion vector PMV to implement step S 740 . For example, the search position generation device  1120  could select suitable search positions by way of circuit determination, look-up table or calculation according to the scenarios as indicated in  FIGS. 10A-10C . Then, the fractional motion estimation apparatus  1100  implements step S 750 . Lastly, the second fractional optimum position is outputted to the mode determination circuit  1170 , which determines the optimum mode according to the previously obtained integer motion vectors, the fractional motion vectors and parameters such as the cost and further outputs the optimum mode to the memory  1180 . Thus, the data such as the optimum motion vector MVB, the optimum mode and the minimum SATD could be outputted for video processing such as encoding. 
     During the implementation of H.264, the predicted motion vector PMV must be generated according to the video system standard. Provided that the predicted motion vector PMV could be provided by the video processor, there is no need for the fractional motion estimation unit  1000  to generate the predicted motion vector PMV again. Therefore, in other implementations, at least one of the predicted motion vector generation device  910  and the motion vectors cost calculation circuit  920  could be regarded as a circuit not belonging to the fractional motion estimation unit  1000 , or does not need to be implemented in the fractional motion estimation unit  1000 , and the predicted motion vector PMV could be directly read from other portions of the video processor. In other embodiments, three or five sets of the HT device  1140  and the ACC  1150  of  FIG. 11  could be employed, corresponding to three or five search positions in the course of FME. 
     The present embodiment is exemplified by H.264. However, the present embodiment could also be used in other instants of fractional motion estimation or video processing. In other instants of video processing, the Hadamard transform could be replaced with other transforms or cost calculation for the optimum search position. Any methods that generate search positions by fractional motion estimation according to the predicted motion vector, and further adaptively refine the search positions according to the predicted motion vector are within the scope of implementation of the present embodiment. 
     Third Embodiment 
     Under the circumstances that the number of the modes requiring fractional motion estimation is reduced according to the first embodiment, in the course of fractional motion estimation such as steps S 510 , S 525 , S 535  and S 545  of  FIG. 5  and steps S 610 , S 625 , S 635  and S 645  of  FIG. 6 , the third embodiment performs estimation with the fewer number of search positions obtained in the second embodiment. Thus, the complexity and the required computation time for coding are reduced, and better efficiency is achieved. Referring to  FIG. 2  and  FIG. 3 , the third embodiment could be regarded as implementing the first embodiment by the controller  100 , the motion estimation unit  200  has the architecture as indicated in  FIG. 2 , and the FME unit  220  could be implemented according to the second embodiment. 
     Other Embodiments 
     The first embodiment and the second embodiment could be implemented separately. That is, during the implementation of the first embodiment, step S 510  or S 610  of fractional motion estimation could be implemented in a manner different from the second embodiment. Also, the implementation of the second embodiment could be incorporated in a manner different from the first embodiment to reduce the number of required modes or perform all of the modes. Further, the second embodiment may be implemented with an independent fractional motion estimation unit or a motion estimation apparatus including both integer motion estimation and fractional motion estimation. The above methods and hardware for implementing the embodiments, no matter used individually or collectively, are within the scope of implementation of the disclosure. 
     In addition to the above implementation by hardware structure, the method of the above embodiments could also be implemented, for example, by a processor, a digital signal processor and a digital video processor, or a programmable integrated circuit such as a microcontroller and a field programmable gate array (FPGA) circuit, wherein the circuit is designed using such as hardware description language (HDL). 
     Also, the method of the above embodiments could also be implemented by software. For example, in an example of the method according to the embodiments, the programming code could be recorded in a memory medium such as an ROM and an RAM, or an optical memory medium, a magnetic memory medium or other recording media, or could be realized by firmware. The video processor (such as an encoder or a microprocessor) of a computation apparatus could read the memory medium recording the programming code of the method of the embodiments and further perform the programming code to implement the method of the embodiments. Moreover, the method of the above embodiments could be implemented by combining software and hardware. 
     The first embodiment of the disclosure provides a method for motion estimation, which reduces the number of the modes requiring fractional motion estimation, hence increasing the efficiency of fractional motion estimation. The second embodiment provides a method for motion estimation, which reduces the number of search positions during fractional motion estimation, so that the required computation resources or hardware resources are reduced. Under the circumstances that the number of the modes requiring fractional motion estimation is decreased according to the above embodiments, fractional motion estimation could be performed with fewer search positions. Thus, the complexity and the required computation time for coding are reduced, and the overall computation time of motion estimation is largely reduced in comparison to the implementation which performs fractional motion estimation with respect to all modes. 
     While the disclosure has been described by way of example and in terms of the preferred embodiment(s), it is to be understood that the disclosure is not limited thereto. On the contrary, it is intended to cover various modifications and similar arrangements and procedures, and the scope of the appended claims therefore should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements and procedures.