Idea: Replace each pixel intensity with some function of the intensities in the pixel's neighbourhood.
The general form of a linear filter is $$p'(i) = \sum_j w(j) \; p(i+j)$$
where
Example: in a width-5 neighbourhood: $$ f'(i) = \sum_{j=-2}^2 w(j) \; f(i+j)$$
[ DEMO of 1D filtering ]
In 2D, typical neighbourhoods are 3x3 or 5x5 around the pixel: $$p'(x,y) = \sum_{i=-1}^{+1} \; \sum_{j=-1}^{+1} w(i,j) \; p(x+i,y+j)$$
Example: To average in 3x3 neighbourhood, set all weights equal: $$w(x,y) = \frac19$$
Then the sum is $$p'(x,y) = \frac19 \; ( \begin{array}[t]{lclclll} p(x-1,y-1) &+& p(x ,y-1) &+& p(x+1,y-1) &+ \\ p(x-1,y ) &+& p(x ,y ) &+& p(x+1,y ) &+ \\ p(x-1,y+1) &+& p(x ,y+1) &+& p(x+1,y+1) &&) \end{array}$$
To correlate means to perform the above computation at each position in $p$.
This is denoted with a star: $$(w \; ☆ \; p)(x,y) = \sum_i \sum_j w(i,j) \; p(x+i,y+j)$$
The summations over $i$ and $j$ are taken over all $i$ and $j$: $[ -\infty, +\infty ]$, so:
For the 3x3 averaging example, above, $w(i,j)$ is defined over all $i$ and $j$ as: $$w(i,j) = \left\{ \begin{array}{cl} \frac19 & \textrm{if } |i| \leq 1 \textrm{ and } |j| \leq 1 \\ 0 & \textrm{otherwise} \\ \end{array} \right.$$
Correlation is not often used in image processing because it does not have nice properties, as follows:
Is correlation commutative? i.e. is $u \; ☆ \; p = p \; ☆ \; u$ ?
No. Here's a proof: $$\begin{array}{rl} (u \; ☆ \; p)(x,y) = & \sum_i \sum_j u(i,j) \; p(x+i,y+j) \\ & \textrm{now substitute } i-x \textrm{ for } i \textrm{ and } j-y \textrm{ for } j \textrm{ ... this has no effect in an infinite sum} \\ = & \sum_i \sum_j u( (i-x), (j-y) ) \; p( x+(i-x), y+(j-y) ) \\ = & \sum_i \sum_j p(i,j) \; u(i-x,j-y) \\ \neq & (p \; ☆ \; u)(x,y) \\ \end{array}$$
Is correlation associative? i.e. is $(u \; ☆ \; v) \; ☆ \; p = u \; ☆ \; (v \; ☆ \; p)$ ?
No (without proof here).
Convolution is like correlation, but does have nice properties, so is more often used.
The convolution operation is denoted with a different star, $∗$, and is similar to correlation, but the filter is "rotated" by 180 degrees: $$(w \; ∗ \; p)(x,y) = \sum_i \sum_j w(i,j) \; p(x-i,y-j)$$
Convolution is commutative, distributive, associative, and has an identity (to be proven next lecture).
This has nice implications in the frequency domain.