04_Edges.ipynb

{
  "cells": [
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {
        "id": "QuUAgQFQlsJU"
      },
      "source": [
        "# Tutorial 04 - Edges\n",
        "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/Digital-Media/vco/blob/main/04_Edges.ipynb)\n",
        "## Dr. David C. Schedl\n",
        "\n",
        "Note: this tutorial is geared towards students **experienced in programming** and aims to introduce you to **Computer Vision** techniques.\n",
        "\n",
        "\n",
        "Useful links:\n",
        "* OpenCV Tutorials: https://docs.opencv.org/master/d9/df8/tutorial_root.html\n",
        "* Image Processing in Pyhton: https://github.com/xn2333/OpenCV/blob/master/Seminar_Image_Processing_in_Python.ipynb\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GVOsLEGclsJZ"
      },
      "source": [
        "# Table of Contents  \n",
        "\n",
        "\n",
        "- Canny Edge Detection\n",
        "- Hough Transformation\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "weMMc2WZlsJc"
      },
      "source": [
        "# Initilization"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zkUzZ6lWK_S5"
      },
      "source": [
        "As always let's import useful libraries, first."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Gpvh7PPVlsJg"
      },
      "outputs": [],
      "source": [
        "import os\n",
        "import cv2 # openCV\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DnGyZdM2LH71"
      },
      "source": [
        "We will work with images today. So let's download some with `curl` (the same sources as in `02_OpenCV.ipynb`)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XTgznuO-LMMH",
        "outputId": "e2aedbeb-9f71-4601-b0f5-0177e9bd5ed7",
        "tags": []
      },
      "outputs": [],
      "source": [
        "!curl -o \"cat.jpg\" \"https://upload.wikimedia.org/wikipedia/commons/thumb/3/3a/Cat03.jpg/481px-Cat03.jpg\" --silent\n",
        "!curl -o \"gogh.jpg\" \"https://upload.wikimedia.org/wikipedia/commons/thumb/3/32/Vincent_van_Gogh_-_National_Gallery_of_Art.JPG/367px-Vincent_van_Gogh_-_National_Gallery_of_Art.JPG\"\n",
        "!curl -o \"einstein.jpg\" \"https://www.cns.nyu.edu/~lcv/ssim/index_files/image003.jpg\"\n",
        "# !curl -o \"woman.jpg\" \"https://live.staticflickr.com/8859/18045025168_3a1ffa6521_w_d.jpg\"\n",
        "!curl -o \"woman.jpg\" \"https://live.staticflickr.com/8859/18045025168_3a1ffa6521_c_d.jpg\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FCkGf5jg0KRg"
      },
      "source": [
        "Let's define utility functions to display images, in Jupyter Notebooks. OpenCV's `imshow` does not work and matplotlib's `imshow` needs special treatment due to color channel handling (RGB vs. BGR)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "z8ANEHCv0a-9",
        "outputId": "1a468910-3366-4411-878f-94ac6e938dad"
      },
      "outputs": [],
      "source": [
        "if 'google.colab' in str(get_ipython()):\n",
        "  print('Running on CoLab')\n",
        "  from google.colab.patches import cv2_imshow\n",
        "else:\n",
        "  print('Not running on CoLab')\n",
        "  def cv2_imshow(img):\n",
        "      \"\"\"A replacement for cv2.imshow() for use in Jupyter notebooks.\n",
        "\n",
        "        Args:\n",
        "          img : np.ndarray. shape (N, M) or (N, M, 1) is an NxM grayscale image. shape\n",
        "            (N, M, 3) is an NxM BGR color image. shape (N, M, 4) is an NxM BGRA color\n",
        "            image.\n",
        "      \"\"\"\n",
        "      cv2.imshow('image', img)\n",
        "      cv2.waitKey(0)\n",
        "      cv2.destroyAllWindows()\n",
        "\n",
        "def imshow(image, *args, **kwargs):\n",
        "    \"\"\"A replacement for cv2.imshow() for use in Jupyter notebooks using matplotlib.\n",
        "\n",
        "        Args:\n",
        "          image : np.ndarray. shape (N, M) or (N, M, 1) is an NxM grayscale image. shape\n",
        "            (N, M, 3) is an NxM BGR color image. \n",
        "    \"\"\"\n",
        "    if len(image.shape) == 3:\n",
        "      # Height, width, channels\n",
        "      # Assume BGR, do a conversion  \n",
        "      image = cv2.cvtColor(image, cv2.COLOR_BGR2RGB)\n",
        "\n",
        "    # Draw the image\n",
        "    plt.imshow(image, *args, **kwargs)\n",
        "    # We'll also disable drawing the axes and tick marks in the plot, since it's actually an image\n",
        "    plt.axis('off')\n",
        "    # Make sure it outputs\n",
        "    # plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b1E5rZhL21bG"
      },
      "source": [
        "# Practice with linear filters\n",
        "\n",
        "Image filters in OpenCV are applied with `cv2.filter2D(img,-1,kernel)`, where the image and the kernel are numpy arrays.\n",
        "You can define a custom kernel by defining a numpy array:  \n",
        "```\n",
        "np.array([[0,0,0],\n",
        "          [0,1,0],\n",
        "          [0,0,0]])\n",
        "```\n"
      ]
    },
    {
      "attachments": {},
      "cell_type": "markdown",
      "metadata": {
        "id": "y4lAjAM9kmg5"
      },
      "source": [
        "## ⌨️ Try it yourself: What results do you expect?\n",
        "\n",
        "What results do you expect if you apply the following kernels:\n",
        "\n",
        "1. \n",
        "    \\begin{pmatrix}\n",
        "    0 & 0 & 0\\\\\n",
        "    0 & 1 & 0\\\\\n",
        "    0 & 0 & 0 \n",
        "    \\end{pmatrix}\n",
        "\n",
        "2. \n",
        "    \\begin{pmatrix}\n",
        "    0 & 0 & 0\\\\\n",
        "    0 & 0 & 1\\\\\n",
        "    0 & 0 & 0 \n",
        "    \\end{pmatrix}\n",
        "\n",
        "3. \n",
        "    \\begin{pmatrix}\n",
        "    1 & 0 & -1\\\\\n",
        "    2 & 0 & -2\\\\\n",
        "    1 & 0 & -1 \n",
        "    \\end{pmatrix}\n",
        "\n",
        "4. Furthermore, what do you expect if you filter an image with:\n",
        "  \\begin{pmatrix}\n",
        "      0 & 0 & 0\\\\\n",
        "      0 & 2 & 0\\\\\n",
        "      0 & 0 & 0 \n",
        "  \\end{pmatrix}\n",
        "  and subtract another filtered image from the result. The second image is filtered with:    \n",
        "  \\begin{pmatrix}\n",
        "      \\frac{1}{9}  & \\frac{1}{9}  & \\frac{1}{9} \\\\\n",
        "      \\frac{1}{9}  & \\frac{1}{9}  & \\frac{1}{9} \\\\\n",
        "      \\frac{1}{9}  & \\frac{1}{9}  & \\frac{1}{9} \n",
        "  \\end{pmatrix} "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 429
        },
        "id": "0f7tq2_D4Vy9",
        "outputId": "878e5d9d-09ab-486a-abfc-c0bfad9600c5"
      },
      "outputs": [],
      "source": [
        "img = cv2.imread('einstein.jpg')[:,:,1].astype(np.float32)\n",
        "\n",
        "# define your costum kernel below\n",
        "kernel = np.array([[0,0,0],\n",
        "                   [0,1,0],\n",
        "                   [0,0,0]])\n",
        "dst = cv2.filter2D(img,-1,kernel)\n",
        "\n",
        "plt.figure(figsize=(15,10)) # this command makes the figure larger so we see the filter results clearer\n",
        "plt.subplot(121),imshow(img, cmap='gray'),plt.title('Original')\n",
        "plt.subplot(122),imshow((dst), cmap='gray'),plt.title(r'Filtered ({}$\\times${})'.format(*kernel.shape[:2]))\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ymS5Jla0zfYZ"
      },
      "source": [
        "# Canny Edge Detection\n",
        "\n",
        "Probably the most widely used edge detector in computer vision.\n",
        "Canny showed that first derivative of Gaussian closely approximates the operator that optimizes the product of signal-to-noise ratio and localization.\n",
        "\n",
        "Scientific Paper: [J. Canny, A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714, 1986.](https://ieeexplore.ieee.org/document/4767851?isnumber=4767846&arnumber=4767851&count=16&index=4)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ut57uLoFpmIJ"
      },
      "source": [
        "## OpenCV's Canny implementation\n",
        "\n",
        "Let's first look at the implementation available with OpenCV. \n",
        "```\n",
        "cv2.Canny(dx, dy, threshold1, threshold2)\n",
        "```\n",
        "The `Canny` function takes the derivatives in x and y and two hysteresis thresholds as input.\n",
        "Let's also look at the magnitude and the orientation."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 962
        },
        "id": "oTynYNVCziVY",
        "outputId": "271414dd-7dbc-4c2e-d222-70e20f3170ce"
      },
      "outputs": [],
      "source": [
        "img = cv2.imread('woman.jpg',0)\n",
        "\n",
        "gsize = (15,15)\n",
        "#img = cv2.GaussianBlur(img, gsize, 3)\n",
        "\n",
        "ksize = 3\n",
        "#edges = cv2.Canny(img,100,200,apertureSize=ksize)\n",
        "\n",
        "sobelx = cv2.Sobel(img,cv2.CV_64F,1,0,ksize=ksize)\n",
        "sobely = cv2.Sobel(img,cv2.CV_64F,0,1,ksize=ksize)\n",
        "\n",
        "plt.figure(figsize=(20,10))\n",
        "plt.subplot(1,2,1),imshow(sobelx,cmap = 'gray'), plt.title('Sobel X')\n",
        "plt.subplot(1,2,2),imshow(sobely,cmap = 'gray'), plt.title('Sobel Y')\n",
        "plt.show()\n",
        "\n",
        "mag = np.sqrt( sobelx**2 + sobely**2 )\n",
        "theta = np.arctan2(sobelx, sobely)\n",
        "\n",
        "plt.figure(figsize=(20,10)) # this command makes the figure larger so we see the filter results clearer\n",
        "plt.subplot(121),imshow(mag,cmap = 'gray'), plt.title('Magnitude')\n",
        "plt.subplot(122), imshow(theta,cmap='hsv'), plt.title('Orientation')\n",
        "plt.show()\n",
        "\n",
        "# OpenCVs implementation using the gradients in x and y\n",
        "edges = cv2.Canny(sobelx.astype(np.int16), sobely.astype(np.int16), 0.1*np.amax(mag),0.2*np.amax(mag))\n",
        "\n",
        "plt.figure(figsize=(20,10)) # this command makes the figure larger so we see the filter results clearer\n",
        "plt.subplot(121),imshow(img,cmap = 'gray'), plt.title('Original')\n",
        "plt.subplot(122), imshow(edges,cmap = 'gray'), plt.title('Canny Edge Image')\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uXR9txZYVhTV"
      },
      "source": [
        "# Hough Transformation\n",
        "\n",
        "Hough Transform is a voting technique that finds the parameters of lines in an image. \n",
        "The algorithm starts with a corner or edge detection for regular images. \n",
        "So it needs a binary/grey image, where 0s are non-edges and >0 are edges.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IRupxW-5rhi-"
      },
      "source": [
        "## OpenCV's Hough implementation\n",
        "\n",
        "Let's first look at the implementation available with OpenCV. \n",
        "We can reuse the edge image (`edges`) that we computed before.\n",
        "The function call is\n",
        "```\n",
        "cv2.HoughLines( edges, rho, theta, threshold )\n",
        "```\n",
        "and the parameters are the edge image, the distance resolution of the accumulator for $d$ in pixels and the angle $\\theta$ in radians, and the accumulator threshold."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 749
        },
        "id": "nrO21rwtPBmE",
        "outputId": "14d279ad-8e28-47d5-e544-df8d8a92fb5d"
      },
      "outputs": [],
      "source": [
        "image = cv2.rotate( edges, cv2.ROTATE_90_CLOCKWISE ) # reuse edges image\n",
        "\n",
        "# Copy edges to the images that will display the results in BGR\n",
        "cdst = cv2.cvtColor(image, cv2.COLOR_GRAY2BGR)\n",
        "\n",
        "lines = cv2.HoughLines(image, 1, np.pi / 180, 150)\n",
        "\n",
        "if lines is not None:\n",
        "    for i in range(0, len(lines)):\n",
        "        d = lines[i][0][0]\n",
        "        theta = lines[i][0][1]\n",
        "\n",
        "        print(\"Line {:2d}: d={:6.2f}, theta={:3.0f}\".format(i, d, np.rad2deg(theta)))\n",
        "\n",
        "        # Plot the lines\n",
        "        # Your TODO!\n",
        "        pt1 = None\n",
        "        pt2 = None\n",
        "        cv2.line( cdst, pt1, pt2, (255,0,0), 3, cv2.LINE_AA)\n",
        "\n",
        "# optionally, we can use the probabilistic hough transform:\n",
        "#linesP = cv2.HoughLinesP(dst, 1, np.pi / 180, 150, None, 40, 20)\n",
        "\n",
        "plt.figure(figsize=(20,10))\n",
        "plt.subplot(121), imshow(image, cmap='gray')\n",
        "plt.subplot(122),imshow(cdst) #\"Detected Lines (Todo)\", \n",
        "plt.show()\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OfrF0z0E8KrO"
      },
      "source": [
        "## Non-OpenCV implementation\n",
        "\n",
        "To understand the algorithm better let's also look at an implementation without the builtin function of OpenCV. This implementation can also be found [online](https://github.com/alyssaq/hough_transform). \n",
        "Note: the implementation is only for illustration and there might be more efficient/robust ways of implementing it."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 445
        },
        "id": "Dtbj2RTvRIBG",
        "outputId": "714b6452-8ee3-412d-dc28-40459418271a"
      },
      "outputs": [],
      "source": [
        "def hough_line(img):\n",
        "  # ds and Theta ranges\n",
        "  thetas = np.deg2rad(np.arange(-90.0, 90.0))\n",
        "  width, height = img.shape\n",
        "  diag_len = int(np.ceil(np.sqrt(width * width + height * height)))  # max_dist\n",
        "  ds = np.linspace(-diag_len, diag_len, diag_len*2)\n",
        "\n",
        "  # Cache some resuable values\n",
        "  cos_t = np.cos(thetas)\n",
        "  sin_t = np.sin(thetas)\n",
        "  num_thetas = len(thetas)\n",
        "\n",
        "  # Hough accumulator array of theta vs rho\n",
        "  accumulator = np.zeros((2 * diag_len, num_thetas), dtype=np.uint64)\n",
        "  y_idxs, x_idxs = np.nonzero(img)  # (row, col) indexes to edges\n",
        "\n",
        "  # Vote in the hough accumulator\n",
        "  for i in range(len(x_idxs)):\n",
        "    x = x_idxs[i]\n",
        "    y = y_idxs[i]\n",
        "\n",
        "    for t_idx in range(num_thetas):\n",
        "      # Calculate rho. diag_len is added for a positive index\n",
        "      d = round(x * cos_t[t_idx] + y * sin_t[t_idx]) + diag_len\n",
        "      accumulator[d, t_idx] += 1\n",
        "\n",
        "  return accumulator, thetas, ds\n",
        "\n",
        "# Create binary image and call hough_line\n",
        "image = np.zeros((50,50),dtype=np.int8)\n",
        "#image[:, :] = np.eye(50)[::-1, :]# + np.eye(50)#[::-1, :]\n",
        "image[10:40,10:40] = np.eye(30)\n",
        "#image[25,10:40] = 1.0\n",
        "accumulator, thetas, ds = hough_line(image)\n",
        "\n",
        "# Easiest peak finding based on max votes\n",
        "idx = np.argmax(accumulator)\n",
        "d = ds[int(idx / accumulator.shape[1])]\n",
        "theta = thetas[idx % accumulator.shape[1]]\n",
        "print(\"d={:.2f}, theta={:.0f}\".format(d, np.rad2deg(theta)))\n",
        "\n",
        "# Plot the lines\n",
        "# Your TODO!\n",
        "\n",
        "plt.figure(figsize=(15,10))\n",
        "plt.subplot(121), imshow(image, cmap='gray'), plt.title( 'original' )\n",
        "plt.subplot(122),imshow(accumulator, cmap='hot'), plt.title( 'Hough space' ) \n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d_Y6AA13-hNS"
      },
      "source": [
        "## ⌨️ Try it yourself: Plot the detected Hough lines.\n",
        "\n",
        "Use the OpenCV or Non-OpenCV implementation of the Hough detector and plot the detected lines. Note that both should have the same parameters. So plotting should work for both implementations.\n",
        "\n",
        "You can use the $m,b$ notation (which has problems with $\\theta=0$) from the slides or you come up with a better way. \n",
        "\n",
        "Use OpenCV's `cv2.line` to directly plot into the image, or you use `plt.plot` to plot on the figure (resolution independent).\n",
        "\n",
        "This image might help you:\n",
        "\n",
        "![image.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAARQAAADZCAYAAADhcc+nAAAgAElEQVR4Ae2d36tm11nHS/4Hb8yNN70qSBC9qBel0uZGRBR6YQ0oFhxGJo0N04qdNhxamITCSDqimTq2lRyKsfEQBzJKITiCja2TMsRTQ1PTnCZOJJ0JnqSJTUOSpls+O3neec7Tvd93r/dd+9e7vgv22e/+tfba37XX5zzPWmuv9a5KQQpIASmQSYF3ZYpH0UgBKSAFKgFFL4EUkALZFBBQskmpiKSAFBBQ9A5IASmQTQEBJZuUikgKSAEBRe+AFJAC2RQQULJJqYikgBQQULb8Hbh69Wp15syZ6vjx49Xp06erJ554YsufWI83pgICypjq93zvN15/ozp16lR18eLF6pVXXqmuXLlS3XH77dX169d7vrOiL1UBAaWnnKfQXr78WLW/v19RsLsErqHQHxwc/Mw1Tz31VPWNb3yjwuKIgfixPLjf888/vzhMXDs7O4ttfpw9e7YGzJGd2pACmRQQUDIJ6aO5dOlSdfLkyercuXO1u4GVsMwq+OlbP612d3fra3BPgADXE4AF+4jj/Pnz9X7WFgAM5wIK7sdv7k+4cOFCfY2da/s4T0EK9KGAgJJZ1RcPX67rK7AyLFCAlxViAxBuiQWr68Bdoe4D6BA4B2hgjRAA0QMPPFD/5g8AMnhxjGuJwxbAA6AUpEAfCggomVXFNTHrwqLG9Yj77BhrYLO3t+d3LX5T+M3isJ2AgoWAFYL1gjtkIPHnRaBwLwHFFNI6twICSmZFAQoF3Af20crSFijgWBBNwWDhj3EulgYBiwQY4SYdO3asvrdZR00uD9cus5b8ffRbCqQqIKCkKrbi/CagYGFgKbQFCrhZHPEcjgEGH9jn3Rw7BlyoXzHY4BbFStmm+Ox6raXApgoIKJsqGK43l8daY7AWfEVpOL3epL7kxIkTiz4i1MMYMHBluN5ab4ifc80KweKw31a5CzQIP3719bqZGJeLQJq41tJW79QfKZBRAQElo5hERYGnrwcWCS4Iv9vcGX9rq5jlGgq9QYFzuJ59gCXCiWPs4zhuFdYJQLJAszXHcZ04J9bH2HlaS4EcCggoOVR0cTS5PO7wyp++pcefjDtzeHi4aO3xx/jNdZzTFrh22fG267RfCqQoIKCkqNXh3E2B0uEWOkUKTFYBASVz1mAJyK3ILKqim40CAspsskoJlQLTV0BAmX4eKYVSYDYKCCghq2iepZm1bbHm23BZ3azbdg37535dfF5tS4EmBQSUoAqFn85hbQvHm8K2X9f0zNonBaICAkpQRBbKjeEPgjTalAIrFSgaKLTI0Eu1zR1ZqV5hJxhspVdhGZ/wuEUDxdyUNjcmQcciTpVew2QznRTp4Uz3g7l9JiGgnD9fV8D2/aq89uST1UsPPVS9/swzfd+qt/gFlN6kbYyY4Sj4aJRPJ2wYi6kDRkBxQOHjuo/d82C98E1NzuXLx45VV48dq1jnjHfIuPhymcpqGyphyHvrXjfem/g9VyONRtopoDigvPDyT6qP/s3/1st/Xn09a5Yc7u7WQPnRo49mjXfIyGShDKn2jXvxNTkfmWKl8PV52/deN64Y75eA4oBCNmChAJVPf/XF6rU33h52MUf2CCg5VCwvDj7oBORThojPFQElAAXT+s//6Yc1VL506cYYr160dX5fu/vu2kKhLmWuQRbKXHNuuHQLKA1AefnVt6pPfOUwq+vz/F131UB589q14XI3850ElMyCbmF0RQOFGnN8Ut+vAguF8K/feW3h+gCYTcNzd95ZA+UtN7L9pnEOfb36oQyt+PzuVzRQmrLLgMIxXB7qUzZ1fYAILTxARUEKbLMCAkrIXQ8U7/pgsawbqDcBKNSjKEiBbVZAQAm564HCIZqPsVKoU1nX9aGpGKDQsU1BCmyzAgJKyN0IFA6b60Przzrh+n1fqIEy5z4o6zy3rilPAQEl5HkTULBM6JeCpZLq+tD71ipk59zCE2TSphRoVKBooDR9bdwEFJTzrg89arsGvt3B3aHZeO5BrTxzz8H+0180UJr6VbQBhazY+/f/q60UXB+bvHxVFlkP2ab6E3pB4gaxzKE5uUmvVc+v42UpIKA0dGxrewXoin/6H16qofK1//hR22mL/UCizd3B/Xni5pur795yS708ftNN1dR70Qooi6zVjxYFBJQEoKDh9194swYK9SnPv/Rmi6xv78YqaWsuZv+zt922uB6X6Olbb11sT/GHgDLFXJlWmgSURKCQfeb6YK20uT7eOmmyPLBIfKsPdS3sm7LrI6BMq/BOMTUCyhpAASLm+gCXGICCfbtDk3FTAB5xsKUImabrxtwnoIyp/jzuLaCsARSy1rs+/LaANWIwYd1mcQAP6lD8IqCYilrPVYGigcI8xIxA5qcOXdbKEzOZilnqUrBWaLGxOhOrN2mDCfEYPLBSbLF98T5T2ZaFMpWcmG46igYKY3bytbEfpzMFKN71eeThb9cVsLTqUDfSVrdirwLw8HUrwId90Q2y86ewVj+UKeTCtNNQNFCasiYFKFxPSw/f+ezc+3htoXhINMVv+2gu9vUrWDcARUEKzFkBASXkXipQuNyPndJ12EgDCGsW6lL0NXLIDG3OTgEBJWTZOkDBvVln2EhAQt8TFm+thCRpUwrMRgEBJWTVOkAhCj92Su4R80MStSkFJquAgBKyZl2gEI13fdYdOyUkR5tSYFYKFA0UpiZgbuN1W3macnod16cpninuUyvPFHNlWmkqGiib9kNpykrv+lw5WH/YyKa4x96nfihj58D07y+gbNCxrS17Acmmw0a2xT3mfgFlTPXncW8BpQegkPWbDhs5xddHQJlirkwrTQJKT0DZZNjIab0iN1IjoNzQQr+aFRBQegIKcq87bGRzVo2/V0AZPw+mngIBpUegkPk2dkrKsJFTfWkElKnmzHTSJaD0DBS64tuI+V2GjZzOq/GzKRFQflYT7TmqQNFA2fRr46NStm/5sVNWDRvZHsv4R9QPZfw8mHoKigZKU+Zs0lO2KT7bZ67PsmEj7dxS13QwpKNhSmAqlAceeKA6c+ZMvX7x8OWUy3VuZgUElCBoX0DxI+Y3DRsZklHkJgNdMeBV18CgVqdOnap2d3crOimyZpv9CuMoIKAE3fsCCrfxro8fNjIkYXabFGAsBT5l6BqwJFKsCeL/8auvH4n+8uXHqp2dnSP72Ga/wjgKCChB9z6Bwq2869N17JSQxEltYlWcPHmytgxOnDhRWwnLRqvDraHQc40tWBeEixcv1q6LPSDWBhYL55Mvx48fPzJc597eXn0/O581Vgr7FcZRQEAJuvcNFD9s5NxdH6wGCrkBAYsDCPgxeoO8NTAuXLiw2H1wcFCxEJqAQt2IfbxJvEDLXBrgce7cuXoYT4byZGE7xW1aJEQ/sihQNFAwoakEtAKBon0DhXvQ0sO3Pixzcn1iKw8F+PTp00deRGBx9uzZI/v8BudT4IFRDE1A4R4WuIb8sWutzgTo2ALQgMocwss//PEckpmUxqKBQgHh5eZFtjAEULiXHztlLq5P7IdCYacg+8C+WK/hj2ONABV0xuUBCmZxrAMUb+1wnyY3yN9/Kr8f+/r3qg++57PVhb+9PJUkZUmHgDISUPywkXNxfboAhQLexUIw6xD4WJ1HKlA4P96Lbf8PIkspyRgJ+f7X9z5S/crP/2n1Sz/3J9XHP3J/xtjHj0pAGQkoZP0LL/+kHjEf12cOw0Y2AQVrwyphqUPB6vBuSnzFicMsEo4BAPqREFKBQt0KdSrWWoQrxLbVucR7j739wg9+WH30d79YgwSgABbTbuy05bq/gDIiUMhE7/pMfdjIJqDccfvtNUSou7BWnmUvJy4S0GGNdcJidSKpQOE+WEQWH+voAi1Ly5DHzMXBKsHVYXsbg4AyMlB4qeYybGQTUAAD7gsV23zK0CVQd8X51Kf4/9DE4/uyYHl4a4ZzgY+/hvtx3/39/c7375LGXOeQ1vs+97XaKgEmWChmUeW6x5TiEVAmAJS5DBvZBpQpvdBTSgsuzh/+1n0LF+f+v/yXKSWvl7QIKBMACjk7h2EjI1BocrcK1V7ezhlH+vVHvlO9/907NUx+45fvqfa/9eyMn6Z70osGCqYnFYhD90Npy56pDxsZ+6G0PUfJ+3FxPv+ZhxcuDq042+zixLwuGihRDLaH6ofSdO9tHDay6Tm3dd8P/uel6vd+/S8WLs7ffenftvVRW59LQAnSjAkUkrJtw0YGebd285GHv33ExfnO/nNb+6zLHkxACeqMDRSSYx8QbsOwkUHerdukFeqeTz60cHE+9UdfqbaxS33XjBNQglJTAIofNpJ+KgrTVOC5Zw+rD3/g3homv/oLn9q6bvTrqD4IUKA4/Qd8H4N1EjvENVMACs/px06Z87CRQ+TZGPf4x7+/UgER+pb89ns/Vz395LUxkjG5e/YOlNTxMoZUyL4nmUorT3x2c32mMmykWnmquhPfZ+588IiLw3uk8LYCvQIFqyR1vIwhM2bMr427POfUho2M/VC6PMM2nYMV4l0crBSFowr0ChT6eKSOl3E0ef1uTR0oPL13fcYeO6VkoDDMgLk4QEUuTnPZ7B0oqeNlNCezn71zAApPPhXXp0Sg4M7QckNdCQvujlyc9vI4OFC6jpfRnuR8R+YCFHpfUo/CMAdjjp1SGlCwQqhwBSRYJ/Q1UViuQO9ASR0vY3ly8x7lK1VGbPOfvE+llSc+6RSGjSwJKPRy9S4OTcQKqxXoHSip42WsTnK+M2jGBig2wA8xTxUopI2pTLFSsFbGGDayBKDQKY3vb8zFodOaH0Ih39u3nTH1DpR1xssYSuq5AQXXx8ZOGcP12Xag0F2eL4OBCV8K88WwQpoCgwAlLUnDnU3lGi1RfvrLKVsoKDPmsJHUOQEV1tsWcHFsnFc+8ONDP4V0BXoFyhzHy5g6UMjiOQ0bmf5KDnsFQwvYOK9YJgw9gCWosJ4CvQJlvSSNe9UcgIJC5vowhorCegow6JG5OIzzKhdnPR39VQKKV2PilbI+qXMZNtKneSq/sUAYjtFcHIZpZLhGhc0VEFCChnOxUEj2HIaNDPKOvhldHAaQlouTL1sElKDlnIBC0m3YSLk+ISMbNkuZyqLh0QfbVTRQ6F9AxfGcWnnimzHksJFzbeXBAvGz9W37VBbxHRlyu2igzK0fStuL4YeNBDB9hTn2Q4lTWWzjbH195fc68QooM+opuyyDzfXpc9jIuQHFuzi05lz55sEyCXUsgwJZgcJgSkxJ2bbQa7btmO2nK7z9blpzPFfYFgsFPYYYNnIuQMHFKWm2vlzlIUc8WYGSI0FDxjFFoNByg7VB1/rUoR+965N6bRfd5wCUOJVFCbP1dcm7oc4RUCbk8uCu/P7n/7vutMYHgO+/63t103DKy9Dn2ClTB0qps/WlvB99nyugTAQoVKa+95P/VY/QZplugLHtLms/bCRfJ+cMUwUKLk6cra/kqSxy5nlqXALKRICCqwNQfGAfVkpq6GvYyCkCxU9lQc/XEmfrS30/+jx/UKAcHBwkT67NIEhU5p44caLa2dmp9vf3s+kxpa+N24ASIdP14ftwfabWD4UR1GwQJFpxSp2tr+s7McR5kwYKHc9o6bl48WI9pw8d0ABLn5/Pj9VTtgkoQIE6lXUCbsAUho1cJ+2rruG9iLP1aZzXVaoNc7wXoJDhWBKYyFgYFtjvZ6KnlYUXgTXnAgwKggW2T548eWTfuXPnjgzZaOfmWo8NFOo9aK1hjbuzycyBUxg2Mle+WDxxKgtGo1eYjgLZgYJbAwTOnj1bUfgZApL+KQQGM8LisIArw8L5fm3HuY44fGAfcfcVxgYKVgVWCUuOSlXiGHPYyJz55Gfr+9D7zmgqi5ziZoorO1AAwN7e3iJ5WCXmojQBBTiYuYo1Q4E2qwZXh0GuWdtC/MCnrzA2UHI/FxafjZ2CCzXHwPvhZ+vTVBbTzcXsQGHAZypPL19+bAEGe/wmoAAKHyjQNjVoG1Di5GH++k1/bxtQ0GPMYSM3zQ9cHKwRm8pCs/Vtqmi/12cHChYJFgpQoXCyxg0irAOUvl0e6mmov7EwFlDoh5LDxbHniOscw0ZiaZKHuJ2+riveK9e2ZuvLpeRw8WQHik86pipAsDqPVKBQ0AGSD7u7u0dcKn9snd98G+S/DxoLKOukPfUac33WHTsFkFAnhkZ+6pHUdKw6n/fGz9anqSxWKTad49mBgpty9erV+gn5L+YLbCpQsHaosOU6Av8haTY2iyeHjD59xLfNQMEK+sRXDutKWlqSUgJ5ajBBIxZzTVPiWXUufUk0W98qlaZ7vBegAAFevuPHj9fWCc3CBCwOX6FKYea/ng+0Anlg8NISHwswief7a9f5XRJQ0MdcH8DSdewU8sBgQj6gGUAhr4B+ruCnsmBCcs3Wl0vZ4eLJDhRLOhDJ+bIdHh5mjc/SWRpQeG4bO6WL68M/Af4xABD+GaCX/WNgXw7XJ87Wx3c5Od8dy2ut+1egN6D0n/Q8dygRKN71WdZxDmsQaLBQ0Q5IDCg07WMxcmwT10ez9eV5j6cSi4BSUKWsf+n82ClNrg8AMZiYm+mBQlwGnHVdHz+VhWbr87kz398CSqFA4ZU114fWHwtWkQ5McHWAiIUIFM7FDeLcFNdHU1mYotu3Lh4o/Jf1hYbCUUrAMvn0V1+sW31wfai3oIkfDaiEja4MrWxoZT2f0SnV9WFcVz9bH+O+KmyPAsUDJWZlSUDh2c31qb/3OX26hgktOf98+ekoTet2F9cHa8ZPZaHZ+lrlnPUBASVkX2lA4fFt7JSP3fNg3ZEQq4Neu3TZ7xJWuT7exWEQJM3W10XVeZ4joIR8KxEofthI+4AQoKR8CtDm+vipLJiQXC5OeOG2bFNACRlaIlCQwA8byTgqwIShFFKCd33oPq+pLFLU245zBZSQj6UCBRnM9QEkAIV6la5uD9eb68P3VtSR8IUwLg7NwxxT2H4FigcKLRkltvIAClp2/Pw9FHobNtI+JPRuT1MrTywiTGWBawNMaM3Z/9az8RRtb7ECxQOlxJ6y9j4DFcDBdz30SQEwjG2LZWKLd3tiPxSLhzUw8lNZaEJyr045vwWUgju2GQgAiX2FbCDxa3N72oASZ+vTVBblACQ+qYBSOFDshTBrxYPEfpvbw9AU9IxlND4LcbY+TWVhypS5Lh4oVCDi9tjXrSVXyuK2NFkrO/c+vujd6ita/VQWH//I/ZVm6ysTIv6piwcK36AAFBuzpWSg2IvhrRVG37fJtIBJXDgmF8eU01pAEVAaS4FZK3wFHCFi2zQJM4i0ghQwBQQUAcXehcb1MqAAlhd+cONL5cYItLMoBYoHCi0XLKpDaX7v/WDRZpnYGncHS0ZBCpgCxQPFhLC16lBMibfXvm+JgcTWTLilIAW8AgKKV2PLR70Pj7p0M87WR32JgYT18Q/9lVp1lipY5kEBJeS7LJSqrmj1U1kwWx+Vr7Tm8MEffU8UpECTAgJKUKV0oMTZ+jSVRXhBtLlUAQElyFMqUOiU5itgNVtfeDG02UmB4oHCpGKlt/L4qSxouXnk4W93enl0khSIChQPlNJ7yvrZ+jSVRSwe2k5VQEAptGMb47zy/Y213NA8rD4lqcVH50cFBJQCgcKgRzaVxfvfvaNWm1gqtL22AgJKYUDxs/VpKou1y40ubFFAQCkEKH4qC9wcTWXRUiK0eyMFBJQCgKKpLDYqI7o4QQEBZYuBQiWrn62PcV71dXBC6dCpyQoUD5Rt/doYcAAQ3Bu+wwEsasVJLh+6IFGB4oES9dqGnrJycWKuansoBQSUoPScgYIFotn6QoZqc1AFBJQg91yBgosTZ+sLj6ZNKdC7AgJKkHiOQIlTWWi2vpCp2hxMAQElSN0VKLgXV48dqx6/6aZ6efa226q3XnklxNbvJmnwI6rRlZ7+JgpSYCwFigfK1atX66+NU6fRuHb33dV3b7mlevPatRokT996awVUhgqarW8opXWfFAWKBwqz4TEvDxOBE7paKE/cfHP10kMPLbT+0aOP1pbKEE2zDC9gc+XwTY5m61tkg36MrICAsiZQcHVef+aZRfYBEva99uSTi325fzAyv5+tjwGRNFtfu8rULdH/hiEapFO7TjmPCCgbAAUXxy8ABUulj8BQjB/+wL11RzWsE4ZqVGhXgLolxsWlGZ26pQ+970zFwNsK/SogoGwAlOfuvLOiLsWWvoDCINHm4lBINFvf8kIBfOkd7MfDBcZ9T5nKTAClBwFlA6D07fLEqSxwcZb9l8XE5xwfMPXpgu8Llz8+9m/giAVBXRCFHsvCAj1+GUWOY6zZtoCLiTuD5cFxCrMNXQmAOd8Hs1T8Pv+b4/7eHGOb4R66Bj5z2DSgB/nFM/FsKfff9N45rhdQ1gRKW6WszUC4aebwYnkXh0KyKtBkjCXjK2n5r0w8ywIFh0m7mpY+XStaqkgvYAB4V755UMOFtPL85tpxnlVE27PZc7HNtRy3wkd8FEqus8XOb9OBjoEffM9nF1YMz401mFL3silQ+GcBSIAb6bZPKPrMgzY91t0voKwJFGs2pu8JEMnZbMwLZC4OMKBwdQ1AwVsp/Jdb9UJSGAFW05LaSY5C4eMxq6Ep/RQcCn5ToPI5zkxowON8jmOVNLWqART0o3DaAiz4vSxQgA1inL9Kdwo9ELQFoNhv1hxPCdZB0T8TzxKtrZQ4hz63eKDs7++v1Q8FiFAhS70JC0ChT8omgcIIDHgxWSg0y1ycpnvxH5tCgbVi/+FyWU1N94v7uC8F3RYPt3gurg5QaQpcT2HygW32EyjsFHqGsARKWCemFefF+wK5VZYa8ZIetF8FYc4lTntO1lzntzmeEjg/Qq9pX0qcQ59bPFCi4F37ofjr/H8Uvz/lNwXEz9a37D/7qnj5j0YBo1DFeoGma3mJDWJxHa2EpuvX3bcsfUAiwiZaNIASS4BnRTsARaAQxv/qQMaOt6WXfAQI6NFmObVdy3602yQ0wQOwdQHhJvfNea2AEtS84/bb66Zfmn9Z6FdC5Wuf3erx772Ls2kFKi8m/72JM9XsDnL0uslzU3jNsuBmll4gQUEyWLNm2yAT3REKHlAhoF9s5QEw3G9ZAL6ABCuLdJGGlJAbKDwzH3x2+aeQks4+zxVQgrpfPnas/kaH73SaFupODnd3a9hsChkq/PivaVYBLk4O94Q4AMqq/8jh0QffJJ0UGAMF1hAQJKAN9T8cN1eHbask5Vyuo7ABmQgAtAQwZpn4a5seFIsQzYAJgboj0uJblpqu8/tyAAUQAjV7vlXp9vefwm8BJeQCQAEYLNfv+8Kijwl9TpoAwznr9I6lroNCwEuYeyoLCipxphSGIMNgm/wX9j1avXWG5YLlARSwLrwlw28gwDEsiabKYzvOtQaitgfj3Gj1oB9p6xrMuup6fjzPXB7uyzPx7P6Z4/lT3BZQQq4sq0PBIsH94RseLBUPGADU1brgBec/ETDBFN/0RQyPUBc+/nsrzEsBA8q8Un00tcUDZd2vjZERwAAXAwvWivn8R2V+ewtzGnPWXBzM9WXnN8Wxah/xYerz301hXgoIKPPKr8bUrvu1sY+M5mJzifwXyP4cTHJzcfDVU0xpH8+cf9Mig4vStmC5tR2z/RQ6+9207hJHbouwa54M8fzoM2Yo3kLJARQyEFfILBVfp4LFgD9sLg6VjKVOZUFBplC1LdQrtR2z/dRz2O+mdZc4VtWn9FUgcz8//6TiEuuB+nqWtniLB8qlS5fq8VAODg5qjZbVobSJaPu9+wNUootDa0RuF8furbUUmIICAso7QHnqqafq/NgEKMDCKmupT8G1ob6E9RxaXKbwQioN81ZAQMkIFF4FWnou3nW++sgvfryGiXWUmvdrotRLgW4KCCgZgRKnsqDSUC5Otxex7SzcRuts1nZO3E/fDSonqbuinmUugXSvU7+G9cu7xjN37brQlyYCSiagkKnm4tCaM6cXua+XK0e8fFuT8j0RFa70LsUytB601l0/R3r6jAMg8O6kBLoecA3PSJ8mljGhUjxQqDthfuPDw8M6H1PrULBAyEzrWyIXJ6U4rD431ULBKqFQWaDVgxa2VCvHrh9ynWqh2DdLZtXwLo7dB6l4oMQXJgUoNAPy8gITXlpeZoV0BSgYWCH8p6WHrx+2AU193wosFrrJ850S5wNw312f/fRF8YFCxjVTCFgP/APiOUk/6aWpm4CV64ddwPrgWVhjdXGN779E50UPT+Lg3BSLLrcmAkpQtCtQyFi+lwEmvBhN35KEqLXZogAFnoIAGNARoNh/XQoH9QMW0JvCBSAogBQooGKBuCiEwN4WzpkK7M01ASJYT6TVejVHlwd48oEi1+BCoxHb1o8GXQCSPSdrnpPrxgoCSlB+FVAwK8lYc3HIUMvgEJU2OyqAlv4/r7+sCSi+fgqwAHQL/La88WsPJTt3jDXwa7MgmoDi0411wzPZPy+O+We03wB3rCCgBOWXAYX/oJidZBwuTjStQ1Ta7KiAARpt+e2BsQoonOuBgoXiXSSSwH/sqVgogBMrgzTj3mCdWEvgKqDwLLx7pg9AiXAiDlkoHV+8IU5rAwr/CXkRyFBeWvN7h0hTCfcA1hQu3B1gbf+FU4GCBRBBD6imUodCXlJBDFhwZWgZBKKEVKDwnHzK4QNx+noYf2yI38VbKExBuqyVBzOTl9zMSTJrbmNUDPEibXIPqy+xOKjzMCikAgVLxBcyQAWg4j3sXkOvqefwASvD6oBSgUIdDP/kfAsW8LQ6GX+foX4XDxT7lqep6z0ZZi4OGTdmRg31QoxxH7Q1cLDmv7YVPNtv6fImP/uiy0Ph4nrAD5SwJvmHMJWAOwJAAIlZKICEkAoUrkEfAzDPTP3JmP/wBJSWjm1krrk4ZBJwUehHAbTFsqCQAQH/HxfXx2tPvvjj/I7uDPuID5BwzOoo+kl9Wnple+YAAAKeSURBVKykjX9MPCtp9K4z1pR/Flqx/LNzp/j8PJu5isTntUlLWZ6zBZQGoEB9c3H4PSbx82SzYpECwyggoDig8N/ArBLW/DdQkAJSoLsCRQCF+hEGUmpazp07V+3s7FRnzpypfvPX/rhe/uB3Plnt7u42nt8Uh9W/dJddZ0qB7VSgCKAAAZqD+1qIX0EKSIGqKgIobRYKVsjJkydrCwWr5OyffbGGTpMVsmyfLBQVJSnwtgJFAKUps2lNoH8CzcI0t1lte1vHtqY4tE8KSIGjChQHFL674fsba8Whl6JvVhRQjr4g2pICKQoUBRT6NNjHY22z9QkoKa+PzpUCRxUoBih0+sHFwTKhZ6H1xDwqR1XXocR92pYCUqCbAkUAha7O5uLQ3dm7OFEmWShREW1Lge4KFAEUumDzfQddmVcFAWWVQjouBdoVKAIoKWN1CijtL4uOSIFVChQBlFUi+OMCildDv6VAmgICStBLQAmCaFMKJCggoASxBJQgiDalQIICAkoQS0AJgmhTCiQoIKAEsQSUIIg2pUCCAgJKEEtACYJoUwokKCCgBLEElCCINqVAggICShBLQAmCaFMKJCggoASxBJQgiDalQIICAso7Ytn3PQYU207QUqdKgeIVEFDeeQWY7Ov69ev118YHBweVRmErvmxIgDUUEFDeEY35TBgOEguFNTMGKkgBKZCmgIDi9Dp16lQNlPPnz7u9+ikFpEBXBQQUp9Te3l4NlP39fbdXP6WAFOiqgIDilMLtOXHihNwdp4l+SoEUBQSUoBaTpytIASmwngICStBNzcVBEG1KgQQFBJQEsXSqFJACyxUQUJbro6NSQAokKCCgJIilU6WAFFiugICyXB8dlQJSIEEBASVBLJ0qBaTAcgX+H3NDp6VBdrp6AAAAAElFTkSuQmCC)\n",
        "\n",
        "[Image Credits: Alyssa Quek](https://alyssaq.github.io/2014/understanding-hough-transform/)\n",
        "\n",
        "Note that $\\rho$ is $d$ in our implementation."
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [
        "tXV5YxS7lsU2"
      ],
      "name": "04_Edges.ipynb",
      "provenance": [],
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "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.8.10"
    },
    "varInspector": {
      "cols": {
        "lenName": 16,
        "lenType": 16,
        "lenVar": 40
      },
      "kernels_config": {
        "python": {
          "delete_cmd_postfix": "",
          "delete_cmd_prefix": "del ",
          "library": "var_list.py",
          "varRefreshCmd": "print(var_dic_list())"
        },
        "r": {
          "delete_cmd_postfix": ") ",
          "delete_cmd_prefix": "rm(",
          "library": "var_list.r",
          "varRefreshCmd": "cat(var_dic_list()) "
        }
      },
      "types_to_exclude": [
        "module",
        "function",
        "builtin_function_or_method",
        "instance",
        "_Feature"
      ],
      "window_display": false
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}