Cross-correlation
Encyclopedia
In signal processing
, cross-correlation is a measure of similarity of two waveforms as a function of a time-lag applied to one of them. This is also known as a sliding dot product
or sliding inner-product. It is commonly used for searching a long-duration signal for a shorter, known feature. It also has applications in pattern recognition
, single particle analysis, electron tomographic averaging, cryptanalysis
, and neurophysiology
.
For continuous functions, f and g, the cross-correlation is defined as:
where f * denotes the complex conjugate
of f.
Similarly, for discrete functions, the cross-correlation is defined as:
The cross-correlation is similar in nature to the convolution
of two functions.
In an autocorrelation
, which is the cross-correlation of a signal with itself, there will always be a peak at a lag of zero unless the signal is a trivial zero signal.
In probability theory
and statistics
, correlation is always used to include a standardising factor in such a way that correlations have values between −1 and +1, and the term cross-correlation is used for referring to the correlation
corr(X, Y) between two random variables X and Y, while the "correlation" of a random vector X is considered to be the correlation matrix (matrix of correlations) between the scalar elements of X.
If
and 
are two independent random variable
s with probability density function
s f and g, respectively, then the probability density of the difference
is formally given by the cross-correlation (in the signal-processing sense) 
; however this terminology in not used in probability and statistics. In contrast, the convolution
(equivalent to the cross-correlation of f(t) and g(−t) ) gives the probability density function of the sum 
.
and 
differing only by an unknown shift along the x-axis. One can use the cross-correlation to find how much 
must be shifted along the x-axis to make it identical to 
. The formula essentially slides the 
function along the x-axis, calculating the integral of their product at each position. When the functions match, the value of 
is maximized. This is because when peaks (positive areas) are aligned, they make a large contribution to the integral. Similarly, when troughs (negative areas) align, they also make a positive contribution to the integral because the product of two negative numbers is positive.
With complex-valued functions
and 
, taking the conjugate
of
ensures that aligned peaks (or aligned troughs) with imaginary components will contribute positively to the integral.
In econometrics
, lagged cross-correlation is sometimes referred to as cross-autocorrelation
where
denotes the Fourier transform, and an asterisk again indicates the complex conjugate. Coupled with fast Fourier transform
algorithms, this property is often exploited for the efficient numerical computation of cross-correlations. (see circular cross-correlation)
. That is, the cross-correlation of a template,
with a subimage 
is
where
is the number of pixels in 
and 
,
is the average of f and
is standard deviation
of f.
In functional analysis
terms, this can be thought of as the dot product of two normalized vectors. That is, if
and
then the above sum is equal to
where
is the inner product and 
is the L² norm
.
Thus, if f and t are real matrices, their normalized cross-correlation equals the cosine of the angle between the unit vectors F and T, being thus 1 if and only if F equals T multiplied by a positive scalar.
Normalized correlation is one of the methods used for template matching
, a process used for finding incidences of a pattern or object within an image. It is in fact just the 2-dimensional version of Pearson product-moment correlation coefficient
.
, the cross correlation between two time series describes the normalized cross covariance function.
Let
represent a pair of stochastic process
es that are jointly wide sense stationary. Then the cross covariance is given by
where
and 
are the means of 
and 
respectively.
The cross correlation function
is the normalized cross-covariance function.
Note that if
for all t, then the cross correlation function is simply the autocorrelation function.
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
, cross-correlation is a measure of similarity of two waveforms as a function of a time-lag applied to one of them. This is also known as a sliding dot product
Dot product
In mathematics, the dot product or scalar product is an algebraic operation that takes two equal-length sequences of numbers and returns a single number obtained by multiplying corresponding entries and then summing those products...
or sliding inner-product. It is commonly used for searching a long-duration signal for a shorter, known feature. It also has applications in pattern recognition
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
, single particle analysis, electron tomographic averaging, cryptanalysis
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
, and neurophysiology
Neurophysiology
Neurophysiology is a part of physiology. Neurophysiology is the study of nervous system function...
.
For continuous functions, f and g, the cross-correlation is defined as:
where f * denotes the complex conjugate
Complex conjugate
In mathematics, complex conjugates are a pair of complex numbers, both having the same real part, but with imaginary parts of equal magnitude and opposite signs...
of f.
Similarly, for discrete functions, the cross-correlation is defined as:
The cross-correlation is similar in nature to the convolution
Convolution
In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
of two functions.
In an autocorrelation
Autocorrelation
Autocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...
, which is the cross-correlation of a signal with itself, there will always be a peak at a lag of zero unless the signal is a trivial zero signal.
In probability theory
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
and statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
, correlation is always used to include a standardising factor in such a way that correlations have values between −1 and +1, and the term cross-correlation is used for referring to the correlation
Covariance and correlation
In probability theory and statistics, the mathematical descriptions of covariance and correlation are very similar. Both describe the degree of similarity between two random variables or sets of random variables....
corr(X, Y) between two random variables X and Y, while the "correlation" of a random vector X is considered to be the correlation matrix (matrix of correlations) between the scalar elements of X.
If
and are two independent random variableRandom variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
s with probability density function
Probability density function
In probability theory, a probability density function , or density of a continuous random variable is a function that describes the relative likelihood for this random variable to occur at a given point. The probability for the random variable to fall within a particular region is given by the...
s f and g, respectively, then the probability density of the difference
is formally given by the cross-correlation (in the signal-processing sense) ; however this terminology in not used in probability and statistics. In contrast, the convolutionConvolution
In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
(equivalent to the cross-correlation of f(t) and g(−t) ) gives the probability density function of the sum .Explanation
For example, consider two real valued functions and differing only by an unknown shift along the x-axis. One can use the cross-correlation to find how much must be shifted along the x-axis to make it identical to . The formula essentially slides the function along the x-axis, calculating the integral of their product at each position. When the functions match, the value of is maximized. This is because when peaks (positive areas) are aligned, they make a large contribution to the integral. Similarly, when troughs (negative areas) align, they also make a positive contribution to the integral because the product of two negative numbers is positive.With complex-valued functions
and , taking the conjugateComplex conjugate
In mathematics, complex conjugates are a pair of complex numbers, both having the same real part, but with imaginary parts of equal magnitude and opposite signs...
of
ensures that aligned peaks (or aligned troughs) with imaginary components will contribute positively to the integral.In econometrics
Econometrics
Econometrics has been defined as "the application of mathematics and statistical methods to economic data" and described as the branch of economics "that aims to give empirical content to economic relations." More precisely, it is "the quantitative analysis of actual economic phenomena based on...
, lagged cross-correlation is sometimes referred to as cross-autocorrelation
Properties
- The cross-correlation of functions f(t) and g(t) is equivalent to the convolutionConvolutionIn mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
of f *(−t) and g(t). I.e.:
- If either f or g is Hermitian, then:
- Analogous to the convolution theoremConvolution theoremIn mathematics, the convolution theorem states that under suitableconditions the Fourier transform of a convolution is the pointwise product of Fourier transforms. In other words, convolution in one domain equals point-wise multiplication in the other domain...
, the cross-correlation satisfies:
where
denotes the Fourier transform, and an asterisk again indicates the complex conjugate. Coupled with fast Fourier transformFast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
algorithms, this property is often exploited for the efficient numerical computation of cross-correlations. (see circular cross-correlation)
- The cross-correlation is related to the spectral densitySpectral densityIn statistical signal processing and physics, the spectral density, power spectral density , or energy spectral density , is a positive real function of a frequency variable associated with a stationary stochastic process, or a deterministic function of time, which has dimensions of power per hertz...
. (see Wiener–Khinchin theoremWiener–Khinchin theoremThe Wiener–Khinchin theorem states that the power spectral density of a wide–sense stationary random process is the Fourier transform of the corresponding autocorrelation function.-History:Norbert Wiener first published the result in...
)
- The cross correlation of a convolution of f and h with a function g is the convolution of the correlation of f and g with the kernel h:
Normalized cross-correlation
For image-processing applications in which the brightness of the image and template can vary due to lighting and exposure conditions, the images can be first normalized. This is typically done at every step by subtracting the mean and dividing by the standard deviationStandard deviation
Standard deviation is a widely used measure of variability or diversity used in statistics and probability theory. It shows how much variation or "dispersion" there is from the average...
. That is, the cross-correlation of a template,
with a subimage is
-
.
where
is the number of pixels in and , is the average of f and is standard deviationStandard deviation
Standard deviation is a widely used measure of variability or diversity used in statistics and probability theory. It shows how much variation or "dispersion" there is from the average...
of f.
In functional analysis
Functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure and the linear operators acting upon these spaces and respecting these structures in a suitable sense...
terms, this can be thought of as the dot product of two normalized vectors. That is, if
and
then the above sum is equal to
where
is the inner product and is the L² normLp space
In mathematics, the Lp spaces are function spaces defined using a natural generalization of the p-norm for finite-dimensional vector spaces...
.
Thus, if f and t are real matrices, their normalized cross-correlation equals the cosine of the angle between the unit vectors F and T, being thus 1 if and only if F equals T multiplied by a positive scalar.
Normalized correlation is one of the methods used for template matching
Template matching
Template matching is a technique in digital image processing for finding small parts of an image which match a template image. It can be used in manufacturing as a part of quality control, a way to navigate a mobile robot, or as a way to detect edges in images....
, a process used for finding incidences of a pattern or object within an image. It is in fact just the 2-dimensional version of Pearson product-moment correlation coefficient
Pearson product-moment correlation coefficient
In statistics, the Pearson product-moment correlation coefficient is a measure of the correlation between two variables X and Y, giving a value between +1 and −1 inclusive...
.
Time series analysis
In time series analysis, as applied in statisticsStatistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
, the cross correlation between two time series describes the normalized cross covariance function.
Let
represent a pair of stochastic processStochastic process
In probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...
es that are jointly wide sense stationary. Then the cross covariance is given by
where
and are the means of and respectively.The cross correlation function
is the normalized cross-covariance function.
-
- where
and 
are the standard deviations of processes 
and 
respectively.
- where
Note that if
for all t, then the cross correlation function is simply the autocorrelation function.See also
- AutocorrelationAutocorrelationAutocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...
- AutocovarianceAutocovarianceIn statistics, given a real stochastic process X, the autocovariance is the covariance of the variable with itself, i.e. the variance of the variable against a time-shifted version of itself...
- Coherence (signal processing)Coherence (signal processing)-Background:The spectral coherence is a statistic that can be used to examine the relation between two signals or data sets. It is commonly used to estimate the power transfer between input and output of a linear system. If the signals are ergodic, and the system function linear, it can be used to...
- ConvolutionConvolutionIn mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
- CorrelationCorrelationIn statistics, dependence refers to any statistical relationship between two random variables or two sets of data. Correlation refers to any of a broad class of statistical relationships involving dependence....
- Digital image correlationDigital image correlationDigital Image Correlation and Tracking is an optical method that employs tracking & image registration techniques for accurate 2D and 3D measurements of changes in images. This is often used to measure deformation , displacement, and strain, but it is widely applied in many areas of science and...
- Phase correlationPhase correlationIn image processing, phase correlation is a method of image registration, and uses a fast frequency-domain approach to estimate the relative translative offset between two similar images.- Example :...
- Spectral densitySpectral densityIn statistical signal processing and physics, the spectral density, power spectral density , or energy spectral density , is a positive real function of a frequency variable associated with a stationary stochastic process, or a deterministic function of time, which has dimensions of power per hertz...
- Cross-spectrumCross-spectrumIn time series analysis, the cross-spectrum is used as part of a frequency domain analysis of the cross correlation or cross covariance between two time series.- Definition :...
- Wiener–Khinchin theoremWiener–Khinchin theoremThe Wiener–Khinchin theorem states that the power spectral density of a wide–sense stationary random process is the Fourier transform of the corresponding autocorrelation function.-History:Norbert Wiener first published the result in...
External links
- Cross Correlation from Mathworld
- http://scribblethink.org/Work/nvisionInterface/nip.html
- http://www.phys.ufl.edu/LIGO/stochastic/sign05.pdf
- http://www.staff.ncl.ac.uk/oliver.hinton/eee305/Chapter6.pdf