computer-vision/implementing-2d-convolution-from-scratch.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Implementing 2-D Convolution from Scratch",
      "provenance": [],
      "authorship_tag": "ABX9TyMyl/XBSUGHEnWKEUgRQ67x"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jh5Xt-W7nYxs"
      },
      "source": [
        "# Implementing 2-D Convolution from Scratch\n",
        "*By Carlos Santiago Bañón*\n",
        "\n",
        "**Year:** 2020\n",
        "\n",
        "**Technologies:** Python, NumPy\n",
        "\n",
        "**Discipline(s):** Computer Vision\n",
        "\n",
        "**Keywords:** `computer-vision`, `convolution`, `kernel`, `matrices`, `2d-convolution`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5JX9Yo9AnlgB"
      },
      "source": [
        "This notebook presents an implementation of the 2-D convolution operation developed from scratch using NumPy.\n",
        "\n",
        "For the purposes of this notebook, all variables are square matrices, and the size $s$ of the kernel matrix can also be an even number."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KpHC4KgWa5w6"
      },
      "source": [
        "## 1. Import Statements\n",
        "\n",
        "---\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8WjFZ9SkZhYE"
      },
      "source": [
        "import numpy as np"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YTE4Hl5HOgDD"
      },
      "source": [
        "## 2. 2-D Convolution Implementation\n",
        "\n",
        "---\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c6QuMd0qQx7I"
      },
      "source": [
        "First, the `conv2d()` function is presented. It takes as input an input matrix `input_mat` and a kernel `kernel_mat` and outputs `output_mat`."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KczvW7nCACv3"
      },
      "source": [
        "def conv2d(input_mat, kernel_mat):\n",
        "  \"\"\"\n",
        "  Perform the 2-D convolution operation.\n",
        "\n",
        "  :input_mat: the input matrix.\n",
        "  :kernel_mat: the kernel matrix used for convolution.\n",
        "  \"\"\"\n",
        "\n",
        "  # Ensure none of the inputs are empty.\n",
        "  if input_mat.size == 0 or kernel_mat.size == 0:\n",
        "    raise Exception(\"Error! Empty matrices found.\")\n",
        "    return [[]]\n",
        "\n",
        "  # Ensure the input is a square matrix.\n",
        "  if input_mat.shape[0] != input_mat.shape[1]:\n",
        "    raise Exception(\"Error! The input is not a square matrix.\")\n",
        "    return [[]]\n",
        "\n",
        "  # Ensure the kernel is a square matrix.\n",
        "  if kernel_mat.shape[0] != kernel_mat.shape[1]:\n",
        "    raise Exception(\"Error! The kernel is not a square matrix.\")\n",
        "    return [[]]\n",
        "\n",
        "  # Get the size of the input and kernel matrices.\n",
        "  input_size = input_mat.shape[0]\n",
        "  kernel_size = kernel_mat.shape[0]\n",
        "\n",
        "  # Ensure the kernel is not larger than the input matrix.\n",
        "  if input_size < kernel_size:\n",
        "    raise Exception(\"Error! The kernel is larger than the input.\")\n",
        "    return [[]]\n",
        "\n",
        "  # Flip the kernel.\n",
        "  kernel_mat = np.flip(kernel_mat)\n",
        "\n",
        "  # Set up the output matrix.\n",
        "  output_size = (input_size - kernel_size) + 1\n",
        "  output_mat = np.zeros(shape = (output_size, output_size), dtype=int)\n",
        "\n",
        "  row_offset = 0\n",
        "\n",
        "  for output_row in range(output_size):\n",
        "    col_offset = 0\n",
        "\n",
        "    for output_col in range(output_size):\n",
        "      kernel_row = 0\n",
        "\n",
        "      for row in range(row_offset, row_offset + kernel_size):\n",
        "        kernel_col = 0\n",
        "\n",
        "        for col in range(col_offset, col_offset + kernel_size):\n",
        "          \n",
        "          # Perform the convolution computation.\n",
        "          output_mat[output_row, output_col] += (kernel_mat[kernel_row, kernel_col] * input_mat[row, col])\n",
        "          kernel_col += 1\n",
        "        \n",
        "        kernel_row += 1\n",
        "\n",
        "      col_offset += 1\n",
        "    \n",
        "    row_offset += 1\n",
        "\n",
        "  return output_mat"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "za32MJDqR2_t"
      },
      "source": [
        "## 3. Test Cases\n",
        "\n",
        "---"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WfcP_KQER5Pf"
      },
      "source": [
        "After defining the `conv2d()` function, it can now be tested with some given test cases."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "saarTunESCY3"
      },
      "source": [
        "### 3.1. Test Case #1"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S4kA14uCBX5h"
      },
      "source": [
        "# Define the input matrix.\n",
        "input_mat = np.array([[1, 2, 1, 2],\n",
        "                      [2, 1, 2, 1],\n",
        "                      [1, 2, 1, 2],\n",
        "                      [2, 1, 2, 1]])\n",
        "\n",
        "# Define the matrix kernel.\n",
        "kernel_mat = np.array([[1, 0],\n",
        "                       [0, 1]])"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kI4S5OGcSSU9",
        "outputId": "e71bb9a5-ee25-42d7-8eb4-9a8f2c2e5c18",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "output_mat = conv2d(input_mat, kernel_mat)\n",
        "print(output_mat)"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[2 4 2]\n",
            " [4 2 4]\n",
            " [2 4 2]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GmbSScdtSZp8"
      },
      "source": [
        "### 3.2. Test Case #2"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NNsucF3mSa6T"
      },
      "source": [
        "# Define the input matrix.\n",
        "input_mat = np.array([[1, 0, 0, 0],\n",
        "                      [0, 1, 0, 0],\n",
        "                      [0, 0, 1, 0],\n",
        "                      [0, 0, 0, 1]])\n",
        "\n",
        "# Define the matrix kernel.\n",
        "kernel_mat = np.array([[1, 0],\n",
        "                       [0, 1]])"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_YevD90jScPu",
        "outputId": "f0303b69-e96c-4b77-a809-97700301d746",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "output_mat = conv2d(input_mat, kernel_mat)\n",
        "print(output_mat)"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[2 0 0]\n",
            " [0 2 0]\n",
            " [0 0 2]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Jq3qvDwcSmt0"
      },
      "source": [
        "### 3.3. Test Case #3"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "89MQZs70TWRC"
      },
      "source": [
        "Here, we can see that the function can work with negative numbers."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "K_uqL-yySo_j"
      },
      "source": [
        "# Define the input matrix.\n",
        "input_mat = np.array([[1, 0, 0, 0],\n",
        "                      [0, 1, 0, 0],\n",
        "                      [0, 0, 1, 0],\n",
        "                      [0, 0, 0, 1]])\n",
        "\n",
        "# Define the matrix kernel.\n",
        "kernel_mat = np.array([[1, -1],\n",
        "                       [-1, 0]])"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xnw0f5jWSp7n",
        "outputId": "5360daad-618c-4a7a-83e1-717664453845",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "output_mat = conv2d(input_mat, kernel_mat)\n",
        "print(output_mat)"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[ 1 -1  0]\n",
            " [-1  1 -1]\n",
            " [ 0 -1  1]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KghsW1ETSwKX"
      },
      "source": [
        "### 3.4. Test Case #4"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PAaZBXkGTRGO"
      },
      "source": [
        "Here, it is ensured that the function works if the input and the kernel matrices are the same."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "34wpl3YQSxoj"
      },
      "source": [
        "# Define the input matrix.\n",
        "input_mat = np.array([[1, 0, 0, 0],\n",
        "                      [0, 1, 0, 0],\n",
        "                      [0, 0, 1, 0],\n",
        "                      [0, 0, 0, 1]])\n",
        "\n",
        "# Define the matrix kernel.\n",
        "kernel_mat = np.array([[1, 0, 0, 0],\n",
        "                       [0, 1, 0, 0],\n",
        "                       [0, 0, 1, 0],\n",
        "                       [0, 0, 0, 1]])"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2xvgR5XnSzrB",
        "outputId": "5333f036-76c5-4a7e-a8d1-b7cbad2cd973",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "output_mat = conv2d(input_mat, kernel_mat)\n",
        "print(output_mat)"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[4]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bKFfzLVqS9IY"
      },
      "source": [
        "### 3.5. Test Case #5"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d03o5mi-TF_S"
      },
      "source": [
        "This test case presents the case where the kernel is larger than the input matrix. In this case, the functions prints an error."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vgb1ipBuS-ei"
      },
      "source": [
        "# Define the input matrix.\n",
        "input_mat = np.array([[1, -1],\n",
        "                      [-1, 0]])\n",
        "\n",
        "# Define the matrix kernel.\n",
        "kernel_mat = np.array([[1, 0, 0, 0],\n",
        "                       [0, 1, 0, 0],\n",
        "                       [0, 0, 1, 0],\n",
        "                       [0, 0, 0, 1]])"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sf25SqNTS_dN",
        "outputId": "6f9259d3-f53d-4668-d895-0c530434ea58",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 300
        }
      },
      "source": [
        "output_mat = conv2d(input_mat, kernel_mat)\n",
        "print(output_mat)"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "error",
          "ename": "Exception",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mException\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-12-b1e05922d6bd>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0moutput_mat\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mconv2d\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minput_mat\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkernel_mat\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      2\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0moutput_mat\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-2-7aaacee30886>\u001b[0m in \u001b[0;36mconv2d\u001b[0;34m(input_mat, kernel_mat)\u001b[0m\n\u001b[1;32m     28\u001b[0m   \u001b[0;31m# Ensure the kernel is not larger than the input matrix.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     29\u001b[0m   \u001b[0;32mif\u001b[0m \u001b[0minput_size\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mkernel_size\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 30\u001b[0;31m     \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Error! The kernel is larger than the input.\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     31\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     32\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mException\u001b[0m: Error! The kernel is larger than the input."
          ]
        }
      ]
    }
  ]
}