Cross-Correlation

The cross-correlation belongs to the area based matching approaches.

It is employed to detect homologous points in two or more images. In order to detect those homologous points in multiple images a rectangular, finite section is selected in one image. This section, respectively a section with the greatest resemblance, is then being searched in the second image. The center coordinates of these image sections are then stored and considered homologous points if the the matching correlation at this given point exceeds a specified threshold. This threshold may vary depending on images, patch sizes and search pattern.

Example

Select a patch in the left picture (required) and change some settings (optional). Press »Start«. Current defaults are: 10 steps per second, line by line with a patch size of 19.

Settings

Current Maximum: NaN
Current Maximum Position: undefined

Feel free to try all algorithms to see how they compare to each other. »Line«, »Meander« and »Circular Movement« usually return the most precise results, »Circular Movement« is the fastest one if the resulting image offset is small. »Meander Overlapping« should demonstrate that it is not suitable to skip larger areas as the results become less precise. Cross-correlation requires gray-scale images. Colored images need to be converted in advance or additional algorithms need to be implemented that calculate the grayscale value itself.

Approach

The aim of cross-correlation is finding homologous points in two or more given images. In one image – the source image – a point is selected. This point is supposed to be rediscovered in the second image, the so called target image. In order to determine homologous points, the cross-correlation value is calculated for each point in the target image. The maximum of all values is considered the homologous point of the source image in the target image.

To determine homologous points and to calculate cross-correlation values, the area around the respective points is taken into account. This so called patch is a rectangle of finite size, i.e. 19 pixels in diameter in both horizontal and vertical direction. The patch size may vary. Notice that greater patch sizes increase the chance to detect homologous points, but on the expense of accuracy. Smaller patch sizes in contrast may not find a unique solution, but results are more accurate. Hence, it is good practise to structure the patch sizes hierarchically, starting with bigger patches in size to find possible homologous points and then narrow it down arround preliminary solutions with patches that are decreasing in size until an adequate accuracy is achieved.

The movement behavior of the patch in the target image can be implemented differently. Most common is a meandering pattern of the patch movement to determine corresponding points.

The equation used to calculate the correlation values will be explained in the following. Gray scaled images are most suitable for the calculation of cross-correlation values. All gray values of pixels in the source and target image that are framed by the patch are taken into account for the calculation with the aim to adapt to contrast. The cross-correlation value therefor is always calculated over the entire patch at a given position which is also called the center of the patch.

Cross-correlation Equation

The cross-correlation values are determined utilizing the following equation.
Where c and r are the current, zero-indexed column and row coordinates and f and g are the average gray values of the source and target image, respectively. The center position of the patch is given by the x and y coordinates for which the correlation value ρ is finally calculated.
Additionally the average gray values of the entire source and target image are included in the calculation. Average Source Image gray value

The cross-correlation equation takes the average gray value of the source image into account.
In order to safe computing resources, this value should be calculated once before the cross-correlation commenced. Average Target Image gray value

The cross-correlation equation takes the average gray value of the target image into account.
In order to safe computing resources, this value should be calculated once before the cross-correlation commenced. • vivid
• easy to implement
• fast, solutions in hardware existing