Methods and apparatus for fast correlation
First Claim
1. An image processing system responsive to a model signal comprising model pixel values and an image signal comprising image pixel values for generating a score signal representative of a degree of correlation between said model signal and said image signal, said system including:
- A. cache memory means for storing for addressable access algebraic squares corresponding to any of model pixel values, image pixel values and sums of image and model pixel values,said cache memory means being responsive to an address signal based on any such value for accessing and generating a signal representative of a corresponding algebraic square,B. central processing unit (CPU) means, coupled to said cache memory means, for processing said model signal and said image signal to generate said score signal, said CPU means including(i) model square means responsive to said model signal for applying to said cache memory means address signals based on at least selected ones of said model pixel values to generate a Σ
Σ
m2 signal comprising sums of the squares of those values,(ii) image square means responsive to said image signal for applying to said cache memory means address signals based on at least selected ones of said image pixel values to generate a Σ
Σ
i2 signal comprising sums of the squares of those values, and(iii) sum square means responsive to said model and image signals for applying to said cache memory means address signals based on sums of at least selected corresponding ones of said image pixel values and model pixel values to generate a Σ
Σ
(i+m)2 signal comprising sums of the squares of those sums,(iv) correlation means, coupled to said model square means, said image square means and said sum square means, for generating said score signal as a function of values in said Σ
Σ
m2 signal, said Σ
Σ
i2 signal, and said Σ
Σ
(i+m)2 signal.
1 Assignment
0 Petitions
Accused Products
Abstract
An image processing system generates a correlation of a model signal and the image signal using an array of algebraic squares of pixel values and sums thereof stored in cache memory. A CPU, coupled to the cache memory, addresses the cache memory array in accord with image pixel values to generate a ΣΣI2 signal comprising the sum of squares of those values. The CPU also addresses the cache memory array in accord with the sums of corresponding image and model pixel values to generate a ΣΣ(I+M)2 signal. A correlation element generates a score signal as a function of the mathematical expression ΣΣ(Iij+Mij)2 -ΣΣIij2 -ΣΣMij2.
59 Citations
11 Claims
-
1. An image processing system responsive to a model signal comprising model pixel values and an image signal comprising image pixel values for generating a score signal representative of a degree of correlation between said model signal and said image signal, said system including:
-
A. cache memory means for storing for addressable access algebraic squares corresponding to any of model pixel values, image pixel values and sums of image and model pixel values, said cache memory means being responsive to an address signal based on any such value for accessing and generating a signal representative of a corresponding algebraic square, B. central processing unit (CPU) means, coupled to said cache memory means, for processing said model signal and said image signal to generate said score signal, said CPU means including (i) model square means responsive to said model signal for applying to said cache memory means address signals based on at least selected ones of said model pixel values to generate a Σ
Σ
m2 signal comprising sums of the squares of those values,(ii) image square means responsive to said image signal for applying to said cache memory means address signals based on at least selected ones of said image pixel values to generate a Σ
Σ
i2 signal comprising sums of the squares of those values, and(iii) sum square means responsive to said model and image signals for applying to said cache memory means address signals based on sums of at least selected corresponding ones of said image pixel values and model pixel values to generate a Σ
Σ
(i+m)2 signal comprising sums of the squares of those sums,(iv) correlation means, coupled to said model square means, said image square means and said sum square means, for generating said score signal as a function of values in said Σ
Σ
m2 signal, said Σ
Σ
i2 signal, and said Σ
Σ
(i+m)2 signal. - View Dependent Claims (2, 3, 8)
-
-
4. An image processing system responsive to a model signal comprising model pixel values and an image signal comprising image pixel values for generating a score signal representative of a degree of correlation between said model signal and said image signal, said system including:
-
A. cache memory means for storing for addressable access algebraic squares corresponding to any of model pixel values, image pixel values and sums of image and model pixel values, said cache memory means being responsive to an address signal based on any such value for accessing and generating a signal representative of a corresponding algebraic square, B. central processing unit (CPU) means, coupled to said cache memory means, for processing said model signal and said image signal to generate said score signal, said CPU means including (i) image square means responsive to said image signal for applying to said cache memory means address signals based on at least selected ones of said image pixel values to generate a Σ
Σ
i2 signal comprising sums of the squares of those values, and(ii) sum square means responsive to said model and image signals for applying to said cache memory means address signals based on sums of at least selected corresponding ones of said image pixel values and model pixel values to generate a Σ
Σ
(i+m)2 signal comprising sums of the squares of those sums,(iii) correlation means, coupled to said image square means and said sum square means, for generating said score signal as a function of values in said Σ
Σ
i2 signal, and said Σ
Σ
(i+m)2 signal. - View Dependent Claims (5, 6, 7)
-
-
9. A method for generating a score signal representative of a degree of correlation between a model signal comprising model pixel values and an image signal comprising image pixel values, in an image processing system, said method comprising:
-
A. storing for addressable access in an on-chip cache memory of a central processing unit (CPU) algebraic squares corresponding to any of model pixel values, image pixel values, and sums of image and model pixel values, B. processing, in said CPU, the model signal and the image signal, to generate a score signal, including; (i). generating a Σ
Σ
I2 signal comprising the squares of the image pixel values, by applying to said cache memory address signals based on said image pixel values,(ii). generating a Σ
Σ
(I+M)2 signal comprising the squares of sums of corresponding image and pixel values, by applying to said cache memory address signals based on said sums,(iii). generating, in response to said Σ
Σ
I2 signal and said Σ
Σ
(I+M)2 signal a score signal, a correlation as a function of the values of said Σ
Σ
I2 signal and said Σ
Σ
(I+M)2 signal. - View Dependent Claims (10, 11)
-
Specification