US 5,731,850 AGranted

Hybrid hierarchial/full-search MPEG encoder motion estimation

OwnerGregory V. Maturi, Vivek Bhargava +2inventors

InventorsGregory V. Maturi, Vivek Bhargava, Sho Long Chen, Ren-Yuh Wang

Life of this patent

Estimating the term…

Loading patent…

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.

Claims17

Dependent claims

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.

8 more elements

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.

17 more elements

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.

13 more elements

Dependencies are inferred from the claim text.