Hybrid hierarchial/full-search MPEG encoder motion estimation

• US 5,731,850 A
• Filed: 06/07/1995
• Issued: 03/24/1998
• Est. Priority Date: 06/07/1995
• Status: Expired due to Fees

• Current Assignee: FutureTel, Inc.
• Original Assignee: FutureTel, Inc.
• Inventors: Chen, Sho Long, Bhargava, Vivek, Wang, Ren-Yuh, Maturi, Gregory V.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US08/485,030
• Time in Patent Office: 1,021 Days
• Field of Search: 348/416, 348/699
• US Class Current: 348/699
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/238 using non-full search, e.g. three-step search
• CPC Class Codes: H04N 19/105 Selection of the reference unit for prediction within a chosen coding or prediction mode, e.g. adaptive choice of position and number of pixels used for prediction
• CPC Class Codes: H04N 19/112 according to a given display mode, e.g. for interlaced or progressive display mode
• CPC Class Codes: H04N 19/137 Motion inside a coding unit, e.g. average field, frame or block difference
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

An apparatus and method for determining inter-frame motion during compression of digital video data incorporates a computationally efficient hierarchical block-matching motion estimation technique in conjunction with a full-search block-matching approach. In the hierarchical block-matching method, a macroblock is filtered and decimated, and a search area is also filtered and decimated. A block-matching search is performed within the filtered and decimated search area. An augmented block in the original search area that corresponds to the block in the decimated search area that provided the best match with the decimated macroblock is then compared with the original macroblock to determine a motion vector. Operating parameters specify the search range based on the type of frame being processed, i.e. P-frame or B-frame, and, in the case of B-frames, the distance of the B-frame from the reference frame. If the operating parameters specify a search range above an established threshold, the hierarchical block-matching search is performed. If the operating parameters specify a search range equal to or below the established threshold, the full-search block-matching search is performed.

Claims

1. In a digital video data compression scheme, a method of estimating the frame-to-frame motion of a block of pels in a video frame comprising the steps of:

(a) filtering and decimating a block located at a position in a current frame thereby establishing a hierarchical search block;

(b) forming a search area in a reference frame, with said search area in said reference frame surrounding the position of said block in said current frame;

(c) filtering and decimating said search area in said reference frame thereby establishing a hierarchical search area;

(d) comparing said hierarchical search block with a block within said hierarchical search area;

(e) repeating step (d) for a plurality of blocks located at various positions within said hierarchical search area;

(f) identifying that region within said hierarchical search area which best matches said hierarchical search;

(g) forming an augmented block within said search area in said reference frame that surrounds a region in said search area in said reference frame that corresponds to said region within said hierarchical search area that was identified in step (f) as best matching said hierarchical search block;

(h) comparing the pels in said block in said current frame with pels in a block in said augmented block in said reference frame;

(i) repeating step (h) for a plurality of blocks located at various positions within said augmented block in said reference frame; and

(j) establishing a motion vector for said block in said current frame equal to a difference between a position of that block in said current frame and a position in said augmented block in said reference frame which best matches said block in said current frame.

2. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 1 wherein said plurality of blocks located at various positions within said hierarchical search area includes all blocks within said hierarchical search area.

3. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 1 wherein said plurality of blocks located at various positions within said augmented block includes all blocks within said augmented block.

4. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 1 wherein a plurality of motion vectors are concurrently established including an odd-odd field motion vector, an even-even field motion vector, an odd-even field motion vector, and an odd-even field motion vector.

5. In a digital video data compression scheme, a method of estimating the frame-to-frame motion of a block of pels in a video frame comprising the steps of:

(a) identifying a reference frame;

(b) identifying a block located at a position in a current frame;

(c) determining a size for a search area in said reference frame;

(d) if the size of said search area in said reference frame is larger than an established threshold, then

(i) filtering and decimating said block in said current frame thereby establishing a hierarchical search block;

(ii) forming a search area in said reference frame, with said search area in said reference frame surrounding the position of said block in said current frame;

(iii) filtering and decimating said search area in said reference frame thereby establishing a hierarchical search area;

(iv) comparing said hierarchical search block with a block within said hierarchical search area;

(v) repeating step (d) (iv) for a plurality of blocks located at various positions within said hierarchical search area;

(vi) identifying that region within said hierarchical search area which best matches said hierarchical search block;

(vii) forming an augmented block within said search area in said reference frame that surrounds a region in said search area in said reference frame that corresponds to said region within said hierarchical search area that was identified in step (d) (vi) as best matching said hierarchical search block;

(viii) comparing the pels in said block in said current frame with pels in a block in said augmented block in said reference frame;

(ix) repeating step (d) (viii) for a plurality of blocks located at various positions within said augmented block in said reference frame; and

(x) establishing a motion vector for said block in said current frame equal to a difference between a position of that block in said current frame and a position in said augmented block in said reference frame which best matches said block in said current frame;

(e) otherwise, if the size of said search area in said reference frame is equal to or less than said established threshold, then

(i) forming a search window in said reference frame, with said search window in said reference frame surrounding the position of said block in said current frame;

(ii) comparing the pels in said block in said current frame with pels in a block within said search window in said reference frame;

(iii) repeating step (e) (ii) for a plurality of blocks located at various positions within said search window in said reference frame;

(iv) establishing a motion vector for said block in said current frame equal to a difference between a position of that block in said current frame and a position in said search window in said reference frame which best matches said block in said current frame.

6. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 5 wherein said plurality of blocks located at various positions within said hierarchical search area includes all blocks within said hierarchical search area.

7. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 5 wherein said plurality of blocks located at various positions within said augmented block includes all blocks within said augmented block.

8. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 5 wherein said predetermined number of blocks within said search window in said reference frame comprises all blocks within said search window in said reference frame.

9. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 5 wherein a plurality of motion vectors are concurrently established including an odd-odd field motion vector, an even-even field motion vector, an odd-even field motion vector, and an odd-even field motion vector.

10. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 5 wherein said method of determining the size for a search area in said reference frame comprises the steps of:

(a) assigning a code to said current frame; and

(b) determining the size of said search window based on the search range specified for said code.

11. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 10 wherein said step of assigning a code to said current frame comprises the steps of:

(a) obtaining a code from a table of codes; and

(b) associating said code with said current frame.

12. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 11 wherein said step of obtaining a code from a table of codes comprises the steps of:

(a) determining whether said current frame is a P-frame or a B-frame;

(b) if said current frame is a P-frame, obtaining a code from a table of codes based on said current frame being a P-frame; and

(c) if said current frame is a B-frame, obtaining a code from a table of codes based on said current frame being a B-frame.

13. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 12 wherein said step of obtaining a code from a table of codes based on said current frame being a B-frame comprises the step of obtaining a code from a table of codes based on the distance from said current frame to said reference frame.

14. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 12 wherein said step of obtaining a code from a table of codes based on said current frame being a B-frame comprises the step of obtaining a code from a table of codes based on whether said current frame precedes or follows said reference frame.

15. The method of estimating frame-to-frame motion of a block of pels in a video frame of claim 14 wherein said step of obtaining a code from a table of codes based on said current frame being a B-frame further comprises the step of obtaining a code from a table of codes based on the distance from said current frame to said reference frame.

16. In a digital video data compression apparatus, a motion estimation apparatus for estimating the frame-to-frame motion of a block of pels in a video frame comprising:

(a) means for filtering and decimating a block located at a position in a current frame for which motion is to be estimated thereby establishing a hierarchical search block;

(b) means for forming a search area in a reference frame, the search area surrounding the position of the block in the current frame;

(c) means for filtering and decimating the search area in the reference frame thereby establishing a hierarchical search area;

(d) means for successively comparing the hierarchical search block with various blocks in the hierarchical search area;

(e) means for identifying a specific block within the hierarchical search area which best matches the hierarchical search block;

(f) means for forming an augmented block within the search area in the reference frame which surrounds a region in the search area that corresponds to the region within the hierarchical search area which best matches the hierarchical search block;

(g) means for comparing pels in the block in the current frame with pels in various successive blocks in the augmented block;

(h) means for establishing a motion vector for the block in the current frame equal to a difference between a position of that block in the current frame and a position in the augmented block in the reference frame which best matches the block in said current frame.

17. In a digital video data compression apparatus, a motion estimation apparatus for estimating the frame-to-frame motion of a block of pels in a video frame comprising:

(a) means for identifying a reference frame;

(b) means for identifying a block located at a position in a current frame for which motion is to be estimated;

(c) means for determining a size for a search area in the reference frame;

(d) means for determining if the size of the search area exceeds an established threshold for regulating estimation of frame-to-frame motion;

(e) means for filtering and decimating a block in the current frame thereby establishing a hierarchical search block;

(f) means for forming a search area in the reference frame, the search area surrounding the position of the block in the current frame;

(g) means for filtering and decimating the search area in the reference frame thereby establishing a hierarchical search area;

(h) means for successively comparing the hierarchical search block with various blocks in the hierarchical search area;

(i) means for identifying a specific block within the hierarchical search area which best matches the hierarchical search block;

(j) means for forming an augmented block within the search area in the reference frame which surrounds a region in the search area that corresponds to the region within the hierarchical search area which best matches the hierarchical search block;

(k) means for comparing pels in the block in the current frame with pels in various successive blocks in the augmented block;

(l) means for establishing a motion vector for the block in the current frame equal to a difference between a position of that block in the current frame and a position in the augmented block in the reference frame which best matches the block in said current frame;

(m) means for forming a search window in the reference frame, with said search window in the reference frame surrounding the position of the block in the current frame;

(n) means for comparing pels in the block in the current frame with pels in various successive blocks in the search window in the reference frame; and

(o) means for establishing a motion vector for the block in the current frame equal to a difference between a position of that block in the current frame and a position in the search window in the reference frame which best matches the block in the current frame.