System and method for performing motion estimation in the DCT domain with improved efficiency
First Claim
1. A method for performing motion estimation between a target frame and a search frame, wherein the target frame includes a plurality of target blocks, the method comprising:
- performing a frequency domain transform on the plurality of target blocks in the target frame;
selecting a candidate block from the search frame;
performing a frequency domain transform on the selected candidate block from the search frame;
determining one or more target blocks in the target frame in response to said selected candidate block;
computing a distance between the transformed values of the selected candidate block and the transformed values of each of said one or more determined target blocks, wherein said computing produces a distance for each of said one or more determined target blocks;
determining if said computed distance is a better metric than a currently stored computed distance for each of said one or more determined target blocks;
storing a location of said selected candidate block for a respective target block if said computed distance for said respective target block is a better metric than the current best computed distance for said respective target block;
wherein said selecting a candidate block from the search frame, performing a frequency domain transform on the selected candidate block from the search frame, determining one or more target blocks in the target frame, computing a distance, determining if said computed distance is a better metric, and storing a location of said selected candidate block, are performed for a plurality of candidate blocks in said search frame, wherein said performing for said plurality of candidate blocks in said search frame produces motion vectors for a plurality of said target blocks in said target frame.
7 Assignments
0 Petitions
Accused Products
Abstract
A system and method for estimating motion vectors between frames of a video sequence which operates in the DCT domain with improved efficiency and reduced computational requirements. The motion estimation system operates to encode a target block using pointers or motion vectors to a previously encoded block, referred to as the reference block or search block. The system first partitions the target frame into a plurality of target blocks, and DCT transforms the target blocks in the target frame. The motion estimation system then selects a candidate block from the search frame and DCT transforms the selected candidate block. The motion estimation system uses a novel method for selecting candidate blocks which allows re-use of at least a portion of the transformed values of a prior selected candidate block. After the candidate block is selected, the motion estimation system determines one or more "relevant" target blocks in the target frame which have a corresponding search window which includes the selected candidate block. The system then computes a distance between the transformed values of the selected candidate block and the transformed values of each of the determined target blocks. If a better metric is found for a respective target block, the system stores the location of the selected candidate block for the respective target block. The above steps are performed for each of the possible candidate blocks in the search frame. This method thus produces or determines "best fit" candidate blocks for each of the target blocks. The system then computes motion vectors for each of the target blocks in the target frame based on these "best fit" blocks.
74 Citations
29 Claims
-
1. A method for performing motion estimation between a target frame and a search frame, wherein the target frame includes a plurality of target blocks, the method comprising:
-
performing a frequency domain transform on the plurality of target blocks in the target frame; selecting a candidate block from the search frame; performing a frequency domain transform on the selected candidate block from the search frame; determining one or more target blocks in the target frame in response to said selected candidate block; computing a distance between the transformed values of the selected candidate block and the transformed values of each of said one or more determined target blocks, wherein said computing produces a distance for each of said one or more determined target blocks; determining if said computed distance is a better metric than a currently stored computed distance for each of said one or more determined target blocks; storing a location of said selected candidate block for a respective target block if said computed distance for said respective target block is a better metric than the current best computed distance for said respective target block; wherein said selecting a candidate block from the search frame, performing a frequency domain transform on the selected candidate block from the search frame, determining one or more target blocks in the target frame, computing a distance, determining if said computed distance is a better metric, and storing a location of said selected candidate block, are performed for a plurality of candidate blocks in said search frame, wherein said performing for said plurality of candidate blocks in said search frame produces motion vectors for a plurality of said target blocks in said target frame. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. An MPEG encoder for performing motion estimation between a target frame and a search frame, wherein the target frame includes a plurality of target blocks, the MPEG encoder comprising:
-
a DCT transform block for performing a frequency domain transform on the plurality of target blocks in the target frame; means for selecting a candidate block from the search frame, wherein the DCT block performs a frequency domain transform on the selected candidate block from the search frame; means for determining one or more target blocks in the target frame in response to the selected candidate block; means for computing a distance between the transformed values of the selected candidate block and the transformed values of each of said one or more determined target blocks, wherein said computing produces a distance for each of said one or more determined target blocks; means for determining if said computed distance is a better metric than a currently stored computed distance for each of said one or more determined target blocks; a memory for storing a location of said selected candidate block for a respective target block if said computed distance for said respective target block is a better metric than the current best computed distance for said respective target block; wherein said means for selecting a candidate block from the search frame, said DCT block for performing a frequency domain transform on the selected candidate block from the search frame, said means for determining one or more target blocks in the target frame, said means for computing a distance, said means for determining if said computed distance is a better metric, and said memory storing a location of said selected candidate block, operate for a plurality of candidate blocks in said search frame, wherein said MPEG encoder produces motion vectors for a plurality of said target blocks in said target frame. - View Dependent Claims (21, 22, 23, 24, 25)
-
-
26. A method for performing motion estimation between a target frame and a search frame, wherein the target frame includes a plurality of target blocks, the method comprising:
-
selecting a candidate block from the search frame; determining one or more target blocks in the target frame in response to said selected candidate block; computing a distance between the values of the selected candidate block and the values of each of said one or more determined target blocks, wherein said computing produces a distance for each of said one or more determined target blocks; determining if said computed distance is a better metric than a currently stored computed distance for each of said one or more determined target blocks; storing a location of said selected candidate block for a respective target block if said computed distance for said respective target block is a better metric than the current best computed distance for said respective target block; wherein said selecting a candidate block from the search frame, determining one or more target blocks in the target frame, computing a distance, determining if said computed distance is a better metric, and storing a location of said selected candidate block, are performed for a plurality of candidate blocks in said search frame, wherein said performing for said plurality of candidate blocks in said search frame produces motion vectors for a plurality of said target blocks in said target frame. - View Dependent Claims (27, 28, 29)
-
Specification