Apparatus and method for motion estimation and image processing apparatus

A motion estimation apparatus and method for quickly performing video encoding based on a user input through a user input device are provided. The motion estimation apparatus includes an input receiver for receiving a user input, an input pattern analysis unit for analyzing the received user input and determining a user input pattern according to the analyzed user input, a storage for storing history information of a motion vector according to the user input pattern, and a motion estimator for initially estimating a motion vector of a motion estimation block of a current frame with reference to history information of a motion vector corresponding to the user input pattern stored in the storage, deciding a search location of a block matching the motion estimation block from a reference frame, and performing motion estimation on the motion estimation block using the decided search location.

This application claims priority under 35 U.S.C. §119(a) to a Korean Patent Application filed in the Korean Intellectual Property office on Feb. 17, 2010 and assigned Serial No. 10-2010-0014373, the entire disclosure of which is incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to an apparatus and method for image processing, and more particularly, the present invention relates to an apparatus and method for performing video encoding using motion estimation.

2. Description of the Related Art

With the development of cloud computing and remote desktop programs, various methods of transmitting images remotely have been introduced. Before transmitting data, conventional remote desktops compress the data using a video encoding technique in order to reduce the amount of data transmitted. This compression is especially useful for transmission of complex video with largely varying images, such as video corresponding to video games, three-dimensional (3D) graphic programs, video from video player programs, etc. Processing for encoding large amounts of video data, such as in the above-described complex videos, requires a lot of time, which makes it difficult to guarantee real-time transmission of encoded and/or compressed video data.

SUMMARY OF THE INVENTION

An aspect of embodiments of the present invention is to address at least the problems and/or disadvantages described above and to provide at least the advantages described below. Accordingly, an aspect of embodiment of the present invention is to provide a motion estimation apparatus and method for quickly performing video encoding based on a user input through a user input device, and an image processing apparatus including the motion estimation apparatus.

In accordance with an aspect of the present invention, there is provided a motion estimation apparatus. The apparatus includes an input receiver for receiving user input; an input pattern analysis unit for analyzing the received user input and determining a user input pattern according to the analyzed user input; a storage for storing history information of a motion vector according to the user input pattern; and a motion estimator for initially estimating a motion vector of a motion estimation block of a current frame with reference to the history information of the motion vector corresponding to the user input pattern stored in the storage, deciding a search location of a block matching the motion estimation block from a reference frame using the initially estimated motion vector, and performing motion estimation on the motion estimation block using the decided search location.

In accordance with another aspect of the present invention, there is provided an image processing apparatus. The apparatus includes a communication unit for communicating with a terminal through a network; a virtualized user input unit for receiving user input transmitted from the terminal through the communication unit; an application execution unit for executing an application according to the user input and creating a plurality of image frames; and an encoder for encoding the plurality of image frames. The encoder performs motion estimation on each block of a current frame by analyzing the user input, determining a user input pattern according to the analyzed user input, initially estimating a motion vector of a motion estimation block of the current frame using history information of a motion vector corresponding to the user input pattern, and deciding a search location of a block matching the motion estimation block from a reference frame using the initially estimated motion vector.

In accordance with another aspect of the present invention, there is provided a motion estimation method. The method includes receiving a user input; analyzing the received user input; determining a user input pattern according to the analyzed user input; initially estimating a motion vector of a motion estimation block of a current frame with reference to history information of a motion vector corresponding to the user input pattern, wherein the user input pattern is stored in a storage that stores motion vector history information according to user input patterns; deciding a search location of a block matching the motion estimation block from a reference frame, using the initially estimated motion vector; and performing motion estimation on the motion estimation block using the decided search location.

Throughout the drawings, the same drawing reference numerals will be understood to refer to the same elements, features, and structures. The relative size and depiction of these elements may be exaggerated for clarity, illustration, and convenience.

The following description is provided to assist a comprehensive understanding of the methods, apparatuses, and/or systems described herein. Accordingly, those of ordinary skill in the art will recognize that various changes, modifications, and equivalents of the methods, apparatuses, and/or systems described herein can be made without departing from the scope and spirit of the invention. Also, descriptions of well-known functions and constructions may be omitted for increased clarity and conciseness.

FIG. 1is a diagram illustrating an example of a motion estimation apparatus according to an embodiment of the present invention.

Referring toFIG. 1, a motion estimation apparatus100includes an input receiver110, an input pattern analysis unit120, a motion estimator130, and a storage140.

The input receiver110receives user input. The input receiver110is configured to receive user input signals created by a user input device, such as a keyboard, a touch pad, a joystick, or a remote controller, etc. A user input signal may be packetized and transmitted to the input receiver110through a network. For example, the user input may be input through a single key or button, or input through several keys or buttons.

The input pattern analysis unit120analyzes the received user input and decides a user input pattern. The input pattern analysis unit120identifies the type of a user input device and an input value according to the type of the user input device from the user input signal and determines the user input pattern based on the type of user input device and the input value. Analysis of an input pattern may be performed on a user's transient input signal or on a combination of user's input signals received during a certain time interval.

The user input signal may include type information indicating the type of a user input device and an input value, which may include one or more values according to the type of the user input device. When the input pattern is a mouse input, the input value may further indicate a location of the mouse or a location change corresponding to a unit of time. The input value may be a real input value input through a user input device or a value obtained by processing a real input value input through a user input device. For example, the input value may be a mouse input value that is acquired as a representative value indicating a range of location changes in a unit of time.

The motion estimator130performs motion estimation on a received frame. The motion estimation may be performed in units of blocks with respect to a reference frame.

FIG. 2is a diagram illustrating an example of a method of estimating a motion vector for each block according to an embodiment of the present invention. Referring toFIG. 2, motion estimation, which is denoted by an arrow10in a frame #2220, is generally performed in units of blocks of a certain size in a direction from the upper-left part of the frame #2220toward the lower-right part of the frame #2220. A block on which motion estimation is performed is referred to as a motion estimation block. For example, various block matching algorithms may be used to find a block most similar to a motion estimation block20of the frame #2220from a frame #1210, which is a reference frame. In the present example, block30in frame #1210, is determined to be the block most similar to a motion of the estimation block20of the frame #2220.

The various block matching algorithms may include a full search method, a 3-step search method, a diamond search method, a hexagon-based search method, etc. The full search method compares a motion estimation block of a current frame with all blocks of a reference frame to extract a block having the smallest Sum of Absolute Differences (SAD) between pixels with respect to the motion estimation block from the reference frame. Other block matching algorithms may reduce the amount of calculations by reducing the number of the motion estimation block of reference frames used to calculate SADs with respect to a motion estimation block.

Referring toFIG. 1, the motion estimator130receives the input pattern determined by the input pattern analyzer120and may perform motion estimation according to the input pattern. Conventional motion estimation methods, which are performed based on input images, do not consider any factors that influence the creation of input images. By contrast, in the current example according to an embodiment of the present invention, since the motion estimator130performs motion estimation in consideration of a user input signal, when the user input is used to create input images, motion estimation may be performed more efficiently than conventional motion estimation.

In order to perform motion estimation based on user input, the motion estimator130may store block-based motion vector information, which is acquired as the result of the block-based motion estimation, as motion vector history information, in the storage140.

The storage140stores the motion vector history information in according to user input patterns. The storage140may include a local motion vector history information storing unit142and a global motion vector history information storing unit144.

The local motion vector history information storing unit142may store location motion vector history information that represents histories of motion vectors for individual blocks. The global motion vector history information storing unit144may store global motion vector history information that represents histories of global motion vectors for individual frames.

The motion estimator130initially estimates a motion vector of the motion estimation block, with reference to the motion vector history information stored in the storage140, and decides a search location of a block matching the motion estimation block from a reference frame, using the initially estimated motion vector. The motion estimator130may perform block-based motion estimation on a received image frame using the decided search location.

For example, when estimating a motion of the motion estimation block, the motion estimator130may set a certain range based on the search location decided from the reference frame, and apply the full search algorithm to the range. For example, the motion estimator130may set a certain range centered on the search location. Alternatively, the motion estimator130may execute a search algorithm, such as the 3-step search method, the diamond search method or the hexagon-based search method, based on the search location decided from the reference frame.

The motion estimator130may perform motion estimation based on a user input as necessary, while performing general motion estimation. For example, when no motion vector history information is accumulated in the storage140, the motion estimator130may perform general motion estimation using only frame information, in a manner similar to an initial motion estimation. When errors are accumulated upon motion estimation based on a user inputs, the motion estimator130may perform general motion estimation periodically, or whenever predetermined number of frames is processed.

The motion estimator130may estimate motion vectors of a predetermined number of blocks in a current frame and when a standard deviation between the estimated motion vectors is less than a threshold value, the motion estimator130may determine that a global motion vector exists in the current frame. Then, the motion estimator130may perform initial motion estimation with reference to the global motion vector history information.

The motion estimator130may perform, when finding a predetermined pattern between a plurality of motion vector values included in local motion vector history information of a block corresponding to the motion estimation block, an initial estimation with reference to the local motion vector information. For example, when the amount of changes between a plurality of motion vector values included in local motion vector history information of a block corresponding to the motion estimation block is less than a threshold value, the motion estimator130may determine that a predetermined pattern exists in the plurality of motion vector values, and then perform initial estimation using the amount of changes between the plurality of motion vectors.

The motion estimator130may perform initial estimation by assigning weights to the to plurality of motion vector values included in the motion vector history information such that the larger weights are assigned to the more recently updated motion vector values. Then, the weighted motion vector values may be averaged.

The motion estimator130may manage information stored in the storage140. For example, the motion estimator130may perform motion estimation on the motion estimation block based on the search location decided from the reference frame to create a motion vector of the motion estimation block, and store the motion vector of the motion estimation block as an updated motion vector of the corresponding block in the storage140. When the motion vector history information stored in the storage140is accumulated such as to exceed a predetermined threshold amount, the motion estimator130may delete old motion vector information from the motion vector history information.

Since motion estimation is performed using a block search location based on a user input signal upon video encoding, motion estimation may be performed quickly. Accordingly, when video data is determined to have large weights as a result of the motion estimation, encoding of the video data may be performed quickly and efficiently.

FIG. 3illustrates a configuration example of the local motion vector history information storing unit142included in the storage140ofFIG. 1according to an embodiment of the present invention.

Referring toFIG. 3, the local motion vector history information storing unit142stores motion vectors for input types and input values in association with blocks. Input types and values input through various input devices, such as a keyboard and a mouse, may be used to configure the local motion vector history information.

For example, when a keyboard input corresponding to an input value “Left_arrow” is received, motion vector history information of {(−1, 3), (−5, 1), (−4, −1), (0, 1)} may be stored. In the above sequence, as well as other sequences described with reference toFIGS. 3-5, the values are listed from left to right, in order from oldest history information to newest history information.

FIG. 4is a diagram illustrating a configuration example of the global motion vector history information storing unit144included in the storage140ofFIG. 1according to an embodiment of the present invention.

Referring toFIG. 4, the global vector history information stored in the global motion vector history information storing unit144is used to check whether a global motion vector for a received frame exists. The global motion vector history information may be set and stored in advance. Alternatively, the motion estimator130may calculate and update the global motion vector history information in real time (seeFIG. 1). Input types and values input through various input devices, such as a keyboard and a mouse, may be used to configure global motion vector history information. As illustrated inFIG. 4, the global motion vector history information storing unit144stores global motion vectors for input types and input values in association with input types.

FIG. 5is a diagram illustrating an example of a method of initially predicting a motion vector for a motion estimation block in the motion estimation apparatus100illustrated inFIG. 1according to an embodiment of the present invention.

Referring toFIG. 5, the motion estimator130(seeFIG. 1) performs motion estimation with respect to a current block501, and local motion vector history information for a location corresponding to the current block501is {(−1, 3), (−5, 1), (−4, −1) (0, 1)}.

InFIG. 5, motion vector values are denoted by reference numbers510,520,530, and540. The motion estimator130may assign weights to motion vectors included in the local motion vector history information such that a sum of the weights is “1”. The motion estimator130may assign higher weights to the more recent motion vectors. For example, the motion estimator130may assign a weight 0.4 to a motion vector (−1, 3), a weight 0.3 to the motion vector (−5, 1), a weight 0.2 to a motion vector (−4, −1) and a weight 0.1 to a motion vector (0, 1). A sum of the motion vectors to which the weights are assigned reaches (−2.7, 1.4). (−2.7, 1.4) is rounded off to (−3, 1) which corresponds to a block503inFIG. 5.

The motion estimator130may apply a block matching algorithm to a reference frame based on the block503at the location (−3, 1). For example, the motion estimator130may set a predetermined range centered on the location of the block503on the reference frame and perform the full search method within the predetermined range, or may perform the 3-step search method, the diamond search method or the hexagon-based search method, starting from the block503.

FIG. 6is a diagram illustrating an example of an image processing apparatus600including the motion estimation apparatus100illustrated inFIG. 1according to an embodiment of the present invention.

The image processing apparatus600is an encoding apparatus which performs H.264 encoding on frames using a motion estimator620based on user input.

Referring toFIG. 6, the image processing apparatus600includes an input receiver630, an input pattern analysis unit632, a motion estimator634, a storage636, a motion compensator638, an intra mode predictor640, an intra predictor642, a converter644, a quantizer646, an entropy encoder648, a dequantizer650, an inverter652and a deblocking filter654. In the following description with reference toFIG. 6, frame610represents a current frame and frame620represents a reference frame.

The input receiver630, the input pattern analysis unit632, the motion estimator634and the storage636correspond to the input receiver110, the input pattern analysis unit120, the motion estimator130and the storage ofFIG. 1, respectively, and therefore, further detailed descriptions of these components is omitted.

The motion estimator634searches for a motion vector from a plurality of reference frames620and searches for a macroblock mode type. The motion compensator638acquires a compensated image from the reference frames620according to the motion vector and macroblock mode type found by the motion estimator634.

The intra mode predictor640performs prediction using adjacent blocks upon intra-coding of a macro block to select an optimal intra prediction mode. In the case of an intra 16×16 block, four prediction modes exist and in intra 4×4 mode, 9 the case of an prediction modes exist.

The intra predictor641acquires a compensated image by intra-prediction from the previously coded adjacent blocks using the intra prediction mode selected by the intra mode predictor640.

The converter644performs a 4×4 integer transform, which is a modification of a 4×4 Discrete Cosine Transform (DCT). The quantizer646quantizes coefficients converted by the converter644. Since the 4×4 integer transform defined in the H.264 standard does not have orthogonality, the 4×4 integer transform needs quantization compensation. Accordingly, the converter644is used together with the quantizer646. The inverter652and the dequantizer650perform the inverse operations of the converter644and quantizer646. The image output from the inverter652is a restored image in a state before filtering through the deblocking filter654.

The entropy encoder648performs entropy encoding using bit allocation depending on the generation probability of quantized DCT coefficients.

The deblocking filter654enhances the picture quality of the restored image received from the inverter652. The enhanced image is used as a reference frame620for subsequent images.

The H.264 standard, like existing Motion Picture Experts' Group (MPEG) standards, defines I_Slice, P_Slice, B_Slice, SI_Slice, SP_Slice, etc. The H.264 standard performs encoding in units of slices. For convenience of description, a slice may be considered equivalent to a frame, i.e., the I_Slice is similar to the I_picture defined in the existing MPEG standard, the P_Slice is similar to P_picture defined in the existing MPEG standard, and the B_Slice is similar to B_picture defined in the existing MPEG standard, and the SI_Slice and SP_Slice are used for particular purposes.

When I_Slice is received, neither the motion estimator634nor the motion compensator638operates, and the intra mode predictor640and the intra predictor642optimally perform intra prediction. The result of the intra prediction is acquired as a difference image between the compensated image and the original image. Then, the acquired difference image is input to the converter644and the quantizer646, thereby acquiring a quantized DCT coefficient. The entropy encoder648performs entropy encoding on the quantized DCT coefficient, thus creating a bit string.

After the bit string is created, next slices are subjected to the dequantizer650and the inverter652to restore a difference image. Then, the restored the difference image is combined with a compensated image, thus creating a restored image. The restored image is used as a reference frame620after passing through the deblocking filter654. In the present example, images to be subjected to intra prediction have not passed through the deblocking filter654.

When a P_Slice is received, the motion estimator634and the motion compensator638decide an optimal motion vector for the P_Slice and a macro block mode. Then, the inter mode predictor640and the intra predictor642optimally perform intra prediction. Thereafter, the execution result from the motion compensator638is compared with the execution result from the intra predictor642to select one of the two execution results as a compensated image. The following B_Slice operations are similar to the above-described operations in association with I_Slice.

When B_Slice is received, the B_Slice is processed in a manner similar to processing for the P_Slice, except that, for the B_Slice, future images as well as previous images are used as reference images when the motion predictor634and the motion compensator638are executed.

FIG. 7is a diagram illustrating an example of a system700of providing video services using the motion estimation apparatus illustrated inFIG. 1according to an embodiment of the present invention.

The system700of providing video services includes an application server710and a terminal720. The application server710and the terminal720may be connected to each other through a wired or wireless network.

The application server710executes an application requested by a user of the terminal720and provides video as an execution result of the application. The application server710may be a server providing a cloud computing service, a virtual machine, a general personal computer that is used as a remote desktop, etc.

The application server710includes a communication unit711, a virtualized input unit712, an application execution unit713, a virtualized output unit714, and an encoder715.

The communication unit711communicates with the terminal720. When a user input is packetized and transmitted to the communication unit711, the communication unit711may depacketize the packetized user input and then transfer the depacketized user input to the virtualized input unit712. The virtualized input unit712may function as the input receiver110by transferring the user input to the encoder715.

The application execution unit713executes the application requested by the user of the terminal720. The application execution unit713may create video including a plurality of frames corresponding to the execution results of the application, while executing the application according to a user input received from the virtualized input unit712. The created video is transferred to the encoder715through the virtualized output unit714.

The encoder715may include a configuration similar to the image processing apparatus600ofFIG. 6, but excluding the input receiver630. The encoder715performs motion estimation based on a user input to encode video, which has been described above with reference toFIGS. 1 through 6. The encoder715analyzes a received user input to decide a user input pattern and initially estimates a motion vector using motion vector history information corresponding to the user input pattern in order to perform block-based motion estimation on image frames. Then, the encoder715decides a search location of a block matching a motion estimation block from a reference frame, using the initially estimated motion vector. The encoded video, i.e., the plurality of frames, is transferred to the terminal720through the communication unit711.

The terminal720, which a user terminal, includes a user input unit721, a communication unit722, a communication unit722, a decoder723and a display724.

The user input unit721allows a user to enter user input to be transferred to the application execution unit713of the application server710. The user input unit721may be one of various user input devices, such as a keyboard, a mouse, a game pad, a remote controller, etc. The user input unit721may transfer information indicating a type of a user input device and an input value that are input by the user, to the communication unit722.

The communication unit722transfers the user input received through the user input unit721to the application server710. The communication unit722receives the encoded video from the application server710and transfers the encoded video to the decoder723.

The decoder723decodes the encoded video and transfers the decoded video to the display724. The display724may display the received video.

The terminal720may further include an audio decoding module and an audio output unit. The terminal720has no application execution module and may display the execution results of a requested application received from the application server710.

FIG. 8is a flowchart illustrating an example of a motion estimation method according to an embodiment of the present invention.

Referring toFIGS. 1 and 8, the input receiver110of the motion estimation apparatus100receives a user input, in step810. The input pattern analysis unit120analyzes the received user input to decide a user input pattern, in step820. The user input pattern may be analyzed as a type of a user input device and an input value according to the type of the user input device.

The motion estimator130performs an initial estimation of a motion vector of a motion estimation block with reference to history information of a motion vector corresponding to the user input pattern from the storage140, which stores history information of motion vectors according to user input patterns, in step830.

The motion estimator130decides a search location of a block matching a motion estimation block from a reference frame according to the initially estimated motion vector, in step840.

The motion estimator130performs motion estimation using the decided search location, in step850.

The motion estimator130may further store local motion vector history information representing histories of motion vectors for individual blocks and global motion vector history information representing histories of global motion vectors for individual frames, in the storage140. The motion estimator130may also manage motion vector history information stored in the storage140.

FIG. 9is a flowchart illustrating another example of a motion estimation method according to an embodiment of the present invention.

Referring toFIGS. 1 and 9, the input pattern analysis unit120of the motion estimation apparatus100analyzes a received user input to decide a user input pattern, in step910. The motion estimator130may perform Motion Estimation (ME) based on user input or may perform general motion estimation according to a predetermined method when errors are accumulated, upon motion estimation based on user input.

Upon a determination that the motion estimator130must perform general motion estimation in step912, the motion estimator130performs general motion estimation on a current motion estimation block, in step914.

When the motion estimator130performs motion estimation based on user inputs, a determination of whether a global Motion Vector (MV) for a current frame exists is performed, in step916. The motion estimator130may determine that a global motion vector for a current frame exists, when a standard deviation between motion vectors, which are obtained as the results of motion estimation performed on representative blocks predetermined for a current frame before motion estimation of a current motion estimation block, is less than or equal to a threshold value.

Upon a determination that a global motion vector exists in step916, the motion estimator130decides a search location from a reference frame using global motion vector history information, in step926. Then, the motion estimator130performs motion estimation using the decided search location, in step928. Then, the motion estimator130updates the global motion vector history information storage144using the results of the motion estimation, in step930.

Upon a determination that no global motion vector exists in step916, the motion estimator130determines whether a pattern exists between a plurality of motion vectors included in the local motion vector history information, in step918.

Upon a determination that a pattern exists between the motion vectors included in the motion vector history information, the motion estimator130decides a search location using the local motion vector history information in step920, and perform motion prediction using the search location, in step922. Then, the motion estimator130updates the local motion vector history information storage142using the results of the motion estimation, in step922. Upon a determination that no pattern exists between the motion vectors included in the local motion vector history information in step920, the motion estimator130may perform general motion estimation, in step914.

If the current motion estimation block is determined to be a final block of a current frame in step932, the motion estimation is terminated. However, if the current motion estimation block is not a final block, the process may return to operation912.

The processes, functions, methods and/or software described above may be recorded, stored, or fixed in one or more computer-readable storage media that includes program instructions to be implemented by a computer to cause a processor to execute or perform the program instructions. The media may also include, alone or in combination with the program instructions, data files, data structures, etc. The media and program instructions may be those specially designed and constructed, or they may be of the kind well-known and available to those having skill in the computer software arts. Examples of computer-readable media include magnetic media, such as hard disks, floppy disks, and magnetic tape; optical media such as Compact Disc (CD)-Read Only Memory (ROM) disks and Digital Versatile Discs (DVDs); magneto-optical media, such as optical disks; and hardware devices that are specially configured to store and perform program instructions, such as ROM, Random Access Memory (RAM), flash memory, etc. Examples of program instructions include machine code, such as produced by a compiler, and files containing higher level code that may be executed by the computer using an interpreter. The described hardware devices may be configured to act as one or more software modules in order to perform the operations and methods described above, or vice versa. In addition, a computer-readable storage medium may be distributed among computer systems connected through a network and computer-readable codes or program instructions may be stored and executed in a decentralized manner.