A Counterexample in Cross-Correlation Template Matching
This addresses a theoretical gap in signal and image processing for researchers, but it is incremental as it builds on known techniques in a specific setting.
The paper tackles the problem of aligning and segmenting noisy sampled signals by showing that cross-correlation template matching can fail for one-dimensional piecewise constant functions, and it proves that using difference sequences, thresholding, and dynamic programming can correctly handle this under certain noise conditions.
Sampling and quantization are standard practices in signal and image processing, but a theoretical understanding of their impact is incomplete. We consider discrete image registration when the underlying function is a one-dimensional spatially-limited piecewise constant function. For ideal noiseless sampling the number of samples from each region of the support of the function generally depends on the placement of the sampling grid. Therefore, if the samples of the function are noisy, then image registration requires alignment and segmentation of the data sequences. One popular strategy for aligning images is selecting the maximum from cross-correlation template matching. To motivate more robust and accurate approaches which also address segmentation, we provide an example of a one-dimensional spatially-limited piecewise constant function for which the cross-correlation technique can perform poorly on noisy samples. While earlier approaches to improve the method involve normalization, our example suggests a novel strategy in our setting. Difference sequences, thresholding, and dynamic programming are well-known techniques in image processing. We prove that they are tools to correctly align and segment noisy data sequences under some conditions on the noise. We also address some of the potential difficulties that could arise in a more general case.