Method and apparatus for block-based motion estimation
First Claim
1. In a system that compresses multi-bit data that is in the form of sequential frames of data, the system analyzing a first frame and a second frame and deriving changes therebetween to thereby permit reconstruction of the second frame from the first frame, a method of block-based motion estimation, comprising:
- (a) selecting a data block in the first frame;
(b) applying a function to convert multi-bit data in the data block to a first group of data having a reduced number of bits;
(c) applying a function to convert multi-bit data in the second frame to data having a reduced number of bits;
(d) comparing the first group of data with data from the second frame having a reduced number of bits to yield an output;
(e) repeating (c)-(d) to compare the same first group of data with different groups of data from the second frame (corresponding to different sets of data in the second frame);
(f) comparing the outputs of (d) with each other and responsively selecting a particular set of data in the second frame which corresponds to a best fit of the data block within at least a portion of the second frame; and
(g) in response to the best fit, deriving motion data that corresponds to motion of data in the data block between the first and second frames.
3 Assignments
0 Petitions
Accused Products
Abstract
This disclosure provides a method of block-based motion estimation used in video compression. The compression process, derives change data for a new frame of data (with respect to a reference frame) by first dividing the frame structure into data tiles (or data blocks) of identical size. Each tile in the new frame is compared to a localized window (about the tile'"'"'s expected position) in the reference frame to search for a best fit, and thereby provide motion data for the particular tile. Once the best fit is determined, motion-compensated difference data is determined, and stored with the motion data for each tile to complete the process. To achieve computation efficiency, each tile under analysis is preferably converted to single-bit value data and searching and comparisons are performed based on such transformed single-bit data. The single-bit data is computed by convolving the original image data with a low-pass filter to obtain a threshold matrix. The original image data is then compared with the threshold matrix, and converted to single-bit values in dependence on whether the values of the data exceed counterparts in the threshold matrix. Comparison is performed using an exclusive-or function and bit-summation of results.
-
Citations
19 Claims
-
1. In a system that compresses multi-bit data that is in the form of sequential frames of data, the system analyzing a first frame and a second frame and deriving changes therebetween to thereby permit reconstruction of the second frame from the first frame, a method of block-based motion estimation, comprising:
-
(a) selecting a data block in the first frame; (b) applying a function to convert multi-bit data in the data block to a first group of data having a reduced number of bits; (c) applying a function to convert multi-bit data in the second frame to data having a reduced number of bits; (d) comparing the first group of data with data from the second frame having a reduced number of bits to yield an output; (e) repeating (c)-(d) to compare the same first group of data with different groups of data from the second frame (corresponding to different sets of data in the second frame); (f) comparing the outputs of (d) with each other and responsively selecting a particular set of data in the second frame which corresponds to a best fit of the data block within at least a portion of the second frame; and (g) in response to the best fit, deriving motion data that corresponds to motion of data in the data block between the first and second frames. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. An apparatus, comprising:
-
a first memory that stores multi-bit data from a first frame; a second memory that stores multi-bit data from a second frame; and means coupled to the first memory for converting a block of data within the first frame to values having a reduced number of bits; means coupled to the second memory for converting data in a search window in the second frame to values having a reduced number of bits, the search window selected be larger in size than the block; and means for comparing the values corresponding to the block with the values corresponding to the search window, for analyzing results of the comparing to select a group of data in the search window that provides a best fit for the data of the data block, and for producing motion data indicating location of the best fit.
-
-
14. An apparatus including machine readible instructions and computer-readable media on which the instructions are stored, for use in a system that compresses multi-bit data that is in the form of sequential frames of data, the system analyzing a first frame and a second frame and deriving changes therebetween to thereby permit reconstruction of the second frame from the first frame, the instructions when executed causing the system to:
-
(a) select a data block in the first frame; (b) apply a function to convert multi-bit data in the data block to a first group of data having a reduced number of bits; (c) apply a function to convert multi-bit data falling within at least a window of data from the second frame to data having a reduced number of bits, and selecting therefrom a second group of data which corresponds in size to the data block; (d) compare the first group of data with the second group of data to yield an output; (e) repeat (c)-(d) for different sets of data in the second frame which have already been converted in (c) to data having a reduced number of bits; (f) compare the outputs of (d) with each other and responsively select a particular set of data in the second frame which corresponds to a best fit of the data block in at least a portion of the second frame; and (g) in response to the best fit, derive motion data that corresponds to motion of data in the data blocks between the first and second frames. - View Dependent Claims (15, 16)
-
-
17. In a system that compresses multi-bit data that is in the form of sequential frames of data, the system analyzing a first frame and a second frame and deriving changes therebetween to thereby permit reconstruction of the second frame from the first frame, a method of block-based motion estimation, comprising:
-
(a) selecting a data block in the first frame; (b) applying a function to transform multi-bit data in the data block to a first group of data having a reduced number of bits, in a manner that emphasizes edge transitions; (c) applying a function to transform multi-bit data in the second frame to data having a reduced number of bits, in a manner that emphasizes edge transitions; (d) comparing the first group of data with data from the second frame having a reduced number of bits to yield an output; (e) repeating (c)-(d) to compare the same first group of data with different groups of data from the second frame (corresponding to different sets of data in the second frame); (f) comparing the outputs of (d) with each other and responsively selecting a particular set of data in the second frame which corresponds to a best fit of the data block within at least a portion of the second frame, to thereby identify a particular set of data in the second frame which most closely replicates edge transitions falling within the data block; and (g) in response to the best fit, deriving motion data that corresponds to motion of data in the data block between the first and second frames.
-
-
18. In a system that compresses multi-bit data that is in the form of sequential frames of data, the system analyzing a first frame and a second frame and deriving changes therebetween to thereby permit reconstruction of the second frame from the first frame, a method of block-based motion estimation, comprising:
-
(a) selecting a data block in the first frame; (b) applying a function to convert multi-bit data in the data block to a first group of data having a reduced number of bits; (c) applying a function to convert multi-bit data in the second frame to data having a reduced number of bits; (d) comparing the first group of data with data from the second frame having a reduced number of bits to yield an output; (e) repeating (c)-(d) to compare the same first group of data with different groups of data from the second frame (corresponding to different sets of data in the second frame); (f) comparing the outputs of (d) with each other and responsively selecting a particular set of data in the second frame which corresponds to a best fit of the data block within at least a portion of the second frame; and (g) in response to the best fit, deriving motion data that corresponds to motion of data in the data block between the first and second frames; (h) wherein applying a function to convert multi-bit data to at least one of the data block and data from the second frame includes developing at least one threshold value, and in dependence upon a comparison between multi-bit data and a threshold value, transforming the multi-bit data to a single-bit value data. - View Dependent Claims (19)
-
Specification