Frame interpolation apparatus and method for motion estimation through separation into static object and moving object

Provided are frame interpolation apparatus and methods in which motion estimation is performed by separation into a static object and a moving object. The frame interpolation apparatus interpolates multiple frames including an nth frame and an (n−1)th frame located adjacent the nth frame in order to generate an interpolation frame. Some embodiments of the apparatus include a static object separation unit, a motion vector (MV) estimation unit, and an interpolation frame generation unit. The static object separation unit may compare a macroblock (MB) of the nth frame with an MB of the (n−1)th frame, which may correspond to the MB of the nth frame, in order to separate each MB of the nth frame into a static object and a moving object. The MV estimation unit may search in the (n−1)th frame for an MB that matches with each of MBs of the nth frame, which may be determined to be the moving object, to estimate an MV. The interpolation frame generation unit may generate the interpolation frame using the estimated MV, the nth frame, and the (n−1)th frame.

CROSS-REFERENCE TO RELATED PATENT APPLICATION

This application claims the benefit of Korean Patent Application No. 10-2007-0011259, filed on Feb. 2, 2007, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.

BACKGROUND OF THE INVENTION

The present invention generally relates to electronic display control, and more particularly, to a frame rate conversion apparatus and method in which frames are converted.

Conventionally, in personal computers (PC) or high-definition televisions (HDTV), frame rate conversion may be performed for compatibility between programs having various broadcasting signal standards such as PAL or NTSC. Frame rate conversion may mean conversion of the number of frames that are output per second. In particular, when a frame rate is increased, interpolation of a new frame may be required. The interpolated frame may be referred to as an interpolation frame. To generate the interpolation frame, motion estimation (ME) may be used. ME may include searching for the most similar blocks between a previous frame and a current frame. A motion vector (MV) may indicate a magnitude of block's movement in ME.

A conventional ME method may be used to reduce temporal redundancy of video data and to generate the MV. Among various ME methods for generating the MV, a block matching algorithm (BMA) may be used. The BMA may search for movement in each block and apply a motion vector corresponding to the movement to all pixels included in the block. The BMA may require a small amount of time to be executed and can be easily implemented as hardware. In a general video, motions can be classified into rotation, translation, and zoom-in/out. In this regard, it may be assumed that a motion between frames having a very small interval therebetween is very little. Therefore, the BMA may be performed on the assumption that there is only translation in a video and motions of all pixels in the same block are the same. Thus, the BMA may search for a block that is most similar to a current block of a current frame in a search range of a previous frame and determine a displacement between the two blocks as an MV. This process may be called a full search. Each block may be composed of 16×16 pixels and may be called as a macroblock (MB).

Since the full search may perform comparison with all pixels included in the search range, it can find an MV having the smallest matching error. However, the full search may require significant computation resources. In other words, the conventional BMA may result in unnecessary computation and power consumption because it may perform ME even for a portion having no motion. Moreover, the conventional BMA may perform a wrong ME by not distinguishing between a static object and a moving object. In this regard, degradation in display quality may result when the wrong ME is applied to an interpolated image.

SUMMARY

Some embodiments of the present invention provide a frame interpolation apparatus capable of generating an accurate interpolation frame through low-power driving and an accurate true motion vector by separation into a static object and a moving object, performing motion estimation only on the moving object, and performing motion estimation in a modified search range. Some embodiments of a frame interpolation apparatus that interpolates multiple frames including an nthframe and an (n−1)thframe located adjacent to the nthframe to generate an interpolation frame may include a static object separation unit that is configured to compare an nthframe macroblock (MB) of multiple nthframe MBs with an (n−1)thframe MB of multiple (n−1)thframe MBs to separate the nthframe MB into a static object and a moving object and a motion vector (MV) estimation unit that is configured to search the (n−1)thframe for an MB that matches the nthframe MB that is determined to be the moving object to estimate an MV. Some embodiments may include an interpolation frame generation unit that is configured to generate the interpolation frame using the estimated MV, the nthframe, and the (n−1)thframe.

In some embodiments, the MV estimation unit includes a search range processing unit that is configured to search in a first search range of the (n−1)thframe for the MB that matches with the nthframe MB to estimate a first MV, a modified search range processing unit that is configured to search in a second search range of the (n−1)thframe for the MB that matches with the nthframe MB to estimate a second MV, and a current MB processing unit that is configured to match nthframe MB with an (n−1)thframe MB of the plurality of (n−1)thframe MBs, which corresponds to the nthframe MB to estimate a third MV. In some embodiments, the first search range includes MBs of the (n−1)thframe and the second search range includes the (n−1)thframe MBs that correspond to nthframe MBs that are determined to be the moving object.

In some embodiments, the first search range includes the (n−1)thframe MB that corresponds to the matching nthframe MB and the (n−1)thframe MBs that are adjacent the corresponding (n−1)thframe MB. In some embodiments, the second search range includes the (n−1)thframe MB that corresponds to the matching nthframe MB and (n−1)thframe MBs that adjacent the corresponding (n−1)thframe MB and that corresponds to the nthframe MBs determined to be moving objects.

In some embodiments, the search range processing unit is configured to calculate a sum of absolute differences (SAD) for matching MBs and to estimate the first MV between an (n−1)thframe MB that has a minimum SAD and the nthframe MB. Some embodiments provide that the modified search range processing unit is configured to calculate a sum of absolute differences (SAD) for matching MBs and to estimate the second MV between an (n−1)thframe MB that has a minimum SAD, and the nthframe MB. In some embodiments, the current MB processing unit is configured to calculate a sum of absolute differences (SAD) for matching MBs to estimate the third MV.

Some embodiments provide that the interpolation frame generation unit is configured to generate the interpolation frame using a median value of the estimated first MV, the estimated second MV, and the estimated third MV. In some embodiments, the interpolation frame generation unit is configured to generate the interpolation frame using a median value of the nthframe MB and the (n−1)thframe MB when a matching MB that matches with the nthframe MB of exists in the (n−1)thframe.

In some embodiments, the interpolation frame generation unit is configured to generate the interpolation frame using the nthframe MB or the (n−1)thframe MB according to a direction of the estimated MV when a matching MB that matches with the nthframe MB does not exist in the (n−1)thframe. In some embodiments, the interpolation frame generation unit uses the nthframe MB when a direction of the estimated MV is from left to right and uses the (n−1)thframe MB when a direction of the estimated MV is from right to left. In some embodiments, the static object separation unit is configured to calculate a difference between luminance signals of the nthframe MB and a corresponding (n−1)thframe MB, compare the difference with a threshold that is a criterion for distinguishing the moving object from the static object, and separate each of the plurality of nthframe MBs into the static object and the moving object.

In some embodiments, the static object separation unit is configured to determine the nthframe MB as the moving object when the difference is greater than the threshold and to determine the nthframe MB as the static object when the difference is less than the threshold. In some embodiments, the MV estimation unit is configured to search in a search range of the (n−1)thframe for an MB that matches with an MB of the nthframe to estimate the MV, wherein the search range includes an (n−1)thframe MB that corresponds to the nthframe MB and the (n−1)thframe MBs that are adjacent the (n−1)thframe MB that corresponds to the nthframe MB.

Some embodiments of the present invention include a frame interpolation apparatus that interpolates multiple frames including an nth frame and an (n−1)thframe located adjacent the nthframe in order to generate an interpolation frame. Some embodiments of such an apparatus include a static object separation unit that is configured to compare an nthframe macroblock (MB) with an (n−1)thframe MB that corresponds to the nthframe MB to separate each of multiple nthframe MBs into a static object and a moving object and a motion vector (MV) estimation unit that is configured to search in a search range of the (n−1)thframe for an MB that matches each of the nthframe MBs that are determined to be the moving object to estimate an MV. Some embodiments include an interpolation frame generation unit that is configured to generate the interpolation frame using the estimated MV, the nthframe, and the (n−1)thframe, such that the search range includes the (n−1)thframe MBs that correspond to each of the nthframe MBs that are determined to be the moving object.

In some embodiments, the search range includes the (n−1)thframe MB that corresponds to a matching nthframe MB and the (n−1)thframe MB's that are located adjacent a corresponding (n−1)thframe MB and that correspond to the nthframe MBs that are determined to be the moving object. Some embodiments provide that the interpolation frame generation unit is configured to generate the interpolation frame using a median value of the nthframe MB and the (n−1)thframe MB when an MB that matches the nthframe MB exists in the (n−1)thframe.

In some embodiments, the interpolation frame generation unit is configured to generate the interpolation frame using the nthframe MB or the (n−1)thframe MB according to a direction of the estimated MV when an (n−1)thframe MB that matches with the nthframe MB does not exist in the (n−1)thframe.

In some embodiments, the static object separation unit is configured to calculate a difference between luminance signals of the nthframe MB and a corresponding (n−1)thframe MB, to compare the difference with a threshold that is a criterion for distinguishing the moving object from the static object, and to separate each nthframe MB into the static object and the moving object.

Some embodiments of the present invention include interpolation methods that interpolate multiple frames including an nthframe and an (n−1)thframe that is located adjacent the nthframe to generate an interpolation frame. Some embodiments of such methods include comparing an nthframe macroblock (MB) with an (n−1)thframe MB that corresponds to the nthframe MB to separate each of multiple nthframe MBs into a static object and a moving object and searching in the (n−1)thframe for an MB that matches each of the nthframe MBs that are determined to be the moving object. Some embodiments include estimating a motion vector (MV) responsive to the MB that matches each of the plurality of nthframe MBs that are determined to be the moving object and generating the interpolation frame using an estimated MV, the nthframe, and the (n−1)thframe.

In some embodiments, estimating the MV includes searching in a first search range of the (n−1)thframe for an MB that matches each of the nthframe MBs to estimate a first MV, searching in a second search range of the (n−1)thframe for an MB that matches each of the nthframe MBs to estimate a second MV, and matching an nil frame MB with an (n−1)thframe MB that corresponds to the nthframe MB to estimate a third MV. In some embodiments, the first search range includes the (n−1)thframe MBs and the second search range includes the (n−1)thframe MBs that correspond to the nthframe MBs that are determined to be the moving object.

In some embodiments, the first search range includes the (n−1)thframe MB that corresponds to the matching nthframe MB and the (n−1)thframe MBs that are located adjacent to the corresponding (n−1)thframe MB. In some embodiments, the second search range includes the (n−1)thframe MB that corresponds to a matching nthframe MB and the (n−1)thframe MBs that are adjacent the corresponding (n−1)thframe MB and correspond to the nthframe MBs that are determined to be the moving object.

In some embodiments, estimation of the first MV includes calculating a sum of absolute differences (SAD) for matching MBs and estimating the first MV between an (n−1)thframe MB that has a minimum SAD and the nthframe MB. In some embodiments, estimation of the second MV includes calculating a sum of absolute differences (SAD) for matching MBs and estimating the second MV between an (n−1)thframe MB that has the minimum SAD and the nthframe MB. In some embodiments, estimation of the third MV includes calculating a sum of absolute differences (SAD) for matching MBs to estimate the third MV.

In some embodiments, generating the interpolation frame includes selecting a median value of the estimated first MV, the estimated second MV, and the estimated third MV and generating the interpolation frame using the selected median value.

In some embodiments, generating the interpolation frame includes determining whether an MB that matches the nthframe MB exists in the (n−1)thframe, generating the interpolation frame using a median value of the nthframe MB and the (n−1)thframe MB when an MB that matches the nthframe MB exists in the (n−1)thframe and generating the interpolation frame using the nthframe MB or the (n−1)thframe MB according to a direction of the estimated MV when an MB that matches the nthframe MB does not exist in the (n−1)thframe.

In some embodiments, generating the interpolation frame according to the direction of the estimated MV includes determining the direction of the estimated MV, generating the interpolation frame using the nthframe MB when the direction of the estimated MV is from left to right and generating the interpolation frame using the (n−1)thframe MB when the direction of the estimated MV is from right to left.

In some embodiments, comparing an nthframe macroblock (MB) with an (n−1)thframe MB that corresponds to the nthframe MB to separate each of multiple nthframe MBs into a static object and a moving object includes calculating a difference between luminance signals of the nthframe MB and the corresponding (n−1)thframe MB and comparing the difference with a threshold that is a criterion for distinguishing the moving object from the static object. Some embodiments include separating each of the nthframe MBs into the static object and the moving object.

In some embodiments, separating each of the nthframe MBs includes determining the nthframe MB as the moving object when the difference is greater than the threshold and determining the nthframe MB as the static object when the difference is less than the threshold.

In some embodiments, estimation of the MV includes searching in a search range of the (n−1)thframe for an MB that matches an nthframe MB to estimate the MV, wherein the search range includes an (n−1)thframe MB that corresponds to a matching nthframe MB and (n−1)thframe MBs that are adjacent a corresponding (n−1)thframe MB.

Some embodiments of the present invention include frame interpolation methods that interpolates multiple frames including an nthframe and an (n−1)thframe that is located adjacent the nthframe to generate an interpolation frame. Methods of some embodiments include comparing an nthframe macroblock (MB) in the nthframe with an (n−1)thframe MB in the (n−1)thframe that corresponds to the nthframe MB to separate each of multiple nthframe MBs into a static object and a moving object. Some embodiments may include searching in a search range of the (n−1)thframe for an MB that matches with each of the nthframe MBs that are determined to be the moving object to estimate a motion vector (MV) and generating the interpolation frame using an estimated MV, the nthframe, and the (n−1)thframe. In some embodiments, the search range includes the (n−1)thframe MBs that correspond to the nthframe MBs that are determined to be the moving object.

In some embodiments, the search range includes the (n−1)thframe MB that corresponds to a matching nthframe MB and multiple (n−1)thframe MBs that are adjacent a corresponding (n−1)thframe MB and that correspond to the nthframe MBs that are determined to be the moving object.

In some embodiments, generating the interpolation frame includes determining whether an MB that matches the nthframe MB exists in the (n−1)thframe, generating the interpolation frame using a median value of the nthframe MB and the (n−1)thframe MB when the MB that matches the nthframe MB exists in the (n−1)thframe, and generating the interpolation frame using the nthframe MB or the (n−1)thframe MB according to a direction of the estimated MV when the MB that matches the nthframe MB does not exist in the (n−1)thframe.

In some embodiments, generating the interpolation frame according to a direction of the estimated MV includes determining the direction of the estimated MV, generating the interpolation frame using the nthframe MB when the direction of the estimated MV is from left to right, and generating the interpolation frame using the (n−1)thframe MB when the direction of the estimated MV is from right to left. In some embodiments, comparing an nthframe macroblock (MB) in the nthframe with an (n−1)thframe MB in the (n−1)thframe that corresponds to the nthframe MB to separate each of a plurality of nthframe MBs into a static object and a moving object includes calculating a difference between luminance signals of the nthframe MB and a corresponding (n−1)thframe MB, comparing the difference with a threshold that is a criterion for distinguishing the moving object from the static object, and separating each of the nthframe MBs into the static object and the moving object.

DETAILED DESCRIPTION OF THE INVENTION

Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. It will be further understood that terms used herein should be interpreted as having a meaning that is consistent with their meaning in the context of this disclosure and the relevant art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.

Reference is now made toFIG. 1, which is a block diagram of a frame interpolation apparatus100according to some embodiments of the present invention. The frame interpolation apparatus100may include a static object separation unit110, a motion vector (MV) estimation unit130, and an interpolation frame generation unit170. The frame interpolation apparatus100may generate an interpolation frame by interpolating an nthframe and an (n−1)thframe, in which n is an integer greater than 2. The nthframe may be a current frame and the (n−1)thframe may be a previous frame that immediately precedes the current frame. The static object separation unit110may separate the nthframe into a static object and a moving object in units of a macroblock (MB). In other words, the frame interpolation apparatus100may compare each MB of the nthframe with a corresponding MB of the (n−1)thframe and separate each MB of the nthframe into a static object and a moving object.

The MV estimation unit130may search in the (n−1)thframe for an MB that matches with each of MBs of the nthframe, which may be determined to be the moving object. In this manner, an MV may be estimated. The MV estimation unit130may include a search range processing unit140, a modified search range processing unit150and a current MB processing unit160. The search range processing unit140may search in a first search range of the (n−1)thframe for an MB that matches with each of the MBs of the nthframe. In this manner, a first MV may be estimated. The first search range may include the matching MB of the (n−1)thframe and MBs of the (n−1)thframe, which may be located adjacent the matching MB of the (n−1)thframe. In other words, the search range processing unit140may estimate an MV using a full search. The modified search range processing unit150may search in a second search range of the (n−1)thframe for an MB that matches with each of the MBs of the nthframe. Thus, a second MV may be estimated. The second search range may include MBs of the (n−1)thframe, which may correspond to the MBs of the nthframe determined to be the moving object. The current MB processing unit160may match an MB of the nthframe with an MB of the (n−1)thframe corresponding to the MB of the nthframe. Thus, a third MV may be estimated. The static object separation unit110, the search range processing unit140, the modified search range processing unit150, and the current MB processing unit160will be described later in more detail with reference toFIGS. 3 through 6.

The interpolation frame generation unit170may generate the interpolation frame using an estimated MV, the nthframe, and the (n−1)thframe. The interpolation frame generation unit170may generate the interpolation frame using a median value of the estimated first MV, the estimated second MV, and/or the estimated third MV. The interpolation frame generation unit170may use different frame interpolation methods according to whether an MB of the (n−1)thframe, which matches with an MB of the nthframe, distinctly exists. In this manner, an occlusion region may be processed. The operation of the interpolation frame generation unit170will be described later in more detail with reference toFIGS. 7 through 9.

Reference is now made toFIG. 2, which illustrates a frame that is divided into MBs according to some embodiments of the present invention. A single frame may be divided into a plurality of MBs, each of which may be composed of, for example, 16×16 pixels. In some embodiments, each of the MBs may also be composed of a variety of quantities and/or configurations of pixels.

Reference is now made to:FIG. 3, which is a flowchart of frame interpolation methods according to some embodiments of the present invention;FIGS. 4 and 5, which illustrate frames410and450divided into macroblocks in operations of the static object separation unit110illustrated inFIG. 1; andFIGS. 6A through 6C, which illustrate frames410and450divided into macroblocks in operations of the motion vector estimation unit130illustrated inFIG. 1. Referring toFIGS. 1 and 3through6C, the static object separation unit110may calculate a difference between luminance values of an MB of the nthframe and an MB of the (n−1)thframe (block310). The difference ImgDiffcan be calculated as follows:
ImgDiff=|f(x,y,n−1)−f(x,y,n)|  (1),

where f( ) indicates a luminance value of a frame, x and y indicate the spatial position of the frame, and n and (n−1) indicate frame numbers.

As illustrated inFIG. 4, when an nthframe450is divided into 5×5 MBs MB′_11, MB′_12, . . . , MB′_55and an (n−1)thframe410is divided into 5×5 MBs MB_11, MB_12, . . . , MB_55, the difference ImgDifffor an MB of the nthframe450and an MB of the (n−1)thframe450corresponding thereto is calculated. In other words, a difference between a luminance value of the MB MB′_11of the nthframe450and a luminance value of the MB MB_11of the (n−1)thframe410may be calculated and a difference between a luminance value of the MB MB′_12of the nthframe450and a luminance value of the MB MB_12of the (n−1)thframe410may be calculated. In this manner, the differences ImgDifffor the other MBs may be calculated.

In some embodiments, the static object separation unit110may compare the difference with a threshold that is a criterion for distinguishing a moving object from a static object (block320). The difference may be large for a moving object, while the difference may be small for a static object. Thus, the static object separation unit110may compare the difference with the threshold in order to determine that a corresponding MB is a moving object if the difference is greater than the threshold and that the MB is a static object if the difference is less than the threshold. Once separation into a moving object and/or a static object for each MB of the nthframe450is finished, “1” is allocated to an MB determined to be a moving object and “0” is allocated to an MB determined to be a static object as illustrated inFIG. 5. In this manner, a binarized image may be implemented. In the following description, motion estimation (ME) may be performed only on MBs allocated “1”. Since MBs allocated “0” are determined to be static objects, an interpolation frame may generated using corresponding MBs of (n−1)thframe without ME for the MBs allocated “0”.

The search range processing unit140, the modified search range processing unit150, and the current MB processing unit160may estimate the first MV, the second MV, and the third MV for the MBs that are determined to be a moving object.

Hereinafter, the operations of the search range processing unit140according to some embodiments will be described with reference toFIG. 6A. In order to process an MB610of the nthframe450, the search range processing unit140may search for an MB that matches with the MB610of the nthframe in a first search range630of the (n−1)thframe410. In this manner, the first MV may be estimated (block330). The first search range630may include an MB MB_33of the (n−1)thframe410corresponding to the MB610of the nthframe450and MBs MB_22, MB_23, MB_24, MB_32, MB_34, MB_42, MB_43, and MB_44of the (n−1)thframe410, which are located adjacent to the MB MB_33. Although, as illustrated, the MBs included the first search range have a size of 3×3, in some embodiments they may also have a size of 4×4, 4×5 and/or 5×5, among others.

The operation of the modified search range processing unit150according to some embodiments will now be described with reference toFIG. 6B. In order to process the MB610of the nthframe450, the modified search range processing unit150may search for an MB that matches with the MB610of the nthframe in a second search range650of the (n−1)thframe410. In this manner, the second MV may be estimated (block340). The second search range650may include the MB MB_33of the (n−1)thframe410corresponding to the MB610of the nthframe450. The second search range650may include MBs MB_22, MB_23, MB_24, MB_32, MB_33, and MB_34of the (n−1)thframe410, which are located adjacent to the MB MB_33and correspond to MBs MB′_22, MB′_23, MB′_24. MB′_32, MB′_33, and MB′_34of the nthframe450, which are determined to be the moving object. In other words, only the MBs MB_22, MB_23, MB_24, MB_32, MB_33, and MB_34of the (n−1)thframe410, which correspond to the MBs MB′_22, MB′_23, MB′_24, MB′_32, MB′_33, and MB′_34allocated “1” out of the MBs of the nthframe450, may be defined as the second search range650.

Operations of the current MB processing unit160according to some embodiments will now be described with reference toFIG. 6C. In order to process the MB610of the nthframe450, the current MB processing unit160may match the MB610of the nthframe450with the MB MB′_33of the (n−1)thframe410corresponding to the MB610. In this manner, the third MV may be estimated (block350).

For motion vector estimation with the search range processing unit130, the modified search range processing unit150, and the current MB processing unit160, a mean square error (MSE) algorithm, a mean absolute difference (MAD) algorithm, and a sum of absolute difference (SAD) algorithm may be used. Motion vector estimation may be performed using the SAD algorithm, which is described herein. In some embodiments, motion vector estimation may be performed using the MAD algorithm among others within the scope and spirit of the present invention.

SADs between a current MB to be processed and all MBs included in the first search range or the second search range may be calculated using Equation 2. An MV may be determined by a spatial distance between the current MB and an MB having the minimum SAD as in Equation 3. In some embodiments, the SADs may be calculated as follows:

where N indicates the size of the MB, i and j indicate the spatial position of a current frame, n and (n−1) indicate frame numbers, and dx and dy indicate a difference between the positions of MBs of the current frame and a previous frame, i.e., an nthframe and an (n−1)thframe. Using the SADs, an MV for an MB having the minimum SAD may be obtained as follows:

where R indicates a search range for ME. In some embodiments, R may be the first search range, the second search range, and/or the MB MB_33.

The interpolation frame generation unit170may select a median value of the estimated first MV, the estimated second MV, and/or the estimated third MV (block360) and generate the interpolation frame using the selected median value (block370). In some embodiments, when any one of the estimated first, second or third MVs sharply changes, the interpolation frame generation unit170can recognize the MV as noise and remove the MV. Hereinafter, the operations for processing an occlusion region according to some embodiments of the interpolation frame generation unit170will be described.

Reference is now made to:FIG. 7, which is a flowchart of frame interpolation methods considering an occlusion region according to some embodiments of the present invention; andFIGS. 8A and 8B, which illustrate directions of MVs estimated for MBs according to some embodiments of the present invention. Also referring toFIGS. 1 and 4, the interpolation frame generation unit170may determine whether an MB that matches with an MB of the nthframe450distinctly exists in the (n−1)thframe410(block710). In this regard, the interpolation frame generation unit170may determine whether the (n−1)thframe410includes an MB that accurately matches with an MB of the nthframe450. When the MB of the (n−1)thframe410and the MB of the nthframe450accurately match with each other, the SAD may be equal to 0. In this case, the interpolation frame may be generated using a median value of the MB of the nthframe450and its matching MB of the (n−1)thframe410(block720).

If the MB of the (n−1)thframe410, which matches with the MB of the nthframe450, does not distinctly exist, then the occlusion region exists. In this case, an image that does not exist in the (n−1)thframe410may exist in the nthframe450or an image that exists in the (n−1)thframe410may not exist in the nthframe450. When the occlusion region exists, the direction of the estimated MV may be determined as illustrated inFIG. 5A(block730). InFIG. 5A, MBs marked with X may be determined to be a static object. When estimated MVs have directions as illustrated inFIG. 8A, “0” may be allocated to an MB in which the SAD of an MV for the MB is equal to 0 as illustrated inFIG. 8B. When the SAD of an MV for an MB is not equal to 0 and the direction of the MV is from left to right, the MB may be allocated “−1”. When the SAD of an MV for an MB is not equal to 0 and the direction of the MV is from right to left, the MB may be allocated “1”. When “−1” is allocated to an MB of nthframe450, the interpolation frame may be generated using the MB of the nthframe450(block740). When “1” is allocated to the MB of nthframe450, the interpolation frame may be generated using a corresponding MB of the (n−1)thframe410(block750).

Reference is now made toFIG. 9, which illustrates a process of generating an interpolation frame for an occlusion region according to some embodiments illustrated inFIG. 7. A stage (a) for generating an interpolation frame970between a previous frame910and a current frame950will be described first. A portion920that exists in the previous frame910disappears in the current frame950by being occluded by a car. In this case, since an MB corresponding to the portion960moves from right to left, it may be allocated “1” and the interpolation frame970may be generated using the portion920of the previous frame910.

Next, a stage (b) for generating the interpolation frame970between the previous frame950and the current frame910will be described. The portion920that does not exist in the previous frame950exists in the current frame910. Since the MB corresponding to the portion960moves from left to right, it may be allocated “−1” and the interpolation frame970may be generated using the portion920of the current frame910.

Reference is now made toFIG. 10, which is a block diagram of a frame interpolation apparatus1000according to some embodiments of the present invention. A static object separation unit101, a search range processing unit1040, and an interpolation frame generation unit1070may operate in the same manner as the static object separation unit110, the search range processing unit140, and the interpolation frame generation unit170as discussed above regardingFIG. 1. The frame interpolation apparatus1000may obtain a first MV that is the same as that discussed above regardingFIG. 1by the search range processing unit1040whereas the frame interpolation apparatus100illustrated inFIG. 1may obtain three estimated MVs by the MV estimation unit130. Other components of the frame interpolation apparatus1000may function according to those discussed above regardingFIG. 1and thus will not be described again.

Reference is now made toFIG. 11, which is a block diagram of a frame interpolation apparatus1100according to some embodiments of the present invention. A static object separation unit1110, a modified search range processing unit1150, and an interpolation frame generation unit1170operate in a similar manner as those discussed above regardingFIG. 1. The frame interpolation apparatus1100may obtain a second MV that is the same as that discussed above regardingFIG. 1by the modified search range processing unit1150whereas the frame interpolation apparatus100illustrated inFIG. 1may obtain three estimated MVs by the MV estimation unit130. Other components of the frame interpolation apparatus1100may function according to those discussed above regardingFIG. 1and thus will not be described again.

As described herein, according to some embodiments of the present invention, an input video may be separated into a static object and a moving object according to the characteristics of the input video and motion estimation may be performed only on the moving object. In this manner, a display may be driven using less power. Moreover, by performing motion estimation only in a modified search range, unnecessary computation may be reduced and an occlusion region can be processed. Furthermore, since a median value of three estimated motion vectors may be selected, a wrong MV may be corrected and a true motion vector may be obtained, thereby implementing a high-precision video.