---
title: Lecture: Edge Detection
categories: lecture
---

# Differentiation - The Canny edge detector

+ $\nabla I = [ I_x, I_y ]$ is the gradient vector.
+ It has length and direction in each pixel in the image.
+ Length $||\nabla I(x,y)||^2= \nabla I^T\nabla I$ 
+ Select points which satisfy two criteria
    + Local optimum *along the direction of the gradient*
    + Larger than a chosen threshold $\tau$.
    + Sometimes we use a soft and a hard threshold, where
      points between the two thresholds are selected if they
      are adjacent to other selected points.
+ We can calculate $\nabla I$ with either Sobel or the derivative
  of a Gaussian.

# Connected Components

1.  Start with a singleton set (single pixel).
2.  Use a mask, typically a $3\times3$ patch and centre it at
    each pixel already selected.
3.  Pixels in the mask *and* the original image are added to the
    set.
4.  Iterate until no pixels are added.

# Line Fitting

1.  Consider each connected component by itself;
    each one is a set of pixels with $(x,y)$ co-ordinates.
2.  Calculate the centre, that is the mean $(\bar x,\bar y)$.
2.  Calculate pixel positions relative tp the, i.e.
     $(\tilde x_i,\tilde y_i)$ where $\tilde x_i=x_i-\bar x$ and
     $\tilde y_i=y_i-\bar y$.
3.  Consider the matrix
    $$D=
      \begin{bmatrix}
         \sum_i \tilde x_i^2 & \sum_i \tilde x_i\tilde y_i \\
         \sum_i \tilde x_i\tilde y_i & \sum_i \tilde y_i^2 &
      \end{bmatrix}
    $$
4.  Suppose as an example that the $\tilde y_i$ are (approximately)
    zero and that there are many large $\tilde x_i$.
    + the matrix has one zero eigenvector and one eigenvector in the
      direction of $x$.
    + the points form an edge in the $x$ direction
5.  If the edge is rotated both $\tilde x_i$ and $\tilde y_i$ are
    non-zero, but the eigenvectors behave the same.
    + One zero eigenvector
    + One eigenvector in the direction of the edge.
6.  If the line is not straight, this is not perfect and the smaller
    eigenvalue is also non-zero.
7.  The line is described by $y\sin\theta-x\cos\theta=\rho$, where
    $\rho$ is the distance between the line and the origin.
    See drawing in [Hough Tutorial](https://docs.opencv.org/3.4/d9/db0/tutorial_hough_lines.html)
    + Note the two points on the line at
      $$\big(0,\frac{r}{\sin\theta}\big) \quad\text{and}\quad \big(\frac{r}{\cos\theta}\big)$$
    + Writing $y=\alpha x + \beta$,  we obviously have
      $$\beta=\frac{r}{\sin\theta}$$
    + We can solve for $\alpha$ to get
      $$\beta=-\frac{r}{\cos\theta}$$

# Hough