Edge and Lines

cv

---

1 what is Edge

An edge is a place of rapid change in the image intensity funciton.

2 Edge Operator Properties

• edge magnitude
• edge orientation
• high detection rate and good localization

3 Image Gradient

the gradient is:

$$\nabla f=[\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}]$$
diretion is:
$$\theta=tan^{-1}{(\frac{\partial f}{\partial x}/\frac{\partial f}{\partial y})}$$
magnitudeis:
$$\left \| \nabla f\right \|=\sqrt{{(\frac{\partial f}{\partial x})}^2+{(\frac{\partial f}{\partial y})}^2}$$

4 Theory of Edge Detection

Laplacian

$$\nabla^2 I= \frac{\partial^2 I}{\partial x^2}+\frac{\partial^2 I}{\partial y^2}$$

5 Discrete Edge Operators

5.1 Laplacian Operators

The key to understand how the Laplacian$\nabla I$ generate Laplacian mask, acturally, it is a convolution(nine element of two matrix do convolution = vector dot).

Two kinds of Laplacian kernel

$\begin{bmatrix} 0 & 1 & 0\\ 1 & -4 & 1\\ 0 & 1 & 0 \end{bmatrix}$ and $\begin{bmatrix} 1 & 4 & 1\\ 4 & -20 & 4\\ 1 & 4 & 1 \end{bmatrix}$

The sencond kernel is more accurate.

5.2 Sobel Opterators

Better approximations of the gradients exist. The Sobel operators below are commonly used.
$\begin{bmatrix} -1 & 0 & 1\\ -2 & 0 & 2\\ -1 & 0 & 1 \end{bmatrix}$ and $\begin{bmatrix} 1 & 2 & 1\\ 0 & 0 & 0\\ -1 & -2 & -1 \end{bmatrix}$

5.3 Comparing Edge Operators

6 Effects of noise

Image noise results in pixels that look very different from their neighbors, Generally, the larger the noise the stronger the response.

Smoothing the image should help –it forces pixels to look more like their neighbors.

• step 1: Smooth first $f*g$

• step 2: Partial derivatives $\frac{d}{dx}(f*g)$
  

• step 1: Partial derivatives first, $\frac{d}{dx}g$

• step 2: Filter then, $f*\frac{d}{dx}g$
  

these two methods have the same effect, because we have Differentiation property of convolution

$$\frac{d}{dx}(f*g) = f*\frac{d}{dx}g$$

Smoothing tradeoffs(平滑权衡). Smoothed derivative removes noise, but blurs edge. Also finds edges at different “scales”.

7 2D edge detection filters(总结)

7.1 Derivative of Gaussian filter(高斯一阶导)

7.2 Laplacian of Gaussian (LoG filter, 高斯二阶导)

Step of LoG

• step1: apply LoG to img
• step2: detect zero-crossings in the img
• step3: threshold the zero-crossings to keep only those strong ones(large difference between the positive maximum and negative minimum)

The last step is needed to suppress the weak zero-crossings most likely caused by noise.(需要采取最后一步来抑制最有可能由噪声引起的弱过零点)

7.3 Difference of Gaussians(DoG)

分别用两次高斯filter做差来近似LoG，减少计算量。

Example 1：

Example 2：

8 Parameters(Scale, Threshold)

8.1 scale

• Large scale: larger scale edges detected
• Small scale: finer features detected
  

8.2 Threshold

Choose a threshold value
(1)Set any pixels less than thresh to zero (off)
(2)Set any pixels greater than or equal to thresh to one (on)

9 Canny edge detector

Probably the most widely used edge detector in computer vision.

9.1 Canny边缘检测基本原理：

(1)图象边缘检测必须满足两个条件：一能有效地抑制噪声；二必须尽量精确确定边缘的位置。
(2)根据对信噪比与定位乘积进行测度，得到最优化逼近算子。这就是Canny边缘检测算子。
(3)类似与Marr（LoG）边缘检测方法，也属于先平滑后求导数的方法。

9.2 Canny 的目标是找到一个最优的边缘检测算法

最优边缘检测的含义是：
(1)好的检测 - 算法能够尽可能多地标识出图像中的实际边缘。
(2)好的定位 - 标识出的边缘要尽可能与实际图像中的实际边缘尽可能接近。
(3)最小响应 - 图像中的边缘只能标识一次，并且可能存在的图像雜訊不应标识为边缘。

9.3 Canny Edge Detect Algorithm:

• Step 1: Filter image with derivative of Gaussian (smoothing)
  
• Step 2: Find magnitude and orientation of gradient(用一阶偏导的有限差分来计算梯度的幅值和方向)
  

• Step 3: Non-maximum suppression: (Localization, NMS Algorithm 对梯度幅值进行非极大值抑制)

  图像梯度幅值矩阵中的元素值越大，说明图像中该点的梯度值越大，但这不不能说明该点就是边缘（这仅仅是属于图像增强的过程）。在Canny算法中，非极大值抑制是进行边缘检测的重要步骤，通俗意义上是指寻找像素点局部最大值，将非极大值点所对应的灰度值置为0，这样可以剔除掉一大部分非边缘的点（这是本人的理解）。
  
  根据上图可知，要进行非极大值抑制，就首先要确定像素点C的灰度值在其8值邻域内是否为最大。图1中蓝色的线条方向为C点的梯度方向，这样就可以确定其局部的最大值肯定分布在这条线上，也即出了C点外，梯度方向的交点dTmp1和dTmp2这两个点的值也可能会是局部最大值。因此，判断C点灰度与这两个点灰度大小即可判断C点是否为其邻域内的局部最大灰度点。如果经过判断，C点灰度值小于这两个点中的任一个，那就说明C点不是局部极大值，那么则可以排除C点为边缘。这就是非极大值抑制的工作原理。
          作者认为，在理解的过程中需要注意以下两点：
          (1)中非最大抑制是回答这样一个问题：“当前的梯度值在梯度方向上是一个局部最大值吗？” 所以,要把当前位置的梯度值与梯度方向上两侧的梯度值进行比较；
          (2)梯度方向垂直于边缘方向。
          但实际上，我们只能得到C点邻域的8个点的值，而dTmp1和dTmp2并不在其中，要得到这两个值就需要对该两个点两端的已知灰度进行线性插值，也即根据图1中的g1和g2对dTmp1进行插值，根据g3和g4对dTmp2进行插值，这要用到其梯度方向，这是上文Canny算法中要求解梯度方向矩阵Thita的原因。
          完成非极大值抑制后，会得到一个二值图像，非边缘的点灰度值均为0，可能为边缘的局部灰度极大值点可设置其灰度为128。根据下文的具体测试图像可以看出，这样一个检测结果还是包含了很多由噪声及其他原因造成的假边缘。因此还需要进一步的处理。
  

• Step 4: Linking and thresholding (hysteresis): (Linking, 用双阈值算法检测和连接边缘)
  

  • Define two thresholds: low and high
    
  • Use the high threshold to start edge curves and the low threshold to continue them
    
    

     Canny算法中减少假边缘数量的方法是采用双阈值法。选择两个阈值，根据高阈值得到一个边缘图像，这样一个图像含有很少的假边缘，但是由于阈值较高，产生的图像边缘可能不闭合，未解决这样一个问题采用了另外一个低阈值。
            在高阈值图像中把边缘链接成轮廓，当到达轮廓的端点时，该算法会在断点的8邻域点中寻找满足低阈值的点，再根据此点收集新的边缘，直到整个图像边缘闭合。