TUTO-Convolution_find-a-8-in-a-forest-of-9.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The goal here is to find one non-repeting pattern in an image. First, find the pattern, then second, compute correlation.\n",
    "\n",
    "It is based on the post https://laurentperrinet.github.io/sciblog/posts/2021-12-01-find-a-8-in-a-forest-of-9.html\n",
    "\n",
    "Let's first initialize the notebook:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'retina'\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "phi = (np.sqrt(5)+1)/2\n",
    "fig_width = 10\n",
    "figsize = (fig_width, fig_width/phi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import imageio as io\n",
    "im = io.v2.imread('files/2021-12-01-99999999999998.jpg')\n",
    "im = im.sum(axis=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N_X, N_Y = im.shape\n",
    "N_X, N_Y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Original image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width))\n",
    "ax.matshow(im, cmap=plt.gray());"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zoom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width))\n",
    "ax.matshow(im[:40, :40]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width))\n",
    "ax.matshow(im[-40:, -40:]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Crop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "im = im[:, 24:1194]\n",
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width))\n",
    "ax.matshow(im, cmap=plt.gray());"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Average on one axis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "im_x = im.mean(axis=1)\n",
    "im_x = np.roll(im_x, N_X//2) # avoid border effects\n",
    "#im_x = np.correlate(im_x, [-1, 2, 1], 'same')*1. # contrast detection\n",
    "im_x -= im_x.mean()\n",
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))\n",
    "ax.plot(im_x[:100]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cross-correlation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xcorr = np.correlate(im_x, im_x, 'same')*1.\n",
    "xcorr /= xcorr.max()\n",
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))\n",
    "ax.plot(xcorr);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N_X//2, im_x.shape, xcorr.shape, im.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))\n",
    "ax.plot(xcorr[(N_X//2+1):(50+N_X//2)]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "period_X = np.argmax(xcorr[(1+N_X//2):]) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f'{period_X=}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The other dimension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "im_y = im.mean(axis=0)\n",
    "im_y -= im_y.mean()\n",
    "#im_y[-1] = im_y[0]\n",
    "#im_y[-2] = im_y[1]\n",
    "im_y = np.roll(im_y, N_Y//2) # avoid border effects\n",
    "#im_y = np.correlate(im_y, [-1, 2, -1], 'same')*1. # contrast detection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))\n",
    "ax.plot(im_y);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))\n",
    "ax.plot(im_y[:40]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xcorr = np.correlate(im_y, im_y, 'same')*1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xcorr /= xcorr.max()\n",
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))\n",
    "ax.plot(xcorr[(N_Y//2+3):]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xcorr /= xcorr.max()\n",
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width/phi**2))\n",
    "ax.plot(xcorr[(N_Y//2+3):(40+N_Y//2)]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "period_Y = np.argmax(xcorr[(3+N_Y//2):]) + 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f'{period_Y=}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One sample (other random choices would *most probably* fit - do not go in the borders!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx, idy = 0, 26\n",
    "kernel = im[idx:idx+period_X, idy:idy+period_Y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width))\n",
    "ax.matshow(kernel);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "compute cross correlation using \n",
    "https://laurentperrinet.github.io//sciblog/posts/2017-09-20-the-fastest-2d-convolution-in-the-world.html\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy.fft  import fft2, ifft2\n",
    "xcorr = np.real(ifft2(fft2(im)*fft2(kernel, s=im.shape)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you can spot where there is a difference (and then in the rest due to kerning...)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "fig, ax = plt.subplots(figsize=(fig_width, fig_width))\n",
    "ax.matshow(xcorr, cmap=plt.magma());"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## some book keeping for the notebook"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext watermark\n",
    "%watermark -i -h -m -v -p numpy,matplotlib,imageio  -r -g -b"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}