Method and apparatus for block-based motion estimation

Claim 2

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.

Claim 3

A method according to claim 1, wherein applying a function to convert multi-bit data includes: converting multi-bit data to single-bit data based upon a comparison of each multi-bit datum with a threshold.

Claim 4

A method according to claim 1, wherein applying a function to convert multi-bit data includes: applying a low-pass filter to the data and developing a threshold matrix therefrom, and converting data based upon a comparison of individual pixel intensity values with corresponding threshold values from the threshold matrix.

Claim 5

A method according to claim 1, wherein the frames are image frames and the data includes pixels representing intensity data in two spatial dimensions, and wherein: selecting a data block includes selecting a block of pixels; applying a function to convert multi-bit data in the data block includes converting multi-bit data to a first group of single-bit value data; applying a function to convert multi-bit data in the second frame includes converting multi-bit data to single-bit value data; and repeating (c)-(d) includes comparing data to match the block of pixels against different sets of pixels corresponding to at least a portion of the second frame.

Claim 6

A method according to claim 1, wherein the frames are frames of visual data, the multi-bit data includes multi-bit intensity data, and the data block represents a two-dimensional block of pixels at a predefined position within the first frame, and wherein: said method further comprises selecting a window in the second frame, the window chosen to be larger in size than the data block; selecting data in the second frame includes selecting a set of data to lie within the window; and repeating includes sequentially searching different sets of pixels within the window, each set identical in size and two-dimensional shape to each other and to the block.

Claim 7

A method according to claim 5, wherein deriving motion data includes: producing a two-dimensional motion vector to represent position in the second frame of a best fit of the data block with respect to the first frame.

Claim 8

A method according to claim 5, wherein said method uses a digital register, and the two-dimensional block is a square block of sixteen pixels by sixteen pixels, and wherein comparing the first group of data with data from the second frame includes: sequentially performing an exclusive-or function between the first group and data from the second frame having a reduced number of bits using the register; and selecting the best fit to be a set of data from the second frame having a reduced number of bits that yields a minimum value from the exclusive-or function.

Claim 9

A method according to claim 7, wherein: developing a threshold value includes developing a set of threshold values from the data block by applying a low-pass filter to the data block.

Claim 10

A method according to claim 8, wherein the data block represents a pixel matrix of size n by m where n and m are integers and wherein: developing a set of threshold values includes developing a threshold matrix by convolving a low-pass matrix of approximate size n by m with the pixel matrix; and transforming each datum includes comparing the multi-bit value of each datum in the pixel matrix with a corresponding value in the threshold matrix, and in response to the comparison, converting the multi-bit value of each datum in the pixel matrix to one of a logical true and false to thereby generate the single bit data of the first group.

Claim 11

A method according to claim 9, wherein m equals n and wherein: developing a threshold matrix includes developing a threshold matrix that is a n by n square matrix.

Claim 12

A method according to claim 9, wherein: developing a low-pass matrix includes developing a low-pass matrix having a values of approximately 0.04 every fourth row and every fourth column, and zero otherwise.

Claim 13

A method according to claim 9, wherein: transforming each datum includes comparing multi-bit value data from the pixel matrix with corresponding data in the threshold matrix, and forming the first group to be a matrix having a value of one for each multi-bit value datum that is greater than a corresponding datum in the threshold matrix, and a zero for each datum that is less than a corresponding datum in the threshold matrix.

Claim 18

An apparatus according to claim 14, wherein the instructions when executed cause the system to: perform (b) by converting pixel intensity values to single-bit value data; and perform (c) by converting pixel intensity values to single-bit value data.

Claim 19

An apparatus according to claim 15, wherein converting pixel intensity values to single-bit value data includes: applying a low-pass filter to pixel intensity values to yield therefrom a threshold matrix, the threshold matrix having plurality of individual thresholds; and comparing individual pixel intensity values with corresponding individual thresholds, and as a result of comparing, generating a matrix of single-bit value data, with each datum representing a result of comparison between a pixel intensity value and a corresponding threshold.

Claim 20

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.

Claim 21

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.

Claim 22

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.

Claim 23

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.

Claim 24

A method according to claim 18, wherein: said method further comprises selecting a window of multi-bit data in the second frame, the window chosen to be larger in size than the data block; selecting data in the second frame includes selecting a set of data from within the window, the set identical in shape and size to the data block; developing at least one threshold value includes convolving a low-pass matrix of approximate size n by m with data from the second frame, including data in the set; applying a function to convert multi-bit data in the second frame includes comparing each datum in the set of data with a corresponding threshold value to yield, for each datum in the set, a single-bit value representing a result of the comparison; and repeating includes repeating (c)-(d) using different sets of data from within the window, each set identical in shape and size to the data block and to each other.