Image Recognizer 

Consider an Image represented by a matrix of digits, each digit represents the brightness of a pixel, as shown below. In early image processing, one could detect a particular feature in the image by finding the location where the feature (template) best matches the image.

Image:  0 1 0 1 1 0 0         Template:  0 0 1 1 1 1
        0 0 0 0 1 1 1                    0 2 0 0 2 0
        0 1 2 0 1 2 0                    3 3 3 3 0 0
        0 3 3 2 3 3 0
        0 1 1 1 0 0 1

To do this, you have to calculate, for each point y in the image where the template can fit entirely within the image, the cross-correlation


Sx i(x) t(x-y)

where i and t are the image and template light function respectively and x runs over all points in the image. The point with maximum cross-correlation is accepted as the location of the feature in the image.

Input and Output 

Develop a program that takes pairs of images - real images (I) and templates (T). For each pair, use the algorithm above and deliver the point of location (which is the pixel (x,y) in i where t has maximum cross-correlation) Give one answer per line. The Image starts al location (0,0) which is the upper-left corner. In the example below, the feature is detected at point of location (1,1). Which is The only output line. I means image and T template.

Notes: The image and templates sizes are variable and never will be greater than 50 by 50 points. The x-axis is horizontal and the y-axis is vertical. A character F in the input file indicates the end of pairs of images. If a template fits equally in more than one place, the correct answer will be the closest to the upper side, then the closest to the left side. You can take the exact format from the example below.

Sample Input 

I
0 1 0 1 1 0 0
0 0 0 0 1 1 1
0 1 2 0 1 2 0
0 3 3 2 3 3 0
0 1 1 0 0 0 1
T
0 0 1 1 1 1
0 2 0 0 2 0
3 3 3 3 0 0
F

Sample Output 

(1,1)



Miguel A. Revilla
1999-01-11