z-xcorr

Little Z has taken a really nice picture with his new camera. The picture has resolution up to 1024 by 1024 pixels, and is black and white - each pixel can have value between 0 and 255.

He is interested only in a part of the picture he has taken, so he decided to crop the picture - take square a sub-part of the picture with dimensions k by k.

Since his camera is really food, the picture didn't have any noise. In order to make the picture like it was taken with some older type of camera, Little Z has added some random noise. Each pixel in the sub-image is randomly modified - a value from -15 to 15 (with Gaussian distribution) is added to the pixel value. However, the pixel values are still kept in the range [0 255].

You are given the original image, and the cropped part, and you have to determine, what part of the original image corresponds to the cropped image.

From your Photography class, you know that the similarity between two images is measured by the square root of the mean square error. What that means is that for two images of the same size you:

1. Calculate the absolute difference of all the corresponding pixels.
2. Square the absolute differences.
3. Sum all the values.
4. Divide by the total number of pixels.
5. Take square root of the result.

Now, for the given original image, and cropped noisy part, you have to find the position of the cropped part so that the square root of the mean square error is minimized. You don't have to report the position, just the value of the square root of the mean square error.

P.S. You don't need to know what a Gaussian distribution is. That basically means that most of the errors will have small values - most of the pixels will be correct, and there will be more smaller errors than larger errors