Method and apparatus for estimating and compensating spatiotemporal motion of image

A method of estimating and compensating for motion in image decoding are provided. The method involves determining a reference block of a reference frame indicated by a motion vector of a current block of a current frame being decoded, and generating a spatiotemporal estimation block of the current block by using the current frame and the reference frame, when some pixels of the reference block are outside the reference frame.

CROSS-REFERENCE TO RELATED PATENT APPLICATION

This application claims priority from Korean Patent Application No. 10-2007-0086549, filed on Aug. 28, 2007, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a method of estimating and compensating for motion in image encoding and decoding, and more particularly, to a method of estimating and compensating for motion when a current block refers to a region that is outside a reference frame by using a motion vector in image encoding and decoding.

2. Description of the Related Art

Video codecs such as H.263, Moving Picture Experts Group 2 (MPEG 2), MPEG 4, H.264/Advanced Video Coding (AVC), etc. use correlation between frames, perform a method of estimating and compensating for motion, and thereby increase compression efficiency, even when motion of an object appears in an image.

The method of estimating and compensating for motion refers to a reference block of a reference frame to reconstruct a block of a current frame. However, a part of the reference block determined by a motion vector may be outside the reference frame. The conventional video codecs such as H.263, MPEG 2, MPEG 4, H.264/AVC, etc. extend an outside region of the reference frame by using boundary pixels of the reference frame, and thereby estimate the part of the reference block which is outside the reference frame.

FIG. 1is a diagram of a conventional method of estimating and compensating for motion when a reference block is outside a reference frame.

A current block120of a current frame110refers to a reference block160of a reference frame150by a motion vector. A region170included in the reference frame150is inserted into an equivalent region130of the current block120. However, when a part180of the reference block160is outside the reference frame150, an equivalent region140of the current block120referring to the part180that is outside the reference frame150is padded with pixel values of boundary pixels190of the reference frame150. This conventional technique is known as a padding method.

When motion occurs in an outside region of a frame, compression efficiency of a block which refers to the outside of the frame by using the conventional simple padding method is decreased. In particular, compression efficiency of an active image sequence having panning, tilting, zooming in/out, fast camera motion, and fast object motion is greatly decreased.

The conventional padding method extends an outside region of a frame prior to performing a method of compensating for motion, and as such only limited information is used in the padding method. Thus, a region that is related to motion and is outside the frame is not accurately estimated.

SUMMARY OF THE INVENTION

The present invention provides a method and apparatus for accurately estimating and compensating for motion by using information of a region included in a neighboring block of a current block and a reference frame, when a reference block selected by a motion vector of the current block has a region that is outside the reference frame.

The present invention also provides a method and apparatus for estimating and compensating for motion, wherein the method and apparatus use correlation with a neighboring block and a reference frame, and can thereby greatly enhance compression efficiency of an active image sequence having panning, tilting, zooming in/out, fast camera motion, and fast object motion.

According to an aspect of the present invention, there is provided a method of estimating and compensating for motion in image decoding, the method including the operations of determining a reference block of a reference frame indicated by a motion vector of a current block of a current frame being decoded; and generating a spatiotemporal estimation block of the current block by using the current frame and the reference frame, when some pixels of the reference block are outside the reference frame.

When a block region in a same position as a region included in the reference frame is defined to be a first block region, wherein the block region is a part of the reference block, and a block region in a same position as a region excluded from the reference frame is defined to be a second block region, wherein the block region is a part of the reference block, the operation of generating the spatiotemporal estimation block may include the operations of determining the first block region of the reference block to be an estimation region of the first block region of the spatiotemporal estimation block; and generating an estimation region of the second block region of the spatiotemporal estimation block by using at least one of pixel values of neighboring blocks of the current block, and pixel values of an estimation region of the first block region.

When a block region in a same position as a region included in the reference frame is defined to be a first block region, wherein the block region is a part of the reference block, and a block region in a same position as a region excluded from the reference frame is defined to be a second block region, wherein the block region is a part of the reference block, the operation of generating the spatiotemporal estimation block may include the operations of determining pixels of the neighboring blocks of the current block and pixels surrounding the second block region to be a search pattern region, wherein the neighboring blocks are from among regions reconstructed prior to the current block, and the pixels surrounding the second block region are part of the first block region of the spatiotemporal estimation block, when the spatiotemporal estimation block is allocated to the current block; searching for an outside estimation region surrounded by a similar pattern region having a minimum difference compared with the search pattern region in the regions reconstructed prior to the current block; and determining the outside estimation region to be an estimation region of the second block region of the spatiotemporal estimation block.

The operation of searching for the outside estimation region may include the operation of searching for the similar pattern region having a same form as the search pattern region in the regions reconstructed prior to the current block, and having a minimum Sum of Absolute Differences (SAD) between pixel values of the search pattern region and pixel values of the similar pattern region.

The operation of determining the estimation region of the second block region of the spatiotemporal estimation block may include the operations of selecting at least one of a pixel line of the neighboring blocks of the current block and a pixel line surrounding the second block region, wherein the pixel line surrounding the second block region is a part of the first block region of the spatiotemporal estimation block, when the spatiotemporal estimation block is allocated to the current block; and determining pixels of the selected pixel line to be estimation pixels related to pixels of the second block region located either vertically or diagonally to the selected pixel line.

The operation of determining the estimation region of the second block region of the spatiotemporal estimation block may include the operation of determining an average value between pixel values of the neighboring blocks of the current block and pixel values surrounding the second block region to be an estimation pixel value of the second block region, wherein the pixel values surrounding the second block region are a part of the first block region of the spatiotemporal estimation block, when the spatiotemporal estimation block is allocated to the current block.

According to another aspect of the present invention, there is provided a method of estimating and compensating for motion in image encoding, the method including the operations of searching for a reference block having a minimum difference compared with a current block in a reference frame, calculating a motion vector, and thereby performing motion estimation; generating an estimation block for the current block by using the current frame and the reference frame, when some pixels of the reference block are outside the reference frame; and encoding an image by using the estimation block and the motion vector.

When a block region in a same position as a region included in the reference frame is defined to be a first block region, wherein the block region is a part of the reference block, and a block region in a same position as a region excluded from the reference frame is defined to be a second block region, wherein the block region is a part of the reference block, the operation of generating the estimation block may include the operations of determining the first block region of the reference block to be an estimation region of the first block region of the estimation block; and generating an estimation region of the second block region of the estimation block by using at least one of pixels of neighboring blocks of the current block and pixels of an estimation region of the first block region.

The operation of generating the estimation region of the second block region of the estimation block may include the operations of determining pixels of the neighboring blocks of the current block and pixels surrounding the second block region to be a search pattern region, wherein the neighboring blocks are from among regions reconstructed prior to the current block, and the pixels surrounding the second block region are of a part of the first block region of the estimation block, when the estimation block is allocated to the current block; searching for an outside estimation region surrounded by a similar pattern region having a minimum difference compared with the search pattern region in the regions reconstructed prior to the current block; and determining the outside estimation region to be an estimation region of the second block region of the estimation block.

The operation of searching for the outside estimation region may include the operation of searching for the similar pattern region having a same form as the search pattern region in the regions reconstructed prior to the current block, and having a minimum SAD between pixel values of the search pattern region and pixel values of the similar pattern region.

The operation of generating the estimation region of the second block region of the estimation block may include the operations of selecting at least one of a pixel line of the neighboring blocks of the current block and a pixel line surrounding the second block region, wherein the pixel line surrounding the second block region is a part of the first block region of the estimation block, when the estimation block is allocated to the current block; and determining pixels of the selected pixel line to be estimation pixels related to pixels of the second block region located either vertically or diagonally to the selected pixel line.

The operation of generating the estimation region of the second block region of the estimation block may include the operation of determining an average value between pixel values of the neighboring blocks of the current block and pixel values surrounding the second block region to be an estimation pixel value of the second block region, wherein the pixel values surrounding the second block region are a part of the first block region of the estimation block, when the estimation block is allocated to the current block.

According to another aspect of the present invention, there is provided a motion estimation and compensation apparatus in image decoding, the motion estimation and compensation apparatus including a reference block determining unit determining a reference block of a reference frame for a current block of a current frame being decoded; and a spatiotemporal estimation block generation unit generating a spatiotemporal estimation block of the current block by using the current frame and the reference frame, when some pixels of the reference block are outside the reference frame.

According to another aspect of the present invention, there is provided a motion estimation and compensation apparatus in image encoding, the motion estimation and compensation apparatus including a motion estimation performing unit searching for a reference block having a minimum difference compared with a current block in a reference frame, calculating a motion vector, and thereby performing motion estimation; an estimation block generation unit generating an estimation block for the current block by using the current frame and the reference frame, when some pixels of the reference block are outside the reference frame; and an encoding unit encoding an image by using the estimation block and the motion vector.

According to another aspect of the present invention, there is provided a computer readable recording medium having recorded thereon a program for executing the method of estimating and compensating for motion in image decoding.

According to another aspect of the present invention, there is provided a computer readable recording medium having recorded thereon a program for executing the method of estimating and compensating for motion in image encoding.

DETAILED DESCRIPTION OF THE INVENTION

Hereinafter, a method and apparatus for estimating and compensating for motion in image decoding, and a method and apparatus for encoding an image, according to exemplary embodiments of the present invention will now be described more fully with reference to the accompanying drawings, in which exemplary embodiments of the invention are shown.

FIG. 2is a block diagram illustrating a motion estimation and compensation apparatus200for image decoding according to an embodiment of the present invention.

The motion estimation and compensation apparatus200for image decoding according to the current embodiment of the present invention includes a reference block determination unit210, and a spatiotemporal estimation block generation unit220. The spatiotemporal estimation block generation unit220includes a first block region determination unit230, and a second block region determination unit240.

The reference block determination unit210determines a reference block of a reference frame for a current block of a current frame being decoded.

When some pixels of the reference block are outside the reference frame, the spatiotemporal estimation block generation unit220generates a spatiotemporal estimation block of the current block by using the current frame and the reference frame.

For convenience of description, it is assumed that a block region in the same position as a region included in the reference frame is defined to be a first block region, wherein the block region is a part of the reference block, and a block region in the same position as a region excluded from the reference frame is defined to be a second block region, wherein the block region is a part of the reference block.

The first block region determination unit230determines the first block region of the reference block to be an estimation region of a first block region of the spatiotemporal estimation block.

The second block region determination unit240generates an estimation region of a second block region of the spatiotemporal estimation block by using at least one of pixel values of neighboring blocks of the current block and pixel values of the estimation region of the first block region.

Embodiments related to the second block region determination unit240will be described later in detail with reference toFIGS. 4 through 6C.

An aspect of the present invention determines blocks estimated by the reference block, and in particular, the spatiotemporal estimation blocks generated by the spatiotemporal estimation block generation unit220when the reference block is outside the reference frame, to be a current block, and as such an image is reconstructed during image decoding.

FIG. 3is a block diagram illustrating a motion estimation and compensation apparatus300for image encoding according to another embodiment of the present invention.

The motion estimation and compensation apparatus300for image encoding according to the current embodiment of the present invention includes a motion estimation performing unit310, an estimation block generation unit320, and an encoding unit330.

The motion estimation performing unit310searches for a reference block in a reference frame, wherein the reference block has a minimum difference compared with a current block, calculates a motion vector, and thereby performs motion estimation.

The motion estimation performing unit310may determine a block to be the reference block, wherein the block has a minimum Sum of Absolute Differences (SAD) between each pixel value of a block in the reference frame and each pixel value of the current block. The motion vector may indicate a positional distance between the current block and the reference block.

When some pixels of the reference block are outside the reference frame, the estimation block generation unit320generates an estimation block for the current block by using the current frame and the reference frame.

An embodiment for the estimation block generation unit320is not illustrated. However, similar to the motion estimation and compensation apparatus200for image decoding, the estimation block generation unit320includes a first block region determination unit and a second block region determination unit which are respectively for a first block region and a second block region of the estimation block. The first and second block region determination units of the estimation block generation unit320respectively have the same operating principle as the first and second block region determination units of the spatiotemporal estimation block generation unit220. Thus, the operating principle of the first and second block region determination units of the estimation block generation unit320will be described later with reference toFIGS. 4 through 6C.

The encoding unit330encodes an image by using the estimation block and the motion vector.

The encoding unit330may determine the estimation block to be the current block, and encode the image by using a difference value between the current block and the reference block.

FIG. 4is a diagram illustrating a method of generating an estimation block when a reference block is outside a reference frame, according to an embodiment of the present invention.

Referring toFIG. 4, a method of operating the spatiotemporal estimation block generation unit220of the motion estimation and compensation apparatus200for image decoding, and the estimation block generation unit320of the motion estimation and compensation apparatus300for image encoding will now be described in detail. In particular, a method of operating the first and second block region determination units of the spatiotemporal estimation block generation unit220and the estimation block generation unit320will now be described in detail.

A frame110, a frame150, and a block160respectively indicate a current frame, a reference frame, and a reference block.

A region170of the reference block160indicates a region included in the reference frame150. A region180of the reference block160indicates a region excluded from the reference frame150.

A block420indicates a spatiotemporal estimation block. Since the spatiotemporal estimation block generated by the present invention is determined to be a current block, the block420eventually becomes a current block120.

A region430indicates a first block region of the spatiotemporal estimation block420.

A region440indicates a second block region of the spatiotemporal estimation block420.

A region450indicates pixels surrounding the current block120, wherein the pixels are from among neighboring blocks of the current block120.

When the reference block160related to the current block120is inside the reference frame150, an estimation block related to the current block120can be determined by a motion estimation/compensation method that is well-known to one of ordinary skill in the art. Hereinafter, a case in which the reference block160is outside the reference frame150will now be described in detail.

As described above, it is assumed that a block region in the same position as the region170included in the reference frame150is defined to be a first block region, wherein the block region is a part of the reference block160, and a block region in the same position as the region180excluded from the reference frame150is defined to be a second block region, wherein the block region is a part of the reference block160. Thus, the region430and the region440respectively become the first block region and the second block region, which are of the spatiotemporal estimation block420that is to be inserted into the current block120.

The first block region determination unit230may determine the first block region170of the reference block160to be an estimation region of the first block region430of the spatiotemporal estimation block420.

The second block region determination unit240may generate an estimation region of the second block region440of the spatiotemporal estimation block420by using at least one of pixel values of neighboring blocks of the current block120, and pixel values of the estimation region of the first block region430of the spatiotemporal estimation block420.

The second block region determination unit240may use a method of using a search pattern including the pixels450, and a method of using values of some of the pixels450without a change, wherein the pixels450surrounding the current block120are from among pixels of the neighboring blocks and first block region430, so as to use the neighboring blocks of the current block120and the estimation region of the first block region430of the spatiotemporal estimation block420. The method of using the search pattern will be described later with reference toFIG. 5, and the method of using the pixels450will be described later with reference toFIGS. 6A through 6C.

The first and second block region determination units of the estimation block generation unit320for image encoding respectively have the same operating principle as the first and second block region determination units230and240of the spatiotemporal estimation block generation unit220for image decoding.

FIG. 5is a diagram illustrating an example of a type of a search pattern for estimating a region that is outside a reference frame.

A method of operating an example of the second block region determination unit240of the spatiotemporal estimation block generation unit220for image decoding, and an example of the second block region determination unit of the estimation block generation unit320for image encoding will now be described in detail with reference toFIG. 5.

A region510indicates a search pattern region for determining the second block region440.

A region520indicates a similar pattern region searched for by the search pattern region510.

A region530indicates an outside estimation region.

The second block region determination unit240may determine pixels of the neighboring blocks of the current block120and pixels surrounding the second block region440to be the search pattern region510, wherein the neighboring blocks are from among regions reconstructed prior to the current block120, and the pixels surrounding the second block region440are part of the first block region430of the spatiotemporal estimation block (estimation block)420.

Also, the second block region determination unit240may search for the similar pattern region520having a minimum difference compared with the search pattern region510in the regions reconstructed prior to the current block120. The similar pattern region520has the same form as the search pattern region510, and a region having a minimum SAD (that is the sum of the absolute values of the difference between pixel values of the search pattern region510and pixel values of the similar pattern region520) in the regions reconstructed prior to the current block120is determined to be the similar pattern region520.

The outside estimation region530corresponds to a region surrounded by the similar pattern region520determined by the search pattern region510. The second block region determination unit240determines the outside estimation region530to be an estimation region of the second block region440, and thereby completes the spatiotemporal estimation block (estimation block)420.

FIGS. 6A through 6Care diagrams illustrating various methods of estimating a region that is outside a reference frame, according to another embodiment of the present invention.

A method of operating an example for the second block region determination unit240of the spatiotemporal estimation block generation unit220for image decoding, and an example of the second block region determination unit of the estimation block generation unit320for image encoding will now be described in detail with reference toFIGS. 6A through 6C. In particular, the method is related to a method of determining the second block region440by using the aforementioned pixels450.

FIG. 6Aprovides diagrams illustrating one of the various methods of estimating the region that is outside the reference frame.

A block610indicates the spatiotemporal estimation block (estimation block)420in which each pixel value of the first block region430is inserted vertically to a boundary line and to each pixel of the second block region440.

A block620indicates the spatiotemporal estimation block (estimation block)420in which each pixel value of a previously reconstructed neighboring block is inserted vertically to a boundary line and to each pixel of the second block region440.

A block630indicates the spatiotemporal estimation block (estimation block)420in which each pixel value of the previously reconstructed neighboring block is inserted horizontally to a boundary line and to each pixel of the second block region440.

The pixel values of the previously reconstructed neighboring block that is the nearest block to the second block region440of the current block120are inserted vertically and horizontally to the boundary line and to each pixel of the second block region440from the boundary lines between the current block120and the previously reconstructed neighboring block, such that the estimation blocks620and630are generated.

The pixel values of the first block region430that is the nearest block region to the second block region440are inserted vertically to each pixel of the second block region440from the boundary line between the first block region430and the second block region440, and such that the estimation block610is generated.

FIG. 6Bprovides diagrams illustrating another method from among the various methods of estimating the region that is outside the reference frame.

A block640indicates the spatiotemporal estimation block (estimation block)420in which the pixel values of the previously reconstructed neighboring block are inserted diagonally left to each pixel of the second block region440.

A block650indicates the spatiotemporal estimation block (estimation block)420in which the pixel values of the previously reconstructed neighboring block are inserted diagonally right to each pixel of the second block region440.

A block660indicates the spatiotemporal estimation block (estimation block)420in which each pixel value of the first block region430is inserted diagonally right to each pixel of the second block region440.

A block670indicates the spatiotemporal estimation block (estimation block)420in which each pixel value of the first block region430is inserted diagonally left to each pixel of the second block region440.

The pixel values of the previously reconstructed neighboring block that is the nearest block to the second block region440of the current block120are inserted diagonally to the boundary line and to each pixel of the second block region440from the boundary line between the current block120and the previously reconstructed neighboring block, such that the estimation blocks640and650are generated.

The pixel values of the first block region430that is the nearest block region to the second block region440are inserted diagonally to each pixel of the second block region440from the boundary line between the first block region430and the second block region440, such that the estimation blocks660and670are generated.

FIG. 6Cprovides a diagram illustrating another method from among the various methods of estimating the region that is outside the reference frame.

A block680indicates the spatiotemporal estimation block (estimation block)420in which an average value of pixel values included in the region510is determined by estimation pixel values of the second block region440.

The estimation block680determines an average value of pixel values of the previously reconstructed neighboring blocks from among neighboring blocks of the current block120, and a region that is the same as the search pattern region510that comprises pixels of the first block region430, wherein the pixels are the nearest pixels to the second block region440, to be an estimation region.

FIG. 7is a flowchart of a method of estimating and compensating for motion in image decoding, according to another embodiment of the present invention.

In operation710, a reference block of a reference frame for a current block of a current frame is determined by using a received frame and a motion vector.

In operation720, when some pixels of the reference block are outside the reference frame, a spatiotemporal estimation block for the current block is generated by using the current frame and the reference frame.

In the current embodiment, the spatiotemporal estimation block is divided into a first block region corresponding to a region included in the reference frame, wherein the region is a part of the reference block, and a second block region corresponding to a region excluded from the reference frame, wherein the region is a part of the reference block, and as such the spatiotemporal estimation block corresponding to the respective regions is generated. That is, temporal estimation using pixel values of the reference block is performed on the first block region of the spatiotemporal estimation block, and spatial estimation using pixel values of a neighboring block of the current block is performed on the second block region of the spatiotemporal estimation block.

FIG. 8is a flowchart of a method of estimating and compensating for motion in image encoding, according to another embodiment of the present invention.

In operation810, a reference block having a minimum difference compared with a current block is searched for in a reference frame, a motion vector is calculated, and thereby motion estimation is performed.

In operation820, when some pixels of the reference block are outside the reference frame, an estimation block for the current block is generated by using a current frame and the reference frame.

In the current embodiment, the spatiotemporal estimation block is divided into a first block region corresponding to a region included in the reference frame, wherein the region is a part of the reference block, and a second block region corresponding to a region excluded from the reference frame, wherein the region is a part of the reference block, and as such the spatiotemporal estimation block corresponding to the respective regions is generated. That is, temporal estimation using pixel values of the reference block is performed on the first block region of the spatiotemporal estimation block, and spatial estimation using pixel values of a neighboring block of the current block is performed on the second block region of the spatiotemporal estimation block.

In operation830, an image is encoded by using the estimation block and the motion vector. In this manner, motion compensation is performed during image encoding and then the image to be encoded is reconstructed. Thus, it is possible to use the image in which information regarding motion is more accurately reflected.

When the reference block, which is selected by the motion vector, for the current block has the region that is outside the reference frame, the method and apparatus for estimating and compensating for the motion in image decoding according to the present invention use information of the region included in the neighboring block of the current block and the reference frame. Accordingly, the method and apparatus can accurately estimate and compensate for the motion in comparison with the conventional technology.

While the conventional technology uses a padding method which depends on limited information corresponding to boundary pixels of a reference frame, the method and apparatus for estimating and compensating for motion in image decoding according to the present invention use the information of the region included in the neighboring block and the reference frame. By doing so, the method and apparatus has reflected therein correlation with the reference frame, thereby has high compression efficiency. In particular, the compression efficiency of an active image sequence having panning, tilting, zooming in/out, fast camera motion, and fast object motion is greatly increased.

Among exemplary embodiments of the present invention, an effect of the method of estimating and compensating for motion in image decoding is higher than an effect of the method of estimating and compensating for motion in image encoding, in terms of calculation time.

The present invention can be applied to video codecs based on temporal motion estimation, or to all methods and apparatuses such as mobile phones, camcorders, digital cameras, Portable Multimedia Players (PMPs), next-generation Digital Video Discs (DVDs), software video codes, and the like which are capable of using the video codecs.

Exemplary embodiments of the present invention can be written as computer programs and can be implemented in general-use digital computers that execute the programs using a computer readable recording medium and other media. In addition, a data structure used in the embodiments of the present invention can be written in a computer readable recording medium through various means. Examples of the computer readable recording medium include magnetic storage media (e.g., ROM, floppy disks, hard disks, etc.) and optical recording media (e.g., CD-ROMs, or DVDs) An example of other media is carrier waves (e.g., transmission through the Internet).