Cross-correlation

In signal processing, cross-correlation is a measure of similarity of two series as a function of the displacement of one relative to the other. This is also known as a "sliding dot product" or "sliding inner-product". It is commonly used for searching a long signal for a shorter, known feature. It has applications in pattern recognition, single particle analysis, electron tomography, averaging, cryptanalysis, and neurophysiology. 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, and its size will be the signal energy.
In probability and statistics, the term "cross-correlations" refers to the correlations between the entries of two random vectors formula_1 and formula_2, while the "correlations" of a random vector formula_1 are the correlations between the entries of formula_1 itself, those forming the correlation matrix of formula_1. If each of formula_1 and formula_2 is a scalar random variable which is realized repeatedly in a time series, then the correlations of the various temporal instances of formula_1 are known as "autocorrelations" of formula_1, and the cross-correlations of formula_1 with formula_2 across time are temporal cross-correlations. In probability and statistics, the definition of correlation always includes a standardising factor in such a way that correlations have values between −1 and +1.
If formula_12 and formula_13 are two independent random variables with probability density functions formula_14 and formula_15, respectively, then the probability density of the difference formula_16 is formally given by the cross-correlation (in the signal-processing sense) formula_17; however, this terminology is not used in probability and statistics. In contrast, the convolution formula_18 (equivalent to the cross-correlation of formula_19 and formula_20) gives the probability density function of the sum formula_21.
Cross-correlation of deterministic signals.
For continuous functions formula_14 and formula_15, the cross-correlation is defined as:
which is equivalent to
where formula_25 denotes the complex conjugate of formula_19, and formula_27 is the displacement, also known as "lag" (a feature in formula_14 at formula_29 occurs in formula_15 at formula_31).
If formula_14 and formula_15 are both continuous periodic functions of period formula_34, the integration from formula_35 to formula_36 is replaced by integration over any interval formula_37 of length formula_34:
which is equivalent to
Similarly, for discrete functions, the cross-correlation is defined as:
which is equivalent to
For finite discrete functions formula_41, the (circular) cross-correlation is defined as: 
which is equivalent to
For finite discrete functions formula_43, formula_44, the kernel cross-correlation is defined as: 
where formula_45 is a vector of kernel functions formula_46 and formula_47 is an affine transform.
Specifically, formula_48 can be circular translation transform, rotation transform, or scale transform, etc. The kernel cross-correlation extends cross-correlation from linear space to kernel space. Cross-correlation is equivariant to translation; kernel cross-correlation is equivariant to any affine transforms, including translation, rotation, and scale, etc.
Explanation.
As an example, consider two real valued functions formula_14 and formula_15 differing only by an unknown shift along the x-axis. One can use the cross-correlation to find how much formula_15 must be shifted along the x-axis to make it identical to formula_14. The formula essentially slides the formula_15 function along the x-axis, calculating the integral of their product at each position. When the functions match, the value of formula_54 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 formula_14 and formula_15, taking the conjugate of formula_14 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.
Cross-correlation of random vectors.
Definition.
For random vectors formula_83 and formula_84, each containing random elements whose expected value and variance exist, the cross-correlation matrix of formula_1 and formula_2 is defined by
and has dimensions formula_87. Written component-wise:
The random vectors formula_1 and formula_2 need not have the same dimension, and either might be a scalar value.
Example.
For example, if formula_91 and formula_92 are random vectors, then
formula_93 is a formula_94 matrix whose formula_95-th entry is formula_96.
Definition for complex random vectors.
If formula_97 and formula_98 are complex random vectors, each containing random variables whose expected value and variance exist, the cross-correlation matrix of formula_99 and formula_100 is defined by
where formula_102 denotes Hermitian transposition.
Cross-correlation of stochastic processes.
In time series analysis and statistics, the cross-correlation of a pair of random process is the correlation between values of the processes at different times, as a function of the two times. Let formula_103 be a pair of random processes, and formula_29 be any point in time (formula_29 may be an integer for a discrete-time process or a real number for a continuous-time process). Then formula_106 is the value (or realization) produced by a given run of the process at time formula_29.
Cross-correlation function.
Suppose that the process has means formula_108 and formula_109 and variances formula_110 and formula_111 at time formula_29, for each formula_29. Then the definition of the cross-correlation between times formula_114 and formula_115 is
where formula_116 is the expected value operator. Note that this expression may be not defined.
Cross-covariance function.
Subtracting the mean before multiplication yields the cross-covariance between times formula_114 and formula_115:
Note that this expression is not well-defined for all-time series or processes, because the mean may not exist, or the variance may not exist.
Definition for wide-sense stationary stochastic process.
Let formula_103 represent a pair of stochastic processes that are jointly wide-sense stationary. Then the Cross-covariance function and the cross-correlation function are given as follows.
Cross-correlation function.
or equivalently
Cross-covariance function.
or equivalently
where formula_122 and formula_123 are the mean and standard deviation of the process formula_124, which are constant over time due to stationarity; and similarly for formula_125, respectively. formula_126 indicates the expected value. That the cross-covariance and cross-correlation are independent of formula_29 is precisely the additional information (beyond being individually wide-sense stationary) conveyed by the requirement that formula_103 are "jointly" wide-sense stationary.
The cross-correlation of a pair of jointly wide sense stationary stochastic processes can be estimated by averaging the product of samples measured from one process and samples measured from the other (and its time shifts). The samples included in the average can be an arbitrary subset of all the samples in the signal (e.g., samples within a finite time window or a sub-sampling of one of the signals). For a large number of samples, the average converges to the true cross-correlation.
Normalization.
It is common practice in some disciplines (e.g. statistics and time series analysis) to normalize the cross-correlation function to get a time-dependent Pearson correlation coefficient. However, in other disciplines (e.g. engineering) the normalization is usually dropped and the terms "cross-correlation" and "cross-covariance" are used interchangeably.
The definition of the normalized cross-correlation of a stochastic process is
If the function formula_130 is well-defined, its value must lie in the range formula_131, with 1 indicating perfect correlation and −1 indicating perfect anti-correlation.
For jointly wide-sense stationary stochastic processes, the definition is
The normalization is important both because the interpretation of the autocorrelation as a correlation provides a scale-free measure of the strength of statistical dependence, and because the normalization has an effect on the statistical properties of the estimated autocorrelations.
Properties.
Symmetry property.
For jointly wide-sense stationary stochastic processes, the cross-correlation function has the following symmetry property:
Respectively for jointly WSS processes:
Time delay analysis.
Cross-correlations are useful for determining the time delay between two signals, e.g., for determining time delays for the propagation of acoustic signals across a microphone array. After calculating the cross-correlation between the two signals, the maximum (or minimum if the signals are negatively correlated) of the cross-correlation function indicates the point in time where the signals are best aligned; i.e., the time delay between the two signals is determined by the argument of the maximum, or arg max of the cross-correlation, as in
Terminology in image processing.
Zero-normalized cross-correlation (ZNCC).
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 deviation. That is, the cross-correlation of a template, formula_136 with a subimage formula_137 is
where formula_139 is the number of pixels in formula_136 and formula_137,
formula_142 is the average of formula_14 and formula_144 is standard deviation of formula_14.
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 formula_149 is the inner product and formula_150 is the "L"² norm. Cauchy–Schwarz then implies that ZNCC has a range of formula_151.
Thus, if formula_14 and formula_29 are real matrices, their normalized cross-correlation equals the cosine of the angle between the unit vectors formula_154 and formula_34, being thus formula_156 if and only if formula_154 equals formula_34 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 also the 2-dimensional version of Pearson product-moment correlation coefficient.
Normalized cross-correlation (NCC).
NCC is similar to ZNCC with the only difference of not subtracting the local mean value of intensities:
Nonlinear systems.
Caution must be applied when using cross correlation for nonlinear systems. In certain circumstances, which depend on the properties of the input, cross correlation between the input and output of a system with nonlinear dynamics can be completely blind to certain nonlinear effects. This problem arises because some quadratic moments can equal zero and this can incorrectly suggest that there is little "correlation" (in the sense of statistical dependence) between two signals, when in fact the two signals are strongly related by nonlinear dynamics.