WO2000072590A2

WO2000072590A2 - Block matching

Info

Publication number: WO2000072590A2
Application number: PCT/EP2000/004220
Authority: WO
Inventors: Piotr Wilinksi; Cornelis W. A. M. Van Overveld; Jaap A. Haitsma
Original assignee: Koninklijke Philips Electronics N.V.
Priority date: 1999-05-20
Filing date: 2000-05-08
Publication date: 2000-11-30
Also published as: WO2000072590A3

Abstract

In a block matching method in which a first block (I) of pixels is compared to a plurality of second blocks (II.1 - II.9) of pixels, A) the first block (I) is compared to a first one (II.1) of the plurality of second blocks (II.1 - II.9) to obtain a matching error; B) a part (I.a) of the first block (I) is compared to a corresponding part (II.2.a) of a next one (II.2) of the plurality of second blocks (II.1 - II.9) to obtain a partial matching error; C) if the partial matching error exceeds the matching error, the part (I.a) of the first block (I) is compared to a corresponding part (ii.3.a) of another one (II.3) of the plurality of second blocks (II.1 - II.9) to obtain a new partial matching error; D) if the partial matching error does not exceed the matching error, a remainder (I.b) of the first block (I) is compared to a corresponding remainder (II.2.b) of the next one (II.2) of the plurality of second blocks (II.1 - II.9) to obtain a second matching error; and E) if the second matching error falls below the matching error, the matching error is replaced by the second matching error, and steps B) thru E) are carried out with respect to another one (II.3) of the plurality of second blocks (II.1 - II.9) unless all second blocks (II.1 - II.9) have already been compared to the first block (I).

Description

Block matching.

The invention relates to a method and device for block matching such as used in motion vector estimation and/or depth estimation. The invention also relates to a display apparatus comprising such a block-matching device.

Block based motion and depth estimation techniques propose to consider an image as a set of blocks obtained most often by a tessellation of the image in squares of uniform size. Such an approach allows matching of those blocks, i.e. the comparison between blocks of the same size in consecutive images. The goal of block matching is to find the best matching block from a finite candidate set. To do this a measure which expresses the similarity of two blocks is used. Most of the time this measure has the form of a mean square criterion.

Block matching algorithms are iterative minimization algorithms which assume that all pixels within a given block move uniformly, say with vector (i,j). If for that block we minimize the Mean Squared Error (MSE) with respect to vector (i,j) ι M N MSE(i, j) = —- Y ∑ [U_t = im, n) - U<(m + i, n + j)Y

MN „,₌₁ „₌₁ we can find after convergence, the most likely motion for that block from time t to t+1. Here M,N are the dimensions of the block in pixels. U_t(m,n) is the pixel intensity of a scene at time t, at the location (m,n). The vectors (ij) are taken from a set CS of candidate vectors. After computing the MSE for all the elements of CS in a sequential way, the candidate that has the minimal value of MSE over CS is chosen and its MSE called the matching penalty (MP). See G. de Haan and P. Biezen, "Sub-pixel motion estimation with 3D recursive search block matching", Signal Processing: Image Communication 6. 1994, pp. 229-239.

US-A-5,818,969 discloses a motion estimation search in which a "good enough" match allows early termination of the search.

It is, inter alia, an object of the invention to provide a more efficient search. To this end, the invention provides a block matching method and device, and a display apparatus, as defined in the independent claims. Advantageous embodiments are defined in the dependent claims.

In a block matching method in accordance with a primary aspect of the invention, in which a first block of pixels is compared to a plurality of second blocks of pixels, A) the first block is compared to a first one of the plurality of second blocks to obtain a matching error,

B) a part of the first block is compared to a corresponding part of a next one of the plurality of second blocks to obtain a partial matching error

C) if the partial matching error exceeds the matching error, the part of the first block is compared to a corresponding part of another one of the plurality of second blocks to obtain a new partial matching error;

D) if the partial matching error does not exceed the matching error, a remainder of the first block is compared to a corresponding remainder of the next one of the plurality of second blocks to obtain a second matching error; and E) if the second matching error falls below the matching error, the matching error is replaced by the second matching error, and steps B) thru E) are carried out with respect to another one of the plurality of second blocks unless all second blocks have already been compared to the first block.

These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.

In the drawings:^'

Fig. 1 shows a first field comprising a first block of pixels, and a second field comprising a plurality of second blocks of pixels; and Fig. 2 shows an embodiment of a display apparatus in accordance with the present invention.

The invention is a proposition of how to speed up matching algorithm. The improvement concerns the way in which the computation of the match penalty is done. It is proposed to change the MSE computation scheme for the CS by carrying out the following steps. These steps are illustrated by Fig. 1, which shows a first field Fl comprising a first block I of pixels, and a second field F2 comprising a plurality of second blocks II.1 thru II.9 of pixels. 1. The MSE for the first element (in Fig. 1 , the vector from block I in field F 1 to block II.1 in field F2) of the CS is computed. It is supposed to be a temporary value MP.

2. The MSE for the next element (in Fig. 1 , the vector from block I in field Fl to block II.2 in field F2) of CS is computed on an incremental basis taking into account pairs of pixels from the blocks that are compared. After a number of increments (in Fig. 1 , when part II.2. a of block II.2 in field F2 has been compared to corresponding part La of block I in field Fl) the value of MSE is compared with the MP. a. If MSE is bigger than MP it's not worth continuing the computation for this pair of blocks. Return to point 2) with a new element of CS. In Fig. 1, block I is compared to block II.3 b. If MSE is smaller than MP the computation continues for the next pair of pixels. So. in Fig. 1, the remainder I.b of block I is compared to the remainder II.2.b of block II.2.

3. If all the pixels in the blocks have been taken into account and the MSE is still smaller than MP, let MP=MSE.

4. Take the next element of CS.

As "if statements are computationally expensive, depending on the implementation (hardware/software) the comparison from the point 2) does not have to be done for each pixel. It can be done on a periodical basis. Instead of mean square errors (MSE), other error measures can be used such as a sum of square errors, a mean absolute difference, or a sum of absolute differences. All such error measures are within the scope of the invention as claimed.

Fig. 2 shows an embodiment of a display apparatus in accordance with the present invention. An antenna A furnishes television signals to a tuner and video signal processor TUN/VSP, which supplies a base-band video signal. The field frequency is doubled by a first field memory FM1 that twice supplies each field it receives. The output of the field memory FM1 is motion-compensated by an arrangement comprising a second field memory FM2 for providing a field delay, a motion vector estimator ME for generating motion vectors from a field and a delayed field, a vector memory VM for providing a plurality of previously estimated vectors as candidate vectors for a new estimation, and a motion-compensated interpolator MCI for providing the motion-compensated output signal of the arrangement on the basis of a field and a delayed field, and the motion vectors from the motion vector estimator ME. The motion-compensated output signal is displayed by a display device DD. A primary aspect of the invention can be summarized as follows. The block matching computation is speeded up by computing the matching error for a first block, and storing the result. For a subsequent block, somewhere during the computation it is checked whether the matching error result computed so far exceeds the previously stored result. If so, that block will have a higher match error than the previous block, so that it does not make sense to continue computing the match error. This saves the calculation effort for continuing the computation of the match error of the second block. If the intermediate result does not exceed the previously stored result, the calculation is finished. If the outcome is lower than the previously stored result, the new result is used as comparison value for another subsequent block. The invention results in less computational efforts being needed. The invention can be used in block matching algorithms when the whole set of MSE obtained for the CS is not used in other computations. Speed up depends on the image that is processed, but is typically of the order of 2. The invention is advantageously applied in block-based motion estimation and block-based depth reconstruction.

It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word "comprising" does not exclude the presence of elements or steps other than those listed in a claim. The word "a" or "an^"" preceding an element does not exclude the presence of a plurality of such elements. The invention can be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In the device claim enumerating several means, several of these means can be embodied by one and the same item of hardware.

Claims

CLAIMS:

1. A block matching method in which a first block (I) of pixels is compared to a plurality of second blocks (II.1 - II.9) of pixels, the method comprising the steps of: A) comparing said first block (I) to a first one (II.1) of said plurality of second blocks to obtain a matching error; B) comparing a part (La) of said first block (I) to a corresponding part (II.2. a) of a next one (II.2) of said plurality of second blocks (II.1 - II.9) to obtain a partial matching error; C) if said partial matching error exceeds said matching error, comparing said part

(La) of said first block (I) to a corresponding part (II.3.a) of another one (II.3) of said plurality of second blocks (II.1 - II.9) to obtain a new partial matching error; D) if said partial matching error does not exceed said matching error, comparing a remainder (Lb) of said first block (I) to a corresponding remainder (II.2. b) of said next one (II.2) of said plurality of second blocks (II.1 - II.9) to obtain a second matching error; and E) if said second matching error falls below said matching error, replacing said matching error by said second matching error, and carrying out steps B) thru E) with respect to another one (II.3) of said plurality of second blocks (II.1 - II.9) unless all second blocks (II.1 - II.9) have already been compared to said first block (I).

2. A motion and/or depth estimation arrangement comprising a device (ME, VM) arranged for carrying out the method of claim 1.

3. A display apparatus, comprising: an image memory (FM2); a motion estimation arrangement (ME, VM) as claimed in claim 2, coupled to an input and an output of said image memory (FM2) for generating a motion vector corresponding to a position of said first block to that second block that upon comparison with said first block yielded said matching error; a motion-compensated interpolation device (MCI) coupled to said input and said output of said image memory (FM2) for generating a motion-compensated output image; and a display device (DD) for displaying said motion-compensated output image.