# Fast Normalized Cross-Correlation for Stream-Data

I read some papers about fast normalized cross-correlation techniques. Most of them are used to identify a template in an original image.

I was not able to find information about input-data in a stream-based fashion: Assume, that there are two audio signals a and b both of the same length. Now, I want to find the position where both signals are best aligned.

It should possible to use normalized cross-correlation to calculate this.

Example (1):

a = {1,2,3,4}; b = {1,2,3,4}

Using normalized cross-correlation the result is given as:

{-1.8, 1.2, 1, 4, 1, 1.2, -1.8}

Now, let us assume that the signals will be extended, but we have a fixed queue-size for a and b.

Example (2):

a = {2,3,4,7}; b = {2,3,4,4}

Again, we use normalized cross-correlation to get our results:

{-0.967, -1.450, -0.161, 3.223, 2.256, -0.483, -2.417}

Normalized cross-correlation makes use of mean and variance of a and b and for me it seems, that there is no option to get a stream-based version of the normalized cross-correlation without recalculate the complete normalized cross-correlation. For sure, variance and mean can be calculated in a stream-based fashion. $$\frac{1}{n} \sum \frac{(f(x,y)- \overline{f})(t(x,y)- \overline{t}) }{\sigma_{f}\sigma_{t}}$$ Is it correct, that because of each calculation consists of mean and variance, it is not possible to have a stream-based normalized cross-correlation, because they change if a and b change?!

Would be happy to have a great discussion about this.

• There is a way to generate correlation estimates on-the-fly, but I'll have to dig for it. Too much real work to do for now, I'll try getting back to this in a few hours. I've seen such techniques used in time delay estimation (which may give you some buzzwords to google for). – Peter K. Jan 21 '16 at 12:53