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)\).
3. 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\).
4. 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} \]
5. 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
6. 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.
7. If the line is not straight, this is not perfect and the smaller eigenvalue is also non-zero.
8. 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
   • 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