DE69425896T2 - Method and device for motion vector detection in an image encoder with image decimation - Google Patents

Description

Field of the invention

The present invention relates to a method and apparatus for encoding an image signal; and more particularly to a method and apparatus for estimating a motion vector in a frame decimation image encoder that uses a frame decimation technique for data compression together with motion estimation and compensation on a pixel-by-pixel basis.

Description of the state of the art

As is well known, the transmission of digitized image signals can provide much higher quality than the transmission of analog signals. When an image signal comprising a sequence of image "frames" is expressed in digital form, a significant amount of data is generated for transmission, particularly in the case of a high definition television system. However, since the available frequency bandwidth of a conventional transmission channel is limited to transmit the significant amounts of digital data through the limited channel bandwidth, it is impractical to compress or reduce the volume of the transmission data. Among various image compression techniques, the so-called hybrid coding technique, which combines temporal and spatial compression techniques together with a statistical coding technique, is known to be the most effective.

Most hybrid coding techniques apply a motion compensated DPCM (differential pulse code modulation), a two-dimensional DCT (discrete cosine transform), a quantization of the DCT coefficients and a VLC (variable length coding). Motion compensated DPCM is a process in which the motion of an object between a current frame and its previous frame is determined and the current frame is predicted according to the motion flow of the object to produce a difference signal representing the difference between the current frame and its prediction. This method is described, for example, in Staffan Ericsson, "Fixed and Adaptive Predictors for Hybrid Predictive/Transform Coding", IEEE Transactions on Communications, COM-33, No. 12 (December 1985); and in Ninomiya and Ohtsuka, "A Motion-Compensated Interframe Coding Scheme for Television Pictures", IEEE Transactions on Communications, COM-30, No. 1 (January 1982).

More specifically, in motion compensated DPCM, current frame data is predicted from the corresponding data of the previous frame based on an estimate of the motion between the current and previous frames. Such estimated motion can be described using two-dimensional motion vectors that describe the displacement of pixels between the previous and current frames.

There have been many approaches to estimate the displacement of pixels of an object. In general, these can be classified into two types, i.e., motion estimation on a block-by-block basis and a pixel-by-pixel basis.

In motion estimation on a block-by-block basis, a block in a current frame is compared with blocks in its previous frame until a best match is determined. From this, an interframe displacement vector (how much the block has moved between frames) can be estimated for the entire block for the current frame to be transmitted. In motion estimation on a block-by-block basis, however, the motion compensation process can introduce a block effect at the boundaries of a block. and it can lead to poor estimates if not all pixels in the block move in the same way, reducing the overall coding efficiency.

On the other hand, when using a pixel-by-pixel approach, a displacement is determined for each and all pixels. This technique allows a more accurate estimation of the pixel value and has the ability to handle scale changes (e.g. zooming, a movement perpendicular to the image plane) more easily. However, since the pixel-by-pixel approach determines a motion vector at each and all pixels, it is impossible to actually transmit all the motion vectors to a receiver. Therefore, motion vectors are transmitted to the receiver for a set of selected pixels, i.e. feature points, where each of the feature points is defined as a position of a pixel that can represent its neighboring pixels such that motion vectors for non-feature points can be recovered from those for feature points in the receiver. The present invention primarily relates to motion estimation using feature points. In an encoder applying motion estimation based on feature points, first a number of feature points are selected from among all the pixels contained in the previous frame. Then motion vectors are determined for each of the selected feature points, where each of the motion vectors is a spatial displacement between a feature point in the current frame and a corresponding match point, i.e., a most similar pixel, in the previous frame. More specifically, the match point for each of the feature points is searched in a search region within a reference frame, e.g., a previous frame, where the search region is defined as a region having a predetermined area enclosing the position of its corresponding feature point.

Another compression technique that can be easily implemented is a frame decimation technique that reduces the amount of data by encoding and transmitting only selected frames of the video image and skipping or decimating the remaining frames in between (see, for example, "Video Codec for Audiovisual Services at p · 64 kb/s", CCITT Recommendation H.261, CDM XV-R 37-E, International Telegraph and Telephone Consultative Committee (CCITT), August 1990).

Typically, the input to the image encoder is an image signal at 30 frames/sec. The frame rate resulting from skipping one, two, or three frames between every two encoded frames is typically 15, 10, or 7.5 frames/sec, respectively.

In a conventional image encoder using both the hybrid coding and frame decimation techniques, the selected frames of the image signal are encoded using both interframe and transform coding methods, and the motion vectors obtained from the interframe coding are detected between two consecutive encoded frames. Since some of the frames are skipped, the motion jump or shift between two consecutive encoded frames becomes more abrupt than that of the undecimated original image signal, resulting in the generation of larger motion vectors. Therefore, to detect an optimal motion vector between two encoded frames, a larger search area should be used in the previous encoded frame, the size of which depends on the frame rate of the encoded frames or the decimation degree. Since the computational complexity of the block matching algorithm is usually dependent on the size of the search area, the image encoder applying the frame decimation technique may be subjected to a larger computational burden for estimating the motion vectors.

The document IEEE 1993 International Conference on Consumer Electronics, 8, June 1993, Rosemont, IL, ISA, pages 2-3, J. Nieweglowski et al. "A Novel Video Coding Scheme Based on Temporal Prediction using Digital Image Warping" discloses a method for temporal prediction of image sequences. In the previous frame, feature pixels are selected arranged on a rectangular grid. These feature points are compared with pixels in the current frame using a block matching technique to determine a motion vector for each feature point. The remaining pixels in the rectangular shaped blocks formed by the feature points are transferred to the blocks formed by the motion compensated feature points using a perspective transformation algorithm.

Document EP-A-424 026 discloses an image signal coding method in which a sequence of seven consecutive frames is encoded by encoding a first part of these frames via intra-frame coding and the remaining part of these frames via inter-frame coding. Motion vectors are calculated for some frames in a forward prediction and for some other frames in a backward prediction. Furthermore, predicted frames are calculated using these motion vectors and then further interpolated.

Document EP-A-397 402 shows an image signal coding method comprising motion estimation together with frame decimation.

The document ICASSP 1991, INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING, Vol. 4, 14 April 1991, Toronto, Ont, CA, pages 2712-2716, Sullivan et al. "Motion Compensation for Video compression using Control Grid Interpolation" discloses an image signal coding method that applies a motion compensation technique based on control grid interpolation.

Summary of the invention

It is therefore a primary object of the present invention to provide an improved method and apparatus for detecting motion vectors of feature points between two coded frames in multiple steps for use in a frame decimation image encoder, thereby reducing the overall computational complexity of the image encoder.

The invention achieves this object with the subject matter of claims 1 and 3, respectively. A preferred embodiment of the invention is described in the dependent claim 2.

Short description of the drawing

The above and other objects and features of the present invention will become apparent from the following description of preferred embodiments with reference to the accompanying drawings, in which:

Fig. 1 is a block diagram of an image encoder using a motion estimation block of the present invention;

Fig. 2A and 2B illustrate differences between the inventive method and the prior art motion estimation techniques;

Figure 3 is a block diagram of the motion estimation block of the present invention;

Fig. 4 is a block diagram of the prediction block shown in Fig. 1; and

Fig. 5 exemplifies a method for detecting a motion vector for the non-feature points.

Detailed description of the preferred embodiments

Referring to Fig. 1, there is shown a block diagram of an image encoder employing a motion estimation block 126 of the present invention. A digital image input signal is input to a frame decimator 101 and the motion estimation block 126. At the frame decimator 101, frames to be encoded are selected by skipping the intervening frames at a predetermined frame decimation rate representing the decimation degree and input to a subtractor 102. For example, the frame decimator 101 selects or uses every second or every third frame of the image signal if the predetermined decimation ratio is 2 or 3, respectively.

At motion estimation block 126, the current or skipped frame signal on a line L10 and a reconstructed previous encoded frame signal on a line L12 from a frame memory 124 are processed to calculate and estimate a first set of motion vectors, each of which represents a displacement between a feature point of the current frame and a best-matching point contained in a corresponding search area in the previous encoded frame.

According to the present invention, the motion vectors between two selected frames, i.e., the current frame and the previous encoded frame, are detected in multiple steps as described below with reference to Figs. 2A and 3. In each of the steps, a motion vector between two consecutive frames, including skipped frames as well as encoded frames, is detected and stored, and a motion vector between two encoded frames is provided by adding the stored motion vectors thereafter.

The motion vector on a line L20 provided by the motion estimation block 126 is fed to a prediction block 122 and an entropy encoder 107.

In response to the motion vector, a prediction signal is determined on a pixel-by-pixel basis at the prediction block 122, as described with reference to Figure 4, and provided to the subtractor 102 and an adder 115 on a line L30.

The prediction signal from the prediction block 122 is subtracted from the current frame signal at the subtractor 102; and the resulting data, i.e. an error signal indicative of the difference pixel value, is input to an image signal encoder 105, where a set of error signals is encoded into a set of quantized transform coefficients using, for example, a discrete cosine transform (DCT) and any of the known quantization techniques. Thereafter, the quantized transform coefficients are transmitted via two signal paths: one leads to the entropy encoder 107, where the quantized transform coefficients are encoded together with the motion vector supplied via the line L20 using, for example, a combination of a run-length and variable-length coding technique for transmission thereof; and the other leads to a picture signal decoder 113, where the quantized transform coefficients are converted back into a reconstructed differential error signal by applying the inverse quantization and the inverse transform. Reconstruction of the error signal is required so that the encoder can monitor the behavior of the decoder in a receiver and thereby prevent the decoder's reconstructed signal from diverging from the current frame signal.

The reconstructed error signal from the image signal decoder 113 and the prediction signal from the prediction block 122 are combined at the adder 115 to produce a reconstructed current frame signal to be written into the frame memory 124.

2A and 2B schematically illustrate the motion vector detection method according to the present invention and the conventional motion vector detection method, respectively. For illustration purposes, it has been assumed that the frame decimation ratio is equal to 3, i.e., two frames are skipped between the previous encoded frame and the current selected frame to be encoded. Fig. 2A shows a procedure for estimating a motion vector between a current frame F1 and the previous encoded frame F4 stored in the frame memory 124 according to the present invention. Two skipped frames F2 and F3 are stored in a frame data stack 190 shown in Fig. 3, which shows the details of the motion estimation block 126 shown in Fig. 1. First, a search area SR3 corresponding to a search point SP4 of the previous encoded frame F4 is determined in its subsequent skipped frame F3, where the search point SP4 is one of the feature points of the previous encoded frame F4. The best matching point to SP4 is detected from the search area SR3, and a motion vector MV3 is provided between F4 and F3. Thereafter, with the best matching point SP3 in F3 as a new search point, a corresponding search area SR2 shifted by MV3 from the search area SR3 is determined in its subsequent skipped frame F2. The best matching point of the search point SP3 is detected in SR2, and a motion vector MV2 is provided between F3 and F2. Similarly, a motion vector MV1 is detected between F2 and the current frame F1. The final motion vector between the current frame F1 and the previous encoded frame F4 is a vector sum of MV1, MV2 and MV3, which represents the displacement between the search point SP4 in F4 and the best-matching point SP1 in F1.

The process described above for estimating a motion vector for a feature point in the previous encoded frame is repeated for all the other feature points in the previous encoded frame.

Fig. 2B shows a procedure for detecting a motion vector between a previous encoded frame F4 and the current frame F1 using the prior art motion estimation method. The best matching point to the search point SP4 is directly determined in a search area in F1. If a search area with the same size as that in the method shown in Fig. 2A, e.g. SR5, is used, the best matching point SP1 determined in the current frame F1 by the method of Fig. 2A will be outside the boundary of the search area SR5. Therefore, a larger search area, e.g. SR6, should be used to obtain a more accurate motion vector. The amount of motion between the current frame and the previous encoded frame depends greatly on the frame decimation ratio. Therefore, a larger search area should be used in the current frame in proportion to the frame decimation ratio to obtain a more accurate motion vector. If a larger search area, e.g., SR6, is used to obtain an accurate motion vector, the computational complexity of finding a best-fitting point in the search area will increase depending on the size of the search area. Accordingly, the method of Fig. 2A will impose less computational overhead than the method of Fig. 2B, except for the additional computational time required to perform the multi-step processing.

Referring to Fig. 3, a detailed block diagram of the motion estimation block 126 of the present invention shown in Fig. 1 is shown.

The image signal input to the motion estimation block 126 on line L10 is fed to a frame data stack 190.

More specifically, the skipped frames and the current frame of the image signal are supplied to and stored in the frame data stack 190 to be provided therefrom to a motion vector detection block 210.

The previous encoded frame retrieved from the frame memory 124 is input to a feature point selection block 200 and the motion vector detection block 210 via the line L12. At the feature point selection block 200, a number of feature points are selected from among the pixels included in the previous encoded frame. Each of the feature points is defined as a position of a pixel suitable to represent its neighboring pixels.

Each of the selected feature points is supplied to a feature point updating block 220 and updated there as described below. The updated feature point is supplied to the motion vector detecting block 210 as the search point, as explained with reference to Fig. 2A, to detect a motion vector for the updated feature point. At the start of processing, the updated feature point is equal to the feature point supplied from the feature point selecting block 200. The motion vector detecting block 210 finds the best matching point for the feature point, e.g., the search point SP4 in Fig. 2A, in the search area SR3 of the skipped frame F3, and thereby determines the motion vector MV3 between the search point SP4 and the best matching point in the search area SR3. There are many processing algorithms to detect the motion vector for the feature point. One of the processing algorithms is to first set a certain block size for a feature point and then detect a motion vector for the feature point by applying one of the well-known block matching algorithms.

The motion vector MV3 is supplied to a motion vector accumulator 230 to be stored therein; and to the feature point update block 220, whereby the best matching point SP3 is provided as a new updated feature point to the motion vector detection block 210. At the motion vector detection block 210, the best matching point for a new search point, which is the new feature point SP3 in Fig. 2A, is determined in the search area SR2 of the skipped frame F2, and thereby the motion vector MV2 between the search point SP2 and the best matching point SP2 in the search area SR2 is determined. The motion vector MV2 is then sent to the motion vector accumulator 230 to be added to MV3 and sent to the feature point updating block 220. This process of detecting a motion vector and updating a feature point is repeated between the skipped frame F2 and the current frame F1. By accumulating the detected motion vectors, e.g. For all the feature points in the previous encoded frame, e.g., MV1, MV2, and MV3, the motion vector accumulator 230 provides a final motion vector, e.g., MV, shown in Fig. 2B, between the feature point SP4 in the previous encoded frame and the best matching point, e.g., SP1, in its corresponding search region, e.g., SR1, within the current frame on line L20. For all the feature points in the previous encoded frame, the above process is repeated, thereby providing the first set of motion vectors for the feature points to the prediction block 122 shown in Fig. 1.

Although the present invention has been described with respect to a frame decimation ratio of 3, different frame decimation methods or ratios may be used in encoding an image signal and the motion vectors may be calculated in a similar manner as has been presented herein.

Referring to Fig. 4, a detailed block diagram of the prediction block 122 is shown. A first set of motion vectors for the feature points is provided from the motion estimation block 126 on line L20 to a non-feature point motion estimator 214. In the non-feature point motion In the motion estimator 214, a second set of motion vectors is determined for each of the non-feature points, ie, points of the previous encoded frame other than the feature points, using the first set of motion vectors for the feature points.

Fig. 5 shows an exemplary method for detecting a motion vector for a non-feature point for the case where feature points are unevenly distributed throughout the frame. A motion vector for a star-marked pixel of a non-feature point is calculated using the feature points located within a circular boundary with a radius of dr + da, where da is the distance of a nearest feature point from the star-marked pixel position, and dr is a predetermined extended radius for enclosing other feature points to be used in the motion vector calculation. For example, if the nearest feature point to the star-marked pixel is "Y" and the feature point "X" is within the circular boundary with radius (da + dr), the motion vector (MVX, MVy) for the star-marked pixel is calculated as follows:

where dx and dy are the distances of the feature points X and Y from the pixel position marked with the star, respectively;

and (MVx, MVy)x and (MVx, MVy)y are the motion vectors for the feature points, respectively.

Referring again to Figure 4, the determined second set of motion vectors for non-feature points is provided to a pixel-to-pixel predictor 216, where each value of the pixels to be included in a predicted current frame is determined using both sets of motion vectors.

Claims (3)

1. A method for determining target motion vectors (MV) between a current frame (F1) and a previous selected frame (F4) for a set of search points (SP4), wherein a number N of frames (F2, F3) are skipped between the current frame (F1) and the previous selected frame (F4), the number N is a positive integer including 1, and the set of search points (SP4) contained in the previous selected frame (F4) is predetermined, which comprises the following steps: a) Saving the N skipped frames (F2, F3); b) setting one of the search points (SP4) as a reference search point; c) determining, for the reference search point (SP4), a best matching point (SP3) contained in a corresponding search area (SR3) in an i-th skipped frame (F3), thereby generating an i-th motion vector (MV3) representing the displacement between the reference search point (SP4) and the best matching point (SP3), and setting the best matching point (SP3) as the reference search point (SP3), where i is a number selected in ascending order from 1 to N, and a smaller value for i refers to a frame closer in time to the previously selected frame (F4); d) storing the i-th motion vector (MV3); e) repeating steps c) to d) until first to N-th motion vectors (MV3, MV2) are obtained; f) determining, for the reference search point (SP2), a best-fitting point (SP1) contained in a corresponding search area (SR1) in the current frame (F1), and thereby generating an (N + 1)-th motion vector (MV1) which represents the shift between the reference search point (SP2) and the best fitting point (SP1); g) summing the (N + 1) motion vectors (MV1, MV2, MV3) to provide a target motion vector (MV) representing the displacement between the one of the search points (SP4) in the previous frame (F4) and the corresponding best-matching point (SP1) in the current frame (F1); h) repeating steps (b) to (g) until a set of target motion vectors (MV) for all the search points (SP4) is detected; and i) calculating a motion vector for a non-feature point which is a point of the previous selected frame (F4) and which is not a search point (SP4) in the previous selected frame (F4) using the set of target motion vectors (MV), using from the set of search points (X, Y, SP4) search points (X, Y) within a circular boundary around the non-feature point, the circular boundary having a radius of dr + da, where da is the distance between a next search point (Y) and the non-feature point and dr is a predetermined extended radius to include further search points (X) to be used in the motion vector calculation. 2. The method of claim 1, wherein the motion vector for the non-feature point is calculated using the following equation: (MVx, Mvy) = {(MVx, MVy)x/dx + (MVx, MVy)y/dy}/{1/dx + 1/dy), where dx and dy are the respective distances from search points X and Y to the non-feature point, Y is the closest search point to the non-feature point, and X is a search point within the circular boundary; and (MVx, MVy)x and (MVx, MVy)y are motion vectors for the search points X and Y, respectively. 3. Motion estimation device for determining target motion vectors (MV) between a current frame (F1) and a previous selected frame (F4) for a set of search points (SP4), wherein a number N of frames (F2, F3) are skipped between the current frame (F1) and the previous selected frame (F4), the number N is a positive integer including 1, and the set of search points (SP4) contained in the previous selected frame (F4) is predetermined, comprising: a) storage means (190) for storing the N skipped frames (F2, F3); b) means (200) for selecting the set of search points (SP4) in the previous selected frame (F4); c) means (220) for providing a reference search point (SP4) in a reference frame (F4), wherein one of the search points (SP4) selected from the previously selected frame (F4) is determined as the reference search point (SP4) if no motion vector is input thereto, and if a motion vector (MV3) is input, the reference search point (SP3) is updated to a best-matching point (SP3) of the reference search point (SP4) in response to the motion vector (MV3), and for providing (N + 1) reference search points (SP4, SP3, SP2) for each of the search points (SP4); d) motion vector detection means (210) for determining, for each reference search point (SP4), a best matching point (SP3) contained in a search area (S3) contained in the frame (F3) following the reference frame (F4), and thereby generating a motion vector (MV3) from successive (N + 1) motion vectors (MV3, MV2, MV1) representing the displacement between the reference search point (SP4) and the best fitting point (SP3); e) means (230) for storing and summing the successive (N + 1) motion vectors (MV3, MV2, MV1) to provide a target motion vector (MV) representing the displacement between each of the search points (SP4) and the corresponding best-matching point (SP1) in the current frame (F1), thereby providing the set of target motion vectors (MV) for all the search points (SP4); and f) means (214) for calculating a motion vector for a non-feature point which is a point of the previous selected frame (F4) and which is not a search point (SP4) in the previous selected frame (F4) using the set of target motion vectors (MV), using search points (X, Y) within a circular boundary around the non-feature point from the set of search points (X, Y, SP4), the circular boundary having a radius dr + da, where da is the distance between a next search point (Y) and the non-feature point and dr is a predetermined extended radius to include further search points (X) to be used in the motion vector calculation. FIGURE LEGEND Fig.1: VIDEO SIGNAL IMAGE SIGNAL 101 FRAME DECIMATOR FRAME DECIMATOR 105 IMAGE SIGNAL ENCODER IMAGE SIGNAL ENCODER 107 ENTROPY CODER ENTROPY CODER TO TRANSMITTER TO THE TRANSMITTER 113 IMAGE SIGNAL DECODER IMAGE SIGNAL DECODER 122 PREDICTION BLOCK PREDICTION BLOCK 124 FRAME MEMORY FRAME MEMORY 126 MOTION ESTIMATION BLOCK MOTION ESTIMATION BLOCK Fig. 3: FROM FRAME MEMORY FROM FRAME MEMORY 200 FEATURE POINT SELECTION FEATURE POINT SELECTION 220 FEATURE POINT UPDATING FEATURE POINT UPDATE VIDEO SIGNAL IMAGE SIGNAL 190 FRAME STACK FRAME DATA STACK 210 MOTION VECTOR DETECTING MOTION VECTOR DETECTING 230 MOTION VECTOR ACCUMULATOR MOTION VECTOR ACCUMULATOR TO PREDICTION BLOCK TO PREDICTION BLOCK Fig.4: PREDICTED SIGNAL PREDICTED SIGNAL 216 PIXEL-BY-PIXEL PREDICTOR PIXEL-BY-PIXEL PREDICTOR FROM FRAME MEMORY FROM FRAME MEMORY 214 NON-FEATURE POINT MOTION ESTIMATOR NON-FEATURE POINT MOTION ESTIMATOR FROM MOTION ESTIMATION BLOCK