System and method for cross correlation with application to video motion vector estimator

• US 5,535,288 A
• Filed: 02/10/1995
• Issued: 07/09/1996
• Est. Priority Date: 05/18/1992
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Silicon Engines Incorporated
• Inventors: Chen, Chih-Kang, Duluk, Jerome F. Jr.
• Primary Examiner(s): GARBER, WENDY RAE
• Application Number:
  US08/388,181
• Time in Patent Office: 515 Days
• Field of Search: 382/30, 382/41, 382/42, 382/44, 382/4, 382/34, 382/43, 382/56, 382/209, 382/218, 382/276, 382/278, 382/279, 382/280, 382/232, 382/236, 382/238, 382/248, 348/420, 348/418, 348/400, 348/401, 348/403, 348/415, 348/416, 348/417, 348/407
• US Class Current: 382/236
• CPC Class Codes: G06F 15/7857 using interleaved memory addressing G06F12/0607
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 17/153 Multidimensional correlation or convolution
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20056 Discrete and fast Fourier transform, [DFT, FFT]
• CPC Class Codes: G06T 7/231 using full search
• 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/61 in combination with predictive coding
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

Method and apparatus for computing cross-correlations with application to image processing and video motion estimation, particularly in video compression applications, are described. Two-dimensional Fourier transform convolution techniques form a basis for novel techniques for performing two simultaneous two-dimensional cross correlations. The size of the input data blocks for the transformations are arbitrary. Apparatus for efficiently performing real-time cross correlations, including cross-correlations using Short Length Transforms (SLTs), using cascaded stages, multi-port memories, and multiple arithmetic units are also described. In video motion vector estimator application, data blocks within a current video frame are selected and converted to form a two-dimensional matrix of complex data. The complex matrix is transformed to the frequency domain to form the frequency domain representations of the selected data blocks. A set of search blocks within the previous video frame having a one-to-one correspondence with the selected data blocks, is then selected, converted into a complex data matrix, and transformed to the frequency domain to form the frequency domain representations of the selected search blocks. Once in the frequency domain, the sets of data corresponding to the data blocks and the search blocks are multiplied together and the product is inverse transformed to return to the spatial domain. The data then passes through an adjustment process to form the cross-correlations between the pairs of data blocks and search blocks.

Claims

1. A data compression method for compressing first image data representing a first image signal and having a plurality of data blocks stored in a memory, each data block representing a portion of said first image data, the steps of the method comprising:

(a) selecting first and second input data blocks from said plurality of data blocks in said first image;

(b) converting the input data blocks to a complex data block by making the first data block a real part and the second data block an imaginary part of said complex data block;

(c) transforming said complex data block to a complex frequency domain data block;

(d) converting said complex frequency domain data block into a first frequency domain data block representing said first input data block and a second frequency domain data block representing said second input data block;

(e) providing data representing a second image having a plurality of search blocks, and selecting first and second input search blocks from said data representing said second image, the input search blocks corresponding to a portion of said second image most likely to contain a best match to the input data blocks;

(f) converting the input search blocks to a complex search block having real and imaginary pads by making the first search block the real pad and the second search block the imaginary pad of said complex search block;

(g) transforming said complex search block to a complex first frequency domain search block;

(h) converting said complex frequency domain search block to a first frequency domain search block representing said first input search block and a second frequency domain search block representing said second input search block;

(i) multiplying the first frequency domain blocks to form a first resultant block and multiplying the second frequency domain blocks to form a second resultant block;

(j) converting said resultant blocks into a complex resultant block;

(k) inverse transforming the complex resultant block to a resultant spatial block having real and imaginary pads;

(l) determining first and second cross-correlations between said input data blocks and said input search blocks by separating the real and imaginary pads of said resultant spatial block wherein said real part is the first cross-correlation between the first input data and search blocks and said imaginary pad is the second cross-correlation between the second input data and search blocks;

(m) finding said best match for said first and second input data blocks from the cross-correlations calculated in step (l) based on predetermined criteria;

(n) repeating steps (a) through (m) for other of said plurality of data blocks so as to generate a plurality of best matches;

(o) generating a stream of compressed second image data representing a second image signal and corresponding to at least a portion of said first image signal and having substantially the same visual information content as said first image signal but representing said first image signal with less data than said first image data, said representation in accordance with said plurality of best matches; and

(p) transmitting said generated stream of compressed second image data to a receiver.

2. The method recited in claim 1, wherein steps (c) and (g) comprise performing at least one discrete fourier transform.

3. The method recited in claim 1, further comprising the step for selecting the best cross-correlation from the cross-correlation calculated in step (l) by identifying the largest cross-correlation value.

4. The method recited in claim 1, wherein steps (c) and (g) transform only a portion of the complex blocks where transform input data has non-zero values.

5. The method recited in claim 1, wherein step (k) transforms only a portion of the complex resultant blocks where said complex resultant blocks have output data that not discarded.

6. A data compression method for compressing first image data representing a first image signal having at least one data block representing a position of said first image data in a memory, the steps of the method comprising:

(a) selecting an input data block from said at least one data block in said first image;

(b) conveding the said input data block to a complex data block by making half of the said input data block a real part and the other half of the said input data block an imaginary part of said complex data block;

(c) transforming said complex data block to a frequency domain data block representing said input data block;

(d) providing data representing a second image having a plurality of search blocks, and selecting an input search block from said data representing said second image, the input search block corresponding to a portion of said second image most likely to contain the best match to the input data block;

(e) converting the input search block to a complex search block having real and imaginary parts by making half of the input search block the real part and the other half of the input search block the imaginary part of said complex data block;

(f) transforming said complex search block to a frequency domain search block representing input search block;

(g) multiplying the frequency domain blocks to form a resultant block;

(h) inverse transforming said resultant block to a resultant spatial block;

(i) determining cross-correlations between said input data block and said input search block from said resultant spatial block; and

(j) repeating steps (a) through (i) for others of said at least one data block so as to generate a plurality of cross-correlations;

(k) generating a stream of compressed second image data representing a second image signal and corresponding to at least a portion of said first image .signal and having substantially the same visual information content as said first image signal but representing said first image signal with less data than said first image data, said representation in accordance with said plurality of cross-correlations; and

(l) transmitting said generated stream Of compressed second image data to a receiver.

7. The method recited in claim 6, wherein steps (c) and (f) comprise performing at least one discrete fourier transform.

8. The method recited in claim 6, further comprising the step of selecting the best cross-correlation from the cross-correlations calculated in step (i) based on predetermined criteria.

9. The method recited in claim 6, wherein steps (c) and (g) transform only a portion of the complex blocks where transform input data has non-zero values.

10. The method recited in claim 6, wherein step (k) transforms only a portion of the resultant blocks where said resultant blocks have output data that is not discarded.

11. A device for compressing data representing data frames of an image having a plurality of data blocks, each data block being made of a portion of a first data frame, said device comprising:

a frame memory for storing at least portions of a second data frame;

a motion estimator, including;

a data controller for selecting first and second input data blocks from said plurality of data blocks in said first data frame, and for selecting from said frame memory, first and second input search blocks from said second data frame, said input search blocks corresponding to a portion of said second data frame most likely to contain the best cross-correlation to said input data blocks;

a plurality of data processor means operable in parallel to perform data processing operations including operations on said data and search blocks under program control, said plurality of processors including;

processor means for converting the input data blocks to a complex data block having real and imaginary parts by making the first data block the real part and the second data block the imaginary part of said complex data block;

processor means for transforming said complex data block to a first frequency domain data block representing said first input data block and a second frequency domain data block representing said second input data block;

processor means for converting the input search blocks to a complex search block having real and imaginary parts by making the first search block the real part and the second search block the imaginary part of said complex search block;

processor means for transforming said complex search block to a first frequency domain search block representing said first input search block and a second frequency domain search block representing said second input search block;

processor means for multiplying the first frequency domain blocks to form a first resultant block and multiplying the second frequency domain blocks to form a second resultant block;

processor means for inverse transforming the result blocks to a resultant spatial block having real and imaginary parts; and

processor means for determining first and second cross-correlations between said input data blocks and said input search blocks by separating the real and imaginary parts of said resultant spatial block wherein said real part is the first cross-correlation between the first input data and search blocks and said imaginary part is the second cross-correlation between the second cross-correlation between the second input data and search blocks;

means, coupled to said motion estimator, for generating a stream of compressed data representing at least a portion of said first data frame based on said first and second cross-correlations; and

a transmitter that transmits said stream of compressed data.

12. A device for compressing data representing a data frame having at least one data block, said device comprising:

a frame memory for storing at least portions of said first data frame and said second data frame;

a motion vector estimator, including;

a data controller for selecting at least one input data block from said at least one data block in said first data frame and for selecting from said frame memory at least one input search block from said second data frame, the input search blocks corresponding to a portion of a second data frame most likely to contain the best cross-correlation to the input data blocks;

a plurality of data processor means operable in parallel to perform data processing operations including Operations on said data and search blocks under program control, said plurality of processors including;

processor means for converting the input data blocks to a complex data block;

processor means for transforming said complex data block to a frequency domain data block representing said input data blocks;

processor means for converting the input search blocks to a complex search block;

processor means for transforming said complex search block to a frequency domain search block representing said input search blocks;

processor means for multiplying the frequency domain blocks to form a resultant block;

processor means for inverse transforming said resultant block to a resultant spatial block; and

processor means for determining cross-correlations between said input data block and said input search block from said resultant spatial block;

means, coupled to said motion vector estimator, for generating a stream of compressed data representing at least a portion of said first data frame based on said cross-correlations; and

a transmitter that transmits said stream of compressed data.

13. The device recited in claim 12, wherein:

said data controller selects only one input data block in said first data frame and selects only one input search block from said second data frame;

said plurality of data processor means converts said input data block to a complex data block having real and imaginary pads by making a first portion of the input data block the real part and a second portion of data block the imaginary part of said complex data block; and

said plurality of data processor means converts said input search block to a complex search block having real and imaginary parts by making a first portion of the input search block the real part and a second portion of the input search block the imaginary part of said complex search block.

14. The device recited in claim 13, wherein:

said first portion of the input data block is one-half of the input data block;

said second portion of the input data block is the other half of the input data block;

said first portion of the input search block is one-half of the input search block; and

said second portion of the input search block is the other half of the input search block.

15. A device for compressing data representing a data frame having at least one data block, comprising:

a frame memory for storing at least portions of said first data frame and said second data frame;

a motion vector estimator, including;

a data controller for selecting at least one input data block from said at least one data block in said first data frame and for selecting from said frame memory at least one input search block from said second data frame, the input search blocks corresponding to a portion of a second data frame most likely to contain the best cross-correlation to the input data blocks;

first data processing apparatus that under program control perform data processing operations, said first data processing apparatus including;

processor means for converting the input data blocks to a complex data block;

processor means for transforming said complex data block to a frequency domain data block representing said input data blocks;

processor means .for converting the input search blocks to a complex search block;

processor means for transforming said complex search block to a frequency domain search block representing said input search blocks;

processor means for multiplying the frequency domain blocks to form a resultant block;

processor means for inverse transforming said resultant block to a resultant spatial block; and

processor means for determining cross-correlations between said input data block and said input search block from said resultant spatial block; and

second data processing apparatus, coupled to said motion vector estimator, for generating a stream of compressed data representing at least a portion of said first data frame based on said cross-correlations; and

a transmitter that transmits said stream of compressed data.

16. A device for compressing data representing a data frame having at least one data block, comprising:

a frame memory for storing at least portions of said first data frame and said second data frame;

data processing apparatus coupled to said frame memory and programmed to perform data processing operations;

a motion vector estimator, including;

a data controller for selecting at least one input data block from said at least one data block in said first data frame and for selecting from said frame memory at least one input search block from said second data frame, the input search blocks corresponding to a portion of a second data frame most likely to contain the best cross-correlation to the input data blocks;

said data processing apparatus including;

processor means for converting the input data blocks to a complex data block;

processor means for transforming said complex data block to a frequency domain data block representing said input data blocks;

processor means for converting the input search blocks to a complex search block;

processor means for transforming said complex search block to a frequency domain search block representing said input search blocks;

processor means for multiplying the frequency domain blocks to form a resultant block;

processor means for inverse transforming said resultant block to a resultant spatial block; and

processor means for determining cross-correlations between said input data block and said input search block from said resultant spatial block;

said data processing apparatus being coupled to said motion vector estimator and programmed to generate a stream of compressed data representing at least a portion of said first data frame based on said cross-correlations; and

a transmitter that transmits said stream of compressed data.