Home Discussion Topics Dictionary Almanac

Signup Login

Cross-correlation

Overview

In signal processing

Signal processing

Signal processing is an area of electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time to perform useful operations on those signals...

, 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, also known as the scalar product, is an operation which takes two vectors over the real numbers R and returns a real-valued scalar quantity. It is the standard inner product of the orthonormal Euclidean space...

or inner-product. It is commonly used to search a long duration signal for a shorter, known feature. It also has applications in pattern recognition

Pattern recognition

Pattern recognition is "the act of taking in raw data and taking an action based on the category of the pattern". Most research in pattern recognition is about methods for supervised learning and unsupervised learning....

, 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 which 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

As found in mathematics, a complex conjugate is most simply defined as one of a pair of complex numbers, each having the same real parts but with imaginary parts that differ in sign; e.g. 3 + 4i and 3 - 4i are complex conjugates...

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.

Discussion

Ask a question about 'Cross-correlation'

Start a new discussion about 'Cross-correlation'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In signal processing

Signal processing

Signal processing is an area of electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time to perform useful operations on those signals...

, 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, also known as the scalar product, is an operation which takes two vectors over the real numbers R and returns a real-valued scalar quantity. It is the standard inner product of the orthonormal Euclidean space...

or inner-product. It is commonly used to search a long duration signal for a shorter, known feature. It also has applications in pattern recognition

Pattern recognition

Pattern recognition is "the act of taking in raw data and taking an action based on the category of the pattern". Most research in pattern recognition is about methods for supervised learning and unsupervised learning....

, 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 which 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

As found in mathematics, a complex conjugate is most simply defined as one of a pair of complex numbers, each having the same real parts but with imaginary parts that differ in sign; e.g. 3 + 4i and 3 - 4i are complex conjugates...

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. Whereas convolution involves reversing a signal, then shifting it and multiplying by another signal, correlation only involves shifting it and multiplying (no reversing).

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.

If and are two independent random variable

Random variable

In mathematics, random variables are used in the study of probability. They were developed to assist in the analysis of games of chance, stochastic events, and the results of scientific experiments by capturing only the mathematical properties necessary to answer probabilistic questions...

s with probability distribution

Probability distribution

In probability theory and statistics, a probability distribution identifies either the probability of each value of an unidentified random variable , or the probability of the value falling within a particular interval...

s f and g, respectively, then the probability distribution of the difference is given by the cross-correlation f g. In contrast, the convolution f g gives the probability distribution of the sum .

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 a branch of mathematics concerned with collecting and interpreting data. According to other definitions, it is a mathematical science pertaining to the collection, analysis, interpretation or explanation, and presentation of data. Statisticians improve the quality of data with the...

, the term cross-correlation is also sometimes used to refer to the covariance

Covariance

In probability theory and statistics, covariance is a measure of how much two variables change together. - Definition :...

cov(X, Y) between two random vectors X and Y, in order to distinguish that concept from the "covariance" of a random vector X, which is understood to be the matrix of covariances

Covariance matrix

In statistics and probability theory, the covariance matrix or dispersion matrix is a matrix of covariances between elements of a random vector...

between the scalar components of X.

Explanation

For example, consider two real valued functions and that differ only by a shift along the x-axis. One can calculate the cross-correlation to figure out 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 for each possible amount of sliding. When the functions match, the value of is maximized. The reason for this is that when lumps (positives areas) are aligned, they contribute to making the integral larger. Also, when the 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

Complex conjugate

As found in mathematics, a complex conjugate is most simply defined as one of a pair of complex numbers, each having the same real parts but with imaginary parts that differ in sign; e.g. 3 + 4i and 3 - 4i are complex conjugates...

of ensures that aligned lumps (or aligned troughs) with imaginary components will contribute positively to the integral.

In econometrics

Econometrics

Econometrics is concerned with the tasks of developing and applying quantitative or statistical methods to the study and elucidation of economic principles. Econometrics combines economic theory with statistics to analyze and test economic relationships...

, 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 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 f *(−t) and g(t). I.e.:

If either f or g is Hermitian
Hermitian function
In mathematical analysis, a Hermitian function is a complex function with the property that its complex conjugate is equal to the original function with the variable changed in sign:for all in the domain of ....

, then:

Analogous to the convolution theorem
Convolution theorem
In 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 transform

Fast Fourier transform

A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex-number arithmetic to group theory and number theory; this article gives an overview of...

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 density
Spectral density
In 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 Hz,...

. (see Wiener–Khinchin theorem
Wiener–Khinchin theorem
The 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.Continuous case:whereis the autocorrelation function...

)

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 deviation

Standard deviation

In probability theory and statistics, the standard deviation of a statistical population, a data set, or a probability distribution is the square root of its variance. Standard deviation is a widely used measure of the variability or dispersion, being algebraically more tractable though...

. That is, the cross-correlation of a template, with a subimage is.
where is the number of pixels in and .
In functional analysis

Functional analysis

Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of vector spaces and operators acting upon them. It has its historical roots in the study of functional spaces, in particular transformations of functions, such as the Fourier transform, as well...

terms, this can be thought of as the dot product of two normalized vectors

Unit vector

In mathematics, a unit vector in a normed vector space is a vector whose length is 1 . A unit vector is often denoted by a lowercase letter with a superscribed caret or “hat”, like this:

{\hat{\imath}}

.In Euclidean space, the dot product of two unit vectors is simply the...

. That is, if
and
then the above sum is equal to
where is the inner product and is the L² norm

Lp space

In mathematics, the L^p spaces are function spaces defined using natural generalizations of p-norms for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue , although according to they were first introduced by...

.

In Machine Vision

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.

External links

Cross Correlation from Mathworld
http://citebase.eprints.org/cgi-bin/citations?id=oai:arXiv.org:physics/0405041
http://scribblethink.org/Work/nvisionInterface/nip.html
http://www.phys.ufl.edu/LIGO/stochastic/sign05.pdf
http://archive.nlm.nih.gov/pubs/hauser/Tompaper/tompaper.php
http://www.staff.ncl.ac.uk/oliver.hinton/eee305/Chapter6.pdf

Cross-correlation

Explanation

Properties

Normalized cross-correlation

In Machine Vision

See also

External links