# Find a 8 in a forest of 9

The goal here is to find one non-repeting pattern in an image. First, find the pattern, then second, compute correlation.

Let's first initialize the notebook:

In [1]:
```%matplotlib inline
%config InlineBackend.figure_format = 'svg'
import matplotlib.pyplot as plt
import numpy as np
phi = (np.sqrt(5)+1)/2
fig_width = 10
figsize = (fig_width, fig_width/phi)
```
In [2]:
```import imageio as io
im = im.sum(axis=-1)
```
In [3]:
```N_X, N_Y = im.shape
N_X, N_Y
```
Out[3]:
`(900, 1220)`

Original image

In [4]:
```fig, ax = plt.subplots(figsize=(fig_width, fig_width))
ax.matshow(im, cmap=plt.gray());
```

Zoom

In [5]:
```fig, ax = plt.subplots(figsize=(fig_width, fig_width))
ax.matshow(im[:40, :40]);
```
In [6]:
```fig, ax = plt.subplots(figsize=(fig_width, fig_width))
ax.matshow(im[-40:, -40:]);
```

Crop

In [7]:
```im = im[:, 24:1194]
fig, ax = plt.subplots(figsize=(fig_width, fig_width))
ax.matshow(im, cmap=plt.gray());
```

Average on one axis

In [8]:
```im_x = im.mean(axis=1)
im_x = np.roll(im_x, N_X//2) # avoid border effects
#im_x = np.correlate(im_x, [-1, 2, 1], 'same')*1. # contrast detection
im_x -= im_x.mean()
fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))
ax.plot(im_x[:100]);
```

Cross-correlation

In [9]:
```xcorr = np.correlate(im_x, im_x, 'same')*1.
xcorr /= xcorr.max()
fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))
ax.plot(xcorr);
```
In [10]:
```N_X//2, im_x.shape, xcorr.shape, im.shape
```
Out[10]:
`(450, (900,), (900,), (900, 1170))`
In [11]:
```fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))
ax.plot(xcorr[(N_X//2+1):(50+N_X//2)]);
```
In [12]:
```period_X = np.argmax(xcorr[(1+N_X//2):]) + 1
```
In [13]:
```print(f'{period_X=}')
```
```period_X=18
```

The other dimension:

In [14]:
```im_y = im.mean(axis=0)
im_y -= im_y.mean()
#im_y[-1] = im_y[0]
#im_y[-2] = im_y[1]
im_y = np.roll(im_y, N_Y//2) # avoid border effects
#im_y = np.correlate(im_y, [-1, 2, -1], 'same')*1. # contrast detection
```
In [15]:
```fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))
ax.plot(im_y);
```
In [16]:
```fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))
ax.plot(im_y[:40]);
```
In [17]:
```xcorr = np.correlate(im_y, im_y, 'same')*1.
```
In [18]:
```xcorr /= xcorr.max()
fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))
ax.plot(xcorr[(N_Y//2+3):]);
```
In [19]:
```xcorr /= xcorr.max()
fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))
ax.plot(xcorr[(N_Y//2+3):(40+N_Y//2)]);
```
In [20]:
```period_Y = np.argmax(xcorr[(3+N_Y//2):]) + 3
```
In [21]:
```print(f'{period_Y=}')
```
```period_Y=11
```

One sample (other random choices would most probably fit - do not go in the borders!)

In [22]:
```idx, idy = 0, 26
kernel = im[idx:idx+period_X, idy:idy+period_Y]
```
In [23]:
```fig, ax = plt.subplots(figsize=(fig_width, fig_width))
ax.matshow(kernel);
```
In [24]:
```from numpy.fft  import fft2, ifft2
xcorr = np.real(ifft2(fft2(im)*fft2(kernel, s=im.shape)))
```

Now you can spot where there is a difference (and then in the rest due to kerning...)

In [25]:
```fig, ax = plt.subplots(figsize=(fig_width, fig_width))
ax.matshow(xcorr, cmap=plt.magma());
```