图像分割-边缘检测

• 边缘检测
  • 边缘的定义
  • 边缘的分类
  • 边缘检测的代数理解
  • 相关算子
• 图书文献

边缘检测

边缘的定义

• 图像中像素灰度由阶跃变化或屋顶变换的那些像素的集合。

边缘的分类

• 阶跃状:
  • 灰度分布一维阶跃函数
  • 一阶导数：在边缘处取到极值
  • 二阶导数：在边缘处零交叉
• 屋顶状:
  • 灰度分布正态状函数
  • 一阶导数：在边缘处零交叉
  • 二阶导数：在边缘处取到极值

边缘检测的代数理解

相关算子

梯度算子（水平垂直差分法）

• 函数$f(x,y)$在$(x,y)$处的梯度为一个向量

  $\nabla f = \left[ \frac{\partial{f}}{\partial{x}},\frac{\partial{f}}{\partial{y}} \right]$

• 梯度大小为:

  $grad(x,y)=\left[ \left( \frac{\partial{f}}{\partial{x}}\right)^2 +\left( \frac{\partial{f}}{\partial{y}}\right)^2 \right]^{\frac{1}{2}}$

• 也可以近似的表示为

  $grad(x,y)\approx|\partial{f_x} |+|\partial{f_y} |\\[2ex] grad(x,y)\approx \max(|\partial{f_x} |,|\partial{f_y} |);$

• 梯度的方向为$\phi{(x,y)}=\tan^{-1}(\frac{\partial{f_y}}{\partial{f_x}})$

• 梯度分量用模板表示为

  $[-1,1],[-1,1]^T$

• 为了检测边缘点,选取适当的阈值$T$,对梯度图像进行二值化,则形成了一幅边缘二值图像

$g(x,y)= \begin{cases} 1,grad(x,y) \ge T \\ 0,other \end{cases}$

• 特点:仅计算相邻像素的灰度差,对噪声比较敏感,无法抑制噪声的影响.

Roberts算子(45度角对角相差的梯度)

• 公式

$f_x' = |f(x+1,y+1)-f(x-1,y-1)| \\ f_y' = |f(x-1,y+1)-f(x+1,y-1)|$

• 模板

  $\left[ \begin{matrix} -1 & 0 \\ 0 & 1 \end{matrix} \right], \left[ \begin{matrix} 0 & 1 \\ -1 & 0 \end{matrix} \right]$

• 特点:与梯度算子检测边缘的方法类似,对噪声敏感,但效果较梯度算子略好。

PreWitt算子(3*3模板)

• 公式

$f_x'=|f(x+1,y-1)+f(x+1,y)+f(x+1,y+1) \\-f(x-1,y-1)-f(x-1,y)-f(x-1，y+1)|\\ f_y'=|f(x+1,y+1)+f(x,y+1)+f(x-1,y+1) \\-f(x-1,y-1)-f(x,y-1)-f(x+1，y-1)|$

• 计算模板

$\left[ \begin{matrix} -1 & 0 & 1 \\ -1 & 0 & 1 \\ -1 & 0 & 1 \end{matrix} \right], \left[ \begin{matrix} -1 & -1 & -1 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{matrix} \right],$

• 特点:计算梯度的时候考虑了邻域的影响,在检测边缘的同时,能有效抑制噪声.

• Sobel算子(带权邻域来计算梯度,四邻域的权值为2,八邻域的权值为1)

  • 公式
  $f_x'=|f(x+1,y-1)+2f(x+1,y)+f(x+1,y+1) \\-f(x-1,y-1)-2f(x-1,y)-f(x-1，y+1)|\\ f_y'=|f(x+1,y+1)+2f(x,y+1)+f(x-1,y+1) \\-f(x-1,y-1)-2f(x,y-1)-f(x+1，y-1)|$
  • 计算模板
  $\left[ \begin{matrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{matrix} \right], \left[ \begin{matrix} -1 & -2 & -1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{matrix} \right],$
  • 特点:对四领域采用带权方法计算差分,能进一步抑制噪声,但__检测到的边缘较宽__.

Kirsch算子(方向算子，夹角是$\Large \frac{\pi}{4}$)

• 方向模板(八个箭头方向,沿着箭头方向,左边为负,右边为正)

$\left[ \begin{matrix} -5 & 3 & 3 \\ -5 & 0 & 3 \\ -5 & 3 & 3 \end{matrix} \right], \left[ \begin{matrix} 3 & 3 & 3 \\ -5 & 0 & 3 \\ -5 & -5 & 3 \end{matrix} \right], \left[ \begin{matrix} 3 & 3 & 3 \\ 3 & 0 & 3 \\ -5 & -5 & -5 \end{matrix} \right], \left[ \begin{matrix} 3 & 3 & 3 \\ 3 & 0 & -5 \\ 3 & -5 & -5 \end{matrix} \right]\\[4ex] \left[ \begin{matrix} 3 & 3 & -5 \\ 3 & 0 & -5 \\ 3 & 3 & -5 \end{matrix} \right], \left[ \begin{matrix} 3 & -5 & -5 \\ 3 & 0 & -5 \\ 3 & 3 & 3 \end{matrix} \right], \left[ \begin{matrix} -5 & -5 & -5 \\ 3 & 0 & 3 \\ 3 & 3 & 3 \end{matrix} \right], \left[ \begin{matrix} -5 & -5 & 3 \\ -5 & 0 & 3 \\ 3 & 3 & 3 \end{matrix} \right]$

• 该方法用8个算子分别求卷积，取积和运算的最大值为边缘强度,而将与之对应的模板方向作为边缘方向
• 在计算边缘强度的同时可以得到边缘的方向,各方向间的夹角为$\frac{\pi}{4}$.

Nevitia算子(和Kirsch算子类似,夹角是$\Large \frac{\pi}{6}$)

• 方向模板(一共该由十二个模板,就不一个一个抄了)
• 

$\left[ \begin{matrix} -100 & -100 & 0 & 100 & 100 \\ -100 & -100 & 0 & 100 & 100 \\ -100 & -100 & 0 & 100 & 100 \\ -100 & -100 & 0 & 100 & 100 \\ \end{matrix} \right]\\[6ex] \left[ \begin{matrix} -100 & -78 & 92 & 100 & 100 \\ -100 & -100 & 0 & 100 & 100 \\ -100 & -100 & -92 & 78 & 100 \\ -100 & -100 & -100 & -32 & 100 \\ \end{matrix} \right]\\[6ex] \left[ \begin{matrix} -32 & 78 & 100 & 100 & 100 \\ -100 & -92 & 0 & 92 & 100 \\ -100 & -100 & -100 & -78 & 32 \\ -100 & -100 & -100 & -100 & 100 \\ \end{matrix} \right]\\ ...$

拉普拉斯算子

• 对于阶跃边缘,其二阶导数在边缘点出现零交叉，并且在边缘点出两边像素的二阶导数异号.

• 定义:

$\nabla{^2f}=\left[\frac{\partial{^2f}}{\partial{x^2}},\frac{\partial{^2f}}{\partial{y^2}}\right]$

• 离散形式:

$\nabla{^2f(x,y)}=f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y)$

• 计算模板

$\left[ \begin{matrix} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \end{matrix} \right]$

• 优点
  • 各向同性,线性和位移不变的
  • 对细线和孤立点检测效果较好;
• 缺点:
  • 对噪声的敏感,对噪声由双倍加强作用
  • 不能检测出边的方向
  • 常产生双像素的边缘

由于梯度算子和拉普拉斯算子都对噪声敏感，因此一般在用他们检测边缘前要先对图像进行平滑。

由于拉普拉斯算子存在以上受噪音影响较大的缺陷，下面引入Marr算子

Marr算子(高斯+拉普拉斯算子)

• 由于拉普拉斯算子对噪声比较敏感,为了减少噪声影响,可先对图像进行平滑,然后再进行拉普拉斯算子检测边缘.
• 平滑函数采用正态分布的高斯函数,即

$\Large h(x,y)=e^{-\frac{x^2+y^2}{2\sigma{^2}}}$

• 用$h(x,y)$对图像$f(x,y)$的平滑可以表示为

$g(x,y)=h(x,y)\star f(x,y)$

其中$\star$表示卷积。令$r$是离原点的径向距离,即$r^2=x^2+y^2$,对图像$g(x,y)$再采用拉普拉斯算子进行边缘检测.就可以得到

$\begin{aligned} \nabla^2g&=\nabla^2\left[h(x,y)\star f(x,y)\right] = (-\frac{r^2-\sigma^2}{\sigma^4})e^{-\frac{r^2}{2\sigma^2}}\star f(x,y)\\ &=\nabla^2h\star f(x,y) \end{aligned}$

这样,利用二阶导数算子过零点的性质，可确定图像中阶跃边缘的位置.

• $\nabla^h$被称为高斯-拉普拉斯滤波算子,也被称为$LoG$滤波器,或者墨西哥草帽.

• 由于Marr算子的平滑性质能减少噪声,所以当边缘模糊或噪声较大时,利用Marr算子检测过零点提高可靠的边缘位置.
• 在该算子中$\sigma$的选择很重要,$\sigma$小时边缘精度高,但边缘细节变化多;$\sigma$大时平滑作用大,但细节损失大,边缘点定位精度低
• 应该根据噪声水平和边缘定位精度适当选择$\sigma$
• Marr算子的卷积模板一般较大,其半径一般为8 ~ 32.

曲面拟合法

• 出发点：基于差分检测图像边缘的算子往往对噪声敏感.因此对一些噪声比较严重的图像难以取得满意的效果.

• 若采用屏幕或高阶曲面来拟合图像中某一区域的灰度表明,求这个拟合平面或曲面外法方向的微分或二阶微分检测边缘,可减少噪声影响。

• 四点拟合灰度平面法：

  • 若用一个平面$p(x,y)=ax+by+c$来拟合空间四邻像素的灰度值$f(x,y),f(x,y+1),f(x+1,y),f(x+1,y+1)$，则均方差为:
  $\epsilon = \sum{\left[p(x,y)-f(x,y)\right]^2}$
  • 按照均方差最小准则,可以求解参数$a,b,c$.经推导得到(好吧,直接抄下来).
  $\begin{aligned} 2a &= [f(x+1,y)+f(x+1,y+1)] - [f(x,y)+f(x,y+1)] \\ 2b &= [f(x,y+1)+f(x+1,y+1)] - [f(x,y)+f(x+1,y)] \\ 4c &= 3f(x,y)+f(x+1,y)+f(x,y+1) \end{aligned}$
  • $a,b$对应的模板为:
  $\left[ \begin{matrix} -1 & -1 \\ 1 & 1 \end{matrix} \right], \left[ \begin{matrix} -1 & 1 \\ -1 & 1 \end{matrix} \right]$
  • 按照梯度的定义,由平面$p(x,y)=ax+by+c$的偏导数很容易求得梯度,其近似表达式为
  $g(x,y)=|a|+|b|$

  • 特点:

    • 其过程是求平均后再求差分,因而对噪声有抑制作用.
    • 用模板对图像求卷积进行边缘检测,计算$a,b$对应的模板为
    $\frac{1}{2} \left[ \begin{matrix} -1 & -1 \\ 1 & 1 \end{matrix} \right], \frac{1}{2} \left[ \begin{matrix} -1 & 1 \\ -1 & 1 \end{matrix} \right]$

• 线的检测

  • 通过比较模板的卷积和计算值,确定一个点是否正在某个方向上.
  • 模板
  $\left[ \begin{matrix} -1 & -1 & -1 \\ 2 & 2 & 2 \\ -1 & -1 & -1 \end{matrix} \right], \left[ \begin{matrix} -1 & -1 & 2 \\ -1 & 2 & -1 \\ 2 & -1 & -1 \end{matrix} \right], \left[ \begin{matrix} -1 & 2 & -1 \\ -1 & 2 & -1 \\ -1 & 2 & -1 \end{matrix} \right], \left[ \begin{matrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{matrix} \right]$
  • 我们通过计算四个模板的卷积结果,获取最大值是否大于某个门限，来判断是否是某种方向的线条。

图书文献

MOOC《数字图像处理》——武汉大学——7. 图像分割